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 that enables researchers to test CCL algorithms under extremely variable points of view. Beside running a CCL algorithm and testing its correctness, YACCLAB performs different kind of tests: average run-time test which reports the average execution times of every algorithm and dataset, density, size, and granularity tests in which the performance of the algorithms are evaluated with images of increasing density, size, and granularity and memory tests which calculate the average memory accesses of an algorithm on a given dataset.

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 references when citing the YACCLAB database/project:

  • Bolelli, Federico; Cancilla, Michele; Baraldi, Lorenzo; Grana, Costantino "Towards Reliable Experiments on the Performance of Connected Components Labeling Algorithms" Journal of Real-Time Image Processing, 2018. BibTex.

  • 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 Bolelli, Federico; Cancilla, Michele; Baraldi, Lorenzo; Grana, Costantino "Towards Reliable Experiments on the Performance of Connected Components Labeling Algorithms" JOURNAL OF REAL-TIME IMAGE PROCESSING, pp. 1 -16 , 2018
DOI: 10.1007/s11554-018-0756-1 Journal
2 Bolelli, Federico; Baraldi, Lorenzo; Cancilla, Michele; Grana, Costantino "Connected Components Labeling on DRAGs" Proceedings of the 24th International Conference on Pattern Recognition, Beijing, China, pp. 121 -126 , Aug 20-24, 2018 Conference
3 Bolelli, Federico; Cancilla, Michele; Grana, Costantino "Two More Strategies to Speed Up Connected Components Labeling Algorithms" Image Analysis and Processing - ICIAP 2017, vol. 10485, Catania, pp. 48 -58 , Sep 11-15, 2017
DOI: 10.1007/978-3-319-68548-9_5 Conference
4 Grana, Costantino; Baraldi, Lorenzo; Bolelli, Federico "Optimized Connected Components Labeling with Pixel Prediction" Advanced Concepts for Intelligent Vision Systems, vol. 10016, Lecce, Italy, pp. 431 -440 , Oct 24-27, 2016
DOI: 10.1007/978-3-319-48680-2_38 Conference
5 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, pp. 3109 -3114 , Dec 4-8, 2016
DOI: 10.1109/ICPR.2016.7900112 Conference
6 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
7 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
8 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
9 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
10 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