A method for adaptively compressing and decompressing digital data having text

<b>Appendix</b>

0001The disclosure in the appendix of this patent disclosure of this patent document contains material to which a claim of copyright protection is made. The copyright owner has no objection to the facsimile reproduction of any one of the patent documents or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but reserves all other rights whatsoever.

<b>Field of The Invention</b>

0002The invention relates generally to the field of digital image compression and, more particularly, to such compression that recognizes text and uses a predetermined strategy for compressing and decompressing the text.

<b>Background Of The Invention</b>

0003It is well known to employ transform coding of digital images for bandwidth compression prior to storage or transmission over a limited bandwidth communication channel. In a typical prior art digital image compression/decompression system employing transform coding, such as the one used in the JPEG International standard <i>(Digital compression and coding of continuous-tone still images - Part I: Requirements and Guidelines (JPEG),</i> ISO/IEC International Standard 10918-1, ITU-T Rec. T.81, 1993, or W. B. Pennebaker and J. L. Mitchell, <i>JPEG Still Image Data Compression Standard,</i> Van Nostrand Reinhold, New York, 1993), the digital image is formatted into blocks (e.g. 8 x 8 pixels) and a linear transformation such as a discrete cosine transform (DCT) is applied to each block to generate 8 x 8 blocks of transform coefficients. Theoretically, for images modeled as a first-order Markov source with a correlation coefficient close to unity, the DCT is very close to the Karhunen-Loeve (KL) Transform that is optimal in reducing correlation. For photographic type images, the DCT still provides very good decorrelation properties and, unlike the KL transform that is image-dependent and does not yield itself to straightforward computation, it can be efficiently implemented in software or hardware. The DCT coefficients are then normalized and quantized using a uniform quantizer.

0004In the JPEG standard, the user can specify a different quantizer step size for each coefficient. This allows the user to control the resulting distortion due to quantization in each coefficient. The quantizer step sizes may be designed based on the relative perceptual importance of the various DCT coefficients or according to other criteria depending on the application. The 64 quantizer step sizes corresponding to the 64 DCT coefficients in each 8x8 block are specified by the 1-byte elements of an 8x8 user-defined array, called the normalization matrix, or the quantization matrix, or the "Q-table". Each block of quantized transform coefficients is ordered into a one-dimensional vector using a zig-zag scan that rearranges the quantized coefficients in the order of decreasing energy. This usually results in long runs of zero quantized values that can be efficiently encoded by runlength coding. Each nonzero quantized value and the number of zero values preceding it are encoded as a {runlength/amplitude} pair using a minimum redundancy coding scheme such as Huffman coding. The binary coded transform coefficients along with an image header containing information such as the Q-table specification, the Huffman table specification, and other image related data are either stored or transmitted over a limited bandwidth channel.

0005At the receiver, the image signal is decoded from the binary bitstream using operations that are the inverse of those employed at the encoder. This technique is capable of producing advantageously high image compression ratios, thereby saving significant storage space or enabling low bit rate transmission of digital images over limited bandwidth communication channels.

0006Although the presently known and utilized method and system for compressing images are satisfactory, improvements are always desirable. In particular, when the system described above is used to compress an image that contains both photographic data and text, undesirable artifacts such as ringing and blocking can occur. This is due to the fact that text contains large intensity variations from one pixel to another that does not compress well with DCT-based schemes.

<b>SUMMARY OF THE INVENTION</b>

0007The present invention is directed at overcoming one or more of the problems set forth above. Briefly summarized, according to one aspect of the present invention, the invention resides in a method for compressing a digital image having both saturated text and/or line art and pictorial imagery , the method comprising the steps of: receiving the digital image as blocks of pixels; analyzing the block content to determine if all or any combination of the saturated text and/or line art, pictorial imagery or other types of image data are present; assigning the saturated text and/or line art, the pictorial imagery, the other types of image data to one of a plurality of categories; compressing the block of saturated text and/or line art, if any, according to a first predetermined compression method; compressing the pictorial imagery, if any, according to a second predetermined compression method; compressing the other types of imagery, if any, according to other predetermined compression methods; and providing means of conveying the image categories to a decoder.

