鬼佬大哥大
  • / 24
  • 下載費用:30 金幣  

基于GPU并行實現的快速運動估計方法.pdf

關 鍵 詞:
基于 GPU 并行 實現 快速 運動 估計 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
摘要
申請專利號:

CN201210013334.3

申請日:

2012.01.17

公開號:

CN102547289B

公開日:

2015.01.28

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效號牌文件類型代碼:1604號牌文件序號:101322520747IPC(主分類):H04N 7/26專利申請號:2012100133343申請日:20120117|||公開
IPC分類號: H04N19/436(2014.01)I 主分類號: H04N19/436
申請人: 西安電子科技大學
發明人: 張崗山; 顏善; 趙林靖; 李建東; 吳宇紅; 劉炯
地址: 710071 陜西省西安市太白南路2號
優先權:
專利代理機構: 代理人:
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201210013334.3

授權公告號:

102547289B||||||

法律狀態公告日:

2015.01.28|||2012.09.05|||2012.07.04

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公開了一種基于GPU并行實現的快速運動估計方法。首先,利用局部全搜索以最大概率判定當前分割塊是否屬于背景域;然后,若當前分割塊屬于背景域,則結束整像素精度搜索,否則通過降低搜索域分辨率來提升搜索步長,執行低分辨率的局部整像素全搜索來捕捉最優運動矢量分布范圍,即粗定位;屬于運動域的分割塊在完成粗定位后,利用局部全搜索細化運動矢量分布范圍,完成整像素精度的運動估計,即細定位;最后,利用高密度、高精度搜索模板細化運動矢量,完成1/4像素精度搜索,并結束當前分割塊的運動估計;搜索過程中采用了中止判別技術,即當前步的最小失真參考塊達到設定匹配精度,則算法的整像素搜索過程結束;搜索過程中每一步的搜索點數都不會發生變化。

權利要求書

