Bildsegmentierung mit Mean Shift erklärt

107

Könnte mir bitte jemand helfen zu verstehen, wie die Mean Shift-Segmentierung tatsächlich funktioniert?

Hier ist eine 8x8-Matrix, die ich gerade zusammengestellt habe

  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

Kann anhand der obigen Matrix erklärt werden, wie die Segmentierung der mittleren Verschiebung die drei verschiedenen Zahlenebenen trennen würde.

Sharpie
quelle
Drei Ebenen? Ich sehe Zahlen um 100 und um 150.
John
2
Da es sich um eine Segmenation handelt, dachte ich, dass die Zahlen in der Mitte zu weit von den Randnummern entfernt sind, um in diesem Abschnitt der Grenze enthalten zu sein. Deshalb habe ich 3 gesagt. Ich könnte mich irren, da ich nicht wirklich verstehe, wie diese Art der Segmenation funktioniert.
Sharpie
Oh ... vielleicht nehmen wir Levels, um verschiedene Dinge zu bedeuten. Alles gut. :)
John
1
Ich mag die akzeptierte Antwort, aber ich glaube nicht, dass sie das ganze Bild zeigt. IMO erklärt dieses PDF die mittlere Verschiebungssegmentierung besser (die Verwendung eines Raums mit höheren Dimensionen als Beispiel ist meiner Meinung nach besser als 2d). eecs.umich.edu/vision/teaching/EECS442_2012/lectures/…
Helin Wang

Antworten:

204

Die Grundlagen zuerst:

Die Mean Shift-Segmentierung ist eine lokale Homogenisierungstechnik, die sehr nützlich ist, um Schattierungen oder Tonalitätsunterschiede in lokalisierten Objekten zu dämpfen. Ein Beispiel ist besser als viele Wörter:

Geben Sie hier die Bildbeschreibung ein

Aktion: Ersetzt jedes Pixel durch den Mittelwert der Pixel in einer Umgebung mit Bereich r, deren Wert innerhalb eines Abstands d liegt.

Die mittlere Verschiebung benötigt normalerweise 3 Eingaben:

  1. Eine Abstandsfunktion zum Messen von Abständen zwischen Pixeln. Normalerweise kann der euklidische Abstand, aber jede andere genau definierte Abstandsfunktion verwendet werden. Die Manhattan Entfernung ist manchmal eine andere nützliche Wahl.
  2. Ein Radius. Alle Pixel innerhalb dieses Radius (gemessen gemäß dem obigen Abstand) werden für die Berechnung berücksichtigt.
  3. Eine Wertdifferenz. Von allen Pixeln innerhalb des Radius r nehmen wir nur diejenigen, deren Werte innerhalb dieser Differenz liegen, zur Berechnung des Mittelwerts

Bitte beachten Sie, dass der Algorithmus an den Rändern nicht gut definiert ist, sodass unterschiedliche Implementierungen dort unterschiedliche Ergebnisse liefern.

Ich werde hier NICHT auf die blutigen mathematischen Details eingehen, da sie ohne die richtige mathematische Notation, die in StackOverflow nicht verfügbar ist, nicht angezeigt werden können und auch, weil sie an anderer Stelle aus guten Quellen stammen .

Schauen wir uns die Mitte Ihrer Matrix an:

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

Bei vernünftigen Auswahlmöglichkeiten für Radius und Abstand erhalten die vier mittleren Pixel den Wert 97 (ihren Mittelwert) und unterscheiden sich von den benachbarten Pixeln.

Berechnen wir es in Mathematica . Anstatt die tatsächlichen Zahlen anzuzeigen, wird eine Farbcodierung angezeigt, damit Sie leichter verstehen, was passiert:

Die Farbcodierung für Ihre Matrix lautet:

Geben Sie hier die Bildbeschreibung ein

Dann nehmen wir eine vernünftige mittlere Verschiebung:

MeanShiftFilter[a, 3, 3]

Und wir bekommen:

Geben Sie hier die Bildbeschreibung ein

Wobei alle Mittelelemente gleich sind (bis 97, übrigens).

Sie können mit Mean Shift mehrmals iterieren und versuchen, eine homogenere Färbung zu erzielen. Nach einigen Iterationen erhalten Sie eine stabile nicht-isotrope Konfiguration:

Geben Sie hier die Bildbeschreibung ein

Zu diesem Zeitpunkt sollte klar sein, dass Sie nicht auswählen können, wie viele "Farben" Sie nach dem Anwenden von Mean Shift erhalten. Lassen Sie uns also zeigen, wie es geht, denn das ist der zweite Teil Ihrer Frage.

