基于GPU的塊匹配運動估計技術(shù)研究

1、block-matching based on gpu for motion estimationconghuan yecollege of computer and information science, xiaogan university, xiaogan, hubei, china abstract：currently, more and more high-resolution video images video codec needs to be addressed also will dramatically increase the amount of data, as p

2、owerful gpu computing power, making the h264 gpu-based video coding technology, has great application value. as the cpu in dealing with massive network video coding and slow speed of existing bottlenecks, this paper presents an improved sub-pixel motion estimation algorithm, mainly sad sub-pixel mot

3、ion vector estimation exercise. the experiment confirmed that improved, high efficiency, feasibility, etc. experimental results show that the proposed gpu-based block-matching motion estimation algorithm could achieve good performance in comparion with the cpu-based method . keyword：gpu；block-matchi

4、ng；motion estimation 基于gpu的塊匹配運動估計技術(shù)研究葉從歡 孝感學(xué)院 計算機(jī)與信息科學(xué)學(xué)院, 孝感，中國，432000【摘要】視頻圖像的分辨率越來越高視頻編解碼需要處理的數(shù)據(jù)量也隨之急劇增大,由于gpu的強(qiáng)大運算能力，使得基于gpu的h264視頻編碼的技術(shù)研究，具有很大的應(yīng)用價值。由于cpu在處理網(wǎng)絡(luò)海量視頻圖像編碼中存在的速度慢等瓶頸，本文提出了一種gpu上的塊匹配運動估計技術(shù)。試驗證實該方法大大提高編碼的加速比。 【關(guān)鍵詞】 gpu; 塊匹配;運動估計 1 緒論隨著網(wǎng)絡(luò)通信技術(shù)和圖形技術(shù)的飛速發(fā)展，互連網(wǎng)用戶使用網(wǎng)上大容量的視頻也變得越來越便利。但是要滿足用戶對高質(zhì)

5、量視頻的需求，要有很多工作要做。目前隨著三網(wǎng)合一技術(shù)的推進(jìn)，視頻信號將廣泛應(yīng)用于日常生活中，則需要高效率的壓縮算法。由于gpu圖形處理器的快速發(fā)展，基于gpu的通用計算已經(jīng)成為一個新的研究領(lǐng)域。通過對nvidia公司最新的通用計算gpu編程模型的研究，作為h.263之后新一代的視頻通信標(biāo)準(zhǔn)，h.264理應(yīng)具有更好的性能。h.264的編碼框架與以往的視頻標(biāo)準(zhǔn)類似，都是基于混合編碼的框架。首先，將待編碼宏塊通過運動估計算法搜索幀內(nèi)或幀間的相匹配宏塊，再將匹配塊和待編碼宏塊的圖象差值經(jīng)過dct變換、量化等處理，這大大提高了視頻壓效率。而h.264標(biāo)準(zhǔn)通過改進(jìn)技術(shù)方案以及應(yīng)用新的算法，使視頻編碼性在各

6、個部分又得到提升。在相同的視覺質(zhì)量下，h.264標(biāo)準(zhǔn)的編碼效率可提高50%1，但是h.264的高壓縮率是以編碼的高計算量為代價，例如，使用264編碼器在intel雙核cpu上編碼高清視頻(1920*1080分辨率)，平均每秒只編碼1.2幀，一部兩個小時的電影需要41個小時編碼才能完，而實時高清視頻傳輸更是困難，因此如何提高編碼效率是目前的研究重點。在相同視頻質(zhì)量，h.264的編碼復(fù)雜度是mpeg-4的510倍，而解碼復(fù)雜度也是mpeg-4的24倍2。另外，圖形硬件gpu的處理速度進(jìn)來更是發(fā)展迅速，計算能力以每年2.8倍的速度增長，遠(yuǎn)遠(yuǎn)高于cpu的發(fā)展速度。gpu的體系架構(gòu)是基于大規(guī)模并行的體系

