劉保江，尹顏朋

（四川大學(xué)計算機(jī)學(xué)院，成都 610065）

0 引言

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

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

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

1 算法實現(xiàn)

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

1.1相鄰圖像匹配

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

進(jìn)一步得到高斯差分尺度空間：

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

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

1.2 三維重建

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

先根據(jù)對極幾何約束通過匹配點對求出基礎(chǔ)矩陣F:

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

其中K’和K分別為兩圖對應(yīng)的攝像機(jī)的內(nèi)參矩陣，F(xiàn)為求得的基礎(chǔ)幾張。然后通過SVD分解恢復(fù)出攝像機(jī)外參R和T，從而可以求得攝像機(jī)投影矩陣P。

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

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

進(jìn)一步得到:

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

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

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

1.3點云優(yōu)化

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

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

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

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

2 實驗結(jié)果與分析

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

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

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

圖1 [12]中的方法和本文方法進(jìn)行比較

[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.