Method for building and extracting entity networks from video

• US 8,294,763 B2
• Filed: 11/14/2008
• Issued: 10/23/2012
• 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): Eng, David
• Application Number:
  US12/271,173
• Publication Number:
  US 20090153661A1
• Time in Patent Office: 1,439 Days
• Field of Search: 348/143
• US Class Current: 348/143
• 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, where the detecting of at least one event is based on detecting at least one spatiotemporal 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 an attribute entity network (AEN) from video data, comprising the steps of:

extracting at least two entities from the video data;

tracking trajectories, based on the video data, of the at least two entities to form at least two tracklets;

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 as a graph wherein the at least two entities form at least two nodes and the at least one association forms a link between the at least two nodes.

2. The method of claim 1, wherein the entity extraction step further comprises the steps of:

detecting moving objects and classifying them into vehicle and people; and

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

3. The method of claim 1, wherein the deriving step further comprises the steps of:

calculating a similarity measure of the closeness of the at least two tracklets;

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

performing pattern analysis to group the at least two tracklets and sites.

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

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

6. The method of claim 5, wherein STO Analysis comprises the steps of:

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).

7. The method of claim 1, further comprising the steps of merging an event ontology with hierarchical weighted graph matching to reduce candidate space wherein the candidate space comprises all entities to be tracked.

8. The method of claim 7, 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 the type of temporal transition between two nodes, the link being assigned a weight that is proportional to the 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 hierarchical 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.

9. The method of claim 8, 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.

10. The method of claim 1, further comprising the step of employing a Markov Logic Network for reasoning and inferencing in visual and geo-spatial domains the spatio-temporal motion correlation between the at least two entities.

11. An apparatus for deriving an attribute entity network (AEN) from video data, comprising:

at least one camera for generating the video data;

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

extracting at least two entities from the video data;

tracking trajectories of the at least two entities to form at least two tracklets;

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 as a graph wherein the at least two entities form at least two nodes and the at least one association forms a link between the at least two nodes; and

a display for displaying the AEN.

12. The apparatus of claim 11, wherein the at least one event is classified as one of a spatial action and a behavioral action, wherein the behavioral action is detected using Spatial-Temporal Object (STO) Analysis.

13. The apparatus of claim 12, wherein STO Analysis comprises the steps of:

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).

14. The apparatus of claim 11, 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.

15. The apparatus of claim 14, wherein merging an event ontology with hierarchical weighted graph matching further comprises:

constructing an event graph wherein a node represents a sub-event and a link represents the type of temporal transition between two nodes, the link being assigned a weight that is proportional to the 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 hierarchical 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.

16. The apparatus of claim 11, wherein the processor is further configured for employing a Markov Logic Network for reasoning and inferencing in visual and geo-spatial domains.

17. A non-transitory computer-readable medium carrying one or more sequences for deriving an attribute entity network (AEN) from video data, wherein execution of the one of more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

extracting at least two entities from the video data;

tracking trajectories of the at least two entities to form at least two tracklets;

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 as a graph wherein the at least two entities form at least two nodes and the at least one association forms a link between the at least two nodes.

18. The computer-readable medium of claim 17, wherein the at least one event is classified as one of a spatial action and a behavioral action, wherein the behavioral action is detected using Spatial-Temporal Object (STO) Analysis.

19. The computer-readable medium of claim 18, wherein STO Analysis comprises the steps of:

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).

20. The computer-readable medium of claim 17, further comprising the steps of merging an event ontology with hierarchical weighted graph matching to reduce candidate space wherein the candidate space comprises all entities to be tracked.

21. The computer-readable medium of claim 20, wherein merging an event ontology with hierarchical weighted graph matching further comprises:

constructing an event graph wherein a node represents a sub-event and a link represents the type of temporal transition between two nodes, the link being assigned a weight that is proportional to the 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 hierarchical 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.

22. The computer-readable medium of claim 17, wherein further comprising the steps of employing a Markov Logic Network for reasoning and inferencing in visual and geo-spatial domains.