Object Recognition

In pattern recognition, understanding “patterns” and “pattern classes” is fundamental. Here’s a structured breakdown of the mathematical concepts and examples discussed.

1. Patterns and Pattern Classes

• Pattern: An arrangement of descriptors (or features) used to represent an object or entity.
• Descriptor: An attribute or characteristic of an object, often called a “feature” in pattern recognition literature.
• Pattern Class: A family of patterns sharing common properties. Each pattern class is denoted by $v_i$, where $i$ represents the class number.

In machine-based pattern recognition, the goal is to assign patterns to their respective classes with minimal human intervention. This involves various techniques and mathematical tools.

2. Common Pattern Arrangements

Three common forms of patterns are vectors, strings, and trees, each suited to different types of descriptions:

a. Pattern Vectors (Quantitative Descriptions)

• Represented by bold lowercase letters (e.g., x, y, z), pattern vectors are used for quantitative features.

• A pattern vector is a column matrix:

  $$\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$$

  where each $x_i$ is a descriptor, and $n$ is the total number of descriptors. This vector is also expressed as:

  $$\mathbf{x} = (x_1, x_2, \ldots, x_n)^T$$

  where $T$ denotes transposition.

Example: Iris Classification (Fisher, 1936)

• Each iris flower is described by two measurements: petal length and width, forming a 2D pattern vector:

  $$\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$$

  Here, $x_1$ is petal length, and $x_2$ is petal width. The pattern classes, $v_1$, $v_2$, and $v_3$, represent the varieties “setosa,” “virginica,” and “versicolor,” respectively.

• By plotting these vectors in a 2D Euclidean space, each flower is represented as a point, allowing us to distinguish classes based on the separation of points.

b. Pattern Vectors in Higher Dimensions

In some cases, descriptors are sampled at specific intervals, creating high-dimensional vectors. For example:

Here, each $u_i$ represents a sampled point, and $r(u_i)$ is the amplitude at that point. These vectors form points in an $n$-dimensional Euclidean space, where patterns are visualized as “clouds” in the space.

c. Structural Descriptions (Strings and Trees)

For certain applications, structural descriptions are more effective than quantitative measures.

i. String Descriptions

Patterns with repeated structures can be represented as strings. For example, a staircase pattern may consist of alternating primitive elements, such as “A” and “B”. A staircase can then be represented by the string:

The order of these elements captures the pattern structure.

ii. Tree Descriptions

Tree structures represent hierarchical relationships, as seen in spatial and image analysis. For example, in a satellite image of a city, we could use the following hierarchy:

• Root node: Entire image
• Next level: Distinguishes “downtown” and “residential areas”
• Further levels: Separate “housing,” “highways,” and “shopping malls” within residential areas

This hierarchical representation allows for detailed structural analysis.

3. Pattern Recognition Techniques

Selecting descriptors impacts the success of pattern recognition. Examples include:

• Quantitative Techniques: These use measurements to create pattern vectors, as seen in iris classification.
• Structural Techniques: These analyze spatial relationships, like fingerprint minutiae (e.g., ridge endings and branch points), which are used in fingerprint recognition.

Example Problem: Recognition of Shapes with Noise

Suppose we want to classify noisy shapes, each represented by a 1D signature. By sampling the signature at intervals, we obtain a pattern vector in $n$-dimensional space. Alternatively, we could compute statistical features, such as moments, for each signature and use these in our pattern vector.

Recognition based on decision-theoretic methods is a fundamental approach in pattern recognition that leverages statistical probability and optimization techniques to classify patterns. These methods rely on decision functions that use feature vectors, distances, and probability distributions to assign patterns to classes, with a primary goal of minimizing misclassification errors.

Here, we expand on the mathematical concepts behind these methods, including the Minimum Distance Classifier, the Bayes Classifier, and Correlation-Based Matching, along with examples that illustrate these principles in action.

1. Decision-Theoretic Framework

In decision-theoretic pattern recognition, we use decision functions $d_i(x)$ for each class $v_i$, where $x = (x_1, x_2, \ldots, x_n)^T$ is an $n$-dimensional feature vector. A pattern is assigned to the class with the highest value of $d_i(x)$, that is:

The set of points $x$ where $d_i(x) = d_j(x)$ forms the decision boundary separating class $v_i$ from $v_j$. Decision boundaries play a critical role in defining the regions of the feature space assigned to each class.

2. Minimum Distance Classifier

