Method and apparatus for detecting improper area for motion compensation in video signal

• US 7,336,707 B2
• Filed: 06/06/2003
• Issued: 02/26/2008
• Est. Priority Date: 06/06/2003
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Yeong-Taeg
• Primary Examiner(s): DIEP, NHON THANH
• Application Number:
  US10/456,497
• Publication Number:
  US 20040247028A1
• Time in Patent Office: 1,726 Days
• Field of Search: None
• US Class Current: 375/240
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/231 using full search
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51
• CPC Class Codes: H04N 7/014 involving the use of motion vectors motion estimation and compensation in video coding H04N19/51

Abstract

A motion compensation method for estimating motion between one image frame and another image frame. Each frame is divided into a number of block, and a match is found for a block of one frame within a search area in another frame. A motion vector is determined that represents the geometrical displacement between the two matched blocks, by determining whether motion estimation is being performed near pattern-like objects in the frames. A new frame is reconstructed by interpolation as a function of the two existing frames based on the motion vector and a degree of being a pattern-like object in a frame.

Claims

1. A motion compensation method for estimating a motion between two image frames, comprising the steps of:

dividing each of the two frames into a number of blocks;

finding a second block, which is a match of a first block in one of the two frames, within a search area in the other one of the two frames; and

determining a motion vector representing a geometrical displacement between the first and second blocks, by determining whether the motion estimation is being performed near pattern-like objects in the two frames.

2. The method of claim 1, wherein the step of finding a match further includes the steps of:

for each block in one of the two frames, searching the other one of the two frames over a search area for a matching block with low error.

3. The method of claim 2, wherein:

at a time t, I^t denotes a t^th frame, I^t(x, y) denotes a pixel value at location (x, y) in I^t, and B_t(x, y) denotes a block at location (x, y) in I^t; and

the steps of finding a match further include the steps of comparing one block B_t(x₁, y₁) in I^t and another block B<sub>t−

1</sub>(x₂, y₂) in I<sup>t−

1</sup> using a cost function that is a measure of a mismatch between the two matched blocks.

4. The method of claim 3, wherein:

(a) the steps of finding a match further include the steps of;

comparing the block B_t(x, y) in the frame I^t with a block B<sub>t−

1</sub>(x+d_x, y+d_y) in the frame I<sup>t−

1</sup>, wherein the blocks B_t(x, y) and B<sub>t−

1</sub>(x+d_x, y+d_y) are displaced by a vector (d_x, d_y), and (d_x, d_y) represents search locations satisfying (d_x, d_y)ε

{(p,q)|p=−

D_x,, . . . ,0, . . . , D_x and q=−

D_y,, . . . ,0, . . . , D_y}, such that D_x, and D_y are difference signals associated with the search area;

said cost function comprising a sum of absolute difference (SAD) function;

5. The method of claim 4, wherein for a full search range, the motion vector (v_x, v_y) is one that satisfies the condition SAD(v_x, v_y)≦

SAD(d_x, d_y) for all (d_x, d_y)ε

R, wherein R={(p,q)|p=−

D_x,, . . . ,0, . . . , D_x and q=−

D_y,, . . . ,0, . . . , D_y}, which represents a set of search locations.

6. The method of claim 4, wherein the steps of determining whether the motion estimation is being performed near pattern-like objects in the frames comprise the steps of:

detecting pattern-like objects in a frame utilizing horizontal and vertical projection functions φ

_x and φ

_y, respectively, wherein;

7. The method of claim 6, wherein the steps of detecting pattern-like objects further include the steps of:

(a) determining values L_x and L_y, wherein;

8. The method of claim 7, wherein the steps of detecting pattern-like objects further include the steps of:

determining a value α

that indicates a degree of having a pattern-like object in a frame, wherein;

α

=min(1.0, L_mzx/K),

where K is a pre-determined constant.

9. The method of claim 3, wherein:

(a) the steps of finding a match further include the steps of comparing a block B<sub>t−

1</sub>(x, y) in the frame I<sup>t−

1</sup> to a block B_t(x+d_x, y+d_y) in the frame I^t, such that the blocks B<sub>t−

1</sub>(x, y) and B_t(x+d_x, y+d_y) are displaced by the vector (d_x, d_y);

where a block difference signal D(d_x, d_y) is expressed as;

D(d_x, d_y)=B<sub>t−

1</sub>(x, y)−

B_t(x+d_x, y+d_y), and

said cost function is expressed as;

10. The method of claim 9, wherein for a full search range in the motion estimation, the motion vector (v_x, v_y) is one that satisfies the condition SAD(v_x, v_y)≦

SAD(d_x, d_y) for all (d_x, d_y)ε

