Logarithmic Interpolation

Michel Rouzic wrote:
> Ron N. wrote:
> > Any logarithmic or even random point can be
> > interpolated from a DFT spectrum by sinc interpolation.
>
> now I'm not really sure about what you mean, if you mean that we can
> interpolate a signal which sample rates varies with differently sized
> sincs, ok,

No.  I'm only talking about samples from bandlimited signals
at a constant sample rate, and where the sinc kernel used for
interpolation is identical.

Sinc interpolation will allow you to rescale a linear time or
frequency axis arbitrarily (to log domain for instance).


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

Michel Rouzic wrote:
> Rune Allnor wrote:
> > I can't, off the top of my head, see an application other than
> > graphical reprsentations to humans, that would benefit from
> > a direct computaton of te DFT with a logarithmic frequency
> > scale.
>
> I didn't wanna talk about this too much, because I rather realize by
> myself if it's a dumb idea than be told, but my plan is to *try* using
> that to perform pitch shift/time stretch.
>
> my basic idea is, get the FFT of the signal you want to shift,
> interpolate the FFT logarithmically, shift the contents towards the
> left or the right depending on what you want to obtain, interpolate
> back to linear form, IFFT. of course, i'm definitly not sure and quite
> sceptical about the odds of obtaining the wanted result, but I think
> it's worth trying.

I think that's been tried.  You will find that shifting the log FFT
results will produce phase mismatches.  These phase errors will
probably not only smear some audio data in the time domain, but
produce harsh  discontinuities between most FFT frame boundries.
Do a Google search on phase vocoder algorithms for some methods
which have been tried to partially solve these problems.


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

Michel Rouzic wrote:

> I didn't wanna talk about this too much, because I rather
> realize by myself if it's a dumb idea than be told, but my plan
> is to *try* using that to perform pitch shift/time stretch.
> 
> my basic idea is, get the FFT of the signal you want to shift,
> interpolate the FFT logarithmically, shift the contents towards
> the left or the right depending on what you want to obtain,
> interpolate back to linear form, IFFT. of course, i'm definitly
> not sure and quite sceptical about the odds of obtaining the
> wanted result, but I think it's worth trying.

Since adding to log frequency is the same as multiplying linear 
frequency you can get the same thing with just one interpolator,
used to resample the scaled spectrum.


Martin

-- 
A trick that is used more than once is called a method.
--Ron Getoor paraphrasing George Polya and Gabor Szego

Martin Eisenberg wrote:
> Michel Rouzic wrote:
>
> > I didn't wanna talk about this too much, because I rather
> > realize by myself if it's a dumb idea than be told, but my plan
> > is to *try* using that to perform pitch shift/time stretch.
> >
> > my basic idea is, get the FFT of the signal you want to shift,
> > interpolate the FFT logarithmically, shift the contents towards
> > the left or the right depending on what you want to obtain,
> > interpolate back to linear form, IFFT. of course, i'm definitly
> > not sure and quite sceptical about the odds of obtaining the
> > wanted result, but I think it's worth trying.
>
> Since adding to log frequency is the same as multiplying linear
> frequency you can get the same thing with just one interpolator,
> used to resample the scaled spectrum.

oh yeah, that's right, but, if I do that, wouldn't the result be just
like interpolating the signal in the time-domain?

Michel Rouzic skrev:
> Martin Eisenberg wrote:
> > Michel Rouzic wrote:
> >
> > > I didn't wanna talk about this too much, because I rather
> > > realize by myself if it's a dumb idea than be told, but my plan
> > > is to *try* using that to perform pitch shift/time stretch.
> > >
> > > my basic idea is, get the FFT of the signal you want to shift,
> > > interpolate the FFT logarithmically, shift the contents towards
> > > the left or the right depending on what you want to obtain,
> > > interpolate back to linear form, IFFT. of course, i'm definitly
> > > not sure and quite sceptical about the odds of obtaining the
> > > wanted result, but I think it's worth trying.
> >
> > Since adding to log frequency is the same as multiplying linear
> > frequency you can get the same thing with just one interpolator,
> > used to resample the scaled spectrum.
>
> oh yeah, that's right, but, if I do that, wouldn't the result be just
> like interpolating the signal in the time-domain?

Nope. Interpolation (i.e. sampling the spectrum on a denser grid)
corresponds to elongating the duration in time domain.

You indicate above that this is an academic exercise, and as such
it makes perfect sense. However, I think you are doing things
a bit too complicated. Why not check the properties of spectrum
interpolation etc in linear scale first, and switch to logarithmic
after you've got some more experience?

Somehow, I think there is a bit confusion about what effects are
caused interpolating the spectrum, and what effects are caused
by working in logarithmic scale. 

Divide and conquer.
 
Rune

