CN1148005C - 快速联合图像专家组霍夫曼编码和解码方法 - Google Patents

Abstract

通过利用依赖码长的两个不同的表格式来简化霍夫曼编码，特别是简化压缩数据格式的霍夫曼编码。霍夫曼表也由此减小了尺寸。通过测试压缩的数据流中的有效霍夫曼码的长度和利用对应于一个测试标准的位移提供霍夫曼表符号值的直接标引来减少解码的执行次数，同时极大的减小用于此目的的查询表的尺寸。

Description

快速联合图像专家组霍夫曼编码和解码方法

                       技术领域

本发明一般涉及用于各种不同应用的图像压缩，特别是涉及结合一种以压缩(packed)格式存储离散余弦变换(DCT)分组的结构，根据JPEG(联合图像专家组)标准进行霍夫曼熵编解码。

                       背景技术

图像和图形包含非常大量的数据，如果数字化这些数据以便传输或由数字数据处理器处理，则要有好的保真度就经常需要数百万个字节表示该图像或图形的各个像素。图像压缩的目的在于用较少的数据表示图像，以节省存储成本或传输时间和费用。通过近似原始图像而不是通过精确再现可以实现最有效的压缩。Pennebaker和Mitchell在″JPEG静止图象数据压缩标准″中详细讨论了JPEG标准，并由VanNostrand Reinhold于1993年出版，这里将其作为参考，该JPEG标准允许图象在各种应用之间互换并开发了在多媒体应用中提供数字连续色调的彩色图像的能力。

JPEG主要涉及具有两维空间的图像，包含灰度级或彩色信息，不具有时间的相关性，这是与MPEG(活动图像专家组)标准的区别之处。JPEG压缩可以降低一个数量级的存储需求并改进此过程中的系统响应时间。JPEG标准的主要目的在于为给定的数据量提供最大的图像保真度和/或可用传输或处理时间，并容纳任意程度的数据压缩。经常是这种情况，即数据被压缩到二十分之一或更多(传输或处理时间降低相当的比例)而不会产生一般观众能够察觉的人为痕迹。

JPEG的的基本构件之一是离散余弦变换(DCT)。此变换的一个重要方面是它产生非相关系数。解相关系数对于压缩很重要，因为可以独立地对待每个系数而不丧失压缩效率。DCT的另一个重要方面是能够利用视觉加权的量化值来量化DCT系数。因为人类的视觉系统将一图像分解成一组波形，每个波形具有一特定的空间频率，所以视觉系统的反应非常依赖空间频率，因此可以从眼睛能够看到的图像结构中除去不能感知的图像结构。因此DCT提供对此分解的良好近似，以允许截去或省略不会显著影响观众对图象保真度的感觉的数据。

根据JPEG标准，原始的单色图像首先被以任意的分辨率分解成8×8阵列六十四象素的分组，该分辨率假设足够高而不会产生看得见的图形失真。(通过将每个分量单独分解成8×8象素分组来压缩彩色图像。)这些技术和硬件是熟知的，它们可以非常迅速地对此量化图象数据执行DCT，生成六十四个DCT系数。许多图像的DCT系数多数是零(在任何情况下都不会对该图像作出贡献)或接近零，当相应于眼睛相对感觉迟钝的空间频率时，它们可以被忽略或省略。因为人类的眼睛对很高和很低的空间频率不是很敏感，作为JPEG标准的一部分，在许多实例中以所谓的Z字型模式提供DCT系数，Z字型模式大致相应于空间频率的总和沿水平和垂直方向增加，这样趋向于将对应不很重要的空间频率的DCT系数归到DCT系数数据流的最后，允许它们作为一组来进行有效地压缩。

虽然上述的离散余弦变换和编码可以为实际遇到的多数图像提供显著的数据压缩，但不能保证数据量的真正降低，而且压缩程度不是最佳的，特别是因为表示每个DCT系数的同等精度要求传送相同数目的位(虽然JPEG标准允许DCT值通过在一表中编码的范围而量化)。即，DCT编码形成的压缩收益大部分体现在增加了处理零和接近零值的DCT系数的效率，虽然某些压缩也通过降低精度的量化来实现。相应地，JPEG标准提供被称为熵编码的第二阶段压缩和编码。

