基于SIMD重叠变换的数字媒体解码

摘要

一种基于块变换的数字媒体编解码器通过将数字媒体数据的分量重新映射成可对其在并行或单指令、多数据(SIMD)的基础上执行变换的许多运算的矢量或并行单元来实现更快的性能。在一维重叠双正交变换的情况下，数字媒体数据分量被重新映射成可对其在SIMD基础上执行重叠预/后滤波器和块变换部分两者的蝴蝶级的矢量。在二维重叠双正交变换的情况下，数字媒体数据分量被重新映射成可对其在SIMD的基础上执行重叠预/后滤波器和块变换两者的哈达玛算子的矢量。

权利要求

1.一种解码数字媒体的方法，所述方法包括：

从压缩比特流中解码变换系数；

将所解码的变换系数排序成一矢量排列，对所述矢量，能在单指令、多数据的基础上跨所解码的变换系数应用逆重叠双正交变换的运算，其中所述逆重叠双正交变换包括逆重叠滤波器和逆块变换；

向所解码的变换系数的块应用所述逆重叠双正交变换以重构所述数字媒体数据的表示，其中应用所述逆重叠双正交变换包括在单指令、多数据的基础上对所解码的变换系数的所述矢量执行至少一个运算；以及将所述矢量的分量重新映射到所述数字媒体数据的初始排列，

其中所述应用所述逆重叠双正交变换包括向所述数字媒体数据的块应用所述逆块变换，以及向与相邻块重叠的重叠区域应用逆重叠滤波器，其中所述应用所述逆重叠双正交变换还包括对所述矢量在单指令、多数据的基础上应用所述逆重叠滤波器的至少一个运算以及所述逆块变换的至少一个运算。

2.如权利要求1所述的方法，其特征在于，所述逆重叠滤波器的所述至少一个运算和所述逆块变换的所述至少一个运算各自包括2×2的哈达玛变换的逆变换。

3.如权利要求1所述的方法，其特征在于，所述逆重叠滤波器和所述逆块变换各自包括在串行指令基础上应用于所述分量的旋转运算。

4.如权利要求1所述的方法，其特征在于，所述矢量是4分量矢量。

5.如权利要求1所述的方法，所述逆重叠双正交变换是一维重叠双正交变换的逆变换。

6.如权利要求5所述的方法，其特征在于，所述逆重叠滤波器的所述至少一个运算和所述逆块变换的所述至少一个运算各自包括一蝴蝶级。

7.如权利要求5所述的方法，其特征在于，所述逆重叠滤波器和所述逆块变换各自包括在串行指令的基础上应用于所述分量的旋转运算。

8.如权利要求5所述的方法，其特征在于，所述矢量是2分量矢量。

9.一种解码数字媒体数据的数字媒体解码器，包括：

从压缩比特流中解码变换系数的装置；

将所解码的变换系数排序成一矢量排列的装置，对所述矢量，能在单指令、多数据的基础上跨所解码的变换系数应用逆重叠双正交变换的运算，其中所述逆重叠双正交变换包括逆重叠滤波器和逆块变换；

向所解码的变换系数的块应用所述逆重叠双正交变换以重构所述数字媒体数据的表示的装置，其中应用所述逆重叠双正交变换包括在单指令、多数据的基础上对所解码的变换系数的所述矢量执行至少一个运算；以及将所述矢量的分量重新映射到所述数字媒体数据的初始排列的装置，其中应用所述逆重叠双正交变换的装置包括向所述数字媒体数据的块应用所述逆块变换，以及向与相邻块重叠的重叠区域应用逆重叠滤波器的装置，其中所述应用所述逆重叠双正交变换的装置还包括对所述矢量在单指令、多数据的基础上应用所述逆重叠滤波器的至少一个运算以及所述逆块变换的至少一个运算的装置。

10.如权利要求9所述的数字媒体解码器，其特征在于，所述逆重叠滤波器的所述至少一个运算和所述逆块变换的所述至少一个运算各自包括2×2的哈达玛变换的逆变换。

11.如权利要求9所述的数字媒体解码器，其特征在于，所述逆重叠滤波器和所述逆块变换各自包括在串行指令基础上应用于所述分量的旋转运算。

12.如权利要求9所述的数字媒体解码器，其特征在于，所述矢量是4分量矢量。

13.如权利要求9所述的数字媒体解码器，所述逆重叠双正交变换是一维重叠双正交变换的逆变换。

