Explicación de la segmentación de imágenes usando Mean Shift

107

¿Alguien podría ayudarme a comprender cómo funciona realmente la segmentación de Mean Shift?

Aquí hay una matriz de 8x8 que acabo de hacer.

  103  103  103  103  103  103  106  104   
  103  147  147  153  147  156  153  104   
  107  153  153  153  153  153  153  107   
  103  153  147  96   98   153  153  104   
  107  156  153  97   96   147  153  107   
  103  153  153  147  156  153  153  101   
  103  156  153  147  147  153  153  104   
  103  103  107  104  103  106  103  107

Usando la matriz anterior, ¿es posible explicar cómo la segmentación de cambio medio separaría los 3 niveles diferentes de números?

Sharpie
fuente
¿Tres niveles? Veo números alrededor de 100 y alrededor de 150.
John
2
Bueno, como es una segmentación, pensé que los números en el medio estarían muy lejos de los números del borde para ser incluidos en esa sección del límite. Por eso dije 3. Podría estar equivocado ya que realmente no entiendo cómo funciona este tipo de segmentación.
Sharpie
Oh ... tal vez estemos tomando niveles para significar cosas diferentes. Todo bien. :)
Juan
1
Me gusta la respuesta aceptada, pero no creo que muestre el panorama completo. En mi opinión, este pdf explica mejor la segmentación de cambio medio (creo que usar un espacio de mayor dimensión como ejemplo es mejor que 2d). eecs.umich.edu/vision/teaching/EECS442_2012/lectures/…
Helin Wang

Respuestas:

204

Primero lo básico:

La segmentación de cambio medio es una técnica de homogeneización local que es muy útil para amortiguar las diferencias de tonalidad o sombreado en objetos localizados. Un ejemplo es mejor que muchas palabras:

ingrese la descripción de la imagen aquí

Acción: reemplaza cada píxel con la media de los píxeles en una vecindad rango-r y cuyo valor está dentro de una distancia d.

El cambio medio toma generalmente 3 entradas:

  1. Una función de distancia para medir distancias entre píxeles. Por lo general, la distancia euclidiana, pero podría usarse cualquier otra función de distancia bien definida. La distancia de Manhattan es otra opción útil a veces.
  2. Un radio. Todos los píxeles dentro de este radio (medidos según la distancia anterior) se tendrán en cuenta para el cálculo.
  3. Una diferencia de valor. De todos los píxeles dentro del radio r, tomaremos solo aquellos cuyos valores estén dentro de esta diferencia para calcular la media

Tenga en cuenta que el algoritmo no está bien definido en las fronteras, por lo que diferentes implementaciones le darán resultados diferentes allí.

NO discutiré los detalles matemáticos sangrientos aquí, ya que son imposibles de mostrar sin la notación matemática adecuada, no están disponibles en StackOverflow, y también porque se pueden encontrar en buenas fuentes en otros lugares .

Veamos el centro de su matriz:

153  153  153  153 
147  96   98   153 
153  97   96   147   
153  153  147  156  

Con opciones razonables de radio y distancia, los cuatro píxeles centrales obtendrán el valor de 97 (su media) y serán diferentes de los píxeles adyacentes.

Calculémoslo en Mathematica . En lugar de mostrar los números reales, mostraremos un código de colores, por lo que es más fácil comprender lo que está sucediendo:

El código de colores para su matriz es:

ingrese la descripción de la imagen aquí

Luego tomamos un cambio medio razonable:

MeanShiftFilter[a, 3, 3]

Y obtenemos:

ingrese la descripción de la imagen aquí

Donde todos los elementos centrales son iguales (a 97, BTW).

Puede iterar varias veces con Mean Shift, tratando de obtener una coloración más homogénea. Después de algunas iteraciones, llega a una configuración no isotrópica estable:

ingrese la descripción de la imagen aquí

En este momento, debe quedar claro que no puede seleccionar cuántos "colores" obtendrá después de aplicar Mean Shift. Entonces, mostremos cómo hacerlo, porque esa es la segunda parte de su pregunta.

Lo que necesita para poder establecer el número de clústeres de salida de antemano es algo así como el clúster Kmeans .

Funciona de esta manera para su matriz:

b = ClusteringComponents[a, 3]

{{1, 1, 1, 1, 1, 1, 1, 1}, 
 {1, 2, 2, 3, 2, 3, 3, 1}, 
 {1, 3, 3, 3, 3, 3, 3, 1}, 
 {1, 3, 2, 1, 1, 3, 3, 1}, 
 {1, 3, 3, 1, 1, 2, 3, 1}, 
 {1, 3, 3, 2, 3, 3, 3, 1}, 
 {1, 3, 3, 2, 2, 3, 3, 1}, 
 {1, 1, 1, 1, 1, 1, 1, 1}}  

O:

ingrese la descripción de la imagen aquí

Lo cual es muy similar a nuestro resultado anterior, pero como puede ver, ahora solo tenemos tres niveles de salida.

HTH!

Dr. belisario
fuente
¿Existe una implementación de Matlab de cambio medio para la imagen?
Kaushik Acharya
2
@KaushikAcharya Ver shawnlankton.com/2007/11/mean-shift-segmentation-in-matlab
Dr. belisarius
164

Una segmentación Mean-Shift funciona así:

Los datos de la imagen se convierten en espacio de características. espacio de características

En su caso, todo lo que tiene son valores de intensidad, por lo que el espacio de características solo será unidimensional. (Puede calcular algunas características de textura, por ejemplo, y luego su espacio de características sería bidimensional, y estaría segmentando según la intensidad y la textura)

Las ventanas de búsqueda se distribuyen por el espacio de funciones. ingrese la descripción de la imagen aquí

El número de ventanas, el tamaño de la ventana y las ubicaciones iniciales son arbitrarios para este ejemplo, algo que se puede ajustar según las aplicaciones específicas.

Iteraciones de cambio medio:

1.) Se calculan las MEDIAS de las muestras de datos dentro de cada ventana ingrese la descripción de la imagen aquí

2.) Las ventanas se desplazan a las ubicaciones iguales a sus medias calculadas previamente ingrese la descripción de la imagen aquí

Los pasos 1.) y 2.) se repiten hasta la convergencia, es decir, todas las ventanas se han asentado en las ubicaciones finales ingrese la descripción de la imagen aquí

Las ventanas que terminan en las mismas ubicaciones se fusionan ingrese la descripción de la imagen aquí

Los datos se agrupan de acuerdo con los recorridos de la ventana. ingrese la descripción de la imagen aquí

... por ejemplo, todos los datos que fueron atravesados ​​por ventanas que terminaron en, digamos, la ubicación "2", formarán un grupo asociado con esa ubicación.

Entonces, esta segmentación producirá (casualmente) tres grupos. Ver esos grupos en el formato de imagen original podría parecerse a la última imagen de la respuesta de belisarius . La elección de diferentes tamaños de ventana y ubicaciones iniciales puede producir resultados diferentes.

mlai
fuente
¿El espacio de características no puede ser tridimensional, teniendo en cuenta la posición de cada píxel?
Helin Wang
@HelinWang Sí, podría.
mlai
Entiendo cómo se coloca la ventana en un espacio de características 1D, pero no veo cómo se puede aplicar su explicación a los algoritmos de cambio medio que incluyen una distancia de búsqueda espacial (por ejemplo, en píxeles) y una distancia espectral (diferencia de valor), por ejemplo como en la respuesta del Dr. belisarius. ¿Podrías aclarar esto?
Lennert
@Lennert Si entiendo su pregunta correctamente, entonces esencialmente lo que haría es agregar las ubicaciones de píxeles (x, y) como características, o agregar otras características basadas en la ubicación, al espacio de agrupación. Parece que la respuesta de Belisarius hace referencia a una implementación específica en Mathematica que puede hacer algo un poco más sofisticado. ¿Eso ayuda?
mlai
1
@Lennert Sí, creo que lo tienes. Puedo entender por qué encontró confusa mi respuesta. Dibujé mis 'ventanas' como bidimensionales, pero en realidad estaba tratando de representar la agrupación en solo los valores espectrales unidimensionales. Sería genial visualizar el grupo de cambio medio en el espacio de características tridimensionales con un dibujo o una animación (tal vez uno de estos días si tengo la hora)
mlai