Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!ub!uhura.cc.rochester.edu!rochester!pt.cs.cmu.edu!o.gp.cs.cmu.edu!dandb
From: dandb+@cs.cmu.edu (Dean Rubine)
Newsgroups: comp.dsp
Subject: Re: Autocorrelation Pitch Tracker
Message-ID: <1991Apr6.062906.11886@cs.cmu.edu>
Date: 6 Apr 91 06:29:06 GMT
References: <17823@sdcc6.ucsd.edu> <78395@bu.edu.bu.edu>
Sender: netnews@cs.cmu.edu (USENET News Group Software)
Organization: School of Computer Science, Carnegie Mellon
Lines: 91

>In article <17823@sdcc6.ucsd.edu> gbell@sdcc13.ucsd.edu (Greg Bell) writes:
>>Does anybody out there have experience implementing the
>>autocorrelation method of pitch detection? 

    I've played around with these, but not for really short signals.

In article <78395@bu.edu.bu.edu> pankaj@bass.bu.edu (Pankaj Tyagi) writes:
>	The autocorrelation algorithm is not suited for pitch-detection/
>spectral estimation for short range data. Try covariance method if you are
>sure that the data is bound to give a stable system(stability in covariance
>method is not guaranteed).

    I may be wrong, but I think Greg Bell is not referring to the
autocorrelation method for doing LPC (as Pankaj Tyagi seems to imply),
but something much simpler.

    In the autocorrelation method of pitch dectection, one actually computes
the autocorrelation of a signal, and then identifies those lags for which the
value of the autocorrelation is maximal.  A periodic signal will have peaks in
its autocorrelation at multiples of the period.  This method returns an
integer number of samples for the period; various methods can be tried to
interpolate for a more accurate period.

    There's also a comb-filter-based method that's kind of a poor man's
autocorrelation.  Here, for various delays, the signal is subtracted from
a delayed copy of itself and the sum of absolute values of the result
computed.  This sum will be show minima for delays equal to the multiples
of the period.  It is thus very similar to the autocorrelation method,
but requires no multiplies, so is often preferred.

    Summarizing, the comb filter method computes the m which minimizes

     	sum_over_n |x[n] - x[n-m]|

     The autocorrelation methods looks for the m which maximizes

     	sum_over_n x[n] * x[n-m]

    I'll talk about the bounds on the summation shortly.

    As for the effectiveness of these methods on really short pieces of
data there's probably not much hope.  To attempt to make it work, I 
offer the following suggestions.  My comments apply to both the auto-
correlation and comb-filter methods.

	1 It seems to me that windowing will make it harder to determine
	  periodicity so should be avoided.
	 
	2 For a valid determination of the extrema the same number of terms
	  needs to be present in the sum for each m.

	3 No term in the sum should ever use an x outside the range of
	  samples you have.  (In other words, don't pad your input with
	  zeros or anything else).

        4 The number of terms in the sum has to be at least the number of
	  samples in one period of the signal.  Since this is unknown, a
	  maximum period (minimum pitch) must be assumed. 

    Assuming the length of the signal is N, the above considerations imply
that the maximum period that may be detected is M=N/2.  Thus I suggest 
you look for 1 <= m <= M that minimizes

     	sum(from n=M to 2M-1) |x[n] - x[n-m]|

    This method could be refined further: once you find an m that gives a
global minimum you could check m/2, m/3, m/4, etc. to see if any are local
minima, to avoid settling on a period that's a multiple of the real period. 
Anyway, I don't have much faith in these methods.  Pankaj Tyagi's post could
be interpreted as a suggestion that maximum entropy or linear prediction
methods be tried for pitch detection on short samples.  I don't know if they
will work well or not.  I do know they're much more complicated than the
autocorrelation methods discussed so far, and might be out of the question if
you're trying to do some real time thing.   

    Well, I've babbled on much too long, especially given that I don't
really know what the particular problem is and I'm not that sure the
term "autocorrelation method of pitch detection" means to you what it means
to me.

    Hope this helps anyway.  Thanks for given me the opportunity to
procrastinate.

	Dean


--
ARPA:       Dean.Rubine@CS.CMU.EDU	
PHONE:	    412-268-2613		[ Free if you call from work ]
US MAIL:    Computer Science Dept / Carnegie Mellon U / Pittsburgh PA 15213
DISCLAIMER: My employer wishes I would stop posting and do some work.