14.如权利要求13所述的数字媒体解码器，其特征在于，所述逆重叠滤波器的所述至少一个运算和所述逆块变换的所述至少一个运算各自包括一蝴蝶级。

15.如权利要求13所述的数字媒体解码器，其特征在于，所述逆重叠滤波器和所述逆块变换各自包括在串行指令的基础上应用于所述分量的旋转运算。

16.如权利要求13所述的数字媒体解码器，其特征在于，所述矢量是2分量矢量。

说明书

基于SIMD重叠变换的数字媒体解码

[0001] 本申请是国际申请日为2006年8月3日、国际申请号为PCT/US2006/030565、中国国家申请日为2006年8月3日、申请号为200680029306.3、发明名称为“基于SIMD重叠变换的数字媒体编码/解码”的专利申请的分案申请。

技术领域

[0002] 本发明涉及数字媒体解码方法和数字媒体解码器，尤其涉及基于SIMD重叠变换的数字媒体解码。

背景技术

[0003] 基于块变换的编码

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

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

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

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

[0008] 对于压缩，变换系数(向量y的分量)可被选择性地量化(即，诸如通过丢弃系数值的最低有效位或将较高分辨率数字集中的值映射到较低分辨率来降低分辨率)，并还可被熵或可变长度编码为压缩的数据流。

[0009] 在解码器150中解码时，如图1所示，在解码器150侧应用这些操作的反过程(反1
量化/熵解码160和反块变换170-171)。在重构数据时，将逆矩阵M(反变换170-171)作为乘数应用于变换域数据。当应用于变换域数据时，反变换几乎重构原始时域或空间域数字媒体。

[0010] 在许多基于块变换达到编码应用中，变换理想地是可逆的以取决于量化因子同时支持有损和无损压缩两者。如果例如没有量化(一般被表示为量化因子1)，则利用可逆变换的编解码器可在解码时精确地再现输入数据。然而，这些应用中的可逆性的要求约束了对用于设计编解码器的变换的选择。

[0011] 诸如MPEG和Windows Media等许多图像和视频压缩系统利用基于离散余弦变换(DCT)的变换。已知DCT具有得到近乎最优的数据压缩的良好能量压缩特性。在这些压缩系统中，在压缩系统的编码器和解码器两者中的重构环路中采用了反DCT(IDCT)来重构各个图像块。

[0012] 重叠变换

[0013] 在上述基于块变换的编码系统中，块变换是连续地应用于输入信号或图像的不重叠相邻块的有限长度(通常是诸如4或8等较短的长度)变换。因此，跨块边界的信号分量不会影响跨边界的块的变换。由于用于数据压缩的高频率分量的量化，对块变换的使用可能会在块边界处引入可察觉到的伪像，即块状现象(blockiness)。块状现象在高度压缩的JPEG图像中是明显的，并且作为图像中的方块或阶梯形而出现。在音频中，块状现象导致周期性的爆音噪声。这些都不是可容许的伪像。

[0014] 重叠变换(图2所示的LT 210)是不会遭受剧烈块状现象的表示信号或图像的替换手段。在重叠变换中，影响每一变换系数集的输入信号分量大于变换输出块的大小。例如，在1D情况下，8个连续的信号分量可能会影响4点变换。同样，对于图像，8×8的区域可能会影响4×4的变换块。

[0015] 重叠变换可用两种方式之一来公式化。重叠变换的一种经典的公式化是一系列块变换后跟一系列混频器。块变换与N点的规则网格(N是变换大小)对齐，而混频器跨块边界对称地间隔开。一种替换的公式化跨块边缘执行预滤波操作，之后是块变换。

[0016] 重叠变换的反变换(例如，图2的ILT 220)的计算和实现一般是直截了当的。反转信号流图，且对每一元素操作求反。反重叠变换的一种经典的公式化是一系列混频器后跟一系列块变换。一种替换的公式化包括一系列块变换后跟跨块边界应用的后滤波操作。

[0017] 在重叠变换的任一公式化中，关键组成部分是(i)块变换，以及(ii)跨块的算子，这可以是混频器、预或后滤波器。这些算子(ii)被统称为重叠滤波器。

[0018] 重叠正交变换(LOT)是重叠变换的一个子类。它们具有前向和反向变换可置换的性质。从压缩观点来看，子类重叠双正交变换更令人感兴趣，因为它们可实现比LOT更好的PSNR。双正交性指的是分析和合成基函数是双正交的(即，互相正交)。

