Parallel light speed labeling: An efficient connected component labeling algorithm for multi-core processors

Lionel Lacassagne (1, 2) , Laurent Cabaret (2, 3) , Daniel Etiemble (3, 2)

1 ALSOC - Architecture et Logiciels pour Systèmes Embarqués sur Puce
2 LRI - Laboratoire de Recherche en Informatique
3 POSTALE - Performance Optimization by Software Transformation and Algorithms & Librairies Enhancement

The paper introduces the parallel version of the Light Speed Labeling (LSL) and compares it with the parallel versions of the competitors. A benchmark shows that the parallel Light Speed Labeling is at least ×1.9 faster than all the other algo- rithms for random images. This factor reach ×3.6 for structured random images. More important, we show that thanks to its run-based processing (segments), LSL is intrinsically more efficient than all pixel-based algorithms.

Keywords: connected component labeling; transitive closure; union-find; bounding box; connected component analysis; parallel algorithm

Domains: Data Structures and Algorithms [cs.DS]; Hardware Architecture [cs.AR]; Image Processing [eess.IV]; Signal and Image Processing; Computer Vision and Pattern Recognition [cs.CV]; Automatic; Signal and Image processing; Computer Arithmetic; Distributed, Parallel, and Cluster Computing [cs.DC]; Discrete Mathematics [cs.DM]; Robotics [cs.RO]

Lionel Lacassagne, Laurent Cabaret, Daniel Etiemble. Parallel light speed labeling: An efficient connected component labeling algorithm for multi-core processors. IEEE International Conference on Image Processing (ICIP 2015), Sep 2015, Quebec, Canada. pp.3486-3489, ⟨10.1109/ICIP.2015.7351452⟩. ⟨hal-01243310⟩