多視圖三角化中特征點噪聲尺度的自適應估算*

魏迎梅，康　來

(1.國防科技大學 信息系統(tǒng)與管理學院， 湖南 長沙　410073；

2.國防科技大學 信息系統(tǒng)工程重點實驗室， 湖南 長沙　410073)

?

多視圖三角化中特征點噪聲尺度的自適應估算*

魏迎梅1，康來2

(1.國防科技大學 信息系統(tǒng)與管理學院， 湖南 長沙410073；

2.國防科技大學 信息系統(tǒng)工程重點實驗室， 湖南 長沙410073)

摘要：魯棒性多視圖三角化方法通常借助重投影誤差經驗閾值來剔除圖像對應中的錯誤匹配，該經驗閾值的選取直接影響三維重構場景點的數(shù)量和精度。在分析圖像特征點定位噪聲及對極傳遞幾何原理的基礎上，建立對極傳遞過程不確定性的傳遞模型，提出一種基于核密度估計的最優(yōu)噪聲尺度估算方法，并將該噪聲尺度作為多視圖三角化中錯誤匹配篩選的依據(jù)。實驗結果表明，該方法可以獲得準確的噪聲尺度估計，從而有效提升多視圖三角化方法的三維重構質量。

關鍵詞：多視圖三角化；特征點定位；高斯噪聲；核密度估計

基于圖像的三維重構是計算機視覺的重要研究內容，近年來備受學術界關注而且取得了眾多研究成果[1]。作為基于圖像三維重構的核心步驟，多視圖三角化(multi-view triangulation)的目標是在各相機內、外參數(shù)均已知的情況下估計場景的三維結構[2]。理想情況下，三維場景點坐標可以通過計算其在不同視圖中視線的交匯點得到。然而，由于特征點定位噪聲和圖像對應匹配錯誤在實際圖像中總是存在，因此多視圖三角化問題不能采用上述簡單的方法求解，而是需要借助魯棒的外點(outlier)剔除方法將錯誤匹配刪除后利用優(yōu)化技術對三維場景重構結果進行求精[3-8]。

在多視圖三維重構中，為消除圖像對應中錯誤匹配對三角化的不利影響，目前有兩種比較流行的策略：一類是迭代剔除方法[3]；另一類是整體剔除方法[4]。從本質上來說，上述多視圖三角化算法均依據(jù)重投影誤差經驗閾值來識別圖像對應中的錯誤匹配，即若重構的三維場景點在某一視圖中的投影與相應的圖像特征點的歐式距離大于某一閾值時，則認為該圖像特征點為錯誤匹配對應[1-2]。選取較小的重投影誤差閾值可以有效剔除匹配錯誤對應，也可以有效降低重投影誤差，但同時也刪除了大量匹配正確的圖像對應，從而導致正確重構的三維場景點數(shù)量下降，同時也會降低多視圖三角化結果的精度。因此，為了獲得更加客觀的三維重構結果，需要準確估計圖像特征點定位噪聲尺度，在此基礎上確定重投影誤差閾值作為錯誤匹配剔除的依據(jù)。

1圖像特征點定位噪聲及對極傳遞

1.1　特征點定位噪聲及其尺度

(1)

(2)

圖1　高斯噪聲下圖像特征點位置分布概率密度Fig.1　Probability density of the distribution of image feature point locations under Gaussian noise

1.2　對極傳遞幾何原理

在沒有噪聲的情況下，假設三維場景點U在三個中心位于O1,O2以及O3的視圖中的圖像點分別為u，u′以及u″(如圖2所示)，即：

(3)

根據(jù)對極幾何原理[2]，如下關系成立：

(4)

(5)

其中，符號“?”表示相差尺度因子的相等。在多視圖幾何中，上述關系稱為對極傳遞(epipolar transfer)[2]。

圖2　三視圖對極傳遞示意圖Fig.2　Illustration of three-view epipolar transfer

