Hough-Transformation PDF

Preview

Summary

Hough-Transformation....

Description

Bildverarbeitung - Hough-Transformation! I.

-

-

I.

Einführung und Motivation man möchte Bilder verstehen für Anwendungen! Primitive finden (z.B.: Geraden, Kreise, Parabeln, …)! alles erkennen, was parametisch beschrieben werden kann! Hough-Transformation = Algorithmus, sehr robust! gesucht werden die Formen im Kantenbild:! 1. Richtung der höchsten Grauwertveränderung = Vektor ! 2. Den Betrag des Vektors ermitteln! 3. Betrag wird im Kantenbild dargestellt! 4. Binarisierung des Kantenbildes:! • beliebiger Schwellenwert wird bestimmt! • alles, was kleiner als der Schwellenwert ist = 0 (schwarz)! • alles, was größer als der Schwellenwert ist = 1 (weiß)! Algorithmus berechnet, welche Punkte ergeben eine Gerade! Ordnet Bildinhalten Beudeutung zu!

Anwendungen

- Straßen- und Bahnbegrenzungen erkennen für autonom fahrende Industrieroboter oder Autos! - Anaylse von Sportvideos wie Fußball- und Tennisspielen zum automatischen Indexieren und Zusammenfassen des Spielverlaufs!

- Starten und Landen von Flugzeugen! - Bildverarbeitung in der Produktion! I.

Hough-Transformation!

Dualraum:! - Hough-Transformation erzeugt einen Dualraum! - Links: gewöhnlicher Ortraum! - Rechts: Parameterraum als Akkumulator! - beide Räume sind diskret! Akkumulator:! - speichert Variablen! - jeder Pixel, der im Kantenbild gesetzt wird, ist mit einer Variable im Akkumulator verbunden! - speichert Grauwerte, die zunächst auf 0 gesetzt sind! - Variablen lassen sich inkrementieren (+1)! Achsen:! - Ortraum:! • interpretiert wird eine Koordinate (x, y) wie gewohnt (Euklidisches Koordinatensystem)! - Parameterraum:! • m-Achse = Steigung m einer Geraden !

-

• desto weiter nach rechts, desto steiler ist die Gerade ! • b-Achse = Höhe b (y-Achsenabschnitt)! ein Punkt im Parameterraum = Gerade im Ortraum!

Geradendarstellung:! - y-Achsenabschnitt verschiebt die Gerade nach oben und unten! - b-Achse (Parameterraum) = y-Achse (Ortsraum)! - Geradendarstellung im Parameterform:! y = mx + b - Steigung m durch Steigungsdreieck:! Quotient aus der Höhe durch Breite! • ! Nachteil:! - Geraden zwischen 0-45° besitzen Steigungen zwischen ≥ 0 und ≤ 1! - Für Geraden nahe 90° geht die Steigung gegen unendlich! - m im Parameterraum steigt jedoch nur linear und ganzzahlig! - gesucht wird eine numerisch robustere Geradengleichung ! Verbesserte Geradengleichung:! - Steigung m über Quotient ! - über Einheitskreis:!

-

I.

∆y kann durch den Sinus berechnet werden! ∆x kann durch den Cosinus berechnet werden! eingesetzt in die Geradengleichung ergibt sich:! unterste Gleichung eignet sich zum Test! • Ist der Punkt (x, y) gegeben, kann durch einsetzen geprüft werden, ob der Punkt auf der Geraden liegt! • ergeben alle 4 Variablen eingesetzt 0=0, so ist die Annahme richtig! Die Transformation!

Wie transfomiert man einen Punkt P vom Ortsraum in den Parameterraum? (Bedenke: ein Punkt ist keine Gerade)! - es wird keine Gerade ausgeschlossen! - jede mögliche Gerade wird im Parameterraum abgetragen ( =Geradenschar)! - für jede mögliche Gerade wird der Winkel und der y-Achsenabschnitt berechnet! es entsteht eine geschwungene Kurve im Parameterraum! - unterschiedliche Punkte erzeugen unterschiedliche Kurven! - Häufungen der einzelnen Geraden im Parameterraum = wo eine Linie sein könnte! - durch die Streuung der Geraden erhält man keinen Schnittpunkt, sondern ein Cluster! - Mittelpunkt des Clusters = Schnittpunkt H! I.

Andere Primitiven!

- es lässt sich alles finden, was sich als Parametergleichung darstellen lässt!

- für jeden Parameter der gesuchten Primitive gibt es eine Achse im Parameterraum!

- mit jedem zusätzlichen Parameter steigt der Speicherbedarf ! - Dimensionen richten sich nach dem Paramtern der Gleichung ! Beispiel - Kreis:! ∆x = (x - mx)2! r 2 = (x − m x)2 + (y − my)2 ∆y = (y - my)2! - Kantenpixel (x, y) liegen auf Kreismantel! - nach Bruce-Force werden alle möglichen Parameter im Parameterraum iteriert! - 3 Variablen (my, mx, r) = 3D Parameterraum! Verbesserte Darstellung:!

0 = ysin (α) + cos (α) − r I.

R-Tabelle für beliebige Formen!

- R-Tabelle erlaubt es beliebige Formen zu finden! - nicht skalierungs- oder rotationsinvariant! Erzeugen einer R-Tabelle:! 1. Beliebigen Referenzpunkt (cx, cy) suchen (vorzugsweise im Objekt)! 2. Sample die Kontur des Objekts in Schritten gleicher Länge ab! Für jeden Punkt P:! 3. Wird das Lot auf die Tangente in P betrachtet! 4. Winkel α zur Tangente (x-Achse) = 1. Spalte! 5. Winkel β zwischen Linie von Refenrenzpunkt zu P und der Tangente (x-Achse) = 2. Spalte! 6. Distanz zwischen P und Refenzpunkt = 3. Spalte! Winkel α

Winkel β

Distanz d

80°! …

160°! …

50! …

Lot berechen:! - Tangente liegt oberflächlich auf Punkt P! - Lot liegt senkrecht auf der Tangente (zeigt weg vom Objekt

- sind alle Punkte abgetragen, ist die Form in der RTabelle codiert !

- soll die Form nun im realien Bild wieder gefunden werden, werden all Pixel P des Bildes iteriert und an jeder Stelle wird der Gradient g berechnet ! Beachte: ! Benutzung der R-Tabelle:! g ist ein Vektor. g erfüllt hier die gleiche Aufgabe, die 1. Berechne an jedem Bildpunkt P den bei der Erstellung der R-Tabelle das Lot auf die Gradienten g. Ist der Betrag |g| aureichend Tangente an die Kurve erfüllt hat. Vekoren der Länge groß, dann…! Null interessieren nicht. Auch kleine Vektoren 2. Berechne den Winkel α zur x-Achse! stammen eher von Kamerarauschen und können 3. Suche die optimal passende Zeile der Rnicht sinnvoll interpretiert werden. Tabelle! 4. Trage den Winkel β der 2. Spalte im Punkt P ab und erzeuge eine Gerade! 5. Folge der Geraden d Längeneinheiten und schwärze den Akkumulator an der entsprechenden Stelle! - Entsteht im Parameterraum ein entsprechender Häufungspunkt, so ist die in der R-Tabelle codierte Form gefunden !...