System for compressing and decompressing binary representations of dithered images

A method for compressing a binary representation of a dithered image (dithered image) comprising the steps of:

• a) defining a plurality of equivalence classes for tiles of binary data contained in said dithered image, wherein tiles are of a predetermined organization of multi-pixel binary data, each of said equivalence classes further having defined and associated therewith a plurality of rendering exemplars having the same gray level;
• b) extracting a tile from said dithered image;
• c) determining which of said plurality of equivalence classes said tile is to be placed in;
• d) storing an identifier for said determined equivalence class in an equivalence class memory;
• e) repeating steps b)-d) for a second predetermined organization of multi-pixel binary data;
• f) compressing said equivalence classes generated pursuant to step e) using a suitable compression technique.

A system for compression and decompression of dithered images, said system comprising:

• input means for receiving a dithered image;
• a processor for performing operations for compressing said dithered image and decompressing a compressed representation of said dithered image;
• storage means for storing tile equivalence class definitions, each of said tile equivalence class definitions for categorizing a plurality of tile configurations into a single class;
• said storage means further for storing data including operations for compressing said dithered image, said operations including:
• operations for creating a binary representation of said dithered image;
• operations for extracting tiles from said binary representation and determining the equivalence class for a tile;
• operations for compressing a predetermined collection of tiles based on their determined equivalence class creating an alternating sequence of literal elements and copy elements;
• said storage means further for storing equivalence class exemplars, each of said equivalence class exemplars comprising a plurality of representative tile configurations for said class, each of said tile configurations have the same gray level;
• said storage means further for storing data including operations for decompressing a compressed representation of a dithered image including:
• operations for decompressing sequences of literal and copy elements into instances of equivalence classes;
• operations for selecting one of said plurality of representative tile configurations for an instance of an equivalence class.

A system for compressing and decompressing a binary representation of a dithered image comprising:

• first storage means for storing equivalence class definitions, each of said equivalence class definitions for assigning an equivalence class identifier to a tile, said tile being a logical organization of binary data in said dithered image;
• equivalence class identification means for identifying the equivalence class for a tile;
• encoding means for encoding sets of tiles based on their identified equivalence class into a compressed data stream;
• second storage means for storing a rendering dictionary, said rendering dictionary having one or more rendering exemplars for each equivalence class;
• decoding means for decoding an instance of said compressed data stream into a sequence of equivalence class identifiers;
• and
• rendering means coupled to said second storage means, said rendering means for selecting a rendering exemplar for an instance of an equivalence class identifier and outputting a decompressed binary representation of said dithered image wherein critical viewing information is retained.