De creatie van 3D-computermodellen van objecten uit foto's Ignace Van de Woestyne 1. Inleiding Computervisie is dat domein van de toegepaste wetenschappen waarin methodes en technieken ontwikkeld worden om de computer de inhoud van beeldmateriaal in de ruime zin van het woord te laten “begrijpen” om “interpretatie” mogelijk te maken. Meerbepaald wordt specifieke informatie uit het beeldmateriaal geëxtraheerd en in een computervisie systeem – dit kan een enkel computerprogramma zijn of een opeenvolging van verschillende computeralgoritmes – verwerkt tot voor ons gemakkelijker interpreteerbare vormen. De creatie van 3D-computermodellen is één van de deelproblemen waarover men zich in de computervisie buigt. We leggen eerst enkele begrippen vast. Met een 3D-object bedoelen we een (solide) object in de 3-dimensionale Euclidische ruimte. Een 3D-model is een “oppervlak” in de 3dimensionale Euclidische ruimte. Zowel 3D-objecten als 3D-modellen kunnen gevisualiseerd worden. Hiermee bedoelen we dat er een grafische (vlakke) voorstelling van gemaakt wordt m.b.v. een computer op een “computerscherm”. Om dit te kunnen realiseren zal er een discretisering (sampling) van het 3D-object/model moeten gebeuren. Immers, een computerscherm bestaat maar uit een eindig aantal punten. Verder zal er gebruik moeten gemaakt worden van projectie en kunnen technieken uit het domein van de computer graphics nuttig zijn om een zo realistisch mogelijke visualisatie te bekomen. We denken hierbij aan technieken zoals triangulatie, het verwijderen van niet zichtbare delen, textuurmapping, belichting, … Met 3D-reconstructie bedoelen we de constructie van een (zo realistisch mogelijk) 3D-model van een 3D-object op basis van metingen (opnames) van het 3D-model. Het 3D-model moet zodanig zijn dat metingen uitgevoerd op het 3D-model, overeenstemmen met gelijkaardige metingen die op het 3D-object zouden zijn uitgevoerd. We spreken ook wel van een metrische reconstructie. De metingen die noodzakelijk zijn om het 3D-model te kunnen construeren, kunnen afhankelijk van het toepassingsdomein, afkomstig zijn van manuele metingen, laserscans, PET, CT of MRI-scans, foto’s, video, radar, … of een combinatie. De meetinformatie die bekomen wordt is veelal te beschouwen als “vlakke” 2-dimensionale informatie. Een 3D-reconstructie zal dus gebruik maken van de meetkundige (algebraïsche) relaties tussen de 2-dimensionale ruimte waarin de metingen gesitueerd zijn en de 3-dimensionale ruimte waarin zich het 3D-object bevindt. Er zijn diverse toepassingen van 3D-reconstructie in onze hedendaagse wereld actief. We vermelden er hier enkele als voorbeeld. Deze lijst is zeker niet volledig. In de medische wetenschappen wordt reeds geruime tijd gebruik gemaakt van de medische beeldvorming. Daarbij worden data afkomstig van CT-scanners, PET-scanners, echografie en dergelijke, omgevormd tot beelden die door een arts kunnen geïnterpreteerd en gebruikt worden. Meer recent maakt men op basis van deze data in sommige situaties ook 3D-reconstructies. Op die manier ontstaat een 3D-model dat kan gebruikt worden als bijkomend hulpmiddel bij het vaststellen van diagnoses en het plannen van complexe chirurgische ingrepen. Ook wordt het mogelijk om dergelijke ingrepen op voorhand op basis van het 3D-model te simuleren. Het spreekt voor zich dat medische 3D-modellen ook zeer nuttig zijn bij de opleiding van medisch personeel. In [6] zijn enkele voorbeelden in de sector van de reconstructieve chirurgie te vinden waarbij gebruik gemaakt wordt van 3D-reconstructies. Als tweede toepassingsdomein van 3D-reconstructie vermelden we stedenbouw – ruimtelijke ordening. Voor diverse toepassingen kan het nuttig zijn te beschikken over 3D-modellen van 1
stadsgedeeltes, regio’s en dergelijke. Deze modellen kunnen bijvoorbeeld geconstrueerd worden op basis van luchtfoto’s of satellietopnames. Ze kunnen dan gebruikt worden voor simulaties en controles. Deze techniek is reeds succesvol gebruikt voor het bepalen van geschikte inplantingplaatsen van GSM-antennes, wegen (zoals bijvoorbeeld HST-lijnen), … Tevens kan op basis van de 3D-modellen kadasterinformatie gecontroleerd en aangevuld worden en kunnen op een semi-automatische wijze allerlei kaarten worden gegenereerd. In [2] is bijvoorbeeld een segmentatietechniek beschreven die toelaat om, op basis van een 3D-model van een stedelijk gebied, het grondniveau op een ruwe maar snelle manier te extraheren. Deze output werd dan gebruikt om een parametrisch model van het grondniveau te schatten. Door eerst de ruwe extractie van het grondniveau uit te voeren, werd convergentie nadien driemaal sneller bereikt dan wanneer dit niet gebeurde, met een globale tijdswinst als gevolg. Ook in het domein van de archeologie en het in stand houden van het cultureel erfgoed, worden tegenwoordig 3D-reconstructies gebruikt. Reconstructies van (delen van) historische gebouwen en voorwerpen maken het mogelijk om een beter inzicht te verkrijgen in het verleden. Ook kunnen op basis van deze modellen exacte metingen en simulaties uitgevoerd worden. In [5] is een Europees onderzoeksproject beschreven waarin ondermeer tools voor 3D-reconstructie met archeologische toepassingen worden ontwikkeld. Als laatste vermelden we een toepassing in de amusementsector. Het komt meer en meer voor dat bij de opnames van een speelfilm stunts moeten uitgevoerd worden die zo gevaarlijk zijn of zelfs zo onrealistisch zijn dat ze onmogelijk door echte acteurs of stuntmensen kunnen worden uitgevoerd. Toch behoren dergelijke scènes tegenwoordig tot de mogelijkheden omdat men een vrij nauwkeurig 3D-model kan maken van de acteurs die de scène zouden moeten spelen. Men speelt vervolgens de gehele scène in een virtueel gecreëerde wereld. Dit kan zo realistisch gebeuren dat de toeschouwer nadien, wanneer deze passage gemonteerd is tussen de andere shots, het verschil niet meer merkt. Als voorbeeld waarbij dergelijke techniek gebruikt werd, vermelden we de tweede speelfilm uit de filmtrilogie The Matrix, nl. The Matrix Reloaded. Daarbij werd van sommige acteurs, een realistisch 3D-model gemaakt op basis van een laserscan en vijf cameraopnames. Meer informatie en ook het resultaat is te vinden op de officiële website van The Matrix [8]. 2. Formulering van het te behandelen probleem Zoals we merken, zijn er heel wat interessante toepassingen te vinden van 3D-reconstructie. Het spreekt voor zich dat het verband tussen de doorgaans 2-dimensionale meetinformatie en de 3dimensionale informatie van het te reconstrueren 3D-object, in sterke mate afhangt van de gebruikte opnametechniek. Een CT-scanner bijvoorbeeld die gebruikt wordt voor medische toepassingen maakt een ander soort opnames dan een gewoon fototoestel. Het zou ons te ver leiden om voor alle opnametechnieken de algebraïsche, meetkundige relaties hier te behandelen, zodat we ons beperken tot één deelprobleem. Dit kan samengevat worden met de vraag hoe we op basis van (digitale) foto’s van een 3D-object, genomen vanuit verschillende gezichtspunten, een 3D-model kunnen maken. Voor alle duidelijkheid, er is niet geweten waar de camera zich bevond op het moment van de opname en er is evenmin geweten hoe de camera was ingesteld op het ogenblik van de opnames (bijvoorbeeld zoom, brandpuntsafstand van de lens, camerakarakteristieken, …). Dus het 3D-model mag enkel geconstrueerd worden op basis van informatie die uit de foto’s zelf komt.
2
3. Naar de wiskundige formulering en de oplossing We trachten nu het gestelde probleem te vertalen naar een wiskundig probleem en bekijken dan hoe dit kan opgelost worden. We geven hier enkel in grote lijnen de constructie aan. Voor meer details verwijzen we bijvoorbeeld naar [1] en [3]. 3.1. De projectievergelijkingen De camera die we op het oog hebben is een courante digitale camera, uitgerust met een degelijke lens zodat we kunnen veronderstellen dat beelden ontstaan volgens het principe van een camera obscura. Dit principe is in Figuur 1 (links) geïllustreerd. Hierbij kunnen we het omgekeerde beeld dat zich op de lichtgevoelige sensor vormt door projectie, theoretisch ook vóór de camera beschouwen. Voordeel is dan dat het beeld rechtopstaand is.
X u
0
Z
P (X,Y,Z)
pu (u,v) v Z=1 Y
Figuur 1: (links) Het principe van de camera obscura; (rechts) Het camera gecentreerd assenstelsel. Wanneer we abstractie maken van de camera, merken we duidelijk een projectiemodel, met het brandpunt van de lens als projectiepunt. We voeren nu een camera gecentreerd assenstelsel in (zie Figuur 1 (rechts)). Dit is een orthonormaal assenstelsel waarbij de oorsprong gesitueerd is in het brandpunt van de lens, de X- en Y-as evenwijdig zijn met het projectievlak en de Z-as daar loodrecht op staat. We kiezen de eenheid zodanig dat het projectievlak als vergelijking Z = 1 krijgt. We bekomen dan de projectievergelijking ρpu = P, met ρ een constante en pu en P zoals in Figuur 1 (rechts). We kunnen deze projectievergelijking ook uitdrukken t.o.v. een vast referentiestelsel. Dit is geïllustreerd in Figuur 2. We zien dat de camera verplaatst is t.o.v. de oorsprong volgens een translatievector C. Verder is de oriëntatie gewijzigd. Dit kan uitgedrukt worden m.b.v. een orthogonale matrix R. Van een dergelijke matrix is geweten dat de inverse matrix gelijk is aan de getransponeerde. Dus is R-1 = Rt. De projectievergelijking kan nu herschreven worden als ρpu = Rt(P - C). Digitale camera’s maken een opname via een lichtgevoelige sensor. Deze sensor bestaat uit heel veel lichtgevoelige beeldpuntjes, pixels genaamd, die volgens een welbepaald 2-dimensionaal rooster zijn opgesteld. De oorsprong van dit rooster bevindt zich links bovenaan, in tegenstelling tot wat we in de wiskunde gewoon zijn. Bovendien hoeven de pixels niet vierkant te zijn en hoeven ze ook niet volgens een orthonormaal assenstelsel te zijn opgesteld. Dit betekent dat er dus nog een transformatie moet worden bekeken, nl. die die de coördinaten van het projectiepunt pu omzet in pixelcoördinaten. Algemeen kan het verband tussen beiden in matrixnotatie uitgedrukt worden als 3
p = Kpu, met K de zogenaamde kalibratiematrix. Deze matrix bevat alle technische karakteristieken van de gebruikte camera. X’ u Z’ Z
pu
C
P (X,Y,Z) v
Y’ Y
0
X
Figuur 2: De camera t.o.v. een vast referentiestelsel. Gecombineerd met het voorgaande bekomen we nu als algemene projectievergelijking ρp = KRt(P - C). Hierbij is p eigenlijk het punt pu, maar dan uitgedrukt in pixelcoördinaten. 3.2. De 3D-reconstructie De oplossing van het reconstructieprobleem bestaat er nu in om uit de algemene projectievergelijking P te berekenen indien we p kennen. Om dit te kunnen doen, zullen we eerst de translatiematrix C, de oriëntatiematrix R en de kalibratiematrix K nog moeten berekenen uit de gemaakte opnames. Om dit te kunnen doen, bekijken we eerst het reconstructieprobleem visueel, zoals voorgesteld in Figuur 3. We gaan ervan uit dat we twee opnames hebben, gemaakt vanuit twee verschillende posities. De eerste camerapositie gebruiken we als oorsprong van een vast referentiestelsel. Indien de punten p1 en p2, gesitueerd in de twee opnames en uitgedrukt in pixelcoördinaten, afkomstig zijn van hetzelfde punt P in de ruimte, dan is dit punt als snijpunt van de twee ruimterechten, elk gaande door de camerapositie en het projectiepunt, te berekenen. X u
Vergelijking?
P (X,Y,Z)
Z
u’
p1 0
v Z=1 Y
L1
p2
v’ C Coördinaten?
Epipolaire rechte
Figuur 3: Reconstructie van het punt P, indien twee corresponderende punten p1 en p2 in de twee beelden bekend zijn. 4
In Figuur 3 zien we ook dat het punt p2 dat in het tweede beeld gelegen is en dat overeenkomt met het punt p1 in het eerste beeld, op de rechte L1 gelegen is. Deze rechte, die men de epipolaire rechte van p1 noemt, ontstaat als doorsnede van het projectievlak van de tweede camerapositie en het vlak bepaald door de cameraposities 0 en C en het punt P. Indien we de vergelijking van deze rechte kunnen vinden, dan hoeven we voor het zoeken van corresponderende punten, niet het ganse vlak te doorzoeken, maar volstaat het om enkel te zoeken langsheen de epipolaire rechte. Uit de algemene projectievergelijkingen kan nu vrij eenvoudig (zie bijvoorbeeld [1] en [3]) aangetoond worden dat er een matrix F bestaat zodat voor alle corresponderende punten p1 en p2 in de twee beelden geldt dat p2tFp1 = 0. (1) Hierbij worden p1 en p2 in pixelcoördinaten uitgedrukt als 3-dimensionale kolomvectoren, met als derde coördinaat 1. Dus p1 = (x1, y1, 1)t en p2 = (x2, y2, 1)t. De matrix F noemt men de fundamentele matrix. Deze matrix wordt zo genoemd omdat deze de matrices C, R en K bevat. Indien we het element op de i-de rij en j-de kolom van F voorstellen door fij, dan is (1) te herschrijven als f11x1x2+f12y1x2+f13x2+f21x1y2+f22y1y2+f23y2+f31x1+f32y1+f33 = 0. (2) Deze vergelijking kan nu op drie verschillende manieren bekeken worden. Stel dat p1 bekend is, evenals de fundamentele matrix F. Dan is (1) de vergelijking van de epipolaire rechte waartoe p2 behoort. Op analoge wijze is, indien p2 en F bekend zijn, (1) de vergelijking van de epipolaire rechte waartoe p1 behoort. Indien F niet bekend is, maar wel twee corresponderende punten p1 en p2, dan is (1) een vergelijking waaraan de negen onbekenden fij moeten voldoen. Deze vaststelling geeft ons een mogelijkheid om de fundamentele matrix te berekenen. Het volstaat nu immers om 8 corresponderende punten aan te duiden in de twee beelden. Hierdoor ontstaat een homogeen stelsel van 8 vergelijkingen in 9 onbekenden. Een dergelijk stelsel heeft een van nul verschillende oplossing die op een constante na bepaald is. Deze techniek om de fundamentele matrix te berekenen staat bekend als het “8-punt algoritme”. Eens de fundamentele matrix bekend is, kan de epipolaire rechte eenvoudig worden berekend, zoals aangegeven, zodat het zoeken van corresponderende punten nu beperkt wordt tot deze rechte. Uiteraard blijven er heel wat corresponderende punten te zoeken indien een nauwkeurige reconstructie moet worden bekomen. Daarom is het onbegonnen werk om die correspondenties manueel te gaan zoeken. We hebben dus nood aan een automatische procedure. Daarvoor nemen we onze toevlucht tot de statistiek. Vooreerst zullen we de twee beelden, die meestal kleurenbeelden zijn, omzetten naar zwart-wit beelden. Er blijkt immers dat deze beelden, die eenvoudiger zijn dan de kleurenbeelden, voldoende informatie bevatten om corresponderende punten te zoeken. Elke pixel in een zwart-wit beeld heeft een bepaalde grijswaarde, ter grootte van één byte. Wanneer de waarde nul is, is de pixel zwart, terwijl de waarde 255 overeenkomt met een witte pixel. Neem nu een pixel p1 in het eerste beeld en een pixel p2 op de epipolaire rechte van p1 in het tweede beeld. Rond die pixels situeren we een vierkante omgeving, waarvan de dimensies even groot zijn en waarbij de punten p1 en p2 in het midden liggen. Bereken nu voor de grijswaarden in die twee omgevingen de correlatie. Herhaal dit voor de overige punten op de epipolaire rechte. Het punt waarvoor de correlatie het grootste is, zullen we als matchpunt weerhouden. We gaan er immers van uit dat de omgeving rond gecorreleerde punten gelijkaardig is. De correlatie zal daarvoor groter zijn. Natuurlijk zullen we af en toe een verkeerde match weerhouden, zodat nadien “opkuistechnieken” zullen moeten worden toegepast om die er zoveel als mogelijk uit te halen. In Figuur 4 wordt het zoeken van corresponderende punten geïllustreerd.
5
p1
p2
Figuur 4: Het zoeken van het corresponderende punt langsheen de epipolaire rechte, gebaseerd op correlatie. Er rest ons nog om de matrices C, R en K te bepalen uit de fundamentele matrix. Hier moeten we echter vaststellen dat dit met slechts twee beelden wiskundig onmogelijk is aangezien er teveel onbekenden zijn (zie bijvoorbeeld [3]). Het initieel gestelde reconstructieprobleem is dus wiskundig onoplosbaar, tenzij men naar meerdere beelden gaat (minstens 3) of bijkomende gegevens i.v.m. de camera heeft. Om het probleem niet ingewikkelder te maken hebben we geopteerd voor het laatste. De huidige digitale camera’s bewaren bij elke opname ook cameragegevens in de zogenaamde EXIF-header. Daarin wordt bijvoorbeeld het type camera opgenomen, wat handig is om de fysische karakteristieken van de gebruikte lichtgevoelige sensor te achterhalen (bijvoorbeeld de afmetingen van één lichtgevoelige pixel) en de brandpuntsafstand van de gebruikte lens. Op basis van deze informatie kan de brandpuntsafstand in pixeleenheden worden uitgedrukt. We veronderstellen bovendien dat de pixels vierkant van vorm zijn en in een orthogonaal rooster zijn opgesteld. Moderne beeldsensoren voldoen effectief aan deze veronderstellingen. Gebruik makend van deze bijkomende informatie wordt het dan wel mogelijk om uit de fundamentele matrix F de vereiste resultaten te halen. We verwijzen voor meer details opnieuw naar [3]. 4. Van de wiskundige oplossing naar een praktische applicatie 4.1. Mogelijke moeilijkheden Indien we de wiskundige oplossing die we bekomen hebben, praktisch willen implementeren, dan worden we met een aantal problemen geconfronteerd. Vooreerst zijn er de basisproblemen die we in de afleiding hiervoor reeds opmerkten, nl. het bepalen van de positie en oriëntatie van de camera bij de tweede opname t.o.v. de eerste (op basis van de fundamentele matrix) en het zoeken van corresponderende punten. In het voorgaande hebben we deze problemen reeds aangepakt. Verder worden we geconfronteerd met moeilijkheden van meer praktische aard. Er zijn de problemen die numeriek van aard zijn. Ten gevolge van fouten (ondermeer omdat pixelcoördinaten geheel zijn) zullen er rekenfouten zitten op de berekende fundamentele matrix. Hierdoor zullen er afwijkingen zitten op de positie van de camera en de oriëntatie, waardoor er onnauwkeurigheden optreden in de reconstructie. Zo zullen de ruimterechten die elkaar theoretisch moeten snijden in het gereconstrueerde punt, elkaar mogelijk niet snijden maar kruisen. Toch verwachten we een snijpunt. Deze eventuele onnauwkeurigheden in de reconstructie zullen we nadien door smoothingtechnieken toe te passen, zoveel als mogelijk reduceren. Verder worden we ook geconfronteerd met visualisatieproblemen waarvoor het domein van computer graphics mogelijk een oplossing heeft. De reconstructietechniek die hierboven beschreven 6
wordt, leidt immers tot een puntenwolk in een 3-dimensionale ruimte. Wanneer deze puntenwolk dicht genoeg is, kunnen we de indruk van een oppervlak bekomen. Eventueel zullen we tussen de punten van deze puntenwolk driehoekjes moeten plaatsen om op die manier de indruk te krijgen van een gevuld oppervlak. Dit kan gebeuren met een zogenaamde Delaunay triangulatie. Het bekomen oppervlak kan bovendien bekleed worden met één van de oorspronkelijke opnames om een realistisch 3D-model te bekomen. Door belichting toe te voegen verhogen we het realiteitsgehalte van het 3D-model. 4.2 Een praktische implementatie: het softwaresysteem ReconLab Op basis van de voorgaande theorie werd aan de K.U.Brussel door de auteur het softwaresysteem ReconLab ontwikkeld als opvolger van het reeds eerder ontwikkelde programma Epipool. Van dit laatste is nog een versie verkrijgbaar op de website Topics uit wiskunde en economie [9]. Volg hierbij de links ‘wiskundige topics’ en ‘3d-reconstructie’. ReconLab is ontwikkeld als een 3D modelleer- en editeeromgeving. Er kunnen 3D-modellen geconstrueerd worden op basis van twee digitale foto’s volgens de methode die hiervoor werd beschreven. Verder heeft ReconLab nog een aantal bijkomende mogelijkheden, die we hier niet zullen beschrijven. We verwijzen daarvoor naar [3]. ReconLab is bovendien interactief/automatisch te gebruiken en beschikt over editeermogelijkheden in alle stadia van het “productieproces”. Het is zodanig ontwikkeld dat het van dezelfde broncode kan worden gecompileerd voor gebruik op zowel het MS Windows als het Linux platform. Voor geïnteresseerden wordt er gratis een lite-versie ter beschikking gesteld via de website [7]. Daar is eveneens meer informatie te bekomen over het gebruik van de software. De lite-versie bezit voldoende functionaliteit om tot zeer redelijke reconstructies te komen. Om dit te illustreren zullen we in het volgende onderdeel een 3D-reconstructie in enkele stappen realiseren. 5. Een stap voor stap 3D-reconstructie met ReconLab Het programma ReconLab is opgebouwd uit de drie onderdelen “2d-environment”, “3denvironment” en “Model”, elk ondergebracht in een afzonderlijk tabblad. We werken normaal gezien door deze tabbladen in deze volgorde, alhoewel het soms wel eens nuttig kan zijn om reeds vroeger een overstap te maken. Ten allen tijde kan er heen en weer geschakeld worden tussen de tabbladen. Stap 1: Het tabblad “2d-environment” We starten door twee verschillende foto’s van een object op te roepen. Dit gebeurt met de knoppen “Open” bij de twee vensters. ReconLab kan werken met beelden met een resolutie van maximaal ongeveer 3 megapixel. Voor dit voorbeeld gebruiken we de volgende beelden van een schelp. Ze zijn in werkelijkheid elk ongeveer 2 megapixel groot.
Figuur 5: De beelden waarvan de reconstructie zal gebeuren. 7
Vervolgens moeten er minstens 8 corresponderende punten in de twee beelden worden aangeduid. Uit het voorgaande weten we dat 8 voldoende is, maar om meer stabiele resultaten te krijgen is het aangewezen om er meer te nemen (bijvoorbeeld 15, wat ook de standaardinstelling is in ReconLab). Het aantal basispunten is te wijzigen in het optiemenu. Best neemt men de basispunten zo verspreid mogelijk over het te modeleren object. Indien mogelijk, kunnen ook enkele punten in de omgevende ruimte geselecteerd worden. Het aanduiden van de punten moet zeer nauwkeurig gebeuren want een afwijking van 1 pixel kan al aanleiding geven tot slechte reconstructies. Best is om hierbij gebruik te maken van het “zoomvenster”, dat opgeroepen wordt via de zoomknop in de knoppenbalk. Er verschijnen dan rode, verplaatsbare vensters in de twee beelden, die als vergrootglas fungeren. Om punten te kunnen selecteren moet eerst het klikgedrag van de muis worden aangepast, door de corresponderende knop in de knoppenbalk te activeren. Daarna kiest men een volgnummer in de knoppenbalk en klikt men de punten aan in de beide beelden. De pixelcoördinaten worden automatisch opgenomen. Wanneer alle basispunten zijn opgegeven, kan de fundamentele matrix F worden berekend, door de corresponderende knop op de knoppenbalk aan te klikken. De epipolaire lijn wordt nu in het tweede beeld zichtbaar door het verschuiven van de muispijl over het eerste beeld. Onderaan ziet men ook de zogenaamde Sampsonfout weergegeven. Die geeft een indicatie over de geldigheid van de geselecteerde punten. Als vuistregel kan men stellen dat indien deze waarde groter is dan 10, er beter andere punten worden geselecteerd of de selectie nauwkeuriger moet gebeuren. In ons voorbeeld is de Sampsonfout afgerond 1.1, dus zeer acceptabel. Vervolgens gaan we een regelmatig rooster plaatsen over het eerste beeld, waarbij we voor elke pixel uit het rooster, het corresponderende punt automatisch laten berekenen langsheen de corresponderende epipolaire rechte, zoals eerder is aangegeven. De afstand tussen de roosterpunten kan via het optiemenu worden aangepast en staat standaard ingesteld op 5. We werken met de standaardinstelling. Dit impliceert voor ons voorbeeld een rooster van 60000 pixelpunten. We activeren deze zoekactie door op de corresponderende knop uit de knoppenbalk te klikken. Dit proces kan naargelang de snelheid van de processor en het aantal punten enige tijd in beslag nemen. De progressie ziet men rechts onderaan in beeld. In ons voorbeeld duurt dit ongeveer 1 minuut. Stap 2: Het tabblad “3d-environment” Eens de corresponderende punten gevonden zijn, kan naar het volgende tabblad “3d-environment” overgestapt worden. Dit is het tabblad waarin de eigenlijke 3d-reconstructie zal uitgevoerd worden. We merken dat de EXIF-header van de jpeg-beelden reeds werd gelezen om hieruit de brandpuntsafstand (focal length) van de gebruikte lens te halen. Deze wordt omgerekend naar pixeleenheden, op basis van de grootte van de lichtgevoelige sensor, die afgeleid wordt uit het type camera. De reconstructie zelf gaat nu eenvoudig door op de knop “Reconstruction” te klikken. In het grafiekvenster rechts wordt de gereconstrueerde puntenwolk gevisualiseerd. We merken op dat er in totaal steeds vier mogelijke reconstructies zijn. Eén daarvan is echter de goede. Proefondervindelijk kan eenvoudig worden vastgesteld welke de juiste is. Verder vermelden we dat de vier reconstructies gepaard voorkomen. Reconstructies 1 en 3 zijn elkaars spiegelbeeld, evenals 2 en 4. Deze wetenschap vereenvoudigt de selectie van het juiste reconstructiemodel aanzienlijk. In het grafiekvenster kunnen de assen verplaatst en geroteerd worden. Dit laatste gebeurt door te slepen in het vereenvoudigd model links bovenaan in beeld. Verder zijn er editeermogelijkheden 8
aanwezig want zoals we merken en zoals te verwachten was, zijn er een aantal verkeerde matches die aanleiding geven tot fout gepositioneerde punten. In Figuur 6 is te zien waartoe de ruwe reconstructie zonder enig opkuiswerk leidt. Hierin zijn de schelp en het grondvlak waarop die ligt reeds duidelijk te zien maar de “rondslingerende” punten moeten nog worden verwijderd.
Figuur 6: Een eerste ruwe reconstructie. Een handige tool om die verkeerd geplaatste punten te verwijderen is te vinden in het Smoothingvenster. Dit wordt geactiveerd via een knop in de knoppenbalk. Dan selecteren we de techniek genaamd “Isolated Point Removal”. Deze eenvoudige techniek construeert een sfeer rond elk 3dpunt en telt hoeveel gereconstrueerde punten in die sfeer gelegen zijn. Indien dit aantal lager is dan een bepaalde drempel, dan wordt het punt als geïsoleerd beschouwd en wordt het verwijderd. Zoniet, dan blijft het staan. De redenering is dat verkeerd geplaatste punten eerder willekeurig verspreid zullen voorkomen dan in clusters. De ervaring leert dat dit doorgaans het geval is. Hoe klein de straal van de sfeer moet genomen worden, evenals de drempel, is kwestie van wat experimenteren. Begin hierbij best met een kleine straal, want hoe kleiner de straal, hoe sneller de methode. Echter een te kleine straal zal ervoor zorgen dat alle punten als geïsoleerd worden aanzien en dus allen zullen verwijderd worden. De undo-mogelijkheid is dan handig om een stap terug te gaan en de straal aan te passen. In ons voorbeeld stellen we de straal in op 0.02 en de drempel op 4. Dit levert het resultaat op zoals in Figuur 7 te zien is.
Figuur 7: (links) De ruwe reconstructie; (rechts) De reconstructie na Isolated Point Removal. 9
Heel wat geïsoleerde punten zijn effectief verdwenen. Een aantal punten liggen echter toch nog te dicht bij elkaar zodat die de filter passeren. Deze punten kunnen nu gemakkelijk manueel weggeknipt worden m.b.v. de beschikbare hulpmiddelen, aanwezig in de knoppenbalk. Eén ervan is het verwijderen of behouden van punten die binnen een geselecteerde polygoon liggen. Het gebruik van die mogelijkheid leidt tot het resultaat in Figuur 8.
Figuur 8: (links) Tekenen van polygoon rond het te behouden gebied; (rechts) Het resultaat. We kunnen eventueel verscholen geïsoleerde punten verwijderen door eerst de reconstructie te bekijken vanuit een ander gezichtspunt en dan opnieuw een polygoon te tekenen. Het programma zal immers 3d-punten behouden/verwijderen die zich in projectie binnen de polygoon bevinden. Na een weinig knipwerk bekomen we reeds een zeer treffelijke reconstructie zoals we in Figuur 9 kunnen vaststellen.
Figuur 9: De reconstructie als puntenwolk na het verwijderen van geïsoleerde punten. Dit is het moment waarop eventueel reeds naar het derde tabblad kan gegaan worden om de reconstructie als puntenwolk te visualiseren. Dit is trouwens wat we deden om de voorgaande figuur te produceren. Indien een reconstructie als puntenwolk voldoende is, is de reconstructie in deze fase doorgaans beëindigd. Het spreekt voor zich dat, hoe meer punten er oorspronkelijk
10
genomen werden in het rooster, hoe meer gereconstrueerde punten er zijn en hoe dichter en nauwkeuriger het resultaat zal zijn. Indien we een triangulatie wensen, d.w.z. tussen de punten van de gereconstrueerde puntenwolk driehoekjes willen plaatsen om een opgevuld oppervlak te bekomen, dan dienen we de optie “Preview” onderaan het tabblad uit te schakelen. Naargelang het aantal punten kan het eventjes duren vooraleer het effect zichtbaar wordt. In Figuur 10 (links) zien we het effect op de reconstructie van de schelp, waarbij via de opties verkozen werd om in te kleuren volgens de hoogte met een belichtingseffect. We merken op die manier in deze visualisatie het effect van kleine afwijkingen in de reconstructie. Om die weg te werken passen we een smoothingtechniek toe die bekend staat als Inverse Distance Weighting. Hierbij wordt de z-coördinaat van elk 3d-punt vervangen door een gewogen gemiddelde van de z-coördinaten van naburige punten. De gewichten worden kleiner naarmate de afstand tot het punt waarvoor de berekening uitgevoerd wordt, groter is. Vandaar ook de gebruikte benaming. Het effect van een dergelijke smoothing is te zien in Figuur 10 (rechts). Hierbij werd de straal ingesteld op 0.02 om het effect van de smoothing te beperken. De structuur van het eigenlijke object komt nu meer duidelijk tot uiting.
Figuur 10: (links) Triangulatie van de 3d-punten; (rechts) Het effect van smoothing. Stap 3: Het tabblad “Model”. We vermeldden dit tabblad reeds eventjes in het voorgaande deel. Op het ogenblik dat de 3Dreconstructie gerealiseerd is in het tweede tabblad, kan naar het derde tabblad gegaan worden om een gepaste visualisatie te selecteren en het model voor te stellen in een overeenkomstige browser. Er kan gekozen worden voor een VRML-model. VRML staat voor Virtual Reality Modeling Language, een taal die speciaal ontworpen is voor het beschrijven van modellen in een 3dimensionale ruimte. Deze modellen kunnen ook gemakkelijk op het internet gepubliceerd worden aangezien VRML een internetstandaard is. Men heeft wel een specifieke browser nodig zoals bijvoorbeeld de Cortona VRML Client, die te downloaden is vanaf [4]. Die maakt het mogelijk om een VRML-model te openen via de gebruikelijke webbrowser. Bij de VRML-modellen is er de keuze tussen een puntmodel, een solide model ingekleurd volgens het kleurpatroon dat in het tweede tabblad werd ingesteld en een textuurmodel, waarbij de eerste foto als textuur “gekleefd” wordt bovenop het 3D-model. In Figuur 11 zien we voorbeelden van de laatste twee mogelijkheden.
11
Figuur 11: (links) VRML-model ingekleurd volgens hoogte; (rechts) VRML-textuurmodel. Aangezien een VRML-puntmodel als nadeel heeft dat de dikte van de punten niet kan worden gewijzigd of ingesteld, heeft de auteur een eigen viewer geschreven die gebruik maakt van OpenGL. Deze viewer, PointViewer3d genaamd, waarin de dikte van de punten kan worden gewijzigd, is ook beschikbaar via [7]. ReconLab kan output genereren die met deze viewer kan worden gevisualiseerd. 6. Conclusie In deze publicatie hebben we na enkele inleidende begrippen ingevoerd te hebben, 3D-reconstructie gesitueerd in een ruim toepassingsdomein. In het bijzonder is dan 3D-reconstructie op basis van twee foto’s meer gedetailleerd behandeld. Dit probleem is eerst wiskundig vertaald en in enkele stappen is een indicatie gegeven hoe het kan worden opgelost, evenwel met de vaststelling dat bijkomende informatie noodzakelijk is om tot een metrische reconstructie te komen. Vervolgens hebben we aan de hand van het programma ReconLab stap voor stap een reconstructie uitgevoerd. We vermelden hierbij nog dat niet alle mogelijkheden van het programma hier aan bod konden komen. ReconLab is bovendien “work in progress”. Er zullen ongetwijfeld nog verfijningen en vernieuwingen aan de software worden aangebracht. Bibliografie 1. T. Moons en I. Van de Woestyne, Van ruimtemeetkunde tot virtuele realiteit, Website Topics uit wiskunde en economie, http://www.kubrussel.ac.be/WSetew/download/reconstructie2001.pdf. 2. I. Van de Woestyne, M. Jordan, T. Moons en M. Cord, A software system for efficient DEM segmentation and DTM estimation in complex urban areas, Proc. of ISPRS Congress 2004, Istanbul, (2004), Vol. XXXV, Part B, 134-139. 3. I. Van de Woestyne en T. Moons, A software system for creating 3D-computer models from photographic images, Kragujevac Journal of Mathematics, Vol 28 (2005), 19-40. 4. Officiële website van Cortona VRML Client, http://www.parallelgraphics.com. 5. Officiële website van EPOCH (European Research Network on Excellence in Processing Open Cultural Heritage), http://www.epoch-net.org/. 6. Officiële website van National Center for Biocomputation, http://biocomp.stanford.edu/. 7. Officiële website van ReconLab, http://www.cmmc.be/reconlab/. 8. Officiële website van The Matrix Trilogy, http://whatisthematrix.warnerbros.com/. 9. Officiële website Topics uit wiskunde en economie, http://www.kubrussel.ac.be/WSetew/. Ignace Van de Woestyne Katholieke Universiteit Brussel, faculteit ETEW, Vrijheidslaan 17, B-1081 Brussel. E-mail:
[email protected] 12
