葉含笑 高智峰 江依法

摘要： 詳細介紹了MC算法，提出了優(yōu)化網(wǎng)格模型簡化算法。優(yōu)化網(wǎng)格模型簡化算法選取坐標點的原則是，盡可能地接近原始網(wǎng)格，通常采用子集選擇法或優(yōu)化選擇法。在盡可能保證圖像精度的前提下，優(yōu)化網(wǎng)格模型簡化算法可以提高運算速度，而單純的網(wǎng)格算法由于失真嚴重而缺乏實用價值?；隗w繪制的網(wǎng)格化簡化算法重建的三維模型比較完全，且算法簡單，在多排螺旋CT等醫(yī)學(xué)圖像三維重建中有較好的應(yīng)用。

關(guān)鍵詞： 三維重建； 移動立方體算法； 面繪制

中圖分類號：TP文獻標志碼：A文章編號：1006-8228（2012）04-12-03

Application of improved MC algorithm in 3-D reconstruction of medical image

Ye Hanxiao1, Gao ZhiFeng2, Jiang Yifa1

（1. Zhejiang Chinese Medicine University， Hangzhou， Zhejiang 310053， China； 2. Zhejiang XinHua Hospital）

Abstract： 3D reconstructions has been widely used in the field of medical disease diagnosis and Marching Cube algorithm (MC) is the most representative structure in the face of 3D reconstructions. The authors introduce in the paper the principle of MC algorithm, and present a simplified algorithm based on optimized grid model. The simplified algorithm selects points as close to original grid as possible, usually using the subset selection method or the optimized selection method. To ensure the best possible result in image accuracy, the simplified algorithm will improve the computation speed, while the pure grid algorithm is not practical due to serious distortion.The experiments show that the simplified algorithm based on optimized grid is better than pure grid algorithm in 3D reconstruction, and has better application in the reconstruction of multiple detector-row CT images.

Key words： 3d reconstruction； Mobile cube algorithm； Volume rendering

0 引言

醫(yī)學(xué)圖像三維重建技術(shù)最早可以追溯到20 世紀70 年代初。由于集成三維重建平臺的醫(yī)學(xué)影像設(shè)備價格昂貴等客觀原因，國內(nèi)醫(yī)學(xué)圖像三維可視化診斷起步較晚，到90年代某些高校才開始進行各層面上的研究[1]。隨著計算機技術(shù)的發(fā)展，短短幾年，三維重建技術(shù)已成為人們探索生命奧秘，以及疾病診斷、手術(shù)規(guī)劃的重要手段。

1 常見的醫(yī)學(xué)三維重建素材

電子計算機斷層掃描Computed tomography，簡稱CT，是電子計算機和X線相結(jié)合的一項新穎的診斷新技術(shù)。其主要特點是具有高密度分辨率，比普通X線照片高10～20倍[2]。CT能準確測出某一平面各種不同組織之間放射衰減特性的微小差異，并以數(shù)字圖像方式顯示，能極其精細地區(qū)分出各種軟組織的不同密度，從而形成對比。例如，頭顱X線平片不能區(qū)分腦組織及腦脊液，但CT不僅能顯示出腦室系統(tǒng)、還能分辨出腦實質(zhì)的灰質(zhì)與白質(zhì)。CT如再引入造影劑以增強對比度，其分辨率更為提高，可加寬疾病的診斷范疇，提高診斷正確率。

磁共振成像Magnetic Resonance Imaging ，簡稱MRI。磁共振成像是斷層成像的一種，它利用磁共振現(xiàn)象從人體中獲得電磁信號，并重建出人體信息。1946年斯坦福大學(xué)的Flelix Bloch和哈佛大學(xué)的Edward Purcell各自獨立發(fā)現(xiàn)了核磁共振現(xiàn)象。1972年P(guān)aul Lauterbur 發(fā)展了一套對核磁共振信號進行空間編碼的方法，這種方法可以重建出人體圖像。磁共振成像技術(shù)與其他斷層成像技術(shù)有一些共同點，比如它們都可以顯示某種物理量（如密度）在空間中的分布。同時磁共振成像也有自身的特色，可以得到任何方向的斷層圖像、三維體圖像、甚至可以得到空間——波譜分布的四維圖像。

