用于半色调数字图像的压缩的方法以及计算设备

摘要

本发明可以提供一种用于半色调数字图像的压缩的方法以及计算设备。基于mxn半色调矩阵和图像的mxn像素块，可以确定mxn像素块的mxn半色调版本。可以对mxn半色调版本的行执行n路交错以创建mnx1半色调段。可以将mnx1半色调段与缓冲区中的一个或多个半色调段相比较。基于该比较，可以输出mnx1半色调段的文字码字和表示，并且可以将mnx1半色调段的表示写入缓冲区。可替代地，可以输出重复码字和重复值，并且可以将mnx1半色调段的至少一个表示写入缓冲区。根据本发明，可以提供一种用于半色调数字图像的压缩的方法。

说明书

技术领域

本发明涉及用于半色调（Halftoned）数字图像的压缩的方法。

背景技术

半色调是通过使用在尺寸、形状或间距方面变化的点来模拟连续色调影像的技术。 在基本二进制半色调方面具有单色调水平的这些点形成半色调点图案。半色调点图案 的正确设计经由单色调水平的仅仅开/关标记提供半色调图像中多色调和平滑阴影的 外观。

发明内容

本发明可以提供用于半色调数字图像的压缩的方法。

在示例实施例中，基于mxn半色调矩阵和图像的第一mxn像素块，可以确定第 一mxn像素块的第一mxn半色调版本。可以对第一mxn像素块的第一mxn半色 调版本的行执行n路交错以创建第一mnx1半色调段。第一mnx1半色调段可以与先 入先出（FIFO）缓冲区中的一个或多个半色调段相比较。如果所述第一mnx1半色调 段与所述FIFO缓冲区中的任意半色调段不相匹配，则可以输出所述第一mnx1半色 调段的文字码字和表示，并且可以将所述第一mnx1半色调段的表示写入所述FIFO 缓冲区。如果所述第一mnx1半色调段与所述FIFO缓冲区中的特定半色调段相匹配， 则可以输出重复码字和重复值，并且可以将所述第一mnx1半色调段的至少一个表示 写入所述FIFO缓冲区。

另外的实施例可以包括一种非暂时性计算机可读介质，在所述计算机可读介质上 存储有程序指令，该程序指令一旦由计算设备执行就导致该计算设备根据上述或其它 示例实施例执行操作。

更多的实施例可以包括一种计算设备，所述计算设备包括：至少一个处理器、数 据储存器，以及在所述数据储存器中的程序指令，所述程序指令一旦由该至少一个处 理器执行就导致所述计算设备根据上述或其它示例实施例操作。

通过在适当之处参照附图阅读下列详细描述，这些以及其它方面、优点和可替代 物对于本领域普通技术人员来说将变得显而易见。进一步，应当理解，在该发明内容 部分以及该文件其它地方提供的描述旨在通过示例的方式而不是通过限制的方式示出 所要求保护的主题。

根据本发明，可以提供用于半色调数字图像的压缩的方法。

附图说明

图1图示根据示例实施例的打印设备。

图2是图解根据示例实施例的打印设备的计算部件的框图。

图3是图解根据示例实施例的涉及打印设备的各种数据路径的框图。

图4图示根据示例实施例的半色调矩阵到图像的像素的应用。

图5A图示根据示例实施例的在图像上平铺的半色调矩阵。

图5B图示根据示例实施例的在具有列填充的图像上平铺的半色调矩阵。

图6图示根据示例实施例的图像和图像的放大部分。

图7图示根据示例实施例的具有列填充的图像的半色调。

图8图示根据示例实施例的图像半色调版本的部分的十六进制表示。

图9图示根据示例实施例的交错图像的半色调版本。

图10图示根据示例实施例的历史缓冲区、先行缓冲区和新的段缓冲区。

图11图示根据示例实施例的压缩后的半色调段的格式。

图12是根据示例实施例的流程图。

图13图示根据示例实施例的历史缓冲区、先行缓冲区和新的段缓冲区的操作， 在该操作中，未找到先行缓冲区的段的匹配。

图14图示根据示例实施例的历史缓冲区、先行缓冲区和新的段缓冲区的操作， 在该操作中，找到先行缓冲区的两段的匹配。

图15图示根据示例实施例的历史缓冲区、先行缓冲区和新的段缓冲区的操作， 在该操作中，未找到先行缓冲区的段的匹配。

图16图示根据示例实施例的历史缓冲区、先行缓冲区和新的段缓冲区的操作， 在该操作中，找到先行缓冲区的一段的匹配。

图17图示根据示例实施例的历史缓冲区、先行缓冲区和新的段缓冲区的操作， 在该操作中，因为使用了列填充而找到先行缓冲区的三段的匹配。

图18图示根据示例实施例的历史缓冲区、先行缓冲区和新的段缓冲区的操作， 在该操作中，找到先行缓冲区和新的段缓冲区的所有段的匹配，方便了扩展重复 码字的使用

图19A、19B、19C和19D图示了其中列填充的使用导致更有效率的半色调图 像压缩的场景。

图20是根据示例实施例的流程图。

具体实施方式

在这里描述示例方法和系统。可以进一步利用其它示例实施例或特征，并且 可以做出其它改变，只要不背离这里呈现的主题的精神或范围。在下列详细描述 中，参考形成该详细描述的一部分的附图。

这里描述的示例实施例并不意味着是限制。将容易理解，在这里一般描述的 和在图中示出的本发明的方面可以被布置、取代、组合、分离和以广泛种类的不 同配置被设计，所有这些在这里被明确地预期。

1、导言

打印技术在过去的30多年间从产生仅仅黑色和白色图像的基于简单点矩阵的 输出设备演进到今天的能够产生高分辨率彩色图像的基于高级激光器的打印设 备。另外，现代打印设备也可以用作复印机、扫描仪和传真机。为了做这些，这 些打印设备可能能够存储排队用于打印或传真的或者已被扫描的数目众多的电子 文件。因此，许多打印设备是专门格式的计算设备，该计算设备可以包括例如一 个或多个处理器、数据储存器和输入/输出接口。

