YACCLAB (Yet Another Connected Components Labeling Benchmark)

YACCLAB provides several types of benchmark tests to evaluate Connected Components Labeling (CCL) algorithms across different performance metrics:

• Average run-time tests: Executes an algorithm on every image of a dataset. Supports multiple repetitions per image to find minimum execution time and allows sequential comparison of multiple algorithms. Outputs include plain text, histogram charts (.pdf/.ps), and LaTeX tables.
• Average run-time tests with steps: Separates allocation/deallocation time from computation time. For multi-scan algorithms, it stores and displays the time for every individual scan.
• Density and size tests: Evaluates performance on the test_random dataset with varying foreground density (10% to 90%) and resolutions (32x32 up to 4096x4096). Outputs include plain text and charts.
• Memory tests: Measures average memory accesses to the label image, the binary image, and data structures used for equivalence solving. It also tracks "other" accesses for extra data structures. Note: These tests use different implementation functions than run-time tests to ensure measurement objectivity.
• Granularity tests: Evaluates algorithms by varying density (1% to 100% in 1% steps) and pixel granularity, while keeping image resolution constant.
• Blocksize tests: Specifically for CUDA algorithms. Uses grid search to find the optimal block size for each kernel. Results are reported in a .csv file containing total execution time in ms for every kernel, dataset, and block size combination.

If you need high-performance Connected Components Labeling (CCL) and do not want to use the full YACCLAB benchmark, you can manually include specific algorithms by adding the necessary source files to your project.

To ensure the code works without modification, you must include the following core files:

1. Base Class & Tensors:

   • labeling_algorithms.h and labeling_algorithms.cc (defines the base class).
   • yacclab_tensor.h and yacclab_tensor.cc (defines input/output data tensors).
   • label_solver.h and label_solver.cc (contains label solving implementations).

2. Support Utilities (required to make the code work without changes):

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

3. Algorithm Specifics:

   • The specific .h and .cc (or .cu for GPU) files for the algorithm you want to use (see the algorithm tables in the documentation for file names).

GPU algorithms are implemented using a .cu file placed in the cuda/src/ folder. The class must extend a GPU-specific labeling class (e.g., GpuLabeling2D<Connectivity2D::CONN_8>).

Key Requirements:

• PerformLabeling(): Implements the labeling logic using d_img_ (OpenCV cuda::GpuMat) and d_img_labels_ (OpenCV cuda::GpuMat). You must call your kernels and ensure cudaDeviceSynchronize() is called at the end.
• PerformLabelingWithSteps(): Similar to the CPU version, uses the perf_ object to record timings for different scan steps.
• PerformLabelingBlocksize(int x, int y, int z): Required for blocksize tests. Use the BLOCKSIZE_KERNEL macro to call kernels while measuring performance.
• Registration: Use REGISTER_LABELING(<algorithm_name>). If the algorithm is used for blocksize tests, you must also use REGISTER_KERNELS(<algorithm_name>, <kernel_name_1>, <kernel_name_2>, ...) to register the kernels used.

// In the .cu file:
__global__ void <kernel_name_1>(...) { ... }

class <algorithm_name> : public GpuLabeling2D<Connectivity2D::CONN_8> {
public:
    void PerformLabeling()
    {
      d_img_labels_.create(d_img_.size(), CV_32SC1);
      <kernel_name_1> <<<...>>> (...);
      cudaDeviceSynchronize();
    }

    void PerformLabelingWithSteps() {
      // Use perf_.start(), perf_.stop(), and perf_.store() as in CPU implementation
    }

    void PerformLabelingBlocksize(int x, int y, int z)
    {
      d_img_labels_.create(d_img_.size(), CV_32SC1);
      BLOCKSIZE_KERNEL(<kernel_name_1>, <grid_size>, <block_size>, <dynamic_shared_mem>, <arguments>...);
    }
};

REGISTER_LABELING(<algorithm_name>);
REGISTER_KERNELS(<algorithm_name>, <kernel_name_1>, <kernel_name_2>, ...);

