System and method for selecting key-frames of video data

• US 6,549,643 B1
• Filed: 11/30/1999
• Issued: 04/15/2003
• Est. Priority Date: 11/30/1999
• Status: Expired due to Term

• Current Assignee: Siemens AG
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Toklu, Candemir, Liou, Shih-Ping
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Lu, Tom Y.
• Application Number:
  US09/449,889
• Time in Patent Office: 1,232 Days
• Field of Search: 382/171, 382/173, 345/723, 348/700, 348/422, 348/207, 348/231, 348/571, 364/419.08, 358/906, 358/909.1
• US Class Current: 382/107
• 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: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G06T 7/207 for motion estimation over a hierarchy of resolutions multi-resolution motion estimation or hierarchical motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/53
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: G06V 20/47 Detecting features for summarising video content
• CPC Class Codes: G11B 27/102 Programmed access in sequence to addressed parts of tracks of operating record carriers access by moving the head G11B3/08, G11B5/54, G11B7/085, G11B21/022; by moving the record carrier G11B15/005, G11B17/005, by driving of both record carrier and head G11B15/1816
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: Y10S 358/906 Hand-held camera with recorder in a single unit

Abstract

A system and method for selecting key-frames to generate a content-based visual summary of video and facilitate digital video browsing and indexing, which provides a real-time approach for key-frame selection irrespective of the available computation power. A method for selecting key-frames according to one aspect of the present invention is based on quantifiable measures such as the amount of motion and behavior of curves defined statistically or non-statistically, i.e. by finding the monotonically increasing segments of a curve, instead of thresholding the statistically defined image dissimilarity measures. In one aspect of the present invention, a method for selecting key-frames from video data comprises the steps of: partitioning video data into segments; generating a temporal activity curve for dissimilarity measures based on one of frame differences, color histograms, camera motion, and a combination thereof, for each segment; and sampling the temporal activity curve to select at least one key-frame for each segment.

Claims

1. A method for selecting key-frames from video data, comprising the steps of:

partitioning video data into segments;

generating a temporal activity curve for dissimilarity measures based on one of frame differences, color histograms, camera motion, and a combination thereof, for each segment, wherein the step of generating a temporal activity curve for dissimilarity measures based on frame differences comprises the steps of computing an average of an absolute pixel-based intensity difference between consecutive frames in a given segment, and computing a cumulative sum of the average of the absolute pixel-based intensity differences for the frames of the given segment; and

sampling the temporal activity curve to select at least one key-frame for each segment, wherein the step of sampling the temporal activity curve comprises the steps of selecting a first frame in the given segment as a key-frame, if the cumulative sum of the average of the absolute pixel-based intensity differences for the frames of the given segment does not exceed a first predefined threshold, and selecting a predefined number of key-frames in the given segment uniformly, if the cumulative sum of the average of the absolute pixel-based intensity differences for the frames of the given segment exceeds the first predefined threshold.

2. The method of claim 1, wherein the segments are video shots.

10. The method of claim 1, further comprising the step of eliminating selected key-frames in each segment that are visually similar.

11. The method of claim 10 wherein the step of eliminating key-frames is based on one a comparison between histograms of the selected key-frames, a comparison of the spatial layout of the selected key-frames and a combination thereof.

3. A method for selecting key-frames from video data, comprising the steps of:

partitioning video data into segments;

generating a temporal activity curve for dissimilarity measures based on one of frame differences, color histograms, camera motion, and a combination thereof, for each segment; and

sampling the temporal activity curve to select at least one key-frame for each segment, wherein the step of generating a temporal activity curve for dissimilarity measures based on camera motion comprises the steps of;

estimating camera motion between consecutive frames in a given segment;

computing a motion activity curve based on the estimated camera motion for the given segment; and

computing a binary motion activity curve by comparing the motion activity curve to a second predefined threshold on a frame-by-frame basis.

4. The method of claim 3, wherein the step of estimating camera motion comprises the step of estimating motion parameters comprising one of zooming, rotational, panning, tilting in a two-dimensional image plane, and a combination thereof.

5. The method of claim 3, wherein the step of sampling the temporal activity curve to select at least one key-frame comprises the steps of:

smoothing the binary motion activity curve to detect motion activity segments within the given segment;

selecting a first and last a frame of each detected motion activity segment as a key-frame;

cumulatively summing the estimated camera motion of each frame in each detected motion activity segment; and

selecting at least one additional frame in each detected motion activity segment as a key-frame if the cumulative sum of the estimated camera motion for a motion activity segment exceeds a third predefined threshold.

6. The method of claim 5, further comprising the step of selecting a first frame of a given segment, if there are no detected motion activity segments for the given segment.

7. A method for selecting key-frames from video data, comprising the steps of:

partitioning video data into segments;

generating a temporal activity curve for dissimilarity measures based on one of frame differences, color histograms, camera motion, and a combination thereof, for each segment; and

sampling the temporal activity curve to select at least one key-frame for each segment, wherein the step of generating a temporal activity curve for dissimilarity measures based on color histograms comprises the steps of;