不管打印设备是否用在住宅、商业或其它类型的场所，打印设备可以是能够 通信连接至各种其它计算设备的共享资源。结果，在一些环境中，当数目众多的 计算设备可能正在向打印设备传送电子文件用于打印时，打印设备的存储需求可 能相当高。通常，打印设备将每次以先到先服务的方式打印、复印、传真和/或扫 描一份电子文件。因此，打印设备可以存储潜在的正在等待服务的大数目电子文 件。由于数据储存器（例如，诸如随机存取存储器（RAM）、固态存储器、硬驱 动存储器和/或闪存之类的存储器）的成本可能昂贵，因此为了降低打印设备的数 据存储需求而压缩所存储的电子文件可能是有利的。另外，由于一些电子文件可 能被传递给打印设备和计算设备和/或从打印设备和计算设备传递，因此压缩这些 电子文件可能使传递更快并且使用较少的网络容量。

而且，由于打印作业可能较大（例如，打印作业可能包括包含数以百计页面 的一份或多份电子文件），因此在打印每个作业之前压缩已排队打印作业节省短 期存储空间。另外，用户可能想以长期存储保存打印作业以在后来的时间进行打 印。因此，压缩打印作业可能允许更多的打印作业被保存。此外，存储和从长期 存储器检索大的打印作业的动作可以是慢的，但可以通过压缩打印作业以使它们 在尺寸方面较小来加速。

2、示例打印设备

图1图示示例打印设备100。打印设备100可以被配置为打印在各种类型物理 输出介质上部分存储和/或完全存储的电子文件。这些输出介质包括但不限于各种 尺寸和类型的纸张、字幕片等。打印设备100可以可互换地被称之为“打印机”。

打印设备100可以用作例如个人计算机、服务器设备、打印服务器等的计算 设备的本地外围设备。在这些情况下，打印设备100可以通过例如串行端口电缆、 并行端口电缆、通用串行总线（USB）电缆、Firewire（IEEE1394）电缆或高分辨 率多媒体接口（HDMI）电缆的电缆附接至计算设备。因此，计算设备可以用作用 于打印设备100的电子文件的源。

另一方面，打印设备100可以包括有线或无线网络接口，例如以太网或802.11 （Wifi）接口。如此被配置，打印设备100可以用作用于在网络上能与打印设备 100通信的任意数目计算设备的打印设备。在一些实施例中，打印设备100可以同 时用作本地外围设备和联网打印机两者。

为了使用打印设备100，计算设备可以安装一个或多个打印机驱动器。这些打 印机驱动器可以包括将待打印的电子文件从存储在计算设备上的各种本地表示转 换成由打印设备100支持的一个或多个表示的软件组件。

无论如何，打印设备100可以被考虑为是计算设备，并且可以实现打印相关 的任务和非打印相关的任务两者。

如以上所指出的那样，打印设备100还可以包括复印机、传真机和扫描仪功 能。在一些实施例中，打印设备100可以使用扫描仪功能来方便复印机和/或传真 机功能。例如，打印设备100可以将物理文件扫描成电子格式，并且然后打印所 得到的电子文件以提供副本，和/或经由电话接口传送所得到的电子文件以提供传 真功能。

为了支持打印设备100的各种功能，打印设备100可以包括文件进纸器/输出 托盘102、纸张储存器104、用户接口106、扫描元件108以及机壳110。应当理 解，打印设备可以处理广泛种类的形式。因此，打印设备100可以包括比图1中 图示的更多或更少的部件，和/或采用与图1中图示的不同方式布置的部件。

文件进纸器/输出托盘102可以保留待扫描、复印或传真的物理文件（例如， 一张或多张纸的堆）。有利地，文件进纸器/输出托盘102可以允许打印设备100 自动喂送多个物理文件以通过打印设备100进行处理，而不需要人工干预。文件 进纸器/输出托盘102还可以包括用于保留已由打印设备100处理的物理文件的一 个或多个分离输出托盘。这些可以包括已由打印设备100扫描、复印或传真的物 理文件以及已由例如打印设备100的传真和/或复印功能产生的物理文件。

纸张储存器104可以包括用于各种类型物理介质的托盘和/或喂送元件。例如， 纸张储存器104可以包括用于8¹/₂x11英寸纸、A4纸、信头纸、信封等的分离托 盘。对于打印设备100的涉及输出物理介质的任意功能（例如，打印、复印和/或 接收传真），纸张储存器104可以供应物理介质。

用户接口106可以方便打印设备100与人类或非人类用户的交互，例如用于 从用户接收输入和向用户提供输出。因此，用户接口106可以包括诸如键区、键 盘、触敏或存在敏感性（presence-sensitive）面板、操纵杆、麦克风、照相机和/ 或摄影机的输入部件。用户接口106还可以包括一个或多个输出部件，例如显示 屏（其例如可以与存在敏感性面板组合）、阴极射线管（CRT）、液晶显示器（LCD）、 基于发光二极管（LED）的显示器、使用数字光处理技术的显示器、电 灯泡和/或一个或多个现在已知或后来开发的其它类似设备。用户接口106还可以 被配置为能够经由扬声器、扬声器插孔、音频输出端口、音频输出设备、耳机和/ 或现在已知或在未来随后开发的其它类似设备产生可听输出。

扫描元件108可以是玻璃面板，在该玻璃面板下，可移动光源操作以扫描被 放置在玻璃面板顶部上的物理介质。可替代地，在玻璃面板下的数字相机可以通 过拍摄物理介质的图片而“扫描”被放置在玻璃面板顶部上的物理介质。被扫描 物理介质的图像可以存储在与打印设备100相关联的数据储存器中。

机壳110可以包括包含打印设备100的各种部件（例如文件进纸器/输出托盘 102、纸张储存器104、用户接口106和扫描元件108）和/或与打印设备100的各 种部件互联的物理外壳。另外，机壳110可以容纳图1中未示出的其它部件。例 如，机壳110可以包含一个或多个硒鼓、液体喷墨、传送带、墨辊和/或电源。进 一步，机壳110可以包括诸如有线和/或无线网络接口、电话接口（例如RJ45插孔）、 USB接口、蓝牙接口、读卡器端口等的通信接口。

而且，由于打印设备100可以基于通用和/或特定设计的计算设备部件，因此 机壳110还可以容纳一些或所有这些部件。为此，图2图示可以包括在打印设备 100中的计算设备部件200（例如，计算设备的功能元件）的示例实施例。

