A Novel Connected-Components Algorithm for 2D Binarized Images
This paper introduces a new memory-efficient algorithm for connected-components labeling in binary images, which is based on run-length encoding. Unlike conventional pixel-based methods that scan and label individual pixels using global buffers or disjoint-set structures, our approach encodes rows a...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/6/344 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839655100946055168 |
|---|---|
| author | Costin-Anton Boiangiu Giorgiana-Violeta Vlăsceanu Constantin-Eduard Stăniloiu Nicolae Tarbă Mihai-Lucian Voncilă |
| author_facet | Costin-Anton Boiangiu Giorgiana-Violeta Vlăsceanu Constantin-Eduard Stăniloiu Nicolae Tarbă Mihai-Lucian Voncilă |
| author_sort | Costin-Anton Boiangiu |
| collection | DOAJ |
| description | This paper introduces a new memory-efficient algorithm for connected-components labeling in binary images, which is based on run-length encoding. Unlike conventional pixel-based methods that scan and label individual pixels using global buffers or disjoint-set structures, our approach encodes rows as linked segments and merges them using a union-by-size strategy. We accelerate run detection by using a precomputed 16-bit cache of binary patterns, allowing for fast decoding without relying on bitwise CPU instructions. When compared against other run-length encoded algorithms, such as the Scan-Based Labeling Algorithm or Run-Based Two-Scan, our method achieves up to 35% faster on most real-world datasets. While other binary-optimized algorithms, such as Bit-Run Two-Scan and Bit-Merge Run Scan, are up to 45% faster than our algorithm, they require much higher memory usage. Compared to them, our method tends to reduce memory consumption on some large document datasets by up to 80%. |
| format | Article |
| id | doaj-art-dc9d74f831b64d11b3f90c9ae36300d9 |
| institution | Matheson Library |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-dc9d74f831b64d11b3f90c9ae36300d92025-06-25T13:21:24ZengMDPI AGAlgorithms1999-48932025-06-0118634410.3390/a18060344A Novel Connected-Components Algorithm for 2D Binarized ImagesCostin-Anton Boiangiu0Giorgiana-Violeta Vlăsceanu1Constantin-Eduard Stăniloiu2Nicolae Tarbă3Mihai-Lucian Voncilă4Faculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, RomaniaFaculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, RomaniaFaculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, RomaniaFaculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, RomaniaFaculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, RomaniaThis paper introduces a new memory-efficient algorithm for connected-components labeling in binary images, which is based on run-length encoding. Unlike conventional pixel-based methods that scan and label individual pixels using global buffers or disjoint-set structures, our approach encodes rows as linked segments and merges them using a union-by-size strategy. We accelerate run detection by using a precomputed 16-bit cache of binary patterns, allowing for fast decoding without relying on bitwise CPU instructions. When compared against other run-length encoded algorithms, such as the Scan-Based Labeling Algorithm or Run-Based Two-Scan, our method achieves up to 35% faster on most real-world datasets. While other binary-optimized algorithms, such as Bit-Run Two-Scan and Bit-Merge Run Scan, are up to 45% faster than our algorithm, they require much higher memory usage. Compared to them, our method tends to reduce memory consumption on some large document datasets by up to 80%.https://www.mdpi.com/1999-4893/18/6/344connected-component labeling (CCL)binary image processingrun-length encoding (RLE)image segmentationpattern recognitiongraph-based labeling |
| spellingShingle | Costin-Anton Boiangiu Giorgiana-Violeta Vlăsceanu Constantin-Eduard Stăniloiu Nicolae Tarbă Mihai-Lucian Voncilă A Novel Connected-Components Algorithm for 2D Binarized Images Algorithms connected-component labeling (CCL) binary image processing run-length encoding (RLE) image segmentation pattern recognition graph-based labeling |
| title | A Novel Connected-Components Algorithm for 2D Binarized Images |
| title_full | A Novel Connected-Components Algorithm for 2D Binarized Images |
| title_fullStr | A Novel Connected-Components Algorithm for 2D Binarized Images |
| title_full_unstemmed | A Novel Connected-Components Algorithm for 2D Binarized Images |
| title_short | A Novel Connected-Components Algorithm for 2D Binarized Images |
| title_sort | novel connected components algorithm for 2d binarized images |
| topic | connected-component labeling (CCL) binary image processing run-length encoding (RLE) image segmentation pattern recognition graph-based labeling |
| url | https://www.mdpi.com/1999-4893/18/6/344 |
| work_keys_str_mv | AT costinantonboiangiu anovelconnectedcomponentsalgorithmfor2dbinarizedimages AT giorgianavioletavlasceanu anovelconnectedcomponentsalgorithmfor2dbinarizedimages AT constantineduardstaniloiu anovelconnectedcomponentsalgorithmfor2dbinarizedimages AT nicolaetarba anovelconnectedcomponentsalgorithmfor2dbinarizedimages AT mihailucianvoncila anovelconnectedcomponentsalgorithmfor2dbinarizedimages AT costinantonboiangiu novelconnectedcomponentsalgorithmfor2dbinarizedimages AT giorgianavioletavlasceanu novelconnectedcomponentsalgorithmfor2dbinarizedimages AT constantineduardstaniloiu novelconnectedcomponentsalgorithmfor2dbinarizedimages AT nicolaetarba novelconnectedcomponentsalgorithmfor2dbinarizedimages AT mihailucianvoncila novelconnectedcomponentsalgorithmfor2dbinarizedimages |