Linear Filtering and Convolution

A linear filter (also called a neighborhood operator or linear shift-invariant system) produces an output image whose value at each pixel is a linear combination of input pixel values in a surrounding window. The pattern of weights is called the kernel or filter mask, written as a small array $h[i,j]$, typically odd-sized ($3\times3$, $5\times5$, …) so it has a well-defined center pixel. There are two closely related, frequently confused operations. Correlation places the kernel directly over the neighborhood and computes

Convolution first flips the kernel by 180° (negating both indices) and then does the same sliding sum:

For a kernel that is symmetric under 180° rotation (true of a Gaussian kernel and of a uniform box kernel), correlation and convolution give identical results. For an asymmetric kernel — a derivative kernel used for Image Gradients, for instance — they differ, and the distinction matters: convolution is the operation with the clean mathematical properties (associativity, commutativity, and a direct correspondence to multiplication in the frequency domain, previewed in The Fourier View of Images), while correlation is what most image-processing libraries actually implement by default because it is more intuitive to specify ("the kernel is the pattern you're matching"). Two properties make this operation worth an entire formal theory rather than being a mere trick. Linearity means filtering a sum of images equals the sum of filtering each image, and scaling an image before filtering scales the output identically: $T(\alpha f_1 + \beta f_2) = \alpha T(f_1) + \beta T(f_2)$. Shift invariance means sliding the input by $(dx,dy)$ before filtering produces exactly the same output slid by $(dx,dy)$ — the filter has no notion of "special" image locations. A system with both properties is called an LSI (linear shift-invariant) system, and a classical result of signal processing states that every LSI system is expressible as a convolution with some kernel — the kernel is the system's complete description, called its impulse response.

The mechanical procedure is the same for correlation and convolution up to the kernel flip, so the pseudocode below implements correlation and notes the one-line change needed for true convolution.

Step 1 — choose the kernel. A $(2k+1)\times(2k+1)$ array of weights, e.g. a $3\times3$ box-blur kernel of all $\tfrac19$, or a Sobel derivative kernel.

Step 2 — decide the border policy. The kernel needs pixels outside the image whenever its center sits within $k$ pixels of an edge. Common choices: zero-padding (treat outside pixels as 0), replicate (clamp to nearest edge pixel), reflect (mirror across the edge), and wrap (treat the image as periodic/toroidal). Each yields a different — sometimes very different — output near the border.

Step 3 — slide and accumulate. For every output pixel, center the kernel there, multiply kernel weights by the (possibly border-extended) underlying pixels, and sum.

Step 4 — (optional) normalize / clip. If the kernel weights do not sum to 1 (e.g. a derivative kernel), the output may need rescaling for display, and values may need clipping into the valid intensity range. ``` function FILTER(image F, kernel H, mode): # mode ∈ {correlate, convolve} (W, H_img) = size(F) k = (size(H) - 1) / 2 # assumes H is (2k+1) x (2k+1) G = new image of size (W, H_img) for y in 0 .. H_img - 1: for x in 0 .. W - 1: sum = 0 for j in -k .. k: for i in -k .. k: if mode == convolve: (hi, hj) = (-i, -j) # flip kernel indices else: (hi, hj) = (i, j) (sx, sy) = BORDER(x - i, y - j, W, H_img) # or x+i,y+j; see note sum += H[hi + k][hj + k] * F[sx][sy] G[x][y] = sum return G function BORDER(sx, sy, W, H_img):

# zero-pad: caller instead returns 0 directly when sx,sy out of range

# replicate: sx = clamp(sx, 0, W - 1) sy = clamp(sy, 0, H_img - 1) return (sx, sy) ``` A production implementation exploits separability: if a 2-D kernel can be written as an outer product of two 1-D kernels, $H = v\,u^{T}$ (true of the box filter and the Gaussian filter), then filtering with $H$ is identical to filtering with $u$ along rows and then $v$ along columns: ``` function SEPARABLE_FILTER(image F, vector u, vector v):

# H = v * u^T (rank-1 kernel) Temp = FILTER_1D_HORIZONTAL(F, u) # convolve each row with u G = FILTER_1D_VERTICAL(Temp, v) # convolve each column with v return G ``` This is not an approximation — it is algebraically exact, because the 2-D sum factors:

Time complexity. For an image with $N = W \times H$ pixels and a $(2k{+}1)\times(2k{+}1)$ kernel, the direct (naive) algorithm visits every output pixel once and does $O(k^2)$ multiply-adds per pixel, giving

This is tight for the direct method: every one of the $k^2$ kernel taps genuinely must be read and multiplied for a general (non-separable) kernel, so no direct algorithm can do fewer operations without extra structure. If the kernel is separable ($H = v u^{T}$, rank 1), filtering decomposes into two 1-D passes, each doing $O(k)$ work per pixel, for a total of

This is a genuine asymptotic win — for a $15\times15$ kernel, $k^2 = 225$ versus $2k = 30$, roughly a 7.5× speedup — and it is exact, not approximate, because of the algebraic factoring shown above. A third route uses the convolution theorem: multiplying in the frequency domain via the FFT costs $O(N \log N)$ regardless of $k$, which wins asymptotically once $k$ is large enough relative to $\log N$; the crossover in practice is typically around $k$ in the dozens, since the FFT carries constant-factor and memory overhead that direct or separable filtering avoids for small kernels.