计算设备部件200可以包括处理器202、数据储存器204和输入/输出功能206， 所有这些可以通过系统总线208或类似机制连接。处理器202可以包括一个或多 个中央处理单元（CPU），例如一个或多个通用处理器和/或一个或多个专用处理 器（例如，特定用途集成电路（ASIC）或数字信号处理器（DSP）等）。

数据储存器204依次可以包括易失性和/或非易失性数据储存器，并且可以整 体或部分地与处理器202集成。数据储存器204可以存储可由处理器202执行的 程序指令和由这些指令操纵的数据以实现这里描述的各种方法、过程或功能。可 替代地，这些方法、过程或功能可以由硬件、固件和/或硬件、固件和软件的任意 组合定义。因此，数据储存器204可以包括有形、非暂时性计算机可读介质，在 这些介质上存储有一旦由一个或多个处理器执行就导致打印设备100实现在本说 明书或附图中公开的任意方法、过程或功能的程序指令。

输入/输出功能206可以包括参照用户接口106描述的任意功能和/或元件。因 此，输入/输出功能206可以用于配置和/或控制处理器202的操作。输入/输出功能 206还可以基于由处理器202执行的操作提供输出。

应当理解，打印设备的这些示例被提供用于示例目的。进一步，除了和/或可 替代于上面示例，在其它可能性之中，打印机和计算机技术的其它组合和/或子组 合也可以存在，只要不背离这里实施例的范围。

图3图示可能数据路径中由打印设备100处理的电子文件的表示可能通过的 一些数据路径。在图3中，假设打印设备100可以包括扫描功能302和打印功能 304。这些功能中的每个可以以硬件、固件、软件或硬件、固件和/或软件的任意组 合来实施。另外，扫描功能302和打印功能304中的每个可以与计算设备300通 信，并且也可能与其它计算设备通信。在一些情况下，由打印设备100支持的数 据路径可以被称之为“管线”。

扫描至打印数据路径310可以由扫描功能302和打印功能304支持。扫描至 打印数据路径310可以例如在用户指令打印设备100复印物理文件时使用。响应 于该指令，扫描功能302可以将物理文件扫描成电子文件，并且经由扫描至打印 数据路径310将电子文件传送至打印功能304。扫描至打印数据路径310的使用可 能涉及至少暂时将电子文件中的一些或全部存储在打印设备100的数据储存器中。 然后，打印功能304可以将电子文件打印成物理介质（例如一张或多张纸）。

扫描至主机数据路径306也可以由扫描功能302和计算设备300支持。扫描 至主机数据路径306可以例如在用户指令打印设备100扫描物理文件时使用。用 户也可以指令打印设备100将所得到的电子文件的表示传送至计算设备100，或者 打印设备100可以被预配置成将电子文件自动传送至计算设备300。因此，响应于 该指令，扫描功能302可以将物理文件扫描成电子文件，并且经由扫描至主机数 据路径306将所得到的电子文件传送至计算设备300。扫描至打印数据路径310的 使用可能涉及至少暂时将电子文件中的一些或全部存储在打印设备100的数据储 存器中，并且将所得到的电子文件的表示传送至计算设备300。

主机至打印数据路径308可以由计算设备300和打印功能304支持。主机至 打印数据路径308可以例如在用户指令计算设备300在打印设备100上打印电子 文件时使用。响应于该指令，计算设备300可以将电子文件的表示传送至打印功 能304。打印设备100经由打印功能304可以将电子文件打印成物理介质。电子文 件中的一些或全部可以在电子文件的打印之前和/或期间存储在打印设备100的数 据储存器中。

明显地，对于上面讨论的数据路径中的至少一个以及由打印设备100支持的 可能其它数据路径，电子文件可能需要存储和/或在网络或电缆上传送。电子文件 的存储和/或传送两者的效率能够通过压缩这些电子文件来提高。例如，如果电子 文件能够平均被压缩成它们原始尺寸的四分之一，则大约四倍多的电子文件能够 存储在固定量的数据储存器中。进一步，这些压缩电子文件在网络或电缆上的传 送能够比未压缩电子文件的传送大约四倍快地发生。

下列部分描述提供由打印设备100处理的电子文件的压缩的各种实施例。

3、示例图像颜色模型

电子文件能够使用多个颜色模型来表示。因此，稳健型压缩技术应当能够对 这些模型中的一些或全部进行操作。进一步，半色调压缩可能对于单个颜色模型 是特定的，或者可能单独对颜色模型的每个通道进行操作。

例如，红绿蓝（RGB）颜色模型可以用于在电子输出设备，例如电视机、监 视器和计算机屏幕上显示图像。RGB是加色模型，在该模型中，红色、绿色和蓝 色光以各种方式一起加入以产生颜色光谱。例如，青色可以通过组合绿色和蓝色 形成，黄色可以通过组合红色和绿色形成，品红可以通过组合红色和蓝色形成， 并且白色可以通过组合红色、绿色和蓝色形成。

RGB图像的特定像素可以被表达为三通道元组（R,G,B），其每个通道可以从 零变化到预定义的最大值（例如255）。如果所有通道处于零，则结果可能是黑色。 如果所有通道处于最大值，则结果可能是最亮的可表达白色。

RGB输出通常依赖于设备，因为不同的输出设备可以以不同的方式显示相同 的RGB图像。因此，在一些情况下，这些不同可以由人识别。在一些实施例中， 使用扫描至主机数据路径306扫描到打印设备100中的物理文件可以使用RGB颜 色模型来编码。

青色-品红-黄色（CMY）颜色模型可以用于通过打印设备打印彩色图像。CMY 是减色模型，在该模型中，青色、黄色和品红以各种方式施加到白色表面以再生 颜色光谱。例如，红色可以通过组合品红和黄色形成，蓝色可以通过组合青色和 品红形成，并且绿色可以通过组合青色和黄色形成。因此，CMY颜色模型可以被 考虑为RGB颜色模型的补充。

CMY图像的特定像素可以被表达为三通道元组（C,M,Y），其每个通道可以 从零变化到预定义的最大值。如果所有通道处于零，则结果可能是白色。如果所 有通道处于最大值，则结果可能是黑色。

与RGB输出同样地，CMY输出通常依赖于设备，因为相同CMY图像在不同 打印设备上的打印输出可能看起来不同。在一些情况下，这些不同可以由人识别。 在一些实施例中，使用主机至打印数据路径308和/或扫描至打印数据路径310由 打印设备100打印的电子文件可以使用CMY颜色模型编码。

