Tag Info

27

Essentially, OS is slightly more efficient since it does not require the addition of the overlapping transients. However, you may want to use OA if you need to reuse the FFTs with zero-padding rather than repeated samples. Here is a quick overview from an article I wrote a while ago Fast convolution refers to the blockwise use of circular convolution ...

7

Two potential problems with your approach: You are computing the FFT on your whole signal, which will be terribly inefficient if your input data gets too large, and prevents you from using windowing. If you want to do frequency-domain modifications of your signal, consider using a Short-Term Fourier Transform, processing the resulting FFT frames, and ...

6

Linear FIR filters are applied to a signal (like your audio file) using discrete convolution. Convolution can be implemented efficiently using the FFT. Two separate schemes for doing this are called the overlap-save and overlap-add methods. I personally prefer overlap-save, as it's a bit simpler to implement. It's not clear from your question exactly what ...

6

I have had good time implementing what this guy says: http://mpastell.com/2010/01/18/fir-with-scipy/ A typical low pass filter I use, got from the given link, is this: def firfilt(interval, freq, sampling_rate): nfreq = freq/(0.5*sampling_rate) taps = sampling_rate + 1 a = 1 b = scipy.signal.firwin(taps, cutoff=nfreq) return scipy....

5

Disclaimer: I know this topic is older, but if one is looking for "fast accurate convolution high dynamic range" or similar this is one of the first of only a few decent results. I wanna share my insights I got on this topic so it might help somebody in the future. I apologize if I might use the wrong terms in my answer, but everything I found on this topic ...

3

Lets put forward the intuition behind the concept of the group delay before further discussing how to find the delay of FIR filters. Consider an input signal $x[n]$ of length $L_x$ which is nonzero between $n=0$ and $n=L_x-1$. And let a simplistic filter impulse response to be $h[n] = \delta[n-d]$. The output is immediately shown to be $y[n] = x[n-d]$ which ...

3

Using the matched filter is right approach and typically a full length filter should be used. One of the advantages is that filter gain is approximately proportional to $10\log(T)$. If you don’t need full gain you can use a chunk of your matched filter and still have acceptable detection performance. One technique in active sonar is to use a broken up ...

3

