序列圖像三維重建中的關(guān)鍵算法

方 欣, 郭觀七, 沈中陽

(1. 湖南理工學(xué)院 信息與通訊工程學(xué)院, 湖南 岳陽 414000; 2. 資興市青少年活動中心, 湖南 郴州 423400)

序列圖像三維重建中的關(guān)鍵算法

方 欣1, 郭觀七1, 沈中陽2

(1. 湖南理工學(xué)院 信息與通訊工程學(xué)院, 湖南 岳陽 414000; 2. 資興市青少年活動中心, 湖南 郴州 423400)

主要討論了基于序列圖像的三維重建中的兩個關(guān)鍵算法: 特征數(shù)據(jù)點(diǎn)列的重采樣算法與三角化算法. 本文改進(jìn)了Chetverikov等提出的輪廓曲線中高曲率點(diǎn)的檢測算法, 使在重采樣時, 數(shù)據(jù)的壓縮比得到了明顯的改善, 也顯著地提高了可視化速度. 并使用一種簡單的三角化算法, 對重采樣后的數(shù)據(jù)點(diǎn)列進(jìn)行三角化, 實(shí)現(xiàn)目標(biāo)的三維重建.

圖像序列; 三維重建; 高曲率; 重采樣; 三角化

Abstract:Two important algorithm in 3D reconstruction of image sequences are studied, i.e. re-sampling algorithm and triangulation algorithm. An improved algorithm for detection of high curvature points in planar curves is presented. This algorithm can improve the performance of re-sampling and 3D data field visualization. Triangulation is implemented by using a simple triangulation algorithm. Sequentially, 3D object reconstruction was achieved.

Key words:image sequence; 3D reconstruction; High Curvature; re-sampling; triangulation

引言

隨著計(jì)算機(jī)軟硬件技術(shù)和醫(yī)學(xué)成像技術(shù)的日益發(fā)展, 基于數(shù)字圖像技術(shù)的醫(yī)學(xué)應(yīng)用系統(tǒng)也得到了長足的發(fā)展. 在這些醫(yī)學(xué)應(yīng)用系統(tǒng)中, 在有效精確地提取出醫(yī)學(xué)圖像中相應(yīng)目標(biāo)特征量的基礎(chǔ)上, 進(jìn)行人體組織或器官的三維重建[1], 是很多實(shí)用系統(tǒng)的基礎(chǔ), 如基于圖像的病理分析[2]、基于圖像的手術(shù)導(dǎo)引與增強(qiáng)[3]、虛擬手術(shù)平臺[4]等應(yīng)用系統(tǒng), 因此醫(yī)學(xué)圖像的三維重建一直是國內(nèi)外醫(yī)學(xué)界及圖像處理領(lǐng)域的研究與應(yīng)用熱點(diǎn)之一.

三維重建的目的是從一系列二維切片數(shù)據(jù)(圖像)中得到物體的三維表示, 一般使用網(wǎng)格的形式來表示. 目前, 三維重建過程中經(jīng)常沿用的一種經(jīng)典算法是Lorensen等人于1987年提出的Marching Cubes方法[6], 其原理簡單, 易于實(shí)現(xiàn). 但這種方法計(jì)算效率低, 輸出的三角網(wǎng)格數(shù)量巨大. 因此近些年來, 研究者們從不同角度對該算法進(jìn)行改進(jìn)[5,7,8]. 本文在文獻(xiàn)[5]的基礎(chǔ)上提出了一種基于輪廓的三維重建方法, 運(yùn)用并改進(jìn)了相關(guān)算法, 與直接運(yùn)用文獻(xiàn)[5]所提出的算法相比較, 本文所提出并改進(jìn)的方法處理速度更快,輸出的三角網(wǎng)格數(shù)量也較少, 而且三角網(wǎng)格的形態(tài)也比較理想.

1 算法描述

作者實(shí)現(xiàn)基于序列圖像三維重建的主要思路如下:

(1) 特征提取: 在序列圖像中提取出需要重建目標(biāo)的輪廓;

