对于具有稀疏直方图的图像的嵌入式图形编码

摘要

公开了用于对具有稀疏直方图的图像进行压缩的过程。将图像划分成块，并且为每个块指派比特预算。转换块的像素并逐比特平面地对其进行编码，从最高有效比特(MSB)开始，朝着最低有效比特(LSB)进行。将块的像素分成群组。每个群组包含具有相同值的像素。从MSB到LSB，处理每个比特平面中的群组。当处理群组时，如果所有群组成员在正被处理的当前比特平面都具有相同比特值，则编码器发送“0”，之后接着是该比特值；否则编码器发送“1”，之后接着是该群组的每个像素的细化比特，并且编码器分割该群组。

说明书

相关申请的交叉引用

本申请要求2009年6月9日提交的序列号为61/185,557、标题为 “Embedded Graphics Coding for Images with Sparse Histograms”的美国临 时申请的优先权，这里通过引用将该申请全部并入。

关于受著作权保护的材料的公告

本专利文献中的一部分材料根据美国和其他国家的著作权法受著作权 保护。著作权所有人不反对任何人对专利文献或专利公开进行复制再现， 因为其出现在了美国专利商标局的公众可得文件或记录中，但是除此之外 保留一切著作权权利。著作权所有人并不据此放弃其使本专利文献保持秘 密的权利，包括但不限于其根据37C.F.R.§1.14的权利。

技术领域

本发明总地涉及数据压缩，更具体而言涉及用于具有稀疏直方图 (sparse histogram)的图像的数据压缩。

背景技术

大多数图像压缩方案被设计用于“自然图像”，例如由数字相机拍摄 的照片。对于自然图像，在相邻像素之间存在强相关性。因此，大多数图 像压缩方案通过利用预测/变换或者这两者对像素进行去相关来工作。这导 致了预测残差或变换系数的稀疏直方图。图1示出了在8×8离散余弦变换 16之后的图像10的直方图12。如图1中所示，直方图12具有单个峰 14，其位于0附近。应用量化(如果必要的话)，并且执行(经量化的) 的预测残差或变换系数的熵编码。熵编码器一般是针对与图1所示的那些 类似的分布设计的。换言之，如果分布具有显著不同的形状，则编码性能 可能较差。

然而，也有大量的“非自然”图像需要压缩。这些图像经常包括图形 或文本，图形或文本通常具有大动态范围、强对比度、尖锐边缘、强纹理 和稀疏直方图。图2是这种“非自然图像”的示例。

传统的图像压缩算法通常不能很好地处理这些类型的图像。像素间相 关性更弱，并且预测或变换不会像对自然图像那样提供稀疏分布。

解决这些图像的压缩的一种尝试被称为“直方图打包”(histogram  packing)，其中编码器遍历整个图像，计算直方图，并且在压缩图像之前 进行像素的非线性映射。压缩要求两遍处理，从而导致增大的存储器成本 和更多的计算。比特流是不可缩放的，这意味着解码器为了对图像解码需 要整个比特流。如果不重编码则不可能部分重建。

发明内容

公开了用于对具有稀疏直方图的图像进行压缩的过程。将图像划分成 块，并且为每个块指派比特预算。转换块的像素并逐比特平面地对其进行 编码，从最高有效比特平面(MSB)开始，朝着最低有效比特平面 (LSB)进行。将块的像素分成群组。每个群组包含具有相同值的像素。 如果群组中的像素在正被编码的比特平面中具有不同的值，则分割该群 组。从MSB到LSB，处理每个比特平面中的群组。如果群组的所有成员 在正被处理的当前比特平面都具有相同比特值，则编码器为该群组发送 “0”，之后接着是该比特值。如果群组成员具有不同的值，则编码器分 割该群组并且发送“1”，之后接着是该群组的每个像素的细化比特。

在一个方面中，一种处理图像的方法包括：利用第一处理器将图像划 分成块，为每个块设定比特预算，将每个块的像素转换成二进制表示，从 最高有效比特平面到最低有效比特平面地扫描和编码像素，并且生成经编 码像素的压缩图像文件并将压缩图像文件保存到与第一处理器耦合的存储 器。图像包括具有稀疏直方图的图像。在每个比特平面扫描和编码像素包 括处理块的每个现有群组，其中，对于每个群组，如果像素在当前比特平 面中全都具有相同值，则把为“0”的第一比特写入到比特流中，并且之 后接着是指明当前群组中的所有像素的值的第二比特值；如果像素值不是 全都具有相同值，则把为“1”的第一比特值写入到比特流中，之后接着 是对于当前群组中的每个像素指明在当前比特平面中该像素的比特值的一 个比特，生成新群组，并且分割原始群组，将具有值“0”的像素保留在 原始群组中并且将具有值“1”的像素放在新群组中。该方法还包括利用 第二处理器对压缩图像文件解码以对图像解压缩。对压缩图像文件解码包 括从MSB到LSB地处理每个块，并且对于每个比特平面处理所有现有群 组。在当前比特平面处理群组包括：从比特流中读取比特，如果比特具有 “0”值，则从比特流中读取第二比特，并且将该值设定为在当前比特平 面中群组中的所有像素的比特值，如果比特具有“1”值，则对于群组中 的每个像素，从比特流中读取一个比特并将其设定为在当前比特平面中该 像素的比特值，生成新群组并将原始群组分割成两个，以使得具有“0” 值的像素在原始群组中并且具有“1”值的像素在新群组中。每个块的比 特预算在块之间是共享的。第一处理器在从由以下各项构成的组中选择的 设备内：个人计算机、膝上型计算机、计算机工作站、服务器、大型机计 算机、手持式计算机、个人数字助理、蜂窝/移动电话、智能器具、游戏控 制器、数字相机、数字摄录机、相机电话、iPod/iPhone、视频播放器、 DVD写入器/播放器、Blu-ray写入器/播放器、电视机以及家庭娱乐系 统。