7、架構(gòu)，目前gpu已經(jīng)采用強(qiáng)大而靈活的統(tǒng)一渲染架構(gòu)3 ,其體系架構(gòu)的設(shè)計主要圍繞著兩大要素:多層次的并行計算和高效率的數(shù)據(jù)訪問。gpu 上的并行性主要體現(xiàn)在3 個層面:任務(wù)并行的多級流水線,數(shù)據(jù)并行的多線程技術(shù)以及指令并行的單指令多數(shù)據(jù)流( single instruction multiple data, simd)。在數(shù)據(jù)訪問方面，gpu 上的內(nèi)存系統(tǒng)由外部顯示內(nèi)存、內(nèi)部高速緩存和寄存器3 個層次構(gòu)成。由于gpu 高速緩存主要用于加速紋理過濾,因此其容量非常有限而且僅能只讀。gpu 內(nèi)存系統(tǒng)側(cè)重追求單位時間的數(shù)據(jù)吞吐量，即帶寬，并采用多線程技術(shù)來掩蓋高達(dá)數(shù)百個時鐘周期的主存訪問延時。相對于c

8、pu，gpu更適合進(jìn)密集型運算，而h.264標(biāo)準(zhǔn)中的運動估計就屬于密集型運算，非常適合在pu上進(jìn)行并行處理。為了合理利用gpu通用計算的資源，cuda4（compute unified device architecture，統(tǒng)一計算設(shè)備架構(gòu)）應(yīng)運而生。cuda是一種并行編程模型，它將pu的可編程頂點渲染器和片元渲染器集成起來，組成統(tǒng)一的spmd(a single program muliple data)計算設(shè)備，所以，若能夠?qū)pu并行計算的能力發(fā)揮在視頻編解碼領(lǐng)域，將會逐步滿足用戶對網(wǎng)上實時視頻傳輸?shù)男枨蟆ｋm然現(xiàn)有的gpu為視頻編碼提供了并行計算的平臺，提高了視頻編碼的效率，但是對于實時

9、視頻技術(shù)而言，例如，視頻會議，無線通信，實時體育賽事視頻等一些對實時性要求比較高的，其視頻質(zhì)量并不能滿足用戶的需求。雖然網(wǎng)速越來越快，但是如果視頻編碼不好的話，經(jīng)過網(wǎng)絡(luò)傳送到客戶端的視頻數(shù)據(jù)量同樣會非常巨大，再加上網(wǎng)絡(luò)環(huán)境的不穩(wěn)定性，也即網(wǎng)絡(luò)流量的突發(fā)性，都會對實時持續(xù)的傳播視頻造成非常大的影響，從而對用戶的服務(wù)質(zhì)量降低。雖然gpu的出現(xiàn)，為視頻編碼的并行可編程性在硬件層面提供了較好的支持，但是即使再好的硬件平臺如果沒有好的軟件平臺的話，其性能不僅得不到充分利用，而且在市場的占有率方面將會下降，從而使得gpu的研發(fā)成本難以下降。限制gpu等硬件設(shè)備性能的進(jìn)一步提高。因此，為了充分利用gpu的性

10、能，并使得在線的實時視頻技術(shù)得到提高，需要在軟件方面同步優(yōu)化，要充分挖掘視頻編碼方面的并行可編程性。h.264視頻編碼就是這樣的一種典型的并行流處理應(yīng)用,適合于在支持cuda的gpu上進(jìn)行優(yōu)化加速4.2 相關(guān)工作2.1 h.264編碼的可并行性分析由于h.264編碼需要進(jìn)行大量的計算，目前已經(jīng)有多種利用硬件平臺的性加速h.264編碼的方法，下文根據(jù)不同層次結(jié)構(gòu)的特點介紹h.264的并行理的研究現(xiàn)狀：(1) gop(group of pictures)級并行：h.264將圖像序列分為多個gop，各gop之間相關(guān)性很低，不僅可以限制誤碼擴(kuò)散，還可以進(jìn)行并行編碼處理 56。 (2) frame級并行

