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

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

6、個(gè)部分又得到提升。在相同的視覺質(zhì)量下，h.264標(biāo)準(zhǔn)的編碼效率可提高50%1，但是h.264的高壓縮率是以編碼的高計(jì)算量為代價(jià)，例如，使用264編碼器在intel雙核cpu上編碼高清視頻(1920*1080分辨率)，平均每秒只編碼1.2幀，一部兩個(gè)小時(shí)的電影需要41個(gè)小時(shí)編碼才能完，而實(shí)時(shí)高清視頻傳輸更是困難，因此如何提高編碼效率是目前的研究重點(diǎn)。在相同視頻質(zhì)量，h.264的編碼復(fù)雜度是mpeg-4的510倍，而解碼復(fù)雜度也是mpeg-4的24倍2。另外，圖形硬件gpu的處理速度進(jìn)來更是發(fā)展迅速，計(jì)算能力以每年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è)計(jì)主要圍繞著兩大要素:多層次的并行計(jì)算和高效率的數(shù)據(jù)訪問。gpu 上的并行性主要體現(xiàn)在3 個(gè)層面:任務(wù)并行的多級流水線,數(shù)據(jù)并行的多線程技術(shù)以及指令并行的單指令多數(shù)據(jù)流( single instruction multiple data, simd)。在數(shù)據(jù)訪問方面，gpu 上的內(nèi)存系統(tǒng)由外部顯示內(nèi)存、內(nèi)部高速緩存和寄存器3 個(gè)層次構(gòu)成。由于gpu 高速緩存主要用于加速紋理過濾,因此其容量非常有限而且僅能只讀。gpu 內(nèi)存系統(tǒng)側(cè)重追求單位時(shí)間的數(shù)據(jù)吞吐量，即帶寬，并采用多線程技術(shù)來掩蓋高達(dá)數(shù)百個(gè)時(shí)鐘周期的主存訪問延時(shí)。相對于c

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

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

10、能，并使得在線的實(shí)時(shí)視頻技術(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ì)算，目前已經(jīng)有多種利用硬件平臺的性加速h.264編碼的方法，下文根據(jù)不同層次結(jié)構(gòu)的特點(diǎn)介紹h.264的并行理的研究現(xiàn)狀：(1) gop(group of pictures)級并行：h.264將圖像序列分為多個(gè)gop，各gop之間相關(guān)性很低，不僅可以限制誤碼擴(kuò)散，還可以進(jìn)行并行編碼處理 56。 (2) frame級并行

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

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

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

14、運(yùn)動估計(jì)，本文采取了1/4像素級的運(yùn)動估計(jì)算法。運(yùn)動估計(jì)就是從圖像序列中提取運(yùn)動圖像區(qū)域的運(yùn)動矢量，而運(yùn)動估計(jì)研究的主要內(nèi)容就是如何快速有效地獲得精度足夠高的運(yùn)動矢量。運(yùn)動估計(jì)的基本原理是將視頻中的每一圖像幀分成多個(gè)相同大小的圖像區(qū)域，稱為宏塊，并假定宏塊內(nèi)所有像素的運(yùn)動矢量都相同，然后在參考幀中搜索與當(dāng)前宏塊最匹配的宏塊，這就被稱為塊匹配法，而確定最佳匹配塊的方法，被稱為運(yùn)動估計(jì)匹配準(zhǔn)側(cè)。與其他匹配方法相比，塊匹配法實(shí)現(xiàn)最為簡單，且運(yùn)動矢量搜索能力強(qiáng)，h.264視頻標(biāo)準(zhǔn)就采用了塊匹配法。目前，有多種運(yùn)動估計(jì)匹配準(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)典的并行運(yùn)動估計(jì)算法全搜索法(fs)也被稱為窮盡搜索算法，是對搜索域內(nèi)的所有位置計(jì)算sad值，并從中找出最小sad，其對應(yīng)原點(diǎn)的偏移即為最佳運(yùn)動矢量。目前，多數(shù)快速搜索算法都是基于搜索模板的，使用不同大小和形狀的搜索模板其搜索速度和性能也不同。比如搜索模板中搜索半徑過大，容易產(chǎn)生錯(cuò)誤搜索方向；而搜索半徑過小，則容易得到局部最優(yōu)解。9提出了一個(gè)運(yùn)行消除無用搜索點(diǎn)算法的并行結(jié)構(gòu)，該算法主要用于塊匹配運(yùn)動估計(jì)，可以成功的清除搜索窗中的無用搜索點(diǎn)，

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

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

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

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

20、work for me圖1. 塊匹配流程 4 實(shí)驗(yàn)與討論為了評估本文提出的方法，我們在實(shí)驗(yàn)環(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的處理性能運(yùn)行時(shí)間統(tǒng)計(jì)如圖2所示。 figure 2. the performance of the proposed method圖2. cpu與gpu編碼速度統(tǒng)計(jì) 在試驗(yàn)中，我們對大小為161

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

22、，該方法相對于傳統(tǒng)的全搜索算法，都可以成比例的減少計(jì)算量。 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;