稀疏统计二次Renyi 熵的运动估计匹配准则

邓志超，汪同庆

(重庆大学光电技术及系统教育部重点实验室，重庆 400044)

1 概述

在数字视频压缩编码领域，已经先后形成了H.261，MPEG -1，MPEG -2，H.263，MPEG -4，H.264/AVC等一系列视频编码标准［1-2］，然而由于编码标准的复杂度越来越高，这就对编码时间提出了更高的要求。基于此，运动估计［3］作为视频编码的核心技术就显得尤为重要。块匹配［4］运动估计算法由于原理简单和易于软硬件实现而被广泛应用，其中匹配准则和搜索模式作为块匹配运动估计的两大重要因素一直是人们研究的热点［5］。匹配准则通常是描述当前图像块与参考图像块之间近似程度的函数，通过分析，运动估计的准确性很大程度上依赖于块匹配过程中选用的匹配准则，一个能够快速精确地描述块匹配程度的匹配准则将会极大地改善算法性能，所以对匹配准则的研究与改进具有十分重要的意义。尽管如此，以往的研究重点都集中在搜索模式上，对匹配准则却没有得到有效的关注，大部分直接采用传统匹配准则如绝对误差和函数(Sum of Absolute Difference，SAD)和均方误差函数(Mean Square Error，MSE)作为搜索模式的匹配准则［6］。

