一種先進運動估計算法的硬件實現

江 飛，楊 奕，楊 兵

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

1 引言

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

2 MEP設計目標

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

RW支持掩模：即在有掩模的區域不作運算。

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

輸出全部的運算結果及其最小的三個值和相應的坐標。

設計定義如下：

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

SW及RW中坐標的定義如圖1。

表1 工作模式

圖1 RW和SW坐標定義

Error（i，j）：對應（i，j）頂點的運算結果（本文的結果、運算結果都是Error）。

3 MEP算法原理

為了使256個PE能全部高效運作，并行算法的設計成了本項目目標能否實現及芯片性能的關鍵。用戶的要求是遍歷整個搜索窗口，并且找出3個最優值及其坐標，這決定了我們對每個頂點都要作運算，運算的數學表達式為：ΣΣ|SW（i，j）-RW（i，j）|。

3.1 RW（16×16）→SW（32×32）的并行運算

SW頂點區域為X（0～5），Y（0～15），即在SW的左上角區域內。每個PE計算一個頂點，各個PE并行運算，使用流水線技術實現數據的復用以確保各PE的獨立運行。

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

圖2 PE排列結構

3.2 冒泡排序算法

如圖3所示，首先將三個排序結果寄存器全部置1，將對應的坐標寄存器清零；然后將Error傳播到三個比較器與各自先前的值比較，若Error小則將Error送入自身的寄存器，并將對應的Error的坐標送入坐標寄存器；再指定優先級，若優先級為1，則將Error送入自身的寄存器，并將對應的Error的坐標送入坐標寄存器；最后返回2，直到排序結束。

圖3 排序結構

3.3 PE結構

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

4 MEP的RW掩模

掩模位單獨載入，每位掩模位對應唯一的PE，它不隨時鐘傳播，它只隨時鐘每次對一個PE進行載入。

圖4 內在結構

圖5 RW掩模

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

如果RW為32×32，對應的MW為32×32，如圖5，MW要隨時鐘循環載入對應的PE中。

掩模位控制對應的PE在以后的255個周期是否需要作運算，如果不要作運算，則將自身的SE置為全1（在作SE比較時才不會出錯）。

掩模位若在芯片內部緩沖，則需要64 bit×64 bit（512B）的緩沖區。

5 硬件實現

具體電路圖如圖6。

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

外掛DSP處理器的主要功能是完成對視頻信號的編碼，產生相應的搜索窗數據、參考窗數據以及搜索模式數據，并接受PE處理結果以完成整個信號的編碼功能。

圖6 電路結構

圖7 PE陣列結構

外置SRAM接收MEP的數據，并按照MEP的要求存儲起來，當MEP需要SRAM中的數據時，可以從SRAM中順序讀出來。

6 結論

本文詳細分析了基于塊的快速匹配的算法原理，對于不同窗口操作方式時的硬件實現速度以及所耗資源都進行了分類比較，并根據硬件實現的處理速度和面積規劃的要求，詳細地設計了該系統的構架以及各部分的硬件電路。

[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.