Digital video segmentation and dynamic segment labeling

• US 20050111824A1
• Filed: 06/25/2003
• Published: 05/26/2005
• Est. Priority Date: 06/25/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mercer, Ian Cameron, Ahlstrom, Bret, Hunter, Kurt M.
• Granted Patent: US 7,242,809 B2
• Time in Patent Office: Days
• US Class Current: 386/240
• 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: G11B 2220/213 Read-only discs
• CPC Class Codes: G11B 2220/2562 DVDs [digital versatile discs]; Digital video discs; MMCDs; HDCDs
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 27/34 Indicating arrangements indicating means incorporated in magazine or cassette G11B23/046 and G11B23/0875; indicating measured values in general G01D
• CPC Class Codes: H04N 5/77 between a recording apparatus and a television camera
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 5/85 on discs or drums

Abstract

A method and system for segmenting video into an optimal set of video clusters that correspond loosely to one or more events, date ranges, time ranges, chapters or other logical segmentations of the digital video that is meaningful to the user. Video shots are selected from one or more video files on a computer-readable medium. The video shots are arranged in chronological order and a distance (e.g., time gap) between each successive pair of the arranged video shots is determined. Video clustering are generated as function of the determined ‘distances’ and/or user input, and an optimal video clustering is identified. After the optimal video clustering is identified, a time span for each of the video clusters is determined and a label is generated for each cluster. The clusters are then displayed for the user to browse using the generated labels and thumbnails derived from the video clips, transferred to a separate medium for display on another computer or other electronic device (e.g. DVD-video player) or made available for the user or other software to manipulate further.

Claims

1. A computer-readable medium having computer executable instructions for segmenting a plurality of video shots within one or more video files, comprising:

determining instructions for determining a time corresponding to each video shot;

organizing instructions for organizing the video shots in a sequence according to the determined time corresponding to each video shot;

determining instructions for determining a time gap between two successive shots in the organized sequence; and

segmenting instructions for grouping the video shots of the video file into a first plurality of clusters as a function of the determined time gaps.

2. The computer-readable medium of claim 1, wherein each video shot includes a video frame having video frame data, wherein the video frame data includes time and date data, and wherein the determining instructions include instructions for determining the time corresponding to each video shot from the video frame data.

3. The computer-readable medium of claim 2, wherein the determined time gap corresponds to a length of time between the determined time of a first video shot and the determined time of a subsequent video shot in the organized sequence.

4. The computer-readable medium of claim 1, wherein the organizing instructions includes instructions for organizing the video shots into a chronological order based on the determined time corresponding to each video shot.

5. The computer-readable medium of claim 1, wherein the segmenting instructions includes instructions for comparing the determined time gaps between successive video shots in the organized sequence, and wherein two successive video shots are grouped into one of the clusters when their corresponding determined time gap indicates they are substantially close in time.

6. The computer-readable medium of claim 6, wherein the segmenting instructions includes instructions for determining a time span of each of the first plurality of clusters, wherein the time span corresponds to a determined time of a first in time video shot within each cluster and the determined time of a last in time video shot within each cluster.

7. The computer-readable medium of claim 6, wherein the segmenting instructions includes instructions for comparing the determined time span of each of the first plurality of clusters to a date boundary (e.g., day, week, month, or year), and wherein the first plurality of clusters is assigned a first quality as a function of the comparison.

8. The computer-readable medium of claim 7, wherein the first plurality of clusters is assigned a favorable quality when the determined time span of each of clusters is less than or equal to the date boundary.

9. The computer-readable medium of claim 8, wherein the segmenting instructions include instructions for biasing the first quality as a function of a number of clusters in the first plurality of clusters, and wherein a favorable bias is applied to the first quality to calculate a first biased quality when the number of clusters in the first plurality of clusters is less than or equal to a predefined cluster count, and wherein a less favorable bias is applied to the second quality to determine the first biased quality when the number of clusters in the second plurality of clusters is greater than the predefined cluster count.

