ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ DIPLOMOVÁ PRÁCE

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ

DIPLOMOVÁ PRÁCE

PRAHA 2012

Jaroslav ŠEDINA

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ OBOR GEODÉZIE A KARTOGRAFIE

DIPLOMOVÁ PRÁCE POROVNÁNÍ 3D SKENOVACÍCH METOD S MRAČNEM BODŮ, VYTVOŘENÝM OBRAZOVOU KORELACÍ V DIGITÁLNÍ FOTOGRAMMETRII

Vedoucí práce: Prof. Dr. Ing. Karel PAVELKA Katedra mapování a kartografie

červen 2012

Jaroslav ŠEDINA

ZDE VLOŽIT LIST ZADÁNÍ

Z důvodu správného číslování stránek

ABSTRAKT Diplomová práce se zabývá teorií SIFT algoritmu, RANSAC, SFM a PMVS. Oblast computer vision prochází v dnešní době bouřlivým vývojem a její dnešní technologie umožňují rekonstrukci povrchu objektu. Práce se zabývá i praktickým využitím dostupných technologií tvorby 3D modelů pro účely památkářské péče.

KLÍČOVÁ SLOVA Fotogrammetrie, počítačové vidění, SFM, RANSAC, SIFT algoritmus, zpracování snímků, mračno bodů, tvorba 3D modelů, památková péče.

ABSTRACT This diploma project deals with the theory SIFT algorithm, RANSAC, SFM and PMVS. Computer vision is rapid developed area and technology of computer vision allows reconstruction of object surface. The work deals with the practical use of available technology of 3D models for Cultural Heritage.

KEYWORDS Photogrammetry, computer vision, SFM, RANSAC, SIFT algorithm, image processing, points clouds, 3D modelling, cultural heritage.

PROHLÁŠENÍ Prohlašuji, že diplomovou práci na téma „Porovnání 3D skenovacích metod s mračnem bodů, vytvořeným obrazovou korelací v digitální fotogrammetrii“ jsem vypracoval samostatně. Použitou literaturu a podkladové materiály uvádím v seznamu zdrojů.

V Praze dne

...............

.................................. (podpis autora)

PODĚKOVÁNÍ Chtěl bych poděkovat vedoucímu práce Prof. Dr. Ing. Karlu Pavelkovi za připomínky a pomoc při zpracování této práce. Dále bych chtěl poděkovat za projevenou důvěru při svěření tohoto úkolu a za bezproblémový přístup k vybavení laboratoře.

Obsah Úvod

9

1 Projekty na téma optického skenování 1.1

10

Využití optického skeneru při dokumentaci římského bronzového pásu a fresek na hradě Quart a v kostele Sv. Maxima . . . . . . . . . . . . 10

1.2

Dokumentace památek optickým skenerem . . . . . . . . . . . . . . . 11

1.3

Využití základnového skeneru s projektorem pro přesné práce . . . . . 12

1.4

Možnost využití optických skenerů v památkové péči pro negeodetické obory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.5

Využití a vyškolení dobrovolníků pro práci v památkové péči . . . . . 14

1.6

Možnosti 3D skenování volně a cenově dostupnými technologiemi . . . 15

1.7

Dokumentace pokladu Essenské katedrály

1.8

Tvorba dokumentace s využitím voxelů . . . . . . . . . . . . . . . . . 17

1.9

Dokumentace předmětů z doby kamenné systémem ATOS II . . . . . 18

. . . . . . . . . . . . . . . 16

1.10 Skenovací systém s více než dvěma kamerami . . . . . . . . . . . . . . 19 2 Cíle projektu

20

3 Tvorba mračna bodů obrazovou korelací

21

3.1

SIFT (scale-invariant feature transform) . . . . . . . . . . . . . . . . 21 3.1.1

Detekce klíčových bodů . . . . . . . . . . . . . . . . . . . . . . 21

3.1.2

Filtrace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1.3

Přiřazení orientace . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.4

Deskriptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2

Propojení klíčových bodů . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3

RANSAC (Random Sample Consensus) . . . . . . . . . . . . . . . . . 30 3.3.1

3.4

RANSAC - LD (Location Determination) . . . . . . . . . . . . 32

SFM (Structure from motion) . . . . . . . . . . . . . . . . . . . . . . 34 3.4.1

Model kamery . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.4.2

Epipolární geometrie . . . . . . . . . . . . . . . . . . . . . . . 39

3.4.3

Fundamentální matice . . . . . . . . . . . . . . . . . . . . . . 40

3.4.4

Lineární algoritmus (8 bodový algoritmus) . . . . . . . . . . . 40

3.4.5

Nelineární algoritmus . . . . . . . . . . . . . . . . . . . . . . . 41

3.4.6

Robustní algoritmus . . . . . . . . . . . . . . . . . . . . . . . 41

3.4.7

Výpočet dvousnímkové geometrie . . . . . . . . . . . . . . . . 41

3.4.8

Obnova structure a motion . . . . . . . . . . . . . . . . . . . . 42

3.5

Svazkové vyrovnání . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.6

PMVS (Patch-based Multi-view Stereo) . . . . . . . . . . . . . . . . . 50 3.6.1

Prvky algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.6.2

Popis algoritmu PMVS . . . . . . . . . . . . . . . . . . . . . . 52

4 Zpracování modelů

55

4.1

Pořízení snímků a příprava objektu . . . . . . . . . . . . . . . . . . . 55

4.2

VisualSFM

4.3

4.4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.2.1

Nastavení CMVS a PMVS2 . . . . . . . . . . . . . . . . . . . 59

4.2.2

Zpracování v Geomagic . . . . . . . . . . . . . . . . . . . . . . 62

4.2.3

Porovnání modelu s referenčním modelem . . . . . . . . . . . 64

4.2.4

Zhodnocení VisualSFM

Agisoft PhotoScan

. . . . . . . . . . . . . . . . . . . . . 68

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.3.1

Zpracování v Agisoft PhotoScan . . . . . . . . . . . . . . . . . 69

4.3.2


4.3.3


4.3.4

Zhodnocení Agisoft PhotoScan . . . . . . . . . . . . . . . . . . 74

Photomodeler Scanner . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.4.1

Zpracování v Photomodeler Scanner . . . . . . . . . . . . . . . 75

4.4.2


4.4.3


4.4.4

Zhodnocení Photomodeler Scanner . . . . . . . . . . . . . . . 85

5 Porovnání relativní přesnosti jednotlivých metod

86

5.1

Pořízení dat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5.2

Zpracování modelů . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5.2.1

Zpracování VisualSFM . . . . . . . . . . . . . . . . . . . . . . 86

5.2.2

Zpracování Agisoft PhotoScan . . . . . . . . . . . . . . . . . . 87

5.3

Potlačení vlivu měřítka . . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.4

Porovnání v Geomagic . . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.5

5.4.1

Porovnání VisualSFM . . . . . . . . . . . . . . . . . . . . . . 87

5.4.2

Porovnání Agisoft PhotoScan

5.4.3

Porovnání Photomodeler Scanner . . . . . . . . . . . . . . . . 90

. . . . . . . . . . . . . . . . . . 88

Porovnání v Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Použité zdroje

94

Seznam symbolů, veličin a zkratek

96

Seznam příloh

97

A Obsah datového disku

98

ČVUT Praha

ÚVOD

Úvod Geodetické metody byly a jsou hlavním nástrojem pro tvorbu dokumentace památkových objektů. Mezi hlavní geodetické disciplíny, které zde našly uplatnění patří fotogrammetrie a laserové skenování. Zároveň je třeba věnovat pozornost oblasti computer vision, která dnes prodělává bouřlivý vývoj. Mezi hlavní produkty computer vision patří software, který kompletně zpracovává pořízené snímky. Záběr těchto software je od tvorby panoramatických snímků, kalibrace kamer až po rekonstrukci povrchu objektu. Tato práce má za úkol porovnat fotogrammetrickou metodu a metodu computer vision tvorby 3D modelu objektu. Porovnání se bude týkat časové náročnosti metody a reálně dosažitelné přesnosti 3D modelu.

9

ČVUT Praha

1

1. PROJEKTY NA TÉMA OPTICKÉHO SKENOVÁNÍ

Projekty na téma optického skenování

1.1

Využití optického skeneru při dokumentaci římského bronzového pásu a fresek na hradě Quart a v kostele Sv. Maxima

Salonia, P., Scolastico, S., Marcolongo, A., Messina, L., Pozzi, A. Three Focal Photogrammetry Application for Multi-Scale and Multi-Level Cultural Heritage Survey, Documentation and 3D Reconstruction. In: CIPA 2009: 22. Symposium, 11. - 15. října 2009, Kyoto, Japonsko.

Práce se zabývá výsledky „fotoskenery“ , které byly použity pro práce malého rozsahu (dokumentace římského bronzového pásu „Balteus “ z druhého století) i pro práce většího rozsahu (dokumentace fresek na hradě Quart a v kostele Sv. Maxima). Pro výpočet mračna bodů byl užit „triplet“ snímků, kde se zařízením ZScan dosáhlo milimetrové přesnosti pro práce většího rozsahu a submilimetrové přesnosti při skenování římského bronzového pásu. Tento příspěvek ukázal potenciál optického skenování.

Obr. 1.1: Římský bronzový pás

Obr. 1.2: Fresky v kostele Sv. Maxima

10

ČVUT Praha

1.2


Dokumentace památek optickým skenerem

Řezníček, J., Pavelka, K. Culture Heritage Preservation with Optical Correlation Scanner. In: CIPA 2009: 22. Sympozium, 11. - 15. října 2009, Kyoto, Japonsko.

V příspěvku je představen optický korelační skener (OKS ), kterým byl zpracován gotický portál v kostele Sv. Petra a Pavla v Bílině, barokní reliéf ukřižování Ježíše Krista ve Velenicích a barokní kamenná socha anděla vytvořená Matyášem Bernardem Braunem. V práci jsou zmíněny dva moduly OKS, modul pro opravu snímků (na stereo páry) a algoritmus pro vyhledání bodu na stereodvojici (zde popsáno pro více snímků najednou) užitím obrazové korelace. Část článku je zaměřena na popis software pro práci 3D daty, jsou zde uvedeny výhody a nevýhody software Raindrop Geomagic Studio, Meshlab, VripPack a VxScan.

Obr. 1.3: Optický korelační skener (OKS)

Obr. 1.4: Model reilefu

11

ČVUT Praha

1.3


Využití základnového skeneru s projektorem pro přesné práce

Valanis, A., Georgopoulos, A., Sofronidou, M., Hadzilacos, Th. SCANNING FOR MICRONS. In: CIPA 2009: 22. Sympozium, 11. - 15. října 2009, Kyoto, Japonsko. An example of a two dimensional pattern is a grid or a line strip Práce se zabývá využitím základnového skeneru projektorem projektor pattern. A camera iss used to record theSL2, deformation of the pattern and a fairly complex algorithm is used to calculate the distance each point the pattern. One reason the promítá na skenovaný objekt vzor. Skener bylatpoužit prointvorbu modelu váz z for doby complexity is ambiguity. Structured light scanning is still a very area ofuresearch many research papers published kamenné (5 260 let př. n. l.), které bylyactive nalezeny osadywith Dispilio v severním Řecku. each year. The advantage of structured light 3D scanners is browser. The visitor of relevant webpage (Figure may structured light each scan and run through the data to check for data speed.na Instead ofthe scanning one point at a10)time, Při užití skeneru byl kladen důraz hlavně kalibraci kamer, kalibrace byla klíčová choose which vase to inspect with the help of the viewer. completeness once an object is finished. scanners scan multiple points or the entire field of view at once. reduces eliminatespodmínky the problem při of distortion from pro přesnost skeneru. Dále byl kladenThis důraz na orsvětelné skenování, 4. PRESENTATION OF RESULTS motion. Some systems that employ such methods enable the scanning moving objects in real-time. In most cases such Once the scans are and stabilitu, processes the meshes may be zajištěna nezávislým osvětlením, aby bylo možné zejména naacquired jejich ta byla systems have a relatively narrow field of view that may range exported in OBJ format along with the respective texture images. All of the data are imported in GSI software, the scans from a few centimeters to a couple of meters, based on the získat kvalitní snímky užití obrazové korelace a pro tvorbu kvalitní textury. are aligned, the individual OBJs are exportedpro so as to retain the components of the system and the calibration process. texture images for the next stages of processing, and all of the registered scans are merged. The merged data are also exported and all of the data are imported in 3D Studio Max where texture data are combined and rendered into texture maps (Figure 8). The resulting texture maps are processed in Photoshop so as to correct for tone differences and merge all of the data.