在另一方面中，一种用于处理图像的装置包括：第一处理器，被配置 用于处理图像的像素，以及可在第一处理器上执行的程序，用于：将图像 划分成块，为每个块设定比特预算，将每个块的像素转换成二进制表示， 从最高有效比特平面到最低有效比特平面地扫描和编码像素，并且生成经 编码像素的压缩图像文件。该装置还包括与第一处理器耦合的存储器，其 中压缩图像文件被存储在存储器内。程序被配置为逐个比特平面地扫描和 编码像素，并且对于每个比特平面包括处理块的所有现有群组，其中，对 于每个群组，如果像素在当前比特平面中全都具有相同值，则把为“0” 的第一比特写入到比特流中，并且之后接着是指明当前群组中的所有像素 的值的第二比特值；如果像素值不是全都具有相同值，则把为“1”的第 一比特值写入到比特流中，之后接着是对于当前群组中的每个像素指明在 当前比特平面中该像素的比特值的一个比特，生成新群组，并且分割原始 群组，将具有值“0”的像素保留在原始群组中并且将具有值“1”的像素 放在新群组中。该装置还包括：在第一处理器或第二处理器上执行的第二 程序，并且第二程序被配置为对压缩图像文件解码以对图像解压缩。解码 器进一步被配置用于从MSB到LSB地处理每个块，并且对于每个比特平 面处理所有现有群组。在当前比特平面处理群组包括：从比特流中读取比 特，如果比特具有“0”值，则从比特流中读取第二比特，并且将该值设 定为在当前比特平面中群组中的所有像素的比特值，如果比特具有“1” 值，则对于群组中的每个像素，从比特流中读取一个比特并将其设定为在 当前比特平面中该像素的比特值，生成新群组并将原始群组分割成两个， 以使得具有“0”值的像素在原始群组中并且具有“1”值的像素在新群组 中。每个块的比特预算在块之间是共享的。该装置是从由以下各项构成的 组中选择的：个人计算机、膝上型计算机、计算机工作站、服务器、大型 机计算机、手持式计算机、个人数字助理、蜂窝/移动电话、智能器具、游 戏控制器、数字相机、数字摄录机、相机电话、iPod/iPhone、视频播放 器、DVD写入器/播放器、Blu-ray写入器/播放器、电视机以及家庭娱乐 系统。

在另一方面中，一种用于处理具有稀疏直方图的图像的装置包括：第 一处理装置，被配置用于处理图像的像素，可在第一处理装置上执行的编 码装置，用于：将图像划分成块，为每个块设定比特预算，将每个块的像 素转换成二进制表示，从最高有效比特平面到最低有效比特平面地扫描和 编码像素，并且生成经编码像素的压缩图像文件，以及与第一处理装置耦 合的存储装置，其中压缩图像文件被存储在存储装置内。编码装置被配置 为逐个比特平面地扫描和编码像素，并且在当前比特平面其包括处理块的 所有现有群组，其中，对于每个群组，如果像素在当前比特平面中全都具 有相同值，则把为“0”的第一比特写入到比特流中，并且之后接着是指 明当前群组中的所有像素的值的第二比特值；如果像素值不是全都具有相 同值，则把为“1”的第一比特值写入到比特流中，之后接着对于当前群 组中的每个像素有指明在当前比特平面中该像素的比特值的一个比特，生 成新群组，并且分割原始群组，将具有值“0”的像素保留在原始群组中 并且将具有值“1”的像素放在新群组中。该装置还包括：可在第一处理 装置或与第一处理装置耦合的第二处理装置上执行的解码装置，并且解码 装置被配置为对压缩图像文件解码以对图像解压缩。解码装置包括解码 器，该解码器被配置为通过从MSB到LSB地处理每个块，并且对于每个 比特平面处理所有现有群组来对压缩图像文件解码。在当前比特平面处理 群组包括：从比特流中读取比特，如果比特具有“0”值，则从比特流中 读取第二比特并且将该值设定为在当前比特平面中群组中的所有像素的比 特值，如果比特具有“1”值，则对于群组中的每个像素，从比特流中读 取一个比特并将其设定为在当前比特平面中该像素的比特值，生成新群组 并将原始群组分割成两个，以使得具有“0”值的像素在原始群组中，并 且具有“1”值的像素在新群组中。每个块的比特预算在块之间是共享 的。该装置是从由以下各项构成的组中选择的：个人计算机、膝上型计算 机、计算机工作站、服务器、大型机计算机、手持式计算机、个人数字助 理、蜂窝/移动电话、智能器具、游戏控制器、数字相机、数字摄录机、相 机电话、iPod/iPhone、视频播放器、DVD写入器/播放器、Blu-ray写入 器/播放器、电视机以及家庭娱乐系统。

