Spatial and temporal alignment of video sequences

• US 7,912,337 B2
• Filed: 11/02/2005
• Issued: 03/22/2011
• Est. Priority Date: 11/02/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Souchard, Christophe
• Primary Examiner(s): Tran; Thai
• Assistant Examiner(s): Chowdhury; Nigar
• Application Number:
  US11/266,101
• Publication Number:
  US 20070097266A1
• Time in Patent Office: 1,966 Days
• Field of Search: 386/1, 386 45- 46, 386/52, 386125-126
• US Class Current: 386/278
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20208 High dynamic range [HDR] image processing
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: H04N 5/265 Mixing

Abstract

Some embodiments allow a video editor to spatially and temporally align two or more video sequences into a single video sequence. As used in this application, a video sequence is a set of images (e.g., a set of video frames or fields). A video sequence can be from any media, such as broadcast media or recording media (e.g., camera, film, DVD, etc.). Some embodiments are implemented in a video editing application that has a user selectable alignment operation, which when selected aligns two or more video sequences. In some embodiments, the alignment operation identifies a set of pixels in one image (i.e., a “first” image) of a first video sequence and another image (i.e., a “second” image) of a second video sequence. The alignment operation defines a motion function that describes the motion of the set of pixels between the first and second images. The operation then defines an objective function based on the motion function. The operation finds an optimal solution for the objective function. Based on the objective function, the operation identifies a transform, which it then applies to the first image in order to align the first image with the second image.

Claims

1. A non-transitory computer readable medium comprising a video editing program for editing a set of video images comprising first and second sequences of video images, the video editing program for execution by a processor, the program comprising sets of instructions for:

comparing a first video image in the first sequence of video images with each of a plurality of video images in the second sequence of video images to identify a second video image in the second sequence of video images that matches the first video image;

using the first and second video images to associate each of a plurality of video images in the first video sequence to a different video image in the second video sequence;

defining a set of transform operations based on a difference between video images in one or more pairs of associated video images; and

aligning the first and second sequences of video images by applying the set of transform operations to one of the images in each pair of video images to align each pair of associated images to produce a panoramic sequence of video images.

2. The non-transitory computer readable medium of claim 1, wherein the set of instructions for defining the set of transform operations comprises sets of instructions for:

defining a set of motion functions, each motion function for expressing a motion between the video images in each pair of associated video images;

defining a set of objective functions based on the set of motion functions;

optimizing the set of objective functions to compute a set of optimal motion functions; and

defining the set of transform operations based on the set of optimal motion functions.

3. The non-transitory computer readable medium of claim 2, wherein each objective function in the set of objective functions expresses a difference between two frames in a pair of associated video images.

4. The non-transitory computer readable medium of claim 2, wherein the set of instructions for optimizing the set of objective functions comprises a set of instructions for minimizing the set of objective functions based on a set of constraints.

5. The non-transitory computer readable medium of claim 1, wherein each video image comprises a plurality of pixels, wherein the set of instructions for comparing the first video image with each of the plurality of video images in the second sequence comprises sets of instructions for:

selecting a set of pixels in the first video image and a set of pixels in each of the plurality of video images in the second sequence; and

comparing the selected set of pixels in the first video image with the selected set of pixels in each of the plurality of video images in the second sequence.

6. The non-transitory computer readable medium of claim 5, wherein the set of instructions for selecting the set of pixels comprises a set of instructions for selecting the set of pixels that include a spatial frequency above a particular value.

7. The non-transitory computer readable medium of claim 1,

wherein each video image in the first sequence of video images has a position in the first sequence, the position in the first sequence expressing a sequential order of the video image in the first sequence of video images,

wherein each video image in the second sequence of video images has a position in the second sequence, the position in the second sequence expressing a sequential order of the video image in the second sequence of video images,

wherein the position of the first video image in the first sequence is different than the position of the second video image in the second sequence.

8. The non-transitory computer readable medium of claim 7, wherein the position of the second image in the first second sequence is before the position of the first image in the first sequence.

9. The non-transitory computer readable medium of claim 7, wherein the position of the second image in the second sequence is after the position of the first image in the first sequence.

10. The non-transitory computer readable medium of claim 1, wherein the program further comprises a set of instructions for specifying a mask before applying the set of transform operations.

11. The non-transitory computer readable medium of claim 10, wherein each image comprises a set of pixels, wherein the mask excludes a plurality of pixels from being transformed when applying the set of transform operations to one of the images in each pair of associated video images.

12. The non-transitory computer readable medium of claim 1, wherein the set of instructions for comparing comprises a set of instructions for comparing each of a plurality of video images in the first sequence with each of the plurality of video images in the second sequence, wherein the first and second video images are images that match as good as any video image in the plurality of images in the first sequence and the plurality of images in the second sequence.

13. The non-transitory computer readable medium of claim 1, wherein the set of instructions for comparing comprises a set of instructions for comparing a portion of the first video image with a portion of each of the plurality of video images in the second sequence.

