Awesome

Yet Another Connected Components Labeling Benchmark

<!-- ALL-CONTRIBUTORS-BADGE:START - Do not remove or modify this section -->

• <p align="justify"> Allegretti, Stefano; Bolelli, Federico; Grana, Costantino "Optimized Block-Based Algorithms to Label Connected Components on GPUs." IEEE Transactions on Parallel and Distributed Systems, 2019. <a title="BibTex" href="https://federicobolelli.it/pub_files/2019tpds.html">BibTex</a>. <a title="Download" href="https://federicobolelli.it/pub_files/2019tpds.pdf">PDF</a>.</p>
• <p align="justify"> 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. <a title="BibTex" href="https://federicobolelli.it/pub_files/2018jrtip.html">BibTex</a>. <a title="Download" href="https://federicobolelli.it/pub_files/2018jrtip.pdf">PDF</a>.</p>
• <p align="justify"> 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. <a title="BibTex" href="https://federicobolelli.it/pub_files/2016icpr.html">BibTex</a>. <a title="Download" href="https://federicobolelli.it/pub_files/2016icpr.pdf">PDF</a>.</p>

Notice that 8-connectivity is always used in the project.

Reproducible Research

Requirements

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

Installation (refer to the image below)

• <p align="justify">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).</p>
• <p align="justify">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). </p>

• <p align="justify">Set the <a href="#conf">configuration file (config.yaml)</a> placed in the installation folder (bin in this example) in order to select desired tests.</p>
• <p align="justify">Open the project, compile and run it: the work is done!</p>

CMake Configuration Variables

How to include a YACCLAB algorithm into your own project?

2D/3D CPU Algorithms

<a name="I">^I</a> standard version. </br> <a name="II">^II</a> with zero-offset optimization. </br> <a name="III">^III</a> with RLE compression. </br> <a name="IV">^IV</a> only on TTA and UF. </br> <a name="V">^V</a> 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.</br> <a name="VI">^VI</a> 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.</br> <a name="VII">^VII</a> CCL algorithm for images in bitonal (1 bit per pixel) format. When applied to these algorithms, the <i>average</i> tests also consider the time for 1 byte to 1 bit per pixel conversion. On the other hand, when performing <i>average with steps</i> 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;
}

<a name="conf"></a>

Configuration File

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

execute:    true

• <i>perform</i> - dictionary which specifies the <a href="#conf">kind of tests</a> to perform:

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

• <i>correctness_tests</i> - 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      

• <i>tests_number</i> - dictionary which sets the number of runs for each test available:

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

• <i>algorithms</i> - list of algorithms on which apply the chosen tests:

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

• <i>check_datasets</i>, <i>average_datasets</i>, <i>average_ws_datasets</i>, <i>memory_datasets</i> and <i>blocksize_datasets</i>- lists of <a href="#conf">datasets</a> on which, respectively, correctness, average, average_ws, memory and blocksize tests should be run:

...
average_datasets: ["3dpes", "fingerprints", "hamlet", "medical", "mirflickr", "tobacco800", "xdocs"]
...

• <i>blocksize</i> - only for the 2D GPU and 3D GPU categories, this dictionary configures <a href=#blocksize_test>blocksize test</a> parameters. For each axis, a list of three values specifies [<first>, <last>, <step>]:

blocksize:
  x: [2, 64, 2]
  y: [2, 64, 2]
  z: [2, 64, 2]

• <i>paths</i> - dictionary with both input (datasets) and output (results) paths. It is automatically filled by Cmake during the creation of the project:

paths: {input: "<datasets_path>", output: "<output_results_path>"}

• <i>write_n_labels</i> - whether to report the number of connected components in the output files:

write_n_labels: false

• <i>color_labels</i> - whether to output a colored version of labeled images during tests:

color_labels: {average: false, density: false}

• <i>save_middle_tests</i> - dictionary specifying, separately for every test, whether to save the output of single runs, or only a summary of the whole test:

save_middle_tests: {average: false, average_with_steps: false, density: false, granularity: false}