熵编码的概念通常类似于热力学中更为熟悉的熵的概念，在热力学中，熵量化一物理系统中的″无序″量。在信息论领域中，在任意大小和与任何给定量的信息或符号的意义无关的数据集合环境中，熵是用来对任何给定量信息(例如符号)的内容的可预测性的度量。此概念对一给定的字母符号的可实现压缩量提供可以实现的下限，更主要的是导致这样一种压缩方案，即前提是相对较多可预测的数据或符号比相对较少可预测的数据或符号包含更少的信息，相反的，相对较少可预测的数据或符号比相对较多可预测的数据或符号包含更多的信息。因此，假设一种用于此目的的适当的码，通过对较多可预测的(即在此数据体中更常见并包含较少的信息)符号或值分配较少的位可以实现最佳的有效压缩，虽然要为相对罕见的符号或数值预留较长的码。

实际上，霍夫曼编码和算术编码适合于熵编码，并且二者都为JPEG标准所采纳。JPEG标准的操作区别在于虽然两种编码技术都要求相应于这些码的数值表，但是算术编码提供了缺省表，但霍夫曼编码没有。但是，如果不过分的折衷图象保真度来降低计算常规霍夫曼表的计算开销，某些特定的霍夫曼表经常不加选择地被使用，虽然在JPEG标准下可以自由地指定这些表以便在重建时获得最大的编码效率和图像保真度，其中许多是缺省的性质。

应当理解的是虽然如果编码或调节表合理地适合于该图像，熵编码，特别是利用霍夫曼编码的熵编码保证了非常主要的数据压缩的程度，但编码自身计算量非常大，因为它是基于统计的，并且需要关于大量的图像值或表示图像的值，例如DCT系数的统计信息的集合。相反，使用体现不表示正被编码的图像的概率的表可能会导致扩展而不是压缩，如果被编码的图像需要编码从中形成这些表的图象中相对罕见的许多值，即使这种情况很少遇见。

为此某些霍夫曼表实际上已经成为标准使用，即使不会实现所使用压缩程度的最佳压缩和/或最佳保真度。相反，霍夫曼编码的压缩效率通常可以显著增加并且可以通过相应于感兴趣图像的定制霍夫曼表在给定数据位数内最佳的保持图像保真度，但是这只能用大的编码计算负荷来实现。

当所编码的任何特定值的发生比例超过50％时，由于将霍夫曼码指定给各个编码值技术的多级性质和至少一个位必须用于表示最经常出现和最可预测的数值的事实，即使包含在其中的信息可以理想地调整得更少，也会遇到霍夫曼编码特性的另一种效率低下。例如，单个值的发生比例上升到75％，霍夫曼编码的效率下降86％。实际上，绝大多数DCT系数是(或量化成)零，因此在霍夫曼编码DCT系数或DCT系数差值中会时常遇到大量的效率低下。对于AC系数，JPEG委员会通过将零值系数游程集合在一起，而且不编码单独为零值的系数来解决这个问题。因此一霍夫曼符号出现超过一半时间的可能性可以极大地被降低。

霍夫曼解码还需要大量的计算负荷，因为压缩效率主要从可变长度码中得出，可变长度码需要另外的处理来检测各个数值或符号的结束点。另外，通过使用编码表可以实现此处理，编码表必须与熵编码图象数据一起传送而且可以随着每个图象而改变。由于霍夫曼码长度可变以根据数据的可预测性或包含在特定符号或值的数据量来分配位数的事实，导致访问表中数据的复杂性尖锐化。为了增加响应速率，已经执行了霍夫曼表中能被用于解码的查询表。因此，每一码字必须经常访问至少两个字节的表数据。

而且，因为允许十六位的霍夫曼码长度，现有技术的解码方法将访问具有用于符号值的2¹⁶个入口和用于码长的2¹⁶个入口的霍夫曼表。每次霍夫曼表被指定或改变时，必须计算这些入口。直到四个DC和四个AC表被用于解码和交织基线的四个分量图像。对于具有小的芯片超高速缓冲存储器或RAM的硬件来说，这种大表将会降低性能，因为每个超高速缓冲存储器的失配(miss)或RAM(随机采取存储)访问都需要额外的处理周期。

                      发明内容

