三維模型的快速重建及簡化

三維模型的快速重建及簡化

1問題及解決策略

三維重構(gòu)的方法可分為面繪制與體繪制兩大類。依據(jù)兩類經(jīng)典算法的各自特點,針對醫(yī)學(xué)圖像數(shù)據(jù)的三維快速重構(gòu)與三維模型的簡化問題,利用面繪制方法,采用了移動立方體算法MC產(chǎn)生構(gòu)成三維體表面的三角面片;再采用Tri-angledecimation算法對生成的模型作約減,約減的目的是用較少的三角面片來保證顯示與處理的速度,用空間來換取時間。所提出的重建與組織同時生成的方法與具體算法,實現(xiàn)了三維模型的實時顯示和與用戶的快速交互。

2三維模型的快速重構(gòu)、組織與去噪

在三維模型重構(gòu)中我們選擇了文獻[1]提出的MC算法來提取三維等值面,MC算法遍歷所有立方體的頂點,將頂點的物理量值與等值面值相比較,從而確定頂點與等值面的位置關(guān)系,通過線性插值得到等值面與Cube的交點,依次遍歷所有的Cube,從而得到給定閾值的等值面。MC算法簡單有效,可以有效的應(yīng)用于密集數(shù)據(jù)場的三維表面模型重構(gòu),但MC算法在實際應(yīng)用中還存在一些問題[2]:1)MC算法產(chǎn)生的結(jié)果為散亂而又大量的三角面片;2)算法對數(shù)據(jù)場的密集度要求較高;上述兩點對三維模型重構(gòu)與組織的速度、對三維模型真實再現(xiàn)的效果及后繼的簡化處理的效率影響很大。

數(shù)據(jù)結(jié)構(gòu)描述

針對上述MC算法,采取將三角面片的生成與組織同步完成的方法思路,在實現(xiàn)中采用頂點-邊表的數(shù)據(jù)結(jié)構(gòu),即與某頂點共同組成一個三角形的邊置于該頂點的邊鏈中,邊鏈按順序存放。盡管這種頂點-邊表結(jié)構(gòu)會產(chǎn)生數(shù)據(jù)的冗余,同一個三角形被定義了3回,但這種結(jié)構(gòu)突出了對頂點數(shù)據(jù)的重視,使得對后繼處理尤其是約減處理帶來很大方便,由于時間是矛盾的焦點,我們采用空間換時間的方法。在頂點-邊表結(jié)構(gòu)中每一個頂點對應(yīng)兩個隊列:現(xiàn)存邊鏈和刪除邊鏈。頂點數(shù)據(jù)結(jié)構(gòu)中存放了該頂點的x,y,z坐標(biāo)和頂點的刪除次序。當(dāng)頂點的刪除次序為零時代表該點未被刪除。邊鏈中每一個Node由4部分組成:邊對應(yīng)的兩個下標(biāo),該邊的插入次序和刪除次序。需要注意的是頂點對應(yīng)的當(dāng)前邊鏈中邊是按順序存放的。對于上述結(jié)構(gòu)我們可以用類將其封裝起來,定義于其上的基本運算包括:插入頂點、刪除頂點、插入邊、刪除邊、插入三角面片、刪除三角面片、邊鏈順序整理。

三維模型的組織與快速重構(gòu)

將MC生成的每一個三角面片插入上述的頂點-邊表結(jié)構(gòu),需要兩步工作[3,4]:①三角面片三個頂點的定位與插入;②三角面片的插入。頂點的定位是三角面片插入的基礎(chǔ)。為快速的將MC生成的每一個三角面片插入上述頂點-邊表結(jié)構(gòu)中,待插入三角面片的三個頂點在頂點鏈中的定位的速度是關(guān)鍵因素,查找的速度直接影響三角網(wǎng)格生成組織的速度。由于一個三角面片只能與當(dāng)前處理立方體和周圍與該立方體相鄰的立方體中的三角面片有共同特點,在查找三角面片三個頂點時可以充分利用MC算法“活動的立方體”的特性,從而大大縮小頂點的搜索范圍,加速頂點的搜索定位過程。其算法步驟描述如下:1)分配緩沖區(qū)Buffer。假定搜索區(qū)域大小為X*Y*Z,緩沖區(qū)Buffer=newint[5*X*Y-2*]。Buffer包含了當(dāng)前層中所有Cube的邊。Buffer[i]存放的是該邊所包含的等值面中頂點的下標(biāo)。置其初值為零代表該邊不與等值面相交。2)在按層遍歷每一個Cube時,若某一Cube的某條邊與等值面存在交點,則計算交點所在的邊在Buffer中的下標(biāo)N,判斷Buffer[N]是否為零,若不為零,則Buffer[N]-1即為該點在頂點數(shù)組中的下標(biāo);若為零,則在頂點數(shù)組最后插入該頂點,并將該頂點在頂點數(shù)組中的下標(biāo)加1存入Buffer[N]。3)將三角面片的三條邊插入各自頂點的邊鏈。4)當(dāng)循環(huán)進入新的一層Cube時,更新Buffer。上述處理大大提高了頂點的定位效率,使得三角面片的生成與組織一步完成,節(jié)省了處理時間,提高了效率。組織后的三維模型為后繼處理帶來了很大的方便。

