cambio medio

tecnica matematica

El desplazamiento medio es una técnica de análisis matemático del espacio de características no paramétrica para localizar los máximos de una función de densidad , el llamado algoritmo de búsqueda de modo . ^[1] Los dominios de aplicación incluyen el análisis de conglomerados en visión por computadora y procesamiento de imágenes . ^[2]

Historia

El procedimiento de cambio medio generalmente se atribuye al trabajo de Fukunaga y Hostetler en 1975. ^[3] Sin embargo, recuerda un trabajo anterior de Schnell en 1964. ^[4]

Descripción general

El desplazamiento medio es un procedimiento para localizar los máximos (las modas ) 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 . Sea una función del núcleo . Esta función determina el peso de los puntos cercanos para volver a estimar la media. Normalmente se utiliza un núcleo gaussiano para la distancia a la estimación actual . La media ponderada de la densidad en la ventana determinada por es ${\displaystyle x}$ ${\displaystyle K(x_{i}-x)}$ ${\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}$ ${\displaystyle K}$

${\displaystyle m(x)={\frac {\sum _{x_{i}\in N(x)}K(x_{i}-x)x_{i}}{\sum _{x_{i}\in N(x)}K(x_{i}-x)}}}$

¿Dónde está la vecindad de un conjunto de puntos para los cuales ? ${\displaystyle N(x)}$ ${\displaystyle x}$ ${\displaystyle K(x_{i}-x)\neq 0}$

La diferencia se llama desplazamiento medio en Fukunaga y Hostetler. ^[3] El algoritmo de desplazamiento medio ahora establece y repite la estimación hasta que converge. ${\displaystyle m(x)-x}$ ${\displaystyle x\leftarrow m(x)}$ ${\displaystyle m(x)}$

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 utilizando un núcleo general en un espacio de alta dimensión. ^[5] 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. ^[6] 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). ^{[5] [7]} Sin embargo, no se han proporcionado condiciones suficientes para que una función nuclear general tenga puntos finitos estacionarios (o aislados).

Gaussian Mean-Shift es un algoritmo de maximización de expectativas . ^[8]

Detalles

Sea los datos un conjunto finito incrustado en el espacio euclidiano de dimensiones ,. Sea un núcleo plano que es la función característica de la bola en , ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle K}$ ${\displaystyle \lambda }$ ${\displaystyle X}$

${\displaystyle K(x)={\begin{cases}1&{\text{if}}\ \|x\|\leq \lambda \\0&{\text{if}}\ \|x\|>\lambda \\\end{cases}}}$

En cada iteración del algoritmo, se realiza para todos simultáneamente. La primera pregunta, entonces, es cómo estimar la función de densidad dado un conjunto disperso de muestras. Uno de los enfoques más simples es simplemente suavizar los datos, por ejemplo, convolucionándolos con un núcleo fijo de ancho , ${\displaystyle s\leftarrow m(s)}$ ${\displaystyle s\in S}$ ${\displaystyle h}$

${\displaystyle f(x)=\sum _{i}K(x-x_{i})=\sum _{i}k\left({\frac {\|x-x_{i}\|^{2}}{h^{2}}}\right)}$

¿Dónde están las muestras de entrada y es la función del núcleo (o ventana de Parzen )? es el único parámetro en el algoritmo y se llama ancho de banda. Este enfoque se conoce como estimación de la densidad del núcleo o técnica de la ventana de Parzen. Una vez que hayamos calculado a partir de la ecuación anterior, podemos encontrar sus máximos locales utilizando el ascenso de gradiente o alguna otra técnica de optimización. El problema con este enfoque de "fuerza bruta" es que, para dimensiones superiores, resulta computacionalmente prohibitivo evaluar todo el espacio de búsqueda. 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 . A partir de una estimación de un máximo local, que puede ser un punto de datos de entrada aleatorio , el desplazamiento medio calcula el gradiente de la estimación de densidad en y da un paso cuesta arriba en esa dirección. ^[9] ${\displaystyle x_{i}}$ ${\displaystyle k(r)}$ ${\displaystyle h}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)}$ ${\displaystyle y_{k}}$ ${\displaystyle x_{1}}$ ${\displaystyle f(x)}$ ${\displaystyle y_{k}}$

tipos de granos

Definición del núcleo: Sea el espacio euclidiano de dimensiones ,. La norma de es un número no negativo, . Se dice que una función es un núcleo si existe un perfil tal que ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle x}$ ${\displaystyle \|x\|^{2}=x^{\top }x\geq 0}$ ${\displaystyle K:X\rightarrow \mathbb {R} }$ ${\displaystyle k:[0,\infty ]\rightarrow \mathbb {R} }$

${\displaystyle K(x)=k(\|x\|^{2})}$y

• k no es negativo.
• k no es creciente: si . ${\displaystyle k(a)\geq k(b)}$ ${\displaystyle a<b}$
• k es continuo por tramos y ${\displaystyle \int _{0}^{\infty }k(r)\,dr<\infty \ }$

Los dos perfiles de kernel más utilizados para el cambio medio son:

Núcleo plano

${\displaystyle k(x)={\begin{cases}1&{\text{if}}\ x\leq \lambda \\0&{\text{if}}\ x>\lambda \\\end{cases}}}$

núcleo gaussiano

${\displaystyle k(x)=e^{-{\frac {x}{2\sigma ^{2}}}},}$

donde el parámetro de desviación estándar funciona como parámetro de ancho de banda, . ${\displaystyle \sigma }$ ${\displaystyle h}$

Aplicaciones

Agrupación

