CN100377599C - 一种快速亚像素运动估计方法 - Google Patents

Abstract

本发明涉及一种快速亚像素运动估计方法，属于图像处理领域。本发明在整像素运动估计的基础上，直接计算出最优亚像素的位置，从而可将亚像素运动估计的搜索点数减少到2个以下，避免了传统方法的逐点搜索比较，不仅大幅度提高了搜索速度，而且插值亚像素点所需的存储开销趋近于零。实验结果表明该方法以极小的搜索代价取得了与全搜索相当的效果。

Description

一种快速亚像素运动估计方法

技术领域

本发明涉及一种提高亚像素运动估计速度、减少亚像素运动估计过程中存储开销的方法，属于图像处理技术领域。

背景技术

近10年来，基于离散余弦变换和运动补偿的编码方案在视频压缩中得到了广泛应用，并纳入到一系列国际标准，如H.263、MPEG-4和JVT等。在该方案中，运动估计是消除视频帧间冗余的有效方法，但由于其采用帧间逐块搜索比较，计算量巨大，成为影响视频压缩性能的关键技术障碍。运动估计由整像素运动估计和亚像素运动估计两部分组成。整像素运动估计直接以已编码帧为参考帧，搜索整像素级的最优匹配块；亚像素运动估计则通过插值估算参考帧中非直接采样点(亚像素点)的值，以此为参考，在整像素运动估计的基础上进一步搜索亚像素级的最优匹配块。实验表明，在整像素运动估计的基础上进行亚像素运动估计，能够明显提高运动补偿效果，因此亚像素运动估计已成为提高图像压缩比的有效方法。

目前视频压缩标准中普遍采用的亚像素运动估计是全搜索方法，即先对整幅图像进行插值，在此基础上，搜索整像素运动估计最优点周围的8个1/2像素点，得到1/2像素级的最优点，如此类推，每一级亚像素搜索都以上一级搜索的最优点为中心搜索其周围的8个下一级亚像素点。对于K级(或称1/2^K)亚像素运动估计，则每个当前块需进行8×K个块的搜索，同时插值后的图像增大为输入图像的2^2K倍，编码过程中需增加2^2K-1倍的插值存储空间。这种全搜索方法不仅运算复杂度极高而且随亚像素精度的增加插值存储开销也呈指数级增长。

为解决亚像素全搜索方法中存在的问题，产生了许多快速算法。当前的这些方法一般从搜索策略、终止条件等方面缩小搜索范围以减少搜索点数。总的来说其搜索精度与全搜索仍存在较大差距，搜索速度也需要进一步提高；此外，大量的插值存储开销也是一个难以解决的问题。实际应用中，尤其针对存储资源有限的应用环境，一种好的亚像素运动估计方法必须同时考虑搜索精度、运行效率及存储开销。

发明内容

本发明的目的在于提供一种快速亚像素运动估计方法。该方法根据邻近整像素值直接推导任意精度下的最优亚像素位置，从而避免了传统逐点搜索比较的方法所带来的存储开销。

为实现上述的发明目的，本发明采用下述的技术方案：

一种快速亚像素运动估计方法，包括根据整像素运动估计得到整像素最优匹配块，其特征在于进一步包括以下步骤：

步骤：用当前块、整像素最优匹配块及其邻近的整像素块表示当前块与整像素最优匹配块周围的亚像素块的最小均方差及其相应的最优亚像素块的位置，并根据当前块、整像素最优匹配块及其邻近的整像素块之间的关系分别计算任意精度下的水平、垂直最优亚像素块的位置；

步骤二：根据具体应用中采用的亚像素精度，对步骤一中得到的最优亚像素位置进行近似处理，得到指定精度下的近似最优位置；

步骤三：将步骤二中分别获得的水平和垂直方向上近似最优位置进行合成，得到二维近似最优位置；

所述二维近似最优位置若处于亚像素位置，将其对应块作为一候选块；并从步骤二中得到水平方向上和垂直方向上的近似最优亚像素位置中选取残差最小者，其处于亚像素位置则将其对应块作为另一候选块；

对所述候选块进行搜索匹配，并与所述整像素运动估计结果相比较，取最优块作为最终结果。