发明内容

[0019] 此处描述的数字媒体编码和解码技术以及该技术在数字媒体编解码器中的实现获得了对用于编码和解码的变换的加速。该技术将重叠(或其它)变换重新公式化为大部分是单指令、多数据(SIMD)友好的一组运算。这是通过重新映射重叠变换的输入和输出采样网格来实现的。通过这一重新映射，输入数据可被分组成“矢量”或并行单元。采用这一重新排列，许多重叠变换步骤可作为矢量运算来执行。不可矢量化的极少剩余运算以串行的方式对矢量分量执行。

[0020] 提供本概述以用简化的形式介绍将在以下详细描述中进一步描述的一些概念。本概述并不旨在标识出所要求保护的主题的关键特征或必要特征，也不旨在用于帮助确定所要求保护的主题的范围。

附图说明

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

[0022] 图2是示出重叠变换的一个示例的流程图。

[0023] 图3是包含了宽范围系数自适应编码的代表性编码器的流程图。

[0024] 图4是包含了自适应编码的宽范围系数的解码的解码器的流程图。

[0025] 图5是示出作为预滤波器(或重叠算子)和块变换的一个示例重叠变换公式化的流程图，其中预滤波器跨块变换的输入边界或块边缘来应用。

[0026] 图6是具有图5的预滤波器和块变换公式化的代表性重叠变换的信号流图。

[0027] 图7是具有图6的预滤波器和块变换公式化的代表性重叠双正交变换的并行化SIMD形式的信号流图。

[0028] 图8是示出将一维数据分组成在图7的一维重叠双正交变换的并行化SIMD形式中使用的2分量矢量的图示。

[0029] 图9是图7的一维重叠双正交变换的矢量信号流图。

[0030] 图10是示出将二维数据分组成在二维重叠双正交变换的并行化SIMD形式中使用的4分量矢量的图示。

[0031] 图11是示出用于按照图10所示的分组成矢量的二维数据的矢量表示法。

[0032] 图12是示出对其应用二维重叠双正交变换的重叠算子(预滤波器)部分并对其应用重叠算子的2×2哈达玛(Hadamard)算子部分的二维数据和相应的并行化分量矢量中的像素分量的图示。

[0033] 图13是示出对其应用二维重叠双正交变换的块变换部分并对其应用块变换部分的2×2哈达玛算子部分的二维数据和相应的并行化分量矢量中的像素分量的图示。

[0034] 图14是示出二维重叠双正交变换的重叠算子的图示。

[0035] 图15是示出实现并行化二维重叠双正交变换的重叠算子的过程的流程图。

[0036] 图16是示出实现并行化二维重叠双正交变换的块变换的过程的流程图。

[0037] 图17是用于实现图3和4的代表性编码器/解码器的并行化SIMD形式的合适的计算环境的框图。

具体实施方式

[0038] 以下描述涉及提供重叠变换的更快实现作为并行化或SIMD运算的编码和解码技术[以下称为“变换并行化技术”]。以下描述在数字媒体压缩系统或编解码器的上下文中描述了该技术的一个示例实现。该数字媒体系统以压缩形式对数字媒体数据进行编码以便传输或存储，并解码该数据以供回放或其它处理。出于说明的目的，包含这一变换并行化技术的该示例性压缩系统是图像或视频压缩系统。或者，该技术也可被结合到用于其它2D数据的压缩系统或编解码器中。变换并行化技术不要求数字媒体压缩系统以特定的编码格式来编码压缩的数字媒体数据。

[0039] 1.编码器/解码器

[0040] 图3和4是在代表性2维(2D)数据编码器300和解码器400中采用的过程的一般化图示。该图呈现了结合了实现变换并行化技术的2D数据编码器和解码器的压缩系统的一般化或简化的图示。在使用变换并行化技术的替换压缩系统中，可使用比本代表性编码器和解码器中所示的更多或更少的过程来进行2D数据压缩。例如，某些编码器/解码器还可包括色彩转换、色彩格式、可缩放编码、无损编码、宏块模式等等。取决于量化，压缩系统(编码器和解码器)可提供2D数据的无损和/或有损压缩，量化可基于从无损到有损变化的量化参数。

