24
$\begingroup$

What are the peak detection algorithms in existence? I have noisy data, and I would like to implement peak detection for this data. Data is in reverse, actually I am trying to determine the bottom.

Here is a snapshot of the data in Excel. I like to detect both bottoms. I thought about passing the data through a low-pass filter and subsequently do a moving average where I determine the peaks and within the moving average I do another search. I have zero DSP background; this is just a common sense approach. I would like to hear what the experts recommend.

Enter image description here

$\endgroup$
  • 2
    $\begingroup$ What are the two bottoms you want to detect? I only see one obvious one. Do you know what kind of noise you have, or where it comes from? $\endgroup$ – Jason R Feb 1 '12 at 14:42
  • $\begingroup$ I'd like to know if you want to implement it on any particular hardware (resource constraints) as that will affect my peak detection strategy. $\endgroup$ – anasimtiaz Feb 1 '12 at 16:38
  • $\begingroup$ @JasonR the purple one is obvious. However the sharp edge there is an outlier. Ideally, I want that to be shaved off and than calculate the bottom point. (hence the LP filter in my approach) The non obvious one on light blue is the min point right side of purple peak. The purple is not a concern really but the light blue is. Excel plot doesn't do justice but this is from a 12 bit ADC where 4096 is 2V. $\endgroup$ – Ktuncer Feb 2 '12 at 0:14
  • $\begingroup$ @anasimtiaz believe it or not this will run on an iPhone/Android so I guess we can say, it is like a PC. No hardware constraints. $\endgroup$ – Ktuncer Feb 2 '12 at 0:15
  • $\begingroup$ @Ktuncer I have added some images for you to see for yourself. $\endgroup$ – Spacey Feb 3 '12 at 7:31
12
$\begingroup$

Ktuncer, there are a number of methods you can use here. One method that I would recommend is to use a Discrete Wavelet Transform, (DWT), and in particular, look at the Daubechies Wavelet. I would pick, say, Daub-14 / Daub-Tetra.

Basically what you really need to do is 'trend' your signal, and then from there, do a min or max pick. That will get rid of your outliers. A daub-14/daub-tetra wavelet transform can help you do this, and this helps especially since you do not know the nature of your signal. (Using daub-14, you can accurately represent polynomial signals of degree 14/2 = 7, and it looks like you wont need more than that).

The computation of this wavelet transform essentially 'compresses' your energy into a few indicies. Those indicies represent weights on basis vectors. The rest of the weights will (ideally) be near zero. When you have noise in your signal (as you do), those weights that were normally zero have some weights now, but you can simply zero them out and 'denoise' your signal. Once that is complete, you can then do a simple max/min detect.

There are more details involved, you may send me an email if you like to discuss how to implement it. I have done similar work on this before.

EDIT: Here are some images illustrating Daub-Tetra Denoiser:

enter image description here enter image description here enter image description here enter image description here

$\endgroup$
  • 1
    $\begingroup$ I like this.. Is there a reference library for this in matlab? $\endgroup$ – Ktuncer Feb 3 '12 at 8:24
  • $\begingroup$ @Ktuncer Shoot me an email. $\endgroup$ – Spacey Feb 4 '12 at 16:49
4
$\begingroup$

I am far from being an expert, but here is what I would do:

You seem to have a slowly varying signal superimposed with fluctuations. The peaks you search are some stronger fluctuations, so I would detect them using that.

  1. Let $X(T)$ be your raw signal. Take a moving average over a suitable number of samples to create $Y(t)$ a smooth carrier.

  2. If you succeed $X-Y$ must should have a zero mean. Compute the standard deviation $\sigma$ of $X-Y$.

  3. You can detect your peaks when $|(X-Y)(t)| > \alpha \times \sigma$, with $\alpha$ being typically 2, 3, 4.

An overshoot or an undershoot can be specifically detected by removing the absolute value and using proper test. Is that what you are looking for?

