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
realtime convolution with time-varying filter
Started by ●December 18, 2004
Reply by ●December 20, 20042004-12-20
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 ●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 >> > > >
Reply by ●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 ●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 ●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. > > Fredim sorry but i cant find usefull info about REVGEN or REVSIM, i dont know what u mean by these terms
Reply by ●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 ●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 ●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 ●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