[0041] 2D数据编码器300产生压缩比特流320，它是作为输入提供给编码器的2D数据310的更紧凑表示(对于典型输入)。例如，2D数据输入可以是图像、视频序列的一帧、或具有两个维度的其它数据。2D数据编码器将输入数据块化(tile)330成宏块，在本代表性编码器中，宏块的大小为16×16像素。2D数据编码器还将每一宏块块化为4×4的块。
对块之间的每一边缘应用“前向重叠”算子340，之后使用块变换350来变换每一4×4的块。该块变换350可以是由Srinivasan在2004年12月17日提交的题为“Reversible Transform For Lossy And Lossless 2-DData Compression”(用于有损和无损2D数据压缩的可逆变换)的美国专利申请第11/015,707号中所描述的可逆的、无缩放的2D变换，该专利申请的公开内容通过引用结合于此。重叠算子340可以是其公开内容通过引用结合于此的、由Tu等人在2004年12月17日提交的题为“Reversible Overlap Operator for Efficient Lossless Data Compression”(用于高效无损数据压缩的可逆重叠算子)的美国专利申请第11/015,148号；以及其公开内容通过引用结合于此的、Tu等人在2005年1月14日提交的题为“Reversible 2-Dimensional Pre-/Post-Filter for Lapped Biorthogonal Transform”(用于重叠双正交变换的可逆2维预/后滤波器)的美国专利申请第11/035,991号中描述的可逆重叠算子。重叠算子和变换共同实现重叠双正交变换。
或者，可使用离散余弦变换或其它块变换和重叠算子。在变换之后，令每一4×4的变换块的DC系数360经受一类似的处理链(块化、前向重叠、之后是4×4的块变换)。所得的DC变换系数和AC变换系数被量化370、熵编码380和分组化390。

[0042] 解码器执行反过程。在解码器侧，从其各自的分组中提取410变换系数位，从中系数本身被解码420和解量化430。DC系数440通过应用反变换来重新生成，并且DC系数的平面使用跨DC块边缘应用的合适的平滑算子来“反重叠”。随后，通过向DC系数应用4×4的反变换450来重新生成整个数据，并从比特流中解码AC系数442。最后，对所得图像平面中的块边缘进行反重叠滤波460。这产生经重构的2D数据输出。

[0043] 在一个示例性实现中，编码器300(图3)将输入图像压缩成压缩比特流320(例如，文件)，而解码器400(图4)基于是采用无损还是有损编码来重构原始输入或其近似。编码过程涉及应用以下所讨论的前向重叠变换(LT)，这是用同样在以下更全面描述的可逆2维预/后滤波来实现的。解码过程涉及应用使用可逆2维预/后滤波的反重叠变换(ILT)。

[0044] 所示的LT和ILT在确切的意义上是彼此的反过程，并且因此可被统称为可逆重叠变换。作为一种可逆变换，LT/ILT对可用于无损图像压缩。

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

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

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

[0048] 2.对于YUV 4:2:0格式彩色图像，每一宏块包含16个4×4的Y块，并且4个各自为4×4的色度(U和V)块。

[0049] 3.对于YUV 4:2:2格式彩色图像，每一宏块包含16个4×4的Y块，以及8个各自为4×4的色度(U和V)块。

[0050] 4.对于RGB或YUV 4:4:4彩色图像，每一宏块包含对Y、U和V通道中的每一个包含16个块。

[0051] 2.快速SIMD重叠双正交变换概述

[0052] 上述代表性编码器300(图3)和解码器400(图4)中的计算上更复杂的运算之一是重叠双正交变换。该运算的复杂度影响编码器和解码器两者的性能。

[0053] 在专利申请(Srinivasan于2004年12月17日提交的题为“Reversible Transform For Lossy And Lossless 2-D Data Compression”的美国专利申请第11/015,707号；Tu等人于2004年12月17日提交的题为“Reversible Overlap Operator for Efficient Lossless Data Compression”的美国专利申请第11/015,148号；以及Tu等人于2005年1月14日提交的题为“Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号)中描述的重叠双正交变换的实现被设计成最小化复杂度。然而，此处所描述的变换并行化通过以SIMD(单指令、多数据)或并行指令友好的方式公式化重叠变换运算来实现进一步的加速。SIMD运算可用于并行地计算多个指令。这一SIMD指令在各种处理器上都得到支持，包括来自英特尔的奔腾 系列处理器、来自AMD的各种x86兼容处理器、PowerPC 和各种其它DSP(数字信号处理器)。

