Cubic Spline Interpolation and Zero Crossing Analysis

Hi Folks

Hope this isn't OT for this forum.

I'm using zero-crossing analysis to extract instantaneous frequency from a signal recorded from a 
frequency-division bat detector. The detector itself uses zero-crossing decimation to divide the 
frequency, so dominant frequency is the only information available in the signal. (The detector 
filters the output and re-applies the original amplitude envelope, so I'm not dealing with a square 
wave signal).

I'm getting pretty good results using linear interpolation to determine the times of the zero 
crossings but I'm sure that I would get less noisy results (particularly at higher frequencies) 
using a cubic spline interpolation. However this is proving less easy than I had hoped and I really 
don't know how to approach the problem.

I would very much appreciate any advice that will point me in the right direction.

Regards

David 

On Jun 27, 6:36 am, "David Lee"
<davidlee_malv...@dontusethisbit.hotmail.com> wrote:
>
> I'm using zero-crossing analysis to extract instantaneous frequency from a signal recorded from a
> frequency-division bat detector.
>
> I'm getting pretty good results using linear interpolation to determine the times of the zero
> crossings but I'm sure that I would get less noisy results (particularly at higher frequencies)
> using a cubic spline interpolation. However this is proving less easy than I had hoped and I really
> don't know how to approach the problem.
>
> I would very much appreciate any advice that will point me in the right direction.
>

Assuming that your data is sampled at regularly-spaced intervals, I
might try using an FFT to upsample (and interpolate).  Then do a
simple zero-crossing analysis.  The basic plan follows:

1.  Take a contiguous set of samples a power-of-2 in size, and big
enough that you are pretty sure it contains several zero-crossings.

2.  FFT the sample set (yielding a array of complex numbers the same
size as the sample set).  At this point, you can use the raw FFT
coefficients, or, if you know something about what the spectrum
"should" look like, you can filter the FFT coefficients to suppress
known noise.

3.  Create an array of complex 0's that's 4, 8, or even 16 times the
size of the array of FFT coefficients (the factor you choose
determines the number of interpolated points between sample points).

4.  Break the array of FFT coefficients in half.  Copy the first half
to the beginning of the 0-array, and the last half to the end of the 0-
array.  Inverse FFT the result of this operation.

5.  Perform your zero-crossing analysis on the result of (4) except
you shouldn't need to do any linear interpolation, just average the
time values corresponding to the the points bracketing the zero-
crossings.

6.  Go back to step 1 and process the next segment.  You may need to
add some logic for pasting segments together (if the current segment
ends below zero and the next segment begins above zero, a zero
crossing happened in the junction between the two segments).

On Jun 27, 5:05 am, John Hadstate <jh113...@hotmail.com> wrote:
> On Jun 27, 6:36 am, "David Lee"
>
> <davidlee_malv...@dontusethisbit.hotmail.com> wrote:
>
> > I'm using zero-crossing analysis to extract instantaneous frequency from a signal recorded from a
> > frequency-division bat detector.
>
> > I'm getting pretty good results using linear interpolation to determine the times of the zero
> > crossings but I'm sure that I would get less noisy results (particularly at higher frequencies)
> > using a cubic spline interpolation. However this is proving less easy than I had hoped and I really
> > don't know how to approach the problem.
>
> > I would very much appreciate any advice that will point me in the right direction.
>
> Assuming that your data is sampled at regularly-spaced intervals, I
> might try using an FFT to upsample (and interpolate).  Then do a
> simple zero-crossing analysis.  The basic plan follows:

Use an FFT, but don't bother upsampling.  Do what phase
vocoders do, and use the FFT to get an estimate of the phase
of the zero crossings.  This is easiest if you use something
like FFTShift to reference the FFT phases to the center of
the FFT aperture.  You can then interpolate *both* frequency
and phase relative to the center of the window, and the two
will tell you where the zero-crossing closest to the center
of the window is located, according to regression against
the two nearest sinusoids, weighted across the entire window.
This is what makes the phase vocoder technique for estimating
frequency very resistant to local noise around the zero
crossing.  You can use fairly small FFT sizes since you are
only interested in phase from the FFT, not bin frequency.

Move the FFT window and repeat to get another zero-crossing
time.  Use the two zero-crossings and a rough estimate of the
period to get a more accurate frequency estimate.



IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M
 http://www.nicholson.com/rhn/dsp.html

On Jun 27, 6:36 am, "David Lee"
<davidlee_malv...@dontusethisbit.hotmail.com> wrote:
> Hi Folks
>
> Hope this isn't OT for this forum.
>
> I'm using zero-crossing analysis to extract instantaneous frequency from a signal recorded from a
> frequency-division bat detector. The detector itself uses zero-crossing decimation to divide the
> frequency, so dominant frequency is the only information available in the signal. (The detector
> filters the output and re-applies the original amplitude envelope, so I'm not dealing with a square
> wave signal).
>
> I'm getting pretty good results using linear interpolation to determine the times of the zero
> crossings but I'm sure that I would get less noisy results (particularly at higher frequencies)
> using a cubic spline interpolation. However this is proving less easy than I had hoped and I really
> don't know how to approach the problem.
>
> I would very much appreciate any advice that will point me in the right direction.
>
> Regards
>
> David

