Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
2000-02-07
2004-02-03
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Adaptive coding
Reexamination Certificate
active
06687410
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention relates to the field of data compression.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever. Sun, Sun Microsystems, and MAJC, are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.
2. Background
Computer systems are increasingly being used to play back multimedia (audio and video) files. Current computer systems are often unable transfer data quickly enough from storage to allow adequate playback. To solve this problem, the multimedia data is compressed for transmission and decompressed for playback. However, some compression schemes are not suitable for environments where there is little processing power available.
Computers are often used to process, play back, and display video data. This video data may come from sources such as storage devices, on-line services, VCRs, cable systems, broadcast television tuners, etc. Video data is memory intensive, that is, video data requires large amounts of memory for storage and use by a computer system.
To reduce the transmission bandwidth and memory requirements when working with video data, various compression schemes have been developed so that less storage space is needed to store video information and a smaller bandwidth is needed to transmit it. Prior art video compression schemes include Motion JPEG, MPEG-1, MPEG-2, Indeo, Quicktime, True Motion-S, CinePak, etc.
Many prior art compression schemes rely on fast processing or powerful processors to decompress image or audio data. Many current systems exist where there is very little processing power available at the point of display. For example, a so called “thin” client that is part of a computer system may lack sophisticated processing power. A scheme is required that can compress and decompress data with little computational effort.
SUMMARY OF THE INVENTION
The present invention is a compression-scheme for compressing audio and video data. For image compression, an image is divided into blocks of pixels. The blocks may be 4×4 pixels, 5×5 pixels, 8×8 pixels, etc. A number of algorithms are used on each block to determine the best method of compressing that block of pixels. In one embodiment, the invention performs tests on the blocks. In one embodiment, the pixels of the block are compared to analogous pixels in a previous block. For example, the top left pixel of a block is compared to the top left pixel of the previous block and so on. If all of the pixels are approximately equal to the corresponding pixels in the previous block, then no data need be sent for that block, instead, the previous data can be used. In a second test, it is determined if all of the pixels in a block are approximately equal to a mean pixel value. If so, then only one color value need be transmitted for the block. In a third test, it is determined if quantization of the pixels via companding result in an acceptable representation of the pixel values. If so, the quantization is used.
The present invention uses quantization (companding) codes that are proportional to the logarithm of the magnitude of the range quantized, computation of a magnitude byte that permits rapid discovery of the number of bits used for quantization of a block, recursive packing and unpacking of quantized pixel data, and two-dimensional paths (even 4 parallel paths) through the 4 by 4 or 8 by 8 block. In the case of image processing, the companding algorithm is initialized for each block using one byte of pixel data, which represents the unquantized representation of the initial pixel of the block. Quantization (companding) proceeds on a pixel-by-pixel basis for each pixel in the block. Thus there are only a finite number of pixels processed for a given block before the quantization algorithm is reset using the unquantized representation of the initial pixel of the next block. Because only a finite number of pixels is processed, there is a high probability that only a limited range of quantization codes will be used for a given block. Therefore, there is an excellent chance that the quantization codes for a given block will fit into one or two bits, not the maximum of four bits. This effect permits compression of the quantization codes via the recursive packing algorithm.
REFERENCES:
patent: 4809067 (1989-02-01), Kenichi et al.
patent: 4984076 (1991-01-01), Watanabe et al.
patent: 5661822 (1997-08-01), Knowles et al.
patent: 5721791 (1998-02-01), Maeda et al.
patent: 5739861 (1998-04-01), Music
patent: 5754698 (1998-05-01), Suzuki et al.
patent: 5847766 (1998-12-01), Peak
patent: 5862261 (1999-01-01), Lee
patent: 6014181 (2000-01-01), Sun
patent: 6023295 (2000-02-01), Pau
patent: 6031937 (2000-02-01), Graffagnino
patent: 6072830 (2000-06-01), Proctor et al.
patent: 6101276 (2000-08-01), Adiletta et al.
patent: 6233017 (2001-05-01), Chaddha
patent: 6275620 (2001-08-01), de Queiroz et al.
patent: 6281942 (2001-08-01), Wang
patent: 6337881 (2002-01-01), Chaddha
patent: WO 93 14600 (1993-07-01), None
IBM Technical Disclosure Bulletin, IBM Corp., New York, vol. 34 No. 1, Jun., 1999 (Jun. 1991), pp. 289-291, XP000210220, ISSN: 0018-8689 p. 291, line 5-last line.
LandOfFree
Method and apparatus for compression and decompression of data 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 compression and decompression of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for compression and decompression of data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3345454