search

seung-lab / connected-components-3d

Connected components on discrete and continuous multilabel 3D & 2D images. Handles 26, 18, and 6 connected variants; periodic boundaries (4, 8, & 6)
GNU Lesser General Public License v3.0
356 stars 42 forks source link

perf: improve performance for very sparse images #67

Closed william-silversmith closed 3 years ago

william-silversmith commented 3 years ago

We handle a special case where the estimated provisional labels is one. For this case, we know that the foreground is located in a single run on a particular row in the image. We can simply draw these voxels as label 1 in the output rather than running through the traditional passes.

Perhaps this seems uncommon, but for example, this would mean an image containing a single foreground voxel or a line streaking through the image.

This update more than doubles the performance on this type of image from ~800 MVx/sec to ~1900 MVx/sec as measured on an Apple M1.

william-silversmith commented 3 years ago

To be clear this can't compete with SparseCCL (Henniquin et al, 2019) which is about 10x more efficient by taking advantage of already having a list of foreground voxels, but it is probably competitive with one-pass algorithms.

william-silversmith commented 3 years ago

This could be improved. If EPL > 1 and first_foreground = last_foreground, then there is a single row of several runs which can be mapped easily.

william-silversmith commented 3 years ago

There's also the case of EPL = 2 and first foreground != last_foreground where we could simply remap the first as 1 and the second as 2. However, this also requires a check that the two rows are far enough apart to not require interaction.