Presentation
Computing the Component-Labeling and the Adjacency Tree of a Binary Digital Image in Near Logarithmic-Time
Author/s | Díaz del Río, Fernando
![]() ![]() ![]() ![]() ![]() ![]() ![]() Molina Abril, Helena ![]() ![]() ![]() ![]() ![]() ![]() ![]() Real Jurado, Pedro ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Department | Universidad de Sevilla. Departamento de Arquitectura y Tecnología de Computadores Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Date | 2019 |
Published in |
|
ISBN/ISSN | 978-3-030-10827-4 0302-9743 |
Abstract | Connected component labeling (CCL) of binary images is
one of the fundamental operations in real time applications. The adjacency
tree (AdjT) of the connected components offers a region-based
representation where each ... Connected component labeling (CCL) of binary images is one of the fundamental operations in real time applications. The adjacency tree (AdjT) of the connected components offers a region-based representation where each node represents a region which is surrounded by another region of the opposite color. In this paper, a fully parallel algorithm for computing the CCL and AdjT of a binary digital image is described and implemented, without the need of using any geometric information. The time complexity order for an image of m × n pixels under the assumption that a processing element exists for each pixel is near O(log(m+ n)). Results for a multicore processor show a very good scalability until the so-called memory bandwidth bottleneck is reached. The inherent parallelism of our approach points to the direction that even better results will be obtained in other less classical computing architectures. |
Project ID. | MTM2016-81030-P
![]() TEC2012-37868-C04-02 ![]() |
Citation | Díaz del Río, F., Molina Abril, H. y Real Jurado, P. (2019). Computing the Component-Labeling and the Adjacency Tree of a Binary Digital Image in Near Logarithmic-Time. En CTIC 2019 : 7th International Workshop on Computational Topology in Image Contex (82-95), Málaga, España: Springer. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Computing the Component-Labeli ... | 1.356Mb | ![]() | View/ | |