Diplomarbeit

Echtzeit Objekterkennung auf low power Embedded
Systems

ausgeführt zum Zwecke der Erlangung des akademischen Grades
eines Diplom-Ingenieurs

Institut für Computertechnik

eingereicht an der Technischen Universität Wien
Fakultät für Elektrotechnik und Informationstechnik

von
Roland Oberhammer

04.02.2007

 

Inhaltsverzeichnis

Kapitel 1 Aufgabenstellung ... 5

1.1 Roboterfußball ... 5
1.1.1 FIRA ... 5
1.1.2 Robocup ... 8

1.2 Anforderungen and das Vision System ... 8

Kapitel 2 Begriffsbildung ... 12

2.1 Das menschliche Sehen ... 13
2.1.1 Der Aufbau des Auges ... 13

2.2 Farbton, Helligkeit und Sättigung ... 16

2.3 Farbräume und ihre Entstehung ... 18
2.3.1 Drei-Komponenten-Theorie ... 18
2.3.2 Der RGB-Farbraum ... 18
2.3.3 Von der analogen in die digitale Welt ... 20
2.3.4 Der FHS-Farbraum ... 22
2.3.5 FHS ähnliche Modelle ... 24
2.3.6 Das YUV-Farbmodell ... 24
2.3.7 Das YCbCr-Farbmodell ... 25
2.3.8 Abtastfrequenzen ... 26

2.4 Auflösung von digitalen Bildern ... 27

2.5 Videoübertragung ... 27
2.5.1 Bildübertragung allgemein ... 28
2.5.2 ITU-R BT.601 ... 28
2.5.3 ITU-R BT.656 ... 29

Kapitel 3 Methoden der Bilderkennung ... 32

3.1 Grundlegende Begriffe ... 32

3.2 Das Schichtenmodell ... 34

3.3 Aufnahme ... 35

3.4 Vorverarbeitung ... 36
3.4.1 Charakterisierung digitaler Bilder ... 36
3.4.2 Punktoperatoren ... 38
3.4.3 Globale Operatoren ... 42
3.4.4 Operationen im Frequenzbereich ... 47
3.4.5 Transformation der Ortskoordinaten ... 50

3.5 Segmentierung ... 51
3.5.1 Schwellwertverfahren ... 52
3.5.2 Kantendetektion ... 53
3.5.3 Kantennachbearbeitung ... 55
3.5.4 Morphologische Operatoren ... 55

3.6 Merkmalsextraktion und Objektidentifikation ... 57
3.6.1 Opening und Closing ... 57
3.6.2 Vektorisierung ... 58
3.6.3 Modellierung ... 59

3.7 Interpretation ... 60

3.8 Rückkopplungen ... 60

Kapitel 4 Systemarchitektur und Wahl der Komponenten ... 62

4.1 Rahmenbedingungen ... 62
4.1.1 Abmessungen ... 62
4.1.2 Leistungsverbrauch ... 63

4.2 Architektur des Objekterkennungssystems ... 63

4.3 Bildaufnahme ... 64
4.3.1 Objektiv ... 64
4.3.2 Fotosensor ... 65
4.3.3 Image-Sensoren und Kameramodule am Markt ... 72
4.3.4 Monokamera gegen Stereokamera ... 76
4.3.5 Kameramontage ... 76

4.4 Prozessor ... 78
4.4.1 Fixkomma gegen Fließkomma ... 79
4.4.2 DSPs am Markt ... 79

4.5 Speicher ... 82
4.5.1 RAM ... 83
4.5.2 Flash ... 83

4.6 Tinyphoon ... 83

Kapitel 5 Realisierung und Ergebnisse ... 85

5.1 Entwicklungstools ... 85
5.1.1 Altium Designer ... 85
5.1.2 VDSP++ ... 85
5.1.3 JTAG ... 86

5.2 Schaltplan und Platinenlayout ... 86
5.2.1 Schaltplan ... 87
5.2.2 PCB-Layout ... 88