所述步骤一包括步骤：

(11)分别计算当前块与整像素运动估计最优匹配块左、右两侧的亚像素块之间的最小匹配误差，并取两者中的最小值作为水平最小残差；

(12)分别计算当前块与整像素运动估计最优匹配块上、下两侧的亚像素块之间的最小匹配误差，并取两者中的最小值作为垂直最小残差。

所述步骤一进一步包括以下步骤：

(13)根据步骤(11)和(12)中得到的水平和垂直方向上的最小匹配误差，分别计算其对应的任意精度下最优亚像素位置。

所述最小匹配误差为最小均方差和最小绝对差和中的一种。

所述当前块与亚像素块的最小均方差和所述当前块、整像素最优匹配块及其邻近整像素块之间的关系为：

$\mathrm{Min}\left(D_{c_{i,j}{s}_{i,j}}\right)=\frac{4D_{r_{i,j}{r}_{i+1,j}}{D}_{c_{i,j}{r}_{i,j}}-{(D_{c_{i,j}{r}_{i,j}}-D_{c_{i,j}{r}_{i+1,j}}-D_{r_{i,j}{r}_{i+1,j}})}^2}{{4D}_{r_{i,j}{r}_{i+1,j}}}$

所述最优亚像素块的位置与当前块、整像素最优匹配块及其邻近整像素块之间的关系为： $m_h=\frac{D_{c_{i,j}{r}_{i+1,j}}-D_{c_{i,j}{r}_{i,j}}}{2D_{r_{i,j}{r}_{i+1,j}}}+\frac{1}{2}$

其中形如D_{dx，yd′x，y}的符号表示图像中左上位置点为d_x，y、d′_x，y的两个块的绝对差和，c_i，j为当前块上的点，r_i，j为整像素最优匹配块上的点，Min(D_ci，jsi，j)表示亚像素块与当前块之间的最小均方差，m_h表示最优位置。

所述步骤二中的对步骤一中得到的最优亚像素位置进行近似处理，包括：当指定搜索精度为1/2^K时，一维近似最优位置m′与步骤一中得到的最优位置m_h间关系为：m′＝roumd(m_b×2^K)/2^k，其中，roumd()表四舍五入，由此得到近似最优位置。

所述步骤三中从二维近似最优位置及水平和垂直方向上近似最优亚像素位置中选取处于亚像素位置的候选块，包括：

1)若二维近似最优位置对应块处于亚像素位置，则将其作为一个候选块。

2)判断水平方向近似最优位置和垂直方向近似最优位置对应的最小绝对差和，如果水平方向近似最优位置对应的最小绝对差和较小，则进一步判断水平方向近似最优位置是否在亚像素位置，如果是，则选定水平方向近似最优位置对应块为候选块；如果垂直方向近似最优位置对应的最小绝对差和较小，则进一步判断垂直方向近似最优位置是否在亚像素位置，如果是，则选定垂直方向近似最优位置对应块为候选块。

步骤三还包括：通过插值计算候选块中各亚像素点的值，并计算该块与当前块的最小绝对差和，并与整像素运动估计得到的最小绝对差和进行比较，将两者中较小值的对应位置作为最终搜索到的运动矢量。

本发明利用整像素运动估计的中间结果，通过计算直接确定0-2个最优亚像素候选块，并在此候选块基础上进行搜索。理论分析表明，对于搜索精度为1/2^K的亚像素运动估计，与亚像素全搜索方法相比，搜索块数下降率高达(8×K-2)/8×K以上。实验结果显示，1/4亚像素运动估计时，搜索块数下降率在90％以上，而图像质量和压缩码率都没有明显变化。同时，本发明搜索过程中的插值存储开销趋近于零，这对于在专用芯片、DSP上实现的视频编码器十分重要。

附图说明

图1是本发明所述的亚像素运动估计方法的流程图；

图2是二维亚像素运动的像素分布示意图；

图3是对二维运动分解为一维运动进行运动估计的示意图；

图4是一维最优近似位置的示意图。

具体实施方式

本发明在整像素运动估计的基础上，根据邻近整像素值直接推导任意精度下的最优亚像素位置，从而提出了一种基于最优位置计算的快速亚像素运动估计方法。

