用于视频压缩的基于超完备基变换的运动残余帧编码方法和装置

摘要

本发明提供了一种利用改进的匹配跟踪算法、基于超完备基变换压缩数字运动图像或视频信号的方法。更具体而言，本发明的焦点集中在运动残余图像的有效编码上，运动残余图像是通过运动估计和补偿过程生成的。残余能量分割算法(RESA)可用来获得对残余图像中高能量区域的形状和位置的初始估计。逐次消除算法(PEA)可用来减少匹配跟踪过程中匹配评价的数量。RESA和PEA可将编码器从预先规定的过完备基字典中搜寻匹配基的速度加快许多倍。匹配模式的三个参数生成一个原子，该原子定义进入字典的索引、所选基的位置以及所选基模式与残余信号之间的内积。本发明提供了一种利用类似四叉树的技术的新原子位置编码方法和一种新的原子模量化方案。提供了用于量化和位置编码设计的、简单有效的自适应机制，以使根据本发明的系统能在低级介质和高比特率情形下正常运行。与先前基于匹配跟踪的视频编码器相比，这些新算法成员可使编码过程更快以及改进压缩性能。

说明书

发明领域

本发明涉及压缩领域，尤其涉及视频压缩方法和装置。

发明背景

当图像序列以非压缩数字形式表示时，可能占用巨大的存储空间，并需要极高的传输带宽。几年前，随着计算机网络和信号压缩技术的进步，点对点数字视频通信变得可实行。

针对数字视频压缩的标准化工作大概于1988年启动。目前，1SO/IEC下属的运动图像专家组(MPEG)委员会已完成了MPEG-1和MPEG-2标准；MPEG-4标准也已经完成，但仍在接受新的提议。此外，CCITT提出了一系列建议-H.261、H.262和H.263+-其焦点集中于低比特率应用。所有这些标准化的尝试都是利用两步程序来压缩视频序列。第一步利用运动估计和补偿算法，用前一视频帧建立当前视频帧的预测视频帧，其中计算当前视频帧与预测视频帧之间的差，该差被称为运动残余图像(MRP)。标准程序的第二步是利用离散余弦变换(DCT)将MRP编码。像这种基于DCT的系统并非在所有情形下都表现良好。在个人视频通信所需的低比特率下，基于DCT的系统会引起显著的失真和可见的区块效应(blockartifact)。对于像DVD这样的高质量可视应用，所获得的压缩率可能相当低。

运动残余图像可利用基于其他变换的技术进行编码。例如，也可使用离散小波变换(DWT)和超完备基变换。Zakhor和Neff在美国专利No.5,699,121中提出了基于被称为匹配跟踪(matching pursuit)的超完备基变换算法的运动残余编码系统。这由Mallat和Zhang在IEEETransaction in Signal Processing，第41卷，第12期，1993年12月，中首次提出。与基于标准DCT的视频编码器相比，Zakhor和Neff的视频编码器改善了视频质量和PNSR。但是，他们的系统很慢，并且由于针对匹配基位置编码和变换系数的量化的特定设计，其压缩性能不是最优化的。因此，需要一种基于新的超完备(overcomplete)变换的视频编码方法，其能提供速度和效率。

提供该背景信息，目的是使申请人认为可能与本发明有关的信息已知。并非意味着，也不应该解释成，任何前述信息构成本发明的现有技术。

发明内容

本发明的目的是提供一种用于视频压缩的、基于超完备基变换的运动残余帧编码方法和装置。根据本发明的一个方面，提供了一种利用来自过完备库的基函数将残余图像编码的方法，所述方法包括步骤：获得残余图像，所述残余图像具有尺寸和能量；以及，将所述残余图像分解成一个单原子或多原子列表(list)，每个原子代表来自过完备库的一个基函数，所述将所述残余图像分解的步骤包括步骤：(i)利用残余能量分割算法，识别残余图像中的替换区域供用原子表示；(ii)建立来自过完备库的基函数子集，子集中的每个基函数在预定阈值内与替换区域匹配；(iii)识别基函数子集内的原子，所述原子用于表示替换区域，并且所述原子具有参数；(iv)量化所述原子，并将原子的参数调整成一种适于编码的形式；(v)将所述量化原子编码，从残余图像中的替换区域中减去所述原子，从而减小残余图像的能量并利用基于四叉树(quadtree)的原子编码器减小残余图像的尺寸；以及，(vi)将残余图像的减小尺寸或残余图像的减小能量与预定标准比较，并重复步骤(i)-(vi)直到达到预定标准；从而将所述残余图像编码并将其尺寸减小到预定水平。

