05

CSS 433 Computer Vision: Chapter 5 (Part 1)

Spatial Domain Filtering — Complete Technical & Exam Preparation Guide

---

Module 1: Foundations of Spatial Domain Filtering

1. Filter Classifications & Definitions

Spatial domain filtering operates directly on the pixel grid $(x,y)$ of an image:

$g(x,y)=T[f(x,y)]$

Filters are categorized along two primary axes:

Frequency Domain Behavior

• Low-Pass Filters (LPFs): Attenuate high spatial frequencies (edges, noise, sharp texture) while passing low spatial frequencies (flat regions, smooth background). Used for smoothing, blurring, and noise suppression.
• High-Pass Filters (HPFs): Attenuate low spatial frequencies and pass high frequencies. Used for edge detection, detail extraction, and image sharpening.
• Band-Pass Filters (BPFs) & Band-Stop / Notch Filters: Pass or attenuate specific frequency bands (e.g., removing periodic hum or grid patterns).

Mathematical Operation

• Linear Filters: The output is a linear combination (weighted sum) of the input neighborhood values. They obey the Superposition Principle:

$T[a\cdot f_1(x,y)+b\cdot f_2(x,y)]=a\cdot T[f_1(x,y)]+b\cdot T[f_2(x,y)]$

• Non-Linear Filters: The output cannot be expressed as a linear sum of inputs. They are based entirely or partially on order statistics (e.g., median, min, max, mode) or conditional intensity differences (e.g., bilateral filters).

---

2. Mechanics of Linear Spatial Filtering

A small matrix called a filter mask, kernel, convolution mask, or impulse response of size $m\times n$ (with odd dimensions $m=2a+1$, $n=2b+1$) is scanned over every pixel of the input image.

       Image Coordinate System (f)          Mask Coordinate System (w)
            y (columns)                              t (horizontal)
        +------------------>                     +------------------>
        |                                        |  w(-1,-1) w(-1,0) w(-1,1)
        |       [ f(x,y) ]                       |  w( 0,-1) w( 0,0) w( 0,1)
      x |                                      s |  w( 1,-1) w( 1,0) w( 1,1)
  (rows)|                                  (rows)|
        v                                        v

Correlation vs. Convolution

• 2D Cross-Correlation ($f\otimes w$): Slips the mask across the image without rotation:

$g(x,y)={\sum }_{s=-a}^a{\sum }_{t=-b}^{b}w(s,t)f(x+s,y+t)$

• 2D Convolution ($f\ast w$): Rotates the mask by $180^{\circ }$ prior to computing the weighted sum:

$g(x,y)={\sum }_{s=-a}^a{\sum }_{t=-b}^{b}w(s,t)f(x-s,y-t)$

• 1D Vector Notation (Dot Product): Over a $3\times 3$ window, let $\mathbf{w}=[w_1,w_2,\dots ,w_9{]}^T$ and $\mathbf{f}=[f_1,f_2,\dots ,f_9{]}^T$. The response is the vector inner product:

$g={\mathbf{w}}^T\mathbf{f}={\sum }_{i=1}^9{w}_i{f}_i$

---

3. Linear Low-Pass Filtering (Weighted Arithmetic Mean)

The general form of a linear smoothing filter is a Weighted Arithmetic Mean (WAM):

$g(x,y)=\frac{{\sum }_{s=-a}^a{\sum }_{t=-b}^{b}w(s,t)f(x+s,y+t)}{{\sum }_{s=-a}^a{\sum }_{t=-b}^{b}w(s,t)}$

Standard $3\times 3$ LPF Kernels

$\text{Mean Filter (Box Blur): }{W}_{\text{mean}}=\frac{1}{9}\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]$

$\text{Gaussian Filter: }{W}_{\text{Gauss}}=\frac{1}{16}\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 1& 2& 1\end{array}\right]$

   Gaussian Weight Surface (3x3):
             [1/16]  [2/16]  [1/16]
             [2/16]  [4/16]  [2/16]   <--- Peak weight at center (4/16)
             [1/16]  [2/16]  [1/16]

Universal Properties of Linear LPFs

1. Sum of normalized coefficients equals 1: $\sum w_i=1$. This ensures that a uniform intensity region ($f(x,y)=C$) is invariant under filtering ($g(x,y)=C\cdot \sum w_i=C$).
2. Symmetry: Coefficients are symmetric with respect to the mask center ($w(s,t)=w(-s,-t)$).
3. Noise Spreading: A linear LPF suppresses an impulse by attenuating its peak amplitude and spreading its energy into an area equal to the mask dimensions. It does not eliminate the noise energy.
4. Mask Size Impact: The larger the mask ($3\times 3\to 5\times 5\to 35\times 35$), the greater the blurring power and noise reduction, but edge localization is severely degraded.

---

4. Boundary Padding & Why Filtering Causes Black Frames

When a mask of size $m\times m$ ($m=2k+1$) centers on a boundary pixel, the mask overhangs the edge by $k$ pixels. MATLAB’s imfilter handles boundary values through four distinct modes:

Boundary Extension Modes (for boundary [a b c]):
Zero-Padding (Default):   0   0 | a  b  c | 0   0   <-- Discontinuity causes black border
Symmetric (Mirror):       c   b | a  b  c | c   b
Replicate (Clamp/Extend): a   a | a  b  c | c   c
Circular (Periodic):      b   c | a  b  c | a   b

The Root Cause of Black Frames

By default, functions like MATLAB’s imfilter(img, mask) pad outer boundary coordinates with zero (X = 0).

• When an averaging mask centers on an outer border pixel, multiple elements of its neighborhood are zero.
• As a result, the weighted sum drops sharply near the border:

$g(\text{border})\approx \frac{1}{9}{\sum }_{\text{valid}}{f}_i\ll f(\text{border})$

• This creates a dark, faded perimeter around the filtered image. Using 'replicate' or 'symmetric' avoids this issue because boundary pixels mirror or clamp valid image data.

---

5. Separable 2-D Filters

A 2D spatial convolution mask $K$ of size $k\times k$ is separable if and only if it has a matrix rank of 1:

$\text{Rank}(K)=1⟺K=\mathbf{v}\cdot {\mathbf{h}}^T=\left[\begin{array}{c}a\\ b\\ c\end{array}\right]\left[\begin{array}{ccc}d& e& f\end{array}\right]=\left[\begin{array}{ccc}ad& ae& af\\ bd& be& bf\\ cd& ce& cf\end{array}\right]$

Computational Complexity Proof

Let an image have size $M\times N$, processed with a $k\times k$ kernel.

• Direct 2D Convolution: Every pixel requires $k^2$ multiplications and $k^2-1$ additions:

$\text{Total Multiplications}=M\cdot N\cdot k^2⟹\mathcal{O}(M\cdot N\cdot k^2)$

• Separated 1D Filtering: Convolve row-wise with ${\mathbf{h}}^T$ ($k$ multiplications per pixel), then column-wise with $\mathbf{v}$ ($k$ multiplications per pixel):

$\text{Total Multiplications}=M\cdot N\cdot k+M\cdot N\cdot k=M\cdot N\cdot (2k)⟹\mathcal{O}(M\cdot N\cdot 2k)$

