重叠双正交变换的可逆二维前置/后置滤波方法

摘要

使用用于在相对于核心变换的交错网格上应用的前置/后置滤波的可逆二维重叠算子实现可在数字媒体编解码器中使用的有效重叠变换。该二维重叠算子基于可分离地应用的一维可逆重叠算子，它被重新排列为各个块的点的子集上交错的级中的一系列初等变换，并且为了计算效率也在提升步骤中实现。交错的级包括在涉及归一化2×2阿达马变换的初始和最后的级之间应用旋转和比例缩放级。

说明书

本申请是申请人于2005年12月14日提交的、申请号为“200510131668.0”的发明名称为“用于重叠双正交变换的可逆二维前置/后置滤波”的发明专利申请的分案申请。

相关申请信息

本申请是Tu等人2004年12月17日提交的名为“Reversible Overlap OperatorFor Efficient Lossless Data Compression(用于有效无损数据压缩的可逆重叠算子)”的美国专利申请第11/015,148号的部分延续，该申请通过引用结合于此。

技术领域

本发明一般涉及使用重叠变换的数字媒体(例如，视频和图像)压缩。

背景技术

重叠变换

重叠变换是一种用于数据压缩的强大的信号处理技术。参见例如H.S.Malvar的Signal Processing with Lapped Transforms(使用重叠变换的信号处理)，Boston，MA：Artech House，1992。然而，至今为止，从未对无损(可逆)数据压缩公式化或应用具有线性相位的有效重叠变换。

如下文更详细地讨论的，已知重叠变换可以用公式表示为前置滤波器其后跟随数据变换(其逆为数据逆变换其后跟随后置滤波器)。见例如H.S.Malvar的“Apre-and post-filtering technique for the reduction of blocking efficets”(用于降低块效应的前置和后置滤波技术)，Proc.Picture Coding Symposium，Stockholm，Sweden，(瑞典斯德哥尔摩图像编码研讨会会刊)1987年6月；以及T.D.Tran、J.Liang和C.Tu的“Lapped Transform via Time-Domain Pre-and Post-Filtering”(通过时域前置和后置滤波的重叠变换)，IEEE Trans.on Signal Processing(关于信号处理的IEEE论文集)第51卷，第6期，2003年6月。可在这一公式中使用无损数据变换以实现较佳的可逆性测量。迄今为止，相信仅可选择某些受限的多种前置和后置滤波器用于可逆性。这一受限的集合在其压缩(码率与失真的关系，或R-D)性能方面是非常有限的。在近来的论文中(W.Dai和T.Tran的“Regularity-constrained pre-andpost-filtering for block DCT-based system”(用于基于块DCT的系统的正则性受限的前置和后置滤波)，IEEE Trans.on Signal Processing(关于信号处理的IEEE论文集)第51卷，第2568-2581页，2003年10月)，提出了一种构造，其中大多数元素是可逆的，且具有良好的压缩特性。

在音频压缩中，引入了若干用于可逆重叠变换的构造。见例如R.Geiger、J，Herre、J.Koller和K.Brandenburg的“IntMDCT-A link between perceptual andlossless audio coding”(IntMDCT-感知和无损音频编码之间的连接)，Proc.IEEEInt.Conf.on Acoustics，Speech，and Signal Processing(关于声学、语音和信号处理的IEEE国际组织会议会刊)，蒙特利尔，加拿大，2004年5月。然而，这些构造仅适用于调制重叠变换(MLT)，也称为改进的离散余弦变换(MDCT)，其基函数是正交的，且不是对称的(即，基函数不是线性相位的)。这些变换不适用于其中需要线性相位(对称)函数的数据压缩应用，诸如在数字图像压缩中。

对于图片(图像)压缩，在R-D性能方面的最佳性能的变换之一是重叠双正交变换(LBT)。见H.S.Malvar的“Biorthogonal and Nonuniform Lapped TransformsFor Transform Coding With Reduced Blocking and Ringing Artifacts”(用于具有降低的块效应和振铃效应的变换编码的双正交且非均匀重叠变换)，IEEE Trans.onSignal Processing(关于信号处理的IEEE论文集)，第46卷，第1043-1053页，1998年4月。与MLT不同，LBT基函数是对称的，且不是完全正交的(在LBT中，解析基函数与综合基函数是正交的，因此使用术语双正交)。LBT已在图像压缩应用中成功地使用，但是它们尚未用于无损图像压缩，因为整数可逆构造是未知的。

基于块变换的编码的综述

变换编码是一种在许多音频、图像和视频压缩系统中使用的压缩技术。未压缩的数字图像和视频通常被表示或捕捉为以二维(2D)网格排列的图像或视频帧中各位置处的像素或色彩的样值。这被称为图像或视频的空间域表示。例如，图像的典型格式由排列成网格的24位的彩色像素样值的流构成。每一样值是表示诸如RGB或YIQ等色彩空间内网格中的像素位置处的色彩分量的数字。各种图像和视频系统可使用各种不同的色彩、空间和时间采样分辨率。类似地，数字音频通常被表示为时间采样的音频信号流。例如，典型的音频格式由以规则的时间间隔获得的音频信号的16位振幅样值的流。

未压缩的数字音频、图像和视频信号可能消耗可观的存储和传输容量。变换编码通过将信号的空间域表示变换成频域(或其它类似的变换域)表示，然后降低变换域表示的某些一般较不易感知的频率分量的分辨率，而减小了数字音频、图像和视频的大小。这一般产生与降低空间域中的图像或视频或时域中的音频的色彩或空间分辨率相比数字信号的更不易感知的劣化。

更具体地，图1所示的典型的基于块变换的编解码器100将未压缩的数字图像的像素划分成固定大小的二维块(X₁，...，X_n)，每一块可能与其它块重叠。完成空间-频率分析的线性变换120-121被应用于每一块，它将块内彼此隔开的样值转换成一般表示在块间隔上对应的频带内的数字信号的强度的一组频率(或变换)系数。对于压缩，变换系数可被选择性地量化130(即，诸如通过丢弃系数值的低位或将高分辨率数字集合中的值映射到较低的分辨率而降低分辨率)，并且也可被熵编码或可变长度编码130成压缩的数据流。在解码时，变换系数将逆变换170-171，以几乎重建原始的色彩/空间采样的图像/视频信号(重建的块)。

块变换120-121可被定义为对大小为N的矢量x的数学运算。大多数情况下，该运算是线性乘法，产生变换域输出y＝Mx，M是变换矩阵。当输入数据是任意长时，它被分段成大小为N的矢量，并向每一分段应用块变换。为数据压缩的目的，选择可逆块变换。换言之，矩阵M是可逆的。在多维中(例如，对于图像和视频)，块变换通常被实现为可分离的运算。矩阵乘法沿数据的每一维度(即，行和列)单独应用。

对于压缩，变换系数(矢量y的分量)可被选择性地量化(即，诸如通过丢弃系数值的低位或将高分辨率数字集合中的值映射到较低的分辨率而降低分辨率)，并也可被熵编码或可变长度编码成压缩的数据流。

在解码器150中的解码处，这些运算的逆运算(反量化/熵解码160和块逆变换170-171)被应用于解码器150侧，如图1所示。尽管重建了数据，然而逆矩阵M¹(逆变换170-171)作为乘子被应用于变换域数据。当被应用于变换域数据时，逆变换几乎重建了原始的时域或空间域数字媒体。

