什么是选择 C# 中最陡的局部最大值的好方法?

huangapple go评论57阅读模式
英文:

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:

什么是选择 C# 中最陡的局部最大值的好方法?

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:
什么是选择 C# 中最陡的局部最大值的好方法?
什么是选择 C# 中最陡的局部最大值的好方法?

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

How can I improve these results?

英文:

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:

什么是选择 C# 中最陡的局部最大值的好方法?

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&lt;Point&gt; 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&lt;Point&gt; pointList, int centerIndex)
    {
        double mag = 0;
        int halfAverageRange = averageRange / 2;
        for (int j = -halfAverageRange; j &lt; 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:
什么是选择 C# 中最陡的局部最大值的好方法?
什么是选择 C# 中最陡的局部最大值的好方法?

Note: Each consecutive points X value follows X=i, as in, X<sub>0</sub> = 0, X<sub>1</sub> = 1

How can I improve these results?

答案1

得分: 0

以下是代码部分的翻译:

private static void GetPeeks(List<int> points)
{
    var acc = ForwardIncrease(points);
    var dec = BackwardIncrease(points);

    var mul = new List<int>();

    for (int i = 0; i < acc.Count; i++)
    {
        mul.Add(acc[i] * dec[i]);
    }

    // 在mul中,最大值是峰值(极小值和极大值)
}

private static List<int> ForwardIncrease(List<int> points)
{
    var result = new List<int>();
    var previous = points[0];
    var cumul = 0;

    foreach (var point in points)
    {
        var diff = point - previous;

        if (diff >= 0 && cumul >= 0)
        {
            cumul += diff;
        }
        else if (diff <= 0 && cumul <= 0)
        {
            cumul += diff;
        }
        else
        {
            cumul = diff;
        }

        result.Add(cumul);
        previous = point;
    }

    return result;
}

private static List<int> BackwardIncrease(List<int> points)
{
    var result = new List<int>();
    var previous = points[points.Count - 1];
    var cumul = 0;

    for (int i = points.Count - 1; i >= 0; i--)
    {
        var point = points[i];
        var diff = point - previous;

        if (diff >= 0 && cumul >= 0)
        {
            cumul += diff;
        }
        else if (diff <= 0 && cumul <= 0)
        {
            cumul += diff;
        }
        else
        {
            cumul = diff;
        }

        result.Insert(0, cumul);
        previous = point;
    }

    return result;
}

这些是您提供的代码的翻译部分,不包括注释和说明。

英文:

I don't know if it will be useful, but this is a pretty straight-forward algorithm I've just coded. It is not math-based, you will definitely find counter-examples that won't work I'm afraid.

private static void GetPeeks(List&lt;int&gt; points)
{
    var acc = ForwardIncrease(points);
    var dec = BackwardIncrease(points);

    var mul = new List&lt;int&gt;();

    for (int i = 0; i &lt; acc.Count; i++)
    {
        mul.Add(acc[i] * dec[i]);
    }

    //in mul, greatest values are the peaks (minima and maxima)
}

private static List&lt;int&gt; ForwardIncrease(List&lt;int&gt; points)
{
    var result = new List&lt;int&gt;();
    var previous = points[0];
    var cumul = 0;

    foreach (var point in points)
    {
        var diff = point - previous;

        if (diff &gt;= 0 &amp;&amp; cumul &gt;= 0)
        {
            cumul += diff;
        }
        else if (diff &lt;= 0 &amp;&amp; cumul &lt;= 0)
        {
            cumul += diff;
        }
        else
        {
            cumul = diff;
        }

        result.Add(cumul);
        previous = point;
    }

    return result;
}

private static List&lt;int&gt; BackwardIncrease(List&lt;int&gt; points)
{
    var result = new List&lt;int&gt;();
    var previous = points[points.Count - 1];
    var cumul = 0;

    for (int i = points.Count - 1; i &gt;= 0; i--)
    {
        var point = points[i];
        var diff = point - previous;

        if (diff &gt;= 0 &amp;&amp; cumul &gt;= 0)
        {
            cumul += diff;
        }
        else if (diff &lt;= 0 &amp;&amp; cumul &lt;= 0)
        {
            cumul += diff;
        }
        else
        {
            cumul = diff;
        }

        result.Insert(0, cumul);
        previous = point;
    }

    return result;
}

答案2

得分: 0

首先,经过大量试验后,我相对容易地修复了这个问题。

首先,我确保在可能的情况下减少数据中的噪声,以获得更清晰的曲线,而不牺牲感兴趣的峰值的锐度(太多)。在我的情况下,我增加了极坐标图原始图像的模糊度。

其次,我采纳了@BenVoigt的建议,切换到使用二阶导数方程来计算曲线上各点的“锐度”。这提供了更准确的读数,适用于图表上的所有点。

然后,我从使用平均值转为使用中值平均值,这使图表更陡峭、更弯曲的部分具有明显更大的中值,从而使选择过程更加准确。

为了进行测试,我还减小了Y轴的刻度,以便更容易观察发生的情况,示例如下:什么是选择 C# 中最陡的局部最大值的好方法?

英文:

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:
什么是选择 C# 中最陡的局部最大值的好方法?

huangapple
  • 本文由 发表于 2023年3月3日 23:12:25
  • 转载请务必保留本文链接:https://go.coder-hub.com/75628795.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定