在另一方面中，一种用于处理具有稀疏直方图的图像的装置包括：第 一处理器，用于处理图像的像素，可在第一处理器上执行的编码器，用 于：将图像划分成块，为每个块设定比特预算，将每个块的像素转换成二 进制表示，从最高有效比特平面到最低有效比特平面地扫描和编码像素， 并且生成经编码像素的压缩图像文件，以及与第一处理设备耦合的存储设 备，其中压缩图像文件被存储在存储设备内。编码器被配置为逐个比特平 面地扫描和编码像素，并且在当前比特平面编码包括处理块的所有现有群 组，其中，对于每个群组，如果像素在当前比特平面中全都具有相同值， 则把为“0”的第一比特写入到比特流中，并且之后接着是指明当前群组 中的所有像素的值的第二比特值；如果像素值不是全都具有相同值，则把 为“1”的第一比特值写入到比特流中，之后接着是对于当前群组中的每 个像素指明在当前比特平面中该像素的比特值的一个比特，生成新群组， 并且分割原始群组，将具有值“0”的像素保留在原始群组中，并且将具 有值“1”的像素放在新群组中。该装置还包括：可在第一处理装置或与 第一处理装置耦合的第二处理装置上执行的解码器，并且解码器被配置为 对压缩图像文件解码以对图像解压缩。解码器被配置为通过从MSB到 LSB地处理每个块，并且对于每个比特平面处理所有现有群组来对压缩图 像文件解码。在当前比特平面处理群组包括：从比特流中读取比特，如果 比特具有“0”值，则从比特流中读取第二比特并且将该值设定为在当前 比特平面中群组中的所有像素的比特值，如果比特具有“1”值，则对于 群组中的每个像素，从比特流中读取一个比特并将其设定为在当前比特平 面中该像素的比特值，生成新群组并将原始群组分割成两个，以使得具有 “0”值的像素在原始群组中并且具有“1”值的像素在新群组中。每个块 的比特预算在块之间是共享的。该装置是从由以下各项构成的组中选择 的：个人计算机、膝上型计算机、计算机工作站、服务器、大型机计算 机、手持式计算机、个人数字助理、蜂窝/移动电话、智能器具、游戏控制 器、数字相机、数字摄录机、相机电话、iPod/iPhone、视频播放器、 DVD写入器/播放器、Blu-ray写入器/播放器、电视机以及家庭娱乐系 统。

在另一方面中，一种设备的网络包括：编码器设备，用于对图像编 码，包括：将图像划分成块，为每个块设定比特预算，将每个块的像素转 换成二进制表示，从最高有效比特平面到最低有效比特平面地扫描和编码 像素，并且生成经编码像素的压缩图像文件，以及解码器设备，用于对压 缩图像文件解码，包括通过从MSB到LSB地处理每个块并且对于每个比 特平面处理所有现有群组。在当前比特平面处理群组包括：从比特流中读 取比特，如果比特具有“0”值，则从比特流中读取第二比特并且将该值 设定为在当前比特平面中群组中的所有像素的比特值，如果比特具有 “1”值，则对于群组中的每个像素，从比特流中读取一个比特并将其设 定为在当前比特平面中该像素的比特值，生成新群组并将原始群组分割成 两个，以使得具有“0”值的像素在原始群组中，并且具有“1”值的像素 在新群组中。编码器被配置为逐个比特平面地扫描和编码像素，并且在当 前比特平面编码包括处理块的所有现有群组，其中，对于每个群组，如果 像素在当前比特平面中全都具有相同值，则把为“0”的第一比特写入到 比特流中，并且之后接着是指明当前群组中的所有像素的值的第二比特 值；如果像素值不是全都具有相同值，则把为“1”的第一比特值写入到 比特流中，之后接着是对于当前群组中的每个像素指明在当前比特平面中 该像素的比特值的一个比特，生成新群组，并且分割原始群组，将具有值 “0”的像素保留在原始群组中并且将具有值“1”的像素放在新群组中。 每个块的比特预算在块之间是共享的。

在一些实施例中，多个块能够相互共享其比特预算，从而使得能够向 难以编码的块分配更多比特。这是为了改善整体编码性能。在一个极端情 况下，一个比特预算被图像中的所有块共享。在另一个极端情况下，每个 块具有其自己的比特预算。一个比特预算用于所有块和每个块具有比特预 算之间的比特预算的任何变化都是可能的。

附图说明

图1示出了现有技术的图像的离散余弦变换和相应直方图的示意图。

图2示出了典型的图形图像。

图3示出了根据一些实施例的用于对图形图像编码的方法的示意图。

图4示出了根据一些实施例的对于块中的比特平面的EGC编码的示 意图。

图5示出了根据一些实施例的对于块的EGC编码的示意图。

图6示出了根据一些实施例的共享比特预算的多个块的EGC编码的 示意图。

图7示出了根据一些实施例的对于块中的比特平面的EGC解码的示 意图。

图8示出了根据一些实施例的对于单个块的EGC解码的示意图。

图9示出了根据一些实施例的共享比特预算的多个块的EGC解码的 示意图。

图10示出了根据一些实施例的用于利用EGC对图形图像编码和解码 的系统的示意图。

具体实施方式

更具体地参考附图，出于例示目的，对于具有稀疏直方图的图像的嵌 入式图形编码被实现在非现有技术附图中概括示出的装置中。应明白，该 装置在配置以及部件的细节方面能够变化，并且方法在具体步骤和序列方 面能够变化，而不脱离这里公开的基本思想。

对于具有稀疏直方图的图像的嵌入式图形编码包括一种编码算法以及 系统和方法，用于对具有稀疏直方图的图像，例如通常对于(但不限于) 图形或文本图像进行编码。

