El desplazamiento medio es una técnica de análisis de espacio de características no paramétrico para localizar los máximos de una función de densidad , un llamado algoritmo de búsqueda de modo . [1] Los dominios de aplicación incluyen el análisis de grupos en la visión por computadora y el procesamiento de imágenes . [2]
Historia
El procedimiento de cambio medio fue presentado originalmente en 1975 por Fukunaga y Hostetler. [3]
Descripción general
El desplazamiento medio es un procedimiento para localizar los máximos —los modos— de una función de densidad dados datos discretos muestreados de esa función. [1] Este es un método iterativo y comenzamos con una estimación inicial.. Deje que un kernel funcione ser dado. Esta función determina el peso de los puntos cercanos para reestimar la media. Normalmente se utiliza un kernel gaussiano en la distancia a la estimación actual,. La media ponderada de la densidad en la ventana determinada por es
dónde es el barrio de , un conjunto de puntos para los que .
La diferencia se llama cambio medio en Fukunaga y Hostetler. [3] El algoritmo de desplazamiento medio ahora establecey repite la estimación hasta converge.
Aunque el algoritmo de desplazamiento medio se ha utilizado ampliamente en muchas aplicaciones, todavía no se conoce una prueba rígida de la convergencia del algoritmo que utiliza un núcleo general en un espacio de alta dimensión. [4] Aliyari Ghassabeh mostró la convergencia del algoritmo de desplazamiento medio en una dimensión con una función de perfil diferenciable, convexa y estrictamente decreciente. [5] Sin embargo, el caso unidimensional tiene aplicaciones limitadas en el mundo real. Además, se ha demostrado la convergencia del algoritmo en dimensiones superiores con un número finito de puntos estacionarios (o aislados). [4] [6] Sin embargo, no se han proporcionado las condiciones suficientes para que una función del núcleo general tenga puntos estacionarios finitos (o aislados).
El desplazamiento medio gaussiano es un algoritmo de maximización de expectativas . [7]
Detalles
Deje que los datos sean un conjunto finito incrustado en el -espacio euclidiano dimensional, . Dejar ser un núcleo plano que es la función característica de la bola en ,
En cada iteración del algoritmo, se realiza para todos simultaneamente. La primera pregunta, entonces, es cómo estimar la función de densidad dado un conjunto escaso de muestras. Uno de los enfoques más simples es simplemente suavizar los datos, por ejemplo, convolviéndolos con un kernel fijo de ancho,
dónde son las muestras de entrada y es la función del kernel (o ventana Parzen ).es el único parámetro del algoritmo y se llama ancho de banda. Este enfoque se conoce como estimación de densidad de kernel o técnica de ventana de Parzen. Una vez que hemos calculadoa partir de la ecuación anterior, podemos encontrar sus máximos locales usando el ascenso en gradiente o alguna otra técnica de optimización. El problema con este enfoque de "fuerza bruta" es que, para dimensiones superiores, resulta prohibitivo computacionalmente evaluarsobre el espacio de búsqueda completo. En cambio, el cambio medio utiliza una variante de lo que se conoce en la literatura de optimización como descenso de gradiente de reinicio múltiple . Partiendo de alguna suposición para un máximo local,, que puede ser un punto de datos de entrada aleatorio , el desplazamiento medio calcula el gradiente de la densidad estimada a y da un paso cuesta arriba en esa dirección. [8]
Tipos de granos
Definición de kernel: Let ser el -espacio euclidiano dimensional, . La norma de es un número no negativo, . Una funciónse dice que es un kernel si existe un perfil , , tal que
y
- k no es negativo.
- k no aumenta: Si .
- k es continuo por partes y
Los dos perfiles de kernel más utilizados para el desplazamiento medio son:
- Grano plano
- Kernel gaussiano
donde el parámetro de desviación estándar funciona como parámetro de ancho de banda, .
Aplicaciones
Agrupación
Considere un conjunto de puntos en un espacio bidimensional. Suponga una ventana circular centrada en C y que tiene un radio r como núcleo. El cambio medio es un algoritmo de escalada que implica cambiar este núcleo de forma iterativa a una región de mayor densidad hasta la convergencia. Cada cambio está definido por un vector de cambio medio. El vector de desplazamiento medio siempre apunta hacia la dirección del aumento máximo en la densidad. En cada iteración, el núcleo se desplaza al centroide o la media de los puntos dentro de él. El método para calcular esta media depende de la elección del kernel. En este caso, si se elige un kernel gaussiano en lugar de un kernel plano, a cada punto se le asignará primero un peso que decaerá exponencialmente a medida que aumente la distancia desde el centro del kernel. En la convergencia, no habrá dirección en la que un cambio pueda acomodar más puntos dentro del núcleo.
Seguimiento
El algoritmo de cambio medio se puede utilizar para el seguimiento visual. El algoritmo más simple de este tipo crearía un mapa de confianza en la nueva imagen basado en el histograma de color del objeto en la imagen anterior y usaría el desplazamiento medio para encontrar el pico de un mapa de confianza cerca de la posición anterior del objeto. El mapa de confianza es una función de densidad de probabilidad en la nueva imagen, que asigna a cada píxel de la nueva imagen una probabilidad, que es la probabilidad de que el color del píxel ocurra en el objeto de la imagen anterior. Algunos algoritmos, como el seguimiento de objetos basado en el núcleo, [9] seguimiento de conjuntos, [10] CAMshift [11] [12] amplían esta idea.
Suavizado
Dejar y ser el -Píxeles de imagen filtrada y de entrada dimensional en el dominio de rango espacial conjunto. Para cada píxel,
- Inicializar y
- Calcular de acuerdo a hasta la convergencia, .
- Asignar . Los superíndices syr denotan los componentes espacial y de rango de un vector, respectivamente. La asignación especifica que los datos filtrados en el eje de ubicación espacial tendrán el componente de rango del punto de convergencia.
Fortalezas
- Mean shift es una herramienta independiente de la aplicación adecuada para el análisis de datos reales.
- No asume ninguna forma predefinida en grupos de datos.
- Es capaz de manejar espacios de características arbitrarios.
- El procedimiento se basa en la elección de un único parámetro: ancho de banda.
- El ancho de banda / tamaño de ventana 'h' tiene un significado físico, a diferencia de k -medios .
Debilidades
- La selección de un tamaño de ventana no es trivial.
- Un tamaño de ventana inadecuado puede hacer que los modos se fusionen o generar modos "superficiales" adicionales.
- A menudo requiere el uso de un tamaño de ventana adaptable.
Disponibilidad
Las variantes del algoritmo se pueden encontrar en los paquetes de procesamiento de imágenes y aprendizaje automático:
- ELKI . Herramienta de minería de datos Java con muchos algoritmos de agrupación.
- ImageJ . Filtrado de imágenes mediante el filtro de desplazamiento medio.
- mlpack . Implementación eficiente basada en algoritmos de doble árbol.
- OpenCV contiene implementación de cambio medio a través del método cvMeanShift
- Caja de herramientas Orfeo . Una implementación de C ++.
- La implementación de Scikit -learn Numpy / Python utiliza el árbol de bolas para una búsqueda eficiente de puntos vecinos
Ver también
Referencias
- ↑ a b Cheng, Yizong (agosto de 1995). "Cambio medio, búsqueda de modo y agrupación". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 17 (8): 790–799. CiteSeerX 10.1.1.510.1222 . doi : 10.1109 / 34.400568 .
- ^ Comaniciu, Dorin; Peter Meer (mayo de 2002). "Cambio medio: un enfoque sólido hacia el análisis del espacio de características". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 24 (5): 603–619. CiteSeerX 10.1.1.160.3832 . doi : 10.1109 / 34.1000236 .
- ^ a b Fukunaga, Keinosuke; Larry D. Hostetler (enero de 1975). "La estimación del gradiente de una función de densidad, con aplicaciones en el reconocimiento de patrones". Transacciones IEEE sobre teoría de la información . 21 (1): 32–40. doi : 10.1109 / TIT.1975.1055330 .
- ^ a b Aliyari Ghassabeh, Youness (1 de marzo de 2015). "Una condición suficiente para la convergencia del algoritmo de desplazamiento medio con el kernel de Gauss" . Revista de análisis multivariante . 135 : 1-10. doi : 10.1016 / j.jmva.2014.11.009 .
- ^ Aliyari Ghassabeh, Youness (1 de septiembre de 2013). "Sobre la convergencia del algoritmo de desplazamiento medio en el espacio unidimensional". Cartas de reconocimiento de patrones . 34 (12): 1423-1427. arXiv : 1407.2961 . doi : 10.1016 / j.patrec.2013.05.004 . S2CID 10233475 .
- ^ Li, Xiangru; Hu, Zhanyi; Wu, Fuchao (1 de junio de 2007). "Una nota sobre la convergencia del desplazamiento medio". Reconocimiento de patrones . 40 (6): 1756-1762. doi : 10.1016 / j.patcog.2006.10.016 .
- ^ Carreira-Perpinan, Miguel A. (mayo de 2007). "El cambio medio gaussiano es un algoritmo EM". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 29 (5): 767–776. doi : 10.1109 / tpami.2007.1057 . ISSN 0162-8828 . PMID 17356198 . S2CID 6694308 .
- ^ Richard Szeliski, Visión por computadora, algoritmos y aplicaciones, Springer, 2011
- ^ Comaniciu, Dorin; Visvanathan Ramesh; Peter Meer (mayo de 2003). "Seguimiento de objetos basado en kernel". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 25 (5): 564–575. CiteSeerX 10.1.1.8.7474 . doi : 10.1109 / tpami.2003.1195991 .
- ^ Avidan, Shai (2005). Seguimiento de conjuntos . 2005 IEEE Computer Society Conference sobre visión por ordenador y reconocimiento de patrones (CVPR'05) . 2 . San Diego, California: IEEE. págs. 494–501. doi : 10.1109 / CVPR.2005.144 . ISBN 978-0-7695-2372-9. PMID 17170479 . S2CID 1638397 .
- ^ Gary Bradski (1998) Seguimiento facial de visión por computadora para su uso en una interfaz de usuario perceptual Archivado el 17 de abril de 2012 en Wayback Machine , Intel Technology Journal, No. Q2.
- ^ Emami, Ebrahim (2013). "Detección y corrección de fallas en línea para el algoritmo de seguimiento CAMShift". 2013 Octava Conferencia Iraní sobre Visión Artificial y Procesamiento de Imágenes (MVIP) . 2013 Conferencia iraní sobre visión artificial y procesamiento de imágenes (MVIP) . 2 . IEEE. págs. 180–183. doi : 10.1109 / IranianMVIP.2013.6779974 . ISBN 978-1-4673-6184-2. S2CID 15864761 .