柯豐愷　陳幼平　謝經(jīng)明　張代林

華中科技大學(xué)，武漢，430074

?

基于凸松弛優(yōu)化算法的相機(jī)內(nèi)外參數(shù)標(biāo)定

柯豐愷陳幼平謝經(jīng)明張代林

華中科技大學(xué)，武漢，430074

摘要：相機(jī)內(nèi)外參數(shù)標(biāo)定的準(zhǔn)確性直接影響后期三維重建與真實(shí)被測(cè)物之間的相似性和三維點(diǎn)云的精度。針對(duì)該情況，提出了一種基于凸松弛多項(xiàng)式優(yōu)化方法來(lái)對(duì)相機(jī)進(jìn)行標(biāo)定。該方法通過(guò)對(duì)優(yōu)化問(wèn)題中的高階單項(xiàng)式進(jìn)行線性化處理并添加相應(yīng)的半正定矩陣約束，從而將原非凸優(yōu)化問(wèn)題轉(zhuǎn)換為可以快速并準(zhǔn)確求解的半正定規(guī)劃問(wèn)題，通過(guò)求解一次或多次的半正定規(guī)化問(wèn)題來(lái)逼近或求解出原優(yōu)化問(wèn)題的全局最優(yōu)解。實(shí)驗(yàn)數(shù)據(jù)證明了該方法的可行性與精確性。對(duì)于其他多視角幾何中的多項(xiàng)式優(yōu)化問(wèn)題，該方法同樣存在著良好的通用性與適應(yīng)性。

關(guān)鍵詞：最優(yōu)化；相機(jī)標(biāo)定；三維重建；半正定規(guī)劃；全局最優(yōu)解

0引言

計(jì)算機(jī)視覺(jué)是對(duì)人類和動(dòng)物的視覺(jué)的一種模擬，通過(guò)對(duì)采集到的圖像進(jìn)行處理和分析來(lái)獲取外界信息。麻省理工學(xué)院的Marr[1]將計(jì)算機(jī)視覺(jué)對(duì)外界的理解分為基元圖、2.5維圖以及三維模型三個(gè)階段。因此，三維模型的重建是計(jì)算機(jī)視覺(jué)的關(guān)鍵目標(biāo)。隨著圖像處理技術(shù)以及成像設(shè)備的發(fā)展，三維重建已經(jīng)被廣泛應(yīng)用在攝影測(cè)量、虛擬現(xiàn)實(shí)、數(shù)字娛樂(lè)等領(lǐng)域[2]。

相機(jī)標(biāo)定也稱相機(jī)定標(biāo)，是三維重建里必不可少的步驟。三維重建的效果與三維坐標(biāo)點(diǎn)的精度直接取決于相機(jī)內(nèi)外參數(shù)的標(biāo)定精度。相機(jī)標(biāo)定的內(nèi)外部參數(shù)包括焦距、畸變系數(shù)、中心點(diǎn)及與世界坐標(biāo)系之間的旋轉(zhuǎn)矩陣和平移向量等。由于在成像過(guò)程中和角點(diǎn)提取過(guò)程中不可避免地會(huì)加入噪聲，因此如何從這些干擾當(dāng)中正確地估計(jì)出相機(jī)的幾何參數(shù)與光學(xué)參數(shù)就是最優(yōu)化算法需要解決的問(wèn)題。Hartley等[3]認(rèn)為三維重建中最簡(jiǎn)單的雙視圖三角化問(wèn)題對(duì)應(yīng)于一個(gè)一元六次方程的求根問(wèn)題，最多情況下局部最優(yōu)解可達(dá)3個(gè)。當(dāng)為三視圖時(shí)，對(duì)應(yīng)于一個(gè)一元47次方程，故其局部最優(yōu)值可達(dá)24個(gè)[4]。因此三維重建過(guò)程中的最優(yōu)化問(wèn)題大部分具有非線性、非凸性且多模態(tài)性(即存在多個(gè)局部最優(yōu)解)等特點(diǎn)，這也是其大部分問(wèn)題始終沒(méi)有一個(gè)可靠、高效的解決方法的原因。

