运动估计是一项去除视频冗余的时间域预测技术，为H.264和高效率视频编码(high efficiency video coding, HEVC)等编码标准贡献了大部分的性能提升[1-2].提高运动估计的效率，使其搜索过程更加健壮和高效不仅是视频编码领域的热点问题，也是进一步改善视频编码效率的重要途径之一.

多年来，视频编码标准始终采用了仅能刻画水平、竖直等平移运动的块匹配算法，可是块平移模型既无法有效预测由物体旋转、缩放、变形和摄像机运动产生的非刚性复合运动，又不能准确表示具有复杂形状的运动区域，导致在运动物体边缘产生大幅值的预测残差.并且，随着块尺寸的减小和运动向量精度的提高，用于编码运动向量、块划分方式的码流开销以及各种软硬件资源开销的增加幅度甚至超过了率失真性能的提升幅度[2].故此，研究能有效表示复杂运动场的运动模型及相应的帧间运动估计方法，对下一代视频编码效率的提升具有重要意义[3-6].

鉴于平移运动模型的不足，研究人员将高阶运动模型引入运动估计，利用高阶函数产生1个或多个扭曲的参考帧实现了更高质量的运动补偿.依据模型显式表现形式的不同，本文将这些运动估计补偿算法划分为4类：1)基于网格模型的运动估计[7-9]；2)基于多项式模型的运动估计[10-12]；3)基于缩放模型的运动估计[13-15]；4)基于弹性模型的运动估计[16-20].其中，算法1对编码率失真的优化较为困难[21]；算法2的参数偏多，搜索复杂度高，且对局部运动的刻画能力不足；算法3无法有效描述物体的旋转、错切和局部变形运动；算法4可刻画物体的平移、错切和扭曲运动，既能表示全局和局部运动，又可通过调整模型参数个数来控制运动估计的计算复杂度.因此，对比各类高阶运动模型并综合现有研究结论，弹性运动模型是一种表示复杂运动场的高效模型.

本文首先简要介绍弹性运动估计的相关工作，然后针对其存在的计算量高的问题，引进一种视频帧的2 b深度像素表示方法，进而提出低位深度的弹性运动模型，并从模型的快速计算和自适应步长选取策略2个方面展开论述，提出一种采用2 b深度像素加速的弹性运动估计算法.本文的主要贡献有3个方面：

1) 利用Prewitt梯度算子和梯度模长的均值、标准差提取视频帧的纹理信息，设计了一种将像素从8 b深度向2 b深度进行变换的方法，可避免视频帧在像素深度降采样后出现大面积的光滑区域；

2) 引进基于位操作的矩阵乘法和基于比较操作的偏导运算，提出了一种基于2 b深度像素的弹性运动估计模型，并根据8 b乘法运算的符号表，进一步给出求解该模型的简化高斯-牛顿法，其优点在于用异或操作替代乘法运算，且无需反复计算黑塞矩阵及其逆矩阵，计算复杂度明显降低；

3) 根据运动补偿误差的分布特性，利用1阶线性逼近策略，推导出高斯-牛顿法的自适应步长与弹性运动向量增量、运动补偿误差之间的函数关系，进而得出其近似计算方法，保证了算法具有较稳定的收敛性.

1 相关工作

弹性运动模型采用离散余弦函数、小波函数和样条函数等调和函数来描述物体的非刚性运动，最初主要应用于医学影像配准、物体跟踪等领域.文献[16-17]将弹性模型引进视频编码中，提出了基于弹性模型的运动估计，在相同码率下获得了比块平移运动估计高出0.70 dB的运动补偿峰值信噪比(peak signal-to-noise ratio, PSNR)；文献[18]的结论显示，弹性运动模型可将H.265的输出码率降低3%～12%；文献[19-20,22]则通过优化弹性模型的求解方法取得了更加理想的预测效率，将传统弹性运动估计的平均PSNR又提高了1.42～1.77 dB，比基于块平移模型的全搜索算法高出1.73～2.54 dB.然而，上述文献均采用高斯-牛顿法来迭代地求解弹性运动模型，在每次迭代过程中需计算偏导数、黑塞矩阵、逆矩阵和矩阵乘法，其计算复杂度甚至高于块平移模型的全搜索(full search, FS).尽管经过文献[19-20,22]改进后的弹性运动估计仅需2～3次迭代即可达到块匹配全搜索的补偿质量，可是仍然无法避免黑塞矩阵及其逆矩阵等的反复求解，计算量约为FS的25.62%，高于菱形搜索(diamond search, DS)和测试域搜索(test zone search, TZSearch)等快速块匹配运动估计.