[0054] 此处所描述的变换并行化技术将重叠(或其它)变换重新公式化为大部分是SIMD友好的一组运算。这是通过重新映射重叠变换的输入和输出采样网格来实现的。通过这一重新映射，输入数据可被分组成“矢量”或并行单元。采用这一重新排列，许多重叠变换步骤可作为矢量运算来执行。不可矢量化的极少其余运算以串行的方式在矢量分量上执行。

[0055] 尽管该技术一般可应用于重叠变换，但是以下出于说明的目的讨论了该技术对于代表性编码器和解码器的重叠双正交变换(即，在以上列出的专利申请中详细描述的重叠双正交变换)的一种具体应用。该变换并行化技术重新映射并分组代表性重叠双正交变换的输入采样网格或点阵，使得每一组数据样本可作为用于实现重叠变换的许多操作的矢量来对待。在这一特定的重叠双正交变换示例中，该技术被用于公式化4点重叠算子和4点块变换的SIMD友好形式，但是该技术也可被推广到其它变换长度。此外，该技术或者可被用于创建其它重叠变换实现的SIMD或并行指令形式。

[0056] 以下小节详细描述了代表性重叠双正交变换的一维和二维SIMD友好实现。在一维情况下，两个元素可被分组在一起成一矢量，并且许多1D重叠变换运算可使用矢量运算来执行。在二维情况下，两个或四个元素可被分组在一起成一矢量，并且许多重叠变换运算可使用矢量运算来执行。

[0057] 这些矢量化技术同样适用于前向和反向变换(分别由编码器和解码器使用)。

[0058] 2.1一维重叠双正交变换的SIMD实现

[0059] 参考图5，考虑被公式化为预滤波器(重叠算子)510和块变换520的重叠变换500的一般情况。在所示的示例情况中，块变换520具有块大小4，而预滤波器510也具有重叠大小4。重叠大小被定义为预/后滤波器长度。由此，如果数据序列被标号为x0，x1，x2，x3等，则重叠变换500如下进行：

[0060] 1.将预滤波器510应用于每一输入数据集[x4i+2，x4i+3，x4i+4，x4i+5]；以及[0061] 2.将块变换520应用于每一集合[x4i，x4i+1，x4i+2，x4i+3]。在替换实现中，重叠变换可用其它不同的块变换大小和重叠大小来定义。

[0062] 图6示出了具有如图5所示的预滤波器和块变换公式化的重叠双正交变换600的一个更具体示例。重叠双正交变换600如上所述在代表性编码器300(图3)和解码器400(图4)中使用，其实现在以下专利申请中更具体地详述：Srinivasan于2004年12月17日提交的题为“Reversible Transform For Lossy And Lossless 2-DData Compression”的美国专利申请第11/015,707号；Tu等人于2004年12月17日提交的题为“Reversible Overlap Operator for Efficient Lossless Data Compression”的美国专利申请第11/015,148号；以及Tu等人于2005年1月14日提交的题为“Reversible
2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号。为简明起见，编码器300的预滤波器和块变换在图6中描述。用于解码器的反重叠变换的后滤波器和反块变换是前向重叠变换600的反过程。如图6所示，预滤波器具有作为一组蝴蝶或提升步运算的实现，这些运算被组织为第一蝴蝶级610、旋转/缩放620、以及第二蝴蝶级630。块变换具有作为第三蝴蝶级640和旋转650的实现。

[0063] 并行化用于使用SIMD指令的实现的运算的一种方式是通过简单地将跨块的相同索引的信号分量分组在一起。换言之，对某一j，形式为x4i+j的分量被分组在一起。对于此处所考虑的具体重叠双正交变换600，2分量的矢量可以为：[x14x18]、[x15x19]、[x16x20]、和[x17x21]。

[0064] 这一分组对于预滤波器能起很好的作用。然而，对于块变换，矢量[x14x18]和[x16x20]跨越了三个而不是两个块。这意味着这一分组不能用于实现对重叠变换的整体加速。在变换级，所需的分组是不同的：[x16x20]、[x17x21]、[x18x22]和[x19x23]。

[0065] 比较用于预滤波器和块变换的所需分组，可以看到有两个矢量对两个分组是共同的(即，[x16x20]和[x17x21])。然而，其余两个矢量在各分组之间不同，这将必须在预滤波器和块变换之间对矢量进行重新分组。这并不是合乎需要的解决方案。

[0066] 另一方面，该变换并行化技术提出了一种并行化1D重叠变换的替换方式。采用该替换技术，在重叠变换之前或之后在某些分量之间添加了一置换，使得将分量分组成SIMD指令矢量对于预滤波器和块变换级两者是共同的。

