CODEWITHSUNDEEP
algorithmmatrix
NeoWang
NeoWang

Reputation: 18563

What is an efficient algorithm to find all local minimums(maximums) in a matrix?

I want to find ALL local maximums in a N*N matrix, with a constraint that every 2 peaks found must be at least M cells away (in both directions). In other words, for very peak P found, local maximums within (2M+1)*(2M+1) sub-matrix around P are ignored, if that peak is lower than P.

By local maximum I mean the largest element in the (2M+1)*(2M+1) submatrix centered at the element.

For the naive method, the complexity is O(N*N*M*M). Is there an efficient algorithm to achieve this?

This is a sample matrix for N=5 and M=1 (3*3 grid):

enter image description here

Upvotes: 2

Views: 1790

Answers (2)

moooeeeep
moooeeeep

Reputation: 32542

As your matrix appears to be something like an image, using image processing techniques appears to be the natural choice.

You could define peaks (local maxima or minima) as image regions with zero crossing of both local partial derivatives. If you want maxima look for negative curvature at these places, if you're looking for minima watch out for positive curvature (curvature -> second order derivative).

There are linear convolution operators available (and a whole lot of theory behind them), that produce the partial derivatives in x and y direction (e.g., Sobel, Prewitt) and second order derivatives.

There's even algorithms for blob detection already, which appears to be related to your task (e.g., Laplacian of Gaussian).

If you are looking for speed, you might want to see if you can benefit of linear separability, precomputation of filter kernels (associativity), or DFT. Also note that this kind of tasks usually benefit hugely of parallelization. See if you can leverage more than one core, a GPU or an FPGA for some performance boost.

Upvotes: 2

Klas Lindbäck
Klas Lindbäck

Reputation: 33283

I would use a floodfill approach (it's not actually floodfill, but floodfill was what I had in mind when I came up with it):

  1. Find all minima. Put them in a sorted list/stack.
  2. Pick (and remove) the first item from the list (lowest minimum).
  3. If the element is marked as used, discard the item and go to 2.
  4. Mark all elements inside the submatrix around the item as used.
  5. Go to 2.

The algortihm ends when the list is empty.

Total cost: O(N*N + p * log p + p * M * M) where p is the number of minima.

Upvotes: 2

Related Questions