为了增强高阶运动模型求解的实时性，文献[23]提出一种1 b深度像素的高斯-牛顿迭代法，并将其应用到基于6-参数仿射变换的图像配准中.然而，由于1 b匹配误差曲面的梯度较小，该算法至少需迭代50次才能缓慢趋于收敛，计算复杂度并未显著降低.文献[24-25]进一步将文献[23]的思路推广到2 b深度像素，实现了一种基于仿射模型的2 b全局运动估计.可是，为节省逆矩阵的计算量，该方法要求保持迭代步长固定不变，无法实现自适应，且只能朝着单一方向进行迭代.而文献[19-20,22]的研究结论却表明，高斯-牛顿法对初始迭代步长和迭代方向均较为敏感，这就不可避免地导致文献[24-25]在大多数情况下都无法求解出全局最优解.同时，文献[23-25]均利用8 b深度表示的图像计算1阶偏导，再结合经过位截断后的低位深度图像得到匹配误差和最速下降方向.由于低位深像素的梯度往往不同于8 b深度像素，两者混合作用很难保证下降方向的准确性；另一方面，文献[26-27]指出，匹配误差往往产生在较低的位，直接截断低位无法有效保留图像的边缘特征，还将使位于最佳匹配块周围的一定区域内的所有像素被量化成相同值，以致失去对最优向量的判断能力.综合来看，无论是运动估计的精度，抑或收敛速度，文献[23-25]的方法尚不够令人满意，且只能求解仿射模型下的运动向量.因此，研究更加有效的、基于低位深度像素的高斯-牛顿法和弹性运动估计，有助于以弹性模型为代表的高阶运动估计走向实用，对新一代视频编码的发展具有一定意义.从本文作者所掌握的文献来看，目前尚鲜见相关研究.

本文提出的2 b深度像素的弹性运动估计，利用梯度均值和标准差提取图像的边缘和纹理特征，将像素从8 b深度向2 b深度进行转换，并实现了基于位操作的快速高斯-牛顿优化求解.不仅解决了初始迭代步长的自适应选取和迭代方向的多样性，也使得1阶偏导与最速下降方向均在2 b深度像素域进行统一计算，从而保证基于低位深像素的弹性运动估计精度和收敛速度.

2 弹性运动模型及其高斯-牛顿求解方法

为便于下文工作的论述，本节首先介绍弹性运动模型的定义，再给出求解弹性运动向量的高斯-牛顿方法.

2.1 弹性运动模型的基本定义

视频运动估计的目标是在参考帧的某个搜索窗口内，为当前待预测块I(尺寸为B×B像素)搜索到1个运动向量，使得I与其最佳匹配块R之间的误差平方和(sum of squared difference, SSD )最小，即：

w(yij,m))-I(xij,yij)]2},

(1)

其中，xij和yij分别表示当前待预测块中i行j列像素的x坐标和y坐标，m表示某种运动模型w下的运动向量.对于弹性运动模型，采用弹性基函数φk建立待预测块中每个像素的坐标及其匹配像素的坐标映射，其定义为

(2)

(3)

其中，p表示运动矢量的分量数目，mk表示m的第k个分量，且φk为离散余弦函数：

φk(i,j)=φk+p2(i,j)=

(4)

其中，

2.2 弹性运动模型的高斯-牛顿解法

为了获得弹性运动向量m，文献[16-20]均采用了高斯-牛顿法进行求解，主要思想是对匹配误差函数进行线性逼近，再通过反复迭代求出极小值.具体地，假设当前迭代点为m，并令(xij,yij)处的预测误差为eij(m)=R(w(xij,m),w(yij,m))-I(xij,yij)，则eij(m)可用其在m处的1阶泰勒展开式近似表示，即：

(5)

其中，表示eij(m)在m处的1阶偏导数将式(5)代入式(1)，则有

(6)

为取得式(6)的最小值，将其对Δm取导并令导数为0，整理后得到：

(7)

令

(8)

(9)

显然，H是1个p×p阶的黑塞矩阵，并且根据求导的链式法则和eij(m)、式(2)、式(3)的定义，有：

(10)

其中，和分别表示匹配块沿着水平和竖直方向的梯度分量，是雅克比矩阵，并且φk(i,j)，k∈[1,p2].于是，有Δm=H-1b，进而得到更新后的弹性运动向量m：m←m+Δm.

图1给出了基于高斯-牛顿法的弹性运动估计过程，其中T表示迭代次数，Tmin表示迭代的条件阈值，表示向量的模长.

3 基于Prewitt梯度算子的2 b变换

由2.2节可见，弹性运动模型的高斯-牛顿解法需反复计算偏导数、黑塞矩阵、逆矩阵和矩阵乘法，计算量明显高于块平移模型的全搜索.为此，我们引进基于低位深度像素的策略，将像素从8 b深度降采样为2 b深度，以达到降低计算开销的目的.

3.1 本文的2 b变换算法

将像素从8 b深度转换至2 b深度，势必会丢失视频帧的部分信息，尤其是细腻的纹理细节，产生大面积的平滑区域，这是导致基于低位截断的低位深度像素运动估计出现性能下降的重要原因[26-27].故此，在像素深度变换过程中尽可能保持视频的纹理特征，对于衡量像素深度降采样的有效性、保证运动估计精度具有重要意义.为了达到这一目的，我们首先通过Prewitt算子计算待预测帧的梯度；其次，假定像素梯度的模长服从正态分布，若用均值μC和标准差σC将概率密度划分为4个区间，则知梯度模长位于区间(-∞,μC-0.68σC)，[μC-0.68σC,μC)，[μC,μC+0.68σC)，[μC+0.68σC,+∞)的概率均近似等于0.25，根据这一规律，本文以像素块为单位，将每个像素处的边缘和纹理强度平均分为弱、较弱、较强、强4个等级，从而实现将像素(x,y)的深度从8 b变换为2 b：

(11)

其中，表示块C中(x,y)处的梯度模长，C′(x,y)表示像素(x,y)经过变换后的2 b深度表示.

本文提出的基于梯度均值和标准差的2 b变换过程如图2所示：

