Rekonštrukcia viacrozmerných dát pomocou triangulácie

Grant UK

Charakteristika vedeckých cieľov projektu

Rekonštrukcia z diskrétnych dát je dôležitá a často vykonaná úloha v matematike ale aj v množstve iných vedných odborov (napr. počítačová grafika, fyzika, medicínska informa-tika, geológia, ekonómia, atď.). Vzhľadom na to, že rekonštrukcia je často len medzikrokom v postupe rôznych operácií a simulácií, je dôležité, aby bola vykonaná čo najkvalitnejšie. Zvyčajne sa však vyžaduje čo najpresnejšia rekonštrukcia významných čŕt, ktoré nesú dôležitú informáciu. V terminológii spracovaní obrazu to znamená vysokofrekvenčné oblasti, t.j. rekonštrukciu hrán; pri rekonštrukcii 3D medicínskych dát (napr. získané pomocou počítačovej tomografie alebo iným spôsobom) získanie vhodne rekonštruovaných izoplôch, atď. Z existujúcich rekonštrukčných techník sa zdá byť najvhodnejším prístupom pre tieto účely takzvaná dátovo závislá triangulácia.

V tomto projekte by som sa chcel zamerať na rozširovanie poznatkov o dátovo závislých trianguláciách v 2D a vo vyšších dimenziách. Základná myšlienka je založená na použití triangulácie ako základ rekonštrukčnej siete. Pomocou topologických zmien táto technika je schopná prispôsobiť trojuholníkovú sieť k významným črtám reprezentovaných v dátach a takto zvýšiť kvalitu rekonštrukcie. Hľadanie optimálnych algoritmov a vhodné nastavenie riadiacich parametrov, alebo voľba vhodnej cenovej funkcie poskytuje priestor pre dôležitý výskum.

Aplikačná oblasť dátovo závislých triangulácií je veľmi rozsiahla, napríklad rekonštrukcia digitálneho obrazu v 2D, rekonštrukcia medicínskych dát v 3D, rekonštrukcia v čase sa meniacich volumetrických dát v 4D, atď. Vhodným nastavením ju možné prispôsobiť ľubovoľnému rekonštrukčnému problému. Je nezávislá od rozmiestnenia funkčných hodnôt a môže slúžiť aj na vektorizáciu dát. Raz vytvorená triangulácia poskytuje základnú štrukturalizáciu dát, v ktorej môžeme získať neznámu funkčnú hodnotu ľubovolnou metódou interpolácie.

Návrh metódy riešenia projektu

Hlavným cieľom projektu je rozširovať poznatky o DDT vo vyšších dimenziách. Jednotlivé aplikačné oblasti vyžadujú mnoho testovania na zistenie vhodnej cenovej funkcie a optimalizačnej techniky. Na tento účel plánujem využiť poznatky z existujúcich 2D prístupov, ako aj hľadanie nových cenových funkcií a algoritmov. Úspešnosť metódy plánujem overiť na volumetrických dátach a porovnať s výsledkami konvolučných techník.

Triangulácie vo vyšších dimenziách majú odlišné vlastnosti ako v 2D, preto bude potrebné vykonať podrobný prieskum literatúry v tomto smere. Štúdium lokálnych topologických zmien triangulácii vo vyšších dimenziách je ďalšou dôležitou súčasťou výskumu. Voľbou lokálnych topologických operácií je tiež možné ovplyvňovať výsledok rekonštrukcie.

Sekundárnym cieľom projektu bude zistiť možnosti využitia DDT vo vyšších dimenziách na kompresiu dát. Priradenie cien k vrcholom triangulácie určuje významnosť jednotlivých vzoriek. Na základe tejto informácie môžeme odstrániť najmenej dôležité vzorky a vypočítať novú trianguláciu, čím získame kompresiu. Aplikačnou oblasťou môže byť napríklad kompresia medicínskych dát.

Vedecké výsledky súvisiace s grantom UK

Tóth Zs., Viola I., Ferko A., Gröller M. E.: N-dimensional Data-Dependent Reconstruction Using Topological Changes. In Topology-Based Methods in Visualization (preliminary title). Springer Mathematics & Visualization Series. Editors: Hagen H., Hauser H., Theisel H. 2007, pp. ???-???. (in print)

Abstract:
We introduce a new concept for a geometrically based feature preserving reconstruction technique of n-dimensional scattered data. Our goal is to generate an n-dimensional triangulation, which preserves the high frequency regions via local topology changes. It is the generalization of a 2D reconstruction approach based on data-dependent triangulation and Lawson‘s optimization procedure. The definition of the mathematic optimum of the reconstruction is given. We discuss an original cost function and a generalization of known functions for the n-dimensional case.

Tóth Zs. Triangulácie v rovine, teréne a priestore. Project of dissertation, Bratislava SR, 2006.

Abstrakt:
V tejto práci prezentujeme preh3/4ad geometricky založenej techniky, ktorá zachováva významné e`rty v dátach a je nazývaná dátovo závislá triangulácia. Sú tu predstavené dva nové deterministické prístupy, ktoré majú za úlohu posunú? túto metóodu bližšie k reálnemu použitiu. Ponúkame modifikáciu optimalizae`ného prístupu simulovaného žíhania v kombinácii s look-ahead prístupom. Hlavným prínosom je rozšírenie dátovo závislej techniky na rekonštrukciu n-dimenzionálnych dát. Naším cie3/4om je generovanie n-dimenzionálnej triangulácie, ktorá zachováva vysokofrekvene`né oblasti pomocou topolóogických zmien. Je to zovšeobecnenie 2D prístupu založeného na dátovo závislých trianguláciách a Lawsonovho optimalizae`ného procesu. Predstavíme novú cenovú funkciu a zovšeobecnenie existujúcich cenových funkcií n-dimenzií. Na záver uvedieme možnosti i"alšieho výskumu ako projekt dizertae`nej práce.

Technical report - coming soon.


Zsolt Toth 2002-2006(c)