Video description system and method

• US 7,143,434 B1
• Filed: 11/05/1999
• Issued: 11/28/2006
• Est. Priority Date: 11/06/1998
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.), Trustees Of Columbia University In The City Of New York (Columbia University), International Business Machines Corporation
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Chang, Shih-Fu, Smith, John R., Li, Chung-Sheng, Bergman, Lawrence, Puri, Atul, Paek, Seungyup, Benitez, Ana
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): SHEPARD, JUSTIN E
• Application Number:
  US09/831,218
• Time in Patent Office: 2,580 Days
• Field of Search: 715/500.1
• US Class Current: 725/142
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06V 10/422 for representing the structure of the pattern or shape of an object therefor
• 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

The present invention relates to a system for generating a description record from multimedia information including, e.g., video data. A multimedia information input interface is used to receive multimedia information. A computer processor receives the multimedia information, processes the video information by performing video object extraction processing to generate video object descriptions from the video information, processes the generated video object descriptions by object hierarchy construction and extraction processing to generate video object hierarchy descriptions, and processes the generated video object descriptions by entity relation graph descriptions.

Claims

1. A system for generating a description record from video information, comprising:

at least one video input interface for receiving said video information;

a computer processor coupled to said at least one video input interface for receiving said video information therefrom, processing said video information by performing video object extraction processing to generate video object descriptions from said video information, processing said generated video object descriptions by object hierarchy construction and extraction processing to generate video object hierarchy descriptions, and processing said generated video object descriptions by entity relation graph generation processing to generate entity relation graph descriptions, wherein at least one description record including said video object descriptions, said video object hierarchy descriptions and said entity relation graph descriptions is generated to represent content embedded within said video information; and

a data storage system, operatively coupled to said processor, for storing said at least one description records;

wherein said video object extraction processing and said object hierarchy construction and extraction processing are performed in parallel.

2. The system of claim 1, wherein said video object extraction processing comprises:

video segmentation processing to segment each video in said video information into regions within said video; and

feature extraction and annotation processing to generate one or more feature descriptions for one or more said regions;

whereby said generated video object descriptions comprise said one or more feature descriptions for one or more said regions.

3. The system of claim 2, wherein said regions are selected from the group consisting of local, segment and global regions.

4. The system of claim 2, wherein said one or more feature descriptions are selected from the group consisting of media features, visual features, temporal features, and semantic features.

5. The system of claim 4, wherein said semantic features are further defined by at least one feature description selected from the group consisting of who, what object, what action, where, when, why, and text annotation.

6. The system of claim 4, wherein said visual features are further defined by at least one feature description selected from the group consisting of color, texture, position, size, shape, motion, camera motion, editing effect, and orientation.

7. The system of claim 4, wherein said media features are further defined by at least one feature description selected from the group consisting of file format, file size, color representation, resolution, data file location, author, creation, scalable layer and modality transcoding.

8. The system of claim 4, wherein said temporal features are further defined by at least one feature description selected from the group consisting of start time, end time and duration.

9. The system of claim 1, wherein said object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on visual feature relationships of video objects represented by said video object descriptions.

10. The system of claim 1, wherein said object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on semantic feature relationships of video objects represented by said video object descriptions.

11. The system of claim 1, wherein said object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on media feature relationships of video objects represented by said video object descriptions.

12. The system of claim 1, wherein said object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from the group consisting of visual feature relationships, semantic feature relationships, temporal feature relationships and media feature relationships.

13. The system of claim 1, wherein said object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on relationships of video objects represented by said video object descriptions, wherein said video object hierarchy descriptions have a plurality of hierarchical levels.

14. The system of claim 13, wherein said video object hierarchy descriptions having a plurality of hierarchical levels comprise clustering hierarchies.

15. The system of claim 14, wherein said clustering hierarchies are based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from a group consisting of visual feature relationships, semantic feature relationships, temporal relationships and media feature relationships.

16. The system of claim 14, wherein said video object hierarchy descriptions having a plurality of hierarchical levels are configured to comprise multiple levels of abstraction hierarchies.

17. The method of claim 16, wherein said multiple levels of abstraction hierarchies are configured to be based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from a group consisting of visual feature relationships, semantic feature relationships, temporal feature relationships and media feature relationships.

18. The system of claim 1, wherein said entity relation graph generation processing generates entity relation graph descriptions of said video object descriptions based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from the group consisting of visual feature relationships, semantic feature relationships, temporal feature relationships and media feature relationships.

19. The system of claim 1, further comprising an encoder for receiving and encoding said video object descriptions into encoded description information, wherein said data storage system is operative to store said encoded description information as said at least one description record.

20. The system of claim 1, wherein said video object descriptions, said video object hierarchy descriptions, and said entity relation graph descriptions are combined together to form video descriptions, and further comprising an encoder for receiving and encoding said video descriptions into encoded description information, wherein said data storage system is operative to store said encoded description information as said at least one description record.

21. The system of claim 20, wherein said encoder comprises a binary encoder.

