 |
 |
 |
von Kai Hübner
|
|
|
Um das Bild optimal zu segmentieren, benötigt
man mehrere Schwellwerte. Ein Verfahren zum Auffinden der optimalen Schwellwerte
zur Segmentierung eines Grauwertbildes liefert die Betrachtung des zugehörigen
Histogramms.
| Grauwertbild |  |
Histogramm H(i) |
|
|
 |
Die Minima von H(i) entsprechen den optimalen
Schwellwerten.
Hier z.B. für S1 = 95 und S2
= 125 (nicht optimal):
| 0 < I(x,y) <= 95 | 95 < I(x,y) <= 125 | 125 < I(x,y) <= 255 |
 |
 |
 |
Man erkennt die Probleme der Schwellwertbildung
in Grauwertbildern: Nur wenn man voraussetzen kann, daß sich die
Grauwerte im Bild stark voneinander unterscheiden, ist das Ergebnis zufriedenstellend.
| Ohne Farbe... | |
Mit Farbe... |  |
|
| ...ist alles nur grau | ...ist viel mehr Information vorhanden | |||
| ...können sich Objekte gleicher Helligkeit zu einem Segmentierungsobjekt verbinden | ...können sich nur Objekte gleicher Farbe zu einem Segmentierungsobjekt verbinden | |||
| ...kann man daher nur selten gut segmentieren | ...kann man daher viel besser segmentieren |
Eine Schwellwertbildung im gebräuchlichen RGB-Farbraum bringt allerdings mehrere Nachteile mit sich:
| - | Die Schwellwertbildung wird über alle Farbkanäle (R,G,B) benötigt, somit auch hoher Aufwand zum Auffinden optimaler Schwellwerte |
| - | Schatten verderben die Segmentierung |
| - | Im RGB gibt es keine Möglichkeit, farbähnliche (aber unterschiedlich helle, z.B. durch Schatteneinfall entstandene) Flächen einfach zusammenzufassen |
| - | Diese Möglichkeit bieten andere Farbräume |
| Farbton | (Hue) | Der Farbton wird durch den Farbwinkel (0° = rot, 120° = grün, 240° = blau) angegeben. |
| Sättigung | (Saturation) | Die Sättigung gibt an, wie stark der jeweilige Farbton ausgeprägt ist. |
| Helligkeit | (Value) | Gibt die Helligkeit an. Je niedriger der V-Wert (je dunkler also die Farbe), desto weniger Sättigung kann noch erreicht werden. Dadurch entsteht die typische Zylinderform des HSV-Farbraums. |
 |
 |
| Helligkeit | (Y) | Luminanzanteil, Helligkeit |
| Cyan-Rot-Balance | (U) | erster Chrominanzanteil, Farbanteil zwischen Cyan und Rot |
| Gelb-Blau-Balance | (V) | zweiter Chrominanzanteil, Farbanteil zwischen Gelb und Blau |
Den YUV-Farbwert kann man durch eine einfache
Matrizentransformation aus den RGB-Farbwerten errechnen:
| Y | = | 0.299 | 0.587 | 0.114 | * | R |
| U | -0.1687 | -0.3313 | 0.5 | G | ||
| V | 0.5 | -0.4187 | -0.0813 | B |
Der YUV-Farbraum ist also eine lineare Abbildung des RGB-Farbraums mit folgenden Eigenschaften:
| - | Die Berechnungsmatrix wurde dem menschlichen Empfinden nach aufgestellt. So ist z.B. für die Berechnung des Helligkeitswertes Y der Grünwert mit einem Faktor von 0.587 am bedeutendsten, da für das menschliche Auge ein satter Grünton heller wirkt als Rot (Faktor 0.299) oder Blau (Faktor 0.114). |
| - | Bei einem Wertebereich von [0,255] für die RGB-Werte besitzt Y einen Wertebereich von [0,255]. U und V besitzen jeweils einen Wertebereich von [-127,127]. |
| - | Sind alle RGB-Werte gleich x, ergibt sich für YUV ein Farbwert von [x,0,0]. Alle Grauwerte von Schwarz bis Weiß liegen somit exakt auf der Y-Achse. |
| - | Durch die weitaus größere Empfindlichkeit des menschlichen Auges für Helligkeitsabstufungen als für Farbabstufungen wird in der Praxis das Y-Signal wie RGB mit 8 Bit codiert, U- und V-Signal können jedoch ohne sichtbare Verluste z.B. mit nur 6 Bit codiert werden. Aufgrund dieses Vorteils findet der YUV-Farbraum in der gesamten Videoübertragungstechnik Anwendung. |
| - | Verwandt mit dem YUV ist der YIQ-Farbraum. Hierbei stehen I und Q für die Chrominanzanteile I = Cyan-Orange-Balance und Q = Magenta-Grün-Balance. |
 |
 |
 |
 |