$\text{Algorithmic Speedup}=\frac{k^2}{2k}=\frac{k}{2}$

For a $5\times 5$ filter, the operation is $2.5\times$ faster; for a $15\times 15$ filter, it is $7.5\times$ faster.

---

Module 2: Exercises 1–4 Solutions & Analysis

Coordinate Grid for Exercises 1 to 4:
Row 1: (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)
Row 2: (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7)
Row 3: (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7)
Row 4: (4,1) (4,2) (4,3) [4,4] (4,5) (4,6) (4,7)  <-- Impulse noise at (4,4)
Row 5: (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7)
Row 6: (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7)
Row 7: (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7)

---

Exercise 1: Mean Filtering on an Impulse Noise

Input

A $7\times 7$ image of zeros with an isolated impulse noise of value $144$ at central coordinate $(4,4)$:

$W_{\text{mean}}=\frac{1}{9}\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]$

Step-by-Step Calculation

• For any pixel $(r,c)$ whose $3\times 3$ neighborhood does not include $(4,4)$, all pixel values are zero:

$g(r,c)=\frac{1}{9}(0)=0$

• For any pixel $(r,c)$ whose $3\times 3$ neighborhood includes $(4,4)$ (meaning $r\in [3,5]$ and $c\in [3,5]$), the neighborhood contains eight zeros and one value of $144$:

$g(r,c)=\frac{1}{9}(144\times 1)=16$

Output Matrix

$$\left[\begin{array}{ccccccc}0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 16& 16& 16& 0& 0\\ 0& 0& 16& 16& 16& 0& 0\\ 0& 0& 16& 16& 16& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

Core Insight: The single sharp spike of $144$ was not eliminated. It was dispersed across a $3\times 3$ area with a lowered amplitude of $16$.

---

Exercise 2: Gaussian Filtering on an Impulse Noise

Input

The same $7\times 7$ image with an impulse of $144$ at $(4,4)$:

$W_{\text{Gauss}}=\frac{1}{16}\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 1& 2& 1\end{array}\right]$

Step-by-Step Calculation

The impulse response of a linear filter centered on a unit delta function is the filter mask itself scaled by the impulse amplitude:

$g(r,c)=144\cdot \frac{w(4-r,4-c)}{16}=9\cdot w(4-r,4-c)$

• At center $(4,4)$, mask coefficient is $4$: $g(4,4)=\frac{144\times 4}{16}=9\times 4=36$
• At 4-neighbors $(3,4),(5,4),(4,3),(4,5)$, mask coefficient is $2$: $g=\frac{144\times 2}{16}=9\times 2=18$
• At diagonal corners $(3,3),(3,5),(5,3),(5,5)$, mask coefficient is $1$: $g=\frac{144\times 1}{16}=9\times 1=9$
• All other pixels do not overlap $(4,4)$: $g=0$

Output Matrix