根据本发明的另一方面，提供了一种利用来自过完备库的基函数将残余图像编码的装置，所述装置包括：获得残余图像的装置，所述残余图像具有尺寸和能量；和，将所述残余图像分解成一个单原子或多原子列表的装置，每个原子代表来自过完备库的一个基函数，所述将所述残余图像分解的装置包括：(i)利用残余能量分割算法、识别残余图像中的替换区域供用原子表示的装置；(ii)建立来自过完备库的基函数子集的装置，子集中的每个基函数在预定阈值内与替换区域匹配；(iii)识别基函数子集内的原子的装置，所述原子用于表示替换区域，并且所述原子具有参数；(iv)量化所述原子、并将原子的参数调整成一种适于编码的形式的装置；(v)将所述量化原子编码、从残余图像中的替换区域中减去所述原子、从而减小残余图像的能量并利用基于四叉树的原子编码器减小残余图像的尺寸的装置；以及，(vi)将残余图像的减小尺寸或残余图像的减小能量与预定标准比较的装置；从而将所述残余图像编码并将其尺寸减小到预定水平。

根据本发明的另一方面，提供了一种包括计算机可读介质的计算机程序产品，计算机可读介质具有记录在其上的计算机程序用于执行利用来自过完备库的基函数将残余图像编码的方法，所述方法包括步骤：获得残余图像，所述残余图像具有尺寸和能量；以及，将所述残余图像分解成一个单原子或多原子列表，每个原子代表来自过完备库的一个基函数，所述将所述残余图像分解的步骤包括步骤：(i)利用残余能量分割算法，识别残余图像中的替换区域供用原子表示；(ii)建立来自过完备库的基函数子集，子集中的每个基函数在预定阈值内与替换区域匹配；(iii)识别基函数子集内的原子，所述原子用于表示替换区域，并且所述原子具有参数；(iv)量化所述原子，并将原子的参数调整成一种适于编码的形式；(v)将所述量化原子编码，从残余图像中的替换区域中减去所述原子，从而减小残余图像的能量并利用基于四叉树的原子编码器减小残余图像的尺寸；以及，(vi)将残余图像的减小尺寸或残余图像的减小能量与预定标准比较，并重复步骤(i)-(vi)直到达到预定标准；从而将所述残余图像编码并将其尺寸减小到预定水平。

附图简述

图1图解了利用根据本发明的一个实施方案的超完备基变换和相关编码方法的视频压缩系统的总图。

图2是本发明的一个实施方案所处理的运动残余图像的例子。

图3图解了供本发明的一个实施方案使用的、具有16个基(base)的简单字典。

图4描述了基于根据本发明的一个实施方案的超完备基的整个原子分解过程。

图5描述了根据本发明的一个实施方案的残余能量分割算法(RESA)所执行的基本步骤。

图6图解了根据本发明的一个实施方案的RESA的第一步。

图7图解了根据本发明的一个实施方案的RESA的第二步：水平生长(grow)方案。

图8图解了根据本发明的一个实施方案的RESA的第三步：垂直生长方案。

图9描述了利用根据本发明的一个实施方案的逐次消除算法(PEA)的匹配跟踪原子搜索。

图10图解了如何形成根据本发明的一个实施方案的匹配基和搜索位置候选的子字典。

图11图解了根据本发明的一个实施方案的区域能量的快速计算。

图12图解了根据本发明的一个实施方案的一个原子的参数。

图13是根据本发明的一个实施方案的原子位置图(map)的例子。

图14是说明根据本发明的一个实施方案的原子编码过程的流程图。

图15是说明根据本发明的一个实施方案的压缩残余信号的解码的流程图。

具体实施方式

