Formbasierte Ballerkennung für humanoide Fußball

Transcrição

Bachelorarbeit
Formbasierte Ballerkennung für humanoide
Fußball-Roboter
Max Maria Losch
Freie Universität Berlin
Fachbereich Mathematik und Informatik
Institut für Informatik
Bachelorarbeit
Formbasierte Ballerkennung für humanoide
Fußball-Roboter
von
Max Maria Losch
[email protected]
Berlin, den 31. August 2012
Gutachter:
Betreuer:
Prof. Dr. Raúl Rojas
Dr. Hamid Reza Moballegh
Zusammenfassung
Diese Bachelorarbeit befasst sich mit der Entwicklung eines Algorithmus zur formbasierten Ballerkennung für Fußball spielende, humanoide Roboter im RoboCup Kontext. Die
Regeln des RoboCups werden jährlich um bestimmte Punkte erschwert, um neue Methoden
zu erproben und dem Ziel näher zu kommen, bis zum Jahr 2050 gegen den Menschen als
Gegner zu gewinnen. Ein nächster Schritt in diese Richtung ist das Erkennen eines Balls
beliebiger Farbe mit beliebigem Muster, da der Ball bisher anhand seiner spezifischen Farbe
detektiert wurde.
Der in dieser Arbeit vorgestellte Algorithmus basiert auf der Idee, einen Ball anhand seiner Kantenrichtungen zu erkennen. Bei einem Ball wird angenommen, dass alle Kantenrichtungen vorkommen und diese gleichverteilt sind. Ziel ist es, diese Idee möglichst gut
auszubauen, sodass die Ballerkennung eine gute Erkennungsrate und eine geringe Laufzeit
erreicht.
iii
Inhaltsverzeichnis
1
Einleitung
1.1
1.2
1.3
1.4
1.5
2
2.2
2.3
2.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Strukturen im Bild erkennen . . .
2.1.1 Farben . . . . . . . . . .
2.1.2 Helligkeitsunterschiede . .
2.1.3 Gradienten . . . . . . . .
Kantendetektion im Detail . . . .
Hough-Transformation für Kreise
Verwandte Arbeiten . . . . . . . .
2.4.1 RoboCup-Domäne . . . .
2.4.2 Fremde Domänen . . . . .
3.2
3.3
1
2
3
4
4
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Formbasierte Ballerkennung
3.1
4
.
.
.
.
.
Grundlagen
2.1
3
1
Motivation . . . . . . . . . . . . . .
RoboCup . . . . . . . . . . . . . .
Die Technical Challenge „Dribbling“
Berlin United - FUmanois . . . . .
Wie Roboter sehen . . . . . . . . .
Anforderungen . . . . . . . . . . . . .
3.1.1 Universalität . . . . . . . . . .
3.1.2 Qualität . . . . . . . . . . . . .
3.1.3 Performance . . . . . . . . . .
Konzept . . . . . . . . . . . . . . . . .
3.2.1 Kantendetektion . . . . . . . .
3.2.2 Hypothesensuche . . . . . . . .
3.2.3 Verifizierung . . . . . . . . . .
Optimierung . . . . . . . . . . . . . . .
3.3.1 Optimieren der Kantendetektion
3.3.2 Integrales Histogrammbild . . .
3.3.3 Rekursive Suche . . . . . . . .
3.3.4 Kandidatenverifizierung . . . .
6
6
7
9
11
15
17
17
19
20
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
20
21
21
21
22
23
26
28
28
34
36
37
Auswertung
41
4.1
4.2
41
42
Laufzeitanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Erkennungsrate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
Inhaltsverzeichnis
5
Fazit
5.1
5.2
6
43
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Vor- und Nachteile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
43
Ausblick
45
6.1
6.2
6.3
45
45
45
Verbesserungsmöglichkeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Anwendbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Alternativen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
1 Einleitung
1.1 Motivation
Die RoboCup - Initiative sieht vor, dass humanoide Roboter bis zum Jahr 2050 gegen Menschen im
Fußball gewinnen [Rob12a]. Dabei sollen sie unter Einhaltung der offiziellen FIFA-Regeln spielen. Um
dieses Ziel zu erreichen werden die RoboCup-Regeln immer weiter angeglichen. 2012 wurde daher die
Technical Challenge „Dribbling“ der Kid-Size-Liga um den Einsatz eines Balls beliebiger Farbe erweitert
[Rob12b]. In dieser Challenge muss der Roboter den Ball um Hindernisse und schlussendlich in das Tor
dribbeln können.
Das Entwickeln eines Algorithmus um Bälle unabhängig von der Farbe und damit formbasiert zu
erkennen ist Thema dieser Arbeit. Sie basiert auf einem Methodenvorschlag der Dissertation von Hamid
Reza Moballegh [Mob11].
Abb. 1.1: Aufbau des Fußballfelds 1
Humanoide Roboter oder allgemeiner die künstliche Intelligenz ist ein Thema, das die Informatik seit
Jahrzehnten intensiv beschäftigt. Ein elementares Teilgebiet davon ist das Sehen, welches analog zum
menschlichen Auge mit Kameras geschehen kann. Das Sehen ist eine der komplexesten Aufgaben, die
das menschliche Gehirn mit erstaunlicher Genauigkeit vollbringt. Das Auswerten von Kamerabildern ist
demzufolge ein anspruchsvolles Thema, vor allem wenn versucht werden soll, die Erkennung auch bei
erschwerten Bedingungen, wie in dunklen Räumen zu gewährleisten.
Auch bei den humanoiden Fußballrobotern spielt das Sehen eine grundlegende Rolle, da dass Auswerten von Kamerabildern die einzige Möglichkeit der Orientierung auf dem Spielfeld ist. Denn nur dadurch
können Objekte wie Tore, Gegner oder Bälle erkannt und lokalisiert werden.
1 Quelle:
[Rob12b, Seite 4]
1
1 Einleitung
Abb. 1.3: Aldebaran NAO 2
Abb. 1.4: NimbRo Teen-Size 3
1.2 RoboCup
1997 wurde die wissenschaftliche Initiative RoboCup mit dem ultimativen Ziel gegründet, Menschen
als Gegner im Fußball unter den offiziellen FIFA-Regeln, bis zum Jahr 2050, zu besiegen. Seit dem
hat sich der jährlich stattfindende RoboCup zu einem der wichtigsten Events für die Wissenschaft der
künstlichen Intelligenz und der autonomen Roboter entwickelt. Dabei gibt es heute nicht mehr nur das
Gebiet des Fußballs, sondern auch neue Gebiete wie zum Beispiel Home sind hinzukommen, in welchen
Roboter entwickelt werden, welche den Menschen beim alltäglichen Haushalt unterstützen sollen. Die
damit verbundenen Wettkämpfe erweitern jährlich die Grenzen der autonom agierenden Roboter und
beeinflussen damit auch die Einsetzbarkeit für kommerzielle Bereiche [Bos12].
Abb. 1.2: Logo der RoboCup Initiative
Die RoboCup-Liga Soccer umfasst mehrere kleinere Ligen, in denen Teams aus der ganzen Welt
ihre Roboter im Fußball gegeneinander antreten lassen. Sie unterteilt sich in die Bereiche Simulation,
Small Size, Mid Size, Standard Platform League (SPL) und Humanoid League. Die Small- und Mid Size
Ligen spielen mit Robotern, welche sich auf Rädern und Rollen fortbewegen und sind auf Grund der
vereinfachten Fortbewegungsart besonders weit in taktischem Verhalten und Koordination im Team. Die
Simulationsliga simuliert komplette Spiele mit Robotern.
In der SPL und der Humanoid League hingegen, treten Roboter mit menschlichen Proportionen und
Merkmalen an, wobei in der SPL nur der gleiche Typ verwendet wird. Bei diesem handelt es sich um den
Aldebaran NAO, bei dem die Software von den Teams jedoch eigenständig entwickelt werden muss. In
2
1 Einleitung
der humanoiden Liga können dagegen jegliche Roboter teilnehmen, solange sie mit den RoboCup - Regeln konform sind. Ausgeschlossen ist hier nur die Verwendung der SPL-Roboter. Die von der Initiative
festgelegten Regeln werden jährlich immer stärker an menschliche Proportionen angepasst. Vorher große
quadratische Füße oder zu lange Arme sind z.B. Merkmale von Robotern, welche noch vor einigen Jahren häufig von Teams verwendet wurden, um unter anderem die Stabilität beim Laufen zu erhöhen. Die
stetige Verschärfung der Regeln zwingt die Teilnehmer ihre Forschungen voranzutreiben und vermischt
die Chancen von bisher schlechten oder guten Teams auf jedes Jahr erneut.
Die schon angesprochene Vielseitigkeit beim RoboCup ergibt sich auch aus der Unterteilung der humanoiden Liga in drei weitere Klassen. Die Kid-Size-Klasse beinhaltet dabei Roboter der Größe (30 60cm), Teen-Size (100 - 120cm) und Adult-Size (>130cm).
Dabei ist die Kid-Size-Klasse die am schnellsten fortschreitende Klasse, in welcher bis zu 3 Roboter
pro Team antreten. Aufgrund der niedrigen Bauhöhe und des leichten Gewichts, sind die ausgetragenen
Spiele bereits relativ schnell.
Neben den regulären Fußball-Wettkämpfen, gibt es noch zusätzliche Herausforderungen, sogenannte Technical Challenges, welche den Robotern neue Fertigkeiten beibringen sollen. Die Absicht dieser
Technical Challenges ist die Vorbereitung auf zukünftige Regeln und die Erprobung dieser Fertigkeiten.
In der Kid-Size-Liga gab es im offiziellen RoboCup 2012 insgesamt 4 verschiedene Technical Challenges: Einwurf, Doppel-Pass, Hochschuss und Dribbling um Hindernisse. Das am besten abschneidende
Team beim RoboCup erhält den Titel "Best Humanoid", muss dafür aber auch gute Ergebnisse bei den
Technical Challenges erreicht haben.
Die Technical Challenge "Dribbling" wurde für 2012 um den Einsatz eines Balls beliebiger Farbe
erweitert.
1.3 Die Technical Challenge „Dribbling“
In der Dribbling-Challenge werden sechs schwarze Gegenstände von 20cm Durchmesser und 90cm Höhe
zufällig auf dem Spielfeld verteilt. Dabei beträgt der Abstand zwischen den Gegenständen mindestens
50cm. Der Schiedsrichten wählt vor Anpfiff einen Ball beliebiger Farbe und beliebigen Musters aus und
legt ihn vor den Roboter in den zentralen Kreis des Spielfelds. Ab diesem Zeitpunkt wird dem Roboter
eine beliebige Zeit zum initialen erkennen des Balls gewährleistet. Währenddessen, darf der Roboter
aber nicht programmiert werden.
Nach Anpfiff muss der Roboter den Ball auf möglichst kurzem Wege durch die Hindernisse und ins
Tor dribbeln. Die Challenge gilt als gewonnen, wenn der Roboter die Torlinie berührt und der Ball vollständig im Tor ist.
Die Größe des zufällig ausgewählten Balls in der Kid-Size-Liga beträgt etwa 7cm und ist von gleicher
Masse und ähnlicher Oberfläche wie der eines Standard-Tennisballs (siehe Abbildung 1.5). Zur Farbe des
Balls wird in den RoboCup-Regeln lediglich die Zusicherung gemacht, dass weder eine ähnliche Farbe
zum Feld noch eine ähnliche Farbe zum bisher eingesetzten, orangenen Ball verwendet wird [Rob12b].
3 Quelle:
http://www.aldebaran-robotics.com/en/Discover-NAO/images-gallery.html#
!ARGallery%5Bgallery1%5D/5/
3 Quelle:
http://www.ais.uni-bonn.de/nimbro/Humanoid/images/RC12/RC12_NimbRo_vs_
DARwIn-XOS_1.jpg
3
1 Einleitung
Abb. 1.5: Standardball der Kid-Size-Liga
1.4 Berlin United - FUmanois
Das Berlin United - FUmanoids - Team ist ein studentisches Projekt der Freien Universität Berlin, in
der Gruppe Künstliche Intelligenz. Entstanden im Jahr 2006, nehmen sie seit 2007 mit ihren eigens
entworfenen humanoiden Robotern an den offiziellen RoboCup-Wettkämpfen in der Kid-Size-Liga teil.
Seitdem konnten sie viele der Wettkämpfe sehr erfolgreich abschließen. Zu nennen sind dabei der 3.
Platz in den USA im Jahr 2007 des ersten Antritts, den 1. Platz bei den Iran Open von 2008 bis 2011 und
viele mehr [FUm12]. Das Entwickeln von humanoiden Fußball spielenden Robotern bietet eine große
Abb. 1.6: Logo der Berlin United - FUmanoids
Bandbreite an erforschbaren Gebieten. Mechanik, Lokalisierung, Vision und weitere Gebiete treiben
noch wenig untersuchte Themen der Robotik voran.
Das Gebiet der Mechanik und der Hardware bei den Berlin United - FUmanoids brachte dieses Jahr
die 5. Generation von Robotern hervor, welche nicht nur leichter und damit stabiler sind, sondern auch
auf Grund eines stärkeren Prozessors Algorithmen schneller ausführen können und damit auch genügend
Leistungsreserven für komplexere Aufgaben besitzen.
1.5 Wie Roboter sehen
Roboter können ihre Umwelt mit einer Vielzahl verschiedener Sensoren wahrnehmen. Dazu zählt das
Aussenden von Laser- oder Ultraschallimpulsen, welche eine gute Rekonstruktion der Umwelt in einem
dreidimensionalen Koordinatensystem ermöglichen, da sie die Entfernung zu jedem Punkt im Raum
messen. Diese Art von Sensorik ist gut geeignet um Hindernisse zu erkennen, nicht jedoch um Farben
oder Helligkeiten zu unterscheiden. Farben und Helligkeiten lassen sich mit Bildsensoren erfassen, welche das einfallende Licht auf eine Ebene abbilden.
4
1 Einleitung
Der Aufbau des Roboters und damit auch die Art wie der Roboter seine Umwelt wahrnehmen darf, ist
in den RoboCup-Regeln festgelegt. Diese besagen, dass der Roboter nur Sinne besitzen darf, welche den
Sinnen des Menschen entsprechen [Rob12b]. Aus diesem Grund beschränkt sich die visuelle Sensorik
auf Kameras, welche die Augen imitieren.
Eine naheliegende Entwicklung wäre der Einsatz von zwei Kameras um räumliches Sehen zu ermöglichen. Da der Rechenaufwand für die Auswertung von zwei Bildern jedoch zu hoch für die aktuell
eingesetzte Hardware ist, beschränkt sich das Sehen bei den Robotern der Berlin United - FUmanoids
auf eine Kamera. Aufgrund der dem Roboter bekannt gemachten Umgebung beim Spiel, ist räumliches
Sehen jedoch nicht notwendig, hätte aber den Vorteil der Tiefenwahrnehmung. Die eingesetzte Kamera
ist in Abbildung 1.7 zu sehen und befindet sich, dem Menschen nicht unähnlich, auf dem Oberkörper des
Roboters.
Abb. 1.7: Roboter 2012
Bei der eingesetzten Kamera handelt es sich um eine Logitech Quickcam C910 mit einer Auflösung
von 640x480 Pixeln. Je nach Lichtverhältnis der Umgebung kann sie bis zu 30 Bilder pro Sekunde liefern
[SOK+ 12]. Das Ausgabeformat der Kamera ist YCbCr (siehe Kapitel 2.1.1).
5
2 Grundlagen
Bevor das Konzept der formbasierten Ballerkennung vorgestellt wird, wird in diesem Kapitel eine Übersicht über einige der wichtigsten Methoden zur Objektdetektion präsentiert. Einige davon werden im
Anschluss auch für diesen Anwendungsfall verwendet und verbessert. Besondere Aufmerksamkeit soll
dem Erzeugen von Kanten gelten, welche im Anschluss die Grundlage für die Balldetektion darstellen
werden.
2.1 Strukturen im Bild erkennen
Das Kamerabild stellt Farben und Helligkeitswerte als Basisinformationen bereit. Mit diesen lassen sich
durch verschiedenste Verfahren Strukturen extrahieren, welche sich wiederum als Objekte interpretieren
lassen. Die gängigsten Methoden beschränken sich auf die Zuordnung von Farben zu Objekten, den Vergleich von Helligkeitswerten oder dem Bestimmen und Auswerten von Kanten.
2.1.1 Farben
Wenn in der Bildverarbeitung vom Begriff Farbe gesprochen wird, ist meist ein Tripel gemeint, welches die Farbe in einem Farbraum definiert. Mit diesen Farbräumen werden, die durch das Licht für den
Menschen visuell wahrnehmbaren Reize abgebildet. Der bekannteste Farbraum ist der RGB-Farbraum,
bestehend aus den Komponenten Rot, Grün und Blau. Dieser wurde zur Darstellung von Farben in Bildschirmen entworfen, da nur durch Intensitätsjustierungen der drei Grundfarben, alle wahrnehmbaren
Farben dargestellt werden können.
Jeder Farbraum erfüllt in bestimmten Domänen einen spezifischen Zweck. Der YCbCr-Farbraum zum
Beispiel , bestehend aus den Komponenten Helligkeit (Y), Blau-Gelb-Sättigung (Cb) und Rot-GrünSättigung (Cr) (siehe Abbildung 2.1), lässt sich auf Grund der Eigenschaften des menschlichen Sehsinns
Farbunterabtasten. Der menschliche Sehsinn kann leichter zwei Helligkeiten, als zwei Farbtöne unterscheiden. Das Farbunterabtasten macht sich dies zu nutze und speichert z.B. für zwei Pixel zwei Y-, aber
nur je einen Cb- und Cr-Wert. Auf diese Weise können ohne subjektiven Verlust die Hälfte an Informationen gespart werden. Der YCbCr-Farbraum wird auch von den Berlin United - FUmanoids verwendet,
da er von der Kamera geliefert wird. Um nun Farben als Grundlage der Objekterkennung verwenden zu
können, benötigt es Methoden, welche die Unterschiede zwischen zwei oder mehreren Werten bestimmt
(siehe Seite 7 und 9) oder bestimmte Farben anhand von Farbraum-Teilmengen klassifiziert.
1 Quelle:
Christoph Peters, http://en.wikipedia.org/wiki/File:YCbCrColorSpace_Perspective.png
, CC0 1.0
6
2 Grundlagen
Abb. 2.1: YCbCr - Farbraum 1
Die Teilmengen-Klassifizierung kann relativ einfach umgesetzt werden. Soll zum Beispiel ein roter
Ball extrahiert werden, kann im YCbCr Farbraum eine Teilmenge selektiert werden, welche die rötlichen
Farben abdeckt. Alle Punkte im Bild, welche Elemente dieser Menge sind, werden als Rot und damit als
Ball markiert. Das Bestimmen der Teilmengen kann auf zwei verschiedene Arten geschehen.
Manuelles Bestimmen führt zu festen Teilmengen, welche nur für sich sehr wenig verändernde Lichtverhältnisse funktioniert. Ändern sich die Lichtverhältnisse schon in geringem Maße, müssen die Teilmengen gänzlich neu bestimmt werden, da nicht mehr alle Farbtöne abgedeckt sind. Bei schlecht ausgeleuchteten oder überbelichteten Umgebungen, sammeln sich die Farben des Bildes nur in einem kleinen
Bereich des Farbraums (siehe Abbildung 2.2b). Hier ist das Zuordnen von Farben erschwert und in den
schlimmsten Fällen gar nicht mehr möglich, da die Farben so stark verlaufen, dass keine ausreichende
Abgrenzung durch die Teilmengen möglich ist. Neben der Bestimmung der Farbräume ist also auch ein
gut belichtetes Kamerabild elementar.
Das Umgehen der manuellen Bestimmung der Teilmengen lässt sich mit dynamischer Schwellwertanpassung lösen. Die Berlin United - FUmanoids benutzen seit 2012 ein sich automatisch kalibrierenden
Algorithmus zur Detektion von Feld, Toren, Seitenpfosten, Ball und Hindernissen. Er wurde im Rahmen
einer Masterarbeit von Lisa Dohrmann entwickelt [Doh12]. Erneut die Detektion des Balls betrachtet,
klassifiziert der Algorithmus von Dohrmann zwar ebenso mit Hilfe einer Teilmenge, welcher jedoch auf
dem HSV-Farbraum definiert ist. Der HSV-Farbraum definiert eine Farbe anhand seines Farbtons, der
Sättigung und der Helligkeit. Da die Farbe des Balls bekannt ist, kann demnach ein Intervall auf dem
Farbton festgelegt werden. Um sich nun automatisch an die Lichtverhältnisse anpassen zu können, ist das
Intervall zu Beginn großzügig definiert, deckt also einen großen Farbtonbereich ab. Wurde ein Ball gefunden, wird der am häufigsten vorkommende Bereich bestimmt und das ursprünglich gesetzte Intervall
darauf angepasst.
2.1.2 Helligkeitsunterschiede
Eine weitere Möglichkeit, Objekte zu erkennen, ist das Vergleichen von durchschnittlichen Helligkeitsoder Farbwerten in disjunkten Bildregionen. Um damit ein Objekt zu klassifizieren, muss ein Durchschnittswert größer oder kleiner als der andere sein. Diese Methode wurde erstmals von Papageorgiou,
Oren und Poggio zur Detektion von Gesichtern eingeführt [POP98]. Inzwischen wird die Methode in der
7
2 Grundlagen
(a) Gut beleuchtetes Spielfeld
(b) Schlecht beleuchtetes Spielfeld
Abb. 2.2: YCbCr Farbverteilung von zwei unterschiedlichen beleuchteten Spielfeldern
Abbildungserläuterung:
Weiße Achse: Y
Blaue Achse: Cb
Rote Achse: Cr
Bildverarbeitung häufig angewendet, da sie sich relativ einfach übertragen lässt.
Das Vergleichen von Helligkeitswerten von Flächen lässt sich formell zusammenfassen. Im folgenden
werden dabei die Hell-Dunkel-Flächen als Haar-like Feature bezeichnet.
AD :
AH :
YD :
YH :
θ:
Dunkle Fläche
Helle Fläche
Durchschnittlicher Intensitätswert von AD
Durchschnittlicher Intensitätswert von AH
Schwellwert
Wert(pixel)
∑
YD =
pixel∈AD
YH =
pixel∈AH
AD
Wert(pixel)
∑
AH
Klassi f ikator(YD ,YH , θ ) :=
−1 f alls YH −YD < θ
1
sonst
(2.1)
Abbildung 2.3a, 2.3b und 2.3c illustriert eine stark vereinfachte Methode, mit durchschnittlichen Helligkeitswerten von Flächen einen Ball zu erkennen. Abbildung 2.3b ist der Extrahierte Cr-Teil des Bildes
2.3a, auf welchem sich die Haar-like Features für dieses Beispiel am deutlichsten anwenden lassen. Liegt
wie hier ein rotes Objekt vor, liefert der Cr Teil einen hellen Wert für rötliche Werte und einen dunklen
für die umgebenden grünen Werte. Ein einfacher Klassifikator könnte nun aus einer Kreisfläche, welche
helle Intensitätswerte erwartet, und einer Ringfläche, welche dunkle Werte erwartet (folglich Abbildung
2.3c), bestehen. Der rote Ball lässt sich daraufhin sehr einfach durch Gleichung (2.1) bestimmen. Um
einen Ball in einem beliebigen Bild zu erkennen, bewegt man den Klassifikator über jeden Pixel, um jede
mögliche Position des Balls abzudecken.
8
2 Grundlagen
(a) Ball (YCbCr-Farbraum)
(b) Cr - Teil des Bildes
(c) Applikation der Hell-Dunkel
Flächen
Abb. 2.3: Exemplarische Balldetektion mit Hell-Dunkel-Flächen
Ein Problem dieser Methode ist, dass das Muster, welches zur Detektion eines Objekts zuständig ist,
nur für eine feste Skalierung funktioniert. Dies impliziert, dass das Muster für einen großen Bereich an
Skalierungen auf das Bild angewendet werden muss. Zusätzlich fällt bei der Detektion das Berechnen
der durchschnittlichen Intensitätswerte ins Gewicht, welche je nach Flächenkomplexität zu einem sehr
hohen Aufwand führen kann. Der Klassifikator des roten Balls als Beispiel führt in einer Abschätzung
zu folgender Komplexität:
t:
c1 :
c2 :
n:
m:
Anzahl Skalierungen
Anzahl der durchschnittlichen Pixel in der dunklen Fläche pro Skalierung
Anzahl der durchschnittlichen Pixel in der hellen Fläche pro Skalierung
Breite des zu durchsuchenden Bildes
Höhe des zu durchsuchenden Bildes
O(Klassi f ikator) = n · m · t · c1 · c2
(2.2)
Für ein Bild mit 640x480 Pixeln und der Annahme, dass der kleinste zu findende Balldurchmesser 10
Pixel und der größte Durchmesser 200 Pixel beträgt, kann eine Abschätzung der Menge an Operationen
gemacht werden. Für c1 und c2 wird an dieser Stelle angenommen, dass die Komplexität konstant ist.
n · m · t · c1 · c2 = 640 · 480 · 190 · 1 · 1 = 58.368.000
Naiv gelöst benötigt das Durchsuchen des Bildes mit diesem Klassifikator also über 58 Millionen Operationen, in welche das Berechnen der Fläche selber noch nicht mit einbezogen ist. Für einfache Flächenformen, insbesondere Rechtecke, ist die Komplexität durch Verwenden eines Integralbildes jedoch
tatsächlich konstant (siehe Kapitel 3.3.2).
2.1.3 Gradienten
Das Vergleichen von Intensitätswerten lässt sich per Vergleich von einzelnen Bildpunkten weiter spezialisieren. Vereinfacht ist dies eine Lösung um Kanten in Bildern zu bestimmen. Dabei werden benachbarte
Bildpunkte verglichen. Ist der eine Wert viel grösser als der andere, muss es sich um eine Kante handeln.
Abbildung 2.4a zeigt ein einfaches Beispiel anhand einer Reihe von Grauwerten.
9
2 Grundlagen
(a) Deutliche Kante
(b) Undeutliche Kante
Abb. 2.4: Schematische Darstellung von Intensitätsverläufen
Abb. 2.5: Graustufenbild mit Vergößerung einer Pixelreihe des linken Torpfostens
Erschwert wird die Kantendetektion, wenn der Kontrast zwischen zwei benachbarten Bildpunkten
nicht mehr eindeutig ist (siehe Abbildung 2.4b). Dies ist kein triviales Problem und wurde bereits in verschiedenen Ausarbeitungen, wie z.B. [Sch00] behandelt und untersucht. Allgemein lässt sich die Kantendetektion durch ableiten einer Reihe oder Spalte eines Bildes beschreiben. Formell lässt sich dies wie
folgt zusammenfassen:
Der Intensitätsverlauf zwischen zwei Punkten im Bild wird als Gradient bezeichnet, welcher die Richtung des größten Anstiegs sowie die Stärke der Änderung definiert. Der Gradient lässt sich als Operator
∇ definieren, welcher angewendet auf ein Bild, ein Gradientenfeld erzeugt.
δ I(x, y) δ I(x, y)
∇I(x, y) =
,
δx
δy
T
= [Gx , Gy ]T
(2.3)
Das Ergebnis sind zwei eindimensionale Gradienten je Bildpunkt, welche die Stärke der Änderung
durch die Beträge und die Richtung durch die Vorzeichen bestimmen. Mit Hilfe der Inversen des Tangens
lässt sich zusätzlich die Richtung der stärksten Änderung im zweidimensionalen Bild bestimmen und mit
Hilfe der euklidischen Norm die Stärke (Magnitude).
Gx q 2
= Gx + Gy 2
mag = Gy Gy
φ = arctan
Gx
(2.4)
(2.5)
Zur Verdeutlichung wird der Differentialoperator auf eine ausgewählte Reihe in Bild 2.5 appliziert.
Die Reihe von Intensitäten lässt sich als stetige Funktion interpretieren. Abbildung 2.6a ist der eine ver-
10
2 Grundlagen
3
3
2
2
1
1
0
1
2
3
4
5
6
7
8
9
0
1
-1
-1
-2
-2
-3
-3
(a) Funktion
2
3
4
5
6
7
8
9
(b) Erste Ableitung (In Rot)
Abb. 2.6: Beispielfunktion und erste Ableitung
einfachte Darstellung, welche die hellen Bildpunkte als Null interpretiert und die dunklen Bildpunkte im
Intervall ]0, −1]. Wird diese Funktion abgeleitet, ergibt sich Abbildung 2.6b. Zu erkennen ist jeweils ein
Extrema bei einem Wechsel von Hell nach Dunkel und einem Wechsel von Dunkel nach Hell. Die Ableitung „reagiert“ also auf Wechsel zwischen Intensitäten und das umso stärker, je schneller der Wechsel
in der Funktion geschieht.
Da das Bild keine stetige Funktion ist, die abgeleitet werden kann, greift man auf Approximationen
zurück, welche auf diskreten Mengen wie Bildern funktionieren. Dafür wird für jeden Bildpunkt lokal
die Differenz zweier Nachbarpixel berechnet, wie bereits zu Beginn dieses Kapitels eingeführt. Durch
Anwenden der Approximation auf die diskrete Bildmenge in x sowie in y Richtung, ergeben sich für
jeden Bildpunkt die Gradienten Gx und Gy .
Folgend ein einfacher Operator, der die erste Ableitung ∇I(x, y) implementiert (siehe Faltungsmatrizen
(2.6). Er berechnet durch Konvolution mit der Bildmatrix die Ergebnisbilder 2.7a und 2.7b. Durch Bestimmung der Magnituden der Gradienten durch Gleichung (2.4) kann ein Kantenbild berechnet werden
(siehe Abbildung 2.8). Die Kantenerkennung der Berlin United - FUmanoids basiert derzeit auf diesem
Operator.

Gx = Kx · I = 1/2 0 −1/2 · I
und

1/2
Gy = Ky · I =  0  · I
−1/2
(2.6)
Einfacher Operator zur Berechnung der Gradienten in horizontaler und vertikaler Richtung
2.2 Kantendetektion im Detail
Ein Problem der besprochenen Kantendetektion ist die Empfindlichkeit gegenüber Bildrauschen. Der
Operator ∇I(x, y) erzeugt auch bei kleinen Intensitätsänderungen einen Ausschlag, welche zu einer sehr
11
2 Grundlagen
(a) Kx aus (2.6)
(b) Ky aus (2.6)
Abb. 2.7: Ergebnisse der Konvolution mit dem horizontalen und dem vertikalen Kantendetektions Operator. (Normiert um negative Gradienten darstellen zu können)
Abb. 2.8: Kantenbild der Abbildung 2.5
12
2 Grundlagen
Abb. 2.9: Robotersicht auf Hinderniss, Ball und Tor (in Grautönen)
(a) θ = 0
(b) θ = 5
(c) θ = 20
Abb. 2.10: Auswirkung des Schwellwertfilters
großen Menge an Kanten im Ergebnisbild führen. Diese durch Rauschen entstandenen Kanten sind für
die Auswertung in der Regel unwichtig, erschweren aber die Analyse. Ziel ist es, diese überflüssigen
Kanten zu filtern. Abbildung 2.10a verdeutlicht die entstandene Menge an Kanten des Beispielbilds 2.9.
In dieser ist jeder Gradient mit einer Magnitude größer als Null mit Weiß markiert, der Rest mit Schwarz.
Ein Ansatz ist das Filtern anhand der Kantenstärke. Dabei werden alle Kanten, die eine kleinere Magnitude als ein festgelegter Schwellwert haben, entfernt (siehe Funktion (2.7)). Oft werden dadurch aber
auch wichtige Kanten entfernt, weil sie sich nicht genug vom Hinter- oder Untergrund abheben. Dazu
Ein Beispiel:
Wirft ein größeres Objekt einen Schatten auf das zu untersuchende Objekt, so sinkt der Kontrast an
dieser Stelle zwischen Umgebung und Objekt. Demzufolge ist der Intensitätsanstieg gemindert, was zu
kleineren Magnituden führt. Ist nun der Schwellwert zu groß eingestellt, um auch schwache Kanten zu
akzeptieren, eliminiert dieser viele der Kanten im Schatten. Abbildung 2.10c zeigt eine stark ausgedünnte
Kantenmenge, in der die unteren Kanten des linken Balls bereits durch den Schattenwurf verschwinden.
0 f alls mag < θ
Schwellwert f ilter(mag, θ ) :=
(2.7)
1 sonst
Eine bessere Methode, das Rauschen in Bildern zu minimieren, ist für jeden Bildpunkt einen Mittelwert aus sich und seinen Nachbarn zu berechnen. Auf diese Weise werden auch die Werte umgebener
Bildpunkte mit einbezogen und sorgen so für eine Glättung des Bildes. Eine einfache Glättung mit Hilfe
des arithmetischen Mittels über alle acht Nachbarn kann mit folgender Faltungsmatrix berechnet werden:
13
2 Grundlagen
(a)
(b)
(c)
Abb. 2.11: Strategien zur Minimierung der Kantenmenge. a) und b) Mit Operator (2.8) Geglättes Bild
und anschließende Schwellwertfilterung mit θ = 5, c) Mit Sobel-Operator nach Schwellwertfilterung
mit θ = 5


1 1 1
1
SA =  1 1 1  · I
9
1 1 1
(2.8)
Im Ganzen betrachtet, wirkt das Bild nach der Glättung unscharf (siehe Abbildung 2.11a). Sehr kleine
Strukturen und Körnungen unterscheiden sich im Anschluss weniger von der Umgebung, alle dominanten Kanten sind aber weiterhin sichtbar. Besonders deutlich wird die Auswirkung durch den Vergleich
zwischen Abbildung 2.10b und Abbildung 2.11b. Bei gleichem Schwellwert θ = 5 sind im geglätteten
Bild ein vielfaches weniger an Kanten als im normalen Bild. Um mit dem normalen Bild ein äquivalentes
Ergebnis zu erhalten, muss der Schwellwert des Filters erhöht werden (siehe Abbildung 2.10c). Hier sind
die unteren Kanten des linken Balls jedoch schon teilweise eliminiert.
Durch das Glätten des Bildes lässt sich also das Problem der Eliminierung von schwachen Kanten in
dunklen Bildbereichen durch den Schwellwertfilter verbessern. Üblicherweise wird anstelle eines arithmetischen Mittels eine Normalverteilung angewendet, um umgebene Pixel weniger stark zu gewichten
als den oder die zentralen Pixel (siehe Faltungsmatrix (2.9)). Im Folgenden wird bei der Glättung mit
Hilfe einer Normalverteilung von einem Gauß-Filter gesprochen.


1 2 1
1 
2 4 2 ·I
SG =
(2.9)
16
1 2 1
3x3 Gauß-Filter
Neben Gradientenbestimmung und Glättung getrennt zu betrachten, gibt es auch Faltungsmatrizen die
beides in sich vereinen. Ein bekanntes Beispiel dafür ist der Sobel-Operator, welcher für horizontale
Kanten die x-Richtung glättet und für vertikale Kanten die y-Richtung (siehe nachfolgende Gleichungen
(2.10) und (2.11)). Der Sobel-Operator bietet zwar ein etwas schlechteres Ergebnis als das Verwenden
von getrennten Faltungsmatrizen (siehe Abbildung 2.11c, ist dafür aber besser als die reine Faltung mit
Operator (2.6).
14
2 Grundlagen




1 0 −1
1
2
1
0
0 ·I
Gx = 2 0 −2 · I
(2.10)
Gy =  0
(2.11)
1 0 −1
−1 −2 −1
Sobel-Operator zur Berechnung der Gradienten in horizontaler und vertikaler Richtung
2.3 Hough-Transformation für Kreise
Richard Duda und Peter Hart evaluierten 1972, basierend auf einem Patent von Paul Hough [Hou62],
ein Verfahren zur Detektion von beliebigen parametrisierbaren geometrischen Formen durch ein VotierVorgang in dessen Parameterraum [DH72].
Der erste Schritt ist dabei das Aufstellen einer geeigneten Formel, welche die geometrische Form
möglichst einfach und mit wenig Parametern beschreibt. Im Falle des Kreises, lässt sich die Formel für
eine zweidimensionale Ebene durch die Gleichungen in (2.12) beschreiben. Er berechnet sich demnach
aus einem Kreismittelpunkt (xM und yM ) und einem Radius (r). Für den Winkel α wird das Invervall
[0, 360) Grad angenommen, um den vollständigen Rand des Kreises abbilden zu können. Es ergeben
sich also drei zu bestimmende Parameter, welche aufgefasst als Parameterraum, einen dreidimensionalen
Raum aufspannen. Dieser Raum wird im Folgenden als Akkumulator (Sammler) bezeichnet. Initial ist
jeder Wert im Akkumulator mit Null gesetzt.
x = xM + r · cos α
y = yM + r · sin α
(2.12)
Für jeden Pixel eines Bildes wird nun angenommen, dass es sich um den Mittelpunkt eines Kreises
handelt. Damit sind bereits die Parameter xM und yM definiert. Für jeden dieser Kreismittelpunkte wird
im Anschluss für eine vorher festgelegte Menge an Radien, alle Werte nach Gleichung (2.12) mit (xM =
x, yM = y, r = ri )(ri , i ∈ N) im Akkumulator um eins erhöht. Der Pixel (x, y) votiert also für verschiedene
Radien. Nach dem Votieren zweier Pixel ergibt sich im Akkumulator die Abbildung 2.12. Jeder Pixel
erzeugt also einen Kegelmantel. Schneiden sich zwei oder mehrere solcher Kegelmantel an einem Punkt
im Akkumulator, liegt an diesem Punkt ein hoher Wert und deutet damit auf einen potentiellen Kreis hin.
Die Hough-Transformation für Kreise ist ein robustes aber zeitintensives Verfahren. Vor jedem Detektionsschritt muss der gesamte Akkumulator reinitialisiert werden. Zudem votiert jeder Punkt für eine
unter Umständen große Zahl an Radien, dessen Kreisränder durch Formel (2.12) oder Approximationen,
berechnet werden müssen. Um den Aufwand größtmöglich einzuschränken, wird die Methode nicht auf
dem Bild direkt angewendet, sondern appliziert im ersten Schritt zunächst eine Kantendetektion, wie
z.B. den Sobel-Operator aus Kapitel 2.2. Ein Schwellwertfilter kann auch hier für eine Verminderung der
Informationsmenge dienen. Schlussendlich begrenzt sich die Anzahl der zu prüfenden Pixel nur noch auf
die Kanten des Bildes.
Es existieren weitere Methoden die Performance der Hough-Transformation für Kreise zu steigern.
Zum Beispiel ist es möglich anhand der Gradienten des Kantenbilds eine Vorhersage über den Kreismittelpunkt zu treffen. So muss im Akkumulator nicht der vollständige Kreis abgebildet werden.
15
2 Grundlagen
r
Ps
x
P1=(x1,y1)
P2=(x2,y2)
y
Abb. 2.12: Hough-Transformation für Kreise: Die Punkte P1 und P2 als Kreismittelpunkte votieren für
eine Menge an Radien (hier: r = (0, ∞)). Schnittpunkte der erzeugten Kegelmantel weisen auf
potentielle Kreise hin. Die Parameter des gefundenen Kreises ergeben sich aus den Koordinaten des
Schnittpunktes (Ps ). In Anlehnung an [Höf08, Doh12]
16
2 Grundlagen
2.4 Verwandte Arbeiten
Aufgrund der stetigen Anpassung der RoboCup Regeln an die originalen FIFA-Regeln werden seit einiger Zeit Methoden zu farbloser, bzw. formbasierter Ballerkennung entwickelt und präsentiert. Aber auch
abseits der RoboCup-Domäne werden für viele Bereiche formbasierte Ball- oder Kreiserkennungen benötigt. Auf einige dieser vorgeschlagenen Methoden soll in diesem Abschnitt eingegangen werden, da
sie auch für diese Ausarbeitung von Interesse sind.
2.4.1 RoboCup-Domäne
Auf Basis von Farben
Aufgrund des bisherigen RoboCup-Reglements ist die Ballerkennung aller Kid-Size-Teams auf der Farbe
basierend. Dafür sprachen bisher die einfache Umsetzung des Algorithmus, die gute Performance und
natürlich die gleichbleibende Farbe des Balls. Auch die Berlin United - FUmanoids besitzen seit jeher
eine farbbasierte Ballerkennung. Eine Zeit lang wurden die Farben des Feldes manuell mit Hilfe eines
Programms kalibriert [Gui07]. Seifert führte später eine automatisierte Methode der Farbkalibrierung
ein [Sei10], welche jedoch auf Grund wechselnder Kameras, durch fortschreitende Weiterentwicklung
der Roboter, nicht adaptiv genug gewesen ist sich schnell auf veränderte Parameter einzustellen und sich
so nicht auf Dauer etablieren konnte. Zuletzt führte Dohrmann die vollständig kalibrierfreie Vision ein,
welche die Klassifikation der Farben während des Spiels ausführt (siehe Kapitel 2.1.1). Diese Methode
wurde nun mit guten Ergebnissen unter anderem während des offiziellen RoboCup 2012 in Mexiko
verwendet.
Auf Basis von Helligkeitsunterschieden
Im vorherigen Abschnitt 2.1.2 wurde bereits eine Art der formbasierten Ballerkennung auf Grundlage
von Helligkeitsunterschieden beschrieben. Treptow, Masselli und Zell adaptierten dafür die Methode zur
Objektdetektion von Viola und Jones [TMZ03, VJ01]. Dafür wurden vier verschiedene Haar-like Features (siehe Abbildung 2.13) als Basis verwendet, welche durch ein Integralbild (siehe Kapitel 3.3.2)
jeweils in konstanter Zeit berechnet werden können. Durch Skalierung und Verschiebung der einzelnen
Features auf den Trainingsdaten wurde die bestmögliche Kombination bestimmt, welche im Anschluss
den Ball-Klassifikator bilden. Dieser Klassifikator wurde durch Verwendung des Adaboost-Algorithmus
[FS95] auf einer Testmenge von Bildern automatisch antrainiert. Der Adaboost-Algorithmus ist ein Verfahren, welches aus vielen schwachen Klassifikatoren2 die Besten anhand einer Trainingsdatenmenge
auswählt und sie linear zu einem starken Klassifikator3 kombiniert.
Der gebildete Klassifikator zur Erkennung des Balls, bestand im Anschluss aus 137 schwachen Klassifikatoren [TMZ03, Seite 3] und benötigt nach eigenen Angaben etwa 35ms4 bei einer Bildauflösung von
320x240 Pixeln. Da das verwendete System, mehr Rechenleistung als die der Berlin United - FUmanoids
Roboter bietet und das Bild vier mal kleiner ist, ist dieses Verfahren als zu rechenaufwändig anzusehen.
2 Schwache
Klassifikatoren haben eine Erkennungsrate schlechter als 100% und besser als 50%.
resultierende starke Klassifikator hat eine bessere Erkennungsrate als der beste schwache Klassifikator aus denen er
gebildet wird. Er muss keine 100% erreichen.
4 Bei 35ms kann die Klassifikation b 1000ms c = 28 mal pro Sekunde ausgeführt werden. 15 mal pro Sekunde wären bereits
35ms
ausreichend für eine flüssige Erkennung.
3 Der
17
2 Grundlagen
Abb. 2.13: Vier verschiedene Kombinationen von Hell-Dunkel-Flächen (Haar-like Features),
entnommen aus [TMZ03, Abbildung 1]
Ein größerer Nachteil ist jedoch, dass der trainierte Klassifikator nur bei einer begrenzten Menge an
verschiedenen Bällen funktioniert. Ein schwarzer Ball z.B. hätte eine invertierte Helligkeitsverteilung zu
dem getesteten Ball, die trainierten Haar-like Feature-Klassifikatoren wären darauf nicht angepasst. Man
bräuchte demnach also für verschiedene Bälle verschiedene Klassifikatoren, welche die Laufzeit und die
Wahrscheinlichkeit einer Falsch-Klassifizierungen erhöhen.
Auf Basis von Kanten
Eine Methode die Kanten eines Bildes als Grundlage zur Detektion von Bällen zu verwenden ist von
Coath und Musumeci vorgeschlagen worden [CM03]. Die Kernidee ist dabei sogenanntes Arc-Fitting
(Kreisbogen-Anpassung). Dabei wird versucht den kreisförmigen Kantenverlauf eines Balls durch eine
Menge von zweidimensionalen Punkten bestmöglich anzugleichen (siehe Abbildung 2.14). Dabei wird
im Bild oder innerhalb einer Region nach einem Gradient mit großer Magnitude gesucht. Ist dieser gefunden gibt die Inverse des Tangens die Richtung an, welche zum Kreismittelpunkt oder vom Kreismittelpunkt weg zeigt. Es kann nun orthogonal dazu nach einem weiteren Gradienten mit großer Magnitude
gesucht werden. Dabei wird die Suche innerhalb eines festgelegten Radius eingegrenzt, um möglichst
eine zum Ball zugehörige Kante zu finden. Um eine möglichst genaue Aussage treffen zu können, ob
es sich um einen Ball handelt, werden mindestens drei, besser mehr, solcher Punkte bestimmt. Durch
paarweises verbinden der Punkte zu Linien, lassen sich aus den Orthogonalen die Schnittpunkte bestimmen, welche auf einen Kreismittelpunkt hindeuten können (siehe Abbildung 2.15). Handelt es sich bei
der gefundenen Kante um einen Kreis liegen alle bestimmten Schnittpunkte nahe beieinander. Durch den
mittleren Abstand zwischen Schnittpunkt und Punkten, kann abschließend die Größe berechnet werden.
Coath und Musumeci beschreiben in ihrer Ausarbeitung leider keine Ansätze wie das Bild intelligent
nach Kreisen durchsucht werden kann. Ohne Hypothesen, wo sich ein Ball im Bild befinden kann, ist es
sehr Wahrscheinlich eine große Menge an Kreisförmigen Objekten zu detektieren. Dies ist aber ebenso
ein Vorteil der vorgeschlagenen Methode. Der Algorithmus ist auch in der Lage unvollständige Kreise
und Bälle, also auch jene Bälle die teilweise verdeckt sind, zu erkennen. In Kapitel 3.3.4 wird diese
Methode näher betrachtet und für eine Verbesserung der Größenabschätzung des Balls herangezogen.
Auf Basis von Hough-Transformation
Die vorgestellte Form der Hough-Transformation für Kreise in Kapitel 2.3, wird in dieser oder ähnlicher
Weise häufig in der Literatur zur Detektion von Kreisen oder Bällen angewendet. Eine interessante Ausarbeitung zur Detektion von Bällen im RoboCup Kontext wurde von Höferlin erstellt [Höf08]. In dieser
18
2 Grundlagen
Ballkante
Gefundener
Gradient mit Richtung
Suchregion nach
nächstem Gradient
Schnittpunkt
Orthogonalen
Abb. 2.14: Arc-Fitting: Bestimmen von
Punkten auf dem Kreisbogen (nach [CM03,
Abbildung 5])
Abb. 2.15: Arc-Fitting: Bestimmen des
potentiellen Kreismittelpunktes durch
Schnittpunkte
vergleicht er verschiedene Arten von Hough-Transformationen für Kreise und kommt zum Schluss, dass
sich die Standard Variante am besten eignet [Höf08, Seite 100]. Hoeferlin verwendet für die Detektion
nicht ausschließlich die Hough-Transformation, sondern setzt als zweiten nachträglichen Schritt noch
eine Klassifikation über Farbverteilungen ein. Der Ball muss dafür initial mehrere Sekunden im Zentrum
des Kamerabildes liegen und gut sichtbar sein. In dieser Zeit wird durch die Hough-Transformation der
Ball zunächst bestmöglich detektiert. Im Anschluss werden über diesen Bereich die Farbinformationen
extrahiert und gespeichert. Für künftige Detektionen des gleichen Balls kann so sichergestellt werden,
dass falsch erkannte Bälle anhand der Farbe aussortiert werden können.
2.4.2 Fremde Domänen
Außerhalb der RoboCup Domäne gibt es vor allem eine Vielzahl an Evaluationen zu Kreisdetektionsalgorithmen wie die Hough-Transformation. Anwendungsfälle sind hier z.B. die Erkennung von Verkehrsschildern [BCMM08] oder das Erkennen von Bällen in anderen Sportarten wie z.B. Cricket [VK10]. In
den meisten Fällen sind vorgestellte domänenspezifische Methoden stark abhängig von Umgebung und
verwendeten Kameras und damit nur bedingt auf die RoboCup Domäne übertragbar.
19
3 Formbasierte Ballerkennung
Wie aus den Grundlagen ersichtlich, kann ein Objekt auf viele verschiedene Arten anhand seiner Form
oder zumindest farblos detektiert werden. Die in der Dissertation von Moballegh vorgestellte Methode zur Ballerkennung ist eine gänzlich neue und vielversprechende Idee und wurde zur Evaluation in
dieser Arbeit aufgegriffen. Sie basiert im Wesentlichen auf den Ideen zweier Arbeiten von [DT05] und
[VJ01]. Im folgenden Kapitel dieser Arbeit wird dieser Konzeptvorschlag nicht nur präsentiert, sondern
zusätzlich versucht zu verbessern.
3.1 Anforderungen
Neben der sich selbsterklärenden Anforderung den Ball zu erkennen, ist es ebenso relevant keine falschen
Bälle zu erkennen. Falsche Klassifizierungen führen dazu, dass der Roboter in eine falsche Richtung
läuft. Dies kann vor allem dann schmerzhaft sein, wenn der Ball auf der Torlinie liegt und der Roboter im
letzten Moment abdreht und versucht den Torpfosten zu treten. Vor allem wenn die Falschklassifikation
über mehrere Bilder oder sogar Sekunden anhält, ist der Roboter unter Umständen vollständig aus dem
Spielgeschehen ausgeschieden.
3.1.1 Universalität
Aufgrund der Tatsache, dass Farbe und Muster des Balls in der Technical Challenge zufällig sind und
keine genaue Aussage darüber getroffen werden kann, welchen Farbton der grüne Boden, oder unter
welchen Lichtverhältnissen gespielt wird, gibt es eine Vielzahl von Farbkombinationen aus Ball und
Hintergrund. Zusätzlich liegt der Ball nicht immer nur auf grüner Fläche, sondern kann auch auf einer
weißen Feldlinie oder vor einem Gegner liegen. Alle diese Kombinationen sollten im Idealfall zu einer
guten Erkennungsrate führen. Ob dieser Idealfall erreichbar ist, liegt jedoch nicht nur an der Software,
sondern auch an der verwendeten Kamera, die hauptsächlich über die Qualität des Bildes entscheidet.
Sind auftretende Störungen wie Rauschen zu häufig oder zu stark vertreten, ist eine gute Detektion demnach erschwert.
Die Technical Challenge bietet eine sehr statische Umgebung, in der sich keine bewegende Gegner
befinden. Dies impliziert, dass auch der Ball nicht durch fremde Einwirkung bewegt wird. Weiterhin
besagen die Regeln der Challenge, dass der Ball zum Start in etwa 1m Entfernung zum Roboter platziert
wird. Zusammen mit dem Wissen, dass der Ball nur durch den eigenen Roboter bewegt wird und er
gedribbelt werden muss, kann die Annahme getroffen werden, dass sich der Ball nie weiter als 3 m1 vom
Roboter entfernt.
16
m ist die Distanz zwischen beiden Toren auf dem Spielfeld
20
Der entworfene Algorithmus sollte letztendlich unter den verschiedensten Bedingungen eine ausreichend gute Erkennungsrate besitzen. Das bedeutet, der Ball sollte zumindest in jedem zweiten Bild erkannt werden, damit fortwährend eine gute Abschätzung über die Position des Balls gemacht werden
kann.
3.1.2 Qualität
Zur Detektion des Balls soll der Algorithmus nicht nur die Aussage treffen, ob ein Ball im Bild existiert
oder nicht, sondern auch wo im Bild er sich befindet. Diese Information ist für den weiteren Verlauf
des Verhaltens der künstlichen Intelligenz sehr wichtig. Bestimmt der Algorithmus den Ort des Balls im
Bild zu ungenau, kann dies in der anschließenden Berechnung seiner Weltkoordinaten zu einem nicht zu
vernachlässigenden Fehler führen. Liegt der erkannte Ball 30 cm näher an den Füßen des Roboters als
der tatsächliche Ball wird der Roboter ihn an dieser Position ohne Erfolg versuchen zu treten.
Die zweite Anforderung ist demnach eine gute Positionsermittlung des Balls im Bild.
3.1.3 Performance
Neben einer guten Erkennungsrate ist auch die Rechenintensität ein wichtiger Faktor. Da die Ressourcen des verwendeten Systems stark begrenzt sind, darf der Algorithmus nicht beliebig komplex sein.
Der bisher von den Berlin United - FUmanoids eingesetzte Algorithmus zur Balldetektion benötigt laut
Dohrmann im Mittel nur 1 ms. Die durchschnittliche Frequenz der gesamten Bildbearbeitung beläuft
sich auf etwa 10-15 Bilder pro Sekunde.
Die statische Umgebung der Technical Challenge ermöglicht auch hier die Anforderung abzuschwächen. Da der Roboter relativ viel Zeit hat, den Ball ins Tor zu Dribbeln und nicht im direkten Wettstreit
mit Gegnern auf dem Feld ist, kann die Laufzeit der Ballerkennung großzügiger ausfallen. Anzustreben
sind mindestens 10 ausgewertete Bilder pro Sekunde. Weniger Bilder pro Sekunde würden sich negativ
auf die Qualität der Auswertung der restlichen Software auswirken.
Trotz der vereinfachten Anforderungen durch die Challenge, sollte der Nutzen für die Zukunft nicht
außer acht gelassen werden. In absehbarer Zeit ist es wahrscheinlich, dass die RoboCup-Wettkämpfe der
Kid-Size-Liga standardmäßig mit einem Ball beliebiger Farbe ausgetragen werden. Bis dahin wird die
Stärke des Prozessors und des restlichen Systems der Berlin United - FUmanoids zugenommen haben
und so den Einsatz einer komplexen formbasierten Erkennung verträglich machen.
3.2 Konzept
Basierend auf dem Wissen zu Gradienten lässt sich die Basis-Idee der Ballerkennung relativ einfach
beschreiben. Sie basiert auf der Annahme, dass alle Gradientenrichtungen zwischen 0 und 360 Grad
gleichverteilt in der Kante des Balls vorkommen. Anschaulich ist dies in Abbildung 3.1 dargestellt. In
dieser sind die durch Kantendetektion erzeugten Gradienten durch Pfeile dargestellt. Je nach Farbe des
Balls können die Gradienten dabei vom oder zum Kreismittelpunkt zeigen.
Auf Basis dieser Annahme lässt sich nun im Bild nach Bereichen suchen, in welchen alle Gradientenrichtungen vorkommen (im folgenden als Hypothesen bezeichnet). Aufgrund von starkem Rauschen
21
Ballkante
Gradient
Abb. 3.1: Schematische Darstellung von
Gradienten am Rand eines Kreises
Abb. 3.2: Schematischer Ablauf der
formbasierten Ballerkennung
oder komplexen Strukturen findet diese Vorgehensweise aber nicht nur kreisförmige Objekte. Im gesamten Bild z.B., kommen in so gut wie jedem Fall alle Gradientenrichtungen vor. Es ist daher wichtig diese
Hypothesen zusätzlich noch zu verifizieren.
Zusammenfassend, lässt sich das Konzept in drei große Bereiche aufteilen (siehe Abbildung 3.2).
Welche Anforderungen die einzelnen Bereiche zu erfüllen haben und wie sie erreicht werden können,
wird in den nachfolgenden Abschnitten erläutert.
3.2.1 Kantendetektion
Die bisher besprochene Kantendetektion wurde auf Graubildern angewendet. Da es in Graubildern jedoch dazu kommen kann, dass zwei verschiedene Farbtöne zu dem gleichen Grauton konvertiert werden
(siehe Abbildung 3.3), muss für die Kantendetektion der formbasierten Ballerkennung auch die Farbe
mit einbezogen werden. Dies macht Sinn, wenn die Farbe des eingesetzten Balls zum gleichen Grauton
umgerechnet und die Kantendetektion keine Kanten erkennen würde.
Um nun also die Kanten im Farbbild zu erkennen, wird das Bild in seine Komponenten zerlegt (z.B.
YCbCr in Y, Cb und Cr) und der Kantendetektions-Operator auf jede Komponente einzeln angewendet. Der Gradient an Position (x, y) ergibt sich dann aus dem Gradienten mit der größten Magnitude
MAX(mag(GY ), mag(GCb ), mag(GCr ).
Um die Ausrichtung eines Gradienten zu bestimmen eignet sich die Inverse des Tangens nicht, da
diese nur auf dem Intervall ] − π2 , π2 [ definiert ist. Für diesen Anwendungsfall wird jedoch das Intervall
] − π, π2 ] benötigt. Es eignet sich dafür die Verwendung des Arkustangens mit zwei Argumenten (3.1).