在一些实施例中，也可以使用四通道CMYK颜色模型。除了也使用主（黑色） 通道以外，该CMYK四通道模型可能与CMY颜色模型类似或相同。除了可能组 合青色、品红和黄色以形成黑色，独立的主（黑色）墨源可以用于形成黑色。因 此，CMYK图像的特定像素可以被表达为四通道元组（C,M,Y,K），其每个通道 可以从零变化至预定义的最大值。

使用CMYK颜色模型，与CMY模型相同的颜色可以被支持，但通常使用较 少的墨，因为K着色剂能够代替C、M和Y着色剂的混合物。然而，CMYK颜色 模型可能不总是能够方便地转换成其它颜色模型以及从其它颜色模型转换，因为K 着色剂的添加增加冗余性，例如相同的颜色能够是混合不同C、M、Y和K组合 物的结果。

加色模型是灰色，也被称之为灰度级，灰度级可以用于黑色和白色图像的表 示。与RGB和CMY/CMYK颜色模型不同，灰色颜色模型的每个像素使用对像素 的强度进行编码的单个通道来表示。由灰色通道使用的值能够从用于黑色的零变 化至用于白色的预定义最大值（例如255）。在一些实施例中，由打印设备100支 持的数据路径中的一条或多条可以能够使用灰色颜色模型对图像进行编码。

另一颜色模型是YCbCr。在一些实施中，该颜色模型可以用作图像的可替代 表示。具体地，Y通道可以表示像素的亮度，并且Cb和Cr通道可以分别表示蓝 色-黄色色度和红色-绿色色度。YCbCr颜色模型具有与RGB和CMY颜色模型定 义明确的关系，并且能够相对轻松地转换成这些颜色模型中的任一个以及从这些 颜色模型中的任一个转换。

YCbCr颜色模型的附加优势是，使用YCbCr颜色模型编码的图像的压缩倾向 于比采用RGB或CMY/CMYK颜色模型编码的图像的压缩更有效率。具体地，人 眼不是非常擅长于检测图像中的高频（例如快速变化）色度信息。因此，使用YCbCr 颜色模型编码的图像能够通过忽视Cb和Cr通道的高频组分而利用该信息。因此， 如在下面更详细讨论的那样，采用特定颜色模型编码的图像可以在压缩之前被转 换成YCbCr颜色模型以便提高压缩性能。

4、示例图像半色调

许多数字图像包含连续色调，在该连续色调中，图像的颜色或灰度级部分从 较亮的色调平滑地过渡到较暗的色调，或者从较暗的色调平滑地过渡到较亮的色 调。然而，许多打印机不支持连续色调。代替地，打印机可能支持从最亮色调到 最暗色调的离散数目的色调。例如，对于图像的任意给定像素，简单的黑色和白 色打印机可以支持仅仅输出黑色或白色。

半色调包括将连续色调图像分解成像素阴影的图案以创建平滑过渡灰色或彩 色的幻影的过程。应当注意，这里术语“图像”可以称之为全图像或图像的部分， 例如图像块。在下面的一些示例中，为了简单起见，操作可能针对图像块而不是 全图像示出。

半色调矩阵可以是mxn块单元，每个单元包含一个或多个阈值。当向图像 应用半色调矩阵时，半色调矩阵可以在图像上平铺，使得图像中的每个像素与平 铺半色调矩阵之一中的单元成对相关联。半色调矩阵可以基于特定打印机的特性 来定义，因此可以是特定于输出设备。半色调矩阵也可以被称之为半色调屏幕、 阈值表或抖动表。

来自图像的每个像素可以与其相关联单元中的阈值比较来确定像素的半色调 值。例如，在特定颜色通道中，像素可以采用指示该像素强度或亮度的0-255的值。 相关联单元可以包含三个阈值：64、128和240，因此定义四个范围：0-64、65-128、 129-240和241-255。像素的值落入这些范围之一中，并且像素所落入的范围可以 限定像素的半色调值。因此，像素的半色调值可以利用2位值来限定。例如，00 可以指示范围0-64，01可以指示范围65-128，10可以指示范围129-240，并且11 可以指示范围241-255。

更正式地说，如果在半色调矩阵中存在为每个单元所限定的阈值，则这些阈 值可以限定i个范围，并且像素值所落入的范围可以由log₂(i)位值表示。将半色调 矩阵应用于图像中的每个像素可能导致图像的半色调版本，在半色调版本中，每 个像素由log₂(i)位值表示。该半色调版本然后可以发送至支持i色调的打印机。

该过程在图4中示出。图像像素矩阵400包含多个单个像素，包括示例像素 402和404，每个采用8位值（例如0-255）。半色调矩阵406包含单元的图案， 包括示例单元408和410，每个包括15个阈值的表示（即指示被标记从0至15的 16个范围，在0-255的全部范围内）。

半色调矩阵406可以覆盖在图像像素矩阵400上，使得示例单元408与示例 像素402相关联，并且示例单元410与示例像素404相关联。示例像素402的值 可以被映射成由示例单元408的阈值限定的范围，并且示例像素404的值可以映 射成由示例单元410的阈值限定的范围。

每个示例单元可以限定不同的阈值。例如，示例单元408可以限定阈值412， 而示例单元410可以限定阈值414。因此，将像素映射成这些相应的阈可能导致确 定示例像素402的值落在阈值412的第四和第五阈值之间，并且示例像素404的 值落在阈值414的第十五阈值上。因此，示例像素402的半色调值可以被表示为4， 而示例像素404的半色调值可以被表示为15。

更一般地，假设半色调矩阵的单元限定i-1个阈值。如果像素值大于或等于最 高阈值，则半色调值为i-1。如果像素值小于最低阈值，则半色调值为0。如果像 素值大于或等于第c阈值但小于第（c+1）阈值，则半色调值为c。

覆盖示例图像块的示例半色调矩阵在图5A中图示出。半色调矩阵的每个单元 被标记为A1…A8或B1…B8中之一。这些标记中的每个指示潜在不同的阈值集 合。因此，标记为A1的单元可以具有与标记为A2的单元不同的阈值集合，等等。