本发明是针对基于超完备变换的残余图像编码的新编码器，用于运动补偿视频压缩系统中。本发明与早先的匹配跟踪视频编码器类似，它们都将残余图像分解成原子列表，原子代表来自过完备字典的基函数。不过，原子搜寻过程是利用残余能量分割算法((Residual EnergySegmentation Algorithm)RESA)和逐次消除算法((ProgressiveElimination Algorithm)PEA)实现的。为描述在运动残余图像中频繁出现的特征的特性，基字典可能非常大。为了搜寻原子，RESA识别运动残余图像中具有高能量的区域的大致形状和位置，以便可通过与字典中的较小基子集比较来找到良好匹配。而且，PEA通过预计算搜索窗口的能量从考虑项中逐次去掉模式候选，从而缩短了找到最好匹配所需的计算时间。一找到匹配原子，就通过去掉以该原子为特征的部分来更新残余图像。重复前述搜寻原子和更新残余图像的步骤直到达到所需的压缩比特率或质量。

本发明提出了一种新的模量化方案用于借助超完备基进行匹配跟踪，其改变了原子搜寻过程。直接从变换产生的系数是连续浮点值，需要量化用于在一比特预算下进行最佳数字编码。在匹配跟踪算法中，有必要使用环内量化器(in-loop quantizer)-其中每个被找到的原子先被量化，然后被用来更新残余图像。照这样，每个原子会影响后续原子的选择。如果，同在早先的匹配跟踪方法中所进行的一样，在编码开始之前就规定量化器，则难以使量化方案最优化，因为最佳量化器设计取决于所选原子模列表的统计(statistics)。本发明的量化方案在原子搜索过程中自适应地选择量化器。

除原子模以外，所选基的索引和原子的位置也需要在基于超完备变换的编码器中传输。本发明包括一种将原子位置信息有效编码的方法。原子位置分布形成2D图，其中像素值1和0分别表示各个位置有原子或没有原子。类似四叉树的技术使得将位置图编码成为可能。模和基索引信息被嵌入位置编码中。不同的彩色视频通道(Y，U，V)的原子独立编码。

所有原子参数先被编码成残余图像的压缩形式，然后被传输。对于解码过程，解码器通过将编码比特流译码为原子参数并将原子信息组合起来形成残余图像的重建流，重建残余图像，然后残余图像与运动补偿图像组合形成重建视频流。

本发明是将运动残余图像编码的方法，该方法包括步骤：利用改进的匹配跟踪算法在超完备基空间形成残余图像的原子分解；选择模量化器；将原子位置图、模以及所选基的索引编码。本发明还提供将利用以上编码方法编码的残余信号解码的方法。

图1图解了视频压缩装置10所执行的相关处理，视频压缩装置10利用了根据本发明的一个实施方案的残余图像编码器20。视频帧最初由运动估计器30处理，运动估计器30将当前帧与一个或两个参考帧进行比较。在大多数情况下，在相继帧中，视频中的物体会改变它们的位置，而背景保持不变。因为参考帧已被传输给视频解码器12，所以参考帧中的一些区域可用来构造当前帧。运动估计器30识别参考帧内那些与当前帧内的区域类似的区域。运动补偿器32产生那些相似区域的差，并将它们组合成运动残余图像。相似区域之间的位置关系用运动矢量表示，运动矢量由运动矢量编码器34处理。首先原子分解器40处理残余图像，然后原子编码器42压缩所得的原子。编码运动矢量和原子由多路复用器22组合成一个比特流。压缩视频由装置24传输或存储起来，装置24可将压缩格式的视频输送给视频解码器12。

图1的下部图解了解码器12，其中多路分解器26分离压缩视频信号，将相应的比特分别发送给运动矢量解码器36和残余图像解码器28。运动重建器38根据参考帧和运动矢量生成预测帧。残余图像解码器28重建残余图像。这两个信号，即预测帧和残余帧，相加产生最终的重建视频帧。

图2是Y彩色通道的运动残余图像的例子。原始残余图像既有正值又有负值。为了将残余图像适当地显示为256级灰度图像，将残余图像中的像素值进行平移和缩放(scaled)使得纯灰表示零，黑色和白色分别表示负值和正值。例如，残余图像包括若干个高能量区域，这若干个高能量区域对应视频中物体的运动。