2自適應特征點定位噪聲尺度估算

當變量的觀察樣本數(shù)量較多時，噪聲尺度的估計可以采用統(tǒng)計方法[9]。在基于圖像的三維重構中，由于所有圖像均只成像一次，因此無法使用統(tǒng)計方法。本節(jié)推導三視圖對極傳遞不確定性傳遞模型并提出基于核密度估計的魯棒性圖像特征點定位噪聲尺度估計方法。

2.1　對極傳遞不確定性描述模型

為便于推導，首先定義如下映射：

(6)

其中，[·]3表示取向量的第3維元素的操作。令

(7)

映射ψ可以表達為如下對極傳遞映射φ：

(8)

其中，

(9)

與

(10)

定理1[2]：記v為m中均值為μv、協(xié)方差矩陣為Σv的隨機向量，φ:mn為v附近可微分的映射，則φ(v)∈n是均值為φ(μv)、協(xié)方差矩陣為的隨機變量(Jφ為映射φ的雅可比矩陣在點μv的取值)。

根據(jù)定理1，u″的均值為：

(11)

(12)

(13)

其中，Jφ為對極傳遞映射φ(如式(8)所示)的雅可比矩陣在點μu″處的取值。

2.2　噪聲尺度估計

本節(jié)研究如何利用圖像觀察值u″，均值μu″以及相應的協(xié)方差矩陣Σu″估計特征點定位噪聲尺度。為了便于推導，首先介紹如下兩個定理。

定理2[2]：記v為m中均值為μv、協(xié)方差矩陣為Σv的隨機向量，則服從分布。其中，為協(xié)方差矩陣Σv的偽逆矩陣，r為矩陣Σv的秩。

定理3[10]：設v為一概率密度函數(shù)fv的隨機變量，g(·)為單調、可逆且可微分的函數(shù)。則z=g(v)的概率密度函數(shù)fz為：

上述原理稱為變量變換原理。

假設三維場景點在M個視圖中可見，記第i(1≤i≤M)個視圖中相應的圖像觀察點為u″i。令：

(14)

(15)

(16)

注意，{ti}僅依賴于圖像觀察，因此可以從圖像特征點對應數(shù)據(jù)中計算獲得。由上述關系以及定理3可知，{ti}的概率密度函數(shù)為：

(17)

(18)

因此，噪聲尺度估算的關鍵是定位{ti}分布的密度函數(shù)的極大值。對于集合{ti|i=1,…,nσ}(nσ為圖像特征點對應三元組數(shù)量)，使用核密度估計(Kernel Density Estimation, KDE)方法[11]來擬合其分布。在任意位置t，核密度計算如下：

(19)

圖3　噪聲尺度估算示意圖Fig.3　Illustration of noise scale calculation

3實驗結果與分析

為驗證算法的有效性，利用合成數(shù)據(jù)和真實圖像兩種數(shù)據(jù)對其進行定性和定量測試。該算法的實現(xiàn)采用C++ 語言，所有實驗均在Windows XP 操作系統(tǒng)下進行，實驗用PC的CPU為Intel Core i7-3770 3.4GHz 處理器，內存為2GB。多視圖三角化所需特征點對應采用尺度不變特征轉換(Scale Invariant Feature Transform,SIFT)圖像特征檢測及匹配方法獲取[13]，錯誤匹配的剔除采用文獻[4]中的方法。上述方法是現(xiàn)有方法中性能最佳的方法之一，不僅能有效刪除外點而且可同時獲得三維結構的初始估計[5]。在此基礎上利用集束優(yōu)化(bundle adjustment)[14]對重建結果進一步迭代求精。為了定量地分析實驗結果，采用模擬數(shù)據(jù)和具有特殊場景結構的真實圖像作為實驗數(shù)據(jù)。

3.1　模擬數(shù)據(jù)實驗

