CN101754023B - 一种图像压缩的运动估计方法 - Google Patents

Abstract

本发明涉及一种图像压缩的运动估计方法。包括以下步骤：S1.将当前帧和参考帧进行宏块划分；S2.载入当前帧的待估计的宏块；S3.以当前帧的待估计的宏块的位置作为参考帧运动估计的搜索起始位置；S4.以参考帧搜索起始位置为中心，构建步长为四的菱形搜索区域，同时以参考帧搜索起始位置的宏块为中心，构建步长为二的十字搜索区域；S5.将上述匹配搜索位置的宏块依次与当前帧载入的待估计的宏块进行绝对误差和(SAD)计算，选取SAD值最小的宏块的位置作为下次匹配搜索的中心起始位置；本发明的有益效果是克服了传统的搜索方法容易陷入局部最优解的缺陷，而且能够有效的降低残差矩阵的能量，提高峰值信噪比。

Description

一种图像压缩的运动估计方法

技术领域

本发明涉及了视频压缩技术领域，具体涉及一种视频压缩技术领域中的宏块的运动估计方法。

背景技术

由现有的理论可以知道，在视频序列中，在相邻的两帧之间存在着极大的空间冗余。视频压缩的目的是为了消除空间冗余，从而进行传输。视频压缩的第一步是进行运动估计，求出残差矩阵。常见的运动估计的搜索方法有三步搜索方法、对数搜索方法、菱形搜索方法。三步搜索方法的主要缺点是搜索的整个过程采用了统一的搜索模板，使得第一步的步长过大，容易引起误导，从而对小运动效率较低。对数搜索方法的主要缺点是该算法的前提是假设搜索区内只有一个谷点，如果在搜索区内存在多个谷点时，该方法可能陷入局部最优解，不能保证找到全局最优解。菱形搜索方法的主要优点是可以快速收敛于搜索区域的最优解，同时可以向最优解方向进行收敛，但是由于在第一步的搜索范围过小，如果前后两帧图像之间的运动过大，有可能会导致在第一步的搜索范围内不能确定出最优解的收敛方向，导致它有可能向局部最优解方向收敛。如图

1和图5所示为现有技术的菱形搜索方法(DSP，Diamond Search Pattern)。该方法的具体包含如下步骤：

步骤1、设置初始搜索步长(本处步长为宏块的长度)为二，选取搜索区域中心(即中心起始位置)和搜索区域中心及其周围按照菱形排列的8个顶点和菱边的中间点的9个位置点作为本步骤的搜索位置集合进行匹配计算，找出9个位置点中绝对误差和(SAD，Sum of Absolute Difference)的值最小的点作为本步骤的最佳匹配点，本步骤搜索过程被称为步长为二的大菱形搜索方法(LDSP，Large Diamond Search Pattern)。若最佳匹配点的位置位于菱形中心点，则进行步骤3；否则进行步骤2；

步骤2、以上一步找到的最佳匹配点作为新的中心点，再次进行步长为二的LDSP搜索和计算，找出本步骤的最佳匹配点；若最佳匹配点的位置位于菱形中心点，则进行步骤3；否则重复进行步骤2直到最佳匹配点位于搜索中心；

步骤3、以上述步骤找到的最佳匹配点作为中心点，设置初始搜索步长为一，选取搜索区域中心和搜索区域中心相临的四个顶点作为本步骤的搜索位置集合进行匹配计算，找出5个位置点中绝对误差和(SAD)的值最小的点作为本步骤的最佳匹配点，该点所在的位置即菱形搜索方法的最佳匹配点，该点对应最佳的运动矢量。本步骤搜索过程被称为小菱形搜索方法(SDSP，SmallDiamond Search Pattern)。

发明内容

本发明的目的是为了克服现有的图像压缩的运动估计方法容易陷入局部最优解的缺陷，提出了一种图像压缩的运动估计方法。

为了实现本发明的目的，本发明提供了一种图像压缩的运动估计方法，包括以下步骤：

S1.将当前帧和参考帧进行宏块划分；

S2.载入当前帧的待估计的宏块；

S3.以当前帧的待估计的宏块的位置作为参考帧运动估计的搜索起始位置；

S4.以参考帧搜索起始位置为中心，构建步长为四的菱形搜索区域，选取菱形搜索区域的顶点和菱边中间点处的宏块，同时以参考帧搜索起始位置的宏块为中心，构建步长为二的十字搜索区域，选取十字搜索区域的四个端点和中心位置的宏块，将上述菱形搜索区域和十字搜索区域选取的宏块作为匹配搜索位置的宏块；

S5.将上述匹配搜索位置的宏块依次与当前帧载入的待估计的宏块进行绝对误差和(SAD)计算，选取SAD值最小的宏块的位置作为下次匹配搜索的中心起始位置；

