20-Bio-B4 Robotics · December 2015
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Paper format: National Exams, December 2015 — 04-Bio-B4 Digital 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/system design) except the convolution-size and complexity items in Question 2, the median-filter nonlinearity proof in Question 2(d)(ii), and the illustrative numeric examples worked into Questions 4 and 6.
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.
A finite impulse response (FIR) filter's output at any pixel is a weighted sum of a finite number of neighbouring input samples (no feedback), so its impulse response has finite support; an infinite impulse response (IIR) filter feeds its own past output back into the computation, so its impulse response can, in principle, persist forever. FIR filters dominate 2D image filtering because (i) FIR filters are always stable regardless of coefficient choice, while a 2D IIR filter's stability region is far harder to characterize and guarantee than the well-understood 1D case; (ii) FIR filters can be made exactly linear-phase (symmetric kernel), which avoids spatial ringing/distortion of edges — a property that matters visually far more than it does for 1D audio; and (iii) images are processed as small, finite 2D arrays with hard boundaries, and an FIR kernel's compact, finite support maps naturally onto that, whereas IIR's recursive dependence requires an awkward, boundary-sensitive 2D recursion (e.g. raster-scan causal/non-causal passes) for comparatively modest computational savings.
Two-dimensional discrete convolution slides the (flipped) kernel over the image; how far the kernel is allowed to overhang the image border fixes the output size:
i. Separable filter. A kernel is separable if it factors as an outer product, $h(m,n)=h_1(m)\,h_2(n)$. Its 2D FFT is then the outer product of two 1D FFTs, $H(u,v)=H_1(u)\,H_2(v)$, and the fast implementation applies two 1D FFT-based filters in sequence, one per axis:
$$g = \text{IFFT}_{\text{cols}}\big(H_2(v)\cdot\text{FFT}_{\text{cols}}\big(\text{IFFT}_{\text{rows}}(H_1(u)\cdot\text{FFT}_{\text{rows}}(f))\big)\big)$$e.g. $h_1=[1,2,1]$, $h_2=[1,0,-1]$ gives the separable kernel $h(m,n)=h_1(m)h_2(n)$ (a Sobel-type edge kernel): $H(u,v)=H_1(u)H_2(v)$ exactly, so row-wise filtering by $h_1$ followed by column-wise filtering by $h_2$ (each a 1D FFT-domain multiply) reproduces the full 2D result. Algebraically, a kernel is separable exactly when its matrix has rank 1 (every $2\times2$ minor vanishes) — $h_1\otimes h_2$ above is rank 1 by construction.
ii. Non-separable filter. A kernel that is not rank 1 (e.g. the discrete Laplacian $h=\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}$, whose top-left $2\times2$ minor is $0\cdot(-4)-1\cdot1=-1\neq0$) cannot be written as $h_1(m)h_2(n)$ for any choice of $h_1,h_2$, so it has no row-then-column shortcut. The FFT-based implementation must instead use the full 2D transform directly:
$$G(u,v) = F(u,v)\,H(u,v), \qquad g = \text{IFFT}_{2D}(G)$$with $H(u,v)=\text{FFT}_{2D}(h_{\text{padded}})$ computed once as a genuinely two-dimensional transform, not as a product of two 1D transforms.
i. Why the median filter is attractive. The median of a neighbourhood is robust to outliers: a single wildly-off pixel (impulsive/salt-and-pepper noise) shifts a mean filter's output substantially but has almost no effect on the median, which simply ignores it as long as it is not the majority value. Unlike a linear (mean/Gaussian) filter, the median also does not blur sharp edges — at a step edge the window is dominated by one side's values, and the median returns one of the actual pixel values on that side rather than an interpolated in-between value — so it removes impulsive noise while preserving edge sharpness, which a linear low-pass filter cannot do simultaneously.
ii. Proof that the median filter is nonlinear. A filter $T$ is linear only if it satisfies both homogeneity, $T(ka)=kT(a)$, and additivity, $T(a+b)=T(a)+b)$. Take a 3-pixel window $a=[1,2,9]$ and $b=[1,8,2]$: $\text{median}(a)=2$ and $\text{median}(b)=2$, so $\text{median}(a)+\text{median}(b)=4$. But the elementwise sum is $a+b=[2,10,11]$, whose median is $10$ — not $4$. Homogeneity alone can hold (e.g. $\text{median}(3a)=6=3\cdot\text{median}(a)$) while additivity fails, and failing additivity is sufficient on its own to disprove linearity.
| Signal | Values | Median |
|---|---|---|
| $a$ | 1, 2, 9 | 2 |
| $b$ | 1, 8, 2 | 2 |
| $\text{median}(a)+\text{median}(b)$ | — | 4 |
| $a+b$ (elementwise) | 2, 10, 11 | 10 $\neq$ 4 |
Wavelet shrinkage denoises by exploiting the fact that a wavelet transform concentrates a natural image's true structure into a small number of large-magnitude coefficients while additive noise spreads roughly evenly across all coefficients (including the many small ones a clean image would not have). The strategy is: (1) take the discrete wavelet transform of the noisy image, (2) apply a threshold to every detail (high-frequency) coefficient — hard thresholding zeros any coefficient below a threshold $\lambda$, soft thresholding additionally shrinks the surviving coefficients toward zero by $\lambda$ (removing the noise floor without leaving a sharp on/off discontinuity), and (3) inverse-transform back to the image domain. Because genuine edges/texture produce large coefficients that survive thresholding while noise-sized small coefficients are suppressed, this removes noise with far less edge-blurring than an equivalent spatial-domain low-pass filter.
