用通用多级树中的集合分裂针对图像和视频自适应熵编码

摘要

本申请涉及用通用多级树中的集合分裂针对图像和视频自适应熵编码，可应用于嵌入式和非嵌入式编码二者。在编码期间的去相关和量化之后，基于图像块内的几何关系，树结构被从多个候选中选出用于编码系数以改善系数零的聚集。树结构具有指定布置中的叶子和非叶子节点，其中包含系数的叶子节点与每个非叶子节点相关联。通过恰当的树选择，可从编码后的输出流中被去除的零聚集系数的个数增多。在解码期间，与针对当前块的编码相兼容的树结构被用来从符号流中解码现有系数并恢复缺失的零系数。

说明书

相关申请的交叉引用

本申请要求2010年4月13日递交的序列号为12/758,981的美国专利 申请的优先权，该美国专利申请的全部内容通过引用被结合于此。本申请 还要求2009年6月9日递交的序列号为61/185,568的美国临时专利申请的 优先权，该美国临时专利申请的全部内容通过引用被结合于此。

技术领域

本发明一般地涉及图像和视频编码，并且更具体地，涉及利用通用多 级树(generalized hierarchical trees)中的集合分裂(set partitioning)的自 适应熵编码装置和方法。

背景技术

熵编码是图像和视频压缩的重要组成部分，图像和视频压缩通常响应 于以下步骤：(1)执行变换(或者，可选地在变换前执行预测)，(2) 量化，以及(3)熵编码。

以下针对常用的JPEG熵编码方法进行描述，JPEG表示联合图像专家 组并且是用于一组计算机图像文件压缩技术的ISO/IEC标准。JPEG文件 是通过从一组压缩质量中进行选择而被创建的，更准确地说，是根据多个 压缩算法中的一种而被创建的。在通过JPEG压缩来转换图像时，结果图 像的目标大小或质量被指定为接近或小于原始图像的质量水平。因为最高 质量的图像产生最大的文件，所以在图像质量和文件大小之间存在折衷。 根据该标准的JPEG方案包括二十九(29)个不同的编码步骤，尽管JPEG 实现装置可以不使用全部的步骤。

当执行JPEG中的熵编码时，每个8×8的块被使用离散余弦变换 (DCT)进行变换，然后DCT系数受到量化、Z形(zig-zag)扫描以及游 程长度编码。可以理解，通过创建相同像素的线性组而非个别地存储每个 像素的值，游程长度编码提供了一种以较低速率来对DCT系数进行编码 的方式。DCT提供了用于将任何波形表示为余弦的加权和的机制，其中心 在于各种形式的信号处理，尤其是图像和视频压缩的信号处理。

图1A图示出4×4块中的Z形扫描的示例，系数位置被示出在图1B 中。根据此Z形模式执行JPEG的熵编码存在许多缺点。尤其是存在以下 缺点：(1)速率控制机制的缺失，同时(2)Z形扫描破坏了DCT系数的 2D相关性，并且(3)固定的Z形扫描是基于大量图像数据的统计特性 的，因此不适合局部图像块的局部特性(例如，方向性)。

应理解，量化中使用的参数部分地决定了速率控制，因此通常需要尝 试不同的量化参数以得到希望的文件大小。

基于位平面(bit plane)的熵编码被广泛用于可伸缩(scalable)图像/ 视频编码。在此过程中，变换系数被转换为二进制形式，并且从最高有效 位平面(MSB)到最低有效位平面(LSB)被编码。在此过程中，较低位 平面的编码和解码是基于较高位平面的知识的。比特流编码过程可在任何 位置处被停止，以在提供合理的良好重构质量的同时满足给定的比特率预 算(bitrate budget)。可以具有在编码过程中的任一点处停止的能力是因 为每个系数的最重要的部分(MSB)已经被编码。已知的该比特流编码机 制是嵌入式编码，并且提供良好的速率控制。

关于2D相关性的缺失，可以看到，例如，如在4×4的块中示出的， 图1B中系数位置2和6在频谱中接近，然而响应于图1A中所示的Z形扫 描顺序，它们是不相邻的并且实际上彼此远离。对于某种类型的块，如果 系数位置2是非零的，则6非常可能也是非零的；在这种情况下，Z形扫 描将可能使长的游程中断并且降低编码效率。

为了提高诸如图像和视频之类的2D可视信号的编码效率，适应局部 几何特征是近来的趋势。然而，这些方法尚未与适当的熵编码方法很好地 关联起来，因此统计学冗余未被充分开发。相反，本发明阐释了设计自适 应熵编码方法的重要性。

因此，需要用于执行复杂度低且效率高的速率可控熵编码和解码的方 法和装置。本发明满足了这些需求和其他需求，克服了之前开发的基于熵 的图像/视频编码技术中的不足。

发明内容

本发明提供了利用通用多级树中的集合分裂的用于图像和视频的自适 应熵编码方法。为了描述简便，通用多级树中的集合分裂在此被称作首字 母缩略词“SPRIGHT”。SPRIGHT编码方法可被用于嵌入式编码，因为 它共享类似的特征并且它可提供速率可控性。

