Kam smeruje budúcnosť priemyslu a vizuálnych systémov? (2), Prehľadové články, Rubriky,

Reprezentácia 3D prostredia

Človek na základe zrakového vnemu dokáže rozpoznať predmety a dokáže hrubo odhadnúť ich vzdialenosť. Ľudský organizmus je veľmi zložitý systém, ktorý dokáže veľmi rýchlo vnímať prostredie a reagovať na zmeny v ňom. Vedci sa snažia priblížiť vlastnosti 3D vizuálnych systémov na úroveň ľudského oka. Avšak v súčasnosti sa žiadna kamera nedokáže vyrovnať ľudskému oku. Na trhu sa neustále objavujú čoraz kvalitnejšie senzory.

Vnímať priestor okolo nás znamená prijať obrovské množstvo dát, ktoré treba rýchlo a efektívne spracovať. Preto existujú rôzne spôsoby reprezentácie prostredia a každá je vhodná pre iné aplikácie a algoritmy.

Reálny povrch, ktorý dokáže 3D kamera zachytiť a snímať, je reprezentovaný množinou bodov, ktoré sa nazývajú mračno bodov (V ang. point cloud). Každému bodu prislúcha súradnica vzhľadom na začiatočný súradnicový systém kamery.

Platí, že čím vyššie rozlíšenie kamery, tým väčšia hustota bodov a zároveň tým viac dát na spracovanie. Práca s veľkým množstvom dát je zložitá na výpočet, a preto je často potrebná transformácia do inej reprezentácie. Medzi najčastejšie používané patria mriežková alebo geometrická reprezentácia.

Mriežková reprezentácia

Prostredie je reprezentované mriežkovou mapou, ktorá je tvorená bunkami nesúcimi informáciu o ich obsadenosti. Veľkou výhodou je možnosť ľahko uložiť informáciu o obsadenom, voľnom a neznámom prostredí. Najprimitívnejšia reprezentácia je mapa, ktorej bunky majú pevne určenú veľkosť. Pri viacrozmerných alebo rozsiahlych mapách nie je takáto reprezentácia príliš efektívna. V prípade požiadavky na lepšiu presnosť sa vyžaduje malá veľkosť buniek, čo predstavuje veľký objem dát a vysokú výpočtovú náročnosť. Naopak ak sú bunky príliš veľké, dochádza k nepresnosti mapy a k chybe diskretizácie.

Efektívnejším prístupom sú stromové reprezentácie využívajúce premenlivú veľkosť buniek. V 2D zobrazení sa označujú ako kvadrantové stromy (z ang. Quadtree) ilustrované na obr. 3. Algoritmus vychádza zo štvorca s veľkosťou celej mapy, ktorý sa označuje ako hlavný uzol alebo koreň stromu. Ak obsahuje súčasne voľný priestor a objekt, tak sa štvorec rozdeľuje práve na štyri menšie štvorce (potomkov). Delenie buniek pokračuje rekurzívne, až kým uzol nebude obsahovať iba voľný alebo obsadený priestor alebo kým sa nedosiahne požadovaná presnosť. Analógiou kvadrantových stromov v 3D priestore sú oktálové stromy (z ang. Octree) [2].

Geometrická reprezentácia

Geometrická reprezentácia prostredia presne opisuje objekty v spojitom priestore na základe matematických rovníc. Existuje široká škála prístupov a techník geometrického modelovania a výber vhodnej reprezentácie závisí od aplikácie a zložitosti problému. Geometrické modelovanie možno rozdeliť na objemové (Solid) a povrchové (Boundary) [4].

Objemové modelovanie sa často používa v softvéroch CAD a princíp konštruovania zložitých objektov pozostáva z aplikovania množinových operácií (prienik, zjednotenie, rozdiel) na primitívne objekty (kváder, guľa), ako je znázornené na obr. 7.

Povrchové modelovanie, nazývané aj polygónové, využíva znalosti z topológie a geometrie. Topológiou sa vyjadrujú jednotlivé prepojenia vrcholov (Vertex) objektu pomocou hrán (Edge). Geometria definuje pozíciu každého vrcholu v priestore. Prienikom hrán vzniká povrch a ten sa označuje ako strana (Face). Tieto pojmy sú ilustrované na obr. 5. Pri polygónovej reprezentácii sa v anglickej literatúre stretávame s pojmom Mesh.

Ak sú hrany a strany zaoblené, treba toto zaoblenie lineárne aproximovať. V počítačovej grafike sa najčastejšie využíva aproximácia zaoblenia povrchu na trojuholníkové strany, pretože povrch akéhokoľvek objektu sa dá vyjadriť pomocou trojuholníkov. Zvyšovaním počtu trojuholníkových strán sa dosahuje lepšia aproximácia [6].