因此本发明的目的在于提供一种霍夫曼编码和解码技术，它可以用少得多的时间和简化的处理资源和硬件来实现。

本发明的另一个目的在于提供一种霍夫曼编码和解码技术，它通过使用压缩的中间数据格式来增强。

为了实现本发明的这些和其它目的，提供一种霍夫曼编码符号的方法，该方法包括步骤：对于表中第一次出现的给定长度的码定义一籽数值(Seed value)，存储一码字的长度，当所述数目和所述码字的位数小于或等于预定位数时以第一种格式存储该长度和码字，当该数目和图象数据包括大于预定位数的多个位数时以第二种格式存储籽数的标引、位移(offset)和码字。

根据本发明的另一个方面，提供一种霍夫曼解码压缩数据的方法，该方法包括步骤：用多个测试标准的每一个测试一数据流的位来确定一个有效霍夫曼码的长度，将相应于该长度的多个位移的其中一个与该有效霍夫曼码相组合而形成一标引，和利用该标引访问霍夫曼表中的一个符号值。

                      附图说明

从下面参照附图对本发明优选实施例的详细描述将更好的理解前述和其它的目的、状况和优点，其中：

图1是根据JPEG标准的说明霍夫曼表规范语法的图，

图1A描述AC DCT系数或DC DCT系数差值的霍夫曼编码，

图2描述根据JPEG标准示范性的说明霍夫曼表规范和熵编码图象数据，

图3和4分别是适于亮度和色度DC DCT系数差值的典型的霍夫曼码表，

图5和5A是可用于实现本发明的另一个硬件实施例的示意表示图，

图6是可用于实现本发明的硬件实施例的一些其它细节的示意表示图，

图7是根据本发明计算比较值和霍夫曼表指针数据的优选形式的流程图，

图8是表示本发明解码包括霍夫曼编码R/S值的压缩数据的方法的流程图，

图9A、9B和9C是描述图8过程的优选特征的流程图，

图10说明可以迅速执行霍夫曼编码的压缩的中间数据格式，

图11是根据本发明编码器的方框图，

图12说明编码器表的初始值，和

图13说明图11一个部分的优选实现方式。

                      具体实施方式

现在参照附图，特别是参照图1，图1表示了根据JPEG标准的霍夫曼表的规范语法，该语法包含在上述参考的Pennebaker等的出版物的第393页上。示出的语法称为用于定义一个或多个霍夫曼编码表的标记段，此后这些霍夫曼编码表用于执行霍夫曼熵编码或解码。不论何时要改变新的参数或表值都使用相同的语法。标记段总是包含整数个字节(有时通过在该段的最后增加给定的逻辑值位而实现)，用于码分组的帧开始(SOF)和扫描开始(SOS)的标记段通常称为首部。

根据JPEG标准的标记段，如图1所示总是以两个字节代码开始，首先是字节对齐的十六进制″FF″字节，随后是规定该标记功能的非零字节，例如″FFDB″表示″定义量化表″(DQT)或″FFC4″表示″定义霍夫曼表″(DHT)。具体到用于″定义霍夫曼表″函数，后面的两个字节规定参数字段的长度，在标记段中记为L_h。下一个字节的前四位中的一位Tc规定紧接着下一个表的类型为DC或AC(″0″或″1″)，之后的四位Th规定该表的名称。每个DC和AC表可以允许直到四个表，标记段可用于定义或重新定义其中任意或所有的表。

接下来的十六个字节规定每个位长的码数，Li，它将包含在下一个表中以对应于JPEG标准所允许的最大位长(否则就是任意的)。作为一种符号约定，一位码的数目是L1，十六位码的数目是L16。不会表示所有的位长，特别是如果图像精度是八位，在量化生成至多十一位系数之后，所有图象数据中未表示的码长将编码为十六进制的″00″。下面的字节V_1，1到V_16，L16是对应于每个霍夫曼编码的实际值，顺序是各自出现的频率/概率(包括提供一个以上给定长度码的情况)。