针对传统匹配准则描述块匹配精度不高的不足，本文提出一种稀疏统计二次Renyi 熵［7-8］(Quadratic Renyi's Entropy，QRE)的运动估计匹配准则。该准则发挥了二次Renyi 熵在评价残差图像的剩余信息量较为准确的优势，在计算QRE 时引入统计直方图来计算概率密度函数，并结合基于梯度的图像质量评价和运动矢量中心偏离特性，对直方图的统计进行稀疏化。实验采用了全搜索算法作为搜索模式［9］，分别对SAD，MSE 和QRE 匹配准则进行了对比分析，并针对QRE 匹配准则需要进行乘法运算的不足，进一步将QRE 中引入的统计直方图进行稀疏优化，并将稀疏前后的峰值信噪比［10］和乘法运算量进行了对比。

2 QRE 匹配准则

1948 年，克劳德·香农提出了用来表示信息内容大小的信息熵，即香农熵［8］。用香农熵来表示帧间运动估计中残差图像块的信息量是最为准确的。数学家Renyi 又提出了意义更为广泛的Renyi 熵。在不知道概率密度函数的前提下，可以通过非参数法即带核函数的Parzen 窗来估计连续变量的二次Renyi 熵。本文为了简化匹配函数，提高运算效率，也引入了二次Renyi 熵。如果能够保证当前图像块与参考帧图像块相减之后，得到的残差图像块的二次Renyi 熵最小，那么这两个图像块的内容最接近，经过编码之后的信息冗余也就越少。

2.1 Renyi 熵

给定一个随机变量e，它的Renyi 熵可以定义为:

其中，f(e)为变量e 的概率密度函数。

在式(1)中，当α→1 时，根据洛比达法则，α 次Renyi 熵就收敛为香农熵。

当α=2 时，随机变量e 的Renyi 熵就成为二次Renyi 熵，即:

为了进一步简化匹配函数，选用式(3)作为匹配准则，则有:

定义变量H，使得:

其中，变量e 对应的是残差图像块中任意像素点的亮度值或色度值。当变量e 满足式(5)时，残差图像块的二次Renyi 熵就最小，当前图像块与参考图像块就是最佳匹配块。

2.2 统计直方图

由于残差图像块每个像素点亮度与色度的取值都是有限个离散值，其概率密度函数也是离散的。为了有效地计算式(7)所表示的匹配函数，引入了统计直方图。如果视频图像的各个分量有I 个不同的取值，那么可以构造出组数为I 的统计直方图。构造统计直方图并求得匹配函数值的具体步骤如下:

(1)将残差图像块作为样本，统计各个组区间的频数γi，0 ＜i ＜I。

(2)根据频数求各个组区间的频率fi:

(3)将每个组区间的频率代入式(5)可得到匹配函数值。

根据各个组区间的频率，匹配函数可以写为:

基于二次Renyi 熵的快速搜索算法整体流程如下:

(1)确定图像块分割的大小和搜索窗口大小，开始菱形搜索算法。

(2)将当前图像块与参考图像块相减，得到残差图像块。

(3)针对残差图像块色彩空间的每个分量，构造统计直方图并根据式(7)求得基于二次Renyi 熵的匹配函数值。

(4)将当前得到的值与保存的最小匹配函数值比较，如果小于则将当前值保存。或者当前值小于某一阈值时，结束搜索，完成当前图像块的匹配。

(5)判断是否完成搜索任务。如果完成，结束当前图像块的匹配搜索;否则重复步骤(1)。

2.3 常用匹配准则

为了更为清晰地体现出所提出匹配准则的不同之处，以便作对比，下面将对几种常用的匹配准则作简要介绍。

SAD 匹配准则定义如下:

MSE 匹配准则定义如下:

上述两式中，(p，q)表示运动向量;D(x，y)表示当前图像块;DR(x，y)表示参考帧中的图像块;M，N分别表示图像块的宽度与高度;(x，y)表示运动向量。当SAD(p，q)或者MSE(p，q)取得最小值时即为最优匹配运动向量(p，q)。SAD 匹配准则由于不需要作乘法运算，实现简单方便，因此使用广泛。

3 QRE 的稀疏统计

QRE 是通过细节反映数据大小波动的较好体现，用当前块与参考块像素差值的二次Renyi 熵衡量前后改变情况，既能微观地反映图像误差较大区域，即局部误差显著区域，又能宏观地反映整体误差情况。然而，与SAD 匹配准则相比，QRE 的缺点在于需要进行乘法运算，需要耗费更多的运算资源，因此，对QRE 匹配准则进行优化显得很有必要。

3.1 统计直方图区间的线性化

为了在乘法运算量上得到改进，结合人眼在实际观察中基于梯度的图像质量评价方法［11］，可以对统计直方图中各个区间作进一步的稀疏处理［12］，如图1 所示。区间可设置为2，4，8，2n等，即统计直方图区间的线性化，当然稀疏程度要限定在一定的范围内以确保图像梯度结构评价方法的有效性。由于灰度图像的像素值分布在区间(0，255)，因此残差图像灰度图像的像素值必将分布在区间(-255，255)，每当进行一次区间稀疏处理，必将减少与之相应的乘法运算量。

图1 统计直方图线性稀疏处理

3.2 统计直方图区间的阈值分类

以上简单稀疏处理从理论上来说可以减少乘法运算量，但是随着稀疏程度的增加，误差会加剧。基于此，根据运动矢量中心偏离特性［13］，残差图像的像素差值理论上将集中在中间区域，即零点附近区域。因此，结合以上稀疏处理的方法，可以设定一个阈值T0，将(-T0，T0)区域内作轻度稀疏处理或不作稀疏处理，将其他区域作重度稀疏处理，如图2 所示，即统计直方图区间的阈值分类［14］稀疏处理。这样不仅可以减少乘法运算量，同时也解决了因为稀疏化带来的误差加剧的问题。

图2 统计直方图阈值分类稀疏处理

4 实验结果与分析

本文的实验工作平台参数如下:处理器为Intel Pentium4 2.40 GHz，内存2 GB，操作系统为Ubuntu 10.04(系统内核:Linux 2.6.32-45-generic)，编译环境为GNU/GCC4.3，代码编辑环境为Vim+Cscope。

为了全面地比较各种匹配函数之间的性能差异，选取了5 组在运动幅度、运动方向和运动物体数量与大小上各不相同的测试视频序列作为实验数据对象，即flower，container，coastguard，bus 和football，分辨率均为CIF(352 ×288 像素)。这5 组视频序列都存在着不同物体不同的运动方式，其中，flower 序列主要表现为水平运动，主要有相机的移动与人物的行走，运动物体较小，运动幅度较大;container 序列主要表现的也是水平运动，但运动物体较大，运动幅度较小，主要是大货轮的运动;coastguard 序列主要体现在水平方向上海岸警卫汽艇和游艇两者的运动，汽艇运动幅度较大，游艇运动幅度较小;bus 序列主要体现为水平方向上的汽车移动，且运动幅度相对较大;football 序列主要表现为垂直与水平方向上的剧烈运动，能够更好地测试匹配准则对于复杂运动的适应能力。同时由于标准视频序列中缺少在垂直方向上运动变化，因此本文拍摄了2 段视频，这2 段视频序列的特点是图像中存在垂直方向上的不同幅度的运动，自拍2 较自拍1 运动幅度大。

实验将每帧图像大小依据常用区分模式，分成为16 ×16 像素互不重叠的图像块，以第i-2 帧图像作为第i 帧的参考帧，分别根据不同的匹配准则来搜索最佳匹配块，并对运动估计后的每帧图像进行运动补偿，计算出补偿帧与当前帧的PSNR 值。

为了描述整体的匹配效果，表1 给出了在相同的输出码率情况下，各个视频前30 帧图像在不同的匹配准则下的平均PSNR 值，搜索方式为全搜索。PSNR 值越大，表示匹配精度就越高，完成运动估计的效果也就越好。匹配准则选取SAD，MSE，QRE 作为对比，ΔPSNR 表示与SAD 匹配准则的PSNR 值之差。

表1 视频序列PSNR 值对比 dB

从实验结果可以看出，针对以上各种运动方式的视频序列，采用不同的匹配准则所得到的结果存在差异。从整体匹配效果来看，QRE 匹配准则所得到的平均PSNR 值最高，效果明显优于SAD 与QRE匹配准则，验证了第2 节的理论。对于container 和自拍1 视频序列，可以看出，QRE 准则对于运动幅度小的情况优势不明显，从其他视频序列看，QRE 对于水平、垂直或其他方向运动幅度大的视频序列，优势较为明显。

表2 考察了统计直方图线形稀疏处理后运动估计的效果，在稀疏处理的过程中，分别将区间宽度设置为2 的整数倍，直至ΔPSNR 值为负数(ΔPSNR 表示与SAD 匹配准则的PSNR 值之差)，即运动估计效果劣于SAD 准则，同时对各种情况下乘法计算量减少的百分比作了统计。从得到的数据结果来看，随着稀疏化程度的增强，乘法运算量急剧下降，但PSNR 值也随之下降，与前文的理论分析结果相符。

表3 考察了统计直方图阈值分类稀疏处理后运动估计的效果，在稀疏处理的过程中，通过对实验对象标准视频序列和自拍两组序列的综合评定，设定阈值为16，分别将阈值区间内与阈值区间以外区域的区间宽度设置为4 和32，这样阈值区间内外分别有8 个和30 个区间，总共38 个区间，相对线性化稀疏处理方法，总体上在保证PSNR 值高于SAD 匹配准则的基础上，使得乘法运算量进一步减少，减少量可以达到80%以上。对于container 视频序列，由于其运动物体大，运动幅度较小，可以看出，基于QRE匹配准则对运动幅度大的视频序列效果明显。

表2 统计直方图线性稀疏处理结果

表3 统计直方图阈值分类稀疏处理结果

5 结束语

本文将二次Renyi 熵引入到运动估计匹配准则中，并采用稀疏统计的方法对直方图的进行统计，提出了一种稀疏统计二次Renyi 熵的运动估计匹配准则。从匹配乘法运算量和匹配效果出发，依据基于梯度的图像质量评价和运动矢量中心偏离特性，通过对统计直方图每个区间的线性全局稀疏、线性区域化稀疏以及非线性阈值化稀疏，不断完善匹配准则的匹配方式。实验结果表明，该匹配准则对运动剧烈视频序列的运动估计效果明显，恢复的图像质量优于SAD 匹配准则。从实验的数据来看，稀疏区间的大小和阈值的设定决定了匹配的效果，下一步工作需要对稀疏区间的大小和整个区间的阈值设定作进一步研究。

［1］Vani R，Sangeetha M.Survey on H.64 Standard［M］.Berlin，Germany:Springer，2012.

［2］Richardson I E.The H.264 Advanced Video Compression Standard［M］.［S.l.］:John Wiley ＆ Sons，2011.

［3］Dhamande C S，Bhalge P A.Overview of Motion Estimation in Video Compression［J］.International Journal of Scientific ＆ Engineering Research，2013，4(6):116-120.

［4］Barjatya A.BlockMatching Algorithms for Motion Estimation［J］.IEEE Transactions Evolution Computation，2004，8(3):225-239.

［5］HuangYuwen，Chen Chingye，Cai Chenhan，et al.Survey on Block Matching Motion Estimation Algorithms and Architectures with New Results［J］.Journal of VLSI Signal Processing，2006，42(3):297-320.

［6］YuFei，Hui Mei，Han Wei，et al.The Application of Improved Block-matching Method and Block Search Method for the Image Motion Estimation［J］.Optics Communications，2010，283(23):4619-4625.

［7］Ramachandran G，Krishnan V，Wu Dapeng，et al.A Model-based Adaptive Motion Estimation Scheme Using Renyi's Entroy for Wireless Video［J］.Journal of Visual Communication and Image Representation，2005，16:432-449.

［8］ErdogmusD，Principe J C.Comparion of Entropy and Mean Square Error Criterion in Adaptive System Training Using Higher Order Statistics［C］//Proc.of International Workshop on Independent Component Analysis and Signal Separation.Helsinki，Finland:［s.n.］，2000:75-80.

［9］Luo Jun，Peng Jiaxin.An Unsymmetrical Diamond Search Algorithm for H.264/AVC Motion Estimation［C］//Proc.of Conference on Image and Graphics Technologies.Berlin，Germany:［s.n.］，2013:54-65.

［10］Hore A，Ziou D.Image Quality Metrics:PSNR vs.SSIM［C］//Proc.of the 20th International Conference on Pattern Recognition.Istanbul，Turkey:［s.n.］，2010:2366-2369.

［11］Zhou Wang，Bovik A C，Simoncelli E P.Image Quality Assessment:From Error Visibility to Structual Similarity［J］.IEEE Transactions on Image Processing，2004，13(4):600-612.

［12］崔 琛，沙正虎，李 莉，等.基于SURE 估计的图像块稀疏收缩去噪算法［J］.计算机工程，2012，38(23):231-235.

［13］倪 伟，郭宝龙，丁贵广.基于运动矢量场和方向自适应的快速运动估计算法［J］.电子与信息学报，2006，28(12):2277-2282.

［14］Nafis U K，Arya K V，Pattanaik M.Histogram Statistics Based Variance Controlled Adaptive Threshold in Anisotropic Diffusion for Low Contrast Image Enhancement［J］.Signal Processing，2013，93 (6):1684-1693.