一種基于兩步運(yùn)動(dòng)估計(jì)的系列圖像匹配算法

摘 要:提出了一種基于兩步運(yùn)動(dòng)估計(jì)的系列圖像匹配算法。首先運(yùn)用簡(jiǎn)化仿射運(yùn)動(dòng)估計(jì)對(duì)相鄰兩幅圖像進(jìn)行粗略匹配，然后運(yùn)用改進(jìn)的光流運(yùn)動(dòng)估計(jì)得到比較精確的匹配圖像;此外，在保證簡(jiǎn)化仿射變換參數(shù)正確的同時(shí)，使用了更加簡(jiǎn)單直接的解法，大大降低了計(jì)算的復(fù)雜性。該算法彌補(bǔ)了傳統(tǒng)圖像匹配方法的不足，而且使圖像匹配殘差明顯減小。實(shí)驗(yàn)表明，對(duì)存在大位移運(yùn)動(dòng)、復(fù)雜形變的圖像，該算法更有效。

關(guān)鍵詞:圖像匹配; 運(yùn)動(dòng)估計(jì); 簡(jiǎn)化仿射變換; 光流法; 匹配殘差

中圖分類號(hào):TP391文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2009)09-3563-03

doi:10.3969/j.issn.1001-3695.2009.09.105

Image matching algorithm based on two-step motion estimation

LI Wen-yu， HU Xue-gang

(College of Computer Science Technology， Chongqing University of Posts Telecommunications， Chongqing 400065， China)

Abstract:This paper proposed a two-step motion estimation algorithm to match a series of images. First， applied simplified affine motion estimation to matching two neighbouring images sketchily. Second， applied improved optic flow motion estimation to obtaining more accurate matching image. Besides， with the use of simple and direct solution， the method could not only assure the accuracy of simplified affine transform parameters， but also greatly reduce computational complexity. The algorithm compensated the disadvantage of classical image matching methods， and obviously reduced image matching error. Experimentresults show that the algorithm is more effective for images with large-scale motion and complex deformation.

Key words:image matching; motion estimation; simplified affine transform; optic flow method; matching error

0 引言

系列圖像匹配就是將相鄰幀圖像進(jìn)行比較，以確定圖像間目標(biāo)或點(diǎn)的對(duì)應(yīng)關(guān)系或相對(duì)變形。這一問(wèn)題是圖像處理和計(jì)算機(jī)視覺(jué)領(lǐng)域研究的熱點(diǎn)，被廣泛應(yīng)用于數(shù)字視頻圖像的壓縮編碼、電子穩(wěn)像技術(shù)、醫(yī)學(xué)圖像分析等。總結(jié)有關(guān)系列圖像匹配的方法[1，2]，主要分為基于形狀匹配的方法和基于運(yùn)動(dòng)預(yù)測(cè)的方法。其中基于形狀匹配的方法就是處理由各種變換引起的形狀變化，如仿射變換法、多項(xiàng)式變換法等;基于運(yùn)動(dòng)預(yù)測(cè)的方法是利用物體的運(yùn)動(dòng)特性，預(yù)測(cè)目標(biāo)在下一幀中的位置和形變，主要包括光流法和塊匹配法等。

基于形狀匹配的仿射變換方法能夠準(zhǔn)確地把發(fā)生了較大平移、旋轉(zhuǎn)、縮放、對(duì)稱、錯(cuò)切變換及其復(fù)合變換的圖像進(jìn)行匹配，被越來(lái)越多的學(xué)者研究和應(yīng)用，其參數(shù)越多意味著匹配目標(biāo)越準(zhǔn)確，還可以根據(jù)不同的需要靈活地選用不同的參數(shù)模型[3];但是當(dāng)圖像或目標(biāo)有遮擋、局部扭曲、彈性變形等復(fù)雜形變時(shí)，常常有很大的匹配誤差。基于運(yùn)動(dòng)預(yù)測(cè)的光流法[4，5]最大優(yōu)點(diǎn)就是可以求得光流場(chǎng)，表示出相鄰圖像中一幅圖像的每個(gè)像素點(diǎn)在另一幅圖像中的具體映射位置，從而克服了基于形狀匹配方法的不足[6，7];但是對(duì)像素灰度不變區(qū)域運(yùn)動(dòng)估計(jì)的精度存在問(wèn)題，大位移的運(yùn)動(dòng)目標(biāo)匹配甚至失敗等。于是，有很多研究人員把這兩種方法進(jìn)行融合，得到了許多改進(jìn)的模型，但是有的方法計(jì)算的最終結(jié)果不是回歸到了基于形狀匹配的全局估計(jì)參數(shù)[8]，就是變成基于運(yùn)動(dòng)估計(jì)的矢量場(chǎng)[9]。

