基于立體視覺的三維重建算法

2013-07-25 02:28齊菲菲薛翠紅

計算機(jī)工程與設(shè)計 2013年2期

于明，齊菲菲，于洋，閻剛，薛翠紅

(河北工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院，天津300401)

0 引言

隨著科技的發(fā)展，三維重建技術(shù)已引起越來越多的計算機(jī)圖形學(xué)研究人員的關(guān)注［1］。目前基于立體視覺的三維重建算法主要有下面幾類:基于輪廓線的算法［2-3］。這類算法通過利用物體投影在圖像平面上的輪廓線來重構(gòu)物體的三維模型;基于深度圖的算法［4-5］。該類算法通過配準(zhǔn)和合并多幅包含圖像深度值的深度圖像來得到物體表面的完整信息;基于體素的算法［6］。這類算法通過將待重建物體劃分為一個個小立方體柵格，然后基于這些體素來進(jìn)行物體的三維重建;基于匹配點(diǎn)的算法［7-8］。該類算法首先通過圖像序列得到物體的稀疏點(diǎn)云結(jié)構(gòu)，再通過擴(kuò)散操作得到物體表面的稠密點(diǎn)云［9-10］。PMVS(patch multi-view stereo)算法［11］便是一種基于面片 (將匹配點(diǎn)用片面形式表示)的點(diǎn)云重建算法，它是通過擴(kuò)展種子面片的原理完成物體表面重建的，是目前公認(rèn)重建效果最好的算法之一。但是PMVS算法在片面擴(kuò)展過程中，容易出現(xiàn)重建表面不夠連續(xù)，與真實(shí)物體的形狀有一些偏差等情況。同時由于PMVS算法空間和時間復(fù)雜度比較高，在處理高分辨率圖像時需要付出巨大的時間和空間代價。針對上述問題，本文提出了一種加入法向調(diào)整的PMVS改進(jìn)算法，并且通過采用多分辨率分級重建策略［12］在一定程度上提高了重建效率。

1 PMVS算法

PMVS算法是由Y.Furukawa等人提出的，它的基本原理是利用Harris算子和DoG(Difference-of-Gaussian)算子檢測出每幅圖像中的特征點(diǎn)，然后利用匹配算法得到稀疏的三維點(diǎn)云結(jié)構(gòu)，再將這些匹配點(diǎn)定義成種子片面，通過擴(kuò)展種子片面得到稠密的片面結(jié)構(gòu)。PMVS算法通常要進(jìn)行多次的擴(kuò)展和過濾操作以達(dá)到高精度的重建效果。算法流程如圖1所示。

圖1 PMVS算法流程

為了方便介紹PMVS算法的原理，給出以下幾個定義:

(1)片面模型 PMVS算法將重建出的每個匹配特征點(diǎn)f對應(yīng)成一個種子片面p，它包含幾個屬性c(p)，n(p)，R(p)，分別表示片面p的中心，p的單位法向，p的參考圖片(p在圖片上是可見的)。它們的初始值定義如下

(O(Ii)表示圖片Ii對應(yīng)的攝像機(jī)光心)

(2)光學(xué)誤差函數(shù) 定義V(p)是p的可見圖像的集合，光學(xué)誤差函數(shù)定義如下

其中h(p，I1，I2)是圖片I1和I2間的灰度差異函數(shù)，PMVS算法通過用共軛梯度法最小化光學(xué)誤差函數(shù)的方法，在p的匹配特征點(diǎn)集合中選擇最優(yōu)的一個作為最終的面片。

(3)圖像塊模型 PMVS算法將每幅圖像Ii劃分為一個個大小為β×β個像素的圖像塊C(x，y)，以每個圖像塊里至少重建出一個種子片面，來確保重建出的面片集合能完全覆蓋物體表面。

