北京航空航天大學(xué)計(jì)算機(jī)學(xué)院　林連慶　楊志剛

一種基于圖像集合的三維重建方法

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院林連慶楊志剛

設(shè)計(jì)并實(shí)現(xiàn)了一整套基于圖像集合的三維重建技術(shù)。首先對(duì)輸入的多幅圖像提取特征點(diǎn)，然后將這些特征點(diǎn)進(jìn)行匹配，接著迭代運(yùn)行從運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)的優(yōu)化算法，得到相機(jī)參數(shù)以及稀疏的空間點(diǎn)云信息，最后利用多視圖立體重建方法得到稠密的空間點(diǎn)云模型，完成對(duì)目標(biāo)的三維重建。實(shí)驗(yàn)結(jié)果表明，本文采用的方法不需要特定的設(shè)備，無(wú)需人工干預(yù)即可自動(dòng)重建出正確的被觀測(cè)目標(biāo)的三維模型。

三維重建；特征點(diǎn)提取與匹配；從運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)SFM；多視圖立體重建PMVS

1.引言

眾所周知，在我們生活的現(xiàn)實(shí)世界中，周?chē)h(huán)境和物體都是三維的客觀存在，這是人類(lèi)通過(guò)雙眼獲得的視覺(jué)信息。如何讓機(jī)器像人一樣感知、分析、理解、記憶以及再現(xiàn)外界的三維場(chǎng)景，是計(jì)算機(jī)視覺(jué)［1］研究的熱點(diǎn)課題之一，即通過(guò)運(yùn)用計(jì)算機(jī)和數(shù)字傳感設(shè)備來(lái)模擬人類(lèi)視覺(jué)功能，獲取被觀測(cè)目標(biāo)的三維幾何信息，這個(gè)過(guò)程就是三維重建。

基于計(jì)算機(jī)視覺(jué)的光學(xué)三維重建方法可以分為主動(dòng)式和被動(dòng)式兩大類(lèi)［2］。主動(dòng)法需要人為對(duì)目標(biāo)場(chǎng)景施加特定的照射光源，根據(jù)光束模式和物體表面的反射特性，利用光學(xué)原理及相關(guān)特性獲取待重建目標(biāo)高精度的三維信息，主要包括結(jié)構(gòu)光和激光掃描等方法。由于需要比較復(fù)雜且造價(jià)高昂的專(zhuān)用設(shè)備，不適合室外大型場(chǎng)景，使得其應(yīng)用受到限制。被動(dòng)法只利用在自然光照條件下拍攝的圖像，就可恢復(fù)出相機(jī)的運(yùn)動(dòng)和場(chǎng)景的結(jié)構(gòu)，具有簡(jiǎn)單易行、成本低廉、適應(yīng)性強(qiáng)、靈活度高等特點(diǎn)，近年來(lái)越來(lái)越受到研究重視。隨著數(shù)碼相機(jī)、攝像機(jī)、手機(jī)等硬件成像設(shè)備的普及，人們可以隨時(shí)隨地拍攝得到想要的圖片，再利用基于圖像的三維重建技術(shù)，直接根據(jù)這些圖片恢復(fù)物體的三維幾何結(jié)構(gòu)，甚至構(gòu)建出非常逼真的三維模型，在日常的生產(chǎn)生活中具有廣泛的應(yīng)用價(jià)值跟前景。

2.三維重建的原理和流程

基于圖像的三維重建是攝像機(jī)成像過(guò)程的逆過(guò)程，主要原理基于光學(xué)中的針孔成像模型，即：三維世界空間的點(diǎn)與二維成像平面上的投影點(diǎn)滿(mǎn)足中心射影的數(shù)學(xué)模型，如公式（1）所示，

本文基于圖像集合進(jìn)行三維重建的具體流程如圖1所示。主要步驟為特征提取與匹配、稀疏3D重建和稠密3D重建，本文將在后續(xù)內(nèi)容進(jìn)行詳細(xì)介紹。

3.特征提取與匹配

本文采用SIFT特征描述子結(jié)合Harris算法來(lái)進(jìn)行特征點(diǎn)提取，在SIFT特征點(diǎn)的基礎(chǔ)上加入了物體的角點(diǎn)特征，二者取長(zhǎng)補(bǔ)短，使得重建結(jié)果在細(xì)節(jié)上更加突出，更加接近真實(shí)物體。