11、：編碼時，p幀都是將已編碼的i幀或p幀為參考幀，而b幀將前后兩個已編碼完成的幀作為參考幀。如果兩相鄰幀沒有相性，就可以對它們并行編碼78，加快編碼速度，以用于對實時性要求比較高的場所。(3) 塊級并行：h.264編碼器也每幀圖像劃分多個塊，對于若干獨立的塊，采用并行處理技術(shù)，這也是在gpu上實現(xiàn)h.264編碼時采用較多的一種技術(shù)。2.2基本原理一般攝像機(jī)等圖像采集設(shè)備采集的原始視頻都是圖像序列，由于背景是相同的，序列中相鄰兩幀圖像之間差別往往很小，對于場景鏡頭變化不大的視頻，甚至相同，如果能去除相鄰幀之間的冗余信息，會大大提高編碼的壓縮率，且不會有明顯的視覺誤差。如何消除幀間的重復(fù)信息，就需要

12、進(jìn)行幀間預(yù)測的技術(shù)。在進(jìn)行視頻編碼時，編碼器把圖像幀內(nèi)運動的圖像區(qū)域通過一種算法提取其運動矢量，并且只存儲運動矢量，這比存儲運動圖像區(qū)域所用比特少，對于h.264標(biāo)準(zhǔn)來說，幀間預(yù)測涉及到的核心技術(shù)主要是運動估計與補(bǔ)償。而h.264的亮度運動補(bǔ)償塊則采用分形學(xué)原理，從大到小按樹狀結(jié)構(gòu)分布，共有7種尺寸的運動補(bǔ)償塊:1616、816、168、88、48、84、44。這些也是目前算法復(fù)雜度最高、性能最好的基于混合編碼框架的視頻編碼技術(shù),它采用了多種在以前視頻編碼標(biāo)準(zhǔn)中不曾出現(xiàn)過的新技術(shù)。其中可變尺寸塊、多參考幀和1/4像素精度是h.264運動補(bǔ)償技術(shù)的三個新特征。分?jǐn)?shù)像素運動補(bǔ)償要求以原參考圖像插值

13、后的圖像作為新的參考圖像,然后進(jìn)行運動補(bǔ)償預(yù)測,從而運動矢量的精度達(dá)到分?jǐn)?shù)像素精度。運動矢量位移的精度越高,幀間剩余誤差越小,傳輸碼率越低,壓縮比越高。運動補(bǔ)償精度增加一倍,可以得到0.15 bit/sample的編碼增益,但是實際越過1/8像素后,繼續(xù)通過提高精度來改善運動補(bǔ)償?shù)男阅艿囊饬x就不大了。目前的標(biāo)準(zhǔn)中, h.263的運動補(bǔ)償精度達(dá)到1/2像素, h.264在指定過程中雖然嘗試采用1/8像素精度的運動補(bǔ)償,但最終亮度信號還是定為1/4像素。通常具有1/4像素精度的運動估計可以通過基本算法,sad(絕對誤差和)值相關(guān)性估計的算法,或sad二次曲線分布的近似估計算法等實現(xiàn)，而為了達(dá)到快速

14、運動估計，本文采取了1/4像素級的運動估計算法。運動估計就是從圖像序列中提取運動圖像區(qū)域的運動矢量，而運動估計研究的主要內(nèi)容就是如何快速有效地獲得精度足夠高的運動矢量。運動估計的基本原理是將視頻中的每一圖像幀分成多個相同大小的圖像區(qū)域，稱為宏塊，并假定宏塊內(nèi)所有像素的運動矢量都相同，然后在參考幀中搜索與當(dāng)前宏塊最匹配的宏塊，這就被稱為塊匹配法，而確定最佳匹配塊的方法，被稱為運動估計匹配準(zhǔn)側(cè)。與其他匹配方法相比，塊匹配法實現(xiàn)最為簡單，且運動矢量搜索能力強(qiáng)，h.264視頻標(biāo)準(zhǔn)就采用了塊匹配法。目前，有多種運動估計匹配準(zhǔn)則，下面就簡單介紹常見的四種匹配準(zhǔn)側(cè)：平均絕對誤差準(zhǔn)則(mae)，均方誤差準(zhǔn)則(

15、mse)， 絕對誤差準(zhǔn)則(sad)， 原始圖像塊和重構(gòu)圖像塊間的誤差平方和。如下（1），（2），（3）和（4）所示。 (1) (2) (3) (4)2.3經(jīng)典的并行運動估計算法全搜索法(fs)也被稱為窮盡搜索算法，是對搜索域內(nèi)的所有位置計算sad值，并從中找出最小sad，其對應(yīng)原點的偏移即為最佳運動矢量。目前，多數(shù)快速搜索算法都是基于搜索模板的，使用不同大小和形狀的搜索模板其搜索速度和性能也不同。比如搜索模板中搜索半徑過大，容易產(chǎn)生錯誤搜索方向；而搜索半徑過小，則容易得到局部最優(yōu)解。9提出了一個運行消除無用搜索點算法的并行結(jié)構(gòu)，該算法主要用于塊匹配運動估計，可以成功的清除搜索窗中的無用搜索點，