R, wherein R={(p,q)|p=−

D_x,, . . . ,0, . . . ,D_x and q=−

D_y,, . . . ,0, . . . ,D_y}.

11. The method of claim 9, wherein the steps of determining whether the motion estimation is being performed near pattern-like objects in the frames further include the steps of:

detecting pattern-like objects in a frame utilizing horizontal and vertical projection functions φ

_x and φ

_y, respectively, wherein;

12. The method of claim 11, wherein the steps of detecting pattern-like objects further include the steps of:

(a) determining values L_x and L_y, expressed as;

13. The method of claim 12, wherein the steps of detecting pattern-like objects further include the steps of:

determining a value α

that indicates a degree of having a pattern-like object in a frame, wherein;

α

=min(1.0, L_mzx/K),

where K is a pre-determined constant.

14. The method of claim 3, wherein:

(a) the steps of finding a match further include the steps of;

comparing a block B_t(x−

d_x, y−

d_y) in the frame I^t to a block B<sub>t−

1</sub>(x+d_x, y+d_y) in the frame I<sup>t−

1</sup>, wherein the blocks B_t(x−

d_x, y−

d_y) and B<sub>t−

1</sub>(x+d_x, y+d_y) are displaced by a vector (2·

d_x, 2·

d_y);

wherein a block difference signal D(d_x, d_y) is expressed as

D(d_x, d_y)=B_t(x−

d_x, y−

d_y)−

B<sub>t−

1</sub>(x+d_x, y+d_y); and

said cost function is expressed as;

15. The method of claim 14, wherein for a full search range in the motion estimation, the motion vector (v_x, v_y) is one that satisfies the condition SAD(v_x, v_y)≦

SAD(d_x, d_y) for all (d_x, d_y)ε

R, wherein R={(p,q)|p=−

D_x,, . . . ,0, . . . ,D_x and q=−

D_y,, . . . ,0, . . . ,D_y}.

16. The method of claim 14, wherein the steps of determining whether the motion estimation is being performed near pattern-like objects in the frames comprise the steps of:

detecting pattern-like objects in a frame utilizing horizontal and vertical projection functions φ

_x and φ

_y, respectively, wherein;

17. The method of claim 16, wherein the steps of detecting pattern-like objects further include the steps of:

(a) determining values L_x and L_y, expresses as;

18. The method of claim 17, wherein the steps of detecting pattern-like objects further include the steps of:

determining a value α

that indicates a degree of having a pattern-like object in a frame, wherein;

α

=min(1.0, L_mzx/K),

where K is a pre-determined constant.

19. The method of claim 3, further comprising the steps of:

interpolating a frame I* based on frames I^t and I<sup>t−

1</sup> by the motion estimation, wherein the to-be-reconstructed frame I* is sequentially between the frames I^t and I<sup>t−

1</sup>.

20. The method of claim 19, wherein:

a frame pixel I*(x, y) is expressed as;

I*(x, y)=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

wherein v_x and v_y represent components of said motion vector, and k is a pre-determined constant between 0 and 1 associated with the relative location of the frame I* in time.

21. The method of claim 20, wherein:

the steps of determining whether the motion estimation is being performed near pattern-like objects in the frames further include the steps of determining a factor α

that indicates a degree of having a pattern-like object in a frame; and

the steps of interpolating further include determining pixel I*(x, y) based on the factor α

such that

I*(x, y)=α

·

I_v+(1−

α

)·

I₀;

where

I_v=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

and

I₀=k·

I<sup>t−

1</sup>(x, y)+(1−

k)·

I^t(x, y).

22. The method of claim 1, further comprising the steps of:

interpolating a new frame as a function of the two existing frames based on the motion vector and a degree of having a pattern-like object in a frame.

23. A motion compensation method for interpolating a new frame based on two existing image frames, comprising the steps of:

dividing each existing frame into a number of blocks, wherein at a time t, I^t denotes the t^th existing frame, I^t (x, y) denotes a pixel value at location (x, y) in the frame I^t, and B_t(x, y) denotes the block at location (x, y) in I^t;

finding a match for a block of one frame within a search area in another frame by comparing a block B_t(x₁, y₁) in I^t and another block B<sub>t−

1</sub>(x₂, y₂) in I<sup>t−

1</sup> using a cost function that is a measure of the mismatch between the two matched blocks;

determining a motion vector representing a geometrical displacement between the two matched blocks, by determining whether a motion estimation is being performed near pattern-like objects in the frames; and

interpolating a new frame I* based on the existing frames I^t and I<sup>t−

1</sup>, wherein a frame pixel I*(x, y) is expressed as;

I*(x, y)=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

