Digital Image Processing

Digital Image Processing (DIP) = Processing of digital images using computer algorithms to improve quality or extract useful information.

A Digital Image = 2D function f(x, y) where:

• (x, y) = spatial coordinates
• f(x, y) = intensity/gray level at that point
• Both coordinates and amplitude are finite and discrete

Objectives:

• Improve image quality for human viewing
• Prepare images for machine analysis
• Extract meaningful features
• Compress images for storage/transmission

Scope of DIP:

Key Outcomes: Students learn to apply spatial/frequency domain filters, compression, and segmentation on digital images.

Steps in DIP (Pipeline):

1. Image Acquisition
      ↓
2. Image Preprocessing
      ↓
3. Image Enhancement
      ↓
4. Image Restoration
      ↓
5. Image Compression
      ↓
6. Image Segmentation
      ↓
7. Representation & Description
      ↓
8. Object Recognition
      ↓
9. Knowledge Base (feeds back to all steps)

Step Details:

• Acquisition: Camera/scanner → raw digital image
• Preprocessing: Noise removal, geometric corrections
• Enhancement: Improve contrast, brightness for viewing
• Restoration: Remove blur/degradation (objective, model-based)
• Compression: Reduce file size (JPEG, PNG)
• Segmentation: Partition image into meaningful regions
• Representation: Chain codes, Fourier descriptors
• Recognition: Classify objects (car, person, tumor)

Key Difference: Enhancement = subjective (looks better), Restoration = objective (remove known degradation)

Digital Image Representation:

An image f(x,y) is a 2D matrix of pixels (picture elements)

f(x,y) = [ f(0,0)  f(0,1)  ... f(0,N-1)  ]
          [ f(1,0)  f(1,1)  ... f(1,N-1)  ]
          [ ...                           ]
          [ f(M-1,0) ...   f(M-1,N-1)    ]

• M×N = image dimensions (rows × columns)
• Each f(x,y) = 0 to 255 for 8-bit grayscale

Sampling (Spatial Discretization):

• Converting continuous x,y coordinates → discrete grid
• Determines spatial resolution (pixels per inch)
• More samples → higher resolution → better detail

Quantization (Amplitude Discretization):

• Converting continuous intensity values → discrete levels
• Gray levels: L = 2^k (k = bits per pixel)
• 8-bit: L = 256 levels (0=black, 255=white)
• 1-bit: L = 2 levels (binary/B&W image)

Image Size Formula:

Storage = M × N × k bits
Example: 512×512 × 8-bit = 2,097,152 bits = 256 KB

Nyquist Theorem: Sampling rate ≥ 2 × highest frequency to avoid aliasing

Color Image Representation:

A color image has 3 planes (channels):

Color Image = [R channel] + [G channel] + [B channel]
Storage = M × N × 3 × 8 bits (for 24-bit color)

RGB Model (Additive):

• Primary colors: Red, Green, Blue
• Used in monitors, cameras
• R(0-255), G(0-255), B(0-255)
• White = (255,255,255), Black = (0,0,0)
• Represented as a unit cube

HSI / HSV Model:

• Better for image processing (separates color from intensity)
• Useful for segmentation by color

YCbCr Model:

• Used in JPEG, video compression
• Y = Luma (brightness), Cb = Blue chrominance, Cr = Red chrominance
• Human eye is more sensitive to Y than Cb/Cr

CMYK Model (Subtractive):

• Used in color printing
• Cyan, Magenta, Yellow, Key(Black)

Pseudo-Coloring: Assigning colors to grayscale values for better visualization

Intensity Transform: s = T(r)

Where r = input intensity, s = output intensity (both in [0, L-1])

1. Image Negative:

s = (L - 1) - r
s = 255 - r  (for 8-bit)

Use: Enhance white detail in dark regions

2. Log Transform:

s = c × log(1 + r)   where c = constant

Use: Compresses high values, expands low values. Useful for Fourier spectrum display.

3. Power-Law (Gamma) Transform:

s = c × r^γ
- γ < 1: Bright image (expand dark areas)
- γ > 1: Dark image (compress dark areas)
- γ = 1: Identity (no change)

Use: Gamma correction for monitor calibration

4. Piecewise Linear Transforms:

• Contrast Stretching: Expand narrow intensity range → full range
• Gray-level Slicing: Highlight specific intensity range
• Bit-plane Slicing: Extract bit-planes (MSB has most info)

