Mar ching Cubes算法研究

熱孜萬古麗·夏米西丁

(新疆師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 新疆 烏魯木齊 830054)

0 引論

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

1 MC算法

1.1 工作原理及步驟

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

整個(gè)重建物體由這些三角面片連接組成.并且 在Open GL中提供了相應(yīng)的處理三角面片信息的接口函數(shù),可以進(jìn)一步提高成像速度.Marching Cubes算法不必考慮分叉問題,并且全局的拓?fù)浣Y(jié)構(gòu)已經(jīng)由局部拓?fù)涮幚硭_定,適用于密集體數(shù)據(jù)的重建[2].Marching Cubes算法的過程可以描述如下[3].

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

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

（3）按從左至右,從上到下的順序提取cube,并對 cube根據(jù)所給閾值進(jìn)行計(jì)算處理,然后再按從下到上順序處理到最后一層.每個(gè)cube需要按照所給閩值進(jìn)行處理,如果一個(gè)頂?shù)幕叶戎翟谒o閡值之間,則將它標(biāo)記為1,而小于閩值的記為0,這樣就可以根據(jù)所有點(diǎn)標(biāo)記情況判斷出等值面與cube的相交情況,進(jìn)而得到相應(yīng)三角面片表示形式.所有的三角面片表示情況共有 256種,去掉對稱情況,再經(jīng)過相應(yīng)旋轉(zhuǎn)可最終確定十五種情況,如圖1所示.

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

圖1 Marching Cubes十五種情況

在不降低成像結(jié)果質(zhì)量的同時(shí)盡可能的減少三角面片的數(shù)量[4].

1.2 MC算法存在的問題

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

1.2.1 四面體剖分消除二義性

使用四面體剖分算法解決二義性時(shí),假設(shè)在四面體 的邊上數(shù)據(jù)場呈線性變化,由于四面體的每個(gè)面是三角形,因此生成的等值面片的連接方式是唯一的.四面體剖分算法能夠解決拓?fù)涠x性,有比較高的逼近精度,但生成三角片的數(shù)量明顯增多.大量的三角片導(dǎo)致計(jì)算量增加,并且在立方體內(nèi)的等值面沒有二義性時(shí),立方體也會(huì)被剖分處理,大大增加了算法的時(shí)間耗費(fèi).此外,Cignoni[5]等提出,四面體剖分算法中等值面的構(gòu)造與剖分方式有關(guān),相鄰立方體單元剖分不一致會(huì)導(dǎo)致裂縫的產(chǎn)生,導(dǎo)致形成的逼近等值面可能和真實(shí)等值面有不同的拓?fù)浣Y(jié)構(gòu),因此它未得到廣泛的應(yīng)用.

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

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

2 結(jié)論

MC算法抽取的等值面的拓?fù)浣Y(jié)構(gòu) 、表示精度 、算法的時(shí)間和空間效率等在實(shí)際使用中都具有非常重要的意義.本文闡述了算法在這些方面存在的不足,對現(xiàn)有的改進(jìn)算法進(jìn)行綜述,改進(jìn)后的算法較之原始MC算法顯示效果已經(jīng)有了較大的改進(jìn),但在應(yīng)用到醫(yī)學(xué)可視化等具體領(lǐng)域時(shí),還存在許多問題,有必要進(jìn)行更深人的研究因此,研究在并行和分布式情況下應(yīng)用MC算法,也是改進(jìn)算法的一個(gè)重要方向.

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

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

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

［4］張尤賽，陳福民.三維醫(yī)學(xué)圖像的體繪制技術(shù)綜述[J].北京：計(jì)算機(jī)工程與應(yīng)用，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