How to Extend YACCLAB with New Algorithms

The source file should be as follows:

#include "<header_file_name>.h"

REGISTER_LABELING_WITH_EQUIVALENCES_SOLVERS(<algorithm_name>);
// Replace the above line with "REGISTER_LABELING(<algorithm_name>);" if the algorithm
// is not template on the equivalence solver algorithm.

The header file should follows the structure below (see <tt>include/labeling_bolelli_2018.h</tt> to have a complete example):

// [...]

template <typename LabelsSolver> // Remove this line if the algorithm is not template 
                                 // on the equivalence solver algorithm
class <algorithm_name> : public Labeling2D<Connectivity2D::CONN_8> { // the class must extend one of the labeling
                                                     // classes Labeling2D, Labeling3D, .. that
                                                     // are template on the connectivity type
                                                    
public:
    <algorithm_name>() {}

    // This member function should implement the labeling procedure reading data from the
    // input image "img_" (OpenCV Mat1b) and storing labels into the output one "img_labels_"
    // (OpenCV Mat1i)
    void PerformLabeling()
    {
      // [...]

      LabelsSolver::Alloc(UPPER_BOUND_8_CONNECTIVITY); // Memory allocation of the labels solver
      LabelsSolver::Setup(); // Labels solver initialization

      // [...]
      
      LabelsSolver::GetLabel(<label_id>) // To get label value from its index
      LabelsSolver::NewLabel(); // To create a new label

      LabelsSolver::Flatten(); // To flatten the equivalence solver array
    }

    // This member function should implement the with step version of the labeling procedure.
    // This is required to perform tests with steps.
    void PerformLabelingWithSteps()
    {

      double alloc_timing = Alloc(); // Alloc() should be a member function responsible
                                     // for memory allocation of the required data structures

      perf_.start();
      FirstScan(); // FirsScan should be a member function that implements the 
                   // first scan step of the algorithm (if it has one)
      perf_.stop();
      perf_.store(Step(StepType::FIRST_SCAN), perf_.last());

      perf_.start();
      SecondScan(); // SecondScan should be a member function that implements the 
                    // second scan step of the algorithm (if it has one)
      perf_.stop();
      perf_.store(Step(StepType::SECOND_SCAN), perf_.last());

      // If the algorithm does not have a distinct firs and second scan replace the lines
      // above with the following ones:
      // perf_.start();
      // AllScans(); // AllScans() should be a member function which implements the entire
                     // algorithm but the allocation/deallocation 
      // perf_.stop();
      // perf_.store(Step(StepType::ALL_SCANS), perf_.last());

      perf_.start();
      Dealloc(); // Dealloc() should be a member function responsible for memory
                 // deallocation.
      perf_.stop();
      perf_.store(Step(StepType::ALLOC_DEALLOC), perf_.last() + alloc_timing);

      // [...]
    }

    // This member function should implement the labeling procedure using the OpenCV Mat
    // wrapper (MemMat) implemented by YACCLAB 
    void PerformLabelingMem(std::vector<uint64_t>& accesses){
      // [...]
    }

}

When implementing a GPU algorithm only the <tt>.cu</tt> file is required. The file should be placed in the <tt>cuda/src</tt> folder. The general structure of a GPU algorithm is the following:

// [...]

// Kernel definitions:

__global__ void <kernel_name_1>(...)
{
  ...
}

__global__ void <kernel_name_2>(...)
{
  ...
}
                                 
class <algorithm_name> : public GpuLabeling2D<Connectivity2D::CONN_8> { // the class must extend one of the labeling
                                                     // classes GpuLabeling2D, GpuLabeling3D, .. that
                                                     // are template on the connectivity type
                                                    
public:
    <algorithm_name>() {}

    // This member function should implement the labeling procedure reading data from the
    // input image "d_img_" (OpenCV cuda::GpuMat) and storing labels into the output one "d_img_labels_"
    // (OpenCV cuda::GpuMat)
    void PerformLabeling()
    {
      // Create the output image
      d_img_labels_.create(d_img_.size(), CV_32SC1);

      // [...]

      // Call necessary kernels
      <kernel_name_1> <<<...>>> (...);

      <kernel_name_2> <<<...>>> (...);

      // [...]
      
      // Wait for the end of the last kernel
      cudaDeviceSynchronize();
    }