圖1　基于圖像集合的三維重建流程圖

3.1SIFT算法

SIFT算法通過(guò)建立圖像的多尺度空間，在不同尺度下檢測(cè)到同一個(gè)特征點(diǎn)，確定特征點(diǎn)位置的同時(shí)確定其所在尺度，以達(dá)到尺度抗縮放的目的，剔出一些對(duì)比度較低的點(diǎn)以及邊緣響應(yīng)點(diǎn)，并提取旋轉(zhuǎn)不變特征描述子以達(dá)到抗仿射變換的目的。主要計(jì)算步驟如下：1）尺度空間極值檢測(cè)；2）關(guān)鍵點(diǎn)的定位；3）確定關(guān)鍵點(diǎn)的方向；4）生成特征點(diǎn)描述子。

由于SIFT特征描述子是一個(gè)128維的向量，可以采用基于歐式距離的最近鄰匹配算法（Nearest Neighbor-NN）完成粗匹配，其過(guò)程是：對(duì)圖像I1中的每個(gè)特征向量a，在圖像I2中利用kd-tree進(jìn)行搜索，查找I2所有特征點(diǎn)中與a對(duì)應(yīng)的最近鄰特征向量b以及次近鄰特征向量b’，如果最近鄰除以次近鄰的距離比值小于某個(gè)給定的比例閾值，即，則b為a的匹配，否則認(rèn)為a在I2中沒(méi)有匹配。實(shí)驗(yàn)中T的取值為0.6。

3.2Harris算法

Harris角點(diǎn)提取是一種基于圖像灰度梯度的檢測(cè)方法，由于自相關(guān)函數(shù)描述了局部圖像灰度的變化程度，將自相關(guān)函數(shù)的近似Hessian矩陣作為Harris算子，表達(dá)式如下：

Harris角點(diǎn)探測(cè)器的響應(yīng)函數(shù)為：

最后以每個(gè)特征點(diǎn)為中心，選取大小為（2n-1）×（2n-1）的灰度窗口稱(chēng)為特征點(diǎn)的鄰域窗（實(shí)驗(yàn)中n=7），利用歸一化互相關(guān)匹配算法（Normalized Cross Correlation， NCC）完成角點(diǎn)的初始匹配，設(shè)m1、m2分別為圖像I1和I2中待匹配的兩個(gè)角點(diǎn)，本文采用的相似度計(jì)算公式如下：

公式中，I（x，y）代表圖像I在像素（x，y）處的灰度值，為鄰域窗內(nèi)的灰度平均值。

3.3基于RANSAC算法優(yōu)化匹配

優(yōu)化過(guò)程利用基礎(chǔ)矩陣計(jì)算特征點(diǎn)到對(duì)應(yīng)極線的垂直距離作為約束（小于1.5個(gè)像素），將只有一個(gè)方向或者兩個(gè)方向都不滿(mǎn)足約束關(guān)系的匹配，視為虛假匹配，予以剔除。求解基礎(chǔ)矩陣采用的是改進(jìn)的8點(diǎn)法［3］。本文基于RANSAC算法實(shí)現(xiàn)對(duì)基礎(chǔ)矩陣的魯棒估計(jì)，通過(guò)對(duì)外點(diǎn)（outlier）加以限制，從數(shù)據(jù)中找到內(nèi)點(diǎn)（inlier），根據(jù)最大內(nèi)點(diǎn)數(shù)和最小誤差方差，選擇最優(yōu)的參數(shù)模型。

為了提高計(jì)算效率，本文采用改進(jìn)的RANSAC算法：在對(duì)每個(gè)模型參數(shù)檢驗(yàn)前，先隨機(jī)抽取少量的數(shù)據(jù)對(duì)模型進(jìn)行預(yù)檢驗(yàn)，如果預(yù)檢驗(yàn)通過(guò)，則繼續(xù)在全部數(shù)據(jù)中進(jìn)行模型評(píng)估，如果沒(méi)有通過(guò)預(yù)檢驗(yàn)，則放棄后面的評(píng)估過(guò)程。