Rune Allnor wrote:
> Michel Rouzic skrev:
> > Martin Eisenberg wrote:
> > > Michel Rouzic wrote:
> > >
> > > > I didn't wanna talk about this too much, because I rather
> > > > realize by myself if it's a dumb idea than be told, but my plan
> > > > is to *try* using that to perform pitch shift/time stretch.
> > > >
> > > > my basic idea is, get the FFT of the signal you want to shift,
> > > > interpolate the FFT logarithmically, shift the contents towards
> > > > the left or the right depending on what you want to obtain,
> > > > interpolate back to linear form, IFFT. of course, i'm definitly
> > > > not sure and quite sceptical about the odds of obtaining the
> > > > wanted result, but I think it's worth trying.
> > >
> > > Since adding to log frequency is the same as multiplying linear
> > > frequency you can get the same thing with just one interpolator,
> > > used to resample the scaled spectrum.
> >
> > oh yeah, that's right, but, if I do that, wouldn't the result be just
> > like interpolating the signal in the time-domain?
>
> Nope. Interpolation (i.e. sampling the spectrum on a denser grid)
> corresponds to elongating the duration in time domain.

what do you mean by elongating the duration? you mean making it longer
while keeping it at the same frequencies or not?

> You indicate above that this is an academic exercise, and as such
> it makes perfect sense. However, I think you are doing things
> a bit too complicated. Why not check the properties of spectrum
> interpolation etc in linear scale first, and switch to logarithmic
> after you've got some more experience?

sure, but in the first place I had some trouble seeing how it could be
performed in the linear scale, and actually, I have quite some trouble
successfully implementing it.

the problem is, no matter how i try to put it, i end up with a
resampled version of my original signal plus zero-padding. let's see,
if i want to move everything up by one octave, it must i must multiply
every frequency by two, frequency 0.01 becomes 0.02, frequency 0.1
becomes 0.2 etc... so basically, it's all about interpolating the
signal in the frequency domain by a factor of 2, which is zero-padding
in the time domain, and then get rid of the upper half of the spectrum
so that I get my frequency multiplication right.

if i got it right, it means that all my original idea would do is
zeropad and decimate all in the time domain, right?

> Somehow, I think there is a bit confusion about what effects are
> caused interpolating the spectrum, and what effects are caused
> by working in logarithmic scale.

yeah, i'm definitly confused, and right now I have no idea on how to
obtain something different than zeropading and decimation in the time
domain out of frequency-domain interpolation.

Michel Rouzic skrev:
> Rune Allnor wrote:
> > Michel Rouzic skrev:
> > > Martin Eisenberg wrote:
> > > > Michel Rouzic wrote:
> > > >
> > > > > I didn't wanna talk about this too much, because I rather
> > > > > realize by myself if it's a dumb idea than be told, but my plan
> > > > > is to *try* using that to perform pitch shift/time stretch.
> > > > >
> > > > > my basic idea is, get the FFT of the signal you want to shift,
> > > > > interpolate the FFT logarithmically, shift the contents towards
> > > > > the left or the right depending on what you want to obtain,
> > > > > interpolate back to linear form, IFFT. of course, i'm definitly
> > > > > not sure and quite sceptical about the odds of obtaining the
> > > > > wanted result, but I think it's worth trying.
> > > >
> > > > Since adding to log frequency is the same as multiplying linear
> > > > frequency you can get the same thing with just one interpolator,
> > > > used to resample the scaled spectrum.
> > >
> > > oh yeah, that's right, but, if I do that, wouldn't the result be just
> > > like interpolating the signal in the time-domain?
> >
> > Nope. Interpolation (i.e. sampling the spectrum on a denser grid)
> > corresponds to elongating the duration in time domain.
>
> what do you mean by elongating the duration? you mean making it longer
> while keeping it at the same frequencies or not?

If you (in linear scale) interpolate to find new spectrum coefficients
at half the bin widths, you ought to get the your original signal
sampled at the original frequency, but zero-padded to twice the
length/number of samples.

> > You indicate above that this is an academic exercise, and as such
> > it makes perfect sense. However, I think you are doing things
> > a bit too complicated. Why not check the properties of spectrum
> > interpolation etc in linear scale first, and switch to logarithmic
> > after you've got some more experience?
>
> sure, but in the first place I had some trouble seeing how it could be
> performed in the linear scale, and actually, I have quite some trouble
> successfully implementing it.

Sure. But doing these things in logarithmic scale don't make
it easier. When something doesn't quite work, is it because the
general idea is wrong, or because something went wrong with
the linear-to-logarithmic conversion? It can be very hard to tell.

> the problem is, no matter how i try to put it, i end up with a
> resampled version of my original signal plus zero-padding.

Seems reasonable, see above.

