[GO] Implementierte Bildsegmentierung in Python (Union-Find)

Vorheriger Artikel war interessant, weil ich ein wenig Bildverarbeitung hatte, also las ich diesmal das Papier und versuchte, eine einfache Bildverarbeitung zu implementieren. (Es sieht aus wie auf dem Bild unten.)

src	dst

Das Papier, das ich dieses Mal gelesen habe, ist relativ alt (2004) und die Implementierung selbst schien nicht so schwierig zu sein, also habe ich es versucht. (Es ist jedoch nicht so gut wie das in der Zeitung veröffentlichte Ergebnis ...)

Der Quellcode für diese Zeit wird auf github veröffentlicht. https://github.com/aratakokubun/GraphBasedSegmentationWithUnionFind.git

Übersicht über die Bildverarbeitung

Dieses Mal haben wir den Bildbereichsteilungsprozess implementiert, bei dem es sich um die Helligkeit handelt. Als Bedingung für das Kombinieren werden die Grenzen (Kante) mit benachbarten Pixeln in aufsteigender Reihenfolge beurteilt und die Bereiche nacheinander kombiniert.

Algorithmus

Führen Sie die folgenden Schritte 1 bis 5 aus, um eine Liste unabhängiger Komponenten zu erhalten. Diese Komponente ist der Bereich, in dem die Pixel kombiniert werden.

Extrahieren Sie alle 8 Kanten jedes Pixels oder jeder Kanten innerhalb eines bestimmten Abstands (nächster Nachbar). Im Ausgangszustand werden nicht alle Pixel kombiniert, und jedes Element wird als Komponente behandelt.
Berechnen Sie für jedes Pixel den Wert, der als Grundlage für die Kopplung verwendet wird.
In diesem Fall wird beispielsweise der Helligkeitswert (Luminanz) verwendet, und Pixel mit ähnlicher Helligkeit werden als der gleiche Bereich kombiniert.
Messen Sie die Differenz (Diff) jeder extrahierten Kante und sortieren Sie sie in aufsteigender Reihenfolge des Diff-Werts.
Wiederholen Sie Schritt 5 in aufsteigender Reihenfolge der Kante
Wenn der Wert von Edge kleiner als die interne Differenz (MInt) der Komponenten auf beiden Seiten der Grenze ist, kombinieren Sie die beiden Komponenten zu einer Komponente.

Dieser Schritt wird in den Edge-Verbindungsbedingungen ausführlich beschrieben.

Randverbindungsbedingung

In Bezug auf die Kombination in Schritt 5 werden der Differenzunterschied von Edge und der interne Differenz Mint von zwei Komponenten C1 und C2 unter den folgenden Bedingungen kombiniert.

diff <= MInt(C1, C2)

Die interne Differenz Mint zweier Komponenten ist wie folgt definiert.

MInt(C1, C2) = min(Int(C1)+τ(C1), Int(C2)+τ(C2))

Die interne Differenz Int jeder Komponente nimmt den Maximalwert der Grenzen an, die jemals an die Komponente gebunden wurden. Wenn Component ein 1-Pixel-Element ist, ist es 0. (Diese Beschreibung ist jedoch nicht streng korrekt. Wenn Sie mehr wissen möchten, lesen Sie bitte Referenz 1.)

Zusätzlich ist τ eine Randwertfunktion gemäß der Größe der Komponente und ist wie folgt definiert.

τ(C) = k/|C|

k ist ein konstanter Parameter, und je größer k ist, desto einfacher ist es für Edge, sich zu verbinden, und desto größer ist die resultierende Komponente.

Techniken zur Beschleunigung

Ein Algorithmus namens Union-Find wird verwendet, um den Prozess zu beschleunigen.
Union-Find berücksichtigt Teilmengen von S, die sich für die Menge S gegenseitig ausschließen. Beim diesmaligen Teilen des Bildbereichs entspricht die Menge S dem Bild, das die Menge der Pixel ist, und die Teilmenge entspricht der Komponente. Dies wird als disjunkte Menge bezeichnet, und die Vereinigungs- und Suchoperationen sind wie folgt definiert.

union(C1, C2) Die Teilmengen C1 und C2 werden zu C1 zusammengeführt. (Dies entspricht dem Vorgang in Schritt 5 des Verbindens von Komponenten.)
find(a) Ruft die Teilmenge ab, zu der ein Element a (Pixel) gehört.

Zum Zeitpunkt dieser Vereinigungsverarbeitung wird das repräsentative Element jeder Komponente einzeln definiert, und die Verknüpfung wird von jedem Element der kombinierten Seite (C2) zum repräsentativen Element der Verbindungsseite (C1) hergestellt. Dies macht es einfach, die Verarbeitung mit einem einzelnen Array zu implementieren.
Darüber hinaus ist eine weitere Beschleunigung mithilfe von Uion-Find by Tree möglich.

Die Implementierungsmethode wird hier nicht im Detail beschrieben. Eine ausführliche Erläuterung von Union-Find finden Sie in Referenz 2. Darüber hinaus wird in Referenz 3 auch der Rechenaufwand erläutert. Bitte beziehen Sie sich auch darauf.

Ergebnis

Das diesmal in Python implementierte Ergebnis ist wie folgt. Die Top 40 mit der größten Flächengröße sind anstelle aller Flächen farbig.

src	dst

Der Quellcode für diese Zeit wird auf github veröffentlicht. https://github.com/aratakokubun/GraphBasedSegmentationWithUnionFind.git

Verweise

Efficient Graph-Based Image Segmentation
http://cs.brown.edu/~pff/papers/seg-ijcv.pdf
Implementierung von Union Find
http://www.geocities.jp/m_hiroi/light/pyalgo61.html
Disjoint-Set Data Structures
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec16.pdf