Yet Another Connected Components Labeling Benchmark

OS	Build	Compiler	OpenCV	CMake	GPU	GitHub Actions	Jenkins
Ubuntu 18.04 LTS	x64	gcc 9.3.0	4.1.2	3.13.5	None		N/A
MacOS (Darwin 19.6.0)	x64	AppleClang 12.0.0 (Xcode-12)	3.1.0	3.13.0	None		N/A
Ubuntu 16.04 LTS	x64	gcc 5.4.0	4.4	3.10.3	2080Ti, CUDA 9.2	N/A
Ubuntu 20.04.02 LTS	x64	gcc 9.3.0	4.4	3.10.3	2080Ti, CUDA 11.4	N/A

Please include the following references when citing the YACCLAB project/dataset:

• Allegretti, Stefano; Bolelli, Federico; Grana, Costantino "Optimized Block-Based Algorithms to Label Connected Components on GPUs." IEEE Transactions on Parallel and Distributed Systems, 2019. BibTex. PDF.

• 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. PDF.

• 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. BibTex. PDF.

YACCLAB is an open source C++ project that enables researchers to test CCL algorithms under extremely variable points of view, running and testing algorithms on a collection of datasets described below. The benchmark performs the following tests which will be described later in this readme: correctness, average run-time (average), average run-time with steps (average_ws), density, size, granularity and memory accesses (memory). Notice that 8-connectivity is always used in the project.

Reproducible Research

This project follows the Reproducible Research paradigms and received the Reproducible Label in Pattern Recognition (RLPR).