该算法、系统和方法使用被称为嵌入式图形编码(Embedded Graphics  Coding，EGC)的新过程，其提供有损到无损可缩放性，其中即使解码在 比特流中间被停止，解码器也仍能够基于其已接收到的比特作出合理的经 解码块。如果发送了整个比特流，则能够无损地重建图像。

这里描述的算法、系统和方法具有低复杂度，以及高编码性能。

图3示出了对具有稀疏直方图的图像编码的过程30的流程图。首 先，在步骤32，将图像划分成块。接下来，在步骤34，对于每个块设定 比特预算。比特预算一般是编码器和解码器双方都一致同意的。编码器和 解码器能够被配置成使得如果带宽是时变的则比特预算能够被动态改变。 经编码的比特流是完全嵌入的，因此比特预算能够被任意改变。

对于每个块，在步骤36，将图像的像素转换成二进制表示。要注意， 编码器不需要执行任何预测或变换，因为假定像素已经具有稀疏直方图。 由于没有预测或变换，削减了计算和要求的处理力。

接下来，在步骤38，逐比特平面地扫描并编码每个块的像素。数字图 像的比特平面是在各个二进制数中具有相同位置的一组比特。例如，对于 8比特数据表示，有8个比特平面。第一比特平面包含最高有效位的集 合，并且第8个包含最低有效位。最高有效比特平面(MSB)首先被扫描 和编码，然后前进到次高有效比特平面，直到最低有效比特平面(LSB) 被扫描为止。每个比特平面的编码过程在下文中更详细描述。

在步骤40，停止编码。一般如果两个条件之一发生则停止编码：1) 当前块的比特预算被耗尽，或者2)如果重建的块已到达了LSB的末尾。 在此情况下，解码器也已确定了块的末尾。

图4示出了根据一些实施例的对于块中的比特平面的EGC编码的示 意图。在步骤50中，获得现有群组的数目(N)。在步骤52中，将当前 群组设为群组1。在步骤54中，算法评估当前群组中的像素在当前比特平 面中是否具有相同比特值。

如果群组中的所有像素都具有相同比特值，则在步骤56中，将“0” 写入到比特流中，之后接着是另一个“0”或“1”，以指示当前群组中的 所有像素的比特值。

如果群组中的像素不具有相同比特值，则在步骤58中，将“1”写入 到比特流中，之后接着是针对当前群组中的每个像素的比特值。在步骤60 中，在不增大N的情况下生成新的群组。在步骤62中，该群组被一分为 二，其中具有值“0”的像素被保持在同一群组中，而具有值“1”的像素 则被放入新群组中。

在步骤64中，编码器评估当前群组是否是群组N。如果当前群组不 是群组N，则在步骤66中过程转到下一群组，并且过程在步骤54中重新 开始。如果当前群组是群组N，则对当前比特平面的编码结束。

图5示出了根据一些实施例的对于块的EGC编码的示意图。在步骤 68中，将块的所有像素放在群组1中。在步骤70中，将当前比特平面设 为MSB。在步骤72中，利用图4中描述的方法对当前比特平面编码。在 步骤74中，判定当前比特平面是否是LSB。如果当前比特平面不是 LSB，则在步骤76中过程转到下一比特平面，并且过程在步骤72中重新 开始。如果当前比特平面是LSB，则对当前块的编码停止。

图6示出了根据一些实施例的共享比特预算的多个块的EGC编码的 示意图。在步骤78中，将每个块的像素放到针对每个块的同一群组中 (不同块的像素在不同群组中)。在步骤80中，将当前比特平面设为 MSB。在步骤82中，将当前块设为第一块。在步骤84中，利用图4的方 法对当前块的当前比特平面编码。在步骤86中，判定当前块是否是最后 块。如果当前块不是最后块，则在步骤88中过程转到下一块，并且过程 在步骤84重新开始。如果当前块是最后块，则在步骤90中判定当前比特 平面是否是LSB。如果当前比特平面是LSB，则编码结束。如果当前比特 平面不是LSB，则在步骤92中过程转到下一比特平面，并且过程在步骤 82重新开始。

图7示出了根据一些实施例的对于块中的比特平面的EGC解码的示 意图。在步骤100中，获得现有群组的数目(N)。在步骤102中，将当 前群组设为群组1。在步骤104中，从比特流中读取一比特。在步骤106 中，判定该比特是否包含值“0”。如果值为“0”，则在步骤108中，从 比特流中读取另一比特并且对当前比特平面中该群组中的所有像素设定该 比特值。例如，如果读取的第二比特是“1”，则所有比特被设定为 “1”。如果比特值不是“0”，则在步骤110中，对于群组中的每个像素 从比特流中读取一比特，并且将该比特设定为当前比特平面中该像素的比 特值。在步骤112中，在不增大N的情况下生成新群组。在步骤114中， 该群组被分割，其中具有值“0”的像素被保持在同一群组中，而具有值 “1”的像素被放入新群组中。在步骤116中，判定当前群组是否是群组 N。如果当前群组不是群组N，则在步骤118中过程转到下一群组。如果 当前群组是群组N，则当前比特平面解码结束。

图8示出了根据一些实施例的对于单个块的EGC解码的示意图。在 步骤120中，将块的所有像素放在群组1中。在步骤122中，将当前比特 平面设为MSB。在步骤124中，利用图7中描述的方法对当前比特平面解 码。在步骤126中，判定当前比特平面是否是LSB。如果当前比特平面不 是LSB，则在步骤128中过程转到下一比特平面，并且过程在步骤124中 重新开始。如果当前比特平面是LSB，则对当前块的解码停止。