大多数信号压缩技术通过不同类型的数学变换将原始数据变换成某种更紧凑的格式。一些数学变换，如DCT和DWT等，利用完备基，完备基形成一个可逆变换矩阵。最近，超完备基和相关的变换算法受到了相当的注意。超完备基字典中基的数量比原始数据的维大得多。超完备基的好处是变换系数在表示原始信号中的真实特征方面更有效。有许多种数学方法可为不同的信号建立基字典。已经设计了几种针对视频运动残余图像的字典，并已证实它们很好地包含了残余图像中的特征。例如，基于可分加博函数(separable Gabor function)的基字典由Neff和Zakhor在“Very Low Bit Rate Video Coding Based on MatchingPursuits”，IEEE Transactions on Circuits and Systems for VideoTechnology，1997年2月，158-171，一文中进行了描述，基于Haar函数的基字典由Vleeschouwer和Macq在“New dictionaries formatching pursuit video coding”，Proc.of the 1998 InternationalConference on Image Processing，第1卷，764-768，中进行了描述。图3是包含16个基的简单示例字典。任何上述字典都可用于本发明。特别注意上面提及的加博字典，其中明确提到了400个2D函数。然而，因为这400个2D函数中的每一个都可放在图像内的所有可能位置上，所以它实际上隐含地包括许多基结构。若利用176×144像素的帧尺寸，则意味着该字典实际上包括400×176×144＝5.7百万个基结构—这使得该字典是高度超完备的。若直接利用由S.Mallat和Z.Zhang在“MatchingPursuits With Time-Frequency Dictionaries”，IEEE Transaction inSignal Processing，第41卷，第12期，1993年12月，一文中描述的“匹配跟踪算法”进行变换，将需要极其大量的计算来确定变换系数。Zakhor和Neff为发明人的、美国专利No.5,699,121中的用于视频压缩的匹配跟踪虽然减轻了计算负担，但计算上仍是昂贵的。本发明提供了一种基于总(general)字典变换残余图像的方法以及一种将变换系数编码的方法，前者由原子分解器40执行，后者由原子编码器42执行。

在图4中将根据一个实施方案详尽描述原子分解器40的操作。原子分解器40执行的第一步(块61)是搜寻起始搜索区域。这一步利用残余能量分割算法(RESA)实现，其中RESA的一个实施方案在图5中示出。RESA基于总区域生长思想。它首先选择一个2×2区块作为区域生长的起始点(块70)。这步需要将残余图像分成16×16个区块，如图6所示。计算每个区块的能量，即所有像素强度的平方和，并将具有最高能量的区块识别为例如图6中示出的区块71。进一步将区块71分成4个8×8子区块，并识别出具有最高能量的子区块72。在该8×8子区块72内，识别出能量最高的2×2区块73，其中这个区块将被用作区域生长的起始点。

RESA的下一步(图5中示出的块74)是检查位于当前区域左侧的2×2区块。图7图解了RESA的这一步骤。将阈值动态计算为：

T＝AE*max(7-AU，5)/10

其中，AU是起始区块左侧已累加区块的数量，AE是当前区域的每2×2区块的平均能量。如果所检查的2×2区块的能量大于当前阈值，则将所测试的2×2区块与当前区域合并在一起，形成一个更大的新当前区域。否则，找到了这一侧的停止点，而不将区块合并在一起。以一种类似的对称方式，检查位于当前区域右侧的2×2区块。首先在左侧继续生长，然后在右侧继续生长，直到找到两侧的停止点或者矩形宽度达到32(无论哪种情形先出现)。完成这步之后，会形成水平带矩形75，其中带的尺寸为2*2m，1＜＝m＜＝16。

RESA的最后一步(图5中的块76)是以带75为基础垂直地生长区域，如图8所示。假设带75的宽度是W。结合阈值，考虑当前区域上方的2*W带矩形：

Ts＝AEs*max(7-AUs，5)/10

其中AUs是已累加在起始带上方的2*W矩形的数量，AEs是包含在当前区域中的每2*W矩形的平均能量。如果所测试的2*W矩形具有的能量大于阈值，则将其合并到当前区域中。否则，找到了这一侧的停止点。以一种类似的对称方式，检查位于当前区域下方的2*W矩形。首先在上方继续生长，然后在下方继续生长，直到找到两侧的停止点或者当前区域的高度达到32(无论哪种情形先出现)。最后，我们得到矩形77，其尺寸为2n*2m，1＜＝n，m＜＝16。

再参照图4，其图解了从给定字典中搜寻最接近匹配基的过程(块62)。基与残余图像之间的匹配度用它们的内积的绝对值(模)表示，该模称为原子模，其中大的模表示良好匹配。确定该模的过程需要计算许多次内积，以及选择具有最大模的内积作为当前原子。这个过程可能是匹配跟踪算法中最慢的部分。在经典匹配跟踪算法中，需要通过计算残余图像与字典中数百万个元素中每一个元素之间的内积来确定模。在现有技术中，例如，简单地选择残余图像中具有最高能量的16*16区块作为起始搜索区域—每个基结构以所选区块中的各个位置为中心，计算基结构与对应的残余区域之间的内积。对具有400个基的字典来说，这个过程需要进行256×400＝102400次内积计算。图9图解了根据本发明的新匹配跟踪过程。