1.一種基于GPU并行實現的快速運動估計方法,其特征在于:
整個運動估計過程劃分為整像素精度搜索與1/4像素精度搜索,且搜索過程中的每
個步驟都采用一種局部全搜索思想;并將搜索域劃分為背景域和運動域;執行步驟如下:
A1、利用局部全搜索以最大概率判定當前分割塊是否屬于背景域;
A2、若當前分割塊屬于背景域,則結束整像素精度搜索,否則通過降低搜索域分辨
率來提升搜索步長,執行低分辨率的局部整像素全搜索來捕捉最優運動矢量分布范圍,
即粗定位;屬于運動域的分割塊在完成粗定位后,利用局部全搜索細化運動矢量分布范
圍,完成整像素精度的運動估計,即細定位;
A3、利用高密度、高精度搜索模板細化運動矢量,完成1/4像素精度搜索,當前分
割塊的運動估計結束;
搜索過程中采用了中止判別技術,即當前步的最小失真參考塊達到設定匹配精度,
則算法的整像素搜索過程結束;搜索過程中每一步的搜索點數都不發生變化。
2.根據權利要求1所述的運動估計方法,其特征在于,具體執行步驟如下:
1)采用搜索點數為N2、搜索尺寸為NxN、步長為1個整像素的正方形模板,并以搜
索域原點(0,0)為中心,執行一次局部整像素精度全搜索,并行計算出N2個搜索點處
的SAD值,
SAD ( i , j ) = Σ m = 1 M Σ n = 1 N | f k ( m , n ) - f k - 1 ( m + i , n + j ) | ; ]]>
式中:(i,j)為搜索點坐標,fk和fk-1分別為當前幀和參考幀的像素值,M與N分別
為分割塊的寬度與高度;
搜索點的集合為:
Ω 1 = { ( s x , x y ) | - N 2 s x N 2 - 1 , - N 2 s y N 2 - 1 } ; ]]>
然后比較已計算出的N2個SAD值來獲取最小SAD值,最小SAD值對應的搜索點即最
小塊誤差(MBD)點,若MBD點落在背景域或塊匹配精度達到閥值,則跳轉至4),否則
進行2);即:
(mcx,mcy)∈{(sx,sy)|-1≤sx≤1,-1≤sy≤1}或SAD(mcx,mcy)≤Threshold;
式中:(mcx,mcy)為當前步的MBD點在搜索域中的坐標,Threshold代表精度閥值;
2)以上一步的MBD點坐標作為本次搜索的中心點,并采用搜索點數為N2、搜索尺
寸為(2N-1)x(2N-1)、步長為2個整像素的正方形模板提升搜索步長,執行一次低分辨
率的局部整像素全搜索;
搜索點的集合為:
Ω 2 = { ( s x , s y ) | s x = mu x + 2 i , s y = mu y + 2 j ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>
式中:(mux,muy)為上一步MBD點的坐標;
然后比較已計算出的N2個SAD值來獲取本次的MBD點,若MBD點的塊匹配精度達到
閥值或本次MBD點的SAD值等于上一步MBD點的SAD值,則跳轉至4),否則執行3);
即:
SAD(mcx,mcy)≤Threshold??或SAD(mcx,mcy)=SAD(mux,muy);
3)采用搜索點數為N2、搜索尺寸為NxN、步長為1個整像素的正方形模板,并以上
一步的MBD點坐標作為本次搜索的中心點,執行一次局部整像素精度全搜索,并行計算
出N2個搜索點處的SAD值;
搜索點的集合為:
Ω 3 = { ( s x , s y ) | s x = mu x + i , s y = mu y + j ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>
然后比較已計算出的N2個SAD值來獲取本次的MBD點,執行4);
4)以上一步的MBD點坐標作為本次搜索的中心點,采用搜索點數為N2、步長為1/4
像素的正方形模板進行1/4像素局部全搜索;
搜索點的集合為:
Ω 4 = { ( s x , s y ) | s x = mu x + i 4 , s y = mu y + j 4 ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>
并行計算出N2個搜索點處的SAD值,并獲取最終MBD點坐標,此次獲取MBD點處對
應的坐標為最終運動矢量MV,算法執行結束。
3.根據權利要求1所述的運動估計方法,其特征在于,上述運算步驟在GPU
平臺上并行執行。

說明書

基于GPU并行實現的快速運動估計方法

技術領域

本發明屬于通信技術領域,涉及信源編碼,是一種利用GPU快速完成視頻壓縮編
碼中運動估計的方法。

背景技術

目前,主流計算機中的處理器主要是中央處理器CPU和圖形處理器GPU。受游戲市
場和軍事視景仿真需求的牽引,GPU性能提高速度很快。最近幾年中,GPU的性能每一
年就可以翻倍,大大超過了CPU遵循摩爾定律(每18~24月性能翻倍)的發展速度。為
了實現更逼真的圖形效果,GPU支持越來越復雜的運算,其可編程性和功能都大大擴展。
傳統上,GPU只負責圖形渲染,而大部分的處理都交給了CPU。但隨著CPU越來越難克
服因提高時鐘頻率后的散熱問題,轉而運用增加運算核心的方法來進行加速。之前,GPU
作為圖形渲染專用的處理器,具有高度的并行特性,GPU也從單一的圖形渲染設備轉化
為作為通用計算的協處理器。

NVIDIA公司于2007年正式發布的CUDA(Compute?Unified?Device?Architecture,
計算統一設備架構)是第一種不需要借助圖形學API就可以使用類C語言進行通用計算
的開發環境和軟件體系。與以往的傳統GPGPU開發方式相比,CUDA有十分顯著的改進。
在性能、成本和開發時間上較傳統的CPU解決方案有顯著優勢,CUDA的推出在學術界和
產業界引起了熱烈反響。現在,CUDA已經在很多領域獲得了廣泛應用,并取得了豐碩的
成果。隨著CUDA的成熟與推廣,以及GPU實現視頻壓縮編碼有著天然的優勢,國內外
研究人員開始著手研究將視頻壓縮中的運動估計應用于CUDA環境中。在當前的各類視
頻編碼標準中,運動估計(Motion?Estimation,ME)是去除時間冗余最基礎和最有效
的方法,也是各類視頻編碼算法所普遍采用的核心技術。運動估計性能的優劣直接決定
編碼效率和重構視頻質量,一般而言,運動估計越準確,則補償的殘差圖像所需表示比
特就越少,編碼效率就越高,在相同碼率下的解碼視頻就具有更好的圖像質量;另一方
面,利用軟件平臺在CPU上實現的視頻編碼系統中,運動估計模塊的時間損耗占整個編
碼的50%以上,甚至在對背景復雜、運動劇烈的視頻序列編碼中占到了80%以上。所以
能否在普通PC機上實現高分辨率視頻的實時編碼,運動估計能否快速、高效的實現是
一個關鍵技術問題。

目前,視頻編碼系統中塊匹配運動估計方法分為全搜索方法與快速運動估計方法。

1.全搜索(Full?Search,FS)算法也稱窮盡搜索法,是在搜索范圍內全局計算每
一個候選搜索點的SAD(i,j)值,并找出最小SAD值,其最小值在搜索域中對應坐標點即
為最終運動矢量,全搜索算法是塊匹配運動估計中精度最高的算法,但其計算復雜度高。
為此,在NVIDIA公司提出CUDA平臺后,由Wei-Nien?Chen?and?Hsueh-Ming撰寫的
《H.264/AVC?motion?estimation?implementation?on?compute?unified?device?
architeture(CUDA)》公開了一種利用CUDA平臺并行實現全搜索運動估計方法,通過他
們的最終測試結果發現:這種利用CUDA平臺并行實現全搜索運動估計相比于單純依靠
CPU實現來說,其速度上大約有10倍左右的加速比。其不足之處是:雖然引入了并行處
理,但全搜索算法未利用運動矢量分布特性來壓縮搜索域中不必要的搜索點,使其耗時
仍然不適合在普通PC機上實時編碼高分辨率視頻序列。

2.針對全搜索算法的計算復雜度高,為此研究者們提出了一系列經典的快速運動估
計算法,如由T.Koga等人提出的經典的三步搜索法、最早由S.Zhu和K.K?Ma提出的菱
形搜索算法、由C.Zhu,X.Lin和L.P.Chan于2002年提出的六邊形搜索算法、還有最
終納入H.264/AVC標準的UMHexagonS算法。這些通過采用適合于運動矢量分布特性的
形狀與大小的模板,并在搜索過程動態調整模板的兩個參數來捕獲全局最小點。如果把
這些算法強制移植到GPU平臺上,算法搜索模板(9點正方形,菱形、六邊形、非對稱
十字)的不規整、模板中搜索點數不滿足warp倍數、不同搜索模板的動態調整等問題,
不利于線程的分配和存儲器的訪問優化,這些技術問題阻礙了其在GPU上的高效實現;
部分快速算法,特別是混合算法,在計算過程中存在大量的邏輯判斷,那么根據平臺的
執行模型,如果需要控制單個線程的行為,必須使用分支,這樣做的后果是在函數的執
行過程中產生大量的divergence(如果一個warp中的線程分別跳轉到不同的分支,那
么SM就需要把每一個分支的指令發射到每一個SP上,在有SP根據線程邏輯決定需不
需要執行,執行時間將是執行多個分支所用時間之和,由此形成的現象叫divergence),
這也會大大降低GPU的執行效率。

全搜索方法的搜索精度高,但即使利用GPU作為協處理器在普通的PC機上實現,
其耗時量也很難讓其投入到實時高分辨率場合的應用;而一些經典的快速運動估計,其
在搜索域中需要運算的搜索點數相對于全搜索大大減少(UMHexagonS方法相對于全搜索
方法能夠節約90%以上的計算量),但這些算法卻很難在GPU上高效實現。

發明內容

本發明的目的在于避免上述已有技術的不足,通過CUDA平臺在GPU上實現搜索精
度高、速度快的運動估計,從而解決在普通PC機上實現高分辨率視頻序列的實時編碼
過程中,運動估計模塊耗時巨大這一瓶頸問題。

本發明的技術方案是:

一種基于GPU并行實現的快速運動估計方法,

整個運動估計過程劃分為整像素精度搜索與1/4像素精度搜索,且搜索過程中的每
個步驟都采用一種局部全搜索思想;并將搜索域劃分為背景域和運動域;執行步驟如下:

A1、利用局部全搜索以最大概率判定當前分割塊是否屬于背景域;

A2、若當前分割塊屬于背景域,則結束整像素精度搜索,否則通過降低搜索域分辨
率來提升搜索步長,執行低分辨率的局部整像素全搜索來捕捉最優運動矢量分布范圍,
即粗定位;屬于運動域的分割塊完成粗定位后,利用局部全搜索細化運動矢量分布范圍,
完成整像素精度的運動估計,即細定位;

A3、利用高密度、高精度搜索模板細化運動矢量,完成1/4像素精度搜索,當前分
割塊的運動估計結束;

搜索過程中采用了中止判別技術,即當前步的最小失真參考塊達到設定匹配精度,
則算法的整像素搜索過程結束;搜索過程中每一步的搜索點數都不發生變化。

所述的運動估計方法,具體執行步驟如下:

1)采用搜索點數為N2、搜索尺寸為NxN、步長為1個整像素的正方形模板,并以搜
索域原點(0,0)為中心,執行一次局部整像素精度全搜索,并行計算出N2個搜索點處
的SAD值,