图9示出了根据一些实施例的共享比特预算的多个块的EGC解码的 示意图。在步骤130中，将每个块的像素放到针对每个块的同一群组中 (不同块的像素在不同群组中)。在步骤132中，将当前比特平面设为 MSB。在步骤134中，将当前块设为第一块。在步骤136中，利用图7的 方法对当前块的当前比特平面解码。在步骤138中，判定当前块是否是最 后块。如果当前块不是最后块，则在步骤140中过程转到下一块，并且过 程在步骤136重新开始。如果当前块是最后块，则在步骤142中判定当前 比特平面是否是LSB。如果当前比特平面是LSB，则编码结束。如果当前 比特平面不是LSB，则在步骤144中过程转到下一比特平面，并且过程在 步骤134重新开始。

在一些实施例中，多个块能够相互共享其比特预算，从而使得能够向 难以编码的块分配更多比特。这是为了改善整体编码性能。在一个极端情 况下，一个比特预算被图像中的所有块共享。在另一个极端情况下，每个 块具有其自己的比特预算。一个比特预算用于所有块和每个块具有比特预 算之间的比特预算的任何变化都是可能的。

在一些情况下，算法执行部分恢复的图像的像素重建。如果像素的 LSB已被解码，则解码器知道该像素的真实值。如果像素的解码在中间某 处停止，则解码器只知道像素值所处的值的范围。

例如，如果像素的前5个比特平面被解码为10110，并且仍有3个比 特平面是解码器未知的，则真实的像素值在范围10110000～10110111中 (用二进制表示)。在此情况下，解码器选择接近中点重建并且将未知比 特设为100...0。在上述示例中，重建值将是10110100。

图10示出了根据一些实施例的用于对具有稀疏直方图的图形图像编 码和解码的示例性系统200。根据一些实施例，原始图像202被具有处理 器206和编码器208的第一设备204处理。设备204、214能够是个人计算 机、膝上型计算机、计算机工作站、服务器、大型机计算机、手持式计算 机、个人数字助理、蜂窝/移动电话、智能器具、游戏控制器、数字相机、 数字摄录机、相机电话、iPod/iPhone、视频播放器、DVD写入器/播放 器、Blu-ray写入器/播放器、电视机、家庭娱乐系统或者具有处理器206 和用于存储编码模块208的存储器或其他存储装置209的其他设备。然后 能够利用包括编程/编码装置的编码器208对原始图像编码以形成压缩图像 文件210(例如经由上述算法/过程)。这能够通过互联网212或类似网络 被发送到第二设备214。第二设备214包括处理器216、存储器或存储装 置219以及解码模块218，解码模块218包括编程/解码装置，该编程/解码 装置被配置为读取压缩数据文件210并且根据这里描述的方法对其解码 (例如经由上述算法/过程)以生成非压缩图像220。要明白，两个设备都 能够包括编码模块208和解码模块218两者，并同样地执行编码和解码操 作两者。

示例1

在示例性的8比特图像中，一半的像素是零，并且其他像素具有值 255。0和255的位置是随机的。理论上，为了无损压缩，需要每个像素至 少1个比特。传统的图像编码算法不能提供接近每像素1比特的无损压缩 (除了直方图打包以外)。

在嵌入式图形编码算法(例如编码算法38)中，在MSB中发送“1” 以指示出被分割成两个群组的原始群组，并且每个像素1个比特来发送在 MSB每个像素的比特值。否则，发送“0”以指示出群组中的所有像素都 是相同的。

对于接下来的比特平面，对于0的群组发送“00”，并且对于255的 群组发送“01”。

块的无损压缩的总比特是

1+n+4×7＝n+29

其中n是块的像素数目。

平均比特率是(1+29/n)比特每像素，这接近合理块大小的理论极限 (例如当n＝8×8＝64时)。

编码算法也能够被构造成使得，如果群组只具有1个或2个成员，则 其不发送1比特的“分割与否”信号，而直接发送(一个或多个)细化比 特。

另外，为了获得更好的嵌入性，能够重安排比特流的顺序。如果群组 被分割，则其细化比特的发送被延迟，并且算法前进到处理下一群组。有 可能下一群组不被分割，从而一个比特能够被用于表示多个比特。另外， 如果比特流停止在比特平面的中间，则此方案提供了更好的重建质量。

如果群组的细化停止在群组的中间，则可能有一些视觉伪影。为了避 免此问题，解码器能够被配置为，如果未接收到当前群组的一些细化比 特，则撤消对群组的细化。

在另一替换实施例中，取代以原始比特的形式发送“分割与否”比特 和细化比特，也能够利用游程长度编码或二进制算术编码对比特进行编码 以进一步改善编码效率。

嵌入式图形编码方法也适合作为传统图像编码的补偿。嵌入式图形编 码能够与任何基于块的图像编码算法相组合。在这种情况下，比特流中的 1比特被用于告知解码器是否使用了EGC。

参考对根据一些实施例的方法和系统的流程图示描述了实施例。这些 方法和系统也能够被实现为计算机程序产品。就这一点而言，流程图的每 个块或步骤以及流程图中的块(和/或步骤)的组合能够通过各种手段来实 现，例如硬件、固件和/或软件，包括体现在计算机可读程序代码逻辑中的 一个或多个计算机程序指令。正如将明白的，任何这种计算机程序指令都 能够被加载到计算机上，包括但不限于通用计算机或专用计算机，或者其 他可编程处理装置以产生机器，使得在计算机或其他可编程处理装置上执 行的计算机程序指令创建用于实现一个或多个的流程图的一个或多个块中 指定的功能的装置。

