太阳城集团

  • / 24
  • 下载费用:30 金币  

基于GPU并行实现的快速运动估计方法.pdf

摘要
申请专利号:

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 并行 实现 快速 运动 估计 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:基于GPU并行实现的快速运动估计方法.pdf
链接地址:http://zh228.com/p-6420738.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');