next up previous
Next: About this document ...

Digital Convolution -- E186 Handout

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

\begin{displaymath}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) \end{displaymath}

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

\begin{displaymath}h*(g*x)=(h*g)*x \end{displaymath}

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

ConvolutionEx1.gif

Convolution in discrete form is

\begin{displaymath}
y[n]=\sum_{m=-\infty}^{\infty} x[n-m] \; h[m] =\sum_{m=-\infty}^{\infty} h[n-m]\;x[m]
\end{displaymath}

If $h[m]$ is finite, e.g.,

\begin{displaymath}
h[m] = \left\{ \begin{array}{ll} h[m] & \vert m\vert\le k  0 & \vert m\vert>k \end{array} \right.
\end{displaymath}

the convolution becomes

\begin{displaymath}
y[n]=\sum_{m=-k}^{k} x[n-m] \; h[m]
\end{displaymath}

If the system in question were a causal system in time domain

\begin{displaymath}h[n)=h[n]u[n],\;\;\;\;\mbox{i.e.},\;\;\;\;h[n]=0\;\;\;\mbox{ if $n<0$} \end{displaymath}

the above would become

\begin{displaymath}y[n]=\sum_{m=0}^{k} x[n-m] \; h[m] \end{displaymath}

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

If $h[m]=h[-m]$ is symmetric (almost always true in image processing), then replacing $m$ by $-m$ we get

\begin{displaymath}
y[n]=\sum_{m=-k}^{k} x[n+m]\;h[-m]=\sum_{m=-k}^{k} x[n+m] \; h[m]
\end{displaymath}

We see that now the convolution is the same as the correlation of the two functions.

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

\begin{displaymath}x[m] = \left\{ \begin{array}{ll} x[m] & 0 \le m <N  0 & otherwise \end{array} \right. \end{displaymath}

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

\begin{displaymath}0 \le n+m \le N-1 \end{displaymath}

or correspondingly, the index $n$ of the output $y[n]$ has to satisfy:

\begin{displaymath}-m \le n \le N-m-1 \end{displaymath}

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:

\begin{displaymath}y[n],\;\;\;\;\;\;(-k \le n \le N+k-1) \end{displaymath}

Digital convolution can be best understood graphically (where the index of $y[n]$ is rearranged) as shown below:

digital_convolution.gif

Assume the size of the input signal $x[n]$ is $N$ ( $n=0,\cdots,n=N-1$) and the size of $h$ is $M=2k+1$ (usually an odd number), then the size of the resulting convolution $y=x*h$ is $N+M-1=N+2k$. However, as it is usually desirable for the output $y$ to have the same size as the input $x$, we can drop $k$ components at each end of $y$. When the size of $h$ is even, we can drop $k$ components at one end and $k-1$ from the other of $y$.

The code segment for this 1D convolution $y=x*h$ is given below.

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

In particular, if the elements of the kernel are all the same (an average operator or a 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.


\begin{displaymath}y[m,n]=\sum_{i=-k}^k \sum_{j=-k}^k x[m+i,n+j] h[i,j] \end{displaymath}

digital_convolution_2D.gif




next up previous
Next: About this document ...
Ruye Wang 2013-09-09