Gewusst wie: Pixelpakete in einem Bild zu repräsentativen Punktkoordinaten (x, y)

7

Lassen Sie uns ein Bild (Graustufen oder sogar Binärbilder) haben, wie in der folgenden Abbildung auf der linken Seite gezeigt. Ziel ist es, eine Liste von Punkten zu generieren, dh Koordinaten in Form von (x, y) für jede Packung der dunkle Pixel im Bild.
Was sind die richtigen Bildverarbeitungswerkzeuge, um dies zu tun, und wo sind sie verfügbar?

Pixelpakete zu Punktkoordinaten


Updates:
1) Hier finden Sie möglicherweise weitere Details zum Problem. (Beachten Sie die Variation in der Größe der Packungen)

Einzelheiten

Ich kann vorschlagen, dass Packungen erkannt werden, um die konvexe Rumpfgrenze für jede zu berechnen und dann den repräsentativen Schwerpunkt zu finden (Einzelheiten siehe hier) .

Pixelpaket zum konvexen Rumpf zum Mittelpunkt


2)
Hier ist das Ergebnis, das durch Anwendung der Distanztransformation (vorgeschlagen von "Libor") erzeugt wurde. Beachten Sie meine Anmerkungen in der Abbildung. Die Methode funktioniert nicht wie versprochen!

Geben Sie hier die Bildbeschreibung ein

3)
Erosion beseitigt kleine Packungen!

from __future__ import division
from scipy import zeros, ndimage as dsp
from pylab import subplot,plot,matshow,show

img = zeros((30,30))
img[10:14,10:14] = 1
img[16:17,16:17] = 1
img[19:23,19] = 1
img[19,19:23] = 1

subplot(221)
matshow(img,0)

subplot(222)
y = dsp.binary_erosion(img,[[1,1],[1,1]])
matshow(y,0)

subplot(223)
y = dsp.binary_erosion(img,[[0,1,0],[1,1,1],[0,1,0]])
matshow(y,0)

subplot(224)
y = dsp.binary_erosion(img,[[1,1,1],[1,1,1],[1,1,1]])
matshow(y,0)

show()

Geben Sie hier die Bildbeschreibung ein

4)
Nun, hier ist eine Python- Implementierung (dh die Sprache der Liebe :)) der Etikettierungsidee (ebenfalls von "Jean-Yves" unten vorgeschlagen):

subplot(221)
l,n = dsp.label(img)
sl = dsp.find_objects(l)
for s in sl:
    x = (s[1].start+s[1].stop-1)/2
    y = (s[0].start+s[0].stop-1)/2
    plot(x,y,'wo')

und das Ergebnis:

Geben Sie hier die Bildbeschreibung ein

Beachten Sie, dass die Hintergrundprozedur in der Funktion eine anstrengende Iteration sein sollte , obwohl sie in Python aufgrund der Scipy-Leistung so schnell ausgeführt labelwird. Dies kann als Kompromiss angesehen werden. Daher bin ich eine Weile bestrebt, nach effizienteren Algorithmen zu suchen. Beachten Sie auch, dass ich im obigen Code das Zentrum der Geometrie so einfach gefunden habe, während dies bei komplexen oder asymmetrischen Formen zu einer Verzerrung der Positionierung führen kann. Das heißt, es ist in Arbeit;).

5)
Hier ist ein komplexer Fall (ein reales Bild), der von hier aus aufgenommen wurde , auf den der Kennzeichnungsvorschlag angewendet wurde, und Sie sehen die Ergebnisse. Beachten Sie, dass der gesamte Vorgang einschließlich des Beschriftens und Findens der Objekte nur 0,015 s dauerte. Scipy Jungs, haben sehr gute Arbeit geleistet, denke ich. Beeindruckend! {Rechtsklick auf Bild, Bild anklicken für volle Auflösung}

Geben Sie hier die Bildbeschreibung ein

Entwickler
quelle
Wissen Sie: 1) Anzahl der Packungen. 2) Max / Min x-Größe einer Packung. 3) Maximale / minimale Größe einer Packung.
Spacey
@Mohammad Given ist nur ein Bild. Somit ist keine der von Ihnen genannten erforderlichen Informationen verfügbar.
Entwickler
Wenn Sie die Anzahl der Packungen ermitteln können, würde ich dies als Wert von 'k' in einem generischen k-means-Algorithmus verwenden. Bei einem Wert von k konvergiert es zur Mitte jedes Clusters. Ich bin mir jedoch nicht sicher, wie Sie den Wert von 'k' bestimmen können. Wie werden Sie das feststellen?
Spacey
Sie benötigen eine Subpixel-Genauigkeit für die Entfernungstransformation / -erosion, um Maxima in den kleinen Patches (z. B. 2x2) zu erkennen. Es gibt Maxima, die jedoch nicht erkannt werden können, da Sie sie bei Ihrer Stichprobe überspringen. Im Falle einer Entfernungstransformation können Sie Ihr Bild um den Faktor zwei hochabtasten oder die Transformation für Subpixelpositionen (0,0, 0,5, 1,0, 1,5 ...) berechnen. Im Falle einer Erosion können Sie diese mithilfe der PDE-basierten Morphologie (iterativ) implementieren.
Libor
@ Entwickler diese Frage von mir auf SO könnte von Interesse sein: stackoverflow.com/questions/4087919/…
Ivo Flipse

