Interpolation of a sequence of images using motion analysis

• US 7,103,231 B2
• Filed: 11/03/2003
• Issued: 09/05/2006
• Est. Priority Date: 09/08/2000
• Status: Expired due to Term

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Gonsalves, Robert A., Dickie, Garth A., Fasciano, Peter J., Cornog, Katherine H., Fayan, Randy M.
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US10/700,285
• Publication Number:
  US 20040091170A1
• Time in Patent Office: 1,037 Days
• Field of Search: 382/284, 382/236, 382/276, 382/300, 382/293, 382/294, 382/107, 348/416.1, 348/413.1, 348/407.1, 348/446, 348/448, 348/451, 348/452, 348/450, 348/540, 358/450, 358/540, 345/629, 345/639, 345/640, 345/646, 345/648, 345/683
• US Class Current: 382/276
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 2210/44 Morphing
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: H04N 5/147 Scene change detection
• CPC Class Codes: H04N 7/014 involving the use of motion vectors motion estimation and compensation in video coding H04N19/51

Abstract

Two images are analyzed to compute a set of motion vectors that describes motion between the first and second images. A motion vector is computed for each pixel in an image at a time between the first and second images. This set of motion vectors may be defined at any time between the first and second images, such as the midpoint. The motion vectors may be computed using any of several techniques. An example technique is based on the constant brightness constraint, also referred to as optical flow. Each vector is specified at a pixel center in an image defined at the time between the first and second images. The vectors may point to points in the first and second images that are not on pixel centers. The motion vectors are used to warp the first and second images to a point in time of an output image between the first and second images using a factor that represents the time between the first and second image at which the output image occurs. The warped images are then blended using this factor to obtain the output image at the desired point in time between the first and second images. The point in time at which the output image occurs may be different from the time at which the motion vectors are determined. The same motion vectors may be used to determine two or more output images at different times between the first and second images. The images may be warped using a technique in which many small triangles are defined in an image corresponding in time to the point in time between the first and second images at which the motion vectors are determined. A transform for each small triangle from the point in time at which the motion vectors are determined to the desired interpolated image time is determined, e.g., the triangle is warped using the motion vectors associated with its vertices. For each pixel in each triangle in the output image, corresponding points in the first and second images are determined, and the first and second images are spatially sampled at these points. These samples for each pixel are combined to produce a value for that pixel in the output image.

Claims

1. A method for generating a transition of a plurality of output images from a first sequence of images to a second sequence of images wherein an image at an end of the first sequence is not contiguous with an image at a beginning of the second sequence, the method comprising:

for each output image, selecting a pair of a first image from the first sequence and a second image from the second sequence such that the output image has a point in time between the first image and the second image in the transition;

for each selected pair of first and second images, determining a set of motion vectors that describes motion between the first and second images;

for each output image, calculating a factor that represents the point in time, between the first and second images selected for the output image, at which the output image occurs;

for each output image, performing motion compensated interpolation to generate the output image according to the determined set of motion vectors and the calculated factor, wherein performing motion compensated interpolation comprises;

warping the selected first image according to the determined set of motion vectors and the calculated factor;

warping the selected second image according to the determined set of motion vectors and the calculated factor; and

blending the warped first image and the warped second image according to the calculated factor to obtain the output image.

2. The method of claim 1, wherein the first sequence has associated audio and the second sequence has associated audio, the method further comprising:

dissolving the audio associated with the first sequence to the audio associated with the second sequence.

3. The method of claim 1, wherein a combination of the output image and the first and second images provides an output sequence of images with a duration at playback different from a duration of an input sequence of images containing the first and second images at playback, and wherein the input sequence of images has associated audio with a duration, the method further comprising:

adjusting the duration of the audio to match the duration of the output sequence of images.

4. A method for processing a jump cut from a first image at an end of a first segment of sequence of images and corresponding audio and a second image at a beginning of a second segment in the sequence of images and corresponding audio, comprising:

processing the corresponding audio to identify an audio break between the audio corresponding to the first segment and the audio corresponding to the second segment;

determining a set of motion vectors that describes motion between the first and second images; and

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors at a point in time corresponding to the audio break.

5. The method of claim 4, further comprising:

dissolving the audio associated with the first sequence to the audio associated with the second sequence around the audio break.