SAD ( i , j ) = Σ m = 1 M Σ n = 1 N | f k ( m , n ) - f k - 1 ( m + i , n + j ) | ; ]]>

式中:(i,j)為搜索點坐標,fk和fk-1分別為當前幀和參考幀的像素值,M與N分別
為分割塊的寬度與高度;

搜索點的集合為:

Ω 1 = { ( s x , x y ) | - N 2 s x N 2 - 1 , - N 2 s y N 2 - 1 } ; ]]>

然后比較已計算出的N2個SAD值來獲取最小SAD值,最小SAD值對應的搜索點即最
小塊誤差點,若MBD點落在背景區域或塊匹配精度達到閥值,則跳轉至4),否則進行2);
即:

(mcx,mcy)∈{(sx,sy)|-1≤sx≤1;-1≤sy≤1}或SAD(mcx,mcy)≤Threshold;

式中:(mcx,mcy)為當前步的MBD點在搜索域中的坐標,Threshold代表精度閥值;

2)以上一步的MBD點坐標作為本次搜索的中心點,采用搜索點數為N2、搜索尺寸
為(2N-1)x(2N-1)、步長為2個整像素的正方形模板提升搜索步長,在低分辨率搜索域
內執行一次低分辨率的局部整像素全搜索;

搜索點的集合為:

Ω 2 = { ( s x , s y ) | s x = mu x + 2 i , s y = mu y + 2 j ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>

式中:(mux,muy)為上一步MBD點的坐標;

然后比較已計算出的N2個SAD值來獲取本次的MBD點,若MBD點的塊匹配精度達到
閥值或本次MBD點的SAD值等于上一步MBD點的SAD值,則跳轉至4),否則執行3);
即:

SAD(mcx,mcy)≤Threshold或SAD(mcx,mcy)=SAD(mux,muy);

3)采用搜索點數為N2、搜索尺寸為NxN、步長為1個整像素的正方形模板,并以上
一步的MBD點坐標作為本次搜索的中心點,執行一次局部整像素精度全搜索,并行計算
出N2個搜索點處的SAD值;

搜索點的集合為:

Ω 3 = { ( s x , s y ) | s x = mu x + i , s y = mu y + j ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>

然后比較已計算出的N2個SAD值來獲取本次的MBD點,執行4);

4)以上一步的MBD點坐標作為本次搜索的中心點,采用搜索點數為N2、步長為1/4
像素的正方形模板進行1/4像素局部全搜索;

搜索點的集合為:

Ω 4 = { ( s x , s y ) | s x = mu x + i 4 , s y = mu y + j 4 ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>

并行計算出N2個搜索點處的SAD值,并獲取最終MBD點坐標,此次獲取MBD點處對
應的坐標為最終運動矢量MV,算法執行結束。

所述的運動估計方法,上述運算步驟在GPU平臺上并行執行。

本發明與現有技術相比,具有如下優點:

(1)本發明結合了運動矢量的分布特性和CUDA的并行處理特性,相比于全搜索的
CUDA并行執行,獲得了高的加速比。通過在NVIDIA公司的GPU上實測:相比于利用CUDA
在GPU上執行并行全搜索方法,本方法獲得了約9倍的加速比。

(2)本發明融合了全搜索與傳統快速運動估計的思想,通過局部并行全搜索提高
了快速運動估計方法的精度。NVIDIA公司的GPU上實測的結果表明,本方法的搜索精度
很接近全搜索方法,因此提升了視頻編碼系統的壓縮比。

(3)本發明把計算量最大的運動估計模塊從CPU上移植到協處理GPU上,極大的
分擔了CPU負荷。

(4)本發明的算法也可采用AMD的OpenCL實現。

(5)本發明具有通用性,能夠運用于國際通用標準H.26x系列的視頻編碼系統、
中國第二代信源編碼標準AVS等基于塊匹配運動估計的視頻編碼系統。

附圖說明

圖1是本發明運動估計流程圖;

圖2是搜索域的背景域與運動域劃分圖;

圖3是kernel的線程組織結構圖;

圖4是kernel的存儲模型圖;

圖5是block中每個線程的執行流程圖;

圖6是并行歸約過程圖;

圖7是具體運動搜索實例圖;

圖8是參與實測的視頻編碼的系統架構圖;

圖9是本發明與全搜索算法的PSNR對比圖;

圖10是分割塊執行步驟分布圖;

圖11是執行步驟的壓縮比貢獻值圖;

圖12是本發明與全搜索的壓縮比對比圖;

圖13是采用本發明編碼不同分辨率測試序列獲得的加速比圖。

具體實施方式

以下結合具體實施例,對本發明進行詳細說明。

本發明采用基于塊的匹配思想,采用多模板動態調整和多步搜索方案,且當前的
步的執行相關于上一步的執行結果。本發明利用了運動矢量分布特性,并通過執行局部
全搜索找到當前局部搜索窗口的最小塊誤差(Minimum?Block?Distortion,MBD)點(局
部全搜索尋找當前區域的MBD可靠性高,且能方便、高效的利用CUDA來并行實現)。搜
索域的分辨率變化實質上是保證在每次搜索的搜索點個數不發生變化(即保證線程的組
織形式在整個的運動估計過程中不發生變化),而動態伸縮每次運動估計搜索步長。由
于塊匹配殘差值實際上是在搜索范圍內建立了誤差表面函數,全局最小點即對應著最佳
運動矢量。而這個誤差表面函數通常并不單調,所以搜索步長太小,就容易陷入局部最
優;而搜索步長太大,又容易產生錯誤的搜索路徑。所以在本方法中采用了3種不同分
辨率的N2點正方形模板來動態調整搜索步長大小。運動估計過程由四步局部全搜索組
成,其中前三步屬于整像素搜索,第四步是1/4像素精度搜索。為減少大量的數據傳輸、
線程分配、參數傳遞等操作所帶來的時間損耗,設計中將1/4像素精度搜索納入到算法
體系,其屬于算法的第四步搜索過程。

參照圖2,根據視頻序列的的運動特征,將搜索域劃分為背景域、運動域。

視頻序列尤其需要實時傳送的視頻信號(視頻聊天、會議系統、監控系統)一般
都存在豐富的背景區域,首次局部全搜索能夠以最大概率的判定當前塊是否為背景,提
前終止后續不必要搜索。

這種方法實現中最主要的技術支持:NVIDIA?GPU的兩項技術和CUDA平臺的編程模
型:

兩項技術:利用共享存儲器進行同一個block中所有線程間通信;通過柵欄同步
保證同一個block中所有線程都執行到同一個位置。這兩項技術保證block中每一個線
程能夠可靠地共享上一步MBD點坐標和終止標志,這樣block中每一個線程通過訪問
shared?memory來確定候選搜索點在紋理參考系中坐標和判斷后續步驟的搜索操作是否
執行。從算法角度,這兩項技術提供了壓縮搜索點數的技術支持。

CUDA編程模型:kernel實質上是以block為單位執行的,當一個block執行結
束后,將會釋放占用的硬件資源,后續的block將會進入到當前SM中成為活動線程塊,
這樣可以實現每一個分割塊獨立并行的進行運動估計,并在滿足提前終止條件情況下釋
放當前block所占資源,這樣將會壓縮總體運動估計搜索時間。

本發明將視頻序列的每一幀劃分為大小相同、互不重疊的分割塊,并為每個分割
塊在參考幀中劃分大小相同的搜索域,然后在搜索域內按照一定的匹配準則搜索與之相
似度最高的預測塊,該預測塊與當前分割塊之間形成的位移即為當前分割塊的運動矢
量。

整個運動估計過程劃分為整像素精度搜索與1/4像素精度搜索,且搜索過程中的
每個步驟都采用了一種局部全搜索思想;根據視頻序列的特征,將搜索域劃分為背景域
和運動域;首先,利用局部全搜索以最大概率判定當前分割塊是否屬于背景域;然后,
若當前分割塊屬于背景域,則結束整像素精度搜索,否則通過降低搜索域分辨率來提升
搜索步長,執行低分辨率的局部整像素全搜索來捕捉最優運動矢量分布范圍,即粗定位;
屬于運動域的分割塊完成粗定位后,利用局部全搜索細化運動矢量分布范圍,完成整像
素精度的運動估計,即細定位;最后,利用高密度、高精度搜索模板細化運動矢量,完
成1/4像素精度搜索,當前分割塊的運動估計結束;搜索過程中采用了中止判別技術,
即當前步的最小失真參考塊達到設定匹配精度,則算法的整像素搜索過程結束;搜索過
程中每一步的搜索點數都不會發生變化。

參照圖1和圖7,本發明的運動估計方法具體執行以下步驟:

步驟1)以搜索域原點(0,0)為中心,執行一次搜索尺寸為NxN的局部整像素全
搜101,并行計算出N2個搜索點處的SAD值,

