Computer Graphics and Visualization • Publications

IEEE Trans Image Process

On GPU Connected Components and Properties: A Systematic Evaluation of Connected Component Labeling Algorithms and Their Extension for Property Extraction

Pedro Asad, Ricardo Marroquim, and Andréa L. e L. Souza

Stacked kernel processing times in Ordinary LE/TM, and stacked kernel overheads due to property computation in Early LE/TM and Late LE/TM measured on four image families (a)-(d), at 8192 × 8192 pixels. For each family member, represented by a point in the x-axes of the respective plot groups (a)-(d), kernel processing times and overheads were averaged over 100 executions. Analogous kernels in LE/TM are colored similarly. The vertical order of the colored stripes does not necessarily reflect the order of operations.

Publisher Paper Cite More

Connected component labeling (CCL) is a fundamental image processing problem that has been studied in many platforms, including GPUs. A common approach to CCL performance analysis is studying the total processing time as a function of abstract image features, like the number of connected components or the fraction of foreground pixels, and input data usually includes synthetic images and segmented video datasets. In this paper, we develop on these ideas and propose an evaluation methodology for GPU CCL algorithms based on synthetic image patterns, addressing the nonexistence of a standard and reliable benchmark in the literature. Our methodology, applied on two important algorithms from existing literature, uncovers their data dependency with great detail, and allows us to model their processing time in three real-world video data sets as functions of abstract, high-level image concepts. We also apply our methodology for studying the memory and performance requirements of two strategies for computing connected component properties: an existing memory-hungry approach, and a new memory-preserving strategy.

More Information

Publisher Paper preprint

Citation

Pedro Asad, Ricardo Marroquim, and Andréa L. e L. Souza, On GPU Connected Components and Properties: A Systematic Evaluation of Connected Component Labeling Algorithms and Their Extension for Property Extraction, IEEE Trans Image Process, 28, pp. 17–31, 2019.

BibTex

@article{bib:asad:2019,
    author       = { Asad, Pedro and Marroquim, Ricardo and L. e L. Souza, Andréa },    
    title        = { On GPU Connected Components and Properties: A Systematic Evaluation of Connected Component Labeling Algorithms and Their Extension for Property Extraction },
    journal      = { IEEE Trans Image Process },
    volume       = { 28 },
    year         = { 2019 },
    pages        = { 17--31 },
    doi          = { 10.1109/TIP.2018.2851445 },
    dblp         = { journals/tip/AsadMS19 },
    url          = { https://publications.graphics.tudelft.nl/papers/121 },
}