14. The non-transitory computer readable medium of claim 1, wherein the set of instructions for aligning comprises a set of instructions for applying a transform operation to each image in the first sequence of video images.

15. The non-transitory computer readable medium of claim 1, wherein the set of instructions for aligning comprises a set of instructions for applying a transform operation to each image in the second sequence of video images.

16. The non-transitory computer readable medium of claim 1, wherein the set of instructions for using the first and second video images comprises a set of instructions for sequentially selecting each image in the first and second sequences after the first and second images, each pair of video images comprising one sequentially selected image from each of the first and second sequences.

17. The non-transitory computer readable medium of claim 1, wherein the set of transform operations comprises only one transform operation that is based on a difference between the first video image and the second video image, wherein the set of instructions for aligning comprises a set of instructions for applying said one transform operation to one of the images in each pair of associated video images.

18. The non-transitory computer readable medium of claim 1, wherein the set of transform operations comprises a plurality of transform operations, wherein each transform operation is based on a difference between the video images in a corresponding pair of video images, wherein the set of instructions for aligning comprises a set of instructions for applying each transform operation to one of the images in the corresponding pair of associated video images.

19. The non-transitory computer readable medium of claim 1, wherein the set of instructions for comparing the first video image with each of the plurality of video images to identify the second video image comprises sets of instructions for:

defining a plurality of motion functions, each motion function for expressing a motion between the first video image and one of the images in the plurality of video images in the second sequence;

defining a plurality of objective functions based on the plurality of motion functions;

optimizing the plurality of objective functions to compute a plurality of optimal motion functions;

defining a transform operation between the first video image and each of the images in the plurality of video images in the second sequence based on the plurality of optimal motion functions;

aligning the first video image with each of the plurality of video images in the second sequence; and

identifying the second video image as a video image that aligns to the first video image better than any other image in the plurality of video images.

20. The non-transitory computer readable medium of claim 19, wherein each objective function in the plurality of objective functions expresses a difference between the first video image and a video image in the plurality of video images in the second sequence.

21. The non-transitory computer readable medium of claim 1, wherein the second image is an image that matches the first video image as good as any other image in the plurality of images.

22. A non-transitory computer readable medium comprising a computer program for creating a panoramic video sequence from first and second video sequences, the computer program comprising sets of instructions for:

comparing a first video frame in the first video sequence with each of a plurality of video frames in the second video sequence to identify a second video frame in the second video sequence that matches the first video frame;

using the first and second video frames to associate each of a plurality of video frames in the first video sequence to a different video frame in the second video sequence;

producing a plurality of composite video frames by aligning each pair of associated video frames in the first and second video sequences; and

defining the panoramic video sequence to include the plurality of composite video frames.

23. The non-transitory computer readable medium of claim 22, wherein the set of instructions for producing the plurality of composite video frames comprises sets of instructions for:

defining a set of transform operations based on a difference between video frames in one or more pairs of associated video frames; and

applying the set of transform operations to one of the frames in each pair of associated video frames to align each pair of associated video frames.

24. The non-transitory computer readable medium of claim 23, wherein the set of instructions for defining the set of transform operations comprises sets of instructions for:

defining a set of motion functions, each motion function for expressing a motion between the video frames in each pair of associated video frames;

defining a set of objective functions based on the set of motion functions;

optimizing the set of objective functions to compute a set of optimal motion functions; and

defining the set of transform operations based on the set of optimal motion functions.

25. The non-transitory computer readable medium of claim 24, wherein each objective function in the set of objective functions expresses a difference between two frames in a pair of video frames.

26. A method for creating a panoramic video sequence from first and second video sequences, the method comprising:

comparing a first video frame in the first video sequence with each of a plurality of video frames in the second video sequence to identify a second video frame in the second video sequence that matches the first video frame;

using the first and second video frames to associate each of a plurality of video frames in the first video sequence to a different video frame in the second video sequence;

by a computer, producing a plurality of composite video frames by aligning each pair of associated video frames in the first and second video sequences; and

defining the panoramic video sequence to include the plurality of composite video frames.

27. The method of claim 26, wherein each video frame comprises a plurality of pixels, wherein comparing the first video frame with each of the plurality of video frames in the second sequence comprises:

selecting a set of pixels in the first video frame and a set of pixels in each of the plurality of video frames in the second sequence; and

comparing the selected set of pixels in the first video frame with the selected set of pixels in each of the plurality of video frames in the second sequence.

28. The method of claim 27, wherein producing the plurality of composite video frames comprises:

defining a set of transform operations based on a difference between video frames in one or more pairs of associated video frames; and

applying the set of transform operations to one of the frames in each pair of associated video frames to align each pair of associated video frames.

29. The method of claim 27, wherein each video frame comprises a set of pixels, wherein producing the plurality of composite video frames further comprises specifying a mask before applying the set of transform operations, wherein the mask excludes a plurality of pixels from being transformed when applying the set of transform operations to one of the frames in each pair of video frames.