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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number201784
Journal / PublicationRoyal Society Open Science
Volume8
Issue number3
Online published3 Mar 2021
Publication statusPublished - Mar 2021

Link(s)

Abstract

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 pixelsb; R2 = 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.

Research Area(s)

  • connected components labelling, parallel processing, sequential region labelling