A Review of World's Fastest Connected Component Labeling Algorithms: Speed and Energy Estimation

Laurent Cabaret (1, 2) , Lionel Lacassagne (1, 2) , Louiza Oudni (1, 2)

1 LRI - Laboratoire de Recherche en Informatique
2 POSTALE - Performance Optimization by Software Transformation and Algorithms & Librairies Enhancement

—Optimizing connected component labeling is cur-rently a very active research field. The current most effective algorithms although close in their design are based on different memory/computation trade-offs. This paper presents a review of these algorithms and a detailed benchmark on several Intel and ARM embedded processors that allows to focus on their advantages and drawbacks and to highlight how processor architecture impact them.

Mots clés: connected component labeling; Rosenfeld; Suzuki; transitive closure; image processing

Domaines: Algorithme et structure de données [cs.DS]; Architectures Matérielles [cs.AR]; Traitement du signal et de l'image [eess.SP]; Vision par ordinateur et reconnaissance de formes [cs.CV]; Automatique / Robotique; Traitement du signal et de l'image [eess.SP]; Arithmétique des ordinateurs; Calcul parallèle, distribué et partagé [cs.DC]; Génie logiciel [cs.SE]; Mathématique discrète [cs.DM]; Robotique [cs.RO]; Traitement des images [eess.IV]

Laurent Cabaret, Lionel Lacassagne, Louiza Oudni. A Review of World's Fastest Connected Component Labeling Algorithms: Speed and Energy Estimation. International Conference on Design and Architectures for Signal and Image Processing, Oct 2014, Madrid, Spain. ⟨10.1109/dasip.2014.7115641⟩. ⟨hal-01081962⟩