劉玉峰，李震

(1.浙江廣播電視集團(tuán)，杭州 310005；2 .浙江大學(xué)，杭州310027 )

1 引言

電子穩(wěn)像是指對(duì)數(shù)字化后的圖像進(jìn)行各種圖像匹配算法來(lái)估計(jì)出圖像序列間的位移，并應(yīng)用相應(yīng)的補(bǔ)償技術(shù)來(lái)實(shí)現(xiàn)圖像序列的穩(wěn)定，是數(shù)碼攝像機(jī)中消除視頻抖動(dòng)的一種重要方法。電子穩(wěn)像中的一個(gè)重要算法就是運(yùn)動(dòng)估計(jì)，運(yùn)動(dòng)估計(jì)不僅可以大幅度提升圖像序列觀測(cè)的穩(wěn)定性，改善圖像壓縮效果，而且可以獲得更為優(yōu)化的成像質(zhì)量，是數(shù)字圖像處理的重要研究方向之一。常見(jiàn)的運(yùn)動(dòng)估計(jì)算法主要有塊匹配法[1]、灰度投影法[2]、光流法[3，4]和特征追蹤法[5，6]。相比于其他算法，塊匹配法由于所需計(jì)算量小而被廣泛應(yīng)用于各種場(chǎng)景下的運(yùn)動(dòng)估計(jì)中。

塊匹配法通過(guò)將一個(gè)圖形分成多個(gè)矩形像素塊，并假設(shè)在所需進(jìn)行匹配的像素塊內(nèi)所有的像素點(diǎn)的運(yùn)動(dòng)矢量相同，對(duì)每一個(gè)像素塊進(jìn)行匹配后只會(huì)得到一個(gè)相應(yīng)的運(yùn)動(dòng)矢量，因此塊匹配法相比于基于像素和特征點(diǎn)的算法大大減少了計(jì)算量。最初的塊匹配法為全搜索法，全搜索法將像素塊可能運(yùn)動(dòng)到的位置均與參考幀相應(yīng)位置的像素塊進(jìn)行比較，導(dǎo)致計(jì)算量較大，計(jì)算速度慢，之后許多加速搜索模板被提出。Koga等人提出了三步法[7]，將搜索過(guò)程簡(jiǎn)化為三步，每一步的搜索步長(zhǎng)為上一步的一半，每次搜索均采用9個(gè)候選點(diǎn)進(jìn)行匹配，但是其缺陷是第一步的匹配錯(cuò)誤會(huì)導(dǎo)致后面兩步無(wú)法得到正確的匹配結(jié)果。由Zhu和Ma提出的鉆石搜索法[8]則先后采用由9個(gè)檢測(cè)點(diǎn)組成的大鉆石搜索和5個(gè)檢測(cè)點(diǎn)組成小鉆石搜索兩個(gè)搜索模板，該方法具有快速的搜索過(guò)程和較強(qiáng)的糾錯(cuò)能力，在1999年被MPEG-4國(guó)際標(biāo)準(zhǔn)采納且歸于了驗(yàn)證模型。

