用于视频和图像压缩的并行金字塔熵编码

摘要

本发明涉及用于视频和图像压缩的并行金字塔熵编码，提供了将诸如图像或视频数据的量化系数的块的代码块划分为更小的块和子块的方法、系统以及计算机程序产品，该更小的块和子块能够使用分层的熵编码和解码方案来并行地处理。本划分在仍然使用同一分层的熵编码方案来编码整个代码块的同时实现。

说明书

技术领域

本公开总体上涉及视频处理，并且更具体地，涉及视频编码技术。

背景技术

视频编码中的许多处理都涉及串行比特流的处理。为了编码或解码比 特流，这些自身绑定至串行操作的处理需要更强力的处理器来有效地完成 此目的。

尤其是，当处理串行数据时，时钟速度成为了限制因素。如果在能够 解析（分辨，resolve）下一条数据之前需要先处理各条数据，那么可以通 过增加处理时钟速度来（通常线性地）增加系统速度。然而，高时钟速度 需要额外的功耗和散热。

因此，希望提供一种可并行化编码技术。

发明内容

本发明提供了一种方法，包括：将代码块划分为像素组；将像素组划 分为子块；以及使用用于代码块的分层编码方案来将分配给子块的像素编 码。

优选地，将代码块划分为像素组包括：将代码块划分为四个等尺寸的 像素组。

优选地，将像素组划分为子块包括：确定一组群集样式；以及选择用 于配置像素组之一的相应子块的群集样式。

优选地，选择群集样式包括：确定用于每个子块的最小和最大代码尺 寸；以及确定用于相应像素组的子块的最小尺寸配置。

优选地，该方法还包括：使用分层熵编码方案来将用于子块和像素组 的代码尺寸存储在所编码的流中。

优选地，该方法还包括：接收包括代码块的数据流；使用代码尺寸和 分层的解码方案来将代码块分开为像素组；使用代码尺寸来将像素组分开 为子块；以及并行地解码子块。

本发明还提供了一种计算机可读存储装置，其上存储有指令，指令通 过计算装置来执行，指令的执行使计算装置执行以下操作，包括：将代码 块划分为像素组；将像素组划分为子块；以及使用用于代码块的分层编码 方案来将分配给子块的像素编码。

优选地，将代码块划分为像素组包括：将代码块划分为四个等尺寸的 像素组。

优选地，将像素组划分为子块包括：确定一组群集样式；以及选择用 于配置像素组之一的相应子块的群集样式。

优选地，选择群集样式包括：确定用于每个子块的最小和最大代码尺 寸；以及确定用于相应像素组的子块的最小尺寸配置。

优选地，操作还包括：使用分层的熵编码方案来将用于子块和像素组 的代码尺寸存储在编码的流中。

优选地，操作还包括：接收包括代码块的数据流；使用代码尺寸和分 层的解码方案将代码块分开为像素组；使用代码尺寸来将像素组分开为子 块；以及并行地解码子块。

本发明还提供了一种系统，包括：编码器，存储在存储器中并且被配 置为执行以下操作，包括：将代码块划分为像素组，将像素组划分为子块， 以及使用用于代码块的分层编码方案来将分配给子块的像素编码；以及一 个以上的处理器，被配置为处理编码器。

优选地，将代码块划分为像素组包括：将代码块划分为四个等尺寸的 像素组。

优选地，将像素组划分为子块包括：确定一组群集样式；以及选择用 于配置像素组之一的相应子块的群集样式。

优选地，选择群集样式包括：确定用于每个子块的最小和最大代码尺 寸；以及确定用于相应像素组的子块的最小尺寸配置。

优选地，编码器还被配置为进行以下操作，包括：使用分层的熵编码 方案将用于子块和像素组的代码尺寸存储在所编码的流中。

优选地，该方法还包括：解码器，被配置为执行以下操作，包括：接 收包括代码块的数据流，使用代码尺寸和分层的解码方案将代码块分开为 像素组，使用代码尺寸来将像素组分开为子块，以及并行地解码子块。

附图说明

结合在本文中并形成说明书的一部分的附图示出了本公开的实施方 式，并且还与描述一起用于解释本公开的原理以及用于使本领域内的技术 人员能够实现和使用所公开的实施方式。

