Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
2000-02-23
2004-04-13
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Including details of decompression
C382S245000, C341S063000, C375S240230, C358S426130
Reexamination Certificate
active
06721456
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of data compression schemes and, more specifically, to data compression schemes using run length encoding.
BACKGROUND
Printer systems have a series of hardware and software operations through which digital data passes in preparation for printing, referred to as a pipeline. The digital data is used by a print engine to form a print image on a print surface using, for examples, a scanning laser beam or an inkjet. An area of the print surface on which the image is formed is referred to as a picture element (pel or pixel). One scan of the laser beam across the print surface forms a row of pixels, referred to as a scan row. As such, the print image is formed with multiple scan rows.
The type of data that passes through the pipeline may include both text, graphics, and image. As printers increase the density of dot placements, particularly with color printing that requires additional bits per pixel over monochrome printing, the time required for the printer's data pipeline to transmit the data becomes substantial. To fully utilize the increasing print speed capabilities of print engines, the pipeline of a printer system must be able to transfer data sufficiently fast to supply a continuous stream of data to the print engine, thereby allowing the print engine to print continuously.
FIG. 1
illustrates one type of printer system that uses data compression and decompression techniques to reduce data size such that data may be transmitted faster through a printer's pipeline. Data compression refers to a process that attempts to convert data in a given format into an alternative format requiring less space than the original. As such, data compressions systems effect a savings in the amount of storage required to hold, or the amount of time required to transmit, a given body of digital information.
With one type of compression method, referred to as run length encoding, the length of continuous identical pixel data is converted into a run length code for transmission. For example, using one run length compression method, the pixel data line “aaaabbbbbbbcccccdd” is converted into the coded data “a
4
b
7
c
5
d
2
.” The coded data consists of bytes of pixel information (a, b, c, and d) and the number of those bytes that are the same (
4
,
7
,
5
, and
2
). Each byte contains 8 bits of pixel information. Such a byte based compression method may still not provide enough reduction in storage space or transmit time that may be required by current print engines. Further, it is possible that the size of the compressed data may be larger than the size of the original data.
Another problem with some compression methods is that they may not be targeted to handle multiple bits/pixel. Furthermore, prior compression methods may not be efficient to decode in terms of output bandwidth.
SUMMARY OF THE INVENTION
The present invention provides a method of data compression. The method may include receiving a data stream having a plurality of bytes and compressing the data stream into a compressed data format by identifying a run of consecutive bytes of the data stream based on the similarity of the consecutive bytes.
Additional features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows.
REFERENCES:
patent: 4800441 (1989-01-01), Sato
patent: 4811113 (1989-03-01), Ozeki et al.
patent: 5049880 (1991-09-01), Stevens
patent: 5625712 (1997-04-01), Schoenzeit et al.
patent: RE35657 (1997-11-01), Buckley et al.
patent: 5721720 (1998-02-01), Kikuchi et al.
patent: 5727090 (1998-03-01), Yellin
patent: 5758007 (1998-05-01), Kitamura et al.
patent: 5809172 (1998-09-01), Melen
patent: 5812119 (1998-09-01), Tateyama
patent: 5832130 (1998-11-01), Kim
patent: 5845021 (1998-12-01), Kikuchi et al.
patent: 5852742 (1998-12-01), Vondran, Jr. et al.
patent: 5857035 (1999-01-01), Rust
patent: 5867612 (1999-02-01), Robson
patent: 6416410 (2002-07-01), Abou-Samra et al.
patent: 6535150 (2003-03-01), Ross
patent: 0886205 (1998-12-01), None
patent: 0886235 (1998-12-01), None
patent: 0886435 (1998-12-01), None
patent: 0886208 (1999-03-01), None
Murray et al, Encyclopedia of Graphics File Formats, Apr. 1996, O'Reilly & Associates, Inc, Second Edition, p. 160-190 and 962.*
IBM Technical Disclosure Bulletin, “Reduced Run-Length Encoding for Bi-Level Image Compression,” IBM TDB vol. 38, No. 2, Feb. 1995., pp. 295-296.
IBM Technical Disclosure Bulleten, “Apparatus and Associated Method for Compression/Decompression of Color Digital Information,” IBM TDB vol. 40, No. 9, Sep. 1997, pp. 43-44.
Fung, HT; Parker KJ,Color, complex document segmentation and compression, Abstract from Conference: Document Recognition IV, San Jose, CA, Feb. 12-13, 1997; 2 pages.
Godfrey, KRL; Attikiouzel, Y,Self-organized color image quantization for color image data compression, Abstract from 1993 IEEE Int'l Conference on Neural Networks; 1 page.
Yfantis, EA, et al.;An image compression algorithm and its implementation, Abstract from Finite Fields, Coding Theory and Advances in Communications and Computing, 1993; 1 page.
Image Processing Algorithms and Techniques III, Abstract from the Proceedings of the SPIE, vol. 1657, Feb. 10-13, 1992; 1 page.
Aizu, M; Nakagawa, O;Color printing image coding using vector quantization, Abstract from the Journal of Visual Communication and Image Representation, vol. 2, No. 3, Sep. 1991; 1 page.
Jaisimha, MY, et al.;Data compression techniques for maps, Abstract from SOUTHEASTCON '89 Proceedings. Energy and Information Technologies in the Southeast, Apr. 9-12, '89; 1 page.
Goel, BD; Kwatra, SC;A data compression algorithm for color images based on run-length coding and fractal geometry, Abstract from IEEE Int'l Conf. on Communications, Jun. '88; 1 page.
Kato, S; Yasuda, Y;Dithering methods of color images directly applicable to run-length coding, Abstract from GLOBECOM Tokyo '87; Tokyo, Japan, Nov. 15-18, 1987; 1 page.
Patent Abstract from EP-717555 A/US-355594 filed Dec. 14, 1994; 1 page.
Patent Abstract from US-355594 dated Jan. 24, 1989; 1 page.
Patent Abstract from EP-512810 A/US-696681, filed May 7, 1991; 1 page.
Aschenbrenner Jean Margaret
Hanna Stephen Dale
Varga John Thomas
Blakely , Sokoloff, Taylor & Zafman LLP
Mehta Bhavesh M.
Sukhaphadhana Christopher
LandOfFree
Color image data and control bit compression scheme with run... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Color image data and control bit compression scheme with run..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Color image data and control bit compression scheme with run... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3260967