0008It is an object of the present invention that, knowing <i>a priori</i> that a given block contains saturated text only, the compression scheme is modified in such a way as to take advantage of this information without a significant modification in the software or hardware implementation. The present invention utilizes knowledge of the type of image to be compressed in the compression process for producing higher quality images.

0009These and other aspects, objects, features and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings.

<b>Advantageous Effect Of The Invention</b>

0010The present invention has the advantage of compressing text and/or line art so that the sharp boundary information is preserved while simultaneously achieving a higher compression of the image data than is otherwise possible, using a standard JPEG compression technique.

<b>BRIEF DESCRIPTION OF THE DRAWINGS</b>

0011<ul id="ul0001" list-style="none" compact="compact"><li>Figure 1 is a block diagram illustrating the encoder employed in the present invention.</li><li>Figures 2A-2I are drawings illustrating exemplary 8x8 blocks of pixel information through various stages of the present invention; and</li><li>Figure 3 is a block diagram illustrating the decoder employed in the present invention.</li></ul>

<b>DETAILED DESCRIPTION OF THE INVENTION</b>

0012In the following description, the present invention will be described in the preferred embodiment as a software program. It is also noted that that a general purpose computer can be used to implement the present invention, and that such a general purpose computer will not be discussed in detail herein as such computers are well known in the art. Those skilled in the art will readily recognize that the equivalent of such software may also be constructed in hardware.

0013A computer program written in C language for performing the steps of determining the block type is contained in the Appendix.

0014Still further, as used herein, computer readable storage medium may comprise, for example; magnetic storage media such as a magnetic disk (such as a floppy disk) or magnetic tape; optical storage media such as an optical disc, optical tape, or machine readable bar code; solid state electronic storage devices such as random access memory (RAM), or read only memory (ROM); or any other physical device or medium employed to store a computer program.

0015Referring to Fig. 1, there is illustrated a block diagram of the present invention. It is noted that before utilizing the present invention, a scene is captured in digital form by any suitable means, such as by scanning a photograph, capturing a scene via a digital camera, composing an image using a software program or any other similar means (all of which are well known and are not disclosed in detail herein). The present invention will use the example of a byte sized pixel which provides 256 values, but other pixel sizes can be used. The digital image pixels are then input into any suitable page description language, such as a "PostScript" interpreter, configured so that images having all pictorial content exclude the values of 0 and 255 from the image; the purpose of which will later become readily apparent. Means of achieving such a condition are well known in the art and will not be discussed in detail herein. Given the above, a digital image having a plurality of pixels each having code values representing its color content is inputted into raster memory 10. The image is sent to and segmented by a block former 20 into 8 x 8 blocks of pixels (Fig. 2A is an example). To classify the block content, the 8 x 8 blocks of pixels from the block former 20 are inputted into a block analyzer 30 which determines the type of the block. The output of the block analyzer 30 is the 8x8 block and a parameter referred to as "block_type." In a preferred embodiment of the present invention, each block is classified into one of four types. The four types used are saturated text and line art only ("block_type"="text"), pictorial image only ("block_type" ="image"), both text and pictorial image ("block_type"="mixed"), or a block having a combination of only two different code values excluding 0 and 255 ("block_type"="bi-level"). It is clear that those skilled in the art may use a slightly different number of block types, at least one of which is text, depending on the application without departing from the scope of the invention. It facilitates understanding to note that each block type will have a unique Q-table specified by the Q-table selector 40, and that the "block_type" parameter for each block will be also included in the compressed bitstream that represents that block to specify to the decoder the Q-table to be used during decoding, as will later become apparent. The following describes the operation of the block analyzer 30.

0016If the block consists of saturated text or lines only, it will contain pixels with only values of 0 and 255. Therefore, for determining if the image block is text, the analyzer 30 checks if the block contains only values of 0 and 255. If it does, the analyzer 30 outputs "block_type"="text".