SAD ( i , j ) = Σ m = 1 M Σ n = 1 N | f k ( m , n ) - f k - 1 ( m + i , n + j ) | ; ]]>

式中:(i,j)為搜索點坐標,fk和fk-1分別為當前幀和參考幀的像素值,M與N分別為分
割塊的寬度與高度;

搜索點的集合為:

Ω 1 = { ( s x , x y ) | - N 2 s x N 2 - 1 , - N 2 s y N 2 - 1 } ; ]]>

然后比較已計算出的N2個SAD值來獲取最小SAD值,最小SAD值對應的搜索點即
最小塊誤差(Minimum?Block?Distortion,MBD)點,若MBD點落在背景區域或塊匹配
精度達到閥值,則跳轉至步驟4),否則進行步驟2);即:

(mcx,mcy)∈{(sx,sy)|-1≤sx≤1;-1≤sy≤1}或SAD(mcx,mcy)≤Threshold;

式中:(mcx,mcy)為當前步的MBD點在搜索域中的坐標,Threshold代表精度閥值;

步驟2)以上一步的MBD點坐標作為本次搜索的中心點,采用搜索點為N2、搜索尺
寸為(2N-1)x(2N-1)、步長為2個整像素的正方形模板102提升搜索步長,在低分辨率
搜索域內執行一次局部整像素全搜索;