$$\left[\begin{array}{ccccccc}0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 9& 18& 9& 0& 0\\ 0& 0& 18& 36& 18& 0& 0\\ 0& 0& 9& 18& 9& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

---

Exercise 3: Mean Filtering on a Ramp Signal with Impulse Noise

Input

A background ramp decreasing by $10$ per row, with an impulse noise of $174$ located at $(4,4)$:

• Row 1: $60$, Row 2: $50$, Row 3: $40$, Row 4: $30$ (with $f(4,4)=174$), Row 5: $20$, Row 6: $10$, Row 7: $0$.

Analytical Solution via Principle of Superposition

Because the filter is linear, decompose the image into two additive components:

$f(x,y)=f_{\text{ramp}}(x,y)+f_{\text{noise}}(x,y)$

Where $f_{\text{noise}}(4,4)=174-30=144$, and $0$ elsewhere.

$g(x,y)=W\ast f_{\text{ramp}}+W\ast f_{\text{noise}}$

1. Response to Linear Ramp ($W\ast f_{\text{ramp}}$): For any interior row $r$ away from boundary limits, the vertical neighbors are $(r-1)$, $r$, and $(r+1)$. Because the vertical ramp is linear:

$\text{Mean}=\frac{(I_r+10)\times 3+I_r\times 3+(I_r-10)\times 3}{9}=\frac{9I_r}{9}=I_r$

The linear filter reconstructs the underlying linear ramp without distortion.

2. Response to Noise ($W\ast f_{\text{noise}}$): From Exercise 1, the noise contribution adds $16$ across the $3\times 3$ neighborhood around $(4,4)$.

Output Matrix

$$\left[\begin{array}{ccccccc}60& 60& 60& 60& 60& 60& 60\\ 50& 50& 50& 50& 50& 50& 50\\ 40& 40& 56& 56& 56& 40& 40\\ 30& 30& 46& 46& 46& 30& 30\\ 20& 20& 36& 36& 36& 20& 20\\ 10& 10& 10& 10& 10& 10& 10\\ 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

(Values in bold represent $I_{\text{ramp}}+16$)

---

Exercise 4: Gaussian Filtering on a Ramp Signal with Impulse Noise

Input

The same ramp background with impulse $174$ at $(4,4)$, using the $3\times 3$ Gaussian kernel.

Step-by-Step Calculation

1. Response to Linear Ramp: For each row $r\in [2,6]$:
   • Row above contributes weight $1+2+1=4$, value $I_r+10$
   • Center row contributes weight $2+4+2=8$, value $I_r$
   • Row below contributes weight $1+2+1=4$, value $I_r-10$

$g_{\text{ramp}}(r)=\frac{4(I_r+10)+8(I_r)+4(I_r-10)}{16}=\frac{16I_r}{16}=I_r$

2. Add Noise Response (from Exercise 2):
   • Row 3: $40+[9,18,9]⟹[49,58,49]$
   • Row 4: $30+[18,36,18]⟹[48,66,48]$
   • Row 5: $20+[9,18,9]⟹[29,38,29]$

Output Matrix

$$\left[\begin{array}{ccccccc}60& 60& 60& 60& 60& 60& 60\\ 50& 50& 50& 50& 50& 50& 50\\ 40& 40& 49& 58& 49& 40& 40\\ 30& 30& 48& 66& 48& 30& 30\\ 20& 20& 29& 38& 29& 20& 20\\ 10& 10& 10& 10& 10& 10& 10\\ 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

---

Module 3: Non-Linear Filters (Bilateral, Median, and Mode)

1. Bilateral Filters (Tomasi & Manduchi, 1998)

Linear Gaussian filtering blurs across boundaries because it computes weights based solely on spatial distance. The Bilateral Filter (BF) preserves edges by incorporating both geometric closeness and photometric similarity.

Standard Gaussian:       Weight = f( Spatial Distance ||p - q|| )
Bilateral Filter:        Weight = f( Spatial Distance ||p - q|| ) * g( Intensity Difference |I_p - I_q| )

Mathematical Formulation

$g(i,j)=\frac{{\sum }_{s=-a}^a{\sum }_{t=-b}^{b}f(i+s,j+t)\cdot w_{\text{spatial}}(s,t)\cdot w_{\text{range}}(s,t)}{{\sum }_{s=-a}^a{\sum }_{t=-b}^b{w}_{\text{spatial}}(s,t)\cdot w_{\text{range}}(s,t)}$

Where:

$w_{\text{spatial}}(s,t)=\exp \left(-\frac{s^2+t^2}{2{\sigma }_1^2}\right)({\sigma }_1={\sigma }_d,\text{ spatial spread})$

$w_{\text{range}}(s,t)=\exp \left(-\frac{(f(i,j)-f(i+s,j+t){)}^2}{2{\sigma }_2^2}\right)({\sigma }_2={\sigma }_r,\text{ photometric range spread})$

Parameter Mechanics

• ${\sigma }_1$ (Spatial Parameter): Controls the spatial neighborhood scale. Larger ${\sigma }_1$ averages over wider neighborhoods.
• ${\sigma }_2$ (Range Parameter): Controls sensitivity to intensity boundaries:
  • As ${\sigma }_2\to \infty$, $w_{\text{range}}\to 1$: the bilateral filter converges to a standard linear Gaussian blur.
  • As ${\sigma }_2\to 0$, $w_{\text{range}}\to 0$ for any intensity difference: no smoothing occurs, leaving the input unchanged.
• Slide 16 Typo Note: In Slide 16 of the lecture presentation, the top Gaussian mask entry at $(row=2,col=5)$ has a value of $4$. The bottom-left table incorrectly shows a $2$, which the slide explicitly labels as a "Typo error!".

---

Exercise 5: Bilateral Filtering in 1-D

Problem

Given 1-D signal: $\mathbf{X}=[1,9,2,8,1,28,22,29,20,28]$

• Gaussian LPF: $\frac{1}{4}[1,2,1]$
• Median filter: size $1\times 3$
• Bilateral filter: $\text{Threshold}=10$. If $|X_i-X_{\text{neighbor}}|>10$, the difference is “great” and weight is set to $0$; otherwise weight is $1$. Spatial weights are $[1,2,1]$.
• Ignore boundaries $X_1=1$ and $X_{10}=28$.

Signal:   [ 1,   9,   2,   8,   1,  |  28,  22,  29,  20,  28 ]
Region:   <--- Low Intensities (~1-9) --> | <-- High Intensities (~20-29) -->
                                     STEP EDGE

Complete Computation Table

| Index $i$ | Window $[X_{i-1},X_i,X_{i+1}]$ | Gaussian LPF: $\frac{X_{i-1}+2X_i+X_{i+1}}{4}$ | Median ($1\times 3$) | Bilateral Filter Range Differences $|X_k-X_i|$ | Bilateral Filter Effective Weights & Output | | :------------------- | :------------------------------- | :--------------------------------------------------------- | :------------------------------------- | :----------------------------------- | :-------- | ------------------------------- | ------------------------------------------- | -------------------------- | --------------------------------------------------------------------------------------------------------- | | $i=2$ ($X_2=9$) | $[1,9,2]$ | $\frac{1+18+2}{4}=5.25$ | $\text{med}(1,2,9)=2$ | $|1-9|=8\le 10$
$|2-9|=7\le 10$ | Weights: $[1,2,1]$, $S=4$
$g_2=\frac{1(1)+2(9)+1(2)}{4}=5.25$ | | $i=3$ ($X_3=2$) | $[9,2,8]$ | $\frac{9+4+8}{4}=5.25$ | $\text{med}(2,8,9)=8$ | $|9-2|=7\le 10$
$|8-2|=6\le 10$ | Weights: $[1,2,1]$, $S=4$
$g_3=\frac{1(9)+2(2)+1(8)}{4}=5.25$ | | $i=4$ ($X_4=8$) | $[2,8,1]$ | $\frac{2+16+1}{4}=4.75$ | $\text{med}(1,2,8)=2$ | $|2-8|=6\le 10$
$|1-8|=7\le 10$ | Weights: $[1,2,1]$, $S=4$
$g_4=\frac{1(2)+2(8)+1(1)}{4}=4.75$ | | $i=5$ ($X_5=1$) | $[8,1,28]$ | $\frac{8+2+28}{4}=9.50$ (Edge blurred!) | $\text{med}(1,8,28)=8$ | $|8-1|=7\le 10$
$|28-1|=27>10⟹w_r=0$ | Weights: $[1,2,0]$, $S=1+2=3$
$g_5=\frac{1(8)+2(1)+0(28)}{3}=\frac{10}{3}=3.33$ | | $i=6$ ($X_6=28$) | $[1,28,22]$ | $\frac{1+56+22}{4}=19.75$ (Edge blurred!) | $\text{med}(1,22,28)=22$ | $|1-28|=27>10⟹w_r=0$
$|22-28|=6\le 10$ | Weights: $[0,2,1]$, $S=2+1=3$
$g_6=\frac{0(1)+2(28)+1(22)}{3}=\frac{78}{3}=26.00$ | | $i=7$ ($X_7=22$) | $[28,22,29]$ | $\frac{28+44+29}{4}=25.25$ | $\text{med}(22,28,29)=28$ | $|28-22|=6\le 10$
$|29-22|=7\le 10$ | Weights: $[1,2,1]$, $S=4$
$g_7=\frac{1(28)+2(22)+1(29)}{4}=25.25$ | | $i=8$ ($X_8=29$) | $[22,29,20]$ | $\frac{22+58+20}{4}=25.00$ | $\text{med}(20,22,29)=22$ | $|22-29|=7\le 10$
$|20-29|=9\le 10$ | Weights: $[1,2,1]$, $S=4$
$g_8=\frac{1(22)+2(29)+1(20)}{4}=25.00$ | | $i=9$ ($X_9=20$) | $[29,20,28]$ | $\frac{29+40+28}{4}=24.25$ | $\text{med}(20,28,29)=28$ | $|29-20|=9\le 10$
$|28-20|=8\le 10$ | Weights: $[1,2,1]$, $S=4$
$g_9=\frac{1(29)+2(20)+1(28)}{4}=24.25$ |

Exam Review Comparison

• Notice $i=5$ and $i=6$ at the step boundary between $1$ and $28$:
  • Gaussian LPF: Strongly blurs across the edge ($g_5=9.50,g_6=19.75$).
  • Bilateral Filter: The weight across the step edge drops to zero ($w_r=0$). It keeps the low side low ($g_5=3.33$) and the high side high ($g_6=26.00$), preserving the step boundary while smoothing noise on each flat plateau.

---

Exercise 6: Bilateral Filtering in 2-D

Input Image

A $5\times 5$ image containing a vertical boundary separating a $\sim 50$ region on the left from a $\sim 100$ region on the right:

$$I=\left[\begin{array}{ccccc}102& 104& 100& 98& 101\\ 100& 99& 101& 105& 102\\ 49& 51& 52& 97& 100\\ 50& 48& 53& 101& 102\\ 52& 49& 50& 100& 99\end{array}\right]$$

Filter Specification

• Spatial Gaussian mask: $W_s=\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 1& 2& 1\end{array}\right]$
• Range threshold: Difference $\le 25⟹\text{weight }1$; difference $>25⟹\text{weight }0$.
• Ignore boundary pixels; evaluate interior $3\times 3$ grid: rows $r\in [2,4]$, cols $c\in [2,4]$.

---

Step-by-Step Pixel Calculations

1. Pixel $(2,2)=99$ (Uniform High Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}102& 104& 100\\ 100& 99& 101\\ 49& 51& 52\end{array}\right]$
• Differences $|f_k-99|$: $\left[\begin{array}{ccc}3& 5& 1\\ 1& 0& 2\\ 50& 48& 47\end{array}\right]$
• Range weights $w_r$ (threshold $\le 25$): $\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 0& 0& 0\end{array}\right]$
• Effective weights $W_{\text{eff}}=W_s\odot w_r$: $\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 0& 0& 0\end{array}\right],\text{Sum }S=1+2+1+2+4+2=12$
• Filtered Value: $g(2,2)=\frac{1(102)+2(104)+1(100)+2(100)+4(99)+2(101)}{12}=\frac{1208}{12}\approx 100.67$