图1示出了示例性熵编码标准。

图2是示出了根据本公开的实施方式的去除代码块相互依赖性的步 骤的处理的流程图。

图3是示出了根据本公开的实施方式的可以将代码块划分为像素组 （子块）的步骤的编码处理的流程图。

图4示出了根据本公开的实施方式的将代码块划分为块和子块的方 式。

图5是示出了根据本公开的实施方式的解码步骤的处理的流程图。

图6示出了可以实现本公开的实施方式的示例性计算机系统。

本公开的实施方式将通过参考附图来详细描述。在附图中，相似的参 考标号通常表示相同或功能相近的元件。此外，参考标号的最左边的数字 通常表示该参考标号第一次出现的附图。

具体实施方式

I.介绍

以下详细描述参考了示出示例性实施方式的附图。其他的实施方式也 是可能的，并且可以在本公开的实质和范围内对实施方式进行修改。因此， 详细描述不旨在限制本发明。相反地，本发明的范围由所附权利要求来限 定。

对本领域内的技术人员显而易见的是，本公开可以以诸如软件、硬件、 固件和/或附图中所示的实体的不同的实施方式来实施。任何具有对实现本 公开的硬件的具体控制的实际软件代码都不限于本公开。因此，将在理解 实施方式的修改和变形都为可能的条件下，并且在本公开的实质和范围内 来描述本公开的操作行为。

在说明书和权利要求书中的对模块的提及意味着用于执行所指示的 功能的硬件、固件或软件成分的任意组合。模块不需要是严格定义的实体， 这使得几个模块可以将硬件和软件成分在功能上重叠。例如，软件模块可 以指在程序内的一行代码，该程序本身是单独的软件程序。本领域内的技 术人员将理解的是可以根据例如多种格式或性能优化技术来定义模块的 功能。

根据公开的实施方式，提供了用于将代码块划分为像素组，用于将像 素组划分为子块，以及使用用于代码块的编码方案来将分配给子块的像素 编码的方法、计算机可读存储装置和系统。

本公开此外的特征和优点，还有本公开的各种实施方式的结构和操 作，都在以下通过参考附图来详细描述。应注意，本公开不限于本文中描 述的具体实施方式。这些实施方式在本文中的提出仅用于说明性的目的。 基于本文中所包含的教导，另外的实施方式对本领域内的技术人员也是显 而易见的。

图1示出了示例性熵编码标准100（现有技术）。诸如霍夫曼编码的 熵编码是依赖于相应的可变长度的无前缀码字（或简单的“代码”）来表 示每个固定长度输入的无损数据压缩技术。例如，如编码标准100中所示， 在数据流中提供了一组像素104a、104b、104n（统称为像素104）。每个 像素都可以由例如包括该像素的颜色强度信息的数据的24比特来表示（例 如，8比特的数据用于红色，8比特的数据用于绿色，8比特的数据用于蓝 色）。然而，虽然数据的24比特可以表示1678万个不同的值，但是像素 块（例如，在图像内的16×16像素区域）只会每像素至多具有一个不同的 值（例如，256个可能的值）。此外，尤其是在应用了有损压缩算法之后（例 如，通过减少像素数据可以解析的唯一值的数量），一些重复很可能意味 着一些像素可以具有相同的量化系数值。

例如，假设在16×16的像素块中的全部像素都具有从只有三种可能 的颜色的调色板中选择的颜色。在这种情况下，熵编码可以仅使用最多二 比特的数据（例如，‘00=红色’，‘01=蓝色’，‘1=黄色’）来表示四种可能 的值。在编码阶段期间，这些编码使用已知的编码技术来确定（诸如霍夫 曼编码）。应注意，在熵编码中，如本领域的技术人员应当理解的，编码 长度是可变的。在以上示例中，在编码序列的起始处检测到‘1’之后， 颜色就会被确定为黄色——数据的下一比特将是新代码的开始。在编码序 列的起始处的代码‘0’仅将概率减小至‘红色’或‘蓝色’，这取决于数 据的下一比特。

