from thesis Pattern matching using similarity measures

There are two types of pattern matching: **combinatorial pattern matching** and **spatial pattern matching**.

**Spatial pattern matching**

is the problem of finding a match between two given intensity images or geometric models. Here, a match may be a correspondence or a geometric transformation.

Pattern matching problems can be categorised by three components:

**the collection of patterns**, e.g. colour images, grey scale images, CAD models, and vector based graphics- the
**class of transformations**: translations,*Euclidean isometries*(which preserve the Euclidean distance between each pair of points),*Affine transformations*(which are compositions of linear transformations and translations),*elastic transformations*(which do not necessarily preserve straight lines) and*correspondences*(which are relations between particular features in both patterns).

- the
**criterion used to select a transformation**.*e.g., a transformation*must minimise the value of a similarity measure (which is a function that assigns a nonnegative real number to each pair of patterns).- The selection criterion is not always made explicit the description of a method.

- the
**input**of a pattern matching algorithm is**a pair of patterns**, Given are two input patterns A and B - and the
**output**is a**transformation**. g for which*g(A) is similar to B*

**Object recognition is similar to pattern matching**.

object recognition is used for:

- region segmentation (determining the regions in an image that correspond to distinct physical objects)
- a form of partial pattern matching (to detect occurrences of a given object in an image)
- shape recognition:
- In the narrow sense, shape recognition is finding the pattern in a finite database whose shape most resembles that of a query pattern.
- known as
**model based object recognition**

- known as
- In the broad sense, shape recognition is determining what shape a pattern has. This does not necessarily involve the use of model patterns
- The
**shape classification**problem is determining to which category a pattern belongs

- The

- In the narrow sense, shape recognition is finding the pattern in a finite database whose shape most resembles that of a query pattern.

- To obtain patterns from geometric models,
**representation conversions**may be necessary - To obtain patterns from images,
**feature extraction**is necessary- corner detection: points on the contour of an object at which the
**curvature is high** - edge detection: finding the boundaries between regions in an image that correspond to distinct physical objects, compute differences in intensities between neighbouring pixels, then thresholded, resulting in edges.
- region detection: determining the regions in an image that correspond to a single physical object. e.g., apply pixelwise thresholding on colour or intensity

- corner detection: points on the contour of an object at which the

**Paradigms in geometric pattern matching**

**1. Correspondence methods **match patterns by fitting pairs of geometric primitives, depending more on the representation and the topology of patterns than on the geometry of patterns.

An **advantage of correspondence methods** is that they may produce an explicit relation between the geometric primitives in both patterns.

- An example is matching polylines in the plane under similarity transformations by pairing line segments of both polylines. Each combination of line segments results in exactly two similarity transformations.
**graph matching**- The structure of a pattern is described as a graph. e.g., Aspect graph
- Matches between the graphs may be found by searching for
**graph isomorphisms**or subgraph isomorphisms(NP-complete). - Drawbacks:
- not very robust for errors: the success of the technique depends on the correct extraction of the graphs from the input.
- a lack of discernment: large classes of patterns share the same graph.

**geometric hashing**- the geometric primitives that make up a pattern are used to generate a normalised description of the pattern as a whole.
- All normalised descriptions are used to build a hash table.
- Geometric hashing is robust for missing points and occlusion
- Geometric hashing works fine on finite point set patterns.
- very dependent on the representation and topology of patterns, which is a drawback if the input patterns are obtained from images by means of feature extraction.

**2. Alignment methods **match patterns by fitting the unions of geometric primitives, search for a match between the two input patterns as sets, ignoring how the patterns is represented.

No matter how two given patterns are represented in terms of geometric primitives, the outcome of an alignment method will remain the same.

**Global methods**- mapping the bounding box of one pattern onto the bounding box of another pattern.
- translating the centroid of a pattern onto the centroid of another pattern.
**Moment based techniques**can be used to match under Euclidean isometries and similarity transformations.

- Most successful if the input patterns are almost equal, Simple, Fast
- Drawbacks:
- not well suited for finding plausible matches between two patterns that differ much
- not well suited for partial pattern matching.

**Similarity measure based pattern matching**

A similarity measure is a function that assigns a nonnegative real number to each pair of patterns.

- finding a
**geometric transformation**that minimises a similarity measure.the precise problems is, given patterns A and B, finding a transformation g (from a specific class of transformations) that**minimises the value of the similarity measure on g(A) and B**. - similarity measure based methods are independent of representation.
- The performance depends much on the choice of
**similarity measure** - can be used to find plausible matches if the patterns differ much, partial pattern matching
- but slower than global matching

**number of matching pairs with the query image**