y
arctan
f alls x > 0

x

 arctan y + π f alls x < 0 ∧ y ≥ 0


x


arctan xy − π f alls x < 0 ∧ y < 0
atan2(y, x) =
(3.1)
+ π2
f alls x = 0 ∧ y > 0





−π
f alls x = 0 ∧ y < 0

 2
unde f iniert
x = 0∧y = 0
22
(a)
(b)
Abb. 3.3: Verlust von Farbinformation bei der Konvertierung von Farbwert zu Grauwert
3.2.2 Hypothesensuche
Die Hypothesensuche sollte Teilbilder mit tatsächlichen Bälle nicht ausschließen, gleichzeitig jedoch
möglichst alle Teilbildern ohne Bälle eliminieren. Weiterhin sollten die Größen der Teilbild-Hypothesen
nahe an den realen Ausmaßen des beinhaltenden Balls liegen.
Es ist nun zu klären, wie intelligent nach Hypothesen gesucht werden kann. Die Suche nach Teilbildern, in denen alle Gradientenrichtungen vorkommen, gestaltet sich ohne Diskretisierung als schwierig,
da die Funktion atan2(y, x) in den reellen Zahlenraum abbildet. Unter der Annahme, dass Kamerabild ist
ebenso aus R, gäbe es sogar überabzählbar viele Richtungen. Die Lösung ist hier das Diskretisieren in
eine feste Anzahl an Schubfächern. Alle Gradienten eines Teilbilds sollen entsprechend ihres Winkels in
ihr zugehöriges Schubfach einsortiert werden. Sind alle Schubfächer mit mindestens einem Gradienten
gefüllt, so kann potentiell davon ausgegangen werden, dass in diesem Teilbild ein kreisförmiges Objekt
vorhanden ist. Diese These ist nachfolgend weiter zu untersuchen: wird z.B. das Intervall [0,360) in vier
gleichgroße Schubfächer geteilt, würde das Prüfen der Schubfächer also nur eine Antwort auf die Frage
geben, ob Gradienten in jeden Quadranten zeigen. In diesem Fall würden aber auch andere Formen wie
Rechtecke oder Kreuze akzeptiert werden (siehe Abbildung 3.5a). Das Erhöhen der Schubfach-Anzahl
vermindert diese ungewollten Fälle (siehe Abbildung 3.5b). Hier würde das umschließende Teilbild verworfen werden, da nicht alle Fächer gefüllt sind. Moballegh verwendet in seiner Ausarbeitung 18 Fächer
und minimiert damit noch weiter die Chance, falsche Hypothesen aufzustellen. Beliebiges erhöhen der
Fächeranzahl ist nicht ratsam, da sich im Kapitel 3.3.2 zeigen wird, dass das Berechnen bereits mit 18
Fächern sehr teuer ist.
In der Praxis wird nun jeder Gradient eines Teilbilds in die Schubfächer einsortiert. Es entsteht ein
Vektor von Klassen und deren Häufigkeiten. Dieser wird als Histogramm bezeichnet. Die Aussagekraft
dieser Histogramme zeigt sich in der Abbildung 3.4. Hier sind mehrere Teilbilder und deren Histogramme aufgetragen. Es zeigt sich, dass in Teilbildern ohne Ball mehrere Histogrammkomponenten 0 oder
sehr klein sind, sodass hier ein Tal entsteht. Weiterhin ist auch zu erkennen, dass verdeckte Bälle ebenso
zu leeren Komponenten führen. Dies ist ein wesentliches Problem dieser Methode. Besondere Beachtung
wird diesem jedoch erst im weiteren Verlauf dieser Arbeit zuteil.
Im nächsten Schritt ist ein Verfahren zu finden, welches mit Hilfe der Histogrammbildung das Kame-
23
0.2
0.2
0.15
0.15
0.12
0.1
0.08
0.1
0.1
0.05
0.05
0.06
0.04
0.02
0
0
-180
-160
-140
-120
-100
-80
-60
-40
-20
0
20
40
60
80
100
120
140
160
0
-180
-160
-140
-120
-100
-80
-60
-40
(a)
-20
0
20
40
60
80
100
120
140
160
-180
-160
-140
-120
-100
-80
-60
-40
(b)
0.5
-20
0
20
40
60
80
100
120
140
160
20
40
60
80
100
120
140
160
(c)
0.16
0.2
0.14
0.4
0.12
0.15
0.1
0.3
0.08
0.1
0.2
0.06
0.04
0.05
0.1
0.02
0
-180
-160
-140
-120
-100
-80
-60
-40
-20
0
20
40
60
80
100
120
140
0
160
0
-180
(d)
-160
-140
-120
-100
-80
-60
-40
-20
0
20
40
60
80
100
120
140
160
-180
-160
-140
-120
-100
-80
-60
-40
(e)
-20
0
(f)
Abb. 3.4: Beispiel-Teilbilder und ihre zugehörigen Histogramme der Gradientenrichtungen
Gradient
1
0-89°
1
Gradient
Kante
1
1
0
90-179° 180-269° 270-359°
0-44°
1
45-89°
0
Kante
1 0
1 0
Schubfächer
Schubfächer
(a) 4 Schubfächer
(b) 8 Schubfächer
Abb. 3.5: Zuordnen von Gradientenrichtung in Schubfächer
24
1
90-134° 135-179° 180-224° 225-269°270-314°315-359°
Level 0
9
7
Level 1
8
6
Teilbilder
5
3
Level n
1
Lv. 1
4
5
2
2
8
(a) Rekursive Suche mit 4
Kindern
(b) Rekursive Suche mit 9
Kindern (nach [Mob11,
Abbildung 11.13b])
Lv. 1
1
2
7
(c) Redundanter Fall. Hier:
Teilbild mit Nummer 7 und 8 sind
identisch
Abb. 3.6: Überlappende rekursive Suche
rabild geeignet durchsucht. Moballegh schlägt hier eine rekursive Suche auf dem Bild vor. Das gesamte
Bild wird dabei sukzessive in mehrere kleine Teilbilder unterteilt (siehe Abbildung 3.6a). Es ist nun
von Vorteil, nicht nach kreisförmigen Objekten zu suchen, sondern Teilbilder auszuschließen in denen
kein kreisförmiges Objekt vermutet wird. Dies ergibt sich aus der Tatsache, dass für die Suche nur Histogramme auf Vollständigkeit geprüft werden. Mit dem Histogramm geht ein Verlust an Information
einher, da nicht interpretiert werden kann, ob alle Gradientenrichtungen tatsächlich auf einen Kreis oder
nur auf eine Normalverteilung oder ähnliches schließen. Um auch Fälle wie teilweise verdeckte Bälle
oder nicht vollständig erkennbare Kanten abzudecken, wird das Kriterium vollständiger Histogramme
abgeschwächt, sodass eine festgelegte Anzahl an Schubfächern mit weniger als z.B. 5 Einträgen toleriert
werden.
Ein Problem der rekursiven Suche ist in dieser einfachen Form, dass jedes Bild nur in 4 Teilbilder
aufgeteilt wird. Dabei kann es dazu kommen, dass der Ball auf den Rändern dieser Teilbilder liegt und
somit von keinem Teilbild ganz eingeschlossen ist. Abbildung 3.6a stellt diese Problematik dar. In diesem
Fall schließt zwar noch die darüber liegende Teilbildebene den Ball voll ein, die Anforderung an eine gute
Größenabschätzung des Balls wäre aber nur schwach erfüllt. Moballegh schlägt daher eine Suche mit 9
Teilbildern vor (siehe Abbildung 3.6b). Auf diese Weise wird ein Einschließen des Balls sichergestellt
und die kleinstmögliche Größe einer Hypothese hat sich halbiert.
Es lässt sich nun ein Algorithmus für die Hypothesensuche aufstellen. Rekursionsanker ist neben
dem Prüfen des Histogramms auch eine maximale Tiefe. Bei einer Tiefe größer als 5 ist ein Teilbild
bereits 10x7 Pixel groß und so klein, dass ein Ball in dieser Größe nicht mehr erkennbar wäre. Dies liegt
vor allem daran, dass in dieser Größe nicht zwingend alle Gradientenrichtungen vorkommen. Rauschen
bewirkt einen sehr großen Fehler in diesen Dimensionen. Eine weitere Abbruchbedingung ergibt sich
aus der Tatsache, dass die Rekursion ein Teilbild unter Umständen mehr als einmal untersucht (siehe
Abbildung 3.6c). Dies basiert auf dem Überlappen der Teilbilder und lässt sich durch eine LookupTabelle vermeiden. Zu Beginn jedes Funktionsaufrufs muss also getestet werden, ob das Teilbild schon
überprüft wurde.
Ist keine der Abbruchbedingungen gültig, wird für jedes der 9 erzeugten Teilbilder die rekursive Funktion erneut aufgerufen. Ein Teilbild wird als Ballkandidat akzeptiert, wenn alle seine Kinder Blätter sind
und somit abgelehnt wurden. Wird ein Teilbild zum zweiten Mal überprüft, so wird durch die LookupTabelle verhindert, dass das Eltern-Teilbild in den Kandidatenpool aufgenommen wird. Es wird davon
ausgegangen, dass dieses Teilbild bereits bearbeitet wurde. Diese Vorgehensweise birgt jedoch ein Pro-
25
blem in bestimmten Fällen. Näheres dazu im Kapitel 3.3.3.
Algorithmus 1: Überlappende Rekursive Suche
1 b o o l e a n o v e r l a p p i n g S e a r c h ( window , l e v e l )
2 begin
3
i f window i s a l r e a y s c a n n e d t h e n
4
return true
5
6
window <− s c a n n e d
7
8
i f l e v e l > 5 then
9
return f a l s e
10
11
h i s t o g r a m <− c a l c u l a t e H i s t o g r a m ( window )
12
13
i f h i s t o g r a m h a s a t l e a s t one z e r o component t h e n
14
return f a l s e
15
16
b <− f a l s e
17
18
f o r a l l 9 s u b windows
19
b <− b or o v e r l a p p i n g S e a r c h ( s u b window , l e v e l + 1 )
20
21
i f not b t h e n
22
p u s h _ b a l l _ c a n d i d a t e ( window )
23 end
3.2.3 Verifizierung
Der an dieser Stelle erzeugte Kandidatenpool muss auf Grund der schon erläuterten Fälle weiter verifiziert werden. Ziel ist es demnach alle realen Bälle als solche zu verifizieren und die restlichen Kandidaten
abzulehnen. Als Basis sollen dafür möglichst nur die bereits erzeugten Histogramme sein, um die Rechenintensivität zu minimieren. Zugriffe auf das Bild sollten vermieden werden, da sie je nach Größe der
Teilbilder und damit mit steigender Anzahl zu prüfender Pixel sehr rechenintensiv werden.
Da Histogramme keine genaue Auskunft über Position und Anordnung der einzelnen Gradienten geben, können sie weder Position des Balls noch deren Durchmesser bestimmen. Um mit Hilfe der Histogramme ein Teilbild nun aber dennoch verifizieren zu können, bedient sich Moballegh zweier Beobachtungen.
Kriterium 1
Die erste Beobachtung basiert auf der Tatsache, dass alle Gradientenrichtungen um einen Kreis gleich
häufig auftreten (siehe z.B. Abbildung 3.1). Es ist demnach ein Maß für die Gleichverteilung eines Histogramms zu finden. Betrachtet man die Gaußverteilung verschiedener Histogramme, so lässt sich feststellen, dass eine perfekte Gleichverteilung eine hohe Standardabweichung bedeutet (siehe Abbildung 3.7a).
Eine Normalverteilung hingegen, besitzt eine geringe Standardabweichung (siehe Abbildung 3.7b). Auf
Basis dieser Beobachtung schlägt Moballegh nun eine Ungleichung aus Mittelwert und Standardabweichung vor (siehe (3.2)). Alpha ist ein empirisch zu bestimmender Schwellwert, welcher die Akzeptanz
26
Histogramm aus Abbildung
Gauß-Funktion
Ball
3.7a
3.7b
3.7c
N (170, 1042 )
N (161, 482 )
N (166, 882 )
Ja
Nein
Ja
Größtes α für wahre Aussage
b σµ c
0.61
0.29
0.53
Tabelle 3.1: Übersicht über den kleinst anzunehmenden Schwellwert α, um ein Histogramm als Ball zu
bewerten
0.06
0.35
0.25
0.3
0.05
0.2
0.25
0.04
0.15
0.2
0.03
0.15
0.1
0.02
0.1
0.05
0.01
0.05
0
0
-180
-160
-140
-120
-100
-80
-60
-40
-20
0
20
40
60
80
100
120
140
160
(a) Gleichverteilung und
N (−10, 1042 )
0
-180
-160
-140
-120
-100
-80
-60
-40
-20
0
20
40
60
80
100
120
140
160
(b) Annähernde Normalverteilung
und N (−21, 482 )
-180
-160
-140
-120
-100
-80
-60
-40
-20
0
20
40
60
80
100
120
140
160
(c) Annähernde Gleichverteilung
mit 4 Ausreißern und
N (−14, 882 )
Abb. 3.7: Beispielhistogramme und deren Gaußfunktionen N (µ, σ 2 ). Die Summe der y-Werte ist auf 1
normiert, die Gaußglocke zur besseren Übersicht vertikal skaliert.
beeinflusst. Ein hoher Schwellwert bedeutet demnach eine hohe Akzeptanz. Damit die Formel für die
Beispiele aus Abbildung 3.7 funktioniert, muss der Mittelwert µ um den Wert 180 verschoben werden.
Der Schwellwert α lässt sich anhand der Beispielhistogramme bestimmen. Dafür sollen Histogramm
3.7a und 3.7c als Ball akzeptiert werden, 3.7b jedoch nicht. Durch Bestimmen des kleinsten α für jedes
Histogramm lässt sich betrachten, in welchen Dimensionen der endgültige Schwellwert anzulegen ist
(siehe Tabelle 3.1). Basierend auf diesen Werten, sollte der Schwellwert α zumindest größer als 0.30
sein, um eine Normalverteilung auzuschließen. In der Praxis hat sich ein Wert von 0.50 als gut erwiesen.
µ:
σ:
α:
Mittelwert des Histogramms
Standardabweichung des Histogramms
Schwellwert
σ < αµ
(3.2)
Kriterium 2
Des weiteren lässt sich feststellen, dass innerhalb eines Teilbilds nur eine bestimmte Größe an Bällen auftreten kann. Die obere Grenze ist hier die kleinste Seite des Teilbildes, da dies der maximale
Durchmesser ist, den ein Kreis in diesem Teilbild einnehmen kann ohne dass die Histogrammanalyse
27
fehlschlägt. Die untere Grenze ist die kleinste Seite halbiert, da jedes Teilbild gegenüber seinem ElternTeilbild eine halbierte Breite und eine halbierte Höhe besitzt. Auf Basis dieser zweiten Beobachtung
und der Information, dass jede Kante nur 1 Pixel breit ist, muss die Anzahl der Gradienten in einem
Teilbild also mit seinem Umfang korrelieren. Moballegh stellt demnach die Bedingung (3.3) auf, die ein
Histogramm zu erfüllen hat, um als Ball akzeptiert zu werden. Als Schwellwert eignet sich auch hier
eine empirische Bestimmung. β sollte jedoch nicht größer als 0.5 sein, damit nicht auch zu kleine Bälle
akzeptiert werden.
d:
n:
β:
Länge der kleinsten Seite des Teilbildes
Anzahl an Gradienten im Teilbild
Schwellwert
π
d(1 − β ) < n < 4d(1 + β )
2
(3.3)
3.3 Optimierung
Das erläuterte Kozept der formbasierten Ballerkennung, soll in diesem Kapitel näher auf die Anforderungen untersucht werden. Dafür werden Kantenbild, Hypothesensuche und Verifizierung auf ihre Qualität
untersucht und versucht, jeden Schritt bestmöglich zu optimieren.
3.3.1 Optimieren der Kantendetektion
Um möglichst gute Hypothesen aus dem Bild extrahieren zu können ist ein gutes Gradientenbild die
nötige Basis. Je besser die Qualität der Kanten, desto einfacher ist es für die Hypothesensuche gute
Entscheidungen treffen zu können.
In den Grundlagen wurden bereits einige wichtigen Aspekte der Kantendetektion erläutert. Neben
diesen postulierte John Canny in seiner Abhandlung zur Kantendetektion drei Kriterien für eine optimale
Detektion [Can86, Seite 680]:
1. Gute Erkennung - Die Kantendetektion sollte möglichst alle, tatsächlich im Bild vorhandene, Kanten finden.
2. Gute Lokalisierung - Die gefundenen Kanten sollten möglichst mittig in den realen Kanten verlaufen.
3. Minimale Kantendicke - Die gefundenen Kanten sollten nur ein Pixel breit sein und nicht mehrmals
gefunden werden.
Diese Kriterien sollen auch für die formbasierte Ballerkennung erfüllt werden. Es ist daher zu untersuchen, welche Schritte vor der Kantendetektion geeignet sind um das Kamerabild in Hinsicht der Deutlichkeit der Kanten zu verbessern. Weiterhin ist zu untersuchen, welcher Kantendetektions-Operator in
Hinsicht auf Performance und Qualität die besten Eigenschaften bietet und wie eine Minimierung der
Kantenbreite erreicht werden kann.
28
Vorverarbeitung des Kamerabilds
Das Kamerabild sollte möglichst von jeglichen Störungen befreit sein und zusätzlich sollten alle wichtigen Kanten erhalten bleiben. Selbstverständlich sollte auch hier die Verarbeitung in so geringer Zeit wie
möglich geschehen. Neben der Glättung mit dem Gauß-Filter eignet sich auch der sogenannte MedianFilter2 . Gegeben eine Fenstergröße, z.B. 3x3, sortiert der Median-Filter alle Werte innerhalb dieses Fensters und belegt den Wert in der Mitte des Fensters mit dem Median. Für ein vollständiges Bild, wird das
Fenster über jeden Pixel iteriert. Das dadurch gefilterte Bild besitzt je nach Größe des Fensters eine
besonders gute Rauschunterdrückung und erhält zusätzlich die Kanten und verbessert sogar noch den
Kontrast. Eine mit dem Median-Filter gefilterte Bilderreihe ist in Abbildung 3.8 aufgeführt. Wird nun
im Anschluss noch ein Sobel-Operator angewendet, zeigt sich die Stärke des Filters. Besonders interessant ist das Ergebnis mit einer 15x15 Fenstergröße 3.8d, bei welchem die Kanten beider Bälle sehr gut
konserviert und dabei Auswirkungen von Schatten stark vermindert sind. Zusätzlich werden sehr kleine
Strukturen wie auch dünne Linien vollständig eliminiert, was zu einer stark vereinfachten Hypothesensuche führt.
Aufgrund der Sortierung, welche für jeden Pixel des Bildes ausgeführt werden muss, ist die Komplexität des Median-Filters relativ hoch. Die Laufzeit ist fast vollständig vom verwendeten Sortierverfahren
abhängig. Mit einem linearen Sortierverfahren ist die Komplexität für jeden Pixel immer noch O(n · m),
bei quadratischem Fenster also O(n2 ). Wie in der Abbildungsreihe 3.8 ersichtlich, ist ein großes Fenster von Vorteil, um ein gutes Kantenbild erzeugen zu können und die Laufzeit dementsprechend hoch.
Tabelle 3.2 zeigt die Zeit, die der Median-Filter für zwei verschiedene Fenstergrößen beno"tigt. Markant ist der enorm hohe Aufwand von 56.2ms für die Medianfilterung eines RGB-Bildes von 640 mal
480 Pixelgröße. Diese Laufzeit ist bereits auf dem Testsystem nicht für die Vorverarbeitung tragbar, der
Median-Filter eignet sich demnach nicht für den Einsatz auf dem Roboter.
Alternativ eignet sich zum Filtern auch der Gauß-Filter. Die Ergebnisse mit Faltungsmatrizen der
Größe 5x5 und 15x15 sind in Abbildung 3.9 zu sehen. Im Vergleich zum Median-Filter sind viel mehr
Details zu erkennen und die Menge an Kanten dementsprechend höher. Der 5x5 Gauß-Filter eliminiert
aber zumindest fast alle unwichtigen Details auf der grünen Fläche und konserviert auch hier genügend
viele Kanten der Bälle. Nachteilig ist hier jedoch, dass die Kanten breiter sind als beim Median-Filter. Die
breite erhöht sich zusätzlich, wenn die Fahltungsmatrixgröße zunimmt. Bei einer Faltungsmatrixgröße
von 15x15 sind die Kanten breiter, dafür aber in der Menge vermindert. Zusätzlich fehlen aber bereits
einige wichtige Kanten des hinteren Balls. Trotz der Nachteile des Gauß-Filters besitzt er eine moderate,
noch vertretbare Laufzeit (siehe Tabelle 3.2). Der 5x5 Gauß-Filter eignet sich demnach zur Glättung des
Eingabebildes.
Nachbearbeitung des Kantenbilds
Bevor ein optimaler Kantendetektions-Operator bestimmt wird, soll zunächst eine Lösung für die Minimierung der Kantendicke vorgestellt werden. Diese wird im Anschluss für die Bewertung und den
Vergleich der Operatoren verwendet.
Unabhängig davon, welcher Operator verwendet wird, beinhaltet das erzeugte Kantenbild immer noch
eine große Menge an Informationen. Diese erschweren das Verifizieren der Hypothesen. Soll die Anzahl
an Pixeln in einem Teilbild gezählt werden, weil diese mit dem Umfang des Kreises korreliert, so ist es
2 Der
Median ist der mittlere Wert einer sortierten Datenmenge. Bei n Daten ist der Median also der Wert an Index
29
n
2
(a)
(b)
(c)
(d)
Abb. 3.8: Mit dem Median-Filter geglättete Bilder und deren Sobel-Kantenbilder nach
Schwellwertfilterung mit θ = 5. Oben: Fenstergröße 5x5. Unten: Fenstergröße 15x15
(e)
(f)
(g)
(h)
Abb. 3.9: Mit dem Gauß-Filter geglättete Bilder und deren Sobel-Kantenbilder nach
Schwellwertfilterung mit θ = 5. Oben: Faltungsmatrixgröße 5x5. Unten: Faltungsmatrixgröße 15x15
30
Filter
Median 5x5
Median 15x15
Gauß 5x5
Gauß 15x15
Ø Laufzeit in ms
4.8
56.2
1.7
6.9
Tabelle 3.2: Qualitativer Vergleich der Laufzeiten des Gauß- und des Median-Filters. (Testprozessor:
3Ghz Intel CPU)
Kantenrichtung
(Gradientenorthogonale)
125 216 238
0
0
0
0
238
37
105 212 246 199
0
0
0
246
0
82
212 239 212 125
0
0
239
0
0
37
37
212 246 212
50
37
0
246
0
0
0
227
37
37
227
0
0
0
0
76
125
(a) Ausschnitt eines Kantenbilds
mit deren Kantenrichtungen und
Magnituden
(b) Erzeugtes
Non-maxima-suppressed-Bild
(c) Endergebnis
Abb. 3.10: Applikation von Non-maxima-suppression auf einem Kantenbild
schwer eine Annahme zu treffen, da die Breite des potentiellen Kreises mehr als 1 Pixel breit ist. Zusätzlich vermindern ein Pixel breite Kanten die Wahrscheinlichkeit einer falschen Klassifizierung. Die
Minimierung der Kantendicke erfüllt Cannys geforderten Punkt 3 und je nach Umsetzung zusätzlich
Punkt 2. Um Punkt 2 zu erfüllen, muss die Kante möglichst nahe im Zentrum der ursprünglichen dicken
Kante verlaufen.
Canny schlägt dafür zwei aufeinander basierende Techniken vor, welche die stärksten Kanten aus
einem Kantenbild extrahieren und damit auf eine Breite von einem Pixel reduzieren. Die erste Technik ist
"Non-maxima-suppression"(Unterdrückung von Nicht-Maxima). Dabei wird jede Kante im Bild verfolgt
und deren lokale Maxima extrahiert. Entscheidend dafür ist die Kantenrichtung, welche sich aus der
orthogonalen der Gradientenrichtung ergibt. Trifft das Verfahren nun auf eine Kante, wird sie anhand
ihrer Kantenrichtung verfolgt. Verläuft adjazent zu der verfolgten Kante eine weitere Kante in die gleiche
Richtung, besitzt aber kleinere Gradientenmagnituden, so wird diese adjazente Kante auf 0 gesetzt (siehe
Abbildung 3.10). Im zweiten Schritt sollen nun zu schwache Kanten, ähnlich zu einem Schwellwertfilter,
eliminiert werden. Um nun aber nur Kanten zu entfernen, welche vollständig aus kleinen Magnituden
bestehen und nicht auch solche, die sich auch aus Teilen mit großen Magnituden zusammensetzen, wird
ein Hysterese-Schwellwertfilter verwendet (siehe Funktion 3.4). Dieser setzt sich aus einem unteren
31
Schwellwert θlow und einem oberen Schwellwert θhigh zusammen. Wird nun durch das Ausgabebild der
Non-maxima-suppression iteriert, so wird eine Kante mit Wert 1 akzeptiert, wenn ihre Magnitude größer
als θhigh ist. Die gefundene Kante wird nun in Kantenrichtung verfolgt. Jeder Gradient in Kantenrichtung
mit einer Magnitude größer als θlow wird ebenso mit Wert 1 akzeptiert. Erst wenn θlow unterschritten
wird, wird die verfolgte Kante mit Wert 0 beendet. Somit werden innerhalb einer starken Kante auch
Teile mit kleinen Magnituden im Ergebnis markiert.
Dieser zweite Schritt ist besonders wichtig für den Fall, dass Teile der Ballkante keine ausreichend
großen Magnituden besitzen.