The Minimum Distance Classifier is a straightforward classifier that assigns a pattern vector $x$ to the class whose prototype vector (often the mean vector) is closest to $x$ in terms of Euclidean distance. This method assumes that each class $v_i$ can be represented by a prototype or mean vector $m_i$ defined as:

where $N_i$ is the number of training samples in class $v_i$.

Euclidean Distance Calculation

For a new pattern $x$, we compute the Euclidean distance $D_j(x)$ from $x$ to each class prototype $m_j$ as:

where $m_{j,k}$ denotes the $k$-th component of the mean vector $m_j$.

Classification Rule

The pattern $x$ is assigned to the class with the smallest $D_j(x)$:

Example: Suppose we classify two types of iris flowers based on petal length and width. The mean vectors for each class are calculated, and the classifier computes the Euclidean distance between a new flower’s feature vector and each class mean. The class with the smallest distance is chosen as the classification for the new flower.

3. Bayes Classifier

The Bayes Classifier is an optimal statistical classifier that minimizes the average probability of misclassification by assigning patterns based on posterior probabilities. The Bayes classifier uses Bayes’ theorem to compute the posterior probability $P(v_i | x)$, the probability of $x$ belonging to class $v_i$ given the observed data.

Bayes Decision Rule

A pattern $x$ is assigned to the class $v_i$ if:

Using Bayes’ theorem, the posterior probability $P(v_i | x)$ can be rewritten as:

where:

• $P(x | v_i)$: Likelihood of observing $x$ given that it belongs to class $v_i$.
• $P(v_i)$: Prior probability of class $v_i$.
• $P(x)$: Marginal probability of observing $x$ across all classes, acting as a normalizing constant.

The decision rule simplifies to:

Zero-One Loss Function

A common choice in Bayes classification is the 0-1 loss function, where the loss is 0 for correct classifications and 1 for incorrect ones. The Bayes classifier then minimizes the probability of misclassification by assigning $x$ to the class with the highest posterior probability.

Gaussian Bayes Classifier

If the probability densities $P(x | v_i)$ follow a multivariate Gaussian distribution, the likelihood of $x$ given class $v_i$ with mean vector $m_i$ and covariance matrix $C_i$ is:

where $|C_i|$ is the determinant of $C_i$.

The Bayes decision function for each class then becomes:

The classifier assigns $x$ to the class with the highest $d_i(x)$.

Example: In remote sensing, multispectral data from different spectral bands can be used to classify land cover types. Each pixel is represented as a vector, and the Bayes classifier assigns each pixel to a land cover class based on estimated Gaussian densities for each class.

4. Correlation-Based Matching

Correlation-based matching is used when patterns are matched with predefined templates, especially in applications involving images or shapes. This method compares patterns based on similarity rather than probability, using a correlation coefficient as a measure of similarity.

Normalized Correlation Coefficient

The normalized correlation coefficient between a pattern $x$ and a template $y$ is given by:

where $\bar{x}$ and $\bar{y}$ are the mean values of $x$ and $y$, respectively. This coefficient $r(x, y)$ ranges from -1 to 1:

• $r(x, y) = 1$ indicates a perfect positive correlation.
• $r(x, y) = -1$ indicates a perfect negative correlation.
• $r(x, y) = 0$ indicates no correlation.

Template Matching Rule

Assign $x$ to the class represented by template $y$ if $r(x, y)$ is maximized for that template among all others:

Example: In satellite image processing, a correlation-based matcher can identify a specific feature within an image (such as the eye of a hurricane) by finding the region with the highest correlation with a template of the feature.

Practical Applications of Decision-Theoretic Methods

Example 1: Character Recognition Using Minimum Distance Classifier In automated reading of bank checks, characters are represented by feature vectors based on pixel densities or boundary points. The minimum distance classifier compares a new character’s vector with prototype vectors of each character, assigning it to the class with the smallest distance.

Example 2: Land Cover Classification Using Bayes Classifier In remote sensing, each pixel of a multispectral image is classified as water, urban, or vegetation using the Bayes classifier. This classifier uses prior knowledge of land cover probabilities and multispectral data from sample regions to compute mean vectors and covariance matrices for each class.

Decision-theoretic methods provide a robust framework for pattern recognition, using probabilistic and mathematical criteria to minimize misclassification risks. The choice of a method depends on the nature of the data, the degree of overlap between classes, and the computational requirements of the application.