在许多基于块变换的编码应用中，期望编码是可逆的以取决于量化因子而支持有损和无损压缩两者。例如，如果没有量化(一般表示为量化因子1)，则利用可逆变换的编解码器能够在解码时完全重现输入数据。然而，这些应用中的可逆性要求限制了可用于设计编解码器的变换的选择。

诸如MPEG和Windows Media等许多图像和视频压缩系统利用基于离散余弦变换(DCT)的变换。已知DCT具有有利的能量压缩性质，可得到几乎最优的数据压缩。在这些压缩系统中，逆DCT(IDCT)用于压缩系统的编码器和解码器中的重建循环，用于重建各个图像块。DCT由N.Ahmed、T.Natarajan和K.R.Rao的“Discrete Cosine Transform”(离散余弦变换)，IEEE Transactions on Computers(关于计算机的IEEE学报)，C-23(1974年1月)，第90-93页描述。IDCT的一个示例性实现在“IEEE Standard Specification for the Implementations of 8x8Inverse Discrete Cosine Transform”(用于8×8的离散余弦逆变换的实现的IEEE标准规范)，IEEE标准1180-1990，1990年12月6日中有描述。

在压缩静止图像(或视频序列中的帧内编码帧)时，诸如MPEG-2、MPEG-4和Windows Media等最常见的标准将图像划分成正方形的小块，并向每一图像小块应用块变换。给定分区(通常称为块)中的变换系数仅受块内的原始数据分量的影响。编码器侧诸如量化等不可逆或有损运算导致在解码的图像中出现人工效应。这些人工效应在各块之间是不相关的，且产生了被称为块效应的视觉上令人讨厌的效应。同样对于音频数据，当独立地对非重叠的块进行变换编码时，在解码器处重建音频信号时，量化误差将产生块边界处信号中的不连续性。对于音频，可听到周期性的咔嗒声的效应。

使用了若干技术来对抗块效应-这些技术中最常用的是平滑块间边缘边界的解块滤波器以及对原始输入数据和来自相邻块边缘的预测之差进行编码的空间外推。这些技术并非没有缺陷。例如，解块滤波器方法是“开环的”，即前向变换过程不考虑解块将在解码器侧的重建之前执行的这一事实。除此之外，这两种技术在计算上都是昂贵的。

为最小化块效应，可利用块间相关。实现块间相关的一种方法是通过使用重叠变换，如H.Malvar的“Signal Processing with Lapped Transforms”(具有重叠变换的信号处理)，Artech House，Norwood MA，1992中所描述的。重叠变换是其输入除当前块中的数据元素之外跨越相邻块中的几个相邻元素的变换。同样，在重建侧，逆变换影响当前块中的所有数据点以及相邻块中的若干数据点。

对于二维(2D)数据的情况，重叠2D变换是当前块以及左、上、右、下以及可能的左上、右上、左下和右下的块的选择元素的函数。相邻块中用于计算当前变换的数据点的个数被称为重叠。

空间域重叠变换的综述

重叠变换可以在变换域中实现，作为在常规的块变换之后合并变换域量的一个步骤。另外，它可以通过应用于重叠范围内的像素的预处理级在空间域中实现。这两种实现在数学上是相关且因此是等效的。

图2示出了常规的空间域重叠变换的一个示例。在所示的示例中，重叠是2个像素，且每一个都来自所示的两个相邻块的两个像素在预处理级210中预处理。两个预处理的输出被发送到每一块，用于图1所示的编解码器100的基于块变换的编码。预处理级的逆在解码后被应用于后处理级220。采用预处理和块变换的审慎选择，可实现较大范围的重叠变换。

重叠变换的空间域实现的一个关键优点是现有的基于块变换的编解码器可用预处理和后处理级来更新，以得到重叠变换的益处，即使用现有编解码器框架的降低的块效应和较好的压缩。预处理210和后处理可被表示为如图3所示的矩阵乘法。常规上，预处理和后处理矩阵彼此为逆，即，预处理矩阵(P_f)和逆或后处理矩阵(P_i)相乘在一起等于单位矩阵I。

定义

一般而言，变换的长度N是某一变换块中变换系数的个数。

变换的支撑K是影响变换块的系数的输入数据点的个数。同样，它是受每一变换系数，受逆变换的过程影响的输出数据点的个数。

对于诸如离散余弦变换(DCT)等典型的块变换，长度和支撑是相同的。然而，重叠变换(LT)是一类重要的变换，其支撑K大于长度N。记法K×N用于表示重叠变换的支撑和长度(其中K＜N的变换是膨胀性的，因此不用于数据压缩)。

作为一个示例300，图3所示的6×4LT 310是具有6个输入和4个输出的变换。由于变换是可逆的，因此两个输入与相邻的变换块共享。重叠逆变换(ILT)320从其4个输入产生6个输出。块边界附近的输出数据点(在这一情况下是在块的每一端的一个点)通过将两个相邻逆变换块的对应响应相加来重建。

对用于压缩系统中的重叠变换的约束

在数学意义上，当考虑输入和输出信号以及中间计算结果为实数时，重叠变换是可逆结构。如果可实现无限的精度，则输入数据可完整地从其重叠变换系数中恢复。然而，无限的精度实际上是不可能的；对于无损数据压缩，要求是设计一种对整数或固定精度的算术运算的变换，给定变换系数的整数表示，仍完整地重建了数据。这是比数学可逆性更强的条件，且这一变换此处被称为“无损”变换。此外，要求无损变换对于数据压缩(无损和有损)也都是有效的。该效率可以通过变换数据的熵来测量；熵越低，诸如基于上下文的算术编码或自适应行程长度编码等标准熵编码技术就能够更大程度地压缩变换数据。

发明内容

本发明描述了整数算术中可逆，并可用作有效且无损数据压缩/解压系统的基础的有效重叠变换的各种实现。

可以看到，大多数有效无损变换设计(即，具有最小的变换数据熵的设计)要求变换矩阵是单位行列式(即，变换矩阵的行列式是±1)。在以下描述中，假定变换可被表示为矩阵乘法，尽管可以认识到，可以有诸如数据舍入等较小的非线性现象。由此，当提及行列式时，不考虑截断或舍入方面。

有效重叠变换是使用此处被称为“重叠算子”的前置和后置滤波器来实现的。这一实现是可逆的，而在R-D方面仍是非常有效的。这些新重叠算子允许可逆LBT实现以及其它应用，它们可用于无损图像压缩。前置和后置滤波器使用了可逆运算。此外，所描述的重叠算子包括对计算效率的简化。

前置和后置滤波运算的一个实现使用了一维可逆重叠算子，它由单位行列式分量矩阵的构成。更具体地，可逆重叠算子被实现为一连串的平面旋转变换和单位行列式平面比例缩放变换。平面比例缩放变换可使用平面修剪或提升步骤来实现。此外，平面旋转和平面修剪具有可逆/无损操作的实现，从而给出了可逆的重叠算子作为结果。

一个示例性应用是使用可逆重叠算子的计算上有效的逼近的8×4的一维重叠变换。

对于二维重叠变换，重叠算子的该一维实现可以单独地应用于数字媒体数据库块的水平行，随后将一维算子应用于该数据的垂直列。该方法具有若干缺陷，其中最严重的是：

1.获取用于有效数据压缩的归一化前置/后置滤波器的难度/几乎不可能，

2.如果可实现这一逼近，其高度复杂性，以及

3.由于当实现这一逼近时多个滤波/提升步骤而引起的不准确性。

