Automatische planextractie uit 3D fotogrammetrie Mathieu Theerens 23 mei 2013
ii
Voorwoord Vooraleer we starten met deze thesis wil ik eerst nog enkele personen en Thomas More Campus De nayer bedanken voor hun hulp bij het opstellen van deze thesis. Eerst zou ik Toon Goedemé willen bedanken voor zijn steun en advies bij deze thesis. Daarnaast wil ik ook mijn familie bedanken voor hun steun.
iv Abstract (Nederlands)
Deze thesis is een onderdeel van het project 3D4SURE door de onderzoeksgroep EAVISE, dit project onderzoekt de mogelijkheden van 3D fotogrammetrie voor landmeters. In deze thesis gaan we onderzoeken of het mogelijk is om met behulp van 3D fotogrammetrie automatisch een 3D model te maken van een gebouw. Dit model kan worden gebruikt door een landmeter en het enige wat hij moet doen om het op te stellen is foto's trekken van een gebouw, aangezien het programma geen andere invoer vereist. Het 3D model wordt gemaakt in AutoCAD maar we werken eerst met een tussenstap namelijk een puntenwolk. Deze puntenwolk moet ons helpen de belangrijke punten te bepalen van het gebouw en met deze punten kunnen we het 3D model in AutoCAD maken. De puntenwolk wordt gemaakt met behulp van het programma Bundler, deze neemt als input een set van foto's en geeft als resultaat een puntenwolk en ook informatie over de transformatie van 2D (foto's) naar 3D (puntenwolk). De gegenereerde puntenwolk bevat nog vele ruispunten en extra bewerkingen zijn vereist om de belangrijke punten te kunnen identi ceren in de puntenwolk. We gaan namelijk lijndetectie toepassen op de foto's en deze gedetecteerde lijnen projecteren van 2D naar 3D met behulp van de informatie verkregen van Bundler. De lijndetectie gebeurt in OpenCV, welke een gratis bibliotheek is voor C++. Deze bevat al enkele functies die randen en lijnen detecteren in foto's welke we kunnen gebruiken. Voor onze thesis hebben we de Progressive Probabilistic Hough Transformation gekozen als onze lijndetector. Hij maakt gebruik van Canny om de randen te detecteren en past dan de Hough transformatie toe om in de randen lijnen te detecteren. Eens alle lijnen gevonden zijn gaan we per foto de gedetecteerde lijnen projecteren naar de puntenwolk. Hiervoor gebruiken we PCL, welke ook een gratis bibliotheek is voor C++ die speci ek over werken met puntenwolken gaat. Voor de projectie hebben we de rotatie, translatie en de intrinsieke matrices nodig van elke foto. Deze krijgen we allemaal van Bundler en het enigste dat we bijgevolg moeten doen is de juist formule berekenen om deze transformatie uit te voeren. Tijdens de projectie gaan we punten in de puntenwolk votes geven, namelijk elk punt dat dichtbij een berekende projectie ligt krijgt een vote. Alle punten die aan het eind van de projectiestap meer votes hebben dan een bepaalde threshold worden onze punten voor het 3D model in AutoCAD. We hebben deze stappen allemaal geschreven in C++ aangezien de functies die we nodig hadden in C++ bibliotheken zaten. We zijn resultaten bekomen voor elke stap, echter was de lijndetectie niet van voldoende kwaliteit zodat de rest van de stappen hier ook nadeel van ondervonden. De lijndetectie gaf namelijk 2 grote fouten, het detecteerde maar delen van lijnen en de verhouding ruislijnen tot goede lijnen was veel te hoog. Hierdoor was het algemene 3D model in AutoCAD van slechte kwaliteit. Een oplossing voor het probleem is een andere lijndetector implementeren, maar er was geen andere betere te vinden online en er was te weinig tijd om er zelf nog één te schrijven.
v Abstract (English)
This thesis is a part of the project 3D4SURE by the research group EAVISE, this project researches the possibilties of 3D photogrammetry for surveyors. In this thesis we're going to research whether it's possible to use 3D photogrammetry in order to automatically create a 3D model of a building which can by used by a surveyor, and the only thing he had to do is taking pictures of said building. The 3D model is made in AutoCAD but we work with a pointcloud to obtain the points needed to create the 3D model in AutoCAD. This pointcloud is made using the program Bundler, this program takes a set of pictures as input and gives a pointcloud as result as well as information about the transformation between 2D (pictures) and 3D (pointcloud). However, the generated pointcloud still contains a lot of noise and extra processing is needed to identify the important points of the pointcloud. What we're going to do is perform line detection on the pictures and then we're going to project these detected lines on the pointcloud using the information of Bundler. The linedetection takes place in OpenCV which is a free library for C++, it already contains some functions about edge detection and line detection which we can use. For our thesis we've chosen the Progressive Probabilistic Hough Transformation as our line detection method, it uses Canny to detect the edges in the pictures and then applies the Hough transformation to detect the lines in these edges. Once all the lines are found we're going to project the detected lines for each picture to the pointcloud. We use PCL for the projection, since PCL is a free C++ library that is made speci cally to make working with pointclouds easier. For the projection we need the rotation, translation and the intrinsic matrices of each picture, but we already got that from Bundler and the only thing we need to do is work out the right formula to do this transformation. During the projection we're going to give the points in the pointcloud votes, each point that is close to a calculated projection gets a vote. Every point that has more votes than a certain threshold gets selected as point for the 3D model in AutoCAD. We have written all these steps in C++ as all the functions we need are from C++ libraries. We've obtained results for each step, however the line detection was not of su cient quality which caused the rest of the steps to get bad results as well. The line detection gave 2 big errors, one was that it detected only parts of the lines and the other one was that there were too many noiselines in comparison to the good lines. Because of this the nal 3D model in AutoCAD was of bad quality. A solution for the problem is to implement another linedetector, but we couldn't nd another better one online and there was too little time left to actually write one ourselves.
vi
Short Summary Introduction
In this thesis we're going to research whether it's possible to create a 3D model of a building in AutoCAD using 3D photogrammetry. The thesis is part of the project 3D4SURE by the research group EAVISE, in this project the possibilities of 3D photogrammetry for surveyors are being researched. At the moment surveyors make a plan of a building using a 'total station', this takes quite some time and work. Therefore we would like to replace this method with 3D photogrammetry, the only thing the surveyor needs to do then is taking pictures of all the sides of the building. Afterwards he uploads the pictures to the computer and runs our program. This would take a lot less time than having to measure everything with the total station. The program itself consists of a few steps, rst the pictures are used to create a 3D pointcloud of the building. However, this pointcloud contains a lot of noise and we will need to nd a way to work around this noise. That's why for the next step we'll put aside the pointcloud for a moment and use the pictures to detect all the possible lines. These lines would give us in the ideal situation the structure of the building and after we've found them we'll then project them on the pointcloud using the extrinsic and intrinsic matrices of each picture. These matrices give information about the camera and the position of each picture in the scéne, we need this information in order to do the transformation between 2D (pictures) and 3D (pointcloud). During this projection we will vote points, with this we mean that we're going to give a point of the pointcloud a vote if they are close to the calculated projection. After this step is complete we'll have a few dozen points with a votecount higher than a chosen threshold and we'll then use these points to make the actual model in AutoCAD.
Creating the pointcloud
To create the pointcloud we can use SFM (Structure From Motion) programs found online, SFM means that we take pictures while moving and we create a structure (pointcloud) of these pictures. For this thesis we will use Bundler as SFM program as it is well documented and is easy to use. To get a decent pointcloud, pictures have to be taken every 15◦ of the building, ofcourse more pictures can be taken to increase the detail of the pointcloud. Once Bundler is complete it will generate said pointcloud and also a projection matrix, which contains the extrinsic and intrinsic matrices of the pictures, which we use for the projection. Something to note about the pointcloud is that the ground of the building
viii doesn't start at Z-coordinate 0, since Bundler has no way to tell which points represent the ground. For that same reason it may be that the building is slightly rotated, so that the coordinate system isn't pointing exactly at the front of the building.
Line detection
Since we're going to program in C++ we can use the free library OpenCV, which is used for image processing. In OpenCV there are already 2 line detectors that we can use, namely the Standard Hough Transform (SHT) and the Progressive Probabilistic Hough Transform (PPHT). Since the PPHT outputs the lines as [beginpoint, endpoint] we'll use this one instead of the SHT. First we're going to detect all the edges in the pictures, for this there are 3 functions in OpenCV: Canny, Sobel and Laplace. All 3 do a decent job of nding the edges, but for Hough Canny is the best one since it creates edges of 1 pixel thick. To detect the edges Canny calculates the gradient of every pixel and those with a gradient higher than a given threshold are edge points. On these edge points we'll then apply the Hough transform, which means that we're going to transform the points from the XY plane to the Hough plane. Every point in the XY plane becomes a sine in the Hough plane and every point in the Hough plane is a line in the XY plane. Once all the points are transformed to the Hough plane we'll look for the intersections of the dierent sines, because these intersections represent the lines in the XY plane. The fact that Canny creates edges of 1 pixel thick means that we have a lot less points to transform, which is better.
Line projection
After all the lines are detected we have to project them on the pointcloud, to do this we need a calibration model which says how the transformation between 2D and 3D is done. There are 2 common calibration models, the one of Hartley and Zisserman and the one of Tsai. Both de ne the transformation but Hartley and Zisserman's model doesn't work with distortion and Tsai's model does. Distortion is the fact that points in a picture will get a slightly altered position than their expected one due to the lens of the camera. Because we want an accurate 3D model in AutoCAD we must try to use the most accurate method in every step, but we also are bound on the calibration model that Bundler uses to do the transformation. Luckily Bundler uses a calibration model that is only slightly dierent from Tsai's model and also takes account of distortion. We had to use this calibration model to compute a formula which we can use to calculate the 3D points of the detected lines. Unfortunately a point in 2D doesn't correspond to exactly one point in 3D, instead it corresponds to a whole line in 3D since we don't know anything about the depth of that point. But as said in the introduction we'll solve this problem by giving points votes, each point of the pointcloud that is within a certain distance to such a 3D line gets a vote. At the end the points with the most votes will be written to a le and normally those points should represent the important points of the building, such as the cornerpoints.
ix Construction 3D model AutoCAD
The last step of the line projection was writing the 3D points to a le. All we have to do in AutoCAD is to drag the le we've written into the AutoCAD window, because the le doesn't only contain the points, it's actually a script which contains commands that AutoCAD can use. However, once we have all the points in AutoCAD we still have to give all the points a global rotation since the building might be rotated as said previously. This rotation is dierent for each pointcloud as it is dependent on the pictures and we haven't found out how to caculate it exactly so the surveyor has to do this after the program has run. Results
We've written code for each step and we've become results for all of them, but we've found out that our implementation of the line detection doesn't give good results. The Hough detector we use gives 2 great errors, one is that only parts of a line are detected and the other error is that we get a lot of lines which aren't really important, or in other words noise. This noise came especially from tiles of the roof and from trees in the garden of the building. The fact that when we do the projection we expect the detected lines to be good, means that our projection step will also contain errors. We don't test if the input lines are good, we just project them and determine which of these lines are detected the most. Ofcourse, if our projection isn't good then our nal 3D model in AutoCAD won't be good either. Everything is dependent on the line detector, so in order to get good results, we have to nd another line detector. Unfortunately we didn't nd the code of another better line detector online and we didn't have enough time left to create our own line detector. Conclusion
When trying to create a 3D model of a building in AutoCAD using only pictures there are several ways to do so. Our method was using a pointcloud (created by the pictures) as temporary workspace, in which we detect the important points of the building. We try to determine which points are important and which are not using line detection on the pictures and then projecting those lines onto the pointcloud. At the end of the projection we know the points that represent our building and we export them to AutoCAD to create a 3D model. Unfortunately the quality of the 3D model in AutoCAD was not high enough, there were too few points and not all points were good (as in, represented an important part of the building). This was due to the line detection giving bad results, what happened was that only parts of the lines were detected and that there was a lot of noise. The solution was to nd a better line detector, but we couldn't nd the code of a better line detector online nor did we have enough time left to create one ourselves. All in all it should be possible to create a 3D model of a building given that the line detector is good.
x
Inhoudsopgave 1 Inleiding 1.1 1.2 1.3 1.4 1.5
Situering . . . . . . . . . . Aanpak . . . . . . . . . . Doelstellingen . . . . . . . Conclusie . . . . . . . . . Organisatie van deze tekst
1 . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
2 Literatuurstudie 2.1 Fotogrammetrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Omzetting foto's naar puntenwolk . . . . . . . . . . . . . . . . . . 2.2.1 Arc3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Catch 123D . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 VisualSFM . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Bundler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.5 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Lijndetectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Randdetectie . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Hough transformatie . . . . . . . . . . . . . . . . . . . . . 2.3.3 Verschil PPHT en SHT . . . . . . . . . . . . . . . . . . . . 2.3.4 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Projectie van 2D lijnen in foto's naar 3D in het puntenwolkmodel 2.4.1 Hartley en Zisserman . . . . . . . . . . . . . . . . . . . . . 2.4.1.1 Intrinsieke matrix . . . . . . . . . . . . . . . . . . 2.4.1.2 Extrinsieke matrices . . . . . . . . . . . . . . . . 2.4.1.3 Projectie matrix . . . . . . . . . . . . . . . . . . 2.4.1.4 Conclusie Hartley en Zisserman . . . . . . . . . .
1 2 3 4 5
7 . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
7 9 9 10 10 10 10 10 11 12 13 14 14 15 15 16 18 19
xii
INHOUDSOPGAVE 2.4.2 Tsai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.2.1 Conclusie Tsai . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.3 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Overzicht van de uitwerking
23
4 Omzetting foto's naar puntenwolk
25
4.1 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5 Lijndetectie
27
5.1 Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6 Projectie naar 3D 6.1 6.2 6.3 6.4
Bundler's cameramodel . . . Berekening formule projectie Probleem projectie . . . . . Conclusie . . . . . . . . . .
30 . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
30 31 33 33
7 Constructie 3D model AutoCAD
35
8 Resultaten
36
8.1 8.2 8.3 8.4 8.5
Omzetting naar puntenwolk . . . Lijndetectie . . . . . . . . . . . . Projectie . . . . . . . . . . . . . . Constructie 3D model AutoCAD Ander voorbeeld . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
37 39 42 44 46
9 Besluit
50
Bibliogra e
51
L¼st van guren 1.1 Een tachymeter, het toestel waarmee een landmeter het gebouw gaat opmeten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Dit is een voorbeeld van hoe het uiteindelijke resultaat van deze thesis eruit zou moeten zien, een 3D model dat de structuur van het gebouw weergeeft.
2
1.3 Links staat de puntenwolk waarvan de ruis wegge lterd is, rechts staat een puntenwolk met nog veel ruispunten in. . . . . . . . . . . . . . . . . . . . .
3
1.4 De projectie van 2D naar 3D. De foto's bestaan uit een lijn, waarvan men het begin en eindpunt gaat projecteren. Deze punten komen niet overeen met juist 1 punt in 3D maar vormen een lijn in 3D. . . . . . . . . . . . . .
4
2.1 Het linkse deel is de puntenwolk met de referentiepunten aangeduid, het rechtse deel is de originele foto. . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2 Mogelijke input en output van fotogrammetrie. . . . . . . . . . . . . . . . .
9
2.3 Het resultaat van randdetectie op een beeld, links staat het originele beeld, rechts het resultaat van de randdetectie op de foto. . . . . . . . . . . . . . 11 2.4 Voorstelling van een lijn met r, θ. . . . . . . . . . . . . . . . . . . . . . . . 12 2.5 Mapping van het (x,y) vlak naar het (r, θ) vlak. . . . . . . . . . . . . . . . 13 2.6 Skew bij een beeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.7 Rotatie en translatie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.8 Rotatie rond de z-as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.9 Lens distorsie, links barrel distortion, rechts pincushion. . . . . . . . . . . . 20 3.1 Het overzicht van alle stappen die doorlopen worden in deze thesis. . . . . 24 4.1 Het verkregen resultaat van Bundler met de bijhorende posities van waaruit elke foto getrokken is. Dit model is gemaakt met 60 foto's, maar allemaal getrokken vanuit het oosten van het gebouw. . . . . . . . . . . . . . . . . . 25 4.2 Hier ziet men 2 foto's met de positie van de bijhorende camera's en het assenstelsel van Bundler dat als Y-niveau 0 het midden heeft van de lijn. . 26
xiv
LST VAN FIGUREN
5.1 Output van het lijndetectie programma, rechts is de originele foto. Hier wordt een redelijk hoge threshold gebruikt voor Canny, hierdoor heeft men weinig ruislijnen, maar als gevolg ook weinig lijnen in totaal. . . . . . . . . 28 5.2 Output van het lijndetectie programma, rechts is de originele foto. Hier wordt een lagere threshold gebruikt dan de foto hierboven, men heeft nu meer lijnen in het algemeen, maar bijgevolg ook meer ruislijnen. . . . . . . 28 6.1 Projectie van hetzelfde punt in 2 foto's naar 3D. Punt A heeft nu 2 votes. . 34 7.1 Een voorbeeld van het nale model na alle stappen te doorlopen. . . . . . 35 8.1 Het gebouw dat we gebruiken als test voor de thesis. . . . . . . . . . . . . 8.2 De puntenwolk die gegenereerd werd van het gebouw. De groene, blauwe en rode lijn vormen het assenstelsel. De blauwe lijn is de Z-as, de groene de Y-as en de rode de X-as. . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 De puntenwolk die gegenereerd werd van het gebouw. . . . . . . . . . . . . 8.4 Fout bij de lijndetectie, er wordt maar een deel van de lijn gedetecteerd, wat resulteerd in fouten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 De lijndetectie die maar delen van de lijnen detecteerd in plaats van de hele lijn, zoals te zien bij de ramen en deuren. . . . . . . . . . . . . . . . . . . . 8.6 De lijndetectie die te veel ruis oplevert. . . . . . . . . . . . . . . . . . . . . 8.7 De projectie uitgevoerd op het gebouw. . . . . . . . . . . . . . . . . . . . . 8.8 Het model gecreëerd met AutoCAD met als vergelijking een foto van het gebouw. Zoals men ziet zijn er te veel punten geprojecteerd zodat het niet echt duidelijk is welk punt waar zit op de foto. . . . . . . . . . . . . . . . . 8.9 De puntenwolk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.10 Een ander aanzicht van de puntenwolk. . . . . . . . . . . . . . . . . . . . . 8.11 De lijndetectie die hier al veel beter werkt dan in het vorige voorbeeld, bijna elka belangrijke lijn wordt volledig gedetecteerd. . . . . . . . . . . . . 8.12 Nog een voorbeeld van de lijndetectie. . . . . . . . . . . . . . . . . . . . . . 8.13 De projecties op de puntenwolk. . . . . . . . . . . . . . . . . . . . . . . . . 8.14 Een ander aanzicht van de projecties. . . . . . . . . . . . . . . . . . . . . . 8.15 Het AutoCAD model, men ziet hier al duidelijker waar elk punt zit op de foto. Het raam en één van de twee garagas worden ook getoond in het model. Het is al een grote verbetering van het vorige model. . . . . . . . .
36 37 38 40 41 41 43 45 46 46 47 47 48 48 49
Hoofdstuk 1 Inleiding 1.1
Situering
Eenvoudig gezegd is het doel van deze thesis het onderzoeken of we door middel van foto's een plan kunnen opstellen van een gebouw, wat kan gebruikt worden door landmeters. Want één van de vele taken van een landmeter op dit moment is het opstellen van een topogra sch plan van een gebouw, waarvoor hij een tachymeter gebruikt (ook wel 'total station' genoemd). Een voorbeeld hiervan vindt men in foto 1.1. Figuur 1.1:
Een tachymeter, het toestel waarmee een landmeter het gebouw gaat opmeten.
Dit opmeten met een tachymeter kost echter vrij veel tijd aangezien men voor elk hoekpunt van het gebouw een meting moet doen. Daarom is men op zoek naar nieuwe snellere manieren om deze metingen te doen waarbij men de tachymeter niet meer nodig heeft. In deze thesis gaan we onderzoeken of het mogelijk is om dit werk te doen door middel van 3D fotogrammetrie, waarbij men een 3D-model genereert uit een hoop digitale beelden. Fotogrammetrie is het bepalen van de vorm en locatie van objecten en gebieden met behulp van foto's. Het wordt tegenwoordig gebruikt in vele vakgebieden zoals chirurgie, biologie, forensisch onderzoek, civiele techniek en natuurlijk de architectuur en bouwtechniek. De fotogrammetrie die wij gaan gebruiken heet Multiple View Geometry, hierbij wordt automatisch een model gegenereerd op basis van de foto's die getrokken zijn, er is
2
Inleiding
geen hulp vereist van de gebruiker. Men gaat namelijk kenmerken detecteren in elke foto, ook wel features genoemd, deze kenmerken bevatten informatie over de kleurenovergang en de uniekheid van een punt. Wanneer elke foto maar lichtjes verschilt van de vorige foto, zullen vaak dezelfde features gedetecteerd worden en door deze features met elkaar te vergelijken kan zo hetzelfde punt in verschillende foto's teruggevonden worden. Door informatie te gebruiken in verband met de positie van elke camera in de 3D scéne kunnen we zo een 3D model genereren. Dit model is echter niet zuiver, het bevat nog vele ruispunten van bijvoorbeeld de omgeving en schaduwen of re ecties. Maar het uiteindelijke resultaat zou een zuiver en nauwkeurig 3D AutoCAD model moeten zijn, wat het plan voorstelt. Een voorbeeld van hoe zo'n AutoCAD model er zou moeten uitzien is te zien in guur 1.2. Figuur 1.2:
Dit is een voorbeeld van hoe het uiteindelijke resultaat van deze thesis eruit zou moeten zien, een 3D model dat de structuur van het gebouw weergeeft.
Het werken met fotogrammetrie zou het werk van een landmeter vele malen vereenvoudigen, omdat het nemen van foto's veel vlugger gebeurt dan opmetingen met de tachymeter. We moeten wel zorgen dat de fotogrammetrie methode even accuraat is als de methode met de tachymeter en moeten daarom bij elke stap van de thesis streven naar een zo nauwkeurig mogelijke oplossing. Zoals hierboven al aangegeven heeft fotogrammetrie echter ook een nadeel namelijk informatie-overvloed, dit is bijvoorbeeld te zien in guur 1.3. De verschillende foto's gaan een 3D puntenwolk genereren die tienduizenden punten kan bevatten, deze zijn natuurlijk niet allemaal goede punten. Hoe we deze ruis gaan oplossen bespreken we in 1.2.
1.2
Aanpak
Om een zuiver beeld te krijgen van het gebouw gaan we eerst een deel buiten de puntenwolk werken, we gaan namelijk eerst de foto's verder analyseren met als doel al de rechte lijnstukken in elke foto te detecteren. Deze lijnen geven in het ideale geval perfect
1.3 Doelstellingen Figuur 1.3:
3
Links staat de puntenwolk waarvan de ruis wegge lterd is, rechts staat een puntenwolk met nog veel ruispunten in.
de structuur van het gebouw weer, zoals bijvoorbeeld de lijnen van guur 1.2. We kunnen dan door deze lijnen te gebruiken in de puntenwolk zeggen welke punten belangrijk zijn en welke niet. Een alternatief is binnen de puntenwolk blijven en door middel van RANSAC de lijnen gaan bepalen in de puntenwolk. Maar als men binnen de puntenwolk blijft doet men eigenlijk niets met de foto's en aangezien we deze extra informatiebron hebben is het beter om deze ook te gebruiken. Het is ook zo dat er op de foto's weinig ruis is in verhouding tot de ruis in de puntenwolk, waardoor de lijndetectie op de foto's betere resultaten zou moeten geven dan de lijndetectie in de puntenwolk. Als we deze gedetecteerde lijnen willen gebruiken moeten we ze op één of andere manier in de puntenwolk zien te krijgen, wat we gaan doen is de lijnen projecteren van 2D (foto) naar 3D (puntenwolk). Elk lijnstuk heeft een begin en eindpunt en deze punten kunnen we door middel van een formule omvormen van 2D naar 3D. We kijken dan welk punt van de puntenwolk hiermee overeenkomt en negeren zo als het ware de ruis omdat deze niet geprojecteerd zal worden. Een voorbeeld om het principe van projectie beter te begrijpen is te vinden in guur 1.4. Eens de projectie gedaan is zullen er een honderdtal punten overblijven en deze kunnen we dan ingeven in AutoCAD voor het zuiver 3D model. Een alternatief hiervoor zou zijn dat we de foto's op elkaar gaan leggen, met de nodige rotatie en translatie en dat we kijken welke lijnen steeds terugkomen in de verschillende foto's. Men heeft dan minder lijnen die men moet projecteren en men zou ook minder ruislijnen hebben, maar een nadeel hiervan is dat het veel moeilijker is om de verschillende foto's te roteren en transleren en dus op elkaar te leggen. Om deze reden hebben we niet voor deze methode gekozen.
1.3
Doelstellingen
In deze thesis gaan we proberen het antwoord te vinden op enkele onderzoeksvragen, de voornaamste is natuurlijk: • Hoe kunnen we een nauwkeurig 3D model (.dxf) van een gebouw generen in Auto-
4
Inleiding CAD met behulp van foto's?
Men kan deze vraag niet ineens oplossen, met moet ze opsplitsen in enkele deelvragen: • Hoe kunnen we een ruw model verkrijgen van het gebouw op de computer, wat we
gaan gebruiken als basis voor de rest van de thesis?
Dit model heeft echter heel veel ruispunten (zoals te zien was op guur 1.3) en is dus zeker niet bruikbaar als naal resultaat. Hierdoor ontstaat de vraag: • Hoe kunnen we ondanks de vele ruispunten toch een nauwkeurig beeld krijgen van
het gebouw?
En als laatste vraag is er: • Als we de omlijning hebben van het gebouw in de puntenwolk, hoe zetten we dit
dan om naar een plan?
Figuur 1.4:
1.4
De projectie van 2D naar 3D. De foto's bestaan uit een lijn, waarvan men het begin en eindpunt gaat projecteren. Deze punten komen niet overeen met juist 1 punt in 3D maar vormen een lijn in 3D.
Conclusie
Bij het opstellen van een topogra sch plan gaat een landmeter meestal gebruik maken van een tachymeter, dit is echter veel werk en tijdsrovend. Daarom gaan we in deze
1.5 Organisatie van deze tekst
5
thesis onderzoeken of het mogelijk is om dit werk te vergemakkelijken en te versnellen door gebruik te maken van 3D fotogrammetrie. De landmeter moet dan niet meer alles opmeten met een tachymeter, maar moet enkel nog maar foto's nemen van het gebouw en de software doet de rest. De thesis kan opgesplitst worden in enkele stappen die doorlopen moeten worden. Eerst zullen we de genomen foto's van het gebouw moeten omzetten naar een 3D model, namelijk een puntenwolk. Daarna gaan we de foto's verder analyseren door de verschillende lijnen in de foto's detecteren. Deze lijnen worden geprojecteerd op de puntenwolk en men kan zo de ruis uit de puntenwolk verwijderen, want alles wat niet op de lijnen ligt hebben we niet nodig. We verkrijgen hierdoor een aantal lijnen in de puntenwolk die de structuur van het gebouw weergeven, en met deze 3D lijnen kunnen we een AutoCAD model maken. 1.5
Organisatie van deze tekst
Het vervolg van de masterproeftekst is als volgt opgebouwd: Eerst volgt een literatuurstudie in hoofdstuk 2 waarin wordt onderzocht welke technieken we moeten gebruiken om deze masterproef op te lossen. Daarna volgt de uitwerking van de masterproef in hoofdstuk 3, 4, 5, 6 en 7. Daarna volgt een overzicht van onze resultaten die we verkregen op een set van gebouwen in 8. En tot slot is er het besluit van de thesis in hoofdstuk 9.
6
Inleiding
Hoofdstuk 2 Literatuurstudie Aangezien we nu goed weten wat de doelstellingen zijn van deze thesis is het best eerst eens na te gaan of er al dingen bestaan die we kunnen gebruiken voor deze thesis. Met name gaan we kijken naar wat er al te vinden is over 3D fotogrammetrie in de literatuur. We beginnen de literatuurstudie met het uitleggen wat fotogrammetrie juist is in sectie 2.1, daarna gaan we in sectie 2.2 kijken hoe we de foto's kunnen omzetten in een ruw model, met nog vele ruispunten. In sectie 2.3 gaan we het lijndetectie algoritme uitleggen en in de rest van de literatuurstudie wordt de transformatie van 2D naar 3D uitgelegd en dit kan men vinden in sectie 2.4.
2.1
Fotogrammetrie
Zoals in de inleiding gezegd is fotogrammetrie de techniek om met foto's de locatie, vorm en afmetingen van een object of gebied te bepalen. Er zijn 2 soorten fotogrammetrie, namelijk terrestrische fotogrammetrie en aerofotogrammetrie. Bij terrestrische fotogrammetrie gaat men foto's nemen vanop de grond, terwijl bij aerofotogrammetrie men foto's gaat nemen vanuit een vliegtuig. Terrestrische wordt vooral gebruikt om 3D modellen te creëeren van bijvoorbeeld gebouwen, terwijl aerofotogrammetrie meer gebruikt wordt om een gebied in kaart te brengen. Wij gaan voor deze thesis foto's nemen vanop de grond, dichtbij het gebouw dus doen we aan terrestrische fotogrammetrie. Men heeft zowel manuele 3D fotogrammetrie als automatische 3D fotogrammetrie. Bij de manuele fotogrammetrie gaat men zelf referentiepunten aanduiden in al de verschillende foto's. Van deze referentiepunten weet men de positie in de wereld en ze duiden steeds dezelfde punten aan, maar dan in verschillende foto's. Wanneer men ook de lenseigenschappen en de positie van de camera weet kan men hieruit een 3D model genereren door de verschillende punten te gaan matchen met elkaar. Een voorbeeld hiervan is te vinden in guur 2.1. Naast de manuele fotogrammetrie is er dus ook de automatische fotogrammetrie, oftewel Multiple View Geometry. Deze gebruiken we in deze thesis en is al in de inleiding besproken, maar voor de volledigheid gaan we hier nog eens uitleggen wat Multiple View Geometry is. Het 3D model gaat hier zonder tussenkomst van een persoon gegenereerd
8
Literatuurstudie
worden. Men heeft geen referentiepunten meer nodig, het gebeurt automatisch aan de hand van features. Deze features zijn belangrijke punten in een foto, punten die uniek zijn omwille van kleurovergang en contrast. Aangezien elke foto maar lichtjes verschillend was van de vorige foto worden vaak dezelfde features gedetecteerd in de foto's. Als men aan feature matching gaat doen, dan kan men zo weten van waaruit elke foto getrokken is en kan men het 3D model genereren. Maar met fotogrammetrie kan men meer dan alleen de 3D positie van punten bepalen op de foto's. Op guur 2.2 ziet men wat de input en output kan zijn van fotogrammetrie. Elke lijn met aan beide kanten een pijlpunt kan zowel input als output zijn, men kan zoals hierboven uitgelegd de 3D positie verkrijgen, maar men kan ook de 2D positie op de foto verkrijgen van een object. Daarnaast kan men ook de positie van de camera in de wereld verkrijgen en tot slot kan men ook de eigenschappen van de camera zelf verkrijgen, zoals de focale lengte en schalingsfactoren. Fotogrammetrie wordt gebruikt wanneer snel goede meetgegevens van een bestaand object nodig zijn, wanneer men grote complexe objecten of gebieden heeft die moeilijk op te meten zijn kan fotogrammetrie veel tijd besparen.
Figuur 2.1:
Het linkse deel is de puntenwolk met de referentiepunten aangeduid, het rechtse deel is de originele foto.
2.2 Omzetting foto's naar puntenwolk Figuur 2.2:
2.2
9
Mogelijke input en output van fotogrammetrie.
Omzetting foto's naar puntenwolk
De eerste stap die we moeten uitvoeren is, zoals uitgelegd in de doelstellingen, het creëren van een 3D model door middel van foto's, dit wordt ook wel Structure From Motion(SFM) genoemd. Hiervoor bestaan echter al programma's die dit zonder problemen doen. We moeten dus zelf geen code gaan schrijven maar kunnen een reeds bestaand programma hiervoor gebruiken. Men kan kiezen uit een hele lijst van deze programma's, maar diegene die wij gaan bespreken zijn: • Arc3D • Catch 123D • VisualSFM • Bundler
2.2.1
Arc3D
Arc3D is een webgebaseerd SFM programma dat gemaakt is door Van Gool en Tingdahl [9]. Eens men de foto's genomen heeft van het object waarvan men een 3D model zou willen creëren, kan men deze doorsturen naar de servers van Arc3D. Op deze servers gebeurt de omzetting naar een 3D model en wanneer deze omzetting klaar is wordt de output teruggestuurd naar de gebruiker. Het voordeel van Arc3D is dat er veel informatie is over welk camera model er gebruikt wordt, wat belangrijk is voor een latere stap in de thesis, namelijk de projectie van 2D naar 3D. Het nadeel van Arc3D is dat men niet direct de output heeft, maar dat men moet wachten tot deze output ook eectief teruggestuurd wordt naar de pc. Als men niet direct een antwoord nodig heeft, dan is Arc3D geen probleem.
10 2.2.2
Literatuurstudie Catch 123D
Catch 123D is het SFM programma van AutoDesk. Het heeft zowel een webgebaseerde versie, die bijna gelijk is aan die van Arc3D, als een versie op de PC zelf. Het nadeel van Catch 123D is dat er bijna geen informatie gegeven wordt over het camera model, waardoor het niet erg nuttig is voor deze thesis. 2.2.3
VisualSFM
Dan heeft men nog VisualSFM [16] [3] [17], dit is een SFM programma dat geschreven werd door Changchang Wu. Het is computer gebaseerd en geeft een meer gra sche weergave van alle stappen die doorlopen worden. Ook bij VisualSFM krijgt men informatie over het camera model dat gebruikt is, wat een voordeel is. Maar een nadeel is dat de output, dus de puntenwolk, geroteerd is en getransleerd is. Hierdoor moet men eerst nog de output aanpassen voordat men ermee kan werken. Dit is extra werk en kan voor problemen zorgen. 2.2.4
Bundler
Als laatste is er nog Bundler [11] [12], een SFM programma geschreven door Noah Snavely, welke de beste resultaten gaf van alle programma's. Het is niet webgebaseerd, waardoor men niet moet wachten op de upload van foto's en het terugsturen van de output, en de output is niet geroteerd of getransleerd zoals bij VisualSFM. Ook hier weer krijgt men informatie over het camera model dat gebruikt werd. Hierdoor zal Bundler het meeste geschikt zijn voor deze thesis als SFM programma. 2.2.5
Conclusie
In deze thesis gaan we Bundler gebruiken als SFM programma, aangezien het een cliënt gebaseerd programma is en het voldoende informatie geeft over het camera systeem dat het gebruikt om de omzetting van 2D naar 3D te doen. Daarboven is het ook nog vrij eenvoudig te gebruiken en kan men via andere programma's zoals PMVS en CMVS een dichtere puntenwolk creëren met de output van Bundler. 2.3
Lijndetectie
Om een zuiver beeld te krijgen van het gebouw gaan we eerst een deel buiten de puntenwolk werken, we gaan namelijk eerst de foto's verder analyseren met als doel al de rechte lijnstukken in elke foto te detecteren. Deze lijnen geven in het ideale geval perfect de structuur van het gebouw weer en kunnen we gebruiken om te zeggen welke punten in de puntenwolk ruis zijn en welke niet. Een alternatief is binnen de puntenwolk blijven en door middel van RANSAC de lijnen gaan bepalen in de puntenwolk. Maar als men binnen de puntenwolk blijft doet men eigenlijk niets met de foto's en aangezien we
2.3 Lijndetectie
11
deze extra informatiebron hebben is het beter om deze ook te gebruiken. Het is ook zo dat er op de foto's weinig ruis is in verhouding tot de ruis in de puntenwolk, waardoor de lijndetectie op de foto's betere resultaten zal geven dan de lijndetectie in de puntenwolk. Nadat we de foto's hebben gebruikt om een puntenwolkmodel te creëren, gaan we de foto's hergebruiken om alle mogelijke lijnen te detecteren van het gebouw. Er zijn tal van algoritmes die lijnen gaan detecteren in foto's, welke bijna allemaal gebaseert zijn op de Hough transformatie. Aangezien wij gaan programmeren in OpenCV zijn we gelimiteerd tot wat er in deze bibliotheek zit van algoritmes, voor lijndetectie zijn dit er 2: de Standard Hough Transform (SHT) [14] en de Progressive Probabilistic Hough Transform (PPHT) [1]. Beide algoritmen maken gebruik van randdetectie en een transformatie naar het Hough vlak, hieronder volgt een uitleg over deze twee. 2.3.1
Randdetectie
De eerste stap in lijndetectie algoritmes is randdetectie, men gaat de randen van objecten opsporen en als uitkomst een zwart-wit foto genereren zoals weergegeven in foto 2.3. Een witte pixel stelt een rand voor en alles wat geen rand is wordt voorgesteld door een zwarte pixel. De witte pixels kan men gebruiken voor de volgende stappen, met name de Hough transformatie, maar meer informatie daarover in sectie 2.3.2. De randdetectie is belangrijk omdat we na deze stap alle overbodige pixels weggooien uit de foto, aangezien men enkel in de randen van objecten lijnen vindt, niet in de platte vlakken. Figuur 2.3:
Het resultaat van randdetectie op een beeld, links staat het originele beeld, rechts het resultaat van de randdetectie op de foto.
Men heeft verschillende soorten randdetectors, één van de meest bekende en meest gebruikte is waarschijnlijk die van Canny. Daarnaast heeft men ook nog die van Sobel, Laplace en nog vele anderen, maar enkel deze zitten al in OpenCV. Op basis van een studie [6] is gebleken dat de Canny Edge Detector geprefereerd wordt boven de andere detectoren omdat deze continue randen geeft met een dikte van één pixel. Dit is zeer gunstig voor onze masterproef aangezien we een zo nauwkeurig mogelijke oplossing willen hebben. We gaan niet dieper in op de werking van de Canny edge detector, meer infor-
12
Literatuurstudie
matie over Canny vindt men in referentie [2]. De Canny Edge Detector wordt gebruikt als randdetectie voor SHT en PPHT in OpenCV. 2.3.2
Hough transformatie
Nadat we de randen gedetecteerd hebben, is de volgende stap het zoeken naar een manier om de rechte lijnstukken gemakkelijk te kunnen de niëren. We hebben dit namelijk nodig indien we willen achterhalen tot welke lijn een punt in de foto behoort. Dit is mogelijk via een transformatie waarbij men de punten in een (x,y) vlak gaat omzetten naar punten in een ander vlak. Bij PPHT en SHT gaan we de lijnen transformeren met de Hough transformatie [7], welke zegt dat een lijn kan voorgesteld worden als een vergelijking met 2 parameters. Zo heeft men bijvoorbeeld: y = ax + b
(2.1)
Hierin is a de richtingscoë cient en b de oset waar de lijn de Y-as snijdt. Echter kan men met deze voorstelling geen verticale lijnen voorstellen, aangezien de richtingscoe cient en de oset dan beiden naar oneindig zouden gaan. Daarom gebruikt Hough een andere voorstelling: r = xcosθ + ysinθ
(2.2)
Waarbij r de afstand is van de oorsprong tot de lijn en θ de hoek is tussen de X-as en r, zoals te zien is op guur 2.4. Alle lijnen kunnen voorgesteld worden als θ ∈ [0,180] en r ∈ R. Figuur 2.4:
Voorstelling van een lijn met r, θ.
Men kan bijgevolg het Hough vlak opstellen, waarbij men 2 dimensies heeft (r, θ). Een lijn in het (x,y) vlak wordt een punt in het (r, θ) vlak, en een punt in het (x,y) vlak komt overeen met een sinusoidale curve in het Hough vlak [14]. Deze mapping is voorgesteld in guur 2.5.
2.3 Lijndetectie
13
Om lijnen te detecteren, gaat men voor elk punt afzonderlijk deze mapping doen en kijkt men waar de intersecties zijn in het Hough vlak. Deze intersecties stellen lijnen voor in het (x,y) vlak en door de inverse transformatie kan men te weten komen waar deze lijnen liggen in het (x,y) vlak. Figuur 2.5:
2.3.3
Mapping van het (x,y) vlak naar het (r, θ) vlak.
Verschil PPHT en SHT
Zoals eerder gezegd maken beide algoritmes gebruik van zowel de randdetectie als de transformatie naar het Hough vlak, het verschil ligt echter in hoeveel punten er getransformeerd worden naar het Hough vlak. Als men elk punt dat men verkrijgt bij de randdetectie gaat omzetten naar het Hough vlak, dan spreekt men van de SHT. Dit kan echter wat tijd kosten, aangezien zelfs na de randdetectie er nog steeds veel punten overblijven. Daarom probeert men bij PPHT dit te versnellen door maar een klein deel van deze punten te transformeren. Welke punten gekozen worden, wordt hieronder uitgelegd: 1. Kies één willekeurig punt uit de randpunten, indien er geen meer zijn stopt het algoritme. 2. Voer de Hough transformatie uit voor dit gekozen punt en verhoog de accumulator daar waar het nodig is. Het verhogen van de waardes noemt men het stemmen van een punt. 1
3. Verwijder het gekozen punt uit de foto met randpunten. 4. Kijk of er al ergens in de accumulator een waarde is die hoger is dan de threshold waarde. Zo niet, ga terug naar stap 1.
2
5. Doe de inverse Hough transformatie en vindt het langste segment dat men verkrijgt als men deze lijn afgaat in de foto met randpunten. Dit segment is ofwel een continue 1 Een
accumalator is eigenlijk een digitale voorstelling van het Hough vlak, in de vorm van een 2-
dimensionale array. Elke cel in de array stelt een deel van het Hough vlak voor.
2 Door
de quantizatie van het Hough vlak, en door ruis kan de accumulator op verkeerde plaatsen een
hoge waarde verkrijgen. Om dit tegen te gaan maakt men gebruik van een threshold waarde.
14
Literatuurstudie lijn, ofwel een lijn met een kleine opening in dat niet groter is dan een bepaalde threshold. 6. Verwijder al de randpunten die op dit segment liggen uit de foto met randpunten. 7. Verwijder de stemmen van de punten die op de lijn liggen. Dit wilt zeggen dat men de accumulatorwaardes terug gaat verlagen. 8. Als het lijn segment groter is dan de minimale lengte voor een lijn (deze legt men op voorhand vast), voeg de lijn toe aan het output bestand. 9. Ga terug naar stap 1.
2.3.4
Conclusie
Aangezien we een keuze moeten maken tussen de 2 algoritmes gaan we voor deze thesis PPHT gebruiken omdat PPHT sneller is en bijna dezelfde resultaten levert als SHT [4]. Nog een voordeel van PPHT is dat in OpenCV deze als resultaat de begin en eindpunten geeft voor elke lijn die gevonden wordt. Dit in tegenstelling tot SHT in OpenCV, die de parameters van het Hough vlak terug geeft (r, θ). Als we al meteen de begin en eindpunten van een lijn hebben is dit gemakkelijker voor het volgende deel, de projectie van 2D naar 3D. 2.4
Pro jectie van 2D lijnen in foto's naar 3D in het puntenwolkmodel
Nadat we de lijnen gedetecteerd hebben in de foto's moeten we deze lijnen gaan projecteren naar de 3D puntenwolk. Een probleem hierbij is dat een foto werkt met 2D (x,y) en de puntenwolk met 3D (x,y,z), we missen dus de z-dimensie oftewel de diepte [10]. (Referentie [10] verwijst naar een thesis van EAVISE waarin men een vereenvoudigd model van een persoon in 3D gaat reconstrueren door middel van camera's die rond de persoon staan. Hiervoor moest men ook de projectie doen van 2D naar 3D, het enige verschil is dat ze een ander calibratiemodel gebruikt hebben dan in deze thesis. Voor meer informatie rond hoe men een vereenvoudigd model kan maken van een persoon, kan deze thesistekst gelezen worden.) Deze extra dimensie kan men niet zomaar verkijgen uit de foto, we gaan ze in deze thesis verkrijgen door middel van trial en error. Men gaat namelijk 2 vergelijkingen opstellen, één voor de X-component en één voor de Y-component, welke beiden in functie van Z geschreven worden. Z is dan de vrijheidsgraad in beide vergelijkingen en als men Z verhoogt of verlaagt zullen de X- en de Y-component ook veranderen. Uiteindelijk zullen we dan de juiste (x,y,z) combinatie verkrijgen en hebben we ons 2D punt omgevormt naar een 3D punt. We kunnen echter niet meteen beginnen met het opstellen van deze vergelijkingen, we hebben eerst meer informatie nodig over wat de relatie is tussen de foto en de scène in
2.4 Projectie van 2D lijnen in foto's naar 3D in het puntenwolkmodel
15
de wereld. Aangezien we de foto's nemen met een gewoon fototoestel moeten we eerst de interne parameters van dit toestel weten te vinden. Deze parameters bepalen hoe een fototoestel de omzetting doet van 3D naar 2D en men kan deze parameters bepalen door de camera te calibreren. Op dit moment zijn er 2 calibratiemodellen die veel gebruikt worden, namelijk het model van Hartley en Zisserman [13] en het model van Tsai [15]. Eerst zullen we hieronder het model van Hartley en Zisserman uitleggen en daarna het model van Tsai.
2.4.1
Hartley en Zisserman
Het calibratiemodel van Hartley en Zisserman maakt gebruik van een projectiematrix [10], deze bevat alle mogelijke informatie over de camera. Met deze projectiematrix kan men dan gemakkelijk de punten omzetten van 3D naar 2D en omgekeerd. De projectiematrix kan opgedeeld worden in 2 aparte matrices, een intrinsieke matrix en een extrinsieke matrix. De intrinsieke matrix geeft informatie over camera speci eke dingen, zoals de focale lengte. Deze intrinsieke matrix moet men daarom telkens opnieuw berekenen indien men van camera verandert, maar kan telkens herbruikt worden indien men steeds dezelfde camera gebruikt (tenzij de zoom van de camera veranderd wordt, want dan verandert ook de focale lengte van de lens). Dan heeft men nog de extrinsieke matrices, deze geven informatie over de positie van de camera ten opzichte van het wereldassenstelsel. Extrinsieke matrices zijn niet camera afhankelijk, maar zullen afhankelijk zijn van de positie waarin de fotograaf zich bevindt. Dit wilt zeggen dat men dezelfde extrinsieke matrices krijgt, indien men met verschillende camera's op dezelfde plaats een foto neemt. We zullen eerst beginnen met de intrinsieke matrix uit te leggen en daarna de extrinsieke.
2.4.1.1 Intrinsieke matrix Deze matrix A geeft, zoals hierboven beschreven, informatie over camera speci eke dingen en heeft de vorm: a A= 0 0
s a 0
x
y
u u 1 x
y
(2.3)
Met • a , a de schaalfactor voor de x en de y-richting, welke berekend worden met de x
y
formule
(2.4) a = fk (2.5) Hierin is f de focale lengte van de camera en k is een camera speci eke parameter met als eenheid [pixels/lengte] die kan berekend worden door a = fk
k=
x
x
y
y
resolutie f ilmsize
(2.6)
16
Literatuurstudie • u , u de x- en y-component van het principal point. Meestal is dit gelijk aan het x
y
middenpunt van het beeld, maar bij sommige camera's is dit anders.
• s de skew factor, die aangeeft of er een helling is tussen de X en de Y as van het
beeld. s wordt berekend door volgende formule: s = tan(θ)
(2.7)
Tegenwoordig is deze skew factor bij de meeste camera's echter verwaarloosbaar klein [10]. Een voorbeeld van een foto met skew groter dan 0 vindt men in guur 2.6. Figuur 2.6:
Skew bij een beeld
2.4.1.2 Extrinsieke matrices Men heeft 2 soorten extrinsieke matrices, een rotatiematrix R en een translatiematrix T. Een voorbeeld van zo'n translatie en rotatie van het assenstelsel vindt men in guur 2.7. De rotatiematrix geeft de rotatie van de camera ten opzichte van het wereldassenstelsel. Men heeft 3 soorten rotaties, een rotatie rond de X-as, één rond de Y-as, en één rond de z-as. Elke rotatierichting heeft een 3x3 matrix, en de vermenigvuldiging van alle 3 de matrices geeft de rotatiematrix R. Een voorbeeld van een rotatie rond de z-as vindt men in guur 2.8. De algemene formules voor de rotatie van een punt rond de Z-as zijn: x0 = xcos(θ) − ysin(θ)
(2.8)
y 0 = xsin(θ) + ycos(θ)
(2.9)
2.4 Projectie van 2D lijnen in foto's naar 3D in het puntenwolkmodel Figuur 2.7:
Rotatie en translatie.
Figuur 2.8:
Rotatie rond de z-as
17
Met θ de hoekverschuiving tussen de 2 punten. Indien we deze vergelijkingen in een matrixvorm zetten krijgen we: 0 x cos(θ) −sin(θ) 0 x y 0 = sin(θ) cos(θ) 0 . y z0 0 0 1 z
(2.10)
Hetzelfde geldt voor de rotatie rond de x-as: 0 x 1 0 0 x y 0 = 0 cos(θ) −sin(θ) . y z0 0 sin(θ) cos(θ) z
en voor de y-as:
(2.11)
18
Literatuurstudie 0 x cos(θ) 0 sin(θ) x y 0 = 0 1 0 . y 0 z −sin(θ) 0 cos(θ) z
(2.12)
Als men 2.10, 2.11, 2.12 met elkaar vermenigvuldigt krijgt men zoals gezegd de rotatiematrix R: R = R .R .R
(2.13)
r1 r2 r3 R = r4 r5 r6 r7 r8 r9
(2.14)
x
y
z
Naast de rotatiematrix heeft men ook nog de translatiematrix die de verplaatsing van de camera ten opzichte van het wereldassenstel weergeeft. Als een punt verschoven wordt, dan krijgt men: 0 x x y 0 y 0 = T. z z 1 1
(2.15)
met 1 0 T = 0 0
0 1 0 0
0 0 1 0
t t t 1 x y z
(2.16)
2.4.1.3 Projectie matrix Als we alle 3 de matrices (2.3, 2.14, 2.16) met elkaar combineren krijgen we de projectie matrix. Dit is een 3x4 matrix en heeft de volgende vorm: m1 m2 m3 m4 P = m5 m6 m7 m8 m9 m10 m11 m12
(2.17)
Met deze matrix kan men dan gemakkelijk de omzetting van 2D naar 3D doen, en omgekeerd. Een willekeurig punt P in 3D wordt het punt p in 2D: X x m1 m2 m3 m4 y = m5 m6 m7 m8 . Y Z 1 m9 m10 m11 m12 1
(2.18)
2.4 Projectie van 2D lijnen in foto's naar 3D in het puntenwolkmodel
19
2.4.1.4 Conclusie Hartley en Zisserman Met de methode van Hartley en Zisserman is het zeer gemakkelijk om de omzetting van 2D naar 3D te doen en omgekeerd omdat men een projectiematrix heeft. Eens men de projectiematrix kent, is de projectie gemakkelijk te berekenen. Een nadeel is wel dat er geen rekening gehouden wordt met de mogelijke vervorming van de punten in de foto door de lens. Hierdoor zal het eindresultaat niet volledig accuraat zijn. Maar indien men geen accuraat model nodig heeft, is deze methode perfect. 2.4.2
Tsai
Bij Tsai werkt men niet met een projectiematrix waarmee men gemakkelijk de omzetting kan doen, maar werkt men in stappen. Men kan deze stappen wel allemaal tesamen brengen, zodat men één formule krijgt. Dit wordt in de implementatie dan ook gedaan om gemakkelijk de omzetting te doen. Volgens Tsai zijn er 4 stappen die men moet doorlopen om te gaan van een 3D punt in de scène naar een 2D punt op een foto. 1. De eerste stap is het omzetten van het 3D punt in een wereldassenstelsel (Xw , Yw , Zw ) naar een 3D punt dat het assenstelsel van de camera gebruikt (x, y, z). Hiervoor is een rotatie en/of een translatie nodig. De rotatiematrix is dezelfde als diegene die we gebruikt hebben voor Hartley en Zisserman, namelijk de matrix in vergelijking 2.14. De translatiematrix is lichtjes verschillend, aangezien men bij Tsai de translatiematrix optelt bij het punt, in plaats van te vermenigvuldigen: Tx T = Ty Tz
(2.19)
De eerste stap kan dan geschreven worden als: x Xw y = R Yw + T z Zw
(2.20)
2. De volgende stap is het omzetten van het 3D punt in de camera naar een ideaal 2D punt in de foto. Ideaal wilt hier zeggen dat er nog geen rekening gehouden wordt met de distorsie, maar meer hierover in de volgende stap. De nieuwe coördinaten (Xu , Yu ) worden berekend als volgt:
Xu = f
x z
(2.21)
Yu = f
y z
(2.22)
20
Literatuurstudie
Met f de focale lengte van de camera, deze kan gevonden worden in de intrinsieke matrix. Deze is verschillend aan de intrinsieke matrix van Hartley en Zisserman, aangezien deze geen skew factor meer bezit en ook geen schaalfactor. Enkel de focale lengte in x en y-richting en de x en y-coördinaten van het principal point (in pixels): fx s Cx A = 0 fy Cy 0 0 1
(2.23)
Aangezien fx en fy meestal gelijk zijn aan elkaar gaan we in het verloop van de tekst de focale lengte voor zowel x als y aangeven met f. 3. De 3e stap in het omzetten is het in rekening brengen van de distorsie. Distorsie is de vervorming van punten op een foto, dit komt door de lens in de camera. Deze vervorming is het beste te merken bij lijnen. Men heeft 2 soorten distorsie, de lijnen kunnen naar buiten gebogen zijn wat men barrel distortion noemt, of naar binnen gebogen wat men pincushion distortion noemt. Beide gevallen zijn te zien op guur 2.9. Figuur 2.9:
Lens distorsie, links barrel distortion, rechts pincushion.
De parameters voor distorsie vindt men in een aparte vector terug, de distorsievector. Deze bevat de componenten voor radiale distorsie en tangentiële distorsie, welke beiden de vervorming van de lijnen karakterisen. Maar volgens Tsai [15] is het voldoende indien men enkel de eerste component gebruikt (k1 ), aangezien deze de meeste invloed heeft op de distorsie en bijna hetzelfde eect heeft als wanneer men toch ook de andere coë cienten zou gebruiken. De distorsievector heeft de volgende vorm: D = [ k1 k2 p1 p2 k3 ]
De vergelijkingen voor de 3e stap zijn:
2.4 Projectie van 2D lijnen in foto's naar 3D in het puntenwolkmodel
21
Xd + Dx = Xu
(2.24)
Y d + Dy = Y u
(2.25)
Hierin zijn Dx en Dy gelijk aan: Dx = Xd (K1 r2 + K2 r4 + ...) Dy = Yd (K1 r2 + K2 r4 + ...)
Met r: r=
p Xd2 + Yd2
4. Bij de laatste stap zet men het punt in de camera over naar een punt op de computer, hiervoor moet men rekening houden met de resolutie van de pc en het principal point (2.26)
'-1
X =s d X +C f
x
d
x
x
(2.27)
-1
Y =d Y +C f
y
d
y
Hierin is: 0
Ncx dx = dx N fx
Met • (C , C ) de middelpunten in pixels die men terugvindt in matrix 2.23. x
y
• s een scale factor. x
• (d , d ) de afstand tussen de middelpunten van 2 naast elkaar gelegen CCD x
y
elementen van de sensor van de camera in respectievelijk de X-richting en de Y-richting. • N het aantal sensor elementen in de X richting en N het aantal pixels in de x-richting. cx
fx
2.4.2.1 Conclusie Tsai Hier zijn de voor en de nadelen het omgekeerde van bij Hartley en Zisserman. Het voordeel van Tsai is namelijk dat men wel met distorsie rekening houdt, waardoor men zeer accurate oplossingen kan vinden voor de projectie van 2D naar 3D. Het nadeel echter
22
Literatuurstudie
is dat men geen projectiematrix heeft die de projectie eenvoudig maakt, maar men heeft verschillende vergelijkingen. Deze vergelijkingen zal men moeten invullen in elkaar, wat leidt tot wat rekenwerk. 2.4.3
Conclusie
De twee modellen zijn beiden goed om de omzetting van 2D naar 3D te doen, echter moeten we in deze thesis proberen zo accuraat mogelijk te werken aangezien het plan de juiste afmetingen en de juiste coördinaten moet bevatten. Daarom moeten we het model van Tsai gebruiken omdat deze rekening houdt met de mogelijke distorsie in een foto. Deze distorsie zou anders leiden tot de foute coördinaten in het model van Hartley en Zisserman. De omzetting die we gaan doen is echter niet volledig gelijk aan die van Tsai, want het camera model van Bundler (het programma om een puntenwolk te creëren uit foto's) laat de laatste stap van Tsai weg.
Hoofdstuk 3 Overzicht van de uitwerking De thesis wordt uitgewerkt in enkele stappen, deze zijn weergegeven in een blokkendiagram dat te zien is in guur 3.1 Nadat er foto's getrokken zijn geweest van alle hoeken van het gebouw, zodat alles goed op beeld staat, gaat de eerste stap van de thesis uitgevoerd moeten worden. Deze eerste stap is het omzetten van de foto's naar een puntenwolk welke beschreven staat in hoofdstuk 4. Hiervoor gaan we het Structure from Motion programma Bundler gebruiken, dit is te vinden online en kan vrij gebruikt worden. Het neemt als invoer de foto's en genereert op basis hiervan een puntenwolk en bepaalt de parameters van de camera waarmee de foto's getrokken zijn, dit zijn de intrinsieke en extrinsieke matrices.. De puntenwolk die gegenereerd wordt is een goede eerste 3D benadering van het gebouw, maar er zijn wel nog tal van ruispunten en hierdoor belanden we bij stap 2. Hier gaan we de output van Bundler even niet gebruiken en gaan we verderwerken met de initiële foto's, we gaan namelijk lijnen detecteren in de verschillende foto's, de uitwerking hiervan staat beschreven in hoofdstuk 5. We moeten ervoor zorgen dat er zoveel mogelijk juiste lijnen gedetecteerd worden, want deze lijnen gaan de basis vormen voor de volgende stap. Eens we de lijndetectie hebben uitgevoerd zullen we deze lijnen projecteren van 2D naar 3D in stap 3 welke beschreven staat in hoofdstuk 6. Hiervoor gaan we de output van de lijndetectie gebruiken en ook terug de output van Bundler, zowel de puntenwolk als de parameters van de camera. Deze parameters zijn namelijk nodig om te zeggen waar exact de gedetecteerde lijn zich bevindt in 3D. Het resultaat van deze stap is dat we alle belangrijke punten in de puntenwolk overhouden, een punt is belangrijk als het iets zegt over de structuur van het gebouw, bijvoorbeeld een hoekpunt van het dak. Als laatste rest er enkel nog het ingeven van deze punten in AutoCAD, we maken hiervoor een .dwg bestand en geven met behulp van een script alle punten in en we zeggen welke paren een lijn vormen.
24
Overzicht van de uitwerking
Figuur 3.1:
Het overzicht van alle stappen die doorlopen worden in deze thesis.
Hoofdstuk 4 Omzetting foto's naar puntenwolk Zoals gezegd in het overzicht maken we gebruik van het SFM programma Bundler. Deze kan aan de hand van foto's een puntenwolk maken, echter zijn er een heleboel foto's nodig aangezien er minstens een foto moet genomen worden om de 15◦ van het gebouw. Dit is nodig omdat anders de gelijkenis tussen de foto's te klein gaat zijn waardoor de gecreëerde puntenwolk niet correct gaat zijn. Het nemen van een foto om de 15◦ betekent dat we minstens 24 foto's nodig hebben voor een 3D model te maken van een gebouw, echter zijn deze 24 foto's allemaal vanuit 1 hoogte getrokken en zeggen ze bijvoorbeeld niets over het dak van het gebouw. Daarom kan het zijn dat we gemakkelijk aan een 50 à 100-tal foto's komen om een gedetailleerd 3D model te maken. Een voorbeeld van hoe zo'n puntenwolk eruit ziet is te zien in guur 4.1. Figuur 4.1:
Het verkregen resultaat van Bundler met de bijhorende posities van waaruit elke foto getrokken is. Dit model is gemaakt met 60 foto's, maar allemaal getrokken vanuit het oosten van het gebouw.
Er zijn echter wel enkele aspecten in verband met de puntenwolk waar we rekening mee moeten houden, zo heeft de puntenwolk een schalingsfactor. Dit wilt zeggen dat de afstand tussen 2 punten in de puntenwolk verschillend is aan de afstand tussen diezelfde punten in de realiteit. Deze factor verschilt echter van scène tot scène en moet telkens opnieuw berekend worden. Ze is echter wel hetzelfde voor alle punten in één puntenwolk, waardoor men de factor maar 1 keer moet berekenen. Een ander belangrijk punt bij Bundler is dat de grond van het model niet juist overeenkomt met Y-niveau 0, dit komt doordat Bundler niet kan weten welke punten van de puntenwolk de grond voorstellen. Bundler bekijkt de foto's ook anders want normaal gezien is in een foto de coördinaat (0,0) linksboven, maar
26
Omzetting foto's naar puntenwolk
Bundler zegt dat de coördinaat (0,0) zich in het midden van de foto bevindt. Hierdoor zal in de puntenwolk het Y-niveau 0 ook overeenkomen met ongeveer het midden van het gebouw. Een voorbeeld om dit aan te tonen is te vinden in guur 4.2. Het is ook zo dat meestal het gebouw iets gedraaid staat ten opzichte van het assenstelsel, dit wilt zeggen dat de voorkant van het gebouw niet parallel loopt met het XY vlak. Dit hangt af van hoeveel foto's getrokken zijn en vanuit welke hoek deze getrokken zijn, indien bijvoorbeeld meer foto's van de linkerkant getrokken zijn dan van de rechterkant dan zal de puntenwolk gedraaid zijn. Dit is belangrijk om te onthouden voor het naal model in AutoCAD, aangezien we daar nog een globale rotatie moeten toepassen op alle punten want anders is de positionering van het model niet correct. Naast de puntenwolk geeft Bundler ook nog andere output, namelijk de extrinsieke en intrinsieke matrices van elke foto en ook de positie van de camera voor die bepaalde foto. De extrinsieke en intrinsieke matrices hebben we nodig voor de projectie, zoals gezegd in 2.4. Figuur 4.2:
4.1
Hier ziet men 2 foto's met de positie van de bijhorende camera's en het assenstelsel van Bundler dat als Y-niveau 0 het midden heeft van de lijn.
Conclusie
Om een deftige puntenwolk te verkrijgen is het noodzakelijk dat er minstens een 50 à 100 tal foto's van het gebouw getrokken worden. De foto's zullen door Bundler verwerkt worden en deze geeft ons de puntenwolk alsook informatie over de camera welke we kunnen gebruiken om de projectie te doen. Er zijn wel 2 factoren waar rekening moet mee gehouden worden bij de puntenwolk, namelijk een scalingsfactor die de afstanden tussen de punten verandert en een globale rotatie van het model die afhankelijk is van de getrokken foto's. Beiden hebben een invloed op de correctheid van het naal model in AutoCAD.
Hoofdstuk 5 Lijndetectie Nadat we een model gegeneeerd hebben moeten we de lijnen detecteren in al de verschillende foto's, het is belangrijk dat de gedetecteerde lijnen zo goed mogelijk overeen komen met de eectieve lijnen aangezien deze de basis vormen voor de volgende stappen. Indien er iets misloopt met de lijndetectie ondervindt de projectie daar ook nadeel van.
5.1
Thresholds
Zoals in 2.3 gezegd gaan we gebruik maken van de PPHT, welke gebruik maakt van de Canny Edge Detector om randen te detecteren in een foto. Maar voor we eectief de randen gaan detecteren moeten we eerst de foto's blurren, dit doen we omdat er soms ruis kan aanwezig zijn op de foto's. Ruis in de vorm van zeer sterke overgangen tussen naburige pixels door bijvoorbeeld schaduw of lichtinval. Om deze ruis te vermijden blurren we aangezien de overgang dan verspreid wordt over de naburige pixels. Als gevolg zal er geen randpunt meer gedetecteerd worden want de gradiënt zal niet meer zo groot zijn als daarvoor. Eens we de randen hebben gaan we de PPHT oproepen, deze zal de verschillende lijnen teruggeven. Echter zullen nooit alle lijnen in een foto gevonden worden, welke wel en welke niet hangt af van welke waarden we gebruiken voor de thresholds. Men heeft voor de lijndetectie verschillende thresholds, namelijk 2 voor Canny en 3 voor Hough. Deze thresholds zijn gemakkelijk in te geven aangezien men in OpenCV Canny en Hough beiden kan oproepen met een functieoproep waarbij men de waarden van de thresholds kan ingeven als argumenten. Bij Canny hebben beide thresholds betrekking tot de waarden van de gradiënt. Een randpunt moet namelijk een gradiënt hebben die groter is dan T1 , welke de eerste threshold voorstelt. Maar indien men een een rand aan het a open is en men vindt geen punten meer met een gradiënt groter dan T1 , dan kijkt men of er misschien nog punten zijn met een gradiënt groter dan T2 en worden deze toegevoegd als randpunten. T2 stelt de tweede threshold voor en is normaal 2 tot 3 keer kleiner dan T1 , daarom hebben wij gekozen voor een verhouding van 3 (T2 = T1 /3). De waarde van T1 kunnen we ook kiezen maar aangezien deze afhangt van scène tot scène is het best om deze te bepalen via trial and error. Bij Hough hebben we 3 thresholds die iets gaan zeggen over wat voor soort lijnen we willen detecteren in de foto's. De eerste bepaalt hoeveel randpunten er minstens moeten gedetecteerd worden opdat men kan
28
Lijndetectie
spreken van een lijn, de tweede bepaalt wat de maximale grootte mag zijn van de opening tussen 2 gedetecteerde lijnen (hoeveel punten er tussen mogen liggen) opdat deze kunnen samengevoegd worden tot één doorlopende lijn en de derde bepaalt hoeveel intersecties er minimaal nodig zijn in het Hough vlak. Ook deze parameters hangen heel veel af van de scène waar de foto's getrokken zijn en opnieuw is het best om via trial and error de thresholds te bepalen. Het is daarom belangrijk dat bij elke nieuwe groep van foto's we kijken of de waarden nog steeds goed zijn en indien nodig bijstellen. Een voorbeeld van de gedetecteerde lijnen is te zien op foto 5.1 en op foto 5.2. Figuur 5.1:
Figuur 5.2:
Output van het lijndetectie programma, rechts is de originele foto. Hier wordt een redelijk hoge threshold gebruikt voor Canny, hierdoor heeft men weinig ruislijnen, maar als gevolg ook weinig lijnen in totaal.
Output van het lijndetectie programma, rechts is de originele foto. Hier wordt een lagere threshold gebruikt dan de foto hierboven, men heeft nu meer lijnen in het algemeen, maar bijgevolg ook meer ruislijnen.
5.2 Conclusie 5.2
29
Conclusie
Via de lijndetectie kan spijtig genoeg niet elke lijn gedetecteerd worden. Hoeveel er gedetecteerd worden hangt af van de thresholds die men gebruikt, maar ook van de manier waarop de foto's getrokken zijn. Zo is het beter indien er overal eenzelfde verlichting is en er veel contrast is tussen het gebouw en de omgeving. Natuurlijk zal het soms zijn dat dit onmogelijk is en moet men experimenteren met de waarden van de thresholds opdat men goede resultaten krijgt. Het is beter indien alle lijnen gedetecteerd worden, zelfs als dit betekend dat er ook een deel ruislijnen gaan aanwezig zijn, want in de volgende stap gaan we met behulp van het voting algoritme deze ruislijnen toch wegwerken. Maar we moeten oppassen met deze ruislijnen aangezien het verhogen of verlagen van de thresholds met een kleine waarde soms kan zorgen voor een drastische verhoging van het aantal ruislijnen.
Hoofdstuk 6 Projectie naar 3D De projectie gaat ervoor zorgen dat we de gedetecteerde lijnen in de foto's kunnen gebruiken in de 3D puntenwolk. Hiervoor moeten we weten welk cameramodel Bundler gebruikt om de omzetting te doen van 2D naar 3D, wat de camera parameters zijn van elke foto en moet elke lijn die gedetecteerd wordt bij de lijndetectie worden weggeschreven in de vorm van [beginpunt,eindpunt]. Als we deze informatie allemaal hebben kunnen we beginnen met de projectie. We kunnen met het cameramodel van Bundler een formule berekenen die ons toelaat om deze projectie te doen. 6.1
Bundler's cameramodel
Zoals gezegd in de literatuurstudie maakt Bundler gebruik van een camera model dat ongeveer gelijk is aan dat van Tsai, enkel de laatste stap wordt overgeslagen. Het model dat Bundler gebruikt om de wereldcoördinaten (Xw , Yw , Zw ) om te zetten in pixelcoördinaten (Xd , Yd ) is: Stap 1: Conversie van wereldcoördinaten naar cameracoördinaten: x Xw y = R Yw + T Zw z
Met R gelijk aan 2.14 en T gelijk aan 2.19
Stap 2: Van 3D naar 2D:
x z
(6.2)
y z
(6.3)
Xu = − Yu = −
(6.1)
Stap 3: Conversie naar pixelcoördinaten: Xd = f ∗ Xu ∗ D x
(6.4)
6.2 Berekening formule projectie
31
Yd = f ∗ Yu ∗ Dy
(6.5)
Hierin zijn Dx en Dy gelijk aan: Dx = (1 + K1 r2 + K2 r4 + ...) Dy = (1 + K1 r2 + K2 r4 + ...)
Met r: r=
6.2
p Xu2 + Yu2
Berekening formule pro jectie
We moeten deze stappen omvormen tot 1 formule waarin we Xw en Yw kunnen bepalen aan de hand van de andere parameters en om dit gemakkelijker te maken gaan we veronderstellen dat er geen distorsie is. Want we gaan met de output van Bundler, namelijk de intrinsieke matrix en de distorsievector, de foto's undistorten nog voor de lijndetectie en zo hoeven we niet te rekenen met de distorsieparameters. De berekening is als volgt: Uit stap 6.1 volgt: x = r1 Xw + r2 Yw + r3 Zw + Tx
(6.6)
y = r4 Xw + r5 Yw + r6 Zw + Ty
(6.7)
z = r7 Xw + r8 Yw + r9 Zw + Ty
(6.8)
Aangezien we zeggen dat er geen distorsie is, kunnen we 6.2 en 6.4 omvormen tot: x=−
Xu z f
(6.9)
Yu z f
(6.10)
En 6.3 en 6.5 omvormen tot: y=−
Als we 6.6 en 6.8 in 6.9 invullen krijgen we:
32
Projectie naar 3D Xu [r7 Xw + r8 Yw + r9 Zw + Tz ] f
(6.11)
r8 Xu r9 Xu Tz Xu r7 Xu ] = Yw [−r2 − ] + Zw [−r3 − ] − Tx − f f f f
(6.12)
r1 Xw + r2 Yw + r3 Zw + Tx = −
Xw [r1 +
Xw =
... r1 + r7fXu
(6.13)
Vervolgens doen we hetzelfde voor 6.10: r4 Xw + r5 Yw + r6 Zw + Ty = −
Xw [r4 +
Yu [r7 Xw + r8 Yw + r9 Zw + Tz ] f
r7 Yu r8 Yu r9 Y u Tz Yu ] = Yw [−r5 − ] + Zw [−r6 − ] − Ty − f f f f Xw =
... r4 + r7fYu
(6.14) (6.15) (6.16)
6.13 gelijk stellen aan 6.16 geeft: r8 Xu r7 Y u r9 Xu r7 Yu r7 Yu Tz Xu r7 Yu ][r4 + ] + Zw [−r3 − ][r4 + ] − Tx [r4 + ]− [r4 + ]= f f f f f f f r8 Yu r7 Xu r9 Yu r7 Xu r7 Xu Tz Yu r7 Xu Yw [−r5 − ][r1 + ] + Zw [−r6 − ][r1 + ] − Ty [r1 + ]− [r1 + ] f f f f f f f
Yw [−r2 −
(6.17)
Om de berekening iets makkelijker te maken zeggen we dat [r4 + r7fYu ] = a1 en dat [r1 + r7fXu ] = a2 . Als uiteindelijke resultaat, na het samenvoegen van de termen krijgt men: Yw
r8 Y u r8 Xu ] − a2 [−r5 − ] a1 [−r2 − f f
r9 Yu r9 Xu = Zw a2 [−r6 − ] − a1 [−r3 − ] f f a1 X u a2 Y u +Tx a1 − Ty a2 + Tz [ − ] f f
(6.18)
Met deze formule kunnen we voor elke pixel op een foto de Y coördinaat vinden in de puntenwolk. Als we al de vorige stappen doen in functie van Yw bekomen we ook de X coördinaat. Het resultaat hiervan:
6.3 Probleem projectie
Xw
r7 Xu r7 Y u a1 [−r1 − ] − a2 [−r4 − ] f f
33
r9 Yu r9 Xu = Zw a2 [−r6 − ] − a1 [−r3 − ] f f a1 X u a2 Y u +Tx a1 − Ty a2 + Tz [ − ] f f
(6.19)
Waarin a1 = [r5 + r8fYu ] en a2 = [r2 + r8fXu ]. 6.3
Probleem pro jectie
Met 6.19 en 6.18 kunnen we voor elke pixel zeggen wat de X en de Y coördinaten zijn, maar zoals te zien in de vergelijkingen komen we niet juist uit op 1 punt aangezien we een vrijheidsgraad hebben, namelijk Zw . We zullen dus per pixel een lijn bekomen in 3D, die we verkijgen door telkens Zw met een kleine waarde te verhogen en de bijhorende X en Y waarden opnieuw te berekenen. Dit zorgt echter voor een probleem, aangezien we niet weten waar op de lijn het eectieve 3D punt zich bevindt. We lossen dit op door een voting systeem te implementeren, we gaan namelijk voor elke geprojecteerde lijn kijken of er punten van de puntenwolk dichtbij deze lijn liggen. Wanneer er punten dichtbij liggen (hoe dichtbij wordt ingesteld met een threshold), dan krijgen deze een vote. De punten met de meeste votes na de projectie zijn de eectieve punten in 3D. Het is echter wel zo dat soms meerdere punten dichtbij een projectie liggen, daarom gaan we telkens het gemiddelde nemen van alle punten die dichtbij liggen en deze nieuwe positie bewaren en een vote geven. Als bij een volgende projectie dan zo'n opgeslagen punt dichtbij ligt, dan gaat opnieuw het gemiddelde berekend worden en de positie van het opgeslagen punt wordt dan gewijzigd naar deze nieuwe berekende positie. Ook wordt de votecount van het opgeslagen punt verhoogd, zo gaat men niet allemaal punten hebben die dicht bij elkaar liggen en een votecount hebben van 1. Een voorbeeld van hoe dit er uit ziet in de praktijk is te zien op guur 6.1
6.4
Conclusie
Via de vergelijkingen 6.19 en 6.18 en het voting systeem kan men gemakkelijk de punten van de puntenwolk overhouden die het meest gedetecteerd worden in de foto's. Indien steeds dezelfde lijnen gedetecteerd worden is het makkelijk om paren van punten bij te houden, die samen 1 lijn vormen. Indien echter de lijndetectie niet optimaal is en telkens andere delen van eenzelfde lijn gedetecteerd worden in de verschillende foto's wordt steeds een ander punt gevote. Dit zorgt ervoor dat ook de output van de projectiestap fout is want enkel punten die een votecount hebben hoger dan de threshold blijven behouden. Het resultaat is dus afhankelijk van de lijndetectie. Maar het is ook belangrijk dat de puntenwolk goed is, want indien de puntenwolk slecht is gaat deze maar een klein aantal punten bevatten en wordt het moeilijker om punten te vinden die dicht bij een projectielijn
34
Projectie naar 3D Figuur 6.1:
Projectie van hetzelfde punt in 2 foto's naar 3D. Punt A heeft nu 2 votes.
liggen. Het kan zelfs zo erg zijn dat men de threshold voor de afstand moet verhogen en bijgevolg slechte punten uitkomt. Of de puntenwolk goed is hangt af van hoeveel foto's er genomen zijn en hoeveel overlapping er is tussen de foto's. Men moet dus zorgen dat de input van voldoende kwaliteit is voordat men aan de projectie begint, enkel indien de kwaliteit voldoende hoog is zal het resultaat ook goed zijn.
Hoofdstuk 7 Constructie 3D model AutoCAD Eens we de belangrijkste lijnen hebben gehaald uit de puntenwolk zullen we deze nog moeten ingeven in AutoCAD zodat er gemakkelijk gewerkt kan worden met het 3D model. Aangezien het enkel lijnen zijn kan dit worden ingegeven met behulp van een AutoCADscript, dit is een bestand dat enkele taken uitvoert voor de gebruiker. Deze taken worden normaal opgegeven via de command-line van AutoCAD en aangezien lijnen tekenen kan uitgevoerd worden met de command-line kunnen we zo'n script gebruiken om dit automatisch te doen. Het enige wat er moet gebeuren is dat de persoon die AutoCAD opstart dit script sleept binnen het AutoCAD venster en alles wordt dan voor hem uitgevoerd. We moeten wel zoals gezegd in 4 nog een globale rotatie doen op het model opdat de grond gelijk zou komen te liggen met het XZ-vlak. Dit kan echter niet automatisch gedaan worden aangezien de rotatie afhangt van de genomen foto's en dus verschilt van puntenwolk tot puntenwolk. Ook moeten we rekening houden met de scalingfactor van de Bundler, opnieuw moet deze manueel toegepast worden op het model. In het ideale geval, zonder optreden van enige fouten, zou het model dat we willen verkrijgen er bijvoorbeeld uitzien als guur 7.1. Figuur 7.1:
Een voorbeeld van het nale model na alle stappen te doorlopen.
Hoofdstuk 8 Resultaten In de vorige hoofdstukken hebben we uitgelegd wat we exact gaan doen om een 3D model te genereren van een gebouw, in dit hoofdstuk zullen we bespreken wat we bekomen zijn als resultaten. We hebben foto's genomen van 8 huizen, deze waren allemaal alleenstaande huizen en zonder tuin, zodat men goed zicht had op het huis zelf. We hebben echter niet van elk huis een 360◦ beeld, meestal hebben we een 20-30 tal foto's getrokken van de voorkant en zijkant van het huis. Dit mag echter geen invloed hebben op het resultaat, het enige verschil is dat het 3D model minder volledig zal zijn. Om de resultaten van de verschillende stappen te bespreken zullen we het huis in guur 8.1 als voorbeeld nemen. Figuur 8.1:
Het gebouw dat we gebruiken als test voor de thesis.
8.1 Omzetting naar puntenwolk 8.1
37
Omzetting naar puntenwolk
De eerste stap was Bundler oproepen op de foto's, het resultaat hiervan is te vinden in guur 8.2 en 8.3. Op te merken valt dat indien de foto's getrokken zijn van op een degelijk lange afstand (5-10 meter) van het gebouw Bundler geen goede resultaten geeft aangezien de puntenwolk dan minder detail gaat hebben en het kan ook leiden tot fouten in het gebouw, zoals muren die krom staan. Zoals gezegd in hoofdstuk 4 zal het model ook een scalingfactor hebben, we hebben deze voor elk model ruw bepaald en kwamen uit dat deze lag tussen de 1.10 en 4. Met andere woorden, de afstand tussen 2 punten in de puntenwolk is 1.10 tot 4 keer groter dan de afstand in de realiteit. We hebben echter maar 8 huizen als meting genomen dus het zou kunnen dat deze scalingfactor nog veel groter kan zijn en het is zoals daarjuist gezegd een ruwe benadering van de scalingfactor. Om deze met grote nauwkeurigheid te bepalen moeten we terug 2 punten van het huis op de oude manier gaan meten, namelijk met een tachymeter. Maar voor nu volstond het om de scalingfactor op een ruwe manier te meten. Daarnaast was er ook nog de rotatie van het model, we konden echter niet achterhalen wat deze was per puntenwolk, het is daarom noodzakelijk om achteraf zelf via trial en error alle punten een rotatie te geven in AutoCAD en kijken naar het resultaat. Figuur 8.2:
De puntenwolk die gegenereerd werd van het gebouw. De groene, blauwe en rode lijn vormen het assenstelsel. De blauwe lijn is de Z-as, de groene de Y-as en de rode de X-as.
38
Resultaten
Figuur 8.3:
De puntenwolk die gegenereerd werd van het gebouw.
8.2 Lijndetectie 8.2
39
Lijndetectie
Zoals gezegd in hoofdstuk 6 gaan we geen rekening houden met distorsie in de projectie om de formule iets eenvoudiger te maken, maar om dit te mogen doen moeten we alle foto's undistorten voordat we de lijndetectie gaan uitvoeren. Het undistorten van de foto's is echter niet zo moeilijk, men heeft namelijk functies in OpenCV die dit voor ons gaan doen. Het enige dat we nodig hebben zijn de distorsieparameters en de intrinsieke matrix per foto, beiden verkrijgen we met Bundler. Deze undistorsie had tot eect dat alle pixels ongeveer 10 plaatsen waren opgeschoven ten opzichte van hun originele positie, veel eect heeft dit niet maar het is wel belangrijk om een nauwkeurig model af te leveren. Na de distorsie te verwijderen en de lijndetectie toe te passen op de foto's merkten we dan voor de meeste foto's de lijndetectie geen goede resultaten gaf, er waren namelijk 2 grote fouten: 1. De gedetecteerde lijnen sluiten niet perfect aan op elkaar. Hiermee bedoelen we dat steeds maar delen gedetecteerd worden van de lijnen waardoor ze niet samenkomen in één punt, ook uitgelegd op guur 8.4. Hier zien we dat door de fout er 4 lijnen gaan gedetecteerd worden, en het kan zijn dat in de volgende foto's nog eens andere delen van de lijnen gedetecteerd worden. Hierdoor gaan bij de projectie telkens andere punten gevote worden want de verschillende begin en eindpunten van de lijnen worden andere punten in de puntenwolk, zoals uitgelegd in hoofdstuk 6. Het is echter nodig dat de lijnen samenkomen in één punt (linkse deel van de guur) want anders gaat de projectie niet juist zijn. Wat ook soms gebeurd is dat de volledige lijn gedetecteerd wordt, maar dat bijkomstig ook verschillende delen van die lijn gedetecteerd worden. Zodat in één foto er 5 verschillende delen van 1 lijn gedetecteerd wordt bovenop de volledige lijn. In het voorbeeldgebouw hadden we ook te maken met deze soort fouten, zoals te zien in guur 8.5. Als men bijvoorbeeld naar de ramen kijkt dan zou in het ideale geval rond elk raam een rode rechthoek zitten, echter zijn er delen van de rand van het raam die niet gedetecteerd worden. Dit leidde ertoe dat in de meeste foto's andere delen van bijvoorbeeld het raam gedetecteerd werden en dit is een groot probleem, aangezien we verwachten dat telkens hetzelfde punt moet geprojecteerd worden. 2. Het aantal ruislijnen dat gedetecteerd werd door Hough was ook te hoog. Ruislijnen zijn groepen van tientallen lijnen die heel dicht bij elkaar liggen, welke dingen weergeven die we niet willen detecteren. In onze set van huizen hebben we gemerkt dat vooral dakpannen en bomen in de tuin zorgden voor heel veel ruis, ook bijvoorbeeld een verschil in lichtinval op de bakstenen zorgde voor ruis. Men kan zelf kiezen natuurlijk ofdat deze lijnen ruis zijn of niet, het hangt af van hoe compleet het uiteindelijke 3D model moet zijn. Indien men ook de lijnen van de cementlagen van de bakstenen en de dakpannen erbij wilt dan zijn deze geen ruis, maar wij willen enkel de lijnen tussen de hoekpunten van het gebouw detecteren, of anders gezegd de breeklijnen van het gebouw. Dit leidde ertoe dat in de foto's soms 3/4 van de gedetecteerde lijnen ruislijnen waren, wat natuurlijk ongewenst is. Deze ruislijnen gaan overdragen worden naar het AutoCAD model, aangezien we in de projectiestap er vanuit gaan dat een ruislijn maar weinig voorkomt en door te werken met votes
40
Resultaten
Figuur 8.4:
Fout bij de lijndetectie, er wordt maar een deel van de lijn gedetecteerd, wat resulteerd in fouten.
deze ruislijnen kunnen wegwerken. Echter indien er meer ruislijnen zijn dan juiste lijnen kunnen we ons niet meer baseren op votes want deze geven een fout beeld. In het voorbeeldgebouw zorgden vooral de dakpannen voor heel veel ruis, zoals te zien is op guur 8.6. Om het aantal ruislijnen te reduceren tot een minimum kan men best foto's nemen van gebouwen waar geen planten voor staan en dat geen dakpannen heeft. Op zich kan men het aantal ruislijnen ook reduceren door de thresholds te verhogen, maar indien we dat doen gaan we in het algemeen veel minder lijnen detecteren en verliezen we ook een heel deel goede lijnen. Aangezien we deze fouten krijgen zouden we beter een andere lijndetector gebruiken in plaats van de PPHT die in OpenCV zit. De nieuwe lijndetector zou 2 dingen extra moeten doen, namelijk verschillende korte lijnsegmenten samenvoegen opdat er 1 grote lijn vormt en een betere manier om onderscheid te maken tussen randpunten en punten in een vlak. Echter hebben we zo'n nieuwe lijndetector niet meer gevonden, er waren wel enkele papers over lijndetectors (zie [8], [5]) die verschillende lijnsegmenten samenvoegden maar er stond geen code online van die papers. We konden ook zelf een eigen lijndetector schrijven maar dit zou te veel werk zijn en aangezien we deze fouten hebben is het al moeilijk om nog tot een goed naal resultaat te komen want de projectiestap gaat ervan uit dat de lijndetectie in orde was.
8.2 Lijndetectie Figuur 8.5:
41
De lijndetectie die maar delen van de lijnen detecteerd in plaats van de hele lijn, zoals te zien bij de ramen en deuren.
Figuur 8.6:
De lijndetectie die te veel ruis oplevert.
42 8.3
Resultaten Pro jectie
Nadat we de lijnen gedetecteerd hadden en we de puntenwolk gegeneerd hadden was de volgende stap het projecteren van de lijnen, echter moeten we eerst nog een conversie doen. De puntenwolk die gecreëerd werd door Bundler is namelijk in .ply formaat, maar PCL werkt enkel met .pcd formaat. Beiden zijn gelijkwaardig, enkel zijn de headers iets anders en worden de punten anders weggeschreven. Om de conversie te doen van .ply naar .pcd gebruiken we een python script dat de header veranderd en de punten anders wegschrijft. In het projectie algoritme hebben we ook een aanpassing moeten doen want normaal gezien was het de bedoeling om telkens een hele lijn te projecteren en dus voor 2 punten tegelijk (begin en eindpunt van de lijn) gaan kijken of deze punten ook in de puntenwolk voorkomen, maar we hebben dit moeten aanpassen omdat de lijndetectie geen uniforme resultaten gaf. De lijndetectie detecteerde namelijk vaak verschillende delen van eenzelfde lijn in de verschillende foto's waardoor we nooit dezelfde punten projecteerden, dit leidde tot het feit dat geen enkele lijn meer dan 1 vote had want elke lijn was anders. Om toch een resultaat te krijgen voor de projectie gaan we in plaats van een lijn projeceteren, een punt projecteren. Men werkt niet meer met 2 punten tegelijk, maar voor elke gedetecteerde lijn wordt nu apart gekeken naar begin en eindpunt en gaan we na of deze overeenkomen met een punt van de puntenwolk. Ze worden los van elkaar verwerkt, als gevolg daarvan weten we op het einde van de projectie niet meer welke punten een lijn vormen maar de votecount van de punten is wel signi cant hoger dan wanneer we ze samen bekijken. We hebben echter nog een probleem, namelijk de grote hoeveelheid ruislijnen die gedetecteerd worden. Want als er in een aantal foto's de helft van de lijnen ruis zijn, dan zorgen deze voor een verkeerde beoordeling van het aantal votes aangezien de ruis dan voor meer votes zullen zorgen dan de goede punten. We hebben de projectiestap uitgevoerd op het voorbeeldgebouw en we bekwamen een 30-tal goede punten, waarvan een tiental punten ruis waren. De projecties zijn te zien in guur 8.7. Elke lijn die men ziet op de guur is een projectielijn, welke dicht bij een punt van de puntenwolk ligt dat aan het eind van de stap een votecount had van 50 of hoger. Deze threshold kan nog aangepast worden om meer punten te krijgen maar dan krijgt men ook weer meer onbelangrijke punten want men heeft honderden projecties met minder dan 50 votes. Men moet dus afwegen of deze onbelangrijke punten kwaad kunnen of niet.
8.3 Projectie
43
Figuur 8.7:
De projectie uitgevoerd op het gebouw.
44 8.4
Resultaten Constructie 3D model AutoCAD
Nadat we het script uitvoeren in AutoCAD zitten alle punten in het model, het engiste wat we dan nog moesten doen was de globale rotatie toepassen op de punten. Echter is dit vrij gemakkelijk, we moeten namelijk de punten tot 1 groep maken en dan op deze groep een rotatie uitvoeren. Het is ook niet zo belangrijk dat het model correct georiënteerd is, want we moeten enkel de afstanden weten tussen de verschillende punten, de correcte 3D positie van elk punt hoeft niet geweten te worden. Maar zelfs na de rotatie was het gereconstrueerde model nog verre van perfect. De meeste van de verkregen punten waren ruis, ze gaven niet de juiste lijnen weer, maar dit was al te verwachten door de vele ruislijnen in de lijndetectie. Het is ook zo dat er vaak meerdere punten van eenzelfde lijn in het model zitten, dit is een gevolg van het feit dat we per punt werken in plaats van per lijn. Dit kan eigenlijk geen kwaad, maar het was oorspronkelijk de bedoeling om een mooi zuiver model te maken met enkel de begin en eindpunten van elke lijn in het model. Een voorbeeld van het model dat we gegenereerd hebben op basis van de foto's is te zien in guur 8.8.
8.4 Constructie 3D model AutoCAD
Figuur 8.8:
45
Het model gecreëerd met AutoCAD met als vergelijking een foto van het gebouw. Zoals men ziet zijn er te veel punten geprojecteerd zodat het niet echt duidelijk is welk punt waar zit op de foto.
46 8.5
Resultaten Ander voorbeeld
Ter vergelijking zullen we de resultaten laten zien van de voorkant van een huis zonder dakpannen en weinig ruis, wat een iets beter resultaat gaf als naal model (nog steeds niet bruikbaar voor een landmeter, maar toch al beter).
Puntenwolk
Figuur 8.9:
Figuur 8.10:
De puntenwolk.
Een ander aanzicht van de puntenwolk.
8.5 Ander voorbeeld
47
Lijndetectie
Figuur 8.11:
De lijndetectie die hier al veel beter werkt dan in het vorige voorbeeld, bijna elka belangrijke lijn wordt volledig gedetecteerd.
Figuur 8.12:
Nog een voorbeeld van de lijndetectie.
48
Resultaten
Pro jectie
Hiervoor hebben we de thresholds voor het aantal votes verlaagd naar 5, aangezien er minder lijnen in het algemeen gedetecteerd werden. Hierdoor is het aantal votes per punt lager dan wanneer er veel lijnen (waaronder ruis) gedetecteerd zouden worden. Ook is het aantal punten in de puntenwolk lager dan in het vorige gebouw (van 10 000 naar 2500) waardoor het kan zijn dat projecties niet teruggevonden worden in de puntenwolk. Figuur 8.13:
Figuur 8.14:
De projecties op de puntenwolk.
Een ander aanzicht van de projecties.
8.5 Ander voorbeeld
49
3D model Autocad Figuur 8.15:
Het AutoCAD model, men ziet hier al duidelijker waar elk punt zit op de foto. Het raam en één van de twee garagas worden ook getoond in het model. Het is al een grote verbetering van het vorige model.
Hoofdstuk 9 Besluit Het doel van deze thesis was het bekomen van een 3D model van een gebouw in AutoCAD met behulp van foto's, wat als vervanging zou dienen voor het opmeten van de gebouwen met een tachymeter. Het is ons gelukt in beperkte mate maar het uiteindelijke model is niet van voldoende kwaliteit opdat het zou kunnen gebruikt worden door landmeters. Dit komt doordat bij de lijndetectie niet elke lijn gedetecteerd wordt en dat er ook veel ruis gedetecteerd wordt. Deze 2 problemen zorgen voor een slecht model, aangezien we met deze lijnen de belangrijke punten van het gebouw gaan bepalen. De lijndetectie werkt het best indien het gebouw geen dakpannen heeft en indien er geen bomen of andere planten voor het gebouw staan, ook is het best als de lichtinval overal ongeveer gelijk is op het gebouw. Indien aan deze voorwaarden voldaan zijn dan kan men een model verkrijgen dat al aanzienlijk beter is dan anders, echter zal het nooit de nauwkeurigheid kunnen benaderen van een total station. Tenzij men een nieuwe lijndetector gebruikt die een zeer hoge nauwkeurigheid heeft en heel weinig ruis detecteerd. Alles is dus afhankelijk van de lijndetectie.
Bibliogra e [1] J. Kittler C. Galambos, J. Matas. Progressive probabilistic hough transform for line detection. In Computer Vision and Pattern Recognition, 1999. IEEE Computer Society Conference on., volume 1, 1999. https://dspace.cvut.cz/bitstream/handle/10467/9451/ 1999-Progressive-probabilistic-Hough-Transform-for-line-detection. pdf?sequence=1.
[2] J. Canny. A computational approach to edge detection. Pattern Analysis and Machine Intelligence, IEEE Transactions on, (6), 1986. http://pdf.aminer.org/000/ 361/016/an_inherent_probabilistic_aspect_of_the_hough_transform.pdf. [3] Brian Curless Changchang Wu, Sameer Agarwal and Steven M. Seitz. Multicore bundle adjustment. CVPR, 2011. http://cs.unc.edu/~ccwu/siftgpu. [4] H. Kalviainen et ali. Probabilistic and non-probabilistichough transforms: overview and comparisons. Image and Vision Computing, 13(4), 1995. http://www.cs.cuhk. hk/~lxu/papers/journal/KHXU95rht.PDF. [5] Van Gool Luc et ali. 3d from line segments in two poorly-textured, uncalibrated images. In 3rd international symposium on 3D data processing, visualization, and transmission, 2006. [6] E. Nadernejad H. Hassanpour, S. Sharifzadeh. Edge detection techniques: Evaluations and comparisons. Applied Mathematical Sciences, 2(31), 2008. http://www.m-hikari.com/ams/ams-password-2008/ams-password29-32-2008/ nadernejadAMS29-32-2008.pdf.
[7] P.V.C Hough. Method and means for recognizing complex patterns, 1962. http: //www.freepatentsonline.com/3069654.html. [8] Smeulders A.W.M. Jonk A. An axiomatic approach to clustering line-segments. In Proceedings of the Third International Conference on Document Analysis and Recognition, 1995. [9] Maarten Vergauwen Luc Van Gool. Web-based 3d reconstruction service. Machine Vision and Applications, 17(1), 2006. http://homes.esat.kuleuven.be/~visit3d/ webservice/v2/webservice.pdf.
52
BIBLIOGRAFIE
[10] Niels Van Malderen. Human motion capturing: Visual hull reconstruction. Master's thesis, Campus De Nayer, 2010. http://www.eavise.be/mastertheses/ VanMalderen.pdf. [11] Richard Szeliski Noah Snavely, Steven M. Seitz. Photo tourism: Exploring image collections in 3d. ACM Transactions on Graphics, 2006. http://phototour.cs. washington.edu/Photo_Tourism.pdf. [12] Richard Szeliski Noah Snavely, Steven M. Seitz. Modeling the world from internet photo collections. International Journal of Computer Vision, 2007. http: //phototour.cs.washington.edu/ModelingTheWorld_ijcv07.pdf. [13] A Zisserman R Hartley. Multiple view geometry in computer vision. Cambridge Univ Press, 2000. http://users.rsise.anu.edu.au/hartley/public_html/Papers/ CVPR99-tutorial/tutorial.pdf. [14] Peter E. Hart Richard O. Duda. Use of the hough transformation to detect lines and curves in pictures. Communications of the ACM, 15(1), 1972. http://www.dtic. mil/dtic/tr/fulltext/u2/a457992.pdf. [15] Roger Y. Tsai. A versatile camera calibration technique for high-accuracy 3d machine vision metrology using o-the-shelf tv cameras and lenses. IEEE Journal of robotics and automation, RA-3(4), August 1987. http://vigir.missouri.edu/~gdesouza/ Research/Calibration/Calibration-Tsai.pdf. [16] Changchang Wu. Siftgpu: A gpu implementation of scale invaraint feature transform (sift)., 2007. http://cs.unc.edu/~ccwu/siftgpu. [17] Changchang Wu. Visualsfm: A visual structure from motion system., 2011. http: //homes.cs.washington.edu/~ccwu/vsfm/.