5. Thresholding:

s = L-1 if r ≥ T, else s = 0

Converts grayscale → binary image

Image Histogram:

A graph showing the frequency of each intensity level in an image.

h(rk) = nk
where nk = number of pixels with intensity rk

Normalized Histogram (PDF):

p(rk) = nk / (M×N)
M×N = total pixels

Histogram Shapes:

Histogram Equalization:

Automatic contrast enhancement by redistributing intensities.

Formula:

sk = T(rk) = (L-1) × Σ p(rj)  for j=0 to k
           = (L-1) × CDF(rk)

Steps:

• 1. Compute histogram h(rk)
• 2. Compute cumulative sum (CDF)
• 3. Normalize: sk = (L-1) × CDF(rk)
• 4. Round to nearest integer
• 5. Map original pixels to new values

Result: Spread histogram across full range → enhanced contrast

Histogram Specification (Matching): Reshape histogram to match a desired target distribution

Spatial Filtering = Modifying pixel values based on neighborhood pixels using a kernel/mask.

Convolution Operation:

g(x,y) = Σ Σ f(x+s, y+t) × w(s,t)

Where w = filter kernel, f = input image, g = output image

1. Smoothing (Low-pass) Filters:

Box/Mean Filter:

1/9 × [1 1 1]
      [1 1 1]
      [1 1 1]

Averages all neighbors → blurs image, reduces noise

Gaussian Filter:

Weighted average (center pixel gets highest weight)

1/16 × [1 2 1]
        [2 4 2]
        [1 2 1]

Better smoothing, preserves edges more than box filter

Median Filter (Non-linear):

Replace pixel with median of neighborhood

• Best for salt-and-pepper noise removal
• Preserves edges better than mean filter

2. Sharpening (High-pass) Filters:

Laplacian:

[0  1  0]     [-1 -1 -1]
[1 -4  1]  or [-1  8 -1]
[0  1  0]     [-1 -1 -1]

Highlights rapid intensity changes (edges)

Sharpened image:

f_sharp(x,y) = f(x,y) - ∇²f(x,y)

Unsharp Masking:

Sharpened = Original + k × (Original - Blurred)

2D Discrete Fourier Transform (DFT):

F(u,v) = Σx Σy f(x,y) × e^(-j2π(ux/M + vy/N))

Inverse DFT (IDFT):

f(x,y) = (1/MN) Σu Σv F(u,v) × e^(j2π(ux/M + vy/N))

Frequency Domain Concepts:

• Low frequencies = slow intensity changes (smooth regions)
• High frequencies = fast intensity changes (edges, noise)

• ∠F(u,v) = Phase spectrum (contains structural info)

Frequency Domain Filtering Pipeline:

Input f(x,y)
   → DFT → F(u,v)
   → Multiply by H(u,v) filter
   → G(u,v) = H(u,v) × F(u,v)
   → IDFT → Output g(x,y)

Frequency Domain Filters:

D(u,v) = distance from center of spectrum

DFT Properties: Linearity, Translation, Rotation, Scaling, Convolution theorem

Convolution Theorem: Convolution in spatial = Multiplication in frequency domain

Colour Models in DIP:

1. RGB (Additive Model):

• Red, Green, Blue primary colours
• Used in displays/cameras
• RGB cube: corners represent 8 basic colours

2. CMY / CMYK (Subtractive):

C = 1-R, M = 1-G, Y = 1-B

• Used in printing

3. HSI Model:

• H (Hue) = dominant colour, 0°-360°
• S (Saturation) = colour purity
• I (Intensity) = average brightness = (R+G+B)/3
• Advantage: Separates colour info from intensity → easier segmentation

4. YCbCr:

• Y = Luma, Cb = Blue-diff, Cr = Red-diff
• Used in JPEG, MPEG
• Human vision more sensitive to Y → more bits for Y

Colour Transforms:

• Convert between colour spaces (RGB↔HSI, RGB↔YCbCr)
• Manipulate individual channels independently

Pseudo-Colouring (False Colouring):

Assigning colours to grayscale intensities for better human visualization.

Methods:

• 1. Intensity Slicing: Assign different colour to each intensity band

→ if 0≤r<64: Blue, 64≤r<128: Green, 128≤r<192: Yellow, 192≤r≤255: Red

