Syntactic pattern recognition
Encyclopedia
Syntactic pattern recognition or structural pattern recognition is a form of pattern recognition
, in which each object can be represented by a variable-cardinality set of symbolic, nominal features. This allows for representing pattern structures, taking into account more complex interrelationships between attributes than is possible in the case of flat, numerical feature vector
s of fixed dimensionality, that are used in statistical classification.
Syntactic pattern recognition can be used instead of statistical pattern recognition if there is clear structure in the patterns. One way to present such structure is by means of a strings
of symbols from a formal language
. In this case the differences in the structures of the classes are encoded as different grammars
.
An example of this would be diagnosis of the heart
with ECG
measurements. ECG waveform
s can be approximated with diagonal and vertical line segments. If normal and unhealthy waveforms can be described as formal grammars, measured ECG signal can be classified as healthy or unhealthy by first describing it in term of the basic line segments and then trying to parse the descriptions according to the grammars. Another example is tessellation
of tiling patterns.
A second way to represent relations are graphs
, where nodes are connected if corresponding subpatterns are related. An item can be labeled as belonging to a class if its graph representation is isomorphic with prototype graphs of the class.
Typically, patterns are constructed from simpler sub patterns in a hierarchical fashion. This helps in dividing the recognition task into easier subtask of first identifying sub patterns and only then the actual patterns.
Structural methods provide description of items, which may useful on its own right. For example, syntactic pattern recognition can be used to find out what object are present in an image. Furthermore, structural methods are strong in finding a correspondence mapping between two images of an object. Under natural conditions, corresponding features will be in different positions and/or may be occluded in the two images, due to camera-attitude and perspective, as in face recognition. A graph-matching algorithm will yield the optimal correspondence.
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
, in which each object can be represented by a variable-cardinality set of symbolic, nominal features. This allows for representing pattern structures, taking into account more complex interrelationships between attributes than is possible in the case of flat, numerical feature vector
Feature vector
In pattern recognition and machine learning, a feature vector is an n-dimensional vector of numerical features that represent some object. Many algorithms in machine learning require a numerical representation of objects, since such representations facilitate processing andstatistical analysis...
s of fixed dimensionality, that are used in statistical classification.
Syntactic pattern recognition can be used instead of statistical pattern recognition if there is clear structure in the patterns. One way to present such structure is by means of a strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
of symbols from a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. In this case the differences in the structures of the classes are encoded as different grammars
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
.
An example of this would be diagnosis of the heart
Heart
The heart is a myogenic muscular organ found in all animals with a circulatory system , that is responsible for pumping blood throughout the blood vessels by repeated, rhythmic contractions...
with ECG
Electrocardiogram
Electrocardiography is a transthoracic interpretation of the electrical activity of the heart over a period of time, as detected by electrodes attached to the outer surface of the skin and recorded by a device external to the body...
measurements. ECG waveform
Waveform
Waveform means the shape and form of a signal such as a wave moving in a physical medium or an abstract representation.In many cases the medium in which the wave is being propagated does not permit a direct visual image of the form. In these cases, the term 'waveform' refers to the shape of a graph...
s can be approximated with diagonal and vertical line segments. If normal and unhealthy waveforms can be described as formal grammars, measured ECG signal can be classified as healthy or unhealthy by first describing it in term of the basic line segments and then trying to parse the descriptions according to the grammars. Another example is tessellation
Tessellation
A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
of tiling patterns.
A second way to represent relations are graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, where nodes are connected if corresponding subpatterns are related. An item can be labeled as belonging to a class if its graph representation is isomorphic with prototype graphs of the class.
Typically, patterns are constructed from simpler sub patterns in a hierarchical fashion. This helps in dividing the recognition task into easier subtask of first identifying sub patterns and only then the actual patterns.
Structural methods provide description of items, which may useful on its own right. For example, syntactic pattern recognition can be used to find out what object are present in an image. Furthermore, structural methods are strong in finding a correspondence mapping between two images of an object. Under natural conditions, corresponding features will be in different positions and/or may be occluded in the two images, due to camera-attitude and perspective, as in face recognition. A graph-matching algorithm will yield the optimal correspondence.
See also
- Grammar inductionGrammar InductionGrammatical induction, also known as grammatical inference or syntactic pattern recognition, refers to the process in machine learning of learning a formal grammar from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects...
- String matching
- Hopcroft–Karp algorithm
- Structural information theoryStructural information theoryStructural information theory is a theory about human perception and in particular about perceptual organization: the way the human visual system organizes a raw visual stimulus into objects and object parts. SIT was initiated, in the 1960s, by Emanuel Leeuwenberg and has been developed further by...