| Y = 128 | U = 0 | V = 0 | Draufsicht |
|
||
| Y-Kanal | U-Kanal | V-Kanal |
 |
 |
 |
 |
 |
 |
Für eine Segmentierung bietet sich hier besonders der V-Kanal an, da die vorhandenen Grauwerte deutlich verschiedener sind als im Y- oder U-Kanal. Man geht also genau so wie bei der Schwellwertbildung in Grauwertbildern vor. Zuerst das Histogramm für die V-Werte erstellen:
| Grauwertbild | |
Histogramm H(i) |
|
|
 |
Und anschließend Minima des Histogramms als optimale Schwellwerte annehmen:
| 0 < V(x,y) <= 100 | 100 < V(x,y) <= 150 | 150 < V(x,y) <= 190 | 190 < V(x,y) <= 255 |
 |
 |
 |
 |
| Idee: | Vorab-Aufteilung des Farbraumes in Gebiete (Cluster), die das menschliche Auge als "konstante Farbe" erkennt. |
| Vorgehen: | |
| - | Aufteilung des HSV-Farbraumes in beliebig viele Cluster und eine achromatische Region. Die Einteilung in Cluster kann über Farbwinkel-, Sättigungs- und Helligkeitsabstufungen geschehen, die Clusterung wird nach der Anzahl dieser Abstufungen benannt (z.B. 12-5-1-Clusterung bei 12 H-, 5 S- und 1 V-Abstufung). Die achromatische Region beinhaltet alle "nichtfarbigen" Farbpunkte des Farbraumes, also alle Farbpunkte, die nahe an der Helligkeitsachse V liegen. |
| - | Für jeden Cluster wird ein Farbpunkt als Prototyp festgelegt, der alle Farbpunkte des Clusters repräsentieren soll. |
| - | Jedem Farbpunkt im HSV-Farbraum wird sein nächstgelegener Prototyp zugeordnet, indem eine Lookup-Tabelle mit Hilfe der Transformation HSV zu RGB zu YUV erstellt wird. Dadurch erfolgt die Abbildung der Cluster in den YUV-Farbraum, so daß nun für jeden YUV-Wert der zugehörige Prototyp in der Tabelle vorliegt. |
| - | Hat man die Tabelle einmal für die gewünschten Clusterabstufungen erstellt, kann man sie zur Konvertierung beliebig vieler Bilder verwenden. Dabei wird für jeden Bildpunkt der seiner Farbe entsprechende Prototyp aus der Tabelle eingesetzt. |
| 1) Y = 128 Ebene | |||
 |
 |
 |
 |
| Original | 12-1-1 Clusterung | 12-5-1 Clusterung | 12-5-1 Clusterung für gesamten YUV (Draufsicht) |
| . | |||
| 2) Hamburger-Bild | |||
 |
 |
 |
 |
| Original | 12-1-1 Clusterung | 12-5-1 Clusterung | 12-5-4 Clusterung |
| . | |||
| 2) Roboter-Bild | |||
|
 |
 |
 |
| Original | 12-1-1 Clusterung | 12-5-1 Clusterung | 4-1-1 Clusterung |
Wie man sieht hängt die günstigste Clusterung
vom zu segmentierenden Bild ab. Beim vielfarbigen Hamburger-Bild bietet
erst eine 12-5-4 Clusterung (240 Cluster) ein einigermaßen annehmbares
Ergebnis. Beim Beispiel Roboterbild hingegen, wo auch nur vier verschiedene
Farben auftreten, reicht eine 4-1-1 Clusterung (nur 4 Cluster).
| Nachteile: | |
| - | Ist die Clusterung zu fein und die Farbpunkte eines Objektes liegen auf einer Clustergrenze, so werden die verschiedenen Farbpunkte in verschiedene Cluster und somit verschiedenen Prototypfarben zugeordnet. Dies sieht man im Beispiel des Hamburger-Bildes. |
| - | Ist die Clusterung zu grob und Farbpunkte verschiedener Objekte fallen in einen Cluster, so wird allen Objektpunkten auch dieselbe Prototypfarbe zugeordnet. Beim Roboterbild reicht die 4-1-1 Clusterung nur aufgrund der Verschiedenfarbigkeit von Robotern, Ball und Hintergrund aus. |
| Idee: | Segmentierung durch Auffinden bildspezifischer "Farbrichtungen" |
| . | |
| Vorgehen: | |
| - | Analyse des Urbildes und Kennzeichnung der gefundenen Farbpunkte im YUV-Farbraum |
| - | Durch Vernachlässigung der Helligkeitskomponente Y entstehen durch Winkel festgelegte "Farbrichtungen" in der 2-dimensionalen UV-Ebene |
| - | Für jede gefundene Farbrichtung wird die UV-Ebene um den zugehörigen Winkel gedreht, so daß die Farbrichtung mit der neuen x-Achse übereinstimmt. Alle Bildpunkte mit geringem y-Wert und mittlerem bis hohem x-Wert (kleine x-Werte liegen in achromatischer Region), stellen also ein segmentiertes Objekt dar. |
|
||
| Markierung der UV-Werte der Bildpunkte in der UV-Ebene | ||
|
||
 |