• 2. Gray-to-Colour Transformation: Use 3 different intensity transforms for R, G, B channels

Applications: Medical imaging (X-ray, thermal), satellite imagery, scientific visualization

Wavelet Transform:

A multi-resolution analysis tool that decomposes an image at multiple scales simultaneously — unlike Fourier which only gives frequency info.

Key Advantage over Fourier:

• Fourier: Only frequency, NO spatial location
• Wavelet: BOTH frequency AND spatial location

1D Discrete Wavelet Transform (DWT):

Decomposes signal into:

• Approximation coefficients (cA) = low frequency (trend)
• Detail coefficients (cD) = high frequency (edges, noise)

2D DWT (Image Decomposition):

Apply 1D DWT on rows then columns → 4 subbands:

┌──────┬──────┐
│  LL  │  LH  │
│(Approx)│(Horiz)│
├──────┼──────┤
│  HL  │  HH  │
│(Vert)│(Diag) │
└──────┴──────┘

• LL = Low-Low = Approximation (blurred version)
• LH = Low-High = Horizontal edges
• HL = High-Low = Vertical edges
• HH = High-High = Diagonal edges/noise

Multi-Resolution: Apply DWT again to LL subband → more levels

Wavelet Families: Haar (simplest), Daubechies, Biorthogonal

Applications:

• JPEG 2000 uses wavelet (better than DCT-based JPEG)
• Image denoising (threshold wavelet coefficients)
• Feature extraction, watermarking

Degradation-Restoration Model:

Original     Degradation     Degraded      Restoration    Restored
Image    →   Function H   →  Image      →  Filter        → Image
f(x,y)    + Noise η(x,y)   g(x,y)         R(u,v)          f̂(x,y)

Mathematical Model:

Where:

• h(x,y) / H(u,v) = degradation (PSF / OTF)
• η(x,y) / N(u,v) = additive noise

= convolution operator

PSF (Point Spread Function): How a point source of light is blurred by the imaging system.

Goal of Restoration:

Estimate original f(x,y) given g(x,y) and knowledge of H and noise.

Key Difference: Enhancement vs Restoration:

Types of Degradation:

• Atmospheric turbulence blur
• Motion blur (camera/object movement)
• Out-of-focus blur (defocus aberration)
• Electronic sensor noise

Noise = Random variation of brightness/colour in images.

Noise Models (by Probability Density Function):

1. Gaussian Noise:

p(z) = (1/√2πσ) × e^(-(z-μ)²/2σ²)
μ = mean, σ = standard deviation

• Most common noise type
• From electronic circuitry, poor illumination
• Appears as random grain throughout image

2. Rayleigh Noise:

p(z) = (2/b)(z-a) × e^(-(z-a)²/b)  for z ≥ a

• Skewed distribution (not symmetric)
• Used in range imaging and radar

3. Erlang (Gamma) Noise:

• Used in laser imaging

4. Exponential Noise:

• Special case of Erlang (b=1)

5. Uniform Noise:

p(z) = 1/(b-a)  for a ≤ z ≤ b

• Flat distribution
• Used in quantization noise modeling

6. Impulse (Salt-and-Pepper) Noise:

p(z) = Pa  for z=a (pepper/black)
       Pb  for z=b (salt/white)

• Random black or white pixels scattered
• Caused by: transmission errors, dead pixels, A/D errors
• Best removed by median filter

Estimating Noise Parameters:

Select a flat region of image → compute mean and variance of that patch

Noise Filters in Spatial Domain:

A. Mean Filters:

1. Arithmetic Mean Filter:

f̂(x,y) = (1/mn) Σ g(s,t)

Simple average of m×n neighborhood. Blurs noise but also edges.

2. Geometric Mean Filter:

f̂(x,y) = [∏ g(s,t)]^(1/mn)

Less blurring than arithmetic mean.

3. Harmonic Mean Filter:

Good for salt noise, not pepper.

4. Contra-harmonic Mean Filter:

f̂(x,y) = Σg(s,t)^(Q+1) / Σg(s,t)^Q

• Q > 0: eliminates pepper noise
• Q < 0: eliminates salt noise

B. Order-Statistics Filters:

Median Filter:

f̂(x,y) = median{g(s,t)} in m×n window

• Best for salt-and-pepper noise
• Preserves edges
• Sort pixels, pick middle value

