基于改進MC算法的醫學圖像三維重建研究

矯春海，張雅麗，張軍衛

（燕山大學，河北 秦皇島 066004）

基于改進MC算法的醫學圖像三維重建研究

矯春海，張雅麗，張軍衛

（燕山大學，河北 秦皇島 066004）

MC算法是經典的三維重建方法。但它重建時效率低，產生了大量的三角面片，增加了繪制的時間和空間。而且存在拓撲二義性，會使重建后的圖像產生空洞的結構，重建的效果也不是很理想。對此，提出相應的改進策略。介紹了如何提高計算效率、減少三角面片數量、消除二義性和平滑圖像等方面。通過實驗證明了改進算法的可行性。

MC算法；拓撲二義性；頂點合并；三角面片平滑

醫學圖像指按某種物理學原理從人體器官采樣得到的單張或序列二維的斷層圖像，如CT、MRI等。醫學圖像的三維重建指將采樣得到的序列斷層圖像進行計算機處理，以恢復器官的三維結構信息。它為醫生提供具有真實感的三維模型，對于醫生的輔助診斷和手術導航具有重要意義。

三維重建技術分為面繪制和體繪制兩大類。面繪制技術由三維空間數據場構造中間幾何圖元 （如曲線、曲面等），然后由計算機圖形學技術實現畫面繪制；體繪制技術由三維數據場直接產生屏幕上的二維圖像。由于體繪制技術運算量大，難以實時處理，而面繪制比體繪制速度快，更適合實時性的要求，所以實際應用中，面繪制仍是主流。面繪制中最經典的是MC（Marching Cubes）算法，該算法由Lorensen等人于1987年提出，因其原理簡單、容易實現，得到了廣泛應用[1]。

1 傳統MC算法

1.1 算法簡介

等值面是空間中具有某個相同值的點的集合，在三維數據場中是一個三次曲面。它的數學表示如下：{（x，y，z）|f（x，y，z）=c}，c 為常數。

傳統MC算法的基本思想是：分層讀入斷層圖像。取相鄰兩層的4個像素點組成一個立方體（體元），體元的8個角點值由輸入數據取得。按照從左到右，從前到后，從下到上的順序逐個處理數據場中的體元，分類出與等值面相交的體元。采用插值法計算等值面與體元邊的交點。根據角點值與等值面的相對位置，將交點按一定方式連接成三角面片，作為等值面在體元內的逼近表示。體元示意圖如圖1所示。

傳統MC算法涉及等值面的剖分方式的確定、等值面與棱邊交點的計算和等值面法向量計算三個主要問題。

1.1.1 等值面剖分方式的確定

MC算法的基本假設是沿著體元的邊數據場呈連續線性變化。一條邊的兩個角點值分別大于、小于等值面的值時，該邊有且僅有一個與等值面的交點。8個角點大于、等于等值面的值時，標記為 0；小于等值面的值時，標記為1。則每個角點有兩種狀態，總共有256種狀態。根據旋轉對稱性，可以簡化為15種。首先建立具有256個索引項的查找表，每個索引項由索引、旋轉和剖分方式組成。8個角點值組成01串，形成一個索引項，用索引項在查找表里查找，確定15種剖分方式的一種。15種部分形式如圖2示。

1.1.2 等值面與棱邊的交點的確定

棱邊的2個角點為0和1時，等值面一定與棱邊相交，有：

（1）當棱邊與X軸平行時，設棱邊的兩個角點為v1（i，j，k），v2（i+1，j，k），則交點為 v（x，j，k）：

（2）當棱邊與Y軸平行時，設棱邊的兩個角點為v1（i，j，k），v2（i，j+1，k），則交點為 v（i，y，k）：

（3）當棱邊與Z軸平行時，設棱邊的兩個角點為v1（i，j，k），v2（i，j，k+1），則交點為 v（i，j，z）：

1.1.3 等值面法向量的確定

為了利用圖形硬件顯示等值面圖像，必須給出等值面的法向量，選擇適當的光照模型計算，生成較真實的重建圖像。直接計算三角面片的法向量是費時的，實際中采用中心差分法計算各角點的梯度，然后通過線性插值計算交點的梯度，即三角面片的頂點的法向量。角點的中心差分公式如下：

式中，Δx、Δy、Δz為立方體的邊長。

1.2 傳統MC算法存在的問題

