Motion compensation image interpolation--frame rate conversion for HDTV

• US 6,229,570 B1
• Filed: 09/25/1998
• Issued: 05/08/2001
• Est. Priority Date: 09/25/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Puri, Narindra N., Petajan, Eric D., Bugwadia, Kobad
• Primary Examiner(s): Eisenzopf, Reinhard
• Assistant Examiner(s): DESIR, JEAN WICEL
• Application Number:
  US09/161,337
• Time in Patent Office: 956 Days
• Field of Search: 348/441, 348/445, 348/446, 348/443, 348/451, 348/452, 348/459, 348/699, 348/700, 348/416.1, 375/240.16, 375/240.17, 382/236, 382/238, 386/111
• US Class Current: 348/441
• CPC Class Codes: H04N 7/0125 one of the standards being a high definition standard
• CPC Class Codes: H04N 7/014 involving the use of motion vectors motion estimation and compensation in video coding H04N19/51

Abstract

A process for up-converting an existing video source signal having a low frequency (frames/second) to a high frequency signal for use with High Definition Television (HDTV). The process samples the existing frames in the existing video signal and calculates integer displacements of pels within the existing frames. A polynomial curve fit is then performed on the displacements to obtain estimates of horizontal and vertical displacements of each block in each existing frame. Based on the alignment of the blocks within a sampling grid on each frame, the blocks are segregated into groups. The block groups are then used to interpolate missing or required frames of the high frequency signal in a piecemeal manner by utilizing blocks of a particular block group to estimate a corresponding block in a frame of the high frequency signal.

Claims

1. A method of converting a frame rate of an existing video signal having a sampling resolution to a higher frame rate video signal, the existing video signal having a sequence of successive-in-time video frames each containing an amount of pels having pel values, comprising the steps of:

(a) defining a number (n) of sampling locations to be present in a given sequence of the successive-in-time video frames of the existing video signal, wherein n is an even number;

(b) increasing the sampling resolution of the existing video signal by performing linear spatial interpolation on an image sequence represented by the successive-in-time video frames of the existing video signal for a number of times to form a high resolution sequence of frames having a number of available frames;

(c) estimating integer pel-shift values from the high resolution sequence of available frames;

(d) constructing vectors S_x and S_y representing estimated pel value displacements at a time value (t) in a first time vector (t₁) of available frames with respect to a first available frame in the high resolution sequence of available frames, wherein vector S_x represents horizontal displacement pel values and vector S_y represents vertical displacement pel values;

(e) performing a polynomial curve fit of the values of vectors S_x and S_y for each value in time vector t₁ to obtain a motion estimate of an image represented by the sequence of available frames;

(f) estimating, based upon the polynomial curve fit, pel shift values for the horizontal and vertical directions at time values corresponding to times at which interpolated frames are to be used to form the higher frame rate video signal;

(g) segregating the frames of the existing signal into groups utilizing the estimated displacements of available frames from said step (d) and the pel shift values from said step (f) so that frames sharing common sampling grids are grouped together; and

(h) interpolating, based upon at least one of the groups of frames of the existing signal, one or more new frames for use in the higher frame rate video signal.

2. The method of claim 1, wherein said step (c) is performed by utilizing a block matching technique to measure displacement between two available frames by matching a rectangular measurement window in one frame with a corresponding measurement window of a search area contained in another frame, and wherein a match is achieved by conducting a search within the search area using a Minimum Absolute Difference (MAD) matching criterion.

3. The method of claim 1, wherein the polynomial curve fit for vector S_x of said step (e) is represented as P_x(t)=a₀+a₁t+a₂t²+ . . . +a_pt^p, wherein p is the smallest degree which is the best polynomial curve fit of the horizontal pet shift values of the sequence of available frames with respect to a first frame in the sequence of available frames, and wherein the polynomial curve fit for vector S_y of step (e) is represented as P_y(t)=b₀+b₁t+b₂t²+ . . . +b_qt^q, wherein q is the smallest degree which is the best polynomial curve fit of the vertical pet shift values of the sequence of available frames with respect to the first frame in the sequence of available frames.

