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

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

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

?

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

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

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

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

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

0引言

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

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

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

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

1相機模型

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

(1)

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

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

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

2多項式優(yōu)化

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

(2)

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

(3)

(4)

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

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

對于一個標(biāo)量多項式優(yōu)化問題，其通用的表達式為

(5)

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

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

以Henrion等[14]在其論文中的多項式問題為例:

(6)

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

(a)原多項式問題可行域

(b)二階凸松弛可行域

(7)

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

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

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

圖4　角點檢測示意圖

(8)

(9)

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

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

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

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

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

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

實驗次數(shù)凸松弛法測量尺寸(mm)牛頓法測量尺寸(mm)真實尺寸(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)卡尺刻度測量數(shù)據(jù)

4結(jié)論

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

參考文獻：

[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í)算法的研究及在人臉識別中的應(yīng)用[D]. 濟南：山東大學(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

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

中圖分類號：TP751.1

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

基金項目：國家自然科學(xué)基金資助項目(51174151)

收稿日期：2015-05-13