System for interactive organization and browsing of video

• US 6,278,446 B1
• Filed: 02/23/1998
• Issued: 08/21/2001
• Est. Priority Date: 02/23/1998
• Status: Expired due to Term

• Current Assignee: Siemens AG
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Liou, Shih-Ping, Das, Madirakshi
• Primary Examiner(s): Bayerl, Raymond J.
• Assistant Examiner(s): Luu, Sy D.
• Application Number:
  US09/027,637
• Time in Patent Office: 1,275 Days
• Field of Search: 345/328, 345/327, 345/348, 345/349, 345/356, 345/431, 386/4, 386/52, 348/700-703, 382/168, 382/206
• US Class Current: 715/700
• CPC Class Codes: G06F 16/745 the internal structure of a single video sequence
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/7854 using shape G06F16/7837 takes precedence
• 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

Abstract

A system for interactively organizing and browsing video automatically processes video, creating a video table of contents (VTOC), while providing easy-to-use interfaces for verification, correction, and augmentation of the automatically extracted video structure. Shot detection, shot grouping and VTOC generation are automatically determined without making restrictive assumptions about the structure or content of the video. A nonstationary time series model of difference metrics is used for shot boundary detention. Color and edge similarities are used for shot grouping. Observation about the structure of a wide class of videos are used for the generating the table of contents. The use of automatic processing in conjuction with input from the user provides a meaningful video organization.

Claims

1. A system for interactively organizing and browsing raw video to facilitate browsing of video archives, comprising:

automatic video organizing means for automatically organizing a raw video into a hierarchical structure that depicts the video'"'"'s organized contents, said automatic video organizing means including shot grouping means for automatically grouping shots, which represent a continuous action in time and space, into groups of visually similar shots, each group of shots capturing a given structure in the raw video; and

user interface means for allowing a user to view and manually edit the hierarchical structure, said user interface means including tree view interface means for allowing the user to view the groups of visually similar shots, create new groups of visually similar shots, and modify the groups of visually similar shots, said tree view interface means including update means for determining whether any image portions of a shot merged with another shot by the user are similar, wherein when said update means finds similar image portions, said update means generates partial match templates which blocks dissimilar image portions of remaining shots and automatically merges the remaining shots that have similar image portions, wherein when said update means does not find any similar image portions, said update means determines whether audio streams of the two merged shots are similar, wherein when said update means finds similar audio streams, said update means searches other shots in the groups for similar audio streams and automatically merges other shots with similar audio streams together, wherein when said update means does not find any similar audio streams in the two merged shots, the update means repeats the user'"'"'s action on all siblings of the merged shot.

2. The system according to claim 1, wherein the automatic organizing means includes shot detecting means for automatically detecting abrupt scene changes in raw frames of the video and automatically organizing the raw frames into a list of shots, each of the shots representing a continuous action in time and space.

3. The system according to claim 1, wherein the user interface means includes browser interface means for allowing the user to view the shots, add new shots to the list of shots, and merge the shots into a single shot.

4. The system according to claim 1, wherein the automatic organizing means includes hierarchical structure generating means for creating the hierarchical structure from groups of visually similar shots, each of the shots representing a continuous action in time and space.

5. The system according to claim 4, wherein the user interface means includes tree view interface means for allowing the user to view and modify the hierarchical structure to make the hierarchical structure substantially useful and meaningful to the user.

6. The system according to claim 1, wherein the user interface means includes video player means for allowing the user to play the video along with the video'"'"'s audio from any point in the video.

7. A method used in automatically organizing video for automatically grouping shots into groups of visually similar shots, each group of shots capturing structure in a raw video, the shots generated by detecting abrupt scene changes in raw frames of the video which represent a continuous action in time and space, the method comprising the steps of:

providing a predetermined list of color names;

describing image colors in each of the shots using the predetermined list of color names;

clustering the shots into visually similar groups based on the image colors described in each of the shots; and