4. The method of claim 1, wherein said step (g) of segregating frames is performed by measuring pel shifts in the vertical and horizontal directions between any two frames and grouping frames into a common group based on an integer value of the measured pet shifts.

5. The method of claim 1, wherein said step (h) of interpolating is performed by utilizing frames prior-in-time to a subject frame and subsequent-in-time to the subject frame.

6. A method of converting a frame rate of an existing video signal having a sampling resolution to a higher frame rate video signal, the existing video signal having a sequence of successive-in-time video frames representing a video scene having motion and each containing an amount of (pels) having pel values, comprising the steps of:

(a) dividing each frame of the existing video signal into blocks and defining a number (n) of sampling locations in a given sequence of the successive-intime video frames of the existing video signal, wherein n is an even number;

(b) increasing the sampling resolution of the existing video signal by performing linear spatial interpolation on an image sequence represented by the successive-in-time video frames of the existing video signal for a number of times equal to log₂n to form a high resolution sequence of frames having a number of available frames;

(c) estimating, for each block of the existing video signal, integer pel-shift values from the high resolution sequence of available frames;

(d) constructing vectors S_x and S_y representing estimated pel value displacements at a time value (t) in a first time vector (t₁) of available frames with respect to a first available frame in the high resolution sequence of available frames, wherein vector S_x represents horizontal displacement pel values and vector S_y represents vertical displacement pel values;

(e) performing a polynomial curve fit of the values of vectors S_x and S_y for each block and for each value in time vector t₁ to obtain, for each block, a motion estimate of an image represented by the sequence of available frames;

(f) estimating, based upon the polynomial curve fit, pel shift values for the horizontal and vertical displacements at time values corresponding to times at which interpolated frames are to be used to form the higher frame rate video signal;

(g) segregating each block of each of the frames of the existing signal into groups utilizing the estimated displacements of available blocks from said step (d) and the pel shift values from said step (f) so that blocks sharing common sampling grids are grouped together; and

(h) interpolating, based upon at least one of the estimated displacements of step (f) and from at least one of the common sampling grid block groups, one or more new blocks for use in constructing one or more new frames for the higher frame rate video signal.

7. The method of claim 6, wherein the polynomial curve fit for vector S_x of said step (e) is represented as P_x(t)=a₀+a₁t+a₂t²+ . . . +a_pt^p, wherein p is the smallest degree, which is the best polynomial curve fit of the horizontal pel shift values of the sequence of available frames with respect to a first frame in the sequence of available frames, and wherein the polynomial curve fit for vector S_y of step (e) is represented as P_y(t)=b_0+b1t+b₂t²+ . . . +b_qt^q, wherein q is the smallest degree which is the best polynomial curve fit of the vertical pel shift values of the sequence of available frames with respect to the first frame in the sequence of available frames.

8. The method of claim 6, wherein said step (g) of segregating blocks is performed by measuring pel shifts in the vertical and horizontal directions between any two blocks and grouping blocks into a common group based on an integer value of the measured pel shifts.

9. The method of claim 6, wherein said step (h) of interpolating is performed by utilizing blocks prior-in-time to a subject block and subsequent-in-time to the subject block.

10. The method of claim 9, wherein said step (h) of interpolating further comprises overlaying an existing frame with blocks of a common groups so that the existing frame is partially covered with the overlaid blocks and so that regions of some of the blocks overlap with each other, and assigning values to pets of a subject block based on the average pel values between the pels forming the overlaid regions.

11. The method of claim 6, further comprising the step of utilizing the motion estimates of each block derived from step (e) to increase the spatial resolution of said new frames.

12. The method of claim 11, further comprising the step of reducing noise in said new frames by averaging blocks having a common sampling grid.

13. A method of converting a frame rate of an existing video signal depicting three-dimensional motion and a sampling resolution to a higher frame rate video signal, the existing video signal having a sequence of successive-in-time available video frames representing a video scene having three-dimensional motion and each containing an amount of pels having pel values, comprising the steps of:

(a) selecting a total number of sampling points to be present in the existing image sequence for a vertical direction and a horizontal direction;

