Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-03-23
2003-07-15
Wu, Jingge (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
C382S251000, C375S240030
Reexamination Certificate
active
06594398
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of image processing. More specifically, the present invention relates to methods and apparatus for run-length encoding video data. These techniques are especially suited for digital video (DV) applications, in which input to a video encoder is run-length encoded. The implementations are suitable for widely-used image compression standards that integrate various algorithms into a compression system, such as the standards specified in the DV standard (DV-SD or the “Blue Book”), which is included herein by reference in its entirety.
In a traditional video compression scheme, a video encoder applies a discrete cosine transform (DCT) to transform the DCT coefficient data in each video block into frequency-domain coefficients. Every video block generally consists of an 8×8 block of DCT coefficients. In order to increase the compression ratio, all the coefficients are weighted with certain weighting quantization numbers. After the weighting, many of the coefficients will be truncated to zero and/or the dynamic ranges of the coefficients will be reduced. This will improve the compression ratio.
In particular, in run-length encoding the repetitive nature of an image is exploited to provide compression. Run-length encoding detects “runs” of the same value, encodes the image, and provides a sequence of “length-of-run” and “value” (or amplitude). Accordingly, run-length encoding is error free (i.e., lossless) compression. Since the weighting stage will truncate many of the coefficients to zero and/or the dynamic ranges of the coefficients will be reduced, the compression ratio can be significantly increased because the run count in the run-length coding is increased. This can replace the zeros appended at the end of the end of block (EOB) token. Usually, the compression ratio will range from 3 to 20.
In the DV system, the situation is different. The compression ratio is expected at around 5:1, which means excessive truncations are unnecessary. In order to maintain a constant ratio, the compression ratio is confined at the video segment level. Each video segment consists of five macro blocks and each macro block contains four (4) 8×8 Y-blocks, one (1) 8×8 U-block, and one (1) 8×8 V-block. With a fixed amount of data to store the encoding bitstream for all 30 blocks in each video segment, this scheme will allow some blocks using longer bitstream to achieve better encoding results. At the same time, some blocks will be able to keep reasonably good quality using short bitstreams. Overall both high compression ratio and high quality are expected to be achieved at the same time.
What is therefore desired is a technique which provides acceptable compression levels for varying types of video data such as ever-changing scenery. Moreover, a technique of this type should provide efficient use of space when implemented in an integrated circuit. Also, the implementation should provide an acceptable level of computational accuracy to provide image quality.
SUMMARY OF THE INVENTION
The present invention solves the problems associated with the prior art by providing methods and apparatus for efficiently and accurately compressing video data. In one embodiment, a video encoder for run-length encoding video data is provided. The video encoder includes a length-decision coder and a code-decision coder. The length-decision coder can be configured to receive the video data and provide length information based on a selected group of quantization factors. The code-decision coder can be configured to receive a plurality of best fit quantization factors and run-length encode the video data.
In another embodiment, the code-decision coder and the length-decision coder can be coupled to a smart encoder. The smart encoder can be configured to receive the length information and select the plurality of best fit quantization factors.
In a further embodiment, the selected group of quantization factors is selected in accordance with the DV Standard.
In yet another embodiment a method of encoding video data is disclosed. The video data includes a plurality of DCT coefficients. The method includes simultaneously analyzing two DCT coefficients of video data, determining a run length for the two DCT coefficients being analyzed, and storing the run length. If both of the two DCT coefficients have a value of zero, then the run length is increased by two. If the first DCT coefficient has a value of zero and the second DCT coefficient has a value of one, then the run length is restarted at one. If the second DCT coefficient has a value of zero and the first DCT coefficient has a value of one, then the run length is incremented by one. Alternatively, if both of the two DCT coefficients have a value of one, then the run length is set to zero.
In a different embodiment, a method of looking up length codes from a plurality of tables is disclosed. The method includes receiving input data, quantizing the input data, and providing a large VLC length table capable of providing length information based on run count and amplitude of the quantized input data. If both a valid run count and amplitude of the quantized input data can be provided for the quantized input data, a length code is looked up from the large VLC length table. The method further provides a run VLC length table capable of providing length information based on run count of the quantized input data. If only a valid run count of the quantized input data can be provided for the quantized input data, a length code is looked up from the run VLC length table. The method also includes providing an amplitude VLC length table capable of providing length information based on amplitude of the quantized input data. If only a valid amplitude of the quantized input data can be provided for the quantized input data, a length code is looked up from the amplitude VLC length table. The method additionally includes combining the length codes looked up from the amplitude VLC length table and the run VLC length table. The method provides a final length code based on whether both a valid run count and amplitude of the quantized input data can be provided for the quantized input data.
In yet a further embodiment of the present invention, an innovative two-DCT coefficient scanning technique and a (relatively small) scratch memory to store EOB locations are provided. The two-DCT coefficient scanning scheme increases the performance up to two-fold. When the lower DCT coefficient value is zero, the factor of two increase in performance is maintained. The small scratch memory (e.g., a 30×33 bit RAM memory) can be used to store the DCT type (1 bit) and class number (2 bits) of each block in one video segment.
These and other embodiments of the present invention, as well as, its advantages and features are described in more detail in conjunction with the text below and attached figures.
REFERENCES:
patent: 5022088 (1991-06-01), Hisada et al.
patent: 5227878 (1993-07-01), Puri et al.
patent: 5347310 (1994-09-01), Yamada et al.
patent: 5402123 (1995-03-01), Jung
patent: 5452104 (1995-09-01), Lee
patent: 5530478 (1996-06-01), Sasaki et al.
patent: 5870145 (1999-02-01), Yada et al.
patent: 6198849 (2001-03-01), Fischer
patent: 6233282 (2001-05-01), Guerrera
patent: 6266375 (2001-07-01), Chang et al.
Wang Ren-Yuh
Wu Tony H.
Divio, Inc.
Wu Jingge
LandOfFree
Method and apparatus for run-length encoding video 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 run-length encoding video data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for run-length encoding video data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3072564