李清玉，趙　巖，王世剛

(吉林大學 通信工程學院，吉林 長春 130012)

?

結合Levenberg-Marquardt算法的垂直視差消減方法

李清玉，趙巖*，王世剛

(吉林大學 通信工程學院，吉林 長春 130012)

垂直視差的存在是影響立體視頻觀視舒適度的主要因素。為了在不影響水平視差的條件下實現(xiàn)對垂直視差的消減，本文引入Levenberg-Marquardt(L-M)非線性算法實現(xiàn)變換矩陣的精確求解。首先用抗縮放、旋轉(zhuǎn)及仿射變換的SIFT(Scale-invariant feature transform)特征匹配算法檢測出雙目圖像對的特征匹配點，然后根據(jù)匹配點的坐標位置運用L-M算法計算可消減垂直視差的變換矩陣，將變換矩陣作用于目標圖像，計算出該視圖每個像素點的新坐標位置。實驗結果表明：與利用線性算法求解二維射影變換矩陣的垂直視差消減方法相比，本文提出的求解方法在垂直視差消減上比該算法提高了約0.029 1～0.323 2個像素，對水平視差的影響比該算法降低了約0.118 7～1.139 1個像素。因此本文提出的方法對垂直視差的消減起到了優(yōu)化作用。

SIFT；射影變換；垂直視差消減；Levenberg-Marquardt算法

1　引　言

近年來，隨著3D技術的迅速發(fā)展，人們已經(jīng)不滿足于從二維圖像中獲得有限的信息，逐漸習慣于享受三維視覺帶來的沉浸感[1]。雙眼視差是立體顯示技術的理論基礎，水平視差在三維重建的過程中起著關鍵的作用，水平視差的變化使得人們對于畫面所呈現(xiàn)的事物有了立體的感知，然而垂直視差則會使人感覺疲勞[2]。理想條件下，在拍攝過程中所有攝相機都應在同一條水平線上，同時要求所有攝像機的光軸平行，并且所拍攝出圖像或視頻的極線嚴格要求水平。但實際上，由于支架的形變及攝像機內(nèi)部感光元件的不一致性等工藝問題往往會造成不同程度的垂直視差，這不僅影響了立體圖像的合成質(zhì)量，還會引起視覺疲勞。因此為了提高觀視者的舒適度，垂直視差消減方法的研究成為了越來越多科研人員的研究重點[3]。

國內(nèi)外對垂直視差消減技術的研究較少，并且這些方法中很多都是在處理過程中需要較多的圖像信息或者攝像機參數(shù)[4]。韓國Yun-Suk Kang和Cheon Lee等人提出了針對平行相機陣列的擬合公共基線解決辦法和針對弧形相機陣列的幾何補償校正算法。但是，這個方法需要多視點相機的標定參數(shù)，無法提供脫離相機參數(shù)的獨立應用。在無攝像機標定情況下，Loop[5]提出了基于基本矩陣的圖像校正方法，將校正過程分解為射影變換和仿射變換。該方法依賴于基本矩陣的精確求解，而由對應點計算基本矩陣還沒有較為穩(wěn)定的算法。上海大學劉利亮和安平[6]等人提出了一種基于公共點提取的多視圖像校正的方法，該方法有效降低了垂直視差，但是在校正垂直視差的過程中使得水平視差也發(fā)生了較大改變。

針對上述問題，本文提出了一種基于Levenberg-Marquardt(L-M)算法的垂直視差消減方法，該方法不需要攝像機的參數(shù)和過多的圖像信息，將由SIFT算法獲得的匹配點通過L-M算法計算出較高精度的變換矩陣，在進一步消減垂直視差的同時降低了對水平視差的影響，從而減緩觀看立體視頻時產(chǎn)生的視覺疲勞。

2　算法實現(xiàn)

首先對雙目圖像對使用SIFT算法進行特征點匹配，然后根據(jù)匹配點坐標應用L-M算法進行校正變換矩陣的計算，并通過校正變換矩陣計算校正后像素的新坐標，生成校正后的視圖。最后通過文獻[7]的后處理方法去除部分圖像中由校正變換引起的噪聲。本文提出方法的流程圖如圖1所示。

圖1　方法流程圖 Fig.1　Flowchart of the proposed method

2.1圖像的特征提取與匹配

本文采用SIFT[8]算法進行圖像的特征提取與匹配，該算法是一種局部描述算法，它可以在圖像中檢測出特征點。在尺度空間中，它通過極值檢測來查找潛在的興趣點，由于采用了高斯微分函數(shù)，它不會受諸如圖像的縮放、旋轉(zhuǎn)及仿射變換的影響[9]。SIFT算法是目前圖像特征匹配領域的研究重點，它的匹配結果十分準確，很少有偏差，而且效率很高。

