{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:09:45Z","timestamp":1767182985078,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2019,4,6]],"date-time":"2019-04-06T00:00:00Z","timestamp":1554508800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Imaging"],"abstract":"<jats:p>Single-pass connected components analysis (CCA) algorithms suffer from a time overhead to resolve labels at the end of each image row. This work demonstrates how this overhead can be eliminated by replacing the conventional raster scan by a zig-zag scan. This enables chains of labels to be correctly resolved while processing the next image row. The effect is faster processing in the worst case with no end of row overheads. CCA hardware architectures using the novel algorithm proposed in this paper are, therefore, able to process images at higher throughput than other state-of-the-art methods while reducing the hardware requirements. The latency introduced by the conversion from raster scan to zig-zag scan is compensated for by a new method of detecting object completion, which enables the feature vector for completed connected components to be output at the earliest possible opportunity.<\/jats:p>","DOI":"10.3390\/jimaging5040045","type":"journal-article","created":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T11:54:52Z","timestamp":1554724492000},"page":"45","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Zig-Zag Based Single-Pass Connected Components Analysis"],"prefix":"10.3390","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1025-3680","authenticated-orcid":false,"given":"Donald G.","family":"Bailey","sequence":"first","affiliation":[{"name":"Department of Mechanical and Electrical Engineering, School of Food and Advanced Technology, Massey University, Palmerston North 4442, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8286-7000","authenticated-orcid":false,"given":"Michael J.","family":"Klaiber","sequence":"additional","affiliation":[{"name":"Independent Researcher, 70176 Stuttgart, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,6]]},"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":"206","DOI":"10.1016\/j.cviu.2003.09.002","article-title":"A linear-time component-labeling algorithm using contour tracing technique","volume":"93","author":"Chang","year":"2004","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"AbuBaker, A., Qahwaji, R., Ipson, S., and Saleh, M. (2007, January 24\u201327). One scan connected component labeling technique. Proceedings of the IEEE International Conference on Signal Processing and Communications (ICSPC 2007), Dubai, UAE.","DOI":"10.1109\/ICSPC.2007.4728561"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S1077-3142(02)00030-9","article-title":"Linear-time connected-component labeling based on sequential local operations","volume":"89","author":"Suzuki","year":"2003","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1145\/321356.321357","article-title":"Sequential operations in digital picture processing","volume":"13","author":"Rosenfeld","year":"1966","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Klaiber, M., Bailey, D.G., and Simon, S. (2019). Comparative study and proof of single-pass connected components algorithms. J. Math. Imaging Vis., submitted.","DOI":"10.1007\/s10851-019-00891-2"},{"key":"ref_7","unstructured":"Di Stefano, L., and Bulgarelli, A. (1999, January 27\u201329). A simple and efficient connected components labeling algorithm. Proceedings of the International Conference on Image Analysis and Processing, Venice, Italy."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s10044-008-0109-y","article-title":"Optimizing two-pass connected-component labeling algorithms","volume":"12","author":"Wu","year":"2009","journal-title":"Pattern Anal. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s11554-009-0134-0","article-title":"Light speed labeling: Efficient connected component labeling on RISC architectures","volume":"6","author":"Lacassagne","year":"2011","journal-title":"J. Real-Time Image Process."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1142\/S0218001410008032","article-title":"A run-based one-and-a-half-scan connected-component labeling algorithm","volume":"24","author":"He","year":"2010","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_11","unstructured":"He, L., Chao, Y., and Suzuki, K. (2012, January 4\u20136). A new two-scan algorithm for labeling connected components in binary images. Proceedings of the World Congress on Engineering, London, UK."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1109\/TIP.2013.2289968","article-title":"Configuration-transition-based connected-component labeling","volume":"23","author":"He","year":"2014","journal-title":"IEEE Trans. Image Process."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2013","DOI":"10.1587\/transinf.2015EDL8135","article-title":"A new connected-component labeling algorithm","volume":"98","author":"Zhao","year":"2015","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_14","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_15","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/978-3-319-48680-2_38","article-title":"Optimized connected components labeling with pixel prediction","volume":"Volume 10016","author":"Grana","year":"2016","journal-title":"Proceedings of the International Conference on Advanced Concepts for Intelligent Vision Systems (ACIVS 2016)"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Schwenk, K., and Huber, F. (2015, January 20\u201321). Connected component labeling algorithm for very complex and high-resolution images on an FPGA platform. Proceedings of the High Performance Computing in Remote Sensing V, Toulouse, France.","DOI":"10.1117\/12.2194101"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Appiah, K., Hunter, A., Dickenson, P., and Owens, J. (2008, January 8\u201310). A run-length based connected component algorithm for FPGA implementation. Proceedings of the International Conference on Field Programmable Technology, Taipei, Taiwan.","DOI":"10.1109\/FPT.2008.4762381"},{"key":"ref_18","unstructured":"Bailey, D., and Johnston, C. (2007, January 5\u20137). Single pass connected components analysis. Proceedings of the Image and Vision Computing New Zealand (IVCNZ), Hamilton, New Zealand."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Johnston, C.T., and Bailey, D.G. (2008, January 23\u201325). FPGA implementation of a single-pass connected components algorithm. Proceedings of the IEEE International Symposium on Electronic Design, Test and Applications (DELTA 2008), Hong Kong, China.","DOI":"10.1109\/DELTA.2008.21"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ma, N., Bailey, D., and Johnston, C. (2008, January 8\u201310). Optimised single-pass connected components analysis. Proceedings of the International Conference on Field Programmable Technology, Taipei, Taiwan.","DOI":"10.1109\/FPT.2008.4762382"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1334","DOI":"10.1109\/TCSVT.2015.2450371","article-title":"A resource-efficient hardware architecture for connected component analysis","volume":"26","author":"Klaiber","year":"2016","journal-title":"IEEE Trans. Circuits Syst. Video Technol."},{"key":"ref_22","unstructured":"Trein, J., Schwarzbacher, A.T., Hoppe, B., Noffz, K.H., and Trenschel, T. (2007, January 13\u201314). Development of a FPGA based real-time blob analysis circuit. Proceedings of the Irish Signals and Systems Conference, Derry, UK."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s11265-015-1048-7","article-title":"A single-pass connected component labeler without label merging period","volume":"84","author":"Jeong","year":"2016","journal-title":"J. Signal Process. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1687-5281-2013-21","article-title":"Real-time single-pass connected components analysis algorithm","volume":"2013","author":"Zhao","year":"2013","journal-title":"EURASIP J. Image Video Process."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s11554-016-0590-2","article-title":"A linked list run-length-based single-pass connected component analysis for real-time embedded hardware","volume":"15","author":"Tang","year":"2016","journal-title":"J. Real-Time Image Process."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wu, K., Otoo, E., and Shoshani, A. (2005, January 15\u201317). Optimizing connected component labelling algorithms. Proceedings of the Medical Imaging 2005: Image Processing, San Diego, CA, USA.","DOI":"10.1117\/12.596105"},{"key":"ref_27","unstructured":"ARM (2010). AMBA 4 AXI4-Stream Protocol Specification, ARM. Volume IHI 0051A."}],"container-title":["Journal of Imaging"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2313-433X\/5\/4\/45\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:43:23Z","timestamp":1760186603000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2313-433X\/5\/4\/45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,6]]},"references-count":27,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,4]]}},"alternative-id":["jimaging5040045"],"URL":"https:\/\/doi.org\/10.3390\/jimaging5040045","relation":{},"ISSN":["2313-433X"],"issn-type":[{"type":"electronic","value":"2313-433X"}],"subject":[],"published":{"date-parts":[[2019,4,6]]}}}