Fast motion estimation apparatus and method using block matching algorithm

• US 20060280248A1
• Filed: 10/04/2005
• Published: 12/14/2006
• Est. Priority Date: 06/14/2005
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Mah, Pyeong Soo, Song, Suk Kyu, Kim, Byung Gyu, Kim, Seon Tae
• Granted Patent: US 7,869,518 B2
• Time in Patent Office: Days
• US Class Current: 375/240.160
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/513 Processing of motion vectors
• CPC Class Codes: H04N 19/533 Motion estimation using multistep search, e.g. 2D-log search or one-at-a-time search [OTS]
• 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
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 21/234309 by transcoding between formats or standards, e.g. from MPEG-2 to MPEG-4 or from Quicktime to Realvideo conversion of standards in analog television systems H04N7/01
• CPC Class Codes: H04N 21/2355 involving reformatting operations of additional data, e.g. HTML pages optimising the visualization of content for information retrieval from the Internet G06F16/9577; tracking of instant messages H04L51/234; media packet handling at the source H04L65/762
• CPC Class Codes: H04N 21/2662 Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities
• CPC Class Codes: H04N 21/812 involving advertisement data advertising per se G06Q30/02

Abstract

A fast motion estimation apparatus and method in which motion estimation is carried out on a current block of a current frame of video image data with reference to a corresponding matching block of a previous frame are provided. The fast motion estimation apparatus includes: a determination unit which determines whether an SAD between pixel values of a current block of a current frame and a corresponding matching block of a previous frame is greater than a predefined threshold; an initial search unit which performs an initial search when the SAD is greater than the predetermined threshold to find which search point of a current search pattern is the minimal SAD point and to determine whether the minimal SAD point matches the center of the current search pattern; and a repetitive search unit which performs an iteration search when the minimal SAD point differs from the center of the current search pattern to reset the minimal SAD point to be a center of the current search pattern and to set a number of search points and the size of a search pattern based on from current search pattern to a center of the search window of the previous frame.

Claims

1. A fast motion estimation method comprising:

determining whether a sum of absolute differences (SAD) between pixel values of a current block of a current frame and a corresponding matching block of a previous frame is greater than a predefined threshold;

performing an initial search when the SAD is greater than the predetermined threshold to find which search point of a current search pattern is the minimal SAD point and to determine whether the minimal SAD point matches the center of the current search pattern; and

performing an iteration search when the minimal SAD point differs from the center of the current search pattern to reset the minimal SAD point to be a center of the current search pattern and to set a number of search points and the size of a search pattern based on from current search pattern to a center of the search window of the previous frame.

2. The fast motion estimation method of claim 1, wherein an SAD of a search point monotonously increases as the distance from an optimal motion vector increases, and in the setting of the number of search points, the SAD points that are predictably not the minimal SAD are excluded.

3. The fast motion estimation method of claim 1, wherein the performing of an iteration search comprises,

detecting a quarter rood search pattern including two search points if the center of the search pattern is located in the first, second, third, or fourth quadrant of an XY plane with an origin at the center of the search window of the previous frame;

detecting a half rood search pattern including two search points if the center of the search pattern is located on the X-axis or the Y-axis of the XY plane with an origin at the center of the search window of the previous frame.

4. The fast motion estimation method of claim 1, wherein, in the performing of an iteration search, as the total number of search iterations increases, the size of a search pattern decreases, but not below a predetermined critical value.

5. The fast motion estimation method of claim 1, wherein in the performing an iteration search, the size of a search pattern is

L_x^k+1=<

ρ

|O_x^k+1−

O_x^k|>

=<

ρ

L_x^k>

, L_y^k+1=<

ρ

|O_y^k+1−

O_y^k|>

=<

ρ

L_y^k>

,

wherein the size of a search pattern to be used in a (k+1)-th search iteration in the direction of an X-axis is determined by multiplying an absolute value of a difference between the x-component of a search pattern used in a k-th search iteration and the x-component of the center of the search pattern to be used in the (k+1)-th search iteration by a predetermined weight and rounding the multiplication result to a closest integer greater than or equal to the multiplication result, the predetermined weight being a value between 0 and 1; and

the size of the search pattern to be used in the (k+1)-th search iteration in the direction of a Y-axis is determined by multiplying an absolute value of a difference between the y-component of the center of the search pattern used in the k-th search iteration and the y-component of the center of the search pattern to be used in the (k+1)-th search iteration by the predetermined weight and rounding the multiplication result to a closest integer greater than or equal to the multiplication result.

6. The fast motion estimation method of claim 5, wherein the sizes of the search pattern used in the k-th search iteration in the x- and y-directions, respectively, satisfy the following inequalities:

L_x^k≦

1; and

L_y^k≦

1.

7. A fast motion estimation apparatus comprising:

a determination unit which determines whether an SAD between pixel values of a current block of a current frame and a corresponding matching block of a previous frame is greater than a predefined threshold;

an initial search unit which performs an initial search when the SAD is greater than the predetermined threshold to find which search point of a current search pattern is the minimal SAD point and to determine whether the minimal SAD point matches the center of the current search pattern; and

a repetitive search unit which performs an iteration search when the minimal SAD point differs from the center of the current search pattern to reset the minimal SAD point to be a center of the current search pattern and to set a number of search points and the size of a search pattern based on from current search pattern to a center of the search window of the previous frame.

8. The fast motion estimation apparatus of claim 7, wherein the search points comprise 4 points forming a diamond-shaped search pattern, the origin for the search iteration, and a motion-estimated point.

9. The fast motion estimation apparatus of claim 7, wherein an SAD of a search point monotonously increases as the distance from an optimal motion vector increases, and in the setting of the number of search points, the SAD points that are predictably not the minimal SAD are excluded.

10. The fast motion estimation apparatus of claim 7, wherein the repetitive search unit uses a quarter rood search pattern having 2 points as search points, if the center of the search pattern used in the initial search is located in the first, second, third, or fourth quadrant of an XY plane whose origin is the center of the search range window of the previous frame, and uses a half rood search pattern having 3 points as search points if the center of the current search pattern is located on the X-axis or the Y-axis of the XY plane.

11. The fast motion estimation apparatus of claim 7, wherein, as the total number of search iteration iterations increases, the repetitive search unit gradually reduces the size of a search pattern, but not below a predetermined critical value.

12. The fast motion estimation apparatus of claim 7, wherein the size of a search pattern is L_x^k+1=<

ρ

|O_x^k+1−

O_x^k|>

=<

ρ

L_x^k>

, L_y^k+1=<

ρ

|O_y^k+1−

O_y^k|>

=<

ρ

L_y^k>

,

wherein the repetitive search unit determines the size of a search pattern to be used in a (k+1)-th search iteration in the direction of an X-axis by multiplying an absolute value of a difference between the x-component of a search pattern used in a k-th search iteration and the x-component of the center of the search pattern to be used in the (k+1)-th search iteration by a predetermined weight and rounding the multiplication result to a closest integer greater than or equal to the multiplication result, the predetermined weight being a value between 0 and 1; and

determines the size of the search pattern to be used in the (k+1)-th search iteration in the direction of a Y-axis by multiplying an absolute value of a difference between the y-component of the center of the search pattern used in the k-th search iteration and the y-component of the center of the search pattern to be used in the (k+1)-th search iteration by the predetermined weight and rounding the multiplication result to a closest integer greater than or equal to the multiplication result.

13. The fast motion estimation apparatus of claim 12, wherein the sizes of the search pattern used in the k-th search iteration in the x- and y-directions, respectively, satisfy the following inequalities:

L_x^k≦

1; and

L_y^k≦

1.