How to find local maxima in matrices?

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.

Answer 1

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.

Answer 2

Determining whether a point is a local maximum is straightforward, just query its 4-neighborhood (or perhaps Moore neighborhood if you're concerned about saddle points). Return true if value is >= value of each neighbor.

Your "desired result" remark puts a slight wrinkle on this. You might choose to populate a new dst matrix from your src matrix. You could smooth out values with Gaussian blur or by sliding a window across the data for a moving average. Or consider identifying contour lines with ConRec or Marching Squares. Adding a little noise could leave you with a much simpler problem.

If you really want to operate on unmodified values, you'll need more than one pass. Fill dst matrix with zeros. Fill in one in positions corresponding to local maxima in your src matrix. Set color=2. Now scan the entire dst matrix from the top, looking for ones. As soon as you find a one, flood fill with color, increment color, then keep scanning. At the end you can see all the local maxima, each with a distinct color. Find the average (x,y) position of all color 2 values, and so on for each color.

You can do this with a single bit per source value. In first pass, set boolean dst values so they correspond to local maxima in src matrix. In second pass, scan for set bits, flood fill, clearing them, and compute average (x,y) during flood fill.