Max Filter (Q=100%): Finds brightest pixel → removes pepper noise

Min Filter (Q=0%): Finds darkest pixel → removes salt noise

Midpoint Filter: Average of max and min

C. Adaptive Filters:

Adaptive Local Noise Reduction Filter:

f̂(x,y) = g(x,y) - [σ²η/σ²L] × [g(x,y) - mL]

• Adapts behavior based on local image statistics
• Low noise region → little smoothing
• High noise region → more smoothing
• Preserves edges while removing noise

Inverse Filtering:

If G(u,v) = H(u,v)·F(u,v) + N(u,v)

Ideal restoration:

F̂(u,v) = G(u,v) / H(u,v)
         = F(u,v) + N(u,v)/H(u,v)

Problem: When H(u,v) ≈ 0, noise term N/H blows up → restoration fails!

Solution - Truncated Inverse Filter:

F̂(u,v) = G(u,v)/H(u,v)  if |H(u,v)| > threshold
         = 0              otherwise

Limits amplification of noise but still not optimal.

Wiener Filter (Minimum MSE Filter):

Optimal restoration considering BOTH degradation AND noise.

F̂(u,v) = [H*(u,v) / (|H(u,v)|² + Sη(u,v)/Sf(u,v))] × G(u,v)

Where:

• H*(u,v) = complex conjugate of H

• Sη(u,v) = noise power spectrum
• Sf(u,v) = signal power spectrum
• Sη/Sf = noise-to-signal power ratio

Simplified (when noise/signal ratio is constant K):

F̂(u,v) = [H*(u,v) / (|H(u,v)|² + K)] × G(u,v)

Wiener vs Inverse:

Wiener filter automatically: Smooths where noise is high, sharpens where signal is strong

Homomorphic Filtering:

A technique to simultaneously correct non-uniform illumination and enhance contrast.

Image Model:

f(x,y) = i(x,y) × r(x,y)

Where:

• i(x,y) = Illumination component (slow varying, low frequency)
• r(x,y) = Reflectance component (fast varying, high frequency)

Problem: i and r are multiplicative → can't separate directly.

Homomorphic Filtering Pipeline:

f(x,y)
  → ln[f(x,y)] = ln[i(x,y)] + ln[r(x,y)]   ← converts × to +
  → DFT → F(u,v) = Fi(u,v) + Fr(u,v)
  → Multiply by H(u,v) high-pass/band filter
  → IDFT
  → Exponential (exp) → output image f̂(x,y)

Filter H(u,v) Design:

• Low-frequency region (illumination): γL < 1 (compress/reduce)
• High-frequency region (reflectance): γH > 1 (expand/enhance)
• Typically: γL = 0.5, γH = 2.0

Result:

• Compresses illumination range (reduces bright/dark patches)
• Expands reflectance range (sharpens details)

Application: Processing images taken under uneven lighting conditions (medical images, satellite photos, indoor scenes)

Image Compression = Reducing the amount of data required to represent a digital image.

Compression Ratio:

CR = Uncompressed Size / Compressed Size
Example: 10 MB → 1 MB means CR = 10:1

Relative Data Redundancy:

RD = 1 - 1/CR
CR = 10 → RD = 0.9 (90% of data is redundant)

Three Types of Redundancy:

1. Coding Redundancy:

Using more bits than necessary to represent intensity values.

• Natural binary: 8 bits per pixel uniformly
• But some intensities appear more → use shorter codes
• Solution: Variable-length coding (Huffman, Arithmetic)
• Average code length < 8 bits when coding redundancy removed

2. Interpixel Redundancy (Spatial/Temporal):

Adjacent pixels are highly correlated (similar values).

• Spatial redundancy: Neighboring pixels in same frame
• Temporal redundancy: Frames in video that barely change
• Solution: Predictive coding (DPCM), Run-Length Encoding (RLE)
• Example: RLE — instead of [200, 200, 200, 200, 200] store [(200, 5)]

3. Psychovisual Redundancy:

Some visual information is not perceived by human eye.

• Eye is less sensitive to high-frequency details
• Eye has lower spatial resolution for color than luminance
• Solution: Quantization, discard imperceptible info
• This causes LOSSY compression (information permanently lost)

Lossless vs Lossy:

Huffman Coding = Lossless variable-length coding that assigns shorter codes to more frequent symbols.

Principle: More frequent symbol → shorter code

Huffman Encoding Algorithm:

• 1. Count frequency of each symbol
• 2. Create leaf node for each symbol, add to priority queue (min-heap)
• 3. While queue has more than 1 node:
• Remove two nodes with lowest frequency
• Create new internal node with sum frequency
• Add back to queue
• 4. Resulting tree = Huffman tree
• 5. Assign 0 to left branch, 1 to right branch
• 6. Code = path from root to leaf

Example:

Symbol | Frequency | Code
-------|-----------|---------
  A    |   0.40    |   0      (1 bit)
  B    |   0.30    |   10     (2 bits)
  C    |   0.20    |   110    (3 bits)
  D    |   0.10    |   111    (3 bits)

Tree Construction:

      (1.0)
      /    \
    (0.6)  A=0
    /    \
  (0.3)   B=10
  /    \
 C=110  D=111

Average Code Length:

L = 0.4×1 + 0.3×2 + 0.2×3 + 0.1×3
  = 0.4 + 0.6 + 0.6 + 0.3 = 1.9 bits/symbol

Vs uniform 2 bits → saving = (2-1.9)/2 = 5% compression

Entropy (Theoretical Minimum):

H = -Σ p(k) × log₂[p(k)]

Huffman coding achieves close to entropy.

Huffman Decoding: Traverse tree bit by bit from root until reaching leaf

Arithmetic Coding:

Encodes an entire message (sequence of symbols) into a single fractional number in [0, 1).

Key Idea: Better than Huffman because it can assign fractional bits per symbol.

Encoding Steps:

• 1. Start with interval [0, 1)
• 2. For each symbol, subdivide current interval proportional to probabilities
• 3. Choose sub-interval corresponding to current symbol
• 4. Final compressed output = any number within last interval

Example:

Symbols: A=0.4, B=0.3, C=0.2, D=0.1
Encode: "AB"

Initial: [0, 1)
After A (prob=0.4): [0, 0.4)
After B (prob=0.3): [0 + 0.4×0.4, 0 + 0.4×0.7) = [0.16, 0.28)
Output: 0.2 (any value in [0.16, 0.28))

Arithmetic vs Huffman:

Lossy Compression Techniques:

1. Predictive Coding (DPCM):

Encode difference between actual and predicted value

e(n) = f(n) - f̂(n)  ← encode error, not original

2. Transform Coding:

Transform image → fewer significant coefficients → quantize → encode

3. Wavelet Coding:

DWT → threshold small coefficients → encode (used in JPEG 2000)

4. Fractal Compression:

Exploit self-similarity in images

JPEG (Joint Photographic Experts Group) — Most widely used lossy image compression standard.

JPEG Compression Pipeline:

Step 1: Color Space Conversion

RGB → YCbCr
Subsample Cb, Cr (4:2:0) — human eye less sensitive to chroma

Step 2: Block Division

Divide image into 8×8 pixel blocks

Step 3: DCT (Discrete Cosine Transform)

F(u,v) = (1/4)C(u)C(v) Σx Σy f(x,y)·cos[(2x+1)uπ/16]·cos[(2y+1)vπ/16]

• Converts 8×8 spatial block → 64 frequency coefficients
• F(0,0) = DC coefficient (average brightness)
• Other F(u,v) = AC coefficients (detail/texture)

Step 4: Quantization (Main Lossy Step)

FQ(u,v) = round[F(u,v) / Q(u,v)]

• Q(u,v) = quantization table (larger values for high frequencies)
• High-frequency coefficients → quantized to 0 (discarded)
• Quality factor controls Q table: low quality → larger Q → more loss

Step 5: Zigzag Scan

Reorders 8×8 block zigzag pattern → long runs of zeros at end

Step 6: Run-Length Encoding + Huffman Coding

• Encode (value, run-length-of-zeros) pairs
• Huffman encode the result

JPEG Decompression: Exact reverse (Huffman → RLE → Dequantize → IDCT → YCbCr→RGB)

JPEG Artifacts:

• Blocking artifacts (visible 8×8 blocks at high compression)
• Ringing around sharp edges

JPEG 2000 uses Wavelet instead of DCT → better quality, no blocking

Segmentation = Partitioning an image into regions/objects based on discontinuities or similarities.