PMVS算法重建過程分三步:特征點(diǎn)檢測與匹配，面片擴(kuò)展，錯誤片面過濾。首先通過DoG算子和Harris算子提取特征點(diǎn)，根據(jù)極線約束原理獲取匹配特征點(diǎn)集合，設(shè)某個特征點(diǎn)f對應(yīng)一個種子片面p，利用式 (1)，(2)，(3)初始化p，將得到的c(p)和n(p)作為變量，用共軛梯度法最小化灰度差異值，在p的匹配特征點(diǎn)集合中選擇最優(yōu)的一個作為最終對應(yīng)面片。接下來進(jìn)行片面的擴(kuò)展，在p的鄰居圖像塊Ci(x，y)中擴(kuò)展p的近鄰片面p'，首先利用片面p的信息初始化片面p'，c(p')的初始值為Ci(x，y)的中心投影線與p所在平面的交點(diǎn)，n(p')的初始值等于n(p)，再利用優(yōu)化過程對c(p')和n(p')進(jìn)行優(yōu)化，從而得到一個新的片面，直到擴(kuò)展出的片面集合能夠完全覆蓋物體表面。擴(kuò)展結(jié)束后，要進(jìn)行過濾操作，將灰度一致性、幾何一致性比較弱的片面剔除。

2 加入法向調(diào)整的PMVS算法改進(jìn)

PMVS算法在進(jìn)行片面擴(kuò)展過程中，對于每個重建出的新片面都要進(jìn)行一次共軛梯度法迭代操作來對片面進(jìn)行優(yōu)化，這樣就使得算法的時間復(fù)雜度非常大，特別當(dāng)圖像較多，圖像分辨較大時，PMVS算法的空間復(fù)雜度和時間復(fù)雜度將是非常大的。同時PMVS在生成新的片面時，僅僅利用當(dāng)前片面的信息來初始化新片面的參數(shù)，并沒有考慮周圍片面的信息，這樣重建出的片面集合往往連接性不好，重構(gòu)出的物體表面不夠光滑。所以既要保證重建精度又能提高重建效率正是本文采用多分辨率分級重建的初衷。實(shí)際上在重建物體時，僅需要在物體結(jié)構(gòu)比較復(fù)雜的區(qū)域重建出較稠密的點(diǎn)云，而在物體結(jié)構(gòu)較平坦的區(qū)域少量的點(diǎn)云便可以描述物體形狀。PMVS算法為用戶提供了選擇分辨率等級的接口，Level 0級指原始圖像，Level L指下采樣圖像，其長、寬是原始圖像長、寬的1/2L。我們可以先選擇在適當(dāng)?shù)牡燃壣线M(jìn)行PMVS重建，利用重建出的稀疏片面，計算每個片面中心點(diǎn)的主曲率，如果其主曲率大于設(shè)定的閾值，則說明物體在該點(diǎn)周圍區(qū)域內(nèi)形狀有較大變化，則需要在該點(diǎn)周圍區(qū)域進(jìn)行高分辨等級的PMVS重建［12］。算法的基本框架如下:

步驟1 根據(jù)重建場景的不同選擇恰當(dāng)?shù)姆直媛实燃塋evel L進(jìn)行PMVS點(diǎn)云重建，在得到的稀疏片面集合中選擇某個種子片面p，采用KD(K-dimension)樹算法尋找p的k近鄰片面。

步驟2 利用p及k近鄰片面集合擬合二次曲面，計算出每個點(diǎn)的主曲率，如果存在主曲率絕對值大于閾值T的點(diǎn)，則把這些點(diǎn)放在集合Q里，把p所在的圖像塊以及其周邊的八個圖像塊一起做下標(biāo)記。

步驟3 把集合Q里的點(diǎn)作為新的種子片面，在做了標(biāo)記的圖像塊上進(jìn)行分辨率等級為Level L－1的PMVS片面擴(kuò)展重建，在擴(kuò)展當(dāng)前片面p的一個臨近片面p'時，為考慮周圍片面對新的片面p'的影響，找到與p距離最近的另一個片面p″，設(shè)p″與p在水平方向上的距離為a，在垂直方向上的距離為b。如果a和b滿足a≤la，b≤lb且0.3＜a/b＜2(其中l(wèi)a和lb為提前設(shè)置的閾值，0.3＜a/b＜2表示a與b不能相差太多，否則意味著斷層現(xiàn)象，不宜再考慮p″對p'的影響)則執(zhí)行步驟4，否則僅用p的信息初始化p'。

步驟4 設(shè)當(dāng)前片面p所在的圖像塊的中心投影線與片面p的交點(diǎn)為p0，則可用pp0表示p到p'的水平距離，記作l，那么p″到p'的水平距離為a－l。在初始化片面p'的法向n(p')時，綜合考慮n(p)和n(p″)的影響，設(shè)它們的影響系數(shù)分別為a－l/a和l/a，則有

