Geospatial-temporal semantic graph representations of trajectories from remote sensing and geolocation data

• US 9,727,976 B1
• Filed: 05/19/2016
• Issued: 08/08/2017
• Est. Priority Date: 09/08/2015
• Status: Active Grant

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Brost, Randolph, Perkins, David Nikolaus, Ray, Lawrence P.
• Primary Examiner(s): Lee, Jonathan S
• Application Number:
  US15/159,384
• Time in Patent Office: 446 Days
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

Various technologies for facilitating analysis of large remote sensing and geolocation datasets to identify features of interest are described herein. A search query can be submitted to a computing system that executes searches over a geospatial temporal semantic (GTS) graph to identify features of interest. The GTS graph comprises nodes corresponding to objects described in the remote sensing and geolocation datasets, and edges that indicate geospatial or temporal relationships between pairs of nodes in the nodes. Trajectory information is encoded in the GTS graph by the inclusion of movable nodes to facilitate searches for features of interest in the datasets relative to moving objects such as vehicles.

Claims

1. A computing device, comprising:

at least one processor; and

memory comprising instructions that, when executed by the at least one processor, cause the at least one processor to perform acts comprising;

based upon a remote sensing image of a scene and geolocation data, the geolocation data indicative of a plurality of locations of a first object over a window of time, constructing a geospatial temporal semantic (GTS) graph that is representative of objects in the scene, the objects in the scene include the first object, the GTS graph comprising;

nodes that represent the objects, wherein a first node in the nodes represents the first object, the first node assigned data that indicates that the first node corresponds to a trajectory, the trajectory comprising the locations of the first object over the window of time; and

undirected edges, wherein each undirected edge in the undirected edges couples a respective pair of nodes in the nodes, the undirected edge is assigned data that is indicative of a symmetric relationship between objects in the scene represented by nodes in the pair of nodes; and

providing the GTS graph to a search system, the GTS graph searchable in response to receipt of a query.

2. The computing device of claim 1, wherein the symmetric relationship between objects in the scene is a distance between the objects in the scene.

3. The computing device of claim 2, wherein a first undirected edge couples the first node and a second node in the nodes, the second node representing a second object, the first undirected edge assigned data that is indicative of a minimum distance between the first object and the second object over the window of time.

4. The computing device of claim 3, wherein the minimum distance is a minimum distance between the second object and the locations of the first object over the window of time.

5. The computing device of claim 3, wherein the minimum distance is a minimum distance between the second object and interpolated locations of the first object, the interpolated locations of the first object based upon the locations of the first object over the window of time.

6. The computing device of claim 5, wherein the interpolated locations are based upon the locations of the first object over the window of time and a heading of the first object.

7. The computing device of claim 5, wherein the data assigned to the first node indicates that the first node corresponds to a first trajectory and a second trajectory, the first trajectory comprising locations of the first object during a first window of time in the window of time, the second trajectory comprising locations of the first object during a second window of time in the window of time, wherein further each of the interpolated locations is based exclusively upon either the locations of the first object during the first window of time or the locations of the first object during the second window of time.

8. The computing device of claim 1, wherein the geolocation data comprises a plurality of timestamped latitude-longitude coordinate pairs.

9. The computing device of claim 1, wherein the data assigned to the first node indicates that the first node corresponds to a first trajectory and a second trajectory, the first trajectory comprising locations of the first object during a first window of time in the window of time, the second trajectory comprising locations of the first object during a second window of time in the window of time.

10. The computing device of claim 9, wherein the symmetric relationship between objects in the scene is a distance between the objects in the scene.

11. A method executed at a computing device, the method comprising:

responsive to receiving a search query pertaining to a feature of interest in a scene, performing a search over a geospatial temporal semantic (GTS) graph for the feature of interest, wherein the GTS graph comprises;

nodes that represent objects captured in at least one of remote sensing data corresponding to the scene or a geolocation dataset, the nodes comprising a first node representing a first object, the first node assigned data that indicates that the first node corresponds to a trajectory, the trajectory comprising locations of the first object over a window of time; and

undirected edges, wherein each undirected edge in the undirected edges couples a respective pair of nodes in the nodes, the undirected edge assigned data that is indicative of a symmetric relationship between objects in the scene represented by nodes in the pair of nodes;

identifying the feature of interest in the scene based upon the search of the GTS graph; and

outputting data indicative of a location of the feature of interest in the scene.

12. The method of claim 11, wherein the search query comprises a graph template, the graph template having characteristics comprising:

a first number of nodes of a first type;

a second number of nodes of a second type; and

a first number of edges connecting pairs of nodes;

wherein identifying the feature of interest in the scene comprises identifying a subgraph of the GTS graph matching the characteristics of the graph template.

13. The method of claim 12, wherein nodes of the first type correspond to respective trajectories, the characteristics of the graph template further comprising a first edge connecting a node of the first type and a node of the second type, the first edge assigned data indicative of a distance relationship between the node of the first type and the node of the second type over a first window of time in the window of time.

14. The method of claim 13, wherein the distance relationship comprises a minimum distance between the node of the first type and the node of the second type over the first window of time.

15. A computer-readable storage medium comprising instructions that, when executed by at least one processor, causes the at least one processor to perform acts comprising:

responsive to receiving a search query pertaining to at least one of an entity or activity of interest in a scene, performing a search over a geospatial temporal semantic (GTS) graph for the at least one of the entity or activity in the scene, wherein the GTS graph comprises;

nodes that represent objects captured in at least one of remote sensing data corresponding to the scene or a geolocation dataset, the nodes comprising a first node representing a first object, the first node assigned data that indicates that the first node corresponds to a trajectory, the trajectory comprising locations of the first object over a window of time; and

undirected edges, wherein each undirected edge in the undirected edges couples a respective pair of nodes in the nodes, the undirected edge assigned data that is indicative of a symmetric relationship between objects in the scene represented by nodes in the pair of nodes;

identifying a location of the at least one of the entity or activity in the scene based upon the search of the GTS graph; and

outputting graphical data to a display indicating the location of the at least one of the entity or activity in the scene.

16. The computer-readable storage medium of claim 15, further comprising:

responsive to identifying the location of the at least one of the entity or activity in the scene, adding a second node to the GTS graph, the second node assigned data indicative of nodes and edges matching parameters of the search query.

17. The computer-readable storage medium of claim 15, wherein identifying the location of the at least one of the entity or activity in the scene comprises identifying match locations in the locations of the first object, the match locations matching parameters of the search query.

18. The computer-readable storage medium of claim 17, the acts further comprising:

responsive to identifying the match locations in the locations of the first object, adding a second node to the GTS graph, the second node assigned first data indicative of the match locations and second data indicative of the trajectory.

19. The computer-readable storage medium of claim 18, wherein the first data comprises a starting location and an ending location corresponding to the match locations.

20. The computer-readable storage medium of claim 15, wherein the search query comprises a graph search template.