I have implemented simple modification of Dmitry Terez frequency estimation method and get awesome results: - CWT-like time resolution for one instantly found frequency - much faster than FFT - final algorithm uses only INTEGERS floating point can be needed for finding center of mass, but this code is very small. Main loop have no any rounding errors related to usual FFT "butterfly". I did some tests on real signals with noise and found this method works well. Here is example of 2000hz changing in time frequency signal sampled at 44100 sound card connected to radio-signals transmitter/reciever. http://www.igrodel.ru/tdg3d/terez-mod.png On this PNG picture: white line - Terez method on 256 points red line - FFT on 4096 points (no smoothing window) Both cases with sliding window (1 sample per one point on picture). In some cases Terez method looks ever more stable than FFT. Also big FFT have slow reaction to amplitude and frequency changes. Testing program made in delphi. for i := 0 to len - 1 do for j := i to len - 1 do if abs(signal2[i]-signal2[j])<radius then begin dt:=abs(i-j); hist[dt]:=hist[dt]+1; end; (early version at http://www.gamedev.ru/flame/forum/?id=134654 , results wass okay, but not enough) Then I did some small improvements: - added histogram peak center of mass finding. It solves problem of lower resolution at high frequencies. - added simple high-pass filter. It solves problem with DC component for some signals. Also there is a possiblity to improve frequency resolution by analysing T's 2*T, 3*T, ... periods of histogram. After all improvements and histogram spectrum accumulation this method can replace FFT in many tasks. I wonder is somebody tried his method before?
FFT vs Terez frequency estimation method.
Started by ●June 21, 2010
Reply by ●June 21, 20102010-06-21
Hello Dmitry Teres's friend, tmtlib wrote:> I have implemented simple modification of Dmitry Terez frequency estimation > method and get awesome results:How much is awesome?> - CWT-like time resolution for one instantly found frequencyHuh? How it compares to CRB?> - much faster than FFTHow much is much?> - final algorithm uses only INTEGERSHuh?> floating point can be needed for finding center of mass, but this code is > very small.How small is small?> Main loop have no any rounding errors related to usual FFT > "butterfly"."no any" ?> I did some tests on real signals with noise and found this method works > well. Here is example of 2000hz changing in time frequency signal sampled > at 44100 sound card connected to radio-signals transmitter/reciever. > http://www.igrodel.ru/tdg3d/terez-mod.pngCan you post this signal in a comprehensible format such as .csv ? So we can run different algorithms and compare the numbers?> On this PNG picture: > white line - Terez method on 256 points > red line - FFT on 4096 points (no smoothing window) > Both cases with sliding window (1 sample per one point on picture). > In some cases Terez method looks ever more stable than FFT.Define "stable"> Also big FFT have slow reaction to amplitude and frequency changes.Engineers don't use words like "big", "small". good", "bad", "awesome". Engineers compare numbers.> Testing program madeTesting what?> in delphi.Delphi ???> for i := 0 to len - 1 do > for j := i to len - 1 do > if abs(signal2[i]-signal2[j])<radius then > begin > dt:=abs(i-j); > hist[dt]:=hist[dt]+1; > end;Incredible program. What it does is called AMDF, and this method is old as a world.> (early version at http://www.gamedev.ru/flame/forum/?id=134654 , results > wass okay, but not enough)So, were the results "OK" or "not enough" ?> Then I did some small improvements: > - added histogram peak center of mass finding. It solves problem of lower > resolution at high frequencies.Huh?> - added simple high-pass filter. It solves problem with DC component for > some signals.Huh?> Also there is a possiblity to improve frequency resolution by analysing T's > 2*T, 3*T, ... periods of histogram. After all improvements and histogram > spectrum accumulation this method can replace FFT in many tasks.There is 1001 method for frequency estimation besides FFT. Which one is the best depends on the nature of the problem.> I wonder is somebody tried his method before?Where can I get a clear and unambiguous description of "the Terez" ? Or is it just simple plain old AMDF, described in every textbook ? If "the Terez" has something new and worthy, it would be interesting if one could publish an article with objective comparisons. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●June 21, 20102010-06-21
On Jun 21, 7:41=A0am, "tmtlib" <tmtlib@n_o_s_p_a_m.narod.ru> wrote:> I have implemented simple modification of Dmitry Terez frequency estimati=on> method and get awesome results: > - CWT-like time resolution for one instantly found frequency > - much faster than FFT > - final algorithm uses only INTEGERS > floating point can be needed for finding center of mass, but this code is > very small. Main loop have no any rounding errors related to usual FFT > "butterfly". > > I did some tests on real signals with noise and found this method works > well. Here is example of 2000hz changing in time frequency signal sampled > at 44100 sound card connected to radio-signals transmitter/reciever. > > http://www.igrodel.ru/tdg3d/terez-mod.png > > On this PNG picture: > white line - Terez method on 256 points > red line - FFT on 4096 points (no smoothing window) > Both cases with sliding window (1 sample per one point on picture). > In some cases Terez method looks ever more stable than FFT. > Also big FFT have slow reaction to amplitude and frequency changes. > > Testing program made in delphi. > for i :=3D 0 to len - 1 do > =A0for j :=3D i to len - 1 do > =A0 if abs(signal2[i]-signal2[j])<radius then > =A0 =A0begin > =A0 =A0 dt:=3Dabs(i-j); > =A0 =A0 hist[dt]:=3Dhist[dt]+1; > =A0 =A0end; > (early version athttp://www.gamedev.ru/flame/forum/?id=3D134654, results > wass okay, but not enough) > > Then I did some small improvements: > - added histogram peak center of mass finding. It solves problem of lower > resolution at high frequencies. > - added simple high-pass filter. It solves problem with DC component for > some signals. > > Also there is a possiblity to improve frequency resolution by analysing T='s> 2*T, 3*T, ... periods of histogram. After all improvements and histogram > spectrum accumulation this method can replace FFT in many tasks. > > I wonder is somebody tried his method before?You can ignore all comments from VLV: he is a well-known abusive comp.dsp troll, but what's even worse - he has no clue whatsoever Can't even distinguish simple periodicity histogram from AMDF (!!!) I bet he also calls autocorrelation AMDF and vice versa all the time I wonder who hires this dude ? (And this dude supposedly got his PhD from Fizteh - unbelievable, simply unbelievable !!!)
Reply by ●June 21, 20102010-06-21
Dear Dmitry Teres, Just few questions: 1) Where can one get your algorithm for evaluation? Intentionally or unintentionally, your patent doesn't make any sense. 2) Is there any objective comparison of performance? 3) Can your claims be supported by a third party technical person, familiar with the art? Can you answer either question? fatalist wrote:> You can ignore all comments from VLV: he is a well-known abusive > comp.dsp troll, but what's even worse - he has no clue whatsoever > Can't even distinguish simple periodicity histogram from AMDF (!!!) > I bet he also calls autocorrelation AMDF and vice versa all the timeAnything meaningfull to say?> I wonder who hires this dude ?My customers are very respectful companies. I do very well, and I don't hide my real name. Why are you hiding your name, Dmitry ? Are you ashamed of something?> (And this dude supposedly got his PhD from Fizteh - unbelievable, > simply unbelievable !!!)Yes, I got my degree from MiPh&T, and so did you, IIRC. So I can address the same question to you, my friend :)))))) VLV
Reply by ●June 21, 20102010-06-21
On Jun 21, 8:53=A0am, Vladimir Vassilevsky <nos...@nowhere.com> wrote:> Hello Dmitry Teres's friend, > > tmtlib wrote: > > I have implemented simple modification of Dmitry Terez frequency estima=tion> > method and get awesome results: > > How much is awesome? > > > - CWT-like time resolution for one instantly found frequency > > Huh? How it compares to CRB? > > > - much faster than FFT > > How much is much? > > > - final algorithm uses only INTEGERS > > Huh? > > > floating point can be needed for finding center of mass, but this code =is> > very small. > > How small is small? > > > Main loop have no any rounding errors related to usual FFT > > "butterfly". > > "no any" ? > > > I did some tests on real signals with noise and found this method works > > well. Here is example of 2000hz changing in time frequency signal sampl=ed> > at 44100 sound card connected to radio-signals transmitter/reciever. > >http://www.igrodel.ru/tdg3d/terez-mod.png > > Can you post this signal in a comprehensible format such as .csv ? > So we can run different algorithms and compare the numbers? > > > On this PNG picture: > > white line - Terez method on 256 points > > red line - FFT on 4096 points (no smoothing window) > > Both cases with sliding window (1 sample per one point on picture). > > In some cases Terez method looks ever more stable than FFT. > > Define "stable" > > > Also big FFT have slow reaction to amplitude and frequency changes. > > Engineers don't use words like "big", "small". good", "bad", "awesome". > Engineers compare numbers. > > > Testing program made > > Testing what? > > > in delphi. > > Delphi ??? > > > for i :=3D 0 to len - 1 do > > =A0for j :=3D i to len - 1 do > > =A0 if abs(signal2[i]-signal2[j])<radius then > > =A0 =A0begin > > =A0 =A0 dt:=3Dabs(i-j); > > =A0 =A0 hist[dt]:=3Dhist[dt]+1; > > =A0 =A0end; > > Incredible program. > What it does is called AMDF, and this method is old as a world. > > > (early version athttp://www.gamedev.ru/flame/forum/?id=3D134654, result=s> > wass okay, but not enough) > > So, were the results "OK" or "not enough" ? > > > Then I did some small improvements: > > - added histogram peak center of mass finding. It solves problem of low=er> > resolution at high frequencies. > > Huh? > > > - added simple high-pass filter. It solves problem with DC component fo=r> > some signals. > > Huh? > > > Also there is a possiblity to improve frequency resolution by analysing=T's> > 2*T, 3*T, ... periods of histogram. After all improvements and histogra=m> > spectrum accumulation this method can replace FFT in many tasks. > > There is 1001 method for frequency estimation besides FFT. Which one is > the best depends on the nature of the problem. > > > I wonder is somebody tried his method before? > > Where can I get a clear and unambiguous description of "the Terez" ? Or > is it just simple plain old AMDF, described in every textbook ? > > If "the Terez" has something new and worthy, it would be interesting if > one could publish an article with objective comparisons. > > Vladimir Vassilevsky > DSP and Mixed Signal Design Consultanthttp://www.abvolt.com>> in delphi.>Delphi ???What's your problem with Delphi, dude ? Ever used Skype ? Skype is written in Delphi (try to rewrite it in C++ or C# or whatever if you can...)> > for i :=3D 0 to len - 1 do > > for j :=3D i to len - 1 do > > if abs(signal2[i]-signal2[j])<radius then > > begin > > dt:=3Dabs(i-j); > > hist[dt]:=3Dhist[dt]+1; > > end; > > Incredible program. > What it does is called AMDF, and this method is old as a world.You DO realize that you are making a fool out of yourself, Vlad ? Here is your textbook AMDF definition: AMDF(k) =3D Sum |s(i)-s(i+k)| Here is periodicity histogram (in it's simplest one-dimensional form): hist(k)=3Dsum H(r-|s(i)-s(i+k)|) (where H is Heaviside, or unit step, function) Are you telling us that these two are the same ??? YES or NO ???
Reply by ●June 21, 20102010-06-21
Reply by ●June 22, 20102010-06-22
On Jun 21, 11:00 am, fatalist <simfid...@gmail.com> wrote:> On Jun 21, 8:53 am, Vladimir Vassilevsky <nos...@nowhere.com> wrote: > > > Hello Dmitry Teres's friend,how do you know it's his friend? it's more likely Dmitry himself posted this.> > > tmtlib wrote: > > > I have implemented simple modification of Dmitry Terez frequency estimation > > > method and get awesome results: > > > How much is awesome?something a little past objective. ...> > > > Incredible program.sounds objective.> > What it does is called AMDF, and this method is old as a world.well, AMDF with selective terms in the sum run through a non-linear function (the step function).> You DO realize that you are making a fool out of yourself, Vlad ?not to always come to Vlad's defense, but this is what i've been saying about Dmitry's alg since 2004 or something. it used to be that Google Groups could help me find these old posts, but it doesn't work so well anymore. in fact, today Google Groups works so shitty that i am not sure i can even post anymore.> > Here is your textbook AMDF definition: > > AMDF(k) = Sum |s(i)-s(i+k)| > > Here is periodicity histogram (in it's simplest one-dimensional form): > > hist(k)=sum H(r-|s(i)-s(i+k)|) (where H is Heaviside, or unit step, > function) > > Are you telling us that these two are the same ??? > > YES or NO ???H(r-x) is a strictly decreasing function of x (r is a fixed parameter). it is nothing other than running the difference terms into a non-invertible non-linear function. since it's decreasing, instead of looking for a minimum as you would for AMDF, Dmitry is looking for a maximum after the sum. there are lot's of non-linear functions, why is H(r-x) the best one for this purpose they are not the same, and since H(|x|-r) is not the same as |x| nor | x|^2, we cannot say they are equivalent. but it *is* a subset of A[??]DF where [??] is a function of the magnitude of the difference. Vlad's right about this. i can say this because i have looked at Dmitry's paper and alg since 2002 or 2004 or whenever he first posted about this. r b-j
Reply by ●June 22, 20102010-06-22
>On Jun 21, 11:00 am, fatalist <simfid...@gmail.com> wrote: >> On Jun 21, 8:53 am, Vladimir Vassilevsky <nos...@nowhere.com> wrote: >> >> > Hello Dmitry Teres's friend, > >how do you know it's his friend? it's more likely Dmitry himself >posted this. > >> >> > tmtlib wrote: >> > > I have implemented simple modification of Dmitry Terez frequencyestimation>> > > method and get awesome results: >> >> > How much is awesome? > >something a little past objective. > >... >> >> > > Incredible program. > >sounds objective. > >> > What it does is called AMDF, and this method is old as a world. > >well, AMDF with selective terms in the sum run through a non-linear >function (the step function). > >> You DO realize that you are making a fool out of yourself, Vlad ? > >not to always come to Vlad's defense, but this is what i've been >saying about Dmitry's alg since 2004 or something. it used to be that >Google Groups could help me find these old posts, but it doesn't work >so well anymore. in fact, today Google Groups works so shitty that i >am not sure i can even post anymore. > >> >> Here is your textbook AMDF definition: >> >> AMDF(k) = Sum |s(i)-s(i+k)| >> >> Here is periodicity histogram (in it's simplest one-dimensional form): >> >> hist(k)=sum H(r-|s(i)-s(i+k)|) (where H is Heaviside, or unit step, >> function) >> >> Are you telling us that these two are the same ??? >> >> YES or NO ??? > >H(r-x) is a strictly decreasing function of x (r is a fixed >parameter). it is nothing other than running the difference terms >into a non-invertible non-linear function. since it's decreasing, >instead of looking for a minimum as you would for AMDF, Dmitry is >looking for a maximum after the sum. there are lot's of non-linear >functions, why is H(r-x) the best one for this purpose > >they are not the same, and since H(|x|-r) is not the same as |x| nor | >x|^2, we cannot say they are equivalent. but it *is* a subset of >A[??]DF where [??] is a function of the magnitude of the difference.Don't you means [??]MDF? Its using the magnitude difference, but its using a kind of twisted modal mean rather than an average.>Vlad's right about this. i can say this because i have looked at >Dmitry's paper and alg since 2002 or 2004 or whenever he first posted >about this.Steve
Reply by ●June 22, 20102010-06-22
>On Jun 21, 11:00 am, fatalist <simfid...@gmail.com> wrote: >> On Jun 21, 8:53 am, Vladimir Vassilevsky <nos...@nowhere.com> wrote: >> >> > Hello Dmitry Teres's friend, > >how do you know it's his friend? it's more likely Dmitry himself >posted this.I am not Dmitry. My name is Georgy Moshkin. I've found Dmitry's method in google.> >> >> > tmtlib wrote: >> > > I have implemented simple modification of Dmitry Terez frequencyestimation>> > > method and get awesome results: >> >> > How much is awesome? > >something a little past objective. > >... >> >> > > Incredible program. > >sounds objective. > >> > What it does is called AMDF, and this method is old as a world. > >well, AMDF with selective terms in the sum run through a non-linear >function (the step function). > >> You DO realize that you are making a fool out of yourself, Vlad ? > >not to always come to Vlad's defense, but this is what i've been >saying about Dmitry's alg since 2004 or something. it used to be that >Google Groups could help me find these old posts, but it doesn't work >so well anymore. in fact, today Google Groups works so shitty that i >am not sure i can even post anymore. > >> >> Here is your textbook AMDF definition: >> >> AMDF(k) = Sum |s(i)-s(i+k)| >> >> Here is periodicity histogram (in it's simplest one-dimensional form): >> >> hist(k)=sum H(r-|s(i)-s(i+k)|) (where H is Heaviside, or unit step, >> function) >> >> Are you telling us that these two are the same ??? >> >> YES or NO ??? > >H(r-x) is a strictly decreasing function of x (r is a fixed >parameter). it is nothing other than running the difference terms >into a non-invertible non-linear function. since it's decreasing, >instead of looking for a minimum as you would for AMDF, Dmitry is >looking for a maximum after the sum. there are lot's of non-linear >functions, why is H(r-x) the best one for this purpose > >they are not the same, and since H(|x|-r) is not the same as |x| nor | >x|^2, we cannot say they are equivalent. but it *is* a subset of >A[??]DF where [??] is a function of the magnitude of the difference. > >Vlad's right about this. i can say this because i have looked at >Dmitry's paper and alg since 2002 or 2004 or whenever he first posted >about this. > >r b-j >i will check admf. Also give windows program for analyzing mono wav files with Dmitry's method later. then maybe post implementation for adsp21xx dsp family, as an example for block floating point method fft replacement. I am sure that code will be much smaller than radix4.
Reply by ●June 22, 20102010-06-22
On Jun 22, 2:11=A0am, "tmtlib" <tmtlib@n_o_s_p_a_m.narod.ru> wrote:> >On Jun 21, 11:00 am, fatalist <simfid...@gmail.com> wrote: > >> On Jun 21, 8:53 am, Vladimir Vassilevsky <nos...@nowhere.com> wrote: > > >> > Hello Dmitry Teres's friend, > > >how do you know it's his friend? =A0it's more likely Dmitry himself > >posted this. > > I am not Dmitry. My name is Georgy Moshkin. I've found Dmitry's method in > google. > > > > > > >> > tmtlib wrote: > >> > > I have implemented simple modification of Dmitry Terez frequency > estimation > >> > > method and get awesome results: > > >> > How much is awesome? > > >something a little past objective. > > >... > > >> > > Incredible program. > > >sounds objective. > > >> > What it does is called AMDF, and this method is old as a world. > > >well, AMDF with selective terms in the sum run through a non-linear > >function (the step function). > > >> You DO realize that you are making a fool out of yourself, Vlad ? > > >not to always come to Vlad's defense, but this is what i've been > >saying about Dmitry's alg since 2004 or something. =A0it used to be that > >Google Groups could help me find these old posts, but it doesn't work > >so well anymore. =A0in fact, today Google Groups works so shitty that i > >am not sure i can even post anymore. > > >> Here is your textbook AMDF definition: > > >> AMDF(k) =3D Sum |s(i)-s(i+k)| > > >> Here is periodicity histogram (in it's simplest one-dimensional form): > > >> hist(k)=3Dsum H(r-|s(i)-s(i+k)|) =A0(where H is Heaviside, or unit ste=p,> >> function) > > >> Are you telling us that these two are the same ??? > > >> YES or NO ??? > > >H(r-x) is a strictly decreasing function of x (r is a fixed > >parameter). =A0it is nothing other than running the difference terms > >into a non-invertible non-linear function. =A0since it's decreasing, > >instead of looking for a minimum as you would for AMDF, Dmitry is > >looking for a maximum after the sum. =A0there are lot's of non-linear > >functions, why is H(r-x) the best one for this purpose > > >they are not the same, and since H(|x|-r) is not the same as |x| nor > >|x|^2, we cannot say they are equivalent. =A0but it *is* a subset of > >A[??]DF where [??] is a function of the magnitude of the difference. > > >Vlad's right about this. =A0i can say this because i have looked at > >Dmitry's paper and alg since 2002 or 2004 or whenever he first posted > >about this. > > i will check admf. > Also give windows program for analyzing mono wav files with Dmitry's meth=od> later. then maybe post implementation for adsp21xx dsp family, as an > example for block floating point method fft replacement. I am sure that > code will be much smaller than radix4.well, long ago i asked Dmitry for a MATLAB program that would run on any platform and not use MEX files. i never really got that. i personally don't think that any FFT method is a particular good method for pitch detection and i don't think that "block floating-point" has much to do with this issue. the whole point in estimating the fundamental frequency of a quasi- periodic waveform is in estimating the reciprocal of that, the (possibly slowly varying) *period* of that waveform. if it is perfectly periodic with period N, x[n] =3D x[n+N] for all n. then x[n] - x[n+N] =3D 0 and |x[n] - x[n+N]| =3D 0 as well as any power of that magnitude. if it's not perfectly periodic, but quite periodic, then f( |x[n] - x[n+N]| ) where f'(x) > 0 and f(0)=3D0 will be positive, but small for all n in the local vicinity of interest. f(x) is a strictly increasing function (some might be better than others, that's where all the different methods have their pros and cons), and we're gonna offset it so that f(0)=3D0. the whole idea is finding a lag, k, that makes that small in some mean sense. so, keeping it general, we want to find a lag, k, where Q(k) =3D SUM{ f( |x[n] - x[n+k]| ) * w[n] } n is minimum, and that k is a good candidate for N. w[n] is a window function (always non-negative) and can be a collection of Kronecker deltas so that it just defines which terms of the summation we add f( |x[n] - x[n+k]| ) and which terms we don't (because w[n] is 0). different methods will have different w[n] as well as different f(x) which is what makes them different. but the idea is the same and they all work on the *difference* of x[n] to x[n+k]. Q(k) is clearly non- negative and and Q(0) must be zero. now we can turn Q(k) upside-down and say instead of seeking a value k that minimizes Q(k), we want to maximize -Q(k). or we can add a constant bias and say we want to find a value k that maximizes R(k) =3D R(0) - Q(k) clearly R(k) <=3D R(0) for all k and if, for some value of k not terribly close to 0, if R(k) approaches R(0), then k is a good candidate for N. now R(0) is just some sort of bias and i can define another value, d, such that R(0) =3D SUM{ d * w[n] } n using the same summation and same window function w[n]. that means that R(k) =3D SUM{ ( d - f( |x[n] - x[n+k]| ) ) * w[n] } n and i can define a new strictly *decreasing* function g(x) such that g'(x) < 0 and g(0) =3D d. then we get g(x) =3D d - f(x) and R(k) =3D SUM{ g( |x[n] - x[n+k]| ) * w[n] } n and, again, we want to find a value k (not approaching 0) that maximizes R(k). such a k is a good candidate for N. now, i assert to you, Georgy Moshkin, that Dmitry's method is no more than that. can you tell me what the function g(x) is and what the window w[n] is for Dmitry's method? now it turns out that autocorrelation is a lot like R(k) where f(x) =3D 1/2 * x^2 and R(0) is the sum of x[n]^2. so autocorrelation and the ASDF (Average Squared Difference Function) have a lot to do with each other. one will maximize when the other minimizes. the lesson is that with variations, they are all based on the same concept: find a lag k so that x[n] and x[n+k] are the most identical functions. there are a few other issues (like avoiding octave errors), but they're all like that, *including* Dmitry's method. it's no more novel than that. Dmitry's method is a variation on the autocorrelation idea, even though it is not the autocorrelation as defined. now many pitch detection algorithms define the function f(x) (or g(x)) in such a way that there is a "dead zone" in the function and that small differences do not add anything to the summation. Dmitry's use of the step function does that also. that's okay, but it *does* throw away information because it is not invertible. i am not so convinced that such is a good idea because i can think up a periodic function of period N that *looks* to these particular algs (including Dmitry's method) like it has period N/2 when it really doesn't have that period. and the reason we suspected you were Dmitry is that objective phrases like "get awesome results" sounds like the same salesman that Dmitry was when he first brought his method to our attention. Vlad is right. i've been trying to get Dmitry to objectively present and test his method since he first announced it here in 2004 or maybe earlier. r b-j
