Explication de la segmentation d'image à l'aide du décalage moyen

107

Quelqu'un pourrait-il m'aider à comprendre comment fonctionne réellement la segmentation Mean Shift?

Voici une matrice 8x8 que je viens de créer

  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

En utilisant la matrice ci-dessus, est-il possible d'expliquer comment la segmentation par décalage moyen séparerait les 3 différents niveaux de nombres?

Sharpie
la source
Trois niveaux? Je vois des nombres autour de 100 et autour de 150.
John
2
Eh bien, comme c'est une segmentation, je pensais que les nombres au milieu seraient trop éloignés des nombres de bord pour être inclus dans cette section de la frontière. C'est pourquoi j'ai dit 3. Je peux me tromper car je ne comprends pas vraiment comment fonctionne ce type de segmentation.
Sharpie
Oh ... peut-être que nous considérons que les niveaux signifient différentes choses. Tout bon. :)
John
1
J'aime la réponse acceptée, mais je ne pense pas qu'elle ait montré toute la situation. IMO ce pdf explique mieux la segmentation moyenne de décalage (en utilisant un espace de dimension plus élevé comme exemple est meilleur que 2d je pense). eecs.umich.edu/vision/teaching/EECS442_2012/lectures/…
Helin Wang

Réponses:

204

Les bases d'abord:

La segmentation Mean Shift est une technique d'homogénéisation locale très utile pour amortir les différences d'ombrage ou de tonalité dans des objets localisés. Un exemple vaut mieux que plusieurs mots:

entrez la description de l'image ici

Action: remplace chaque pixel par la moyenne des pixels dans un voisinage range-r et dont la valeur est à une distance d.

Le décalage moyen prend généralement 3 entrées:

  1. Une fonction de distance pour mesurer les distances entre les pixels. Habituellement, la distance euclidienne, mais toute autre fonction de distance bien définie peut être utilisée. La Manhattan Distance est parfois un autre choix utile.
  2. Un rayon. Tous les pixels dans ce rayon (mesurés selon la distance ci-dessus) seront pris en compte pour le calcul.
  3. Une différence de valeur. De tous les pixels à l'intérieur du rayon r, nous ne prendrons que ceux dont les valeurs sont comprises dans cette différence pour calculer la moyenne

Veuillez noter que l'algorithme n'est pas bien défini aux frontières, donc différentes implémentations vous donneront des résultats différents là-bas.

Je ne discuterai PAS des détails mathématiques sanglants ici, car ils sont impossibles à montrer sans une notation mathématique appropriée, non disponible dans StackOverflow, et aussi parce qu'ils peuvent être trouvés à partir de bonnes sources ailleurs .

Regardons le centre de votre matrice:

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

Avec des choix raisonnables de rayon et de distance, les quatre pixels centraux auront la valeur 97 (leur moyenne) et seront différents des pixels adjacents.

Calculons-le dans Mathematica . Au lieu d'afficher les chiffres réels, nous afficherons un code couleur, il est donc plus facile de comprendre ce qui se passe:

Le code couleur de votre matrice est:

entrez la description de l'image ici

Ensuite, nous prenons un décalage moyen raisonnable:

MeanShiftFilter[a, 3, 3]

Et nous obtenons:

entrez la description de l'image ici

Où tous les éléments centraux sont égaux (à 97, BTW).

Vous pouvez itérer plusieurs fois avec Mean Shift, en essayant d'obtenir une coloration plus homogène. Après quelques itérations, vous arrivez à une configuration non isotrope stable:

entrez la description de l'image ici

À ce stade, il devrait être clair que vous ne pouvez pas sélectionner le nombre de «couleurs» que vous obtenez après l'application de Mean Shift. Alors, montrons comment faire, car c'est la deuxième partie de votre question.

Ce dont vous avez besoin pour pouvoir définir le nombre de clusters de sortie à l'avance est quelque chose comme le clustering Kmeans .

Il fonctionne de cette façon pour votre matrice:

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}}  