图3给出了分别采用低位截断方法[28]、基于亮度均值和方差的2 b变换方法[29]，以及本文方法处理Football序列和Foreman序列第2帧的结果.从图3不难发现，基于低位截断的变换方法损失了Football序列包含的复杂背景纹理(图3(b))；虽然基于亮度均值和方差的2 b变换方法[29]在一定程度上避免了位截断方法的不足，可是未充分考虑正态分布的特点，选用亮度均值μ、标准差σ及其线性组合μ-σ和μ+σ作为变换阈值，这将导致约有68%的像素会从8 b深度被降采样为00和01，产生较大面积的平滑区，如Football的运动员身体和Foreman的脸部区域中大量像素被转换为相同值，易使运动估计陷入局部最优，甚至失去对最优向量的判断能力；而本文方法无论在复杂的背景纹理区，还是在平滑的渐变区(如Foreman的脸部)，均能保持适当的图像细节，进而形成能有效区分错误运动向量的特征.

3.2 2 b深度像素的匹配误差曲面的特点

由于位深度变换过程难免丢失少量纹理细节，会出现2种情况：1)当一定区域内的像素均被变换为相同值时，像素值的变化率降低、自相关系数增大.这样，当待预测块在该区域内搜寻最佳匹配块时，匹配误差的变化趋于平缓.我们称这样的区域为“曲面平滑区域”.2)在2个曲面平滑区的交界线两侧，像素值被变换为不同值，像素值的变化率提高，而自相关系数减小.对2 b深度的像素而言，由于匹配误差的值域显著小于8 b深度像素，即使匹配误差增加1，也意味着25%的增幅，这相当于8 b误差增幅的32倍.因此，在交界区域中不同候选向量的运动补偿误差易产生较大变化.2 b匹配误差曲面的这种“区域内平滑、区域间锐化”的分布特点，会使其呈现更加明显的单调性和梯度变化.

图4给出了Stefan序列第2帧内左上角坐标为(144,112)的块和Football序列第2帧内左上角坐标为(176,176)的块，分别进行基于8 b深度像素和基于本文2 b深度像素的整数精度全搜索后得到的匹配误差曲面，搜索窗口为33×33.对比可见：首先，8 b深度像素的匹配误差曲面(图4(a)(c))较之2 b深度像素的匹配误差曲面(图4(b)(d))具有更强的波动性，局部极值点也更多，易导致典型的快速搜索陷入局部最优.其次，在曲面平滑区域，8 b深度像素的匹配误差的变化幅度和频率均大于2 b深度像素的匹配误差；而在极值点的一定邻域以及2个局部极值区域的交界，8 b深度像素匹配误差的变化趋势却较平滑，其数值梯度和衰减速度明显小于2 b深度像素的匹配误差曲面.这不仅印证了上一段的理论分析，也充分说明2 b深度像素的运动估计陷入局部最优的概率更小，且能通过梯度下降策略以更快的速度向全局最优点收敛，尤其是当搜索初始点较为准确、位于全局极值点的单调区间时，从而有利于提高运动补偿精度和运动估计效率.

4 低位深度的弹性运动模型

传统高斯-牛顿法的每次迭代都需要计算待预测块的偏导数、黑塞矩阵、逆矩阵、矩阵乘法和运动补偿误差等，其计算复杂度达到了max{O(p3),O(p2B2)}.若能降低反复执行上述操作的运算量，则可进一步改善弹性运动估计补偿的效率.同时，经过第3节的处理，视频帧的全部像素已由8 b深度降采样到2 b深度，若继续延用传统高斯-牛顿法中基于8 b整数的偏导、矩阵乘法等运算，则达不到通过精度下采样来提高计算效率的目的.故此，本文对匹配误差eij(m)及其1阶偏导数也进行了位深度变换，利用异或运算取代乘法运算，提出了面向低位深度像素的弹性运动模型，从而加快弹性运动估计的速度.

根据1阶偏导的符号，文献[23]将其直接2值化为

(12)

其中，用bit “1”表示正数，用bit “0”表示非正数，表示的第k个分量.同理，采用同样的规则将匹配误差eij(m)进行位深度的变换，即：

(13)

此时，将经过2值化后的eij(m)和代入式(8)，并将式(8)中的乘法运算替换为异或运算来计算向量b.为了验证上述规则的有效性，表1给出了基于8 b运算的的乘法符号表，而表2所示则为低位深度的和经过1 b异或运算“⊕”的真值表.

对比表1和表2可以发现，8 b乘法运算的符号与1 b异或运算的真值并不一致.例如正数与负数的乘积为负数，也就是“1”与“0”的乘积应为“0”，而异或的结果却等于“1”.另一方面，高斯-牛顿法通过控制每次迭代的方向，若则由Δm=H-1b可知，将导致迭代步长失去向全局最优解收敛的驱动力.这表明，采用文献[23]的方法将弹性模型进行2值化，仅能产生单一方向的迭代动力(也就是当时的情形)，不利于保证解的精度和收敛速度.

为了解决这个问题，本文通过将匹配误差进行2次互为相反数的2值化转换，提出了基于2 b深度的弹性运动模型，即：

(14)

(15)

其中，和表示当前帧和参考帧的2 b深度表示，和分别表示在弹性运动参数m下像素(i,j)处匹配误差的高位和低位.在此基础上，将高、低位分别与进行异或运算，再将所得结果相减：

(16)

表3给出了经过上述改进后，1 b异或运算和8 b乘法运算的对比结果.可见，与表现出一致的极性，并且表明，上述基于2 b深度的弹性运动模型不仅避免了时可能出现的不收敛现象，也使得求解过程能够朝着2个不同方向进行迭代，从而提高取得全局最优解的概率.鉴于这一原因，本文向量b的计算过程为