為了進(jìn)一步提高塊匹配法的計(jì)算效率，位平面匹配法被提出。其中Koga等人最早在1998年提出的灰度圖位平面匹配[9]，利用包含圖像信息的第四位平面代替灰度圖進(jìn)行匹配，簡(jiǎn)化了匹配運(yùn)算的復(fù)雜度，但是相鄰的像素值之間的二進(jìn)制表示的多位數(shù)據(jù)的不同，給匹配帶來(lái)很大的誤差，相比于灰度圖匹配精度較低。為了改善位平面的匹配精度，多種位平面匹配法被提出。在1999年，Koga提出了改進(jìn)算法，先將灰度圖用格雷碼進(jìn)行編碼，并采用三步法進(jìn)行搜索，提升了搜索匹配的速度[10]。文獻(xiàn)[11]則進(jìn)一步提出了基于格雷碼編碼的位平面和鉆石搜索模板的全局運(yùn)動(dòng)估計(jì)算法，進(jìn)一步改善了匹配過(guò)程的糾錯(cuò)能力。截?cái)喔窭状aTGC(Truncated Graycode)位平面匹配是一種利用多個(gè)經(jīng)過(guò)格雷碼編碼后的位平面進(jìn)行匹配的算法，文獻(xiàn)[12]比較測(cè)試證明，經(jīng)過(guò)截?cái)喔窭状a編碼的位平面匹配相比于未經(jīng)過(guò)格雷編碼的截?cái)辔黄矫婢哂懈玫钠ヅ湫Ч?BT(One-bit Transform)位平面匹配法[13]的位平面生成不同于[9]中的位平面，是將灰度圖像通過(guò)變換后設(shè)定閾值轉(zhuǎn)換為1個(gè)bit的數(shù)據(jù)。而Erturk在文獻(xiàn)[14]中提出了2BT(Two-bit Transform)位平面匹配的概念，即使用兩個(gè)位平面來(lái)提升匹配性能?；?BT算法，文獻(xiàn)[15]則引入了Constraint Mask的概念，提出了C1BT(Constrained One-bit Transform)算法，其匹配性能高于2BT算法和其他的1BT算法。文獻(xiàn)[16]利用C1BT算法與2BT算法的優(yōu)勢(shì)，提出了C2BT(Constrained Two-bit Transform)算法，其匹配效果分別比基于2BT的位平面匹配和基于C1BT的位平面匹配高出0.35dB和0.28dB。截?cái)喔窭状a，C1BT和C2BT等算法改進(jìn)了灰度圖位平面匹配法的匹配效果，同時(shí)也增加了匹配過(guò)程的復(fù)雜度和計(jì)算量。改進(jìn)位平面匹配法的匹配效果且盡量減少計(jì)算量成為運(yùn)動(dòng)估計(jì)中的難題。

本文首先研究了基于格雷碼的位平面匹配法的原理，進(jìn)一步分析了基于格雷碼的不同位平面全搜索匹配效果，基于分析結(jié)果，并利用鉆石搜索法的快速搜索特性，提出了位平面混合快速匹配法，在鉆石搜索模板的第一步中使用了基于格雷碼的第4位平面進(jìn)行大鉆石搜索模板匹配，在第二步中使用了基于格雷碼的第5位平面進(jìn)行大鉆石搜索模板匹配，在第三步中使用灰度圖進(jìn)行小鉆石搜索模板匹配。最后將本文提出的位平面混合快速匹配法與C1BT，C2BT，截?cái)喔窭状a第五、第六位平面及基于格雷碼的第5位平面分別進(jìn)行鉆石模板搜索，通過(guò)仿真比較各自的匹配效果和計(jì)算量，驗(yàn)證了本文算法的優(yōu)越性。

2 基于格雷碼的位平面匹配

2.1 提取位平面

對(duì)于灰度圖像中任意像素的8 bit大小的灰度值，可由式(1)進(jìn)行二進(jìn)制分解[9]。

f(x，y)=a727+a626+…+a121+a020

(1)

其中f(x，y)表示二維灰度圖像中位置為(x，y)點(diǎn)的灰度值，ak的值為0或1，第k層位平面包含了整幅圖像每個(gè)點(diǎn)像素值的ak值。

圖1是用Lena圖生成的各個(gè)位平面的圖像信息。從圖1可以觀察到，處于較高層的位平面圖像包含了視覺(jué)有效信息，較低層的位平面圖像僅僅包含一些圖像的細(xì)節(jié)信息及噪聲，不能提供有效的視覺(jué)參考。使用不同位平面進(jìn)行匹配得到的結(jié)果不同，選取合適的位平面作為匹配平面對(duì)整個(gè)匹配過(guò)程的精度有著非常大的影響。直接利用灰度圖位平面進(jìn)行匹配的主要問(wèn)題在于相鄰的灰度值之間的二進(jìn)制顯示會(huì)有多位數(shù)據(jù)的不同，給匹配帶來(lái)很大的誤差。例如灰度值127的二進(jìn)制顯示為01111111，灰度值128的二進(jìn)制顯示為10000000，雖然127與128在數(shù)值上僅相差1，但是兩者的二進(jìn)制顯示有8位不同。