Tvorba geometrickej reprezentácie prostredia

Ako bolo uvedené vyššie, v počítačovej grafike a programoch sa často používa polygonálny model aproximujúci reálne zobrazenie. Štandardný výstup z hĺbkového senzora predstavuje často len hĺbkový obraz alebo vypočítané mračno bodov, ktoré treba „preložiť“ do polygonálnej reprezentácie.

Tvorba modelu

Na vytvorenie modelu sa používa algoritmus s názvom Marching Cubes. Ide o grafický algoritmus prvýkrát publikovaný v roku 1987. Úlohou tohto algoritmu je získať polygonálnu mriežku z trojrozmerného diskrétneho skalárneho poľa bodov niekedy nazývaných voxely. Algoritmus vymysleli William E. Lorensen a Harvey E. Cline, kde hľadali spôsob, ako efektívne vizualizovať 3D dáta z CT a MRI zariadení. Algoritmus prechádza cez skalárne pole bodov a vždy berie osem susedných bodov, čím vytvára imaginárnu kocku. Následne určuje polygóny potrebné na reprezentáciu povrchu, ktorý prechádza touto kockou. Jednotlivé polygóny sa následne spájajú do požadovaného povrchu [7].

Tvorba komplexného modelu prostredia

Na dosiahnutie komplexného modelu prostredia často nestačí len možnosť snímania scény z jedného uhla, ale je potrebná fúzia viacerých snímok. Aby bola fúzia dát zo senzora možná, treba poznať jeho presnú polohu v priestore. Na základe znalosti polohy možno následne transformovať hĺbkové dáta, spájať ich a tak vytvárať ucelenú reprezentáciu scény.

Poloha senzora môže byť zaznamenaná jeho presnou kalibráciou na robotickom manipulátore alebo využitím algoritmov, ktoré dokážu sledovať relatívnu zmenu polohy senzora na základe nameraných hĺbkových dát. Na algoritmoch fúzie dát sa pracuje posledných 20 rokov, pričom najväčší úspech a prelom dosiahol algoritmus Kinect Fusion vytvorený v roku 2011 [8]. Algoritmus bol schopný sledovať pozíciu senzora a vytvárať model prostredia takmer v reálnom čase.

Od roku 2011 začalo následne vznikať množstvo verzií tohto algoritmu, ktoré sú optimalizované pre veľkorozmerné scény, dokážu pracovať s výpočtovým výkonom grafickej karty, filtrovať dynamické objekty a pod. V súčasnosti nás však pri dosahovaní dostatočnej presnosti a kvality snímaných objektov často limituje výpočtový výkon.

Zdroje

[1] Test-retest reliability of smile tasks using three-dimensional facial topography – Scientific Figure on ResearchGate. Citované 10. 9. 2020. Dostupné na: https://www.researchgate.net/figure/Example-of-the-point-cloud-of-the-face_fig1_322498282.

[2] Ayala, D. – Brunet, P. – Juan, R. – Navazo, I.: Object Representation by Means of Nonminimal Division Quadtrees and Octrees. In: ACM Transactions on Graphics, 1985, vol. 4, no. 1, pp. 41 – 59.

[3] Sortino, M. – Kuljanic, E. – Totis, G. – Cukor, G.: Simulation of Cutting Forces and Cutting Conditions in Complex Turning Operations. In: 12th International Scientific Conference on Production Engineering 2009.

[4] Lavalle, S. M.: Planning Algorithms. New York (Ny): Cambridge University Press, Cop, 2014, pp. 81 – 92.

[5] Zhou, Q.: Mesh Boolean — PyMesh 0.2.1 documentation. Readthedocs.io 2018. [online]. Citované 4. 1. 2020. Dostupné na: https://pymesh.readthedocs.io/en/latest/mesh_boolean.html.

[6] Botsch, M. – Pauly, M. – Rossl, C. – Bischoff, S. – Kobbelt, L.: Geometric Modeling based on Triangle Meshes. ACM SIGGRAPH 2006 Courses on – SIGGRAPH’06, 2006.

[7] Lorensen, W. E. – Cline, H. E.: Marching cubes: A high resolution 3d surface construction algorithm. ACM Computer Graphics 1987. s. 163 – 169. ISBN 0-89791-227-6.

[8] Newcombe, R. A. et al.: KinectFusion: Real-time dense surface mapping and tracking. In: 10th IEEE International Symposium on Mixed and Augmented Reality, Oct. 2011.

[9] Igelbrink, T. et al.: Online Mesh Optimization for Large Scale Kinect Fusion Meshes. In: IFAC-PapersOnLine, 2016, vol. 49, no. 15, pp. 126 – 131, 10.1016/j.ifacol.2016.07.720.