为了导航的简单，该行为通常包括在诸如树的数据结构中。例如，诸 如“1001010111011”的代码序列应当被翻译为‘黄色’（1）、‘红色’（00）、 ‘黄色’（1）、‘蓝色’（01）、‘蓝色’（01）、‘黄色’（1）、‘黄色’（1）、 ‘蓝色’（01）、‘黄色’（1）。编码本身（例如，诸如树的数据结构）可以 与所编码的数据一起被设置为前缀代码列表102。然后，各个像素104仅 包括唯一地表示其前缀代码所需的数量的数据比特。

该方法的严重缺陷是全部编码序列都必须被串行（顺序）地解码。因 为像素间的分割是提前未知的，所以不可能例如用第一处理线程对首先的 X个像素解码，以及用第二处理线程对其次的Y个像素解码。例如，跳至 以上示例代码序列的中间（例如，‘111011’）并且照常对其解码会将‘黄 色’（1）生成为第一个值。然而，这第一个‘1’实际上是用于‘蓝色’（01） 的编码的一部分，但是在没有串行处理全部的序列的条件下这是不可能确 定的。

II.并行化技术

如上所述，现有的解码技术必须串行处理。为了了解对随后的像素解 码所需要的信息，必须解码先前的像素。因此，为了实现并行，需要一种 技术来去除该相互依赖性。

图2是示出了根据本公开的实施方式的去除代码块相互依赖性的步 骤的处理200的流程图。虽然本领域内的技术人员应当理解本文中描述的 技术可以以任何等级（例如，以在独立图像中的相互依赖的代码块、以在 独立流中的相互依赖的图像等）来应用，但是例如，但不限于，在图像或 图像序列中代码块（例如，16×16的像素块）与其他代码块独立。

本方法开始于步骤202并且进行至将代码块（例如，图像被划分为 16×16的代码块）划分为像素组的步骤204。例如，完整的图像可以被划 分为独立的16×16的代码块，该16×16的代码块继而被划分为8×8的像素 组，并且8×8的像素组可以被划分为四个4×4的像素组。在步骤206中， 做出是否对新的像素组进行进一步的划分的决定。如果是，那么本方法进 行至步骤204从而进一步地划分像素组（例如，每个4×4的像素组可以更 进一步地划分为四个2×2的像素组；四个4×1的像素组；一个2×1、一个 2×3和两个1×4的像素组的组合；等）。本领域内的技术人员应当理解的 是步骤204中进行的划分可以视情况由相同的模块或几个不同的模块处 理。

如果没有请求进一步的划分，那么本方法进行至在各层提供本地前缀 代码的步骤208。本方法随后结束于步骤210。根据本发明的实施方式， 每次划分根据层号来命名。全部图像的第一级划分的代码块包括“层0”。 第一组像素组（例如，划分16×16的代码块的8×8像素组）包括“层1” 等。在以上示例中，采用了层0至3。

III.划分代码块

根据本公开的实施方式，每个代码块都包括用于表示块内的像素值的 一组量化系数。本领域内的技术人员将理解的是代码块可以包含额外的或 不同的数据，并且量化系数的使用以示例而非限制的方式来提供。具体地， 尽管系数通常被量化，但是它们可以是非量化的。因此，公开的实施方式 还预期以一组非量化的系数来工作。

根据本公开的实施方式，代码块根据“群集样式（cluster pattern）” 来划分，该群集样式（图案）诸如如上所述4×4的像素组可以被划分为四 个2×2的像素组，四个4×1的像素组，一个2×1、一个2×3以及两个1×4 的像素组的组合，或诸如三角形、对角线或L形样式的其他样式。不管使 用什么样式，编码器都会通过例如将群集样式信息嵌入在块或子块的前缀 中来告知解码器选择了哪个样式，否则该样式应当提前由解码器得知。

图3是示出了根据本公开的实施方式的可以将代码块划分为像素组 （子块）的步骤的编码处理300的流程图。本领域内的技术人员应当理解 的是可以应用各种技术以不同等级来分割块，并且本文中描述的技术以示 例而非限制的方式来提供。例如，4×4代码块可以被划分为四个2×2代码 块——实现方式始终可以选择进行这种特定的划分，或可以采用以下进一 步详细描述的群集样式。

为了本文中概述的示例的目的，代码块包括最终被划分为4×4块（例 如，16×16的代码块被划分为8×8的像素组，每个8×8的像素组被划分为 4×4的像素组）的几个像素组。如以下描述的，每个4×4块都被划分为进 一步的子块。