針對(duì)灰度圖位平面的問(wèn)題，使用格雷碼對(duì)灰度圖進(jìn)行編碼，得到基于格雷碼的位平面[10]，格雷碼編碼公式如(2)所示：

位平面0 位平面1 位平面2 位平面3

位平面4 位平面5 位平面6 位平面7圖1 Lena圖分解得到各個(gè)位平面的圖像信息

(2)

其中g(shù)k即為基于格雷碼的第k層位平面數(shù)據(jù)。利用相鄰灰度圖位平面數(shù)據(jù)依次異或可得基于格雷碼的位平面。

2.2 塊匹配法

塊匹配法首先從基于格雷碼的位平面中獲取匹配塊數(shù)據(jù)，然后在全搜索范圍內(nèi)利用位平面數(shù)據(jù)進(jìn)行匹配，以最小化非匹配點(diǎn)數(shù)NNMP (Number of Non-matched Points)為準(zhǔn)則獲取最佳匹配位置，如圖2所示。

匹配使用的像素塊大小的選擇對(duì)匹配精度有著非常大的影響，匹配塊過(guò)小不足以提供足夠的有效信息來(lái)實(shí)現(xiàn)匹配，匹配塊過(guò)大可能會(huì)導(dǎo)致像素塊內(nèi)存在不一致的運(yùn)動(dòng)和計(jì)算量過(guò)大等問(wèn)題。在測(cè)試圖像大小為480*640時(shí)，塊匹配法在使用匹配塊面積小于32*32時(shí)不能估計(jì)到有效的運(yùn)動(dòng)矢量，在匹配塊面積為64*64時(shí)，得到的運(yùn)動(dòng)矢量的匹配效果較好；而在匹配塊面積為128*128時(shí)，匹配效果更好，但是其計(jì)算量非常大[17]。

將匹配圖像塊的位數(shù)據(jù)進(jìn)行異或操作并求得和值即可獲取NNMP，計(jì)算公式如式(3)所示。

(3)

最后將各個(gè)圖像塊匹配所獲得的局部運(yùn)動(dòng)矢量與前一幀的全局運(yùn)動(dòng)矢量做中值濾波，除去局部運(yùn)動(dòng)矢量的尖峰脈沖。

3 位平面匹配效果分析

為了分析基于格雷碼的位平面匹配法的性能，如圖3所示，我們對(duì)手持拍攝設(shè)備拍攝的7組視頻進(jìn)行測(cè)試，對(duì)比分析了使用基于格雷碼的不同位平面全搜索得到的匹配結(jié)果與使用灰度圖進(jìn)行全搜索得到的匹配結(jié)果。測(cè)試視頻的圖像大小為1280*720像素，每組視頻序列均選取11幀圖像共10對(duì)進(jìn)行匹配，每幅圖像選取相同間隔的16個(gè)大小為64*64像素的匹配塊，檢測(cè)塊在圖中的位置如圖2所示，每個(gè)位平面在進(jìn)行匹配以后可以得到的運(yùn)動(dòng)矢量總數(shù)為160個(gè)。由于低位平面只包含了一些圖像的微小細(xì)節(jié)及噪聲，不能包含有效的視覺(jué)信息和匹配信息，匹配效果很差，因而主要考慮第3-7層位平面的匹配效果。我們以灰度圖全搜索匹配的結(jié)果作為參考，對(duì)于相同位置的匹配塊，如果基于格雷碼的不同位平面全搜索匹配結(jié)果與灰度圖全搜索匹配的結(jié)果不一致，即判定為相應(yīng)位置的匹配塊產(chǎn)生了錯(cuò)誤匹配。

