Hybrid Image Compressor

1. Field of the Invention

The present invention relates generally to digital image compression systems, and more particularly to a system and method of compressing a document containing multiple types of images with compression schemes optimized for the characteristics of separate regions.

2. Description of Background Art

The archiving of documents has long been an important task in many business enterprises and other organizations. Recently, the archiving of digital images of documents has become possible, with affordable document scanners and fast computers. Retaining the full uncompressed digital image of documents, however, leads to difficulties with storage and efficient transmittal across networks. For this reason, most digital document archives employ some sort of compression scheme to decrease the amount of memory required for a single digital document image.

A number of techniques are used to compress digital images, and they generally fit into two broad categories: lossy and lossless. Lossy techniques allow some image data to be lost in the process of compression, while with lossless techniques there is no loss of image data. With lossless techniques the decompressed image is identical to the original. Compression techniques tend to be optimized for specific types of images. One of the image types is "grayscale," meaning that an image is composed of many different shades of gray. A typical grayscale image is a "black and white" photograph of a real world scene, in which the shading of objects is characterized by subtle changes from white to light gray to dark gray to black. Grayscale images are a special case of "continuous tone" images. Continuous tone images contain many colors, but only those colors which are on a gradient between two distinct colors. A continuous tone image could, for example, be composed entirely of color gradations ranging from green to yellow. In the case of grayscale images, the two distinct colors are black and white, with the colors in the image being some combination of black and white. Most instances of non-grayscale continuous tone images are found in images created by graphic artists, such as in some magazine advertisements. Another type of image is referred to as "bitonal." A bitonial image is composed entirely of two distinct colors. The most commonly seen example of bitonal images is probably black text on white paper. Bitonal images are characterized by sharp contrasts, for example the edges of the letters on a printed page. Yet another type of image is the "full color" image. Full color images contain a large number of very different color values, as in a color photograph of a real world scene. A full color image is similar to the continuous tone images, in that it is characterized by smooth variations in color, but the colors are not limited to those on a gradient between two distinct colors. In a typical magazine or newspaper page multiple types of images are present: the photographs and artwork tend to be continuous tone or full color, and the text tends to be bitonal. An image which is composed of more than one type of image is referred to as a "hybrid image."

For the compression of continuous tone and full color images, maximum compression with acceptable results can generally be achieved with lossy compression schemes, such as the Joint Photographic Experts Group (JPEG) standard. This standard is described in J. D. Murray and W. VanRyper, Encyclopedia of Graphics File Formats, Second Edition, O'Reilly & Associates, Inc., Bonn:1996 and ISO/IEC 10918-1:1994, Information Technology--Digital Compression and Coding of Continuous-tone Still Images: Requirements and Guidelines. The loss of image information in lossy schemes such as JPEG does result in the loss of some image detail. After decompression, however, the result of a JPEG compression performed on most grayscale and full color images is an image which appears to the human eye to be nearly identical to the original. When JPEG (or other lossy compression schemes) are applied to bitonal images, such as a page of text, the results are poor. The sharpness of the characters suffers and the text appears fuzzy. Other loosy compression schemes include fractal compression, described in Yuval Fisher, ed., Fractal Image Compression: Theory and Application to Digital Images, Springer Verlag, New York, 1995; and wavelet compression, described in C. K. Chui, An Introduction to Wavelets, Academic Press, London, 1992.

Bitonal images are generally compressed with a lossless scheme, in order to preserve the sharpness of the image. Many lossless schemes are specifically optimized for bitonal images and do not handle grayscale and full color images well. Examples of such schemes are the Joint Bilevel Imaging Group (JBIG) standard, described in International Telecommunication Union Recommendation T.82; and the Group 3 and Group 4 standards (G3 and G4) of the 1-D Consultative Committee of the International Telephone and Telegraph (CCITT). These schemes are described in Encyclopedia of Graphics File Formats and R. C. Gonzalez & R. E. Woods, Digital Image Processing, Addison-Wesley, Reading, Mass.: 1992. While these standards result in significant compression of bitonal images without loss of detail, they perform poorly on grayscale and full color images, sometimes even resulting in negative compression (i.e., larger files).

When scanning and compressing images containing more than one type of image, as in a typical magazine or newspaper page, a tradeoff must be made. If lossy techniques are utilized, the image quality of the text portion of the page suffers, and if lossless techniques are utilized, less compression is achieved. What is needed is a way to maximize compression of hybrid images without loss of detail in the bitonal portions.