[0067] 图7示出了图6的重叠双正交变换的经修改的实现700，它是根据此处所描述的变换并行化技术来并行化的。该经修改的重叠变换实现700在功能上等同于图6的重叠双正交变换实现600，但是包括第一级中的分量的扭转或置换710，以及略微不同的蝴蝶网络720、740和750。这些蝴蝶级可与2分量矢量并行地实现，因为对于这些级，奇分量仅与奇分量相互作用，而偶分量仅与偶分量相互作用。此外，用于奇分量和偶分量的运算在这些级中是相同的。由此，对相邻的奇和偶分量的分组实现了并行实现。

[0068] 尽管如此，该重叠双正交变换的SIMD实现700的某些级仍是不可并行化的。预滤波器中的旋转/缩放步730和块变换中的旋转步760被串行地实现。

[0069] 图9描绘了使用如图8所示的数据变为2分量矢量的排列的重叠双正交变换700(图7)的一个实现900。在图9中，数据路径的值为2分量矢量，并且加粗箭头是矢量内运算(即，同一矢量的分量之间的运算)。图8所示的矢量分组用于输入，这基于以下分量一矢量映射规则：

[0070] v2i＝[x4i x4i+1]

[0071] v2i+1＝[x4i+3x4i+2]

[0072] 该映射将原始信号分组成2分量矢量，对于许多重叠变换步骤向这些矢量应用SIMD算术，而对于其余的步骤应用串行处理。

[0073] 2.2二维重叠双正交变换的SIMD实现

[0074] 二维重叠双正交变换(2D LBT)可使用刚才描述的一维重叠双正交变换(1DLBT)来实现。在这一实现中，将1D LBT应用于图像的每一行，接着将1D LBT应用于每一列(或相反)。在这一情况下，可使用两种矢量化技术：

[0075] 1.在第一种矢量化中，可对水平和垂直变换使用1D LBT中使用的相同的分组(如在以上2.1节中描述的)。

[0076] 2.在第二种矢量化中，可通过将多行的相同索引的分量分组在一起同时沿行实现1D LBT，并将多列的相同索引的分量分组在一起同时沿列实现1D LBT来形成矢量。

[0077] 在这两种技术中，矢量化在行和列变换之间改变。这导致在变换计算期间从一种矢量化格式到另一种的重新映射的附加成本，这可能是昂贵的。不涉及变换级之间的重新打乱的一种替换矢量化技术将在下文描述。

[0078] 此外，以上列出的专利申请(即，Srinivasan于2004年12月17日提交的题 为“Reversible Transform For Lossy And Lossless 2-D Data Compression”的美国专利申请第11/015,707号；以及Tu等人于2005年1月14日提交的题为“Reversible2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号)中描述的2D LBT在两个维度中直接实现LBT。该变换不能被分割成两个1D运算。

[0079] 对于这一直接2D LBT实现(以及对于可分割的2D实现)的并行化SIMB形式，首先如图10所示地应用双向扭转重新映射1000-1001。区域1010内的每一4×4像素块被映射1000-1001到区域1020内的四个4分量矢量，使得每一矢量包含来自4×4块的2×2子块的像素。矢量内的分量的排序遵循以上描述的1D重新映射(图7所示的置换710)的二维扩展。图11示出了用于所得的区域1020中的一组4分量矢量的矢量表示法1100。

[0080] 如此形成的4分量矢量具有以下性质：在直接2D LBT的重叠算子级或块变换级中向其应用哈达玛变换的4个像素的组在矢量内的同一位置中对齐。这对于重叠算子在图12中示出，而对于光子核变换在图13中示出，并在下文中详细解释。

[0081] 2.2.1二维重叠双正交变换的SIMD实现中重叠算子的并行实现

[0082] 再次参考图5，跨块边界来应用重叠变换中的重叠算子(预滤波器510)。这可在块变换520之前或之后完成。

[0083] 在以上列出的专利申请(即，Srinivasan于2004年12月17日提交的题为“Reversible Transform For Lossy And Lossless 2-D Data Compression”的美国专利申请第11/015,707号；以及Tu等人于2005年1月14日提交的题为“Reversible2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号)中描述的2D LBT实现的情况下，在编码器侧在块变换之前应用重叠算子。同样，在解码器侧在反块变换之后应用重叠算子。不考虑图像的边界处的特殊情况，重叠算子被应用于跨4个4×4的块的4×4区域。