(17)

5 迭代步长的自适应计算

在高斯-牛顿方法中，b用于确定每次迭代的方向，黑塞矩阵H的逆H-1则用于确定每次迭代的步长.然而，计算H-1需要大量的乘法运算，其时间复杂度为O(p3)；并且，1阶偏导经过第4节的2 b转换后，H-1所给出的步长亦不够精确，没有必要再通过H-1计算迭代步长.所以，文献[25]采用固定步长s来近似H-1，于是弹性运动向量的增量表示为

Δm=-s×sgn(b),

(18)

其中，sgn(·)表示符号函数.但是，这种做法无异于放弃了黑塞矩阵对高斯-牛顿迭代过程的控制.而文献[19-20,22]的研究结论却表明，高斯-牛顿法对初始迭代步长较为敏感，文献[25]的这种固定初始步长的方式显然不利于迭代过程收敛到全局最优解.为了验证这一推论，我们选取Akiyo，Tempete，Football这3个运动特性和纹理复杂度各异的视频序列的前10帧，应用固定步长的2 b深度弹性模型进行了运动估计补偿实验.图5给出了在不同的初始步长s下，3个序列经过15次迭代后所获得的平均运动补偿PSNR曲线.从图5可见，Akiyo序列的运动幅度很小、画面纹理细节简单，随着初始步长的缩小，该序列的运动补偿PSNR明显升高(图5(a))，但是即使初始步长缩小至1×10-6，仍未取得最高的PSNR；Tempete序列的运动幅度中等，可是纹理细节复杂，且包含摄像机的拉摄运动，其运动补偿的平均PSNR在初始步长为4×10-6时取得极值，然后随着初始步长的增大迅速下降(图5(b))；Football序列既包含快速的前景运动和中等复杂度的纹理，又存在物体的局部形变，它在初始步长等于3×10-5时取得了运动补偿PSNR的极值(图5(c))，而此时，Akiyo的平均PSNR已比其最高值下降了4.74 dB.

对比这3个视频序列的实验结果可知，不同序列的最优初始步长相差几十倍.对于运动幅度较小、画面细节较多的视频，应为其选取一个较小的迭代步长；反之，对于运动速度较快、局部形变较多的视频，为其设定一个较大的迭代步长则更加合适.可见，文献[25]固定初始步长的方式不仅无法保证运动补偿的质量，而且在现实中亦很难做到折中选择.为此，本节采用一种自适应步长s来近似H-1，下面讨论其计算方法.

由式(6)可知，高斯-牛顿法的基本思路是在每次迭代中利用2次函数来逼近匹配误差D(m)，并求解近似函数的极小点作为下一个迭代点，则第k+1次迭代的弹性运动向量mk+1有：

mk+1=mk+H-1b,

(19)

其中，那么：

(20)

(21)

由于匹配误差eij(m)在全局最优解附近“几乎”是白噪声[30]，式(21)第2项的数学期望近似为0，就有：

≈2H.

(22)

而由微分的1阶近似性质Δf(x)≈f′(x)·Δx，可知：

(23)

进一步，将式(20)代入式(23)，得到：

(24)

再由式(22)易知H≈-ΔbΔm，整理后即可得到自适应步长s：

(25)

式(25)表明：自适应步长s与运动向量的变化量Δm成正比，而与匹配误差的变化量及其关于m的导数呈反比.对比图5的实验结果，Akiyo序列的运动幅度很小，其Δm几乎为0，而由于播音员的头部和嘴部存在局部运动，第1次迭代后产生的匹配误差必然大于0，这就使得该序列的最优初始步长趋近于0；尽管Tempete序列存在中等幅度的运动(即Δm>0)，可是复杂纹理细节势必产生较大的匹配误差，故此，由式(25)可推知Tempete序列的最优初始步长也相对较小；考虑到Football序列包含快速运动，其Δm将明显超过Akiyo和Tempete，且纹理细节的复杂度一般，匹配误差变化量在预期上不会显著大于Tempete序列，于是Football序列的最优初始步长较大.综合上述分析，式(25)的结论与图5的实验结果一致.

为了进一步降低式(25)所需要的计算量，本文采用取绝对值运算代替乘法和开平方运算来近似取模长运算：

(26)

(27)

其中，Δmk，Δbk分别表示Δm和Δb的第k个分量.同时，本文仅利用式(25)～(27)确定初始迭代步长，而对于后续的迭代，为保证算法具有较稳定的收敛性，本文在步长值满足以下条件时将其减半[25]：b的符号在连续3次迭代中改变3次，即在某个解的局部邻域内发生往返式的迭代.如第4节所述，本文的低位深度的弹性运动模型能朝着2个不同方向进行迭代，若发生折返式迭代，则表明算法很可能处于某个全局局部最优解的单调区间内，且当前步长较大，导致每次迭代均越过该最优解，故应选取更小的步长向这个解进行逼近.

6 2 b深度像素的弹性运动估计步骤

在第5节算法的基础上，本节给出一种基于2 b深度像素的弹性运动估计方法，具体步骤如图6所示，其中，xi，yi表示I中某个像素的横、纵坐标，0≤xi,yi≤B-1；m0表示只包含平移分量的初始运动向量，且m0=(m1,0,…,mp2+1,0,…)；Th表示预设的迭代次数阈值；R′(·)表示参考帧中位于坐标“·”处的2 b深度的像素值；8 b深度像素的菱形搜索和弹性运动估计的搜索窗口尺寸为W×W像素.

