Multithreaded two-pass connected components labelling and particle analysis in ImageJ

Sequential region labelling, also known as connected components labelling, is a standard image segmentation problem that joins contiguous foreground pixels into blobs. Despite its long development history and widespread use across diverse domains such as bone biology, materials science and geology, connected components labelling can still form a bottleneck in image processing pipelines. Here, I describe a multithreaded implementation of classical two-pass sequential region labelling and introduce an efficient collision resolution step, 'bucket fountain'. Code was validated on test images and against commercial software (Avizo). It was performance tested on images from 2 MB (161 particles) to 6.5 GB (437 508 particles) to determine whether theoretical linear scaling (O(n)) had been achieved, and on 1-40 CPU threads to measure speed improvements due to multithreading. The new implementation achieves linear scaling (b = 0.905-1.052, time proportional to pixels(b); R-2 = 0.985-0.996), which improves with increasing thread number up to 8-16 threads, suggesting that it is memory bandwidth limited. This new implementation of sequential region labelling reduces the time required from hours to a few tens of seconds for images of several GB, and is limited only by hardware scale. It is available open source and free of charge in BoneJ.

Automated summary

Sequential region labelling, also known as connected components labelling, is a standard image segmentation problem that can be a bottleneck in image processing pipelines. A new implementation using multithreading achieves linear scaling and reduces processing time for large images from hours to seconds.