Syntactic Pattern Recognition

Recognising Geometric Patterns

Here are some examples of the recognition of highly structured patterns in the presence of noise. The patterns involved are hexagonal tessellations, squares, chains and crosses.

A hexagonal tessellation consists of any number of hexagons, at any orientation, size and position. The hexagons are of roughly equal size, the angles between their edges are approximately 120 degrees, and their edges are roughly line segments of approximately equal length.

A chain consists of any number of squares, each square linked to its neighbours by a line. At each end of the chain is a line.

A cross consists of a central square with four long 'trunks' radiating out from it, each trunk having one or more small 'twigs'. Each trunk must have the same number of twigs - the grammar must enforce this 'context-free' constraint.

An Hnest consists of an 'H' shape with two smaller 'H's nested inside it, each of which has two smaller 'H's nested inside it, and so on, to an arbitrary finite depth.

In the test runs I present an image containing several overlapping patterns and I ask the program to recognise all the patterns present. The program recognises the patterns using a type of context-free graph grammar.

Peter Fletcher.
Up to home page