本方法开始于步骤302并且进行至确定要分析的可能的群集样式的 步骤304。例如，如果在四个2×2子块或四个4×1子块之间选择，那么具 有两个待分析的群集样式。本领域内的技术人员将理解的是多个群集样式 是可用的，并且所分析的样式可以包括这些样式的任何子集。此外，可以 使用特定的样式而不进行任何分析。

在步骤306中，对于给定群集样式确定用于子块的最小和最大尺寸。 例如，通过四个2×2子块的群集样式，用于编码每一个子块的最大代码尺 寸被确定。然后，通过四个2×2子块的组集，最小代码尺寸（即，对于具 有最小代码尺寸的单独子块的代码尺寸）与最大代码尺寸（即，对于具有 最大代码尺寸的单独子块的代码尺寸）一起被确定。

根据本公开的实施方式，对用于各个子块的代码尺寸的确定通过找到 两者的每个量化系数的补码尺寸（complement size）来完成，尽管本领域 内的技术人员将理解本技术可以被不同地应用于其他数据，或可以使用不 同的技术来找到全部的量化系数的代码尺寸。可以基于通过应用特定代码 表示量化系数所需的字节来确定子块的最大和最小尺寸。根据本发明的实 施方式，由编码技术领域中的技术人员来选择代码从而编码独立的量化系 数。如上所述，该信息用于确定相应的群集样式的最小和最大尺寸（即， 该组子块的最小和最大代码尺寸）。

在步骤308中，将各种群集样式的尺寸与其他群集样式相比较。根据 本公开的实施方式，通过将用于编码全部量化系数的全部代码尺寸和用于 编码群集样式的前缀代码尺寸相加，基于最小化用于块（例如，4×4块） 的比特总数来选择来自一组可用群集样式的群集样式。例如，可以做出使 用四个2×2子块将比使用四个4×1子块需要更少的比特来表示整个块的决 定。

在步骤310中，如以下描述地存储关于所选配置的前缀代码信息，并 且本方法结束于步骤312。作为非限制性的示例，需要1至4比特来编码 在左上4×4块的系数的最大尺寸与在该4×4块中的每个子块的系数的最大 尺寸之间的差异，同时可以需要1或3比特来编码对于其余的4×4块的上 述差异。本算法可以将2比特用于左上的4×4块从而规定被用于对用于编 码上述差异（即在左上4×4块的系数的最大尺寸与该4×4块中样式的每个 子块的系数的最大尺寸之间的差异）的比特数量进行编码的比特数量，以 及将1比特用于其余的4×4块从而规定被用于对用于编码上述差异的比特 数量进行编码的比特数量，即，将用于对其余的4×4块的上述差异进行编 码的1或3比特。

根据本公开的实施方式，群集（诸如4×4块）的尺寸（会被用于编 码的比特的数量）被编码为在较上层（诸如包含该4×4块的8×8块）中的 前缀的一部分，使得当解码器解码该比特流时，能够与提取用于编码其他 群集的全部比特并行地提取用于编码该群集的全部比特。将同样的想法应 用于以上示例中的低于该群集等级（例如，对于2×2子块（层3）的4×4 块层（层2））的层（诸如组成群集4×4块的四个2×2子块）中，其中用 于编码每个子块的比特数量被编码为4×4块中的前缀的一部分。

转至图4，作为与本公开的实施方式一致的非限制性示例，8×8代码 块402被示出为划分为四个4×4块。根据本公开的实施方式，四个块404a、 404b、404c和404d都各自根据群集或分割样式被进一步地划分为子块。

在块404a的情况中，子块405被示出为2×2块。根据本公开的实施 方式，块404a的所有子块405的尺寸都一致。在如以上所述确定子块405 的最大尺寸之后，将其与块404a的其他子块的最大尺寸相比较从而确定 子块的最大（和最小）尺寸。与以上示例一致，在块404a的最大尺寸和 各个子块的最大尺寸之间的差可以需要1至4比特来用于编码。因此，2 比特专门用于规定需要多少比特（从1到4）来编码以上的差异。

将最大尺寸编码为图3中描述的尺寸的处理在块级进行，其中每个 4×4块即404a、404b、404c和404d的最大样式尺寸也都被编码。