10. The computer-readable medium of claim 9, wherein the segmenting instructions includes instructions for grouping the video shots of the video file into a second plurality of clusters as a function of the determined time gaps, and wherein the segmenting instructions includes instructions for determining a time span of each of the second plurality of clusters, wherein the time span corresponds to a determined time of a first in time video shot within each cluster and the determined time of a last in time video shot within each cluster, and wherein the segmenting instructions includes instructions for comparing the determined time span of each of the second plurality of clusters to a date boundary (e.g., day, week, month, or year), and wherein the second plurality of clusters is assigned a second quality as a function of the comparison.

11. The computer-readable medium of claim 10, wherein the segmenting instructions include instructions for biasing the second quality as a function of a number of clusters in the second plurality of clusters, and wherein the favorable bias is applied to the second quality to determine a second biased quality when the number of clusters in the second plurality of clusters is less than or equal to the predefined cluster count, and wherein the less favorable bias is applied to the second quality to determine the second biased quality when the number of clusters in the second plurality of clusters is greater than the predefined cluster count.

12. The computer-readable medium of claim 10, wherein the segmenting instructions further includes instructions for comparing the first quality and the second quality and grouping the video shots as a function of the comparison.

13. The computer readable medium of claim 11, wherein the segmenting instructions further includes instructions for comparing the first biased quality and the second biased quality and grouping the video shots as a function of the comparison.

14. A computer-readable medium having computer executable instructions for storing a group of video shots, comprising:

storage identifying instructions for identifying a time span corresponding to the group of video shots;

storage labeling instructions for determining a label for the group of video shots corresponding to the identified time span corresponding to the group of video shots; and

storage instructions for storing the group of video shots as a grouped video shot file.

15. The computer-readable medium of claim 14, wherein the time span corresponds to a determined time of a first shot within the group of video shots and the determined time of a last video shot within the group of video shots.

16. The computer-readable medium of claim 14, wherein the label indicates a date boundary, and wherein the time span corresponding to the group of video shots is less than or equal to the date boundary.

17. The computer-readable medium of claim 14, wherein storage instructions includes chapter storage instructions for storing the group of video shots on a removable CRM such as an optical video disc.

18. A computer-readable medium having computer executable instructions for displaying a group of video shots, comprising:

display identifying instructions for identifying a time span corresponding to the group of video shots;

display labeling instruction for determining a label for the group of video shots corresponding to the identified time span corresponding to the group of video shots for, and for displaying the group of video shots and displaying the determined label as a title of the displayed video shots.

19. The computer-readable medium of claim 18, wherein the time span corresponds to a determined time of a first shot within the group of video shots and the determined time of a last video shot within the group of video shots.

20. The computer-readable medium of claim 18, wherein the label indicates a date boundary, and wherein the time span corresponding to the group of video shots is less than or equal to the date boundary.

21. A method for segmenting a plurality of video shots of within a video file for storage on a computer-readable medium:

determining a time corresponding to each video shot;

organizing the video shots in a sequence according to the determined time corresponding to each video shot;

determining time gaps between two successive shots in the organized sequence;

first grouping the video shots into a first plurality of clusters as a function of the determined time gaps;

assigning a first quality to the a first plurality of clusters as a function of a time span of each cluster in the first plurality of clusters;

second grouping the video shots into a second plurality of clusters as a function of the determined time gaps;

assigning a second quality to the second plurality of clusters as a function of a time span of each cluster in the second plurality of clusters;

comparing the first and second quality and selecting the first or second grouping as a function of the comparison; and

storing the selected grouping as a file on the computer-readable medium.

22. The method of claim 21, wherein the determining a time of each video shot includes analyzing video data associated with a video frame to determine a start time of the video shot and end time of the video shot, wherein each video shot includes one or more video frames, and wherein said video data includes time and date data.

23. The method of claim 21, wherein the organizing the video shots includes organizing the video shots in a chronological order.

24. The method of claim 21, wherein the determining a time gap includes determining a time difference between the determined time of a first video shot in the organized sequence and the determined time of a subsequent video shot in the organized sequence.