5.3 Betriebssystem ... 88

5.4 Software-Bibliotheken zur Bilderkennung ... 89

5.5 Treibersoftware ... 89
5.5.1 PLL ... 89
5.5.2 SDRAM-Controller ... 90
5.5.3 GPIO ... 91
5.5.4 SCCB ... 91
5.5.5 Kamerainitialisierung ... 92
5.5.6 Kamerkalibrierung ... 93
5.5.7 PPI und DMA ... 94
5.5.8 Flashspeicher ... 94

5.6 Bootvorgang ... 94

5.7 Aufnahmetests ... 95
5.7.1 AEC und AWB ... 96
5.7.2 Auflösung und Objektgrößen ... 97

5.8 DMA und Speicherverwaltung ... 97
5.8.1 Framebuffer ... 99
5.8.2 Cache der Bilddaten ... 100
5.8.3 Synchronisation der DMA-Transfers ... 101

5.9 Der Objekterkennungsalgorithmus ... 105
5.9.1 Vorverarbeitung des Bildes ... 105
5.9.2 Wahl eines geeigneten Farbraums ... 105
5.9.3 Kantendetektion und Farbklassifizierung ... 108
5.9.4 Nachbearbeitung der Segmente ... 111
5.9.5 Das „Short Line Detection“ Konzept ... 111
5.9.6 Die Modellierung und Objektbestimmung ... 112
5.9.7 Bildkoordinaten ... 114

5.10 Transformation der Bild- in Roboterkoordinaten ... 115
5.10.1 Koordinatentransformation ... 116
5.10.2 Testaufbau ... 118
5.10.3 Methode der kleinsten Quadrate ... 119
5.10.4 Stückweise lineare Approximation ... 120

5.11 Ablauf und Timing des Algorithmus ... 122

5.12 Performance optimiertes Kodieren ... 124

5.13 Evaluierung der Performance ... 125
5.13.1 Genauigkeit ... 125
5.13.2 Ausführungszeit ... 127
5.13.3 Leistungsaufnahme ... 127

5.14 Erkenntnisse und Problembereiche ... 128

Kapitel 6 Weitere Entwicklungen ... 129

6.1 FPGAs ... 129

6.2 Drehbarer Stereokopf ... 129

6.3 Neue Prozessoren ... 130

6.4 Neue Kameramodule ... 130

6.5 Autofokus ... 130

6.6 Verbesserungen des Monokamerasystems ... 131
6.6.1 Verdoppelung der Framerate ... 131
6.6.2 Verringerung der Empfindlichkeit gegen Verdeckung ... 131
6.6.3 Verbesserte Objektdetektion ... 132
6.6.4 Weniger Empfindlichkeit gegenüber Helligkeitsänderungen ... 132
6.6.5 Verringerung der Ausführungszeit ... 132

6.7 Intelligenter Bildverarbeitungssensor ... 132

 

Abstract

Object detection is a broad area that comprises a variety of methods for measuring and categorising objects, through the use of various sensor systems. These sensor systems differ according to their environments, allowed lighting conditions and the type of objects that they can detect; they have advantages and disadvantages accordingly. This diploma thesis is about object detecion in the area of robotics, especially about its use in Robot-soccer - which is increasing in popularity due to the associated research possibilities. The designed robot is required to follow the rules of the Mirosot Category, specified by the international organisation for advancement of Robot-soccer called FIRA. A digital camera is the sensor used for object detection: Starting from constraints in the measurements (based on the Mirosot Category and Rules), this thesis presents an appropriate hardware-platform and the reasons for choosing particular components. Based on standard methods of image processing and approximations for their algorithmic complexity, a software concept was sought-after, that meets the requirements. The main aim is the detection of the ball (an orange golfball) and the coloured goalposts. Since standard methods are not optimized for the specific hardware, and the efficiency is a major concern, a concept is presented, which allows basic geometric shapes (e.g. circles, rectangles) to be detected and measured. This new concept partly uses well-known methods from the standard literature, that were optimized for the required tasks; but also includes a new approach that makes it possible to handle the detection-complexity of the dynamic motion of the target objects. The result is a image processing system with a detection-rate of 60 images per second. The precision of the ball-detection lies at +/- 1 mm at a mean distance of 50 cm. The average power consumption is 1,5 Watt and the hardware-dimensions are such, that the hardware could be housed in a cube with sides of 7.5cm length.

