Back to the research area

Connected Components Labeling

In 2010, research activity on Connected Component Labeling (CCL) algorithms leaded to the development of an open source version of a very fast labeling routine called Block Based with Decision Trees (BBDT). Recently, our research group released YACCLAB (Yet Another Connected Component Labeling Algorithm Benchmark) an open source CCL performance evaluation benchmark which compare the performance of the state of the art labeling algorithms. The benchmarking system confirms the very good performances of the BBDT algorithm which is now the default algorithm included in the OpenCV library. 


labeling 1

Optimized Block-Based labeling with Decision Trees (BBDT)

The BBDT paradigm scans the binary input image in 2 x 2 blocks using an optimal decision tree (both the mask and the tree used by the algorithm are reported in the figure above). Build the decision tree for the blocks mask is hard, because of the large number of possible combination. Thus, we propose a proved optimal strategy to automatically build that tree by means of a dynamic programming approach.

Yet Another Connected Components Labeling Benchmark (YACCLAB)

The YACCLAB project

YACCLAB is an open source C++ project which runs and tests CCL algorithms on a extremely varied collection of public datasets. Beside running a CCL algorithm and testing its correctness, YACCLAB performs four more kinds of test: average run-time test which reports the average execution times of every algorithm and dataset, density and size test in which the performance of the algorithms are evaluated with images of increasing density and size, and memory test which calculate the average memory accesses of an algorithm on a given dataset. To check the correctness of an implementation, the output of an algorithm is compared with that of the Scan Array Union Find (SAUF) algorithm, originally proposed by Wu et al., which is assumed to be a correct reference point.

The YACCLAB dataset

random1 random2 random3 mirflickr1 mirflickr2 mirflickr3
hamlet1 hamlet2 hamlet3 medical1 medical2 medical3
fingerprints2 fingerprints1 fingerprints3 3dpes2 3dpes1 3dpes3

Following a common practice in the literature, we build a dataset that includes both synthetic and real images. The provided dataset is suitable for a wide range of applications, ranging from document processing to survaillance, and features a significant variability in terms of resolution, image density and number of components. All images are provided in 1 bit per pixel PNG format, with 0 (black) being background and 1 (white) being foreground.

Please include the following reference when citing the YACCLAB database:

  • Grana, Costantino; Bolelli, Federico; Baraldi, Lorenzo; Vezzani, Roberto "YACCLAB - Yet Another Connected Components Labeling Benchmark" Proceedings of the 23rd International Conference on Pattern Recognition , Cancun, Mexico, 4-8 Dec 2016, 2016. BibTex

Publications

1 Costantino, Grana; Lorenzo, Baraldi; Federico, Bolelli "Optimized Connected Components Labeling with Pixel Prediction" Advanced Concepts for Intelligent Vision Systems, vol. 10016, Lecce, Italy, pp. 431 -440 , Oct. 24-27, 2016, 2016
DOI: 10.1007/978-3-319-48680-2_38 Conference
2 Grana, Costantino; Bolelli, Federico; Baraldi, Lorenzo; Vezzani, Roberto "YACCLAB - Yet Another Connected Components Labeling Benchmark" Proceedings of the 23rd International Conference on Pattern Recognition, Cancun, Mexico, 4-8 Dec 2016, 2016 Conference
3 C. Grana; M. Montangero; D. Borghesani; R. Cucchiara "Optimal Decision Trees Generation from OR-Decision Tables" Image Analysis and Processing - ICIAP 2011, vol. LNCS 6978, Ravenna, Italy, pp. 443 -452 , Sep 14-16, 2011 Conference
4 C. Grana; D. Borghesani; P. Santinelli; R. Cucchiara "High Performance Connected Components Labeling on FPGA" 2010 Workshops on Database and Expert Systems Applications, Bilbao, Spain, pp. 221 -225 , Sep 1, 2010 Conference
5 C. Grana; D. Borghesani; R. Cucchiara "Optimized Block-based Connected Components Labeling with Decision Trees" IEEE TRANSACTIONS ON IMAGE PROCESSING, vol. 19 (6), pp. 1596 -1609 , 2010 Journal
6 C. Grana; D. Borghesani; R. Cucchiara "Connected component labeling techniques on modern architectures" Image Analysis and Processing - ICIAP 2009, vol. 5716, Vietri sul Mare, Salerno, Italy, pp. 816 -824 , Sep 8-11, 2009 Conference
7 C. Grana; D. Borghesani; R. Cucchiara "Fast Block Based Connected Components Labeling" Proceedings of the IEEE International Conference on Image Processing, Cairo, Egypt, pp. 4061 -4064 , Nov 7-12, 2009 Conference