MC算法在醫學圖像三維重建中的應用

葉含笑 高智峰 江依法

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

關鍵詞： 三維重建； 移動立方體算法； 面繪制

中圖分類號：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 引言

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

1 常見的醫學三維重建素材

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

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

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

2 Marching Cubes算法基本原理

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

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

等值面是空間中所有具有某個相同值的體素點的集合，體素點的值采用V0~V7八個點在體素區域內三線性插值的結果。可以表示為：c是常數。F(f)為體數據f中的等值面。計算公式可表達為：

⑴

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

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

圖1三維空間規則數據場

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

圖2體元素圖

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

⑴將三維離散規則數據場分層讀入內存。

⑵掃描兩層數據，逐個構造體素，每個體素中的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所示)。

⑶將體素每個角點的函數值與給定的等值面值c比較，根據比較結果，構造該體素的狀態表。

⑷根據狀態表，得出將與等值面有交點的邊界體素。

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

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

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

圖3體元素坐標點圖

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

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

⑵

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

4 等值面的法向量的計算

為了利用圖形硬件顯示等值面圖像，必須給出三角面片等值面的法向，選擇適當的光照模型進行渲染，生成真實感圖形。對于等值面上的每一點，其沿面的切線方向的梯度分量應該是零，因此沿該點的梯度矢量方向也就代表了等值面在該點的法向。等值面往往是具有不同密度物質的分界面，因而其梯度矢量值不為零，即公式⑶：

⑶

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

⑷

5 Marching Cubes的優化--網格模型簡化算法

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

⑸

折疊代價的度量

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

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

⑹

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

⑺

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

⑻

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

⑼

而，

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

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

6 網格簡化算法在醫學三維重建上的應用

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

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

7 結束語

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

參考文獻：

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

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

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

[4] 田捷,包尚聯,周明全. 醫學圖像處理與分析[M].電子工業出版社2003.

[5] 金天弘,劉振宅. 醫學圖像三維重建的研究[J].醫療衛生裝備,2008.2:34

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