Point pattern match-based change detection in a constellation of previously detected objects

• US 9,361,352 B2
• Filed: 01/23/2013
• Issued: 06/07/2016
• Est. Priority Date: 08/26/2011
• 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.
• Primary Examiner(s): Sotomayor, John B
• Assistant Examiner(s): Windrich, Marcus
• Application Number:
  US13/748,447
• Publication Number:
  US 20140207810A1
• Time in Patent Office: 1,231 Days
• Field of Search: 342/22, 342 25 R- 25 F
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A method and system is provided that applies attribute- and topology-based change detection to objects that were detected on previous scans of a medium. The attributes capture properties or characteristics of the previously detected objects, such as location, time of detection, detection strength, size, elongation, orientation, etc. The locations define a three-dimensional network topology forming a constellation of previously detected objects. The change detection system stores attributes of the previously detected objects in a constellation database. The change detection system detects changes by comparing the attributes and topological consistency of newly detected objects encountered during a new scan of the medium to previously detected objects in the constellation database. The change detection system may receive the attributes of the newly detected objects as the objects are detected by an object detection system in real time.

Claims

1. A method in a computing device for matching a new constellation of newly detected objects to a previous constellation of previously detected objects, the method comprising:

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

generating a constellation offset based on a distance between the previously detected object and the newly detected object of the pair; and

generating a constellation matching score indicating a degree to which the new constellation matches the previous constellation assuming the constellation offset between the new constellation and the previous constellation and factoring in a probabilistic uncertainty model for the locations of the previously detected objects and the newly detected objects;

identifying the constellation matching score indicating the best match between the new constellation and the previous constellation; and

indicating that the constellation offset resulting in the identified constellation matching score as a best constellation offset for matching the new constellation with the previous constellation.

2. The method of claim 1 wherein generating the constellation matching score includes:

for each newly detected object, generating a best object matching score indicating a best match with a previously detected object; and

setting the constellation matching score based on the best object matching scores.

3. The method of claim 2 wherein the constellation matching score is set to an average of the best object matching scores.

4. The method of claim 2 wherein generating the best object matching score for a newly detected object includes:

for each previously detected object, generating an object matching score indicating a degree of match between the newly detected object and the previously detected object; and

selecting as the best object matching score the object matching score indicating the best match between the newly detected object and the previously detected object.

5. The method of claim 1 wherein the probability uncertainly model is based on a proximity likelihood.

6. The method of claim 5 wherein the proximity likelihood indicates a probability that the newly detected object matches a previously detected object based on the proximity of the objects.

7. The method of claim 1 wherein the constellation matching score factors in strength of detection for previously detected objects.

8. A computer-readable storage medium storing computer-executable instructions for controlling a computing device to detect a change in newly detected objects from previously detected objects, the computer-executable instructions implementing a method comprising:

for a newly detected object,

designating a new constellation to include newly detected objects within a match range of that newly detected object;

designating a previous constellation to include previously detected objects with the match range of the newly detected object;

matching the new constellation to the previous constellation to identify a best constellation offset based on constellation matching scores generated assuming different constellation offsets;

selecting as a matching object the previously detected object that best matches that newly detected object, factoring in a best constellation offset; and

generating a change statistic based on a comparison of values of an attribute of the matching object and the newly detected object.

9. The computer-readable storage medium of claim 8 wherein the change statistic is based on the difference between detection strength for the matching object from the constellation of previously detected objects and detection strength for the newly detected object divided by the detection strength for the matching object from the constellation of previously detected objects.

10. The computer-readable storage medium of claim 9 wherein the matching includes:

for each of a plurality of pairs that includes a previously detected object of the previous constellation and a newly detected object of the new constellation,

generating a constellation offset based on a distance between the previously detected object and the newly detected object of the pair; and

generating a constellation matching score indicating a degree to which the new constellation matches the previous constellation, factoring in the constellation offset between the new constellation and the previous constellation; and

identifying the constellation matching score that indicates the best match between the new constellation and the previous constellation; and

indicating that the constellation offset resulting in the identified point pattern matching score is the best constellation offset for matching the new constellation with the previous constellation.

11. The computer-readable storage medium of claim 9 wherein the matching is valid only when more than a threshold number of newly detected objects of the new constellation match the previously detected object in the previous constellation at the best constellation offset.

12. The computer-readable storage medium of claim 11 wherein a change is not detected until after a threshold number of newly detected objects result in valid constellation matches.

13. The computer-readable storage medium of claim 11 wherein the matching uses a nominal range of admissible offsets to exclude pairs of a newly detected object and a previously detected object as a basis for a constellation match and refines the range of admissible offsets based on the best constellation offset as matches for newly detected objects are found.

14. The computer-readable storage medium of claim 13 wherein the range of admissible offsets is updated based on the median and median deviation of the best constellation offsets for newly detected objects.

15. A computing device for updating a previous constellation of previously detected objects based on a constellation of newly detected objects, comprising:

a component that, for each of the newly detected objects, performs a first point pattern match between newly detected objects within a match range of that newly detected object and previously detected objects within a match range of that newly detected object, the first point pattern match being performed using a nominal range of admissible offsets to exclude pairs that include a newly detected object and a previously detected object as a basis for a point pattern match, each point pattern match generating a best constellation offset;

