Polygon aus Kantenbild extrahieren

[Nikolas]

Hallo

Ich schreibe gerade an einer kleinen Objekterkennungssoftware die auf Fourierdeskriptoren basiert und habe ein kleines Problem.

Nachdem ich in meinem Bild die Kanten gefunden habe, habe ich rote Konturlinie auf schwarzem Grund, die ich jetzt als Polynom darstellen will. Leider fehlt mir da ein schöner Ansatz.

Wenn ich jedes gefärbte Pixel als Ecke benutze, kann ich sie in keine Sinnvolle Reihenfolge bringen und wie ich Pixel auslassen soll, weiss ich auch nicht.
Vielleicht ist ja einer von euch schon über einen passenden Algorithmus gestolpert.

Nikolas

[taaktaak]

Ähhh, du sprichst von Konturlinien auf schwarzem Grund. OK. Aber wieso soll dann jedes gefärbte Pixel eine Ecke sein? Eine Ecke ist dort, wo sich die Steigung der Linie ändert - oder?

// edit: Vorausgesetzt, dass Linie = Gerade

[Nikolas]

Mit Konturlinie meine ich nur eine geschlossene Linie. Also einmal Stift aufgesetzt, ohne Überkreuzungen gemalt und wieder zum Ausgangspunkt.

[Medium]

Zunächst einmal müsstest du die Nachbarschaft klären. Es werden hierbei 8er und 4er Nachbarschaften unterschieden, und auf eine davon sollte man die Konturlinien normieren (edit: 4er sind üblich). Anschließend ist es üblich eine Punktliste zu erzeugen, in dem man zunächst linear im Bild einen ersten Pixel sucht, der noch nicht zugeordnet ist, und entsprechend seiner Nachbarschaft um ihn herum nach weiteren sucht. Alle gefundenen Pixel werden in der Finde-Reihenfolge in eine Liste gespeichert, und so markiert, dass sie kein zweites Mal gefunden werden (z.B. schwarz überzeichnen). Findet man um einen Pixel keinen weiteren mehr, ist die Kontur vollständig, und das ganze beginnt von vorne.
Sobald jeder Konturpixel in einer Liste gelandet ist, hast du sämtliche Konturen als geordnete Pixellisten vorliegen. Die einzige Unschönheit ist: Man kann nicht sagen, wie die Listen orientiert sind, bovor sie nicht vollständig sind. Möchtest du also alle Listen z.B. im Uhrzeigersinn haben, musst du hinterher alle überprüfen und ggf. umsortieren.
Edit: Auch ist undefiniert welcher Pixel am Anfang/Ende der Liste Steht. Hier könnte man auch durch nachgelagerte Verarbeitung beikommen.

[Nikolas]

Wie meinst du das mit der 4er Nachbarschaft?

so:

Delphi-Quellcode:

foo(x,y):
if (pixel(x,y)==rot) then
schreibe (x,y) in die Liste und mache foo (x-1,y), foo (x+1,y),foo(x,y+1), foo(x,y-1)

Meine extrahierte Konturlinie ist grob 3-4Pixel breit. Mit obiger Methode hätte ich ja alle Pixel in der Liste, oder wird da noch eine Auswahl getroffen?

[Medium]

Zitat:

Zitat von Nikolas

Wie meinst du das mit der 4er Nachbarschaft?

so:

Jap. Bei der 8er kommen die diagonalen hinzu. Aber das interessiert dich noch nicht, weil:

Zitat:

Meine extrahierte Konturlinie ist grob 3-4Pixel breit.

D.h. du brauchst noch einen Verarbeitungsschritt davor, da die Linie auf 1px Breite geracht werden muss, da sonst die Nachbarschaften ja auch keinen Sinn machen. 4er Nachbarschaft heisst, dass ein Pixel der Kontur in seinen 4 Nachbarn (oben, unten, links, rechts) maximal 2 weitere Pixel haben darf: Einen Vorgänger und einen Nachfolger. Diese Bedingung ist logischerweise nicht mit >1px breiten Konturen erfüllbar. Du musst, wie man es so schön nennt, vor her skelettieren. Dieses PDF beschreibt einen möglichen Algo dazu. Bevor das nicht geschehen ist, kannst du mit deinen Konturen nichts machen, da sie eigentlich gar keine sind.

[Nikolas]

Das klingt sehr gut. Wenn ich nur noch eine Linie (1px) habe, kann ich auch deutlich einfacher Pixel entfernen, die nichts zur Kontur beitragen. Alternativ kann ich sie auch einfach drinlassen, der Berechnungsaufwand ist linear und recht klein,
und sobald ich bei den Fourierkoeffizienten die höheren Terme weglasse, habe ich auch so eine Glättung im kleinen Bereich.
Hast du da irgendwo eine Implementierung rumliegen? (Sprache egal, da ich eigentlich in Java schreibe?) Beim einfachen Skelletieren mit den 3x3Matrizen weiss ich nicht genau, was mit den 9 Vergleichsmasken gemeint ist. Bei der Durchlaufrichtung steht "oben links nach unten links"... Was soll ich mir darunter vorstellen?

Vielen Dank :mrgreen:

[Medium]

