In this paper we introduce a new Connected Components Labeling (CCL) algorithm which exploits a novel approach to model decision problems as Directed Acyclic Graphs with a root, which will be called Directed Rooted Acyclic Graphs (DRAGs). This structure supports the use of sets of equivalent actions, as required by CCL, and optimally leverages these equivalences to reduce the number of nodes (decision points). The advantage of this representation is that a DRAG, differently from decision trees usually exploited by the state-of-the-art algorithms, will contain only the minimum number of nodes required to reach the leaf corresponding to a set of condition values. This combines the benefits of using binary decision trees with a reduction of the machine code size. Experiments show a consistent improvement of the execution time when the model is applied to CCL.

Connected Components Labeling on DRAGs / Bolelli, Federico; Baraldi, Lorenzo; Cancilla, Michele; Grana, Costantino. - 2018-:(2018), pp. 121-126. (Intervento presentato al convegno 24th International Conference on Pattern Recognition, ICPR 2018 tenutosi a Beijing, China nel Aug 20-24) [10.1109/ICPR.2018.8545505].

Connected Components Labeling on DRAGs

Bolelli, Federico;Baraldi, Lorenzo;Cancilla, Michele;Grana, Costantino
2018

Abstract

In this paper we introduce a new Connected Components Labeling (CCL) algorithm which exploits a novel approach to model decision problems as Directed Acyclic Graphs with a root, which will be called Directed Rooted Acyclic Graphs (DRAGs). This structure supports the use of sets of equivalent actions, as required by CCL, and optimally leverages these equivalences to reduce the number of nodes (decision points). The advantage of this representation is that a DRAG, differently from decision trees usually exploited by the state-of-the-art algorithms, will contain only the minimum number of nodes required to reach the leaf corresponding to a set of condition values. This combines the benefits of using binary decision trees with a reduction of the machine code size. Experiments show a consistent improvement of the execution time when the model is applied to CCL.
2018
29-nov-2018
24th International Conference on Pattern Recognition, ICPR 2018
Beijing, China
Aug 20-24
2018-
121
126
Bolelli, Federico; Baraldi, Lorenzo; Cancilla, Michele; Grana, Costantino
Connected Components Labeling on DRAGs / Bolelli, Federico; Baraldi, Lorenzo; Cancilla, Michele; Grana, Costantino. - 2018-:(2018), pp. 121-126. (Intervento presentato al convegno 24th International Conference on Pattern Recognition, ICPR 2018 tenutosi a Beijing, China nel Aug 20-24) [10.1109/ICPR.2018.8545505].
File in questo prodotto:
File Dimensione Formato  
2018_ICPR_Connected_Components_Labeling_on_DRAGs.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 688.67 kB
Formato Adobe PDF
688.67 kB 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/1159834
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 14
social impact