0 f alls ¬onEdge ∧ mag < θlow



1 f alls onEdge ∧ mag ≥ θlow
Hysterese(mag, onEdge, θlow , θhigh , ) :=
(3.4)
1 f alls mag ≥ θhigh



0 sonst
Das von Canny vorgeschlagene Verfahren bietet ein gutes Endergebnis und eignet sich auf Grund minimal breiter Kanten gut für die Balldetektion. Ebenso ist eine gute Lokalisierung gegeben, da für die
endgültige Kante nur die Maxima einer Kante verwendet werden, welche im Allgemeinen im Kantenzentrum liegen. Wird der Hysterese-Filter für die Kantendetektion verwendet, kann das Filtern durch einen
Standard-Schwellwertfilter ausbleiben, da auch hier alle Magnituden kleiner als θlow eliminiert werden.
Das endgültige Ergebnis am Beispielbild ist in Abbildung ?? dargestellt.
Geeigneter Kantendetektions-Operator
Mit Hilfe der Kantenminimierung kann nun ein geeigneter Operator für die Kantendetektion bestimmt
werden. Sie ermöglicht es, einen Operator anhand einer Fehlerfunktion zu vergleichen. Wird ein Testsatz
von Bildern mit Bällen so annotiert, dass die vorkommenden Bälle jeweils in möglichst eng umschließenden Teilbildern liegen, ist die Größe des Balls damit bekannt und damit ebenso die optimale Anzahl
an Gradienten pro Schubfach. Diese Tatsache beruht auf dem Wissen, dass die Kante des Balls im optimalen Fall ein Pixel breit ist und dass sich die Gesamtanzahl an Gradienten durch den Umfang berechnen
lässt. Die Fehlerfunktion kann damit aufgestellt werden (siehe Gleichung (3.5)). ei unterscheidet dabei
drei Fälle: ist die Summe an Gradienten eines Schubfachs sum(Hi ) größer als die optimale Anzahl n,
so wird die Differenz aus beiden zum Gesamtfehler E hinzu addiert. Dieser Fall sollte weniger streng
bewertet werden, da überflüssige Einträge oft durch Schatten oder umgebene Muster auftreten. Ist die
Summe hingegen kleiner als n, so wird das Quadrat der Differenz zu E hinzu addiert. Ist die Summe null,
wird konstant 10 hinzu addiert. Die beiden letzten Fälle sorgen dafür, dass zu wenig Gradienten in einem
Schubfach einen hohen Fehler bewirken. Um große Bälle nicht stärker zu gewichten als kleine, wird die
Summe der Gradienten auf n normiert.
h, b:
H:
|H|:
N:
n:
Höhe h und Breite b des Teilbilds, wobei h = b
Histogramm
Anzahl Schubfächer des Histogramms
Optimale Summe an Gradienten im Teilbild
Optimale Summe an Gradienten in einem Schubfach des Histogramms
N := πb
N
n := |H|
32
|H|
E := ∑ ei
(3.5)
i=1
 sum(Hi )
