一種基于子搜索格雷碼核的快速視頻塊運動估計算法*

王　冠，羅　珅，葛　迦

(1.中國電子科技集團公司第二十八研究所，南京210007; 2.東南大學影像科學與技術實驗室，南京210096)

?

一種基于子搜索格雷碼核的快速視頻塊運動估計算法*

王冠1*，羅珅1，葛迦2

(1.中國電子科技集團公司第二十八研究所，南京210007; 2.東南大學影像科學與技術實驗室，南京210096)

摘要:快速視頻塊運動估計是視頻編碼中的一個重要問題。在格雷碼核(GCK)算法的基礎上，提出一種改進的子搜索格雷碼核(Sub-GCK)算法。理論上的計算復雜度分析表明:提出的子搜索格雷碼核算法的運算量大約為原始格雷碼核算法的22.1%。實驗比較了子搜索格雷碼核算法、原始格雷碼核算法和其他幾種常見的運動估計算法的編碼性能，結果顯示:新算法在保證編碼質量的前提下，有效降低了運動估計時間，時間約為原始格雷碼核算法的41.9%。

關鍵詞:視頻編碼;運動估計;子搜索格雷碼核;計算復雜度;運行時間

項目來源:江蘇省自然科學基金項目(BK2012329) ;國家自然科學基金項目(61201344，11301074)

隨著通信和網絡技術的快速發展，人們的通信方式已經從信件、語音發展為可視電話等交互式視頻信息模式。據統計通過視覺途徑獲得的信息量占人類感官獲得信息量的60%［1］以上。視頻信息被認為是多媒體信息中最重要的信息［2－6］。

H. 264的編碼過程包括預測及運動估計、變換及量化、熵編碼等。其中，基于塊匹配的運動估計過程是所有編碼過程中最費時和復雜的步驟，在H. 264中占50%以上的運算量［7］。所以，優化運動估計算法將大大減少編碼復雜度和編碼時間，降低對編碼器硬件的要求。對運動估計算法的研究不僅在視頻壓縮的研究方面具有重要的理論意義，并且在商業和工業等領域也有著很高的實際應用價值。

基于塊匹配的運動估計算法的優劣主要體現在3個方面:搜索速度、壓縮碼率以及圖像質量，這些效果又主要由3個因素決定:匹配準則、初始搜索點和搜索策略。

(1)運動估計的匹配準則

運動估計匹配準則的實質是一類誤差衡量函數，用以度量兩個圖像塊的相似度。實際中常用的匹配準則包括:最小絕對誤差和SAD (Sum of Absolute Difference)和投影絕對誤差和SPAD(Sum of Projection Absolute Difference)［8］等。

(2)運動估計的初始搜索點

初始搜索點的預測是基于當前塊和相鄰幀匹配塊在時間和空間上的相關性，使用相鄰塊的運動矢量對當前塊的最佳起始搜索位置進行預測。大量實驗證明，使用預測點作為起始搜索點，能夠加快運動估計過程。

(3)運動估計的搜索策略

運動估計的搜索策略主要從搜索路徑方面入手，通過減少搜索點數來達到降低運動估計計算復雜度的目的。國內外研究人員已經對此進行了許多研究，提出了一系列的搜索策略，主要包括:全搜索算法FS(Full Search)，三步搜索算法TSS(Three Step Search )［9］，菱形搜索算法DS (Diamond Search)［10］。其中菱形搜索算法因為同時具有較高的搜索速度和精度而被被納入MPEG－4標準的驗證模型。最近，Ben-Artzi等人提出基于格雷碼核GCK(Gray Code Kernel)［11］的滑動窗快速算法。Moshe和Hel-Or提出利用GCK進行視頻快速運動估計［12］，比菱形搜索算法具有更快的搜索性能。

圖1　構造一維GCK的樹結構(k=3)

針對快速視頻塊運動估計問題，在格雷碼核(GCK)算法的基礎上，下面提出一種改進的子搜索格雷碼核(Sub-GCK)算法，在保證編碼質量的前提下，盡可能降低計算復雜度，從而保證視頻編碼的實時性。