此处所描述的二维重叠变换的替换实现达到了比单独水平和垂直地应用一维重叠算子的方法更好的计算效率。该替换实现将一维重叠算子分割成级，并散置重叠算子的水平和垂直应用的级。在每一级内，在提升步骤中实现的归一化比例缩放运算可通过在散置的二维结构中记录“交叉项”的抵消而被应用于数据块的有限子集(例如，4×4数据块的2×2子集或信号对)。这可得到有效的无比例缩放可逆2D前置/后置滤波器。

2D前置/后置滤波器可与诸如有效的无比例缩放可逆2D块变换等可逆变换相组合，后者由Srinivasan在2004年12月17日提交的名为“Reversible Transform ForLossy and Lossless 2-D Data Compression”(用于有损和无损2-D数据压缩的可逆变换)的美国专利申请第11/015,707号中描述(该申请的公开内容通过引用结合于此)。组合的前置/后置滤波器和变换形成了可用于无损和有损图像和视频的高效和计算有效压缩的重叠变换。

当参考附图继续以下实施例的详细描述时，可清楚本发明的其它特征和优点。

附图说明

图1是现有技术中常规的基于块变换的编解码器的框图。

图2是同样在现有技术中被实现为与图1的基于块变换的编解码器组合的预处理和后处理运算的空间域重叠变换的框图。

图3是示出一维数据上的重叠变换和重叠逆变换对的框图。

图4是基于使用可逆重叠算子的重叠变换的编码器的流程图。

图5是基于重叠变换的解码器的流程图。

图6是示出结合块变换使用前置和后置滤波运算(或可逆重叠算子)对一维数据的重叠变换和重叠逆变换对的框图。

图7是示出用作图6的重叠变换中的可逆重叠算子的线性相位前置(或后置)滤波器的结构的信号流图。

图8是作为可逆重叠算子中使用的四个提升步骤的无损比例缩放的信号流图。

图9是作为可逆重叠算子中使用的五个提升步骤的无损比例缩放的信号流图。

图10是应用于较大维数的矩阵以实现无损单位行列式比例缩放的2点比例缩放的级联的信号流图。

图11是具有图7所示的结构并使用图10的无损单位行列式比例缩放的可逆重叠算子(或前置/后置滤波器)的信号流图。

图12是图11的可逆重叠算子的操作的流程图。

图13是示出使用图11的可逆重叠算子的可逆重叠变换实现的一个示例的信号流图。

图14是图13的示例重叠变换的DC系数的脉冲响应图。

图15是示出用作用于4×4大小的块的二维重叠算子的支撑的像素的图示。

图16是示出用作用于2×2大小的块的二维重叠算子的支撑的像素的图示。

图17是由图4的编码器在编码器侧应用的变换的流程图。

图18是由图5的解码器在解码器侧应用的变换的流程图。

图19是提供图11所示的一维可逆重叠算子的正则表示的信号流图。

图20是示出用于通过水平和垂直地单独应用图19的一维可逆重叠算子而实现的重叠变换的二维前置和后置滤波器的信号流图。

图21是示出用于通过交错各级中的二维滤波器的水平和垂直操作而实现的重叠变换的二维前置/后置滤波器的信号流图。

图22是用于实现形成图21的二维前置/后置滤波器的一部分的归一化2×2阿达马(Hadamard)算子的C编程语言程序清单。

图23是示出用2×2前置/后置滤波器处理的数据点之间的对应性的图示。

图24是示出在图21的4×4二维前置/后置滤波器的实现的第一级中向其应用2×2的阿达马算子的4×4数据块的数据点的图示。

图25是用于实现形成图21的二维前置滤波器的一部分的前向旋转的C编程语言程序清单。

图26是用于实现形成图21的二维后置滤波器的一部分的反向旋转的C编程语言程序清单。

图27是用于实现形成图21的二维前置滤波器的一部分的前向2点旋转的C编程语言程序清单。

图28是用于实现形成图21的二维后置滤波器的一部分的反向2点旋转的C编程语言程序清单。

图29是示出在图21的4×4二维前置/后置滤波器的实现的另一级中向其应用图25-28的旋转的4×4数据块的数据点的图示。

图30是示出在图21的4×4二维前置/后置滤波器的实现的又一级中向其应用2点比例缩放运算的4×4数据块的数据点的图示。

图31是用于实现形成图21的二维前置滤波器的一部分的前向比例缩放的C编程语言程序清单。

图32是用于实现形成图21的二维后置滤波器的一部分的反向比例缩放的C编程语言程序清单。

图33是用于实现图21的二维4×4前置滤波器的C编程语言程序清单。

图34是用于实现图21的二维4×4后置滤波器的C编程语言程序清单。

图35是用于实现图21的二维2×2前置滤波器的C编程语言程序清单。

图36是用于实现图21的二维2×2后置滤波器的C编程语言程序清单。

图37是用于实现在具有不足数据点的图像边缘处应用图35的二维前置滤波器的一维2点前置滤波器的C编程语言程序清单。

图38是用于实现在具有不足数据点的图像边缘处应用图36的二维前置滤波器的一维2点后置滤波器的C编程语言程序清单。

图39是用于实现在具有不足数据点的图像边缘处应用图33的二维前置滤波器的一维4点前置滤波器的C编程语言程序清单。

图40是用于实现在具有不足数据点的图像边缘处应用图35的二维前置滤波器的一维4点后置滤波器的C编程语言程序清单。

图41是用于实现结合图21的前置滤波器使用来实现图4的编码器中的重叠变换的前向变换的C编程语言程序清单。

图42是用于实现形成图41的前向变换的一部分的变换的C编程语言程序清单。

图43是用于实现形成图41的前向变换的一部分的另一变换的C编程语言程序清单。

图44是用于实现结合图21的后置滤波器使用来实现图5的解码器中的重叠逆变换的逆变换的C编程语言程序清单。

图45是用于实现形成图44的逆变换的一部分的变换的C编程语言程序清单。

图46是用于实现形成图44的逆变换的一部分的另一变换的C编程语言程序清单。

图47是适用于实现具有图4和5的改进的空间域重叠变换的基于块变换的编解码器的计算环境的框图。

具体实施方式

以下描述涉及数字媒体压缩系统或编解码器，它使用了可逆二维前置/后置滤波器用于重叠变换。为说明起见，结合该二维前置/后置滤波的压缩系统的一个实施例是图像或视频压缩系统。或者，可逆重叠算子也可被结合到用于其它2D数据的压缩系统或编解码器中。可逆重叠算子不要求数字媒体压缩系统以特定的编码格式对压缩的数字媒体数据进行编码。

1.编码器/解码器

图4和5是基于使用可逆重叠算子的重叠变换的代表性二维(2D)数据编码器400和解码器500中使用的过程的概图。这些图表示了该可逆重叠算子在结合了2D数据编码器和解码器的压缩系统中的使用和应用的概括或简化图示。在基于该可逆重叠算子的替换编码器中，可对2D数据压缩使用比这一代表性编码器和解码器中所示的更多或更少的过程。例如，某些编码器/解码器也可包括色彩转换、色彩格式、可伸缩编码、无损编码、宏块模式等。压缩系统(编码器和解码器)可提供2D数据的无损和/或有损压缩，取决于可基于从无损到有损变化的量化参数的量化。