SPRIGHT编码遵循如下的一般步骤：将图像(或视频帧)划分为块， 利用变换对每个块进行去相关(可选地，在变换之前可以存在预测)，量 化变换系数，从多个树的集合(即树的预定集合)中选择树并且利用该所 选树来编码块。编码效率被大幅提高，因为树不是固定的而是响应于存在 于系数的块内的2D关系而被选出的。

本发明是可修改的以以多种方式来实现，这些方式包括而不限于以下 描述。

本发明的一个实施例是一种用于图像或视频编码器内的自适应熵编码 的装置，包括：(a)被配置用于图像/视频编码的计算机；(b)耦合到所 述计算机的存储器；以及(c)可在所述计算机上执行的程序，用于执行 以下步骤：(c)(i)将图像或视频帧划分为块(例如，块可以具有任何 希望的形状和大小，包括4×4、8×8和16×16、32×32)，(c)(ii) (在根据重构了的块的预测之后)利用变换(例如，空间变换)对每个块 进行去相关，(c)(iii)量化变换系数，(c)(iv)响应于对图像的像 素块内的几何关系的确定，从多个候选中选择希望的树结构，该几何关系 有时等同于块的变换系数之间的关系，以及(c)(v)响应于所选择的树 结构，利用零系数的聚集来对块进行编码。上文中，将会理解，响应于使 得所述所选择的树结构中的非叶子节点表示其相应的叶子节点仅包含零系 数并且不将这些子孙叶子节点编码到由所述装置在编码图像/视频时生成的 输出比特流中，零系数的部分被从编码后的输出中去除。

在本发明的至少一个实施例中，将块编码到所选树结构中是根据对树 结构的预定遍历来执行的，例如使用广度优先遍历(BFT)方法。这里使 用的短语“预定遍历”表示处理如何通过给定树的节点前进的模式。使用 预定遍历，解码器能够遵循在编码时使用了的、通过树的相同模式，从而 变换系数被解码到与它们被编码时的顺序相同的顺序中。可替换地，编码 器和解码器可使用任何希望的机制来使解码顺序与编码顺序同步，而不会 背离本发明的教导。

将注意到，多个候选树结构中的每个是通过具有指定配置的叶子和非 叶子节点二者来配置的，其中包含系数的一个或多个叶子节点被与每个非 叶子节点相关联。在本发明的至少一种实现方式中，通过指示出每个非叶 子节点的子孙叶子节点是全都包含零系数还是不全都包含零系数的比特 (例如，0＝叶子节点都是零，1＝叶子节点系数不都是零)，来表示每个非 叶子节点的状态。在本发明的一种模式中，树结构的集合被保留在编码器 中，并且被配置用于允许树结构中的一种树结构被选出用于对块进行编 码。块内的各种几何关系能够被识别，例如平坦、嘈杂、水平、垂直、对 角线+45°、对角线-45°以及其他所希望的，而不会背离本发明的教导。这 样的几何关系可被等同地转化为被编码的块中的变换系数之间的二维关 系。

在至少一种实现方式中，编码器将关于在对图像的每个块进行编码时 选择了哪种树结构的信息提供给解码器，并且可选地在多种变换中的一种 被选择的情况下将关于当对图像/视频的块进行去相关时使用了哪种变换的 信息提供给解码器。作为示例而非限制，索引可被传送给解码器以传递关 于哪种树结构被选择的信息以及可选地哪种变换被使用的信息。虽然变换/ 树结构的信令消耗开销比特，但是开销比特率可通过对信令进行编码(例 如响应于算术编码)来降低。

本发明的至少一种实现方式还包括在执行变换之前执行块间预测或对 块的预滤波。

本发明的实施例可被配置用于非嵌入式或嵌入式编码，在嵌入式编码 中，在任意希望数目的位平面间执行编码并且能够以任意希望的编码速率 来停止编码。

本发明的一个实施例是一种用于对图像或视频进行自适应熵编码和解 码的系统，包括：(a)被配置用于图像/视频编码的具有处理元件和存储 器的编码器；(b)在所述编码器的处理元件上可执行的用于执行以下步 骤的程序：(b)(i)将图像或视频帧划分为块，(b)(ii)(在可选的 根据重构了的块的预测之后)利用变换对每个块进行去相关，(b)(iii) 量化变换系数，(b)(iv)响应于对块内的几何关系的确定，从多个候选 的集合中选择树结构，以及(b)(v)响应于使用从多个候选中所选择的 树结构，利用零系数的聚集来对块进行编码；以及(c)被配置用于对来 自所述编码器的图像/视频比特流进行图像/视频解码的具有处理元件和存 储器的解码器；(d)在所述解码器的处理元件上可执行的用于响应于执 行以下步骤来输出图像/视频信号的程序：(d)(i)确定在对块进行编码 时由所述编码器选择的树结构，(d)(ii)将树结构的叶子解码为输出中 的系数，(d)(iii)响应于对没有非零分支的非叶子节点进行解码，在输 出中输出零系数，(d)(iv)对输出执行反量化，(d)(v)对输出执行 逆变换，以及(d)(vi)响应于对输出的接收来重构图像或视频信号。在 编码处理中，响应于使得非叶子节点表示相应的叶子节点仅包含零系数， 零系数的部分被从输出中去除。解码处理使用在编码期间选出的相同树结 构来恰当地针对每个块解译符号。