0017If the image block contains a mixed block, the image block will have at least one value between 0 and 255 inclusive in addition to at least one value equal to 0 or 255. Thus, for determining if the image block is a mixed block, the analyzer 30 determines if the block contains any values between 0 and 255 inclusive along with at least one value equal to 0 or 255. If it does, the analyzer 30 outputs "block_type"="mixed".

0018If the image block contains a bi-level image, the image block will have just two unique values selected from the range of 1 to 254. Thus, for determining if the image block is a bi-level block, the analyzer 30 finds first one value, and then a second value, both between 1 and 254 inclusive, but finds no third value when all pixels of a block have been examined. Additionally, it is required that the difference between the first and second value be at least some minimum, 16 for example, so that noise or other stray patterns are not needlessly classified. If such conditions prevail, the analyzer 30 outputs "block_type"="bi-level".

0019Finally, if the image block contains all image, the 8 x 8 image block will have values between 1 and 254 inclusive due to the result of the page description interpreter or any suitable agent excluding values of 0 and 255, as described above. Thus, for determining if the image block is all image, the analyzer 30 determines if the block contains at least three unique values between 1 and 254 inclusive. If it does, the analyzer 30 outputs "block_type"="image".

0020The complete logic employed in a preferred embodiment of the present invention to determine the block type is in the Appendix.

0021The comparator block 50 checks to determine if "block_type"= "text". If "YES", the contrast of the 8x8 input block is reduced by the contrast reducer 60 prior to the DCT operation to improve the compression efficiency. The contrast reducer utilizes the fact that the DCT transformation is much better suited to decorrelating low-contrast image data as opposed to the large transitions encountered in typical text blocks. By reducing the contrast of the block prior to the DCT transformation and quantization, a higher quality reconstruction of the input block can be obtained at the output for the same amount of compression. In general, the contrast reducer 60 changes all the pixels with a value of zero to a larger value of "LOW", and changes all the pixels with a value of 255 to a smaller value of "HIGH". In a preferred embodiment of the present invention, the contrast reducer 60 reduces the contrast of the input "text" block by choosing "LOW"=112 and "HIGH"=144. Other values for "LOW" and "HIGH" can be used based on various system considerations without departing from the scope of the invention. An example of the output of the contrast reducer 60 is shown in Fig. 2B. If the output of the comparator box 50 is "NO", i.e., the 8x8 block being encoded is not text, the input block is directly fed into the DCT processing unit 70 that converts the 8x8 array of pixel values into a corresponding 8x8 array of spatial frequency values or DCT coefficients (Fig. 2C is an example).

0022The DCT coefficients representing a particular block are inputted to the quantization unit 80 along with the Q-table selected by the Q-table selector 40 for that block based on its block type. The Q-table is an 8x8 array of quantizer step sizes with the entry at each location represented by a single byte of information (values between 1 and 255). Each location in the array is identified by an index (<i>k,l</i>), where <i>k</i> specifies the row number (ranging from 0 to 7), and <i>l</i> specifies the column number (ranging from 0 to 7). For a given quantization table specification, the quantization procedure used in a preferred embodiment of the present invention is identical to the one used in the JPEG compression standard and is described below. The elements of the Q-table are used to normalize the DCT coefficients, and the results are rounded to the nearest integer to create the output quantizer indices. For a given input DCT coefficient, the output of the quantizer unit 80 is the quantizer index that results from quantizing that coefficient with its corresponding step size. The Q-tables used in the quantization process are stored in the header and are used by the decoder during the dequantization process as will be explained later.

0023If "block_type"="text", the Q-table chosen in a preferred embodiment of this invention is given by Fig. 2D. As an example, the (0,0) entry (top left) for this table is 8. This Q-table has been designed to maximize the compression performance and minimize the quantization loss for a typical text block when employed in conjunction with a thresholding operation at the decoder that will be discussed later. Those skilled in the art may modify the Q-table values without departing from the scope of the invention, for example the value 14 at location (0,7) can be replaced by 15 without a significant impact on performance. Also, depending on the exact configuration of the contrast reducer, the Q-table might be different from the one in Fig. 2D.

