摘 要： 提出了半像素運動估計" title="運動估計">運動估計算法的硬件實現(xiàn)方案，該方案可有效地提高視頻編碼的速度，耗費較低的硬件資源，減小處理器的面積。
關鍵詞： 半像素運動估計 視頻壓縮
1 運動估計和運動補償
在視頻壓縮編碼中，當編碼器對圖像序列中的第N幀進行處理時，利用運動補償中的核心技術——運動估值ME(Motion Estimation)，得到第N幀的預測幀N’。在實際編碼傳輸時，并不總是傳輸?shù)贜幀，而是第N幀與其預測幀N’的差值⊿。如果運動估計十分有效，⊿中的概率基本上分布在零的附近，從而導致⊿比原始圖像第N幀的能量小得多，編碼傳輸⊿所需的比特數(shù)也就少得多。這就是運動補償技術能夠去除信源中時間冗余度的本質(zhì)所在[5]。
2 整像素運動估計
在獲得運動矢量的方法上有著很多的標準和技術。其中平均絕對誤差MAE(Mean Absolute Error)在精確程度和計算復雜度之間是一個很好的折衷(還有很多其他的標準，例如：CCF、MSE、SAD、SAD summation truncation、SAD estimation、PDC、MME、RBMAD、ABT、DPC、MADM)。如果使用MAE標準，對于一個確定的向量vector (i, j)，兩個宏塊" title="宏塊">宏塊之間的偏差定義為：
其中r是參考宏塊，s是候選坐標宏塊。參考宏塊的大小為M×N, 候選宏塊的大小是(N+2p-1)(M+2p-1)。讓D(i,j)達到最小的就是運動矢量。如果參考宏塊與所有的搜索區(qū)域內(nèi)的候選宏塊比較，這個過程就叫做全局搜索匹配算法FSBMA(full-search block matching algorithm，實現(xiàn)方法參見文獻[2])。例如，在32×32的搜索塊中，參考宏塊16×16，則共算出289(=17×17)個D(i,j)，讓D(i,j)達到最小的就是運動矢量。
3 半像素運動估計
許多視頻應用中都會需要一些亞像素運動估計，如半像素或者是四分之一像素估計。分數(shù)像素的像素估計將會有更好的圖像預測效果。半像素估計是在先前最好的整數(shù)像素估計上繼續(xù)操作。搜索區(qū)域是目標周圍的區(qū)域。像素值的插值" title="插值">插值由周圍的在這個范圍中間的像素一起計算得到。插值中一般采用線性插值" title="線性插值">線性插值的方法。圖1是H.263標準的內(nèi)差法公式。
計算出整像素最優(yōu)的運動矢量后，在其附近進行插值，然后再比較得出的新最優(yōu)的運動矢量。流程如下：
·從前一個模塊輸入計算得到的整像素的運動矢量；
·在此運動矢量附近進行半像素插值" title="像素插值">像素插值，插值時只需要原先最優(yōu)的宏塊和這個宏塊周圍的一圈像素來進行插值。 這樣除了原先的宏塊，另外在每個像素點的附近又插值出8個半像素點，這些對應的半像素點構成了8個相同規(guī)模的宏塊；
·在插值后，將新的8個模塊與原始參考模塊進行比較，計算出8個SAD(累計誤差和)。然后比較出最優(yōu)的匹配宏塊，輸出計算結果。 最后再將最優(yōu)的與原先整像素的最優(yōu)比較，輸出其中最優(yōu)的結果。
4 VLSI實現(xiàn)
本設計提出的計算半像素運動估計的體系結構中，設所使用的參考宏塊為(N-2)×(N-2)的像素矩陣,那么經(jīng)過全搜索方式得到最佳匹配模塊后，再經(jīng)邊緣擴展，共有N×N個整像素點，這些像素點作為半像素插值模塊的輸入數(shù)據(jù)，逐行串行輸入進行處理。本文具體討論半像素插值和半像素運動估計的硬件實現(xiàn)，對于前級的整像素運動估計和邊緣擴展的實現(xiàn)方法不作具體討論。
本文所提出的體系結構如圖2、圖3所示，模塊P為線性插值模塊，將兩個輸入數(shù)據(jù)的線性插值輸出。P’的輸出為兩輸入數(shù)據(jù)的中值，P’是通過已得到的縱向插值來計算斜向插值的模塊。在線性插值的計算中，對橫向插值、縱向插值和斜向插值分別計算，其中Hor_Mem存放橫向插值(如圖1中的點3，5)，該存儲器的深度為(N-2)×(N-1)；Ver_Mem存放縱向插值(如圖1中的點1，7)，該存儲器的深度為(N-1)×(N-2)；Diag_Mem存放斜向插值(如圖1中的點0，2，6，8)，該存儲器的深度為(N-1)×(N-1)。
原始的N×N個整像素點逐行串行輸入橫向插值模塊，該模塊將每兩個相鄰像素點的線性插值輸出，結果存到Hor_Mem中。但每行(即N個像素點)輸入結束時，最后一個線性插值結果應該忽略，因為該值是由本行最后一個點和下一行的第一個點插值而來，這個值是沒有意義的，并且在插值結果中，第一行和最后一行也應舍棄掉，因為它們不是半像素插值點。反映到數(shù)據(jù)流中，這個過程就是將開始的連續(xù)N個輸出結果丟棄，然后每N個點舍棄一個點，最后將結束的連續(xù)N點丟棄。這個過程可以通過Control模塊來控制Hor_Mem的write_enable完成。
對于縱向插值，可以這樣得到：不難想象，縱向插值即為當前像素點與該點前面的第N個點的插值，這樣可以對輸入數(shù)據(jù)做N個時鐘周期的延遲，再與當前像素點作線性插值。對于這個插值結果，同樣需要丟棄一些數(shù)據(jù)。首先，開始的N個插值結果需要丟棄，因為輸入的第一行數(shù)據(jù)的前面N個值是不存在的，所以這N個插值結果是沒有意義的。對于插值結果的首尾兩列也應舍棄掉，因為它們不是半像素插值點。反映到數(shù)據(jù)流中，這個過程就是將開始的連續(xù)N個輸出結果丟棄，然后每N個點舍棄首尾兩點。這個過程同樣由Control來控制。
對于斜向插值，其計算公式為h0=(a+b+c+d+2)/4，將其變換成h0=((a+b+1)/2+(c+d+1)/2)/2。于是不難發(fā)現(xiàn)，斜向插值即為與其相鄰的兩個縱向(或橫向)插值結果的中值，這里選用縱向插值作為輸入，因為連續(xù)兩個縱向插值即可求出一個斜向插值來，這樣只要將縱向插值結果串行輸入到P’模塊即可。同樣，對于輸入到Diag_Mem存儲器中的數(shù)據(jù)，同樣需要取舍：首先前N個縱向插值沒有意義，那么前N個斜向插值自然也會舍掉，然后每行的最后一個中值結果也要舍掉。因為這個結果是隔行算出的中值結果，顯然沒有意義。
這樣所有的插值結果都已經(jīng)計算出來并存在三個存儲器中，那么接下來就可以計算這些半像素插值的累計誤差和(SAD)，其中通過Hor_Mem算出2個水平運動的SAD，Ver_Mem算出2個垂直運動的SAD，Diag_Mem算出4個斜向運動的SAD。對于計算SAD的過程，有兩種選擇，可以用一個計算累計誤差和的模塊順序逐一計算出這8個SAD，這樣做可以節(jié)省硬件資源，但是缺點也很明顯，輸出結果要等到8個SAD計算完之后才能輸出，延遲過長，影響整體編碼的速度和效率。相應地，還可以用多個SAD模塊并行計算累計誤差和，對水平、垂直、斜向的累計誤差和分別同時計算，這樣提高了編碼效率，但這是以硬件資源為代價的?？傊谟嬎阃瓴逯岛?，作半像素運動估計時，要根據(jù)具體的應用需求和硬件資源進行相應的取舍。
5 關于存儲器
對于存儲器的設計，同樣面臨兩種選擇：一是選擇單口RAM，這樣只有等到半像素插值點全部計算完畢并且已經(jīng)存在三個存儲器中，才可以讀取RAM中的數(shù)據(jù)來計算接下來的8個累計誤差和，這樣做對于單口RAM的設計來說，實現(xiàn)起來比較簡單，可以節(jié)省硬件資源，但是同樣也會帶來較大的時間延遲；二是選擇雙口RAM，這樣對三個存儲器的讀寫可同時進行，隨著半像素插值點不斷存入存儲器，累計誤差和模塊同時也在對已有的半像素插值點計算累計誤差和。這樣實現(xiàn)了流水線設計，減小了整體延時，當然這仍舊是以硬件資源為代價的。首先雙口RAM的邏輯設計要比單口RAM消耗更多的邏輯資源，而且累計誤差和模塊要通過復制來并行處理三個存儲器中的數(shù)據(jù)，這些都會增加硬件的負擔。
既然兩種方法利弊明顯，筆者在這里提出一種折衷的方案：設算出一個累計誤差和的時間為TS，那么從4個斜向運動估計的累計誤差和的計算總共需要4TS的時間、而水平、垂直運動的累計誤差和分別只需要2TS的時間，那么即使采用流水線的實現(xiàn)方案，也要等到4個斜向SAD算出之后才能對8個SAD值做出比較。也就是說，有水平、垂直的累計誤差和模塊要閑置2TS的時間，硬件資源的利用率沒有得到完全發(fā)揮。于是采用一種折衷的方案，Hor_Mem、Diag_Mem采用雙口RAM，以流水線的方式完成累計誤差和的計算，而Ver_Mem則采用單口RAM的方式實現(xiàn)，并且水平垂直的累計誤差和的計算將復用同一個模塊，即先算出水平運動的2個SAD，然后再算垂直運動的2個SAD，這樣可以與斜向運動的4個SAD值的計算同步完成。
6 時序分析
原始的N×N個整像素點矩陣串行輸入，這要花費N2個時鐘周期，半像素插值點的計算是隨著整像素點的輸入同時進行的，在這N×N個數(shù)據(jù)輸入結束時，所有的半像素插值點也已經(jīng)計算完畢，存儲在三個Mem中。接下來的時序要根據(jù)運動估計模塊來分析，如果只用一個計算累計誤差和的模塊逐一計算這8個SAD，假定每個模塊耗時(N-1)2個時鐘周期,那么整個過程總共耗時N2+8×(N-1)2個時鐘周期。假定時鐘頻率為100MHz，搜索模塊大小為32×32，那么N=34，計算得到總時間約為0.1ms，完全可以滿足大多數(shù)的視頻壓縮需求。而如果采用雙口RAM，并且通過對累計誤差和模塊的復制來提高速度，那么編碼時間還會大大降低。
本文提出了一個實現(xiàn)半像素運動估計的VLSI的體系結構，這個算法模型包括：累計誤差和模塊、線性插值模塊，控制模塊(即存儲器的地址發(fā)生器)和三個存儲器模塊、每個模塊的實現(xiàn)都很簡單，只需要一些加法器、計數(shù)器、移位操作和一些簡單的控制電路。本設計方案已經(jīng)用行為級verilog實現(xiàn)成功，綜合后的工作頻率為200MHz，其關鍵路徑由存儲器的數(shù)據(jù)訪問速度決定。
參考文獻
1 T. Toivonen. Number Theoretic Transform -Based Block Mo-tion Estimation. Master′s Thesis. University of Oulu.Finland (2002)
2 H. A. Mahmoud, M. Bayoumi.A Low Power Architecture for a New Efficient Block-Matching Motion Estimation Algo-rithm. Proceedings of International Conference on Communi-cation Technology 2,2000:1173～1179
3 Y. Naito, T. Miyazaki, I. Kuroda. A Fast Full-Search Motion Estimation Method for Programmable Processors with a Multiply-Accumulator. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, 1996:3221～3224
4 Uwe Meyer-Baese, Digital Signal Processing with Field Pro-grammable Gate Arrays,2001
5 張益貞，劉 滔.Visual C++實現(xiàn)MPEG/JPEG編解碼技術.北京：人民郵電出版社, 2002