采用自适应缩放系数优化的块匹配运动估计-宋传鸣，闫小红，葛明博，王相海，尹宝才.pdf

上善若水

170

18页

0次

2022-05-24

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2020,31(11):3603−3620 [doi: 10.13 328/j.cnki.jos.005864] http://www.jos.org.cn

采用自适应缩放系数优化的块匹配运动估计

∗

宋传鸣

1,2, 3

闫小红

葛明博

王相海

尹宝才

(辽宁师范大学计算机与信息技术学院,辽宁大连 116029)

(大连理工大学计算机科学与技术学院,辽宁大连 116024)

(计算机软件新技术国家重点实验室(南京大学),江苏南京 210023)

通讯作者: 宋传鸣, E-mail: chmsong@lnnu.edu.cn

摘要: 尽管基于平移模型的快速块匹配运动估计算法在一定程度上解决了高计算量的问题,但却是以牺牲运动

补偿质量为代价的,而高阶运动模型尚存在计算量高、收敛不稳定的不足.通过实验统计发现,视频中约有 56.21%的

块包含缩放运动,进而得出缩放运动是除平移运动外最主要的视频运动形式的结论.进而借助双线性插值,在传统的

块平移模型中引进一个缩放系数,将运动补偿误差表示为该缩放系数的一元二次函数,利用韦达定理推导出 1D 缩

放运动下最佳缩放系数的计算方法,并将其进一步推广到 2D 等比例缩放运动的情况下.在此基础上,提出了一种采

用自适应缩放系数优化的快速块匹配运动估计算法.该算法以菱形搜索计算平移矢量,再用自适应缩放系数确定待

预测块的最佳匹配块.在 33 个标准测试视频上的实验结果表明,与基于平移模型的块匹配全搜索和快速菱形搜索相

比,该算法的平均运动补偿峰值信噪比(peak signal-to-noise ratio,简称 PSNR)分别提高了 0.11dB 和 0.64dB,计算量比

全搜索下降了 96.02%,略高于菱形搜索;与基于缩放模型的运动估计相比,该算法的平均峰值信噪比较之 3D 全搜索

下降了 0.62dB,但是比快速 3D 菱形搜索提高了 0.008dB,而计算量仅分别为两者的 0.11%和 3.86%,并且无需向解码

端传输缩放矢量,能够实现编、解码端的自同步,不会增加边信息的码流开销.此外,该自适应缩放系数计算方法还可

与菱形搜索以外的其他快速块匹配运动估计相结合,提高其运动补偿质量.

关键词: 视频编码;运动估计;块匹配;缩

放模型;自适应缩放系数

中图法分类号: TP391

中文引用格式: 宋传鸣,闫小红,葛明博,王相海,尹宝才.采用自适应缩放系数优化的块匹配运动估计.软件学报,2020,31(11):

3603−3620. http ://www.jos.org.cn/1000-9825/5864.htm

英文引用格式: Song CM, Yan XH, Ge MB, Wang XH, Yin BC. Optimized block-matching motion estimation using adaptive

zoom coefficient. Ruan Jian Xue Bao/Journal of Software, 2020,31(11):3603−3620 (in Chinese). http://www.jos.org.cn/1000 -

9825/5864.htm

Optimize d Block -matc hing Motio n Est imation Usin g Adaptive Zoom Co effic i ent

SONG Chuan-Mi ng

1,2,3

, YAN Xiao-Hong

, GE Ming-Bo

, WANG Xiang-Hai

, YIN Bao-Cai

(School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, China)

(School of Computer Science and Technology, Dalian University o f Technology, Dalian 116024, Chin a)

(State Key Laboratory for Novel Soft ware Technology ( Nanjing Univ ersity), Nanjing 210023, China)

∗ 基金项目: 国家自然科学基金(61402214, 41671439, 61632006); 辽宁省自然科学基金(20180550570); 大连市青年科技之星支

持计划(2015R069); 计算机软件新技术国家重点实验室(南京大学)开放课题(KFKT2018B07); 辽宁省高等学校创新团队支持计划

(LT2017013); 辽宁省高等学校创新人才支持计划([2018]478-64)

Foundation item: National Natural Science Foundation of China (61402214, 41671439, 61632006); Natural Science Foundation of

Liaoning Province (20180550570); Program for Youth Science and Technology Star of Dalian City (2015R069); Open Foundation of State

Key Laboratory for Novel Software Technology (Nanjing Universit y) (KFKT2018B07); Programfor Liaoning Innovative Research Team

inUniversity (LT2017013); Program for Liaoning Excellent Talen ts in University ([2018]478-64)

收稿时间: 2018-10-27; 修改时间: 2019-02-25; 采用时间: 2019-05-12

3604

Journal of Software 软件学报 Vol.31, No.11, November 2020

Abstra ct : Fas t block-wise motion estimation algorithm based on translational model solves the high computational complexity issue to

some extent, but it sacrifices the motion compensation quality, whilst the higher-order motion model still exhibits the problems of

