Filtering: Cross-Correlation, Convolution, and Sharpening¶

Linearity of Operators¶

An operator H is linear if it satisfies:

Additivity: \(H(f_1 + f_2) = H(f_1) + H(f_2)\)
Homogeneity: \(H(a \cdot f) = a \cdot H(f)\)

Because filtering uses multiplication and summation, correlation and convolution are linear operators. Non-linear examples: max, square root.

Impulse Function and Response¶

A discrete impulse is a single pixel with value 1, all others 0. In continuous domain, it has zero width, infinite height, and unit area.

If a system’s impulse response is known, the system’s effect on any input can be determined by decomposing the input into shifted/scaled impulses and summing the individual responses (superposition).

Filtering an impulse with kernel H via correlation produces a spatially flipped copy of H (flipped left-right and up-down).

Correlation vs Convolution¶

Cross-correlation:

\[G[i,j] = \sum_{u=-k}^{k} \sum_{v=-k}^{k} H[u,v] \, F[i+u, j+v]\]

Convolution adds a 180-degree rotation of the kernel (flip both axes):

\[G[i,j] = \sum_{u=-k}^{k} \sum_{v=-k}^{k} H[u,v] \, F[i-u, j-v]\]

For symmetric kernels (e.g., Gaussian, box filter), correlation and convolution produce identical results. The distinction matters for asymmetric kernels (e.g., derivative filters).

Convolving any image with an impulse returns the original image.

Properties of Convolution¶

Commutative: \(f * g = g * f\)
Associative: \((f * g) * h = f * (g * h)\)
Identity: \(f * \delta = f\)
Differentiation: \(\frac{\partial}{\partial x}(f * g) = \left(\frac{\partial f}{\partial x}\right) * g\)

Computational Complexity and Separability¶

Filtering an \(N \times N\) image with a \(W \times W\) kernel requires \(O(W^2 N^2)\) multiplications.

A kernel is linearly separable if it can be expressed as the outer product of a column vector and a row vector: \(H = c \cdot r^T\). Then:

\[F * H = F * (c * r) = (F * r) * c\]

This reduces cost to \(O(2WN^2)\) — a factor of \(W/2\) speedup.

Example: the kernel [[1,2,1],[2,4,2],[1,2,1]] separates into column [1,2,1]^T convolved with row [1,2,1].

Boundary Issues¶

When the kernel extends past image edges, the output boundary must be defined. Common strategies:

Clip (zero-pad): Assume pixels outside are 0. Causes darkening at edges.
Wrap (circular): Treat image as periodic. Introduces opposite-edge artifacts.
Replicate: Extend edge pixel values outward. Reasonable default.
Reflect (symmetric): Mirror the image at boundaries. Preserves local statistics; often preferred.

In MATLAB/Octave imfilter:

imfilter(img, h, 0)            % zero-pad (default)
imfilter(img, h, 'circular')   % wrap
imfilter(img, h, 'replicate')  % copy edge
imfilter(img, h, 'symmetric')  % reflect

Sharpening Filters¶

A sharpening filter is constructed as:

\[\text{sharp} = 2 \cdot \delta - \text{blur}\]

where \(\delta\) is the unit impulse and blur is a smoothing kernel (e.g., box filter). This is equivalent to adding the difference between the original and a blurred version back to the original:

\[I_{\text{sharp}} = I + (I - I_{\text{blur}}) = 2I - I_{\text{blur}}\]

The unsharp mask in Photoshop uses this principle: subtract a blurred copy from the original to enhance edges.

Median Filter¶

Gaussian/box averaging works for additive Gaussian noise but fails for salt-and-pepper noise (random pixels set to extreme values).

Median filter: replace each pixel with the median of its local neighborhood.

Properties:

Non-linear (not expressible as weighted sum)
Edge-preserving: does not blur sharp transitions
Eliminates impulse noise effectively since outliers are never selected as the median

MATLAB/Octave:

noisy = imnoise(img, 'salt & pepper', 0.02);
filtered = medfilt2(noisy, [3 3]);