Method for building and extracting entity networks from video

• US 8,995,717 B2
• Filed: 08/29/2012
• Issued: 03/31/2015
• Est. Priority Date: 12/14/2007
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Cheng, Hui, Xiao, Jiangjian, Sawhney, Harpreet
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US13/597,698
• Publication Number:
  US 20120321137A1
• Time in Patent Office: 944 Days
• Field of Search: None
• US Class Current: 382/103
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69

Abstract

A computer implemented method for deriving an attribute entity network (AEN) from video data is disclosed, comprising the steps of: extracting at least two entities from the video data; tracking the trajectories of the at least two entities to form at least two tracks; deriving at least one association between at least two entities by detecting at least one event involving the at least two entities, said detecting of at least one event being based on detecting at least one spatio-temporal motion correlation between the at least two entities; and constructing the AEN by creating a graph wherein the at least two objects form at least two nodes and the at least one association forms a link between the at least two nodes.

Claims

1. A computer implemented method for deriving, from video data, an association between at least two entities in motion, comprising:

extracting the entities from the video data;

tracking trajectories of the entities based on the video data to form two or more tracklets;

deriving one or more associations between the entities by;

detecting an event based on at least one spatio-temporal motion correlation between the entities;

calculating a similarity measure of the closeness of the tracklets;

identifying entity behaviors comprising at least one of spatial actions and behavioral action;

performing pattern analysis to group the tracklets and sites; and

merging an event ontology with hierarchical weighted graph matching to reduce candidate space wherein the candidate space comprises all entities to be tracked.

2. The method of claim 1, wherein extracting the entities further comprises:

detecting moving objects and classifying them as at least one of vehicles or people; and

determining which structures in the video data are sites, comprising at least one of roads, parking lots, buildings and building descriptions.

3. The method of claim 1, wherein the at least one event is classified as one of a spatial action and a behavioral action.

4. The method of claim 3, wherein a behavioral action is detected using Spatial-Temporal Object (STO) Analysis.

5. The method of claim 4, wherein STO Analysis further comprises:

obtaining a focus-of-attention of moving objects in the video data using Spatio-Temporal Cues;

obtaining spatio-temporal fragments extracted from the moving objects within the focus-of-attention, the moving objects including at least one person;

combining the obtaining spatio-temporal fragments to compute at least one pose of the at least one person;

extracting and classifying at least one object associated the at least one person;

extracting feature words are extracted from the at least one objects and at least one person to create spatio-temporal object words;

encoding the spatio-temporal object words as feature vectors; and

classifying the feature vectors using a Supporting Vector Machine (SVM).

6. The method of claim 1, wherein the step of merging an event ontology with hierarchical weighted graph matching further comprising the steps of:

constructing an event graph wherein a node represents a sub-event and a link represents a type of a temporal transition between two nodes, the link being assigned a weight that is proportional to an importance of the temporal transition to the overall event;

forming a hierarchical event description by removing nodes with small weights and combining the links between nodes with large weights;

matching observations using the event graph at its highest level, wherein observations receiving a predetermined minimum matching score being passed to a next level for verification; and

repeating the step of matching with other observations until a predetermined confidence level is achieved for accepting or rejecting an event.

7. The method of claim 6, wherein the step of matching further comprising the step of computing the similarity between two events using a shortest path length measure between two entities/actions in an entity/action taxonomy.

8. An apparatus for deriving an association between at least two entities in motion from video data captured by at least one sensor, comprising:

a processor communicatively connected to said at least one sensor, the processor being configured for;

extracting the entities from the video data;

tracking trajectories of the entities based on the video data to form two or more tracklets; and

deriving one or more associations between the entities by;

detecting an event based on at least one spatio-temporal motion correlation between the entities;

calculating a similarity measure of the closeness of the tracklets;

identifying entity behaviors comprising at least one of spatial actions and behavioral action;

performing pattern analysis to group the tracklets and sites; and

merging an event ontology with hierarchical weighted graph matching to reduce candidate space wherein the candidate space comprises all entities to be tracked.

9. The apparatus of claim 8, wherein extracting the entities further comprises:

detecting moving objects and classifying them as at least one of vehicles or people; and

determining which structures in the video data are sites, comprising at least one of roads, parking lots, buildings and building descriptions.

10. The apparatus of claim 8, wherein the at least one event is classified as one of a spatial action and a behavioral action.

11. The apparatus of claim 10, wherein a behavioral action is detected by:

obtaining a focus-of-attention of moving objects in the video data using Spatio-Temporal Cues;

obtaining spatio-temporal fragments extracted from the entities in motion within the focus-of-attention, the entities in motion including at least one person;

combining the spatio-temporal fragments to compute at least one pose of the at least one person;

extracting and classifying at least one object associated the at least one person;

extracting feature words are extracted from the at least one objects and at least one person to create spatio-temporal object words;

encoding the spatio-temporal object words as feature vectors; and

classifying the feature vectors using a Supporting Vector Machine (SVM).

12. The apparatus of claim 8, wherein the processor is further configured for merging an event ontology with hierarchical weighted graph matching to reduce candidate space wherein the candidate space comprises all entities to be tracked comprising:

constructing an event graph wherein a node represents a sub-event and a link represents a type of a temporal transition between two nodes, the link being assigned a weight that is proportional to an importance of the temporal transition to the event;

forming a hierarchical event description by removing nodes with small weights and combining the links between nodes with large weights;

matching observations using the event graph at its highest level, wherein observations receiving a predetermined minimum matching score being passed to a next level for verification; and

repeating the step of matching with other observations until a predetermined confidence level is achieved for accepting or rejecting an event.

13. A computer implemented method for deriving, from video data, an association between at least two entities in motion, comprising:

extracting the entities from the video data;

tracking trajectories of the entities;

deriving one or more associations between the entities by detecting at least one event based on at least one spatio-temporal motion correlation between the entities; and

merging an event ontology with hierarchical weighted graph matching to reduce candidate space wherein the candidate space comprises all entities to be tracked.

14. The method of claim 13, wherein extracting the entities further comprises:

detecting moving objects and classifying them as at least one of vehicles or people; and

determining which structures in the video data are sites, comprising at least one of roads, parking lots, buildings and building descriptions.

15. The method of claim 13, wherein the at least one event is classified as one of a spatial action and a behavioral action.

16. The method of claim 13 wherein tracking the trajectories of the entities forms two or more tracklets, and the method further comprises:

calculating a similarity measure of the closeness of the two or more tracklets; and

performing pattern analysis using the similarity measure to group the two or more tracklets.

17. A computer implemented method for deriving, from video data, an association between at least two entities in motion, comprising:

extracting the entities from the video data;

tracking trajectories of the entities;

deriving one or more associations between the entities by detecting at least one event based on at least one spatio-temporal motion correlation between the entities; and

employing a Markov Logic Network for reasoning and inferencing in visual and geo-spatial domains.

18. The method of claim 17, wherein extracting the entities further comprises:

detecting moving objects and classifying them as at least one of vehicles or people; and

determining which structures in the video data are sites, comprising at least one of roads, parking lots, buildings and building descriptions.

19. The method of claim 17, wherein the at least one event is classified as one of a spatial action and a behavioral action.

20. The method of claim 17 wherein tracking the trajectories of the entities forms two or more tracklets, and the method further comprises:

calculating a similarity measure of the closeness of the two or more tracklets; and

performing pattern analysis using the similarity measure to group the two or more tracklets.