dijkstra3d
dijkstra3d copied to clipboard
seung-lab
Make euclidean_distance_field Faster
Distance field computation seems amenable to a scan-line algorithm and may be a rate-limiting step in Kimimaro.
It's possible to exactly compute the distance in a burst from the point, however, the soon as there is a direction change, a more complex algorithm is needed. Since burst would be far faster than dijkstra and could cover large fractions of a shape, doing a hybrid algorithm would be essentially guaranteed to be faster.
Can we combine dijkstra with serial free space bursts? The problem is that if there's a loop in the structure, duplicate effort may be required to correctly deal with overlapping empty spaces.
Filling then fixing doesn't seem like it makes things much easier. Dijkstra would then have to look for ways to make the field distance larger, but this would cause dijkstra to go haywire.
Might be able to use a similar scanline fill strategy as in fill_voids. However, what would be the stopping criteria? We can try to detect critical regions and stop there?
We got a good speedup for somata, but there's still a lot on the table.
Got another speedup from prefetching (for sufficiently large images).