16、從而達(dá)到減少塊匹配比較的數(shù)量。相對于全搜索，大大減少計算量，可以減少57%的計算量。該方法不僅提高搜索效率，而且為幀間預(yù)測的并行計算提供了更快更準(zhǔn)的塊匹配算法，同時為h.264的實時編碼，以及實時視頻應(yīng)用提供了好的解決方案。10利用gpu的并行運算能力來解決圖像處理中的密集型的計算問題，并行加速了圖像處理的進(jìn)程。正是基于快速提高視頻的編碼質(zhì)量，當(dāng)前，利用gpu解決h.264的編碼問題成為一個非常熱門的研究領(lǐng)域。11利用gpu的并行處理能力來加速塊匹配進(jìn)程。12,13在gpu上采取多通道和幀并行技術(shù)來加速視頻編碼中的運動估計，并使得整像素運動估計和分?jǐn)?shù)精度像素的運動估計得加速比分別達(dá)到12倍和3

17、5倍左右。3 gpu上的并行運動估計h.264編碼的時候，首先是將圖像分割成很多個宏塊，然后再對各個宏塊選擇最合適的編碼模式進(jìn)行編碼，而編碼模式又主要分為幀內(nèi)預(yù)測和幀間預(yù)測。幀內(nèi)預(yù)測模式是為了消除視頻圖像序列的空間冗余，主要采用44和1616子塊的兩種模式，其原理是利用周圍已經(jīng)編碼的宏塊預(yù)測當(dāng)前宏塊的系數(shù)，然后將當(dāng)前宏塊和預(yù)測值的差值進(jìn)行變換編碼，從而提高壓縮效率。幀間預(yù)測是為了消除視頻圖像序列之間的時間冗余，h.264標(biāo)準(zhǔn)中，幀間預(yù)測采用了可變塊的運動估計技術(shù)，比如亮度宏塊可以分為1616、168、816、88的宏塊分區(qū)，而每一個88的塊，又可分為84、48、44的宏塊子分區(qū)，每個分區(qū)都要進(jìn)

18、行運動估計 對于44的塊中，對于匹配塊中每一個內(nèi)插的像素點,都可以采用最相近鄰整像素點進(jìn)行內(nèi)插,各亞像素的像素值是通過整像素像素值的線性計算得到。實際應(yīng)用中, 1/2像素值由周邊6個像素亮度值按(1,4,18,18,-4,1)加權(quán)中值濾波得到。然后用線性插值獲得1/4像素樣本。對于4:1:1的視頻格式,亮度信號的1/4像素精度對應(yīng)于色度部分1/8像素的運動矢量,對色度信號1/8像素的內(nèi)插運算可用8抽頭濾波器實現(xiàn), 采用雙線性內(nèi)插. 整像素點與內(nèi)插亞像素點之間存在相關(guān)性,因此可以通過整像素的sad值來估算內(nèi)插亞像素點的sad值。先分別在x和y方向分別做1維的最佳匹配點計算, 得到運動矢量在x 方

