Pattern Recognition & Shape Analysis: Features, Classifiers & Shape Descriptors

TAKEAWAYS:

• Pattern recognition is the automated classification of objects (e.g., digits, faces) using features like edges, textures, or statistical moments, with decision-theoretic methods minimizing misclassification errors via Bayes’ theorem.
• Shape analysis quantifies objects via boundary descriptors (chain codes, Fourier descriptors) or region descriptors (moments, Zernike polynomials), enabling tasks like handwritten signature verification or tumor segmentation.
• Decision-theoretic classifiers (Bayesian, minimum-distance) rely on probability distributions of features, while structural classifiers (syntactic, neural) model patterns as grammars or hierarchical networks.
• Chain codes represent object boundaries as 8-directional sequences, while Fourier descriptors capture shape spectra for rotation/scale invariance—critical for OCR and fingerprint matching.
• Moment invariants (Hu moments) describe shape properties (area, orientation) independently of affine transformations, used in license plate recognition (NTC) and satellite image analysis.
• Mexican Hat filters (DoG) detect edges via second-derivative zero-crossings, forming the backbone of feature extraction in SIFT and edge-based segmentation.

---

1. Pattern Recognition: From Pixels to Decisions

Pattern recognition (PR) is the process of assigning labels (classes) to input data (e.g., images, signals) based on learned features. It combines:

• Feature extraction: Converting raw pixels into meaningful descriptors (e.g., edges, textures).
• Classification: Mapping features to classes using statistical, structural, or neural models.

1.1 Definitions: Pattern vs. Pattern Class

• Pattern: A set of measurements (features) describing an object. Example: A 16×16 pixel handwritten digit’s edge density and curvature.
• Pattern class: A category of similar patterns (e.g., "digit ‘5’" or "malignant tumor").
• Feature vector: A numerical representation of a pattern (e.g., [edge_count, texture_energy, compactness]).

Example of 28×28 pixel patterns for digits 0–9. (Image: Suvanjanprasai, CC BY-SA 4.0, via Wikimedia Commons)

1.2 Decision-Theoretic Methods: Minimizing Misclassification

These methods use probability theory to classify patterns by minimizing errors. Key approaches:

Worked Example: Bayesian Classification for eSewa Face Recognition Suppose eSewa’s system uses two features for face verification:

• $x_1$: Eye distance (normalized).
• $x_2$: Nose width (normalized).

Given:

• Class ${\omega }_1$ (User): $P({\omega }_1)=0.9$, $x_1\sim N(0.5,0.1)$, $x_2\sim N(0.4,0.05)$.
• Class ${\omega }_2$ (Impostor): $P({\omega }_2)=0.1$, $x_1\sim N(0.3,0.08)$, $x_2\sim N(0.6,0.1)$.

Test pattern: $x=[0.48,0.45]$. Step 1: Compute likelihoods $P(x|{\omega }_i)$ using Gaussian PDF: $$P(x|{\omega }_1)=\frac{1}{2\pi {\sigma }_1{\sigma }_2}\exp \left(-\frac{(x_1-0.5{)}^2}{2\cdot 0.1^2}-\frac{(x_2-0.4{)}^2}{2\cdot 0.05^2}\right)$$ $$P(x|{\omega }_2)=\frac{1}{2\pi {\sigma }_3{\sigma }_4}\exp \left(-\frac{(x_1-0.3{)}^2}{2\cdot 0.08^2}-\frac{(x_2-0.6{)}^2}{2\cdot 0.1^2}\right)$$ Step 2: Apply Bayes’ theorem: $$P({\omega }_1|x)=\frac{P(x|{\omega }_1)P({\omega }_1)}{P(x)},P({\omega }_2|x)=\frac{P(x|{\omega }_2)P({\omega }_2)}{P(x)}$$ Result: $P({\omega }_1|x)>P({\omega }_2|x)$ → Classify as User.

---

2. Shape Analysis: Describing Objects Mathematically

Shape analysis quantifies geometric properties of objects for recognition. Approaches:

1. Boundary-based: Describes the object’s outline.
2. Region-based: Describes internal properties (e.g., moments).
3. Hybrid: Combines both (e.g., SIFT descriptors).

2.1 Boundary Representation: Chain Codes

Chain codes represent an object’s boundary as a sequence of 8-directional steps (0–7). Example for a square:

Chain code for the square: {0, 1, 7, 7} (right, up, left, left).

Worked Example: Shape Number of a Chain Code Given chain code {0, 7, 5, 4, 3, 1}:

1. Convert to complex numbers: $0\to 1$, $7\to i$, $5\to -1-i$, etc.
2. Sum the vectors: $1+i+(-1-i)+(-i)+(-1)+i=-1$.
3. Shape number = angle of the sum: $\text{atan2}(0,-1)=\pi$ (180°).

Application: Used in signature verification (e.g., bank checks). A forged signature’s chain code will have a different shape number than the genuine one.

2.2 Fourier Descriptors: Shape Spectra

Fourier descriptors decompose a shape’s boundary into frequency components, enabling:

• Rotation/scale invariance: Phase and magnitude of Fourier coefficients.
• Noise robustness: Low-frequency coefficients capture coarse shape.

Steps:

1. Trace boundary as $z(k)=x(k)+iy(k)$.
2. Compute DFT: $Z(u)={\sum }_{k=0}^{N-1}z(k)e^{-i2\pi uk/N}$.
3. Use first $M$ coefficients (e.g., $M=10$) for description.

Example: A circle’s Fourier descriptor will have a dominant DC component (constant magnitude).