圖2　兩幅圖像間三維重建流程圖

4.稀疏3D重建

本文采用從運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)（Structure From Motion， SFM）［4］的方法基于圖像集合重建目標(biāo)的三維模型。SFM方法從兩幅圖像的匹配和重建開(kāi)始，通過(guò)迭代逐漸增加新的圖像，直至重建整個(gè)圖像集合。通過(guò)兩幅圖像進(jìn)行三維重建的大體步驟如下：在獲得兩幅圖像間的匹配點(diǎn)對(duì)后，根據(jù)基本矩陣F求解Kruppa方程［5］，得到攝像機(jī)內(nèi)參數(shù)K；同時(shí)根據(jù)基本矩陣計(jì)算本質(zhì)矩陣E，對(duì)本質(zhì)矩陣進(jìn)行SVD分解得到攝像機(jī)的運(yùn)動(dòng)參數(shù)［6］——旋轉(zhuǎn)矩陣R和平移向量t；然后由內(nèi)外參數(shù)得到投影矩陣P；最后按照公式（1），由每對(duì)匹配點(diǎn)聯(lián)立方程，求解出空間離散點(diǎn)在相差一個(gè)尺度因子下的三維坐標(biāo)，生成空間稀疏3D點(diǎn)云。流程圖如圖2所示。

SFM將前兩幅圖像的重建結(jié)果作為一個(gè)初始結(jié)構(gòu)，利用光束法平差［7］對(duì)其進(jìn)行優(yōu)化，然后在此基礎(chǔ)上每次從圖像序列中選擇一副新的圖像加入此結(jié)構(gòu)，重復(fù)如下的迭代過(guò)程：

1）在新增圖像中找到已存在于當(dāng)前結(jié)構(gòu)的特征點(diǎn)，根據(jù)其與前面已重建三維點(diǎn)的對(duì)應(yīng)關(guān)系，采用RANSAC算法求出新增圖像的投影矩陣；

2）根據(jù)計(jì)算出的投影矩陣對(duì)新增圖像進(jìn)行重投影，去除誤差過(guò)大的特征點(diǎn)；

3）重建新增圖像與前一幅圖像的匹配點(diǎn)對(duì)中未被重建的特征點(diǎn)對(duì)；

4）對(duì)現(xiàn)有的結(jié)構(gòu)進(jìn)行更新；

5）通過(guò)光束法平差優(yōu)化，同時(shí)對(duì)重建結(jié)果的三維結(jié)構(gòu)和相機(jī)參數(shù)提供整體最優(yōu)解。

5.稠密3D重建

為了得到更加真實(shí)、準(zhǔn)確的目標(biāo)重建模型，本文在稀疏重建的基礎(chǔ)上，采用基于面片的PMVS（Patch-based Multi-view Stereo）準(zhǔn)稠密算法［8］，該算法利用區(qū)域增長(zhǎng)原理，輸出具有方向的小矩形面片密集集合，由此產(chǎn)生稠密的三維點(diǎn)云模型。PMVS算法主要包括匹配-擴(kuò)展-過(guò)濾三個(gè)步驟：

1）匹配。首先進(jìn)行初始特征匹配，本文利用前面稀疏重建生成的結(jié)構(gòu)作為潛在面片的初始值建立面片模型，通過(guò)光照一致性約束進(jìn)行優(yōu)化，得到一系列稀疏面片以及對(duì)應(yīng)的圖像區(qū)域，以此作為種子；

2）擴(kuò)展。利用相鄰面片具有相似的法向和位置的特性，擴(kuò)展初始匹配到已經(jīng)存在面片的鄰近空擋區(qū)域，并進(jìn)行優(yōu)化更新，得到比較稠密的面片序列；

3）過(guò)濾。利用視覺(jué)一致性約束構(gòu)建濾波器，去除位于觀察物體實(shí)際表面之前或之后的錯(cuò)誤匹配。