25. The method of the claim 21, wherein the assigning a first quality to the first plurality of clusters includes comparing the determined time span of each cluster in the first plurality of clusters to a date boundary (e.g., day, week, month, or year) to determine whether the determined time span is less than or equal to the date boundary, and wherein assigning a second quality to the second plurality of clusters includes comparing the determined time span of each cluster in the second plurality of clusters to a date boundary (e.g., day, week, month, or year) to determine whether the determined time span is less than or equal to the date boundary.

26. The method of the claim 25, wherein the comparing the first and second quality includes determining whether the assigned first quality is more favorable than the assigned second quality, or whether the assigned first quality is less favorable than the assigned second quality, wherein the selecting the first or second grouping includes selecting the first plurality of clusters when the assigned first quality is more favorable than the assigned second quality, and wherein the selecting the first or second grouping includes selecting the second plurality of clusters when the assigned first quality is less favorable than the assigned second quality.

27. The method of the claim 21 further including biasing the first quality assigned to the first plurality of clusters as a function of a number of cluster in the first plurality of clusters and biasing the second quality assigned to the second plurality of clusters as a function of a number of cluster in the second plurality of clusters, wherein the biasing the first quality includes determining a first biased quality, and wherein the biasing the second quality includes determining a first biased quality, and wherein the comparing further includes comparing the first biased quality and second biased quality and selecting the first or second grouping as a function of the comparison.

28. The method of claim 25, wherein the determining the first biased quality includes applying a favorable bias to the first quality when the number of clusters in the first plurality of clusters is less than or equal to a predefined cluster count, and applying a less favorable bias to the first quality when the number of clusters in the first plurality of clusters is greater than the predefined cluster count, and wherein the determining the second biased quality includes applying the favorable bias to the second quality when the number of clusters in the second plurality of clusters is less than or equal to a predefined cluster count, and applying the less favorable bias to the first quality when the number of clusters in the second plurality of clusters is greater than the predefined cluster count.

29. The method of the claim 21 further including determining a label for each of the clusters in the selected grouping that identifies the time span corresponding to the group of video shots grouped into each cluster, and assigning the determined label as a name of the file to be stored on the computer-readable medium.

30. A computer-readable medium having stored thereon a data structure, comprising:

a first data field comprising a first file of two or more video shots grouped by time;

a first label identifying the first file;

a second data field comprising a second file of two or more video shots grouped by time; and

a second label identifying the second file.

31. A computer-readable medium having quality instructions for evaluating a potential clustering of clusters, wherein each potential clustering includes two or more clusters, said clusters being separated by a time gap, and wherein each cluster includes one or more video shots, said video shots being separated by a time gap, and said quality instructions comprising assigning each potential clustering a quality value as a function of determined time gaps within clusters and as a function of determined time gaps remaining between clusters within the potential clustering.

32. The computer-readable medium of claim 31 further including selection instructions for examining the quality value associated with each potential clustering to select a best clustering among various potential clusterings.

33. The computer-readable medium of claim 32 further including storage instructions for storing the selected clustering on a computer-readable medium as a file or as a series of files with associated menus and metadata, and wherein the storage instructions create a single file or a series of files that include a sequence of groups of video shots together with metadata about each video shot and a determined label.

35. The computer-readable medium of claim 32 further including storage labeling instructions for assigning the determined label as the name of the created file.

34. A computer-readable medium having labeling instructions for determining a label for each cluster within a potential clustering based on a time span corresponding to video shots within the cluster and based on a time span associated with each of the other clusters within the potential clustering.

36. In a computer system for displaying a potential clustering, said potential clustering including two or more clusters, said system having a user interface including a display and a user interface selection device, a method of manipulating and selecting from a plurality of potential clusterings on the display, comprising

selecting a potential clustering from the plurality of potential clusterings being displayed on the user interface;

and

subdividing the selected clustering into a new potential clustering, or combining a plurality of clusters within the selected clustering to form a new potential clustering.