| FER / ZEMRIS / RG | Vizualizacija medicinskih podataka putem Interneta |
|
Početak Uvod Zahtjevi Arhitektura Uzorkovani podaci Vizualizacija Zapis 3D modela Primjeri Sažetak Zaključak Reference Autor Abstract |
Vizualizacija |
|
Ideja algoritma pokretne kocke (engl. Marching cubes) Algoritam pokretne kocke [7] (engl. The Marching cubes) koristi se za generiranje 3D modela iz volumnog podataka (niz slika generiranih uređajem za uzorkovanje). Postupak se nalazi u skupini algoritama koji se nazivaju „Izdvajanje područja istih vrijednosti“ (engl. Isosurface rendering). Algoritam je, i danas gotovo 20 godina nakon prvog predstavljanja, još uvijek najbolji za generiranje 3D modela iz niza slika. U samom početku algoritam je predstavljen kao efikasan način generiranja 3D modela dijelova ljudskog tijela na temelju CT i MR slika. To su rasterske slike koje dolaze u nizovima. Presijecanje punog valjka paralelnim ravninama daje rezove (engl. Slices) R1 i R2 (Slika 14.). Udaljenost između ravnina je d. Desno na slici vidimo dva kvadrata koji predstavljaju ravnine. Na ravninama možemo vidjeti dva kruga koji predstavljaju skup točaka u kojima ravnina presijeca valjak. Ovaj primjer prikazuje način na koji se dobivaju CT slike. Izlazi su upravo ravnine tj. slike na kojima je prikazana struktura ljudskih kostiju i tkiva. Na CT slici nema izraženih linija već je sve predstavljeno točkama u nijansama sive boje. Nijansa se dobiva u ovisnosti o gustoći tkiva i na temelju nje se prepoznaje tkivo, kost ili nešto drugo. Prostor između rezova R1 i R2 podijeljen je na jednake dijelove, kocke (Slika 15.). Od tud dolazi i naziv samog algoritma „pokretne kocke“. Algoritam na temelju vrijednosti u vrhovima kocaka, linijama unutar rezova, određuje točke koje zatim postaju vrhovi poligona koji trebaju biti dodani (Slika 16.) .
Slika 14. Volumni podatak nastao uzorkovanjem.
Slika 15. Kocke nadopunjuju prostor između rezova.
Slika 16. Algoritam pokretne kocke prostor nadopunjuje poligonima. Pokretni kvadrati (engl. Marching squares) Da bi se lakše shvatilo kako se određuju poligoni koji se određuju unutra jedne kocke algoritam se pojednostavlja na kvadrate u 2D prostoru. Na slici 17. prikazana je elipsa koju treba prikazati linijama. Zeleni kvadrat predstavlja jedinični kvadrat.
Slika 17. Elipsa u 2D prostoru. Algoritam koristi interpolaciju između vrhova jediničnog prostora tako da se na rubu dobije točka koja predstavlja točno mjesto na kojem krivulja siječe rubove prostora.
Slika 18. Rekonstrukcija elipse sa i bez interpolacije. Ako je jedinični prostor relativno rijedak, generirani model odstupa u velikoj mjeri od originala (Slika 19.).
Slika 19. Rekonstrukcija elipse u slučaju rijetkog jediničnog prostora. Kod algoritma pokretni kvadrati kao i kod algoritma pokretne kocke najvažniji pojam je vrh unutar tj. vrh izvan prostora krivulje. Kada nemamo zatvorene krivulje u rezu, već se radi o tonovima boja, koristimo vrijednost praga (istovrijedne točke) kao parametar koji to određuje. Točkama su označeni vrhovi jediničnih prostora koji se nalaze unutar elipse. Na temelju tih točaka algoritam odlučuje kako će se iscrtati dotični jedinični prostor. Kod algoritma pokretnih kvadrata postoji 16 mogućnosti (Slika 20.). Te mogućnosti govore koji rubovi se sijeku.
Slika 20. Slučajevi jediničnih prostora u algoritmu pokretni kvadrati. Na temelju nekog od 16 slučajeva određuje se koji rubovi ulaze u interpolaciju. Uglavnom se koristi linearna interpolacija.
Slika 21. Linearna interpolacija dvije točke.
Gdje su:
Pokretne kocke (engl. Marching cubes) Sve što je prikazano u prošlom odlomku vrijedi i za 3D prostor. Razlika je naravno u trećoj dimenziji i većem broju mogućih slučajeva. U 2D prostoru postoji 16 mogućih slučajeva, a u 3D prostoru postoji 256 različitih slučajeva. Tih 256 slučajeva može se svesti u 15 porodica (Slika 22.). Sve ostale kombinacije dobivaju se rotacijom i komplementiranjem.
Slika 22. 15 porodica kocki u algoritmu pokretne kocke. Primjena algoritma pokretne kocke Algoritam pokretne kocke za generiranje 3D modela kao ulazne podatke koristi volumni podatak i vrijednost praga tj. numeričku vrijednost koja predstavlja razinu sive boje (Slika 23.). Određivanje pravilne vrijednosti praga izvodi se na temelju 1D histograma (Slika 24).
Slika 23. Arhitektura algoritma pokretne kocke.
Slika 24. Selekcija razine sive na 1D histogramu.
Modificirani algoritam pokretne kocke Selekcija i izdvajanje područja na temelju 2D spojnog histograma (Slika 25.) nije moguća primjenom originalnog algoritma pokretne kocke.
Slika 25. Funkcija prijenosa (engl. transfer function) predstavljaju moguće rješenje. Funkcije transfera na temelju ne samo jednog parametra (npr. vrijednost praga) već i nekih drugih (npr. prva derivacija) omogućuju segmentaciju željenog organa tj. područja. Ovim radom željelo se ispitati postoji li mogućnost primjene funkcije transfera koje su inicijalno zamišljene za korištenje u prikazu volumena (engl. Volume rendering) na postupak pokretne kocke. Implementacija funkcije transfera navodi na modifikaciju algoritma pokretne kocke. Implementaciju je moguće izvesti na dva načina:
U radu je isprobana tehnika pretprocesiranja podataka tj. primjena funkcije transfera i sama takva tehnika spada u područje segmentacije unutar procesiranja slike. Razlika je što se volumni podataka ne mijenja nego se generira dodatno polje koje je veličine volumnog podataka, ali se vrijednosti predstavljaju s istinom ili neistinom (engl. Boolean). Na taj način omogućeno je korištenje algoritma pokretne kocke na način koji je zamišljen od svojih autora uz dodatnu mogućnost izdvajanja područja na temelju više parametara tj. transfer funkcija (Slika 26.).
Slika 26. Ulazni podaci modificiranog algoritma pokretne kocke. Modificirani algoritam ne provjerava pripadnost točaka izdvojenom području već se taj podatak dobiva kao rezultat primjene funkcije transfera kroz postupak segmentacije. Vrijednost praga predstavlja ulazni podatak u modificirani postupak pokretne kocke jer se koristi u postupku interpolacije. Kasnije će se pokazati da, u slučaju izdvajanja raspršenog područja na temelju funkcije transfera, vrijednost praga predstavlja problem i potrebno je na neki način volumni podatak promijeniti uz promjenu same vrijednosti praga. Izdvajanje područja na temelju transfer funkcija dovodi do problema interpolacije unutar algoritma pokretne kocke. Pravilne točke poligona, koje se generiraju algoritmom pokretne kocke, generiraju se primjenom inverzne interpolacije gdje se traži točka na rubu kocke čija vrijednost odgovara vrijednosti praga. U slučaju rada sa 2D spojnim dijagramom vrijednost praga zapravo više i ne postoji. Moguća rješenje problema su sljedeća:
Ideja koja se prezentira ovim radom je razdvajanje pomoću Gaussa tj. separacija primjenom Gaussa. Iz procesa segmentacije generira se izdvojeno područje. Izdvojeno područje zapravo je prostorni podatak koji govori koje su točke volumnog podatka proglašene unutarnjima, a koje vanjskima. Grade se 2 nova polja veličine volumnog podatka tj. izdvojenog područja. Polja se nazivaju „polje unutarnjih točaka“ i „polje vanjskih točaka“ (Slika 27.).
Slika 27. Ulazni podaci modificiranog algoritma pokretne kocke. Primjena separacije Gaussom preferira velika izdvojena područja oko kojih se generira veće područje nego je to slučaj kod jedne izdvojene točke u okolici neizdvojenih (Slika 28.). Separacija Gaussom smanjuje učinak terasastih područja (Slika 29.). Metoda koja se u ovome radu naziva „separacija Gaussom“ pokazala je neke dobre rezultate i učinke na 3D modelu. Njezinu primjenu i mogućnosti treba dodatno ispitati na više primjera.
Slika 28. Ulazni podaci modificiranog algoritma pokretne kocke.
Slika 29. Ulazni podaci modificiranog algoritma pokretne kocke.
|
|
|
Bojan Blažona - Računalna grafika - ZEMRIS - 2004/05 |
|