For the system initially be pe interior orientat position and the calibration boar (Figure 2). The and the system actually involve light are projec are alternating b system calculat these patterns o (up to 150µm) surface (Figure manufacturers i

Skener dosahoval neuvěřitelné přesnostiForažthe50 𝜇𝑚. work carried out in this paper, a stereoscopic structured light scanner has been used. The XYZRGB Inc. SL2 system (Figure 1) comprises of off-the-shelf components. A common LCD projector is used to project the alternating patterns of light 10: The webpage interfaceeither two DSLR’s or two on to theFigure object. Two cameras, 5. CONCLUDING REMARKS It has been demonstrated that the 3D digital representation of small objects at high accuracies and resolutions is feasible, provided the suitable instrumentation and procedures are followed. However, all problems have not been sorted out yet and a lot of research in this field remains to be carried out. On the other hand although structured light systems for acquiring 3D information and texture is definitely a cutting edge technology, the road to perfection is long. A lot of parameters affect decisively the final result and it greatly depends on the size, shape and the material of the object of interest. The photographic set up is of significance and a lot of care should be devoted to its perfection. All in all and despite the various difficulties, the result is rewarding and it has already proven useful both for electronic visitors and experts.

Figure 1: The XYZRGB Inc. SL2 Scanner components Figure 8:Sample of a rendered object

Obr. 1.5: Model vázy

Acknowledgements

machine are mounted rigid base, which in Obr.vision 1.6:cameras, Optický skenerons aprojektorem

The support of the Computer Technology Institute and the Open turn sits on topwho of have a sturdy photographic tripod. The distance University of Cyprus, undertook the whole project is acknowledged. Thecameras intellectual property rights according for all vasesto the size of the between the may be varied, belong to theofUniversity Thessaloniki. the financial object interest.of The systemFinally is driven via a laptop with support of the European Commission, European Social Fund proprietary software that carries out the required processing for and the Greek Operational Program “Information Society” are the structured light data. gratefully acknowledged.

References

Figure 9: The environment of the VRML viewer The final 3D models have been published in VRML format which is most easy to share over the internet. The main effort during processing is to make the surface as light as possible, i.e. less polygons, and apply a rich texture so as to have a detailed result in a relatively low size file. Cosmoplayer (Figure 9), has been selected as the suggested plug-in for the visitors of the webpage who wish to view the models through their internet

Dispilio, The lake settlement, Kastoria Prefecture. http://kpekastor.kas.sch.gr/the_lake/lake/history.htm (last accessed August 2009). The archaeological digs of Dispilio, www.dispilio.org, (last accessed August 2009). Valanis, A. 2008. The Geometric documentation and production of 3D digital copies of pottery from the collection of the Dispilio 12 Lake Settlement in Kastoria for their presentation via the web. Technical Report, pp.16 (in Greek).

Once the syste reliable. Howe behaviour of li should be given use of suitable cameras is reco

3. SCAN

Dispilio is a vi (Figure 4). Like of the lake of K its southern ban Stone Age, i.e. the C14 method found during Chourmouziadi University of T by chance in 1 the lake retreat settlement http: Prof. Chourmou findings and ha in the area and s

ČVUT Praha

1.4

Možnost využití optických skenerů v památkové péči pro negeodetické obory

Boochs, F., Heinz, G., Huxhagen, U., Müller, H. LOW-COST IMAGE BASED SYSTEM FOR NON-TECHNICAL EXPERTS IN CULTURAL HERITAGE DOCUMENTATION AND ANALYSIS. In: CIPA 2007: 21. Sympozium, 1. - 6. října 2007, Athény, Řecko.

Příspěvek se zabývá možností využití optických skenerů pro negeodetické obory, pro lidi, kteří neznají fotogrammetrické základy. Hlavním problémem řešeným v článku bylo, jak se vyvarovat problému nevhodně pořízených snímků (nevhodné úhly protnutí, přeexponované snímky). Byl navržen základnový skener, kde snímky jsou díky základně prakticky stereodvojicí snímků. Dále bylo navrženo pořizovat HDR (high dynamic range) snímky. Takto jednoduchý pracovní postup může využít každý člověk. Tento optický skener byl využit při pořizování dokumentace středověkých jeskyní, vytesaných do vápencové skály. Tyto jeskyně se nacházejí na Krymu. Druhým projektem byla Porta Nigra v Trevíru, Německo. Zde byl skener porovnán spolu

XXI International CIPA Symposium, 01-06 October

ational CIPA Symposium, s01-06 October, Athens, Greece metodou laserového skenování

nical experts on their own ing sections a complete nd software components sual properties of cultural wo case studies will show ed in practice to achieve


a tachymetrickým měřením. Zde měl optický skener

výhodu, neboť je schopen zaznamenat prostorovou a vizuální 3D laser scanning covers the (texturu) recorded object informaci by millions of

relative orientation approach allowing to calculate the true orientation without large interaction of the user. So, correct v jednom kroku. photogrammetric functionality is assured without special knowledge of the user and without largely investing into the technical equipment.

points and gives good visual impression and a digital reproduction of even complex and structured surfaces. Nevertheless, edge effects and noise of range measurements downgrade the usage for the intended purpose as joints in the point clouds did not appear in a usable way.

Boochs, F.; Eckha system for the col VII. International

ATION STATION -

Böhler, W.; M Photogrammetry Proceedings of Geoinformatics, G

view off-the-shelf digital ntional PC-equipment are mmetric tasks (Drap 2001, Even stereo viewing is no with different technical gone big improvements in ution and image quality. a reasonable price. When ce bar of variable length

bility of these techniques ork flow and the software together with efficient, equipment. It is necessary application scientists and ly then this technique will user allowing to widely n the appropriate field of

n process images have to steps, determining the and, in addition, being

Boochs, F.; Heinz Documentation o recording techniq Virtual Reality, A Nicosia.

Böhler, W.; Borda of Sisupalgarh in C GIS Monthly, Jun

Figure 1. Single-camera-system with space bar

Obr. 1.7: Optický skener

The designed more or less fixed stereo configuration could be seen as a limitation factor and as being not flexible enough, but it avoids problems for an end user being not familiar with the rules of photogrammetry. And this is of great importance as long-term experiences with non-technical users have shown. The lack of photogrammetric knowledge often ends up in an inappropriate selection of the view points for the cameras resulting in unreliable geometrical constellations with 13 corresponding wrong spatial data. 2.2 Software With respect to the software components all standard

Figure 8. The Porta Nigra, Trier / Germany, UNESCO World Heritage Site

Obr. 1.8: Porta Nigra

In addition, stereo photogrammetry was tested during the project at a section of the Porta Nigra. The evaluation of the image material was done with the DISTA application whereas some exemplary contour plans were evaluated (see Figure 8). It was reflected that photogrammetry is the most suitable technique to produce base maps for the work of historians. The desired procedure is to produce basic contour maps which can be completed and refined by specialised scientists by evaluation directly at the object’s surface from scaffolding. 4. CONCLUSIONS

Drap P., Grusse Photogrammetric Orthoimage Gene Int. Symposium, C

Heinz, G., 2002. C use non-metric archaeological exc - Close-Range Ima

Henze, Siedler, Verfahren der Stereoauswertesys

ISPRS, 2007: Int Remote Sensing, Analysis and App Heritage Doc http://www.comm 2007)

ČVUT Praha

1.5


Využití a vyškolení dobrovolníků pro práci v památkové péči

Chandler, J.H., Bryan, P. COST-EFFECTIVE ROCK-ART RECORDING IN A PRODUCTION ENVIRONMENT: IS THERE A WIDER MESSAGE?. In: CIPA 2007: 21. Sympozium, 1. - 6. října 2007, Athény, Řecko.

Článek se zabývá možností využití a vyškolení dobrovolníků v oblasti památkové péče. Projekt se zabýval dokumentací kamenných rytin v severní Anglii. Jeli-

PA Symposium, 01-06 October, Athens, Greece kož měřiči byli vybráni z řad běžného obyvatelstva s různou technickou zdatností,

bylo potřeba využít jednoduchou, levnou a dostatečně přesnou metodu pro dokumentaci kamenných rytin. Jako metoda byla zvolena stereodvojice snímků (snímky

texture from such models, leaving just thekamery hostNikon rockCobylythe mírně konvergentní). Pro pořízení snímků byly zakoupeny

surface, has proved of enormous benefit to the volunteers in attempting to understand the underlying carvings (figure rem5). projektu bylo získatas dobrovolníky pro sběr dat, kdy během let 2005 až 2007 However, with laser scanning further tools, bylopreferably zdokumentováno automated, 1 500 kamenných rytin. byli vyškoleni pro needDobrovolníci development andpráci dissemination to enable the end-user extract any) manoject is how a s jednoduchými fotogrammetrickými programy (např.toTopcon PI-3000 a byli tak made features from those occurring naturally, based on learned how schopni provést kompletní dokumentaci kamenných rytin od snímání až po výstupy such objectively acquired 3D data sets. essing tasks at volunteers v podobě modelu reliéfu a ortofota. nly, and a ty for creating lar sites. The rd” and data the future, if le about the nd then carry hemselves. It oject in 2007, ill have been w very simple ck outcrops. the six teams nd they now Figure 5 Old Bewick inrytiny untextured form, as Obr. rock-art 1.9: Model panel kamenné hophotos and processed by Joe Gibson using Topcon PI-3000 software Some of the elopers of the 14 n use, and, in 6. CONCLUSION n and Leica that it should This paper has demonstrated that a fast, cost-effective olpix 5400, které byly kalibrovány v Loughboroughské univerzitě. Původním zámě-

nale des Sciences Geographiques (ENSG), Institut Geographique National 6 - 8 avenue Blaise Pascal Cite Descartes, Champs-sur-Marne Praha 1. PROJEKTY NA TÉMA OPTICKÉHO SKENOVÁNÍ NE LA VALLEE CEDEX ČVUT 2, France-(mahzad.kalantari,[email protected]) CNRS 6597, Polytech’Nantes - rue Christian Pauc BP 50609 - 44306 Nantes cedex 3 France

1.6

Možnosti 3D skenování volně a cenově dostup-

omputer Vision, Archaeology, Cultural Heritage, Acquisition, Three-dimensiona Modelling

nými technologiemi Kalantari, M., Kasser, M. IMPLEMENTATION OF A LOW-COST PHOTOGRA-

eveloped for measuring shards ofMETHODOLOGY old ceramics, foundFOR in archaeological yards.OF It CERAMIC is based on FRAGMENTS. a MMETRIC 3D MODELLING ammetric and computer vision freeware completed by home-made software developments. The In:images, CIPA 2007: Sympozium, 1. - 6. 2007, Athény, Řecko. r the acquisition of the and the21. processing software forříjna the various steps. This software is ng from computer vision community, and from more classical photogrammetry. Some intermediate of the present work being a very dense cloud of points describing the geometry of the surface of the Práce představuje sestavení 3D skeneru z volně technologií, které many off-the-shelf drawing commercial software, depending on the needs of dostupných the archaeologists. jsou volně dostupné v obchodě (kamera, osvětlení, ...) a na internetu (volně doCTION On the corners of the rotating table, are fixed four small spotstupné programy). se skládal z kamery a otočné na with kterou byl přilights, soSkener as to provide a strong illumination to desky, the shard shape of the shards pevněn of old skenovaný nearly noobjekt. shadow. spotlights rotate with the shard, so that referenční NaThese otočné desce byly vyznačeny body určující hand, with methods that are the shadows are moving with it, which appeared as a key feature systém. Snímky pořizovány ve dvou řadách. Pro výpočetdesk bodů mračna byla ch have been led to automate for thebyly efficiency of the processing used. An additional light , but the methods published providesdvojice a zenithal light, výsledné that actually does bylo not rotate with the využita vertikální snímků, mračno obdrženo spojením jedctive of simplicity and very shard, but this point apparently did not make any trouble in the mpel et al., 2002), required notlivých vertikálních snímků (vyznačené data process,dvojic c.f. Figure 1. do Thereferenčního high level ofsystému illuminations ob- body na scussed with various archaetained allows for a good depth of field, highly necessary so as to otočné desce). Takto vytvořený 3D skener dosáhl přesnosti pod 1 𝑚𝑚, což bylo waitings, a methodology has avoid any fuzziness in the more distant parts of the shard. A first ing specifications : shledáno jako archeologické jako je například získávání obrysů set postačující of images ispro acquired with theúčely, camera placed slightly lower o than the shard, a picture being acquired every 30 of the rotating objektů a rovinná prezentace pro znázornění dekorace objektů. acquire the data table. In a second set of pictures, the camera is placed higher than e data the shard. Such an acquisition device provides a set of 24 images, been rejected, as up to now ive of low cost, and here a ssical photogrammetry, and n community as well, have

THE PROJECT

ting table (television stand), to a PC, a photographic trinsional calibrated object that camera and the PC are not are henceforth current tools o demonstrate, so that they ny archaeological team.

y fixing the shard on the ro. In the present experiment, iers have been used (Fig. 2) n the table. On the table is pots (2 mm diameter) reguargets, and whose geometry photogrammetric survey (cf as close as possible (a few as this helps a lot in the fur-

Figure 1: The device used for image acquisition. On the left, the Obr. 1.10: 3D skener využívající obrazové korelace camera on its tripod 12 in low and 12 in high position of the camera. A mobile sheet of white paper is put behind the 15 shard with respect to the camera for each acquisition, so that in each image there are nearly no visible details other than the shard itself, its fixation, and a few of the 12 targets spots.

ČVUT Praha

1.7


Dokumentace pokladu Essenské katedrály

sium, 01-06 October 2007, Athens, Greece Przybilla, H.-J., Peipe, J. 3D MODELING OF HERITAGE OBJECTS BY FRINGE

PROJECTION AND LASER SCANNING SYSTEMS. In: CIPA 2007: 21. Sympo-

OF HERITAGE OBJECTS zium, 1. - 6. října 2007, Athény, Řecko. N AND LASER SCANNING SYSTEMS

Przybilla a, *, J. Peipe b

Poklad Essenské katedrály je jedna z nejkomplexnější sbírky středověkého umění.

K dokumentaci využity dvaGermany principy získávání 3D dat, laserové skenování Geoinformatics, Bochum University of byly Applied Sciences, [email protected] (MicroScribe a MicroScan) a základnový skener s projekcí strukturovaného světla rtography, Bundeswehr University Munich, Germany (triTOS), dále byla použita SLR kamera Nikon D2Xs pro pořízení digitálních snímků [email protected] pro texturu modelu. Přesnost snímání 3D dat byla u obou technologií rovna 0, 2 𝑚𝑚. Tento projekt se zabýval možností prezentace modelů objektů na internetu, zde byla

scanning, Modeling, Documentation

řešena otázka redukce objemu dat. Zajímavých výsledků bylo dosaženo při 1,5% až 3% objemu původních dat při pokrytí modelu texturou. Dále byla testována možnost nastavení systému triTOS pro skenování různě velkých objektů, kde byla využita

the few collections of medieval art completely preserved in the course of ses, crowns, swords, statues, precious délka manuscripts, základy odand 50 reliquaries. 𝑚𝑚 až poThese 300 𝑚𝑚, což odpovídá vzdálenosti měření 400 𝑚𝑚 ial, and complexity. In the paper, ideas and concepts for recording the až 1000 𝑚𝑚.and Účelem projektuare bylo pořídit as photogrammetry, fringe projection laser technique reported on.3D dokumentaci Essenského pokladu pro s calibration aspects, difficulties of data acquisition and processing are XXI International 01-06 October 2007, Athens, Greece historické bádání CIPA i pro Symposium, veřejnost. d.

or the ation, mmon al 3D photoations sfully on of

of the al 3D dral is art in vent's er the n has Figure (left) and digital image10th (right) Figure 7. Digitizing the ceremonial sword Figure5.1.Scan Otto-Mathilden-Cross, century, different pieces materials, 44.5 cmObr. high,1.11: 29.5 cm wide (© Martinkříž Engelbrecht) Otto-Matyldin on is Obr. 1.12: can triTOS Specifications of the data acquisition be found in Tab. 1. easure 3. STATE OF THE PROJECT some ElfenbeinLudgerusCeremonial pyxis kelch sword (Figs. As mentioned in chapter 2, the Golden Madonna of the base16length 50 mm 50 mm 300 mm ing in cathedral's treasure was digitized and modeled at first. In the meantime, some more works of art have been surveyed (Figs. 6 measuring d. The & 7): 400 mm 400 mm 1000 mm distance llenge - the so-called Elfenbeinpyxis, an elliptical box (10.4 cm and survey depth 90 mm 90 mm 180 mm to be 12.5 cm in diameter, 8.8 cm high), made of ivory, originating

During the subsequent image acquisitions, the focus remained cts. Voxel methods consume large fixed. mple 512³ bytes (128 mbytes) for a in each direction). Since there are owever, this problem is becoming 1. PROJEKTY NA TÉMA OPTICKÉHO SKENOVÁNÍ representations is becomingČVUT more Praha

can be easily acquired by shape which the shape of the1.8 objects Tvorba is dokumentace s využitím voxelů he volumes. The intersection of e images gives a good estimation Y., Sinram, O. VOLUMETRIC RECONSTRUCTION OF CULTURAL HEoximate model is calledKuzu, the visual atusik et al, 2000). Shape from RITAGE ARTIFACTS. In: CIPA 2003: 19. Sympozium, 30. září - 4. října 2003, d robust; however the concavities Figure 1: Camera calibration and control point determination ject cannot be recovered with this Antalya, Turecko. ing region doesn’t completely 2.2 Image Orientation work to recover the shape of the In order to model the objects accurately, the images should be is concentrated on voxel coloring Metoda se zabývá tvorbou modelů historických památek s využitím oriented. As mentioned above, we determined some natural objemových 1997), (Culbertson et al, 1999), control na points on the voxelů. objects surface, we should not vputnasnímání ob. These algorithms modelů use color založených principu Principsince metody spočívá markings on an historical artifact. They were defined in an rface points from the other points arbitrarily chosen coordinate system, since there is no opraveny need to o distorzi). kolem dokola a svazkovém vyrovnání snímků (ty jsou act that surface points jektu in a scene have the coordinates in a specific higher-level coordinate r) colors in the input images. Modelovaný system.vzniká postupným promítáním voxelů podél přímky zobrazení veral tools to refine the object’s objekt The imagestestováním, were adjustedzda in atyto bundle blockpatří adjustment process. do snímku a následným voxely do modelovaného objektu, We used enough tie points in all images in the circular camera ers is as follows: In chapter 2 the setup je to ideálně perform jednobarevné). a bundle blockPokud adjustment, covering all jsou smazány. do pozadí (které patří do pozadí, described. The image či orientation images. Figure 2 shows an OpenGL visualization of the reconstruction of the model using přiWe které jsou z very jednich dat získávány o objektu situation. achieved accurate results for 3D the informace image ue will be described inJedná chapterse3,o metodu, orientations, informacemi. using the previously calibrated camera. re introduced as well. spolu Also there, s jeho obrazovými ver visibility information will be information will be enhanced with e surface normal vector of a voxel wing direction of the image. In ithm is explained.

QUISITION SETUP

ur experiment is simple, we use a r to acquire still images of the calibration object to compute the rs of the camera. We place the kground. Image segmentation is a al hull of the object. In order to background pixels we place the ous blue background. We capture esulting in a circular camera setup.

and Determination of Control

the camera should be calibrated. standard CCD video camera with amera can be fixed but we cannot d since the last use. Hence, we several images with a special

Obr. 1.13: Schéma snímků objektu po vyrovnání 3. VOXEL-BASED ALGORITHMS 3.1 Shape from Silhouette Shape from silhouette is a well-known approach for recovering the shape of the objects from their contours. This approach is popular in computer vision and in computer graphics due to its fast computation and robustness. As a precondition of volume intersection algorithms, the contour of the real object must be extracted from input images. In this experiment a monochromatic blue background was used

Obr. 1.14: Skenovaný objekt, model s texturou, model bez textury

17

ČVUT Praha

1.9


Dokumentace předmětů z doby kamenné systémem ATOS II

Boehler, W., Boehm, K., Heinz, G., Justus, A., Schwarz, Ch., Siebold, M. DOCUMENTATION OF STONE AGE ARTIFACTS. In: CIPA 2003: 19. Sympozium, 30. září - 4. října 2003, Antalya, Turecko.

V údolí středního Rýna se nachází oblast paleolitického osídlení. Nacházejí se zde různé kamenné nástroje, které jsou sbírány soukromými sběrateli. Aby bylo možné tyto nálezy využít k výzkumu a nenarušit tak soukromé vlastnictví, bylo přistoupeno k vytvoření digitální dokumentace těchto nálezů. Jedná se o databázi objektů, kdy je vytvořena 3D dokumentace objektu a spolu s ní se určují další parametry objektu (materiál, místo nálezu, vlastník,...). Jedná se tedy o kompletní GIS databázi objektů a nalezišť. K 3D dokumentaci byl použit systém ATOS II, což je základnový skener s projektorem strukturovaného světla, který na objekt promítá světelný vzor, který je patrný na obr. 1.15. Přesnost skenování se pohybovala kolem 0, 01 𝑚𝑚. Projekt dále řešil dostupnost dokumentace prostřednictvím internetu, tak aby objekty mohly být podrobovány výzkumu a aby byly přístupné široké veřejnosti. Dále byla řešena otázka automatizace tvorby dokumentace, kde byly automaticky generovány hrany objektu, což nahrazuje ručně tvořenou dokumentaci objektu.

Obr. 1.15: Objekt, promítnutý vzor na objektu, 3D model, vygenerované hrany

18

ČVUT Praha

1.10


Skenovací systém s více než dvěma kamerami

Po-Chia Yeh, Jiann-Yeou Rau CLOSE-RANGE OBJECT 3D SURFACE MODELING USING MULTI-CAMERA AND MULTI-IMAGE MATCHING. In: ACRS 2010: 31. Sympozium, 1. - 5. listopadu 2010, Hanoj, Vietnam.

Práce se zabývá navržením a testováním vícekamerového skenovacího systému. Na tyči dlouhé 1, 5 𝑚 je umístěno 5 DSLR kamer SONY A850, které jsou konvergentní. Systém umožňuje provádět orientaci vnitřní i vnější všech kamer naráz, nebo provést vnitřní orientaci každé kamery zvlášť a výsledky vložit do vnější orientace. Pro vnitřní kalibraci kamer bylo použito 3D kalibrační pole, které snižuje korelaci mezi vnitřními parametry kamery. Výpočet vnitřní i vnější orientace probíhá svazkovým vyrovnáním. Při generování mračna jsou využívány všechny snímky dohromady, mračno je pak generováno spolu s texturou objektu. Přesnost navrženého systému byla textována se skenerem ATOS-I 2M, který má přesnost kolem 0, 01 𝑚𝑚. Směrodatná odchylka odlehlosti mračen byla 0, 31 𝑚𝑚, na vzdálenost snímání 1, 5𝑚 při ohniskové vzdálenosti 50 𝑚𝑚. Systém byl testován na lidské tváři a na živém objektu, zde výsledek byl spíše podprůměrný. Systém byl shledán vhodným pro objekty s plynulejším přechodem tvaru a velikostí menších objektů, jako jsou menší sochy a vázy, které se nacházejí v památkové péči.

Fig.14, Buddha statue 3D models for cultural heritage documentation. Acknowledges Obr. 1.16: Ukázka vytvořených 3D modelů sochy Buddhy We acknowledge the funding support from National Science Council (98-2815-C-006-059-E), and ATOS modeling from Dr. Li-Chang Chuang of Engineer of Investigation Lab., Aviation Safety Council, Taiwan. References 19 Al-kheder, S., Al-shawabkeh, Y. & Haala, N., 2009. Developing a documentation system for desert palaces in Jordan using 3D laser scanning and digital photogrammetry, Journal of Archaeological Science, Vol. 36, pp.537-546. Albertz, J., 2001: Albrecht Meydenbauer - Pioneer of photogrammetric documentation of the cultural heritage. Proceedings 18th International Symposium CIPA, 18-21 September 2001, Potsdam (Germany), pp. 19-25.

ČVUT Praha

2

2. CÍLE PROJEKTU

Cíle projektu Tento projekt má za úkol seznámit čtenáře s projekty dokumentace památek,

které byly vytvořeny metodami obrazové korelace a seznámit čtenáře se základy computer vision v oblasti tvorby 3D modelů.

Bude uveden postup od pořizování dat, přes jejich editaci, až po jejich zpracování v jednotlivých software. Budou uvedeny veškeré komplikace, kterým bylo čeleno a jejich řešení.

Výsledkem této práce je určení reálně dosažitelné přesnosti jednotlivých software a posouzení vhodnosti pro využití v oblasti památkové péče, ale i posouzení ekonomické stránky jednotlivých software.

20

ČVUT Praha

3

3. TVORBA MRAČNA BODŮ OBRAZOVOU KORELACÍ

Tvorba mračna bodů obrazovou korelací

3.1

SIFT (scale-invariant feature transform)

Je algoritmus počítačového vidění (computer vision), který detekuje a popisuje vlastnosti lokální obrazové funkce. Algoritmus je patentován v USA, majitelem je Univerzita Britské Kolumbie a v roce 1999 ho publikoval David Lowe.

SIFT algoritmus umí rozpoznávat charakteristické body (feature) obrazové funkce při změně měřítka, šumu a osvětlení. Takovéto body často leží v oblastech snímku s vysokým kontrastem (jakou jsou hrany objektu). Další charakteristickou vlastností pro tyto body je, že se nemění jejich relativní pozice na snímcích.

SIFT algoritmus nejdříve detekuje extrémy obrazové funkce, tyto body jsou kandidáti. Z kandidátů jsou vyloučeny nestabilní body a body na hranách, následně jsou feature spárovány v sérii snímků.

Obr. 3.1: Ukázka propojení dvou snímků, použito z [3]

3.1.1

Detekce klíčových bodů

Detekce klíčových bodů (keypoint) probíhá ve více měřítkách. Zde se využívá dvojího Gaussova rozostření, kdy se snímky od sebe odečtou. Tím je získán rozdílový

21

ČVUT Praha


snímek gaussovských rozostření (Difference of Gaussians - DoG), na kterém jsou maxima a minima klíčovými body. Rozdílový snímek gaussovských rozostření DoG 𝐷(𝑥, 𝑦, 𝜎) je obdržen:

𝐷(𝑥, 𝑦, 𝜎) = 𝐿(𝑥, 𝑦, 𝑘𝑖 𝜎) − 𝐿(𝑥, 𝑦, 𝑘𝑗 𝜎)

(3.1)

Kde 𝐿(𝑥, 𝑦, 𝑘𝜎) je konvoluce originálního snímku 𝐼(𝑥, 𝑦) s Gaussovým rozostřením 𝐺(𝑥, 𝑦, 𝑘𝜎) v měřítku 𝑘𝜎.

𝐿(𝑥, 𝑦, 𝜎) = 𝐺(𝑥, 𝑦, 𝑘𝑖 𝜎) * 𝐼(𝑥, 𝑦)

(3.2)

Obr. 3.2: Vícenásobná aplikace Gaussovského rozostření, použito z [3] Rozdíl dvou gaussovských rozostření je aproximací druhé derivace snímku (přesněji Laplaciánu).

Z obrázku 3.3 je patrné, že černé oblasti znamenají nulový rozdíl, ty nejsou předmětem zájmu, jsou to tedy hrany a velké homogenní oblasti snímku, naopak bílé oblasti, které jsou předmětem zájmu, značí velký rozdíl, jsou to oblasti vedle hran a středy malých kruhů.

22

ČVUT Praha


Obr. 3.3: DoG snímek a označení extrémů obrazové funkce, použito z [3]

Algoritmus na začátku vybere lokální extrémy v rozdílových snímcích DoG ve všech měřítkách a polohách (scale space), to je provedeno porovnáním každého pixelu v rozdílovém snímku s jeho osmi sousedy ve stejném měřítku a devíti pixely v jiném měřítku. Pokud je hodnota pixelu maximum, nebo minimum v porovnání se všemi pixely, pak je tento pixel označen jako kandidát. Tím je obdrženo maximum/minimum obrazové funkce s ohledem k měřítku a poloze pixelu.

Obr. 3.4: Sestavení scale space, použito z [3] Po odečtení sousedních snímků od sebe obdržíme DoG scale space.

23

ČVUT Praha


Obr. 3.5: Nalezené extrémy v scale space, použito z [3] Určení přesné lokalizace klíčových bodů K určení přesné lokalizace se využívá proložení trojrozměrnou kvadratickou funkcí okolními daty, jak je ukázáno na obrázku 3.6. Určení trojrozměrné kvadratické funkce je provedeno Taylorovým rozvojem funkce scale space rozdílových snímků DoG 𝐷(𝑥, 𝑦, 𝜎), kde počátkem Taylorova rozvoje kandidát:

𝐷(𝑥) = 𝐷 +

𝛿𝐷𝑇 1 𝛿2𝐷 𝑥 + 𝑥𝑇 2 𝑥 𝛿𝑥 2 𝛿𝑥

(3.3)

Kde D a jeho derivace byly určeny na kandidátovi a x(𝑥, 𝑦, 𝜎) je odsazení od tohoto bodu.

Obr. 3.6: Proložení okolí kandidáta Taylorovým rozvojem, použito z [3]

24

ČVUT Praha


̂︀ je pak dáno derivací této funkce, která se položí rovna nule. Určení extrému x

̂︀ větší, jak 0, 5 v jakémkoli směru, pak je extrém blíže jinému Pokud je odsazení x

kandidátu. V tom případě je kandidát vyměněn a interpolace je provedena v jeho poloze. Odsazení je přidáno ke kandidátu a tím je obdržen odhad interpolovaného extrému se subpixelovou přesností.

3.1.2

Filtrace

Filtrace je proces, kdy jsou odstraněny nestabilní body a body na hranách, jak je ukázáno na obrázku 3.7.

Obr. 3.7: Nalezené extrémy, odstranění nestabilních bodů, odstranění bodů na hranách, použito z [3]

Vyřazení bodů s nízkým kontrastem K vyřazení kandidáta se využívá hodnota druhého řádu Taylotova rozvoje 𝐷(𝑥), ̂︀ (extrému funkce). Pokud je hodnota menší která je vypočtena v odsazeném bodě x

než 0, 03, kandidát je vyřazen. V opačném případě je ponechán a výsledná poloha ̂︀ a měřítko 𝜎, kde y je pozice původního kandidáta v měřítku 𝜎. je dána y + x

25

ČVUT Praha


Obr. 3.8: Proložení plochy bodem s nízkým kontrastem, použito z [3] Vyřazení bodů na hranách Algoritmus obdrží velké množství kandidátů na hranách díky velkému kontrastu. Nicméně aby byla obdržena vyšší stabilita, je třeba odstranit body na hranách, které mají nejednoznačné určení své polohy na hranách. Pro špatně definované extrémy v rozdílových snímcích DoG bude platit, že křivost napříč hranou bude mnohem větší, než podél hrany, což je patrné z obrázku 3.10. K nalezení křivosti se využívá Hessova matice H : ⎡

⎤

𝐷𝑥𝑥 𝐷𝑥𝑦 ⎥ 𝐻=⎢ ⎣ ⎦ 𝐷𝑥𝑦 𝐷𝑦𝑦

(3.4)

Hodnoty Hessovy matice H jsou úměrné křivosti D. Ukazuje se, že poměr 𝑟 = 𝛼/𝛽 dvou hodnot matice H, kde 𝛼 je větší a 𝛽 je menší, je dostačující pro účely SIFT algoritmu. Stopa matice H je určena jako 𝐷𝑥𝑥 + 𝐷𝑦𝑦 , zatímco determinant je určen 2 𝐷𝑥𝑥 𝐷𝑦𝑦 − 𝐷𝑥𝑦 . Poměr 𝑅 = 𝑇 𝑟(𝐻)2 /𝐷𝑒𝑡(𝐻) je roven (𝑟 + 1)2 /𝑟, který závisí spíše na

poměru hodnot, než na jejich hodnotách. R je minimální, pokud jsou si hodnoty H rovny. Proto vyšší absolutní rozdíl mezi hodnotami H značí vyšší R a tedy i vyšší rozdíl křivosti. Proto je určen práh poměru vlastních čísel 𝑟𝑡ℎ , pokud je R kandidáta větší než (𝑟𝑡ℎ + 1)2 /𝑟𝑡ℎ , pak je poloha bodu nejednoznačně určena a bod je vyřazen. Hodnota 𝑟𝑡ℎ je nastavena na 10.

26

ČVUT Praha


Obr. 3.9: Proložení plochy bodem na hraně, použito z [3]

3.1.3

Přiřazení orientace

Každému klíčovému bodu je přiřazena jedna nebo více orientací založených na místních směrech gradientů snímku. To je klíčový krok při dosažení invariance k rotaci. Deskriptor klíčového bodu je využíván relativně k této orientaci a proto je dosaženo invariance k rotaci snímku.

Je použit gaussovsky rozostřený snímek 𝐿(𝑥, 𝑦, 𝜎) v měřítku 𝜎, takže všechny výpočty jsou provedeny měřítkově invariantně. Pro vzorek snímku 𝐿(𝑥, 𝑦) v měřítku 𝜎 je velikost gradientu 𝑚(𝑥, 𝑦) a jeho orientace 𝜃(𝑥, 𝑦) vypočtena pomocí pixelových rozdílů:

𝑚(𝑥, 𝑦) =

√︁

(𝐿(𝑥 + 1, 𝑦) − 𝐿(𝑥 − 1, 𝑦))2 + (𝐿(𝑥, 𝑦 + 1) − 𝐿(𝑥, 𝑦 − 1))2 = (︃

𝐿(𝑥, 𝑦 + 1) − 𝐿(𝑥, 𝑦 − 1) 𝜃(𝑥, 𝑦) = 𝑎𝑟𝑐𝑡𝑎𝑛 𝐿(𝑥 + 1, 𝑦) − 𝐿(𝑥 − 1, 𝑦)

27

)︃

(︃

𝑑𝑦 = 𝑎𝑟𝑐𝑡𝑎𝑛 𝑑𝑥

)︃

√︁

𝑑𝑥2 + 𝑑𝑦 2 (3.5)

ČVUT Praha


Výpočet velikosti a směru gradientu je prováděn pro každý pixel v sousedství klíčového bodu v gaussovsky rozostřeném snímku L. Je vytvořen histogram orientací s 36 položkami s každou položkou pokrývající 10 stupňů. Každý vzorek souseda v oknu rámce (neightbour window ) je přidán do histogramu a jako váha je použita velikost gradientu a gaussovská váha kruhového okna s 𝜎, který je 1, 5 krát větší než měřítko klíčového bodu. Vrcholy histogramu určují dominantní orientaci. Jakmile je histogram vyplněn, orientace odpovídající nejvyššímu vrcholu a lokální vrcholy, které odpovídají 80% nejvyššího vrcholu jsou přiřazeny klíčovému bodu. V případě přiřazení vícenásobné orientace je přidán další klíčový bod ve stejném místě se stejným měřítkem, jako originální klíčový bod pro každou přidanou orientaci.

Obr. 3.10: Přiřazení velikosti a orientace gradientu klíčových bodů, použito z [3]

3.1.4

Deskriptor

Nyní je třeba vypočítat deskriptor pro každý klíčový bod, tak aby deskriptor měl vysokou rozlišovací schopnost a byl částečně invariantní k zbývajícím proměnným, jako je osvětlení, 3D pohled, atd. Tento krok je prováděn na snímku s nejbližším měřítkem k měřítku klíčovému bodu.

28

ČVUT Praha


První soubor histogramů orientací je vytvořen na mřížce 4 × 4 pixelů s 8 položkami pro každý. Tyto histogramy jsou vypočteny z hodnot velikosti a orientace vzorku v mřížce 16 × 16 kolem klíčového bodu tak, že každý histogram obsahuje vzorek z mřížky 4 × 4 pixelů z původní podoblasti kolem klíčového bodu, jako na obrázku 3.11. Těmto velikostem je pak přiřazena váha z Gaussovy funkce 𝜎 rovnající se polovině šířky okna deskriptoru. Deskriptor se pak stane vektorem těchto hodnot histogramů. Protože je zde 4 × 4 = 16 histogramů každý s 8 položkami, vektor má pak rozměr 128 prvků. Deskriptor je tedy histogramem gradientů. Vektor je pak normalizován na jednotku délky, aby se zvýšila invariance afinní změny osvětlení. K redukci účinků nelineárního osvětlení je použit práh 0,2 a vektor je znovu normalizován.

Obr. 3.11: Výpočet deskriptoru, použito z [3]

Protože rozměr deskriptoru (128) se zdá být veliký, deskriptory s nižším rozměrem nejsou schopny provést celou řadu propojení a výpočetní náročnost je kompenzována Best Bin First (BBF) algoritmem. Delší deskriptory pokračují ve zlepšení identifikace, nicméně zde narůstá nebezpeční v podobě zvýšené citlivosti vůči distorzi a okluzi. Je prokázáno, že přesnost propojení klíčových bodů je vyšší než 50% při změně úhlu pohledu až do 50∘ . Proto je SIFT deskriptor invariantní k malým

29

ČVUT Praha


afinním změnám. Na rozlišovací schopnost SIFT deskriptoru a přesnost propojení klíčových bodů má vliv počet klíčových bodů v databázi. Bylo prokázáno, že přesnost propojení klíčových bodů klesá velmi pomalu pro velké množství klíčových bodů v databázi, což ukazuje, že SIFT klíčové body jsou velmi výrazné.

3.2

Propojení klíčových bodů

K propojení klíčových bodů se využívá eukleidovské metriky. Pro každý klíčový bod existuje normalizovaný deskriptor, na druhém snímku je nalezen klíčový bod s deskriptorem co nejpodobnějším. Jelikož je deskriptor vektor, je možno použít k porovnání dvou deskriptorů eukleidovskou metriku:

𝑚𝑒

(︁

⎯ ⎸

𝑛 → − )︁ ⎸∑︁ → − 𝑎 , 𝑏 = ⎷ (𝑎𝑖 − 𝑏𝑖 )2

(3.6)

𝑖=1

→ − − Kde → 𝑎 a 𝑏 jsou vektory o stejném rozměru.

3.3

RANSAC (Random Sample Consensus)

Konsenzus náhodného výběru (Random Sample Consensus) je metoda, která soubor měření usadí na matematický model. RANSAC je vhodný pro interpretaci a vyhlazení dat obsahující významné procento hrubých chyb. A proto je vhodnou metodou pro automatizovanou analýzu obrazu, hlavně pro řešení LDP (Location Determination Problem). Kdy určí polohu snímku v prostoru, na kterém jsou zachyceny body se známou polohou. Metodu představili v roce 1981 Martin A. Fischler a Robert C. Bolles.

Interpretace měřených dat zahrnuje dvě činnosti. Za prvé najít nejlepší shodu mezi daty a matematickým modelem (klasifikační problém) a za druhé výpočet volných parametrů zvoleného matematického modelu (problém odhadu parametrů). Často tyto činnosti nejsou nezávislé, řešení odhadu parametrů většinou předchází řešení klasifikace.

30

ČVUT Praha


Mnoho technik odhadu parametrů (např. MNČ) využívá vyhlazení dat a spoléhají na předpoklad, že maximální očekávaná odchylka od matematického modelu je přímou funkcí velikosti datového souboru. Nejsou tedy schopny odstranit hrubé chyby.

RANSAC je schopen vyhladit data s významným podílem hrubých chyb, což se zejména používá při analýze snímku. Detektory klíčových bodů (feature detectors) poskytují výsledky s dvěma typy chyb. První chybou je chyba klasifikace, kdy detektor klíčových bodů nesprávně identifikuje klíčový bod v části snímku. Druhou chybou je chyba měření, kdy detektor klíčových bodů identifikuje správně klíčový bod, ale nepřesně odhadne jeden jeho parametr (např. poloha ve snímku). Měřické chyby mají charakter normálního rozdělení, a proto jsou odstraněny bez potíží (zprůměrovány). Klasifikační chyby mají větší vliv, než měřické chyby, jsou tedy hrubými chybami a nelze je zprůměrovat.

Metoda používá malý vstupní soubor dat, který rozšiřuje o konzistentní data, pokud je to možné. Postup metody: ∙ Je dán model, který vyžaduje k odhadu volných parametrů minimálně n bodů a je dána množina bodů P, kde počet bodů množiny P je větší než n ♯ [(𝑃 ) ≥ 𝑛]. Z náhodně zvolené podmnožiny S1 z množiny P o počtu bodů n vypočteme model M1. Pomocí modelu M1 určíme podmnožinu bod S1* v množině P, která je v chybové toleranci M1. Množina S1* je nazývána množina konsensů S1. ∙ Jestliže ♯ (S1* ) je větší než práh t, což je funkce odhadu počtu hrubých chyb v P, použije se S1* pro výpočet nového modelu M1* (může být použita i MNČ). ∙ Jestliže ♯ (S1* ) je menší než t, náhodně je zvolena nová podmnožina S2 a opakuje se celý proces. Pokud po předem stanoveném počtu pokusů není žádná

31

ČVUT Praha


množina konsensů s t a více členy nalezena, pak je model vyřešen s největším souborem konsensů, nebo je proces ukončen s neúspěchem.

Zlepšením je, pokud existuje podmínka pro výběr bodů k vytvoření S, použije se deterministický postup místo náhodného výběru. Jestliže vhodný soubor konsensů S* byl nalezen a model M* vypočten a nebyly přidány nové body z P, pak se použije tato větší množina pro výpočet nového modelu.

RANSAC obsahuje tři nespecifikované parametry: ∙ Tolerance chyb, která se používá k určení, zda je bod kompatibilní s modelem. ∙ Maximální počet podmnožin k výpočtu. ∙ Prahová hodnota t, což je počet kompatibilních bodů naznačující, že byl nalezen správný model.

3.3.1

RANSAC - LD (Location Determination)

Jelikož je SIFT algoritmus plně automatizovaný systém detekce klíčových bodů, nelze se vyhnout hrubým chybám. MNČ se však s těmito hrubými chybami není schopna vypořádat, proto se zde s výhodou využije RANSAC – LD algoritmus (Location Determination), který je velmi tolerantní vůči hrubým chybám. Vstupní data ∙ Seznam L o počtu m 6-tic. Každá 6-tice obsahuje 3D souřadnice kontrolního bodu a jeho korespondující snímkové souřadnice a volitelnou hodnotu udávající očekávanou chybu (v pixelech) určení polohy bodu na snímku. ∙ Konstanta komory a snímkové souřadnice hlavního bodu ∙ Pravděpodobnost (1 − 𝑤), že 6-tice obsahuje hrubou chybu ∙ Konfidenční číslo G, které je použito k nastavení vnitřní prahové hodnoty pro akceptaci dílčích výsledků, které přispívají k řešení.

32

ČVUT Praha


Schéma RANSAC - LD 1. Tři 6-tice jsou ze seznamu L vybrány metodou quasirandom, zajišťující přiměřené prostorové rozložení pro odpovídající si kontrolní body. Tento počáteční výběr je nazván S1. 2. CP (Center of Perspective) – projekční centrum nazvané CP1 odpovídající výběru S1 je odhadnuto uzavřenou formou. Za vícenásobné řešení lze považovat takové, pokud bylo obdrženo několik projekčních center z různých výběrů v následujících krocích. 3. Chyba určení polohy CP1 je označena za rušivou vzhledem k snímkovým souřadnicím tří zvolených kontrolních bodů (buď z hodnoty uvedené v 6-tici anebo výchozí hodnotou pixelu) a určením efektu na polohu CP1. 4. Pro určení chyby odhadu CP1 se používá technika pro určení elips chyb (rozměry jsou založené na dodaném konfidenčním čísle) ve snímkové rovině pro každý kontrolní bod uvedený v seznamu L. Pokud snímkové souřadnice asociovaného snímku jsou zobrazeny v chybové elipse, pak 6-tice je připojena k množině konsensu S1/CP1. 5. Pokud velikost S1/CP1 je rovna, nebo překračuje prahovou hodnotu t (implicitně rovna hodnotě 7 a mw ), pak množiny konsensů S1/CP1 je dodána do MNČ za účelem určení polohy CP a orientace snímku v prostoru. V opačném případě jsou prováděny kroky uvedené výše s náhodným výběrem S2, S3, . . . 6. Pokud počet iterací přesáhne 𝑘 = [𝑙𝑜𝑔(1 − 𝐺)]/[𝑙𝑜𝑔(1 − 𝑤3 )], pak doposud nalezená největší množina konsensů je použita pro výpočet řešení, nebo je výpočet ukončen selháním, pokud nebyla nalezena množina konsensů obsahující více jak 6 členů. Výstupní data ∙ Projekční centra kamer. ∙ Orientace snímku v prostoru. 33

3D Structure from 2D Mo

Tony Jebara, Ali Azarbayejani and Alex Pent MIT Media Laboratory, Cambridge MA, 021 f jebara, ali, sandy [email protected] 3.4 SFM (Structure from motion) ČVUT Praha


tently extract, locate a Such 2D features could age, corners of objects, around their contours. detected and associate tiations in the other fr error-prone) 2D measur problem. The availab stricts the SfM proble Structure from Motion