To correctly install and run YACCLAB following packages, libraries and utilities are needed: - CMake 3.18 or higher (https://cmake.org); - OpenCV 3.0 or higher (http://opencv.org), required packages are `core`, `imgcodecs`, `imgproc`; - Gnuplot (http://www.gnuplot.info/); - One of your favourite IDE/compiler with C++14 support. GPU algorithms also require: - CUDA Toolkit 9.2 or higher (https://developer.nvidia.com/cuda-toolkit) and OpenCV `cudafeatures2d` package (as of OpenCV 4.5.3, package dependencies entail that required packages for CUDA algorithms are `core`, `cudafeatures2d`, `cudaarithm`, `cudafilters`, `cudaimgproc`, `cudawarping`, `cudev`, `features2d`, `imgcodecs`, `imgproc`). Notes for gnuplot: - on Windows system: be sure add gnuplot to system path if you want YACCLAB automatically generates charts. - on MacOS system: 'pdf terminal' seems to be not available due to old version of cairo, 'postscript' is used instead.

Clone the GitHub repository (HTTPS clone URL: https://github.com/prittt/YACCLAB.git) or simply download the full master branch zip file and extract it (e.g YACCLAB folder).

• Install software in YACCLAB/bin subfolder (suggested) or wherever you want using CMake (point 2 of the example image). Note that CMake should automatically find the OpenCV path whether correctly installed on your OS (3), download the YACCLAB Dataset (be sure to check the box if you want to download it (4a) and (4b) or to select the correct path if the dataset is already on your file system (7)), and create a C++ project for the selected IDE/compiler (9-10). Moreover, if you want to test 3D or GPU algorithms tick the corresponding boxes (5) and (6).

• Set the configuration file (config.yaml) placed in the installation folder (bin in this example) in order to select desired tests.

• Open the project, compile and run it: the work is done!

CMake Configuration Variables

How to include a YACCLAB algorithm into your own project?

If your project requires a Connected Components Labeling algorithm and you are not interested in the whole YACCLAB benchmark you can use the connectedComponent function of the OpenCV library which implements the BBDT and SAUF algorithms since version 3.2., Spaghetti Labeling algorithm and BKE (for GPU only) since version 4.6.

Anyway, when the connectedComponents function is called, a lot of additional code will be executed together with the core function. If your project requires the best performance you can include an algorithm implemented in YACCLAB adding the following files to your project:

1. labeling_algorithms.h and labeling_algorithms.cc which define the base class from which every algorithm derives from;
2. yacclab_tensor.h, yacclab_tensor.cc which define input and output data tensors;
3. label_solver.h and label_solver.cc which cointain the implementation of labels solving algorithms;
4. memory_tester.h, performance_evaluator.h, volume_util.h, volume_util.cc, utilities.h, utilities.cc, system_info.h, system_info.cc, check_labeling.h, check_labeling.cc, file_manager.h, file_manager.cc, stream_demultiplexer.h, config_data.h, register.h, yacclab_test.h, progress_bar.h, cuda_mat3.hpp, cuda_types3.hpp, and cuda_mat3.inl.hpp just to make things work without changing the code;
5. headers and sources files of the required algorithm/s. The association between algorithms and headers/sources files is reported in the tables below.

2D/3D CPU Algorithms

^I standard version.
^II with zero-offset optimization.
^III with RLE compression.
^IV only on TTA and UF.
^V it only copies the pixels from the input image to the output one simply defining a lower bound limit for the execution time of CCL algorithms on a given machine and dataset.
^VI EPDT_19c and EPDT_22c algorithms are based on very big decision trees that translate to many lines of C++ code. They may thus noticeably increase the build time. For this reason, a special flag (YACCLAB_ENABLE_EPDT_ALGOS) to enable/disable such algorithms is provided in the CMake file. By default the flag is OFF.
^VII CCL algorithm for images in bitonal (1 bit per pixel) format. When applied to these algorithms, the average tests also consider the time for 1 byte to 1 bit per pixel conversion. On the other hand, when performing average with steps tests conversion time is ignored.

2D/3D GPU Algorithms

Example of Algorithm Usage Outside the Benchmark

#include "labels_solver.h"
#include "labeling_algorithms.h"
#include "labeling_grana_2010.h" // To include the algorithm code (BBDT in this example)

#include <opencv2/opencv.hpp>

using namespace cv;

int main()
{
    BBDT<UFPC> BBDT_UFPC; // To create an object of the desired algorithm (BBDT in this example)
                          // templated on the labels solving strategy. See the README for the
                          // complete list of the available labels solvers, available algorithms
                          // (N.B. non all the algorithms are templated on the solver) and their
                          // acronyms.

    BBDT_UFPC.img_ = imread("test_image.png", IMREAD_GRAYSCALE); // To load into the CCL object
                                                                 // the BINARY image to be labeled

    threshold(BBDT_UFPC.img_, BBDT_UFPC.img_, 100, 1, THRESH_BINARY); // Just to be sure that the
                                                                      // loaded image is binary

    BBDT_UFPC.PerformLabeling(); // To perform Connected Components Labeling!

    Mat1i output = BBDT_UFPC.img_labels_; // To get the output labeled image  
    unsigned n_labels = BBDT_UFPC.n_labels_; // To get the number of labels found in the input img

    return EXIT_SUCCESS;
}

Configuration File

A YAML configuration file placed in the installation folder lets you specify which kinds of tests should be performed, on which datasets and on which algorithms. Four categories of algorithms are supported: 2D CPU, 2D GPU, 3D CPU and 3D GPU. For each of them, the configuration parameters are reported below.

• execute - boolean value which specifies whether the current category of algorithms will be tested:

  execute:    true

• perform - dictionary which specifies the kind of tests to perform:

  perform:
  correctness:        false
  average:            true
  average_with_steps: false
  density:            false
  granularity:        false
  memory:             false
  blocksize:          false 

• correctness_tests - dictionary indicating the kind of correctness tests to perform:

  correctness_tests:
  eight_connectivity_standard:  true
  eight_connectivity_steps:     true
  eight_connectivity_memory:    true
  eight_connectivity_blocksize: true      

• tests_number - dictionary which sets the number of runs for each test available:

  tests_number:
  average:            10
  average_with_steps: 10
  density:            10
  granularity:        10

• algorithms - list of algorithms on which apply the chosen tests:

  algorithms:
  - SAUF_RemSP
  - SAUF_TTA
  - BBDT_RemSP
  - BBDT_UFPC
  - CT
  - labeling_NULL

• check_datasets, average_datasets, average_ws_datasets, memory_datasets and blocksize_datasets- lists of datasets on which, respectively, correctness, average, average_ws, memory and blocksize tests should be run:

  Federico Bolelli 💻 📆 🚧 🚇 🤔	Stefano Allegretti 💻 🚧 🐛 🤔 🚇	Costantino Grana 💻 📆 🤔 🚇	Michele Cancilla 💻 📦 🚧	Lorenzo Baraldi 💻 📦	Maximilian Söchting 💻
  patrickhwood 🐛	WalnutVision 🐛

  This project follows the all-contributors specification. Contributions of any kind welcome.

  References

  [1]	F. Chang, C.-J. Chen, and C.-J. Lu, “A linear-time component-labeling algorithm using contour tracing technique,” Computer Vision and Image Understanding, vol. 93, no. 2, pp. 206–220, 2004.
  [2]	W.-Y. Chang, C.-C. Chiu, and J.-H. Yang, “Block-based connected-component labeling algorithm using binary decision trees,” Sensors, vol. 15, no. 9, pp. 23 763–23 787, 2015.
  [3]	L. Di Stefano and A. Bulgarelli, “A Simple and Efficient Connected Components Labeling Algorithm,” in International Conference on Image Analysis and Processing. IEEE, 1999, pp. 322–327.
  [4]	C. Grana, D. Borghesani, and R. Cucchiara, “Optimized Block-based Connected Components Labeling with Decision Trees,” IEEE Transac-tions on Image Processing, vol. 19, no. 6, pp. 1596–1609, 2010.
  [5]	L. Lacassagne and B. Zavidovique, “Light speed labeling: efficient connected component labeling on risc architectures,” Journal of Real-Time Image Processing, vol. 6, no. 2, pp. 117–135, 2011.
  [6]	K. Wu, E. Otoo, and K. Suzuki, "Optimizing two-pass connected-component labeling algorithms,” Pattern Analysis and Applications," vol. 12, no. 2, pp. 117–135, 2009.
  [7]	L. He, X. Zhao, Y. Chao, and K. Suzuki, "Configuration-Transition-Based Connected-Component Labeling", IEEE Transactions on Image Processing, vol. 23, no. 2, pp. 943–951, 2014.
  [8]	H. Zhao, Y. Fan, T. Zhang, and H. Sang, "Stripe-based connected components labelling," Electronics letters, vol. 46, no. 21, pp. 1434–1436, 2010.
  [9]	C. Grana, L. Baraldi, and F. Bolelli, "Optimized Connected Components Labeling with Pixel Prediction," in Advanced Concepts for Intelligent Vision Systems, 2016, pp. 431-440.
  [10]	M. J. Huiskes and M. S. Lew, “The MIR Flickr Retrieval Evaluation,” in MIR ’08: Proceedings of the 2008 ACM International Conference on Multimedia Information Retrieval. New York, NY, USA: ACM, 2008.
  [11]	G. Agam, S. Argamon, O. Frieder, D. Grossman, and D. Lewis, “The Complex Document Image Processing (CDIP) Test Collection Project,” Illinois Institute of Technology, 2006.
  [12]	D. Lewis, G. Agam, S. Argamon, O. Frieder, D. Grossman, and J. Heard, “Building a test collection for complex document information processing,” in Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 2006, pp. 665–666.
  [13]	F. Bolelli, M. Cancilla, L. Baraldi, C. Grana, "Towards Reliable Experiments on the Performance of Connected Components Labeling Algorithms," Journal of Real-Time Image Processing, 2018.
  [14]	D. Baltieri, R. Vezzani, and R. Cucchiara, “3DPeS: 3D People Dataset for Surveillance and Forensics,” in Proceedings of the 2011 joint ACM workshop on Human gesture and behavior understanding. ACM, 2011, pp. 59–64.
  [15]	F. Dong, H. Irshad, E.-Y. Oh, M. F. Lerwill, E. F. Brachtel, N. C. Jones, N. W. Knoblauch, L. Montaser-Kouhsari, N. B. Johnson, L. K. Rao et al., “Computational Pathology to Discriminate Benign from Malignant Intraductal Proliferations of the Breast,” PloS one, vol. 9, no. 12, p. e114885, 2014.
  [16]	D. Maltoni, D. Maio, A. Jain, and S. Prabhakar, "Handbook of fingerprint recognition", Springer Science & Business Media, 2009.
  [17]	C.Grana, F.Bolelli, L.Baraldi, and R.Vezzani, "YACCLAB - Yet Another Connected Components Labeling Benchmark," Proceedings of the 23rd International Conference on Pattern Recognition, Cancun, Mexico, 4-8 Dec 2016, 2016.
  [18]	V. Oliveira and R. Lotufo, "A study on connected components labeling algorithms using GPUs," in SIBGRAPI. vol. 3, p. 4, 2010.
  [19]	O. Kalentev, A. Rai, S. Kemnitz, R. Schneider," Connected component labeling on a 2D grid using CUDA," in Journal of Parallel and Distributed Computing 71(4), 615–620, 2011.
  [20]	S. Zavalishin, I. Safonov, Y. Bekhtin, I. Kurilin, "Block Equivalence Algorithm for Labeling 2D and 3D Images on GPU," in Electronic Imaging 2016(2), 1–7, 2016.
  [21]	L. Cabaret, L. Lacassagne, D. Etiemble, "Distanceless Label Propagation: an Efficient Direct Connected Component Labeling Algorithm for GPUs," in Seventh International Conference on Image Processing Theory, Tools and Applications, IPTA, 2017.
  [22]	S. Allegretti, F. Bolelli, M. Cancilla, C. Grana, "Optimizing GPU-Based Connected Components Labeling Algorithms," in Third IEEE International Conference on Image Processing, Applications and Systems, IPAS, 2018.
  [23]	F. Bolelli, L. Baraldi, M. Cancilla, C. Grana, "Connected Components Labeling on DRAGs," in International Conference on Pattern Recognition, 2018, pp. 121-126.
  [24]	S. Allegretti, F. Bolelli, C. Grana, "Optimized Block-Based Algorithms to Label Connected Components on GPUs," in IEEE Transactions on Parallel and Distributed Systems, 2019.
  [25]	P. Chen, H. Zhao, C. Tao, H. Sang, "Block-run-based connected component labelling algorithm for gpgpu using shared memory." Electronics Letters, 2011
  [26]	F. Bolelli, S. Allegretti, L. Baraldi, and C. Grana, "Spaghetti Labeling: Directed Acyclic Graphs for Block-Based Bonnected Components Labeling," IEEE Transactions on Image Processing, vol. 29, no. 1, pp. 1999-2012, 2019.
  [27]	D. S. Marcus, A. F. Fotenos, J. G. Csernansky, J. C. Morris, R. L. Buckner, “Open Access Series of Imaging Studies (OASIS): Longitudinal MRI Data in Nondemented and Demented OlderAdults,” J. Cognitive Neurosci., vol. 22, no. 12, pp. 2677–2684, 2010.
  [28]	A. Lucchi, Y. Li, and P. Fua, “Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 1987–1994.
  [29]	S. Allegretti, F, Bolelli, M. Cancilla, F. Pollastri, L. Canalini, C. Grana, "How does Connected Components Labeling with Decision Trees perform on GPUs?," In 18th International Conference on Computer Analysis of Images and Patterns, 2019.
  [30]	L. He, Y. Chao, K. Suzuki. "A run-based two-scan labeling algorithm." IEEE Transactions on Image Processing, 2008.
  [31]	M. Söchting, S. Allegretti, F. Bolelli, C. Grana. "A Heuristic-Based Decision Tree for Connected Components Labeling of 3D Volumes." 25th International Conference on Pattern Recognition, 2021
  [32]	W. Lee, F. Bolelli, S. Allegretti, C. Grana. "Fast Run-Based Connected Components Labeling for Bitonal Images." 5th International Conference on Imaging, Vision & Pattern Recognition, 2021
  [33]	F. Bolelli, S. Allegretti, C. Grana. "One DAG to Rule Them All." IEEE Transactions on Pattern Analisys and Machine Intelligence, 2021
  [34]	F. N. Paravecino, D. Kaeli, "Accelerated Connected Component Labeling Using CUDA Framework." International Conference on Computer Vision and Graphics, ICCVG, 2014
  [35]	A. Hennequin, L. Lacassagne, L. Cabaret, Q. Meunier, "A new Direct Connected Component Labeling and Analysis Algorithms for GPUs", DASIP, 2018
  [36]	Y. So, H. Ashraf, Y. Hae, I. Kim, "Fast Parallel Connected Component Labeling Algorithm Using CUDA Based On 8-Directional Label Selection", International Journal of Latest Research in Science and Technology, 2014
  [37]	A. Rasmusson, T.S. Sørensen, G. Ziegler, "Connected Components Labeling on the GPU with Generalization to Voronoi Diagrams and Signed Distance Fields", International Symposium on Visual Computing, 2013
  [38]	O. Stava, B. Benes, "Connected Components Labeling in CUDA", GPU Computing Gems, 2011
  [39]	K. Yonehara, K. Aizawa, "A Line-Based Connected Component Labeling Algorithm Using GPUs", Third International Symposium on Computing and Networking, 2015