本发明的一个实施例是一种用于图像编码器内的自适应熵编码的方 法，包括以下步骤：(a)将图像或视频帧划分为块；(b)(在可选的根 据重构了的块的预测之后)利用频谱变换对每个块进行去相关；(c)量 化变换系数；(d)响应于对图像/视频的系数块内的二维关系的确定，从 多个候选中选择树结构；以及(e)响应于所选择的树结构，在聚集零系 数的同时对块进行编码。从以上内容应当理解，响应于使得所述所选择的 树结构中的非叶子节点表示其相应的叶子节点仅包含零系数，零系数的部 分被从编码后的输出中去除。

本发明的一个实施例允许编码器和解码器二者基于先前解码的图像/视 频块的统计特性来修改(adapt)候选树中的一个或多个树结构；并且该修 改以如下方式被完成：当处理某一个块时，编码器和解码器总是具有相同 的候选树集合。

本发明提供了可单独实现或以任何希望的组合实现而不会背离本发明 教导的多个有益要素。

本发明的一个要素提供了具有高编码效率的图像/视频编码。

本发明的另一要素是响应于所选树结构中的零系数的聚集以及在编码 后的输出流中跳过聚集的零系数来提供高编码效率的编码和解码。

本发明的又一要素是不依赖于用于编码/解码每个块的固定树结构的编 码和解码。

本发明的又一要素是包括在对图像/视频块进行去相关之前的块间或帧 间预测。

本发明的又一要素是从多种可能的变换操作中(例如，DCT、DWT、 重叠的变换或方向性变换)选择一种去相关变换操作。

本发明的又一要素是基于在被编码时被编码的块内的几何关系来从多 个候选中选择树结构的编码。

本发明的又一要素是响应于对树结构的预定遍历的编码和解码。

本发明的又一要素是其中对树结构的预定遍历包括执行广度优先遍历 (BFT)的编码和解码。

本发明的又一要素是将关于在编码期间使用了哪种去相关变换和/或哪 种树结构的信息传送给解码器。

本发明的又一要素是变换/树结构的信令以及编码后的比特流允许对比 特率的进一步的降低，例如通过利用算术编码。

本发明的又一要素是可在嵌入式和非嵌入式图像编码系统二者中使用 的编码和解码方法。

在说明书的以下部分中将给出本发明的更多要素，其中详细的描述是 为了充分公开本发明的优选实施例而非为了对本发明施以限制。

附图说明

通过参考以下仅用于进行说明的附图将更加充分地理解本发明：

图1A-图1B是示出Z形扫描顺序(图1A中)和系数位置(图1B 中)的系数块阵列。

图2A-图2C是四个系数(A-D)的变换后的块的系数数据图(图2A 中)，以及根据本发明的要素的针对块可供选择的树多级结构的系数数据 图(图2B-图2C中)。

图3A-图3C是系数块的系数数据图，以及根据本发明的要素的针对 块选择的树多级结构操作的系数数据图。

图4A-图4C是与图3A略微不同的系数块的系数数据图，以及其相关 联的根据本发明的要素的针对块选择的树多级结构操作的系数数据图。

图5是为了对块进行去相关而对其执行了哈尔(Haar)变换的系数块 阵列。

图6A-图6D是示出根据本发明要素的可被选择的多个树多级结构的 系数数据图。

图7是根据本发明实施例的SPRIGHT编码和解码的框图，示出了树 类型选择控制编码和解码过程二者。

图8是编码器-解码器系统的框图，示出了根据本发明实施例的被配置 用于执行自适应熵编码和解码的计算机处理器和存储器。

图9是根据本发明实施例的自适应熵编码方法的流程图。

图10是根据本发明实施例的自适应熵解码方法的流程图。

具体实施方式

现更具体地参考附图，出于举例说明目的，本发明在图2A到图10中 一般地示出的装置中被实现。应理解，装置的配置以及部件的细节可以改 变，并且方法的具体步骤和顺序可以改变，而不会背离这里公开的基本概 念。

1、介绍

描述了自适应熵编码和解码的装置和方法，其利用通用多级树中的集 合分裂来编码和解码图像或视频。作为示例而非限制，用“通用多级树中 的集合分裂(Set PaRtitioning in Generalized Hierarchical Trees)”的首字母 缩略词“SPRIGHT”来一般地称呼该装置和方法。

图像或视频帧被划分为块，每个块(可选地从先前重构的块预测出， 并且)被利用变换来进行去相关(decorrelate)，其变换系数被量化，并 且响应于块内的几何关系，树从多个候选中(例如，从预定树的集合中) 被选出，尤其是响应于该块中各系数之间的二维(2D)关系来执行选择。 该块然后响应于所选择的树结构被编码。编码效率显著提高，因为树不是 固定的而是响应于存在于系数块内的2D关系而被选择的。

应理解，可以以各种不同的方式来将图像或视频帧划分为块，而不会 背离本发明的教导。例如，可以以任何随意的形状或大小来配置块，这些 块不必是正方形或矩形的。每个块可以包含单一的或多个颜色分量。块可 以是彼此重叠的，如果结合重叠的变换的话。不太优选地，块可以包括整 个图像或视频帧。