1　格雷碼核［11］

1.1一維格雷碼核

定義1:

式中:αkv表示數αk乘以核v，“Ⅱ”表示串聯過程。該組核的遞歸定義可以由一個深度為k的二叉樹來表示，圖1為k= 3的二叉樹。處于二叉樹第i層的節點就是的核，包含2i個核。圖中二叉樹的樹葉就是V(3)s的8個核，樹枝上標記的是α的值，用以產生這些核。

定義2:當序列α=α1，α2，…，αk，αi∈{ +1，－1}唯一確定了一個核，則稱該序列為v的α索引。

定義4:連續α相關的一組有序核v0，v1，…，vn組成格雷碼核GCK(Gray Code Kernels)，該序列稱為格雷碼序列GCS(Gray Code Sequence)。定義5:給定兩個α相關的核，它們的和vp與差vm定義如下:

GCK算法主要根據兩個α相關的核v+，v－∈在空間上的相關性來做快速計算的。設兩個α相關核v+，v－的索引序列分別為()、()，它們存在一個共同的長度為Δ= 2r－1(r為索引序列中出現不同索引的序號)的向量，則以下關系式成立:

式中: 0Δ表示由Δ個零組成的向量。由上式推導出以下公式:

設b+，b－分別為信號序列x與濾波核v+，v－的線性卷積，即:

則b+(i)，b－(i)有如下關系:

上式提供了一種計算信號與GCK濾波核線性卷積的快速算法(圖2)。當獲得某個線性卷積結果b－(b+)后，只需要兩次運算就能得到與之α相關的濾波核對應的線性卷積結果b+(b－)，并且與核大小無關。對于定義1，當s=［1］時，就是一維沃爾什－哈達瑪變換WHT(Walsh-Hadamard Transform)濾波核序列。

圖2　一維信號與GCK濾波核線性卷積的快速算法［11］

1.2二維格雷碼核

二維格雷碼核算法的輸入信號和濾波核都為二維。

定義6:設v01(i1，i2)、v02(i1，i2)是兩個二維濾波核:

若v1，v2為α相關的一維濾波核，并且有一個共同的長度為Δ的向量，由文獻［7］可知v01(i1，i2)、v02(i1，i2)存在如下關系:

若b1=I·v01為圖像在濾波核v01上的濾波結果，若b2=I·v02為圖像在濾波核v02上的濾波結果，則有如下關系［7］:

由上式可知，在二維情況下，計算圖像的一個濾波值需要兩次運算。當s=［1］時，v01(i1，i2)即為二維沃爾什－哈達瑪(WHT)濾波核，所以可使用式(8)來實現WHT的快速算法，即滑動窗WHT算法。圖3(a)描述了8×8的二維WHT濾波核，圖3 (b)描述了我們取前m個投影值的順序。

2　基于GCK WHT的運動估計方案［12］

文獻［12］提出了一種基于GCK WHT算法的快速運動估計方案:設或為第j幀圖像Ij在位置(x，y)上的宏塊，宏塊周圍的搜索區域為SA)，使用序列Sq中的前m個二維WH濾波核。設宏塊的第i個濾波值為。

對于第j幀圖像做運動估計的過程:

(1)使用滑動窗WHT計算Ij中的所有宏塊p(j)對應的前m個WH濾波值，將結果保存起來。

圖3　二維沃爾什－哈達瑪濾波核

(2)對于Ij中的某一宏塊做如下計算

①計算參考幀Ij－1中搜索區域內每個宏塊的前m個濾波值。

④重復步驟2。

3　改進的基于Sub-GCK WHT的運動估計方案