圖2 匹配塊在圖中的位置

對(duì)每一幀采用第3至7位平面進(jìn)行匹配的結(jié)果與對(duì)相同圖像進(jìn)行灰度圖全搜索匹配得到的結(jié)果進(jìn)行對(duì)比，錯(cuò)誤匹配的運(yùn)動(dòng)矢量數(shù)據(jù)如表1所示，可以觀察到基于格雷碼的第5位平面匹配效果最優(yōu)，第4位平面匹配效果其次，誤匹配率都低于15%，其他位平面匹配的誤匹配率均大于15%。結(jié)合Celebi[12]和Koga[10]的仿真結(jié)果，可以得出基于格雷碼的第4位平面與第5位平面在不同場(chǎng)景中相對(duì)其他位平面具有較好的匹配效果。

此外，在仿真中我們發(fā)現(xiàn)基于格雷碼的位平面匹配結(jié)果即使存在錯(cuò)誤匹配的發(fā)生，但大多數(shù)的發(fā)生錯(cuò)誤匹配的運(yùn)動(dòng)矢量與灰度圖匹配得到的運(yùn)動(dòng)矢量誤差并不大。表2中統(tǒng)計(jì)了將錯(cuò)誤匹配運(yùn)動(dòng)矢量與灰度圖匹配得到的運(yùn)動(dòng)矢量相差小于一個(gè)像素誤差的數(shù)據(jù)。可以看到每個(gè)位平面的錯(cuò)誤匹配運(yùn)動(dòng)矢量與正確運(yùn)動(dòng)矢量距離小于1概率大于50%，而位平面5錯(cuò)誤匹配運(yùn)動(dòng)矢量與正確運(yùn)動(dòng)矢量距離小于1概率高達(dá)87.31%，這也表明大部分錯(cuò)誤匹配的運(yùn)動(dòng)矢量都與正確匹配的運(yùn)動(dòng)矢量非常接近。

由上述分析，我們可以總結(jié)出使用單個(gè)位平面進(jìn)行匹配，即使是匹配效果最優(yōu)的兩個(gè)位平面，其錯(cuò)誤匹配的概率仍在11.96%與13.57%，會(huì)給運(yùn)動(dòng)估計(jì)的最終結(jié)果帶來(lái)很大的影響，需要我們進(jìn)一步增強(qiáng)其匹配精度，而可以通過(guò)改善搜索的最后幾步的精度來(lái)減小匹配錯(cuò)誤。

圖3 隨機(jī)拍攝的7個(gè)場(chǎng)景圖像

位平面7位平面6位平面5位平面4位平面3視頻序列1301951325視頻序列26465283318視頻序列35838383749視頻序列44733172237視頻序列55940252635視頻序列6241010721視頻序列72319111425總誤匹配率27.23%20.00%11.96%13.57%18.75%

表2 錯(cuò)誤匹配運(yùn)動(dòng)矢量與正確運(yùn)動(dòng)矢量距離小于等于1的概率

4 鉆石搜索法

鉆石搜索法[8]采用了兩個(gè)搜索模板：大鉆石搜索模板和小鉆石搜索模板。如圖4中所示大鉆石搜索模板由9個(gè)檢測(cè)點(diǎn)組成，小鉆石搜索模板由5個(gè)檢測(cè)點(diǎn)組成。

(a)大鉆石搜索模板

(b)小鉆石搜索模板圖4 鉆石搜索模板

鉆石搜索的操作方法為：首先采用大鉆石搜索模板進(jìn)行搜索，當(dāng)匹配點(diǎn)為大鉆石搜索模板中心時(shí)，下一步搜索過(guò)程切換到小搜索模板，當(dāng)匹配點(diǎn)不是大鉆石搜索模板的中心點(diǎn)時(shí)，以匹配點(diǎn)為中心點(diǎn)，繼續(xù)用大鉆石搜索模板進(jìn)行匹配；之后使用小鉆石搜索模板進(jìn)行匹配，誤差最小點(diǎn)即為運(yùn)動(dòng)估計(jì)中心點(diǎn)，其與參考圖像的中心點(diǎn)的差即為運(yùn)動(dòng)矢量。