S6.如果步骤S5中的中心起始位置为步骤S4中选取的十字搜索区域的四个端点和中心位置，则运用小菱形搜索方法得到当前帧待运动估计的宏块在参考帧中搜索获得的最佳匹配位置的宏块的运动估计向量；

S7.如果步骤S5中的中心起始位置为步骤S4中选取的菱形搜索区域的顶点和菱边中间点处，则运用菱形搜索方法得到当前帧待运动估计的宏块在参考帧中搜索获得的最佳匹配位置的宏块的运动估计向量。

本发明的有益效果是：本发明是在菱形搜索方法的基础之上作出的改进。该方法充分利用了视频序列运动矢量在分布上的中心偏置的特性，在菱形搜索方法的基础上引入了十字型分布的4个点构成的搜索点群。实验结果表明本发明克服了传统的搜索方法容易陷入局部最优解的缺陷，而且能够有效的降低残差矩阵的能量，提高峰值信噪比。

附图说明

图1是现有的菱形搜索方法(DSP，Diamond Search Pattern)的搜索原理示意图。

图2是本发明步骤S6的搜索原理示意图。

图3是本发明步骤S7的搜索原理示意图。

图4是本发明的主流程图。

图5是现有的菱形搜索方法即本发明的步骤S7的具体流程图。

图6是本发明的搜索区域比较示意图。

图7是本发明的实施结果的一个效果示意图。

图8是本发明与现有的几种方法的峰值信噪比的对比图。

具体实施方式

下面结合附图和具体的实施例对本发明做进一步的说明。

如图4所示，本发明提供了一种图像压缩的运动估计方法，包括以下步骤：

S1.将当前帧和参考帧进行宏块划分。在本实施例中，当前帧和参考帧均被分成若干相同的16×16大小的宏块(MB，Macro block)，当然也可以被分割为更小单位的块，如16×8、8×16、8×8、8×4、4×8、4×4大小的块，块的大小主要和所采用的视频压缩标准有关。

S2.载入当前帧的待估计的宏块。

S3.以当前帧的待估计的宏块的位置作为参考帧运动估计的搜索起始位置。通常取宏块左下角的原点作为宏块位置的定位点，也即宏块的位置由其左下角的原点决定。

S4.以参考帧搜索起始位置为中心，构建步长为四的菱形搜索区域，选取菱形搜索区域的顶点和菱边中间点处的宏块，同时以参考帧搜索起始位置的宏块为中心，构建步长为二的十字搜索区域，选取十字搜索区域的四个端点和中心位置的宏块，将上述菱形搜索区域和十字搜索区域选取的宏块作为匹配搜索位置的宏块。步长可以根据需要设定，本发明的实施例中，设置一个步长的长度为一个宏块的长度。

S5.将上述匹配搜索位置的宏块依次与当前帧载入的待估计的宏块进行绝对误差和(SAD)计算，选取SAD值最小的宏块的位置作为下次匹配搜索的中心起始位置。SAD值按下述公式计算：

$\mathrm{SAD}(i,j)=\underset{m=0}{\overset{M-1}{\mathrm{\Σ}}}\underset{n=0}{\overset{N-1}{\mathrm{\Σ}}}|f_k(m,n)-f_{k-1}(m+i,n+j)|---\left(1\right)$

式中，i，j为行号和列号，f_k(m，n)表示当前帧匹配搜索位置宏块的坐标(m，n)处的象素值，f_k-1(m+i，n+j)表示当前帧载入的待估计的宏块的坐标(m+i，n+j)处的象素值，M和N分别代表当前帧中宏块的宽度和高度。

S6.如果步骤S5中的中心起始位置为步骤S4中选取的十字搜索区域的四个端点和中心位置，则运用小菱形搜索方法(SDSP，Small Diamond SearchPattern)得到当前帧待运动估计的宏块在参考帧中搜索获得的最佳匹配位置的宏块的运动估计向量。由于小菱形搜索方法(SDSP，Small Diamond SearchPattern)在背景技术中已经做了详细的描述，故不在此处详细叙述。

S7.如果步骤S5中的中心起始位置为步骤S4中选取的菱形搜索区域的顶点和菱边中间点处，则运用菱形搜索方法(DSP，Diamond Search Pattern)得到当前帧待运动估计的宏块在参考帧中搜索获得的最佳匹配位置的宏块的运动估计向量。现结合附图1和附图5对菱形搜索方法的具体实施过程做详细的描述：

步骤1、设置初始搜索步长(本处步长为宏块的长度)为二，选取搜索区域中心(即中心起始位置)和搜索区域中心及其周围按照菱形排列的8个顶点和菱边的中间点的9个位置点作为本步骤的搜索位置集合进行匹配计算，找出9个位置点中绝对误差和(SAD，Sum of Absolute Di fference)的值最小的点作为本步骤的最佳匹配点，本步骤中选取的中心起始位置定义为(0，0)点，

