# US 7,613,673 B2 · Iterative particle reduction methods and systems for localization and pattern recognition

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

- Number: US 7,613,673 B2
- Document ID: US7613673B2
- Status: Granted
- Kind: B2
- Application number: 11/550,738
- Filed: 2006-10-18
- Published: 2008-06-26
- Granted: 2009-11-03
- Earliest claimed: 2006-10-18
- Assignees: The Boeing Company
- Inventors: David W. Payton; Scott D. G. Smith
- Web page: https://patentgrep.com/patent/US7613673B2

## CPC

- G06V 20/10: Terrestrial scenes (scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59)
- G06V 10/24: Aligning, centring, orientation detection or correction of the image
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

Systems and methods using iterative particle reduction for localization and pattern recognition are disclosed. In one embodiment, a method for localization of a plurality of sensor nodes includes establishing a set of particles representing candidate positions for the plurality of sensor nodes; iteratively reducing the set of particles using a plurality of particle reduction iterations, wherein each particle reduction iteration eliminates at least some particles based on at least one constraint and a set of remaining particles from a prior iteration; and after performing the plurality of particle reduction iterations, determining a set of probable locations of the plurality of sensor nodes based on a final set of particles.

## Claims

### Claim 1

A method for localization of a plurality of sensor nodes, comprising using a computing-based device to:
establish a set of particles representing candidate positions for the plurality of sensor nodes;
iteratively reduce the set of particles using one or more particle reduction iterations, wherein each particle reduction iteration other than an initial particle reduction iteration eliminates at least some particles based on at least one constraint and a set of remaining particles from a prior iteration; and
after performing the plurality of particle reduction iterations, determine a set of probable locations based on a final set of particles.

### Claim 2 (depends on 1)

The method of claim 1, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles until each particle of the set of remaining particles satisfies the at least one constraint.

### Claim 3 (depends on 1)

The method of claim 1, wherein iteratively reducing the set of particles using one or more particle reduction iterations includes iteratively reducing the set of particles by applying one or more particle reduction iterations with the same data to iteratively remove degrees of freedom from a final solution state.

### Claim 4 (depends on 1)

The method of claim 1, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles using a plurality of particle reduction iterations, wherein each particle reduction iteration includes:
applying one or more constraints to each particle; and
eliminating one or more particles that do not satisfy the one or more applied constraints.

### Claim 5 (depends on 4)

The method of claim 4, wherein applying one or more constraints to each particle includes applying a distance constraint to each particle.

### Claim 6 (depends on 1)

The method of claim 1, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles using a plurality of particle reduction iterations, wherein each particle reduction iteration includes a top-down process comprising:
selecting a highest-ranked particle for each a corresponding one of the sensor nodes;
selecting a subset of nodes that at least approximately satisfies one or more distance constraints to the highest-ranked particle;
removing all other particles corresponding to the corresponding one of the sensor nodes; and
performing an iterative bottom-up reduction process on each reduced particle set to obtain a unique solution.

### Claim 7 (depends on 6)

The method of claim 6, wherein each particle reduction iteration further includes:
scoring the unique solutions;
selecting a lowest scoring solution;
eliminating the highest-ranked particle that led to the lowest scoring solution; and
recording a highest scoring solution obtained for each of the particles in the unique solution.

### Claim 8 (depends on 1)

The method of claim 1, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles using a plurality of particle reduction iterations, wherein each particle reduction iteration includes performing a bottom-up reduction procedure comprising:
determining a probability for each particle, and
eliminating at least some of the particles having a relatively low probability; and
performing a top-down reduction procedure comprising:
selecting a highest-ranked particle for each sensor node;
selecting a subset of nodes that at least approximately satisfies one or more distance constraints to the highest-ranked particle;
removing all other particles corresponding to the corresponding one of the sensor nodes;
selecting a lowest scoring solution;
eliminating the highest-ranked particle that led to the lowest scoring solution; and
recording a highest scoring solution obtained for each of the particles.

### Claim 9 (depends on 8)

The method of claim 8, wherein determining a set of probable locations of the plurality of sensor nodes includes reconstructing the recorded particle sets having the highest scoring solutions.