The present invention is a computer apparatus and method for efficiently compressing hybrid images without unacceptable loss of image detail. A hybrid digital image is sent to a classifier (103), which categorizes portions of the image based on a number of image types. The classifier produces multiple images (105a, 105b) which are each sent to a compressor (104a, 104b). Each image contains image data corresponding to one image type. Each compressor is optimized to compress images of the type sent to it, so each region in the original image is efficiently compressed. The individual compressed images can be stored and efficiently transmitted, then reconstructed, producing an image that retains that image detail that is necessary.

FIG. 1 is a block diagram depicting the operation of the present invention.

FIG. 2 is an illustration of typical pixel values found within the rows of a hybrid digital image containing both grayscale and bitonal portions.

FIG. 3 is a block diagram showing registers and memory devices contained within one embodiment of the classifier from FIG. 1.

The present invention may be implemented as functional components of a scanning system, or may take the form of hardware, software, firmware or some combination thereof. In one embodiment, illustrated in FIG. 1, the present invention is part of a scanning system. For the purposes of this discussion, the operation of the invention will be described in relation to a hybrid image containing grayscale and bitonal portions only. This is for illustrative purposes only and in alternative embodiments other image types, such as full color, continuous tone and motion images, may be used.

Document 101 is a piece of paper containing a hybrid image on it. This particular hybrid image is composed of both grayscale portions and text portions. Alternatively, the document 101 could contain a hybrid image that is composed of other types, such as full color images, moving images and others.

Document 101 is scanned by scanner 102, a conventional device that uses optical means to produce a digital image from an image on a piece of paper.

The digital output of scanner 102 is input to classifier 103, which may be implemented in either hardware, software or firmware. In one embodiment classifier 103 receives input from the scanner one horizontal row of pixels at a time. Classifier 103 performs operations on this row of pixels and then forwards a row of pixels to each compressor 104. Alternatively, classifier 103 could wait for more than one row of pixels, perhaps the entire image, before performing the classification operations. Waiting for more than one row of pixels would allow the classifier 103 to perform more complex operations on the pixel data, but at the price of waiting until the scanner is finished with the entire page. In cases where speed and economy are important, it is preferred that the classifier 103 examines pixels one row at a time, independently of other rows of pixels. This allows the classifier 103 to work while scanning is proceeding and reduces the need for memory to store multiple scan-lines.

When a row of pixels comes into classifier 103, they are divided into groups of eight pixels. The JPEG compression scheme performs its operations on square regions of N pixels by N pixels, with N most commonly being eight. Because at least some of the pixels will be forwarded, after processing by the classifier 103, to JPEG compressor 104a it is advantageous to operate on the pixels in groups of N, in this case groups of eight. Each group of eight horizontal pixels is categorized as being either grayscale or bitonal. Alternatively, other classifications could be used as well.

The classifier 103 must determine whether the series of eight pixels represents a grayscale series or a bitonal series. A typical grayscale series of pixel values is shown in FIG. 2 as series 202. The values (shown in hexadecimal) correspond to the brightness of the given pixel in the image, with 00 being white and FF being black. In series 202 there is a gradual rise from value 00 (white) to value FF (black). This is typical of the pixels in a grayscale image. One way to discriminate between grayscale and bitonal pixel series is to determine the ratio of grayscale pixels to bitonal pixels. To do this, pixels below a particular threshold, for example 10, are considered white, pixels above another threshold, for example EF, are considered black, and all pixels with values in between the thresholds are considered gray. The gray pixels (in this example those with values from 10 to EF) are considered grayscale, while those which are white (from 00 to 0F ) and those which are black (F0 to FF) are considered bitonal. Such a scheme is effective on a pixel series like 202, where there is a single rise in pixel values, but is less effective on a pixel series like 203. Series 203 has the same pixel values as series 202, but in a different order. The ratio of grayscale pixels to bitonal pixels is the same in series 202 and series 203. While series 202, with its two transitions from white to gray and gray to black, might well be considered bitonal, series 203, with its several sharp changes between black, gray and white probably would not.

