Un algoritmo de componentes conectados novedoso para imágenes binarizadas en 2D
Autores: Boiangiu, Costin-Anton; Vlsceanu, Giorgiana-Violeta; Stniloiu, Constantin-Eduard; Tarb, Nicolae; Voncil, Mihai-Lucian
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Un algoritmo de componentes conectados novedoso para imágenes binarizadas en 2D
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Etiquetado de componentes conectadas
Codificación de longitud de ejecución
Eficiente en memoria
Imágenes binarias
Estrategia de unión por tamaño
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Este documento presenta un nuevo algoritmo eficiente en memoria para etiquetado de componentes conectados en imágenes binarias, basado en codificación de longitud de carrera. A diferencia de los métodos convencionales basados en píxeles que escanean y etiquetan píxeles individuales utilizando búferes globales o estructuras de conjuntos disjuntos, nuestro enfoque codifica filas como segmentos enlazados y los fusiona utilizando una estrategia de unión por tamaño. Aceleramos la detección de carreras utilizando una caché precalculada de 16 bits de patrones binarios, lo que permite una decodificación rápida sin depender de instrucciones de CPU a nivel de bits. En comparación con otros algoritmos codificados en longitud de carrera, como el Algoritmo de Etiquetado Basado en Escaneo o el Escaneo de Dos Etapas Basado en Carrera, nuestro método logra hasta un 35% más rápido en la mayoría de los conjuntos de datos del mundo real. Mientras que otros algoritmos optimizados para binarios, como el Escaneo de Dos Etapas de Bit-Carrera y el Escaneo de Carrera de Fusión de Bit, son hasta un 45% más rápidos que nuestro algoritmo, requieren un uso de memoria mucho mayor. En comparación con ellos, nuestro método tiende a reducir el consumo de memoria en algunos conjuntos de datos de documentos grandes hasta en un 80%.
Descripción
Este documento presenta un nuevo algoritmo eficiente en memoria para etiquetado de componentes conectados en imágenes binarias, basado en codificación de longitud de carrera. A diferencia de los métodos convencionales basados en píxeles que escanean y etiquetan píxeles individuales utilizando búferes globales o estructuras de conjuntos disjuntos, nuestro enfoque codifica filas como segmentos enlazados y los fusiona utilizando una estrategia de unión por tamaño. Aceleramos la detección de carreras utilizando una caché precalculada de 16 bits de patrones binarios, lo que permite una decodificación rápida sin depender de instrucciones de CPU a nivel de bits. En comparación con otros algoritmos codificados en longitud de carrera, como el Algoritmo de Etiquetado Basado en Escaneo o el Escaneo de Dos Etapas Basado en Carrera, nuestro método logra hasta un 35% más rápido en la mayoría de los conjuntos de datos del mundo real. Mientras que otros algoritmos optimizados para binarios, como el Escaneo de Dos Etapas de Bit-Carrera y el Escaneo de Carrera de Fusión de Bit, son hasta un 45% más rápidos que nuestro algoritmo, requieren un uso de memoria mucho mayor. En comparación con ellos, nuestro método tiende a reducir el consumo de memoria en algunos conjuntos de datos de documentos grandes hasta en un 80%.