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

• US 20040247028A1
• Filed: 06/06/2003
• Published: 12/09/2004
• 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
• Granted Patent: US 7,336,707 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• 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 motion between one image frame and another image frame, comprising the steps of:

dividing each frame into a number of blocks;

finding a match for a block of one frame within a search area in another frame; and

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

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

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

3. The method of claim 2, 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 steps of finding a match further includes the steps of comparing one block B_t(x₁,y₁) in the t^th frame and another block B<sub>t−

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

1^th frame using a cost function that is a measure of the mismatch between the two matched blocks.

4. The method of claim 3, wherein:

(a) the steps of finding a match further includes 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 the search locations satisfying (d_x,d_y)ε

{(p,q)|p=−

D_{x, . . . ,0}, . . . , D 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;

$\mathrm{SAD}<br><br>\left(d_x,d_y\right)=<br><br>D<br><br>\left(x,y\right)<br><br><br><br><br><br>\text{\hspace{1em}<br><br>}=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>D_{i,j}<br><br>,$

 

for a block of N×

M pixels;

where;

D(d_x,d_y)=B_t(x,y)−

B<sub>t−

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

$D<br><br>\left(d_x,d_y\right)=\left[\begin{array}{cccc}{D}_{1,1}& D_{1,2}& \mathrm{\cdots <br><br>}& D_{1,M}\\ D_{2,1}& D_{2,2}& \mathrm{\cdots <br><br>}& D_{2,M}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \text{\hspace{1em}<br><br>}& \mathrm{⋮<br><br>}\\ D_{N,1}& D_{N,1}& \mathrm{\cdots <br><br>}& D_{N,M}\end{array}\right];<br><br>$

 

and

(b) the steps of determining said motion vector further includes the steps of determining a motion vector (v_x,v_y) which provides the minimum SAD, wherein the motion vector (v_x,v_y) satisfies the condition SAD(v_x,v_y)≦

SAD(d_x,d_y), for one or more search locations of (d_x,d_y) in the search range.

5. The method of claim 4, wherein for a full search range, the motion vector (v_x,v_y) is one which 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 the set of search locations.

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

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

_x, and φ

_y, respectively, wherein;

${\mathrm{\phi <br><br>}}_x<br><br>\left(d_x\right)=\underset{q=-D_y}{\overset{D_y}{\sum <br><br>}}<br><br>\mathrm{SAD}<br><br>\left(d_x,q\right),d_x=-D_x,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_x$$\mathrm{and}$${\mathrm{\phi <br><br>}}_y<br><br>\left(d_y\right)=\underset{p=-D_x}{\overset{D_x}{\sum <br><br>}}<br><br>\mathrm{SAD}<br><br>\left(p,d_y\right),d_y=-D_y,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_y.$

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

(a) determining values L_x and L_y, wherein;

$L_x=\underset{d_x=-D_x+1}{\overset{D_x}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_x\right)-\mathrm{\phi <br><br>}<br><br>\left(d_x-1\right)<br><br>$$\mathrm{and}$$L_y=\underset{d_y=-D_y+1}{\overset{D_y}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_y\right)-\mathrm{\phi <br><br>}<br><br>\left(d_y-1\right)<br><br>;<br><br>$

such that as the value of L_x increases, it is more probable that the horizontal projection function φ

_x has multiple minima, and as the value of L_y increases, it is more probable that the vertical projection function φ

_y has multiple minima; and

(b) estimating an overall minima L_max in the SAD, as;

L_max=max(L_x, L_y),

 

wherein as the value of L_max increases, it is more likely that the SAD may have multiple minima, indicating a pattern-like object in the frame.

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

determining a value α

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

α

=min(1.0, L_max/K),

 

where K is a pre-determined constant.

9. The method of claim 3, wherein:

(a) the steps of finding a match further includes 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,(x+d,,y+dy) are displaced by the vector(d.,dy);

where a block difference signal D(d.,dy) is expressed as;

D(d,,dy)=B,,(x,y)-B,(x+d_,y+dy), and said cost functions is expressed as;

$\hspace{1em}<br><br>\begin{array}{c}\mathrm{SAD}<br><br>\left(d_x,d_y\right)=<br><br>D<br><br>\left(x,y\right)<br><br>\\ =\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>D_{i,j}<br><br>\end{array}$

 

for blocks on N×

M pixels; and

(b) the steps of determining said motion vector includes the steps of determining a motion vector (vX,vy) which provides the minimum SAD, and is determined as one which satisfies the condition SAD(v.vy)≦

SAD(d,,dy), for one or more search locations of (d.,dy) in the search range.

10. The method of claim 9, wherein for a full search range in the motion estimation, the motion vector (v,vy) is one which satisfies the condition SAD(v_,vy)≦

SAD(d,,dy), for all (d_,,dy)ER, whereinR={(p,q)lp=-D,,.,O,.,Dx andq=-Dy,, ,0, ...,Dy}.

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

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

_x and φ

_y, respectively, wherein;

${\mathrm{\phi <br><br>}}_x<br><br>\left(d_x\right)=\underset{q=-D_y}{\overset{D_y}{\sum <br><br>}}<br><br>\mathrm{SAD}<br><br>\left(d_x,q\right),d_x=-D_x,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_x$$\mathrm{and}$${\mathrm{\phi <br><br>}}_y<br><br>\left(d_y\right)=\underset{p=-D_x}{\overset{D_x}{\sum <br><br>}}<br><br>\mathrm{SAD}<br><br>\left(p,d_y\right),d_y=-D_y,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_y.$

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

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

$L_x=\underset{d_x=-D_x+1}{\overset{D_x}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_x\right)-\mathrm{\phi <br><br>}<br><br>\left(d_x-1\right)<br><br>$$\mathrm{and}$$L_y=\underset{d_y=-D_y+1}{\overset{D_y}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_y\right)-\mathrm{\phi <br><br>}<br><br>\left(d_y-1\right)<br><br>;<br><br>$

 

wherein as the value of L_x increases, it is more probable that the horizontal projection function φ

_x has multiple minima, and as the value of L_y increases, it is more probable that the vertical projection function φ

_y has multiple minima; and

(b) estimating an overall minima L_max in the SAD as;

L_max=max(L_x,L_y)

 

wherein as the value of L_max increases, it is more likely that the SAD may have multiple minima, indicating a pattern-like object in the frame.

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

determining a value α

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

α

=min(1.0,L_max/K),

 

where K is a pre-determined constant.

14. The method of claim 3, wherein:

(a) the steps of finding a match further includes 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_t−

1(x+d_x,y+d_y) are displaced by the vector (2·

d_x,2·

d_y);

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

D(d_y,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;

$\hspace{1em}<br><br>\begin{array}{c}\mathrm{SAD}<br><br>\left(d_x,d_y\right)=<br><br>D<br><br>\left(x,y\right)<br><br>\\ =\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>D_{i,j}<br><br>\end{array}$

 

for blocks on N×

M pixels; and

(b) the steps of determining said motion vector further includes the steps of determining a motion vector (v_x,v_y) which provides the minimum SAD, such that the motion vector (v_x,v_y) is determined as one which satisfies the condition SAD(v_x,v_y)≦

SAD(d_x,d_y), for one or more search locations.

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 which 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 motion estimation is being performed near pattern-like objects in the frames, further includes the steps of:

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

_x and φ

_y, respectively, wherein;

${\mathrm{\phi <br><br>}}_x<br><br>\left(d_x\right)=\underset{q=-D_y}{\overset{D_y}{\sum <br><br>}}<br><br>\mathrm{SAD}<br><br>\left(d_x,q\right),d_x=-D_x,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_x$$\mathrm{and}$${\mathrm{\phi <br><br>}}_y<br><br>\left(d_y\right)=\underset{p=-D_x}{\overset{D_x}{\sum <br><br>}}<br><br>\mathrm{SAD}<br><br>\left(p,d_y\right),d_y=-D_y,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_y.$

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

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

$L_x=\underset{d_x=-D_x+1}{\overset{D_x}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_x\right)-\mathrm{\phi <br><br>}<br><br>\left(d_x-1\right)<br><br>$$\mathrm{and}$$L_y=\underset{d_y=-D_y+1}{\overset{D_y}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_y\right)-\mathrm{\phi <br><br>}<br><br>\left(d_y-1\right)<br><br>;<br><br>$

 

wherein as the value of L_x increases, it is more probable that the horizontal projection function φ

_x has multiple minima, and as the value of L_y increases, it is more probable that the vertical projection function φ

_y has multiple minima; and

(b) estimating an overall minima L_max in the SAD as;

L_max=max(L_x,L_y)

 

wherein as the value of L_max increases, it is more likely that the SAD may have multiple minima, indicating a pattern-like object in the frame.

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

determining a value a that indicates the degree of being a pattern-like object in a frame, wherein;

α

=min(1.0,L_max/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 motion estimation, wherein the frames I^t and I<sup>t−

1</sup> are the i^th and i−

I^th frames, respectively, and the to-be-reconstructed frame I* is sequentially in 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 motion estimation is being performed near pattern-like objects in the frames further includes the steps of determining a factor ax that indicates the degree of being a pattern-like object in a frame; and

the steps of interpolating further includes 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*(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 being 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 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;

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 the t^th frame and another block B<sub>t−

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

1^th frame using a cost function that is a measure of the mismatch between the two matched blocks;

determining a motion vector representing the geometrical displacement between the two matched blocks, by determining whether 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_t)+(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 the 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 includes the steps of determining a factor α

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

the steps of interpolating further includes 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 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 motion estimation is being performed near pattern-like objects in the frames.

26. The apparatus of claim 25, further comprising:

a motion vector generator that determines a motion vector representing the 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 the t^th frame and another block B<sub>t−

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

1^th frame 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_t(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;

$\hspace{1em}<br><br>\begin{array}{c}\mathrm{SAD}<br><br>\left(d_x,d_y\right)=<br><br>D<br><br>\left(x,y\right)<br><br>\\ =\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>D_{i,j}<br><br>,\end{array}$

 

for a block of N×

M pixels;

where;

D(d_x,d_y)=B_t(x,y)−

B<sub>t−

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

$D<br><br>\left(d_x,d_y\right)=\left[\begin{array}{cccc}{D}_{1,1}& D_{1,2}& \mathrm{\cdots <br><br>}& D_{1,M}\\ D_{2,1}& D_{2,2}& \mathrm{\cdots <br><br>}& D_{2,M}\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \text{\hspace{1em}<br><br>}& \mathrm{⋮<br><br>}\\ D_{N,1}& D_{N,1}& \mathrm{\cdots <br><br>}& D_{N,M}\end{array}\right];<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$

 

and

the motion vector generator determines a motion vector (v_x,v_y) which provides the minimum SAD, wherein the motion vector (v_x,v_y) satisfies the condition SAD(v_x,v_y)≦

SAD(d_x,d_y), for one or more search locations of (d_y,d_y) in the search range.

29. The apparatus of claim 28, wherein for a full search range, the motion vector (v_x,v_y) is one which 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 the 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;

$L_x=\underset{d_x=-D_x+1}{\overset{D_x}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_x\right)-\mathrm{\phi <br><br>}<br><br>\left(d_x-1\right)<br><br>$$\mathrm{and}$$L_y=\underset{d_y=-D_y+1}{\overset{D_y}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_y\right)-\mathrm{\phi <br><br>}<br><br>\left(d_y-1\right)<br><br>;<br><br>$

such that as the value of L_x increases, it is more probable that the horizontal projection function φ

_x has multiple minima, and as the value of L_y increases, it is more probable that the vertical projection function φ

_y has multiple minima; and

and a minima estimator that estimates an overall minima L_max in the SAD, as;

L_max=max(L_x,L_y)

wherein as the value of L_max increases, it is more likely that the SAD may have multiple minima, indicating a pattern-like object in the frame.

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

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

α

=min(1.0,L_max/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 functions is expressed as;

$\mathrm{SAD}<br><br>\left(d_x,d_y\right)=<br><br>D<br><br>\left(x,y\right)<br><br><br><br><br><br>\text{\hspace{1em}<br><br>}=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>D_{i,j}<br><br>$

 

for blocks on N×

M pixels; and

the motion vector generator determines a motion vector (v_x,v_y) which provides the minimum SAD, and is determined as one which satisfies the condition SAD(v_x,v_y)≦

SAD(d_x,d_y), for one or more search locations of (d_x,d_y) in the search range.

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 which 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:

projection function block that utilizes horizontal and vertical projection functions φ

_x and φ

_y, respectively, wherein;

${\mathrm{\phi <br><br>}}_x<br><br>\left(d_x\right)=\underset{q=-D_y}{\overset{D_y}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{SAD}<br><br>\left(d_x,q\right),\begin{array}{cc}{d}_x=-D_x,\mathrm{\cdots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\cdots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_x& \text{\hspace{1em}<br><br>}\end{array}$$\mathrm{and}$${\mathrm{\phi <br><br>}}_y<br><br>\left(d_y\right)=\underset{p=-D_x}{\overset{D_x}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{SAD}<br><br>\left(p,d_y\right),\begin{array}{cc}{d}_y=-D_y,\mathrm{\cdots <br><br>}<br><br>\text{\hspace{1em}<br><br>},0,\mathrm{\cdots <br><br>}<br><br>\text{\hspace{1em}<br><br>},D_y.& \text{\hspace{1em}<br><br>}\end{array}$

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;

$L_x=\underset{d_x=-D_x+1}{\overset{D_x}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_x\right)-\mathrm{\phi <br><br>}<br><br>\left(d_x-1\right)<br><br>$$\mathrm{and}$$L_y=\underset{d_y=-D_y+1}{\overset{D_y}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_y\right)-\mathrm{\phi <br><br>}<br><br>\left(d_y-1\right)<br><br>;<br><br>$

wherein as the value of L_x increases, it is more probable that the horizontal projection function φ

_x has multiple minima, and as the value of L_y increases, it is more probable that the vertical projection function φ

_y has multiple minima; and

a minima estimator that estimates an overall minima L_max in the SAD as;

L_max−

max(L_x,L_y)

wherein as the value of L_max increases, it is more likely that the SAD may have multiple minima, indicating a pattern-like object in the frame.

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

that indicates the degree of being 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 the 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;

$\mathrm{SAD}<br><br>\left(d_x,d_y\right)=<br><br>D<br><br>\left(x,y\right)<br><br><br><br><br><br>\text{\hspace{1em}<br><br>}=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>D_{i,j}<br><br>$

 

for blocks on N×

M pixels; and

the motion vector generator further determines a motion vector (v_x,v_y) which provides the minimum SAD, such that the motion vector (v_x,v_y) is determined as one which satisfies the condition SAD(v_x,v_y)≦

SAD(d_x,d_y), for one or more search locations.

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 which 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 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;

$L_x=\underset{d_x=-D_x+1}{\overset{D_x}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_x\right)-\mathrm{\phi <br><br>}<br><br>\left(d_x-1\right)<br><br>$

and

$L_y=\underset{d_y=-D_y+1}{\overset{D_y}{\sum <br><br>}}<br><br><br><br>\mathrm{\phi <br><br>}<br><br>\left(d_y\right)-\mathrm{\phi <br><br>}<br><br>\left(d_y-1\right)<br><br>;<br><br>$

wherein as the value of L_x increases, it is more probable that the horizontal projection function φ

_x has multiple minima, and as the value of L_y increases, it is more probable that the vertical projection function φ

_y has multiple minima; and

a minima estimator that estimates an overall minima L_max in the SAD as;

L_max=max(L_x,L_y)

wherein as the value of L_max increases, it is more likely that the SAD may have multiple minima, indicating a pattern-like object in the frame.

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

value ae that indicates the degree of being 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 frames I^t and I<sup>t−

1</sup> are the i^th and i−

1^th frames, respectively, and the to-be-reconstructed frame I* is sequentially in 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 the relative location of the frame I* in time.

45. The apparatus of claim 44, wherein:

the pattern detector further determines a factor α

that indicates the degree of being 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_vk·

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 being a pattern-like object in a frame.

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

a motion estimator that estimates 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 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 the t^th frame and another block B<sub>t−

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

1^th frame using a cost function that is a measure of the mismatch between the two matched blocks;

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

a pattern detector that determines whether 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^t(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 the relative location of the frame I* in time.

49. The apparatus of claim 48, wherein:

pattern detector determine s a factor α

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

the interpolator 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).