[0084] 参考图14，该2D LBT实现的重叠算子1400由应用于对称地位于网格中的像素象限的两个2×2哈达玛变换1410、之后的旋转和缩放级1420和1430、之后的应用于同一像素象限的另一2×2哈达玛变换1440构成。运算细节由Tu等人于2005年1月14日提交的题为“Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号来提供。可如本专利申请中所描述地在2D LBT公式化中使用进一步的简化，其中缩放级和2×2哈达玛级之一略去某些运算。

[0085] 对于该重叠算子的并行化SIMD形式，首先应用如上在2.2节中描述并在图10和11中示出的相同矢量化过程。参考图15，基于该矢量化数据的重叠算子的并行化SIMD形式根据以下过程1500来实现：

[0086] 1.如在动作1510处所指示的，将图像或其它二维数据工作区域矢量化成如图10和11所示的4分量矢量。

[0087] 2.对整个图像上跨4个4×4的块1200的每一4×4的重叠区域执行动作1520-1570中的重叠运算，如图12所示。对于此运算，使用利用图11所示的矢量表示法标识为[v3 v6 v9 v12]的矢量。对所有这些区域重复这些步骤。

[0088] 3.首先，在动作1530处在这4个矢量之中执行2×2哈达玛运算。

[0089] 4.对于下一动作1540，在矢量v3和v12之间执行缩放运算(在以下专利申请中详细描述：Tu等人于2004年12月17日提交的题为“Reversible Overlap Operator for Efficient Lossless Data Compression”的美国专利申请第11/015,148号；以及Tu等人于2005年1月14日提交的题为“Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号)。

[0090] 5.在矢量v6、v9和v12的分量内执行旋转1550。这些大多是大部分没有利用数据并行性的串行运算。

[0091] 6.最后，在动作1560处在重叠区域的四个矢量[v3 v6 v9 v12]之中再次执行2×2哈达玛运算。

[0092] 在过程1500中，以上运算是对所指示的矢量原地执行的。此外，在实践中，可取消以上步骤3和4之间的某些，这导致进一步的简化，如在以下专利申请中详细描述的：Tu等人于2004年12月17日提交的题为“Reversible Overlap Operator for Efficient Lossless Data Compression”的美国专利申请第11/015,148号；以及Tu等人于2005年1月14日提交的题为“Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号。

[0093] 2.2.2二维重叠双正交变换的SIMD实现中块变换的并行实现

[0094] 在向块内的所有2×2子块应用重叠算子之后，4×4的块1300(图13)准备好进行块变换。块变换运算保持相同的矢量化-因此不必在重叠和块变换运算之间打乱数据。

[0095] 参考图16，根据以下过程1600执行块变换的并行实现。该过程以仍由用对于图10和11中所示的重叠算子的动作1510(图16)矢量化的图像或工作区域开始。另一方面，在向2D数据单独应用块变换而没有首先应用重叠算子过程1500的情况下，过程1600改为通过执行动作1510来提供相同的矢量化而开始。

[0096] 1.在动作1610-1640的循环中，向图像的每一4×4的块1300应用变换。例如，图13所示的矢量[v0 v1 v2 v3]用于左上块。对所有块重复这些步骤。

[0097] 2.在第一动作1620处，在这4个矢量之中执行2×2哈达玛运算。

[0098] 3.在下一动作1630处，在矢量v0，v1，v2和v3的分量内执行旋转。这些大多是大部分没有利用数据并行性的串行运算。所执行的旋转如在以下专利申请中详细描述的：Srinivasan于2004年12月17日提交的题为“Reversible Transform For Lossy And Lossless 2-D Data Compression”的美国专利申请第11/015,707号；以及Tu等人于2005年1月14日提交的题为“Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform”的美国专利申请第11/035,991号。

[0099] 在SIMD重叠变换的替换实现中，应用于块的矢量的变换运算可以是其它类似DCT的变换的那些变换运算(而非以上列出的专利申请中所描述的可逆变换)。

[0100] 2.3扩展

[0101] 对于重叠算子1500和变换1600过程两者，四路的2×2哈达玛变换是基本且重复的运算。采用由如图10和11所示的矢量化来排序的数据分量，该2×2哈达玛作为对这些矢量操作的SIMD指令来容易地执行。此外，对于重叠算子，缩放运算同样可作为对这些矢量操作的SIMD指令来执行。旋转(动作1550、1630)是可部分并行化的。这是因为所涉及的某些旋转是对4分量矢量内的两对数据点执行的相同的1D运算。这些旋转也可用乘法和位移运算来并行化。

