Digital video segmentation and dynamic segment labeling

• US 7,242,809 B2
• Filed: 06/25/2003
• Issued: 07/10/2007
• Est. Priority Date: 06/25/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mercer, Ian Cameron, Ahlstrom, Bret, Hunter, Kurt M.
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US10/603,565
• Publication Number:
  US 20050111824A1
• Time in Patent Office: 1,476 Days
• Field of Search: 382/225, 382/165, 382/173, 382/243, 382/170, 382/168, 382/305, 382/236, 382/226, 382/171, 382/224, 375/240.16, 375/240.26, 375/240.15, 375/240.01, 348/700, 348/397.1, 704/245, 702/76, 702/16, 715/723, 715/720, 360/48, 386/52, 386/48, 386/98
• US Class Current: 382/224
• 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; and

wherein the segmenting instructions include instructions for;

comparing the determined time gaps between successive video shots in the organized sequence;

grouping two successive video shots into one of the clusters when their corresponding determined time gap indicates they are substantially close in time; and

determining a time span of each of the first plurality of clusters, said time span corresponding 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.

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 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.

6. The computer-readable medium of claim 5, 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.

7. The computer-readable medium of claim 6, 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.

8. The computer-readable medium of claim 7, 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.

9. The computer-readable medium of claim 8, 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.

10. The computer readable medium of claim 9, 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.

11. The computer-readable medium of claim 8, 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.

12. 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; and

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.

13. The computer-readable medium of claim 12, wherein the storage instructions include instructions for assigning the determined label as a name of a file to be stored on the computer-readable medium.

14. The computer-readable medium of claim 12, 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 storage identifying instructions include instructions for determining the time corresponding to each video shot from the video frame data.

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

16. A method for segmenting a plurality of video shots 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.

17. The method of claim 16, 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.

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

19. The method of claim 16, 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.

20. The method of the claim 16, 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.

21. The method of the claim 20, 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.

22. The method of claim 20, 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.

23. The method of the claim 16 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.

24. The method of the claim 16 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.

25. 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; and

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.

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

27. The computer-readable medium of claim 25, wherein the storage instructions include instructions for assigning the determined label as a name of a file to be stored on the computer-readable medium.

28. The computer-readable medium of claim 25, 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 storage identifying instructions include instructions for determining the time corresponding to each video shot from the video frame data.

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

30. The computer-readable medium of claim 29, wherein the storage identifying instructions include instructions for 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.

31. 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; and

wherein storage instructions includes chapter storage instructions for storing the group of video shots on a removable computer-readable medium.

32. The computer-readable medium of claim 31, wherein the storage instructions include instructions for assigning the determined label as a name of a file to be stored on the computer-readable medium.

33. The computer-readable medium of claim 31, 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 storage identifying instructions include instructions for determining the time corresponding to each video shot from the video frame data.

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

35. The computer-readable medium of claim 34, wherein the storage identifying instructions include instructions for 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.

36. The computer-readable medium of claim 31, 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.