三維模型中噪聲點的去除

MC算法對數(shù)據(jù)場的密集度要求較高,實際應(yīng)用中由于一些醫(yī)學(xué)圖像層間數(shù)據(jù)密集度較低,造成了用MC算法提取等值面的過程中產(chǎn)生了一些像“臺階”一樣的中間層,影響了模型的真實再現(xiàn)。其實這些處于中間層上的點是由MC算法線性插值而得到的,但對生成的模型而言它們是噪點[5,6]。針對此問題,在具體實現(xiàn)過程中我們并沒有采取插值的方法增加原始數(shù)據(jù)的密集度,以消除算法產(chǎn)生的“臺階”,而是充分利用上述已經(jīng)得到的三維模型基礎(chǔ),方便的解決點去噪處理的問題。具體解決辦法是:①遍歷所有頂點,找出在輸入數(shù)據(jù)密集度較低方向上的處于中間層的頂點;②給找出頂點做刪除標(biāo)記;③對刪除頂點后得到的“洞”進行三角剖分處理,然后調(diào)整頂點-邊表結(jié)構(gòu);④重復(fù)1)到3)步,直到滿足的“中間層”頂點全部刪光。模型經(jīng)上述處理后,“臺階”自然不復(fù)存在,模型也“光滑”了,同時三角面片也得到相當(dāng)程度的減少。其實這種做法與先在各層求出等值輪廓線、再在相鄰兩層的等值輪廓線間通過三角剖分得到三維模型的方法相比有異曲同工之處。在后續(xù)的約減算法中,也需要利用三角剖分算法,所以在去噪工作中無須新增添代碼模塊,依賴于在約減之前對數(shù)據(jù)所作的預(yù)處理。

3三維模型的簡化與多分辨率模型的生成

由于繪制時間和存儲量與三角形的數(shù)目成正比,而MC算法產(chǎn)生的三角面片很多,約減至關(guān)重—222要。約減的方法很多,我們采用了基于TD算法的思路,TD算法是通過不斷刪去重要度低的頂點來完成約減過程,所以約減模型是在連續(xù)的變化,為此我們提出了一種適用于頂點刪除約減方法的多分辨率模型的生成算法,借助上述數(shù)據(jù)結(jié)構(gòu)和TD算法的特點,在約減的同時還保留了中間結(jié)果,從而產(chǎn)生了一個多分辨率模型,不僅方便用戶對所需模型不同程度的需求,而且提高了TD算法的效率。具體做法是:在每刪除一個頂點后,包含此頂點的三角形均被刪除,剖分后又有一批新的三角形被插入。在上述結(jié)構(gòu)中對三角面片的刪除具體表現(xiàn)為對邊的刪除,對三角形的插入體現(xiàn)為對邊的插入。設(shè)立了一個計數(shù)器,其初值為零。每刪除一個頂點之后計數(shù)器加1,并記錄在該頂點的刪除次序字段。刪除頂點之后會有一批三角面片被刪除和插入。當(dāng)邊被刪除時只將其移入刪除鏈,并不在邊鏈中物理刪除該節(jié)點,同時在該節(jié)點中記錄計數(shù)器的值。在刪除頂點后的對刪除后留下的“洞”進行剖分,將新產(chǎn)生的三角形的三條邊插入其對應(yīng)的頂點當(dāng)前邊鏈,同時在插入節(jié)點中記錄計數(shù)器的值。最后,調(diào)整當(dāng)前邊鏈中節(jié)點的順序。1)能很方便的判斷頂點類型,確定邊界頂點,邊界邊。2)在約減中通過頂點-邊表結(jié)構(gòu)能快速找到一個頂點周圍的所有鄰點。3)由于頂點周圍的邊均按序排列,加快了判斷頂點重要度和三角剖分的過程。等約減完成得到了該被簡化模型的多分辨率模型。這樣模型的減化與多個不同細(xì)節(jié)層次模型同時產(chǎn)生,大大節(jié)省了時間,提高了效率,但該方法對內(nèi)存的消耗過大,數(shù)據(jù)存儲量也相應(yīng)較大。在顯示模型時,可以根據(jù)用戶的需要動態(tài)調(diào)整模型的大小。由于每次頂點刪除總是刪去1到2個三角形,所以頂點的刪除順序與模型的大小有直接關(guān)系。在計算所需顯示的三角面片時,根據(jù)刪除的次序可以在頂點-邊表的一次遍歷中迅速定位在該頂點被刪除以前的模型包含的所有三角面片。4結(jié)果上述方法,適合于使模型連續(xù)變化、基于頂點刪除的約減,該算法產(chǎn)生多分辨率模型。操作系統(tǒng)為,開發(fā)工具