Method and apparatus for data compression of bitmaps using rows and columns of bit-mapped printer data divided into vertical slices

• US 5,930,466 A
• Filed: 03/11/1997
• Issued: 07/27/1999
• Est. Priority Date: 03/11/1997
• Status: Expired due to Term

• Current Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Original Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Inventors: Rademacher, Timothy John
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/814,850
• Time in Patent Office: 868 Days
• Field of Search: 395/114, 395/115, 395/109, 395/110, 395/112, 395/116
• US Class Current: 358/1.15
• CPC Class Codes: G06K 15/10 by matrix printers G06K15/028 takes precedence
• CPC Class Codes: G06K 2215/0014 Transforming the printer input data into internal codes
• CPC Class Codes: G06K 2215/0077 Raster outputting to the print element(s)
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

An improved printing system is provided that compresses bitmap print data by determining, per each vertical slice of a horizontal swath of the printed page, which one of two different data compression techniques to more efficiently compresses each individual slice, then temporarily stores this compressed data in a memory circuit until needed by the printhead for actual printing of the final output in the form of print media. When using slices containing seven (7) different words per slice, the present invention utilizes a single "control bit" of a "control word" to represent each of the data words of the slice. Depending upon which type of compression technique is used, the control bit for each data word will be set to either Logic 1 or Logic 0, depending upon the value of the data word as compared to a pre-determined data word value that is chosen by the system, and which may be used in both types of data compression techniques. After each slice has been analyzed by both types of data compression techniques, certain of the data words in the slice can be temporarily discarded, leaving behind less than seven (7) data words to represent that slice as compressed data. This compressed data for each individual slice will be matched up with a "control word" that is made up of the individual control bits described above, thereby creating a relatively small data set that can be stored in memory in a space that would be less than the amount of memory required to store the uncompressed slices for the same print data. Later, these (compressed) data sets (one per individual slice) can be decompressed according to the proper decompression technique, and the full print data is then restored just before printing by the printhead. As part of the control word, a "mode bit" can be set to either binary value of Logic 1 or Logic 0, thereby indicating which of the two data compression techniques was initially used for that slice. The two data compression techniques used are called a "USE-X MODE" and a "REPEAT MODE."

Claims

1. A method of compressing data to be printed, comprising:

(a) dividing initial print data of any type, including non-character print data, into a plurality of swaths of print information, each of said swaths containing a plurality of slices, and each of said slices having a plurality of bits representing pels to be printed;

(b) analyzing and, where appropriate compressing each individual one of said plurality of slices, using at least one data compression technique controlled by a processing circuit, and temporarily storing the resulting compressed data in a memory circuit as a plurality of compressed slices, such that when two different data compression techniques are used on each of said individual slices, each individual slice is examined to see which of the two different data compression techniques is more efficient in compressing the data for that particular slice, and then a compressed slice is created and stored using the more efficient of the two different data compression techniques for each of said plurality of slices; and

(c) decompressing where appropriate, using a corresponding data decompression technique that is compatible with said at least one data compression technique, each individual one of said plurality of compressed slices, thereby generating a plurality of uncompressed slices of print information for each of said swaths that are equivalent to said initial slices of print data before compression occurred, and presenting said equivalent print data of any type, including non-character print data, to a printing apparatus, such that the appropriate one of two different data decompression techniques that corresponds to said two different data compression techniques is used on each said individual compressed slice.

2. The method as recited in claim 1, wherein either of said two different data compression techniques may be used to compress any individual one of said slices in which the efficiency of compression by both said different data compression techniques provides an equal result for such slice.

3. The method as recited in claim 1, wherein, of the two different data compression techniques, a first compression technique comprises a USE-X mode, and a second compression technique comprises a REPEAT mode.

4. The method as recited in claim 3, wherein said USE-X mode compression technique comprises creating a control word, for each of said plurality of slices, containing a plurality of control bits having a position "i" within said control word, in which each said control bit "i" represents one data word of said individual uncompressed slice, and wherein each control bit "i" is set to binary 1 if the data value for its corresponding data word is equal to the data value of a pre-determined variable "X," and is cleared to binary 0 if the data value for its corresponding data word is not equal to the data value of said pre-determined variable "X;