图8中作为结果产生的RESA矩形为高能量特征的形状提供初始估计。它用来过滤掉字典中形状与RESA矩形大不相同的基。然后形成匹配基候选子集(块80)。假定矩形77的宽度和高度分别为w和h，则形成的子字典包含形状分别由width(宽度)和height(高度)规定时满足以下条件的所有基：

w-tw1＜＝width＜＝w+tw2且h-th1＜＝height＜＝h+th2

其中tw1、tw2、th1和th2为被设置用以限制基尺寸的值。这些值可根据字典结构进行变化和调整。被测试基的最大和最小尺寸在图10中用矩形90和91示出。例如，区块B80是包含四个基的简单子字典的例子。

RESA还能估计残余图像中高能量特征所在的位置。围绕RESA矩形77的中心选择匹配基的位置候选(块81)。图10示出了小矩形92，其中心与RESA矩形77的中心相同。假设矩形92中的所有像素都将充当被测试残余图像的中心。图10中的矩形94是一个以点93或矩形92的左上角为中心的例子。假设矩形92的宽度(ws)和高度(hs)可随RESA矩形77变化。关系为：

ws＝2*min(w/2+1，6)且hs＝2*min(h/2+1，6)

在一种实现方法中，矩形92的尺寸可通过其他准则确定或者简单地是固定的。基本思想是良好匹配位于RESA矩形77的中心附近。而且，矩形92内已经包含原子的中心的所有位置都不会被考虑用于任何新原子。图10中的点95就是一个例子。应该注意到，现有技术没有施加这样的限制。这种限制的思想是：如果一个原子提供了良好拟合，它理应移走围绕其中心的能量而不会在它的边界上引入过多额外能量。同样地，不期望匹配跟踪算法回到同样的位置产生第二原子。这一强迫无位置重复的限制几乎对编码性能没有影响，并能使原子位置信息的编码更简单。

下一个处理步骤(图9的块89)称为用于残余匹配跟踪的逐次消除算法(PEA)。它与用来形成测试基子字典和测试位置集的方法无关。例如，如果子字典是整个字典且位置候选集是包括整个残余图像的候选集，PEA将仍然起作用。PEA是一种更有效地搜寻最接近匹配基的方法，其通过从考虑项中逐次地去掉比较候选进行搜寻。这与经典匹配跟踪形成对照，经典匹配跟踪是在所有可能位置比较所有基候选。首先，将最大模Mm设为零(块82)。接下来，考虑基b(k，1)(块83)，其中k和1表示2D基函数的宽度和高度。在残余图像中以一个位置候选为中心形成相同尺寸的区域r(k，1，p)。块85将r(k，1，p)的能量||r(k，1，p)||与当前最大模(Mm)进行比较以确定是否需要计算r(k，1，p)与b(k，1)之间的内积。为了解释这一操作，回忆一下数学三角不等式：

|<r(k，1，p)，b(k，1)>|＜＝||r(k，1，p)||||b(k，1)||

匹配跟踪的目的是找到最大值|<r(k，1，p)，b(k，1)>|。假定当前最大模是Mm。如果，对于位置p处的基b(k，1)，对应的残余r(k，1，p)满足||r(k，1，p)||||b(k，1)||＜＝Mm，则：

|<r(k，1，p)，b(k，1)>|＜＝||r(k，1，p)||||b(k，1)||＜＝Mm

在这种情况下，没有必要计算内积<r(k，1，p)，b(k，1)>，并将区域r(k，1，p)移到下一个位置。基||b(k，1)||的范数(norm)可事先计算(实际上大多数基都是归一化的，即||b(k，1)||＝1)，这一测试的唯一开销是计算r(k，1，p)的能量。确定||r(k，1，p)||的有效算法在下面描述。

假设有n个大小不同的基高度{v₁，v₂，…，v_n}和m个大小不同的基宽度{h₁，h₂，…，h_m}，它们递增排列。搜索矩形尺寸为hs*ws，搜索矩形的左上点为p(x，y)。通过以下四步可计算hs*ws*n*m个能量值。