where v_x and v_y represent components of said motion vector, and k is a pre-determined constant between 0 and 1 associated with a relative location of the frame I* in time.

24. The method of claim 23, wherein:

the steps of determining whether motion estimation is being performed near pattern-like objects in the frames further include the steps of determining a factor α

that indicates a degree of having a pattern-like object in a frame; and

the steps of interpolating further include determining pixel I*(x, y) based on the factor α

such that

I*(x, y)=α

·

I_v+(1−

α

)·

I₀;

where

I_v=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

and

I₀=k·

I<sup>t−

1</sup>(x, y)+(1−

k)·

I^t(x, y).

25. A motion compensation encoding apparatus for use in an image encoder, comprising:

a motion estimator that estimates a motion between one image frame and another image frame by finding a match for a block of one frame within a search area in the other frame; and

a pattern detector that determines whether a motion estimation is being performed near pattern-like objects in the frames.

26. The apparatus of claim 25, further comprising:

a motion vector generation that determines a motion vector representing a geometrical displacement between the two matched blocks.

27. The apparatus of claim 26, wherein:

at a time t, I^t denotes the t^th frame, I^t(x, y) denotes the pixel value at location (x, y) in the frame I^t, and B_t(x, y) denotes the block at location (x, y) in the t^th frame; and

the motion estimator finds a match by comparing one block B_t(x₁, y₁) in I^t and another block B<sub>t−

1</sub>(x₂, y₂) in I<sup>t−

1</sup> using a cost function that is a measure of the mismatch between the two matched blocks.

28. The apparatus of claim 27, wherein:

the motion estimator compares the block B_t(x, y) in the frame I^t with a block B<sub>t−

1</sub>(x+d_x, y+d_y) in the frame I<sup>t−

1</sup>, wherein the blocks B_t(x, y) and B<sub>t−

1</sub>(x+d_x, y+d_y) are displaced by a vector (d_x, d_y), and (d_x, d_y) represents the search locations satisfying (d_x, d_y)ε

{(p,q)|p=−

D_x,, . . . ,0, . . . ,D_x and q=−

D_y,, . . . ,0, . . . ,D_y}, such that D_x, and D_y are difference signals associated with the search area;

said cost function comprises a sum of absolute difference (SAD) function;

29. The apparatus of claim 28, wherein for a full search range, the motion vector (v_x, v_y) is one that satisfies the condition SAD(v_x, v_y)≦

SAD(d_x, d_y) for all (d_x, d_y)ε

R, wherein R={(p,q)|p=−

D_x,, . . . ,0, . . . ,D_x and q=−

D_y,, . . . ,0, . . . ,D_y}, which represents a set of search locations.

30. The apparatus of claim 28, wherein the pattern detector further includes a projection function block that generates horizontal and vertical projection functions φ

_x and φ

_y, respectively, wherein;

31. The apparatus of claim 30, wherein the pattern detector further includes:

a minima function block that determines values L_x and L_y, wherein;

32. The apparatus of claim 31, wherein the pattern detector further determines a value α

that indicates a degree of having a pattern-like object in a frame, wherein;

α

=min(1.0, L_mzx/K),

where K is a pre-determined constant.

33. The apparatus of claim 27, wherein:

the motion estimator finds a match by comparing a block B<sub>t−

1</sub>(x, y) in the frame I<sup>t−

1</sup> to a block B_t(x+d_x, y+d_y) in the frame I^t, such that the blocks B<sub>t−

1</sub>(x, y) and B_t(x+d_x, y+d_y) are displaced by the vector (d_x, d_y);

where a block difference signal D(d_x, d_y) is expressed as;

D(d_x, d_y)=B<sub>t−

1</sub>(x, y)−

B_t(x+d_x, y+d_y), and

said cost function is expressed as;

34. The apparatus of claim 33, wherein for a full search range in the motion estimation, the motion vector (v_x, v_y) is one that satisfies the condition SAD(v_x, v_y)≦

SAD(d_x, d_y) for all (d_x, d_y)ε

R, wherein R={(p,q)|p=−

D_x,, . . . ,0, . . . ,D_x and q=−

D_y,, . . . ,0, . . . ,D_y}.

35. The apparatus of claim 33, wherein the pattern detector further includes:

a projection function block that utilizes horizontal and vertical projection functions φ

_x and φ

_y, respectively, wherein;

36. The apparatus of claim 35, wherein the pattern detector further includes:

a minima function block that determines values L_x and L_y, expressed as;

37. The apparatus of claim 36, wherein the pattern detector further determines a value α

that indicates a degree of having a pattern-like object in a frame, wherein;

α

=min(1.0, L_max/K),

where K is a pre-determined constant.