7 实验结果与分析

为了验证本文算法的有效性，以通用中间格式(common intermediate format, CIF)、4CIF和高清格式的34个标准视频序列(见表4)的1～90f为例进行实验，并将结果与基于8 b深度像素的菱形运动估计[31](简称8 b-DS)、基于8 b深度像素的块平移全搜索(简称8 b-FS)、基于8 b深度像素的弹性运动估计[16](简称8 b-Elastic)、基于传统2 b深度像素的块平移全搜索算法[29](简称2 b-FS)以及未引进自适应初始步长的本文算法(简称2 b-Elastic-NAStep)进行比较.

实验参数选取为：搜索窗口为33×33像素，宏块尺寸为B=16像素，这与文献[16,29,31]的参数取值相同，也是视频编码器的典型设置.为了在预测精度和收敛速度之间实现折中，令迭代次数阈值Th=5，7.2节还将对此进行深入讨论.同时，为公平起见，将传统8 b-Elastic的迭代次数也设置为5次.运动补偿质量采用PSNR进行评价.

7.1 运动估计补偿质量的比较

表5罗列了各个测试序列的亮度分量采用不同运动估计算法所得到的平均PSNR.从表5可见，相对于传统的2 b深度像素的全搜索算法2 b-FS[29]，未引进自适应初始步长的本文算法2 b-Elastic-NAStep将PSNR平均提高了1.15 dB，表明基于Prewitt算子的2 b变换和2 b深度像素的弹性运动模型能够进行更有效的运动估计补偿.2 b-Elastic-NAStep算法的平均PSNR比传统的8 b深度弹性运动估计8 b-Elastic[16]提高了0.46 dB，其根本原因在于8 b像素的匹配误差曲面富含局部极值点，在缺少初始搜索的情况下易陷入局部最优，并且8 b匹配误差曲面的下降梯度为高斯-牛顿法提供的迭代驱动力不足，收敛速度较慢；而2 b-Elastic-NAStep算法则利用8 b-DS计算弹性运动向量的水平和竖直分量，将起始搜索点置入全局最优点的单调区间，再沿着梯度下降方向进行迭代，这表明起始搜索点对于提高弹性运动估计的精度有重要作用，该结论与文献[19-20,22]的研究结果一致.同时，2 b-Elastic-NAStep算法的平均PSNR较之8 b深度像素的菱形运动估计8 b-DS高出0.90 dB，并且比8 b深度像素的块平移全搜索8 b-FS提高0.23 dB，说明本文提出的低位深度弹性运动模型在初始搜索的基础上取得了进一步的性能增益.在引进了自适应初始步长之后，本文算法的运动补偿PSNR比2 b-Elastic-NAStep又提高了0.92 dB，这表明通过自适应步长实现黑塞矩阵对迭代过程的控制，有助于弹性运动估计收敛到全局最优解，进而表现出与8 b深度像素的阻尼高斯-牛顿法相近的准确程度.

图7给出了Akiyo，Husky，City，Flowervase序列的PSNR逐帧比较情况.其中，Akiyo序列仅含有局部慢速运动，且细节简单；Husky序列则与之相反，前景具有较大幅度的平移运动且纹理复杂性高；City序列含有摄像机的中速摇摄运动和丰富的细节信息；而Flowervase序列则包含摄像机的慢速拉摄运动和中等复杂性的纹理.如图7所示，尽管4个序列的运动类型、速度和纹理复杂度各有不同，本文算法的运动补偿质量均较为稳定，在绝大部分情况下都取得了最高的PSNR，而其他算法的运动估计精度却会随着视频特点的不同出现一定波动.

需要指出，作为逆黑塞矩阵的1阶近似，本文的自适应步长对于前景运动慢、纹理细节简单或者含有慢速摇摄、拉摄运动的视频(如Akiyo,Johnny,Flowervase)尤为有效，而对于含有快速运动和复杂纹理的视频(如Husky和City)，其性能增益则不够明显.究其原因在于，后者的匹配误差曲面非常复杂，导致每次迭代的最优步长之间存在较大差异，尤其当迭代过程从搜索起始点所在的单调区间进入其他单调区间时，初始步长的普适性难免会受到影响.这也是除了像素深度降采样这个原因以外，本文算法在Mobile，Waterfall，Harbour等序列上的运动补偿PSNR低于传统8 b-Elastic运动估计的根本缘故.当然，作为一种基于低位深度像素的快速运动估计算法，本文工作的基本目的是在计算量和运动估计精度之间尽量实现折中，而不是通过精确估计阻尼步长来取得最理想的补偿质量.从这个意义上讲，本文提出的低位深度的弹性模型及其初始步长的自适应计算能够满足较低计算负载下的弹性运动估计需要.

7.2 收敛速度与迭代次数的讨论