目前，對(duì)于多視角幾何下最優(yōu)化問(wèn)題的求解算法主要可以分為三大類。第一類是線性求解算法，這類算法主要以奇異值分解為主，該方法將所有的未知量羅列成n×1的列向量x，并從關(guān)于這些未知量的等式中提取出對(duì)應(yīng)未知量的系數(shù)寫成Ax=0的形式，對(duì)系數(shù)矩陣A進(jìn)行奇異值分解，即A=UDV，則矩陣V的最后一列即為所求系數(shù)[5]。還有一些改進(jìn)方案，如文獻(xiàn)[6-7]中的方法。這類方法求解速度快，但由于沒(méi)有考慮噪聲的性質(zhì)，因此沒(méi)有幾何上的意義。第二類是通用最優(yōu)解算法，這類方法通用性較強(qiáng)，并不針對(duì)某一類特定問(wèn)題，不論是線性問(wèn)題還是非線性問(wèn)題均可，但優(yōu)化的最終結(jié)果是局部最優(yōu)解還是全局最優(yōu)解取決于初始點(diǎn)的選擇。這類算法大體分為兩種，其中一種較為傳統(tǒng)，代表有梯度下降法、牛頓法等，這種通用算法的優(yōu)點(diǎn)是能較快地收斂到最優(yōu)解，但很大幾率收斂到局部最優(yōu)解。另外一種是智能算法，這種優(yōu)化算法的代表有李京[8]提出的遺傳粒子群優(yōu)化算法、李永明[9]提出的人工神經(jīng)網(wǎng)絡(luò)反向傳播算法以及混沌粒子群優(yōu)化算法等，其共有的特點(diǎn)是有策略性地、廣泛地將初始點(diǎn)或樣本分布于優(yōu)化問(wèn)題可行域內(nèi)并設(shè)定好優(yōu)化方向與迭代條件，通過(guò)大范圍、多方向地對(duì)最優(yōu)解進(jìn)行求解，因此迭代次數(shù)與計(jì)算量比梯度下降法等前一種通用最優(yōu)解算法多得多，計(jì)算時(shí)間更長(zhǎng)，這種算法由于有多個(gè)備選最優(yōu)值，故有更大概率獲得全局最優(yōu)解，但無(wú)法保證每次均收斂于全局最優(yōu)解。第三類是全局最優(yōu)化算法，這一類被解決的問(wèn)題很少，如針對(duì)L∞范數(shù)下的多視角幾何最優(yōu)化問(wèn)題[10]以及針對(duì)仿射相機(jī)下的L2范數(shù)下的多視角幾何最優(yōu)化問(wèn)題等[11]。總而言之，最普遍的基于高斯分布的噪聲模型下(也即L2范數(shù)下)的多視角幾何優(yōu)化問(wèn)題仍是一個(gè)開放性問(wèn)題。

基于上述問(wèn)題，本文提出了針對(duì)L2范數(shù)下的多視角幾何全局最優(yōu)化算法，并利用紅藍(lán)的棋盤格標(biāo)定板來(lái)改善標(biāo)定過(guò)程中對(duì)角點(diǎn)的提取精度。

1相機(jī)模型

如果把普通的二維投影相機(jī)成像看作是一個(gè)函數(shù)映射過(guò)程的話，那么這個(gè)過(guò)程是將空間三維點(diǎn)映射到相機(jī)成像面上的平面二維點(diǎn)的過(guò)程。它可以表示為

(1)

其中，s是標(biāo)量，x與X分別是成像面的二維點(diǎn)以及空間的三維點(diǎn)，K包含了相機(jī)的內(nèi)部參數(shù)，R和t分別是相機(jī)相對(duì)世界坐標(biāo)系的旋轉(zhuǎn)矩陣和平移向量。對(duì)相機(jī)參數(shù)的標(biāo)定就是對(duì)式(1)中的K、R及t的標(biāo)定。

