A fast and adaptive solution for object separation.

A fast and adaptive solution for object separation. (Laurent Bernard, Joseph Baptista, Warren Aim, Rémi Abbal - Reactiv'IP, Linkedin 2021)

Object separation in 2D and 3D images is a major challenge in image processing applications. Even if recent algorithms based on Machine Learning or Deep Learning techniques permit to classify pixels in a much simpler way, the second step consists most of the time in individualizing objects.

The most widely used algorithm to separate objects is based on watershed for decades. This very efficient algorithm most often provides a satisfactory solution. This being said, this process is directly linked to the seed definition which directly impacts the number of objects that will be separated. Therefore, the existing solutions to separate objects from binary images (such as in ITK, FIJI, Avizo, IPSDK, ...) only permit to properly separate similar sized and circular shaped objects.

Successful example for classical watershed separation:

Failing example for classic watershed separation:

This topic has already been widely covered in many papers. These publications led to Munch's implementation (1). This Watershed implementation progressively generates seeds by considering, at each level of the elevation map, the ratio between the object size and the connection thickness to be separated by fracturing. This parameter is then set by the operator. This very efficient implementation is unfortunately based on an iterative approach that often leads to prohibitive processing times (as described in the Benchmarks section at the very end of this article). This algorithm is available in the ImageJ Xlib plugin.

New proposed Approach 

All these studies converge towards the fact that it is essential to find a fast solution to generate seeds in relation with the object size to be separated. To be efficient, this solution must be able to globally generate seeds on the image without requiring the algorithm to locally consider each configuration, which would induce prohibitive computation times.

Reactiv'IP Development Team has solved this challenge with an adaptive version of Watershed Binary function. This algorithm is still based on the distance map to define seeds, however the local maxima dilation is now performed proportionally to the maxima height.

The given parameter in this new function is merely the relative percentage needed to perform the distance map thresholding on each local maximum. For example, if we set this parameter to 0.5 (50%), the seed size used will be 50% of the object size.

To highlight this new algorithm value, a Test Image was artificially generated for this paper. This image contains both elongated shapes and a wide range of object sizes.

Separation test performed with the "traditional" binary separation algorithm

This test highlights that with traditional binary Watershed algorithm, it is impossible to set the dilation parameter to a proper value. Either the small objects are not separated, or the large non-convex objects are incorrectly splitted. 

Separation test performed using the Munch binary separation algorithm (Fiji version)

This test highlights the interest of Munch's segmentation algorithm. The parameter allows to adjust properly the separation process of the objects from this test image. The processing time is about 5s with Fiji (2).

Separation test performed using IPSDK 3.1 adaptive binary separation algorithm

In a very similar way, this test highlights the value of IPSDK 3.1 new adaptive separation algorithm. The parameter allows to properly adapt the processing to separate objects in this test image. The processing time is about 0.07s with IPSDK (2).

Benchmark

To validate the performance of this adaptive algorithm, an additional test was performed on a 1000x1000x1000 voxels dataset (3).

This image was successively processed using Munch's algorithm in Fiji and then using IPSDK 3.1's adaptive separation algorithm. The object separation performance is pretty similar (Number of obtained objects and Histogram of Size). But the processing times are dramatically different (2):

Conclusion

This investigation confirms that IPSDK's adaptive separation algorithm offers a segmentation quality very similar to Munch's algorithm, which was so far the most efficient algorithm to separate 2D or 3D objects in images. In addition, the performed tests demonstrate that the new algorithm generation is definitely more efficient in processing time. The observed average time reduction is about 44 times faster. In addition, its availability in Python and C++ permits a much simpler integration into users' processes.

Availability

The adaptive separation algorithm is available in IPSDK Library V3.1. You can test this algorithm in Python or C++ upon simple request. Please specify whether you want to test it on Windows or Linux. contact@reactivip.com

References

(1)  Munch, B., Gasser, P., Holzer, L., & Flatt, R. (2006). FIB-Nanotomography of Particulate Systems—Part II: Particle Recognition and Effect of Boundary Truncation. Journal of the American Ceramic Society, 89(8), 2586–2595. doi:10.1111/j.1551-2916.2006.01121.x

(2)  PC used : Intel Core I9-10980XE, 3 GHz, Ram 128 Go, 18 Cores, Windows 10 64 bits.

(3) Dataset comes from: Iheb Haffar, Frédéric Flin, Christian Geindreau, Nicolas Petillon, Pierre-Colin Gervais, Vincent Edery, (2021). X-ray tomography for analysis of ice particles in jet A-1 fuel, Powder Technology, volume 384, May 2021, pages 200-210. doi.org/10.1016/j.powtec.2021.01.069