{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T17:28:13Z","timestamp":1780680493623,"version":"3.54.1"},"reference-count":38,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T00:00:00Z","timestamp":1749081600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Politehnica University of Bucharest, through the PubArt program"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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%.<\/jats:p>","DOI":"10.3390\/a18060344","type":"journal-article","created":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T08:34:32Z","timestamp":1749112472000},"page":"344","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Novel Connected-Components Algorithm for 2D Binarized Images"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2987-4022","authenticated-orcid":false,"given":"Costin-Anton","family":"Boiangiu","sequence":"first","affiliation":[{"name":"Faculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, Romania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1664-3812","authenticated-orcid":false,"given":"Giorgiana-Violeta","family":"Vl\u0103sceanu","sequence":"additional","affiliation":[{"name":"Faculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, Romania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4934-1829","authenticated-orcid":false,"given":"Constantin-Eduard","family":"St\u0103niloiu","sequence":"additional","affiliation":[{"name":"Faculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, Romania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7769-8289","authenticated-orcid":false,"given":"Nicolae","family":"Tarb\u0103","sequence":"additional","affiliation":[{"name":"Faculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, Romania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6764-9125","authenticated-orcid":false,"given":"Mihai-Lucian","family":"Voncil\u0103","sequence":"additional","affiliation":[{"name":"Faculty of Automatic Control and Computers, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, Romania"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.patcog.2017.04.018","article-title":"The connected-component labeling problem: A review of state-of-the-art algorithms","volume":"70","author":"He","year":"2017","journal-title":"Pattern Recognit."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"33240","DOI":"10.1109\/ACCESS.2019.2902579","article-title":"An efficient edge detection approach to provide better edge connectivity for image analysis","volume":"7","author":"Mittal","year":"2019","journal-title":"IEEE Access"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"10839","DOI":"10.1007\/s11042-022-11946-9","article-title":"Improving machine learning recognition of colorectal cancer using 3D GLCM applied to different color spaces","volume":"81","author":"Alqudah","year":"2022","journal-title":"Multimed. Tools Appl."},{"key":"ref_4","first-page":"941","article-title":"Rail Surface Defect Detection Based on Improved UPerNet and Connected Component Analysis","volume":"77","author":"Min","year":"2023","journal-title":"Comput. Mater. Contin."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Gupta, S., Palsetia, D., Patwary, M.M.A., Agrawal, A., and Choudhary, A. (2014, January 19\u201323). A new parallel algorithm for two-pass connected component labeling. Proceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops, Phoenix, AZ, USA.","DOI":"10.1109\/IPDPSW.2014.152"},{"key":"ref_6","unstructured":"Liu, S.C., and Tarjan, R.E. (2018). Simple concurrent labeling algorithms for connected components. arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Zuo, Y., and Zhang, D. (2023, January 8\u201311). Connected Components Labeling Algorithms: A Review. Proceedings of the 2023 9th International Conference on Computer and Communications (ICCC), Chengdu, China.","DOI":"10.1109\/ICCC59590.2023.10507420"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Wu, K., Otoo, E., and Shoshani, A. (2005, January 12\u201317). Optimizing connected component labeling algorithms. Proceedings of the Medical Imaging 2005: Image Processing, San Diego, CA, USA.","DOI":"10.1117\/12.596105"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1999","DOI":"10.1109\/TIP.2019.2946979","article-title":"Spaghetti labeling: Directed acyclic graphs for block-based connected components labeling","volume":"29","author":"Bolelli","year":"2019","journal-title":"IEEE Trans. Image Process."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Tench, D., West, E., Zhang, V., Bender, M.A., Chowdhury, A., Dellas, J.A., Farach-Colton, M., Seip, T., and Zhang, K. (2022, January 12\u201317). GraphZeppelin: Storage-friendly sketching for connected components on dynamic graph streams. Proceedings of the 2022 International Conference on Management of Data, Philadelphia, PA, USA.","DOI":"10.1145\/3514221.3526146"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Schwenk, K., and Huber, M. (2015, January 20). Connected Component Labeling Algorithm for Very Complex and High-Resolution Images on an FPGA Platform. Proceedings of the SPIE Real-Time Image and Video Processing 2015, Baltimore, MD, USA.","DOI":"10.1117\/12.2194101"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bailey, D., and Klaiber, C. (2019). An Efficient Hardware-Oriented Single-Pass Approach for Connected Component Analysis. Sensors, 19.","DOI":"10.3390\/s19143055"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/321556.321570","article-title":"Connectivity in digital pictures","volume":"17","author":"Rosenfeld","year":"1970","journal-title":"J. ACM (JACM)"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bolelli, F., Allegretti, S., Lumetti, L., and Grana, C. (2024). A State-of-the-Art Review with Code about Connected Components Labeling on GPUs. IEEE Trans. Parallel Distrib. Syst., 1\u201320.","DOI":"10.1109\/TPDS.2024.3434357"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/0734-189X(85)90016-7","article-title":"Topological structural analysis of digitized binary images by border following","volume":"30","author":"Suzuki","year":"1985","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"ref_16","unstructured":"Haralock, R.M., and Shapiro, L.G. (1991). Computer and Robot Vision, Addison-Wesley Longman Publishing Co., Inc."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s11554-016-0574-2","article-title":"Parallel Light Speed Labeling: An efficient connected component algorithm for labeling and analysis on multi-core processors","volume":"15","author":"Cabaret","year":"2018","journal-title":"J. Real-Time Image Process."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"He, K., Gkioxari, G., Doll\u00e1r, P., and Girshick, R. (2017, January 22\u201329). Mask R-CNN. Proceedings of the IEEE International Conference on Computer Vision, Venice, Italy.","DOI":"10.1109\/ICCV.2017.322"},{"key":"ref_19","first-page":"103","article-title":"Region-based convolutional neural network for segmenting text in epigraphical images","volume":"1","author":"Preethi","year":"2023","journal-title":"Artif. Intell. Appl."},{"key":"ref_20","unstructured":"Boiangiu, C.-A., Vl\u0103sceanu, G.V., and St\u0103niloiu, C.E. Method for Identifying Connected Components in Binary Images. Romanian Patent Filed at OSIM A\/00599. 30 September 2021. Issued in March 2023, p. 45. Available online: https:\/\/www.osim.ro\/images\/Publicatii\/Inventii\/2023\/inv_03_2023.pdf."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Grana, C., Bolelli, F., Baraldi, L., and Vezzani, R. (2016, January 4\u20138). YACCLAB-yet another connected components labeling benchmark. Proceedings of the 2016 23rd International Conference on Pattern Recognition (ICPR), Cancun, Mexico.","DOI":"10.1109\/ICPR.2016.7900112"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s11554-018-0756-1","article-title":"Toward reliable experiments on the performance of connected components labeling algorithms","volume":"17","author":"Bolelli","year":"2020","journal-title":"J. Real-Time Image Process."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1109\/TPDS.2019.2934683","article-title":"Optimized block-based algorithms to label connected components on GPUs","volume":"31","author":"Allegretti","year":"2019","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1596","DOI":"10.1109\/TIP.2010.2044963","article-title":"Optimized block-based connected components labeling with decision trees","volume":"19","author":"Grana","year":"2010","journal-title":"IEEE Trans. Image Process."},{"key":"ref_25","unstructured":"Grana, C., Baraldi, L., and Bolelli, F. (2016). Optimized connected components labeling with pixel prediction. Advanced Concepts for Intelligent Vision Systems: 17th International Conference, ACIVS 2016, Lecce, Italy, 24\u201327 October 2016, Springer International Publishing."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bolelli, F., Baraldi, L., Cancilla, M., and Grana, C. (2018, January 20\u201324). Connected components labeling on DRAGs. Proceedings of the 2018 24th International Conference on Pattern Recognition (ICPR), Beijing, China.","DOI":"10.1109\/ICPR.2018.8545505"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1434","DOI":"10.1049\/el.2010.2016","article-title":"Stripe-based connected components labelling","volume":"46","author":"Zhao","year":"2010","journal-title":"Electron. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1109\/TIP.2008.919369","article-title":"A run-based two-scan labeling algorithm","volume":"17","author":"He","year":"2008","journal-title":"IEEE Trans. Image Process."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Lee, W., Allegretti, S., Bolelli, F., and Grana, C. (2021, January 16\u201320). Fast Run-Based Connected Components Labeling for Bitonal Images. Proceedings of the 2021 Joint 10th International Conference on Informatics, Electronics & Vision (ICIEV) and 2021 5th International Conference on Imaging, Vision & Pattern Recognition (icIVPR), Kitakyushu, Japan.","DOI":"10.1109\/ICIEVicIVPR52578.2021.9564149"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Maltoni, D., Maio, D., Jain, A.K., and Prabhakar, S. (2009). Handbook of Fingerprint Recognition, Springer.","DOI":"10.1007\/978-1-84882-254-2"},{"key":"ref_31","unstructured":"(2025, May 26). The Hamlet Dataset. Available online: http:\/\/www.gutenberg.org."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Dong, F., Irshad, H., Oh, E.Y., Lerwill, M.F., Brachtel, E.F., Jones, N.C., Knoblauch, N.W., Montaser-Kouhsari, L., Johnson, N.B., and Rao, L.K.F. (2014). Computational pathology to discriminate benign from malignant intraductal proliferations of the breast. PLoS ONE, 9.","DOI":"10.1371\/journal.pone.0114885"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Baltieri, D., Vezzani, R., and Cucchiara, R. (2011, January 1). 3dpes: 3d people dataset for surveillance and forensics. Proceedings of the 2011 Joint ACM Workshop on Human gesture and Behavior Understanding, Scottsdale, AZ, USA.","DOI":"10.1145\/2072572.2072590"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Agam, G., Argamon, S., Frieder, O., Grossman, D., and Lewis, D. (2006). The Complex Document Image Processing (CDIP) Test Collection Project, Illinois Institute of Technology.","DOI":"10.1145\/1148170.1148274"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Lewis, D., Agam, G., Argamon, S., Frieder, O., Grossman, D., and Heard, J. (2006, January 6\u201311). Building a test collection for complex document information processing. Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, WA, USA.","DOI":"10.1145\/1148170.1148307"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Bolelli, F., Borghi, G., and Grana, C. (2017). XDOCS: An application to index historical documents. Italian Research Conference on Digital Libraries, Springer International Publishing.","DOI":"10.1007\/978-3-319-73165-0_15"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Bolelli, F. (2017). Indexing of historical document images: Ad hoc dewarping technique for handwritten text. Italian Research Conference on Digital Libraries, Springer International Publishing.","DOI":"10.1007\/978-3-319-68130-6_4"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Huiskes, M.J., and Lew, M.S. (2008, January 30\u201331). The mir flickr retrieval evaluation. Proceedings of the 1st ACM International Conference on Multimedia Information Retrieval, Vancouver, BC, USA.","DOI":"10.1145\/1460096.1460104"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/6\/344\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:47:01Z","timestamp":1760032021000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/6\/344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,5]]},"references-count":38,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["a18060344"],"URL":"https:\/\/doi.org\/10.3390\/a18060344","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,5]]}}}