如前所述，诸如霍夫曼编码之类的熵编码对出现频率或概率越大的数值分配的位越少，并且许多DCT系数是零。因此，JPEG标准提供八个霍夫曼编码表，每个表具有256个入口(并确保总是定义了特殊霍夫曼码与特殊DCT系数之间的变换)。为了加快该过程，查询表也可以提供到霍夫曼表V_i，j字段的标引，这可以减少查找一特定V_i，j值的操作次数，但需要额外的存储资源并为开发更多的表入口产生额外的计算负荷，如上面所提到的。

现在将结合图2示范性的霍夫曼表解释标记段语法的应用。简言之，应当理解压缩过程中的量化和离散余弦变换(DCT)的结果是光栅扫描顺序的一系列DCT系数。通过以Z字型顺序访问和进一步压缩(和包括熵编码的其他变换处理的加强)零值系数，零值的系数被大致分组，正如在上面所引入的和同时提交的相关申请所公开的，根据游程和尺寸(R/S)数据压缩数据来得到进一步的压缩。游程(run)是AC DCT系数的连续零值串的长度，尺寸是说明一非零DCT系数所必需的位数。游程或R值编码为字节中较高有效位的四位，尺寸或S值表示同一R/S字节中较低有效位的四位。

可以看出DC DCT系数差和AC DCT系数值并没有被R/S值所完全规定。但是，根据JPEG标准只编码R/S值并将正AC DCT系数或DC DCT差值的实际位和根据如图1A所示用于负AC DCT系数和DC DCT系数差值的适当规则改变的位级联或附加到每个码，足以包含所有的原始DCT系数信息，同时提供非常可观的数据压缩，这将在下面讨论，同时所有的细节都符合JPEG标准。

为了清楚，图2表示成右边对齐的十六列，因此两个字节的标记段伸到左边。每个字节由表示其两个单独的四位的两个十六进制编码的数字表示。

图2的第一个标记是表示图像开始(SOI)的“FFD8”。第二个标记是“FFDB”，表示量化表的规定。应当理解，量化的DCT系数值不需要表示固定尺寸值的一个范围，但是每个值可以表示尺寸不同于其他值的一个值的范围。此表是以对理解本发明并不重要的方式从分析原始图像的角度得出的，并将随后在重建图像期间用于“解量化”DCT系数。

第三个标记是“FFC4”，表示规定一个或多个霍夫曼表的标记段的开始。下面的两个字节“01A2”是418的十六进制码，它是下一个表示扫描开始(SOS)的标记“FFDA”之前的字节数，其中在分量数目的开始规定参数列表的长度(例如R、G或B，灰度、亮度/色度等，之后是示意表示成“…”的压缩数据)。

下一个字节包含两个四位，表示成Tc和Th并将该表定义为DC表0，因为两个四位都是零。因为这些都是DC表并且每个分组只提供一个DC DCT系数，所以没有游程长度并且每个字节的前四位是零，同时后四位规定每个尺寸的多余字节数(它是紧邻压缩数据流的多余字节数)。特定的码数对应于图3所示的霍夫曼码，只有12个，包括3位长的5个码。这12个值在后面12个字节中规定以结束DC表0。

此处，只用了29个字节(1个用于Tc、Th，16个用于L_i，12个用于V_i，j)，这比紧邻该标记之后规定的参数长度的418个字节少得多。因此下一个字节，在这种情况下即AC表0的两个四位定义在该标记段规定的第二霍夫曼表的类别和名称，因为Tc和Th值分别是1和0。接下来的16个字节是L_i值，表示每个长度的码数，再接下来的字节是V_i，j符号值，数目等于在L_i字节枚举的码的总和，最大值是64，V_i，j符号值用于为完成AC表0出现频率下降顺序的对应霍夫曼码。

418的其余部分包括两个表，DC表1和AC表1，以上述相同的格式描述和编码。DC表1的霍夫曼码在图4用表格示出。

