Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-04-19
2001-08-07
Britton, Howard (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240180
Reexamination Certificate
active
06272180
ABSTRACT:
FIELD OF THE INVENTION
This present invention relates to the transmission and storage of images, and in particular, to interframe video encoding and decoding.
BACKGROUND OF THE INVENTION
In video compression technology, interframe coding (e.g. motion predictive coding) is most often used to remove temporal redundancy in the video sequence. For example, the most popular video coding standards, including H.261, MPEG-1, MPEG-2, H.263, and the new MPEG4 standard, all use motion predictive coding to remove temporal redundancy. In order to facilitate interframe decoding, frame memory is usually required to store a reference frame(s) (e.g., a previous frame). The cost of this frame memory can be a very significant part of a digital video decoder, especially for higher-resolution video. By far, the memory cost predominates in the cost of an HDTV MPEG-2 decoder.
Many researchers have attempted to reduce the memory requirements for reference frame storage. Generally, these methods require that the reference frames be compressed prior to storage in the decoder frame memory and then decompressed when they are needed to perform interframe decoding. Thus the common elements of systems implementing these methods are an image compressor, a compressed image storage memory, and an image decompressor.
The earliest such systems simply downsampled the reference frames prior to storage. For instance, U.S. Pat. No. 5,614,952 proposes that reference frames be either subsampled at a lower resolution, or that pixel values be truncated to a lower precision. U.S. Pat. No. 5,825,424 implements this method in a configurable processor that can be used in different configurations with different amounts of memory. Systems such as these are relatively low in complexity, but tend to suffer greatly from drift. Drift typically manifests itself as visible temporal cycling in reconstructed picture quality, due to the errors introduced in interframe decoding by throwing away part of the reference information during downsampling.
Later systems added complexity in an attempt to combat drift. U.S. Pat. No. 5,777,677 proposes Hadamard transforming a reference frame and quantizing the transform to achieve compression. European Patent Application 0,794,673 A2 proposes multiplying image blocks by a one-dimensional “Harr” transform matrix and quantizing the product to achieve compression. U.S. Pat. No. 5,680,129 codes pixel values directly with a predictive coder. European Patent Application 0,778,709 A1 codes pixel values directly with an adaptive pulse-code modulation technique. And European Patent Application 0,687,111 A2 compresses reference frames using an MPEG-like approach with a DCT, quantizer, and variable-length coder.
SUMMARY OF THE INVENTION
In U.S. patent application Ser. No. 08/975,922, I proposed a method having relatively low complexity and low drift, using a Haar block-based two-dimensional wavelet transform followed by compression using the Set Partitioning In Heirarchical Trees (SPIHT) algorithm. For details on the SPIHT algorithm, see Said and Pearlman, “A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees,”
Trans. On Circuits and Systems for Video Technology
, Vol. 6, No. 3, pp. 243-250, Jun. 1996. The present disclosure includes a further improvement on this idea, one that simplifies compression and decompression, and is more suitable for hardware implementation.
The SPIHT algorithm and other similar embedded coding techniques achieve compression by exploiting the hierarchical and contextual redundancies present in a wavelet transform coefficient array. The present invention avoids the complexity of these methods while achieving similar performance. The present invention recognizes, for the first time, that the bit planes of a relatively small wavelet transform coefficient array can be efficiently coded with a run-length encoder, if the coefficients are first reordered to group coefficient subbands with similar expected bit-level run-length statistics together.
Thus, in one aspect of the present invention, a method for compressing a digital image is disclosed. This method comprises wavelet transforming a block of data from a digital image, thereby generating a multiple-subband transform coefficient array. The coefficients of the transform coefficient array are then reordered so as to group coefficient subbands with similar expected bit-level run-length statistics together. The reordered coefficients are then coded using an embedded run-length encoder.
In another aspect of the present invention, a method for storing and retrieving reference frames in a digital video decoder is disclosed. This method comprises the steps of dividing each reference frame to be stored into a group of compression blocks, and storing a wavelet-transformed and embedded run-length coded version of each compression block in a compressed block memory. The method also entails the step of retrieving a specified compression block by run-length embedded decoding and inverse wavelet transforming the version of that block stored in the compressed block memory, when that compression block is needed by the decoder.
In yet another aspect of the present invention, a digital video decoder having a reference frame storage and retrieval subsystem is disclosed. The reference frame storage and retrieval subsystem comprises a compressed block memory, and a compressor for block-wise compressing reference frame information into the compressed block memory. The compressor stores reference frame information from a given block of a reference frame in a wavelet-transformed, embedded run-length coded format. The subsystem further comprises a decompressor for block-wise decompressing reference frame information out of the compressed block memory as needed by the decoder.
REFERENCES:
patent: 5262854 (1993-11-01), Ng
patent: 5436666 (1995-07-01), Astle
patent: 5526295 (1996-06-01), Astle
patent: 5539664 (1996-07-01), Haghighi
patent: 5585852 (1996-12-01), Agarwal
patent: 5614952 (1997-03-01), Boyce et al.
patent: 5635985 (1997-06-01), Boyce et al.
patent: 5646686 (1997-07-01), Pearlstein
patent: 5680129 (1997-10-01), Weinberger et al.
patent: 5764374 (1998-06-01), Seroussi et al.
patent: 5767907 (1998-06-01), Pearlstein
patent: 5777677 (1998-07-01), Linzer et al.
patent: 5808683 (1998-09-01), Tong et al.
patent: 5818530 (1998-10-01), Canfield et al.
patent: 5825424 (1998-10-01), Canfield et al.
patent: 6130911 (2000-10-01), Lei
patent: 0794673A2 (1996-09-01), None
patent: 0778709A1 (1997-06-01), None
patent: 0782345A2 (1997-07-01), None
patent: 0794675A2 (1997-09-01), None
patent: 0794673A2 (1997-09-01), None
patent: 0961494A1 (1999-12-01), None
patent: 0687111A2 (1995-12-01), None
patent: 2310101A (1997-08-01), None
patent: WO97/36376 (1997-10-01), None
Franco Lotti, Bruno Aiazzi, Stefano Baronti and Andrea Casini, “Content-Driven Pyramid Compression of Medical Images for Error-Free Archival and Progressive Transmission,” May-Jun. 1995, pp. 301-310.
“An SDTV Decoder with HDTV Capability: An All-Format ATV Decoder”, by Larry Pearlstein, John Henderson and Jill Boyce, pp. 422-434.
“A New, Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees”, by Amir Said and William A. Pearlman,IEEE, vol. 6, No. 3, Jun. 1996, pp. 243-250.
“MPEG: A Video Compression Standard for Multimedia Applications”, by Didier Le Gall,Communications of the ACM, vol. 34, No. 4, Apr. 1991, pp. 47-58.
“HDTV Down-Conversion Decoder”, by Jay Bao, Huifang Sun and Tommy C. Poon,IEEE, 1996, pp. 100-101.
“Compressing Still and Moving Images with Wavelets”, by Michael L. Hilton, Bjorn D. Jawerth and Ayan Sengupta,Multimedia Systems, vol. 2, No. 3, Apr. 18, 1994, pp. 1-20.
“Sequential Scaler Quantization of Color Images”, by Raja Balasubramanian, Charles A. Bouman and Jan P. Allebach,Journal of Electronic Imaging, vol. 3(1), Jan. 1994, pp. 45-59.
“A Low-Complexity Modeling Approach for Embedded Coding of Wavelet Coeffecients”, by Erik Ordentlich, Marcelo Weinberger and Gadiel Seroussi, pp. 1-10.
“Method and Apparatus for Reducing Mem
Britton Howard
Marger & Johnson & McCollom, P.C.
Sharp Laboratories of America Inc.
LandOfFree
Compression and decompression of reference frames in a video... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression and decompression of reference frames in a video..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression and decompression of reference frames in a video... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2455637