In order to more accurately determine the type to which a pixel series belongs, a state change counter is utilized by the classifier 103. Two "states" are define for the pixels, based on their values: a bitonal state (including black pixels and white pixels), and a gray state (including gray pixels). In FIG. 3 the classifier 103 is seen to include six registers. Register 301 is the "low threshold," the value below which a pixel is determined to be white. Register 302 is the "high threshold," the value above which a pixel is determined to be black. Register 303 is the "state change counter," which is reset to zero by the classifier before a pixel series is analyzed, and incremented by one each time a pixel is encountered which is of a different state than the previous pixel (i.e., a gray pixel is encountered immediately following a white pixel, or a black pixel is encountered immediately following a gray pixel). Register 304 is the "grayscale counter," which is reset to zero by the classifier before a pixel series is analyzed, and incremented by one each time a pixel is encountered which is of the gray state. Register 305 is the "state change threshold." After all eight pixels have been analyzed, the state change counter 303 is compared to the state change threshold 305. If the value in the state change counter 303 exceeds the value in the state change threshold 305, the series of pixels is categorized grayscale. A second test is necessary to handle the situation, as in series 204, where all (or nearly all) pixels are grayscale in a particular series. In that case, the state change counter will contain zero, but the grayscale counter will have a large value. To handle this situation, when state change counter 303 does not exceed the state change threshold 305, grayscale counter 304 is compared to register 306, the "grayscale threshold." If the value of the grayscale counter 304 exceeds the value of the grayscale threshold 306, the series of pixels is categorized as grayscale. Only if neither counter exceeds the corresponding threshold is a series of pixels categorized as bitonal. This procedure categorizes a series of pixels as grayscale if either the number of state changes is high, or if the number of grayscale pixels is high. The threshold values in registers 301, 302, 305 and 306 are programmable by the user to optimize the categorization process for a particular input image. For example, if the background of an image is dark, register 301, the low threshold, may be set higher than otherwise.

In another embodiment, the classifier 103 examines the pixel statistics of the series immediately in front of and the series immediately behind a target series. The effects of the pixels ahead of and behind the target pixels can be modified by weighting. Although a larger memory buffer is required in classifier 103 for this embodiment, the accuracy of the classifier will be improved in many cases. Many other implementations of the classifying procedure will be apparent to those skilled in the art.

Memory device 307 holds the series of eight pixels being analyzed, having been received from the scanner 102. If the classification for a series of pixels is grayscale, then grayscale memory device 308 is filled with the values present in memory device 307, and bitonal memory device 309 is filled with zeroes. If, instead, the categorization for a series of pixels is bitonal, then bitonal memory device 308 is filled with the values of memory device 307, and grayscale memory device 307 is filled with zeroes. The classifier 103 then sends the values from grayscale memory device 307 to the grayscale compressor 104a, and sends the values from bitonal memory device 308 to the bitonal compressor 104b. In this way, each type of compressor 104 receives either pixel series of its own type, or else zeroes. Compressor 104a is optimized to compress grayscale images using a scheme such as JPEG. Compressor 104b is optimized to compress bitonal images using a scheme such as JBIG, G3 or G4. Because the regions classified as bitonal may contain some grayscale pixels, it is preferable to use a simple thresholding function to set all pixels in a bitonal series to black (FF) or white (00). This permits a more efficient bitonal compression. Each compressor 104 may be implemented either as a hardware, software or firmware module. A hardware implementation of the JPEG compressor is the model #Z36050 image compressor from Zoran. The model #PM2 image compressor from Pixel Magic is a conventional hardware implementation of a compression scheme optimized for bitonal images. The effect of zeroes in the data transmitted to a compressor 104 is that it is given an image 105 in which those portions of the image that the compressor 104 cannot efficiently compress are masked out in white. Since all of the compression schemes can efficiently compress a large white space, each compressor 104 is able to efficiently compress a different part of the image.

Each compressor 104 stores the result of its compression in a storage device 106. The separate compressed images can reside in the storage device until reconstruction of the original image is desired. At that time, merge device 107 calls upon the storage devices 106 for each compressed portion of the hybrid image 101. The merge device decompresses each image retrieved from storage 106 according to the scheme it was compressed with (in this case JPEG for the grayscale compressed image and JBIG, G3 or G4 for the bitonal compressed image). These separate decompressed images are then superimposed upon one another to form the reconstructed hybrid image 108. The reconstructed hybrid image may be printed, displayed on a monitor, or transmitted to another device, among other things. In an alternate embodiment, the compressed images may be transmitted over a computer network directly to a merge device in another location, where the hybrid image is reconstructed.

The above description is included to illustrate the operation of the preferred embodiments and is not meant to limit the scope of the invention. The scope of the invention is to be limited only by the following claims. From the above description, many variations will be apparent to one skilled in the art that would be encompassed by the spirit and scope of the present invention.