Given a 2D numeric "height map" matrix in R, how can I find all local maxima?

4
votes

I have an R matrix with nonnegative numeric values. The matrix is effectively a 2D height map, and I want to find all the local maxima in this matrix. For "flat" peaks, where neighboring elements are equal to each other (and they are collectively a local maximum), I don't care what happens as long as I get at least one coordinate within each "flat" region.

Are there any functions to do this efficiently? Obviously I could write the loop manually to go through and test every element individually, but doing that in R would be quite slow. I need to do this for around a million matrices, with an average of about 884 elements per matrix.

Ideally there would be a function that takes the matrix as input and returns a 2-column matrix with column 1 being row coordinates, column 2 being the column coordinates, and one row for each local maximum in the matrix.

Local maxima on the edges of the matrix are allowed. Areas outside of the matrix can be treated as having zero height.

Reproducible example matrix to use:

set.seed(5)
msize <- 20 # Change this to whatever you like
x <- matrix(data=abs(rnorm(msize*2)), nrow=msize, ncol=msize)
1
rmatrixmax
Do two diagonally touching elements count as "neighboring" when it comes to defining a collective local maximum? Also, can you construct a relatively simple (e.g. 10x10 matrix) that folks can work off of? – Josh O'Brien
For diagonal elements, I don't really care whether or not they counts as neighbors, since if there are two (or more) equal-valued local maxima that are diaginal neighbors, I'm happy as long as I get at least one of them. I'll add a simple example matrix to work off of. – Ryan C. Thompson

1 Answers

12
votes

The focal() function in the raster package is designed for calculations like this. The following code returns coordinates of all local maxima, including those on edges and those that are parts of "plateaus ".

library(raster)

## Construct an example matrix
set.seed(444)
msize <- 10
x <- matrix(sample(seq_len(msize), msize^2, replace=TRUE), ncol=msize)

## Convert it to a raster object
r <- raster(x)
extent(r) <- extent(c(0, msize, 0, msize) + 0.5)

## Find the maximum value within the 9-cell neighborhood of each cell
f <- function(X) max(X, na.rm=TRUE)
ww <- matrix(1, nrow=3, ncol=3) ## Weight matrix for cells in moving window
localmax <- focal(r, fun=f, w=ww, pad=TRUE, padValue=NA)

## Does each cell have the maximum value in its neighborhood?
r2 <- r==localmax

## Get x-y coordinates of those cells that are local maxima
maxXY <- xyFromCell(r2, Which(r2==1, cells=TRUE))
head(maxXY)
#       x  y
# [1,]  8 10
# [2,] 10 10
# [3,]  3  9
# [4,]  4  9
# [5,]  1  8
# [6,]  6  8

# Visually inspect the data and the calculated local maxima
plot(r)   ## Plot of heights
windows() ## Open a second plotting device
plot(r2)  ## Plot showing local maxima