Vectorization approach to isolating local maxima in an N-dimensional dataset

• US 9,041,586 B2
• Filed: 08/23/2012
• Issued: 05/26/2015
• Est. Priority Date: 08/23/2012
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Tarhan, Kurt K., Maxey, Gilbert C.
• Primary Examiner(s): Sotomayor, John B
• Application Number:
  US13/593,294
• Publication Number:
  US 20140056528A1
• Time in Patent Office: 1,006 Days
• Field of Search: 342 25 A- 25 F, 342/25.R
• US Class Current: 342/25.F
• CPC Class Codes: G01S 13/00 Systems using the reflection or reradiation of radio waves, e.g. radar systems; Analogous systems using reflection or reradiation of waves whose nature or wavelength is irrelevant or unspecified
• CPC Class Codes: G01S 13/90 using synthetic aperture techniques , e.g. synthetic aperture radar [SAR] techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: H04L 1/06 using space diversity

Abstract

Identification of maximum power scatters in an N-dimensional dataset generally requires two basic steps. The first step is to identify the max power scatters of the dataset and the second step removes neighboring power scatters (e.g., “hits”) of lower power. Current naïve approaches utilize an inefficient and computationally intensive brute force implementation which requires multiple comparisons of each initial “hit” power to all “hits” of lesser power. Such brute force implementations require 2×N×(M−1)! comparisons, where N is the number of dimensions and M is the number of “hits.” Embodiments of the present disclosure utilize vectorization to identify a plurality of neighboring hits for each max power scatter and removes the neighboring hits of lesser power that are within a predetermined isolation region. Advantageously, embodiments of the present invention perform M−1 comparisons.

Claims

1. A local maxima detection system, the system comprising:

an interface configured to receive at least one array of available candidate hits, each hit including a location in N dimensions and a power value, the array of candidate hits being sorted based on the power value;

a neighboring hits processor configured to, for each candidate hit of the array, identify a plurality of neighboring hits of the candidate hit in the array of available candidate hits;

a candidate hit removal processor configured to remove a subset of the plurality of neighboring hits within an isolation region about the candidate hit from the array of available candidate hits;

a vector collapsing processor configured to represent the location of the neighboring hits relative to the location of the candidate hit in a 1-dimensional location array;

a vector masking processor configured to generate a mask using a 1-dimensional description of at least the isolation region; and

the vector masking processor configured to apply the mask to the 1-dimensional location array, the mask removing neighboring hits within the isolation region about the candidate hit from the 1-dimensional location array and the array of available candidate hits.

2. The system of claim 1 wherein each available candidate hit represents a pixel described entirely by a location in at least two dimensions and the power value corresponds to an intensity.

3. The system of claim 1 wherein the neighboring hits processor is further configured to:

begin from the candidate hit having the greatest power value relative to the other candidate hits in the array of available candidate hits; and

identify a plurality of neighboring hits of the candidate.

4. The system of claim 1 further comprising a vector location processor configured to, for each of the N-dimensions of the neighboring hits, compute a vector representing a location of the neighboring hits relative to the location of the candidate hit.

5. The system of claim 1 further comprising a vector clipping processor configured to clip remaining neighboring hits to a clipping region about the candidate hit, the clipping region bordering the isolation region.

6. The system of claim 4 further comprising:

an absolute value vector converter configured to compute an absolute value of the N vectors representing the location of each of the neighboring hits relative to the candidate hit.

7. A method of maximum location detection, executed by an image processing system, the method comprising:

receiving at least one array of available candidate hits, each hit including a location in N dimensions and a power value, the array of candidate hits being sorted based on the power value;

for each candidate hit of the array, identifying a plurality of neighboring hits of the candidate hit in the array of available candidate hits;

removing a subset of the plurality of neighboring hits within an isolation region about the candidate hit from the array of available candidate hits;

representing the location of the neighboring hits relative to the location of the candidate hit in a 1-dimensional location array;

generating a mask using a 1-dimensional description of at least the isolation region; and

applying the mask to the 1-dimensional location array, the mask removing neighboring hits within the isolation region about the candidate hit from the 1-dimensional location array and the array of available candidate hits.

8. The method of claim 7 wherein each available candidate hit represents a pixel described entirely by a location in at least two dimensions and the power value corresponds to an intensity.

9. The method of claim 7 wherein identifying a plurality of neighboring hits of the candidate hit and removing the plurality of neighboring hits from the array of available candidate hits includes beginning from the candidate hit having the greatest power value relative to the other candidate hits in the array of available candidate hits.

10. The method of claim 7 further comprising for each of the N-dimensions of the neighboring hits, computing a vector representing a location of the neighboring hits relative to the location of the candidate hit.

11. The method of claim 7 further comprising:

clipping remaining neighboring hits to a clipping region about the candidate hit, the clipping region bordering the isolation region.

12. The method of claim 10 wherein removing the plurality of neighboring hits includes:

computing an absolute value of the N vectors representing the location of each of the neighboring hits relative to the candidate hit.