Search code examples
c#algorithmmaxima

What's a good way to select the steepest local maxima C#?

I'm trying to find the 4 steepest local maxima (corners of a piece) in a polar coordinate plot generated from a Jigsaw Piece, example plot:

Example Polar Coordinate Plot

My current implementation, which uses the same idea as this answer and works perfectly, but when combined with a "steepest peaks" function, does not work well, the issue most certainly lies in how a peak is measured for its "steepness".

Here is the "steepest peak" determining function, it returns a single number, smaller is better.

    public double GetMagnitude(List<Point> pointList, int centerIndex)
    {
        Point crrt = pointList[centerIndex];
        Point prev = pointList[centerIndex - 1];
        Point next = pointList[centerIndex + 1];

        Point rhs = new Point((next - crrt).x, (next - crrt).y);
        Point lhs = new Point((prev - crrt).x, (prev - crrt).y);

        // Calculate the gradient of the lhs against the rhs
        return Math.Abs((lhs.y - rhs.y) / (lhs.x - rhs.x));
    }

It's called like so (where averageRange is 20, and the number of sample points to take across the curve from the centerIndex)

    public double GetAverageMagnitude(List<Point> pointList, int centerIndex)
    {
        double mag = 0;
        int halfAverageRange = averageRange / 2;
        for (int j = -halfAverageRange; j < halfAverageRange; j++)
        {
            mag += GetMagnitude(pointList, centerIndex + j);
        }

        return mag / averageRange;
    }

The math at the end of the GetMagnitude() function could be entirely wrong, I have also tried:

  • Cross product of lhs against rhs
  • Separately calculating gradient of lhs and rhs and averaging them (absolute) No luck on any of those methods, the current one is the best so far, yet it's not good enough.

See example below for incorrect vs correct identification: Incorrect Identification Correct Identification

Note: Each consecutive points X value follows X=i, as in, X0 = 0, X1 = 1

How can I improve these results?

Solution

  • I managed to fix this relatively easy after lots of experimentation.

    Firstly, I made sure to reduce any noise in the data where possible, giving cleaner looking curves without sacrificing (too much) the sharpness of the peaks of interest. In my case, I increased the blur on the original image that the polar plot was made from.

    Secondly, I took @BenVoigt's advice and switched to using a second derivative equation for calculating the "sharpness" of points along the curve. This gave more accurate readings across all points on the graph.

    Then, I switched from using a mean average to a median average, this left the steeper, more curved parts of the graph with a distinctly greater median making the selection process much more accurate.

    To help with testing, I also decreased the scale of the Y axis to make it easier to see what was happening, example below: New Polar Plot