本文在文獻［12］的基礎上，提出一種改進的基于Sub-GCK WHT的運動估計方案。由式(8)可知，使用GCK WHT算法計算位置(i，j)下的WH濾波值時，需要使用位置(i，j－Δ)下的濾波值，所以GCK WHT算法，可以應用于子搜索區域的搜索中。在滑動窗GCK算法中，Δ=2r－1(r為兩個α相關濾波核的索引序列中出現不同索引的序號)，最大搜索間隔Δ取決于用于運動估計的所有WH濾波核中r的最小值。由于實際中使用的WH濾波核對應的r最小為3，所以子搜索區域的最大搜索間隔Δ= 4。出于搜索精度的考慮，我們使用Δ= 2，在GCK算法的基礎上提出一種子搜索格雷碼核Sub-GCK(Sub Search GCK)運動估計方案，其過程如下:

對于第j幀圖像做運動估計的過程:

(1)使用滑動窗WHT計算Ij中的所有宏塊p(j)對應的前m個WH濾波值，將結果保存起來。

(2)對于Ij中的某一宏塊做如下計算

①計算參考幀Ij－1中子搜索區域內每個宏塊的前m個濾波值。

⑤重復步驟2。

4　改進方案的計算復雜度以及硬件實現復雜度分析

4.1計算復雜度分析及比較

假設加法、減法、取絕對值以及乘2操作均需要一次運算。設宏塊大小為k×k，搜索范圍為n×n，濾波核個數為m，m個濾波核中包含的所有黑色矩形塊的個數為b，改進方案中步驟②取t個塊，步驟③取q個塊。以下我們將分析對單個宏塊做運動估計時，5種搜索算法的計算復雜度。這5種搜索算法為全搜索算法(FS)、3步搜索算法(TSS)［9］、菱形算法(DS)［10］、GCK［12］以及提出的Sub-GCK。

用積分圖［13］計算當前宏塊的前m個濾波值需要3+3b+2(m－1)次運算。由于子搜索區域有n2/4個搜索點，并且計算圖像塊的一個濾波值需要2次運算，所以計算所有搜索點的投影值需要mn2/2次運算。步驟②，找出n2/4個搜索點中的濾波值最小的前t個點需要tn2/4次運算。步驟③，計算t個點的所有領域搜索點的濾波值需要8t［3+3b+2(m－1)］次運算。在這9t個點(包括t個點本身)中，找出濾波值最小的前q個點需要9qt次運算。步驟④，用SAD準則對這q個點做匹配運算得到最佳匹配點，需要q(3k2－1) +(q－1)次運算。所以，對單個宏塊做匹配運算的計算復雜度為3+3b+2(m－1) +mn2/2+tn2/4+8t［3+ 3b+2(m－1)］+9qt+q(3k2－1) +(q－1)，簡化為(8t+ 1) (3b + 2m + 1) + (2m + t) n2/4 + 3q (k2+ 3t)－1。表1比較了5種算法的計算復雜度(取實驗中的m=5，搜索范圍15×15)。注意GCK的計算復雜度受4個方面因素影響:宏塊大小為k×k，搜索范圍n× n，濾波核個數m以及塊的個數q。

由于實驗中我們使用的宏塊大小為16×16，選取的較優候選塊個數q=4，改進方案中第一次排除后剩下的候選塊個數t = 3。所以，FS、TSS、DS、GCK以及Sub-GCK對應的運算量分別為172 800、19 200、11 904、10 193、2 253。改進后的算法Sub-GCK的運算量大約為GCK的22.1%。

表1　5種搜索算法的計算復雜度

4.2硬件實現復雜度分析

在這一小節，類似于文獻［14－15］，我們將在乘法/加法器和蝶形處理器兩種情況下分析提出的Sub-GCK的算法硬件實現中的空間－時間復雜度。

4.2.1乘法/加法器系統

文獻［14］指出，在單乘法器硬件中(比如: DSP微機)，由乘法和加法共同決定執行時間。在這些情況下，以上5種算法的空間復雜度一樣，都是一個乘法/加法器的空間。因此，空間－時間復雜度的大小主要決定于計算時間的長短。從表1看出，提出的Sub-GCK的硬件計算時間要優于其他5種算法

4.2.2基于蝶形計算的多核處理器

