El problema de la segmentación de imágenes tiene que ver con dividir una imagen en múltiples regiones de acuerdo con algún criterio de homogeneidad. Este artículo se ocupa principalmente de los enfoques teóricos de gráficos para la segmentación de imágenes aplicando la partición de gráficos mediante corte mínimo o corte máximo . La categorización de objetos basada en segmentación puede verse como un caso específico de agrupamiento espectral aplicado a la segmentación de imágenes.
Aplicaciones de la segmentación de imágenes
- Compresión de imagen
- Segmente la imagen en componentes homogéneos y utilice el algoritmo de compresión más adecuado para cada componente para mejorar la compresión.
- Diagnostico medico
- Segmentación automática de imágenes de resonancia magnética para la identificación de regiones cancerosas.
- Mapeo y medición
- Análisis automático de datos de teledetección de satélites para identificar y medir regiones de interés.
- Transporte
- La partición de una red de transporte permite identificar regiones caracterizadas por estados de tráfico homogéneos. [1]
Segmentación mediante cortes normalizados
Formulación de la teoría de grafos
El conjunto de puntos en un espacio de características arbitrario se puede representar como un gráfico completo no dirigido ponderado G = (V, E), donde los nodos del gráfico son los puntos en el espacio de características. El peso de un borde es una función de la similitud entre los nodos y . En este contexto, podemos formular el problema de segmentación de imágenes como un problema de partición de gráficos que solicita una partición. del conjunto de vértices , donde, según alguna medida, los vértices de cualquier conjunto tienen alta similitud, y los vértices en dos conjuntos diferentes tienen poca similitud.
Cortes normalizados
Sea G = ( V , E , w ) una gráfica ponderada. Dejar y ser dos subconjuntos de vértices.
Dejar:
En el enfoque de cortes normalizados, [2] para cualquier corte en , mide la similitud entre diferentes partes, y mide la similitud total de vértices en la misma parte.
Desde , un corte que minimiza también maximiza .
Calcular un corte que minimiza es un problema NP-difícil . Sin embargo, podemos encontrar en tiempo polinomial un corte de pequeño peso normalizado utilizando técnicas espectrales .
El algoritmo ncut
Dejar:
Además, sea D un matriz diagonal con en la diagonal, y deja frijol matriz simétrica con .
Después de algunas manipulaciones algebraicas, obtenemos:
sujeto a las limitaciones:
- , por alguna constante
Minimizar sujeto a las restricciones anteriores es NP-hard . Para hacer que el problema sea manejable, relajamos las restricciones sobrey permitirle tomar valores reales. El problema relajado se puede resolver resolviendo el problema de valores propios generalizados para el segundo valor propio generalizado más pequeño.
El algoritmo de partición:
- Dado un conjunto de características, configure un gráfico ponderado , calcular el peso de cada borde y resumir la información en y .
- Resolver para vectores propios con los segundos valores propios más pequeños.
- Utilice el vector propio con el segundo valor propio más pequeño para dividir el gráfico en dos partes (por ejemplo, agrupando según el signo).
- Decide si la partición actual debe subdividirse.
- Divida recursivamente las partes segmentadas, si es necesario.
Complejidad computacional
Resolver un problema de valores propios estándar para todos los vectores propios (utilizando el algoritmo QR , por ejemplo) requierehora. Esto no es práctico para aplicaciones de segmentación de imágenes donde es el número de píxeles de la imagen.
Dado que el algoritmo sin cortar solo utiliza un vector propio, correspondiente al segundo valor propio generalizado más pequeño, la eficiencia puede mejorarse drásticamente si la resolución del problema de valor propio correspondiente se realiza sin matrices , es decir, sin manipular explícitamente con o incluso calcular la matriz W, como, por ejemplo, en el algoritmo de Lanczos . Los métodos sin matrices solo requieren una función que realice un producto matriz-vector para un vector dado, en cada iteración. Para la segmentación de imágenes, la matriz W suele ser escasa, con varias entradas distintas de cero., por lo que dicho producto matriz-vector toma hora.
Para imágenes de alta resolución, el segundo valor propio a menudo está mal condicionado , lo que lleva a una convergencia lenta de los solucionadores de valores propios iterativos, como el algoritmo de Lanczos . El preacondicionamiento es una tecnología clave que acelera la convergencia, por ejemplo, en el método LOBPCG sin matriz . Calcular el vector propio utilizando un método sin matriz preacondicionado de manera óptima requiere tiempo, que es la complejidad óptima, ya que el vector propio tiene componentes.
CORTE OBJ
OBJ CUT [3] es un método eficaz que segmenta automáticamente un objeto. El método OBJ CUT es un método genérico y, por lo tanto, es aplicable a cualquier modelo de categoría de objeto. Dada una imagen D que contiene una instancia de una categoría de objeto conocida, por ejemplo, vacas, el algoritmo OBJ CUT calcula una segmentación del objeto, es decir, infiere un conjunto de etiquetas m .
Sea m un conjunto de etiquetas binarias y sea ser un parámetro de forma (es una forma anterior en las etiquetas de un modelo de estructura pictórica en capas (LPS)). Una función energética se define de la siguiente manera.
- (1)
El termino se llama un término unario, y el término se llama un término por pares. Un término unario consiste en la probabilidad basado en el color, y el potencial unario basado en la distancia desde . Un término por pares consta de una y un término de contraste .
El mejor etiquetado minimiza , dónde es el peso del parámetro .
- (2)
Algoritmo
- Dada una imagen D, se elige una categoría de objeto, por ejemplo, vacas o caballos.
- El modelo LPS correspondiente se compara con D para obtener las muestras
- La función objetivo dada por la ecuación (2) se determina calculando y usando
- La función objetivo se minimiza utilizando una única operación MINCUT para obtener la segmentación m .
Otros enfoques
Referencias
- ^ López, Clélia; Leclercq, Ludovic; Krishnakumari, Panchamy; Chiabaut, Nicolas; Van Lint, Hans (25 de octubre de 2017). "Revelando la regularidad del día a día de los patrones de congestión urbana con mapas de velocidad en 3D" . Informes científicos . 7 (14029): 14029. doi : 10.1038 / s41598-017-14237-8 . PMC 5656590 . PMID 29070859 .
- ^ Jianbo Shi y Jitendra Malik (1997): "Cortes normalizados y segmentación de imágenes", Conferencia IEEE sobre visión por computadora y reconocimiento de patrones, págs. 731–737
- ^ MP Kumar, PHS Torr y A. Zisserman. Obj cut. En Proceedings of IEEE Conference on Computer Vision and Pattern Recognition , San Diego, páginas 18-25, 2005.
- ^ E. Borenstein, S. Ullman: Segmentación de arriba hacia abajo específica de la clase . En Actas de la 7ª Conferencia Europea de Visión por Computador, Copenhague, Dinamarca, páginas 109-124, 2002.
- ^ Z. Tu, X. Chen, AL Yuille, SC Zhu: Análisis de imágenes: unificación de segmentación, detección y reconocimiento . Hacia el reconocimiento de objetos a nivel de categoría 2006: 545–576
- ^ B. Leibe, A. Leonardis, B. Schiele: un modelo de forma implícita para la categorización y segmentación de objetos combinados . Hacia el reconocimiento de objetos a nivel de categoría 2006: 508–524
- ^ J. Winn, N. Joijic. Locus: clases de objetos de aprendizaje con segmentación no supervisada . En Actas de la Conferencia Internacional IEEE sobre Visión por Computador, Beijing, 2005.
- ^ JM Winn, J. Shotton: El campo aleatorio consistente de diseño para reconocer y segmentar objetos parcialmente ocluidos . CVPR (1) 2006: 37–44