魏迎梅，康　來(lái)

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

2.國(guó)防科技大學(xué) 信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙　410073)

?

多視圖三角化中特征點(diǎn)噪聲尺度的自適應(yīng)估算*

魏迎梅1，康來(lái)2

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

2.國(guó)防科技大學(xué) 信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙410073)

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

關(guān)鍵詞：多視圖三角化；特征點(diǎn)定位；高斯噪聲；核密度估計(jì)

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

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

1圖像特征點(diǎn)定位噪聲及對(duì)極傳遞

1.1　特征點(diǎn)定位噪聲及其尺度

(1)

(2)

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

1.2　對(duì)極傳遞幾何原理

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

(3)

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

(4)

(5)

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

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

2自適應(yīng)特征點(diǎn)定位噪聲尺度估算

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

2.1　對(duì)極傳遞不確定性描述模型

為便于推導(dǎo)，首先定義如下映射：

(6)

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

(7)

映射ψ可以表達(dá)為如下對(duì)極傳遞映射φ：

(8)

其中，

(9)

與

(10)

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

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

(11)

(12)

(13)

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

2.2　噪聲尺度估計(jì)

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

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

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

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

假設(shè)三維場(chǎng)景點(diǎn)在M個(gè)視圖中可見(jiàn)，記第i(1≤i≤M)個(gè)視圖中相應(yīng)的圖像觀察點(diǎn)為u″i。令：

(14)

(15)

(16)

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

(17)

(18)

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

(19)

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

3實(shí)驗(yàn)結(jié)果與分析

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

3.1　模擬數(shù)據(jù)實(shí)驗(yàn)

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

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

(20)

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

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

(21)

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

(22)

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

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

3.2　真實(shí)圖像實(shí)驗(yàn)

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

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

圖7　真實(shí)圖像三角化結(jié)果Fig.7　Results of triangulation on real images

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

表1　真實(shí)圖像實(shí)驗(yàn)結(jié)果對(duì)比

4結(jié)論

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

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

參考文獻(xiàn)(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

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61402487)

收稿日期：*2015-01-28

doi:10.11887/j.cn.201506022