图4在示图的左手侧示出了根据本公开的实施方式的术语为并行金 字塔熵编码（“PPEC”）的算法。该名称来源于被展开的本示图看上去会 像金字塔形的概念，其中以编码的像素数据410为基础，子块数据408为 中间层并且块数据406为顶层。在每一层中，所有的块或子块都可以被并 行地编码和解码。

如图4中所示，各个子块都包括编码的像素数据。如上所述，各个块 包括的数据具有用于限定比特（其用于编码在块的最大尺寸与该块内的各 个子块的最大尺寸之间的差异）数量的比特，以及编码子块数据的比特。 全部的代码块数据包括每个块的最大尺寸，还有用于编码像素数据的前缀 代码（例如，霍夫曼编码方案）。本领域内的技术人员应当理解虽然本示 图示出了上述各种成分，但是这些成分不需要以图4中所示的特定顺序出 现。此外，如早先论述的，可以引入额外的层来提供子块和子子块的更细 致的划分。此外，可以采用其中特定的块被划分为子块，但是其他的块被 串行编码而不进行进一步划分的混合方法。本领域内的技术人员应当理解 的是这些改变及其他都在本公开的实质和范围内。

V.解码器侧操作

以前述方式来构造代码块将极大地有利于解码器的尺寸。根据本公开 的实施方式，对与以上描述一致的方式来构造的代码块进行操作的解码器 可以并行地处理代码块，并且甚至可以并行地处理独立的子块。

在先前的串行操作中，需要按顺序将代码块内的各个符号解码。然而， 通过如本文中描述将代码块分解为层，可以并行地解码多个符号（例如， 像素组、字符组或可解码数据的其他组），这为以可相比的时钟速度运行 的串行处理解决方案提供了量级上的改进。可选地，可以使用较低的时钟 速度获得相同的处理速度，这导致了高能量效率。

为了将如上所述的由编码器包括的信息从整体的代码块解析为分离 的块和子块而构造解码器。这意味着例如解码器应当能够了解在代码块中 存在多少划分的层，采用了什么群集样式等。全部该数据都在报头块中的 某处规定或遍及代码块而展开。

图5是示出了根据本公开的实施方式的解码步骤的处理500的流程 图。本方法开始于步骤502并且进行至将块代码数据划分为独立块成分（例 如，图4的块404a、404b、404c和404d）的步骤504。在步骤506中， 根据本公开的实施方式，各个块进一步分为子块（例如，图4的子块405）。 应注意，因为以上的层（例如，用于层2解码的层1）限定了被解码层的 代码尺寸，所以在步骤506中对各个块的处理可以并行地进行。此外，因 为限定并且已经解码了各个子块的尺寸，所以在步骤508中并行地实行对 各个子块的解码。该方法结束于步骤510。

VI.示例性计算机系统实现方式

本公开的各方面可以由软件、固件、硬件或它们的组合来实现。图6 示出了本公开或其部分可以实现为计算机可读代码的计算机系统600的示 例。例如，处理200（图2）、处理300（图3）和处理500（图5）可以在 系统600中实现。本公开的各种实施方式都依照该示例性计算机系统600 来描述。在读完本描述后，怎么使用其他的计算机系统和/或计算机架构来 实现本公开对本领域内的技术人员而言应当是显而易见的。

计算机系统600包括诸如处理器604的一个以上的处理器。处理器 604可以是专用目的或一般目的的处理器。处理器604连接至通信基础设 施606（例如，总线或网络）。

计算机系统还包括主存储器608，优选为随机存取存储器（RAM）并 且还可以包括第二存储器610。第二存储器610可以包括例如硬盘驱动器 612、可移除存储驱动器614和/或存储棒。可移除存储驱动器614可以包 括软盘驱动器、磁带驱动器、光盘驱动器、闪速存储器等。可移除存储驱 动614以众所周知的方式从可移除存储单元615中读取和/或写入至可移除 存储单元615。可移除存储单元615可以包括由可移除存储驱动614读取 并且写入的软盘、磁带、光盘等。如本领域内的技术人员应当了解的，可 移除存储单元615包括计算机可用存储介质，该计算机可用存储介质具有 存储在其中的软件和/或数据。

