# US 2014/0207810 A1 · Point pattern match-based change detection in a constellation of previously detected objects

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0207810 A1
- Document ID: US20140207810A1
- Status: Published application
- Kind: A1
- Application number: 13/748,447
- Filed: 2013-01-23
- Published: 2014-07-24
- Earliest claimed: 2013-01-23
- Assignees: Lawrence Livermore National Security, LLC
- Inventors: David W. Paglieroni
- Web page: https://patentgrep.com/patent/US20140207810A1

## CPC

- G06F 16/283: {Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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 point pattern matching score indicating a degree to which the new point pattern matches the previous constellation assuming a 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 point pattern matching score indicating 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 as a best constellation offset for matching the new constellation with the previous constellation.

### Claim 2 (depends on 1)

The method of claim 1 wherein generating the point pattern 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 point pattern matching score based on the best object matching scores.

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 2)

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.

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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

### Claim 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;
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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 9)

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 point pattern matching score indicating a degree to which the new point pattern matches the previous constellation, factoring in the constellation offset between the new constellation and the previous constellation; and
identifying the point pattern 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.

### Claim 11 (depends on 9)

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 point pattern match the previously detected object in the previous constellation at the best constellation offset.

### Claim 12 (depends on 11)

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 point pattern matches.

### Claim 13 (depends on 11)

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 point pattern match and refines the range of admissible offsets based on the best constellation offset as matches for newly detected objects are found.

### Claim 14 (depends on 13)

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.

### Claim 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 the offsets for the best constellation matches; 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 15)

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.

### Claim 20 (depends on 15)

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.

### Claim 21 (depends on 15)

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.

### Claim 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 point pattern matching score indicating a degree to which the new point pattern matches the previous constellation assuming a 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.

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 23)

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.

### Claim 25 (depends on 23)

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
selects as the best object matching score the object matching score indicating the best match between the newly detected object and the previously detected object.

### Claim 26 (depends on 22)

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.

### Claim 27 (depends on 26)

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

### Claim 28 (depends on 27)

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.

### Claim 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 the 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 point pattern 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.

### Claim 30 (depends on 29)

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

### Claim 31 (depends on 29)

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.

### Claim 32 (depends on 29)

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.