搜索點的集合為:

Ω 2 = { ( s x , s y ) | s x = mu x + 2 i , s y = mu y + 2 j ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>

式中:(mux,muy)為上一步MBD點的坐標;

然后比較已計算出的N2個SAD值來獲取本次的MBD點,若MBD點的塊匹配精度達
到閥值或本次MBD點的SAD值等于上一步MBD點的SAD值,則跳轉至步驟4),否則執行
步驟3);即:

SAD(mcx,mcy)≤Threshold或SAD(mcx,mcy)=SAD(mux,muy);

步驟3)以上一步的MBD點坐標作為本次搜索的中心點,執行一次搜索尺寸為NxN
的局部整像素全搜索103,并行計算出N2個搜索點處的SAD值;

搜索點的集合為:

Ω 3 = { ( s x , s y ) | s x = mu x + i , s y = mu y + j ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>

然后比較已計算出的N2個SAD值來獲取本次的MBD點,執行步驟4);

步驟4)以上一步的MBD點坐標作為本次搜索的中心點,采用搜索點數為N2、步長
為1/4像素的正方形模板104進行1/4像素局部全搜索;

搜索點的集合為:

Ω 4 = { ( s x , s y ) | s x = mu x + i 4 , s y = mu y + j 4 ; - N 2 i N 2 - 1 , - N 2 j N 2 - 1 } ; ]]>

并行計算出N2個搜索點處的SAD值,并獲取最終MBD點坐標,此次獲取MBD點處
對應的坐標為最終運動矢量MV,算法執行結束。

采用統一計算設備架構編程模型CUDA在GPU平臺上并行執行。

基于kernel的啟動是異步的,本發明的設計中把運動估計的算法整合在一個
kernel函數中,這樣做能夠在視頻編碼系統中簡單、可靠地實現其它模塊與運動估計模
塊進行CPU+GPU異構并行處理,充分利用CPU與GPU資源。通過三個部分來闡述本發明
的具體實施過程:線程的組織結構、存儲模型、線程的執行流程。當前幀運動估計采用
固定的8x8分割模式(在H.264標準中執行4x4分割模式)、前向單參考幀預測、精
度閥值為32。

1.線程的組織結構:

參照圖3,它是本發明的kernel線程組織結構,每一個block執行一個當前分割塊
的運動估計,并行計算得到一個最終運動矢量。

線程網格(Grid)的x維度和y維度分別為:

gridDim.x=Frame_width/Block_width

gridDim.y=Frame_height/Block_height

式中:Frame_width和Frame_height分別為當前幀的寬度和高度;Block_width和
Block_width分別代表當前塊的寬度和高度。

在kernel函數中需要執行block總數為:

Block_num=gridDim.x*gridDim.y

block中線程的任務劃分:每一個線程對應負責每一步搜索模板中的一個候選搜索
點的計算。模板中搜索點是二維排列,為方便線程索引,block中線程結構組織為二維
形式,線程塊(block)的x維度(blockDim.x)和y維度(blockDim.y)都是8,在一
個block中共存在64個線程(2個warp)。

2.存儲模型:

參照圖4,是kernel的存儲模型。參考幀存儲在紋理存儲器(Texture?memory)
中,紋理存儲器中的數據可通過緩存加速訪問,且對大量數據的隨機訪問或非對齊訪問
也有良好的加速效果,而且紋理存儲器的鉗位尋址模式能夠支持不受限制運動矢量模
式,即MV允許指向圖像的外部,當參考像素位于被編碼圖像以外時,該像素值由它所
在行(或列)的邊緣像素值代替。運動估計執行前,主機端(Host)會把內存中待預測
的當前幀的原始數據復制到設備端(Device)的全局存儲器(Global?memory)中,然
后,block中的線程通過訪問全局存儲器來獲取當前塊所對應的64個原始像素,并將數
據放入到GPU片內的高速存儲器共享存儲器(Shared?memory)中。block中64個線程
通過紋理拾取與共享存儲器訪問操作來獲取參考像素與預測塊像素,并將計算結果中64
個SAD值合成64個SADC值(SAD值與線程的兩個內建變量threadIdx.x與threadIdx.y
的組合值),SADC值存儲于已分配的共享存儲器中。為進行線程間的通信,攜帶最小SAD
值的SADC、終止標志位會被存儲在共享存儲器中。最終通過訪問共享存儲器將運動矢量
復制到全局存儲器中。在kernel的執行過程中的背景塊判定運用了常數存儲器
(Constant?memory)。

3.線程的執行流程:

參照圖5,是本發明block中每個線程的執行流程圖,線程的執行步驟為:

Step1.block中的每一個線程(thread?0-thread?63)負責從存儲當前幀的global?
memory中取出對應的一個原始像素值pixel,并將其放入到已分配的shared?memory中,
在整個運動估計過程中,此次數據傳遞操作只需進行一次。

Step2.block中一個線程負責計算對應的一個候選搜索點處的SAD值,并對SAD
變量執行移位操作,以組合線程的兩個內建變量threadIdx.x與threadIdx.y,組合后
的新值SADC將被存放在shared?memory中相應的位置。線程在block中的組織形式讓
線程的threadIdx.x與threadIdx.y中包含了搜索點在搜索域中的位置信息。這樣做的
優勢:通過并行歸約求出最小SAD值后,不用再根據最小SAD值去標定當前最小SAD值
在搜索區域的位置。

Step3.block完成64個SADC值的計算后,利用并行歸約(Parallel?Reduction)
方法獲取攜帶最小SAD值的SADC(min_sadc)。參照圖6,是并行歸約過程的示意圖。

Step4.并行歸約過程中最后執行的線程索引號(threadID)為0的線程T(0,0),
在完成最后一次比較操作并獲取攜帶最小SAD值的SADC(min_sadc)后,將會執行下列兩
項任務:

a)取出SADC值所攜帶的Tx與Ty值,并將其存入到已分配的shared?memory中,
以方便下步局部全搜索中的線程通過訪問shared?memory來快速確定候選搜索點在紋理
參考系中的坐標。

b)根據當前步的終止條件來置位已分配的shared?memory,以便將跳轉信息通過
shared?memory廣播給所有線程,控制后續整像素精度搜索步驟是否執行(根據算法流
程,步驟1)與步驟4)是每一個block必須執行的)。

Step5.利用同步函數(__syncthreads())執行一次block中的線程同步,讓block
中的所有線程都執行到同一位置,保證T(0,0)線程生產的數據能被block中所有線程
安全、可靠共享。同時,在終止條件不成立的情況下,同步函數可以保證下一步搜索重
新可靠的并行執行。

Step6.block中的每一個線程通過shared?memory訪問跳轉信息的值,如果值非
零,則繼續執行step2~step5,否則執行算法的1/4像素精度搜索,也是最終運動矢量
的最終獲取過程,完成攜帶最小SAD值的SADC的計算后,此過程中最后執行線程T(0,
0)將會把最終運動矢量(SADC值所攜帶待的最小SAD值的坐標信息)放入到已分配的
global?memory中,作為視頻編碼系統中運動補償模塊的數據輸入。

參照圖7,它是本發明實現的一個具體實例,其中假設步驟1)、步驟2)終止條件
都不成立,點(-4,-3)、(-12,-11)、(-9,-15)分別是步驟1)、步驟2)、步驟3)
搜索的MBD點,最終得到的運動矢量為(-8.75,-15.25)。

以下對本發明的技術效果做進一步描述。

圖8是參與實測的視頻編碼的系統架構,各模塊的技術支持和參數的設置如下:

(1)當前幀匹配塊采用固定的8x8分割模式和前向單參考幀預測;

(2)幀內編碼中直接對原始信號進行整數變換、量化、掃描、熵編碼形成壓縮碼流
直接輸出;

