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.

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, vol. 17, pp. 229 -244 , 2020 \| DOI: 10.1007/s11554-018-0756-1 Journal
2	Bolelli, Federico; Cancilla, Michele; Baraldi, Lorenzo; Grana, Costantino "Connected Components Labeling on DRAGs: Implementation and Reproducibility Notes" Reproducible Research in Pattern Recognition, vol. 11455, Beijing, China, pp. 89 -93 , Aug 20-24, 2019 \| DOI: 10.1007/978-3-030-23987-9_7 Conference
3	Bolelli, Federico; Baraldi, Lorenzo; Cancilla, Michele; Grana, Costantino "Connected Components Labeling on DRAGs" 2018 24th International Conference on Pattern Recognition (ICPR), vol. 2018-, Beijing, China, pp. 121 -126 , Aug 20-24, 2018 \| DOI: 10.1109/ICPR.2018.8545505 Conference
4	Allegretti, Stefano; Bolelli, Federico; Cancilla, Michele; Grana, Costantino "Optimizing GPU-Based Connected Components Labeling Algorithms" 2018 IEEE International Conference on Image Processing, Applications and Systems (IPAS), Inria Sophia Antipolis, France, pp. 175 -180 , Dec 12-14, 2018 \| DOI: 10.1109/IPAS.2018.8708900 Conference
5	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
6	Grana, Costantino; Bolelli, Federico; Baraldi, Lorenzo; Vezzani, Roberto "YACCLAB - Yet Another Connected Components Labeling Benchmark" 2016 23rd International Conference on Pattern Recognition (ICPR), Cancun, Mexico, pp. 3109 -3114 , Dec 4-8, 2016 \| DOI: 10.1109/ICPR.2016.7900112 Conference
7	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
8	Grana, Costantino; Montangero, Manuela; Borghesani, Daniele; Cucchiara, Rita "Optimal Decision Trees Generation from OR-Decision Tables" Image Analysis and Processing - ICIAP 2011, vol. 6978, Ravenna, ita, pp. 443 -452 , Sep 14-16, 2011 \| DOI: 10.1007/978-3-642-24085-0_46 Conference
9	Grana, Costantino; Borghesani, Daniele; Cucchiara, Rita "Optimized Block-based Connected Components Labeling with Decision Trees" IEEE TRANSACTIONS ON IMAGE PROCESSING, vol. 19, pp. 1596 -1609 , 2010 \| DOI: 10.1109/TIP.2010.2044963 Journal
10	Grana, Costantino; Borghesani, Daniele; Santinelli, Paolo; Cucchiara, Rita "High Performance Connected Components Labeling on FPGA" 2010 Workshops on Database and Expert Systems Applications, Bilbao, Spain, pp. 221 -225 , Sep 1, 2010 \| DOI: 10.1109/DEXA.2010.57 Conference
11	Grana, Costantino; Borghesani, Daniele; Cucchiara, Rita "Fast Block Based Connected Components Labeling" Proceedings of the IEEE International Conference on Image Processing, Cairo, egy, pp. 4061 -4064 , Nov 7-12, 2009 \| DOI: 10.1109/ICIP.2009.5413731 Conference
12	Grana, Costantino; Borghesani, Daniele; Cucchiara, Rita "Connected component labeling techniques on modern architectures" Image Analysis and Processing - ICIAP 2009, vol. 5716, Vietri sul Mare, ita, pp. 816 -824 , Sep 8-11, 2009 \| DOI: 10.1007/978-3-642-04146-4_87 Conference

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, vol. 17, pp. 229 -244 , 2020 \| DOI: 10.1007/s11554-018-0756-1 Journal
2	Bolelli, Federico; Cancilla, Michele; Baraldi, Lorenzo; Grana, Costantino "Connected Components Labeling on DRAGs: Implementation and Reproducibility Notes" Reproducible Research in Pattern Recognition, vol. 11455, Beijing, China, pp. 89 -93 , Aug 20-24, 2019 \| DOI: 10.1007/978-3-030-23987-9_7 Conference
3	Bolelli, Federico; Baraldi, Lorenzo; Cancilla, Michele; Grana, Costantino "Connected Components Labeling on DRAGs" 2018 24th International Conference on Pattern Recognition (ICPR), vol. 2018-, Beijing, China, pp. 121 -126 , Aug 20-24, 2018 \| DOI: 10.1109/ICPR.2018.8545505 Conference
4	Allegretti, Stefano; Bolelli, Federico; Cancilla, Michele; Grana, Costantino "Optimizing GPU-Based Connected Components Labeling Algorithms" 2018 IEEE International Conference on Image Processing, Applications and Systems (IPAS), Inria Sophia Antipolis, France, pp. 175 -180 , Dec 12-14, 2018 \| DOI: 10.1109/IPAS.2018.8708900 Conference
5	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
6	Grana, Costantino; Bolelli, Federico; Baraldi, Lorenzo; Vezzani, Roberto "YACCLAB - Yet Another Connected Components Labeling Benchmark" 2016 23rd International Conference on Pattern Recognition (ICPR), Cancun, Mexico, pp. 3109 -3114 , Dec 4-8, 2016 \| DOI: 10.1109/ICPR.2016.7900112 Conference
7	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
8	Grana, Costantino; Montangero, Manuela; Borghesani, Daniele; Cucchiara, Rita "Optimal Decision Trees Generation from OR-Decision Tables" Image Analysis and Processing - ICIAP 2011, vol. 6978, Ravenna, ita, pp. 443 -452 , Sep 14-16, 2011 \| DOI: 10.1007/978-3-642-24085-0_46 Conference
9	Grana, Costantino; Borghesani, Daniele; Cucchiara, Rita "Optimized Block-based Connected Components Labeling with Decision Trees" IEEE TRANSACTIONS ON IMAGE PROCESSING, vol. 19, pp. 1596 -1609 , 2010 \| DOI: 10.1109/TIP.2010.2044963 Journal
10	Grana, Costantino; Borghesani, Daniele; Santinelli, Paolo; Cucchiara, Rita "High Performance Connected Components Labeling on FPGA" 2010 Workshops on Database and Expert Systems Applications, Bilbao, Spain, pp. 221 -225 , Sep 1, 2010 \| DOI: 10.1109/DEXA.2010.57 Conference
11	Grana, Costantino; Borghesani, Daniele; Cucchiara, Rita "Fast Block Based Connected Components Labeling" Proceedings of the IEEE International Conference on Image Processing, Cairo, egy, pp. 4061 -4064 , Nov 7-12, 2009 \| DOI: 10.1109/ICIP.2009.5413731 Conference
12	Grana, Costantino; Borghesani, Daniele; Cucchiara, Rita "Connected component labeling techniques on modern architectures" Image Analysis and Processing - ICIAP 2009, vol. 5716, Vietri sul Mare, ita, pp. 816 -824 , Sep 8-11, 2009 \| DOI: 10.1007/978-3-642-04146-4_87 Conference