you can split up your long impulse response into smaller segments and use multiple concurrent fast-convolutions that convolve each segment against your audio, align the delays correctly, and add up the result. what must be the case for each segment (or one big segment if you don't split it up) is that if the FFT length is $N$ and the impulse response (or ...

3

Rather than scrapping the fast convolution algorithm, why not use an FFT with a higher dynamic range? An answer to this question shows how to use the Eigen FFT library with boost multiprecision.

3

One candidate is the Karatsuba algorithm, which runs in $O\big(N^{\log_23}\big) \approx O\big(N^{1.5849625}\big)$ time. It's not transform-based. There's also some code with an explanation in the Music-DSP Source Code Archive, which looks like an independent discovery of a similar algorithm. Testing a Python implementation of the Karatsuba algorithm (...

3

Google "overlap add". Quick outline zero pad filter to 256 taps, do an FFT Initialize and "overlap" buffer of length 128 taps to all zeros Initialize an input pointer to 0 Loop starts here Take 128 samples from your input starting at input pointer. Zero pad to 256, FFT Multiply the FFTs Inverse FFT, add overlap buffer to the first 128 samples, output these ...

3

The traditional overlap-add technique cannot be used as is in musical applications (reverberation) where latency is critical. It is a common practice to break down the impulse response into non-uniform chunks, and to run in parallel different convolvers for each segment of the impulse response - some of them being naive FIR implementations (for the short ...

3

You need to know the length of the impulse response of your bandpass filter, and use an FFT longer than 256 by that length (to prevent circular convolution boundary artifacts). Combine the longer FFT results back into a sequence of length 256 windows by overlap-add or overlap-save.

2

Zero-padding is one domain is equivalent to Sinc (or Dirichlet) convolution in the other, which is O(n^2), so that won't save you. For less computation, you might want to try different filter design methods (compositing existing FIR filters, IIRs, etc.) or finding a way to recompute your filter less often.

2

The main alternative that I can think of is the hybrid method proposed by Bill Gardner and patented by Lake DSP (now part of Dolby). There appears to be a copy of Gardner's paper here.

2

And as it is well known, the computational complexity is $\mathcal{O}(N^2)$ and $\mathcal{O}(N \log N)$ for them respectively. $\mathcal{O}$ notation ignores any constants that determine exactly how fast those functions run. Depending on the constants out front, it may be faster to compute the convolution (or correlation) directly. For example, the ...

2

IDFT the smaller or both of the DFTs if needed. Zero pad one or both of the kernel and image to make them the same dimension and size. Re-DFT as needed, and now you can complex multiply the 2 DFT arrays element-by-element because they will now be the same size.

2

This (kind of) question has been possibly asked and answered a few times, but for your convenience let me put another. Given a 2D discrete-space sequence (representing a sampled image) of $x[n_1,n_2]$ of length $N_1$ along $n_1$-axis from $n_1=0$ to $n_1=N_1-1$ and length $N_2$ along $n_2$-axis from $n_2=0$ to $n_2=N_2-1$, and a 2D discrete-space filter's ...

2

I believe that the Cordic algorithm's precision can be extended as far as you want, if so use an integer DFT and a word length appropriate to your problem. The same would be true with direct convolution, use very long integers.

2

This is an insightful question, one that I remember pondering in the 1980s when I first learned of the Overlap-Add (OLA) and Overlap-Save (OLS, sometimes called Overlap-Scrap) methods of "fast convolution". It turns out that for strict LTI filtering, that you need not window with a Hann, but you could if you wanted to, and for a general frequency-domain ...

2

You can make a big FFT out of smaller FFTs This code implements a 16384 point FFT with a 16 point FFT and 1024 point FFT. You need only calculate the Twiddle matrix once. clear all M=16; N=1024; x=sin(linspace(1,M*N,M*N)*2*pi*60/(M*N)); % test signal X=reshape(x,N,M).'; % form 2D matrix read data in as rows Twiddle=zeros(size(X)); % make Twiddle ...

2

In your case, since you have multiple images while you have a given set of kernels the DFT based Correlation would be the best fit. Pay attention that the DFT Based Convolution / Correlation is equivalent to Convolution / Correlation with Periodic / Circular boundary conditions. It means that if you need different boundary conditions (Like padding with ...

1

Knowing the order of magnitude of the data you are dealing with is a good start to troubleshooting your problem because it might be something to do with other things around your implementation of overlap add or save (OA,OS). OA, OS will work for even the weakest of CPUs. It might appear to take ages but it will not fail in a "hard way". By "hard way" here, ...

1

I do a lot of decimation in the frequency domain. Little details are important. I assume you already know the basic rules for fast convolution: the FFT length N is equal to the data blocksize L plus the length of the filter impulse response M minus 1. Each operation uses L samples of new data plus M-1 samples of data from the old block. Ensure that the ...

1

You dont have sigma specified for the gaussian filter. I typically use something like fspecial('gaussian',6*sigma,sigma); as the gaussian kernel is roughly 6 x sigma wide. (see graph here but note they plot against variance https://en.wikipedia.org/wiki/Gaussian_function) Because of that, your padding should be 3 x sigma. But padding with zeros creates an ...

1

I am not sure I understand your question, and I am not sure whether you are looking for expert help with a rather esoteric filtering problem, or if you are new to digital filtering. I am guessing you are new to this subject and you don't realize there is a much simpler way to filter data, other than with the FFT approach. If so, take a look at this: http://...

1

Quadratic time convolution to get a DFT result is usually less accurate (can incur more finite quantization numerical noise, due to a deeper layering of arithmetic steps) than the typical FFT algorithm when using the same arithmetic types and operation units. You might want to try higher precision data types (quad precision or bignum arithmetic).

1

You seem to be aware of the Fourier Transform pair that relates a sinc function in the time domain to a rectangle function in the frequency domain, but you don't seem to be able to correctly apply this to your situation. I am going to take one more stab at answering you. Let me know if you have questions. A sinc filter can be designed using the relationship ...

1

1) Can I add the overlapping parts before taking the IFFT of each sequence? Yes, but you will also end up adding the non-overlapped parts as well. Before the IFFT the non-overlapped and overlapped parts are completely mixed together in the intermediate spectral product, and can't be separated (except by an IFFT or equivalent). So you can't add only the ...

1

your FIR, $h[n]$ can be converted, once and for all, into $H[k]$ the spectrum with which you will multiply in the frequency domain. but for every frame of $x[n]$, you must zero pad and FFT that into $X[k]$, multiply that $X[k]$ by $H[k]$ (which now becomes $Y[k]$) and you must iFFT that back into $y[n]$ and overlap add with the previous frame of $y[n]$.

Only top voted, non community-wiki answers of a minimum length are eligible