在执行变换之前，应理解，块间预测或预滤波可被执行，然而这不是 必需的。

图像或视频帧的每个块然后根据以下的编码步骤被处理。块内的值被 利用变换来进行去相关，该变换例如是离散余弦变换(DCT)、离散小波 变换(DWT)或提供去相关的其他变换。应理解，根据本发明的一种实现 方式，可以在同一图像或视频帧中使用不同类型的变换。如果不同类型的 变换被使用，则用于块的变换的类型应当被传送给解码器，例如通过响应 于针对每个块而被编码的一个或多个比特的状态来发信号通知给解码器。

块内的变换系数然后被量化。应理解，量化步骤将把低于希望的量化 阈值的所有系数都量化为零。

然后针对每个块从多个候选树结构中选出树结构。树结构选择优选地 是响应于每个块内的系数之间的关系(例如二维关系)从预定树的集合中 进行的，然后每个块被利用所选出的树结构进行编码。

应理解，编码所使用的树结构并非对于所有给定的块而固定，而是基 于被编码的具体块的频谱特征而被选出的，因此编码效率可被显著提高。 可选地，编码器和解码器都可以基于先前解码的块的统计特性来修改(一 个或多个)树结构；执行修改使得当处理某一个块时，编码器和解码器二 者具有相同的候选树的集合。

所选树的索引应当被用信号通知给解码器，以使得解码器能够确定当 块被编码时所选择的树结构。

应理解，在所使用的变换和所选择的树结构之间通常存在关系。因 此，在许多实现方式中，编码器将发送一个索引来表示(变换，树)对， 这使得(变换，树)能够共同地被优化。

树结构和/或变换的索引需要利用一些开销比特(overhead bit)。应理 解，通过将诸如算术编码之类的编码技术应用于索引，开销的量优选地被 降低。

2、SPRIGHT中的树结构

图2A-2C图示出经过变换的2×2的块以及作为示例而非限制示出的 多个树结构。应认识到，本发明可被应用于任何大小的块而不会背离本发 明的教导。为了简便起见，图2A图示了较小的2×2的经过变换的块10， 其具有系数A-D。通常，块大小是4×4、8×8、16×16、32×32等等， 但是块可以以任何希望的形状和大小来配置。

在本发明中，“树”被认为是用于辅助编码和解码的数据结构。它被 用从非叶子节点(非终端节点)连接的叶子节点(终端节点)来定义。每 个叶子节点代表来自该块的系数，而每个非叶子节点代表系数组，更具体 地代表所有其子孙(descendent)的集合。已知为根的非叶子节点包括给 定块的所有系数的集合。

图2B-2C例示出用于图2A中所示的经过变换的块的两种可能的树结 构。在图2B的树12中，单个非叶子节点16被示出，它也是树的根，四 个系数A-D 18a-18d从它直接成组。在图2C的树14中示出了非叶子节点 20，也是根20，从它关联了叶子节点A(24a)和另一个非叶子节点22， 非叶子节点22关联了三个叶子节点B、C和D(24b、24c、24d)。因 此，在图2B中，所有系数被一次性地成组在一起，而在图2C中，系数 B-D在最低层级(level)处被成组在一起。

3、利用树的SPRIGHT编码

以下示例考虑了使用本发明的非嵌入式版本进行的编码。优选地执行 树的广度优先遍历(BFT)，并且响应于节点类型和系数值来控制输出。 如果当前节点是叶子，则系数的值被输出。应理解，系数值优选地是非二 进制的，并且例如可以使用算术编码来编码。非叶子节点包含一个或多个 叶子节点，并且作为示例，在至少一个子孙叶子具有非零系数的情况下用 1来进行标记，或者在系数的相应集合都是零的情况下被标记为0，藉此 所有的子孙节点被跳过。“跳过”子孙节点意味着这些节点不被显式地 (explicitly)编码到编码后的输出比特流中，这样节约了用于这些零系数 的编码空间。将认识到，虽然值1和0被用于简单说明非叶子节点的值， 但是任何希望的值都可用于指示对于非叶子节点而言非零子孙是否存在。

图3A-3C和4A-4C图示出具有类似几何结构的2×2的块的编码。作 为示例而非限制，非叶子节点中的子孙被以二进制表示，其中“1”指示 至少一个分支具有非零系数，而“0”指示任一分支都不具有非零系数。

图3A图示了具有四个系数5、0、0、0的块30。图3B图示了为块30 选择第一编码32，其具有单个非叶子节点36和单个层级39中的四个叶子 节点38a-38d。图3B中的编码的输出生成五个值的序列1、5、0、0、0。 与此编码不同，图3C中示出的编码使用特别的两层级树结构。在图3C的 树34中，根节点40具有包含值为5(作为示例)的系数的单个叶子节点 44a，以及聚集了包括组46中的三个叶子节点44b、44b和44d的零节点的 非叶子节点42。因为这些叶子节点都是零，所以它们可以被跳过，因此相 应的根42被用0进行编码。响应于此编码，此编码序列输出是1、5、0； 这当然比图3B中使用的编码更短。作为示例示出了较小的2×2的块大 小，然而应理解，较大的块大小能够提供更高水平的编码效率增长。此 外，应理解，虽然为了说明起见将系数图示为单数位整数，但是实际的系 数需要大得多的表示比特空间。

