Methods and apparatus for improved motion estimation for video encoding
First Claim
Patent Images
1. A system for video encoding employing frequency domain based motion estimation comprising:
- an input for receiving frames of video input to be encoded;
a processor;
a memory;
a frequency domain encoder; and
an output port for outputting encoded video, the system operating to quantize two dimensional discrete cosine transform values for a reference block and a sample block and to encode based upon a frequency domain comparison of a subset of the quantized reference block and a subset of the quantized sample block.
5 Assignments
0 Petitions
Accused Products
Abstract
A new motion estimation system and process for video compression is presented. The approach is computationally less expensive than typical spatial domain block matching algorithms. The search for matching blocks is performed in the frequency domain making extensive use of data already computed by the video encoding process. Moreover, additional good block matches can be recognized with this approach. A multi-tiered approach may be employed to combine the frequency domain analysis with existing spatial domain techniques.
-
Citations
27 Claims
-
1. A system for video encoding employing frequency domain based motion estimation comprising:
-
an input for receiving frames of video input to be encoded;
a processor;
a memory;
a frequency domain encoder; and
an output port for outputting encoded video, the system operating to quantize two dimensional discrete cosine transform values for a reference block and a sample block and to encode based upon a frequency domain comparison of a subset of the quantized reference block and a subset of the quantized sample block. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system for video encoding employing frequency domain based motion estimation comprising:
-
an input for receiving frames of video to be encoded;
a processor;
a memory;
a program memory for storing a program which directs the processor to compute a quantized two dimensional discrete cosine transform (2D DCT) for a block of a frame of video to be encoded and to perform frequency domain motion estimation based on a subset of said quantized 2D DCT block with respect to a subset of a first reference block, and encoding frames of video input received by the input source; and
an output port for outputting encoded frames of video. - View Dependent Claims (9, 10)
-
-
11. A system for video encoding employing frequency domain based motion estimation comprising:
-
an input for receiving frames of video to be encoded;
a processor;
a memory;
a program memory for storing a program which directs the processor to compute a quantized two dimensional discrete cosine transform (2D DCT) for a block of a frame of video to be encoded and to perform frequency domain motion estimation of said block with respect to a first reference block, and encoding frames of video input received by the input source; and
an output port for outputting encoded frames of video;
wherein the processor subject to the program stored in the program memory is further operative to compute a first frequency domain mean of absolute differences (FD-MAD) value for the block and the first reference block;
to compute a second FD-MAD value for the block and a second reference block of a video frame;
to determine if the second computed FD-MAD value is less than the first computed FD-MAD value; and
to replace the first computed FD-MAD value with the second computed FD-MAD value upon determining that the second computed FD-MAD value is less than the first computed FD-MAD value;
wherein the FD-MAD values are computed on a subset of the quantized 2D DCT block data.
-
-
12. A system for video encoding employing frequency domain based motion estimation comprising:
-
an input for receiving frames of video to be encoded;
a processor;
a memory;
a program memory for storing a program which directs the processor to compute a two dimensional discrete cosine transform (2D DCT) for a block of a frame of video to be encoded and to perform frequency domain motion estimation of said block with respect to a first reference block, and encoding frames of video input received by the input source; and
an output port for outputting encoded frames of video;
wherein the processor subject to the program stored in the program memory is further operative to compute a first frequency domain mean of absolute differences (FD-MAD) value for the block and the first reference block;
to compute a second FD-MAD value for the block and a second reference block of a video frame;
to determine if the second computed FD-MAD value is less than the first computed FD-MAD value; and
to replace the first computed FD-MAD value with the second computed FD-MAD value upon determining that the second computed FD-MAD value is less than the first computed FD-MAD value;
wherein the FD-MAD values are computed after excluding a DC-coefficient, the coefficient in the 0,0 position of the 2D-DCT.
-
-
13. A system for video encoding employing frequency domain based motion estimation comprising:
-
an input for receiving frames of video to be encoded;
a processor;
a memory;
a program memory for storing a program which directs the processor to compute a quantized two dimensional discrete cosine transform (2D DCT) for a block of a frame of video to be encoded and to perform frequency domain motion estimation of said block with respect to a first reference block, and encoding frames of video input received by the input source; and
an output port for outputting encoded frames of video;
wherein FD-SAD values are computed on a subset of the quantized 2D DCT block data.
-
-
14. A system for video encoding employing frequency domain based motion estimation comprising:
-
an input for receiving frames of video to be encoded;
a processor;
a memory;
a program memory for storing a program which directs the processor to compute a two dimensional discrete cosine transform (2D DCT) for a block of a frame of video to be encoded and to perform frequency domain motion estimation of said block with respect to a first reference block, and encoding frames of video input received by the input source; and
an output port for outputting encoded frames of video;
wherein FD-SAD values are computed after excluding a DC coefficient, the coefficient in the 0,0 position of the 2D-DCT.
-
-
15. A method for video encoding employing frequency domain based motion estimation comprising the steps of:
-
extracting a first block to be matched from a current frame;
computing a two dimensional discrete cosine transform for the first block;
extracting a second block from a reference frame;
computing a two dimensional discrete cosine transform for the second block;
computing a frequency domain mean of absolute differences (FD-MAD) for a subset of the first two dimensional discrete cosine transform block and a subset of the second two dimensional discrete cosine transform block;
determining if the computed FD-MAD is less than a previously determined and stored lowest FD-MAD value;
replacing the previously determined and stored lowest FD-MAD value with the computed FD-MAD value if the computed FD-MAD value is less than said lowest FD-MAD value;
determining if additional blocks in the reference frame remain to be searched;
extracting a third block from the reference frame;
computing an FD-MAD for the first and third blocks;
determining if the computed FD-MAD for the first and third blocks is less than the stored lowest FD-MAD value;
encoding and outputting the current frame; and
wherein said FD-MAD is computed after excluding a DC-coefficient corresponding to the 0,0 position of the two dimensional discrete transform.
-
-
16. A method for video encoding employing frequency domain based motion estimation comprising the steps of:
-
extracting a first block to be matched from a current frame;
computing a two dimensional discrete cosine transform for the first block;
extracting a second block from a reference frame;
computing a two dimensional discrete cosine transform for the second block;
computing a frequency domain mean of absolute differences (FD-MAD) for a subset of the first two dimensional discrete cosine transform block and a subset of the second two dimensional discrete cosine transform block;
determining if the computed FD-MAD is less than a previously determined and stored lowest FD-MAD value;
replacing the previously determined and stored lowest FD-MAD value with the computed FD-MAD value if the computed FD-MAD value is less than said lowest FD-MAD value;
determining if additional blocks in the reference frame remain to be searched;
encoding and outputting the current frame; and
determining if the lowest FD-MAD at the time it is determined that no further blocks in the reference frame remain to be searched is less than a threshold value. - View Dependent Claims (17, 18, 19)
-
-
20. A method for video encoding employing frequency domain based motion estimation comprising the steps of:
-
extracting a first block to be matched from a current frame;
computing a two dimensional discrete cosine transform (2D DCT) for the first block;
extracting a second block from a reference frame;
computing a two dimensional discrete cosine transform (2D-DCT) for the second block;
computing a frequency domain sum of absolute differences (FD-SAD) value for a subset of the first two dimensional discrete cosine transform block and a subset of the second two dimensional discrete cosine transform block;
determining if the computed FD-SAD value is less than a previously determined and stored lowest FD-SAD value;
encoding and outputting the current frame;
replacing the previously determined and stored lowest FD-SAD value with the computed FD-SAD value if the computed FD-SAD value is less than said lowest FD-SAD value;
determining if additional blocks in the reference frame remain to be searched; and
determining if the lowest FD-SAD value at the time it is determined that no further blocks in the reference frame remain to be searched is less than a threshold value. - View Dependent Claims (21)
-
-
22. A method for video encoding employing frequency domain based motion estimation comprising the steps of:
-
extracting a first block to be matched from a current frame;
computing a two dimensional discrete cosine transform (2D DCT) for the first block;
extracting a second block from a reference frame;
computing a two dimensional discrete cosine transform (2D-DCT) for the second block;
computing a frequency domain sum of absolute differences (FD-SAD) value for a subset of the first two dimensional discrete cosine transform block and a subset of the second two dimensional discrete cosine transform block;
determining if the computed FD-SAD value is less than a previously determined and stored lowest FD-SAD value;
encoding and outputting the current frame;
replacing the previously determined and stored lowest FD-SAD value with the computed FD-SAD value if the computed FD-SAD value is less than said lowest FD-SAD value;
determining if additional blocks in the reference frame remain to be searched;
wherein best reference difference pairs from both frequency domain and spatial domain analyses are compared to determine which pairs are overall the best.
-
-
23. A method for video encoding employing frequency domain based motion estimation comprising:
-
receiving incoming video to be encoded on a video input;
converting a first block of a first frame of the incoming video from spatial domain data to frequency domain data utilizing a two dimensional discrete cosine transform;
quantizing the frequency domain data;
comparing the quantized frequency domain data of the first block with quantized frequency domain data for a second block;
zigzag scan ordering, run length encoding, and variable length encoding the quantized frequency domain of the first block data based upon the comparison, to produce output data;
appending the output data to an output bitstream; and
sending a copy of the quantized frequency domain data of the first block for storage and future processing by a frequency-domain motion estimation processor. - View Dependent Claims (24, 25, 26, 27)
sending a copy of the quantized frequency domain data of the first block for inverse quantization by an inverse quantizer and conversion back to spatial domain data by a two dimensional inverse discrete cosine transform (2D-IDCT).
-
-
25. The method of claim 24 further comprising:
storing the 2D-IDCT processed data for future processing by a motion compensation processor.
-
26. The method of claim 23 further comprising after completion of the processing of the first frame:
-
converting a first block of a second frame from spatial domain data to frequency domain data utilizing the two dimensional discrete cosine transform;
quantizing the frequency domain data for the first block of the second frame;
sending the quantized frequency domain data for the first block of the second frame to the frequency domain motion estimation processor; and
finding a best match.
-
-
27. The method of claim 26 further comprising:
-
producing a motion vector for the best match; and
encoding the motion vector for inclusion in the output bitstream.
-
Specification