Worked Example: Daraz Product Logo Recognition Suppose Daraz’s logo is a stylized "D" with boundary points: $$z(k)=[x(k),y(k)]\text{for }k=0,\dots ,63$$ Compute $Z(u)$ and retain $Z(0),Z(1),Z(2)$ (low frequencies). A rotated/scaled "D" will have the same magnitude spectrum for these coefficients.

---

2.3 Region-Based Descriptors: Moments and Invariants

Moments capture an object’s intensity distribution. The $(p+q)$-th moment is: $$m_{pq}=\sum _x\sum _y{x}^p{y}^{q}I(x,y)$$ Central moments (shifted to origin): $${\mu }_{pq}=\sum _x\sum _y(x-\bar{x}{)}^p(y-\bar{y}{)}^{q}I(x,y)$$

Hu Moments (7 invariants under rotation/scale): $${\varphi }_1={\eta }_{20}+{\eta }_{02},{\varphi }_2=({\eta }_{20}-{\eta }_{02}{)}^2+4{\eta }_{11}^2,\dots$$ where ${\eta }_{pq}={\mu }_{pq}/{\mu }_{00}^{(p+q+2)/2}$.

Worked Example: NTC License Plate Recognition A license plate has a rectangular shape. Compute its Hu moments:

1. Binary threshold the plate region.
2. Compute ${\mu }_{pq}$ for $p+q\le 2$.
3. Calculate ${\varphi }_1,{\varphi }_2,{\varphi }_3$:
   • ${\varphi }_1$ captures compactness (rectangles have low ${\varphi }_1$).
   • ${\varphi }_2$ captures orientation (rectangles have ${\varphi }_2\approx 0$ if axis-aligned).

Comparison Table: Shape Descriptors

---

3. Structural Pattern Recognition

Models patterns as hierarchical structures (e.g., grammars, graphs). Used in:

• Syntactic methods: Parse patterns using formal grammars (e.g., scene analysis).
• Graph matching: Compare objects as graphs (e.g., molecular structures).

Example: WhatsApp’s sticker recognition uses graph-based matching to identify emoji shapes.

---

4. Edge Detection and Feature Extraction: Mexican Hat Filters

The Mexican Hat filter (DoG: Difference of Gaussians) detects edges via second derivatives: $$\text{DoG}(x,y)=G(x,y,{\sigma }_1)-G(x,y,{\sigma }_2)$$ where $G$ is a Gaussian kernel.

Steps:

1. Convolve image with DoG at multiple scales.
2. Find zero-crossings (edges) where the response changes sign.

Worked Example: NEPSE Stock Chart Edge Detection A stock price chart (e.g., NEPSE index) can be edge-detected to find:

• Support/resistance levels (horizontal edges).
• Trend changes (vertical edges).

---

In the Real World

1. eSewa’s Face Recognition

   • Idea: Bayesian classification of facial features (eye distance, nose width).
   • How: Uses a decision-theoretic approach to minimize impostor acceptance rate. Features are extracted via Haar cascades, then classified with a trained Gaussian model.
   • Nepali context: Enables secure mobile payments by verifying user identity before transactions.

2. NTC’s License Plate Recognition

   • Idea: Hu moments for shape invariance + OCR for character recognition.
   • How: Plates are segmented, their rectangular shape is verified using ${\varphi }_1$ and ${\varphi }_2$, then characters are classified via template matching.
   • Nepali context: Automates traffic violations and toll collection at highways.

3. Pathao’s Driver App Route Optimization

   • Idea: Fourier descriptors for shape matching of city blocks.
   • How: Pathao’s algorithm compares the shape of a driver’s current route to precomputed "block signatures" (Fourier descriptors of road networks) to suggest optimal paths.
   • Nepali context: Reduces fuel costs and delivery times in Kathmandu’s chaotic traffic.

---

Exam Tip

1. Definitions:

   • Always define pattern, pattern class, and feature vector clearly. For example:

     "A pattern is a set of measurements representing an object, while a pattern class groups similar patterns (e.g., all handwritten ‘A’s)."

   • For shape number, state:

     "The shape number is the angle of the resultant vector obtained by summing chain code directions, used to quantify boundary orientation."

2. Decision-Theoretic Methods:

   • Bayesian classifiers are favored in exams. Show the formula: $${\omega }_i^{\ast }=\arg \underset{i}{\max }P({\omega }_i|x)=\arg \underset{i}{\max }P(x|{\omega }_i)P({\omega }_i)$$
   • Minimum-distance classifiers are simpler; draw a 2D feature space with class means and decision boundaries.

3. Shape Analysis:

   • Chain codes: Practice converting simple shapes (circle, square) to chain codes. Memorize the 8-directional codes (0=right, 1=upper-right, etc.).
   • Fourier descriptors: Explain invariance by saying "low-frequency coefficients are rotation/scale-invariant."
   • Hu moments: List the 7 invariants and their geometric meanings (e.g., ${\varphi }_1$ = compactness).

4. Worked Examples:

   • Bayesian classification: Always show the likelihood calculation step.
   • Chain code shape number: Given a chain code, compute the resultant vector and its angle.
   • Hu moments: For a rectangle, state that ${\varphi }_2\approx 0$ (symmetric about axes).

5. Applications:

   • Link Mexican Hat filters to edge detection in medical imaging (e.g., detecting tumor boundaries).
   • Relate Fourier descriptors to logo recognition (e.g., Daraz’s "D" vs. fake copies).
   • Moment invariants are key for license plate recognition—mention NTC’s use case.

6. Common Pitfalls:

   • Chain codes: Forgetting to normalize for starting point (use Freeman’s convention: start at the top-leftmost pixel).
   • Bayesian assumptions: Not stating that features must be independent.
   • Fourier descriptors: Using too few coefficients (lose shape details).

---

Figure: Pipeline for pattern recognition in real-world systems.