Motion estimation method, medium, and system with fast motion estimation

• US 20070297512A1
• Filed: 04/10/2007
• Published: 12/27/2007
• Est. Priority Date: 06/21/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Ho-Jin, Lee, Sang-Jo, Lee, Si-hwa, Kim, Do-hyung
• Granted Patent: US 8,335,255 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search

Abstract

A motion estimation method, medium, and system with fast motion estimation. The motion estimation method includes comparing a cost indicating a difference between a current block of a current image and a block of a reference image specified by a starting point with a predetermined threshold and selectively searching for the best matching block of the current block from the starting point according to the comparison result.

Claims

1. A motion estimation method, comprising:

comparing a predetermined threshold with a cost indicating a difference between a current block of a current image and a block of a reference image specified by a select starting point, wherein the select starting point is changed based upon the comparison of the predetermined threshold and the cost; and

selectively searching for a matching block of the current block from the select starting point or the changed select starting point.

2. The motion estimation method of claim 1, wherein the selectively searching comprises searching for the matching block of the current block from the select starting point if the cost is less than the predetermined threshold.

3. The motion estimation method of claim 1, wherein the comparing of the predetermined threshold with the cost further comprises changing the select starting point if the cost is not less than the predetermined threshold and comparing the predetermined threshold with a corresponding cost based upon the changed select starting point.

4. The motion estimation method of claim 3, further comprising:

comparing a minimum cost among costs indicating differences between the current block and blocks of the reference image specified by at least one of a plurality of corresponding changed select starting points with the cost indicating the difference between the current block and the block of the reference image specified by the select starting point; and

searching in the reference image for the matching block of the current block from additional blocks corresponding to the at least one of the plurality of corresponding changed select starting points having the minimum cost if the minimum cost is less than the cost indicating the difference between the current block and the block of the reference image specified by the select starting point.

5. The motion estimation method of claim 3, further comprising:

comparing the predetermined threshold with a minimum cost indicating the difference between the current block and the block of the reference image specified by at least one of a plurality of corresponding changed select starting points; and

selecting another changed select starting point, of the plurality of corresponding changed select starting points, in addition to the at least one of the plurality of corresponding changed select starting points if the minimum cost is greater than the predetermined threshold.

6. The motion estimation method of claim 1, further comprising determining the predetermined threshold so as to be a criterion for selecting a suitable starting point for searching in the reference image for the matching block of the current block.

7. The motion estimation method of claim 6, wherein the determining of the predetermined threshold comprises:

calculating a peak signal to noise ratio (PSNR) between original images making up a test sequence and reconstructed images using a random threshold;

comparing the calculated PSNR with a predetermined PSNR; and

selectively determining the random threshold to be the predetermined threshold based on the comparing of the calculated PSNR with the predetermined PSNR.

8. The motion estimation method of claim 7, wherein the determining of the predetermined threshold further comprises:

selecting the select starting point for searching in the reference image for the matching block of the current block of the current image from among the original images;

comparing the cost indicating the difference between the current block and a block of the reference image specified by the select starting point selected in the selecting of the select starting point with the random threshold;

selectively searching in the reference image corresponding to the original image for the matching block of the current block from the select starting point according to the comparison of the cost indicating the difference between the current block and the block of the reference image;

generating a prediction image for the current image from among the original images using a motion vector corresponding to a displacement between the current block of the current image and a block found in the selectively searching in the reference image; and

generating a reconstructed image of the current image from among the original images from the prediction image.

9. The motion estimation method of claim 6, wherein the determining of the predetermined threshold comprises determining the predetermined threshold using costs indicating differences between neighboring blocks of the current block and blocks of the reference image corresponding to the neighboring blocks.

10. The motion estimation method of claim 9, wherein the determining of the predetermined threshold comprises determining the predetermined threshold using a cost indicating a difference between a block located above the current block and a block of the reference image corresponding to the block located above the current block, a cost indicating a difference between a block located above and to the right side of the current block and a block of the reference image corresponding to the block located above and to the right side of the current block, and a cost indicating a difference between a block located to the left side of the current block and a block of the reference image corresponding to the block located to the left side of the current block.

11. The motion estimation method of claim 1, wherein the selectively searching for the matching block of the current block comprises performing a search according to a predetermined local search algorithm.

12. At least one medium comprising computer readable code to control at least one processing element to implement a motion estimation method, the motion estimation method comprising:

comparing a predetermined threshold with a cost indicating a difference between a current block of a current image and a block of a reference image specified by a select starting point, wherein the select starting point is changed based upon the comparison of the predetermined threshold and the cost; and

selectively searching for a matching block of the current block from the select starting point or the changed select starting point.

13. A motion estimation system, comprising:

a comparison unit to compare a predetermined threshold with a cost indicating a difference between a current block of a current image and a block of a reference image specified by a select starting point, wherein the select starting point is changed based upon the comparison of the predetermined threshold and the cost; and

a search unit to selectively search for a matching block of the current block from the select starting point or the changed select starting point.

14. A video encoding method, comprising:

calculating a motion vector using a threshold that is a criterion for determining a suitable start point for searching in a reference image for a matching block of a current block of a current image;

generating a prediction image of the current image from the reference image using the calculated motion vector;

calculating a difference between the generated prediction image and the current image to generate a difference between the current image and the generated prediction image; and

encoding and outputting the calculated difference between the current image and the generated prediction image.

15. The video encoding method of claim 14, wherein the calculating of the motion vector comprises comparing the threshold with a cost indicating a difference between the current block of the current image and a block of the reference image specified by a select starting point, wherein the select starting point is changed based upon the comparison of the threshold and the cost and selectively searching for the matching block of the current block from the select starting point or the changed select starting point.

16. The video encoding method of claim 14, wherein the encoding and outputting of the calculated difference comprises:

transforming the calculated difference between the current image and the generated prediction image from a color domain to a frequency domain;

quantizing values of the frequency domain transformed calculated difference; and

performing entropy encoding on the quantized values.

17. At least one medium comprising computer readable code to control at least one processing element to implement a video encoding method, the video encoding method comprising:

calculating a motion vector using a threshold that is a criterion for determining a suitable start point for searching in a reference image for a matching block of a current block of a current image;

generating a prediction image of the current image from the reference image using the calculated motion vector;

calculating a difference between the generated prediction image and the current image to generate a difference between the current image and the generated prediction image; and

encoding and outputting the calculated difference between the current image and the generated prediction image.

18. A video encoder, comprising:

a motion estimation unit to calculate a motion vector using a threshold that is a criterion for determining a suitable start point for searching in a reference image for a matching block of a current block of a current image;

a motion compensation unit to generate a prediction image of the current image from the reference image using the calculated motion vector;

a subtraction unit to calculate a difference between the generated prediction image and the current image to generate a difference between the current image and the generated prediction image; and

an encoding unit to encode and output the calculated difference between the current image and the generated prediction image.