然而，如果块中的系数之间的关系略有不同，例如在图4A的块中图 示出的那样，其中系数之一的位置被移动了，则相对于树结构的编码效率 将显著改变。图4A图示了具有四个系数0、0、5、0的块50。图4A图示 了响应于第一所选树结构52的编码，该树结构52具有单个非叶子节点56 和在单个层级60中的四个叶子节点58a-58d。此编码的输出生成五个值的 序列1、0、0、5、0。在图4C中，不同的树结构50被选择，其具有根 62，在第一层级70上具有叶子66a(0系数)和非叶子64，并且在第二层 级68上具有叶子66b(0)、66c(5)和66d(0)。响应于叶子66c中的 系数的非零值，系数组无法在不引入错误的情况下被跳过，并且非叶子64 被用1(指示其叶子必须被包括在编码中)编码。使用此树的编码生成六 个输出1、0、1、0、5、0，并且与图4B的相比效率较低。

从以上讨论显然可见：使用不适合块内的几何关系的树结构导致低效 率的块编码。本发明提供针对任何给定块的从多个候选中对树结构的恰当 选择以确保该块的高效编码。

4、利用树的SPRIGHT解码

在解码图像块时，解码器必须确定块曾是如何被确定的并且从多个候 选树结构中选择恰当的树结构。解码器优选地接收关于哪种树结构被用于 编码每个块的信息，例如接收在编码期间使用的树结构的索引。一旦恰当 的树被从多个候选树中选出，树就在解码期间被利用与编码处理相兼容的 技术进行遍历，例如利用树的广度优先遍历(BFT)。如果当前节点是树 的叶子，则符号被从比特流中解码，并且解码后的符号的值被指派给相应 的系数。相反，如果当前节点不是叶子，则一个比特被从比特流中读出并 且被操作；如果该比特是1，则处理继续，然而如果是0，则当前节点的 所有子孙节点的值被设定为0并且它们被从树中丢弃。

5、零聚集(Zero Clustering)

从前述讨论可见，本发明的编码增益主要响应于零聚集而得到，其中 从变换编码产生的零被聚集到组中，并且使得单个零存在于它们相应的非 叶子节点中。相反，如果零只能由非零来分裂，则得不到比特节省。

很容易认识到，变换编码通常产生许多零，并且这些零可能是彼此相 邻的。这些系数可以以许多不同的方式成为邻居，包括(1)空间位置， 从而它们可以是同一DWT子频带中的相邻系数；或者(2)频谱位置，从 而它们可以是相邻的DCT系数。

本发明通过基于块内系数的关系来针对每个块选择特定的树结构，来 利用此特性。

6、树设计

此部分说明可用于被编码的不同块的不同树结构。

图5图示出在选择用于编码块的树结构之前对像素块执行哈尔变换。 应理解，可使用提供类似结果的其他块变换(例如DCT)而不会背离本发 明的教导。在所示出的简单的2×2示例中，响应于块72的像素a-d，块 74的结果系数A-D被生成如下：

A＝(a+b+c+d)/2

B＝(a-b+c-d)/2

C＝(a+b-c-d)/2

D＝(a-b-c+d)/2

考虑块的以下模式(pattern)：

A.块是平坦的。

a≈b≈c≈d→B、C、D在量化后很可能是零。

B.块是水平边缘化(edged)的。

a≈b，c≈d→B、D在量化后很可能是零。

C.块是垂直边缘化的。

a≈c，b≈d→C、D在量化后很可能是零。

D.块是嘈杂(noisy)的。

在{A，B，C，D}中几乎没有零。

以上，可看到像素之间的某些几何关系，它们可被转化为变换系数之 间的2D关系。通过与以上相同的方法，应理解，在块内可认识到其他几 何关系，比如对角线1(例如+45°)、对角线2(例如-45°)等等，尤其 是考虑到使用超出在此作为示例使用的2×2的块大小的块大小时。

图6A-6D图示出可响应于块内发现的频谱模式而被选择的四种示例树 结构。应理解，树结构可针对不同的块大小和不同的变换而不同。可根据 需要在线或离线确定这些树结构。如果被离线创建，则它们被存储并且基 于块内的几何模式而被选择供使用，而如果被在线创建，则它们必须基于 已经重构的块的过去统计特性而被创建以避免将树结构作为附带信息 (side information)发送给解码器。对大多数应用而言，离线创建可能是 更为优选的方法，因为它在编码和解码时都需要更少的计算。

图6A图示了针对平坦的几何结构优化的树76。树76具有根节点 84，其下是叶子节点88a(A)和非叶子节点86。在非叶子节点86下面是 三个叶子节点88b(B)、88c(C)和88d(D)。因此，两个层级90、 100处于根层级84之下。

图6B图示了针对水平的几何结构优化的树78。树78具有根节点 102，其下是叶子节点106a(A)、106c(C)和非叶子节点104。存在于 非叶子节点104下面的是两个叶子节点106b(B)和106d(D)。因此， 两个层级108、110处于根层级102之下。

图6C图示了针对垂直的几何结构优化的树80。树80具有根节点 112，其下是叶子节点116a(A)、116b(B)和非叶子节点114。存在于 非叶子节点114下面的是两个叶子节点116c(C)和116d(D)。因此， 两个层级118、120处于根层级112之下。