[0102] 由于矢量中的数据分量的重排，变换的最终输出也被重排。这通常不是问题，因为扫描变换以在压缩比特流中将系数重排为用于编码器的输出的列表。在并行实现中，扫描数组考虑了重排，并且对于算法复杂度没有负面影响。

[0103] 同样的并行化技术也适用于反重叠双正交变换，除了块变换和重叠算子的顺序被反转之外，并且相应过程中的动作1530-1560和1620-1630的顺序被反转。重排的扫描模式用于填充输入数据数组，并且之后输出以与图10所示的映射相反的方式来重新映射。

[0104] 该并行化技术还适用于使用其它形式的重叠正交/双正交变换的替换实现。如在块变换过程1600的讨论中所指出的，并行化也可用于块变换本身(即，没有重叠算子)。除4之外的其它变换和重叠大小以及大于2的维度也用并行化逻辑的直接扩展来适应。

[0105] 矢量化的成本通过在色彩转换级期间在编码器上对扭转点阵执行重新映射，并在解码器上从扭转点阵重新映射来最小化。解码器中的色彩转换一般是串行实现的，这是由于以下若干原因：(i)多种色彩格式，(ii)由于许多色彩格式的24位像素边界而导致的缺少字对齐，(iii)在解码器侧上执行限幅的需求等等。在色彩转换上以及其上方进行重新映射的附加成本是最小的，并便于使用该并行化技术来获得总体性能改善。此外，当在旋转和/或横向翻转方向上呈现输入图像或当在旋转和/或横向翻转方向上期望输出图像时，这可在对总体计算复杂度几乎没有任何增加的情况下实现。

[0106] 3.计算环境

[0107] 上述包含了使用变换并行化技术实现的重叠双正交变换的代表性编码器300(图3)和解码器400(图4)可以在其中执行数字媒体信号处理的各种设备中的任一种上执行，这些设备包括计算机；图像和视频记录、传输和接收设备；便携式视频播放器；视频会议；
以及其它示例。数字媒体编码技术可以用硬件电路以及诸如在图17所示的计算机或其它计算环境中执行的数字媒体处理软件来实现。

[0108] 图17示出了其中可实现所描述的实施例的合适的计算环境(1700)的一般化的示例。计算环境(1700)并不对本发明使用范围或功能提出任何局限，因为本发明可在不同的通用或专用计算环境中实现。

[0109] 参考图17，计算环境(1700)包括至少一个处理单元(1710)和存储器(1720)。在图17中，这一最基本的配置(1730)被包括在虚线内。处理单元(1710)执行计算机可执行指令，并且可以是真实或虚拟处理器。在多处理系统中，多个处理单元执行计算机可执行指令以提高处理能力。存储器(1720)可以是易失性存储器(例如，寄存器、高速缓存、RAM)、非易失性存储器(例如，ROM、EEPROM、闪存等)或两者的某种组合。存储器(1720)储存实现所描述的数字媒体编码/解码和变换并行化技术的软件(1780)。

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

[0111] 存储(1740)可以是可移动或不可移动的，并包括磁盘、磁带或磁带盒、CD-ROM、CD-RW、DVD或可用于储存信息并可在计算环境(1700)内访问的任何其它介质。存储(1740)储存用于实现所描述的使用变换并行化技术的编码器/解码器的软件(1780)的指令。

[0112] 输入设备(1750)可以是诸如键盘、鼠标、笔或跟踪球等触摸输入设备、语音输入设备、扫描设备或向计算环境(1700)提供输入的另一设备。对于音频，输入设备(1750)可以是声卡或接受模拟或数字形式的音频输入的类似设备、或将音频样本提供给计算环境的CD-ROM读取器。输出设备(1760)可以是显示器、打印机、CD刻录机或提供来自计算环境(1700)的输出的另一设备。

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

[0114] 此处的数字媒体处理技术可在计算机可读介质的一般上下文中描述。计算机可读介质可以是可在计算环境内访问的任何可用介质。作为示例而非局限，对于计算环境(1700)，计算机可读介质包括存储器(1720)、存储(1740)、通信介质和以上任一种的组合。

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

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

[0117] 鉴于此处描述的主题的许多可能的变型，要求保护落入所附权利要求书及其等效技术范围内的所有这些实施例作为本发明。