Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Porovnání vyhlazovacích. objem

Za´padoˇceska´ univerzita v Plzni Fakulta aplikovany´ch vˇed Katedra informatiky a vy´poˇcetn´ı techniky

Bakal´ aˇ rsk´ a pr´ ace Porovn´ an´ı vyhlazovac´ıch pˇ r´ıstup˚ u zachov´ avaj´ıc´ıch objem

Plzeˇ n 2014

Jiˇr´ı Z´akouck´ y

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakal´ aˇrskou pr´aci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 26. ˇcervna 2014 Jiˇr´ı Z´akouck´ y

Abstract This work deals with approach to smooth 3D surface nets in the context of biomedical application. It looks into various reasons for the need of smoothing 3D surface models from biomedical devices. Afterwords it describes some basic smoothing methods and points out volume and feature preserving ones. The comparison is performed on the basis of the implementation of chosen methods according to various points of view. Finally the conclusion is formulated.

Abstrakt Tato pr´ ace pojedn´ av´ a o vyhlazovac´ıch pˇr´ıstupech na 3D povrchov´ ych s´ıt´ıch v kontextu biomedic´ınsk´ ych aplikac´ı. Zab´ yv´a se r˚ uzn´ ymi pˇr´ıˇcinami potˇreby vyhlazov´an´ı 3D povrchov´ ych model˚ u z biomedic´ınsk´ ych zaˇr´ızen´ı. D´ale popisuje nˇekter´e z´akladn´ı obecn´e vyhlazovac´ı metody a vyzved´ av´a ty, kter´e zachov´avaj´ı objem a charakteristick´e rysy objektu (volume a feature preserving). Na z´akladˇe implementace vybran´ ych metod je provedeno srovn´ an´ı podle r˚ uzn´ ych hledisek a formulov´any z´avˇery.

Obsah ´ 1 Uvod 2 3D 2.1 2.2 2.3

modelov´ an´ı v biomedic´ınsk´ em F´ aze skenov´ an´ı . . . . . . . . . . F´ aze segmentace . . . . . . . . . F´ aze extrakce povrchov´e s´ıtˇe . .

1 kontextu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Vybran´ e z´ akladn´ı vyhlazovac´ı techniky a pˇ r´ıstupy 3.1 Iteraˇcn´ı vyhlazovac´ı techniky . . . . . . . . . . . . . 3.1.1 Laplaci´ ansk´e vyhlazov´an´ı – z´akladn´ı varianta 3.1.2 Laplaci´ ansk´e vyhlazov´an´ı – v´aˇzen´e varianty . 3.1.3 Bilater´ aln´ı vyhlazov´an´ı . . . . . . . . . . . . . 3.1.4 Norm´ alov´e vyhlazov´an´ı . . . . . . . . . . . . 3.1.5 Sign´ alov´ y pˇr´ıstup k vyhlazov´an´ı . . . . . . . 3.2 Neiteraˇcn´ı vyhlazovac´ı techniky . . . . . . . . . . . . 3.2.1 Bilater´ aln´ı vyhlazov´an´ı - neiteraˇcn´ı verze . . 3.2.2 Glob´ aln´ı laplaci´ ansk´e vyhlazov´an´ı (GLS) . . 3.2.3 Vyhlazov´ an´ı zjemˇ nov´an´ım povrchov´e s´ıtˇe . .

2 3 4 4

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

5 6 6 7 8 10 11 14 14 16 18

4 Doplˇ nkov´ e techniky pro zachov´ an´ı objemu 4.1 Inflataˇcn´ı metoda . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Single-point relaxaˇcn´ı metoda . . . . . . . . . . . . . . . . . . . 4.3 Single-edge relaxaˇcn´ı metoda . . . . . . . . . . . . . . . . . . . 4.4 Objemov´e omezen´ı minimalizaˇcn´ıch rovnic u glob´aln´ıch technik

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

18 19 19 19 20

5 Zp˚ usob porovn´ av´ an´ı vybran´ ych vyhlazovac´ıch 5.1 Volba referenˇcn´ıch 3D model˚ u. . . . . . . . . . 5.2 Hodnot´ıc´ı krit´eria pro porovn´av´an´ı . . . . . . . 5.2.1 Vizu´ aln´ı hodnocen´ı . . . . . . . . . . . . 5.2.2 Metrika zmˇeny celkov´eho objemu tˇelesa 5.2.3 L2 chybov´ a norma . . . . . . . . . . . . 2 5.2.4 L norm´ alov´ a chybov´a norma . . . . . . 5.2.5 Hodnota zakˇriven´ı . . . . . . . . . . . . 5.2.6 Kvalita troj´ uheln´ık˚ u . . . . . . . . . . . 5.2.7 V´ ypoˇcetn´ı ˇcas . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

metod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

20 20 21 21 22 22 23 23 24 25

6 Implementace s vyuˇ zit´ım VTK 6.1 VTK - The Visualization Toolkit . . . . . . . . . . . . . . . . . . . . 6.2 Z´ akladn´ı vizualizaˇcn´ı roura . . . . . . . . . . . . . . . . . . . . . . . 6.3 Implementace jednotliv´ ych hodnot´ıc´ıch metrik a vyhlazovac´ıch filtr˚ u 6.3.1 Metrika zmˇeny celkov´eho objemu tˇelesa . . . . . . . . . . . . 6.3.2 L2 chybov´ a norma . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 L2 norm´ alov´ a chybov´a norma . . . . . . . . . . . . . . . . . . 6.3.4 Metrika zakˇriven´ı . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.5 Kvalita troj´ uheln´ık˚ u . . . . . . . . . . . . . . . . . . . . . . . 6.3.6 V´ ypoˇcetn´ı ˇcas . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.7 Vyhlazovac´ı filtry . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

25 26 26 27 27 27 28 28 28 28 28

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

7 Vyhodnocen´ı jednotliv´ ych technik 29 7.1 Vyhodnocen´ı - Laplaci´ ansk´e vyhlazov´an´ı s uniformn´ımi vahami . . . . . . . 30 7.2 Vyhodnocen´ı - Implicit fairing . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7.3 7.4

Vyhodnocen´ı - Taubin FIR filter . . . . . . . . . . . . . . . . . . . . . . . . 33 Shrnut´ı vz´ ajemn´eho porovn´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . 34

8 Z´ avˇ er

39

1

´ Uvod

3D modelov´ an´ı je jiˇz bˇeˇznou discipl´ınou oboru poˇc´ıtaˇcov´e grafiky, jej´ıˇz v´ ysledky se v´ yznamnˇe prom´ıtaj´ı do vˇsedn´ı aplikaˇcn´ı praxe napˇr´ıˇc mnoha obory lidsk´e ˇcinnost´ı. Je vyuˇz´ıv´ ano napˇr. pro vizualizaci nejr˚ uznˇejˇs´ıch prostorov´ ych dat, pro konstruov´ an´ı stroj´ırensk´ ych produkt˚ u (CAD) ˇci obecnˇe pr˚ umyslov´ y design, simulov´an´ı vˇedeck´ ych pokus˚ u ˇci k prost´e z´ abavˇe ve formˇe poˇc´ıtaˇcov´ ych her atd. Jedn´ım z obor˚ u, ve kter´ ych nach´az´ı 3D modelov´ an´ı sv´e opodstatnˇen´ı je i medic´ına ˇci biomechanika, kde 3D modelov´ an´ı m˚ uˇze b´ yt v´ yznamn´ ym diagnostick´ ym n´astrojem, jenˇz pˇrin´aˇs´ı urˇcit´e v´ yhody, ale i u ´skal´ı oproti klasick´ ym 2D zobrazovac´ım metod´am. Pˇr´ıstup˚ u k reprezentace objekt˚ u v poˇc´ıtaˇci existuje nˇekolik, napˇr. reprezentace objemov´ a, kdy objekt nen´ı pops´ an geometricky, ale pouze jako sada vzork˚ u z dan´ ych um´ıstˇen´ı v objektu. Patrnˇe nejrozˇs´ıˇrenˇejˇs´ı reprezentac´ı objekt˚ u v poˇc´ıtaˇci je vˇsak reprezentace hraniˇcn´ı, kdy objekt b´ yv´ a pops´an geometricky jeho povrchem. Jelikoˇz je hraniˇcn´ı reprezentace v praxi nejˇcastˇeji pouˇz´ıvanou a jelikoˇz pro pˇrevod z objemov´e reprezentace jsou vyvinuty pˇr´ısluˇsn´e algoritmy, je tato pr´ace zamˇeˇrena pr´avˇe na objekty reprezentovan´e pomoc´ı tzv. povrchov´e s´ıtˇe (mesh). Ve skuteˇcn´em re´ aln´em svˇetˇe b´ yvaj´ı povrchy pˇredmˇet˚ u tvoˇreny nejr˚ uznˇeji zakˇriven´ ymi plochami, kter´e vˇsak pro poˇc´ıtaˇcov´e zpracov´an´ı ˇci vizualizaci neb´ yvaj´ı vhodn´e a ˇcasto ani d˚ uslednˇe technicky ˇreˇsiteln´e zejm´ena ve vztahu k dostupn´emu hardwaru. V praxi pak b´ yvaj´ı tyto zakˇriven´e plochy nahrazov´any mnoˇzinou jednotliv´ ych spojit´ ych ploˇsek. Tyto ploˇsky b´ yvaj´ı nejˇcastˇeji troj´ uheln´ıkov´e, a to vzhledem k jejich podpoˇre a optimalizaci jejich zobrazov´ an´ı ze strany hardwaru. Z podstaty tohoto zjednoduˇsen´ı popisu skuteˇcn´eho povrchu objektu pomoc´ı jednotliv´ ych ploˇsek (troj´ uheln´ık˚ u) vypl´ yvaj´ı neˇz´adouc´ı efekty, a to mj. hranat´ y vzhled“ nam´ısto ” plynul´eho, zkreslen´ı, zmˇena objemu tˇelesa ˇci obsahu povrchu. Mnoho dalˇs´ıch neˇz´adouc´ıch efekt˚ u m˚ uˇze d´ ale plynout i ze samotn´e troj´ uheln´ıkov´e s´ıtˇe, resp. z jej´ı kvality, kter´a je ovlivnˇena jak zdrojov´ ymi daty, kter´e mohou b´ yt ovlivnˇeny napˇr. ˇsumem, komplikovanost´ı tvaru objektu, tak pouˇzit´ ym algoritmem pˇri tvorbˇe s´ıtˇe. Vˇsechny tyto vlivy pak vyvol´avaj´ı potˇrebu, aby z´ıskan´ a troj´ uheln´ıkov´a s´ıt’ byla nˇejak´ ym zp˚ usobem optimalizov´ana ˇci vyhlazena, odstranˇeny neˇz´ adouc´ı efekty, a pˇritom aby byly zachov´any urˇcit´e vlastnosti objektu, jako napˇr. zachov´ an jeho objem, zachov´any specifick´e rysy (napˇr. v´ yrazn´e hrany) ˇci prostorov´e vztahy. Pro tyto potˇreby byla vyvinuta ˇrada algoritm˚ u, jejichˇz porovn´ an´ı (nˇekter´ ych z nich) je hlavn´ım u ´kolem t´eto pr´ace, zejm´ena ve vztahu k biomedic´ınsk´ ym aplikac´ım. V prvn´ı ˇc´ asti pr´ ace bude proto nast´ınˇena problematika 3D modelov´an´ı biomedic´ınsk´ ym dat a nˇekter´ a jejich specifika. D´ ale bude ve struˇcnosti uveden pˇrehled a popis vybran´ ych metod ˇci pˇr´ıstup˚ u k vyhlazov´ an´ı troj´ uheln´ıkov´ ych s´ıt´ı. Pro n´asledn´e porovn´an´ı nˇekter´ ych tˇechto ˇreˇsen´ı bude nutn´e navrhnout vyhodnocovac´ı apar´at ve formˇe krit´eri´ı, a to jak vizu´aln´ıch, tak i kvantifikovateln´ ych, kter´ ym je pak moˇzn´e zhodnotit v´ ysledek vyhlazov´an´ı, zejm´ena pak s ohledem na dosahovanou chybu zachov´an´ı objemu, hladkost v´ ysledn´e s´ıtˇe, tvar troj´ uheln´ık˚ u atd. Pro tato vyhodnocen´ı bude navrhnut software vyuˇz´ıvaj´ıc´ı open-source vizualizaˇcn´ı n´ astroj VTK (The Visualization Toolkit), kter´ y zaintegrov´av´a jednotliv´e metody a vyhodnocovac´ı krit´eria. Vyhodnocen´ı pak bude provedeno na vybran´ ych re´aln´ ych biomedic´ınsk´ ych datech, ale i na umˇele vygenerovan´ ych objektech typu koule ˇci krychle s pˇr´ıpadn´ ym umˇele vyvolan´ ym ˇsumem.

1

2

3D modelov´ an´ı v biomedic´ınsk´ em kontextu

Se vzr˚ ustaj´ıc´ı kvalitou vstupn´ıch dat z l´ekaˇrsk´ ych tomografick´ ych pˇr´ıstroj˚ u jako napˇr. magnetick´ a rezonance (MRI) ˇci poˇc´ıtaˇcov´a tomografie (CT) vzr˚ ust´a i popt´avka po jejich zpracov´ av´ an´ı a vizualizace jako trojrozmˇern´e modely. V´ ystupn´ı data z tˇechto pˇr´ıstroj˚ u pˇredstavuj´ı ekvidistantn´ı sekvenci sn´ımkov´ ych ˇrez˚ u pˇr´ısluˇsn´e oblasti lidsk´eho tˇela, ze kter´eho pak lze sestavit pˇr´ısluˇsn´ y 3D model, kter´ y m˚ uˇze slouˇzit zpravidla pro: • diagnostiku onemocnˇen´ı • pl´ anov´ an´ı operaˇcn´ıch z´ akrok˚ u • v´ yukovou a v´ yzkumnou ˇcinnost, atd. V l´ekaˇrstv´ı hraje spr´ avn´ a diagnostika ˇci spr´avnost rozhodnut´ı napˇr. chirurgick´em postupu velice v´ yznamnou roli na v´ ysledn´ y dopad na zdrav´ı pacienta a jeho n´aslednou kvalitu ˇzivota. Pro rozhodov´ an´ı obecnˇe je vˇzdy velice d˚ uleˇzit´a u ´plnost a kvalita relevantn´ıch podklad˚ u, kter´e mohou na rozhodnut´ı m´ıt vliv. V´ ystupy z MRI, CT ˇci jin´ ych zobrazovac´ıch pˇr´ıstroj˚ u jsou v tomto smˇeru velmi d˚ uleˇzitou souˇc´ast´ı dneˇsn´ı medic´ıny, na jejichˇz z´akladˇe jsou ˇcinˇena d˚ uleˇzit´ a l´ekaˇrsk´ a rozhodnut´ı. Jejich v´ ysledn´a kvalita je proto kl´ıˇcov´ ym faktorem. V medic´ınsk´em kontextu proto z´akladn´ımi poˇzadavky jsou: • vysok´ a pˇresnost • zachov´ an´ı objemu a proporc´ı • zachov´ an´ı prostorov´ ych vztah˚ u a z´avislost´ı atd. Vysok´ a pˇresnost je spojena s faktem, ˇze i nˇekter´e velmi mal´e patologick´e anom´alie mohou b´ yt z´asadn´ı pro celkovou diagnostiku, jako napˇr. mal´e n´adory apod. Rovnˇeˇz tak i zachov´ an´ı objemu, nebot’ i zmˇenˇen´ y objem skuteˇcn´eho org´anu m˚ uˇze b´ yt indik´atorem poruchy ˇci onemocnˇen´ı. Zachov´ an´ı prostorov´ ych vztah˚ u a z´avislost´ı je nav´ıc d˚ uleˇzit´e napˇr´ıklad pro pl´anov´ an´ı chirurgick´ ych z´ akrok˚ u, kdy jednotliv´e org´any nejsou posuzov´any samostatnˇe, ale je posuzov´ ana cel´ a vyˇsetˇrovan´a oblast atd. V´ yrazn´ ym specifikem modelov´ an´ı biomedic´ınsk´ ych dat je fakt, ˇze ˇc´asti lidsk´eho tˇela, kter´e b´ yvaj´ı v z´ ajmu l´ekaˇr˚ u, jsou m´ alokdy sloˇzen´e z pˇr´ım´ ych, pravo´ uhl´ ych ˇci jinak pravideln´ ych geometrick´ ych tvar˚ u (jak tomu b´ yv´a napˇr´ıklad u 3D model˚ u z produkce CAD syst´em˚ u v aplikac´ıch pr˚ umyslov´eho designu), ale jejich tvary b´ yvaj´ı nepravideln´e, organick´e. Na cestˇe od skuteˇcn´e ˇc´ asti lidsk´eho tˇela aˇz po jeho 3D model existuje mnoho potenci´aln´ıch negativn´ıch vliv˚ u, kter´e mohou zapˇr´ıˇcinit v´ yznamn´e rozd´ıly mezi skuteˇcnost´ı a modelem. Zjednoduˇsen´ y pohled na proces, jak´ ym je skuteˇcnost transformov´ana aˇz do podoby 3D modelu ve formˇe troj´ uheln´ıkov´e s´ıtˇe, je zn´azornˇen na Obr´azku 1. Prakticky v kaˇzd´e f´ azi z´ısk´ an´ı 3D modelu mohou vznikat vznikat neˇz´adouc´ı jevy, jako napˇr. chybˇej´ıc´ı ˇc´ asti, pˇridan´e faleˇsn´e ˇc´asti, schodovitost s´ıtˇe, terasovitost, d´ıry atd. Vzhledem k tomuto faktu jsou v jednotliv´ ych f´az´ıch aplikov´any r˚ uzn´e techniky, kter´e maj´ı vznikl´e nepˇr´ızniv´e jevy eliminovat nebo alespoˇ n potlaˇcit (ˇzlut´e ˇc´asti Obr´azku 1). Techniky jednotliv´ ych u ´prav ale mohou m´ıt sv´a u ´skal´ı, nebot’ odstranˇen´ım jednoho neˇz´adouc´ıho jevu mohou zp˚ usobit neˇz´ adouc´ı jev jin´ y, nebo pˇri ˇspatn´em pouˇzit´ı tˇechto technik m˚ uˇze dokonce doj´ıt nam´ısto potlaˇcen´ı naopak ke zv´ yraznˇen´ı neˇz´adouc´ıho jevu. To vˇse je nav´ıc ovlivnˇeno i pˇr´ısluˇsnou f´ az´ı zpracov´an´ı, nebot’ neˇz´adouc´ı jevy, kter´e vznikly v poˇc´ateˇcn´ıch f´az´ıch procesu, pˇrech´ azej´ı i do f´ az´ı n´asleduj´ıc´ıch, kde m˚ uˇze b´ yt jejich dalˇs´ım zpracov´an´ım negativn´ı efekt d´ ale multiplikov´ an. 2

Příprava na skenování

Reálný objekt (pacient)

Úprava segmentovaných dat

Úprava raw dat

skenování

Raw data (snímkové řezy)

segmentace

extrakce Segmentovaná objemová data povrchové sítě

Úprava povrchové sítě

Povrchová síť

Obr´ azek 1: Proces vytvoˇren´ı 3D modelu

Jelikoˇz jedn´ım z c´ıl˚ u technik u ´prav p˚ uvodn´ıch dat v jednotliv´ ych f´az´ıch zpracov´an´ı (mezi nˇeˇz patˇr´ı i vyhlazov´ an´ı, viz f´ aze Povrchov´a s´ıt’“ v Obr´azku 1) je eliminace tˇechto ” neˇz´adouc´ıch jev˚ u, je d˚ uleˇzit´ a i anal´ yza pˇr´ıˇcin jejich vzniku, resp. charakter tˇechto jev˚ u. Pˇri porovn´ an´ı vyhlazovac´ıch algoritm˚ u pak m˚ uˇze b´ yt kladen d˚ uraz pr´avˇe na specificky identifikovan´e negativn´ı jevy. Tuto problematiku zmiˇ nuj´ı ve sv´em porovn´an´ı podrobnˇeji napˇr. [BHP06], kteˇr´ı rozeb´ıraj´ı zdroje jednotliv´ ych neˇz´adouc´ıch artefakt˚ u vzhledem k f´ azi skenov´ an´ı, segmentace a extrakce s´ıtˇe, a jejichˇz z´avˇery jsou ve struˇcnosti rozebr´any v n´asleduj´ıc´ıch podkapitol´ ach.

2.1

F´ aze skenov´ an´ı

F´aze skenov´ an´ı z´ avis´ı na zvolen´e technice sn´ımkov´an´ı, napˇr. ˇcasto pouˇz´ıvan´ ymi jsou CT ˇci MRI, ale i jin´e druhy tomografie (PET, SPECT...). Tyto techniky vytv´aˇrej´ı sadu ekvidistantn´ıch obrazov´ ych ˇrez˚ u. Velkou roli na u ´roveˇ n podrobnosti m´a pak rozliˇsen´ı z´ıskan´ ych dat. Technika ˇrez˚ u vˇsak zp˚ usobuje, ˇze vzd´alenost jednotliv´ ych ˇrez˚ u (tzn. rozliˇsen´ı v ose z) je obecnˇe vˇetˇs´ı, neˇz vzd´alenosti jednotliv´ ych vzork˚ u uvnitˇr jednoho ˇrezu (tzn. rozliˇsen´ı v os´ ach x a y), a tud´ıˇz pro u ´ˇcely modelov´an´ı je m´enˇe informac´ı pod´el osy z. [BHP06] uv´ ad´ı pˇr´ıklad bˇeˇzn´eho rozliˇsen´ı z´ıskan´ ych dat cca od 128x128x64 do 512x512x400. CT je z´ astupce radiologick´ ych technik, kdy okolo pacienta ob´ıh´a zdroj rentgenov´eho z´aˇren´ı, kter´e proch´ az´ı pacientem. Pr˚ uchodnost paprsku jednotliv´ ymi druhy tk´an´ı je rozd´ıln´a a jej´ı intenzita je pak n´ aslednˇe zmˇeˇrena na detektorech. Z detektor˚ u je n´aslednˇe z´ısk´av´an sign´ al, kter´ y je pˇrevzorkov´ an do hodnot vhodn´ ych pro zpracov´an´ı. Limituj´ıc´ım faktorem tohoto zp˚ usobu vyˇsetˇren´ı je ˇskodlivost rentgenov´eho z´aˇren´ı, kter´emu je pacient vystaven, a to i v d´avk´ ach vˇetˇs´ıch neˇz pˇri bˇeˇzn´em rentgenov´em vyˇsetˇren´ı [WIKICT]. MRI je zaloˇzena na vlastnostech j´adra atom˚ u jednotliv´ ych tk´an´ı. Vystaven´ı magnetick´ ym pol´ım je vyvol´ ana zmˇena magnetick´eho momentu v jednotliv´ ych atomech. V´ ysledn´ y sign´ al je pak sn´ım´ an jako velikost elektrick´eho napˇet´ı, kter´e se indukuje v indukˇcn´ıch c´ıvk´ ach v bl´ızkosti rotuj´ıc´ıho magnetick´eho momentu [WIKIMRI]. Tato metoda je d´ıky absenci rentgenov´eho z´ aˇren´ı pˇr´ıznivˇejˇs´ı pro pacienty, avˇsak m´a i sv´a omezen´ı napˇr. v podobˇe kovov´ ych pˇredmˇet˚ u v tˇele pacienta, a tak´e doba poˇr´ızen´ı jednotliv´ ych sn´ımk˚ u. [BHP06] identifikuj´ı jako typick´e neˇz´adouc´ı projevy ve f´azi skenov´an´ı: • obrazov´ y ˇsum • pohybov´e artefakty • sign´ alov´e artefakty • partial volume efect

3