收敛速度是衡量弹性运动估计效率的指标之一.图8所示为Akiyo，Husky，City序列第2帧采用本文算法的前15次迭代结果.从图8中能够发现，对于运动幅度小、细节简单的Akiyo序列，本文算法在第1次迭代后就趋于收敛；对于运动幅度较大、纹理复杂的Husky序列，运动补偿的PSNR随着迭代次数的增加而不断升高，但是经过5次迭代就已达到最高PSNR值的99.97%；而对于含有摇摄运动且纹理丰富的City序列，本文算法在第8次迭代时取得了最高的运动补偿质量，之后出现PSNR的下降，不过在第5次迭代后已达到PSNR峰值的99.99%；由于Flowervase序列的情况与City类似，这里不再赘述.图8结果表明，一方面，本文算法在视频具有不同运动模式和空间分布特点的情况下，均能取得较快的收敛速度.另一方面，视频的运动幅度和模式，以及空间纹理复杂性对本文算法的收敛速度存在一定影响：当匹配误差曲面在全局局部最优解附近呈现单峰分布时(如Akiyo)，本文算法将快速收敛，这与3.2节所讨论的2 b匹配误差曲面具有“区域内平滑、区域间锐化”的分布特点一致，下降梯度能提供足够的迭代驱动力；反之，当迭代过程需越过不同的单峰区间时，可能引起运动补偿质量的波动甚至小幅下降.这种情况与7.1节末尾的讨论一致，源于本文为了节省计算量，仅求解1次自适应步长并且未对相邻2次迭代的均方误差进行比较(若设1个视频帧包含N个像素，则计算均方误差的时间复杂度为O(Th×N)).

考虑到本文算法经过5次迭代即可获得超过最优补偿质量99%的PSNR，并且此时迭代过程在很大概率下仍然处于起始搜索点的单调区间内，自适应步长对具有较高的逼近程度，我们在实验中将设置迭代次数阈值Th=5.同时，经过2～3次迭代后，本文算法就能够达到与8 b-FS相当的PSNR，这也表明本文基于Prewitt梯度算子的像素深度转换方法保持了视频帧的纹理特征，并未由于深度降采样导致运动估计精度的明显下降，有效避免了传统像素深度转换方法(如文献[28-29])产生大面积平滑区时陷入局部最优的现象.

7.3 计算复杂度分析

设宏块尺寸为B×B像素，搜索窗口为W×W像素，则不同运动估计算法处理1个宏块的计算量为：

1) 8 b-FS和2 b-FS的时间复杂度均为O(B2W2).另外，2 b-FS在像素深度变换阶段还需O(B2)的复杂度.

2) 由文献[31-32]可知，8 b-DS的计算复杂度约为8 b-FS的7%，即O(0.07B2W2).

3) 用高斯-牛顿法求解8 b深度弹性运动模型的每次迭代需计算偏导数、黑塞矩阵、逆矩阵、矩阵乘法、双线性插值和当前的运动补偿误差，其渐近时间复杂度分别为O(pB2)，O(p2B2)，O(p3)，O(pB2)，O(B2)，O(B2).

4) 由于省去了黑塞矩阵及其逆矩阵的计算，本文算法的每次迭代过程只需求解偏导数、向量乘法、双线性插值和运动补偿误差，其渐近时间复杂度分别为O(pB2)，O(pB2)，O(B2)，O(B2)，基于菱形搜索的初始点预测还需约为O(0.07B2W2)的计算复杂度.

当搜索窗口W=33、块尺寸B=16、迭代次数阈值Th=5时，本文算法的时间复杂度约为8 b-FS算法和2 b-FS算法的15.26%、8 b-Elastic算法的39.58%，但是高于8 b-DS.若进一步将迭代次数Th减少到2～3次，本文算法则可在8 b-FS算法的10.31%～11.60%的时间复杂度内，获得与之相当的运动估计精度.

具体地，表6给出了各种算法求解1个块的运动向量所需的平均操作次数，其中运动估计阶段的“Addition”操作包括8 b定点加法和浮点加法.从表6可见，本文方法的操作次数显著少于8 b-FS，2 b-FS和8 b-Elastic.尽管8 b加法、2 b加法、乘法、取绝对值、比较、位运算等各类操作所需的CPU周期数和计算代价存在明显差异，可是这些指标依赖于具体的硬件设计和指令集，已超出本文的讨论范围，所以在此不予进一步的定量比较，详细了解可参见文献[28].不过，考虑到本文算法采用位操作和比较操作来求解偏导数、向量乘法和运动补偿误差，其计算开销将低于8 b像素的加法和乘法，且有利于实现多个像素的并行计算，其实际开销比渐近时间复杂度更低.

8 结 论

为进一步改善弹性运动估计的实时性，本文引进了基于Prewitt梯度算子和正态分布的像素深度变换，以及基于位操作和比较操作的矩阵乘法和偏导运算，推导出高斯-牛顿法的自适应初始步长的1阶逼近方法，从而提出了一种基于2 b深度像素的弹性运动估计.其优点在于尽可能地简化求解弹性运动模型的高斯-牛顿法，用异或运算替代乘法运算，且无需反复计算黑塞矩阵及其逆矩阵.实验结果表明，该算法的运动补偿质量和计算效率优于8 b深度像素的块平移全搜索算法、菱形搜索算法、传统弹性搜索算法，以及传统2 b深度像素的块平移全搜索算法.

另外，本文算法仍存在若干问题可臻完善，如快速预测起始搜索点、根据匹配误差曲面的曲率变化来自适应地更新初始步长，以及设计能够高效执行本文算法的硬件电路等，我们将在今后的工作中进一步深入研究这些问题的解决思路.

参考文献

[1]Ma Siwei. History and recent development of AVS video coding standards[J]. Journal of Computer Research and Development, 2015, 52(1): 27-37 (in Chinese)