由于亚像素位置点并非直接采样，而是由邻近整像素采样点插值而来，因此与当前块具有最优匹配的亚像素块的位置完全可由其周围的整像素值直接导出，以避免当前方法中的逐点搜索比较。

下面结合附图说明本发明的实现方式。图1中明确表示了本发明所述方法的整体流程，即：先分别计算水平和垂直方向上的一维最优亚像素位置；再根据设定的精度，对一维最优亚像素位置进行近似处理，分别得到水平和垂直方向上的近似最优位置；最后再根据水平和垂直方向上的近似最优位置选择侯选块，完成搜索。下面详细说明如下：

步骤一：根据当前块与整像素最优匹配块及其邻块间的关系，分别计算任意精度下的水平、垂直最优亚像素块的位置。

下面结合图2、图3具体说明如何计算水平或垂直最优亚像素位置。在图2和图3中，用“●”表示整像素点；“X”表示亚像素点。图3中各点为其所在块的左上点，R_i，j为整像素运动估计(IME)最优匹配块，R_i+1，j、R_i-1，j为其水平两侧距离为1个像素的邻块，R_i，j+1、R_i，j+1为其垂直两侧距离为1个像素的邻块。

在本发明所述方法中，设编码帧中当前待搜索块上的点为c_i，j(i∈(0，M)，j ∈(0，N))，其中M，N分别表示搜索块包含的水平、垂直方向像素数；整像素运动估计后得到的参考帧中最优匹配块上各点为r_i，j(i∈(0，M)，j∈(0，N))；最优匹配块上各点r_i，j之间插值得到的亚像素块为s_i，j，且S_i，j满足公式：s_i，j＝mr_i，j+(1+m)r_i+1，j其中，m是位置参数。

通过数学上的推导，IME最优匹配块水平或垂直方向上一侧的亚像素块与当前块之间的均方差经过化简可最终表示为：

$D_{c_{i,j}{s}_{i,j}}=D_{r_{i,j}{r}_{i+1,j}}{m}^2+(D_{c_{i,j}{r}_{i,j}}-D_{c_{i,j}{r}_{i+1,j}}-D_{r_{i,j}{r}_{i+1,j}})m+D_{c_{i,j}{r}_{i+1,j}}---\left(1\right)$

对(2)式求导，并根据二次函数的性质，可知亚像素块与当前块的最小均方差为：

$\mathrm{Min}\left(D_{c_{i,j}{s}_{i,j}}\right)=\frac{{4D}_{r_{i,j}{r}_{i-1,j}}{D}_{c_{i,j}{r}_{i,j}}-{(D_{c_{i,j}{r}_{i,j}}-D_{c_{i,j}{r}_{i+1,j}}-D_{r_{i,j}{r}_{i+1,j}})}^2}{{4D}_{r_{i,j}{r}_{i+1,j}}}---\left(2\right)$

其对应的任意精度下的最优亚像素位置为：

$m_h=\frac{D_{c_{i,j}{r}_{i+1,j}}-D_{c_{i,j}{r}_{i,j}}}{2D_{r_{i,j}{r}_{i-1,j}}}+\frac{1}{2}---\left(3\right)$

其中形如D_{dx，d′x，y}的符号表示图像中左上位置点为d_x，y、d′_x，y的两个块的绝对差和，c_i，j为当前块的上点，r_i，j为整像素最优匹配块上的点，Min(D_ci，jsi，j)表示亚像素块与当前块之间的最小均方差，m_h表示最优位置。

需要指出的是：运动估计通常以均方差(MSE)或其简化形式绝对差之和(SAD)作为匹配准则，在上述的数学分析中，取MSE匹配准则进行分析。实际运动估计过程中为减少运算量通常以绝对差和SAD值取代均方差MSE。因此可以理解，本发明所述的方法也可以类似地采用SAD匹配准则。在这种情况下，式(2)、(3)中MSE值以相应的SAD值取代。

根据上述数学推导所获得的数学公式，在步骤一中需要进行的具体实施步骤如下：

(1)由式(2)分别计算当前块与R_i，j的左、右两侧的亚像素块最小绝对差和，并取两者中的最小值作为水平最小残差，记作S_h；