"I'm using zero-crossing analysis to extract instantaneous frequency
from a signal ..." ???

"so dominant frequency is the only information available in the
signal" ???

Heck, what is it you are dealing with ?

"Ron N." <rhnlogic@yahoo.com> wrote in message 
news:1182966144.243478.322450@i13g2000prf.googlegroups.com...
> On Jun 27, 5:05 am, John Hadstate <jh113...@hotmail.com> 
> wrote:
>> On Jun 27, 6:36 am, "David Lee"
>>
>> <davidlee_malv...@dontusethisbit.hotmail.com> wrote:
>>
>> > I'm using zero-crossing analysis to extract 
>> > instantaneous frequency from a signal recorded from a
>> > frequency-division bat detector.
>>
>> > I'm getting pretty good results using linear 
>> > interpolation to determine the times of the zero
>> > crossings but I'm sure that I would get less noisy 
>> > results (particularly at higher frequencies)
>> > using a cubic spline interpolation.
>>
>> Assuming that your data is sampled at regularly-spaced 
>> intervals, I
>> might try using an FFT to upsample (and interpolate). 
>> Then do a
>> simple zero-crossing analysis.
>
> Use an FFT, but don't bother upsampling.  Do what phase
> vocoders do, and use the FFT to get an estimate of the 
> phase
> of the zero crossings.  This is easiest if you use 
> something
> like FFTShift to reference the FFT phases to the center of
> the FFT aperture.  You can then interpolate *both* 
> frequency
> and phase relative to the center of the window, and the 
> two
> will tell you where the zero-crossing closest to the 
> center
> of the window is located, according to regression against
> the two nearest sinusoids, weighted across the entire 
> window.
> This is what makes the phase vocoder technique for 
> estimating
> frequency very resistant to local noise around the zero
> crossing.  You can use fairly small FFT sizes since you 
> are
> only interested in phase from the FFT, not bin frequency.
>

This sounds like a very clever technique but I can't 
visualize how you would implement it.  How do you get the 
zero crossings from phase and frequency analysis, and how do 
you improve noise immunity when the FFT coefficients are 
directly interchangeable with the time-domain samples?  Are 
you relying on some a-priori knowledge that you can throw 
away some of the FFT terms because they represent "noise"?

On Jun 27, 3:05 pm, "John E. Hadstate" <jh113...@hotmail.com> wrote:
> "Ron N." <rhnlo...@yahoo.com> wrote in message
> news:1182966144.243478.322450@i13g2000prf.googlegroups.com...
...
> > On Jun 27, 5:05 am, John Hadstate <jh113...@hotmail.com>
> > wrote:
> >> On Jun 27, 6:36 am, "David Lee"
>
> >> <davidlee_malv...@dontusethisbit.hotmail.com> wrote:
>
> >> > I'm using zero-crossing analysis to extract
> >> > instantaneous frequency from a signal recorded from a
> >> > frequency-division bat detector.
>
> >> > I'm getting pretty good results using linear
> >> > interpolation to determine the times of the zero
> >> > crossings but I'm sure that I would get less noisy
> >> > results (particularly at higher frequencies)
> >> > using a cubic spline interpolation.
>
> >> Assuming that your data is sampled at regularly-spaced
> >> intervals, I
> >> might try using an FFT to upsample (and interpolate).
> >> Then do a
> >> simple zero-crossing analysis.
>
> > Use an FFT, but don't bother upsampling.  Do what phase
> > vocoders do, and use the FFT to get an estimate of the
> > phase
> > of the zero crossings.  This is easiest if you use
> > something
> > like FFTShift to reference the FFT phases to the center of
> > the FFT aperture.  You can then interpolate *both*
> > frequency
> > and phase relative to the center of the window, and the
> > two
> > will tell you where the zero-crossing closest to the
> > center
> > of the window is located, according to regression against
> > the two nearest sinusoids, weighted across the entire
> > window.
> > This is what makes the phase vocoder technique for
> > estimating
> > frequency very resistant to local noise around the zero
> > crossing.  You can use fairly small FFT sizes since you
> > are
> > only interested in phase from the FFT, not bin frequency.
>
> This sounds like a very clever technique but I can't
> visualize how you would implement it.  How do you get the
> zero crossings from phase and frequency analysis,

Note that the OP wasn't interested in the zero crossing
locations per se, but only in using them for "instantaneous"
fundamental frequency estimation.  Thus the time difference
between any two identical phase references will serve as
a proxy for the time difference between two zero crossings
of a (close enough to) periodic waveform.  A complex fft
reveals phase information; FFTShift references it to the
center of the fft aperture where the phase is consistent
with the referenced waveform phase.

