中期報告--塊匹配算法比較研究

1、.塊匹配算法研究與比較-以EBMA和TSS算法為例1、 塊匹配算法簡介運(yùn)動估計是視頻處理系統(tǒng)的一個重要組成部分，二維運(yùn)動估計是其中一個大類，迄今已發(fā)展出一系列的二維運(yùn)動估計算法，被廣泛地應(yīng)用于視頻壓縮、采樣率轉(zhuǎn)換等方面。二維運(yùn)動估計算法主要目標(biāo)是估計出相鄰視頻幀之間的二維運(yùn)動向量。根據(jù)不同的運(yùn)動表示方法，可以分為整體運(yùn)動估計，基于像素的運(yùn)動估計，基于塊的運(yùn)動估計，基于區(qū)域的運(yùn)動估計，不同方法應(yīng)用場合不同，各有優(yōu)劣。本文主要研究基于塊的運(yùn)動估計算法。塊匹配算法是一種重要的基于塊的運(yùn)動估計算法?；趬K的運(yùn)動估計算法是在已估計的運(yùn)動場上施加平滑約束，不圖像分割為互不重疊的稱為塊的區(qū)域，并且假定每個塊

2、內(nèi)的運(yùn)動可以用一個簡單的參數(shù)模型（如恒定、仿射、雙線性）特征化。令表示第m個圖像塊，M代表圖像塊數(shù)，塊的分割應(yīng)滿足，理論上，一個塊可以表示成任意形狀，實(shí)際上一般都表示成N*N的正方形。在最簡單的情況下，假設(shè)每個塊的整體運(yùn)動是恒定的，即做整體平移。本文將采用這一假設(shè)，此時的估計問題是為每一個塊尋找一個MV，這一類算法被稱為塊匹配算法(BMA)。在錨定幀中給定一個圖像塊，此時估計問題是在目標(biāo)幀中尋找一個匹配塊，使得兩塊之間誤差最小，這兩塊之間空間位置的位移矢量是這個塊的MV。在塊平移模型下，誤差公式表示為對于每個塊的MV估計只影響這個塊的預(yù)測誤差，因此只要使每個塊估計時預(yù)測誤差最小，從而使得累積誤

3、差最小，即塊匹配算法包括簡單地窮盡塊匹配算法及一些快速算法，快速算法有二維對數(shù)法，三步搜索法，鉆石算法，MVFAST算法，其中鉆石算法被列入MPEG-4標(biāo)準(zhǔn)。2、 窮盡塊匹配算法及其快速算法三步搜索法實(shí)現(xiàn)2.1 窮盡塊匹配(EBMA)算法在1中的討論使得已知，塊匹配算法在估計每個塊的MV目標(biāo)在于使得最小，一種方法可以是在一個預(yù)定的搜索區(qū)域內(nèi)，將與目標(biāo)幀中所有候選塊進(jìn)行比較，并尋找具有最小誤差的一個。這兩個塊之間的位移差即為所估計的MV。為了減小計算量，令p=1。搜索區(qū)域取關(guān)于當(dāng)前區(qū)域?qū)ΨQ，左右上下各有R個像素，搜索的步長為d，搜索步長決定估計精度。令塊大小為，圖像大小為，塊數(shù)目為。對于單像素步

4、長，錨定幀每一塊候選匹配塊共(2*R+1)個。令一次運(yùn)算定義包括一個減法，一個絕對值和一個加法，計算每個候選塊誤差運(yùn)算次數(shù)為，估計每個塊MV的運(yùn)算次數(shù)為，那么一幀的運(yùn)算次數(shù)為。可見其運(yùn)算次數(shù)不依賴于塊大小。該過程代碼實(shí)現(xiàn)如下：/為a塊分?配?空?間?N*N并賦3值char sliceN*N;for(int s=0;sN;s+)for(int t=0;tN;t+)slices*N+t=*(Y1+(s+i*N)*width+t+j*N); /在-r,r*-r,r遍歷for(int p=-r;p=r;p+=d)/p=-r:d:r共22*r+1在d=1if(p+i*Nheight-1) break;f

5、or(int q=-r;q=r;q+=d)/p=-r:d:r共22*r+1在d=1if(q+j*Nwidth-1) break;/獲?得?目?標(biāo)幀?對?應(yīng)|塊char goal_sliceN*N;for(int s=0;sN;s+)for(int t=0;tN;t+)goal_slices*N+t=*(Y2+(p+s+i*N)*width+q+t+j*N); /求兩?個?塊間?距離?double d_sum=0.0;for(int s=0;sN;s+)for(int t=0;tN;t+)d_sum+=abs(goal_slices*N+t-slices*N+t);/獲?得?最?小?間?距塊if