(2) 特征點(diǎn)列重采樣: 將(1)中檢測出的邊緣按創(chuàng)建Chain-code的方法, 形成點(diǎn)列, 并對此點(diǎn)列進(jìn)行重采樣, 以減少后續(xù)階段中處理的數(shù)據(jù)量;

(3) 基于輪廓的空間點(diǎn)三角化: 采用一種簡單有效的三角化算法, 對(2)中重采樣后的點(diǎn)列進(jìn)行三角化, 形成三角面片;

(4) 三角面片的可視化: 使用OpenGL技術(shù), 實(shí)現(xiàn)重建目標(biāo)的三維顯示.

本文主要討論了第(2)與第(3)過程中所采用及改進(jìn)的算法. 特征點(diǎn)列重采樣采用文獻(xiàn)[5]所描述的算法,但該算法主要應(yīng)用于輪廓曲線上高曲率點(diǎn)的檢測, 而應(yīng)用于重采樣時, 數(shù)據(jù)的壓縮比并不理想, 本文提出了對該算法的改進(jìn)方法, 使得重采樣數(shù)據(jù)的壓縮比得到了明顯改善.

經(jīng)過實(shí)驗(yàn)測試比較, 在提取序列圖像中目標(biāo)的邊緣輪廓過程中, 使用傳統(tǒng)的Robert算子或Canny算子,能較好地保證分割出來的邊緣是單像素點(diǎn). 否則的話, 則可使用細(xì)化(Thinning)算法作進(jìn)一步處理. 當(dāng)?shù)玫絾蜗袼攸c(diǎn)的邊緣后, 按照創(chuàng)建Chain-code的方法, 掃描檢測出的邊緣點(diǎn), 由此而形成點(diǎn)序列, 便于重采樣算法的操作.

1.1 特征點(diǎn)列重采樣

文獻(xiàn)[5]提出了一種兩次掃描算法: 對獲得的特征點(diǎn)列進(jìn)行兩次掃描. 第一次掃描, 選擇出可能的高曲率點(diǎn), 作為重采樣點(diǎn)列的候選點(diǎn); 第二次掃描, 根據(jù)特定的條件, 在第一次掃描所產(chǎn)生的候選點(diǎn)中進(jìn)一步剔除一些點(diǎn), 形成最終的重采樣點(diǎn)列結(jié)果.

(1) 第一次掃描

在本次掃描中, 文獻(xiàn)[5]中采用一種非嚴(yán)格數(shù)學(xué)意義上的高曲率定義. 如圖1所示, 在當(dāng)前所處理的點(diǎn)P兩側(cè), 分別找出滿足表達(dá)式(1)與(2)的點(diǎn)對與P+, 并計(jì)算出由此三點(diǎn)所構(gòu)成三角形的一個內(nèi)角α, 如果角α滿足表達(dá)式(3), 則稱P為高曲率點(diǎn), 將其作為重采樣點(diǎn)列的候選點(diǎn). 繼續(xù)處理輪廓點(diǎn)列中的下一個點(diǎn), 如此反復(fù), 直到所有輪廓點(diǎn)處理完畢. 記錄所有候選點(diǎn)的坐標(biāo)值及其一個內(nèi)角α.

(2) 第二次掃描

如圖2所示, 在第一次掃描所產(chǎn)生的候選點(diǎn)列中選擇一個初始處理點(diǎn)P, 在其一側(cè)查找滿足表達(dá)式(4)或(5)的所有點(diǎn)Pv, 如果有任意一個點(diǎn)Pv使表達(dá)式(6)成立, 則P點(diǎn)被剔除. 繼續(xù)處理下一個候選點(diǎn), 如此反復(fù)直至處理所有候選點(diǎn), 最后所剩下的點(diǎn)就是重采樣點(diǎn)列.

式中: α(P)表示在第一次掃描過程所記錄下來的P 點(diǎn)所對應(yīng)的三角形內(nèi)角.

圖1

圖2

(3) 算法中的參數(shù)

