{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T08:18:04Z","timestamp":1743063484241,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031133237"},{"type":"electronic","value":"9783031133244"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-13324-4_11","type":"book-chapter","created":{"date-parts":[[2022,8,3]],"date-time":"2022-08-03T20:21:50Z","timestamp":1659558110000},"page":"119-131","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Run-Based Connected Component Labeling Algorithm for\u00a0Processing Holes"],"prefix":"10.1007","author":[{"given":"Florian","family":"Lemaitre","sequence":"first","affiliation":[]},{"given":"Nathan","family":"Maurice","sequence":"additional","affiliation":[]},{"given":"Lionel","family":"Lacassagne","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"11_CR1","unstructured":"Bailey, D., Johnston, C.: Single pass connected component analysis. In: Image and Vision New Zeland (IVNZ), pp. 282\u2013287 (2007)"},{"issue":"45","key":"11_CR2","first-page":"1","volume":"5","author":"DG Bailey","year":"2019","unstructured":"Bailey, D.G., Klaiber, M.J.: Zig-zag based single-pass connected components analysis. J. Imaging 5(45), 1\u201326 (2019)","journal-title":"J. Imaging"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1999","DOI":"10.1109\/TIP.2019.2946979","volume":"29","author":"F Bolelli","year":"2020","unstructured":"Bolelli, F., Allegretti, S., Baraldi, L., Grana, C.: Spaghetti labeling: directed acyclic graphs for block-based connected components labeling. IEEE Trans. Image Process. 29, 1999\u20132012 (2020)","journal-title":"IEEE Trans. Image Process."},{"issue":"2","key":"11_CR4","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s11554-018-0756-1","volume":"17","author":"F Bolelli","year":"2018","unstructured":"Bolelli, F., Cancilla, M., Baraldi, L., Grana, C.: Toward reliable experiments on the performance of Connected Components Labeling algorithms. J. Real-Time Image Process. 17(2), 229\u2013244 (2018). https:\/\/doi.org\/10.1007\/s11554-018-0756-1","journal-title":"J. Real-Time Image Process."},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Cabaret, L., Lacassagne, L.: What is the world\u2019s fastest connected component labeling algorithm? In: IEEE International Workshop on Signal Processing Systems (SiPS), pp. 97\u2013102 (2014)","DOI":"10.1109\/SiPS.2014.6986069"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s11554-016-0574-2","volume":"15","author":"L Cabaret","year":"2018","unstructured":"Cabaret, L., Lacassagne, L., Etiemble, D.: Parallel light speed labeling for connected component analysis on multi-core processors. J. Real-Time Image Process. (JRTIP) 15(1), 173\u2013196 (2018)","journal-title":"J. Real-Time Image Process. (JRTIP)"},{"issue":"3","key":"11_CR7","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1145\/116873.116878","volume":"23","author":"Z Galil","year":"1991","unstructured":"Galil, Z., Italiano, G.: Data structures and algorithms for disjoint set union problems. ACM Comput. Surv. 23(3), 319\u2013344 (1991)","journal-title":"ACM Comput. Surv."},{"issue":"5","key":"11_CR8","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1109\/T-C.1971.223289","volume":"20","author":"SB Gray","year":"1971","unstructured":"Gray, S.B.: Local properties of binary images in two dimensions. Trans. Comput. 20(5), 551\u2013561 (1971)","journal-title":"Trans. Comput."},{"issue":"9","key":"11_CR9","first-page":"2725","volume":"24","author":"L He","year":"2017","unstructured":"He, L., Chao, Y.: A very fast algorithm for simultaneously performing connected-component labeling and Euler number computing. Trans. Image Process. 24(9), 2725\u20132735 (2017)","journal-title":"Trans. Image Process."},{"key":"11_CR10","unstructured":"He, L., Chao, Y., Suzuki, K.: A new algorithm for labeling connected-components and calculating the Euler number, connected-component number, and hole number. In: International Conference on Pattern Recognition (ICPR), pp. 3099\u20133102 (2012)"},{"issue":"3","key":"11_CR11","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/s11390-013-1348-y","volume":"28","author":"L He","year":"2013","unstructured":"He, L., Chao, Y., Suzuki, K.: An algorithm for connected-component labeling, hole labeling and Euler number computing. J. Comput. Sci. Technol. 28(3), 468\u2013478 (2013)","journal-title":"J. Comput. Sci. Technol."},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.patcog.2017.04.018","volume":"70","author":"L He","year":"2017","unstructured":"He, L., Ren, X., Gao, Q., Zhao, X., Yao, B., Chao, Y.: The connected-component labeling problem: a review of state-of-the-art algorithms. Pattern Recogn. 70, 25\u201343 (2017)","journal-title":"Pattern Recogn."},{"issue":"4","key":"11_CR13","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1007\/s11554-016-0626-7","volume":"16","author":"L He","year":"2016","unstructured":"He, L., Ren, X., Zhao, X., Yao, B., Kasuya, H., Chao, Y.: An efficient two-scan algorithm for computing basic shape features of objects in a binary image. J. Real-Time Image Proc. 16(4), 1277\u20131287 (2016)","journal-title":"J. Real-Time Image Proc."},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Hennequin, A., Masliah, I., Lacassagne, L.: Designing efficient SIMD algorithms for direct connected component labeling. In: ACM Workshop on Programming Models for SIMD\/Vector Processing (PPoPP), pp. 1\u20138 (2019)","DOI":"10.1145\/3303117.3306164"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Hennequin, A., Meunier, Q.L., Lacassagne, L., Cabaret, L.: A new direct connected component labeling and analysis algorithm for GPUs. In: IEEE International Conference on Design and Architectures for Signal and Image Processing (DASIP), pp. 1\u20136 (2018)","DOI":"10.1109\/DASIP.2018.8596835"},{"issue":"4","key":"11_CR16","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1007\/s11554-016-0610-2","volume":"16","author":"MJ Klaiber","year":"2019","unstructured":"Klaiber, M.J., Bailey, D.G., Simon, S.: A single-cycle parallel multi-slice connected components analysis hardware architecture. J. Real-Time Image Proc. 16(4), 1165\u20131175 (2019)","journal-title":"J. Real-Time Image Proc."},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Lacassagne, L., Zavidovique, A.B.: Light speed labeling for RISC architectures. In: IEEE International Conference on Image Analysis and Processing (ICIP) (2009)","DOI":"10.1109\/ICIP.2009.5414352"},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s11554-009-0134-0","volume":"6","author":"L Lacassagne","year":"2011","unstructured":"Lacassagne, L., Zavidovique, B.: Light speed labeling: efficient connected component labeling on RISC architectures. J. Real-Time Image Process. (JRTIP) 6(2), 117\u2013135 (2011)","journal-title":"J. Real-Time Image Process. (JRTIP)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Lemaitre, F., Hennequin, A., Lacassagne, L.: How to speed connected component labeling up with SIMD RLE algorithms. In: ACM Workshop on Programming Models for SIMD\/Vector Processing (PPoPP), pp. 1\u20138 (2020)","DOI":"10.1145\/3380479.3380481"},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/978-3-642-14390-8_20","volume-title":"Parallel Processing and Applied Mathematics","author":"F Manne","year":"2010","unstructured":"Manne, F., Patwary, M.M.A.: A scalable parallel union-find algorithm for distributed memory computers. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds.) PPAM 2009. LNCS, vol. 6067, pp. 186\u2013195. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14390-8_20"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-13193-6_35","volume-title":"Experimental Algorithms","author":"MMA Patwary","year":"2010","unstructured":"Patwary, M.M.A., Blair, J., Manne, F.: Experiments on union-find algorithms for the disjoint-set data structure. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 411\u2013423. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13193-6_35"},{"issue":"6","key":"11_CR22","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1109\/TPDS.2018.2799216","volume":"29","author":"DP Playne","year":"2018","unstructured":"Playne, D.P., Hawick, K.: A new algorithm for parallel connected-component labelling on GPUs. IEEE Trans. Parallel Distrib. Syst. 29(6), 1217\u20131230 (2018)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-030-10828-1_7","volume-title":"Computational Topology in Image Context","author":"F D\u00edaz del R\u00edo","year":"2019","unstructured":"D\u00edaz del R\u00edo, F., Molina-Abril, H., Real, P.: Computing the component-labeling and the adjacency tree of a binary digital image in near logarithmic-time. In: Marfil, R., Calder\u00f3n, M., D\u00edaz del R\u00edo, F., Real, P., Bandera, A. (eds.) CTIC 2019. LNCS, vol. 11382, pp. 82\u201395. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10828-1_7"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.patrec.2019.11.039","volume":"131","author":"FD del Rio","year":"2020","unstructured":"del Rio, F.D., Sanchez-Cuevas, P., Molina-Abril, H., Real, P.: Parallel connected-component-labeling based on homotopy trees. Pattern Recogn. Lett. 131, 71\u201378 (2020)","journal-title":"Pattern Recogn. Lett."},{"issue":"8","key":"11_CR25","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1080\/00029890.1979.11994873","volume":"28","author":"A Rosenfeld","year":"1979","unstructured":"Rosenfeld, A.: Digital topology. Am. Math. Mon. 28(8), 621\u2013360 (1979)","journal-title":"Am. Math. Mon."},{"issue":"4","key":"11_CR26","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1145\/321356.321357","volume":"13","author":"A Rosenfeld","year":"1966","unstructured":"Rosenfeld, A., Platz, J.: Sequential operator in digital pictures processing. J. ACM 13(4), 471\u2013494 (1966)","journal-title":"J. ACM"},{"key":"11_CR27","unstructured":"Somasundaram, K., Kalaiselvi, T.: A method for filling holes in objects of medical images using region labeling and run length encoding schemes. In: National Conference on Image Processing (NCIMP), pp. 110\u2013115 (2010)"},{"issue":"1","key":"11_CR28","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s11554-016-0590-2","volume":"15","author":"JW Tang","year":"2016","unstructured":"Tang, J.W., Shaikh-Husin, N., Sheikh, U.U., Marsono, M.N.: A linked list run-length-based single-pass connected component analysis for real-time embedded hardware. J. Real-Time Image Proc. 15(1), 197\u2013215 (2016)","journal-title":"J. Real-Time Image Proc."},{"issue":"2","key":"11_CR29","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R Tarjan","year":"1975","unstructured":"Tarjan, R.: Efficiency of good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975)","journal-title":"J. ACM"},{"key":"11_CR30","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R Tarjan","year":"1984","unstructured":"Tarjan, R., Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM 31, 245\u2013281 (1984)","journal-title":"J. ACM"},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s10044-008-0109-y","volume":"12","author":"K Wu","year":"2009","unstructured":"Wu, K., Otoo, E., Suzuki, K.: Optimizing two-pass connected-component labeling algorithms. Pattern Anal. Appl. 12, 117\u2013135 (2009)","journal-title":"Pattern Anal. Appl."},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Yao, B., He, L., Kang, S., Zhao, X., Chao, Y.: Bit-quad-based Euler number computing. IEICE Trans. Inf. Syst. E100.D(9), 2197\u20132204 (2017)","DOI":"10.1587\/transinf.2017EDP7012"},{"key":"11_CR33","doi-asserted-by":"publisher","first-page":"1715","DOI":"10.4028\/www.scientific.net\/AMM.433-435.1715","volume":"433\u2013435","author":"H Zhao","year":"2013","unstructured":"Zhao, H., Chen, Z.X.: A simple hole filling algorithm for binary cell images. Appl. Mech. Mater. 433\u2013435, 1715\u20131719 (2013)","journal-title":"Appl. Mech. Mater."}],"container-title":["Lecture Notes in Computer Science","Image Analysis and Processing. ICIAP 2022 Workshops"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-13324-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T19:05:56Z","timestamp":1666465556000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-13324-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031133237","9783031133244"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-13324-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"4 August 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICIAP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Image Analysis and Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lecce","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 May 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 May 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iciap2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iciap2021.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Microsoft","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"307","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"168","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"55% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}