libs/Music/CumulativeDiffAlgo.cpp

   1 // Copyright 2004 "Gilles Degottex"
   2
   3 // This file is part of "Music"
   4
   5 // "Music" is free software; you can redistribute it and/or modify
   6 // it under the terms of the GNU Lesser General Public License as published by
   7 // the Free Software Foundation; either version 2.1 of the License, or
   8 // (at your option) any later version.
   9 //
  10 // "Music" is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13 // GNU Lesser General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU Lesser General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18
  19
  20 #include "CumulativeDiffAlgo.h"
  21
  22 #include <cassert>
  23 #include <cmath>
  24 #include <deque>
  25 #include <iostream>
  26 #include <limits>
  27 using namespace std;
  28 #include <CppAddons/CAMath.h>
  29 using namespace Math;
  30
  31 #include "Music.h"
  32
  33 //#define MUSIC_DEBUG
  34 #ifdef MUSIC_DEBUG
  35 #define LOG(a)  a
  36 #else
  37 #define LOG(a)
  38 #endif
  39
  40 namespace Music
  41 {
  42         void CumulativeDiffAlgo::init()
  43         {
  44                 setMinMaxLength(int(GetSamplingRate()/h2f(GetSemitoneMax())), int(GetSamplingRate()/h2f(GetSemitoneMin())));
  45         }
  46
  47         CumulativeDiffAlgo::CumulativeDiffAlgo(double noise_treshold)
  48         : m_noise_threshold(noise_treshold)
  49         , m_wave_length(0)
  50         {
  51                 init();
  52         }
  53
  54         //! return the average differance on the sample delimited by [0,size]
  55         // - ne pas utiliser tout size
  56         // - sauter des données
  57         double diff(const deque<double>& buff, size_t size, size_t s)
  58         {
  59                 double r = 0.0;
  60                 for(size_t i=0; i<size; i++)
  61                         r += abs(buff[i] - buff[i+s]);
  62                 return r / size;
  63         }
  64
  65         void CumulativeDiffAlgo::apply(const deque<double>& buff)
  66         {
  67                 if(buff.size()<2*m_max_length)
  68                 {
  69                         m_wave_length = 0;
  70                         return;
  71                 }
  72
  73                 double max_vol = 0.0;
  74                 for(size_t i=0; i<m_max_length; i++)
  75                         max_vol = max(max_vol, buff[i]);
  76
  77                 // use a relative threshold
  78                 double threshold = m_noise_threshold*max_vol;
  79
  80 //      cerr << "min=" << min_length << " max=" << m_max_length << " threshold=" << treshold << endl;
  81
  82                 double r = 0.0;
  83                 size_t s;
  84                 for(s=m_min_length; r<=threshold && s<m_max_length; s++)
  85                         r = diff(buff, m_max_length, s);
  86
  87                 while((r=diff(buff, m_max_length, s+1))>threshold && s<m_max_length)
  88                         s++;
  89
  90 //      cerr << "s=" << s << " r=" << r << endl;
  91                 double old_r = r;
  92                 while(s+1<m_max_length && (r=diff(buff, m_max_length, s+1))<old_r)
  93                 {
  94 //      cerr << "s=" << s << " r=" << r << endl;
  95                         s++;
  96                         old_r = r;
  97                 }
  98
  99 //      cerr << "s=" << s << " r=" << old_r << endl;
 100
 101 //      cerr << "absolute threshold=" << m_noise_threshold << " max volume="<<max_vol<<" relative threshold="<<threshold << " s="<<s << " m_max_length="<<m_max_length << endl;
 102
 103                 m_wave_length = (s<m_max_length)?s:0;
 104         }
 105
 106 /*
 107  * ~YIN version, unused because too costly for the CPU: O(n^3) ...
 108         double CumulativeDiffAlgo::squar_diff(const deque<double>& buff, size_t s)
 109         {
 110                 double r = 0.0;
 111                 for(size_t i=0; i<s; i++)
 112                 {
 113                         double d = buff[i] - buff[i+s];
 114                         r += d*d;
 115                 }
 116
 117                 return r;
 118         }
 119         double CumulativeDiffAlgo::norm_squar_diff(const deque<double>& buff, size_t s)
 120         {
 121                 double r = 0.0;
 122                 for(size_t i=0; i<s; i++)
 123                         r += squar_diff(buff, i);
 124
 125                 return squar_diff(buff, s) / (r/s);
 126         }
 127         void CumulativeDiffAlgo::receive(const deque<double>& buff)
 128         {
 129                 assert(m_sampling_rate>0);
 130                 size_t min_length = size_t(m_sampling_rate * m_min_wave_length);
 131                 size_t max_length = size_t(m_sampling_rate * m_max_wave_length);
 132
 133                 if(buff.size()<2*max_length)    return;
 134
 135         cerr << "min=" << min_length << " max=" << max_length << " noise=" << m_noise_treshold << endl;
 136
 137                 double r = 1.0;
 138                 double max_vol = 0.0;
 139                 size_t s;
 140                 for(s=min_length; r>m_noise_treshold && s<max_length; s++)
 141                 {
 142                         max_vol = max(max_vol, buff[s]);
 143
 144                         r = norm_squar_diff(buff, s);
 145 //      cerr << "s=" << s << " r=" << r << endl;
 146                 }
 147                 s--;
 148         cerr << "s=" << s << " r=" << r << endl;
 149 //      cerr << "---" << endl;
 150                 double old_r;
 151                 do
 152                 {
 153                         s++;
 154                         old_r = r;
 155
 156                         r = norm_squar_diff(buff, s);
 157 //      cerr << "s=" << s << " r=" << r << endl;
 158                 }
 159                 while(r<old_r && s<max_length);
 160
 161                 r = old_r;
 162                 s--;
 163         cerr << "s=" << s << " r=" << r << endl;
 164
 165         cerr << "m_noise_treshold=" << m_noise_treshold << " max_vol=" << max_vol << " r=" << r << endl;
 166
 167                 m_freq = 0.0;
 168                 if(max_vol>m_noise_treshold && s<max_length)
 169                 {
 170                                                 cerr << "r=" << r << " m_noise_treshold=" << m_noise_treshold << endl;
 171                         m_freq = double(m_sampling_rate)/s;
 172                 }
 173
 174         cerr << "m_sampling_rate=" << m_sampling_rate << " freq=" << m_freq << endl;
 175         }
 176 */
 177 }
 178