Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-09-28
2002-09-17
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06452969
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to reconstructing motion compensated images, and more particularly, to constructing a motion compensated block with fractional pel accuracy in a transform domain.
BACKGROUND OF THE INVENTION
Video data is commonly compressed utilizing well known compression standards such as JPEG, MPEG-1, MPEG-2, and H.261. In order to obtain a compressed representation of the video data, these compression standards utilize intraframe coding techniques in order to exploit spatial redundancies often found within a single frame of video. A common intraframe coding technique employs a block-based two-dimensional transform that transforms each frame of video data from a spatial domain to a transform domain. One common intraframe coding technique first divides a video frame into 8×8 blocks of pels, and independently applies a two-dimensional discrete cosine transform (DCT) to each pel block. This operation results in an 8×8 block of DCT coefficients in which most of the energy in the original pel block is typically concentrated in a few low-frequency coefficients. The 8×8 block of DCT coefficients is then quantized and variable length encoded in order to reduce the number of bits necessary to represent the original 8×8 pel block.
Moreover, compression standards, such as MPEG-1, MPEG-2, and H.261, utilize interframe coding techniques in order to exploit temporal redundancies often found between temporally adjacent video frames. These compression standards exploit temporal redundancy by computing an interframe difference signal called “prediction error.” In computing the prediction error, the technique of motion compensation is employed to correct the prediction for motion. Reference is made to
FIG. 1
in order to illustrate unidirectional motion estimation which is also known as “forward prediction.” In forward prediction, a target macroblock
100
of a video frame
102
to be encoded is matched with pel blocks of the same size in a past video frame
104
called the “reference video frame.” The pel block in the reference video frame
104
that best matches the target macroblock
100
is selected for use as a prediction macroblock
106
. After selecting the prediction macroblock
106
, a prediction error macroblock is computed as the difference between the target macroblock
100
and the prediction macroblock
106
. The prediction error macroblock is then encoded utilizing the two-dimensional DCT encoding technique described above.
The position of the prediction macroblock
106
is indicated by a motion vector
108
that indicates a horizontal and vertical pel displacement between the target macroblock
100
and the prediction macroblock
106
. The motion vector
108
is then encoded for transmission along with the encoded prediction error macroblock.
FIG. 2
depicts a block diagram of a prior art video editing system
200
that utilizes a traditional approach for editing video compressed in accord with the MPEG-2 standard. The video editing system
200
essentially decompresses the video stream to obtain the video stream in the spatial domain, edits the decompressed video stream in the spatial domain, and compresses the edited video stream in order to place the edited video stream back into the compressed domain.
Performing image manipulation techniques such as resizing, transcoding, and compositing are relatively straight forward in the spatial domain since the goal of these editing techniques are to alter the spatial domain appearance of video frames. For example, resizing video frames of a video stream in the spatial domain involves downsampling the pels of each video frame in order to reduce the spatial resolution of each video frame. In other words, in order to reduce the spatial resolution of each 720×480 video frame of a video stream to a 360×240 video frame in the spatial domain, the video editing system
200
may average each two by two block of pels to obtain a single pel. While the video editing system
200
is relatively intuitive implementation of a compressed video editing system, the video editing system
200
is also computationally intensive due to (1) the high computational complexity of the decompression and compression tasks, and (2) the large volume of spatial domain data that has to be manipulated. Due to the computational complexity of the video editing system
200
, the hardware required to implement the video editing system
200
may be costly.
For this reason there has been a great effort in recent years to develop fast algorithms that perform these video editing techniques directly in the compressed domain and thereby avoid the need of completely decompressing the video stream. One such example is U.S. Pat. No. 5,708,732 to Merhav et al., entitled Fast DCT Domain Downsampling and Inverse Motion Compensation, which is hereinafter referred to as the “Merhav patent”. The Merhav patent discloses a method of inverse motion compensating in the DCT domain. In particular, the Merhav patent discloses inverse motion compensating in the DCT domain with integer pel accuracy. In other words, the Merhav patent discloses a method of inverse motion compensating in the DCT domain based upon a motion vector that indicates integer pel displacements in both the vertical and horizontal directions.
However, one drawback of the method described in the Merhav patent arises from the method being limited to inverse motion compensating with integer pel accuracy. Such a limitation is a drawback because both the MPEG-1 and MPEG-2 standards utilize motion vectors that are computed to the nearest half pel of displacement, using bilinear interpolation to obtain brightness values between pels. As a result, the method of the Merhav patent when applied to MPEG-1 and MPEG-2 video, would likely result in an edited MPEG video stream that contains undesirable visible artifacts due to the method disclosed in the Merhav patent not taking into account motion vectors computed to the nearest half pel of displacement.
Accordingly, since MPEG video utilizes motion vectors computed with half pel accuracy, there is still a need for transform domain inverse motion compensation having fractional pel accuracy.
SUMMARY OF THE INVENTION
The present invention fulfills the above need, as well as others, by providing a partial video decoder that inverse motion compensates interframe encoded frames in a transform domain with fractional pel accuracy. In general, the partial video decoder partially decodes a compressed video stream in order to obtain a transform domain representation of the video stream. In obtaining the transform domain representation of the video stream, the partial video decoder reconstructs frames that have been encoded based upon other frames (i.e. reference frames) of the video stream. In particular, the partial video decoder constructs transform domain target blocks of a video frame based upon transform domain prediction blocks and transform domain prediction error blocks. In order to obtain the transform domain prediction block, the partial video decoder inverse motion compensates transform domain reference blocks of a reference frame. To this end, the partial video decoder applies shifting and windowing matrices to the transform domain reference blocks which shift the transform domain reference blocks by fractional pel amounts. By utilizing the shifting and windowing matrices that account for fractional pel displacements, the partial video decoder inverse motion compensates the transform domain reference blocks without introducing undesirable artifacts that would otherwise arise if integer pel shifting and windowing matrices were utilized.
An exemplary method according to the present invention is a method of constructing a transform domain target block. One step of the method includes the step of obtaining a first displacement value. Another step of the method includes the step of determining whether the first displacement value indicates a first fractional pel displacement between a pel target block of a target ima
Eriksen Guy H.
Kelley Chris
Kurdyla Ronald H.
Thomson Licensing S.A.
Tripoli Joseph S.
LandOfFree
Transform domain inverse motion compensation having... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Transform domain inverse motion compensation having..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transform domain inverse motion compensation having... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2824226