數(shù)字穩(wěn)像系統(tǒng)運(yùn)動(dòng)估計(jì)算法的研究

邱慶順

摘 要 運(yùn)動(dòng)矢量估計(jì)技術(shù)的研究總是圍繞著解決計(jì)算復(fù)雜度和檢測(cè)精度這對(duì)矛盾進(jìn)行的。運(yùn)動(dòng)矢量估計(jì)的算法主要有灰度投影法、特征匹配法、光流法、塊匹配法等，應(yīng)該根據(jù)實(shí)際需要合理選擇運(yùn)動(dòng)估計(jì)算法。本文先介紹了數(shù)字穩(wěn)像系統(tǒng)中的運(yùn)動(dòng)估計(jì)原理，然后介紹了兩類(lèi)運(yùn)動(dòng)估計(jì)，即平移運(yùn)動(dòng)估計(jì)和旋轉(zhuǎn)運(yùn)動(dòng)估計(jì)，然后再介紹運(yùn)動(dòng)估計(jì)中遇到的各種問(wèn)題，最后介紹了塊匹配法。

關(guān)鍵詞 運(yùn)動(dòng)估計(jì)算法 塊匹配法

中圖分類(lèi)號(hào)：TP391.4 文獻(xiàn)標(biāo)識(shí)碼：A

0前言

視頻圖像序列的相鄰幀間存在很大的時(shí)間冗余，對(duì)視頻序列進(jìn)行壓縮時(shí)，采用各種運(yùn)動(dòng)估計(jì)算法，可以大幅度提高視頻編碼的效率。塊匹配法因其簡(jiǎn)單有效，在視頻編碼中得到廣泛應(yīng)用。塊匹配運(yùn)動(dòng)估計(jì)法是基于塊內(nèi)各像素運(yùn)動(dòng)一致性的假設(shè)基礎(chǔ)上的。

1塊匹配運(yùn)動(dòng)估計(jì)原理

塊匹配法的原理為：將圖像的當(dāng)前幀劃分為固定大小（M€譔像素）的圖像子塊，一般是16€？6或者8€？像素，并假定位于同一圖像子塊內(nèi)的所有像素具有相同的位移，然后對(duì)當(dāng)前幀中的每一塊，在上一幀的一定范圍內(nèi)（搜索窗口），根據(jù)一定的匹配準(zhǔn)則找出最優(yōu)匹配塊（預(yù)測(cè)塊），并認(rèn)為該塊就是從上一幀最優(yōu)匹配塊位置處平移過(guò)來(lái)的，所得運(yùn)動(dòng)位移即為當(dāng)前塊的運(yùn)動(dòng)矢量。設(shè)可能的最大位移矢量為（dx，dy），則搜索范圍為（M+2dx）€？N+2dy），為了方便算法的實(shí)現(xiàn)，子塊的M和N 取值一般相等，dx和dy也取相等。預(yù)測(cè)塊和當(dāng)前塊逐像素的差值組成殘差塊，預(yù)測(cè)塊與當(dāng)前塊之間通過(guò)匹配準(zhǔn)則函數(shù)得到的值稱(chēng)為塊匹配誤差。

塊運(yùn)動(dòng)模型分為塊平移模型和可變形塊模型兩種，塊平移模型假定每個(gè)塊只做二維平移運(yùn)動(dòng)。給定兩幀視頻圖像 1（x）和 2（x），對(duì)于 1（x）中的一個(gè)塊，可由 2（x）中一個(gè)同樣大小的塊重建，即 1（x）|x∈ = 2（x+d）

其中，d是兩個(gè)塊的空間距離。塊重建的過(guò)程稱(chēng)為運(yùn)動(dòng)補(bǔ)償。 2（x）中的塊可以是重疊或者非重疊的。對(duì)于非重疊塊，每個(gè)塊估計(jì)一個(gè)運(yùn)動(dòng)矢量，進(jìn)行運(yùn)動(dòng)補(bǔ)償；對(duì)于重疊塊，重疊部分像素的運(yùn)動(dòng)矢量可以由兩個(gè)塊的平移矢量求平均得到，也可選擇其中匹配程度較好的運(yùn)動(dòng)矢量。

2塊匹配運(yùn)動(dòng)估計(jì)技術(shù)指標(biāo)

塊匹配運(yùn)動(dòng)估計(jì)的效率主要體現(xiàn)在圖像質(zhì)量、壓縮碼率、搜索速度三方面。運(yùn)動(dòng)估計(jì)越準(zhǔn)確，預(yù)測(cè)補(bǔ)償?shù)膱D像質(zhì)量就越高，補(bǔ)償?shù)臍埐罹驮叫。a(bǔ)償編碼所需位數(shù)越少，比特率越小；運(yùn)動(dòng)估計(jì)速度越快，越有利于實(shí)時(shí)應(yīng)用。提高圖像質(zhì)量，加快估計(jì)速度，減少比特率是塊匹配運(yùn)動(dòng)估計(jì)的目標(biāo)。塊運(yùn)動(dòng)估計(jì)可以從以下四個(gè)方面進(jìn)行研究：塊形狀與大小，塊匹配準(zhǔn)則，初始搜索點(diǎn)的選擇，搜索策略。

2.1塊的形狀與大小

