基于改進位平面匹配法的運動估計

劉玉峰，李震

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

1 引言

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

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

為了進一步提高塊匹配法的計算效率，位平面匹配法被提出。其中Koga等人最早在1998年提出的灰度圖位平面匹配[9]，利用包含圖像信息的第四位平面代替灰度圖進行匹配，簡化了匹配運算的復雜度，但是相鄰的像素值之間的二進制表示的多位數據的不同，給匹配帶來很大的誤差，相比于灰度圖匹配精度較低。為了改善位平面的匹配精度，多種位平面匹配法被提出。在1999年，Koga提出了改進算法，先將灰度圖用格雷碼進行編碼，并采用三步法進行搜索，提升了搜索匹配的速度[10]。文獻[11]則進一步提出了基于格雷碼編碼的位平面和鉆石搜索模板的全局運動估計算法，進一步改善了匹配過程的糾錯能力。截斷格雷碼TGC(Truncated Graycode)位平面匹配是一種利用多個經過格雷碼編碼后的位平面進行匹配的算法，文獻[12]比較測試證明，經過截斷格雷碼編碼的位平面匹配相比于未經過格雷編碼的截斷位平面具有更好的匹配效果。1BT(One-bit Transform)位平面匹配法[13]的位平面生成不同于[9]中的位平面，是將灰度圖像通過變換后設定閾值轉換為1個bit的數據。而Erturk在文獻[14]中提出了2BT(Two-bit Transform)位平面匹配的概念，即使用兩個位平面來提升匹配性能。基于1BT算法，文獻[15]則引入了Constraint Mask的概念，提出了C1BT(Constrained One-bit Transform)算法，其匹配性能高于2BT算法和其他的1BT算法。文獻[16]利用C1BT算法與2BT算法的優(yōu)勢，提出了C2BT(Constrained Two-bit Transform)算法，其匹配效果分別比基于2BT的位平面匹配和基于C1BT的位平面匹配高出0.35dB和0.28dB。截斷格雷碼，C1BT和C2BT等算法改進了灰度圖位平面匹配法的匹配效果，同時也增加了匹配過程的復雜度和計算量。改進位平面匹配法的匹配效果且盡量減少計算量成為運動估計中的難題。

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

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

2.1 提取位平面

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

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

(1)

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

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

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

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

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

(2)

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

2.2 塊匹配法

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

匹配使用的像素塊大小的選擇對匹配精度有著非常大的影響，匹配塊過小不足以提供足夠的有效信息來實現匹配，匹配塊過大可能會導致像素塊內存在不一致的運動和計算量過大等問題。在測試圖像大小為480*640時，塊匹配法在使用匹配塊面積小于32*32時不能估計到有效的運動矢量，在匹配塊面積為64*64時，得到的運動矢量的匹配效果較好；而在匹配塊面積為128*128時，匹配效果更好，但是其計算量非常大[17]。

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

(3)

最后將各個圖像塊匹配所獲得的局部運動矢量與前一幀的全局運動矢量做中值濾波，除去局部運動矢量的尖峰脈沖。

3 位平面匹配效果分析

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

圖2 匹配塊在圖中的位置

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

此外，在仿真中我們發(fā)現基于格雷碼的位平面匹配結果即使存在錯誤匹配的發(fā)生，但大多數的發(fā)生錯誤匹配的運動矢量與灰度圖匹配得到的運動矢量誤差并不大。表2中統(tǒng)計了將錯誤匹配運動矢量與灰度圖匹配得到的運動矢量相差小于一個像素誤差的數據?？梢钥吹矫總€位平面的錯誤匹配運動矢量與正確運動矢量距離小于1概率大于50%，而位平面5錯誤匹配運動矢量與正確運動矢量距離小于1概率高達87.31%，這也表明大部分錯誤匹配的運動矢量都與正確匹配的運動矢量非常接近。

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

圖3 隨機拍攝的7個場景圖像

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

表2 錯誤匹配運動矢量與正確運動矢量距離小于等于1的概率

4 鉆石搜索法

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

(a)大鉆石搜索模板

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

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

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

圖5 鉆石搜索過程

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

此外鉆石搜索法具有較強的糾錯能力，在大鉆石搜索模板搜索時，必須滿足匹配中心位于大鉆石搜索模板的中心時才能進入小鉆石搜索模板的搜索，在一定程度上增加了鉆石搜索法的匹配精度。

5 位平面混合快速算法

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

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

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

(b)當第一步的匹配結果為大鉆石搜索模板中心時，則進入第三步；否則以得到的最佳匹配點為中心，使用基于格雷碼的第5位平面進行大鉆石搜索模板匹配，如果匹配結果為大鉆石搜索模板中心，則進入第三步，否則仍重復第二步搜索操作；

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

圖6 位平面混合快速匹配法的匹配過程

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

6 實驗結果與評價

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

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

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

Container News Stefan Bridge Paris

Foreman Bus Flower Highway Elephants Dream圖7 10組常見測試視頻序列

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

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

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

7 結論

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

[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]王彥錕，劉方.采用位平面和鉆石搜索的全局運動估計[J]. 兵工自動化，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]鐘平，于前洋，金光，等.動態(tài)圖像序列運動矢量估計算法的研究[J]. 光學技術，2003，29(2): 219-225.