基于改進(jìn)MC算法的醫(yī)學(xué)圖像三維重建研究

矯春海，張雅麗，張軍衛(wèi)

（燕山大學(xué)，河北 秦皇島 066004）

基于改進(jìn)MC算法的醫(yī)學(xué)圖像三維重建研究

矯春海，張雅麗，張軍衛(wèi)

（燕山大學(xué)，河北 秦皇島 066004）

MC算法是經(jīng)典的三維重建方法。但它重建時效率低，產(chǎn)生了大量的三角面片，增加了繪制的時間和空間。而且存在拓?fù)涠x性，會使重建后的圖像產(chǎn)生空洞的結(jié)構(gòu)，重建的效果也不是很理想。對此，提出相應(yīng)的改進(jìn)策略。介紹了如何提高計算效率、減少三角面片數(shù)量、消除二義性和平滑圖像等方面。通過實(shí)驗(yàn)證明了改進(jìn)算法的可行性。

MC算法；拓?fù)涠x性；頂點(diǎn)合并；三角面片平滑

醫(yī)學(xué)圖像指按某種物理學(xué)原理從人體器官采樣得到的單張或序列二維的斷層圖像，如CT、MRI等。醫(yī)學(xué)圖像的三維重建指將采樣得到的序列斷層圖像進(jìn)行計算機(jī)處理，以恢復(fù)器官的三維結(jié)構(gòu)信息。它為醫(yī)生提供具有真實(shí)感的三維模型，對于醫(yī)生的輔助診斷和手術(shù)導(dǎo)航具有重要意義。

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

1 傳統(tǒng)MC算法

1.1 算法簡介

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

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

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

1.1.1 等值面剖分方式的確定

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

1.1.2 等值面與棱邊的交點(diǎn)的確定

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

（1）當(dāng)棱邊與X軸平行時，設(shè)棱邊的兩個角點(diǎn)為v1（i，j，k），v2（i+1，j，k），則交點(diǎn)為 v（x，j，k）：

（2）當(dāng)棱邊與Y軸平行時，設(shè)棱邊的兩個角點(diǎn)為v1（i，j，k），v2（i，j+1，k），則交點(diǎn)為 v（i，y，k）：

（3）當(dāng)棱邊與Z軸平行時，設(shè)棱邊的兩個角點(diǎn)為v1（i，j，k），v2（i，j，k+1），則交點(diǎn)為 v（i，j，z）：

1.1.3 等值面法向量的確定

為了利用圖形硬件顯示等值面圖像，必須給出等值面的法向量，選擇適當(dāng)?shù)墓庹漳Ｐ陀嬎?，生成較真實(shí)的重建圖像。直接計算三角面片的法向量是費(fèi)時的，實(shí)際中采用中心差分法計算各角點(diǎn)的梯度，然后通過線性插值計算交點(diǎn)的梯度，即三角面片的頂點(diǎn)的法向量。角點(diǎn)的中心差分公式如下：

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

1.2 傳統(tǒng)MC算法存在的問題

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

（2）在等值面剖分方式的確定時，存在拓?fù)涠x性。

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

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

2 改進(jìn)MC算法

針對傳統(tǒng)MC算法存在的問題，主要從四個方面進(jìn)行改進(jìn)。

2.1 提高計算效率

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

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

傳統(tǒng)MC算法每次線性插值要進(jìn)行4次代數(shù)計算，3個頂點(diǎn)就需要12次計算。而使用中點(diǎn)法3個頂點(diǎn)只需要3次計算，大大減少了每次插值的計算量。

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

2.2 提高等值面的拓?fù)湔_程度

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

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

2.3 減少三角面片數(shù)量

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

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

2.3.1 合并頂點(diǎn)的約束條件

一般認(rèn)為，短小的邊、平坦的區(qū)域應(yīng)該優(yōu)先合并。所以采用距離和法向兩個約束條件。

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

2.3.2 合并頂點(diǎn)的位置確定

2.4 平滑三角面片

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

由圖可知，改進(jìn)的算法和傳統(tǒng)的算法相比，繪制時間明顯減少，但繪制效果并沒有因?yàn)槿敲嫫臏p少而而使圖像質(zhì)量降低。

本文介紹了傳統(tǒng)的MC算法三維重建原理，指出了該算法存在的問題，并給出了改進(jìn)算法。在重建的各個環(huán)節(jié)分別采取相應(yīng)的策略：在提高計算效率方面，采用了中點(diǎn)法和相關(guān)性處理；在保證拓?fù)湫问秸_的前提下采用頂點(diǎn)合并法，減少了三角面片數(shù)量；采用平滑策略，使重建后的圖像得到較好的視覺效果。實(shí)驗(yàn)表明，改進(jìn)的算法在保證圖像質(zhì)量的前提下，大幅提高了重建的速度。

[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]徐效文，王永華.基于等值面優(yōu)化重建醫(yī)學(xué)圖像的改進(jìn)算法[J].微計算機(jī)信息（管控一體化），2009，25（91）.

[3]徐曉玲，李現(xiàn)民.體素重建中的快速移動立方體方法[J].系統(tǒng)仿真學(xué)報，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].微計算機(jī)信息（管控一體化），2009，25（83）.

[7]秦緒佳，歐宗瑛.醫(yī)學(xué)圖像三維重建系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)表達(dá)及表面模型的構(gòu)建[J].生物醫(yī)學(xué)工程學(xué)雜志，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]蔣遂平，周明天，戴穎.基于法向的網(wǎng)格簡化[J].計算機(jī)學(xué)報，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年生，在讀研究生，主要研究方向：數(shù)字圖像處理，識別和圖像理解。