(马思伟. AVS视频编码标准技术回顾及最新进展[J]. 计算机研究与发展, 2015, 52(1): 27-37)

[2]Sinangil M E, Sze V, Zhou Minhua, et al. Cost and coding efficient motion estimation design considerations for high efficiency video coding (HEVC) standard[J]. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(6): 1017-1028

[3]Narroschke M, Swoboda R. Extending HEVC by an affine motion model[C] Proc of the 30th PCS. Piscataway, NJ: IEEE, 2013: 321-324

[4]Ahmmed A, Hannuksela M M, Gabbouj M. Fisheye video coding using elastic motion compensated reference frames[C] Proc of the 23rd IEEE ICIP. Piscataway, NJ: IEEE, 2016: 2027-2031

[5]Liu Dong, Wu Feng. Advances and trends of video coding technologies[J]. Communications of the CCF, 2016,12(6): 20-23 (in Chinese)

(刘东, 吴枫. 视频编码技术发展与趋势[J]. 中国计算机学会通讯, 2016, 12(6): 20-23)

[6]Ahmmed A, Xu Rui, Naman A T, et al. Motion segmentation initialization strategies for bi-directional inter-frame prediction[C] Proc of the 15th IEEE MMSP. Piscataway, NJ: IEEE, 2013: 58-63

[7]Wu Feng, Gao Peng, Gao Wen. Motion estimation technologies based on mesh model[J]. Acta Electronica Sinica, 2000, 28(5): 47-51 (in Chinese)

(吴枫, 高鹏, 高文. 基于网格模型的运动估计技术[J]. 电子学报, 2000, 28(5): 47-51)

[8]Al-Regib G, Altunbasak Y, Mersereau R M. Hierarchical motion estimation with content-based meshes[J]. IEEE Transactions on Circuits and System for Video Technology, 2003, 13(10): 1000-1005

[9]Cui Suxia, Wang Yonghui, Fowler J E. Motion estimation and compensation in the redundant-wavelet domain using triangle meshes[J]. Signal Processing: Image Communication, 2006, 21(7): 586-598

[10]Huang Han, Woods J W, Zhao Yao, et al. Control-point representation and differential coding affine-motion compensation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(10): 1651-1660

