CN1022012C - 图形图象数据压缩方法 - Google Patents

Abstract

本发明的图形图象数据压缩方法包括选择性地或逐个光栅行或逐个字节组地对数据进行压缩的软件。对相邻光栅行内各字节进行逐个光栅行比较(14，66)，并借此检测出行间重复。当逐个光栅行对数据比较时，本发明的方法以相对偏移和置换字节的方式记录任何差别(18)。对单个光栅行内不同字节进行逐个字节组的比较(76)，并借此检测出该行本身内的重复。

Description

本发明涉及图形数据压缩方法，更具体地说，涉及能够有选择地对数据进行逐个光栅行或逐个字节组的压缩的软件。

数据字节常将图形图象描述为光栅行的排列。光栅行为一行或一条图形图象。可将许多平行的光栅行进行排列或叠加而产生完整的图形图象。

每个数据字节描述图形图象内光栅行的一部分。由于每个字节描述光栅行的一部分，所以，数据本身可当作是光栅行数据或逐个光栅行排列的数据，如同对下面的文本所作处理那样。

因为图形常常是复杂的，所以，描述图象的数据可能是大量的和详细的。因此，在系统中各部件之间传送这种数据（例如在主计算机和打印机之间）常常需要大量存储器并可能产生不希望有的时间延迟。为限制所需要的存储器并避免这种时间延迟，可对数据压缩，使得可使用较少数据来传送信息，并由此节省时间。

可用各种方法对数据压缩。例如，Gilbert    Held在他的书“数据压缩”（由Wiley    Hayden出版、1984年版权）公开了一种压缩方法，它将一个光栅行内的各位与相邻光栅行的各数据位进行比较。通过各位间的比较，可记录各行间的差别。一旦记录下，可通过该行中各位如何不同于相邻行各位的说明来描述一个光栅行。与描述光栅行的数据相比，描述该差别的数据可以是较小量的，从而导致数据的压缩。

然而，这种逐位的不同光栅行数据的比较并不能识别光栅行自身内部的重复数据。所以，这种比较本身并不能用于记录行间位变化的简明方法。

本发明的方法通过识别光栅行中的重复以及通过提供记录行间变化的简明方法来克服这种先有的数据压缩方法的限制。

本发明的图形图象数据压缩方法包括有选择地逐个光栅行或逐个字节组地压缩数据的软件。逐个光栅行地比较相邻光栅行内的字节并借此检测所述行间的重复。当逐个光栅行地比较数据时，本发明的方法以相对偏移和置换字节的形式记录任何差异。逐个字节组地比较单个光栅行内的不同字节组并借此检测光栅行自身内的重复。根据这些检测有选择地压缩数据而导致性能优良的数据压缩。

图1为说明本发明的逐个光栅行数据压缩方法的框图。

图2描绘图3A、3B、3C的关系。

图3A-3C构成说明本发明数据压缩方法的详细框图。

图1一般地展示了本发明的光栅行数据压缩方法的框图（用10标示）。起初，将数据块逐个光栅行地进行排列，如框12所表示。又，按逐个光栅行排列的数据块把描述图象的数据排列成光栅行。

然后，步骤14比较第一和第二光栅行的数据，并在步骤16记下光栅行之间的变化。具体地说，在步骤18以相对偏移和置换字节的形式记录下不同于第一光栅行中相应字节的第二光栅行中的所有字节。相应字节就是确定在垂直方向上相邻但处于不同光栅行的图象部分的数据字节。相对偏移和置换字节可作为记录这些光栅行间变化的方式。

例如，可以把第二光栅行中若干不同于第一光栅行中的相应字节的待置换的字节记录为3比特的数。待置换字节的位置可记录为5 比特的数。该5比特数为相对位移值。该偏移为当前光栅行距离上一个未处理字节的字节数，或换言之，是距离上一个已置换字节后的字节的字节数。另一选择为，该偏移可相对于左图形边界。

大的偏移要好几个字节来表示。数0-30可表示0-30的相对偏移，其中，0指的是下一个未压缩字节。如果该5字节数据为31，那么，下一字节解释为附加偏移值并被加到前面的5比特数上。例如，31的偏离量可记录为数31加上附加偏移0，该附加偏移包含在数据的下一字节中。32可记录为数31加上附加偏移1。如果该下一字节包含数255，那么，将该值加到5比特数上而下一字节作为偏离等等。

如上解释，记录了置换字节数和这些字节的位置（偏移）。置换字节本身接在定义偏移值的字节之后。对每一待置换字节。，必须跟有置换字节。置换字节个数的范围为1-8，但对于单个命令字节，由于只有三个二进制数可用来表示置换字节的数目，故而置换字节个数不能超过8。所以，这种数据的格式可表示为：

<命令字节>[<可选偏移字节>]<置换字节>