步驟5 將上面步驟得到的n(p')做參數(shù)，利用共軛梯度法迭代優(yōu)化新片面p'的位置和法向，最終得到最優(yōu)的新的片面p'，依次在做過標(biāo)記的圖像塊中對剩下的片面進(jìn)行以上步驟的擴(kuò)展操作，直到圖像分辨率等級提高為Level 0，則算法停止。

3 實(shí)驗(yàn)與分析

本文利用從多個角度拍攝的真實(shí)圖像序列，來進(jìn)行PMVS算法及本文改進(jìn)算法的對比實(shí)驗(yàn)。實(shí)驗(yàn)分為兩部分，實(shí)驗(yàn)1分別用原始的PMVS算法和加入法向調(diào)整后的改進(jìn)算法對真實(shí)圖像序列進(jìn)行三維重建，并比較重建結(jié)果。實(shí)驗(yàn)2分別用單分辨率PMVS算法和加入多分辨率分級重建后的算法，對真實(shí)圖像序列進(jìn)行三維重建，并比較重建結(jié)果。

實(shí)驗(yàn)1 本文的實(shí)驗(yàn)數(shù)據(jù)是通過攝像機(jī)每隔10度拍攝得到的兩組圖像序列。圖像分辨率為1600×1200，圖2、圖4為圖像序列，圖3、圖5為原始PMVS算法和加入法向調(diào)整后的算法的重建效果對比。表1列出了重建片面總數(shù)的結(jié)果對比。

圖5 重建結(jié)果

表1 原始PMVS算法與加入法向調(diào)整的算法的重建結(jié)果對比

實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法比原始算法得到的片面總數(shù)增加了將近4%，并且改進(jìn)后的算法在物體表面結(jié)構(gòu)復(fù)雜的區(qū)域得到了較好的細(xì)節(jié)刻畫效果，重建出的物體表面也更加光滑，更加連續(xù)。

實(shí)驗(yàn)2 利用上圖2及圖4中的圖像序列，分別進(jìn)行單一分辨率與多分辨率分級的PMVS重建。圖6、圖7是實(shí)驗(yàn)結(jié)果對比。其中進(jìn)行多分辨率分級重建時選擇初始分辨率為Level 2。

圖6(a)為原始PMVS算法在Level 0等級上的重建結(jié)果，圖6(b)為從Level 2到Level 0上的重建結(jié)果，首先從Level 2上重建得到47895個稀疏點(diǎn)，根據(jù)計算曲率，設(shè)置曲率閾值T=5，得到18206個種子點(diǎn)，然后利用這些點(diǎn)在Level 1上進(jìn)行重建，得到69162個點(diǎn)，將閾值調(diào)整為6，得到下一步的種子點(diǎn)25589個，再利用這些點(diǎn)在Level 0上進(jìn)行重建，得到97239個點(diǎn)，將三次的重建結(jié)果合并得到圖6(b)的重建結(jié)果。

圖7(a)為原始PMVS算法在Level 0等級上的重建結(jié)果，圖7(b)為從Level 2到Level 0上的重建結(jié)果，首先從Level 2上重建得到38581個稀疏點(diǎn)，根據(jù)計算曲率，設(shè)置曲率閾值T=5，得到14725個種子點(diǎn)，然后利用這些點(diǎn)在Level 1上進(jìn)行重建，得到56959個點(diǎn)，將閾值調(diào)整為6，得到下一步的種子點(diǎn)20574個，再利用這些點(diǎn)在Level 0上進(jìn)行重建，得到78182個點(diǎn)，將三次的重建結(jié)果合并得到圖7(b)的重建結(jié)果。

表2列出了兩組實(shí)驗(yàn)的運(yùn)行時間，通過對比可知采用多分辨率分級重建的PMVS算法比原始的算法在運(yùn)行時間上縮短了很多。

表2 單一分辨率與多分辨率分級重建的運(yùn)行時間對比

本文實(shí)驗(yàn)環(huán)境:Intel雙核 (CPU 2.80GHz)，2G內(nèi)存，Windows XP操作系統(tǒng)。算法利用Visual C++實(shí)現(xiàn)。本文實(shí)驗(yàn)中閾值la=6l，lb=3l(l為每次計算得到的常數(shù))，β=2，k=100，T=5～10。

4 結(jié)束語

雖然PMVS算法是目前公認(rèn)的重建效果最好的算法之一，但是在對一些具有復(fù)雜結(jié)構(gòu)的場景進(jìn)行重建時，場景的一些細(xì)節(jié)重建效果并不理想，重建出的物體表面不夠連續(xù)，與真實(shí)物體的形狀有一些偏差，因此本文通過考慮近鄰片面對新片面的影響，對新的片面加入了法向的調(diào)整，使重建出的物體表面更連續(xù)更接近真實(shí)物體的形狀，進(jìn)而提高了重建的準(zhǔn)確性。另外PMVS算法的時間復(fù)雜度與空間復(fù)雜度非常大，特別是對于高分辨率的場景進(jìn)行重建時，算法運(yùn)行時間非常長，因此本文采用多分辨率分級重建的策略，根據(jù)物體表面結(jié)構(gòu)復(fù)雜程度進(jìn)行不同級別的PMVS重建，這樣既保證了重建的精度，又提高了重建的效率。

［1］SHU Bo，QIU Xianjie，WANG Zhaoqi.Survey of shape from image［J］.Journal of Computer Research and Development，2010，47(3):549-560(in Chinese).［束搏，邱顯杰，王兆其.基于圖像的幾何建模技術(shù)綜述［J］.計算機(jī)研究與發(fā)展，2010，47(3):549-560.］

［2］QIAN Subin，LIN Yi.3D reconstruction of rotated surface based on contour lines［J］.Computer Engineering and Design，2009，30(16):3875-3878(in Chinese).［錢蘇斌，林意.基于輪廓線的旋轉(zhuǎn)曲面三維重建［J］.計算機(jī)工程與設(shè)計，2009，30(16):3875-3878.］

［3］WANG Yanxia.Research on profile extraction and key technologies for 3D reconstruction［D］.Chongqing:University of Chongqing，2010:63-74(in Chinese).［王艷霞.圖像輪廓提取與三維重建關(guān)鍵技術(shù)研究［D］.重慶:重慶大學(xué)，2010:63-74.］

［4］Bradley D，Boubekeur T，Heidrich W.Accurate multi-view reconstruction using robust binocular stereo and surface meshing［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Anchorage，USA:IEEE，2008:1-8.

［5］LI Tao.Depth map recovery for monocular and multi-view images［D］.Beijing:Tsinghua University，2009:14-26(in Chinese).［李濤.單目視圖與多目視圖的深度圖恢復(fù)方法研究［D］.北京:清華大學(xué)，2009:14-26.］

［6］Pons J P，Keriven R，F(xiàn)augeras O D.Multi-view stereo reconstruction and scene flow estimation with a global image based matching score［J］.International Journal of Computer Vision，2007，72(2):179-193.

［7］ZHU Qingsheng，LUO Dajiang，GE Liang，et al.Multiple-imagebased 3D reconstruction ［J］.Computer Engineering and Design，2010，31(10):2351-2357(in Chinese).［朱慶生，羅大江，葛亮，等.基于多幅圖像的三維重建［J］.計算機(jī)工程與設(shè)計，2010，31(10):2351-2357.］

［8］LIU Wei，MA Jun.Accurate linear triangulation method based on multiple view ［J］.Computer Engineering and Design，2009，30(12):3035-3037(in Chinese).［劉偉，馬俊.基于多視圖的三維空間點(diǎn)精確重建算法［J］.計算機(jī)工程與設(shè)計，2009，30(12):3035-3037.］

［9］Furukawa Y，Curless B，Seitz S M，et al.Towards internet-scale multi-view stereo［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Miami，USA:IEEE，2010:1434-1441.

［10］Hiep V H，Keriven R，Labatut P，et al.Towards high-resolution large-scale multi-view stereo［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Miami，USA:IEEE，2009:1430-1437.

［11］Furukawa Y，Ponce J.Accurate，dense，and robust multi-view stereopsis［C］//Proceedings of the IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(8):1362-1376.