塊匹配方法隱含著如下假設(shè)：同一塊內(nèi)像素的運(yùn)動(dòng)是一致的。顯然該假設(shè)具有一定的片面性，但選擇合適的塊形狀與大小可在一定程度上消除這種片面性。一般來(lái)說(shuō)，塊形狀選用正方形是比較自然的選擇，這樣既便于圖像的劃分，又有利于塊匹配準(zhǔn)則函數(shù)的計(jì)算。但這并不一定是最佳選擇，有的算法采用了其他形狀，如三角形等。塊大小的選擇受兩個(gè)矛盾的約束。塊大時(shí)，塊內(nèi)各個(gè)像素做相等平移運(yùn)動(dòng)的假設(shè)不合理；快越小，編碼一幀圖像所需要的運(yùn)動(dòng)估計(jì)次數(shù)越多，因而需要存儲(chǔ)和傳輸?shù)倪\(yùn)動(dòng)矢量數(shù)也越多，可能降低編碼效率。因此，要綜合考慮多種因素，選擇合適的塊大小。作為折中，通常選擇的宏塊作為單位。

2.2塊匹配準(zhǔn)則

塊匹配準(zhǔn)則是判斷塊相似程度的依據(jù)，因此匹配準(zhǔn)則的好壞直接影響了運(yùn)動(dòng)估計(jì)的精度；另一方面，匹配運(yùn)算復(fù)雜度、數(shù)據(jù)讀取復(fù)雜度在很大程度上取決于所采用的塊匹配準(zhǔn)則。因此，提高運(yùn)動(dòng)估計(jì)算法的速度可以用兩種途徑：一種是減少搜索匹配的點(diǎn)數(shù)，另外一種是降低塊匹配準(zhǔn)則的計(jì)算復(fù)雜度。運(yùn)動(dòng)估計(jì)算法中常用的匹配準(zhǔn)則有以下三種：

（1）平均絕對(duì)誤差（Mean absolute difference criterion，MAD）：

MAD準(zhǔn)則實(shí)現(xiàn)簡(jiǎn)單、方便，所以使用最多，還可以將MAD簡(jiǎn)化為SAD（Sum of Absolute Difference），即求和絕對(duì)誤差，可以去掉不必要的運(yùn)算。SAD定義為：

（2）均方誤差（Mean square error，MSE）

（3）歸一化互相關(guān)函數(shù)：

2.3初始搜索點(diǎn)的選擇

一種是直接選擇參考幀對(duì)應(yīng)的（0，0）位置，這種方法簡(jiǎn)單，但容易陷入局部最優(yōu)。如果采用的算法初始步長(zhǎng)太大，而原點(diǎn)又不是最優(yōu)點(diǎn)，有可能使快速搜索跳出離原點(diǎn)周?chē)赡苄员容^大的區(qū)域而去搜索遠(yuǎn)距離的點(diǎn)，導(dǎo)致搜索方向的不確定性，故有可能陷入局部最優(yōu)。另一種是選擇預(yù)測(cè)的起點(diǎn)。由于運(yùn)動(dòng)物體的整體相關(guān)性和視頻運(yùn)動(dòng)的連續(xù)性，因此視頻序列圖像的運(yùn)動(dòng)必然具有時(shí)間和空間上的相關(guān)性。許多算法都利用這種相關(guān)性先對(duì)初始搜索點(diǎn)進(jìn)行預(yù)測(cè)，以預(yù)測(cè)點(diǎn)作為搜索起點(diǎn)。大量的實(shí)驗(yàn)證明，預(yù)測(cè)點(diǎn)更加靠近最優(yōu)匹配點(diǎn)，即加強(qiáng)了運(yùn)動(dòng)矢量中心偏置分布，使得搜索次數(shù)減少。

2.4算法的評(píng)價(jià)指標(biāo)

匹配效果：峰值信噪比： PSNR=10log10（2552/MSE）

搜索時(shí)間：由于搜索時(shí)間受運(yùn)動(dòng)平臺(tái)及其他因素的影響，目前常見(jiàn)的還是比較搜索點(diǎn)數(shù)即搜索過(guò)程中進(jìn)行匹配的次數(shù)。對(duì)于塊匹配運(yùn)動(dòng)估計(jì)，計(jì)算復(fù)雜度主要依賴(lài)于平均搜索點(diǎn)數(shù)。

3結(jié)語(yǔ)

運(yùn)動(dòng)估計(jì)算法的優(yōu)劣，主要取決于匹配效果和搜索時(shí)間。匹配效果可以通過(guò)人眼進(jìn)行主觀評(píng)價(jià)，但這具有較大的隨意性，且不易進(jìn)行定量的比較。一般選擇平均峰值性噪比（PSNR）或者平均MSE進(jìn)行評(píng)價(jià)。

參考文獻(xiàn)

[1] 朱娟娟.電子穩(wěn)像理論及其應(yīng)用研究[D].四川：電子科技大學(xué)，2009.

[2] 黎洪松.數(shù)字視頻處理[M].北京：北京郵電大學(xué)出版社，2006.

[3] 楊軍.基于塊匹配的視頻圖像運(yùn)動(dòng)估計(jì)技術(shù)研究[D].湖南：湖南大學(xué)，2007.

[4] 錢(qián)捷.數(shù)字視頻的穩(wěn)像軟件設(shè)計(jì)[D].四川：電子科技大學(xué)，2011.endprint