半色调矩阵的覆盖图案向左移动，使得半色调矩阵的垂直相邻平铺的起始位 置偏移两个单元。例如，半色调矩阵502的A1单元比半色调矩阵500的A1单元 进一步向左两个单元。相似地，半色调矩阵504的A1单元比半色调矩阵502的 A1单元进一步向左两个单元。该偏移可能导致由打印机产生的半色调图案具有美 学上吸引人的角度。

平铺半色调矩阵的一个可能缺点是，当图像的宽度是这样时需要非整数的半 色调矩阵来覆盖图像的每行。例如，在图5A中，图像块为12x8个像素，并且半 色调矩阵为8x2个单元。因此，需要1¹/₂半色调矩阵来跨越图像块的宽度。因为 下面将更详细解释的原因，填充图像块的行可能导致图像的半色调版本的压缩效 率增加。具体地，图像块可以利用额外的像素列填充，使得整数的半色调矩阵可 以覆盖在每行上。这些填充列（padding column）可以包含在图像块的最右列中的 像素副本。

填充列的数目可以以各种方法确定。确定填充列数目r的一个可能方法是根据 下列等式：

r＝m-(p-q)modm

其中m为单元中半色调矩阵的宽度，p为像素中图像块的宽度，并且q为偏 移。对于图5A，m=8，p=12，并且q=2。因此，r=6。

图5B图示图5A的图像块，其具有6个填充列，并且平铺有半色调矩阵。除 了图5B中示出的平铺半色调矩阵以外，更多的半色调矩阵可以通过将半色调矩阵 从一对行的右端缠绕到接下来下面一对行的左端而在填充图像块上平铺。因此， 半色调矩阵可以在右上角中的A1…A6和B1…B6单元上展开，并且然后“卷绕” 到位于接下来最下面两行的左侧的A7…A8和B7…B8单元。因此，当从左到右相 邻读取每对行时，半色调矩阵顺次重复。

为了提供基于实际图像的另一示例，图6图示示例图像600和图像600的图 像块602。为了简单和例示的目的，图像600包括单个颜色通道。图像块602表示 图像600的区域的扩大，即程式化的“R”。

作为示例，可以假设图像块602的尺寸为128x128像素。进一步假设图5A 的8x2半色调矩阵用于覆盖图像块602，并且偏移为2，则m=8，p=128，并且q=2。 因此，填充列的数目r为2。

图7再次图示图像块602，图像块602此时与2像素填充列700对准。填充 列700可以附加至图像块602的右侧以形成130x128像素块。填充列700的像素 可以从图像块602的两个最右列导出，并且半色调可以应用于这些像素。因此， 半色调后，填充列700的像素可能不类似导出它们的像素。

另外，图7还包括图像块702，图像块702为图像块602的略微放大、半色 调后的版本。类似地，列704是列700的略微放大、半色调后的版本。当在适当 距离处观看时，图像块702近似图像块602的阴影。该效果可以通过向图像块602 应用合适的半色调矩阵而实现。

图8中的半色调像素800图示应用半色调后图像块602的右上角的像素。因 此，半色调像素800可以表示图像块702的部分。在半色调像素800中，单个半 色调像素可以具有采用十六进制符号的从0到F的值。0可以表示最亮的半色调像 素（例如，白色），而F可以表示最暗的半色调像素（例如，黑色）。0和F之间 的半色调像素值可以表示以用于半色调像素值1的浅灰色开始的灰色阴影，并且 随着半色调像素值增加日益变得较暗。

由于图像块602的右上角是纯色，因此半色调像素800的值反映三角图案在 图像块702的右上角明显。这示出半色调如何能够用于表示颜色的特定阴影。

给定图像块的半色调像素，这些像素可以被布置成段。做出这种布置的一个 可能方法在图9中示出。在图9中，假设应用于图像块的半色调矩阵是8单元宽 和2单元高。毫无疑问，其它尺寸的半色调矩阵可以使用。例如，一些实施例可 以使用m单元宽和n单元高的mxn像素半色调矩阵。这些段可以包括填充列中 的像素。

具体地，图9示出被布置成段900A、902A、904A和906A的半色调像素800 的顶部两行的一部分。每段是半色调矩阵的尺寸，也就是说8像素宽和2像素高， 或者8x2。然而，在完全一般性上，如果mxn单元半色调矩阵被使用，则相应 地可以使用mxn像素段。

图9还示出每段的2路交错。例如，在段900A中，该段的顶部像素与该段的 底部像素一个接一个地交错。结果可能是交错段900B，其是16像素宽和1像素高。 以类似的方式，段902A可以被交错以形成交错段902B，段904A可以被交错以形 成交错段904B，并且段906A可以被交错以形成交错段906B。一般地，如果段的 高度是n像素，则可以使用n路交错。因此，为了清楚起见，这些交错段可以可 选择地被称之为mnx1半色调段。

一旦它们被形成，交错段900B、902B、904B和906B可以按图9中示出的顺 序被布置，其中最左交错段由第二最左交错段紧接着，依次类推。这些交错段可 以按该特定顺序提供给被布置以存储这些段用于进一步处理的一个或多个缓冲 区。因此，在下列讨论中对“段”的引用可以假定该段是交错段。进一步，这些 段的序列可以被称之为缓冲区的“输入流”。

图10图示缓冲区布置1000，其包含12段历史缓冲区1002（条目HB_0至 HB_11）、4段先行缓冲区（lookahead buffer）1004（条目LB_0至LB_3）和“新” 缓冲区1006。历史缓冲区1002可以是FIFO缓冲区，因为在历史缓冲区1002（例 如，HB_11）的一端插入的段可以按它们插入的顺序行进通过至历史缓冲区1002 （例如，HB_0）的另一端。数据流的一般方向在图10中被示出为从底部到顶部； 也就是说，段可以首先被放置在“新”缓冲区1006中、移动至先行缓冲区1004， 然后至历史缓冲区1002。

为了方便起见，历史缓冲区1002可以被称之为“FIFO缓冲区”，并且可以 由h条目组成，而先行缓冲区1004可以由k条目组成。“新”缓冲区1006可以由 图10中示出的单个条目或更多条目组成。因此，应当理解，缓冲区布置1000的 单个缓冲区可以各自包含任意数目的条目，并且图10中示出的特定布置是为了示 例的目的。例如，在一些实施中，“新”缓冲区1006的条目可以被考虑为是先行 缓冲区1004的部分。