通常來(lái)說(shuō)，相機(jī)標(biāo)定主要分為兩種：一種是自標(biāo)定，即根據(jù)實(shí)際生活或工作場(chǎng)景中的已知參照物來(lái)對(duì)相機(jī)進(jìn)行標(biāo)定，廣泛應(yīng)用于機(jī)器人領(lǐng)域中；另外一種是基于標(biāo)定物的標(biāo)定，這種標(biāo)定方法精度更高，主要采用精確制作的二維或三維的標(biāo)定物。標(biāo)定圖案有棋盤格的，有圓的及不規(guī)則圖案的，其中棋盤格標(biāo)定模板制作因工藝簡(jiǎn)單且其鞍點(diǎn)辨識(shí)度高而得到廣泛應(yīng)用。棋盤格標(biāo)定板的對(duì)比色有很多種，圖1a所示為傳統(tǒng)的黑白棋盤格標(biāo)定模板，由于其在強(qiáng)光下存在鞍點(diǎn)模糊的情況，故本文采用紅藍(lán)的棋盤格樣式來(lái)進(jìn)行標(biāo)定，如圖1b所示。

(a)黑白棋盤格標(biāo)定模板(b)紅藍(lán)棋盤格標(biāo)定模板圖1　標(biāo)定模板

2多項(xiàng)式優(yōu)化

為了獲取準(zhǔn)確的相機(jī)內(nèi)外部參數(shù)，需要某種標(biāo)準(zhǔn)來(lái)衡量標(biāo)定質(zhì)量的好壞，通常使用的就是以相機(jī)內(nèi)外部參數(shù)為未知量及空間三維點(diǎn)與平面二維點(diǎn)為已知量的某個(gè)累加函數(shù)。大量的經(jīng)驗(yàn)與實(shí)驗(yàn)數(shù)據(jù)表明，數(shù)字圖像處理中的噪聲分布大致符合高斯噪聲分布。因此，已知m個(gè)對(duì)應(yīng)點(diǎn)，則相機(jī)標(biāo)定的最優(yōu)化問(wèn)題可以表示為

(2)

由上述知，標(biāo)定的參數(shù)中含有旋轉(zhuǎn)矩陣R，它存在著RTR=I和det(R)=1的非線性約束，展開則為7個(gè)多項(xiàng)式約束條件：

(3)

(4)

這種利用向量表達(dá)旋轉(zhuǎn)矩陣的方式有效地減少了矩陣參數(shù)個(gè)數(shù)，但由于旋轉(zhuǎn)角θ與π-θ對(duì)應(yīng)于同一旋轉(zhuǎn)矩陣，故在向量v與旋轉(zhuǎn)矩陣R相互轉(zhuǎn)化時(shí)，存在映射模糊的問(wèn)題[12]。

為了避免上述問(wèn)題，本文直接采用R的矩陣表達(dá)形式，并利用Lasserre[13]在2001年提出的凸松弛優(yōu)化方法來(lái)計(jì)算相機(jī)的內(nèi)外部參數(shù)值。

對(duì)于一個(gè)標(biāo)量多項(xiàng)式優(yōu)化問(wèn)題，其通用的表達(dá)式為

(5)

其中，χ∈Rn,g0(χ)與gi(χ)均為標(biāo)量的多變量多項(xiàng)式。在Lasserre[13]提出的凸松弛方法中，多項(xiàng)式優(yōu)化問(wèn)題的可行域從高維空間變換成無(wú)窮維的概率函數(shù)空間，每一項(xiàng)不同的高階單項(xiàng)式被視為關(guān)于某一個(gè)非負(fù)概率函數(shù)的矩。在將原問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題的同時(shí)，根據(jù)概率函數(shù)空間的特性，添加一個(gè)或多個(gè)半正定矩陣約束。通過(guò)求解一系列呈遞進(jìn)分層式的半正定規(guī)劃問(wèn)題，逼近或計(jì)算出原多項(xiàng)式優(yōu)化問(wèn)題的全局最優(yōu)解。該凸優(yōu)化的方法可以歸納為以下步驟：

(3)求解前兩步中新構(gòu)成的半正定規(guī)劃問(wèn)題，若求得的解不滿足事先設(shè)定的收斂條件，則將d加1并重復(fù)上述步驟。

以Henrion等[14]在其論文中的多項(xiàng)式問(wèn)題為例:

(6)

分別將式(6)中不同的單項(xiàng)式替換為新的變量，例如將x2替換為y01，對(duì)應(yīng)的新的半正定規(guī)劃問(wèn)題為

(a)原多項(xiàng)式問(wèn)題可行域

(b)二階凸松弛可行域

(7)

由圖2b所示，經(jīng)過(guò)凸松弛后的半正定規(guī)劃問(wèn)題，很好地逼近了原多項(xiàng)式問(wèn)題。由于求解半正定規(guī)劃問(wèn)題的全局最優(yōu)解已非常成熟，利用現(xiàn)有的開源程序Sedumi可以對(duì)半正定規(guī)劃問(wèn)題式(7)進(jìn)行快速求解，所求得的全局最優(yōu)解也即原多項(xiàng)式問(wèn)題的全局最優(yōu)解[15]。

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

(a)紅藍(lán)標(biāo)定板效果圖(b)黑白標(biāo)定板效果圖圖3　效果圖

圖4　角點(diǎn)檢測(cè)示意圖

(8)

(9)

(a)牛頓優(yōu)化算法

(b)凸松弛優(yōu)化算法圖5　標(biāo)定誤差總體分布圖

由圖5與實(shí)驗(yàn)數(shù)據(jù)所知，經(jīng)凸松弛優(yōu)化處理后，角點(diǎn)的估計(jì)誤差明顯減小，且相機(jī)參數(shù)估計(jì)誤差更小。

為了定量分析經(jīng)過(guò)牛頓優(yōu)化算法和經(jīng)過(guò)凸松弛優(yōu)化算法后的參數(shù)精度與準(zhǔn)確度，本文采用兩種算法對(duì)雙目相機(jī)進(jìn)行標(biāo)定，通過(guò)雙目相機(jī)來(lái)進(jìn)行空間尺寸測(cè)量，依據(jù)測(cè)量出的數(shù)據(jù)精度來(lái)判斷各自標(biāo)定效果的好壞。

如圖6所示，本文對(duì)棋盤格標(biāo)定板的方塊尺寸以及游標(biāo)卡尺的尺寸進(jìn)行測(cè)量，圖中標(biāo)記點(diǎn)為測(cè)量目標(biāo)尺寸。經(jīng)過(guò)雙目視覺(jué)三角化求得角點(diǎn)空間坐標(biāo)后，計(jì)算的尺寸長(zhǎng)度如表1與表2所示。由表中數(shù)據(jù)可知，凸松弛在測(cè)量棋盤格方格和游標(biāo)卡尺刻度值時(shí)的平均誤差均遠(yuǎn)小于牛頓法所測(cè)量的結(jié)果，這證明了本文提出的凸松弛優(yōu)化方法在攝像機(jī)標(biāo)定過(guò)程中的有效性與正確性。

(a)棋盤格(b)游標(biāo)卡尺圖6　測(cè)量樣本圖

實(shí)驗(yàn)次數(shù)凸松弛法測(cè)量尺寸(mm)牛頓法測(cè)量尺寸(mm)真實(shí)尺寸(mm)凸松弛法平均誤差(%)牛頓法平均誤差(%)125.107523.1102225.366829.2489324.548226.0156425.172424.9117525.063826.0006624.738524.8262724.913327.0856825.068526.9726925.715724.71301025.553926.9841250.53.95

表2　游標(biāo)卡尺刻度測(cè)量數(shù)據(jù)

4結(jié)論

由于相機(jī)成像與角點(diǎn)檢測(cè)過(guò)程中不可避免地會(huì)引入噪聲干擾，因此相機(jī)標(biāo)定優(yōu)化問(wèn)題中存在著多個(gè)局部最優(yōu)解。本文提出了一種基于L2范數(shù)的全局最優(yōu)算法。該算法通過(guò)求解一系列的半正定規(guī)劃問(wèn)題來(lái)逼近與求得目標(biāo)函數(shù)的全局最優(yōu)值。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)優(yōu)化方法相比，該凸松弛的方法能快速有效地逼近全局最優(yōu)解，相機(jī)標(biāo)定參數(shù)的誤差得到大幅減小。