i)

f alls sum(H
≥1
1
−

n
n
 2
i)
i)
ei :=
f alls 1 > sum(H
1 − sum(H
>0

n
n


10
sonst
Ziel des optimalen Kantendetektions-Operators ist es, vor allem alle Kanten von Bällen zu finden und
damit ein vollständiges und gleichverteiltes Histogramm zu induzieren. Neben der Bewertung durch die
Fehlerfunktion E, sollen zusätzlich zwei subjektive Kriterien bewertet werden:
1. Zusammenhängend: Existiert eine zusammenhängende Kante um den Ball?
2. Keine überflüssigen Kanten: Ist die Anzahl an Kanten in Regionen ohne echte Kante möglichst
gering?
Auf Basis von 52 Bildern mit beinhalteten Bällen, werden folgende drei Operatoren verglichen:
• Einfacher Operator: Aufgrund der kleinen Faltungsmatrix ist die Komplexität dieses Operators
sehr klein und die Rechenintensität dementsprechend gering. Zusätzlich würde er sich eignen, da
die restlichen kantenbasierten Algorithmen der Berlin United - FUmanoids auf diesem Operator
aufbauen und demnach keine weiteren Anpassungen vorgenommen werden müssten.


1/2
Gx = 1/2 0 −1/2
Gy =  0 
−1/2
• Sobel-Operator: Der Sobel-Operator ist der wahrscheinlich am Häufigsten eingesetzte KantendetektionsOperator und wird auch in der Implementierung des ebenso bekannten Canny-Algorithmus der
OpenCV-Bibliothek3 verwendet.




1
2
1
1 0 −1
0
0
Gx = 2 0 −2 Gy =  0
−1 −2 −1
1 0 −1
• Scharr-Operator: Der Scharr - Operator ist der von Hanno Scharr optimierte Sobel-Operator
in Hinsicht auf eine perfekte Rotationssymmetrie[Sch00]. Rotationssymmetrie bedeutet für einen
Kantenfilter, dass er keine Gradientenrichtungen bevorzugt. Um einen perfekten, einen Pixel breiten Kreis, besäßen also alle Gradienten die gleiche Magnitude.




3 0 −3
3
10
3
0
0
Gx = 10 0 −10 Gy =  0
3 0 −3
−3 −10 −3
Vor dem Berechnen des Fehlers E, wird noch die Minimierung der Kantendicke angewendet. Da hier die
Schwellwerte θlow und θhigh maßgebend zum Ergebnis beitragen, werden zusätzlich für jeden Operator
3 OpenCV
ist eine Bibliothek von Algorithmen zur Bildverarbeitung. Sie ist kostenlos unter der BSD-Lizenz nutzbar.
33
verschiedene Schwellwert-Kombinationen ausgetestet, um so das globale Minimum für E zu finden. In
der Ergebnistabelle 3.3 ist der durchschnittliche Fehler ØE pro Teilbild angegeben, das Minimum ist
grau markiert.
Operator
θlow
θhigh
ØE
Einfach
20
21
22
23
24
25
26
27
28
29
16.48
15.86
15.44
15.46
15.94
Sobel
140
160
180
200
220
190
210
230
250
270
16.75
15.19
14.70
20.29
23.80
Scharr
200
220
240
260
280
250
270
290
310
330
21.52
20.61
19.69
22.14
25.26
Tabelle 3.3: Vergleich dreier Kantendetektions-Operatoren mit Hilfe einer Fehlerfunktion. Kleineres E
ist besser.
Die Ergebnisse zeigen, dass der Sobel-Operator den kleinsten Fehler erreicht. Aber auch der einfache
Operator hat nur einen marginal schlechteren Fehler. Einen unerwartet hohen Fehler erreicht der ScharrOperator. Da er laut [Sch00] eine perfekte Rotationssymmetrie besitzt, wurde das beste Ergebnis zur
Detektion von Kreisen erwartet. Aufgrund des hohen Fehlers scheidet er jedoch als optimaler Operator
aus.
Es sind nun der einfache und der Sobel-Operator noch subjektiv zu bewerten. Der Sobel-Operator bietet hier ein wesentlich besseres Gesamtbild, da er nach Kriterium 2 wenig ungewollte Kante produziert.
Dies lässt sich durch die Kombination mit dem Gauß-Filter erklären. Beide Operatoren produzieren jedoch ausreichend gute Kanten um die Bälle.
Zusammengefasst verspricht der Sobel-Operator also die besten Ergebnisse für diesen Anwendungsfall. Er wird im Folgenden daher als optimaler Kantendetektions-Operator angesehen.
3.3.2 Integrales Histogrammbild
Die angesprochene schlechte Laufzeit der Hypothesensuche, basiert auf dem Erzeugen der Teilbildhistogramme. Auf die vorgestellte unoptimierte Art und Weise würde diese Methode zu einer sehr schlechten
Laufzeit führen. Grundlegendes Problem ist hier, dass die überlappende Suche zu redundanten Operationen führt. Wird das Histogramm des gesamten Kamerabilds berechnet, so wurde bereits jeder Pixel
einmal angefasst. Im nächsten Level würden insgesamt 9 Teilbilder betrachtet werden. Bereits 4 davon
34
x
x
y
y
I(x,y)
I(x',y')
I(x,y')
i(x,y,x',y')
(x,y)
I(x',y)
(a) Berechnung des Integralbilds
I(x,y)
(b) Berechnung einer Teilsumme mit Hilfe des
Integralbilds
Abb. 3.11: Berechnung und Verwendung des Integralbilds (nach [Mob11, Abb. 11.12])
fassen in der Summe erneut alle Pixel des Gesamtbilds an. Diese redundanten Operationen lassen sich
mit dem Verwenden eines Integralbilds verhindern.
Das Integralbild, erstmals eingeführt 1984 [Cro84] und erstmals in der Bildverarbeitung von Viola &
Jones verwendet [VJ01], ist ein Verfahren um schnell Summen von rechteckigen Bildausschnitten zu
berechnen. Dies wird erreicht, indem jeder Bildpunkt die Summe aller Werte des Rechtecks zwischen
sich und Punkt (0,0) speichert (siehe Gleichung (3.6) und Abbildung 3.11a).
x
y
I(x, y) = ∑ ∑ I(i, j)
(3.6)
i=0 j=0
Die nun vorliegende integrale Repräsentation vereinfacht das Berechnen eines beliebigen Rechtecks auf
konstant 4 Speicherzugriffe und drei arithmetischen Operationen (siehe Gleichung (3.7) und Abbildung
3.11b).
(3.7)
i(x, y, x0 , y0 ) = I(x, y) + I(x0 , y0 ) − (I(x0 , y) + I(x, y0 ))
Selbstverständlich muss zusätzlich das Integralbild berechnet werden, welches jedoch in einem Bilddurchlauf berechnet werden kann. Dafür wird eine temporäre Variable S eingeführt, die die Summe der
aktuell bearbeiteten Bildzeile y speichert. I(x, y) berechnet sich dann aus der Summe von S, des Bildpunkts B(x, y) und I(x, y − 1). Als rekursive Funktion lässt sich die Berechnung folgend auffassen:
S(x, y) = S(x − 1, y) + B(x, y)
(3.8)
I(x, y) = I(x, y − 1) + S(x, y)
Bezogen auf die formbasierte Ballerkennung wird nun ein Integralbild von Histogrammen benötigt. Auf
diese Weise kann das Histogramm eines Teilbilds ebenfalls mit nur 4 Speicherzugriffen erfolgen. Alle
vorgestellten Gleichungen gelten weiterhin für die Verwendung mit Histogrammen, wobei die Addition zweier Histogramme komponentenweise zusätzlich zum Aufwand des Integralen Histogrammbilds
zuzurechnen ist. Bei 18 Komponenten bedeutet dies bei der Berechnung des Bildes einen Aufwand von
35
Lv. 1
Lv. 1
1
5
2
8
2
7
Abb. 3.12: Defekt der rekursiven Hypothesensuche: Der Ball in Teilbild 5 wird ausgeschlossen, weil
das Teilbild des 2. Levels zum zweiten Mal bearbeitet wird.
2·18 arithmetischen Operationen, anstatt von 2. Und auch bei der Berechnung eines Teilbildhistogramms
erweitert sich der Aufwand von 3 auf 3 · 18 Operationen. Es wird somit deutlich, dass das Berechnen des
Integralen Histogrammbilds zwar einen enormen Vorteil, aber immer noch einen sehr hohen Aufwand
bedeutet. Welchen Einfluss dies auf die Performance der Ballerkennung hat, wird im Kapitel Auswertung
besprochen.
3.3.3 Rekursive Suche
Der von Moballegh vorgeschlagene Algorithmus zur Hypothesensuche birgt einen Defekt, der an dieser
Stelle korrigiert werden soll. Zunächst sei an dieser Stelle noch einmal auf den Algorithmus 1 in Kapitel
Hypothesensuche auf Seite 26 verwiesen, auf welchen sich hier bezogen wird.
Der Defekt entsteht durch Rückgabe des booleschen Wertes true in Zeile 4 und tritt damit auf, wenn
ein Teilbild zum zweiten Mal bearbeitet wird. Mit dieser Rückgabe wird das Eltern-Teilbild aus dem
Kandidatenpool ausgeschlossen, da die Variable b durch die Veroderung in jedem Fall ebenso zu true
ausgewertet wird. Kommt es nun jedoch zu dem Fall, dass innerhalb dieses Eltern-Teilbilds ein Ball
eingeschlossen ist, so wird es trotzdem ausgeschlossen. Abbildung 3.12 verdeutlicht diesen Fall.
Die Lösung dieses Problems ist das zusätzliche Speichern des Ergebnis, ob das Teilbild ausgeschlossen werden kann oder nicht. Zwar erwähnt Moballegh diese Idee, der Algorithmus ist aber unvollständig.
Algorithmus 2 auf Seite 36 zeigt die neuen Modifizierungen. Das Speichern der Information, ob ein Teilbild ausgeschlossen ist oder nicht wird in Zeile 18 durch die Variable hasChildren ermöglicht. Diese wird
initial auf true gesetzt und durch die beiden Rekursionsanker in Zeile 8 und 14 je nach Fall verändert. Die
ursprüngliche Variable b wurde in diesem Algorithmus umbenannt zu childrenHaveChildren, um den
Nutzen zu verdeutlichen. Das Ergebnis der rekursiven Suche ist durch die Markierung von akzeptierten
Teilbildern in Abbildung 3.15a zu sehen.
Algorithmus 1b: Optimierte überlappende Rekursive Suche
1 b o o l e a n o v e r l a p p i n g S e a r c h ( window , l e v e l )
2 begin
3
i f window i s a l r e a y s c a n n e d t h e n
4
r e t u r n window −> h a s C h i l d r e n
5
6
h a s C h i l d r e n <− t r u e
7
8
i f l e v e l > 5 then
9
h a s C h i l d r e n <− f a l s e
10
11
i f hasChildren
12
h i s t o g r a m <− c a l c u l a t e H i s t o g r a m ( window )
13
36
14
15
16
17
18
19
20
21
22
23
24
25
26
i f h i s t o g r a m h a s a t l e a s t one z e r o component t h e n
h a s C h i l d r e n <− f a l s e
window <− s c a n n e d
window <− h a s C h i l d r e n
i f not h a s C h i l d r e n
return f a l s e
c h i l d r e n H a v e C h i l d r e n <− f a l s e
f o r a l l 9 s u b windows
c h i l d r e n H a v e C h i l d r e n <− c h i l d r e n H a v e C h i l d r e n or o v e r l a p p i n g S e a r c h ( s u b window ,
level + 1 )
27
28
i f not c h i l d r e n H a v e C h i l d r e n t h e n
29
p u s h _ b a l l _ c a n d i d a t e ( window )
30
31
return true
32 end
3.3.4 Kandidatenverifizierung
Ein zu optimierender Punkt der Kandidatenverifizierung ist das zweite Kriterium (3.3) der Verifizierung.
Sie verwendet nur einen Schwellwert β für die untere und die obere Grenze. Besser ist es hier jedoch für
die obere Grenze einen anderen Schwellwert zu nehmen, da die Menge an Kanten in einem Ball theoretisch erst durch seine Fläche begrenzt wird. Bisher wurde davon ausgegangen, dass der Ball einfarbig ist
und die Kante somit nur um den Rand entsteht. Aufgrund den Vorgaben der Technical Challenge kann
aber auch das Muster beliebig sein. Es ist also davon auszugehen, dass auch innerhalb des Balls eine
große Menge an Kanten vorkommen kann. Die Einführung eines weiteren Schwellwerts ist demnach
eine einfache Möglichkeit damit umgehen zu können. Zusätzlich ist an dieser Stelle anzumerken, dass
der Durchmesser des kleinsten Balls in einem Teilbild nicht halb so groß ist wie die kürzeste Seite des
Teilbilds, sondern im schlimmsten Fall etwa viermal so klein. Abgebildet ist dieses Problem in Abbildung 3.13. Hier ist der Ball gerade großgenug um nicht vom bestmöglichen Teilbild eingeschlossen zu
werden. Das Eltern-Teilbild muss demnach einen etwa viertel so großen Ball verifizieren. In Abbildung
3.14 tritt dieser Fall in einem Testbild auf. Der untere Schwellwert muss mit 0.3 also niedriger angesetzt
werden als zunächst besprochen. Die neue Ungleichung ist abschließend:
d:
n:
βlow :
βhigh :
Länge der kleinsten Seite des Teilbildes
Anzahl an Gradienten im Teilbild
Schwellwert für die untere Grenze
Schwellwert für die obere Grenze
π
d(1 − βlow ) < n < 4d(1 + βhigh )
2
(3.9)
Die neue Erkenntnis beeinflusst auch das erste Kritierium der Verifizierung in der Annahme, dass die
Schubfächer in einem Histogramm gleich verteilt sein müssen. Hat der Ball das typische Muster beste-
37
100%
50%
28%
Abb. 3.13: Kleinstmöglicher Ball in einem Teilbild. Die roten Teilbilder lehnen ab, daher muss das
grüne Eltern-Teilbild den Ball verifizieren
hend aus Pentagons oder ähnlichen Polygonen, kommen je nach Lage des Balls viele weitere Gradienten
dazu, welche die Verteilung der Richtungen streuen. Dieses Problem lässt sich mit dem Histogramm
als Information nicht ohne Weiteres lösen. Für die Auswertung wurde daher der Schwellwert α auf den
Wert 0.8 erhöht. Das so geschwächte Kriterium resultiert in einer höheren Anzahl an akzeptierten Kandidaten. Um dem entgegen zu wirken, muss daher ein dritter Schritt zur Verifizierung eingeführt werden.
Zusätzlich ist dieser Schritt wichtig, da in Abbildung 3.15 zu erkennen ist, dass die Größe des Balls unter
Umständen sehr schlecht durch ein Teilbild approximiert wird. Für den Fall, dass mehr als eine Teilbild
als Ball verifiziert wird, würde eine Plausibilitätsprüfung der Größe wenig Sinn machen, wenn ungewiss
ist wie groß der Ball nun wirklich ist.
Das Histogramm als Informationsquelle bietet sehr wenig Spielraum zur Verifizierung von Formen.
Für den dritten Schritt soll daher das Kantenbild ausgewertet werden. Dazu wurde bereits die HoughTransformation (siehe Seite 16) und das Arc-Fitting (siehe Seite 19) vorgestellt. In erster Linie sollte
ein möglichst schnelles Verfahren angewendet werden, da sich bereits andeutet, dass die notwendigen
Schritte zur Kantendetektion und zum Erzeugen des Integralen Histogrammbildes insgesamt sehr rechenaufwändig sind. Aus diesem Grund wurde eine Implementierung der Hough-Transformation aus
der OpenCV Bibliothek und eine eigene Implementierung des Arc-Fittings verwendet, um eine grobe
Abschätzung der Laufzeiten dieses zusätzlichen Schritts machen zu können. Dafür wurde das größtmögliche Teilbild (640x480) als Worst-Case-Szenario ausgewählt und beide Algorithmen bestmöglich
justiert, so dass sie den vorkommenden Ball schnellst möglich erkennen. Dieses Vorgehen soll das Potential der Algorithmen zeigen, wobei selbstverständlich zu beachten ist, dass im praktischen Gebrauch, die
Algorithmen auch mehr als doppelt so lange benötigen könnten. Die Laufzeiten beider Algorithmen sind
stark von der Menge an Kanten abhängig. Die Hough-Detektion bietet den Vorteil einer stets akkuraten
Detektion in Bezug auf Position und Größe des Balls, der Arc-Fitting-Algorithmus ist schnell, hat aber
Probleme wenn viele unwichtige Kanten im Bild vorhanden sind. Die Laufzeit der Algorithmen ist in
Tabelle 3.4 aufgetragen, wobei sie aus dem Mittel von 20 Durchläufen eines Algorithmus gebildet wird.
Das visuelle Ergebnis der Balldetektion ist in Abbildung 3.14 aufgetragen.
38
(a) Hough-Circle-Detektion
(b) Arc-Fitting-Detektion
Abb. 3.14: Ergebnis der Kreisdetektions-Algorithmen: Hough-Circles und Arc-Fitting
Algorithmus
Hough-Circles
Arc-Fitting
Ø Laufzeit in ms
9.234
0.062
Tabelle 3.4: Vergleich der Laufzeiten der Kreisdetektions-Algorithmen: Hough-Circles und Arc-Fitting
(Testprozessor: 3Ghz Intel CPU)
Der Laufzeitvergleich zeigt einen beachtlichen Unterschied. Die Hough-Circle-Detektion benötigt für
das gleiche Bild 100 mal mehr Zeit und ist damit als dritte Verifikation völlig ungeeignet. Das ArcFitting-Verfahren verspricht hier ein besseres Ergebnis, welches jedoch unter Vorbehalt zu betrachten ist.
Durch Beobachtung einiger verschiedener Testbilder ist zu erkennen, dass die Erkennungsrate für einen
echten Einsatz noch nicht ausreichend gut ist. Falsche Klassifikationen sind zwar nicht oder nur selten zu
erwarten, eine richtige Klassifikation wird aber durch umgebene Feldlinien oder Gegenstände erschwert.
Demzufolge müsste der implementierte Arc-Fitting-Algorithmus hinsichtlich der Robustheit verbessert
werden. Da dies den Rahmen dieser Bachelorarbeit sprengt, ist die Verbesserung an dieser Stelle ein
Vorschlag für eine weitere Ausarbeitung.
Aufgrund der unzuverlässigen Erkennungsrate, wird der dritte Verifikationsschritt im Folgenden nicht
eingesetzt. Das Ergebnis des gesamten Prozesses inklusive Arc-Fitting ist anhand eines Beispielbilds in
der Abbildungsreihe 3.15 zu sehen.
39
(a) Hypothesen
(b) Verifizierte Hypothesen
(c) Ergebnis des Arc-Fittings
Abb. 3.15: Ergebnis der rekursiven Suche, der Hypothesenverifizierung und des Arc-Fittings
40
4 Auswertung
Nachdem nun alle Punkte der formbasierten Ballerkennung erläutert und optimiert wurden, steht nun
noch die Auswertung der Erkennungsrate und die der Laufzeit aus.
Die Laufzeitanalyse wird auf der Zielhardware ausgeführt und unter möglichst vielen verschiedenen
Szenen getestet. Ziel ist es ein repräsentatives Ergebnis der mittleren Laufzeit zu erhalten, um den praktischen Einsatz des Algorithmus bewerten zu können.
Die Auswertung der Erkennungsrate erfolgt offline mit einem Testsatz von 73 Bildern. Unter den
73 Bildern sind bis zu drei verschiedene Bälle zu finden: ein glänzend roter mit starken Reflektion,
ein weißer matter um Komplikationen mit den weißen Feldlinien zu prüfen und der orangene StandardTennisball (siehe Bälle in Abbildung 3.4). Erschwert werden die Bedingungen durch aufgestellte schwarze Hindernisse.
4.1 Laufzeitanalyse
Zur Messung der Laufzeiten wurde ein 2012er - Roboter (siehe Abbildung 1.7) an mehrere, möglichst
unterschiedliche Positionen auf dem Spielfeld gestellt. An jeder Position wurde der Ball vom weit entferntesten Punkt langsam in Richtung Roboter gerollt, sodass der Ball in verschiedenen Größen sichtbar
war. Die gesamte Prozedur wurde drei Minuten ausgeführt.
Gemessen wurden alle elementaren Schritte des Algorithmus. Diese sind die Glättung des Bildes,
die Kantendetektion, die Minimierung der Kantendicke, die Erzeugung des integralen Histogrammbilds,
die rekursive Suche und die Verifizierung. Um ein repräsentatives Ergebnis der einzelnen Laufzeiten zu
erhalten, wird der Durchschnitt aus allen gemessenen Laufzeiten gebildet.
Bildglättung
Kantendetektion
Minimierung der Kantendicke
Integrales Histogrammbild
Rekursive Suche
Kandidatenverifizierung
Summe
Gesamt Vision
Ø Laufzeit in ms
113.96
152.80
22.50
144.64
1.66
1.15
436.71
2.05 Bilder pro Sekunde
Bildglättung, Kantendetektion und Erzeugen des integralen Histogrammbilds benötigen jeweils über
100ms. In der Summe liegt die Laufzeit des gesamten Algorithmus zur formbasierten Ballerkennung
zwischen 400 und 450ms, sodass letztendlich etwa 2 Bilder pro Sekunde verarbeitet werden können.
Die Bildglättung und die Kantendetektion benötigen viel Zeit, da die Konvolutionsmatrizen auf alle
41
4 Auswertung
drei Farbkomponenten des Bilds angewendet werden müssen. Bei der Kantendetektion kommt zusätzlich die Berechnung des Arkustanges hinzu. Das erzeugen des integralen Histogrammbilds ist wie auf
Seite 35 bereits erwartet ebenso sehr zeitintensiv, da pro Bildpunkt zwei Histogramme mit 18 Schubfächern summiert werden müssen. Die restlichen Teile des Algorithmus haben relativ gesehen, keinen
nennenswerten Einfluss auf die Gesamtlaufzeit.
4.2 Erkennungsrate
Für die Erkennungsrate wurden alle vorkommenden Bälle mit umschließenden Quadraten annotiert. Um
sie auszuwerten, werden die annotierten Bilder mit den verifizierten Teilbildern verglichen. Überlappen
sich die Rechtecke und teilen sich mehr als 50 Prozent ihrer Fläche, so wird die Detektion als wahr deklariert. Alle anderen werden als falsch deklariert.
Sei G die Summe an detektierbaren Bällen1 in allen Testbildern und W die Summe an erkannten
Bällen. Dann ist Wp = W ·100
der prozentuale Anteil an korrekt erkannten Bällen. Sei F die Summe an
G
falsch erkannten Bällen im Bild.
G
W
Wp
100 −Wp
F
59
32
54.24%
45.76%
62
Tabelle 4.1: Erkennungsrate der formbasierten Ballerkennung
Neben der geringen Anzahl an richtig erkannten Bällen fällt besonders die Anzahl an falschen Klassifikationen auf. Bei 73 Bildern beläuft sich das auf fast eine falsche Klassifikation pro Bild. Eine große
Anzahl an falschen Klassifikationen wäre akzeptabel, wenn zumindest ein sehr großer Teil korrekt erkannt werden würde. Hier könnte durch zusätzliche Verifikation nachfolgend noch aussortiert werden.
Die schlechte Erkennungsrate ist vor allem auf die selten zutreffende Anforderung eines vollständigen
Histogramms oder einer fehlenden Gleichverteilung zurückzuführen. Neben teilweise verdeckten Bällen,
besitzt vor allem der rote Ball ein großen Glanzpunkt, welcher viele Gradientenrichtungen zum Teilbild
hinzufügt und die Gleichverteilung abschwächt. Auch der weiße Ball wird im Normalfall nicht erkannt,
wenn er direkt auf einer weißen Feldlinie liegt. In diesem Fall ist die Ballkante, auf Grund zu geringer
Intensitätsdifferenzen, unvollständig.
Die hohe Rate an falschen Klassifikationen ergibt sich aus der Tatsache, dass besonders Hindernisse
und teilweise auch sich kreuzende Feldlinien zu einem gefüllten Histogramm und damit zu einer wahren
Aussage führen.
In Bezug auf die ungenügende Erkennungsrate, ist es an dieser Stelle hinfällig ein Vergleich mit der
aktuell eingesetzten farbbasierten Ballerkennung zu ziehen.
1 Detektierbar
meint hier, dass mehr als etwa 33% der Ballfläche sichtbar ist.
42
5 Fazit
5.1 Zusammenfassung
In dieser Arbeit wurde ein Ansatz zur formbasierten Ballerkennung auf dem Methodenvorschlag von
Hamid Reza Moballegh vorgestellt und evaluiert. Ziel war es, die Anforderung der für 2012 geänderten
Technical Challenge zu erfüllen und einen Ball beliebiger Farbe und beliebigem Musters um Hindernisse
in das Tor zu dribbeln.
Dafür wird die Eigenschaft ausgenutzt, dass alle Gradientenrichtungen an einer Ballkante eines idealen Kreises gleich verteilt oft vorkommen, um einen Klassifikator zu bilden. Durch rekursives Einteilen
des Bildes und anschließender Eliminierung von Teilbildern, welche die Bedingung nicht erfüllen, werden uninteressante Bereiche aussortiert. Übrig gebliebene Teilbilder werden durch das Kriterium der
Gleichverteilung und durch das Kriterium der Kreisumfang-Gradientenanzahl-Korrelation gefiltert.
Zur Optimierung wurde eine optimale Kantendetektion evaluiert, sowie die rekursive Suche in ihrer
Funktion verbessert. Zusätzlich wurden Ansätze wie Hough-Transformation für Kreise und Arc-Fitting
versucht zu verwenden, um das Endergebnis zu verbessern.
Die Auswertung der Erkennungsrate und der Performance des entwickelten Algorithmus zeigen jedoch, dass ein praktischer Einsatz eher begrenzt möglich ist. Gründe dafür sind eine zu rechenintensive
Vorverarbeitung und die zu selten zutreffenden Annahme, eines perfekten Kreises.
5.2 Vor- und Nachteile
In diesem Abschnitt sollen nun zusammenfassend alle Vor- und Nachteile der evaluierten formbasierten
Ballerkennung dargelegt werden.
Vorteile:
• Vorselektierung: Viele Bereiche lassen sich mit Hilfe des Integralen Histogrammbilds und der
rekursiven Suche vollkommen ausschließen. Die Menge an zu bearbeitenden Informationen reduziert sich.
• Universalität: Das erzeugte integrale Histogrammbild ist nicht nur für eine Balldetektion anwendbar. Vorstellbar sind verschiedene Methoden, welche sich die Auswertung von Gradientenrichtungen zu nutze machen.
Nachteile:
• Langsam: Die Berechnungen vor der Detektion wie das Glätten, das Ausführen der Kantenminimierung und das Erzeugen des integralen Histogrammbilds dauern sehr lange, sind aber notwendig
um ein gutes Kantenbild zu erhalten und damit die Histogramme verifizieren zu können.
43
5 Fazit
(a)
(b)
(c)
(d)
Abb. 5.1: Detektionsproblem bei bestimmten Ballhintergründen. a) Problematischer Hintergrund c)
Problemloser Hintergrund b) und d) Gefärbtes Gradientenbild. Grün: Gradienten zeigen nach oben,
Blau: Gradienten zeigen nach unten.
• Schlecht approximierte Ballgröße: Der kleinst mögliche Balldurchmesser von einem Viertel
der kürzesten Teilbildseite ist für eine gute Abschätzung der echten Ballgröße unzureichend ohne
weitere Klassifikation.
• Unzureichende Verifikation: Die Verifikation des Histogramms ist auf Grund des stark variierenden Balldurchmessers und des unvorhersehbaren Ballmusters schlecht durchführbar.
• Detektionsproblem bei zwei verschiedenen Hintergründen: Die Eigenschaft der ersten Ableitung, je nach Intensitätsan- oder abstieg positiv oder negative Werte zu erzeugen, kann zu einem
Problem bei zwei verschiedenen Ball-Hintergründen führen. Abbildung 5.1b zeigt dies anhand
eines Beispielbilds. Gradienten mit positiver y-Komponente sind Blau und Gradienten mit negativer y-Komponente Grün markiert. Es ist zu erkennen, dass alle Gradienten eine positive yKomponente besitzen. Es kann damit nicht zu einem vollständig gefüllten Histogramm kommen.
Dieser Fall könnte auftreten, wenn der Ball vor einem Gegenstand oder einem Gegner liegt.
Es ist abschließend festzustellen, dass die vorgeschlagene Annahme zwar ein Aussortieren von Regionen im Bild ermöglicht, aber keine vertrauenswürdige Klassifikation für einen Ball ist. Es gibt zu
viele Fälle in denen der Ball nur teilweise sichtbar ist. Durch Schattenwurf, Glanzpunkte, Muster oder
ungenügenden Kontrast zwischen Ball und Hintergrund kommt es zu fehlenden Gradientenrichtungen,
die die Auswertung der Histogramme erschwert. Folgerichtig muss eine Abschwächung von Bedingungen vorgenommen werden, welche daraufhin die Anzahl der Hypothesen wesentlich erhöht. Notwendig
wäre dann eine weitere Klassifikation. Durch die hohe Laufzeit jedoch, ist es nicht ertragreich die Histogrammanalyse als Basis zu verwenden.
44
6 Ausblick
Trotz des negativen Fazits, muss das Verfahren nicht vollständig verworfen werden. Die Eliminierung
von Suchbereichen könnte weiterhin von Interessen sein und müsste lediglich schneller berechnet werden.
6.1 Verbesserungsmöglichkeiten
Um dies zu erreichen gibt es verschiedene Ansätze. Möglich ist eine Unterabtastung des Bildes um das
Integrale Histogrammbild in seiner Größe zum Beispiel zu halbieren. Auch das Auslagern auf weitere
ungenutzte Hardware ist sinnvoll, da dadurch das Erzeugen parallel geschehen kann. Im Rahmen dieser
Arbeit wurde dieser Ansatz versucht auf dem noch ungenutzten DSP1 auf dem IGEP-Board anzubinden.
Leider konnte jedoch das Kamerabild dem DSP nicht verfügbar gemacht werden. Auch der Beispielcode
des Herstellers Texas Instruments funktionierte nicht. Ein Nachteil bei der Verwendung des DSP’s ist
jedoch, dass bei einem Wechsel der Hardware, auch das Programm portiert werden muss und unter
Umständen auch wieder auf dem Hauptprozessor laufen muss.
Einen besseren Ansatz zur Verbesserung verspricht das Paper von Müller, Lenz, Barner und Knoll,
welche das Integrale Histogrammbild adaptiv erzeugen [MLBK08]. Dabei wird durch Einteilen des Bildes in gleichfarbige Bereiche nicht für jeden Pixel ein Histogramm erzeugt, sondern nur für jedes dieser
besagten Bereiche.
6.2 Anwendbarkeit
Das integrale Histogrammbild bietet, eine entsprechende Performance vorausgesetzt, eine gute Grundlage für jegliche Objektdetektionen. Durch zukünftige Verschärfung der RoboCup-Regeln werden in
absehbarer Zeit auch die Tore einfarbig. Auch beliebige Farben sind möglich. Hier könnten mit einer
ähnlichen Methode uninteressante Bereiche aussortiert werden.
Außerhalb der doch sehr kontrollierten RoboCup-Umgebung ist der Einsatz der vorgestellten Methode
nur denkbar, wenn der Hintergrund des zu detektierenden Objekts sehr wenige Informationen beinhaltet.
6.3 Alternativen
Da sich die evaluierte Methode nicht zur Detektion von Bällen im RoboCup eignet, werden im letzten Abschnitt dieser Arbeit mögliche Alternativen vorgeschlagen. Aus den gewonnen Erkenntnissen zu
1 Digitaler
Signalprozessor
45
6 Ausblick
Verfahren und deren Laufzeiten ist vor allem entscheidend, eine Alternative zu finden, welche weniger
zeitintensiv ist. Dabei sollte die Erkennungsrate selbstverständlich nicht mit sinken.
Die Detektion auf Basis der Kanten erscheint als sinnvoll, da Farben oder Helligkeitsunterschiede wenig universell sind. Da die Kante des Balls nicht immer vollständig ist, sollte auch ein etwa halb verdeckter Ball erkannt werden. Um dies zu erreichen, könnte die Hough-Transformation für Kreise verwendet
werden. Zwar ist diese ebenso zeitintensiv, jedoch ist sie sehr robust. Hier sollte evaluiert werden, ob
die Bildglättung wegfallen kann. Die Applikation des Kantendetektions-Operators kann zur Beschleunigung, je nach Bereich im Bild, auf jeden zweiten oder dritten Pixel erfolgen. Hier kann die Annahme
getroffen werden, dass ein Ball im unteren Teil des Bildes größer erscheint, als im oberen Teil. In den
oberen Bildbereichen müssen daher mehr Bildpunkte ausgewertet werden, als in den unteren. Die Verifizierung der produzierten Hypothesen sollte anschließend durch eine Plausibilitätsprüfung geschehen.
Dabei gilt eine Hypothese als Plausibel, wenn ihre Größe gleich der errechneten Größe an dieser Position
ist. Da die Ballgröße bekannt ist und die Annahme getroffen werden kann, dass der Ball auf dem Boden
liegt, kann durch geeignete Matrix-Transformation ein Bildpunkt in Weltkoordinaten umgerechnet werden und umgekehrt. Der unterste Punkt der Ballhypothese wird also in Weltkoordinaten umgerechnet,
um die Höhe des Balls verschoben und anschließen wird der höchste Punkt zurück in Bildkoordinaten
umgerechnet. Die Differenz zwischen unterstem und errechnete Punkt ist dann die erwartete Größe des
Balls an dieser Position.
Eine weitere Alternative, wäre das Verwenden der bereits eingesetzten Kantendetektion der Berlin
United - FUmanoids. Das eingesetzte Gradient Vector Griding [Sch11, Mob11] bestimmt dabei den
Verlauf von Kanten innerhalb der Zellen eines Rasters. Eine Zelle ist dabei in der aktuell eingesetzten
Version 16 mal 16 Pixel groß. Auf diese Weise wird pro Zelle ein Kantenverlauf zugeordnet und anschließend mit umliegenden Zellen anhand ihrer Farbe und Ausrichtung verbunden. Während dieses Ablaufs
kommt es auch zu Zellen, welche nicht durch ihre Nachbarn und deren Farbe zugeordnet werden können. Diese Zellen gehören dann meist zu einem Hindernis oder zu einem Ball und können als Grundlage
für die weitere Balldetektion verwendet werden. Eignen würde sich dafür besonders das in dieser Arbeit
vorgestellte Arc-Fitting.
Unabhängig von dem verwendeten Verfahren, sollte ein Tracking in Betracht gezogen werden. Das
Tracking prädiziert anhand von letzten Ballpositionen und der Eigenbewegung des Roboters die nächste
Ballposition. Im ersten Schritt sollte also die Detektion um den Bereich des prädizierten Balls vollzogen
werden, da hier die Wahrscheinlichkeit am höchsten ist. Auf diese Weise kann im normalen Spielverlauf
die Rechenzeit stark vermindert werden.
46
Literaturverzeichnis
[BCMM08] BARRILE, Vincenzo ; C ACCIOLA, Matteo ; M EDURI, Giuseppe M. ; M ORABITO, Francesco C.: Automatic recognition of road signs by Hough transform. In: International archives
of the photogrammetry, remote sensing and spatial information sciences (2008)
[Bos12] B OSCH, Torie: Why You Should Care About RoboCup. http://www.slate.
com/articles/technology/future_tense/2012/06/robocup_2012_
how_robot_soccer_has_led_to_robotics_breakthroughs_.html.
Version: Juni 2012, Abruf: 07.07.2012
[Can86] C ANNY, John F.: A Computational Approach to Edge Detection. In: IEEE Transactions on
pattern analysis and machine intelligence 8 (1986), November, Nr. 6, S. 679–698
[CM03] C OATH, Genevieve ; M USUMECI, Phillip: Adaptive Arc Fitting for Ball Detection in RoboCup. In: APRS Workshop on Digital Image Computing (2003), Februar
[Cro84] C ROW, Franklin C.: Summed-Area Tables for Texture Mapping. In: Computer Graphics
18 (1984), Juli, Nr. 3
[DH72] D UDA, Richard O. ; H ART, Peter E.: Use of the Hough transformation to detect lines and
curves in pictures. In: Commun. ACM 15 (1972), Januar, Nr. 1, 11–15. http://dx.doi.
org/10.1145/361237.361242. – DOI 10.1145/361237.361242. – ISSN 0001–0782
[Doh12] D OHRMANN, Lisa: Kalibrierungsfreie Vision für humanoide Fußball-Roboter, Freie Universität Berlin, Diplomarbeit, 2012
[DT05] DALAL, N. ; T RIGGS, B.: Histograms of oriented gradients for human detection. In: IEEE
Computer Society Conf. Computer Vision and Pattern Recognition CVPR 1 (2005), S. 886–
893
[FS95] F REUND, Yoav ; S CHAPIRE, Robert E.: A decision-theoretic generalization of on-line learning and an application to boosting. In: Proceedings of the Second European Conference
on Computational Learning Theory. London, UK, UK : Springer-Verlag, 1995 (EuroCOLT
’95). – ISBN 3–540–59119–2, 23–37
[FUm12] Berlin United - FUmanoids - Awards and Scores. http://www.fumanoids.de/
awards-and-scores/. Version: 2012, Abruf: 06.07.2012
[Gui07] G UILBOURD, R.: Entwurf und Implementierung eines Programms zur manuellen Farbkalibrierung im Rahmen des Projekts "Humanoide Fußballroboter". Studienarbeit, Freie
Universität Berlin, 2007
47
Literaturverzeichnis
[Höf08] H ÖFERLIN, Markus: Anpassungsfähige Ballerkennung im RoboCup. Universität Stuttgart,
2008
[Hou62] H OUGH, P.V.C.: Method and means for recognizing complex patterns. U. S. Patent 3, 069
654, Dezember 1962
[MLBK08] M ÜLLER, Thomas ; L ENZ, Claus ; BARNER, Simon ; K NOLL, Alois: Accelerating Integral
Histograms Using an Adaptive Approach. Version: 2008. http://dx.doi.org/10.
1007/978-3-540-69905-7_24. In: E LMOATAZ, Abderrahim (Hrsg.) ; L EZORAY,
Olivier (Hrsg.) ; N OUBOUD, Fathallah (Hrsg.) ; M AMMASS, Driss (Hrsg.): Image and Signal Processing Bd. 5099. Springer Berlin, 2008. – ISBN 978–3–540–69904–0, 209-217
[Mob11] M OBALLEGH, Dr. Hamid R.: Development of an Autonomous Humanoid Robot Team,
Freie Universität Berlin, Diss., 2011
[POP98] PAPAGEORGIOU, Constantine P. ; O REN, Michael ; P OGGIO, Tomaso: A General Framework for Object Detection. In: International Conference on Computer Vision (1998)
[Rob12a] RoboCup Soccer Humanoid League - About. http://www.tzi.de/humanoid/
bin/view/Website/WebHome. Version: Juli 2012, Abruf: 08.07.2012
[Rob12b] RoboCup Soccer Humanoid League Rules and Setup.
http://www.tzi.
de/humanoid/bin/view/Website/Downloads.
Version: Juni 2012, Abruf:
08.07.2012
[Sch00] S CHARR, Dr. H.: Optimale Operatoren in der Digitalen Bildverarbeitung, Ruprecht-KarlsUniversität Heidelberg, Diss., August 2000
[Sch11] S CHMUDE, Naja v.: Farb- und Kantenbasierte Objekterkennung Humanoider Roboter im
RoboCup-Szenario, Freie Universität Berlin, Diplomarbeit, 2011
[Sei10] S EIFERT, Daniel: Automatische Farbkalibrierung fußballspielender Roboter, Freie Universität Berlin, Diplomarbeit, 2010
[SOK+ 12] S EIFERT, Daniel ; OTTE, Stefan ; K ULICK, Johannes ; S CHMUDE, Naja v. ; D OHRMANN,
Lisa ; H EINRICH, Steffen ; D OHRMANN, Lisa ; M OBALLEGH, Hamid ; M IELKE, Sebastian
; F REITAG, Lutz ; H OHBERG, Simon ; AUER, Julius ; L OSCH, Max ; ROJAS, Raul: Berlin
United - FUmanoids Team Description Paper 2012. In: RoboCup 2012: Robot Soccer World
Cup XVI Preproceedings (2012)
[TMZ03] T REPTOW, André ; M ASSELLI, Andreas ; Z ELL, Andreas: Real-Time Object Tracking for
Soccer-Robots without Color Information. In: European Conference on Mobile Robotics
(2003), S. 33–38
[VJ01] V IOLA, Paul ; J ONES, Michael: Robust Real-time Object Detection. In: International
Journal of Computer Vision (2001), Juli
[VK10] V ELAMMAL, B.L. ; K UMAR, P. A.: An Efficient Ball Detection Framework for Cricket. In:
IJCSI International Journal of Computer Science Issues 7 (2010), Mai, Nr. 2
48
Abbildungsverzeichnis
1.1
1.3
1.4
1.2
1.5
1.6
1.7
Aufbau des Fußballfelds . . . . . .
Aldebaran NAO . . . . . . . . . . .
NimbRo Teen-Size . . . . . . . . .
Logo der RoboCup Initiative . . . .
Standardball der Kid-Size-Liga . . .
Logo der Berlin United - FUmanoids
Roboter 2012 . . . . . . . . . . . .
.
.
.
.
.
.
.
1
2
2
2
4
4
5
2.1
2.2
2.3
2.4
2.5
2.6
2.7
YCbCr - Farbraum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
YCbCr Farbverteilungen von zwei unterschiedlichen beleuchteten Spielfeldern . . . . .
Exemplarische Balldetektion mit Hell-Dunkel-Flächen . . . . . . . . . . . . . . . . . .
Schematische Darstellung von Intensitätsverläufen . . . . . . . . . . . . . . . . . . . .
Graustufenbild mit Vergößerung einer Pixelreihe des linken Torpfostens . . . . . . . . .
Beispielfunktion und erste Ableitung . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ergebnisse der Konvolution mit dem horizontalen und dem vertikalen Kantendetektions
- Operator. (Normiert um negative Gradienten darstellen zu können) . . . . . . . . . . .
Kantenbild der Abbildung 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Robotersicht auf Hinderniss, Ball und Tor (in Grautönen) . . . . . . . . . . . . . . . . .
Auswirkung des Schwellwertfilters . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Strategien zur Minimierung der Kantenmenge . . . . . . . . . . . . . . . . . . . . . . .
Hough-Transformation für Kreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Vier verschiedene Kombinationen von Hell-Dunkel-Flächen (Haar-like Features), entnommen aus [TMZ03, Abbildung 1] . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Arc-Fitting: Bestimmen von Punkten auf dem Kreisbogen (nach [CM03, Abbildung 5]) .
Arc-Fitting: Bestimmen des potentiellen Kreismittelpunktes durch Schnittpunkte . . . .
7
8
9
10
10
11
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Schematische Darstellung von Gradienten am Rand eines Kreises . . . . . . . . . . . .
Schematischer Ablauf der formbasierten Ballerkennung . . . . . . . . . . . . . . . . . .
Verlust von Farbinformation bei der Konvertierung von Farbwert zu Grauwert . . . . . .
Beispiel-Teilbilder und ihre zugehörigen Histogramme der Gradientenrichtungen . . . .
Zuordnen von Gradientenrichtung in Schubfächer . . . . . . . . . . . . . . . . . . . . .
Überlappende rekursive Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Beispielhistogramme und deren Gaußfunktionen . . . . . . . . . . . . . . . . . . . . .
Mit dem Median-Filter geglättete Bilder und deren Sobel-Kantenbilder nach Schwellwertfilterung mit θ = 5. Oben: Fenstergröße 5x5. Unten: Fenstergröße 15x15 . . . . . .
49
12
12
13
13
14
16
18
19
19
22
22
23
24
24
25
27
30
Abbildungsverzeichnis
3.9
3.10
3.11
3.12
3.13
3.14
3.15
Mit dem Gauß-Filter geglättete Bilder und deren Sobel-Kantenbilder nach Schwellwertfilterung mit θ = 5. Oben: Faltungsmatrixgröße 5x5. Unten: Faltungsmatrixgröße 15x15
Applikation von Non-maxima-suppression auf einem Kantenbild . . . . . . . . . . . . .
Berechnung und Verwendung des Integralbilds . . . . . . . . . . . . . . . . . . . . . .
Defekt der rekursiven Hypothesensuche . . . . . . . . . . . . . . . . . . . . . . . . . .
Kleinstmöglicher Ball in einem Teilbild . . . . . . . . . . . . . . . . . . . . . . . . . .
Ergebnis der Kreisdetektions-Algorithmen: Hough-Circles und Arc-Fitting . . . . . . .
Ergebnis der rekursiven Suche, der Hypothesenverifizierung und des Arc-Fittings . . . .
30
31
35
36
38
39
40
5.1
Detektionsproblem bei bestimmten Ballhintergründen . . . . . . . . . . . . . . . . . . .
44
50
Tabellenverzeichnis
3.1
3.3
3.4
Übersicht über den kleinst anzunehmenden Schwellwert α, um ein Histogramm als Ball
zu bewerten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Qualitativer Vergleich der Laufzeiten des Gauß- und des Median-Filters. (Testprozessor:
3Ghz Intel CPU) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Vergleich dreier Kantendetektions-Operatoren mit Hilfe einer Fehlerfunktion . . . . . .
Vergleich der Laufzeiten der Kreisdetektions-Algorithmen: Hough-Circles und Arc-Fitting
31
34
39
4.1
Erkennungsrate der formbasierten Ballerkennung . . . . . . . . . . . . . . . . . . . . .
42
3.2
51
27
Selbständigkeitserklärung
Ich erkläre, dass ich die vorliegende Arbeit selbständig und nur unter Verwendung der angegebenen
Literatur und Hilfsmittel angefertigt habe.
Berlin, den 28.01.2008
Max Maria Losch
52

Formbasierte Ballerkennung für humanoide Fußball

Transcrição

Documentos relacionados

Blech-Ronaldinho

Minigolf-Spielregeln in Kürze

Fußballtennis - Training und Service

20140708 Kickertische_und_Bälle_Anwälte

Trainingsplan 3 F

Golf Journal Quick Tipp_Der lange Bunkerschlag

Bogey, Par und Hightech

Datei öffnen - Golf

Landratsamt Rosenheim - Gymnasium Bad Aibling

Regeln – Dodgeball - Löcknitz