到目前為止，真正把這兩種方法結(jié)合起來(lái)同時(shí)處理系列圖像的精確匹配問(wèn)題的研究還較少。為此，本文以光流法(optic flow)為基礎(chǔ)，結(jié)合簡(jiǎn)化的仿射變換模型(simplified affine transform)，提出一種新的系列圖像匹配算法，稱為SAT_OF算法。

1 基于兩步運(yùn)動(dòng)估計(jì)的匹配算法

1.1 仿射運(yùn)動(dòng)估計(jì)

假如取視頻系列圖像中相鄰兩幀分別為I(xiàn)1和I2，為了減少全局運(yùn)動(dòng)估計(jì)的計(jì)算量、提高估計(jì)速度，考慮到系列圖像一般大小是相同的，即I1、I2每一對(duì)應(yīng)的維數(shù)值相等，所以這里認(rèn)為攝像機(jī)先只有沿著平行于目標(biāo)的方向移動(dòng)和轉(zhuǎn)動(dòng)，從而運(yùn)用簡(jiǎn)化的仿射變換模型:

x′y′= cos θsin θ-sin θcos θxy+ΔxΔy(1)

由上式可知，圖像只有旋轉(zhuǎn)和平移。為了便于求解，令

a1=cos θ， a2=sin θ， b1=Δx， b2=Δy(2)

于是式(1)變?yōu)榱硪环N方程組形式

x′=a1x+a2y+b1y′=-a2x+a1y+b2(3)

將式(3)中第一個(gè)方程兩邊同時(shí)減去x，第二個(gè)方程兩邊同時(shí)減去y，并用速度近似代替位移，有下式成立:

u≈(a1-1)x+a2y+b1v≈-a2x+(a1-1)y+b2(4)

這樣可以利用光流法計(jì)算簡(jiǎn)化仿射變換參數(shù)，避免了文獻(xiàn)[3]中使用迭代的最小二乘方法計(jì)算復(fù)雜和計(jì)算量大的問(wèn)題。現(xiàn)在推導(dǎo)簡(jiǎn)單直接的計(jì)算過(guò)程。

根據(jù)Horn等人[4]提出的時(shí)空2-D模型，同一個(gè)像素點(diǎn)在t時(shí)刻(x，y)位置的強(qiáng)度f(wàn)(x，y，t)與在(t+dt)時(shí)刻(x+dx，y+dy)位置的強(qiáng)度f(wàn)(x+dx，y+dy，t+dt)應(yīng)該相等，即

f(x，y，t)=f(x+dx，y+dy，t+dt)(5)

根據(jù)圖像運(yùn)動(dòng)場(chǎng)基本平滑變化，函數(shù)f(x，y，t)中變量x、y、t具有連續(xù)性，可將式(5)右邊在(x，y，t)點(diǎn)按Taylor公式展開(kāi)，計(jì)算后得

(f/x)(dx/dt)+(f/y)(dy/dt)+(f/t)=0(6)

其中:令Ex=f/x，Ey=f/y，Et=f/t，u=dx/dt，v=dy/dt。以上方程變?yōu)榱硪环N形式:

Exu+Eyv+Et=0(7)

式(7)就是基本的光流約束方程，它反映了圖像時(shí)間梯度和空間梯度之間的時(shí)—空微分關(guān)系，表示圖像強(qiáng)度對(duì)時(shí)間變化率等于強(qiáng)度的空間變化率與運(yùn)動(dòng)速度的乘積。

把式(4)代入(7)并進(jìn)行整理得超定方程:

(a1-1)(xEx+yEy)+a2(yEx-xEy)+b1Ex+b2Ey=-Et(8)

為了計(jì)算參數(shù)，令a′1=a1-1，把式(8)寫成向量形式:

(xEx+yEy yEx-xEy Ex Ey)a′1a2b1b2=-Et(9)

上式中若令A(yù)=(xEx+yEy yEx-xEy Ex Ey)，X=(a′1 a2 b1 b2)T，B=-Et，同時(shí)將上式等號(hào)兩邊左乘以AT得矩陣方程:

ATAX=ATB(10)

如果ATA非奇異，就可以得式(10)的惟一解，否則在實(shí)際應(yīng)用中設(shè)此方程的解為零。由矩陣元素分析知，只要圖像不是完全平坦光滑，總是可以求出所得的解:

X=(ATA)-1ATB(11)

將式(11)求得的a′1、a2、b1、b2代入式(2)，計(jì)算出進(jìn)行粗略估計(jì)的全局運(yùn)動(dòng)參數(shù)θ、Δx、Δy，一直迭代到圖像金字塔的最高層。至此可以對(duì)圖像作簡(jiǎn)化的仿射變換，得到粗略匹配圖像I(xiàn)′1。

