03

Part 1: Gray-Level (Intensity) Transformations

1. Mathematical Concept & Mapping Function (Slides 2–3)

An intensity transformation is a point-processing operation mapping an input intensity $r$ to an output intensity $s$ via a transformation function $T$: $s=T(r)$

• For an 8-bit image, $r,s\in [0,255]$ (or normalized to $[0,1]$).
• Thresholding Function (Slide 2): $s=T(r)=\{\begin{array}{ll}0& \text{if }r<m(\text{Dark})\\ L-1& \text{if }r\ge m(\text{Light})\end{array}$ where $m$ is the threshold value. A smooth, continuous sigmoidal curve can also be used to smoothly expand contrast around $m$ without harsh binary clipping.

2. Negative Transformation (Slides 4–5)

$s=T(r)=(L-1)-r$ For an 8-bit image ($L=256$): $s=255-r$

   Input (r)    Output (s = 255 - r)
      0 (Black)  ------> 255 (White)
    128          ------> 127
    255 (White)  ------>   0 (Black)

Purpose & Example

• Medical Imaging (Slide 4): In digital mammograms or chest X-rays, subtle lesions and microcalcifications surrounded by large dark areas are difficult for the human eye to discern. Inverting the image to a bright background with dark anomalies leverages human visual sensitivity to dark features on light backgrounds.
• Histogram Effect (Slide 5): The histogram is mirrored horizontally: a distribution skewed toward the dark end ($0\le r\le 50$) flips entirely to the bright end ($205\le s\le 255$).

---

3. Logarithmic Transformation (Slides 6–7)

$s=T(r)=c\cdot \log (1+r)$

Why the Log Transformation is Used

1. Dynamic Range Compression: It maps a narrow range of dark input levels into a wider range of output levels, while compressing high input values.
2. Fourier Spectrum Display (Slides 6–7): The 2D Discrete Fourier Transform (DFT) of an image has a central 0-frequency DC peak that can reach values of $10^6$ to $10^7$, while high-frequency details may have values of order $10^0$ to $10^1$. Displaying $|F(u,v)|$ linearly yields a single white pixel at the center surrounded by total blackness. Applying $s=c\log (1+|F(u,v)|)$ compresses this huge dynamic range into visible bands, rendering the surrounding diffraction patterns visible.

---

4. Power-Law (Gamma) Transformation & Gamma Correction (Slides 8–11)

$s=c\cdot r^{\gamma }$

   Curve Behavior:
   • γ < 1 (nth root):   Curves upward. Expands dark values (brightens dark images).
   • γ = 1:              Identity line (s = c · r).
   • γ > 1 (nth power):  Curves downward. Compresses dark values (darkens bright images).

Physical Display Gamma Correction (Slides 10–11)

Cathode Ray Tubes (CRTs) and modern monitor controllers exhibit a physical power-law response between input voltage $V$ and emitted luminance $L_{\text{out}}$: $L_{\text{out}}\propto V^{{\gamma }_{\text{display}}}(\text{where typically }{\gamma }_{\text{display}}\approx 2.2\text{ to }2.5)$

If an uncorrected image is displayed, the monitor will darken all mid-tones and shadow details. To cancel this distortion, image acquisition systems apply a gamma correction: $s=r^{1/{\gamma }_{\text{display}}}=r^{1/2.2}\approx r^{0.45}$ When displayed, the combined system transfer function becomes linear: $\text{Output}=(r^{1/\gamma }{)}^{\gamma }=r^1=r$

---

5. Walkthrough of Exercise 1 (Slides 12–15)

Question 1: Explain why we need to add 1 in the log function as $\log (r+1)$.

• Mathematical Reason: For digital images, minimum intensity is $r=0$ (black). Since $\log (0)=-\infty$, evaluating $\log (r)$ at 0 is undefined and causes a mathematical singularity.
• Adding 1 shifts the input: when $r=0$, $\log (0+1)=\log (1)=0$. This ensures the output passes through the origin $(0,0)$, mapping pure black to pure black.

---

Question 2: Determine coefficient $c$ in the log transformation for 8-bit images ($0\le r,s\le 255$).

We require that maximum input $r_{\max }=255$ maps to maximum output $s_{\max }=255$: $s_{\max }=c\cdot \log (1+r_{\max })$ $255=c\cdot \log (1+255)=c\cdot \log (256)$ $c=\frac{255}{\log (256)}$

---

Question 3: Determine coefficient $c$ in the power-law transformation for 8-bit images.

Equation: $s=c\cdot r^{\gamma }$. We require that $r=255$ yields $s=255$: $255=c\cdot (255{)}^{\gamma }⟹c=\frac{255}{255^{\gamma }}=255^{1-\gamma }$ (Note: If input $r$ is normalized to $[0,1]$, then $1=c\cdot 1^{\gamma }⟹c=1$.)

---

Question 4: Compare natural logarithm ($\ln ={\log }_e$) with base-10 logarithm (${\log }_{10}$). Is there any difference in the resulting images?

• Mathematical Derivation (Slide 14): Using the change-of-base formula ${\log }_b(x)=\frac{{\log }_a(x)}{{\log }_a(b)}$: $s_{\text{base }e}=\left(\frac{255}{\ln 256}\right)\ln (1+r)=\left(\frac{255}{\frac{{\log }_{10}256}{{\log }_{10}e}}\right)\cdot \left(\frac{{\log }_{10}(1+r)}{{\log }_{10}e}\right)=\frac{255}{{\log }_{10}256}{\log }_{10}(1+r)=s_{\text{base }10}$
• Conclusion: There is no difference whatsoever. The change-of-base factor cancels out entirely in the scaling coefficient $c$.

---

Question 5: Small $4\times 4$ image with 3-bit gray levels ($0\le r\le 7$).

Histogram: $h=[1,4,4,3,2,1,1,0]$ for $r=0,1,2,3,4,5,6,7$. Total pixels $n=1+4+4+3+2+1+1+0=16$.

Step 1: Find the scaling coefficient $c$

For 3-bit: $r_{\max }=7$, $s_{\max }=7$. $s=c\cdot \log (1+r)⟹7=c\cdot \log (1+7)=c\cdot \log (8)$ $c=\frac{7}{\log (8)}$ Thus, the transformation formula is: $s=\text{round}\left(\frac{7}{\log (8)}\cdot \log (1+r)\right)$

Step 2: Compute mapped intensity values $s$ for each $r$

(Using base-2 for clarity since $8=2^3$, so ${\log }_2(8)=3$ and $c=7/3\approx 2.333$):

• $r=0⟹s=\frac{7}{3}{\log }_2(1)=0\to 0$
• $r=1⟹s=\frac{7}{3}{\log }_2(2)=\frac{7}{3}\approx 2.33\to 2$
• $r=2⟹s=\frac{7}{3}{\log }_2(3)\approx \frac{7}{3}(1.585)\approx 3.70\to 4$
• $r=3⟹s=\frac{7}{3}{\log }_2(4)=\frac{7}{3}(2)=\frac{14}{3}\approx 4.67\to 5$
• $r=4⟹s=\frac{7}{3}{\log }_2(5)\approx \frac{7}{3}(2.322)\approx 5.42\to 5$
• $r=5⟹s=\frac{7}{3}{\log }_2(6)\approx \frac{7}{3}(2.585)\approx 6.03\to 6$
• $r=6⟹s=\frac{7}{3}{\log }_2(7)\approx \frac{7}{3}(2.807)\approx 6.55\to 7$
• $r=7⟹s=\frac{7}{3}{\log }_2(8)=\frac{7}{3}(3)=7.00\to 7$

Step 3: Accumulate pixel counts into the new histogram

Output Level $s$	Mapped from Input $r$	Pixel Count Calculation	Final Count in New Histogram
0	$r=0$	$h(0)=1$	1
1	None	0	0
2	$r=1$	$h(1)=4$	4
3	None	0	0
4	$r=2$	$h(2)=4$	4
5	$r=3,r=4$	$h(3)+h(4)=3+2$	5
6	$r=5$	$h(5)=1$	1
7	$r=6,r=7$	$h(6)+h(7)=1+0$	1

$\text{New Histogram}=[1,0,4,0,4,5,1,1]$

• Effect Observed (Slide 15): The low input levels ($r=1,2$) are stretched apart ($s=2,4$), increasing local dark contrast. Higher input levels ($r=3,4$ and $r=6,7$) are merged/compressed into single output bins ($s=5$ and $s=7$).

---

6. MATLAB imadjust Syntax and Mechanics (Slides 16–18)

output = imadjust(img, [low_in high_in], [low_out high_out], gamma);

All parameters are normalized to the range $[0.0,1.0]$.

• Any input $r\le \text{low\_in}$ is clipped to $\text{low\_out}$.
• Any input $r\ge \text{high\_in}$ is clipped to $\text{high\_out}$.
• Within $[\text{low\_in},\text{high\_in}]$, the mapping follows: $s={\left(\frac{r-\text{low\_in}}{\text{high\_in}-\text{low\_in}}\right)}^{\gamma }\cdot (\text{high\_out}-\text{low\_out})+\text{low\_out}$

---

Walkthrough of Exercise 2 (Slides 17–18)

Question 1: An 8-bit image has intensities varying from 50 to 200 and appears too bright. Set parameters $p_1$ to $p_5$ to improve quality:

output = imadjust(img, [p1 p2], [p3 p4], p5);

• Input Range $[p_1,p_2]$: We stretch the active data window $[50,200]$ to the full display range: $p_1=\frac{50}{255}\approx 0.196,p_2=\frac{200}{255}\approx 0.784$
• Output Range $[p_3,p_4]$: Expand to the full black-to-white dynamic range $[0,1]$: $p_3=0,p_4=1$
• Gamma parameter $p_5$: The image is too bright, so we must darken it. A darkening power-law curve requires: $p_5=\gamma >1(\text{e.g., }\gamma =1.5\text{ or }2.0)$

---

Question 2: Find output $s$ for input $r=120$ when $p_1=0.1$, $p_2=0.8$, $p_3=0$, $p_4=1$, and $p_5=1$.

Since $p_5=\gamma =1$, the function is a straight line between $(p_1,p_3)=(0.1,0)$ and $(p_2,p_4)=(0.8,1)$.

1. Normalize input $r=120$ to $[0,1]$: $r_{\text{norm}}=\frac{120}{255}$
2. Equation of the line: $\text{Slope }m=\frac{p_4-p_3}{p_2-p_1}=\frac{1-0}{0.8-0.1}=\frac{1}{0.7}=\frac{10}{7}$ $s_{\text{norm}}=\frac{1}{0.7}\cdot (r_{\text{norm}}-0.1)=\frac{10}{7}\left(\frac{120}{255}-\frac{1}{10}\right)$
3. Evaluate inside brackets (Slide 18 handwritten steps): $s_{\text{norm}}=\frac{10}{7}\cdot \frac{120}{255}-\frac{1}{7}=\frac{1200-255}{7\times 255}=\frac{945}{7\times 255}$ Dividing $945$ by $7$: $\frac{945}{7}=135$ $s_{\text{norm}}=\frac{135}{255}$
4. Denormalize back to 8-bit integer: $s=s_{\text{norm}}\times 255=135$

---

Part 2: Histogram Equalization (HE)

1. Mathematical Formulation (Slides 19–21)

Given an image with $n$ total pixels and $L$ gray levels ($r_k$ for $k=0,1,\dots ,L-1$):

• Probability of occurrence (PDF): $p(r_k)=\frac{n_k}{n}$
• Cumulative Distribution Function (CDF): $\text{CDF}(r_k)={\sum }_{j=0}^{k}p(r_j)={\sum }_{j=0}^k\frac{n_j}{n}$
• Discrete Mapping Function: $s_k=T(r_k)=\text{round}\left((L-1)\cdot {\sum }_{j=0}^{k}p(r_j)\right)=\text{round}\left(\frac{L-1}{n}{\sum }_{j=0}^k{n}_j\right)$

---

2. Walkthrough of Exercise 3 (Slides 22–23)

• Image Specifications: Size $4\times 4⟹n=16$ pixels.
• Bit-depth: 3-bit $⟹L=2^3=8$ levels ($0$ to $7$). Factor $(L-1)=7$.
• Original Histogram: $h=[0,0,1,2,4,6,3,0]$

Detailed Calculation Table:

Level $k$	Intensity $r_k$	Count $n_k$	Cumulative Count ${\sum }_{j=0}^k{n}_j$	$\text{CDF}=\frac{\sum n_j}{16}$	Exact Mapping: $7\times \frac{\sum n_j}{16}$	Integer Output $s_k$
0	0	0	0	$0/16=0.0$	$0$	0
1	1	0	0	$0/16=0.0$	$0$	0
2	2	1	1	$1/16=0.0625$	$7/16=0.4375$	0
3	3	2	3	$3/16=0.1875$	$21/16=1.3125$	1
4	4	4	7	$7/16=0.4375$	$49/16=3.0625$	3
5	5	6	13	$13/16=0.8125$	$91/16=5.6875$	6
6	6	3	16	$16/16=1.0$	$112/16=7.0$	7
7	7	0	16	$16/16=1.0$	$112/16=7.0$	7

Step (1): Cumulative Histogram Plot (Slide 23)

The cumulative sums plotted against $r\in [0,7]$ are: $[0,0,1,3,7,13,16,16]$

Step (2): New Histogram After Equalization

We place the original pixel counts into their mapped bins $s_k$:

• $s=0$: receives counts from $r=0,1,2⟹0+0+1=1$
• $s=1$: receives counts from $r=3⟹2$
• $s=2$: receives no allocations $⟹0$
• $s=3$: receives counts from $r=4⟹4$
• $s=4$: receives no allocations $⟹0$
• $s=5$: receives no allocations $⟹0$
• $s=6$: receives counts from $r=5⟹6$
• $s=7$: receives counts from $r=6,7⟹3+0=3$

$\text{New Histogram}=[1,2,0,4,0,0,6,3]$

   Original Histogram:              Equalized Histogram:
   6 |           *                  6 |                       *
   5 |           *                  5 |                       *
   4 |         * *                  4 |             *         *
   3 |         * * *                3 |             *         * *
   2 |       * * * *                2 |   *         *         * *
   1 |     * * * * *                1 | * *         *         * *
     +----------------                +--------------------------
       0 1 2 3 4 5 6 7                  0 1 2 3 4 5 6 7
       (Narrowly clustered: 2 to 6)     (Spread across full dynamic range: 0 to 7)

---

Part 3: Image Contrast Metrics & Statistical Measures

1. Root-Mean-Square (RMS) Contrast (Slides 26–27)

RMS contrast is the standard deviation of pixel intensities: $\text{RMS Contrast}={\sigma }_x=\sqrt{\frac{1}{MN}{\sum }_{r=1}^M{\sum }_{c=1}^N(I_{rc}-\bar{I}{)}^2}$ Where the mean intensity is $\bar{I}=\frac{1}{MN}{\sum }_{r=1}^M{\sum }_{c=1}^N{I}_{rc}$.

Two Equivalent Computational Formulas (Slide 27):

• Formula 1 (Direct Definition): ${\sigma }_x^2=\frac{1}{n}{\sum }_{i=1}^n(x_i-\bar{x}{)}^2$
• Formula 2 (Computational Shortcut via Expected Values): ${\sum }_{i=1}^n(x_i-\bar{x}{)}^2={\sum }_{i=1}^n(x_i^2-2\bar{x}{x}_i+{\bar{x}}^2)=\sum x_i^2-2\bar{x}\sum x_i+n{\bar{x}}^2$ Substituting $\bar{x}=\frac{\sum x_i}{n}$: $=\sum x_i^2-2\frac{(\sum x_i{)}^2}{n}+\frac{(\sum x_i{)}^2}{n}=\sum x_i^2-\frac{(\sum x_i{)}^2}{n}$ Dividing through by $n$: ${\sigma }_x^2=\frac{\sum x_i^2}{n}-{\left(\frac{\sum x_i}{n}\right)}^2$ ${\sigma }_x=\sqrt{\frac{\sum x_i^2}{n}-{\bar{x}}^2}$

---

2. Walkthrough of Review Quiz 1 (Slide 30)

Problem: Find the RMS contrast of the $2\times 2$ image: $I=\left[\begin{array}{cc}10& 20\\ 30& 40\end{array}\right],n=4\text{ pixels},x=[10,20,30,40]$

Solution Method 1:

1. Mean ($\bar{x}$): $\bar{x}=\frac{10+20+30+40}{4}=\frac{100}{4}=25$
2. Deviations squared: $(10-25{)}^2=(-15{)}^2=225$ $(20-25{)}^2=(-5{)}^2=25$ $(30-25{)}^2=(5{)}^2=25$ $(40-25{)}^2=(15{)}^2=225$
3. Variance (${\sigma }_x^2$): ${\sigma }_x^2=\frac{225+25+25+225}{4}=\frac{500}{4}=125$
4. RMS Contrast: ${\sigma }_x=\sqrt{125}=5\sqrt{5}\approx 11.18$

Solution Method 2:

1. Sum of squares: $\sum x_i^2=10^2+20^2+30^2+40^2=100+400+900+1600=3000$
2. Average of squares: $\frac{\sum x_i^2}{n}=\frac{3000}{4}=750$
3. Square of the mean: ${\bar{x}}^2={\left(\frac{100}{4}\right)}^2=25^2=625$
4. Variance & RMS Contrast: ${\sigma }_x^2=750-625=125⟹{\sigma }_x=\sqrt{125}\approx 11.18$

---

3. Walkthrough of Review Quiz 2 (Slide 31)

Problem: Given the pixel array $x=[2,2,3,6,7]$, find ${\sigma }_x^2$ and interpret the statistics.

Part A: Numerical Variance

1. Mean ($\bar{x}$): $\bar{x}=\frac{2+2+3+6+7}{5}=\frac{20}{5}=4$
2. Using Method 1: ${\sigma }_x^2=\frac{(2-4{)}^2+(2-4{)}^2+(3-4{)}^2+(6-4{)}^2+(7-4{)}^2}{5}=\frac{4+4+1+4+9}{5}=\frac{22}{5}=4.4$
3. Using Method 2: $\sum x_i^2=4+4+9+36+49=102$ ${\sigma }_x^2=\frac{102}{5}-4^2=20.4-16=4.4$

Part B: Physical & Statistical Interpretations (Slide 31)

• Arithmetic Mean ($\text{AM}=4$): Represents the Center of Gravity (Balance Point) of the histogram: $\text{Left torque: }2\text{ kg}\times 2\text{ m}+1\text{ kg}\times 1\text{ m}=5\text{ kg}\cdot \text{m}$ $\text{Right torque: }1\text{ kg}\times 2\text{ m}+1\text{ kg}\times 3\text{ m}=5\text{ kg}\cdot \text{m}(\text{Balanced!})$
• Median ($=3$): Represents the Histogram Splitter (divides the cumulative area under the histogram exactly in half: $50\%$ to the left, $50\%$ to the right).
• Mode ($=2$): Represents the Highest Peak (the most frequently occurring intensity level).

---

4. Michelson Contrast vs. RMS Contrast (Slide 28–29)

Michelson Contrast Formula:

$C_{\text{Michelson}}=\frac{I_{\max }-I_{\min }}{I_{\max }+I_{\min }}$

Detailed Comparison on the Slide 28–29 Distributions:

• $\text{Hist 1}=[0,0,1,2,4,6,3,0]$ (Before Equalization):
  • Active range: $I_{\min }=2,I_{\max }=6$.
  • $\bar{x}=\frac{2(1)+3(2)+4(4)+5(6)+6(3)}{16}=\frac{72}{16}=4.5$
  • ${\sigma }_1=\sqrt{\frac{344}{16}-{\left(\frac{72}{16}\right)}^2}=\sqrt{21.5-20.25}=\sqrt{1.25}\approx 1.118$
  • $C_{\text{Michelson}}=\frac{6-2}{6+2}=\frac{4}{8}=0.5$
• $\text{Hist 2}=[1,2,0,4,0,0,6,3]$ (After Equalization):
  • Active range: $I_{\min }=0,I_{\max }=7$.
  • $\bar{x}=\frac{0(1)+1(2)+3(4)+6(6)+7(3)}{16}=\frac{71}{16}\approx 4.4375$
  • ${\sigma }_2=\sqrt{\frac{401}{16}-{\left(\frac{71}{16}\right)}^2}=\sqrt{25.0625-19.6914}=\sqrt{5.3711}\approx 2.3176$
  • $C_{\text{Michelson}}=\frac{7-0}{7+0}=\frac{7}{7}=1.0$
• Result: Histogram equalization doubled the Michelson contrast from $0.5$ to $1.0$ and more than doubled the RMS contrast from $1.12$ to $2.32$.

---

Part 4: Image Quality Metrics (RMSE, PSNR)

1. Definitions & Formulas (Slides 32–35)

For a reference image $f(x,y)$ and a degraded image $g(x,y)$ of size $M\times N$: $\text{MSE}=\frac{1}{MN}{\sum }_{x=1}^M{\sum }_{y=1}^N[f(x,y)-g(x,y){]}^2$ $\text{RMSE}=\sqrt{\text{MSE}}$ $\text{PSNR (dB)}=10{\log }_{10}\left(\frac{{\text{MAX}}_I^2}{\text{MSE}}\right)=20{\log }_{10}\left(\frac{{\text{MAX}}_I}{\text{RMSE}}\right)$ For 8-bit images, ${\text{MAX}}_I=255$.

Perceived Quality Rule-of-Thumb Table (Slide 35):

PSNR (dB)	Perceived Visual Quality	Interpretation
$>40\text{ dB}$	Excellent	Differences are virtually imperceptible.
$30-40\text{ dB}$	Good	Slight differences, generally acceptable.
$20-30\text{ dB}$	Fair	Noticeable degradation.
$<20\text{ dB}$	Poor	Severe distortion, unacceptable quality.

Maximum Theoretical PSNR for Smallest Non-Zero Error ($\text{MSE}=1$):

• 8-bit: $20{\log }_{10}(255/1)\approx 48.13\text{ dB}$
• 10-bit: $20{\log }_{10}(1023/1)\approx 60.20\text{ dB}$
• 12-bit: $20{\log }_{10}(4095/1)\approx 72.25\text{ dB}$
• 16-bit: $20{\log }_{10}(65535/1)\approx 96.33\text{ dB}$

---

2. Walkthrough of Review Quiz 3 (Slide 34)

Problem: Compare original image $I_{\text{orig}}$ with test image $I_{\text{test}}$: $I_{\text{orig}}=\left[\begin{array}{cc}10& 20\\ 30& 40\end{array}\right],I_{\text{test}}=\left[\begin{array}{cc}12& 18\\ 32& 38\end{array}\right]$

1. Pixel Differences squared: $(10-12{)}^2=(-2{)}^2=4$ $(20-18{)}^2=(2{)}^2=4$ $(30-32{)}^2=(-2{)}^2=4$ $(40-38{)}^2=(2{)}^2=4$
2. MSE and RMSE: $\text{MSE}=\frac{4+4+4+4}{4}=4$ $\text{RMSE}=\sqrt{4}=2$
3. PSNR Calculation: $\text{PSNR}=20{\log }_{10}\left(\frac{255}{2}\right)=20{\log }_{10}(127.5)=20\times 2.1055\approx 42.11\text{ dB}$ _(Using MSE formulation yields the same result: $10{\log }_{10}\left(\frac{255^2}{4}\right)=10\log \ast 10(16256.25)\approx 42.11\text{ dB}$).*

---

3. Walkthrough of Exercise 4 (Slides 36–37)

Setup: Reference image $A$ is $3\times 3$ with background $50$ and center pixel $200$: $A=\left[\begin{array}{ccc}50& 50& 50\\ 50& 200& 50\\ 50& 50& 50\end{array}\right]$ Compare against Noisy Image $B$: $B=\left[\begin{array}{ccc}52& 53& 48\\ 54& 201& 51\\ 49& 47& 53\end{array}\right]$

1. Compute squared differences matrix $(A-B{)}^2$: $(50-52{)}^2=4,(50-53{)}^2=9,(50-48{)}^2=4$ $(50-54{)}^2=16,(200-201{)}^2=1,(50-51{)}^2=1$ $(50-49{)}^2=1,(50-47{)}^2=9,(50-53{)}^2=9$
2. Row sums (Slide 37 handwritten notes):
   • Row 1: $4+9+4=17$
   • Row 2: $16+1+1=18$
   • Row 3: $1+9+9=19$
   • Total sum: $17+18+19=54$
3. MSE and RMSE: $\text{MSE}=\frac{54}{9}=6$ $\text{RMSE}=\sqrt{6}\approx 2.4495$
4. PSNR: $\text{PSNR}=20{\log }_{10}\left(\frac{255}{\sqrt{6}}\right)=20{\log }_{10}\left(\frac{255}{2.4495}\right)=20{\log }_{10}(104.103)=20\times 2.0175\approx 40.35\text{ dB}$

---

Part 5: Pattern Matching & Distance Metrics

                    PATTERN MATCHING METRICS
      --------------------------------------------------
      |                        |                       |
   L1 Norm                  L2 Norm            Correlation / Angle
  SAD (Manhattan)        SSD (Euclidean)         ZNCC (Cosine Sim)
      |                        |                       |
   Zero-Mean:               Zero-Mean:            Inherently
  ZSAD (b-invariant)       ZSSD (b-invariant)    Affine-Invariant (a, b)

1. SAD and SSD (Slides 39–43)

Let $I_1(k,l)$ be a template of size $m\times n$, and $I_2(i+k,j+l)$ be the candidate patch in the target image.

Sum of Absolute Differences (SAD) — $L_1$ Norm / Manhattan Distance:

$\text{SAD}(i,j)={\sum }_{k=0}^{m-1}{\sum }_{l=0}^{n-1}|I_1(k,l)-I_2(i+k,j+l)|$

Sum of Squared Differences (SSD) — Squared $L_2$ Norm / Euclidean Distance:

$\text{SSD}(i,j)={\sum }_{k=0}^{m-1}{\sum }_{l=0}^{n-1}[I_1(k,l)-I_2(i+k,j+l){]}^2=mn\times \text{MSE}$

Geometric Interpretation of $L_1$ vs $L_2$ Equidistance Contours (Slide 42):

• $L_1$ distance form: $|x|+|y|=d⟹$ produces a rotated square (diamond) contour.
• $L_2$ distance form: $\sqrt{x^2+y^2}=d⟹$ produces a perfect circle.

---

2. Illumination Limitations & Zero-Mean Extensions (Slides 43, 51)

Under an affine illumination change where all pixel intensities shift by gain $a$ and offset $b$: $I^{\prime }(x,y)=a\cdot I(x,y)+b$

• Standard SAD and SSD fail completely because additive bias $b$ is accumulated across all pixels, causing large errors even for structurally identical patterns.

Zero-Mean Extensions (ZSAD & ZSSD):

By subtracting the patch mean before taking differences: $\text{ZSAD}(i,j)={\sum }_{k=0}^{m-1}{\sum }_{l=0}^{n-1}|[I_1(k,l)-{\bar{I}}_1]-[I_2(i+k,j+l)-{\bar{I}}_2]|$ $\text{ZSSD}(i,j)={\sum }_{k=0}^{m-1}{\sum }_{l=0}^{n-1}([I_1(k,l)-{\bar{I}}_1]-[I_2(i+k,j+l)-{\bar{I}}_2]{)}^2$

• Advantage: Both ZSAD and ZSSD are invariant to additive lighting shifts ($I^{\prime }=I+b$).
• Limitation: They remain sensitive to multiplicative/contrast scale changes ($a\ne 1$).

---

Part 6: Zero-Mean Normalized Cross-Correlation (ZNCC)

1. Statistical & Vector Formulations (Slides 45–47)

Statistical Formula:

$r_{\text{ZNCC}}=\frac{{\sigma }_{xy}}{{\sigma }_x{\sigma }_y}=\frac{{\sum }_{k=1}^n(x_k-\bar{x})(y_k-\bar{y})}{\sqrt{{\sum }_{k=1}^n(x_k-\bar{x}{)}^2}\sqrt{{\sum }_{k=1}^n(y_k-\bar{y}{)}^2}}$

Vector Geometry (Exercise 5, Slide 46):

Define centered difference vectors $\mathbf{u}$ and $\mathbf{v}\in {\mathbb{R}}^n$: $\mathbf{u}=\left[\begin{array}{c}{x}_1-\bar{x}\\ x_2-\bar{x}\\ ⋮\\ x_n-\bar{x}\end{array}\right],\mathbf{v}=\left[\begin{array}{c}{y}_1-\bar{y}\\ y_2-\bar{y}\\ ⋮\\ y_n-\bar{y}\end{array}\right]$ Then: $r=\frac{\mathbf{u}\cdot \mathbf{v}}{\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert }=\cos \theta$ Where:

• $\mathbf{u}\cdot \mathbf{v}={\sum }_{k=1}^n(x_k-\bar{x})(y_k-\bar{y})$
• $\Vert \mathbf{u}\Vert =\sqrt{{\sum }_{k=1}^n(x_k-\bar{x}{)}^2}$
• $\Vert \mathbf{v}\Vert =\sqrt{{\sum }_{k=1}^n(y_k-\bar{y}{)}^2}$
• $\theta$ is the angle between the two vectors in $n$-dimensional space.

Key Mathematical Bounds:

$-1\le \text{ZNCC}\le +1$

• $\text{ZNCC}=+1⟺\theta =0^{\circ }$ (Perfect positive correlation; identical pattern shape up to positive affine scaling).
• $\text{ZNCC}=0⟺\theta =90^{\circ }$ (Orthogonal; zero linear relationship).
• $\text{ZNCC}=-1⟺\theta =180^{\circ }$ (Perfect inverse correlation; photographic negative).

---

2. Walkthrough of Exercise 6 (Slides 48–50)

Given: $3\times 3$ template $g$: $g=\left[\begin{array}{ccc}90& 90& 90\\ 90& 0& 90\\ 90& 90& 90\end{array}\right]$ Total pixels $n=9$.

• Mean of $g$: $\bar{g}=\frac{8\times 90+1\times 0}{9}=\frac{720}{9}=80$
• Centered Vector $\mathbf{u}=g-\bar{g}$:
  • For the 8 outer pixels: $90-80=+10$
  • For the 1 center pixel: $0-80=-80$ $\mathbf{u}=[10,10,10,10,-80,10,10,10,10{]}^T$
• Norm of $\mathbf{u}$ (Slide 49): $\Vert \mathbf{u}\Vert =\sqrt{8\times (10^2)+(-80{)}^2}=\sqrt{800+6400}=\sqrt{7200}=\sqrt{3600\times 2}=60\sqrt{2}$

---

Test Image 3: $f_3=2g+60$ (Both Multiplicative & Additive Changes)

$f_3=\left[\begin{array}{ccc}240& 240& 240\\ 240& 60& 240\\ 240& 240& 240\end{array}\right]$

1. Mean of $f_3$: ${\bar{f}}_3=\frac{8\times 240+60}{9}=\frac{1920+60}{9}=\frac{1980}{9}=220$
2. Centered Vector $\mathbf{v}=f_3-{\bar{f}}_3$:
   • Outer pixels: $240-220=+20$
   • Center pixel: $60-220=-160$ $\mathbf{v}=[20,20,20,20,-160,20,20,20,20{]}^T$ (Notice: $\mathbf{v}=2\mathbf{u}$!)
3. Norm of $\mathbf{v}$ (Slide 49): $\Vert \mathbf{v}\Vert =\sqrt{8\times (20^2)+(-160{)}^2}=\sqrt{3200+25600}=\sqrt{28800}=\sqrt{14400\times 2}=120\sqrt{2}$
4. Dot Product $\mathbf{u}\cdot \mathbf{v}$: $\mathbf{u}\cdot \mathbf{v}=8\times (10\times 20)+(-80\times -160)=8\times 200+12800=1600+12800=14400$
5. Compute ZNCC: $\text{ZNCC}=\frac{\mathbf{u}\cdot \mathbf{v}}{\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert }=\frac{14400}{(60\sqrt{2})\times (120\sqrt{2})}=\frac{14400}{7200\times 2}=\frac{14400}{14400}=1.0$ $\cos \theta =1⟹\theta =0^{\circ }$

• Key Takeaway: ZNCC is fully invariant to linear changes in illumination ($I^{\prime }=aI+b$ with $a>0$).

---

Behavior on Other Test Images from Exercise 6 (Slides 48, 50):

• $f_1=g+60$ (Additive shift): $\mathbf{v}=\mathbf{u}⟹\text{ZNCC}=+1.0,\theta =0^{\circ }$.
• $f_2=2g$ (Multiplicative scaling): $\mathbf{v}=2\mathbf{u}⟹\text{ZNCC}=+1.0,\theta =0^{\circ }$.
• $f_7=255-g$ (Negative/Inverted image): Here $a=-1<0$. The vector flips orientation: $\mathbf{v}=-\mathbf{u}$. $\text{ZNCC}=\frac{-\Vert \mathbf{u}{\Vert }^2}{\Vert \mathbf{u}{\Vert }^2}=-1.0⟹\theta =180^{\circ }$
• $f_4,f_5,f_6$ (Structural noise - 1, 2, 3 pixels altered): Changing pixel values breaks vector alignment. For example, in $f_5$, two pixels change from $90$ to $0$, rotating vector $\mathbf{v}$ away from $\mathbf{u}$, which lowers the correlation coefficient ($\text{ZNCC}<1$, $\theta >0^{\circ }$).

---

Part 7: Structural Similarity Index (SSIM)

1. The SSIM Formula & Components (Slide 52)

Developed by Wang and Bovik (2004), SSIM matches human visual perception by measuring three separate attributes between images $\mathbf{x}$ and $\mathbf{y}$:

$\text{SSIM}(\mathbf{x},\mathbf{y})=[l(\mathbf{x},\mathbf{y})]\cdot [c(\mathbf{x},\mathbf{y})]\cdot [s(\mathbf{x},\mathbf{y})]$

$\text{SSIM}(\mathbf{x},\mathbf{y})=\left(\frac{2{\mu }_x{\mu }_y+C_1}{{\mu }_x^2+{\mu }_y^2+C_1}\right)\cdot \left(\frac{2{\sigma }_x{\sigma }_y+C_2}{{\sigma }_x^2+{\sigma }_y^2+C_2}\right)\cdot \left(\frac{{\sigma }_{xy}+C_3}{{\sigma }_x{\sigma }_y+C_3}\right)$

• Luminance Comparison $l(\mathbf{x},\mathbf{y})$: Compares mean brightness (${\mu }_x,{\mu }_y$).
• Contrast Comparison $c(\mathbf{x},\mathbf{y})$: Compares intensity standard deviations (${\sigma }_x,{\sigma }_y$).
• Structure Comparison $s(\mathbf{x},\mathbf{y})$: Evaluates correlation after removing mean and variance (${\sigma }_{xy}/{\sigma }_x{\sigma }_y$ is the correlation coefficient, matching ZNCC!).
• Stability Constants: $C_1,C_2,C_3>0$ prevent division by zero in near-flat or black regions.

---

2. Derivation of SSIM Terms from AM and GM (Slides 54–55)

The mathematical foundation behind both the luminance and contrast terms comes from the Ratio of Geometric Mean to Arithmetic Mean:

For two positive numbers $X$ and $Y$:

• Arithmetic Mean: $\text{AM}=\frac{X+Y}{2}$
• Geometric Mean: $\text{GM}=\sqrt{XY}$

AM–GM Inequality Proof:

$(\sqrt{X}-\sqrt{Y}{)}^2\ge 0$ $X-2\sqrt{XY}+Y\ge 0⟹\frac{X+Y}{2}\ge \sqrt{XY}⟹\text{AM}\ge \text{GM}$ Therefore: $\frac{\text{GM}}{\text{AM}}=\frac{\sqrt{XY}}{\frac{X+Y}{2}}=\frac{2\sqrt{XY}}{X+Y}\le 1$

• $\frac{\text{GM}}{\text{AM}}=1$ if and only if $X=Y$.

Deriving the SSIM Terms (Slide 55):

• Let $X={\mu }_x^2$ and $Y={\mu }_y^2$: $\frac{\text{GM}}{\text{AM}}=\frac{2\sqrt{{\mu }_x^2{\mu }_y^2}}{{\mu }_x^2+{\mu }_y^2}=\frac{2{\mu }_{\mathbf{x}}{\mu }_{\mathbf{y}}}{{\mu }_{\mathbf{x}}^2+{\mu }_{\mathbf{y}}^2}\text{(Luminance Term!)}$
• Let $X={\sigma }_x^2$ and $Y={\sigma }_y^2$: $\frac{\text{GM}}{\text{AM}}=\frac{2\sqrt{{\sigma }_x^2{\sigma }_y^2}}{{\sigma }_x^2+{\sigma }_y^2}=\frac{2{\sigma }_{\mathbf{x}}{\sigma }_{\mathbf{y}}}{{\sigma }_{\mathbf{x}}^2+{\sigma }_{\mathbf{y}}^2}\text{(Contrast Term!)}$

---

3. Harmonic Mean (HM) and the Full Inequality (Slide 57)

• Harmonic Mean Definition: $\text{HM}=\frac{2}{\frac{1}{x}+\frac{1}{y}}=\frac{2xy}{x+y}$
• Physical Example (Slide 57): Average speed over a round-trip route of distance $l$ out at speed $v_1$ and return at speed $v_2$: $\bar{v}=\frac{\text{Total Distance}}{\text{Total Time}}=\frac{2l}{\frac{l}{v_1}+\frac{l}{v_2}}=\frac{2v_1{v}_2}{v_1+v_2}=\text{Harmonic Mean of }(v_1,v_2)$
• Connection to GM and AM: $\text{HM}=\frac{2xy}{x+y}=\frac{(\sqrt{xy}{)}^2}{\frac{x+y}{2}}=\frac{{\text{GM}}^2}{\text{AM}}=\left(\frac{\text{GM}}{\text{AM}}\right)\cdot \text{GM}$ Because $\frac{\text{GM}}{\text{AM}}\le 1$, it directly follows that: $\text{AM}\ge \text{GM}\ge \text{HM}$

---

4. Walkthrough of Exercise 7 (Slide 56)

Calculate $\text{AM}$, $\text{GM}$, and the ratio $\frac{\text{GM}}{\text{AM}}$ for pairs where $x+y=10$:

$x$	$y$	$\text{AM}=\frac{x+y}{2}$	$\text{GM}=\sqrt{xy}$	Metric: $\frac{\text{GM}}{\text{AM}}$
10	0	$\frac{10+0}{2}=5$	$\sqrt{0}=0$	$0/5=0.00$
9	1	$\frac{9+1}{2}=5$	$\sqrt{9}=3$	$3/5=0.60$
8	2	$\frac{8+2}{2}=5$	$\sqrt{16}=4$	$4/5=0.80$
7	3	$\frac{7+3}{2}=5$	$\sqrt{21}\approx 4.583$	$4.583/5\approx 0.92$
6	4	$\frac{6+4}{2}=5$	$\sqrt{24}\approx 4.899$	$4.899/5\approx 0.98$
5	5	$\frac{5+5}{2}=5$	$\sqrt{25}=5$	$5/5=1.00$ (Maximum)
4	6	$\frac{4+6}{2}=5$	$\sqrt{24}\approx 4.899$	$4.899/5\approx 0.98$
3	7	$\frac{3+7}{2}=5$	$\sqrt{21}\approx 4.583$	$4.583/5\approx 0.92$
2	8	$\frac{2+8}{2}=5$	$\sqrt{16}=4$	$4/5=0.80$
1	9	$\frac{1+9}{2}=5$	$\sqrt{9}=3$	$3/5=0.60$
0	10	$\frac{0+10}{2}=5$	$\sqrt{0}=0$	$0/5=0.00$

• Takeaway: The ratio $\frac{\text{GM}}{\text{AM}}$ is normalized to $[0,1]$. It equals $1$ if and only if $x=y$, and smoothly falls off toward $0$ as the discrepancy between the two values increases.

---

Part 8: Comparison of Matching Metrics & Real-World Challenges

1. Summary Comparison Table (Slide 44 & 51)

Metric	Mathematical Formula	Invariant to $I^{\prime }=I+b$ (Additive)?	Invariant to $I^{\prime }=aI$ (Multiplicative)?	Computational Cost
SAD ($L_1$)	$\sum \Vert I_1-I_2\Vert$	No	No	Very Low (subtractions & additions only)
SSD ($L_2^2$)	$\sum (I_1-I_2{)}^2$	No	No	Low (subtractions & MAC operations)
ZSAD	$\sum \Vert (I_1-{\bar{I}}_1)-(I_2-{\bar{I}}_2)\Vert$	Yes	No	Low
ZSSD	$\sum [(I_1-{\bar{I}}_1)-(I_2-{\bar{I}}_2){]}^2$	Yes	No	Moderate
ZNCC	$\frac{\sum (I_1-{\bar{I}}_1)(I_2-{\bar{I}}_2)}{\sqrt{\sum (I_1-{\bar{I}}_1{)}^2\sum (I_2-{\bar{I}}_2{)}^2}}$	Yes	Yes (for $a>0$)	High (square roots & divisions per candidate window)
SSIM	$l(\mathbf{x},\mathbf{y})\cdot c(\mathbf{x},\mathbf{y})\cdot s(\mathbf{x},\mathbf{y})$	Partial	Partial	High (evaluates local window statistics)

---

2. Seven Core Challenges in Pattern Matching (Slide 58)

1. Changes of Image Intensities: Direct sunlight, shadows, or automatic camera gain alter pixel values (handled by ZNCC or ZSAD).
2. Occlusion Problem: An intervening foreground obstacle covers part of the template, altering squared errors across the patch.
3. Rotations of a Pattern: Standard 2D sliding templates assume axis-aligned patterns. Any rotation breaks row-column alignment.
4. Scale Changes: Distance changes between camera and scene cause the target to appear larger or smaller than the fixed template size.
5. Perspective Distortion: Non-frontal viewing angles introduce homographic/keystone transformations that warp square features into general quadrilaterals.
6. Changes of Focus Levels: Out-of-focus blur removes the high-frequency components that cross-correlation relies upon.
7. The Aperture Problem (Insufficient Gradient Directions): If a local template contains only a straight edge (a 1D gradient), motion or matches perpendicular to the gradient can be detected, but movement along the parallel edge is ambiguous and cannot be localized. Point features (corners with gradients in at least two orthogonal directions) are required for unique pattern matching.