> let's see,
> if i want to move everything up by one octave, it must i must multiply
> every frequency by two, frequency 0.01 becomes 0.02, frequency 0.1
> becomes 0.2 etc... so basically, it's all about interpolating the
> signal in the frequency domain by a factor of 2, which is zero-padding
> in the time domain, and then get rid of the upper half of the spectrum
> so that I get my frequency multiplication right.

Aha... you want to do a frequency shift? It is not obvious how to do
that. In radio, this is usally done as Amplitude Modulation, AM,
where you multiply (mix) with a sinusoidal at the carrier frequency.
Now, in AM the carrier is usually a lot figher than the bandwidth
of the baseband signal. In your case, you get some sort of aliasing
that ought to make lots of problems.

If you haven't done so already, have a look at a text on
AM modulation.

> if i got it right, it means that all my original idea would do is
> zeropad and decimate all in the time domain, right?

I don't know. I didn't notice that frequency shift thing until
right now.

> > Somehow, I think there is a bit confusion about what effects are
> > caused interpolating the spectrum, and what effects are caused
> > by working in logarithmic scale.
>
> yeah, i'm definitly confused, and right now I have no idea on how to
> obtain something different than zeropading and decimation in the time
> domain out of frequency-domain interpolation.

The zero padding is as expected, the resampling... well, I don't know.

Rune

"Michel Rouzic" <Michel0528@yahoo.fr> wrote in message 
news:1145210628.255691.248350@z34g2000cwc.googlegroups.com...

................

...
> the problem is, no matter how i try to put it, i end up with a
> resampled version of my original signal plus zero-padding. let's see,
> if i want to move everything up by one octave, it must i must multiply
> every frequency by two, frequency 0.01 becomes 0.02, frequency 0.1
> becomes 0.2 etc... so basically, it's all about interpolating the
> signal in the frequency domain by a factor of 2, which is zero-padding
> in the time domain, and then get rid of the upper half of the spectrum
> so that I get my frequency multiplication right.
>

If you want to move everything "up one octave" then you have a fundamental 
decision to make:
Do you want to multiply each frequency (as you describe) or shift each 
frequency the same amount and by "one octave" relative to some reference 
frequency?

If you shift then there's no need to interpolate unless that's what you want 
to do as another step and another objective.

If you multiply the frequencies, that is, shift each component differently, 
then I'm not at all sure how that would be handled over all.  It's a 
nonlinear stretch.

Now, if you express the spectral content on a log scale by doing judicious 
summation of a finely-scaled linearly scaled FT into logarithmic bins then a 
shift will accomplish the multiply you refer to I think.  But, I don't know 
what one would call it and this is a mechanical description of how to do it 
but not what it means, etc.  Again, there's no need to interpolate unless 
that's another step and objective.

Getting back to the original linear frequency scale I suppose would be the 
reverse of the process that got the data into a log scale to begin with.

I can imagine a process like this:

Start with x(kT), a temporal sequence
Compute the DFT{x(kT)} X(k/T), a complex frequency sequence
 .. at this stage you need to decide if you're working only with magnitudes 
or what ... I will assume magnitudes because I don't know what else you 
might do.

Compute the magnitudes of X(k/T).
Combine bins of X(k/T) resulting in Y(log(k/T)) on a log frequency scale 
with "equal" spacing.
Note that the spacing is now consistent with the log frequency scale.

{Now, forget all about what the sequence Y represents to maintain our 
sanity}.

The objective is to do a shift of Y by some number of sample points.... and 
we need to worry about positive and negative frequencies.

So we will use the frequency shifting theorem of the FT and do this:
1) inverse FT Y to get y(msT) where m is the index and s is a scaling factor 
on T so there's an all new effective value for T here.  This is just a 
sequence that's been mapped.
2) multiply y(msT) by e^-jRmsT where R is the desired upward frequency shift 
relative to the scale of linear "logfreq" samples.
3) FT the product to get the logfreq shifted version.  This gets us back out 
of the mapping to the original sequence space - and with the desired 
modification.
Now get back to the original linear frequency scale by using like the 
reverse of the process you used to get log scale values of Y.  This might be 
tricky.

I don't know if this works for you (or anyone) but it might at least suggest 
something useful.
Phase information is lost in the magnitude calculation.
There could be distortions in going from linear to log and log to linear 
scale in frequency.

Fred

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message 
news:fLmdnZEJBLanPN_ZRVn-tQ@centurytel.net...

...and since the shifted logfreq sequence will be complex, you'll need to 
take the magnitude again IF you intend to move it all back to a linear 
frequency scale.  ... unless there's a trick that I don't know about.

Fred 

Fred Marshall wrote:

   ...

> I don't know if this works for you (or anyone) but it might at least suggest 
> something useful.
> Phase information is lost in the magnitude calculation.
> There could be distortions in going from linear to log and log to linear 
> scale in frequency.

Why reinvent? http://www.dspdimension.com/ lays it all out, including 
source code.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������