利用模擬數(shù)據(jù)對對極傳遞不確定性及噪聲尺度估計的精度進行測試。為獲取模擬數(shù)據(jù)，在多個位置上生成虛擬相機同時觀察斯坦福大學的bunny點云模型。通過調節(jié)相機內、外參數(shù)，各相機觀察到的圖像被限定在1000×1000像素以內。通過改變高斯噪聲的標準差，可生成不同噪聲尺度的圖像數(shù)據(jù)供測試。

首先，將該協(xié)方差計算方法與基于大數(shù)定理[9]的統(tǒng)計方法進行對比。對于統(tǒng)計方法，均值Ed[u″]的計算如下：

(20)

其中，Nd為樣本數(shù)量(取Nd=1500)。協(xié)方差Covd[u″]為：

Covd[u″]=Ed[(u″j-Ed[u″])(u″j-Ed[u″])j]

(21)

為了直觀地比較協(xié)方差估計的優(yōu)劣，本實驗采用k-超橢球(k-hyper-ellipsoid)對協(xié)方差進行可視化[9]。對于任意標量k(0≤k≤1)，u″位于k-超橢球

(22)

圖4　對極傳遞協(xié)方差可視化(σ=2.0像素)Fig.4　Visualization of the covariance of epipolar transfer (σ=2.0 pixel)

圖5　噪聲尺度估計精度箱圖(外點比例為30%)Fig.5　Boxplot of the accuracy of noise scale estimation (with 30% outliers)

3.2　真實圖像實驗

對于真實圖像，由于無法獲取圖像特征點定位噪聲尺度的真實值，因此無法對噪聲尺度估計的精度進行評估。因此，本實驗借助場景中的約束來從側面測試本文方法在真實圖像三角化中的性能。圖6為本實驗采用的真實圖像樣張，后續(xù)定量分析重點考察真實場景中兩個便攜式電腦屏幕對應的平面區(qū)域。

為了考察錯誤匹配剔除過程中重投影誤差閾值選取對三角化結果的影響，本實驗利用不同噪聲尺度進行處理。三角化重構的最終平面通過最小二乘法擬合三維場景點獲得。平面場景三維點重構三維誤差定義為重構三維點到擬合平面的最小距離。由于僅考察度量重建，并不關注場景的真實尺寸，因此考察距離的絕對大小并無意義。為了便于比較三維重建精度，將平面區(qū)域對應的三維點進行縮放，以確保其包圍盒最大邊長為100“單位”。同時，本實驗考察所有三維點的重投影誤差，且上述兩個誤差度量均計算所有場景點的均方根誤差，部分三角化結果如圖7所示。其中，圖7(a)展示的三角化結果使用的噪聲尺度為0.2像素，成功重建的三維點數(shù)量約為2400。圖7(b)和圖7(c)為使用本文自適應噪聲尺度的三角化結果的兩個視圖，成功重建的三維點數(shù)量約為10 500。

圖7　真實圖像三角化結果Fig.7　Results of triangulation on real images

更多的定量對比實驗結果如表1所示。實驗結果表明，魯棒性多視圖三角化方法采用較小的噪聲尺度可以獲取較小的重投影誤差，但三維重構的精度卻并未隨之提升。此外，如果采用過小的噪聲尺度，會極大地減少成功重建的三維點數(shù)量。從表1也可以看出，通過準確的噪聲尺度估計，可以有效提升三角化結果的三維精度，而且不會導致成功重建的場景點數(shù)量明顯減少。

表1　真實圖像實驗結果對比

4結論

假設圖像特征點定位噪聲滿足高斯噪聲分布，在此假設條件下根據(jù)對極傳遞幾何原理，推導了三視圖對極傳遞過程中特征點定位不確定性的傳遞模型，提出一種基于核密度估計的特征點定位噪聲尺度估計算法，并將其應用于魯棒性多視圖三角化中錯誤匹配的識別和剔除。利用仿真數(shù)據(jù)和真實圖像進行實驗驗證，從定性和定量的實驗結果可以看出，該方法估計的噪聲尺度具有較高的精度，將自適應噪聲尺度作為外點剔除依據(jù)有助于提高魯棒性多視圖三角化結果的質量。