算法在上述表達(dá)式(1)～ (5)中使用了三個可調(diào)參數(shù): dmax, dmin,αmax, 分別表示距離的最大、最小值與角度的最大值. 文獻(xiàn)[5]中設(shè)定 dmax= dmin+ 2. 如圖3中(a)～(d)分別是dmin與αmax取不同值時的實(shí)驗(yàn)結(jié)果.

(4) 算法改進(jìn)

作者在自己實(shí)現(xiàn)的上述算法測試程序中, 以及在文獻(xiàn)[5]所提供的網(wǎng)站上進(jìn)行實(shí)驗(yàn)比較, 在兩次掃描過程中設(shè)定參數(shù)為 dmax= 5, dmin= 3, αmax= 170時得到了該算法的最佳效果, 如圖4(b)所示, 從圖中可以很明顯地看到, 還可以剔除大量的點(diǎn), 但文獻(xiàn)[5]所提出的算法對此已無能為力了. 經(jīng)實(shí)驗(yàn)測試, 本文提出了如下改進(jìn)方法:

增加第四個參數(shù). 在原算法第二次掃描中, 表達(dá)式(4)與(5)中所使用參數(shù)仍然與第一次掃描中參數(shù)一致, 本文經(jīng)測試, 如果增加一個與第一次掃描中無任何關(guān)系的新參數(shù), 則重采樣數(shù)據(jù)的壓縮比有明顯改善,即本文將式(4)與(5)中參數(shù)dmax的值設(shè)置為10, 與式(1)與(2) 中參數(shù)dmax無約束關(guān)系. 如圖4所示, (a)是用來處理的原始切片圖像, (b)是使用文獻(xiàn)[5]的算法處理結(jié)果圖, (c)是改進(jìn)算法處理結(jié)果圖.

圖4 特征點(diǎn)列重采樣結(jié)果

原始算法的檢測結(jié)果, (c)是使用改進(jìn)算法的檢測結(jié)果. 顯然(c)所示結(jié)果圖中產(chǎn)生的點(diǎn)數(shù)量比(b)要少得多, 也即重采樣的壓縮比高, 同時仍然可以逼真的擬合原始輪廓曲線.

1.2 簡單的三角化算法

在這一過程中, 對重采樣后的輪廓點(diǎn)列采用如下簡單的三角化算法:

(1) 對所有序列圖像中重采樣后的輪廓點(diǎn)按同一方向掃描, 形成新的點(diǎn)序列;

(2) 在相鄰兩幀圖像的輪廓點(diǎn)序列中查找出其空間距離最小的兩個點(diǎn);

(3) 將(2)中所選擇的兩點(diǎn)作為三角形的兩個頂點(diǎn);

(4) 如圖5所示, 第三個頂點(diǎn)有兩種選擇方案, 但選擇α角較小者作為最優(yōu)三角形, 形成一個三角面片(網(wǎng)格).

圖5 三角形的第三個頂點(diǎn)選擇原理示意圖

(5) 選擇(4)生成的三角形第三邊的兩個頂點(diǎn), 作為下一個三角形的兩個頂點(diǎn), 然后重復(fù)(4), 直至(2)所處理的兩幀圖像中所有輪廓點(diǎn)序列均被處理完畢.

(6) 變換相鄰的兩幀圖像, 然后重復(fù)(2)～(5), 如此反復(fù), 直至所有序列圖像中的輪廓點(diǎn)列均被處理完畢.如圖6中圖所示, 該三角化算法所產(chǎn)生的三角網(wǎng)格形態(tài)都比較理想, 三角網(wǎng)格的內(nèi)角基本都為銳角, 這樣可改善可視化過程中計(jì)算三角網(wǎng)格法向量的運(yùn)算速度(左圖為原始切片圖像, 中圖為三角化后的部分三角網(wǎng)格, 右圖為三維重建后的可視化結(jié)果).

圖6

2 結(jié)束語