在可选的实现方式中，第二存储器610可以包括其他类似地装置以用 于允许将计算机程序或其他指令装载在计算机系统600中。这样的装置可 以包括，例如可移除存储单元622和接口620。这样的装置的示例可以包 括程序盒以及盒式接口（诸如在视频游戏装置中出现的）、可移除存储器 芯片（诸如EPROM或PROM）和关联的针槽（socket）、以及其他的诸如 可移除存储单元622的可移除存储单元以及允许软件和数据从可移除存储 单元622中传输至计算机系统600的诸如接口620的接口。

计算机系统600还可以包括通信接口624。通信接口624允许软件和 数据在计算机系统600和外部装置之间传输。通信接口624可以包括调制 解调器、网络接口（诸如以太网卡）、通信端口、PCMCIA卡槽（slot）和 卡等。经由通信接口624传输的软件和数据可以是电子的、电磁的、光学 的信号或者能够由通信接口624接收的其他信号的形式。这些信号经由通 信路径626而提供给通信接口624。通信路径626运载信号并且可以使用 线路或线缆、光纤、电话线、蜂窝电话链路、RF链路或其他通信信道来 实现。

在本文中，术语“计算机程序介质”和“计算机可读介质”用于一般 地指诸如可移除存储单元615、可移除存储单元622和安装在硬盘驱动器 612中的硬盘的介质。在通信路径626上运载的信号也可以体现本文中描 述的逻辑。计算机程序介质和计算机可用介质还可以指诸如主存储器608 和第二存储器610的存储器，该存储器可以是存储半导体（例如，DRAM 等）。这些计算机程序产品是用于将软件系统提供给系统600的装置。

计算机程序（也称为计算机控制逻辑）存储在主存储器608和/或第 二存储器610中。计算机程序还可以经由通信接口624来接收。当执行计 算机程序时，该计算机程序使计算机系统600能够按照本文中所描述的来 实现本公开。尤其是，当执行计算机程序时，该计算机程序使处理器604 能够实现本公开的处理，该处理诸如上述的处理200（图2）、处理300（图 3）和处理500（图5）中的步骤。因此，该计算机程序表示计算机系统600 的控制器。其中，本公开使用软件来实现，可以使用可移除存储驱动器614、 接口620、硬盘驱动器612或通信接口624来将该软件存储在计算机程序 产品中以及装载在计算机系统600中。

本公开还涉及包括存储在计算机可用介质上的软件的计算机程序产 品。这样的软件当在一个以上的数据处理装置中执行时使数据处理装置如 本文所述的那样进行操作。本公开的实施方式采用任何现在或将来所知晓 的计算可用或可读介质。计算机可用介质的示例包括但不限于主存储装置 （例如任何类型的随机存取存储器）、第二存储装置（例如硬盘驱动器、 软盘、CD-ROM、ZIP盘、磁带、磁存储装置、光存储装置、MEMS、纳 米技术存储装置等）以及通信媒介（例如有线和无线通信网络、局域网、 广域网、内联网等）。

VII.结论

应理解，具体说明部分，而非发明内容和摘要部分，旨在用于解释权 利要求。发明内容和摘要部分可以提出一个以上的而非全部的由发明人设 想的本公开的实施方式，并且因此，发明和摘要部分不旨在以任何方式来 限制本公开和所附的权利要求。

在示出具体功能的实现方式的功能构造块和它们的关系的帮助下，在 以上描述了本公开。为了表述的方便，在本文中任意地定义了这些功能构 造块的界限。只要具体的功能和其关系被合适地执行，就可以定义其他的 界限。

之前的具体实施方式的描述将完整地体现本公开的一般性质，使得他 人在没有进行过度的实验、没有偏离本公开的整体概念的条件下，可以通 过运用本领域内的技术知识来容易地修改和/或调整以用于该具体实施方 式的各种应用。因此，基于本文中呈现的教导和指导，这些调整和修改旨 在处于公开的实施方式的等同物的范围和含义内。应当理解，本文中的措 辞和术语为了描述而非限制的目的，这使得本公开的术语或措辞能够依照 教导和指导而被技术人员理解。

本公开的外延和范围应当不由上述任何示例性实施方式来限制，而应 当只根据所附的权利要求及其等同物来限定。