Low-power and high-performance video coding method for performing motion estimation

• US 8,218,643 B2
• Filed: 09/11/2009
• Issued: 07/10/2012
• Est. Priority Date: 02/05/2009
• Status: Active Grant

• Current Assignee: Acer, Inc.
• Original Assignee: Acer, Inc.
• Inventors: Huang, Shih-Chia, Kuo, Sy-Yen
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): NGO, NGUYEN HOANG
• Application Number:
  US12/557,766
• Publication Number:
  US 20100195734A1
• Time in Patent Office: 1,033 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/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape

Abstract

A method for performing motion estimation is provided. The method includes the following steps: selecting a current block in a current frame; comparing the current block with an initial reference block in a reference frame to obtain an initial comparison parameter, wherein position of the initial reference block in the reference frame is corresponding to position of the current block in the current frame; determining a predicted search window corresponding to the current block based on the initial comparison parameter; and comparing the current block with reference blocks in the predicted search window to obtain comparison parameters respectively, whereby a best-match reference block in the predicted search window is determined.

Claims

1. A method for performing motion estimation, comprising:

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

(b) comparing the current block with an initial reference block in a reference frame to obtain an initial comparison parameter, wherein position of the initial reference block in the reference frame is corresponding to position of the current block in the current frame;

(c) determining a predicted search window corresponding to the current block based on the initial comparison parameter; and

(d) comparing the current block with reference blocks in the predicted search window to obtain comparison parameters respectively, whereby a best-match reference block in the predicted search window is determined;

wherein each of the comparison parameters is a function of a SAD (sum of absolute difference) value between the current block and each of the reference, blocks and is represented as;

2. The method according to claim 1, wherein the step (d) is performed along a spiral path.

3. The method according to claim 2, wherein in the step (d), when a comparison parameter of a specific reference block is smaller than a predetermined threshold value, the step (d) is terminated and the specific reference block is determined as the best-match reference block.

4. The method according to claim 1, further comprising a step of obtaining a plurality of predicted search windows respectively corresponding to a plurality of neighboring blocks of the current block.

5. The method according to claim 4, wherein the predicted search window corresponding to the current block is represented as:

Avg(LEFT_ASR, TOP_ASR, TOP-RIGHT_ASR, TOP-LEFT_ASR)×

Max(MV_x, MV_y)×

δ

+θ

where LEFT_ASR is a predicted search window of a left neighboring block of the current block, TOP_ASR is a predicted search window of a upper neighboring block of the current block, TOP-RIGHT_ASR is a predicted search window of a upper-right neighboring block of the current block, RIGHT_ASR is a predicted search window of a right neighboring block of the current block, TOP-LEFT_ASR is a predicted search window of a upper-left neighboring block of the current block, (MV_x, MV_y) is a set of motion vectors containing motion vectors of upper, upper-left, upper-right, and right neighboring blocks, Max represents a maximum value function, Avg represents an average value function, and δ and

θ

are two different constant factors.

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

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

(e) determining predicted search windows corresponding to blocks in a current row associated with the selected current block;

(f) loading the predicted search windows determined in the step (e) from an external memory into an internal memory;

(g) performing block-matching operation for the blocks in the current row;

(h) determining predicted search windows corresponding to blocks in a next row adjacent to said current row; and

(i) comparing the predicted search windows determined in the step (e) and the predicted search windows determined in the step (h) to determine an added predicted search window, and loading the added predicted 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) comparing the current block with an initial reference block in a reference frame to obtain an initial comparison parameter, wherein position of the initial reference block in the reference frame is corresponding to position of the current block in the current frame;

(c) determining a predicted search window corresponding to the current block based on the initial comparison parameter and a plurality of predicted search windows respectively corresponding to a plurality of neighboring blocks of the current block; and

(d) comparing the current block with reference blocks in the predicted search window to obtain comparison parameters respectively, whereby a best-match reference block in the predicted search window is determined,

wherein the predicted search window corresponding to the current block is represented as;

Avg(LEFT_ASR, TOP_ASR, TOP-RIGHT_ASR, TOP-LEFT_ASR)×

Max(MV_x, MV_y)×

δ

+θ

where LEFT_ASR is a predicted search window of a left neighboring block of the current block, TOP_ASR is a predicted search window of a upper neighboring block of the current block, TOP-RIGHT_ASR is a predicted search window of a upper-right neighboring block of the current block, RIGHT_ASR is a predicted search window of a right neighboring block of the current block, TOP-LEFT_ASR is a predicted search window of a upper-left neighboring block of the current block, (MV_x, MV_y)is a set of motion vectors containing motion vectors of upper, upper-left, upper-right, and right neighboring blocks, Max represents a maximum value function Avg represents an average value function, and δ and

θ

are two different constant factors.

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

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

(e) determining predicted search windows corresponding to blocks in a current row associated with the selected current block;

(f) loading the predicted search windows determined in the step (e) from an external memory into an internal memory;

(g) performing block-matching operation for the blocks in the current row;

(h) determining predicted search windows corresponding to blocks in a next row adjacent to said current row; and

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