Methods for selecting a subsequence of video frames from a sequence of video frames

• US 20050198575A1
• Filed: 10/13/2004
• Published: 09/08/2005
• Est. Priority Date: 04/15/2002
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Liu, Tiecheng, Kender, John R.
• Granted Patent: US 7,643,597 B2
• Time in Patent Office: Days
• US Class Current: 715/723
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames

Abstract

A method for selecting a subsequence of video frames (72-84) from a sequence of video frames (70) comprising defining a distance function between video frames (72-84) in the sequence of video frames (70). An optimization criterion is defined to express a feature of a plurality of subsequences of video frames (72-84) selected from the sequence of video frames (70). A method is disclosed for displaying key frames for browsing and streaming.

Claims

1. A method for selecting a subsequence of video frames from a sequence of video frames, comprising the steps of:

(a) defining a distance function between video frames in the sequence of video frames;

(b) defining an optimization criterion to express a feature of a plurality of subsequences of video frames selected from said sequence of video frames;

(c) for a predetermined number of iterations;

(i) defining a first subsequence of video frames and a second subsequence of video frames selected from said sequence of video frames;

(ii) for each video frame in said second subsequence of video frames, determining a respective optimal value of the optimization criterion as determined between said video frame and each prior video frame in said first subsequence and storing information relating to the video frames associated with said optimal value;

(d) determining an overall optimal value among the optimal values of the optimization criterion determined in step (c);

(e) retrieving the video frames stored in step (c) and associated with the overall optimal values of the optimization criterion.

2. A method according to claim 1, wherein the step of defining the distance function comprises defining the histogram difference based on the L¹ norm.

3. A method according to claim 1, wherein the step of defining the optimization criterion comprises defining the sum of all distances of adjacent frames in a subsequence.

4. A method according to claim 3, wherein the optimal value of the optimization criterion is a maximum value of the optimization criterion.

5. A method according to claim 1, wherein the step of defining a first subsequence of video frames and a second subsequence of video frames comprises defining said first subsequence and second subsequence based on the number of frames in the video sequence and the predefined number of iterations.

6. A method according to claim 1, wherein the step of defining a first subsequence of video frames and a second subsequence of video frames comprises, defining said first subsequence of video frames as said second subsequence of video frames defined in a previous iteration of step (c).

7. A method according to claim 1, wherein the step of determining a respective optimal value of the optimization criterion as determined between said video frame and each prior video frame in said first subsequence comprises determining a maximum value of a sum of a difference between said video frame and a prior video frame in the first subsequence and an optimal value of the optimization criterion for a previous iteration of step (c).

8. A method according to claim 1, wherein the step of determining a respective optimal value of the optimization criterion as determined between said video frame and each prior video frame in said first subsequence comprising storing information relating a subsequence of video frames associated with said optimal value in which the last video frame in said subsequence is said video frame.

9. A method according to claim 1, wherein the predetermined number of iterations in step (c) is a selected number of key frames.

10. A method according to claim I wherein each video frame selected in steps (a)-(e) is associated with a display time in which display of each said video frame begins, further comprising the step of determining said display time such that an error function is minimized.

11. A method according to claim 10, wherein said error function is a distance function measured between said video frames.

12. A method for selecting a first subsequence of video frames selected from a sequence of video frames, comprising the steps of:

(a) defining a distance function between video frames in the sequence of video frames;

(b) defining an optimization criterion to express a feature of subsequences of video frames selected from said sequence of video frames;

(c) determining values of the optimization criterion for each frame in the sequence of video frames and organizing said video frames according to said values of the optimization criterion;

(d) discarding a frame associated with an optimal value of the optimization criterion and reorganizing the video frames remaining after said discarding;

(e) determining values of the optimization criterion for video frames affected by the step of discarding and reorganizing the video frames; and

(f) for a predetermined number of iterations, repeating steps (d) and (e).

13. A method according to claim 12, wherein the step of defining a distance function comprises defining the histogram difference based on the L¹ norm.

14. A method according to claim 13, wherein the step of defining the optimization criterion comprises defining the sum of all distances of adjacent frames in a subsequence

15. A method according to claim 12, wherein the method comprises the step of creating a reconstructed sequence of video frames based on a subsequence of video frames, and wherein the optimization criterion corresponds to the difference between corresponding frames of the sequence of video frames and the reconstructed sequence of video frames.

16. A method according to claim 15, wherein the step of defining the optimization criterion function comprises defining the root mean square error of all distances of corresponding frames from said sequence of video frames and said sequence of reconstructed video frames.

17. A method according to claim 12, wherein the step of defining an optimization criterion for each frame in the sequence of video frames further comprises defining a compensation value which represents a differential change of the value of the optimization criterion if the frame is discarded.

18. A method according to claim 12, wherein the step of organizing said video frames according to said values of the optimization criterion comprises organizing said video frames in a binary tree structure.

19. A method according to claim 18, further comprising organizing said video frames such that nodes of the binary tree structure correspond to said video frames.

20. A method according to claim 19, wherein said binary tree structure is a binary heap.

21. A method according to claim 20, wherein a node corresponding to a video frame having the lowest value of the optimization criterion is located at the root node of the binary tree structure.

22. A method according to claim 21, wherein the step of discarding a frame associated with an optimal value of the optimization criterion comprises discarding the video frame having the lowest value of the optimization criterion.

23. A method according to claim 22, wherein the step of reorganizing the video frames remaining after said discarding comprises reorganizing said remaining video frames into a binary heap.

24. A method according to claim 23, wherein the step of determining values of the optimization criterion affected by the step of discarding comprises recalculating the optimization criterion for video frames adjacent to said discarded frame.

25. A method according to claim 24, wherein the step of determining values of the optimization criterion affected by the step of discarding further comprises reorganizing said video frames in a binary heap.

26. A method according to claim 12, wherein the step of discarding a frame associated with an optimal value of the optimization criterion further comprises storing information associated with said discarded frame.

27. A method according to claim 26, further comprising displaying said video frames remaining after said step of discarding.

28. A method according to claim 27, further comprising providing the option of displaying video frames discarded in said step of discarding which are temporally located between a pair of selected frames.

29. A method according to claim 12, wherein step (f) further comprises repeating steps (d) and (e) until a predetermined number of video frames are remaining to form a second subsequence of video frames, the method further comprising the steps of:

(g) defining a second optimization criterion to express a feature of a plurality of subsequences of video frames selected from said second subsequence of video frames;

(h) for a predetermined number of iterations;

(i) defining a third subsequence of video frames and a fourth subsequence of video frames selected from said second subsequence of video frames;

(ii) for each video frame in said fourth subsequence of video frames, determining a respective optimal value of the second optimization criterion as determined between said video frame and each prior video frame in said third subsequence and storing information relating to the video frames associated with said optimal value;

j) determining an overall optimal value among the optimal values of the second optimization criterion determined in step (h);

(k) retrieving the video frames stored in step (k) and associated with the overall optimal values of the second optimization criterion.

30. A method according to claim 29, wherein the step of defining the distance function comprises defining the histogram difference based on the L¹ norm.

31. A method according to claim 29, wherein the step of defining the optimization criterion comprises defining the sum of all distances of adjacent frames in a subsequence.