目前，醫(yī)學(xué)圖像三維重建方法主要有面繪制、體繪制以及由物體表面的二維灰度圖像重構(gòu)其三維幾何形狀法或稱明暗恢復(fù)形狀法等幾種。

2 Marching Cubes算法基本原理

移動立方體Marching Cubes[3]算法是Lorensen等人在1987年提出的等值面構(gòu)造方法，一直沿用至今，是體素單元內(nèi)等值面抽取技術(shù)的代表[4]。所謂等值面，是指在一個網(wǎng)格空間中由采樣值等于某一給定值的所有點組成的集合。該算法的本質(zhì)是將一系列兩維的切片數(shù)據(jù)看做是一個三維的數(shù)據(jù)場，從中將具

有某種域值的物質(zhì)抽取出來，以某種拓撲形式連接成三角面片。

等值面是空間中所有具有某個相同值的體素點的集合，體素點的值采用V0~V7八個點在體素區(qū)域內(nèi)三線性插值的結(jié)果?？梢员硎緸椋篶是常數(shù)。F(f)為體數(shù)據(jù)f中的等值面。計算公式可表達為：

⑴

其中α0,α1,……,α7是由V0~V7八個定點的值決定的常數(shù)。

在MC算法中，假定原始數(shù)據(jù)是離散的三維空間規(guī)則數(shù)據(jù)場如圖1所示。用于醫(yī)療診斷的斷層掃描(CT)及核磁共振成像(MRI) 等產(chǎn)生的圖像均屬于這一類型。

圖1三維空間規(guī)則數(shù)據(jù)場

MC算法的基本思想是逐個處理數(shù)據(jù)場中的體素，如圖2所示，分類出與等值面相交的體素，采用插值計算出等值面與體素棱邊的交點(V0~V7) 。根據(jù)體素中每一頂點與等值面的相對位置，將等值面與立方體邊的交點按一定方式連接生成等值面，作為等值面在該立方體內(nèi)的一個逼近表示。在計算出關(guān)于體數(shù)據(jù)場內(nèi)等值面的有關(guān)參數(shù)后，利用常用的圖形軟件包或硬件提供的面繪制功能繪制出等值面[5]。

圖2體元素圖

等值面的繪制一般采用二值化的方法，即通過與給定閥值的比較來確定該點的值(0或1)，頂點密度值＜域值為Outside的為1，頂點密度值≥域值Inside的為0。V0~V7每個頂點有Outside和Inside 2個狀態(tài)，因此8個頂點共有256種組合狀態(tài)，根據(jù)互補對稱性以及旋轉(zhuǎn)對稱性，共有15種三角構(gòu)型。在重建時根據(jù)索引進行查找時，每個索引分為索引，旋轉(zhuǎn)，三角模型三部分。Marching Cubes算法主要流程如下：

⑴將三維離散規(guī)則數(shù)據(jù)場分層讀入內(nèi)存。

⑵掃描兩層數(shù)據(jù)，逐個構(gòu)造體素，每個體素中的8個角點取自相鄰的兩層；8個定點可定義為(i，j，k)，(i+1，j，k)，(i+1，j+1，k)，(i+1，j，k+1)，(i+1，j+1，k+1)，(i，j+1，k+ 1)，(i，j+1，k)，(i，j，k+1)(如圖3所示)。

⑶將體素每個角點的函數(shù)值與給定的等值面值c比較，根據(jù)比較結(jié)果，構(gòu)造該體素的狀態(tài)表。