(b) performing linear spatial interpolation on the existing image sequence for expanding a sampling resolution by an amount (k) in both the horizontal direction and the vertical direction to generate an expanded image sequence;

(c) estimating integer displacements for each pel within frames of the expanded image sequence generated in step (b);

(d) selecting a frame of the expanded image sequence which lies within the sequence of successive-in-time available video frames, and dividing the estimated integer displacements for each pel in the selected frame by the amount (k) for generating motion estimates for each pel in the selected frame within the available frames of the original sequence;

(e) performing polynomial fits of the displacements in both a horizontal and a vertical direction for each pel in the selected frame within the other available frames;

(f) using the polynomial fits from step (e), estimating horizontal and vertical displacements of each pel of the selected frame at missing values of time corresponding to instances at which interpolation of missing frames is to be used to form the higher rate video signal;

(g) utilizing the estimated displacements of each pel from step (f), segregating the pels in the selected frame and pels from available and missing frames corresponding to the pels in the selected frame into groups, such that pels within the same group lie within the same sampling grid; and

(h) interpolating pel values of the missing frames based on corresponding pel values from available frames of the original sequence lying within the same sampling grid.

14. The method of claim 13, wherein step (c) is performed by:

selecting an available frame from the new sequence and segmenting the selected frame into triangular-shaped blocks, each having three vertices;

estimating motion vectors of the three vertices of each of the triangular blocks within the other available frames;

computing motion parameters for each block within the other available frames by solving a set of linear equations; and

computing the displacements for each pel inside each of the patches within the other available frames using the corresponding transformation functions f(x, y) and g(x, y) for each patch.

15. An apparatus for converting a frame rate of an existing video signal having a sampling resolution to a higher frame rate video signal, the existing video signal having a sequence of successive-in-time video frames each containing an amount of pels having pel values, said apparatus comprising:

means for defining a number (n) of sampling locations to be present in a given sequence of the successive-in-time video frames of the existing video signal, wherein n is an even number;

means for increasing the sampling resolution of the existing video signal by performing linear spatial interpolation on an image sequence represented by the successive-in-time video frames of the existing video signal for a number of times to form a high resolution sequence of frames having a number of available frames;

first means for estimating integer pel-shift values from the high resolution sequence of available frames;

means for constructing vectors S_x and S_y representing estimated pel value displacements at a time value (t) in a first time vector (t₁) of available frames with respect to a first available frame in the high resolution sequence of available frames, wherein vector S_x represents horizontal displacement pel values and vector S_y represents vertical displacement pel values;

means for performing a polynomial curve fit of the values of vectors S_x and S_y for each value in time vector t₁ to obtain a motion estimate of an image represented by the sequence of available frames;

second means for estimating, based upon the polynomial curve fit, pel shift values for the horizontal and vertical directions at time values corresponding to times at which interpolated frames are to be used to form the higher frame rate video signal;

means for segregating the frames of the existing signal into groups utilizing the estimated displacements of available frames and the pel shift values so that frames sharing common sampling grids are grouped together; and

means for interpolating, based upon at least one of the groups of frames of the existing signal, one or more new frames for use in the higher frame rate video signal.

16. The apparatus of claim 15, wherein said first estimating means utilizes a block matching technique to measure displacement between two available frames by matching a rectangular measurement window in one frame with a corresponding measurement window of a search area contained in another frame, and wherein a match is achieved by conducting a search within the search area using a Minimum Absolute Difference (MAD) matching criterion.

17. The apparatus of claim 15, wherein said second estimating means uses a polynomial curve fit for vector S_x represented as P_x(t)=a₀+a₁t+a₂t²+ . . . +a_pt^p, wherein p is the smallest degree which is the best polynomial curve fit of the horizontal pel shift values of the sequence of available frames with respect to a first frame in the sequence of available frames, and wherein the polynomial curve fit for vector S_y is represented as P_y(t)=b₀+b₁t+b₂t²+ . . . +b_qt^q, wherein q is the smallest degree which is the best polynomial curve fit of the vertical pel shift values of the sequence of available frames with respect to the first frame in the sequence of available frames.