focus herein. It should and detecting feature p Obr. 3.12: Vztah a objektu, použito z [5] I. kamery Introduction edly dicult computer In their day-to-day lives, people naturally understand dismissed so easily in p Obrázek and 3.12 znázorňuje nastavení SFM, kdy kamera pozorujeThe scénu. locations of the operate in standardní a three dimensional world. Curiously, on 1) rovtheir coordinates though, they only sense projections of it. The seemJedním klíčovým předpokladem je, že 2D se objekty nepohybují (nebo se pohybují ingly eortless act of inferring 3D from 2D observations is motion between the cam noměrně, tak nebyl mezi nimi) a pouze kamera můžeinternal pogeometry. theabyresult of relativní complex pohyb mechanisms that are still quite far se era's fromobjektu. being resolved. For many rozpoznání years, this task hasabeen hybovat kolem SFM předpokládá feature jejich knowledge propojení of these thre parameters only from 2 considered thev ostatních primary role of visual processing. Pioneers s odpovídajícími feature snímcích. Tyto 2D měření (obvykle zašuměná in the elds of arti cial intelligence and computer vision over several frames or v outchyby) to recover a 3D representation of visible scenes a obsahující set hrubé jsou vstupem do SFM. Poloha 2D feature závisíalternative na jejich problem st with various twists ran which could then be used to recognize objects and reason souřadnicích v 3D prostoru, relativním 3D pohybu mezi kamerou a scénou, tures prv(i.e. curves or lin about the world. algorithm's required ou However,Řešení the general problem recovering 3D fromv praktických cích vnitřní orientace. poskytnutá SFMofmají mnoho využití 1 2D imagery and the many steps involved require a sig- primarily on the task st aplikacích: ni cant understanding of how the mind works, from is- can be seen in [31] [14] The paper motivates sues of learning to intelligent behavior. Thus, the eld is ∙ Rekonstrukce plagued3Dbymodelu several of the same hurdles that have occu- some current practical a pied AI researchers for many years. A tractable and more brief discussion of the b Existuje mnoho technik 3D skenování, SFM je alternativou a je používáno theoretically well-posed problem is the speci c computa- eral techniques are outl k rekonstrukci souřadnicfrom a 3D z 2Dorsnímání objektů. approaches and paradi tion of 3D3Dgeometry 2Dmodelů geometry Structure-fromcal issues, advantages a Motion (SfM). Subsequently, we prese ∙ 3D motion matching A. The Structure from Motion Task sive estimation of moti Obnovení parametrů 3D motion v rámci SFM může být také využitotry in a nonlinear dyn Several simplifying assumptions are made to the gen- k účelům are given 3D animace. Tyto techniky jsou integrovány do software pro užití ve filmu, for synthetic eral problem of 3D models from 2D imagery to formulate the Structure from Motion task. The gure above shows to assess the accuracy a video, hrách, interaktivních médiích a průmyslovém designu. a standard SfM setup where a camera is viewing a scene. then discuss some pract One key assumption is that objects in the scene are mov- have encountered and t ∙ Kalibrace ing kamery rigidly or, equivalently, only the camera is allowed to approach in those sett results from an indepen in vnější the environment. Obnovamove prvků a vnitřní orientace je další praktickou aplikací. An additional simpli cation is that there exists a mod- by industry where the p ule which pre-processes the camera's images to consis- favorably to alternative available for public ftp 34 steps include dicult problems such as segmentation, recognition, correspondence, etc. 1 These

ftp whitechapel

ČVUT Praha


∙ 3D Vision V mnoha aplikacích computer vision je SFM užitečné k výpočtu dílčích součástí. 3D rekonstrukce nemusí být finálním krokem, ale důležitým mezikrokem. ∙ Počítačové vnímání gest

58

Použití computer vision, jako rozhraní pro interakci člověka a počítače je apliMultiple View Geometry

Chapter 3

kací pro techniky obnovy 3D, které mohou být použity k identifikaci gesta, aneboCameras nahrazující tradiční klávesnici a myš. 3.4 doplňující Modelling

This chapter deals with the task of building a mathematical model of a ∙ Robotika camera. We will give a mathematical model of the standard pin-hole camera Oblast intrinsic robotiky and zahrnuje úkolyparameters. „koordinace ruky a oka“detailed , navigace a detekce and define extrinsic For more treatment see [24], [15] and a different approach see mezikrok. [26]. překážek, kdyfor je obnova structure důležitý

3.4.1 The pinhole camera ∙ Mozaikování a rektifikace

The simplest optical system used for modelling cameras is the složeného so called snímku. pinVe fotogrammetrii slouží ke spojení dílčích snímků do jednoho hole camera. The camera is modelled as a box with a small hole in one SFM odhaduje posun snímku plate a zarovná snímky k reprojekci jednoho3.6. sloof the sides and a photographic at the opposite side, seedoFigure Introduce coordinate system as in Figure 3.6. Observe that the origin of ženéhoa snímku (mozaiky). the coordinate system is located at the centre of projection, the so called focal point, and that the z-axis is coinciding with the optical axis. The 3.4.1 distanceModel from thekamery focal point to the image, f , is called the focal length. Similar triangles give

(X, Y, Z) ex

X

ey

(x0 , y0 ) x

C

(x, y)

ez

Z f Figure 3.6. camera with a coordinate Obr.The 3.13:pinhole Pinhole kamera, použito z [6] system.

x y Y X and = . (3.5) = f Z f Z This equation can be written in matrix form, using homogeneous coordinates, as       X x f 0 0 0   Y λ y  =  0 f35 0 0  (3.6) Z  , 1 0 0 1 0 1

ČVUT Praha


Nejjednodušším modelem kamery je pinhole kamera. Kamera je modelována jako krychle s otvorem v jedné stěně a fotografickou rovinou na straně druhé. Souřadnicový systém je na obrázku 3.13. Počátek systému je umístěn v projekčním centru (ohnisku) a osa 𝑧 je vložena do optické osy. Z podobnosti trojúhelníků vyplývá:

𝑥 𝑓

=

𝑋 , 𝑍

𝑦 𝑓

=

𝑌 𝑍

(3.7)

Rovnice 3.7 může být zapsána maticově v homogenních souřadnicích: ⎡

⎤

⎤

⎡

⎤

⎡