1.2 光流運(yùn)動(dòng)估計(jì)

為了計(jì)算上一步所估計(jì)圖像I(xiàn)′1與模板圖像I2的局部運(yùn)動(dòng)和各種形變的估計(jì)參數(shù)，且解決光流計(jì)算的不適定問(wèn)題，楊勇等人[10]將二維標(biāo)號(hào)場(chǎng)引入光流運(yùn)動(dòng)估計(jì)中，使光流估計(jì)算法得到極大優(yōu)化。

ε(u，v)=[λ(Exu+Eyv+Et)2+c2]dxdy(12)

其中:c2=(u/x)2+(u/y)2+(v/x)2+(v+y)2為附加約束平滑條件;λ=λμ0且λ0為大于1的常數(shù);μ是與標(biāo)號(hào)場(chǎng)有關(guān)的量。先計(jì)算相鄰幀k與k+1的幀間差:

FDk，k+1(i，j)=Ik+1(i，j)-Ik(i，j)(13)

由于噪聲的存在，未變化區(qū)域FD不一定為0，選最優(yōu)化閾值T[11]得標(biāo)號(hào)場(chǎng):

zk，k+1(i，j)=1 |FDk，k+1(i，j)|>T0 |FDk，k+1(i，j)|≤T(14)

于是μ的值為

μ(i，j)=1zk，k+1(i，j)=1-1 zk，k+1(i，j)=0(15)

式(12)實(shí)際上是泛函的極值問(wèn)題，可用變分法求得兩個(gè)歐拉方程， 得到如下松弛迭代求解公式:

u(n+1)=u(n)-λEx(Exu(n)+Eyv(n)+Et)/[1+λ(E2x+E2y)](16)

v(n+1)=v(n)-λEy(Exu(n)+Eyv(n)+Et)/[1+λ(E2x+E2y)](17)

對(duì)全部x、y值，當(dāng)達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)或結(jié)果滿足事先給定的估計(jì)容差，迭代計(jì)算結(jié)束，最終得出光流場(chǎng)，可以用來(lái)進(jìn)行圖像I′1和I2匹配，得到最終結(jié)果匹配圖像I′2，基本解決了局部運(yùn)動(dòng)和彈性形變部分沒(méi)有得到匹配的問(wèn)題。

從這兩步的求解過(guò)程可以看出，不需要對(duì)圖像進(jìn)行分割和目標(biāo)提取，使匹配的過(guò)程更加簡(jiǎn)單，大大提高了算法效率。

1.3 SAT_OF算法模型

本文的SAT_OF算法模型如圖1所示。

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

為了說(shuō)明SAT_OF匹配算法的效果，本文基于MATLAB 7.1平臺(tái)下，選用兩組圖像進(jìn)行匹配實(shí)驗(yàn):向右平移和旋轉(zhuǎn)的hand圖像(圖2);圖像和樹(shù)木都發(fā)生不同運(yùn)動(dòng)的landscape圖像(圖3)。

比較的模型算法，在橫向比較上選用了已有的Horn光流圖像匹配算法，在縱向比較分析中選用仿射匹配算法。本文取金字塔層數(shù)為3，迭代次數(shù)n=20，加權(quán)系數(shù)λ=25。在圖2、3的實(shí)驗(yàn)中，以原圖像第二幀圖像(圖(b))作為模板圖，根據(jù)運(yùn)動(dòng)估計(jì)復(fù)原后的圖像，可以看出本文算法計(jì)算的圖像與模板圖最接近。根據(jù)運(yùn)動(dòng)估計(jì)復(fù)原后的圖像與模板圖的匹配殘差圖，本文算法的效果更加明顯，比由仿射變換和Horn光流法復(fù)原的圖像匹配精度更高，且較大殘差的分布更為隨機(jī)，這對(duì)于由圖像運(yùn)動(dòng)的位移信息進(jìn)行圖像恢復(fù)有利。從圖2(c)與(b)對(duì)比可知，因圖像中手只有平移和小角度的旋轉(zhuǎn)，通過(guò)仿射變換進(jìn)行運(yùn)動(dòng)估計(jì)已經(jīng)比較準(zhǔn)確，光流法再修正就比較少，這符合本文簡(jiǎn)化的仿射變換模型的理論分析。

客觀結(jié)果評(píng)價(jià)參數(shù)本文選用平均灰度差(mean)，參數(shù)的計(jì)算公式為

mean=∑Mi=1∑Mj=1|I1(i，j)-I2(i，j)|/(M×N)(17)

