ansaurus

Question

Answer 1

+6 A:

The local maxima would be any x point which has a higher y value than either of its left and right neighbors. To eliminate noise, you could put in some kind of tolerance threshold (ex. x point must have higher y value than n of its neighbors).

To avoid scanning every point, you could use the same approach but go 5 or 10 points at a time to get a rough sense of where the maximum lie. Then come back to those areas for a more detailed scan.

btreat 2010-07-14 02:13:44

This is sort of how my current algorithm works. The problem is that I have to know what threshold to give it, and that threshold could change depending on the actual data.

FogleBird 2010-07-14 02:18:12

@FogleBird You could find that threshold by going through the data once and computing the mean/std dev of the differences between adjacent y-values; and let your threshold be some function of that.

quantumSoup 2010-07-14 02:21:29

@Aircule: Good idea, I'll try that tomorrow.

FogleBird 2010-07-14 02:30:07

'The local maxima would be any x point which has a higher y value than either of its left and right neighbors'Not necessarily this simple, right? The presence of equal values will break this. If your data points are 1, 2, 3, 50, 3, 3, 10, 10, 3, then the 10s represent a local maxima, though neither of them is higher than both left + right neighbours.

Cowan 2010-07-14 07:17:44

Closest to what I ended up doing, so accepting this for now.

FogleBird 2010-07-14 19:57:38

To handle maxima that might occur in flat spots, re-word "any x point which has a higher y value than its neighbors" to "any x point which *does not* have a *lower* y value than its neighbors".

bta 2010-07-14 20:26:02

Answer 2

+2 A:

You could try to fit a spline to the data and then find the extrema of the spline. Since the spline is piecewise polynomial, the exact locations of the extrema can be found with relatively simple formulas.

Victor Liu 2010-07-14 02:15:34

I think fitting the data in a spline would be more computationally intensive than going through the data "manually."

quantumSoup 2010-07-14 02:23:07

Fitting splines is very fast -- O(n).

John D. Cook 2010-07-14 02:40:17

I also think fitting would be the most accurate solution; though I would not use spline. In this case I'd try a sum of 3 Gauss-bells.

Curd 2010-07-14 20:13:52

I do ultimately use curve fitting to find the actual peaks. But I do that with a higher resolution scan around each maxima, so then I just do a simple parabolic fit. I use the algorithm being discussed here just to figure out roughly where the peaks are during a more coarse grained (faster) focus scan.

FogleBird 2010-07-15 00:07:57

Answer 3

+6 A:

Couldn't you move along the graph, regularly calculating the derivative and if it switches from positive to negative you've found a peak?

Graphain 2010-07-14 02:19:08

The derivative will fluctuate +/- too much due to the random noise. How do I eliminate that problem?

FogleBird 2010-07-14 02:24:42

Have you tried a low pass filter?

K. Brafford 2010-07-14 02:30:01

Basically averaging with filters as suggested I would guess.

Graphain 2010-07-14 02:55:36

If that happens, the noise is creating local maxima. Averaging or filtering away the noise is one way to decide which maxima are 'important' enough.However, there's no need to calculate a derivative here. Just compare the value of the point to its neighbors.

Larry Wang 2010-07-14 04:00:00

Answer 4

+1 A:

Do you know the derivative of the data? If yes and you can symbolically solve the system then you can find the points where the derivative is equal to zero.

If you don't have the formula (which seems to be the case from your OP) then you might want to try filter out some noise then do the following:

If you can't solve symbolically then you can use something like Newton–Raphson method to get to the local maxima and choose the starting points randomly from the range to try to capture all the maxima.

If you don't have the derivative data then you might want to try a hill climbing algorithm that doesn't require the derivative and start it at multiple different randomly chosen points. You could then keep track of the points that you find when the iterative hill climbing part of the algorithm terminates. This will only probabilistically find all the local maxima but it may be good enough for your purposes.

EDIT: given that the 3 peaks will be roughly in the same places you should try guarantee that the starting point for these algorithms is near those points for at least some of the times you run the iterative algorithm.

shuttle87 2010-07-14 02:19:20

Answer 5

+1 A:

You could try a band-pass filter to reject the noise and make it easier to reliably select those maxima.

The point of a band-pass (rather than low-pass) is to pull nearly-constant down to zero. That way, the highest values you find in the filtered result will probably be the clearest peaks.

Certainly if you can define a narrow frequency-range for your signal and apply a very selective filter, it should make a fairly unsophisticated maxima-finding algorithm practical - e.g. a simple sample-thats-higher-than-either-neighbour scan.

A sophisticated filter might not be necessary - you could get away with a mexican hat wavelet at a single well-chosen scale. One scale probably means it's not really a wavelet any more - just a band-pass FIR filter.

EDIT

There's an asymmetric wavelet (I forget the name) which, if the mexican hat is analogous to a cosine, takes the role of the sine. I mention it as it combines band-pass filtering with a kind of derivative - the zero-crossings in the result are the stationary-points of a band-pass filtered version of the original signal.

A "debounced" scan could then identify reliable maxima by looking for crossing points in this "derivative" signal.

Steve314 2010-07-14 02:38:38

Answer 6

A:

I practice, I've found what works well is to use a dilation morphology operation to produce a dilated version of your sampled function (data points) then to identify local max's compare the dilated version vs. the original and anywhere where the dilated version equals the original version should be a local maximum. This works really well I find with 2D+ data (i.e. images) but since you have 1D data it may be easier just to use the differences between successive points as an approximation to the derivative.

Note if you do use the dilation technique, the structuring element (both the size and shape) that you use in the dilation greatly determines the types of peaks you are looking for.

Also if you have noise in your data, smooth it with a low pass filter, like a 1D Gaussian before searching.

More info on dilation can be found here:

here is the idea implemented in matlab: http://www.mathworks.com/matlabcentral/fileexchange/14498-local-maxima-minima

if you don't know what dilation is: http://en.wikipedia.org/wiki/Dilation_%28morphology%29

(its dead simple once you understand it here is a really easy explanation) http://homepages.inf.ed.ac.uk/rbf/HIPR2/dilate.htm

ldog 2010-07-14 18:06:16

Answer 7

+2 A:

direct approach, something like this:

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100

double smooth(double arr[], int n, int i)
{
        double l,r,smoo;
        l = (i - 1 < 0)?arr[0]:arr[i-1];
        r = (i + 1 >= n)?arr[n-1]:arr[i+1];
        smoo = (l + 2*arr[i] + r)/4;
        return smoo;
}

void findmax(double arr[], int n)
{
        double prev = arr[0];
        int i;
        int goup = 1;

        for(i = 0; i < n; i++)
        {
                double cur = smooth(arr,n,i);
                if(goup) {
                        if(prev > cur && i > 0) {
                                printf("max at %d = %lf\n", i-1, arr[i-1]);
                                goup = 0;
                        }
                } else {
                        if(prev < cur)
                                goup = 1;
                }
                prev = cur;
        }
}

int main()
{
        double arr[MAXN] = {0,0,1,2,3,4,4,3,2,2,3,4,6,8,7,8,6,3,1,0};
        int n = 20, i;

        for(i = 0; i < n; i++)
                printf("%.1lf ",arr[i]);
        printf("\n");

        findmax(arr,n);
        return 0;
}

output:

0.0 0.0 1.0 2.0 3.0 4.0 4.0 3.0 2.0 2.0 3.0 4.0 6.0 8.0 7.0 8.0 6.0 3.0 1.0 0.0
max at 6 = 4.000000
max at 14 = 7.000000

1) set state = goup: going upward the curve;
2) if previuos value is greater than current then there was maximum:
print it and set state to godown
3) while in godown state wait until previous is less then current and switch to (1)

to reduce noise use some smoothing function smooth()

oraz 2010-07-14 19:44:02

Answer 8

A:

As others have mentioned derivatives or comparing to local neighbors usually works for me. If you're worried about noise I can recommend median filtration as a pretty fast and reliable filtration scheme. I use it and reverse median filtration all the time to squelch noise in acoustic sensors, works great.

ChrisC 2010-07-14 20:07:09

ansaurus

tags:

views:

answers:

Algorithm to locate local maxima

related questions