(3)幀間編碼中的運動估計采用本發明;

(4)亮度信號采用8x8的整數變換,色度信號采用4x4的整數變化;

(5)量化模塊采用均勻量化;

(6)8x8整數變換后的亮度信號采用交叉式Zig_Zag掃描模式形成4個比特序列,4x4
整數變換后的色度信號采用Zig_Zag掃描模式;

(7)熵編碼采用H.264標準中的CAVLC編碼;

(8)采用H.264標準中的去塊濾波器方法。

測試環境配置如下:

(1)Inter(R)Pentium(R)4CPU?3.00GHZ,1.00GB;Microsoft?Windows?XP;
Microsoft?Visual?Studio?2008.

(2)Device:GeForce?GT?240;CUDA?Driver?Version:3.20;CUDA?Runtime?Version:
3.20;DRAM:512MB.

實測過程中采用統一的編碼架構、參數設置和環境配置。實驗采用了10個國際常
用標準測試序列,測試序列視頻格式為CIF、采樣格式為4:2:0的YUV,每一種測試序
列具有不同的背景分布和運動特征。包括:container、news、mother_daughter、hall、
foreman、city、football、soccer、crew、bus.

參照圖9,是分別采用FS與本發明作為測試系統的運動估計算法來編碼10個標準
測試序列,解碼后圖像的PSNR值曲線對比圖。從測試結果圖中可以發現:

a)采用本發明編碼news參考序列,其解碼后視頻的每幀圖像的PSNR值較FS算法
高。

b)采用本發明編碼參考序列container、mother_daughter、hall、foreman、city、
football、soccer、crew、bus,其解碼后視頻中部分幀的PSNR值較FS算法高,如foreman
序列的250~280幀,而部分幀的PSNR值較FS算法低,如foreman序列的180~200幀。

由此可得出下列結論:

a)背景豐富或中等程度運動的視頻序列幀,本發明所產生的PSNR值與FS算法相
當,對于部分視頻序列幀,本發明所產生的PSNR值大于FS算法。

b)場景切換或運動特征復雜的視頻序列幀,本發明所產生的PSNR值相比于FS算
法大約低0.3。

參照圖10,對于背景豐富或運動弱的視頻序列,參與運動估計的分割塊中執行完第
一步終止的分割塊占總塊數的80%以上,這大大降低了數據的計算量。

以1080P高清視頻序列為例,本發明壓縮的不必要搜索點數最小值為:

((1920*1080)/8*8)*(32*32-8*8)*0.80=24883200;

每一步壓縮比貢獻值如圖11所示,壓縮比貢獻值公式:

CRCV = Crc - Cru Cre ; ]]>

式中,CRCV為當前步的壓縮比貢獻值;Crc為當前步獲得的壓縮比值;Cru為上一
步獲得的壓縮比值;Cre為最終獲得的壓縮比值。

第一步對整個系統提供了82%以上的壓縮比貢獻值,進一步肯定了第一步局部全搜
索的價值。對于運動劇烈的視頻序列,后續步驟逐級細化運動矢量范圍,提高搜索精度,
從圖11中可以發現后續步驟為整個系統提供了很明顯的壓縮比貢獻值。

參照圖12,本發明的壓縮比在相同的PSNR值條件下很接近全搜索。尤其是對于背
景豐富或運動弱的視頻序列,甚至會超過全搜索算法。其原因是:利用局部全搜索以最
大概率判定當前分割塊是否為背景域,產生錯誤的搜索路徑達到最小概率;由于SAD值
的局限性,SAD值小的殘差塊不能絕對代表其經過變換、量化、掃描、熵編碼后,所耗
比特數最少。

圖13是采用本發明編碼不同分辨率測試序列獲得的加速比圖,紋理細節多和運動
較強視頻序列編碼中,利用本發明在單核CPU和娛樂性應用的中端GPU顯卡上,執行720P
和1080P高清運動估計耗時分別為11ms左右和21ms左右。根據以上數據,本發明能夠
解決在普通PC機上實現高清視頻序列的實時編碼過程中,運動估計模塊耗時巨大這一
瓶頸問題,具有很強的實際應用價值。

以上實施例并不構成對發明的任何限制,相關技術領域的開發人員可以不經過任何
創造性勞動,而利用本發明的技術構思,開發高效、實時的高清視頻編碼系統。

關于本文
本文標題:基于GPU并行實現的快速運動估計方法.pdf
鏈接地址:http://www.wwszu.club/p-6420738.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大