FPGA Central

I'm trying to find a way to detect the pitches of fundamental
frequencies of harmonic content shown in log-scale FFTs. Basically,
all I have is the log-scale FFTs of bits of sound which may or may not
contain harmonic content, and I want the output to look like the
result of cepstral analysis. This is what it looks like
http://photosounder.com/misc/comp.dsp_fig1.png (and from such an input
ideally the result would be a fairly sharp peak in the place of the
leftmost peak, surrounded by noise)

Because in log frequency scale harmonics have a spacing that is
independent from their fundamental frequency (i.e. the distance
between the Nth harmonic and the N+1th harmonic is always the same) I
thought a great way to get to what I want would be to convolve the log-
FFT with a kernel that would somehow stack up all the harmonic peaks
on top of each other and leave the surroundings clean. However I
really don't have any idea how to come up with such a kernel. I
already tried cross-correlating with a series of peaks similar to the
figure above but as one might expect all I obtained was a wide and
blurry mess. It don't _have_ to solve it using convolution, I'm open
to any alternative, it just seems to me like there would be such a
convolution kernel that would give me what I want.

As for the characteristics of what it would be used for, it might be
on any type of input sound really. The log-FFT might represent 30
oboes playing simultaneously, or just a bunch of noise, or some
anharmonic sound like a bell (which "pitch" I don't want to detect).
Ultimately I don't even need to isolate and determine precisely how
many different discrete fundamental pitches are present, it's more
about getting a cepstral visualisation. Also I don't necessarily have
access to the original sound nor the original linear-scale FFT, so
really all I have to base the analysis from is log-scale FFTs.

Thanks in advance,

Michel Rouzic

On 10 Okt, 15:07, Michel Rouzic <Michel0...@yahoo.fr> wrote:
> I'm trying to find a way to detect the pitches of fundamental
> frequencies of harmonic content shown in log-scale FFTs. Basically,
> all I have is the log-scale FFTs of bits of sound which may or may not
> contain harmonic content, and I want the output to look like the
> result of cepstral analysis. This is what it looks likehttp://photosounder.com/misc/comp.dsp_fig1.png(and from such an input
> ideally the result would be a fairly sharp peak in the place of the
> leftmost peak, surrounded by noise)

So when you say 'log scale FFT' you mean the frequency is
logarithmic? This is important, since cepstra are based on
computing the DFT of the log magnitude of the spectrum.

> Because in log frequency scale harmonics have a spacing that is
> independent from their fundamental frequency (i.e. the distance
> between the Nth harmonic and the N+1th harmonic is always the same) I
> thought a great way to get to what I want would be to convolve the log-
> FFT with a kernel that would somehow stack up all the harmonic peaks
> on top of each other and leave the surroundings clean. However I
> really don't have any idea how to come up with such a kernel.

This is what the cepstrum does for the linear-frequency log
magnitude spectrum: The log mag spectrum with many harmonic
features will look like a regular spike train. DFT this spike
train and find the period between spikes (which are the
harmonics). Find that period, and you have found your
fundamental.

....
> Also I don't necessarily have
> access to the original sound nor the original linear-scale FFT, so
> really all I have to base the analysis from is log-scale FFTs.

Hmmm.... try this with the linear-frequency DFT first.
Only when (if...) you get that to work, attempt to adapt
to log-frequency spectra.

Rune

On Oct 10, 6:07*am, Michel Rouzic <Michel0...@yahoo.fr> wrote:
> I'm trying to find a way to detect the pitches of fundamental
> frequencies of harmonic content shown in log-scale FFTs.

Looks like you have a log-log plot of the FFT. If you convert
back to just a log magnitude plot, the harmonic peaks will be
periodically spaced on the X axis instead of log spaced.

Then you can try either cepstral analysis (using another FFT to
try and separate out the fundamentals and their filter envelopes),
or maybe harmonic product spectrum analysis to find a train of
frequency peaks that look like they might be related harmonics.


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

Rune Allnor wrote:
> So when you say 'log scale FFT' you mean the frequency is
> logarithmic?

Oh yeah, logarithmic frequency, not logarithmic magnitude.

> Hmmm.... try this with the linear-frequency DFT first.
> Only when (if...) you get that to work, attempt to adapt
> to log-frequency spectra.

Well, the thing is, the two things are entirely different. I mean,
making my log FFT go linear, do the cepstrum thing and then making it
go from linear to logarithmic again is a solution I keep in mind, but
that's not a very elegant or efficient one. And that's a different
problem. With a linear FFT, you look for regularly spaced peaks, and
then measure their spacing. With a log-frequency scale FFT, you look
for a fixed pattern of peaks.

When you think about it, it's just pattern recognition. Surely there
must be a solution to recognising that pattern other than using the
special property of that pattern that if you apply a transform to it
(log scale to linear scale) then you have something with a fixed
periodicity. Like, how would you do it if you had to detect a precise
fixed pattern of peaks but that they had a much more arbitrary and
unremarkable spacing? Normally I know that you can detect any
arbitrary pattern by cross-correlation (seems to work quite well with
images) but in this case cross-correlation doesn't even remotely work,
probably because it's all a bunch of peaks.