Considere un conjunto de puntos en un espacio bidimensional. Supongamos una ventana circular centrada y con radio 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 máximo aumento de la densidad. En cada iteración, el núcleo se desplaza al centroide o a la media de los puntos que contiene. El método para calcular esta media depende de la elección del núcleo. En este caso, si se elige un núcleo gaussiano en lugar de un núcleo plano, a cada punto se le asignará primero un peso que decaerá exponencialmente a medida que aumente la distancia desde el centro del núcleo. En la convergencia, no habrá dirección en la que un desplazamiento pueda acomodar más puntos dentro del núcleo. ${\displaystyle C}$ ${\displaystyle r}$

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 antigua posición 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 aparezca en el objeto de la imagen anterior. Algunos algoritmos, como el seguimiento de objetos basado en kernel, ^[10] el seguimiento de conjuntos, ^[11] CAMshift ^{[12] [13]} amplían esta idea.

Suavizado

Sea y la entrada de dimensiones y los píxeles de la imagen filtrada en el dominio de rango espacial conjunto. Para cada píxel, ${\displaystyle x_{i}}$ ${\displaystyle z_{i},i=1,...,n,}$ ${\displaystyle d}$

• Inicializar y ${\displaystyle j=1}$ ${\displaystyle y_{i,1}=x_{i}}$
• Calcular según hasta la convergencia, . ${\displaystyle y_{i,j+1}}$ ${\displaystyle m(\cdot )}$ ${\displaystyle y=y_{i,c}}$
• Asignar . Los superíndices s y r 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 . ${\displaystyle z_{i}=(x_{i}^{s},y_{i,c}^{r})}$ ${\displaystyle y_{i,c}^{r}}$

Fortalezas

1. Mean Shift es una herramienta independiente de la aplicación adecuada para el análisis de datos reales.
2. No asume ninguna forma predefinida en los grupos de datos.
3. Es capaz de manejar espacios de características arbitrarios.
4. El procedimiento se basa en la elección de un único parámetro: el ancho de banda.
5. El ancho de banda/tamaño de ventana 'h' tiene un significado físico, a diferencia de k -means .

Debilidades

1. La elección del tamaño de la ventana no es trivial.
2. Un tamaño de ventana inadecuado puede hacer que los modos se fusionen o generen modos "superficiales" adicionales.
3. A menudo requiere el uso de un tamaño de ventana adaptable.

Disponibilidad

Se pueden encontrar variantes del algoritmo en paquetes de procesamiento de imágenes y aprendizaje automático:

• ELKI . Herramienta de minería de datos Java con muchos algoritmos de agrupación.
• ImagenJ . Filtrado de imágenes mediante el filtro de desplazamiento medio.
• paquete ml . 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 un árbol de bolas para una búsqueda eficiente de puntos vecinos

Ver también

• DBSCAN
• Algoritmo ÓPTICO
• Estimación de la densidad del kernel (KDE)
• Núcleo (estadísticas)

Referencias

1. Cheng, Yizong (agosto de 1995). "Cambio medio, búsqueda de modo y agrupación". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 17 (8): 790–799. CiteSeerX  10.1.1.510.1222 . doi : 10.1109/34.400568.
2. 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 artificial . 24 (5): 603–619. CiteSeerX 10.1.1.160.3832 . doi :10.1109/34.1000236. S2CID  691081. 
3. 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.
4. Schnell, P. (1964). "Eine Methode zur Auffundung von Gruppen". Biometrische Zeitschrift (en alemán). 6 (1): 47–48. doi :10.1002/bimj.19640060105.
5. Aliyari Ghassabeh, Youness (1 de marzo de 2015). "Una condición suficiente para la convergencia del algoritmo de desplazamiento medio con el núcleo gaussiano". Revista de análisis multivariado . 135 : 1–10. doi : 10.1016/j.jmva.2014.11.009 .
6. Aliyari Ghassabeh, Youness (1 de septiembre de 2013). "Sobre la convergencia del algoritmo de desplazamiento medio en el espacio unidimensional". Letras de reconocimiento de patrones . 34 (12): 1423-1427. arXiv : 1407.2961 . Código Bib : 2013PaReL..34.1423A. doi :10.1016/j.patrec.2013.05.004. S2CID  10233475.
7. Li, Xiangru; Hu, Zhanyi; Wu, Fuchao (1 de junio de 2007). "Una nota sobre la convergencia del cambio medio". Reconocimiento de patrones . 40 (6): 1756-1762. Código Bib : 2007PatRe..40.1756L. doi :10.1016/j.patcog.2006.10.016.
8. Carreira-Perpiñán, Miguel A. (mayo de 2007). "El cambio medio gaussiano es un algoritmo EM". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 29 (5): 767–776. doi :10.1109/tpami.2007.1057. ISSN  0162-8828. PMID  17356198. S2CID  6694308.
9. Richard Szeliski, Visión por computadora, algoritmos y aplicaciones, Springer, 2011
10. Comaniciu, Dorin; Visvanathan Ramesh; Peter Meer (mayo de 2003). "Seguimiento de objetos basado en kernel". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 25 (5): 564–575. CiteSeerX 10.1.1.8.7474 . doi :10.1109/tpami.2003.1195991. S2CID  823678. 
11. Avidan, Shai (2005). "Seguimiento de conjunto". Conferencia de la IEEE Computer Society de 2005 sobre visión por computadora y reconocimiento de patrones (CVPR'05) . vol. 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.
12. Gary Bradski (1998) Seguimiento facial por 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.
13. 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) . vol. 2. IEEE. págs. 180-183. doi : 10.1109/IranianMVIP.2013.6779974. ISBN 978-1-4673-6184-2. S2CID  15864761.