步骤1：计算s＝h_m+k列的能量(图11示出了列的例子)。这些列的中心位于(x-h_m/2+i，y)，i＝0，1，2，…，s-1。它们的高度为v₁。它们的能量表示为C_1，0(0)，C_1，1(0)，…，C_1，s(0)，计算如下：

C_1，i(0)＝e(x-h_m/2+i，y-v₁/2)+…+e(x-h_m/2+i，y)+…+e(x-h_m/2+i，y+v₁/2)

其中e(x，y)表示位置(x，y)处像素的能量。

可计算具有与上面的带相同的坐标和长度v₂的下一个s列的能量：

C_2，i(0)＝C_1，i(0)+Extra(v₂-v₁)Pixels Energy，i＝1，2，…，s

一般地，我们得到：

C_j，i(0)＝C_j-1，i(0)

+Extra(v_j-v_(j-1))Pixels Energy，i＝1，2，…，s；j＝1，2，…，n

步骤2：计算相对步骤1中的列垂直平移的列的能量，如下：

C_j，i(a)＝C_j，i(a-1)+e(x-h_m/2+i，y-v₁/2+a-1)+e(x-h_m/2+i，y+v₁/2+a)，a＝1，…，hs

其中a表示与y对应的垂直平移量。

步骤3：计算具有高度vj，(j＝1，…，n)、宽度h₁，h₂，…，h_m以及中心(x，y+a)，(v＝0，1，…，hs)的区域的能量，如下：

S_j，1(0，a)＝C_{j，(hm-h1)/2}(a)+…+C_j，hm/2(a)+…+C_{j，(hm+h1)/2}(a)

S_j，2(0，a)＝S_j，1(0，a)+Extra(h₂-h₁)columns’energy一般地，

S_j，i(0，a)＝S_j，i-1(0，a)+Extra(h_i-h_(i-1))columns’energy，i＝1，…，m

步骤4：计算具有垂直基长度vj，(j＝1，…，n)、水平基长度h_i，(i＝1，…，m)以及中心(x+b，y+a)，(b＝1，…，ws且a＝1，…，hs)的第一区域集的能量，如下：

S_j，i(b，a)＝S_j，i(b-1，a)-C_{j，(hm-hi)/2+b-1}(a)+C_{j，(hm+hi)/2+b}(a)

最大模可在匹配跟踪过程中连续更新；这能逐次地限制搜索空间。若干个基可能具有相同的尺寸，因而一次能量计算可避免若干次内积计算。PEA的性能还与多快找到良好匹配(未必是最好匹配)有关。因为大区域总是包含较多能量，所以首先测试较大尺寸的基。

如果||r(k，1，p)|1＞Mm，则执行块86以计算r(k，1，p)与b(k，1)之间的内积(p)。块87将p的绝对值与当前最大模Mm进行比较。如果|p|＞Mm，则将新Mm设为|p|，并记录对应的基索引和位置。不管怎样，我们始终返回块84直到检查完所有搜索位置。然后，重复运行块83-块88，直到测试完所有基候选。最后，产生一个原子，该原子包括三个参数：1.字典中给出最好匹配的基的索引；2.用(x，y)坐标表示的最好匹配在残余图像中的位置；以及，3.基与残余图像之间的内积(p)。图12示出了残余图像上一个原子的例子。

再参照图4，找到原子之后的步骤是记录原子参数(块63)。注意到，在这个阶段，不对原子的模进行量化。决策块64将决定何时开始进行原子量化。它的操作取决于视频压缩系统所定义的比率(rate)控制目标。如果压缩率是固定的，则块64将检查是否还有比特可用于更多原子。因为尚未完成实际编码，所以必须估计编码当前原子所用的比特。设“Bip”表示用于编码基索引和位置的平均比特，“Bm(i)”表示第i个原子的模不量化所用的实际比特。若为内积(p)的符号分配一个比特，则估计n个原子所用的比特为：

Used Bits＝n*(Bip+1)+∑(Bm(1)+Bm(2)+…+Bm(n))

其中“Bip”根据第一残余帧的经验数据进行初始化，并将其设为最近(last)帧的实际值。每个模的Bm(i)可以是精确已知的。一个重要事实是：随后模将被量化，并会导致待使用的比特比当前估计的少。因而，在这个阶段，原子数一般比能编码的原子少。如果视频系统希望达到一定的质量，该质量由编码残余图像与实际残余图像相比的均方差(MSE)定义，则块64将达到的当前MSE与MSE目标进行比较。引入一个原子后，根据以下等式更新MSE：