Obrazov´ ym ˇsumem jsou myˇsleny nedokonalosti z´ıskan´ ych dat v d˚ usledku n´aroˇcnosti technologick´eho ˇreˇsen´ı pˇr´ıstroj˚ u (citlivost detektor˚ u) ˇci omezen´ıch dan´ ych zdravotn´ımi restrikcemi (mnoˇzstv´ı z´ aˇren´ı) atd. Pohybov´e artefakty souvisej´ı se zmiˇ novanou dobou sn´ım´an´ı, kdy v pr˚ ubˇehu sn´ım´an´ı m˚ uˇze doch´azet ke zmˇen´ am, resp. k pohyb˚ um jednotliv´ ych tk´an´ı, napˇr. v d˚ usledku d´ ych´an´ı, tlukotu srdce, pohybu stˇrevn´ıch kliˇcek, ˇci pohybu pacienta, kter´e mohou neˇz´adouc´ım zp˚ usobem ovlivnit z´ıskan´ a data. Sign´alov´e artefakty jsou zp˚ usobeny nedokonalost´ı ˇci omezen´ımi dan´e technologie, napˇr. chybov´e zobrazen´ı m´ıst s kovov´ ymi implant´aty, odst´ınˇen´ı odraz˚ u rentgenov´eho z´aˇren´ı atd. Tzv. partial volume efect se projevuje ˇcastˇeji pˇri niˇzˇs´ıch rozliˇsen´ıch obrazu, a to v d˚ usledku toho, ˇze jeden pixel (resp. voxel) m´a sd´ılet souˇcasnˇe nˇekolik hodnot (napˇr. v jednom voxelu maj´ı b´ yt dva typy tk´ an´ı). To pak ovlivn´ı v´ yslednou hodnotu pixelu (voxelu) a t´ım tak´e hranice objektu detekovan´e ve f´ azi segmentace. Vliv nˇekter´ ych jev˚ u zde popsan´ ych lze eliminovat jeˇstˇe v pˇr´ıpravn´e ˇc´asti pˇred zaˇc´atkem samotn´eho skenov´ an´ı nebo pˇr´ımo pˇri n´ı. Napˇr. spr´avn´e uloˇzen´ı pacienta a jeho pouˇcen´ı, ˇc´ımˇz jsou alespoˇ n ˇc´ asteˇcnˇe redukov´any pohybov´e a sign´alov´e artefakty (viz operace Pˇr´ıprava ke skenov´ an´ı“ v Obr´ azku 1). Odstranˇen´ı partial volume efektu se vˇenuj´ı nˇekter´e ” ´ pokroˇcil´e specializovan´e algoritmy, napˇr [PVE92] (viz operace Uprava raw dat“ v Obr´azku ” 1).

2.2

F´ aze segmentace

Segmentace je t´ım procesem, ve kter´em se z jednotliv´ ych vzork˚ u vstupn´ıch dat detekuj´ı jednotliv´e objekty. Jednotliv´ y vzorek je pak klasifikov´an jako souˇc´ast nˇekter´eho objektu s pomoc´ı r˚ uzn´ ych klasifikaˇcn´ıch technik (napˇr. prahov´an´ı). [BHP06] identifikuj´ı jako typick´e neˇz´adouc´ı projevy ve f´azi segmentace: • blokov´e artefakty • schodovit´e artefakty • d´ıry • roztˇrepen´e okraje • oddˇelen´e ˇc´ asti • faleˇsnˇe pˇripojen´e ˇc´ asti Tyto vznikaj´ı v d˚ usledku jednoznaˇcnosti pˇriˇrazen´ı kaˇzd´eho pixelu/voxelu k objektu. Blokov´e a schodovit´e artefakty se projevuj´ı napˇr. v d˚ usledku moˇzn´e vz´ajemn´e nekonzistentnosti jednotliv´ ych ˇrez˚ u. Jak jiˇz bylo zm´ınˇeno dˇr´ıve, negativn´ı vlivy, kter´e nebyly v pˇredchoz´ı f´azi eliminov´any, pak n´ aslednˇe ovlivˇ nuj´ı i tuto f´ azi. V d˚ usledku chyb zanesen´ ych ve f´azi sn´ım´an´ı jsou pak ovlivnˇeny hodnoty jednotliv´ ych pixel˚ u/voxel˚ u, a segmentaˇcn´ı algoritmus je tud´ıˇz m˚ uˇze nespr´ avnˇe klasifikovat, v d˚ usledku ˇcehoˇz se projev´ı v´ yˇse vyjmenovan´e jevy.

2.3

F´ aze extrakce povrchov´ e s´ıtˇ e

Na vytvoˇren´ı povrchov´e s´ıtˇe z objemov´ ych dat existuj´ı vˇseobecnˇe zn´am´e z´akladn´ı algoritmy jako napˇr. marching cube ˇci marching tetrahedra popˇr. jin´e v´ıce sofistikovan´e metody. 4

[BHP06] identifikuj´ı jako typick´e neˇz´adouc´ı projevy ve f´azi extrakce s´ıtˇe: • velk´e mnoˇzstv´ı troj´ uheln´ık˚ u, kter´e plynou z pouˇzit´eho extrahovac´ıho algoritmu • podlouhlost troj´ uheln´ık˚ u, plynouc´ı z rozd´ıln´e vzd´alenosti rozliˇsen´ı ve smˇeru osy z • nepomˇer velikosti troj´ uheln´ık˚ u k d˚ uleˇzit´ ym rys˚ um povrchu Na odstranˇen´ı ˇci zm´ırnˇen´ı zde zm´ınˇen´ ych jev˚ u jsou vyv´ıjeny r˚ uzn´e optimalizaˇcn´ı techniky ´ pro zlepˇsen´ı kvality povrchov´e s´ıtˇe s ohledem na r˚ uzn´a krit´eria (viz operace Uprava povrchov´e s´ıtˇe v Obr´ azku 1). K tˇemto technik´am patˇr´ı i r˚ uzn´e vyhlazovac´ı techniky, kter´e budou rozebr´ any v n´ asleduj´ıc´ı ˇc´ asti. Vstupem pro algoritmus extrakce povrchov´e s´ıtˇe jsou segmentovan´a data. V pˇr´ıpadˇe, ˇze segmentovan´ a data trp´ı v´ yˇse zm´ınˇen´ ymi artefakty, algoritmus je zpracuje, jako by to byla ˇz´adouc´ı data, tzn. ˇze do v´ ysledn´e s´ıtˇe budou prom´ıtnuty i negativn´ı vlivy z pˇredchoz´ıch f´az´ı se vˇsemi d˚ usledky.

3

Vybran´ e z´ akladn´ı vyhlazovac´ı techniky a pˇ r´ıstupy

Obecnˇe se d´ a ˇr´ıci, ˇze vyhlazovac´ı techniky usiluj´ı o potlaˇcen´ı ˇsumu a osamocen´ ych fluktuac´ı ve vstupn´ıch datech. Pro u ´ˇcely t´eto pr´ace jsou za data uvaˇzov´ana data o prostorov´e mˇr´ıˇzce 3D modelu objektu. Pˇri vyhlazov´an´ı tak doch´az´ı k pˇrem´ıstˇen´ı jednotliv´eho vrcholu v mˇr´ıˇzce do jin´eho um´ıstˇen´ı, tak, aby se v´ıce vyv´aˇzil vztah mezi t´ımto vrcholem a jeho okol´ım. Jednotliv´e pˇr´ıstupy se pak zaob´ıraj´ı volbou d´elky a pˇr´ıhodn´eho smˇeru pohybu, volbou pˇr´ıhodn´eho okol´ı bodu, volbou poˇctu souˇcasnˇe pˇremist’ovan´ ych bod˚ u atd., ve vztahu k zadan´ ym poˇzadavk˚ um na vyhlazovac´ı efekt (napˇr. zachov´an´ı hran, rys˚ u, objemu atd.). Mnoh´e techniky usmˇerˇ nuj´ı vztah mezi bodem a jeho okol´ım postupn´ ym upˇresˇ nov´an´ım aˇz do poˇzadovan´e u ´rovnˇe vyhlazen´ı, nˇekter´e se naopak snaˇz´ı pˇrij´ıt k v´ ysledku najednou dle zadan´ ych parametr˚ u. Tento pˇr´ıstup vych´az´ı zejm´ena ze snahy uˇsetˇrit potˇrebn´ y v´ ypoˇcetn´ı ˇcas, kter´ y plyne z n´ asobn´eho prov´adˇen´ı jednotliv´ ych vyhlazovac´ıch krok˚ u – iterac´ı. Z toho pohledu se nab´ız´ı i z´ akladn´ı ˇclenˇen´ı jednotliv´ ych technik na: • iteraˇcn´ı vyhlazovac´ı techniky • neiteraˇcn´ı vyhlazovac´ı techniky Nˇekter´e techniky se ve sv´em d˚ usledku vz´ajemnˇe velmi podobaj´ı, ale d´ıky odliˇsn´emu pˇr´ıstupu s sebou pˇrin´ aˇsej´ı pˇr´ıpadn´ y dalˇs´ı n´astrojov´ y apar´at pro n´asledn´a rozˇs´ıˇren´ı tˇechto technik. Nˇekter´e techniky jsou zase sp´ıˇse jen optimalizac´ı pro dosahov´an´ı lepˇs´ıch v´ ypoˇcetn´ıch ˇcas˚ u. Pˇred popisem jednotliv´ ych vybran´ ych technik je zapotˇreb´ı zm´ınit jeˇstˇe zp˚ usob popisu povrchov´ ych s´ıt´ı ve vztahu k v´ ypoˇct˚ um jednotliv´ ych algoritm˚ u. Povrchov´ a s´ıt’ je ch´ ap´ ana jako souvisl´ y graf G = {V, E}, kde V je mnoˇzina vrchol˚ u V = (v1 , v2 ..., vn )T a E je mnoˇzina hran E = (e1 , e2 ..., en )T . Vrchol vi je reprezentov´ an jako trojrozmˇern´ y vektor prostorov´ ych souˇradnic, avˇsak jelikoˇz nˇekter´e algoritmy pracuj´ı v jednotliv´ ych smˇerech nez´ avisle, b´ yv´a proto nˇekdy vrchol ve v´ ypoˇctech pˇredstavov´ an hodnotou pouze jedn´e jeho sloˇzky a znaˇcen vi . Ve znaˇcen´ı nˇekter´ ych algoritm˚ u b´ yv´a obˇcas vrchol v pˇreznaˇcen jako x, zejm´ena v souvislosti s pohledem na vrcholy jako na hodnoty diskr´etn´ıho sign´ alu. Okol´ım indexu vrcholu vi v grafu G je naz´ yv´ana mnoˇzina i∗ sloˇzen´ a z index˚ u j spojen´ ych s i hranou, tzn. i∗ = {j : (i, j) ∈ E}; jestliˇze index j patˇr´ı do okol´ı, 5

ˇr´ık´ame, ˇze j je soused i. Takto definovan´e okol´ı je ˇcasto oznaˇcov´ano jako tzv. 1st order okol´ı a pˇredstavuje tedy nejbliˇzˇs´ı pˇr´ım´e okol´ı. Nˇekter´e algoritmy poˇc´ıtaj´ı i s rozˇs´ıˇren´ım okol´ı jeˇstˇe o dalˇs´ı u ´roveˇ n, tedy ˇze do nˇej zahrnou i okol´ı vrchol˚ u z okol´ı, tzv. 2nd order okol´ı, viz Obr´ azek 2.

Obr´ azek 2: 1st oder (ˇcerven´e) a 2nd order okol´ı (modr´e+ˇcerven´e). Zdroj [BHP06]

Bez pˇridan´ ych specifick´ ych poˇzadavk˚ u lze graf povrchov´e s´ıtˇe br´at jako neorientovan´ y graf, tzn. ˇze je-li i sousedem j, tak j je tak´e sousedem i. Avˇsak transformac´ı grafu a hran do orientovan´e podoby lze dos´ ahnout zaj´ımav´ ych efekt˚ u zejm´ena v okrajov´ ych ˇc´astech s´ıtˇe ˇci v situac´ıch, kdy pohyb vrcholu nen´ı ˇz´adouc´ı napˇr. kv˚ uli zachov´an´ı ˇz´adan´eho rysu objektu nebo vnˇejˇs´ıho obrysu objektu. D´ıky jednostrann´e vazbˇe se tak tento vrchol m˚ uˇze pod´ılet na v´ ypoˇctu pohybu ostatn´ıch vrchol˚ u z okol´ı (je jejich sousedem), ale v´ ypoˇcet vlastn´ıho posunu je eliminov´ an v d˚ usledku absence relevantn´ıho okol´ı.

3.1

Iteraˇ cn´ı vyhlazovac´ı techniky

Iteraˇcn´ı vyhlazovac´ı techniky pracuj´ı tak, ˇze celkov´ y v´ ysledn´ y efekt se neprojev´ı ihned, ale vyhlazovac´ı efekt se bude prohlubovat t´ım, ˇze proces bude aplikov´an opakovanˇe na postupnˇe vyhlazovan´ a data. 3.1.1

Laplaci´ ansk´ e vyhlazov´ an´ı – z´ akladn´ı varianta

Ve vyhlazov´ an´ı jednorozmˇern´ ych statistick´ ych dat je jednou z ˇcasto pouˇz´ıvan´ ych metod metoda klouzav´ ych pr˚ umˇer˚ u ˇci metoda v´aˇzen´ ych klouzav´ ych pr˚ umˇer˚ u, jejichˇz c´ılem je podchytit z´ akladn´ı trend ˇrady a eliminovat ruˇsiv´e odchylky od tohoto trendu. Metoda pracuje na principu pr˚ umˇerov´ an´ı okoln´ıch hodnot upravovan´e hodnoty. Laplaci´ansk´e vyhlazov´ an´ı pracuje analogicky i pro prostorov´a data, kdy v´ ysledn´a nov´a pozice upravovan´eho vrcholu je d´ ana jako line´arn´ı kombinac´ı pozic vˇsech vrchol˚ u z okol´ı. Tento pˇr´ıstup je jednoduch´ y a intuitivn´ı a vede k tomu, ˇze v´ ysledn´ y vrchol je pˇresunov´an smˇerem k centroidu dan´eho okol´ı. V´ ysledn´ y posun vrcholu vi je pak v´ ysledkem aplikov´an´ı Laplacian oper´atoru (naz´ yvan´ y t´eˇz Umbrella operator), kter´ y je definov´an jako pr˚ umˇer nad cel´ ym okol´ım dan´eho vrcholu: ∆vi =

1 X vj − vi n j∈i∗

(1)

kde n je poˇcet vrchol˚ u. V´ ysledn´ a nov´a pozice vrcholu vi pak je: vi0 = vi + ∆vi 6

(2)

Obr´azek 3: Pohyb vrcholu (∆vi ) pˇri laplaci´ansk´em vyhlazov´an´ı s uniformn´ımi vahami (ˇcerven´ y) a u ´hlov´ ymi vahami (zelen´ y). Zdroj [NEAL06]

resp. po dosazen´ı z rovnice (1): vi0 = vi +

1 X vj − vi n j∈i∗

(3)

Graficky je tento zp˚ usob zn´ azornˇen na Obr´azku 3 (ˇcerven´ y posun). Tato technika produkuje v´ yrazn´e vyhlazen´ı jiˇz po m´alo iteraˇcn´ıch kroc´ıch, avˇsak jej´ım v´ ysledkem je v´ yrazn´e smrˇst’ov´ an´ı povrchu modelu. 3.1.2

Laplaci´ ansk´ e vyhlazov´ an´ı – v´ aˇ zen´ e varianty

Jelikoˇz v d˚ usledku pln´eho prom´ıtnut´ı se cel´eho okol´ı do v´ ysledn´eho pohybu vrcholu doch´ az´ı v z´akladn´ı nejjednoduˇsˇs´ı variantnˇe laplaci´ansk´eho vyhlazov´an´ı k podstatn´emu smrˇstˇen´ı povrchu modelu, obsahuj´ı nˇekter´e techniky ve sv´e konstrukci i dalˇs´ı parametr. Jeho u ´kolem je vybran´ ym zp˚ usobem zredukovat vliv jednotliv´ ych vrchol˚ u z okol´ı. Dalˇs´ı parametr tedy pˇredstavuje v´ ahu, s jakou se m´ a vliv jednotliv´ ych okoln´ıch vrchol˚ u projevit. V´ ysledn´ y posun vrcholu vi je pak v´ ysledkem aplikov´an´ı Laplacian oper´atoru, kter´ y je definov´ an jako v´ aˇzen´ y pr˚ umˇer nad cel´ ym okol´ım dan´eho vrcholu [TAU00]: ∆vi =

X

wij (vj − vi ) nebo maticovˇe ∆v = −KV

(4)

j∈i∗

kde wij je pˇr´ısluˇsn´e v´ ahov´e ohodnocen´ı vztahu vi a vj , K = (I − W), kde I je jednotkov´ a matice. Pro platnost z´ apisu z rovnice (4) jsou jako v´ahy wij z matice W br´any kladn´ a ˇc´ısla, kter´ a splˇ nuj´ı podm´ınku v´ aˇzen´eho pr˚ umˇerov´an´ı, kdy X

wij = 1

(5)

j∈i∗

Po dosazen´ı do v´ yrazu (1) tak dost´av´ame: vi0 = vi +

X

wij (vj − vi )

(6)

j∈i∗

Z odliˇsn´e konstrukce tˇechto vah jsou pak ˇcasto odvozeny jednotliv´e modifikovan´e techniky pro vyhlazov´ an´ı. Pˇr´ıkladem jsou napˇr. uniformn´ı v´ahy, v´ahy dle d´elky hrany, v´ahy dle plochy tvoˇren´ ych troj´ uheln´ık˚ u ˇci napˇr. v´ahy dle tvaru troj´ uheln´ık˚ u (resp. jejich u ´hl˚ u). Uniformn´ı v´ ahy jsou konstantn´ı pro vˇsechny vrcholy a tud´ıˇz jsou rovny 1/n, kde n je poˇcet vrchol˚ u v okol´ı. Pouˇzit´ım uniformn´ıch vah tedy dost´av´ame z´akladn´ı variantu 7

laplaci´ ansk´eho vyhlazov´ an´ı viz 3.1.1. Jak poznamen´av´a [TAU00], konstantn´ı v´ahy v podstatˇe nerozliˇsuj´ı mezi r˚ uznˇe vzd´alen´ ymi sousedy z okol´ı, a jsou proto vhodn´e pro pouˇzit´ı v s´ıt´ıch s troj´ uheln´ıky s podobnˇe dlouh´ ymi stranami a u ´hly (v opaˇcn´em pˇr´ıpadˇe doch´az´ı k nepˇrirozen´emu zkreslen´ı). Toto omezen´ı je ˇreˇseno napˇr. zohlednˇen´ım d´elek jednotliv´ ych hran v jednotliv´ ych koeficientech. Jako koeficienty pomˇerov´e k d´elce pˇr´ısluˇsn´e hrany zmiˇ nuje [TAU00] napˇr. Fujiwarovy v´ ahy. Jejich pouˇzit´ım pak vyhlazovac´ı proces prob´ıh´a smˇerem k postupn´emu pomˇerov´emu srovn´ av´ an´ı d´elek jednotliv´ ych hran (tzv. scale-dependent umbrella operator). V´ahy jsou tedy konstruov´ any ve smyslu [TAU95]: kvi − vj k−1 −1 h∈i∗ (kvi − vh k )

wij = P

(7)

Pro zahrnut´ı vlivu r˚ uznorodosti hranami sv´ıran´ ych u ´hl˚ u, nam´ısto vlivu d´elky hran, jsou zmiˇ nov´ any i Desbrunovy v´ ahy (´ uhlov´e, kotangentov´e). V´ ysledkem jejich pouˇzit´ı je pak tendence k lepˇs´ı aproximaci zachov´an´ı parametr˚ u pr˚ ubˇehu zakˇriven´ı v˚ uˇci okol´ı (eliminace tangentov´e sloˇzky posunu - hodnota zakˇriven´ı se sice zmˇen´ı, ale je zachov´ an jeho charakter), pˇriˇcemˇz avˇsak neodstraˇ nuje nepravidelnost s´ıtˇe (mesh irregularity). V´ahy jsou pak konstruov´ any ve smyslu [TAU95]: cot αi j + cot βi j h∈i∗ (cot αi h + cot βi h)

wij = P

(8)

kde αi j a βi j jsou u ´hly protilehl´e k hranˇe e = (i, j) sd´ılen´e obˇema troj´ uheln´ıky (viz Obr´azek 3). Oper´ ator s takto konstruovan´ ymi vahami b´ yv´a t´eˇz oznaˇcov´an jako curvature ” operator“ ˇci curvature flow method“ [DES99]. ” Dalˇs´ı ˇcasto pouˇz´ıvan´e v´ ahy vych´azej´ı z tzv. gaussovsk´e funkce, jej´ıˇz tvar umoˇzn ˇuje d´at v´ yraznˇe vˇetˇs´ı v´ ahu bliˇzˇs´ım soused˚ um a naopak (tzv. gaussovsk´ e vyhlazov´ an´ı). Normalizovan´e v´ ahy pak maj´ı tvar: e

wij =

−kvi −vj k2 2σ 2

 P

e

h∈i∗

−kvi −vh k2 2σ 2



(9)

kde parametr σ urˇcuje ˇs´ıˇrku hlavn´ı ˇc´asti gaussovsk´e funkce, a t´ım tud´ıˇz i pr´ah vzd´alenosti, kdy vliv soused˚ u bude povaˇzov´ an za v´ yznamn´ y. Obecnˇe vzato, vˇsechny v´ yˇse zmiˇ novan´e neuniformn´ı v´ahy jsou z´avisl´e na poloze vrcholu, a tud´ıˇz se jejich hodnoty mezi jednotliv´ ymi iteracemi mˇen´ı. Z tohoto d˚ uvodu je pro dosaˇzen´ı pln´eho poˇzadovan´eho efektu ˇz´adouc´ı v´ahy mezi iteracemi pˇrepoˇc´ıt´avat, ˇc´ımˇz vˇsak adekv´ atnˇe vzr˚ ust´ a v´ ypoˇcetn´ı n´ aroˇcnost. 3.1.3

Bilater´ aln´ı vyhlazov´ an´ı

Bilater´ aln´ı vyhlazov´ an´ı (Bilateral mesh denoising) je metoda inspirovan´a podobn´ ymi postupy uˇz´ıvan´ ymi pro odˇsumov´ an´ı 2D obrazu. Touto metodou se zab´ yv´a napˇr. [FLEIS03]. Zat´ımco pˇri v´ aˇzen´em laplaci´ ansk´em vyhlazov´an´ı zohledˇ nuj´ı v´ahy pouze prostorov´e hledisko, bilater´ aln´ı vyhlazov´ an´ı pˇrid´av´a jeˇstˇe hledisko druh´e, tzv. podobnostn´ı, jehoˇz u ´kolem je zachov´ av´ an´ı rys˚ u objektu. Pˇri pˇrevodu na 3D povrchov´e s´ıtˇe pak [FLEIS03] vyuˇz´ıv´a i tu vlastnost, ˇze hodnoty povrchov´e s´ıtˇe lze rozloˇzit na norm´alovou (geometrick´a informace o tvaru) a tangentovou 8

komponentu (parametrick´ a informace). Vrcholy s´ıtˇe jsou pak v r´amci vyhlazovac´ıho procesu posouv´ any ve smˇeru norm´aly. Hlavn´ı myˇslenka vych´ az´ı z toho, ˇze vrcholy zaˇsumˇen´e povrchov´e s´ıtˇe neleˇz´ı pˇresnˇe v m´ıstˇe, kter´e bylo na ide´ aln´ım nezaˇsumˇen´em povrchu, ale jsou od nˇej vzd´aleny o nˇejakou hodnotu ´ (d´ale v´ yˇsku). Ukolem algoritmu je posunout vrcholy tak, aby byly co nejbl´ıˇze k ide´aln´ımu povrchu. K tomu je tˇreba urˇcit smˇer a vzd´alenost posunu. Smˇer je urˇcen norm´alou k ide´aln´ımu povrchu v nejbliˇzˇs´ım bodˇe od posunovan´eho bodu. Jelikoˇz vˇsak ide´aln´ı povrch je nezn´ am´ y, je nahrazen aproximac´ı - norm´alou v dan´em bodˇe vyhlazovan´e povrchov´e s´ıtˇe. Nov´a poloha bodu pak vyh´ az´ı ze vztahu: vi0 = vi + di · ni

(10)

