3D skeneri obično generiraju veliku količinu podataka o geometriji i atributima objekta. Geometrijski podaci opisuju oblik i dimenzije objekta, dok atributi opisuju svojstva površine kao što su boja, koordinate tekstura, temperaturu i sl. Višerezolucijski prikaz (ili analiza) efikasan je način za predstavljanje skupa podataka pri različitim razinama razlučivosti. U takvom prikazu početni skup podataka rastavlja se u niz aproksimacija i niz detalja. Svaka pojedina aproksimacija predstavlja početni skup podataka na pojedinoj razlučivosti. Skup detalja bilježi podatke izgubljene pri pojedinoj aproksimaciji. Glavna prednost višerezolucijskog prikaza je efikasnost u prikazu kao i računalna efikasnost. Višerezolucijski prikaz višefunkcionalan je alat i ima mnogobrojnu primjenu kao što su kompresija, uklanjanje šuma, editiranje i sl.

 

Progresivne mreže

 

Algoritmi opisani u ovom poglavlju koriste progresivne mreže s ograničenim kolapsiranjem bridova za frekvencijsku dekompoziciju. Ideju višerezolucijskog prikaza pomoću progresivnih mreža prvi put je predstavio Hugues Hoppe iz Microsofta na Siggraphu '96 [Hoppe96].

 

Modeli u računalnoj grafici vrlo često su prikazani upotrebom mreže trokuta. Geometrijski to je glatka linearna struktura koja se sastoji od trokuta spojenih zajedničkim bridovima. Detaljni modeli predstavljeni na ovaj način mogu se sastojati od stotina tisuća trokuta, pa je zbog njihove veličine takve modele vrlo problematično i vremenski zahtjevno prikazivati ili prenositi preko računalne mreže.

 

U rješavanju ovog problema Hoppes je predložio takvu optimizaciju mreže u kojoj bi se proizvoljna mreža M pohranila kao mnogo grublja mreža M⁰ zajedno s nizom od n zapis kako postepeno poboljšati mrežu M⁰ točno do razine početne mreže M= M^n.

Svaki od tih zapisa sadrži podatke povezane podjelom vrhova (engl. vertex split), elementarnom operacijom koja u mrežu dodaje jedan novi vrh. Takav prikaz naziva se progresivna mreža (PM). Možemo, prema tome, mrežu M u PM reprezentaciji zapisati kao niz mreža M^0, M¹, M²,..., Mⁿ sve veće točnosti.

 

Da bi se proizvoljna mreža M pohranila u progresivnom obliku, koristi se topološka transformacija koja se naziva kolapsom brida (edge collapse).

 

Slika 3-4. Ilustracija kolapsa brida.

 

Kao što se vidi na slici 3-4 transformacija kolapsa brida ecol ({v_s, v_t}), spaja dva susjedna vrha v_s i v_t u jedinstveni vrh v_s. vrh v_t, a dva susjedna trokuta {v_s, v_t, v_l} i {v_t, v_s, v_r} u toku procesa nestanu. Za novi, jedinstveni vrh v_s odredi se nova lokacija. Prema tome inicijalnu mrežu M =Mⁿ možemo pojednostaviti kroz niz od n sukcesivnih kolapsa bridova:

 

      

 

Konkretan izbor redoslijeda kolapsa bridova treba pažljivo odabrati, kako bi aproksimacije u pojedinim koracima (M^i, i<n) bile što kvalitetnije.

Ključna činjenica je da je operacija kolapsa brida reverzibilna. Inverzna operacija naziva se podjela vrhova (vrh split), koja je također prikazana na slici 3-4 podjela vrhova vsplit(s,l,r,t,A) u blizinu zajedničkog vrhova v_s dodaje novi vrh v_t i dva nova trokuta {v_s, v_t, v_l} i {v_t, v_s, v_r}. Ovakva transformacija također prepravlja atribute mreže u okolici transformacije (npr. poziciju vrhova v_s i eventualne diskretne i skalarne atribute mreže kao što su normale, koordinate tekstura i sl.).

Sada možemo prikazati mrežu M kao jednostavnu mrežu M⁰ i niz od n vsplit zapisa:

 

 

Oblik (M⁰, {vsplit₀,..., vsplit_n-1}) naziva se progresivni oblik mreže M.

 