Space complexity. The direct and separable algorithms need $O(N)$ space for the output image (plus $O(N)$ for the intermediate pass in the separable case, or in-place with care), and $O(k^2)$ or $O(k)$ for the kernel itself — negligible compared to the image. FFT-based filtering needs $O(N)$ working space for the transformed arrays, with a larger constant due to complex-valued intermediate storage and (for linear, not circular, convolution) zero-padding to at least $W + k - 1$ by $H + k - 1$.

Correctness argument. The claim to justify is not an algorithmic subtlety but a mathematical identity: the sliding-window sum, as defined, is correlation or convolution by construction, so correctness reduces to showing the loop faithfully implements the sum. Three invariants guarantee this: 1. Index coverage. For each output location $(x,y)$, the inner double loop over $i, j \in [-k,k]$ visits every kernel tap exactly once, matching the summation range in the definition. 2. Correct addressing. For correlation the sample read is $f[x+i, y+j]$; for convolution it is $f[x-i, y-j]$ — equivalently, correlation with the 180°-rotated kernel. Implementing the flip as `hi, hj = -i, -j` while still reading `F[x - i][y - j]` reproduces exactly the convolution sum; swapping only one of the two (kernel index or image index) but not both is the classic bug that silently turns convolution into correlation or vice versa. 3. Border consistency. Whatever border policy is chosen, it must be applied consistently to every out-of-range access, otherwise the boundary handling itself is not shift-invariant (a pixel near the top edge and an identical pixel pattern near the left edge should be treated by the same rule, just reflected in orientation). Given these invariants hold, the output at every pixel equals the defined sum exactly (up to floating-point rounding), so the algorithm is correct. Separability's correctness follows from the distributive-law factoring shown earlier — it is not a heuristic approximation, so the separable and direct algorithms are provably identical (up to floating-point associativity effects), not merely similar.

Honest tradeoffs. Larger kernels blur more but cost proportionally more time ($O(k^2)$) unless separable. Zero-padding introduces a dark halo near edges (output pixels near the border are biased toward zero); replicate and reflect avoid that bias but can create artifacts of their own (replicate can smear an edge feature; reflect assumes local symmetry that may not exist). FFT-based convolution is asymptotically superior for large kernels but adds implementation complexity, a periodic-wraparound artifact if padding is insufficient, and higher constant overhead unsuitable for the small $3\times3$–$7\times7$ kernels dominant in classical vision.

Take a $5\times5$ grayscale image (values 0–9, purely illustrative) and correlate it with the non-symmetric $3\times3$ kernel

(the horizontal Sobel kernel, foreshadowing Image Gradients), using zero-padding, and compute one interior output pixel by hand to make the flip/no-flip distinction concrete. Image $F$ (rows top to bottom, columns left to right, 0-indexed):

This is a vertical step edge (dark on the left, bright on the right) — exactly the pattern Sobel-x is designed to detect.

Correlation at pixel $(r2, c2)$. The $3\times3$ neighborhood centered there (rows 1–3, cols 1–3):

Correlation multiplies elementwise with $H$ as written and sums:

Convolution at the same pixel. First flip $H$ by 180° (reverse both rows and columns):

Now correlate $N$ with $H_{\text{flip}}$:

So at this pixel correlation gives $-24$ and convolution gives $+24$ — exact sign flips, as expected for a kernel that is antisymmetric under 180° rotation. Both correctly signal "there is a strong vertical edge here"; the sign merely encodes which side is brighter, and a consistent choice (always convolution, or always correlation) must be used throughout a pipeline so signs stay comparable across the whole image.

Border pixel check. Now compute correlation at $(r0, c0)$, which needs zero-padded neighbors above and to the left:

Compare this to the true (unpadded) local pattern, which is uniformly $2$ in the visible region — an interior pixel deep inside the left constant region gives exactly $0$ (no edge), while this corner pixel gives $-6$ purely because zero-padding manufactured a fake dark region outside the image. This is precisely the border artifact discussed in Complexity & Correctness: it is not a bug in the loop, but a consequence of the chosen border policy, and a replicate border would have returned $0$ here instead, matching the interior behavior.

The mathematics of convolution predates computer vision by roughly two centuries, developed for analyzing linear systems in physics and later electrical engineering; image filtering imported this apparatus wholesale once digital images and Digital Images and Sampling made it computable.

The throughline from Fourier's series to Sobel's edge kernel to LeCun's learned filters is the same sliding-window sum: only the source of the kernel weights changes, from analytic derivation, to manual engineering, to gradient-based learning.

Camera image signal processors (ISPs) apply small linear filters at every stage of the pipeline: demosaicing interpolation, noise reduction, and sharpening (an "unsharp mask," itself a linear filter combination) all run before an image is even displayed. Medical imaging systems filter CT and MRI slices to suppress acquisition noise while preserving diagnostic edges. Classical computer vision feature detectors — Sobel and Prewitt gradients, the Laplacian of Gaussian, the Harris corner detector — are built from a handful of small, fixed convolution kernels applied in sequence. In deep learning, the convolutional layer at the heart of every CNN (from LeNet to ResNet to modern vision transformer hybrids that still use convolutional stems) performs exactly the sliding weighted-sum operation described here, differing only in that the kernel weights are learned by gradient descent rather than hand-designed, and that many kernels (channels) are learned and combined at once. GPUs and specialized accelerators are built around fast convolution primitives (im2col + matrix multiply, Winograd convolution, FFT-based convolution) precisely because this operation is the dominant cost in both classical and learned vision pipelines. Video codecs and graphics pipelines use separable filters for fast resizing and blurring at real-time frame rates, directly exploiting the $O(Nk)$ separable complexity argued above.

Ask the tutor: How does the convolution theorem let us compute large-kernel filtering faster using the FFT, and why does zero-padding size matter there?