2D数据编码器400产生压缩的比特流420，它是作为对编码器的输入呈现的2D数据410的更紧凑表示(对于典型输入)。例如，2D数据输入可以是图像、视频序列的帧或具有两个维度的其它数据。2D数据编码器将输入数据划分(430)成宏块，在该代表性编码器中宏块是16×16像素的大小。2D数据编码器还将每一宏块划分成4×4的块432。“前向重叠”算子440被应用于块之间的每一边缘，之后每一4×4的块使用块变换450来变换。该块变换450可以是可逆的、无比例缩放的2D变换，如由Srinivasan在2004年12月17日提交的名为“Reversible TransformFor Lossy And Lossless 2-D Data Compression”(用于有损和无损2D数据压缩的可逆变换)的美国专利申请第11/015,707号中描述的，该申请的公开内容通过引用结合于此。或者，可与此处所描述的可逆重叠算子一起使用离散余弦变换或其它块变换。在变换之后，每一4×4的变换块的DC系数460经受类似的处理链(划分、前向重叠、之后是4×4的块变换)。所得的DC变换系数和AC变换系数被量化470、熵编码480并被分组化490。

解码器执行逆向过程。在解码器侧，从其各自的分组中提取(510)变换系数比特，从中系数本身被解码520和反量化530。通过应用逆变换来再生DC系数540，并且使用跨DC块边缘应用的合适的平滑算子来“逆重叠”DC系数的平面。随后，通过向DC系数应用4×4的逆变换550来再生整个数据，且从该比特流中解码AC系数542。最后，所得的图像平面中的块边缘被逆重叠过滤560。这产生重建的2D数据输出。

在一个示例性实现中，编码器400(图4)将输入图像压缩成压缩的比特流420(例如，文件)，且解码器500(图5)基于是采用无损还是有损编码来重建原始输入或其近似。编码的过程涉及下述前向重叠变换(LT)的应用，这是用同样在下文更完整描述的可逆二维前置/后置滤波来实现的。解码过程涉及使用可逆二维前置/后置滤波的重叠逆变换(ILT)的应用。

所示的LT和ILT在确切的意义上是彼此的逆，并且因此可被共同称为可逆重叠变换。作为可逆变换，LT/ILT对可用于无损图像压缩。

由所示的编码器400/解码器500压缩的输入数据410可以是各种色彩格式(例如，RGB/YUV4:4:4或YUV4:2:0色彩图像格式)的图像。通常，输入图像总是具有亮度(Y)分量。如果它是RGB/YUV4:4:4或YUV4:2:0图像，则该图像也具有色度分量，诸如U分量和V分量。图像的这些单独的色彩平面或分量可具有不同的空间分辨率。在例如YUV4:2:0色彩格式的输入图像的情况下，U和V分量具有Y分量的宽度和高度的一半。

如上所述，编码器400将输入图像或图片划分成宏块。在一个示例性实现中，编码器400将输入图像划分成Y通道中的16×16的宏块(它可以是U和V通道中的16×16或8×8区域，取决于色彩格式)。每一宏块色彩平面被划分成4×4的区域或块。因此，宏块按以下用于该示例性编码器实现的方式对各种色彩格式组成：

1.对于灰度级图像，每一宏块包含16个4×4的亮度(Y)块。

2.对于YUV4:2:0格式的色彩图像，每一宏块包含16个4×4的Y块，以及4个每一个都是4×4的色度(U和V)块。

3.对于RGB或YUV4:4:4色彩图像，每一宏块包含16个块，其每一个都有Y、U和V通道。

2.使用重叠算子实现的重叠变换

更一般地，编码器400(图4)的重叠算子440和块变换450是一大类重叠变换600的示例，这类变换可被分解成前置滤波操作，其后是块数据变换620，如图6所示。图6示出了这一分解的重叠变换的概括示例。在这一示出的情况下，图3中所示的6×4重叠变换310被分解成前置滤波操作610和块变换620级。前置滤波操作610和块变换620在数据点上均匀地交错。在这一所示的6×4的重叠变换600示例中，每一前置滤波器是跨越相邻块的长度为2的数据点变换。在解码器侧，后置滤波器640跨块边界在块逆变换630之后应用。同样，对于一般的K×N情况，前置滤波器被应用于与块边界相邻的每一块的(K-N)/2个数据点。

为实现可逆性，前置滤波器610和后置滤波器640是彼此的逆。然而，为实现无损重叠变换，这一条件是不充分的。这除了以无损方式实现块(核心)变换620之外，进一步也将前置和后置滤波器610、640约束为无损变换。DCT可以使用基于阶梯、点阵或提升的方法等用无损的方式来实现。见例如A.A.M.L.Bruekens和A.W.M.van den Enden的“New networks for perfect inversion and perfectreconstruction”(用于理想求逆和理想重建的新网络)，IEEE J.Selected AreasCommunications(选择的区域通信IEEE期刊)第10卷第1期，1992年；以及I.Daubechies和W.Sweldens的“Factoring wavelet transform into lifting steps”(将小波变换分解成提升步骤)，J.Fourier Anal.Appl.(J.傅立叶分析应用)第4卷第247-269页，1998。可逆的无比例缩放二维变换也由Scrinivasan在2004年12月17日提交的名为“Reversible Transform For Lossy And Lossless 2-D Data Compression”(用于有损和无损2-D数据压缩的可逆变换)的美国专利申请第11/015,707号中描述，该申请通过引用结合于此。一维中对DCT的基于提升的可逆逼近也是已知的。见例如J.Liang和T.D.Tran的“Fast Multiplierless Approximations Of The DCTWith The Lifting Scheme”(具有提升模式的DCT快速无乘子逼近)，IEEE Trans.Signal Processing(信号处理IEEE论文集)，第49卷，第3032-3044页，2001年12月。

有效的可逆性进一步要求两步骤，即前置/后置滤波和块变换都是单位行列式。

3.可逆重叠算子

用作编码器400/解码器500(图4和5)作为基础的无损重叠变换600的前置滤波器610(图6)的有效可逆重叠算子可被实现为线性相位前置滤波器，它被分解成图7所示的结构700。该前置滤波器的逆(即，后置滤波器640)也具有相同的结构，但具有不同的系数。

该线性相位滤波器结构700具有多个正交分量作为其输入和输出，包括交叉阿达马网络710。所示的阿达马网络710中的内部箭头表示该图中的非。结构700还包括正交矩阵U1、U2、V1和V2。这些分量可以通过使用基于点阵/提升的方法以无损的方式来实现。

另外，结构700具有非零比例缩放因子s₁到s_M。单位行列式约束隐含。当所有的比例缩放因子都是±1时，前置/后置滤波器可被实现为一无损变换，其中分量矩阵U1、U2、V1和V2被实现为无损点阵/提升步骤。然而，当比例缩放因子不都为±1时，无损实现保留了如下文更完整讨论地解决的难题。

采用这一线性相位前置滤波器结构700，实现无损前置/后置滤波器对的问题被精简到以下三个步骤：

1.对于正交矩阵U1、U2、V1和V2，将过滤器F分解成以下形式：

其中I是单位矩阵，且

2.导出对U1、U2、V1和V2的无损实现；以及

3.导出对比例缩放矩阵的无损实现。

对于步骤1，右边的第一和最后一个矩阵定义了2点阿达马变换，它们结合了某些项的1/2因子，以使这些级是单位行列式。剩余部分被重新排列成具有两个块的块行列式形式，其每一个是F的线性维数的一半。每一块的奇异值分解，即SVD提供了正交矩阵U1、U2、V1和V2以及比例缩放。

