Connected Components Labeling (CCL) is a fundamental task in binary image processing. Since its introduction in the sixties, several algorithmic strategies have been proposed to optimize its execution time. Most CCL algorithms in literature, including the current state-of-the-art, are designed to work on an input stored with 1-byte per pixel, even if the most memory-efficient format for a binary input only uses 1-bit per pixel. This paper deals with connected components labeling on 1-bit per pixel images, also known as 1bpp or bitonal images. An existing run-based CCL strategy is adapted to this input format, and optimized with Find First Set hardware operations and a smart management of provisional labels, giving birth to an efficient solution called Bit-Run Two Scan (BRTS). Then, BRTS is further optimized by merging pairs of consecutive lines through bitwise OR, and finding runs on this reduced data. This modification is the basis for another new algorithm on bitonal images, Bit-Merge-Run Scan (BMRS). When evaluated on a public benchmark, the two proposals outperform all the fastest competitors in literature, and therefore represent the new state-of-the-art for connected components labeling on bitonal images.

Fast Run-Based Connected Components Labeling for Bitonal Images / Wonsang, Lee; Allegretti, Stefano; Bolelli, Federico; Grana, Costantino. - (2021). (Intervento presentato al convegno Joint 10th International Conference on Informatics, Electronics and Vision, ICIEV 2021 and 2021 5th International Conference on Imaging, Vision and Pattern Recognition, icIVPR 2021 tenutosi a Kitakyushu, Fukuoka, Japan nel Aug 16-20) [10.1109/ICIEVicIVPR52578.2021.9564149].

Fast Run-Based Connected Components Labeling for Bitonal Images

Allegretti Stefano;Federico Bolelli
;
Grana Costantino
2021

Abstract

Connected Components Labeling (CCL) is a fundamental task in binary image processing. Since its introduction in the sixties, several algorithmic strategies have been proposed to optimize its execution time. Most CCL algorithms in literature, including the current state-of-the-art, are designed to work on an input stored with 1-byte per pixel, even if the most memory-efficient format for a binary input only uses 1-bit per pixel. This paper deals with connected components labeling on 1-bit per pixel images, also known as 1bpp or bitonal images. An existing run-based CCL strategy is adapted to this input format, and optimized with Find First Set hardware operations and a smart management of provisional labels, giving birth to an efficient solution called Bit-Run Two Scan (BRTS). Then, BRTS is further optimized by merging pairs of consecutive lines through bitwise OR, and finding runs on this reduced data. This modification is the basis for another new algorithm on bitonal images, Bit-Merge-Run Scan (BMRS). When evaluated on a public benchmark, the two proposals outperform all the fastest competitors in literature, and therefore represent the new state-of-the-art for connected components labeling on bitonal images.
2021
Joint 10th International Conference on Informatics, Electronics and Vision, ICIEV 2021 and 2021 5th International Conference on Imaging, Vision and Pattern Recognition, icIVPR 2021
Kitakyushu, Fukuoka, Japan
Aug 16-20
Wonsang, Lee; Allegretti, Stefano; Bolelli, Federico; Grana, Costantino
Fast Run-Based Connected Components Labeling for Bitonal Images / Wonsang, Lee; Allegretti, Stefano; Bolelli, Federico; Grana, Costantino. - (2021). (Intervento presentato al convegno Joint 10th International Conference on Informatics, Electronics and Vision, ICIEV 2021 and 2021 5th International Conference on Imaging, Vision and Pattern Recognition, icIVPR 2021 tenutosi a Kitakyushu, Fukuoka, Japan nel Aug 16-20) [10.1109/ICIEVicIVPR52578.2021.9564149].
File in questo prodotto:
File Dimensione Formato  
2021_IVPR_Fast_Run_Based_Connected_Components_Labeling_for_Bitonal_Images.pdf

Open access

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