---

2. Pixel $(2,3)=101$ (Uniform High Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}104& 100& 98\\ 99& 101& 105\\ 51& 52& 97\end{array}\right]$
• Differences $|f_k-101|$: $\left[\begin{array}{ccc}3& 1& 3\\ 2& 0& 4\\ 50& 49& 4\end{array}\right]$
• Range weights $w_r$: $\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 0& 0& 1\end{array}\right]$
• Effective weights $W_{\text{eff}}$: $\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 0& 0& 1\end{array}\right],S=1+2+1+2+4+2+1=13$
• Filtered Value: $g(2,3)=\frac{104+200+98+198+404+210+97}{13}=\frac{1311}{13}\approx 100.85$

---

3. Pixel $(2,4)=105$ (Uniform High Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}100& 98& 101\\ 101& 105& 102\\ 52& 97& 100\end{array}\right]$
• Differences $|f_k-105|$: $\left[\begin{array}{ccc}5& 7& 4\\ 4& 0& 3\\ 53& 8& 5\end{array}\right]$
• Range weights $w_r$: $\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 0& 1& 1\end{array}\right]$
• Effective weights $W_{\text{eff}}$: $\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 0& 2& 1\end{array}\right],S=1+2+1+2+4+2+2+1=15$
• Filtered Value: $g(2,4)=\frac{100+196+101+202+420+204+194+100}{15}=\frac{1517}{15}\approx 101.13$

---

4. Pixel $(3,2)=51$ (Step Edge: Low Side)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}100& 99& 101\\ 49& 51& 52\\ 50& 48& 53\end{array}\right]$
• Differences $|f_k-51|$: $\left[\begin{array}{ccc}49& 48& 50\\ 2& 0& 1\\ 1& 3& 2\end{array}\right]$
• Range weights $w_r$: $\left[\begin{array}{ccc}0& 0& 0\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]$
• Effective weights $W_{\text{eff}}$: $\left[\begin{array}{ccc}0& 0& 0\\ 2& 4& 2\\ 1& 2& 1\end{array}\right],S=2+4+2+1+2+1=12$
• Filtered Value: $g(3,2)=\frac{2(49)+4(51)+2(52)+1(50)+2(48)+1(53)}{12}=\frac{98+204+104+50+96+53}{12}=\frac{605}{12}\approx 50.42$

---

5. Pixel $(3,3)=52$ (Low Side, Neighboring High Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}99& 101& 105\\ 51& 52& 97\\ 48& 53& 101\end{array}\right]$
• Differences $|f_k-52|$: $\left[\begin{array}{ccc}47& 49& 53\\ 1& 0& 45\\ 4& 1& 49\end{array}\right]$
• Range weights $w_r$: $\left[\begin{array}{ccc}0& 0& 0\\ 1& 1& 0\\ 1& 1& 0\end{array}\right]$
• Effective weights $W_{\text{eff}}$: $\left[\begin{array}{ccc}0& 0& 0\\ 2& 4& 0\\ 1& 2& 0\end{array}\right],S=2+4+1+2=9$
• Filtered Value: $g(3,3)=\frac{2(51)+4(52)+1(48)+2(53)}{9}=\frac{102+208+48+106}{9}=\frac{464}{9}\approx 51.56$

---

6. Pixel $(3,4)=97$ (High Side, Neighboring Low Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}101& 105& 102\\ 52& 97& 100\\ 53& 101& 102\end{array}\right]$
• Differences $|f_k-97|$: $\left[\begin{array}{ccc}4& 8& 5\\ 45& 0& 3\\ 44& 4& 5\end{array}\right]$
• Range weights $w_r$: $\left[\begin{array}{ccc}1& 1& 1\\ 0& 1& 1\\ 0& 1& 1\end{array}\right]$
• Effective weights $W_{\text{eff}}$: $\left[\begin{array}{ccc}1& 2& 1\\ 0& 4& 2\\ 0& 2& 1\end{array}\right],S=1+2+1+4+2+2+1=13$
• Filtered Value: $g(3,4)=\frac{101+210+102+388+200+202+102}{13}=\frac{1305}{13}\approx 100.38$

---

7. Pixel $(4,2)=48$ (Uniform Low Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}49& 51& 52\\ 50& 48& 53\\ 52& 49& 50\end{array}\right]$
• All differences $\le 5\le 25⟹$ all range weights are $1$.
• Effective weights equal the full Gaussian mask ($S=16$).
• Filtered Value: $g(4,2)=\frac{49+102+52+100+192+106+52+98+50}{16}=\frac{801}{16}\approx 50.06$

---

8. Pixel $(4,3)=53$ (Low Side, Bordering High Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}51& 52& 97\\ 48& 53& 101\\ 49& 50& 100\end{array}\right]$
• Differences $|f_k-53|$: $\left[\begin{array}{ccc}2& 1& 44\\ 5& 0& 48\\ 4& 3& 47\end{array}\right]$
• Range weights $w_r$: $\left[\begin{array}{ccc}1& 1& 0\\ 1& 1& 0\\ 1& 1& 0\end{array}\right]$
• Effective weights $W_{\text{eff}}$: $\left[\begin{array}{ccc}1& 2& 0\\ 2& 4& 0\\ 1& 2& 0\end{array}\right],S=1+2+2+4+1+2=12$
• Filtered Value: $g(4,3)=\frac{51+104+96+212+49+100}{12}=\frac{612}{12}=51.00$

---

9. Pixel $(4,4)=101$ (High Side, Bordering Low Region)

• Neighborhood $3\times 3$: $\left[\begin{array}{ccc}52& 97& 100\\ 53& 101& 102\\ 50& 100& 99\end{array}\right]$
• Differences $|f_k-101|$: $\left[\begin{array}{ccc}49& 4& 1\\ 48& 0& 1\\ 51& 1& 2\end{array}\right]$
• Range weights $w_r$: $\left[\begin{array}{ccc}0& 1& 1\\ 0& 1& 1\\ 0& 1& 1\end{array}\right]$
• Effective weights $W_{\text{eff}}$: $\left[\begin{array}{ccc}0& 2& 1\\ 0& 4& 2\\ 0& 2& 1\end{array}\right],S=2+1+4+2+2+1=12$
• Filtered Value: $g(4,4)=\frac{194+100+404+204+200+99}{12}=\frac{1201}{12}\approx 100.08$

---