" and wherein said compressed slice comprises said control word and each data word that was not equal to the data value of said pre-determined variable "X."

5. The method as recited in claim 4, wherein said decompressing step for said USE-X mode comprises (a) inspecting said control word for each of said plurality of compressed slices, (b) for each said control bit "i" set to binary 1 of each compressed slice'"'"'s control word, inserting the data value of said pre-determined variable "X" into the appropriate word location "i" within said compressed slice, (c) for each said control bit "i" cleared to binary 0 of each compressed slice'"'"'s control word, inserting the data value existing in said compressed slice at the appropriate word location "i," and (d) deleting said control word from said compressed slice, thereby generating an uncompressed slice having bit data equivalent to its initial state before said compressing/decompressing steps.

6. The method as recited in claim 3, wherein said REPEAT mode compression technique comprises creating a control word, for each of said plurality of slices, containing a plurality of control bits having a position "i" within said control word, in which each said control bit "i" represents one data word of said individual uncompressed slice, and wherein each control bit "i" is set to binary 1 if the data value for its corresponding data word is equal to the data value of the immediately preceding data word at position (i-1), and is cleared to binary 0 if the data value for its corresponding data word is not equal to the data value of the immediately preceding data word at position (i-1), except for the very first data word of said individual uncompressed slice in which the first control bit "i" is set to binary 1 if the data value for its corresponding data word is equal to the data value of a pre-determined variable "X," and the first control bit "i" is cleared to binary 0 if the data value for its corresponding data word is not equal to the data value of said pre-determined variable "X;

" and wherein said compressed slice comprises said control word and each data word that was not equal to the data value of the immediately preceding data word at position (i-1), and the very first data word of said individual uncompressed slice in the event that its data value was not equal to the data value of said pre-determined variable "X."

7. The method as recited in claim 6, wherein said decompressing step for said REPEAT mode comprises (a) inspecting said control word for each of said plurality of compressed slices, (b) for each said control bit "i" set to binary 1 of each compressed slice'"'"'s control word, inserting the data value of said immediately preceding data word at position (i-1) into the appropriate word location "i" within said compressed slice, (c) for each said control bit "i" cleared to binary 0 of each compressed slice'"'"'s control word, inserting the data value existing in said compressed slice at the appropriate word location "i," (d) for the very first control bit "i" of each compressed slice'"'"'s control word, if set to binary 1, inserting the data value of said pre-determined variable "X," and if cleared to binary 0, inserting the data value existing in said compressed slice at the appropriate word location "0," and (e) deleting said control word from said compressed slice, thereby generating an uncompressed slice having bit data equivalent to its initial state before said compressing/decompressing steps.

8. A printing system having a host computer, a printer, and a communications link therebetween, said system comprising:

(a) a host computer having a first processing circuit, a first memory circuit, and a first communications port, wherein said first processing circuit is configured to compress a first data set of bitmap print data stored in said first memory circuit by;

(i) dividing initial print data of any type, including non-character print data, into a plurality of swaths of print information, each of said swaths containing a plurality of slices, and each of said slices having a plurality of bits representing pels to be printed; and

(ii) analyzing and, where appropriate compressing, using at least one data compression technique controlled by said first processing circuit, each individual one of said plurality of slices and temporarily storing the resulting compressed data in said first memory circuit as a plurality of compressed slices, such that when two different data compression techniques are used on each of said individual slices, each individual slice is examined to see which of the two different data compression techniques is more efficient in compressing the data for that particular slice, and then a compressed slice is created and stored using the more efficient of the two different data compression techniques for each of said plurality of slices, thereby creating a second data set that contains compressed print data;

said first processing circuit being further configured to send said second data set to said first communications port;

(b) a communications link that is operatively connected to said first communications port and that receives data from said first communications port; and

(c) a printer having a second processing circuit, a second memory circuit, a second communications port and a print engine, said second communications port being operatively connected to said communications link and receiving data from said communications link, wherein said second processing circuit is configured to decompress said second data set by;

