Motivation
Smoothing, sharpening, edge detection and blur all replace each pixel by a weighted sum of its neighbors, with the same weights everywhere. This unit gives that operation a precise form, proves what it is characterized by, shows how to compute it cheaply, and links it to frequency. It relies on the unit on sampling, aliasing and prefiltering, which introduced the averaging filter, and it provides the language used by the units on blur inversion and gradient imaging.
Definitions
Work first with one-dimensional signals , , that are zero outside a finite range; images are treated later by the same formulas in two indices.
Definition 9.2.1
(Kernel, correlation and convolution)
A kernel is a finitely supported sequence . The correlation and the convolution of with are
Convolution is correlation with the flipped kernel . For a symmetric kernel, , the two coincide. For images, in the same way.
Definition 9.2.2
(Linear shift-invariant operator)
An operator on signals is linear if , and shift-invariant if commutes with the shift .
Definition 9.2.3
(Frequency response)
The frequency response of a kernel is for real .
At the edge of an image the sum would use pixels that do not exist. Common conventions are zero padding (treat missing pixels as ), replication of the edge value, mirror reflection, or valid output only (compute where the whole kernel fits). Every claim below about exact formulas assumes that the convention is stated; results near the border differ between conventions.
Main results
Theorem 9.2.4
(Characterization of linear shift-invariant filters)
Let be linear and shift-invariant on finitely supported signals. Put , where for and otherwise. Then for every such .
Proof
(Decomposing a signal into shifted impulses)
Every finitely supported equals , a finite sum. By linearity and shift-invariance, . The substitution shows .
Proof X-ray
One output determines the whole operator
Each hypothesis is used exactly once. Finite support makes the decomposition into impulses a finite sum, so no continuity of is needed. Linearity lets pass through that sum and the scalars . Shift-invariance converts into , the shifted copy of the single known output .
The non-obvious move is therefore to test the operator on one signal, the impulse, and to rebuild every other output from shifted copies of it. The proof closes with a pure reindexing, which is why convolution has the flipped index : the output at collects the copy of that was placed at each input position . Dropping shift-invariance leaves the first two steps intact but breaks the third, as the next example shows.
The kernel is the impulse response: filtering a single bright pixel produces a copy of the kernel.
Counterexample mode
Linearity alone does not give a convolution
A tempting claim is that every linear operator on signals is convolution with . Take the operator , which keeps every second sample. It is linear, and , so . For we get for every , because has no integer solution, whereas . The operator is not shift-invariant: shifting the input by one sample does not shift the output by one. The repair is to require shift-invariance; downsampling is accordingly analyzed as a convolution followed by sampling.
Proposition 9.2.5
(Convolution is commutative and associative)
Convolution is commutative and associative, and is its identity. Hence successive linear filters can be applied in either order, and .
Proof
(Reindexing the defining sums)
Commutativity is the substitution in the defining sum. Associativity: , and grouping terms by gives ; all sums are finite. That is the identity follows from .
Theorem 9.2.6
(Separable kernels)
If a two-dimensional kernel has the form , then , where filters along the first index and along the second. A kernel on a support is of this form exactly when its matrix has rank at most one.
Proof
(Pulling the first index inside)
, which is the stated composition. A matrix has rank at most one, and every matrix of rank at most one equals some .
A separable kernel therefore needs multiplications per output pixel rather than . A sampled Gaussian is exactly separable. Not every smooth-looking two-dimensional kernel is separable, so the rank of the kernel matrix should be checked.
Theorem 9.2.7
(Convolution theorem, circular case)
For -periodic sequences define the DFT and the circular convolution . Then .
Proof
(Splitting the exponential)
. Write and sum first over with fixed. Because and the exponential are -periodic, permutes the residues, so the inner sum is . What remains is .
Concept lensAnalytic
A filter as a multiplier on each frequency
A complex exponential is an eigenfunction of every convolution: . In this description the same filter is not a sliding weighted sum but a list of numbers telling how much each frequency is scaled. Two filters with responses applied in succession scale a frequency by , so composing filters becomes multiplying their responses.
Worked examples
Worked example 9.2.8
(Smoothing a pulse and composing filters)
Let at positions and (taps at ), with zero padding. At each position , :
For instance and . The total is preserved because the kernel weights sum to . Next, the kernel composed with itself is , since the coefficients at offsets count the pairs of taps with the required sum, namely pairs, each pair carrying weight ; by the associativity result, two passes of the three-tap average equal one pass of the five-tap kernel.
Worked example 9.2.9
(A separable filter on a patch)
Let with , and consider the patch . The center response of the direct computation (the kernel is symmetric) is . Separably: filtering each column of with gives , , for the three columns; filtering that row with gives . Both routes agree, as the separability result asserts. For a kernel the saving is against multiplications per output pixel.
Worked example 9.2.10
(Reading a frequency response)
For , . Thus , , . The sequence is annihilated: . Check at with the period-four signal : and , matching and .
Common mistakes and subtle points
Common mistake
(Confusing correlation with convolution)
Convolution flips the kernel, correlation does not. For an antisymmetric kernel such as the derivative mask , , , the two differ by a sign. With at positions , correlation at gives and convolution gives .
Common mistake
(Forgetting normalization)
A smoothing kernel should sum to to preserve mean brightness; a derivative kernel should sum to so that constants map to . A blur with taps and no division by makes every constant image four times as bright, which looks like a gain error rather than a smoothing.
Common mistake
(Using circular convolution for a linear filter)
The convolution theorem is for circular convolution. Take and . The linear convolution is , which has five entries, but the circular convolution wraps the last entry onto the first and gives . Using the DFT for linear convolution requires padding to length at least five, so that no wrap-around occurs.
Exercises
Exercise 9.2.11
(Compute the full convolution of with , both starting at index .)
Foundation
Solution(2)
- 1
Write the defining sum for this kernel
Since and , , with outside .
- 2
Evaluate every index where the output can be nonzero
; ; ; . So . As a check, the entries add up to , which equals .
Because: The full output has length .
Exercise 9.2.12
(Let for and let the kernel have , , . Compute and .)
Foundation
Solution(3)
- 1
Compute the correlation
.
- 2
Compute the convolution
.
Because: Convolution uses in place of .
- 3
Compare
The signs are opposite, as for any antisymmetric kernel.
Exercise 9.2.13
(Decide whether and are separable; if so, give and .)
Core
Solution(3)
- 1
Test the first matrix for rank one
The second column is twice the first column , so the rank is one.
- 2
Factor it as
so and .
- 3
Test the identity matrix
The identity matrix has determinant , so its rank is two and it is not separable.
Because: Separable means rank at most one.
Exercise 9.2.14
(Find the frequency response of with taps at , and evaluate it at and .)
Core
Solution(3)
- 1
Sum the exponentials
- 2
Evaluate at the two frequencies
and .
- 3
Interpret
A constant signal is mapped to zero and the alternating signal is amplified by : this is a high-pass second-difference filter.