Data compression is required in data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links, where the time to transmit is long, or where bandwidth is limited. Another use for compression is in data storage, where the amount of media space on which the data is stored can be substantially reduced with compression. Yet another application is a digital copier or a multi-function device (MFD) where an intermediate storage for collation, reprint or any other digital copier/MFD functions is desired. Generally speaking, scanned images, i.e., electronic representations of hard copy documents, are commonly large, and thus are desirable candidates for compression.
Many different compression techniques exist, and many are proprietary to individual users. However, standards are desirable whenever intercommunication between devices will be practiced. Particularly with the advent of proliferating network communication, where formerly dissimilar devices are required to communicate, a common standard will be required. An example is the current desirability of FAX machines to be able to communicate with printers. Currently, compression standards are generally distinct for different devices.
Three major schemes for image compression are currently being studied by international standardization groups. A first, for facsimile type image transmission, which is primarily binary, is under study by the JBIG (Joint Binary Image Group) committee, a second for TV and film, a standard is worked on by the MPEG (Motion Pictures Expert Group). For non-moving general images, i.e., still images which are more general than the ones covered by JBIG, the group JPEG (Joint Photographic Expert Group) is seeking to develop a device independent compression standard, using an adaptive discrete cosine transform scheme.
ADCT (Adaptive Discrete Cosine Transform, described for example, by W. H. Chen and C. H. Smith, in "Adaptive Coding of Monochrome and Color Images", IEEE Trans. Comm., Vol. COM-25, pp. 1285-1292, November 1977), as the method disseminated by the JPEG committee will be called in this application, is a lossy system which reduces data redundancies based on pixel to pixel correlations. Generally, in images, on a pixel to pixel basis, an image does not change very much. An image therefore has what is known as "natural spatial correlation". In natural scenes, correlation is generalized, but not exact. For example, noise makes each pixel somewhat different from its neighbors.
ADCT transforms are well known, and hardware exists to perform the transform on image data, e.g., U.S. Pat. No. 5,049,991 to Nihara, U.S. Pat. No. 5,001,559 to Gonzales et al., and U.S. Pat. No. 4,999,705 to Puri. The primary thrust of these particular patents, however, is moving picture images, and not document images.
Generally, as shown in FIG. 1, the process of compression requires a tile memory 10 storing an M.times.M tile of the image. Square tiles are used in the description based on the JPEG recommendations, but it may be noted that the inventive method can be performed with any form of tiling. From the portion of the image stored in tile memory, a frequency space representation of the image is formed at transformer 12 using the discrete cosine transform (DCT). In the following we will refer to the DCT data as frequency space data. Hardware implementations are available, such as the C-Cube Microsystems CL550A JPEG image compression processor, which operates in either the compression or the decompression mode according to the proposed JPEG standard. A divisor/quantization device 14 is used, from a set of values referred to as a Q-Table, stored in a Q table memory 16, so that a distinct Q table value is divided into the DCT value, returning the integer portion of the value as the quantized DCT value. A statistical encoder 20 further compresses the quantized DCT values to generate the compressed image that is output for storage, transmission, etc.
The current ADCT compression method divides an image into M.times.M pixel blocks, where M=8. The selection of M=8 is a compromise, where the larger the block given, the higher the compression ratio obtainable. However, such a larger block is also more likely to have non-correlated pixels within the block, thereby reducing the compression ratio. If the block was smaller, greater correlation within the block might be achieved, but less overall compression would be achieved. Particularly within a document image, edges of the image are more likely to be encountered within an 8.times.8 block, than would be the case for a scene forming a natural image.
Compression schemes tend to use a set of basis functions to utilize the intra block correlations. Basis functions define the data as a projection onto a set of orthogonal functions on an interval. ADCT uses cosine functions as the basis functions and the Discrete Cosine Transform (DCT) as the projection step. In the first step of the ADCT standard, the image is tiled into 8.times.8 blocks. Within each block, a set of 64 DCT coefficients is determined for the pixels in the block. The DCT coefficients represent the coefficients of each cosine term of the discrete cosine transform of the 8.times.8 block.
Referring now to FIG. 2A, an array of 64 gray level values representing 64 pixels in an 8.times.8 block of the image is shown. This 8.times.8 block is transformed according to the JPEG ADCT specifications giving the DCT coefficients shown in FIG. 2B. These coefficients still completely describe the image data of FIG. 2A, but in general larger values will now cluster at the top left corner in the low spatial frequency region. Simultaneously, in the vast majority of images as the frequency of the image increases, the coefficient values in the lower right hand portion of the grid tend towards lower values and zero.
Generally, the human eye tends to see low frequencies in an image better than high frequencies. At higher frequencies, changes from amplitude to amplitude are unnoticeable, unless such changes occur at extremely high contrast. This is a well known effect of the Human Visual System and extensively documented, see e.g. "Visual Performance and Image Coding" by P. Roetling, Proceedings of the S.I.D. 17/2 pp. 111-114 (1976). The ADCT method makes use of the fact that small amplitude changes at high frequencies can be generally ignored.
The next step in the ADCT method involves the use of a quantization or Q-matrix. The Q-matrix shown in FIG. 2C is a standard JPEG-suggested matrix for compression, but ADCT as well as the proposed inventive method can also operate using other Q-matrices (or Q-Tables). The matrix incorporates the effect that lower frequencies are roughly more important than high frequencies by introducing generally larger quantization steps, i.e. larger entries, for larger frequencies. However, the table also attempts to internally construct some desirable variations from the general assumption. Accordingly, the values in the table do vary with frequency, where the exact variation might be a function of the human visual system, of the document type expected, i.e.: photo, text, graphic, etc., or of some other application dependent parameter. Each of the DCT values from FIG. 2B is divided by a corresponding Q-matrix value from FIG. 2C giving quantized DCT (QDCT) values by way of: EQU QDCT[m][n]=INT{DCT[m][n].div.Q-Table[m][n]+1/2}
where INT{A} denotes the integer part of A
The remainder from the division process is discarded, resulting in a loss of data. Here and in the following we use the term division to describe the process detailed in ADCT including the methods for handling truncation and round-off. Furthermore, since the Q values in the lower right hand portion of the table tend to be high, most of the values in that area go to zero, unless there were extremely high amplitudes of the image at the higher frequencies.
After deriving the quantized set of DCT values, shown in FIG. 2D, pixels are arranged in the order of a space filling zigzag curve shown in FIG. 2E and a statistical encoding method, such as the Huffman process, is used to generate the transmitted signal which in this example is described using 171 bits. This statistical coding is performed in a lossless way and the only loss introduced in the compression is the one generated by the quantization of the DCT coefficients using the Q-Table.
To decompress the now-compressed image, and with reference to FIG. 1, a series of functions or steps are followed to reverse the process described. The Huffman encoding is removed at decoder 50. The image signal now represents the quantized DCT coefficients, which are multiplied at signal multiplier 52 by the Q table values in memory 54 in a process inverse to the compression process. At inverse transformer 56, the inverse transform of the discrete cosine transform is derived, and the output image in the spatial domain is stored at image buffer 58.
The actual amount of compressed data, or the compression ratio can be seen to be a function of the image itself, and therefore cannot be predicted. Unfortunately, this leads to difficulties in designing systems that handle compressed image, in terms of selecting buffer size, bandwidth, etc.
All of the references cited herein above are incorporated by reference for their teachings.
USPTO Backgrounds
USPTO Backgrounds