葉含笑 高智峰 江依法

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

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

中圖分類號(hào)：TP文獻(xiàn)標(biāo)志碼：A文章編號(hào)：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 世紀(jì)70 年代初。由于集成三維重建平臺(tái)的醫(yī)學(xué)影像設(shè)備價(jià)格昂貴等客觀原因，國(guó)內(nèi)醫(yī)學(xué)圖像三維可視化診斷起步較晚，到90年代某些高校才開始進(jìn)行各層面上的研究[1]。隨著計(jì)算機(jī)技術(shù)的發(fā)展，短短幾年，三維重建技術(shù)已成為人們探索生命奧秘，以及疾病診斷、手術(shù)規(guī)劃的重要手段。

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

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

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

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

2 Marching Cubes算法基本原理

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

有某種域值的物質(zhì)抽取出來，以某種拓?fù)湫问竭B接成三角面片。

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

⑴

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

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

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

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

圖2體元素圖

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

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

⑵掃描兩層數(shù)據(jù)，逐個(gè)構(gòu)造體素，每個(gè)體素中的8個(gè)角點(diǎn)取自相鄰的兩層；8個(gè)定點(diǎn)可定義為(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所示)。

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

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

⑸通過線性插值方法計(jì)算出體素棱邊與等值面的交點(diǎn)。

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

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

圖3體元素坐標(biāo)點(diǎn)圖

3 空間等值點(diǎn)的判斷及等值面與體素邊界的交點(diǎn)計(jì)算

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

⑵

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

4 等值面的法向量的計(jì)算

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

⑶

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

⑷

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

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

⑸

折疊代價(jià)的度量

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

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

⑹

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

⑺

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

⑻

其中kp為平面P的二次誤差測(cè)度。

⑼

而，

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

稱為點(diǎn)v的二次誤差。當(dāng)進(jìn)行邊折疊時(shí)，可使用一個(gè)附加規(guī)則(Garland et al. ， 1987)獲得點(diǎn)v處的二次誤差測(cè)度，該頂點(diǎn)的二次誤差值為，也就是該邊的折疊代價(jià)。

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

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

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

7 結(jié)束語

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

參考文獻(xiàn)：

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

[2] 羅述謙,周果宏,石教英.基于三角形移去準(zhǔn)則的多面體簡(jiǎn)化模型[J].計(jì)算機(jī)學(xué)報(bào),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圖像分割上的實(shí)現(xiàn)和比較[J].北京理工大學(xué)學(xué)報(bào),20.6:720~724