pattern matching

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 fi nding 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:

  1. the collection of patterns, e.g. colour images, grey scale images, CAD models, and vector based graphics
  2. 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).
  3. 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 fi nding the pattern in a finite database whose shape most resembles that of a query pattern.
      • known as model based object recognition
    • 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 classi fication problem is determining to which category a pattern belongs
  1. To obtain patterns from geometric models, representation conversions may be necessary
  2. 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: fi nding the boundaries between regions in an image that correspond to distinct physical objects, compute di fferences 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

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 fi nite 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 fi nding plausible matches between two patterns that di ffer 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 specifi c 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 fi nd plausible matches if the patterns diff er much, partial pattern matching
    • but slower than global matching

number of matching pairs with the query image


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Just another site

Jing's Blog

Just another site

Start from here......







Just another site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision


Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness



Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: