Segmentación basada en árbol de expansión mínima

La segmentación de imágenes busca dividir una imagen digital en regiones de píxeles con propiedades similares, por ejemplo, homogeneidad. ^{[ 1 ]} La representación de regiones de nivel superior simplifica las tareas de análisis de imágenes, como contar objetos o detectar cambios, porque los atributos de la región (por ejemplo, intensidad promedio o forma ^{[ 2 ]} ) se pueden comparar más fácilmente que los píxeles sin procesar.

Para acelerar la segmentación de imágenes grandes, el trabajo podría dividirse entre varias CPU . Una forma de lograr esto consiste en dividir las imágenes en mosaicos que se procesan de forma independiente. Sin embargo, las regiones que abarcan el borde de un mosaico podrían dividirse o perderse si los fragmentos no cumplen con los requisitos de tamaño mínimo del algoritmo de segmentación. Una solución sencilla consiste en superponer mosaicos, es decir, permitir que cada procesador considere píxeles adicionales alrededor del borde de su mosaico. Desafortunadamente, esto aumenta la carga computacional, ya que los procesadores a ambos lados del límite de un mosaico realizan trabajo redundante. Además, solo se garantiza la preservación de objetos más pequeños que la superposición del mosaico, lo que significa que los objetos largos, como los ríos en imágenes aéreas, probablemente se dividirán. En algunos casos, los resultados de los mosaicos independientes pueden fusionarse para aproximar los resultados reales. ^{[ 3 ]} Existe una alternativa en forma de métodos de segmentación basados ​​en grafos. La información de conectividad inherente a los grafos permite realizar trabajo independiente en partes de la imagen original y volver a conectarlas para obtener un resultado exacto como si el procesamiento se hubiera realizado globalmente.

La posibilidad de unir subimágenes independientes motiva la adición de información de conectividad a los píxeles. Esto puede verse como un grafo, cuyos nodos son píxeles y cuyas aristas representan conexiones entre ellos. Una variante simple y relativamente eficiente en cuanto a espacio es un grafo de cuadrícula , donde cada píxel está conectado a sus vecinos en las cuatro direcciones cardinales . Dado que la relación de vecindad de píxeles es simétrica, el grafo resultante no está dirigido y solo es necesario almacenar la mitad de sus aristas (por ejemplo, el vecino este y sur de cada píxel). El paso final consiste en codificar la información de similitud de píxeles en pesos de aristas, de modo que la imagen original ya no sea necesaria. En el caso más simple, los pesos de las aristas se calculan como la diferencia de las intensidades de los píxeles.

Un árbol de expansión mínima (MST) es un subconjunto de peso mínimo y libre de ciclos de las aristas de un grafo, de modo que todos los nodos estén conectados. En 2004, Felzenszwalb introdujo un método de segmentación ^{[ 4 ]} basado en el algoritmo MST de Kruskal . Las aristas se consideran en orden creciente de peso; sus píxeles de extremo se fusionan en una región si esto no causa un ciclo en el grafo y si los píxeles son "similares" a los píxeles de las regiones existentes. La detección de ciclos es posible en tiempo casi constante con la ayuda de una estructura de datos de conjuntos disjuntos . ^{[ 5 ]} La similitud de píxeles se juzga mediante una heurística, que compara el peso con un umbral por segmento. El algoritmo produce múltiples MST disjuntos, es decir, un bosque; cada árbol corresponde a un segmento. La complejidad del algoritmo es cuasi lineal porque la ordenación de las aristas es posible en tiempo lineal mediante ordenación por conteo .

En 2009, Wassenberg et al. desarrollaron un algoritmo ^{[ 6 ]} que calcula múltiples bosques de expansión mínima independientes y luego los combina. Esto permite el procesamiento paralelo sin dividir los objetos en los bordes de los mosaicos. En lugar de un umbral de peso fijo, se utiliza un etiquetado inicial de componentes conectados para estimar un límite inferior del umbral, lo que puede reducir tanto la sobresegmentación como la subsegmentación. Las mediciones muestran que la implementación supera al algoritmo secuencial de Felzenszwalb por un orden de magnitud.

En 2017, Saglam y Baykan utilizaron la representación secuencial de Prim del árbol de expansión mínima y propusieron un nuevo criterio de corte para la segmentación de imágenes. ^{[ 7 ]} Construyeron el MST con el algoritmo MST de Prim utilizando la estructura de datos de montón de Fibonacci. El método logró un éxito significativo en las imágenes de prueba con un tiempo de ejecución rápido.

• Información sobre el algoritmo PHMSF (Heurística paralela para bosques de expansión mínima)