Užitočná je vo všetkých oblastiach počítačovej grafiky, pri 3D skenovaní či digitalizácii kultúrneho dedičstva.
Mladý slovenský vedec Marcel Makovník sa venuje nadvzorkovaniu mračien bodov. Zdroj: Marcel Makovník
Odborný asistent na Fakulte matematiky, fyziky a informatiky Univerzity Komenského v Bratislave Marcel Makovník sa vo svojej aktuálnej práci zaoberá metódami spracovania dát z 3D skenerov a ich vyhodnocovaním. V jeho odbore sa málokto vyzná, no napriek tomu má dnes široké využitie. Stretajú sa s ním najmä odborníci v oblasti počítačovej grafiky.
Na úvod, prosím, vysvetlite pojem mračná bodov. Čo to je? Na čo nám slúžia a v akých oblastiach ich využívame?
Pod mračnami bodov vo všeobecnosti rozumieme ľubovoľnú množinu bodov v trojrozmernom priestore. Ak jednotlivé body zobrazíme ako sféry s malým polomerom, výsledok naozaj pripomína oblak, preto sa udomácnil pojem mračno bodov.
Hoci mračná bodov vieme zostrojiť manuálne, zadaním súradníc jednotlivých bodov, rozmach ich spracovania spôsobil až príchod 3D skenerov, ktoré ich dokážu generovať. Mračná bodov sa využívajú ako reprezentácia objektov prakticky vo všetkých oblastiach počítačovej grafiky, kde je potrebné zobrazovať reálne objekty na obrazovke nejakého zariadenia. Jednou zo zaujímavých aplikácií je aj využitie v digitalizácii kultúrneho dedičstva, napríklad pri skenovaní muzeálnych exponátov, sôch a podobne.
Vo svojej práci sa venujete nadvzorkovaniu mračien bodov, čiže pridávate do mračien nové body, aby ste dosiahli požadovanú hustotu a pravidelnosť vzorkovania a zároveň zachovali geometrické detaily pôvodného objektu. Z akého dôvodu sa to robí? Vďaka vašej metóde dokážete zdokonaliť objekt do takej podoby, že ho nebude treba ešte dodatočne opracúvať? Budú vďaka nej skrátka dokonalejšie, minimalizujú sa tým chyby?
Potreba nadvzorkovania mračien bodov vznikla najmä z dôvodu, že 3D skener nie vždy vygeneruje mračno v dostatočnej kvalite. Môžu sa tam napríklad nachádzať oblasti, ktoré sú v porovnaní so zvyškom navzorkované riedko, alebo môže vzniknúť šum (jednotlivé body sú posunuté o malú vzdialenosť od povrchu skenovaného objektu) a podobne.
Nadvzorkovanie rieši práve problém nerovnomerného vzorkovania. Taktiež ho možno využiť na kompresiu mračien bodov, kde do pamäte uložíme objekt s malým počtom bodov a pri používaní ho nadvzorkujeme do používateľom požadovanej hustoty. Samotné odstraňovanie chýb (najmä redukcia šumu) sa vníma ako osobitná úloha, ktorá je však tiež predmetom môjho výskumu.
Vo svojom výskume sa zaoberáte spracovaním geometrických dát s využitím nelineárnych metód. Vysvetlite, prosím, o aké metódy ide. Čo si pod tým môžeme predstaviť?
Medzi nelineárne metódy patria také, ktoré využívajú optimalizáciu účelových funkcií. Tie zvyčajne merajú chybu, ktorá opisuje nejakú, v našom prípade geometrickú, vlastnosť vstupných dát.
Minimalizovaním teda získame takú funkciu, ktorej chyba je pre konkrétne vstupné dáta najmenšia. Vo svojej práci využívam myšlienku, že pre vybranú malú podmnožinu bodov a k nim asociovaných normálových vektorov hľadám takú kvadratickú plochu, ktorá je k nim najbližšie. To znamená, že mnou používaná účelová funkcia meria špeciálnu vzdialenosť bodov a normálových vektorov od tejto kvadratickej plochy.
Venujete sa aj zjemňovaniu pletív. Rozumiem tomu správne, že vďaka mračnu bodov dokážete vyhladiť i určitý povrch? Na akých povrchoch ste vašu metódu testovali?
Myšlienka nelineárnych metód pochádza práve z problematiky zjemňovania mnohouholníkových pletív, v rámci ktorej sa výskum realizuje od sedemdesiatych rokov minulého storočia. Mnohouholníkové pletivo je po častiach lineárna plocha, čiže ho chápeme ako súbor vrcholov, hrán a stien. Ak sa naň pozrieme ako na typ geometrických dát, ide v podstate o mračno bodov s doplňujúcou informáciou, akým spôsobom sú jednotlivé body „pospájané“, čiže ktorými bodmi sú tvorené jednotlivé hrany a steny pletiva.
Zjemnenie je teda ekvivalentná úloha nadvzorkovania, len s tým rozdielom, že pracujeme s mnohouholníkovým pletivom. Jeho myšlienka je vytvoriť pletivo s väčším počtom vrcholov, čo sa dosiahne tým, že každú stenu „podrozdelíme”, teda rozdelíme na viac stien. A práve tu prichádza rozdelenie týchto metód na lineárne a nelineárne.
Lineárne metódy určujú súradnice nových vrcholov ako lineárne kombinácie pôvodných. To znamená, že nové súradnice vypočítame ako súčet ováhovaných pôvodných súradníc. Hoci je tento prístup výpočtovo veľmi efektívny a sú podrobne preskúmané vlastnosti takto zjemnených pletív, nie vždy dobre zachováva geometrické detaily objektu. Má tendenciu ho „vyhladzovať“ aj tam, kde to nie je želané. To podporilo vznik nelineárnych metód, ktorým sa vo svojom výskume venujem aj ja.
Ako hľadáte kvadratickú plochu pre daný objekt? (Predpokladám, že to závisí od komplikovanosti hrán objektu a celkovo jeho zložitosti – vzorec pre knihu nájdete ľahšie ako pre sochu.) Alebo pracujete len s určitými typmi objektov?
Cieľom je zostrojiť takú metódu, ktorá dokáže korektne spracovať čo najrozmanitejšie typy vstupných dát. Práve preto aj spomenuté zjemnenie (nadvzorkovanie) spracúva objekt lokálne, čiže vždy sa vyberie malá podmnožina (stačí nám 9 bodov), a nové body sa dopĺňajú z aproximujúcej kvadriky v rámci nej. To nám umožní, že vieme efektívne zjemniť aj jednoduché objekty ako torus či sféra, ale tiež objekty s komplikovanými detailmi, ako je napríklad socha.
Domnievam sa, že pracujete v na to určených programoch. Využívate na prácu softvéry, ktoré sa dajú bežne zakúpiť, alebo nejaké špeciálne programy, ktoré ste si sami vytvorili? Ak využívate komerčné programy, máte k nim vlastné pluginy? Alebo ako to funguje?
Na prácu používam vývojárske prostredie na tvorbu C++ aplikácií, ktoré sa bežne využíva v komerčnej aj v akademickej sfére. Na prácu s pletivami a mračnami bodov využívam voľne dostupné knižnice, v ktorých sú implementované základné operácie, napríklad hľadanie najbližšieho suseda. Vďaka tomu sa môžem sústrediť priamo na implementáciu svojich myšlienok a postupov bez toho, aby som musel ošetrovať základné úkony.
Koľko také nadvzorkovanie mračna trvá, ak chceme počet bodov v mračne navýšiť z dajme tomu tisíc na štvornásobok? Predstavujem si to tak, že zadáte vypočítaný vzorec do programu a ten nadvzorkuje objekt behom niekoľkých sekúnd. Alebo to trvá dlhšie?
Čas potrebný na nadvzorkovanie je závislý jednak od veľkosti vstupu, ale aj požadovanej veľkosti výstupu. Vami uvedený príklad, kde sa mračno s 1000 bodmi zväčší na štvornásobok, trvá niekoľko stoviek milisekúnd. Pri šestnásťnásobnom nadvzorkovaní ide už o sekundy.
Aká náročná je táto operácia pre počítač? Zvládne to aj bežne dostupný počítač alebo napríklad mobilný telefón či na takéto úkony potrebujete extra výkonný procesor?
Metódu, na ktorej som pracoval s p. doc. Chalmovianským a publikovali sme ju pod názvom PU-QF (Pointcloud Upsampling via Quadric Fitting), je možné spustiť aj na bežnom počítači. To znamená, že by sa mala dať spustiť tiež v mobilnom telefóne – pre ten to však implementované zatiaľ nemám.
Časy, ktoré som uviedol v predošlej otázke, boli dosiahnuté na bežnom „hráčskom“ laptope, ktorý má o čosi lepšie hardvérové vybavenie ako bežný „kancelársky“ počítač.
Keď máte objekt hotový, rekonštruujete ho pomocou algoritmu do reálnej podoby. Tá potom mieri rovno do 3D tlače alebo treba ešte pred vstupom do tlačiarne niečo zabezpečiť?
Predtým, ako môže ísť objekt do 3D tlače, je potrebné zabezpečiť, aby bol reprezentovaný vo forme mnohouholníkového pletiva, ktoré je aj typologicky korektné. Veľmi zjednodušene povedané, potrebujeme zabezpečiť okrem iného aj to, aby z pletiva „nevytekala voda“. Konverziu mračna bodov na mnohouholníkové pletivo vieme zabezpečiť niektorou z metód na rekonštrukciu plôch.
Obr. 1: (a) Vstupné mračno bodov s 1024 bodmi. (b) Mračno nadvzorkované na 4096 bodov použitím PU-QF. (c) Následná rekonštrukcia pomocou algoritmu Ball pivoting. Zdroj: Marcel Makovník
Akú minimálnu hustotu musia mať mračná bodov, aby z nich 3D tlačiareň dokázala zhotoviť objekt? Alebo na tom nezáleží a ide len o to, že čím viac bodov v mračne je, tým bude objekt dokonalejšie tvarovaný?
V zásade možno tvrdiť, že čím viac detailov má vytlačený objekt mať, tým musí mať aj hustejšie vzorkovanie. Avšak napríklad pre kocku nám stačí pletivo s ôsmimi vrcholmi a šiestimi stenami. Úroveň detailu teda závisí od požiadaviek používateľa a možno ju regulovať aj práve spomínanými metódami na nadvzorkovanie (zjemnenie).
V súčasnosti v téme mračien dominujú metódy založené na využití neurónových sietí. Prosím, priblížte, o aké metódy ide, ako vyzerá ich využitie v praxi.
Neurónové siete sú v prípade nadvzorkovania schopné generovať vizuálne veľmi pôsobivé výsledky, ktoré často kvalitatívne prevyšujú tie, ktoré sú získané štandardnými optimalizačnými (nelineárnymi) metódami. Postup možno zjednodušene (a aj nepresne) opísať nasledovne.
Zvolí sa kritérium v podobe chybových funkcií, ktoré má neurónová sieť optimalizovať. Potom je potrebný dataset. Ten obsahuje mračná bodov s hustým a dostatočne detailným vzorkovaním, ktoré slúžia ako referenčné mračná. Z referenčných mračien sa následne zostroja tréningové tak, že sa vyberie podmnožina s pevne stanoveným, ale menším počtom bodov. Vstup následne postupuje do neurónovej siete, kde sa nadvzorkuje, zohľadňujúc zvolené kritérium, a porovná sa chyba s referenčným pletivom. Pokiaľ je chyba väčšia ako zvolený prah, vstup sa opäť zjemní, ale pomocou kritéria s novými parametrami, ktoré sa získali v predošlom kroku.
Týmto spôsobom sa neurónová sieť dokáže natrénovať ako zjemňovať mračná bodov, aby bolo optimalizované zvolené kritérium. Preto pokiaľ do natrénovanej siete vložíme vstup, ktorý je podobný testovacím dátam, ale nenachádza sa v nich, dokážeme dostať kvalitný výstup.
Obr. 2: (a) Vstupné mračno bodov s 1024 bodmi a nepravidelným vzorkovaním. (b) Referenčné mračno bodov s 4096 bodmi a optimálnymi vzorkovaním (c) Mračno nadvzorkované na 4096 bodov použitím PU-QF. Hoci v niektorých častiach nebolo možné dosiahnuť optimálnu hustotu vzorkovania, naša metóda je schopná zreprodukovať dôležité geometrické detaily. Zdroj: Marcel Makovník
Prečo je podľa vás dôležité pracovať na metódach využívajúcich štandardné matematické prístupy, keď máme už naporúdzi iné efektívne spôsoby, ako mračno bodov vytvoriť?
Nevýhodou neurónových sietí je najmä dlhá doba trénovania (pokojne aj niekoľko dní vkuse). Hoci na nadvzorkovanie možno použiť vopred natrénovanú sieť, stále pretrváva problém, že pre vstup, ktorý je príliš odlišný od tréningových dát, nedostaneme vo všeobecnosti uspokojivý výstup. Okrem toho sa v mnohých oblastiach (napríklad pri spracovaní medicínskych dát) vyžadujú metódy, ktorých fungovanie a korektnosť je možné matematicky overiť, čo sa pri neurónových sieťach zatiaľ nepodarilo.
Je vaším cieľom pokračovať s projektom aj v komerčnej sfére? Budú si od vás môcť záujemcovia zakupovať softvér, ktorý im nadvzorkuje mračno bodov alebo vyhladí určitý povrch? Budete na to školiť ľudí či ako plánujete váš výskum uplatniť v praxi?
Mojím cieľom je poskytnúť výsledky mojej práce širokej verejnosti bez komerčných ambícií. K čím širšej palete používateľov a odborníkov sa dostanú, tým väčšia je šanca na získanie pripomienok a podnetov pre ďalší výskum a o to reálnejšie je ďalšie napredovanie v oblasti spracovania geometrických dát, špeciálne mračien bodov.
