Peak Search Algorithm with sliding window and peak excursion
-
Dear coder/Mathematician folk, I have a question on how to best peak search a series of noise like points. The points are stored as doubles in a double array. The points represent voltage levels in dBuV. I'm not a mathematician and I have limited knowledge regarding the elegancie's of how C# can be put to handle complex problems. Or maybe not so complex to some :) I would like 'n' points returning that have a delta from there neighbours of >= 6dB and within a specified window of 'm' points. The window allows us to reject all peaks regardless of delta bar the point with the highest peak. As we go through the data points we look at each point [DP] with respect to its neighbour. If the delta to left neighbour [P1] is >= 6dB and delta to right neighbour [P2] is >= 6dB we have a peak. if either neighbours delta is less than 6dB we may have a slope condition. We must there for ride the slope with respect to [P2] goint up and down the troughs until we hit a transition and the delta from [P2] is >= 6dB. This would be our next point. We repeat the process though all points returning just the peaks that are separated by the window width and have clear >= 6dB margin from there neighbours. The following data represents a typical trace. Only points 9,11, and 24 are real points that should be returnd.
double[] trace = new double[] {47.92370605,44,49,46.31715393,44.98129654,46.17653275,78,73,82,63,69,41.72979736,41.13000488,41.49586487,37,40,30,40.79894257,40.65593719,41.37298584,39.13498688,55,51,60,39.3440094,38.51491547,42,35.12589264};
I hope I explained things clearly. Please feel free to ask for any clarifications :) Many thanks for your time and effort Nigel
-
Dear coder/Mathematician folk, I have a question on how to best peak search a series of noise like points. The points are stored as doubles in a double array. The points represent voltage levels in dBuV. I'm not a mathematician and I have limited knowledge regarding the elegancie's of how C# can be put to handle complex problems. Or maybe not so complex to some :) I would like 'n' points returning that have a delta from there neighbours of >= 6dB and within a specified window of 'm' points. The window allows us to reject all peaks regardless of delta bar the point with the highest peak. As we go through the data points we look at each point [DP] with respect to its neighbour. If the delta to left neighbour [P1] is >= 6dB and delta to right neighbour [P2] is >= 6dB we have a peak. if either neighbours delta is less than 6dB we may have a slope condition. We must there for ride the slope with respect to [P2] goint up and down the troughs until we hit a transition and the delta from [P2] is >= 6dB. This would be our next point. We repeat the process though all points returning just the peaks that are separated by the window width and have clear >= 6dB margin from there neighbours. The following data represents a typical trace. Only points 9,11, and 24 are real points that should be returnd.
double[] trace = new double[] {47.92370605,44,49,46.31715393,44.98129654,46.17653275,78,73,82,63,69,41.72979736,41.13000488,41.49586487,37,40,30,40.79894257,40.65593719,41.37298584,39.13498688,55,51,60,39.3440094,38.51491547,42,35.12589264};
I hope I explained things clearly. Please feel free to ask for any clarifications :) Many thanks for your time and effort Nigel
So, what code do you have so far? What is the problem that you are trying to solve (e.g., is your logic too slow)?
This space for rent
-
Dear coder/Mathematician folk, I have a question on how to best peak search a series of noise like points. The points are stored as doubles in a double array. The points represent voltage levels in dBuV. I'm not a mathematician and I have limited knowledge regarding the elegancie's of how C# can be put to handle complex problems. Or maybe not so complex to some :) I would like 'n' points returning that have a delta from there neighbours of >= 6dB and within a specified window of 'm' points. The window allows us to reject all peaks regardless of delta bar the point with the highest peak. As we go through the data points we look at each point [DP] with respect to its neighbour. If the delta to left neighbour [P1] is >= 6dB and delta to right neighbour [P2] is >= 6dB we have a peak. if either neighbours delta is less than 6dB we may have a slope condition. We must there for ride the slope with respect to [P2] goint up and down the troughs until we hit a transition and the delta from [P2] is >= 6dB. This would be our next point. We repeat the process though all points returning just the peaks that are separated by the window width and have clear >= 6dB margin from there neighbours. The following data represents a typical trace. Only points 9,11, and 24 are real points that should be returnd.
double[] trace = new double[] {47.92370605,44,49,46.31715393,44.98129654,46.17653275,78,73,82,63,69,41.72979736,41.13000488,41.49586487,37,40,30,40.79894257,40.65593719,41.37298584,39.13498688,55,51,60,39.3440094,38.51491547,42,35.12589264};
I hope I explained things clearly. Please feel free to ask for any clarifications :) Many thanks for your time and effort Nigel
Sounds like you just need to loop through the array, doing a single check for each item?
Member 12616185 wrote:
The following data represents a typical trace. Only points 9,11, and 24 are real points that should be returnd.
Hehe, so you are requesting code? :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]
-
So, what code do you have so far? What is the problem that you are trying to solve (e.g., is your logic too slow)?
This space for rent
Hi Pete, Thanks for getting back to me, I have a modified peak search function that returns peak/troughs.
public static IEnumerable> LocalPeakMinMax(IEnumerable source, int windowSize)
{
if (windowSize < 2) windowSize = 2;windowSize = windowSize - windowSize % 2 + 1; int halfWindow = windowSize / 2; int index = 0; var before = new Queue(Enumerable.Repeat(double.NegativeInfinity, halfWindow)); var after = new Queue(source.Take(halfWindow + 1)); foreach (double d in source.Skip(halfWindow + 1).Concat(Enumerable.Repeat(double.NegativeInfinity, halfWindow + 1))) { double curVal = after.Dequeue(); if (before.All(x => curVal > x ) && after.All(x => curVal >= x )) { yield return Tuple.Create(index, curVal); } else if (before.All(x => curVal <= x) && after.All(x => curVal < x)) { yield return Tuple.Create(index, curVal); } before.Dequeue(); before.Enqueue(curVal); after.Enqueue(d); index++; } }The problem is I cannot figure out how best to filter out all the chaff and return the peaks that align with the prescribed logic explained in my original post. I was going to take the output from this and play with it but it was getting messy. I was hoping the community may be able to come up with a more elegant solution. The code isn't slow at all, quite the opposite. At least with the 625 points i'm currently playing with. Br Nigel
-
Sounds like you just need to loop through the array, doing a single check for each item?
Member 12616185 wrote:
The following data represents a typical trace. Only points 9,11, and 24 are real points that should be returnd.
Hehe, so you are requesting code? :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]
Hi Eddy, I have code that returns the peaks and troughs but not the window/peak excursion implementation. I was hoping there would be an elegant way to do this in maybe linq. I posted my current code in a previous reply. It returns the peaks and troughs. I could post process this in a bunch of loops but it was getting messy so I decided to request help from the Brain, AKA codeproject c# forum :) Kind Regards Nigel
-
Hi Eddy, I have code that returns the peaks and troughs but not the window/peak excursion implementation. I was hoping there would be an elegant way to do this in maybe linq. I posted my current code in a previous reply. It returns the peaks and troughs. I could post process this in a bunch of loops but it was getting messy so I decided to request help from the Brain, AKA codeproject c# forum :) Kind Regards Nigel
-
Your spot on with that assessment :) LINQ isn't everything, and by elegant I meant not done with a 100 for/if loops etc. If it can be done in LINQ then great :). I'm just blowing my brain trying to conceptualise the best way of doing this in code. Br Nigel
-
Your spot on with that assessment :) LINQ isn't everything, and by elegant I meant not done with a 100 for/if loops etc. If it can be done in LINQ then great :). I'm just blowing my brain trying to conceptualise the best way of doing this in code. Br Nigel
Nigel_Davison wrote:
LINQ isn't everything, and by elegant I meant not done with a 100 for/if loops etc.
LINQ will do the same, just in another form of notation. If you need to inspect a list of values, a loop will be somewhere. Also doesn't look like you have that much loops/branches yet. If it works, it works :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]
-
Nigel_Davison wrote:
LINQ isn't everything, and by elegant I meant not done with a 100 for/if loops etc.
LINQ will do the same, just in another form of notation. If you need to inspect a list of values, a loop will be somewhere. Also doesn't look like you have that much loops/branches yet. If it works, it works :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]
Hey Eddy >> "Also doesn't look like you have that much loops/branches yet" Yes, but the code I posted only retrieves the peak maxima/minima. It doesn't respect the 6dB peak excursion requirement. >> "If it works, it works" Couldn't have put it better myself :) Br Nigel
-
Hey Eddy >> "Also doesn't look like you have that much loops/branches yet" Yes, but the code I posted only retrieves the peak maxima/minima. It doesn't respect the 6dB peak excursion requirement. >> "If it works, it works" Couldn't have put it better myself :) Br Nigel
Krellon wrote:
It doesn't respect the 6dB peak excursion requirement.
Did you mean "exclusion"? Given the list you return, which (simple) steps should I do on paper to satisfy your requirement? I was assuming you'd just check the previous and following values and add them to a list of the delta is bigger than 6 doorbells. The simpeler the explanation, the simpeler the code (usually) :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]
-
Hi Pete, Thanks for getting back to me, I have a modified peak search function that returns peak/troughs.
public static IEnumerable> LocalPeakMinMax(IEnumerable source, int windowSize)
{
if (windowSize < 2) windowSize = 2;windowSize = windowSize - windowSize % 2 + 1; int halfWindow = windowSize / 2; int index = 0; var before = new Queue(Enumerable.Repeat(double.NegativeInfinity, halfWindow)); var after = new Queue(source.Take(halfWindow + 1)); foreach (double d in source.Skip(halfWindow + 1).Concat(Enumerable.Repeat(double.NegativeInfinity, halfWindow + 1))) { double curVal = after.Dequeue(); if (before.All(x => curVal > x ) && after.All(x => curVal >= x )) { yield return Tuple.Create(index, curVal); } else if (before.All(x => curVal <= x) && after.All(x => curVal < x)) { yield return Tuple.Create(index, curVal); } before.Dequeue(); before.Enqueue(curVal); after.Enqueue(d); index++; } }The problem is I cannot figure out how best to filter out all the chaff and return the peaks that align with the prescribed logic explained in my original post. I was going to take the output from this and play with it but it was getting messy. I was hoping the community may be able to come up with a more elegant solution. The code isn't slow at all, quite the opposite. At least with the 625 points i'm currently playing with. Br Nigel
Searching for peaks, and using your example here, the following code gives you the results you expect:
double[] trace =
{
47.92370605, 44, 49, 46.31715393, 44.98129654, 46.17653275, 78, 73, 82, 63, 69, 41.72979736, 41.13000488,
41.49586487, 37, 40, 30, 40.79894257, 40.65593719, 41.37298584, 39.13498688, 55, 51, 60, 39.3440094,
38.51491547, 42, 35.12589264
};
for (int i = 1; i < trace.Length - 1; i++)
{
double deltaLeft = trace[i - 1];
double deltaRight = trace[i + 1];if (trace[i] - deltaLeft >= 6 && trace[i] - deltaRight >= 6)
{
Console.WriteLine($"Peak at {i + 1}");
}
}You may notice that I don't start at 0 and I don't finish at the last element in the array; as it's assumed that you will always have a left and right value, this is sufficient.
This space for rent
-
Krellon wrote:
It doesn't respect the 6dB peak excursion requirement.
Did you mean "exclusion"? Given the list you return, which (simple) steps should I do on paper to satisfy your requirement? I was assuming you'd just check the previous and following values and add them to a list of the delta is bigger than 6 doorbells. The simpeler the explanation, the simpeler the code (usually) :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]
Hi Eddy, If you stick the following data into Excel and plot it. Then place markers on the 9th 11th and 24th point you would see what I was after.
double[] trace = new double[] { 47.92370605, 44, 49, 46.31715393, 44.98129654, 46.17653275, 78, 73, 82, 63, 69, 41.72979736, 41.13000488, 41.49586487, 37, 40, 30, 40.79894257, 40.65593719, 41.37298584, 39.13498688, 55, 51, 60, 39.3440094, 38.51491547, 42, 35.12589264 };
If I could embed an image into my comment I would show you. Your essentially looping through an array of points looking for the biggest and smallest peaks and waiting for the delta either side them to go >= 6dB. When it does you grab the biggest peak between the -6dB points. Rinse and repeat. So, 1,6,3,7,1 would yield a peak at p[4] = 7 with a window size of 5. 1,7,1 would yield a peak at p[2] = 7 with a window size of 3. 1,-3,-2,7,5,1 would yield a peak at p[4] = 7 with a window size of 4. 1,-7,1,-6 would yield 2 peaks. One at p[1] = 1 with a window size if 2 and one at p[3] with a window size of 3. stick them all together and you get 1,6,3,7,1,1,7,1,1,-3,-2,7,5,1,1,-7,1,-6 Peaks at p[4], p[7], p[12] and p[17] Respective window sizes in points would be, 5, 3, 4 and 3 :) Hope that's helps :| Br Nigel
-
Searching for peaks, and using your example here, the following code gives you the results you expect:
double[] trace =
{
47.92370605, 44, 49, 46.31715393, 44.98129654, 46.17653275, 78, 73, 82, 63, 69, 41.72979736, 41.13000488,
41.49586487, 37, 40, 30, 40.79894257, 40.65593719, 41.37298584, 39.13498688, 55, 51, 60, 39.3440094,
38.51491547, 42, 35.12589264
};
for (int i = 1; i < trace.Length - 1; i++)
{
double deltaLeft = trace[i - 1];
double deltaRight = trace[i + 1];if (trace[i] - deltaLeft >= 6 && trace[i] - deltaRight >= 6)
{
Console.WriteLine($"Peak at {i + 1}");
}
}You may notice that I don't start at 0 and I don't finish at the last element in the array; as it's assumed that you will always have a left and right value, this is sufficient.
This space for rent
Hi Pete, Many thanks for looking into this for me. This is a great attempt but its using a sliding window observing the points immediately adjacent the current point. If you change data point p8. from 73 to 77, you would observe that the peak at p9. level 82 is no longer detected. p9. is still a legitimate peak as it is 6dB above p6 and p10. The peak would have changed from being 3 points wide to 5 points wide. Think of a peak as an noisy parabola which could be represented with >= 3 points. If the peak to troughs are less than 6dB then they all form part of the same emissions. The seperation points being when the emissions lobes descend to >= -6dB. Hope this helps and thanks again for your help.! Br Nigel
-
Searching for peaks, and using your example here, the following code gives you the results you expect:
double[] trace =
{
47.92370605, 44, 49, 46.31715393, 44.98129654, 46.17653275, 78, 73, 82, 63, 69, 41.72979736, 41.13000488,
41.49586487, 37, 40, 30, 40.79894257, 40.65593719, 41.37298584, 39.13498688, 55, 51, 60, 39.3440094,
38.51491547, 42, 35.12589264
};
for (int i = 1; i < trace.Length - 1; i++)
{
double deltaLeft = trace[i - 1];
double deltaRight = trace[i + 1];if (trace[i] - deltaLeft >= 6 && trace[i] - deltaRight >= 6)
{
Console.WriteLine($"Peak at {i + 1}");
}
}You may notice that I don't start at 0 and I don't finish at the last element in the array; as it's assumed that you will always have a left and right value, this is sufficient.
This space for rent
Hi Pete, Many thanks for looking into this for me. This is a great attempt but its using a sliding window observing the points immediately adjacent the current point. If you change data point p8. from 73 to 77, you would observe that the peak at p9. level 82 is no longer detected. p9. is still a legitimate peak as it is 6dB above p6 and p10. The peak would have changed from being 3 points wide to 5 points wide. Think of a peak as an noisy parabola which could be represented with >= 3 points. If the peak to troughs are less than 6dB then they all form part of the same emissions. The seperation points being when the emissions lobes descend to >= -6dB. Hope this helps and thanks again for your help.! Br Nigel
-
Hi Pete, Many thanks for looking into this for me. This is a great attempt but its using a sliding window observing the points immediately adjacent the current point. If you change data point p8. from 73 to 77, you would observe that the peak at p9. level 82 is no longer detected. p9. is still a legitimate peak as it is 6dB above p6 and p10. The peak would have changed from being 3 points wide to 5 points wide. Think of a peak as an noisy parabola which could be represented with >= 3 points. If the peak to troughs are less than 6dB then they all form part of the same emissions. The seperation points being when the emissions lobes descend to >= -6dB. Hope this helps and thanks again for your help.! Br Nigel
Please don't repost if your message does not appear immediately: both of these went to moderation and required a human being to review them for publication. In order to prevent you being kicked off as a spammer, both had to be accepted, and then I have to clean up the spares. Have a little patience, please! I've deleted one version.
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay... AntiTwitter: @DalekDave is now a follower!
-
Please don't repost if your message does not appear immediately: both of these went to moderation and required a human being to review them for publication. In order to prevent you being kicked off as a spammer, both had to be accepted, and then I have to clean up the spares. Have a little patience, please! I've deleted one version.
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay... AntiTwitter: @DalekDave is now a follower!
-
Hi Pete, Many thanks for looking into this for me. This is a great attempt but its using a sliding window observing the points immediately adjacent the current point. If you change data point p8. from 73 to 77, you would observe that the peak at p9. level 82 is no longer detected. p9. is still a legitimate peak as it is 6dB above p6 and p10. The peak would have changed from being 3 points wide to 5 points wide. Think of a peak as an noisy parabola which could be represented with >= 3 points. If the peak to troughs are less than 6dB then they all form part of the same emissions. The seperation points being when the emissions lobes descend to >= -6dB. Hope this helps and thanks again for your help.! Br Nigel
Ah, I see. That wasn't quite what your initial post described. So, effectively, you're pinning a value and as long as the next value continues the trend of moving upwards (as an example), we keep going until we hit the maximum. As soon as the value moves in the opposite direction, we repin the value we're comparing against. Does that sound right to you?
This space for rent
-
Ah, I see. That wasn't quite what your initial post described. So, effectively, you're pinning a value and as long as the next value continues the trend of moving upwards (as an example), we keep going until we hit the maximum. As soon as the value moves in the opposite direction, we repin the value we're comparing against. Does that sound right to you?
This space for rent
Hi Pete, That is almost correct. If the value changes direction from say north to south but the distance south is < 6 from the pinned max then the trend should remain northerly until the change south from the pinned value is >= 6. E.g. south 5 north 3 south 5 constitutes a southerly trend and north 5 south 3 north 5 constitutes a positive trend even though the direction is changing. The trend only shifts in the opposite direction once we get to pinned <=6. Hope that's clearer :| Best Regards Nigel
-
Hi Eddy, If you stick the following data into Excel and plot it. Then place markers on the 9th 11th and 24th point you would see what I was after.
double[] trace = new double[] { 47.92370605, 44, 49, 46.31715393, 44.98129654, 46.17653275, 78, 73, 82, 63, 69, 41.72979736, 41.13000488, 41.49586487, 37, 40, 30, 40.79894257, 40.65593719, 41.37298584, 39.13498688, 55, 51, 60, 39.3440094, 38.51491547, 42, 35.12589264 };
If I could embed an image into my comment I would show you. Your essentially looping through an array of points looking for the biggest and smallest peaks and waiting for the delta either side them to go >= 6dB. When it does you grab the biggest peak between the -6dB points. Rinse and repeat. So, 1,6,3,7,1 would yield a peak at p[4] = 7 with a window size of 5. 1,7,1 would yield a peak at p[2] = 7 with a window size of 3. 1,-3,-2,7,5,1 would yield a peak at p[4] = 7 with a window size of 4. 1,-7,1,-6 would yield 2 peaks. One at p[1] = 1 with a window size if 2 and one at p[3] with a window size of 3. stick them all together and you get 1,6,3,7,1,1,7,1,1,-3,-2,7,5,1,1,-7,1,-6 Peaks at p[4], p[7], p[12] and p[17] Respective window sizes in points would be, 5, 3, 4 and 3 :) Hope that's helps :| Br Nigel
Krellon wrote:
If I could embed an image into my comment I would show you.
A good thing you can't; I asked not only because I'm bad at math, but also because I'm a bit simple. The PC is too, so once you can describe your problems in those kind of steps it becomes easy to translate it to code. So I opened Calc, generated a chart, and.. you're looking for those three tops?
Krellon wrote:
Your essentially looping through an array of points looking for the biggest and smallest peaks and waiting for the delta either side them to go >= 6dB. When it does you grab the biggest peak between the -6dB points. Rinse and repeat.
That sounds like pseudo-code, so let me pseudo away (without compiler)
double lastValue = 44;
List peaks = new List();
for (int i = 0; i < trace.Length; i++)
{
double currentValue = trace[i];// waiting for the delta (so, diff between this and last value?)
double delta = currentValue - lastValue;// either side them to go >= 6dB. (both sides = do for + and -)
if (Math.Abs(delta) > 6)
{
// When it does you grab the biggest peak between the -6dB points.
DoMagic();
}// now the current value becomes our "last read value" before looping again
lastValue = currentValue;
} // Rinse and repeat.There's a DoMagic in there, because that's a complex sentence there. From which range would you want the maximum? Which two points would the -6dB points be? Do you want to use a fixed window size? If you can describe that in simple terms, you can complete the code :)
Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]
-
Dear coder/Mathematician folk, I have a question on how to best peak search a series of noise like points. The points are stored as doubles in a double array. The points represent voltage levels in dBuV. I'm not a mathematician and I have limited knowledge regarding the elegancie's of how C# can be put to handle complex problems. Or maybe not so complex to some :) I would like 'n' points returning that have a delta from there neighbours of >= 6dB and within a specified window of 'm' points. The window allows us to reject all peaks regardless of delta bar the point with the highest peak. As we go through the data points we look at each point [DP] with respect to its neighbour. If the delta to left neighbour [P1] is >= 6dB and delta to right neighbour [P2] is >= 6dB we have a peak. if either neighbours delta is less than 6dB we may have a slope condition. We must there for ride the slope with respect to [P2] goint up and down the troughs until we hit a transition and the delta from [P2] is >= 6dB. This would be our next point. We repeat the process though all points returning just the peaks that are separated by the window width and have clear >= 6dB margin from there neighbours. The following data represents a typical trace. Only points 9,11, and 24 are real points that should be returnd.
double[] trace = new double[] {47.92370605,44,49,46.31715393,44.98129654,46.17653275,78,73,82,63,69,41.72979736,41.13000488,41.49586487,37,40,30,40.79894257,40.65593719,41.37298584,39.13498688,55,51,60,39.3440094,38.51491547,42,35.12589264};
I hope I explained things clearly. Please feel free to ask for any clarifications :) Many thanks for your time and effort Nigel
using System;
namespace ConsoleApplication10 {
class Program {
static void Main( string\[\] args ) { double\[\] trace = new double\[\] { 47.92370605, 44, 49, 46.31715393, 44.98129654, 46.17653275, 78, 73, 82, 63, 69, 41.72979736, 41.13000488, 41.49586487, 37, 40, 30, 40.79894257, 40.65593719, 41.37298584, 39.13498688, 55, 51, 60, 39.3440094, 38.51491547, 42, 35.12589264 }; double low = trace\[ 0 \]; double previous = trace\[ 0 \]; double peak = trace\[ 0 \]; for ( int i = 1; i < trace.Length; i++ ) { double current = trace\[ i \]; if ( current > previous ) { peak = current; } else { if ( current < previous ) { if ( ( peak - low >= 6.0 ) && ( peak - current >= 6.0 ) ) { Console.WriteLine( $"Peak: {peak} @{i}" ); low = peak = current; } } } previous = current; } // end for. Console.ReadKey(); }} // end class.
}"(I) am amazed to see myself here rather than there ... now rather than then". ― Blaise Pascal
