Vectorization approach to isolating local maxima in an N-dimensional dataset
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.
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.