图6D图示了针对嘈杂块优化的树82。树82具有单个非叶子(根)节 点122和在相同层级126处的四个叶子节点124a-124d(A-D)。

7、嵌入式编码中的SPRIGHT

此部分描述了在具有任意希望数目的位平面的嵌入式编码中使用本发 明的实施例。假设存在N个位平面，其索引是N-1，...，2，1，0(当从MSB 到LSB考虑时)。

在位平面上执行初始化，例如：

LIC＝φ；(不重要系数的列表)

LIS＝根；(不重要集合的列表)

LSC＝φ；(重要系数的列表)

k＝N-1；

当k≥0时，执行

阈值＝2^k；

处理LIC；

处理LIS；

处理LSC；

K＝k-1；

位平面的编码可以在任何希望时刻被停止，例如响应于比特预算的耗 尽。可以理解，根据本发明的SPRIGHT装置和方法能够在嵌入式或非嵌 入式模式中工作，比如以与其他编码方法(包括嵌入式零树小波(EZW) 和多级树中的集合分裂(SPIHT))的方式类似的方式。

根据本发明实施例的SPRIGHT的输出编码优选地是作为二进制流， 可利用算术编码对其进行进一步编码，或者简单地将其如其原样地发送。 将编码“如其原样地”发送使得在仅牺牲少量编码效率的同时显著降低了 复杂度。此外，在编码器和解码器之间的其他形式的信令可被执行，比如 转换类型和/或树索引。可利用诸如已经描述了的算术编码之类的压缩编码 的形式来减小由这些附加信号所代表的开销。

处理不重要系数的列表(LIC)。

对于LIC中的每个系数x，执行：

如果|x|＜阈值，则输出0

否则，输出1；以及

在x＞0的情况下输出1，或者在x＜0的情况下输出0；

从LIC中删除x，将其添加到LSC。

处理不重要集合的列表(LIS)。

对于LIS中的每个集合s，执行：

如果对于s中的所有x都成立|x|＜阈值，则输出0；

否则，输出1；以及

从LIS中删除s。

处理s的后代(offspring)。

对于s的每个后代o，执行：

如果o是叶子，则执行与处理LIC相同的操作；

如果o不是叶子，将其添加到LIS。

处理LSC。

对于LSC中的每个系数，执行：

如果在当前的位平面处它仅被添加到LSC，则跳过它；

否则，输出mod(|x|＞＞k，2)。

8、总结的SPRIGHT装置和方法

熵编码的传统方法使用单个算法来进行编码，因此并不基于被编码的 块的几何结构来选择编码的形式。将理解，传统方法通过依赖于固定的编 码方法来执行编码，比如将单个固定的树用于EZW和SPIHT中，以编码 当前块。

图7图示出耦合到解码器的编码器的简化框图130。原始图像数据 132在编码器装置134处被接收，该编码器装置134接收关于从多个候选 树中对树类型进行选择的判决136。虽然被图示为独立信号，但是将理 解，此选择信号功能136优选地作为编码器的一部分被执行。编码器的比 特流输出138在解码器140处被接收，该解码器同样接收树类型选择信号 136，并输出解码后的数据142。在本发明中，普通的编码器装置和普通的 解码器装置被用于响应于被编码的块的几何结构来执行多个基于树的编码 操作。如所示出的，编码器和解码器基于块的几何结构来选择在对块进行 编码时要使用的树结构。将理解，响应于选择了哪种树，SPRIGHT可以为 给定块提供与EZW/SPIHT或其他已知编码技术相同的输出。

应理解，本发明的实施例还允许使用非传统的树来提高编码效率。例 如，树结构可被配置为适合图像数据的局部统计特性。因为树结构是响应 于块的特性而被选出的，所以对于给定块而言很有针对性的树结构可被选 出，然而该树结构如果在许多块上被使用则可能提供十分低效率的编码。

图8图示出实施例150，该实施例150示出编码器136和解码器142 的更多细节。编码器136被示出为包括计算机处理器(CPU)152和存储 器154。应理解，这些处理元件可被单一地实现或者被实现为多处理器， 和/或通过任何希望的加速水平的硬件来实现，而不会背离本发明的教导。 可在处理器152上执行的程序执行对图像源158的编码156，包括执行预 测160、执行变换162、量化164、树选择166和编码168，以输出编码后 的图像数据(或信号)170。更具体地，响应于块中的系数之间的二维关 系来执行树选择，此后利用所选的树来编码块。与其中在执行编码所使用 的编码算法内树结构是固有的(固定的)实现方式相比，利用所选的树结 构能够提供大幅提高的编码效率。

解码器142被示出为通过处理器元件172和存储器174来类似地实 现，并且它还可以包括任何希望的处理元件并且与数字加速硬件组合而不 会背离本发明的教导。响应于程序的执行，解码处理176被执行，其中信 号170被接收并被解码块178解码，该解码块178在进行解码之前进行树 结构选择180。解码块178的输出然后被逆变换182并且图像被按块重构 184以产生最终的解码后的图像输出186。