2.2二維射影變換矩陣

射影變換就是射影平面上的可逆齊次線性變換，可以用3×3的矩陣來描述這個變換:

(1)

可以更簡略地記為x′=H·x。

本文在坐標點的表述上使用了齊次坐標，即變換是齊次的，因而同一個射影變換矩陣可以相差一個非零常數(shù)因子，所以射影變換矩陣的元素所構成的8個比值，就可以確定這個射影變換矩陣。

Richard Hartley[10]對二維射影變換矩陣做了簡要定義，如圖2所示。一條射線由圖像平面C上的一點x延伸，與世界平面Π相交于點xπ，這個點在圖像平面C′上的投射點為x′。由平面Π引起的點x與x′之間的映射關系即射影變換。世界平面Π與兩圖像平面C和C′關系分別如下：

(2)

(3)

由式(2)和式(3)可整理出兩個圖像平面的單應性關系:

(4)

圖2　射影變換定義 Fig.2　Definition of projective transformation

2.3垂直視差消減理論

假設左視圖和右視圖中的P(x,y)和Q(x′,y′)是一對特征匹配點，如果不存在垂直視差，那么Q的坐標值應為(x′,y)。同理，假設兩幅圖像使用SIFT算法檢測出n對匹配點對，這些匹配點對的坐標形式整理為矩陣形式[11]:

前者作為基準圖(左視圖)上匹配點的二維坐標矩陣形式，后者為待處理的右視圖上匹配點的二維坐標矩陣形式，可以得到消減垂直視差前、后的坐標矩陣應該分別為:

根據(jù)式(4)可以得到一系列的二維射影關系:

(5)

其中，二維射影變換矩陣為:

(6)

式中，采用齊次坐標方式，由式(5)通過L-M算法即可計算出二維射影變換矩陣 。

2.4L-M算法簡介及在矩陣計算中的應用

L-M算法又稱為阻尼最小二乘法，是目前應用較為廣泛的一種無條件約束優(yōu)化方法，該方法具有高斯-牛頓法的局部快速收斂特性，并克服了牛頓法不能有效處理奇異矩陣和非正定矩陣及對初始點要求比較苛刻的缺點；同時繼承了梯度下降法的全局搜索特性，精確度很高[12]。

下面對L-M算法進行簡要介紹：

設x(k)表示第k次迭代的權值和閾值所組成的向量，新的權值和閾值組成的向量x(k+1)可根據(jù)式(7)、(8)的規(guī)則求得：

(7)

(8)

(9)

式中，ei(x)為誤差。對于高斯-牛頓法的計算法則有:

(10)

J(x)為E(x)的Jacobian矩陣。L-M算法是一種改進的高斯-牛頓法，它的形式為:

(11)

式(11)中，比例系數(shù)μ>0為常數(shù),I為單位矩陣[13]。

當μ足夠大時，總可以保證[JT(x)J(x)+μI]-1是正定的，從而保證其可逆，算法的每次迭代都對μ進行自適應調(diào)整。當接近解時，μ逐漸減小，權值調(diào)整類似于高斯-牛頓法，利用類似于二階導數(shù)的信息，可以快速收斂到這個解；當遠離解時，μ逐漸增大，權重調(diào)整又類似于梯度下降法，可以進行全局搜索。所以L-M算法同時具備了牛頓法和梯度法的優(yōu)點，但計算J(x)要占用較多的內(nèi)存[14]。

本文給出了一種應用L-M算法來迭代優(yōu)化二維變換矩陣參數(shù)的方法。首先使用SIFT算法檢測出匹配特征點對，再由垂直視差消減原理求出經(jīng)過矩陣變化后的新坐標值，使用文獻[6]的線性算法計算出二維變換矩陣的初值，通過L-M算法的不斷迭代得到最后優(yōu)化的二維變換矩陣參數(shù)。根據(jù)二維射影變換原理，可以將變換后的坐標和原始坐標表示成式(12):

(12)

式(12)中，m2表示水平方向位移量，m5表示垂直方向位移量，m0、m1、m3、m4表示尺度和旋轉(zhuǎn)量，m6、m7表示水平和垂直方向的形變量。

由式(12)可得:

(13)

(14)

對于L-M算法，一個很關鍵的步驟就是設定誤差指標函數(shù)，本文的目標是求解變換矩陣的8個參數(shù)的最優(yōu)解，使得所有特征點的像點與其匹配點之間的距離之和最小。因此本文定義誤差指標函數(shù)為:

(15)

則由式(9)可知:

(16)

式中，i=1,…,N,N表示點的個數(shù)，顯然LM優(yōu)化的結果是E(M)越小越好。

J(M)為ei(M)的Jacobian矩陣:

(17)

對e1(M),…eN(M)分別求出8個偏導數(shù)：

對m0求偏導:

(18)

為了簡化下面公式的證明過程，將變量代換如下:

(19)

(20)

(21)

將式(19)、(20)、(21)定義的變量帶入到求解Jacobian矩陣的過程中，則有:

(22)

(23)

(24)

(25)

(26)

(27)

(28)

設M為列向量(m0,m1,…m7)T,則：

(29)

(30)

J(M)上面已經(jīng)求得，則JT(M)為J(M)的轉(zhuǎn)置也已知，所以ΔM可以求出。其中I為單位矩陣，μ>0為常數(shù)，是一個試探性參數(shù)，對于給定的μ，如果能使誤差指標函數(shù)E(M)降低，則μ降低，反之，μ增加。下面是具體的L-M優(yōu)化算法的步驟：

①給出誤差的允許值ε，常數(shù)β、μ以及初始化向量Mk,k=0。ε為兩個像素，β=10,μ=0.001；

②利用變換矩陣Mk計算目標圖像的新坐標，并計算誤差指標函數(shù)E(Mk)；

③計算誤差指標函數(shù)的Jacobian矩陣J(M);

④計算ΔM;

⑤若E(Mk)<ε，轉(zhuǎn)到⑦；否則計算Mk+1，并計算誤差指標函數(shù)E(Mk+1);

⑥若E(Mk+1)

⑦停止。

3　實驗結果與分析

本文使用MatlabR2012b進行方法的仿真實現(xiàn)。實驗采用的是分辨率均為1 024×768的立體視頻測試序列“breakdancer”和“ballet”。

為了檢驗垂直視差消減的效果以及文獻[6]和改進方法對水平視差的影響，利用檢測出匹配點對的垂直視差的平均值eval和水平視差的平均值hori作為校正前后的評價標準：

(31)

(32)

式(31)中，eval值越小，說明垂直視差平均值越小，則觀視者的立體觀視感受越好[15]；式(32)中hori值與未處理過的原圖像對的水平視差越接近[16]，說明在消減垂直視差的同時對水平視差的影響越小,則該垂直視差消減方法越好。

圖3是對breakdancer立體視頻序列第7幀的3、4視點進行垂直視差消減的實驗效果圖。其中(c)與(d)分別是利用文獻[6]和本文提出的改進方法處理后的結果圖。

表1是在不同參數(shù)設置情況下進行垂直視差消減前后的評價標準，eval是檢測出匹配點對的垂直視差的平均值，單位為像素，用它來評價垂直視差消減的效果；hori表示檢測出匹配點對的水平視差的平均值，單位同樣為像素。

圖3　breakdancer第7幀的3、4視點實驗效果圖 Fig.3　Experimental results of the 3 and 4 view points of the 7th frame of breakdancer image

參數(shù)原圖像對eval值文獻[6]方法eval值本文方法改進后eval值原圖像對hori值文獻[6]方法hori值本文方法改進后hori值0．252．68421．34181．30615．35534．07594．16520．402．60111．53301．51085．98915．45605．67910．502．68971．53191．50266．53026．14476．1882

在表1中，沒有進行垂直視差消減的原始圖像對在不同參數(shù)下的eval平均值是2.658 3個像素，hori平均值是5.958 2個像素。垂直視差消減后的eval平均值分別為1.468 9和1.439 8，使用本文方法改進后的結果比文獻[6]中使用二維單應性矩陣方法提高了0.029 1個像素，比原始圖像對提高了1.218 5個像素;垂直視差消減后的hori平均值分別為5.225 5和5.344 2，使用本文方法改進后的結果對水平視差的影響比文獻[6]中降低了0.118 7個像素。

圖4是對ballet立體視頻序列的第1幀的1、2視點進行垂直視差消減的實驗效果圖。在表2中，沒有進行垂直視差消減的原始圖像對在不同參數(shù)下的eval平均值是7.750 9個像素，hori平均值是32.278 0個像素。垂直視差消減后的eval平均值分別為1.910 7和1.587 5，使用本文方法改進后的結果比文獻[6]中使用二維單應性矩陣方法提高了0.323 2個像素，比原始圖像對提高了6.163 4個像素;垂直視差消減后的hori平均值分別為29.162 7和30.301 8，使用本文方法改進后的結果對水平視差的影響比文獻[6]中降低了1.139 1個像素。