MSE(n)＝MSE(n-1)-p(n)*p(n)

其中MSE(n)表示使用n个原子后的MSE，p(n)表示第n个原子的内积。最初，将MSE或MSE(0)设为原始残余图像的能量。进行量化后，MSE(n)很可能增加，因此将不再满足MSE目标。总之，如果有比特可用或者尚未达到质量目标，则基于当前原子更新残余图像(块65)，接着在块61重新开始以搜索另一个原子。否则，如果实现了比特或质量目标，则执行块66进行量化设计。残余图像更新，标准匹配跟踪算法的一个步骤，可在数学上描述为：

r(k，1，p)＝r(k，1，p)-p(n)*b(k，1)

当前原子未覆盖的所有区域将不改变。

量化器的设计(块66)基于到目前为止找到的最小模(Minm)值进行。量化步长(QS)设为：

利用上面的QS以一种简单的中等读数(mid-read)标量量化方案，对到目前为止找到的所有原子进行量化。接下来，根据现在的原子模量化列表再更新残余图像67。假定量化前后的原子系数分别为p(i)、q(i)，(i＝1，2，…，n)。假定对应的基为b(i)，(i＝1，2，…，n)。引入n个未量化原子之后的残余图像是：

E(n)＝(0riginal Residual)-p(1)b(1)-p(2)b(2)-…-p(n)b(n)它的能量||E(n)||也是已知的。有两种方法计算量化后的残余能量。第一种方法是简单地将量化后的残余图像计算为：

EQ(n)＝(0riginal Residual)-q(1)b(1)-q(2)b(2)-…-q(n)b(n)另一种方法是递归地更新残余图像。假定p(i)的量化误差是Δp(i)。那么，仅p(n)被量化时的残余图像是：

EQ(1)＝E(n)-Δp(n)b(n)且

||EQ(1)||＝||E(n)||+Δp(n)*Δp(n)-2Δp(n)<E(n)，b(n)>p(n)和p(n-1)被量化时的残余变为：

EQ(2)＝EQ(1)-Δp(n-1)g(n-1)这一关系是真正递归的，可写作：

EQ(i)＝EQ(i-1)-Δp(n-i+1)g(n-i+1)，i＝l，2，…，n，EQ(0)＝E(n)对应的能量为：

||EQ(i)||＝||EQ(i-1)||+Δp(n-i+1)Δp(n-i+1)-2*Δp(n-i+1)<EQ(i-1)，g(n-i+1)>最后，我们将得到EQ(n)和||EQ(n)||，这是进一步搜寻原子的起始点。重要的是，原子列表可以任何顺序进行递归更新—不需按找到原子的顺序进行更新。

因为原子的模已被量化，所以，现在为达到比率控制或质量目标更多原子将是必要的。因此，执行块68以找到附加原子。过程与块61-63相同。不过，在这个阶段，原子模将立即被量化。现在，我们需要处理模小于(QS-QS/4)的原子，而不是通过将它们的量化值设为零而不显示(throw out)它们。所使用的方案如下：

1.如果原子模大于(QS-QS/4)，则量化器在使用QS；

2.否则，如果原子模大于(QS/2-QS/8)，则将其量化为值QS/2；

3.否则，如果原子模大于(QS/4-QS/16)，则将其量化为值QS/4；

4.否则，如果原子模大于(QS/8-QS/32)，则将其量化为值QS/8。

实际上，一般来说，向下有三个层次就足够了，不过可使用更多个层次。

执行块68后，执行实际比率控制逻辑单元(块69)。在这个阶段，因为对原子进行环内量化，所以可估计达到的质量或使用的实际比特数。当达到压缩目标时，系统将进入原子编码器42。否则，将基于量化原子模更新残余图像，并且系统将返回块68以搜寻下一个原子。对于彩色视频，残余图像包括几个通道，即Y、U和V通道。将针对每个通道独立使用原子分解器40。用这种方案，每个通道可具有它自己的比特预算或期望质量目标。有一些比特分配方法，可用来为不同通道分配比特预算。

