Academiejaar 2006-2007
Departement Industri¨ ele Wetenschappen BME-CTL Schoonmeersstraat 52 - 9000 Gent
Lokaliseren en volgen van personen en objecten met behulp van camera’s
Eindwerk voorgedragen tot het behalen van het diploma van INDUSTRIEEL INGENIEUR INFORMATICA
Sofie DE COOMAN Promotoren:
Koen VAN DE WIELE Gert VAN HOEY (BARCO N.V., 8500 Kortrijk)
Academiejaar 2006-2007
Departement Industri¨ ele Wetenschappen BME-CTL Schoonmeersstraat 52 - 9000 Gent
Lokaliseren en volgen van personen en objecten met behulp van camera’s
Eindwerk voorgedragen tot het behalen van het diploma van INDUSTRIEEL INGENIEUR INFORMATICA
Sofie DE COOMAN Promotoren:
Koen VAN DE WIELE Gert VAN HOEY (BARCO N.V., 8500 Kortrijk)
Woord vooraf Vooreerst wil ik mijn externe promotor, Dhr. Gert Van Hoey, bedanken voor de aangename samenwerking. Bij hem kon ik steeds terecht voor begeleiding en feedback. Zijn advies leidde soms tot nieuwe inzichten. Daarnaast mijn oprechte dank aan mijn interne promotor, Dhr. Koen Van de Wiele, voor de begeleiding en opvolging van mijn eindwerk. Ook aan het bedrijf Barco een woord van dank voor het mogelijk maken van de stage en de vlotte organisatie. Tenslotte nog een speciaal woord van dank aan mijn ouders, dankzij hen kon ik deze opleiding volgen.
Sofie De Cooman Landegem, mei 2007
Abstract Real-time lokalisatie van een observator die een camera draagt in een ruimte waar merktekens werden aangebracht. Wanneer de camera merktekens in beeld krijgt, worden deze uit het beeld ge¨extraheerd en ge¨ıdentificeerd. Via de gekende locaties van de merktekens in de kamer en de locaties van de merktekens in het beeldvlak kan de locatie van de observator in de kamer bepaald worden. Een toepassing (C++/Matlab) werd geschreven die geschikte merktekens genereert, merktekens extraheert uit het beeld en de locatie bepaalt. Tot slot werd een voorbeeldtoepassing ontworpen voor interactieve 3D visualisatie.
Real-time localisation of an observer which carries a camera in a room where markers have been placed. When markers are present in a camera frame, they will be extracted and identified. By matching the known locations of the markers in the room with the locations of the markers in the frame, the location of the observer in the room can be determined. An application (C++/Matlab) was developed to generate suitable markers, extract markers from a frame and determine the location of the observer. Finally, an example application was developed for interactive 3D visualisation.
Inhoudsopgave Woord vooraf
2
Abstract
3
Inhoudsopgave
6
Lijst van figuren
7
Lijst van tabellen
12
Inleiding
13
1 Bestaande systemen 1.1 ARToolkit . . . . . . . . . . . . . 1.1.1 Opsporen Merktekens . . 1.1.2 Positiebepaling . . . . . . 1.1.3 Calibratie . . . . . . . . . 1.1.4 Beperkingen . . . . . . . . 1.2 ARTag . . . . . . . . . . . . . . 1.3 Vergelijking ARToolkit en ARTag 1.4 Andere . . . . . . . . . . . . . . . 1.5 Besluit . . . . . . . . . . . . . . .
. . . . . . . . .
15 15 15 17 19 20 21 23 25 28
. . . . . . . .
29 29 29 30 31 32 33 33 34
2 Merktekens 2.1 Criteria . . . . . . . 2.2 Gekozen aanpak . . 2.3 Algemene opbouw . 2.4 Opbouw applicatie . 2.4.1 Configuratie . 2.4.2 Pariteitsbits . Foutdetectie . Foutcorrectie
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . . 4
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
Inhoudsopgave
2.5 2.6
Rotatiedetectie . . . . . . . . 2.4.3 Generatie . . . . . . . . . . . 2.4.4 Extractie ID . . . . . . . . . 2.4.5 Interface met andere modules Specifieke aanpassingen . . . . . . . GUI . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
3 Extractie en identificatie merktekens 3.1 Basisbegrippen . . . . . . . . . . . . . . . . . 3.1.1 Convolutie . . . . . . . . . . . . . . . 3.1.2 Homografie . . . . . . . . . . . . . . . 3.1.3 Ruis . . . . . . . . . . . . . . . . . . . 3.1.4 Gaussian smoothing . . . . . . . . . . 3.2 Uitvoering onderzoek . . . . . . . . . . . . . . 3.3 Criteria . . . . . . . . . . . . . . . . . . . . . 3.4 Algemene werkwijze . . . . . . . . . . . . . . 3.5 Edge detection (randdetectie) . . . . . . . . . 3.5.1 Gradi¨ent gebaseerde randdetectie . . . Roberts, Prewitt, Sobel . . . . . . . . Canny randdetectie . . . . . . . . . . 3.5.2 Laplacian of Gaussian (LoG) . . . . . 3.6 Edge tracking . . . . . . . . . . . . . . . . . . 3.7 Onderzoek krommming . . . . . . . . . . . . 3.8 Linken contouren . . . . . . . . . . . . . . . . 3.8.1 Extractie segmenten, bepalen hoeken . 3.9 Sampling bitpatroon . . . . . . . . . . . . . . 3.10 Extra eliminatiecriteria . . . . . . . . . . . . 3.11 Eindresultaat . . . . . . . . . . . . . . . . . . 3.12 Prestaties . . . . . . . . . . . . . . . . . . . . 3.12.1 Grootte gedetecteerd merkteken . . . 3.12.2 Hoek tussen camera en merkteken . . 3.12.3 Kwaliteit camerabeelden . . . . . . . . 3.12.4 Beweging object dat de camera draagt 3.12.5 Lichtgevoeligheid . . . . . . . . . . . . 3.12.6 Occlusie . . . . . . . . . . . . . . . . . 3.13 Performantie . . . . . . . . . . . . . . . . . . 3.14 Interface met andere modules . . . . . . . . . 3.15 Configuratie . . . . . . . . . . . . . . . . . . . 3.16 GUI . . . . . . . . . . . . . . . . . . . . . . .
5
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
35 35 38 39 39 40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43 43 43 45 46 47 49 50 50 51 52 52 54 58 62 67 75 76 78 80 81 83 83 86 86 87 87 88 88 89 89 91
Inhoudsopgave 4 Positiebepaling 4.1 Pinhole camera model . . . . 4.2 Calibratie camera . . . . . . . 4.2.1 Configuratie . . . . . . 4.2.2 GUI . . . . . . . . . . 4.3 Principe positiebepaling . . . 4.4 Interface met andere modules 4.5 Plaatsing merktekens . . . . . 4.5.1 Configuratie . . . . . . 4.6 Nauwkeurigheid . . . . . . . . 4.7 Performantie . . . . . . . . . 4.8 GUI . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
93 93 97 99 100 101 105 106 108 110 113 114
5 Voorbeeldtoepassing 117 5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.2 GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Besluit
120
Bibliografie
123
Bijlage: Inhoud CD
126
6
Lijst van figuren 1
Situatieschets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Detectie merktekens: 1. Origineel beeld, 2. beeld na thresholding, 3. geconnecteerde gebieden na segmentatie, 4. uitwendige omtreklijn afgeleid uit 3, 5. bepaling hoeken en randen merktekens, 6. merktekens herkend en eventueel bedekt met synthetische objecten (Fiala, 2004) . . . . . . . . . . . . . . . . . 1.2 Modellen van het inwendig patroon van een merkteken (Fiala, 2004) . . . . . 1.3 Relatie tussen co¨ordinaten merkteken en camera co¨ordinaten(Kato & Billinghurst, 1999) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Correctie op de richtingsvectoren van de koppels geprojecteerde parallelle zijden van een merkteken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Illustratie van de eerste en eventuele tweede stap van het calibratieproces (Hitlab, Z.D.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Schatting afstand ARToolkit steeds groter dan werkelijke afstand . . . . . . 1.7 Gemiddelde fout in x- en y-richting (bovenaan). Fout in x- en y-richting i.f.v. de hoek (in °, onderaan) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Detectie merktekens: 1. originele afbeelding, 2. randdetectie, 3. groepering in vierhoeken, 4. gedetecteerde merktekens met geldige code (Fiala, 2004) . . . 1.9 Camera en label gebruikt bij PTrack. De retro-reflectieve markeringen aangebracht op het label kunnen opgespoord worden dankzij de IR LED’s aan de camera. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10 Detectie van merktekens bij ARStudio. Links: search mode, unwarping van het merkteken en zoeken van het best passende gekende merkteken. Rechts: tracking mode, hoekdetectie. . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.1
2.1 2.2 2.3 2.4 2.5 2.6
Een voorbeeld van een merkteken . . . . Structuur klassen generatie merktekens . Klassen foutdetectie . . . . . . . . . . . Klassen foutcorrectie . . . . . . . . . . . Klassen rotatiedetectie . . . . . . . . . . Werking CornerRotationDetector . . . . 7
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
16 16 17 18 19 21 21 22
26
26 30 31 34 34 35 35
Lijst van figuren 2.7 2.8 2.9 2.10 2.11
Merktekengeneratie: bitpatronen merktekens voldoende verschillend Verschillende ori¨entaties leveren hetzelfde ID . . . . . . . . . . . . . Overzichtsmenu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GUI merktekengeneratie . . . . . . . . . . . . . . . . . . . . . . . . . GUI merktekengeneratie, genereren van een enkel merkteken . . . .
3.1 3.2 3.3
2-dimensionale convolutie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-dimensionale convolutie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Links: oorspronkelijk merkteken, rechts: gedetecteerd merkteken. Relatie tussen beide via perspectieve transformatie. . . . . . . . . . . . . . . . . . . . . . Voorbeeld kunstmatig toevoegen ruis. Links: origineel, midden: Gaussiaanse ruis met variantie 0.02 en gemiddelde waarde 0, rechts: 10% salt & pepper ruis 1-D Gaussfunctie (gemiddelde 0, σ 1.0) (links) en voorstelling m.b.v. een kernel (rechts) (R. Fisher & Wolfart., 2003). . . . . . . . . . . . . . . . . . . . . . . 2D-Gaussfunctie (gemiddelde 0, σ 1.0) (links) en voorstelling m.b.v. een kernel (rechts) (R. Fisher & Wolfart., 2003). . . . . . . . . . . . . . . . . . . . . . . Resultaat na convolutie met Gauss-kernel op afbeeldingen met ruis. Links: Gaussiaanse ruis, rechts: Salt & pepper ruis . . . . . . . . . . . . . . . . . . Profiel van een ideale rand (links) en een re¨ele rand (rechts) (Gonzalez & Woods, 2001) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Profiel, 1e en 2e afgeleide van een rand (Gonzalez & Woods, 2001) . . . . . . Maskers voor berekening van de gradi¨ent (Gonzalez & Woods, 2001). . . . . . Origineel testbeeld voor randdetectie . . . . . . . . . . . . . . . . . . . . . . . Resultaten voor Sobel (links), Prewitt (midden) en Roberts (rechts) . . . . . Resultaten voor Sobel(links), Prewitt(midden) en Roberts (rechts) bij een threshold-waarde gelijk aan nul . . . . . . . . . . . . . . . . . . . . . . . . . . Non-maximum Suppression (CVonline, 1996) . . . . . . . . . . . . . . . . . . Test Canny edge detector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Canny bij merktekens met een breedte van 21 pixels. . . . . . . . . . . . . . . Canny bij merktekens met een breedte van 12 pixels. . . . . . . . . . . . . . . Kandidaat-merktekens bij een breedte van 21 pixels (links) en 12 pixels (rechts). Profiel, 1e en 2e afgeleide van een rand bij toevoegen van Gaussiaanse ruis met σ 0.1 (Gonzalez & Woods, 2001). . . . . . . . . . . . . . . . . . . . . . . . . Functie Laplacian of Gaussian en bijhorend masker bij σ gelijk aan 1.4 . . . . Resultaat na convolutie met LoG-kernel. . . . . . . . . . . . . . . . . . . . . . Zoeken van nuldoorgangen via lineaire interpolatie. . . . . . . . . . . . . . . . Resultaat toepassen LoG op figuur 3.17 (links). . . . . . . . . . . . . . . . . . Toepassen van een threshold voor de LoG-methode. . . . . . . . . . . . . . . Verband tussen het teken van de 2e afgeleide en de overgang van de intensiteiten.
3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24 3.25
8
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
36 40 40 41 42 43 44 45 46 48 48 49 51 51 53 53 54 54 55 56 57 57 58 58 59 60 60 60 61 63
Lijst van figuren 3.26 Mogelijke labels voor punten op segmenten in verschillende richtingen. . . . 3.27 Zoekvensters vanuit een randpunt naar een volgend randpunt op een zelfde segment met bijhorende prioriteiten, bij zoeken in wijzerzin. . . . . . . . . . 3.28 Zoekvensters vanuit een randpunt naar een volgend randpunt op een zelfde segment met bijhorende prioriteiten, bij zoeken in tegenwijzerzin. . . . . . . 3.29 Zoekvensters vanuit een randpunt naar een volgend randpunt op een volgend segment met bijhorende prioriteiten, bij zoeken in wijzerzin. . . . . . . . . . 3.30 Zoekvensters vanuit een randpunt naar een volgend randpunt op een volgend segment met bijhorende prioriteiten, bij zoeken in tegenwijzerzin. . . . . . . 3.31 Kromming in de punten van een contour van een merkteken (σ = 3) met de lokale minima en maxima. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.32 Voorbeeld voor het elimineren van valse hoeken m.b.v. het criterium angle of corner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.33 Links: Testafbeelding, gemaakt met minst goede camera (wazig beeld). Maxima (rood) voor de kromming die als hoeken herkend werden en naburige minima (geel) bij een σ gelijk aan 4 (midden) en 9 (rechts). . . . . . . . . . . . 3.34 Kromming in punten van de contour bij σ gelijk aan 4. Maxima die overeenkomen met hoeken werden aangeduid in rood en worden rechts in een lijst vermeld. De hoeken die ook de echte hoeken zijn van het merkteken, werden aangeduid in de lijst. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.35 Kromming in punten van de contour bij σ gelijk aan 9. Maxima die overeenkomen met hoeken werden aangeduid in rood. . . . . . . . . . . . . . . . . . 3.36 Lokale Maxima (rood) die overeenkomen met hoeken en naburige minima (geel) bij een σ gelijk aan 4 (links) en 9 (rechts). . . . . . . . . . . . . . . . . . . . 3.37 Maxima (rood) en minima (geel) bij een σ gelijk aan 9 (links) en 3 (rechts). 3.38 Maskers gebruikt bij achteraf linken contouren. . . . . . . . . . . . . . . . . 3.39 Voorbeeld succesvol toepassen van het achteraf linken van contouren. . . . . 3.40 Kromming hoeken, naburige minima (rood) en eindpunten segmenten (groen). 3.41 Minima (geel) en maxima (rood) van de kromming, eindpunten segmenten (blauw), uiteindelijke hoeken (paars). . . . . . . . . . . . . . . . . . . . . . . . 3.42 Unwarping beeld merkteken, origineel beeld (links), beeld merkteken na unwarping (midden) en na thresholding (rechts). . . . . . . . . . . . . . . . . . . 3.43 Samplingpunten aanpassen aan de vorm van het merkteken. . . . . . . . . . 3.44 Extra controles bij sampling. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.45 Overzicht extractie merktekens. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.46 Minimale breedte herkende merktekens met een bitpatroon van 2x2. Boven: randdikte 1, Onder: randdikte 2 . . . . . . . . . . . . . . . . . . . . . . . . . 3.47 Minimale breedte herkende merktekens met een bitpatroon van 3x3. Links: randdikte 1, Rechts: randdikte 2 . . . . . . . . . . . . . . . . . . . . . . . . . 9
63 65 66 66 67 69 70
71
72 73 73 74 75 76 77 77 78 79 79 81 84 84
Lijst van figuren 3.48 Minimale breedte herkende merktekens met een bitpatroon van 4x4. Links: randdikte 1, Rechts: randdikte 2 . . . . . . . . . . . . . . . . . . . . . . . . . 3.49 Minimale breedte herkende merktekens met een bitpatroon van 6x6. Links: randdikte 1, Rechts: randdikte 2 . . . . . . . . . . . . . . . . . . . . . . . . . 3.50 Minimale hoek tussen camera en vlak merkteken, links: merktekens met 4x4 bits, rechts: merktekens met 6x6 bits. . . . . . . . . . . . . . . . . . . . . . . 3.51 Prestaties bij aanwezigheid van een aanzienlijke hoeveelheid Gaussiaanse ruis (gemiddelde waarde 0, variantie 0.02) . . . . . . . . . . . . . . . . . . . . . . 3.52 Prestaties bij variabele lichtinval. . . . . . . . . . . . . . . . . . . . . . . . . 3.53 Merktekens gedetecteerd bij onderbreking door rand figuur. . . . . . . . . . 3.54 GUI merktekenextractie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.55 Weergeven camerabeelden met kenmerken aangeduid in figuur 3.54. . . . . . 4.1 4.2 4.3 4.4 4.5 4.6 4.7
4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16
5.1 5.2 5.3
Geometrie van het pinhole camera model. . . . . . . . . . . . . . . . . . . . . Perspectieve projectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Co¨ordinaten beeldvlak (x, y) en camera-co¨ordinaten stelsel (xcam , ycam ). . . Translatie en rotatie tussen camera- en wereld-co¨ordinatenstelsel. . . . . . . Distorsie, links: oorspronkelijk beeld, projecties van rechte lijnen zijn gebogen. Rechts: beeld na correctie distorsie, projecties van rechte lijnen zijn nu recht. Schaakbordpatroon gebruikt voor calibratie. . . . . . . . . . . . . . . . . . . Calibratie, links: hoeken calibratiepatroon nodig voor calibratie opgespoord, midden: terugprojectie hoeken via parameters calibratie zonder rekening te houden met distorsie parameters, rechts: idem, maar nu werden de distorsie parameters wel gebruikt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GUI calibratie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minimalisatie object-space error . . . . . . . . . . . . . . . . . . . . . . . . . Resultaat test paper (Lu et al., 2000) . . . . . . . . . . . . . . . . . . . . . . Test met 3 merktekens in beeld . . . . . . . . . . . . . . . . . . . . . . . . . Test met 2 merktekens in verschillend vlak . . . . . . . . . . . . . . . . . . . Uitvoeringstijd en aantal iteraties i.f.v. het aantal referentiepunten (Lu et al., 2000). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Uitvoeringstijd bij een constant aantal referentiepunten i.f.v. de tolerantie (R− Rcalc . (WindF¨all, 2005) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GUI positiebepaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weergave gedetecteerde merktekens en positie en eventueel terugprojecties van de hoekpunten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Voorbeeldtoepassing: rendering scene m.b.v. Ogre3D . . . . . . . . . . . . . GUI voorbeeldtoepassing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Illustratie Harris Corner detector. . . . . . . . . . . . . . . . . . . . . . . . . 10
85 85 86 86 87 88 91 92 93 93 94 95 96 97
98 100 102 110 112 112 113 114 115 116 117 119 121
Lijst van figuren 5.4
Illustratie feature tracking (Intel, 2007). . . . . . . . . . . . . . . . . . . . . .
11
122
Lijst van tabellen 1.1
Bereik detectie in functie van zijde merkteken (Hitlab, Z.D.)
4.1 4.2 4.3
Test met 1 merkteken met DLT-algoritme . . . . . . . . . . . . . . . . . . . . Test met 1 merkteken met globaal convergerend algoritme . . . . . . . . . . Test met 1 merkteken met globaal convergerend algoritme en RPP-optimalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Test met 3 merktekens met globaal convergerend algoritme en RPP-optimalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Test met 2 merktekens in verschillend vlak met globaal convergerend algoritme
4.4 4.5
12
. . . . . . . . .
20 111 111 111 112 113
Inleiding
Figuur 1: Situatieschets
Camerabeelden worden vaak gebruikt om automatisch mensen of objecten te lokaliseren in een kamer. Een mogelijkheid is te werken met vast opgestelde camera’s en de personen en objecten dan te detecteren, lokaliseren en volgen op basis van de camerabeelden. Bij deze thesis werd echter een andere mogelijkheid bekeken: het voorwerp of de persoon draagt zelf de camera en de lokalisatie van persoon of voorwerp gebeurt door in real-time in het camerabeeld merktekens te lokaliseren die in de kamer aangebracht zijn. Deze techniek wordt bv. ook toegepast in toepassingen van augmented reality. Dit wordt ge¨ıllustreerd in de figuur bovenaan. De camera is bv. vastgemaakt aan een bril en krijgt merktekens in beeld. De posities van de merktekens in de kamer zijn gekend t.o.v. een vast co¨ordinatenstelsel in de kamer, het zogenaamde wereld-co¨ordinatenstelsel (3D). De merktekens worden nu in het beeld gelokaliseerd (2D) en ge¨ıdentificeerd. Via de overeen13
komsten tussen de 2D- en 3D-locaties kan nu de positie van de camera t.o.v. het wereldco¨ordinatenstelsel bepaald worden. Het project bestaat uit een aantal onderdelen en deze scriptie werd dan ook analoog gestructureerd: Eerst werden een aantal bestaande systemen onderzocht en vergeleken die een analoog principe toepassen. Bepaalde idee¨en die bij deze systemen voorkomen konden hergebruikt worden in de eigen toepassing. Dit wordt uitvoering besproken in het eerste hoofdstuk. In hoofdstuk 2 wordt het gekozen ontwerp van de merktekens toegelicht. Deze merktekens kunnen gegenereerd worden a.d.h.v. een aantal parameters die door de gebruiker worden gespecifieerd. De merktekens kunnen nu uit het beeld worden ge¨extraheerd en ge¨ıdentificeerd. De gebruikte werkwijze komt gedetailleerd in hoofdstuk 3 aan bod. De prestaties van deze fase worden ook besproken i.f.v. een aantal criteria die voorop werden gesteld. Nu kan de eigenlijke positiebepaling gebeuren, zoals in hoofdstuk 4 wordt besproken. Eerst wordt het model en de bijhorende calibratie van de camera toegelicht om dan over te gaan naar de methode voor de eigenlijke positiebepaling. De posities van de merktekens in de kamer kunnen hierbij ook worden gegenereerd. Tot slot werden de prestaties van de positiebepaling onderzocht. Tenslotte werd een voorbeeldtoepassing ontworpen voor interactieve 3D-visualisatie. Hierbij wordt het zicht op een virtuele ruimte aangepast naargelang de positie van de camera in de echte kamer. Hoe dit precies gebeurt, komt in hoofdstuk 5 aan bod.
Hoofdstuk 1
Bestaande systemen 1.1
ARToolkit
ARToolkit is een bibliotheek van functies met als basis de lokalisatie van merktekens. ARToolkit werd ontwikkeld door Dr. Hirokazu Kato (Osaka Universiteit, Japan) en ondersteund door de Universiteit van Washington. Dit systeem is gratis en vrij eenvoudig in gebruik mede dankzij de uitgebreide documentatie (Hitlab, Z.D.). ARToolkit is dan ook een populair systeem bij toepassingen binnen Augmented Reality (AR). Hierbij wordt in real-time in de beelden, die worden vastgelegd door een camera, gezocht naar specifieke merktekens die worden gebruikt voor het positioneren van synthetische objecten.
1.1.1
Opsporen Merktekens
ARToolkit gebruikt vierkante merktekens met een zwartgekleurde rand en een willekeurig inwendig patroon om de merktekens te kunnen onderscheiden. Het opsporen van de merktekens gebeurt hierbij in 2 stappen (figuur 1.1). Eerst wordt gezocht naar vierzijdige contouren. Op basis van een bepaalde threshold (drempelwaarde) voor de grijswaarden van de pixels bekomt men een binair beeld (zwart-wit) en wordt het beeld ingedeeld in segmenten. Door het bepalen van de contouren van deze segmenten worden de vierhoeken eruit gefilterd. Als tweede stap wordt uit deze verzameling vierhoeken de aangebrachte merktekens ge¨ıdentificeerd. Dit gebeurt via de inwendige patronen van de merktekens. De hoekpunten van de vierhoeken worden opgespoord en worden de vierhoeken genormaliseerd via een perspectieve transformatie (Kato & Billinghurst, 1999). Hiertoe worden de hoeken van de vierhoeken gebruikt om een soort raster (homographie) te defini¨eren waarbinnen de grijswaarden van het inwendig patroon worden bemonsterd. Voor elk merkteken wordt door ARToolkit immers een configuratiebestand voorzien waarin voor het inwendige patroon per rotatie 4 modelrasters met grijswaarden worden gedefinieerd, telkens voor een andere belichtingsgraad. Dit wordt 15
Hoofdstuk 1. Bestaande systemen
Figuur 1.1: Detectie merktekens: 1. Origineel beeld, 2. beeld na thresholding, 3. geconnecteerde gebieden na segmentatie, 4. uitwendige omtreklijn afgeleid uit 3, 5. bepaling hoeken en randen merktekens, 6. merktekens herkend en eventueel bedekt met synthetische objecten (Fiala, 2004)
Figuur 1.2: Modellen van het inwendig patroon van een merkteken (Fiala, 2004)
ge¨ıllustreerd in figuur 1.2. Voor elke gedetecteerde vierhoek wordt een betrouwbaarheidswaarde cf (tussen 0.0 en 1.0) berekend die aangeeft in hoeverre de inhoud met een bepaald merkteken overeenkomt. Deze cf-waarde is de correlatieco¨effici¨ent ρ (Owen et al., Z.D.): !1/2
1 X X µI = I(x, y) xy x y
σI =
X X x
2
(I(x, y) − µI )
y
!1/2
1 X X P (x, y) µP = xy x y
σP =
X X x
2
(P (x, y) − µP )
y
Met P(x,y) het merkteken en I(x,y) de kandidaat-overeenkomst P P ρ=
x
y (I(x, y)
− µI )(P (x, y) − µP ) σI σP
16
(1.1)
Hoofdstuk 1. Bestaande systemen
1.1.2
Positiebepaling
Het correct positioneren van synthetische objecten vereist ook de berekening van de positie van de merktekens t.o.v. de camera. Dit wordt verder beschreven in hoofdstuk 4. Bij ARToolkit kan hiertoe de functie ARGetTransMat() of ARMultiGetTransMat(), bij gebruik van meerdere patronen, gebruikt worden (Hitlab, Z.D.). Deze functies geven een 3x4 transformatiematrix terug die correspondeert met de translatie en rotatie van de camera t.o.v. het co¨ordinatenstelsel van de merktekens. Dit is equivalent met de transformatie tussen het wereldco¨ordinatenstelsel en het camera-co¨ordinatenstelsel, ook wel de externe parameters genoemd, zoals beschreven in sectie 4.1.
Figuur 1.3: Relatie tussen co¨ ordinaten merkteken en camera co¨ordinaten(Kato & Billinghurst, 1999)
Xc V11 V12 V13 Wx Xm X Xm # m " Yc V21 V22 V23 Wy Ym V3x3 W3x1 = = Ym = Tcm Ym Z V Z 0 0 0 1 c 31 V32 V33 Wz Zm Zm m 1 0 0 0 1 1 1 1
(1.2)
Vergelijking 1.2 stelt de relatie voor tussen deze co¨ordinatenstelsels (zie ook figuur 1.3). Er wordt dus gezocht naar V3x3 (rotatie) en W3x1 (translatie). Twee parallelle zijden van het merkteken worden geprojecteerd op het beeldvlak en kunnen uitgedrukt worden via vergelijkingen 1.3. De parameters van deze vergelijkingen werden berekend bij het bepalen van de contour van het merkteken.
17
Hoofdstuk 1. Bestaande systemen
a1 x + b1 y + c1 = 0 P11 P12 P13 0 P22 P23 P= 0 0 1 0 0 0
a2 x + b2 y + c2 = 0 0 hxc Xc 0 hyc = Yc 0 h Zc 1 1 1
(1.3)
(1.4)
a1 P11 Xc + (a1 P12 + b1 P22 )Yc + (a1 P13 + b1 P23 + c1 )Zc = 0 a2 P11 Xc + (a2 P12 + b2 P22 )Yc + (a2 P13 + b2 P23 + c2 )Zc = 0
(1.5)
In vergelijking 1.4 stelt P de perspectieve projectie voor waarmee het beeld op het beeldvlak wordt gevormd. Deze matrix wordt bepaald via het calibratieproces, zoals hieronder wordt beschreven. Deze co¨effici¨enten komen overeen met de interne parameters uit sectie 4.1 Door de vergelijkingen 1.3 te vermenigvuldigen met h en hierin xc en yc in te vullen via vergelijking 1.4 bekomt men vergelijkingen 1.5. Deze stellen de twee vlakken voor die het cameracentrum (oorsprong camera-co¨ordinatenstelsel) verbinden met de geprojecteerde zijden.
Figuur 1.4: Correctie op de richtingsvectoren van de koppels geprojecteerde parallelle zijden van een merkteken
n1 en n2 stellen nu de normaalvectoren voor op deze vlakken. Het vectorieel product u1 = n1 ×n2 stelt dan de richtingsvector voor van het koppel parallelle zijden van het oorsponkelijke merkteken. Analoog wordt de richtingsvector u2 voor het andere koppel zijden bepaald. Deze zouden nu loodrecht op elkaar moeten staan, maar door fouten bij de beeldverwerking zal dit vaak niet het geval zijn. Ter compensatie worden twee eenheidsvectoren v1 en v2 (figuur 1.4) bepaald, loodrecht op elkaar en in het zelfde vlak als u1 en u2 . v3 is nu een eenheidsvector loodrecht op v1 en v2 . De rotatie V3x3 , vanh het co¨ordinatenstelsel van het merkteken naar dit i 1 2 3 van de camera, is bijgevolg bepaald door vt vt vt . De bepaling van de translatiecomponent W3x1 gebeurt via de hoekpunten van een opgespoord merkteken (Kato & Billinghurst, 1999). De co¨ordinaten hiervan in het wereldco¨ordinatenstelsel zijn gekend en hun projectie wordt in het beeld opgespoord. De gezochte co¨effici¨enten kunnen 18
Hoofdstuk 1. Bestaande systemen dan worden berekend via deze vier koppels punten in combinatie met vergelijkingen 1.2 en 1.4. De transformatiematrix P is nu bekend maar is meestal niet exact. De fout kan worden beperkt door nu via P de projecties van de hoekpunten van de merktekens te bepalen. Vervolgens wordt de som van de verschillen tussen de gemeten co¨ordinaten van deze punten in het beeld (reeds gekend) en de berekende projecties geminimaliseerd. Op deze manier wordt de rotatiematrix geoptimaliseerd en de translatiematrix met deze nieuwe parameters opnieuw berekend zoals hierboven beschreven.
1.1.3
Calibratie
Figuur 1.5: Illustratie van de eerste en eventuele tweede stap van het calibratieproces (Hitlab, Z.D.)
ARToolkit voorziet zelf een configuratiebestand met defaultwaarden voor de interne parameters van de calibratie. Dit bestand is bruikbaar voor de meeste camera’s, maar men kan ook gebruik maken van een procedure om deze parameters te bepalen specifiek voor de gebruikte camera zodoende meer exacte resultaten te bekomen. Hiertoe legt de gebruiker een tiental afbeeldingen vast van het patroon links in figuur 1.5 vanuit verschillende hoeken en afstanden. De gebruiker duidt telkens alle punten van dit patroon in een specifieke volgorde aan. Dit proces wordt voornamelijk gebruikt voor de bepaling van de distorsie van de lens. Zoals beschreven in sectie 4.1 kan distorsie bijvoorbeeld zorgen voor een ’speldenkussen’ effect. De afstand tussen de verschillende punten wordt dan onregelmatig in tegenstelling tot de gekende constante afstand tussen de punten van het patroon. Men kan het houden bij deze eerste stap, maar als men wil werken met 3D-metingen wordt ook het uitvoeren van de tweede stap aangeraden. Hierbij moet de camera loodrecht t.o.v. het patroon rechts in figuur 1.5 worden opgesteld. Er moeten vijf afbeeldingen worden vastgelegd, waarbij het patroon telkens 10 cm verder wordt geplaatst. Dit maakt het proces praktisch wel moeilijker uitvoerbaar. De gebruiker wordt dan geacht de lijnen van het rooster zo goed mogelijk te laten overlappen met verplaatsbare en vervormbare lijnen en dit in een welbepaalde volgorde. Dit zorgt vooral voor een goede schatting van de brandpuntsafstand en de overige parameters.
19
Hoofdstuk 1. Bestaande systemen
1.1.4
Beperkingen
Het systeem zoals hierboven beschreven lijkt op het eerste zicht een onmiddellijke oplossing te bieden voor ´e´en van de doelstellingen. In praktijk echter stuitten we op enkele cruciale beperkingen. Tabel 1.1: Bereik detectie in functie van zijde merkteken (Hitlab, Z.D.)
zijde merkteken (cm)
bereik detectie (cm)
6.99
40.64
8.89
63.50
10.80
86.36
18.72
127.00
Naargelang de zijde van een merkteken groter is, wordt het bereik waarover het wordt herkend groter (tabel 1.1). Dit bereik blijft echter te beperkt voor het vooropgestelde doel. Het resultaat hangt ook enigszins af van het inwendige patroon: hoe complexer dit patroon, hoe kleiner het bereik waarover het merkteken wordt gedetecteerd. Dit alles wordt ook bevestigd door (Malbezin et al., 2002). De nauwkeurigheid van de positiebepaling (enkel de translatie) door ARToolkit wordt hier getest met een eenvoudig herkenbaar patroon met een grootte van 20 cm x 20 cm en dit voor ’grote’ afstanden (1 m - 3 m). ARToolkit wordt namelijk vooral gebruikt in AR-toepassingen waar het patroon vaak op nauwelijks een armlengte van de camera is verwijderd. Het merkteken werd nauwelijks meer herkend op een afstand boven de 2.5 m. Metingen werden uitgevoerd op een afstand van 1 m, 1.5 m, 2 m en 2.5 m (een bereik van 1.5 m) en telkens om de 15° rond het merkteken. Figuren 1.6 en 1.7 tonen de resultaten. De fout stijgt naarmate de afstand tussen de camera en het merkteken toeneemt. De berekende afstand blijkt steeds groter te zijn dan de werkelijke afstand waarbij de fout in x-richting steeds groter is dan deze in y richting. Bovendien hangt de fout in x- en y-richting sterk af van de hoek. In x-richting blijkt deze nauwkeurig te zijn bij hoeken van 90° en 270°, terwijl dit in y-richting bij 90° en 180° het geval is. Deze metingen werden wel uitgevoerd met ´e´en camera (1394 Firewire Pyro WebCam) en ´e´en patroon. Deze test herhalen met een andere camera, een ander patroon, andere afstanden. . . zou waarschijnlijk andere resultaten geven. Hieruit blijkt wel dat de positiebepaling beter kan. Bij deze test werden de interne parameters van de calibratie manueel aangepast, aangezien het calibratieproces door ARToolkit vaak niet nauwkeurig genoeg is. Voor AR-toepassingen hoeft 20
Hoofdstuk 1. Bestaande systemen
Figuur 1.7: Gemiddelde fout in x- en y-richting (bovenaan). Fout in x- en y-richting i.f.v. de hoek (in °, onderaan)
Figuur 1.6: Schatting afstand ARToolkit steeds groter dan werkelijke afstand
deze schatting niet nauwkeurig te zijn (Piekarski & Thomas, 2002) wanneer het genereren van synthetische objecten eveneens met ARToolkit gebeurt. Het effect van deze interne parameters wordt bij het tekenen immers weer teniet gedaan, waardoor deze objecten op de juiste plaats terecht komen. Bij rechtstreeks gebruik van de resultaten van de positiebepaling dient de calibratie wel zo nauwkeurig mogelijk te gebeuren.
1.2
ARTag
ARTag is een systeem ontwikkeld door M. Fiala en is gebaseerd op ARToolkit. Het zou een beter mechanisme voor patroonherkenning hanteren. Je kan dit systeem gebruiken (Fiala, 2007) voor niet-commerci¨ele doeleinden, bijvoorbeeld voor eigen AR-toepassingen. De broncode is echter niet beschikbaar, het systeem wordt geleverd onder de vorm van een library. Het zou dan ook moeilijk zijn om dit systeem aan te passen aan ons specifieke probleem als we dat zouden willen. In dit systeem worden er 2002 merktekens voorzien. Deze hebben eveneens een vierkante vorm en een een intern patroon dat bestaat uit een rooster van 6x6 witte en zwarte cellen.
21
Hoofdstuk 1. Bestaande systemen Het volledige merkteken bestaat uit 10x10 eenheden (randdikte van 2 eenheden). 1001 patronen hebben een zwarte rand met vanbinnen een witte achtergrond, vice-versa voor de andere 1001. Het interne patroon wordt aanzien als een bitpatroon, waarmee de merktekens duidelijk kunnen worden ge¨ıdentificeerd. Er is bijgevolg geen extra configuratiebestand nodig voor elk merkteken.
Figuur 1.8: Detectie merktekens: 1. originele afbeelding, 2. randdetectie, 3. groepering in vierhoeken, 4. gedetecteerde merktekens met geldige code (Fiala, 2004)
Het detectiealgoritme is gewijzigd t.o.v. ARToolkit (figuur 1.8). Hier wordt een methode voor randdetectie gebruikt. De randpixels met een grijswaarde boven een bepaalde drempelwaarde worden behouden en worden gegroepeerd in segmenten. Op hun beurt worden deze segmenten in vierhoeken gegroepeerd. Dit proces kan worden toegepast op 3 schalen: de originele grootte, de helft en een kwart van de originele afmetingen. Op deze manier kunnen onscherpe randen vaak beter worden gedetecteerd. Vervolgens wordt het inwendige patroon onderzocht. Het interne patroon met het bitpatroon wordt bemonsterd via een geschikt 6x6 rooster. De individuele bits worden gevonden via 22
Hoofdstuk 1. Bestaande systemen een threshold-waarde die wordt afgeleid uit de intensiteiten die voorkomen in de rand. Op deze manier bekomt men vier bitpatronen (´e´en bitpatroon voor elke rotatiepostie). Door de opbouw van de geldige bitpatronen vormt slechts ´e´en van de vier een geldige code. De gebruikte codes bestaan dus uit 36 bits. Slechts 11 bits vormen het ID, waarbij het eerste bit de kleur van de rand aangeeft. De overige bits worden gebruikt om unieke codes te garanderen over de 4 rotatierichtingen en helpen de detectie van het juiste ID. Er wordt namelijk gebruik gemaakt van FEC (Forward Error Correction) en CRC (Cyclic Redundancy Check) om bitfouten te detecteren en indien mogelijk te corrigeren. Bovendien wordt gebruik gemaakt van een XOR masker zodat de bitpatronen van opeenvolgende ID’s minder op elkaar zouden lijken. Binnen een toepassing worden immers vaak merktekens met opeenvolgende ID’s gebruikt en op deze manier wordt beter vermeden dat merktekens zouden omgewisseld worden door bits verkeerd te detecteren. De ID’s 682 en 1706 worden niet gebruikt omdat deze leiden tot een volledig zwart of wit binnenste patroon, deze vormen komen vaker in een omgeving voor terwijl ze niet als merkteken zijn bedoeld. Verder werden er 12 ID’s weggelaten aangezien de Hamming afstand tussen hun bitpatroon en (een rotatie van) het bitpatroon van een ander ID slechts gelijk is aan vier. Dit leidt makkelijker tot afleiden van een verkeerd ID. Verder werden er nog 10 ID’s weggelaten omdat hun bitpatroon te sterk lijkt op dit van het gespiegeld merkteken. Het is immers niet de bedoeling dat spiegelingen worden gedetecteerd. Door het dubbel gebruik (witte en zwarte achtergrond) zijn er dus 46 merktekens die niet gebruikt (versie 1) of afgeraden worden (versie 2). Aangezien de meeste toepassingen niet alle ID’s nodig hebben, werd een prioriteitslijst voorzien van de ID’s die het best worden gebruikt op basis van de Hamming afstand (Fiala, 2004), zie verder ook sectie 1.3.
1.3
Vergelijking ARToolkit en ARTag
ARTag verbetert twee tekortkomingen van ARToolkit. Enerzijds mogen bij ARToolkit de merktekens niet begrensd worden door een ander donker voorwerp. Na thresholding kunnen de vierhoekige vormen van de merktekens immers niet meer onderscheiden worden. Bij ARTag daarentegen mag een voorwerp de rand of zelfs een hoek onderbreken. Bij de randdetectie kan dit worden gecorrigeerd. Een klein deel van het inwendige patroon mag zelfs bedekt worden aangezien de foutcorrigerende systemen deze bitfouten kunnen corrigeren. Dit wordt ook ge¨ıllustreerd in figuur 1.8: het merkteken rechtsboven kan niet worden gedetecteerd omdat de pen teveel bits bedekt, het merkteken linksonder, waar minder bits zijn bedekt, kan daarentegen wel worden gedetecteerd. ARTag biedt bovendien betere resultaten in functie van de belichting. Door het gebruik van thresholding kan ARToolkit een merkteken vaak onvoldoende afscheiden van de omgeving.
23
Hoofdstuk 1. Bestaande systemen Wanneer de gebruiker bovendien een nieuw merkteken gebruikt, dient de belichting bij detectie dan ook gelijkaardig te zijn als deze bij aanmaken van het configuratiebestand voor het nieuwe merkteken. (Fiala, 2004) biedt een grondige vergelijking tussen ARTag en ARToolkit. Hier volgt een overzicht van de belangrijkste bevindingen: Detecteren van merktekens waar er geen zijn: ARTag en ARToolkit kregen dezelfde reeksen uiteenlopende beelden zonder merktekens voorgeschoteld. Bij een cf-waarde van 0.50, 0.70, 0.80 en 0.90 vond ARToolkit op een totaal van 16534 beelden in respectievelijk 1492, 213, 88 en 33 beelden minstens ´e´en merkteken. Men zou steeds een cf-waarde van 0.90 kunnen kiezen, maar dan zouden echte merktekens vaak niet meer herkend worden. ARTag vond in geen van de beelden een merkteken. Wanneer immers een patroon zou gevonden worden met een structuur gelijkaardig aan dit van een ARTag-merkteken, is de kans klein dat het inwendig bitpatroon een geldige ARTag-code voorstelt. Stel 2 = bijvoorbeeld dat de foutcorrigerende code 2 bits kan corrigeren. Er zijn dan 1+36+C36 667 codes die op ´e´en geldige 36-bit code worden afgebeeld (De juiste code + deze met ´e´en fout + deze met twee fouten) . Aangezien er 236 mogelijkheden zijn komt dit neer = 0.0039% geldige combinaties. op 4004∗667 236 Verwisselen van merktekens: Bij ARToolkit is dit afhankelijk van de merktekens die binnen een toepassing worden ingeladen. De correlatieco¨effici¨ent (vergelijking 1.1) tussen de merktekens bepalen, geeft een idee welke merktekens best worden gebruikt. Bij ARTag hangt dit af van twee factoren. Enerzijds zijn er systeemafhankelijke zaken (ruis. . . ) waardoor een bit verkeerd kan worden gedetecteerd. Anderzijds is er het onderscheid tussen de verschillende bitpatronen, wat kan bepaald worden via de Hamming afstand. De kans dat een bitpatroon A wordt gezien als een bitpatroon B (6= A) is gelijk aan pa1 (1 − p)36−a1 + pa2 (1 − p)36−a2 + pa3 (1 − p)36−a3 + pa4 (1 − p)36−a4 met a1, a2, a3 en a4 de Hamming afstand tussen A en B bij de verschillende rotaties en p de kans dat een bit verkeerd wordt gedetecteerd. De kans berekenen dat A wordt verward met een willekeurige merkteken, kan door deze berekening voor elk ander merkteken te maken en de resultaten op te tellen. Stel dat men voor elke rotatie van elk merkteken uit een bepaalde set de Hamming afstand bepaalt met elk ander bitpatroon uit die set, dan is P n (36−n) de kans dat een willekeurig merkteken wordt verward P = 36 n=1 HA(n) p (1 − p) met een ander. Hierbij is HA(n) het aantal gevallen met Hamming afstand n. Op deze manier werd ook de prioriteitslijst opgesteld die werd vermeld in sectie 1.2. Minimum grootte gedetecteerd merkteken: Bij ARTag bestaan de merktekens uit 10x10 eenheden, voor de randdetectie van een merkteken is echter een minimum breedte van 13 pixels nodig. Na een experiment met 6 camera’s bleken effectief ongeveer 13 pixels (full resolution mode) en 26 pixels (half resolution mode) nodig te zijn bij een zeer goede
24
Hoofdstuk 1. Bestaande systemen kwaliteit. Bij minder goede omstandigheden werd dit respectievelijk 20 en 35 pixels. Het gedrag van ARTag is vrij voorspelbaar in tegenstelling tot dat van ARToolkit. Het inwendige patroon kan hier in principe bemonsterd worden met een resolutie van 16x16 en bij eenvoudige patronen kan een kleinere waarde soms volstaan. De herkenningsgraad (het aantal herkende / het aantal aangebrachte merktekens) stijgt hier echter slechts geleidelijk naarmate de grootte stijgt, bij ARTag is dit eerder asymptotisch, en blijkt zeer afhankelijk van de cf-waarde. Voor een zelfde herkenningsgraad bij een cf-waarde van 0.8 is vaak een dubbele grootte nodig in vergelijk met een cf-waarde van 0.4. Bovendien blijken zelf-gedefinieerde merktekens beter te scoren dan de standaardset. Deze zijn immers aangepast aan de belichting en camera. ARTag blijkt dus iets robuuster te zijn en minder afhankelijk van de omstandigheden. Uitvoeringstijd: De detectie van de vierhoeken vraagt minder tijd bij ARToolkit dan bij ARTag. Er is immers slechts ´e´en bewerking nodig per pixel bij thresholding. Bij de randdetectie worden maskers gebruikt, waarbij een nieuwe pixelwaarde wordt bekomen door voor elke pixel de oude waarde te vermenigvuldigen worden met elk van de co¨effici¨enten uit het masker en deze waarden op te tellen. Het onderzoek van het inwendige patroon is dan weer sneller bij ARTag. Bij ARTag worden immers slechts 6x6 punten bemonsterd en de bijkomende logica om het ID uit het bitpatroon te filteren vraagt slechts een beperkt aantal bewerkingen. Bij ARToolkit echter wordt een correlatie uitgevoerd van minimum 16x16 punten met 12 patronen per geladen merkteken (zie figuur 1.2). Hieruit volgt dat de uitvoeringstijd bij ARTag enkel afhankelijk is van het aantal gedetecteerde vierhoeken, bij ARToolkit is dit ook afhankelijk van het aantal gebruikte merktekens. Dit alles maakt ARToolkit sneller wanneer er slechts een beperkt aantal merktekens worden gebruikt, zoniet is ARTag sneller en effici¨enter.
1.4
Andere
Naast ARToolkit en ARTag zijn er nog een aantal marker-gebaseerde systemen, zoals ook beschreven in (Fiala, 2004). Vaak zijn deze systemen eveneens bedoeld voor Augmented Reality-toepassingen, maar ook andere toepassingen zijn mogelijk, zoals opslag van informatie. Hierbij komen verschillende varianten van merktekens voor. Naast de vierkante merktekens zijn er ook cirkelvormige, 3D-vormen . . . met daarop concentrische cirkels, barcodes of andere markeringen. Vaak komt een vierkante vorm wel terug aangezien de vier hoekpunten hierbij in principe voldoende zijn om de positie van de camera te achterhalen. Ook kunnen er speciale technieken of instrumenten gebruikt worden, zoals in het systeem PTrack (Santos et al., 2006). Hierbij worden labels opgespoord d.m.v. de cirkelvormige, 25
Hoofdstuk 1. Bestaande systemen
Figuur 1.9: Camera en label gebruikt bij PTrack. De retro-reflectieve markeringen aangebracht op het label kunnen opgespoord worden dankzij de IR LED’s aan de camera.
retro-reflectieve markeringen m.b.v. de infrarode LED’s aangebracht rond de lens van de camera (zie figuur 1.9). Vier markeringen zijn aangebracht op de hoeken van een label. E´en markering is aangebracht op de bovenste rand zodat deze wordt opgesplitst in 1/3 en 2/3 van de lengte, om zo de correcte rotatie van het label terug te vinden. Tenslotte wordt ´e´en markering gebruikt ter identificatie. Deze kan de posities innemen bepaald door een rooster, op deze manier zijn verschillende labels mogelijk. Bij ons systeem echter werken we echter met een eenvoudige USB-camera, zodat hoekpunten of andere feature” points m.b.v. gewone beeldverwerkingstechnieken moeten opgespoord ” worden.
Figuur 1.10: Detectie van merktekens bij ARStudio. Links: search mode, unwarping van het merkteken en zoeken van het best passende gekende merkteken. Rechts: tracking mode, hoekdetectie.
Een interessant concept wordt toegepast bij ARStudio (Gerhard, 2002). Dit is een systeem dat eveneens gebruikt wordt voor Augmented Reality-toepassingen. Hierbij wordt namelijk een onderscheid gemaakt tussen een search mode en een tracking mode. Bij de search mode worden eerst alle aanwezige merktekens in het beeld gezocht. Bij de tracking mode kunnen diezelfde merktekens in een volgend frame gezocht worden in de buurt van hun positie in het vorige frame. De merktekens zijn hier eveneens vierkant met een zwarte rand en binnenin witte 26
Hoofdstuk 1. Bestaande systemen veelhoeken. De hoeken van deze witte veelhoeken worden bewaard in een configuratiebestand en worden zo gekozen dat de gebruikte merktekens uniek ge¨ıdentificeerd kunnen worden, ook bij verschillende rotaties. De search mode bestaat achtereenvolgens uit: Thresholding van het frame naar een binair beeld. Zoeken van gebieden met aaneengesloten zwarte pixels. Enkel deze gebieden waarvan de bounding box” aan de criteria voldoen worden verder behandeld. ” Zoeken van de vier duidelijkste hoeken van het aaneengesloten gebied in wijzerszin. Bepaling van een homografie 3.1.2 tussen de hoekpunten van het oorspronkelijke merkteken en de opgespoorde hoekpunten uit de vorige stap. Genereren van een figuur van het merkteken door ”unwarping” van de pixels van het merkteken van het frame (zie ook sectie 3.9. Zoeken van het best passende merkteken door de figuur uit de vorige stap te vergelijken met figuren van de originele merktekens door binair aftrekken van beide beelden (zie ook figuur 1.10).
Bij de volgende frames kan dan overgeschakeld worden naar tracking mode. Deze bestaat uit de volgende stappen: De posities van de hoeken van de witte veelhoeken op het merkteken uit het configuratiebestand kunnen omgezet worden naar posities op het beeldvlak via de homografie die werd berekend bij search mode. In een volgend frame zullen deze hoeken slechts over een beperkte afstand verplaatst zijn en worden ze dan ook gezocht in een klein zoekvenster rond de huidige posities. Zoeken van de eigenlijke hoeken binnen de zoekvensters met subpixel nauwkeurigheid. Aanpassen van de parameters van de homographie zodat deze overeenkomt met de nieuwe posities van de hoeken.
Wanneer de tracking mode faalt omdat het merkteken niet meer of onvoldoende nauwkeurig kan terug gevonden worden, wordt terug overgeschakeld naar search mode. Bij gebruik van de tracking mode is de verwerkingstijd per merkteken dan bijna 3x lager dan bij search mode. De merktekens moeten echter minstens 25% van het beeld innemen om bij search mode gedetecteerd te kunnen worden. Bij tracking mode varieert dit van 10% tot 150% afhankelijk van het aantal en de locaties van de hoeken van het merkteken.
27
Hoofdstuk 1. Bestaande systemen
1.5
Besluit
Na onderzoek van bestaande systemen bleek ARTag de beste karakteristieken te vertonen. De merktekens kunnen onafhankelijk van elkaar ge¨ıdentificeerd worden, zodat de verwerkingstijd onafhankelijk is van het aantal gebruikte exemplaren. Bovendien zorgen de technieken voor foutcorrectie -en detectie voor een meer betrouwbare identificatie. De gebruikte techniek voor extractie van de merktekens zorgt bij dit systeem ook voor invariantie t.o.v. lichtintensiteit en schaal. Er werd dan ook gekozen voor een aanpak gebaseerd op ARTag. De elementen van de werkwijze zoals beschreven in 1.2 kunnen als basis dienen voor het eigen ontwerp en eventueel aangevuld worden met andere concepten zoals de search mode en tracking mode van ARStudio zoals beschreven in 1.4. Verdere details of broncode van ARTag zijn niet beschikbaar, ARTag is enkel beschikbaar onder de vorm van een library. Rechtstreeks gebruik van ARTag lukt niet echt omdat we dit systeem moeilijk kunnen aanpassen aan ons specifieke probleem. Bovendien zou eventueel onderzoek achteraf van of verbeteringen aan het uiteindelijke systeem niet mogelijk zijn, terwijl dit ook wel deels een doel is van het systeem. We willen ook nagaan of we de prestaties van ARTag kunnen verbeteren, bijvoorbeeld de benodigde breedte van 13 pixels om een merkteken te herkennen.
28
Hoofdstuk 2
Merktekens 2.1
Criteria
Bij het ontwerp van de merktekens zijn volgende criteria belangrijk: Eenvoudige en snelle extractie mogelijk Voldoende te onderscheiden van de omgeving Unieke en snelle identificatie mogelijk Detectie van rotaties van een merkteken moeten leiden tot dezelfde identificatie en moeten teruggebracht kunnen worden naar de oorspronkelijke ori¨entatie Onterechte detectie van een merkteken beperken Het niet detecteren van een merkteken beperken Kans beperken dat merktekens verkeerd worden ge¨ıdentificeerd Minimumgrootte van een merkteken nodig voor betrouwbare detectie moet zo klein mogelijk zijn
2.2
Gekozen aanpak
Wegens de voordelen van de merktekens gebruikt bij ARTag (sectie 1.3) vormde dit het uitgangspunt voor het ontwerp. Deze merktekens voldoen vrij goed aan bovenstaande criteria. Aangezien echter de broncode van de eigenlijke generatie en extractie van de merktekens niet verkrijgbaar is, is hergebruik van code van dit systeem onmogelijk. Hergebruik van bepaalde idee¨en zoals beschreven in sectie 1.2 is wel mogelijk, maar bepaalde details over de opbouw zijn niet gekend (vb. bepaling van de bits voor het rotatieprobleem). 29
Hoofdstuk 2. Merktekens De grootte van een merkteken t.o.v. de afstand waarover het merkteken wordt herkend is bij ons specifieke probleem belangrijk. Het aantal bits per zijde van het interne bitpatroon speelt hierbij een belangrijke rol. Daarom werd gekozen om een softwaremodule uit te bouwen voor het genereren van merktekens waarbij dit aantal bits per zijde kan vari¨eren. Het is immers niet steeds nodig om 2002 merktekens ter beschikking te hebben, zoals bij ARTag het geval is. Ook kan het gebruik van een andere (of geen) fout detector en - corrector kan het aantal benodigde bits doen dalen. Bovendien kan een dergelijke softwaremodule later nog hergebruikt worden voor andere toepassingen. Denk bijvoorbeeld aan een krant waarin dergelijke merktekens worden afgebeeld bij bepaalde artikels of advertenties om bijkomende of meer recente informatie te bekomen (ETH Zurich, Department of Computer Science, 2006). Deze merktekens fungeren dan als een soort fysieke hyperlink. De hyperlink kan gevolgd worden door het merkteken te selecteren met de ingebouwde camera van een GSM. Vervolgens kan extra informatie opgehaald en weergegeven worden.
2.3
Algemene opbouw
Figuur 2.1: Een voorbeeld van een merkteken
Een merkteken heeft dus een vierkante vorm met een rand en een inwendig bitpatroon (zie figuur 2.1). De rand heeft een dikte die een veelvoud is van de dikte van een bitveldje. Het inwendig bitpatroon bestaat uit een ID waarop achtereenvolgens eventueel redundantiebits worden berekend voor foutdetectie en - correctie. Om de juiste rotatie terug te kunnen vinden kunnen eveneens extra bits worden toegevoegd. Door middel van deze bits kan het merkteken dan naar de oorspronkelijke rotatie worden getransformeerd, alvorens de foutcorrectie en - detectiebits te controleren. Dit wordt verder beschreven in sectie 2.4.2 Een groot nadeel van deze manier van werken is echter dat de foutbits niet kunnen berekend worden op de rotatiebits. Controleren van de foutbits kan immers maar eens de juiste rotatie 30
Hoofdstuk 2. Merktekens gekend is. Daarom werd ook voorzien dat ID’s en de bijhorende merktekens kunnen geweigerd worden zodanig dat de Hamming-afstand H tussen de geroteerde bitpatronen minstens gelijk is aan C ∗ 2 + 1 met C het aantal corrigeerbare bits. Deze werkwijze wordt verder beschreven in sectie 2.4.3.
2.4
Opbouw applicatie
Figuur 2.2: Structuur klassen generatie merktekens
ErrorCorrector, ErrorDetector en RotationDetector zijn abstracte klassen die redundantiebits voorzien voor foutcorrectie, foutdetectie en detectie van de correcte rotatie. De specifieke werkwijzen die hiervoor kunnen gebruikt worden, worden ge¨ıdentificeerd door een kenmerkende string. Via drie factories (ErrorCorrectorFactory, ErrorDetectorFactory en RotationDetectorFactory) kan dan een object gevraagd worden van de klasse die de gewenste methode implementeert. MarkerGenerator zorgt voor de eigenlijke generatie van de merktekens. Afbeeldingen van deze merktekens worden bewaard in de gewenste map. MarkerIdExtractor bepaalt het ID van een merkteken, gegeven een willekeurige rotatie van het interne bitpatroon van dit merkteken.
31
Hoofdstuk 2. Merktekens De klasse MarkerConfig bevat de parameters die de merktekens beschrijven. Deze kunnen opgehaald worden uit en weggeschreven worden naar een configuratiebestand. MarkerGenerator en MarkerIdExtractor hebben deze parameters nodig. Tijdens de generatie worden nog extra parameters toegevoegd om generatie van dezelfde merktekens later sneller te laten verlopen. ImageCreator zorgt voor de eigenlijke generatie van de afbeelding van een merkteken. Hiertoe wordt gebruik gemaakt van OpenCV-functies.
2.4.1
Configuratie
Het configuratiebestand is als volgt gestructureerd: [ Foutdetector ] [ Foutcorrector ] [ Rotatiedetector ] [ D ikt e rand ] [ Aantal g e w e n s t e merktekens ] [ Aantal b i t s ID ] [ Aantal b i t s f o u t d e t e c t i e ] [ Aantal b i t s f o u t c o r r e c t i e ] [ Aantal b i t s r o t a t i e d e t e c t i e ] [ Aantal e x t r a b i t s p e r z i j d e ] [ Maximum ID o n d e r z o c h t ] [ Geweigerde ID ’ s ]
Initieel moeten de eerste 5 parameters beschikbaar zijn in het configuratiebestand. Tijdens de eigenlijke generatie worden de overige parameters bepaald. De laatste 3 parameters worden enkel gebruikt wanneer er geen extra bits worden toegevoegd voor rotatiedetectie, maar er ID’s worden geweigerd. Dit wordt verder beschreven in sectie 2.4.3. Alle parameters moeten beschikbaar zijn voor de extractie van het ID vanuit het inwendig bitpatroon. Aangezien de configuratie bij de volgende modules later m.b.v. XML werd uitgewerkt, werd dit voor de uniformiteit ook hier gedaan. Her parsen van XML gebeurt via (The Apache Software Foundation, 2005). Configuratie via een txt-bestand blijft hier wel nog mogelijk. Het XML-bestand heeft nu de volgende structuur: <MarkerTracking x m l n s : x s i=” h t t p : //www. w3 . o r g /2001/XMLSchema−i n s t a n c e ” xsi:noNamespaceSchemaLocation=” c o n f i g u r a t i o n S c h e m a . xsd ”> <MarkerConfig> <e r r o r D e t e c t o r>Empty
32
Hoofdstuk 2. Merktekens <e r r o r C o r r e c t o r>ExtendedHamming
A l t e r n a t i v e M e t h o d 1 13 11 0 5 0 1 <maxIDExamined>24 0 1 2 3 4 5 6 7 8 10 12
Het bijhorende XML schema moet wel telkens beschikbaar zijn (in dezelfde map), anders kan er niet gevalideerd worden bij het parsen en wordt er een exceptie opgeworpen.
2.4.2
Pariteitsbits
Hieronder wordt een kort overzicht gegeven van de klassen die instaan voor de berekening van de pariteitsbits voor foutcorrectie en - detectie en rotatiedetectie. Telkens werd ook een soort dummy-klasse voorzien (EmptyErrorDetector, EmptyErrorCorrector en EmptyRotationDetector), deze wordt gebruikt wanneer geen pariteitsbits gewenst zijn voor een bepaalde functie. Op deze manier kan de generatie van merktekens of extractie van het ID steeds zoveel mogelijk op dezelfde manier gebeuren. Foutdetectie Voor foutdetectie is CRC-codering (CrcErrorDetector), ´e´en pariteitsbit (SimpleParity) of Golay-code (Golay) voorzien. Golay (Wallace, 2003) is een [23,12] - code (23 bits in totaal,
33
Hoofdstuk 2. Merktekens
Figuur 2.3: Klassen foutdetectie
12 databits) en kan per 12 databits 6 bitfouten detecteren. Wanneer echter nog een extra pariteitsbit wordt toegevoegd, berekend op het volledige codewoord ([24,12]-code), is detectie van een oneven aantal bitfouten eveneens mogelijk (ExtendedGolay). Foutcorrectie
Figuur 2.4: Klassen foutcorrectie
Naast gewone Hamming-code (HammingErrorCorrector) is hier eveneens uitgebreide Hammingcode voorzien (ExtendedHamming). Bij deze code wordt nog een extra pariteitsbit toegevoegd aan het codewoord waardoor tegelijk correctie van 1 bitfout en detectie van 2 bitfouten mogelijk is (Ext, 2005). Golay komt ook hier voor. Wanneer deze code als foutcorrector gebruikt wordt, is de correctie van 3 bitfouten mogelijk. ExtendedGolay kan als foutcorrector tegelijk 3 bitfouten corrigeren en 4 bitfouten detecteren. Tenslotte werd ook de mogelijkheid voorzien om een pariteitsbit op elke rij en op elke kolom toe te voegen(ExtendedParity). Dit laat correctie van 1 bitfout toe of detectie van de meeste bitfouten. Enkel wanneer bijvoorbeeld 2 rijen op dezelfde plaatsen een bitfout bevatten, zal dit niet gedetecteerd worden. 34
Hoofdstuk 2. Merktekens Rotatiedetectie
Figuur 2.5: Klassen rotatiedetectie
Wanneer men bits wil toevoegen om de juiste ori¨entatie terug te vinden, kan men CornerRotationDetector gebruiken. Deze voegt de bits (1,0,0) toe op respectievelijk de rechterbovenhoek, de linkerbenedenhoek en de rechterbenedenhoek. Deze bits bepalen de oorspronkelijke ori¨entatie uniek.
Figuur 2.6: Werking CornerRotationDetector
Dit wordt ge¨ıllustreerd in figuur 2.6. Bij de oorspronkelijke ori¨entatie (links) worden de rotatiebits toegevoegd. Deze ori¨entatie kan dan later via deze bits teruggevonden worden aangezien bij de andere ori¨entaties op dezelfde plaatsen steeds andere bits zullen voorkomen.
2.4.3
Generatie
c l a s s MarkerGenerator { public : MarkerGenerator ( const MarkerConfig &
markerConfig ) ;
void g e n e r a t e M a r k e r s ( s t r i n g pathMarkers ) ; void g e n e r a t e S i n g l e M a r k e r ( s t r i n g pathMarker , int ID ) ; ... };
35
Hoofdstuk 2. Merktekens De functie generateMarkers zorgt voor de eigenlijke generatie van de merktekens. Afhankelijk van het feit of EmptyRotationDetector gebruikt wordt (al dan niet rotatiedetectie via extra bits), zijn er 2 mogelijkheden: EmptyRotationDetector wordt niet gebruikt: Voor het aantal gewenste merktekens wordt een uniek ID voorzien, dit wordt omgezet naar een bitpatroon. Nu worden achtereenvolgens extra bits toegevoegd voor foutdetectie, foutcorrectie en rotatiedetectie, telkens berekend op het codewoord uit een vorige stap. Parameters 6 tot 9 uit 2.4.1 zijn nu bekend en worden aan MarkerConfig doorgegeven. EmptyRotationDetector wordt wel gebruikt: Zoals reeds aangehaald in 2.3 is het nadeel van de eerste methode dat er geen foutcorrectie -en detectiebits kunnen berekend worden op de rotatiebits. Eerst moet immers de juiste ori¨entatie teruggevonden worden via de rotatiebits vooraleer de foutdetectieen correctiebits kunnen gecontroleerd worden. Daarom hebben we een tweede manier voorzien die er voor zorgt dat de bitpatronen van de verschillende ori¨entaties van alle merktekens voldoende ver uit elkaar liggen (namelijk minstens 2 ∗ E + 1 met E het aantal corrigeerbare bits).
Figuur 2.7: Merktekengeneratie: bitpatronen merktekens voldoende verschillend
Dit wordt getoond in figuur 2.7. Veronderstel dat er 1 bit corrigeerbaar (E) is, dan moet de Hamming afstand minstens 3 zijn tussen 2 bitpatronen. Op het voorbeeld links staat er een merkteken afgebeeld samen met de 4 ori¨entaties van een ander merkteken. Het bitpatroon van het 1e merkteken wordt nu gelezen als 000011101. Bij het 2e merkteken zijn er 2 van de 4 ori¨entaties die slechts in 2 bits verschillen met het 1e bitpatroon. Beschouwen we vb. de eerste ori¨entatie, momenteel wordt het bitpatroon hiervan gelezen als 000011110. Veronderstel dat tijdens identificatie van het merkteken 1 bit verkeerd wordt gezien, vb. het laatste bit, dan wordt het bitpatroon herkend als 000011111. Aangezien er 1 bit kan gecorrigeerd worden, kan het algoritme voor foutcorrectie dit 36
Hoofdstuk 2. Merktekens zien als een patroon met een fout bij het voorlaatste bit. Dan wordt het bitpatroon gewijzigd naar 000011101 en dit was precies het bitpatroon van het 1e merkteken. Bij het voorbeeldje rechts echter is de Hamming afstand tussen de bitpatronen steeds groot genoeg. Hoe precies te werk wordt gegaan om de juiste merktekens effectief te genereren wordt nu uitgelegd. Het inwendige bitpatroon van een merkteken bestaat uit een rooster van X op X bits, met X zo klein mogelijk. Het aantal mogelijke merktekens wordt afgerond naar een aantal Y zodat T = I + D + C zo dicht mogelijk bij X ∗ X ligt. Hierbij is T het totale aantal bits, I het aantal ID-bits, D het aantal bits voor foutdetectie en C het aantal bits voor foutcorrectie. Het volledige bitpatroon wordt gegenereerd voor de ID’s 0 tot 2I −1. Voor elk bitpatroon wordt nu de Hamming afstand H tussen de 4 rotaties van dit bitpatroon en alle volgende bitpatronen in de reeks berekend. Wanneer H op een bepaald moment kleiner is dan E ∗ 2 + 1 met E het aantal corrigeerbare bits, dan zou het merkteken kunnen ge¨ıdentificeerd worden als een ander merkteken en wordt het bijgevolg geweigerd. Dit gaat door tot het aantal geldige merktekens gelijk is aan het aantal gewenste merktekens. Wanneer echter na doorlopen van de volledige reeks het aantal geldige merktekens nog steeds kleiner is dan het gewenste aantal, wordt X met ´e´en verhoogd en wordt de voorgaande procedure herhaald. In de eigenlijke implementatie worden enkel de eerste Yvolgend = min(2 ∗ Yvorig , 2Ivorig ) merktekens getest bij een volgende poging, X wordt dan enkel verhoogd indien nodig. Y is hier nu het aantal merktekens dat wordt getest. Ybegin is gelijk aan het aantal gewenste merktekens. Op deze manier wordt het aantal te testen bitpatronen sterk beperkt. Een voorbeeldje om dit even te verduidelijken. Veronderstel dat men 60 merktekens wil genereren en enkel extra bits voor foutdetectie worden toegevoegd. Ybegin is dan gelijk aan 60, er zijn dan minstens 6 ID-bits nodig en stel dat er hiervoor 2 bits nodig zijn voor foutdetectie. X moet dan gelijk zijn aan 3. Stel dat bij gebruik van de huidige configuratie en bij volledig gebruik van de X ∗ X (= 9) bits er I = 7 bits mogelijk zijn en er dan D = 2 bits nodig zijn. Wanneer er bij generatie nu minstens 1 merkteken werd geweigerd, dan moet opnieuw begonnen worden want het aantal geldige merktekens was kleiner dan het aantal gewenste. Yvolgend wordt dan min(2 ∗ 60, 27 ) = 120 te testen merktekens. X kan nog steeds gelijk blijven aan 3 aangezien de I = 7 bits voldoende zijn voor 120 merktekens. Stel nu dat er weer teveel merktekens werden geweigerd om aan de vraag te voldoen, dan worden er nu min(2 ∗ 120, 27 ) = 128 merktekens getest. Nu worden dus alle merktekens getest die mogelijk zijn met X gelijk aan 3. Wanneer we echter 2 ∗ 120 merktekens zou37
Hoofdstuk 2. Merktekens den testen, zou X gelijk moeten worden aan 4, terwijl X = 3 eventueel wel voldoende was geweest. Stel dat echter opnieuw niet aan de vraag werd voldaan, worden nu 2 ∗ 128 merktekens getest en moet X toch gelijk worden aan 4. Wanneer we echter deze optimalisatie niet zouden doorgevoerd hebben, dan zou de eerste keer 27 = 128 merktekens getest worden (maximaal aantal mogelijke merktekens bij X gelijk aan 3). Aangezien dit niet voldoende was, zou daarna het maximaal aantal mogelijke merktekens getest worden voor X gelijk aan 4. Stel dat bij X gelijk aan 4, I gelijk is aan 13 en D gelijk is aan 3, dan zou dit betekenen dat er 213 = 8192 merktekens zouden moeten getest worden. De laatste 7 parameters uit 2.4.1 zijn nu ook bekend en worden aan MarkerConfig doorgegeven. De 3 laatste parameters zijn respectievelijk het aantal bits waarmee X werd verhoogd, het grootste ID dat werd getest en de ID’s van de merktekens die werden geweigerd.
Na de generatie worden de parameters door MarkerConfig naar een configuratiebestand weggeschreven. Wanneer men de merktekens later nog eens wil genereren kan de voorgaande procedure dankzij kennis van deze parameters nu sneller verlopen. Genereren en wegschrijven van 2000 merktekens met CRC-16 foutdetectie en Hamming foutcorrectie geeft bijvoorbeeld merktekens met een bitpatroon van 6 x 6 bits en duurde oorspronkelijk bijna 90s. Achteraf duurde dit slechts 4s meer. Bovendien kan nu ook een enkel merkteken gegenereerd worden (procedure generateSingleMarker ).
2.4.4
Extractie ID
class MarkerIdExtractor { public : M a r k e r I d E x t r a c t o r ( const MarkerConfig&
markerConfig ) ;
int decodeCodeword ( b v e c t o r& codeWord ) ; ... };
Om uit het inwendig bitpatroon het ID te kunnen extraheren, zijn alle parameters nodig uit 2.4.1 (De laatste 3 parameters enkel bij gebruik van EmptyRotationDetector).
38
Hoofdstuk 2. Merktekens De functie decodeCodeword zorgt voor de eigenlijke extractie van het ID. Opnieuw zijn er 2 mogelijkheden, afhankelijk van het gebruik van EmptyRotationDetector. EmptyRotationDetector wordt gebruikt: Voor de 4 rotaties wordt getracht de pariteitsbits te controleren voor foutcorrectie en foutdetectie en eventuele fouten te corrigeren. Bij slechts ´e´en van de vier rotaties van een geldig merkteken leidt dit tot een geldig ID dat niet geweigerd werd bij de generatie, tenzij er teveel bitfouten waren. EmptyRotationDetector wordt niet gebruikt: De RotationDetector geeft de correcte rotatie terug. Vervolgens corrigeert ErrorCorrector eventuele bitfouten en detecteert ErrorDetector of er nog bitfouten zijn.
Wanneer er geen geldig ID kon gevonden worden of er een fout is opgetreden, wordt -1 teruggegeven. Dit kan gebeuren wanneer het bitpatroon niet afkomstig was van een geldig merkteken of omdat er teveel bitfouten waren die wel konden gedetecteerd worden, maar niet gecorrigeerd.
2.4.5
Interface met andere modules
Er is enkel interactie met de module voor merktekendetectie. Nadat een merkteken in een frame werd gedetecteerd en het interne bitpatroon werd bepaald, wordt de functie decodeCodeword van de klasse MarkerIdExtractor aangeroepen (zie 2.4.4).
2.5
Specifieke aanpassingen
Voor onze specifieke toepassing zijn er een aantal beperkingen mogelijk/nodig: Controle van de pariteitsbits voor Golay en ExtendedGolay bij foutcorrectie vraagt vrij veel bewerkingen en kan hier beter niet toegepast worden. Deze methode kan uiteraard later wel gebruikt worden voor eventuele andere toepassingen met minder strenge snelheidseisen. Merktekens met een volledig wit of zwart intern patroon worden best geweigerd, dergelijke patronen komen immers meer voor in een natuurlijke omgeving. Merktekens weigeren waarbij 2 ori¨entaties leiden tot hetzelfde ID. In dit geval kan de gedetecteerde ori¨entatie immers niet teruggebracht worden naar de oorspronkelijke ori¨entatie (wat wel nodig is voor de positiebepaling).
39
Hoofdstuk 2. Merktekens
Figuur 2.8: Verschillende ori¨entaties leveren hetzelfde ID
Dit wordt getoond in figuur 2.8. Bij het eerste merkteken (links) leiden de 4 ori¨entaties allemaal tot hetzelfde ID, bij het tweede merkteken (rechts) zijn er 2 dergelijke ori¨entaties.
2.6
GUI
Figuur 2.9: Overzichtsmenu
Ter ondersteuning werd in Matlab een GUI gemaakt. Op deze manier wordt de functionaliteit van alle fasen samengebracht en kan alles gebruiksvriendelijk worden getest. Telkens werden er ook EXE-bestanden gemaakt die minstens evenveel mogelijkheden bieden als de overeenkomstige GUI, zodat men niet verplicht is om Matlab te gebruiken. Bij deze uitvoerbare bestanden zijn er soms nog extra mogelijkheden, vb. weergeven van de uitvoeringstijd per frame en dergelijke. De mogelijkheden voor GUI’s in Matlab zijn niet zo uitgebreid. Aangezien er vb. niet kan gewerkt worden met tabbladen, werd dit hier opgelost via een overzichtsmenu (figuur 2.9). Het eerste item in dit overzichtsmenu laat merktekengeneratie toe, bij een klik op de knop verschijnt het venster uit figuur 2.10. Via dit venster kunnen de parameters die de merktekens beschrijven op een gebruiksvriendelijke manier worden gespecifieerd. De C++-code voor de 40
Hoofdstuk 2. Merktekens
Figuur 2.10: GUI merktekengeneratie
merktekengeneratie en generatie van een bijhorend configuratiebestand wordt opgeroepen via een zogenaamd MEX-script. De map waar de merktekens in moeten terecht komen moet ingegeven worden. Vervolgens kan het aantal gewenste merktekens en de methodes voor foutdetectie, foutcorrectie en rotatiedetectie aangevuld worden. De namen van de verschillende methodes worden opgehaald uit de C++-module, eveneens via een MEX-script. Bij een klik op de knop met opschrift Generate Markers” worden nu de merktekens ge” genereerd. Wanneer echter geen pad voor de merktekens werd gespecifieerd, verschijnt een foutmelding. Een configuratiebestand wordt eveneens gegenereerd en in dezelfde map als de merktekens geplaatst. Eventuele foutmeldingen of extra informatie over de merktekengeneratie verschijnen in de onderste textbox. 41
Hoofdstuk 2. Merktekens Wanneer men later dezelfde merktekens wil genereren kan het pad van het configuratiebestand worden ingegeven. Dit configuratiebestand kan zowel een xml-bestand als een txt-bestand zijn met de structuur die wordt beschreven in 2.4.1. De parameters in het paneel Marker ” setup” worden automatisch gewijzigd naar de parameters die in het configuratiebestand staan. Wanneer nu op de knop wordt geklikt, worden de merktekens sneller gegenereerd dankzij de gekende parameters, zie ook sectie 2.4.3. Als echter een van de parameters werd gewijzigd vooraleer op de knop te klikken, worden de gewijzigde parameters naar het bestand geschreven en moet de generatie opnieuw vanaf nul beginnen.
Figuur 2.11: GUI merktekengeneratie, genereren van een enkel merkteken
Wanneer het pad van een configuratiebestand wordt opgegeven dat alle parameters bevat, kan via de dropdownlist in het paneel General” ook gekozen worden om een enkel merkteken ” te genereren, zie ook figuur 2.11.
42
Hoofdstuk 3
Extractie en identificatie merktekens 3.1
Basisbegrippen
Hier worden kort enkele basisbegrippen verklaard die later zullen gebruikt worden.
3.1.1
Convolutie
Figuur 3.1: 2-dimensionale convolutie
43
Hoofdstuk 3. Extractie en identificatie merktekens Het begrip convolutie kent zijn oorsprong in de signaal- en systeemtheorie als (f ∗ g)(t) = R f (τ )g(t − τ )dτ en kan gezien worden als een soort gewogen gemiddelde. Binnen beeldverwerking wordt dit gebruikt voor filter-operaties die bijvoorbeeld worden toegepast op de pixels van een beeld. Het komt erop neer dat elk element uit een bepaalde omgeving” rond ” een punt wordt vermenigvuldigd met welbepaalde co¨effici¨enten uit een masker, ook wel filter of kernel genoemd. De som van deze vermenigvuldigingen vormt het resultaat voor dat punt. Bij convolutie wordt het masker eerst geroteerd over 180°. In wat volgt wordt een onderscheid gemaakt tussen 1D- en 2D - convolutie. Bij 2-dimensionale convolutie (figuur 3.1) van een beeld wordt een masker van m x n elementen gebruikt. m en n zullen steeds oneven gemaakt worden. Het centrum van het masker wordt verschoven van pixel naar pixel over het beeld. Het resultaat voor een pixel is dan de som van de producten van de waarden van de pixels die onder het masker liggen met de overeenkomstige co¨effici¨ent die er net boven ligt. Aan de randen van het beeld zullen bepaalde co¨effici¨enten van het masker niet overlappen met het beeld. Dit kan vb. opgelost worden door nullen toe te voegen.
Figuur 3.2: 1-dimensionale convolutie
Bij 1-dimensionale convolutie wordt hetzelfde principe toegepast, maar nu slechts in 1 richting 44
Hoofdstuk 3. Extractie en identificatie merktekens (figuur 3.2). Er zal voor gezorgd worden dat het resultaat na convolutie dezelfde grootte heeft als de invoer. De eerste waarde wordt dan ook gevonden door het centrum van het masker te laten samenvallen met het eerste element van de invoer (stap a). Links worden er weer (n − 1)/2 elementen toegevoegd (vb. nullen), met n het aantal elementen in het masker. De volgende waarden worden bekomen door het masker steeds 1 positie naar rechts te verschuiven. Bij de berekening van de laatste waarde (stap f ) valt het centrum van het masker samen met het laatste element van de invoer, weer werden er (n − 1)/2 extra elementen toegevoegd.
3.1.2
Homografie
Dit begrip al reeds gebruikt in 1.4 en zal ook in dit hoofdstuk terugkomen. In deze context wordt het gebruikt om een relatie te vinden tussen de hoekpunten van het oorspronkelijke vierkante merkteken en het gedetecteerde merkteken. Dit kan gebeuren met een perspectieve transformatie van 2D naar 2D.
Figuur 3.3: Links: oorspronkelijk merkteken, rechts: gedetecteerd merkteken. Relatie tussen beide via perspectieve transformatie.
Veronderstel dat (x, y) de coordinaten zijn geassocieerd met het oorspronkelijke merkteken en (x0 , y 0 ) deze van het gedetecteerde merkteken (figuur 3.3). Dan kan de relatie tussen beide uitgedrukt worden als: x0 x 0 y = H y 1 1
(3.1)
Hierbij is de 3x3-matrix H de homografie. Dit levert de vergelijkingen:
x0 (h31 x + h32 y + h33 ) = h11 x + h12 y + h13
(3.2)
y 0 (h31 x + h32 y + h33 ) = h21 x + h22 y + h23
(3.3)
met hij het (i, j)e element van H. Er zijn 4 overeenkomsten nodig om de homografie te kunnen bepalen, de hoeken van de merktekens zijn dus voldoende. Er wordt dan een stelsel van 8 vergelijkingen bekomen waarmee de elementen van h kunnen bepaald worden:
45
Hoofdstuk 3. Extractie en identificatie merktekens
x1 0 x 2 0 x 3 0 x 4 0
3.1.3
y1 0 y2 0 y3 0 y4 0
1 0 1 0 1 0 1 0
0 x1 0 x2 0 x3 0 x4
0 y1 0 y2 0 y3 0 y4
0 1 0 1 0 1 0 1
−x01 x1 −y10 x1 −x02 x2 −y20 x2 −x03 x3 −y30 x3 −x04 x4 −y40 x4
−x01 y1 −y10 y1 −x02 y2 −y20 y2 −x03 y3 −y30 y3 −x04 y4 −y40 y4
h11 −x01 h12 0 −y1 h13 −x02 h21 0 −y2 h = 0 met h = h22 −x03 h23 0 −y3 h31 0 −x4 h32 −y40 h33
(3.4)
Ruis
Bij het vastleggen van beelden (vb. met een camera) kunnen er afwijkingen ontstaan t.o.v. het ideale, dit wordt ruis genoemd. Dit als gevolg van allerlei imperfecties die al dan niet kunnen gemodelleerd worden. De eigenschappen van de optredende ruis hangen af van de oorzaak. Ruis kan onderverdeeld worden in 2 categorie¨en: ruis afhankelijk van het beeld en onafhankelijke ruis. Ruis afhankelijk van het beeld kan vaak beschreven worden via een model van de vorm f (i, j) = s(i, j) + n(i, j) met f (i, j) het bekomen beeld, s(i, j) het werkelijke beeld en n(i, j) de ruis (additieve ruis). n(i, j) heeft vaak een gemiddelde waarde gelijk aan nul en kan beschreven worden door zijn variantie σn 2 . De impact van ruis op een beeld kan vaak worden beschreven via de signaal-ruisverhouding (signal to noise ratio, SNR). Vaak is additieve ruis evenredig verdeeld over het frequentiedomein van een beeld (witte ruis). Aangezien een beeld echter vooral bestaat uit informatie op een lage frequentie, zal ruis relatief gezien vooral op de hoge frequenties voorkomen. Vaak kan dergelijke ruis dan ook verminderd worden via een laagdoorlaatfilter, een voorbeeld hiervan wordt in 3.1.4 besproken.
Figuur 3.4: Voorbeeld kunstmatig toevoegen ruis. Links: origineel, midden: Gaussiaanse ruis met variantie 0.02 en gemiddelde waarde 0, rechts: 10% salt & pepper ruis
46
Hoofdstuk 3. Extractie en identificatie merktekens Ruis kan ook kunstmatig worden toegevoegd aan een beeld. Op deze manier kan getest worden in welke mate beeldverwerkingsalgoritmen bestand zijn tegen ruis. Een voorbeeld van ruis afhankelijk van het beeld is Gaussiaanse ruis. Dit kan bijvoorbeeld gemodelleerd worden door een additief model, waarbij een Gaussiaanse distributie met gemiddelde waarde 0 wordt gebruikt. Elke pixel in het beeld met ruis is dan de som van de echte pixelwaarde en een random waarde, bepaald volgens een Gaussiaanse verdeling. Figuur 3.4 (midden) toont een voorbeeld van Gaussiaanse ruis. Een voorbeeld van onafhankelijke ruis is salt and pepper” ruis. Hierbij worden sommige ” pixels op de maximum -of minimumwaarde gezet of worden er bepaalde bits gewijzigd in de grijswaarde van een pixel. De andere pixels blijven ongewijzigd. Vaak wordt de ruis hier uitgedrukt als het percentage van de pixels dat werd gewijzigd. Figuur 3.4 (rechts) toont een voorbeeld van salt & pepper ruis.
3.1.4
Gaussian smoothing
Dit begrip komt in dit hoofdstuk meermaals terug en wordt daarom hier al even toegelicht. Bij Gaussian smoothing wordt een convolutie toegepast van een afbeelding met een kernel die een Gaussfunctie voorstelt. Dit heeft als effect dat de afbeelding vervaagt (blurring), waardoor ruis en detailelementen in een afbeelding worden verminderd. Als waarde voor een bepaalde pixel wordt hierbij een gewogen gemiddelde genomen van de pixels in een bepaalde omgeving, waarbij de pixels die dichter bij het centrum een groter gewicht krijgen dan pixels die verder liggen. Om een Gaussfunctie te kunnen voorstellen moeten voor de kernel gepaste discrete waarden gevonden worden. In theorie is de Gaussfunctie overal groter dan nul, maar in praktijk is deze bijna gelijk aan nul wanneer x 3σ verwijderd is van de gemiddelde x. Een Gaussfunctie in 1-D heeft de volgende vorm: G(x) = √
x2 1 e− 2σ2 2πσ
(3.5)
Bij een σ gelijk aan 1.0 kan deze worden voorgesteld door het masker in figuur 3.5 (rechts).
47
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.5: 1-D Gaussfunctie (gemiddelde 0, σ 1.0) (links) en voorstelling m.b.v. een kernel (rechts) (R. Fisher & Wolfart., 2003).
Voor convolutie van een beeld is echter een 2D-Gaussfunctie nodig, deze heeft de vorm: G(x, y) = √
x2 +y 2 1 e− 2σ2 2πσ 2
(3.6)
en kan bijvoorbeeld voorgesteld worden door het masker in figuur 3.6 (rechts).
Figuur 3.6: 2D-Gaussfunctie (gemiddelde 0, σ 1.0) (links) en voorstelling m.b.v. een kernel (rechts) (R. Fisher & Wolfart., 2003).
Door de symmetrie van de Gaussfunctie kan deze worden opgesplitst in een x- en een ycomponent. De 2D-convolutie kan dan ook worden uitgevoerd via een 1D-convolutie in de x-richting gevolgd door een 1D-convolutie in de y-richting, wat veel performanter is. Als we de Gauss-kernel uit figuur 3.6 toepassen op de afbeeldingen met ruis (figuur 3.4), 48
Hoofdstuk 3. Extractie en identificatie merktekens dan bekomen we als resultaat figuur 3.7. De afbeelding moet hiertoe eerst naar grijswaarden omgezet worden.
Figuur 3.7: Resultaat na convolutie met Gauss-kernel op afbeeldingen met ruis. Links: Gaussiaanse ruis, rechts: Salt & pepper ruis
Het resultaat is vrij goed voor de afbeelding waaraan Gaussiaanse ruis werd toegevoegd. Het resultaat is minder goed voor de afbeelding met salt & pepper” ruis. Dit komt doordat ” de waarde van een pixel met ruis hierbij vrij sterk afwijkt van zijn oorspronkelijke waarde. Doordat deze pixel het meeste gewicht krijgt, zal het eindresultaat na Gaussian smoothing nog steeds sterk afwijken van het origineel. Een oplossing zou het gebruik van een mediaan filter kunnen zijn (R. Fisher & Wolfart., 2003).
3.2
Uitvoering onderzoek
Voor dit onderdeel van het project werd eerst in Matlab (The MathWorks, 2007) en de Image Processing Toolbox gewerkt. Deze omgeving biedt immers de mogelijkheid om eenvoudig beelden te manipuleren en standaardalgoritmen voor beeldverwerking uit te proberen. Bovendien kunnen testresultaten hier mooi weergegeven worden. Uiteindelijk werd alles omgezet naar C++ om zo een performant systeem te verkrijgen. Documentatie werd hierbij gegenereerd via doxygen (van Heesch, 2007). Hier kon gebruik gemaakt worden van OpenCV (Intel, 2007), een open-source bibliotheek voor beeldverwerking. De vaak gebrekkige documentatie zorgde hier soms wel voor problemen. Er werd getest met 2 USB-camera’s die beide een verschillende kwaliteit van camerabeelden leveren. De eerste camera leverde vrij onscherpe beelden. De tweede camera was van het merk DigiVue en leverde wel beelden van hoge kwaliteit.
49
Hoofdstuk 3. Extractie en identificatie merktekens
3.3
Criteria
Bij extractie van de merktekens zijn volgende criteria belangrijk: Minimum - en maximumgrootte van een gedetecteerd merkteken in een frame. Dit bepaalt immers ook de afstand die mogelijk is tussen camera en merkteken, wat hier een belangrijk criterium is. Hoek tussen merkteken en camera Nauwkeurigheid van de gedetecteerde hoeken. Dit vormt ook de basis voor een nauwkeurige positiebepaling. Prestaties bij beweging van het object dat de camera draagt. Uitvoeringstijd Lichtgevoeligheid Prestaties bij mindere kwaliteit van de camerabeelden (scherpte, ruis. . . ) Occlusie van een voorwerp
3.4
Algemene werkwijze
De uiteindelijke werkwijze bestaat uit volgende stappen: Randdetectie (edge detection) Opsporen van contouren (edge tracking) Onderzoek van de kromming in de punten van de contour om zo vierhoeken te detecteren Betere lokalisatie van de hoeken Sampling van het bitpatroon en identificatie
Voor elk van deze fasen wordt nu besproken welke werkwijze we uiteindelijk hebben toegepast en hoe we ertoe zijn gekomen.
50
Hoofdstuk 3. Extractie en identificatie merktekens
3.5
Edge detection (randdetectie)
Randdetectie is een methode die op zoek gaat naar betekensvolle discontinu¨ıteiten in grijswaarden van beelden. Een kleurenbeeld (RGB-waarden) moet dan ook eerst omgezet worden naar grijswaarden, dit kan via de formule grijswaarde = 0.299∗R +0.587∗G+0.114∗B. Een rand is dan een reeks aaneengesloten pixels waarin een dergelijke discontinu¨ıteit voorkomt. Een rand ligt dan weer op zijn beurt op de grenslijn tussen 2 gebieden. Een rand is dus eerder een lokaal concept, een grens globaal. De vraag is nu hoe dergelijke overgangen in grijswaarden kunnen gemeten worden.
Figuur 3.8: Profiel van een ideale rand (links) en een re¨ele rand (rechts) (Gonzalez & Woods, 2001) .
Een ideale rand heeft een stap-profiel (figuur 3.8, links) met een verticale overgang. In praktijk echter zal door allerlei imperfecties, vb. bij vastleggen van de beelden, een rand minder scherp zijn, waardoor het profiel eerder een helling vertoont (figuur 3.8, rechts). De grootte van de richtingsco¨effici¨ent van deze helling is hierbij omgekeerd evenredig met de mate waarin de randen wazig zijn.
Figuur 3.9: Profiel, 1e en 2e afgeleide van een rand (Gonzalez & Woods, 2001) .
Figuur 3.9 toont de eerste en tweede afgeleide van het grijswaardenprofiel van een rand. De eerste afgeleide is nul voor gebieden met een constante grijswaarde, positief waar de helling begint en eindigt en is constant voor punten op de helling. De tweede afgeleide is positief aan het uiteinde van de helling dat hoort bij het donkere gebied van de rand (kleinere grijswaarde), negatief bij het lichtere gebied (grotere grijswaarde) en is gelijk aan nul voor punten op de helling en in gebieden met constante grijswaarde. 51
Hoofdstuk 3. Extractie en identificatie merktekens Hieruit blijkt dat de grootte van de eerste afgeleide kan gebruikt worden om uit te maken of een punt al dan niet op een rand ligt. Het teken van de tweede afgeleide kan dan weer gebruikt worden om te bepalen of een punt aan de donkere of lichtere kant ligt van een rand. Een tweede methode voor lokalisatie van randpunten is dan ook het zoeken van nuldoorgangen van de 2e afgeleide. De eerste afgeleide kan worden bepaald door berekening van de gradi¨ent. De gradi¨ent op positie (x, y) voor het beeld f (x, y) wordt gedefinieerd als de vector # " # ∂f Gx ∂x = ∂f ∇f = Gy ∂y "
(3.7)
Deze vector wijst in de richting waarin f het sterkst varieert bij het punt met co¨ordinaten (x, y). Een belangrijke maat bij randdetectie is de grootte van deze vector (∇f ): h i1/2 ∇f = |∇f| = G2x + G2y
(3.8)
∇f geeft de grootte van de variatie aan per eenheid afstand, in de richting van ∇f. Deze richting (α(x, y)) is ook een belangrijke maat en wordt gedefinieerd als α(x, y) = arctan(
Gx ) Gy
(3.9)
De richting van de rand in een punt (x, y) is loodrecht t.o.v. α(x, y) in dat punt. De tweede afgeleide kan worden bepaald via de Laplaciaan (∇2 f ), deze wordt gedefinieerd als ∇2 f =
3.5.1
∂2f ∂2f + ∂x2 ∂y 2
(3.10)
Gradi¨ ent gebaseerde randdetectie
Roberts, Prewitt, Sobel De gradi¨ent bepalen in elk punt van een beeld, kan door gebruik van de maskers uit figuur 3.10. De Roberts cross-gradi¨ent operatoren zijn de meest eenvoudige, maar hebben geen duidelijk centrum. De 3x3-varianten worden vaker gebruikt. Via de Prewitt operatoren bijvoorbeeld kan via het eerste masker de gradi¨ent in x-richting worden benaderd, via het tweede masker de gradi¨ent in y-richting. Een variatie hierop zijn de Sobel operatoren, die meer gewicht geven aan het centrale punt en zo enigzins ruis onderdrukken. Enkel de punten waarbij de grootte van de gradi¨ent boven een bepaalde threshold (drempelwaarde) liggen, worden als randpunten in rekening gebracht. Daarbij wordt de grootte van de gradi¨ent vaak benaderd door |G| = |Gx | + |Gy |, dit is effici¨enter dan berekening 3.8.
52
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.10: Maskers voor berekening van de gradi¨ent (Gonzalez & Woods, 2001).
Deze filters zijn echter niet invariant t.o.v. rotatie (isotroop). Wanneer enkel gebruik wordt gemaakt van de filters uit figuur 3.10, worden enkel de sterkste variaties van grijswaarden in een welbepaalde richting gevonden. De filters bij Sobel en Prewitt zouden kunnen aangepast worden zodat ze bijvoorbeeld in een diagonale richting werken, maar het probleem doet zich dan weer voor in een andere richting.
Figuur 3.11: Origineel testbeeld voor randdetectie
Dit wordt duidelijk als we deze randdetectoren uittesten op figuur 3.11. Hierbij werd zowel de filter voor de horizontale als de verticale richting eens toegepast en werden de resultaten samengevoegd tot ´e´en beeld.
53
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.12: Resultaten voor Sobel (links), Prewitt (midden) en Roberts (rechts)
Figuur 3.12 toont duidelijk de horizontale en verticale stukjes rand die worden gedetecteerd. Bovendien treden er gaatjes op in de contour, wat deze randdetectoren niet echt aantrekkelijk maakt voor verder gebruik. Bij deze test werd er wel een threshold gebruikt voor de grootte van de gradi¨ent, maar zelfs wanneer een thresholdwaarde gelijk aan 0 wordt gebruikt, blijft het probleem bestaan (figuur 3.13). Het resultaat zou misschien kunnen verbeterd worden door ook de resultaten voor de 2 diagonale richtingen toe te voegen, maar dan wordt het resultaat wel erg ruisgevoelig aangezien er geen voorzieningen zijn om ruis te verwijderen.
Figuur 3.13: Resultaten voor Sobel(links), Prewitt(midden) en Roberts (rechts) bij een thresholdwaarde gelijk aan nul
Canny randdetectie De Canny edge detector werd in 1986 ontworpen en is ´e´en van de krachtigste methodes om randen te detecteren. De doeleinden voor Canny edge detectie werden expliciet vooropgesteld: Goede detectie: zoveel mogelijk echte” randen lokaliseren en aanduiden. ” Goede lokalisatie: minimale afstand tussen de gedetecteerde rand en de werkelijke rand. Een rand mag slechts eenmaal aangeduid worden en ruis in het beeld moet zo weinig mogelijk extra randen cre¨eren.
54
Hoofdstuk 3. Extractie en identificatie merktekens Hiertoe wordt er gewerkt in verschillende fasen: Smoothing: 3.1.4)
Om ruis weg te werken wordt eerst Gaussian smoothing toegepast (zie
Zoeken gradi¨ ent: Een rand kan verschillende richtingen volgen. Daarom wordt het beeld bekomen na stap 1 afgeleid in x- en y-richting. Dit zou bijvoorbeeld kunnen gebeuren via de overeenkomstige Sobel maskers (figuur 3.10). Via de waarde van de gradi¨ent in x- en y-richting kan de richting van de rand worden bepaald en de grootte van de gradi¨ent. Non-maximum Suppression: Nu we de intensiteitsvariatie in elk punt van de afbeelding kennen, moeten randen nu geplaatst worden waar maxima voor de gradi¨ent voorkomen en niet-maxima moeten onderdrukt worden. Op deze manier bekomt men een fijne lijn voor de rand.
Figuur 3.14: Non-maximum Suppression (CVonline, 1996)
Aangezien de richting van de gradi¨ent loodrecht staat op de richting van een rand, moeten niet-maxima loodrecht t.o.v. de rand onderdrukt worden. Dit kan als volgt gebeuren: elke pixel vormt het centrum van een 9x9 - omgeving. De grootte van de gradi¨ent wordt berekend aan de rand van deze omgeving in beide richtingen loodrecht op de rand vanuit de centrale pixel. Dit kan gebeuren door interpolatie van de naburige waarden voor de gradi¨ent. In figuur 3.14 bijvoorbeeld kan dit voor het aangeduide punt gebeuren via interpolatie van de waarden voor e, g en h, nadien wordt deze berekening in de andere richting herhaald, vb. via interpolatie van a, b en d. Wanneer de centrale pixel een waarde voor de gradi¨ent heeft die niet groter is dan deze 2 waarden, dan wordt deze ge¨elimineerd. Edge Tresholding: Hiertoe wordt een hysteresis”-methode toegepast. Bij de meeste ” methodes wordt een enkele threshold gebruikt, waardoor de rand in stukken uiteenvalt (streaking) bij schommelingen rond deze threshold-waarde. Hier wordt echter een bovenen ondergrens gebruikt. Punten met een waarde boven de bovengrens worden onmiddellijk geaccepteerd als randpunt. Punten met een waarde onder de ondergrens worden
55
Hoofdstuk 3. Extractie en identificatie merktekens onmiddellijk geweigerd. Punten met een waarde tussen beide grenzen worden enkel geaccepteerd als deze aansluiten bij een punt met een waarde boven de bovengrens. De kans op streaking” wordt drastisch verminderd, aangezien dit enkel zal voorkomen ” wanneer er schommelingen optreden van boven de bovengrens tot onder de ondergrens. Bovendien zal eventuele ruis die nog aanwezig was na Gaussian smoothing nog verder ge¨elimineerd worden, aangezien de gradi¨ent hierbij eerder onder de bovengrens zal blijven.
Figuur 3.15: Test Canny edge detector.
De kracht van deze methode wordt ook duidelijk wanneer we deze toepassen op figuur 3.11, het resultaat wordt weergegeven in figuur 3.15. In eerste instantie werd dan ook besloten om de Canny edge detector te gebruiken. Deze methode werd gedurende lange tijd als eerste stap gebruikt bij het extractieproces en er werd getracht de extractie in de volgende fasen te verbeteren, maar uiteindelijk bleken er toch enkele cruciale tekortkomingen op te treden in deze fase. Bij testen van de merktekenextractie werd o.a. gebruik gemaakt van een reeks testbeelden op verschillende afstanden, vastgelegd met de tweede camera (zie 3.2). Hierbij werd gebruik gemaakt van merktekens met een intern bitpatroon van 4 x 4 bits en een randdikte van 1 eenheid (waarbij 1 eenheid de breedte van 1 bitveldje is). Op de ID-bits werd uitgebreide Hamming-code toegepast (1 bitfout corrigeerbaar, 2 bitfouten detecteerbaar). Er werden geen bits toegevoegd voor rotatiedetectie (EmptyRotationDetector, zie 2.4.3).
56
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.16: Canny bij merktekens met een breedte van 21 pixels.
Merktekens die op het beeldvlak vrij breed zijn, worden goed gevonden en de samplingpunten (3.9 worden correct gepositioneerd (figuren 3.16, 3.18 links). Alle merktekens in figuur 3.16 werden correct ge¨extraheerd en ge¨ıdentificeerd.
Figuur 3.17: Canny bij merktekens met een breedte van 12 pixels.
Wanneer de merktekens op het beeldvlak echter minder breed zijn, treden er problemen op (figuren 3.17, 3.18 rechts). De contouren worden niet goed benaderd, hoeken zijn te afgerond, verkeerde delen van contouren worden met elkaar gelinkt, gaten in de contouren. . . De gaten in de contouren zouden deels kunnen ge¨elimineerd worden door de thresholdwaarden voor Canny aan te passen, maar een goede globale thresholdwaarde zoeken voor elke situatie blijkt moeilijk. Eventueel zou deze dynamisch kunnen aangepast worden, bijvoorbeeld in functie van de afstand tot de camera, maar er spelen nog teveel andere factoren mee (kwaliteit camerabeelden, ruis. . . ) en dit brengt ook geen soelaas voor de andere problemen die optreden. Wanneer er bovendien een kandidaat-merkteken wordt gevonden, worden de samplingpunten vaak niet correct gepositioneerd. Deze worden immers relatief t.o.v. de hoeken bepaald (sectie 3.9), terwijl deze hier vaak niet goed worden benaderd. Dit zou trouwens ook de nodige problemen geven bij de positiebepaling. 57
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.18: Kandidaat-merktekens bij een breedte van 21 pixels (links) en 12 pixels (rechts).
3.5.2
Laplacian of Gaussian (LoG)
Figuur 3.19: Profiel, 1e en 2e afgeleide van een rand bij toevoegen van Gaussiaanse ruis met σ 0.1 (Gonzalez & Woods, 2001).
Deze methode is een voorbeeld van het gebruik van de tweede afgeleide voor randdetectie (sectie 3.5). De tweede afgeleide is echter vrij gevoelig voor ruis (figuur 3.19), daarom wordt het beeld eerst Gaussiaans (Gaussian) gefilterd (sectie 3.1.4) alvorens de tweede afgeleide (Laplacian) te bepalen. In plaats van het beeld eerst te filteren met een Gauss-kernel en dan met een kernel voor de Laplaciaan, wordt een samengestelde kernel gebruikt. Convolutie met een dergelijke kernel vereist minder bewerkingen. De discrete waarden voor deze kernel kunnen op voorhand worden bepaald voor een vaste σ voor de Gaussiaan, door de tweede afgeleide van de Gaussiaanse functie (sectie 3.1.4) te nemen: x2 + y 2 − x2 +y2 2 −1 1− e 2σ LoG(x, y) = πσ 4 2σ 2
(3.11)
Deze functie en de bijhorende kernel worden weergegeven in figuur 3.20 voor een σ gelijk aan 1.4. Na convolutie met deze kernel bekomt men als resultaat: Nul bij gebieden met constante grijswaarde. Positieve waarden aan de ene kant van een rand. Negatieve waarden aan de andere kant van een rand.
58
Hoofdstuk 3. Extractie en identificatie merktekens Nul bij een bepaald punt op de rand zelf.
Figuur 3.20: Functie Laplacian of Gaussian en bijhorend masker bij σ gelijk aan 1.4
Figuur 3.21 toont het resultaat na convolutie, de bekomen waarden noemen we verder de LoG-waarden”. Donker duidt op lage (evt. negatieve) waarden, lichter duidt op positieve ” waarden. De nuldoorgangen (overgang van waarden met een verschillend teken) komen steeds voor op gesloten contouren, zodat het probleem van gaten in de contouren (sectie 3.5.1) kan worden opgelost! De vraag is nu hoe we deze nuldoorgangen kunnen opsporen, er bestaat hiervoor geen standaardmethode. Hier wordt dit opgelost door de LoG-waarde van elke pixel te vergelijken met deze van de pixel er rechts naast (horizontaal, figuur 3.22). Als deze waarden een verschillend teken hebben, treedt ertussen een nuldoorgang op. Indien niet, wordt de LoG-waarde van de pixel vergeleken met deze van de pixel er net onder (verticaal). Wanneer er een tekenwissel optreedt, wordt het overeenkomstig randpunt gezocht. De positieve en negatieve LoG-waarde kan handig gebruikt worden om het randpunt met subpixelnauwkeurigheid op te sporen. De x-co¨ordinaat wordt bij een tekenwissel in horizontale richting gevonden via lineaire interpolatie: xP 1 ∗ LoGP 2 − (xP 2 ) ∗ LoGP 2 LoGP 2 − LoGP 1 De y-co¨ordinaat wordt analoog gevonden bij een tekenwissel in verticale richting.
59
(3.12)
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.22:
Figuur 3.21:
Resultaat na convolutie met LoG-kernel.
Zoeken van nuldoorgangen via lineaire interpolatie.
Figuur 3.23 toont de gevonden randpunten (groen). De randen van de merktekens worden veel beter benaderd en de randpunten vormen gesloten contouren. Rechts wordt het resultaat getoond op pixelniveau (door afronden van de co¨ordinaten van de gevonden randpunten). De subpixel-benadering is duidelijk veel precieser, dit zal ook nodig blijken bij het benaderen van de hoeken en het bepalen van de samplingpunten.
Figuur 3.23: Resultaat toepassen LoG op figuur 3.17 (links).
Een nadeel van de LoG-methode is wel dat niet enkel randen worden opgespoord. Nuldoorgangen komen steeds voor wanneer er een grotere overgang optreedt in grijswaarden. Hierdoor worden vaak talloze gesloten lusjes gevonden. Deze methode wordt dan ook eerder bestempeld als een feature” detector dan een randdetector. Dit wordt deels verholpen door een gepaste ” waarde voor σ te gebruiken voor de LoG-kernel. Hoe groter σ, hoe minder dergelijke lusjes worden gevonden en hoe groter de features” moeten zijn die wel nog worden herkend. Toch ” mag σ niet te groot worden aangezien de merktekens dan niet meer zouden herkend worden wanneer ze in het beeldvlak kleiner worden. Een waarde van 1.4 voor σ en een breedte van 9 voor de LoG-kernel blijken globaal goed te werken. 60
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.24: Toepassen van een threshold voor de LoG-methode.
Bovendien werd nog een tweede optimalisatie toegevoegd. Door een threshold-waarde te gebruiken voor het verschil tussen de LoG-waarden net voor en net na een nuldoorgang, kunnen zwakke overgangen ge¨elimineerd worden. Doordat de randen van de merktekens wel voor een grote overgang in grijswaarden zorgen, worden de randpunten op deze randen wel behouden. Een voorbeeld wordt getoond in figuur 3.24. Dit zorgt voor een snelle eliminatie van heel wat valse randen, zodat deze in de volgende fasen dan niet meer behandeld moeten worden. Dit resulteert ook in een grote performantiewinst. Om toch toe te laten dat er hier en daar een randpunt verdwijnt op de randen van de merktekens, worden in een latere fase contouren gelinkt (sectie 3.8). De threshold-waarde die best gebruikt wordt, hangt wel af van de camera. Wanneer de beelden vrij onscherp zijn, zullen de grijswaarden bij de randen van een merkteken ook slechts geleidelijk veranderen. De threshold-waarde wordt best proefondervindelijk vastgelegd. Voor randdetectie bij een beeld met resolutie a × b via de LoG-methode zijn dus a ∗ b ∗ breedte2kernel operaties nodig. Zoeken van nuldoorgangen en bijhouden van andere informatie 61
Hoofdstuk 3. Extractie en identificatie merktekens (labels, zie 3.6) is O(ab).
3.6
Edge tracking
De subpixel benadering van de randpunten is nu gekend. Deze worden opgeslaan als een lookup-table met dezelfde grootte van het oorspronkelijke beeld. Op deze manier kan in O(1) per pixel opgevraagd worden of er een randpunt voorkomt en met welke co¨ordinaten. Als volgende stap moeten deze randpunten worden gelinkt tot zinvolle randen. Algemeen kunnen we hiervoor een onderscheid maken tussen globale en lokale methodes. De Hough transform (Gonzalez & Woods, 2001) is een voorbeeld van een globale methode. Deze zoekt naar deelverzamelingen van randpunten die op rechte lijnen liggen. Dit zou ons in principe in staat stellen om zo de zijden van de merktekens op te sporen en deze in een volgende fase verder te koppelen. Wanneer echter de zijden van de merktekens in het beeldvlak kleiner worden, zullen deze maar moeilijk meer gevonden worden. Bovendien werken deze methodes zo dat vooral de langste lijnen worden ontdekt. Wanneer op de achtergrond langere lijnen te zien zijn, zullen deze lijnen gevonden worden, terwijl de zijden van de merktekens eerder buiten beschouwing zullen gelaten worden. Bij lokale methodes echter wordt in een kleine omgeving (vb. 3x3) rond een randpunt gezocht naar een naburig randpunt. Selectie van naburige randpunten kan op basis van informatie die bekomen werd bij de randdetectie. Bij de gradi¨ent gebaseerde methodes is dit de grootte en de richting van de gradi¨ent (formules 3.9 en 3.8). (Kyung-Seok Seo & Choi, 2006) stelt een goede methode voor om op basis van de richting horende bij de randpunten lokaal op zoek te gaan naar lijnsegmenten. Doordat er echter overgestapt werd naar de LoG-methode voor randdetectie werd deze informatie verloren. De tweede afgeleide is invariant t.o.v. de richting, zodat de voorgaande methode onbruikbaar wordt. Wel levert de LoG-methode een ander soort informatie, via het teken van de tweede afgeleide kunnen we immers te weten komen langs welke kant van de rand een bepaald punt ligt. Hiervan werd in deze fase dan ook handig gebruik gemaakt.
62
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.25: Verband tussen het teken van de 2e afgeleide en de overgang van de intensiteiten.
Dit wordt getoond in figuur 3.25. Bovenaan wordt een rand getoond van een gebied waarbij overgegaan wordt van donkere naar lichtere grijswaarden, onderaan wordt het omgekeerde geval weergegeven. In het midden wordt het profiel van beide randen weergegeven, rechts de tweede afgeleide na Gaussian smoothing (LoG). In het eerste geval gaat de tweede afgeleide van links naar rechts over van positieve naar negatieve waarden, in het tweede geval van negatieve naar positieve waarden. Zoals weergegeven in figuur 3.22 werden overgangen tussen LoG-waarden bekeken van links naar rechts en van boven naar onder. Wanneer we een merkteken bekijken betekent dit dat bij de zijde die links ligt en de zijde bovenaan, een overgang wordt gevonden van negatieve naar positieve LoG-waarden, bij de zijde onderaan en rechts van positieve naar negatieve LoG-waarden. We kennen dan ook labels toe tijdens LoG-randdetectie aan elk van de randpunten. Een label bestaat hierbij uit een waarde voor de overgang van links naar rechts en van boven naar onder. Telkens krijgt 1 van beide een relevante waarde.
Figuur 3.26: Mogelijke labels voor punten op segmenten in verschillende richtingen.
63
Hoofdstuk 3. Extractie en identificatie merktekens Figuur 3.26 geeft een overzicht van de labels van de punten die voorkomen op de verschillende zijden van een merkteken. Telkens staat bovenaan de waarde bij een overgang van boven naar onder, onderaan de waarde bij een overgang van links naar rechts. Wanneer een merkteken in het beeldvlak mooi recht ligt, zal er op elk van de randen maar 1 label terug komen. Wanneer het merkteken en dus ook de zijden schuin liggen, kunnen er 2 labels voorkomen op een zijde. Een randpunt kan in dit geval immers zowel terug gevonden worden door de overgang in grijswaarden van boven naar onder als van links naar rechts. Veronderstel dat binnen in de achthoek in figuur 3.26 donkere grijswaarden voorkomen, erbuiten lichte (dit komt overeen met de lichtere grijswaarden buiten een merkteken en de donkere grijswaarden in de rand erbinnen). Bij de zijde van de achthoek linksboven zal een randpunt dan gevonden worden via een overgang van negatieve naar een positieve LoG-waarde van boven naar onder (label 1-3) of van links naar rechts (label 3-1). Het cijfer 3 duidt erop dat de overgang in die richting niet werd gevonden. Op deze manier werden alle labels op de figuur toegekend. Wanneer we nu op zoek gaan naar naburige randpunten, selecteren we deze op basis van hun label. Wanneer dan bijvoorbeeld in een 3x3-omgeving rond een randpunt 2 naburige randpunten liggen, waarbij het ene het volgende punt is van de rand van het merkteken en het andere een punt is afkomstig van de rand van een bitveldje, zal het eerste punt geselecteerd worden. Op deze manier zal de contour rond een merkteken mooi gevolg worden, zonder over te gaan naar andere contouren, dit zorgde oorspronkelijk voor de grootste problemen bij het linken van randpunten. Het is echter niet zo dat enkel randpunten met hetzelfde label op mekaar volgen. Het label 1-3 kan bijvoorbeeld samen met het label 3-2 of 3-1 voorkomen op hetzelfde segment. Wanneer wordt overgegaan op een volgend segment kunnen ook de labels 3-1 of 2-3 gevonden worden, bij overlopen van de contour in tegenwijzerzin. Dit betekent dat elk label in feite kan volgen op elk ander label, de volgorde waarin labels getest worden speelt echter wel een grote rol. In eerste instantie wordt een naburig randpunt gezocht met hetzelfde label als dit van het huidig randpunt. Nadien wordt gezocht naar randpunten met een label dat samen met het huidig label kan voorkomen op hetzelfde segment. Tenslotte wordt gezocht naar een label dat voorkomt op een volgend segment. In eerste instantie werd gezocht naar geschikte naburige randpunten in een 3x3-omgeving en werd het punt op de kleinste afstand geselecteerd, maar uiteindelijk werd overgeschakeld naar een methode met zoekprioriteiten”. In functie van het huidige label, het volgend label dat ” wordt gezocht en het feit of de contour wordt overlopen in wijzerzin of tegenwijzerzin, kan een volgend randpunt maar op bepaalde plaatsen in de 3x3 omgeving voorkomen. Bovendien kan per plaats een prioriteit worden toegekend afhankelijk van de kans dat het randpunt op die bepaalde plaats voorkomt. Op deze manier zal het volgende randpunt vaak na ´e´en 64
Hoofdstuk 3. Extractie en identificatie merktekens opzoekoperatie gevonden worden en wordt de kans nog groter dat telkens het juiste volgende randpunt wordt geselecteerd. Figuren 3.27 en 3.28 tonen de zoekvensters en bijhorende zoekprioriteiten (lagere waarden geven een hogere prioriteit aan) bij zoeken van een naburig randpunt met hetzelfde label (links) en bij zoeken van een naburig randpunt op hetzelfde segment en dit respectievelijk in wijzerzin en in tegenwijzerzin. Figuren 3.29 en 3.30 tonen de zoekvensters en bijhorende zoekprioriteiten bij zoeken van een naburig randpunt op een volgend segment en dit respectievelijk in wijzerzin en in tegenwijzerzin. De pixels op de lokaties die aangeduid zijn in het rood worden niet meer bekeken, aangezien deze plaatsen reeds werden bekeken in de vorige fase (bij zoeken van randpunten op hetzelfde segment).
Figuur 3.27: Zoekvensters vanuit een randpunt naar een volgend randpunt op een zelfde segment met bijhorende prioriteiten, bij zoeken in wijzerzin.
65
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.28: Zoekvensters vanuit een randpunt naar een volgend randpunt op een zelfde segment met bijhorende prioriteiten, bij zoeken in tegenwijzerzin.
Figuur 3.29: Zoekvensters vanuit een randpunt naar een volgend randpunt op een volgend segment met bijhorende prioriteiten, bij zoeken in wijzerzin.
66
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.30: Zoekvensters vanuit een randpunt naar een volgend randpunt op een volgend segment met bijhorende prioriteiten, bij zoeken in tegenwijzerzin.
Wanneer er geen volgend randpunt meer kan gevonden worden in wijzerzin/tegenwijzerzin, wordt terug gezocht in de andere richting vanaf het beginpunt. Bij een lus wordt een contour volledig doorlopen in ´e´en richting, maar bij een contour die bijvoorbeeld door de rand van de figuur wordt onderbroken is dit niet het geval. Contouren die bestaan uit een klein aantal punten, worden na deze fase buiten beschouwing gelaten. Op deze manier wordt nog meer ruis en detail ge¨elimineerd. Telkens wordt het startpunt van een contour gezocht beginnende van het startpunt van de vorige contour, zoeken van alle startpunten vereist dus O(ab) bewerkingen met a × b de resolutie van een beeld. Zoeken van een buurpunt is O(1) zodat het opsporen van een contour met lengte l O(l) is.
3.7
Onderzoek krommming
We beschikken nu over een reeks contouren. Uit deze reeks moeten de contouren geselecteerd worden van de kandidaat-merktekens. Deze selectie gebeurt op basis van het aantal hoeken, dit moet gelijk zijn aan vier. (Mokhtarian & Suomela, 1998) en de verbeterde methode (He & Yung, 2004) stellen een methode voor die op basis van de co¨ordinaten van de punten van 67
Hoofdstuk 3. Extractie en identificatie merktekens een contour de punten selecteert die overeen komen met de hoeken, een curvature scale space hoekdetector. Deze methode zou als hoekdetector bovendien beter presteren dan vele bekende methodes zoals de Harris Corner detector”. ” Hiertoe wordt gebruik gemaakt van de kromming in elk punt van de contour: ˙ X(u, σ) ¨ ˙ ¨ X(u, σ) X(u, σ)Y¨ (u, σ) − X(u, σ)Y˙ (u, σ) met K(u, σ) = ˙ Y˙ (u, σ) (X(u, σ)2 + Y˙ (u, σ)2 )1.5 Y¨ (u, σ)
= = = =
x(u) x(u) y(u) y(u)
⊗ ⊗ ⊗ ⊗
g(u, ˙ σ) g¨(u, σ) g(u, ˙ σ) g¨(u, σ)
(3.13)
g(u, σ) is een 1D-Gaussiaanse functie (sectie 3.1.4), g(u, ˙ σ) en g¨(u, σ) stellen respectievelijk de eerste en tweede afgeleide van deze Gaussiaanse voor. ⊗ stelt een 1D-convolutie operator voor (sectie 3.1.1). Er moet m.a.w. een 1D-convolutie worden uitgevoerd op de x- en y-co¨ordinaten van de punten van een contour met de eerste en tweede afgeleide van een 1D-Gaussiaanse functie. Deze afgeleide functies van de Gaussiaanse moeten dus worden benaderd via de co¨effici¨enten van een masker, deze maskers worden op voorhand bepaald. Zoals beschreven in sectie 3.1.1 zullen bepaalde co¨effici¨enten van het masker niet overlappen met punten van de contour. Om toch een correcte waarde voor de kromming te bekomen voor de punten aan de uiteinden van een contour, wordt er niet zomaar aangevuld met nullen, zoals in 3.1.1 wordt voorgesteld. Wanneer de contour een lus vormt, worden de punten in rekening gebracht aan de andere kant van de contour, de contour loopt in realiteit namelijk gewoon door. Wanneer de contour geen lus is, wordt de contour aan de uiteinden a.h.w. doorgetrokken m.b.v. een lijnstuk dat wordt bepaald in functie van de laatste punten van de contour. Van deze methode voor hoekdetectie zijn 2 stappen bruikbaar: Bepaal de kromming in elk punt van de contour bij gebruik van een constante lage schaal (σ stelt hierbij de schaal voor). Alle punten waarvoor de kromming een lokaal maximum bereikt, worden als kandidaathoeken beschouwd. Twee criteria worden gebruikt om de valse hoeken te elimineren: adaptive local threshold en angle of corner.
68
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.31: Kromming in de punten van een contour van een merkteken (σ = 3) met de lokale minima en maxima.
Figuur 3.31 geeft een voorbeeld van de kromming in de randpunten van een contour van een merkteken. In een eerste fase worden de lokale minima en maxima bepaald (aangeduid in groen en rood op figuur 3.31). Alle lokale maxima worden als kandidaat-hoeken beschouwd. De vier grootste pieken stellen hier duidelijk de vier hoeken voor van het merkteken, maar in realiteit zal dit niet altijd het geval zijn (zie verder). Bovendien beschikken we nu nog over heel wat contouren die geen contouren van merktekens zijn. Als we dan zomaar van elke contour de 4 punten met de grootste kromming als hoeken zouden nemen, zouden we onnodig veel kandidaat-merktekens overhouden, wat dan meer kans zou geven op detectie van valse merktekens. Daarom worden er twee criteria gebruikt om de juiste hoeken te selecteren. Vaak worden er punten als kandidaat-hoeken beschouwd waarvan de kromming weinig verschilt t.o.v. deze van de naburige punten, dit is bijvoorbeeld het geval bij afgeronde hoeken. Het criterium adaptive local threshold tracht deze valse hoeken te elimineren. Hiertoe wordt voor elk lokaal maximum een lokale thresholdwaarde bepaald: u+L1 X 1 K(i) T (u) = C × K = C × L1 + L2 + 1
(3.14)
i=u−L2
met K de gemiddelde waarde van de kromming in een bepaald gebied, de region of support (ROS ). De ROS loopt voor een lokaal maximum van het voorgaande lokale minimum tot het volgende lokale minimum. L1 en L2 zijn het aantal punten vanaf het voorgaande lokale minimum tot het huidige lokale maximum en vanaf het huidige lokale maximum tot het volgende lokale minimum. C is een co¨effici¨ent, bij een waarde van 1 wordt er geen enkele hoek verwijderd, bij een waarde van 2 wordt elke hoek verwijderd. Een waarde van 1.5 voor C blijkt globaal een goede waarde te zijn. 69
Hoofdstuk 3. Extractie en identificatie merktekens De contour maakt bij een hoek van een merkteken een vrij uitgesproken bocht” (vrij scherpe ” hoek). Het criterium angle of corner elimineert hoeken waarvoor dit niet het geval is. Een gepaste ROS is hier weer van belang, deze loopt voor elk lokaal maximum van het vorige lokale maximum tot het volgende lokale maximum. Het criterium op basis waarvan hoeken worden ge¨elimineerd wordt toegepast op elk lokaal maximum dat overgebleven is na het eerste criterium:
Wanneer threshhoek ° ≤ ∠C1 ≤ 360 − threshhoek °, dan is C1 geen hoek, anders is C1 wel een hoek. ∠C1 wordt hierbij gegeven door: ∠C1 = tan−1 (∆Y1 /∆X1 ) − tan−1 (∆Y2 /∆X2 ) , met Pu+L1 ∆X1 = L11 X(i) − X(u) i=u+1 Pu−1 1 ∆X2 = L1 X(i) − X(u) 2 Pi=u−L u+L1 1 ∆Y1 = L1 Y (i) − Y (u) i=u+1 Pu−1 1 Y (i) − Y (u) ∆Y2 = L2 i=u−L2 met L1 L2
(3.15)
(3.16)
(3.17)
het aantal randpunten tussen het vorige en het huidige lokale maximum, het aantal randpunten tussen het huidige en het volgende lokale maximum
Een waarde van 160 voor threshhoek blijkt globaal goed te werken.
Figuur 3.32: Voorbeeld voor het elimineren van valse hoeken m.b.v. het criterium angle of corner.
Dit criterium wordt iteratief toegepast tot wanneer er geen valse hoeken meer konden ge¨elimineerd worden. Via dit criterium worden dan kandidaat-hoeken, ontstaan door ruis en triviale details ge¨elimineerd. Op figuur 3.32 bijvoorbeeld zijn 1 → 5 oorspronkelijk de lokale maxima. Voor 1 en 5 is er geen vorig/volgend lokaal maximum. Dit hebben we opgelost door bij een lus de hoek te nemen aan het andere uiteinde van de contour, dus het laatste lokale maximum stelt het vorige lokale maximum voor van het eerste lokale maximum, het eerste lokale maximum stelt het volgende lokale maximum voor van het laatste lokale maximum. Bij een contour die geen lus is, worden de uiteinden van de contour gebruikt, dus het eerste punt voor het eerste lokale maximum, het laatste punt voor het laatste lokale maximum. Wanneer na toepassen van het eerste criterium alle lokale maxima behouden blijven, zal de ROS voor 3 van 2 → 4 lopen, 3 zal dan behouden blijven wegens de relatief scherpe hoek. Wanneer echter enkel 1, 3 en 5 zouden behouden blijven als kandidaat-hoeken na toepassen
70
Hoofdstuk 3. Extractie en identificatie merktekens van het eerste criterium, zal de ROS voor 3 nu lopen van 1 → 5 en zal 3 waarschijnlijk ge¨elimineerd worden wegens de bijna rechte lijn tussen 1 en 5.
Figuur 3.33: Links: Testafbeelding, gemaakt met minst goede camera (wazig beeld). Maxima (rood) voor de kromming die als hoeken herkend werden en naburige minima (geel) bij een σ gelijk aan 4 (midden) en 9 (rechts).
Belangrijk bij dit algoritme is de keuze van σ bij berekening van de kromming (formule 3.13). Globaal blijkt een σ gelijk aan 3 vrij goed te werken. Toch treden er hierbij soms problemen op, bijvoorbeeld wanneer de camerabeelden minder scherp zijn. Figuur 3.33 toont links een afbeelding van een merkteken gemaakt met de minst goede camera (bespreking gebruikte camera’s: zie sectie 3.2). Het beeld is hier vrij wazig, zodat de grijswaarden aan de rand van het merkteken slechts geleidelijk veranderen. Wanneer we hier randdetectie (LoG) op toepassen, zien we dat de zijden van het merkteken, benaderd door de randpunten, nu niet steeds recht lopen. Bijgevolg worden er bij een lagere waarde voor σ verkeerdelijk andere randpunten als hoeken herkend (aangeduid in rood, midden op figuur 3.33). Bij een grotere waarde voor σ worden de hoeken wel correct herkend (figuur 3.33, rechts).
71
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.34: Kromming in punten van de contour bij σ gelijk aan 4. Maxima die overeenkomen met hoeken werden aangeduid in rood en worden rechts in een lijst vermeld. De hoeken die ook de echte hoeken zijn van het merkteken, werden aangeduid in de lijst.
Waarom dit gebeurt wordt duidelijk wanneer we de kromming in de randpunten bekijken. Figuur 3.34 toont de kromming in de randpunten bij gebruik van een σ gelijk aan 4. De lokale maxima aangeduid in het rood komen overeen met de randpunten die werden herkend als hoeken. Een lijst van de nummers van deze punten wordt ook rechts weergegeven. De randpunten die effectief overeenkomen met de echte hoeken van het merkteken werden aangeduid in groen, hieruit blijkt ook dat de 2 grote pieken bij de kromming niet eens overeenkomen met echte hoeken.
72
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.35: Kromming in punten van de contour bij σ gelijk aan 9. Maxima die overeenkomen met hoeken werden aangeduid in rood.
De kromming in de randpunten voor een σ gelijk aan 9 (figuur 3.35), toont echter wel duidelijk 4 pieken die ook overeenkomen met de echte hoeken van het merkteken (De piek in het begin en op het einde vormt ´e´en geheel aangezien de contour een lus vormt). De grotere waarde voor σ zorgt er immers voor dat de contour zodanig wordt uitgemiddeld” dat enkel de echte ” grote features”, de echte hoeken, duidelijk blijven. ”
Figuur 3.36: Lokale Maxima (rood) die overeenkomen met hoeken en naburige minima (geel) bij een σ gelijk aan 4 (links) en 9 (rechts).
Wanneer we nu echter een beeld van een ander merkteken bekijken dat kleiner is, gemaakt met dezelfde camera, treedt er een probleem op. Slechts drie van de vier hoeken worden nog herkend bij een σ gelijk aan 9, terwijl alle vier de hoeken wel correct werden herkend bij een 73
Hoofdstuk 3. Extractie en identificatie merktekens σ gelijk aan 4.
Figuur 3.37: Maxima (rood) en minima (geel) bij een σ gelijk aan 9 (links) en 3 (rechts).
Wanneer we een beeld met 12 merktekens bekijken (figuur 3.37), die nog kleiner zijn, gemaakt met een betere camera, wordt geen enkele hoek meer gevonden bij een σ gelijk aan 9, bij σ gelijk aan 3 werden alle hoeken wel nog correct gevonden. Dit probleem werd opgelost door σ dynamisch te laten vari¨eren. We gebruiken een minimumwaarde, σmin en een maximumwaarde σmax voor σ. Voor elke contour bepalen we de hoeken voor σmin , indien er teveel hoeken gevonden werden, bepalen we de hoeken opnieuw voor een grotere σ, die maximaal σmax wordt. Indien we op een bepaald moment 4 hoeken vinden, beschouwen we de contour als deze van een kandidaat-merkteken. Om niet alle mogelijke waarden voor σ te moeten proberen, werd de mogelijkheid voorzien om de waarden voor σ in stappen van σstep te proberen. Wanneer er bij een bepaald σ1 meer dan 4 en bij een andere σ2 minder dan 4 hoeken worden gevonden, worden de waarden voor σ tussen σ1 en σ2 lineair geprobeerd. De waarden die best voor σmin en σmax worden gebruikt, hangen af van de camera. Vaak werkt een waarde gelijk aan 3 voor beide vrij goed. Het veiligste zijn bijvoorbeeld de waarden 3 en 10, maar dit zal de verwerkingstijd per frame wel iets doen toenemen. Voor een contour met lengte l is het bepalen van de kromming O(ld) met d de grootte van de maskers van de afgeleide van de Gaussiaanse. Bepalen van de lokale minima en maxima is O(l). Toepassing van het 1e criterium (adaptive local threshold ) is eveneens O(l). Het 2e criterium zou in het slechtste geval O(l ∗ m) kunnen zijn, met m het aantal maxima die overgehouden worden na toepassing van het 1e criterium. Dit kan wanneer er telkens slechts 1 maximum wordt ge¨elimineerd, maar in praktijk blijkt dit goed mee te vallen.
74
Hoofdstuk 3. Extractie en identificatie merktekens
3.8
Linken contouren
Zoals vermeld in sectie 3.5.2 kan er een threshold-waarde gebruikt worden bij de LoG-methode. Dit kan wel als gevolg hebben dat er hier en daar een randpunt verdwijnt op de contour van een merkteken. De methode zoals ze nu reeds werd beschreven kan sowieso overweg met contouren van merktekens waar randpunten ontbreken zodat ´e´en zijde of ´e´en hoek onderbroken is, op voorwaarde dat de overige delen van de zijden lang genoeg zijn en de overige hoeken correct worden herkend. Wanneer er nog bijkomende randpunten ontbreken, zou een merkteken niet meer worden herkend. Om dit enigzins te vermijden werd ook de mogelijkheid voorzien om contouren achteraf te linken. Hiertoe wordt aan het uiteinde van een contour gezocht naar naburige contouren. Bij de hoekdetectie worden de contouren die niet voldeden, maar wel een zekere lengte hebben, apart bijgehouden. Deze worden dan doorgegeven” aan deze fase. ”
Figuur 3.38: Maskers gebruikt bij achteraf linken contouren.
Hiertoe worden de maskers gebruikt uit figuur 3.38. De vorm van het masker hangt weer af van het label van het eindpunt van de contour, van waaruit een andere contour wordt gezocht. In de 3x3 - omgeving rond het uiteinde van de huidige contour wordt niet meer gezocht, aangezien deze omgeving reeds werd doorzocht bij het linken van randpunten tot contouren (sectie 3.6). De breedte van de maskers is instelbaar (is gelijk aan 2 in figuur 3.38). Vanuit het huidige punt wordt dan gezocht naar eindpunten van andere contouren. Eerst wordt er gezocht op de lokaties in de rand die 2 pixels verwijderd ligt van het huidige punt, dan 3 pixels ver. . . Wanneer 2 contouren werden gelinkt, wordt ook vanuit deze samengestelde contour verder gezocht naar naburige contouren. Op deze manier kunnen meerdere gaatjes in een contour nog hersteld worden. Dit alles werd ge¨ımplementeerd via lookup-tabellen, zodat het linken van 2 contouren in O(1) kan gebeuren. Het zoeken van de beginpunten van de samengestelde contouren vereist a ∗ b bewerkingen met a × b de resolutie van een beeld. De gelinkte contouren worden terug onderworpen aan hoekdetectie, indien ze nu wel voldoen aan de voorwaarden kunnen ze alsnog als kandidaat-merktekens in aanmerking komen.
75
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.39: Voorbeeld succesvol toepassen van het achteraf linken van contouren.
Figuur 3.39 toont een voorbeeld van een merkteken waarbij deze fase succesvol werd toegepast. Doordat er een vrij hoge threshold-waarde werd gebruikt bij de LoG-methode was de contour op 2 plaatsen onderbroken en werd ze dus als 2 aparte contouren herkend. Door de volgorde waarin pixels worden getest en de volgorde waarin labels in aanmerking komen, is de kans bovendien klein dat de contour horende bij het inwendig bitveldje wordt gelinkt.
3.8.1
Extractie segmenten, bepalen hoeken
We beschikken nu over de co¨ordinaten van de punten op de contour die ongeveer overeenkomen met de hoeken van het merkteken. Vaak is deze schatting echter nog niet echt nauwkeurig omdat de contour vb. afgerond is aan de hoeken. Dit is zichtbaar in figuren 3.33 en 3.36. Daarom wordt in deze fase een betere benadering voor de hoeken gezocht. Hiertoe worden rechten aangemeten aan de vier zijden van de contour. De snijpunten van deze rechten leveren dan de uiteindelijke co¨ordinaten van de hoeken. Om ervoor te zorgen dat de afgeronde hoeken geen nadelige invloed hebben op de benadering voor deze rechten wordt er voor elke zijde een segment bepaald dat eindigt waar de kromming in de contour te groot wordt.
76
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.40: Kromming hoeken, naburige minima (rood) en eindpunten segmenten (groen).
Hiertoe wordt een threshold gekozen voor de kromming in de uiteinden van de segmenten. Deze threshold-waarde wordt gekozen i.f.v. de kromming in het overeenkomstige lokale maximum en het naburige minimum. Dit wordt weergegeven in figuur 3.40. De threshold-waarde is hier ongeveer krommingmax − krommingmin (3.18) 2 De noemer in de breuk is hierbij instelbaar, het punt op de contour dat met die kromming ongeveer overeen komt wordt gevonden door binair zoeken in de opeenvolgende waarden voor de kromming. Zoeken van een eindpunt van een segment is dus O(lg(aantalLoG−punten in[min, max]). krommingmin +
Figuur 3.41: Minima (geel) en maxima (rood) van de kromming, eindpunten segmenten (blauw), uiteindelijke hoeken (paars).
De blauwe markeringen in figuur 3.41 tonen dan de gevonden uiteinden van de segmenten. Zeker wanneer de breedte van het merkteken kleiner wordt, is deze fase van belang (figuur 3.41, rechts). Een minder goede benadering van de hoeken levert immers problemen voor de volgende fase, maar ook voor de positiebepaling (sectie 4.3). 77
Hoofdstuk 3. Extractie en identificatie merktekens Voor de rechten die worden aangemeten aan de zijden van een merkteken worden de parameters a, b en c in de vergelijking ax+by +c = 0 bepaald i.f.v. de co¨ordinaten van de randpunten op de overeenkomstige segmenten m.b.v. de kleinste kwadraten methode (dit werd trouwens ook door (Kyung-Seok Seo & Choi, 2006) gebruikt): S
xy b = Sxy = Sxx met a = y − bx Sxx =
Pn i=1 (xi − x)(yi − y) Pn 2 i=1 (xi − x)
(3.19)
De hoeken (aangeduid in paars op figuur 3.41) zijn dan de snijpunten van deze rechten. Bepalen van de parameters voor een segment met lengte s is dus O(s). Bepalen van de hoeken is O(1).
3.9
Sampling bitpatroon
Nu we de hoeken van alle kandidaat-merktekens gevonden hebben kunnen we deze tenslotte identificeren. Hiertoe moet de waarde van het interne bitpatroon bekomen worden. Eerst wordt een homografie bepaald i.f.v. de co¨ordinaten van de hoeken van een kandidaatmerkteken (zie sectie 3.1.2).
Figuur 3.42: Unwarping beeld merkteken, origineel beeld (links), beeld merkteken na unwarping (midden) en na thresholding (rechts). .
Deze werd in eerste instantie gebruikt om het beeld van een merkteken te extraheren uit een frame (figuur 3.42) en terug te brengen naar de originele vorm (dit wordt unwarping genoemd). Op deze manier zou dan op het volledige bekomen beeld een threshold-waarde kunnen bepaald worden. De samplingpunten liggen dan in dit geval op een vierkantig raster. Door de grijswaarde bij elk samplingpunt te vergelijken met de threshold-waarde zouden dan de waarden van de bits kunnen bepaald worden. Figuur 3.42 toont ter illustratie het merkteken wanneer er thresholding zou worden toegepast op het volledige beeld.
78
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.43: Samplingpunten aanpassen aan de vorm van het merkteken.
Deze methode vraagt echter onnodig veel tijd. De waarde van elke pixel binnen het beeld van het merkteken moet worden bepaald, terwijl enkel de samplingpunten van belang zijn. Daarom werd ervoor gekozen om de samplingpunten aan te passen aan de vorm van het merkteken. De co¨ordinaten van de samplingpunten worden op voorhand bepaald t.o.v. het oorspronkelijke merkteken (figuur 3.43 links). Voor elk merkteken worden dan de co¨ordinaten van de uiteindelijke samplingpunten bepaald door de matrix van de homografie te vermenigvuldigen met de oorspronkelijke samplingpunten (figuur 3.43, rechts). Nu wordt een thresholdminsamplingwaarde +maxsamplingwaarde gebruikt om de waarde van het bitpatroon waarde gelijk aan 2 te bekomen. Deze threshold-waarde blijkt globaal goed te werken. Dit betekent wel dat een merkteken geen volledig wit of zwart bitpatroon mag hebben, maar hiervoor hebben we reeds gezorgd tijdens de merktekengeneratie (zie sectie 2.5).
Figuur 3.44: Extra controles bij sampling.
Tijdens deze fase wordt er eerst nog een controle uitgevoerd op de kleur van de rand. Hiertoe worden de grijswaarden in de rand en net buiten de rand met elkaar vergeleken. De koppels punten, met telkens een punt binnen en net buiten de rand worden vergeleken, zoals getoond door de groene markeringen in figuur 3.44. Oorspronkelijk werd geprobeerd dit te controleren door binnen de rand het teken van het LoG-gefilterde beeld (figuur 3.21) te bekijken, maar dit bleek onbetrouwbaar omdat er ook binnen de rand vaak tekenwissels optreden. Wanneer 79
Hoofdstuk 3. Extractie en identificatie merktekens er teveel koppels zijn waarbij de intensiteit buiten de rand lager ligt dan binnen de rand, wordt het bitpatroon niet bekeken, zoals in figuur 3.44 het geval is bij het witte bitveldje. Wanneer een vals merkteken wordt gevonden met binnenin een wit of zwart vlak of algemeen met grijswaarden die weinig verschillend zijn, is de kans nu wel groter dat toch een geldig bitpatroon wordt gevonden. Door de gekozen threshold zullen er immers altijd grijswaarden zijn die er boven of onder liggen. Daarom worden er nog 2 eenvoudige correcties toegepast. Enerzijds wordt de grijswaarde van elk 1-bit vergeleken met het gemiddelde van de grijswaarden van de dichtstbij gelegen randen (voor het bit op rij 1 en kolom 3 bij figuur 3.44 wordt vb. het gemiddelde genomen van de grijswaarde van het derde samplingpunt van de rand bovenaan en de grijswaarde van het eerste samplingpunt van de rechterrand). Wanneer deze grijswaarde te dicht bij dit gemiddelde ligt, wordt de 1-bit gewijzigd in een 0-bit. Anderzijds wordt het minimum van de sampling-waarden van het bitpatroon (een 0-bit) weer vergeleken met het gemiddelde van de dichtstbij gelegen randen. Wanneer het verschil tussen beide te groot is, wordt het merkteken verworpen. Dit kan vb. wijzen op een zwarte rand en een volledig wit inwendig patroon. Per kandidaat-merkteken is er een constant aantal sampling-punten zodat dit O(1) is.
3.10
Extra eliminatiecriteria
Op de kandidaat-merktekens worden nog twee eenvoudige eliminatiecriteria toegepast. Enerzijds is er een beperking op de lengte van elke zijde (gemeten in pixeleenheden). Deze moet immers lang genoeg zijn om sampling mogelijk te maken. Wanneer een zijde vb. kleiner is dan 2 ∗ dikterand + aantal bits per zijde, zouden sommige samplingpunten binnen dezelfde pixel vallen, waardoor het merkteken onmogelijk betrouwbaar kan ge¨ıdentificeerd worden. Anderzijds wordt er gecontroleerd of de diagonalen elkaar snijden. Dit gebeurt door voor beide diagonalen te controleren of de eindpunten langs weerszijden van de andere diagonaal vallen. Deze twee eenvoudige criteria zorgen ervoor dat vrij veel merktekens niet verder dienen behandeld te worden en kan in O(1) per kandidaat-merkteken uitgevoerd worden.
80
Hoofdstuk 3. Extractie en identificatie merktekens
3.11
Eindresultaat
Figuur 3.45: Overzicht extractie merktekens.
Voor de extractie van de merktekens worden dus achtereenvolgens (figuur 3.45) volgende bewerkingen toegepast: Frame afkomstig van camera, wordt naar grijswaarden omgezet. Randdetectie via de LoG-methode en opsporen van de contouren. Onderzoek kromming in de contour, enkel contouren waar vier maxima voor de kromming overgehouden worden, worden doorgegeven naar de volgende fase. Linken van contouren met te weinig kandidaat-hoeken, bij de gelinkte contouren wordt de kromming opnieuw onderzocht. Rechten aanmeten aan de zijden van de kandidaat-merkteken, bepalen betere benadering hoeken. Sampling bitpatroon. Correcte extractie en identificatie.
Dit alles wordt ge¨ımplementeerd door de klasse MarkerExtractor. Hier worden de belangrijkste functies weergegeven die instaan voor uitvoering van de verschillende fasen. Daarnaast zijn er nog een reeks hulpfuncties die we hier niet vermelden. Telkens werden de belangrijkste parameters vermeld met een aanduiding of het invoer- of uitvoerparamers zijn.
81
Hoofdstuk 3. Extractie en identificatie merktekens Ook worden een aantal belangrijke attributen van deze klasse vermeld. Zo stellen cssGaussDeriv1Masks, cssGaussDeriv2Masks en kernel een aantal maskers voor die op voorhand worden bepaald. De andere attributen die hier vermeld worden, zijn tabellen die door verschillende methodes gebruikt worden. Ze worden als attributen bijgehouden zodat ze slechts eenmaal moeten aangemaakt worden (cvCreateMat) en ze achteraf eenmaal moeten vrijgegeven worden (cvReleaseMat). c l a s s Ma r ke rE xt r ac t or { private : // maskers voor e e r s t e a f g e l e i d e G a u s s i a a n s e v e c t o r cssGaussDeriv1Masks ; // maskers voor t w e e d e a f g e l e i d e G a u s s ia a n s e v e c t o r cssGaussDeriv2Masks ; //LoG − k e r n e l CvMat * k e r n e l ; // l o o k u p −t a b e l voor l a b e l n u l d o o r g a n g e n i n v e r t i c a l e r i c h t i n g CvMat * tbMap ; // l o o k u p −t a b e l voor l a b e l n u l d o o r g a n g e n i n h o r i z o n t a l e r i c h t i n g CvMat * lrMap ; // l o o k u p −t a b e l voor s u b p i x e l −c o ¨ o r d i n a t e n randpunten CvMatND* pointsEdgeMap ; // o o r s p r o n k e l i j k e sampling −punten CvMat * s r c P t s ; // l o o k u p −t a b e l voor de e i n d p u n t e n van c o n t o u r e n d i e i n aanmerking //komen om g e l i n k t t e worden met andere c o n t o u r e n CvMat * endPtsLink ; // l o o k u p −t a b e l voor de i n d i c e s van de c o n t o u r e n d i e i n aanmerking //komen om g e l i n k t t e worden met andere c o n t o u r e n CvMat * i C o n t o u r L i n k ; public : M a r ke rE xt r ac to r ( i n
marke rCo nfi g , i n
markerExtractConfig ) ;
void e x t r a c t M a r k e r s ( i n / u i t frame , u i t r e s u l t i n g M a r k e r s ) ; void z e r o C r o s s i n g s L o G ( i n frame , u i t imgGray , i n k e r n e l ) ;
82
Hoofdstuk 3. Extractie en identificatie merktekens
void e x t r a c t C o n t o u r s ( u i t c o n t o u r s ) ; void getExtremaContours ( i n c o n t o u r s , u i t minimaCurvatures , u i t maximaCurvatures , u i t c o n t o u r C u r v a t u r e s , uit linkableContours ) ; void g e t L i n k e d C o n t o u r s ( i n l i n k a b l e C o n t o u r s , u i t l i n k e d C o n t o u r s ) ; void f i n d L i n k S e g m e n t s ( u i t contoursSegments , u i t contoursSegmentsParams , i n c o n t o u r s , i n minimaCurvatures , i n maximaCurvatures , i n c o n t o u r C u r v a t u r e s ) ; void g e t C o r n e r s P o s s i b l e M a r k e r s ( u i t c a n d i d a t e M a r k e r s , i n contoursSegmentsParams ) ; I d e n t i f i c a t i o n i d e n t i f y M a r k e r ( i n c o r n e r s , i n imgGray ) ; ... };
3.12
Prestaties
Hier worden de prestaties van de merktekenextractie bekeken in functie van de criteria die vooropgesteld werden in sectie 3.3.
3.12.1
Grootte gedetecteerd merkteken
Enerzijds hangt dit af van de rand- en hoekdetectie. Contouren van vrij kleine objecten blijken echter vrij goed benaderd te worden en de hoekdetectie blijft vrij betrouwbaar, wanneer de σ bij deze methodes niet te groot wordt genomen. De prestaties voor dit criterium hangen vooral samen met de dikte van de rand van het merkteken en het aantal bits van het bitpatroon. Op grote afstand en bij gebruik van een dunne rand voor de merktekens zal deze rand minder duidelijk aanwezig zijn in het beeld en lopen de grijswaarden van de omgeving over in de grijswaarden van de witte bitveldjes, de contour wordt dan niet meer gevonden. De bitveldjes moeten echter ook steeds voldoende kunnen afgescheiden worden, ze moeten een bepaalde breedte hebben in de camerabeelden waardoor een merkteken met meer bits per zijde ook een grotere breedte in het frame zal moeten hebben om herkend te worden.
83
Hoofdstuk 3. Extractie en identificatie merktekens De minimum breedte in het frame van een herkend merkteken werd getest bij verschillende configuraties, met de tweede camera uit sectie 3.2.
Figuur 3.46: Minimale breedte herkende merktekens met een bitpatroon van 2x2. Boven: randdikte 1, Onder: randdikte 2
Voor de test met de merktekens met 2x2 bits werden de merktekens uit figuur 3.46 gebruikt. Bij randdikte 1 werden ze nog herkend bij een breedte van +/- 8 pixels. Bij randdikte 2 werd dit 11 pixels. Aangezien voor deze merktekens geen pariteitsbits werden toegevoegd en door het korte bitpatroon, werden er wel veel valse merktekens herkend. Bij een kleinere breedte van de merktekens werden deze ook nog herkend, maar het ID was vaak niet meer correct. Bitwaarden worden dan soms verkeerd bepaald en aangezien er geen foutdetectie- of correctie is, leidt dit dan ook tot een fout ID.
Figuur 3.47: Minimale breedte herkende merktekens met een bitpatroon van 3x3. Links: randdikte 1, Rechts: randdikte 2
Bij merktekens met 3x3 bits (figuur 3.47) werd de benodigde breedte respectievelijk 9 en 11 pixels. Aangezien hier CRC-4 foutdetectie werd toegepast, werden er bijna geen valse merktekens meer in de omgeving herkend.
84
Hoofdstuk 3. Extractie en identificatie merktekens
Figuur 3.48: Minimale breedte herkende merktekens met een bitpatroon van 4x4. Links: randdikte 1, Rechts: randdikte 2
Voor de merktekens met 4x4 bits was dit bijna gelijk (figuur 3.48), 11 `a 12 pixels, waarschijlijk begint hier het effect van de te dunne rand te spelen.
Figuur 3.49: Minimale breedte herkende merktekens met een bitpatroon van 6x6. Links: randdikte 1, Rechts: randdikte 2
Bij 6x6 bits werd dit ongeveer 16 pixels in beide gevallen(figuur 3.49). De minimale grootte van een gedetecteerd merkteken hangt dus inderdaad samen met het aantal eenheden waaruit een zijde bestaat (breedterand ∗ 2 + zijdebitpatroon ), maar een dikkere rand betekent niet noodzakelijk dat de merktekens groter moeten zijn. Het resultaat is wel afhankelijk van de camerabeelden. Algemeen blijkt wel dat de merktekens vrij ver herkend worden en ze zijn dan ook geschikt voor deze toepassing, de eigenlijke afstand tussen camera en merkteken hangt af van de resolutie en kwaliteit van de beelden. Er wordt veel beter gepresteerd dan bij ARToolkit (sectie 1.1), waarbij een merktekens van 20cm x 20cm niet verder dan op 2.5 m wordt herkend. Ook de prestaties van ARTag (zie 85
Hoofdstuk 3. Extractie en identificatie merktekens 1.2) worden verbeterd. Bij gebruik van merktekens analoog aan deze van ARTag wordt er ongeveer gelijk gepresteerd. Bij ARTag was er echter een ondergrens van 13 pixels om de randen op te sporen. Deze beperking is hier niet aanwezig waardoor merktekens met een kleiner aantal bits ook kleiner herkend kunnen worden.
3.12.2
Hoek tussen camera en merkteken
Figuur 3.50: Minimale hoek tussen camera en vlak merkteken, links: merktekens met 4x4 bits, rechts: merktekens met 6x6 bits.
Een merkteken wordt herkend zolang de rand van het merkteken zichtbaar blijft en de bitveldjes niet in elkaar overlopen. De prestaties voor dit criterium hangen dus weer samen met het aantal eenheden van een zijde van een merkteken. Dit wordt ook duidelijk weergegeven in figuur 3.50, links is een kleinere hoek tussen camera en vlak van het merkteken mogelijk. Aangezien het aantal samplingpunten meestal wel beperkt zal zijn, kan er doorgaans wel een vrij scherpe hoek gemaakt worden.
3.12.3
Kwaliteit camerabeelden
Figuur 3.51: Prestaties bij aanwezigheid van een aanzienlijke hoeveelheid Gaussiaanse ruis (gemiddelde waarde 0, variantie 0.02)
Wazige camerabeelden zorgen ervoor dat de bits moeilijker gelezen worden. Ook zijn de randen dan minder duidelijk. Dit zorgt ervoor dat een lagere threshold kan worden gebruikt 86
Hoofdstuk 3. Extractie en identificatie merktekens bij de randdetectie(sectie 3.5.2). De prestaties werden in dit geval wel zeer sterk verbeterd door de dynamische σ (sectie 3.7). Ook hebben we de invloed van ruis op de camerabeelden bekeken. Hiertoe werd er kunstmatig ruis aan de camerabeelden toegevoegd, zoals beschreven in 3.1.3. Zoals vermeld in 3.1.4 zorgt de Gaussiaanse filter bij de randdetectie ervoor dat de ruis a.h.w. uitgemiddeld wordt. Dit had minder effect op de Salt & pepper ruis, maar wel op de Gaussiaanse ruis. Dit werd ook proefondervindelijk duidelijk. Vele merktekens werd niet meer herkend bij de random Salt & pepper ruis, maar bij toevoegen van een aanzienlijke hoeveelheid Gaussiaanse ruis werd het grootste deel van de merktekens toch nog herkend (figuur 3.51). Hiertoe werd de σ bij de LoG-methode wel licht aangepast. De σ mag echter niet te groot worden, anders worden merktekens op grotere afstanden niet meer herkend.
3.12.4
Beweging object dat de camera draagt
Zolang de camera niet te sterk beweegt worden de merktekens nog vrij goed herkend. Bij een te snelle beweging treedt zogenaamde motion blur op, waardoor een merkteken volledig wazig wordt en de randen niet meer af te scheiden zijn. Nadien herstelt de merktekenextractie zich onmiddellijk.
3.12.5
Lichtgevoeligheid
Figuur 3.52: Prestaties bij variabele lichtinval.
Bij een vrij donkere omgeving worden de merktekens zeer goed herkend. Dit is het effect van de randdetectie, bij gebruik van vb. thresholding zou dit niet het geval zijn. Wanneer er veel direct licht invalt, heeft dit wel een effect op de zwarte bitveldjes die vlak naast de witte bitveldjes liggen (figuur 3.52). In dit geval wordt een merkteken dan soms verkeerd ge¨ıdentificeerd. 87
Hoofdstuk 3. Extractie en identificatie merktekens
3.12.6
Occlusie
Figuur 3.53: Merktekens gedetecteerd bij onderbreking door rand figuur.
Dit criterium is hier in feite niet echt belangrijk. Er kan verondersteld worden dat de merktekens niet worden bedekt met of begrensd door andere objecten. Doordat we tijdens de extractie ook niet-gesloten contouren behandelen kunnen we wel merktekens herkennen waarvan een hoek onderbroken wordt door de rand van het beeld en er niet teveel bits bedekt worden (zie figuur 3.53). Bij dit project werden toch enkele mogelijkheden onderzocht om de bekomen hoeken of segmenten verder te behandelen, vooral in Matlab. Bij de C++-implementatie werden nog twee technieken behouden. Wanneer de rand vb. te dun wordt, loopt de contour van een merkteken soms over in de rand rond een wit bitveldje en wordt er soms een extra hoek herkend. We hebben dan ook de mogelijkheid voorzien om de convex omhullende van de hoekpunten te bepalen. Hiertoe kan parameter execute bij element TryConvexHull bij de configuratie (sectie 3.15) ingesteld worden. Een tweede mogelijkheid is om bij een niet-gesloten contour segmenten in het begin of aan het einde te verwerpen. Parameter execute bij element DropExcessSegmentsLine bij de configuratie (sectie 3.15) kan hiervoor ingesteld worden. Dit kan nuttig zijn wanneer er randpunten van een ander object aanpalen aan de contour van het merkteken, zodat er een niet-gesloten contour wordt gevormd. Uiteindelijk werkt deze aanpak maar voor specifieke gevallen, zodat de algemene prestaties niet zoveel verbeterd worden voor deze toepassing.
3.13
Performantie
Bij de verschillende fasen hebben we de performantie vermeld. Convolutie van het beeld met de LoG-kernel neemt een groot deel van de tijd in beslag. Verder hangt veel af van het aantal gevonden LoG-punten en bijhorende contouren. Vele onbeduidende randen worden reeds vroeg ge¨elimineerd. Verder maakt een gepaste threshold bij de LoG-methode ook een 88
Hoofdstuk 3. Extractie en identificatie merktekens groot verschil. In praktijk zien we wel dat de verwerkingstijd stijgt naarmate er meer detail in het beeld aanwezig is. Bij dit project hebben we gewerkt met beelden met resolutie 320 × 240. We zien dat de verwerkingstijd voor de merktekenextractie per frame dan doorgaans rond de 33 ms ligt of minder, wanneer een gepast threshold-waarde bij de LoG-methode wordt gebruikt. In praktijk kunnen er minder frames behandeld worden per seconde aangezien het ophalen van de camerabeelden m.b.v. OpenCV zorgt voor vertraging.
3.14
Interface met andere modules
Module voor opbouw van de merktekens: Ingave: Initieel werd het pad van het configuratiebestand doorgegeven. Dit moet ook worden gewijzigd bij gebruik van een ander soort merktekens. Tijdens de eigenlijke uitvoering dient dan ook enkel het gedetecteerde interne bitpatroon doorgegeven te worden. Teruggave: Het ID van het merkteken of een ongeldige waarde indien het bitpatroon ongeldig was. Een aanduiding van de correcte rotatie.
Module voor positiebepaling: Ingave: De ID’s van de geldige merktekens aanwezig in het frame. De hoeken van de geldige merktekens in de juiste volgorde (deze die hoort bij de geldige rotatie).
3.15
Configuratie
De klasse MarkerExtractionConfig houdt de configuratie voor de merktekenextractie bij. Deze wordt opgeslagen in een XML-bestand waarvan de layout hieronder wordt weergegeven. Parsen van het XML-bestand kan in C++ via xerces-c (The Apache Software Foundation, 2005). <MarkerTracking> <M a r k e r E x t r a c t i o n> 0 . 5
89
Hoofdstuk 3. Extractie en identificatie merktekens 1 . 4 9 <sigmaMin>2 <sigmaMax>5 160 1 . 5 0 . 0 0 0 1 <widthNeighb>2 <Segmentation> 2
De parameters werden ongeveer opgesplitst per fase: Voor de LoG-randdetectie (sectie 3.5.2) kan de threshold (thresh), de σ voor de Gausscomponent (kernelSigma) en de breedte (kernelSize) van de LoG-kernel worden opgegeven. Voor de hoekdetectie (sectie 3.7) kan de minimum- en maximumwaarde (sigmaMin en sigmaMax ) worden opgegeven die gebruikt worden voor de σ om de kromming te bepalen. Verder kan threshangle in formule 3.15 (threshAngle) en C (threshRoS ) in formule 3.14 worden opgegeven. Tenslotte kan de minimumwaarde (gaussDerivLim) worden ingesteld voor de co¨effici¨enten van de maskers die nodig zijn voor het bepalen van de kromming. Waarden die onder deze limiet liggen worden verworpen, zodat de breedte van deze maskers beperkt wordt. Ook kan bepaald worden of het linken van contouren moet worden uitgevoerd (parameter execute bij LinkContours) en kan de breedte van de maskers in figuur 3.38 worden ingesteld. Bij het bepalen van de segmenten kan de threshold voor de kromming aan de uiteinden van deze segmenten worden ingesteld. a.d.h.v. de noemer in vergelijking 3.18 (threshCurvature).
90
Hoofdstuk 3. Extractie en identificatie merktekens Voor TryConvexHull en DropExcessSegmentsLine kan worden ingesteld of de overeenkomstige technieken (sectie 3.12.6) moeten worden uitgevoerd (parameter execute)
Er worden sowieso default parameters voorzien voor elk van deze instellingen, dit zijn de waarden die in het voorbeeld hieronder werden ingevuld. De gebruiker hoeft dan ook enkel een tag te voorzien voor de parameters die hij wil wijzigen.
3.16
GUI
Figuur 3.54: GUI merktekenextractie
Via het tweede item uit het menu uit figuur 2.9 kan de GUI voor de merktekenextractie gestart worden (figuur 3.54). Eerst moet het het pad naar het configuratiebestand met de opbouw van de merktekens (sectie 2.4.1) en het bestand met de configuratie van de merktekenextractie (sectie 3.15) gespecifieerd worden. In principe kan dit hetzelfde bestand zijn, maar er werd bewust gekozen om hiervoor ook aparte bestanden toe te laten. De parameters voor de merktekenextractie zijn immers eerder specifiek voor een camera. Dezelfde camera wordt gebruikt voor meerdere soorten merktekens en dezelfde merktekens worden gebruikt in combinatie met meerdere camera’s. Vervolgens kan ervoor gekozen worden om bepaalde zaken aan te duiden op de camerabeelden: de LoG-punten (rood), minima (navy-blauw) en maxima (olijfgroen) van de kromming, hoeken (paars), de eindpunten van de segmenten (heldergroen), de buitenrand van het merkteken (lijnstukken tussen de hoeken, geel), het ID (geel) en de sampling punten van het bitpatroon 91
Hoofdstuk 3. Extractie en identificatie merktekens (blauw). Op deze manier kan men elk van de fasen van de merktekenextractie aan het werk zien. Bovendien kan de configuratie voor de merktekenextractie op deze manier bijgewerkt worden. Door de LoG-punten vb. weer te geven kan je een gepaste threshold kiezen voor de randdetectie. Dit gebeurt door het weergeven van een venster met de oorspronkelijke camerabeelden en een venster met de beelden na aanduiden van de gewenste kenmerken. Vastleggen en weergeven van de camerabeelden gebeurt m.b.v. OpenCV-functies. Een voorbeeld van een venster met de kenmerken zoals aangeduid in figuur 3.54 wordt weergegeven in figuur 3.55. Door op de enter-toets te drukken wordt dit scherm opnieuw gesloten indien het geactiveerd is.
Figuur 3.55: Weergeven camerabeelden met kenmerken aangeduid in figuur 3.54.
Soms kan er een foutbericht verschijnen vanuit OpenCV omdat de camera niet kon gevonden worden. Verwijderen van de camera (uit de USB-poort) en opnieuw insteken (eventueel in een andere USB-poort) lost dit probleem doorgaans op.
92
Hoofdstuk 4
Positiebepaling Nu we de merktekens uit het beeld hebben ge¨extraheerd, kunnen we overgaan naar de positiebepaling. Hierbij wordt gebruik gemaakt van de relatie tussen de gekende posities van de merktekens in de kamer en de positie van de merktekens in het beeldvlak. Eerst wordt dan ook de wiskundige relatie tussen de 3D wereld en het 2D beelvlak van de camera besproken (sectie 4.1) en de bijhorende calibratie van de camera (sectie 4.2). Vervolgens wordt het algoritme voor de eigenlijke positiebepaling bekeken (sectie 4.3). Ten slotte wordt de integratie van de positiebepaling in onze toepassing besproken (vanaf 4.4).
4.1
Pinhole camera model
Figuur 4.2: Perspectieve projectie
Figuur 4.1: Geometrie van het pinhole camera model.
93
Hoofdstuk 4. Positiebepaling We beperken ons hier tot het pinhole camera model” (figuur 4.1), wat bruikbaar is voor ” de meeste camera’s, zeker voor de camera’s die bij deze thesis gebruikt werden. In essentie wordt het beeld hierbij gevormd via een perspectieve projectie, zoals weergegeven in figuur 4.2.
h Via gelijkvormigheid van driehoeken is duidelijk dat een 3D punt M = X Y h iT afgebeeld op het punt f X/Z f Y /Z met f de brandpuntsafstand.
Z
iT
wordt
Figuur 4.3: Co¨ ordinaten beeldvlak (x, y) en camera-co¨ordinaten stelsel (xcam , ycam ).
Hierbij werd verondersteld dat de oorsprong van de co¨ordinaten in het beeldvlak samenvalt met p. p is het snijpunt van de hoofdas (komt overeen met de kijkrichting van de camera) en het beeldvlak. In praktijk is dit niet altijd het geval, zodat M eigenlijk wordt afgebeeld h iT op f X/Z + px f Y /Z + py . (px , py ) bevinden zich vaak ongeveer in het midden van het beeldvlak. Voor perspectieve projectie geldt dan algemeen het verband (in homogene co¨ordinaten) X X f X + Zpx f 0 px 0 Y Y → f Y + Zpy = 0 f py 0 Z Z Z 0 0 1 0 1 1
(4.1)
h i ˜ met M ˜ en m Algemeen kan dit geschreven worden als m ˜ = K I | 0 M ˜ de homogene co¨ordinaten van het 3D-punt M en de 2D-projectie op het beeldvlak m. De co¨ordinaten van M worden hier uitgedrukt t.o.v. het camera-co¨ordinaten stelsel (figuur 4.1). De camera bevindt zich bij de oorsprong van dit co¨ordinatenstelsel en wijst in de richting van de hoofdas, die langs de z-as ligt. K is de camera calibratie matrix en bevat de interne parameters van de camera. Er werd verondersteld dat de schaal in x- en y-richting in het beeldvlak gelijk is. Bij sommige camera’s (vb. CCD camera’s) is dit niet het geval. We moeten dan ook een onderscheid
94
Hoofdstuk 4. Positiebepaling maken tussen fx = αx ∗ f en fy = αy ∗ f met αx en αy schaalfactoren in respectievelijk x- en y-richting. K wordt dan uiteindelijk fx 0 px K = 0 fy py 0 0 1
(4.2)
Figuur 4.4: Translatie en rotatie tussen camera- en wereld-co¨ordinatenstelsel.
Meestal worden punten in een ruimte uitgedrukt in een ander co¨ordinatenstelsel dan het camera-co¨ordinatenstelsel: het wereld-co¨ordinatenstelsel. Deze twee co¨ordinatenstelsels kunnen uitgedrukt worden t.o.v. van elkaar via een translatie t en een rotatie R (figuur 4.4). R en t stellen de externe parameters voor. Algemeen bekomen we dan de relatie ˜ sm ˜ = PM
h i met P = K R | t
en s een schaalfactor
(4.3)
s is oorspronkelijk gelijk aan 1, maar wanneer de grootte van een camerabeeld vergroot/verkleind wordt met een bepaalde factor, moeten de interne parameters vermenigvuldigd/gedeeld worden met dezelfde factor. Er zijn in totaal 10 vrijheidsgraden. Vier vrijheidsgraden voor K (fx , fy , px en py ), drie vrijheidsgraden voor t (tx , ty , tz ) en drie vrijheidsgraden voor R (αx , αy en αz : de rotatie rond de x-as, y-as en z-as). K kan echter op voorhand bepaalt worden tijdens een calibratiefase, nadien wijzigen deze parameters niet meer. Voorwaarde daarbij is dan wel dat f voor de camera gelijk blijft. Bij camera’s met een zoomlens dient men dan ook een andere calibratie te gebruiken bij instellen van een andere zoomfactor. Er werd dan ook de mogelijkheid voorzien om een camera te calibreren, zie sectie 4.2. De eigenlijke positiebepaling bestaat dus uit het vinden van de overige 6 vrijheidsgraden in 95
Hoofdstuk 4. Positiebepaling R en t. Dit wordt verder beschreven in sectie 4.3.
Figuur 4.5: Distorsie, links: oorspronkelijk beeld, projecties van rechte lijnen zijn gebogen. Rechts: beeld na correctie distorsie, projecties van rechte lijnen zijn nu recht.
Louter perspectieve projectie is vaak onvoldoende om de beeldvorming te beschrijven, aangezien de cameralens ook kan zorgen voor distorsie van het beeld (figuur 4.5). Gelukkig kan dit gemodelleerd worden als een 2D vervorming van het beeld, a.d.h.v. een aantal parameters. h iT b = u Stel dat u de waargenomen 2D-co¨ordinaten zijn van de punten in het beeldb vb h iT b = x vlak, met distorsie en x b yb de overeenkomstige genormaliseerde co¨ordinaten zodat h iT u b = px + fx x b en vb = py + fy yb (niet-homogene co¨ordinaten). Stel dat u = u v en h iT x= x y de overeenkomstige co¨ordinaten zijn zonder distorsie. De distorsie wordt dan b = x + dxradial + dxtangential , met uitgedrukt i.f.v. twee componenten zodat x dxradial = (1 + k1 r2 + k2 r4 + ...)x " # 2p1 xy + p2 (r2 + 2x2 ) dxtangential = p1 (r2 + 2y 2 ) + 2p2 xy p r = x2 + y 2
(4.4) (4.5) (4.6)
dxtangential heeft hierbij minder invloed dan dxradial . Parameters k1 , k2 , p1 en p2 worden dan ook bij de calibratie bepaald (sectie 4.2).
96
Hoofdstuk 4. Positiebepaling
4.2
Calibratie camera
Figuur 4.6: Schaakbordpatroon gebruikt voor calibratie.
Voor de calibratie werd eerst een Matlab-toolbox gebruikt (Bouguet, 2007). Deze werkt met een schaakbordpatroon, zoals weergegeven in figuur 4.6. De binnenste hoeken van de vakjes van het patroon worden gebruikt als referentiepunten. Voor de eigenlijke calibratie moeten dan eerst een aantal afbeeldingen (20 `a 25) worden gemaakt met de camera van dit patroon. Enkele tips voor het vastleggen van de beelden worden gegeven in (Graphics & Media lab, 2006). Gebruik van deze toolbox vereist wel wat manueel werk, een benadering van de hoeken moet vb. manueel aangeduid worden. Aangezien echter ook OpenCV - functies (Intel, 2007) bestaan die hetzelfde algoritme toepassen en zelf de hoeken van het patroon opsporen, werd hiermee ook de mogelijkheid tot calibratie voorzien in dit project. Opsporen van de hoeken van het patroon kan via de OpenCV-functie cvFindChessboardCorners. Deze geeft de gevonden hoeken in het beeldvlak terug, rij per rij. Deze functie geeft een waarde 0 terug indien niet alle hoeken gevonden werden. De overeenkomsten tussen de co¨ordinaten van de hoekpunten op het oorspronkelijke patroon (object points) en de gevonden projecties op het beeldvlak bekomen via voorgaande functie (image points), voor de verschillende beelden, dienen dan als input voor de functie cvCalibrateCamera2. Het calibratie-algoritme verloopt hierbij als volgt: Bepalen van een homografie (zie sectie 3.1.2) voor alle punten van alle afbeeldingen, dit stelt dan een perspectieve projectie voor tussen het vlak van het calibratiepatroon en het beeldvlak. Initialisatie van de interne parameters, distorsieparameters worden ge¨ınitialiseerd op 0, px en py worden ge¨ınitialiseerd op het centrum van het beeld. Bepalen van de externe parameters voor elke afbeelding.
97
Hoofdstuk 4. Positiebepaling Optimalisatie van de interne parameters door minimalisatie van de fout tussen de gevonden co¨ordinaten van de hoekpunten van het patroon in het beeldvlak en de overeenkomstige terugprojecties, gebruik makende van de voorlopige waarden voor de interne parameters. Aangezien de externe parameters berekend werden, kan men immers via formule 4.3 de terugprojecties bepalen van de object points. Dergelijke terugprojecties zullen we later nog gebruiken.
Men kan echter ook zelf een initialisatie opgeven voor de interne parameters. Dit vormde de basis voor de klasse CalibrationCamera. Via de functie createChessboardCalib kan een schaakbordpatroon gegenereerd worden a.d.h.v. de parameters meegegeven met de constructor. Met de functie captureImages kan men de benodigde afbeeldingen afkomstig van de camera genereren en opslaan. Er verschijnt hiertoe een venstertje met de camarabeelden. Door te drukken op te spatie-toets wordt een afbeelding bewaard. Eerst wordt echter eens de functie cvFindChessboardCorners toegepast om te controleren of alle hoeken van het patroon op deze afbeelding kunnen gevonden worden, pas dan wordt de afbeelding effectief aanvaard.
Figuur 4.7: Calibratie, links: hoeken calibratiepatroon nodig voor calibratie opgespoord, midden: terugprojectie hoeken via parameters calibratie zonder rekening te houden met distorsie parameters, rechts: idem, maar nu werden de distorsie parameters wel gebruikt.
Voor de eigenlijke calibratie kan dan de functie calibrate gebruikt worden. Hierbij worden de calibratieparameters eerst bepaald m.b.v. de helft van alle afbeeldingen. Vervolgens worden de parameters opnieuw bepaald, maar nu via initialisatie met de parameters van de vorige berekening en met een afbeelding meer. Dit gebeurt tot alle afbeeldingen werden gebruikt. Deze aanpak blijkt goede resultaten te geven. Men kan ook afbeeldingen genereren en opslaan die de gevonden hoeken van het schaakbordpatroon (parameter showChessBoardCorners) en de terugprojecties van deze hoeken met en zonder gebruik van de distorsieparameters (parameter showBackprojection) weergeven (zie figuur 4.7). Dit geeft een idee van de nauwkeurigheid van de calibratie. class CalibrationCamera { public :
98
Hoofdstuk 4. Positiebepaling // C o n s t r u c t o r , p a t h D i r b e p a a l t de map waarin a l l e // c a l i b r a t i e b e s t a n d e n worden g e p l a a t s t . numSquaresWidth en // numSquaresHeight b e p a l e n de hoeken van h e t s c h a a k b o r d , // w i d t h S q u a r e b e p a a l t de b r e e d t e van een v i e r k a n t j e op h e t p a t r o o n . // numImg b e p a a l t h o e v e e l f i g u r e n g e b r u i k t z u l l e n worden v oor de // c a l i b r a t i e . C a l i b r a t i o n C a m e r a ( s t r i n g p a t h D i r , int numImg , int numSquaresWidth , int numSquaresHeight , int w i d t h S q u a r e ) ; //Aanmaken van f i g u r e n voor c a l i b r a t i e met een volgnummer void c a p t u r e I m a g e s ( ) const ; //Aanmaken s c h a a k b o r d p a t r o o n n o d i g v oor c a l i b r a t i e void c r e a t e C h e s s b o a r d C a l i b ( ) const ; //Aanmaken van h e t c o n f i g u r a t i e b e s t a n d na u i t v o e r e n van de c a l i b r a t i e void w r i t e C o n f i g F i l e ( ) const ; // e i g e n l i j k e c a l i b r a t i e van de camera void c a l i b r a t e ( bool showBackProjection , bool showChessBoardCorners ) ; private : // A f b e e l d i n g g e s c h i k t voor c a l i b r a t i e ? bool f r a m e O k C a l i b r a t i o n ( I p l I m a g e * img ) const ; // Bepalen van de ” o b j e c t p o i n t s ” CvMat * g e t M a t r O b j e c t P o i n t s ( int numImgs ) const ; // Bepalen van de ” image p o i n t s ” van a f b e e l d i n g e n met nummers // numFirstImg t o t numLastImg CvMat * g e t I m a g e P o i n t s ( int numFirstImg , int numLastImg , bool showChessBoardCorners ) const ; // tonen van de t e r u g p r o j e c t i e s van de hoeken van h e t p a t r o o n // voor a f b e e l d i n g e n met nummer numFirstImg t o t numLastImg void s h o w B a c k P r o j e c t i o n ( int numFirstImg , int numLastImg ) const ; };
4.2.1
Configuratie
Via de functie writeConfigFile van de klasse CalibrationCamera kan nu een configuratiebestand gegenereerd worden met de berekende parameters. Dit kan dan gebruikt worden bij de eigenlijke positiebepaling. 99
Hoofdstuk 4. Positiebepaling <MarkerTracking> <x>3 9 5 . 1 7 3 9 2 . 1 5 1 <x>1 7 6 . 0 6 3 3 6 . 4 0 9 8 −0.419405 0 . 0 7 8 1 9 2 7 0 . 0 1 4 9 3 2 5 −0.000627283 288 <width>352
4.2.2
GUI
Figuur 4.8: GUI calibratie.
Via het derde item in het menu van figuur 2.9 kan de GUI voor de calibratie gestart worden 100
Hoofdstuk 4. Positiebepaling (figuur 4.8). Alle bestanden die gegenereerd en gebruikt worden komen terecht in de opgegeven directory. De parameter Width square moet de breedte zijn in mm van een vakje van het afgedrukte patroon. Verder spreekt het gebruik voor zich.
4.3
Principe positiebepaling
Positiebepaling of beter bekend als pose estimation is een bekend probleem binnen computer visie. Hierbij zijn minstens 4 overeenkomsten tussen 3D-punten en punten in het beeldvlak vereist. Bij dit onderdeel van het project moesten dan ook eerst bestaande methodes gezocht en vergeleken worden. (Lepetit & Fua, 2005) geeft een overzicht van een aantal klassieke methodes. Een van de methodes bleek ge¨ımplementeerd in OpenCV a.d.h.v. de functie cvFindExtrinsicCameraParams2. (Een andere algoritme, het POSIT -algoritme, is ook in OpenCV ge¨ımplementeerd, maar deze methode werkt enkel voor niet-coplanaire 3D-referentiepunten.) Bij deze methode wordt de matrix P in vergelijking 4.3 bekomen a.d.h.v. een stelsel lineair onafhankelijke vergelijkingen. Elke overeenkomst tussen een 3D-punt Mi en de overeenkomstige projectie mi geeft immers 2 vergelijkingen: P11 Xi + P12 Yi + P13 Zi + P14 = ui P31 Xi + P32 Yi + P33 Zi + P34 P21 Xi + P22 Yi + P23 Zi + P24 = vi P31 Xi + P32 Yi + P33 Zi + P34
(4.7) (4.8)
Via de gekende matrix met de interne parameters K wordt [R|t] dan gegeven via K −1 P . Dit noemt men de DLT -methode (Direct Linear Transformation). Wanneer de 3D-referentiepunten coplanair zijn, stelt de bekomen P een homografie H voor. Veronderstel dat de 3D-punten gelegen zijn in het Z = 0 vlak, dan is
f m e = HM
(4.9)
h = K R1 R2
h = K R1 R2
X i Y 3 R t 0 1 i X t Y 1
(4.10)
(4.11)
Enkel de eerste en tweede kolom van R en t zijn nu dus gekend. De derde kolom van R kan echter bekomen worden via R1 ×R2 aangezien de kolommen van R orthonormaal moeten zijn. 101
Hoofdstuk 4. Positiebepaling Op deze manier wordt echter enkel een algebra¨ısche fout geminimaliseerd (bij het coplanaire geval wordt wel al een geometrische eigenschap gebruikt bij het vinden van R3 ). Beter is om een geometrische fout te beschouwen. Dit gebeurt door minimalisatie van X
fi , mi ) dist2 (P M
(4.12)
i
Dit is dus weer minimalistie van de fout op de terugprojecties. Deze methode blijkt echter niet steeds te convergeren, laat staan naar de juiste positie (Lee, 2006). Ook de nauwkeurigheid blijkt beter te kunnen. Een betere methode werd gevonden in de paper (Lu et al., 2000). Deze methode is globaal convergent en heeft hiervoor slechts 5 `a 10 iteraties nodig, zelfs bij een slechte initialisatie. In de paper wordt de methode vergeleken met de Levenberg-Marquardt methode, een van de meest betrouwbare methodes. De volledige afleiding wordt in deze paper beschreven, samen met een bewijs voor de globale convergentie. We vatten hier de belangrijkste elementen van de methode samen.
Figuur 4.9: Minimalisatie object-space error
Vele methodes werken met de zogenaamde image space error (fout tussen terugprojecties). Bij deze methode wordt echter gewerkt met de object space error (figuur 4.9). Wanneer pi een 102
Hoofdstuk 4. Positiebepaling 3D-referentiepunt is, is qi = Rpi +t het overeenkomstige punt in het camera-co¨ordinatenstelsel. qi , de projectie op het beeldvlak van dit punt en de oorsprong moeten collineair zijn. De object space error wordt dan gevonden door projectie van qi op de rechte bepaald door de oorsprong en vi , het gemeten overeenkomstige 2D-punt op het beeldvlak. De qi ’s zijn echter niet gekend, maar de foutenfunctie kan zodanig herscheven worden dat deze kan uitgedrukt worden i.f.v. R. De methode vereist een eerste initialisatie voor R en kan iteratief een betere benadering voor R vinden. Voor elke waarde van R kan men een waarde bepalen voor qi . Via het zogenaamde absolute orientation problem dat de fout minimaliseert tussen de koppels 3D-punten qi en pi en gebruik maakt van het feit dat Rt R = I kan een betere benadering voor R gevonden worden tot de object space error uiteindelijk convergeert naar een minimum en we de uiteindelijke waarde voor R vinden. t kan dan i.f.v. R gevonden worden. Voor de initialisatie van de methode kan in principe elke waarde voor R gebruikt worden aangezien het algoritme globaal convergent is, maar in praktijk wil men beginnen van een redelijke benadering. Bij deze methode wordt een benadering voorgesteld op basis van het weak perspective camera model. Hierbij veronderstelt men dat de 3D-referentiepunten niet ver verwijderd liggen van de optische as en de z-co¨ordinaat (langs de optische as) voor elk van deze punten gelijk kan gesteld worden aan s. Door de formules voor minimalisatie van de fout op de terugprojectie en minimalisatie van de fout tussen de werkelijke z en s te combineren, wordt een eerste benadering gevonden. Toch blijkt deze methode niet steeds te convergeren naar de juiste oplossing. (Schweighofer & Pinz, 2006) (RPP ) werkt met coplanaire punten en toont aan dat bij positiebepaling doorgaans twee lokale minima voorkomen, waardoor er zogenaamde pose jumps optreden. Voor niet-coplanaire punten kan dit dus niet gebruikt worden. Hier wordt een methode voorgesteld die op zoek gaat naar deze twee lokale minima en het minimum behoudt dat resulteert in de kleinste fout. In deze paper wordt ook gewerkt in combinatie met voorgaande methode voor positiebepaling. Er werd verwezen naar een eigen Matlab-implementatie en een C++ - implementatie in ARToolkitPlus (Wagner, 2007) (Dit systeem werkt met dezelfde principes als ARToolkit, maar voorziet een verbeterde API en enkele optimalisaties, o.a. deze verbeterde methode voor positiebepaling, een automatische threshold-waarde en eveneens het gebruik van vaste merktekens met bitlogica. De eigenlijke merktekenextractie van ARToolkit werd verder niet verbeterd.) Na veel zoekwerk hebben we deze methode in het eigen project aan de praat gekregen. Toch bleek zeker niet altijd de juiste positie teruggegeven te worden. De reden vonden we terug in (Schweighofer & Pinz, 2006). In combinatie met de methode uit (Lu et al., 2000) wordt slechts in ongeveer 60% van de gevallen effectief de juiste positie gekozen. Daarom hebben we de methode zelf aangepast. Aangezien de bepaalde positie bij twee opeenvolgende frames 103
Hoofdstuk 4. Positiebepaling doorgaans niet veel verschilt, wordt de positie gekozen die het dichtst ligt bij de voorgaand bepaalde positie. Dit levert doorgaans veel betere resultaten. Later hebben we nog een andere benadering voorzien. Naast de translatie zal namelijk ook de rotatiematrix bij twee opeenvolgende frames weinig verschillen. Bijgevolg kan de rotatiematrix uit een vorig frame gebruikt worden als initialisatie van de positiebepaling door (Lu et al., 2000) voor het volgende frame. Als laatste optimalisatie wordt ook telkens de maximum fout op de terugprojectie bepaald. Als deze een bepaalde threshold overschrijdt, wordt de nieuw bepaalde positie niet aanvaard en wordt de positie bepaald bij het vorige frame behouden. Op deze manier worden de pose jumps zoveel mogelijk vermeden. We hebben nu enkel een initialisatie van de positie nodig voor het 1e frame. Dit kan via de methode op basis van het weak perspective model, maar als tweede mogelijkheid hebben we het gebruik van de functie cvFindExtrinsicCameraParams2 voorzien. Een 3D-punt Mw in het wereld-co¨ordinatenstelsel kan nu via de vector Mc = RMw + t worden uitgedrukt in het camera-co¨ordinatenstelsel. We willen echter de relatie van het camera- t.o.v. het wereld-co¨ordinatenstelsel. Het camera center C kan gevonden worden t.o.v. het wereldco¨ordinatenstelsel via de relatie 0 = RC + t, waaruit volgt dat C = −R−1 t = −RT t. De rotatie van het camera-co¨ordinatenstelsel t.o.v. het wereld-co¨ordinatenstelsel is R−1 = RT . Deze uiteindelijke positie kan bekomen worden via de functie getInvertedPose. Voor deze twee methodes werden 2 klassen voorzien: DLTPoseEstimator en RppPoseEstimator. De DLTPoseEstimator gebruikt de functie cvFindExtrinsicCameraParams2. In de broncode van deze functie werd wel een fout verbeterd. De RppPoseEstimator gebruikt de code voor (Schweighofer & Pinz, 2006) en (Lu et al., 2000). Hierbij kan ingesteld worden of de berekening van de tweede positie bij coplanaire 3D-referentiepunten gewenst is. De klasse PoseEstimator is de bovenklasse van beide. De belangrijkste functies worden hieronder weergegeven. class PoseEstimator { public : P o s e E s t i m a t o r ( P o s e E s t i m a t i o n C o n f i g&
config );
//De t e r u g p r o j e c t i e van de ho ekp un te n wordt w e e r g e g e v e n op ”img” // i n d i e n een nieuwe g e l d i g e p o s i t i e kon b e p a a l d worden . //De r e t u r n −waarde b e p a a l t o f een nieuwe g e l d i g e p o s i t i e werd b e p a a l d . v i r t u a l bool e s t i m a t e P o s e ( I p l I m a g e * img , v e c t o r <ExtractedMarker>& e x t r a c t e d M a r k e r s ) = 0 ;
104
Hoofdstuk 4. Positiebepaling // Teruggevevn van r e l a t i e van camera−c o ¨ ordinatenstelsel t .o. v . // w e r e l d −c o ¨ ordinatenstelsel . // Keuze t u s s e n r o t a t i e m a t r i x en r o t a t i e v e c t o r v i a ” rotVec ” // ( Een r o t a t i e v e c t o r i s een v e c t o r d i e de r o t a t i e a s v o o r s t e l t , // g r o o t t e van de v e c t o r i s de r o t a t i e h o e k rond d e z e as ) void g e t I n v e r t e d P o s e ( const double ( * & r o t I n v ) [ 3 ] , const double *& t r a n s l I n v , bool rotVec ) ; protected : // Co¨ o rdinaten van een punt c o r r i g e r e n v oor d i s t o r s i e void c o r r e c t D i s t o r t i o n ( CvPoint2D64f& pt ) const ; // Co¨ o rdinaten van een punt aanpassen om d i s t o r s i e t o e t e voegen void a d d D i s t o r t i o n ( CvPoint2D64f& pt ) const ; // b e p a l e n van de i n d i c e s van de m e r k t e k e n s i n ” e x t r a c t e d M a r k e r s ” // d i e kunnen g e b r u i k t worden om de p o s i t i e t e b e p a l e n void g e t I n d i c e s M a r k e r s O k ( v e c t o r & iMarkersOk , const v e c t o r <ExtractedMarker>& e x t r a c t e d M a r k e r s ) const ; // Bepalen van de c o ¨ o r d i n a t e n van de h oe kp unt en van een merkteken // r e l a t i e f t . o . v . h e t c o ¨ o r d i n a t e n s t e l s e l van ´e´e n van de v l a k k e n . // Als h e t merkteken n i e t i n d i t v l a k l i g t , worden de c o ¨ ordinaten // van de hoekpunten g e t r a n s f o r m e e r d naar d i t v l a k . bool getCoordMarkerPlane ( int ID , int i P l a n e , CvPoint3D64f& r e s , int i C o r n e r ) const ; // w e r e l d −c o ¨ o r d i n a t e n s t e l s e l t . o . v . camera−c o ¨ ordinatenstelsel // k e u z e t u s s e n r o t a t i e m a t r i x en r o t a t i e v e c t o r v i a ” rotVec ” void g e t P o s e ( const double ( * & r o t ) [ 3 ] , const double *& t r a n s l , bool rotVec ) ; ... };
4.4
Interface met andere modules
Van de module die zorgt voor de merktekenextractie krijgen we de hoeken en ID’s van de geldige merktekens. De hoeken worden doorgegeven in een specifieke volgorde: eerst de linkerbovenhoek, dan de linkerbenedenhoek, vervolgens de rechterbeneden- en rechterbovenhoek. Via de functie getIndicesMarkersOk houden we dan de merktekens over die gebruikt kunnen worden voor de positiebepaling. Bij merktekens die dubbel werden gedetecteerd, wordt enkel 105
Hoofdstuk 4. Positiebepaling het buitenste behouden (soms kan dit voorkomen wanneer er binnen de rand van het merkteken een contour wordt ontdekt). Anderzijds worden enkel de merktekens gebruikt die in de configuratie worden vermeld.
4.5
Plaatsing merktekens
De vraag rest nu hoe we de plaatsing van de merktekens best configureren. Met het oog op het genereren van de merktekenposities werd een kamer opgevat als een verzameling vlakken. De hoeken van deze vlakken worden gespecifieerd t.o.v. het eigenlijke wereld-co¨ordinatenstelsel. De posities van de merktekens worden dan gespecifieerd t.o.v. een co¨ordinatenstelsel dat hoort bij het vlak waarin ze liggen. Aan deze vlakken wordt een co¨ordinatenstelsel gehecht dat ligt in de linkerbovenhoek. x wijst hierbij naar rechts, y naar boven en z naar voor. Door nu op voorhand de rotatie en translatie tussen de vlakken en het hoofd-wereldco¨ordinatenstelsel te bepalen, samen met de inverse translatie en rotatie, kunnen we de posities van de merktekens bekomen relatief t.o.v. dit wereldco¨ordinatenstelsel of t.o.v. andere vlakken. De positiebepaling gebeurt relatief t.o.v. het co¨ordinatenstelsel van een vlak. (De RPP -methode blijkt enkel te werken bij referentiepunten in het z = 0 vlak, zodat dit ook een noodzaak is). Wanneer er merktekens in meerdere vlakken worden herkend, wordt er ´e´en vlak gekozen en worden de co¨ordinaten van de hoekpunten van de andere merktekens uitgedrukt t.o.v. het co¨ordinatenstelsel van dit vlak. Dit kan via de functie getCoordMarkerPlane uit de klasse PoseEstimator. Nu kunnen we de eigenlijke posities en grootte van de merktekens bepalen. Hiertoe zijn per vlak een aantal gegevens nodig. Enerzijds hebben we de minimum- en maximumafstand (in mm) nodig van de camera t.o.v. een vlak. De maximumafstand zal immers bepalen hoe groot onze merktekens moeten zijn, terwijl de minimumafstand bepaalt hoe dicht we de merktekens moeten plaatsen om telkens minimaal het gewenste aantal merktekens in beeld te hebben. Tenslotte moet de benodigde breedte (in pixels) in het beeldvlak worden gespecifieerd van een bitveldje van een merkteken zodat dit merkteken wordt herkend. Op deze manier kan bij het bepalen van de merktekenposities rekening gehouden worden met het aantal eenheden per zijde van een merkteken. Bepalen van de benodigde grootte van de merktekens gebeurt dan als volgt: We hebben de afstand nodig die overeenkomt met de breedte (hof , horizontal field of view) en hoogte (vof , vertical field of view) van een camerabeeld bij de maximumafstand (maxdist ) en de minimumafstand (mindist ) tussen camera en vlak. Aangezien we fx en fy in pixeleenheden kennen, kan dit als volgt bepaald worden:
106
Hoofdstuk 4. Positiebepaling
a ∗ af standcamera−>vlak fx b vof = ∗ af standcamera−>vlak fy
hof =
(4.13) (4.14)
met a × b de resolutie van de camera. De benodigde breedte van een merkteken kan dan in mm als volgt bekomen worden: aantalu ∗ breedteu ∗ hofmindist a met u een eenheid van de zijde van een merkteken.
breedtemerkteken =
(4.15)
De merktekens worden geplaatst op een horizontale afstand maxHS en een verticale afstand maxV S van elkaar. Deze afstanden worden bepaald door de minimumafstand mindist tussen camera en vlak en het gewenste aantal merktekens in horizontale (aantalM erktekenshoriz ) en verticale (aantalM erktekensvert ) richting. hofmindist − (aantalM erktekenshoriz + 1) ∗ breedtemerkteken aantalM erktekenshoriz vofmindist − (aantalM erktekensvert + 1) ∗ breedtemerkteken maxV S = aantalM erktekensvert
maxHS =
(4.16) (4.17)
Dit wordt gerealiseerd via de klasse PoseEstimationConfig. Deze klasse leest de configuratieparameters in die nodig zijn voor de positiebepaling. Nadat deze werden ingelezen worden de benodigde transformatiematrices tussen de vlakken bepaald (functie generateTransformationsPlanes). Het genereren van de merktekenposities kan via de procedure generateMarkerPositions. Wegschrijven van deze merktekenposities kan via de procedure writeMarkerPositions. De structuur van het gegenereerde bestand wordt beschreven in 4.5.1. class PoseEstimationConfig { private : // Genereren van de t r a n s f o r m a t i e m a t r i c e s van de c o ¨ ordinatenstelsels // van de v l a k k e n naar h e t w e r e l d −c o ¨ o r d i n a t e n s t e l s e l en omgekeerd . void g e n e r a t e T r a n s f o r m a t i o n s P l a n e s ( ) ; // W i j z i g e n van de c a l i b r a t i e −p a r a m e t e r s i . f . v . de h u i d i g e r e s o l u t i e void changeFrameSize ( CvSize newFrameSize ) ; public : // C o n f i g u r a t i e wordt i n g e l e z e n v a n u i t h e t b e s t a n d met pad ” p a t h ”
107
Hoofdstuk 4. Positiebepaling // C a l i b r a t i e p a r a m e t e r s worden a u t o m a t i s c h a a n g e p a s t aan de h u i d i g e // r e s o l u t i e van de camera . P o s e E s t i m a t i o n C o n f i g ( s t r i n g path , CvSize curFrameSize = c v S i z e ( 0 , 0 ) ) ; // Genereren van de p o s i t i e s en g r o o t t e van de b e n o d i g d e m e r k t e k e n s // C o n f i g u r a t i e van de kamer moet b e s c h i k b a a r z i j n i n h e t b e s t a n d // d a t werd o p g e g e v e n i n de c o n s t r u c t o r . void g e n e r a t e M a r k e r P o s i t i o n s ( int numUnitsMarkers ) ; // W e g s c h r i j v e n van de c o n f i g u r a t i e van de m e r k t e k e n s . void w r i t e M a r k e r P o s i t i o n s ( s t r i n g path ) ; ... };
4.5.1
Configuratie
De vlakken (element Plane) van de kamer worden beschreven binnen het element Room. Voor elk vlak wordt een attribuut ID gespecifieerd zodat via dit ID voor de merktekens kan worden aangegeven in welk vlak ze liggen. Voor elk vlak moeten de co¨ordinaten van de linkerbovenhoek (TL), linkerbenedenhoek (BL) en rechterbovenhoek (TR) worden opgegeven t.o.v. het wereldco¨ordinatenstelsel, samen met de minimum- en maximumafstand tussen camera en vlak (MinDistance en MaxDistance). De volgende parameters stellen dan respectievelijk het aantal merktekens voor dat steeds aanwezig moet zijn in horizontale en verticale richting en de minimum breedte van een eenheid van een merkteken. De gegevens binnen het element MarkerPositions kunnen nu ofwel manueel worden gespecifieerd, ofwel automatisch via de functie generateMarkerPositions. Bij automatische generatie worden de ID’s voor de merktekens nog niet ingevuld. De gebruiker bepaalt immers zelf welk merkteken waar wordt opgehangen, het attribuut Plane bepaalt het vlak waarvoor het merkteken bestemd is en wordt wel ingevuld. Voor elk merkteken worden nu via de Corner -elementen de hoeken in volgorde opgegeven (linksboven, linksonder, rechtsonder, rechtsboven). <MarkerTracking> <x>3296 −2276
108
Hoofdstuk 4. Positiebepaling 2136 <x>3296 −3017 2136 <x>3296 −2276 2616 <MinDistance>1500 <MaxDistance>3000 1 1 <minWidthUnitMarker>1 . 6 <M a r k e r P o s i t i o n s> <Marker ID=”5” Plane=” k a s t Z i j d e ”> <x>1421 −1609 <x>1421 −1709 <x>1521 −1709 <x>1521 −1609
109
Hoofdstuk 4. Positiebepaling
4.6
Nauwkeurigheid
Figuur 4.10: Resultaat test paper (Lu et al., 2000)
(Lu et al., 2000) toont het resultaat van een test waarbij een set van 3D-referentiepunten geselecteerd worden in een ruimte van [−5, 5] × [−5, 5] × [−5, 5]. Een random rotatie en een translatie werd gegenereerd en de referentiepunten werden via die translatie en rotatie getransformeerd. Op deze manier werd de configuratie zo random mogelijk. Bovendien werd ruis toegevoegd met een SN R = −20log(σ/0.3)dB = 50dB. Het doel was te testen in hoeverre de nauwkeurigheid werd verbeterd door het vergroten van het aantal referentiepunten. Figuur 4.10 toont het resultaat. De fout wordt weergegeven in log-schaal. De fout neemt inderdaad af bij een hoger aantal referentiepunten. In vergelijking met het Levenberg-Marquardt algoritme kan de fout over het algemeen vrij laag gehouden worden. Ook bij dit project werden een aantal testen uitgevoerd bij een aantal verschillende configuraties. Er werd getracht de metingen zo nauwkeurig mogelijk uit te voeren, maar toch moet een meetfout van 1 cm in rekening gebracht worden. De resultaten worden hier dan ook in cm weergegeven. Bij elke configuratie werden op verschillende posities 50 opeenvolgende waarden voor de camerapositie bepaald. Telkens werd het gemiddelde en de gemiddelde variantie van alle meetwaarden bepaald. De gebruikte merktekens hadden een breedte van 145 mm.
110
Hoofdstuk 4. Positiebepaling
Tabel 4.1: Test met 1 merkteken met DLT-algoritme
echte positie (cm)
gemiddelde positie (cm)
gemiddelde variantie (σ 2 ) (cm2 )
0 92 150
-16.9941 92.3975 146.4682
0.2842 2.0967 0.0278
0 92 200
-25.7954 102.9472 191.9524
187.0262 88.1685 1.4605
0 92 250
-31.7315 138.6532 235.4325
7.1222 23.7072 1.4368
0 92 300
23.4048 134.5435 284.8386
1645 63.0222 3.4250
Tabel 4.2: Test met 1 merkteken met globaal convergerend algoritme
echte positie (cm)
gemiddelde positie (cm)
gemiddelde variantie (σ 2 ) (cm2 )
0 92 100
-8.3770 90.2624 100.6588
0.2707 0.2126 0.3520
0 92 150
-16.6598 93.1245 147.2950
0.2248 4.9771 0.0302
0 92 200
-31.7146 111.1109 191.0128
2.2905 11.0009 1.0347
0 92 250
-36.7318 116.6241 234.4518
30.5190 128.0511 1.6524
0 92 300
-58.1119 113.0814 276.4247
24.4079 73.1679 2.2425
Tabel 4.3: Test met 1 merkteken met globaal convergerend algoritme en RPP-optimalisatie
echte positie (cm)
gemiddelde positie (cm)
gemiddelde variantie (σ 2 ) (cm2 )
0 92 100
-8.4196 90.0775 100.5753
0.0755 0.1054 0.0039
0 92 150
-16.4381 92.9519 147.4153
0.3837 3.4172 0.0463
0 92 200
-31.1913 110.4824 191.4485
1.4709 6.6409 0.7824
0 92 250
75.1669 109.6785 223.3785
2.8902 187.3424 2.5430
0 92 300
-63.4598 102.3037 279.9812
11.9307 206.8842 2.5596
Eerst werd een test met ´e´en merkteken uitgevoerd. Dit bevond zich op een hoogte van ongeveer 98,9 cm. De oorsprong van het wereld-co¨ordinatenstelsel bevond zich op het grondvlak en het vlak van het merkteken. De y-as liep naar boven door de linkerzijde van het merkteken, de x-as naar rechts en de z-as naar voor. Zowel voor het DLT-algoritme als het globaal convergerende algoritme, met en zonder de RPP-optimalisatie, werden er metingen uitgevoerd. De z-co¨ordinaat wordt over het algemeen vrij goed benaderd. Op een afstand van 3 m is er een fout rond de 20 cm wat vrij goed meevalt. De x- en y- co¨ordinaat zijn wel voor verbetering vatbaar. Wat hier echter het meeste opvalt is de variantie bij de DLT-methode, zeker bij de meting voor x op 3 m. Dit is ten gevolge van het feit dat de juiste oplossing niet steeds wordt benaderd, zoals we in sectie 4.3 hebben besproken. Het globaal convergerende algoritme blijkt 111
Hoofdstuk 4. Positiebepaling zowel met als zonder gebruik van de RPP -optimalisatie ongeveer even goed te werken, zonder RPP zijn de resultaten zelfs nog iets beter.
Figuur 4.12: Test met 2 merktekens in verschillend vlak
Figuur 4.11: Test met 3 merktekens in beeld
Tabel 4.4: Test met 3 merktekens met globaal convergerend algoritme en RPP-optimalisatie
echte positie (cm)
gemiddelde positie (cm)
gemiddelde variantie (σ 2 ) (cm2 )
24 92 150
21.3520 94.5298 140.6062
0.0570 0.0687 0.0009
24 92 200
17.6547 95.5963 189.1381
0.2139 2.0847 0.0017
24 92 250
17.8724 94.9848 236.6117
0.1744 0.1829 0.0012
24 92 300
4.5853 106.4751 281.0754
7.6442 25.0919 0.1447
Bij een tweede configuratie werd er met 3 merktekens getest, zie figuur 4.11. Er werd ook getest met 4 merktekens, maar dit bleek de prestaties niet te verbeteren. Opnieuw ligt de oorsprong van het co¨ordinatenstelsel op grondniveau, analoog als hiervoor, maar nu valt de y-as samen met de linkerzijde van de 2 linkse merktekens. De linkerbovenhoek van het linkse merkteken bevond zich op een hoogte van ongeveer 121 cm. De andere merktekens waren ongeveer 48 cm verwijderd van het merkteken linksboven. We zien dat de fout op de x- en y-co¨ordinaat wel degelijk veel kleiner is. Bovendien is de gemiddelde variantie zeer beperkt, de positie is nog stabieler. Hieruit blijkt dat het gebruik van meerdere merktekens wel degelijk een gunstig effect heeft op de bepaalde positie.
112
Hoofdstuk 4. Positiebepaling
Tabel 4.5: Test met 2 merktekens in verschillend vlak met globaal convergerend algoritme
echte positie (cm)
gemiddelde positie (cm)
gemiddelde variantie (σ 2 ) (cm2 )
100 97 100
97.3362 100.1233 97.9193
0.0918 0.0516 0.0777
200 97 200
190.5210 96.6619 196.2973
0.0865 0.6995 0.0693
Tot slot werd een configuratie geprobeerd met 2 merktekens die in een verschillend vlak liggen, zie figuur 4.12. Beide vlakken stonden loodrecht op elkaar. Hierbij lag de oorsprong van het wereld-co¨ordinatenstelsel opnieuw op grondniveau. De y-as liep naar boven en volgde de kruising van beide vlakken. De x-as liep volgens het rechtervlak, de z-as volgens het linkervlak. De resultaten blijken hier nog beter. De echte positie wordt zeer goed benaderd en de gemiddelde variantie is zeer beperkt.
4.7
Performantie
Figuur 4.13: Uitvoeringstijd en aantal iteraties i.f.v. het aantal referentiepunten (Lu et al., 2000).
Dit aspect werd ook besproken in (Lu et al., 2000). Dit is wat het algoritme interessant maakt. In een beperkt aantal iteraties is er steeds convergentie tot de oplossing (figuur 4.13, rechts). Dit resulteert ook in een beperkte uitvoeringstijd (figuur 4.13, links), wat het algoritme geschikt maakt voor real-time positiebepaling.
113
Hoofdstuk 4. Positiebepaling
Figuur 4.14: Uitvoeringstijd bij een constant aantal referentiepunten i.f.v. de tolerantie (R − Rcalc . (WindF¨ all, 2005)
Figuur 4.14 geeft een overzicht van de uitvoeringstijd bij een constant aantal referentiepunten i.f.v. de fout-tolerantie op de rotatiematrix. Dit aantal punten komt ongeveer overeen met het aantal dat per frame zal gebruikt worden. De uitvoeringstijd varieert hier wel iets, maar blijft steeds binnen de perken. Deze tijden komen ook ongeveer overeen met wat bij dit project werd vastgesteld.
4.8
GUI
Tot slot hebben we ook voor het uittesten van de positiebepaling een GUI voorzien (figuur 4.15. Deze kan bekomen worden via het voorlaatste item in het menu van figuur 2.9. Eerst moet opnieuw het pad naar de nodige configuratiebestanden opgegeven worden. Indien de nodige configuratieparameters (zie sectie 4.5.1) voorzien werden, kunnen door een klik op de knop Generate Marker Positions de posities van de merktekens gegenereerd worden. De gegenereerde posities (element MarkerPositions) worden toegevoegd aan het einde van het
114
Hoofdstuk 4. Positiebepaling
Figuur 4.15: GUI positiebepaling
configuratiebestand voor de positiebepaling. Dit moet dus eerst nog op de juiste plaats in het bestand gezet worden. Verder kunnen alle methodes voor positiebepaling uitgeprobeerd worden. Indien gewenst kunnen ook de terugprojecties van de hoeken van de merktekens aangeduid worden op de figuur. Dit geeft doorgaans een idee van de nauwkeurigheid van de bepaalde posities. Bij een klik op de knop Start Pose Estimation wordt een venster geopend met de camerabeelden (figuur 4.16). De translatie wordt onderaan weergegeven. In figuur 4.16 werden merktekens 1, 4 en 5 gebruikt voor de positiebepaling. De oorsprong van het wereld-co¨ordinatenstelsel is hier gelegen bij de linkerbovenhoek van het merkteken linksboven. De x-as wijst naar rechts, de y-as naar boven en de z-as naar voor.
115
Hoofdstuk 4. Positiebepaling
Figuur 4.16: Weergave gedetecteerde merktekens en positie en eventueel terugprojecties van de hoekpunten.
116
Hoofdstuk 5
Voorbeeldtoepassing 5.1
Principe
Figuur 5.1: Voorbeeldtoepassing: rendering scene m.b.v. Ogre3D
117
Hoofdstuk 5. Voorbeeldtoepassing Als voorbeeldtoepassing werd een voorbeeld van interactieve 3D visualisatie uitgewerkt. Hierbij wordt het zicht op een scene aangepast naargelang de positie van de observator. Rendering van een scene kon via Ogre3D (Torus Knot Software Ltd, 2007). Deze scene werd ge¨ımporteerd in Ogre3D vanuit Google SketchUp (Google, 2007), in deze omgeving kan op een intu¨ıtieve manier een 3D model worden aangemaakt. Bovendien kan je ook 3D modellen downloaden. Het model wordt in Google SketchUp wel best gealigneerd met de co¨ordinaatassen zodat het correct wordt weergegeven in Ogre3D. Exporteren van het model kan via de OgreXMLConverter (Torus Knot Software Ltd, 2007). Nadien moet de map waarin het model staat in het bestand resources.cfg vermeld worden, dit bestand staat in dezelfde map als het uitvoerbare bestand. Als scene werd gekozen voor een virtuele kamer/ruimte. De bedoeling is dat je a.h.w. kan bewegen doorheen de virtuele kamer op dezelfde manier als dit gebeurt in de echte kamer, waarin de eigenlijke merktekens werden aangebracht. De kamer wordt verondersteld balkvormig te zijn. Door bij aanvang van het renderen de afmetingen van de BoundingBox van het 3D-model op te vragen kunnen de afmetingen van de echte kamer, die vooraf worden doorgegeven, dan worden afgebeeld op de afmetingen van de virtuele kamer. Op deze manier kan eenvoudig een ander 3D-model worden gebruikt. Enkel de naam van het gebruikte model dient gewijzigd te worden. Het zicht op de scene kan in Ogre3D worden geregeld via een virtuele camera. De positie en rotatie van deze camera kan worden ingesteld t.o.v. een basis co¨ordinatenstelsel. Bij het renderen van een nieuw frame in Ogre3D wordt een frame opgevraagd van de echte camera. Indien via dit frame een nieuwe positie kon worden bepaald in de echte kamer, wordt de positie en ori¨entatie van de camera in de virtuele kamer aangepast zodat deze analoog gepositioneerd wordt aan de echte camera. Figuur 5.1 toont hier een voorbeeld van. Het 3D-model stelt hier een voetbalstadion voor. Door de overhead van het renderen wordt een framerate van ongeveer 16 frames per seconde gehaald. Na het installeren van de gepaste drivers kan de virtuele kamer ook via een head-mounted display (HMD) bekeken worden.
5.2
GUI
Via het laatste item in het menu van figuur 2.9 kan de GUI voor de voorbeeldtoepassing gestart worden (figuur 5.2). Opnieuw moet eerst het pad naar de configuratiebestanden worden doorgegeven. Vervolgens moet enkel de naam van het model en de dimensies van de echte kamer worden doorgegeven. Bij een klik op de knop Start verschijnt het Ogre3D-menu.
118
Hoofdstuk 5. Voorbeeldtoepassing
Figuur 5.2: GUI voorbeeldtoepassing
Belangrijk is wel dat het menu-item Floating-point mode bij gebruik van de Direct3D-renderer op Consistent wordt gezet. Na klikken op OK wordt het venster geopend met de gerenderde scene, dit kan wel enkele seconden duren.
119
Besluit Het doel van dit eindwerk was lokalisatie van een persoon of object dat een camera draagt door het opsporen van merktekens in de camerabeelden. Hiertoe werden in eerste instantie geschikte merktekens ontworpen. De opbouw van deze merktekens is flexibel, de merktekens kunnen worden samengesteld door de gebruiker zodat ze perfect aangepast kunnen worden aan de omgeving. Enerzijds is het aantal benodigde merktekens hierbij van belang, maar ook de redundantiebits spelen een grote rol. Wanneer in de omgeving bv. weinig detail voorkomt, mogen de merktekens doorgaans minder foudetectiebits bevatten. Op deze manier wordt ook onrechtstreeks de benodigde grootte van de merktekens bepaald. Een tweede onderdeel was de merktekenextractie en -identificatie. Het zoeken van de juiste methode, rekening houdende met de performantie, was hierbij zeker niet eenvoudig. Er werd grotendeels afgeweken van de standaardmethodes die binnen beeldverwerking gekend zijn. Op deze manier werd meer vat op het proces verkregen en kon bij elke fase van het proces de structuur van de merktekens zo goed mogelijk uitgebuit worden, wat geleid heeft tot een betrouwbare extractie. Van OpenCV werden naast de functies voor het ophalen van camerabeelden, de datatypes en enkele basisbewerkingen dan ook weinig elementen gebruikt. Deze fase blijkt wel degelijk te voldoen aan de voorwaarden voor deze toepassing. Via de configuratieparameters kan het proces bovendien goed aangepast worden aan de gebruikte camera. Dan werd de eigenlijke positiebepaling gerealiseerd. Eerst werd de calibratie van een camera in het systeem ge¨ıntegreerd zodat dit heel eenvoudig kan uitgevoerd worden. Vervolgens werden in eerste instantie bestaande methodes voor positiebepaling vergeleken en onderzocht. Ook hier was heel wat zoekwerk nodig en het begrijpen van de methodes was niet eenvoudig. Na veel problemen kon uiteindelijk een bestaande implementatie binnen het eigen project ge¨ıntegreerd worden. Bovendien kon het algoritme nog geoptimaliseerd worden, zodat het probleem met de pose jumps zoveel mogelijk werd vermeden. Er werden een aantal experimenten uitgevoerd, waaruit blijkt dat de nauwkeurigheid algemeen goed meevalt. Het werd hierbij ook duidelijk dat gebruik van een groter aantal merktekens wel degelijk een positieve
120
invloed op de nauwkeurigheid heeft. Een configuratie met merktekens in verschillende vlakken blijkt het best te werken. De configuratie voor de positiebepaling is ook flexibel. Deze laat toe om merktekens te gebruiken die op alle mogelijke plaatsen in een ruimte werden aangebracht. Het specifi¨eren van de merktekenposities t.o.v. een co¨ordinatenstelsel van een vlak zorgt ook voor een groter gebruiksgemak. Ook werd de mogelijkheid voorzien om de merktekenposities automatisch te genereren, waarbij met alle nuttige criteria rekening wordt gehouden. Tot slot werd een toepassing ontworpen voor interactieve 3D visualisatie die een mooie illustratie is van het ontworpen systeem. Om de gebruiksvriendelijkheid nog te vergroten werd ook voor elk onderdeel een GUI ontworpen. Alle items van het thesisvoorstel werden dus volledig gerealiseerd. De ontworpen GUI’s vormen hierbij nog een extraatje. De uitbreidingen werden niet gerealiseerd, wel werden 2 technieken gevonden die een basis kunnen vormen voor verder werk. Deze worden ge¨ımplementeerd via OpenCV-functies, voor elk van beide werd een testprogramma geschreven.
Figuur 5.3: Illustratie Harris Corner detector.
Enerzijds kan bij de merktekenextractie informatie gebruikt worden uit een vorig frame. De positie van de merktekens zal immers maar weinig gewijzigd zijn. Een mogelijkheid zou het opsporen van hoeken binnen de afbeelding kunnen zijn en het afbeelden van de hoeken van de merktekens binnen het huidige beeld op de nieuw gevonden hoeken. Het zoeken van hoeken vereist namelijk niet altijd de contouren van objecten. De Harris Corner detector bijvoorbeeld werkt anders en wordt door de OpenCV-functie cvCornerHarris ge¨ımplementeerd. De gevonden hoeken kunnen hierbij weergegeven worden via een beeld met verschillende intensiteiten (figuur 5.3).
Figuur 5.4: Illustratie feature tracking (Intel, 2007).
Uiteindelijk zou ook zonder merktekens gewerkt kunnen worden en zou de beweging van de camera kunnen worden bepaald op basis van features in het beeld. Dit kan misschien via de OpenCV-functies cvGoodFeaturesToTrack en cvCalcOpticalFlowPyrLK. De eerste functie spoort features op in het beeld. De tweede tracht de beweging tussen 2 frames te bepalen op basis van deze features. Op basis van ´e´en van de voorbeeldprogramma’s geleverd bij een distributie van OpenCV, werd een testprogramma geschreven waarbij eerst wordt gezocht naar features. In de volgende frames worden de posities van dezelfde features in het beeldvlak opnieuw berekend door het bepalen van de beweging (figuur 5.4). Wanneer geen van de features meer in beeld zijn, wordt er opnieuw naar features gezocht.
Bibliografie (2005). Error correcting codes. http://www.hackersdelight.org/ecc.pdf. J.-Y. Bouguet (2007). Camera calibration toolbox for matlab. http://www.vision.caltech. edu/bouguetj/calib_doc/. CVonline (1996). Edges: The canny edge detector. http://homepages.inf.ed.ac.uk/rbf/ CVonline/LOCAL_COPIES/MARBLE/low/edges/canny.htm. ETH Zurich, Department of Computer Science (2006). Visual code recognition for cameraequipped mobile phones. http://www.inf.ethz.ch/personal/rohs/visualcodes/. M. Fiala (2004). Artag revision 1. a fiducial marker system using digital techniques. NRC/ERB-1117, p. 46. http://iit-iti.nrc-cnrc.gc.ca/publications/nrc-47419_ e.html. M. Fiala (2007). Artag. http://www.artag.net. S. M. Gerhard (2002). Robust 2d tracking for real-time augmented reality. In In Proceedings of Vision Interface (VI), pp. 399–406. Calgary, Alberta, Canada. R. C. Gonzalez & R. E. Woods (2001). Digital Image Processing. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. ISBN 0201180758. Google (2007). Google sketchup. http://www.sketchup.com/. Graphics & Media lab (2006). Recommendations for taking calibration photos. http://research.graphicon.ru/calibration/ recommendations-for-taking-calibration-photos.html. X. C. He & N. H. C. Yung (2004). Curvature scale space corner detector with adaptive threshold and dynamic region of support. In ICPR ’04: Proceedings of the Pattern Recognition, 17th International Conference on (ICPR’04) Volume 2, pp. 791–794. IEEE Computer Society, Washington, DC, USA. ISBN 0-7695-2128-2. Hitlab (Z.D.). Artoolkit. http://www.hitl.washington.edu/artoolkit/. 123
Bibliografie Intel (2007). Open source computer vision library. http://www.intel.com/technology/ computing/opencv/index.htm. H. Kato & M. Billinghurst (1999). Marker tracking and hmd calibration for a video-based augmented reality conferencing system. In IWAR ’99: the 2nd International Workshop on Augmented Reality, pp. 85–94. San Francisco, USA. E.-J. P. Kyung-Seok Seo, Jong-Hwa Kim & H.-M. Choi (2006). Directional edge tracking for line extraction. In SPPRA’06: Proceedings of the 24th IASTED international conference on Signal processing, pattern recognition, and applications, pp. 280–283. ACTA Press, Anaheim, CA, USA. ISBN 0-88986-580-9. T. Lee (2006). 3d reconstruction for augmented reality. http://www.cs.ucsb.edu/~taehee/ pdf/3D%20Reconstruction%20for%20Augmented%20Reality.pdf. V. Lepetit & P. Fua (2005). Monocular Model-based 3d Tracking of Rigid Objects (Foundations and Trends in Computer Graphics and Vision(R)). Now Publishers Inc. ISBN 1933019034. http://www.nowpublishers.com/product.aspx?product=CGV&doi=0600000001. C.-P. Lu, G. D. Hager & E. Mjolsness (2000). Fast and globally convergent pose estimation from video images. IEEE Trans. Pattern Anal. Mach. Intell., 22(6):610–622. ISSN 01628828. http://citeseer.ist.psu.edu/lu98fast.html. P. Malbezin, W. Piekarski & B. Thomas (2002). Measuring artoolkit accuracy in long distance tracking experiments. ART02, 1st International Augmented Reality Toolkit Workshop. citeseer.ist.psu.edu/malbezin02measuring.html. F. Mokhtarian & R. Suomela (1998). Robust image corner detection through curvature scale space. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(12):1376–1381. ISSN 0162-8828. C. Owen, F. Xiao & P. Middlin (Z.D.). What is the best fiducial. http://metlab.cse.msu. edu/tracking-prepared/charles-owen-art02.pdf. W. Piekarski & B. Thomas (2002). Using artoolkit for 3d hand position tracking in mobile outdoor environments. ART02, 1st International Augmented Reality Toolkit Workshop. http://www.tinmith.net/papers/piekarski-art-2002.pdf. A. W. R. Fisher, S. Perkins & E. Wolfart. (2003). Gaussian smoothing. http://homepages. inf.ed.ac.uk/rbf/HIPR2/gsmooth.htm. P. Santos, A. Stork, A. Buaes & J. Jorge (2006). Ptrack: Introducing a novel iterative geometric pose estimation for a marker-based single camera tracking system. vr, 0. ISSN 1087-8270. 124
Bibliografie G. Schweighofer & A. Pinz (2006). Robust pose estimation from a planar target. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(12):2024–2030. ISSN 01628828. http://www.emt.tugraz.at/publications/EMT_TR/TR-EMT-2005-01.pdf. The Apache Software Foundation (2005). Xerces c++ parser. http://xml.apache.org/ xerces-c/. The MathWorks (2007). Matlab - the language of technical computing. mathworks.com/products/matlab/.
http://www.
Torus Knot Software Ltd (2007). Ogre. http://www.ogre3d.org/. D. van Heesch (2007). Doxygen - source code documentation generator tool. http://www. doxygen.org. D. Wagner (2007). Artoolkitplus. http://studierstube.icg.tu-graz.ac.at/handheld_ ar/artoolkitplus.php. H. Wallace (2003). Using the golay error detection and correction code. http://www.aqdi. com/golay.htm. A. WindF¨all (2005). Principles of robust and accurate computational 3d positioning from 2d image data. http://www.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/ 2005/rapporter05/windfall_asa_05030.pdf.
125
Inhoud CD In de hoofdmap werd de elektronische versie van deze scriptie, het eindwerkvoorstel, logboek en poster voor de opendeurdag geplaatst. Binnen de map MarkerTracking zijn de bestanden als volgt ingedeeld: De map Matlab-code bevat de belangrijkste Matlab-functies die bij dit project werden geschreven. Telkens werd bovenaan bij elk bestand de nodige documentatie voorzien. De belangrijkste functie is detectIdentifyMarkersFrame, deze zorgt voor de eigenlijke extractie en identificatie van merktekens en roept andere functies aan. Deze functies kunnen bijvoorbeeld uitgeprobeerd worden op de afbeeldingen in de map testfiguren. De map mex voorziet de code voor het mex-bestand mexMarkerIdExtractor en kan gebuild worden via make mexMarkerIdExtractor. Eventueel moeten de parameters in het bestand opts worden aangepast. De mappen Ogre, OpenCV en xerces-c bevatten nodige header-files, bibliotheken en 3D-modellen van de gelijknamige technologie¨en. De mappen src en include bevatten de source-code en header-bestanden voor de C++implementatie van het project. De map testProgramma’s bevat de broncode van een aantal testprogramma’s waarvan de bijhorende uitvoerbare bestanden zich in de map bin bevinden. De meeste testprogramma’s kunnen rechtstreeks van op de CD gestart worden. De toepassing voor interactieve 3D visualisatie genereert echter een configuratiebestand in de huidige directory. De gebruikte bestanden worden dan ook best gewoon lokaal gekopieerd. De map documentatie bevat de documentatie die bij de C++-implementatie hoort, gegenereerd via doxygen. De map configuratie bevat het XML-schema en de XSLT voor de configuratie van de applicatie. Daarnaast werden een aantal voorbeeldbestanden voorzien, o.a. de configuraties die gebruikt werden bij het testen van de positiebepaling. De map samplesMarkerConfig bevat een aantal voorbeeldmerktekens met hun bijhorende configuratie.
126
De map GUI bevat de bestanden voor het oproepen van de GUI in Matlab. Gui Main bevat hierbij het hoofdmenu. De map mex bevat opnieuw de broncode van de bijhorende mex-bestanden, met de script-bestanden om ze te genereren a.d.h.v. de broncode. De map verder werk bevat tenslotte de testprogramma’s voor de Harris corner detector en het gebruik van features. De bijhorende uitvoerbare bestanden bevinden zich in de map bin.