树选择链接188被示出在编码期间的树选择和解码期间所使用的树选 择之间以代表其中关于所选树结构的信息被传送给解码器142来确保它以 数据被编码的方式解码数据的实施例。通常，关于所选树结构的信息将被 并入到要发送给解码器的编码信号流的预定比特中。还应理解，针对给定 块的树结构的传送可作为从编码器到解码器的比特被传送，或者可替代 地，来自编码器的数据可以以将树选择通知给解码器的方式被组织，或者 解码器可以以别的方式确定与编码相兼容的解码所要使用的树结构。

在所描述的示例实施例中，解码器总是知道编码给定块所使用的树结 构。例如，树结构被预编程到解码器的可执行程序中，或者在会话开始时 由编码器来通知。作为示例而非限制，图8图示了多个候选树结构的集合 189(例如，可被选择的垂直(V)、水平(H)、对角线1^st或2^nd(D)和 平坦(F))。当进行BFT时，解码器首先区分当前节点是否是叶子，然 后当它是非叶子时从比特流中读取BIT，或者针对叶子从流中读取符号。 取决于它是如何被编码的(例如使用指数哥伦布(exp-golomb)编码)， 符号可以包括一个或多个比特。

图9图示出根据本发明的编码方法的实施例。传入图像被划分为块 190，被利用所选变换去相关192，并且被利用变换系数量化194。在步骤 196，块内的2D关系被确定。在步骤198，响应于所确定的2D关系，树 结构被选择，所确定的2D关系可以被单独使用，或者可选地与关于其他 块或图像本身的附加信息(比如图像特性)组合使用，来选择如步骤200 所示的对块进行编码所使用的最优的树。应注意，对去相关变换的选择和 从多个候选中对树结构的选择可以是互相关的。

应理解，基于所选树结构的块编码优选地遵循树内的模式，该模式与 解码器相兼容，比如利用预定的树遍历模式(未示出)。例如，在本发明 的至少一个实施例中，树结构的广度优先遍历(BFT)被执行，其中系数 在向下前进到下一较低层级之前在给定方向上填充树的每一层级。用于传 送要由解码器使用的关于所选树结构的信息(例如索引)的可选步骤204 被示出。

图10图示出根据本发明的解码方法的实施例。在对块进行解码之 前，解码器确定当前块是如何被编码的210，该确定优选地基于关于哪种 树结构被用于对当前块进行编码的、诸如索引之类的来自编码器的接收信 息。遵循与编码相兼容的模式来执行解码。在本示例实施例中，到所有现 存非零分支的树的广度优先遍历(BFT)被执行212；使得叶子被解码为 系数214，并使“零”(空)非叶子被解码为零系数216。一旦所有系数 被恰当地恢复，解码器就前进到反量化218、逆变换220和重构222。

这里称作SPRIGHT的本装置和方法提供针对图像/视频数据的基于熵 的编码和解码。在编码处理期间，优选地基于块的几何结构(或者等同地 块中系数之间的2D关系)，树结构被从多个候选中选出，并且响应于所 选的树，块被编码。在编码处理中，零系数(即，在量化期间变为零的零 系数)的集群可从编码后的输出中被除去(eliminate)。在解码处理中， 由编码器使用的树结构被确定，并且解码器基于所选树结构来将编码后的 数据转换回块系数，同时替换(恢复)零系数。响应于对树结构的恰当选 择，系统的整体编码效率能够被提高。本发明的教导可被应用于各种图像/ 视频编码和解码系统，并且可被应用于嵌入式或非嵌入式模式二者中。在 嵌入式模式中，本发明提供可在任何地方被停止的完全嵌入的比特流，并 且其可被利用而无需诸如哈夫曼(huffman)编码或算术编码之类的复杂熵 编码方法。

本发明提供了用于在图像/视频处理设备中执行熵编码和解码的方法和 装置。发明性教导可被应用于各种装置和应用，包括嵌入式和非嵌入式图 像/视频编码二者等等。

可见，因此，本发明例如包括以下发明性实施例：

1.一种用于图像或视频编码器内的自适应熵编码的装置，包括：被配 置用于图像/视频编码的计算机；耦合到所述计算机的存储器；以及可在所 述计算机上执行的程序，用于执行以下步骤：将图像或视频帧划分为块， 利用变换对每个块进行去相关，量化变换系数，响应于对图像的像素块内 的几何关系的确定，从多个候选中选择希望的树结构，以及响应于所选择 的树结构，利用零系数的聚集来对块进行编码；其中，响应于使得所述所 选择的树结构中的非叶子节点表示相应的叶子节点仅包含零系数并且不将 这些子孙叶子节点编码到由所述装置生成的编码后输出的比特流中，零系 数的部分被从编码后的输出中去除。

2.根据权利要求1所述的装置，其中，所述对块进行编码是响应于根 据树结构的预定遍历的所选择树结构而被执行的。

3.根据权利要求1所述的装置：其中，所述树结构具有指定布置中的 叶子和非叶子节点；并且其中，包含系数的一个或多个叶子节点被与每个 非叶子节点相关联。

4.根据权利要求1所述的装置，其中，通过指示出每个非叶子节点的 子孙叶子节点是全都包含零系数还是不全都包含零系数的比特，来表示每 个非叶子节点的状态。