⎢ 𝑋 ⎥ ⎥ ⎢ 𝑓 0 0 0 ⎥ ⎢ ⎢ 𝑥 ⎥ ⎥ ⎥ ⎢ ⎢ ⎥ ⎢ 𝑌 ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎥ 𝜆·⎢ 𝑦 ⎥=⎢ 0 𝑓 0 0 ⎥·⎢ ⎥ ⎥ ⎢ ⎢ ⎥ ⎢ ⎦ ⎢ 𝑍 ⎥ ⎣ ⎦ ⎣ ⎥ ⎦ ⎣ 0 0 1 0 1 1

(3.8)

Kde hloubka 𝜆 je rovna 𝑍. Matice kamery

𝐾 =

⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣

⎤

𝑓 0 0 ⎥ 0 𝑓 0 0 0 1

⎥ ⎥ ⎥, ⎥ ⎦

x=

⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣

⎡

⎤

⎥ , X=⎢ 𝑦 ⎥ ⎢ ⎥

⎥ ⎥ ⎥ ⎥ ⎦

⎤

𝑥 ⎥ 1

⎥ ⎦

Dosazením rovnice 3.9 do rovnice 3.8 obdržíme:

⎢ 𝑋 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 𝑌 ⎥ ⎢ ⎢ ⎣

𝑍

1

𝜆 · x = 𝐾 [𝐼3×3 |𝑂3×1 ] · X = 𝑃 · X

(3.9)

(3.10)

Kde 𝑃 = 𝐾 [𝐼3×3 |𝑂3×1 ] vztahuje rozšířené snímkové souřadnice x k rozšířeným souřadnicím objektu X, podle rovnice:

𝜆·x=𝑃 ·X

(3.11)

Rovnice 3.11 je rovnice kamery a 𝑃 je matice kamery. Ohniskový bod je dán vztahem PC = 0, kde C jsou homogenní souřadnice ohniska C.

36

ČVUT Praha


Vnitřní parametry (Prvky vnitřní orientace) V přesnějším modelu je matice 𝐾 nahrazena:

𝐾 = 60

⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣

⎤

𝛾𝑓 𝑠𝑓 𝑥0 ⎥ ⎥ 0

0

𝑓

0

⎥

𝑦0 ⎥ ⎥ ⎦

Multiple View Geometry 1

(3.12) Chapter 3

Kde 𝑓 je ohnisková vzdálenost, 𝛾 je poměr stran pixelů, 𝑠 je zkosení pixelů, (𝑥0 , 𝑦0 ) je poloha hlavního bodu. Pro většinu kamer platí, že 𝑠 = 0 a 𝛾 = 1 a hlavní 1 arctan(1/s) bod je blízko středu snímku. 60 Multiple View Geometry Chapter 3 γ

Figure 3.7. The intrinsic parameters

1 3.4.4

arctan(1/s)

The extrinsic parameters

γ

It is often advantageous to be able to express object coordinates in a different coordinate system than the camera coordinate system. This is especially the case when the relation between these coordinate systems are not known. For this purpose it is necessary to model the relation between two different coordinate systems in 3D.3.7. The natural way to do this is to model the relaFigure The intrinsic parameters Obr. 3.14: parametry kamery (prvky vnitřní orientace), použito tion as aVnitřní Euclidean transformation. Denote the camera coordinate systemz [6] with ec and points expressed in this coordinate system with index c, e.g. (Xc , Yc , Zc ), and similarly denote the object coordinate system with eo and points expressed in this coordinate system with index o, see Figure 3.8. A

Vnější parametry (Prvky vnější orientace)

3.4.4

The extrinsic parameters

It is often advantageous to be able to express (R, t) object coordinates in a different coordinate system than the camera coordinate system. This is especially the case when the relation between these coordinate systems are not known. For this purpose it is necessary to model the relation between two different coordinate systems in 3D.ec The natural way to do this is eto o model the relation as a Euclidean transformation. Denote the camera coordinate system with ec and points expressed in this coordinate system with index c, e.g. (Xc , Yc , Zc ), and similarly denote the object coordinate system with eo and Figure 3.8. coordinate systemswith for theindex camera o, andsee the object. points expressed in Using this different coordinate system Figure 3.8. A Obr. 3.15: Vnější parametry kamery (prvky vnější orientace), použito z [6] Euclidean transformation from the object coordinate system to the camera

(R, t)

37

ČVUT Praha


Převod souřadnic objektu do systému kamery je proveden Eukleidovskou transformací. Systém souřadnic kamery má označení (𝑋𝑐 , 𝑌𝑐 , 𝑍𝑐 ) a systém souřadnic objektu (𝑋𝑜 , 𝑌𝑜 , 𝑍𝑜 ). Eukleidovská transformace ze souřadnicového systému objektu do souřadnicového systému kamery je v homogenních souřadnicích: ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣

⎤

𝑋𝑐 ⎥ ⎥ 𝑌𝑐 ⎥ ⎥

⎤ ⎡

⎡

𝑅𝑇 0 ⎥ ⎢ 𝐼 ⎥=⎢ ⎦·⎣ ⎣ ⎥ 0 0 1 𝑍𝑐 ⎥ ⎥ 1

⎦

−𝑡 1

⎡

⎤ ⎢ ⎢ ⎢ ⎥ ⎢ ⎦·⎢ ⎢ ⎢ ⎢ ⎣

⎤

𝑋𝑜 ⎥ ⎥ 𝑌𝑜 ⎥ ⎥

⎤

⎡

𝑅𝑇 −𝑅𝑇 𝑡 ⎥ ⎥ ⇒ 𝑋𝑐 = ⎢ ⎦ · 𝑋𝑜 ⎣ ⎥ 0 1 𝑍𝑜 ⎥ ⎥ 1

(3.13)

⎦

Kde 𝑅 je ortogonální matice rotace a 𝑡 vektor translace. Ohnisko (0, 0, 0) má v systému objektu souřadnice vektoru 𝑡. Pokud 𝑋𝑐 označíme, jako 𝑋 a rovnici 3.13 vložíme do rovnice 3.10 obdržíme:

𝜆 · x = 𝐾𝑅𝑇 [𝐼| − 𝑡] · 𝑋𝑜 = 𝑃 · 𝑋

(3.14)

Kde 𝑃 = 𝐾𝑅𝑇 [𝐼| − 𝑡] a ohnisko 𝐶𝑓 = 𝑡 = (𝑡𝑥 , 𝑡𝑦 , 𝑡𝑧 ) je dáno položením pravé strany rovné 0. Pokud máme danou kameru, kterou popisuje matice kamery 𝑃 , může být tato matice kamery zapsána, jako 𝜇𝑃 , 0 ̸= 𝜇 ∈ 𝑅, obdržíme stejný snímkový bod, to znamená, že matice kamery 𝑃 je definována kromě měřítka a může být chápána, jako projektivní transformace. Nahradí-li se 𝑡 s 𝜇𝑡 a (𝑋, 𝑌, 𝑍) s (𝜇𝑋, 𝜇𝑌, 𝜇𝑍), 0 ̸= 𝜇 ∈ 𝑅, je obdržen stejný výsledek. ⎡

⎤

⎡

⎤

𝐾𝑅𝑇 [𝐼|𝜇 − 𝑡] · ⎢ ⎢

⎥ ⎥ ⎥ ⎥ ⎦

= 𝜇𝐾𝑅𝑇 [𝐼| − 𝑡] · ⎢ ⎢

⎥ ⎥ ⎥ ⎥ ⎦

⎢ 𝜇𝑋 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 𝜇𝑌 ⎥ ⎢ ⎢ ⎣

𝜇𝑍 1

⎢ 𝑋 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 𝑌 ⎥ ⎢ ⎢ ⎣

𝑍

1

(3.15)

Vztah 3.15 je nazýván měřítková ambiguita. Počet parametrů matice kamery 𝑃 : ∙ K: 5 parametrů (𝑓, 𝛾, 𝑠, 𝑥0 , 𝑦0 ) ∙ R: 3 parametry ∙ t: 3 parametry 38

ČVUT Praha


Celkem je obdrženo tedy 11 parametrů, které jsou stejné, jako u obecné 3 × 4 matice definované až po měřítko. Pro nekalibrovanou kameru je tedy 𝑃 obecnou 3 × 4 maticí.

3.4.2

Epipolární geometrie

X=(X,Y,Z)

x2= (x2, y2 )

x1= (x1, y1 )

C1

e2

e1

C2

Obr. 3.16: Epipolární geometrie, použito z [5] Obrázek 3.16 znázorňuje zobrazení pro dva snímky. Použití projektivní geometrie na tuto situaci vede v epipolární geometrii. Tři body [𝐶1 , 𝐶2 , 𝑋] jsou epipolární rovinou a průsečíky této roviny s rovinami snímků tvoří epipolární linie. Linie, spojující dvě projekční centra [𝐶1 , 𝐶2 ], protíná roviny snímků v bodech 𝑒1 a 𝑒2 , které se nazývají epipóly. 3D bod 𝑃 je zobrazen na dvě snímkové roviny jako bod 𝑥1 a 𝑥2 , jejich homogenní souřadnice jsou (𝑥1 , 𝑦1 , 1) a (𝑥2 , 𝑦2 , 1). Po několika manipulacích je hlavním výsledkem epipolární geometrie lineární vztah:

𝑥𝑇1 𝐹 𝑥2 = 0 Kde F je fundamentální matice.

39

(3.16)

ČVUT Praha

3.4.3


Fundamentální matice

Fundamentální matice má rozměr 3 × 3 s 9 parametry. Nicméně je omezena 2 stupni det 𝐹 = 0 a může být uvoleno libovolné měřítko. Je zde tedy jen 7 stupňů volnosti v 𝐹 . Fundamentální matice definuje kompaktním způsobem geometrii korespondencí mezi dvěma snímky, kódování prvků vnitřní orientace a relativní prvky vnější orientace (relativní pohyb) dvou kamer. Kromě toho structure scény je vyřazen z odhadu 𝐹 a může být využit v samostatném kroku. Matice 𝐹 umožňuje identifikací bodu v jednom snímku identifikaci odpovídající epipolární linie v druhém snímku. Epipól druhého snímku (pravého) je obdržen, pokud položíme pravou stranu rovnu nule a epipól levého snímku obdržíme, pokud položíme levou stranu rovnu nule.

Nicméně nastane degenerativní případ, kdy body jsou koplanární (ležící v rovině 𝐶1 , 𝐶2 , 𝑋𝑖 ) a kdy jsou projekční centra blízko sebe. Když se centra překryjí (je dána pouze rotace kamery), nelze zobrazit na snímcích epipolární linii. Proto je jedním z požadavků dodržet přiměřenou translaci projekčních center (obdoba základnového poměru). Epipolární geometrie vykazuje citlivost na šum (ve 2D měření), kdy každý bod může být propojen s jakýmkoli bodem na epipolární linii v jiném snímku. Řešení pak mají vysoké zbytkové chyby podél epipolární linie a špatnou rekonstrukci.

3.4.4

Lineární algoritmus (8 bodový algoritmus)

Jednou technikou pro obnovení parametrů fundamentální matice je, kdy je nejméně 8 bodů pozorováno. Rozšířením výrazu rovnice 3.16 je obdrženo jedno lineární omezení na 𝐹 pro pozorovaný bod, jako v rovnici 3.17. Kombinací 𝑁 těchto rovnic z 𝑁 korespondencí feature vede k lineárnímu systému ve formě 𝐴𝑓 = 0. [︂

𝑥1 𝑥2 𝑦1 𝑥2 𝑥2 𝑥1 𝑦2 𝑦1 𝑦2 𝑦2 𝑥1 𝑦1 1

]︂

𝑓 =0

(3.17)

Jedním řešením takového lineárního systému využívající více než 8 bodů může být MNČ (𝑚𝑖𝑛Σ|𝐴𝑓 2 |) s omezením, že |𝑓 | = 1. Toto omezení stanoví měřítko fundamentální matice, které je jinak libovolné. Kromě toho musí být normalizovány

40

ČVUT Praha


snímkové souřadnice, před řešením lineárních rovnic, v rozpětí [−1, 1]. Algoritmus využívá SVD výpočet, proto je důležité normalizovat snímkové souřadnice, jinak bude výpočet numericky nestabilní.

3.4.5

Nelineární algoritmus

Výsledek lineárních rovnic může být zpřesněn minimalizováním následujícího kritéria: (︁

𝐶(𝐹 ) = Σ 𝑑 (𝑥2 , 𝐹 𝑥1 )2 + 𝑑 (𝑥1 , 𝐹 𝑥2 )2

)︁

(3.18)

Kde 𝑑(., .) reprezentující Eukleidovskou vzdálenost ve snímku. Toto kritérium může být minimalizováno Levenberg-Marquard algoritmem. Ještě lepší přístup se skládá z výpočtu odhadu s maximální pravděpodobností (pro Gaussovský šum) minimalizací kritéria:

(︁

)︁

𝐶 (𝐹, 𝑥̂︀1 , 𝑥̂︀2 ) = Σ 𝑑 (𝑥̂︀1 , 𝑥1 )2 + 𝑑 (𝑥̂︀2 , 𝑥2 )2 , 𝑠

𝑥̂︀𝑇2 𝐹 𝑥̂︀1 = 0

(3.19)

Nicméně v tomto případě minimalizace musí být provedena s mnohem větším souborem proměnných.

3.4.6

Robustní algoritmus

Pro výpočet fundamentální matice ze souboru matches, které byly automaticky získány z dvojice snímků, je důležité se vypořádat s odlehlými měřeními. Pokud soubor matches obsahuje i malý soubor odlehlých měření, může výsledek být nestabilní. Toto je typická vlastnost MNČ, i jeden odlehlý bod, který je velmi vzdálený od pravé polohy může kompletně znehodnotit celkový výsledek. Proto je vhodné použít RANSAC algoritmus, který se s tímto problémem vypořádá. Obvykle se volí pravděpodobnost 95% (prahová hodnota t), že byl zvolen dobrý vzorek.

3.4.7

Výpočet dvousnímkové geometrie

Kombinací různých algoritmů obdržíme praktický algoritmus pro výpočet dvousnímkové geometrie z reálných snímků:

41

ČVUT Praha


1. Výpočet inicializačního souboru potenciálních korespondencí (nastavit 𝜌𝑚𝑎𝑥 = 0, 𝑚 = 0). (︁

2. While 1 − (1 − 𝜌7𝑚𝑎𝑥 )

𝑚

)︁

< 95% do

(a) Náhodně vybrat minimální vzorek (7 párů odpovídajících si bodů) (b) Vypočítat 𝐹 (c) Určit procento inliers 𝜌 (pro všechna řešení) (d) Zvýšit 𝑚, obnovit 𝜌𝑚𝑎𝑥 pokud 𝜌𝑚𝑎𝑥 < 𝜌 3. Zpřesnit 𝐹 na všechny inliers 4. Vyhledat další matche podél epipolární linie 5. Zpřesnit 𝐹 na všechny správné matches (nejlépe rovnicí 3.19)

3.4.8

Obnova structure a motion

Jakmile byla epipolární geometrie vypočtena mezi všemi po sobě jdoucími snímky, dalším krokem je rekonstrukce structure a motion pro celou sekvenci snímků. Zde je použit sekvenční přístup. Nejprve je structure a motion inicializován dvěma snímky a pak je postupně rozšířen na celou sekvenci snímků. Nakonec je řešení zpřesněno globální minimalizací všech neznámých parametrů. Inicializace výpočtu motion Dva snímky sekvence jsou použity k určení referenčního rámce. Souřadnicová soustava je vložena do prvního snímku, druhý snímek je zvolen tak, že epipolární geometrie odpovídá vztažené fundamentální matici. 𝑃1 = [𝐼3×3 |𝑂3 ] [︁

]︁

𝑃2 = 𝑇𝑒 𝐹 + 𝑒𝑣 𝑇 |𝜎𝑒

(3.20)

Rovnice 3.20 není zcela určena epipolární geometrií (tj. 𝐹 a 𝑒), ale má další čtyři stupně volnosti (tj. 𝑣 a 𝜎). Vektor 𝑣 určuje polohu referenční roviny (tj. roviny v nekonečnu v afinním nebo metrickém rámci) a 𝜎 určuje globální měřítko rekonstrukce.

42

ČVUT Praha


Umístění referenční roviny by nemělo mít žádný rozdíl, pokud je algoritmus projektivně invariantní. K dosažení tohoto cíle je důležité použít homogenní souřadnice pro všechny 3D objekty a používat pouze měření k minimalizaci. Hodnota parametru 𝜎 může být zafixována na 1. Inicializace výpočtu motion Hned dvě projekční matice byly plně určeny a matches mohou být rekonstruovány pomocí triangulace. Kvůli šumu se linie snímků neprotnou perfektně. V případě projekce by minimalizace měla být provedena ve snímku. Měla by být proto minimalizována vzdálenost mezi určeným 3D bodem a bodem na snímku. 𝑑 (𝑥1 , 𝑃1 𝑋)2 + 𝑑 (𝑥2 , 𝑃2 𝑋)2

(3.21)

Důležitou volbou je, ve které epipolární rovině bude bod rekonstruován. Jakmile je tento výběr proveden, je jednoduché zvolit optimální bod z roviny. Vzhledem k tomu, že svazek epipolárních rovin má pouze jeden parametr, je dimenze řešení redukována z 3 na 1. Minimalizace rovnice 3.22 je ekvivalentní k minimalizaci rovnice 3.21. 𝑑 (𝑥1 , 𝑙1 (𝜆))2 + 𝑑 (𝑥2 , 𝑙2 (𝜆))2

(3.22)

Kde 𝑙1 (𝜆) a 𝑙2 (𝜆) jsou epipolárními liniemi obdrženými v závislosti na parametru 𝜆 popisující svazky epipolárních rovin. Tato rovnice je polynom 6 stupně v 𝜆. Globální minimum rovnice 3.22 může být vypočteno přímo. V obou snímcích jsou vybrány body na epipolární linii 𝑙1 (𝜆) a 𝑙2 (𝜆) nejblíže k bodům 𝑥1 respektive 𝑥2 . Vzhledem k tomu, že tyto body jsou v epipolární korespondenci jejich linie se přesně protínají v 3D bodě. V případě, že rovnice 3.19 byla minimalizována, aby byla obdržena fundamentální matice 𝐹 , mohou být (𝑥1 , 𝑥2 ) rekonstruovány přímo. Aktualizace structure a motion - určení polohy projekčního centra Pro každý přidaný snímek je určena pozice k již existující rekonstrukci, jako na obrázku 3.17. Předpokládá se, že epipolární geometrie byla vypočtena mezi snímky

43

ČVUT Praha


𝑖 − 1 a 𝑖. Matches, které odpovídají k již zrekonstruovaným bodům, jsou použity k odvození jejich korespondencí mezi 2D a 3D. Na základě těchto projekčních matic je 𝑃𝑖 vypočteno pomocí robustního postupu, podobném pro výpočet fundamentální matice. V tomto případě je potřeba minimálního vzorku 6 matches k výpočtu 𝑃𝑖 . Bod je považován za inlier, pokud existuje 3D bod, který je promítnut dostatečně blízko ke všem odpovídajícím bodům. To vyžaduje upřesnění inicializačního řešení 𝑋 založeném na všech observacích, včetně poslední. Protože se jedná o výpočetně náročné řešení (nezapomeňte, že toto musí být provedeno pro každou generovanou hypotézu), je doporučeno používat upravenou verzi RANSAC, která ruší ověřování „neslibných“ hypotéz. Jakmile 𝑃𝑖 byla určena, projekce již rekonstruovaných bodů může být předvídána, aby bylo možné obdržet další matches. To znamená, že prohledávaný prostor se postupně snižuje z celého snímku na epipolární linii předpoSection 3.7.

85

Structure and Motion II

kládaného průmětu bodu.

X

x i−3 ^x i−3

x i−2 x^ i−2

x i−1 x^ i−1

F

xi xî

Figure 3.14. Image matches (xi−1 , xi ) are found as described before. Since some , relate to object points,zeX,sekvence, the pose for view i can bezcomputed image points, xi−1Přidání Obr. 3.17: snímku použito [6] from the inferred matches (X, xi ). A point is accepted as an inlier if a solution for exist for which d(P X, xi ) < 1 for each view k in which X has been observed. X

Tento postup se týká aktuálního a předchozího snímku, předpokládá se, že pokud Although this is true for many sequences, this assumptions does not always

hold. Assume that a specific point got out of sight, but thatmnoho it becomes se bod dostane mimo dohled, tak se3D„nevrátí“ . Nicméně pro sekvencí tento visible again in the two most recent views. This type of points could be

předpoklad vždy neplatí. Pokud 3D bod seHowever, dostalthe z naive dohledu, alewould stane se znovu interesting to avoid error accumulation. approach just reinstantiate a new independent 3D point. A possible solution to this

viditelným v problem posledních dvou insnímcích, může být zajímavý z pohledu zabránění was proposed [35]. The structure is refined using an iterated linear reconstruction algorithm on each point. The scale factors can also be eliminated from (3.25) so that homogeneous equations in X are obtained:

Refining and extending structure hromadění chyb.

P3 Xx − 44 P1 X = 0 P3 Xy − P2 X = 0

(3.35)

ČVUT Praha