具體操作過(guò)程如圖5所示。第一次搜索使用大鉆石搜索模板，候選點(diǎn)為紅色圓形位置，搜索結(jié)果得到位移為(-2，0)的位置為第一次搜索的最佳匹配點(diǎn)；第二次搜索以(-2，0)點(diǎn)為中心，仍舊采用大搜索模板進(jìn)行匹配，候選點(diǎn)顯示為綠色菱形，位移為(-3，1)的位置為第二次搜索的最佳匹配點(diǎn)；第三次搜索以(-3，1)點(diǎn)為中心，仍舊采用大搜索模板進(jìn)行匹配，搜索點(diǎn)為藍(lán)色方形，位移為(-4，2)的位置為第三次搜索的最佳匹配點(diǎn)；第四次搜索以(-4，2)點(diǎn)為中心，仍舊采用大搜索模板進(jìn)行匹配，搜索點(diǎn)為黑色三角形，位移為(-4，2)的位置為第四次搜索的最佳匹配點(diǎn)，也是其大鉆石搜索模板的中心，下次搜索將采用小鉆石搜索模板進(jìn)行匹配；第五次搜索以(-4，2)為中心，采用小鉆石搜索模板進(jìn)行匹配，候選點(diǎn)為白色五角形，獲得的最佳匹配點(diǎn)即為全局的最佳匹配點(diǎn)。

圖5 鉆石搜索過(guò)程

使用鉆石搜索法，在幾次大鉆石搜索模板的匹配過(guò)程中如果獲得的匹配點(diǎn)為大鉆石搜索模板的中心點(diǎn)，就可以快速地進(jìn)入小鉆石搜索模板，并最終獲得最佳匹配點(diǎn)。這樣的操作可以避免全搜索過(guò)程大多數(shù)點(diǎn)的匹配計(jì)算，大大減少了計(jì)算量。

此外鉆石搜索法具有較強(qiáng)的糾錯(cuò)能力，在大鉆石搜索模板搜索時(shí)，必須滿(mǎn)足匹配中心位于大鉆石搜索模板的中心時(shí)才能進(jìn)入小鉆石搜索模板的搜索，在一定程度上增加了鉆石搜索法的匹配精度。

5 位平面混合快速算法

全搜索法雖然是一種匹配精度較高的算法，但是其計(jì)算量過(guò)于龐大，導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)。鉆石搜索法由于具有快速搜索的特性被廣泛應(yīng)用，此外相比于其他搜索方法具有較高的匹配精度。將鉆石搜索模板應(yīng)用于基于格雷碼的位平面搜索，雖然可以提高基于格雷碼的位平面搜索的搜索速度，但是不能提升匹配精度，其匹配精度受限于最佳匹配位平面的匹配效果。由位平面分析可知采用位平面匹配時(shí)，大多數(shù)錯(cuò)誤匹配的運(yùn)動(dòng)矢量與正確的運(yùn)動(dòng)矢量之間誤差不大，只差一到兩個(gè)像素。使用基于格雷碼的位平面進(jìn)行鉆石搜索模板匹配，絕大多數(shù)搜索過(guò)程中都能找到正確的小鉆石搜索模板中心，但是由于自身匹配精度限制，無(wú)法在小鉆石搜索模板中找到正確的最佳匹配點(diǎn)。因此使用基于格雷碼的位平面匹配只需要提升小鉆石搜索模板的匹配精度就可以大幅度提升整個(gè)鉆石搜索匹配的精度。