其中，命令字节包括3比特的待置换字节数和初始的5比特的偏移。例如，在二进制码中，如果命令字节为“01000000”，那么，当前光栅行的下三个字节可用诸如此类的后接的置换字节来替换。如果命令字节为“01100101”，那么，跳过当前光栅行的下5个字节，并用适当的4个置换字节替换下面的4个字节。如果命令字节为“00000000”，那么，置换下一字节。

在最佳实施例中，将光栅行或字节组之间变化的编码适用于记录这些变化的次数和位置，如前所说明那样。但是，可使用不同的记录方法而不偏离本发明的压缩方法。

在步骤20复制经比较的光栅行间未变化的数据。所复制的字节 并不是被压缩的数据的一部分，因为，这些字节已存在于任务处理器的存储器或缓冲器中。换言之，复制步骤简单地留下未修改的数据。所复制的字节数、相对偏移和置换字节完全描述了第二光栅行内的数据。然后，该数据可由步骤22符号化而送至任务处理器。又，仅仅将偏移和置换字节送至任务处理器，因复制数据已在那里而且维持不变。然后，步骤24判定整个数据块是否已压缩。如已压缩，步骤26结束压缩过程。如尚未压缩，本方法由步骤14对后继光栅行信息进行比较而重新开始压缩过程。

起初，对第一和第二光栅行进行比较。对描述后继光栅行的数据进行比较，意味着将前面作为“第二光栅行”的现在作为“第一光栅行”。换言之，这里所用“第一”光栅行是指基准或种子行。下一光栅行变为第二光栅行，这是与未压缩的描述新的第一光栅行的数据比较而言的。因此，术语第一和第二光栅行指的是随压缩进行的不同的行。

图2描绘了图3A-3C间的关系，其中，用框28描绘图3A，用框30描绘图3B，用框32描绘图3C。图3A、3B和3C展示了本发明的可选择的压缩方法。

在图3A中，框34表示描述图象光栅行的数据字节。步骤36识别这种数据的第一光栅行。

在压缩动作起始时将第一光栅行与基准行进行比较，如步骤38所示。基准行由使用本发明的方法的系统所产生，通常可设置为0，因为图形图象原始行一般为空白。

下一步骤40为记录并编译第一光栅行和基准光栅行之间的变化。这些变化的编译构成了描述第一光栅行的数据的压缩描述。然后，步骤42判定该压缩是否充分。如果压缩满足预定的压缩比，例如 9∶1，那么该压缩便是充分的。

如果该压缩不充分，那么，本发明的方法在步骤44确定第一光栅行内的数据字节是否已经按逐个字节组压缩过。如果字节组压缩尚未完成，那么，本方法压缩第一光栅行内的字节组，如步骤46所示。字节组为给定光栅行内的预定字节数。然后，步骤40和42重复字节组压缩。

如果光栅行压缩不充分，并且，字节组压缩也不充分时，那么，本发明的方法使用最高程度的压缩数据，如步骤48所示。最高程度的压缩数据可以是要求较少存储器来存储的光栅行压缩、字节组压缩或未压缩数据本身。

如果初始光栅行压缩充分、后继字节组压缩充分，或者，如果已选择使用最高程度的压缩数据，那么，下一步骤50便将这些数据送至任务处理器。然后，本发明的方法在步骤52判定该压缩是否完成。如果已完成，该任务在步骤54处结束，如果未完成，本方法在56处执行标有“A”的步骤。

图3B绘出标号“A”后的步骤。起始时，本方法在步骤58识别下一光栅行。然后，以同前面光栅行相同的方式对该行进行压缩。例如，如果前面光栅行是以逐个字节组的方式进行压缩的，那么，下一光栅行也可以逐个字节组的方式进行压缩。步骤60判定前面所进行的压缩的方式是什么。如果前面的光栅行未压缩，那么，可从两种压缩方式中任选一种。

如果前面的压缩是按逐个光栅行进行的，那么，本发明的方法通过在62处标有“B”的步骤继续进行。如果前面的压缩是按逐个字节组进行的，那么，本发明的方法继续进行64处标有“C”的步骤。

由标号“B”标识的步骤起始于将当前光栅行和前面光栅行的比较，如步骤66所示。在步骤68处对行间变化进行记录及编译。然后，本方法在步骤70判定该压缩是否充分。如果充分压缩，那么，使用由光栅行压缩得到的数据，如图3C中步骤72所示。

如果步骤70判定没有充分的压缩，那么，下一步骤是判定光栅行是否已经按逐个字节组压缩，如74所示。如还未被压缩，本方法进行64处标号“C”后的那些步骤。

因此，如果前面的光栅行是按逐个字节组压缩的（如在步骤60所确定），或者，如果步骤66、68的光栅行压缩没有导致充分的压缩，那么，便执行标号“C”后的步骤。无论那种情形，在76处对字节组进行比较。在78处对字节组之间的变化进行记录并编译。