Final Filtered Interior Grid

$$\left[\begin{array}{ccc}100.67& 100.85& 101.13\\ 50.42& 51.56& 100.38\\ 50.06& 51.00& 100.08\end{array}\right]$$

Conclusion: The boundary between the $\approx 51$ values and the $\approx 100$ values remains sharp. No intermediate blurred values (such as $75$) appear at the transition pixels $(3,3)$ and $(3,4)$.

---

2. Median Filters

The median filter replaces the center pixel with the statistical median of its neighborhood:

$g(x,y)=\text{median}\{f(s,t)\mid (s,t)\in S_{xy}\}$

Square Mask (3x3, N=9):                 Cross Mask (3x3, N=5):
      [ *  *  * ]                               [ .  *  . ]
      [ *  *  * ]                               [ *  *  * ]
      [ *  *  * ]                               [ .  *  . ]
Median is 5th ranked element.            Median is 3rd ranked element.

Core Properties & Design Rules

1. Outlier Removal: Completely eliminates impulse noise (salt-and-pepper) without blurring sharp step edges, because extreme values sort to the minimum or maximum ends of the array.
2. The $2\times$ Geometric Removal Rule: A median filter eliminates any target object or detail whose spatial width is less than half the mask size:

$W_{\text{mask}}\ge 2\cdot W_{\text{object}}+1$

To preserve an object, the mask must be smaller than twice the object width. 3. Square vs. Cross Mask: _ Square Mask ($3\times 3$): Better noise suppression ($9$ samples); rounds or erodes sharp $90^{\circ }$ corners and thin lines. _ Cross-Shape Mask ($3\times 3$): Better preservation of horizontal and vertical lines and sharp corners; weaker noise reduction ($5$ samples).

---

Exercise 7: Median Filtering on Image A and Image B

1. Processing Image A (Impulse noise at center)

Image A:
5   5   5   5   5
4   4   4   4   4
3   3  13   3   3   <-- Impulse noise of 13 at (3,3)
2   2   2   2   2
1   1   1   1   1

• At Center Pixel $(3,3)=13$:
  • Square $3\times 3$ mask: $\text{Neighborhood}=\{4,4,4,3,13,3,2,2,2\}$ $\text{Sorted}=[2,2,2,3,3,4,4,4,13]⟹\text{Median}=3$
  • Cross-shape $3\times 3$ mask: $\text{Neighborhood}=\{\text{top: }4,\text{ bottom: }2,\text{ left: }3,\text{ right: }3,\text{ center: }13\}$ $\text{Sorted}=[2,3,3,4,13]⟹\text{Median}=3$
• Result: Both masks successfully remove the impulse noise, restoring the underlying true value $3$.

---

2. Processing Image B (Corner Boundary)

Image B:
0   0   0   0   0
0   0   0   0   0
0   0  10  10  10   <-- Corner feature at (3,3)
0   0  10  10  10
0   0  10  10  10

• At Corner Pixel $(3,3)=10$:
  • Square $3\times 3$ mask: $\text{Neighborhood}=\left[\begin{array}{ccc}0& 0& 0\\ 0& 10& 10\\ 0& 10& 10\end{array}\right]$ $\text{Sorted}=[0,0,0,0,0,10,10,10,10]⟹\text{Median}=0$ (The corner pixel at $(3,3)$ is eroded to $0$. The square mask cuts the corner).
  • Cross-shape $3\times 3$ mask: $\text{Neighborhood}=\{\text{top: }0,\text{ bottom: }10,\text{ left: }0,\text{ right: }10,\text{ center: }10\}$ $\text{Sorted}=[0,0,10,10,10]⟹\text{Median}=10$ (The corner pixel is preserved).

---

Exercise 8: Median Filtering on Thin Vertical Lines

Inputs

• Image A: 1-pixel wide vertical line of zeros embedded in an image of tens.
• Image B: 1-pixel wide vertical line of tens embedded in an image of zeros.

    Image A (Dark Line):               Image B (Bright Line):
    10  10   0  10  10                  0   0  10   0   0
    10  10   0  10  10                  0   0  10   0   0
    10  10   0  10  10                  0   0  10   0   0
    10  10   0  10  10                  0   0  10   0   0
    10  10   0  10  10                  0   0  10   0   0

Calculations for Center Column ($c=3$)

1. Square $3\times 3$ Mask ($N=9$)

• Image A (Dark Line, Center = 0): Each row contains $[10,0,10]$. Across 3 rows, there are three $0$s and six $10$s. $\text{Sorted}=[0,0,0,10,10,10,10,10,10]⟹\text{Median}=10$ The 1-pixel dark line is completely eliminated.
• Image B (Bright Line, Center = 10): Each row contains $[0,10,0]$. Across 3 rows, there are six $0$s and three $10$s. $\text{Sorted}=[0,0,0,0,0,10,10,10,10]⟹\text{Median}=0$ The 1-pixel bright line is completely eliminated.

2. Cross-Shape $3\times 3$ Mask ($N=5$)

• Image A (Dark Line, Center = 0): Neighborhood: $\{\text{top: }0,\text{ bottom: }0,\text{ center: }0,\text{ left: }10,\text{ right: }10\}$. $\text{Sorted}=[0,0,0,10,10]⟹\text{Median}=0$ The dark vertical line is preserved.
• Image B (Bright Line, Center = 10): Neighborhood: $\{\text{top: }10,\text{ bottom: }10,\text{ center: }10,\text{ left: }0,\text{ right: }0\}$. $\text{Sorted}=[0,0,10,10,10]⟹\text{Median}=10$ The bright vertical line is preserved.

Summary Table

Input Pattern	Square $3\times 3$ Result	Cross-Shape $3\times 3$ Result
Image A (1-px Dark Line)	Line removed (replaced with $10$)	Line preserved ($0$)
Image B (1-px Bright Line)	Line removed (replaced with $0$)	Line preserved ($10$)

---

Exercise 9: Shading Correction via Median Filter

Problem Analysis

In the retinal fundus image (Slide 28), non-uniform background illumination (vignetting/shading) causes bright patches on one side and gradual darkening on the other, while thin blood vessels have fine spatial detail.

Retinal Model:      f(x,y) = Background_Shading(x,y) + Blood_Vessels(x,y)
Goal:               Isolate Blood_Vessels without shading artifacts.

Engineering Solution

1. Filter Selection: Apply a large 2D Median Filter to the image: $B(x,y)=\text{median\_filter}(f(x,y),W_{\text{large}})$
2. Filter Size Design:
   • Let the maximum blood vessel width be $d_{\text{vessel}}$ (typically $3$ to $7$ pixels).
   • Choose a mask dimension $W>2\cdot d_{\text{vessel}}+1$ (e.g., $31\times 31$ or $51\times 51$).
   • Because the mask is much wider than any vessel, the median filter treats the vessels as outliers and removes them entirely, leaving only the smoothly varying background shading $B(x,y)$.
3. Correction (Background Subtraction / Normalization):

$\text{Corrected Image }g(x,y)=f(x,y)-B(x,y)+C$

(Where $C$ is a constant, such as $128$, to center displayable dynamic range).

---

Exercise 10: Median Filtering on Lines of Various Geometries