（1）計算效率低。在計算等值面與棱邊的交點時，線性插值法不夠簡化，而且相鄰立方體每次要對共有棱邊進行插值，一條棱邊需要重復計算4次。

（2）在等值面剖分方式的確定時，存在拓撲二義性。

（3）輸出的三角面片數量巨大，難以實時顯示。

（4）三角面片不夠光滑，有魚鱗現象。因三角面片法向不連續，使其明亮也不連續。為了得到較好的視覺效果，需要進行平滑處理。

2 改進MC算法

針對傳統MC算法存在的問題，主要從四個方面進行改進。

2.1 提高計算效率

為了簡化線性插值法，參考文獻[2]提出三點線性插值法，在立方體棱邊取3個等分點，根據等值點的值，選取一點用來代替線性插值點。本文采用中點法[3]，即用棱邊的中點代替線性插值點。由于醫學圖像的分辨率越來越高，有的螺旋 CT機已經達到 1 024×1 024，而中點法引起的誤差投影到最終成像，在視覺上幾乎沒有影響。中點法的核心公式：

式中，P為等值面與棱邊的交點即三角面片頂點的坐標；P1、P2為棱邊的 2個角點坐標；N為三角面片頂點的法向量；N1、N2為棱邊的2個角點的法向量。

傳統MC算法每次線性插值要進行4次代數計算，3個頂點就需要12次計算。而使用中點法3個頂點只需要3次計算，大大減少了每次插值的計算量。

為了避免重復計算，本文提出相關性處理方法。由于一個立方體對一條棱邊的占有率為1/4，一個立方體有 12條棱邊，則 12×1/4=3，一個立方體只占有 3條棱邊，只要計算其中的3條棱邊就可避免重復插值。具體做法：可以對立方體的12條邊編號，每次只對其中固定的3條邊插值，如對0、3、8邊插值，則所有的邊界立方體存在等值點的邊都可以得到插值，而且不會重復計算。編號的體元如圖3所示。

2.2 提高等值面的拓撲正確程度

MC算法存在連接方式上的二義性，即當立方體面對角線上的一對角點為0、另一對角點為1時，該面上的交點連接就出現二義性[4]，如圖4所示。

任選一種方式可能導致錯誤的拓撲形式，使構造的等值面出現空隙。為了消除單元面上二義性，參考文獻[5]提出的漸近線判別法，利用面上的雙線性插值解決單元面上的二義性；參考文獻[6]采用剖分法，剖分二義性面為4個小正方形，直到每個小正方形不再具有二義性；參考文獻[7]采用MC算法的變形MT算法解決拓撲二義性。本文則采用漸近線判別法消除二義性。一般情況下，等值面與邊界面的交線是雙曲線，該雙曲線的兩條漸近線的交點必然與邊界面對角線的交點落在同一個區域內。當出現二義性時，計算漸近線交點處的插值，如果插值大于等值面的值，稱之為正值二義面，漸近線的交點與函數值大于閾值的一對角點落在同一區域；如果漸近線交點處的插值小于等值面的閾值，稱之為負值二義面，漸近線的交點與函數值小于閾值的一對角點落在同一區域。如圖5所示。

2.3 減少三角面片數量

由于先進的醫學設備得到的斷層圖像數據十分密集，建立的三維網格模型通常由幾十萬、幾百萬，甚至上億個三角面片組成。雖然這樣可以更加精確地表達實體，但是存儲占用空間太大，繪制耗費時間太長，很不實用。如何在保持模型精度的同時合理簡化模型成為一個重要課題。

三角面片簡化主流是頂點合并法[8-9]，該法基本思想是投影到圖像空間中足夠小的區域內的一組頂點可用一個代表性頂點代替，形成的新頂點又可以參與下一輪的合并。每次合并一條邊的兩個頂點（稱邊收縮）；每次合并一個三角形的3個頂點，（稱三角形收縮）。本文采用基于邊收縮的頂點合并法，一條邊的兩個頂點滿足約束條件時，將此邊收縮到一個點上，同時刪除共享該邊的三角形。合并示意圖如圖6示。

2.3.1 合并頂點的約束條件

一般認為，短小的邊、平坦的區域應該優先合并。所以采用距離和法向兩個約束條件。

（1）距離約束：將三角形頂點 Vi、Vj的幾何距離記為d（Vi，Vj），設定一個最大距離約束 MDC，則距離約束為d（Vi，Vj）≤MDC。