然后，本方法在步骤80判定字节组压缩是否充分。如果充分，就使用按逐个字节组压缩后的数据，如图3C中步骤82所示。如果字节组压缩没有产生充分压缩，那么，本方法判定是否已按逐个光栅行进行过压缩，如步骤84所示。如未压缩过，则本方法在62处继续标号“B”之后的步骤。

图3C进一步图示本发明的数据压缩方法。如果已按逐个光栅行和逐个字节组基础上对光栅行进行过压缩，而两种压缩均未产生充分的压缩，那么，本方法便进至框86并使用最高程度的压缩数据。最压缩的数据可以是光栅行压缩数据、字节组压缩数据或未压缩的数据。

无论使用哪一种数据，都要将它送至任务处理器（步骤88）。然后，本方法在步骤90判定数据压缩是否完成，如果完成，则该任务结束，如框92所示。如压缩未完成，本方法返回到图3B中56处的标号“A”并继续下续步骤。

光栅行数据压缩方法以及可供选择的数据压缩方法可用于基于逐个光栅行的描述、图形图象的任何数据。通过光栅行比较的数据压缩，对那些从光栅行到光栅行（即，在“垂直”方向上）重复的数据具有高的压缩比。字节组数据压缩对在单个光栅行内（即，在“水平”方向上）重复的数据具有高的压缩比。

可选择的数据压缩方法考虑到或者按光栅行或者按字节组压缩的数据，取决于哪一种压缩方法产生有效的结果。与其它数据压缩方法相比，这种选择性的压缩方法产生优越的性能，因为，图形图象通常在水平或垂直方向是重复的，但并不总是同时在两个方向上是重复的。

Claims (7)

1、一种在其数据字节按逐个光栅行排列的系统中，用于对这种数据进行压缩的方法，其特征在于包含：

将第一光栅行数据与相邻的第二个光栅行进行比较(14)以便检测其重复和变化，

记下第二光栅行字节相对于第一光栅行中字节的变化(16)，

以相对偏移和置换字节的形式记录这些变化，以及

对后继的顺序相邻的“第一和第二”光栅行的数据重复上述步骤。

2、权利要求1的方法，其特征在于还包括：

复制在第二光栅行中没有变化的第一光栅行中每一字节信息（20），

使用所复制的字节和相对偏移及置换字节来描述第二光栅行中数据。

3、一种在其数据字节组按逐个光栅行排列的系统中，用于对这种数据进行压缩的方法，其特征在于包含：

有选择地或者按以逐个相邻光栅行的方式、或者按逐个相邻字节组的方式、比较这些光栅行数据（66，76），

利用这些比较方式中所选用的一种，记下所比较的相邻行或相邻字节组之间的变化（68，78），

对所述变化编译，以便构成所述比较行或字节组之一的第一压缩描述（68，78），

判定该第一压缩描述是否导致数据的充分压缩（70，80），

如果是充分压缩，则使用第一压缩描述（72，82），

如果不是充分压缩，则以另一种比较方式（初始比较中未用的）对数据进行比较（66，76），

记下所述相邻比较行或相邻比较字节组之间的变化（68，78），

对这些变化编译，以便它们构成所述比较行或字节组之一的第二压缩描述（68，78），

判定该第二压缩描述是否导致数据的充分压缩，

如果是充分压缩，则使用第二压缩数据（72，82），

如果不是充分压缩，则使用在第一和第二压缩描述及未压缩数据中的最高程度的压缩描述（86），以及

对后续光栅行数据重复以上步骤。

4、权利要求3的方法，其特征在于，所述比较步骤（76）是逐个字节进行的，该步骤包含将预定字节数的数据与同一光栅行内顺序相邻的预定字节数的数据进行比较，并重复这些字节的比较直至构成光栅行的所有字节已经被比较。

5、权利要求3的方法，其特征在于，所述重复步骤包含以与对紧接的前面的数据进行比较的相同的方法，即，根据对紧接的前面的数据进行比较的方式，按逐个光栅行或逐个字节组对后继光栅行数据进行比较。

6、权利要求3的方法，其特征在于还包含：通过对逐个光栅行的数据进行比较来开始数据压缩过程，执行记录、编译和判定步骤，然后，如果未充分压缩，对预定的若干光栅行进行逐个字节组的数据比较，执行记录、编译、判定和使用的步骤，然后，以逐个光栅行的比较重新开始，重复上述步骤。

7、权利要求3的方法，其特征在于，在逐个光栅行地进行比较（66）、记下（68）和编译（68）时，这些步骤还包含以相对偏移和置换字节的方式，记录第二光栅行中不同于第一光栅行的对应字节的每一个字节，并对这些偏移和置换字节进行编译以便它们构成该第二光栅行的压缩的描述。

Images