Wat is perceptie? perceptie? • Perceptie is het waarnemen van de “staat van de wereld”. • Hiervoor heb je sensors nodig, voorbeeld – Binaire sensor: een drukknop. – Analoge sensor: een thermometer. – Complexe sensors: een oog.
Artificiële Intelligentie 1
• Geen enkele sensor is perfect
Visuele perceptie
– Ruis. – Afwijkingen. – Ambiguiteit.
Hoofdstuk 24 uit Russell & Norvig
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Soorten perceptie
Perceptie
• Feature extraction
• Een sensor beeld de wereld af op een representatie.
De agent trekt een beperkt aantal kenmerken uit zijn sensorwaarneming, en gebruikt dit om te reageren op de wereld.
• Kunnen we weten hoe de wereld eruit ziet door inverse te nemen?
• Model-based De sensorinput dient om een model van de wereld op te bouwen.
• Lukt niet… wat we waarnemen is ambigue en partieel. We kunnen nooit terug construeren hoe de wereld echt is.
Ze zullen ons eerst concentreren op modelgerichte perceptie… • Visuele perceptie, kan nooit volledig terug reconstrueren. David Marr noemt dit 2½ D reconstructie.
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Ambigue en partieel, partieel, voorbeeld
Is
een probleem? probleem?
• Enkel een probleem wanneer de wereld exact gereconstrueerd wordt binnen onze computer. • En… dat doen we gelukkig nooit. – Perceptie dient een doel. Reconstructie slechts tot zover om dat doel te bereiken.
• Waarvoor dient perceptie dan wel? – – – – –
Necker-kubus Autonomous Systems – Tony Belpaeme
Inspectie. Manipulatie. Navigatie. Objectdetectie. Objectherkenning.
Occlusie Autonomous Systems – Tony Belpaeme
1
De camera obscura
Camera obscura
Een camera zonder lens: pinhole camera
• Punten op oneindig (op de horizon) worden op een punt afgebeeld.
Y
image plane
• Wanneer een voorwerp niet veel in diepte varieert (Z± Z0) met Z0 << Z, dan kan je vereenvoudigen tot…
P X
• Camera obscura laat weinig licht binnen: groter gat nodig. Een groot gat verstrooit licht: lens nodig.
Z pinhole
P'
• Met een lens kan je niet de ganse scene scherp hebben Oplossing, je focust op een diepte. Voorwerpen met een geringe dieptevariatie hebben daar weinig last van.
f
Autonomous Systems – Tony Belpaeme
Perspectief projectie
Autonomous Systems – Tony Belpaeme
Lenscamera
•
Menselijk oog
Dunne lens vergelijking
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Digitaliseren
LowLow-level beeldverwerking
• Een analoog signaal wordt omgezet naar een digitale representatie. • Voorbeeld
• Lijndetectie (edge detection) – Om de randen de vinden in het beeld. Belangrijk om objecten van elkaar te onderscheiden. – Construeert een lijntekening van het beeld.
• Smoothing – Het verwijderen van ruis uit het beeld.
25 0 200 1 50 1 00
11 2 75
50 38 12 1
1 45
25
1
Autonomous Systems – Tony Belpaeme
73
49
Ax is Titl e
97
0
Ax is Title
1
Autonomous Systems – Tony Belpaeme
2
Edge detection: manier 1
Edge detection: manier 2
• Bereken het verschil met buurpixels
• Kernel operator 0 0
0
0
0
0
0
-12 -23 13 22
0
0
0
0
12 35 22
0 0
0
0
0
0
0
20 56 78 79 25
6
30 40 48 48 52 14
0
0
0
21 34 26 28 26
5
0 0
1
0
0
21 34 26 28 26
1
0
0
21 34 26 28 26
1
0
0
3
1
0
5
5
5
5
0
0
0
0
0
0
0
5
0
-6 -10 16 30 31 -27 -9
0
0
0
-20 -44 -43 -57 -25 -5
0
-12 -35 -22
0
0
-20 -36 -22 -1
54 20
-24 -10 -8
0
-4
38 14
0
6
9
6
22 20 26 13
0
-21 -13
8
-2
2
25
1
0
0
0
0
0
0
-21 -13
8
-2
2
25
1
0
0
0
-21 -13
8
-2
2
25
1
0
0
18 29 21 23 21
0
0
-3
0
0
0
4
1
0
0
3
1
0
-2
0 5
0 5
0 0 5
0 0 5
0 0
0
0
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Edge detection
Ruis verwijderen: verwijderen: smoothing
• Beide methoden zijn een benadering van de eerste afgeleide van het beeld.
• Het lokaal gemiddelde nemen van elke pixel.
• Beide methoden hebben last van ruis. – Wanneer er ruis in beeld is, dan wordt dat ook als een rand gezien. 2 1 0 -1 0
10
20
30
40
50
60
70
80
90
100
10
20
30
40
50
60
70
80
90
100
1 0 -1 0
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Edge detection en smoothing in één
Algoritme voor 1D Gaussian edge detection
• Smoothen gebeurt vaak door een Gaussiaan de convolueren over het beeld
1. Convolueer het beeld I met G’, het resultaat is een nieuw beeld R. 2. Bereken de absolute waarde van R. 3. Markeer de pieken in |R| die boven een drempelwaarde T voorkomt.
• Na het smoothen de eerste afgeleide nemen levert een edge detectie op.
De drempelwaarde is gekozen afhankelijk van het doel van de edge detection.
• Het kan echter gecombineerd: convolueer met de eerste afgeleide van de Gaussiaan.
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
3
Gaussiaanse edge detection in 2D •
Gaussiaanse convolutieoperator
•
Twee filters nodig: voor verticale en horizontale richting
•
Algorithme
Sobel versus Gaussiaan
origineel
Sobel
1. Convolueer het beeld I(x,y) met fV(x,y), het resultaat is RV 2. Convolueer het beeld I(x,y) met f H(x,y), het resultaat is RH 3. Bereken grootte
Gaussiaan
4. Bereken richting 5. Markeer de pieken in R(x,y) die boven een drempelwaarde T uitkomen. Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
2d Gaussiaan
3D informatie uit beeld halen
•
• Om bepaalde taken uit te voeren is het nodig om informatie over de diepte uit het beeld te halen.
Een 5x5 convolutiematrix voor een Gaussiaan
– Vb. Een robot in een supermarkt moet navigeren en manipuleren.
• Verschillende mogelijkheden – – – – – •
Beweging. Stereovisie. Textuur. Schaduwen. Contouren.
De som van alle elementen is 1, dit betekend concreet dat de helderheid van het beeld niet toe- of afneemt.
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
3D uit beweging
Optical flow
• Wanneer camera en objecten relatief bewegen t.o.v. elkaar, dan noemt men de beweging optical flow.
• Optical flow wordt voorgesteld door twee vectoren
• Tussen 2 lichtverschillende beelden zoek je de zelfde pixels. – Bijvoorbeeld door som van gekwadrateerde verschillen
– Of door correlatie
– Wanneer die maat maximaal is heb je juiste Dx en Dy gevonden.
• De optical flow op positie (x,y) is dan Dx/Dt en Dy/Dt. Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
4
Optical flow…
Egomotion uit optical flow
• Het berekenen van optical flow heeft corresponderende punten nodig tussen twee opeenvolgende beelden.
• Stel je kent de translatiesnelheid T en hoeksnelheid de snelheden van de punten in het beeld zijn dan: "
• Lukt niet wanneer er weinig structuur is!
"!
!
– Onmogelijk om optical flow te berekenen van egale objecten (bv. roterende effen bol).
van de camera,
"
"!
!
• Vereenvoudigen tot enkel translatie "
"!
"
"!
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Toepassing egomotion
Hoe diepte uit optical flow halen? halen? • Wanneer meerdere beelden bekeken worden kan je uit de snelheid waarmee elk punt beweegt afleiden hoever het van de camera staat. – Bv. Kijken uit het treinraam.
Biorobotic Vision Laboratory (2001)
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Stereovisie
Diepte uit twee beelden
• Binoculaire stereo-opsis: het berekenen van diepte uit een beeld dat vanuit twee verschillende oogpunten is gemaakt.
• Beelden staan allebei op zelfde lijn. %
– Meestal m.b.v. twee camera die op een verschillende plaats en onder een verschillende hoek staan. Perceived object
!
Left image
!
Right image
#
Autonomous Systems – Tony Belpaeme
$
Autonomous Systems – Tony Belpaeme
5
Voorbeeld
Diepte uit twee beelden • Beelden staan onder verschillende fixatiehoek
%
! !
!
Kurt Konolidge, small vision system Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Diepte uit twee beelden
Voorbeeld
• Kost tijd om steeds op alle punten van het beeld te fixeren om de diepte te kennen. • Je fixeert op één punt P0, hierna kan je de diepte van andere punten berekenen. & !
&'
! Saccadic Eye Movement (1996) Cog Project, AI lab, MIT
#
$
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Diepte uit twee beelden, beelden, problemen
Diepte uit twee beelden, beelden, problemen
• Vereist een goede beschrijving van de optische en geometrische eigenschappen van de cameraopstelling.
• Je moet corresponderende punten terugvinden in elk camerabeeld. – Wordt moeilijk bij effen vlakken.
• Je kan gebruik maken van features. – – – –
Afstand tussen camera’s (base line). Focale afstand f moet. Hoek die elke camera maakt. Rotatiepunt van elke camera (rotatie om brandpunt of midden van lens vereenvoudigt de berekeningen). – Vervormingen van de lens.
Autonomous Systems – Tony Belpaeme
– Bv. Eerst edge detection, dan op zoek naar corresponderende punten.
Autonomous Systems – Tony Belpaeme
6
Voorbeeld
Diepte uit textuur • Objecten worden kleiner naarmate ze verder wegstaan van de camera. • Hiermee kan diepte berekend worden: shape from shading.
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Diepte uit contouren
Diepte uit contouren
• Wanneer men een lijntekening heeft, kan men lijnen markeren.
• Aan de hand van de markeringen kan men afleiden in welke oriëntatie de objecten zich bevinden, en hoe hun 3D structuur is.
– Convex, concaaf. – Een lijn welke andere lijnen verbergt. – Een limb.
• Problemen
• Er bestaat ook een beperkte verzamelig mogelijkheden waarop lijnen elkaar kunnen snijden.
3
3
1
5
3
5
1
3
– Enkel toepasbaar op netjes afgelijnde objecten, bv. natuurlijke objecten lukken moeilijk. – Nooit slaagt men erin om een scherpe contour uit een beeld of te leiden (altijd last van schaduwen, occlusies, onvolledige lijnen, …)
5
7
1
3
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Objectherkenning
Oplossingen
•
Het herkennen van gezichten, voorwerpen, …
•
Je kan het beeld vereenvoudigen tot een nonvariant beeld
•
Toepassingen
•
Het herkennen van een beeld doe je door de afstand te nemen tussen het beeld en een referentie.
•
Voorbeeld
– – – –
•
Biometrisch identificeren. Tekstherkenning. Image base retrieval. Herkennen van gezichtsexpressies.
– Bijvoorbeeld door edge detection te doen.
A.
B.
C.
Groot Probleem – Beelden zijn erg variabel: ze verschillen in lichtinval, lichtkwaliteit, cameraperspectief.
Sum(A-A) = 0 Sum(A-B) = 194 Sum(A-C) = 989 Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
7
Kleur
Informatie in kleur
• Vooruitgang in cameratechnologie en rekenkracht. • Om kleur voor te stellen hebben we 3 kanalen nodig ipv. 1.
• Kleur is makkelijk te herkennen en snel uit beeld te halen. – Men kan markeringen aanbrengen om de visuele perceptie te helpen.
• Kleur heeft verrassend eenvoudige toepassingen. 198 198 199 199 200 200 200 200 200 201 200 200 200 204 202 204 159 110 116 116
200 199 201 201 202 202 202 202 203 202 198 199 201 206 205 205 151 107 116 115
202 202 203 203 202 202 202 202 203 203 198 196 202 205 207 206 144 106 117 116
204 203 203 203 202 202 202 202 202 202 197 193 202 202 209 206 138 109 118 118
205 205 203 203 203 203 202 202 202 202 196 190 200 200 208 208 135 112 120 119
205 205 202 202 202 201 201 201 201 200 194 188 198 197 208 208 135 114 121 120
206 205 199 206 206 201 201 205 202 196 200 181 178 204 200 214 124 114 120 121
207 206 201 206 208 206 205 205 198 188 208 186 180 208 202 217 140 115 117 118
209 208 206 206 206 203 204 204 199 191 191 160 157 203 203 206 140 112 125 126
211 210 212 206 201 199 201 203 201 197 164 134 131 193 216 201 136 124 131 133
212 212 214 208 205 204 203 199 193 190 179 167 147 179 219 206 132 128 125 128
213 212 213 212 214 215 207 192 180 175 194 203 173 151 198 212 136 125 125 128
214 212 211 211 213 213 202 185 178 179 186 195 179 136 183 217 142 127 127 130
212 212 210 208 206 203 192 182 185 196 197 191 191 150 184 211 130 117 119 122
217 204 215 213 226 210 192 194 186 194 202 197 185 175 145 205 143 116 121 133
210 207 210 213 207 201 181 172 166 197 184 187 177 159 127 171 136 116 118 106
211 215 211 217 211 220 172 177 185 190 196 198 188 174 154 167 144 111 126 111
– Bv. Gezichtsdetectie.
212 215 230 215 206 209 219 210 204 216 207 209 220 217 219 224 215 217 111 69 108 120 52 68 134 69 90 82 33 127 65 5 197 68 2 185 70 3 165 78 3 143 87 4 103 101 12 68 131 84 105 124 122 125 117 116 125 126 132 117
• Kleur duidt vaak de randen aan van objecten. – Doch, niet altijd. Bv., kleurrijke kleren, voetbalbal, …
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Segmenteren van het beeld
Segmenteren
• Het groeperen van pixels in groepen die homogeen zijn volgens één of ander criterium.
• Two manieren van segmenteren
– Deel een beeld I(x,y) op in overlappende segmenten Ri zo dat ∪ Ri ≤ 1 en ∩ Ri ≥ 0
– Je weet waar je naar op zoek bent (je hebt een set eigenschappen waaraan een segment moet voldoen).
• Segmenteren van kleur: groeperen van pixels die hetzelfde kleur hebben en die naburig zijn.
– Je weet het niet: hier heb je een 2 passen nodig • pass 1 om verschillende prototypes te vinden. • pass 2 om het beeld te segmenteren.
– Belangrijke en veelgebruikte operatie. – Een eerste stap in het categoriseren, discrimineren, herkennen, …
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
Algoritme
Voorbeeld van kleur in visuele perceptie
• Region growing
!
" " ← " " # $ ←
"
" % &
$
Robocup team Freiburg (2001)
Autonomous Systems – Tony Belpaeme
Autonomous Systems – Tony Belpaeme
8
Active vision • Een meer biologische manier van visuele perceptie. • Eigenschappen – – – –
Verwerk enkel wat je nodig heb. Selective attentie. Bewegende camera. Inspiratie uit biologie, bv. gebruik maken van neurale netwerken.
Autonomous Systems – Tony Belpaeme
9