本文實(shí)驗(yàn)通過(guò)迭代將上述擴(kuò)展和過(guò)濾步重復(fù)執(zhí)行3次，并在擴(kuò)散過(guò)程中加入幾何空間約束，即同時(shí)考慮到四周相鄰面片對(duì)于擴(kuò)展面片的影響，沿著NCC增大的方向進(jìn)行匹配傳播。由于通過(guò)前面算法得到的初始種子匹配點(diǎn)對(duì)比較穩(wěn)定和可靠，并加入了上述對(duì)PMVS算法的改進(jìn)，使得用較少的圖像序列即可生成魯棒、精確的幾何估計(jì)，得到高稠密的三維點(diǎn)云模型，實(shí)現(xiàn)對(duì)目標(biāo)的三維重建。

6.實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)使用iPhone6（焦距長(zhǎng)度4.15mm）手機(jī)圍繞實(shí)驗(yàn)的人體頭部雕塑拍攝了20幅圖像，其中一幅如圖3（a）所示，圖像像素為2448 ×2448，通過(guò)自標(biāo)定實(shí)際算得相機(jī)的焦距為2669.368像素。采用C++ 與MATLAB混合編程對(duì)上述算法進(jìn)行實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果如下：圖3（b）為SFM重建出的3D稀疏點(diǎn)云，共計(jì)得到5174個(gè)稀疏點(diǎn)；圖3（c）為利用改進(jìn)的PMVS算法重建出的稠密3D點(diǎn)云，共計(jì)1409503個(gè)稠密點(diǎn)；圖3（d）為根據(jù)稠密3D點(diǎn)云重建的三角網(wǎng)格曲面模型。

圖3　頭部雕塑模型重建實(shí)例

7.結(jié)束語(yǔ)

本文設(shè)計(jì)并實(shí)現(xiàn)了一整套基于圖像集合的三維重建技術(shù)，通過(guò)對(duì)輸入的多幅圖像進(jìn)行特征點(diǎn)提取、匹配和優(yōu)化，根據(jù)計(jì)算出的基礎(chǔ)矩陣，迭代運(yùn)行從運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)的優(yōu)化算法，得到相機(jī)參數(shù)以及稀疏的空間點(diǎn)云信息，最后利用多視圖立體重建方法得到稠密的空間點(diǎn)云模型，完成了對(duì)目標(biāo)的三維重建。實(shí)驗(yàn)結(jié)果表明，本文采用的方法不需要特定的設(shè)備，無(wú)需人工干預(yù)即可自動(dòng)重建出正確的被觀測(cè)目標(biāo)的三維模型。后續(xù)還要對(duì)算法進(jìn)行相關(guān)改進(jìn)，例如增加圖像預(yù)處理、輸入更多先驗(yàn)信息、加入魯棒性策略等等，進(jìn)一步減低算法的計(jì)算開(kāi)銷(xiāo)，同時(shí)減輕誤差累積效應(yīng)，使重建結(jié)果更加完整逼真。

［1］馬頌德，張正友.計(jì)算機(jī)視覺(jué)——計(jì)算理論與算法基礎(chǔ)［M］.北京：科學(xué)出版社，1998.

［2］Maxime Lhuillier，Long Quan.A Quasi-Dense Approach to Surface Reconstruction from Uncalibrated Images.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005.

［3］Richard I.Hartley.In defense of the8-point Algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19（ 6）：580～593.

［4］Goesele M，Curless B，Seitz S M.Multi-View Stereo Revisited［C］. CVPR，New York，NY，2006.

［5］Lourakis M I A，Deriche R.Camera Self-Calibration Using the Kruppa Equations and the SVD of the Fundamental Matrix： The Case of Varying Intrinsic Parameters［R］.INRIA Tech Report，RR-3911，2000.

［6］Sonka M，Hlavac V，Boyle R.Image Processing，Analysis and Machine Vision（2nd Edition）［M］.New York：Thomson Press，2002：460-469.

［7］B.Triggs，P.McLauchlan，R.Hartley，et al.Bundle adjustment- a modern synthesis［J］.Vision algorithms： theory and practice，2000，1883： 298-372.

［8］Y.Furukawa，J.Ponce.Accurate， dense，and robust multiview stereopsis［J］.IEEE Transactions on PatternAnalysis and Machine Intelligen ce，2010，32（8）：1362-1376

林連慶（1985－），女，碩士研究生，現(xiàn)就讀于北京航空航天大學(xué)計(jì)算機(jī)學(xué)院，研究方向：計(jì)算機(jī)圖形學(xué)、圖像處理。