computationally inefficiency and unstable convergence. Through a number of experiments, it is found that about 56.21% of the video

blocks contain zoom motion, thus a conclusion is drawn that zoom motion is one of the most important motion forms in video except for

the translational motion. Therefore, a zoom coefficient is introduced into the conventional block-wise translational model by bilinear

interpolation, and model the motion-compensated error into a quadratic function with regard to the zoom coefficient. Subsequently, the

approach is derived to compute the optimal zoom coefficient under the condition of 1D zoom motion through Vieta’s theorem, which is

further extended to the condition of 2D zoom motion with equal proportion. Based on the abo ve, a fast block-matching motion estimation

algorithm is presented and is optimized by the adaptive zoom coefficient. It first uses the diamond search (DS) to compute the

translational motion vector, and then determines an optimal matching block for the block to be predicted with the adaptive zoom

coefficient. Experimental results carried out on 33 standard test video sequences show ed that the proposed algorithm gains separately 0.11

dB and 0.64 dB higher motion-compensated peak signal-to-noise ratio (PSNR) than those of the full search (FS) and the DS based on

block-wise translational mod el. And its computational co mplexity is 96.02% lower th an that of the FS, slightl y higher than th at of the DS.

Compared with the motion esti mation based on the zoom model, the average PSNR of the proposed algorithm is 0.62 dB lower than that

of 3D full search, but 0.008 dB high er than that of fast 3D diamond s earch. And th e computational complexity on ly amounts to 0.11% and

3.86% of the 3D full search and the 3D diamond search, respectively. Meanwhile, the proposed algorithm can realize the self-

synchronization between the encoder and decoder without tr ansmitting the zoom vectors, so it does not increase the overh ead of the side

information. Additionally, the proposed adaptive zoom coefficient computation can also be combined with state-of-art fast block-wise

motion estimation algorith ms other than th e diamond search, i mproving th eir motion-comp ensation qualit y.

Key words: vid eo coding; motion estimation; block matching; zoom mod el; adaptive zoom coefficient

运动估计是 AV S 、H.26 5/ HE VC 和 MPEG 等视频编码器所采用的一种时间域差分预测方法,它为“差分预

测+变换”的闭环反馈编码架构带来了最主要的编码增益

[1,2]

.然而文献[1,3,4]在对各个编码环节的计算量进行

定量分析后发现,运动估计环节的计算开销占整个编码器所需计算资源的 40%以上.若视频编码器开启了可变

块尺寸的 1/8 像素运动估计、自适应运动矢量预测等高级模式,运动估计甚至会耗费编码器全部计算资源的

80%.在这种情况下,为了达到更加合理的码率-失真-计算复杂度(rate -distort ion-c omplexity,简称 R-D-C)性能,现

有视频编码标准均采用了基于平移模型的块匹配算法来去除由物体平移运动所产生的时间域冗余,并出现了 7

类快速视频运动估计算法

[5]

(1) 基于候选向量下采样的运动估计:按照某种原则(如中心偏置原则),选择搜索窗口中的少数运动向量

作为候选向量集合, 进而确定补偿误差最小的候选向量作为运动向量, 如 UMHexagonS

[6]

、

TZSearch

[7]

、EPZS

[8]

和抛物线搜索

[9]

等.

(2) 基于像素下采样的运动估计:采用某种采样矩阵(如层次采样矩阵

[10,11]

、梅花形采样矩阵

[12]

和自适应

采样矩阵

[13]

)将待匹配的宏块进行下采样,进而在搜索窗口中,为尺寸缩小了的待预测宏块计算每个

候选向量的补偿误差,得到最佳运动向量.

(3) 基于像素预排序的运动估计:在计算待匹配宏块的运动补偿误差时,采用一定的预测策略确定宏块中

可能产生较大帧差的像素,并优先统计其对应的运动补偿误差.若累积误差超过当前最优向量的预测

误差,则可排除该候选向量成为最佳运动向量的可能,例如 PDS 算法

[14,15]

等.

(4) 基于低复杂度匹配函数的运动估计:采用异或、比较、取绝对值等运算替代均方差函数的减法、乘

法、平方根操作,从而减少计算运动补偿误差所需要的 CPU 时钟周期数及硬件开销,如文献[16,17]等.

(5) 基于低比特深度像素的运动估计:采用某种位深度映射函数,将具有较高位深(如 12bit 和 8bit)的像素

转换为低位深的像素,进而将多个像素的低位深表示合并到 1 个机器字中.若与第(4)类的低复杂度匹

配函数联合使用,则能达到 1 次操作即可求解多个像素的补偿误差的目的,如 1bit 运动估计

[18]

和 2bit

运动估计

[19,20]

等.

(6) 基于散列表的运动估计:利用散列函数将待匹配块的像素值映射为一个散列值,再借助散列表查找最

佳匹配块

[21−23]

,从而避免了匹配误差的重复计算,可将运动估计的时间复杂度由平方阶降低到线性

of 18

免费下载

软件学报计算机技术

关注

评论