kde vi je dan´ y vrchol, ni norm´ala k povrchu vyhlazovan´e s´ıtˇe v mˇenˇen´em vrcholu vi a di je filtraˇcn´ı parametr ud´ avaj´ıc´ı s´ılu posunu (vzd´alenost). Konstrukce tohoto filtraˇcn´ıho parametru, resp. d´elky posunu, vych´az´ı z konstrukce obdobn´eho filtru pro odˇsumov´an´ı 2D obrazu. Ten zohledˇ nuje dvˇe z´ akladn´ı krit´eria: • prostorov´e (spatial, closeness) • podobnostn´ı (similarity, influence) Prostorov´e krit´erium je zohlednˇeno vzd´alenostn´ı v´ahou v˚ uˇci sousedn´ım vrchol˚ um, kdy bliˇzˇs´ım vrchol˚ um ze sousedstv´ı je pˇriˇrazena vyˇsˇs´ı v´aha, kdeˇzto vliv nejvzd´alenˇejˇs´ıch je postupnˇe potlaˇcen. Konstrukce t´eto v´ahov´e funkce vych´az´ı z gaussovsk´e funkce a m´a tvar [FLEIS03]: −x2

Wc (x) = e 2σc2

(11)

kde x pˇredstavuje 3D euklidovskou vzd´alenost kvi − vj k posunovan´eho bodu vi a dan´eho bodu ze sousedstv´ı vj a σc je voliteln´ y parametr pro ovl´ad´an´ı rozsahu sousedstv´ı s podstatn´ ym vlivem na posun (tzv. mesh radius), pˇriˇcemˇz rozsah sousedstv´ı je omezen vztahem kvi − vj k < ρ = [2σc ], kde j ∈ i∗. Ze zvolen´eho menˇs´ıho σc tedy vypl´ yv´a menˇs´ı rozsah relevantn´ıho sousedstv´ı i∗, ˇc´ımˇz se i sn´ıˇz´ı poˇcet v´ ypoˇcetn´ıch krok˚ u ve vzorci (13), a t´ım i nutn´ y v´ ypoˇcetn´ı ˇcas v jedn´e iteraci. Pro v´ ysledn´ y efekt je pak vˇsak tˇreba v´ıce iterac´ı. Naopak pˇri pˇr´ıliˇs velk´em σc je zapotˇreb´ı k v´ ysledn´emu efektu sice menˇs´ı poˇcet iterac´ı, avˇsak nˇekter´e drobnˇejˇs´ı rysy (napˇr. hrany, rohy) nebudou pak zachov´any a budou tak´e vyhlazeny. Podobnostn´ı krit´erium je d´ ano dalˇs´ı v´ahovou funkc´ı, kter´a v pˇr´ıpadˇe 2D obrazu m´a za u ´kol penalizovat velk´e rozd´ıly v intenzitˇe pixelu (zohledˇ nuje v´ıce podobn´e pixely, hodnoty s v´ yrazn´ ymi zmˇenami jsou pak v´aˇzeny n´ıˇze). Velk´e rozd´ıly v intenzit´ach jsou povaˇzov´any za rysy objektu (napˇr. hrany) a aplikov´an´ım t´eto v´ahov´e funkce tak dojde ke sn´ıˇzen´ı vlivu tohoto vrcholu na celkov´em v´ ypoˇctu, a tud´ıˇz rysy z˚ ustanou zachov´any. V pˇr´ıpadˇe 3D povrchov´e s´ıtˇe jsou intenzity nahrazeny v´ yˇskami (vzd´alenostmi) mezi body ze sousedstv´ı vj∈i∗ a teˇcnou rovinou ve sledovan´em bodˇe vi . Podobnostn´ı v´ ahov´ a funkce rovnˇeˇz vych´az´ı z gaussovsk´e funkce a m´a tvar [FLEIS03]: −x2

Ws (x) = e 2σs2

(12)

kde vˇsak x pˇredstavuje vzd´ alenost dan´eho bodu vj∈i∗ k teˇcn´e rovinˇe posouvan´eho bodu vi (resp. jeho projekc´ı na tuto rovinu), tzn. v´ yˇsku hj . Parametr σs pˇredstavuje voliteln´ y parametr, tzv. smooth point, kter´ y ovlivˇ nuje, jak budou jednotliv´e v´ yˇsky penalizov´any

9

vzhledem ke sv´e velikosti ( pr´ ah podobnosti“). Kontroluje se j´ım tedy velikost rys˚ u, kter´e ” z˚ ustanou zachov´ any. Doporuˇcovanou volbou je hodnota standardn´ı odchylky hodnot v´ yˇsek. Kombinac´ı obou dvou krit´eri´ı, dosazen´ım promˇenn´ ych a normalizac´ı pak vznik´a v´ ysledn´ y vztah pro v´ ypoˇcet parametru di : P

di =

− vj k) · Ws (|hj |) · hj j∈i∗ Wc (kvi − vj k) · Ws (|hj |)

j∈i∗ Wc (kvi

P

(13)

Norm´ alu ni do vzorce (10) poˇc´ıt´ a [FLEIS03] jako v´aˇzen´ y pr˚ umˇer norm´al vˇsech troj´ uheln´ık˚ u (v´ahy dle plochy troj´ uheln´ık˚ u) pouze z 1st order okol´ı, aby zabr´anil tzv. oversmoothing“, ” kter´ y by napˇr. u velmi ostr´ ych hran mohl pˇri pouˇzit´ı ˇsirˇs´ıho okol´ı nastat. Pouˇzit´ı ˇsirˇs´ıho okol´ı doporuˇcuje na velmi zaˇsumˇen´a data, kde hroz´ı, ˇze pouˇzit´ı pouze 1st order okol´ı by mohlo v´ yznamnˇe zkreslit v´ ypoˇcet norm´al. Popis algoritmu v pseudok´ odu lze nal´ezt napˇr. v [FLEIS03]. Algoritmus je c´ılen jako algoritmus zachov´ avaj´ıc´ı rysy modelu, avˇsak neˇreˇs´ı probl´em smrˇst’ov´an´ı. [FLEIS03] tak´e upozorˇ nuje na probl´em, kdy se vzr˚ ustaj´ıc´ım poˇctem iterac´ı v kombinaci s v´ yraznˇe nepravidelnou povrchovou s´ıt´ı s ostr´ ymi u ´hly m˚ uˇze doch´azet k pˇrekˇr´ıˇzen´ı vrchol˚ u. Algoritmus je tedy vhodn´ y sp´ıˇse na pravideln´e s´ıtˇe (coˇz je ˇcast´ y pˇr´ıpad u s´ıt´ı ze skenovac´ıch zaˇr´ızen´ı). 3.1.4

Norm´ alov´ e vyhlazov´ an´ı

Norm´ alov´e vektory na povrchu s´ıtˇe maj´ı velik´ y geometrick´ y v´ yznam ve vztahu k modelovan´emu objektu a z hlediska norm´alov´eho vyhlazov´an´ı dokonce vyˇsˇs´ı, neˇz v´ yznam pozice vrchol˚ u, jako je tomu v pˇr´ıpadˇe klasick´ ych vyhlazovac´ıch metod. Jak uv´ad´ı [LEE05], hladk´ y povrch m˚ uˇze b´ yt pops´ an jako takov´ y povrch, kter´ y m´a plynule se mˇen´ıc´ı norm´ aly, ” zat´ımco rysy, jako napˇr. hrany a rohy, se jev´ı jako nespojitosti mezi norm´alami.“ Z´akladn´ı princip norm´ alov´eho vyhlazov´an´ı tedy spoˇc´ıv´a ve vyhlazen´ı“ pˇr´ıliˇsn´ ych odchylek ” norm´ alov´ ych vektor˚ u a n´ asledn´em odvozen´ı nov´ ych pozic jednotliv´ ych vrchol˚ u povrchov´e s´ıtˇe. Pro vyhlazen´ı“ norm´ alov´ ych vektor˚ u lze vyuˇz´ıt r˚ uzn´e metody, napˇr. z´akladn´ı ˇci v´aˇzen´e ” pr˚ umˇerov´ an´ı, bilater´ aln´ı vyhlazov´an´ı atd. viz napˇr. [BEOH03], [SRML07], [LEE05]. Jednu z metod popisuje napˇr. [BEOH03], kter´ y pouˇz´ıv´a pr˚ umˇerov´an´ı norm´al v´aˇzen´e dle plochy sousedn´ıch troj´ uheln´ık˚ u. Pˇri v´ ypoˇctu nepracuje [BEOH03] s jednotliv´ ymi vrcholy, ale pˇr´ımo s cel´ ymi troj´ uheln´ıky povrchov´e s´ıtˇe. Nov´a vyhlazen´a norm´ala n0i troj´ uheln´ıku i pak vych´ az´ı ze vztahu: X n0i = Aj · nj (14) j∈i∗

kde sousedstv´ı i∗ se vztahuje nikoliv k bodu, n´ ybrˇz k troj´ uheln´ıku i, a tud´ıˇz Aj pˇredstavuje plochu troj´ uheln´ıku j soused´ıc´ıho s upravovan´ ym troj´ uheln´ıkem i a nj pˇredstavuje jeho norm´ alu. Pro dalˇs´ı v´ ypoˇcty se pak novˇe vznikl´e vyhlazen´e norm´aly normuj´ı na jednotkovou d´elku n0j → n0j . Jin´ y zp˚ usob zp˚ usob norm´ alov´eho vyhlazov´an´ı popisuje napˇr. [LEE05], kter´ y pro vyhlazen´ı“ norm´ alov´ ych vektor˚ u vyuˇz´ıv´a modifikaci bilater´aln´ıho filtru zmiˇ novan´eho ” v kapitole o bilater´ aln´ım vyhlazov´an´ı (3.1.3), jenˇz metodˇe dod´av´a vlastnost zachov´av´ an´ı rys˚ u modelu (feature preserving). Pro nov´e um´ıstˇen´ı jednotliv´ ych vrchol˚ u pak n´aslednˇe vyuˇz´ıv´ a metod nejmenˇs´ı kvadratick´e chyby (LSE) obdobnˇe jako [BEOH03]. Pˇri konstrukci bilater´ aln´ıho filtru pracuje [LEE05] obdobnˇe jako [BEOH03] s cel´ ymi troj´ uheln´ıky povrchov´e s´ıtˇe, kde bod ci pˇredstavuje tˇeˇziˇstˇe (centroid) troj´ uheln´ıku i 10

a vektor ni jemu pˇr´ısluˇsn´ y jednotkov´ y norm´alov´ y vektor. Pro v´ ysledn´ y nov´ y vyhlazen´ y“ ” norm´ alov´ y vektor n0i pak [LEE05] vych´az´ı ze vztahu: n0i

P

=

− ci k) · Ws (dij ) · nj j∈i∗ Wc (kcj − ci k) · Ws (dij )