||
| Rotation um 60° | Rotation um 205° | Rotation um 260° |
|
|
|
 |
 |
 |
| Nur Betrachtung aller Werte mit kleinem y- und mittlerem bis hohem x-Wert. | ||
|
|
|
 |
 |
 |
Die UV-Werte des dunkelgrünen Hintergrundes
sind nicht satt genug und folglich in die achromatische Region um den Nullpunkt
gefallen. Die drei satten Farben gelb (Ball), rot und blau (Roboter) dagegen
konnten ihre "Farbrichtungen" in der UV-Ebene gut ausprägen und waren
somit auch gut zu segmentieren.
Beim RoboCup besteht die Aufgabe darin, die Positionen von Ball und Robotern im Bild der Overhead-Kamera durch Segmentierung zu gewinnen. Die Berechnung der echten Positionen im Raum erfolgt später mit Hilfe der Kamera-Kalibrierung. Wir haben hier also die Möglichkeit, das Vorwissen für den Segmentierungsalgorithmus durch deutliche farbliche Kennzeichnung der Objekte selbst zu bestimmen und ihn somit zu beschleunigen.
Wenn alle Objekte optimal gekennzeichnet sind,
ist nur noch ein einfacher Algorithmus nötig, der die UV-Werte jedes
Bildpixels mit denen der Objekte vergleicht.
| Spielfeld | Grün, fällt in den achromatischen Bereich und wird daher nicht beachtet |
| Ball | Knall-Orange (Original RoboCup-Ball) |
| Roboter | Bisher Gelb, Violett, Dunkelblau und Hellblau, wir experimentieren aber noch mit günstigeren Farbmarkierungen |
| Plättchen zur Orientierungserkennung | Rot, die kleinen Plättchen werden an einem Ende der Roboter-Markierungen befestigt, um die Orientierung festzustellen |
Die Segmentierungsmethode "Rotation der Chrominanzebene"
nach Torsten Scherer wird verwendet. Dabei werden die Farbwinkel der Objekte
zur Zeit noch per Hand vorgegeben, als Hilfe hierfür können zwei
Arten von Histogrammen erstellt werden:
| 2D-Histogramm | Im 2D-Histogramm wird der Farbwinkel auf die x-Achse aufgetragen. Auf die y-Achse wird die Zahl der Bildpunkte aufgetragen, die in etwa in diesem Winkel liegen. |
| 3D-Histogramm | Das 3D-Diagramm zeigt die Verteilung der Punkte in der UV-Ebene. Die relative Anzahl der Bildpunkte mit Farbwerten (u,v) wird durch die Intensität des Punktes in der UV-Ebene dargestellt. |
Eventuell sollen die Farbwinkel in Zukunft beim
Programmstart einmalig automatisch bestimmt werden. Hinzu kommt eine achromatische
Region um den Ursprung der UV-Ebene, die das Grün des Spielfeldes
einschließt.
Das Suchen geschieht jeweils durch Vergleich
der gefundenen Pixel im UV-Raum mit dem Farbwinkel des zu suchenden Objekts.
Der Algorithmus arbeitet für jedes Objekt in zwei Phasen:
| Fenster-Modus | Grundsätzlich wird jedes Objekt
in einem Fenster fester Größe um die alte Objektposition gesucht,
bei Betrachtung der Maximalgeschwindigkeiten von Roboter und Ball funktioniert
dies auch sehr gut.
Die roten Orientierungsplättchen werden immer nur in diesem Fenster gesucht. Im Fenster wird jeder Pixel beachtet. |
| Gesamtbild-Modus | Wird das Objekt im Fenster-Modus nicht gefunden, so wird das gesamte Bild durchsucht. Dabei wird das Gesamtbild mit einer größeren Schrittweite von mehreren Pixeln abgerastert, um den Algorithmus zu beschleunigen. |
Mit diesem Algorithmus und gut auf die verwendeten Objektmarkierungen angepaßten Farbwinkeln wird derzeit eine Bildrate von ca. 10 Bilder / Sekunde erreicht.
06.08.2000
Außerdem gibt es jetzt auch ein paar Screenshots zu sehen:
Bild 1: Linux-Oberfläche
Zu Anfang sieht das Urprungsbild so aus (ja, es sind noch keine echten Roboter zu sehen, aber uns steht auch erst ein Prototyp zur Verfügung ... außerdem geht es hier ja erstmal nur um die Bildverarbeitung):
Bild 2.1: Original-Kamerabild
Die Programmoberfäche dazu:
Hier können einige Sachen aktiviert werden:
| Farbformat | Aktuelles Farbformat; das einzige für uns wichtige ist der YUV-Planer |
| Anwenden | Hierdurch wird das ausgewählte Farbformat erst angewendet |
| Speichern | Speichern ? Funktioniert (noch?) nicht |
| 2D-Histogramm | Ein echtes Histogramm (2D) (siehe oben); wird nicht mehr gebraucht |
| 3D-Histogramm | 3D-Histogramm (siehe oben); wichtig für automatische Farberkennung |
| Farben-Init | Automatische Farberkennung starten; nur einmal (bei Initialisierung) nötig |
| FPS | Bilder / Sekunde |
Ist der YUV-Planer aktiviert und die automatische Farberkennung einmal durchlaufen worden, sieht das ganze dann so aus:
Bild 3.1: Bild mit gefundenen Objekten
Alle fünf Objekte und die vier Orientierungen sind gefunden. Die Programmoberfläche dazu:
Bild 3.2: Programmoberfläche B
Die Schieberegler dienen dazu:
| Suchbereich
Glättungsfaktor 1 und 2 |
Das Ausgangsbild des YUV-3D-Histogramms enthält
im Ausgangszustand nicht nur die Cluster, sondern auch einiges an Rauschen.
Dies muß (den äußeren Umständen entsprechend, wie
z.B. Lichteinfall) herausgefiltert werden. Dazu wird eine einfache Boxfiltermaske
benutzt und das Ergebnis anschließend mit einem Schwellwert verglichen.
Die Größe der Maske wird durch den Suchbereich angegeben: Ein Suchbereich von n entspricht einer (2*n+1) x (2*n+1) - Matrix, die mit Einsen aufgefüllt ist. Im Prinzip wird also nur bestimmt, wieviele Punkte im Umfeld U des aktuellen Pixels zu finden sind. Der erste Glättungsfaktor besagt: Wenn weniger als X % in der Umgebungs U weiß sind, dann streiche den Pixel weg. Dadurch wird das Rauschen unterdrückt. Der zweite Glättungsfaktor besagt: Wenn mehr als X % in der Umgebungs U weiß sind, dann streiche den Pixel weg. Dies war mal dazu gedacht, die sehr große achromatische Region wegzufressen. Hierfür haben wir aber neuerdings einen kleinen rekursiven "Fressalgorithmus" eingebaut, der vom Ursprung der UV-Ebene alle weißen Pixel wegfrißt. Standard für Glättungsfaktor 2 = 100 %. |
| Fenstergröße | Seitenlänge der Suchfenster für die Objekte. |
| Achromatische Region | War ebenfalls mal dazu gedacht, die achromatische
Region auszublenden, indem alle Pixel mit Abstand < X zum Urpsprung
der UV-Ebene weggestrichen wurden. Hat sich aber ebenfalls dank unseres
rekusiven Fressers erledigt.
Standard: UNBEDINGT 0, wenn der Freßalgorithmus zur Anwendung kommen soll, da dieser sich vom Ursprung aus nach außen durchfrißt. Bei einem X > 0 ist der Ursprung schwarz, d.h. es gibt nicht zu fressen :(. |
| Delta-Winkel | Gibt bei der Farbwinkelfestlegung an, wie weit ein gefundener Pixel von einem bereits vorhandenen Farbwinkel abweichen darf, um noch zu diesem gerechnet zu werden. Ist der Winkel zwischen allen bereits gefundenen Farbwinkeln und dem aktuellen Pixel > X, wird hier ein neuer Farbwinkel angelegt. |
| Orientierungs-Intensität | Da die Qualität der Orientierungsserkennung von äußeren Gegebenheiten abhängt, kann hier angegebenen werden, ab welchen Y-Wert (Helligkeit) ein Pixel zum Orientierungsplättchen gezählt wird. Da die Plättchen weiß sind, sind Werte von 220-250 meist ganz gut (Feinabstimmung). |
| Farben-Init | Automatische Farberkennung starten; nur einmal (bei Initialisierung) nötig |
| Farbslider (rechts) | Hier werden die gefundenen Farbcluster aus der
UV-Ebene farblich dargestellt. Dies ist meist nicht exakt dieselbe Farbe
wie im Bild, was darauf zurückzuführen ist, daß durch die
Projektion auf die UV-Ebene Information über die Farbhelligkeit (Y-Wert)
verloren gegangen ist. Anhand der Slider kann man den Farben die Roboter-IDs
zuordnen.
Im fünften Kästchen ist die Ballfarbe. Der Ball wird anhand einprogrammierter Farbparameter (grell-orange) aus den gefundenen Farbclustern ausgewählt. |
Alles ein bißchen schlecht zu erklären, ohne eine Anwendung gesehen zu haben. Also hier das 3D-Histogramm zur obigen Szene mit obigen Parametern:
Bild 4: 3D-Histogramm
Ein Blick auf die UV-Ebene: Die weißen Flächen sind die nach geeigneter Glättung übriggebliebenen Cluster. Graue Flächen stellen die aufgrund des ersten Glättungsfaktors weggestrichenen Punkte (Entfernung von Rauschen). Die schwarze Fläche im inneren ist unserem kleinen Fressalgorithmus zu verdanken (Hintergrundgrün wird herausgefiltert). Daraufhin werden die Cluster gesucht. Clusterprototypen werden durch Polarkoordinaten (Radius und Betrag) charakterisiert. Im Originalbild gefundene Pixel, die von einem der Prototypen nur sehr gering abweichen, werden dann zum jeweiligen Objekt zur weiteren Schwerpunktbestimmung genutzt.
So. Ich hoffe, ich habe den derzeitigen Stand der Bildverarbeitung erstmal angemessen dargelegt. Sollte ich irgendwas vergessen haben oder solltet ihr irgendwelche Fragen haben sprecht mich einfach an oder mailt mir.
15.11.2000
| Horn | "Robot Vision",
Kapitel 5: "Regions & Image Segmentation" |
| Christian Scheering,
Alois Knoll |
"Fast Colour Image Segmentation Using A Pre-Clustered Chromaticity-Plane" |
| Henryk Palus | "Nutzung des Wissens über die Farbe des Bildhintergrundes zur Segmentierung von Farbbildern" |
| Christian Scheering | "Domain-Knowledge Incorporation For Fast Colour Image Segmentation Using A Pre-Clustered Chromaticity-Plane" |
| K.S. Fu,
R.C. Gonzalez, C.S.G. Lee |
"ROBOTICS Control,
Sensing, Vision And Intelligence",
Kapitel 8.2: "Segmentation" |
Links zum Vortrag:
| http://www.techfak.uni-bielefeld.de/techfak/ags/ti/personen/pcscheer/home_pcscheer.html
Verschiedene Artikel von Christian Scheering zum downloaden |
| http://www.fh-trier.de/~soldoa/VideoRZ/Glossar.html
Lexikon |
| http://chemsrv0.pph.univie.ac.at/SUPPORT/Lexicon/yl.htm
Lexikon |
| http://videox.net/lexikon.html
Lexikon |
| http://www.uni-paderborn.de/fachbereich/AG/agdomik/extern/computergrafik/cg_skript/html/node141.htm
YUV-Beschreibung |
| http://www.cs.sfu.ca/undergrad/CourseMaterials/CMPT365/material/notes/Chap3/Chap3.3/Chap3.3.html
Ausführliche Grundlagen von Farbe und Video |
| http://www.prz.tu-berlin.de/docs/Publications/TUB-PRZ-W-1243/diplomto.html |
| http://www.brandenburg-gmbh.de/brandenburg-gmbh/lightcolor_de.html
Links und 3D-Modelle von Farbräumen |
andere Links von Thomas Hofmann