墨滴群集显式表示的二级图像压缩的制作方法
专利名称：墨滴群集显式表示的二级图像压缩的制作方法
技术领域：
本发明常与数字图像处理有关，尤其涉及对用墨滴群集显式表示的图像进行二级图像压缩的一种系统和方法。
背景技术：
随着计算机网络，因特网和数字存储方法的广泛扩展，计算机可用信息量已经明显增加。正由于信息量如此激增它已面临快速传输和有效存储的需求。数据压缩是一种便于有效传输和存储信息的技术。
数据压缩减少了表示信息所需的空间量，并能用于多种信息类型。包括图像、文本、音频和视频在内的数字信息的压缩要求总量是在不断增加。通常，标准计算机系统采用数据压缩；然而，其它采用数据压缩的技术，例如但不限于数字和卫星电视，还有单元/数字电话。
数据压缩的要求随着运用、传输和处理大信息量要求的增加而增加。虽然，存储器件容量已经大大增加，但信息要求还超出容量的提高。例如，一幅未经压缩的图片需要5兆字节空间，而同样一幅图片，经无损压缩后，只要2.5兆字节空间。这样，数据压缩有利于传输更大量的信息。即使用诸如宽带、对称数字用户环路(DSL)、和有线调制解调器因特网等来增加传输速率，非压缩信息还很容易达到传输极限。例如，一幅未压缩图像通过一条DSL线要用10分钟传输。但是，这幅图像经数据吞吐量为10倍增益的压缩后，只需要传输1分钟。
通常，有两种压缩，无损和有损的。无损压缩允许将压缩后的图像精确恢复到原始数据，而有损压缩后恢复的数据和原始数据不同。在这两种压缩模式之间存在着一种权衡，有损压缩相比无损压缩能给出较好的压缩率，因为在一定程度上，它能容忍对数据完整性的损害。当压缩关键文本时，可采用无损压缩，因为数据不能精确重建会大大影响文本的质量和可读性。有损压缩可用于图片或非关键文本，这时可接受一定量的、或不易感受到的破坏或噪声。
在数字文件处理中十分通用两级图像，因为它们有可能致密表示包含文本和图画的黑白文件。这种图像中，象元(象素)可看作来自一种二进制源(例如，白是“0”和黑是“1”)。因为他们经常包含许多白空间和重复的墨滴图像，有效编码这种图像的一种基本方法是用光栅顺序进行扫描，即从顶到底和从左到右，通过自适应算术编码(AC)对每个象素进行编码，用围绕在前已编码象素的一个小模板中的象素值构成的上下文来控制象素的状态(或几率表)。这种想法是最现代二级图像压缩系统的基础。
经常用老的CCITT(国际电报电话咨询委员会)标准T.4和T.6来传输传真图像，这些标准分别称为组3和组4。G3常用修正的霍夫曼(Huffman，简称MH)码编码图像(即，对黑或白象素流进行霍夫曼编码)，而G4用“修正修正读”(MMR)编码，MH和MMR不如上下文自适应AC有效，但是实现较为简便。这些时候，G3和G4进展到包含通过JBIG(联合二级图像组，亦称作T.82规则)编码。JBIG采用自适应模板的上下文自适应AC，和有效QM二进制算术编码器。JBIG-2标准将JBIG扩展成对文本和半色调数据匹配的模式以及对有损编码的软模式匹配(SPM)。JB2编码器亦基于SPM，但是用二进制编码的Z编码器。JBIG，JBIG-2和JB2相对G4，压缩性能有很大改进。
发明内容
为了对本发明某些方面有基本了解，下面对本发明作简单概述。概述并不是对本发明的广泛综述。不试图验证本发明的关键组元或描述本发明涉及的范围。唯一的目的是用简化形式给出本发明的一些概念，为以后较为详细的阐述作序。
本发明给出一种二级编码系统，它推广当前二级编码技术，通过优先假设-位图对应于很可能包含大量文本的扫描文件。扫描文件可能包含对黑象素群集的字符位图模式。为讨论起见，假设该文件背景相当地白，而文本相当地黑。但是，打算将本发明能用的任何合适的二级颜色表示都归入附属权利要求范围。
二级编码系统扫描一张位图(即，从左到右和从顶到底)。第一次找到一个墨滴群集，就把它追加到群集字典。然后，不是对该群集象素编码，而是对字典指针P和该群集在页上的位置坐标{X，Y}编码。下次在位图中再找到同样的群集，或相当接近的群集时，同样我们不对象素进行编码，而是对{P，X，Y}坐标编码。假如该群集包含足够的象素，则用一个类似二级编码器(BLC)的无损编码器对{P，X，Y}坐标编码比象素编码更为有效。BLC在题为“二级图像的自适应编码和解码”的美国专利申请中描述。该专利的客户号为No.MS158314.1。多页文件的压缩增益更高，因为所有页面可共享群集字典，故编码字典本身的总开销变得微不足道。
二级编码系统能用无损模式或有损模式操作。在无损模式中，如果位图中的一个群集处于字典群集的第一阀值量内，则发送{P，X，Y}数据和“群集残留”——实际群集和字典中群集之间的小差异。可以用无损二级编码器对该群集残留编码。在有损模式中，如果位图中的一个群集在字典群集的第二阀值量内，则对三位一组的{P，X，Y}进行编码；但不编码群集残留。
本发明的二级编码系统能生成文件，这些文件相比常规扫描仪(例如CCITT的G4标准)生成的要小得多。这样，该二级扫描系统对传输和/或存储应用的文件可以大大地压紧，例如用于数字图书馆和数字文件数据库。
按照本发明的一个方面，该二级编码系统可包括群集形状估算器，位图的群集组分估算，群集位置估算器，第一编码器，第二编码器，第三编码器和第四编码器。群集形状估算器分析与位图有关的连接组分信息(例如颜色，水平大小，垂直大小，水平位置和/或垂直位置)。群集形状估算器提取群集，并将它们至少存进形状总字典，形状页字典和非群集形状存储中的至少一个。
在有损模式中，群集形状估算器决定群集是否处于总字典群集的第二阀值量以内。在一个实例中，如果有群集处于第二阀值量以内，则要注意该群集在该页上的出现。在另一实例中，如果该群集处于第二阀值量以内，则注意到群集在页面上的出现，并至少部分根据该群集修改总字典中存储的群集。例如，群集形状估算器能完成对总字典中存的群集和产生总字典中存的修正群集的群集作加权平均，这在解码位图中生成相比于原始位图中更为清楚的文本。还在另一实例中，第一阀值(例如，无损模式用的)和第二阀值(即有损模式用的)大致相同。
形状总字典包含总群集。总群集是在当前位图(例如，页面)上不止一次出现的群集和/或作为同一文件的一部分已经处理过的群集。
形状页字典包含页级群集——在当前位图(例如，页)中只找到一次的群集。例如，群集形状估算器一旦已实质完成对当前位图(例如，页)的分析，就能发送由在当前位图(例如，页)上只出现一次的群集组成的部分形状页字典(例如，包含在编码文件中)。这些页字典中的索引(例如指针)不一定要编码，因为页字典是按群集在页上出现的顺序排序的，而按定义页级群集在该页上只出现一次。
形状页字典可存储在以前位图(例如，页)仅出现一次的群集，这样如果在随后的位图上找到极为相似群集的第二次出现，则将该群集存入形状总字典，而从页字典中移出。非群集形状存储是存非文本字符的太小(例如，小于第三阀值)或太大(例如，大于第四阀值)的连接组分，所以不作为群集为好。
位图的群集组分估算，它决定总字典中存储群集的字典位置。它可利用来自群集形状估算器的信息(例如，指针)。然后用第二编码器编码指针。因为群集是按页上位置存储，其索引(例如指针)形成一个类似文本串排序，在一个实例中，第二编码器能采用适合文本字符串的压缩算法(例如LZX编码)。
在无损模式中，位图估算器能决定群集残留。它能为第四编码器提供信息，用非群集形状存储进行编码。(例如，用无损二级编码)。
群集位置估算器利用连接组分信息决定总字典和/或页字典群集的页位置。这样，对于总字典和/或页字典中的一个群集，用连接组分信息以及总字典或页字典的一个字典条目性质来决定其页位置。然后用第一编码器对页位置编码。
在一个实例中，对同一行上群集的水平(X方向)间隙进行编码，因为群集是有规则地隔开，尤其是字之间。此外，对同一行，可计算出平均水平间隙，然后用基于平均水平间隙和实际水平间隙之差的间隙信息进行编码。
在另一实例中，计算平均垂直(Y方向)值。对一行的平均垂直值进行编码，随后对群集垂直值和平均垂直值之差进行编码。群集边框的底边看作和顶一样的许多沿底边排齐的罗马字母。结果，已知群集和平均之间的差变得很小。因为第一编码器以逐行为基准编码，所以能对每行的第一水平值(X方向)和平均Y值进行编码。
第一编码器对收自群集位置估算器的页位置编码。例如，第一编码器能用位平面编码。第二编码器对收自位图群集组分估算的字典位置编码(例如，LZX编码)。
第三编码器对页字典和/或总字典中的位图模式采用无损二级位图编码。第四编码器对非群集形状存储采用无损二级位图编码。
日益强调的“无纸办公”常意味着将文件从纸笺形式转换成电子形式。当用户采用常规技术扫描、存储和/或处理电子文件时生成的转换文件是一个大文件。例如，用许多扫描仪，扫描20页就很容易产生1兆字节数据。用户很难例如通过E-mail来发送扫描文件，其中造成大文件是一个问题。然而，采用了本发明的系统和/或方法的扫描仪能减小存储要求，例如，每200页扫描可小到1兆字节，因此50页的法律文件只产生一个250千字节的“.blc”文件，能很快通过E-mail传送。
再说，对一个清楚的文件，本发明的系统和/或方法相对普通G4格式的增益可能是10的倍数。对有噪声的文件，相对G4的压缩增益可能是5的倍数，而对一个非常短的文件(单页)为3的倍数。
本发明的另一方面提供二级编码系统，它还包括群集系统和/或激活检测系统。
群集系统确定和多个群集(例如，连接组分)相关的信息。例如，信息包括该多个群集(例如，连接组分)的宽度(例如，X大小)，高度(例如，Y大小)，颜色，水平位置(例如，绝对的和/或相对的)和/或垂直位置(例如，绝对的和/或相对的)等。
激活检测系统接收二级图像输入。例如，二级图像输入可能是从掩膜分隔器组分(未显示)或扫描图像(例如从文件扫描仪和/或传真机)收到的一个二进制掩膜。激活检测系统分析该二级图像的颤动/半色调和/或噪声。激活检测系统提供基于该二级图像输入的二级图像输出；只是带有缩减的颤动/半色调和/或噪声。
基于有颤动/半色调文件图像的二级图像通常具有大量在区域内或与区域相交的连接组分。此外，有噪声的二级图像很少有在区域内或与区域相交的连接组分。这样通过确定区域内或与区域相交的连接组分的量，激活检测系统能够检测出可能存在颤动/半色调和/或噪声的区域。
除了检测上述颤动，激活检测系统还适于检测出二级图像输入中的噪声。“噪声”是指无关的信息(例如，标记)，删除噪声将不会大大损害二级图像的完整性。移去二级图像输入中的噪声导致平滑图像所造成的数据压缩改善。有噪声的二级图像区域一般显示出相对小的连接性。例如，在一个白背景上只有一个连接杂散标记的区域也就只有一个连接组分。
本发明再一方面还提供了一种由二级编码系统、无损二级编码器和选择组分构成的可选二级编码系统。
无损二级编码器可采用无损二级编码技术。选择组分允许在采用无损二级编码器的无损二级编码和二级编码系统(例如，采用群集(无损或有损))之间进行选择。选择可以根据例如用户的爱好和/或该二级编码系统中的群集系统。
本发明的另一方面提供了一个由第一解码器、第二解码器、第三解码器、第四解码器、群集发生器和组合器组成的二级解码系统。
第一解码器至少将部分位流输入(例如，由相应编码器产生的)解码，并提供群集的页位置。第二解码器也将部分位流输入(例如，由相应编码器产生的)解码，并提供已解码的字典位置。第三解码器至少也将部分位流输入(例如，由相应编码器产生的)解码，并提供解码的形状总字典和/或解码的形状页字典。第四解码器至少也将部分位流输入(例如，由相应编码器产生的)解码，并提供非群集形状的存储。
群集发生器至少部分根据页位置、字典位置和总字典和页字典中的至少一个产生群集。组合器至少部分根据群集发生器产生的群集和/或非群集形状存储提供二级输出。
本发明的另一方面还提供一种用于文件图像应用大阵列的二级编码系统，它包括但不局限于有台式个人计算机、分段分层图像系统、影印机、文件扫描仪、光字符识别系统、个人数字辅助设备、传真机、数码相机、数码摄像机和/或视频游戏机等。
本发明的另一方面还提供完成二级编码、群集分析和二级解码的方法。还提供了一种计算机可读媒体，它包含二级编码系统用的计算机指令和二级解码系统用的计算机指令。还提供了在两台或多台计算机组分之间传输的数据包，这些计算机用于二级编码包含已编码的页位置的第一数据字段、包含已编码的字典位置的第二数据字段、包含已编码总字典和已编码页字典中至少一个的第三数据字段、和包含已编码的非群集形状存储的第四数据字段。
为了完成所述的和有关结局，用下列叙述和附图相结合地描述本发明的某些示例方面。然而，虽然已经指明了这些方面，但还有多种采用本发明原理的途径。本发明试图包含所有这些方面和其等价物。从下列详细描述，结合附图一起考虑，本发明的其他优点和新奇特点也就一目了然了。
图1是根据本发明一个方面的二级编码系统的框图。
图2是4连特性的示意图。
图3是8连特性的示意图。
图4是根据本发明一个方面的连接组分边框的示例。
图5是根据本发明一个方面的总字典数据结构的示例。
图6是根据本发明一个方面的二级编码系统的框图。
图7是根据本发明一个方面的可选二级编码系统的框图。
图8是根据本发明一个方面的二级解码系统的框图。
图9是根据本发明一个方面的二级编码方法的流程图。
图10是根据本发明的一个方面的二级编码方法的流程图。
图11是图10方法更详细的流程图。
图12是根据本发明的一个方面的群集分析方法的流程图。
图13是图12方法更详细的流程图。
图14是根据本发明的一个方面的二级解码方法的流程图。
图15是本发明运行操作环境示例。
具体实施例方式
现在参照附图来描述本发明，图中用类似的标号始终对应相应部分。在下列描述中，为解释起见，设定了许多特定细节，便于透彻了解本发明，但是很显然，没有这些特定细节，本发明亦可实现的。在其它实例中，为便于叙述本发明，用框图形式表明常用结构和器件。
正如本申请中，术语“计算机组分”指与计算机相关的实体，可以是硬件、硬件与软件的组合、软件、或执行软件。例如，计算机组分可能是但不限于在处理器上运行的一个进程、一台处理器、一个对象、一个可执行程序、一个执行链、一个程序和/或一台计算机。用示例方法，运行在服务器上的应用程序和该服务器都可是计算机组分。一个或多个计算机组分可常驻在一个进程和/或一个执行链中，一个组分可以局限于一台计算机和/或分布于两台或多台计算机。
参照图1，说明按照本发明一个方面的二级编码系统100。二级编码系统100包括群集形状估算器110、位图的群集组分估算120、群集位置估算器130、第一编码器140、第二编码器150、第三编码器160和第四编码器170。
二级编码系统100扩展了当前的二级编码技术，先假设位图对应于可能包含大量文本的扫描文件。扫描文件可能包含相应黑象素群集的字符位图模式。为讨论起见，假设文件的背景相当白，而文本是相当黑。但是，打算把适用于本发明的任何二级颜色表示都归入附录的权利要求。
二级编码系统100扫描一张位图(例如，从左到右和从顶到底)。第一次找到一个墨滴群集，把它追加到群集字典。然后，不对该群集中的象素编码，而是对字典指针P以及该群集在页上出现的位置坐标{X，Y}编码。下次在这位图上再找到相同群集或非常接近的群集时，同样不对象素编码，而对{P，X，Y}坐标编码。如果该群集包含足够多的象素，则用无损BLC对{P，X，Y}坐标编码比编码象素有效得多。对多页文件，压缩增益更高，因为所有页能共享群集字典，所以编码该字典本身的开销变得微不足道。
二级编码系统100可用无损模式或有损模式操作。在无损模式，如果位图中一个群集处于字典中群集的第一阀值量内，则发送{P，X，Y}和“群集残留”——实际群集和字典中群集之间的很小差异。用无损二级编码器对群集残留编码。在有损模式，如果位图中的群集处于字典的第二阀值量内，则对三位一体的{P，X.Y}编码，而不编码群集残留。
本发明的二级编码系统100能生成文件，这些文件例如要比常规扫描仪(例如，CCITT G4)生成的文件要小得多。这样，二级编码系统100能大大压紧如数字图书馆和数字文件数据库要发送和/或存储的文件。
群集形状估算器110分析与位图相关的连接组分信息。例如，连接组分信息可能包括其颜色、水平大小、垂直大小、水平位置和/或垂直位置。群集形状估算器110提取群集并将它存入形状总字典172、形状页字典174和非群集形状176存储中的至少一个。
简单参照图2，说明描绘4连特性的图200。4连特性仅识别处于四个主要罗盘方向的连接象素。图2说明4连特性，显示了周围有四个主要罗盘方向象素的一个象素。再转到图3，说明描绘8连特性的图300。图3说明8连特性是，显示了周围有8个主要方向象素的一个象素。连接组分既包括文本，还包括非文本标记。可意识到本发明的系统和方法能用于有一定程度连接的连接组分，并不限于4连或8连的连接组分。
转向图4，说明按本发明一个方面的连接组分边框实例400。通常边框400包括有X大小(宽度)和Y大小(高度)连接组分围成的矩形。
回到图1，在有损模式，群集形状估算器110可能决定一个群集是否处于总字典172的第二阈值是之内。在一个实施例中，形状接近度取决于候选形状和字典中形状的匹配，然后计数候选形状中象素值(黑或白)不同于字典形状的部分象素。在一个实例中，如果该群集处于第二阀值量内，注意到该页上出现群集。在另一实施例中，如果该群集处于第二阀值量内，则注意页上出现的群集，并至少部分根据该群集将总字典172中存的群集进行修正。例如，群集形状估算器110能对总字典172内存的群集及其修正群集作加权平均。这样在解码位图中能生成比原始位图更清楚的文本。
形状总字典172包括总群集。总群集是在当前位图(例如，页)中不至一次出现的群集和/或作为同一文件的一部分处理过的群集。参照图5，说明按照本发明的一个方面的总字典数据结构500的实例。总字典数据结构500的第一字段510存储数据结构500的索引，第二字段520存储宽度(例如，X大小)，第三字段530存储高度(例如Y大小)和第四字段540存储该总群集的位图。例如，X大小可能是连接组分的最大宽度，Y大小可能是该连接组分的最大高度。数据结构500可能包括许多总群集条目550。
数据结构500仅是一个实例，可以理解为有助于使用与主发明相关的二级编码，可用许多其它结构来组织和/或存储多种数据类型。任何这种适合的数据结构都企图归入附属权利要求范围。这种数据结构可存入计算机可读媒体中，包括但不限于存储器、磁盘和载波。
参照回图1，形状页字典174包括页级群集——在当前位图(例如，页)上只找到一次的群集。例如，一旦群集形状估算器110已经实质性地完成当前位图(例如，页)分析，则可发送包括在当前位图(例如，页)上只找到一次的群集组成的部分形状页字典174(例如，包括在编码文件中)。页字典174的索引(例如，指针)不一定要编码，因为页字典174按照群集在页面上出现的次序排序，以及按定义页级群集在该页上仅出现一次。
在一个实例中，每页有它自己的页字典174，它是在页处理后被编码的。相应地，前页字典174中的条目永远不移出，一旦页被处理完后，页字典174被编码，并且永远不被修正。
形状页字典174能存储前面位图(例如，页)上仅出现过一次的群集，所以在以后的位图上，如果能够找到十分相似群集的第二次出现，则把该群集存入总字典172，并移出页字典174。非群集形状存储176，存储非文本字符的太小(例如小于第三域值)或太大(例如大于第四域值)的连接组分，所以不作为群集为好。
这样，群集形状估算器110提取群集，并将群集存入形状总字典172、形状页字典174、非群集形状存储176中的至少一个。群集形状估算器110能给位图的群集组分估算120提供信息(例如，形状总字典172的指针)。
位图的群集组分估算120决定总字典中群集的字典指针。位图的群集组分估算除了群集的字典信息外，还能使用来自群集形状估算器110的信息(例如，指针)。然后用第二编码器150对指针编码。因为群集企图俘获文本字符，索引(例如，指针)企图构成类似字符串次序的映象，它很接近于文件中的文本字符串。因此，在一个实例中，第二编码器150可以采用适合于文本字符串的压缩算法，例如二级编码器150可采用LZX编码。
在无损模式，位图的群集组分估算120可以决定群集残留。位图的群集组分估算120可以向第四编码器170提供信息，然后用非群集形状存储176进行编码(例如，使用无损二级编码)。
群集位置估算器130利用连接组分信息决定总字典172和/或页字典174的群集的页位置。因此，对于总字典172和/或页字典174中的一个群集，用连接组分信息和总字典172或页字典174中一个字典条目的特性来决定它的页位置。然后用第一编码器140对页位置编码。因为群集已经按页位置分类，所以页位置趋于单调增加。这样，在一个实施例中，第一编码器140通过计算出位置差{例如，X当前-X以前和Y当前-Y以前}并用一个适合于假设为较小整数的熵编码器对该差值编码，从而对位置编码，该熵编码器例如是在题为“有限字母数据的无损自适应编码”的美国专利申请中描述的位-平面编码器，该专利的客户号为MS127658.1。
在一个实例中，因群集有规则地隔开，尤其是在字内部，所以对一行中群集间的水平(X方向)间隙编码。此外，对一行可算出平均水平间隙并用间隙信息，随后基于平均水平间隙和实际水平间隙之差进行编码。
在另一实例中，计算平均垂直(Y方向)值。对一行的平均垂直值进行编码，随后对一个群集，对群集垂直值和平均垂直值之差进行编码。群集边框的底边看作和顶一样的许多沿底边排齐的罗马字母。结果，已知群集和平均之差很小。由于第一编码器140以逐行为基础进行编码，所以对每行第一水平值(X方向)和平均Y值进行编码。
第一编码器140对来自群集位置估算器130的页位置编码。例如，第一编码器140可采用位平面编码。第二编码器150对来自位置群集组分估算120的字典位置进行编码(例如，LZX编码)。
第三编码器160对页字典和/或总字典中的位图模式编码，可用无损二级位图编码。第四编码器170对非群集形状存储编码，能采用无损二级位图编码。
虽然图1是说明二级编码系统100的框图，但是其中群集位置估算器120、位图的群集组分估算130、第一编码器140、第二编码器150、第三编码器160和/或第四编码器170，可按照它们的定义用一个或多个计算机组分来实施。因此，显然实施二级编码系统100、群集形状估算器110、群集位置估算器120、位图的群集组分估算130、第一编码器140、第二编码器150、第三编码器160和/或第四编码器170等计算机可执行组分可存储在计算机可读媒体上，包括但不限于ASIC(专用集成电路)、CD(致密磁盘)、DVD(数字视频磁盘)、ROM(只读存储器)、软盘、硬盘、EEPROM(电可擦只读可编程存储器)和符合本发明的记忆棒。
再回到图6，说明符合本发明一个方面的二级编码系统600。该二级编码系统600包括群集形状估算器110、位图的群集组分估算120、群集位置估算器130、第一编码器140、第二编码器150、第三编码器160和第四编码器170。该二级编码系统还包括群集系统610和/或激活检测系统620。
群集系统610确定与多个群集(例如连接组分)有关的信息。例如，该信息可包括多个群集(例如连接组分)的宽度(例如，X大小)、高度(例如，Y大小)、颜色、水平位置(例如，绝对的和/或相对的)。
激活检测系统620接收二级图像输入。例如，二级图像输入可以是从掩膜分隔器组分(未显示)接收到的二进制掩膜或扫描图像(例如，从文件扫描仪和/或传真机)。激活检测系统620分析颤动/半色调和/或噪声。激活检测系统620根据该二级图像输入给出二级图像输出；只是它带有缩减的颤动/半色调和/或噪声。
基于有颤动/半色调的文件图像的二级图像通常有大量在区域内或与区域相交的连接组分。此外，有噪声的二级图像很少有在区域内或与区域相交的连接组分。因此，激活检测系统可以根据连接组分的量检测出有颤动/半色调和/或噪声的区域。
除了检测出上述颤动外，激活检测系统620还适于检测出二级图像输入中的噪声。“噪声”指无关紧要的信息(例如，标记)，对它的删除不会实质性影响二级图像的完整性。二级图像输入中噪声的消除能够得到平滑图象所造成的数据压缩改善。二级图像中有噪声的区域通常会显示出相对小的连接性。例如，在白背景上仅包含一个连接杂散标记的区域，只会有一个连接组分。
显然，群集系统610和/或激活检测系统620可以按这里的定义用一个或多个计算机组分来实施。
参照图7，说明符合本发明一个方面的可选二级编码系统700。可选二级编码系统700包括二级编码系统600、无损二级编码器710和选择组分720。
无损二级编码器710可采用无损二级编码技术。例如无损二级编码器710可以采用不用算术编码的编码处理(BLC)，但其性能接近于诸如JBIG，JBIG-2和JB2等现代编码器的性能。通常，二级编码器(BLC)用两个基于上下文的自适应模块1)用低分辨率控制的自适应预测器，用来将原始象素明显地映像到预测错误的象素，和2)反向自适应运行长度赖斯(RLR)编码器，对预测错误象素编码。对通常用上下文相关率估算对象素预测和自适应熵编码控制的常用方法是相反的。出于简单，在许多应用中，BLC相对其它当前编码器，还是一种较好的选择。
二级图像压缩编码始于象素预测过程和错误发生预测过程。象素预测过程常承担基于四周象素来预测一个象素值(例如，是0或1)。更讲究些，通过计算上下文相关率估算作象素预测。上下文实质是四邻已编码象素，构成一个所谓模板的模式。本发明能采用任何标准模板。上下文可看作是光栅顺序的规定数量像素值的矢量列表。这些构成一个能唯一确定上下文二进制字。把该二进制字认作上下文索引。
用首先生成和初始化象素几率表来计算上下文相关率估算，这是对每个可能的上下文索引赋一个初始几率，较可取的是设初始几率为0.5(即，上下文相关象素是黑或白为等几率)，但在编码器和解码器之间要预防对几率值标称的四舍五入问题。较可取的是选择一个整数代表白象素的几率为100％。例如，在本发明的实施例中用数字“8”。这样，表示后述初始值的标称几率将是“4”。
对每个象素，按光栅顺序，用已编码象素模式确定上下文索引并从表中读出标称几率。如果几率是0.5或0.5以上(即，上例中标称几率是4)，则预测该象素为白，并赋相应二进制值(例如，象素值为“0”)。要注意，第一次遇到的上下文索引，预测总是白象素，因为开始对表中的每个上下文索引赋的标称几率是4。然后调整标称预测值。如果想被预测的象素是白，则提高一个预定量(例如，1)；相反认为被预测象素是黑，则降低一个预定量(例如，1)标称几率调整的结果如果它降到0以下，则截到0；如果它升过最大值，则标称几率为最大值-1。这样，几率随编码图像变化，并能预测象素位置，这被称作反向自适应象素预测。因为解码器能完成相同的几率估算调整，而不用将明显的上下文几率信息发送到解码器。
再计算预测错误。实际上对二级图像中每个象素或黑或白的预测象素值和实际象素比较，计算预测错误。这样，只要发送与错误预测有关的数据。在大多数情况，预测是正确的所以可做到数据是相当节省，以后会讲到解码器完成同样的预测处理，并得到包括错误的同样结果。因此，所有的解码器需要知道哪些预测象素值是错误的，这样在图像重建时，可改变它们从白到黑或从黑到白。具体用二进制技术计算预测错误，将图像中每个象素的实际值和它的预测值进行“或”逻辑运算。这样，如果实际象素值和预测值匹配(例如，都是‘0’或都是‘1”)，则给所谓预测错误图像中该象素位置赋“0”。但是，如果实际象素值和预测值不同，则给预测错误图像中的相应象素位置赋“1”。
二级图像编码的下一阶段包括使用一个上下文相关、反向自适应、运行长度赖斯(RLR)编码过程。因为发现预测值常常和实际值匹配，所以预测错误图像大部分是“0”。使得预测错误图像特别适合于进一步压缩，甚至允许有损信息发送。为了编码预测错误图像，比较喜欢用RLR编码技术。RLR编码器常是一个可变长度——可变长度熵编码器，其中连续运行的2k个零，用单个0构成的代码字表示；后续1的部分运行的r(r＜2k)个零，用一个1后面再跟r的k位二进制字表示组成的代码字表示。变量k定义为发送一个代码字以前在预测错误图像中零的最大运行长度。调整这个变量来控制编码操作的效率。较喜欢用的技术是用反向自适应调整k。该方法包括先选择一个k的初始值，然后根据是否发生一个“0”代码字或发生一个“1+k位二进制字”代码字来向上或向下调节增量。符合本发明的RLR编码技术还与前述上下文有关。具体说，建立给每个上下文索引赋k值的编码表。刷新编码表以反映在二级图像编码期间k值的变化，下面会进行解释。
前面提到的上下文有关，反向自适应RLR编码技术包括先初始化所述编码表，将每个与上下文索引相关的k值设为所述的初始值(例如，k＝2)。此外，将每个上下文赋给标为赖斯参数k’的k变量的标称版本。例如，单个标称因子乘上当前k值产生当前k’值，它比k值要大。
当对象素位置建立预测错误值时，目前的RLR编码器按照前述预测错误决定过程，确定该象素位置相关的上下文索引，然后从编码表中读出当前赋予该上下文索引的k值。在所考虑象素位置为图像中按光栅次序的第一个象素(即左上角的象素)的情况，用表中读出的相关k值计算运行长度，常等于2k，运行长度表示按光栅次序连贯的白象素的数目，为生成一个“0”代码字，它必须存在。当算出下一个预测错误值时，决定它是“1”还是“0”。如果是“0”，则确定该值是否处于已算出的运行长度的“中间”，还是表示运行长度的末尾。如果不代表运行末尾，则不产生代码字。如果该预测错误值表示运行末尾，则发送一个“0”代码字。当然，为了知道预测错误值是否表示当前运行长度的末尾，现在的RLR编码器必须保持跟踪已经遇到多少个“0”。常喜欢用在编码表中包括运行计数器的做法，具体说，每个上下文索引有单独的运行计数器。在一个实施例中，将运行计数器初始设置成算出的运行长度值，然后，每遇到前面讨论过的一个“0”，包括序列中的第一个，计数器减1。当计算器减到零，想要当前处理的预测错误值是当前运行长度的末尾。另一方面，在运行期间，遇到任意次的预测错误值为“1”，则现在的RLR编码器产生一个“1+k位二进制字”代码，其中k位二进制字表示在当前运行中先于“1”之前所遇到“0”的数目。用前述运行计数器很容易决定“0”的数目，只要运行开始时，将该象素位置相关的上下文索引给计数器赋值。一旦产生一个代码字，无论它是“0”，还是“1+k位二进制字”，正是用产生的下一预测错误值来启动另一次运行，与第一象素位置一样，确定与预测错误值的象素位置相关的上下文索引，并重复上述过程。
此外，实质上每产生一次代码字，则与形成代码字的运行相关的k值都被调整，常这样来实现，如果产生的代码字是“0”，则参数k增加一个预定量。相反，如果代码字不是“0”，则参数k减去一个预定量。预定量是可变的，可以与当前值k’有关。新的k值为新的k’值除前面提到的标称因子。然后将新的k’值替代以前的值存入编码表。按整数步长调整k’，有可能实现RLR参数k的细调整，对优化编码性能很有必要，当仅保持整数算术时，有必要允许解码器精确跟踪k调整步骤。
选择组分720允许在用无损二级编器710进行无损二级编码和二级编码系统(例如，采用群集(无损或有损))之间进行选择。例如，选择可根据用户喜好和/或二级编码系统600中的群集系统610。在一个实例中，群集系统610决定用无损二级编码系统作更有效处理并提供一个输出给选择组分720，用来选择无损二级编码器710。
例如，对手写记录或别的图形，群集系统610能决定群集比无损二级编码(例如，因为没有许多重复群集)更无效。相应地，选择组分720允许使用无损二级编码器710。
可预料，无损二级编码器710和/或选择组分720可按这里的定义，用一个或多个计算机组分来实施。
转向图8，说明符合本发明一个方面的二级解码系统800，该二级解码系统800包括第一解码器810、第二解码器820、第三解码器830、第四解码器840、群集发生器850和组合器860。
第一解码器810至少将部分位流输入(例如，相应编码器产生的)解码并提供群集的页位置864。在一个实例中，第一解码器810采用位-平面解码。
第二解码器820至少将部分位流输入(例如，相应编码器产生的)解码并提供解码的字典位置868。在一个实例中，第二解码器可采用LZX解码。
第三解码器830至少将部分位流输入(例如，相应编码器产生的)解码并提供解码形状总字典872和/或解码形状页字典876。例如，第三解码器可采用无损二级解码。
第四解码器840至少将部分位流输入(例如，相应编码器产生的)解码并产生非群集形状存储880。例如，第四解码器可采用无损二级解码。
群集发生器850至少部分根据页位置、字典位置和总字典和页字典中的至少一个来产生群集。
组合器860至少部分根据群集发生器850和/或非群集形状存储产生的群集提供一个二级输出。
回顾上述所示示范系统，参照图9、10、11、12、13和14，本发明的方法将更好地实现。为简化说明起见，将方法解释成一系列的框图。可理解，本发明并不限于框图的次序，按照本发明，某些框图可按不同次序或同在此显示和描述的其他框图并存。更有甚者，还要求有没画出的框图实施符合本发明的方法。
本发明可用普通计算机可执行指令的上下文来描述，诸如用一个或多个组分执行的程序模块。总之，程序模块包括能完成特殊任务或实现特殊抽象数据类型的子程序、程序、对象、数据结构等等。一般，程序模块的功能在多种环境可任意组合或分散。
转向图9，说明符合本发明一个方面的二级编码方法900。在910，执行群集分析。例如，能分析与位图有关的连接组合信息，(例如，用群集形状估算器110)。连接组分信息包括连接组分的颜色、水平大小、垂直大小、水平位置和/或垂直直位置。在914，提取群集。例如，可以把提取的群集存入总字典、页字典和非群集形状存储。
接着，在920，对非群集形状编码。例如，非群集形状可包括非文本字符的太小(例如，小于第三阀值)或太大(大于第四阈值)的连接组分，它们不作为群集为宜，可用无损二级编码对非群集形状编码。
在930，确定总字典指针。至少部分根据群集分析和/或连接组分信息来确定指针。在940，对指针编码。在一个实例中，因为群集已按页上的位置存储，采用适合文本字符串的压缩算法(例如，LZX编码)索引(例如，指针)倾向于形成一个与编码次序相关似的文字字符串。
在950，确定页位置，可以用连接组分信息确定总字典和/或页字典中群集的页位置。因此，对总字典和/或页字典中的一个群集，用连接组分信息以及总字典或页字典中字典条目特性来确定群集的页位置。在960，对页位置编码，例如，用位-平面编码。
在970，决定是否想用无损模式。如果970的决定是YES，则到980编码残留图像，到990继续处理。如果在970的决定是NO，则继续处理990。在990，编码页字典。在992，编码总字典(例如，用无损二级编码)。
参照图10和图11，说明完成符合本发明一个方面的二级编码方法1000。在1004，接收到群集的信息(例如，颜色、水平大小、垂直大小、水平位置和/或垂直位置)。
在1008，对该群集是否处于总字典中作决定。例如，在无损模式，可以根据该群集是否处于总字典中第一阀值量内来确定。另外，在有损模式，可根据该群集是否处于总字典中第二阀值量内来确定。
如果在1008的决定是YES，则继续处理1012，如果在1008的决定是NO，则到1016再决定该群集是否在页字典中。如果在1016的决定是NO，则到1020将该群集存入页字典并继续处理1012，如果在1016的决定是YES，则到1024，将该群集存入总字典。在1028，将该群集移出页字典并继续处理1012。
在1012，从位图中提取群集。接着到1032，决定该页上是否还有群集，如图在1032的决定是YES，则继续处理1004，如果在1032的决定是NO，则到1036对页字典编码。在1040，确定页上群集的总字典指针。在1044，对页上群集的总字典指针编码。接着到1048，对是否还有更多的页作决定。如果在1040的决定是YES，则继续处理1004。如果在1040的决定是NO，则到1052对总字典编码。
转到图12和图13，说明完成符合本发明一个方面的群集分析方法1200。在1024确定群集。在1208完成激活检测。在1212完成群集分析。在1216，对非群集形状编码。在1220确定总字典中的指针。在1224对指针编码。在1228确定页指针。在1232，对页指针编码。在1236，决定是否想用无损模式。如果在1236的决定是YES，则在1240编码残留图象并继续处理1244。如果在1236的决定是NO，则继续处理1244。在1244对页字典编码。在1248，对总字典编码。
参照图14，说明符合本发明一个方面的二级解码方法1400。在1410，解码页位置。在1420，解码字典位置。在1430，解码总字典。在1440，解码页字典。在1450，解码非群集形状。在1460，至少部分根据页位置、字典位置和总字典和/或页字典产生群集。在1470，组合产生的群集和非群集形状，例如形成一个二级图像。
显然，本发明的系统和/或方法能够用于压缩文本，手写体，图画，图片诸如此类的所有压缩系统。进一步还将认识到本发明的系统和/或方法还可用于包括，但不限于台式个人计算机、影印机、文件扫描仪、光字符识别系统、PDA、传真机、数码相机、数码摄像机、数字游戏机中的大阵列文件图像应用。
为了给本发明的多方面提供附加的上下文，企图用图15和以下的讨论给操作环境1510简单概括的描述，其中可以实施本发明的多个方面。当本发明用计算机可执行指令的一般上下文来描述时，诸如一个或多个计算机或者其他器件执行的程序模块，将认识到本发明也可以组合其他程序模块和/或作为硬件和软件的一个组合来实施。总之，然而程序模块包括完成特定任务或者实现特定数据类型的子程序、程序、对象、组分和数据结构等。操作环境1510只是合适的操作环境的一个实例，并不企图对本发明的使用和功能范围作任何限制。适合于本发明使用的其他熟知的计算机系统，环境和/或结构包括，但不限于个人计算机、手持或台式设备、多处理器系统、基于微处理器的系统、可编程用户电子设备、PC网络、小型计算机、大型计算机、包括上述系统或者设备的公布式计算环境等。
参照图15，说明实施本发明多个方面的示范性环境1510，其中包括计算机1512。计算机1512包括处理单元1514，系统存储器1516和系统总线1518。系统总线1518连接系统组件，系统组件包括但不限于连接到处理单元1514的系统存储器1516。处理单元1514可以是任一可用处理器。双微处理器或其他多处理器结构亦可用作处理单元1514。
系统总线1518可以是几种总线结构中的任何一种，包括存储器总线或存储器控制器、外围总线或外部总线、和/或采用任何一种可用总线结构的局部总线，可用总线结构包括但不限于15位总线、工业标准体系结构(ISA)、微信道体系结构(MSA)、扩展ISA(EISA)、智能驱动电子设备(IDE)、VESA局部总线(VLB)、外围部件内联(PCI)、通用串行总线、高级图形端口(AGP)、个人计算机存储卡国际联合总线(PCMCIA)和小型计算机系统接口(SCSI)。
系统存储器1516包括易失性存储器1520和非易失性存储器1522。包含在计算机1512各单元之间在诸如起动期间传送信息的基本子程序的基本输入/输出系统(BIOS)存在非易失存储器1522中。按照图示方式，但不限于此，非易失存储器1522可以包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除ROM(EEPROM)或闪存。易失存储器1520包括随机存取存储器(RAM)，它用作外高速缓冲存储器。按图示方式，但并不限于此，现用RAM有许多方式，诸如对称RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDR SDRAM)、增强型SDRAM(ESDRAM)、同步联接DRAM(SLDRAM)和直接拉姆总线RAM(DRRAM)。
计算机1512还包括可卸/不可卸、易失/非易失计算机存储媒体。图15示出例如磁盘存储器1524。磁盘存储器1524包括，但并不限于磁盘驱动器件、软盘驱动器、磁带驱动器、Jazz驱动器、Zip驱动器、LS-100驱动器、闪存卡或记忆棒。此外，磁盘存储器1524可包括单独的存储媒体或和别的存储媒体组合的存储媒体。别的存储媒体包括，但不限于诸如致密磁盘ROM器件(CD_ROM)的光盘驱动器、CD可记录驱动器(CD-R驱动器)、CD可重写驱动器(CD-RW驱动器)或数字多用磁盘ROM驱动器(DVD-ROM)。为便于磁盘存储器件1524和系统总线1518连接，通常用可卸或非可卸接口，如接口1526。
显然，图15描述了用作用户和合适操作环境1510的基本计算机资源之间中间体的软件。这种软件包括操作系统1528，操作系统1528可存在磁盘存储器1524中，用来控制和分配计算机系统1512的资源。系统应用程序1530通过存在系统存储器1516或存在磁盘存储1524上的程序模块1532和程序数据1534，由操作系统1528管理资源。显然，本发明可以用各种操作系统或操作系统组合来实施。
用户通过输入设备1536，将命令或信息输入计算机1512，输入设备1536包括，但不限于这些定点设备，诸如鼠标、跟踪球、输入笔、触模式小键盘、键盘、话筒、游戏棒、游戏板、卫星盘、扫描仪、TV调频卡、数码相机、数码摄像机、网络摄像机等等。这些和其他输入设备通过系统总线1518经接口1538连到处理单元1516，接口1538包括例如串行口、并行口、游戏口和多用串行总线(USB)，输出设备1540采用与输入设备1536同类的某些接口。这样，例如用USB接口给计算机1512提供输入和从计算机1512输出信息到输出设备1540，给出的输出适配器1542是说明某些输出设备1540，如在其它输出设备1540之间的监示器、扬声器和打印机需要特殊的适配器。输出适配器1542包括，按说明方式但并不限于，提供输出设备1540和系统总线1518之间多种连接的视频和音频卡，应注意到其他设备和/或设备系统都提供输入和输出功能，诸如远程计算机1544。
计算机1512采用逻辑连接连到一台或多台远程计算机，诸如远程计算机1544，就能在网络环境下操作。远程计算机1544可以是个人计算机、服务器、路由器、PC网络、工作站、基于微处理器的器具、同级设备或其他公用网节点等，通常包括相对计算机1512描述的许多或所有组元。简化起见，只用一个存储器存储设备1546和远程计算机1544连接。远程计算机1544在逻辑上通过网络接口1548跟计算机1512连接，在物理上是经由通讯连接1550连接。网络接口1548包括通讯网络，如局域网(LAN)和广域网(WAN)。LAN技术包括光纤分布式数据接口(FDDI)，同轴电缆分布数据接(CDDI)，以太网/IEEE1502.3和令牌环/IEEE1502.5等。WAN技术包括，但并不限于，点对点链路，电路开关网络，如综合业务数字网络(ISDN)和随后的变异，报文分组交换网络和数字用户环路(DSL)。
通讯连接1550是连接网络接口1548到总线1518所用的硬件/软件。图示计算机1512内部的通讯连接1550，也可是在计算机1512的外部。连接到网络接口1548所必需的硬件/软件包括，仅为示例，内部和外部技术诸如，包括正规电话类调制解调器，有线调制解码器和数字用户环路调制解调器等调制解调器，综合业务数字网络适配器和以太网卡。
以上描述包括了本发明的实例。当然，不可能描述本发明用的组分和方法的每个可想到的组合，但这方面的普通技术人员都可认识到本发明还可有许多进一步的组合和修正。相应地，本发明力图包罗归入所附权利要求的精神和范围的所有这种选择，修正和变动。不仅如此，本发明还力图将详细描述或权利要求中用的术语“包括”加以扩展。倾向类似术语“由……组成”。在权利要求中是被用作一个过渡字，随后加以解释。
权利要求
1.一种二级编码系统，其特征在于，它包括群集形状估算器，它分析与一个文件相关的连接组分信息，提取群集并将它们存进形状总字典、形状页字典和非群集形状存储中的至少一个；位图的群集组分估算，它决定群集在总字典中的存储位置；以及群集位置估算器，它决定总字典和页字典中至少一个的群集在文件上的页位置。
2.如权利要求1所述的二级编码系统，其特征在于，还包括对从所述群集位置估算器接收到的所述页位置进行编码的第一编码器。
3.如权利要求2所述的二级编码系统，其特征在于，还包括对从所述位图群集组分估算接收到的所述字典位置进行编码的第二编码器。
4.如权利要求3所述的二级编码系统，其特征在于，还包括对所述页字典和所述总字典中至少一个进行编码的第三编码器。
5.如权利要求4所述的二级编码系统，其特征在于，还包括对所述非群集形状存储进行编码的第四编码器。
6.如权利要求1所述的二级编码系统，其特征在于，所述连接组分信息包括所述连接组分的颜色、水平大小、垂直大小、水平位置和垂直位置中的至少一个。
7.如权利要求1所述的二级编码系统，其特征在于，所述页位置包括群集间的水平间隙。
8.如权利要求1所述的二级编码系统，其特征在于，所述页位置包括平均垂直位置。
9.如权利要求8所述的二级编码系统，其特征在于，所述页位置还包括所述平均垂直位置和群集的垂直位置之差。
10.如权利要求2所述的二级编码系统，其特征在于，所述第一编码器至少部分采用基于位平面编码。
11.如权利要求3所述的二级编码系统，其特征在于，所述第二编码器至少部分采用基于LZX编码。
12.如权利要求4所述的二级编码系统，其特征在于，所述第三编码器至少部分采用基于无损二级编码。
13.如权利要求5所述的二级编码系统，其特征在于，所述第四编码器至少部分采用基于无损二级编码。
14.如权利要求1所述的二级编码系统，其特征在于，所述群集形状估算器至少部分根据所述存储群集和某个群集的加权平均修正总字典中存储的群集。
15.如权利要求1所述的二级编码系统用于影印机。
16.如权利要求1所述的二级编码系统用于文件扫描仪。
17.如权利要求1所述的二级编码系统用于光字符识别系统。
18.如权利要求1所述的二级编码系统用于个人数字辅助设备。
19.如权利要求1所述的二级编码系统用于传真机。
20.如权利要求1所述的二级编码系统用于数码相机。
21.如权利要求1所述的二级编码系统用于数码摄像机。
22.如权利要求1所述的二级编码系统用于分段分层图像系统。
23.如权利要求1所述的二级编码系统用于视频游戏机。
24.如权利要求1所述的二级编码系统用于台式个人计算机。
25.一种二级编码系统，其特征在于，它包括群集系统，它确定与多个连接组分相关的信息；群集形状估算器，它分析与文件有关的连接组分信息，提取群集并将它们存入形状总字典、形状页字典和非群集形状存储中的至少一个；位图的群集组分估算，它决定总字典中存的群集的字典位置；以及群集位置估算器，它决定总字典和页字典中至少一个的群集在文件上的页位置。
26.如权利要求25所述的二级编码系统，其特征在于，还包括对从所述群集位置估算器接收到的所述页位置进行编码的第一编码器。
27.如权利要求26所述的二级编码系统，其特征在于，还包括对从所述位图群集组分估算接收到的所述字典位置进行编码的第二编码器。
28.如权利要求27所述的二级编码系统，其特征在于，还包括对所述页字典和所述总字典中至少一个进行编码的第三编码器。
29.如权利要求28所述的二级编码系统，其特征在于，还包括对所述非群集形状存储进行编码的第四编码器。
30.如权利要求25所述的二级编码系统，其特征在于，所述连接组分信息包括连接组分的水平大小、垂直大小、水平位置和垂直位置中的至少一个。
31.如权利要求25所述的二级编码系统，其特征在于，还包括激活检测系统，它根据二级图像输入提供二级图像输出，所述二级图像输出具有缩减的颤动/半色调和缩减的噪声中的至少一个。
32.如权利要求26所述的二级编码系统，其特征在于，所述第一编码器至少部分采用基于位平面编码。
33.如权利要求27所述的二级编码系统，其特征在于，所述第二编码器至少部分采用基于LZX编码。
34.如权利要求28所述的二级编码系统，其特征在于，所述第三编码器至少部分采用基于无损二级编码。
35.如权利要求29所述的二级编码系统，其特征在于，所述第四编码器至少部分采用基于无损二级编码。
36.一种二级解码系统，其特征在于，包括第一解码器，对至少部分位流解码，所述第一解码器解码页位置；第二解码器，对至少部分位流解码，所述第二解码器解码字典位置；第三解码器，对至少部分位流解码，所述第三解码器解码形状总字典和形状页字典；第四解码器，对至少部分位流解码，所述第四解码器解码非群集形状存储；群集发生器，它至少部分根据页位置、字典位置和所述总字典和所述页字典中的至少一个来产生群集；以及组合器，它至少部分根据所述产生的群集和所述非群集形状存储提供二级输出。
37.如权利要求36所述的二级解码系统，其特征在于，所述第一解码器至少部分采用基于位平面解码。
38.如权利要求36所述的二级解码系统，其特征在于，所述第二解码器至少部分采用基于LZX解码。
39.如权利要求36所述的二级解码系统，其特征在于，所述第三解码器至少部分采用基于无损二级解码。
40.如权利要求36所述的二级解码系统，其特征在于，所述第四解码器至少部分采用基于无损二级解码。
41.一种二级编码方法，其特征在于，包括以下步骤完成群集分析；编码非群集形状；确定总字典中的指针；以及编码所述指针。
42.如权利要求41所述的方法，其特征在于，还包括下列步骤中的至少一个确定群集的页位置；编码所述页位置；编码页字典；以及编码所述总字典。
43.如权利要求41所述的方法，其特征在于，还包括下列步骤中的至少一个编码残留图像；确定群集；以及完成激活检测。
44.如权利要求42所述的方法，其特征在于，完成群集分析的步骤包括下列步骤中的至少一个决定群集是否处于所述总字典中；如果所述群集不在所述总字典中，则决定所述群集是否处于所述页字典中；如果所述群集处于所述页字典中，则将所述群集存入所述总字典中；如果所述群集处于所述页字典中，则将所述群集移出所述总字典；如果所述群集不在所谓页字典中，则将所述群集存入所述页字典中；以及从位图提取所述群集。
45.一种二级解码方法，其特征在于，包括解码页位置；解码字典位置；解码总字典；以及至少部分根据所述页位置、所述字典位置和所述总字典产生群集，以提供二级输出。
46.如权利要求45所述的方法，其特征在于，还包括下列步骤中的至少一个解码页字典；解码非群集形状；组合所述群集和所述非群集形状，以提供所述二级输出。
47.一种在用于二级编码的两个或多个计算机组分之间传输的数据包，其特征在于，所述数据包包括包括已编码的页位置的第一数据字段；包括已编码的字典位置的第二数据字段；包括已编码的总字典和已编码的页字典中的至少一个的第三数据字段；以及包括已编码的非群集形状存储的第四数据字段。
48.一种存储二极编码系统的计算机可执行组分的计算机可读媒体，其特征在于，它包括群集形状估算器，分析与文件有关的连接组分信息，提取群集并将它们存入形状总字典、形状页字典和非群集形状存储中的至少一个；位图的群集组分估算，决定所述总字典中存的群集的字典位置；以及群集位置估算器，决定所述总字典和所述页字典中至少一个的群集在文件上的页位置。
49.如权利要求48所述的计算机可读媒体，其特征在于，还包括对从所述群集位置估算器接收到的所述页位置进行编码的第一编码器。
50.如权利要求49所述的计算机可读媒体，其特征在于，还包括对从所述位图群集组分估算接收到的所述字典位置进行编码的第二编码器。
51.如权利要求50所述的计算机可读媒体，其特征在于，还包括对所述页字典和所谓总字典中至少一个进行编码的第三编码器。
52.如权利要求51所述的计算机可读媒体，其特征在于，还包括对非群集形状存储进行编码的第四编码器。
53.一种存储二极解码系统的计算机可执行组分的计算机可读媒体，其特征在于，它包括解码至少部分位流的第一解码器，所述第一解码器解码页位置；解码至少部分位流的第二解码器，所述第二解码器解码字典位置；解码至少部分位流的第三解码器，所述第三解码器解码形状总字典和形状页字典；解码至少部分位流的第四解码器，所述第四解码器解码非群集形状存储；群集发生器，它至少部分根据所述页位置、字典位置和所述总字典和所述页字典中的至少一个来产生群集；以及组合器，它至少部分根据所述已产生的群集和所述非群集形状存储提供二级输出。
54.一种二级编码系统，其特征在于，包括至少部分根据与文件相关的连接组分信息分析群集形状的装置；提取群集并将它们存入形状总字典、形状页字典和非群集形状存储中的至少一个的装置；决定总字典中存储群集的字典位置的装置，以及决定所述总字典和所述页字典中至少一个的群集在文件上的页位置的装置。
55.如权利要求54所述的系统，其特征在于，还包括对所述页位置进行编码的装置。
56.如权利要求55所述的系统，其特征在于，还包括对所述字典位置进行编码的装置。
57.如权利要求56所述的系统，其特征在于，还包括对所述页字典和所述总字典中的至少一个进行编码的装置。
58.如权利要求57所述的系统，其特征在于，还包括对非群集形状存储进行编码的装置。
59.一种二级解码系统，其特征在于，包括对页位置进行解码的装置；对字典位置进行解码的装置；对形状总字典和形状页字典中至少一个进行解码的装置；对非群集形状存储进行解码的装置；至少部分根据所述页位置、所述字典位置和所述总字典和所述页字典中的至少一个产生群集的装置；以及将所述已产生的群集和所述非群集形状存储进行组合，以提供二级输出的装置。
全文摘要
对用墨滴群集显式表示的二级图像进行压缩的系统和方法。本发明包括群集形状估算器，它能分析连接组分信息，提取群集并将群集存入总字典、页字典或非群集形状存储中。位图的群集组分估算决定总字典中存储群集的字典位置，然后对字典位置编码。群集位置估算器决定总字典和/或页字典中群集的页位置，然后对页位置编码。再有，还对总字典、页字典和非群集形状存储进行编码。
文档编号G06T9/00GK1453724SQ0311030
公开日2003年11月5日 申请日期2003年4月2日 优先权日2002年4月25日
发明者E·L·伦肖, P·Y·希玛德, H·S·玛尔瓦 申请人:微软公司
技术领域：
本发明常与数字图像处理有关，尤其涉及对用墨滴群集显式表示的图像进行二级图像压缩的一种系统和方法。
背景技术：
随着计算机网络，因特网和数字存储方法的广泛扩展，计算机可用信息量已经明显增加。正由于信息量如此激增它已面临快速传输和有效存储的需求。数据压缩是一种便于有效传输和存储信息的技术。
数据压缩减少了表示信息所需的空间量，并能用于多种信息类型。包括图像、文本、音频和视频在内的数字信息的压缩要求总量是在不断增加。通常，标准计算机系统采用数据压缩；然而，其它采用数据压缩的技术，例如但不限于数字和卫星电视，还有单元/数字电话。
数据压缩的要求随着运用、传输和处理大信息量要求的增加而增加。虽然，存储器件容量已经大大增加，但信息要求还超出容量的提高。例如，一幅未经压缩的图片需要5兆字节空间，而同样一幅图片，经无损压缩后，只要2.5兆字节空间。这样，数据压缩有利于传输更大量的信息。即使用诸如宽带、对称数字用户环路(DSL)、和有线调制解调器因特网等来增加传输速率，非压缩信息还很容易达到传输极限。例如，一幅未压缩图像通过一条DSL线要用10分钟传输。但是，这幅图像经数据吞吐量为10倍增益的压缩后，只需要传输1分钟。
通常，有两种压缩，无损和有损的。无损压缩允许将压缩后的图像精确恢复到原始数据，而有损压缩后恢复的数据和原始数据不同。在这两种压缩模式之间存在着一种权衡，有损压缩相比无损压缩能给出较好的压缩率，因为在一定程度上，它能容忍对数据完整性的损害。当压缩关键文本时，可采用无损压缩，因为数据不能精确重建会大大影响文本的质量和可读性。有损压缩可用于图片或非关键文本，这时可接受一定量的、或不易感受到的破坏或噪声。
在数字文件处理中十分通用两级图像，因为它们有可能致密表示包含文本和图画的黑白文件。这种图像中，象元(象素)可看作来自一种二进制源(例如，白是“0”和黑是“1”)。因为他们经常包含许多白空间和重复的墨滴图像，有效编码这种图像的一种基本方法是用光栅顺序进行扫描，即从顶到底和从左到右，通过自适应算术编码(AC)对每个象素进行编码，用围绕在前已编码象素的一个小模板中的象素值构成的上下文来控制象素的状态(或几率表)。这种想法是最现代二级图像压缩系统的基础。
经常用老的CCITT(国际电报电话咨询委员会)标准T.4和T.6来传输传真图像，这些标准分别称为组3和组4。G3常用修正的霍夫曼(Huffman，简称MH)码编码图像(即，对黑或白象素流进行霍夫曼编码)，而G4用“修正修正读”(MMR)编码，MH和MMR不如上下文自适应AC有效，但是实现较为简便。这些时候，G3和G4进展到包含通过JBIG(联合二级图像组，亦称作T.82规则)编码。JBIG采用自适应模板的上下文自适应AC，和有效QM二进制算术编码器。JBIG-2标准将JBIG扩展成对文本和半色调数据匹配的模式以及对有损编码的软模式匹配(SPM)。JB2编码器亦基于SPM，但是用二进制编码的Z编码器。JBIG，JBIG-2和JB2相对G4，压缩性能有很大改进。
发明内容
为了对本发明某些方面有基本了解，下面对本发明作简单概述。概述并不是对本发明的广泛综述。不试图验证本发明的关键组元或描述本发明涉及的范围。唯一的目的是用简化形式给出本发明的一些概念，为以后较为详细的阐述作序。
本发明给出一种二级编码系统，它推广当前二级编码技术，通过优先假设-位图对应于很可能包含大量文本的扫描文件。扫描文件可能包含对黑象素群集的字符位图模式。为讨论起见，假设该文件背景相当地白，而文本相当地黑。但是，打算将本发明能用的任何合适的二级颜色表示都归入附属权利要求范围。
二级编码系统扫描一张位图(即，从左到右和从顶到底)。第一次找到一个墨滴群集，就把它追加到群集字典。然后，不是对该群集象素编码，而是对字典指针P和该群集在页上的位置坐标{X，Y}编码。下次在位图中再找到同样的群集，或相当接近的群集时，同样我们不对象素进行编码，而是对{P，X，Y}坐标编码。假如该群集包含足够的象素，则用一个类似二级编码器(BLC)的无损编码器对{P，X，Y}坐标编码比象素编码更为有效。BLC在题为“二级图像的自适应编码和解码”的美国专利申请中描述。该专利的客户号为No.MS158314.1。多页文件的压缩增益更高，因为所有页面可共享群集字典，故编码字典本身的总开销变得微不足道。
二级编码系统能用无损模式或有损模式操作。在无损模式中，如果位图中的一个群集处于字典群集的第一阀值量内，则发送{P，X，Y}数据和“群集残留”——实际群集和字典中群集之间的小差异。可以用无损二级编码器对该群集残留编码。在有损模式中，如果位图中的一个群集在字典群集的第二阀值量内，则对三位一组的{P，X，Y}进行编码；但不编码群集残留。
本发明的二级编码系统能生成文件，这些文件相比常规扫描仪(例如CCITT的G4标准)生成的要小得多。这样，该二级扫描系统对传输和/或存储应用的文件可以大大地压紧，例如用于数字图书馆和数字文件数据库。
按照本发明的一个方面，该二级编码系统可包括群集形状估算器，位图的群集组分估算，群集位置估算器，第一编码器，第二编码器，第三编码器和第四编码器。群集形状估算器分析与位图有关的连接组分信息(例如颜色，水平大小，垂直大小，水平位置和/或垂直位置)。群集形状估算器提取群集，并将它们至少存进形状总字典，形状页字典和非群集形状存储中的至少一个。
在有损模式中，群集形状估算器决定群集是否处于总字典群集的第二阀值量以内。在一个实例中，如果有群集处于第二阀值量以内，则要注意该群集在该页上的出现。在另一实例中，如果该群集处于第二阀值量以内，则注意到群集在页面上的出现，并至少部分根据该群集修改总字典中存储的群集。例如，群集形状估算器能完成对总字典中存的群集和产生总字典中存的修正群集的群集作加权平均，这在解码位图中生成相比于原始位图中更为清楚的文本。还在另一实例中，第一阀值(例如，无损模式用的)和第二阀值(即有损模式用的)大致相同。
形状总字典包含总群集。总群集是在当前位图(例如，页面)上不止一次出现的群集和/或作为同一文件的一部分已经处理过的群集。
形状页字典包含页级群集——在当前位图(例如，页)中只找到一次的群集。例如，群集形状估算器一旦已实质完成对当前位图(例如，页)的分析，就能发送由在当前位图(例如，页)上只出现一次的群集组成的部分形状页字典(例如，包含在编码文件中)。这些页字典中的索引(例如指针)不一定要编码，因为页字典是按群集在页上出现的顺序排序的，而按定义页级群集在该页上只出现一次。
形状页字典可存储在以前位图(例如，页)仅出现一次的群集，这样如果在随后的位图上找到极为相似群集的第二次出现，则将该群集存入形状总字典，而从页字典中移出。非群集形状存储是存非文本字符的太小(例如，小于第三阀值)或太大(例如，大于第四阀值)的连接组分，所以不作为群集为好。
位图的群集组分估算，它决定总字典中存储群集的字典位置。它可利用来自群集形状估算器的信息(例如，指针)。然后用第二编码器编码指针。因为群集是按页上位置存储，其索引(例如指针)形成一个类似文本串排序，在一个实例中，第二编码器能采用适合文本字符串的压缩算法(例如LZX编码)。
在无损模式中，位图估算器能决定群集残留。它能为第四编码器提供信息，用非群集形状存储进行编码。(例如，用无损二级编码)。
群集位置估算器利用连接组分信息决定总字典和/或页字典群集的页位置。这样，对于总字典和/或页字典中的一个群集，用连接组分信息以及总字典或页字典的一个字典条目性质来决定其页位置。然后用第一编码器对页位置编码。
在一个实例中，对同一行上群集的水平(X方向)间隙进行编码，因为群集是有规则地隔开，尤其是字之间。此外，对同一行，可计算出平均水平间隙，然后用基于平均水平间隙和实际水平间隙之差的间隙信息进行编码。
在另一实例中，计算平均垂直(Y方向)值。对一行的平均垂直值进行编码，随后对群集垂直值和平均垂直值之差进行编码。群集边框的底边看作和顶一样的许多沿底边排齐的罗马字母。结果，已知群集和平均之间的差变得很小。因为第一编码器以逐行为基准编码，所以能对每行的第一水平值(X方向)和平均Y值进行编码。
第一编码器对收自群集位置估算器的页位置编码。例如，第一编码器能用位平面编码。第二编码器对收自位图群集组分估算的字典位置编码(例如，LZX编码)。
第三编码器对页字典和/或总字典中的位图模式采用无损二级位图编码。第四编码器对非群集形状存储采用无损二级位图编码。
日益强调的“无纸办公”常意味着将文件从纸笺形式转换成电子形式。当用户采用常规技术扫描、存储和/或处理电子文件时生成的转换文件是一个大文件。例如，用许多扫描仪，扫描20页就很容易产生1兆字节数据。用户很难例如通过E-mail来发送扫描文件，其中造成大文件是一个问题。然而，采用了本发明的系统和/或方法的扫描仪能减小存储要求，例如，每200页扫描可小到1兆字节，因此50页的法律文件只产生一个250千字节的“.blc”文件，能很快通过E-mail传送。
再说，对一个清楚的文件，本发明的系统和/或方法相对普通G4格式的增益可能是10的倍数。对有噪声的文件，相对G4的压缩增益可能是5的倍数，而对一个非常短的文件(单页)为3的倍数。
本发明的另一方面提供二级编码系统，它还包括群集系统和/或激活检测系统。
群集系统确定和多个群集(例如，连接组分)相关的信息。例如，信息包括该多个群集(例如，连接组分)的宽度(例如，X大小)，高度(例如，Y大小)，颜色，水平位置(例如，绝对的和/或相对的)和/或垂直位置(例如，绝对的和/或相对的)等。
激活检测系统接收二级图像输入。例如，二级图像输入可能是从掩膜分隔器组分(未显示)或扫描图像(例如从文件扫描仪和/或传真机)收到的一个二进制掩膜。激活检测系统分析该二级图像的颤动/半色调和/或噪声。激活检测系统提供基于该二级图像输入的二级图像输出；只是带有缩减的颤动/半色调和/或噪声。
基于有颤动/半色调文件图像的二级图像通常具有大量在区域内或与区域相交的连接组分。此外，有噪声的二级图像很少有在区域内或与区域相交的连接组分。这样通过确定区域内或与区域相交的连接组分的量，激活检测系统能够检测出可能存在颤动/半色调和/或噪声的区域。
除了检测上述颤动，激活检测系统还适于检测出二级图像输入中的噪声。“噪声”是指无关的信息(例如，标记)，删除噪声将不会大大损害二级图像的完整性。移去二级图像输入中的噪声导致平滑图像所造成的数据压缩改善。有噪声的二级图像区域一般显示出相对小的连接性。例如，在一个白背景上只有一个连接杂散标记的区域也就只有一个连接组分。
本发明再一方面还提供了一种由二级编码系统、无损二级编码器和选择组分构成的可选二级编码系统。
无损二级编码器可采用无损二级编码技术。选择组分允许在采用无损二级编码器的无损二级编码和二级编码系统(例如，采用群集(无损或有损))之间进行选择。选择可以根据例如用户的爱好和/或该二级编码系统中的群集系统。
本发明的另一方面提供了一个由第一解码器、第二解码器、第三解码器、第四解码器、群集发生器和组合器组成的二级解码系统。
第一解码器至少将部分位流输入(例如，由相应编码器产生的)解码，并提供群集的页位置。第二解码器也将部分位流输入(例如，由相应编码器产生的)解码，并提供已解码的字典位置。第三解码器至少也将部分位流输入(例如，由相应编码器产生的)解码，并提供解码的形状总字典和/或解码的形状页字典。第四解码器至少也将部分位流输入(例如，由相应编码器产生的)解码，并提供非群集形状的存储。
群集发生器至少部分根据页位置、字典位置和总字典和页字典中的至少一个产生群集。组合器至少部分根据群集发生器产生的群集和/或非群集形状存储提供二级输出。
本发明的另一方面还提供一种用于文件图像应用大阵列的二级编码系统，它包括但不局限于有台式个人计算机、分段分层图像系统、影印机、文件扫描仪、光字符识别系统、个人数字辅助设备、传真机、数码相机、数码摄像机和/或视频游戏机等。
本发明的另一方面还提供完成二级编码、群集分析和二级解码的方法。还提供了一种计算机可读媒体，它包含二级编码系统用的计算机指令和二级解码系统用的计算机指令。还提供了在两台或多台计算机组分之间传输的数据包，这些计算机用于二级编码包含已编码的页位置的第一数据字段、包含已编码的字典位置的第二数据字段、包含已编码总字典和已编码页字典中至少一个的第三数据字段、和包含已编码的非群集形状存储的第四数据字段。
为了完成所述的和有关结局，用下列叙述和附图相结合地描述本发明的某些示例方面。然而，虽然已经指明了这些方面，但还有多种采用本发明原理的途径。本发明试图包含所有这些方面和其等价物。从下列详细描述，结合附图一起考虑，本发明的其他优点和新奇特点也就一目了然了。
图1是根据本发明一个方面的二级编码系统的框图。
图2是4连特性的示意图。
图3是8连特性的示意图。
图4是根据本发明一个方面的连接组分边框的示例。
图5是根据本发明一个方面的总字典数据结构的示例。
图6是根据本发明一个方面的二级编码系统的框图。
图7是根据本发明一个方面的可选二级编码系统的框图。
图8是根据本发明一个方面的二级解码系统的框图。
图9是根据本发明一个方面的二级编码方法的流程图。
图10是根据本发明的一个方面的二级编码方法的流程图。
图11是图10方法更详细的流程图。
图12是根据本发明的一个方面的群集分析方法的流程图。
图13是图12方法更详细的流程图。
图14是根据本发明的一个方面的二级解码方法的流程图。
图15是本发明运行操作环境示例。
具体实施例方式
现在参照附图来描述本发明，图中用类似的标号始终对应相应部分。在下列描述中，为解释起见，设定了许多特定细节，便于透彻了解本发明，但是很显然，没有这些特定细节，本发明亦可实现的。在其它实例中，为便于叙述本发明，用框图形式表明常用结构和器件。
正如本申请中，术语“计算机组分”指与计算机相关的实体，可以是硬件、硬件与软件的组合、软件、或执行软件。例如，计算机组分可能是但不限于在处理器上运行的一个进程、一台处理器、一个对象、一个可执行程序、一个执行链、一个程序和/或一台计算机。用示例方法，运行在服务器上的应用程序和该服务器都可是计算机组分。一个或多个计算机组分可常驻在一个进程和/或一个执行链中，一个组分可以局限于一台计算机和/或分布于两台或多台计算机。
参照图1，说明按照本发明一个方面的二级编码系统100。二级编码系统100包括群集形状估算器110、位图的群集组分估算120、群集位置估算器130、第一编码器140、第二编码器150、第三编码器160和第四编码器170。
二级编码系统100扩展了当前的二级编码技术，先假设位图对应于可能包含大量文本的扫描文件。扫描文件可能包含相应黑象素群集的字符位图模式。为讨论起见，假设文件的背景相当白，而文本是相当黑。但是，打算把适用于本发明的任何二级颜色表示都归入附录的权利要求。
二级编码系统100扫描一张位图(例如，从左到右和从顶到底)。第一次找到一个墨滴群集，把它追加到群集字典。然后，不对该群集中的象素编码，而是对字典指针P以及该群集在页上出现的位置坐标{X，Y}编码。下次在这位图上再找到相同群集或非常接近的群集时，同样不对象素编码，而对{P，X，Y}坐标编码。如果该群集包含足够多的象素，则用无损BLC对{P，X，Y}坐标编码比编码象素有效得多。对多页文件，压缩增益更高，因为所有页能共享群集字典，所以编码该字典本身的开销变得微不足道。
二级编码系统100可用无损模式或有损模式操作。在无损模式，如果位图中一个群集处于字典中群集的第一阀值量内，则发送{P，X，Y}和“群集残留”——实际群集和字典中群集之间的很小差异。用无损二级编码器对群集残留编码。在有损模式，如果位图中的群集处于字典的第二阀值量内，则对三位一体的{P，X.Y}编码，而不编码群集残留。
本发明的二级编码系统100能生成文件，这些文件例如要比常规扫描仪(例如，CCITT G4)生成的文件要小得多。这样，二级编码系统100能大大压紧如数字图书馆和数字文件数据库要发送和/或存储的文件。
群集形状估算器110分析与位图相关的连接组分信息。例如，连接组分信息可能包括其颜色、水平大小、垂直大小、水平位置和/或垂直位置。群集形状估算器110提取群集并将它存入形状总字典172、形状页字典174和非群集形状176存储中的至少一个。
简单参照图2，说明描绘4连特性的图200。4连特性仅识别处于四个主要罗盘方向的连接象素。图2说明4连特性，显示了周围有四个主要罗盘方向象素的一个象素。再转到图3，说明描绘8连特性的图300。图3说明8连特性是，显示了周围有8个主要方向象素的一个象素。连接组分既包括文本，还包括非文本标记。可意识到本发明的系统和方法能用于有一定程度连接的连接组分，并不限于4连或8连的连接组分。
转向图4，说明按本发明一个方面的连接组分边框实例400。通常边框400包括有X大小(宽度)和Y大小(高度)连接组分围成的矩形。
回到图1，在有损模式，群集形状估算器110可能决定一个群集是否处于总字典172的第二阈值是之内。在一个实施例中，形状接近度取决于候选形状和字典中形状的匹配，然后计数候选形状中象素值(黑或白)不同于字典形状的部分象素。在一个实例中，如果该群集处于第二阀值量内，注意到该页上出现群集。在另一实施例中，如果该群集处于第二阀值量内，则注意页上出现的群集，并至少部分根据该群集将总字典172中存的群集进行修正。例如，群集形状估算器110能对总字典172内存的群集及其修正群集作加权平均。这样在解码位图中能生成比原始位图更清楚的文本。
形状总字典172包括总群集。总群集是在当前位图(例如，页)中不至一次出现的群集和/或作为同一文件的一部分处理过的群集。参照图5，说明按照本发明的一个方面的总字典数据结构500的实例。总字典数据结构500的第一字段510存储数据结构500的索引，第二字段520存储宽度(例如，X大小)，第三字段530存储高度(例如Y大小)和第四字段540存储该总群集的位图。例如，X大小可能是连接组分的最大宽度，Y大小可能是该连接组分的最大高度。数据结构500可能包括许多总群集条目550。
数据结构500仅是一个实例，可以理解为有助于使用与主发明相关的二级编码，可用许多其它结构来组织和/或存储多种数据类型。任何这种适合的数据结构都企图归入附属权利要求范围。这种数据结构可存入计算机可读媒体中，包括但不限于存储器、磁盘和载波。
参照回图1，形状页字典174包括页级群集——在当前位图(例如，页)上只找到一次的群集。例如，一旦群集形状估算器110已经实质性地完成当前位图(例如，页)分析，则可发送包括在当前位图(例如，页)上只找到一次的群集组成的部分形状页字典174(例如，包括在编码文件中)。页字典174的索引(例如，指针)不一定要编码，因为页字典174按照群集在页面上出现的次序排序，以及按定义页级群集在该页上仅出现一次。
在一个实例中，每页有它自己的页字典174，它是在页处理后被编码的。相应地，前页字典174中的条目永远不移出，一旦页被处理完后，页字典174被编码，并且永远不被修正。
形状页字典174能存储前面位图(例如，页)上仅出现过一次的群集，所以在以后的位图上，如果能够找到十分相似群集的第二次出现，则把该群集存入总字典172，并移出页字典174。非群集形状存储176，存储非文本字符的太小(例如小于第三域值)或太大(例如大于第四域值)的连接组分，所以不作为群集为好。
这样，群集形状估算器110提取群集，并将群集存入形状总字典172、形状页字典174、非群集形状存储176中的至少一个。群集形状估算器110能给位图的群集组分估算120提供信息(例如，形状总字典172的指针)。
位图的群集组分估算120决定总字典中群集的字典指针。位图的群集组分估算除了群集的字典信息外，还能使用来自群集形状估算器110的信息(例如，指针)。然后用第二编码器150对指针编码。因为群集企图俘获文本字符，索引(例如，指针)企图构成类似字符串次序的映象，它很接近于文件中的文本字符串。因此，在一个实例中，第二编码器150可以采用适合于文本字符串的压缩算法，例如二级编码器150可采用LZX编码。
在无损模式，位图的群集组分估算120可以决定群集残留。位图的群集组分估算120可以向第四编码器170提供信息，然后用非群集形状存储176进行编码(例如，使用无损二级编码)。
群集位置估算器130利用连接组分信息决定总字典172和/或页字典174的群集的页位置。因此，对于总字典172和/或页字典174中的一个群集，用连接组分信息和总字典172或页字典174中一个字典条目的特性来决定它的页位置。然后用第一编码器140对页位置编码。因为群集已经按页位置分类，所以页位置趋于单调增加。这样，在一个实施例中，第一编码器140通过计算出位置差{例如，X当前-X以前和Y当前-Y以前}并用一个适合于假设为较小整数的熵编码器对该差值编码，从而对位置编码，该熵编码器例如是在题为“有限字母数据的无损自适应编码”的美国专利申请中描述的位-平面编码器，该专利的客户号为MS127658.1。
在一个实例中，因群集有规则地隔开，尤其是在字内部，所以对一行中群集间的水平(X方向)间隙编码。此外，对一行可算出平均水平间隙并用间隙信息，随后基于平均水平间隙和实际水平间隙之差进行编码。
在另一实例中，计算平均垂直(Y方向)值。对一行的平均垂直值进行编码，随后对一个群集，对群集垂直值和平均垂直值之差进行编码。群集边框的底边看作和顶一样的许多沿底边排齐的罗马字母。结果，已知群集和平均之差很小。由于第一编码器140以逐行为基础进行编码，所以对每行第一水平值(X方向)和平均Y值进行编码。
第一编码器140对来自群集位置估算器130的页位置编码。例如，第一编码器140可采用位平面编码。第二编码器150对来自位置群集组分估算120的字典位置进行编码(例如，LZX编码)。
第三编码器160对页字典和/或总字典中的位图模式编码，可用无损二级位图编码。第四编码器170对非群集形状存储编码，能采用无损二级位图编码。
虽然图1是说明二级编码系统100的框图，但是其中群集位置估算器120、位图的群集组分估算130、第一编码器140、第二编码器150、第三编码器160和/或第四编码器170，可按照它们的定义用一个或多个计算机组分来实施。因此，显然实施二级编码系统100、群集形状估算器110、群集位置估算器120、位图的群集组分估算130、第一编码器140、第二编码器150、第三编码器160和/或第四编码器170等计算机可执行组分可存储在计算机可读媒体上，包括但不限于ASIC(专用集成电路)、CD(致密磁盘)、DVD(数字视频磁盘)、ROM(只读存储器)、软盘、硬盘、EEPROM(电可擦只读可编程存储器)和符合本发明的记忆棒。
再回到图6，说明符合本发明一个方面的二级编码系统600。该二级编码系统600包括群集形状估算器110、位图的群集组分估算120、群集位置估算器130、第一编码器140、第二编码器150、第三编码器160和第四编码器170。该二级编码系统还包括群集系统610和/或激活检测系统620。
群集系统610确定与多个群集(例如连接组分)有关的信息。例如，该信息可包括多个群集(例如连接组分)的宽度(例如，X大小)、高度(例如，Y大小)、颜色、水平位置(例如，绝对的和/或相对的)。
激活检测系统620接收二级图像输入。例如，二级图像输入可以是从掩膜分隔器组分(未显示)接收到的二进制掩膜或扫描图像(例如，从文件扫描仪和/或传真机)。激活检测系统620分析颤动/半色调和/或噪声。激活检测系统620根据该二级图像输入给出二级图像输出；只是它带有缩减的颤动/半色调和/或噪声。
基于有颤动/半色调的文件图像的二级图像通常有大量在区域内或与区域相交的连接组分。此外，有噪声的二级图像很少有在区域内或与区域相交的连接组分。因此，激活检测系统可以根据连接组分的量检测出有颤动/半色调和/或噪声的区域。
除了检测出上述颤动外，激活检测系统620还适于检测出二级图像输入中的噪声。“噪声”指无关紧要的信息(例如，标记)，对它的删除不会实质性影响二级图像的完整性。二级图像输入中噪声的消除能够得到平滑图象所造成的数据压缩改善。二级图像中有噪声的区域通常会显示出相对小的连接性。例如，在白背景上仅包含一个连接杂散标记的区域，只会有一个连接组分。
显然，群集系统610和/或激活检测系统620可以按这里的定义用一个或多个计算机组分来实施。
参照图7，说明符合本发明一个方面的可选二级编码系统700。可选二级编码系统700包括二级编码系统600、无损二级编码器710和选择组分720。
无损二级编码器710可采用无损二级编码技术。例如无损二级编码器710可以采用不用算术编码的编码处理(BLC)，但其性能接近于诸如JBIG，JBIG-2和JB2等现代编码器的性能。通常，二级编码器(BLC)用两个基于上下文的自适应模块1)用低分辨率控制的自适应预测器，用来将原始象素明显地映像到预测错误的象素，和2)反向自适应运行长度赖斯(RLR)编码器，对预测错误象素编码。对通常用上下文相关率估算对象素预测和自适应熵编码控制的常用方法是相反的。出于简单，在许多应用中，BLC相对其它当前编码器，还是一种较好的选择。
二级图像压缩编码始于象素预测过程和错误发生预测过程。象素预测过程常承担基于四周象素来预测一个象素值(例如，是0或1)。更讲究些，通过计算上下文相关率估算作象素预测。上下文实质是四邻已编码象素，构成一个所谓模板的模式。本发明能采用任何标准模板。上下文可看作是光栅顺序的规定数量像素值的矢量列表。这些构成一个能唯一确定上下文二进制字。把该二进制字认作上下文索引。
用首先生成和初始化象素几率表来计算上下文相关率估算，这是对每个可能的上下文索引赋一个初始几率，较可取的是设初始几率为0.5(即，上下文相关象素是黑或白为等几率)，但在编码器和解码器之间要预防对几率值标称的四舍五入问题。较可取的是选择一个整数代表白象素的几率为100％。例如，在本发明的实施例中用数字“8”。这样，表示后述初始值的标称几率将是“4”。
对每个象素，按光栅顺序，用已编码象素模式确定上下文索引并从表中读出标称几率。如果几率是0.5或0.5以上(即，上例中标称几率是4)，则预测该象素为白，并赋相应二进制值(例如，象素值为“0”)。要注意，第一次遇到的上下文索引，预测总是白象素，因为开始对表中的每个上下文索引赋的标称几率是4。然后调整标称预测值。如果想被预测的象素是白，则提高一个预定量(例如，1)；相反认为被预测象素是黑，则降低一个预定量(例如，1)标称几率调整的结果如果它降到0以下，则截到0；如果它升过最大值，则标称几率为最大值-1。这样，几率随编码图像变化，并能预测象素位置，这被称作反向自适应象素预测。因为解码器能完成相同的几率估算调整，而不用将明显的上下文几率信息发送到解码器。
再计算预测错误。实际上对二级图像中每个象素或黑或白的预测象素值和实际象素比较，计算预测错误。这样，只要发送与错误预测有关的数据。在大多数情况，预测是正确的所以可做到数据是相当节省，以后会讲到解码器完成同样的预测处理，并得到包括错误的同样结果。因此，所有的解码器需要知道哪些预测象素值是错误的，这样在图像重建时，可改变它们从白到黑或从黑到白。具体用二进制技术计算预测错误，将图像中每个象素的实际值和它的预测值进行“或”逻辑运算。这样，如果实际象素值和预测值匹配(例如，都是‘0’或都是‘1”)，则给所谓预测错误图像中该象素位置赋“0”。但是，如果实际象素值和预测值不同，则给预测错误图像中的相应象素位置赋“1”。
二级图像编码的下一阶段包括使用一个上下文相关、反向自适应、运行长度赖斯(RLR)编码过程。因为发现预测值常常和实际值匹配，所以预测错误图像大部分是“0”。使得预测错误图像特别适合于进一步压缩，甚至允许有损信息发送。为了编码预测错误图像，比较喜欢用RLR编码技术。RLR编码器常是一个可变长度——可变长度熵编码器，其中连续运行的2k个零，用单个0构成的代码字表示；后续1的部分运行的r(r＜2k)个零，用一个1后面再跟r的k位二进制字表示组成的代码字表示。变量k定义为发送一个代码字以前在预测错误图像中零的最大运行长度。调整这个变量来控制编码操作的效率。较喜欢用的技术是用反向自适应调整k。该方法包括先选择一个k的初始值，然后根据是否发生一个“0”代码字或发生一个“1+k位二进制字”代码字来向上或向下调节增量。符合本发明的RLR编码技术还与前述上下文有关。具体说，建立给每个上下文索引赋k值的编码表。刷新编码表以反映在二级图像编码期间k值的变化，下面会进行解释。
前面提到的上下文有关，反向自适应RLR编码技术包括先初始化所述编码表，将每个与上下文索引相关的k值设为所述的初始值(例如，k＝2)。此外，将每个上下文赋给标为赖斯参数k’的k变量的标称版本。例如，单个标称因子乘上当前k值产生当前k’值，它比k值要大。
当对象素位置建立预测错误值时，目前的RLR编码器按照前述预测错误决定过程，确定该象素位置相关的上下文索引，然后从编码表中读出当前赋予该上下文索引的k值。在所考虑象素位置为图像中按光栅次序的第一个象素(即左上角的象素)的情况，用表中读出的相关k值计算运行长度，常等于2k，运行长度表示按光栅次序连贯的白象素的数目，为生成一个“0”代码字，它必须存在。当算出下一个预测错误值时，决定它是“1”还是“0”。如果是“0”，则确定该值是否处于已算出的运行长度的“中间”，还是表示运行长度的末尾。如果不代表运行末尾，则不产生代码字。如果该预测错误值表示运行末尾，则发送一个“0”代码字。当然，为了知道预测错误值是否表示当前运行长度的末尾，现在的RLR编码器必须保持跟踪已经遇到多少个“0”。常喜欢用在编码表中包括运行计数器的做法，具体说，每个上下文索引有单独的运行计数器。在一个实施例中，将运行计数器初始设置成算出的运行长度值，然后，每遇到前面讨论过的一个“0”，包括序列中的第一个，计数器减1。当计算器减到零，想要当前处理的预测错误值是当前运行长度的末尾。另一方面，在运行期间，遇到任意次的预测错误值为“1”，则现在的RLR编码器产生一个“1+k位二进制字”代码，其中k位二进制字表示在当前运行中先于“1”之前所遇到“0”的数目。用前述运行计数器很容易决定“0”的数目，只要运行开始时，将该象素位置相关的上下文索引给计数器赋值。一旦产生一个代码字，无论它是“0”，还是“1+k位二进制字”，正是用产生的下一预测错误值来启动另一次运行，与第一象素位置一样，确定与预测错误值的象素位置相关的上下文索引，并重复上述过程。
此外，实质上每产生一次代码字，则与形成代码字的运行相关的k值都被调整，常这样来实现，如果产生的代码字是“0”，则参数k增加一个预定量。相反，如果代码字不是“0”，则参数k减去一个预定量。预定量是可变的，可以与当前值k’有关。新的k值为新的k’值除前面提到的标称因子。然后将新的k’值替代以前的值存入编码表。按整数步长调整k’，有可能实现RLR参数k的细调整，对优化编码性能很有必要，当仅保持整数算术时，有必要允许解码器精确跟踪k调整步骤。
选择组分720允许在用无损二级编器710进行无损二级编码和二级编码系统(例如，采用群集(无损或有损))之间进行选择。例如，选择可根据用户喜好和/或二级编码系统600中的群集系统610。在一个实例中，群集系统610决定用无损二级编码系统作更有效处理并提供一个输出给选择组分720，用来选择无损二级编码器710。
例如，对手写记录或别的图形，群集系统610能决定群集比无损二级编码(例如，因为没有许多重复群集)更无效。相应地，选择组分720允许使用无损二级编码器710。
可预料，无损二级编码器710和/或选择组分720可按这里的定义，用一个或多个计算机组分来实施。
转向图8，说明符合本发明一个方面的二级解码系统800，该二级解码系统800包括第一解码器810、第二解码器820、第三解码器830、第四解码器840、群集发生器850和组合器860。
第一解码器810至少将部分位流输入(例如，相应编码器产生的)解码并提供群集的页位置864。在一个实例中，第一解码器810采用位-平面解码。
第二解码器820至少将部分位流输入(例如，相应编码器产生的)解码并提供解码的字典位置868。在一个实例中，第二解码器可采用LZX解码。
第三解码器830至少将部分位流输入(例如，相应编码器产生的)解码并提供解码形状总字典872和/或解码形状页字典876。例如，第三解码器可采用无损二级解码。
第四解码器840至少将部分位流输入(例如，相应编码器产生的)解码并产生非群集形状存储880。例如，第四解码器可采用无损二级解码。
群集发生器850至少部分根据页位置、字典位置和总字典和页字典中的至少一个来产生群集。
组合器860至少部分根据群集发生器850和/或非群集形状存储产生的群集提供一个二级输出。
回顾上述所示示范系统，参照图9、10、11、12、13和14，本发明的方法将更好地实现。为简化说明起见，将方法解释成一系列的框图。可理解，本发明并不限于框图的次序，按照本发明，某些框图可按不同次序或同在此显示和描述的其他框图并存。更有甚者，还要求有没画出的框图实施符合本发明的方法。
本发明可用普通计算机可执行指令的上下文来描述，诸如用一个或多个组分执行的程序模块。总之，程序模块包括能完成特殊任务或实现特殊抽象数据类型的子程序、程序、对象、数据结构等等。一般，程序模块的功能在多种环境可任意组合或分散。
转向图9，说明符合本发明一个方面的二级编码方法900。在910，执行群集分析。例如，能分析与位图有关的连接组合信息，(例如，用群集形状估算器110)。连接组分信息包括连接组分的颜色、水平大小、垂直大小、水平位置和/或垂直直位置。在914，提取群集。例如，可以把提取的群集存入总字典、页字典和非群集形状存储。
接着，在920，对非群集形状编码。例如，非群集形状可包括非文本字符的太小(例如，小于第三阀值)或太大(大于第四阈值)的连接组分，它们不作为群集为宜，可用无损二级编码对非群集形状编码。
在930，确定总字典指针。至少部分根据群集分析和/或连接组分信息来确定指针。在940，对指针编码。在一个实例中，因为群集已按页上的位置存储，采用适合文本字符串的压缩算法(例如，LZX编码)索引(例如，指针)倾向于形成一个与编码次序相关似的文字字符串。
在950，确定页位置，可以用连接组分信息确定总字典和/或页字典中群集的页位置。因此，对总字典和/或页字典中的一个群集，用连接组分信息以及总字典或页字典中字典条目特性来确定群集的页位置。在960，对页位置编码，例如，用位-平面编码。
在970，决定是否想用无损模式。如果970的决定是YES，则到980编码残留图像，到990继续处理。如果在970的决定是NO，则继续处理990。在990，编码页字典。在992，编码总字典(例如，用无损二级编码)。
参照图10和图11，说明完成符合本发明一个方面的二级编码方法1000。在1004，接收到群集的信息(例如，颜色、水平大小、垂直大小、水平位置和/或垂直位置)。
在1008，对该群集是否处于总字典中作决定。例如，在无损模式，可以根据该群集是否处于总字典中第一阀值量内来确定。另外，在有损模式，可根据该群集是否处于总字典中第二阀值量内来确定。
如果在1008的决定是YES，则继续处理1012，如果在1008的决定是NO，则到1016再决定该群集是否在页字典中。如果在1016的决定是NO，则到1020将该群集存入页字典并继续处理1012，如果在1016的决定是YES，则到1024，将该群集存入总字典。在1028，将该群集移出页字典并继续处理1012。
在1012，从位图中提取群集。接着到1032，决定该页上是否还有群集，如图在1032的决定是YES，则继续处理1004，如果在1032的决定是NO，则到1036对页字典编码。在1040，确定页上群集的总字典指针。在1044，对页上群集的总字典指针编码。接着到1048，对是否还有更多的页作决定。如果在1040的决定是YES，则继续处理1004。如果在1040的决定是NO，则到1052对总字典编码。
转到图12和图13，说明完成符合本发明一个方面的群集分析方法1200。在1024确定群集。在1208完成激活检测。在1212完成群集分析。在1216，对非群集形状编码。在1220确定总字典中的指针。在1224对指针编码。在1228确定页指针。在1232，对页指针编码。在1236，决定是否想用无损模式。如果在1236的决定是YES，则在1240编码残留图象并继续处理1244。如果在1236的决定是NO，则继续处理1244。在1244对页字典编码。在1248，对总字典编码。
参照图14，说明符合本发明一个方面的二级解码方法1400。在1410，解码页位置。在1420，解码字典位置。在1430，解码总字典。在1440，解码页字典。在1450，解码非群集形状。在1460，至少部分根据页位置、字典位置和总字典和/或页字典产生群集。在1470，组合产生的群集和非群集形状，例如形成一个二级图像。
显然，本发明的系统和/或方法能够用于压缩文本，手写体，图画，图片诸如此类的所有压缩系统。进一步还将认识到本发明的系统和/或方法还可用于包括，但不限于台式个人计算机、影印机、文件扫描仪、光字符识别系统、PDA、传真机、数码相机、数码摄像机、数字游戏机中的大阵列文件图像应用。
为了给本发明的多方面提供附加的上下文，企图用图15和以下的讨论给操作环境1510简单概括的描述，其中可以实施本发明的多个方面。当本发明用计算机可执行指令的一般上下文来描述时，诸如一个或多个计算机或者其他器件执行的程序模块，将认识到本发明也可以组合其他程序模块和/或作为硬件和软件的一个组合来实施。总之，然而程序模块包括完成特定任务或者实现特定数据类型的子程序、程序、对象、组分和数据结构等。操作环境1510只是合适的操作环境的一个实例，并不企图对本发明的使用和功能范围作任何限制。适合于本发明使用的其他熟知的计算机系统，环境和/或结构包括，但不限于个人计算机、手持或台式设备、多处理器系统、基于微处理器的系统、可编程用户电子设备、PC网络、小型计算机、大型计算机、包括上述系统或者设备的公布式计算环境等。
参照图15，说明实施本发明多个方面的示范性环境1510，其中包括计算机1512。计算机1512包括处理单元1514，系统存储器1516和系统总线1518。系统总线1518连接系统组件，系统组件包括但不限于连接到处理单元1514的系统存储器1516。处理单元1514可以是任一可用处理器。双微处理器或其他多处理器结构亦可用作处理单元1514。
系统总线1518可以是几种总线结构中的任何一种，包括存储器总线或存储器控制器、外围总线或外部总线、和/或采用任何一种可用总线结构的局部总线，可用总线结构包括但不限于15位总线、工业标准体系结构(ISA)、微信道体系结构(MSA)、扩展ISA(EISA)、智能驱动电子设备(IDE)、VESA局部总线(VLB)、外围部件内联(PCI)、通用串行总线、高级图形端口(AGP)、个人计算机存储卡国际联合总线(PCMCIA)和小型计算机系统接口(SCSI)。
系统存储器1516包括易失性存储器1520和非易失性存储器1522。包含在计算机1512各单元之间在诸如起动期间传送信息的基本子程序的基本输入/输出系统(BIOS)存在非易失存储器1522中。按照图示方式，但不限于此，非易失存储器1522可以包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除ROM(EEPROM)或闪存。易失存储器1520包括随机存取存储器(RAM)，它用作外高速缓冲存储器。按图示方式，但并不限于此，现用RAM有许多方式，诸如对称RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDR SDRAM)、增强型SDRAM(ESDRAM)、同步联接DRAM(SLDRAM)和直接拉姆总线RAM(DRRAM)。
计算机1512还包括可卸/不可卸、易失/非易失计算机存储媒体。图15示出例如磁盘存储器1524。磁盘存储器1524包括，但并不限于磁盘驱动器件、软盘驱动器、磁带驱动器、Jazz驱动器、Zip驱动器、LS-100驱动器、闪存卡或记忆棒。此外，磁盘存储器1524可包括单独的存储媒体或和别的存储媒体组合的存储媒体。别的存储媒体包括，但不限于诸如致密磁盘ROM器件(CD_ROM)的光盘驱动器、CD可记录驱动器(CD-R驱动器)、CD可重写驱动器(CD-RW驱动器)或数字多用磁盘ROM驱动器(DVD-ROM)。为便于磁盘存储器件1524和系统总线1518连接，通常用可卸或非可卸接口，如接口1526。
显然，图15描述了用作用户和合适操作环境1510的基本计算机资源之间中间体的软件。这种软件包括操作系统1528，操作系统1528可存在磁盘存储器1524中，用来控制和分配计算机系统1512的资源。系统应用程序1530通过存在系统存储器1516或存在磁盘存储1524上的程序模块1532和程序数据1534，由操作系统1528管理资源。显然，本发明可以用各种操作系统或操作系统组合来实施。
用户通过输入设备1536，将命令或信息输入计算机1512，输入设备1536包括，但不限于这些定点设备，诸如鼠标、跟踪球、输入笔、触模式小键盘、键盘、话筒、游戏棒、游戏板、卫星盘、扫描仪、TV调频卡、数码相机、数码摄像机、网络摄像机等等。这些和其他输入设备通过系统总线1518经接口1538连到处理单元1516，接口1538包括例如串行口、并行口、游戏口和多用串行总线(USB)，输出设备1540采用与输入设备1536同类的某些接口。这样，例如用USB接口给计算机1512提供输入和从计算机1512输出信息到输出设备1540，给出的输出适配器1542是说明某些输出设备1540，如在其它输出设备1540之间的监示器、扬声器和打印机需要特殊的适配器。输出适配器1542包括，按说明方式但并不限于，提供输出设备1540和系统总线1518之间多种连接的视频和音频卡，应注意到其他设备和/或设备系统都提供输入和输出功能，诸如远程计算机1544。
计算机1512采用逻辑连接连到一台或多台远程计算机，诸如远程计算机1544，就能在网络环境下操作。远程计算机1544可以是个人计算机、服务器、路由器、PC网络、工作站、基于微处理器的器具、同级设备或其他公用网节点等，通常包括相对计算机1512描述的许多或所有组元。简化起见，只用一个存储器存储设备1546和远程计算机1544连接。远程计算机1544在逻辑上通过网络接口1548跟计算机1512连接，在物理上是经由通讯连接1550连接。网络接口1548包括通讯网络，如局域网(LAN)和广域网(WAN)。LAN技术包括光纤分布式数据接口(FDDI)，同轴电缆分布数据接(CDDI)，以太网/IEEE1502.3和令牌环/IEEE1502.5等。WAN技术包括，但并不限于，点对点链路，电路开关网络，如综合业务数字网络(ISDN)和随后的变异，报文分组交换网络和数字用户环路(DSL)。
通讯连接1550是连接网络接口1548到总线1518所用的硬件/软件。图示计算机1512内部的通讯连接1550，也可是在计算机1512的外部。连接到网络接口1548所必需的硬件/软件包括，仅为示例，内部和外部技术诸如，包括正规电话类调制解调器，有线调制解码器和数字用户环路调制解调器等调制解调器，综合业务数字网络适配器和以太网卡。
以上描述包括了本发明的实例。当然，不可能描述本发明用的组分和方法的每个可想到的组合，但这方面的普通技术人员都可认识到本发明还可有许多进一步的组合和修正。相应地，本发明力图包罗归入所附权利要求的精神和范围的所有这种选择，修正和变动。不仅如此，本发明还力图将详细描述或权利要求中用的术语“包括”加以扩展。倾向类似术语“由……组成”。在权利要求中是被用作一个过渡字，随后加以解释。
权利要求
1.一种二级编码系统，其特征在于，它包括群集形状估算器，它分析与一个文件相关的连接组分信息，提取群集并将它们存进形状总字典、形状页字典和非群集形状存储中的至少一个；位图的群集组分估算，它决定群集在总字典中的存储位置；以及群集位置估算器，它决定总字典和页字典中至少一个的群集在文件上的页位置。
2.如权利要求1所述的二级编码系统，其特征在于，还包括对从所述群集位置估算器接收到的所述页位置进行编码的第一编码器。
3.如权利要求2所述的二级编码系统，其特征在于，还包括对从所述位图群集组分估算接收到的所述字典位置进行编码的第二编码器。
4.如权利要求3所述的二级编码系统，其特征在于，还包括对所述页字典和所述总字典中至少一个进行编码的第三编码器。
5.如权利要求4所述的二级编码系统，其特征在于，还包括对所述非群集形状存储进行编码的第四编码器。
6.如权利要求1所述的二级编码系统，其特征在于，所述连接组分信息包括所述连接组分的颜色、水平大小、垂直大小、水平位置和垂直位置中的至少一个。
7.如权利要求1所述的二级编码系统，其特征在于，所述页位置包括群集间的水平间隙。
8.如权利要求1所述的二级编码系统，其特征在于，所述页位置包括平均垂直位置。
9.如权利要求8所述的二级编码系统，其特征在于，所述页位置还包括所述平均垂直位置和群集的垂直位置之差。
10.如权利要求2所述的二级编码系统，其特征在于，所述第一编码器至少部分采用基于位平面编码。
11.如权利要求3所述的二级编码系统，其特征在于，所述第二编码器至少部分采用基于LZX编码。
12.如权利要求4所述的二级编码系统，其特征在于，所述第三编码器至少部分采用基于无损二级编码。
13.如权利要求5所述的二级编码系统，其特征在于，所述第四编码器至少部分采用基于无损二级编码。
14.如权利要求1所述的二级编码系统，其特征在于，所述群集形状估算器至少部分根据所述存储群集和某个群集的加权平均修正总字典中存储的群集。
15.如权利要求1所述的二级编码系统用于影印机。
16.如权利要求1所述的二级编码系统用于文件扫描仪。
17.如权利要求1所述的二级编码系统用于光字符识别系统。
18.如权利要求1所述的二级编码系统用于个人数字辅助设备。
19.如权利要求1所述的二级编码系统用于传真机。
20.如权利要求1所述的二级编码系统用于数码相机。
21.如权利要求1所述的二级编码系统用于数码摄像机。
22.如权利要求1所述的二级编码系统用于分段分层图像系统。
23.如权利要求1所述的二级编码系统用于视频游戏机。
24.如权利要求1所述的二级编码系统用于台式个人计算机。
25.一种二级编码系统，其特征在于，它包括群集系统，它确定与多个连接组分相关的信息；群集形状估算器，它分析与文件有关的连接组分信息，提取群集并将它们存入形状总字典、形状页字典和非群集形状存储中的至少一个；位图的群集组分估算，它决定总字典中存的群集的字典位置；以及群集位置估算器，它决定总字典和页字典中至少一个的群集在文件上的页位置。
26.如权利要求25所述的二级编码系统，其特征在于，还包括对从所述群集位置估算器接收到的所述页位置进行编码的第一编码器。
27.如权利要求26所述的二级编码系统，其特征在于，还包括对从所述位图群集组分估算接收到的所述字典位置进行编码的第二编码器。
28.如权利要求27所述的二级编码系统，其特征在于，还包括对所述页字典和所述总字典中至少一个进行编码的第三编码器。
29.如权利要求28所述的二级编码系统，其特征在于，还包括对所述非群集形状存储进行编码的第四编码器。
30.如权利要求25所述的二级编码系统，其特征在于，所述连接组分信息包括连接组分的水平大小、垂直大小、水平位置和垂直位置中的至少一个。
31.如权利要求25所述的二级编码系统，其特征在于，还包括激活检测系统，它根据二级图像输入提供二级图像输出，所述二级图像输出具有缩减的颤动/半色调和缩减的噪声中的至少一个。
32.如权利要求26所述的二级编码系统，其特征在于，所述第一编码器至少部分采用基于位平面编码。
33.如权利要求27所述的二级编码系统，其特征在于，所述第二编码器至少部分采用基于LZX编码。
34.如权利要求28所述的二级编码系统，其特征在于，所述第三编码器至少部分采用基于无损二级编码。
35.如权利要求29所述的二级编码系统，其特征在于，所述第四编码器至少部分采用基于无损二级编码。
36.一种二级解码系统，其特征在于，包括第一解码器，对至少部分位流解码，所述第一解码器解码页位置；第二解码器，对至少部分位流解码，所述第二解码器解码字典位置；第三解码器，对至少部分位流解码，所述第三解码器解码形状总字典和形状页字典；第四解码器，对至少部分位流解码，所述第四解码器解码非群集形状存储；群集发生器，它至少部分根据页位置、字典位置和所述总字典和所述页字典中的至少一个来产生群集；以及组合器，它至少部分根据所述产生的群集和所述非群集形状存储提供二级输出。
37.如权利要求36所述的二级解码系统，其特征在于，所述第一解码器至少部分采用基于位平面解码。
38.如权利要求36所述的二级解码系统，其特征在于，所述第二解码器至少部分采用基于LZX解码。
39.如权利要求36所述的二级解码系统，其特征在于，所述第三解码器至少部分采用基于无损二级解码。
40.如权利要求36所述的二级解码系统，其特征在于，所述第四解码器至少部分采用基于无损二级解码。
41.一种二级编码方法，其特征在于，包括以下步骤完成群集分析；编码非群集形状；确定总字典中的指针；以及编码所述指针。
42.如权利要求41所述的方法，其特征在于，还包括下列步骤中的至少一个确定群集的页位置；编码所述页位置；编码页字典；以及编码所述总字典。
43.如权利要求41所述的方法，其特征在于，还包括下列步骤中的至少一个编码残留图像；确定群集；以及完成激活检测。
44.如权利要求42所述的方法，其特征在于，完成群集分析的步骤包括下列步骤中的至少一个决定群集是否处于所述总字典中；如果所述群集不在所述总字典中，则决定所述群集是否处于所述页字典中；如果所述群集处于所述页字典中，则将所述群集存入所述总字典中；如果所述群集处于所述页字典中，则将所述群集移出所述总字典；如果所述群集不在所谓页字典中，则将所述群集存入所述页字典中；以及从位图提取所述群集。
45.一种二级解码方法，其特征在于，包括解码页位置；解码字典位置；解码总字典；以及至少部分根据所述页位置、所述字典位置和所述总字典产生群集，以提供二级输出。
46.如权利要求45所述的方法，其特征在于，还包括下列步骤中的至少一个解码页字典；解码非群集形状；组合所述群集和所述非群集形状，以提供所述二级输出。
47.一种在用于二级编码的两个或多个计算机组分之间传输的数据包，其特征在于，所述数据包包括包括已编码的页位置的第一数据字段；包括已编码的字典位置的第二数据字段；包括已编码的总字典和已编码的页字典中的至少一个的第三数据字段；以及包括已编码的非群集形状存储的第四数据字段。
48.一种存储二极编码系统的计算机可执行组分的计算机可读媒体，其特征在于，它包括群集形状估算器，分析与文件有关的连接组分信息，提取群集并将它们存入形状总字典、形状页字典和非群集形状存储中的至少一个；位图的群集组分估算，决定所述总字典中存的群集的字典位置；以及群集位置估算器，决定所述总字典和所述页字典中至少一个的群集在文件上的页位置。
49.如权利要求48所述的计算机可读媒体，其特征在于，还包括对从所述群集位置估算器接收到的所述页位置进行编码的第一编码器。
50.如权利要求49所述的计算机可读媒体，其特征在于，还包括对从所述位图群集组分估算接收到的所述字典位置进行编码的第二编码器。
51.如权利要求50所述的计算机可读媒体，其特征在于，还包括对所述页字典和所谓总字典中至少一个进行编码的第三编码器。
52.如权利要求51所述的计算机可读媒体，其特征在于，还包括对非群集形状存储进行编码的第四编码器。
53.一种存储二极解码系统的计算机可执行组分的计算机可读媒体，其特征在于，它包括解码至少部分位流的第一解码器，所述第一解码器解码页位置；解码至少部分位流的第二解码器，所述第二解码器解码字典位置；解码至少部分位流的第三解码器，所述第三解码器解码形状总字典和形状页字典；解码至少部分位流的第四解码器，所述第四解码器解码非群集形状存储；群集发生器，它至少部分根据所述页位置、字典位置和所述总字典和所述页字典中的至少一个来产生群集；以及组合器，它至少部分根据所述已产生的群集和所述非群集形状存储提供二级输出。
54.一种二级编码系统，其特征在于，包括至少部分根据与文件相关的连接组分信息分析群集形状的装置；提取群集并将它们存入形状总字典、形状页字典和非群集形状存储中的至少一个的装置；决定总字典中存储群集的字典位置的装置，以及决定所述总字典和所述页字典中至少一个的群集在文件上的页位置的装置。
55.如权利要求54所述的系统，其特征在于，还包括对所述页位置进行编码的装置。
56.如权利要求55所述的系统，其特征在于，还包括对所述字典位置进行编码的装置。
57.如权利要求56所述的系统，其特征在于，还包括对所述页字典和所述总字典中的至少一个进行编码的装置。
58.如权利要求57所述的系统，其特征在于，还包括对非群集形状存储进行编码的装置。
59.一种二级解码系统，其特征在于，包括对页位置进行解码的装置；对字典位置进行解码的装置；对形状总字典和形状页字典中至少一个进行解码的装置；对非群集形状存储进行解码的装置；至少部分根据所述页位置、所述字典位置和所述总字典和所述页字典中的至少一个产生群集的装置；以及将所述已产生的群集和所述非群集形状存储进行组合，以提供二级输出的装置。
全文摘要
对用墨滴群集显式表示的二级图像进行压缩的系统和方法。本发明包括群集形状估算器，它能分析连接组分信息，提取群集并将群集存入总字典、页字典或非群集形状存储中。位图的群集组分估算决定总字典中存储群集的字典位置，然后对字典位置编码。群集位置估算器决定总字典和/或页字典中群集的页位置，然后对页位置编码。再有，还对总字典、页字典和非群集形状存储进行编码。
文档编号G06T9/00GK1453724SQ0311030
公开日2003年11月5日 申请日期2003年4月2日 优先权日2002年4月25日
发明者E·L·伦肖, P·Y·希玛德, H·S·玛尔瓦 申请人:微软公司
最新回复(0)