參考文獻(xiàn)：

[1]MarrD.Vision:aComputationalInvestigationintotheHumanRepresentationandProcessingofVisualInformation[M].NewYork:W.H.FreemanandCompany, 1982.

[2]HartleyR,ZissermanA.MultipleViewGeometryinComputerVision[M]. 2nded..England:CambridgeUniversityPress, 2004.

[3]HartleyR,SturmP.Triangulation[J].ComputerVisionandImageUnderstanding,1997, 68(2):164-157.

[4]SteweniusH,SchaffalitzkyF,NisterD.HowHardis3-viewTriangulationReally?[C]//ProceedingsofIEEEInternationalConferenceonComputerVision(ICCV).Beijing:2005:686-693.

[5]Bookstein F. Fitting Conic Sections to Scattered Data[J]. Computer Graphics and Image Processing, 1979, 9: 56-71.

[6]Chesi G, Garullli A, Vicino A, et al. Estimation the Fundamental Matrix Via Constrained Least Squares: a Convex Approach[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2002, 24(3): 397-401.

[7]Hartley R. Indefense of the Eight-point Algorithm[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence, 1997, 19(6): 580-593.

[8]李京. 基于遺傳粒子群優(yōu)化算法的遙感圖像分類方法研究與應(yīng)用[D]. 北京：首都師范大學(xué)，2013.

[9]李永明. 人工神經(jīng)網(wǎng)絡(luò)BP學(xué)習(xí)算法的研究及在人臉識(shí)別中的應(yīng)用[D]. 濟(jì)南：山東大學(xué)，2012.

[10]Kahl F, Hartley R. Multiple View Geometry under the Norm[J].Pattern Analysis and Machine Intelligence, 2008,30(9):1603-1617.

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

[12]Richard H, Jochen T, Dai Yuchao, et al. Rotation Averaging[J]. International Journal of Computer Vision, 2013,103(3):267-305.

[13]Lasserre J B. Global optimization with Polynomials and the Problem of Moments[J]. SIAM J. Optimization, 2001, 11(3): 796-817.

[14]Henrion D, Lasserre J B. Solving Nonconvex Optimization Problems-How Gloptipoly is Applied to Problems in Robust and Non-linear Control[J]. IEEE Control Systems Magazine,2004,24(3): 72-83.

[15]Sturm J F. Using SeDuMi 1.02: a Matlab Toolbox for Optimization Over Symmetric Cones[J]. Optimization Methods and Software, 1999,11(12):625-653.

[16]Waki H, Kim S, Kojima M, et al. Sparse POP: A Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems[J]. ACM Transactions on Mathmatical Software, 2008，35(2)：1-15.

(編輯袁興玲)

Internal and External Parameter Calibrations of a Camera Based on Convex Relaxation Optimization Algorithm

Ke FengkaiChen YoupingXie JingmingZhang Dailin

Huazhong University of Science and Technology,Wuhan,430074

Abstract:The similarity between the real object and the reconstructed model and the precision of the 3D point cloud were determined by the accuracy of the internal and external parameters of the camera. A convex relaxation algorithm was proposed to deal with the problems of camera calibration. Each monomial in the polynomial optimization problem was replaced by its corresponding linear item and some semi-definite matrix inequalities were added. The global optima could be approximated or achieved by solving one or more semi-definite programming problems. The experimental results confirm the feasibility and the accuracy of this algorithm. Moreover, the algorithm can be applied to the problems of camera calibration and some other polynomial optimization problems in multiple view geometry.

Key words:optimization; camera calibration; 3D reconstruction; semi-definite programming; global optimum

作者簡(jiǎn)介：柯豐愷，男，1989年生。華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院博士研究生。主要研究方向?yàn)樽顑?yōu)化算法及三維重建。陳幼平，男，1957年生。華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院教授、博士研究生導(dǎo)師。謝經(jīng)明，男，1966年生。華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院副教授。張代林，男，華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院講師。

中圖分類號(hào)：TP751.1

DOI：10.3969/j.issn.1004-132X.2016.05.011

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

收稿日期：2015-05-13