考慮到提出的Sub-GCK具有時序的特點，即利用前一個時間計算出來的投影值來計算當前的投影值，所以類似于文獻［15］，我們可以采用串行硬件結構實現(即“串入串出”結構)。串行實現的過程中可以采用移位寄存器或者RAM實現數據的收集。對于大小為k×k的宏塊，我們只需要2個加法器和2k個數據存儲空間。

5　實驗結果及分析

我們使用視頻壓縮標準H. 264的標準測試軟件來進行實驗，版本為JM86。PC配置為:操作系統Windows 7(32位)，處理器Intel(R) Core(TM) 2 Quad CPU Q8400 @ 2.66 GHz 2.67 GHz，內存4 Gbyte。選擇的測試序列為City，Coastguard，Football，Motherdaughter，視頻格式為YUV，大小為352×288。選擇亮度分量的峰值信噪比(Y-PSNR)，比特率(Bit-Rate)以及運動估計時間(ME Time)作為比較參數。Y-PSNR能反應編碼后視頻圖像的質量，Bit-Rate的高低反應視頻的壓縮效果，ME Time反應搜索算法的速度。

表2　5種運動估計算法(FS、TSS、DS、GCK、Sub-GCK)的視頻編碼結果比較

由表2可以得到如下結論:

(1)分析各視頻序列編碼后的Y-PSNR數據可知，編碼后的視頻質量由高到低依次是: FS、GCK、 Sub-GCK、DS、TSS，并且Sub-GCK的Y-PSNR與GCK非常接近，大約相差0.04 db，與FS相差大約0.18 db。所以，采用Sub-GCK與采用GCK的視頻編碼質量在客觀上是基本相同的。

(2)分析各視頻序列編碼后的Bit-Rate數據可知，TSS、DS、GCK、Sub-GCK的比特率比全搜索算法(FS)的比特率分別多出約31.1%、4.6%、2.3%、3.4%。其中改進算法Sub-GCK與原算法GCK相比，多出約1.1%的比特率。

(3)分析各視頻序列編碼的ME Time數據可知，FS、TSS、GCK、Sub-GCK算法的運動估計時間比較穩定，DS算法由于搜索點數不固定，所以實際搜索時間不穩定(例如視頻序列Football中DS的運動估計時間遠大于TSS)，但是多數情況下DS的速度還是比TSS快。運動估計時間最少的是Sub-GCK，約為改進前的算法GCK的41.9%。這個數值高于理論值22.1%，初步判斷是因為運動估計過程不僅僅包含搜索過程，還包括初始化和運動矢量預測等過程。

圖4給出了Mother-daughter視頻序列的利用FS、GCK、Sub-GCK算法編碼前后的部分圖像(原圖、QP =28、QP =36三幅圖)的主觀效果圖。由圖4可知，雖然Sub-GCK算法的客觀編碼效果比FMEGCK略差，但是主觀差異微乎其微，甚至與客觀效果最好的全搜索算法(FS)相比，也很難看出兩者之間的差異。

圖4　Mother-daughter視頻序列利用FS、GCK、Sub-GCK算法編碼前后的主觀效果圖(a1)～(a3)分別為FS算法下的原圖、QP = 28、QP = 36的主觀效果圖; (b1)～(b3)分別為GCK算法下的原圖、QP=28、QP=36的主觀效果圖; (c1)～(c3)分別為Sub-GCK算法下的原圖、QP=28、QP=36的主觀效果圖

6　結論

針對快速視頻塊運動估計問題，本文提出一種改進的子搜索格雷碼核(Sub-GCK)算法。與其他幾種運動估計算法的比較結果顯示: Sub-GCK的Y-PSNR與GCK非常接近，因此Sub-GCK與GCK的視頻編碼質量在客觀上是基本相同的，與FS略有差異。主觀效果上，Sub-GCK與GCK基本相同，與FS的差異也很小。運動估計時間方面，消耗最少的是提出的Sub-GCK，約為改進前GCK算法的41.9%。綜合來看，改進后算法Sub-GCK在保證編碼質量的前提下，有效降低了運動估計時間，并且在編碼速度和編碼質量上都優于TSS、DS算法。

參考文獻:

［1］胡棟.靜態圖像編碼的基本方法與國際標準［M］.北京:北京郵電大學出版社，2003: 3.

［2］劉紀紅，劉祚，李中帆.基于特征分析的人臉檢測算法的DSP實現［J］.電子器件，2013，36(6) : 774－778.

［3］楊彥.基于人臉檢測和多線索融合的實時人臉跟蹤系統［J］.電子器件，2013，36(3) : 304－308.

［4］張美燕，蔡文郁.無線視頻傳感器網絡有向感知K覆蓋控制算法研究［J］.傳感技術學報，2013，26(5) : 728－733.

［5］秦晅.一種視頻圖像目標抗遮擋跟蹤算法［J］.指揮信息系統與技術，2011，2(6) : 50－54.

［6］羅麗莉，秦晅.基于視頻圖像序列的動目標跟蹤定位技術研究［J］.指揮信息系統與技術，2011，1(3) : 22－27.

［7］Wiegand T，Sullivan G J，Bjontegaard G，et al.Overview of the H. 264/AVC Video Coding Standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13(7) : 560－576.

［8］Li N，Mak C M，Cham W K.Fast Block Matching Algorithm in Walsh Hadamard Domain［C］/ /Computer Vision—ACCV 2006.Springer Berlin Heidelberg，2006: 712－721.

［9］Koga T.Motion-Compensated Interframe Coding for Video Conferencing［C］/ /Proc NTC’81.1981: 5－3.

［10］Zhu S，Ma K K.A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation［J］.IEEE Transactions on Image Processing，2000，9(2) : 287－290.

［11］Ben-Artzi G，Hel-Or H，Hel-Or Y.The Gray-Code Filter Kernels ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(3) : 382－393.

［12］Moshe Y，Hel-Or H.Video Block Motion Estimation Based on Gray-Code Kernels［J］.IEEE Transactions on Image Processing，2009，18(10) : 2243－2254.

［13］Crow Franklin C.Summed-Area Tables for Texture Mapping［C］/ / Proceedings of the 11th Annual Conference on Computer Graphics and Interactive Techniques.1984: 207－212.

［14］Richards M A.On Hardware Implementation of the Split-Radix FFT［J］.IEEE Trans Acoust，Speech，Signal Process，1988，36 (10) : 1575－1581.

［15］Bi G，Aung A，Ng B P.Pipelined Hardware Structure for Sequency-Ordered Complex Hadamard Transform［J］.IEEE Signal Process Lett，2008，15: 401－404.

王　冠(1982－)，男，漢族，江蘇南京人，現就職于中國電子科技集團公司第二十八研究所，碩士研究生，工程師。主要研究方向為信息系統軟件研發與集成，52guantou@ 163.com。

Applications of Delay Precise Calibration in the Equivalent Sampling Based on FPGA

LIU Wenbin1，ZHU Mingri1*，ZHENG Danping2，YAO Xin1，PAN Kai1
(1.School of Electronic Engineering and Automation，Guilin University of Electronic Technology，Guilin Guangxi 541004，China; 2.School of Computer Science and Engineering，Guilin University of Electronic Technology，Guilin Guangxi 541004，China)

Abstract:For some high-frequency signals，such as ultra-wideband radar echo signal，because its bandwidth is often in the hundreds of megabytes and it is difficult to make real-time sampling，so equivalent sampling is usually implemented by adopting FPGA and in combination with programmable delay device.There is a difference between the delay value of each delay device and delay value of programmable delay device which exists temperature drift.Delay precise calibration based on FPGA is designed to minimized the delay value of programmable delay device with temperature drift.Experiment results show that the delay precise calibration is effective，and there is a good reference value in the acquisition of high frequency signals.

Key words:FPGA; equivalent sampling; delay precise calibration; temperature drift

中圖分類號:TP391

文獻標識碼:A

文章編號:1005－9490(2015) 03－0699－07

收稿日期:2014－07－21修改日期: 2014－08－22

doi:EEACC: 7210G10.3969/j.issn.1005－9490.2015.03.046