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

• US 8,335,255 B2
• Filed: 04/10/2007
• Issued: 12/18/2012
• 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
• Primary Examiner(s): Zia, Syed A.
• Application Number:
  US11/783,599
• Publication Number:
  US 20070297512A1
• Time in Patent Office: 2,079 Days
• Field of Search: 375/240.01, 375/240.12, 375/240, 375/16, 375/240.15, 375/240.13
• 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, by at least one processor, 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 comparing of the predetermined threshold and the cost;

selectively searching, by at least one processor, for a matching block of the current block using a predetermined local search algorithm from the changed select starting point, according to the comparing; and

calculating, by at least one processor, a motion vector corresponding to a displacement between the current block and the matching block found by the searching.

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.

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.

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.

4. A motion estimation method, comprising:

comparing, by at least one processor, 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 comparing of the predetermined threshold and the cost;

selectively searching, by at least one processor, for a matching block of the current block from the select starting point or the changed select starting point; and

calculating, by at least one processor, a motion vector corresponding to a displacement between the current block and the matching block found by the searching,

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, and

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.

8. A motion estimation method, comprising:

comparing, by at least one processor, 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 comparing of the predetermined threshold and the cost;

selectively searching, by at least one processor, for a matching block of the current block from the select starting point or the changed select starting point; and

calculating, by at least one processor, a motion vector corresponding to a displacement between the current block and the matching block found by the searching, and

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,

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,

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 comparing 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.

10. A motion estimation method, comprising:

comparing, by at least one processor, 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 comparing of the predetermined threshold and the cost;

selectively searching, by at least one processor, for a matching block of the current block from the select starting point or the changed select starting point; and

calculating, by at least one processor, a motion vector corresponding to a displacement between the current block and the matching block found by the searching, and

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,

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,

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. At least one non-transitory 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 comparing of the predetermined threshold and the cost; and

selectively searching for a matching block of the current block using a predetermined local search algorithm from the changed select starting point, according to the comparing; and

calculating a motion vector corresponding to a displacement between the current block and the matching block found by the searching.

12. 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 comparing of the predetermined threshold and the cost;

a search unit to selectively search for a matching block of the current block using a predetermined local search algorithm from the changed select starting point, according to the comparing; and

a motion vector calculation unit to calculate a motion vector corresponding to a displacement between the current block and the matching block found by the search unit,

wherein at least one of the above units are performed by at least one processor.

13. A video encoding method, comprising:

calculating, by at least one processor, 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, by at least one processor, a prediction image of the current image from the reference image using the calculated motion vector;

calculating, by at least one processor, 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, by at least one processor, the calculated difference between the current image and the generated prediction image,

wherein the suitable starting point is determined based upon the comparison of the threshold and a cost indicating a difference between the current block and a block of the reference image specified by a select starting point, and

further comprising selectively searching for a matching block of the current block using a predetermined local search algorithm from a start point other than the select starting point, according to the comparison.

14. The video encoding method of claim 13, wherein the calculating of the motion vector comprises comparing the threshold with the cost, 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.

15. The video encoding method of claim 13, 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.

16. At least one non-transitory 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,

wherein the suitable starting point is determined based upon a comparison of the threshold and a cost indicating a difference between the current block and a block of the reference image specified by a select starting point, and

further comprising selectively searching for a matching block of the current block using a predetermined local search algorithm from a start point other than the select starting point, according to the comparison.

17. 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,

wherein the suitable starting point is determined based upon a comparison of the threshold and a cost indicating a difference between the current block and a block of the reference image specified by a select starting point, and

further comprising a search unit to selectively search for a matching block of the current block using a predetermined local search algorithm from a start point other than the select starting point, according to the comparison,

wherein at least one of the above units are performed by at least one processor.