本文提出一種位平面混合快速匹配算法，在鉆石搜索第一步與第二步采用基于格雷碼的第4位平面與第5位平面，這兩個(gè)位平面在不同場(chǎng)景的匹配過(guò)程中相比于其他位平面具有較好的匹配效果。而在第三步小鉆石搜索模板過(guò)程中采用灰度圖進(jìn)行匹配，與其他的位平面匹配算法相比，使用灰度圖進(jìn)行匹配可以獲得最佳的匹配精度。位平面混合快速匹配算法的主要步驟如下：

(a)進(jìn)行塊匹配的搜索模板采用鉆石搜索模板，第一步搜索使用基于格雷碼的第4位平面進(jìn)行大鉆石搜索模板匹配；

(b)當(dāng)?shù)谝徊降钠ヅ浣Y(jié)果為大鉆石搜索模板中心時(shí)，則進(jìn)入第三步；否則以得到的最佳匹配點(diǎn)為中心，使用基于格雷碼的第5位平面進(jìn)行大鉆石搜索模板匹配，如果匹配結(jié)果為大鉆石搜索模板中心，則進(jìn)入第三步，否則仍重復(fù)第二步搜索操作；

(c)進(jìn)入第三步后使用灰度圖進(jìn)行小鉆石搜索模板進(jìn)行匹配，并得到最終的匹配點(diǎn)。

圖6 位平面混合快速匹配法的匹配過(guò)程

具體匹配過(guò)程如圖6所示，在第一步的搜索中使用大鉆石搜索模板，候選點(diǎn)顯示為紅色圓形，使用基于格雷碼的第4位平面進(jìn)行匹配，搜索結(jié)果得到位移為(1，1)的位置為第一次搜索的最佳匹配點(diǎn)；進(jìn)入第二步搜索，但由于上一次大鉆石搜索模板匹配中心不為自身中心，第二次搜索仍以大鉆石模板進(jìn)行搜索，以(1，1)點(diǎn)為中心，候選點(diǎn)顯示為綠色菱形，由于第一步與第二步匹配的內(nèi)容不一致，第二步需要重新計(jì)算9個(gè)匹配點(diǎn)，使用基于格雷碼的第5位平面進(jìn)行匹配，位移為(1，3)的位置為第二次搜索的最佳匹配點(diǎn)；但由于上一次大鉆石搜索模板匹配中心不為自身中心，第三次搜索仍以大鉆石模板進(jìn)行搜索，以(-3，1)點(diǎn)為中心，搜索點(diǎn)為藍(lán)色方形，使用基于格雷碼的第5位平面進(jìn)行匹配，位移為(2，4)的位置為第三次搜索的最佳匹配點(diǎn)；但由于上一次大鉆石搜索模板匹配中心不為自身中心，第四次搜索仍以大鉆石模板進(jìn)行搜索，以(2，4)點(diǎn)為中心，候選點(diǎn)為黑色三角形，使用基于格雷碼的第5位平面進(jìn)行匹配，位移為(2，4)的位置為第四次搜索的最佳匹配點(diǎn)，也是其大鉆石搜索模板的中心，下次搜索則采用小鉆石搜索模板進(jìn)行匹配；第五次搜索以(2，4)為中心，采用小鉆石搜索模板進(jìn)行匹配，匹配計(jì)算使用灰度圖進(jìn)行匹配，候選點(diǎn)為白色五角形，由于第三步與第二步匹配的內(nèi)容不一致，需要重新計(jì)算匹配中心點(diǎn)的匹配值，獲得的最佳匹配點(diǎn)即為全局的最佳匹配點(diǎn)。

6 實(shí)驗(yàn)結(jié)果與評(píng)價(jià)