Na slici 3-5 dan je primjer PM zapisa jedne proizvoljne mreže M.

 

 Slika 3-5. PM zapis proizvoljne mreže M. Modeli imaju (slijeva na desno) 150, 500, 1000 i 13500 trokuta.

Praun-Hoppeov algoritam

 

Osnovni uvjet da bi algoritam bio robustan, je da se vodeni žig pohrani što dublje u sam sadržaj objekta. Ideja ovog algoritma je da uz zadanu proizvoljnu mrežu trokuta v=(v₁,...v_n)^T i zadani vodeni žig w=(w₁... w_m)^T omogućimo da svaki od koeficijenata iz vodenog žiga w_i izazove mali pomak određenog podskupa vrhova. Taj pomak postiže se generalizacijom opisane ideje raspršenog spektra. Za svaki koeficijent w_i vodenog žiga, konstruira se po jedna skalarna funkcija baze . Tijekom proces umetanja vodenog, cilj je da se vrh v_j pomjeri za vektor proporcionalan s w_id_i, pri čemu je d_i vektor smjera pomaka, određen kao normala iz vrha c_j. Osnovni problem je kako odrediti bazne funkcije Φ=(φ¹ … φ^m).

 

 

Da bi cjelokupni ovakav model zaštite vodenim žigom bio robustan, bazne funkcije Φ moraju korespondirati vizualno značajnim odlikama modela, iz razloga opisanih u uvodu u ovo poglavlje. Kao što je već rečeno, kod 2D objekata to su DCT koeficijenti s najvećom amplitudom.

Pristup s progresivnim mrežama previđa da se odredi m kolapsa (odnosno m split operacija) koji uzrokuju najvidljivije promjene na modelu, odnosno najveću promjenu geometrije modela i te promjene označimo kao najvažnije. Za svaku takvu promjenu definira se po jedna bazna funkcija s područjem djelovanja na cijelom susjedstvu pripadajućeg vrhova u mreži M. Tih m baznih funkcija se tada upotrijebi za umetanje vodenog žiga od m članova.

 

Prvi korak algoritma je da se zadana mreža M pojednostavi prebacivanjem u PM prikaz, primjenom niza ograničenih kolapsa bridova. U svakoj takvoj operaciji po jedan brid se pretvara u jednu od svojih krajnjih točaka, kao što je prikazano na slici 3-6.

 

 

 

Slika 3-6. Prikazan je niz pojednostavljenja modela upotrebom kolapsa bridova. Crvenim obrubom prikazano je isto područje na modelima s različitim brojem bridova.

 

Veličinu promjene modela h nastale u pojedinoj operaciji podijele vrhova određujemo na način da predvidimo lokaciju na kojoj bi se mogao pojaviti novi vrh i onda izračunamo veličinu proporcionalnu udaljenosti predviđene i stvarne lokacije novog vrhova. Predviđenu lokaciju računamo kao koordinate centroida neposrednih susjeda vrhova koji se dijeli. Nakon toga izračunamo normalu na trokut u kojem se nalazila predviđena lokacija i konačno h izračunamo kao skalarni produkt vektora normale i vektora udaljenosti između predviđene i stvarne lokacije.

Nakon što smo odredili m podjela vrhova s najvećim h, možemo konstruirati m pripadajućih baznih funkcija φⁱ. Budući da se koristi ograničeni kolaps bridova, svaki vrh c_i koji se počne dijeliti u konačnici je povezan s skupom bridova u izvornoj mreži M koji su nastali zbog podijele tog vrhova i novih vrhova nastalih iz njega.

Susjedstvo B_i pripadajućeg vrhova c_i određujemo kao prsten rubova oko vrhova c_i koji se određuje tako da pratimo kako se šire neposredni bridovi vrha c_i tijekom postupka: .

Na slici 3-6 crvenim rubom označeno je susjedstvo vrha c_i u pojedinim koracima gore naznačenog postupka.

Susjedstva pojedinih baznih funkcija mogu se preklapati, kao što je to vidljivo na slici 3-7 gdje prikazan model s 50 baznih funkcija.

 

 Slika 3-7. susjedstva nad kojima su definirane funkcije φⁱ.

 

U svakom susjedstvu konstruira se radijalno simetrična bazna funkcija. Za početak, mora se odrediti funkcija radijusa  za svaki vrh v_j, takva da preslikava središnji vrh c_i u 0, a vrhove s granice B_i u 1, dok između linearno raste. Preciznije, za svaki vrh v_j definiramo funkciju preslikavanja u relativni radijus:

 

 