圖4　ballet第1幀的1、2視點實驗效果圖 Fig.4　Experimental results of the 1 and 2 view points of the 1th frame of ballet image

ballet圖像序列的旋轉(zhuǎn)現(xiàn)象比較嚴重，使用本文方法改進后的結果比文獻[6]使用二維單應性矩陣方法提高的效果優(yōu)于對breakdancer這類旋轉(zhuǎn)程度不大的圖像序列。

雖然在圖3和圖4的(c)和(d)中看不出明顯的差別，但是從表1和表2中可以清晰地看出：通常情況下，選取不同參數(shù)時，在垂直視差消減方面，本文方法改進后的垂直視差比文獻[6]使用二維單應性矩陣方法有所降低；在對水平視差的影響方面，本文方法改進后的立體圖像對的水平視差相較于文獻[6]的方法更接近于原立體圖像對的水平視差，實現(xiàn)了在消減垂直視差的同時降低了對水平視差的影響。因此，使用本文改進方法比文獻[6]的方法在垂直視差消減和對水平視差的影響兩個方面均有所改善。而且圖像的旋轉(zhuǎn)程度越大，本文使用的方法對視差的調(diào)節(jié)越明顯。

表2　不同參數(shù)下ballet垂直視差消減前后性能評價(單位：像素)

4　結　論

本文通過在二維變換矩陣的計算中引入L-M算法，從而實現(xiàn)了變換矩陣的精確求解。在垂直視差消減方面，本文提出的算法與文獻[6]中使用二維射影變換的方法相比有了明顯的提高。同時，在對水平視差影響方面，本文提出的方法與文獻[6]相比更接近于原始圖像對的水平視差。改進后的方法在垂直視差消減上比該算法提高了0.029 1～0.323 2個像素，對水平視差的影響比該算法降低了0.118 7～1.139 1個像素。對于旋轉(zhuǎn)變換較大的圖像，本文提出的方法改進更為明顯。因此改進后的方法有利于在不影響水平視差的情況下對垂直視差的消減。

[1]杜歆,鄒瀧.視點合成中基于深度的空洞修復[J].浙江大學學報:工學版,2015,49(9):1616-1624.

DU X,ZOU L. Depth-based hole filling in view synthesis[J].J.ZhejiangUniversity(Engineering Science),2015,49(9):1616-1624.(in Chinese)

[2]王曉燕，王世剛，姜秀紅，等.亮度優(yōu)化立體視頻視覺舒適度評價[J].中國光學，2015,8(3):394-400.

WANG X Y,WANG SH G,JIANG X H,etal.. Evaluation of stereo video visual comfort based on luminance optimization[J].ChineseOptics,2015,8(3):394-400.(in Chinese)

[3]李實秋,雷建軍,周志遠,等.基于SIFT匹配的多視點立體圖像零視差調(diào)整[J].紅外與激光工程,2015(2):764-768.

LI SH Q,LEI J J,ZHOU ZH Y,etal.. Zero-disparity adjustment of multiview stereoscopic images based on SIFT matching[J].InfraredandLaserEngineering,2015(2):764-768.(in Chinese)

[4]邵楓,姜求平,蔣剛毅,等.基于顯著性分析的立體圖像視覺舒適度預測[J].光學 精密工程,2014,22(6):1631-1638.

SHAO F,JIANG Q P,JIANG G Y,etal.. Prediction of visual discomfort of stereoscopic images based on saliency analysis[J].Opt.PrecisionEng.,2014,22(6):1631-1638.(in Chinese)

[5]LOOP C,ZHANG Z. Computing rectifying homographies for stereo vision[C]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Fort Collins,Colorado,USA,1999:125-131.

[6]劉利亮，安平，王賀,等.基于公共點提取的多視圖像校正[J].信號處理，2011,6(27)：857-863.

LIU L L,AN P,WANG H,etal.. Multi-view images rectification based on common points extraction[J].SignalProcessing,2011,6(27):857-863.(in Chinese)

[7]ZHOU B L,ZHAO Y,WANG J Y,etal.. Improvement of visual fatigue based on vertical parallax elimination[C]. 2013 9th International Conference on Natural Computation,Shengyang,China,2013:1350-1354.

[8]DAVID G L. Distinctive image features from scale-invariant keypoints[J].InternationalJ.ComputerVision,2004(60):91-110.

[9]王燦進,孫濤,陳娟.局部不變特征匹配的并行加速技術研究[J].液晶與顯示,2014,29(2):266-274.

