Technical Report CSI-0039

A New Algorithm for Parallel Connected-Component Labelling on GPUs with CUDA

D. P. Playne and K. A. Hawick

Archived: 2017

Abstract

Connected-component labelling remains an important and widely-used technique for processing and analysing images and other forms of data in various application areas. Different data sources produce components with different structural features and may be more or less suited to certain connected-component labelling algorithms. Although many efficient serial algorithms exist, determining connected-components on Graphical Processing Units (GPUs) is of interest as many applications use GPUs for processing other parts of the application and labelling on the GPU can avoid expensive memory transfers. The general problem of connected-component labelling and existing GPU algorithms are discussed and a new GPU-based parallel component-labelling algorithm is presented that identifies and eliminates redundant operations in existing algorithms. A set of test-cases with a range of structural features and systems sizes is presented and used to evaluate the new labelling algorithm on modern NVIDIA GPU devices and compare it to existing algorithms. The results of the performance evaluation are presented and show that the new algorithm can provide a meaningful performance improvement over previous methods across a range of test cases.

Keywords: connected-component labelling; GPU;parallel; CUDA

Full Document Text: Not yet available.

Citation Information: BiBTeX database for CSI Notes.

BiBTeX reference:

@TechReport{CSI-0039,
        Title = {A New Algorithm for Parallel Connected-Component Labelling on GPUs with CUDA},
        Author = {D. P. Playne and K. A. Hawick},
        Institution = {Computer Science, Massey University and University of Hull},
        Year = {2017},
        Address = {Cottingham Road, Hull HU6 7RX, UK},
        Month = {April},
        Note = {Sumbitted to Parallel Computing, April 2017},
        Number = {CSI-0039},
        Type = {CSI},
        Keywords = {connected-component labelling; GPU;parallel; CUDA},
        Owner = {kahawick},
        Timestamp = {2017.04.09}
}