### Claim 10 (depends on 1)

The method of claim 1, wherein
establishing a set of particles representing candidate positions for the plurality of sensor nodes includes assigning a set of probabilistic particles based on one or more factors for the plurality of sensor nodes; and
iteratively reducing the set of particles using one or more particle reduction iterations includes iteratively reducing the set of particles using one or more probabilistic particle reduction iterations, wherein each probabilistic particle reduction iteration includes:
assigning a probability score to each probalistic particle based on at least one of the one or more factors; and
eliminating at least one particle having a relatively low probability score.

### Claim 11 (depends on 10)

The method of claim 10, wherein assigning a set of probabilistic particles includes assigning a set of probabilistic particles based on one or more of:
an a priori probability based on a match between a particle self-indicated elevation and a measured elevation of the particle;
a distance between a particle and other particles for other sensor nodes; and
an a priori probability of the other particles for other sensor nodes.

### Claim 12 (depends on 10)

The method of claim 10, wherein iteratively reducing the set of particles using one or more probabilistic particle reduction iterations includes iteratively reducing the set of particles by applying one or more particle reduction iterations with the same data to iteratively remove degrees of freedom from a final solution state.

### Claim 13 (depends on 10)

The method of claim 10, wherein assigning a set of probabilistic particles includes:
for each individual particle of each individual sensor node, computing a pair-wise distance probability to each of the other remaining particles of the individual sensor node and all other sensor nodes;
multiplying each pair-wise distance probability by the individual particle's probability based on a correspondence to a pattern measurement to provide an intermediate probability; and
summing the intermediate probabilities to obtain a pair-wise net probability of the individual particle relative to all other particles of the individual sensor node.

### Claim 14 (depends on 1)

The method of claim 1, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles using one or more particle reduction iterations, wherein each particle reduction iteration includes both performing a bottom-up reduction procedure; and performing a top-down reduction procedure.

### Claim 15 (depends on 1)

The method of claim 1, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles using a plurality of particle reduction iterations, wherein each particle reduction iteration includes at least one of:
performing a bottom-up reduction procedure comprising determining a probability for each particle, and eliminating at least some of the particles having a relatively low probability; and
performing a top-down reduction procedure comprising selecting a highest-ranked particle for each sensor node; selecting a subset of nodes that at least approximately satisfies one or more distance constraints to the highest-ranked particle; removing all other particles corresponding to the corresponding one of the sensor nodes; selecting a lowest scoring solution; eliminating the highest-ranked particle that led to the lowest scoring solution; and recording a highest scoring solution obtained for each of the particles.

### Claim 16

A method for localization of a plurality of moveable nodes, comprising using a computing-based device to:
establish a set of particles representing candidate positions for the plurality of moveable nodes;
iteratively reduce the set of particles using one or more particle reduction iterations to provide a set of highest scoring particles, wherein each particle reduction iteration other than an initial particle reduction iteration eliminates at least some particles based on at least one constraint and a set of remaining particles from a prior iteration;
model a movement of the plurality of moveable nodes by establishing a set of moving particles;
iteratively reduce the set of moving particles using one or more moving particle reduction iterations to provide a final set of moving particles, wherein each moving particle reduction iteration other than an initial moving particle reduction iteration eliminates at least some moving particles based on at least one constraint and a set of remaining moving particles from a prior iteration; and
after performing the plurality of moving particle reduction iterations, determine a set of probable locations of the plurality of moveable nodes based on the final set of moving particles.

### Claim 17 (depends on 16)

The method of claim 16, wherein modeling a movement of the plurality of moveable nodes includes establishing a set of moving particles for each initial particle assuming that the moveable nodes move for a known distance in a different direction than the other moveable nodes.

### Claim 18 (depends on 16)

The method of claim 16, wherein iteratively reducing the set of moving particles includes iteratively reducing the set of moving particles using one or more moving particle reduction iterations, wherein each moving particle reduction iteration includes at least one of performing a bottom-up reduction procedure; and performing a top-down reduction procedure.

### Claim 19 (depends on 16)

