Searches over graphs representing geospatial-temporal remote sensing data

• US 9,911,039 B1
• Filed: 09/08/2015
• Issued: 03/06/2018
• Est. Priority Date: 09/08/2015
• Status: Active Grant

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Inventors: Brost, Randolph, Perkins, David Nikolaus
• Primary Examiner(s): Lee, Jonathan S
• Application Number:
  US14/848,169
• Time in Patent Office: 910 Days
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 20/176 Urban or other man-made structures

Abstract

Various technologies pertaining to identifying objects of interest in remote sensing images by searching over geospatial-temporal graph representations are described herein. Graphs are constructed by representing objects in remote sensing images as nodes, and connecting nodes with undirected edges representing either distance or adjacency relationships between objects and directed edges representing changes in time. Geospatial-temporal graph searches are made computationally efficient by taking advantage of characteristics of geospatial-temporal data in remote sensing images through the application of various graph search techniques.

Claims

1. A computing device comprising:

a processor; and

memory that comprises instructions that, when executed by the processor, cause the processor to perform acts comprising;

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

nodes that represent objects captured in a remote sensing image in the scene, wherein a first node in the nodes is assigned data indicating that the first node represents an object that is expected to change position over 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;

identifying a location of the activity in the scene based upon the search of the GST graph; and

outputting graphical data to a display indicating the location of activity in the scene.

2. The computing device of claim 1, wherein performing the search over the GST graph comprises performing a star graph search over the GST graph for the activity in the scene.

3. The computing device of claim 2, wherein performing the star graph search over the GST graph comprises performing the star graph search based upon a star graph search template, the star graph search template comprises:

a hub that identifies a type of object included a signature indicative of the activity; and

a spoke that identifies a second type of object included in the signature and further identifies a relationship between the hub and the spoke.

4. The computing device of claim 3, the star graph search template further comprises a plurality of spokes, each spoke identifies a respective type of object included in the signature and further identifies a relationship between the hub and each spoke.

5. The computing device of claim 4, wherein at least one spoke in the plurality of spokes is identified as being of a type of object that is optionally included in the signature.

6. The computing device of claim 3, the star graph search template further comprises a signature interrupt node, the signature interrupt node comprises a characteristic that is indicative of an acceptable interrupt between two nodes to allow for inferring that the nodes are representative of a single object.

7. The computing device of claim 3, wherein performing the star graph search over the GST graph further comprises searching the GST graph for a subgraph that conforms to the star graph search template.

8. The computing device of claim 2, wherein performing the search over the GST graph further comprises:

returning a plurality of search results based upon the star graph search, the plurality of search results comprising a sub-graph; and

responsive to returning the plurality of search results, filtering the sub-graph from the plurality of search results based upon a constraint assigned between spokes of the sub-graph.

9. The computing device of claim 1, wherein performing the search over the GST graph comprises performing a heterogeneous complex search over the GST graph.

10. The computing device of claim 9, wherein performing the heterogeneous complex search over the GST graph comprises:

executing a search over the GST graph based upon a heterogeneous complex signature, the heterogeneous complex signature comprises;

an identity of a first object type;

an identity of a second object type; and

a constraint pertaining to a relationship between an object of the first object type and an object of the second object type.

11. The computing device of claim 10, wherein the constraint pertaining to the relationship between the object of the first object type and the object of the second object type is at least one of:

a symmetric relationship constraint that constrains an acceptable symmetric relationship between the object of the first object type and the object of the second object type;

or

an asymmetric relationship constraint that constrains an acceptable asymmetric relationship between the object of the first object type and the object of the second object type.

19. The computing device of claim 1, wherein the first node is assigned data indicating that the first node represents a vehicle.

12. A method executed by a computer processor, the method comprising:

receiving a geospatial graph that is representative of objects in a scene depicted in a remote sensing image, the graph comprising;

nodes that represent objects captured in the remote sensing image, wherein each node is assigned data that indicates that the node is of a respective object type, wherein a first node in the nodes is assigned data that indicates that the first node represents a vehicle; and

undirected edges, wherein each undirected edge in the undirected edges couples a respective pair of nodes in the nodes, each 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;

receiving a query, the query comprises data that is indicative of an acceptable structure of sub-graphs in the geospatial graph;

performing at least one of a star graph search or a heterogeneous complex search over the geospatial graph based upon the query to identify a sub-graph that conforms to the acceptable structure of sub-graphs, wherein the sub-graph comprises the first node; and

outputting graphical data to a display based upon the sub-graph.

13. The method of claim 12, wherein the query comprises:

a hub that identifies a first object type;

a spoke that identifies a second object type; and

constraint data that defines a constraint between the hub and the spoke.

14. The method of claim 13, wherein the constraint data defines an acceptable distance range between an object of the first object type and an object of the second object type.

15. The method of claim 13, wherein the query further comprises at least one additional spoke, the at least one additional spoke identified as being optionally included in the sub-graph.

16. The method of claim 12, wherein the geospatial graph has temporal features encoded therein, and wherein the query is configured to identify an activity represented in the geospatial graph, the activity being movement of the vehicle.

17. The method of claim 12, wherein the query is configured in connection with performing the heterogeneous complex search.

18. A computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

executing a graph search over a geospatial temporal (GST) graph, the GST graph representative of objects in a scene including an object associated with activity in the scene, symmetric relationships between the objects in the scene, and asymmetric relationships between the objects in the scene, wherein the GST graph comprises a first node representative of a first object in the scene, the first node assigned data indicating that the first node represents an object that is expected to change position over time, wherein executing the graph search comprises identifying a sub-graph in the GST graph that corresponds to a sub-graph structure set forth in a query, the sub-graph structure comprising at least one of a star graph structure or a heterogeneous complex structure; and

outputting graphical data that is based upon the identified sub-graph in the GST graph.

20. The computing device of claim 18, wherein the object associated with activity is a vehicle.