Informatica — Universiteit van Amsterdam
Bachelor Informatica
3D Desktop Scanner
Remco Gubbels
[email protected] 5872456
14 juni 2011
Supervisor(s): Rein van den Boomgaard (UvA)
2
HOOFDSTUK 1
Samenvatting Het doel van dit onderzoek is om met een simpele huis-tuin-en-keuken webcam en een simpele lijn-laserpen een scan te maken van een 3D object. Door middel van het kalibreren van de camera, detecteren van de laserlijn in de veschillende foto’s die gemaakt worden en het terugrekenen van de 2D naar 3D coordinaten wordt geprobeerd om dit doel te halen. Technieken die hiervoor gebruikt worden zijn bijvoorbeeld Zhang’s camera kalibratie algoritme en het Total Least Squares algoritme. Tot slot wordt er nog geprobeerd van alle berekende punten een mooie mesh te maken met behulp van Delaunay.
3
4
Inhoudsopgave
1 Samenvatting
3
2 Inleiding 2.1 Probleem schets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Gerelateerde Onderzoeken . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Introductie geometrisch model . . . . . . . . . . . . . . . . . . . . . . . .
7 7 8 9
3 Camera kalibratie 3.1 Verschillende methoden 3.1.1 Zhang . . . . . . 3.1.2 DLT . . . . . . . 3.1.3 SVD-trick . . . . 3.1.4 Dit onderzoek . . 3.2 Interne Matrix . . . . . 3.3 Externe Matrix . . . . .
. . . . . . .
4 Detectie laserlijn 4.1 Detectiemechanisme . . . 4.2 Op de achtergrond . . . . 4.2.1 Total least squares 4.3 Op het object . . . . . . . 4.3.1 Data fitting . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . . . .
11 11 11 11 12 12 12 13
. . . . .
15 15 16 16 17 18
5 Omrekenen van punten 19 5.1 Oplossing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Visualisatie 6.1 Mesh . . . . . . . . . . . . . . . . . . 6.2 Delaunay . . . . . . . . . . . . . . . 6.2.1 Voorbereidend werk . . . . . 6.2.2 Beginnen met de triangulatie 6.2.3 Range Searching . . . . . . . 6.2.4 Shelling . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
21 21 21 22 23 23 24
7 Conclusie 7.1 Kalibratie . . . . . 7.2 Detectie laserlijn . 7.3 Omrekenen punten 7.4 Vormen mesh . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
27 27 28 28 29
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . 5
. . . .
7.5 7.6
Eindconclusie . . . . . . . . . . . . . Uitbreidingen . . . . . . . . . . . . . 7.6.1 Verbeteren huidige systeem . 7.6.2 Combineren van verschillende
6
. . . . . . . . . . . . . . . meshes
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
29 30 30 30
HOOFDSTUK 2
Inleiding 2.1 Probleem schets Tegenwoordig worden er steeds vaker 3D modellen gebruikt, kijk maar naar de groei in de gaming wereld of in de architectuur wereld. Mensen die beroepen uit oefenen in deze beroepsgroepen zullen te maken krijgen met het vormgeven van 3D modellen, hier is tegenwoordig al aardig wat software voor om dit vanaf scratch te doen. Sommige van dit soort werknemers zijn al heel goed in het sculpten van beelden, maar die moeten omdat het resultaat verwerkt moet worden met de computer dit soort software onder de knie gaan krijgen. Dit kan voor veel vertraging zorgen, aangezien een sculpter niet altijd net zo snel een 3D model kan weergeven in de computer als in het echt. Voor dit soort mensen zijn 3D desktop scanners een uitvinding. Het 3D model kan gewoon gesculpt worden, ingescanned en dan de imperfecties van de scan kunnen er dan snel uitgehaald worden in een 3D model edit programma. Over het onderwerp 3D desktop scanners zijn al verschillende scripties [4] [3] verschenen, deze zijn over het algemeen heel oppervlakkig en gaan niet diep in op de wiskunde die gebruikt wordt bij zo’n project. Op de markt zijn ook al verschijnende goedkope 3D desktop scanners, maar hier zit over het algemeen ook geen informatie bij hoe dit gerealiseerd wordt.
Figuur 2.1: Het uiteindelijke doel van object (links) naar 3D model (rechts) bron: http://www.vision.caltech.edu/bouguetj/ICCV98/index.html Het doel van dit onderzoek is om met behulp van state-of-de-art technologie van een object een 3D visualisatie te maken door middel van een vlak-laser en een webcam. Voor de webcam is er gebruik gemaakt van een Logitech Quickcam for Notebook Pro en voor de laserpen is er gebruik gemaakt van een laserpen van david-vision-systems.de. Er zal onderscheidt gemaakt worden tussen verschillende onderdelen die nodig zijn voor dit project. Het probleem kan opgedeeld worden in kleinere problemen, deze kunnen dan 7
Figuur 2.2: Links: Webcam (Bron: 2dayblog.com). Rechts: Laserpen (Bron: davidvision-systems.de) ´e´en voor ´e´en opgelost worden. Er is voor de volgende opdeling gekozen voor dit project. 1. Het kalibreren van de camera, om er voor te zorgen dat de geometrische omgeving bekend is en de oneffenheden er ook uitgehaald worden. 2. Detecteren van de laserlijn in de afbeeldingen die gebruikt worden. 3. Het omrekenen van de 2D punten uit de afbeelding naar 3D punten in de geometrische omgeving. 4. Omzetten van de 3D punten in een oppervlak voor de visualisatie van het model. In de volgende hoofdstukken zullen al deze problemen behandeld worden en zal er per onderdeel een resultaat te zien zijn die veel belovend zijn voor verdere onderzoeken.
2.2 Gerelateerde Onderzoeken In dit onderzoeksveld zijn al meerdere onderzoeken gedaan naar 3D desktop scanners. In het verleden zijn er verschillende thesisen verschenen van verschillende mensen op dit gebied. In het jaar 1999 kwam Bouguet [4] met een 3D desktop scanner die werkt doormiddel van een lamp, stok en een camera om alles op te nemen. Hierbij wordt inplaats van een laserlijn gebruikt gemaakt van de schaduw van de stok die op het object geprojecteerd wordt. Een duidelijke overeenkomst tussen de twee projecten is dat dezelfde soort berekeningen worden gedaan. De punten worden bij het project van Bouguet namelijk ook vergeleken met de achterwand en de schaduw die daar op valt. Meer hierover is te vinden in hoofdstuk 4 dat over het omrekenen van de punten gaat. In 2009 is op de Brown universiteit ook nog een thesis [3]verschenen die deze zelfde benadering had toegepast en uitgelegd. In hetzelfde thesis wordt er ook gebruik gemaakt van structered licht, dit houdt in dat er voor een lamp een patroon wordt gehouden of vastgemaakt die er dan voor zorgt dat er rechte lijnen op het object vallen die dan worden gebruikt om de 3D coordinaten te bepalen van het object. Het verschil tussen Brown en Bouguet is dat de Brown er gebruik wordt gemaakt van meerdere schaduwen in ´e´en foto, dit zorgt ervoor dat er minder foto’s nodig zijn om hetzelfde resultaat te kunnen ondervinden.
8
2.3 Introductie geometrisch model Voor een 3D desktop scanner maak je gebruik van een 3D omgeving, ook wel het geometrische model genoemd. Het model bevat x, y, z coordinaten die in het plaatje worden weergegeven. Deze coordinaten geven aan waar in de 3D omgeving een punt zich zou moeten bevinden in vergelijking tot de andere punten. Voor het berekenen van deze punten zullen we gebruik gaan maken van de twee statische achterwanden. De twee achterwanden zullen tijdens de kalibratie vaste 3D coordinaten krijgen, zodat er een vergelijkingspunt is. Dit geometrisch model zal als een rode draad door de scriptie lopen, omdat het model bij elke stap gebruikt zal worden en benoemd.
Figuur 2.3: Geometrische model In figuur 2.3 is het geometrische model te zien. In dit figuur worden de assen van de 3D wereld aangeven door de blauwe (z-as), groen (y-as) en rood (x-as). De witte stippen geven de kalibratie punten aan.
9
10
HOOFDSTUK 3
Camera kalibratie 3.1 Verschillende methoden Het kalibreren van een camera is een activiteit die voor veel verschillende beeldbewerkings opdrachten noodzakelijk is. Hierdoor is er al veel onderzoek gedaan naar verschillende methoden om dit voor elkaar te krijgen. De meest gebruikte kalibratie methoden zijn de methoden van Zhang en DLT.
3.1.1 Zhang De complete uitleg over Zhang’s kalibratie methode is een heel uitgebreide en zal hier dus niet uitgebreid behandeld worden. Deze complete uitleg is te vinden in de scriptie die is door Zhang is geschreven in 2000 [1]. Zhang maakt gebruik van meerdere plaatjes van een schaakbord patroon, die in verschillende hoeken is gehouden. Uit al deze plaatjes is het mogelijk om de transformaties te vinden tussen de 2D en de 3D coordinaten. Al deze transformaties die gevonden worden in de afbeeldingen zijn genoeg om door middel van Zhang’s methode de interne matrix te vinden.
3.1.2 DLT De DLT methode is een goede kalibratie techniek als er al een paar bekende 2D coordinaten zijn die matchende 3D coordinaten vastgesteld hebben. Deze methode wordt uitgevoerd door de lineare transformatie te berekenen tussen deze punten. X x Y (3.1) s y = P Z 1 1
Of:
˜ s˜ x = PX
(3.2)
Waarin P de lineare transformatie matrix voorsteld en s de schaalfactor. Omdat het van een 1 bij 4 vector naar een 1 bij 3 vector berekend moet worden is de lineare transformatie matrix een 4 bij 3 matrix. Dit kan omgeschreven worden naar: sx1 sx2 s
= = = 11
˜ pT1 X ˜ pT2 X T ˜ p3 X
(3.3)
Als we nu de eerste twee berekingen samenvoegen met de derde resulteerd dit in een vergelijking waarmee we P kunnen berekenen. T p1 T T ˜ ˜ X 0 − xX p2 = H n p = 0 (3.4) T T ˜ ˜T 0 X − yX p3
Voor elk 2D-3D paar dat er beschikbaar is is er zo’n berekening. Deze worden verticaal op elkaar gestapeld om zo H te vormen. H1 .. (3.5) . p = Hp = 0 Hn
Om de optimale p te vinden wordt nu de SVD-Trick uitgevoerd op de matrix H. Deze optimale p is een 1x12 vector. Om de lineare transformatie matrix te vormen uit deze vector wordt deze omgezet in een 3x4 matrix. p1 p 1 . . . p4 .. . .. (3.6) . ⇒ .. . p1 2 p9 . . . p12
3.1.3 SVD-trick De SVD trick is een lineare algebra trucje dat hier kort toegelicht zal worden. Voor verdere informatie kan gekeken worden naar de Pinhole Camera pdf [9] van R. van den Boomgaard en L. Dorst. Als de singular value decompesation wordt losgelaten op een matrix A, die samenhangt met h op de volgende manier Ah = 0 dan is de optimale oplossing voor de vector h de laatste kolom van V in A = U DV T .
3.1.4 Dit onderzoek Bij dit onderzoek zal er gebruik worden gemaakt van beide technieken, dit omdat de methode van Zhang heel goed is in het bepalen van de interne matrix met een beperkt aantal beelden. Om de externe matrix te berekenen zal er ook gebruik worden gemaakt van een gedeelte uit de DLT methode, dit omdat DLT weer heel snel en precies werkt als er een vast aantal bekende 2D gematched met 3D coordinaten zijn.
3.2 Interne Matrix De interne matrix zorgt ervoor dat de ongelijkheden van de camera wegvallen. Een gewone webcame is verreweg van perfect qua pixelplaatsing. Dat wil zeggen soms staan punten niet op de plek waar je ze verwacht. Dit heeft te maken met verschillende factoren namelijk: 1. Positie van het midden van de afbeelding (is niet altijd breedte/2, hoogte/2) 2. Brandpuntsafstand van de lens 3. Verschillende schalingsfactoren voor de rij en kolom pixels 4. Skew factor (Afbeelding is scheef) 12
5. Lens distortion (speldenkussen effect) (verstoring, vervorming, ruis) Deze matrix is een 3x3 matrix die al deze effecten probeert te verminderen. αx γ u 0 A = 0 αy v 0 0 0 1
(3.7)
Deze vijf parameters stellen de brandspuntafstand, midden van de afbeelding en de skewfactor voor. αx = f × mx en αy = f × my waarin mx en my de schalingsfactoren in respectiefelijk de x en y richting zijn. f stelt de gewone brandspuntafstand voor. u0 en v0 zijn de coordinaten van het echte midden van de afbeelding, hoe dunner de lens, hoe minder dit breedte hoogte zal afwijken van , 2 van de afmetingen van de afbeelding. y is de skewfactor 2 van de afbeelding en is over het algemeen 0.
Figuur 3.1: Twee van de foto’s die gebruikt worden bij het kalibratie proces van de interne matrix
3.3 Externe Matrix
Figuur 3.2: De groene punten stellen de subpixel nauwkeurige coordinaten voor, die gebruikt worden bij de externe matrix kalibratie. Rechts een vergroting. Nu de interne matrix I berekend is door middel van meerdere views, is het tijd om de camera op de plaats te zetten waar deze gaat staan tijdens het scannen van het object. In deze fase wordt de externe matrix berekend die de rotatie vectoren en de translatie vectoren bevat. Deze matrix zorgt ervoor dat een 2D coordinaat omgezet kan worden in de juiste 3D coordinaat. Om dit te kunnen berekenen maken we gebruik van de interne matrix en zes vaste wereld coordinaten, waarbij ook de 2D coordinaten bekend zijn. Deze punten zijn te zien in figuur 2.2. Als eerste wordt de lineare transformatie matrix P berekend door middel van de DLT methode, die in 2.1.2 is uitgelegd. Voor de externe 13
matrix is er een 3x4 matrix nodig, die bestaat uit drie rotatievectoren, voor elke as ´e´en en een translatievector. De lineare transformatie matrix P heeft dezelfde vectoren die nodig zijn al. Het enige probleem is dat deze nog niet genormalizeerd zijn en nog niet door een filter heen zijn gegaan om de ongelijkheden van de camera weg te halen. Dit gebeurt door de inverse te gebruiken van de interne matrix, I ′ . P I1 = A
(3.8)
Waarin A de gefilterde lineare transformatie matrix is. Om de schaalfactor te berekenen kan er gebruik worden gemaakt van het feit dat alle vectoren in P homogeen zijn, dus hoeft er maar ´e´en vector genormalizeerd te worden. s=
1 norm(P1T )
(3.9)
Nu de schaalfactor s bekend is kan deze worden toegepast op de gehele matrix A. sA = E E is de uiteindelijke externe matrix r1
r2
14
r3
(3.10) t
HOOFDSTUK 4
Detectie laserlijn 4.1 Detectiemechanisme Bij dit project wordt er gebruikt gemaakt van een fel rode laserlijn, dit zorgt er namelijk voor dat de laserlijn makkelijker op te sporen is in een afbeelding. Om de laserlijn op te sporen wordt er gekeken naar de intensiteits waarden van elke pixel. Per x-coordinaat wordt er een top bepaald waar de rode intensiteit van de pixel het hoogst is. Dit zorgt er
Figuur 4.1: Intensiteits waarden van alle y pixels met een vaste x. over het algemeen voor dat de pixels die op de laserlijn liggen worden gebruikt als top. Als de laserpunten geselecteerd zijn, worden deze op twee manieren gescheiden, punten op het object en punten die op de achtergrond liggen. Het bepalen of een punt op de achtergrond ligt wordt uitgevoerd met een versimpeld Wall and Danielson algoritme. Dit algoritme bekijkt of het volgende punt in de lijst ook op dezelfde functie lijn zou kunnen liggen met een fout-marge natuurlijk. Het werkt heel simpel, het eerste punt dat wordt gepakt ligt een paar pixels vanaf de rand, om er voor te zorgen dat er nog wat speling is met de rand van de achterwand. Daarna wordt er paar volgend punt gekeken of deze binnen een bepaalde afstand zit van het vorige punt, is dit zo voeg hem toe en anders negeer dit punt en controleer het volgende punt. De reden waarom er af en toe een punt genegeerd kan worden maar toch nog verder kan worden gekeken, is omdat er af en toe foute lezingen bij zitten van welk punt de top is. 15
Er is een limiet gesteld aan twee fouten achter elkaar, als er twee optreden dan zijn er genoeg punten op de achterwand geselecteerd. Ditzelfde principe wordt uitgevoerd voor de andere wand, maar daar lopen we terug in de pixels.
4.2 Op de achtergrond Er zullen ook punten van de laserlijn naast het object terecht komen, dit is ook de bedoeling. Deze punten worden namelijk gebruikt om het laserplane te berekenen waar de punten van het object in liggen. Omdat de bovenstaande methode om de punten op de laserlijn te detecteren niet sub-pixel nauwkeurig is zal er nog gebruik gemaakt moeten gaan worden van twee fit technieken.
4.2.1 Total least squares Total least squares is een uitbreiding op het veel gebruikte Least squares algoritme dat voor een groep punten de subpixel nauwkeurige lineare functie kan vinden. Total least squares is iets uitgebreider, maar hierdoor wel preciezer. Bij het least squares algoritme bekijk je het verschil tussen de lijn en de punten in ´e´en asrichting. Bij total least squares bekijk je de kortste afstand vanaf het punt tot de lijn. Een total least squares functie ziet er uit als een gewone lineare functie namelijk
Figuur 4.2: Links: Least squares, rechts: Total least squares. Bron: Wikipedia x+c = y. r1 x + r2 y + c = 0 of omgeschreven in een bruikbare functie r1−r 2 Het algoritme zorgt voor een functie die voor alle afstanden vanaf de punten een minimale waarde geven, zodat het de best gefitte lijn is. Om dit minimalizeer probleem op te lossen gebruik we de volgende functie om de optimale waarde voor r1 en r2 te vinden.
I(r, z¯) = (r1 (xi − x ¯) + r2 (yi − y¯))2 = ||Br||22
(4.1)
Waarin z¯ = (¯ x, y¯)T x ¯ en y¯ worden berekend door middel van het gemiddelde te berekenen van alle punten in de verzameling.
(¯ x, y¯) =
n
n
i=0
i=0
1X 1X xi , yi n n 16
!
(4.2)
En B is een matrix die gevormd wordt door alle punten in de verzameling. x1 − x ¯y1 − y¯ x2 − x ¯y2 − y¯ B= . .. . . . xn − x ¯y2 − y¯
(4.3)
Nu B gevormd is het mogelijk om door middel van de SVD trick toe te passen op deze matrix B de vector r te vergaren. Dit is een 1x2 vector, waardoor r1 en r2 simpel te bepalen zijn. Om de formule r1 x + r2 y + c = 0 te voltooien is er alleen nog de constante c nodig, die als startwaarde dient. c = −(r1 x + r2 y)
(4.4)
Voor uitgebreide informatie over total least squares is de scriptie van P. de Groen [7], An Introduction to Total Least Squares goed te gebruiken.
4.3 Op het object De punten die op het object liggen zijn de punten die uiteindelijk nodig zijn om het uiteindelijke model te representeren. Deze punten worden gekozen doormiddel van het vergelijken van het punt en de total least squares functies van de achterwand, als de waarde die voor die x waarde dichtbij de uitgelezen waarde ligt dan ligt dit punt nog op de achterwand. Als dit niet het geval is ligt dit punt op het object. Om deze resulterende punten zo nauwkeurig mogelijk te krijgen maken we gebruik van data fitting.
17
4.3.1 Data fitting Data fitting zorgt ervoor dat er een subpixel nauwkeurige benadering zal worden bepaald voor een functie fit door een aantal punten. In dit geval de punten rondom de hoogste rode intensiteit waarde. Er wordt hier uitgegaan van een tweedegraads polynominale functie, omdat het hier over ´e´en top gaat. Dit moet een functie opleveren in de vorm van y = ax2 + bx + c. Hier zal verder niet ingaan op het fitting proces, maar een
Figuur 4.3: Een data fit van vijf punten veel gebruikt fitting proces is het Least Squares Fitting algoritme [6] Als deze functie gevonden is door middel van het fitting proces, wordt hier de vanaf de eerste x waarde tot de laatste x waarde van de punten die gebruikt zijn in dit proces gekeken naar de resulterende waarden. De hoogste waarde is de subpixel nauwkeurige coordinaat die gezocht werd.
18
HOOFDSTUK 5
Omrekenen van punten Het enige dat nog te doen is het omrekenen van de punten die we uit de frames halen om te rekenen naar de 3D wereld punten die we willen hebben. Het ligt voor de hand om gebruik te maken van de kalibratie matrix, aangezien deze de geometrische omgeving kent. Maar het probleem zit hierin dat je in een 2D beeld geen diepte hebt. Hierdoor is het alleen mogelijk om alleen gebruik te maken van de kalibratie matrix en voor de rest niks op punten die op de bekende achterwanden liggen.
5.1 Oplossing Het probleem ligt er dus in om van het 2D punt zonder diepte een 3D punt te maken die diepte heeft. Hiervoor maken we gebruik van een laserplane. Dit laserplane is te berekenen doormiddel van de punten op de achterwanden A en B. Door middel van deze punten hebben we namelijk de twee zijnkanten van het laserplane te pakken. Van deze
Figuur 5.1: De twee zijwanden met A als linker en B als rechter twee zijden worden meerder punten gepakt die op de laserlijn liggen. Al deze punten 19
worden gestappeld in een grote matrix B. A1 .. . An B= B1 .. .
(5.1)
Bn
Waarin de punten van A en B homogene 3D coordinaten zijn. Door nu de SVD trick toe te passen op B komt daar als resultaat het laserplane Pl . Nu we het laserplane berekend hebben kunnen we doormiddel van het laserplane en de kalibratiematrix het 2D punt omzetten in een 3D punt. Gegeven Pl en C willen we nu de 3D coordinaten X van de 2D coordinaten x krijgen. Gegeven het kruisproduct van de twee evenwijdige vectoren: x × CX = 0 Kruisproduct in matrixvorm: [x]x CX = 0 Omdat X ook in laserplane Pl ligt, weten we ook: PlT X = 0 Ofwel:
[x]× C M X = 0 met M = PlT
(5.2)
Nadat M is berekend, kunnen we hierop de SVD-trick die in 2.1.3 is uitgelegd toepassen. Dit levert een homogeen 3D coordinaat op.
20
HOOFDSTUK 6
Visualisatie Er zijn verschillende methoden om de 3D coordinaten te visualiseren nadat deze zijn berekend. De simpelste manier om deze punten te visualiseren is om op deze coordinaten kubusen te plaatsen om zo een indicatie te krijgen van hoe het model er uit ziet. Dit levert over het algemeen geen goed resultaat op, omdat er in normale modellen over het algemeen ook schuine zijden zitten en omdat er gebruik wordt gemaakt van kubusen is het niet mogelijk om deze schuine zijden goed te visualiseren. Een andere en veel gebruikte methode om de punten te weergeven is het vormen van een skelet van de punten. Zo’n skelet wordt een meestal een mesh genoemd en bestaat over het algmeen uit driehoeken, maar kan door allerlei verschillende soorten polygonen bestaan.
6.1 Mesh Zoals hierboven ook al staat beschreven is een mesh en verzameling van punten. Het grote verschil tussen een mesh en gewoon het gebruik maken van kubusen is het feit dat bij de kubusen over het algemeen de punten het middelpunt zijn en bij een mesh liggen de punten op de zijkant. Dit zorgt ervoor dat de precisie van de gescande modellen veel hoger ligt. Een mesh wordt gevormd uit polygonnen, over het algemeen wordt er per mesh gebruik gemaakt van dezelfde soort polygonnen, maar dit is niet altijd zo. Er zijn verschillende methoden om een mesh te berekenen. Twee bekende en veel gebruikte methoden zijn de marching cubes algoritme, die gebruikt maakt van kubusen zoals de naam al verspeld, of het delaunay algoritme, die gebruikt maakt van driehoeken. Voor dit project heb ik gekozen voor het delaunay algoritme, omdat dit een mooier resultaat opleverd dan het marching cubes algoritme, aangezien er meer vrijheid is, omdat er niet vast wordt gehouden aan een soort polygon.
6.2 Delaunay Het delaunay algoritme is een triangulatie algoritme, een algoritme dat van een set van punten alle punten indeeld in driehoeken. In dit hoofdstuk zal er oppervlakkig worden gekeken naar dit algoritme, omdat het uitgebreid na gelezen kan worden in de scriptie Delaunay Triangulation in Three Dimensions van T. Fang en L. A. Piegl [5]. Het algoritme kan worden opgedeeld in twee verschillende fases en die fases zal worden gebruikt als stappenplan voor de uitleg. Er zijn ook nog twee methoden die op andere problemen worden losgelaten die ervoor kunnen zorgen dat de tweede stap een stuk efficienter is. De delaunay conditie die er voor zorgt dat er een goede verdeling komt van de triangulatie is 21
De Delaunay conditie is: De som van twee hoeken van twee driehoeken die tegenover elkaar liggen mag niet groter zijn dan 180 graden.
Figuur 6.1: Links een vierkant met alleen de hoekpunten, rechts de mesh met behulp van Delaunay
6.2.1 Voorbereidend werk Voordat de triangulatie kan beginnen zijn er wat standaardwaarden nodig. Namelijk de uiteinden van de pointcloud. Dit houdt in de maximale en minimale waarde van de x, y en z coordinaten. Deze worden bepaald door door alle punten heen te filteren en te onthouden welke de grootste en kleinste waarde zijn. Nadat deze punten geselecteerd zijn, moeten deze waarde aangepast worden. Alle maximale waarden verhogen de waarde met een tolerantie factor en alle minimale waarden verlagen de waarde juist met deze factor. Dit zorgt ervoor dat punten die precies op de rand liggen van de pointcloud ook meegenomen worden. Het delaunay principe werkt met cellen, in deze cellen zitten een aantal punten die dicht bij elkaar liggen. Deze cellen moeten eerst een grote aangewezen krijgen, deze grote wordt bepaald met de volgende formule. r 3 (xmax − xmin)(ymax − ymin)(zmax − zmin) size = (6.1) N Waarbij N het totaal aantal punten in de point cloud is. Om de grote te berekenen per cel in de as richtingen word gebruik gemaakt van de volgende simpele formules. x res y res z res
= = =
⌊ xmax−xmin ⌋+1 size ymax−ymin ⌋+1 ⌊ size ⌋ +1 ⌊ zmax−zmin size
(6.2)
Als deze cellen berekend zijn worden alle punten ingedeeld in de cell die bij dit punt hoort. Dit wordt door een simpele berekening gedaan. cell x cell y cell z i j k
= = = = = = 22
xi −xmin size yi −ymin size zi −zmin size
⌊cell x⌋ ⌊cell y⌋ ⌊cell z⌋
(6.3)
Stop het punt i in de cell met coordinaten (i, j, k) en controlleer eerst of de cell niet leeg is. Is deze leeg stop het punt er in, zo niet controlleer dan of er een punt overeenkomt met het punt i. Als dit het geval is voeg punt i niet toe aan een cell en ga door met het volgende punt in de cloud.
6.2.2 Beginnen met de triangulatie Nadat de punten zijn opgedeeld in de cellen kan er begonnen worden met de triangulatie van de punten. Dit begint bij het middelste punt, P 1, de reden hiervoor is dat dit over het algemeen het efficients bleek en er bijna altijd voor zorgt dat de delaunay conditie niet wordt overtreden. Als deze middelste cell niet leeg is, kan elk punt gebruikt worden. Is deze cel wel leeg, dan moet er in de cellen er omheen gezocht worden tot er een punt gevonden is. Indien dit punt gevonden is wordt er het punt dat hier het dichstebij ligt gezocht, P 2. Deze twee punten vormen de eerste zijkant, om te controleren of dit klopt wordt er gekeken of er een punt ligt in de bol met als diameter P 1P 2, als er een punt in deze bol ligt dan is dat punt P 2. Om het derde punt P 3 te vinden maken we gebruik van de bounding box van de sphere [8] met als diameter P 1P 2. Vind punten die in deze box liggen en selecteer het punt dat op het plane (P 1, P 2, Q), waarin Q een punt is dat veranderd, ligt en de kleinste bol vormt met de overige punten. Bereken van deze sphere de nieuwe bounding box. Herhaal de vorige stap tot dat de nieuwe bounding box helemaal in de oude ligt. Dan is P 3 gevonden en is er een driehoek(P 1, P 2, P 3). Om punt P 4 te vinden die de tetrahedon afmaakt te vinden wordt er gebruik gemaakt van een techniek genaamd range searching.
6.2.3 Range Searching Er zijn verschillende soorten van range searching, in dit hoofdstuk zal uitgelegd gaan worden hoe de tunnel methode werkt van range searching. Begin met de normaal vector te berekenen van de driehoek waarvoor het vierde punt wordt gezocht. Zoek uit in welke richting de normaal vector het snelst groeit. Dit is de zoekrichting die aangenomen gaat worden. Hier wordt een tunnel gevormd, dat betekend dat er in de richting van de normaal vector per cell een tunnel wordt gevormd en de buurcellen die eromheen liggen ook. De cell die precies in het midden ligt vormt alleen een tunnel, de buurcellen delen een tunnel met een andere buurcell, voor verduideleking figuur 6.2. Begin te zoeken in de tunnel die in het midden van de driehoek ligt. Als er in die tunnel punten liggen, zoek dan naar het punt dat een omschrijvende bol heeft die het meeste op de delaunay bol van de driehoek lijkt. Neem van deze bol het selectiekader en zoek in de tunnels die door dit selectiekader geraakt worden naar punten. Als er een punt wordt gevonden dat een omschrijvende bol heeft die beter lijkt op de delaunay bol van de driehoek. Deze zoektocht blijft doorgaan tot dat er in de tunnel geen cellen meer zijn met punten die nog niet gecontroleerd zijn. Het punt dat op dat moment de best omschrijvende bol heeft die het dichts op de delaunay bol lijkt is P 4. Om er voor te zorgen dat de triangulatie goed verloopt word er gebruik gemaakt van een techniek genaamd shelling. 23
Figuur 6.2: Cellen met — om de randen krijgen een tunnel, Bron: [5]
6.2.4 Shelling Een methode om er voor te zorgen dat de triangulatie in goede lijnen geleid wordt is shelling. Shelling zorgt ervoor dat er geen gaten in de triangulatie vallen. Elke driehoek heeft een voorkant en elke driehoek wordt in ´e´en grote zoeklijst opgeslagen. Iedere keer als er een nieuwe tethrahedon gevormd is wordt er een andere driehoek gepakt uit de lijst en wordt er gezocht door middel van range searching naar het vierde punt. Indien dit punt niet gevonden wordt zit deze driehoek aan de rand van het model en wordt van de zoeklijst verwijderd. Als dit punt gevonden wordt, wordt er gecontroleerd of deze al van een bestaande tethrahedon is of een nieuwe vormd. Indien dit punt van een bestaande tethrahedon is worden er verschillende aanrakingen met de nieuwe tethrahedon gedefineerd. Elke keer als er een nieuwe tethrahedon wordt gevormd, worden alle nieuwe zijkanten aan de zoeklijst toegevoegd. Deze methode wordt uitgevoerd tot dat de zoeklijst helemaal leeg is. Tweezijdige aanraking Een tweezijdige aanraking komt voor als er bijvoorbeeld een driehoek A is met punten (a, b, c) en er is een driehoek B(a, b, d). De nieuwe tetrahedon die gevormd word is er eentje met de punten (a, b, c, d) vanuit driehoek A. Deze tetrahedon deelt dus een zijde met driehoek A, want vanuit hier is de zoektocht gestart, maar ook een zijde met driehoek B. Wanneer dit voorkomt worden niet alle zijden aan de zoeklijst toegevoegd maar alleen de zijdes (a, c, d) en (b, c, d). En tegelijkertijd worden allebei de zijdes (a, b, c) en (a, b, d) verwijderd uit de zoeklijst. Tweezijdige aanraking Bij de driezijdige aanraking is het hetzelfde geval als bij een tweezijdige aanraking alleen dan zit er nog een extra tetrahedon tegen aan geplakt. Dus de nieuw gevormde tetrahedon (a, b, c, d) deelt nog een zijkant met de oudere tetrahedonzijde (b, c, d). Nu wordt 24
alleen de zijkant (a, c, d) toevoegd aan de zoeklijst en alle andere drie de zijden worden uit de lijst verwijderd. Lijn en zijkant aanraking Iedere keer als er een tweezijdige aanraking optreedt wordt er ook gecontroleerd of deze niet zorgt voor een gat in de triangulatie. In het voorbeeld wordt er een nieuwe driehoek gevormd door middel van het combineren van de punten (a, b, e). Dit zorgt ervoor dat er een gat ontstaat bij de zijde (a, c, d). Daarom wordt er elke keer als er een tweezijdige aanraking plaats vindt ook een zijkant detectie gedaan. Als dit het geval is dan wordt deze driehoek achteraan de lijst gezet en wordt er een andere driehoek gebruikt om de triangulatie voort te zetten. Om het proces later te versnellen worden wel de punten voor deze tetrahedon die gevormd zou worden bij elkaar bewaard, om later geen range search meer te hoeven te doen.
25
26
HOOFDSTUK 7
Conclusie In dit hoofdstuk zal er per onderdeel worden gekeken naar de resultaten van een paar onafhankelijke tests.
7.1 Kalibratie De kalibratie maakt gebruik van technieken die in het verleden al vaak getest en gebruikt zijn . Om de eigen implementatie te testen is er gebruik gemaakt van een kubus die in het plaatje is geplaats op coordinaten die van voor af aan vast stonden.
Figuur 7.1: De geplaatsde kubus na kalibratie Ook is er gekeken naar de afwijking in de verschillende assen, met behulp van dezelfde kubus. As x y z
Afwijking in 2D pixels per 3D pixel 0.10577 0.15259 1.55864
De afwijkingen zijn te verklaren door middel van het feit dat er gebruik is gemaakt van meerdere plaatjes voor de kalibratie die met een webcam zijn gemaakt en geen hoogwaardige precisie heeft. 27
7.2 Detectie laserlijn In figuur 3.1 zijn de intensiteit waarden te zien van een enkele rij x, y coordinaten. Hierin is goed te zien dat de laserlijn er duidelijk uitspringt op het gebied van de rode intensiteit.
Figuur 7.2: Laserlijn is blauw gekleurd waar de hoogste intensiteit is Het detecteren van punten op de achterwand is duidelijk te zien in figuur 6.2, de groene punten op de laserlijn zijn de punten die gedetecteerd zijn op de achterwand. Met behulp van deze punten worden de total least squares functies bepaald.
Figuur 7.3: Blauwe lijn is de TLS functie Aan het figuur 6.3 te zien is de precisie hoog bij de berekening van de TLS. In figuur 6.3 is ook goed waar te nemen dat de laserlijn af en toe niet helemaal precies is, maar af en toe wat verspreid opgenomen wordt. Dit heeft geen invloed op de bepaling van de laserlijn, want dan wordt over de hele laserlijn de onderste lijn aangehouden.
7.3 Omrekenen punten Om het omrekenen van de punten te testen, wordt er gebruik gemaakt van een object met een locatie die bekend is. In dit plaatje is goed te zien dat de berekeningen qua precisie goed werkt bij een eenvoudig object. 28
Figuur 7.4: Vlak ingescand object met controle lijn, twee rode lijnen liggen qua coordinaten op dezelfde lijn
7.4 Vormen mesh Voor dit project is er gebruik gemaakt van een bibliotheek die al vaak getest is, namelijk Delny [10]. Dus zal hier niet behandeld worden.
7.5 Eindconclusie Het doel van het project was om een 3D desktop scanner te maken die met behulp van een eenvoudige webcam en laserpen een object kon inscannen in de computer in 3D coordinaten. Het detecteren van een laserlijn was de hoofdlijn van het project en zoals in hoofdstuk 6.2 te zien is dit tot een redelijk goede precisie gelukt. De overige onderdelen van het project zijn in de respectievelijke hoofdstukken behandeld en geven een resultaat dat er mag zijn. In deze gescande afbeeldingen is goed te zien dat de scanmethode werkt,
Figuur 7.5: Het model dat is gebruikt voor de scan maar er nog wel foutieve punten die niet op het model zitten weggefilterd moeten worden. Deze foutieve punten worden ook meegenomen in het vormen van de mesh en dit zorgt ervoor dat de resultaten van de scans die gemeshed zijn niet goed zijn. 29
Figuur 7.6: Linksboven: Voorkant, Rechtsboven: Bovenaanzicht, Onder: Zijaanzicht
7.6 Uitbreidingen 7.6.1 Verbeteren huidige systeem In 6.5 wordt geconcludeerd dat er bij het scannen nog punten mee worden gepakt die niet bij het model horen, maar door ruis toch meegenomen worden. Er is dus nog genoeg werk om het systeem te verbeteren op welke punten wel en niet doorgelaten mogen worden. Een ander punt is om andere soorten mesh algoritmen te proberen, in dit project was hier geen tijd voor, maar is nog wel de behoefte aan. Als laatste verbetering aan het huidige systeem is het gebruik van een andere webcam met een hogere scherpe resolutie, dit zorgt ervoor dat de detectie van de laserlijn verbeterd en de berekeningen nauwkeuriger zijn.
7.6.2 Combineren van verschillende meshes Een onderdeel dat nog mist in het systeem is het combineren van verschillende meshes. Het combineren van verschillende meshes zorgt ervoor dat een geheel object ingescand kan worden en een heel 3D object vormt. Een methode dat dit mogelijk kan maken is om het middelpunt van het object te bepalen vanuit de berekende 3D coordinaten. Hierna dit middelpunt te transleren naar de oorsprong van de omgeving. Alle punten dezelfde translatie laten ondergaan en daarna roteren in de juiste gradenhoek. Als deze berekenen zijn gedaan dan weer dezelfde translatie omgekeerd uitvoeren op deze punten. De grootste hindernis hier is om het middelpunt van het object te kunnen vinden met alleen de informatie van de 3D coordinaten.
30
Bibliografie [1] Z. Zhang. A flexible new technique for camera kalibration. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(11):1330-1334, 2000. [2] J. Zobel. Writing for Computer Science, 2nd edition. Springer-Verlag, 2004 [3] D. Lanman and G. Taubin. Build Your Own 3D Scanner: 3D Photograhy for Beginners, SIGGRAPH ’09: ACM SIGGRAPH 2009 courses, 2009 [4] J. Bouguet and P. Perona, Weakly structured lighting, California Institute of Technology, May 1999 [5] T. Fang and L. A. Piegl, Delaunay Triangulation in Three Dimensions, University of South Florida, September 1995 [6] Weisstein, Eric W. ”Least Squares Fitting–Polynomial.”From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/LeastSquaresFittingPolynomial.html [7] P. de Groen, An Introduction to Total Least Squares, Vrije Universiteit Brussel, Nieuw Archief voor Wiskunde, Vierde serie, deel 14, 1996, pp. 237-253. [8] Weisstein, Eric W. ”Circumsphere.”From MathWorld– A Wolfram Web Resource. http://mathworld.wolfram.com/Circumsphere.html [9] R. van den Boomgaard, L. Dorst - PinholeCamera.pdf [10] F. Bruynooghe, http://flub.stuffwillmade.org/delny
31