在下一步工作中將繼續(xù)探索在相機內、外參數(shù)未知的情況下，特征點定位噪聲的估計問題，并研究噪聲尺度估計對相機標定及其他多視圖幾何估計問題(如：相機姿態(tài)估計、多視圖立體)求解精度的影響。

參考文獻(References)

[1]Szeliski R. Computer vision: algorithms and applications[M]. London,UK: Springer, 2010.

[2]Hartley R, Zisserman A. Multiple view geometry in computer vision[M]. 2nd ed.New York,USA: Cambridge University Press, 2004.

[3]Sim K, Hartley R. Removing outliers using theLnorm[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), New York, IEEE, 2006: 485-494.

[4]Olsson C, Eriksson A, Hartley R. Outlier removal using duality[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), New York, IEEE, 2010: 1450-1457.

[5]Bourmaud G, Megret R. Robust large scale monocular visual SLAM[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), New York, IEEE, 2015: 1638-1647.

[6]Li H D. A practical algorithm forLtriangulation with outliers[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), New York, IEEE, 2007: 1-8.

[7]Seo Y, Lee H, Lee S W. Outlier removal by convex optimization forLapproaches[C] //Proceedings of Pacific Rim Symposium on Image and Video Technology (PSIVT), Berlin, Springer, 2009: 203-214.

[8]Ke Q F, Kanade T. Quasiconvex optimization for robust geometric reconstruction[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(10): 1834-1847.

[9]Csurka G, Zeller C, Zhang Z Y, et al. Characterizing the uncertainty of the fundamental matrix[J]. Computer Vision and Image Understanding, 1997, 68 (1): 18-36.

[10]Lavine M. Introduction to statistical thought[M]. Tallahassee, USA: Orange Grove Texts Plus, 2009.

[11]Silverman B W. Density estimation: for statistics and data analysis[M].London,UK: Chapman and Hall, 1986.

[12]Wang H Z, Suter D. Robust adaptive-scale parametric model estimation for computer vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(11): 1459-1474.

[13]Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[14]Triggs B, Mclauchlan P F, Hartley R I, et al. Bundle adjustment—a modern synthesis[C]//Proceedings of ICCV’99: Proceedings of the International Workshop on Vision Algorithms: Theory and Practice,London, Springer Verlag, 2000: 298-375.

http://journal.nudt.edu.cn

Adaptive estimation of noise scale in feature localization for multi-view triangulation

WEIYingmei1,KANGLai2

(1. College of Information System and Management, National University of Defense Technology, Changsha 410073, China；

2. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China)

Abstract：Robust multi-view triangulation algorithms usually rely on an empirical reprojection error threshold to identify and remove the outliers. The selection of such threshold is critical to both the quantity of successfully reconstructed scene point and its accuracy. Based on the analysis of the noise in feature point localization and the geometry of epipolar transfer, the uncertainty propagation model in epipolar transfer was derived. A novel noise scale estimation approach based on kernel density estimation was proposed and the estimated noise scale was further incorporated into robust state-of-the-art multi-view triangulation algorithm. Experimental results demonstrate that the proposed method is able to obtain accurate estimation of noise scale and to improve the 3D reconstruction quality of multi-view triangulation algorithm significantly.

Key words：image-based 3D reconstruction; feature point localization; Gaussian noise; kernel density estimation

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-2486(2015)06-116-05

作者簡介：魏迎梅(1972—)，女，甘肅蘭州人，教授，博士，碩士生導師，E-mail：weiyingmei126@126.com

基金項目：國家自然科學基金資助項目(61402487)

收稿日期：*2015-01-28

doi:10.11887/j.cn.201506022