0024If "block_type"="mixed", the Q-table chosen in a preferred embodiment of this invention has a constant value of 1 at each location as illustrated by Fig. 2H. This is the highest quality encoding that can be performed with quantizing the DCT coefficients and it is used in this mode to preserve the quality of the reconstructed image to the highest degree possible.

0025If "block_type"="bi-level", the Q-table chosen in a preferred embodiment of this invention has a constant value of 8 at each location as illustrated by Fig. 2I. Finally, if the "block_type"="image", any well known JPEG compression Q-table utilized in the prior art to compress pictorial images can be used.

0026Once the image block is quantized, the quantized values are sent to and encoded via an entropy encoder 90 into a binary bit stream by any suitable means. The output of the block analyzer, namely the "block_type", is also inputted to the entropy coder 90 to be included in the bit stream as will be described later. In a preferred embodiment of this invention, the quantized DCT coefficients are encoded in a method identical to the one used in the JPEG standard. Briefly, in this method, first the quantized DC value of the block is encoded by using a DC Huffman code table to encode the difference between the quantized DC value of the current block and that of the previous block. Next, the quantized AC values are encoded using an AC Huffman code table to encode the {runlength/amplitude} pairs. If desired, the "block_type" parameter can also be used to select a specific set of AC and DC Huffman tables that may be better suited to the particular type of the block being encoded.

0027The information about the block type is needed at the decoder to select the appropriate decoding process and should be included in the compressed image file. In a preferred embodiment of this invention, the "block_type" parameter of each block is represented by a 2-bit fixed-length binary code that identifies one of the possible 4 block types. These 2-bit codewords are concatenated together in a single file that is included as part of the compressed image header. Alternatively, this information may be sent as a separate file or by other means without departing from the scope of the invention. Another approach is to use the entropy encoder to append the information about the block type to the beginning of the bit stream that represents the compressed block information.

0028Once compressed, the binary bit stream is either stored or transmitted through a low bandwidth communication channel.

0029The decoder is depicted in Fig. 3. First, the Huffman tables and the Q-tables that have been used at the encoder to encode the various block types are extracted 100 from the header. In the case that the information about the "block_type" parameter of each block has been stored in the header, that information is also extracted at this stage. Otherwise, the entropy decoder 110 decodes the "block_type" parameter that has been appended to the beginning of the bit stream for that block. The "block_type" parameter is then used to select the appropriate Huffman decoding table to decode the bit stream that corresponds to that particular 8x8 block. Next, the decoded quantizer indices are inputted to the dequantization step 120. The objective of the dequantization process 120 is to convert the quantizer indices back into the actual quantized values. In a preferred embodiment of the present invention, a dequantization procedure identical to the one used in the JPEG compression standard is employed. In this simple procedure, the dequantizer multiplies each quantizer index by its corresponding quantization step size to get the dequantized value. The quantizer step sizes are given by the elements of the Q-table corresponding to that particular block type, and have already been extracted from the header by the decoder. An example of the output of the dequantizer for the example block of Fig. 2A is given in Fig. 2E.

0030An inverse discrete cosine transform (IDCT) processor 130 then reverses the DCT transform. An example of the output of the IDCT is shown in Fig. 2F for the example text block of Fig. 2A.

0031A feature of the present invention is a thresholding operation that is applied to the output of the IDCT for those blocks that have been classified as "text". This preserves the boundary information of the text and creates higher quality outputs at greater compression than those produced by the prior art where the text is compressed and decompressed in the same way as other types of image data. If the "block_type"="text", the 8x8 output of the IDCT is supplied to a thresholder 140, which converts all the values below 128 to a value of 0 and converts all the values at or above 128 to a value of 255. This thresholding, in combination with the specific Q-table for text, preserves the sharp edges of the text. Figure 2G shows an example of the output of the thresholder 140 when its input is the example of Fig. 2F. It is to be understood that the threshold could be modified to other values without departing from the scope of the invention, as those skilled in the art will be able to determine. For all other block types, the IDCT values are rounded to 8 bits and are clipped to the range of (0,255) to constitute the reconstructed 8x8 block.