Pri tome je d(v, S) duljina najkraćeg puta između vrha v i bilo kojeg drugog vrha iz skupa S.

 

 

Udaljenosti d(v_j, {c_i}) i d(v_j,B_i) mogu se lagano izračunati primjenom Dijkstrinog algoritma na bridove mreže.

 

Dvije su bitne odlike važne kod konstrukcije baznih funkcija. Kao prvo promjene izazvane na 3D objektu ne bi smjele biti vizualno uočljive i kao drugo ne bi se smio mijenjati volumen objekta (što bi značilo da se dio objekta skalirao u nekom smjeru).

 

 

 Kako su poligonalne mreže i same po sebi C⁰ kontinuiteta, nije potrebno da bazna funkcija bude primjerice n kontinuirana, ali iskustveno je utvrđeno da ljudsko oko vrlo dobo zamjećuje diskontinuitete derivacija, tako da funkcije koje nemaju barem C¹ kontinuitet izazivaju vidljive distorzije na modelu. Da bi se eliminirali te te diskontinuitete može se upotrijebiti polinom trećeg stupnja =2*r³-3*r³+1 koji ima oblik polucilindra (slika 3-8).

Kako je na početku postavljeno još jedno ograničenje da bazna funkcija ne smije mijenjati volumen objekta, integral funkcije unutar radijusa  mora biti 0. To rezultira funkcijom koja liči na sombrero. Da bi se takva funkcija izgladila, postavljen je dodatni uvjet da druga derivacija u vrhu bude 0, čime je dobiven konačni oblik funkcije =-21*r⁵ + 45*r⁴ – 25*r³ +1. Sve tri funkcije i njihovo djelovanje na vrhove unutar relativnog radijusa r prikazane su na slici 3-8.

 

Slika 3-8 Moguće bazne funkcije i njihovo djelovanje na model.

Postupak umetanja vodenog žiga

Slika 3-9. Pomak svakoj pojedinog vrha v_j određen je zajedničkim utjecajem svih baznih funkcija unutar čijih se dosega nalazi vrh. (odnosno ako su unutar relativnog radijusa manjeg ili jednakog 1).

 

Svaka bazna funkcija množi se pripadnim koeficijentom w_i iz vodenog žiga. Koeficijenti w_i su realni brojevi, dobiveni slučajno odabrani po normalnoj razdiobi s srednjom vrijednošću 0 i standardnim odstupanjem (varijancom) 1.

U matričnom zapisu, umetanje vodenog žiga možemo zapisati ovako (za X koordinatu):

 

 su X koordinate dobivene nakon umetanja vodenog žiga.

 v_x su X koordinate vrha v u nemodificiranom (izvornom) objektu.

 ε je korisnički zadan parametar koji služi za skaliranje energije vodenog žiga.

 Φ je n x m matrica čiji su stupci skalarne funkcije φⁱ

 h_id_ix je m x m dijagonalna matrica čiji su elementi X komponente vektora smjera d_i, skalirane veličinom bazne funkcije h_i koja određuje veličinu utjecaja pojedine bazne funkcije

w je vektor stupac vodenog žiga

 

 

Ako konkateniramo matrice za sve prostorne komponente (X,Y,Z) proces umetanja vodenog žiga možemo opisati matričnom jednadžbom:

 

v_{' =} v + B w

 

Izvorni model w, zajedno s vodenim žigom w¸ pohrani se na sigurno mjesto, a dokument v_' sa umetnutim vodenim žigom se objavi.

 

Dohvat vodenog žiga

Prije nego što pokušamo dohvatiti vodeni žig iz sumnjivog dokumenta, moramo obadva dokumenta postaviti u isti koordinatni prostor (i prema potrebi ponovno uzorkovati kako bi dobili model s geometrijom modela koji ispitujemo i topologijom našeg originalnog dokumenta).

Upotrebom istog skupa baznih funkcija tj. matrice B, iz gornje jednadžbe kojom je opisano umetanje vodenog žiga dobivamo :

 

B w^* =(v^*-v)

 

Izraz na desnoj strani ove jednakosti opisuje pomak vrhova sumnjivog modela u odnosu na naš originalni dokument. Rješavanjem te jednadžbe dobivamo koeficijente w^* koje usporedimo s koeficijentima w našeg pohranjenog vodenog žiga.