19、向的分量和y方向的分量, 最后對兩個分量進(jìn)行合成得到最佳運動矢量.運動矢量合成的具體過程是，搜索整像素最優(yōu)匹配點,可以通過菱形算法等。對當(dāng)前重建的參考幀, 進(jìn)行二次內(nèi)插建立1/4像素精度的參考幀。gpu的體系架構(gòu)屬于單指令流，多數(shù)據(jù)流。而對視頻的某一單一場景幀可以通過關(guān)鍵幀之間的插值進(jìn)行運動估計，這些幀的運動估計可以在gpu上進(jìn)行并行處理，并行處理是指將數(shù)據(jù)或指令并發(fā)處理，主要分為空間上和時間上的并行。空間上的并行是指在多處理器或多核上并發(fā)的執(zhí)行代碼，gpu上sads的并行計算模型如圖1所示。而時間上的并行則通常指流水線技術(shù)。 figure 1. the block matching rame

20、work for me圖1. 塊匹配流程 4 實驗與討論為了評估本文提出的方法，我們在實驗環(huán)境為：intel(r) pentium（r）d cpu 2.80ghz，1gb的內(nèi)存，microsoft visual studio 2005，以及nvidia geforce 7800gt，顯存256mb, cuda toolkit，對stefan，格式為cif（352 288）系列進(jìn)行測試，對cpu與gpu的處理性能運行時間統(tǒng)計如圖2所示。 figure 2. the performance of the proposed method圖2. cpu與gpu編碼速度統(tǒng)計 在試驗中，我們對大小為161

21、6的塊匹配過程分別在cpu上，以及cpu+gpu上，試驗效果如圖3所示，橫軸1，2，3對應(yīng)的搜索區(qū)域大小為1616，3232，6464，而縱軸為編碼的速度（幀/秒）。由圖2可知，基于gpu+cpu的塊匹配過程性能明顯優(yōu)于cpu， 1616搜索區(qū)域在塊匹配進(jìn)行搜索時加速比最高，可達(dá)到5，其他兩種搜索區(qū)域的加速比接近5。 5 結(jié)論由于現(xiàn)階段人們對高質(zhì)量實時的視頻需求越來越高，而傳動的視頻編碼技術(shù)根本達(dá)不到互聯(lián)網(wǎng)用戶的日益增長的需求，正式因為如此，h.264可以在編碼方面取得較高的效率，但是該效率是以犧牲編碼的復(fù)雜度為前提的，不利于視頻的實時編碼。本文采取一種基于gpu的并行塊匹配算法來估計運動矢量

22、，該方法相對于傳統(tǒng)的全搜索算法，都可以成比例的減少計算量。 references (參考文獻(xiàn))1 ostermann j.，bormans j.，list p.et al.video coding with h.264: tools，performance and complexity.ieee circuits and systems magazine，2004，4(1):7282 m.ravasi，m.mattavelli,c.clere.a computational complexity comparison of mpeg-4 and jvt codecs.joint video t

23、eam(jvt)of iso/iec mpeg&itu-t vceg，jvt-dl53rl-l，2002,(7):22-263 blythe d. the direct 3d 10 system j. acm transactions on graphics, 2006, 25(3): 724-7344 nvidia,nvidia cuda compute unified device architecture -programming guide version 2.1，5 denilson m.barbosa，joao paulo kitajama，wagner meira jr.et a

24、l,“parallelizing mpeg video encoding using multiprocessors”，proceedings of the xii brazilian symposium on computer graphics and image processing，19996 e.b.vander，e.g.t.jaspers，r.h.gelderblom，“mapping of h.264 decoding on a multiprocessor architecture”，spie conf.on image and video communications and

25、processing，2003.5(7):707-7187 yen-kuang chen，eric q.li，xiaosong zhou，steven ge，“implementation of h.264 encoder and decoder on personal computers”，2005,10(8):960-9838 yen-kuang chen，matthew holliman，eric debes，sergey zheltov，alexanderknyazev，stanislav bratanov，roman belenov，ishmael santos，“media app

26、lications on hyper-threading technology”，intel technology journal q1，2002,6(1):960-983，9 srinivasarao, b.k.n.; chakrabarti, i.; a parallel architecture for successive elimination block matching algorithm . computer vision, graphics & image processing, 2008. icvgip 08. sixth indian conference on 2008 , page(s): 226 - 23110 nan zhang;