0032Finally, the 8x8 reconstructed blocks are sent to raster memory 160 that re-assembles the blocks of data back into its original form and size.

0033Other aspects of the invention include: <ul id="ul0002" list-style="none"><li>1. The method further comprising determining if the block contains only values of 0 and 255 which indicates saturated text and/or line art by.</li><li>2. The method further comprising determining if the block contains three unique values between 1 and 254 which indicates pictorial imagery.</li><li>3. The method further comprising determining if the block contains only two unique values selected from a range of 1 to 254 which indicates bi-level image.</li><li>4. The method further comprising determining if the block contains at least one value between 0 and 255 inclusive in addition to at least one value equal to 0 or 255 which indicates both saturated text and/or line art imagery and pictorial imagery.</li><li>5. The method further comprising using a first 8x8 quantization matrix if the block is saturated text and/or line art, wherein the first 8x8 quantization matrix is<maths id="math0001" num=""><img file="EP0989518A2_D0001.tif" /></maths></li><li>6. The method further comprising using a second 8x8 quantization matrix if the block is bi-level, wherein the second quantization matrix is 8 at each location.</li><li>7. The method further comprising using a third 8x8 quantization matrix if the block is both saturated text and/or line art, and pictorial imagery, wherein the third quantization matrix is 1 at each location.</li><li>8. The method wherein step (a) includes receiving 8x8 blocks of pixels.</li><li>9. The method wherein the steps of compressing the block of saturated text and/or line art, if any, according to a first predetermined compression method; of compressing the pictorial imagery, if any, according to a second predetermined compression method; and of compressing the other types of imagery, if any, according to other predetermined compression methods include using JPEG compression with a first, second, and other predetermined quantization matrices.</li><li>10. The method further comprising, prior to the step of compressing the block of saturated text and/or line art, if any, according to a first predetermined compression method, applying a contrast reducer to the saturated text and/or line art.</li><li>11. The method further comprising transmitting a code in a header for each 8x8 block which code identifies to a decoder whether the 8x8 block is saturated text and/or line art, pictorial imagery, or the other types of imagery.</li><li>12. The method further comprising transmitting in the compressed image header a set of concatentated codewords which code identifies to a decoder whether each 8x8 block is saturated text and/or line art, pictorial imagery, or the other types of imagery.</li><li>13. The method wherein the step of analyzing the block content to determine if all or any combination of the saturated text and/or line art, pictorial imagery or other types of image data are present includes using text and pictorial images, and bi-level images as the other types of image data.</li><li>14. The method further comprising determining if the block contains only values of 0 and 255 which indicates saturated text and/or line art by.</li><li>15. The method further comprising determining if the block contains three unique values between 1 and 254 which indicates pictorial imagery.</li><li>16. The method further comprising determining if the block contains only two unique values selected from a range of 1 to 254 which indicates bi-level image.</li><li>17. The method further comprising determining if the block contains at least one value between 0 and 255 inclusive in addition to at least one value equal to 0 or 255 which indicates both saturated text and/or line art imagery and pictorial imagery.</li><li>18. The method further comprising using a first 8x8 quantization matrix if the block is saturated text and/or line art, wherein the first 8x8 quantization matrix is<maths id="math0002" num=""><img file="EP0989518A2_D0002.tif" /></maths></li><li>19. The method further comprising using a second 8x8 quantization matrix if the block is bi-level, wherein the second quantization matrix is 8 at each location.</li><li>20. The method further comprising using a third 8x8 quantization matrix if the block is both saturated text and/or line art, and pictorial imagery, wherein the third quantization matrix is 1 at each location.</li></ul><img file="EP0989518A2_D0003.tif" />