Mean shift

Mean shift es una técnica no paramétrica de análisis matemático del espacio de características para localizar los máximos de una función de densidad, un algoritmo denominado de búsqueda de modos.^[1]​ Entre los ámbitos de aplicación se incluyen el análisis de clúster en visión por ordenador y el procesamiento de imágenes.^[2]​

Historia

El procedimiento de mean shift suele atribuirse a los trabajos de Fukunaga y Hostetler en 1975,^[3]​ pero recuerda a los de Schnell en 1964.^[4]​

Descripción general

Mean shift es un procedimiento para localizar los máximos -las modas- de una función de densidad dados datos discretos muestreados a partir de dicha función.^[1]​ Se trata de un método iterativo, y partimos de una estimación inicial ${\displaystyle x}$. Se da la siguiente función kernel ${\displaystyle K(x_{i}-x)}$. 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, ${\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}$ . La media ponderada de la densidad en la ventana determinada por ${\displaystyle K}$ es:

${\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)}}}$

Donde, ${\displaystyle N(x)}$ es la vecindad de ${\displaystyle x}$, un conjunto de puntos para los que ${\displaystyle K(x_{i}-x)\neq 0}$.

La diferencia ${\displaystyle m(x)-x}$ se denomina mean shift en Fukunaga y Hostetler.^[3]​ El algoritmo de mean shift establece ahora ${\displaystyle x\leftarrow m(x)}$ y repite la estimación hasta que ${\displaystyle m(x)}$ converja.

Aunque el algoritmo de desplazamiento de la media 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 demostró la convergencia del algoritmo de desplazamiento de la media 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. También se ha demostrado la convergencia del algoritmo en dimensiones superiores con un número finito de puntos estacionarios (o aislados),^[5]​^[7]​ pero no se han proporcionado las condiciones suficientes para que una función de núcleo general tenga puntos estacionarios (o aislados) finitos.

El mean shift gaussiano es un algoritmo esperanza-maximización.^[8]​

Detalles

Sean los datos un conjunto finito ${\displaystyle S}$ incrustado en el espacio euclidiano de dimensión ${\displaystyle X}$. Sea ${\displaystyle K}$ un núcleo plano que es la función característica de la bola 𝜆 en ${\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, ${\displaystyle s\leftarrow m(s)}$ es realizado para todos los ${\displaystyle s\in S}$ de forma simultánea. La primera cuestión es cómo estimar la función de densidad a partir de un conjunto disperso de muestras. Uno de los enfoques más sencillos consiste en suavizar los datos, por ejemplo, convolviéndolos con un núcleo fijo de anchura ${\displaystyle h}$:

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

Donde ${\displaystyle x_{i}}$ son las muestras de entrada y ${\displaystyle k(r)}$ es la función kernel (o ventana de Parzen). ${\displaystyle h}$ es el único parámetro del algoritmo y se denomina ancho de banda. Este enfoque se conoce como estimación de la densidad del kernel o técnica de la ventana de Parzen. Una vez calculado ${\displaystyle f(x)}$ de la ecuación anterior, podemos encontrar sus máximos locales utilizando el ascenso gradiente o alguna otra técnica de optimización. El problema de este planteamiento de «fuerza bruta» es que, para dimensiones mayores, resulta prohibitivo desde el punto de vista informático evaluar ${\displaystyle f(x)}$ sobre el espacio de búsqueda completo. En su lugar, el desplazamiento medio utiliza una variante de lo que se conoce en la literatura de optimización como descenso de gradiente de reinicio múltiple. Empezando con una estimación de un máximo local, ${\displaystyle y_{k}}$, que puede ser un punto de datos de entrada aleatorio ${\displaystyle x_{1}}$, el desplazamiento medio calcula el gradiente de la estimación de la densidad ${\displaystyle f(x)}$ en ${\displaystyle y_{k}}$ y da un paso cuesta arriba en esa dirección.^[9]​

Tipos de kernel

La definición de kernel dice: Dejar que ${\displaystyle X}$ sea sea el espacio euclidiano 𝑛-dimensional ${\displaystyle \mathbb {R} ^{n}}$. La norma de ${\displaystyle x}$ es un número no negativo, ${\displaystyle \|x\|^{2}=x^{\top }x\geq 0}$. La función ${\displaystyle K:X\rightarrow \mathbb {R} }$ se dice que es un núcleo si existe un perfil, ${\displaystyle k:[0,\infty ]\rightarrow \mathbb {R} }$, de forma que:

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

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

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

Kernel plano

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

Kernel gaussiano

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

Donde el parámetro de desviación típica ${\displaystyle \sigma }$ funciona como parámetro de ancho de banda, ${\displaystyle h}$.^[10]​

Aplicaciones

Agrupación

Consideremos un conjunto de puntos en un espacio bidimensional. Supongamos una ventana circular centrada en ${\displaystyle C}$ y con radio ${\displaystyle r}$ como kernel. El desplazamiento medio es un algoritmo de escalada que consiste en desplazar este núcleo de forma iterativa 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 que lo componen. El método de cálculo de 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, se asignará primero a cada punto un peso que decaerá exponencialmente a medida que aumente la distancia al centro del núcleo. En el momento de la convergencia, no habrá ninguna dirección en la que un desplazamiento pueda acomodar más puntos dentro del núcleo.

Seguimiento

El algoritmo de desplazamiento medio puede utilizarse para el seguimiento visual. El algoritmo más sencillo 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 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 se encuentre en el objeto de la imagen anterior. Algunos algoritmos, como el seguimiento de objetos basado en kernel,^[11]​ el seguimiento de conjuntos,^[12]​CAMshift^[13]​^[14]​ amplían esta idea.

Suavizado

Dejemos que ${\displaystyle x_{i}}$ y ${\displaystyle z_{i},i=1,...,n,}$ sea el 𝑑-dimensionales de entrada y los píxeles de la imagen filtrada en el dominio conjunto espacio-rango. Para cada píxel,

• Iniciar ${\displaystyle j=1}$ y ${\displaystyle y_{i,1}=x_{i}}$
• Calcular ${\displaystyle y_{i,j+1}}$ de acuerdo con ${\displaystyle m(\cdot )}$ hasta la convergencia ${\displaystyle y=y_{i,c}}$
• Asignar ${\displaystyle z_{i}=(x_{i}^{s},y_{i,c}^{r})}$. 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 localización espacial tendrán la componente de rango del punto de convergencia ${\displaystyle y_{i,c}^{r}}$.

Puntos fuertes

1. El 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.^[15]​

Debilidades

1. La selección del tamaño de una ventana no es trivial.
2. Un tamaño de ventana inadecuado puede provocar la fusión de modos o generar modos adicionales «poco profundos».
3. A menudo es necesario utilizar 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 Java de minería de datos con numerosos 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 la implementación de mean-shift a través del método cvMeanShift^[16]​
• Orfeo toolbox. Una implementación en C++.
• La implementación de scikit-learn Numpy/Python utiliza un árbol de bolas para una búsqueda eficiente de puntos vecinos.

Véase también

• DBSCAN
• Estimación de Densidad de Kernel (KDE)
• Kernel (estadística)

Referencias