Method and apparatus for video browsing based on content and structure

• US 5,821,945 A
• Filed: 05/15/1997
• Issued: 10/13/1998
• Est. Priority Date: 02/03/1995
• Status: Expired due to Fees

• Current Assignee: The Trustees of Princeton University (Princeton University)
• Original Assignee: The Trustees of Princeton University (Princeton University)
• Inventors: Yeo, Boon-Lock, Yeung, Minerva M., Wolf, Wayne, Liu, Bede
• Primary Examiner(s): JANKUS, ALMIS R
• Application Number:
  US08/856,899
• Time in Patent Office: 516 Days
• Field of Search: 345/440, 345/302, 345/473-475, 345/326, 345/327, 345/328, 345/348-350, 345/356, 345/357, 382/226, 348/391
• US Class Current: 345/440
• CPC Class Codes: G06F 16/7328 Query by example, e.g. a complete video frame or video sequence graphical querying G06F16/7335
• CPC Class Codes: G06F 16/738 Presentation of query results
• CPC Class Codes: G06F 16/745 the internal structure of a single video sequence

Abstract

A new technique for extracting a hierarchical decomposition of a complex video selection for browsing purposes, combines visual and temporal information to capture the important relations within a scene and between scenes in a video, thus allowing the analysis of the underlying story structure with no a priori knowledge of the content. A general model of hierarchical scene transition graph is applied to an implementation for browsing. Video shots are first identified and a collection of key frames is used to represent each video segment. These collections are then classified according to gross visual information. A platform is built on which the video is presented as directed graphs to the user, with each category of video shots represented by a node and each edge denoting a temporal relationship between categories. The analysis and processing of video is carried out directly on the compressed videos. Preliminary tests show that the narrative structure of a video selection can be effectively captured using this technique.

Claims

1. A video browser comprising:

node defining means for defining a plurality of nodes, each of the plurality of nodes representing a collecting of video shots;

temporal relationship defining means for defining at least one temporal relationship between at least first and second ones of the plurality of nodes; and

a display for displaying graphical representations of the plurality of nodes and the at least one temporal relationship.

2. The video browser of claim 1, wherein the video shots of each of the plurality of nodes are interrelated by at least one of color, spatial correlation and shape.

3. The video browser of claim 1, wherein the video shots of each of the plurality of nodes are arranged in temporal order.

4. The video browser of claim. 1, wherein the graphical representation of the temporal relationship is an edge.

5. The video browser of claim 1, wherein the graphical representations of the plurality of nodes and the at least one temporal relationship are displayed as a hierarchical scene transition graph.

6. The video browser of claim 5, wherein the hierarchical scene transition graph includes a plurality of levels and wherein each of the levels can be constructed according to different criteria.

7. The video browser of claim 1, further comprising means for grouping video shots of at least two of the plurality of nodes to form an additional node.

8. The video browser of claim 1, further comprising means for ungrouping video shots from at least one of the plurality of nodes to form an additional node.

9. A method for presenting video shots for browsing, comprising the steps of:

defining a plurality of nodes, each of the plurality of nodes representing a collection of the video shots;

defining at least one temporal relationship between at least first and second ones of the plurality of nodes; and

displaying graphical representations of the plurality of nodes and the at least one temporal relationship.

10. The method of claim 9, wherein the video shots of each of the plurality of nodes are interrelated by at least one of color, spatial correlation, and shape.

11. The method of claim 9, wherein the video shots of each of the plurality of nodes are arranged in temporal order.

12. The method of claim 9, wherein the graphical representation(s) of the temporal relationship is an edge.

13. The method of claim 9, wherein the graphical representations of the plurality of nodes and the at least one temporal relationship are displayed as a hierarchical scene transition graph.

14. The method of claim 13, wherein the hierarchical scene transition graph includes a plurality of levels and wherein each of the levels can be constructed according to different criteria.

15. The method of claim 9, further comprising the step of grouping video shots of at least two of the plurality of nodes to form an additional node.

16. The method of claim 9, further comprising the step of ungrouping video shots from at least one of the plurality of nodes to form an additional node.