Motion estimation approach for real-time embedded multimedia design

• US 8,243,810 B2
• Filed: 09/22/2009
• Issued: 08/14/2012
• Est. Priority Date: 02/18/2009
• Status: Active Grant

• Current Assignee: Acer, Inc.
• Original Assignee: Acer, Inc.
• Inventors: Huang, Shih-Chia, Kuo, Sy-Yen
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): NGO, NGUYEN HOANG
• Application Number:
  US12/564,556
• Publication Number:
  US 20100208820A1
• Time in Patent Office: 1,057 Days
• Field of Search: 375/240, 375/240.01, 375/240.16, 375/240.24, 375/240.12
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/557 Motion estimation characterised by stopping computation or iteration based on certain criteria, e.g. error magnitude being too large or early exit
• 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 method for performing motion estimation is provided. The method includes the following steps: selecting a current block in a current frame; obtaining motion vectors and residual data of a plurality of neighboring blocks adjacent to the current block; setting a predetermined threshold value according to the residual data of the plurality of neighboring blocks; comparing the current block with an initial reference block in a reference frame to obtain an initial comparison result, and comparing the predetermined threshold value with the initial comparison result; determining a predicted motion vector of the current block according to the motion vectors of the plurality of neighboring blocks if the initial comparison result is larger than the predetermined threshold value; and performing a block-matching operation in a search window corresponding to the predicted motion vector to determine a corresponding reference block which best matches the current block.

Claims

1. A method for performing motion estimation, comprising:

(a) selecting a current block in a current frame;

(b) obtaining motion vectors and residual data of a plurality of neighboring blocks adjacent to the current block;

(c) setting a predetermined threshold value according to the residual data of the plurality of neighboring blocks;

(d) comparing the current block with an initial reference block in a reference frame to obtain an initial comparison result, and comparing the predetermined threshold value with the initial comparison result;

(e) determining a predicted motion vector of the current block according to the motion vectors of the plurality of neighboring blocks if the initial comparison result is larger than the predetermined threshold value;

(f) performing a block-matching operation in a search window corresponding to the predicted motion vector to determine a best-match reference block in the search window;

wherein the predetermined threshold value is represented as;

α

n=(2×

LEFTSAD+2×

TOPSAD+TOP-RIGHTSAD+TOP-LEFTSAD+ε

)/6;

where LEFTSAD is residual data of a left neighboring block of the current block, TOPSAD is residual data of an upper neighboring block of the current block. TOP-RIGHTSAD is residual data of an upper-right neighboring block of the current block, TOP-LEFTSAD is residual data of an upper-left neighboring block of the current block, and ε

is a constant factor.

2. The method according to claim 1, wherein position of the initial reference block in the reference frame is corresponding to position of the current block in the current frame.

3. The method according to claim 1, wherein the step (f) is performed by using a square search algorithm.

4. The method according to claim 1, wherein in the step (d), if the initial comparison result is smaller than the predetermined threshold value, the initial reference block is determined as the best-match reference block.

5. The method according to claim 4, further comprising a step of repeating the step (a) to the step (f), wherein in the step (a), the current block is selected in a raster-scan order.

6. The method according to claim 1, wherein the initial comparison result is a function of a SAD (sum of absolute difference) value between the current block and the initial reference block.

7. The method according to claim 1, further comprising the following steps:

(g) loading the search window from an external memory into an internal memory;

(h) determining a search window corresponding to a next block adjacent to the selected current block;

(i) comparing the search window determined in the step (h) and the search window loaded in the step (g) to determine an added search window, and loading the added search window from the external memory into the internal memory.

8. A non-transitory computer readable medium embedded with a computer executable program including instructions for causing a computing device to implement the method of claim 1.

9. A method for performing motion estimation, comprising:

(a) selecting a current block in a current frame;

(b) obtaining motion vectors and residual data of a plurality of neighboring blocks adjacent to the current block;

(c) setting a predetermined threshold value according to the residual data of the plurality of neighboring blocks;

(d) comparing the current block with an initial reference block in a reference frame to obtain an initial comparison result, and comparing the predetermined threshold value with the initial comparison result;

(e) determining a predicted motion vector of the current block according to the motion vectors of the plurality of neighboring blocks if the initial comparison result is larger than the predetermined threshold value;

(f) performing a block-matching operation in a search window corresponding to the predicted motion vector to determine a best-match reference block in the search window; and

wherein the predicted motion vector of the current block is represented as;

MV =½

(−

MV1 +MV3 +2MV4);

where MV1 is a motion vector of an upper-left neighboring block of the current block, MV3 is a motion vector of an upper-right neighboring block of the current block, and MV4 is a motion vector of a left neighboring block of the current block.

10. The method according to claim 9, wherein position of the initial reference block in the reference frame is corresponding to position of the current block in the current frame.

11. The method according to claim 9, wherein the step (f) is performed by using a square search algorithm.

12. The method according to claim 9, wherein in the step (d), if the initial comparison result is smaller than the predetermined threshold value, the initial reference block is determined as the best-match reference block.

13. The method according to claim 12, further comprising a step of repeating the step (a) to the step (f), wherein in the step (a), the current block is selected in a raster-scan order.

14. The method according to claim 9, wherein the initial comparison result is a function of a SAD (sum of absolute difference) value between the current block and the initial reference block.

15. The method according to claim 9, further comprising the following steps:

(g) loading the search window from an external memory into an internal memory;

(h) determining a search window corresponding to a next block adjacent to the selected current block;

(i) comparing the search window determined in the step (h) and the search window loaded in the step (g) to determine an added search window, and loading the added search window from the external memory into the internal memory.