因此，流程图的块支持用于执行指定功能的装置的组合，用于执行指 定功能的步骤的组合，以及用于执行指定功能的计算机程序指令，例如体 现在计算机可读程序代码逻辑装置中的。还将理解，流程图示的每个块以 及流程图示中的块的组合能够由执行指定功能或步骤的专用的基于硬件的 计算机系统实现，或者由专用硬件和计算机可读程序代码逻辑装置的组合 实现。

另外，这些计算机程序指令，例如体现在计算机可读程序代码逻辑中 的，也能够被存储在计算机可读存储器中，该存储器能够指导计算机或其 他可编程处理装置以特定方式工作，使得存储在计算机可读存储器中的指 令产生包括实现一个或多个流程图的一个或多个块中指定的功能的指令装 置的制造品。计算机程序指令也能够被加载到计算机或其他可编程处理装 置上，以使得在计算机或其他可编程处理装置上执行一系列操作性步骤， 以产生由计算机实现的过程，从而使得在计算机或其他可编程处理装置上 执行的指令提供用于实现一个或多个流程图的一个或多个块中指定的功能 的步骤。

为了对于具有稀疏直方图的图像利用EGC，用户例如在数字摄录机上 获取视频/图像，并且在获取视频的同时或之后，或者当将视频发送到诸如 计算机之类的另一设备时，EGC方法自动对视频的每个图像编码，从而使 得视频被适当编码以维持高质量视频。EGC方法自动发生，无需用户参 与。也能够利用类似的方法对视频解码以便显示。

在操作中，EGC方法被用于对诸如视频的帧之类的图像进行编码和传 送。每个图像块被从MSB到LSB地处理，因此所得到的比特平面仍是嵌 入的。改善的编码方法能够用在任何实现方式中，包括但不限于无线高清 (WiHD)。

这里描述的对于具有稀疏直方图的图像的EGC的方法能够用于视频 和/或图像，包括高清视频。

高清视频能够具有任何格式，包括但不限于HDCAM、HDCAM-SR、 DVCPRO HD、D5 HD、XDCAM HD、HDV和AVCHD。

对于具有稀疏直方图的图像的嵌入式图形编码的一些实施例

1.一种处理图像的方法，包括：

a.利用第一处理器将图像划分成块；

b.为每个块设定比特预算；

c.将每个块的像素转换成二进制表示；

d.从最高有效比特平面到最低有效比特平面地扫描和编码像素；并且

e.生成经编码像素的压缩图像文件并将所述压缩图像文件保存到与第 一处理器耦合的存储器。

2.如第1条中所述的方法，其中，图像包括具有稀疏直方图的图像。

3.如第1条中所述的方法，其中，在每个比特平面扫描和编码像素包 括处理该比特平面中的每个现有群组，这进一步包括：

a.如果群组的像素值在当前比特平面全都具有相同值，则把为“0” 的第一比特值写入到比特流中；并且

b.把指明当前群组中的所有像素的值的第二比特值写入到比特流中。

4.如第3条中所述的方法，还包括：

a.如果群组的像素值在当前比特平面不是全都具有相同值，则把为 “1”的第一比特值写入到比特流中，之后接着是对于当前群组中的每个 像素指明在当前比特平面中该像素的比特值的一个比特；

b.生成新群组；并且

c.将原始群组分割成两个，将具有值“0”的像素保留在原始群组 中，并且将具有值“1”的像素放在新群组中。

5.如第4条中所述的方法，还包括利用第二处理器对压缩图像文件解 码以对图像解压缩。

6.如第5条中所述的方法，其中，对压缩图像文件解码包括从最高有 效比特平面到最低有效比特平面地扫描和解码像素，并且对于每个比特平 面：

a.获得现有群组的数目；

b.将当前群组设定为第一群组；

c.从比特流中读取比特；

d.如果比特具有“0”值，则从比特流中读取第二比特并且将该值设 定为在当前比特平面中群组中的所有像素的比特值；

e.如果比特具有“1”值，则对于群组中的每个像素，从比特流中读 取一个比特并将其设定为在当前比特平面中该像素的比特值，生成新群组 并将新群组分割成第一群组和第二群组，以使得具有“0”值的像素在第 一群组中，并且具有“1”值的像素在第二群组中；并且

f.重复c-e，直到达到当前比特平面的末尾为止。

7.如第1条中所述的方法，其中，每个块的比特预算在块之间是共享 的。

8.如第1条中所述的方法，其中，第一处理器在从由以下各项构成的 组中选择的设备内：个人计算机、膝上型计算机、计算机工作站、服务 器、大型机计算机、手持式计算机、个人数字助理、蜂窝/移动电话、智能 器具、游戏控制器、数字相机、数字摄录机、相机电话、iPod/iPhone、 视频播放器、DVD写入器/播放器、Blu-ray写入器/播放器、电视机以及 家庭娱乐系统。

9.一种用于处理图像的装置，包括：

a.第一处理器，该第一处理器被配置用于处理图像的像素；以及

b.可在第一处理器上执行的程序，用于：

i.将图像划分成块；

ii.为每个块设定比特预算；

iii.将每个块的像素转换成二进制表示；

iv.从最高有效比特平面到最低有效比特平面地扫描和编码像素； 并且

v.生成经编码像素的压缩图像文件。

10.如第9条中所述的装置，还包括与第一处理器耦合的存储器，其 中，压缩图像文件被存储在存储器内。

