基于有序圖像的快速三維重建

劉保江，尹顏朋

（四川大學計算機學院，成都 610065）

0 引言

計算機三維重建技術是當前研究的一個熱點。三維重建目的是從輸入的多張二維場景圖像恢復出場景三維立體模型。與傳統(tǒng)的利用激光掃描儀等精密設備直接測量出物體三維模型相比具有方便、成本低以及適用范圍廣等優(yōu)點，在文物考古、醫(yī)療衛(wèi)生、旅游、數字娛樂和軍事測繪導航等各個領域應用廣泛。

進幾十年來出現了許多基于圖像視覺的三維重建方法，例如明暗度法[1-3]、紋理法[4-6]、輪廓法[7-8]、運動法[9]、調焦法[10]、雙目視覺法[11]和多目視覺法[12]等。但是大都存在重建精度較差、魯棒性較差問題，或是重建效果不錯，但存在運算時間太長問題。故如何在達到不錯的重建質量基礎上提高重建速度就顯得十分重要。

針對上面提出的方法存在的問題，本文提出一種基于有序圖像序列的快速三維重建方法，在三維重建過程中，僅對相鄰的圖像進行特征匹配，對于n張輸入圖像，能夠將匹配階段的時間復雜度從O（n2）降低到O（n），對于大場景的重建在時間上節(jié)省尤為明顯。然后利用多視圖幾何和對極幾何約束關系，計算出場景的幾何結構和攝像機的參數信息，重建出場景的三維立體模型，并使重建質量達到傳統(tǒng)的三維重建的水平。主要包括三個步驟：相鄰圖像匹配、增量重建、點云優(yōu)化。

1 算法實現

輸入圖像時，要保證輸入圖像是有序序列，即任意兩張相鄰的圖像為需要重建的圖像。在相鄰圖像匹配前，需要先確定攝像機內部參數。本文采用讀取EXIF信息方法，因為許多攝像機的焦距和其他信息存放在圖像的EXIF信息中，先通過對圖像的EXIF信息解析得到相機的內參K，雖然并不一定精確，但可以將其作為攝像機的初始內參，然后在后續(xù)重建過程中對攝像機內參K進行優(yōu)化。

1.1相鄰圖像匹配

檢測所有圖像中的特征點是匹配的第一步。本文采取的是SIFT方法[13]，總體思想為：首先對圖像I（x,y）構造尺度空間：

進一步得到高斯差分尺度空間：

其中G(x ,y,σ ) 是尺度可變高斯函數，D(x ,y,σ)是高斯差分尺度空間。然后檢測尺度空間中極值點，將檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2共26個點比較，若為最大值或最小值就認為是特征點。接著去除不好的特征點，然后將特征點賦值128維的方向參數，用以生成特征點描述子。完成特征點檢測后，對兩圖匹配圖像，通過特征點描述子之間的距離計算可得到匹配的特征點對。

傳統(tǒng)的重建方法在此處會對任意的兩張圖像進行匹配，匹配的結果用于后續(xù)求同一三維空間點在各圖像上對應的特征點序列和反投影求三維空間點。本算法在此處只對相鄰的圖像進行匹配。對于N張輸入圖像，傳統(tǒng)方法共需要進行N*（N-1）/2次匹配，而本算法只需要進行N-1次匹配。故對于較大的N，此處節(jié)省的時間尤為明顯。

1.2 三維重建

三維重建的過程是一個增量重建的過程，先對前兩幅圖像進行重建，然后按輸入圖像順序依次對加入圖像進行重建。對于任何兩張圖像重建過程如下：

先根據對極幾何約束通過匹配點對求出基礎矩陣F:

其中x1和x2為兩圖上對應的匹配點。由上式可知最少需要8對點可求得F矩陣，然后通過基礎矩陣F得到essential矩陣E:

其中K’和K分別為兩圖對應的攝像機的內參矩陣，F為求得的基礎幾張。然后通過SVD分解恢復出攝像機外參R和T，從而可以求得攝像機投影矩陣P。

通過上面步驟得到了匹配點的坐標和相機投影矩陣P。在對極幾何約束下一對匹配點反投影射線在空間中相交，該空間點位置坐標即為兩匹配點對應的三維空間點。故對于需要重建的兩張圖像：

假設空間點X（X,Y,Z,1）T在圖像上的投影為圖像點 x（x,y,1）T，則有：

進一步得到:

其中,PiT是矩陣P的第i行。因此通過兩圖可以得到：

這是一個具有四個齊次未知量的四個方程,其解在相差一個尺度因子下被確定。對矩陣A采用SVD可求出對應三維空間點的坐標X（X,Y,Z,1）T。

采用上述三維重建方法，依次對相鄰兩張圖像進行重建，可以得到初始三維重建結果：稀疏的三維點云。且傳統(tǒng)的方法對于加入的待重建的圖像，會將它和所有已加入的圖像進行嘗試重建，這也會在很大程度上增加重建時間。