2.3.2 合并頂點的位置確定

2.4 平滑三角面片

傳統的MC算法重建的三維圖像清晰度往往不夠理想，三角面片的位置和方向很容易受到數據場中噪聲的干擾，從而導致魚鱗效應。為了達到理想的等值面平滑效果，應將等值面分解為一個坐標場和一個法向量場，通過對法向量場進行平滑，得到較好的視覺效果。

將各頂點的法向量設為 gx=a、gy=b、gz=c，對其法向量場做平滑處理。設頂點t相鄰的頂點（即包含t頂點不同三角面片的所有頂點）為{ti|i=0，1，2，…，K}，其對應的各方向的法向量分別為：

等值面的方向平滑方法并不改變原等值面上三角面片的坐標位置，根據光照模型的濃淡繪制原理，通過提高等值面上三角面片法向量之間的連續相關性來取得三維繪制的平滑效果。

3 實驗結果及分析

實驗在AMD 1.6 G電腦上，以Visual C++語言和OpenGL圖形庫執行算法。實驗對象來自一組CT圖片，數據大小為512×512×80，層距為 3 mm。由實驗得到傳統算法三角面片數為405 472，繪制時間為5.7 s。改進算法三角面片為223 790，繪制時間為2.5 s。改進的算法三角面片數減少了44.8%，繪制時間減少了56.1%。傳統和改進算法重建的圖像如圖7所示。

由圖可知，改進的算法和傳統的算法相比，繪制時間明顯減少，但繪制效果并沒有因為三角面片的減少而而使圖像質量降低。

本文介紹了傳統的MC算法三維重建原理，指出了該算法存在的問題，并給出了改進算法。在重建的各個環節分別采取相應的策略：在提高計算效率方面，采用了中點法和相關性處理；在保證拓撲形式正確的前提下采用頂點合并法，減少了三角面片數量；采用平滑策略，使重建后的圖像得到較好的視覺效果。實驗表明，改進的算法在保證圖像質量的前提下，大幅提高了重建的速度。

[1]LORENSEN W E，CLINE H E.Marching cubes：a high resolution 3D surface construction algorithms[J].Computer Graphics，1987，21（4）：163-169.

[2]徐效文，王永華.基于等值面優化重建醫學圖像的改進算法[J].微計算機信息（管控一體化），2009，25（91）.

[3]徐曉玲，李現民.體素重建中的快速移動立方體方法[J].系統仿真學報，2002，14（4）：509-513.

[4]DURST M J.Additional reference to marching cubes[J].Computer Graphics，1998，22（2）：72-73.

[5] NIELSON G， HAMANN B.The asymptotic decider resolving the ambiguity in Marching Cubes[C].Proceedings of Visualization′91，1991：83-91.

[6]於時才，唐占紅.MC三維重建算法的二義性消除研究[J].微計算機信息（管控一體化），2009，25（83）.

[7]秦緒佳，歐宗瑛.醫學圖像三維重建系統的數據結構表達及表面模型的構建[J].生物醫學工程學雜志，2002，19（2）：239-243.

[8]OH K M，PARK K H.A vertex merging algorithm for extraction a variable-resolution sosurface from volume data[C].IEEE International Conference on System，Man and Cybernetics，1995：3543-3548.

[9]蔣遂平，周明天，戴穎.基于法向的網格簡化[J].計算機學報，1999，22（10）：1074-1079.

3D reconstruction research of medical image based on improved MC algorithm

Jiao Chunhai，Zhang Yali，Zhang Junwei

（Yanshan University，Qinhuangdao 066004，China）

Marching cubes algorithm is a classical reconstruction method.But it has low efficiency and produces a lot of triangles so that it takes a lot of time and space.What’s more，it has topology ambiguity to make reconstructed image hollow.And its effect also is not ideal.The paper puts forward corresponding improvement strategies，mainly about how to increase calculation efficiency，reduce the number of triangles，eliminate topology ambiguity and smooth image，and so on.Finally，the experiments prove the feasibility of the improved algorithm.

MC algorithm；topology ambiguity；vertexes merging；smooth triangles

TP391

A

1674-7720（2011）03-0039-03

2010-08-04）

矯春海，男，1984年生，在讀研究生，主要研究方向：數字圖像處理，識別和圖像理解。