    // This member function should implement the with step version of the labeling procedure.
    // This is required to perform tests with steps.
    void PerformLabelingWithSteps()
    {

      double alloc_timing = Alloc(); // Alloc() should be a member function responsible
                                     // for memory allocation of the required data structures

      perf_.start();
      FirstScan(); // FirsScan should be a member function that implements the 
                   // first scan step of the algorithm (if it has one)
      perf_.stop();
      perf_.store(Step(StepType::FIRST_SCAN), perf_.last());

      perf_.start();
      SecondScan(); // SecondScan should be a member function that implements the 
                    // second scan step of the algorithm (if it has one)
      perf_.stop();
      perf_.store(Step(StepType::SECOND_SCAN), perf_.last());

      // If the algorithm does not have a distinct first and second scan replace the lines
      // above with the following ones:
      // perf_.start();
      // AllScans(); // AllScans() should be a member function which implements the entire
                     // algorithm but the allocation/deallocation 
      // perf_.stop();
      // perf_.store(Step(StepType::ALL_SCANS), perf_.last());

      perf_.start();
      Dealloc(); // Dealloc() should be a member function responsible for memory
                 // deallocation.
      perf_.stop();
      perf_.store(Step(StepType::ALLOC_DEALLOC), perf_.last() + alloc_timing);

      // [...]
    }

    void PerformLabelingBlocksize(int x, int y, int z)
    {
      // Create the output image
      d_img_labels_.create(d_img_.size(), CV_32SC1);

      // [...]

      // Call necessary kernels through a macro that measures times separately
      BLOCKSIZE_KERNEL(<kernel_name_1>, <grid_size>, <block_size>, <dynamic_shared_mem>, <arguments>...);

      BLOCKSIZE_KERNEL(<kernel_name_2>, <grid_size>, <block_size>, <dynamic_shared_mem>, <arguments>...);

      // [...]
    }

}

REGISTER_LABELING(<algorithm_name>);

// Only necessary for blocksize test
REGISTER_KERNELS(<algorithm_name>, <kernel_name_1>, <kernel_name_2>, ...);

<a name="datasets"></a>

The YACCLAB Dataset

2D Datasets

• <b>MIRflickr <a href="#MIRFLICKR">[10]</a>:</b><p align="justify"> Otsu-binarized version of the MIRflickr dataset, publicly available under a Creative Commons License. It contains 25,000 standard resolution images taken from Flickr. These images have an average resolution of 0.17 megapixels, there are few connected components (495 on average) and are generally composed of not too complex patterns, so the labeling is quite easy and fast.</p>