18. The apparatus of claim 15, wherein said segregating means measures pel shifts in the vertical and horizontal directions between any two frames and groups frames into a common group based on an integer value of the measured pel shifts.

19. The apparatus of claim 15, wherein said interpolating means utilizes frames prior-in-time to a subject frame and subsequent-in-time to the subject frame.

20. An apparatus for converting a frame rate of an existing video signal having a sampling resolution to a higher frame rate video signal, the existing video signal having a sequence of successive-in-time video frames representing a video scene having motion and each containing an amount of (pels) having pel values, said apparatus comprising:

means for dividing each frame of the existing video signal into blocks and defining a number (n) of sampling locations in a given sequence of the successive-in-time video frames of the existing video signal, wherein n is an even number;

means for increasing the sampling resolution of the existing video signal by performing linear spatial interpolation on an image sequence represented by the successive-in-time video frames of the existing video signal for a number of times equal to log₂n to form a high resolution sequence of frames having a number of available frames;

first means for estimating, for each block of the existing video signal, integer pel-shift values from the high resolution sequence of available frames;

means for constructing vectors S_x and S_y representing estimated pel value displacements at a time value (t) in a first time vector (t₁) of available frames with respect to a first available frame in the high resolution sequence of available frames, wherein vector S_x represents horizontal displacement pel values and vector S_y represents vertical displacement pel values;

means for performing a polynomial curve fit of the values of vectors S_x and S_y for each block and for each value in time vector t₁ to obtain, for each block, a motion estimate of an image represented by the sequence of available frames;

second means for estimating, based upon the polynomial curve fit, pel shift values for the horizontal and vertical displacements at time values corresponding to times at which interpolated frames are to be used to form the higher frame rate video signal;

means for segregating each block of each of the frames of the existing signal into groups utilizing the estimated displacements of available blocks and the pel shift values so that blocks sharing common sampling grids are grouped together; and

means for interpolating, based upon at least one of the estimated displacements and from at least one of the common sampling grid block groups, one or more new blocks for use in constructing one or more new frames for the higher frame rate video signal.

21. The apparatus of claim 20, wherein said segregating means measures pel shifts in the vertical and horizontal directions between any two blocks and grouping blocks into a common group based on an integer value of the measured pel shifts.

22. The apparatus of claim 20, wherein said interpolating means utilizes blocks prior-in-time to a subject block and subsequent-in-time to the subject block.

23. The apparatus of claim 22, wherein said interpolating means further comprises means for overlaying an existing frame with blocks of a common group so that the existing frame is partially covered with the overlaid blocks and so that regions of some of the blocks overlap with each other, and means for assigning values to pels of a subject block based on the average pel values between the pels forming the overlaid regions.

24. An apparatus for converting a frame rate of an existing video signal depicting three-dimensional motion and a sampling resolution to a higher frame rate video signal, the existing video signal having a sequence of successive-in-time available video frames representing a video scene having three-dimensional motion and each containing an amount of pels having pel values, said apparatus comprising:

means for selecting a total number of sampling points to be present in the existing image sequence for a vertical direction and a horizontal direction;

means for performing linear spatial interpolation on the existing image sequence for expanding a sampling resolution by an amount (k) in both the horizontal direction and the vertical direction to generate an expanded image sequence;

means for estimating integer displacements for each pel within frames of the expanded image sequence;

means for selecting a frame of the expanded image sequence which lies within the sequence of successive-in-time available video frames, and for dividing the estimated integer displacements for each pel in the selected frame by the amount (k) for generating motion estimates for each pel in the selected frame within the available frames of the original sequence;

means for performing polynomial fits of the displacements in both a horizontal and a vertical direction for each pel in the selected frame within the other available frames and for estimating, based on the polynomial fits, horizontal and vertical displacements of each pel of the selected frame at missing values of time corresponding to instances at which interpolation of missing frames is to be used to form the higher rate video signal;

means for segregating, based on the estimated displacements of each pel, the pels in the selected frame and pels from available and missing frames corresponding to the pels in the selected frame into groups, such that pels within the same group lie within the same sampling grid; and

means for interpolating pel values of the missing frames based on corresponding pel values from available frames of the original sequence lying within the same sampling grid.