其中:以I(xiàn)2(i，j)為模板圖像;I1(i，j)在計(jì)算時(shí)分別被原始第一幀、仿射變換、Horn光流法、本文算法經(jīng)運(yùn)動(dòng)估計(jì)后復(fù)原的圖像所代替;M、N分別是圖像的長(zhǎng)和寬。兩組實(shí)驗(yàn)的平均灰度差如表1所示。

由表 1可知，從縱向比較可以看出，本文算法與仿射變換得到的平均灰度差相比，有明顯減少，這與SAT_OF算法的理論分析是相一致的。由仿射變換先對(duì)全局運(yùn)動(dòng)作概略的估計(jì)，再由光流法對(duì)局部的運(yùn)動(dòng)和形變進(jìn)行估計(jì)而得到的匹配精度有很大提高。從橫向來(lái)看，雖然Horn光流法能夠完成精度比較高的配準(zhǔn)，但是經(jīng)本文兩步運(yùn)動(dòng)估計(jì)之后，平均灰度差較Horn光流法有明顯減少，從而說(shuō)明用本文算法計(jì)算的運(yùn)動(dòng)估計(jì)參數(shù)來(lái)匹配復(fù)原圖像效果更好。

3 結(jié)束語(yǔ)

本文給出了用兩步運(yùn)動(dòng)估計(jì)參數(shù)來(lái)對(duì)視頻系列圖像作復(fù)原匹配的算法:a)推導(dǎo)計(jì)算簡(jiǎn)化仿射變換參數(shù)，得到圖像的全局粗略估計(jì);b)利用光流松弛迭代求解公式計(jì)算粗略估計(jì)與模板圖像的光流場(chǎng)，進(jìn)一步得到比較精確匹配的圖像。在推導(dǎo)仿射變換參數(shù)的過(guò)程中，本文用了有別于以前最小二乘方法的方程解法，大大降低了計(jì)算的復(fù)雜性。實(shí)驗(yàn)表明:本文的兩步運(yùn)動(dòng)估計(jì)更準(zhǔn)確，得到的平均灰度差明顯減小。但是，本文算法因建立在光流法運(yùn)動(dòng)估計(jì)基礎(chǔ)之上，存在平滑約束條件和多次迭代，導(dǎo)致運(yùn)動(dòng)估計(jì)結(jié)果圖像有一定的模糊，這對(duì)匹配算法是十分不利的。所以提高匹配后圖像的質(zhì)量是本文下一步所要研究的工作。

參考文獻(xiàn):

[1]黃新生，楊慶偉，王亦平，等. 圖像系列運(yùn)動(dòng)估計(jì)綜述[J]. 計(jì)算機(jī)仿真， 2008，25(5): 180-184.

[2]梁英宏， 王知衍， 曹曉葉，等. 視頻圖像理解的一般性框架研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2008，25(7): 2203-2207.

[3]王嘉，王海峰，劉青山，等. 基于三參數(shù)模型的快速全局運(yùn)動(dòng)估計(jì)[J]. 計(jì)算機(jī)學(xué)報(bào)， 2006，29(6): 920-927.

[4]HORN B K P， SCHUNCK B G. Determining optical flow[J]. Artificial Intelligence， 1981，17: 185-203.

[5]ANDRES B， JOACHIM W， CHRISTOPH S， et al. Lucas/Kanade meets Horn/Schunck: combining local and global optic flow methods [J]. International Journal of Computer Vision， 2005，61(3): 211-231.

[6]CHAMORRO-MARTINEZ J， FEMANDEZ-VALDIVIA J. A new approach to motion pattern recognition and its application to optical flow estimation[J]. IEEE Trans on Systems， Man， and Cybernetics-part C: Applications and Reviews， 2007，37(1): 39-51.

[7]王新衛(wèi)，周利莉，肖永隆. 一種基于自適應(yīng)梯度的運(yùn)動(dòng)估計(jì)算法[J]. 計(jì)算機(jī)工程， 2007，33(14):198-200.

[8]XIONG Jing-yi， LUO Yu-pin， TANG Guang-rong. An improved optical flow method for image registration with large-scale movements[J]. Acta Automatica Sinica， 2008，34(7): 760-764.

[9]楊新，郭豐俊，PHILIPS W，等. 基于 HUBER 函數(shù)的序列圖像位移場(chǎng)估計(jì)算法[J]. 高技術(shù)通訊， 2001 (1):38-42.

[10]楊勇，王楊，吳樂(lè)南.基于標(biāo)號(hào)場(chǎng)的光流法二維運(yùn)動(dòng)估計(jì)[J].電子與信息學(xué)報(bào)，2001， 23(12):1321-1325.

[11]RUSENFELD A， AVINASH C K. Digital picture processing[M]. New York: Academic Press， 1976: 263-270.