$\endgroup$
  • 1
    $\begingroup$ Interesting approach. What is σ ? (Std. dev?). Also, math aside, what is the logic behind it? $\endgroup$ – Ktuncer Feb 2 '12 at 15:36
  • $\begingroup$ @user4749: Interesting name:) Ok. So yes, $\sigma$ is the standard deviation. We use it as a measure of the fluctuation amplitude. On your data, it looks pretty constant over time, so it indicates that it is the right approach. The logic is to say that a peak is detected when it is larger than these fluctuations, so that we are robust in the detection. Do you do MATLAB? iw we would have your signal, we could at least flag the peaks very easily. $\endgroup$ – Jean-Yves Feb 2 '12 at 19:19
  • $\begingroup$ @user4749 Basically what is happening here, your Y(t) is going to be the 'trend only' signal. Also means average. So now you are subtracting the average of your signal, from the signal. That is the X(t) - Y(t) part. So now what is left is your noise. Now, (assuming your noise is Gaussian), you take your std, &\sigma&. Now look at all values of abs(X(t)-Y(t)) > $4\sigma$. Why? This basically means in english, "Discard 99.99% of all values likely to be the noise, and leave only values not due to noise". $\endgroup$ – Spacey Feb 3 '12 at 5:21
  • $\begingroup$ @user4749 This will help you get the outlier peaks, although I am not sure it will get the overall peaks you are looking for, (I am assuming you are looking for the 'broad' peaks?) $\endgroup$ – Spacey Feb 3 '12 at 5:22
  • 1
    $\begingroup$ @Jean-Yves Hello! :-) Are you are assuming the noise is guassian here btw? (That is why we can std threshold). I am curious, what if the noise is colored? $\endgroup$ – Spacey Feb 3 '12 at 5:23
4
$\begingroup$

Peak detection has quite a few applications, for 1D or multidimensional signals. Here are a few examples showing how varied these signals and their interpretations of a peak can be:

  • The original poster's 1D data;

  • Hough transform of an image, each peak corresponds to a line in the original image; enter image description here

  • autocorrelation of an image, each peak corresponds to a frequency revealing a "periodic pattern"; enter image description here

  • "generalized" cross-correlation of an image and a template, each peak corresponds to an occurrence of the template in the image (we may be interested in detecting only the best peak or several peaks);

enter image description here

  • result of filtering an image for Harris corners, each peak corresponds to a corner in the original image.

enter image description here

These are definitions and detection techniques of peaks I have encountered--certainly there are others that I either forgot or don't know, and hopefully other answers will cover them.

Preprocessing techniques includes smoothing and denoising. @Mohammad's answer is about wavelets, and you can see various usages of them in the documentation of Mathematica's WaveletThreshold (where I also took my examples from, by the way).

Then you search for maxima. Depending on your application, you need only the global maxima (e.g., image registration), a few local maxima (e.g. line detection), or many local maxima (keypoints detection): This can done iteratively, looking for the highest value in the data then erasing a region around the selected peak, etc. until the highest remaining value is below a threshold. Alternatively, you can look for the local maxima within a certain neighborhood size, and keep only those local maxima whose values are above a threshold -- some recommend to keep the local maxima based on their distance to the rest of the local maxima (the further the better). The arsenal also features morphological operations: Extended maxima and top-hat transform can both be suitable.

See the results of three of these techniques on an image filtered for Harris corners:

enter image description here

Moreover, some applications attempt to find peaks at sub-pixel resolution. Interpolation, which can be application-specific, comes handy.

As far as I know, there is no silver bullet, and the data will tell which techniques work best.

It will be really nice to have more answers, esp. coming from other disciplines.

$\endgroup$
  • $\begingroup$ How did you extract the data of the question body for your use? I cannot find it in a clean form. $\endgroup$ – Léo Léopold Hertz 준영 May 18 '16 at 18:29
  • 1
    $\begingroup$ Did I? I used other examples. Looking at the question again today, I don't see how to extract cleanly data from the question. $\endgroup$ – Matthias Odisio Sep 23 '16 at 21:46
-1
+100
$\begingroup$

I think one typical peak detection algorithm is like this where ref is peak(bottom).

for i=1,N   {
       if i=1   {  ref=data(i) }
       else { if data(i)<=ref {ref =data(i) }}
}
$\endgroup$
  • 3
    $\begingroup$ I did not downvote your answer, but I think it was considered off-topic by those who did. This sketch detects the absolute minimum of a sequence. The OP is looking for peaks, where one needs to deal with locality and noise. $\endgroup$ – Matthias Odisio Feb 2 '12 at 19:29
  • $\begingroup$ Alas there has been no response at all to the "canonical answer" bounty. In that respect all answers are equally "irrelevant"; I awarded the bounty to this answer because it's the oldest. $\endgroup$ – Matthias Odisio Feb 9 '12 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.