20-Bio-B4 Robotics · May 2015
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Paper format: National Exams, May 2015 — 04-Bio-B4 Image Processing. Three hours, open book (any paper notes or textbooks permitted, but no calculator or computer). Six questions of equal value (20 marks each); five constitute a complete paper and only the first five appearing in the answer book are marked. All six are solved here, because this set is a study resource rather than an examination script. Every question is essay/descriptive (definitions, algorithm design, system design); the only quantitative content is the computational-complexity discussion in Question 3(f)/(g).
Reference texts (the books a candidate should have reviewed for this subject):
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.
For an $M \times N$ image $f(x, y)$, the 2D DFT is
$$F(u, v) = \sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x, y)\, e^{-j 2\pi \left( \frac{ux}{M} + \frac{vy}{N} \right)}, \quad u = 0, \dots, M-1,\ v = 0, \dots, N-1,$$
with the inverse transform $f(x, y) = \frac{1}{MN} \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u, v)\, e^{+j 2\pi \left( \frac{ux}{M} + \frac{vy}{N} \right)}$.
Spatial convolution becomes pointwise multiplication in the frequency domain (the convolution theorem), which is far cheaper than direct convolution for large kernels; frequency content directly exposes periodic structure (e.g. scan-line or moiré noise) that is difficult to isolate spatially; band-limited resizing/interpolation is naturally expressed as truncating or zero-padding the spectrum; and image sharpness/energy content is easy to quantify as the proportion of energy in high- versus low-frequency bands, which underlies compression.
Periodic noise removal (notch or band-reject filtering of scan-line/moiré artifacts) is effective because periodic spatial noise appears as isolated, well-separated peaks in the spectrum that can be surgically removed without disturbing the rest of the image. Image compression (DCT/DFT-based, as in JPEG) is effective because natural images concentrate most of their energy in a few low-frequency coefficients, so quantizing/discarding high-frequency coefficients removes little perceptible information. Large-kernel blurring and deblurring (inverse or Wiener filtering) are effective because deconvolution is a simple division in the frequency domain, $\hat{F}(u,v) = G(u,v)/H(u,v)$, versus solving a large linear system spatially.
The DFT provides no spatial localization — it cannot say where in the image a given frequency component occurs, which is a problem whenever the required processing is spatially varying (e.g. a spatially varying blur, or a local edit); the DFT implicitly assumes the image is periodic, so linear (non-circular) operations require explicit zero-padding to avoid wraparound artifacts; the transformed representation is complex-valued and not directly interpretable by inspection; and because the transform is global, even a small local edit requires transforming (and re-transforming) the entire image.
To compute the linear convolution $g = f * h$ using the frequency domain: zero-pad both $f$ (size $M_1 \times N_1$) and $h$ (size $M_2 \times N_2$) to a common size at least $(M_1+M_2-1)\times(N_1+N_2-1)$ (to avoid circular wraparound corrupting the result), compute $F = \mathcal{F}\{f\}$ and $H = \mathcal{F}\{h\}$ via the 2D DFT/FFT, form the pointwise product $G(u,v) = F(u,v)H(u,v)$, and take the inverse transform $g = \mathcal{F}^{-1}\{G\}$; the convolution theorem guarantees this equals the direct spatial convolution exactly.
The direct 2D DFT needs $O((MN)^2)$ complex multiplications (each of the $MN$ output points sums over all $MN$ input points). The 2D FFT, computed by row-column decomposition — a 1D FFT along every row, then a 1D FFT along every column of the result — needs only $O(MN \log(MN))$ multiplications: $M$ row-transforms of length $N$ cost $O(N\log N)$ each and $N$ column-transforms of length $M$ cost $O(M \log M)$ each, for a total of $O\!\left(MN(\log M + \log N)\right) = O(MN\log(MN))$. The efficiency comes from the Cooley-Tukey divide-and-conquer structure: each length-$n$ 1D FFT recursively splits the sequence into even- and odd-indexed halves, computes their (length-$n/2$) transforms, and recombines them using twiddle-factor symmetry ($e^{-j2\pi k/n}$ periodicity) so that a length-$n$ transform's cost is $2T(n/2) + O(n)$, which resolves to $O(n\log n)$ — each recursion level reuses work across "butterfly" pairs instead of recomputing every output from scratch, unlike the direct DFT.
A single-level 2D discrete wavelet transform (DWT), implemented as separable 1D filter banks applied along rows then columns with dyadic downsampling, costs $O(MN)$ — linear in the number of pixels — because each stage is a short, fixed-length FIR filter convolution (length independent of $M, N$) applied once per pixel, unlike the FFT's global, size-dependent butterfly network. A full multi-level (multi-octave) DWT recursively re-applies the transform only to the low-pass (approximation) sub-band, whose pixel count shrinks by $4\times$ per level in 2D; the total work across all levels is the geometric series $MN(1 + \tfrac{1}{4} + \tfrac{1}{16} + \cdots) < \tfrac{4}{3}MN$, still $O(MN)$ overall (confirmed by direct level-by-level counting in the accompanying script). This is strictly faster than the FFT's $O(MN\log(MN))$ because the wavelet filters are short and fixed while the FFT's per-sample cost grows with $\log(MN)$; the trade-off is that the DWT gives joint space-frequency (multiresolution) localization rather than the FFT's single global spectrum.
