Reply by Fred Marshall●December 25, 20042004-12-25
"Emile" <bla.abla@telenet.be> wrote in message
news:oWKyd.8781$hC2.432318@phobos.telenet-ops.be...
> 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
Reply by Emile●December 23, 20042004-12-23
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).
>
> 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
>
>
Reply by Fred Marshall●December 23, 20042004-12-23
> 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
Reply by Fred Marshall●December 23, 20042004-12-23
"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.
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
Reply by Emile●December 23, 20042004-12-23
Fred Marshall wrote:
> "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
> ************************
>
> 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.
Reply by Fred Marshall●December 21, 20042004-12-21
"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.
************************
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
Reply by Emile●December 21, 20042004-12-21
Fred Marshall wrote:
> "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 :)
> 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).
...
[/quote]
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.
>
> 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
Reply by Jon Harris●December 21, 20042004-12-21
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...
> 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
>>>
>>
>>
Reply by Fred Marshall●December 20, 20042004-12-20
"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.
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
Reply by Emile●December 20, 20042004-12-20
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
>>
>
>
>