對(duì)10組常用的視頻測(cè)試序列如圖7所示，使用本文算法進(jìn)行幀間運(yùn)動(dòng)估計(jì)，并與利用C1BT算法，C2BT算法，截?cái)辔粸?和6的截?cái)喔窭状a位平面和基于格雷碼的第5位平面分別進(jìn)行鉆石搜索的匹配精度和計(jì)算量進(jìn)行比較。測(cè)試視頻大小為352*288像素，采用32*32的匹配塊進(jìn)行匹配，每幅圖像取16個(gè)匹配塊，每個(gè)視頻測(cè)試序列選取連續(xù)的11幀進(jìn)行10組測(cè)試總共進(jìn)行160次匹配。

以灰度圖全搜索匹配的結(jié)果作為參考結(jié)果，對(duì)每個(gè)視頻序列測(cè)試的誤匹配結(jié)果如下表3所示?？梢杂^察到本文提出的位平面混合快速匹配算法誤匹配率為22.18%，遠(yuǎn)低于其他平面的匹配算法進(jìn)行鉆石搜索的誤匹配率，在所有場(chǎng)景都具有較好的匹配性能。

比較了不同位平面匹配算法進(jìn)行匹配的計(jì)算量。假定在鉆石搜索的三步中不進(jìn)行匹配內(nèi)容的切換，一共進(jìn)行了X次的匹配X≥13。由鉆石搜索法的特性可知，當(dāng)前的最佳匹配點(diǎn)的非匹配點(diǎn)數(shù)目已為最少，即使在不同步驟中發(fā)生匹配內(nèi)容的更換，只需要多計(jì)算一次最佳匹配點(diǎn)的NNMP值。分兩種情況進(jìn)行考慮，如果在鉆石搜索法第一步得到的最佳匹配點(diǎn)為大鉆石搜索模板的中心，那么位平面混合快速匹配法將進(jìn)行9次基于格雷碼的第4位平面匹配，5次灰度圖匹配；否則位平面混合快速匹配法將一共進(jìn)行了9次基于格雷碼的第4位平面匹配，X-12次基于格雷碼的第5位平面匹配，5次灰度圖匹配。每次位平面匹配需要進(jìn)行1次矩陣異或運(yùn)算和1次矩陣求和運(yùn)算，每次灰度圖匹配需要進(jìn)行1次矩陣相減運(yùn)算和1次矩陣求和運(yùn)算。

Container News Stefan Bridge Paris

Foreman Bus Flower Highway Elephants Dream圖7 10組常見(jiàn)測(cè)試視頻序列

視頻序列本文算法C1BTC2BTTGC5TGC6Container113077News61619813Stefan8297939492Bridge5379676563Paris019101314Foreman3978666880Bus6683736983Flower5368637477Highway541119196106Elephant Dream110769誤匹配率22.18%35.88%30.56%31.25%34.00%

不同位平面匹配算法進(jìn)行鉆石搜索一次運(yùn)動(dòng)估計(jì)的計(jì)算量如下表4所示，由表中數(shù)據(jù)可以得到位平面混合快速匹配法一共進(jìn)行了X-3次矩陣位運(yùn)算操作，X+7次矩陣加減操作。位平面混合快速匹配法的計(jì)算量?jī)H高于使用單個(gè)位平面進(jìn)行匹配的C1BT和位平面5的計(jì)算量，低于C2BT、TGC5、TGC6等位平面匹配法進(jìn)行鉆石搜索的計(jì)算量。

表4 不同位平面匹配算法進(jìn)行鉆石搜索的計(jì)算量

7 結(jié)論

