Attribute and topology based change detection in a constellation of previously detected objects

• US 9,239,382 B2
• Filed: 08/26/2011
• Issued: 01/19/2016
• Est. Priority Date: 08/26/2010
• Status: Active Grant

• Current Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Original Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Inventors: Paglieroni, David W., Beer, N. Reginald
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Gonzales, Vincent
• Application Number:
  US13/219,425
• Publication Number:
  US 20130085982A1
• Time in Patent Office: 1,607 Days
• Field of Search: 706/12, 706/62
• US Class Current: 1/1
• CPC Class Codes: G01S 13/003 Bistatic radar systems; Multistatic radar systems
• CPC Class Codes: G01S 13/885 for ground probing prospecting or detecting using electromagnetic waves G01V3/12
• CPC Class Codes: G01S 13/90 using synthetic aperture techniques , e.g. synthetic aperture radar [SAR] techniques
• CPC Class Codes: G01V 3/12 operating with electromagnetic waves operating with millimetre waves G01V8/005
• CPC Class Codes: G01V 3/15 specially adapted for use during transport, e.g. by a person, vehicle or boat
• CPC Class Codes: G06N 99/00 Subject matter not provided for in other groups of this subclass

Abstract

A system that applies attribute and topology based change detection to networks of objects that were detected on previous scans of a structure, roadway, or area of interest. The attributes capture properties or characteristics of the previously detected objects, such as location, time of detection, size, elongation, orientation, etc. The topology of the network of previously detected objects is maintained in a constellation database that stores attributes of previously detected objects and implicitly captures the geometrical structure of the network. A change detection system detects change by comparing the attributes and topology of new objects detected on the latest scan to the constellation database of previously detected objects.

Claims

1. A method in a computing device for determining whether a designated newly detected object represents an object that does not correspond to an object in a constellation of previously detected objects, the method comprising:

for each of a plurality of edge attributes, providing a likelihood function for generating a matching score indicating how well values for the edge attribute match;

selecting a root previously detected object and a root newly detected object as having a root correspondence;

calculating previous values for edge attributes for edges connecting the previously detected object to the root previously detected object from attributes of the previously detected objects;

calculating new values for edge attributes for edges connecting newly detected objects to the root newly detected object from attributes of the newly detected objects; and

indicating that the designated newly detected object is not a previously detected object based on

for each of a plurality of pairs of a previously detected object and a newly detected object,

for each edge attribute, generating a matching score using the provided likelihood function for the edge attribute to indicate how well the previous value of the edge attribute of the previously detected object of the pair and the new value of the edge attribute of the newly detected object of the pair match; and

combining the matching scores for the edge attributes into a combined matching score to indicate how well the previously detected object and the newly detected object of the pair match; and

applying a minimal cost assignment algorithm to costs derived from the combined matching scores to identify which newly detected objects correspond to which previously detected objects.

2. The method of claim 1 including generating a change index for the designated newly detected object indicating whether the designated newly detected object does not correspond to a previously detected object based on a minimum computed assignment costs to the previously detected objects.

3. The method of claim 2 wherein the change index is further based on fitness of detection of the object.

4. The method of claim 1 wherein the attributes of the objects are selected from a group consisting of location of the object, time the object was last detected, angle of long axis of the object, and length and width of the object.

5. The method of claim 1 wherein the edge attributes are selected from a group consisting of a pointing vector from a root detected object to a leaf detected object, difference in times of most recent detection of the root detected object and the leaf detected object, angle between long axis of the root or leaf detected object and vector from that root detected object to the leaf detected object, angle from a vector from the root detected object to a first leaf detected object to a vector from the root detected object to the leaf detected object, and angle between the long axis of the root detected object and the long axis of the leaf detected object.

6. A method in a computing device for determining whether a designated newly detected object represents an object that does not correspond to an object in a constellation of previously detected objects, the method comprising:

for each of a plurality of edge attributes, providing a likelihood function for the edge attribute;

selecting a root previously detected object and a root newly detected object as having a root correspondence;

calculating previous values for edge attributes for edges connecting the previously detected object to the root previously detected object from attributes of the previously detected objects;

calculating new values for edge attributes for edges connecting newly detected objects to the root newly detected object from attributes of the newly detected objects; and

indicating that the designated newly detected object is not a previously detected object based on

combining a likelihood for each edge attribute, the likelihood for an edge attribute generated by the likelihood function for that edge attribute applied to the previous value of that edge attribute given the new value of that edge attribute;

assigning a cost to pairs of a newly detected object and a previously detected object, the cost being derived from the detection fitnesses and combined likelihoods of the edge attributes that define topological consistency; and

applying a minimal cost assignment algorithm to the costs to identify possible correspondences between each newly detected object and a previously detected object.

7. The method of claim 6 including indicating a newly detected object corresponds to a previously detected object based on assignment of the minimal cost assignment algorithm.

8. A computer-readable medium that is not a transitory, propagating signal, the computer-readable medium storing computer-executable instructions for controlling a computing device to identify newly detected objects that correspond to previously detected objects, the computer-executable instructions implementing a method comprising:

providing values for edge attributes for edges connecting the previously detected objects to a root previously detected object;

providing values for edge attributes for edges connecting the newly detected objects to a root newly detected object;