6. A method for processing a jump cut from a first image at an end of a first segment of sequence of images and corresponding audio and a second image at a beginning of a second segment in the sequence of images and corresponding audio, comprising:

processing the corresponding audio to identify an audio break between the audio corresponding to the first segment and the audio corresponding to the second segment;

determining a set of motion vectors that describes motion between the first and second images;

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors point in time corresponding to the audio break; and

dissolving the audio associated with the first sequence to the audio associated with the second sequence around the audio break;

wherein determining a set of motion vectors comprises determining a motion vector for each pixel in an image at a map time between the first image and the second image, wherein the map time is different from the point in time of the output image, wherein the motion vector describes motion of a pixel of the image at the map time to a first point in the first image and a second point in the second image, and wherein performing motion compensated interpolation comprises;

calculating a factor that represents the point in time between the first image and the second image at which the output image occurs;

warping the first image according to the determined motion vectors and the factor;

warping the second image according to the determined motion vectors and the factor; and

blending the warped first image and the warped second image according to the factor to obtain the output image.

7. A method for processing a jump cut from a first image at an end of a first segment of sequence of images and corresponding audio and a second image at a beginning of a second segment in the sequence of images and corresponding audio, comprising:

processing the corresponding audio to identify an audio break between the audio corresponding to the first segment and the audio corresponding to the second segment;

determining a set of motion vectors that describes motion between the first and second images;

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors at a point in time corresponding to the audio break; and

dissolving the audio associated with the first sequence to the audio associated with the second sequence around the audio break;

wherein determining a set of motion vectors comprises determining a motion vector for each pixel in an image at a map time between the first image and the second image, wherein the motion vector describes motion of a pixel of the image at the map time to a first point in the first image and a second point in the second image, and wherein performing motion compensated interpolation comprises;

for each output image, calculating a factor that represents the point in time between the first image and the second image at which the output image occurs;

for each output image, warping the first image according to the determined motion vectors and the factor for the output image;

for each output image, warping the second image according to the determined motion vectors and the factor for the output image; and

for each output image, blending the warped first image and the warped second image according to the factor for the output image.

8. A method for changing duration of an input sequence of images with associated audio, wherein the input sequence of images and associated audio has a duration, comprising:

receiving an indication of a selection of an operation by an operator indicative of a desired duration of an output sequence of images, and, in response to the received indication;

selecting a first image and a second image in the sequence of images;

determining a set of motion vectors that describes motion between the first and second images;

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors;

repeating the selecting, determining and performing steps for multiple pairs of first and second images in the sequence of images to provide the output sequence of images; and

adjusting the duration of the associated audio to retain synchronization with the output sequence of images.

9. The method of claim 8, further comprising:

playing back the output sequence of images with the audio.

10. The method of claim 8, wherein adjusting comprises resampling of the audio.

11. The method of claim 8, wherein adjusting comprises time scaling of the audio.

12. A computer program product, comprising:

a computer readable medium;

computer program instructions stored on the computer readable medium that, when processed by a computer, instruct the computer to perform a method for generating a transition of a plurality of output images from a first sequence of images to a second sequence of images wherein an image at an end of the first sequence is not contiguous with an image at a beginning of the second sequence, the method comprising;

for each output image, selecting a pair of a first image from the first sequence and a second image from the second sequence such that the output image has a point in time between the first image and the second image in the transition;

for each selected pair of first and second images, determining a set of motion vectors that describes motion between the first and second images;

for each output image, calculating a factor that represents the point in time, between the first and second images selected for the output image, at which the output image occurs;

for each output image, performing motion compensated interpolation to generate the output image according to the determined set of motion vectors and the calculated factor, wherein performing motion compensated interpolation comprises;

warping the selected first image according to the determined set of motion vectors and the calculated factor;

warping the selected second image according to the determined set of motion vectors and the calculated factor; and

blending the warped first image and the warped second image according to the calculated factor to obtain the output image.

13. The computer program product of claim 12, wherein the first sequence has associated audio and the second sequence has associated audio, the method further comprising:

dissolving the audio associated with the first sequence to the audio associated with the second sequence.

14. The computer program product of claim 12, wherein a combination of the output image and the first and second images provides an output sequence of images with a duration at playback different from a duration of an input sequence of images containing the first and second images at playback, and wherein the input sequence of images has associated audio with a duration, the method further comprising:

adjusting the duration of the audio to match the duration of the output sequence of images.

15. A computer program product, comprising:

a computer readable medium;

computer program instructions stored on the computer readable medium that, when processed by a computer, instruct the computer to perform a method for processing a jump cut from a first image at an end of a first segment of sequence of images and corresponding audio and a second image at a beginning of a second segment in the sequence of images and corresponding audio, comprising;

processing the corresponding audio to identify an audio break between the audio corresponding to the first segment and the audio corresponding to the second segment;

determining a set of motion vectors that describes motion between the first and second images; and

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors at a point in time corresponding to the audio break.

16. The computer program product of claim 15, further comprising:

dissolving the audio associated with the first sequence to the audio associated with the second sequence around the audio break.

17. A computer program product, comprising:

a computer readable medium;

computer program instructions stored on the computer readable medium that, when processed by a computer, instruct the computer to perform a method for processing a jump cut from a first image at an end of a first segment of sequence of images and corresponding audio and a second image at a beginning of a second segment in the sequence of images and corresponding audio, comprising;

processing the corresponding audio to identify an audio break between the audio corresponding to the first segment and the audio corresponding to the second segment;

determining a set of motion vectors that describes motion between the first and second images;

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors at a point in time corresponding to the audio break; and

dissolving the audio associated with the first sequence to the audio associated with the second sequence around the audio break;

wherein determining a set of motion vectors comprises determining a motion vector for each pixel in an image at a map time between the first image and the second image, wherein the map time is different from the point in time of the output image, wherein the motion vector describes motion of a pixel of the image at the map time to a first point in the first image and a second point in the second image, and wherein performing motion compensated interpolation comprises;

calculating a factor that represents the point in time between the first image and the second image at which the output image occurs;

warping the first image according to the determined motion vectors and the factor;

warping the second image according to the determined motion vectors and the factor; and

blending the warped first image and the warped second image according to the factor to obtain the output image.

18. A computer program product, comprising:

a computer readable medium;

computer program instructions stored on the computer readable medium that, when processed by a computer, instruct the computer to perform a method for processing a jump cut from a first image at an end of a first segment of sequence of images and corresponding audio and a second image at a beginning of a second segment in the sequence of images and corresponding audio, comprising;

processing the corresponding audio to identify an audio break between the audio corresponding to the first segment and the audio corresponding to the second segment;

determining a set of motion vectors that describes motion between the first and second images;

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors at a point in time corresponding to the audio break; and

dissolving the audio associated with the first sequence to the audio associated with the second sequence around the audio break;

wherein determining a set of motion vectors comprises determining a motion vector for each pixel in an image at a map time between the first image and the second image, wherein the motion vector describes motion of a pixel of the image at the map time to a first point in the first image and a second point in the second image, and wherein performing motion compensated interpolation comprises;

for each output image, calculating a factor that represents the point in time between the first image and the second image at which the output image occurs;

for each output image, warping the first image according to the determined motion vectors and the factor for the output image;

for each output image, warping the second image according to the determined motion vectors and the factor for the output image; and

for each output image, blending the warped first image and the warped second image according to the factor for the output image.

19. A computer program product, comprising:

a computer readable medium;

computer program instructions stored on the computer readable medium that, when processed by a computer, instruct the computer to perform a method for changing duration of an input sequence of images with associated audio, wherein the input sequence of images and associated audio has a duration, comprising;

receiving an indication of a selection of an operation by an operator indicative of a desired duration of an output sequence of images, and, in response to the received indication;

selecting a first image and a second image in the sequence of images;

determining a set of motion vectors that describes motion between the first and second images;

performing motion compensated interpolation to generate one or more images between the first image and the second image according to the determined set of motion vectors;

repeating the selecting, determining and performing steps for multiple pairs of first and second images in the sequence of images to provide the output sequence of images; and

adjusting the duration of the associated audio to retain synchronization with the output sequence of images.

20. The computer program product of claim 19, further comprising:

playing back the output sequence of images with the audio.

21. The computer program product of claim 19, wherein adjusting comprises resampling of the audio.

22. The computer program product of claim 19, wherein adjusting comprises time scaling of the audio.