(2)由式(2)分别计算当前块与R_i，j的上、下两侧的亚像素块最小绝对差和，并取两者中的最小值作为垂直最小残差，记作S_v；

(3)由式(3)分别计算S_h、S_v对应的任意精度下最优亚像素位置h、v。

步骤二：根据具体应用中采用的亚像素精度，对步骤一中得到的最优亚像素位置进行近似处理，得到指定精度下的近似最优位置。

步骤一得到任意精度下的最优位置。但实际应用中，在运动估计(ME)达到一定精度后，残差系数的减少量很小，而运动矢量却占用较多比特数，从而导致最终编码比特数不再显著下降。因此，实际应用中一般采用1/2，1/4或1/8精度，如MPEG-4的ME采用1/2像素，JVT则可精确到1/8像素。为与国际标准相吻合，在实际应用中的m_h取值应该与标准中所用的搜索精度(1/2，1/4或1/8)保持一致。

由式(1)，当前块与整像素最优匹配块周围的亚像素块的绝对差和D_ci，jsi，j为亚像素位置m的二次抛物线函数，由抛物线的对称单调性可知：当指定搜索精度为1/2^K时，距离计算最优位置最近的亚像素位置为最优近似，据此得到指定精度下的一维近似最优位置m′的计算公式：

m′＝round(m_b×2^K)/2^K    (4)

其中round表示四舍五入，m_h为步骤一中得到的最优位置。如图2所示，当采用1/4像素精度、亚像素位置为9/16时取得最小绝对差和，此时与9/16最近的1/4亚像素位置是1/2，因此1/2为最优近似位置。

根据步骤一中得到的最优位置h、v及指定的搜索精度，按照式(4)计算得到该搜索精度下的近似最优位置h’和v’。

步骤三：将步骤二中的水平和垂直方向上近似最优位置合成得到二维近似最优位置。从合成得到的二维近似最优位置及前述步骤中水平和垂直方向上近似最优亚像素位置中选取处于亚像素位置的候选块，并对候选块进行搜索，获得运动估计结果。

步骤二中分别计算出水平、垂直两个一维方向上的近似最优位置，考虑到二维运动可看作水平、垂直两个一维方向上的分运动的合成，本发明中将该水平、垂直位置合成对应的二维位置块作为一个候选块。此外，考虑到该候选块的位置是一种近似结果，为提高ME的精度又将水平最优位置块S_h、垂直最优位置块中残差S_v中较小者的对应块作为另一候选块。对两个候选块中处于亚像素位置的块进行搜索匹配，并与整像素搜索结果相比较，取最优块作为最终结果。可见，本发明将侯选块减少至两个或更少，因此显著降低了开销，但是搜索速度却很快。步骤三的具体步骤如下：

(1)置候选块集合为空，若点(h’，v’)处于亚像素位置，将其对应块加入候选块集合；

(2)若S_h≤S_v且点(h’，0)处于亚像素位置，则将(h’，0)对应块加入候选块集合；转(4)；

(3)若S_h＞S_v且点(0，v’)处于亚像素位置，则将(v’，0)对应块加入候选块集合；

(4)对候选块集合中各块进行插值、搜索等运算，确定最终结果。即：通过插值计算候选块中各亚像素点的值，并计算其与当前块的绝对差和，比较其与整像素运动估计的最小绝对差和，将两者中最小值的对应位置作为最终搜索到的运动矢量。

以上公开的仅为本发明的具体实施例，根据本发明提供的思想，本领域的技术人员能思及的变化，都应落入本发明的保护范围内。

Claims (9)

1.一种快速亚像素运动估计方法，包括根据整像素运动估计得到整像素最优匹配块，其特征在于进一步包括以下步骤：

步骤一：用当前块、整像素最优匹配块及其邻近的整像素块表示当前块与整像素最优匹配块周围的亚像素块的最小均方差及其相应的最优亚像素块的位置，并根据当前块、整像素最优匹配块及其邻近的整像素块之间的关系分别计算任意精度下的水平、垂直最优亚像素块的位置；

步骤二：根据具体应用中采用的亚像素精度，对步骤一中得到的最优亚像素位置进行近似处理，得到指定精度下的近似最优位置；