比较图3和图4，可以看出霍夫曼码的多个特点。首先，如上所述，霍夫曼码长度可变，“类别”是位数或包含在上面讨论的和上述所结合的申请中的R/S字节中的尺寸或S值，并在例如图2的霍夫曼表中纪录为V_i，j值。第二，不允许位全部为“1”值的码。第三，允许给定长度的多个码，这些码的数目将小于该长度的码表示的值的数目。第四，对理解本发明最为重要的一点是，JPEG霍夫曼码被构成表示多级可被识别的值。在不允许任何码与长度更长的其他码的前缀相同的特点中，此约束或特性得以强调。

从前述的内容中可以回顾到霍夫曼表的结构允许特殊的霍夫曼码和分别分配给它用来重建的R/S值的对应关系。但是，正如上面所提到的，这种重建既复杂又耗时，而且使用查询表来标引霍夫曼表更普遍。由于霍夫曼码的长度可变和还必须识别对应一有效霍夫曼码的连续位数(16或更少)的事实，此过程变得复杂。

识别一有效霍夫曼码和标引到霍夫曼表中的已知方法是在压缩数据中取16个(相邻)连续位，和查询(在有2¹⁶入口的表中)该码中的位数，在另一个表(相似尺寸)中，查询相应于该码的R/S值。但是，这对存储空间而言是非常浪费的，同时引起大量的存储器负荷。例如，如果该码是一位码(在所检查的16个位的开始)，则每个表的一半对于位数会是“1”，并且对于该符号是同一个R/S值字节。其他已知的方法利用多个表并需要相应的更多次数的查询操作。

本发明利用了霍夫曼码的特点，即每个码都可以看成用于任何给定的二进制位数的数值，并且可以计算对于给定的位数来说太大的数值。如果n位的压缩数据逻辑上大于或等于该最大值(此后为max(n)，其中n是位数)，则另外一个位必须被检查并与max(n+1)进行比较。本发明还利用了一个事实，即就硬件结构来说，必须并行执行这些测试，因为所有的测试都必须通过(例如，对于一有效霍夫曼码来说逻辑值太大)直到认为是正确的位数，对更多的位数进行的其余测试都将失败。

例如，如图5所示，可以利用16个比较器并行执行该测试(图5表示成表达式C[0...n]≥max(n))，每个比较器有一到十六个输入连接到诸如筒形移位器之类的C-寄存器的连续各级。这些比较器应当是数字的并构成逻辑门阵列。

也就是说，第一次测试比较C-寄存器中当前最高有效位(MSB(C[0]))与一位值max(1)。如果没有一位码，max(1)＝0。如果有一位码(这个码必须是“0”，因为全“1”码是不允许的)，max(1)＝1。对于有几个码的第一个Ln来说，将是一个非零的max(n)，因为构造成max(n)的max(n)值是n位的第一个码，它是一个更长码字的前缀(例如，max(2)＝“10”，它是图3的类别5的前缀)。

图5A表示另一个实施例，其中越来越多的压缩数据位与max(n)值进行比较。n的值是确定成比较失败的第一个值(生成0)。

图6示出了与C-寄存器的n个最高有效位相级联的作为算术逻辑单元(ALU)的一个输入的先行零。另一个输入是预先计算的偏移(n)。在加法运算后，低阶的结果是到查询表(LUT)/霍夫曼表的标引(用于AC编码的8个位中用于DC差值的四个位)，它包含通过规定的霍夫曼表(DHT)的标记段的V_i，j符号值。该表的输出是R/S字节。

