How to combine connected labels with multi-label segmentations

[MattTheCuber]

We are trying to replace SciPy's label function with cc3d.connected_components because it is significantly faster. After using connectivity=6 and return_N=true, the only problem we have found so far is that SciPy marks connected labels at different values as the same feature while cc3d does not.

Consider this array:

array([[[2, 1]], [[0, 0]]])

SciPy returns array([[[1, 1]], [[0, 0]]]) while cc3d returns array([[[1, 2]], [[0, 0]]]).

The only way I have found to get around this is using the delta argument. In theory, I would need to set the delta to something really high like float("inf"). However, this throws an error. I also tried really large values like 10000000, but this sometimes results in overflow errors during auto-downcasting. My current workaround is using delta=255 which seems to never error.

Is there a more optimal method to accomplish this?

[william-silversmith]

Hi! That certainly works, though the delta feature uses a somewhat slower algorithm. Scipy treats the input as a binary mask. cc3d was written to accommodate dense segmentation, so you have to convert the input to a binary mask.

import numpy as np
import cc3d

arr = np.array([[[2, 1]], [[0, 0]]], dtype=np.uint16)
np.greater(arr, 0, out=arr) # arr = arr > 0, but memory optimized
cc_labels, N = cc3d.connected_components(arr, connectivity=6, return_N=True)

I think this will do what you want. The binarization step does add overhead, but it should be pretty dang fast.

[MattTheCuber]

I did some tests.

First, I found that np.greater is much faster, as you said. However, this is only the case when using the out argument to overwrite your data.

start = time.time()
res1 = data > 0
print(time.time() - start)

start = time.time()
res2 = np.greater(data, 0)
print(time.time() - start)

start = time.time()
res3 = np.empty_like(data)
np.greater(data, 0, out=res3)
print(time.time() - start)

returns

0.05327296257019043
0.055936336517333984
0.06541633605957031

Then I ran some tests to find which method is fastest using a large segmentation that we use. The results shows that delta is slightly faster (when you need to preserve the original array). However, the difference is marginal and not robust if the segmentation values range greater than 256.

start = time.time()
cc3d.connected_components(data > 0, return_N=True)
print(time.time() - start)

start = time.time()
cc3d.connected_components(data, return_N=True, delta=255)
print(time.time() - start)

start = time.time()
label(data)
print(time.time() - start)

2.6196281909942627
2.227769613265991
50.19565415382385

[william-silversmith]

I'm impressed that the continuous function was faster in this case. The code for the multivalued comparison is more optimized. I'm glad it works for you!

In the future, maybe I should include a special function that treats input images as binary images even if they are continuous. Certain optimizations are possible on binary images that are impossible on multivalued or continuous images.

[MattTheCuber]

That would be fantastic

[william-silversmith]

This feature is released in 3.19.0. Beta, let me know if you run into any problems. You can use it by providing binary_image=True to the function. Note that I haven't used any superior binary algorithms yet, just getting this basic functionality in place.

[MattTheCuber]

That functions properly, thank you.