Re: Finding local maxima/minima in noisy, pediodic data

If the data is suitable, you can try to split the signal to half periods roughly by alternatly searching for the first point when the signal reaches an upper threshold and a lower threshold. After this, you just find the minimum or maximum in each half period.

Let me show an example because my description is not clear. Assume the signal is like this:

our @s = map { sin(0.18*$_) + rand(0.6) - 0.3 } 0 .. 99;
[download]

Then you split the time to approximate half periods like this:

our(@xlo, @xhi); my $t = my $t0 = $s[0] < 0; for my $x (0 .. @s - 1) {
+ if ($t) { if ($s[$x] > 0.5) { $t = 0; push @xhi, $x; } } else { if (
+$s[$x] < -0.5) { $t = 1; push @xlo, $x; } } }
[download]

Now values in @xlo give the start of each lower half period, and similarly @xhi contain the starting time of each higher half period. So now you search for a minimum in each lower half period and the maximum in each upper half.

our(@xmi, @xma); for my $p (0 .. @xlo - 1) { my $xmi = $xlo[$p]; for m
+y $x ($xlo[$p] .. ($xhi[$p + $t0] || @s) - 1) { $s[$x] < $s[$xmi] and
+ $xmi = $x; } push @xmi, $xmi; } for my $p (0 .. @xhi - 1) { my $xma 
+= $xhi[$p]; for my $x ($xhi[$p] .. ($xlo[$p + 1 - $t0] || @s) - 1) { 
+$s[$xma] < $s[$x] and $xma = $x; } push @xma, $xma; }
[download]

(The code is complicated only because of the boundary conditions, furthermore it is left as an exercise to the reader to fix any off by one errors.)

Let's plot the results

for my $x (0 .. @s - 1) { my $l = " "x15 . ":" . " "x15; if (@xlo && $
+xlo[0] <= $x) { shift @xlo; substr $l, 0, 10, "v"x10; } elsif (@xhi &
+& $xhi[0] <= $x) { shift @xhi; substr $l, 20, 10, "v"x10; } if (@xmi 
+and $xmi[0] <= $x) { shift @xmi; substr $l, 0, 7, "minimum"; } elsif 
+(@xma and $xma[0] <= $x) { shift @xma; substr $l, 23, 7, "maximum"; }
+ substr $l, 15+int(10*$s[$x]), 1, "*"; print $l, "\n"; }
[download]

We get, for example, this.

               *               
              *:               
               : *             
               :    v*vvvvvvvv 
               :   *           
               :      *        
               :        *      
               :        *      
               :        *      
               :      *        
               :      *        
               :       max*mum 
               :    *          
               :        *      
               :   *           
               :   *           
               :    *          
               *               
              *:               
               *               
vvvvvvvv*v     :               
            *  :               
      *        :               
          *    :               
    *          :               
min*mum        :               
      *        :               
      *        :               
       *       :               
     *         :               
           *   :               
          *    :               
             * :               
          *    :               
             * :               
               :*              
               :   *           
               :  *            
               :    vv*vvvvvvv 
               :     *         
               :       *       
               :        *      
               :      *        
               :        *      
               :       max*mum 
               :        *      
               :        *      
               :        *      
               :    *          
               :     *         
               : *             
               : *             
              *:               
               *               
           *   :               
           *   :               
            *  :               
vvvvvvvv*v     :               
       *       :               
         *     :               
min*mum        :               
    *          :               
      *        :               
    *          :               
       *       :               
        *      :               
           *   :               
            *  :               
          *    :               
              *:               
               :  *            
               :*              
               :    v*vvvvvvvv 
               :    *          
               :      *        
               :     *         
               :          *    
               :      *        
               :        *      
               :        *      
               :       maxi*um 
               :       *       
               :     *         
               :     *         
               :   *           
               :   *           
               : *             
               : *             
              *:               
             * :               
vvvvvvvv*v     :               
          *    :               
        *      :               
         *     :               
     *         :               
         *     :               
     *         :               
minim*m        :               
       *       :               
        *      :
[download]

If the data is more noisy, you may need to smooth it before comparing with the thresholds. If the amplitude varies then it's not so easy to set a fix threshold this way, so I'm not sure what to do in that case.

Comment on Re: Finding local maxima/minima in noisy, pediodic data Select or Download Code

Replies are listed 'Best First'.
Re^2: Finding local maxima/minima in noisy, pediodic data by Xilman (Hermit) on Oct 14, 2009 at 08:17 UTC
This may sound heretical, but I suggest that Perl may be the wrong tool for the specific job you want doing. Great for collecting the data to feed to a better tool and great for interpreting and/or displaying that tool's result, but not especially good for doing the signal processing. You can write signal processing code in Perl, or any other Turing complete language, but sometimes it's better not to. I learned this lesson through experience ... As others have said, you're asking a moderately hard question in DSP and, IMO, you should be using tools which have been designed specifically to perform efficient and robust DSP. There are a good number available, some which cost real money, some which are free (as in beer and/or speech) and some which are in between. You don't reveal the nature of the platform you want to run this on, your budget (time and money, remember) or your views on free / non-free software so it's difficult to give specific advice and targeted use of Google is highly recommended. That said, consider Matlab/Octave for turn-key solutions. I've learned a lot from Numerical Recipes and have used their code in some of my projects. Good luck! Paul	[reply]
Re^3: Finding local maxima/minima in noisy, pediodic data by ambrus (Abbot) on Oct 14, 2009 at 10:11 UTC
Hey, I did not recommend perl for the tool, I just gave this toy example in perl to explain what method to use.	[reply]
Re^4: Finding local maxima/minima in noisy, pediodic data by Xilman (Hermit) on Oct 14, 2009 at 13:21 UTC
My apologies, and I wish to state publicly that it was my incompetence which led me to following up your post and not the original, which is where I'd intended to post it in the first place. That said, I stand by the contents of the posting, but it must be read in the appropriate context. Paul	[reply]