Patent US6549643B1 successfully refreshed from Google Patents.
US6549643B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for selecting key-frames of video data
Assignee: Siemens AG
•
Filing: 1999-11-30
•
Granted: 2003-04-15
•
Expires: 2019-11-30
Abstract
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.
Inventors
- 👤 Candemir Toklu
- 👤 Shih-Ping Liou
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:53
CPC Classifications
G; G11; G11B; G11B27/00; G11B27/10; G11B27/19; G11B27/28; G06; G06F; G06F16/00; G06F16/70; G06F16/73; G06F16/738; G06F16/739; G06F16/78; G06F16/783; G06F16/7847; G06F16/785; G06F16/786; G06T; G06T7/00; G06T7/20; G06T7/207; G06T7/277; G06V; G06V20/00; G06V20/40; G06V20/46; G06V20/47; G11B27/102; Y; Y10; Y10S; Y10S358/00; Y10S358/906
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
202 words
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.
Claim 2
Independent Claim
202 words
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.
Claim 3
Dependent Claim
12 words
The method of claim 1 , wherein the segments are video shots.
Claim 4
Independent Claim
124 words
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.
Claim 5
Independent Claim
124 words
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.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Dependent Claim
106 words
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.
Claim 8
Dependent Claim
31 words
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.
Claim 9
Independent Claim
161 words
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.
Claim 10
Independent Claim
161 words
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.
Claim 11
Dependent Claim
56 words
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.
Claim 12
Dependent Claim
32 words
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.
Claim 13
Dependent Claim
21 words
The method of claim 1 , further comprising the step of eliminating selected key-frames in each segment that are visually similar.
Claim 14
Dependent Claim
37 words
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.
Claim 15
Dependent Claim
216 words
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.
Claim 16
Dependent Claim
216 words
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.
Claim 17
Dependent Claim
14 words
The program storage device of claim 12 , wherein the segments are video shots.
Claim 18
Dependent Claim
151 words
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.
Claim 19
Dependent Claim
151 words
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.
Claim 20
Dependent Claim
45 words
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.
Claim 21
Dependent Claim
110 words
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.
Claim 22
Dependent Claim
36 words
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.
Claim 23
Dependent Claim
188 words
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.
Claim 24
Dependent Claim
188 words
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.
Claim 25
Dependent Claim
65 words
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.
Claim 26
Dependent Claim
37 words
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.
Claim 27
Dependent Claim
26 words
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.
Claim 28
Dependent Claim
45 words
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.
References Cited (Backward Citations)
US5805746A
Cited
US5635982A
Cited
US5915250A
Cited
US5969772A
Cited
US5956026A
Cited
US6393054B1
Cited
US6389168B2
Cited
US6381363B1
Cited
US6331859B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-04-14 | 2006-10-14 | 2007-04-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-04-14 | 2010-10-14 | 2011-04-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-04-14 | 2014-10-14 | 2015-04-15 | $7700.00 | Window Closed / Lapsed |