El modelo de contorno activo , también llamado serpientes , es un marco en visión por computadora introducido por Michael Kass , Andrew Witkin y Demetri Terzopoulos [1] para delinear el contorno de un objeto a partir de una imagen 2D posiblemente ruidosa . El modelo de serpientes es popular en visión por computadora y las serpientes se usan ampliamente en aplicaciones como seguimiento de objetos, reconocimiento de formas, segmentación , detección de bordes y coincidencia estéreo.
Una serpiente es una spline deformable que minimiza la energía y que está influenciada por las fuerzas de restricción e imagen que la atraen hacia los contornos del objeto y las fuerzas internas que resisten la deformación. Las serpientes pueden entenderse como un caso especial de la técnica general de hacer coincidir un modelo deformable con una imagen mediante la minimización de la energía. [1] En dos dimensiones, el modelo de forma activa representa una versión discreta de este enfoque, aprovechando el modelo de distribución de puntos para restringir el rango de forma a un dominio explícito aprendido a partir de un conjunto de entrenamiento.
Las serpientes no resuelven por completo el problema de encontrar contornos en imágenes, ya que el método requiere conocer de antemano la forma deseada del contorno. En cambio, dependen de otros mecanismos, como la interacción con un usuario, la interacción con algún proceso de comprensión de imágenes de nivel superior o la información de datos de imágenes adyacentes en el tiempo o el espacio.
Motivación
En la visión artificial, los modelos de contorno describen los límites de las formas en una imagen. Las serpientes, en particular, están diseñadas para resolver problemas en los que se conoce la forma aproximada del límite. Al ser un modelo deformable, las serpientes pueden adaptarse a las diferencias y al ruido en la correspondencia estéreo y el seguimiento del movimiento. Además, el método puede encontrar contornos ilusorios en la imagen ignorando la información faltante sobre los límites.
En comparación con las técnicas clásicas de extracción de características, las serpientes tienen múltiples ventajas:
Buscan de forma autónoma y adaptativa el estado mínimo.
Las fuerzas de la imagen externa actúan sobre la serpiente de manera intuitiva.
La incorporación del suavizado gaussiano en la función de energía de la imagen introduce sensibilidad de escala.
Se pueden utilizar para rastrear objetos dinámicos.
Las principales desventajas de las serpientes tradicionales son:
Son sensibles a estados mínimos locales, que pueden contrarrestarse mediante técnicas de recocido simulado.
A menudo se ignoran las características minúsculas durante la minimización de energía en todo el contorno.
Su precisión depende de la política de convergencia. [2]
Formulación energética
Una serpiente elástica simple se define mediante un conjunto de n puntos para , el término de energía elástica interna y el término de energía externa basada en el borde . El propósito del término de energía interna es controlar las deformaciones realizadas en la serpiente, y el propósito del término de energía externa es controlar el ajuste del contorno sobre la imagen. La energía externa suele ser una combinación de las fuerzas debidas a la propia imagen y las fuerzas de restricción introducidas por el usuario.
La función energética de la serpiente es la suma de su energía externa y su energía interna, o
Energía interna
La energía interna de la serpiente se compone de la continuidad del contorno y la suavidad del contorno .
[3]
Esto se puede ampliar como
donde y son pesos definidos por el usuario; estos controlan la sensibilidad de la función de energía interna a la cantidad de estiramiento en la serpiente y la cantidad de curvatura en la serpiente, respectivamente, y por lo tanto controlan la cantidad de restricciones en la forma de la serpiente.
En la práctica, un peso elevado para el término de continuidad penaliza los cambios en las distancias entre los puntos del contorno. Un peso elevado para el término de suavidad penaliza las oscilaciones del contorno y hará que este actúe como una placa delgada.
Energía de la imagen
La energía de la imagen es una función de las características de la imagen. Este es uno de los puntos de modificación más comunes en los métodos derivados. Las características de las imágenes y las imágenes mismas se pueden procesar de muchas y diversas maneras.
Para una imagen , líneas, bordes y terminaciones presentes en la imagen, la formulación general de energía debida a la imagen es
donde , , son los pesos de estas características destacadas. Los pesos más altos indican que la característica destacada tendrá una mayor contribución a la fuerza de la imagen.
Línea funcional
La línea funcional es la intensidad de la imagen, que se puede representar como
El signo de determinará si la línea será atraída por líneas oscuras o líneas claras.
Se puede utilizar algún suavizado o reducción de ruido en la imagen, con lo que la línea funcional aparece como
Borde funcional
La función de borde se basa en el gradiente de la imagen. Una implementación de esto es
Una serpiente que se origina lejos del contorno del objeto deseado puede converger erróneamente a algún mínimo local. Se puede utilizar la continuación del espacio de escala para evitar estos mínimos locales. Esto se logra utilizando un filtro de desenfoque en la imagen y reduciendo la cantidad de desenfoque a medida que avanza el cálculo para refinar el ajuste de la serpiente. La función de energía que utiliza la continuación del espacio de escala es
donde es una función gaussiana con desviación estándar . Los mínimos de esta función caen en los cruces por cero de los cuales definen aristas según la teoría de Marr-Hildreth .
Terminación funcional
La curvatura de las líneas de nivel en una imagen ligeramente suavizada se puede utilizar para detectar esquinas y terminaciones en una imagen. Con este método, supongamos que la imagen se suaviza mediante
con ángulo de gradiente
vectores unitarios a lo largo de la dirección del gradiente
y vectores unitarios perpendiculares a la dirección del gradiente
La función de terminación de la energía se puede representar como
Energía de restricción
Algunos sistemas, incluida la implementación original de las serpientes, permitían la interacción del usuario para guiar a las serpientes, no solo en la ubicación inicial sino también en términos de energía. Dicha energía de restricción se puede utilizar para guiar interactivamente a las serpientes hacia o desde características particulares.
Optimización mediante descenso de gradiente
Dada una estimación inicial de una serpiente, la función de energía de la serpiente se minimiza iterativamente. La minimización por descenso de gradiente es una de las optimizaciones más simples que se pueden utilizar para minimizar la energía de la serpiente. [4] Cada iteración da un paso en el gradiente negativo del punto con un tamaño de paso controlado para encontrar mínimos locales. Esta minimización por descenso de gradiente se puede implementar como
¿Dónde está la fuerza sobre la serpiente, que se define por el negativo del gradiente del campo de energía?
Suponiendo que los pesos y son constantes con respecto a , este método iterativo se puede simplificar a
Aproximación discreta
En la práctica, las imágenes tienen una resolución finita y solo se pueden integrar en pasos de tiempo finitos . Por lo tanto, se deben realizar aproximaciones discretas para la implementación práctica de las serpientes.
La función energética de la serpiente se puede aproximar utilizando los puntos discretos de la serpiente.
En consecuencia, las fuerzas de la serpiente se pueden aproximar como
La aproximación de gradiente se puede realizar a través de cualquier método de aproximación finita con respecto a s , como por ejemplo la diferencia finita .
Inestabilidad numérica debido al tiempo discreto
La introducción de tiempo discreto en el algoritmo puede introducir actualizaciones que hagan que la serpiente se mueva más allá de los mínimos que la atraen; esto a su vez puede causar oscilaciones alrededor de los mínimos o hacer que se encuentre un mínimo diferente.
Esto se puede evitar ajustando el paso de tiempo de forma que el tamaño del paso nunca sea mayor que un píxel debido a las fuerzas de la imagen. Sin embargo, en regiones de baja energía, las energías internas dominarán la actualización.
Alternativamente, las fuerzas de la imagen se pueden normalizar para cada paso de modo que las fuerzas de la imagen solo actualicen la serpiente en un píxel. Esto se puede formular como
donde está cerca del valor del tamaño del píxel. Esto evita el problema de dominar las energías internas que surgen al ajustar el paso de tiempo. [5]
Inestabilidad numérica debido al espacio discreto
Las energías en una imagen continua pueden tener cruces por cero que no existen como píxeles en la imagen. En este caso, un punto en la serpiente oscilaría entre los dos píxeles vecinos de este cruce por cero. Esta oscilación se puede evitar utilizando la interpolación entre píxeles en lugar del vecino más cercano. [5]
Algunas variantes de serpientes
El método predeterminado de las serpientes tiene varias limitaciones y casos especiales en los que la convergencia funciona mal. Existen varias alternativas que abordan los problemas del método predeterminado, aunque con sus propias desventajas. A continuación se enumeran algunas de ellas.
Bajo rendimiento de convergencia para límites cóncavos.
Bajo rendimiento de convergencia cuando la serpiente se inicializa lejos del mínimo
En 2D, el campo vectorial GVF minimiza la función energética
donde es un término de suavizado controlable. Esto se puede resolver resolviendo las ecuaciones de Euler.
Esto se puede resolver mediante iteración hacia un valor de estado estable.
Este resultado reemplaza la fuerza externa predeterminada.
El problema principal con el uso de GVF es que el término de suavizado hace que los bordes del contorno se redondeen. Si se reduce el valor de , se reduce el redondeo, pero se debilita la cantidad de suavizado.
El modelo del globo
El modelo de globo [5] aborda estos problemas con el modelo de contorno activo predeterminado:
La serpiente no se siente atraída por los bordes distantes.
La serpiente se encogerá hacia adentro si no actúan sobre ella fuerzas sustanciales.
una serpiente más grande que el contorno mínimo eventualmente se encogerá en él, pero una serpiente más pequeña que el contorno mínimo no encontrará los mínimos y en cambio continuará encogiéndose.
El modelo del globo introduce un término de inflación en las fuerzas que actúan sobre la serpiente.
donde es el vector unitario normal de la curva en y es la magnitud de la fuerza. debe tener la misma magnitud que el factor de normalización de la imagen y ser menor en valor que para permitir que las fuerzas en los bordes de la imagen superen la fuerza de inflación.
El uso del modelo de globo plantea tres problemas:
En lugar de encogerse, la serpiente se expande hacia los mínimos y no encontrará contornos mínimos más pequeños que ella.
La fuerza hacia afuera hace que el contorno sea ligeramente más grande que los mínimos reales. Esto se puede solucionar disminuyendo la fuerza del globo después de que se haya encontrado una solución estable.
La fuerza de inflación puede superar las fuerzas de los bordes débiles, lo que amplifica el problema cuando las serpientes ignoran las características más débiles de una imagen.
Modelo de serpientes de difusión
El modelo de serpiente de difusión [7] aborda la sensibilidad de las serpientes al ruido, el desorden y la oclusión. Implementa una modificación de la función de Mumford-Shah y su límite de dibujos animados e incorpora conocimiento estadístico de la forma. La función de energía de imagen predeterminada se reemplaza por
donde se basa en una función Mumford-Shah modificada
donde es el modelo suavizado por partes de la imagen del dominio . Los límites se definen como
donde son funciones base B-spline cuadráticas y son los puntos de control de las splines. El límite de dibujos animados modificado se obtiene como y es una configuración válida de .
La función se basa en el entrenamiento a partir de imágenes binarias de varios contornos y se controla en fuerza mediante el parámetro . Para una distribución gaussiana de vectores de puntos de control con vector de punto de control medio y matriz de covarianza , la energía cuadrática que corresponde a la probabilidad gaussiana es
La solidez de este método depende de la solidez de los datos de entrenamiento, así como del ajuste de la función Mumford-Shah modificada. Diferentes serpientes requerirán diferentes conjuntos de datos de entrenamiento y ajustes.
Contornos activos geométricos
El contorno activo geométrico, o contorno activo geodésico (GAC) [8] o contornos activos conformes [9] emplea ideas de la evolución del acortamiento de la curva euclidiana . Los contornos se dividen y fusionan dependiendo de la detección de objetos en la imagen. Estos modelos están inspirados en gran medida en los conjuntos de niveles y se han empleado ampliamente en la computación de imágenes médicas .
Por ejemplo, la ecuación de evolución de la curva de descenso de gradiente del GAC es [8]
donde es una función de parada, c es un multiplicador de Lagrange, es la curvatura y es la normal interna unitaria. Esta forma particular de ecuación de evolución de la curva solo depende de la velocidad en la dirección normal. Por lo tanto, se puede reescribir de manera equivalente en una forma euleriana insertando la función de conjunto de niveles en ella de la siguiente manera
Esta reforma de conjunto de niveles, simple pero poderosa, permite que los contornos activos manejen cambios de topología durante la evolución de la curva de descenso de gradiente. Ha inspirado un tremendo progreso en los campos relacionados, y el uso de métodos numéricos para resolver la reformulación de conjunto de niveles ahora se conoce comúnmente como el método de conjunto de niveles . Aunque el método de conjunto de niveles se ha convertido en una herramienta bastante popular para implementar contornos activos, Wang y Chan argumentaron que no todas las ecuaciones de evolución de curvas deberían resolverse directamente con él. [10]
Los desarrollos más recientes en contornos activos abordan el modelado de propiedades regionales, la incorporación de formas anteriores flexibles y la segmentación completamente automática, etc.
Lankton y Allen Tannenbaum han formulado modelos estadísticos que combinan características locales y globales . [11]
Relaciones con cortes de gráficos
Los cortes de gráfico , o flujo máximo/corte mínimo , son un método genérico para minimizar una forma particular de energía llamada energía de campo aleatorio de Markov (MRF). El método de cortes de gráfico también se ha aplicado a la segmentación de imágenes y, en ocasiones, supera al método de conjunto de niveles cuando el modelo es MRF o se puede aproximar mediante MRF.
^ ab Kass, M.; Witkin, A .; Terzopoulos, D. (1988). "Serpientes: modelos de contorno activos" (PDF) . Revista internacional de visión por computadora . 1 (4): 321. CiteSeerX 10.1.1.124.5318 . doi :10.1007/BF00133570. S2CID 12849354. Archivado desde el original (PDF) el 2016-01-12 . Consultado el 2015-08-29 .
^ Serpientes: un modelo activo, Ramani Pichumani, http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RAMANI1/node31.html
^ Dr. George Bebis, Universidad de Nevada, http://www.cse.unr.edu/~bebis/CS791E/Notes/DeformableContours.pdf
^ Comprensión de imágenes , Bryan S. Morse, Universidad Brigham Young, 1998-2000 http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MORSE/iu.pdf
^ abc Cohen, Laurent D. (1991). "Sobre modelos de contorno activos y globos". CVGIP: Comprensión de imágenes . 53 (2): 211–218. doi :10.1016/1049-9660(91)90028-N.
^ Chenyang Xu; Prince, JL (1997). "Flujo de gradiente vectorial: una nueva fuerza externa para las serpientes". Actas de la Conferencia de la IEEE Computer Society sobre visión artificial y reconocimiento de patrones (PDF) . pp. 66–71. doi :10.1109/CVPR.1997.609299. ISBN0-8186-7822-4.S2CID 980797 .
^ Cremers, D.; Schnorr, C.; Weickert, J. (2001). "Serpientes de difusión: combinación de conocimiento estadístico de la forma e información de la imagen en un marco variacional". Actas del taller IEEE sobre métodos variacionales y de conjuntos de niveles en visión artificial . Vol. 50. págs. 137–144. CiteSeerX 10.1.1.28.3639 . doi :10.1109/VLSM.2001.938892. ISBN.978-0-7695-1278-5. Número de identificación del sujeto 14929019.
^ ab Contornos activos geodésicos, V. Caselles, R. Kimmel, G. Sapiro http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.2196
^ Kichenassamy, Satyanad; Kumar, Arun; Olver, Peter; Tannenbaum, Allen; Yezzi, Anthony (1996). "Flujos de curvatura conforme: de las transiciones de fase a la visión activa". Archivo de Mecánica racional y análisis . 134 (3): 275–301. Código Bibliográfico :1996ArRMA.134..275K. doi :10.1007/BF00379537. S2CID 116487549.
^ Wang, Junyan; Chan, Kap Luk (8 de julio de 2014). "Contorno activo con un componente tangencial". Revista de imágenes y visión matemática . 51 (2): 229–247. arXiv : 1204.6458 . doi :10.1007/s10851-014-0519-y. ISSN 0924-9907. S2CID 13100077.
^ Lankton, S.; Tannenbaum, A. (2008). "Localización de contornos activos basados en regiones". IEEE Transactions on Image Processing . 17 (11): 2029–2039. Bibcode :2008ITIP...17.2029L. doi :10.1109/TIP.2008.2004611. PMC 2796112 . PMID 18854247.
Enlaces externos
David Young, marzo de 1995
Serpientes: contornos activos, CVOnline
Contornos activos, modelos deformables y flujo de vectores de gradiente de Chenyang Xu y Jerry Prince, incluye descarga de código
ICBE, Universidad de Manchester
Implementación de contornos activos y plataforma de prueba GUI
Una implementación sencilla de serpientes por el Profesor Asociado Cris Luengo
Documentación de MATLAB para activecontour, que segmenta una imagen utilizando contornos activos
Código de muestra
Ejemplos prácticos de diferentes serpientes desarrolladas por Xu y Prince
Herramienta básica para jugar con serpientes (modelos de contorno activos) de Tim Cootes, Universidad de Manchester
Implementación de Matlab de serpiente 2D y 3D que incluye GVF y fuerza de globo
Demostración de Matlab Snake por Chris Bregler y Malcolm Slaney , Interval Research Corporation.
Una demostración usando Java
Implementación y plataforma de prueba de contornos activos GUI de Nikolay S. y Alex Blekhman implementando "Contornos activos sin bordes"
Segmentación de contornos activos por Shawn Lankton, que implementa "Contornos activos sin bordes"
Código de contorno activo geométrico de Jarno Ralli