本文討論了基于序列圖像三維重建中的關(guān)鍵算法, 提出了一種改進(jìn)的輪廓曲線上高曲率點(diǎn)檢測算法,并應(yīng)用于特征點(diǎn)列的重采樣處理中. 實(shí)驗(yàn)結(jié)果表明, 該算法明顯的改善了重采樣過程中的數(shù)據(jù)壓縮比, 從而使用后續(xù)處理(如三角化)的數(shù)據(jù)大大減少, 加速了可視化的處理速度. 在重慶第三軍醫(yī)大學(xué)所提供的人體切片圖像數(shù)據(jù)集的基礎(chǔ)上, 采用本文所討論的算法實(shí)現(xiàn)了人體外形輪廓的三維重建及可視化, 取得很好的效果. 圖6右圖顯示了運(yùn)用本文提出的算法進(jìn)行三維重建的可視化結(jié)果, 將本文算法(記為方法A)與運(yùn)用文獻(xiàn)[5]所提出的算法(記為方法B), 在可視化處理速度及輸出三角網(wǎng)格數(shù)量方面進(jìn)行了比較. 方法B是在提取二維圖像中外輪廓后, 運(yùn)用文獻(xiàn)[5]的原始算法進(jìn)行特征點(diǎn)重采樣, 然后進(jìn)行三角化及可視化處理. 在IBM ThinkPad R50(CPU為迅馳1.6G, 內(nèi)存512M)計(jì)算機(jī)上測試, 僅顯示圖6右圖所示的人體肩部以上部分, 基于面繪制的可視化處理平均時間分別為: 方法A為0.9秒, 方法B為6分. 對圖6右圖處理的部分, 方法A最終輸出的三角網(wǎng)格數(shù)目為110520個, 而方法B輸出三角網(wǎng)格數(shù)目已超過300000多個.

[1] 中國可視化人體: http://www.chinesevisiblehuman.com/

[2] 金豐華, 朱 斌, 周光泉, 等. 一個基于內(nèi)容檢索的醫(yī)學(xué)圖像數(shù)據(jù)庫[J]. 山東生物醫(yī)學(xué)工程, 2003(3)

[3] Grimson, W. E. L., Ettinger, G. J., Kapur, T., Leventon, M. E., Wells III, W. M., Kikinis, R.,Utilizing SegmentedMRIData in Image Guided Surgery[J], Inter. Journal of Pattern Recognition and Artificial Intelligence, 1998,11(8).

[4] Virtual Reality,Visualization and Imaging Research Centre: http://www.cse.cuhk.edu.hk/～crc/

[5] Dmitry Chetverikov and Zsolt Szabo.A Simple and Efficient Algorithm for Detection of High Curvature Points in Planar Curves[C]. //Proc. of 4 (k=4) the 23rd Workshop of the Austrian Pattern Recognition Group. [S. l]: ACM Press, 1999: 175～184

[6] W.Loresen and H.Cline.Marching Cubes:A high resolution 3D Surface Construction Algorithm. ACM Computer Graphics, 1987, 31(4): 163～170.

[7] R.Shekhar, E.Fayyad, R.Yagel and J.Cornhill.Octree-based Decimation of Marching Cubes Surfaces[J]. In IEEE Visualization’96 Proceedings, 1996, 335-342.

[8] Shu, R.Chen, Z.Kankanhalli.Adaptive Marching Cubes[J]. The Visual Computer, 1995, 11: 202～217

The Algorithm about 3D Reconstruction of Image Sequences

FANG Xin1, GUO Guan-qi1, SHEN Zhong-yang2
(1. College of Information & Communication Engineering, Hunan Institute of Science and Technology, Yueyang 414006, China; 2. Zixing Activity Centre for Teenagers, Chenzhou 423400, China )

TP317.4

A

1672-5298(2010)01-0035-04

2009-09-29

方 欣(1971- ), 男, 湖南岳陽人, 碩士, 湖南理工學(xué)院信息與通訊工程學(xué)院講師. 主要研究方向: 計(jì)算機(jī)網(wǎng)絡(luò)、圖像處理