Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-11-30
2004-03-23
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S166000
Reexamination Certificate
active
06711299
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to digital image compression/decompression, and particularly, to a wavelet-based system and method of image compression and decompression.
BACKGROUND OF THE INVENTION
Nearly every computer user needs to store, transfer, and view images. These images include still images, or pictures, as well as video images, which are sequences of still images displayed in a manner that depicts motion. The enormous size of image files leads to serious file management limitations. For example, a single still image (equivalent to a video frame) displayed by a rectangular array of picture elements (pixels) arranged in 640 rows and 800 columns, with the color of each pixel represented by twenty-four bits, would require over 1.5 megabytes of digital memory to store. One solution to this problem is high-quality data compression technology. Essentially, image compression mathematically transforms a grid of image pixels into a new, much smaller set of digital values holding the information needed to regenerate the original image or data file.
In addition to imaging systems, compression technology can be incorporated into “video on demand” systems, such as video servers. Compression technology can also be applied to streaming video, which is the real-time capture and display of video images over a communications link. Applications for streaming video include video telephones, remote security systems, and other types of monitoring systems.
Several standards for compressing real-time video currently exist. The H.263 standard for real-time video is an industry standard based upon the discrete co-sign transform (DCT). DCT is also the basis for both of the public domain image compression standards, MPEG (Motion Picture Experts Group) and JPEG (Joint Photographic Experts Group). Although the DCT approach performs interframe coding adequately, its compression ratio and speed can be improved upon.
Various other types of data compression have been developed in recent years. Conventional data compression techniques are generally referred to as being either “lossless” or “lossy”, depending upon whether data is discarded in the compression process. Examples of conventional lossless compression techniques include Huffman encoding, arithmetic encoding, and Fano-Shannon encoding. With a lossless compression, the decompression process will reproduce all bits of the original image. Lossless compression is important for images found in such applications as medical and space science. In such situations, the designer of the compression algorithm must be very careful to avoid discarding any information that may be required or even useful at some later point.
Lossy compression, in contrast, provides greater efficiency over lossless compression in terms of speed and storage, as some data is discarded. As a result, lossy techniques are employed where some degree of inaccuracy relative to the input data is tolerable. Accordingly, lossy compression is frequently used in video or commercial image processing. Two popular lossy image compression standards are the MPEG and JPEG compression methods.
The wavelet transform has proven to be one of the most powerful tools in the field of data compression. Theoretically, the wavelet transformation is lossless, but since all computers have only finite precision even when using floating point calculations, most of the transformations are lossy in practice. On the other hand, integer calculations are much faster than floating point for virtually all computers; and integer computations are much easier to implement in hardware, which is more important in some applications. While integers require less memory than real numbers, the direct use of integers in conventional wavelet transforms and their inverses typically causes an unacceptable loss of accuracy. Accordingly, there is a need for a wavelet-based compression technique that permits lossless or near-lossless data compression, yet retains the speed and memory advantages of integer arithmetic.
SUMMARY OF THE INVENTION
It is an advantage of the present invention to provide a system and method of wavelet-based data compression that permits integer computations in a computer without significant loss of accuracy. This is accomplished by using an integer reversible wavelet transform that possesses a property of precision preservation (PPP). The integer reversible transform greatly reduces the computer resources needed to compress and decompress images, as well as the time required to perform the same.
It is an advantage of the present invention to provide a system and method of wavelet-based image compression that is suitable for both still and video images.
It is also an advantage of the present invention to provide a system and method of image compression that is capable of selectively performing lossless and lossy compression of either color or gray-scale images.
According to one aspect of the invention, a wavelet-based image compression method can be implemented using a software program. Compression is accomplished by performing a wavelet transform on an input digital image. The resulting wavelet components are compared to a threshold value; coefficients falling below the threshold are discarded. The remaining coefficients are quantized. The quantized coefficients are then compressed using an entropy encoding technique, such as arithmetic, run length, or Huffman encoding, or a combination of Huffman and run length encoding. The wavelet transform can be an integer reversible wavelet transform derived using a lifting scheme or correction method, while the quantization scheme can be sub-band oriented. To further enhance the speed of the compression scheme, input color image pixels can be reduced using a color table. In addition, color pixels can be transformed between color spaces prior to wavelet transformation.
According to another aspect of the invention, a corresponding method of decompression is provided.
According to another aspect of the present invention, a compression method is provided that allows user selected portions of an image to be compressed to different image qualities, thereby permitting non-uniform image compression.
According to another aspect of the present invention, a compression method is provided that permits compression quality to be based on image specific parameters.
According to another aspect of the present invention, a method of compressing images using a “split and merge” technique is provided.
According to further aspect of the present invention, an image compression system includes a compressor configured to generate a compressed image based on an integer wavelet transform derived using either a lifting scheme or correction method. The compressor can be implemented using one or more electronic components, such as application specific integrated circuits (ASICs), microprocessors, discrete logic components, or any combination of the aforementioned.
According to another aspect of the present invention, a corresponding image decompression system is provided.
REFERENCES:
patent: 5014134 (1991-05-01), Lawton et al.
patent: 5101446 (1992-03-01), Resnikoff et al.
patent: 5241395 (1993-08-01), Chen
patent: 5333212 (1994-07-01), Ligtenberg
patent: 5381180 (1995-01-01), Keith
patent: 5412741 (1995-05-01), Shapiro
patent: 5414780 (1995-05-01), Carnahan
patent: 5420636 (1995-05-01), Kojima
patent: 5453945 (1995-09-01), Tucker et al.
patent: 5467110 (1995-11-01), White et al.
patent: 5495292 (1996-02-01), Zhang et al.
patent: 5600373 (1997-02-01), Chui et al.
patent: 5604824 (1997-02-01), Chui et al.
patent: 5615287 (1997-03-01), Fu et al.
patent: 5640159 (1997-06-01), Furlan et al.
patent: 5682152 (1997-10-01), Wang et al.
patent: 5748786 (1998-05-01), Zandi et al.
patent: 5754793 (1998-05-01), Eom et al.
patent: 5757974 (1998-05-01), Impagliazzo et al.
patent: 5764805 (1998-06-01), Martucci et al.
patent: 5828849 (1998-10-01), Lempel et al.
patent: 5880856 (1999-03-01), Ferriere
patent: 5881176 (1999-03-01), Keith et al.
patent: 5901249 (1999-05-01), Ito
p
Chao Hongyang
Fisher Howard P.
Fisher Paul S.
Hua Zeyi
Johnson Timothy M.
Ostrolenk Faber Gerb & Soffen, LLP
Vianet Technologies, Inc.
LandOfFree
Wavelet transformation of dithered quantized/reduced color... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Wavelet transformation of dithered quantized/reduced color..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wavelet transformation of dithered quantized/reduced color... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3203655