Antworten:

4

Nur ein naiver Vorschlag: Kennen Sie sich mit der Kennzeichnung von Komponenten aus ?

Bei dieser Technik geht es darum, Teile von "berührenden" Pixeln zu finden und ihnen eine Bezeichnung zuzuweisen, z . B. eine Ganzzahl. Sie können dann jeden Riss einzeln abfragen und nach dem Pixel suchen, das dieselbe Bezeichnung hat.

In MATLAB ist hier die Funktion, die dies trivial macht: bwlabel

Jean-Yves
quelle
Danke für den Vorschlag. Ich war bereits so vorgegangen und habe, wie Sie bereits erwähnt haben, den Beitrag mit einer Implementierung in Python aktualisiert . Ich habe einige Probleme bezüglich der Verwendung der Kennzeichnung in Update 4 festgestellt :
Entwickler
Ich habe dies positiv bewertet, da es ein anderer Ansatz ist, um das Problem zu lösen. Vielen Dank für das Teilen :)
Entwickler
Könnten Sie das Update 4 klarstellen? Ich verstehe nicht, was du mit Kompromiss und Erschöpfung meinst.
Jean-Yves
Das Beschriften ist eine iterative Aufgabe, die viel Rechenaufwand erfordert. Allerdings hat Scipy Jungs hervorragende Arbeit geleistet (oder einige Tricks!), Um es fast sofort zu tun. Ich habe einen wirklich komplexen Fall zur Bewertung vorgelegt, der nur in 0,015 s funktioniert hat. Ist es nicht großartig? Beachten Sie, dass der zweite Teil, dh das Finden der Mitte der erkannten Pakete, immer noch eine Frage ist. Offensichtlich wird die Anwendung einer konvexen Hülle für einen solchen Satz von Packungen nicht empfohlen.
Entwickler
Dort bin ich anderer Meinung: Die Kennzeichnung verbundener Komponenten ist NICHT expansiv. In den meisten modernen Implementierungen wird es in linearer Zeit ausgeführt, und einige haben es sogar geschafft, Multithreading auszuführen.
Jean-Yves
3

Sie können auch eine Entfernungstransformation für das Bild ausführen und dann lokale Maxima erkennen (Suche nach Pixeln mit dem höchsten / niedrigsten Wert aller Pixel im 3x3-Pixel-Patch - kann je nach erwartetem Mindestabstand zwischen den ursprünglichen Blobs größer sein).

Beachten Sie, dass Sie zum Erkennen von Merkmalen mit einer Größe von 1 bis 3 Pixel Ihre Abtastfrequenz verdoppeln müssen (entweder das Quellbild hochskalieren oder eine Entfernungstransformation / -erosion mit Subpixel-Genauigkeit durchführen).

AKTUALISIEREN:

Sowohl bei der Entfernungstransformation als auch bei der Erosion wird davon ausgegangen, dass die von Ihnen erkannten Merkmale konvex sind. Beispielsweise kann etwas mit U-Form mehrmals in Ihrem Detektor ausgelöst werden.

Eine ausgefeiltere Methode für eine solche Segmentierung basiert auf Ebenensätzen und aktiven Konturen . Es beginnt mit einer großen geschlossenen Kurve, die iterativ an Ihre Funktionen angepasst wird. Diese Methode wurde an meiner Universität zum Zählen von Zellen und zum Nachweis von Chromosomen in Mikroskopbildern verwendet.

Libor
quelle
Das Ergebnis meiner Umsetzung Ihrer Idee sehen Sie im Abschnitt Updates: 2 . Es scheint nicht wie erwartet zu funktionieren :(
Entwickler
OK, ich habe meine Antwort erweitert.
Libor
Ich habe dies positiv bewertet, da es ein anderer Ansatz ist, um das Problem zu lösen. Vielen Dank für das Teilen :)
Entwickler
2

