{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T17:44:41Z","timestamp":1776879881783,"version":"3.51.2"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,3,4]],"date-time":"2008-03-04T00:00:00Z","timestamp":1204588800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Pattern Anal Applic"],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s10044-008-0109-y","type":"journal-article","created":{"date-parts":[[2008,3,3]],"date-time":"2008-03-03T08:13:28Z","timestamp":1204532008000},"page":"117-135","source":"Crossref","is-referenced-by-count":241,"title":["Optimizing two-pass connected-component labeling algorithms"],"prefix":"10.1007","volume":"12","author":[{"given":"Kesheng","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ekow","family":"Otoo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenji","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,3,4]]},"reference":[{"key":"109_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal PK, Arge L, Ke Yi (2006) I\/O-efficient batched union-find and its applications to terrain analysis. In: SCG \u201906: Proceedings of the 22nd annual symposium on computational geometry. ACM Press, New York, pp 167\u2013176","DOI":"10.1145\/1137856.1137884"},{"key":"109_CR2","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison\u2013Wesley, Reading"},{"key":"109_CR3","volume-title":"Data structures and algorithms","author":"AV Aho","year":"1983","unstructured":"Aho AV, Ullman JD, Hopcroft JE (1983) Data structures and algorithms. Addison\u2013Wesley, Reading"},{"issue":"10","key":"109_CR4","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1109\/34.159904","volume":"14","author":"HM Alnuweiri","year":"1992","unstructured":"Alnuweiri HM, Prasanna VK (1992) Parallel architectures and algorithms for image component labeling. IEEE Trans Pattern Anal Mach Intell 14(10):1014\u20131034","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"109_CR5","unstructured":"Alstrup S, Ben-Amram AM, Rauhe T (1999) Worst-case and amortised optimality in union-find. In: Proceedings of 31th Annual ACM symposium on theory of computing (STOC\u201999). ACM Press, New York, pp 499\u2013506"},{"issue":"3","key":"109_CR6","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s100440070009","volume":"3","author":"A Amin","year":"2000","unstructured":"Amin A, Fisher S (2000) A document skew detection method using the Hough transform. Pattern Anal Appl 3(3):243\u2013253","journal-title":"Pattern Anal Appl"},{"key":"109_CR7","volume-title":"Comput vision","author":"DH Ballard","year":"1982","unstructured":"Ballard DH (1982) Computer vision. Prentice-Hall, Englewood"},{"key":"109_CR8","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s B, Simon I (1985) On the expected behavior of disjoint set union algorithms. In: STOC \u201985: Proceedings of the 17th annual ACM symposium on theory of computing. ACM Press, New York, pp 224\u2013231","DOI":"10.1145\/22145.22171"},{"issue":"2","key":"109_CR9","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.cviu.2003.09.002","volume":"93","author":"F Chang","year":"2004","unstructured":"Chang F, Chen C-J, Lu C-J (2004) A linear-time component-labeling algorithm using contour tracing technique. Comput Vis Image Underst 93(2):206\u2013220","journal-title":"Comput Vis Image Underst"},{"issue":"2","key":"109_CR10","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/128749.128750","volume":"39","author":"MB Dillencourt","year":"1992","unstructured":"Dillencourt MB, Samet H, Tamminen M (1992) A general approach to connected-component labeling for arbitrary image representations. J ACM 39(2):253\u2013280","journal-title":"J ACM"},{"issue":"5","key":"109_CR11","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/0020-0190(76)90061-2","volume":"5","author":"J Doyle","year":"1976","unstructured":"Doyle J, Rivest RL (1976) Linear expected time of a simple union-find algorithm. Inf Process Lett 5(5):146\u2013148","journal-title":"Inf Process Lett"},{"issue":"2","key":"109_CR12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0304-3975(94)00262-2","volume":"154","author":"C Fiorio","year":"1996","unstructured":"Fiorio C, Gustedt J (1996) Two linear time union-find strategies for image processing. Theor Comput Sci 154(2):165\u2013181","journal-title":"Theor Comput Sci"},{"key":"109_CR13","doi-asserted-by":"crossref","unstructured":"Fiorio C, Gustedt J (1997) Memory management for union-find algorithms. In: Proceedings of 14th symposium on theoretical aspects of computer Science. Springer, New York, pp 67\u201379","DOI":"10.1007\/BFb0023449"},{"key":"109_CR14","doi-asserted-by":"crossref","unstructured":"Gabow HN, Tarjan RE (1983) A linear-time algorithm for a special case of disjoint set union. In: STOC \u201983: Proceedings of the 15th annual ACM symposium on theory of computing. ACM Press, New York, pp 246\u2013251","DOI":"10.1145\/800061.808753"},{"issue":"3","key":"109_CR15","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/116873.116878","volume":"23","author":"Z Galil","year":"1991","unstructured":"Galil Z, Italiano GF (1991) Data structures and algorithms for disjoint set union problems. ACM Comput Surv 23(3):319\u2013344","journal-title":"ACM Comput Surv"},{"issue":"5","key":"109_CR16","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/364099.364331","volume":"7","author":"BA Galler","year":"1964","unstructured":"Galler BA, Fisher MJ (1964) An improved equivalence algorithm. Commun ACM 7(5):301\u2013303","journal-title":"Commun ACM"},{"key":"109_CR17","volume-title":"Digital image processing","author":"RC Gonzalez","year":"2002","unstructured":"Gonzalez RC, Woods RE (2002) Digital Image Processing, 2nd edn. Prentice-Hall, New Jersy","edition":"2"},{"key":"109_CR18","doi-asserted-by":"crossref","unstructured":"Gotoh T, Ohta Y, Yoshida M, Shirai Y (1987) Component labeling algorithm for video rate processing. In: Proceedings of SPIE 1987. Advances in image processing, vol 804, pp 217\u2013224","DOI":"10.1117\/12.941317"},{"key":"109_CR19","volume-title":"Some neighborhood operations","author":"RM Haralick","year":"1981","unstructured":"Haralick RM (1981) Some neighborhood operations. Plenum Press, New York, pp 11\u201335"},{"issue":"1","key":"109_CR20","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0734-189X(85)90153-7","volume":"29","author":"RM Haralick","year":"1985","unstructured":"Haralick RM, Shapiro LG (1985) Image segmentation techniques. Comput Vis Graph Image Process 29(1):100\u2013132","journal-title":"Comput Vis Graph Image Process"},{"issue":"1","key":"109_CR21","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s100440170021","volume":"4","author":"H Hayashi","year":"2001","unstructured":"Hayashi H, Kudo M, Toyama J, Shimbo M (2001) Fast labelling of natural scenes using enhanced knowledge. Pattern Anal Appl 4(1):20\u201327","journal-title":"Pattern Anal Appl"},{"key":"109_CR22","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1016\/j.cviu.2005.04.001","volume":"99","author":"H Qingmao","year":"2005","unstructured":"Qingmao H, Guoyu Q, Nowinski WL (2005) Fast connected-component labelling in three-dimensional binary images based on iterative recursion. Comput Vis Image Underst 99:414\u2013434","journal-title":"Comput Vis Image Underst"},{"issue":"4","key":"109_CR23","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1007\/s100440070003","volume":"3","author":"J-H Kim","year":"2000","unstructured":"Kim J-H, Kim KK, Suen CY (2000) An HMM-MLP hybrid model for cursive script recognition. Pattern Anal Appl 3(4):314\u2013324","journal-title":"Pattern Anal Appl"},{"issue":"2","key":"109_CR24","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1006\/jpdc.1997.1420","volume":"49","author":"F Knop","year":"1998","unstructured":"Knop F, Rego V (1998) Parallel labeling of three-dimensional clusters on networks of workstations. J Parallel Distrib Comput 49(2):182\u2013203","journal-title":"J Parallel Distrib Comput"},{"key":"109_CR25","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0304-3975(78)90009-9","volume":"6","author":"DE Knuth","year":"1978","unstructured":"Knuth DE, Sch\u00f6nhage A (1978) The expected linearity of a simple equivalence algorithm. Theor Comput Sci 6:281\u2013315","journal-title":"Theor Comput Sci"},{"issue":"5","key":"109_CR26","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1137\/0219060","volume":"19","author":"JM Lucas","year":"1990","unstructured":"Lucas JM (1990) Postorder disjoint set union is linear. SIAM J Comput 19(5):868\u2013882","journal-title":"SIAM J Comput"},{"issue":"2","key":"109_CR27","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0734-189X(83)90113-5","volume":"23","author":"R Lumia","year":"1983","unstructured":"Lumia R (1983) A new three-dimensional connected components algorithm. Comput Vis Graph Image Process 23(2):207\u2013217","journal-title":"Comput Vis Graph Image Process"},{"issue":"2","key":"109_CR28","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0734-189X(83)90071-3","volume":"22","author":"R Lumia","year":"1983","unstructured":"Lumia R, Shapiro L, Zungia O (1983) A new connected components algorithm for virtual memory computers. Comput Vis Graph Image Process 22(2):287\u2013300","journal-title":"Comput Vis Graph Image Process"},{"issue":"5","key":"109_CR29","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1109\/34.589204","volume":"19","author":"AN Moga","year":"1997","unstructured":"Moga AN, Gabbouj M (1997) Parallel image component labeling with watershed transformations. IEEE Trans Pattern Anal Mach Intell 19(5):441\u2013450","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"109_CR30","unstructured":"Naoi S (1995) High-speed labeling method using adaptive variable window size for character shape feature. In: IEEE Asian Conference on computer vision, vol 1, pp 408\u2013411"},{"key":"109_CR31","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/TSMC.1979.4310076","volume":"9","author":"N Otsu","year":"1979","unstructured":"Otsu N (1979) A threshold selection method from gray level histograms. IEEE Trans Syst Man Cybern 9:62\u201366","journal-title":"IEEE Trans Syst Man Cybern"},{"issue":"8","key":"109_CR32","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1109\/TPAMI.2002.1023801","volume":"24","author":"E Regentova","year":"2002","unstructured":"Regentova E, Latifi S, Deng S, Yao D (2002) An algorithm with reduced operations for connected components detection in itu-t group 3\/4 coded images. IEEE Trans Pattern Anal Mach Intell 24(8):1039\u20131047","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"1","key":"109_CR33","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/321556.321570","volume":"17","author":"A Rosenfeld","year":"1970","unstructured":"Rosenfeld A (1970) Connectivity in digital pictures. J ACM 17(1):146\u2013160","journal-title":"J ACM"},{"key":"109_CR34","volume-title":"Digital picture processing","author":"A Rosenfeld","year":"1982","unstructured":"Rosenfeld A, Kak AC (1982) Digital picture processing, 2nd edn. Academic Press, San Diego","edition":"2"},{"issue":"8","key":"109_CR35","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22(8):888\u2013905","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"109_CR36","volume-title":"Comput Vis","author":"GC Stockman","year":"2001","unstructured":"Stockman GC, Shapiro LG (2001) Computer Vision. Prentice-Hall, Englewood"},{"issue":"1","key":"109_CR37","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/s100440200005","volume":"5","author":"JS Suri","year":"2002","unstructured":"Suri JS, Singh B, Reden L (2002) Computer vision and pattern recognition techniques for 2-d and 3-d MR cerebral cortical segmentation: a state-of-the-art review. Pattern Analy Appl 5(1):46\u201376","journal-title":"Pattern Analy Appl"},{"issue":"1","key":"109_CR38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S1077-3142(02)00030-9","volume":"89","author":"K Suzuki","year":"2003","unstructured":"Suzuki K, Horiba I, Sugie N (2003) Linear-time connected-component labeling based on sequential local operations. Comput Vis Image Underst 89(1):1\u201323","journal-title":"Comput Vis Image Underst"},{"issue":"2","key":"109_CR39","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"RE Tarjan","year":"1984","unstructured":"Tarjan RE, van Leeuwen J (1984) Worst-case analysis of set union algorithms. J ACM 31(2):245\u2013281","journal-title":"J ACM"},{"issue":"2","key":"109_CR40","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan RE (1975) Efficiency of a good but not linear set union algorithm. J ACM 22(2):215\u2013225","journal-title":"J ACM"},{"key":"109_CR41","doi-asserted-by":"crossref","unstructured":"Tarjan RE (1977) Reference machines require non-linear time to maintain disjoint sets. In: STOC \u201977: Proceedings of the 9th annual ACM symposium on theory of computing. ACM Press, pp 18\u201329","DOI":"10.1145\/800105.803392"},{"issue":"3","key":"109_CR42","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0734-189X(90)90008-J","volume":"51","author":"JK Udupa","year":"1990","unstructured":"Udupa JK, Ajjanagadde VG (1990) Boundary and object labelling in three-dimensional images. Comput Vis Graph Image Process 51(3):355\u2013369","journal-title":"Comput Vis Graph Image Process"},{"key":"109_CR43","first-page":"353","volume":"19","author":"K-B Wang","year":"2003","unstructured":"Wang K-B, Chia T-L, Chen Z, Lou D-C (2003) Parallel execution of a connected component labeling operation on a linear array architecture. J Inf Sci Eng 19:353\u2013370","journal-title":"J Inf Sci Eng"},{"issue":"2","key":"109_CR44","first-page":"163","volume":"12","author":"Y Wang","year":"2003","unstructured":"Wang Y, Bhattacharya P (2003) Using connected components to guide image understanding and segmentation. Mach Graph Vis 12(2):163\u2013186","journal-title":"Mach Graph Vis"},{"key":"109_CR45","doi-asserted-by":"crossref","unstructured":"Wu K, Otoo E, Shoshani A (2005) Optimizing connected component labeling algorithms. In: Proceedings of SPIE medical imaging conference 2005, San Diego, CA, 2005. LBNL report LBNL-56864","DOI":"10.1117\/12.596105"},{"issue":"1","key":"109_CR46","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1137\/0214010","volume":"14","author":"AC Yao","year":"1985","unstructured":"Yao AC (1985) On the expected performance of path compression algorithms. SIAM J Comput 14(1):129\u2013133","journal-title":"SIAM J Comput"},{"key":"109_CR47","unstructured":"Yapa RD, Koichi H (2007) A connected component labeling algorithm for grayscale images and application of the algorithm on mammograms. In: SAC\u201907: Proceedings of the 2007 ACM symposium on applied computing. ACM Press, New York, pp 146\u2013152"}],"container-title":["Pattern Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10044-008-0109-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10044-008-0109-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10044-008-0109-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T04:02:27Z","timestamp":1559102547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10044-008-0109-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,4]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["109"],"URL":"https:\/\/doi.org\/10.1007\/s10044-008-0109-y","relation":{},"ISSN":["1433-7541","1433-755X"],"issn-type":[{"value":"1433-7541","type":"print"},{"value":"1433-755X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,4]]}}}