2021-06-182021-06-182020Díaz del Río, F., Sánchez Cuevas, P., Molina Abril, H. y Real Jurado, P. (2020). Parallel connected-Component-Labeling based on homotopy trees. Pattern Recognition Letters, 131 (march 2020), 71-78.0167-8655https://hdl.handle.net/11441/111886Taking advantage of the topological and isotopic properties of binary digital images, we present here anew algorithm for connected component labeling (CLL). A local-to-global treatment of the topologicalinformation within the image, allows us to develop an inherent parallel approach. The time complexityorder for an image of m ×n pixels, under the assumption that a processing element exists for each pixel, is near O (log(m + n )) . Additionally, our method computes both the foreground and background CCL, and allows a straightforward computation of topological features like Adjacency Trees. Experiments show thatour method obtains better performance metrics than other approaches. Our work aims at generating anew class of labeling algorithms: those centered in fully parallel approaches based on computationaltopology, thus allowing a perfect concurrent execution in multiple threads and preventing the use ofcritical sections and atomic instructions.application/pdf8engAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Connected-Component-LabelingComputational topologyAdjacency treeDigital imageParallelisminfo:eu-repo/semantics/articleinfo:eu-repo/semantics/openAccess10.1016/j.patrec.2019.11.039