Eine Möglichkeit wäre , das Bild wiederholt morphologisch zu erodieren, bis es vollständig erodiert ist. Zu diesem Zeitpunkt würde jeder der oben gezeigten Blobs auf ein einzelnes Pixel reduziert; Sie können die Positionen dieser Pixel als Liste der Punkte verwenden, nach denen Sie suchen.

Jason R.
quelle
Einige Punkte: 1) Wie kann ich die Iteration stoppen? 2) Es kann verschwinden, dass diese Packungen kleiner sind. 3) Es sieht sehr rechenintensiv aus, da für den gesamten Datensatz eine Iteration erforderlich ist. Beachten Sie, dass das Bild groß sein kann.
Entwickler
Ich habe Ihre Idee schnell in der aktuellen Form umgesetzt, aber sie hat nicht funktioniert. Es eliminiert kleine Packungen. Alle meine vorherigen Kommentare gelten.
Entwickler
Ich bin mir nicht sicher, was du mit "kleinen Packungen" meinst. Werden im Beispielbild irgendwelche gezeigt?
Jason R
Nun, wie gezeigt, sind die Packungen in verschiedenen Größen und Formen und als ich iterative Erosion anwendete (Python: Scipy: Spatial: Erosion), verschwanden die kleineren (oder schmaleren). Beachten Sie, dass das Paket im Eingabebild im tatsächlichen Fall im Bereich von einem Pixel bis sehr groß sein kann.
Entwickler
@Developer Kennen Sie die Anzahl der "Packs" im Voraus? Zum Beispiel haben Sie hier 6.
Spacey
2

Ich befürchte, dass es nicht einfach sein wird, wie auch immer Sie sich dafür entscheiden, denn um die Ziele Clustern zuzuweisen, müssen Sie das Bild (mindestens einmal) durchgehen.

Ich nehme an, dass das Erhalten der Punkte das einfachere Problem der beiden ist (Sie wenden wahrscheinlich bereits eine Form der Schwellenwertbildung an).

Um die Cluster, in denen Punkte gruppiert sind, wiederherzustellen und dies schnell zu tun, können Sie eine Quad-Tree-Struktur erstellen , die "Ketten verbundener Pixel" enthält, die sich irgendwo im Bereich der Quad-Tree-Zelle befinden.

Auf diese Weise können Sie das Bild durchlaufen und, sobald Sie auf ein Pixel stoßen, das ein Ziel ist, es in Ihre Quad-Tree-Struktur "schieben".

Diese "Push" -Operation würde einen iterativen Prozess starten, der die Zelle (mit anderen Worten den spezifischen Bereich des Bildes) zurückgibt, in dem sich das bestimmte Pixel befindet. Sie könnten dann alle Pixelketten durchlaufen, die dieser Zelle zugewiesen sind, und es versuchen um das Pixel (erneut) an die Pixelkette zu "schieben". Eine Pixelkette akzeptiert ein neues Pixel, wenn es sich mindestens 1 Pixel in der Nähe eines seiner bereits zugewiesenen Pixel befindet. Wenn keine Pixelkette das neue Pixel "akzeptiert", erstellen Sie eine neue Pixelkette in dieser Zelle und weisen Sie ihr das neue Pixel zu.

Der Quad-Baum hier ist eine Möglichkeit, die Suche nach der nächsten Pixelkette einzuschränken. Dies ist erforderlich, wenn Ihr Bild groß und die Ziele zahlreich sind, damit die Pixelketten-Push-Vorgänge schnell ausgeführt werden. Wenn Sie wissen, dass Sie nicht mit einer großen Anzahl von Zielen zu tun haben, können Sie sogar den Quad-Tree überspringen und eine einfache "Liste der Pixelketten" führen. Jedes Mal, wenn Sie auf ein "Ziel" stoßen, können Sie die Listen durchlaufen und versuchen, das Pixel darauf zu "schieben". Wenn keine Liste das Pixel "zulässt", erstellen Sie eine neue Liste und weisen Sie das Pixel zu.

Unabhängig davon, wie Sie sich dafür entscheiden, werden Sie am Ende dieses Prozesses eine Reihe verbundener "Pixelketten" (Ihre Cluster) haben, die Sie dann an einen anderen Teil Ihres Programms übergeben können, der sich mit deren Schätzung befasst Standort. Dies kann eine konvexe Hülle, eine Modellanpassung (zum Beispiel ein Ellipsoid oder ein anderes) oder einfach der Mittelwert / Median der x, y-Koordinaten sein.

Ich hoffe das hilft.

A_A
quelle
Ich habe dies positiv bewertet, da es ein anderer Ansatz ist, um das Problem zu lösen. Vielen Dank für das Teilen :)
Entwickler