title: Number of peaks in histogram
body: <p>I have 1D data that represent some intensity values. I want to detect number of components in these data (clusters of points with similar intensity, or alternatively number of "peaks" in histogram created from this data).</p>
  
  <p>This approach: <a href="https://stackoverflow.com/questions/3790445/1d-multiple-peak-detection">1D multiple peak detection?</a> is not very useful for me, because one "peak" can contain more local maximums (see image below). </p>
  
  <p><img src="https://i.stack.imgur.com/nKkws.png" alt="enter image description here"></p>
  
  <p>Of cause, I can use statistical approach, for example, I can try to fit data for 1,2,3,....n peaks, then calculate <a href="http://en.wikipedia.org/wiki/Bayesian_information_criterion" rel="nofollow noreferrer">BIC</a>, <a href="http://en.wikipedia.org/wiki/Akaike_information_criterion" rel="nofollow noreferrer">AIC</a> or whatever for each fit. And finally use <a href="http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set" rel="nofollow noreferrer">elbow method</a> for number of clusters determination. However, I want to detect approximate number of peaks as fast as possible and fitting gaussian mixture is quite time consuming procedure.</p>
  
  <p><strong>My approach</strong></p>
  
  <p>So I came up with following approach (in C++). It takes histogram bins heights (y) and searches for indices in which y values start to decline. Then values lower than y tolerance (yt) are filtered. And finally, indices that are near to other using x tolerance (xt) are filtered too:</p>
  
  <pre><code>Indices StatUtils::findLocalMaximas(const Points1D &amp;y, int xt, int yt) {
  
    // Result indices
    Indices indices;
  
    // Find all local maximas
    int imax = 0;
    double max = y[0];
    bool inc = true;
    bool dec = false;
    for (int i = 1; i &lt; y.size(); i++) {    
  
      // Changed from decline to increase, reset maximum
      if (dec &amp;&amp; y[i - 1] &lt; y[i]) {
        max = std::numeric_limits&lt;double&gt;::min();
        dec = false;
        inc = true;
      }
  
      // Changed from increase to decline, save index of maximum
      if (inc &amp;&amp; y[i - 1] &gt; y[i]) {
         indices.append(imax);
         dec = true;
         inc = false;
      }
  
      // Update maximum
      if (y[i] &gt; max) {
         max = y[i];
         imax = i;
      }
    }
  
    // If peak size is too small, ignore it
    int i = 0;
    while (indices.count() &gt;= 1 &amp;&amp; i &lt; indices.count()) {
      if (y[indices.at(i)] &lt; yt) {
        indices.removeAt(i);
      } else {
        i++;
      }
    }
  
    // If two peaks are near to each other, take only the largest one
    i = 1;
    while (indices.count() &gt;= 2 &amp;&amp; i &lt; indices.count()) {
      int index1 = indices.at(i - 1);
      int index2 = indices.at(i);
      if (abs(index1 - index2) &lt; xt) {
        indices.removeAt(y[index1] &lt; y[index2] ? i-1 : i);
      } else {
        i++;
      }
    }
    return indices;
  }
  </code></pre>
  
  <p><strong>Problem with approach</strong></p>
  
  <p>Problem with this solution is that strongly depends on those tolerance values (xt and yt). So I have to have information about minimum allowed distance among peaks. Moreover, there are isolated outliers in my data that are higher then maximums of those smaller peaks. </p>
  
  <p>Could you suggest some other approach how to determine number of peaks for data similar to those in attached figure.</p>