(i) temporarily storing in said second memory circuit said second data set,

(ii) decompressing where appropriate, using a corresponding data decompression technique that is compatible with said at least one data compression techniques, each individual one of said plurality of compressed slices of said second data set, thereby generating a plurality of uncompressed slices of print information for each of said swaths that are equivalent to said initial slices of print data before compression occurred, such that the appropriate one of two different data decompression techniques that corresponds to said two different data compression techniques is used on each said individual compressed slice, thereby creating a third data set that contains uncompressed print data of any type, including non-character print data; and

(iii) transmitting, swath by swath, to said print engine said third data set of uncompressed print data;

thereby printing an entire page which has an identical appearance according to said first data set of bitmap print data.

9. The printing system as recited in claim 8, wherein, of the two different data compression techniques, a first compression technique comprises a USE-X mode, and a second compression technique comprises a REPEAT mode.

10. The printing system as recited in claim 9, wherein said first processing circuit is configured to perform said USE-X mode compression technique by creating a control word, for each of said plurality of slices, containing a plurality of control bits having a position "i" within said control word, in which each said control bit "i" represents one data word of said individual uncompressed slice, and wherein each control bit "i" is set to binary 1 if the data value for its corresponding data word is equal to the data value of a pre-determined variable "X," and is cleared to binary 0 if the data value for its corresponding data word is not equal to the data value of said pre-determined variable "X;

" and wherein said compressed slice comprises said control word and each data word that was not equal to the data value of said pre-determined variable "X."

11. The printing system as recited in claim 10, wherein said second processing circuit is further configured to perform said USE-X mode decompression technique by (a) inspecting said control word for each of said plurality of compressed slices, (b) for each said control bit "i" set to binary 1 of each compressed slice'"'"'s control word, inserting the data value of said pre-determined variable "X" into the appropriate word location "i" within said compressed slice, (c) for each said control bit "i" cleared to binary 0 of each compressed slice'"'"'s control word, inserting the data value existing in said compressed slice at the appropriate word location "i," and (d) deleting said control word from said compressed slice, thereby generating an uncompressed slice having bit data equivalent to its initial state before said compressing/decompressing steps.

12. The printing system as recited in claim 9, wherein said first processing circuit is configured to perform said REPEAT mode compression technique by creating a control word, for each of said plurality of slices, containing a plurality of control bits having a position "i" within said control word, in which each said control bit "i" represents one data word of said individual uncompressed slice, and wherein each control bit "i" is set to binary 1 if the data value for its corresponding data word is equal to the data value of the immediately preceding data word at position (i-1), and is cleared to binary 0 if the data value for its corresponding data word is not equal to the data value of the immediately preceding data word at position (i-1), except for the very first data word of said individual uncompressed slice in which the first control bit "i" is set to binary 1 if the data value for its corresponding data word is equal to the data value of a pre-determined variable "X," and the first control bit "i" is cleared to binary 0 if the data value for its corresponding data word is not equal to the data value of said pre-determined variable "X;

" and wherein said compressed slice comprises said control word and each data word that was not equal to the data value of the immediately preceding data word at position (i-1), and the very first data word of said individual uncompressed slice in the event that its data value was not equal to the data value of said pre-determined variable "X."

13. The printing system as recited in claim 12, wherein said second processing circuit is further configured to perform said REPEAT mode decompression technique by (a) inspecting said control word for each of said plurality of compressed slices, (b) for each said control bit "i" set to binary 1 of each compressed slice'"'"'s control word, inserting the data value of said immediately preceding data word at position (i-1) into the appropriate word location "i" within said compressed slice, (c) for each said control bit "i" cleared to binary 0 of each compressed slice'"'"'s control word, inserting the data value existing in said compressed slice at the appropriate word location "i," (d) for the very first control bit "i" of each compressed slice'"'"'s control word, if set to binary 1, inserting the data value of said pre-determined variable "X," and if cleared to binary 0, inserting the data value existing in said compressed slice at the appropriate word location "0," and (e) deleting said control word from said compressed slice, thereby generating an uncompressed slice having bit data equivalent to its initial state before said compressing/decompressing steps.