基于立體視覺(jué)的三維重建算法

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

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

0 引言

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

1 PMVS算法

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

圖1 PMVS算法流程

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

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

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

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

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

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

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

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

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

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

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

步驟3 把集合Q里的點(diǎn)作為新的種子片面，在做了標(biāo)記的圖像塊上進(jìn)行分辨率等級(jí)為L(zhǎng)evel L－1的PMVS片面擴(kuò)展重建，在擴(kuò)展當(dāng)前片面p的一個(gè)臨近片面p'時(shí)，為考慮周圍片面對(duì)新的片面p'的影響，找到與p距離最近的另一個(gè)片面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″對(duì)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')時(shí)，綜合考慮n(p)和n(p″)的影響，設(shè)它們的影響系數(shù)分別為a－l/a和l/a，則有

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

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

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

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

圖5 重建結(jié)果

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

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

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

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

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

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

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

本文實(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為每次計(jì)算得到的常數(shù))，β=2，k=100，T=5～10。

4 結(jié)束語(yǔ)

雖然PMVS算法是目前公認(rèn)的重建效果最好的算法之一，但是在對(duì)一些具有復(fù)雜結(jié)構(gòu)的場(chǎng)景進(jìn)行重建時(shí)，場(chǎng)景的一些細(xì)節(jié)重建效果并不理想，重建出的物體表面不夠連續(xù)，與真實(shí)物體的形狀有一些偏差，因此本文通過(guò)考慮近鄰片面對(duì)新片面的影響，對(duì)新的片面加入了法向的調(diào)整，使重建出的物體表面更連續(xù)更接近真實(shí)物體的形狀，進(jìn)而提高了重建的準(zhǔn)確性。另外PMVS算法的時(shí)間復(fù)雜度與空間復(fù)雜度非常大，特別是對(duì)于高分辨率的場(chǎng)景進(jìn)行重建時(shí)，算法運(yùn)行時(shí)間非常長(zhǎng)，因此本文采用多分辨率分級(jí)重建的策略，根據(jù)物體表面結(jié)構(gòu)復(fù)雜程度進(jìn)行不同級(jí)別的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ì)算機(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).［錢(qián)蘇斌，林意.基于輪廓線的旋轉(zhuǎn)曲面三維重建 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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ì)算機(jī)工程與設(shè)計(jì)，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ì)算機(jī)工程與設(shè)計(jì)，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.

［12］SHI Limin，GUO Fusheng，HU Zhanyi.An improved PMVS through scene geometric information ［J］.Acta Automatica Sinica，2011，37(5):561-563(in Chinese).［史利民，郭復(fù)勝，胡占義.利用空間幾何信息的改進(jìn)PMVS算法 ［J］.自動(dòng)化學(xué)報(bào)，2011，37(5):561-563.］