分量矩阵的无损实现可使用标准的基于提升的技术在步骤2中导出，这些技术诸如由A.A.M.L.Bruekens和A.W.M.van den Enden的“New networks for perfectinversion and perfect reconstruction”(用于理想求逆和理想重建的新网络)，IEEEJ.Selected Areas Communications(选择的区域通信IEEE期刊)第10卷第1期，1992年中所描述的技术。

步骤3中比例缩放矩阵的无损实现如下解决。为简明起见，假定具有某一2输入2输出分量，它是(a)无损的，且(b)对第一分量实现按s(0＜s＜1)的比例缩放，对第二分量实现1/s的比例缩放(其它情况可通过还原一个或两个输出信号的符号来获得)。换言之，具有由以下公式给出的输入-输出关系

$y=\left(\begin{array}{cc}s& 0\\ 0& 1/s\end{array}\right)x---\left(2\right)$

公式(2)中变换矩阵的行列式是s/s＝1。该矩阵可在如图8和9所示的四个提升步骤的过程800或五个提升步骤的过程900中实现。通常以y＝(a.x+r)＞＞b的形式逼近所有的提升步骤，其中x是输入，y是输出，a、b和r是整数，且r用于舍入误差控制，以获得无除法的整数实现。由公式(2)定义的变换此处被称为单位行列式比例缩放变换，简称为比例缩放变换。

有趣的是，比例缩放变换与如下定义的修剪运算密切相关：

$y=\left(\begin{array}{cc}a& b\\ b& a\end{array}\right)x---\left(3\right)$

在约束a²-b²＝1(a＞0，b≥0)下，修剪运算具有单位行列式，且可用三个提升步骤来实现：

$\left(\begin{array}{cc}a& b\\ b& a\end{array}\right)=\left(\begin{array}{cc}1& \sqrt{\frac{a-1}{a+1}}\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ b& 1\end{array}\right)\left(\begin{array}{cc}1& \sqrt{\frac{a-1}{a+1}}\\ 0& 1\end{array}\right),---\left(4\right)$

因此，

$\left(\begin{array}{cc}a+b& 0\\ 0& a-b\end{array}\right)=\left(\begin{array}{cc}1& 1/2\\ -1& 1/2\end{array}\right)\left(\begin{array}{cc}1/2& 0\\ 0& 1\end{array}\right)\left(\begin{array}{cc}a& b\\ b& a\end{array}\right)\left(\begin{array}{cc}2& 0\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1/2& -1/2\\ 1& 1\end{array}\right)$

$=\left(\begin{array}{cc}1& 0\\ -1& 1\end{array}\right)\left(\begin{array}{cc}1& \frac{1}{2}(\sqrt{\frac{a-1}{a+1}}+1)\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ 2b& 1\end{array}\right)\left(\begin{array}{cc}1& \frac{1}{2}(\sqrt{\frac{a-1}{a+1}}-1)\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)---\left(5\right)$

此处，夹住修剪矩阵的矩阵中的比例缩放因子1/2和2被分布到修剪提升步骤，且第一个矩阵的最后一个提升步骤与第一个修剪提升步骤组合，而最后一个矩阵的第一个提升步骤与第一个修剪提升步骤组合。如图9所示的比例缩放变换的过程900的五步骤实现基于公式(5)。对该结构的简化通过在可能时取消公式(1)中的三个组，即阿达马网络、正交矩阵和比例缩放运算(可进而被分解成阿达马和修剪运算)之间的逆运算是可能的。

更具体地，如过程800的无损比例缩放的四个提升步骤实现的有效变换矩阵是其中c²＝1-s²。另一方面，过程900中五个提升步骤实现的有效变换矩阵是其中c²＝1-s²。

尽管图8所示的比例缩放过程比图9的过程少了一个提升步骤，但是后一过程900与前一过程中的四个非平凡提升步骤相比只有三个非平凡提升步骤。为上文陈述的原因，图9中的第一或最后一个平凡提升步骤在某些条件下(例如，当U1、U2和V1是单位矩阵时)可与先前或随后的变换步骤合并(例如，与图7的任一端的阿达马网络710组合)。

比例缩放过程可被容易地扩展到更大的矩阵。这在图10中示出，其中M个可能不同的比例缩放因子s₁到s_M被应用于M个数据路径，作为比例缩放变换的级联1000。为以可逆的方式实现这一结果，一般需要M-1个可逆的比例缩放变换。

一个有用的特殊情况是M个比例缩放因子s₁到s_M可被组合成形式为(s，1/s)的M/2个组。在这一情况下，仅需要M/2个可逆的比例缩放变换。一个示例是s₁＝s₂＝...＝s_M/2＝s且s_M/2+1＝s_M/2+2＝...＝s_M＝1/s。一种较佳的组合方式是维持跨中心轴的对称性，换言之，每一组按比例缩放系数s_i和s_M+1-i。如果M是奇数，则未组合的一个比例缩放因子是1，对应于沿该轴的数据路径。

在其中前置/后置滤波器需要扩展到信号之外的信号边界上，一种解决方案是对称地扩展信号，然后应用前置/后置滤波器。由于比例缩放，这一般不是无损运算。另一种解决方案是在边界上跳过前置/后置滤波器。在R-D性能以及感知质量(例如，如果用于有损图像/视频压缩)方面在两种解决方案之间没有显著的区别。

现在转向图11，具有期望的R-D有效(即，单位行列式)属性的可逆重叠算子然后被实现为线性相位前置滤波器结构700(图7)，它包括可逆的单位行列式阿达马网络710、可逆的正交旋转1110(对分量矩阵U1、U2、V1和V2)以及可逆的单位行列式比例缩放1120(例如，使用提升步骤过程800、900或级联1100)。后置滤波器类似于前置滤波器，且是使用同一构造来构建的，但是在相反的顺序上具有逆提升步骤。这在图7中示出，其中块中的数据值的个数M一般是任何自然数。尽管所示的是对于偶数值的M，但是通过注意中心数据值的“1点阿达马”变换是其本身，奇数值也是可能的。该过程可被推广到较高维数的数据。

总言之，可逆重叠算子的运算在图12中示出。在第一个步骤1210，将输入的二维数字媒体数据划分成块(也对图4的编码器400示出)。可逆重叠算子在步骤1220块相邻的小块应用阿达马网络710。该算子然后在步骤1230向和与差应用可逆旋转，随后在步骤1240应用可逆比例缩放算子。之后是另一可逆块旋转(步骤1250)和可逆的逆阿达马网络(步骤1260)。

现在参考图13，可逆块旋转和比例缩放算子的矩阵表示取决于例如使用公式(1)中所描述的运算的期望重叠算子。图13示出了具有图7和11所示的结构700的后置滤波器的一个示例，它之前有一可逆块变换(在此情况下是4点阿达马变换)。后置滤波器的传递函数是：

$T=\left(\begin{array}{cccc}0.9885& 0.1553& -0.1553& 0.2183\\ -0.1499& 0.9885& 0.2183& 0.1499\\ 0.1502& 0.2167& 0.9884& -0.1502\\ 0.2167& -0.1556& 0.1556& 0.9884\end{array}\right)---\left(6\right)$

阿达马过程的低通分量产生图14的曲线图中所示的脉冲响应。

4.重叠变换模式

在一个示例性实现中，编码器400和解码器500使用不同类型的变换(例如，此处所描述的重叠变换，以及其中省略了重叠过滤的模式)支持多种压缩模式。在编码过程中，由用户提供内部参数OverlapMode(重叠模式)。该参数确定了用于编码的变换的类型，并通过比特流向解码器发信号通知。在该示例性实现中，允许OverlapMode的三种选择-“OL_NONE”、“OL_ONE”以及“OL_TWO”，并如下运作：

