Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-09-02
2001-02-13
Britton, Howard (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06188728
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to video compression and decompression algorithms.
2. Description of the Related Art
In a typical transform-based video compression algorithm, such as one conforming to the Moving Picture Experts Group (MPEG) family of algorithms, a block-based transform, such as a discrete cosine transform (DCT), is applied to blocks of image data corresponding either to pixel values or pixel differences generated, for example, based on a motion-compensated inter-frame differencing scheme. The resulting transform coefficients for each block are then typically quantized for subsequent encoding (e.g., run-length encoding followed by variable-length encoding) to generate an encoded video bitstream.
Depending on the particular video compression algorithm, images may be designated as the following different types of frames for compression processing:
An intra (I) frame which is encoded using only intra-frame compression techniques,
A predicted (P) frame which is encoded using inter-frame compression techniques based on a reference frame corresponding to a previous I or P frame, and which can itself be used to generate a reference frame for encoding one or more other frames, and
A bidirectional (B) frame which is encoded using inter-frame compression techniques based on either (i) forward, (ii) reverse, or (iii) bidirectional prediction from either (i) a previous I or P frame, (ii) a subsequent I or P frame, or (iii) a combination of both, respectively, and which cannot itself be used to encode another frame.
Note that, in P and B frames, one or more blocks of image data may be encoded using intra-frame compression techniques.
In any case, in order to decode the resulting encoded video bitstream, the particular compression processing is reversed and inverted. For example, variable-length decoding may be applied to the bitstream, followed by run-length decoding and then dequantization to generate blocks of dequantized transform coefficients. An inverse transform is then applied to the blocks of dequantized transform coefficients to generate either (1) decoded pixel data or (2) pixel difference data (depending on whether the corresponding block of image data was originally encoded using (1) intra-frame or (2) inter-frame compression techniques, respectively). If motion-compensated inter-frame compression techniques were used, then inter-frame addition is applied to the pixel difference data using motion-compensated reference frame data to generate the decoded pixel data, where the amount of motion compensation is determined by motion vectors encoded into the bitstream during compression processing. The motion-compensated reference frame data may be considered to be a prediction of the decoded image data and the pixel difference data may be considered to be the error in that prediction. As such, the motion-compensated inter-frame addition step corresponds to the correction of the prediction.
In some applications, additional processing is to be applied after an encoded video bitstream has been generated. Typically, the encoded video bitstream was previously generated by another, perhaps remote, processor and is treated as an input for purposes of the desired additional processing. For example, it may be desirable to perform “transcoding,” in which an existing encoded video bitstream that conforms to one video compression/decompression (codec) algorithm is converted into a corresponding encoded video bitstream that conforms to a different video codec algorithm. One “brute force” approach to performing such a transcoding operation is to fully decode the input bitstream to the decoded pixel domain based on the first video codec algorithm and then fully encode the resulting decoded pixel data into the output bitstream based on the second video codec algorithm.
Another possible application may be the insertion of a watermark into an existing encoded video bitstream. Here, too, one brute force approach to watermark insertion is to fully decode the input bitstream to the decoded pixel domain, perform processing on the decoded pixel data in the pixel domain to insert the desired watermark, and then fully re-encode the modified pixel data to generate the desired processed output encoded video bitstream.
In a typical transform-based video codec algorithm, the forward and inverse transform steps may be relatively expensive in terms of both coding complexity and processing time. In addition, for lossy transforms, the application of the inverse transform and then re-application of the forward transform during brute force processing of an existing encoded video bitstream will typically result in loss of information contained in the input bitstream, leading to degradation of decoded image quality in the processed bitstream. As such, it is desirable to be able to perform certain processing operations (e.g., related to transcoding or watermark insertion) on an input bitstream without first having to fully decode the bitstream. If such processing operations can be performed in the transform domain without significant loss of information, then expensive and lossy inverse and forward transform steps can be avoided.
SUMMARY OF THE INVENTION
The present invention is directed to video compression and decompression techniques that enable further processing to be applied to an existing encoded video bitstream without first having to fully decode the input bitstream. In particular, the present invention enables partially decoded video data to be processed in the transform domain without significant—or even possibly any—loss of information contained in the input bitstream. As such, the present invention avoids having to apply expensive and lossy inverse and forward transform steps during the processing of the existing input bitstream.
According to the present invention, any motion-compensated inter-frame video compression techniques used to generate the input encoded video bitstream are limited to being based on motion vectors that coincide with block boundaries. For example, in an MPEG video compression algorithm based on an (8×8) DCT transform, motion vector components are limited to integer multiples of 8 (where the integers may be positive, negative, or zero). As a result, processing operations can be applied to partially decoded video data in the transform domain without suffering significant (or possibly any) loss of information. For a typical MPEG video codec algorithm, the input encoded video bitstream may be variable-length decoded, run-length decoded, and dequantized to generate DCT coefficient data. Because the motion vectors are constrained to coincide with block boundaries, motion-compensated inter-frame addition may then be performed in the DCT transform domain without first having to apply an inverse DCT transform. The resulting motion-compensated transform data may then be subjected to the particular desired processing operations (e.g., transcoding operations, insertion of watermarks) in the transform domain. Depending on the application, the resulting processed DCT coefficient data may then subjected to at least some of motion estimation, motion-compensated inter-frame subtraction, re-quantization, run-length re-encoding, and variable-length re-encoding to generate the desired processed output encoded video bitstream, without having to implement separate inverse and forward DCT transform steps.
According to one embodiment, the present invention is a method for compressing video data, comprising the steps of (a) performing motion estimation on a frame of the video data based on corresponding reference data to identify a set of motion vectors for the frame, wherein the motion estimation is constrained to identify only block-based motion vectors that coincide with block boundaries in the reference data and at least one of the block-based motion vectors is a non-zero motion vector; (b) applying motion-compensated inter-frame differencing to the video data based on the reference data and the block-based motion vectors to genera
Britton Howard
Burke William J.
Sarnoff Corporation
LandOfFree
Block motion video coding and decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block motion video coding and decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block motion video coding and decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2582226