To add a new CPU algorithm, you must provide a .h header file (in include/) and a .cc source file (in src/).

1. Source File Structure

Use the REGISTER_LABELING_WITH_EQUIVALENCES_SOLVERS(<algorithm_name>) macro (or REGISTER_LABELING if not using a template for the equivalence solver) in your .cc file.

2. Header File Structure

Your class must extend one of the labeling classes (e.g., Labeling2D<Connectivity2D::CONN_8> or Labeling3D). You must implement the following methods:

• PerformLabeling(): The main labeling logic using input img_ (OpenCV Mat1b) and output img_labels_ (OpenCV Mat1i). Use LabelsSolver methods for memory and label management.
• PerformLabelingWithSteps(): Required for step-based performance testing. It should use perf_.start(), perf_.stop(), and perf_.store(Step(StepType::...), ...) to record timings for different stages (e.g., FIRST_SCAN, SECOND_SCAN, ALLOC_DEALLOC).
• PerformLabelingMem(std::vector<uint64_t>& accesses): (Optional) For memory access analysis.

#include "<header_file_name>.h"

REGISTER_LABELING_WITH_EQUIVALENCES_SOLVERS(<algorithm_name>);

// In the header file:
template <typename LabelsSolver>
class <algorithm_name> : public Labeling2D<Connectivity2D::CONN_8> {
public:
    <algorithm_name>() {}

    void PerformLabeling()
    {
      LabelsSolver::Alloc(UPPER_BOUND_8_CONNECTIVITY);
      LabelsSolver::Setup();
      // ... labeling logic ...
      LabelsSolver::GetLabel(<label_id>);
      LabelsSolver::NewLabel();
      LabelsSolver::Flatten();
    }

    void PerformLabelingWithSteps()
    {
      double alloc_timing = Alloc();
      perf_.start();
      FirstScan();
      perf_.stop();
      perf_.store(Step(StepType::FIRST_SCAN), perf_.last());
      // ... other scans ...
      perf_.start();
      Dealloc();
      perf_.stop();
      perf_.store(Step(StepType::ALLOC_DEALLOC), perf_.last() + alloc_timing);
    }
};

To reproduce the experimental results from the paper 'A Heuristic-Based Decision Tree for Connected Components Labeling of 3D Volumes' (ICPR2020) using YACCLAB v3.1, you must configure CMake and the config.yaml file with specific flags and algorithm lists.

CMake Configuration

When running CMake, enable the following flags to support 3D algorithms and EPDT implementations:

• YACCLAB_ENABLE_3D
• YACCLAB_ENABLE_EPDT_19C
• YACCLAB_ENABLE_EPDT_22C
• YACCLAB_ENABLE_EPDT_26C
• YACCLAB_FORCE_CONFIG_GENERATION

Additional CMake Notes:

• OpenCV: CMake should find OpenCV automatically. If it fails, specify the path using the OpenCV_DIR parameter.
• Datasets: Enable YACCLAB_DOWNLOAD_DATASET_3D to have CMake automatically download the required 3D dataset.

Configuration Optimization

To avoid unnecessary tests, it is recommended to disable CPU 2D 8-way connectivity in your config.yaml.

YACCLAB uses a YAML configuration file located in the installation folder to define which tests to run, which datasets to use, and which algorithms to benchmark. The configuration is organized into categories: 2D CPU, 2D GPU, 3D CPU, and 3D GPU.

For each category, you can specify:

• execute: Boolean to enable/disable the category.
• perform: A dictionary of test types to run (e.g., correctness, average, density, memory, blocksize).
• algorithms: A list of algorithm names to include.
• [test_type]_datasets: Lists of datasets specific to a test type (e.g., average_datasets).
• tests_number: Number of runs per test.

Common parameters for all categories include paths (input/output), write_n_labels, color_labels, and save_middle_tests.

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

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

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

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

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

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