6、(d_summin_dis) min_dis=d_sum;/COORDINATE(0,i,j)=i*N+N/2;/COORDINATE(1,i,j)=j*N+N/2;shifti*width/N+j=p;shiftheight*width/(N*N)+i*width/N+j=q;在求得位移向量MV后，根據(jù)錨定幀和MV可以預(yù)測目標(biāo)幀。for(int i=0;iheight/N;i+)for(int j=0;jwidth/N;j+)int i_indexN*N;int j_indexN*N;/塊（i,j）?的?預(yù)測a坐?標(biāo)for(int s=0;sN;s+)for(int t=0;tN;t+)i_

7、indexs*N+t=shifti*width/N+j+i*N+s;j_indexs*N+t=shiftheight*width/(N*N)+i*width/N+j+j*N+t; for(int s=0;sN;s+)for(int t=0;tY1=new charheight*width;this-Y2=new charheight*width;/從YUV文?件t中D讀取?頭兩?幀?Y分?量?fseek(fp,0,SEEK_SET);fread(this-Y1,1,height*width,fp);/讀取?參?考?幀?（幀?1）?fseek(fp,height*width*3/2,SEEK_S

8、ET);fread(this-Y2,1,height*width,fp);/讀取?目?標(biāo)幀?（幀?2）?3、 實(shí)驗(yàn)結(jié)果比較分析1、 不同搜索步長下窮盡塊匹配算法性能比較搜索范圍信噪比(dB)運(yùn)行時間(s)323.0404100.998203.6326010.452163.6326010.343103.6326010.156表1 測試幀為foremanforeman測試結(jié)果觀察表1及foreman測試結(jié)果，可知當(dāng)搜索范圍過大時，三步搜索法預(yù)測效果反而變差，這是因?yàn)閳D片不滿足衡亮度假設(shè)，大范圍搜索時，滿足MAD最小的最佳匹配塊并非實(shí)際錨定塊。在R=32時，雖然SNR上減少不大，但是主管視覺感受明顯

9、變差；在R=20,16,10時，SNR及主觀感受無差異，但是小的R帶來了極大的運(yùn)算量上的減小，因此可以盡量選擇較小的R=10或16。這也說明主管感受與客觀標(biāo)準(zhǔn)之間雖然存在一定相關(guān)，但是并非理想上相關(guān)。搜索范圍信噪比(dB)運(yùn)行時間(s)3217.9668340.9912017.9668340.4371617.9668340.3121017.9668340.156表2 測試幀為akiyoakiyo測試結(jié)果觀察表2及akiyo測試結(jié)果，預(yù)測效果極好，這可以體現(xiàn)在SNR及預(yù)測圖像給人的主觀感受上，明顯優(yōu)于foreman預(yù)測效果?？梢钥吹?，Akiyo預(yù)測效果與搜索范圍無關(guān)，這是因?yàn)閍kiyo滿足了恒亮

10、度要求且塊的位移向量很小(大多為0)，因此預(yù)測效果要優(yōu)于foreman且不受R范圍的影響。通過上述比較可知，預(yù)測效果與視頻幀質(zhì)量相關(guān)，對于視頻幀質(zhì)量較差視頻，不適合采用塊匹配算法；預(yù)測效果的主觀感受與客觀標(biāo)準(zhǔn)間并非完全吻合的，這是值得注意的。2、 窮盡塊匹配算法與三步搜索法測試效果比較下面測試在三步搜索法下兩種圖像表現(xiàn)出來的預(yù)測效果：搜索范圍信噪比(dB)運(yùn)行時間(s)323.6111030.063163.6111030.04683.6111030.031表3 測試幀為foremanforeman測試結(jié)果搜索范圍信噪比(dB)運(yùn)行時間(s)3217.9668340.0621617.966834

11、0.047817.9668340.031表4 測試幀為akiyoakiyo測試結(jié)果采用三步搜索法進(jìn)行估計時，觀察比較foreman和akiyo測試結(jié)果可知，搜索范圍改變并未引起SNR及圖像主觀感受的改變，但小的搜索范圍可以使得運(yùn)算量減小。foreman與akiyo之間比較可以發(fā)現(xiàn)，質(zhì)量好的視頻幀同樣會取得好的預(yù)測效果。將三步搜索法與1中窮盡塊匹配算法所得測試結(jié)果比較，可知對于質(zhì)量較差的視頻幀，三步搜索法在大的搜索范圍時，預(yù)測效果優(yōu)于窮盡搜索法，但在小的搜索范圍時，預(yù)測質(zhì)量有所降低（但主觀感受上無差別），但運(yùn)算量大大減??；對于質(zhì)量好的視頻幀，三步搜索法預(yù)測質(zhì)量不變，但運(yùn)算量大大減小?？梢?，三步搜索法綜合性能較優(yōu)，并且較穩(wěn)定。綜上分析可知，塊匹配算法性能與視頻幀的質(zhì)量相關(guān)：視頻幀質(zhì)量越好，預(yù)測效果越好。三步搜索法總體性能優(yōu)于窮盡搜索法，只是在視頻幀質(zhì)量較差時預(yù)測質(zhì)量會略劣于窮盡搜索法（無視覺感官上明顯差別