Discontinuity-Based Segmentation:

Detects abrupt changes in intensity (points, lines, edges).

1. Point Detection:

Uses Laplacian mask:

[-1 -1 -1]
[-1  8 -1]
[-1 -1 -1]

Where R = sum of mask × image region

2. Line Detection:

Four directional masks (horizontal, vertical, +45°, -45°):

Horizontal:  [-1 -1 -1]   Vertical: [-1 2 -1]
              [ 2  2  2]             [-1 2 -1]
              [-1 -1 -1]             [-1 2 -1]

A line is detected in direction where response is maximum.

3. Edge Detection:

Edge = Boundary between two regions with significantly different intensity.

Steps in Edge Detection:

• 1. Smoothing — reduce noise (Gaussian blur)
• 2. Enhancement — emphasize edge pixels (gradient)
• 3. Detection — threshold gradient magnitude
• 4. Localization — find exact edge location (optional)

Gradient-Based:

∇f = [Gx, Gy] = [∂f/∂x, ∂f/∂y]
|∇f| = √(Gx² + Gy²)  ← gradient magnitude
θ = arctan(Gy/Gx)     ← edge direction

Common Edge Detectors:

• Roberts: 2×2 diagonal differences, simple but noisy
• Prewitt: 3×3, uses horizontal and vertical differences
• Sobel: 3×3 weighted (better noise handling)
• Laplacian of Gaussian (LoG): Combines smoothing + second derivative
• Canny: Best overall — multi-step, optimal edge detector

Sobel Edge Detector:

Two 3×3 kernels for horizontal (Gx) and vertical (Gy) gradients:

Gx = [-1 0 +1]    Gy = [+1 +2 +1]
     [-2 0 +2]         [ 0  0  0]
     [-1 0 +1]         [-1 -2 -1]

Gradient Magnitude and Direction:

|G| = √(Gx² + Gy²)  ≈ |Gx| + |Gy|  (approximation)
θ = arctan(Gy/Gx)

Prewitt Detector: Similar to Sobel but without the 2 weighting at center.

Canny Edge Detector (Optimal):

Best edge detector — minimizes false edges, good localization.

5 Steps:

• 1. Gaussian Smoothing: Remove noise

 f(x,y)```

2. **Gradient Computation:** Sobel operators → Gx, Gy, magnitude, direction

3. **Non-Maximum Suppression (NMS):**
   - Thin edges to 1 pixel wide
   - Keep pixel only if it is local maximum in gradient direction

4. **Double Thresholding:**
   - High threshold TH and Low threshold TL
   - |G| > TH → strong edge ✓
   - TL < |G| < TH → weak edge (candidate)
   - |G| < TL → not an edge ✗

5. **Hysteresis (Edge Tracking):**
   - Weak edge kept only if connected to strong edge
   - Eliminates isolated noise points

**Canny Parameters:** σ (smoothing), TH, TL
**Canny Criteria:** Good detection, good localization, minimal response

Thresholding = Simplest segmentation method. Converts grayscale to binary by selecting a threshold T.

g(x,y) = 255  if f(x,y) > T    (object/foreground)
          0    if f(x,y) ≤ T   (background)

Types of Thresholding:

1. Global Thresholding:

Single T value for entire image.

• Works when object and background have clearly distinct intensities
• Histogram has two distinct peaks (bimodal)
• T selected at valley between peaks

Basic Global Threshold Algorithm (Iterative):

1. Initial T = midpoint (T₀ = 127)
2. Segment into G1 (pixels > T) and G2 (pixels ≤ T)
3. Compute means μ1 = mean(G1), μ2 = mean(G2)
4. New T = (μ1 + μ2)/2
5. Repeat steps 2-4 until T converges

2. Otsu's Method (Optimal Global Threshold):

Finds T that minimizes intra-class variance (or maximizes inter-class variance).

σ²B(T) = w1(T) × w2(T) × [μ1(T) - μ2(T)]²

Where w1, w2 = fractional areas, μ1, μ2 = means of two classes.

Optimal T* = argmax σ²B(T)

3. Local / Adaptive Thresholding:

Different T for different image regions.

• Handles non-uniform illumination
• T(x,y) depends on local statistics of neighborhood

4. Multiple Thresholding:

For images with multiple objects at different intensities:

g = a  if f > T2
    b  if T1 < f ≤ T2
    c  if f ≤ T1

Best Case: Use when illumination is uniform and histogram is clearly bimodal.

Hough Transform = Technique to detect geometric shapes (lines, circles, ellipses) in an edge image.

Hough Transform for Lines:

A line in image space: y = mx + b

But vertical lines have m = ∞ → Problem!

Solution — Normal Parametrization:

ρ = x·cos(θ) + y·sin(θ)

Where:

• ρ = perpendicular distance from origin to line
• θ = angle of the perpendicular (0° to 180°)

Algorithm:

• 1. Create accumulator array A(ρ, θ) initialized to 0
• 2. For each edge pixel (x,y):
• For each θ from 0° to 180°:
• Compute ρ = x·cos(θ) + y·sin(θ)
• Increment A(ρ, θ) += 1
• 3. Find peaks in accumulator → each peak = a line
• 4. Peak at (ρ₀, θ₀) means a line exists with those params

Intuition: Each point in image space maps to a sinusoidal curve in (ρ,θ) space. If multiple points lie on same line, their curves intersect at same peak.

Hough Transform for Circles:

(x - a)² + (y - b)² = r²

For known radius r: accumulate in (a,b) space (2D).

For unknown radius: 3D accumulator (a, b, r).

Advantages:

• Robust to noise and occlusion
• Detects lines even if partially missing
• Works on disconnected edge segments

Disadvantages:

• High computational cost for high-dimensional parameter spaces
• Memory intensive for 3D accumulators

Region-Based Segmentation:

Group pixels that are similar in some property (intensity, texture, color) into regions.

1. Region Growing:

Start from seed pixels, expand region by adding similar neighboring pixels.

Algorithm:

1. Select seed pixel(s) manually or automatically
2. Define similarity criterion (e.g., |f(x,y) - mean_region| < T)
3. Examine 4-connected or 8-connected neighbors
4. Add neighbor to region if criterion satisfied
5. Repeat until no more pixels can be added
6. Unvisited pixels → new seed for next region

Similarity Criteria:

• Intensity difference < threshold
• Similar texture properties
• Same color range

Problem: Seed selection is critical; noisy pixels can cause leaking.

2. Region Splitting (Top-Down):

1. Start with entire image as one region
2. If region is NOT homogeneous:
   → Split into 4 quadrants (Quadtree decomposition)
3. Repeat recursively until all regions are homogeneous

3. Region Merging (Bottom-Up):

1. Start with individual pixels as separate regions
2. Merge adjacent regions if they are similar
3. Repeat until no more merging possible

4. Split-and-Merge (Combined):

• Split non-homogeneous regions
• Merge similar adjacent regions
• Produces better results than either alone

Homogeneity Predicate P(R):

Example: P(R) = TRUE if max(R) - min(R) ≤ T

Comparison:

Boundary Representation:

After segmentation, boundaries of regions need to be represented compactly.

1. Chain Code:

Encodes boundary as sequence of directional codes (0-7 for 8-connectivity).

Directions (8-connected):
  3  2  1
  4  ·  0
  5  6  7

Algorithm:

• 1. Start at a boundary pixel
• 2. Move clockwise along boundary
• 3. Record direction code at each step
• 4. Result: sequence of 0-7 values

Example boundary → chain code: [0, 0, 6, 6, 4, 4, 2, 2]

Normalization:

• Starting point normalization: Treat chain code as circular sequence, start with smallest integer value
• Rotation normalization: First difference of chain code (subtract consecutive codes mod 8) → invariant to rotation

2. Polygonal Approximation:

Approximate boundary by polygon with minimum vertices.

• Merging technique: merge collinear segments
• Splitting technique: find point furthest from line, add vertex there

3. Signatures:

Plot distance from centroid to boundary as function of angle.

r(θ) = distance from centroid at angle θ

• Compact 1D representation of 2D boundary
• Rotation invariant when normalized

4. Fourier Descriptors:

• Express boundary as complex numbers: u(k) = x(k) + j·y(k)
• Take 1D DFT → Fourier coefficients
• Use first N coefficients (low frequencies capture shape)
• Advantages: Scale, rotation, translation invariant when normalized

5. Boundary Moments:

Statistical moments of boundary pixels:

μ_p = (1/K)Σ [u(k)]^p

• Mean, variance, skewness describe shape characteristics