computing a color histogram of each frame of a given segment;

computing a moving average histogram of the given segment using the computed color histograms for each frame;

generating a color histogram activity curve by computing a distance between the color histogram of each frame and the moving average histogram; and

computing a binary color histogram activity curve by comparing a change in value of the color histogram activity curve between each consecutive frame of the given segment to a fourth predefined threshold value.

8. The method of claim 7, wherein the step of sampling the temporal activity curve to select key-frames comprises the steps of:

smoothing the binary color histogram activity curve to detect color histogram activity segments; and

selecting at least one representative frame of each detected color histogram activity segment as a key-frame for the given segment.

9. The method of claim 8, further comprising the step of selecting a first frame of a given segment, if there are no detected color histogram activity segments for the given segment.

12. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for selecting key-frames from video data, the method steps comprising:

partitioning video data into segments;

generating a temporal activity curve for dissimilarity measures based on one of frame differences, color histograms, camera motion, and a combination thereof, for each segment, wherein the step of generating a temporal activity curve for dissimilarity measures based on frame differences comprises computing an average of an absolute pixel-based intensity difference between consecutive frames in a given segment, and computing a cumulative sum of the average of the absolute pixel-based intensity differences for the frames of the given segment; and

sampling the temporal activity curve to select at least one key-frame for each segment, wherein the step of sampling the temporal activity curve comprises selecting a first frame in the given segment as a key-frame, if the cumulative sum of the average of the absolute pixel-based intensity differences for the frames of the given segment does not exceed a first predefined threshold, and selecting a predefined number of key-frames in the given segment uniformly, if the cumulative sum of the average of the absolute pixel-based intensity differences for the frames of the given segment exceeds the first predefined threshold.

13. The program storage device of claim 12, wherein the segments are video shots.

21. The program storage device of claim 12, further comprising instructions for performing the step of eliminating selected key-frames in each segment that are visually similar.

22. The program storage device of claim 21, wherein the instructions for performing the step of eliminating key-frames comprise instructions for one of comparing histograms of the selected key-frames, comparing spatial layouts of the selected key-frames, and a combination thereof, to eliminate similar selected key-frames.

14. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for selecting key-frames from video data, the method steps comprising:

partitioning video data into segments;

generating a temporal activity curve for dissimilarity measures based on one of frame differences, color histograms, camera motion, and a combination thereof, for each segment; and

sampling the temporal activity curve to select at least one key-frame for each segment,

wherein the instructions for performing the step of generating a temporal activity curve for dissimilarity measures based on camera motion comprise instructions for performing the steps of;

estimating camera motion between consecutive frames in a given segment;

computing a motion activity curve based on the estimated camera motion for the given segment; and

computing a binary motion activity curve by comparing the motion activity curve to a second predefined threshold on a frame-by-frame basis.

15. The program storage device of claim 14, wherein the instructions for performing the step of estimating camera motion comprise instructions for performing the step of estimating motion parameters comprising one of zooming, rotational, panning, tilting in a two-dimensional image plane, and a combination thereof.

16. The program storage device of claim 14, wherein the instructions for performing the step of sampling the temporal activity curve to select at least one key-frame comprise instructions for performing the steps of:

smoothing the binary motion activity curve to detect motion activity segments within the given segment;

selecting a first and last a frame of each detected motion activity segment as a key-frame;

cumulatively summing the estimated camera motion of each frame in each detected motion activity segment; and

selecting at least one additional frame in each detected motion activity segment as a key-frame if the cumulative sum of the estimated camera motion exceeds a third predefined threshold.

17. The program storage device of claim 16, further comprising instructions for performing the step of selecting a first frame of a given segment, if there are no detected motion activity segments for the given segment.

18. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for selecting key-frames from video data, the method steps comprising:

partitioning video data into segments;

generating a temporal activity curve for dissimilarity measures based on one of frame differences, color histograms, camera motion, and a combination thereof, for each segment; and

sampling the temporal activity curve to select at least one key-frame for each segment,

wherein the instructions for performing the step of generating a temporal activity curve for dissimilarity measures based on color histograms comprise instructions for performing the steps of;

computing a color histogram of each frame of a given segment;

computing a moving average histogram of the given segment using the computed color histograms for each frame;

generating a color histogram activity curve by computing a distance between the color histogram of each frame and the moving average histogram; and

computing a binary color histogram activity curve by comparing a change in value of the color histogram activity curve between each consecutive frame of the given segment to a fourth predefined threshold value.

19. The program storage device of claim 18, wherein the instructions for performing the step of sampling the temporal activity curve to select key-frames comprise instructions for performing the steps of:

smoothing the binary color histogram activity curve to detect color histogram activity segments; and

selecting at least one representative frame of each detected color histogram activity segment as a key-frame for the given segment.

20. The program storage device of claim 19, further comprising instructions for performing the step of selecting a first frame of a given segment, if there are no detected color histogram activity segments for the given segment.