图7表示用于构造max(n)值的流程图。该方法还按照图2的DHT标记段的规定将位移构造成R/S字节，其中offset(0)是R/S列第一字节的标引(例如0)或到该列表的指针。从步骤71初始化max(n)和offset(n)开始，在步骤72中将i、max(0)和offset(0)设置成0，i被递增，并且位移被设置成最后的位移减max(i-1)。max(i)的值作为Li+max(i-1)计算。因此直到Li非零，offset(n)和max(n)将保持为零。因此图5或5A的前面的比较C[0...n]因为前面一位或多位的逻辑/数值总是大于或等于零而总是通过，直到遇到非零的Li(表示至少存在该长度的一个码)为止。当遇到非零(即“1”)的Li时，将它加到零将max(i)设置成第一码，即更大码的前缀，如步骤73所示。此过程在i＜16时重复，以便为所有的Ln产生所有可能的max(n)。因此，例如，如果有5个3位码(即0，1、2、3和4)，max(3)将设置成5，而且值5(二进制“101”)是一个可能的更长码的一部分，尽管如果没有更多码的话，这个码不一定必须使用。因此max(i)指向i位的第一个码，这个码太大(即，这个码的值大于i位的最大码)。如果L(i+1)不为空(即，有一个码大出1位)则这个码值是两倍的max(i)。i+1码在2*max(i)开始，随后被编号，并且max(i+1)是该序列之后的下一个数(即，2*max(i)+L(i+1))。如果L(i+1)＝0，则max(i+1)等于2*max(i)，并且在下一个非零Li之前可能有多个这样的加倍。

更概括的说，根据Li，max(i)和offset(i)如下进行计算：