Ich würde das Verfahren nach Zhang und Suen eher empfehlen, als die 9-Matrizen Variante. (Das ist in o.g. auch beschrieben.) Klingt zwar zunächst etwas aufwendig, aber wenn man sich dazu einmal die Basisoperationen gebastelt hat gehts.

Um einzelne "Fransen" und lose Pixel loszuwerden, kann man ein sog. Opening durchführen, welches sich wiederum aus den Schritten Erosion und Dilatation zusammensetzt. Das hier enthält eine der besser verständlichen Beschreibungen des ganzen (ziemlich am Ende). Der Kram ist an sich total Simpel, nur irgendwie recht kompliziert zu erklären...
Opening kann nur dazu führen, dass ab und an mal eine eigentlich geschlossene Kontur unterbrochen wird, je nach Bild und gewähltem Strukturelement. Das müsste man dann in Kauf nehmen.

[Nikolas]

Für Zhang/Suen habe ich ich mich jetzt auch entschieden.
Die Implementation ist ja eher einfach, und bringt schöne Ergebnisse.

Vielen Dank für deine Hilfe, dass hat mich doch ordentlich weitergebracht.

Leider ist der Code in Java, sonst hätte ich ihn in die CodeLib gestellt.

Vielleicht hat ja einer der Leute, die nie wissen, was sie schreiben sollen, Lust ihn umzuschreiben und etwas zu beschleunigen.

Eine Anleitung und Code gibt's hier.

Meine JavaAnpassung mit ein paar Hilfsfunktionen für rgb-Bilder sind im Anhang.

[Nikolas]

So, da bin ich wieder. Ich schaffe es leider nicht, aus der Pixellinie jetzt ein Polygon zu machen :wall:
Mein Ansatz sieht so aus, dass ich mit einem Pixel starte, alle Objektpixel in der 8er Nachbarschaft auf einen Stack schreibe, dann das oberste Objekt vom Stack nehme, denn Nachbarn draufschreibe usw. Alle gepopten Elemente schreibe ich dann in eine Liste

Damit erreiche ich zwar alle Punkte, nur leider stimmt die Reihenfolge nicht so ganz. Ich kann leider nicht ganz naiv die Pixel entlang gehen, da ich bei manchen Kanten noch kleine Kreuzungen habe, an denen ein paar Pixel der Kontur falsch abbiegen.

Hast da jemand eine Idee?

[Medium]

Mhh, generell ist da eine 4er Nachbarschaft deutlich besser geeignet, wenn nicht sogar nötig (ich erinner mich grad nicht). Man konnte auch irgendwie 8er in 4er überführen und umgekehrt, aber auch da hab ich gerade eine Sperre in den Synapsen :?. Es war zumindest nicht schwer!

Das Problem bei 8er ist ja:

Code:

Starte bei X, suche links herum, beginnend mit dem oberen möglichen Nachbarn:

0    | 1    | 2    | 3    | 4 
-----+------+------+------+------
   X |    - |    - |    - |    -
   O |    X |    - |    - |    -
OOOO | OOOO | OOXO | OO-X | OO--

-> Tracing Ende, Kontur unvollständig, da "falsch abgebogen"

Sowas kann dir bei 4er NBs nicht passieren.


Kreuzungen kannst du übrigens nicht überwinden, ohne wirklich aufwendig zu werden. Eine Kreuzung wird immer als Ecke erkannt werden, es sei denn, du prüfst zusätzlich die 2px Nachbarschaft mit ab, und schaffst Kriterien für Kreuzungen. Dabei musst du noch drauf achten, dass Pixel in denen sich was kreuzt mehr als nur ein Mal zugeordnet werden müssen, wenn die "andere" kreuzende Kontur nicht unterbrochen werden soll. Das stell ich mir arg fummelig vor!

[Nikolas]

Ich habe jetzt eine recht elegante Möglichkeit gefunden:

Man nehme einen Stack!
Auf den legt man ein Pixel aus dem Polygon und

-> nimm das oberste Objekt vom Stack und schaue ob du nahe am Ziel bist. (und dein Polygon schon mehr als 10 Punkte beinhaltet. )
Wenn ja, bist du fertig
ansonsten lege alle (8er) Nachbarn drauf, die auch zur Kontur gehören und noch nicht gesehen wurden.
goto (->)

Mein Problem bestand aus kleinen Anhängseln, die nur ein paar Pixel lang waren. Komme ich jetzt an eine Kreuzung, gehe ich einen Weg. Ist es die kurze Sackgasse, finde ich bald keine Nachbarn mehr und gehe zurück zum richtigen Weg. Damit habe ich dann einen kleinen Schlenker im Polygon, aber da nachher alles durch Fourier geglättet wird, kann mir das egal sein.
Gehe ich den richtigen Weg, wird mich der irgenwann ans Ziel führen, an dem ich dann meinen Stack verwerfe und so den falschen Weg nicht in meinem Polygon habe.

lineare Laufzeit, recht stabil und ziemlich einfach :)

Damit ist ein Problem gelöst, das nächste kommt sofort
Durchlaufrichtung eines Polygons bestimmen

[bernhard_LA]

ps : hier gib es einen algo zu diesem problem
http://cardhouse.com/computer/vector.htm