Mar ching Cubes算法研究

熱孜萬古麗·夏米西丁

(新疆師范大學計算機科學與技術學院 新疆 烏魯木齊 830054)

0 引論

三維重建方法主要分為面繪制和體繪制兩類.其中面繪制的主要思想是首先提取感興趣物體的表面信息,把體數據轉換為一系列三角形面片擬合的等值面,然后再根據光照 、明暗模型進行消隱和渲染得到三維的顯示圖像.與體繪制比較,面繪制原理簡單、易于實現,有較高的效率,并由于目前的顯卡都可以對三角面片進行硬件加速的繪制,使它成為至今為止最具影響力的一種等值面構造方法,一直到現在為止在可視化領域的著名雜志和會議上還經常有針對MC方法的改進算法[1]。使用面繪制可以輕易地完成對立方體素的三角面片構型確定,三角面片頂點坐標的計算,三角面片頂點法向量的計算,并最終完成對三維圖像的高精度完全重建.Marching Cubes算法的不斷完善和發展,使得提供直觀、逼真而且能夠包含原始信息中隱含的豐富內容的三維信息成為可能.通過圖形圖像技術,可以對影像進行任意放大、縮小、旋轉、對比調整、三維重建等處理,得到便于研究者從多角度、多層次進行觀察的三維模型.這對分析結果的準確性有深遠的意義.

1 MC算法

1.1 工作原理及步驟

醫學圖像的三維重建的主要思想就是根據輸人的大量的醫學斷層圖像.經分割和提取處理之后,重建出可視的三維圖像.這些三維圖像在大多數時候是計算出來的大量的三角面片逼近表示.所以如何計算出這些三角面片信息是三維重建的關鍵.Marching Cubes算法是基于體素的三維物體表面重構方法.其基本原理是首先找出經過該等值面的體元,求出該體元內的等值面并計算出相關參數,通過這些參數在物體表面通過的每一個體素內構造三角面片.

整個重建物體由這些三角面片連接組成.并且 在Open GL中提供了相應的處理三角面片信息的接口函數,可以進一步提高成像速度.Marching Cubes算法不必考慮分叉問題,并且全局的拓撲結構已經由局部拓撲處理所確定,適用于密集體數據的重建[2].Marching Cubes算法的過程可以描述如下[3].

（1）每次讀取兩張切片,形成一層 (Laver).

（2）每個laver中上下兩切片對應的相鄰四個像素構成一個立方體(Cube);

（3）按從左至右,從上到下的順序提取cube,并對 cube根據所給閾值進行計算處理,然后再按從下到上順序處理到最后一層.每個cube需要按照所給閩值進行處理,如果一個頂的灰度值在所給閡值之間,則將它標記為1,而小于閩值的記為0,這樣就可以根據所有點標記情況判斷出等值面與cube的相交情況,進而得到相應三角面片表示形式.所有的三角面片表示情況共有 256種,去掉對稱情況,再經過相應旋轉可最終確定十五種情況,如圖1所示.

（4）將計算出來的全部三角面片信息使用Open GL提供的三角面片繪制函數進行繪制,便可得到最終的三維成像結果.

圖1 Marching Cubes十五種情況

在不降低成像結果質量的同時盡可能的減少三角面片的數量[4].

1.2 MC算法存在的問題

Durst通過分析基本體元狀態模型,提出在立方體的一個面上,如果位于等值面內和在等值面外的頂點分別分布在對角線的兩端,就會有2種連接方式;當相鄰的2個立方體在公共面上采取的連接不同時,就會 導致孔洞的生成.如何從2種以上的連接模式中選擇正確的模式是解決二義性的關鍵.解決這種面上二義性的算法主要有2類:四面體剖分算法和雙曲線漸近線算法.

1.2.1 四面體剖分消除二義性

使用四面體剖分算法解決二義性時,假設在四面體 的邊上數據場呈線性變化,由于四面體的每個面是三角形,因此生成的等值面片的連接方式是唯一的.四面體剖分算法能夠解決拓撲二義性,有比較高的逼近精度,但生成三角片的數量明顯增多.大量的三角片導致計算量增加,并且在立方體內的等值面沒有二義性時,立方體也會被剖分處理,大大增加了算法的時間耗費.此外,Cignoni[5]等提出,四面體剖分算法中等值面的構造與剖分方式有關,相鄰立方體單元剖分不一致會導致裂縫的產生,導致形成的逼近等值面可能和真實等值面有不同的拓撲結構,因此它未得到廣泛的應用.

1.2.2 雙曲線漸近線算法消除二義性

Nielson[6]提出使用雙曲線漸近線算法來解決面上的二義性.等值面與立方體某一面的交線是一組雙曲線或者其中的一支.當2支雙曲線都與立方體表面相交時,就會產生二義性.在出現二義性的情況中,2支雙曲線將立方體表面分成 3個區域,可以證明,雙曲線漸近線的交點總是和其中一對交點落在同一個區域.比較漸近線交點和等值 面的標量值,如果漸近線交點的標量值大于等值面的標量值,則標量值大于等值面標量值的一對頂點與該交點落在同一個區域;反之,另一對頂點與漸近線交點落在同一區域.

2 結論

MC算法抽取的等值面的拓撲結構 、表示精度 、算法的時間和空間效率等在實際使用中都具有非常重要的意義.本文闡述了算法在這些方面存在的不足,對現有的改進算法進行綜述,改進后的算法較之原始MC算法顯示效果已經有了較大的改進,但在應用到醫學可視化等具體領域時,還存在許多問題,有必要進行更深人的研究因此,研究在并行和分布式情況下應用MC算法,也是改進算法的一個重要方向.

［1］祁俐娜，羅述謙.基于 VTK的醫學圖像三維重建[J].北京:北京生物醫學工程，2006，25(1)：1-5.

［2］羅述謙，周果宏.醫學圖像處理與分析[M].北京：科學出版社，2003.

［3］Arie E.Kaufman.Accelerated Volume Graphics[J].Geometric Modeling and Processing，2002，3(7)：3-7.

［4］張尤賽，陳福民.三維醫學圖像的體繪制技術綜述[J].北京：計算機工程與應用，2002(8):18-19，122.

［5］Cignoni P，Ganovelli F.Montani.etal.Reconstruction of topologically correct and adaptive trilinear surfaces[J].Computers and Graphics，2000，24(3)：399-418.

［6］Nielson G，Hamann B.The asymptotic decider：resolving the ambiguity in marching cubes[C].Proceedings of Visualization’91，Los Alamitos CA，1991：83-91