Question 1: Two Crossing Lines of Width 1 Pixel

• Filter: 2D $3\times 3$ Median Filter:
  • Along the lines: 3 line pixels, 6 background pixels $⟹$ line is removed.
  • At the intersection $(x_0,y_0)$: The $3\times 3$ window contains 5 line pixels (one vertical line of 3, one horizontal line of 3, sharing the center) and 4 background pixels.
  • Sorted: four $0$s, five $1$s $⟹\text{Median}=1$.
  • Result: The crossing lines vanish, leaving a single isolated white dot at the intersection.
• Filter: 2D $5\times 5$ Median Filter:
  • At the intersection: Line pixels within the window form a cross: 5 horizontal + 5 vertical $-1$ center $=9$ line pixels.
  • Total pixels in $5\times 5=25$. Background pixels $=25-9=16$.
  • Sorted: sixteen $0$s, nine $1$s $⟹\text{Median}=0$.
  • Result: Both lines and their intersection are completely removed.

---

Question 2: Applying 1D Median Filters Separately and Sequentially

• 1D horizontal filter ($1\times 3$):
  • Scans horizontally. For a vertical line of width 1, the cross-section is $[0,1,0]⟹\text{Median}=0$. The vertical line is removed.
  • For a horizontal line, the cross-section along the filter is $[1,1,1]⟹\text{Median}=1$. The horizontal line is preserved.
• 1D vertical filter ($3\times 1$):
  • Scans vertically. The horizontal line has cross-section $[0,1,0{]}^T⟹\text{Median}=0$, so it is removed.
  • The vertical line has cross-section $[1,1,1{]}^T⟹\text{Median}=1$, so it is preserved.
• Sequential Application ($1\times 3$ followed by $3\times 1$):
  • Step 1 ($1\times 3$): Removes vertical line; keeps horizontal line.
  • Step 2 ($3\times 1$ applied to output of Step 1): Removes the remaining horizontal line.
  • Result: The entire image becomes completely black (all lines removed).

---

Question 3: Lines of Width 2 Pixels

• 2D Median Filter: To eliminate a 2-pixel wide line, the mask dimension must satisfy $W>2\cdot \text{width}=4⟹$ use a $5\times 5$ Square Median Filter.
• 1D Median Filter: To remove a 2-pixel wide line in 1D, use a $1\times 5$ (or $5\times 1$) filter. In a 5-element window, a 2-pixel line contributes 2 ones and 3 zeros $⟹\text{Median}=0$.

---

Question 4: Three Parallel Lines of Widths 1, 2, and 3 Pixels

Objective: Remove lines of widths 1 and 3, while preserving the line of width 2.

       Line 1 (w=1)           Line 2 (w=2)           Line 3 (w=3)
          |                      ||                     |||

1. Step 1: Apply a 1D median filter of size $1\times 3$ perpendicular to the lines.
   • Width 1 line: $[0,1,0]⟹$ removed ($0$).
   • Width 2 line: $[0,1,1]⟹$ preserved ($1$).
   • Width 3 line: $[1,1,1]⟹$ preserved ($1$).
   • Result: Contains lines of width 2 and width 3. Call this $I_{2,3}$.
2. Step 2: Apply a 1D median filter of size $1\times 5$ to $I_{2,3}$ (or to the original image).
   • Width 1 line: removed ($0$).
   • Width 2 line: $[0,0,1,1,0]⟹2$ ones, $3$ zeros $⟹$ removed ($0$).
   • Width 3 line: $[0,1,1,1,0]⟹3$ ones, $2$ zeros $⟹$ preserved ($1$).
   • Result: Contains only the line of width 3. Call this $I_3$.
3. Step 3 (Reconstruct Target): Subtract $I_3$ from $I_{2,3}$:

$I_{\text{target}}=I_{2,3}-I_3$

Result: The line of width 2 is isolated, while lines of widths 1 and 3 are eliminated.

---

3. Mode Filters & The “Oil Painting” Effect

• Definition: Replaces the center pixel with the statistical mode (the most frequently occurring intensity value) within the neighborhood:

$g(x,y)=\text{mode}\{f(s,t)\mid (s,t)\in S_{xy}\}$

• Visual Characteristic: It clusters local pixel values into piecewise-constant patches. Fine gradients collapse into flat color regions while major boundaries remain fixed.
• The “Oil Painting” Effect: Because gradual tonal changes are mapped to the locally dominant intensity, the image looks like it was rendered with brushstrokes of uniform paint.

% MATLAB implementation:
fun = @(x) mode(x(:));
OilPainting = nlfilter(double(img), [5 5], fun);

---

Module 4: High-Pass Filters & Gradient Operators

High-Pass Filters are based on spatial derivatives, measuring the rate of change of image intensity.

Edge Model:
Intensity Profile:   _____/‾‾‾‾‾  (Step / Ramp)
1st Derivative:      _____/\_____  (Forms an extreme peak at the slope)
2nd Derivative:      ___/\__\/___  (Forms a zero-crossing)

1. Mathematical Approximations of First Derivative

Two-Point Forward Approximation

$\frac{\partial f(x,y)}{\partial x}\approx \frac{f(x+\Delta x,y)-f(x,y)}{\Delta x}⟹\left[\begin{array}{cc}-1& 1\end{array}\right](\text{for }\Delta x=1)$

$\frac{\partial f(x,y)}{\partial y}\approx \frac{f(x,y+\Delta y)-f(x,y)}{\Delta y}⟹\left[\begin{array}{c}-1\\ 1\end{array}\right]$

Centered Difference Approximation

$\frac{\partial f(x,y)}{\partial x}\approx \frac{f(x+\Delta x,y)-f(x-\Delta x,y)}{2\Delta x}⟹\left[\begin{array}{ccc}-1/2& 0& 1/2\end{array}\right]$

$\frac{\partial f(x,y)}{\partial y}\approx \frac{f(x,y+\Delta y)-f(x,y-\Delta y)}{2\Delta y}⟹\left[\begin{array}{c}-1/2\\ 0\\ 1/2\end{array}\right]$

---

Exercise 11: First & Second Derivatives on a 1D Signal

Input Signal

Given discrete array: $\mathbf{X}=[5,5,5,17,5,5,5,14,14,14,14,5,5,5]$ Indices $n=1,2,\dots ,14$.

Operators

• 1st Derivative Kernel: $[-1,0,1]$ (Centered difference: $X_{n+1}-X_{n-1}$)
• 2nd Derivative Kernel: $[1,-2,1]$ (Laplacian: $X_{n+1}-2X_n+X_{n-1}$)

Step-by-Step Calculation Table