Kurzfassung

Objekterkennung ist ein weit gefächertes Gebiet und umfasst eine Vielzahl von Verfahren zur Vermessung und Kategorisierung von Objekten mittels unterschiedlichster Sensorsysteme, die je nach Umgebung, Beleuchtung und Art der Objekte die detektiert oder vermessen werden sollen, unterschiedlich geeignet sind und ensprechend ihre Vor- und Nachteile besitzen. Diese Diplomarbeit beschäftigt sich mit der Objekterkennung im Rahmen der Robotik, speziell im Roboterfußball, welcher sich in den letzten Jahren, aufgrund der sich daraus ergebenden Forschungsmöglichkeiten, immer größerer Beliebtheit erfreut. Der Roboter soll den Regeln der Mirosot Kategorie der internationalen Organisation zur Förderung des Roboterfußballs FIRA entsprechen. Als Sensor für die Objekterkennung dient eine Digitalkamera. So wird in dieser Arbeit ausgehend von den Einschränkungen in den Abmessungen, bestimmt durch die Regeln der Kategorie Mirosot, eine geeignete Hardware-Plattform erarbeitet und Gründe für den Entscheid zur Wahl bestimmter Komponenten dargelegt. Ausgehend von gängigen Methoden der Bildverarbeitung und der Aufwandsabschätzung für diese Algorithmen, wird nach einem Softwarekonzept gesucht, das auf der gewählten Plattform den gestellten Anforderungen entspricht. Ziel ist in erster Linie die Erkennung des Spielballes, ein oranger Golfball und der farbig markierten Tore. Da Standardverfahren aber nicht auf die spezielle Hardware optimiert sind und auch ansonsten hohe Anforderungen an die Rechenleistung stellen, wird ein Konzept vorgestellt, das es erlaubt einfache geometrische Formen wie Kreise oder Rechtecke zu detektieren und zu vermessen. Dieses neue Konzept greift teilweise auf in der Fachliteratur bekannte Methoden zurück die hierfür entsprechend optimiert werden, enthält aber auch einen neuen Ansatz, der es erlaubt den Anforderungen durch die hohe Dynamik der Bewegung der zu detektierenden Objekte Rechung zu tragen. So entstand ein Bilderkennungssystem mit einer Erkennungsrate von 60 Bildern pro Sekunde. Für den Spielball liegt die Genauigkeit bei +/- 1 mm in einer mittleren Entfernung von 50 cm. Dies bei einem durchschnittlichen Leistungsverbrauch von 1,5 Watt und Dimensionen der Hardware die in einem Würfel von 7,5 cm Kantenlänge Platz finden.

 

Kapitel 1 Aufgabenstellung

Objekterkennung ist ein weit gefächertes Gebiet und es gibt mittlerweile zahllose Verfahren mittels unterschiedlichster Sensoren zur Detektion und Vermessung von Objekten. Im vorliegenden Fall geht es um die Entwicklung eines passiven bildgebenden Verfahrens zur Entfernungsbestimmung eines autonomen mobilen Roboters von anderen Objekten. Andere Objekte heißt in diesem Fall, da der Roboter Fußball spielen soll, um den Ball die Tore und evt auch die Gegner. Die Herausforderung liegt in den kleinen Abmessungen des Roboters und der damit verbundenen eingeschränkten Verfügbarkeit von Energie und Rechenleistung. Ziel ist somit die Entwicklung eines „intelligenten Sensors“ der die Abstände des Roboters zu Objekten definierter Größe an einer Kommunikationsschnittstelle zur Verfügung stellt. Die Bildaufnahme soll mittels einer Videokamera erfolgen. Getestet wird dieser Sensor im Rahmen von Roboter Fußballspielen.

