Cambio medio

Técnica matemática

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

Historia

El procedimiento de desplazamiento medio suele atribuirse al trabajo de Fukunaga y Hostetler en 1975. ^[3] Sin embargo, recuerda al trabajo anterior de Schnell en 1964. ^[4]

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 . Sea dada una función kernel . Esta función determina el peso de los puntos cercanos para la reestimación de la media. Normalmente se utiliza un kernel gaussiano sobre 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á el vecindario de , un conjunto de puntos para los cuales . ${\displaystyle N(x)}$ ${\displaystyle x}$ ${\displaystyle K(x_{i}-x)\neq 0}$

La diferencia se denomina 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, aún 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 de núcleo general tenga puntos estacionarios (o aislados) finitos.

El desplazamiento medio gaussiano es un algoritmo de maximización de expectativas . ^[8]

Detalles

Sea datos un conjunto finito embebido en el espacio euclidiano de dimensión -, . 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 ejecuta 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, convolvié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)}$

donde son las muestras de entrada y es la función kernel (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 densidad kernel o técnica de ventana de Parzen. Una vez que hemos calculado a partir de la ecuación anterior, podemos encontrar sus máximos locales utilizando ascenso de gradiente o alguna otra técnica de optimización. El problema con este enfoque de "fuerza bruta" es que, para dimensiones superiores, se vuelve computacionalmente prohibitivo evaluar sobre 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 . A partir de alguna estimación para un máximo local, , que puede ser un punto de datos de entrada aleatorio , el cambio 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 de núcleo: Sea el espacio euclidiano de dimensión . 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 continua por partes y ${\displaystyle \int _{0}^{\infty }k(r)\,dr<\infty \ }$

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

Grano 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 el parámetro de ancho de banda, . ${\displaystyle \sigma }$ ${\displaystyle h}$

Aplicaciones

Agrupamiento

Considere un conjunto de puntos en un espacio bidimensional. Supongamos una ventana circular centrada en un núcleo y cuyo radio es el núcleo. El desplazamiento medio es un algoritmo de escalada que implica desplazar este núcleo iterativamente a una región de mayor densidad hasta la convergencia. Cada desplazamiento se define mediante un vector de desplazamiento medio. El vector de desplazamiento medio siempre apunta hacia la dirección del aumento máximo de la densidad. En cada iteración, el núcleo se desplaza hacia el centroide o la media de los puntos dentro de él. 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, entonces a cada punto se le asignará primero un peso que decaerá exponencialmente a medida que aumenta la distancia desde el centro del núcleo. En la convergencia, no habrá ninguna dirección en la que un desplazamiento pueda acomodar más puntos dentro del núcleo. ${\displaystyle C}$ ${\displaystyle r}$

Seguimiento

El algoritmo de desplazamiento 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 utilizarí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 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

Sean y los píxeles de entrada y de imagen filtrada en dimensiones 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 de acuerdo a 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 espaciales 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 tamaño de ancho de banda/ventana 'h' tiene un significado físico, a diferencia de k -means .

Debilidades

1. La selección del tamaño de una ventana no es algo trivial.
2. Un tamaño de ventana inadecuado puede provocar que se fusionen modos o generar 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 aprendizaje automático y procesamiento de imágenes:

• ELKI . Herramienta de minería de datos Java con muchos algoritmos de clusterización.
• ImageJ . Filtrado de imágenes utilizando el filtro de desplazamiento medio.
• mlpack . Implementación eficiente basada en algoritmo de árbol dual.
• OpenCV contiene la implementación del cambio de media a través del método cvMeanShift
• Caja de herramientas Orfeo . Implementación en C++.
• La implementación de Numpy/Python de scikit-learn utiliza un árbol de bolas para una búsqueda eficiente de puntos vecinos

Véase también

• Escaneo de base de datos
• Algoritmo ÓPTICO
• Estimación de la densidad del kernel (KDE)
• Kernel (estadísticas)

Referencias

1. Cheng, Yizong (agosto de 1995). "Desplazamiento de la media, búsqueda de modos y agrupamiento". IEEE Transactions on Pattern Analysis and Machine Intelligence . 17 (8): 790–799. CiteSeerX  10.1.1.510.1222 . doi :10.1109/34.400568.
2. Comaniciu, Dorin; Peter Meer (mayo de 2002). "Desplazamiento medio: un enfoque robusto hacia el análisis del espacio de características". IEEE Transactions on Pattern Analysis and Machine Intelligence . 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". IEEE Transactions on Information Theory . 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 de la media con núcleo gaussiano". Journal of Multivariate Analysis . 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 de la media en el espacio unidimensional". Pattern Recognition Letters . 34 (12): 1423–1427. arXiv : 1407.2961 . Código Bibliográfico :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 de media". Reconocimiento de patrones . 40 (6): 1756–1762. Bibcode :2007PatRe..40.1756L. doi :10.1016/j.patcog.2006.10.016.
8. Carreira-Perpinan, Miguel A. (mayo de 2007). "Gaussian Mean-Shift Is an EM Algorithm" (El desplazamiento medio gaussiano es un algoritmo EM). IEEE Transactions on Pattern Analysis and Machine Intelligence (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 artificial, algoritmos y aplicaciones, Springer, 2011
10. Comaniciu, Dorin; Visvanathan Ramesh; Peter Meer (mayo de 2003). "Seguimiento de objetos basado en kernel". IEEE Transactions on Pattern Analysis and Machine Intelligence . 25 (5): 564–575. CiteSeerX 10.1.1.8.7474 . doi :10.1109/tpami.2003.1195991. S2CID  823678. 
11. Avidan, Shai (2005). "Seguimiento de conjuntos". Conferencia de la IEEE Computer Society sobre visión artificial y reconocimiento de patrones (CVPR'05) de 2005. Vol. 2. San Diego, California: IEEE. págs. 494–501. doi :10.1109/CVPR.2005.144. ISBN 978-0-7695-2372-9. Número de identificación personal  17170479. Número de identificación personal  1638397.
12. Gary Bradski (1998) Seguimiento facial mediante visión artificial para su uso en una interfaz de usuario perceptiva Archivado el 17 de abril de 2012 en Wayback Machine , Intel Technology Journal, n.º Q2.
13. Emami, Ebrahim (2013). "Detección y corrección de fallos en línea para el algoritmo de seguimiento CAMShift". 2013 8.ª 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. Número de identificación del sujeto  15864761.