Legacy Documentation

Digital Image Processing (2000)

This is documentation for an obsolete product.
Current products and services
User's Guide / Area Operations /
Previous section-----Next section

5.2 Basics of LSI Systems: Convolution and Correlation

One of the most widely used signal/image processing operations is filtering. In many practical cases the filtering operation is linear shift-invariant (LSI) and may be described by the following relation
where h[n] is the so-called impulse response, x[n] is the input, and y[n] is the output of the filter. Equation (5.2.1) is called the convolution sum formulation of an LSI system. An LSI system's impulse response is a unique property of the system, one that completely characterizes its dynamic behavior. A single output value is computed by summing over all point-wise products of one sequence with a time-reversed and shifted version of the other.
An important category of discrete-time systems exhibits a finite impulse response (FIR), so h[n] has finite length. It is common to define h[n] on the interval 0≤n≤ N-1. In practice, the sequence x[n] is also finite in length, so that y[n] can be computed in finite time. Consider two sequences x[n] and h[n], of lengths M and N, respectively, and defined for positive values of n only. Equation (5.2.1) then reduces to the following finite summation:
The output sequence y[n] has length L = M+N-1. Equation (5.2.2) is called a linear convolution.�
Here we define two finite length sequences and evaluate (5).
The linear correlation of two finite-length sequences is defined as
Equations (5.2.2) and (5.2.3) have the same form and differ only in the reverse ordering of the samples of one sequence with respect to the other. Equation (5.2.2) calls for the samples of h[n] to be folded or reflected around the origin, while Equation (5.2.3) does not. One of the principle applications of correlation in image processing is in template matching, where a signal is searched for the existence of some pattern. The pattern of interest is defined by the sequence h[n], called the template, which according to Equation (5.2.3) is scanned across the signal x[n]. A match between the pattern and a segment of the signal results in a large response, thus identifying the existence and location of the pattern within the given signal.

DiscreteConvolve and DiscreteCorrelate functions.

DiscreteConvolve and DiscreteCorrelate accept a small number of options that implement the standard convolution forms and some convenient variations. These functions simplify, but also constrain the argument syntax of ListConvolve and ListCorrelate, on which they are based.

Options for DiscreteConvolve and DiscreteCorrelate functions.

This loads the package.
In[1]:=
It is instructive to evaluate the sums in Equation (5.2.2) given some input sequence x[n] and impulse response sequence h[n]. For demonstration purposes, we use two symbolic sequences.
In[2]:=
Here we convolve the two sequences using DiscreteConvolve.
In[3]:=
Out[3]//TableForm=Out[3]//TableForm=
The output sequence may be subdivided into three subranges. The first two output samples represent a transient portion of the output signal due to a partial overlap of nonzero values of the sequences x[n] and h[n]. The middle four samples represent a steady-state portion of the output sequence (nonzero values of x[n] and h[n] are fully overlapped). The last two output samples represent a second transient portion of the output sequence, which again is due to a partial overlap of the two sequences. The lengths of these transients are always given by N-1, where N=Length[h]. A result that excludes the transient samples is sometimes sufficient or desirable.
In[4]:=
Out[4]//TableForm=Out[4]//TableForm=
An important variant of the convolution (correlation) operation described thus far is the so-called circular convolution (correlation). While linear convolution assumes that a finite-length signal is extended by padding with zeros, circular convolution uses padding with periodic extensions. It can be easily verified that circular and linear convolution return the same steady-state values but different transient values. Here is the circular convolution result.
In[5]:=
Out[5]//TableForm=Out[5]//TableForm=
It is frequently desirable to have the steady-state samples appear centered in the output list. This is achieved with the option Centered→True.
In[6]:=
Out[6]//TableForm=Out[6]//TableForm=
FIR systems play an especially important role in 2D systems. In digital image processing, many useful operators (i.e., edge detectors) are linear with finite spatial dimensions. The 2D linear convolution sum takes the following form:
for 0≤n1≤M1-1, 0≤n2≤M2-1, where L1, L2 are the dimensions of x[n1,n2], N1,N2 are the dimensions of h[n1,n2], and M1,M2 are the dimensions of y[n1,n2]. The properties of the convolution operator defined in Equation (5.2.4) are straightforward extensions of the 1D linear convolution operator. Similarly, 2D discrete correlation is defined
for 0≤n1≤M1-1, 0≤n2≤M2-1.