Methods and apparatus for improved motion estimation for video encoding

• US 6,697,427 B1
• Filed: 11/02/1999
• Issued: 02/24/2004
• Est. Priority Date: 11/03/1998
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: PTS Corporation
• Inventors: Moller, Christian H. L., Kurak, Charles W. Jr.
• Primary Examiner(s): LEE, RICHARD J
• Application Number:
  US09/432,705
• Time in Patent Office: 1,575 Days
• Field of Search: H04/N.712, H04/N.730, H04/N.732, 348/14.09, 375/240.01, 375/240.03, 375/240-2-2, 375/240.18, 375/240.2, 375/240.24, 382/232, 382/236, 382/238, 382/248, 382/250, 382/251, 712/11
• US Class Current: 375/240.03
• CPC Class Codes: H04N 19/547 Motion estimation performed in a transform domain

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.

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.

2. The system of claim 1 wherein the system is further operative to choose the quantized two dimensional discrete cosine transform values based on a zigzag scan ordering for the reference block and the sample block.

3. The system of claim 2 wherein a predetermined number of coefficients from the zigzag scan ordering are analyzed for purposes of making said frequency domain comparison of the reference block and the sample block.

4. The system of claim 3 wherein the predetermined number of coefficients is adaptively varied.

5. The system of claim 1 wherein the system is operative to compute a frequency domain mean of absolute differences between the reference quantized block and the sample block.

6. The system of claim 1 wherein the sample block is an I-frame block and the quantized two dimensional discrete cosine transform values for a plurality of reference blocks have been previously computed and stored in the memory.

7. The system of claim 1 wherein the system is operative to perform at least a two tier analysis, the first tier being the frequency domain comparison and the second tier being a spatial domain analysis.

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.

9. The system of claim 8 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-MA 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.

10. The system of claim 8 wherein the processor subject to the program stored in the program memory is further operative to compute a first FD-SAD value for the block and the first reference block;

to compute a second FD-SAD value for the block and a second reference block of a video frame;

to determine if the second computed FD-SAD value is less than the first computed FD-SAD value; and

to replace the first computed FD-SAD value with the second computed FD-SAD value upon determining that the second computed FD-SAD value is less than the first computed FD-SAD value.

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.

17. The method of claim 16 wherein the blocks corresponding to the lowest FD-MAD at the time it is determined that no further blocks in the reference frame remain to be searched are accepted as a reference-difference pair.

18. The method of claim 17 wherein a spatial domain analysis is also performed on the blocks of the current frame with respect to the blocks of the reference frame.

19. The method of claim 18 wherein best reference difference pairs from both frequency domain and spatial domain analyses are compared to determine which pairs are overall the best.

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.

21. The method of claim 20 wherein the blocks corresponding to the lowest FD-SAD at the time it is determined that no further blocks in the reference frame remain to be searched are accepted as a reference-difference pair.

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.

24. The method of claim 23 further comprising:

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.