Attribute and topology based change detection in a constellation of previously detected objects
First Claim
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 onfor 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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17)
- comprising;
-
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. - View Dependent Claims (19)
-
Specification