Finding multiple peaks from a vector

[ivar5000]

Can anyone help me with finding multiple peaks given a vector with amplitudes?
I need to use the first difference as well as the smooth difference(median of 5) to find the peaks.

A typical data vector has values in the multiples of 60.
Here is a sample data set of length 60 with a single peak : https://ibb.co/hLiPma


I have the following vectors available:
vector<int> amplitudes;
vector<int> firstDifference;
vector<int> secondDifference;
vector<int> smoothSecondDifference;
vector<int> smoothSecondDifferencePeaks;

In the sample data, I know that I have a peak at index 18 with a value of 240

/*
 * Calculate all the peaks
 */
void Calculations::findPeaks(){
  int count = 1;
  int noOfPeaks = 0;
  
    for(int i = 0; i<smoothSecondDifference.size(); i++){
      if(count == 1 && smoothSecondDifference[i] > 
                    smoothSecondDifference[i+1] < 0){
        smoothSecondDifferencePeaks.push_back(i+3); // i+3 due to the way I'm storing the elements in the vector
        noOfPeaks++;
        count++;
      }
      else if(count == 58 && smoothSecondDifference[i] > 
                             smoothSecondDifference[i-1]){
        smoothSecondDifferencePeaks.push_back(i+3);
        noOfPeaks++;
        count = 1;
      }
      else if(smoothSecondDifference[i] >= smoothSecondDifference[i+1]
              && smoothSecondDifference[i] > smoothSecondDifference[i-1]){
        smoothSecondDifferencePeaks.push_back(i+3);        
        noOfPeaks++;
        count++;
      }
    }
}

I can disregard all amplitudes <4 as noise, so when I take into account all amplitudes >=4, my code finds the following:

Peak: 35 found at location: 14
Peak: 240 found at location: 18
Peak: 14 found at location: 30
Peak: 6 found at location: 38
Peak: 4 found at location: 42
Peak: 6 found at location: 46


Which is clearly wrong.

[Handy Andy]

Hello ivar5000,

I see one problem right off with the if statement. It does not work the way you have written it.
&& smoothSecondDifference[i] > smoothSecondDifference[i + 1] < 0 The final "< 0" does not work this way. What you want is something more like this:
&& smoothSecondDifference[i] > smoothSecondDifference[i + 1] && smoothSecondDifference[i + 1] < 0.
the second "&&" could be an "||"and you might need a set of () around everything after the first "&&".

Hope that helps,

Andy

[Handy Andy]

Hello ivar5000,

When I set up your function to test it I found some more problems.

1. When you have a subscript of "i - 1" in the first iteration of the for loop this becomes "-1" which is out side the boundaries of the vector.

2. The same thing happens at the other end end of the for loop when "i + 1" becomes 47 and is out side of the boundaries of the vector.

3. I think the conditions of the if/else if statements is wrong. It looks like only the second else if is ever executed and I received these numbers for an output:

15
25
43

I do not believe this is what you are looking for. Na example of what the output should be would help. I will see what I can come up with that works better.

Hope that helps,

Andy

[dhayden]

Can you explain how the smooth second difference is calculated? I don't get it.

A local peak occurs when the first difference changes sign from positive to negative. A change from positive to zero or zero to negative represents a plateau.

[keskiverto]

A change from positive to zero or zero to negative represents a plateau.

You probably mean that zero(s) are a plateau, and

a b c d e  f g h i  j k  l
0 1 2 2 2  1 1 1 4  1 1  0
 1 1 0 0 -1 0 0 3 -3 0 -1

b-c is positive and e-f is negative. Between them is a c-d-e plateau that is also a "wide peak".

f-g-h is a plateau too, but a "wide local minima" (before negative, after positive).

The i is a clear peak (positive->negative).

The j-k is a plateau, but part of i-j-k-l downhill (1st diff before and after the plateau has same sign).


Is a wide peak a peak?

[ivar5000]

@Andy -

