一種先進(jìn)運(yùn)動(dòng)估計(jì)算法的硬件實(shí)現(xiàn)

江 飛，楊 奕，楊 兵

（中國電子科技集團(tuán)公司第58研究所，江蘇 無錫 214035）

1 引言

視頻壓縮是數(shù)字視頻信號(hào)傳輸和儲(chǔ)存的必要手段，一般我們采用基于預(yù)測和變換的混合編碼技術(shù)，它們在H.261、H.262、H.263和MPEG-1、MPEG-2、MPEG-4標(biāo)準(zhǔn)中已經(jīng)被采納。在這種編碼技術(shù)中運(yùn)動(dòng)估計(jì)占有很重要的地位，也耗費(fèi)了視頻編碼中大部分的計(jì)算時(shí)間。通常能夠得到精確和平滑的運(yùn)動(dòng)場矢量的運(yùn)動(dòng)估計(jì)方法都比較復(fù)雜，如光流場運(yùn)動(dòng)估計(jì)、貝葉斯運(yùn)動(dòng)估計(jì)、基于小波的分層估計(jì)，甚至基于全搜索的塊匹配法等，需要大量的計(jì)算時(shí)間，并不適合實(shí)際的軟件和硬件實(shí)現(xiàn)。而一些在實(shí)際中經(jīng)常采用的快速運(yùn)動(dòng)估計(jì)方法如快速塊匹配法（三步法、四步法、菱形搜索法）基本可以滿足實(shí)際視頻顯示的效果，并且在硬件方面也較容易實(shí)現(xiàn)。本文介紹的就是一種基于快速塊匹配法的硬件實(shí)現(xiàn)。

2 MEP設(shè)計(jì)目標(biāo)

六種工作模式如表1所示。

RW支持掩模：即在有掩模的區(qū)域不作運(yùn)算。

在最大的模式（64×64 →128×128）下，運(yùn)算時(shí)間不超過5ms（工作頻率為33MHz）。

輸出全部的運(yùn)算結(jié)果及其最小的三個(gè)值和相應(yīng)的坐標(biāo)。

設(shè)計(jì)定義如下：

PW：Peak Window（頂點(diǎn)窗，頂點(diǎn)區(qū)域）；RW：Reference Window（參考窗）；SW：Search Window（搜索窗）；PE：Processor Element（處理單元）。

SW及RW中坐標(biāo)的定義如圖1。

表1 工作模式

圖1 RW和SW坐標(biāo)定義

Error（i，j）：對(duì)應(yīng)（i，j）頂點(diǎn)的運(yùn)算結(jié)果（本文的結(jié)果、運(yùn)算結(jié)果都是Error）。

3 MEP算法原理

為了使256個(gè)PE能全部高效運(yùn)作，并行算法的設(shè)計(jì)成了本項(xiàng)目目標(biāo)能否實(shí)現(xiàn)及芯片性能的關(guān)鍵。用戶的要求是遍歷整個(gè)搜索窗口，并且找出3個(gè)最優(yōu)值及其坐標(biāo)，這決定了我們對(duì)每個(gè)頂點(diǎn)都要作運(yùn)算，運(yùn)算的數(shù)學(xué)表達(dá)式為：ΣΣ|SW（i，j）-RW（i，j）|。

3.1 RW（16×16）→SW（32×32）的并行運(yùn)算

SW頂點(diǎn)區(qū)域?yàn)閄（0～5），Y（0～15），即在SW的左上角區(qū)域內(nèi)。每個(gè)PE計(jì)算一個(gè)頂點(diǎn)，各個(gè)PE并行運(yùn)算，使用流水線技術(shù)實(shí)現(xiàn)數(shù)據(jù)的復(fù)用以確保各PE的獨(dú)立運(yùn)行。

如圖2所示，RW的數(shù)據(jù)按先X方向后Y方向的順序滾入PE；同時(shí)SW中的數(shù)據(jù)按先X方向后Y方向的順序滾入PE。在PE同時(shí)收到RW與SW后進(jìn)行已定義好的運(yùn)算操作，并在下一個(gè)時(shí)鐘周期將RW的數(shù)據(jù)向下一個(gè)PE進(jìn)行傳播。而SW的數(shù)據(jù)是在數(shù)據(jù)總線上按一定的順序進(jìn)行傳播，也就是有多個(gè)PE同時(shí)接收一個(gè)SW的數(shù)據(jù)。RW的數(shù)據(jù)全部滾入PE1起的下一個(gè)周期開始輸出誤差結(jié)果Error并進(jìn)行冒泡排序，在RW（15，15）到達(dá)PE256時(shí)，全部數(shù)據(jù)輸入完成，并且除去最后一個(gè)數(shù)外，其他255個(gè)頂點(diǎn)計(jì)算完畢；再過一個(gè)周期，排序完畢?？偣残?56+256+1=513個(gè)周期來完成全部的頂點(diǎn)運(yùn)算及結(jié)果排序。