5.根据权利要求1所述的装置，其中，树结构的集合被保留在编码器 中，并且被配置用于允许树结构中的一种树结构响应于所述对树结构的选 择而被选出。

6.根据权利要求1所述的装置，其中，能够被识别的块内的所述几何 关系是从包括平坦、嘈杂、水平、垂直、+45°对角线、-45°对角线的几何 块关系的组中被选出的。

7.根据权利要求1所述的装置，还包括可在所述计算机上执行的用于 将关于当对图像的块进行去相关时使用了哪种变换的信息提供给解码器的 程序。

8.根据权利要求1所述的装置，还包括可在所述计算机上执行的用于 将关于在对图像的每个块进行编码时选择了哪种树结构的信息提供给解码 器的程序。

9.根据权利要求1所述的装置，还包括可在所述计算机上执行的用于 执行以下步骤的程序：将关于选择了哪种树结构以供用于编码图像的每个 块的信息提供给解码器，其中，所述信息包括传送所述所选择的树结构的 至少一个索引给被配置用于接收编码后图像的解码器。

10.根据权利要求1所述的装置，其中，所述几何关系包括被编码的 当前块中系数之间的二维关系。

11.根据权利要求1所述的装置，还包括可在所述计算机上执行的用 于在变换之前的块间预测或对块的预滤波的程序。

12.根据权利要求1所述的装置，其中所述块能够具有任何希望的形 状和大小，包括从含有4×4、8×8、16×16和32×32的系数块的块大小 的组中选出的块大小。

13.根据权利要求1所述的装置，还包括可在所述计算机上执行的用 于在被配置用于非嵌入式编码的图像编码器内执行自适应熵编码的程序。

14.根据权利要求1所述的装置，还包括可在所述计算机上执行的用 于在被配置用于嵌入式编码的图像编码器内执行自适应熵编码的程序，在 嵌入式编码中，在任意希望数目的位平面间执行编码并且能够以任意希望 的编码速率来停止编码。

15.根据权利要求1所述的装置，其中，响应于针对编码后的图像流 在比特预算内进行拟合，所述编码被执行到希望的编码速率。

16.根据权利要求1所述的装置，其中，所述变换包括频谱变换。

17.根据权利要求1所述的装置，其中，所述变换包括离散小波变换 (DWT)或离散余弦变换(DCT)，或者任何重叠的变换。

18.一种用于对图像进行自适应熵编码和解码的系统，包括：被配置 用于图像编码的具有处理元件和存储器的编码器；在所述编码器的处理元 件上可执行的用于执行以下步骤的程序：将图像或视频帧划分为块，利用 变换对每个块进行去相关，量化变换系数，响应于对图像的块内的几何关 系的确定，从多个候选的集合中选择树结构，以及响应于所选择的树结 构，利用零系数的聚集来对块进行编码；其中，响应于使得所述所选择的 树结构中的非叶子节点表示相应的叶子节点仅包含零系数并且不将这些子 孙叶子节点编码到去向解码器的输出比特流中，零系数的部分被从编码后 的输出中去除；被配置用于对来自所述编码器的图像流进行图像解码的具 有处理元件和存储器的解码器；在所述解码器的处理元件上可执行的用于 响应于执行以下步骤来输出图像信号的程序：确定在对块进行编码时由所 述编码器选择的树结构，将树结构的叶子解码为输出中的系数，响应于对 没有非零分支的非叶子节点进行解码，在输出中输出零系数，对输出执行 反量化，对输出执行逆变换，响应于对输出的接收来重构图像信号。

19.根据权利要求18所述的系统，其中所述对块进行编码是响应于根 据树结构的预定遍历的所选择树结构而被执行的。

20.一种用于图像编码器内的自适应熵编码的方法，包括以下步骤： 将图像或视频帧划分为块，利用频谱变换对每个块进行去相关，量化变换 系数，响应于对图像的块内的二维几何关系的确定，从多个候选中选择树 结构，以及响应于所选择的树结构，在聚集零系数的同时对块进行编码； 其中，响应于使得所述所选择的树结构中的非叶子节点表示其相应的叶子 节点仅包含零系数，零系数的部分被从编码后的输出中去除。

尽管以上描述包含许多细节，但是这些细节不应被解释为限制本发明 的范围而应被解释为仅仅提供对本发明的一些目前优选的实施例的说明。 因此，将理解，本发明的范围完全包括对于本领域技术人员而言可能变得 显而易见的其他实施例，以及本发明的范围因此将仅由随附的权利要求书 而非任何其他事物来限定，在权利要求书中，提到单数的元件并非意欲表 示“一个且仅一个”(除非明确地如此陈述)而是表示“一个或多个”。 本领域普通技术人员已知的、上述优选实施例中的要素的结构和功能等同 物通过引用被清楚地结合于此并且意欲被本权利要求书所包括。此外，设 备或方法并非必须解决本发明所要努力解决的每个以及所有问题，因为它 要被本权利要求书所包括。此外，本公开中的任何要素、组件或方法步骤 都不意欲贡献给公众，无论要素、组件或方法步骤是否被清楚地记载于权 利要求书中。这里的任何的权利要求要素都不在35U.S.C.112第六款的规 定下进行解释，除非要素被使用短语“用于...的装置(means for)”清楚 地记载。