(i＝0

(max(0)＝0

(offset(0)＝0

(i＝1

(max(1)＝Li+2*0

(offset(1)＝0-0＝0

(i＝2

(max(2)＝L₂+2*L₁

(offset(2)＝0-L₁

：

offset(i)用于确定对应于该码的解码值位于R/S值的列表的什么位置。即，如果i位的霍夫曼码加到offset(i)，得到的结果值将是在可以找到相应R/S字节的霍夫曼表中的地址。在本发明的上下文中提供了几个非常重要的优点。具体来说，多个查询表的功能，每个具有2¹⁶个入口的查询表将被限制为16个入口的max(n)和offset(n)值表替换，并且可以非常快速的计算和高效存储。因为此表是单一的并且很小，因此可以非常迅速的检索其中的数据以提供进入霍夫曼表的直接索引，来得到用于计算DCT系数和系数差值数据的R/S数据，这些数据与霍夫曼码一起包含在JPEG标准语法的数据流中(这可以用于其他的处理技术和其他类型的数据)。

概括的说，压缩数据的解码在图8中说明，它的优选特征将在下面结合图9讨论。当该过程在步骤81开始时，被解码的AC系数的数目k初始化为零，随后进入处理每个非零AC系数的循环。16位的压缩码串装载到C-寄存器(例如图5或5A)，通过并行或顺序比较而确定一有效霍夫曼码的位数n，如上述和步骤83所述。一旦知道n，相应的offset(n)也就知道了，计算(例如图6)到霍夫曼表地址的指针，c[0…n-1]+offset(n)，通过将R/S值向右移四位从霍夫曼表中的R/S字节提取S值，如步骤84所示。被压缩数据然后(向左)移n个位(相应于霍夫曼码的长度)以提供该数据流中的AC系数值，如步骤85所述。

为了以图10所示的格式表示该数据，通过使R/S值的位与十六进制0F字节相“与”可以从R/S值中去掉R，R/S字节被存储，并且S个多余位存储成两个另外的字节，压缩数据左移S个位，以便在C-寄存器的开始呈现下一个霍夫曼码，如步骤86所示。然后将k值递增R+1来解码下一个非零AC系数。为了完成压缩的数据格式，在步骤88测试R/S值，如果为零，则标明并存储分组结束(EOB)和长度字节，如步骤90所示，如果不为零，则在步骤89测试k的增加值，如果等于63，即一个分组中AC系数的最大值，则存储为零值的R/S值来表示已经存储了EOB和长度字节。如果k小于63，则该过程循环到步骤83来进一步处理AC系数。

图8过程的理想特性在图9中示出，本发明的此项特性根据例如图5或5A的硬件结构，将max(n)值压缩成5个xC_max<0…4>32位字，然后在寄存器中存储和操作，以避免需要访问多个存储器来得到用于比较的值。

max(n)值被紧密压缩成下面的字：

xC_max<0>max(1)，max(2)，max(3)，max(4)，max(5)，max(6)，max(7)，0000＝32位；

xC_max<1>＝max(8)，max(9)，max(10)，00000＝32位；

xC_max<2>＝max(11)，max(12)，max(10)，000000000＝32位；

xC_max<3>＝max(13)，max(14)，00000＝32位；和

xC_max<4>＝max(15)，max(16)，0＝32位。

这些值在执行图8的步骤83中如图9所示进行操作。具体来说，为了确定霍夫曼码中的位数n，n值初始化为1，并且寄存器或变量(Comp)装到压缩数据的下面32位。Comp与xC_max<0>最高有效位进行逻辑比较。如果它逻辑大于或等于该位，则该霍夫曼码不是1位，n递增到2。比较顺序将下一个max(n)值移到寄存器的最高有效位，并且将另一个位与comp值比较，对于每一次访问递增n。当比较结果Comp不再大于或等于该位时，则找到位数并且完成比较顺序。一些RISC(精简指令系统计算机)结构有一个拷贝到寄存器，屏蔽和移位指令的周期，假设n，comp和xC_max值在寄存器中，则需要三个周期确定n是否需要更大，和不需要存储访问。因此，比较测试操作可以非常快的执行，特别是因为较短的霍夫曼码比较长的码出现的更频繁。

因此，由上述根据本发明的解码器和解码过程的说明，可以看出在根据JPEG标准重建压缩的图像数据中，能显著增加速度和响应，基于同样的理由，大量降低了数据处理硬件和/或软件要求。在结合上述引用的同时提交的申请中所公开的压缩数据格式的编码处理中也提供了显著的优点。其中公开的中间数据格式在图10中示出。

图11表示将压缩的DCT分组编码成熵编码数据的流程图。首先在步骤1001中编码DC系数，然后进入循环1002。每执行一次循环就在步骤1003中编码R/S字节，根据S值在步骤1004中编码额外的位，并在步骤1005中存储两者。如果在步骤中1006发现EOB码，则该过程出现分支(对于当前方框)，在步骤1007中测试k以确定k是否等于63。如果是，则过程结束，因为k＝63表示可以提供的最大数目的值和不需要单独编码的EOB符号。如果k小于63，则在步骤1008中编码EOB和在步骤1009中存储以结束此过程。应当注意每个入口已经大致处于霍夫曼编码数据所需的形式，该过程可以用最快的速度轮流进行每个R/S和额外位对的编码直至达到EOB标记。

在编码过程中，R/S字节必须转换成霍夫曼码。图10的压缩数据格式特别有利于收集统计数据，由此霍夫曼码分配给R/S值。即，一次通过数据分组将允许对每个R/S值的出现次数和分配要传送的霍夫曼码和L_i值的赋值计数。在第二次通过该数据之前，所用的实际R/S值汇集用于传输，因为V_i，j符号值作为图1格式的一部分传输。因为每个霍夫曼码长度内的类别，n可以任意指定，而不是存储max(n)，定义seed(n)值用于长度n的第一霍夫曼码，它在数值上等于2*max(n-1)。

图12是初始化H_code、H_offset和H_seed表的流程图。开始的籽数(即，对于给定数目的位数值最小的第一码字)初始化为零。该码字中的位数(即，码字的长度)初始化为零。

之后，只要i小于16，i就递增1，籽数加倍并存储在H_seed(i)中。该码设置为籽数，然后籽数加上多个i位码，并且j初始化为0。

只要j小于码数L_i，R/S设置成定义霍夫曼表(DHT)标记段的下一个V_i，j符号值。如果该码中的位数小于6，位数和该码压缩成H_code(RS)，这个字节中的3个最高有效位设置成该码中的位数，低阶的5个位设置成该码。如果i大于5，则H_code(RS)设置成位数。然后H_offset(RS)设置成j，因为这是i位码的第j+1个码。对于两个路径，j和码都递增。

对于软件实现，H_seed表入口可能作为至少16个位的整数来实现，因为最长的籽数是16位。对于硬件，第n个入口仅需要是n个位，因为它是n位码的籽数。为了简化图12，H_seed表初始化为17个入口(0-16)。图13所示的流程图只可以使用第6到第16个入口。另外，硬件实施例可以利用此优点来减少可装载寄存器的数目。

每个DC和AC霍夫曼表都需要一组H_seed、H_code和H_offset表。幸运的是，对于这些基线的实现方式，DC H_code和H_offset表只需要12个入口，因为R＝0和S的最大值是11。对于更通常的实现方式，S的最大值是16，使得这些表有最多17个入口。

为了简单，H_code和H_offset表每个可能具有256个入口，因为可以使用大多数的R/S字节。这些表中的入口最多是一个字节。因此，不需要16位的码字入口加上更多的位来标明码字中的位数，一个小H_seed表用于更长的码字，而且只需要多余的一个字节计算该尺寸的最终码字。所有的短码(即，小于5位)都包含在H_code字节中。因为越频繁的符号具有越短的码，对存储器的单个字节访问对包含最通常的编码符号所需的所有内容。

图13提供图11的方框1003中的编码R/S的其他细节。临时的变量或寄存器tem设置成H_code(RS)的内容。n值设置成该字节的3个最高有效位。如果n是零，则n设置成tem并且通过H_seed(n)与H_offset(RS)相加产生该码。否则，码设置成tem的低5位。压缩数据左移n位，并且该码放入该n个低阶位。Comp如像连续的筒形移位器一样处理，并且输出32位字的过程为本领域技术人员所熟知。

在现有技术中，n和直到16位的位模式被存储直到256个R/S符号。但根据本发明，当n和该码字存储于总共8个位或更少时，它们存储在一个字节中。这允许大幅度的缩短霍夫曼表并且特别有利，因为遇到的大多数码都短到适用于该格式。由该字节的3个MSB位置的非零值表示使用此格式。

对于所有的更长位模式，仅一个长度指示被存储为S，高阶四位设置成0000以表示不同的格式。对于这些更长的码，长度用作对籽数的标引(即，一特定位长的第一码值)。然后从查询表中可以确定响应的位移(这适合一个字节，因为最大位移为255)，该位移加上籽数来生成码值。在编码和存储R/S值之后，编码额外的S位，最好通过移位使图10中间数据格式的每个AC系数值的两个字节长度可变。

从上面可以看出本发明使编码的数据处理效率提高，极大的提高了计算和标引霍夫曼表的表存储效率。这些优点是以完全符合JPEG标准的方式产生的，并应用于霍夫曼编码的所有应用。

虽然本发明是从JPEG标准的单个优选实施例描述的，但本领域技术人员可以理解本发明可以在所附权利要求书的精神和范围内进行改进来实现。例如这些快速编码和解码方法应用于从码长为上升顺序的码数构造的任何霍夫曼表。另外，本领域技术人员可以从上面本发明的描述中将上述的技术用于以下降顺序构造的霍夫曼表。

Claims (8)

1.一种霍夫曼编码符号的方法，包括步骤：

为表中的给定长度的码第一次出现定义籽数值；

存储码字的长度；

当所述长度和所述码字的位数小于或等于预定位数时以第一种格式存储所述长度和所述码字；和

当所述长度和所述码字包括大于所述预定位数的位数时以第二种格式存储到所述籽数的标引、位移和所述码字。

2.如权利要求1所述的方法，其特征在于所述符号是JPEG(联合图像专家组)R/S字节。

3.如权利要求1所述的方法，其特征在于所述码字表示压缩图像数据。

4.如权利要求3所述的方法，其特征在于所述压缩图像数据是JPEG压缩图像数据。

5.一种霍夫曼解码压缩数据的方法，包括步骤：

用多个测试标准的每一个测试数据流的位，确定一有效霍夫曼码的长度；

组合对应于所述长度的多个位移的一个与所述有效霍夫曼码来形成标引；和

用所述标引访问霍夫曼表中的符号值。

6.如权利要求5所述的方法，进一步包括步骤：

计算所述测试标准和所述多个霍夫曼表数据的位移。

7.如权利要求5所述的方法，其特征在于所述压缩数据是压缩图像数据。

8.如权利要求7所述的方法，其特征在于所述压缩图像数据是JPEG压缩图像数据。

Images