11.如第9条中所述的装置，其中，程序被配置为在每个比特平面扫 描和编码像素，包括处理该比特平面中的每个现有群组，这进一步包括：

a.如果群组的像素值在当前比特平面全都具有相同值，则把为“0” 的第一比特值写入到比特流中；并且

b.把指明当前群组中的所有像素的值的第二比特值写入到比特流中。

12.如第11条中所述的装置，其中，程序还被配置为通过以下操作来 扫描和编码像素：

a.如果群组的像素值在当前比特平面不是全都具有相同值，则把为 “1”的第一比特值写入到比特流中，之后接着是对于当前群组中的每个 像素指明在当前比特平面中该像素的比特值的一个比特；

b.生成新群组；并且

c.将原始群组分割成两个，将具有值“0”的像素保留在原始群组 中，并且将具有值“1”的像素放在新群组中。

13.如第12条中所述的装置，还包括：

a.在第一处理器或第二处理器上执行的第二程序；并且

b.第二程序被配置为对压缩图像文件解码以对图像解压缩。

14.如第13条中所述的装置，其中，解码器还被配置用于从最高有效 比特平面到最低有效比特平面地扫描和解码像素，并且对于每个比特平 面：

a.获得现有群组的数目；

b.将当前群组设定为第一群组；

c.从比特流中读取比特；

d.如果比特具有“0”值，则从比特流中读取第二比特，并且将该值 设定为在当前比特平面中群组中的所有像素的比特值；

e.如果比特具有“1”值，则对于群组中的每个像素，从比特流中读 取一个比特并将其设定为在当前比特平面中该像素的比特值，生成新群组 并将新群组分割成第一群组和第二群组，以使得具有“0”值的像素在第 一群组中并且具有“1”值的像素在第二群组中；并且

f.重复c-e，直到达到当前比特平面的末尾为止。

15.如第9条中所述的装置，其中，每个块的比特预算在块之间是共 享的。

16.如第9条中所述的装置，其中，该装置是从由以下各项构成的组 中选择的：个人计算机、膝上型计算机、计算机工作站、服务器、大型机 计算机、手持式计算机、个人数字助理、蜂窝/移动电话、智能器具、游戏 控制器、数字相机、数字摄录机、相机电话、iPod/iPhone、视频播放 器、DVD写入器/播放器、Blu-ray写入器/播放器、电视机以及家庭娱乐 系统。

17.一种用于处理具有稀疏直方图的图像的装置，包括：

a.第一处理装置，该第一处理器被配置用于处理图像的像素；

b.可在第一处理装置上执行的编码装置，用于：

i.将图像划分成块；

ii.为每个块设定比特预算；

iii.将每个块的像素转换成二进制表示；

iv.从最高有效比特平面到最低有效比特平面地扫描和编码像素； 并且

v.生成经编码像素的压缩图像文件；以及

c.与第一处理装置耦合的存储装置，其中，压缩图像文件被存储在存 储装置内。

18.如第17条中所述的装置，其中，编码装置被配置为在每个比特平 面扫描和编码像素，包括处理该比特平面中的每个现有群组，这进一步包 括：

a.如果群组的像素值在当前比特平面全都具有相同值，则把为“0” 的第一比特值写入到比特流中；并且

b.把指明当前群组中的所有像素的值的第二比特值写入到比特流中。

19.如第18条中所述的装置，其中，编程装置还被配置为扫描和编码 像素，包括：

a.如果群组的像素值在当前比特平面不是全都具有相同值，则把为 “1”的第一比特值写入到比特流中，之后接着是对于当前群组中的每个 像素指明在当前比特平面中该像素的比特值的一个比特；

b.生成新群组；并且

c.将原始群组分割成两个，将具有值“0”的像素保留在原始群组中 并且将具有值“1”的像素放在新群组中。

20.如第19条中所述的装置，还包括：

a.可在第一处理装置或与第一处理装置耦合的第二处理装置上执行的 解码装置；并且

b.解码装置被配置为对压缩图像文件解码以对图像解压缩。

21.如第20条中所述的装置，其中，解码装置包括解码器，该解码器 被配置为通过从最高有效比特平面到最低有效比特平面地扫描和解码像 素，并且对于每个比特平面进行以下操作来对压缩图像文件解码：

a.获得现有群组的数目；

b.将当前群组设定为第一群组；

c.从比特流中读取比特；

d.如果比特具有“0”值，则从比特流中读取第二比特并且将该值设 定为在当前比特平面中群组中的所有像素的比特值；

e.如果比特具有“1”值，则对于群组中的每个像素，从比特流中读 取一个比特并将其设定为在当前比特平面中该像素的比特值，生成新群组 并将新群组分割成第一群组和第二群组，以使得具有“0”值的像素在第 一群组中并且具有“1”值的像素在第二群组中；并且

f.重复c-e，直到达到当前比特平面的末尾为止。

22.如第17条中所述的装置，其中，每个块的比特预算在块之间是共 享的。

23.如第17条中所述的装置，其中，该装置是从由以下各项构成的组 中选择的：个人计算机、膝上型计算机、计算机工作站、服务器、大型机 计算机、手持式计算机、个人数字助理、蜂窝/移动电话、智能器具、游戏 控制器、数字相机、数字摄录机、相机电话、iPod/iPhone、视频播放 器、DVD写入器/播放器、Blu-ray写入器/播放器、电视机以及家庭娱乐 系统。

24.一种用于处理具有稀疏直方图的图像的装置，包括：

a.第一处理器，该第一处理器用于处理图像的像素；