On Oct 10, 1:58*pm, Michel Rouzic <Michel0...@yahoo.fr> wrote:
> When you think about it, it's just pattern recognition. Surely there
> must be a solution to recognising that pattern ...

That line seems vaguely familiar. I think from a book on AI
written about 40 years ago...

I prefer to use one of the punch lines to mathematician jokes:
"now I've reduced ... to a previously solved problem".


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

Michel Rouzic wrote:


>
> Oh yeah, logarithmic frequency, not logarithmic magnitude.
> When you think about it, it's just pattern recognition. Surely there
> must be a solution to recognising that pattern

Those solutions are more or less empirical and based on features. Such
as take the largest peak, then find the largest peaks next to it, check
the frequency ratios, check if there are the other peaks with the same
relation, repeat until the best result is found.

> other than using the
> special property of that pattern that if you apply a transform to it
> (log scale to linear scale) then you have something with a fixed
> periodicity. Like, how would you do it if you had to detect a precise
> fixed pattern of peaks but that they had a much more arbitrary and
> unremarkable spacing? Normally I know that you can detect any
> arbitrary pattern by cross-correlation (seems to work quite well with
> images) but in this case cross-correlation doesn't even remotely work,
> probably because it's all a bunch of peaks.

Why are you insisting on doing the things in the difficult way?


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

R.Nicholson wrote:
> On Oct 10, 1:58*pm, Michel Rouzic <Michel0...@yahoo.fr> wrote:
> > When you think about it, it's just pattern recognition. Surely there
> > must be a solution to recognising that pattern ...
>
> That line seems vaguely familiar. I think from a book on AI
> written about 40 years ago...
>
> I prefer to use one of the punch lines to mathematician jokes:
> "now I've reduced ... to a previously solved problem".

I'm not sure whether you're telling me that I just have to read about
pattern recognition to solve my problem or whether you're trying to
say that to make the problem come down to a pattern recognition
problem doesn't get me any closer to the solution.

As for the cross-correlation idea, I've done some more thinking and
I'm not sure that can possibly work with peaks that have widely
inconsistent and variable intensities.. Well I don't know, to be
honest I'm not so familiar with such problems and I thought you guys
might have a better clue than I do ;-).

Vladimir Vassilevsky wrote:
> Michel Rouzic wrote:
>
>
> >
> > Oh yeah, logarithmic frequency, not logarithmic magnitude.
> > When you think about it, it's just pattern recognition. Surely there
> > must be a solution to recognising that pattern
>
> Those solutions are more or less empirical and based on features. Such
> as take the largest peak, then find the largest peaks next to it, check
> the frequency ratios, check if there are the other peaks with the same
> relation, repeat until the best result is found.

Yeah, I'm thinking about such solutions, looks like it's the way to
go. Although I must say I'm almost surprised there isn't a more
established and conventional to go about doing that. Although actually
I suppose I could adapt the concept of the harmonic product spectrum
to this. Just one thing though, if the harmonic product spectrum works
by adding logarithmic values, isn't it the same as multiplying the
linear values? If so I wonder why they insist on going through the
logarithmic stuff, and also why they make it a sum and not an
average.. Also there's one problem with it. What if one harmonic is at
0? I've seen it in speech, sometimes the first harmonic has a blank
spot. If I use something similar to harmonic product spectrum,
wouldn't a single 0 ruin it all? Unless I have a hard limit...

> > other than using the
> > special property of that pattern that if you apply a transform to it
> > (log scale to linear scale) then you have something with a fixed
> > periodicity. Like, how would you do it if you had to detect a precise
> > fixed pattern of peaks but that they had a much more arbitrary and
> > unremarkable spacing? Normally I know that you can detect any
> > arbitrary pattern by cross-correlation (seems to work quite well with
> > images) but in this case cross-correlation doesn't even remotely work,
> > probably because it's all a bunch of peaks.
>
> Why are you insisting on doing the things in the _elegant_ way?
Fixed your post. I insist on researching an elegant solution when I
think there may be one because I don't want to settle for the first
mediocre-but-viable solution. If I settled for mediocre but viable
solutions then I'd be using the same crappy algorithms as my
competitors and I'd wouldn't be any better off. Taking a log frequency
scale FFT, making it linear, FFTing it and then making it log
frequency scaled again is far from elegant, not to mention nowhere
near as computationally efficient as whatever the hell you might want
to do with just the log FFT as it is. That's viable, but still a
mediocre solution, so I can't settle for that.

On Oct 11, 4:44*am, Michel Rouzic <Michel0...@yahoo.fr> wrote:
> Just one thing though, if the harmonic product spectrum works
> by adding logarithmic values, isn't it the same as multiplying the
> linear values? If so I wonder why they insist on going through the
> logarithmic stuff, and also why they make it a sum and not an
> average.. Also there's one problem with it. What if one harmonic is at
> 0? I've seen it in speech, sometimes the first harmonic has a blank
> spot. If I use something similar to harmonic product spectrum,
> wouldn't a single 0 ruin it all? Unless I have a hard limit...

You probably shouldn't let frequency magnitude bins below some noise
floor affect your harmonic product spectrum result, else the
"harmonics"
of the very 1st FFT bin would contain the total non-DC energy of your
entire signal, and thus be the maxima. But you will need some way of
estimating what the current noise floor might be.


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