• <b>Hamlet:</b><p align="justify"> A set of 104 images scanned from a version of the Hamlet found on Project Gutenberg (http://www.gutenberg.org). Images have an average amount of 2.71 million of pixels to analyze and 1447 components to label, with an average foreground density of 0.0789. </p>

• <b>Tobacco800 <a href="#TOBACCO1">[11]</a>,<a href="#TOBACCO2">[12]</a>:</b><p align="justify"> A set of 1290 document images. It is a realistic database for document image analysis research as these documents were collected and scanned using a wide variety of equipment over time. Resolutions of documents in Tobacco800 vary significantly from 150 to 300 DPI and the dimensions of images range from 1200 by 1600 to 2500 by 3200 pixels. Since CCL is one of the initial preprocessing steps in most layout analysis or OCR algorithms, hamlet and tobacco800 allow to test the algorithm performance in such scenarios. </p>

• <b>3DPeS <a href="#3DPES">[14]</a>:</b> <p align="justify"> It comes from 3DPeS (3D People Surveillance Dataset), a surveillance dataset designed mainly for people re-identification in multi camera systems with non-overlapped fields of view. 3DPeS can be also exploited to test many other tasks, such as people detection, tracking, action analysis and trajectory analysis. The background models for all cameras are provided, so a very basic technique of motion segmentation has been applied to generate the foreground binary masks, i.e., background subtraction and fixed thresholding. The analysis of the foreground masks to remove small connected components and for nearest neighbor matching is a common application for CCL. </p>

• <b>Medical <a href="#MEDICAL">[15]</a>:</b><p align="justify"> This dataset is composed by histological images and allow us to cover this fundamental medical field. The process used for nuclei segmentation and binarization is described in <a href="#MEDICAL">[15]</a>. The resulting dataset is a collection of 343 binary histological images with an average amount of 1.21 million of pixels to analyze and 484 components to label. </p>

• <b>Fingerprints <a href="#FINGERPRINTS">[16]</a>:</b><p align="justify"> This dataset counts 960 fingerprint images collected by using low-cost optical sensors or synthetically generated. These images were taken from the three Verification Competitions FCV2000, FCV2002 and FCV2004. In order to fit CCL application, fingerprints have been binarized using an adaptive threshold and then negated in order to have foreground pixel with value 255. Most of the original images have a resolution of 500 DPI and their dimensions range from 240 by 320 up to 640 by 480 pixels. </p>

• <b>Synthetic Images</b>:
  • <b>Classical <a href="#BBDT">[4]</a></b>:<p align="justify"> A set of synthetic random noise images who contain black and white random noise with 9 different foreground densities (10% up to 90%), from a low resolution of 32x32 pixels to a maximum resolution of 4096x4096 pixels, allowing to test the scalability and the effectiveness of different approaches when the number of labels gets high. For every combination of size and density, 10 images are provided for a total of 720 images. The resulting subset allows to evaluate performance both in terms of scalability on the number of pixels and on the number of labels (density). </p>
  • <b>Granularity <a href="#LSL">[5]</a> </b>:<p align="justify"> This dataset allows to test algorithms varying not only the pixels density but also their granularity <i>g</i> (<i>i.e.</i>, dimension of minimum foreground block), underlying the behaviour of different proposals when the number of provisional labels changes. All the images have a resolution of 2048x2048 and are generated with the Mersenne Twister MT19937 random number generator implemented in the <i>C++</i> standard and starting with a "seed" equal to zero. Density of the images ranges from 0% to 100% with step of 1% and for every density value 16 images with pixels blocks of <i>gxg</i> with <i>g</i> ∈ [1,16] are generated. Moreover, the procedure has been repeated 10 times for every couple of density-granularity for a total of 16160 images.</p>

3D Datasets

• <b>OASIS <a href="#OASIS">[27]</a></b>: <p align="justify"> This is a dataset of medical MRI data taken from the Open Access Series of Imaging Studies (OASIS) project. It consists of 373 volumes of 256 × 256 × 128 pixels, binarized with the Otsu threshold.</p>

• <b>Mitochondria <a href="#MIT1">[28]</a></b>: <p align="justify">It is the Electron Microscopy Dataset, which contains binary sections taken from the CA1 hippocampus for a total of three volumes composed by 165 slices with a resolution of 1024 × 768 pixels.</p>

• <b>Hilbert <a href="#TPDS">[24]</a></b>: <p align="justify">This dataset contains six volumes of 128 × 128 × 128 pixels, filled with the 3D Hilbert curve obtained at different iterations (1 to 6) of the construction method. The Hilbert curve is a fractal space-filling curve that representsa challenging test case for the labeling algorithms.</p>

• <b>Granularity <a href="#TPDS">[24]</a></b>: <p align="justify">It contains 3D synthetic images generated as described for the 2D version. In this case, images have a resolution of 256 x 256 x 256 pixels and only three different images for every couple of density-granularity have been generated.</p>

<a name="tests"></a>

Available Tests

• <b>Average run-time tests:</b> <p align="justify"> execute an algorithm on every image of a dataset. The process can be repeated more times in a single test, to get the minimum execution time for each image: this allows to get more reproducible results and overlook delays produced by other running processes. It is also possible to compare the execution speed of different algorithms on the same dataset: in this case, selected algorithms (see <a href="#conf">Configuration File</a> for more details) are executed sequentially on every image of the dataset. Results are presented in three different formats: a plain text file, histogram charts (.pdf/.ps), either in color or in gray-scale, and a LaTeX table, which can be directly included in research papers.</p>

• <b>Average run-time tests with steps:</b> <p align="justify"> evaluates the performance of an algorithm separating the allocation/deallocation time from the time required to compute labeling. Moreover, if an algorithm employs multiple scans to produce the correct output labels, YACCLAB will store the time of every scan and will display them separately. To understand how YACCLAB computes the memory allocation time for an algorithm on a reference image, it is important to underline the subtleties involved in the allocation process. Indeed, all modern operating systems (not real-time, nor embedded ones, but certainly Windows and Unix) handle virtual memory exploiting a demand paging technique, <i>i.e</i> demand paging with no pre-paging for most of Unix OS and cluster demand paging for Windows OS. This means that a disk page is copied into physical memory only when it is accessed by a process the first time, and not when the allocation function is called. Therefore, it is not possible to calculate the exact allocation time required by an algorithm, which computes CCL on a reference image, but its upper bound can be estimated using the following approach:</p>

  • forcing the allocation of the entire memory by reserving it (<tt>malloc</tt>), filling it with zeros (<tt>memset</tt>), and tracing the time;
  • calculating the time required by the assignment operation (<tt>memset</tt>), and subtracting it from the one obtained at the previous step;
  • repeating the previous points for all data structures needed by an algorithm and summing times together.
  <p align="justify">This will produce an upper bound of the allocation time because caches may reduce the second assignment operation, increasing the estimated allocation time. Moreover, in real cases, CCL algorithms may reserve more memory than they really need, but the <tt>demand paging</tt>, differently from our measuring system, will allocate only the accessed pages.</p>

• <b>Density and size tests:</b> <p align="justify"> check the performance of different CCL algorithms when they are executed on images with varying foreground density and size. To this aim, a list of algorithms selected by the user is run sequentially on every image of the test_random dataset. As for run-time tests, it is possible to repeat this test for more than one run. The output is presented as both plain text and charts(.pdf/.ps). For a density test, the mean execution time of each algorithm is reported for densities ranging from 10% up to 90%, while for a size test the same is reported for resolutions ranging from 32 x 32 up to 4096 x 4096.</p>

• <b>Memory tests:</b> <p align="justify"> are useful to understand the reason for the good performances of an algorithm or in general to explain its behavior. Memory tests compute the average number of accesses to the label image (i.e the image used to store the provisional and then the final labels for the connected components), the average number of accesses to the binary image to be labeled, and, finally, the average number of accesses to data structures used to solve the equivalences between label classes. Moreover, if an algorithm requires extra data, memory tests summarize them as ``other'' accesses and return the average. Furthermore, all average contributions of an algorithm and dataset are summed together in order to show the total amount of memory accesses. Since counting the number of memory accesses imposes additional computations, functions implementing memory access tests are different from those implementing run-time and density tests, to keep run-time tests as objective as possible.</p>

• <b>Granularity tests:</b> <p align="justify"> evaluates an algorithm varying density (from 1% to 100%, using a 1% step) and pixels granularity, but not images resolution. The output results display the average execution time over images with the same density and granularity.</p>

<a name="blocksize_test"></a>

• <b>Blocksize tests:</b> <p align="justify"> this test, which only makes sense for CUDA algorithms, is aimed at finding the best block size for each kernel with grid search parameter optimization. The range of values for each block axis can be specified in the configuration file. Given a set of CUDA algorithms, the blocksize test reports execution times of each kernel on one or multiple datasets, repeating the measurement for every different block size. Results are presented in a csv file. For every kernel, dataset and block size, the total execution time in ms is reported.</p>

Examples of YACCLAB Output Results

Contributors

Thanks goes to these wonderful people (emoji key):

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

References