所有原子被传给原子编码器42供以压缩形式输出。本发明将每个通道的原子分布看作双值(bi-value)图，如图13所示。黑色像素代表其相应位置的原子，白色像素代表其所在的位置没有原子。可使用类似四叉树的技术将包含原子的位置编码，不过，容易理解的是，也可使用其他技术进行编码。在编码原子位置信息之后，可利用例如可变长度编码将每个原子的其他参数编码，不过，如本领域的技术人员所知晓的，也可使用其他编码方法进行。原子参数信号的编码过程在图14中示出，下面将作更详细的描述。

原子编码的第一步是将整个原子图分解成，例如，图13所示的n*n区块(块101)。值n可为16(对于Y通道)或8(对于U和V通道)。对于每个n*n区块，如果区块中没有原子，则输出零比特；否则，输出1比特，并进一步处理该区块以将原子定位(locate)到解码器中。四叉树分解过程供该目的使用，归纳为以下四步：

步骤1.用一个元素-n*n区块本身，将原子区块列表(LAB)初始化。

步骤2.从LAB中挑选一个元素e。如果e的尺寸是1*1，则输出除位置以外的所有原子参数：即基索引、模和e的内积符号，然后进行步骤4；否则，进行步骤3。

步骤3.输出e的四个子区块的原子模式比特：a1a2a3a4，其中如果对应的子区块中有原子，则ai(i＝1，2，3，4)为1，否则为零。将所有ai值等于1的子区块i放到LAB的末尾，回到步骤2。

步骤4.检查LAB是否为空。如果非空，则返回步骤2；否则结束所述一个n*n区块的编码。

基索引和原子模可利用可变长度编码器进行编码以节省比特，因为这些信号参数可能不是均匀分布的。通过用0/1比特数据记录分解过程，可对原子位置信息进行隐含编码。可利用可变长度编码方法来编码四个子区块的原子模式比特：a1a2a3a4。原子模式比特a1a2a3a4有15种模式，其中应该注意到0000是不可能的。然而，有些模式，如1000等，发生的概率比其他模式高。不同模式的概率可通过实验进行估计，并用来创建可变长度表设计。此外，应该注意到，对于不同的通道和不同的原子密度，概率分布是可变的。因此，可使用多个表，并可首先将区块的类别信息编码以使解码器知晓应该用哪个表进行解码。

图15图解了原子解码器46，其执行的操作与原子编码器42所执行的操作相反。首先，原子解码器46接收一个表示当前n*n区块的状态的比特。如果值为1，则通过对称的四叉树分解过程进行处理。最初，将n*n区块分成四个子区块。利用逆向可变长度编码(VLC)，将四个子区块的原子模式比特解码。然后，将所有值为1的子区块放到原子区块表(LAB)中。通过递归地分解LAB中的每个元素并获得其原子模式比特，动态更新LAB。如果来自LAB的元素是1*1区块，则应利用逆向VLC表将原子基索引和模解码；然后，应写入表示内积符号的比特。如果LAB变空，则原子编码器结束对一个n*n区块的解码。

然后将解码原子参数信号传给残余重建器48，其利用经典匹配跟踪方法逐个通道地形成残余图像。最初，将残余图像中的所有像素设为零。然后，利用如下过程将各个原子逐个累加：设q(i)和b(i，k，1)分别表示第i个原子系数和对应的2D基矩阵。如果(x(i)，y(i))表示第i个原子的位置，则在位置(x(i)，y(i))处将矩阵q(i)*b(i，k，1)增加到目前为止所构造的残余图像中，以得到新的当前残余图像。重复该过程直到累加了该通道的所有原子。一旦各个通道被分解完，该过程就结束，残余图像得以被重建。

那些熟悉先前基于匹配跟踪的视频编码技术的人将会认识到与本发明的方法有关的许多优点。通过更准确的能量区域估计过程和逐次候选消除算法，加快了基于超完备基空间的原子分解过程。原子模量化器设计是利用原子分解方案进行无缝选择得到的，而早先的技术在变换开始之前就规定了量化器。最后，因为借助所发明的基于四叉树的分解方案利用了原子之间的空间关系，所以原子编码过程更有效。特别是，现有技术将所有原子收集到一个1D列表中，从而使得与本发明相比，更难将它们有效编码。

既然这样描述了本发明的实施方式，显然所述实施方式可以多种方式进行改变。这样的变更不被视为脱离本发明的精神和范围，并且旨在所有这些对本领域的技术人员而言明显的变型都落入以下权利要求的范围内。