Find the peak of each islands in sparse matrix

algorithm-analysisalgorithmsdata structuresmatrices

I have a sparse matrix that contains several islands of unknown size. I would like to find the highest peak of each islands. Consider this matrix as an example:

0 0 1 0 0 0 0
0 0 1 2 1 0 0
0 0 0 3 2 1 0
0 1 0 0 0 0 0
0 2 3 4 0 1 0
0 0 1 1 0 1 0
0 0 0 0 0 1 0

In this case I would like to get the position of 3 at (3, 2), the position of 4 at (3, 4) and the position of 1 at (5, 4), (5, 5) or (5, 6). Note: I consider 4-connected neighbours.

Until now I came up with the solution that scans each pixel and if it is not zero it starts a flood fill from that pixel. The flood fill paints the pixels to zero keeping track the maximum value visited. This algorithm works well but I was wondering if there are any faster solution?

In my target platform (iOS) I have access to different vector processing frameworks like BLAS, LAPACK, vDSP that provide some functions for fast finding the maximum value in a vector (or matrix). Maybe one could implement a faster solution with the help of these functions?

Best Answer

I once had to solve the exact same problem, as part of commercial image processing software. In the end I opted for a scan-line implementation, because it reads the matrix only once.

Basically, you consider a single row of the matrix and keep track of all 'events' on this scan line. Events are left and right edges of islands. Note that the same island might have multiple left and right edges on the same scan line. Also note that what seems to be 2 seperate islands on your scan line, might turn out to be the same island later.

You also keep a record of each known island with its highest value.

You start with the top row, initialize the events. And then go down one row at a time, each time revealing one more row of the matrix and updating the events. Next to updating the position of the existing events, you need consider also the following topology-changes:

  1. Start (top) of new land: a new island record, and new left and right edges are inserted in the scan line.
  2. End (bottom) of a piece of land: a left and right event are removed from the scan line.
  3. Top of a lake/sea: An island that splits into 2 seperate peninsulae of the same island (2 new events)
  4. Bottom of a lake/sea: two peninsulae merge into one. If they didn't already belong to the same island records, then these 2 island records need to be merged.
Related Topic