[11]Li Li, Li Houqiang, Liu Dong, et al. An efficient four-parameter affine motion model for video coding[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2018, 28(8): 1934-1947

[12]Zheng Jiali, Qin Tuanfa, Ni Guangnan. Adaptive global motion estimation method based on rate distortion optimization[J]. Journal of Image and Graphics, 2011, 16(8): 1346-1352 (in Chinese)

(郑嘉利, 覃团发, 倪光南. 结合率失真优化的自适应全局运动估计方法[J]. 中国图象图形学报, 2011, 16(8): 1346-1352)

[13]Po L M, Wong K M, Cheung K W, et al. Subsampled block-matching for zoom motion compensated prediction[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(11): 1625-1637

[14]Yuan Hui, Liu Ju, Sun Jiande, et al. Affine model based motion compensation prediction for zoom[J]. IEEE Transactions on Multimedia, 2012,14(4): 1370-1375

[15]Kim H S, Lee J H, Kim C K, et al. Zoom motion estimation using block-based fast local area scaling[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(9): 1280-1291

[16]Muhit A A, Pickering M R, Frater M R, et al. Video coding using elastic motion model and larger blocks[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(5): 661-672

[17]Muhit A A, Pickering M R, Frater M R, et al. Video coding using fast geometry-adaptive partitioning and an elastic motion model[J]. Journal of Visual Communication and Image Representation, 2012, 23(1): 31-41

[18]Deng Binyou. Study on video compression based on elastic motion model[D]. Xiamen: Xiamen University, 2014 (in Chinese)

(邓斌攸. 基于弹性运动模型的视频压缩算法研究[D].厦门: 厦门大学, 2014)

[19]Song Chuanming, Zhao Changwei, Liu Dan, et al. Elastic motion estimation of video using improved Gauss-Newton method[J]. Journal of Software, 2016, 27(11): 2946-2960 (in Chinese)

(宋传鸣, 赵长伟, 刘丹, 等. 采用改进高斯-牛顿法的视频弹性运动估计[J]. 软件学报, 2016, 27(11): 2946-2960)

[20]Zhao Changwei. Research on motion estimation algorithm using elastic model[D]. Dalian: Liaoning Normal University, 2015 (in Chinese)

(赵长伟. 基于弹性模型的运动估计算法研究[D]. 大连: 辽宁师范大学, 2015)

[21]Huang Han. Research on interintra prediction and optimization techniques in HEVC[D]. Beijing: Beijing Jiaotong University, 2013 (in Chinese)

(黄晗. HEVC帧间帧内预测及优化技术研究[D]. 北京: 北京交通大学, 2013)

[22]Song Chuanming, Min Xin, Yan Xiaohong, et al. Fast elastic motion estimation using improved Levenberg-Marquardt method[JOL]. Journal of Software, 2019. [2019-02-09]. http:www.jos.org.cn1000-98255487.htm (in Chinese)

(宋传鸣, 闵新, 闫小红, 等. 采用改进Levenberg-Marquardt法的快速弹性运动估计[JOL]. 软件学报, 2019. [2019-02-09]. http:www.jos.org.cn1000-98255487.htm)

[23]Haque M N, Biswas M, Pickering M R, et al. A low complexity algorithm for global motion parameter estimation targeting hardware implementation[C] Proc of the 11th DICTA. Piscataway, NJ: IEEE, 2009: 1-5

[24]Haque M N, Biswas M, Pickering M R, et al. An adaptive low-complexity global motion estimation algorithm[C] Proc of the 27th PCS. Piscataway, NJ: IEEE, 2010: 598-601

[25]Haque M N, Biswas M, Pickering M R, et al. A low-complexity image registration algorithm for global motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(3): 426-433

[26]Song Chuanming, Guo Yanwen, Wang Xianghai, et al. Fuzzy quantization based bit transform for low bit-resolution motion estimation[J]. Signal Processing: Image Communication, 2013, 28(10): 1435-1447

[27]Song Chuanming, Guo Yanwen, Wang Xianghai, et al. Motion estimation algorithm using 2 bit-depth pixel and fuzzy quantization[J]. Journal on Communications, 2013, 34(7): 59-70 (in Chinese)

(宋传鸣, 郭延文, 王相海, 等. 基于模糊量化和2 bit深度像素的运动估计算法[J].通信学报, 2013, 34(7): 59-70)

[28]He Zhongli, Tsui C Y, Chan K K, et al. Low-power VLSI design for motion estimation using adaptive pixel truncation[J]. IEEE Transactions on Circuits Systems for Video Technology, 2000, 10(8): 669-678

[29]Ertürk A, Ertürk S. Two-bit transform for binary block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2005, 15(7): 938-946

[30]Diniz P S R. Adaptive Filtering: Algorithm and Practical Implementation[M]. New York: Springer US, 2013

[31]Zhu Shan, Ma K K. A new diamond search algorithm for fast block-matching motion estimation[J]. IEEE Transactions on Image Processing, 2000, 9(2): 287-290

[32]Li Renxiang, Zeng Bing, Liou M L. A new three-step search algorithm for block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1994, 4(4): 438-442

Elastic Motion Estimation Algorithm Using Two-Bit-Depth Pixels

Song Chuanming1,2,4, Min Xin1,3, Xie Weidong1,3, Yin Baocai2, and Wang Xianghai1

1(School of Computer and Information Technology, Liaoning Normal University, Dalian, Liaoning 116029) 2(School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024) 3(School of Computer Science and Engineering, Northeastern University, Shenyang 110169) 4(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023)

Abstract To reduce the computational complexity of traditional elastic motion estimation, this paper proposes a novel elastic motion estimation algorithm using two-bit-depth pixels. First, the Prewitt operator is employed to calculate the gradient of each video frame. The mean and standard deviation of the gradient norm is utilized to down-sample each pixel’s depth from 8 b into 2 b. Second, the bitwise operation-based matrix multiplication and the comparison based partial derivative computation are introduced. We subsequently describe an elastic motion model using two-bit-depth pixels, as well as a simplified Gaussian-Newton method which avoids the repetitive computation of the Hessian matrix and its inverse matrix. Meanwhile, we establish the functional relationship of the damping step size versus motion vector increment and motion-compensated errors by the first-order linear approximation, obtaining a method for approximately calculating the initial step size. Furthermore, we address a fast method for solving the elastic motion model with two-bit-depth pixels, using the diamond search algorithm as initial search. Experimental results illustrate that our algorithm obviously outperforms the full search with eight-bit-depth pixels, the full search with two-bit-depth pixels, as well as the conventional elastic motion estimation with eight-bit-depth pixels in terms of the peak signal-to-noise ratio (PSNR) and computational efficiency.

Key words video coding; motion estimation; low bit-depth pixel; elastic motion model; adaptive damping coefficient

(chmsong@lnnu.edu.cn)

收稿日期：20181012；

修回日期：20190411

基金项目：国家自然科学基金项目(61402214,41671439,61632006)；辽宁省自然科学基金项目(20180550570)；辽宁省高等学校创新人才支持计划项目(64)；南京大学计算机软件新技术国家重点实验室开放课题项目(KFKT2018B07)

This work was supported by the National Natural Science Foundation of China (61402214, 41671439, 61632006), the Natural Science Foundation of Liaoning Province of China (20180550570), the Program for Liaoning Excellent Talents in University (64), and the Open Foundation of State Key Laboratory for Novel Software Technology (Nanjing University) (KFKT2018B07).

中图法分类号 TP37；TN941.1

Song Chuanming, born in 1980. Associate professor of the School of Computer and Information Technology of Liaoning Normal University. Received his PhD degree at the Department of Computer Science & Tech-nology of Nanjing University. Member of CCF. His main research interests include image and video coding, and digital watermarking of multimedia.

Min Xin, born in 1992. Received his master degree in computer science and technology at the School of Computer and Information Technology of Liaoning Normal University. His main research interests include video coding. (hy_minxin@126.com)

Xie Weidong, born 1992. PhD candidate. Received his master degree in computer science and technology from the School of Computer and Information Technology of Liaoning Normal University. His main research interests include video and image coding. (xwdshiwo@163.com)

Yin Baocai, born in 1963. Professor and PhD supervisor of the School of Computer Science and Technology of Dalian University of Technology. Senior member of CCF. His main research interests include digital multimedia, multi-functional perception, virtual reality, as well as computer graphics. (ybc@dlut.edu.cn)

Wang Xianghai, born in 1965. Professor and PhD supervisor of the School of Computer and Information Technology of Liaoning Normal University. Senior member of CCF. His main research interests include computer graphics and multimedia infor-mation processing. (xhwang@lnnu.edu.cn)