1.3點云優(yōu)化

每次加入圖片會重建出三維點，得到的只是初始的三維點，需要在每次加入圖片重建出三維點后對已有的點云進行優(yōu)化。對于重建出的點云理論上滿足：

其中Xj代表空間中第j個三維點，Pi代表第i個相機，xi

j表示第j個3D點經過第i個相機在圖像上的投影。優(yōu)化目標就是：

其中d（x,y）代表齊次點x和y的幾何圖像距離，i是優(yōu)化估計后的投影矩陣，j是優(yōu)化估計后的3D點，表示第j個3D點經過第i個相機在圖像上的投影。在每次加入圖片重建后，都需要進行一次全局優(yōu)化，然后將反投影誤差較大的點剔除，直到去除所有的異常點后繼續(xù)加入下一張圖片進行重建。所有圖片都加入重建完成后，再進行一次整體優(yōu)化。重復上述去除異常點步驟，得到重建后稀疏點云。然后將稀疏點云文件輸入PMVS2中，通過特征匹配、擴展和過濾過程將稀疏點云稠密化，得到最終的三維點云模型。

2 實驗結果與分析

硬件環(huán)境基于Intel Core i7-4790k CPU@4.0 GHz。本文實驗使用了22張圖像的數據集，分別用文獻[12]中提供的方法和本文的方法，比較結果如圖1所示。

在時間花費上，文獻[12]中的方法稀疏重構部分共計花費895s,本文的方法共計花費208s，其中主要的差別體現在圖像匹配部分，文獻[12]中的方法和本文方法耗時分別為828s和194s。在增量重建部分本文方法也比文獻[12]中方法要快一點，但差距并不明顯。總體來說，本文在時間花費上比文獻[12]中方法具有比較明顯優(yōu)勢，且由分析可知，輸入圖像的數量N越大，優(yōu)勢會越明顯。

實驗結果表明，與傳統(tǒng)的多視角三維重建相比，本方法能達到相同水平的重建效果，甚至在某些局部區(qū)域具有更好的結果，且在時間上更具有優(yōu)勢。但由于本算法要求輸入圖像序列有序，因此對數據采集要求較為嚴格，無法處理無序圖片序列。故本算法仍需改進，需要做到能對無序圖片篩選排序。

圖1 [12]中的方法和本文方法進行比較

[1]Horn B K P.Shape from Shading:A Method for Obtaining the Shape of a Smooth Opaque Object from One View[J]，1970.

[2]Bakshi S,Yang Y H.Shape from Shading for Non-Lambertian Surfaces[C].Image Processing,1994.Proceedings.ICIP-94.,IEEE International Conference.IEEE,1994,2:130-134.

[3]Subbarao M,Gurumoorthy N.Depth Recovery from Blurred Edges[C].Computer Vision and Pattern Recognition,1988.Proceedings CVPR′88.,Computer Society Conference on.IEEE,1988:498-503.

[4]Clerc M,Mallat S.The Texture Gradient Equation for Recovering Shape from Texture[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24（4）:536-549.

[5]Loh A M,Hartley R I.Shape from Non-Homogeneous,Non-Stationary,Anisotropic,Perspective Texture[C].BMVC.2005:69-78.

[6]Massot C,Hérault J.Model of Frequency Analysis in the Visual Cortex and the Shape from Texture Problem[J].International Journal of Computer Vision,2008,76（2）:165-182.

[7]Favaro P,Soatto S.A Geometric Approach to Shape from Defocus[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27（3）:406-417.

[8]Casas J R,Salvador J.Image-Based Multi-View Scene Analysis Using′Conexels′[C].Proceedings of the HCSNet Workshop on Use of Vision in Human-Computer Interaction-Volume 56.Australian Computer Society,Inc.,2006:19-28.

[9]Tomasi C,Kanade T.Shape and Motion from Image Streams under Orthography:a Factorization Method[J].International Journal of Computer Vision,1992,9（2）:137-154.

[10]Noakes L,Kozera R.Nonlinearities and Noise Reduction in 3-Source Photometric Stereo[J].Journal of Mathematical Imaging and Vision,2003,18（2）:119-127.

[11]Stewart C V,Dyer C R.The Trinocular General Support Algorithm:A Three-Camera Stereo Algorithm for Overcoming Binocular Matching Errors[C].Computer Vision.,Second International Conference on.IEEE,1988:134-138.

[12]Snavely N,Seitz S M,Szeliski R.Modeling the World from Internet Photo Collections[J].International Journal of Computer Vision,2008,80（2）:189-210.

[13]Lowe D G.Distinctive Image Features from Scale-Invariant Keypoints[J].International journal of computer vision,2004,60（2）:91-110.