Labeling of connected components in a binary image is one of the most fundamental operations in pattern recognition and computer (or robot) vision. It is indispensable in almost all image-based applications such as fingerprint identification, character recognition, automated inspection, target recognition, face identification, and medical image analysis. Our FLCCL is a raster-scan type which has the great advantage that the running time is less dependent on the number of objects in an image or the complexity of objects. Our FLCCL completes labeling by two raster scans, which is the theoretical lower bound of the number of scans. By the first scan, object pixels are assigned provisional labels, and provisional label dependencies are resolved by our unique set-based analysis together with our efficient equivalent-label-table registration scheme.  By the second scan, all provisional labels assigned to each connected component are replaced with a unique final label by use of the completed label equivalence table. Our FLCCL is a linear-time algorithm, i.e., the running time is linear against the size of a given image; thus, it is suited for applications to large images. Our FLCCL is the fastest connected-component labeling algorithm available to date. More importantly, our algorithm solves the bottleneck problem with labeling, i.e., the running time of our FLCCL is less than that of other fundamental image-processing operations such as thresholding, edge detection, noise reduction, and interpolation. Therefore, labeling does not interfere any longer with real-time applications of pattern-recognition systems.

For technical details, please refer to

He L., Chao Y., Suzuki K., and Wu K., “Fast connected-component labeling.” Pattern Recognition, vol. 42, pp. 1977-1987, 2009.

For related references, please look at:

He L., Chao Y., and Suzuki K., “A run-based two-scan labeling algorithm.” IEEE Transactions on Image Processing, vol. 17, pp. 749-756, 2008.

Suzuki K., Horiba I., and Sugie N., “Linear-time connected-component labeling based on sequential local operations.” Computer Vision and Image Understanding, vol. 89, pp. 1-23, 2003.

File Number: 1531 

Web site: http://suzukilab.uchicago.edu/

Other Information:

How to use FLCCL Software:

The input images should be given in PBM format.  The maximum size of an input image is 4,096 x 4,096.  The maximum number of provisional labels is 1,048,576.

Usage:  flccl INPUT_IMAGE. pbm

An example of labeling of the image baboon.pbm:

Labeling connected components in [     baboon.pbm]...... 

         Running time for labeling: 0.01000[sec]  

Running time with input and output: 0.06000[sec] 

    Number of connected components: 2099

      Number of provisional labels: 4466

                   The output file: baboon.labeled

Web site:

http://suzukilab.uchicago.edu/