🚀 go-pugleaf

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 have the algorithm in
>front of me, and some code that works for a large sample, but am
>having problems getting the thing to reliably work on shorter
>samples of data (30ms, where the signal only repeats only twice).
>
>Thanks!
>
>-- 
>-----------------------------------------------------------------------------
>  Who:  Greg Bell                            Address:  gbell@ucsd.edu
> What:  EE hobbyist and major                  Where:  UC San Diego
>-----------------------------------------------------------------------------

	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). The reason why autocorrelation method fails  for
short range data is due to the fact that it has edge effects of the implict 
window it uses in the algoritm formulation.

	Well if you are dealing with narrowband signals, and have short data
range then the best bet is probably the Burg's method. It is very much
like the Levinson's recursion for autocorrelation, only faster and it
does not suffer from the 'edge-effect' that autocorrelation does. 
	You can find useful information on the Burg's method in
"Advanced Digital Signal Processing" Edited by Oppenheim and Lim , under
chapter 2.

Pankaj Tyagi

---------------------------------------------------------------------
p.s. I had a C code for Burg's algorithm and I can't trace it now,
	I'll email it to you if I can find it.  pt
---------------------------------------------------------------------

>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.

>>>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.
>

Everybody here has really been talking about periodicity detectors and NOT
pitch detection.

It is important to realize that pitch is a perceptual quality.  An official
definition of pitch (ANSI?) defines pitch as that quantity that humans would
perceive and try to sing to.  It is not defined in terms of the periodicities
of the signal....although if the signal is periodic then the pitch is
usually the same as the fundamental.  Once you add a bit of noise then your
signal is not periodic.

That said, you need more than two cycles of a signal to perceive its pitch!
I just tried it.  I synthesized (with MatLab) a signal that looks like
	1 second of silence 
	a small number of cycles of 220Hz sine wave
	1 second of silence
If there is only one or two cycles then all one hears is a click.  There is
nothing in this sound that would let me hear a pitch.  Not until I get to 
four or five cycles does it start to sound musical so I can assign a pitch
to it.  Try it, if you don't believe me.

It is also important to realize that pitch is not a unique quantity.  There
are many examples where it is possible to perceive more than one pitch.  
Shepard tones (on the ASA Auditory Demonstrations CD) and creaky voice are
two common examples.  The engineering world likes to reduce pitch to a 
single number but that just isn't realistic.  If your system outputs a 
single number then it is probably a periodicity detector and not a pitch
detector.

If you want to know more about pitch there is a book that reviews most of
the pre-1983 literature
	Hess, Wolfgang. PITCH DETERMINATION OF SPEECH SIGNALS (Berlin ;
	       Springer-Verlag, 1983)

Within the psychoacoustics world the Journal of the Acoustical Society
of America has a few articles a year talking about pitch.  There seems
to be two camps, the place based people led by Julius Goldstein and the
autocorrelation people.  I think both of these approaches are flawed and
a hybrid approach was described in my 1990 ICASSP paper and an upcoming
JASA article by Ray Meddis.

						Malcolm Slaney
						Apple Perception Group

In article <1991Apr6.062906.11886@cs.cmu.edu> dandb+@cs.cmu.edu (Dean Rubine) writes:
>
>    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.

Exactly... I wasn't sure what PT was talking about!  This is
actually part of an LPC analysis package, but you need to determine
whether a signal is periodic or not, and if so, its period in order
to feed this info to one of TI's LPC synthesizers.
>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

Also called, according to my book, AMDF for Average Magnitude
Difference Function.

>	1 It seems to me that windowing will make it harder to determine
>	  periodicity so should be avoided.

It does make it harder to determine the periodicity, but apparently
it is necessary.  There are methods that do not require windowing,
but the autocorr. method is not one of them.

>	 
>	2 For a valid determination of the extrema the same number of terms
>	  needs to be present in the sum for each m.
>

Hmm... good point.  My book says each sum goes from n=1 to N where N
is the length of the sample.  This didn't make sense since one of
the terms is s[n+k] so you go out of the range of samples.  So, I
made my sum to from n=1 to N-k.  This doesn't follow what you are
saying, but it did work well for a larger segment.  I'll try your
guidelines for my troublesome short segments.

I'll have to read you guidelines for the number of sum terms later
when I can look 'em over a little more carefully.

Thanks for the input!


-- 
-----------------------------------------------------------------------------
  Who:  Greg Bell                            Address:  gbell@ucsd.edu
 What:  EE hobbyist and major                  Where:  UC San Diego
-----------------------------------------------------------------------------