WANG C J,SUN T,CHEN J. Speeding up local invariant feature matching using parallel technology[J].ChineseJ.LiquidCrystalsandDisplays,2014,29(2):266-274.(in Chinese)

[10]HARTLEY R. Theory and practice of projective rectification[J].InternationalJ.ComputerVision,1999(35):115-127.

[11]程明明，王賀，安平,等.基于特征點匹配的多視圖像校正[J].液晶與顯示，2010,8(24):593-597.

CHENG M M,WANG H,AN P,etal.. Multi-view images rectification based on feature points matching[J].ChineseJ.LiquidCrystalsandDisplays,2010.8(24):593-597.(in Chinese)

[12]姚佳寶,田秋紅,陳本永.一種基于L-M算法的RANSAC圖像拼接算法[J].浙江理工大學學報：自然科學版,2015,33(4):552-557.

YAO J B,TIAN Q H,CHEN B Y. RANSAC image stitching algorithm based on L-M algorithm[J].J.ZhejiangSci-TechUniversity(Natural Sciences),2015,33(4):552-557.(in Chinese)

[13]項文強,張華,王姮,等.基于L-M算法的BP網(wǎng)絡在變壓器故障診斷中的應用[J].電力系統(tǒng)保護與控制,2011,39(8):100-103.

XIANG W Q,ZHANG H,WANG H,etal..Application of BP neural network with L-M algorithm in power transformaer fault diagnosis[J].PowerSystemProtectionandControl,2011,39(8):100-103.(in Chinese)

[14]SHAO X T,SHAN L,ZONG M L. Levenberg-Marquardt algorithm based nonlinear optimization of camera calibration for relative measurement[C]. 2015 34th Chinese Control Conference(CCC),IEEE,Hangzhou,China,2015:4868-4872.

[15]鄒瀧.3D視頻中的虛擬視點合成方法研究[D]. 浙江大學,2015.

ZOU L. Research on virtual view synthesis for 3D video[D]. Zhejiang University,2005.(in Chinese)

[16]高強,金杰,沈麗麗,等.使用EEG分析水平視差對3D圖像舒適性的影響[J].紅外與激光工程,2014(12):4140-4145.

GAO Q,JIN J,SHEN L L,etal.. Effect analysis of horizontal parallax on 3D images comfortableness using EEG[J].InfraredandLaserEngineering,2014(12):4140-4145.(in Chinese)

Method of vertical parallax reduction combined with Levenberg-Marquardt algorithm

LI Qing-yu, ZHAO Yan*, WANG Shi-gang

(College of Communication Engineering,Jilin University,Changchun 130012,China)*Correspondingauthor,E-mail:zhao_y@jlu.edu.cn

The existence of vertical parallax is the main factor of affecting the viewing comfort of stereo video. In order to reduce the vertical parallax without affecting the horizontal parallax, Levenberg-Marquardt(L-M) algorithm which is the nonlinear algorithm, is introduced in this paper to achieve the accuracy of the transformation matrix. Firstly, the SIFT algorithm, which is invariant to scaling, rotation and affine transformation, is used to detect the feature matching points from the binocular images. Then according to the coordinate position of matching points, the transformation matrix, which can reduce the vertical parallax, is calculated using Levenberg-Marquardt algorithm. Finally, the transformation matrix is applied to target image to calculate the new coordinate position of each pixel from the view images. The experimental results show that compared with the method that can reduce the vertical parallax using linear algorithm to calculate two-dimensional projective transformation, the proposed method using nonlinear algorithm improves the vertical parallax reduction from about 0.029 1 to 0.323 2 pixel and the effect of horizontal parallax is reduced from about 0.118 7 to 1.139 1 pixel. Therefore, the proposed method can optimize the vertical parallax reduction.

SIFT;projective transformation;vertical parallax reduction;Levenberg-Marquardt algorithm

2016-01-25；

2016-02-21

國家自然科學基金項目(No.61271315)

2095-1531(2016)03-0312-08

TN919.8

A

10.3788/CO.20160903.0312

李清玉(1989—)，女，遼寧葫蘆島人，碩士研究生，2012年于吉林大學獲得學士學位，主要從事圖像視頻方面的研究。E-mail:597181451@qq.com

趙巖(1971—)，女，吉林遼源人，教授，博士生導師，2003年于吉林大學獲得博士學位，主要從事圖像與視頻編碼和立體視頻處理方面的研究。E-mail:zhao_y@jlu.edu.cn

Supported by National Natural Science Foundation of China(No.61271315)