Connected Components Labeling is an essential step of many Image Processing and Computer Vision tasks. Since the first proposal of a labeling algorithm, which dates back to the sixties, many approaches have optimized the computational load needed to label an image. In particular, the use of decision forests and state prediction have recently appeared as valuable strategies to improve performance. However, due to the overhead of the manual construction of prediction states and the size of the resulting machine code, the application of these strategies has been restricted to small masks, thus ignoring the benefit of using a block-based approach. In this paper, we combine a block-based mask with state prediction and code compression: the resulting algorithm is modeled as a Directed Rooted Acyclic Graph with multiple entry points, which is automatically generated without manual intervention. When tested on synthetic and real datasets, in comparison with optimized implementations of state-of-the-art algorithms, the proposed approach shows superior performance, surpassing the results obtained by all compared approaches in all settings.

Spaghetti Labeling: Directed Acyclic Graphs for Block-Based Connected Components Labeling / Bolelli, Federico; Allegretti, Stefano; Baraldi, Lorenzo; Grana, Costantino. - In: IEEE TRANSACTIONS ON IMAGE PROCESSING. - ISSN 1057-7149. - 29:1(2020), pp. 1999-2012. [10.1109/TIP.2019.2946979]

Spaghetti Labeling: Directed Acyclic Graphs for Block-Based Connected Components Labeling

Federico Bolelli;Stefano Allegretti;Lorenzo Baraldi;Costantino Grana
2020

Abstract

Connected Components Labeling is an essential step of many Image Processing and Computer Vision tasks. Since the first proposal of a labeling algorithm, which dates back to the sixties, many approaches have optimized the computational load needed to label an image. In particular, the use of decision forests and state prediction have recently appeared as valuable strategies to improve performance. However, due to the overhead of the manual construction of prediction states and the size of the resulting machine code, the application of these strategies has been restricted to small masks, thus ignoring the benefit of using a block-based approach. In this paper, we combine a block-based mask with state prediction and code compression: the resulting algorithm is modeled as a Directed Rooted Acyclic Graph with multiple entry points, which is automatically generated without manual intervention. When tested on synthetic and real datasets, in comparison with optimized implementations of state-of-the-art algorithms, the proposed approach shows superior performance, surpassing the results obtained by all compared approaches in all settings.
2020
17-ott-2019
29
1
1999
2012
Spaghetti Labeling: Directed Acyclic Graphs for Block-Based Connected Components Labeling / Bolelli, Federico; Allegretti, Stefano; Baraldi, Lorenzo; Grana, Costantino. - In: IEEE TRANSACTIONS ON IMAGE PROCESSING. - ISSN 1057-7149. - 29:1(2020), pp. 1999-2012. [10.1109/TIP.2019.2946979]
Bolelli, Federico; Allegretti, Stefano; Baraldi, Lorenzo; Grana, Costantino
File in questo prodotto:
File Dimensione Formato  
2018_TIP_Spaghetti Labeling Directed Acyclic Graphs for Block-Based Connected Components Labeling.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 5.55 MB
Formato Adobe PDF
5.55 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1181437
Citazioni
  • ???jsp.display-item.citation.pmc??? 3
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 27
social impact