一般地，半色调段可以通过在历史缓冲区1002中查找匹配段来压缩。具体地， 先行缓冲区1004中段的当前序列可以与历史缓冲区1002中的段序列相比较，以 确定在能够做出的相应段序列之间的最长匹配。当考虑以HB_9、HB_10或HB_11 开始的匹配时，包括在先行缓冲区1004中的段可以被考虑为历史缓冲区1002的 部分。

图11图示在压缩后可以用于表示半色调段的若干不同格式。图11基于图10 的缓冲区布置1000；也就是说，64位段，在历史缓冲区中为12条目，在先行缓 冲区中为4条目，并且在“新”缓冲区中为一个条目。毫无疑问，其它缓冲区布 置可能通过相应调节图11的格式而可以被支持。为了例示的目的，格式1100、1102 和1104的尺寸未按规定比例示出。

格式1100可以表示段的文字编码，并且可以在特定段不能基于缓冲区布置 1000中的信息被压缩时使用。因此，格式1100可以以文字码字开始，其可以是1 的单个位集合。文字码字可以指示下一字段包括未压缩的段。具体地，该下一字 段可以是64位，并且可以是不能被压缩的段的副本。

格式1102可以被称之为重复或短重复格式。格式1102可以以重复码字开始， 其可以是0的单个位集合。该字段可以由4位重复位置字段和2位重复长度字段 紧接着。重复位置字段可以指示在历史缓冲区中重复段从哪开始。重复长度字段 可以指示从该位置开始的重复段的数目。为了高效利用重复长度字段中的位，该 字段可以包含重复段减去1的数目。因此，如果重复长度字段包含值“00”，则1 的重复长度可以被表示。如果重复长度字段包含值“01”，则2的重复长度可以 被表示，等等。

格式1104可以被称之为扩展重复或长重复格式。格式1104可以以扩展重复 码字开始，其可以是1的三个位集合。该字段可以由5位重复长度字段紧接着， 指示条目HB_11中的段在先行缓冲区1004、“新”缓冲区1006和/或输入流中的 倍数。为了高效利用重复长度字段中的位，该字段可以包含重复段减去5的数目。 因此，如果重复长度字段包含值“00000”，则5的重复长度可以被表示。如果重 复长度字段包含值“00001”，则6的重复长度可以被表示，等等。

图12是可以被跟紧接着以确定图11的哪个格式用在特定场景中的全部过程 的流程图。如上所指出的，在步骤1200，先行缓冲区1004中段的当前序列可以与 历史缓冲区1002中的段序列相比较以确定能够做出的段的相应序列之间的最长匹 配。“新”缓冲区1006可以包含将从输入流读取的下一段。

在步骤1202，确定匹配长度是否为零，零指示未找到匹配。如果匹配长度为 零，则在步骤1204处，可以采用下列动作：（1）输出以格式1100编码的LB_0 中的段，（2）移动历史缓冲区一段，将条目HB_0中的之前段从历史缓冲区中清 空，（3）将条目LB_0中的段移动到条目HB11中，以及（4）将新段移动到LB_3 中。

如果匹配长度为非零，则采取的动作可能依赖于匹配的长度。在步骤1206， 确定下列条件是否为真：匹配开始于HB_11并且具有五的长度（所有先行缓冲区 段相同并且等于段HB_11，并且“新”缓冲区1006中的段也与HB_11中的值相 匹配）。

如果条件为真，则在步骤1208，可以采取下列动作：（1）设置扩展计数值 为5，（2）只要扩展计数值小于36并且“新”缓冲区1006中的段与HB_11处的 段相匹配，则丢弃“新”缓冲区1006中的段并且累加扩展计数值，（3）使用格 式1104，输出具有以重复长度字段编码的最后扩展长度的扩展重复码，（4）丢弃 先行缓冲区1004中的所有四个值，而不更新历史缓冲区1002，以及（5）利用来 自输入流的下一段重新加载先行缓冲区1004。

如果条件为非真，则在步骤1210处，可以采取下列动作：（1）利用编码的 匹配历史缓冲区1002位置和匹配长度输出格式1102，（2）以匹配长度移动运行 窗口，以及（3）利用来自输入数据流的下一段重新加载先行缓冲区1006。如果具 有相同非零最好匹配长度的多个匹配存在，则可以使用以最低历史缓冲区1002索 引数开始的匹配。

注意，解压缩器模块可以以相同的原始历史缓冲区值开始，并且可以利用与 压缩器模块相同的规则维持运行窗口。另外，如果待压缩的图像不是段尺寸的整 数倍，则最后一段可能在输入流耗尽时以0位填充。

为了进一步示出能够压缩半色调图像或图像块的各种方法中的一些，图13至 图18提供如何能够操作图10的缓冲区、图11的格式和图12的过程以方便这种 压缩的示例。

图13示出来自输入流的段如何可以添加到“新”缓冲区1006和先行缓冲区 1004。一旦初始化，历史缓冲区1002就可以利用用于条目HB_0至HB_10的所有 “F”值（即采用二进制的1111）和用于条目HB_11的所有“0”值（即采用二进 制的0000）来加载。先行缓冲区1004可以利用来自输入流的第一四段来加载。

在图13所示出的场景中，未能找到匹配。相应地，采用格式1100的输出可 以产生，包括指示输出段未被压缩的文字码字和输出段的副本（例如，由LB_0处 的段表示的64位“00000F9F00000F9”）。因此，全部65位可以输出用于该段。

另外，历史缓冲区1002的段可以向上移动一个条目，其包括丢弃条目HB_0 中的段。输出段也可以是写入的条目HB_11。

图14示出在先行缓冲区1004和历史缓冲区1002中的段之间找到两段匹配的 示例场景。图14的示例场景近似从图13的示例场景离开的位置继续。因此，先 行缓冲区1004的段已向上移动一个条目，“新”缓冲区1006中的段已被移入LB_3 中，并且来自输入流的下一段已被放置在“新”缓冲区1006中。

先行缓冲区1004中段的序列再次可以与历史缓冲区1002中的段序列相比较 以确定那些缓冲区中段的相应序列之间的最长匹配。此时，对于2段的匹配，LB_0 和LB_1的段与段HB_11和LB_0相匹配（如上所指出的那样，当搜索匹配时，先 行缓冲区1004的内容可以被考虑为历史缓冲区1002的部分）。

