摘 要： 提出了半像素運動估計" title="運動估計">運動估計算法的硬件實現方案，該方案可有效地提高視頻編碼的速度，耗費較低的硬件資源，減小處理器的面積。
關鍵詞： 半像素運動估計 視頻壓縮
1 運動估計和運動補償
在視頻壓縮編碼中，當編碼器對圖像序列中的第N幀進行處理時，利用運動補償中的核心技術——運動估值ME(Motion Estimation)，得到第N幀的預測幀N’。在實際編碼傳輸時，并不總是傳輸第N幀，而是第N幀與其預測幀N’的差值⊿。如果運動估計十分有效，⊿中的概率基本上分布在零的附近，從而導致⊿比原始圖像第N幀的能量小得多，編碼傳輸⊿所需的比特數也就少得多。這就是運動補償技術能夠去除信源中時間冗余度的本質所在[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)達到最小的就是運動矢量。如果參考宏塊與所有的搜索區域內的候選宏塊比較，這個過程就叫做全局搜索匹配算法FSBMA(full-search block matching algorithm，實現方法參見文獻[2])。例如，在32×32的搜索塊中，參考宏塊16×16，則共算出289(=17×17)個D(i,j)，讓D(i,j)達到最小的就是運動矢量。
3 半像素運動估計
許多視頻應用中都會需要一些亞像素運動估計，如半像素或者是四分之一像素估計。分數像素的像素估計將會有更好的圖像預測效果。半像素估計是在先前最好的整數像素估計上繼續操作。搜索區域是目標周圍的區域。像素值的插值" title="插值">插值由周圍的在這個范圍中間的像素一起計算得到。插值中一般采用線性插值" title="線性插值">線性插值的方法。圖1是H.263標準的內差法公式。
計算出整像素最優的運動矢量后，在其附近進行插值，然后再比較得出的新最優的運動矢量。流程如下：
·從前一個模塊輸入計算得到的整像素的運動矢量；
·在此運動矢量附近進行半像素插值" title="像素插值">像素插值，插值時只需要原先最優的宏塊和這個宏塊周圍的一圈像素來進行插值。 這樣除了原先的宏塊，另外在每個像素點的附近又插值出8個半像素點，這些對應的半像素點構成了8個相同規模的宏塊；
·在插值后，將新的8個模塊與原始參考模塊進行比較，計算出8個SAD(累計誤差和)。然后比較出最優的匹配宏塊，輸出計算結果。 最后再將最優的與原先整像素的最優比較，輸出其中最優的結果。
4 VLSI實現
本設計提出的計算半像素運動估計的體系結構中，設所使用的參考宏塊為(N-2)×(N-2)的像素矩陣,那么經過全搜索方式得到最佳匹配模塊后，再經邊緣擴展，共有N×N個整像素點，這些像素點作為半像素插值模塊的輸入數據，逐行串行輸入進行處理。本文具體討論半像素插值和半像素運動估計的硬件實現，對于前級的整像素運動估計和邊緣擴展的實現方法不作具體討論。
本文所提出的體系結構如圖2、圖3所示，模塊P為線性插值模塊，將兩個輸入數據的線性插值輸出。P’的輸出為兩輸入數據的中值，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個像素點)輸入結束時，最后一個線性插值結果應該忽略，因為該值是由本行最后一個點和下一行的第一個點插值而來，這個值是沒有意義的，并且在插值結果中，第一行和最后一行也應舍棄掉，因為它們不是半像素插值點。反映到數據流中，這個過程就是將開始的連續N個輸出結果丟棄，然后每N個點舍棄一個點，最后將結束的連續N點丟棄。這個過程可以通過Control模塊來控制Hor_Mem的write_enable完成。
對于縱向插值，可以這樣得到：不難想象，縱向插值即為當前像素點與該點前面的第N個點的插值，這樣可以對輸入數據做N個時鐘周期的延遲，再與當前像素點作線性插值。對于這個插值結果，同樣需要丟棄一些數據。首先，開始的N個插值結果需要丟棄，因為輸入的第一行數據的前面N個值是不存在的，所以這N個插值結果是沒有意義的。對于插值結果的首尾兩列也應舍棄掉，因為它們不是半像素插值點。反映到數據流中，這個過程就是將開始的連續N個輸出結果丟棄，然后每N個點舍棄首尾兩點。這個過程同樣由Control來控制。
對于斜向插值，其計算公式為h0=(a+b+c+d+2)/4，將其變換成h0=((a+b+1)/2+(c+d+1)/2)/2。于是不難發現，斜向插值即為與其相鄰的兩個縱向(或橫向)插值結果的中值，這里選用縱向插值作為輸入，因為連續兩個縱向插值即可求出一個斜向插值來，這樣只要將縱向插值結果串行輸入到P’模塊即可。同樣，對于輸入到Diag_Mem存儲器中的數據，同樣需要取舍：首先前N個縱向插值沒有意義，那么前N個斜向插值自然也會舍掉，然后每行的最后一個中值結果也要舍掉。因為這個結果是隔行算出的中值結果，顯然沒有意義。
這樣所有的插值結果都已經計算出來并存在三個存儲器中，那么接下來就可以計算這些半像素插值的累計誤差和(SAD)，其中通過Hor_Mem算出2個水平運動的SAD，Ver_Mem算出2個垂直運動的SAD，Diag_Mem算出4個斜向運動的SAD。對于計算SAD的過程，有兩種選擇，可以用一個計算累計誤差和的模塊順序逐一計算出這8個SAD，這樣做可以節省硬件資源，但是缺點也很明顯，輸出結果要等到8個SAD計算完之后才能輸出，延遲過長，影響整體編碼的速度和效率。相應地，還可以用多個SAD模塊并行計算累計誤差和，對水平、垂直、斜向的累計誤差和分別同時計算，這樣提高了編碼效率，但這是以硬件資源為代價的?？傊?，在計算完插值后，作半像素運動估計時，要根據具體的應用需求和硬件資源進行相應的取舍。
5 關于存儲器
對于存儲器的設計，同樣面臨兩種選擇：一是選擇單口RAM，這樣只有等到半像素插值點全部計算完畢并且已經存在三個存儲器中，才可以讀取RAM中的數據來計算接下來的8個累計誤差和，這樣做對于單口RAM的設計來說，實現起來比較簡單，可以節省硬件資源，但是同樣也會帶來較大的時間延遲；二是選擇雙口RAM，這樣對三個存儲器的讀寫可同時進行，隨著半像素插值點不斷存入存儲器，累計誤差和模塊同時也在對已有的半像素插值點計算累計誤差和。這樣實現了流水線設計，減小了整體延時，當然這仍舊是以硬件資源為代價的。首先雙口RAM的邏輯設計要比單口RAM消耗更多的邏輯資源，而且累計誤差和模塊要通過復制來并行處理三個存儲器中的數據，這些都會增加硬件的負擔。
既然兩種方法利弊明顯，筆者在這里提出一種折衷的方案：設算出一個累計誤差和的時間為TS，那么從4個斜向運動估計的累計誤差和的計算總共需要4TS的時間、而水平、垂直運動的累計誤差和分別只需要2TS的時間，那么即使采用流水線的實現方案，也要等到4個斜向SAD算出之后才能對8個SAD值做出比較。也就是說，有水平、垂直的累計誤差和模塊要閑置2TS的時間，硬件資源的利用率沒有得到完全發揮。于是采用一種折衷的方案，Hor_Mem、Diag_Mem采用雙口RAM，以流水線的方式完成累計誤差和的計算，而Ver_Mem則采用單口RAM的方式實現，并且水平垂直的累計誤差和的計算將復用同一個模塊，即先算出水平運動的2個SAD，然后再算垂直運動的2個SAD，這樣可以與斜向運動的4個SAD值的計算同步完成。
6 時序分析
原始的N×N個整像素點矩陣串行輸入，這要花費N2個時鐘周期，半像素插值點的計算是隨著整像素點的輸入同時進行的，在這N×N個數據輸入結束時，所有的半像素插值點也已經計算完畢，存儲在三個Mem中。接下來的時序要根據運動估計模塊來分析，如果只用一個計算累計誤差和的模塊逐一計算這8個SAD，假定每個模塊耗時(N-1)2個時鐘周期,那么整個過程總共耗時N2+8×(N-1)2個時鐘周期。假定時鐘頻率為100MHz，搜索模塊大小為32×32，那么N=34，計算得到總時間約為0.1ms，完全可以滿足大多數的視頻壓縮需求。而如果采用雙口RAM，并且通過對累計誤差和模塊的復制來提高速度，那么編碼時間還會大大降低。
本文提出了一個實現半像素運動估計的VLSI的體系結構，這個算法模型包括：累計誤差和模塊、線性插值模塊，控制模塊(即存儲器的地址發生器)和三個存儲器模塊、每個模塊的實現都很簡單，只需要一些加法器、計數器、移位操作和一些簡單的控制電路。本設計方案已經用行為級verilog實現成功，綜合后的工作頻率為200MHz，其關鍵路徑由存儲器的數據訪問速度決定。
參考文獻
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++實現MPEG/JPEG編解碼技術.北京：人民郵電出版社, 2002