Syntactic Pattern Recognition

  1. What is Syntactic pattern recognition

It is a form of pattern recognition, which objects can be represented by variable, cardinality set of symbolic, nominal features.In syntactic pattern recognition, objects can be described as labeled graph, tree, array, matrix, or attributed string. In the simplest case, recognition is a merely symbolic procedure based on a formal generative definition of languages. A set of production rules (defining a formal grammar) are applied to ascertain whether the object under examination belongs to a given language and the yes/no answer is used to predict the object class. While the most widely known theory on formal language is restricted to strings (for example, the theory commonly used for programming languages), researchers in the syntactic pattern recognition community more often use languages defined on graphical domains, i.e. labeled trees or labeled webs are used instead of strings. This is because graphs have a much richer description power. If the image is clearly visible and it has important structural features this method can be used in object recognition. This is an example of tree representation of a logo image

In this case the image was recursively decomposed into a tree whose nodes correspond to sub-objects and edges express the contained-in relation. For each sub-object, some local features are measured. In this example, shape, perimeter and area of each sub-object are local features attached to nodes.

Primitives:Primitives are the simplest sub pattern of a pattern, also known as symbols or terminals.

Pattern Decompose to similar sub patterns Decompose to similar sub patterns

Simplest sub pattern (primitive)

Relational structure:Relationship between primitives

Applications:

  • English and chines character recognition
  • Fingerprint recognition
  • Speech recognition
  • Remote sensing data analysis

Chain code

  • This is a form of representing shape of an object
  • Separately encode each connected component of an image by identifying the object in a form of symbol
  • Start from a point of the boundary of the object to be represented, encoder moves along the boundary of the object by using 4-connected or 8-connected neighborhood detection methods, continue until it reach the starting point.
  • So a chain code can be representing as a string of numbers.

4-directional chain code: 0033333323221211101101

8-directional chain code: 076666553321212

  • We have two problems with the chain codes, dependent on the start point and dependent on the orientation.(If we can obtain a unique chain code for each shape, which is invariant to translation, rotation and scaling we can use it in similarity checking of objects and shape representation.)
  • Solution is
  • Normalized codes
  • Normalization for rotation-first difference

Counting (counterclockwise) the number of direction changes that separate two adjacent element of the code

  • Normalization for start point-shape number

The first difference of smallest magnitude

  • Normalization for size-Multi-scaling resampling

◦Example:

The 4-direction chain code: 10103322

The first difference of the code: 33133030

3: (1-2) mod 4 = 3

3: (0-1) mod 4 = 3

1: (1-0) mod 4 = 1

dk=ck-ck-1 (mod 4) for 4-directional chain codes

dk=ck-ck-1 (mod 8) for 8-directional chain codes

The first difference of smallest magnitude of the code(shape no):03033133

(Arrange the digits of the code, so that it has the smallest magnitude without interchanging digits)

  • Use in content based image retrieval, to represent shapes which are invariant to rotation, scale and translation.
  • Disadvantages-Small variation in counter gives different codes.(Matching chain code is slightly noisy version of the same object can be very different.)