1.OL_NONE发信号通知使用块变换用于压缩图像。

2.OL_ONE发信号通知使用重叠变换用于高通(细节)图像，并使用块变换用于低通(DC)图像分量。

3.OL_TWO发信号通知使用重叠变换用于图像的高通和低通分量两者。在其它编码器/解码器实现中，可支持更少或更多的变换模式。

在该示例性实现中，重叠变换被实现为编码器侧的4×4的前置滤波器(前向重叠440)，其后是4×4的块变换450，如图17所示且在下文更完整描述的。在解码器侧，重叠变换由4×4的块逆变换550及其后的4×4后置滤波器(逆重叠560)来实现，如图18所示且在下文更完整描述的。当仅使用块变换时(例如，OL_NONE模式，以及对于OL_ONE模式压缩的图像的低通频带)，省略前置和后置滤波器步骤。

对于YUV4:2:0格式的亮度低通色彩平面的特殊情况，滤波器和变换块的大小是2×2。以下描述使用了术语“4×4”来指滤波器/变换大小，要理解2×2的块将用于该特殊情况。

如图15所示，该示例性编码器实现中块变换在自然的4×4网格，即4×4小块中与宏块边界对齐的像素阵列上执行。滤波过程在交错的4×4网格，即4×4小块中在水平和垂直方向上与宏块边界的偏移为2的像素阵列上执行。在图15的图示1500中，所指示的四个块1510-1513对应于变换的自然网格，且中心的阴影(灰色)块1520是在其上应用前置/后置滤波器的区域。中心块中的像素被称为重叠算子的“支撑”。图16示出了对于2×2的特殊情况的变换和重叠算子的对齐1600。

示例性实现中使用且应用于4×4的块中的每一个的块变换此处被称为“核心”变换。该核心变换实现了可逆的近似4×4DCT，由Srinivasan在2004年12月17日提交的名为“Reversible Transform For Lossy and Lossless 2-D Data Compression”(用于有损和无损2-D数据压缩的可逆变换)的美国专利申请第11/015,707号中描述(该申请的公开内容通过引用结合于此)，且也在下文名为“核心变换”一节中讨论。在核心变换之后，块被映射到1个DC系数460和15个AC系数462(如图4所示)的系数块。

前置/后置滤波器(图4的前向重叠440以及图5的逆重叠560)结合核心变换共同实现了重叠变换，此处也称为重叠算子。

在由编码器400(图4)应用核心变换450之后，收集图像的所有块的DC系数460以形成DC子带。该核心变换的第二级被应用于该DC子带。如果OverlapMode＝OL_TWO，则第二级重叠算子也在第二级核心变换之前应用。如果图像是YUV_444图像的Y分量或U或V分量，则DC子带460被划分成4×4的块，且使用与第一级相同的4×4的PCT和4×4的PLO。然而，如果图像是YUV4:2:0图像的U或V分量，则DC子带改为划分成2×2的块。因此，使用2×2的PCT和2×2的PLO。图16示出了用于2×2的重叠算子的2×2支撑1620，它也跨越2×2的相邻块1610-1613。

参考图15，在图像的角上，重叠算子所跨越的4个块中仅一个块可用。这些是左上角的块3、右上角的块1、左下角的块2和右下角的块0。在这些情况下，跳过4×4或2×2的重叠算子。

在除4个角之外的图像边界上，重叠算子1520所跨越的4个块中的2个块可用。在这些区域中，只需一维算子。因此，4×4重叠的算子由1D 4点重叠算子的两个实例来替换(且对于2×2的重叠算子也是如此)。

具体地，有四种情况(参考图15)：

·支撑1520、1620跨越顶部图像边界(块0和2不可用，块1和3可用)：4点重叠算子被应用于点(i，j，k，l)和点(m，n，o，p)，或者2点重叠算子被应用于点(c，d)；

·支撑1520、1602跨越底部图像边界(块1和3不可用，块0和2可用)：4点重叠算子被应用于点(a，b，c，d)和点(e，f，g，h)，或者2点重叠算子被应用于点(a，b)；

·支撑1520、1620跨越左侧图像边界(块0和1不可用，块2和3可用)：4点重叠算子被应用于点(c，g，k，o)和点(d，h，l，p)，或者2点重叠算子被应用于点(b，d)；

·支撑1520、1620跨越右侧图像边界(块2和3不可用，块0和1可用)：4点重叠算子被应用于点(a，e，i，m)和点(b，f，j，n)，或者2点重叠算子被应用于点(a，c)。

因此，编码器400(图4)的示例性实现的编码过程1700(图17)中使用的重叠变换涉及2×2的核心变换、4×4的核心变换、2×2的重叠算子、4×4的重叠算子、2点重叠算子以及4点重叠算子。解码器500(图5)使用的解码过程1800(图18)无损地反转了该过程。逆核心变换是编码器的核心变换的理想逆运算，逆重叠算子是编码器的重叠算子的理想逆运算。一维的4点重叠算子在上文名为“可逆重叠算子”一节中描述。接下来描述二维重叠算子。

5.二维前置/后置滤波

在一种方法中，用于二维前置/后置滤波440(图4)的4×4重叠算子可通过水平和垂直地向4×4的重叠算子支撑1520(图15)单独应用图19的4点重叠算子1900(也在上文名为“可逆重叠算子”一节中描述)来实现。4×4的重叠算子的这一可分离的方法实现2000在图20中示出。更具体地，该方法向4×4的重叠算子支撑1520的垂直列(即，列a，e，i，m；列b，f，j，n；列c，g，k，o；以及列d，h，l，p)应用一维4点重叠算子，之后向水平行(即，行a，b，c，d；行e，f，g，h；行i，j，k，l；以及行m，n，o，p)应用一维4点重叠算子。然而，该方法2000具有若干缺点，如在下文“总结”一节中所描述的。

此处所描述的编码器400/解码器500的示例性实现使用了另一种方法来实现解决这些缺点的二维前置/后置滤波(前向重叠440和逆重叠560)。这一其它方法2100(图21)在多个级中散置可分离方法的水平和垂直滤波器的操作。此外，操作被组合以形成具有归一化的无比例缩放且可逆的“蝶形结构”实现的2×2变换，如图24、29和30所示。此外，在上文名为“可逆重叠算子”一节中描述的提升步骤中实现的归一化的比例缩放运算可通过注意散置的二维结构中“交叉项”的抵消而被应用于一组更有限的信号对。这可得到有效的无比例缩放可逆二维前置/后置滤波器，它与有效的无比例缩放可逆二维块变换结合提供了可在用于图像和视频的有效且计算上高效的无损和有损压缩的编码器/解码器中使用的重叠变换。

如图21所示，在一个所示的实现中，该第二种方法将前置/后置滤波器的垂直和水平操作散置到三级中。在每一级中，运算被重新排列成4×4的数据块的单独的4点组上的基本2×2的运算。

更具体地，前置/后置滤波器中的第一级以及最后一级被实现为归一化的2点阿达马蝶形结构。该级中的垂直和水平运算被重新排列成在图22所示的程序清单2200中定义的2×2的归一化阿达马运算(它是先前引用的Srinivasan在2004年12月17日提交的名为“Reversible Transform For Lossy and Lossless 2-D DataCompression”(用于有损和无损2-D数据压缩的可逆变换)的美国专利申请第11/015,707号中描述的T_H变换)，它被单独应用于4×4的数据块中的4点组。该2×2的归一化阿达马运算被应用于图23所示的2×2的输入矩阵2300(点a、b、c和d)。在图23中和该文档的剩余部分中使用了阴影以表示数据点(等效的像素或矩阵元素)和处理步骤之间的对应性。应用于输入矩阵[a b；c d]的基本2×2运算如图23所示原地计算。