响应于确定存在两段的匹配，可以产生采用格式1102的输出。该输出可以包 括0的重复码字（二进制）、1011的重复位置（二进制）（指示匹配开始于HB_11）、 第11缓冲区条目和01的重复长度（二进制）（指示HB_11处的段重复两次）（如 上所指出的那样，为了效率的目的，重复长度码可以指代重复长度减去1）。因此， 代替两个64位的段，可以使用一个7位的值。

另外，历史缓冲区1002中的段可以向上移动两个条目，其可以包括丢弃条目 HB_0和HB_1中的段。进一步，先行缓冲区中的段可以向上移动两个条目，其可 能涉及条目LB_0和LB_1中的段移入条目HB_10和HB_11中。另外，“新”缓 冲区1006中的段可以移入条目LB_2中，并且来自输入流的接下来两段可以分别 存储在条目LB_3和“新”缓冲区1006中。

图15图示近似从图14的示例场景离开的位置继续的另一场景。再次，先行 缓冲区1004中段的序列可以与历史缓冲区1002中的段序列相比较，以确定那些 缓冲区中段的相应序列之间的最长匹配。在此场景中，与图13的场景相同，未找 到匹配（零长度匹配）。

相应地，可以产生采用格式1100的输出。该输出可以包括指示输出段未被解 压缩（1二进制）的文字码字和输出段的副本（例如，由LB_0处的段表示的64 位“FAE00FFFFAE00FFF”）。因此，可以针对该段输出总的65位。另外，历史 缓冲区1002的段可以向上移动一个条目，其包括丢弃条目HB_0中的段。输出段 也可以是写入的条目HB_11。

图16示出在先行缓冲区1004与历史缓冲区1002中的段之间找到一段匹配的 示例场景。图16的示例场景近似从图15的示例场景离开的位置继续。

先行缓冲区1004中段的序列再次可以与历史缓冲区1002中的段序列相比较 以确定那些缓冲区中段的相应序列之间的最长匹配。此时，最长匹配位于条目LB_0 中的段与条目LB_11中的段之间。

响应于确定存在一段的匹配，可以产生采用格式1102的输出。该输出可以包 括重复码字（0二进制）、1011的重复位置（二进制）（指示匹配开始于HB_11）、 第11缓冲区条目和00的重复长度（二进制）（指示匹配为一段长度）（再次， 重复长度可以指代实际重复长度减去1）。因此，代替64位的段，可以使用一个 7位的值。

另外，历史缓冲区1002中的段可以向上移动一个条目，其可以包括丢弃条目 HB_0中的段。进一步，先行缓冲区中的段也可以向上移动一个条目，其可能涉及 条目LB_0中的段移入条目HB_11中。“新”缓冲区1006中的段可以移入先行缓 冲区1004的条目LB_3中，并且来自输入流的接下来的段可以分别存储在“新” 缓冲区1006中。

图17示出在先行缓冲区1004与历史缓冲区1002中的段之间找到三段匹配的 示例场景。先行缓冲区1004中段的序列再次可以与历史缓冲区1002中的段序列 相比较以确定那些缓冲区中段的相应序列之间的最长匹配。此时，最长匹配位于 条目LB_0、LB_1和LB_2中的段与条目HB_4、HB_5和HB_6中的段之间。图 17中圈出的值表示来自填充列的值。

响应于确定存在三段的匹配，可以产生采用格式1102的输出。该输出可以包 括重复码字（0二进制）、0100的重复位置（二进制）（指示匹配开始于HB_4） 历史缓冲区1002的第四条目和10的重复长度（二进制）（指示匹配针对三段继 续）。因此，代替三个64位的段，可以使用一个7位的值。

另外，历史缓冲区1002中的段可以向上移动三个条目，其可以包括丢弃条目 HB_0、HB_1和HB_2中的段。进一步，先行缓冲区中的段也可以向上移动三个条 目，其可能涉及条目LB_0、LB_1和LB_2中的段移入条目HB_9、HB_10和HB_11 中。“新”缓冲区1006中的段可以移入条目LB_1中，并且来自输入流的接下来 的三段可以分别存储在LB_2、LB_3和“新”缓冲区1006中。

图18示出在先行缓冲区1004和历史缓冲区1002中的段之间找到五段匹配的 示例场景。该场景是条目HB_11中的段与先行缓冲区1004和“新”缓冲区1006 中的所有条目相匹配的“扩展重复”的示例。因此，最长匹配位于条目HB11、LB_0、 LB_1、LB_2和LB_3中的段与条目LB_0、LB_1、LB_2、LB_3和“新”缓冲区 1006中的段之间。

响应于确定存在五段的扩展重复匹配，可以产生使用格式1104的输出。该输 出可以包括111的扩展重复码字（二进制）和00000的重复长度（二进制）（指 示匹配针对五段继续）（对于扩展重复码字，重复长度码可以指代重复长度减去5）。 因此，代替五个64位的段，可以使用一个8位的值。在重复针对额外段继续的场 景中，输入流可以继续读取并且重复长度可以相应地累加。

图19A、图19B、图19C和图19D提供上述列填充机制的可能益处的进一步 例示。图19A图示具有覆盖的示例8x2半色调矩阵的示例图像块1900。显著地， 在半色调后，与在点1902处开始的三个半色调矩阵对准的像素和与在点1904处 开始的三个半色调矩阵对准的像素相同。

图19B图示包含交错后图19A的半色调矩阵的缓冲区布置1906。如在图19B 中所能看出的，即使与在点1902处开始的三个半色调矩阵对准的像素和与在点 1904处开始的三个半色调矩阵对准的像素相同，但它们也在缓冲区布置1906中彼 此偏移。结果，在先行缓冲区和历史缓冲区中的条目之间不存在匹配。

图19C图示具有覆盖的示例8x2半色调矩阵的示例图像块1908。除了两个 填充列1910应用于右手侧以外，示例图像块1908与示例图像块1900类似。除了 由填充矩阵1910的加入所做出的改变以外，与在点1902处开始的三个半色调矩 阵对准的像素和与在点1904处开始的三个半色调矩阵对准的像素相同。