for each of a plurality pairs of a previously detected object and a newly detected object, generating a score based on a likelihood that the previously detected object corresponds to the newly detected object, by;

for each edge attribute, generating a matching score using a likelihood function for the edge attribute to indicate how well the values of the edge attribute of the previously detected object and the newly detected object of the pair match; and

combining the matching scores for the edge attributes into a combined matching score to indicate how well the previously detected object and the newly detected object of the pair match; and

generating a mapping from newly detected objects to corresponding previously detected object based on the combined matching scores by applying a minimal cost assignment algorithm to costs represented by the combined matching scores

wherein each newly detected object that is mapped to a previously detected object indicates that the newly detected object corresponds to that previously detected object.

9. The computer-readable medium of claim 8 wherein when no previously detected object maps to a newly detected object, indicating that the newly detected object is not a previously detected object.

10. The computer-readable medium of claim 8 wherein selecting a root previously detected object and a root newly detected object as having a root correspondence includes for pairs of a previously detected object and a newly detected object, evaluating the objects of the pair as having a root correspondence by calculating a mapping efficiency indicating how well the newly detected object corresponds to the previously detected object based on locations of the other newly detected objects in a vicinity of a root object relative to locations of other previously detected objects in the vicinity of a root object.

11. The computer-readable medium of claim 8 wherein the objects are detected based on return signals acquired by receivers from ground-penetrating radar signals emitted by transmitters.

12. The computer-readable medium of claim 8 including prior to generating the scores, identifying a root previously detected object and a root newly detected object as having a root correspondence and wherein the generating of a score for a previously detected object and a newly detected object factors in location of the previously detected object relative to the root previously detected object and location of the newly detected object relative to the root newly detected object.

13. The computer-readable medium of claim 8 including prior to generating the scores, identifying a root previously detected object and a root newly detected object as having a root correspondence and wherein a score is not generated for pairs that include either the root previously detected object or the root newly detected object.

14. A computing device for identifying newly detected objects that do not correspond to previously detected objects;

comprising;

a computer-readable storage medium storing values for edge attributes for edges connecting the previously detected objects to a root previously detected object and values for edge attributes for edges connecting the newly detected objects to a root newly detected object;

a component that, for each of a plurality of pairs of a previously detected object and a newly detected object, generates a score based on a likelihood that the previously detected object corresponds to the newly detected object, by;

for each edge attribute, generating a matching score using a likelihood function for the edge attribute to indicate how well the values of the edge attribute of the previously detected object and the newly detected object of the pair match; and

combining the matching scores for the edge attributes into a combined matching score to indicate how well the previously detected object and the newly detected object of the pair match;

a component that applies a minimal cost assignment algorithm to costs represented by the combined matching scores to identify newly detected objects that correspond to previously detected objects; and

a component that, for each newly detected object that does not correspond to a previously detected object, indicating that the newly detected object does not correspond to a previously detected object.

15. The computing device of claim 14 including a component that

selects a root previously detected object and a root newly detected object as having a root correspondence;

calculates previous values for edge attributes for edges connecting the previously detected object to the root previously detected object from attributes of the previously detected objects;

calculates new values for edge attributes for edges connecting newly detected objects to the root newly detected object from attributes of the newly detected objects; and

generates the likelihood by combining a likelihood for each edge attribute, the likelihood for an edge attribute generated by the likelihood function for that edge attribute applied to the previous value of that edge attribute given the new value of that edge attribute.

16. The computing device of claim 15 wherein the component that selects a root previously detected object and a root newly detected object as having a root correspondence, for pairs of a previously detected object and a newly detected object, calculates a mapping efficiency indicating how well the newly detected object corresponds to the previously detected object based on locations of the other newly detected objects relative to locations of other previously detected objects.

17. The computing device of claim 16 wherein the objects are detected based on return signals acquired by receivers from ground-penetrating radar signals emitted by transmitters.

18. A method performed by a computing device for determining which objects in a first set of objects are the same objects in a second set of objects, comprising:

providing values for edge attributes for edges connecting the objects in the first set to a first root object of the first set;

providing values for edge attributes for edges connecting the objects in the second set to a second root object in the second set;

for pairs of objects that include an object in the first set and an object in the second set, generating a score indicating how well the objects of the pair match based on comparison of the values of the edge attributes of the objects, the score being generated by combining a likelihood score for each edge attribute, each likelihood score for an edge attribute generated by a likelihood function indicating a likelihood that the objects of the pair match based on the values for the edge attributes for the objects of the pair; and

applying a minimal cost assignment algorithm to costs derived from the scores to identify an assignment of objects in the first set to objects in the second set

wherein an object in the first set corresponds to an object in the second set when the minimal cost assignment algorithm assigns that object of the first set to that object of the second set, and

wherein the first set represents newly detected objects and the second set represents previously detected objects, and the first root object and the second root object are identified initially as best matching objects.

19. The method of claim 18 including prior to generating the scores, identifying a root object from the first set and a root object of the second set that are considered to be the same object, wherein the objects have locations and wherein attribute values for an object in the first set is based at least in part on location of the object relative to the root object of the first set and attribute values for an object in the second set is based at least in part on location of the object relative to the root object of the second set.