⑷根據(jù)狀態(tài)表，得出將與等值面有交點的邊界體素。

⑸通過線性插值方法計算出體素棱邊與等值面的交點。

⑹利用中心差分方法，求出體素各角點處的法向量，再通過線性插值方法，求出三角面片各頂點處的法向。

⑺根據(jù)各三角面片上各頂點的坐標及法向量繪制等值面圖像。

圖3體元素坐標點圖

3 空間等值點的判斷及等值面與體素邊界的交點計算

任取一離散網(wǎng)格棱邊，設(shè)棱邊上兩結(jié)點分別為：Mi(xi, yi, zi, qi)和Mj (xj, yj, zj, qj)；取量值的等值為C，當滿足(q-c)(q-c)≤0（等值點判定條件式）則Mi和Mj兩點間取等值點Mo。另設(shè)等值點Mo的坐標為(xo，yo，zo)，由Mi和Mj兩點根據(jù)線性插值可得公式⑵：

⑵

式中k=(qi-c)(qj-c)≤0。根據(jù)等值面判定條件式⑴，和等值點坐標公式⑵可以按結(jié)構(gòu)離散信息對網(wǎng)格棱邊進行搜索判斷，從而求出指定域中結(jié)構(gòu)體所有等值點。求出等值點以后，就可以將這些等值點連接成三角形或多邊形形成等值面的一部份。

4 等值面的法向量的計算

為了利用圖形硬件顯示等值面圖像，必須給出三角面片等值面的法向，選擇適當?shù)墓庹漳Ｐ瓦M行渲染，生成真實感圖形。對于等值面上的每一點，其沿面的切線方向的梯度分量應(yīng)該是零，因此沿該點的梯度矢量方向也就代表了等值面在該點的法向。等值面往往是具有不同密度物質(zhì)的分界面，因而其梯度矢量值不為零，即公式⑶：

⑶

直接計算三角面片的法向是費時的，為了消除各三角面片之間的明暗度的不連續(xù)變化，只要給出三角面片各頂點處的法向，并采用Gouraud模型繪制各三角面片。這里我們采用中心插分方法來計算各體素各角點的梯度。在三角形的情況下，計算出每一個三角形面片的法向量，然后用三角面的法向量求得每個頂點的法向量，最后用三角形三個頂點的三個法向量插值求出三角形面上某一點的法向量。對于等值面來說有簡單的方法計算頂點的法向量?？紤]到等高線的梯度方向與等高線的切線垂直，因此，可以用梯度矢量代替等高線的垂直線。在三維情況下，等值面的梯度方向就是等值面的法向方向。由此，可得到公式⑷：

⑷

5 Marching Cubes的優(yōu)化--網(wǎng)格模型簡化算法

網(wǎng)格模型簡化算法已經(jīng)取得了一系列的成果。目前的簡化算法大多考慮以邊折疊前后的模型幾何位置變化為折疊代價，從而減少多邊形的數(shù)量，以達到提高運算效率的目的。網(wǎng)格簡化算法的目的是在盡可能保證圖像精度的前提下提高效率。因此，選取坐標點的原則是盡可能接近原始網(wǎng)格，一般有子集選擇法和優(yōu)化選擇法[6]兩種子集選擇法即簡單地在邊的兩個端點中選擇代價較小的那一個，優(yōu)化選擇法則是選取二次誤差最小的點v作為折疊點，該點所對應(yīng)的二次誤差測度為，而點v的二次誤差是二次方程，求其最小值就是求方程對x，y，z偏導(dǎo)為零的點，解出的x，y，z即為新的頂點坐標。這一過程等價于公式⑸的矩陣方程求解。

⑸

折疊代價的度量

折疊代價的計算分為兩步。第一步：計算每個頂點的二次誤差側(cè)度時，以Garland的標準二次誤差測度為基礎(chǔ)，同時考慮周邊三角形面積的影響，計算每個頂點的二次誤差測度均值；第二步：計算邊折疊代價時，以邊的長度和邊折疊后所引起的三角形形態(tài)變化的程度作為加權(quán)因子。

