I need to develop an algorithm for finding all the local maxima in a two-dimensi
ID: 654353 • Letter: I
Question
I need to develop an algorithm for finding all the local maxima in a two-dimensional array: how to search for local maxima in the the most efficient way? Are there algorithms about it?
Moreover, the algorithm should be able to handle even the "flat" peaks, that is it should find the central coordinates of each peak. Here's an example with a one-dimensional array: some consecutive elements have the same peak value, so the algorithm should return the central location.
| flat peak |
|-----------------------|
array = [... 0.8 0.9 1.0 1.0 1.0 1.0 1.0 0.9 0.8 ...]
|
desired result
How to handle the problem of the flat peaks in a two-dimensional array? In the flat peaks, the neighbor elements are equal to each other and form a single local maximum, so I would like to get the central coordinates of this neighborhood.
Explanation / Answer
If you want to lump together neighbors with equal values, you can use a disjoint-set (aka union-find) datastructure to efficiently categorize sets of equivalent neighbors.
However, if your matrix values are floating point (as in your example), you should note that comparing floating point data for exact equality is almost always the wrong thing to do.
Finally, finding the "central coordinates" of a "flat peak" can be more complicated in a 2-dimensional array than in a 1-dimensional one. For example, the geometric center-of-mass of a C-shaped "flat peak" may not be near any of its actual members. Now, that may be what you want for a particular application -- or it may not.