Large scale video search using queries that define relationships between objects

• US 10,275,656 B2
• Filed: 11/20/2015
• Issued: 04/30/2019
• Est. Priority Date: 11/21/2014
• Status: Active Grant

• Current Assignee: Trustees of Boston University
• Original Assignee: Trustees of Boston University
• Inventors: Castanon, Gregory D., Saligrama, Venkatesh, Zhang, Ziming, Chen, Yuting
• Primary Examiner(s): Grant, II, Jerome
• Application Number:
  US15/526,670
• Publication Number:
  US 20170357853A1
• Time in Patent Office: 1,257 Days
• Field of Search: 382209
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/483 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 20/30 in albums, collections or shared content, e.g. social network photos or video
• CPC Class Codes: G06V 20/48 Matching video sequences
• CPC Class Codes: G06V 20/54 of traffic, e.g. cars on the road, trains or boats

Abstract

One embodiment of the present solution is a relationship-based video server system. The server system is programmed to provide a platform for large scale video search based on relationships between objects in video segments, and the platform executes search based on probabilistically discriminative objects and relationships.

Claims

1. A relationship-based video server system, programmed to provide a platform for large scale video search based on relationships between objects in video segments, the platform executing search based on probabilistically discriminative objects and relationships, wherein the server system is configured to run processes that:

for each video segment received for storage in a video database,

analyze image data in the video segment to (1) recognize objects that are represented in the video segment and (2) identify relationships between the objects,

determine, based on probabilities of occurrence for the recognized objects and identified relationships, at least one of (1) the most discriminative object or (2) the most discriminative relationship in the video segment,

configure, based on at least one of the most discriminative object or the most discriminative relationship, a data structure that includes the recognized objects and identified relationships of the video segment;

store the data structure in the video database;

receive a video search query defining relationships between a plurality of objects;

determine, based on probabilities of occurrence for the objects and relationships of the video search query, at least one of the most discriminative object or the most discriminative relationship of the video search query;

identify, based on at least one of the most discriminative object or the most discriminative relationship of the video search query, a subset of the data structures to search for video segments;

determine, for each video segment represented in the subset of the data structures, a score based on similarity between the objects and the relationships in the video search query and the objects and the relationships associated with the video segment; and

display representations of video segments with the highest scores.

2. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that, for each video segment received for storage, analyze the image data in the video segment to identify at least one attribute of at least one recognized object.

3. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that, for each video segment received for storage, determine a set of discriminative objects and relationships based on probabilities of occurrence for the recognized objects and identified relationships.

4. The relationship-based video server system of claim 3, wherein the server system is configured to run processes that, for each video segment received for storage, configure the data structure for the video segment by hashing the objects and the relationships in the set of discriminative objects and relationships.

5. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that, for each video segment received for storage, configure the data structure for the video segment by hashing the recognized objects and identified relationships of the video segment.

6. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that, for each video segment received for storage, stored the data structure for the video segment in a fuzzy hash table.

7. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that receive a video search query in a graphical representation, wherein each object is represented by a unique node and each relationship is represented by a unique edge.

8. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that determine a set of discriminative objects and relationships for the video search query.

9. The relationship-based video server system of claim 8, wherein the server system is configured to run processes that identify the subset of the data structures to search by downsampling the stored video segments based on the set of discriminative objects and relationships for the video search query.

10. The relationship-based video server system of claim 8, wherein the server system is configured to run processes that determine a maximally discriminative spanning tree based on the set of discriminative objects and relationships for the video search query.

11. The relationship-based video server system of claim 10, wherein the server system is configured to run processes that identify the subset of the data structures to search by creating a graph based on the maximally discriminative spanning tree of the video search query and the stored video segments.

12. The relationship-based video server system of claim 11, wherein the graph is a tree structure.

13. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that identify the subset of the data structures to search by downsampling the stored video segments based on at least one of the most discriminative object or the most discriminative relationship of the video search query.

14. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that determine, for each video segment represented in the subset of the data structures, the score based on similarity by (1) computing subscores between the objects in the video search query and the objects in the video segment, (2) computing subscores between the relationships in the video search query and the relationships in the video segment, and (3) summing the subscores.

15. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that determine, for each video segment represented in the subset of the data structures, the score based on similarity that accounts for tolerance levels of a user.

16. The relationship-based video server system of claim 1, wherein the server system is configured to run processes that (1) predict a user intent of the video search query, (2) determine at least one potential alteration to the video search query based on the user intent, and (3) display an altered video search query as a proposed search query for the user.

17. The relationship-based video server system of claim 1, wherein each video segment has a duration of a pre-determined interval.

18. The relationship-based video server system of claim 17, wherein the pre-determined interval is 15 minutes.

19. The relationship-based video server system of claim 1, wherein at least one relationship in the video search query is a spatial relationship.

20. A computer program product having a non-transitory computer-readable medium with computer code thereon for searching large scale video data, the computer program product comprising:

program code for receiving a video search query defining relationships between a plurality of objects;

program code for determining, based on probabilities of occurrence for the objects and relationships of the video search query, at least one of the most discriminative object or the most discriminative relationship of the video search query;

program code for accessing a video database that stores video segments;

program code for identifying, based on at least one of the most discriminative object or the most discriminative relationship of the video search query, a subset of the video segments stored in a video database to be subject to search;

program code for determining, for each video segment in the subset subject to search, a score based on similarity between the objects and the relationships in the video search query and the objects and the relationships associated with the video segment; and

program code for displaying representations of video segments with the highest scores.

21. The computer program product of claim 20, further comprising:

program code for receiving the video search query in a graphical representation, wherein each object is represented by a unique node and each relationship is represented by a unique edge.

22. The computer program product of claim 20, further comprising:

program code for downsampling the stored video segments based on at least one of the most discriminative object or the most discriminative relationship of the video search query.