Digital Convolution -- E186 Handout

The convolution of two continuous signals $x(t)$ and $h(t)$ is defined as

$$y(t)=h(t)*x(t) \stackrel{\triangle}{=} \int_{-\infty}^{\infty... ... = \int_{-\infty}^{\infty} h(\tau) x(t-\tau) d\tau = x(t)*h(t)$$

i.e., convolution is commutative. Also convolution is associative:

$$h*(g*x)=(h*g)*x$$

Typically, $y(t)$ is the output of a system characterized by its impulse response function $h(t)$ with input $x(t)$.

Convolution in discrete form is

$$y(n)=\sum_{m=-\infty}^{\infty} x(n-m) \; h(m) =\sum_{m=-\infty}^{\infty} h(n-m) \; x(m)$$

If $h(m)$ is finite, e.g.,

$$h(m) = \left\{ \begin{array}{ll} h(m) & \vert m\vert\le k 0 & \vert m\vert>k \end{array} \right.$$

the convolution becomes

$$y(n)=\sum_{m=-k}^{k} x(n-m) \; h(m)$$

If the system in question were a causal system in time domain, i.e.,

$$h(n)=0\;\;\;\;\;\;\mbox{ if $n<0$}$$

the above would become

$$y(n)=\sum_{m=0}^{k} x(n-m) \; h(m)$$

However, in image processing, we often consider convolution in spatial domain where causality does not apply.

If $h(m)$ is symmetric (almost always true in image processing), i.e.,

$$h(-m)=h(m)$$

the convolution becomes the same as the correlation of the two functions:

$$y(n)=\sum_{m=-k}^{k} x(n+m) \; h(m)$$

The correlation can be considered as the computational model for the neural networks in the biological visual system.

If the input $x(m)$ is finite (always true in reality), i.e.,

$$x(m) = \left\{ \begin{array}{ll} x(m) & 0 \le m <N 0 & otherwise \end{array} \right.$$

its index $n+m$ in the convolution has to satisfy the following for $x$ to be in the valid non-zero range:

$$0 \le n+m \le N-1$$

or correspondingly, the index $n$ of the output $y(n)$ has to satisfy:

$$-m \le n \le N-m-1$$

When the variable index $m$ in the convolution is equal to $k$, the index of output $y(n)$ reaches its lower bound $n=-k$; when $m=-k$, the index of $y(n)$ reaches its upper bound $n=N+k-1$. In other words, there are $N+2k$ valid (non-zero) elements in the output:

$$y(n),\;\;\;\;\;\;(-k \le n \le N+k-1)$$

Digital convolution can be best understood graphically (where the index of $y(n)$ is rearranged).

Assume the dimensionality of the input signal $x$ is $N$ and that of the kernel $h$ is $M=2k+1$ (usually an odd number), then the dimensionality of the resulting convolution $y=x*h$ is $N+M-1$. However, as it is usually desirable for the output $y$ to have the same dimensionality as the input $x$, $k$ components at each end of $y$ are dropped. A code segment for this 1D convolution $y=x*h$ is given below.

$$\par k=(M-1)/2; \par \;\;for (n=0;\; n<N; \; n++) \{ \par \;... ...par \;\;\;\;\;\;\;\;\;\;y[n]+=x[n+m]*h[m+k]; \par \;\; \} \par$$

In particular, if the elements of the kernel are all the same (an average or low-pass filter), the we can speed up the convolution process while sliding the kernel over the input signal by taking care of only the two ends of the kernel.

In image processing, all of the discussions above for one-dimensional convolution are generalized into two dimensions, and $h$ is called a convolution kernel, or mask.

$$y(m.n)=\sum_{i=-k}^k \sum_{j=-k}^k x(m+i,n+j) h(i,j)$$