The final "< 0" does not work this way..

the additional <0 was an oversight. Fixed that.

@dhayden - the smooth second difference is calculated on the second difference by taking a median of 5 (the element itself and its two neighbors on either side). A median filter of sorts

@keskiverto - My final output should be two peaks, one at c and one at i.

A change from positive to zero or zero to negative represents a plateau.

this is true for the first difference. How do i disregard the plateaus in my code?

[lastchance]

#include <iostream>
#include <vector>
using namespace std;

// Prototypes
vector<int> getData();
void findPeaks( const vector<int> &amp );

//======================================================================

int main()
{
   vector<int> amp = getData();
   findPeaks( amp );
}

//======================================================================

vector<int> getData()
{
   // Hard-code for testing; better read from file in future

   // Data from original post
// vector<int> amp = { 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 1, 9, 35, 88, 115, 212, 240, 237, 200,
//                     145, 87, 42, 18, 12, 13, 14, 15, 15, 14, 13, 10, 8, 8, 8, 8, 7, 6, 6, 4, 4, 4,
//                     3, 4, 5, 6, 4, 4, 3, 2, 2, 1, 1, 0, 1, 2, 3, 4, 4, 2 };

   // Keskiverto data
   vector<int> amp = { 0, 1, 2, 2, 2, 1, 1, 1, 4, 1, 1, 0 };

   return amp;
}

//======================================================================

void findPeaks( const vector<int> &amp )
{
   const int NOISE = -1;               // Level up to and including which peaks will be excluded
   int wideStart = -1;                 // The start of any current wide peak

   int grad = -1;                      // Sign of gradient (almost)
                                       //    =  1 for increasing
                                       //    =  0 for level AND PREVIOUSLY INCREASING (so potential wide peak)
                                       //    = -1 for decreasing OR level, but previously decreasing
                                       // A sharp peak is identified by grad=1 -> grad=-1
                                       // A wide  peak is identified by grad=0 -> grad=-1

   for ( int i = 0; i < amp.size() - 1; i++ )
   {
      if ( amp[i+1] < amp[i] )         // Only possibility of a peak
      {
         if ( grad == 1 && amp[i] > NOISE )
         {
            cout << "Sharp peak of " << amp[i] << " at i = " << i << '\n';
         }
         else if ( grad == 0 && amp[i] > NOISE )
         {
            cout << "Wide peak of " << amp[i] << " from i = " << wideStart << " to " << i << '\n';
         }
         grad = -1;
      }
      else if ( amp[i+1] == amp[i] )   // Check for start of a wide peak
      {
         if ( grad == 1 )
         {
            wideStart = i;
            grad = 0;
         }
      }
      else
      {
         grad = 1;
      }
   }
}

//====================================================================== 

Using @Keskiverto's sample data:

Wide peak of 2 from i = 2 to 4
Sharp peak of 4 at i = 8

Using the original post sample data (up to any transcribing errors):

Wide peak of 2 from i = 1 to 3
Sharp peak of 240 at i = 18
Wide peak of 15 from i = 28 to 29
Sharp peak of 6 at i = 46
Wide peak of 4 from i = 58 to 59

Just increase the variable NOISE if you want to exclude the low peaks in the chatter at the ends of the dataset.


You could use first differences instead of the comparison of successive amplitudes. However, the second difference isn't really necessary and I can't see any purpose in "smoothing" it.

If you restricted yourself to "sharp" peaks then (by analogy with differential calculus for a maximum without point of inflexion: dy/dx changes sign and d²y/dx² is negative) you can find these by the condition that successive first differences have opposite sign (just multiply them and look for a negative) AND the second difference is negative (i.e. gradient is decreasing). Smoothing the second difference wouldn't help you.

If you want to smooth anything then smooth the original amplitudes; either use weighted moving averages or Fourier transform and cut off the high frequencies.

[ivar5000]

@lastchance - thank you for your help. I will try smoothing out the original data and see if that helps!