Find local maxima in grayscale image using OpenCV

Question

Does anybody know how to find the local maxima in a grayscale IPL_DEPTH_8U image using OpenCV? HarrisCorner mentions something like that but I'm actually not interested in corners ... Thanks!

Solution 1

I think you want to use the

MinMaxLoc(arr, mask=NULL)-> (minVal, maxVal, minLoc, maxLoc)
Finds global minimum and maximum in array or subarray

function on you image

Solution 2

A pixel is considered a local maximum if it is equal to the maximum value in a 'local' neighborhood. The function below captures this property in two lines of code.

To deal with pixels on 'plateaus' (value equal to their neighborhood) one can use the local minimum property, since plateaus pixels are equal to their local minimum. The rest of the code filters out those pixels.

void non_maxima_suppression(const cv::Mat& image, cv::Mat& mask, bool remove_plateaus) {
    // find pixels that are equal to the local neighborhood not maximum (including 'plateaus')
    cv::dilate(image, mask, cv::Mat());
    cv::compare(image, mask, mask, cv::CMP_GE);

    // optionally filter out pixels that are equal to the local minimum ('plateaus')
    if (remove_plateaus) {
        cv::Mat non_plateau_mask;
        cv::erode(image, non_plateau_mask, cv::Mat());
        cv::compare(image, non_plateau_mask, non_plateau_mask, cv::CMP_GT);
        cv::bitwise_and(mask, non_plateau_mask, mask);
    }
}

Solution 3

Here's a simple trick. The idea is to dilate with a kernel that contains a hole in the center. After the dilate operation, each pixel is replaced with the maximum of it's neighbors (using a 5 by 5 neighborhood in this example), excluding the original pixel.

Mat1b kernelLM(Size(5, 5), 1u);
kernelLM.at<uchar>(2, 2) = 0u;
Mat imageLM;
dilate(image, imageLM, kernelLM);
Mat1b localMaxima = (image > imageLM);

Solution 4

Actually after I posted the code above I wrote a better and very very faster one .. The code above suffers even for a 640x480 picture.. I optimized it and now it is very very fast even for 1600x1200 pic. Here is the code :

void localMaxima(cv::Mat src,cv::Mat &dst,int squareSize)
{
if (squareSize==0)
{
    dst = src.clone();
    return;
}

Mat m0;
dst = src.clone();
Point maxLoc(0,0);

//1.Be sure to have at least 3x3 for at least looking at 1 pixel close neighbours
//  Also the window must be <odd>x<odd>
SANITYCHECK(squareSize,3,1);
int sqrCenter = (squareSize-1)/2;

//2.Create the localWindow mask to get things done faster
//  When we find a local maxima we will multiply the subwindow with this MASK
//  So that we will not search for those 0 values again and again
Mat localWindowMask = Mat::zeros(Size(squareSize,squareSize),CV_8U);//boolean
localWindowMask.at<unsigned char>(sqrCenter,sqrCenter)=1;

//3.Find the threshold value to threshold the image
    //this function here returns the peak of histogram of picture
    //the picture is a thresholded picture it will have a lot of zero values in it
    //so that the second boolean variable says :
    //  (boolean) ? "return peak even if it is at 0" : "return peak discarding 0"
int thrshld =  maxUsedValInHistogramData(dst,false);
threshold(dst,m0,thrshld,1,THRESH_BINARY);

//4.Now delete all thresholded values from picture
dst = dst.mul(m0);

//put the src in the middle of the big array
for (int row=sqrCenter;row<dst.size().height-sqrCenter;row++)
    for (int col=sqrCenter;col<dst.size().width-sqrCenter;col++)
    {
        //1.if the value is zero it can not be a local maxima
        if (dst.at<unsigned char>(row,col)==0)
            continue;
        //2.the value at (row,col) is not 0 so it can be a local maxima point
        m0 =  dst.colRange(col-sqrCenter,col+sqrCenter+1).rowRange(row-sqrCenter,row+sqrCenter+1);
        minMaxLoc(m0,NULL,NULL,NULL,&maxLoc);
        //if the maximum location of this subWindow is at center
        //it means we found the local maxima
        //so we should delete the surrounding values which lies in the subWindow area
        //hence we will not try to find if a point is at localMaxima when already found a neighbour was
        if ((maxLoc.x==sqrCenter)&&(maxLoc.y==sqrCenter))
        {
            m0 = m0.mul(localWindowMask);
                            //we can skip the values that we already made 0 by the above function
            col+=sqrCenter;
        }
    }
}