j∈i∗ Wc (kcj

P

(15)

kde pro v´ ahov´e funkce Wc a Ws plat´ı stejn´e z´akladn´ı vztahy jak´e byly pops´any v kapitole o bilater´ aln´ım vyhlazov´ an´ı (3.1.3), tj. vztahy z rovnice (11) a (12). Promˇenou dosazovanou do funkce Wc je zde vˇsak, nam´ısto 3D euklidovsk´e vzd´alenosti vrchol˚ u, vzd´alenost mezi ´ tˇeˇziˇsti c jednotliv´ ych troj´ uheln´ık˚ u. Uloha t´eto v´ahov´e funkce je rovnˇeˇz obdobn´a, a to ovlivˇ novat rozsah relevantn´ıho sousedn´ıho okol´ı, tj. d´avat vˇetˇs´ı v´ahu bliˇzˇs´ım a menˇs´ı v´ahu vzd´ alenˇejˇs´ım troj´ uheln´ık˚ um ze sousedstv´ı. Do funkce Ws je jako promˇenn´a, nam´ısto vzd´alenost´ı sousedn´ıch bod˚ u a teˇcn´e roviny, dosazov´an parametr dij , kter´ y pˇredstavuje prom´ıtnut´ı rozd´ılov´eho vektoru jednotkov´ ych norm´al ni a nj na norm´alu ni , tj. je d´ an skal´arn´ım souˇcinem: dij = ni · (ni − nj ) (16) Tato konstrukce Ws (dij ) zajiˇst’uje, ˇze ve v´ ypoˇctu vyhlazen´e norm´aly je potlaˇcen vliv velmi odliˇsn´ ych norm´ alov´ ych vektor˚ u, kter´e jsou charakteristick´e napˇr. pro rysy objektu (hrany, rohy), kter´e je ˇz´ adouc´ı nevyhlazovat. Popisovan´ a metoda patˇr´ı mezi iteraˇcn´ı metody, tzn. ˇze vyhlazen´ı norm´al“ prob´ıh´ a ” v jednotliv´ ych iterac´ıch aˇz do dosaˇzen´ı poˇzadovan´eho efektu. Jelikoˇz jsou vˇsak do vztah˚ u (15) a (16) dosazov´ any vˇzdy jednotkov´e vektory, je tˇreba v´ ysledn´ y norm´alov´ y vektor nj mezi jednotliv´ ymi iteracemi normalizovat na jednotkovou d´elku n0j → n0j . Po vyhlazen´ı norm´ al jednotliv´ ych troj´ uheln´ık˚ u povrchov´e s´ıtˇe je jako n´asleduj´ıc´ı krok nutn´e stanovit odpov´ıdaj´ıc´ı nov´e pozice vrchol˚ u. Jelikoˇz norm´alov´ y vektor je v˚ uˇci troj´ uheln´ıku kolm´ y, mˇelo by i pro hrany novˇe zformovan´ ych troj´ uheln´ık˚ u platit, ˇze jejich prom´ıtnut´ı na vyhlazen´ y norm´ alov´ y vektor by nemˇelo m´ıt ˇz´adnou d´elku, resp. by mˇelo b´ yt nulov´e. Mˇelo by tedy platit:  0   ni · (vj − vi ) = 0 (17) n0i · (vk − vj ) = 0   0 ni · (vi − vk ) = 0 Jelikoˇz jsou vˇsak jednotliv´e vrcholy sd´ıleny v´ıce troj´ uheln´ıky a vztah (17) mus´ı platit pro kaˇzd´ y troj´ uheln´ık, [LEE05] upozorˇ nuje na neexistenci ˇreˇsen´ı pro obecn´e povrchov´e s´ıtˇe. Z toho d˚ uvodu vyuˇz´ıv´ a pˇribliˇzn´e ˇreˇsen´ı s nejmenˇs´ı chybou (minimalizuje nejmenˇs´ı kvadratickou chybou). Pro v´ ysledn´e nov´e um´ıstˇen´ı vrchol˚ u vi0 existuje nˇekolik vyj´adˇren´ı a pˇr´ıstup˚ u, viz [SRML07]. [LEE05] napˇr. uv´ad´ı vztah: vi0 = vi + λ

X X

nf · nT f (vj − vi )

(18)

j∈i∗ f ∈Fij

kde Fij pˇredstavuje mnoˇzinu troj´ uheln´ık˚ u f pˇril´ehaj´ıc´ıch k hranˇe {i, j} a λ je doplˇ nkov´ y parametr ovlivˇ nuj´ıc´ı velikost iteraˇcn´ıho kroku. 3.1.5

Sign´ alov´ y pˇ r´ıstup k vyhlazov´ an´ı

V [TAU95] ˇci [TAU00] je pˇredstaven odliˇsn´ y pˇr´ıstup k vyhlazov´an´ı a pohledu na data, i kdyˇz s n´ım lze dos´ ahnout vztah˚ u analogick´ ych k v´ yˇse pˇredstaven´ ym technik´am. Pˇri zpracov´ av´ an´ı 1D ˇci 2D dat, napˇr. pro potˇreby zpracov´an´ı obr´azk˚ u, ekonomick´ ych predikc´ı ˇci fyzik´ aln´ıch mˇeˇren´ı, je zcela bˇeˇzn´e pˇristupovat k dat˚ um jako k diskr´etn´ımu 11

sign´alu, na jehoˇz zpracov´ an´ı je vyuˇz´ıv´ana frekvenˇcn´ı anal´ yza, kde z´akladn´ım n´astrojem je Fourierova transformace. Ta je zaloˇzena na skuteˇcnosti, ˇze kaˇzd´ y sign´al jde rozloˇzit a vyj´ adˇrit s pomoc´ı harmonick´ ych sign´al˚ u. V´ yrazn´e zmˇeny ve vstupn´ım sign´alu, kter´e ˇcasto pˇredstavuj´ı ˇsum, odpov´ıdaj´ı sign´alu o vysok´e frekvenci. Je-li k dispozici rozklad sign´alu do frekvenˇcn´ı oblasti, nab´ız´ı se jako ˇreˇsen´ı pro potlaˇcen´ı neˇz´adouc´ıho ˇsumu tyto vysokofrekvenˇcn´ı prvky rozloˇzen´eho sign´alu eliminovat ˇci zcela vypustit a ze zbyl´eho zpˇetnˇe sloˇzit vyhlazen´ y sign´ al nov´ y. Tento pˇr´ıstup aplikuje napˇr. [TAU95], [TAU96], [TAU00] i na 3D povrchovou s´ıt’, kdy na vrcholy s´ıtˇe nahl´ıˇz´ı jako na hodnoty diskr´etn´ıho sign´alu. [TAU95][TAU96][TAU00] vyuˇz´ıv´ a toho, ˇze v´ ypoˇcet diskr´etn´ı Fourierovy transformace je ekvivalentn´ı rozkladu sign´alu jako ” line´arn´ı kombinaci vlastn´ıch vektor˚ u Laplacian oper´atoru“. Pro rozklad vyuˇz´ıv´a Laplacian oper´ator viz rovnice (4). V´ ysledn´ y rozklad takto pojat´eho sign´alu x, s vyuˇzit´ım vlastnost´ı matice K a jej´ıch vlastn´ıch vektor˚ u, m´a pak podobu: x=

n X

ξi ui

(19)

i=1

kde u jsou pˇr´ısluˇsn´e vlastn´ı vektory k matici K, a kde koeficienty ξ pˇredstavuj´ı diskr´etn´ı Fourierovu transformaci x. Jak uv´ad´ı [TAU00], vlastn´ı vektory lze ch´apat jako pˇrirozen´e vibraˇcn´ı m´ ody a jim pˇr´ısluˇsn´ a vlastn´ı ˇc´ısla (odpov´ıdaj´ıc´ı prvky z K) jako pˇrirozen´e frekvence. Proto se pˇri filtrov´ an´ı sign´alu zamˇeˇruje pr´avˇe na tyto hodnoty. Nicm´enˇe d˚ usledn´ a aplikace tohoto postupu je v´ ypoˇcetnˇe nepˇrijateln´a, coˇz vede k pˇredstaven´ı pˇribliˇzn´ ych metod pomoc´ı r˚ uzn´ ych tzv. low-pass filtr˚ u. Ty jsou zaloˇzeny na tzv. transferov´e funkci f (k) s n´ asleduj´ıc´ım vztahem pro v´ ypoˇcet pˇribliˇzn´e aproximace: x0 = f (K)x =

n X

f (ki )ξi ui

(20)

i=1

Ide´aln´ı transferov´ a funkce f (k) by mˇela m´ıt ostˇre schod’ovit´ y charakter, kdy pro n´ızk´e frekvence by mˇela hodnoty 1 (tzn. pro dalˇs´ı v´ ypoˇcty by z˚ ustaly tyto frekvence zachov´any), a pro vysok´e frekvence by mˇela hodnoty 0, ˇc´ımˇz by tyto byly eliminov´any (viz Obr´azek 4 vlevo). Na n´ avrhu takov´eto funkce, s ohledem na pouˇzitelnost ve v´ ypoˇctech, jsou pak zaloˇzeny dalˇs´ı vyhlazovac´ı techniky a jejich modifikace.

Obr´ azek 4: Ide´ aln´ı filtr a λ − µ filtr po nˇekolika iterac´ıch. Zdroj [TAU96]

Algoritmus λ − µ. Na z´ akladˇe v´ yˇse zm´ınˇen´eho pˇr´ıstupu navrhl [TAU95] vlastn´ı filtr, resp. transferovou funkci a souvisej´ıc´ı dvoustupˇ nov´ y algoritmus, kter´ y je z´aroveˇ n pˇr´ızniv´ y vzhledem ke k nechtˇen´emu smrˇst’ov´an´ı povrchu. Transferov´a funkce m´a tvar: f (k) = (1 − λk)(1 − µk) 12

(21)

kde λ je kladn´e ˇc´ıslo a µ je takov´e ˇc´ıslo, ˇze plat´ı µ < −λ < 0. Pro zjiˇstˇen´ı filtraˇcn´ıho prahu kP B (pass-band freqency) je d˚ uleˇzit´a hranice f (k) = 1. D˚ usledkem je vztah pro jeho stanoven´ı: 1 1 + >0 (22) λ µ Z pr˚ ubˇehu grafu takto nastaven´e transferov´e funkce je vidˇet alespoˇ n pˇribliˇzn´a podoba s ide´aln´ı schodovitou transferovou funkc´ı, viz Obr´azek 4. Tato se jeˇstˇe v´ıce pˇribliˇzuje se vzr˚ ustaj´ıc´ım poˇctem iterac´ı. kP B =

Oblast s n´ızk´ ymi frekvencemi je zde zachycena jako oblast mezi 0 a kP B . Tyto frekvenˇcn´ı ˇcleny se do v´ ysledn´ ych hodnot pˇrenesou plnˇe, kdeˇzto hodnoty vysokofrekvenˇcn´ıch ˇclen˚ u nikoliv (ide´ alnˇe) nebo jen v omezen´em rozsahu dan´em strmost´ı transferov´e funkce. Parametr kP B tedy urˇcuje hranici, kter´e frekvence jsou povaˇzov´any za n´ızk´e a kter´e za vysok´e. Tento parametr je uˇzivatelsky nastaviteln´ y a m´a vliv na s´ılu fin´aln´ıho vyhlazovac´ıho efektu. [TAU96] tak´e poukazuje, ˇze dle rovnice (19) lze k v´ ysledn´emu kP B dospˇet s mnoha zp˚ usoby ˇ nastaven´ı parametr˚ u λ a µ. C´ım vyˇsˇs´ı jsou tyto parametry, t´ım strmˇejˇs´ı tvar filtr m´a (a t´ım m´enˇe iterac´ı je zapotˇreb´ı k dosaˇzen´ı poˇzadovan´eho tvaru filtru neˇz u niˇzˇs´ıch hodnot parametr˚ u), avˇsak napˇr. [TAU96] upozorˇ nuje na hrozbu nestability takov´ ychto filtr˚ u, kdy pro vysok´e parametry se transferov´a funkce od urˇcit´e hodnoty pˇrestane bl´ıˇzit k 0, n´ ybrˇz zaˇcne strmˇe nab´ yvat neˇz´ adouc´ıch hodnot. Pro z´akladn´ı pouˇzit´ı napˇr. [TAU95] doporuˇcuje nastaven´ı parametru kP B v intervalu 0, 01 − 0, 1 a pro nastaven´ı λ a µ vyuˇz´ıv´a vztahu f (1) = f (−2), kter´ y jiˇz pro mal´ y poˇcet iterac´ı zaruˇcuje stabiln´ı pr˚ ubˇeh filtru a z´aroveˇ n jsou hodnoty parametr˚ u dostateˇcnˇe vysok´e pro zajiˇstˇen´ı uspokojiv´e strmosti transferov´e funkce. Algoritmicky je postup rozdˇelen do dvou f´az´ı, kdy nejprve je proveden vyhlazovac´ı krok (1−λk) a vz´ apˇet´ı na to korekˇcn´ı (protipohyb) krok (1−µk). Popis algoritmu v pseudok´odu lze nal´ezt napˇr. v [TAU95]. Geometricky se d´ a na λ − µ algoritmus a na jeho transferovou funkci nahl´ıˇzet tak´e tak, ˇze prvn´ı jeho ˇc´ ast samostatnˇe pˇredstavuje smˇer pohybu ve stylu laplace´ansk´eho vyhlazov´ an´ı s pˇr´ısluˇsn´ ym scale faktorem λ. Druh´a jeho ˇc´ast je podobn´e konstrukce, avˇsak s opaˇcn´ ym znam´enkem dan´eho charakterem faktoru µ, a tud´ıˇz dojde ke korekci smˇeru pohybu smˇerem zpˇet a v´ ysledn´e zkreslen´ı, resp. smrˇstˇen´ı, nen´ı v´ yrazn´e. Transferov´ a funkce opˇet vyuˇz´ıv´ a matici K spolutvoˇrenou z matice pˇr´ısluˇsn´ ych vah, avˇsak tyto v´ ahy nejsou specifikov´ any. Tento algoritmus tud´ıˇz nab´ız´ı dalˇs´ı moˇzn´e kombinace sv´eho nastaven´ı s r˚ uzn´ ymi typy vah (pˇri dodrˇzen´ı charakteru matice K, kdy 0 < k∈K < 2), napˇr. z rovnic (7) ˇci (8). Taubin FIR Filter. Ve snaze o optimalizaci vyhlazovac´ıho procesu se nab´ız´ı zkoum´ an´ı ˇsirok´eho spektra funkc´ı s charakterem low-pass filtru, kdy je snaha se tomu ide´aln´ımu co nejbl´ıˇze pˇribl´ıˇzit. Po algoritmu s vyuˇzit´ım λ − µ filtru zkoum´a d´ale [TAU96] vyuˇzit´ı vyj´ adˇren´ı polynomi´ aln´ı transferov´e funkce pomoc´ı Chebyshevovo polynom˚ u. Takto navrˇzen´ a transferov´ a funkce m´ a pak tvar: θP B k fN (k) = · T0 1 − π 2 



+

N X 2 sin(nθP B ) n=1

nπ



· Tn

k 1− 2



(23)

kde N je poˇcet iterac´ı a θP B odpov´ıd´a vztahu: kP B = 2 · (1 − cos(θP B )) 13

(24)

a Tn (w) je n-t´ y Chebyshev˚ uv polynom definovan´ y jako: Tn (w) =

   1

w

  2·w·T n−1 (w) − Tn−2 (w)

pro n = 0 pro n = 1 pro n > 1

(25)

Protoˇze takto navrˇzen´ a funkce m´a pˇred i po hlavn´ı strm´e f´azi poklesu jeˇstˇe nezanedbateln´e v´ ykyvy“ (tzv. Gibbs˚ uv fenom´en), vyuˇz´ıv´a [TAU96] techniky pouˇz´ıvan´e pro tvorbu FIR ” filtr˚ u, tzv. windowing“. Ten spoˇc´ıv´a v aplikov´an´ı speci´aln´ı funkce (tzv. okno), jej´ımˇz ” u ´kolem je hodnoty v dan´e ˇc´ asti tzv. okna zv´ yraznit a v jin´ ych ˇc´astech potlaˇcit. Tˇechto okenn´ıch“ funkc´ı existuje cel´ a ˇrada dle zp˚ usobu vyuˇzit´ı. Pro v´ yˇse zm´ınˇenou transferovou ” funkci uvaˇzuje [TAU96] pˇr´ıpady tˇechto okenn´ıch funkc´ı“: ”   1.0 Rectangular    0.5 + 0.5 cos(nπ/(N + 1)) Hanning wn = (26)  0.54 + 0.46 cos(nπ/(N + 1)) Hamming    0.42 + 0.5 cos(nπ/(N + 1)) + 0.08 cos(2nπ/(N + 1)) Blackman N´avrh transferov´e funkce dle vztahu (23) d´ale trp´ı rovnˇeˇz nedostatkem spoˇc´ıvaj´ıc´ım ve velice u ´zk´em pass-band regionu [0, kP B ], kter´ y by splˇ noval poˇzadavky f (k) ≥ 1 (v cel´em pass-band regionu by fN (k) mˇela b´ yt co nejbl´ıˇze hodnotˇe 1), pˇriˇcemˇz vyuˇzit´ım zmiˇ novan´ ych oken“ se tento probl´em jeˇstˇe prohlubuje. Jako ˇreˇsen´ı [TAU96] doplˇ nuje ” jeˇstˇe dalˇs´ı parametr σ, kter´ y zajiˇst’uje rozˇs´ıˇren´ı hlavn´ı vlny“ transferov´e funkce tak, ” aby transferov´ a funkce v pass-band oblasti co nejv´ıce vyhovovala poˇzadavk˚ um. Probl´em vˇsak spoˇc´ıv´ a ve stanoven´ı samotn´eho parametru σ, kter´ y je tˇreba stanovit numericky maximalizac´ı f (kP B ) za podm´ınky |f (k)| < 1 pro kP B < k ≤ 2, resp. ˇreˇsen´ım fN (kP B ) = 1. V´ ysledn´ a transferov´ a funkce vyuˇz´ıvaj´ıc´ı okna“ a parametr σ m´a pak podobu: ”     N X (θP B + σ) 2 sin(n(θP B + σ)) k k fN (k) = w0 · · T0 1 − + wn · · Tn 1 − π 2 nπ 2 n=1

(27)

Porovn´ an´ı transferov´ ych funkc´ı bez pouˇzit´ı okna, s pouˇzit´ım okna, s pouˇzit´ım okna vˇcetnˇe parametru σ a transferovou funkc´ı λ − µ stejn´eho ˇr´adu (N = 20) ukazuje Obr´azek 5. Na nˇem je vidˇet ˇz´ adan´ y strmˇejˇs´ı pokles transferov´e funkce oproti λ − µ transferov´e funkci i zmiˇ novan´ a problematika u ´zk´eho hlavn´ıho vrcholu funkce, kdy bez pouˇzit´ı parametru σ (σ = 0.00) funkce v´ yznamnˇe kles´a jiˇz v pass-band oblasti, ve kter´e je ˇz´adouc´ı aby byla st´ale co nejbl´ıˇze hodnotˇe 1. Stanoven´a transferov´a funkce se pak pouˇz´ıv´a dle rovnice (20). Popis cel´eho algoritmu v pseudok´odu lze nal´ezt napˇr. v [TAU96].

3.2

Neiteraˇ cn´ı vyhlazovac´ı techniky

Pˇri pouˇzit´ı iteraˇcn´ıch technik pro vyhlazov´an´ı je v´ ysledn´eho efektu dosahov´ano postupnˇe bˇehem opˇetovn´eho nˇekolikan´ asobn´eho aplikov´an´ı techniky na pˇredchoz´ı v´ ysledek. To sebou nutnˇe nese tak´e patˇriˇcn´ y n´ ar˚ ust potˇrebn´eho v´ ypoˇcetn´ıho ˇcasu. Tento nedostatek se snaˇz´ı eliminovat techniky neiteraˇcn´ı, kdy poˇzadovan´eho vyhlazovac´ıho efektu je dosaˇzeno hned pˇri jedin´em aplikov´ an´ı vyhlazovac´ıho procesu. 3.2.1

Bilater´ aln´ı vyhlazov´ an´ı - neiteraˇ cn´ı verze

Jednu z technik neiteraˇcn´ıho vyhlazov´an´ı povrchov´e troj´ uheln´ıkov´e s´ıtˇe pˇredstavuje technika pˇredstaven´ a v [JODD03]. Tato technika se ˇrad´ı mezi techniky bilater´aln´ıho 14

Obr´azek 5: Porovn´ an´ı r˚ uznˇe konstruovan´ ych transferov´ ych funkci fN (k) stejn´eho ˇr´adu (N = 20). Zdroj: vlastn´ı v´ ypoˇcty

vyhlazov´ an´ı jako napˇr. technika uveden´a v ˇc´asti 3.1.3. Tyto techniky jsou velmi podobn´e a maj´ı stejn´e teoretick´e v´ ychodisko v odˇsumov´an´ı 2D obrazu. Technika viz 3.1.3 je vˇsak v principu iterativn´ı (byt’ iterac´ı je zapotˇreb´ı pouze mal´e mnoˇzstv´ı), kdeˇzto technika pˇredstaven´ a v [JODD03] je jiˇz v n´avrhu konstruov´ana jako pouze jednopr˚ uchodov´a. Aby bylo jiˇz pˇri jedin´em pr˚ uchodu dosaˇzeno poˇzadovan´eho efektu, mus´ı technika obsahovat sofistikovan´e n´ astroje, jeˇz urˇc´ı novou polohu bodu ve vyhlazen´e povrchov´e s´ıti. [JODD03] stav´ı na vyuˇzit´ı: • robustn´ı statistiky ve formˇe gaussovsk´e funkce • lok´ aln´ıho prediktoru povrchu vych´azej´ıc´ıho z pr˚ umˇetu zkouman´eho bodu do teˇcn´ ych rovin sv´eho sousedstv´ı. −x2

S pomoc´ı gaussovsk´e funkce W (x) = e 2σ2 je ve v´ ypoˇctu vˇernˇeji ohodnocen vliv bl´ızk´ ych a vzd´ alen´ ych sousedn´ıch vrchol˚ u na novou pozici zkouman´eho vrcholu, zejm´ena v porovn´ an´ı s line´ arn´ımi ˇci kvadratick´ ymi funkcemi (nejmenˇs´ı ˇctverce). Je j´ı vyuˇz´ıv´ano jak pro stanoven´ı prostorov´ ych vah Wc , tak i pro stanoven´ı u ´ˇcinnostn´ıch (influence) vah Ws . Jejich v´ yznam, pouˇzit´ı a nastaven´ı parametr˚ u σ m´a stejn´ y v´ yznam jako u iteraˇcn´ı metody bilater´ aln´ıho vyhlazov´ an´ı v ˇc´ asti 3.1.3. V´ ysledn´ a nov´ a pozice vrcholu je pak poˇc´ıt´ana jako v´aˇzen´ y pr˚ umˇer vˇsech sv´ ych prediktor˚ u. V´ahy pak, jako u iterativn´ı verze bilater´aln´ıho vyhlazov´an´ı, zohledˇ nuj´ı dvˇe hlediska prostorov´e a u ´ˇcinnostn´ı (influence, similarity). Prostorov´e v´ ahy Wc maj´ı opˇet stejn´ y v´ yznam jako v ˇc´asti 3.1.3, kde vzd´alen´ ym vrchol˚ um ´ ze sousedstv´ı pˇriˇrazuj´ı podstatnˇe menˇs´ı v´ahy, neˇz vrchol˚ um z tˇesn´e bl´ızkosti. Uˇcinnostn´ı v´ahy Ws maj´ı vˇsak konstrukci promˇenn´e odliˇsnou. Zat´ımco v ˇc´asti 3.1.3 jsou do n´ı dosazov´ any v´ yˇsky poˇc´ıtan´e jako pr˚ umˇety sousedn´ıch vrchol˚ u na teˇcnou rovinu zkouman´eho bodu, v pˇr´ıpadˇe techniky dle [JODD03] jsou dosazov´any v´ yˇsky vych´azej´ıc´ı z pr˚ umˇetu zkouman´eho bodu do teˇcn´ ych rovin sv´eho sousedstv´ı (viz Obr´azek 6). Efektem je pak omezen´ı vlivu vrchol˚ u s velkou vzd´alenost´ı mezi zkouman´ ym bodem p a jeho prediktorem Πq (p) , kter´e signalizuj´ı moˇznou hranici d˚ uleˇzit´ ych rys˚ u (napˇr. hran, roh˚ u).

15

Obr´ azek 6: Prediktor Πq (p) - pr˚ umˇet bodu p na teˇcnou rovinu q. Zdroj: [JODD03]

V´ ysledn´ y vzorec z [JODD03] po dosazen´ı a sjednocen´ı znaˇcen´ı promˇenn´ ych m´a pak tvar: vi0

P

=

· Wc (kcj − vi k) · Ws (kΠj (vi ) − vi k) · Πj (vi ) j∈i∗ Aj · Wc (kcj − vi k) · Ws (kΠj (vi ) − vi k)

j∈i∗ Aj

P

(28)

kde Aj je dodatkov´ a v´ aha dle plochy troj´ uheln´ıku qj , kcj − vi k je euklidovsk´a vzd´alenost mezi zkouman´ ym vrcholem vi a centroidem cj sousedn´ıho troj´ uheln´ıku qj , prediktor Πj (vi ) je pr˚ umˇet vrcholu vi na teˇcnou rovinu troj´ uheln´ıku qj a Wc a Ws jsou v´ahov´e funkce zmiˇ novan´e v´ yˇse. V [JODD03] je d´ ale upozorˇ nov´ ano na pˇr´ıpady velmi zaˇsumˇen´ ych norm´al, kter´e pak mohou v´ yraznˇe ovlivnit kvalitu prediktor˚ u, kter´e z norm´al (resp. jimi urˇcen´ ych teˇcn´ ych rovin) vych´azej´ı. Jako ˇreˇsen´ı navrhuje [JODD03] pˇred samotn´ ym v´ ypoˇctem vyhladit norm´ aly samostatnˇe na b´ azi z´ akladn´ıho laplaci´ansk´eho vyhlazov´an´ı (avˇsak bez pˇrem´ıstˇen´ı vrchol˚ u) a teprve pot´e pouˇz´ıt v´ yˇse zmiˇ novanou techniku. 3.2.2

Glob´ aln´ı laplaci´ ansk´ e vyhlazov´ an´ı (GLS)

Pˇri laplaci´ ansk´em vyhlazov´ an´ı z ˇc´asti 3.1.2 doch´az´ı k lok´aln´ımu aplikov´an´ı pˇr´ısluˇsn´eho Laplacian oper´ atoru na jednotliv´e vrcholy a n´aslednˇe se cel´ y proces iterativnˇe opakuje aˇz do dosaˇzen´ı poˇzadovan´eho efektu. Glob´aln´ı laplaci´ansk´e vyhlazov´an´ı vˇsak pohl´ıˇz´ı na vyhlazovac´ı proces jako na celistvou operaci nad celou povrchovou s´ıt´ı. Touto technikou se zab´ yv´ a napˇr. [LIU05], [LIU07] ˇci [NEAL06]. Pˇristupuj´ı k vyhlazov´an´ı jako k hled´ an´ı aproximovan´eho povrchu minimalizac´ı celkov´e energie pˇresunu. Laplacian oper´ ator ∆vi je v [NEAL06] i [LIU07] vyj´adˇren obdobnˇe jako v rovnici 4, tzn. ∆vi =

X

wij (vj − vi ) = {

X

wij vj } − vi , nebo maticovˇe ∆v = LV

(29)

j∈i∗

j∈i∗

kde V je vektor s hodnotami jednotliv´ ych vrchol˚ u V = [v1 , v2 , ...vn ]T a L je matice s pˇr´ısluˇsn´ ymi v´ ahami takov´ a, ˇze

Lij =

   −1

pro i = j pro j ∈ i∗ jinak

wij   0

(30)

Rovnˇeˇz r˚ uzn´e druhy vah zmiˇ novan´ ych napˇr. v ˇc´asti 3.1.2 jsou poplatn´e i pro GLS. [NEAL06] uv´ ad´ı vhodnost r˚ uzn´ ych druh˚ u vah z hlediska c´ılov´eho efektu, kdy pro u ´ˇcely vyhlazov´ an´ı vyuˇz´ıv´ a nejˇcastˇeji v´ahy kotangentov´e, pˇri jejichˇz pouˇzit´ı, jak uv´ ad´ı [NEAL06], pˇredstavuje laplacian oper´ator dobrou aproximaci norm´al povrchu. Kromˇe nich vyuˇz´ıv´ a i v´ ahy zaloˇzen´e na hodnotˇe pr˚ umˇern´eho zakˇriven´ı povrchu v dan´em bodˇe, kter´e z kotangentov´ ych vah vych´ azej´ı.

16

V´ yˇse zm´ınˇen´e vztahy jsou vˇzdy vyj´adˇreny pro jednu dimenzi prostoru, resp. pˇri v´ ypoˇctu jsou souˇradnice pro osy x, y, z kaˇzd´eho vrcholu poˇc´ıt´any zvl´aˇst’. Z´akladn´ı myˇslenka pro vyuˇzit´ı glob´aln´ı techniky minimalizuj´ıc´ı energii vych´ az´ı z pozorov´ an´ı, ˇze u vyhlazen´ ych (nezaˇsumˇen´ ych) povrch˚ u dosahuje velikost Laplacian oper´atoru velmi n´ızk´ ych hodnot ([NEAL06]). To vede ke vztahu, ˇze v ide´aln´ım pˇr´ıpadˇe vyhlazen´eho povrchu by mˇelo platit: ∆vi = 0, resp. glob´alnˇe nad vˇsemi vrcholy ∆v0 = LV0 = 0

(31)

Z tohoto vztahu je pak formulov´an minimalizaˇcn´ı probl´em, jehoˇz ˇreˇsen´ım je nov´ a optimalizovan´ a povrchov´ a s´ıt’. Jeho tvar je: 

 2

min kLV0 k +

X

2 wk2 |vk0 − vk | 

(32)

k∈C

kde v 0 jsou vrcholy na budouc´ı nov´e vyhlazen´e povrchov´e s´ıti, C je podmnoˇzina vrchol˚ u C ⊂ V urˇcen´ a pro ukotven´ı (z d˚ uvodu zabr´anˇen´ı deformaci a vyhlazen´ı rys˚ u v m´ıstˇe tohoto vrcholu) a wk je v´ ahov´e ohodnocen´ı. Vrcholy s omezuj´ıc´ımi podm´ınkami zabraˇ nuj´ı v dan´em vrcholu neˇz´ adouc´ımu pohybu, a t´ım chr´an´ı napˇr. rysy modelu ˇci omezuj´ı pˇr´ıliˇsn´e neˇz´adouc´ı smrˇstˇen´ı. Prvn´ı ˇc´ ast minimalizovan´eho v´ yrazu tedy pˇredstavuje velikost chyby Laplacian oper´atoru, druh´a ˇc´ ast pak pˇredstavuje velikost chyby ukotven´ı (omezen´ı u rys˚ u charakteristick´eho vrcholu). [NEAL06] i [LIU07] pak ukazuj´ı, ˇze tuto u ´lohu lze doplnit jeˇstˇe o dalˇs´ı minimalizaci dalˇs´ıch omezen´ı s ohledem na poˇzadovan´e vlastnosti s´ıtˇe. [NEAL06] i [LIU07] pak ˇreˇs´ı u ´lohu ve smyslu metody nejmenˇs´ıch ˇctverc˚ u, coˇz vede na 0 ˇreˇsen´ı syst´emu line´ arn´ıch rovnic AX = b, resp. konkr´etnˇe po dosazen´ı za A a b: "

L Im×m |0

#

" 0

V =

0 V(1...m)

#

(33)

kde Im×m |0 je speci´ aln´ı podmatice s jednotkov´ ymi prvky na pozic´ıch toho vrcholu, kter´eho se t´ yk´ a omezuj´ıc´ı podm´ınka, V(1...m) jsou hodnoty odpov´ıdaj´ıc´ıch vrchol˚ u a L je v´ahov´ a matice viz vztah (30). Jelikoˇz v´ yˇse zm´ınˇen´e vztahy jsou vˇzdy br´any jen z pozice jedn´e dimenze prostoru, pˇri fin´aln´ım v´ ypoˇctu je tˇreba je zahrnout vˇsechny. [LIU07] pak uspoˇr´ad´av´a cel´ y syst´em n´asledovnˇe:      V0x bx Ax 0 0      0   V0y  =  by  (34)  0 Ay 0 0 0 Az bz Vz kdy obsahy matic Ax,y,z a vektoru bx,y,z odpov´ıdaj´ı obsahu pˇr´ısluˇsn´ ych prvk˚ u ze vztahu (33). N´aslednˇe je pak nutn´e cel´ y syst´em line´arn´ıch rovnic vyˇreˇsit, a z´ıskat tak nov´e rozm´ıstˇen´ı vrchol˚ u. Z hlediska v´ ypoˇcetn´ıho ˇcasu pak velmi z´aleˇz´ı, jak´ y numerick´ y apar´at je pro v´ ypoˇcet pouˇzit, zejm´ena s ohledem na znaˇcnou ˇr´ıdkost matice L. Tato optimalizace vˇsak pˇresahuje r´ amec t´eto pr´ ace. V´ yˇse zmiˇ novan´e vrcholy s omezuj´ıc´ımi podm´ınkami vˇsak tvoˇr´ı jen podmnoˇzinu z celkov´eho poˇctu vrchol˚ u a typicky jsou urˇcov´any interaktivnˇe uˇzivatelem, coˇz vˇsak nen´ı vˇzdy vhodn´e, ˇci v˚ ubec moˇzn´e. Tuto nev´ yhodu ˇreˇs´ı [NEAL06] tak, ˇze omezuj´ıc´ı podm´ınky jsou aplikov´any na u ´plnˇe vˇsechny vrcholy s t´ım, ˇze do tˇechto podm´ınek jsou zabudov´any v´ahov´a ohodnocen´ı 17

jejich vlivu, tzv. poziˇcn´ı WP a laplaci´ansk´e v´ahy WL . Modifikovan´a rovnice (33) m´a pak tvar: # " # " WL L 0 0 (35) V = WP WP V0 Pro v´ ysledn´ y efekt je pak d˚ uleˇzit´a spr´avn´a volba v´ yˇse zm´ınˇen´ ych vah WP a WL , kdy, jak uv´ ad´ı [NEAL06], ”vˇetˇs´ı hodnoty vah WP posiluj´ı poziˇcn´ı omezen´ı, a proto zachov´avaj´ı origin´ aln´ı geometrii, coˇz m˚ uˇze b´ yt uˇziteˇcn´e v oblastech s vysok´ ym zakˇriven´ım a ostr´ ymi rysy”. V´ ahy WL pak slouˇz´ı k zd˚ uraznˇen´ı nebo potlaˇcen´ı vlivu L, a m˚ uˇze tak b´ yt vyuˇzito k pos´ılen´ı zachov´ an´ı charakteristick´ ych rys˚ u. [NEAL06] pak d´ale diskutuje r˚ uzn´e moˇznosti pˇri volbˇe obou vah, kdy u poziˇcn´ıch vah WP uvaˇzuje napˇr. o pevn´ ych konstantn´ıch vah´ ach ˇci o r˚ uzn´ ych funkc´ıch vych´ azej´ıc´ı z hodnot pr˚ umˇern´eho zakˇriven´ı, ˇci o vyuˇz´ıv´an´ı gaussovsk´e funkce u vah WL . Pro objekty s plynul´ ymi zmˇenami hodnot pr˚ umˇern´eho zakˇriven´ı (typicky pˇr´ırodn´ı a obl´e objekty, jejichˇz v´ yskyt je v medic´ınsk´em kontextu pˇrevaˇzuj´ıc´ı) pak doporuˇcuje pro v´ ahy WP vyuˇzit´ı normalizovan´e kumulativn´ı funkce hodnot pr˚ umˇern´eho zakˇriven´ı (cumulative densiti function - cdf), coˇz vede mj. k dobr´emu zachov´an´ı detail˚ u v oblastech s vysok´ ymi hodnotami zakˇriven´ı. 3.2.3

Vyhlazov´ an´ı zjemˇ nov´ an´ım povrchov´ e s´ıtˇ e

Pˇredchoz´ı techniky spoˇc´ıvaly v manipulaci s vrcholy povrchov´e s´ıtˇe v rozsahu, jak je obsahuje zdrojov´ y model. Je-li vˇsak hustota vrchol˚ u povrchov´e s´ıtˇe n´ızk´a, zmiˇ novan´e ˇ sen´ım proto b´ techniky nemus´ı b´ yt dostateˇcnˇe u ´ˇcinn´e. Reˇ yv´a dalˇs´ı zjemnˇen´ı povrchov´e s´ıtˇe pˇrid´ an´ım vrchol˚ u a rozdˇelen´ım st´avaj´ıc´ıch ploch, ze kter´ ych je povrchov´ y model tvoˇren, na v´ıce menˇs´ıch. Pˇri tomto procesu jsou vyuˇz´ıv´any nejr˚ uznˇejˇs´ı algoritmy snaˇz´ıc´ı se z´aroveˇ n o optimalizaci novˇe vznikl´ ych ploch (typicky troj´ uheln´ık˚ u) podle zadan´ ych krit´eri´ı, tzv. fairing“ (minimalizace pˇr´ıliˇs ostr´ ych u ´hl˚ u, rovnostrannost troj´ uheln´ık˚ u, zachov´ an´ı ” pr˚ ubˇehu zakˇriven´ı atd.). Vyhlazovac´ı efekt pak m˚ uˇze b´ yt zp˚ usoben: • samostatn´ ym vyhlazovac´ım krokem aplikovan´ ym na novou s´ıt’ za pouˇzit´ı nˇekter´e z pˇredchoz´ıch vyhlazovac´ıch metod, • zakomponov´ an´ım do samotn´eho zjemˇ novac´ıho algoritmu, napˇr. formou omezuj´ıc´ıch podm´ınek, napˇr. zohlednˇen´ım parametr˚ u zakˇriven´ı v dan´ ych vrcholech apod. Tˇechto algoritm˚ u existuje cel´ a ˇrada a jsou mimo rozsah t´eto pr´ace. Ne vˇzdy je vˇsak ˇz´adouc´ı, aby v´ ystupn´ı povrchov´a s´ıt’ mˇela v´ yraznˇe vyˇsˇs´ı poˇcet vrchol˚ u a troj´ uheln´ık˚ u, napˇr. z d˚ uvodu n´ aroˇcnosti n´ asledn´eho zpracov´an´ı. Z tohoto pohledu hybridn´ı pˇr´ıstup je zm´ınˇen napˇr. v [XXWT06], kde vstupn´ı povrchov´a s´ıt’ je adaptivnˇe zjemnˇena (na z´akladˇe detekce hran a rys˚ u), tato pak n´aslednˇe vyhlazena pˇr´ısluˇsn´ ym vyhlazovac´ım algoritmem a v posledn´ım kroku je nakonec zpˇetnˇe obnoveno rozliˇsen´ı s´ıtˇe na p˚ uvodn´ı rozsah.

4

Doplˇ nkov´ e techniky pro zachov´ an´ı objemu

Vyhlazovac´ı metody zm´ınˇen´e v kapitole 3 prim´arnˇe nec´ıl´ı na zachov´av´an´ı objemu. Jako doplnˇek k tˇemto klasick´ ym vyhlazovac´ım metod´am existuj´ı techniky, kter´e p˚ uvodn´ı dok´ aˇz´ı zachovat ˇci obnovit.

18

4.1

Inflataˇ cn´ı metoda

Inflataˇcn´ı metoda je z tˇech, kter´e objem obnovuj´ı dodateˇcnˇe pot´e, co je aplikov´ano z´akladn´ı vyhlazov´ an´ı. Jej´ı popis zmiˇ nuje napˇr.[DES99]. Princip spoˇc´ıv´a v tom, ˇze kaˇzd´ y bod je posunut ve sv´ ych souˇradnic´ıch oproti vybran´emu bodu (poˇc´atek souˇradn´eho syst´emu, centroid atd.) dle jednotn´eho koeficientu. Koeficient vych´az´ı z pomˇeru objem˚ u pˇred a po aplikaci vyhlazen´ı, konkr´etnˇe je d´an vztahem [DES99]: s

β=

3

objempred objempo

(36)

Pro zamezen´ı zmˇeny pozice tˇelesa v prostoru je posun vrcholu v typicky vztahov´ an centroidu tˇelesa c. V´ ysledn´ a nov´a pozice vrcholu je potom d´ana: v0 = β(v − c) + c

(37)

T´ımto zp˚ usobem dojde k ”nafouknut´ı” objemu v poˇzadovan´em pomˇeru. Jelikoˇz se posunut´ı t´ yk´a vˇsech bod˚ u stejnˇe, jsou v pˇr´ısluˇsn´em pomˇeru vyzdviˇzeny i hodnoty pˇr´ıpadn´eho ˇsumu (jsou zes´ıleny vˇsechny frekvence sign´alu). Proto je vhodn´e co nejv´ıce ˇsumov´ ych frekvenc´ı eliminovat jeˇstˇe pˇred aplikac´ı t´eto techniky.

4.2

Single-point relaxaˇ cn´ı metoda

Technikami zachov´ an´ı objemu se zaob´ır´a napˇr. i [KUPR01]. Princip t´eto metody spoˇc´ıv´ a v korekci vyhlazovac´ıho kroku v norm´alov´em smˇeru a pˇr´ısluˇsn´e velikosti. Tzn., ˇze zvolen´ y vyhlazovac´ı oper´ ator ∆vvyhl je nav´ıc korigov´an dalˇs´ım vektorem s norm´alov´ ym smˇerem a velikost´ı h. Pˇrid´an´ı korekce je nez´ avisl´e na pouˇzit´e vyhlazovac´ı technice, pro korekci je d˚ uleˇzit´ y pouze vektor ∆v dan´ y pˇr´ısluˇsn´ ym vyhlazovac´ım algoritmem a norm´alov´ y vektor nevyhlazen´e s´ıtˇe n v dan´em bodˇe. V´ ysledn´ y oper´ ator posunu ∆vf inal (tedy nejen laplacian oper´ator) je konstruov´an ve smyslu [KUPR01] jako: ∆vf inal = ∆vvyhl + hn (38) Aby z˚ ustal dodrˇzen objem, odvozuje [KUPR01] pro korekˇcn´ı krok hn v´ ysledn´ y vztah: hn = −(∆vvyhl · n)n

(39)

V´ yznamn´ ym nedostatkem t´eto metody je vˇsak pr´avˇe korekˇcn´ı smˇer, nebot’ v jeho smˇeru k vyhlazen´ı nedojde. Dalˇs´ı probl´em nast´av´a v situac´ıch s velmi protich˚ udn´ ymi charakterem zakˇriven´ı mezi sousedn´ımi vrcholy. [KUPR01] tento jev ilustruje na 2D pˇr´ıkladu hvˇezdicov´eho u ´tvaru, kdy je tento algoritmus z pohledu vyhlazov´an´ı v norm´alov´em smˇeru zcela ne´ uˇcinn´ y.

4.3

Single-edge relaxaˇ cn´ı metoda

Vzhledem k nedostatk˚ um singl-point metody (viz 4.2) pˇredstavuje [KUPR01] techniku, u kter´e se korekˇcn´ı krok zmˇeny objemu nestanovuje pˇri pohybu jednoho bodu, n´ ybrˇz dvou sousedn´ıch. Uvolnˇena k pohybu je tedy cel´a jedna hrana. Pˇri v´ ypoˇctu korekˇcn´ıho kroku je nutn´e zohlednit to, ˇze na zmˇenu objemu nem´a vliv jen bod samotn´ y, ale i ten druh´ y.

19

Z´akladn´ı vztah pro v´ ypoˇcet ∆vf inal , kdy k z´akladn´ımu vyhlazovac´ımu kroku je pˇriˇcten krok korekˇcn´ı v norm´ alov´em smˇeru z˚ ust´av´a stejn´ y jako v rovnici (38). Zmˇenˇeny o spoleˇcnou v´ yˇsku h vˇsak mus´ı b´ yt oba body. [KUPR01] pak odvozuje koneˇcn´e vztahy pro v´ ypoˇcet h a n jako: h=−

∆v1vyhl · A1 + ∆v2vyhl · A2 + ∆v2vyhl · E × v1vyhl n · (A1 + A2 + E × (∆v1vyhl − ∆v2vyhl ))

a n=

(j) (j+1) (j) , i = 1, 2, kde ei je hranov´ y j∈i∗ ei ×ei (n2 ) (2) (2) (n1 ) vj a kde E = e2 − e2 = e1 − e1 .

kde Ai = vrcholu

A1 + A2 + E × (∆v1vyhl − ∆v2vyhl ) kA1 + A2 + E × (∆v1vyhl − ∆v2vyhl )k

P

(40)

(41)

vektor z vrcholu vi do sousedn´ıho

T´ımto dojde k pˇrizp˚ usoben´ı d´elky hrany x1 x2 tak, aby objem z˚ ustal zachov´an.

4.4

Objemov´ e omezen´ı minimalizaˇ cn´ıch rovnic u glob´ aln´ıch technik

U glob´ aln´ıch vyhlazovac´ıch metod zaloˇzen´ ych na minimalizaˇcn´ı u ´loze zmˇeny celkov´e energie lze zachov´ an´ı objemu ˇreˇsit t´ım, ˇze do minimalizaˇcn´ı rovnice (viz vztah (32)) je pˇrid´ana podm´ınka, aby v´ ysledn´a zmˇena objemu byla nulov´a. Podm´ınka je do rovnice zaˇrazena jako tzv. hard constraint, tj. takov´a, kter´a mus´ı b´ yt vˇzdy splnˇena pˇresnˇe. Podm´ınkou tedy je, aby objem zmˇenˇen´e s´ıtˇe byl shodn´ y s objemem s´ıtˇe p˚ uvodn´ı. Vyj´adˇreno vzorcem [HUANG]:   

1X (vi × vj ) · vk  − V0 = 0 6T

(42)

ijk

kde Tijk je mnoˇzina vˇsech troj´ uheln´ık˚ u s´ıtˇe s vrcholy vi , vj , vk a V0 je objem p˚ uvodn´ı s´ıtˇe. Probl´emem pˇri pˇrid´ an´ı t´eto podm´ınky je, ˇze nen´ı line´arn´ı a pro ˇreˇsen´ı soustavy rovnic je pak zapotˇreb´ı sofistikovan´eho pˇr´ıstupu (linearizace, Lagrangeovi multiplik´atory).

5

Zp˚ usob porovn´ av´ an´ı vybran´ ych vyhlazovac´ıch metod

Aby mohlo doj´ıt k porovn´ an´ı nˇekolika odliˇsn´ ych vyhlazovac´ıch technik, je nutn´e stanovit jednoznaˇcn´ a krit´eria a zp˚ usoby hodnocen´ı. Pro jednoznaˇcn´e posouzen´ı vyhlazovac´ı metody neexistuje ˇz´ adn´ y univerz´ aln´ı ukazatel a rovnˇeˇz data, na kter´a jsou metody aplikov´any, jsou r˚ uzn´eho charakteru. Pro v´ ysledek porovn´an´ı je tud´ıˇz d˚ uleˇzit´a volba: • vhodn´ ych referenˇcn´ıch model˚ u povrchov´ ych s´ıt´ı • vhodn´ ych hodnot´ıc´ıch krit´eri´ı a porovn´avac´ıch metrik.

5.1

Volba referenˇ cn´ıch 3D model˚ u

Referenˇcn´ı modely mus´ı b´ yt vyb´ır´any tak, aby splˇ novaly vˇsechny poˇzadovan´e parametry a podm´ınky. Pro u ´ˇcely porovn´ av´an´ı je vhodn´e m´ıt k dispozici takov´e, u kter´ ych m˚ uˇzeme ovˇeˇrit pˇresn´e v´ ysledky napˇr. analytick´ ym v´ ypoˇctem ˇci laboratorn´ım mˇeˇren´ım. Z´aroveˇ n je vhodn´e ovˇeˇrit techniky na re´ aln´ ych datech, tzn. na modelech, na kter´ ych by vybran´e techniky mˇely b´ yt vyuˇzity v aplikaˇcn´ı praxi. Jakoˇzto re´aln´e referenˇcn´ı modely by pak tyto mˇely obsahovat typick´e neˇz´ adouc´ı jevy (ˇspatn´ y tvar troj´ uheln´ık˚ u, ˇsum, d´ıry atd.). 20

Pro volbu model˚ u v obou skupin´ach je d˚ uleˇzit´a i podm´ınka, ˇze 3D povrchov´a s´ıt’ mus´ı b´ yt uzavˇren´ a, resp. m´ıt uzavˇren´ y objem. Ten je pak moˇzn´e snadno a pˇresnˇe spoˇc´ıtat pomoc´ı dostupn´ ych algoritm˚ u (viz ˇc´ ast 5.2.2).

5.2

Hodnot´ıc´ı krit´ eria pro porovn´ av´ an´ı

Vyhodnocen´ı u ´spˇeˇsnosti jednotliv´ ych vyhlazovac´ıch technik nen´ı pˇr´ımoˇcar´e, nebot’ neexistuje jednoznaˇcn´ y univerz´ aln´ı ukazatel ˇci metrika, kter´a by vypov´ıdala o kvalitˇe dan´e metody. Na u ´spˇeˇsnost vyhlazovac´ıch technik lze nahl´ıˇzet z r˚ uzn´ ych u ´hl˚ u pohledu s ohledem na u ´ˇcel a zp˚ usob jejich dalˇs´ıho zpracov´an´ı. Pro nˇekter´e aplikace je z´asadn´ı kvalita v´ ysledn´ ych troj´ uheln´ık˚ u, pro jin´e zachov´an´ı detail˚ u, objemu ˇci pouze jen akceptovateln´ a vizu´aln´ı str´ anka. V principu se pˇredpokl´ ad´ a, ˇze pokud si jsou dvˇe vyhlazovac´ı metody v nˇekter´em ohledu ve v´ ysledc´ıch velice bl´ızk´e, neznamen´a to zcela odliˇsn´e v´ ysledky z pohledu krit´eria jin´eho. Zejm´ena s iteraˇcn´ımi metodami (ale i neiteraˇcn´ımi s voliteln´ ymi parametry) je d´ ale spojen probl´em jejich konvergence s rostouc´ım poˇctem iterac´ı, resp. s probl´emem tzv. oversmoothingu, kdy je model vyhlazen v´ıce, neˇz je ˇz´adouc´ı stav. Definice ˇz´adouc´ıho stavu (tzv. ”stop” krit´erium) rovnˇeˇz nen´ı jednoznaˇcnˇe stanovena a b´ yv´a ˇcasto urˇcov´ana subjektivnˇe vizu´ alnˇe, ˇci kvantifikov´ana s pomoc´ı nˇekter´e vybran´e metriky (ˇci nˇekolika metrik), v z´ avislosti na u ´ˇcelu vyuˇzit´ı. Pro u ´ˇcely t´eto pr´ ace je jako z´ akladn´ı ”stop” krit´erium zvoleno hledisko vizu´aln´ı. D´ale je tak´e zapotˇreb´ı db´ at, aby nedoˇslo k velk´emu objemov´emu zkreslen´ı, aby z˚ ustaly zachov´any relevantn´ı detaily a rysy, ale z´ aroveˇ n aby doˇslo k zahlazen´ı neˇz´adouc´ıch jev˚ u vznikl´ ych pˇri procesu z´ısk´ an´ı modelu. Hledisko zachov´an´ı charakteristick´ ych rys˚ u a podstatn´ ych detail˚ u (hran, roh˚ u atd.), stejnˇe tak jako hledisko zachov´an´ı objemu (a proporc´ı), je tedy z hlediska biomedic´ınsk´eho pouˇzit´ı rovnˇeˇz v´ yznamn´e. 5.2.1

Vizu´ aln´ı hodnocen´ı

Aˇckoliv se v pˇr´ıpadˇe vizu´ aln´ıho posouzen´ı jedn´a o hledisko uˇzivatelsky subjektivn´ı, jedn´ a se o hledisko kl´ıˇcov´e. Mohou totiˇz nastat pˇr´ıpady, kdy napˇr. metoda m˚ uˇze zaˇsumˇenou krychli vyhladit do podoby ide´ aln´ı koule s dobrou kvalitou troj´ uheln´ık˚ u, pˇriˇcemˇz objem z˚ ustane plnˇe zachov´ an. Transformace z krychle na kouli vˇsak nen´ı pˇrijateln´ y v´ ysledek, coˇz vˇsak jin´e d´ ale uveden´e nesubjektivn´ı ukazatele neodhal´ı. Pˇri porovn´ av´ an´ı jednotliv´ ych vyhlazovac´ıch pˇr´ıstup˚ u slouˇz´ı vizu´aln´ı posouzen´ı v´ ysledku zejm´ena k urˇcen´ı takov´ ych nastaven´ı jednotliv´ ych metod (poˇcet iterac´ı, volba parametr˚ u atd.), kter´e produkuj´ı v´ ysledky, jenˇz jsou z hlediska dalˇs´ıho pouˇzit´ı a zkoum´ an´ı akceptovateln´e. Vizu´ aln´ı posouzen´ı tedy slouˇz´ı k z´akladn´ı uˇzivatelsk´e eliminaci pˇr´ıpad˚ u nedostateˇcn´eho ˇci naopak nadmˇern´eho vyhlazen´ı. Lidsk´e vizu´aln´ı vn´ım´an´ı 3D tvar˚ u m´ a vˇsak sv´ a omezen´ı, kdy dva modely mohou b´ yt vizu´alnˇe hodnoceny obdobnˇe, avˇsak ostatn´ı jejich parametry mohou b´ yt diametr´alnˇe odliˇsn´e (objem, kvalita troj´ uheln´ık˚ u atd.). A k n´ asledn´emu rozsouzen´ı pak slouˇz´ı dalˇs´ı objektivn´ı ukazatele (viz n´asleduj´ıc´ı kapitoly). V´ yznamn´ y nedostatek vizu´ aln´ıho pˇr´ıstupu spoˇc´ıv´a v subjektivitˇe posuzovatele. Je proto nanejv´ yˇs ˇz´ adouc´ı, aby si osoba posuzovatele byla vˇedoma r˚ uzn´ ych moˇznost´ı v´ yskytu nedostatk˚ u, umˇela je rozpoznat, popˇr. pˇredv´ıdat a soustˇredit se na oblasti s nejpravdˇepodobnˇejˇs´ım m´ıstem jejich vzniku.

21

5.2.2

Metrika zmˇ eny celkov´ eho objemu tˇ elesa

Mnoh´e v´ yzkumy v oblasti vyhlazovac´ıch algoritm˚ u se soustˇred’uj´ı zejm´ena na schopnost algoritmu detekovat a zachovat hrany, rohy a jin´e charakteristick´e rysy modelu. Mnohem menˇs´ı pozornost se pak soustˇred’uje na zachov´an´ı objemu v´ ysledn´eho vyhlazen´eho modelu, k jehoˇz zmˇen´ am v d˚ usledku jejich aplikov´an´ı doch´az´ı. V kontextu biomedic´ınsk´ ych aplikac´ı se vˇsak jedn´ a o nezanedbateln´ y aspekt, nebot’ velikost modelovan´eho org´anu b´ yv´a, napˇr. z hlediska diagnostiky, ˇcasto z´asadn´ı (jedn´ım z pˇr´ıznak˚ u nemoci, klasifikace n´ador˚ u, zachov´ an´ı prostorov´ ych vztah˚ u atd.). Vzhledem k tomu pˇredstavuje parametr zachov´av´ an´ı objemu prim´ arn´ı oblast z´ ajmu pˇri porovn´av´an´ı jednotliv´ ych algoritm˚ u v n´asleduj´ıc´ıch kapitol´ ach. Probl´emem porovn´ av´ an´ı zmˇen objemu vyhlazovan´ ych povrchov´ ych s´ıt´ı je stanoven´ı zdrojov´eho referenˇcn´ıho objemu, kter´ y by ide´alnˇe mˇel odpov´ıdat re´aln´emu objektu. Jiˇz samotn´ a reprezentace troj´ uheln´ıkovou s´ıt´ı pˇredstavuje pouze aproximaci povrchu, a tedy i jej´ı objem je v˚ uˇci re´ aln´emu objemu (ˇci analyticky spoˇc´ıtan´emu) zpravidla odliˇsn´ y. U re´aln´ ych model˚ u z´ıskan´ ych napˇr. ze CT ˇci MRI nen´ı ide´aln´ı analyticky vypoˇc´ıtan´ y objem zjistiteln´ y a z´ıskan´ a troj´ uheln´ıkov´a s´ıt’ m´a zase ve sv´em objemu zapoˇc´ıt´any i vlivy ˇsumu a jin´ ych neˇz´ adouc´ıch jev˚ u. Je-li jako zdrojov´ y referenˇcn´ı objem zvolen objem p˚ uvodn´ı nevyhlazen´e troj´ uheln´ıkov´e s´ıtˇe, nen´ı proto u ´ˇceln´e poˇzadovat od ide´aln´ıho algoritmu striktnˇe zachov´ an´ı pˇresn´e hodnoty objemu jako u zdrojov´eho referenˇcn´ıho modelu. Pˇres vˇsechny tyto nedostatky je d´ale jako referenˇcn´ı objem uvaˇzov´an objem p˚ uvodn´ı nevyhlazen´e troj´ uheln´ıkov´e s´ıtˇe. Pro v´ ypoˇcet z´ akladn´ıho objemu troj´ uheln´ıkov´e s´ıtˇe lze pouˇz´ıt vzorec [VOLU]: Objem =

1 X ((vf 2y − vf 1y )(vf 3z − vf 1z ) − (vf 2z − vf 1z )(vi3y − vf 1y )) · (vf 1x + vf 2x + vf 3x ) 6 f ∈F (43)

Pˇri tomto zp˚ usobu je objem poˇc´ıt´an jako souˇcet objem˚ u ˇctyˇrstˇen˚ u tvoˇren´ ych vrcholy pˇr´ısluˇsn´ ych troj´ uheln´ık˚ u a referenˇcn´ım bodem (zde bod 0). Tento zp˚ usob v´ ypoˇctu vˇsak nepoˇc´ıt´ a s t´ım, ˇze nˇekter´e troj´ uheln´ıky se mohou prot´ınat a kˇr´ıˇzit. V takov´em pˇr´ıpadˇe je v´ ypoˇcet objemu zkreslen o tyto protnut´e ˇc´asti objemu, kter´e jsou zapoˇcteny n´asobnˇe. Tento probl´em nenast´ av´ a pˇri zp˚ usobu v´ ypoˇctu zaloˇzen´em na diskr´etn´ı formˇe divergenˇcn´ıho teor´emu tak, jak je naimplementov´an v r´amci n´astroje VTK. Porovn´an´ı tˇechto dvou zp˚ usob˚ u v´ ypoˇctu pak nav´ıc slouˇz´ı jako pomocn´ y indik´ator existence neˇz´adouc´ıch kˇr´ıˇzen´ ych troj´ uheln´ık˚ u. Pomoc´ı v´ yˇse zm´ınˇen´ ych v´ ypoˇct˚ u je zjiˇst’ov´an objem uzavˇren´e troj´ uheln´ıkov´e s´ıtˇe v jeho absolutn´ıch hodnot´ ach. Pro zajiˇstˇen´ı vz´ajemn´e soumˇeˇritelnosti r˚ uzn´ ych referenˇcn´ıch model˚ u a technik je ˇz´ adouc´ı pouˇzit´ı ukazatel˚ u zmˇeny objemu v procentu´aln´ım vyj´adˇren´ı objempo ) · 100. dle vzorce ( objempred 5.2.3

L2 chybov´ a norma

Pˇri vyhlazov´ an´ı doch´ az´ı ke zmˇen´am dan´e povrchov´e s´ıtˇe. Pro u ´ˇcely numerick´eho porovn´ an´ı 2 p˚ uvodn´ı a novˇe vznikl´e je ˇcasto pouˇz´ıv´an ukazatel pr˚ umˇern´e L chyby. Ta vypov´ıd´ a o pr˚ umˇern´e vzd´ alenosti vyhlazen´e s´ıtˇe od t´e p˚ uvodn´ı. [METRO] ˇci [BEOH03] jej stanovuj´ı jako: v u 1 X u Ev = t Ai∗ · dist(vi0 , M )2 (44) 3AM 0 0 0 vi ∈M

22

kde M a M 0 pˇredstavuj´ı p˚ uvodn´ı a vyhlazenou troj´ uheln´ıkovou s´ıt’, Ai∗ je plocha vˇsech troj´ uheln´ık˚ u pˇril´ehaj´ıc´ıch k vrcholu vi a dist(vi0 , M ) pˇredstavuje nejkratˇs´ı vzd´alenost mezi vrcholem vi0 z vyhlazen´e s´ıtˇe a troj´ uheln´ıkem z p˚ uvodn´ı s´ıtˇe, kter´ y je vrcholu vi0 nejbl´ıˇze. Prost´e zmˇeˇren´ı vzd´ alenost´ı mezi odpov´ıdaj´ıc´ımi si p˚ uvodn´ımi a nov´ ymi vrcholy nelze pouˇz´ıt, protoˇze napˇr. leˇz´ı-li vrcholy na jedn´e rovinn´e ploˇse, m˚ uˇze vlivem vyhlazovac´ıho posunu doj´ıt k v´ yznamn´ ym zmˇen´am v jejich pozic´ıch, pˇrestoˇze tuto plochu neopustily. Ukazatel vzd´ alenost´ı zmˇen polohy by tud´ıˇz nab´ yval nezanedbateln´ ych hodnot, aniˇz by se zmˇenila podstata pˇredmˇetu, kterou tyto vrcholy reprezentuj´ı (st´ale stejn´a plocha, jen jinak rozm´ıstˇen´e vrcholy). Z tohoto d˚ uvodu se pouˇz´ıv´a vzd´alenost mezi vrcholem vyhlazen´e s´ıtˇe a nejbliˇzˇs´ım troj´ uheln´ıkem s´ıtˇe p˚ uvodn´ı (viz vztah (44)). Podstatou vyhlazov´ an´ı je pozmˇenˇen´ı povrchov´e s´ıtˇe tak, aby byl odstranˇen ˇsum, artefakty ˇci jin´e neˇz´ adouc´ı jevy, ale aby z´aroveˇ n nedoˇslo k pˇr´ıliˇsn´e deformaci podstaty dan´eho modelu. K urˇcit´e odchylce vzd´alenosti (chybˇe) tedy pˇrirozenˇe doch´az´ı a pˇri ide´aln´ım vyhlazen´ı by mˇela b´ yt u ´mˇern´ a velikosti odbouran´eho ˇsumu. Rostouc´ı tempo zvˇetˇsov´ an´ı pr˚ umˇern´e chyby (ve vztahu k poˇctu iterac´ı ˇci parametrick´ ym krok˚ um u neiteraˇcn´ıch metod) naznaˇcuje, ˇze vyhlazen´ y model se ˇc´ım d´al t´ım v´ıce vzdaluje sv´e pˇredloze, a je to tedy sign´ al k posouzen´ı, zda jiˇz nedoch´ az´ı k tzv. oversmoothingu, tedy pˇr´ıliˇsn´emu vyhlazen´ı. [BEOH03] napˇr. vyuˇz´ıv´ a tento ukazatel (okamˇzik kdy je jeho pˇr´ır˚ ustkov´a hodnota mezi jednotliv´ ymi iteracemi minim´ aln´ı) jako jedno ze ”stop”krit´eri´ı pro stanoven´ı optim´aln´ı u ´rovnˇe vyhlazen´ı. Pˇri vyuˇzit´ı ukazatele L2 pr˚ umˇern´e chyby je vˇzdy nutn´e zohlednit, ˇze jeho hodnoty jsou z´avisl´e na velikosti, resp. mˇeˇr´ıtku dan´eho 3D modelu. 5.2.4

L2 norm´ alov´ a chybov´ a norma

Jako dalˇs´ı n´ astroj pro porovn´ an´ı v´ ysledk˚ u vyhlazovac´ıho procesu vyuˇz´ıv´a [BEOH03] tzv. L2 norm´ alovou chybu. Ta se, narozd´ıl od z´akladn´ıho ukazatele L2 chyby, nevztahuje k pozic´ım jednotliv´ ych vrchol˚ u, n´ ybrˇz ukazuje, jak se zmˇenilo norm´alov´e pole jednotliv´ ych troj´ uheln´ık˚ u. Pro urˇcen´ı L2 norm´ alov´e chyby vyuˇz´ıvaj´ı [BEOH03] vztah: v u u 1 En = t

A

M0

X

At0 · |nt − nt0 |2

(45)

t0 ∈M 0

kde M a M 0 pˇredstavuj´ı p˚ uvodn´ı a vyhlazenou troj´ uheln´ıkovou s´ıt’, At0 je plocha 0 troj´ uheln´ıku t a nt je jednotkov´ y norm´alov´ y vektor k troj´ uheln´ıku t. Troj´ uheln´ık t je pak takov´ y troj´ uheln´ık p˚ uvodn´ı nevyhlazen´e troj´ uheln´ıkov´e s´ıtˇe, kter´ y je nejbl´ıˇze k troj´ uheln´ıku t0 z vyhlazen´e s´ıtˇe. Vypov´ıdac´ı hodnota je obdobn´ a jako u L2 chyby (viz 5.2.3) s t´ım rozd´ılem, ˇze, jak uv´ ad´ı [BEOH03], ”je citliv´ a k degradaci s´ıtˇe v oblasti s ostr´ ymi rysy a ve velmi zakˇriven´ ych oblastech”. Narozd´ıl od L2 chyby nen´ı jeho hodnota z´avisl´a na velikosti, resp. mˇeˇr´ıtku dan´eho modelu. 5.2.5

Hodnota zakˇ riven´ı

Vyhlazovac´ı algoritmy obecnˇe otupuj´ı zakˇriven´e oblasti troj´ uheln´ıkov´e s´ıtˇe, avˇsak nˇekter´e z nich tento efekt u vybran´ ych vrchol˚ u potlaˇcuj´ı, napˇr. z d˚ uvodu zachov´an´ı ostr´ ych hran ˇci rys˚ u. Postupn´ ym vyhlazov´an´ım m´a tedy hodnota pr˚ umˇern´eho zakˇriven´ı klesat. Charakteristick´e rysy a hrany jsou tedy klasifikov´any jako oblasti s vysokou hodnotou 23

ukazatele zakˇriven´ı a je z´ aleˇzitost´ı algoritmu, zda ˇci jak z˚ ustanou zachov´any. Jako n´astroj pro posouzen´ı tohoto aspektu m˚ uˇze slouˇzit napˇr. transformace jednotliv´ ych hodnot do histogramu, ze kter´eho je zˇrejm´e, zda s postupn´ ymi vyhlazovac´ımi kroky plynule kles´ a zakˇriven´ı u vˇsech vrchol˚ u rovnomˇernˇe, ˇci naopak vznikne ostr´a hranice, od kter´e si ˇc´ ast vrchol˚ u ponech´ a sv´ a zakˇriven´ı (nebo bude klesat pomaleji), zat´ımco u ostatn´ıch dojde k jeho plynul´emu poklesu. Histogram vˇsak neud´av´a, ve kter´ ych oblastech se dan´e druhy vrchol˚ u nach´ az´ı (napˇr. pro posouzen´ı, zda se jedn´a opravdu o vrcholy v oblasti s ostr´ ymi hranami ˇci rysy). Toto m˚ uˇze b´ yt ˇreˇseno napˇr. pomoc´ı barevn´eho namapov´an´ı hodnot zakˇriven´ı na dan´ y 3D model. Celkov´ a hodnota zakˇriven´ı v dan´em bodˇe se odv´ıj´ı od hodnot zakˇriven´ı v tzv. hlavn´ıch (”principal”) smˇerech. U hodnoty zakˇriven´ı jsou nejˇcastˇeji uvaˇzov´any dva typy ukazatel˚ u zakˇriven´ı - pr˚ umˇern´ y (H) a Gaussovsk´ y (K). Pr˚ umˇern´ y vyjadˇruje pr˚ umˇernou hodnotu zakˇriven´ı v jednotliv´ ych smˇerech. Hodnoty bl´ızk´e nule pak pˇredstavuj´ı ˇz´adn´e zakˇriven´ı, tzn. body v rovinˇe, hodnoty bl´ızk´e nekoneˇcn˚ um naopak extr´emn´ı zakˇriven´ı. Gaussovsk´ y je pak d´ an souˇcinem hodnot v jednotliv´ ych hlavn´ıch smˇerech. Znam´enka pak urˇcuj´ı charakter zakˇriven´ı (eliptick´ y, hyperbolick´ y ˇci parabolick´ y bod). Pro u ´ˇcely porovn´av´ an´ı vyhlazovac´ıch technik je d˚ uleˇzit´a informace o velikosti zakˇriven´ı, nam´ısto charakteru zakˇriven´ı, a proto je pro u ´ˇcely t´eto pr´ace volen ukazatel pr˚ umˇern´eho zakˇriven´ı. Pro stanoven´ı ˇc´ıseln´e hodnoty zakˇriven´ı existuj´ı r˚ uzn´e v´ ypoˇcetn´ı metody, napˇr. proloˇzen´ı povrchu plochou (paraboloid fitting), jej´ıˇz parametry zakˇriven´ı jsou zn´am´e, vyuˇzit´ı GaussBonnet teor´emu, Taubinova metoda atd. Bliˇzˇs´ı popis a porovn´an´ı r˚ uzn´ ych metod lze nal´ezt napˇr. v [MASORI07]. Vztah pro v´ ypoˇcet pr˚ umˇern´eho zakˇriven´ı ve vrcholu vi dle GaussBonnet sch´ematu uv´ ad´ı [MASORI07] jako: Hi =

1 4

P

j∈i∗ keij kβj 1 3 Ai∗

(46)

kde keij k pˇredstavuje d´elku hrany eij , βj je u ´hel, kter´ y sv´ıraj´ı norm´aly obou troj´ uheln´ık˚ u pˇril´ehaj´ıc´ıch k hranˇe eij a Ai∗ je plocha vˇsech troj´ uheln´ık˚ u pˇril´ehaj´ıc´ıch k vrcholu vi . 5.2.6

Kvalita troj´ uheln´ık˚ u

Pˇri zpracov´ an´ı 3D povrchov´ ych s´ıt´ı hraje v´ yznamnou roli i tzv. kvalita povrchov´e s´ıtˇe, resp. kvalita troj´ uheln´ık˚ u, ze kter´ ych se skl´ad´a. Napˇr. pˇr´ıliˇs u ´zk´e a dlouh´e troj´ uheln´ıky mohou b´ yt limituj´ıc´ı z hlediska pˇresnosti v´ ypoˇct˚ u a pouˇzitelnosti nˇekter´ ych algoritm˚ u. ˇ Z´adouc´ım stavem je tud´ıˇz stav co nejbliˇzˇs´ı parametr˚ um rovnostrann´eho troj´ uheln´ıku. Aˇckoliv zlepˇsov´ an´ı kvality troj´ uheln´ık˚ u nen´ı prim´arn´ım c´ılem vyhlazovac´ıch metod, jejich pouˇzit´ı aspekt kvality povrchov´e s´ıtˇe ovlivˇ nuje, a proto je toto hledisko zohlednˇeno i v n´asleduj´ıc´ım porovn´ av´ an´ı vyhlazovac´ıch technik. K posuzov´ an´ı z tohoto hlediska je moˇzn´e pouˇz´ıt nˇekolik pˇr´ıstup˚ u a ukazatel˚ u. M˚ uˇze j´ım b´ yt napˇr. histogram hodnot jednotliv´ ych u ´hl˚ u, kdy vˇsak z u ´daje o jednom u ´hlu neplynou informace o tˇech ostatn´ıch, a posouzen´ı celkov´e kvality troj´ uheln´ıku je tud´ıˇz problematick´e. Dalˇs´ımi moˇzn´ ymi ukazateli jsou napˇr. pomˇerov´e ukazatele nejdelˇs´ı ku nejkratˇs´ı stranˇe ˇci souˇcet druh´ ych mocnin d´elek stran ku obsahu troj´ uheln´ıku atd. Kromˇe celkov´ ych (pr˚ umˇern´ ych) ukazatel˚ u je d˚ uleˇzit´e sledovat i jejich minim´aln´ı a maxim´aln´ı hodnoty, nebot’ i nˇekolik m´ alo nekvalitn´ıch troj´ uheln´ık˚ u v jinak kvalitn´ı s´ıti m˚ uˇze b´ yt z hlediska aplikace dalˇs´ıch algoritm˚ u v´ yznamnˇe limituj´ıc´ı. Pro celkov´e posouzen´ı kvality troj´ uheln´ıku pouˇz´ıv´a napˇr. [NEAL06] ukazatel tzv. radius ratio, jeˇz vyjadˇruje vztah: rv q =2· (47) ro 24

kde rv je polomˇer kruˇznice troj´ uheln´ıku vepsan´e a ro je polomˇer kruˇznice opsan´e. Z bˇeˇzn´ ych vzorc˚ u pro jejich v´ ypoˇcet lze odvodit, ˇze pro rovnostrann´ y troj´ uheln´ık je polomˇer kruˇznice opsan´e dvojn´ asobn´ y polomˇeru kruˇznice vepsan´e. Naproti tomu u velmi u ´zk´ ych a dlouh´ ych troj´ uheln´ık˚ u s velmi ostr´ ymi u ´hly je tento pomˇer znaˇcn´ y, a tedy v pˇrevr´acen´e hodnotˇe velmi bl´ızk´ y nule. Vztah (47) tedy mapuje ukazatel na interval h0, 1i, kdy hodnota 1 pˇredstavuje dobˇre tvarovan´ y troj´ uheln´ık a 0 nevyhovuj´ıc´ı, degenerovan´ y troj´ uheln´ık. 5.2.7

V´ ypoˇ cetn´ı ˇ cas

Aˇckoliv prim´ arn´ım hlediskem pˇri v´ ybˇeru vyhlazovac´ı metody b´ yv´a hledisko kvalitativn´ı, v r˚ uzn´ ych typech aplikac´ı m˚ uˇze b´ yt kladen i d˚ uraz na rychlost pouˇzit´eho algoritmu (napˇr. interaktivn´ı aplikace), resp. na ˇcas potˇrebn´ y pro dosaˇzen´ı poˇzadovan´e u ´rovnˇe vyhlazen´ı. Pˇri porovn´ av´ an´ı jednotliv´ ych vyhlazovac´ıch technik je vˇsak v´ ypoˇcetn´ı ˇcas pro u ´ˇcely t´eto pr´ace br´ an pouze jako pomocn´ y ˇci orientaˇcn´ı ukazatel, nebot’ pouˇzit´e vyhlazovac´ı filtry, kromˇe z´ akladn´ıho algoritmu, zahrnuj´ı jeˇstˇe dalˇs´ı reˇzii d˚ uleˇzitou napˇr. pro univerz´alnost tˇr´ıdy, zapnut´ı ˇci vypnut´ı doplˇ nkov´ ych funkc´ı, oˇsetˇren´ı regul´ernosti vstupn´ıch dat (oˇsetˇren´ı druhu vstupn´ıch dat, pˇrevod na striktnˇe troj´ uheln´ıkovou s´ıt’, vylouˇcen´ı neplatn´ ych prvk˚ u, vytvoˇren´ı vazeb a struktur potˇrebn´ ych pro dalˇs´ı v´ ypoˇcet atd.). Tato reˇzie je nezanedbateln´ a a pro kaˇzd´ y filtr rozd´ıln´ a v z´ avislosti na jeho implementaci. Filtry vybran´e pro porovn´av´ an´ı jsou pouˇzit´e z ˇc´ asti z VTK (napˇr. vtkWindowedSincPolyDataFilter), z poskytnut´ ych implementac´ı tˇret´ıch stran (vtkOptimizePolydata) ˇci je pouˇzita implementace vlastn´ı. V´ ysledek vyhodnocen´ı jednotliv´ ych metod v programov´e smyˇcce m˚ uˇze b´ yt rovnˇeˇz ovlivnˇen napˇr. memory managementem operaˇcn´ıho syst´emu a je rovnˇeˇz z´avisl´ y na pouˇzit´em hardwaru.

6

Implementace s vyuˇ zit´ım VTK

Pro u ´ˇcely porovn´ an´ı jednotliv´ ych vyhlazovac´ıch metod, vygenerov´an´ı grafick´ ych v´ ystup˚ u a z´apisu v´ ystupn´ıch dat pro jednotliv´e proveden´e pˇr´ıpady jsou vytvoˇreny dva podp˚ urn´e softwarov´e n´ astroje. Prvn´ı n´ astroj slouˇz´ı k hromadn´emu vygenerov´an´ı dat k dan´e vyhlazovac´ı technice. Na vstupn´ı model je ve smyˇcce aplikov´ano vyhlazov´an´ı s nastaven´ ymi parametry (poˇcet iterac´ı) a vypoˇcteny poˇzadovan´e metriky. V kaˇzd´em pr˚ uchodu smyˇckou jsou v´ ysledky z metrik zaps´ any do logovac´ıho souboru a z´aroveˇ n je vygenerov´an obrazov´ y v´ ystup do form´ atu PNG. Tento obr´ azkov´ y soubor pak obsahuje v´ ystupn´ı u ´daje z jednotliv´ ych metrik a obrazy samotn´eho vyhlazen´eho 3D modelu. V´ ystupem z programu je pak ˇrada obr´azk˚ u, kter´ a pˇri proch´ azen´ı plynule zobrazuje v´ yvoj vyhlazov´an´ı dle postupn´ ych iterac´ı (u iteraˇcn´ıch metod). Kaˇzd´ y obr´azek je tedy moˇzn´e kdykoliv porovn´avat s ostatn´ımi a sledovat mezn´ı vlivy mezi jednotliv´ ymi po sobˇe jdouc´ımi obr´azky. Druh´ y n´ astroj slouˇz´ı k jednor´ azov´emu zobrazen´ı konkr´etn´ıho zkouman´eho pˇr´ıpadu na obrazovku s moˇznost´ı interaktivn´ıho prohl´ıˇzen´ı a bliˇzˇs´ıho zkoum´an´ı (napˇr. pˇribl´ıˇzen´ı, natoˇcen´ı atd.). Za bˇehu programu je tedy k dispozici interaktivn´ı okno, po skonˇcen´ı programu je vygenerov´ an textov´ y logovac´ı soubor a obrazov´ y v´ ystup obdobnˇe jako u prvn´ıho n´ astroje. Prim´arn´ım programovac´ım jazykem je jazyk C++, a to zejm´ena kv˚ uli snadn´e pouˇzitelnosti s n´astroji VTK. Implementace obou n´ astroj˚ u je zaloˇzena na vyuˇzit´ı volnˇe dostupn´ ych n´astroj˚ u VTK ”The Visualization Toolkit”. Spr´ avn´ a instalace VTK je z´akladn´ım pˇredpokladem pro pr´aci se 25

zdrojov´ ymi k´ ody pˇriloˇzen´ ymi v r´amci elektronick´ ych pˇr´ıloh.

6.1

VTK - The Visualization Toolkit

VTK (The Visualization Toolkit) je multiplatformn´ı, ”open-source, zdarma dostupn´ y softwarov´ y syst´em pro 3D poˇc´ıtaˇcovou grafiku, zpracov´an´ı obrazu a vizualizaci.”[VTK]. Skl´ad´ a se z rozs´ ahl´e knihovny tˇr´ıd s jednotliv´ ymi algoritmy pro 3D vizualizaci a zpracov´ an´ı obrazu a souvisej´ıc´ıch n´ astroj˚ u. Z´akladn´ı vizualizaˇcn´ı sch´ema VTK je zaloˇzeno na principu tzv. rour, kde figuruj´ı datov´e objekty a procesn´ı objekty (filtry), kter´e jsou pospojov´any tak, aby v´ ystup(y) z jednoho je vstupem do dalˇs´ıho (ˇci dalˇs´ıch). Napˇr´ıklad v z´ akladn´ı podobˇe mohou b´ yt z´ıskan´a tzv. polydata obsahuj´ıc´ı u ´daje 3D modelu pˇred´ana do r˚ uzn´ ych procesn´ıch filtr˚ u (vyhlazen´ı, decimace atd.). N´aslednˇe polydata ˇci pˇrefiltrovan´ a polydata vstupuj´ı do tzv. mapperu, jenˇz rozkl´ad´a polygon´aln´ı data na grafick´ a primitiva k dalˇs´ımu zobrazen´ı. Z mapperu jsou pak data pˇred´ana do tzv. actoru, kter´ y organizuje vykreslov´ an´ı grafick´ ych primitiv z´ıskan´ ych z mapperu (napˇr. barvy, pr˚ uhlednosti atd.). D´ ale data pˇreb´ır´a tzv. renderer, kter´ y se star´a o samotn´e vykreslen´ı s ohledem na viewport. Vˇsechny renderery jsou pak souˇc´ast´ı okna, o jehoˇz ovl´ad´an´ı a reakce se m˚ uˇze starat tzv. interactor nebo m˚ uˇze b´ yt vyexportov´an pomoc´ı nˇejak´eho tzv. outputwriteru. Pro vyhlazov´ an´ı obsahuje VTK dvˇe samostatn´e knihovn´ı tˇr´ıdy: vtkSmoothPolyDataFilter a vtkWindowedSincPolyDataFilter. Prvn´ı z nich implementuje klasick´e nev´ aˇzen´e laplaci´ansk´e vyhlazov´an´ı, umoˇzn ˇuje fixaci hraniˇcn´ıch bod˚ u neuzavˇren´ ych s´ıt´ı a zachov´ an´ı charakteristick´ ych rys˚ u a hran, vych´azej´ıc´ı z prahov´ an´ı u ´hl˚ u sevˇren´ ych hranami. Druh´ a implementuje Taubin˚ uv FIR filtr s Hammingovo okenn´ı funkc´ı.

6.2

Z´ akladn´ı vizualizaˇ cn´ı roura

Oproti v´ yˇse zm´ınˇen´emu pˇr´ıkladu z´akladn´ı vizualizaˇcn´ı roury jsou v rouˇre pouˇzit´e v obou n´astroj´ıch zapojeny filtry pro v´ ypoˇcet vˇsech metrik, d´ale samostatn´e prvky potˇrebn´e pro vyobrazen´ı grafov´ ych a textov´ ych informac´ı ve v´ ysledn´em obrazu apod. Velmi zjednoduˇsen´e sch´ema z´ akladn´ı roury pouˇzit´e v podp˚ urn´ ych n´astroj´ıch zobrazuje Obr´azek 7. Ze vstupn´ıho souboru ve form´ atu .vtk jsou pomoc´ı vtkPolyDataReader naˇctena zdrojov´ a data s 3D povrchovou s´ıt´ı. Tato data jsou postoupena do pˇr´ısluˇsn´eho vyhlazovac´ıho filtru (dle vybran´e metody), pˇriˇcemˇz pˇred vstupem do filtru a pˇri v´ ystupu z filtru je mˇeˇren spotˇrebovan´ y ˇcas. Z v´ ystupu vyhlazovac´ıho filtru jsou data d´ale pˇred´av´ana postupnˇe do filtr˚ u implementuj´ıc´ıch jednotliv´e metriky (mujVtkVolumeComputer, mujVtkL2ErorMetrix, mujVtkL2ErorNormMetrix, vtkCurvatures). Vypoˇcten´e v´ ysledky metrik jsou po v´ ypoˇctu zaznamen´any do textov´eho .log souboru a z´aroveˇ n pˇred´any pˇr´ısluˇsn´emu vtkTextActoru a vtkRendereru (vtkChartXY, vtkContextActoru a vtkRendereru v pˇr´ıpadˇe grafu). Hlavn´ı vstupn´ı polydata do filtr˚ u s metrikami jsou po v´ ypoˇctu pˇred´ av´ ana v nezmˇenˇen´e formˇe (popˇr. doplnˇen´a o doplˇ nuj´ıc´ı datov´a pole) na v´ ystup, odkud vstupuj´ı do vtkMapperu a z nˇej pak do vtkActor. D´ale data pˇreb´ır´ a vtkRenderer. Vˇsechny vtkRenderery jsou pak souˇc´ast´ı okna (vtkRenderWindow). O ”screenshot”okna se star´ a vtkWindowToImageFilter spoleˇcnˇe s pˇr´ısluˇsn´ ym writerem (napˇr. vtkPNGWriter).

26

vtkChartXY + vtkContextActor + vtkRenderer

.vtk file

vtkPolyDataReader

smoothFilter

filtry pro výpočet všech metrik

stopWatch

vtkActor + vtkRenderer

vtkRenderWindow + vtkWindowToImage Filter

vtkPNGWriter

.png file

vtkTextActor + vtkRenderer

log file

Obr´azek 7: Sch´ema z´ akladn´ı vizualizaˇcn´ı pipeline testovac´ıho programu. Zdroj: vlastn´ı

V´ ysledkem pr˚ uchodu rourou je tedy jeden textov´ y a jeden obr´azkov´ y soubor. Textov´ y soubor obsahuje u ´daje o pouˇzit´e vyhlazovac´ı technice, o vstupn´ım 3D modelu a v´ ysledky jednotliv´ ych metrik. Obr´ azkov´ y soubor obsahuje u ´daje o pouˇzit´e vyhlazovac´ı technice, o vstupn´ım 3D modelu, v´ ysledky jednotliv´ ych metrik, grafy ˇcetnost´ı z jednotliv´ ych metrik, jeden obraz vyhlazen´eho 3D modelu (”flat shaded”), dalˇs´ı tˇri obrazy vyhlazen´eho modelu s barevnˇe namapovan´ ymi hodnotami vybran´ ych metrik. V prvn´ım n´ astroji, kter´ y slouˇz´ı k hromadn´emu generov´an´ı dat o vyhlazovan´ ych modelech, je v´ yˇse popsan´ a roura (viz Obr´ azek 7) od okamˇziku naˇcten´ı vstupn´ıch dat opakov´ana ve smyˇcce. Poˇcet pr˚ uchod˚ u smyˇckou pak z´avis´ı na nastaven´ ych parametrech vyhlazovac´ıho algoritmu, typicky na zvolen´em poˇctu iterac´ı. Druh´ y n´astroj vizualizaˇcn´ı rouru neopakuje, ale slouˇz´ı k jednor´ azov´emu zobrazen´ı konkr´etn´ıho zkouman´eho pˇr´ıpadu na obrazovku s moˇznost´ı interaktivn´ıho prohl´ıˇzen´ı a bliˇzˇs´ıho zkoum´an´ı (napˇr. pˇribl´ıˇzen´ı, natoˇcen´ı atd.). Vizualizaˇcn´ı roura popsan´ a v´ yˇse je zde doplnˇena o vtkRenderWindowInteractor, kter´ y drˇz´ı okno zobrazen´e na obrazovce a monitoruje ud´alosti myˇsi ˇci kl´avesnice a zajiˇst’uje odpov´ıdaj´ıc´ı reakci modelu.

6.3 6.3.1

Implementace jednotliv´ ych hodnot´ıc´ıch metrik a vyhlazovac´ıch filtr˚ u Metrika zmˇ eny celkov´ eho objemu tˇ elesa

V r´amci obou podp˚ urn´ ych n´ astroj˚ u je metrika zmˇeny objemu reprezentov´ana novˇe vytvoˇrenou tˇr´ıdou mujVtkVolumeComputer. Ta pˇredstavuje procesn´ı filtr, jenˇz zpracuje vstupn´ı vtkPolyData a v nezmˇenˇen´e podobˇe je pˇred´a na v´ ystup. Bˇehem toho jsou vypoˇcteny poˇzadovan´e u ´daje o objemu, kter´e jsou pot´e dostupn´e pˇres funkce getobjem() resp. getmassVolume(). Funkce getmassVolume() vyuˇz´ıv´a pro v´ ypoˇcet objemu tˇr´ıdu z knihovny vtk vtkMassProperties a jej´ı funkci GetVolume() a funkce getobjem() vyuˇz´ıv´ a pro v´ ypoˇcet objemu vzorec dle [VOLU], tzn. dle vztahu (43): 6.3.2

L2 chybov´ a norma

Metrika L2 pr˚ umˇern´e chyby je reprezentov´ana novˇe vytvoˇrenou tˇr´ıdou mujVtkL2ErorMetrix. Ta pˇredstavuje procesn´ı filtr, jenˇz zpracuje vstupn´ı vtkPolyData a v nezmˇenˇen´e podobˇe je pˇred´ a na v´ ystup, doplnˇen´e o pole s hodnotami k jednotliv´ ym 2 vrchol˚ um. Bˇehem toho jsou vypoˇcteny poˇzadovan´e hodnoty L pr˚ umˇern´e chyby

27

v jednotliv´ ych vrcholech i celkov´ y ukazatel. Celkov´ y ukazatel je pot´e dostupn´ y pˇres funkce getmeanL2errorW(), pole hodnot pro jednotliv´e vrcholy je pak pˇrid´ano do v´ ystupn´ıch dat, odkud jsou pak vyuˇzity k barevn´emu mapov´an´ı a tvorbˇe grafu. Pro v´ ypoˇcet je pouˇzit vztah viz (44). Pro hled´an´ı nejbliˇzˇs´ıho bodu z referenˇcn´ı s´ıtˇe je vyuˇzito tˇr´ıdy z knihovny vtk vtkCellLocator. 6.3.3

L2 norm´ alov´ a chybov´ a norma

Metrika L2 pr˚ umˇern´e norm´ alov´e chyby je reprezentov´ana novˇe vytvoˇrenou tˇr´ıdou mujVtkL2ErorMetrix. Tato je obdobn´a jako v 6.3.2, kdy v´ ypoˇcet se vˇsak ˇr´ıd´ı vztahem viz (45). Pojem ”troj´ uheln´ık nejbliˇzˇs´ı k troj´ uheln´ıku”je zde ch´ap´an ve smyslu minim´ aln´ı vzd´ alenosti centroid˚ u dvou troj´ uheln´ık˚ u. Pro vyhled´an´ı nejbliˇzˇs´ıho troj´ uheln´ıku z referenˇcn´ı s´ıtˇe je vyuˇzito tˇr´ıdy z knihovny vtk vtkPointLocator. 6.3.4

Metrika zakˇ riven´ı

K v´ ypoˇctu metriky zakˇriven´ı je vyuˇzito tˇr´ıdy vtkCurvatures dostupn´e v r´amci n´astroj˚ u VTK. Ten je implementov´ an v souladu se vztahem (46). Po pr˚ uchodu t´ımto filtrem je do vstupn´ıch dat pˇrid´ ano pole s hodnotami zakˇriven´ı v konkr´etn´ıch bodech. Odtud jsou pak vyuˇzity k v´ ypoˇctu pr˚ umˇern´e hodnoty, k barevn´emu mapov´an´ı a k tvorbˇe grafu. 6.3.5

Kvalita troj´ uheln´ık˚ u

´ Udaje o kvalitˇe troj´ uheln´ık˚ u poskytuje novˇe vytvoˇren´a tˇr´ıda mujVtkTriQuality. Ta pˇredstavuje procesn´ı filtr, jenˇz zpracuje vstupn´ı vtkPolyData a v nezmˇenˇen´e podobˇe je pˇred´ a na v´ ystup, doplnˇen´e o pole ukazatel˚ u vypoˇcten´ ych dle vztahu (47) pro ´ kaˇzd´ y troj´ uheln´ık. Takto dostupn´e u ´daje pak slouˇz´ı k tvorbˇe grafu ˇcetnost´ı. Udaje o minim´ aln´ı, maxim´ aln´ı ˇci pr˚ umˇern´e hodnotˇe lze z´ıskat pˇres funkce GetworstQuality() , GetbestQuality() a GetmeanQuality() 6.3.6

V´ ypoˇ cetn´ı ˇ cas

V r´amci podp˚ urn´ ych n´ astroj˚ u je mˇeˇren´ı ˇcasu implementov´ano tak, ˇze po nastaven´ı parametr˚ u dan´eho vyhlazovac´ıho filtru, avˇsak pˇred vyvol´an´ım spuˇstˇen´ı jeho hlavn´ı funkce (tj. napˇr. pˇred poˇzadavkem na v´ ystup, kter´ y spust´ı vykon´an´ı filtru), je zaznamen´an u ´daj o aktu´ aln´ım ˇcase a vyvol´ ano vynucen´e spuˇstˇen´ı pomoc´ı funkce Update(). N´aslednˇe je opˇet zjiˇstˇen u ´daj o aktu´ aln´ım ˇcase, kter´ y se pak odeˇcte od ˇcasu zaznamenan´eho pˇred spuˇstˇen´ım filtru. 6.3.7

Vyhlazovac´ı filtry

Pro laplaci´ ansk´e vyhlazov´ an´ı byla vytvoˇrena nov´a tˇr´ıda, kter´a oproti z´akladn´ı implementaci dostupn´e ve VTK obsahuje pˇr´ıpadn´ y v´ ypoˇcet kotangentov´ ych vah (viz 3.1.2), inflataˇcn´ı metodu (viz 4.1) a single-point relaxaˇcn´ı metodu (4.2). Tato implementace je tud´ıˇz ve v´ ysledku ˇcasovˇe n´ aroˇcnˇejˇs´ı neˇz optimalizovan´a z´akladn´ı metoda z VTK. Obecnˇe se z v´ ykonnostn´ıch d˚ uvod˚ u nˇekdy vyuˇz´ıv´a triku, ˇze se v´ahy, jejichˇz velikost se odv´ıj´ı od pozice vrchol˚ u, nepˇrepoˇc´ıt´ avaj´ı po kaˇzd´e iteraci. Tato implementace vˇsak kotangentov´e v´ahy pˇrepoˇc´ıt´ av´ a vˇzdy, norm´ alov´e vektory pro singl-point relaxaˇcn´ı metodu tohoto triku vyuˇz´ıvaj´ı, a proto nen´ı zachov´ an´ı objemu vˇzdy zcela u ´pln´e. 28

Kromˇe vestavˇen´ı inflataˇcn´ı metody pˇr´ımo do vyhlazovac´ıho filtru, byla tato metoda implementov´ ana i jako samostatn´a tˇr´ıda - filtr dle konvenc´ı VTK, kter´ y je moˇzno zapojit do bˇeˇzn´e kter´ekoliv vizualizaˇcn´ı roury, za podm´ınky nastaven´ı hlavn´ıho a vedlejˇs´ıho vstupu. Pro Taubin FIR filtr je vyuˇzita tˇr´ıda dostupn´a z VTK vtkWindowedSincPolyDataFilter, kter´a vyuˇz´ıv´ a Hammingovo okenn´ı funkci (viz vztah (26)). Pass-Band region je pevnˇe nastaven na doporuˇcovanou hodnotu k = 0.1.

7

Vyhodnocen´ı jednotliv´ ych technik

Hlavn´ım u ´kolem t´eto pr´ ace bylo porovn´an´ı vyhlazovac´ıch technik s ohledem na zachov´av´ an´ı objemu. Vyhlazovac´ı techniky prim´arnˇe zachov´an´ı objemu negarantuj´ı, a proto, jak je uvedeno v kapitole 4, pro zachov´an´ı objemu existuj´ı i doplˇ nkov´e techniky k z´akladn´ım vyhlazovac´ım technik´ am. Pro co nejv´ yraznˇejˇs´ı zviditelnˇen´ı u ´ˇcinnosti tˇechto metod byla jako z´ akladn´ı vyhlazovac´ı technika, se kterou jsou tyto doplˇ nky zkombinov´any, zvolena technika nev´ aˇzen´eho laplaci´ ansk´eho vyhlazov´an´ı. U toho je obecnˇe zn´amo, ˇze pokles objemu pˇri vyhlazov´ an´ı je velmi v´ yrazn´ y. Do porovn´an´ı byla jeˇstˇe zaˇrazena metoda Taubin FIR filtru. V´ ybˇer pouˇzit´ ych vyhlazovac´ıch technik je tedy: • nev´ aˇzen´e laplaci´ ansk´e vyhlazov´an´ı • nev´ aˇzen´e laplaci´ ansk´e vyhlazov´an´ı s korekc´ı inflataˇcn´ı metodou • nev´ aˇzen´e laplaci´ ansk´e vyhlazov´an´ı s korekc´ı single-point relaxaˇcn´ı metodou • ”implicit fairing”- kotangentov´e laplaci´ansk´e vyhlazov´an´ı • ”implicit fairing”- kotangentov´e laplaci´ansk´e vyhlazov´an´ı s korekc´ı inflataˇcn´ı metodou • ”implicit fairing”- kotangentov´e laplaci´ansk´e vyhlazov´an´ı s korekc´ı single-point relaxaˇcn´ı metodou • Taubin FIR filtr • Taubin FIR filtr s korekc´ı inflataˇcn´ı metodou Pro zjemnˇen´ı kroku mezi jednotliv´ ymi iteracemi u laplaci´ansk´eho vyhlazov´an´ı a u metody ”implicit fairing” byly hodnoty laplacian oper´atoru upraveny o α koeficient 0.5. V aplikaˇcn´ı praxi, kdy je zapotˇreb´ı, aby byla moˇznost vˇetˇs´ı uˇzivatelsk´e regulace m´ıry vyhlazov´ an´ı, se zpravidla pouˇz´ıv´a koeficient α jeˇstˇe mnohem menˇs´ı, kdy vˇsak cenou je vyˇsˇs´ı poˇcet nutn´ ych iterac´ı. Pro u ´ˇcely t´eto pr´ace vyˇsˇs´ı koeficient volen z d˚ uvodu lepˇs´ı sledovatelnosti zmˇen mezi jednotliv´ ymi iteracemi. Pro u ´ˇcely porovn´ av´ an´ı byly jako referenˇcn´ı modely zvoleny dvˇe skupiny 3D objekt˚ u. Prvn´ı skupina referenˇcn´ıch model˚ u je, jak je jiˇz zm´ınˇeno v zad´an´ı pr´ace, ze skupiny z´akladn´ıch geometrick´ ych tˇeles, tedy umˇele vygenerovan´e kouli a krychli s umˇele zanesen´ ym ˇsumem do ˇc´asti jejich povrchu. Tyto modely jsou zvoleny zejm´ena proto, ˇze jejich ide´aln´ı koneˇcn´ a vyhlazen´ a podoba je pˇredem zn´ama, a to vˇcetnˇe analytick´ ych ˇreˇsen´ı jejich vlastnost´ı, zejm´ena pak objemu. Model krychle pak nav´ıc obsahuje viditeln´e ostr´e hrany, na nichˇz je zˇreteln´ au ´ˇcinnost jednotliv´ ych metod v oblasti zachov´av´an´ı rys˚ u (feature preserving). Druhou skupinu referenˇcn´ıch model˚ u tvoˇr´ı modely z´ıskan´e z re´aln´ ych biomedic´ınsk´ ych dat. Tyto jsou zvoleny tak, aby obsahovaly typick´e neˇz´adouc´ı jevy spojen´e se z´ısk´an´ım dat 29

a vytvoˇren´ım modelu, jako napˇr. ostr´e u ´zk´e troj´ uheln´ıky, ˇsum, d´ıry, schodovit´e artefakty atd., a z´ aroveˇ n aby obsahovaly jak velk´e plochy s n´ızk´ ym zakˇriven´ım, tak i m´ısta s vysokou hodnotou zakˇriven´ı ˇci charakteristick´ ymi rysy (hranami, kouty apod.). Pro tyto u ´ˇcely je zvolen model p´ anevn´ı kosti a kus ˇslachy, viz Obr´azek 8. Oba trp´ı vysokou u ´rovn´ı drobn´eho povrchov´e ˇsumu i ˇspatnou kvalitou nˇekter´ ych troj´ uheln´ık˚ u.

Obr´azek 8: Zvolen´e referenˇcn´ı modely - koule, krychle, p´anevn´ı kost, lebeˇcn´ı kosti. Zdroj: vstupn´ı modely

K v´ ypoˇct˚ um byla pouˇzita sestava s procesorem Intel Core2 Duo 2,4 GHz, 3Gb DDRII800 RAM, 750GB SATAII HDD, AMD Radeon HD6570 a operaˇcn´ı syst´em Windows 8.1 Pro 64bit. Veˇsker´e obrazov´e v´ ystupy generovan´e pomocn´ ymi programy a datov´e ˇrady jsou z d˚ uvodu jejich mnoˇzstv´ı zaˇrazeny do pˇr´ıloh pouze v elektronick´e formˇe.

7.1

Vyhodnocen´ı - Laplaci´ ansk´ e vyhlazov´ an´ı s uniformn´ımi vahami

Z hlediska vizu´ aln´ıho posouzen´ı lze konstatovat, ˇze tato metoda dosahuje pomˇernˇe siln´eho vyhlazovac´ıho efektu, kdy vˇsak vyhlazen´ı prob´ıh´a ve vˇsech oblastech rovnomˇernˇe, bez ohledu na charakteristick´e rysy a hrany. Nejvˇetˇs´ı povrchov´ y ˇsum je zcela potlaˇcen jiˇz po nˇekolika m´ alo iterac´ıch (cca 10, pˇri α = 0.5) a hrany jsou otupeny ˇci potlaˇceny velmi intenzivnˇe. To lze pozorovat na vˇsech zkouman´ ych modelech. Pˇri cca 25 iterac´ıch je jiˇz model krychle velmi zakulacen, model p´anve m´a silnˇe potlaˇcenou kloubn´ı jamku a stydk´ a a sedac´ı kost je na konc´ıch velmi zeslabena a otvor celkovˇe zvˇetˇsen, viz Obr´ azek 9 . Inflataˇcn´ı metoda vyhlazen´ı z vizu´aln´ıho hlediska neovlivnila. Naproti tomu single-point relaxaˇcn´ı metoda m´ a po vizu´ aln´ı str´ance efekt nev´ yrazn´ y, nebot’ obecnˇe je tato metoda slab´a v norm´ alov´em smˇeru. Z pohledu zachov´ an´ı objemu je obecnˇe zn´amo, ˇze nev´aˇzen´a varianta laplaci´ansk´eho vyhlazov´ an´ı trp´ı smrˇst’ovac´ım efektem. Toto potvrzuj´ı i namˇeˇren´a data, viz Obr´azek 10. Nejvˇetˇs´ı pokles nastal u modelu p´anve, d´ale u krychle, koule a ˇslachy. Smrˇstˇen´ı je v´ yrazn´e, a m´a t´emˇeˇr line´ arn´ı pr˚ ubˇeh. Vzhledem k vizu´aln´ımu porovn´an´ı, kdy pˇrijateln´ ych v´ ysledk˚ u bylo dosaˇzeno cca v rozmez´ı 8-20 iterac´ı, dosahuje smrˇstˇen´ı aˇz k hodnot´am 82% p˚ uvodn´ı velikosti. Inflataˇcn´ı metoda je pak plnˇe navrac´ı na p˚ uvodn´ı velikost. Na kvalitu troj´ uheln´ık˚ u m´ a laplaci´ansk´e vyhlazov´an´ı pozitivn´ı vliv, kdy pr˚ umˇern´ y ukazatel rostl. V poˇc´ ateˇcn´ıch iterac´ıch, kter´e jsou nejrelevantnˇejˇs´ı, doˇslo k relativnˇe rychl´emu n´ ar˚ ustu tempa zv´ yˇsen´ı kvality, kter´e se se zvyˇsuj´ıc´ım se poˇctem iterac´ı zm´ırˇ novalo. V´ yjimkou byl model ˇslachy. Pˇrid´an´ı inflataˇcn´ı techniky k samotn´emu vyhlazov´ an´ı nem´ a na kvalitu ˇz´ adn´ y dopad, obˇe kˇrivky jsou shodn´e. Relaxaˇcn´ı metoda 30

Obr´azek 9: Vizu´ aln´ı porovn´ an´ı vyhlazen´ ych model˚ u krychle a p´anve. Vlevo nevyhlazen´e modely, uprostˇred po 26 iterac´ıch, vpravo po 26 iterac´ıch a singl-point relaxaˇcn´ı metodˇe. Zdroj: programov´e v´ ystupy.

m´a slab´ y vyhlazovac´ı u ´ˇcinek, avˇsak ve vˇsech pˇr´ıpadech lepˇs´ı vliv na kvalitu troj´ uheln´ık˚ u. Viz obr´ azek 11. Vlivem vyhlazov´ an´ı doch´ az´ı ke vzniku ”chyby” , kter´a vypov´ıd´a, jak moc je nov´a vyhlazen´ a s´ıt’ vzd´ alen´ a od t´e p˚ uvodn´ı. Zaj´ımav´ y je jak pr˚ umˇern´ y ukazatel L2 error, tak i i rozloˇzen´ı t´eto chyby v prostoru. Pr˚ umˇern´ y ukazatel u vˇsech model˚ u byl vyˇsˇs´ı u vyhlazen´ı bez korekce objemu, zejm´ena t´ım, jak se vlivem smrˇst’ov´an´ı vzdaloval od sv´eho p˚ uvodn´ıho vzoru. Pˇri pohledu na rozloˇzen´ı v prostoru lze pak pozorovat, kter´a m´ısta byla vyhlazen´ım nejv´ıce zasaˇzena, viz Obr´ azek 12. V ploch´ ych ˇc´ astech je chyba na velk´em regionu mal´a, v kontrastu s vysok´ ymi hodnotami u hran a roh˚ u. U inflataˇcn´ı metody lze pozorovat zv´ yˇsen´ y n´ar˚ ust chyby v ploch´ ych ˇc´astech oproti metodˇe bez objemov´e korekce. Je to d´ano redistribuc´ı objemu, kdy objem ztracen´ y pˇri zaoblen´ı hran a roh˚ u je rozprostˇren mezi vˇsechny vrcholy, tedy i ty uprostˇred ploch. Pˇr´ım´e srovn´ an´ı mezi jednotliv´ ymi modely nen´ı moˇzn´e, nebot’ ukazatel je mˇeˇr´ıtkovˇe z´avisl´ y v˚ uˇci modelu.

7.2

Vyhodnocen´ı - Implicit fairing

Jedn´a se o v´ aˇzen´e laplaci´ ansk´e vyhlazov´an´ı s kotangentov´ ymi vahami. I zde byl pro zjemnˇen´ı kroku mezi jednotliv´ ymi iteracemi byl laplacian oper´ator upraven o α koeficient 0.5. Po vizu´ aln´ı str´ ance je v prvn´ıch iteraˇcn´ıch kroc´ıch vyhlazovac´ı efekt velmi v´ yrazn´ y a i na tak typick´ ych hran´ ach, jak´e m´a napˇr. krychle, se zaˇc´ınaj´ı hrany viditelnˇe zaoblovat. Nicm´enˇe oproti z´ akladn´ı nev´ aˇzen´e variantˇe laplaci´ansk´eho vyhlazov´an´ı nejsou zmˇeny v oblasti tˇechto rys˚ u tak velk´e. V cca 10 iteraci, kdy v nev´aˇzen´e variantˇe jiˇz zanesen´ y

31

Obr´azek 10: Graf v´ yvoje objemu v z´avislosti na iteraci pro laplaci´ansk´e vyhlazov´an´ı. V0 jsou bez korekce, V1 a V2 jsou s aplikovanou korekc´ı. Zdroj: programov´e v´ ystupy.

ˇsum viditeln´ y v˚ ubec nebyl, pˇri pouˇzit´ı t´eto metody jeˇstˇe slab´e zn´amky viditeln´e jsou. Pˇri eliminaci v´ yrazn´eho ˇsumu (ve smyslu v´ yrazn´a anom´alie, neˇz okoln´ı ˇsum) je viditeln´e, jak je tento eliminov´ an podstatnˇe m´enˇe neˇz okoln´ı, m´enˇe v´ yrazn´ y ˇsum. Uk´azka viz Obr´azek 13. Pr´ ah pouˇzitelnosti t´eto metody z hlediska zachov´an´ı rys˚ u je po vizu´aln´ı str´ance jistˇe vyˇsˇs´ı. V´ yˇse zm´ınˇen´e je viditeln´e i na ostatn´ıch modelech. Na modelu p´anve, v iteraci, kdy laplaci´ ansk´e vyhlazov´ an´ı je jiˇz v´ yraznˇe nedostateˇcn´e (napˇr. v´ yˇse zmiˇ novan´ ych 25 iterac´ı), implicit fairing poskytuje znatelnˇe v´ıce detail˚ u, hloubka kloubn´ı jamky nen´ı tolik zahlazena, jej´ı okraj je st´ ale zˇreteln´ y, sedac´ı kost nen´ı tolik ztenˇcena, otvor nen´ı tolik zvˇetˇsen a stydk´ y hrbol z˚ ust´ av´ a v´ yrazn´ y. I s pˇrib´ yvaj´ıc´ım poˇctem iterac´ı tyto v´ yrazn´e charakteristiky z˚ ust´ avaj´ı v˚ uˇci okol´ı v´ yrazn´e, viz napˇr. v´ yrazn´ y v´ yˇcnˇelek na Obr´azku ˇc. 13, je st´ ale pˇr´ıtomen i po mnoho dalˇs´ıch iterac´ı. Na modelu u ´ponu doch´az´ı k postupn´emu vyhlazen´ı velk´ ych ploch, zat´ımco ostr´ y hˇrbet z˚ ust´av´a st´ale viditeln´ y. Obecnˇe pˇri tomto nastaven´ı je pˇrijateln´ a hodnota vyhlazen´ı mezi 10-15 iterac´ı. Pˇri zachov´ av´ an´ı objemu inflataˇcn´ı metodou opˇet nen´ı pozorov´an v´ yznamn´ y vizu´aln´ı rozd´ıl oproti vyhlazen´ı bez zachov´an´ı objemu. Single-point relaxaˇcn´ı metody je naopak vizu´ alnˇe zcela bez u ´ˇcinku v cel´em spektru iterac´ı. To je d´ano t´ım, ˇze pˇri pouˇzit´ı kotangentov´ ych vah je eliminov´ana tangentov´a sloˇzka posunu a korekˇcn´ı krok v norm´ alov´em smˇeru jej eliminuje zpˇet. Z hlediska zachov´ an´ı objemu trp´ı i implicit fairing efektem ztr´aty objemu. Pokles m´a t´emˇeˇr line´arn´ı charakter a dosahuje vysok´ ych hodnot. Z namˇeˇren´ ych hodnot lze vypozorovat, ˇze tento pokles je vˇsak vˇzdy menˇs´ı, neˇz u nev´aˇzen´eho laplaci´ansk´eho vyhlazov´an´ı (porovn´ an´ı viz Obr´ azek 19). Z pouˇzit´ı kotangentov´ ych vah obecnˇe nevypl´ yv´a zlepˇsen´ı kvality troj´ uheln´ık˚ u, coˇz potvrzuj´ı i v´ ysledn´ a data, viz Obr´azek 15. Naopak ve vˇetˇsinˇe pˇr´ıpad˚ u, s v´ yjimkou krychle, doˇslo k poklesu. I zde inflataˇcn´ı metoda na kvalitu troj´ uheln´ık˚ u nem´a vliv a kˇrivky se

32

Obr´azek 11: Graf v´ yvoje pr˚ umˇern´e kvality troj´ uheln´ık˚ u v z´avislosti na iteraci pro laplaci´ ansk´e vyhlazov´ an´ı. V0 jsou bez korekce, V1 a V2 jsou s aplikovanou korekc´ı. Zdroj: programov´e v´ ystupy.

pˇrekr´ yvaj´ı a pˇri pouˇzit´ı relaxaˇcn´ı metody jsou hodnoty vˇzdy vyˇsˇs´ı. Pro metriku L2 error u implicit fairing metody jsou hodnoty obecnˇe niˇzˇs´ı, neˇz u laplaci´ ansk´eho vyhlazov´ an´ı. Nicm´enˇe stejnˇe jako u laplaci´ansk´eho vyhlazov´an´ı, s rostouc´ım poˇctem iterac´ı velikost chyby roste od urˇcit´e iterace prakticky line´arnˇe. Stejnˇe jako u laplaci´ ansk´eho vyhlazov´ an´ı, roste chyba pˇri aplikaci inflataˇcn´ı techniky i na m´ıstech, kter´e z´ akladn´ı algoritmus nepostihne.

7.3

Vyhodnocen´ı - Taubin FIR filter

Porovnatelnost s ohledem na poˇcet iterac´ı je zde omezena, nebot’ tato metoda m´a odliˇsn´e parametry nastaven´ı. U laplaci´ ansk´ ych byla velikost vyhlazovac´ı kroku ovlivnˇena α, kdeˇzto zde se nastavuje pr´ ah tzv. pass-band regionu (kP B ), kter´ y byl pro testov´an´ı nastaven dle obecn´ ych doporuˇcen´ı na hodnotu kP B = 0.1. Po vizu´ aln´ı str´ ance je velikost efektu v porovn´an´ı s dˇr´ıve zmiˇ novan´ ymi metodami celkovˇe menˇs´ı. Nejsilnˇejˇs´ıho efektu je dosaˇzeno v cca prvn´ıch 15 iterac´ıch, po nichˇz uˇz je pˇr´ınos dodateˇcn´ ych iterac´ı minim´aln´ı. Algoritmus se snaˇz´ı odfiltrov´avat jen vysok´e frekvence ˇsumu a n´ızk´e, odpov´ıdaj´ıc´ı moˇzn´ ym charakteristick´ ym rys˚ um, zachov´av´a. Na modelu krychle je i pˇri vyˇsˇs´ım poˇctu iterac´ı patrn´ y z´akladn´ı tvarov´ y charakter krychle (byt’ se znaˇcnˇe zakulacen´ ymi hranami) oproti pˇredchoz´ım zmiˇ novan´ ym metod´am, kter´e maj´ı tendenci pˇremˇeny do tvaru koule. Vyhlazen´ı modelu u ´ponu je dostateˇcn´e, v cel´em zkouman´em rozsahu iterac´ı z˚ ustal cel´ y ostr´ y hˇrbet v pod´eln´e rovinˇe ostr´ y, otupˇeny byly jen drobn´e jeho otˇrepky. Na modelu p´ anve je vˇsak moˇzn´e naj´ıt nejedno m´ısto, kdy zachov´an´ı rys˚ u je neopodstatnˇen´e a ku ˇskodˇe vˇeci. Na obr´ azku jsou vyznaˇcena m´ısta lemuj´ıc´ı kloubn´ı jamku, kter´e filtr nevyhladil, naopak v˚ uˇci okol´ı zv´ yraznil. Obdobnˇe je zde vyznaˇcen i hˇrbet boltcovit´e plochy s v´ yrazn´ ym ˇspiˇcat´ ym v´ ybˇeˇzkem, kter´ y m´a b´ yt ve skuteˇcnosti plynul´ y (viz Obr´azek 16).

33

Obr´azek 12: Krychle vyhlazen´ a laplaci´ansk´ ym vyhlazov´an´ım o 20 iterac´ıch. Vlevo bez objemov´e korekce, vpravo s inflataˇcn´ı metodou. Barva namapov´ana dle L2 error. Zdroj: programov´e v´ ystupy.

Obr´azek 13: V´ yˇrez z obr´ azku koule vyhlazen´e pomoc´ı implicit fairing metody (vlevo) a z´akladn´ıho laplaci´ ansk´eho vyhlazov´an´ı (vpravo) po 10 iterac´ıch. Zdroj: programov´e v´ ystupy.

Aplikace inflataˇcn´ı techniky zachov´an´ı objemu nemˇela po vizu´aln´ı str´ance na vyhlazen´ y model ˇz´ adn´ y vliv. Taubin FIR filter dosahuje velmi dobr´ ych hodnot pro zachov´ an´ı objemu i bez doplˇ nkov´ ych technik. Jeho hodnoty osciluj´ı pod´el 100% hranice v cel´em zkouman´em rozsahu iterac´ı pouze v u ´zk´em rozpˇet´ı hodnot. Viz Obr´azek 17. V prvn´ıch nˇekolika iterac´ıch m´a pouˇzit´ı Taubin FIR filtru v´ yrazn´ y vliv na zlepˇsen´ı pr˚ umˇern´e kvality troj´ uheln´ık˚ u. Od cca sedm´e iterace se vˇsak kvalita ve vˇsech pˇr´ıpadech ust´alila. Celkovˇe tak po aplikaci filtru doˇslo ve vˇsech pˇr´ıpadech ke zlepˇsen´ı. Aplikov´ an´ı inflataˇcn´ı techniky opˇet nem´ a na kvalitu troj´ uheln´ık˚ u vliv a kˇrivky v grafu se tud´ıˇz pˇrekr´ yvaj´ı. U Taubin FIR filtru byly hodnoty L2 error u vˇsech zkouman´ ych model˚ u nejniˇzˇs´ı. Jej´ı pr˚ umˇern´ y charakter odpov´ıd´ a oscilaci objemu kolem stoprocentn´ı hodnoty.

7.4

Shrnut´ı vz´ ajemn´ eho porovn´ an´ı

Pˇri zkoum´ an´ı vizu´ aln´ıho hlediska lze konstatovat, ˇze z´akladn´ı laplaci´ansk´e vyhlazov´ an´ı nen´ı pˇr´ıliˇs vhodn´e, velmi brzo vyhlazuje i d˚ uleˇzit´e ˇc´asti, hrany a charakteristick´e rysy. Taubin FIR Filtr vyhlazuje dostateˇcnˇe s ohledem na zachov´an´ı rys˚ u, avˇsak lze nal´ezt 34

Obr´azek 14: Graf v´ yvoje objemu v z´avislosti na iteraci pro implicit fairing techniku. V0 jsou bez korekce, V1 a V2 jsou s aplikovanou korekc´ı. Zdroj: programov´e v´ ystupy.

pˇr´ıpady, kdy nˇekter´e nedokonalosti jsou nam´ısto vyhlazen´ı zv´ yraznˇeny. Z vizu´aln´ıho hlediska lze uspokojiv´ ych v´ ysledk˚ u dos´ahnout pomoc´ı implicit fairing metody, avˇsak je zapotˇreb´ı peˇcliv´ a volba poˇctu iterac´ı. Jak laplaci´ ansk´e vyhlazov´ an´ı, tak implicit fairing metoda dle oˇcek´av´an´ı selh´av´a ve smyslu zachov´ an´ı objemu, kdy objem t´emˇeˇr line´arnˇe kles´a v z´avislosti na poˇctu iterac´ı a je tˇreba je doplnit korekˇcn´ımi mechanismy. Inflataˇcn´ı technika ve vˇsech zkouman´ ych situac´ıch pod´avala dobr´e v´ ysledky. Graf z´avislosti objemu na poˇctu iterac´ı zobrazuje Obr´azek 19. Ze z´ıskan´ ych dat se n´ ar˚ ust kvality troj´ uheln´ık˚ u vˇzdy projevil pˇri pouˇzit´ı Taubin FIR filtru. Naproti tomu u implicit fairing metody nen´ı tento aspekt jednoznaˇcn´ y, nebot’ ve vˇetˇsinˇe pˇr´ıpad˚ u doˇslo k poklesu pr˚ umˇern´e kvality. Pouˇzit´ı inflataˇcn´ı techniky ve vˇsech pˇr´ıpadech nemˇelo na kvalitu troj´ uheln´ık˚ u ˇz´adn´ y dopad, zat´ımco single-point relaxaˇcn´ı metoda dos´ ahle ve vˇsech sledovan´ ych pˇr´ıpadech lepˇs´ıch hodnot, neˇz samotn´e vyhlazen´ı. Jako pˇr´ıklad pro Obr´ azek 20 slouˇz´ı model koule.

35

Obr´azek 15: Graf v´ yvoje pr˚ umˇern´e kvality troj´ uheln´ık˚ u v z´avislosti na iteraci pro implicit fairing techniku. V0 jsou bez korekce, V1 a V2 jsou s aplikovanou korekc´ı. Zdroj: programov´e v´ ystupy.

Obr´azek 16: V´ yˇrez z obr´ azku p´anevn´ı kosti v oblasti jamky kyˇceln´ıho kloubu. Vlevo implicit fairing (10 iterac´ı), vpravo Taubin FIR Filtr (20 iterac´ı). Zdroj: programov´e v´ ystupy.

36

Obr´azek 17: Graf v´ yvoje objemu v z´avislosti na iteraci pro Taubin FIR filtr. V0 jsou bez korekce, V1 a V2 jsou s aplikovanou korekc´ı. Zdroj: programov´e v´ ystupy.

Obr´azek 18: Graf v´ yvoje pr˚ umˇern´e kvality troj´ uheln´ık˚ u v z´avislosti na iteraci pro Taubin FIR filtr. V0 jsou bez korekce, V1 a V2 jsou s aplikovanou korekc´ı. Zdroj: programov´e v´ ystupy.

37

Obr´azek 19: Graf v´ yvoje objemu v z´avislosti na iteraci mezi jednotliv´ ymi technikami bez korekce objemu. U=nev´ aˇzen´e laplaci´ansk´e vyhlazov´an´ı, C=Implicit fairing, F=FIR filter. Zdroj: programov´e v´ ystupy.

Obr´azek 20: Graf v´ yvoje pr˚ umˇern´e kvality troj´ uheln´ık˚ u na modelu koule v z´avislosti na iteraci mezi jednotliv´ ymi technikami. U=nev´aˇzen´e laplaci´ansk´e vyhlazov´an´ı, C=Implicit fairing, F=FIR filter. Zdroj: programov´e v´ ystupy.

38

Z pohledu metriky L2 error dosahuje nejpˇr´ıznivˇejˇs´ıch hodnot Taubin FIR filter, u nˇejˇz pr˚ umˇern´ a hodnota osciluje obdobnˇe jako hodnota objemu. Nejvˇetˇsi chybou je zat´ıˇzeno z´akladn´ı laplaci´ ansk´e vyhlazov´ an´ı. Inflataˇcn´ı metodou doch´azelo k poklesu hodnot L2 error, avˇsak zmˇeny se projevovaly ploˇsnˇe i v m´ıstech, kde by nemˇely (napˇr. prohnut´ı roviny), viz napˇr. Obr´ azek 12. N´azorn´e porovn´an´ı metod na pˇr´ıkladu modelu u ´ponu vyjadˇruje Obr´ azek 21.

Obr´azek 21: Graf v´ yvoje pr˚ umˇern´e L2 error na modelu u ´ponu v z´avislosti na iteraci mezi jednotliv´ ymi technikami. U=nev´aˇzen´e laplaci´ansk´e vyhlazov´an´ı, C=Implicit fairing, F=FIR filter, V0 jsou bez korekce, V1 a V2 jsou s aplikovanou korekc´ı. Zdroj: programov´e v´ ystupy.

Srovn´ an´ı v´ ypoˇcetn´ıho ˇcasu je v t´eto pr´aci obt´ıˇzn´e, nebot’ pouˇzit´e metody maj´ı odliˇsn´e zp˚ usoby implementace ˇci jsou z odliˇsn´ ych zdroj˚ u. Vytvoˇren´e implementace nebyly, narozd´ıl od pˇrevzat´ ych knihovn´ıch funkc´ı, nijak optimalizov´any. Ve v´ ysledku pak jsou mezi jednotliv´ ymi v´ ypoˇcty ˇr´ adov´e rozd´ıly, kdy napˇr. pˇrevzat´ y Taubin FIR filtr m´a desetinovou potˇrebu v´ ypoˇcetn´ıho ˇcasu a implicit fairing, pˇri kter´em jsou v kaˇzd´e iteraci kotangentov´e v´ahy pˇrepoˇc´ıt´ av´ any, m´ a jeˇstˇe o to v´ıce. Posuzov´an´ı v´ ypoˇcetn´ı n´aroˇcnosti touto cestou tud´ıˇz nem´a dostateˇcnou vypov´ıdac´ı hodnotu pro formulaci z´avˇeru.

8

Z´ avˇ er

Tato pr´ ace se zab´ yvala porovn´ an´ım vyhlazovac´ıch pˇr´ıstup˚ u se zamˇeˇren´ım na zachov´ an´ı objemu, zejm´ena v kontextu biomedic´ınsk´ ych aplikac´ı. Byly rozebr´ any potˇreby, kter´e vedou k d˚ uleˇzitosti vyhlazovac´ıch technik obecnˇe i v medic´ınsk´em kontextu a rozebr´any pˇr´ıˇciny vzniku neˇz´adouc´ıch jev˚ u objevuj´ıc´ıch se na r˚ uzn´ ych stupn´ıch zpracov´ an´ı z´ıskan´ ych dat. D´ale byly sumarizov´ any z´ akladn´ı teoretick´e poznatky o bˇeˇznˇe pouˇz´ıvan´ ych z´akladn´ıch vyhlazovac´ıch metod´ ach, jako je napˇr´ıklad z´akladn´ı i r˚ uznˇe v´aˇzen´e laplaci´ansk´e vyhlazov´ an´ı, norm´ alov´e vyhlazov´an´ı, bilater´aln´ı vyhlazov´an´ı a jejich neiteraˇcn´ı verze. Posl´eze byly uvedeny r˚ uzn´e zp˚ usoby pro hodnocen´ı vyhlazovac´ıch algoritm˚ u a definov´any jednotliv´e hodnot´ıc´ı metriky. N´aslednˇe byly pˇredstaveny softwarov´e n´astroje vytvoˇren´e 39

pro generov´ an´ı potˇrebn´ ych v´ ystupn´ıch dat a velmi struˇcn´ y popis jejich implementace. Do v´ ybˇeru metod byla zaˇrazena metoda laplaci´ansk´eho vyhlazov´an´ı s uniformn´ımi vahami, implicit fairing metoda a Taubin FIR filtr s Hammingovo okenn´ı funkc´ı. Na z´ akladˇe vygenerovan´ ych vstupn´ıch podklad˚ u bylo provedeno porovn´an´ı v´ ysledk˚ u v ˇclenˇen´ı dle jednotliv´ ych vyhlazovac´ıch metod a hodnot´ıc´ıch krit´eri´ı. Na z´avˇer bylo provedeno shrnut´ı napˇr´ıˇc jednotliv´ ymi technikami. Pro u ´ˇcely vyhlazov´ an´ı ve vˇsech sledovan´ ych aspektech dosahovalo z´akladn´ı laplaci´ansk´e vyhlazov´ an´ı dle oˇcek´ av´ an´ı nejhorˇs´ıch hodnot. Z hlediska zachov´an´ı detail˚ u pˇri spr´avn´em nastaven´ı poˇctu iterac´ı dosahuje dostateˇcn´ ych hodnot implicit fairing metoda. Taubin FIR filtr rovnˇeˇz poskytuje akceptovateln´e v´ ysledky a je jednoznaˇcnˇe nejv´ıce pˇr´ızniv´ y v ot´azce zachov´ an´ı objemu, kdy i bez korekˇcn´ıch metod objem osciloval kolem ˇz´adan´e hodnoty. FIR filtr rovnˇeˇz dosahoval zlepˇsen´ı v oblasti kvality troj´ uheln´ık˚ u. Jako dodateˇcn´ a technika pro zachov´ an´ı objemu se byla bezprobl´emov´a inflataˇcn´ı technika. Porovn´ an´ı z hlediska v´ ypoˇcetn´ıho ˇcasu nen´ı uvedeno vzhledem k rozd´ıln´emu charakteru a optimalizaci jednotliv´ ych implementac´ı vyhlazovac´ıch metod ve VTK. Z´avˇerem lze dodat, ˇze vyhlazovac´ıch technik a hodnot´ıc´ıch krit´eri´ı existuje velk´e mnoˇzstv´ı a tato pr´ ace se zab´ yvala pouze zlomkem z nich. Z˚ ust´av´a tak otevˇreno ˇsirok´e pole p˚ usobnosti k dalˇs´ımu porovn´ av´ an´ı a prac´ı podobn´eho charakteru.

40

Reference [BEOH03] BELYAEV A., OHTAKE Y. A Comparison of Mesh Smoothing Methods. In Proceedings of the Israel-Korea BiNational Conference on Geometric Modeling and Computer Graphic, 2003, 83-87 [BHP06]

BADE R., HAASE J., PREIM B. Comparison of Fundamental Mesh Smoothing Algorithms for Medical Surface Models. In Simulation und Visualisierung, 2006, 289-304

[DES99]

¨ DESBRUN M., MEYER M., SCHRODER P., BARR A.H.Implicit Fairing of Irregular Meshes using Diffusion and Curvature Flow. In SIGGRAPH ’99, 1999, 317–324

[FLEIS03] FLEISHMAN S., DRORI I., COHEN-OR D. Bilateral Mesh Denoising. In SIGGRAPH ’03, 2003, 950-953 [HOLM]

HOLMSTROM V.Modified SurfaceNets: Smoothing a Marching Cubes Mesh [on-line]. [cit. 2014-03-30]. Dostupn´e na http://www.cs.wm.edu/∼ nikos/cs420/projects/ModifiedSurfaceNets.pdf

[HUANG] HUANG J., SHI X., LIU X., ZHOU K., WEI L., TENQ S., BAO H., GUO B., SHUM H. Subspace gradient domain mesh deformation. In SIGGRAPH ’06, 2006, 1126-1134. [JODD03] JONES T. R., DURAND F., DESBRUN M. Non-iterative, feature-preserving mesh smoothing. In SIGGRAPH ’03, 2003, 943-946 [KUPR01] KUPRAT A., KHAMAYSEH A., GEORGE D., LARKEY L. Volume conserving smoothing for piecewise linear curves, surfaces, and triple lines. In Journal of Computational Physics 01/2001, 99-118, 2001 [LEE05]

LEE K-W., Wang W-P. Feature-Preserving Mesh Denoising via Bilateral Normal Filtering. In CAD-CG ’05, 2005, 275-280

[LIU05]

JI Z., LIU L., WANG G. A global laplacian smoothing approach with feature preservation. In Proceedings of the 9th international conference on computer aided design and computer graphics. 2005. 269–274

[LIU07]

LIU L., TAI Ch-L., JI Z., WANG G. Non-iterative approach for global mesh optimization. In Computer-Aided Design 39, 2007, 772-782

[MASORI07] MAGID E., SOLDEA O., RIVLIN E. 2007. A comparison of Gaussian and mean curvature estimation methods on triangular meshes of range image data. In Computer Vision and Image Understanding, 2007, 139-159 [METRO] CIGNONI P., ROCCHINI C.C., SCOPIGNO R. Metro: Measuring error on simplified surfaces. Computer Graphics Forum, 1998, 167–174 [NEAL06] NEALEN A., IGARASHI T., SORKINE O., ALEXA M. Laplacian Mesh Optimalization. In GRAPHITE ’06, 2006, 381-389 [PVE92]

¨ ¨ MULLER-G ARTNER H. W., LINKS J. M., PRINCE J. L., BRYAN R. N., McVEIGH E., LEAL J. P., DAVATZIKOS C., FROST J. J. Measurement of radiotracer concentration in brain gray matter using positron emission tomography: MRI-based correction for partial volume effects. In Journal of Cerebral Blood Flow & Metabolism, 1992, 571–583

[SRML07] SUN X., ROSIN P.L., MARTIN R.R., LANGBEIN F.C. Fast and Effective Feature-Preserving Mesh Denoising. Visualization and Computer Graphics, IEEE Transactions on, 2007, 925-938 [TAU95]

TAUBIN G. A Signal Processing Approach To Fair Surface Design. In SIGGRAPH ’95, 1995, 351-358

[TAU96]

TAUBIN G., ZHANG T., GOLUB G.H. Optimal surface smoothing as filter design. In Proceedings of the 4th European Conference on Computer Vision, 1996

[TAU00]

TAUBIN G. Geometric Signal Processing on Polygonal Meshes. In EUROGRAPHICS ’00, 2000

[TAUCS]

TOLEDO S., CHEN D., ROTKIN V. TAUCS - A Library of Sparse Linear Solvers [on-line]. [cit. 2014-05-02]. Dostupn´e na http://tau.ac.il/˜stoledo/taucs/

[VOLU]

OWEN K. Area and Volume Calculations [on-line]. [cit. 2014-0502]. Dostupn´e na http://www.gamedev.net/page/resources/ /technical/gameprogramming/area-and-volume-calculations-r2247

[VTK]

Kitware Inc. Visualization Toolkit [on-line]. [cit. 2014-03-02]. Dostupn´e na http://vtk.org

[WIKICT] Wikipedie, otevˇren´ a encyklopedie. Poˇc´ıtaˇcov´ a tomografie [on-line]. [cit. 201401-30]. Dostupn´e na http://cs.wikipedia.org/wiki/Poˇc´ıtaˇcov´a tomografie [WIKIMRI] Wikipedie, otevˇren´ a encyklopedie. Magnetick´ a rezonance [on-line]. [cit. 201401-30]. Dostupn´e na http://cs.wikipedia.org/wiki/Magnetick´a rezonance [XXWT06] XU K., XIONG Y., WANG Y., TAN K., GUO G. A simple and stable feature-preserving smoothing method for contours-based reconstructed meshes. In GRAPHITE ’06, 2006, 391-398 ˇ [ZBSF04]

ˇ ARA ´ ˇ B., SOCHOR J., FELKEL P. Modern´ı poˇc´ıtaˇcov´ Z J., BENES a grafika. Vyd. 1. Brno: Computer Press, 2004, 609 s., ISBN 80-251-0454-0.