Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1998-11-13
2003-05-13
Wu, Jingge (Department: 2623)
Image analysis
Image compression or coding
Adaptive coding
C382S250000
Reexamination Certificate
active
06563955
ABSTRACT:
The present invention is directed to a method and apparatus for compressing digital image data such that data transmission speed matches the speed of an associated modem. More specifically, the invention accomplishes image transmission by implementing multiple compressors, each of which compresses image data to achieve a different output image quality level. Throughout transmission, the invention continues to send the image data to the compressor that will process it such that an appropriate level of image quality will be retained, while simultaneously outputting it at a speed that will result in efficient serial data transmission.
BACKGROUND OF THE INVENTION
The transmission of electronic data via facsimile machines and similar devices has become quite common, and efforts to transmit significantly larger volumes of this data within equal and even substantially shortened periods of time are constantly being made. This is true not only to allow data to be sent from one location to another at faster speeds and thereby cause less inconvenience to the user, but to enable more complex data to be transmitted between the same locations without drastically increasing the required transmission time. For example the facsimile transmission time for a detailed halftoned image will be many times more than that of a simple sheet of black text on a white page when using the same fax machine. By the same token, fax transmission of a color image will require an even greater amount of time than its greatly detailed halftoned counterpart.
The “sending” portion of fax transmission includes scanning the original image and generating a corresponding digital image thereof, followed by serial transmission of digital image data to a receiving fax machine. Without any form of data reduction, transmission of color image data files via facsimile would require extensive resources—very fast modems and/or large buffers—and would still take a great deal of time, thereby causing such transmission to become very expensive and therefore, impractical. Thus, some form of data compression is typically employed prior to fax transmission of color image data.
The JPEG (Joint Photographic Experts Group) standard provides a well known method of compressing electronic data. JPEG uses the discrete cosine transform (DCT) to map spatial data into spatial frequency domain data. Briefly, first JPEG requires transforming an 8×8 block of pixels into a set of 8×8 coefficients using the DCT to produce a DC coefficient (DCC), and a set of AC coefficients (ACCs). The DCC and ACCs are quantized, rounded to the nearest whole number and arranged in a one dimensional vector which is encoded into a bit stream.
Because color image data is so complex, ordinary data compression schemes require high compression ratios to be applied in order to complete the transmission within an acceptable time frame. Higher compression ratios lead to more data loss, typically at the higher end of the frequency range.
Successful fax transmission requires a proper correspondence between the compression ratio being applied to the image and the CPU speed of the sending fax machine. In other words, if the compression ratio is smaller than necessary for a given CPU speed, the CPU will have to be slowed down, or the data will have to wait to be transmitted and an appropriately sized buffer will be required. On the other hand, high compression levels mean that very few bits will be generated and less data will have to be sent through the modem. If the compression ratio is high relative to the CPU speed the modem will become idle waiting for the CPU to complete image processing and transmit more data. Since modems are typically configured to detect a large lapse in data transmission as the end of transmission, this large idle time typically causes the modem to disconnect. Thus, it is advantageous to continue the stream of data from the sending fax machine to the receiving fax machine, and eliminate gaps in the data stream. One way to do this is obviously to implement a faster JPEG compressor which can keep the data moving through the modem even if a high compression ratio is used. However, this solution results in significant cost increases and may be impractical.
One way to maintain proper compression ratio to clock speed correspondence is to provide multiple compressors to which portions of the digital image data may be transmitted. If the portion of the image being processed contains a lot of pictorial or other data that requires high quality reproduction, that data should be processed by the compressor which will provide the best image quality. However, if the portion of the image being processed contains text or other data that does not require high quality reproduction, that image data can be routed to a compressor that will produce a lower quality output to benefit from the fact lower quality output can be produced by the compressor at a much faster processing speed. In fact when text or other simple data is being processed, differences between image quality that is produced by a high quality output producing processor and that produced by a lower quality output producing processor will hardly be noticed by the human eye.
All pixels, and therefore blocks of pixels, are defined using a certain number of bits. In an image processing operation known as vector quantization (VQ), a block of X×Y pixels is mapped to a single “codeword” which is defined using a smaller number of bits than the number required by the original block. Codewords are stored in transmitting, receiving and storage devices, and each codeword is associated with a pre-defined set of image data. The codeword to which each pixel block is mapped is that which is associated with image data that most closely matches the image data in the pixel block. The typical process includes mapping the pixel block to a codeword, storing the codeword or transmitting it to a receiving device, and then mapping the codeword back to image data when it is retrieved from storage or received at the receiving device. Since codebook storage and codeword transmission require less space and time than storage and transmission of original image data, this process greatly reduces the resources required to reproduce the original image data.
There are typically many more combinations of pixel blocks than there are available codewords, and as indicated by the term “quantization” several input blocks can be mapped to a single codeword. For a fixed number of codewords, increasing the size of the pixel block reduces the quality of mapping and reconstruction since more actual image data must be mapped to the same number of codewords. Some drawbacks of VQ are that codebook design is often very complex, and that large amounts of time are usually required to search through the codebook and to match blocks to the appropriate codeword. While codebook design can be performed off-line, block matching searches must be performed on-line.
In hierarchical vector quantization (HVQ), block matching searches are performed two samples at a time. Thus, look up tables (LUTs) can be used directly to perform HVQ in two or more stages. In the first stage, two image pixels are mapped to one codeword, reducing the number of samples by a factor of 2. In the next stage, the process is repeated to map pairs of codewords to single codewords. Preferably, codewords are grouped in a direction perpendicular to the one used for the previous level. As the process continues, the resulting codewords are mapped to larger and larger amounts of data.
HVQ allows for a rough approximation of the content of each image block using simple look-up table operations. The final codeword represents a block approximation and can, therefore be directly mapped to other quantities which describe certain characteristics of the approximated block, such as block activity. HVQ codebook design methods follow standard VQ codebook design algorithms and is usually performed by designing the codebooks for a single stage at a time.
The following disclosures may be relevan
Dudley Mark Z.
Waites Michelle W.
Wu Jingge
Xerox Corporation
LandOfFree
Method and apparatus for analyzing image data to use... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for analyzing image data to use..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for analyzing image data to use... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3075531