本文主要對(duì)數(shù)字視頻中幀間運(yùn)動(dòng)估計(jì)算法進(jìn)行了研究。對(duì)具有計(jì)算簡(jiǎn)單，易于硬件實(shí)現(xiàn)特性的基于格雷碼的位平面匹配法進(jìn)行了分析，通過(guò)仿真測(cè)試得出第4位平面與第5位平面在不同場(chǎng)景中相對(duì)其他位平面具有較好的匹配效果并且發(fā)現(xiàn)大部分錯(cuò)誤匹配的運(yùn)動(dòng)矢量都與正確匹配的運(yùn)動(dòng)矢量非常接近。針對(duì)基于格雷碼的位平面匹配法采用全范圍搜索模板搜索時(shí)間長(zhǎng)的缺點(diǎn)，利用具有快速搜索特性和較強(qiáng)的糾錯(cuò)能力鉆石搜索模板的進(jìn)行搜索，同時(shí)針對(duì)位平面在匹配過(guò)程中精度不高，使用快速搜索模板會(huì)進(jìn)一步降低圖像的匹配精度的問(wèn)題，根據(jù)基于格雷碼的位平面匹配法性能分析的發(fā)現(xiàn)，提出了位平面混合快速匹配法，在不同的大鉆石搜索步驟中使用匹配精度高的位平面進(jìn)行匹配，尤其僅在小鉆石搜索步驟中使用具有最高匹配精度的灰度平面匹配，大大提高了匹配精度。實(shí)驗(yàn)結(jié)果表明位平面混合快速匹配法與其他位平面匹配法同時(shí)使用鉆石搜索模板，其誤匹配率最小，匹配效果最好，而其計(jì)算量較小。

[1]Barjatya A. Block matching algorithms for motion estimation[J]. IEEE Transactions on Evolution Computation，2004，8(3): 225-239.

[2]Sauer K，Schwartz B. Efficient block motion estimation using integral projections[J]. IEEE Transactions on Circuits and Systems for Video Technology，1996，6(5):513-518.

[3]Lucas B D，Kanade T. An iterative image registration technique with an application to stereo vision[C]. IJCAI，1981，81: 674-679.

[4]Horn B K P，Schunck B G. Determining optical flow[C]. Technical Symposium East，International Society for Optics and Photonics，1981:319-331.

[5]Huang J C，Hsieh W S. Automatic feature-based global motion estimation in video sequences[J]. IEEE Transactions on Consumer Electronics，2004，50(3):911-915.

[6]Ranade S，Rosenfeld A. Point pattern matching by relaxation[J]. Pattern recognition，1980，12(4): 269-275.

[7]Koga T. Motion-compensated interframe coding for video conferencing[C]. Proc of NTC，1981: 5-3.

[8]Zhu S，Ma K K. A new diamond search algorithm for fast block-matching motion estimation[J]. IEEE Transactions on Image Processing，2000，9(2):287-290.

[9]Ko S J，Lee S H，Lee K H. Digital image stabilizing algorithms based on bit-plane matching[J]. IEEE Transactions on Consumer Electronics，1998，44(3): 617-622.

[10]Ko S J，Lee S H，Jeon S W，Kang E S. Fast digital image stabilizer based on gray-coded bit-plane matching[J].IEEE Transactions on Consumer Electronics，1999，45(3): 598-603.

[11]王彥錕，劉方.采用位平面和鉆石搜索的全局運(yùn)動(dòng)估計(jì)[J]. 兵工自動(dòng)化，2007，26(11):80-85.

[12]Celebi A，Akbulut O，Urhan O，et al. Truncated graycoded bit-plane matching based motion estimation and its hardware architecture[J]. IEEE Transactions on Consumer Electronics，2009，55(3):1530-1536.

[13]Natarajan B，Bhaskaran V，Konstantinides K. Low-complexity block-based motion estimation via one-bit transforms[J]. IEEE Transactions on Circuits and Systems for Video Technology，1997，7(4): 702-706.

[14]Erturk A，Erturk S. Two-bit transform for binary block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology，2005，15(7):938-946.

[15]Urhan O，Erturk S. Constrained one-bit transform for low complexity block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology，2007，17(4) : 478-482.

[16]Choi C，Jeong J. Constrained two-bit transform for low complexity motion estimation[C].International Conference on Consumer Electronics，2013: 350-351.

[17]鐘平，于前洋，金光，等.動(dòng)態(tài)圖像序列運(yùn)動(dòng)矢量估計(jì)算法的研究[J]. 光學(xué)技術(shù)，2003，29(2): 219-225.