Method and device for image interpolation with motion compensation

• US 7,302,003 B2
• Filed: 09/03/2003
• Issued: 11/27/2007
• Est. Priority Date: 09/03/2002
• Status: Expired due to Fees

• Current Assignee: Snaptrack Incorporated (Qualcomm, Inc.)
• Original Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Inventors: Battistella, Andrea
• Primary Examiner(s): Diep; Nhon
• Application Number:
  US10/654,582
• Publication Number:
  US 20040165662A1
• Time in Patent Office: 1,546 Days
• Field of Search: None
• 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 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 method of interpolating images intended to be incorporated, into a sequence of moving images, each between a first original image and a second original image of the sequence, comprises an estimation of a motion vector associated with a given pixel block of a current interpolated image. This estimation comprises the preselection of P first motion vectors associated with first other pixel blocks that are adjacent to the given pixel block in the current interpolated image, for which there is already an estimated motion vector. It also comprises the preselection of at most Q second motion vectors associated respectively with second other pixel blocks adjacent to the given pixel block in the preceding interpolated image. Finally, it comprises the selection of the motion vector which minimizes a cost function from the first and second preselected motion vectors.

Claims

1. A method of interpolating images comprising:

receiving a sequence of video images for interpolation between a first original image (Or(t−

T)) and a second original image (Or(t+T)) of the sequence, wherein the interpolation includes estimation of at least one motion vector associated with at least one pixel of a current interpolated image (In(t));

oversampling the video images; and

displaying the video images which has been oversampled;

wherein the estimation of the motion vector associated with a given pixel block (B(x,y)) of a current interpolated image includes;

a) preselecting a given number P of first motion vectors associated respectively with first other pixel blocks (B(x−

1,y), B(x,y−

1)) that are adjacent to the given pixel block in the current interpolated image, where P is an integer, for which there is already an estimated motion vector;

b) preselecting a given number Q of second motion vectors associated respectively with second other pixel blocks (B(x+1,y), B(x,y+1)) that are adjacent to the given pixel block in a previous interpolated image (In(t−

2T)), where Q is an integer; and

c) selecting, from the first motion vectors and the second motion vectors, the motion vector which minimizes a cost function between;

pixels of a first given pixel block, which is pointed into the first original image by the motion vector from the given pixel blocks of the current interpolated image; and

pixels of a second given pixel blocks, which is pointed into the second original image by a symmetrical vector of the motion vector from the given pixel block of the current interpolated image.

2. The method according to claim 1, wherein the estimation of the motion vector associated with the given pixel block further comprises:

d) generating a given number K of corrected motion vectors, wherein each corrected motion vector corresponds to the motion vector previously selected to minimize the cost function and assigned a respective given pair of correction values;

e) selecting from the corrected motion vectors that minimizes the cost function is selected from the corrected motion vectors; and

f) replacing the motion vector selected at step c) with the corrected motion vector selected at step e).

3. The method according to claim 2, characterized in that, at step f), the motion vector selected at step c) is replaced with the corrected motion vector selected at step e) only if the corrected motion vector has a corresponding a value less than a value of the cost function.

4. The method according to claim 1, characterized in that the cost function is defined from a sum-of-the-absolute-differences estimator given by:

5. The method according to claim 2, characterized in that the correction values are additive coefficients defined, from a value of a pair of coordinates m,n of the motion vector, by all pairs of coordinates m±

m1,n±

n1, where m1 is an integer taking all values between 0 and M1, where n1 is an integer taking all values between 0 and N1, and where M1 and N1 are given non-zero integers.

6. The method according to claim 1, characterized in that the second other pixel blocks are different from the first other pixel blocks.

7. The method according to claim 1, characterized in that at least one of the first other pixel blocks and the second other pixel blocks are adjacent to the given pixel block in the video images.

8. The method according to claim 1, characterized in that at least one of P and Q is equal to 2.

9. The method according to claim 7, characterized by:

indices identifying a position of the given pixel block in the video images by x and y; and

indices identifying at least one of;

positions of the two first other pixel blocks by x and y−

1 and by x−

1 and y, respectively; and

positions of the two second other pixel blocks are identified by x+1 and y and by x and y+1 respectively.

10. The method according to claim 1, characterized in that a value of at least one pixel of the current interpolated image is given by:

11. The method according to claim 1, characterized in that a value of at least one pixel of the current interpolated image is given by the following relation:

12. The method according to claim 1, characterized in that a value of at least one pixel of the current interpolated image is given by the following relation:

13. The method according to claim 1, characterized in that a value of at least one pixel of the current interpolated image is given by the following relation:

14. The method according to claim 1, characterized in that a value of at least one pixel of the current interpolated image is given by the following relation:

Pin(i,j,t)=median(P_stat(i,j,t),P_dyn(i,j,t),P_mid(i,j,t))

where Pstat(i,j,t), Pdyn(i,j,t) and Pmid(i,j,t) are values given by the following relations

Pstat(i,i,t)=

15. A device for interpolating images comprising:

a receiver to receive a sequence of video images for interpolation between a first original image (Or(t−

T)) and a second original image (Or(t+T)) of the sequence, wherein the interpolation includes a means for estimating at least one motion vector associated with at least one given pixel block (B(x,y)) of a current interpolated image (In(t));

wherein the means for estimating the at least one a motion vector associated with the at least one given pixel block (B(x,y)) of the current interpolated image includes;

first preselecting means for preselecting a given number P of first motion vectors associated respectively with first other pixel blocks (B(x−

1,y), B(x,y−

1)) that are adjacent to the given pixel block in the current interpolated image, where P is an integer, for which there is already an estimated motion vector;

second preselecting means for preselecting a given number Q of second motion vectors associated respectively with second other pixel blocks (B(x+1,y), B(x,y+1)) that are adjacent to the given pixel block in the previous interpolated image (In(t−

2)), where Q is an integer; and

first selecting means for selecting, from the first motion vectors and the second motion vectors, the motion vector which minimizes a cost function between;

pixels of a first given pixel block, which is pointed into the first original image by the motion vector from the given pixel blocks of the current interpolated image; and

pixels of a second given pixel blocks, which is pointed into the second original image by a symmetrical vector of the motion vector from the given pixel block of the current interpolated image.

16. The device according to claim 15, wherein the estimation means further comprise:

generating means for generating a given number K of corrected motion vectors, wherein each corrected motion vector corresponds to the motion vector previously selected to minimize the cost function and assigned a respective given pair of correction values;

selecting means for selecting from the corrected motion vectors that minimizes the cost function is selected from the corrected motion vectors; and

replacing means for replacing the motion vector selected by the first selection means with the corrected motion vector selected the second selection means.

17. The device according to claim 15, wherein the replacing means includes replacing the motion vector selected by the first selection means with the corrected motion vector selected at the second selection means only if the corrected motion vector has a corresponding a value less than a value of the cost function.

18. The device according to claim 15, characterized in that the cost function is defined from a sum-of-the-absolute-differences estimator given by:

19. The device according to claim 16, characterized in that the correction values are additive coefficients defined, from a value of a pair of coordinates m,n of the motion vector, by all pairs of coordinates m±

m1, n±

n1, where m1 is an integer taking all values between 0 and M1, where n1 is an integer taking all values between 0 and N1, and where M1 and N1 are given non-zero integers.

20. The device according to claim 15, characterized in that the second other pixel blocks are different from the first other pixel blocks.

21. The device according to claim 15, further comprising:

a communicating terminal including;

receiving means for receiving coded data corresponding to the video images;

decoding means for decoding coded data received by the receiving means;

means for oversampling the video; and

display means for displaying the oversampled video.

22. A communicating terminal comprising:

a receiver to receive a sequence of coded data corresponding to video images for interpolation between a first original image (Or(t−

T)) and a second original image (Or(t+T)) of the sequence, wherein the interpolation includes a means for estimating at least one motion vector associated with at least one given pixel block (B(x,y)) of a current interpolated image (In(t));

decoding means for decoding coded data received by the receiving means;

means for oversampling the video; and

display means for displaying the oversam pled video;

wherein the means for estimating the at least one motion vector associated with the at lease one given pixel block (B(x,y)) of the current interpolated image includes;

first preselecting means for preselecting a given number P of first motion vectors associated respectively with first other pixel blocks (B(x−

1,y), B(x,y−

1)) that are adjacent to the given pixel block in the current interpolated image, where P is an integer, for which there is already an estimated motion vector;

second preselecting means for preselecting a given number Q of second motion vectors associated respectively with second other pixel blocks (B(x+1,y), B(x,y+1)) that are adjacent to the given pixel block in the previous interpolated image (In(t−

2T)), where Q is an integer; and

first selecting means for selecting, from the first motion vectors and the second motion vectors, the motion vector which minimizes a cost function between;

pixels of a first given pixel block, which is pointed into the first original image by the motion vector from the given pixel blocks of the current interpolated image; and

pixels of a second given pixel blocks, which is pointed into the second original image by a symmetrical vector of the motion vector from the given pixel block of the current interpolated image.