> and how do
> you improve noise immunity when the FFT coefficients are
> directly interchangeable with the time-domain samples?

By using an entire FFT window instead of just 3 adjacent
points for the interpolation.  A Kaiser or Gaussian
window may allow one to choose the number of points.

> Are
> you relying on some a-priori knowledge that you can throw
> away some of the FFT terms because they represent "noise"?

Yes. A phase vocoder depends on the assumption that one
is looking at a waveform that is "mostly" periodic. If
the waveform is not periodic (say, completely different
looking between each pair of positive zero crossings),
then a phase vocoding technique will likely fail.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

fizteh89 wrote

> "I'm using zero-crossing analysis to extract instantaneous frequency
> from a signal ..." ???
>
> "so dominant frequency is the only information available in the
> signal" ???
>
> Heck, what is it you are dealing with ?
>

Exactly what I said in my original post if you read the bit you snipped between the two quotations!

"A signal recorded from a frequency-division bat detector. The detector itself uses zero-crossing 
decimation to divide the frequency, so dominant frequency is the only information available in the 
signal. (The detector filters the output and re-applies the original amplitude envelope, so I'm not 
dealing with a square wave signal)."

I would have thought that would be reasonably explanatory.

However, the detector divides the frequency of the original ultrasonic FM bat vocalization by a 
suitable factor (normally a factor of 10 in my case). The detector output is filtered to restore a 
sinusoidal signal and the original amplitude of the original signal is also restored. Since 
frequency division is carried out by zero crossing analysis and decimation, all harmonic information 
is lost apart from the dominant frequency component. Hence there is nothing to be gained by using 
the traditional FFT analysis tools to produce a spectrogram and much better time/frequency 
resolution can be achieved using zero-crossing analysis.

As I said, I am getting reasonably good results by determining the times of the zero crossings from 
simple linear interpolation but this does lead to noise, particularly at higher frequencies where 
there are few samples per half cycle. Sampling rate is usually 44.1kHz and the frequency of the bat 
echolocation vocalizations can be as high as 110kHz.

Is that clearer?

David

David Lee wrote...
> Sampling rate is usually 44.1kHz and the frequency of the bat echolocation vocalizations can be as 
> high as 110kHz.

That's the original frequency of course - I'm not trying to beat Nyquist!  I'm dealing with the 
frequency divided signal (sampled at 44.1kHz)  which can contain frequencies as high as 11kHz.

David 

On Jun 27, 7:02 pm, "David Lee"
<davidlee_malv...@dontusethisbit.hotmail.com> wrote:
> David Lee wrote...
> > Sampling rate is usually 44.1kHz and the frequency of the bat echolocation vocalizations can be as
> > high as 110kHz.
>
> That's the original frequency of course - I'm not trying to beat Nyquist!  I'm dealing with the
> frequency divided signal (sampled at 44.1kHz)  which can contain frequencies as high as 11kHz.

What's the maximum rate-of-change of the frequency
which you're trying to track?

Ron N wrote...
> David Lee:
>> Sampling rate is usually 44.1kHz and the frequency of the bat echolocation
>> vocalizations can be as high as 110kHz.
>>
>> That's the original frequency of course - I'm not trying to beat Nyquist!  I'm
>> dealing with the frequency divided signal (sampled at 44.1kHz)  which can
>> contain frequencies as high as 11kHz.

> What's the maximum rate-of-change of the frequency
> which you're trying to track?

A Natterer's bat, for example, uses an extremely linear broadband frequency sweep and can sweep from 
above 110kHz to below 20kHz  (ie 11 to 2 kHz after division) in times around 2.5 to 4ms. Insect 
"vocalizations" can exhibit much higher sweep rates - and maximum rate of change of frequency is one 
of the criteria used in the automatic recognition of bat calls to eliminate insect sounds.

The purpose of the time/frequency representation of calls is identification of species and so the 
requirement is to be able to identify characteristic features of the calls and not to extract 
accurate detailed parameters - for which purpose we normally use FFT-based tools to analyse the 
original call (usually captured as a 10x time-expanded signal so as to be audible and easily handled 
as an audio sound file).

Another major issue is that the recordings can be up to several hours in length, so a rapid analysis 
technique is required to extract frequency data and filter out the bat-call candidates from the 
background noise.

There is a commercial bat detector system - the Anabat - that  carries out the analysis in real-time 
and can be left unattended in the field for months at a time (provided that it isn't blown up by the 
bomb disposal squad as happened recently here in the UK when the ecologists concerned failed to 
properly label their equipment!)  What I am trying to do is to extract zero-crossing data from a 
much cheaper, more accessible, detector into a form that can be used with the same freely available 
software as is used for the commercial device.

Using linear interpolation to determine zero-crossing times, I am already obtaining acceptable 
results. I was just looking for a staightforward and rapid way of refining the interpolation and 
thought that a cubic spline may fit the bill.

Thanks for your interest

David