3. Bildverarbeitung, Konturverfolgung und Pi=4

Bildverarbeitung, Konturverfolgung und Pi=4

  • ?

    Hallo,

    angenommen ich habe ein Bild mit einigen Filtern und abschließendem Binarisierungsverfahren auf ein Binärbild runtergerechnet. Nun berechne ich einige Merkmale der einzelnen Blobs (schwarze Objekte vor weißen Hintergrund). Zum Beispiel Momente, Trägheitsachsen, Orientierung oder ganz einfach die Fläche (Pixelanzahl).

    Nun wollte ich auch die "Circularity" berechnen, die definiert ist als: Circularity = Umfang² / Fläche
    Ein Kreis hätte eine Circularity von 4*Pi ~ 12.6 wie man einfach nachrechnen kann. Es fehlt also der Umfang eines Blobs um diese Größe berechnen zu können.
    Dazu habe ich im ersten Schritt den Turtle-Algorithmus implementiert um alle Randpixel zu erfassen. Der ist relativ einfach zu verstehen. Ausgehend von einem Startpunkt wiederholt man folgendes, bis man nach einem vollständigen Umlauf des Blobs wieder beim Startpunkt angekommen ist:

    Die Turtle wandert am Rand entlang. Bei einem Pixel der NICHT zum Blob gehört dreht sie sich nach links, bei einem Pixel der DOCH zum Blob gehört dreht sie sich nach rechts. So wandert die gedankliche Schildkröte den Rand des Blobs entlang und man kann alle Randpixel erfassen.
    Aus den jeweils letzten beiden und verschiedenen Randpixeln ergibt sich ein Richtungsvektor (der als Konturcode gespeichert werden kann). Der kann nur aus der Menge { (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1) } sein. Die Randpixel liegen nämlich immer in direkter 8-Nachbarschaft zueinander.
    Hat man Alle erfasst, kann man den Umfang einfach berechnen. Sei G die Anzahl der horizontalen oder vertikalen und U die Anzahl der Diagonalen Vektoren (Konturcodes), dann ist der Umfang = G + Sqrt(2)*U

    Alles, nach etlichen Tests, korrekt implementiert und gut zu verstehen. Für ein Quadrat ergibt sich eine Circularity von 16. Stimmt mit der Theorie überein.
    Problem: Die Circularity ergibt für beliebige Kreise immer einen Wert um 17 oder 18 statt 4*Pi.
    Das ist somit völlig unbrauchbar als Feature zur Klassifizierung von kreisähnlichen Objekten.

    Nach ein wenig nachdenken ist mir glaube ich auch klar geworden woran es liegt. Man kann einen Kreis auf Pixelebene so approximieren, dass sich PI = 4 ergibt. (Siehe Bild: http://blog.bfg9000.co.uk/wp-content/uploads/2010/11/pi_equals_4.png)
    Und genau das scheint bei der Konturverfolgung mit dem Turtle zu passieren. Obwohl durchaus diagonale Schritte erfasst werden!
    Wenn ich den Umfang und die Fläche in eine Gleichung packe und nach Pi auflöse kriege ich auch einen Wert um die 4 für Pi.

    Es liegt also wahrscheinlich an der Konturverfolgung des Turtlealgorithmus. Mir fällt aber keine bessere Lösung ein.

    Weißt jemand Rat, wie man Konturen besser erfasst? Also aus mathematischer Sicht? Oder habe ich sonst wo einen Denkfehler?

    Gruß, µ

    EDIT: Gehört sowas in Grafikforum? Vielleicht sollte Bildverarbeitung dort in der Forenbeschreibung aufgenommen werden 🙂

    0
  • G

    Ich wuerde folgendes probieren...

    Momentan beschreibst Du den Rand Deines Objekts mit Geraden. Ueber diese Beschreibung musst Du hinausgehen. Du musst Kurven zulassen. Nimm nicht immer 2 Punkte, die Du verbindest, sondern 4 benachbarte Punkte und lege da ein Polynom 3. Grades durch (fuer x- und y-Koordinaten separat). Die Laenge der daraus entstehenden Kurve zwischen dem 2. und 3. Punkt nimmst Du dann fuer den Abstand der beiden Punkte entlang des Randes.

    0
  • Mod

    So weit würde ich gar nicht gehen, Diagonalen sollten schon reichen um einem brauchbaren Ergebnis näherzukommen und sind nicht kompliziert einzubauen. Denk da dran, dass die Diagonale eines Pixels sqrt(2)*Pixelkantenlänge lang ist.

    0
  • V

    Oder besser zuerst alle Umfangspunkte sammeln und danach 36 im Array gleich weit entfernte ziehen. Das sollte einen Kreis deutlich kreisig sein lassen.

    0
  • G

    SeppJ schrieb:

    So weit würde ich gar nicht gehen, Diagonalen sollten schon reichen um einem brauchbaren Ergebnis näherzukommen und sind nicht kompliziert einzubauen. Denk da dran, dass die Diagonale eines Pixels sqrt(2)*Pixelkantenlänge lang ist.

    Hat er glaube ich schon, wenn ich das da richtig interpretiere...

    µ schrieb:

    Hat man Alle erfasst, kann man den Umfang einfach berechnen. Sei G die Anzahl der horizontalen oder vertikalen und U die Anzahl der Diagonalen Vektoren (Konturcodes), dann ist der Umfang U = G + Sqrt(2)*U

    0
  • G

    Ich habe nochmal über die Problematik nachgedacht. Vermutlich wird das Polynom auch nichts bringen. Probier's mit Fourierdeskriptoren. Das heißt, im Prinzip machst Du eine Fourierentwicklung des Randes und ab einer bestimmten Frequenz brichst Du ab. ...und dann nimmst Du die Länge der damit beschriebenen Kurve.

    EDIT: Die falschen Ergebnisse werden nicht mit wachsendem Kreisradius besser? Eigentlich würde ich das erwarten.

    0
  • V

    Gregor schrieb:

    SeppJ schrieb:

    sqrt(2)*Pixelkantenlänge lang ist.

    Hat er glaube ich schon, wenn ich das da richtig interpretiere...

    Nein. Die Punkte sind doch so:

    abcd
  789
 56
34
2
1

    Die Kröte kennt nur vier Richtungen.

    U=8r
    A=4    r^2
    PI=sqrt(U2/A=64r2/4r^2)=4
    Daher PI==4 vom Quadratkreis.

    Mit Diagonalen kommt Ihr aber wohl auch nocht auf was besseres als PI=3,64 vom Achteckkreis. Da würden Parabeln, Splines oder Kreisbögen auch nicht viel retten, denn sie verfolgen auch nur die Pixeltreppen.

    edit: Falsch, er schreibt von "8-Nachbarschaft", seltsam, daß PI dann 4 ergibt.

    0
  • V

    Gregor schrieb:

    EDIT: Die falschen Ergebnisse werden nicht mit wachsendem Kreisradius besser? Eigentlich würde ich das erwarten.

    Hast Du das PI==4-Bildchen aus dem Eröffnungsposting beachtet?
    Es geht dabei darum, daß man weitergeht und einen Grenzwertübergang macht mit unendlich vielen unendlich kleinen treppenstufen, also den Kreis sogar genau trifft, und doch ist dann PI==4.

    0
  • G

    volkard schrieb:

    edit: Falsch, er schreibt von "8-Nachbarschaft", seltsam, daß PI dann 4 ergibt.

    Vielleicht einfach ein Bug, bei dem er nur "G"s kriegt und keine "U"s. 🙂

    EDIT: @Threadersteller: Dreh mal die Quadrate um 45° und sag, was Du dann kriegst. 🙂

    0
  • G

    volkard schrieb:

    Gregor schrieb:

    EDIT: Die falschen Ergebnisse werden nicht mit wachsendem Kreisradius besser? Eigentlich würde ich das erwarten.

    Hast Du das PI==4-Bildchen aus dem Eröffnungsposting beachtet?
    Es geht dabei darum, daß man weitergeht und einen Grenzwertübergang macht mit unendlich vielen unendlich kleinen treppenstufen, also den Kreis sogar genau trifft, und doch ist dann PI==4.

    Ok, mir ist jetzt klar, warum es nicht besser wird. Im Prinzip erwarten wir den Umfang eines gleichseitigen Achtecks, obwohl er den Umfang eines Kreises haben will. Das ist dann natürlich unabhängig von der Größe.

    Dann gefällt mir aber die Idee mit den Fourierdeskriptoren ganz gut. Das ist allerdings ein vermutlich schwieriges Abwägen bezüglich der Frequenzen, die man mitnimmt. Für einen Kreis benötigt man nur ganz niedrige Frequenzen. Wenn das Objekt hingegen irgendwelche "echten" Ecken hat, dann benötigt man auch hohe Frequenzen. Zu hohe Frequenzen führen aber wieder dazu, dass man nur an den Pixeln entlanggeht.

    0
  • R

    µ schrieb:

    Weißt jemand Rat, wie man Konturen besser erfasst? Also aus mathematischer Sicht? Oder habe ich sonst wo einen Denkfehler?

    bei der 3d version ist es ueblich erstmal so wie du das machst um die objekte zu wandern, dabei speichert man sich das mesh (in deinem fall einen linienzug).
    anschliessend "zieht" man das mesh glatt.
    http://www.cs.wm.edu/~nikos/cs420/projects/ModifiedSurfaceNets.pdf
    damit solltest du ziemlich genau auf PI kommen bei dem umfang.

    du kannst anschliessend den linienzug auch triangulieren und so eine besser passende flaeche errechnen.

    0
  • ?

    Gregor schrieb:

    EDIT: Die falschen Ergebnisse werden nicht mit wachsendem Kreisradius besser? Eigentlich würde ich das erwarten.

    Nein. Die Ergebnisse bleiben mit erstaunlicher Genauigkeit falsch (was für ein Satz). Egal wie groß die Kreise sind, die Circularity ist immer Nahe bei 17 oder 18.

    volkard schrieb:

    Die Kröte kennt nur vier Richtungen.
    [...]
    edit: Falsch, er schreibt von "8-Nachbarschaft", seltsam, daß PI dann 4 ergibt.

    Die Kröte kennt nur 4 Richtungen. Aber es werden stets die beiden letzten besuchten Randpunkte des Blobs verwendet, um den Richtungsvektor/Konturcode zu berechnen. Und die liegen durchaus häufig diagonal zueinander.

    Gregor schrieb:

    Vielleicht einfach ein Bug, bei dem er nur "G"s kriegt und keine "U"s. 🙂

    Ich habe den Algorithmus für einen kleinen Kreis von Hand nachgerechnet. Er arbeitet korrekt und liefert auch Us.

    Gregor schrieb:

    EDIT: @Threadersteller: Dreh mal die Quadrate um 45° und sag, was Du dann kriegst. 🙂

    Gute Idee. Ich werde es später testen.

    Das Verfahren ist in der Literatur verbreitet und nirgends ist die Rede von Fourierdeskriptoren, nur um den Umfang möglichst genau zu berechnen. Das erstaunt mich ein wenig.

    0
  • ?

    Gregor schrieb:

    EDIT: @Threadersteller: Dreh mal die Quadrate um 45° und sag, was Du dann kriegst. 🙂

    Quadrat mit Kantenlänge 500 Pixel => Umfang 2000, Circularity 16.

    Gedreht in 10° Schritten:

    winkel 0
    Umfang 1996
    Circularity 16

    winkel 10
    Umfang 2205,3868683519
    Circularity 19,5403553901618

    winkel 20
    Umfang 2359,66103833159
    Circularity 22,3746557840176

    winkel 30
    Umfang 2436,27835406179
    Circularity 23,8441479569111

    winkel 40
    Umfang 2435,92510704351
    Circularity 23,8371381569166

    winkel 50
    Umfang 2437,09667991876
    Circularity 23,8601687533737

    winkel 60
    Umfang 2436,27835406179
    Circularity 23,8441479569111

    winkel 70
    Umfang 2359,66103833159
    Circularity 22,3746557840176

    winkel 80
    Umfang 2205,3868683519
    Circularity 19,5403553901618

    winkel 90
    Umfang 1996
    Circularity 16

    Verdammt nochmal das ganze Verfahren ist in der Form völlig unbrauchbar 😞

    0
  • V

    Kannste mal meinen Vorschlag probieren, nur voll wenige Punkte des Umfangs zu nehmen? Sagen wir mal nur jeden zweiundvierzigsten Punkt?

    0
  • J

    Was du gerade erlebst ist genau der unterschied zwischen punktweiser und gleichmäßiger konvergenz. dein approximierter rand koonvergiert zwar punktweise gegen den kreis, aber nicht gleichmäßig, und daher konvergiert der umfang auch nicht gegen den echten umfang. Mit bel. Liniensegmenten oder auch irgendwelchen polynomen ist es aber möglich den kreis gleichmäßig zu approximieren.

    Die Idee von volkard ist doch schonmal nicht schlecht. Evtl. solltest Du die Svhrittweite noch an die lokale Krümmung anpassen.

    0
  • ?

    Aaaah ich habs. Jeder n-te Punkt tut es. Genau das was Volkard gleichzeitig geschrieben und auch schon früher vorgeschlagen hat. Hier Ergebnisse für jeden 5. Punkt.

    Quadrate. Ideal: Umfang = 2000, Circularity = 16.

    winkel 0
    Umfang 1993,15298244508
    Circularity 15,9543889840994

    winkel 10
    Umfang 2010,20652727901
    Circularity 16,2346992343129

    winkel 20
    Umfang 2005,96277396668
    Circularity 16,1697333387185

    winkel 30
    Umfang 2022,02948951365
    Circularity 16,4249087341382

    winkel 40
    Umfang 2011,21630039606
    Circularity 16,2497077736798

    winkel 50
    Umfang 2007,07071474906
    Circularity 16,1827229319455

    winkel 60
    Umfang 2021,28393479123
    Circularity 16,4127987122534

    winkel 70
    Umfang 2003,07377341062
    Circularity 16,1231913689024

    winkel 80
    Umfang 2009,7026554746
    Circularity 16,2265615809184

    winkel 90
    Umfang 1993,15298244508
    Circularity 15,9543889840994

    Und Kreise verschiedener Größe.
    Ideal: Circularity = 4*Pi = 12,566

    pixelCount 1227
    Umfang 119,75738698811
    Circularity 12,3743155636065

    pixelCount 7511
    Umfang 304,845325521225
    Circularity 12,6539586726772

    pixelCount 17805
    Umfang 470,681095304744
    Circularity 12,6295181984023

    pixelCount 73931
    Umfang 968,24975141415
    Circularity 12,7721478302996

    pixelCount 118713
    Umfang 1225,25084538832
    Circularity 12,7157425081403

    Mit der Genauigkeit kann ich leben. 👍
    Geschwindigkeit ist auch relevant deswegen verzichte ich vorerst auf Polynome höheren Grades. Aber aus Interesse an der Genauigkeit werde ich es vielleicht mal testweise implementieren.

    0
  • ?

    Jester schrieb:

    Was du gerade erlebst ist genau der unterschied zwischen punktweiser und gleichmäßiger konvergenz.

    Interessante theoretische Erklärung 👍

    0
  • V

    Ok, bitte noch einen Testlauf mit 42 oder 41 statt 5.

    0
  • ?

    42 ist zu viel.
    Schon 15 hat keine so guten Ergebnisse mehr wie 5 gebracht.
    Das Optimum für diese Testdaten scheint zwischen 4 und 10 zu liegen. Das Optimum für meine Realdaten (Kamerabilder) werde ich mit einem geeigneten Satz an Testbildern iterativ bestimmen.

    Aber Du hattest das richtige Gespür für die Lösung 👍

    Quadrate (Umfang = 2000, Circularity = 16), Schrittweite 42

    winkel 0
    Umfang 1949,74930905663
    Circularity 15,2670967914458

    winkel 10
    Umfang 1948,68119450545
    Circularity 15,2561334065302

    winkel 20
    Umfang 1936,29591181392
    Circularity 15,0660906563606

    winkel 30
    Umfang 1968,19103989357
    Circularity 15,5618955337

    winkel 40
    Umfang 1953,54691900362
    Circularity 15,331183699432

    winkel 50
    Umfang 1948,99651778647
    Circularity 15,2597836576993

    winkel 60
    Umfang 1966,74599756765
    Circularity 15,5390528908008

    winkel 70
    Umfang 1936,43263740907
    Circularity 15,0682184230171

    winkel 80
    Umfang 1945,63081674964
    Circularity 15,2084082612617

    winkel 90
    Umfang 1949,74930905663
    Circularity 15,2670967914458

    Kreise (Ideal: Circularity = 4*Pi = 12,566) , Schrittweite 42

    Umfang 96,0266672702513
    Circularity 7,95610079985466

    Umfang 292,796943100463
    Circularity 11,673481738695

    Umfang 442,206151455661
    Circularity 11,14763733918

    Umfang 928,077806371849
    Circularity 11,7343198757533

    Umfang 1189,60240052603
    Circularity 11,9865821740134

    0
  • G

    Hi. Kannst Du mal bei dem Quadrat, das Du schrittweise drehst folgendes machen:

    Nimm die Variante, bei der Du jeden Punkt betrachtest und gib jeweils die Anzahl der U und G aus. Die würden mich echt interessieren.

    EDIT: Wenn Du nur jeden n-ten Punkt nimmst, dann musst Du aufpassen, dass Dein n nicht zu sehr an den Testdaten orientiert ist, die vielleicht nicht sooo viel mit den tatsächlichen Daten zu tun haben. Zum Beispiel wird jeder 42-te Punkt bei sehr großen Kreisen sehr gut funktionieren, aber nicht bei kleineren Kreisen. Bei sehr kleinen Kreisen wirst Du auch mit jedem 5. Punkt Probleme kriegen.

    0
Anmelden zum Antworten