Question 2 of 6: Image Filtering

Question 2: Image Filtering (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. An image $f$ of size $M_1\times N_1$ convolved with a kernel $h$ of size $M_2\times N_2$.

Find. (a) The three possible output sizes. (b)–(c) How to compute the convolution directly and via the FFT. (d) The practical issues with FFT-based convolution. (e) Why naive 3D convolution is a poor fit for video.

(a) The Three Convolution Output Sizes

How far the (flipped) kernel is allowed to overhang the image border fixes the output size:

• "Full" convolution keeps every position with any non-zero overlap: size $(M_1+M_2-1)\times(N_1+N_2-1)$. Example: a $256\times256$ image with a $9\times9$ kernel gives $264\times264$.
• "Same" convolution crops the full result (equivalently, zero-pads $f$ first) so the output matches the input size: $M_1\times N_1 = 256\times256$. This is the default size used by most image-filtering functions.
• "Valid" convolution keeps only positions where the kernel lies entirely inside $f$: size $(M_1-M_2+1)\times(N_1-N_2+1) = 248\times248$.

A second, non-square example makes the asymmetry between axes explicit: $f$ of size $15\times11$ with $h$ of size $4\times6$ gives full $=18\times16$ and valid $=12\times6$.

(b) Direct Computation of $g=f*h$

function g = convolve2D(f, h)
    [M1, N1] = size(f);
    [M2, N2] = size(h);
    Mg = M1 + M2 - 1;  Ng = N1 + N2 - 1;   % "full" output
    g = zeros(Mg, Ng);
    for m = 1:Mg
        for n = 1:Ng
            acc = 0;
            for p = 1:M2
                for q = 1:N2
                    i = m - p + 1;  j = n - q + 1;   % f-index for flipped kernel
                    if i >= 1 && i <= M1 && j >= 1 && j <= N1
                        acc = acc + f(i, j) * h(M2 - p + 1, N2 - q + 1);
                    end
                end
            end
            g(m, n) = acc;
        end
    end
end

The kernel is flipped in both axes (index $M_2-p+1,\,N_2-q+1$) per the definition of convolution (as opposed to correlation, which skips the flip); every output pixel sums the elementwise product of $h$ (flipped) with whichever part of $f$ it currently overlaps, and out-of-range $f$ indices are simply skipped (equivalent to zero-padding $f$).

(c) Computing $g$ via Fourier Transforms

The convolution theorem states that convolution in the spatial domain is equivalent to elementwise multiplication in the frequency domain: $G(u,v)=F(u,v)\,H(u,v)$, where $F,H$ are the 2D Fourier transforms of $f,h$. The method is therefore: (1) zero-pad both $f$ and $h$ to a common size at least $(M_1+M_2-1)\times(N_1+N_2-1)$ (Question 2(d) explains why), (2) compute $F(u,v)$ and $H(u,v)$, (3) multiply elementwise to get $G(u,v)$, and (4) inverse-transform: $g=\mathcal{F}^{-1}\{G\}$. This was verified directly here on a 1D example ($x=[1,2,3,4,0,1,2]$, $h=[1,0,-1]$, both zero-padded to length $L=9=\mathrm{len}(x)+\mathrm{len}(h)-1$): the elementwise-product-then-inverse-transform result matches the direct linear convolution to numerical precision, confirming the theorem's correctness in practice, not just in principle.

(d) Issues Using the FFT to Compute a Convolution

• Zero-padding to avoid circular wraparound. The DFT/FFT is inherently circular: multiplying two length-$N$ transforms and inverting gives circular convolution, which wraps the tail of the true linear-convolution result around onto the front. Padding both signals to at least $M_1+M_2-1$ (per axis, in 2D) before transforming is required to make the circular result equal the desired linear one; this was confirmed directly — repeating the (c) example WITHOUT padding past the shorter of the two lengths produces a result that visibly disagrees with the correct linear convolution, exactly the aliasing this padding rule prevents.
• FFT size constraints. The classic radix-2 FFT is fastest for lengths that are a power of 2 (or at least highly composite); the required padded length $M_1+M_2-1$ is rounded UP to the next convenient FFT size, adding a small amount of extra padding beyond the strict minimum.
• Break-even point. FFT-based convolution costs $O(MN\log(MN))$ versus direct convolution's $O(M_1N_1M_2N_2)$; for a SMALL kernel (e.g. a $3\times3$ or $5\times5$ blur/edge kernel), direct spatial convolution is often cheaper in practice once implementation overhead (two forward transforms, one inverse, the elementwise multiply) is accounted for — the FFT route pays off mainly for large kernels.
• Complex arithmetic and numerical precision. The forward/inverse transforms are complex-valued even for a real input/kernel; the inverse transform's tiny imaginary residue (rounding error) must be discarded, and floating-point rounding accumulates across the transform-multiply-inverse chain.

(e) Why Naive 3D (Space-Space-Time) Convolution Is a Poor Fit for Video

Extending a 2D spatial kernel with a temporal dimension multiplies both the computational cost and the memory footprint by the kernel's temporal depth $T_k$, for no corresponding benefit in most video-processing tasks. Quantitatively, for an HD ($1920\times1080$) frame with a modest $5\times5$ spatial kernel: a per-frame 2D filter costs $1920\cdot1080\cdot5\cdot5$ multiplies per output frame, while a 3D filter with a $T_k=5$-frame-deep temporal extent costs exactly $T_k=5\times$ as many multiplies per output frame — and it must buffer $T_k=5$ full float32 frames ($\approx8.29$ MB each, $\approx39.55$ MB total) in memory before it can produce a single output frame, instead of the $\approx8.29$ MB a purely spatial (or causal, frame-by-frame) filter needs. Beyond cost, a non-causal 3D kernel centred in time cannot even emit its output for frame $t$ until $(T_k-1)/2=2$ future frames have arrived, imposing a real-time latency that most video applications (broadcast, video calls, robotics) cannot tolerate. Finally, most of what video processing actually needs — motion, which is a spatial displacement over time, not a fixed spatiotemporal weighting — is poorly modelled by a fixed 3D kernel in the first place; optical-flow/motion-compensated methods that explicitly track how content moves between frames (rather than blindly averaging co-located pixels across a time window) handle motion far more effectively and far more cheaply than a brute-force 3D convolution.