Um die Anzahl der Ausgabecluster im Voraus festlegen zu können, benötigen Sie beispielsweise Kmeans-Clustering .

Für Ihre Matrix läuft es folgendermaßen ab:

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

Oder:

Geben Sie hier die Bildbeschreibung ein

Das ist unserem vorherigen Ergebnis sehr ähnlich, aber wie Sie sehen können, haben wir jetzt nur drei Ausgangspegel.

HTH!

Dr. Belisarius
quelle
Gibt es eine Matlab-Implementierung von Mean Shift for Image?
Kaushik Acharya
2
@ KaushikAcharya Siehe shawnlankton.com/2007/11/mean-shift-segmentation-in-matlab
Dr. belisarius
164

Eine Mean-Shift-Segmentierung funktioniert ungefähr so:

Die Bilddaten werden in den Feature-Space konvertiert Funktionsraum

In Ihrem Fall haben Sie nur Intensitätswerte, sodass der Merkmalsraum nur eindimensional ist. (Sie könnten beispielsweise einige Texturmerkmale berechnen, und dann wäre Ihr Merkmalsraum zweidimensional - und Sie würden nach Intensität und Textur segmentieren. )

Suchfenster sind über den Funktionsbereich verteilt Geben Sie hier die Bildbeschreibung ein

Die Anzahl der Fenster, die Fenstergröße und die anfänglichen Positionen sind für dieses Beispiel beliebig - etwas, das je nach Anwendung genau eingestellt werden kann

Mean-Shift-Iterationen:

1.) Die MEANs der Datenproben in jedem Fenster werden berechnet Geben Sie hier die Bildbeschreibung ein

2.) Die Fenster werden auf die Positionen verschoben, die ihren zuvor berechneten Mitteln entsprechen Geben Sie hier die Bildbeschreibung ein

Die Schritte 1.) und 2.) werden bis zur Konvergenz wiederholt, dh alle Fenster haben sich an den endgültigen Positionen niedergelassen Geben Sie hier die Bildbeschreibung ein

Die Fenster, die an denselben Speicherorten landen, werden zusammengeführt Geben Sie hier die Bildbeschreibung ein

Die Daten werden gemäß den Fensterdurchläufen geclustert Geben Sie hier die Bildbeschreibung ein

... z. B. bilden alle Daten, die von Fenstern durchlaufen wurden, die beispielsweise an Position „2“ gelandet sind, einen Cluster, der diesem Standort zugeordnet ist.

Diese Segmentierung erzeugt also (zufällig) drei Gruppen. Das Anzeigen dieser Gruppen im Originalbildformat ähnelt möglicherweise dem letzten Bild in Belisarius 'Antwort . Die Auswahl unterschiedlicher Fenstergrößen und Anfangspositionen kann zu unterschiedlichen Ergebnissen führen.

mlai
quelle
Kann der Merkmalsraum nicht dreidimensional sein und die Position jedes Pixels berücksichtigen?
Helin Wang
@HelinWang Ja, das könnte es.
Mlai
Ich verstehe, wie das Fenster in einem 1D-Merkmalsraum positioniert ist, aber ich sehe nicht, wie Ihre Erklärung auf mittlere Verschiebungsalgorithmen angewendet werden kann, die beispielsweise eine räumliche Suchentfernung (z. B. in Pixel) und eine spektrale Entfernung (Wertdifferenz) umfassen wie in der Antwort von Dr. belisarius. Könnten Sie das klarstellen?
Lennert
@Lennert Wenn ich Ihre Frage richtig verstehe, würden Sie im Wesentlichen die Pixelpositionen (x, y) als Features hinzufügen oder andere standortbasierte Features zum Clustering-Bereich hinzufügen. Es scheint, als ob Belisarius 'Antwort auf eine bestimmte Implementierung in Mathematica verweist, die etwas anspruchsvolleres bewirken könnte. Hilft das?
Mlai
1
@ Lennert Ja, ich denke du hast es verstanden. Ich kann verstehen, warum Sie meine Antwort verwirrend fanden. Ich habe meine 'Fenster' irgendwie zweidimensional gezeichnet, aber eigentlich habe ich versucht, die Clusterbildung nur auf den eindimensionalen Spektralwerten darzustellen. Es wäre ziemlich cool, den mittleren Verschiebungscluster im dreidimensionalen Merkmalsraum mit einer Zeichnung oder Animation zu visualisieren (vielleicht eines Tages, wenn ich Zeit habe)
mlai