散置的方法2100(图21)中的第1级和第3级运算然后可被重新排列为该2×2的归一化阿达马运算2200(图22)对数据块中的4个单独的4点组2400(图24)的应用，即角2410上的4点、中心的4点2420、顶边/底边上的4点2430以及左边/右边上的4点2440。

另一方面，第2级运算包括两个步骤-第一个是旋转(图21中所示)，第二个是比例缩放(图21中未示出)。这两个步骤的顺序不是重要的，尽管为一致性必须由所有的编解码器维持相同的顺序，并且其在重叠变换中的顺序相对于重叠逆变换是相反的。

旋转步骤通过再一次将运算重新排列成单独的2×2变换来实现。由于低通项对于一维情况(图19的4点重叠算子1900的点x0和x1)是通过的，因此二维中低-低点(即，两个方向上都是低通的)再一次是通过的(即，在该级不被过滤)。这对应于图29中的左上角的2×2子块2910。

高-高项2920(图29)用有效的2×2归一化可逆旋转运算2500来实现，它是先前引用的Srinivasan在2004年12月17日提交的名为“Reversible Transform ForLossy and Lossless 2-D Data Compression”(用于有损和无损2-D数据压缩的可逆变换)的美国专利申请第11/015,707号中描述的T_odd-odd变换。该T_odd-odd变换可在图25所示的C编程语言清单2500中实现。选择非平凡提升步骤(即，涉及乘以3的那些步骤)中的偏移以最小化总偏差。用于后置滤波器的这一变换的逆变换可在图26所示的C编程语言清单2600中实现。

高-低和低-高项2930(图29)仅涉及一维滤波，因为其它维度的运算是通过。这些是用图27所示的C编程语言清单2700中定义的2点旋转来实现的。用于后置滤波器的逆运算在图28所示的C编程语言清单2800中实现。这些2点旋转是涉及2个计算上平凡的提升步骤的简单逼近，它们在实践中能起很好的作用。也可替换地使用其它逼近。该2点旋转作为4组2点运算被应用于高-低和低-高项2930，如由图29中的阴影指示的。

对于第2级的比例缩放步骤，一维4点重叠算子1900(图19)包括按[ff 1/f 1/f]比例缩放四个点。对于二维情况，比例缩放步骤实现[f f 1/f 1/f]与其自身的外积。所得的比例缩放矩阵是

$\left(\begin{array}{cccc}{f}^2& f^2& 1& 1\\ f^2& f^2& 1& 1\\ 1& 1& f^{-2}& f^{-2}\\ 1& 1& f^{-2}& f^{-2}\end{array}\right)$

该矩阵项的一半是单位元素，因此这些点仅仅通过。剩余的项在围绕矩阵中心的2点运算中配对(即，对3010、3020、3030和3040，如图30中的阴影所示的)。对称对于与散置的方法2100(图21)的第1级和第3级匹配的最佳码率-失真性能是必要的。应用于每一对的2点比例缩放运算本身在图31所示的C编程语言清单3100中实现。用于后置滤波器的2点比例缩放逆运算在图32的清单3200中示出。或者，其它逼近对于2点比例缩放过程也是可能的。此外，比例缩放过程可与注意了其最终操作之间的抵消的第1级和第3级的2×2阿达马运算组合。

图33示出了使用图21所示的散置方法2100的完整的4×4重叠算子的程序清单3300。如上对于图17和18中所示的编码器400/解码器500的示例性实现所述的，如果OL_ONE为真，则4×4的重叠算子被应用于图像的非角和非边界部分。如果OL_TWO为真，则如果它不是YUV4:2:0图像的U或V分量，它也被应用于图像的DC子带的非角和非边界部分。具有不同的逼近或合并的步骤(尤其是比例缩放和阿达马之间)的其它替换实现是可能的。

如上文图15中所示的，4×4的重叠算子被应用于重叠算子支撑，它可以被表示为输入数据块

$\left(\begin{array}{cccc}a& b& c& d\\ e& f& g& h\\ i& j& k& l\\ m& n& o& p\end{array}\right)$

4×4的前向重叠算子然后在该程序清单中被定义为函数PLO4×4(a，b，c，d，e，f，g，h，i，j，l，l，m，n，o，p)。如上所述，该函数包括在三级中向图24、29和30所示的输入块的点的子组应用2×2的阿达马运算2200(图22)、前向比例缩放3100(图31)、2点旋转2700(图27)、以及前向奇-奇变换2500(图25)。

图34示出了同样使用散置的方法的4×4重叠逆算子的实现的程序清单3400。其中4×4重叠逆算子的输入系数块是块

$\left(\begin{array}{cccc}a& b& c& d\\ e& f& g& h\\ i& j& k& l\\ m& n& o& p\end{array}\right)$

然后该算子在该程序清单中被定义为函数IPLO4×4(a，b，c，d，e，f，g，h，i，j，l，l，m，n，o，p)。4×4重叠逆算子包括再一次在三级中向图24、29和30所示的系数块的点的子组应用2×2的阿达马运算2200(图22)(它是其自己的逆运算)、奇-奇逆变换2600(图26)、2点逆旋转2800(图28)以及逆比例缩放3200(图32)。

作为上述的一个特殊情况，图17和18中所示的编码器/解码器的示例性实现也应用2×2的前置/后置滤波运算。图35示出了用于2×2的前置滤波的程序清单3500。2×2的前置/后置滤波类似于4×4的前置/后置滤波，不同之处在于在第2级中没有旋转。2×2的前置滤波因此可对上文所描述的4×4情况来实现，消除了第2级的旋转步骤。图36示出了实现2×2的后置过滤的程序清单3600。

在图17和18所示的编码器/解码器的示例性实现中，沿一维的滤波也必须沿图像边缘进行，在边缘中没有足够的像素用于2D滤波步骤。由于缺少对归一化无损提升实现的简化操作，因此1D滤波器可能比对应的2D滤波器更复杂。1D前置/后置滤波器的实现在上文名为“可逆重叠算子”一节中讨论。

图37示出了一维2点重叠算子的程序清单3700(以C编程语言)，它在图17和18的编码器/解码器的示例性实现中在OL_TWO为真时应用于YUV 4:2:0图像的U和V分量的DC子带的边界。图38示出了一维2点重叠逆算子的程序清单3800。

图17和18的编码器/解码器的示例性实现也在OL_ONE为真时向图像的边界应用4点重叠算子。如果OL_TWO为真，则如果它不是YUV 4:2:0图像的U或V分量，4点重叠算子也被应用于图像的DC子带的边界。用于被排序为[a b c d]的输入数据的一维4点前向重叠算子然后在图39所示的程序清单3900(以C编程语言)中被定义为函数PLO4(a，b，c，d)。图40所示的程序清单4000包括函数IPLO(a，b，c，d)，它定义了输入系数[a b c d]上的4点重叠逆算子。

6.核心变换