本步骤搜索过程被称为步长为二的大菱形搜索方法(LDSP，Large DiamondSearch Pattern)。若最佳匹配点的位置位于菱形中心点，则进行步骤3；否则进行步骤2；

步骤2、以上一步找到的最佳匹配点作为新的中心点，再次进行步长为二的LDSP搜索和计算，找出本步骤的最佳匹配点；若最佳匹配点的位置位于菱形中心点，则进行步骤3；否则重复进行步骤2直到最佳匹配点位于搜索中心；

步骤3、以上述步骤找到的最佳匹配点作为中心点，设置初始搜索步长为一，选取搜索区域中心和搜索区域中心相临的四个顶点作为本步骤的搜索位置集合进行匹配计算，找出5个位置点中绝对误差和(SAD)的值最小的点作为本步骤的最佳匹配点，该点所在的位置即菱形搜索方法的最佳匹配点，并且该点对应最佳的运动估计向量。本步骤搜索过程被称为小菱形搜索方法(SDSP，Small Diamond Search Pattern)。

本发明的设计思想是根据运动估计向量的中心偏置的特性进行设计。在九幅不同的视频序列中进行运动估计的测试，将16×16的宏块在搜索窗为±7的范围内进行搜索。发现不管是慢速运动的序列“Akiyo”、“Miss America”、“Container”还是高速运动的序列“Football”、“Table tennis”，还是具有摄像机镜头平移的固定物体序列“F1owers Garden”等等，从这些序列的运动估计测试的结果来看，这些序列的运动矢量具有自身的特点和规律，这些特点如图6所示：1、大概有81.80％的运动矢量是位于距离中心原点为五个像素的正方形的搜索区域范围内，及搜索半径为2的搜索窗内，大概有77.52％的运动矢量位于菱型和十字型的搜索范围内，特别是有45.44％运动矢量是为零的运动矢量。2、运动矢量的概率分布是以(0，0)点为中心向四周递减的。3、运动矢量在水平方向和垂直方向上的概率分布要比在相同的半径下其他地方的分布要大。

如图7所示，现以foreman(352×288，4:2:0)的视频序列作为实验数据，划分为16×16的宏块。以第5帧作为参考帧，获得第六帧的当前帧。从实验结果可以看出，通过本发明的方法得到的当前帧的重建图像，近似的接近参考帧的原始图像。

仍以foreman的视频序列作为实验数据。该视频序列为8-bit。以PSNR作为衡量搜索算法的标准。对于8-bit的视频序列，PSNR的计算式如下所示：

$\mathrm{PSNR}={10\log }_{10}\left[\frac{255\×255}{\mathrm{MSE}}\right],$

MSE由以下公式确定： $\mathrm{MSE}=\frac{1}{M\×N}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}\underset{j=1}{\overset{N}{\mathrm{\Σ}}}{[f(i,j)-g(i,j)]}^2,$

f(i，j)为原始图像，g(i，j)为通过运动矢量得到的重建图像。以前三十帧图像作为被测对象，分别进行新菱形搜索算法，三步搜索算法，菱形搜索算法，得到的峰值信噪比如图所示8，本采用本发明的方法的峰值信噪比比其他方法(如三步法、菱形法)的峰值信噪比明显提高。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为发明的保护范围并不局限于这样的特别陈述和实施例。凡是根据上述描述做出各种可能的等同替换或改变，均被认为属于本发明的权利要求的保护范围。

Claims (1)

1.一种图像压缩的运动估计方法，其特征在于，包括以下步骤：

S1.将当前帧和参考帧进行宏块划分；

S2.载入当前帧的待估计的宏块；

S3.以当前帧的待估计的宏块的位置作为参考帧运动估计的搜索起始位置；

S4.以参考帧搜索起始位置为中心，构建步长为四的菱形搜索区域，选取菱形搜索区域的顶点和菱边中间点处的宏块，同时以参考帧搜索起始位置的宏块为中心，构建步长为二的十字搜索区域，选取十字搜索区域的四个端点和中心位置的宏块，将上述菱形搜索区域和十字搜索区域选取的宏块作为匹配搜索位置的宏块；

S5.将上述匹配搜索位置的宏块依次与当前帧载入的待估计的宏块进行绝对误差和(SAD)计算，选取SAD值最小的宏块的位置作为下次匹配搜索的中心起始位置；

S6.如果步骤S5中的中心起始位置为步骤S4中选取的十字搜索区域的四个端点和中心位置，则运用小菱形搜索方法得到当前帧待运动估计的宏块在参考帧中搜索获得的最佳匹配位置的宏块的运动估计向量；

S7.如果步骤S5中的中心起始位置为步骤S4中选取的菱形搜索区域的顶点和菱边中间点处，则运用菱形搜索方法得到当前帧待运动估计的宏块在参考帧中搜索获得的最佳匹配位置的宏块的运动估计向量。

Images