3D počítačové vidění Markéta Dubská, Bronislav Přibyl, Pavel Zemčík Ústav počítačové grafiky a multimédií Fakulta informačních technologií Vysoké učení technické v Brně
Motto
"Často potřebujeme 3D model scény, můžeme jen u existujících scén prostě sejmout?"
Přehled ● ● ● ● ●
3D rekonstrukce z jediného obrazu 3D z nekalibrované kamery 3D z kalibrované kamery Postupy rekonstrukce Výhled a závěr
Proč 3D z obrazu? ● ● ● ● ● ● ●
virtuální prohlídky zachování kulturního dědictví kontrola kvality výrobků filmový průmysl hry robotické systémy interakce s počítači
Proč 3D zrovna z obrazu? ● kamery jsou poměrně ● kamery jsou všude (na PC) ● data z kamer obsahují potřebné informace (skoro) ● když to nestačí, můžeme si pomoci světlem
3D rekonstrukce z jediného obrazu (Single-View/Monocular reconstruction)
3D z jediného obrazu ● vždy je lepší rekonstruovat 3D z více pohledů kvůli přesnosti, ale někdy máme prostě jen 1 obrázek (zničená budova, znalecký posudek místa činu, ...)
● nutná apriorní znalost parametrů kamery nebo vlastností scény, např.: ○ ○ ○ ○ ○ ○ ○ ○
velikost objektů překrytí objektů stíny, deformace textur symetrie objektů rovnoběžnost rovin/přímek kolmost rovin/přímek příslušnost bodů k rovině ...
3D z jediného obrazu nekalibrovaná kamera
kalibrace kamery
kalibrovaná kamera
výpočet 3D odhad 3D
A. odhad 3D struktury z obrazu nekalibrované kamery B. výpočet 3D struktury z obrazu kalibrované kamery
3D
3D z nekalibrované kamery Př.: Automatic Photo Pop-up. D. Hoeim, A. A. Efros a M. Herbert, ACM Transactions on Graphics 24(3), 2005.
● klasifikace částí obrazu na vodorovné a svislé plochy a pozadí ● "nařezání" svislých ploch na bilboardy ● generování nových pohledů na scénu z 1 fotografie
3D z nekalibrované kamery Př.: Nonparametric Single View Reconstruction of Curved Obects using Convex Optimization. M. R. Oswald, E. Töppe, K. Kolev a D. Cremers, Pattern Recognition, ISBN 97836420379-9, 2009, s. 171-180.
● segmentace modelu od pozadí (silueta) ● "nafouknutí" modelu v závislosti na vzdálenosti od okraje siluety ● uživatel může přidat další omezení na tvar objektu, eventuálně změnit parametry "nafouknutí" ● výsledkem je hladký povrch v podobě polyg. modelu
Geometrická kalibrace kamery = stanovení vnitřních a vnějších parametrů kamery
libovolná nenulová změna měřítka
2D bod v souřadnicích obrazu
matice kamery
rotační matice
transformační matice
?
relativní ohnisková vzdálenost [px] _____ poměr stran pixelů ___ zešikmení pixelů =_____________ souřadnice hlavního bodu (principal point)
translační vektor
kalibrační matice kamery
3D bod v souřadnicích scény
Reference - kalibrace kamery ●
The Geometry of Multiple Images: The Laws That Govern the Formation of Multiple Images of a Scene and Some of Their Applications. O. Faugeras a Q. Luong. The MIT Press, USA, 2004. ISBN 978-0-262-56204-1. Strany 236-239.
●
Multiple View Geometry in Computer Vision. R. Hartley a A. Zisserman. University Press, UK, 2006. ISBN 0521-54051-8. Strany 195-233.
●
An Introduction to 3D Computer Vision Techniques and Algorithms. B. Cyganek a J. P. Siebert. Willey, UK, 2009. ISBN 978-0-470-01704-3. Strany 70-72.
●
3D Computer Vision: Efficient Methods and Applications. Ch. Woehler. Springer Verlag, DE, 2009. ISBN 978-3-642-01731-5. Strany 17-27.
●
Three-Dimensional Computer Vision: A Geometric Viewpoint. O. Faugeras. The MIT Press, USA, 1996. ISBN 0-262-06158-9. Strany 51-65.
3D z kalibrované kamery Př.: Creating Architectural Models from Images. D. Liebowitz, A. Criminisi a A. Zisserman. Computer Graphics Forum 18(3), 1999.
● kalibrace kamery ze souřadnic úběžníků 3 navzájem kolmých směrů u, v a w
3D z kalibrované kamery Creating Architectural Models from Images. D. Liebowitz, A. Criminisi a A. Zisserman. Computer Graphics Forum 18(3), 1999.
Příklad rekonstrukce prostoru z renesanční malby a budovy.
Reference ●
Creating Architectural Models from Images. D. Liebowitz, A. Criminisi a A. Zisserman. Computer Graphics Forum 18(3), 1999.
●
Single View Metrology. A. Criminisi, I. Reid a A. Zisserman. International Journal of Computer Vision 40(2), 2000.
●
Automatic Photo Pop-up. D. Hoeim, A. A. Efros a M. Herbert, ACM Transactions on Graphics 24(3), 2005.
●
Nonparametric Single View Reconstruction of Curved Obects using Convex Optimization. M. R. Oswald, E. Töppe, K. Kolev a D. Cremers, Pattern Recognition, ISBN 97836420379-9, 2009, s. 171-180.
Structured Light
Vlastnosti ● Rozšířené v průmyslu (a dnes i obecné) ● Neinvazivní ● Přesné ● Automatické ● Závislé na detekci čar
Setup ● Zdroj světla (projektor, laser) ● Kamera (1 a více)
Triangulace ● Jednoduchá korespondence bodů
Single light stripe
● Hloubka bodu
Shrnutí ● Přesné (< 0.01 mm) ● Jeden pruh - pomalé ● Více pruhů (barev, tvarů) - složitější algoritmy, ale lepší výsledky ● Využití stínů?
Reference ●
High-accuracy stereo depth maps using structured light. D Scharstein, R Szeliski, (CVPR 2003)
●
3D Photography on your desk. Jean-Yves Bouguet and Pietro Perona (ICCV 1998)
●
Pattern codification strategies in structured light systems. Joaquim Salvi, Jordi Pagès, Joan Batlle.
●
3-D Surface Geometry and Reconstruction. U. Ch. Pati et al. Information Science Reference, USA, 2012. ISBN 978-1-4666-0113-0. Strany 9-11.
3D z dvojice obrazů (Binocular Stereo)
Binokulární stereo ● vstup: 2 obrazy téže scény zachycené z různých známých pozic ○ pokud nejsou pozice kamer známé, je nutné určit jejich vzájemnou polohu = s využitím epipolární geometrie vypočítat tzv. fundamentální matici
● algoritmus: ○ najdi korespondující body v obou obrazech ○ vypočti paprsky procházející těmito body ○ skutečný 3D bod leží na průsečíku těchto paprsků
● výstup: hloubková mapa / point cloud
Epipóly ● Projekce středů promítání na průmětnu.
Epipoláry ● Epipolára l' bodu x je projekce přímky procházejíci středem promítaní O a promítnutým bodem x v průmětně. ● Projekce bodu X leží na přímce l'.
Fundamentální matice F ● Určuje mapování x → l' ● Matice 3x3 řádu 2, 7 stupňů volnosti ● platí: ○ x'TFx = 0 ○ Fx = l', FTx' = l ○ Fe = 0, FTe' = 0
Odvození matice F ● bod x a jeho obraz x' na epipoláře l' ● epipolára l' prochází body e' a x'
● fundamentální matice
Odvození matice F pomocí projekcí ● Matice projekce kamer P, P' ○ PX = x, P'X = x'
Výpočet matice F v praxi ● Z korespondujících dvojic bodů x a x' ○ 7 dvojic - minimum ○ 8 dvojic - lineární systém rovnic ○ více dvojic - SVD, RANSAC
● iterativní metody ● nelineární metody ○ Maximum Likelihood Estimation
Esenciální matice E ● Fundamentální matice, která splňuje podmínku normalizovaných souřadnic, x̂
● Normalizované matice kamer
● Esenciální matice
Vztah F a E ● Kalibrované kamery - esenciální matice. ● Nekalibrované kamery - fundamentální mat. ● Esenciální matice má 5 parametrů (3 pro rotaci, 2 pro translaci). ● Fundamentální má 7 (2x2 pro epipóly a 3 pro homografii mezi epipolárami).
Epipolární geometrie v binokulárním stereu ● hledání korespondujících bodů se díky epipolárám redukuje z 2D problému na 1D problém rektifikace obrazů (projekce do roviny rovnoběžné se spojnicí optických středů)
● epipoláry rovnoběžné s řádky obrazu = 1D hledání korespondencí podél řádků obrazu
Hledání korespondencí Základní algoritmus:
● pro každý pixel levého obrazu (xL, yL) ○ ○ ○
porovnej jej se všemi pixely (xR, yL) na epipoláře v pravém obrazu vyber nejpodobnější pixel (xR,best, yL) disparita d = xL - xR,best disparita
X
Binokulární stereo ● hloubka z disparity: h = |OL-OR| * f / d ● při hledání korespondencí je možné porovnávat i okna, ne jen sam ostatné pixely ● problém s volbou velikosti okna
velké okno
h
f
f OL
OR
malé okno
● metrika podobnosti oken: většinou SSD (Sum of Squared Differences) ● výpočet disparity je obtížný v oblastech se slabou texturou
Reference ●
Podrobná taxonomie algoritmů pro výpočet disparity: A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. D. Scharstein a R. Szeliski, International Journal of Computer Vision 47(1), 2002.
●
An Introduction to 3D Computer Vision Techniques and Algorithms. B. Cyganek a J. P. Siebert. Willey, UK, 2009. ISBN 978-0-470-01704-3. Strany 31-70. Epipolar Geometry in Stereo, Motion and Object Recognition. G. Xu a Z. Zhang. Kluwer Academic Publishers, Holandsko, 1996. ISBN 0-7923-4199-6.
●
●
Vyhodnocení různých algoritmů pro výpočet disparity: http://vision. middlebury.edu/stereo
●
Stereo Matching by Compact Windows via Minimum Ratio Cycle. O. Veksler, 8th IEEE Conference on Computer Vision, 2001.
Multiple View Geometry
Motivace ● Matchmoving ○ určení pohybu kamery z videa
● 3D modelování ● Kalibrace kamery
Úloha F - reprojection error
Minimalizace F
● počet rovnic 2nm ● počet neznámých 2n + 6(m - 1) - 1 ● konverguje do lokálniho minima ● třeba dobrý počáteční odhad
SLAM (Simultaneous Localisation and Mapping)
SLAM ● robotika ● současné mapování neznámého prostředí + lokalizace sebe sama v tomto prostředí ● fúze informací z více vstupních senzorů: laserový dálkoměr, LIDAR, sonar, RGB(D) kamera ● indoor funguje, outdoor stále problematický ● pohyb robota v uzavřených smyčkách umožňuje zpřesnit výsledky odstraněním kumulativních chyb
SLAM: formulace
xk - pozice a orientace robota v čase k uk - řídicí vstup zadaný v čase k-1 mi - pozice význačného bodu i (statické prostředí) m = {mi | 1 <= i <= n} - mapa prostředí zk,i - pozorování/měření význačného bodu i v čase k
SLAM: algoritmus 1. Time-update - odhad pohybu robota na zákl. řídícího vstupu a předchozí polohy - f popisuje kinematiku robota 2. Measurement-update
- aktualizace pozice robota a mapy na základě pozorování, odhadu pozice robota a mapy - h popisuje geometrii měření
SLAM ● nepřesnosti měření --> nutnost použít pravděpodobnostní model (tzv. Probabilistic SLAM) ● např. extended Kalman filter (EKF-SLAM), RaoBlackwellised particle filter (FastSLAM), Iterated Closest Points (ICP-SLAM) Aktuální témata ● mapování rozsáhlých/venkovních prostředí ● dynamická prostředí
Reference ●
Simultaneous Localisation and Mapping (SLAM): Part I The Essential Algorithms, Part II State of the Art, H. Durrant-Whyte and T. Bailey, 2006.
● ●
The Mobile Robot Programming Toolkit, www.mrpt.org. http://www.youtube.com/watch?v=IQbGURQu9g4&t=1m38s
Rekonstrukce 3D scény
Motivace ● ● ● ● ● ●
Filmový průmysl Hry Virtuální světy Robotické systémy Rozpoznáváni obličejů Zachování kulturního dědictví
3D rekonstrukce ● Vstup ○ 2 až n (stovky) různých pohledů
● Výstup ○ point cloud ○ polygonální model
● Různe metody ○ ○ ○ ○
materiál osvětlení (ne)známa pozice kamery textury
Přístupy Získaní modelu pomocí ● siluet ● korespondence barvy/textury ● osvětlení ● strukturálního světla ● kombinace technik
Postup zpracování ● Vstupní obrázky ○ video, kontrolované podmínky (pozice, světlo)
● Pozice kamery ○ zjištění/zpřesnění
● 3D rekonstrukce
Structure from motion ● Detekce význačných bodů ○ SURF, SIFT, Harris
● Korespondence bodů ○ RANSAC
● 3D rekonstrukce
Triangulace ● Výpočet 3D pozice z korespondujícich bodů/patchů
Aktuální témata ● objekty s lesklým povrchem (mramor, kov) ● automatizace rekonstrukce ● 3D rekonstrukce z libovolně se pohybující kamery ● průhledné objekty ● přesnost a "smyčky" ● zjištění povrchu (kde jsou plochy?) ● odstranění nejednoznačností
Reference ●
A Comparison and Evaluation of Multi-View Stereo Reconstruction Algorithms, Steven M. Seitz, Richard Szeliski et. al. (CVPR 2006)
●
A Survey of Methods for Volumetric Scene Reconstruction, Greg Slabaugh et. al. (VG 2001) : Volume Graphics
●
Modelling Dynamic Scenes by Registering Multi-View Image Sequences, J-P. Pons, R. Keriven and O. Faugeras (CVPR 2005)
●
Multi-view stereo via Volumetric Graph-cuts, G. Vogiatzis, P.H.S. Torr and R. Cipolla (CVPR 2005)
●
Accurate and Scalable Surface Representation and Reconstruction from Images, Gang Zeng, Sylvain Paris, Long Quan, and Francois Sillion, (PAMI)
