【文章內(nèi)容簡介】 比較清晰的等值面圖像，而且可以利用現(xiàn)有的圖形硬件實(shí)現(xiàn)繪制功能，是圖像生成和變換的速度加快。因此，這是一類常用的可視化方法。第二類算法并不構(gòu)造中間幾何圖元，而是直接由三維數(shù)據(jù)場產(chǎn)生屏幕上的二維圖像，稱為體繪制（Volume rendering）算法或者直接體繪制算法（Direct Volume Rendering）算法。這種方法直接對待重建數(shù)據(jù)進(jìn)行處理，可以產(chǎn)生三維數(shù)據(jù)場的整體圖像，包括每一個細(xì)節(jié)，并具有圖像質(zhì)量高，便于并行處理等優(yōu)點(diǎn)。它存在的主要問題是：計算量太大，難于利用傳統(tǒng)的圖像硬件加速繪制，因而計算時間較長，不適合交互顯示。. 等值面抽取算法等值面抽取算法構(gòu)造出來的可視化圖形雖然不能反映整個原始數(shù)據(jù)場的全貌和細(xì)節(jié)，但是可以對感興趣的等值面產(chǎn)生清晰的圖像，而且可以利用現(xiàn)有的圖形硬件實(shí)現(xiàn)繪制功能，速度較快，適合實(shí)時交互，因而得到了廣泛的應(yīng)用。在三維空間規(guī)則數(shù)據(jù)場種構(gòu)造等值面的方法很多，大概可以分為兩類：一類是輪廓拼接。它先將三維數(shù)據(jù)場從Z方向分解成若干層二維數(shù)據(jù)，然后從二維數(shù)據(jù)里面提取出輪廓線，最后把一系列的二維輪廓線拼接成三維模型。另一類方法直接從三維數(shù)據(jù)場抽取出等值面，其中最有代表性的是Marching Cubes(MC)算法。這一方法原理簡單，易于實(shí)現(xiàn)，目前已經(jīng)得到了廣泛的應(yīng)用。屬于這一類方法的還有離散Marching Cubes算法，Marching Tetrahedra算法和剖分立方體算法[9]。. Marching Cubes(MC)算法Marching Cubes算法是一種應(yīng)用很廣泛的由體密度數(shù)據(jù)重構(gòu)三維等值面的方法，于1987年由Lorensen和Cline 兩人提出。處理的對象一般是CT，或是MRI 圖像。數(shù)據(jù)點(diǎn)都位于網(wǎng)格點(diǎn)上，一般適用于灰度圖，這樣可以明確給出閾值。它的目的是從這樣的體數(shù)據(jù)中抽取出三維結(jié)構(gòu)的邊界面，但它不是像二維中追蹤等值線一樣需要鄰接關(guān)系，而是孤立的看待每一個體元，由體元八個頂點(diǎn)的數(shù)據(jù)值來得到在該立方體內(nèi)的邊界面，以三角面片的形式來表示。1. 基本原理 圖 。8個數(shù)據(jù)點(diǎn)位于該體元的8個定點(diǎn)上。 對于一個體元（立方體）來說，給定等值面的閾值后，立方體的每個頂點(diǎn)要么在等值面外，要么在等值面內(nèi)。我們規(guī)定：1）如立方體頂點(diǎn)的數(shù)據(jù)值≥等值面的值，則定義該頂點(diǎn)位于等值面之外，記為“0”；2）如立方體頂點(diǎn)的數(shù)據(jù)值＜等值面的值，則定義該頂點(diǎn)位于等值之內(nèi)，記為“1”。頂點(diǎn)狀態(tài)有2的8次方256種可能的情況。然而從拓?fù)涞慕嵌葋砜?，?jīng)過反轉(zhuǎn)和旋轉(zhuǎn)變換之后只有15 種不同的情況（）。圖中還顯示了在該種拓?fù)錉顟B(tài)下立方體內(nèi)的等值面的定性情況（以三角面片表示）。確定體元狀態(tài)之后，使用線性插值求出等值面和體元邊界的交點(diǎn)，之后將這些交點(diǎn)連接成三角形，作為等值面的一部分。為了利用圖形硬件顯示等值面圖像，必須給出組成等值面的三角形面片的法向。MC算法采用中心差分求體元各角點(diǎn)處的梯度，然后在體元邊界上再次采用線性插值求交點(diǎn)的梯度，也就是各三角形頂點(diǎn)的法向。為了消除三角面片之間明暗度不連續(xù)變化，三角面片采用Gourand模型繪制?？傊琈C算法的流程如下：將三維離散規(guī)則數(shù)據(jù)場分層讀入內(nèi)存；掃描兩層數(shù)據(jù)，逐個構(gòu)造體元，每個體元8個頂點(diǎn)來自相鄰的兩層；將體元每個交點(diǎn)的函數(shù)值和給定的等值面做比較，根據(jù)比較結(jié)果，構(gòu)造該體元的狀態(tài)表；根據(jù)狀態(tài)表，得出與等值面由交點(diǎn)的體元邊界；通過線性插值方法，計算出體元邊界和等值面的交點(diǎn)；利用中心差分方法，求出體元各個頂點(diǎn)處的法向，通過線性插值方法，求出三角形各個頂點(diǎn)處的法向；根據(jù)三角形面片和各個頂點(diǎn)的坐標(biāo)值和法向量繪制等值面圖像。2． 存在問題：二義性在MC算法中，在體元的一個面上，如果值為1的頂點(diǎn)和值為0的頂點(diǎn)分別位于對角線的兩端，就會含有兩種可能的連接方式，因而存在著二義性[10]。這樣的面稱為二義性面，包含二義性面的體元稱為具有二義性的體元。一個體元可能包含多個二義性面。3. 消除二義性：MC方法的二義性問題如果不解決，將造成等值面連接上的錯誤。人們也提出了幾種不同的判別和消除二義性的方法，其中以漸近線法最為常用。一般情況下，等值面和體元邊界所在平面的交線是雙曲線。 在該圖所列的四種狀態(tài)中，當(dāng)雙曲線的兩支均與某邊界面相交時，就產(chǎn)生了連接方式的二義性。這時，雙曲線的兩支將邊界面劃分成3個區(qū)域。雙曲線的兩條漸近線的交點(diǎn)坐標(biāo)是：當(dāng)出現(xiàn)二義性時，需要計算f(X,Y,Zo)的值，如果f(X,Y,Zo)Co，則漸近線的交點(diǎn)應(yīng)該與函數(shù)值大于Co的對角點(diǎn)落在同一區(qū)域內(nèi)。 如果f(X,Y,Zo)Co，則漸近線的交點(diǎn)應(yīng)該與函數(shù)值小于Co的對角點(diǎn)落在同一區(qū)域內(nèi)。 這就是當(dāng)出現(xiàn)二義性的時候，交點(diǎn)之間的連接規(guī)則。，第0，1，2，4，5，8，9，11，14這9種情況不存在二義性。第3，6兩種情況各存在一個二義性面，因此各有兩種連接方式。第10，12兩種情況，各存在兩個二義性面，因此各有四種諒解方式。第7種有3個二義性面，因而有8種連接方式。第13種情況有6個二義性面，因而有64種連接方式。以上各種情況加在一起，共有93種不同的連接方式。. Discretized Marching Cubes 算法離散Marching Cubes算法（簡記為DiscMC）是C. Montani, R. Scateni Cubes的改進(jìn)算法[11]，它將三維表面的重構(gòu)和簡化過程融為一體，在等值面的生成過程中就自適應(yīng)的完成了面片合并。與其它簡化算法相比，DiscMC 具有算法效率高、簡化比例高，損失精度小等優(yōu)點(diǎn)。同時，DiscMC 還采用了非常簡捷的辦法解決了經(jīng)典Marching Cubes算法中的二義性問題。經(jīng)典Marching Cubes算法直接根據(jù)體元頂點(diǎn)的內(nèi)外狀態(tài)構(gòu)造出三角面片，這些三角面片的頂點(diǎn)是根據(jù)所在邊的兩個頂點(diǎn)的密度值通過插值計算得出。DiscMC 則把整個過程分成三步：(1) 掃描(Marching)：首先，所有與等值面相交的體元被逐一掃描，根據(jù)其八個頂點(diǎn)的內(nèi)外狀態(tài)按照規(guī)定好的方式生成三角面片。在這一步中，所有生成的三角面片只是用它所在體元的位置和其形態(tài)的編號進(jìn)行記錄，并不計算實(shí)際的頂點(diǎn)坐標(biāo)值。也就是先假設(shè)所有的三角形面片的頂點(diǎn)只可能落在立方體體元邊界的中點(diǎn)和體元中心點(diǎn)這13個地方，因而生成的三角形面片的形狀是個數(shù)有限的。(2) 合并(Merging)：三角面片生成后，將凡是位于同一平面并且相鄰的三角面片合并，形成大的多邊形，隨后，大的多邊形又被重新劃分為三角形。(3) 插值(Interpolating)：DiscMC 的最后一個步驟是通過線性插值計算出最后所得的三角面片的頂點(diǎn)坐標(biāo)，這一步和經(jīng)典的MC 算法是相同的。離散Marching Cubes算法中“離散”的思想就是延后插值計算，之前生成的三角面片全部用離散值來表示，也就是說，三角面片所處平面的位置、方向，在所處體元中的位置、形態(tài)全部都是離散量，僅有有限數(shù)目的可能取值。步驟一、掃描根據(jù)以上的思想，在第一個步驟——掃描的過程中，所生成的三角面片的頂點(diǎn)在一個體元中只有13 個可能位置（每條邊的中點(diǎn)12個，外加體元中心點(diǎn)）。當(dāng)然，如果考慮平面的法向方向，則一共是26 種。DiscMC 。在掃描過程中，三角面片生成后就馬上根據(jù)其所處的平面方向和位置存儲在一個兩層的鏈表結(jié)構(gòu)中。第一個層次存儲26個不同的平面方向，每個元素指向另一個鏈表，該鏈表存儲了這個方向上的一系列平行的平面。第二個層次上每一個元素均是一個鏈表，存儲該平面上的已生成的三角面片，這樣存儲的三角面片只需用它在該平面上的位置信息記錄即可，這樣也便于后面合并過程的進(jìn)行。步驟二、合并DiscMC 的核心是三角面片合并這一步，合并的目的是將所有鄰接且位于同一平面的三角面片合并成大的多邊形，再將得到的多邊形劃分為盡可能大的凸多邊形，最后再將得到的凸多邊形劃分成三角形。這樣，合并過程又可以分為三個子步驟：(1) 合并、(2) 分割、(3) 三角形劃分。下面將以z=c平面為例描述這一過程。(1) 合并是將掃描步驟中產(chǎn)生的在同一平面又相鄰的小三角面片合并，形成大的多邊形。在合并過程中，每一個在掃描過程中形成的統(tǒng)一平面上的三角面片被重新以“異或”模式寫入一個二維數(shù)組，這樣，這些三角面片就自然而然的“合并”了，數(shù)組中僅剩下合并后多邊形的邊界。另外，所有三角面片的水平邊也不需要記錄，只要記錄垂直邊和斜邊就足可以表示多邊形的邊界了。(2) 分割是將合并得到的多邊形分割為一個個小的凸多邊形，以便進(jìn)行下一步的三角形分割。為了方便起見，凸多邊形的分割是按水平方向進(jìn)行的自上而下進(jìn)行的。分割完成后，每個凸多邊形的信息便從二維數(shù)組中提取出來，按照逆時針的順序?qū)⑵漤旤c(diǎn)存儲在一個鏈表中。(3) 三角形劃分是將分割得到的各個凸多邊形最后化分為三角形，形成三角面片網(wǎng)格模型。步驟三：插值節(jié)點(diǎn)的坐標(biāo)值最終通過線性插值計算出來，這一步同經(jīng)典的Marching Cubes算法是一樣的。從上述的算法描述中可以看出，DiscMC 具有以下特點(diǎn)：(1) 由于DiscMC 算法的主要部分是基于離散值的，耗時的插值計算量被降至了最低，故而算法效率很高，這在后面的實(shí)驗結(jié)果中也得到了驗證。(2) 簡化比例高，由于凡是位于同一平面且相鄰的三角面片都進(jìn)行合并，所以如果初始三維表面比較平坦，可以達(dá)到很高的簡化比，并保持有限的精度損失。(3) 可以保持細(xì)微結(jié)構(gòu)，只要某細(xì)微結(jié)構(gòu)在第一次的掃描中能夠體現(xiàn)出來，則它就不會被DiscMC 的簡化過程所破壞，這也是DiscMC 優(yōu)于其他簡化算法的地方。. Marching Tetrahedra算法和剖分立方體算法Marching Tetrahedra（MT）方法是從MC方法的基礎(chǔ)上發(fā)展起來的。 該方法首先剖分立方體體元為四面體，然后在其中構(gòu)造等值面。這種方法的優(yōu)點(diǎn)有：首先，由于四面體是最簡單的多面體，其它類型的多面體都能剖分成四面體，因而具有廣泛的應(yīng)用背景。其次，將立方體剖分成四面體后，在四面體中構(gòu)造的等值面的精度顯然比在立方體中構(gòu)造的等值面要高。剖分立方體算法和MC算法一樣，對數(shù)據(jù)場中的體元逐層、逐行、逐列的進(jìn)行處理。當(dāng)某一個體元8個頂點(diǎn)的函數(shù)值均大于（或者均小于）給定的等值面的數(shù)值時，就表明等值面不通過該體元，因而不予處理。當(dāng)某一個體元8個頂點(diǎn)的函數(shù)值中有的大于等值面的值，有的小于等值面的值，而此體元在屏幕上的投影又大于象素時，則將此體元沿x，y，z三個方向進(jìn)行剖分直至其投影小于等于象素后，在對所有剖分后的小體元的8個頂點(diǎn)進(jìn)行檢測。當(dāng)部分頂點(diǎn)的函數(shù)值大于等值面的值，部分頂點(diǎn)的函數(shù)值小于等值面的值時，將此小體元投影到屏幕上，形成所需要的等值面圖像。. 輪廓拼接由一個序列的二維輪廓線重構(gòu)三維形體有著廣泛的應(yīng)用。在我們的三維重建軟件中，如果CT或者M(jìn)RI圖像兩層之間的切片距離遠(yuǎn)遠(yuǎn)大于圖像的分辨率，也就是Z方向的采樣十分稀疏，或者，由于目前的圖像分割技術(shù)不能完全準(zhǔn)確的分割出共存于二維圖像中的不同物質(zhì)，往往需要人工干預(yù)，由醫(yī)學(xué)專家勾劃出感興趣的區(qū)域，這種時候就需要從一個序列的二維輪廓重構(gòu)出三維形體。1. 單、凸輪廓線之間的三維形體重構(gòu)假設(shè)兩相鄰平面上各有一輪廓線（）。 上輪廓線上的點(diǎn)列為P(0),P(1),P(2)…P(m1)；下輪廓線上的點(diǎn)列為Q(0),Q(1),Q(2)…Q(n1)。 點(diǎn)列均按照逆時針方向排列。 如果將上述點(diǎn)列分別依次用直線連接起來，則得到這條輪廓線的多邊形近似表示。連接上輪廓線上一點(diǎn)和下輪廓線上一點(diǎn)的線段稱為跨距。很顯然，一條輪廓線線段和它兩端端點(diǎn)與相鄰輪廓線上的一點(diǎn)相連的兩段跨距構(gòu)成了一個三角面片，稱為基本三角面片。如何確定上輪廓和下輪廓的連接辦法？ ，并假定優(yōu)化的目標(biāo)是兩平行平面的輪廓線之間連接生成的表面面積最小[12]。 同樣有人提出了別的優(yōu)化目標(biāo)，比如使得兩平行平面的輪廓線之間連接生成表面所包圍的體積最大[13]。 但是無論哪一種目標(biāo)函數(shù)都需要全局搜索策略來求解，盡管已經(jīng)提出了不少算法，但是效率不高。基于局部計算和決策的啟發(fā)式方法和上述方法不同，它不要求全局最優(yōu)，而是基于局部計算來決定當(dāng)前的選擇。它得到的似近似最優(yōu)解，計算量小，速度快，實(shí)例效果尚可。比如：最短對角線法[14]，假如當(dāng)前已經(jīng)確定P(i)Q(i)為跨距，在選擇P(i)Q(i+1)還是P(i+1)Q(i)作為下一個跨距的時候，只需要選擇其中距離小的就可以。這種方法簡單，容易實(shí)現(xiàn)，當(dāng)上下兩條輪廓線的大小和興致相近，對中情況較好是，效果不錯。為了使得該算法能夠適應(yīng)更加復(fù)雜的情況，可以將上下兩條輪廓線都變換到以統(tǒng)一原點(diǎn)為中心的單位正方形里面，從而較好的保證了大小和形狀相似，并使得對中情況較好。在變換后的輪廓線之間連接好三角面片之后，需要進(jìn)行反變換，將各輪廓線變換到原來的位置。最大體積法這種方法和上面的最短對角線法的思路和步驟一致，只是在選擇下一個跨距的時候，把選擇標(biāo)準(zhǔn)改成選擇所圍體積較大者相鄰輪廓線同步前進(jìn)法[15]這個方法和上述兩種方法也很相似，只是在選擇下一個跨距的時候，把選擇標(biāo)準(zhǔn)改成：盡量使得上下兩輪廓線中已經(jīng)連接過三角面片的輪廓線線段長度占該輪廓線所有線段長度的比例保持一致。2. 非凸單輪廓線之間的三維形體重構(gòu)當(dāng)相鄰兩輪廓線之間其中之一為非凸輪廓線的時候，構(gòu)造兩輪廓線之間的可接受表面要復(fù)雜一些，上述三種方法都很容易出現(xiàn)錯誤的結(jié)果。實(shí)現(xiàn)非凸輪廓線之間的三角面片重構(gòu)比較好的方法是首先將非凸輪廓線變換為凸輪廓線，在凸輪廓線之間構(gòu)造好三角面片之后，再將其反變化為非凸輪廓線[16]。變換的過程首先是遞歸求出封閉輪廓線的所有非凸輪廓線點(diǎn)集。，首先求得輪廓線P的凸包E={1,2,4,8,9}，P和E之間的差為兩個凹區(qū){2,3,4}和{4,5,6,7,8}，對這兩個凹區(qū)繼續(xù)進(jìn)行分解，直到所有分解出來的點(diǎn)集都是凸的為止。接著，非凸輪廓線的變換從樹形結(jié)構(gòu)的葉子開始，自底向上，逐級消除非凸輪廓線的基本凹區(qū)，最后形成一條凸輪廓線。針對上面例子，對凹區(qū){2,3,4}處理的步驟