如上所述，编码器/解码器的示例性实现实现了一种重叠变换，它是上述重叠算子与由上文引用的Srinivasan在2004年12月17日提交的名为“ReversibleTransform For Lossy and Lossless 2-D Data Compression”(用于有损和无损2-D数据压缩的可逆变换)的美国专利申请第11/015,707号中描述的可逆近似4×4 DCT的组合。如图17中对于该示例性实现的编码过程1700以及图18中对于解码过程1800所示，编码器/解码器使用2×2的核心变换、2×2的核心逆变换、4×4的核心变换和4×4的核心逆变换。这些变换的实现在图41-46所示的程序清单(以C编程语言)中定义，如下所述。

2×2的输入块上的2×2的前向核心变换

$\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$

可以在2个步骤中实现：

1.应用图22的阿达马2×2(a，b，c，d)函数2200；

2.交换点b和c。

在某些实现中，步骤2可与量化或锯齿形扫描相组合。

2×2的系数块上的2×2核心逆变换

$\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$

可在两个步骤中实现：

1.交换点b和c；

2.应用阿达马2×2(a，b，c，d)函数2200(图22)。

在某些实现中，步骤1可以与反量化或反向锯齿形扫描相组合。

在4×4输入数据块上应用的4×4前向核心变换

$\left(\begin{array}{cccc}a& b& c& d\\ e& f& g& h\\ i& j& k& l\\ m& n& o& p\end{array}\right)$

可在2个步骤中实现：

1.应用图41所示的函数4100 PCT4×4(a，b，c，d，e，f，g，h，I，j，k，l，m，n，o，p)。类似于4×4的重叠算子，该函数使用了散置的方法，其中操作被进一步排列成数据块的点的子组上的2×2的运算。这些2×2的运算包括在图42所示的函数4200中实现的奇变换，以及图43所示的函数4300中实现的奇-奇变换。基于更多或更少提升步骤来实现旋转的其它逼近也是可能的。

2.将数据块从重新打乱成这可以与量化/锯齿形扫描相组合。

4×4的输入系数块上的4×4的核心逆变换

$\left(\begin{array}{cccc}a& b& c& d\\ e& f& g& h\\ i& j& k& l\\ m& n& o& p\end{array}\right)$

可以在以下2个步骤中实现：

1.将系数块从重新打乱成这可以与反量化/反向锯齿形扫描相组合。

2.应用图44所示的函数4400 IPCT4×4(a，b，c，d，e，f，g，h，I，j，k，l，m，n，o，p)，它是函数4100 PCT4×4的逆运算。函数4400包括2×2的变换：由图45所示的函数4500实现的奇逆变换，以及由图46所示的函数4600定义的奇-奇逆变换。

7.计算环境

上述基于使用4×4前置/后置滤波的重叠变换的编解码器可以在其中可执行数字媒体信号处理的各种设备的任一个上执行，包括计算机；图像和视频记录、传输和接收设备；便携式视频播放器；视频会议；等等以及其它实例。数字媒体编码技术可以用硬件电路以及在如图47所示的计算机或其它计算环境中执行的数字媒体处理软件来实现。

图47示出了其中可实现所描述的实施例的合适的计算环境(4700)的一般化的示例。计算环境(4700)并非对本发明的使用范围或功能提出任何局限，因为本发明可以在各种通用或专用计算环境中实现。

参考图47，计算环境(4700)包括至少一个处理单元(4710)以及存储器(4720)。在图47中，这一最基本的配置(4730)包括在虚线内。处理单元(4710)执行计算机可执行指令，并可以是真实或虚拟处理器。在多处理系统中，多个处理单元执行计算机可执行指令以提高处理能力。存储器(4720)可以是易失性存储器(例如，寄存器、高速缓存、RAM)、非易失性存储器(例如，ROM、EEPROM、闪存等)或两者的某一组合。存储器(4720)储存实现所描述的解码器/编码器和变换的软件(4780)。

计算环境可具有附加特征。例如，计算环境(4700)包括存储(4740)、一个或多个输入设备(4750)、一个或多个输出设备(4760)以及一个或多个通信连接(4770)。诸如总线、控制器或网络等互连机制(未示出)将计算环境(4700)的组件互连。通常，操作系统软件(未示出)为在计算环境(4700)中执行的其它软件提供了操作环境，并协调计算环境(4700)的组件的活动。

存储(4740)可以是可移动或不可移动的，并包括磁盘、磁带或磁带盒、CD-ROM、CD-RW、DVD或可用于储存信息并可在计算环境(4700)内访问的任何其它介质。存储(4740)储存用于实现基于使用4×4的前置/后置滤波的重叠变换的编解码器的软件(4780)的指令。

输入设备(4750)可以是诸如键盘、鼠标、笔或跟踪球等触摸输入设备、语音输入设备、扫描设备或向计算环境(4700)提供输入的另一设备。对于音频，输入设备(4750)可以是接受模拟或数字形式的音频输入的声卡或类似的设备，或向计算环境提供音频样值的CD-ROM阅读器。输出设备(4760)可以是从计算环境(4700)提供输出的显示器、打印机、扬声器、CD-刻录机或另一设备。

通信连接(4770)允许通过通信介质与另一计算实体进行通信。通信介质在已调制数据信号中传达诸如计算机可执行指令、压缩的音频或视频信息或其它数据等信息。已调制数据信号是其一个或多个特征以对信号中的信息编码的方式来设置或改变的信号。作为示例，而非局限，通信介质可包括用电、光、RF、红外、声学或其它载波实现的有线或无线技术。

本发明的数字媒体处理技术可以在计算机可读介质的通用环境中描述。计算机可读介质可以是可在计算环境内访问的任何可用介质。作为示例，而非局限，对于计算环境(4700)，计算机可读介质包括存储器(4720)、存储(4740)、通信介质以及上述的任一个的组合。

本发明的数字媒体处理技术可以在诸如包括在程序模块中在目标真实或虚拟处理器上的计算环境中执行的计算机可执行指令的通用环境中描述。一般而言，程序模块包括例程、程序、库、对象、类、组件、数据结构等，它们执行特定的任务或实现特定的抽象数据类型。程序模块的功能可以如各种实施例中所需的组合或分开。用于程序模块的计算机可执行指令可以在本地或分布式计算环境中执行。

为演示起见，详细描述使用了如“确定”、“生成”、“调整”和“应用”等术语来描述计算环境中的计算操作。这些术语是由计算机执行的操作的高级抽象，并且不应当与人类执行的动作混淆。对应于这些术语的实际的计算机操作可取决于实现而改变。

4.可逆重叠算子的变体和扩展

可以作出上述可逆重叠算子的各种修改和扩展。尽管上文提出的描述用于一维数据，然而相同的过程可以分离或非分离地应用于多个数据维度。

上述可逆重叠算子实现中描述的正交旋转可以用其近似或可能不正交的其它变换来替换。

此外，尽管以上描述主要集中于输入数据的无损恢复，然而相同的变换也可以用于有损数据压缩。在这一情况下，损失可以在量化过程中发生，或者由于前置或后置滤波器的有限精度/近似实现而发生，或者可由于其它不准确性或多个因素的组合而发生。

此处所描述的可逆重叠算子可应用于数据压缩以外的领域。使用可逆重叠算子的重叠变换本身可以是膨胀性的。

可逆重叠算子可以用适当修改的形式应用来实现多速率滤波器组、小波、具有跨越2个以上块宽度(K＞2N)的支撑的重叠变换。

可逆重叠算子可以用空间上变化的方式来应用，其中重叠滤波器的范围和形状可以跨数据的空间范围而变化。

鉴于可应用本发明的原理的许多可能的实现，要求保护落入所附权利要求书及其等效技术方案的范围和精神之内的所有这样的实施例作为本发明。