The method of claim 16, wherein iteratively reducing the set of moving particles includes iteratively reducing the set of moving particles using one or more moving particle reduction iterations, wherein each moving particle reduction iteration includes at least one of:
performing a bottom-up reduction procedure comprising determining a probability for each moving particle, and eliminating at least some of the moving particles having a relatively low probability; and
performing a top-down reduction procedure comprising selecting a highest-ranked moving particle for each moveable node; selecting a subset of moveable nodes that at least approximately satisfies one or more distance constraints to the highest-ranked moving particle; removing all other moving particles corresponding to the corresponding one of the moveable nodes; selecting a lowest scoring solution; eliminating the highest-ranked moving particle that led to the lowest scoring solution; and recording a highest scoring solution obtained for each of the moving particles.

### Claim 20

A method of navigating at least one moveable device, comprising using a computing-based device to perform at least one of:
establishing a set of particles representing candidate positions for the at least one moveable device;
iteratively reducing the set of particles using one or more particle reduction iterations, wherein each particle reduction iteration other than an initial particle reduction iteration eliminates at least some particles based on at least one constraint and a set of remaining particles from a prior iteration;
after performing the plurality of particle reduction iterations, determining a probable location of the at least one moveable device based on a final set of particles.

### Claim 21 (depends on 20)

The method of claim 20, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles until each particle of the set of remaining particles satisfies the at least one constraint.

### Claim 22 (depends on 20)

The method of claim 20, wherein iteratively reducing the set of particles using one or more particle reduction iterations includes iteratively reducing the set of particles by applying one or more particle reduction iterations with the same data to iteratively remove degrees of freedom from a final solution state.

### Claim 23

A method comprising:
using a plurality of sensors to provide a plurality of measured values;
using the measured values to establish an initial set of particles representing candidate positions of the sensors; and
iteratively eliminating those particles that do not satisfy a distance-based constraint, including testing each particle to see whether there are companion particles corresponding to other sensors at the appropriate distances, and eliminating those particles that do not have corresponding sets of companion particles at appropriate distances.

### Claim 24 (depends on 23)

A system comprising the plurality of sensors of claim 23 and a computing-based device for using the measured values and performing the iterative elimination as recited in claim 23.

### Claim 25

An article comprising a computer readable medium encoded with data for causing a computing-based device to establish a set of particles representing candidate positions for a plurality of sensor nodes; iteratively reduce the set of particles using one or more particle reduction iterations, wherein each particle reduction iteration other than an initial particle reduction iteration eliminates at least some particles based on at least one constraint and a set of remaining particles from a prior iteration; and after performing the plurality of particle reduction iterations, determine a set of probable locations based on a final set of particles.

### Claim 26 (depends on 25)

The article of claim 25, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles using a plurality of particle reduction iterations, wherein each particle reduction iteration includes:
applying one or more constraints to each particle; and
eliminating one or more particles that do not satisfy the one or more applied constraints.

### Claim 27 (depends on 26)

The article of claim 26, wherein applying one or more constraints to each particle includes applying a distance constraint to each particle.

### Claim 28 (depends on 25)

The article of claim 25, wherein iteratively reducing the set of particles includes iteratively reducing the set of particles using a plurality of particle reduction iterations, wherein each particle reduction iteration includes a top- down process comprising:
selecting a highest-ranked particle for each a corresponding one of the sensor nodes;
selecting a subset of nodes that at least approximately satisfies one or more distance constraints to the highest-ranked particle;
removing all other particles corresponding to the corresponding one of the sensor nodes; and
performing an iterative bottom-up reduction process on each reduced particle set to obtain a unique solution.

### Claim 29 (depends on 25)

The article of claim 25, wherein
establishing a set of particles representing candidate positions for the plurality of sensor nodes includes assigning a set of probabilistic particles based on one or more factors for the plurality of sensor nodes; and
iteratively reducing the set of particles using one or more particle reduction iterations includes iteratively reducing the set of particles using one or more probabilistic particle reduction iterations, wherein each probabilistic particle reduction iteration includes:
assigning a probability score to each probalistic particle based on at least one of the one or more factors; and
eliminating at least one particle having a relatively low probability score.