Index $n$	$X_n$	1st Derivative: $X_{n+1}-X_{n-1}$	2nd Derivative: $X_{n+1}-2X_n+X_{n-1}$	Feature Type
1	5	Boundary	Boundary	Flat
2	5	$5-5=0$	$5-2(5)+5=0$	Flat
3	5	$17-5=+12$	$17-2(5)+5=+12$	Step onset to isolated spike
4	17	$5-5=0$	$5-2(17)+5=-24$	Peak of isolated impulse
5	5	$5-17=-12$	$5-2(5)+17=+12$	Step return from spike
6	5	$5-5=0$	$5-2(5)+5=0$	Flat
7	5	$14-5=+9$	$14-2(5)+5=+9$	Leading edge of step
8	14	$14-5=+9$	$14-2(14)+5=-9$	Trailing edge of step onset
9	14	$14-14=0$	$14-2(14)+14=0$	Flat plateau
10	14	$14-14=0$	$14-2(14)+14=0$	Flat plateau
11	14	$5-14=-9$	$5-2(14)+14=-9$	Leading edge of downward step
12	5	$5-14=-9$	$5-2(5)+14=+9$	Trailing edge of downward step
13	5	$5-5=0$	$5-2(5)+5=0$	Flat
14	5	Boundary	Boundary	Flat

Key Takeaways for the Exam

• At the isolated noise point ($n=4$): The 1st derivative produces zero at the peak, flanked by $\pm 12$. The 2nd derivative produces a strong negative spike of $-24$, showing that the Laplacian responds intensely to isolated noise points.
• At the step edge ($n=7\to 8$): The 1st derivative produces a single-polarity hump ($+9,+9$). The 2nd derivative transitions from positive to negative ($+9\to -9$), producing a zero-crossing.

---

Exercise 12: Proof of Maximum Gradient Direction

Problem Statement

Prove that the directional derivative of an image $f(x,y)$ reaches its maximum magnitude along the direction of the gradient vector $\nabla f$.

Formal Mathematical Proof

1. Define Gradient Vector: The gradient of $f(x,y)$ is defined as: $\nabla f=\left[\begin{array}{c}\frac{\partial f}{\partial x}\\ \frac{\partial f}{\partial y}\end{array}\right]=\left[\begin{array}{c}{f}_x\\ f_y\end{array}\right]$
2. Define Directional Derivative: Let $\mathbf{u}$ be an arbitrary unit vector pointing in direction $\alpha$: $\mathbf{u}=\left[\begin{array}{c}\cos \alpha \\ \sin \alpha \end{array}\right],\Vert \mathbf{u}\Vert =\sqrt{{\cos }^2\alpha +{\sin }^2\alpha }=1$ The directional derivative of $f$ in the direction of $\mathbf{u}$ is: $D_{\mathbf{u}}f=\nabla f\cdot \mathbf{u}$
3. Apply Vector Dot Product Properties: $D_{\mathbf{u}}f=\Vert \nabla f\Vert \Vert \mathbf{u}\Vert \cos \theta =\Vert \nabla f\Vert \cos \theta$ Where $\theta$ is the angle between the gradient vector $\nabla f$ and the unit direction vector $\mathbf{u}$.
4. Maximize the Function: Because $\Vert \nabla f\Vert$ is fixed at any given coordinate: ${\max }_{\mathbf{u}}(D_{\mathbf{u}}f)⟺{\max }_{\theta }(\cos \theta )$ The cosine function reaches its maximum when: $\cos \theta =1⟹\theta =0^{\circ }$
5. Conclusion: $\theta =0^{\circ }$ means $\mathbf{u}$ is collinear with and points in the exact direction of $\nabla f$: ${\mathbf{u}}_{\max }=\frac{\nabla f}{\Vert \nabla f\Vert }$ The maximum rate of increase equals the gradient magnitude: $(D_{\mathbf{u}}f{)}_{\max }=\Vert \nabla f\Vert =\sqrt{f_x^2+f_y^2}■$

---

2. Standard 2-D Gradient Kernels

Roberts Cross Operators ($2\times 2$)

Diagonal differences:

$G_x=\left[\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right],G_y=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$

Prewitt Operators ($3\times 3$)

Separable edge detectors with a box averaging profile along the orthogonal axis:

$G_x=\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right],G_y=\left[\begin{array}{ccc}-1& -1& -1\\ 0& 0& 0\\ 1& 1& 1\end{array}\right]$

Sobel Operators ($3\times 3$)

Separable edge detectors with a Gaussian $[1,2,1]$ smoothing profile along the orthogonal axis to better suppress noise:

$G_x=\left[\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\right],G_y=\left[\begin{array}{ccc}-1& -2& -1\\ 0& 0& 0\\ 1& 2& 1\end{array}\right]$

---

Exercise 13: Prewitt Operators on a Step Edge Image

Input Image

A $7\times 7$ binary step image:

$$f=\left[\begin{array}{ccccccc}0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 1& 1\end{array}\right]$$

Kernels

$G_x=\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right](\text{Vertical Edges}),G_y=\left[\begin{array}{ccc}-1& -1& -1\\ 0& 0& 0\\ 1& 1& 1\end{array}\right](\text{Horizontal Edges})$

$\text{Gradient Magnitude }|\nabla f|=\sqrt{G_x^2+G_y^2}(\text{or }|G_x|+|G_y|)$

---

Step-by-Step Calculations for Representative Pixels

1. Uniform Regions:
   • Any pixel surrounded entirely by $0$s or entirely by $1$s yields $G_x=0$ and $G_y=0$, so $|\nabla f|=0$.
2. Pure Vertical Boundary (e.g., Pixel $(5,4)$ where column transitions from $0$ to $1$):
   • Neighborhood $3\times 3$: $\left[\begin{array}{ccc}0& 1& 1\\ 0& 1& 1\\ 0& 1& 1\end{array}\right]$
   • $G_x=(-1)(0)+0(1)+1(1)+(-1)(0)+0(1)+1(1)+(-1)(0)+0(1)+1(1)=1+1+1=+3$
   • $G_y=(-1)(0)+(-1)(1)+(-1)(1)+0+1(0)+1(1)+1(1)=-2+2=0$
   • Magnitude: $|\nabla f|=\sqrt{3^2+0^2}=3$
3. Pure Horizontal Boundary (e.g., Pixel $(4,6)$ where row transitions from $0$ to $1$):
   • Neighborhood $3\times 3$: $\left[\begin{array}{ccc}0& 0& 0\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]$
   • $G_x=0$ (columns are symmetric left-to-right)
   • $G_y=(-1)(0+0+0)+0(1+1+1)+1(1+1+1)=+3$
   • Magnitude: $|\nabla f|=\sqrt{0^2+3^2}=3$
4. Corner Junction Pixel $(4,4)$:
   • Neighborhood $3\times 3$: $\left[\begin{array}{ccc}0& 0& 0\\ 0& 1& 1\\ 0& 1& 1\end{array}\right]$
   • $G_x=(-1)(0+0+0)+0(0+1+1)+1(0+1+1)=+2$
   • $G_y=(-1)(0+0+0)+0(0+1+1)+1(0+1+1)=+2$
   • Magnitude: $|\nabla f|=\sqrt{2^2+2^2}=\sqrt{8}\approx 2.83$ (or $|2|+|2|=4$)

Resulting Gradient Magnitude Matrix $|\nabla f|$

$$\left[\begin{array}{ccccccc}0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1.41& 3& 3& 3\\ 0& 0& 1.41& 2.83& 3& 3& 3\\ 0& 0& 3& 3& 0& 0& 0\\ 0& 0& 3& 3& 0& 0& 0\\ 0& 0& 3& 3& 0& 0& 0\end{array}\right]$$

