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
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.
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,
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|
Bolelli, Federico; Cancilla, Michele; Grana, Costantino
"Two More Strategies to Speed Up Connected Components Labeling Algorithms"
Image Analysis and Processing - ICIAP 2017,
DOI: 10.1007/978-3-319-68548-9_5 Conference
Grana, Costantino; Baraldi, Lorenzo; Bolelli, Federico
"Optimized Connected Components Labeling with Pixel Prediction"
Advanced Concepts for Intelligent Vision Systems,
DOI: 10.1007/978-3-319-48680-2_38 Conference
Grana, Costantino; Bolelli, Federico; Baraldi, Lorenzo; Vezzani, Roberto
"YACCLAB - Yet Another Connected Components Labeling Benchmark"
Proceedings of the 23rd International Conference on Pattern Recognition,
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|