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

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

(河北工業大學計算機科學與軟件學院，天津300401)

0 引言

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

1 PMVS算法

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

圖1 PMVS算法流程

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

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

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

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

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

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

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

2 加入法向調整的PMVS算法改進

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

步驟1 根據重建場景的不同選擇恰當的分辨率等級Level L進行PMVS點云重建，在得到的稀疏片面集合中選擇某個種子片面p，采用KD(K-dimension)樹算法尋找p的k近鄰片面。

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

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

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

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

3 實驗與分析

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

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

圖5 重建結果

表1 原始PMVS算法與加入法向調整的算法的重建結果對比

實驗結果表明，改進后的算法比原始算法得到的片面總數增加了將近4%，并且改進后的算法在物體表面結構復雜的區域得到了較好的細節刻畫效果，重建出的物體表面也更加光滑，更加連續。

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

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

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

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

表2 單一分辨率與多分辨率分級重建的運行時間對比

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

4 結束語

雖然PMVS算法是目前公認的重建效果最好的算法之一，但是在對一些具有復雜結構的場景進行重建時，場景的一些細節重建效果并不理想，重建出的物體表面不夠連續，與真實物體的形狀有一些偏差，因此本文通過考慮近鄰片面對新片面的影響，對新的片面加入了法向的調整，使重建出的物體表面更連續更接近真實物體的形狀，進而提高了重建的準確性。另外PMVS算法的時間復雜度與空間復雜度非常大，特別是對于高分辨率的場景進行重建時，算法運行時間非常長，因此本文采用多分辨率分級重建的策略，根據物體表面結構復雜程度進行不同級別的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).［束搏，邱顯杰，王兆其.基于圖像的幾何建模技術綜述［J］.計算機研究與發展，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).［錢蘇斌，林意.基于輪廓線的旋轉曲面三維重建 ［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).［王艷霞.圖像輪廓提取與三維重建關鍵技術研究［D］.重慶:重慶大學，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).［李濤.單目視圖與多目視圖的深度圖恢復方法研究［D］.北京:清華大學，2009:14-26.］

［6］Pons J P，Keriven R，Faugeras 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］.計算機工程與設計，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).［劉偉，馬俊.基于多視圖的三維空間點精確重建算法［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).［史利民，郭復勝，胡占義.利用空間幾何信息的改進PMVS算法 ［J］.自動化學報，2011，37(5):561-563.］