---

Module 5: Second Derivatives (Laplacian) & Sharpening

1. The Laplacian Operator

The Laplacian is the isotropic, rotationally invariant 2nd-order differential operator:

${\nabla }^{2}f=\frac{{\partial }^{2}f}{\partial x^2}+\frac{{\partial }^{2}f}{\partial y^2}$

Finite difference expansions: $\frac{{\partial }^{2}f}{\partial x^2}\approx f(x+1,y)-2f(x,y)+f(x-1,y)$ $\frac{{\partial }^{2}f}{\partial y^2}\approx f(x,y+1)-2f(x,y)+f(x,y-1)$

${\nabla }^{2}f\approx [f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)]-4f(x,y)$

4-Neighbor Laplacian:                  8-Neighbor Laplacian:
    [  0   1   0 ]                         [  1   1   1 ]
    [  1  -4   1 ]                         [  1  -8   1 ]
    [  0   1   0 ]                         [  1   1   1 ]

Essential Properties

1. Zero-Sum: Coefficients sum to zero ($\sum w=0$). Output in uniform intensity areas is strictly zero.
2. Zero-Crossing Edge Localization: A zero-crossing in the Laplacian response marks the inflection point where the first derivative (gradient) reaches its maximum.
3. Noise Sensitivity: Second derivatives heavily amplify high-frequency noise. In practice, images are pre-smoothed with a Gaussian filter, forming the Laplacian of Gaussian (LoG) operator:

$\text{LoG}(x,y)={\nabla }^2[G_{\sigma }(x,y)\ast f(x,y)]$

---

Exercise 14: Laplacian Operator on a Step Edge

1. Apply the 8-Neighbor Laplacian

$W_{\text{Laplace}}=\left[\begin{array}{ccc}1& 1& 1\\ 1& -8& 1\\ 1& 1& 1\end{array}\right]$

Applying this mask to the binary step image from Exercise 13:

Step Image f:
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   1   1   1   1
0   0   0   1   1   1   1
0   0   0   1   1   1   1
0   0   0   1   1   1   1

• Uniform regions ($0$s or $1$s): $\sum w_i=0⟹{\nabla }^{2}f=0$.
• Just outside the horizontal boundary (e.g., Pixel $(3,5)=0$):
  • Neighborhood has three $1$s in the bottom row: ${\nabla }^{2}f=1(1+1+1)-8(0)=+3$
• Just inside the horizontal boundary (e.g., Pixel $(4,5)=1$):
  • Neighborhood has five $1$s (itself and four neighbors) and three $0$s: ${\nabla }^{2}f=1(1+1+1+1+1)-8(1)=5-8=-3$
• At the outer corner pixel $(3,3)=0$:
  • Only pixel $(4,4)$ has a value of $1$: ${\nabla }^{2}f=1(1)-8(0)=+1$
• At the inner corner pixel $(4,4)=1$:
  • Three neighbors have value $1$: $(4,5),(5,4),(5,5)$.
  • ${\nabla }^{2}f=1(1+1+1)-8(1)=3-8=-5$

Output Matrix ${\nabla }^{2}f$

$$\left[\begin{array}{ccccccc}0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 3& 3& 3& 3\\ 0& 0& 3& -5& -3& -3& -3\\ 0& 0& 3& -3& 0& 0& 0\\ 0& 0& 3& -3& 0& 0& 0\\ 0& 0& 3& -3& 0& 0& 0\end{array}\right]$$

---

2. How to Sharpen the Detected Borders

Sharpening restores high-frequency edge details by subtracting the negative-center Laplacian:

$f_{\text{sharpened}}(x,y)=f(x,y)-c\cdot {\nabla }^{2}f(x,y)$

(Use addition if the center coefficient is positive).

Verification at Edge Pixels (using $c=1$):

• Outer Edge Pixel $(3,5)$: $f_{\text{orig}}=0,{\nabla }^{2}f=+3⟹f_{\text{sharp}}=0-(+3)=-3\to \text{clipped to }0$ (Dark side is pushed darker, creating an undershoot).
• Inner Edge Pixel $(4,5)$: $f_{\text{orig}}=1,{\nabla }^{2}f=-3⟹f_{\text{sharp}}=1-(-3)=1+3=4$ (Bright side is boosted higher, creating an overshoot).

This introduces Mach-band overshoot and undershoot along the edge, increasing perceived sharpness.

---

2. Unsharp Masking & Highboost Filtering

Unsharp masking sharpens images using a low-pass filter:

[Original Image] -----> [Low-Pass Filter] -----> [Blurred Image]
       |                                                |
       +------------------- (-) <-----------------------+
                            |
                     [High-Pass Mask]
                            |
                   (x k) Scaling Factor
                            |
[Original Image] -----> (+) +
                         |
                 [Sharpened Image]

Formula

1. Obtain smoothed baseline: $f_{\text{smooth}}(x,y)=\text{LPF}\{f(x,y)\}$
2. Compute the unsharp detail mask: $g_{\text{mask}}(x,y)=f(x,y)-f_{\text{smooth}}(x,y)$
3. Add scaled mask back to original: $f_{\text{enhanced}}(x,y)=f(x,y)+k\cdot g_{\text{mask}}(x,y)$

• $k=1$: Standard Unsharp Masking.
• $k>1$: Highboost Filtering (amplifies high frequencies over low-frequency background).

---

Comprehensive Exam Summary

Filter Name	Type	Weight Constraint	Noise Response	Edge / Boundary Behavior	Computational Complexity
Mean (Box) Filter	Linear LPF	$\sum w_i=1$ (Uniform weights)	Spreads impulse noise into a $k\times k$ block	Blurs edges; causes square artifacts	$\mathcal{O}(k^2)$ or $\mathcal{O}(2k)$ (separable)
Gaussian Filter	Linear LPF	$\sum w_i=1$ (Gaussian bell)	Spreads noise into a smooth Gaussian profile	Blurs edges smoothly; isotropic	$\mathcal{O}(2k)$ (strictly separable)
Bilateral Filter	Non-Linear LPF	$\sum W_{\text{eff}}=1$ ($w_s\cdot w_r$)	Suppresses noise locally within smooth plateaus	Preserves sharp edges; stops averaging across boundaries	$\mathcal{O}(k^2)$ per pixel (non-separable)
Median Filter	Non-Linear LPF	Order statistic	Completely removes salt-and-pepper noise	Preserves step edges; erodes objects smaller than $\frac{k}{2}$	$\mathcal{O}(k^2\log k)$ (sorting overhead)
Mode Filter	Non-Linear LPF	Order statistic	Replaces values with neighborhood mode	Collapses gradients into flat patches (oil-painting)	$\mathcal{O}(k^2)$ (histogram voting)
Prewitt / Sobel	Linear HPF	$\sum w_i=0$	Amplifies high-frequency noise	Computes 1st derivative; produces gradient magnitude peaks	$\mathcal{O}(2k)$ (separable)
Laplacian Filter	Linear HPF	$\sum w_i=0$	Strongly amplifies noise; requires Gaussian preprocessing (LoG)	Computes 2nd derivative; forms zero-crossings at edges	Non-separable ($8$-neighbor)