Method and apparatus for compressing color or gray scale documents

#The present invention is related to the field of color image processing, and in particular to techniques for compressing the digital representation of a color document.

#Documents scanned at high resolutions require very large amounts of storage space. For example, an 8.5".times.11"page scanned at 300 spots/inch takes about 8.5 million bytes for a gray-scale pixel map (8 bits/pixel), and over 25 million bytes for a full-color pixel map. "Lossless" compression methods such as Lempel-Ziv Welch (LZW) do not perform particularly well on scanned pixel maps. "Lossy" methods such as JPEG work fairly well on continuous-tone pixel maps, but do not work particularly well on the parts of the page containing text. To optimize compression, techniques which can recognize the type of data being compressed are needed.

#Various approaches are used to compress scanned images. An example of image compression based on symbol matching is described in U.S. Pat. No. 5,303,313 entitled "Method and Apparatus For Compression Of Images", Mark et al., issued Apr. 12, 1994 (the '313 patent). In the '313 patent an image is "precompressed" prior to symbol matching. The '313 patent describes using run-length encoding for such precompression. Symbols are extracted from the run-length representation. A voting scheme is used in conjunction with a plurality of similarity tests to improve symbol matching accuracy. The '313 patent further discloses a template composition scheme wherein the template may be modified based on symbol matches. However, the symbol matching approach while good for text based documents, does not do well on continuous tone images.

#FIG. 1 is a flowchart illustrating the basic steps for compressing a color or gray scale document in the currently preferred embodiment of the present invention.

#FIG. 2 is an illustration of an original document.

#FIG. 3 is an illustration of a foreground map for the foreground plane of the original document shown in FIG. 2.

#A technique for compressing scanned representations of color or gray scale documents is described. The technique if suitable for uses in various devices required to store or transmit color documents such as facsimile devices, image storage devices and the like. It should be noted in some details have been omitted, such as the compression technique used to compress a particular plane, in order not to obscure or detract from the present invention. In other instances, details have been disclosed which would have been apparent to one of skill in the art, such as a particular technique for thresholding a bit-mapped image, in order to more clearly describe the present invention.

#In the description below, various portions are described with reference to color documents, but apply equally to gray scale documents. It should be noted that the examples and illustrations presented in the Figures are in gray scale, but the same concepts apply to color documents.

#A pixel map is one in which each pixel represents some "value" which indicates the color or how light or dark (for gray scale documents) the image is at that point. Most pixel maps have values which are taken from a set of discrete, non-negative integers. For example, a typical gray-scale pixel map might have values ranging from 0, representing black, to 255, representing the whitest tone possible. The pixel maps of concern in the currently preferred embodiment are representations of "scanned" images, that is, images which are created by digitizing light reflected off of physical media using a digital scanner. The term bitmap is used to mean a binary pixel map in which pixels can take one of two values, 1 or 0.