Ou:

entrez la description de l'image ici

Ce qui est très similaire à notre résultat précédent, mais comme vous pouvez le voir, nous n'avons plus que trois niveaux de sortie.

HTH!

Dr Bélisarius
la source
Existe-t-il une implémentation Matlab de Mean shift for image?
Kaushik Acharya
2
@KaushikAcharya Voir shawnlankton.com/2007/11/mean-shift-segmentation-in-matlab
Dr. belisarius
164

Une segmentation Mean-Shift fonctionne comme ceci:

Les données d'image sont converties en espace de fonctionnalités espace caractéristique

Dans votre cas, vous n'avez que des valeurs d'intensité, donc l'espace des fonctionnalités ne sera qu'unidimensionnel. (Vous pourriez calculer certaines caractéristiques de texture, par exemple, puis votre espace d'entités serait bidimensionnel - et vous segmenteriez en fonction de l'intensité et de la texture)

Les fenêtres de recherche sont réparties sur l'espace des fonctionnalités entrez la description de l'image ici

Le nombre de fenêtres, la taille de la fenêtre et les emplacements initiaux sont arbitraires pour cet exemple - quelque chose qui peut être ajusté en fonction des applications spécifiques

Itérations de décalage moyen:

1.) Les MOYENNES des échantillons de données dans chaque fenêtre sont calculées entrez la description de l'image ici

2.) Les fenêtres sont décalées vers les emplacements égaux à leurs moyennes précédemment calculées entrez la description de l'image ici

Les étapes 1.) et 2.) sont répétées jusqu'à la convergence, c'est-à-dire que toutes les fenêtres se sont installées sur les emplacements finaux entrez la description de l'image ici

Les fenêtres qui se retrouvent aux mêmes emplacements sont fusionnées entrez la description de l'image ici

Les données sont regroupées en fonction des traversées de fenêtres entrez la description de l'image ici

... Par exemple, toutes les données qui ont été traversées par des fenêtres qui se sont terminées, par exemple, à l'emplacement «2», formeront un cluster associé à cet emplacement.

Ainsi, cette segmentation produira (par coïncidence) trois groupes. L'affichage de ces groupes dans le format d'image d'origine peut ressembler à la dernière image de la réponse de Bélisaire . Le choix de différentes tailles de fenêtre et emplacements initiaux peut produire des résultats différents.

mlai
la source
l'espace des fonctionnalités ne peut-il pas être tridimensionnel, en tenant compte de la position de chaque pixel?
Helin Wang
@HelinWang Oui, c'est possible.
mlai
Je comprends comment la fenêtre est positionnée dans un espace d'entités 1D, mais je ne vois pas comment votre explication peut être appliquée aux algorithmes de décalage moyen qui incluent une distance de recherche spatiale (par exemple en pixels) et une distance spectrale (différence de valeur), par exemple comme dans la réponse du Dr belisarius. Pourriez-vous clarifier cela?
Lennert
@Lennert Si je comprends bien votre question, alors ce que vous feriez essentiellement est d'ajouter les emplacements de pixels (x, y) en tant que caractéristiques, ou d'ajouter d'autres caractéristiques basées sur l'emplacement, à l'espace de clustering. Il semble que la réponse de Belisarius fait référence à une implémentation spécifique dans Mathematica qui peut faire quelque chose d'un peu plus sophistiqué. Est ce que ça aide?
mlai
1
@Lennert Ouais, je pense que tu l'as compris. Je peux comprendre pourquoi vous avez trouvé ma réponse déroutante. J'ai un peu dessiné mes «fenêtres» en deux dimensions, mais en réalité, j'essayais de représenter le regroupement uniquement sur les valeurs spectrales unidimensionnelles. Ce serait plutôt cool de visualiser un cluster de décalage moyen dans un espace de fonctionnalités en trois dimensions avec un dessin ou une animation (peut-être un de ces jours si j'ai l'heure)
mlai