圖2 PE排列結(jié)構(gòu)

3.2 冒泡排序算法

如圖3所示，首先將三個(gè)排序結(jié)果寄存器全部置1，將對(duì)應(yīng)的坐標(biāo)寄存器清零；然后將Error傳播到三個(gè)比較器與各自先前的值比較，若Error小則將Error送入自身的寄存器，并將對(duì)應(yīng)的Error的坐標(biāo)送入坐標(biāo)寄存器；再指定優(yōu)先級(jí)，若優(yōu)先級(jí)為1，則將Error送入自身的寄存器，并將對(duì)應(yīng)的Error的坐標(biāo)送入坐標(biāo)寄存器；最后返回2，直到排序結(jié)束。

圖3 排序結(jié)構(gòu)

3.3 PE結(jié)構(gòu)

如圖4所示。只要將SW'中的數(shù)據(jù)按upper、lower組織好，即可實(shí)現(xiàn)對(duì)SW'中數(shù)據(jù)的復(fù)用。在第二次加載RW（0，0）時(shí)，SW'正在讀入SW'（0，16），它也正是PE需要的數(shù)據(jù)。Counter為12bit，其余的reg為8bit。

4 MEP的RW掩模

掩模位單獨(dú)載入，每位掩模位對(duì)應(yīng)唯一的PE，它不隨時(shí)鐘傳播，它只隨時(shí)鐘每次對(duì)一個(gè)PE進(jìn)行載入。

圖4 內(nèi)在結(jié)構(gòu)

圖5 RW掩模

如果RW為16×16，則MW（掩模窗口）也為16×16，并且MW只需載入一次。

如果RW為32×32，對(duì)應(yīng)的MW為32×32，如圖5，MW要隨時(shí)鐘循環(huán)載入對(duì)應(yīng)的PE中。

掩模位控制對(duì)應(yīng)的PE在以后的255個(gè)周期是否需要作運(yùn)算，如果不要作運(yùn)算，則將自身的SE置為全1（在作SE比較時(shí)才不會(huì)出錯(cuò)）。

掩模位若在芯片內(nèi)部緩沖，則需要64 bit×64 bit（512B）的緩沖區(qū)。

5 硬件實(shí)現(xiàn)

具體電路圖如圖6。

PE陣列的功能就是接收DSP提供的搜索窗（Searching Window ，簡稱SW）數(shù)據(jù)、參考窗（Referencing Window，簡稱RW）數(shù)據(jù)，以及搜索模式（Searching Pattern，簡稱SP）數(shù)據(jù)，計(jì)算出運(yùn)動(dòng)向量，并將處理結(jié)果返回給DSP。

外掛DSP處理器的主要功能是完成對(duì)視頻信號(hào)的編碼，產(chǎn)生相應(yīng)的搜索窗數(shù)據(jù)、參考窗數(shù)據(jù)以及搜索模式數(shù)據(jù)，并接受PE處理結(jié)果以完成整個(gè)信號(hào)的編碼功能。

圖6 電路結(jié)構(gòu)

圖7 PE陣列結(jié)構(gòu)

外置SRAM接收MEP的數(shù)據(jù)，并按照MEP的要求存儲(chǔ)起來，當(dāng)MEP需要SRAM中的數(shù)據(jù)時(shí)，可以從SRAM中順序讀出來。

6 結(jié)論

本文詳細(xì)分析了基于塊的快速匹配的算法原理，對(duì)于不同窗口操作方式時(shí)的硬件實(shí)現(xiàn)速度以及所耗資源都進(jìn)行了分類比較，并根據(jù)硬件實(shí)現(xiàn)的處理速度和面積規(guī)劃的要求，詳細(xì)地設(shè)計(jì)了該系統(tǒng)的構(gòu)架以及各部分的硬件電路。

[1]T Koga,K Iinuma,A Hirano,Y Iijima,and T Ishiguro.Motion compensated interframe coding for video conferencing[C].Proc.Nat.Telecommun.Conf.,New Orleans,LA,Dec.1981.G5.3.1-G5.3.5.

[2]M Po,C K Cheung,W C Ma.A novel fast block motion estimation algorithm using center-biased search pattern[J].Proc.IEEE Int.Conf.on Neural Net and Signal Proc,1995,2(12): 1 616-1 619.

[3]T Sikora.The MPEG-4 video standard verification model[J].IEEE Trans.Circuits Syst.Video Technol,1997,7(2): 19-31.

[4]J Y Tham,S Ranganath,M Ranganath,and A A Kassim.A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation[J].IEEE Trans.Circuits Syst.Video Technol,1998,8(8): 369-377.

[5]J R Jain,A K Jain.Displacement measurement and its application in interframe image coding[J].IEEE Trans.Commun,1981,COM-29(12) :1 799-1 808.