Aktualizace structure a motion - zpřesnění a rozšíření structure Structure je zpřesněna použitím iteračního lineárního rekonstrukčního algoritmu v každém bodě. Měřítkový faktor může být odstraněn tak, aby byly získány homogenní rovnice v 𝑋: 𝑃3 𝑋𝑥 − 𝑃1 𝑋 = 0

(3.23)

𝑃3 𝑋𝑦 − 𝑃2 𝑋 = 0 Kde 𝑃𝑖 je řádek 𝑖 v 𝑃 a (𝑥, 𝑦) jsou snímkové souřadnice bodu. Odhad 𝑋 je vypočten řešením soustavy lineárních rovnic obdržených ze všech snímků, kde jsou k dispozici odpovídající si body. Aby bylo obdrženo lepší řešení, kritérium Σ𝑑(𝑃 𝑋, 𝑥)2 by mělo být minimalizováno. To může být přibližně obdrženo iteračním řešením MNČ se započtením vah pro následující vztah: ⎤

⎡

1 ⎢ 𝑃 3 𝑥 − 𝑃1 ⎥ 𝑋=0 ˜ ⎣ 𝑃 𝑦−𝑃 ⎦ 𝑃3 𝑋 3 2

(3.24)

˜ je předchozí řešení pro 𝑋. Tento postup lze opakovat několikrát. Řešením Kde 𝑋 tohoto systému rovnic pomocí SVD je automaticky obdržen normalizovaný homogenní bod. Pokud 3D bod není pozorován, jeho pozice není aktualizována. V tomto případě je možné zkontrolovat, zda byl bod viděn v dostatečném počtu snímků, aby byl ponechán pro konečnou rekonstrukci. Tento minimální počet snímků může být například nastaven na 3. Tím se zabrání významnému počtu odlehlých bodů, díky rušivým matches. Samozřejmě se ve snímkové sekvenci objeví nové feature u každého nového snímku. Pokud bodové matches jsou k dispozici, které nejsou spojeny s existujícími body ve structure, pak může být inicializován nový bod. Zpřesnění structure a motion Jakmile byly structure a motion obdrženy pro celou sekvenci, doporučuje se zpřesnit je pomocí kroku globální minimalizace tak, že se potlačí zkreslení původního snímku. Odhad s maximální pravděpodobností může být obdržen prostřednictvím svazkového vyrovnání. Cílem je nalézt parametry kamery 𝑃𝑘 a 3D body 𝑋𝑖 pro které

45

ČVUT Praha


suma čtverců vzdáleností mezi pozorovanými body 𝑚𝑘𝑖 a zobrazenými body 𝑃𝑘 (𝑋𝑖 ) je minimální. Doporučuje se rozšířit projekční model kamery o radiální distorzi. Pro 𝑚 snímků a 𝑛 bodů by mělo být minimalizováno následující kritérium:

min

𝑃𝑘 ,𝑋𝑖

𝑚 ∑︁ 𝑛 ∑︁

𝑑 (𝑥𝑘𝑖 , 𝑃𝑘 ((𝑋𝑖 ))2

(3.25)

𝑘=1 𝑖=1

Pokud chyby v určení polohy feature jsou nezávislé a splňují normální rozdělení, pak svazkové vyrovnání odpovídá odhadu s největší pravděpodobností. Toto řešení minimalizace má obrovský rozměr, např. pro sekvenci 20 snímků a 100 bodů na snímek, dosahuje řešení minimalizace více jak 6000 proměnných (většina z nich závisí na structure). Algoritmus obnovující structure a motion Celý proces algoritmu obnovy structure a motion se skládá z následujících kroků: 1. Určit matching nebo tracking bodů celé snímkové sekvence. 2. Inicializovat obnovu structure a motion: (a) Zvolit dva snímky, které jsou vhodné pro inicializaci. (b) Nastavit inicializační snímek. (c) Rekonstruovat inicializační structure. 3. Pro každý přidaný snímek: (a) Odvodit matches k již existující structure. (b) Vypočítat pozici kamery robustním algoritmem. (c) Zpřesnit existující structure. (d) Inicializovat nové body structure. 4. Zpřesnit structure a motion svazkovým vyrovnáním. Výsledkem tohoto algoritmu jsou pozice kamer všech snímků a rekonstrukce významných bodů objektu.

46

ČVUT Praha

3.5


Svazkové vyrovnání

Tato metoda spočívá v současném vyrovnání všech parametrů (pozice a rotace kamer, souřadnice bodů). Je to poslední krok před tvorbou mračna metodami využívající obrazovou korelaci. Svazkové vyrovnání používá přímé vyjádření mezi snímkovými souřadnicemi a modelovými souřadnicemi klíčových bodů a jeho inverzní vztah. Vztah obsahuje nelineární prvky (𝑠𝑖𝑛, 𝑐𝑜𝑠), proto je nutné jej nejprve linearizovat Taylorovým rozvojem. Výpočet pak probíhá iterativně.

Přímý vztah mezi snímkovými souřadnicemi a geodetickými (modelovými) souřadnicemi je dán výrazem:

𝑥 = 𝑥0 − 𝑓

𝑟11 (𝑋 − 𝑋0 ) + 𝑟21 (𝑌 − 𝑌0 ) + 𝑟31 (𝑍 − 𝑍0 ) 𝑅1 𝑋 = 𝑥′0 − 𝑓 𝑟13 (𝑋 − 𝑋0 ) + 𝑟23 (𝑌 − 𝑌0 ) + 𝑟33 (𝑍 − 𝑍0 ) 𝑅3 𝑋

(3.26)

𝑦 ′ = 𝑦0′ − 𝑓

𝑟12 (𝑋 − 𝑋0 ) + 𝑟22 (𝑌 − 𝑌0 ) + 𝑟32 (𝑍 − 𝑍0 ) 𝑅2 𝑋 = 𝑦0′ − 𝑓 𝑟13 (𝑋 − 𝑋0 ) + 𝑟23 (𝑌 − 𝑌0 ) + 𝑟33 (𝑍 − 𝑍0 ) 𝑅3 𝑋

(3.27)

Neznámé jsou prvky vnější orientace (𝑋0 , 𝑌0 , 𝑍0 , 𝜔, 𝜙, 𝜅) a při nadbytečném počtu bodů (klíčových bodů je nadbytek) je možno vyrovnat i prvky vnitřní orientace (konstantu komory a polohu hlavního bodu).

Schématický zápis linearizace Taylorovým rozvojem:

𝑓 (𝑥1 , ..., 𝑥𝑛 ) = 𝑓

(︁

Kde 𝑙𝑖 +𝑣𝑖 = 𝑓 (𝑥1 , ..., 𝑥1 ),

(︁

𝜕𝑓𝑖 𝜕𝑥𝑗

(︃

)︃0

(︃

)︃0

)︁

𝜕𝑓 + 𝜕𝑥1

)︁0

= 𝑎𝑖𝑗 jsou parciální derivace všech proměnných,

𝑥01 , ..., 𝑥0𝑛

𝜕𝑓 𝑑𝑥1 + ... + 𝜕𝑥𝑛

𝑑𝑥𝑛

(3.28)

které jsou numericky vyčíslené pomocí přibližných hodnot neznámých 𝑥01 , ..., 𝑥0𝑛 , jsou to tedy prvky matice 𝐴. 𝑙𝑖 jsou hodnoty pozorování (snímkové souřadnice) a 𝑙𝑖′ = 𝑙𝑖 − 𝑓 (𝑥01 , ..., 𝑥0𝑛 ) je vektor redukovaných měření.

47

ČVUT Praha


Rovnice oprav pak bude mít tvar: (︃

𝑣𝑥𝑖𝑗 =

𝜕𝑥′ 𝜕𝑋0𝑗

(︃

)︃0

𝜕𝑥′ + 𝜕𝜅𝑗 𝑣𝑦𝑖𝑗 =

(︃

𝜕𝑦 ′ + 𝜕𝜅𝑗

(︃

𝜕𝑥′ 𝑑𝑋0𝑗 + 𝜕𝑌0𝑗 (︃

𝜕𝑥′ 𝑑𝜅𝑗 + 𝜕𝑋𝑖

𝜕𝑦 ′ 𝜕𝑋0𝑗

(︃

)︃0

)︃0

)︃0

)︃0

(︃

𝜕𝑦 ′ 𝑑𝜅𝑗 + 𝜕𝑋𝑖

)︃0

(︃

𝜕𝑥′ 𝑑𝑌0𝑗 + 𝜕𝑍0𝑗 (︃

𝜕𝑥′ 𝑑𝑋𝑖 + 𝜕𝑌𝑖

𝜕𝑦 ′ 𝑑𝑋0𝑗 + 𝜕𝑌0𝑗 (︃

)︃0

)︃0

)︃0

𝜕𝑥′ 𝑑𝑍0𝑗 + 𝜕𝜔𝑗

𝜕𝑥′ 𝑑𝑌𝑖 + 𝜕𝑍𝑖

𝜕𝑦 ′ 𝑑𝑌0𝑗 + 𝜕𝑍0𝑗

𝜕𝑦 ′ 𝑑𝑋𝑖 + 𝜕𝑌𝑖

(︃

(︃

(︃

(︃

)︃0

)︃0

)︃0

)︃0 (︃

𝜕𝑦 ′ 𝑑𝑌𝑖 + 𝜕𝑍𝑖

)︃0

(︃

𝜕𝑥′ 𝑑𝜔𝑗 + 𝜕𝜙𝑗 (︁

𝑑𝑍𝑖 − 𝑥′𝑖𝑗 − 𝑥′0 𝑖𝑗

𝜕𝑦 ′ 𝑑𝑍0𝑗 + 𝜕𝜔𝑗 (︃

)︃0

)︃0

(︃

)︁

𝜕𝑦 ′ 𝑑𝜔𝑗 + 𝜕𝜙𝑗 (︁

𝑑𝑍𝑖 − 𝑦𝑖𝑗′ − 𝑦𝑖𝑗′0

)︃0

𝑑𝜙𝑗 +

(3.29) )︃0

)︁

𝑑𝜙𝑗 +

(3.30)

′0 Kde 𝑥′𝑖𝑗 , 𝑦𝑖𝑗′ je měřená snímková souřadnice a 𝑥′0 𝑖𝑗 , 𝑦𝑖𝑗 je vypočtená snímková

souřadnice ze vztahu (3.26) a (3.27) vypočtená z přibližných hodnot neznámých.

Parciální derivace výrazu (3.26): (︃

(︃

(︃

𝜕𝑥′ 𝜕𝑋0

)︃

(︃

𝜕𝑥′ 𝜕𝑌0

)︃

(︃

𝜕𝑥′ 𝜕𝑍0

)︃

𝜕𝑥′ 𝜕𝜔

𝜕𝑥′ 𝜕𝜙

)︃

)︃

)︃

=−

(︃

)︃

=−

(︃

)︃

=−

𝑓 (𝑟23 𝑅1 · 𝑋 − 𝑟21 𝑅3 · 𝑋) 𝜕𝑥′ =− , 𝜕𝑌 (𝑅3 · 𝑋)2

𝑓 (𝑟33 𝑅1 · 𝑋 − 𝑟31 𝑅3 · 𝑋) 𝜕𝑥′ =− , 𝜕𝑍 (𝑅3 · 𝑋)2

=−

=