具體計算方法為：在三維空間中，平面P可以表示為ax+by+cz+d=0，也可以表示為PTv=0.其中P=[a，b，c]T是平面P的單位法向量，且有，d為常量。模型空間中任一點v=[x，y，z，1]T到該平面的距離的平方為公式⑹：

⑹

網(wǎng)格模型中的任意點v=[x，y，z，1]T的二次誤差Δ(v)的定義為該頂點到與該定點相關(guān)的平面的平方和，可以表示為公式⑺：

⑺

其中，planes(v)表示所有包含定點v的三角平面構(gòu)成的一個集合，稱為頂點v的相關(guān)平面集。初始狀態(tài)下網(wǎng)格模型中每個點的二次誤差為0，上式變形后可以得到公式⑻。

⑻

其中kp為平面P的二次誤差測度。

⑼

而，

稱為v=[x，y，z，1]T的二次矩陣。

稱為點v的二次誤差。當進行邊折疊時，可使用一個附加規(guī)則(Garland et al. ， 1987)獲得點v處的二次誤差測度，該頂點的二次誤差值為，也就是該邊的折疊代價。

6 網(wǎng)格簡化算法在醫(yī)學(xué)三維重建上的應(yīng)用

網(wǎng)格算法一般應(yīng)用于加快三維重建的速度，但是單純的網(wǎng)格算法卻缺乏實用價值。相對于其高速的繪制，損失的精度是無法接受的。因此，對網(wǎng)格簡化算法又進行了進一步的優(yōu)化—基于體繪制的網(wǎng)格簡化算法。

體繪制是將切片中所有的物質(zhì)（皮膚、骨骼、肌肉等）集中在一幅圖中顯示。但在只需要觀察骨骼的情況下，很多的三角面繪制都是沒有意義的。忽略那些不必要的三角面可在保證精度的同時有效地提高重建速度。

7 結(jié)束語

MC算法通過對比閥值來確定體素的多邊形，在面對大容量數(shù)據(jù)時往往有著速度慢這一無法回避的缺點，但現(xiàn)在各種有針對性的改進使得它有了更大的發(fā)展?jié)摿Γ訫C算法不僅僅是個單純的算法，它更接近于“體素” 這個概念?，F(xiàn)在流行的很多三維重建算法都是基于MC進行改良的，目的是為了獲得所需要的特定的三維模型。象基于小波變換的醫(yī)學(xué)圖像融合算法，斷層醫(yī)學(xué)圖像插值算法等，則主要是為了使CT等數(shù)據(jù)容易受到MC算法中閥值的分割?，F(xiàn)在，OpenGL，VTK等圖像函數(shù)庫的使用已使得三維圖像建模變得簡單期望三維重建技術(shù)在醫(yī)學(xué)上的應(yīng)用會有更大的發(fā)展。

參考文獻：

[1] 蒲超,張育民.醫(yī)學(xué)圖象三維處理算法與應(yīng)用[J].兵工自動化,2004.6:210~212

[2] 羅述謙,周果宏,石教英.基于三角形移去準則的多面體簡化模型[J].計算機學(xué)報,2008.2:135~138

[3] Nielson GM.Dual Marching Cubes.IEEE Visualization 2004.

[4] 田捷,包尚聯(lián),周明全. 醫(yī)學(xué)圖像處理與分析[M].電子工業(yè)出版社2003.

[5] 金天弘,劉振宅. 醫(yī)學(xué)圖像三維重建的研究[J].醫(yī)療衛(wèi)生裝備,2008.2:34

[6] 楊加,吳祈耀,田捷.幾何圖像的分割法在CT圖像分割上的實現(xiàn)和比較[J].北京理工大學(xué)學(xué)報,20.6:720~724