22. The system of claim 20, wherein said encoder comprises an XML encoder.

23. The system of claim 1, further comprising:

a video display device operatively coupled to the computer processor for displaying the video information; and

at least one user input device operatively coupled to the computer processor, wherein at least a portion of said video object extraction processing, said object hierarchy construction and extraction processing, or said entity relation graph generation processing includes receiving a user input through manipulation of said user input device.

47. The system of claim 1, wherein feature descriptions include pointers to extraction and matching code to facilitate code downloading.

48. The system of claim 4, wherein feature descriptions include pointers to extraction and matching code to facilitate code downloading.

24. A method for generating a description record from video information, comprising the steps of:

receiving said video information;

processing said video information by performing video object extraction processing to generate video object descriptions from said video information;

processing said generated video object descriptions by object hierarchy construction and extraction processing to generate video object hierarchy descriptions;

processing said generated video object descriptions by entity relation graph generation processing to generate entity relation graph descriptions, wherein at least one description record including said video object descriptions, said video object hierarchy descriptions and said entity relation graph descriptions is generated to represent content embedded within said video information; and

storing said at least one description record;

wherein said steps of video object extraction processing and object hierarchy construction and extraction processing are performed in parallel.

25. The method of claim 24, wherein said step of video object extraction processing comprises the further steps of:

video segmentation processing to segment each video in said video information into regions within said video; and

feature extraction and annotation processing to generate one or more feature descriptions for one or more said regions;

whereby said generated video object descriptions comprise said one or more feature descriptions for one or more said regions.

26. The method of claim 25, wherein said regions are selected from the group consisting of local, segment and global regions.

27. The method of claim 25, further comprising the step of selecting said one or more feature descriptions from the group consisting of media features, visual features, temporal and semantic features.

28. The method of claim 27, wherein said semantic features are further defined by at least one feature description selected from the group consisting of who, what object, what action, where, when, why and text annotation.

29. The method of claim 27, wherein said visual features are further defined by at least one feature description selected from the group consisting of color, texture, position, size, shape, motion, editing effect, camera motion and orientation.

30. The method of claim 27, wherein said media features are further defined by at least one feature description selected from the group consisting of file format, file size, color representation, resolution, data file location, author, creation, scalable layer and modality transcoding.

31. The method of claim 27, wherein said temporal features are further defined by at least one feature description selected from the group consisting of start time, end time and duration.

32. The method of claim 24, wherein said step of object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on visual feature relationships of video objects represented by said video object descriptions.

33. The method of claim 24, wherein said step of object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on semantic feature relationships of video objects represented by said video object descriptions.

34. The method of claim 24, wherein said step of object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on media feature relationships of video objects represented by said video object descriptions.

35. The method of claim 24, wherein said step of object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on temporal feature relationships of video objects represented by said video object descriptions.

36. The method of claim 24, wherein said step of object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from the group consisting of visual feature relationships, semantic feature relationships, temporal feature relationships and media feature relationships.

37. The method of claim 24, wherein said step of object hierarchy construction and extraction processing generates video object hierarchy descriptions of said video object descriptions based on relationships of video objects represented by said video object descriptions, wherein said video object hierarchy descriptions are configured to have a plurality of hierarchical levels.

38. The method of claim 37, wherein said video object hierarchy descriptions having a plurality of hierarchical levels are configured to comprise clustering hierarchies.

39. The method of claim 38, wherein said clustering hierarchies are configured to be based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from a group consisting of visual feature relationships, semantic feature relationships, temporal feature relationships and media feature relationships.

40. The method of claim 38, wherein said video object hierarchy descriptions having a plurality of hierarchical levels are configured to comprise multiple levels of abstraction hierarchies.

41. The method of claim 38, wherein said multiple levels of abstraction hierarchies are configured to be based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from a group consisting of visual feature relationships, semantic feature relationships, temporal feature relationships and media feature relationships.

42. The method of claim 24, wherein said step of entity relation graph generation processing generates entity relation graph descriptions of said video object descriptions based on relationships of video objects represented by said video object descriptions, wherein said relationships are selected from the group consisting of visual feature relationships, semantic feature relationships, temporal feature relationships and media feature relationships.

43. The method of claim 24, further comprising the steps of receiving and encoding said video object descriptions into encoded description information, and storing said encoded description information as said at least one description record.

44. The method of claim 24, further comprising the steps of combining said video object descriptions, said video object hierarchy descriptions, and said entity relation graph descriptions to form video descriptions, and receiving and encoding said video descriptions into encoded description information, and storing said encoded description information as said at least one description record.

45. The method of claim 44, wherein said step of encoding comprises the step of binary encoding.

46. The method of claim 44, wherein said step of encoding comprises the step of XML encoding.

49. The method of claim 24, wherein feature descriptions include pointers to extraction and matching code to facilitate code downloading.

50. The method of claim 27, wherein feature descriptions include pointers to extraction and matching code to facilitate code downloading.