图19D图示包含交错后图19C的半色调矩阵的缓冲区布置1912。填充列的第 一两个像素1914（最顶部填充像素）被圈出，填充列的第二两个像素1916（第二 顶部填充像素）也被圈出。如在图19D中可看出的，填充列的加入导致历史缓冲 区和先行缓冲区之间的三个匹配。具体地，条目HB_5、HB_6和HB_7与条目LB_0、 LB_1和LB_2相匹配。以该方式，填充列可以导致半色调图像的更高效压缩。

5、示例操作

图20是示例实施例的流程图。由该流程图示出的步骤可以由一个或多个打印 设备，例如打印设备100和/或计算设备，例如计算设备300实施。每个单独步骤 的方面可以由单个设备执行或者分布在多个计算设备之间。图20的示例实施例还 可以包括任意特征或始终在本说明书和/或附图中公开的特征。

在步骤2000，基于mxn半色调矩阵和图像的第一mxn像素块，可以确定第 一mxn像素块的第一mxn半色调版本。该确定可能涉及在图像上平铺mxn半 色调矩阵，使得mxn半色调矩阵的垂直相邻平铺的开始位置偏移q像素。另外， r1xn填充像素列可以附加至图像的最右列。在一些实施例中，p可以是在附加r1 xn填充像素列之前像素中的图像的宽度，并且r可以是m-(p-q)modm。

在步骤2002，可以在第一mxn像素块的第一mxn半色调版本的行上执行n 路交错，以创建第一mnx1半色调段。

在步骤2004，第一mnx1半色调段可以与先入先出（FIFO）缓冲区中的一个 或多个半色调段相比较。该比较可能涉及确定FIFO缓冲区中与第一mnx1半色调 段相匹配的半色调段和连续紧接第一mnx1半色调段的任意其它半色调段的最长 连续范围。

在步骤2006，可以确定第一mnx1半色调段是否与FIFO缓冲区中的任意半 色调段相匹配。如果第一mnx1半色调段与FIFO缓冲区中的特定半色调段相匹配， 则在步骤2008处可以输出重复码字和重复值，并且可以向FIFO缓冲区写入第一 mnx1半色调段的至少一个表示。在一些实施例中，指示特定半色调段在FIFO缓 冲区中的地点的重复位置可以包括在该输出中。

如果第一mnx1半色调段与FIFO缓冲区中的任意半色调段不相匹配，则在 步骤2010处可以输出第一mnx1半色调段的文字码字和表示，并且可以向FIFO 缓冲区写入第一mnx1半色调段的表示。

在一些实施例中，第一mnx1半色调段可以存储在具有其它mnx1半色调段 的一个或多个先行缓冲区中。另外，FIFO缓冲区中的其它mnx1半色调段也可以 与特定半色调段相匹配。j匹配半色调段可以在先行缓冲区中相邻，和/或重复值指 示j。将第一mnx1半色调段的至少一个表示写入FIFO缓冲区可能涉及将第一mn x1半色调段的j表示写入FIFO缓冲区。进一步，其它mnx1半色调段可以从图 像的其它mxn像素块导出。在一些实施中，j匹配半色调段可以从先行缓冲区去 除。

另外，重复码字可以是短重复码字或扩展重复码字。在任一情况下，j可以与 k比较。如果j<k，则短重复码字可以用作重复码字，而如果j≥k，则扩展重复码 字可以用作重复码字。如果扩展重复码字是重复码字，则在向FIFO缓冲区写入第 一mnx1半色调段的j表示之后，可以利用第二mnx1半色调段代替先行缓冲区 中的至少一个条目。第二mnx1半色调段可以从图像的第二mxn像素块导出。

而且，mxn半色调矩阵的每个单元可以包含阈值。阈值可以限定i个像素值 范围，并且第一mxn像素块的第一mxn半色调版本的每个单元可以包含log₂(i) 位值。对于第一mxn像素块中的每个特定单元，确定第一mxn像素块的第一mx n半色调版本可能涉及：（i）确定第一mxn像素块中特定单元的特定像素值，（ii） 确定mxn半色调矩阵的特定单元中的i像素值范围之一包含特定像素值，其中第 一mxn像素块中的特定单元对应于mxn半色调矩阵的特定单元，以及（iii）向 第一mxn像素块的第一mxn半色调版本的特定单元写入表示确定i像素值范围 之一的log₂(i)位值。

6、结论

本发明不限于在本申请中描述的特定实施例方面，该特定实施例旨在作为各 个方面的例示。对于本领域技术人员来说将显而易见的是，可以做出许多更改和 改变，只要不背离其精神和范围。除了这里列出的那些以外，在本发明范围内的 功能等同的方法和装置将从前面的描述中显而易见。这种更改和改变旨在落入所 附权利要求的范围内。

关于图中以及这里讨论的梯形图、场景和流程图中的任意一个或所有，每块 和/或通信可以根据示例实施例表示信息的处理和/或信息的传送。可替代实施例可 以包括在这种示例实施例的范围内。进一步，或多或少的块和/或功能可以与这里 讨论的梯形图、场景和流程图中的任一个一起使用，并且这些梯形图、场景和流 程图可以部分或整体地彼此结合。

表示信息的处理的步骤或块可以对应于能够被配置为执行这里描述的方法或 技术的特定逻辑功能的电路。可替代地或另外地，表示信息的处理的步骤或块可 以对应于模块、段或程序代码的一部分（包括相关数据）。程序代码可以包括可 由处理器执行的用于实施方法或技术中的特定逻辑功能或动作的一个或多个指 令。程序代码和/或相关数据可以存储在任意类型的计算机可读介质上，例如存储 设备，包括盘驱动器、硬盘驱动器或其它存储介质。

计算机可读介质也可以包括非暂时性计算机可读介质，例如像寄存器存储器、 处理器缓存和/或随机存取存储器（RAM）的短时间段存储数据的计算机可读介质。 计算机可读介质还可以包括较长时间段存储程序代码和/或数据的非暂时性计算机 可读介质，例如像只读存储器（ROM）、光盘或磁盘和/或紧凑盘只读存储器 （CD-ROM）的二次或永久长期储存器。计算机可读介质还可以是任意其它的易 失性或非易失性存储系统。计算机可读介质可以被考虑为例如计算机可读存储介 质和/或有形存储设备。

尽管这里已公开了各个方面和实施例，但其它方面和实施例对于本领域技术 人员来说将显而易见。这里公开的各个方面和实施例是为了例示的目的而不旨在 是限制，其真实范围和精神由所附权利要求指示。