b.可在第一处理器上执行的编码器，用于：

i.将图像划分成块；

ii.为每个块设定比特预算；

iii.将每个块的像素转换成二进制表示；

iv.从最高有效比特平面到最低有效比特平面地扫描和编码像素； 并且

v.生成经编码像素的压缩图像文件；以及

c.与第一处理设备耦合的存储设备，其中，压缩图像文件被存储在存 储设备内。

25.如第24条中所述的装置，其中，编码器被配置为扫描和编码像 素，包括：

a.如果像素值全都具有相同值，则把指明像素值全都具有相同值的第 一比特值写入到比特流中；并且

b.把指明当前群组中的所有像素的值的第二比特值写入到比特流中。

26.如第25条中所述的装置，其中，编码器被配置为在每个比特平面 扫描和编码像素，包括处理该比特平面中的每个现有群组，这进一步包 括：

a.如果群组的像素值在当前比特平面全都具有相同值，则把为“0” 的第一比特值写入到比特流中；

b.把指明当前群组中的所有像素的值的第二比特值写入到比特流中；

c.如果群组的像素值在当前比特平面不是全都具有相同值，则把为 “1”的第一比特值写入到比特流中，之后接着是对于当前群组中的每个 像素指明在当前比特平面中该像素的比特值的一个比特；

d.生成新群组；并且

e.将原始群组分割成两个，将具有值“0”的像素保留在原始群组中 并且将具有值“1”的像素放在新群组中。

27.如第26条中所述的装置，还包括：

a.可在第一处理装置或与第一处理装置耦合的第二处理装置上执行的 解码器；并且

b.解码器被配置为对压缩图像文件解码以对图像解压缩。

28.如第27条中所述的装置，其中，解码器被配置为通过从最高有效 比特平面到最低有效比特平面地扫描和解码像素，并且对于每个比特平面 进行以下操作来对压缩图像文件解码：

a.获得现有群组的数目；

b.将当前群组设定为第一群组；

c.从比特流中读取比特；

d.如果比特具有“0”值，则从比特流中读取第二比特并且将该值设 定为在当前比特平面中群组中的所有像素的比特值；

e.如果比特具有“1”值，则对于群组中的每个像素，从比特流中读 取一个比特并将其设定为在当前比特平面中该像素的比特值，生成新群组 并将新群组分割成第一群组和第二群组，以使得具有“0”值的像素在第 一群组中并且具有“1”值的像素在第二群组中；并且

f.重复c-e，直到达到当前比特平面的末尾为止。

29.如第24条中所述的装置，其中，每个块的比特预算在块之间是共 享的。

30.如第24条中所述的装置，其中，该装置是从由以下各项构成的组 中选择的：个人计算机、膝上型计算机、计算机工作站、服务器、大型机 计算机、手持式计算机、个人数字助理、蜂窝/移动电话、智能器具、游戏 控制器、数字相机、数字摄录机、相机电话、iPod/iPhone、视频播放 器、DVD写入器/播放器、Blu-ray写入器/播放器、电视机以及家庭娱乐 系统。

31.一种设备的网络，包括：

a.编码器设备，用于对图像编码，包括：

i.将图像划分成块；

ii.为每个块设定比特预算；

iii.将每个块的像素转换成二进制表示；

iv.从最高有效比特平面到最低有效比特平面地扫描和编码像素； 并且

v.生成经编码像素的压缩图像文件；以及

b.解码器设备，用于通过从最高有效比特平面到最低有效比特平面地 扫描和解码像素，并且对于每个比特平面进行以下操作来对压缩图像文件 解码：

i.获得现有群组的数目；

ii.将当前群组设定为第一群组；

iii.从比特流中读取比特；

iv.如果比特具有“0”值，则从比特流中读取第二比特，并且将 该值设定为在当前比特平面中群组中的所有像素的比特值；

v.如果比特具有“1”值，则对于群组中的每个像素，从比特流中 读取一个比特并将其设定为在当前比特平面中该像素的比特值，生成 新群组并将新群组分割成第一群组和第二群组，以使得具有“0”值的 像素在第一群组中并且具有“1”值的像素在第二群组中；并且

vi.重复iii-v，直到达到当前比特平面的末尾为止。

32.如第31条中所述的装置，其中，编码器设备被配置为在每个比特 平面扫描和编码像素，包括处理该比特平面中的每个现有群组，这进一步 包括：

a.如果群组的像素值在当前比特平面全都具有相同值，则把为“0” 的第一比特值写入到比特流中；

b.把指明当前群组中的所有像素的值的第二比特值写入到比特流中。

33.如第32条中所述的装置，其中，编码器设备被配置为扫描和编码 像素，包括：

a.如果群组的像素值在当前比特平面不是全都具有相同值，则把为 “1”的第一比特值写入到比特流中，之后接着是对于当前群组中的每个 像素指明在当前比特平面中该像素的比特值的一个比特；

b.生成新群组；并且

c.将原始群组分割成两个，将具有值“0”的像素保留在原始群组中 并且将具有值“1”的像素放在新群组中。

34.如第33条中所述的装置，其中每个块的比特预算在块之间是共享 的。

已经就包含细节的具体实施例描述了本发明以帮助理解本发明的构造 和操作的原理。这里对具体实施例及其细节的这种提及并不意欲限制所附 权利要求的范围。本领域的技术人员将容易清楚，在不脱离由权利要求限 定的本发明的精神和范围的情况下，可对被选择用于例示的实施例进行其 他各种修改。