1.1 Roboterfußball

Fußball spielende Roboter erfreuen sich immer größerer Beliebtheit, da dieses Spiel ein breites Forschungsfeld bietet und unterschiedlichste Disziplinen und Forschungsschwerpunkte vereint. Nicht nur die Testmöglichkeiten unter „realen“ Bedingungen, sondern auch die hohe Dynamik des Spiels, das höchste Anforderungen an Sensorik und Mechanik stellt, bieten einen Anreiz sich diesem Thema zu widmen.

Es gibt derzeit zwei große konkurrierende Verbände die internationale Meisterschaften im Roboterfußball in den unterschiedlichsten Kategorien veranstalten. Es sind dies die FIRA und der Robocup.

1.1.1 FIRA

FIRA steht für „Federation of International Robosoccer Association“. Sie wurde 1995 von Prof. Jong-Hwan Kim gegründet und organisiert seither jährlich internationale Meisterschaften im Roboterfußball in unterschiedlichen Kategorien [FIRA06]. Die Ligen reichen von einer reinen Simulationsliga bis hin zu humanoiden Robotern die in einem Elfmeterschiessen gegeneinander antreten.

Im folgenden wird die Liga in der der Roboter antreten soll, vorgestellt und die Regeln für die physikalischen Grenzen des Roboters erläutert, um zu zeigen, mit welchen Bedingungen die Objekterkennung zurecht kommen muss.

Mirosot:

Die Roboter der Mirosot-Liga besitzen in der derzeitigen Konfiguration kaum „Intelligenz“. Sie werden von einem externen Host-Rechner gesteuert der das gesamte Spielgeschehen mittels einer über dem Spielfeld montierten Kamera aufnimmt wie es in Abbildung 1.1 dargestellt ist. Jeder Roboter ist obenauf mit einer Farbkodierung gekennzeichnet um im von der globalen Kamera aufgenommenen Bild Gegner und die Spieler der eigenen Mannschaft unterscheiden zu können. Die gesamte Software zur Bildauswertung und Objekterkennung und auch jene Algorithmen zur Steuerung jedes einzelnen Roboters bzw. die „Strategie“ laufen auf einem handelsüblichen Desktop-Rechner. Dieser sendet nur mehr die Steuersignale an jeden einzelnen Roboter.

(Abbildung 1.1: Aufbau des MIROSOT Systems - In Downloadversion enthalten)

Die Roboter selbst sind würfelförmig mit einer Kantenlänge von maximal 75 mm. Sie werden von zwei unabhängigen Rädern an den Seiten angetrieben.

Gespielt wird mit einem orangen Golfball mit einem Durchmesser von ca. 43 mm [DGV04] auf grünem Untergrund. Die Abmessungen des Spielfelds hängen von der Unterkategorie ab. Derzeit werden Spiele mit 3, 5 oder 11 Spielern pro Mannschaft veranstaltet [FIRA06].

(Abbildung 1.2: Regelschleife eines MIROSOT Roboters - In Downloadversion enthalten)

Abbildung 1.2 zeigt ein prinzipielles Problem der Mirosot Roboter. Durch die Funkstrecke zwischen dem externen Host-Rechner und den Robotern entsteht eine Verzögerung die den Roboter entsprechend verspätet auf die im momentan aufgenommenen Kamerabild sich bietende Situation reagieren lässt. Dieser Umstand ließe sich umgehen, würde ein entsprechender Sensor direkt am Roboter montiert und dort eine Bildauswertung und Steuerung vorgenommen, beisbielsweise in besonders zeitkritischen Situation wie etwa den Abfangen sehr schnell geschossener Bälle, die Geschwindigkeiten von 5 m/s [NVK02] erreichen können.

[...]