38. The apparatus of claim 27, wherein:

the motion estimator finds a match by comparing a block B_t(x−

d_x, y−

d_y) in the frame I^t to a block B<sub>t−

1</sub>(x+d_x, y+d_y) in the frame I<sup>t−

1</sup>, wherein the blocks B_t(x−

d_x, y−

d_y) and B<sub>t−

1</sub>(x+d_x, y+d_y) are displaced by a vector (2·

d_x, 2·

d_y);

wherein a block difference signal D(d_x, d_y) is expressed as;

D(d_x, d_y)=B_t(x−

d_x, y−

d_y)−

B<sub>t−

1</sub>(x+d_x, y+d_y); and

said cost function is expressed as;

39. The apparatus of claim 38, wherein for a full search range in the motion estimation, the motion vector (v_x, v_y) is one that satisfies the condition SAD(v_x, v_y)≦

SAD(d_x, d_y) for all (d_x, d_y)ε

R, wherein R={(p,q)|p=−

D_x,, . . . ,0, . . . ,D_x and q=−

D_y,, . . . ,0, . . . ,D_y}.

40. The apparatus of claim 38, wherein the pattern detector further includes a projection function block that utilizes horizontal and vertical projection functions φ

_x and φ

_y, respectively, wherein;

41. The apparatus of claim 40, wherein:

the pattern detector further includes a minima function block that determines values L_x and L_y, expresses as;

42. The apparatus of claim 41, wherein the pattern detector further determines a value α

that indicates a degree of having a pattern-like object in a frame, wherein;

α

=min(1.0, L_max/K),

where K is a pre-determined constant.

43. The apparatus of claim 27, further comprising:

an interpolator that interpolates a frame I* based on frames I^t and I<sup>t−

1</sup>, wherein the to-be-reconstructed frame I* is sequentially between the frames I^t and I<sup>t−

1</sup>.

44. The apparatus of claim 43, wherein:

a frame pixel I*(x, y) is expressed as;

I*(x, y)=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

wherein v_x and v_y represent components of said motion vector, and k is a pre-determined constant between 0 and 1 associated with a relative location of the frame I* in time.

45. The apparatus of claim 44, wherein:

the pattern detector further determines a factor α

that indicates a degree of having a pattern-like object in a frame; and

the interpolator further determines pixel I*(x, y) based on the factor α

such that

I*(x, y)=·

I_v+(1−

α

)·

I₀;

where

I_v=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

and

I₀=k·

I<sup>t−

1</sup>(x, y)+(1−

k)·

I^t(x, y).

46. The apparatus of claim 25, further comprising:

an interpolator that interpolates a new frame as a function of the two existing frames based on the motion vector and a degree of having a pattern-like object in a frame.

47. A motion compensation apparatus for use in an image encoder, comprising:

a motion estimator that estimates a motion between one image frame and another image frame by finding a match for a block of one frame within a search area in another frame; and

a pattern detector that determines whether the motion estimation is being performed near pattern-like objects in the frames.

48. A motion compensation encoding apparatus for use in an image encoder having a memory that maintains existing frames including a number of blocks, wherein at a time t, I^t denotes the t^th existing frame, I^t(x, y) denotes the pixel value at location (x, y) in the frame I^t, and B_t(x, y) denotes the block at location (x, y) in the t^th frame, the apparatus comprising:

a motion estimator that finds a match for a block of one frame within a search area in another frame by comparing a block B_t(x₁, y₁) in I^t and another block B<sub>t−

1</sub>(x₂, y₂) in I<sup>t−

1</sup> using a cost function that is a measure of a mismatch between the two matched blocks;

a motion vector generator that generates a motion vector representing a geometrical displacement between the two matched blocks;

a pattern detector that determines whether a motion estimation is being performed near pattern-like objects in the frames; and

an interpolator that interpolates a new frame I* based on the existing frames I^t and I<sup>t−

1</sup>, wherein a frame pixel I*(x, y) is expressed as;

I*(x, y)=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

where v_x and v_y represent components of said motion vector, and k is a pre-determined constant between 0 and 1 associated with a relative location of the frame I* in time.

49. The apparatus of claim 48, wherein:

the pattern detector further determines a factor α

that indicates a degree of having a pattern-like object in a frame; and

the interpolator further determines a pixel I*(x, y) based on the factor α

such that

I*(x, y)=α

·

I_v+(1−

α

)·

I₀;

where

I_v=k·

I<sup>t−

1</sup>(x+v_x, y+v_y)+(1−

k)·

I^t(x−

v_x, y−

v_y),

and

I₀=k·

I<sup>t−

1</sup>(x, y)+(1−

k)·

I^t(x, y).