步骤三：将步骤二中分别获得的水平和垂直方向上近似最优位置进行合成，得到二维近似最优位置；

所述二维近似最优位置若处于亚像素位置，将其对应块作为一候选块；并从步骤二中得到水平方向上和垂直方向上的近似最优亚像素位置中选取残差最小者，其处于亚像素位置则将其对应块作为另一候选块；

对所述候选块进行搜索匹配，并与所述整像素运动估计结果相比较，取最优块作为最终结果。

2.如权利要求1所述的快速亚像素运动估计方法，其特征在于：所述步骤一包括步骤：

(11)分别计算当前块与整像素最优匹配块左、右两侧的亚像素块之间的最小匹配误差，并取两者中的最小值作为水平最小残差；

(12)分别计算当前块与整像素最优匹配块上、下两侧的亚像素块之间的最小匹配误差，并取两者中的最小值作为垂直最小残差。

3.如权利要求2所述的快速亚像素运动估计方法，其特征在于：所述步骤一进一步包括以下步骤：

(13)根据步骤(11)和(12)中得到的水平和垂直方向上的最小匹配误差，分别计算其对应的任意精度下最优亚像素位置。

4.如权利要求2所述的快速亚像素运动估计方法，其特征在于：

所述最小匹配误差为最小均方差和最小绝对差和中的一种。

5.如权利要求1所述的快速亚像素运动估计方法，其特征在于：

所述当前块与亚像素块的最小均方差和所述当前块、整像素最优匹配块及其邻近整像素块之间的关系为：

$\mathrm{Min}\left(D_{c_{i,j}{s}_{i,j}}\right)=\frac{{4D}_{r_{i,j}{r}_{i+1,j}}{D}_{c_{i,j}{r}_{i,j}}-{(D_{c_{i,j}{r}_{i,j}}-D_{c_{i,j}{r}_{i+1,j}}-D_{r_{i,j}{r}_{i+1,j}})}^2}{{4D}_{r_{i,j}{r}_{i+1,j}}}$

所述最优亚像素块的位置与当前块、整像素最优匹配块及其邻近整像素块之间的关系为： $m_b=\frac{D_{c_{i,j}{r}_{i+1,j}}-D_{c_{i,j}{r}_{i,j}}}{{2D}_{r_{i,j}{r}_{i+1,j}}}+\frac{1}{2}$

其中形如D_{dx，yd′x，y}的符号表示图像中左上位置点为d_x，y、d′_x，y的两个块的绝对差和，c_i，j为当前块上的点，r_i，j为整像素最优匹配块上的点，Min(D_ci，jxi,j)表示亚像素块与当前块之间的最小均方差，m_b表示最优位置。

6.如权利要求1所述的快速亚像素运动估计方法，其特征在于：

所述步骤二中的对步骤一中得到的最优亚像素位置进行近似处理，包括：当指定搜索精度为1/2^K时，一维近似最优位置m′与步骤一中得到的最优位置m_b间关系为：m′＝round(m_b×2^K)/2^K，其中，round()表四舍五入，由此得到近似最优位置。

7.如权利要求1所述的快速亚像素运动估计方法，其特征在于：

所述步骤三中从二维近似最优位置及水平和垂直方向上近似最优亚像素位置中选取处于亚像素位置的候选块，包括：

1)若二维近似最优位置对应块处于亚像素位置，则将其作为一个候选块。

2)判断水平方向近似最优位置和垂直方向近似最优位置对应的最小绝对差和，如果水平方向近似最优位置对应的最小绝对差和较小，则进一步判断水平方向近似最优位置是否在亚像素位置，如果是，则选定水平方向近似最优位置对应块为候选块；如果垂直方向近似最优位置对应的最小绝对差和较小，则进一步判断垂直方向近似最优位置是否在亚像素位置，如果是，则选定垂直方向近似最优位置对应块为候选块。

8.如权利要求7所述的快速亚像素运动估计方法，其特征在于：

所述步骤三还包括：通过插值计算候选块中各亚像素点的值，并计算该块与当前块的最小绝对差和，并与整像素运动估计得到的最小绝对差和进行比较，将两者中较小值的对应位置作为最终搜索到的运动矢量。

Images