a component that refines the range of admissible offsets based on a statistical value derived from the best constellation offsets; and

a component that, for each of the newly detected objects, performs a second point pattern match between newly detected objects within a match range of the newly detected object and previously detected objects within a match range of the newly detected object, the point pattern match being performed using the refined range of admissible offsets to exclude pairs of a newly detected object and a previously detected object as a basis for a point pattern match; and

a component that updates the previous constellation based on the second point pattern matches.

16. The computing device of claim 15 wherein the components that perform a point pattern match,

for each of a plurality of pairs that include a previously detected object and a newly detected object that lie within the range of admissible offsets,

generate a constellation offset based on the range of admissible offsets between the previously detected object and the newly detected object of the pair;

and

generate a point pattern matching score indicating a degree to which newly detected objects within the match range match the previously detected object within the match range, factoring in the constellation offset;

identify the point pattern matching score indicating the best match; and

select the constellation offset resulting in the identified point pattern matching score being determined to be the best constellation offset.

17. The computing device of claim 16 wherein the component that generates the point pattern matching score,

for each newly detected object, generates a best object matching score indicating a best match with a previously detected object;

and

sets the point pattern matching score based on the best object matching scores.

18. The computing device of claim 17 wherein the component that generates the point pattern matching score sets the point pattern matching score to an average of the best object matching scores.

19. The computing device of claim 15 wherein the component that updates the previous constellation adds a newly detected object to the previous constellation when the second point pattern match indicates that the newly detected object has no correspondence in the previous constellation.

20. The computing device of claim 15 wherein the component that updates the previous constellation sets a value of an attribute of each previously detected object that has a matching newly detected object to an average of the values of the attribute for each detection of the previously detected object.

21. The computing device of claim 15 wherein the component that refines the range of admissible offsets updates the range of admissible offsets based on a median and median deviation of the best constellation offsets resulting from performing the first point pattern match.

22. A computer-readable storage medium storing computer-executable instructions for controlling a computing device to match a new constellation of newly detected objects to a previous constellation of previously detected objects, the computer executable instructions comprising:

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

generate a constellation offset based on a distance between the previously detected object and the newly detected object of the pair; and

generate a point pattern matching score indicating a degree to which the new constellation matches the previous constellation assuming the constellation offset between the new constellation and the previous constellation and factoring in strength of detection of the previously detected objects;

instructions that identify the point pattern matching score indicating the best match between the new constellation and the previous constellation; and

instructions that indicate that the constellation offset resulting in the identified point pattern matching score as a best constellation offset for matching the new constellation with the previous constellation.

23. The computer-readable storage medium of claim 22 wherein the instructions that generate the point pattern matching score include instructions that:

for each newly detected object, generate a best object matching score indicating a best match with a previously detected object; and

set the point pattern matching score based on the best object matching scores.

24. The computer-readable storage medium of claim 23 wherein the point pattern matching score is set to an average of the best object matching scores.

25. The computer-readable storage medium of claim 23 wherein the instructions that generate the best object matching score for a newly detected object include instructions that:

for each previously detected object, generate an object matching score indicating a degree of match between the newly detected object and the previously detected object; and

select as the best object matching score the object matching score indicating the best match between the newly detected object and the previously detected object.

26. The computer-readable storage medium of claim 22 wherein the point pattern matching score factors in a probabilistic uncertainty model for the locations of the previously detected objects and the newly detected objects.

27. The computer-readable storage medium of claim 26 wherein the probabilistic uncertainly model is based on a proximity likelihood.

28. The computer-readable storage medium of claim 27 wherein the proximity likelihood indicates a probability that the newly detected object matches a previously detected object based on the proximity of the objects.

29. A computer-readable storage medium storing computer-executable instructions for controlling a computing device to match a new constellation of newly detected objects to a previous constellation of previously detected objects, the computer executable instructions comprising:

instructions that, for each of a plurality of pairs that includes a previously detected object and a newly detected object for which the distance between the previously detected object and the newly detected object of the pair lies within a range of admissible offsets,

generate a constellation offset based on the distance; and

generate a point pattern matching score indicating the degree to which the new constellation matches the previous constellation assuming a constellation offset between the new constellation and the previous constellation and factoring in strength of detection for the previously detected objects;

instructions that identify the point pattern matching score indicating the best match between the new constellation and the previous constellation; and

instructions that indicate that the constellation offset resulting in the identified point pattern matching score as a best constellation offset for matching the new constellation with the previous constellation.

30. The computer-readable storage medium of claim 29 wherein the range of admissible offsets specifies that the distance is within a designated offset range.

31. The computer-readable storage medium of claim 29 wherein a relative uncertainty in location of previously detected objects is typically significantly smaller than the distance between the previously detected objects.

32. The computer-readable storage medium of claim 29 wherein by not generating a point pattern matching score for pairs that do not lie within the range of admissible offsets, the computational efficiency of matching the new constellation to a previous constellation can be reduced from 4th order polynomial time to a 3rd order polynomial time.