Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm wondering how the concept of convolution can be extended to 2D. As example, let us take a constant function $z=f(x,y)=1$ with support on $[0..1]^2 \in \mathbb{R}^2$ (see Fig. 1).

If we now convolute $f$ with itself (see Fig. 2), in the direction $(1,1)^T$, we should end up with a linear hexagonal hat function (see Fig. 3), which has the value $z=1$ at the center.

enter image description here

There are at least two ways to compute the resulting function/surface, but for both these methods I'm not completely sure how to apply them.

  • Integrating, just like convoluting two univariate functions $f(t)$ and $g(t)$: $$(f * g)(t) = \int_{-\infty}^\infty f(\tau) g(t-\tau) \; d \tau$$ However, in the bivariate case I guess we should use a double integral, since we're convoluting surfaces now, not curves. Moreover, we have to consider the direction in which we convolute, which in this example is $(1,1)^T$.

  • Fourier transformation. Since convolution reduces to multiplication in the frequency domain, this seems a useful method. Suppose that we would know the Fourier transform $\hat{f}$ of $f(x,y)$, how should we then involve the direction?

I hope somebody can demonstrate one or both of these methods, using the example above. References to bivariate convolution, preferably with examples, are of course also welcome!

[Edit]: Ok, using the expression $$(f*g)(x,y) = \int f(x',y')g(x-x',y-y')dx'dy'$$ I end up with different values than expected. For example, at $(.5,.5)$ the computed value is $.25$, instead of the expected $.5$.

Just to be sure, the convolution of the unit square (i.e. a constant value $z=1$ on $[0..1]^2 \in \mathbb{R}^2$) in the direction $(1,1)^T$ should result in the hexagonal hat function, correct?

enter image description here

Additionally, instead of the function $y$, I got the function $xy$ for the highlighted green part of the resulting function. How does one end up with $y$?

share|improve this question
1  
Lots of questions about two-dimensional convolutions can be found on the sister site dsp.SE –  Dilip Sarwate Dec 22 '12 at 23:37
    
What do you mean by convolution in a direction? You convolve two signals, that's it; there is no need to also specify a direction. Anyway, the convolution of a box function with itself is not a hexagonal tent function. It is a bilinear tent supported on $[0,2]^2$ whose value is $xy$ on $[0,1]^2$ and symmetrically extends to the other quadrants. It looks like this: i.stack.imgur.com/eHpvM.png –  Rahul Dec 28 '12 at 11:23
    
After all, $(1,0)$ lies in the support of $f$, so $(2,0)$ should lie in the support of $f*f$. Your calculations seem to be perfectly correct; it's your expectations that are mistaken. –  Rahul Dec 28 '12 at 11:28
    
@RahulNarain: I'm looking at convolution from a geometric perspective. So there is one function that is fixed — e.g. $f(x',y')$ — and another one $g(x-x',y-y')$ that moves in a certain direction $\xi$. I got the definition from this book, Figure 12: link –  Ailurus Dec 28 '12 at 11:42
1  
In that case, it looks like they're not convolving the square with itself but with the line segment between $(0,0)$ and $(1,1)$. Your integral is going to be $\int_0^1 f(\vec x-\vec\xi t)\,\mathrm dt$ where $\vec x = (x,y)$ and $\vec\xi = (1,1)$. –  Rahul Dec 28 '12 at 12:26

2 Answers 2

up vote 1 down vote accepted

It turns out that two different things have been conflated together in your sentence "we now convolute convolve $f$ with itself in the direction $(1,1)^T$".

The convolution of $f$ with itself is $$(f*f)(x,y) = \iint f(x',y') f(x-x',y-y')\,\mathrm dx'\,\mathrm dy',$$ which for your $f$ being the box function looks like this:

The convolution of $f$ in the direction $(1,1)^T$, on the other hand, is apparently $$g(x,y) = \int_0^1 f(x-t,y-t)\,\mathrm dt.$$ I haven't seen this terminology before, but that's what your book seems to imply. And yields the hexagon you desire:

share|improve this answer
    
Thank you very much for taking the effort to post this answer! One more short question, how did you generate these figures? –  Ailurus Dec 28 '12 at 16:07
    
I used Mathematica. I've heard Sage is a good open-source alternative. –  Rahul Dec 28 '12 at 16:18
    
After studying the integral in some more detail, I actually have two more short questions. First, wouldn't the value of $g(1,1)$ be $\sqrt{2}$ instead of $1$? The value $1$ is the expected value and is also the value displayed in your figure, but when I compute it I obtain $\sqrt{2}$. Second, I don't see how to obtain the piecewise closed-form expressions (e.g. $y$ for the triangle where $x \in [0..1]$ and $y \in [0..x]$), see the bottom figure in my question. –  Ailurus Dec 29 '12 at 0:32
1  
Okay, think of it as the path integral divided by the length of the path. You can see that as an average, right? Just like the integral of a function over an interval, divided by the length of the interval, is the average value of the function on that interval. –  Rahul Dec 29 '12 at 14:53
1  
Anyway, the code is straightforward: f[x_, y_] = Piecewise[{{1, 0 <= x <= 1 && 0 <= y <= 1}}]; g[x_, y_] = Integrate[f[x - t, y - t], {t, 0, 1}]; Plot3D[g[x, y], {x, -0.5, 2.5}, {y, -0.5, 2.5}, PlotRange -> Full] –  Rahul Dec 29 '12 at 14:54

2D convolution is common in optical calculations, in which there is a cylindrical geometry. The convolution of 2, 2D functions is analogous to that of 2, 1D functions:

$$(f \star g)(u,v) = \int_{-\infty}^{\infty} du' dv' f(u-u',v-v')g(u',v')$$

Each point $(u,v)$ represents an amount of overlap between the shifted $f$ and $g$ functions. To build the convolution function, you have to find the support in the convolution integral (i.e., where the integral is nonzero), and evaluate the overlap integral for every point in the support.

The Fourier transform stuff is entirely analogous.

share|improve this answer
    
The support in the convolution integral would be the hexagon from Fig. 3, right? Should I just rewrite the integral to a double integral, both with boundaries from $0$ to $2$? –  Ailurus Dec 22 '12 at 23:46
    
If you are convolving 2 regions of finite support, then yes. But it is possible to have a convolution of 2 functions that are not compactly supported (like gaussians, or exponentials, or lorentzians, or...) –  Ron Gordon Dec 23 '12 at 0:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.