(︃

𝑓 (𝑟13 𝑅1 · 𝑋 − 𝑟11 𝑅3 · 𝑋) 𝜕𝑥′ =− , 𝜕𝑋 (𝑅3 · 𝑋)2

{︁

𝑓 (𝑟11 𝑅3 · 𝑋 − 𝑟13 𝑅1 · 𝑋) (𝑅3 · 𝑋)2

𝑓 (𝑟21 𝑅3 · 𝑋 − 𝑟23 𝑅1 · 𝑋) (𝑅3 · 𝑋)2

𝑓 (𝑟31 𝑅3 · 𝑋 − 𝑟33 𝑅1 · 𝑋) (𝑅3 · 𝑋)2 }︁

1 ·𝑋 − (𝑟31 (𝑌 − 𝑌0 ) + 𝑟21 (𝑍 − 𝑍0 )) 𝑓 (𝑟33 (𝑌 − 𝑌0 ) − 𝑟23 (𝑍 − 𝑍0 )) 𝑅 𝑅3 ·𝑋

{︁

𝑅3 · 𝑋

}︁ (︃

1 ·𝑋 𝑓 (𝑅1 · 𝑐𝑜𝑠 (𝜅) − 𝑅2 · 𝑠𝑖𝑛 (𝜅)) 𝑅 + (𝑅3 · 𝑋𝑐𝑜𝑠 (𝜅)) 𝑅3 ·𝑋

𝑅3 · 𝑋

𝜕𝑥′ , 𝜕𝜅

)︃

=−

𝑓 𝑅2 · 𝑋 𝑅3 · 𝑋

Parciální derivace výrazu (3.27): (︃

𝜕𝑦 ′ 𝜕𝑋0

(︃

𝜕𝑦 ′ 𝜕𝑌0

)︃ )︃

(︃

)︃

=−

(︃

)︃

=−

𝑓 (𝑟13 𝑅2 · 𝑋 − 𝑟12 𝑅3 · 𝑋) 𝜕𝑦 ′ =− , 𝜕𝑋 (𝑅3 · 𝑋)2 𝑓 (𝑟23 𝑅2 · 𝑋 − 𝑟22 𝑅3 · 𝑋) 𝜕𝑦 ′ =− , 𝜕𝑌 (𝑅3 · 𝑋)2 48

𝑓 (𝑟12 𝑅3 · 𝑋 − 𝑟13 𝑅2 · 𝑋) (𝑅3 · 𝑋)2

𝑓 (𝑟22 𝑅3 · 𝑋 − 𝑟23 𝑅2 · 𝑋) (𝑅3 · 𝑋)2

ČVUT Praha (︃

(︃

(︃

𝜕𝑦 ′ 𝜕𝑍0

′

𝜕𝑦 𝜕𝜔

′

𝜕𝑦 𝜕𝜙

)︃

)︃

)︃

(︃

𝑓 (𝑟33 𝑅2 · 𝑋 − 𝑟32 𝑅3 · 𝑋) 𝜕𝑦 ′ =− , 𝜕𝑍 (𝑅3 · 𝑋)2

=−

=


{︁

)︃

=−

𝑓 (𝑟32 𝑅3 · 𝑋 − 𝑟33 𝑅2 · 𝑋) (𝑅3 · 𝑋)2 }︁

2 ·𝑋 𝑓 (𝑟33 (𝑌 − 𝑌0 ) − 𝑟23 (𝑍 − 𝑍0 )) 𝑅 − (𝑟32 (𝑌 − 𝑌0 ) + 𝑟22 (𝑍 − 𝑍0 )) 𝑅3 ·𝑋

𝑅3 · 𝑋

{︁

}︁ (︃

𝑅2 ·𝑋 𝑓 (𝑅1 · 𝑐𝑜𝑠 (𝜅) − 𝑅2 · 𝑠𝑖𝑛 (𝜅)) 𝑅 + (𝑅3 · 𝑋𝑠𝑖𝑛 (𝜅)) 3 ·𝑋

𝑅3 · 𝑋

𝜕𝑦 ′ , 𝜕𝜅

)︃

=−

𝑓 𝑅1 · 𝑋 𝑅3 · 𝑋

Rovnici oprav můžeme tedy zapsat jako: 𝑣 = 𝐴1 · 𝑥1 + 𝐴2 · 𝑥2 − 𝑙′

(3.31)

Kde 𝑥𝑇1 = (𝑑𝜔𝑗 , 𝑑𝜙𝑗 , 𝑑𝜅𝑗 , 𝑑𝑋0𝑗 , 𝑑𝑌0𝑗 , 𝑑𝑍0𝑗 ) je vektor vyrovnaných přírůstků prvků vnější orientace, 𝑥𝑇2 = (𝑑𝑋𝑖 , 𝑑𝑌𝑖 , 𝑑𝑍𝑖 ) je vektor vyrovnaných přírůstků určovaných bodů, 𝑣 𝑇 = (𝑣𝑥𝑖𝑗 , 𝑣𝑦𝑖𝑗 , ) je vektor oprav snímkových souřadnic, 𝐴1 , 𝐴2 jsou matice koeficientů pro prvky vnější orientace a pro určované body. Pro základní tvar rovnic oprav 𝑣 = 𝐴 · 𝑥 − 𝑙′ je řešení 𝑥 = (𝐴𝑇 𝐴)− 1 · 𝐴𝑇 𝑙′ .

Nahradíme výrazy 𝐴𝑇 𝐴 = 𝑁 a 𝐴𝑇 𝑙′ = 𝑛, pak řešení bude mít tvar: ⎛

⎞ ⎛

⎞

⎛

⎞

⎜ 𝑁11 𝑁12 ⎟ ⎜ 𝑥1 ⎟ ⎜ 𝑛1 ⎟ ⎝ ⎠·⎝ ⎠=⎝ ⎠ 𝑇 𝑁12 𝑁22 𝑥2 𝑛2

(3.32)

Matice 𝑁11 a 𝑁22 jsou hyperdiagonálními maticemi, kde 𝑁11 obsahuje submatice 6x6 (prvky vnější orientace každého snímku) a 𝑁22 obsahuje submatice 3x3 (souřadnice nově určovaných bodů). Opravy prvků vnější orientace se určí podle: (︁

)︁

− 𝑇 −1 1 · 𝑁12 · 𝑥1 = 𝑛1 − 𝑁12 · 𝑁22 · 𝑛2 𝑁11 − 𝑁12 · 𝑁22

49

(3.33)

ČVUT Praha

3.6


PMVS (Patch-based Multi-view Stereo)

ure 1. Overall approach. From left to right: a sample input image; detected features; reconstructed patche Obr. 3.18: PMVS, zleva: pořízený snímek, nalezení feature, rekonstrukce al patches after expansion andPostup filtering; polygonal surface extracted from reconstructed patches. patch, rekonstrukce celého povrchu, použito z [7]

rowded scenes, where moving obstacles in differ2. orientovaných Key Elements of the Prop PMVS je algoritmus, jehožappear výstupem je soubor malých patch (obplaces in multiple images of a static structure of interest v úrovni pixelů a těsně pokrývá délníkových plošek), obdržených z korespondencí Before detailing our algorithm i g., people passing in front of a building). pozorovaný objekt s výjimkou malých oblastí bez textury, nebo okluzních oblastí. the patches that willAlmake up our Techniques suchgoritmus as space carving [12, 15, 19] and varithe data structures used througho je schopen detekovat a vyřadit odlehlé body a as překážky a neprovádí žádná onal methods based on gradient descent [3, 4, 7], level We also introduce two oth vyhlazení. Algoritmus používá účinnou metodu určení images. místní fotometrické konziss [1, 9, 18], or graph cuts [3, 8, 17, 22, 23] typically blocks of our approach, namely, t tence a určuje globální viditelnost patch. Algoritmus je realizován jako match (prouire an initial bounding volume and/or a wide range of curately reconstruct a patch once t a filtrační proces, začínající souborem klíčových bodů wpoints. Object pojovací), datasets expanzní are the ideal input for these al- řídkýmfragments have been matched, and rithms, but methods using multiple depthdomaps 21]před or použitím určení viditelnosti, aby a opakujícím se rozšířením jejich[5, okolí all, independent filtroval surfacenesprávná elementsmatch [6, 13] are better suited 2.1. Patch Models (propojení). the more challenging scene datasets. Crowded scenes A patch p is a rectangle with c even more difficult. The method proposed in [21] uses 3.6.1 Prvky algoritmu mal vector n(p) oriented toward t pectation maximization and multiple depth maps to re(Fig. 2). We associate with p a ref nstruct a crowded scene despite the presence occludZde bude definován patch, kterýof tvoří rekonstrukci a metody používané k přesné sen so that its retinal plane is close , but it is limited to a small number of images (typirekonstrukci patch. Jedna metoda spočívá v určení snímkového fragmentu, který byl distortion. In turn, R(p) determine ly three). As shown by qualitative and quantitative expropojen a druhá metoda určuje viditelnost patch. tent of the rectangle p in the plan iments in the rest of this paper, our algorithm effecthe projection of one of its edges in ely handles all three types of data, and, in particular, Model patch image rows, and the smallest axis puts accurate object and scene models with fine surface ing its image covers a µ × µ pixel2 ail despite low-texture regions, large se concavities, Patch 𝑝 je obdélník středem 𝑐𝑝 aand/or jednotkovým vektorem normály 𝑛𝑝 orien5 or 7 for µ in all of our experim n, high-curvaturetovaný parts.naAs noted earlier, it implements kameru (obrázek 3.19). Pokud je 𝑝 spojen s referenčním snímkem 𝑅𝑝 , tures are also attached to each pa lti-view stereopsis as a simple match, expand, and filwhere p should be visible (despite procedure (Fig. 1): (1) Matching: features found by in practice not be recognizable (d 50 rris and Difference-of-Gaussians operators are matched blur, etc.), or hidden by moving o oss multiple pictures, yielding a sparse set of patches T (p) where it is truly found (R(p) ociated with salient image regions. Given these initial

ČVUT Praha


tak aby mřížka snímku byla přibližně rovnoběžná s 𝑝. 𝑅𝑝 určuje orientaci a rozsah čtverce 𝑝 v rovině kolmo k 𝑛𝑝 tak, že zobrazení jeho hrany do 𝑅𝑝 je rovnoběžné s řádky snímku. Pro každý patch jsou dvě množiny snímků, v množině 𝑆𝑝 není patch viditelný a v množině 𝑇𝑝 je viditelný. Model má dvě omezení, první omezení se týká fotometrické konzistence, kdy zobrazená textura každého patch je konzistentní nejméně na 𝛾 snímcích, |𝑇𝑝 | ≥ 𝛾. Druhé omezení se týká globální viditelnosti, kdy žádný patch 𝑝 nesmí být zakryt jiným patch ve snímku.

R(p)

T(p)

n(p) p p

S(p)

c(p) P

Figure 2. Definition of a patch (left) and of the images associated with itObr. (right). for these details. 3.19: See Patchtext a snímky kterými je propojen, použito z [7]

cell (we use values of 1 or 2 for β1 in all our experiments). The cell C(i, j) keeps track of two difKaždému snímku 𝐼 je přiřazena pravidelná mřížka 𝛽1 × 𝛽1 pixelových buněk ferent sets Qt (i, j) and Q f (i, j) of reconstructed patches po𝐶(𝑖, 𝑗) a algoritmus se pokusí v každé buňce zrekonstruovat alespoň jeden patch. tentially visible in C(i, j): A patch p is stored in Qt (i, j) if Patch je uložen do 𝑄𝑡 (𝑖, 𝑗), pokud 𝐼 ∈ 𝑇𝑝 a 𝑄𝑓 (𝑖, 𝑗), pokud 𝐼 ∈ 𝑆𝑝 ∨ 𝑇𝑝 . Je spojeno I ∈ T (p), and in Q f (i, j) if I ∈ S(p) \ T (p). We also as𝐶(𝑖, 𝑗) s hloubkou středu patch v 𝑄𝑡 (𝑖, 𝑗), která je nejblíže ohnisku kamery. Tím je sociate with C(i, j) the depth of the center of the patch in vytvořena snímku 𝐼, kterácenter je použita výpočtu viditelnosti patch. closestmapa to the optical ofk the corresponding Qt (i, j)hloubková camera. This amounts to attaching a depth map to I, which Určení fotometrické konzistence will prove useful in the visibility calculations of Sect. 2.4. Model patchsnímku in every

Pro daný patch 𝑝 je použita normalizovaná korelace (NCC - Normalized Cross Corre-

2.3.𝑁Enforcing Photometric lation) (𝑝, 𝐼, 𝐽) jeho zobrazení do snímků 𝐼 aConsistency 𝐽 k změření fotometrické konzistence. MřížkaGiven 𝜇 × 𝜇 jea promítnuta na patch a zobrazena do snímků. hodnoty patch p, we use 𝑝the normalized crossKorelační correlation jsou obdrženy bilineární Danému patch 𝑝 odpovídá referenční snímek (NCC) N(p, I, J)interpolací. of its projections into the images I and J to𝑅𝑝

measure their photometric consistency. Concretely, a µ × µ grid is overlaid on p and projected into the two images, the 51 correlated values being obtained through bilinear interpolation. Given a patch p, its reference image R(p), and the

to rely mine (o cretely, the NC {I|N(p sion ph structio ages, an these d where d spondin in the c value o the dep of β1 p metric is truly This pr self an gorithm matchi ity and

3. Alg

3.1. M

As t blob fe

ČVUT Praha


a soubor snímků 𝑇𝑝 , kde je opravdu viditelný, může být pak odhadnuta jeho poloha 𝑐𝑝 a jeho normála 𝑛𝑝 minimalizací průměru NCC.

𝑁𝑝 =

∑︁ 1 𝑁 (𝑝, 𝑅𝑝 , 𝐼) |𝑇𝑝 | − 1 𝐼∈𝑇𝑝 ,𝐼 ̸=𝑅𝑝

(3.34)

Pro zjednodušení výpočtu může být omezeno 𝑐𝑝 tak, aby leželo na paprsku spojujícím ohnisko referenční kamery a odpovídající bod snímku, což sníží počet stupňů volnosti optimizace na tři (hloubku podél paprsku a dva rotační úhly 𝑛𝑝 ). Určení podmínky viditelnosti Viditelnost pro každý patch 𝑝 je určena snímky 𝑆𝑝 a 𝑇𝑝 , kde je potenciálně anebo opravdu pozorován. Mohou být použity dvě metody pro konstrukci 𝑆𝑝 a 𝑇𝑝 , závisející na fázi rekonstrukce. Ve fázi match jsou patch rekonstruovány z řídkých feature matches a k určení viditelnosti je použito omezení fotometrické konzistence. Jsou inicializovány oba soubory snímků, pro které NCC přesahuje práh 𝑆𝑝 = 𝑇𝑝 = {𝐼|𝑁 (𝑝, 𝑅𝑝 , 𝐼) > 𝛼0 }. Ve fázi expanze algoritmu je hustota patch dostatečná k propojení hloubkových map se všemi snímky. A 𝑆𝑝 je konstruováno pro {︁

}︁

každý patch posouzením těchto map. Práh tedy je 𝑆𝑝 = 𝐼|𝑑𝐼(𝑝) ≤ 𝑑𝐼(𝑖,𝑗) + 𝜌1 , kde 𝑑𝐼(𝑝) je hloubka centra 𝑝 podél zaznamenané v buňce 𝐶(𝑖, 𝑗) propojená se snímkem 𝐼 a patch 𝑝. Hodnota 𝜌1 je určena automaticky, jako vzdálenost hloubky 𝑐𝑝 odpovídajícího snímku nahrazeným 𝛽1 pixely v 𝑅𝑝 . Pak je odhadnuta 𝑆𝑃 (fotometrická konzistence je použita k určení snímku), kde patch 𝑝 je opravdu pozorován, jako 𝑇 = {𝐼 ∈ 𝑆𝑝 |𝑁 (𝑝, 𝑅𝑃 , 𝐼) > 𝛼1 }. Tento proces může selhat, pokud je referenční snímek 𝑅𝑝 outlier.

3.6.2

Popis algoritmu PMVS

Algoritmus se skládá ze tří kroků, prvním krokem je matching feature. Tento krok je již proveden v SFM algoritmu a PMVS algoritmus tak převezme jen jeho výsledky. Druhým krokem je expanze, kdy jsou patch rozšiřovány do svého okolí a posledním krokem je filtrace nových patch.

52

ČVUT Praha


Expanze V této fázi se iterativně přidávají noví sousedé k již existujícím patch, dokud nepokryjíInput: viditelný povrchPscény 𝑝 a 𝑝′ step. jsou považovány za sousedy, Patches from(objektu). the featurePatch matching

Output: set of reconstructed pokud jsou uloženyExpanded v sousedních buňkách 𝐶(𝑖, 𝑗) apatches. 𝐶(𝑖′ , 𝑗 ′ ) téhož snímku 𝐼 v 𝑆𝑝 a jejich normály jsou podobné. Vytváření nových sousedů je jen v nutném případě,

Use P to initialize, for each image, Q f , Qt , and its depth map.

′ ′ když 𝑄𝑡 (𝑖While , 𝑗 ) jePprázdné a žádný prvek 𝑄𝑡 (𝑖′ , 𝑗 ′ ) není vedle patch 𝑝. Patch 𝑝 a 𝑝′ is not empty Figure 6. Poly Pick and remove spolu nesousedí, pokud | (𝑐𝑝 −a 𝑐patch | +from | (𝑐𝑝 P; − 𝑐𝑝′ ) · 𝑛𝑝 | < 2𝜌2 . Jsou určena 𝜌1 a 𝜌2 ,umes for the d 𝑝′ ) · 𝑛𝑝p

For each image I ∈ T (p) and cell C(i, j) that p projects onto

jako délka v hloubce bodu 𝑐𝑝 a 𝑐𝑝′ odpovídajících rozdílu ve snímku 𝛽 1 pixelů v 𝑅𝑝 .(union of hem For each cell C(i , j ) adjacent to C(i, j) such that Qt (i , j ) Right: geomet Když jsou ověřeny tytoand podmínky, 𝑝′ přiřazením is empty p is not inicializuje n-adjacentsetopatch any patch in Q (i k, j𝑅 )𝑝′ , 𝑇𝑝′ a 𝑛𝑝′

p ,

R(p ), T (p )′ and

n(p )

f

copying p; prochází Create a new odpovídajícím hodnotám pro patch 𝑝 a přiřazením k 𝑐𝑝 bodu, kdefrom paprsek

c(p ) ← Intersection of optical ray through tha center of C(i , j ) with plane of p; ); fotometrickou konzistencí podmínkou Protože některé match mohoudeformation ¯ viditelnosti. argmaxN(p n(p ), c(p )a← phases. Brie {Visible mapy), images jsou of p prvky estimated by the do 𝑆𝑝′ , aby byly být nesprávné S(p (tím ) i←hloubkové 𝑇𝑝′ přidány a predetermi current ′ depth maps } ∪ T (p ); ′ je použito zachyceny všechny snímky, kde 𝑝 je viditelný. Nakonec po aktualizaci 𝑇 𝑝 reconstructed T (p ) ← {J ∈ S(p )|N(p , R(p ), J) ≥ α1 }; ) < γ |, go kdy určení fotometrické konzistence, backjetoakceptován For-loop; patch 𝑝, pokud |𝑇𝑝′ | ≥ 𝛾, paktered at thes If |T (p ′ P; je zaregistrovánAdd do 𝑄p𝑡 (𝑖to , 𝑗 ′ ) a 𝑄𝑓 (𝑖′ , 𝑗 ′ ) a aktualizují se hloubkové mapy spojené sewe repeatedl (Fig. 6): a sm snímky v 𝑆𝑝′ . Update Qt , Q f and depth maps for S(p ); Return all the reconstructed patches stored in Q f and Qt . ric consisten ohniskem 𝐶(𝑖′ , 𝑗 ′ ) a protíná rovinu obsahující patch 𝑝. Pak jsou patch zpřesněnyapproach

patches in th mesh in the are available I3 I2 I2 I3 I1 I1 deforming su I4 Concretel where ∆ deno a local param P2 P1 P0 and ζ2 = 0.4 Correct patch U P1 phase, the ph P4 Outlier P2 P3 P0 essentially d and is given Figure 5. Outliers lying outside (left) or inside (right) the correct normal to S Obr.surface. 3.20: Určení patch mimo rekonstruovaný použito z [7] images Arrows areležícího drawn between the patches ppovrch, i and the I j in S(pi ), while solid arrows correspond to the case where I j ∈ is the signed denotes a setkroky of patches occluded by anpatch, outlier. text konzis-along n(v) ( (pi ). U dva JsouT použity filtrační na rekonstruovaný ke See zvýšení for details. tence viditelnosti a k odstranění chybných match. První filtr je zaměřen na odstra-tude of the fo intersections nění patch, který leží mimo skutečný povrch (obrázek 3.20). Odstraní se 𝑝0 , pokud length in S). lect the set Π remove p0 when |T (p0 )| < γ . Note that the recomputed 53 be different from those obmals compat values of S(p0 ) and T (p0 ) may see Fig. 6) th tained in the expansion step since more patches have been and compute computed after the reconstruction of p0 . Finally, we enforce Filtrace

Figure 4. Patch expansion algorithm.

ČVUT Praha

|𝑇𝑝0 𝑁 𝑝0 <

∑︀

𝑝𝑗 ∈𝑈


𝑁 𝑝𝑗 , kde 𝑈 je soubor patch které tvoří objekt. Druhý filtr se za-

měřuje na patch, jestli leží na povrchu anebo mimo povrch. Spočte se 𝑆𝑝0 a 𝑇𝑝0 pro každý patch 𝑝0 pomocí hloubkových map spojených s odpovídajícími snímky a 𝑝0 se odstraní pokud |𝑇𝑝0 | < 𝛾. Nakonec se zde pro každý patch 𝑝 shromáždí veškeré patch v jeho vlastních a okolních buňkách ve všech snímcích. Pokud poměr patch, které jsou vedle 𝑝, z tohoto souboru je menší než 𝜖 = 0, 25, patch 𝑝 je odstraněn.

54

ČVUT Praha

4

4. ZPRACOVÁNÍ MODELŮ

Zpracování modelů

4.1

Pořízení snímků a příprava objektu

Celkem bylo pořízeno 456 snímků pro software VisualSFM a Agisoft PhotoScan a 234 snímků pro software Photomodeler Scanner. Snímky byly pořízeny kamerou Canon EOS 5D Mark II (obrázek 4.1) s objektivy Canon EF 16-35mm f/2,8 L II USM a Canon EF 50 mm f/1.8 II, dále byl využit stativ, osvětlovací sada a rám s body po obvodě.

Obr. 4.1: Digitální kamera Canon EOS 5D Mark II, použito z [11]

Snímky pro software VisualSFM a Agisoft PhotoScan byly pořízeny ze stativu a bez osvětlovací sady s objektivem Canon EF 16-35mm f/2,8 L II USM s nastavenou konstantou komory na 35 𝑚𝑚. Snímky pro software Photomodeler Scanner byly pořízeny s osvětlovací sadou a z ruky, nicméně zde byly použity oba objektivy, kdy objektiv Canon EF 16-35mm f/2,8 L II USM měl nastavenou konstantou komory na 35 𝑚𝑚. V obou případech bylo obtížné vypořádat se s hloubkou ostrosti, aby byl zachycen detailně členitý objekt, což při pořizování snímků ze stativu je celkem jednoduché. Nicméně pokud byly snímky pořizovány z ruky, muselo být zajištěno dostatečné osvětlení.

55

ČVUT Praha


Rozlišení v Mpx

21

Velikost snímače

fullframe

Druh snímače

CMOS

Druh paměti

CF

Zaostřovací body (křížové)

15 (1), Face Detection

Min. / Max. citlivost v ISO

100 / 1600

Rozhraní

A/V, HDMI, infra spoušť, kabelová spoušť, systémový blesk, X-sync konektor

Napájení

Li-Ion Tab. 4.1: Základní parametry kamery, převzato z [11]

Obr. 4.2: Schéma ideálního nasnímání objektu V obou případech byl objekt nasnímán z osmi stran, jak je uvedeno na obrázku 4.2. Z každého bočního pohledu bylo pořízeno několik desítek snímků ve vertikální řadě. Pro VisualSFM a Agisoft PhotoScan bylo pořízeno 45 až 65 snímků a bylo otáčeno objektem, pro pořízení nové vertikální řady snímků. Před pořízením snímků pro Photomodeler Scanner byl objekt polepen body, které byly vyrobeny z černé samolepicí tapety, avšak papírové body se na objektu neudržely a opadaly. Snímky pro Photomodeler Scanner byly pořízeny ve dvou etapách. V první etapě byly pořízeny

56

ČVUT Praha


snímky celého objektu ve třech horizontálních řadách kolem objektu objektivem Canon EF 16-35mm f/2,8 L II USM s konstantou komory 35 𝑚𝑚. V druhé etapě byly pořízeny snímky objektu s rámem (Canon EF 16-35mm f/2,8 L II USM ) s konstantou komory 35 𝑚𝑚 (rám sloužil k lepší orientaci snímků stereopáru) a ihned byly pořízeny stereodvojice objektivem Canon EF 50 mm f/1.8 II (rám nesměl změnit polohu vůči objektu).

Obr. 4.3: Objekt s umístěným rámem Rám byl dřevěná konstrukce obepínající objekt s odstupy od objektu přibližně 10 𝑐𝑚. Rám byl po obvodě polepen body, vytvořenými z černé a bílé samolepicí tapety.

4.2

VisualSFM

VisualSFM je SFM software (dostupný z [8]), který umožňuje spouštět software CMVS (dostupný z [9]) a PMVS2 (dostupný z [10]). Ke zpracování modelu byl použit VisualSFM V 0.5.16, CMVS 3/27/2011 a PMVS2 7/13/2010. Požití VisualSFM je velmi jednoduché, jak je ukázáno na obrázku 4.4. Krokem 1 se nahrají snímky, buď samostatné, nebo je možné nahrát výstup ze software Bundler. Krokem 2 je spuštěn proces vyhledání a spárování feature bodů. Krok 3 slouží k rekonstrukci řídkého mračna bodů, kdy se určí poloha projekčních center kamer a 3D souřadnice

57

ČVUT Praha


významných bodů objektu. Ještě než bude použit krok 4, doporučuje se použít ikonu 𝐵𝐴 (Bundle Adjustment), pokud byly nahrány samostatné snímky. Ikonou je spuštěno svazkové vyrovnání. Následuje krok 4, kdy je spuštěna rekonstrukce povrchu objektu.

Obr. 4.4: Toolbar VisualSFM, použito z [8] Správnost obnovy structure a motion může být zkontrolována přímo vizuálně, což je patrné z obrázku 4.5.

Obr. 4.5: Provedená rekonstrukce structure a motion Nicméně nastala jedna komplikace při obnově structure a motion. Jelikož se pohyboval objekt a kamera zůstala v jedné pozici a bylo nastaveno celkem velké clonové číslo, tak na snímku bylo zachyceno pozadí. SIFT algoritmus vyhledával feature i mimo objekt, což vedlo k degeneraci řešení SFM. Model nebyl spojen v jeden celek, ale různé části modelu byly promíchány. Řešením bylo rozostřit pozadí snímku tak, aby SIFT algoritmus nebyl schopen detekovat žádné feature nebo jen velmi malé

58

ČVUT Praha


množství feature mimo snímaný objekt. Rozostření bylo provedeno hlavně v dolní části objektu, kdy byla zachycena textura podložky.

4.2.1

Nastavení CMVS a PMVS2

CMVS (Clustering Views for Multi-view Stereo) Mnoho multi-view stereo (MVS) algoritmů nezpracuje velké množství vstupních snímků (nedostatek výpočetních zdrojů a paměti). Software CMVS má za svůj vstup výstupní data z SFM software, kdy rozloží vstupní snímky do skupin snímků zpracovatelné velikosti. Pak může být použit PMVS2 software ke zpracování každé skupiny nezávisle a souběžně. Nastavení CMVS a PMVS Nastavení CMVS a PMVS2 je provedeno konfiguračním souborem (nv.ini ) software VisualSFM, který je umístěn v jeho složce. Důležitými parametry pro rekonstrukci povrchu objektu jsou: ∙ param_cmvs_max_images nastavuje maximální počet snímků ve skupině, která má být zpracována PMVS2, ∙ param_pmvs_min_image je minimální počet snímků pro rekonstrukci patch, ∙ param_pmvs_level určuje úroveň převzorkování snímků, ∙ param_pmvs_csize je krok, kdy se má PMVS2 pokusit vyhledat nový patch, ∙ param_pmvs_wsize určuje nastavení fotometrické optimalizace, ∙ param_search_multiple_models nastavuje, zda má být vytvořen jeden model (0), či více (1). Experiment testující jednotlivá nastavení Pro všechny případy bylo nastaveno param_pmvs_min_image na 3, param_search_multiple_models na 0 a param_cmvs_max_images na 50, ale hodnota nebyla uplatněna, když bylo k rekonstrukci použito 8 snímků.

59

ČVUT Praha


Obrázek level

csize

wsize

Počet patch [tis.] Doba výpočtu [min]

Model 1

0

3

7

564

11

Model 2

1

3

7

338

5

Model 3

1

3

14

410

7

Model 4

1

5

7

104

2

Model 5

0

1

14

1026

23

Model 6

1

2

7

797

8

Tab. 4.2: Jednotlivá nastavení testovacích modelů

Obr. 4.6: Model 1

Obr. 4.7: Model 2

Obr. 4.8: Model 3

Obr. 4.9: Model 4

60

ČVUT Praha


Obr. 4.10: Model 5

Obr. 4.11: Model 6

Jako nejuspokojivější výsledek bylo shledáno nastavení param_pmvs_level = 1, param_pmvs_csize = 3 a param_pmvs_wsize = 14, kdy počet patch dosahoval přiměřeného počtu, výpočetní čas byl v rozumných hranicích a vizuální kontrola dopadla nejlépe.

Dále bylo prozkoumáno, jaký vliv na zašumění modelu bude mít změna param_pmvs_min_image. Byl proveden pokus na části modelu s nastavením tohoto parametru na 5 (obrázky 4.13 a 4.15). Konečný model byl zrekonstruován s parametrem nastaveným na 3 (obrázky 4.12 a 4.14).

Obr. 4.12: Model hlavy, nastaveno na 3

Obr. 4.13: Model hlavy, nastaveno na 5

61

ČVUT Praha


Obr. 4.14: Model pařezu, nastavení 3

Obr. 4.15: Model pařezu, nastavení 5

Z obrázků 4.12, 4.13, 4.14 a 4.15 je patrné, že na výsledném modelu není pozorovatelné žádné zpřesnění (modely vytvořené s param_pmvs_min_image nastaveným na 5 navíc nejsou vyhlazené). Model byl automaticky vytvořen ve formátu *.ply.

4.2.2

Zpracování v Geomagic

Ke zpracování modelu byl použit software Geomagic 12 (v. 2012.0.00), detailnější popis postupu zpracování modelu v software Geomagic je popsán v [12]. Ořezání mračen

Obr. 4.16: Pohled na celkový model

Obr. 4.17: Deformace okraje mračna

62

ČVUT Praha


Jelikož spojené mračno vykazovalo velké zašumění, byla použita jednotlivá mračna zpracovaná PMVS2, která byla jednotlivě zbavena zašuměných krajů mračen. Situace je patrná z obrázků 4.16 a 4.17. Vyhlazení modelu Model byl vyhlazen s nastavením pro celý model: ∙ úroveň vyhlazení – 5, ∙ intenzita – 5, ∙ priorita křivosti – 2. Dále byly vyhlazeny jednotlivé části modelu, kde se křivost objektu měnila plynule, a model byl zašuměný, jak je ukázáno na obrázkách 4.18 a 4.19. Zde bylo zvoleno individuální nastavení.

Obr. 4.18: Výběr k vyhlazení

Obr. 4.19: Vyhlazený výběr

Určení měřítka modelu Na objektu byly změřeny čtyři délky mezi poměrně dobře identifikovatelnými body. V software Geomagic byly změřeny vzdálenosti mezi stejnými body na modelu. Pro každý pár délek bylo vypočteno měřítko:

63

ČVUT Praha


𝑚=

𝑑 𝑑𝑚

(4.1)

Kde 𝑚 je měřítko, 𝑑 je délka měřená na objektu a 𝑑𝑚 je délka měřená na modelu.

Byly vypočteny čtyři měřítka, výsledné měřítko bylo určeno, jako průměr z určených měřítek. V software Geomagic bylo změněno měřítko modelu podle vypočtené hodnoty a celý proces byl ještě jednou zopakován. Výstupní modely Byly vytvořeny tři modely, každý model byl exportován do *.stl, *.wrl, *.wrp: ∙ VSFM_technicky.* je model, ve kterém nejsou zaplněny velké díry. Má technické využití, kdy povrch modelu je vytvořen z měřených dat, vyjímkou jsou jen malé otvory, které byly zaplněny v místech, kde se plynule měnila křivost povrchu. ∙ VSFM_prezentacni.* je model se všemi zaplněnými otvory, kromě spodní plochy podstavce. Model slouží k prezentačním účelům. ∙ VSFM_prezentacni_uzavreny.* je model s uzavřenou spodní plochou podstavce. Model je určen pro 3D tisk.

4.2.3

Porovnání modelu s referenčním modelem

Byl vytvořen referenční model triangulačním skenerem KONICA VI-9I s MIDDLE objektivem. Skenerem bylo pořízeno 96 skenů. Referenční model byl vytvořen v software Geomagic. Model vytvořený VisualSFM a PMVS2 byl porovnán s referenčním modelem v software Geomagic a vznikl tak rozdílový rastr modelů, jak je ukázáno na obrázku 4.20 a 4.21.

64

ČVUT Praha


Obr. 4.20: Rozdílový rastr s rozpětím stupnice ±2 𝑚𝑚


65

ČVUT Praha


Z rozdílových rastrů by mohlo být uvažováno o reálné přesnosti vytvořeného modelu se směrodatnou odchylkou kolem 1 𝑚𝑚, tato hodnota popisuje hlavně přesnost určení měřítka modelu, kde hrozí největší chyba. Samotné zachycení a rekonstrukci detailů modelu, nelze moc ovlivnit. Měřítko je obdrženo z přímo měřených délek a délek měřených v modelu. Ze zákona hromadění středních chyb a průměrování měřítka je jasné, že přesnost určení měřítka může být zlepšena více měřeními (změření více délek na objektu a modelu). Pokud nebudeme brát v úvahu přesnost měřidla a měřené délky budou přibližně stejně velké, jako je objekt (zabrání se tím extrapolaci chyby určení měřítka), pak lze z rovnice 4.1 určit střední chybu měřítka:

2 𝜎𝑚

(︂

1 = 𝑑𝑚

)︂2

·

(︃

𝑑 + − 2 𝑑𝑚

𝜎𝑑2

)︃2

· 𝜎𝑑2𝑚

(4.2)

Kde 𝜎𝑚 je střední chyba měřítka, 𝑑 je délka měřená na objektu, 𝜎𝑑 je střední chyba délky měřené na objektu, 𝑑𝑚 je délka měřená na modelu, 𝜎𝑑𝑚 je střední chyba délky měřené na modelu. Střední chyba měřené délky v modelu bude:

𝜎𝑑2𝑚 =

(︂

1 𝑚

)︂2

· 𝜎𝑑2

(4.3)

Kde 𝑚 je měřítko. Střední chybu měřítka lze upravit dosazením 4.3 do 4.2: 2 𝜎𝑚

(︂

1 = 𝑑𝑚

)︂2

·

𝜎𝑑2

(︃

𝑑 + − 2 𝑑𝑚 · 𝑚

)︃2

· 𝜎𝑑2 =

𝑑2𝑚 · 𝑚2 + 𝑑2 2 · 𝜎𝑑 𝑑4𝑚 · 𝑚2

(4.4)

Lze zavést aproximaci:

𝑑𝑚 · 𝑚 ≈ 𝑑

(4.5)

Vztah 4.5 dosadíme do rovnice 4.4 a upravíme:

2 𝜎𝑚 =

2 𝑑2 + 𝑑2 2 · 𝜎𝑑 = 2 · 𝜎𝑑2 2 2 𝑑𝑚 · 𝑑 𝑑𝑚

(4.6)

Aproximujeme délku měřenou na modelu:

𝑑𝑚 ≈

𝑑 𝑚

Aproximaci 4.7 dosadíme do rovnice 4.6 a výraz upravíme:

66

(4.7)

ČVUT Praha


2 =2· 𝜎𝑚

𝑚2 2 𝜎𝑚 √ 𝜎𝑑 ⇒ = 2· · 𝜎 𝑑 𝑑2 𝑚 𝑑

(4.8)

Ze vztahu 4.8 lze vyčíst, že relativní střední chyba měřítka je přímo úměrná relativní střední chybě měřené délky. Průměrné měřítko se vypočte:

𝑚𝜑 =

𝑚1 + . . . + 𝑚𝑛 𝑛

(4.9)

Střední chyba průměrného měřítka bude: 2 = 𝜎𝑚 𝜑

(︂ )︂2

1 𝑛

· 𝜎𝑚21 + . . . +

2 𝜎𝑚 = 𝜑

(︂ )︂2

1 𝑛

· 𝜎𝑚2𝑛

2 𝑛 · 𝜎𝑚 𝑛2

𝜎𝑚 𝜎𝑚𝜑 = √ 𝑛

(4.10)

Rovnici 4.10 rozšíříme: 𝜎𝑚𝜑 ·

1 𝜎𝑚 1 =√ · 𝑚 𝑛 𝑚

Následně do rovnice 4.11 dosadíme vztah 4.8: √ 𝜎𝑚𝜑 2 · 𝜎𝑑 = √ 𝑚𝜑 𝑛·𝑑

(4.11)

(4.12)

Ze vztahu 4.12 lze vyčíst, že relativní střední chyba průměrného měřítka je přímo úměrná relativní střední chybě délky na objektu a nepřímo úměrná odmocnině počtu měřených délek. Definujeme střední chybu modelu, jako délku modelu vynásobenou střední chybou měřítka. Jinak řečeno, chybu modelu můžeme chápat jako rozdíl délky modelu a délky objektu a při správně určeném měřítku by mělo platit: 𝑑𝑚 − 2 · 𝜎𝑚𝜑 · 𝑑𝑚 ≤ 𝑑 ≤ 𝑑𝑚 + 2 · 𝜎𝑚𝜑 · 𝑑𝑚 Pak lze zapsat střední chybu modelu, jako:

𝜎𝑚𝑜𝑑𝑒𝑙 ≈ 𝜎𝑚𝜑 · 𝑑𝑚

(4.13)

Následně do rovnice 4.12 dosadíme za 𝑚𝜑 vztah pro 𝑚 z rovnice 4.1 a obdržíme:

67

ČVUT Praha


√ 𝜎𝑚𝜑 · 𝑑𝑚 2 · 𝜎𝑑 = √ 𝑑 𝑛·𝑑 Dosadíme vztah 4.13 do rovnice 4.14: √ 2 2 𝜎𝑚𝑜𝑑𝑒𝑙 = √ · 𝜎𝑑 = √ · 𝜎𝐵𝑂𝐷 𝑛 𝑛

(4.14)

(4.15)

Kde 𝜎𝐵𝑂𝐷 je střední chyba určení polohy bodu na objektu. Pokud bychom vzali v úvahu, že směrodatná odchylka určení bodu na objektu je 1 𝑚𝑚 a pokud by byly změřeny 4 délky, jako v případě modelu vytvořeného VisualSFM a PMVS2, směrodatná odchylka modelu by odpovídala 1 𝑚𝑚 (za předpokladu měření přibližně stejně velkých délek, jako je model). Tento předpoklad přibližně platí i v případě určení měřítka modelu vytvořeného VisualSFM. Rozdílové rastry modelů potvrzují tuto hypotézu. Maximální chyba nastane na hlavě a podstavci modelu, což je patrné z obrázků 4.20 a 4.21.

4.2.4

Zhodnocení VisualSFM

V software VisualSFM byl vyhotoven model sochy. Pokud se zaměříme na časovou náročnost tvorby modelu, tak nasnímání objektu trvalo přibližně půl dne. Následovala editace snímků (s objektem bylo v průběhu snímání otáčeno), kdy byla rozostřena nasnímaná podložka. Tato práce trvala několik hodin. Zpracování ve VisualSFM zabralo asi 10 až 12 hodin, kdy se jedná jen o výpočetní čas. Následovalo zpracování v Geomagic, které zabralo asi půl dne. Pokud se tedy jedná o čas potřebný k vytvoření modelu, můžeme uvažovat o časové dotaci jeden a půl až dva dny. Byla dosažena přesnost pohybující se kolem 1 𝑚𝑚, což je velmi uspokojivý výkon na volně stažitelný software. Navíc ovládání je velmi intuitivní.

4.3

Agisoft PhotoScan

Agisoft PhotoScan je software určený pro tvorbu 3D modelů ze statických snímků. Software vychází z technologie multi-view 3D rekonstrukce. Snímky mohou

68

ČVUT Praha


být pořízeny z jakékoli pozice, kdy objekt je viditelný alespoň na dvou snímcích. Proces rekonstrukce je plně automatizovaný. Zpracování proběhlo v Agisoft PhotoScan Profesional Edition V 0.8.3.

4.3.1

Zpracování v Agisoft PhotoScan

Rozbalením menu Workspace a výběrem Add Chunk se přidá nový chunk. Rozbalením menu Chunk a výběrem Add Photos. . . se přidají snímky do chunk. Rozvinutím menu Chunk a volbou Align Photos. . . je spuštěn průvodce vytvořením řídkého mračna bodů (obrázek 4.22).

Obr. 4.22: Okno funkce Align Photos. . . Kde Accuracy (přesnost zarovnání snímků) může být nastavena na High (vysokou), Medium (střední) a Low (nízkou) a Pair preselection (předvolba párů) na Disabled (vypnuto), Generic (software určí páry sám) a Ground Control (propojovacími body). Model byl vytvořen s nastavením Accuracy na Medium a Pair preselection na Generic. Takto byla vytvořena jednotlivá mračna vertikálních řad. Všechny snímky software nebyl schopen zarovnat (výpočet trval 37 hodin), jak je ukázáno na obrázku 4.23.

69

ČVUT Praha


Obr. 4.23: Výsledek zarovnání všech snímků Následně byly jednotlivé Chunk postupně spojeny do jednoho modelu. Spojení dvou a více Chunk se provede spuštěním funkce Align Chunks. . . v menu Workflow. Dialogové okno funkce Align Chunks. . . je ukázáno na obrázku 4.24.

Obr. 4.24: Okno funkce Align Chunks. . . V dialogovém okně je na výběr nastavení metody (Method ), které může být nastavena na Point based (bodová) a Marker based (s užitím značek). Dále se volí

70

ČVUT Praha


přesnost (Accuracy), kde je na výběr High (vysoká), Medium (střední) a Low (nízká). Pro tvorbu modelu bylo využito nastavení metody Point based a přesnosti Medium a to z důvodu časové náročnosti výpočtu. Tímto krokem jsou snímky orientovány v jednom modelu. Nyní je možné přistoupit k vygenerování 3D modelu objektu. Generování povrchu modelu se provede funkcí Build Geometry. . . v menu Workflow. Okno funkce je zobrazeno na obrázku 4.25.

Obr. 4.25: Okno funkce Build Geometry. . . V okně funkce Build Geometry. . . je možnost nastavení: ∙ Object type (typ objektu) s volbami Arbitary (vhodný pro uzavřené objekty) a Height field (vhodný pro rovinné objekty – reliéfy). ∙ Target quality (požadovaná kvalita) s možnostmi vytvoření mračna bodů (Point cloud - vytvoří řídké mračno) a vytvoření polygonové sítě (Lowest, Low, Medium, High, Ultra High - vytváří polygonovou síť od nejnižší kvality až po nejvyšší kvalitu). ∙ Geometry type (typ tvaru objektu) s nastavením Sharp (vhodné pro členitější objekty) a Smooth (vhodné pro hladší objekty). ∙ Face count (počet polygonů) vygenerované sítě. ∙ Filter treshold je práh filtru pro malé komponenty v procentech z celkového modelu.

71

ČVUT Praha


∙ Hole treshold je práh pro zaplnění děr v procentech z celkového modelu. Model měl být vygenerován s nastavením, které je uvedeno na obrázku 4.25. Nicméně po cca 40 hodinách, kdy byly generovány body (cca 165 mil. bodů po filtraci) byl výpočet ukončen. Decimace polygonové sítě běžela 10 hodin a stále byla na 0% výpočtu. Byl vytvořen nový model s nastavením Align Chunks. . . , kde metoda byla zvolena Point based a přesnost High. Model byl exportován ve fázi řídkých bodů ve formátu *.ply. Na tomto modelu byla testována přesnost rekonstrukce projekčních center kamer, což se projeví torzí modelu.

4.3.2


V software Geomagic byla provedena filtrace odlehlých bodů a model byl vyhlazen s nastavením: ∙ úroveň vyhlazení – 4, ∙ intenzita – 4, ∙ priorita křivosti – 4. Zde byla zvolena vyšší priorita křivosti, aby byly zachovány detaily objektu. Následně bylo určeno měřítko ze čtyř délek měřených na objektu. Výstupní modely Byly vytvořeny tři modely, jako v předchozích případech: ∙ Agisoft_technicky.*, ∙ Agisoft_prezentacni.*, ∙ Agisoft_prezentacni_uzavreny.*.

72

ČVUT Praha

4.3.3



Model vytvořený Agisoft PhotoScan byl porovnán s referenčním modelem v software Geomagic 12, byly vytvořeny rozdílové rastr modelů, jak je ukázáno na obrázku 4.26 a 4.27.



73

ČVUT Praha


Z rozdílových rastrů by mohlo být uvažováno o reálné přesnosti vytvořeného modelu se směrodatnou odchylkou pod 1 𝑚𝑚.

4.3.4

Zhodnocení Agisoft PhotoScan

Byl vyhotoven model sochy v software Agisoft PhotoScan. Snímání objektu zabralo přibližně půl dne (jako v předchozím případě). Samotné generování řídkého mračna zabralo přibližně den a zpracování v Geomagic trvalo přibližně půl dne. Pokud bychom chtěli vytvořit takovýto model, potřebovali bychom přibližně dva dny na zpracování. Byla dosažena přesnost modelu pohybující se kolem 2 𝑚𝑚, což je na model z řídkého mračna dobrý výkon. Avšak při zhodnocení modelu na obrázcích 4.26 a 4.27 dojdeme k závěru, že model je zkroucený. Jeho horní a dolní část oproti referenčnímu modelu vykazuje „vnoření“ do referenčního modelu a jeho střední část pravý opak.

4.4

Photomodeler Scanner

Ke zpracování modelu byl použit Photomodeler Scanner 2012.0.0.586. Photomodeler Scanner využívá stereopáry k rekonstrukci povrchu objektu. Aby bylo dosaženo přijatelného základnového poměru, byl objekt zachycen po stranách snímků (pro levý snímek na pravé straně a pro pravý snímek na levé straně). Takže by kamera byla orientována pouze z necelé poloviny snímku. Proto byl použit rám, který zvětšil pokrytí plochy snímku body, ze kterých byl snímek orientován. Proces zpracování probíhal ve třech krocích. V prvním kroku byly určeny souřadnice bodů (kruhové terčíky černé barvy) na modelu. V druhém kroku byl přiorientován rám pro jednotlivé strany, ze kterých byl objekt snímán. V posledním kroku byly orientovány stereopáry.

74

ČVUT Praha

4.4.1


Zpracování v Photomodeler Scanner

Automatické označení bodů a automatická reference Bylo využito automatického označování bodů, kdy software vyhledá nalepené body na objektu a rámu a označí jejich střed. Funkce se spustí z menu Marking volbou Automatic Target Marking. . . a je zobrazeno okno funkce (obrázek 4.28).

Obr. 4.28: Okno funkce Automatic Target Marking. . . Zde je možnost určit typ bodu, který má být vyhledán. Na objektu a rámu byly rozmístěny kruhové body bílé a černé barvy. Proto byl Target type (typ bodu) nastaven na Dots (tečky) a Target color (barva bodu) na Both (černá i bílá). Nejprve bylo zapotřebí určit polohu bodů modelu v prostoru. Proto byly první body referencovány ručně. Když byla určena poloha bodů v prostoru, mohla být využita funkce automatického referencování bodů, ta se spustí z menu Referencing volbou Automatic Referencing. . . a je zobrazeno okno funkce (obrázek 4.29).

Funkce se spustí příkazem Execute Referencing. Parametr Search Distance byl ponecháván na implicitní hodnotu, pokud funkce referencovala dostatečné množství bodů. Jinak je možnost upravit prohledávané okolí navýšením tohoto parametru, nicméně je zde nebezpečí, že funkce vyhledá a referencuje chybný bod. K referencování chybných bodů i přesto docházelo, v tomto projektu byly tři páry různých bodů, kterým se jejich reference propojovaly. Po zpracování modelu (Process) byly těmto bodům kompletně zrušeny reference a byly dále automaticky referencovány

75

ČVUT Praha


Obr. 4.29: Okno funkce Automatic Referencing. . . další snímky. Po automatické referenci posledního snímku určité fáze zpracování byly tyto páry referencovány manuálně a byl vypočten model (Process). Kompletní model včetně rámu byl vytvořen s využitím automatických referencí. Nicméně automatické referencování přestalo fungovat, pokud byly do projektu nahrány snímky z jiné kamery. Tato fáze nastala až po přiorientování rámu. Výpočet modelu Nejprve byl vypočten model, který se skládal z nalepených bodů na objektu. Na tyto body byly přiorientovány rámy (pro každou z osmi stran objektu), účelem tohoto kroku bylo vypočítat souřadnice pomocných bodů rámu k lepší orientaci kamery. Tento model charakterizují parametry uvedené v tabulce 4.3. Overall RMS

0.547 pixelů

Maximum

2.112 pixelů

Overall RMS Vector Length

0.00019

Maximum Vector Length

0.000375

Tab. 4.3: Parametry modelu s rámem Následně bylo určeno měřítko modelu, k tomu účelu posloužil rám, na kterém se změřili délky mezi nalepenými body. Nejprve bylo měřítko udáno pomocí jedné délky funkcí Scale/Rotate (obrázek 4.30) v menu Project.

76

ČVUT Praha


Obr. 4.30: Okno funkce Scale/Rotate Měřítko se zadá definováním vzdálenosti dvou bodů. Distance je vzdálenost mezi body a Define určíme dva body, mezi kterými byla délka měřena. Jelikož rám byl přiorientován osmkrát, bylo změřeno 16 délek mezi modelovými souřadnicemi. Takže bylo možno vypočítat dvě délky z osmi měření (modelové souřadnice bodů rámu byly určeny jen z 3 snímků). Byly určeny rozdíly mezi měřenými délkami na rámu a délkami určenými z modelových souřadnic. Rozdíly byly zprůměrovány. Byla odečtena jedna délka na rámu a tento průměr rozdílů byl k ní přičten. Následně bylo nastaveno měřítko znovu na bodech, mezi kterými byla odečtena délka. Tím bylo určeno měřítko modelu. Modelu odpovídají hodnoty uvedené v tabulce 4.4.

Overall RMS

0.547 pixelů

Maximum

2.112 pixelů


0.127 mm


0.251 mm

Tab. 4.4: Parametry modelu s rámem v měřítku

Hodnoty jsou ukazatel kvality modelu. Následně byly orientovány stereopáry, v tomto kroku přestala fungovat automatická reference. Po zorientování všech snímků byl vytvořen model s charakteristikami uvedenými v tabulce 4.5.

77

ČVUT Praha


Overall RMS

1.415 pixelů

Maximum

12.843 pixelů


0.161 mm


0.619 mm

Tab. 4.5: Parametry modelu se všemi snímky Kalibrace kamery a její přiřazení snímkům Jelikož maximální chyba byla poměrně veliká a označení bodu bylo zkontrolováno, byla provedena reverzní kalibrace. Photomodeler Scanner 2012.0.0.586 má v kalibraci definováno, že kódované body tvoří přesně čtverec. Předpoklad nebyl splněn vlivem různé srážky a deformací kalibračního pole. Reverzní kalibrace mohla být provedena pouze v projektu s jedinou kamerou. Proto byl projekt uložen, jako nový projekt a snímky pořízené kamerou s konstantou komory 35 𝑚𝑚 byly smazány. Byla provedena reverzní kalibrace, kdy se konstanta komory celkem výrazně změnila, jak je patrné z obrázků 4.31 a 4.32.

Obr. 4.31: Původní kalibrační parametry kamery

78

ČVUT Praha


Obr. 4.32: Kalibrační parametry kamery z reverzní kalibrace Nová kamera byla nahrána do projektu (z projektu ve kterém byla kalibrována). K nahrání kamery slouží Load from disk. . . , jak je ukázáno na obrázku 4.31. Následně musela být nově kalibrovaná kamera přiřazena snímkům. To se provede označením všech snímků, kterým má být kamera změněna. Přidržením klávesy Shift a pravým tlačítkem myši se rozbalí roletové menu a zvolí se položka Properties of selected photo(s). . . a tím je zobrazeno dialogové okno vlastností snímků, kde může být kamera změněna (obrázek 4.33).

Obr. 4.33: Okno vlastností snímků

79

ČVUT Praha


Výpočet konečného modelu Po vypočtení modelu s nově kalibrovanou kamerou byly určeny parametry uvedené v tabulce 4.6. Overall RMS

1.138 pixelů

Maximum

8.605 pixelů


0.128 mm


0.492 mm

Tab. 4.6: Parametry modelu s kalibrovanou kamerou (reverzní kalibrace)

Oprava snímků o distorzi Následně byl projekt idealizován použitím Idealize Project. . . v menu Project. Tím byly snímky opraveny o distorzi. Komplikací bylo, že Photomodeler Scanner nebyl schopen opravit všechny snímky (184) v jednom kroku. Proto byly snímky idealizovány po částech, nicméně každé části byla přiřazena vlastní kamera a v následujícím kroku přiřazena snímkům jediná kamera. Určení oblasti pro generování mračna

Obr. 4.34: Ukázka definování Trim ve snímku Snímkům byly určeny oblasti pro výpočet mračna (funkce DSM Trim Mode). Snímek s takto vytvořeným Trim je na obrázku 4.34.

80

ČVUT Praha


Generování a export mračna bodů Nyní mohlo být přistoupeno ke generování mračna bodů. Nástroj se spustí Create Dense Surface. . . v menu Dense Surface (obrázcích 4.35 a 4.36).

Obr. 4.35: Create Dense Surface. . .

Obr. 4.36: Create Dense Surface. . .

(nastavení generování mračna)

(nastavení úpravy mračna)

Jako optimální nastavení pro generování mračna (DSM Options) bylo po řadě experimentů zvoleno: ∙ Sampling interval - 1.0000 (parametr určující vzdálenost bodů na povrchu objektu). ∙ Sampling interval units - 𝑚𝑚 (nastavení jednotek předchozího parametru). ∙ Extents from - DSM Trims (whole photo boundary – mračno bude vytvořeno z celého snímku, DSM Trims – mračno bude vytvořeno z vybraných oblastí).

81

ČVUT Praha


∙ Depth range - [60.000𝑚𝑚/60.000𝑚𝑚] (parametr určující maximální odlehlost bodu od generovaného povrchu). ∙ Matching region radius - 10 (parametr určuje velikost korelačního okna, při nastavení na 30 byly v modelu vytvořeny „odskoky“ , zde je vhodné volit tento parametr radši menší). ∙ Type texture - 1 (parametr určující jedinečnost textury 1 − 10). ∙ Downsample factor - 2 (parametr určující downsampling snímku, 0 – software určí hodnotu sám, 1 – bude ponechán původní snímek, 2 – snímek bude mít poloviční rozlišení). ∙ Run isolated point filter - Ano (použití filtru na izolované body). ∙ Sub-pixel - True (použití subpixelové metody). ∙ Super-sampling factor - 8 (faktor ovlivňující zvlnění povrchu). Z dalšího zpracování mračna bylo využito pouze zasíťování mračna (Triangulation) bez potlačení šumu. Nevýhodou bylo postupné generování mračen. Každá z osmi stran musela být rozdělena na poloviny, jinak software nebyl schopen otevřít 3D View pro export jednotlivých mračen. Každé mračno bylo označeno a exportováno zvlášť funkcí Save PointMesh. . . v menu Dense Surface. Mračna byla exportována ve formátu *.ply.

4.4.2


Z Photomodeler Scanner bylo obdrženo 94 mračen. Ta byla registrována globální registrací s výsledkem registrace uvedeným v tabulce 4.7.

Average Distance

0.595287

Standard Deviation

0.329135

Tab. 4.7: Hodnoty obdržené z registrace mračen

82

ČVUT Praha


Model byl vyhlazen s nastavením: ∙ úroveň vyhlazení – 3, ∙ intenzita – 2, ∙ priorita křivosti – 0. Úroveň vyhlazení je patrná na obrázku 4.37.

Obr. 4.37: Model před a po vyhlazení

Výstupní modely Byly vytvořeny tři modely, jako v předchozích případech: ∙ Photomodeler_technicky.*, ∙ Photomodeler_prezentacni.*, ∙ Photomodeler_prezentacni_uzavreny.*.

4.4.3


Model vytvořený Photomodeler Scanner byl porovnán s referenčním modelem v software Geomagic 12 a vznikl tak rozdílový rastr modelů, jak je ukázáno na obrázku 4.38 a 4.39.

83

ČVUT Praha



Obr. 4.39: Rozdílový rastr s rozpětím stupnice ±1 𝑚𝑚 Z rozdílových rastrů by mohlo být uvažováno o reálné přesnosti vytvořeného modelu se směrodatnou odchylkou pod 1 𝑚𝑚.

84

ČVUT Praha

4.4.4


Zhodnocení Photomodeler Scanner

V software Photomodeler Scanner byl vyhotoven model sochy. Snímky byly pořízeny během půl dne i s nalepením bodů na objekt. Zpracování v software Photomodeler Scanner trvalo jeden a půl týdne. Nejvíce času zabralo referencování bodů. Zde by bylo na místě zaměřit se právě na tuto problematiku. Protože se jedná o komerční software, tak taková časová náročnost není na místě. Vše bylo hlavně způsobeno problémy s automatickou referencí, která přestala fungovat, když byla nahrána druhá kamera. Dalším problémem bylo chybné automatické referencování. Nemohla být exportována jednotlivá mračna v dávce, nemožnost idealizovat celý projekt v jednom kroku a problémy při otevírání 3D View s větším množstvím mračen. Dosažená přesnost modelu se pohybovala kolem 1 𝑚𝑚.

85

ČVUT Praha

5

5. POROVNÁNÍ RELATIVNÍ PŘESNOSTI JEDNOTLIVÝCH METOD

Porovnání relativní přesnosti jednotlivých metod Cílem experimentu je otestovat relativní přesnost jednotlivých metod, kdy v

předchozí kapitole byla určována absolutní přesnost (i s chybou určení měřítka). Relativní přesnost je tedy dosažena potlačením vlivu chybného určení měřítka. Jednotlivé modely budou pak porovnány s referenčním modelem.

5.1

Pořízení dat

K otestování relativní přesnosti byl obličej objektu nasnímán objektivem Canon EF 50 mm f/1.8 II z velké blízkosti (cca 30 až 40 𝑐𝑚), kdy bylo pořízeno 58 snímků. Dále byl obličej objektu naskenován triangulačním skenerem KONICA VI-9I s objektivem TELE. Nakonec byl využit již existující model vytvořený v software Photomodeler Scanner (zde byly snímky pořízeny stejným objektivem, ale ze vzdálenosti kolem 80 𝑐𝑚).

5.2 5.2.1

Zpracování modelů Zpracování VisualSFM

Model byl vytvořen s nastavením: ∙ param_pmvs_min_image - 5, ∙ param_pmvs_level – 1, ∙ param_pmvs_csize – 3, ∙ param_pmvs_wsize – 20. Zde byl navýšen param_pmvs_min_image z 3 na 5 z důvodu zašumění dat. Dále byl zvýšen param_pmvs_wsize na 20, pro lepší fotometrickou konzistenci při výpočtu modelu.

86

ČVUT Praha


Dále byl model editován v software Geomagic, aby odpovídal reálnému modelu objektu (bez tunelů, průsečíků trojúhelníků, atd.).

5.2.2

Zpracování Agisoft PhotoScan

Model byl vytvořen s nastavením Align Photos. . . : High (Accuracy) a Generic (Pair preselection). Nastavení Build Geometry bylo Arbitary (Object type), High (Target quality), Sharp (Geometry type), 2000000 (Face count), 0,5 (Filter treshold ) a 0,1 (Hole treshold ). Následně byl model zpracován v software Geomagic.

5.3

Potlačení vlivu měřítka

Nejprve bylo určeno přibližné měřítko modelu. Pak byly jednotlivé modely registrovány v programu Geomagic na referenční model (Konica). Následně bylo určeno měřítko z měřených vzdáleností na modelech. Nakonec měřítko bylo určováno iteračně, kdy z registrace byla použita Average Distance (průměrná vzdálenost) a přičítána nebo odčítána od střední délky v modelu (vzdálenost mezi tvářemi) a tím bylo určováno nové měřítko. Proces byl zastaven ve chvíli, kdy Average Distance a Standard Deviation (směrodatná odchylka) přestaly konvergovat, což bylo patrné na modelech, kdy síť jednoho z nich začala vystupovat nad síť druhého modelu. Tímto postupem byla eliminována chyba z určení měřítka.

5.4

Porovnání v Geomagic

V software Geomagic byly vytvořeny rozdílové rastry modelů.

5.4.1

Porovnání VisualSFM

Z rozdílových snímků (obrázky 5.1 a 5.2) lze vyčíst, že VisualSFM si dobře vedl v oblastech s plynulou změnou křivosti. Nicméně v oblastech, kde je křivost vyšší dosahoval rozdílu modelů až 0, 5 𝑚𝑚. Kdybychom měli odhadovat směrodatnou odchylku, tak by její hodnota mohla být někde mezi 0, 25 až 0, 30 𝑚𝑚. Což je poměrně dobrý výsledek.

87

ČVUT Praha


Obr. 5.1: Rozdílový rastr při pohledu zepředu

Obr. 5.2: Rozdílový rastr při pohledu zespoda

5.4.2

Porovnání Agisoft PhotoScan

Zde model dopadl jednoznačně nejlépe ze všech (obrázky 5.3 a 5.2). Software si vedl dobře i v oblastech s vyšší křivostí. U tohoto modelu by se směrodatná odchylka mohla pohybovat někde kolem 0, 05 až 0, 07 𝑚𝑚, což je velmi dobrý výsledek.

88

ČVUT Praha




89

ČVUT Praha

5.4.3


Porovnání Photomodeler Scanner

Tento model dopadl nejhůře (obrázky 5.5 a 5.6), ale to je způsobeno daty, která byla pořízena z větší vzdálenosti. Z obrázků je patrné, že model byl celkem vyhlazen (velké rozdíly v oblastech se změnou křivosti). Nicméně odhad směrodatné odchylky kolem 0, 2 až 0, 25 𝑚𝑚 je rovněž příznivý.



90

ČVUT Praha


Porovnání v Matlab

5.5

K provedení nezávislého porovnání přesnosti byl použit Matlab. Vstupními daty byla registrovaná mračna jednotlivých metod tvorby povrchu 3D objektu a referenční mračno bodů (Konica). Jelikož byla mračna registrovaná, byla jejich poloha brána jako fixní. Pro jednotlivé body mračna dané metody byly vypočteny vzdálenosti k nejbližšímu bodu referenčního mračna. Byla vypočtena průměrná vzdálenost a ze souboru vypočtených délek byly odstraněny odlehlé hodnoty (některá mračna byla pořízena s nalepenými terčíky na objektu). Výpočet probíhal iteračně, kdy byly odstraněny hodnoty nad 𝑛 násobek průměrné vzdálenosti bodů. Výpočet konvergoval k průměrné hodnotě délky, pro každý 𝑛 násobek. Výsledky jsou uvedeny v tabulkách 5.1, 5.2 a 5.3.

Pro mračno VisualSFM, byla v registraci vypočtena průměrná délka (Average Distance) 0.122807 𝑚𝑚 a směrodatná odchylka (Standard Deviation) 0.164636 𝑚𝑚. Zde byly vypočteny hodnoty průměrné délky kolem 0.1 𝑚𝑚 a směrodatné odchylky kolem 0.05 𝑚𝑚, pro mračno s vynecháním odlehlých délek.

Násobek

𝑑𝜑

𝜎𝑑𝜑

Počet délek celkem

Počet délek ve výpočtu

-

0.140924 0.130061

117921

117921

3.0

0.117608 0.066728

117921

111519

2.5

0.109021 0.054043

117921

106708

Tab. 5.1: Hodnoty výpočtu pro mračno VisualSFM

Pro mračno Agisoft PhotoScan, byla v registraci vypočtena průměrná délka (Average Distance) 0.042474 𝑚𝑚 a směrodatná odchylka (Standard Deviation) 0.048286 𝑚𝑚. Zde byly vypočteny hodnoty průměrné délky kolem 0.085 𝑚𝑚 a směrodatné odchylky kolem 0.035 𝑚𝑚, pro mračno s vynecháním odlehlých délek.

91

ČVUT Praha

Násobek


𝑑𝜑

𝜎𝑑𝜑



-

0.092094 0.078764

130517

130517

3.0

0.086478 0.036940

130517

129100

2.5

0.085426 0.034906

130517

128175

Tab. 5.2: Hodnoty výpočtu pro mračno Agisoft PhotoScan

Pro mračno Photomodeler Scanner, byla v registraci vypočtena průměrná délka (Average Distance) 0.158411 𝑚𝑚 a směrodatná odchylka (Standard Deviation) 0.163755 𝑚𝑚. Zde byly vypočteny hodnoty průměrné délky kolem 0.13 𝑚𝑚 a směrodatné odchylky kolem 0.07 𝑚𝑚, pro mračno s vynecháním odlehlých délek. Násobek

𝑑𝜑

𝜎𝑑𝜑



-

0.170948 0.143573

63046

63046

3.0

0.147291 0.086264

63046

59972

2.5

0.136490 0.071118

63046

57365

Tab. 5.3: Hodnoty výpočtu pro mračno Photomodeler Scanner

Dosažená přesnost rozdílového modelu pro Agisoft PhotoScan byla charakterizována průměrnou délkou 0.042474 𝑚𝑚 a směrodatnou odchylkou 0.048286 𝑚𝑚 pro software Geomagic a průměrnou délkou 0.092094 𝑚𝑚 a směrodatnou odchylkou 0.078764 𝑚𝑚 pro Matlab. Po odstranění odlehlých délek hodnoty klesly k 0.085 𝑚𝑚 pro průměrnou délku a k 0.035 𝑚𝑚 pro směrodatnou odchylku. Software VisualSFM dosáhl průměrnou délkou 0.122807 𝑚𝑚 a směrodatnou odchylkou 0.164636 𝑚𝑚 pro software Geomagic a průměrnou délkou 0.140924 𝑚𝑚 a směrodatnou odchylkou 0.130061 𝑚𝑚 pro Matlab, které klesly k 0.11 𝑚𝑚 pro průměrnou délku a k 0.06 𝑚𝑚 pro směrodatnou odchylku. A software Photomodeler Scanner dosáhl průměrnou délkou 0.158411 𝑚𝑚 a směrodatnou odchylkou 0.163755 𝑚𝑚 pro software Geomagic a průměrnou délkou 0.170948 𝑚𝑚 a směrodatnou odchylkou 0.143573 𝑚𝑚 pro Matlab, které klesly k 0.13 𝑚𝑚 pro průměrnou délku a k 0.07 𝑚𝑚 pro směrodatnou odchylku. Snímky pro Photomodeler Scanner byly pořízeny z větší vzdálenosti, než snímky pro Agisoft PhotoScan a VisualSFM.

92

ČVUT Praha


Závěr Diplomová práce má sloužit, jako podklad pro zpracování 3D modelů objektů metodou optického skenování. Čtenář je seznámen s teorií tvorby mračna metodami obrazové korelace, kdy jsou představeny jednotlivé prvky metody a nastíněn jejich teoretický základ. Následně je popsán postup zpracování pro tři software (VisualSFM, Agisoft PhotoScan a Photomodeler Scanner ), ve kterých byl vytvořen komplexní model. Z celkového hlediska si nejlépe vedl software VisualSFM, který je zadarmo, plně automatizovaný a výpočet byl nejkratší (asi půl dne). Z hlediska přesnosti je software VisualSFM hodnocen jako velmi dobrý, kdy dosáhl přesnosti celého modelu kolem 1 𝑚𝑚. Byly testovány dva komerční software, kde každý má jiný přístup ke generování mračna bodů. Agisoft PhotoScan stojí přibližně 180 $ a lze s ním řešit kompletní generování mračna bodů. Software má i pár funkcí na automatickou úpravu sítě (při generování). Nicméně dosáhl dvou rozporuplných výsledků. Při tvorbě modelu celé sochy byla zaznamenána torze modelu (model byl generován z řídkého mračna) a tím i horší přesnost celého modelu (asi 2 𝑚𝑚). Avšak výpočetní nároky mohou být obrovské (výpočty trvají desítky hodin i několik dní). Při modelování hlavy objektu dosáhl software Agisoft PhotoScan výtečných výsledků. Cena 180 $ je velmi dobrá za takto kvalitní software. Byl otestován software Photomodeler Scanner, který je zástupce fotogrammetrické metody. Zde byla časová náročnost zpracování opravdu velká. Jen referencování 234 snímků trvalo týden a půl. Z hlediska přesnosti modelu bylo dosaženo dobrých výsledků, kdy přesnost celého modelu mohla být kolem 1 𝑚𝑚. Z hlediska ceny se jedná o nejdražší testovaný software, avšak zpracování trvalo nejdéle. Doporučený software pro účely památkářů by mohl být VisualSFM i Agisoft PhotoScan, oba software dosáhly zajímavých výsledků a jsou buď zdarma, nebo za minimální cenu.

93

ČVUT Praha

POUŽITÉ ZDROJE

Použité zdroje [1] VÚGTK: Slovník VÚGTK WWW stránky, [online], [cit. 2012-1-6]. Dostupné z URL: . [2] WIKIPEDIA: Scale-invariant feature transform WWW stránky, [online]. Dostupné z URL: . [3] Mach, L.: Referát na Grafiku I o SIFT algoritmu na matchování fotografií WWW stránky, [online]. Dostupné z URL: . [4] Fischer, M., Bolles, R.: Random Sample Consensus: A Paradigm for Model Fitting with Apphcatlons to Image Analysis and Automated Cartography WWW stránky, [online]. Dostupné z URL: . [5] Jebara, T., Azarbayejani, A., Pentland, A.: 3D Structure from 2D Motion WWW stránky, [online]. Dostupné z URL: . [6] Heyden, A., Pollefeys, M.: Multiple view geometry WWW stránky, [online]. Dostupné z URL: . [7] Furukawa, Y., Ponce, J.: Accurate, Dense, and Robust Multi-View Stereopsis WWW stránky, [online]. Dostupné z URL: . [8] Changchang, Wu: VisualSFM WWW stránky, software, [online]. Dostupné z URL: .

94

ČVUT Praha

POUŽITÉ ZDROJE

[9] Furukawa, Y.: CMVS WWW stránky, software, [online]. Dostupné z URL: . [10] Furukawa, Y., Ponce, J.: PMVS2 WWW stránky, software, [online]. Dostupné z URL: . [11] Centrum FotoŠkoda: CANON EOS 5D Mark II WWW stránky, [online]. Dostupné z URL: . [12] Šedina, J.: Dokumentace a tvorba modelu sochy pomocí 3D skenování a prostorového tisku Praha: ČVUT 2010. Bakalářská práce, ČVUT, Fakulta stavební, Katedra mapování a kartografie. [13] PAVELKA, K.: Fotogrammetrie 20. Praha: Nakladatelství ČVUT, 2006, 193 s., ISBN 80-01-02762-7.

95

ČVUT Praha

SEZNAM SYMBOLŮ, VELIČIN A ZKRATEK

Seznam symbolů, veličin a zkratek BBF

Best Bin First

CIPA

International Scientific Committee for Documentation of Cultural Heritage

CMVS Clustering Views for Multi-view Stereo ČVUT České vysoké učení technické DoG

Difference of Gaussians

DSM

Dense Surface Models

FSv

Fakulta stavební

LD

Location Determination

MNČ

Metoda nejmenších čtverců

MVS

Multi-view Stereo

NCC

Normalized Cross Correlation

PMVS Patch-based Multi-view Stereo RANSAC Random Sample Consensus RMS

Root Mean Square

SD

Standard Deviation

SFM

Structure from Motion

SIFT

Scale-Invariant Feature Transform

SVD

Singular Value Decomposition

96

ČVUT Praha

SEZNAM PŘÍLOH

Seznam příloh A Obsah datového disku

98

97

ČVUT Praha

A

A. OBSAH DATOVÉHO DISKU

Obsah datového disku ∙ Text diplomové práce v formátu PDF ∙ Modely Agisoft PhotoScan ∙ Modely Konica ∙ Modely Photomodeler Scanner ∙ Modely VisualSFM ∙ VisualSFM_windows_64bit ∙ Rozdílové snímky modelu Agisoft PhotoScan ∙ Rozdílové snímky modelu Photomodeler Scanner ∙ Rozdílové snímky modelu VisualSFM ∙ Rozdílové snímky tváře Agisoft PhotoScan ∙ Rozdílové snímky tváře Photomodeler Scanner ∙ Rozdílové snímky tváře VisualSFM

98

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA STAVEBNÍ DIPLOMOVÁ PRÁCE

Recommend Documents