Solution 5

The following listing is a function similar to Matlab's "imregionalmax". It looks for at most nLocMax local maxima above threshold, where the found local maxima are at least minDistBtwLocMax pixels apart. It returns the actual number of local maxima found. Notice that it uses OpenCV's minMaxLoc to find global maxima. It is "opencv-self-contained" except for the (easy to implement) function vdist, which computes the (euclidian) distance between points (r,c) and (row,col).

input is one-channel CV_32F matrix, and locations is nLocMax (rows) by 2 (columns) CV_32S matrix.

int imregionalmax(Mat input, int nLocMax, float threshold, float minDistBtwLocMax, Mat locations)
{
    Mat scratch = input.clone();
    int nFoundLocMax = 0;
    for (int i = 0; i < nLocMax; i++) {
        Point location;
        double maxVal;
        minMaxLoc(scratch, NULL, &maxVal, NULL, &location);
        if (maxVal > threshold) {
            nFoundLocMax += 1;
            int row = location.y;
            int col = location.x;
            locations.at<int>(i,0) = row;
            locations.at<int>(i,1) = col;
            int r0 = (row-minDistBtwLocMax > -1 ? row-minDistBtwLocMax : 0);
            int r1 = (row+minDistBtwLocMax < scratch.rows ? row+minDistBtwLocMax : scratch.rows-1);
            int c0 = (col-minDistBtwLocMax > -1 ? col-minDistBtwLocMax : 0);
            int c1 = (col+minDistBtwLocMax < scratch.cols ? col+minDistBtwLocMax : scratch.cols-1);
            for (int r = r0; r <= r1; r++) {
                for (int c = c0; c <= c1; c++) {
                    if (vdist(Point2DMake(r, c),Point2DMake(row, col)) <= minDistBtwLocMax) {
                        scratch.at<float>(r,c) = 0.0;
                    }
                }
            }
        } else {
            break;
        }
    }
    return nFoundLocMax;
}

View more solutions

Comments

[AruniRC]

Doesn't the morphology Dilation operation in OpenCV find out the local maxima in a 3x3 or a user-defined kernel and set the pixels to this max value? So this could be modified to your purpose.

[Durin]

actually that looks for the global. I'd prefer local (regional) like Matlab's imregionmax() function.

[peakxu]

You can use cvSetImageROI and cvResetImageROI calls to define the subregion over which you're searching. Then, fabrizio's suggestion would work just fine.

[Coding Mash]

you can always edit your own post and even if you two answers, you can post them separately.

[Doga Siyli]

I just realized that :) thanks for the tip.. but is it possible to delete the one above?

[Coding Mash]

A moderator can delete that. You can flag it for a moderator to consider.

[Doga Siyli]

awesome.. thanks a ton..but although I can flag this one the other post doesn't have a flag option below :(

[John Demetriou]

@DogaSiyli what is SANITYCHECK?

[John Demetriou]

it only gives negative X and Y

[TimZaman]

Before running this function, consider blurring the image if you would like to obtain local peaks.

[TimZaman]

This code gives 'connected' results, which is weird since we are looking for local maxima; two maxima cannot be connected if you ask me. Even if i increase the kernel size.

[TimZaman]

Although the idea is good and fast, your code doesn't work for features located at the bottom and right edges of the image. This is possibly because your pProcess[m++] will not get to the bottom and right edges, and if the threshold has not been triggered, it will not give a result, while near those edges the threshold might indeed be higher, but it will never trigger. The solution here is to increase the SearchWidth and searchHeight and then to some sanitation on your crop rectangle.

[G453]

+1 for making a function with all possible options like distance btw max, no. of max, threshold values etc. Haven't looked into the computations efficiency yet. Will let u know if there are any issues related to that.

[Ben]

@peakxu It's actually not that easy use the global MinMaxLoc function to find local extrema in combination with some ROI. How do you set the subregion? In a sliding window manner? MinMaxLoc will always return a minimum and maximum. A border pixel in the ROI might be a global maximum within the ROI, but the next pixel outside the ROI might have an even larger value.

[Ben]

see my comment in the accepted answer. This method is not working. Consider an 100x100 image with greyvalue(x,y) = x+y. There is only one maximum at [99,99]. A sliding window would always find a local maximum in the lower right corner. Your method would basically return almost every pixel as a local maximum.

[ed22]

Where are "vdist" and "Point2DMake" from?

[Pieter Meiresone]

You have to implement those yourself.

[Doerthous]

what if one neighbor has the same maximum value?