Questions tagged [convolution]
Convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions.
1,004
questions
64
votes
17
answers
180k
views
What is the physical meaning of the convolution of two signals?
If we convolve 2 signals we get a third signal. What does this third signal represent in relation to the input signals?
- 743
55
votes
5
answers
53k
views
What is the difference between convolution and cross-correlation?
I've found on multiple sites that convolution and cross-correlation are similar (including the tag wiki for convolution), but I didn't find anywhere how they differ.
What is the difference between ...
- 815
36
votes
6
answers
24k
views
Flipping the impulse response in convolution
During convolution on a signal, why do we need to flip the impulse response during the process?
- 463
28
votes
2
answers
20k
views
Overlap-Add versus Overlap-Save
What differences or other criteria can be used to help decide between using overlap-add and overlap-save for filtering? Both overlap-add and overlap-save are described as algorithms for doing FFT ...
- 35.2k
26
votes
1
answer
9k
views
How to circularly shift a signal by a fraction of a sample?
The shift theorem says:
Multiplying $x_n$ by a linear phase $e^{\frac{2\pi i}{N}n m}$ for some integer m corresponds to a circular shift of the output $X_k$: $X_k$ is replaced by $X_{k-m}$, where ...
- 15.7k
23
votes
6
answers
16k
views
What are the problems with designing an FIR filter using FFT?
I'm trying to get an understanding of the relationship between an FIR filter designed from "first principles" using a filter kernel with convolution, and a filter designed in one of two ways using FFT ...
- 1,413
22
votes
1
answer
45k
views
Difference Between Correlation and Convolution in the Context of Image Processing
Could you please clearly explain what is the difference between correlation and convolution that is done by a filter on an image?
I mean in terms of signal processing definition I know that ...
- 363
15
votes
13
answers
37k
views
Deconvolution of 1D Signals Blurred by a Gaussian Kernel
I have convolved a random signal with a a Gaussian and added noise (Poisson noise in this case) to generate a noisy signal. Now I would like to deconvolve this noisy signal to extract the original ...
- 159
15
votes
6
answers
146k
views
What Are Linear and Circular Convolution?
I have some basic understanding of signals and convolution. As far as I know it shows the similarities of two signals. Could I get some explanation in plain English of:
what are the linear and ...
- 336
14
votes
3
answers
8k
views
Why convolution is required, or what is the philosophy behind convolution?
I am working in digital image restoration field. I have read all things about convolution, that, for an LTI system, if we know its impulse response, then we can find its output by just using ...
- 521
14
votes
5
answers
7k
views
Why do linear systems show sinusoidal fidelity?
I am looking for a proof for sinusoidal fidelity. In DSP we study a lot about linear systems. Linear systems are homogenous and additive. One more condition it satisifies is that if a signal is a sine ...
- 141
14
votes
4
answers
29k
views
Why is circular convolution used in DSP? Why not linear convolution?
Why are we using circular convolution in DSP?
What's the main solid reason for the use of it in digital
processing?
Why does the concept of circular convolution come more often than
linear ...
- 141
14
votes
5
answers
26k
views
How Does a Convolution of an Image Can Be Expressed as a Matrix Multiplication (Matrix Form)?
I know this question may not be very relevant to programming, but if I don't understand the theory behind image processing I'll never be able to implement something in practice.
If I got it right ...
- 251
14
votes
1
answer
2k
views
How to find the convolution kernel in frequency domain?
I have a two vectors of spatial data (each about 2000 elements in length). One is a convolved version of the other. I am trying to determine the kernel that would produce such a convolution. I know ...
- 251
14
votes
2
answers
4k
views
How to Deduce a Linear System's Impulse Response from a Set of Input and Output Signals?
I want to know how to solve those types of problems.. is it by inspection ?
Consider the linear system below. When the inputs to the system $x_1[n]$, $x_2[n]$ and $x_3[n]$, the responses of the ...
- 149
12
votes
4
answers
3k
views
DFT - Removing window effect in spectral domain with convolution
I was thinking about the DFT windowing subject and a thought came to my mind. A DFT will yield the spectrum of a signal convoluted with spectrum of the window used, therefore having a main lobes and ...
12
votes
2
answers
5k
views
Generate the Convolution Matrix of 2D Kernel for Convolution Shape of `same`
I want to find a convolution matrix for a certain 2D kernel $ H $.
For example, for image Img of size $ m \times n $ , I want (in MATALB):
...
- 877
11
votes
2
answers
23k
views
Apply a Gabor filter to an input image
I tried to apply a Gabor filter with a specific scale (according to my values of lambda and sigma, so it is (7x7) and for 4 orientations (0, $\frac{\pi}{4}$, $\frac{\pi}{2}$ and $\frac{3\pi}{4}$) to a ...
- 111
10
votes
4
answers
4k
views
Why LTI system cannot generate new frequencies?
Why $Y (\omega) = X(\omega)H(\omega)$ implies that an LTI system cannot
generate any new frequencies?
Why if a system generates new frequencies, then it is not LTI?
- 125
10
votes
5
answers
2k
views
Fast & accurate convolution algorithm (like FFT) for high dynamic range?
It seems that FFT-based convolution suffers from limited floating-point resolution due to evaluating everything around the roots of unity, as you can see in the $10^{14}$-factor error in this Python ...
- 495
10
votes
2
answers
7k
views
Meaning of the Transpose of Convolution
I have an $n \times n$ asymmetric convolution kernel, $k(t_1,t_2)$. $k$ is zero everywhere except for in small regions near the corners.
I also have an $n \times n$ image, $f$.
Let $*$ denote ...
- 295
10
votes
1
answer
1k
views
Solving a Convolution Problem of a 1D Signal
I'm finding in trouble trying to resolve this exercise. I have to calculate the convolution of this signal:
$$y(t)=e^{-kt}u(t)\frac{\sin\left(\dfrac{{\pi}t}{10}\right)}{({\pi}t)} $$
where $u(t)$ is ...
- 545
10
votes
2
answers
421
views
Deconvolution Question on Article "Deriving Intrinsic Images from Image Sequences" by Yair Weiss
there are n derivative filters: $f_i$, and denote $f_i^r$ as $f_i$'s reverse filter such that
$$f_i(x,y)=f_i^r(-x, -y)$$
$r_i, f_i$ given, to find $r$ from the equations:
$$f_i * r = r_i, (1 \leq i \...
- 101
9
votes
2
answers
3k
views
For complex values, why use complex conjugate in convolution?
Taken from Adaptive Filter Theory (2014) written by Haykin page 110 :
$$y(n) = \sum_{k=0}^{\infty} w_k^*u(n-k), \quad n=0,1,2,...$$
where $u$ and $w$ are complex values. My question is why use ...
9
votes
4
answers
4k
views
Deconvolution by Convolution
This is now a second time I am attempting to ask this very important but simple question here. What I want to know is can you do deconvolution by convolving a signal. It is often stated that, for ...
- 121
9
votes
1
answer
5k
views
How do real-time convolution plugins process audio so quickly
Okay, so in Logic Pro I can load up a Space Designer plugin (convolution reverb) with an impulse that's 9.1 seconds long, turn my mic on, and get real-time convolution reverb as the mic records ...
- 93
9
votes
2
answers
4k
views
MOD-N Circular Convolution
How to find MOD-2 Circular convolution for the two sequences $h =[-1,3,-2,1]$ and $x = [1,-1,-2,1,3,2,1,2]$.
I know the answer is $7$ $0$ from matlab but I don't know how to find it graphicly or ...
- 91
9
votes
3
answers
1k
views
Deconvolution of Synthetic 1D Signals - How To?
I convolved a square wave with a Gaussian wave using linear convolution. Can I get the original square wave back by deconvolving my output with the Gaussian function?
I took the FFT of both signals, ...
- 117
9
votes
7
answers
1k
views
Intuition behind commutativity of convolution in LTI systems
Why is convolution commutative, as it seems to treat two signals in a different way in an LTI system?
If you imagine $y[n] = x[n] \star h[n]$ with $x[n]$ being an input signal and $h[n]$ being the ...
- 193
9
votes
3
answers
5k
views
How to Zero Pad in Order to Perform Filtering in the Fourier (Frequency) Domain?
Consider an $M\times N$ image $f$ and an $G \times K$ filter $h$. Given that convolution in the spatial domain corresponds to multiplication in the Fourier domain, then we can perform a convolution of ...
user40095
9
votes
1
answer
7k
views
Auto Correlation vs Cross Correlation vs Convolution and their applications
I know from wikipedia that auto correlation in done on the same signal while cross correlation is done on different signals.But what does this actually imply in terms of application.I can always apply ...
- 93
8
votes
1
answer
169
views
Image / Video Upscaling (Super Resolution) Algorithm Explanation (Image and Video Upscaling from Local Self Examples)
So, I'm trying to implement the classical algorithm described in this paper Image and Video Upscaling from Local Self-Examples and this presentation to serve as a baseline for comparison with AI/NN-...
- 81
7
votes
2
answers
8k
views
Circular and Linear Convolution
What is the difference between circular and linear convolution? When would I choose one over the other? In image processing where a filter is applied to an image with a mask which type of convolution ...
- 173
7
votes
2
answers
8k
views
Sampling Theorem and Dirac Comb
I am reading "The Scientist and Engineer's Guide to Digital Signal Processing" and trying to understand Figure 3.5 below which is about the sampling theorem and aliasing.
I do not understand the ...
- 527
7
votes
1
answer
310
views
Convolution involving turning each pixel value to the most represented pixel value of the neighbourhood
In order to correct gradual changes of intensities in the background of grey-scales images, I have been blurring them and then subtracting the original images from the convolved one.
In some cases, I ...
7
votes
1
answer
365
views
Computing a convolution using FFT and more than minimum number of samples
Assume vector s is a set of time samples of length 1000.
Assume vector h is a set of samples of length 50.
If I want to compute the convolution of those vectors, the result will be 1000+50-1 = 1049 ...
7
votes
1
answer
5k
views
Convolution Kernels for Image Filtering
As I understand it, in image processing, when it is desired to apply a filter of some sort to an 2D image, a kernel is applied to all the pixels of the 2D image in a process called convolution. Median,...
- 185
7
votes
3
answers
2k
views
Convolution of Signal with a Wavelet
I know that the complex wavelet transform is given by
$$\int_{-\infty}^{\infty}f(x)\psi^*_{s,u}(x)\,dx$$
where $f$ is the signal, $\psi_{s,u}(x)=\frac{1}{\sqrt{s}}\psi(\frac{x-u}{s})$ is the wavelet.
...
- 617
7
votes
2
answers
140
views
Do $|s(t)|$ and $|S(f)|$ uniquely determine $s(t)$?
Consider a signal $s(t)$. My question is if you know $|s(t)|$ and $|\mathcal{FT}[s(t)](f)| = |S(f)|$ or equivalently $|s(t)|^2$ and $|S(f)|^2$ is it possible to determine $s(t)$? That is, is $s(t)$ ...
- 312
7
votes
2
answers
7k
views
Gaussian Filter Close to Image Border
When applying Gaussian filters close to the borders of an image, algorithms usually zero-pad or replicate/mirror/wrap the borders. This is not good enough for my case, so I wonder if there is ...
- 73
7
votes
1
answer
326
views
Circular Convolution as Cyclic Shift Operator
Given the following signal vectors:
$$ γ=[ψ_0,0,ψ_1,0,ψ_2,0,…,ψ_{N-1},0]^T\in \mathbb{R}^{2N}, ϕ=[1,\frac{1}{2},0,…,0,\frac{1}{2}]^T \in \mathbb{R}^{2N}$$
I want to show that the convolution of $γ$ ...
- 197
7
votes
1
answer
5k
views
1D Deconvolution with Gaussian Kernel (MATLAB)
Suppose that I know the output and the transfer functions of a system and I would like to calculate the input function using deconvolution.
To get a grasp of the idea I have created a simple ...
- 73
7
votes
2
answers
2k
views
Kernel Convolution in Frequency Domain - Cyclic Padding
I don't know whether this is the right place to post this, but I suppose it is.
I know that frequency multiplication = circular convolution in time space for discrete signals (vectors).
I also know ...
- 223
7
votes
0
answers
321
views
Efficient Convolution Without I/O Delay (Gardner 1995) implementation
I am trying to perform real-time convolution on an audio stream using a fairly large FIR for convolutional reverb.
I found a great paper explaining how to do just that: Gardner, 1995. But, I'm new to ...
- 171
7
votes
1
answer
248
views
Filter design to realize Cauchy product
I come from Computer Science so please pardon for my possibly wrong terminology.
I need to design a filter which has coefficients
$$h_0, h_1, \ldots, h_n, \ldots \quad\text{such that}\quad h_0 > ...
7
votes
1
answer
387
views
Analytical Expression for Convolution of Two 2D DFTs
I am trying to do an image analysis problem on some images, and I want to calculate some things in the frequency domain which are giving me problems. Say I have an (discrete) image $I(x,y)$ of size $...
- 171
6
votes
3
answers
1k
views
Delay a signal in time vs in frequency
I have a signal h that I want to delay for a time t.
I know that I could use two possible approaches:
$h_{\text{delay}}[k] = \...
6
votes
1
answer
11k
views
2D Convolution as a Doubly Block Circulant Matrix Operating on a Vector
I was reading Fundamental Image Processing, Chapter 5 (Image Transforms), I encountered the following problem:
Given the arrays $x_1(m,n)$ and $x_2(m,n)$ as follows:
Write their convolution $x_3(m,n)...
- 369
6
votes
2
answers
13k
views
How to Prove a 2D Filter Is Separable?
I want to prove that 2D Gaussian filter is separable and we can separate it into two dimensions, my problem is about the size of filters. we should prove that $G(x,y)*I$(where $G(x,y)=$$\begin{bmatrix}...
- 163
6
votes
3
answers
8k
views
Conceptually, how does real time convolution reverb work?
I've got an impulse response of a hall, it's 10 seconds long.
Now say I want to apply this reverb to a wav file of some singing. I would perform a convolution of the data in two wav files and that ...
user5695