| Author |
Message |
Emile
Guest
|
 Posted:
Sun Dec 19, 2004 1:47 am Post subject:
realtime convolution with time-varying filter |
|
|
Hi,
i am new to this newsgroup and relatively new to dsp programming (i have
basic theoretical background). For my application im trying to implement
i need to realtime convolute an audiostream with a time-varying filter.
Is there some opensource or at least free C/C++ library that i can
easyly use for that?
(im alreay checking http://www.fftw.org/ for my fft needs, but would
like a lib that can do it all)
I find lots of info on overlap-add/overlap-save, but dont seam to find
good info for when the filter changes over time, can someone direct me
to a good book or website concerning this topic?
grtz
Emile |
|
| Back to top |
|
 |
Jon Harris
Guest
|
| Posted:
Mon Dec 20, 2004 7:58 am Post subject:
Re: realtime convolution with time-varying filter |
|
|
How often does the filter change? If it changes more often that one "block
size" of your FFT, then it could be a problem to use frequency domain
convolution. But good old-fashioned time domain convolution should work just
fine. If your filter is time-varying, you just use the current coefficients
each sample period.
You state that you are using an FFT for the convolution without giving a reason
for that. Usually that is only done if the filter is fairly long and you need
to save processing power. Is that the case or do you have some other compelling
reason to use the frequency domain approach.?
"Emile" <bla.abla@telenet.be> wrote in message
news:vH0xd.3929$Oe4.107626@phobos.telenet-ops.be...
| Quote: | Hi,
i am new to this newsgroup and relatively new to dsp programming (i have
basic theoretical background). For my application im trying to implement
i need to realtime convolute an audiostream with a time-varying filter.
Is there some opensource or at least free C/C++ library that i can
easyly use for that?
(im alreay checking http://www.fftw.org/ for my fft needs, but would like a
lib that can do it all)
I find lots of info on overlap-add/overlap-save, but dont seam to find
good info for when the filter changes over time, can someone direct me
to a good book or website concerning this topic?
grtz
Emile
|
|
|
| Back to top |
|
|
Emile
Guest
|
| Posted:
Mon Dec 20, 2004 2:56 pm Post subject:
Re: realtime convolution with time-varying filter |
|
|
Im making a thesis about realtime acoustical modelling of a virtual
environment. I calculate an impulse response for a givin sound source
location, reciever location and virtual environment using a beamtracing
approach (something like [1]). That is verry cpu intensive so i need all
free cpu time i can get. Also i can imagine my filter is gonna be
several seconds for some roomtypes, and for a constantly moving source
and/or reciever i have to have an update rate of about 20Hz to make it
believable (i read in some paper).
[1]www.cs.princeton.edu/~funk/acoustics.html
Jon Harris wrote:
| Quote: | How often does the filter change? If it changes more often that one "block
size" of your FFT, then it could be a problem to use frequency domain
convolution. But good old-fashioned time domain convolution should work just
fine. If your filter is time-varying, you just use the current coefficients
each sample period.
You state that you are using an FFT for the convolution without giving a reason
for that. Usually that is only done if the filter is fairly long and you need
to save processing power. Is that the case or do you have some other compelling
reason to use the frequency domain approach.?
"Emile" <bla.abla@telenet.be> wrote in message
news:vH0xd.3929$Oe4.107626@phobos.telenet-ops.be...
Hi,
i am new to this newsgroup and relatively new to dsp programming (i have
basic theoretical background). For my application im trying to implement
i need to realtime convolute an audiostream with a time-varying filter.
Is there some opensource or at least free C/C++ library that i can
easyly use for that?
(im alreay checking http://www.fftw.org/ for my fft needs, but would like a
lib that can do it all)
I find lots of info on overlap-add/overlap-save, but dont seam to find
good info for when the filter changes over time, can someone direct me
to a good book or website concerning this topic?
grtz
Emile
|
|
|
| Back to top |
|
|
Fred Marshall
Guest
|
| Posted:
Tue Dec 21, 2004 7:12 am Post subject:
Re: realtime convolution with time-varying filter |
|
|
"Emile" <bla.abla@telenet.be> wrote in message
news:Skxxd.5141$TV.170053@phobos.telenet-ops.be...
| Quote: | Im making a thesis about realtime acoustical modelling of a virtual
environment. I calculate an impulse response for a givin sound source
location, reciever location and virtual environment using a beamtracing
approach (something like [1]). That is verry cpu intensive so i need all
free cpu time i can get. Also i can imagine my filter is gonna be several
seconds for some roomtypes, and for a constantly moving source and/or
reciever i have to have an update rate of about 20Hz to make it believable
(i read in some paper).
|
I can't see how this can work.
Instead of looking at this in the time domain and doing filtering in the
frequency domain, back up and think of it in a spatial / sound speed
domain.
The sound source is moving in the environment.
If the sound source moves appreciably with respect to the boundaries and the
receiver while an impulse of sound moves from the source via all the
reflections to the receiver then thinking of the environment as a "filter"
is likely not a good model.
Consider that there is different Doppler potentially associated with each
path. Surely modeling the Doppler shifts or time scale
compression/expansion is as important as modeling the multiple paths isn't
it?
Perhaps what you have isn't so much a time-varying environment as a
time-varying source. Maybe that's a better way to think about it. That
would certainly account for Doppler.
In the limit, you would model the environment for each sample coming from
the source and treat it as a single weighted sample. Obviously that gets
complicated when there's relative motion. Treatments like REVGEN and REVSIM
come to mind.
Fred |
|
| Back to top |
|
|
Jon Harris
Guest
|
| Posted:
Tue Dec 21, 2004 8:03 am Post subject:
Re: realtime convolution with time-varying filter |
|
|
Thanks for clearing up your application. If you filters are several seconds
long, then undoubtedly the FFT-based convolution is the way to go. Sorry I
don't have any other advice for you on the time-varying aspects other than try
changing on FFT block boundaries and see how that works. Using a smaller FFT
would allow for faster changes.
"Emile" <bla.abla@telenet.be> wrote in message
news:Skxxd.5141$TV.170053@phobos.telenet-ops.be...
| Quote: | Im making a thesis about realtime acoustical modelling of a virtual
environment. I calculate an impulse response for a givin sound source
location, reciever location and virtual environment using a beamtracing
approach (something like [1]). That is verry cpu intensive so i need all free
cpu time i can get. Also i can imagine my filter is gonna be several seconds
for some roomtypes, and for a constantly moving source and/or reciever i have
to have an update rate of about 20Hz to make it believable (i read in some
paper).
[1]www.cs.princeton.edu/~funk/acoustics.html
Jon Harris wrote:
How often does the filter change? If it changes more often that one "block
size" of your FFT, then it could be a problem to use frequency domain
convolution. But good old-fashioned time domain convolution should work just
fine. If your filter is time-varying, you just use the current coefficients
each sample period.
You state that you are using an FFT for the convolution without giving a
reason for that. Usually that is only done if the filter is fairly long and
you need to save processing power. Is that the case or do you have some
other compelling reason to use the frequency domain approach.?
"Emile" <bla.abla@telenet.be> wrote in message
news:vH0xd.3929$Oe4.107626@phobos.telenet-ops.be...
Hi,
i am new to this newsgroup and relatively new to dsp programming (i have
basic theoretical background). For my application im trying to implement
i need to realtime convolute an audiostream with a time-varying filter.
Is there some opensource or at least free C/C++ library that i can
easyly use for that?
(im alreay checking http://www.fftw.org/ for my fft needs, but would like a
lib that can do it all)
I find lots of info on overlap-add/overlap-save, but dont seam to find
good info for when the filter changes over time, can someone direct me
to a good book or website concerning this topic?
grtz
Emile
|
|
|
| Back to top |
|
|
Emile
Guest
|
| Posted:
Tue Dec 21, 2004 7:23 pm Post subject:
Re: realtime convolution with time-varying filter |
|
|
Fred Marshall wrote:
| Quote: | "Emile" <bla.abla@telenet.be> wrote in message
news:Skxxd.5141$TV.170053@phobos.telenet-ops.be...
Im making a thesis about realtime acoustical modelling of a virtual
environment. I calculate an impulse response for a givin sound source
location, reciever location and virtual environment using a beamtracing
approach (something like [1]). That is verry cpu intensive so i need all
free cpu time i can get. Also i can imagine my filter is gonna be several
seconds for some roomtypes, and for a constantly moving source and/or
reciever i have to have an update rate of about 20Hz to make it believable
(i read in some paper).
I can't see how this can work.
|
i still have some problems understanding parts of it myself :)
| Quote: | Instead of looking at this in the time domain and doing filtering in the
frequency domain, back up and think of it in a spatial / sound speed
domain.
The sound source is moving in the environment.
If the sound source moves appreciably with respect to the boundaries and the
receiver while an impulse of sound moves from the source via all the
reflections to the receiver then thinking of the environment as a "filter"
is likely not a good model.
Consider that there is different Doppler potentially associated with each
path. Surely modeling the Doppler shifts or time scale
compression/expansion is as important as modeling the multiple paths isn't
it?
Perhaps what you have isn't so much a time-varying environment as a
time-varying source. Maybe that's a better way to think about it. That
would certainly account for Doppler.
|
every path is used for a delay in the time-domain and is put into an
impulse response, but how exactly a path turnes into an impulse response
is still somewhat of a mistery to me (i still havent got my hands on a
paper that fully explaines it). In a siggraph course note i read the
following, this probably explaines it better than i can:
| Quote: |
The signal processing for each geometric path generally consists of 3
phases: 1) a resampling phase, 2)a “filtering” phase, and 3) a spatial
output phase.
....
Each sound path is processed independently as follows. The input signal
is first resampled according to the length of the path (and thus the
propagation delay). This stage is usually implemented in time domain
using a variable delay line (note that variable delay lines account for
the proper Doppler shift).
....
|
spatial output phase is where a head related transfer function is used
to model interaural time delay and interaural amplitude diffrence, so
the user should be able to locate the sound source in 3D.
| Quote: |
In the limit, you would model the environment for each sample coming from
the source and treat it as a single weighted sample. Obviously that gets
complicated when there's relative motion. Treatments like REVGEN and REVSIM
come to mind.
Fred
|
im sorry but i cant find usefull info about REVGEN or REVSIM, i dont
know what u mean by these terms |
|
| Back to top |
|
|
Fred Marshall
Guest
|
| Posted:
Tue Dec 21, 2004 10:19 pm Post subject:
Re: realtime convolution with time-varying filter |
|
|
"Emile" <bla.abla@telenet.be> wrote in message
news:clWxd.6234$ca6.328817@phobos.telenet-ops.be...
| Quote: | Fred Marshall wrote:
"Emile" <bla.abla@telenet.be> wrote in message
news:Skxxd.5141$TV.170053@phobos.telenet-ops.be...
......................................... |
| Quote: | every path is used for a delay in the time-domain and is put into an
impulse response,
|
Well, if the situation were static, and if the signal were continuous rather
than sampled, then it would look something like a FIR filter or transversal
filter with each tap representing a path.
- the direct path would have the least delay
- the shortest bounce path would have the next smallest delay and would have
amplitude and phase that would depend on the bounce mechanism as well as
path distance.
and so forth.
However, if the situation is not static - as when the source is moving -
then the delay positions in the "filter" above change. If one is doing
temporal convolution at very high sample rates then it's pretty easy to move
the temporal location of the taps in real time.
I see no way to accomodate this into a method that uses spectral
multiplication because the temporal arrays are probably quite long as you've
mentioned - and the "filter" changes within the temporal epoch that would be
handled as if it were static for the FFT.
************************
REVGEN - REVerberation GENeration - is a method for generating reverberation
for active sonar that includes a moving source. It uses a cascade of two
FFTs to do it efficiently:
- space is divided into cells
- each cell has a reverberation magnitude and frequency that results from
transmitter motion at the time of transmit and receiver motion at the time
of receiving reverberation from that cell. So, frequency can change over
short time intervals.
- at any instant of time a "sphere" of cell reverberations are being
received. The task is to add them all up at the appropriate frequencies.
- the cells fill what's referred to as a range-doppler map. So, each sphere
is at one range.
- Thus at any instant of time, there is a "spectrum" of reverberation cells.
- This spectrum is multiplied by the spectrum of the transmit pulse. This
results in *many* spectra being computed - all appplying to different times.
- ..... and it goes from there
The simplest case works in a very simple environment of course.
The only difference that I see from your application is that there isn't a
reverberating medium (so much) but you still have to add up all the path
contributions, at the right frequencies, at the receiver.
I think it's a simpler problem so it's amenable to adding a more complex
environment.
Fred |
|
| Back to top |
|
|
Emile
Guest
|
| Posted:
Thu Dec 23, 2004 4:42 pm Post subject:
Re: realtime convolution with time-varying filter |
|
|
Fred Marshall wrote:
| Quote: | "Emile" <bla.abla@telenet.be> wrote in message
news:clWxd.6234$ca6.328817@phobos.telenet-ops.be...
Fred Marshall wrote:
"Emile" <bla.abla@telenet.be> wrote in message
news:Skxxd.5141$TV.170053@phobos.telenet-ops.be...
........................................
every path is used for a delay in the time-domain and is put into an
impulse response,
Well, if the situation were static, and if the signal were continuous rather
than sampled, then it would look something like a FIR filter or transversal
filter with each tap representing a path.
- the direct path would have the least delay
- the shortest bounce path would have the next smallest delay and would have
amplitude and phase that would depend on the bounce mechanism as well as
path distance.
and so forth.
However, if the situation is not static - as when the source is moving -
then the delay positions in the "filter" above change. If one is doing
temporal convolution at very high sample rates then it's pretty easy to move
the temporal location of the taps in real time.
I see no way to accomodate this into a method that uses spectral
multiplication because the temporal arrays are probably quite long as you've
mentioned - and the "filter" changes within the temporal epoch that would be
handled as if it were static for the FFT.
|
i think i actually understand what u are saying here, but it would
probably be to compututational expensive (doing the N
multiplications/additions per output sample for time-domain
convolution). Im reading a paper where the author does it by
cross-fading between 2 outputs of filters in the time-domain after
convolution (in frequency domain). But does that without mathimatical
proof or reference to some other paper that this is correct, and i cant
really see how it can be.
Time-Varying Filter In Non-Uniform Block Convolution
http://www.csis.ul.ie/dafx01/proceedings/papers/m%FCller-tomfelde_a.pdf
| Quote: | ************************
REVGEN - REVerberation GENeration - is a method for generating reverberation
for active sonar that includes a moving source. It uses a cascade of two
FFTs to do it efficiently:
- space is divided into cells
- each cell has a reverberation magnitude and frequency that results from
transmitter motion at the time of transmit and receiver motion at the time
of receiving reverberation from that cell. So, frequency can change over
short time intervals.
- at any instant of time a "sphere" of cell reverberations are being
received. The task is to add them all up at the appropriate frequencies.
- the cells fill what's referred to as a range-doppler map. So, each sphere
is at one range.
- Thus at any instant of time, there is a "spectrum" of reverberation cells.
- This spectrum is multiplied by the spectrum of the transmit pulse. This
results in *many* spectra being computed - all appplying to different times.
- ..... and it goes from there
The simplest case works in a very simple environment of course.
The only difference that I see from your application is that there isn't a
reverberating medium (so much) but you still have to add up all the path
contributions, at the right frequencies, at the receiver.
I think it's a simpler problem so it's amenable to adding a more complex
environment.
|
this does seem verry interesting, but i cant find more info about it. |
|
| Back to top |
|
|
Fred Marshall
Guest
|
| Posted:
Fri Dec 24, 2004 5:09 am Post subject:
Re: realtime convolution with time-varying filter |
|
|
"Emile" <bla.abla@telenet.be> wrote in message
news:layyd.8091$JC2.461018@phobos.telenet-ops.be...
| Quote: |
i think i actually understand what u are saying here, but it would
probably be to compututational expensive (doing the N
multiplications/additions per output sample for time-domain
convolution).
|
Well, waitaminnit ..... you need to think about what is "N".
If there are M paths, then you need to do M additions per output point.
I don't know what N is for sure here.....
That is, the "filter" can be very sparse indeed. This is entirely driven by
the number of paths. There are only as many filter coefficients as there
are paths. All of the intervening coefficients are zero. Now, if you FFT
and multiply then you have to transform the model - including all the zeros.
So *that* would be pretty compute intensive in comparison I should think.
If there is one path, then no additions.
If there are two paths then one addition.
If ther are three paths then two additions
...........
Fred |
|
| Back to top |
|
|
Fred Marshall
Guest
|
| Posted:
Fri Dec 24, 2004 5:28 am Post subject:
Re: realtime convolution with time-varying filter |
|
|
| Quote: | If there is one path, then no additions.
If there are two paths then one addition.
If ther are three paths then two additions
..........
|
It gets more complicated when there's motion because you have to generate
relative advance or delay on the coefficients. But, presumably you keep all
the data points that are in the path at the appropriate input/output sample
rate. So advancing or delaying is only a matter of addressing locations in
that large array.
If you want to generate Doppler in this fashion then it's even more
complicated if the samples are temporal rather than spatial. It becomes a
sample rate conversion exercise.
Fred |
|
| Back to top |
|
|
Emile
Guest
|
| Posted:
Fri Dec 24, 2004 7:12 am Post subject:
Re: realtime convolution with time-varying filter |
|
|
Fred Marshall wrote:
| Quote: | "Emile" <bla.abla@telenet.be> wrote in message
news:layyd.8091$JC2.461018@phobos.telenet-ops.be...
i think i actually understand what u are saying here, but it would
probably be to compututational expensive (doing the N
multiplications/additions per output sample for time-domain
convolution).
Well, waitaminnit ..... you need to think about what is "N".
If there are M paths, then you need to do M additions per output point.
I don't know what N is for sure here.....
That is, the "filter" can be very sparse indeed. This is entirely driven by
the number of paths. There are only as many filter coefficients as there
are paths. All of the intervening coefficients are zero. Now, if you FFT
and multiply then you have to transform the model - including all the zeros.
So *that* would be pretty compute intensive in comparison I should think.
|
yes idd, u're right. I forgot to tell u that only the early reflections
(about 20ms after direct sound) are modeled with geometrical paths, the
rest is approximated with an artificial reverberation algorithm. These
first reverberations are most important to be able to locate the
soundsource in space, the rest of the response is to dense.
Also i have to admit i have some troubles understanding how doppler
shift works in this case. Suppose i only take 1 direct path that becomes
shorter, thus the delay gets smaller (and amplitude higher). As an input
signal i take a discrete sine-wave. Ok i think i can see how this can
work when it is done in time-domain when some interpollation is used.
(something like u said in ur next post about the sample rate conversion
exercise)
but what if when using fft, i shift the frequency of the block being
processed based on the speed-vectors of the source/reciever
also should i forget, thank u so far. This discussion really helps me
think about my problem (and understanding the things i've read so far).
I only came into contact with dsp during my digital image processing
class (wich hasnt finished yet), where the discrete function is a
function of color not time.
another question i still cant figure out, i seem to see impulse
responses of 2 types.
Ones with only positive taps, when this is the model i can see how a
path becomes a tap in the response.
But i also see responses with negative taps, more like a sound wave
representation, but then i dont see how i should transform paths to
impulse responses. Also i cant find good reading about this subject
(this is maybe more a question for some acoustics newsgroup).
| Quote: |
If there is one path, then no additions.
If there are two paths then one addition.
If ther are three paths then two additions
..........
Fred
|
|
|
| Back to top |
|
|
Fred Marshall
Guest
|
| Posted:
Sat Dec 25, 2004 7:57 am Post subject:
Re: realtime convolution with time-varying filter |
|
|
"Emile" <bla.abla@telenet.be> wrote in message
news:oWKyd.8781$hC2.432318@phobos.telenet-ops.be...
| Quote: | Fred Marshall wrote:
"Emile" <bla.abla@telenet.be> wrote in message
news:layyd.8091$JC2.461018@phobos.telenet-ops.be...
i think i actually understand what u are saying here, but it would
probably be to compututational expensive (doing the N
multiplications/additions per output sample for time-domain
convolution).
Well, waitaminnit ..... you need to think about what is "N".
If there are M paths, then you need to do M additions per output point.
I don't know what N is for sure here.....
That is, the "filter" can be very sparse indeed. This is entirely driven
by the number of paths. There are only as many filter coefficients as
there are paths. All of the intervening coefficients are zero. Now, if
you FFT and multiply then you have to transform the model - including all
the zeros. So *that* would be pretty compute intensive in comparison I
should think.
yes idd, u're right. I forgot to tell u that only the early reflections
(about 20ms after direct sound) are modeled with geometrical paths, the
rest is approximated with an artificial reverberation algorithm. These
first reverberations are most important to be able to locate the
soundsource in space, the rest of the response is to dense.
Also i have to admit i have some troubles understanding how doppler shift
works in this case. Suppose i only take 1 direct path that becomes
shorter, thus the delay gets smaller (and amplitude higher). As an input
signal i take a discrete sine-wave. Ok i think i can see how this can work
when it is done in time-domain when some interpollation is used.
(something like u said in ur next post about the sample rate conversion
exercise)
but what if when using fft, i shift the frequency of the block being
processed based on the speed-vectors of the source/reciever
also should i forget, thank u so far. This discussion really helps me
think about my problem (and understanding the things i've read so far). I
only came into contact with dsp during my digital image processing class
(wich hasnt finished yet), where the discrete function is a function of
color not time.
another question i still cant figure out, i seem to see impulse responses
of 2 types.
Ones with only positive taps, when this is the model i can see how a path
becomes a tap in the response.
But i also see responses with negative taps, more like a sound wave
representation, but then i dont see how i should transform paths to
impulse responses. Also i cant find good reading about this subject (this
is maybe more a question for some acoustics newsgroup).
|
Well, if it's a simple path, and not the direct path, then at least there's
a reflection. As I recall, some surfaces will reflect with an inversion and
others don't. Thus sign differences.
Let us say there is a direct path at 2500 feet in water - so the temporal
length is of the direct path is around 0.5 seconds or 500msec. This is
represented by a delay of 500msec and a multiplier that is equivalent to the
attenuation loss.
Now let's assume that the transmitter and receiver are at 2500 feet depth
and there is a noticeable surface reflection path. The surface reflection
path has a length sqrt(5)*2500=5590 so a delay of around 5590msec and a
multiplier that is equivalent to the attenuation loss for this path and
maybe the bounce is inverting (I don't remember).
These two paths look like a transversal filter with two taps at delays of
2500 and 5590msec respectively.
The model builds from there. Perhaps including multiple paths across the
transmit beam pattern, etc.....
Fred |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in