Graph matching by sub-graph grouping and indexing

Patent metadata

Field	Value
Publication number	US-10642891-B2
Application number	US-201414252661-A
Country	US
Kind code	B2
Filing date	Apr 14, 2014
Priority date	Apr 12, 2013
Publication date	May 5, 2020
Grant date	May 5, 2020

Abstract

Relational graphs may be used to extract information. Similarities between the relational graphs and the items they represent may be determined. For example, when applied to video searching, relational graphs may be obtained from searching videos to extract objects, events and/or relations therebetween. Each relational graph may comprise a plurality of nodes and edges, wherein at least some of the detected objects and events are represented by each node, and wherein each edge and represents a relationship between two nodes. Subgraphs may be extracted from each relational graph and dimension reduction may be performed on the subgraphs to obtain a reduced variable set which may then be used to perform searches, such as similarity analyses of videos.

First claim

We claim:

1. A method of performing video searching, comprising:
maintaining a storage of a plurality of grouped events in the form of a plurality of corresponding relational graphs, each relational graph having a number of subgraphs;
for at least a first grouped event having a corresponding first relational graph, extracting and indexing a first set of subgraphs including a plurality of subgraphs, the first set of subgraphs including at least one subgraph having at least 1 node;
performing dimension reduction for the first grouped event to form a plurality of subgraph groupings, each subgraph grouping including a plurality of subgraphs of the first set of subgraphs;
receiving a search request for a video search, the search request for a portion of a video that includes at least a second grouped event; and
based on the plurality of subgraph groupings, determining that the second grouped event matches the first grouped event.

2. The method of claim 1 , wherein the first set of subgraphs includes all subgraphs of the first relational graph having an order of 1 and all subgraphs of the first relational graph having an order of 2.

3. The method of claim 1 , further comprising:
performing the dimension reduction by selecting a predetermined number of topics, wherein each subgraph grouping is associated with a respective topic.

4. The method of claim 3 , wherein:
the predetermined number of topics is less than the number of subgraphs of the first relational graph.

5. The method of claim 4 , wherein:
the predetermined number of topics is at least two orders of magnitude smaller than the number of subgraphs of the first relational graph.

6. The method of claim 5 , wherein a particular subgraph is associated with a plurality of different topics and is weighted differently in at least one of the topics compared to the other topics.

7. The method of claim 1 , wherein the second grouped event has corresponding second relational graph, and further comprising:
for the second grouped event, indexing a second set of subgraphs including a plurality of subgraphs, the second set of subgraphs including at least one subgraph having an order of 2; and
performing dimension reduction for the second grouped event to form a plurality of subgraph groupings, each subgraph grouping including one or more subgraphs of the second set of subgraphs,
wherein determining that the second grouped event matches the first grouped event further includes:
comparing the plurality of subgraph groupings of the second grouped event to the plurality of subgraph groupings of the first grouped event.

8. The method of claim 1 , wherein each subgraph of the first set of indexed subgraphs is associated with a weighting factor.

9. The method of claim 8 , wherein the weighting factor for a particular subgraph of the first set of indexed subgraphs is learned based on a frequency of occurrence of the particular subgraph from a large set of training data.

10. The method of claim 1 , further comprising:
based on the plurality of subgraph groupings, determining that the second grouped event matches a third grouped event different from the first grouped event; and
ranking the first grouped event as a search result having a higher rank than the third grouped event.

11. The method of claim 1 , further comprising:
forming the first relational graph by performing semantic video analysis of a video clip.

12. A method of retrieving a video clip, comprising:
receiving a video search query for a portion of video that includes a first grouped event, the first grouped event corresponding to a first relational graph, the video search query including a first video clip;
extracting and indexing a first set of subgraphs for the first grouped event based on the first relational graph, the first set of subgraphs including a plurality of subgraphs including at least one subgraph having an order of 2;
performing dimension reduction for the first grouped event to form a plurality of first subgraph groupings, each first subgraph grouping including a plurality of subgraphs of the first set of subgraphs;
comparing the plurality of first subgraph groupings to a plurality of stored subgraph groupings that correspond to stored grouped events;
based on the comparison, determining that the first grouped event matches a stored subgraph grouping of the plurality of stored subgraph groupings; and
retrieving a second video clip corresponding to the stored subgraph grouping in response to the determining.

13. The method of claim 12 , wherein each first subgraph grouping corresponds to a topic related to the video and the stored subgraph grouping corresponds to a topic related to the video clip.

14. The method of claim 12 , wherein the retrieved video clip is ranked among a plurality of retrieved video clips based on the comparison.

15. A method of performing video searching, comprising:
maintaining a storage of a plurality of relational graphs including at least a first relational graph, the first relational graph corresponding to a first event in a video and having a number of subgraphs of M;
for at least a first event having a corresponding first relational graph, extracting and indexing a first set of subgraphs including a plurality of subgraphs, the first set of subgraphs including at least one subgraph having an order of 2;
forming a plurality of N subgraph groupings, each subgraph grouping including a plurality of subgraphs of the first set of subgraphs, wherein N is less than M;
receiving a search request for a video search, the search request for a portion of a video that includes at least a second event; and
based on the plurality of subgraph groupings, determining that the second event matches the first event.

16. The method of claim 15 , wherein N is at least two orders of magnitude smaller than M.

17. A method of performing video-to-video searching, comprising:
maintaining a storage of a plurality of relational graphs, each relational graph representing a set of related information and having a number of subgraphs;
for at least a first relational graph corresponding to a first set of related information, extracting and indexing a first set of subgraphs including a plurality of subgraphs, the first set of subgraphs including p subgraphs and at least one subgraph having an order of 2;
performing dimension reduction for the first relational graph to form k variables derived from the p subgraphs, k being an integer less than p;
receiving a video clip as a search request, the search request for a second set of related information, wherein each of the first and second sets of related information is a grouped event that is part of a video; and
based on the k variables, determining that the second set of related information matches the first set of related information.

18. The method of claim 17 , wherein:
the k variables comprise k subgraph groupings, each subgraph grouping including a group of subgraphs from the p subgraphs.

19. The method of claim 18 , wherein the second grouped event has corresponding second relational graph, and further comprising:
for the second grouped event, indexing a second set of subgraphs including a plurality of subgraphs, the second set of subgraphs including at least one subgraph having an order of 2; and
performing dimension reduction for the second grouped event to form a plurality of subgraph groupings, each subgraph grouping including one or more subgraphs of the second set of subgraphs,
wherein determining that the second grouped event ma

Assignees

• Avigilon Fortress Corp

Inventors

• Choe Tae Eun
• Deng Hongli
• Lee Mun Wai
• Guo Feng

Classifications

• G06F16/71

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/73 Primary

  Querying · CPC title