Digital Convolution -- E186 Handout

The convolution of two continuous signals and is defined as

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

Typically, is the output of a system characterized by its impulse response function with input .

Convolution in discrete form is

If is finite, e.g.,

the convolution becomes

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

the above would become

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

If is symmetric (almost always true in image processing), then replacing by we get

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

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

its index in the convolution has to satisfy the following for to be in the valid non-zero range:

or correspondingly, the index of the output has to satisfy:

When the variable index in the convolution is equal to , the index of output reaches its lower bound ; when , the index of reaches its upper bound . In other words, there are valid (non-zero) elements in the output:

Digital convolution can be best understood graphically (where the index of is rearranged) as shown below:

Assume the size of the input signal is ( ) and the size of is (usually an odd number), then the size of the resulting convolution is . However, as it is usually desirable for the output to have the same size as the input , we can drop components at each end of . When the size of is even, we can drop components at one end and from the other of .

The code segment for this 1D convolution is given below.

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 is called a convolution kernel, or mask.