2. ConvolutionOne 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 [1]: , where is the so-called impulse response of the filter, is the input, and is the output of the system. Equation (2.1) is called the convolution sum formulation of an LSI system. 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 has finite length. It is common to define on the interval . In practice, the sequence is also finite in length, so that can be computed in finite time. Consider two sequences and , of lengths and , respectively, and defined for positive values of n only. Equation (2.1) then reduces to the following finite summation:
The output sequence has length . Equation (2.2) is called a linear convolution. It is instructive to evaluate the sums in Equation (2.2) given some input sequence and impulse response sequence . For demonstration purposes, we use two symbolic sequences.
This returns a linear convolution of the two sequences using
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 and . The middle four samples represent a steady state portion of the output sequence (nonzero values of and 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 , where . A result that excludes the transient samples is sometimes sufficient or desirable.
Two additional convolution formulations can be found in the signal processing literature. The first is called periodic convolution and defines a convolution operation for periodic sequences. Assuming two sequences and have periods M and N, respectively (i.e., and ), we define periodic convolution of the two sequences as
where . The output sequence is also periodic with period min(N, M). Equation (2.3) looks very much like linear convolution and involves the summation of the products of one sequence with the time-reversed and shifted copy of the other. However, since the sequences in Equation (2.3) are periodic, shifts of such sequences produce results different from shifts of finite-duration signals (see Figure 2.1).
Figure 2.1. Demonstration of a right shift of an aperiodic (left) and periodic (right) signal. The other convolution formulation is called circular convolution [1]. By analogy with linear convolution, the formulation applies to finite-length signals, but all shifts are "circular" as in periodic convolution (see Figure 2.2). Circular convolution is particularly important, since it arises from a discrete Fourier transform (DFT) implementation of the convolution operation. It is well known that given three sequences of length , , , , and their respective N-point DFTs, , , , and further given that
it can be shown that the following convolution relationship exists between the sequences:
where represents a circular shift of the sequence . A well-known algorithm called the fast Fourier transform (FFT) allows a fast computation of the DFT, and thus a fast implementation of convolution. Circular and linear convolutions yield different transient samples and identical steady-state samples.
Figure 2.2. Example of a circular shift of a sequence of length . Circular convolution is equivalent to periodic convolution if we consider sequences and to correspond to single periods of their respective infinite periodic extensions and , such that
We calculate the circular convolution of the two example sequences and compare with linear convolution.
An examination of the last result confirms that circular and linear convolutions yield the same steady-state samples. Note that the last four output samples are the same as the steady-state outputs resulting from linear convolution of the two sequences. It is frequently desirable to have the steady-state samples appear centered in the output list. This is achieved by setting the klist elements and equal to the index of the center element of
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 , where are the dimensions of , are the dimensions of , and are the dimensions of . The properties of the convolution operator defined in Equation (2.7) are straightforward extensions of the 1D linear convolution operator. In two dimensions, circular convolution is given by
for . Converted by Mathematica |