Binary image data compression and decompression

• US 5,974,179 A
• Filed: 02/13/1995
• Issued: 10/26/1999
• Est. Priority Date: 02/13/1995
• Status: Expired due to Term

• Current Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Original Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Inventors: Caklovic, Nenad
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US08/387,528
• Time in Patent Office: 1,716 Days
• Field of Search: 348/420, 348/422, 348/413, 382/232, 382/246, 382/244, 358/433, 358/261.3, 341/50
• US Class Current: 382/232
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A method for preprocessing a binary file for data compression under a dictionary-based data compression algorithm takes advantage of redundancy in a two-dimensional binary image. The method rearranges a linear representation of a binary image, i.e. a representation based on pixels of horizontal lines, to a two-dimensional representation, i.e. a representation based on a sequence of adjoining picture areas, to achieve an improvement of compression ratio. The present invention is applicable to dictionary-based data compression methods, such as LZW, LZ77 and LZ78.

Claims

1. An apparatus for compressing a binary image, said binary image including a plurality of scan lines, each scan line having a plurality of pixels, said apparatus comprising:

a preprocessor for (i) segmenting each scan line of said binary image into segments of equal number of pixels, (ii) grouping said binary image into data groups, each data group including a segment of pixels from each of a predetermined number of adjacent scan lines, wherein said segments of pixels in each data group represents pixels at corresponding locations in said predetermined number of adjacent scan lines, and (iii) dividing each data group into a predetermined number of data units, each data unit including pixels selected from each of said predetermined number of adjacent scan lines within said data group

said preprocessor comprising a plurality of registers, equalling in number to said predetermined number of adjacent scan lines, for receiving a data group, wherein each register receives one of said segments of pixels in said data group received;

said preprocessor further comprising a first control circuit, receiving a data group of said binary image at a time, said first control circuit loading said segments of pixels of said data group into said plurality of registers; and

said preprocessor further comprising a second control circuit, said second control circuit extracting from said plurality of registers said data units; and

a compressor, receiving said data units sequentially, for applying a dictionary data compression algorithm on said data units received.

2. An apparatus as in claim 1, wherein said segments of pixels in said data group received in said first control circuit are provided to said registers sequentially, and wherein each register includes a plurality of individually enabled output signals, said second control circuit extracting said data units by activating sequentially selected sets of said individually enabled output signals, each of said selected set includes an output signal from each of said plurality of registers.

3. A system including said apparatus of claim 1, further comprising:

a decompressor, said decompressor undoing data compression performed in accordance with said compression algorithm; and

a postprocessor, said postprocessor restoring said binary image from said data units.

4. A system as in claim 3, wherein said postprocessor comprises:

a plurality of registers, equalling in number to said predetermined number of adjacent scan lines, for receiving data units of a data group, wherein each register capable of holding a segment of pixels in said data group;

a first control circuit, receiving data units of a data group of said binary image at a time, said first control circuit loading said data units into said plurality of registers, such that each register contains a segment of pixels of said data group; and

a second control circuit, said second control circuit outputting from said plurality of registers each a segment of said data group.