4
$\begingroup$

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$?

  • 1
    Lots of questions about two-dimensional convolutions can be found on the sister site dsp.SE2012-12-22
  • 0
    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: http://i.stack.imgur.com/eHpvM.png2012-12-28
  • 0
    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.2012-12-28
  • 0
    @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](http://books.google.nl/books?id=k26pjOi6qLkC&lpg=PP1&dq=box%20splines&pg=PA6#v=snippet&q=%22Starting%20with%20the%20characteristic%20function%22&f=false)2012-12-28
  • 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)$.2012-12-28
  • 0
    @RahulNarain: Ah I see, that clarifies it. Thanks! Would you consider posting this as an answer?2012-12-28

2 Answers 2

1

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:

  • 0
    Thank you very much for taking the effort to post this answer! One more short question, how did you generate these figures?2012-12-28
  • 0
    I used [Mathematica](http://www.wolfram.com/mathematica/). I've heard [Sage](http://www.sagemath.org/) is a good open-source alternative.2012-12-28
  • 0
    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.2012-12-29
  • 0
    If you compute $g(1,1) = \int_0^1 f(1-t,1-t)\,\mathrm dt = \int_0^1 1\,\mathrm dt$ you shouldn't get $\sqrt 2$. You would get $\sqrt 2$ if you were multiplying by the path length $\mathrm d\ell = \lVert\xi\,\mathrm dt\rVert$ inside the integral, but we're not. We're just computing the average value of $f$ over the path between $(x,y)$ and $(x-1,y-1)$. The same logic should help you figure out how to get the closed form for each of the pieces: consider how much of the path is inside $[0,1]^2$.2012-12-29
  • 0
    But if it is not a regular path integral, what kind of integral is it? I just don't see the *averaging* nature of this expression. For instance, how would you calculate $g(.5,.5)$? In the meantime I installed Mathematica, could you perhaps provide the code to obtain the hexagonal function? Thanks!2012-12-29
  • 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.2012-12-29
  • 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]`2012-12-29
  • 0
    One last question — can the six closed-form expressions (as displayed in my figure) be derived *directly* from this integral? I'm used to end up with closed-form expressions when using convolution, but in this case I don't see how. Of course I *can* find the expressions by analyzing (the results from) the integral. Incidentally, I do understand your original integral now!2012-12-30
  • 0
    I'm asking this because I would like to repeat this construction for other directions (e.g. for $\vec{\xi} = (-1,1)$ in order to end up with the Zwart-Powell element — [link](http://books.google.nl/books?id=k26pjOi6qLkC&lpg=PP1&dq=box%20splines&pg=PA6#v=snippet&q=%22Starting%20with%20the%20characteristic%20function%22&f=false)). Figuring out the closed-form expressions with this 'manual' approach might become rather difficult!2012-12-30
  • 0
    Well, you just have to do a bunch of case analysis. The essential problem is to determine, for any $(x,y)$, the range of $t$ such that $(x-t,y-t)$ lies in the region(s) of interest, in this case $[0,1]^2$. You can certainly work this out manually and get the piecewise domains for $g$. But then you'll have to do the same thing over the pieces of $g$ to get the ZP element, and that's much much worse. Best to let a computer algebra system like Mathematica deal with it: `h[x_, y_] = Integrate[g[x + t, y - t], {t, 0, 1}];`2012-12-30
1

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.

  • 0
    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$?2012-12-22
  • 0
    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...)2012-12-23