using image edge information from each of the shots to identify and remove incorrectly clustered shots from the groups.

8. The method according to claim 7, wherein the list of color names includes a plurality of hue names.

9. The method according to claim 7, wherein the step of describing includes the step of obtaining a color histogram for each shot based on the predetermined list of color names.

10. The method according to claim 9, wherein the step of describing further includes the step of normalizing bin counts of the color histograms to provide a feature vector which describes the image colors of the shots.

11. The method according to claim 7, wherein the step of clustering includes the steps of:

providing a single one of the groups containing a first shot;

getting a color feature vector of a new shot, the color feature vector based on the predetermined list of color names;

finding a nearest match between the vector and group means of existing groups; and

determining if the nearest match is less than a predetermined color threshold.

12. The method according to claim 11, wherein the step of clustering further includes the steps of:

adding the new shot to a group producing the nearest match if the nearest match is less than the color threshold; and

updating means of the group producing the nearest match.

13. The method according to claim 11, wherein the step of clustering further includes the steps of

creating a new group with the color feature vector as its mean if the nearest match is not less than the predetermined color threshold;

and

adding the shot to the new group.

14. The method according to claim 7, wherein the step of using image edge information includes the steps of:

computing edge feature vectors E for each shot of groups having more than one shot; and

computing mean edge feature vector M for each group having more than one shot.

15. The method according to claim 14, wherein the step of using image edge information further includes the steps of:

finding a shot of a group which gives a maximum absolute value for (M−

E); and

determining if the maximum absolute value for (M−

E) is greater than a predetermined edge threshold.

16. The method according to claim 15, wherein the step of using image edge information further includes the steps of:

deleting the shot of the group if the maximum absolute value for (M−

E) is greater than the predetermined threshold and place the shot in a new group; and

recomputing the mean edge feature vector of the group with the removed shot.

17. The method according to claim 16, further comprising the step of writing a merge-list which specifies a group number for each of the shots.

18. A method for interactively organizing and browsing video, the method comprising the steps of:

automatically organizing a raw video into a hierarchical structure that depicts the video'"'"'s organized contents, said step of automatically organizing including the steps of;

automatically detecting abrupt scene changes in raw frames of the video,

automatically organizing the raw frames into a list of shots, each of the shots representing a continuous action in time and space, and

automatically grouping shots, which represent a continuous action in time and space, into groups of visually similar shots, each group of shots capturing a given structure in the raw video; and

viewing and manually editing the hierarchical structure to make the hierarchical structure substantially useful and meaningful to the user, said step of viewing including the steps of;

viewing the shots,

manually editing the shots,

viewing the groups of visually similar shots, and

manually editing the groups of shots; and

wherein the step of manually editing the groups of shots includes the step of determining whether any image portions of a first shot merged with a second shot by the user are similar, wherein when similar image portions are found, partial match templates are generated which block dissimilar image portions of remaining shots and automatically merges the remaining shots having image portions which are similar to the similar image portions of the merged first and second shots, wherein when similar image portions in the merged first and second shots are not found, determining whether audio streams of the merged first and second shots are similar, wherein when similar audio streams are found in the merged first and second shots, searching audio streams of the remaining shots to determine if they are are similar to the audio streams of the merged first and second shots and automatically merging the remaining shots, having audio streams that are similar to the audio streams of the merged first and second shots, with the merged first and second shots, wherein when similar audio streams are not found in the merged first and second shots, the action taken by the user on the first shot is automatically repeated on all siblings of the first shot.

19. The method according to claim 18, wherein the step of automatically organizing includes the step of generating the hierarchical structure from groups of visually similar shots, each of the shots representing a continuous action in time and space.

20. The method according to claim 19, wherein the step of viewing includes the steps of:

viewing the hierarchical structure; and

modifying the hierarchical structure to make the hierarchical structure substantially useful and meaningful to the user.

21. The method according to claim 18, wherein the step of viewing includes the step of playing the video along with the video'"'"'s audio from any point in the video.