# 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.

- Example 1 - two overlapping hexagonal
tessellations.

- Example 2 - two overlapping hexagonal
tessellations.

- Example 3 - three overlapping hexagonal
tessellations.

- Example 4 - one hexagonal tessellation
overlapping with three squares.

- Example 5 - one hexagonal tessellation
overlapping with five squares.

- Example 6 - one hexagonal tessellation
overlapping a chain and a square.

- Example 7 - one hexagonal tessellation
overlapping with six squares.

- Example 8 - one cross (showing how the
context-free constraint is enforced using subsymbols).

- Example 9 - two overlapping crosses.

- Example 10 - three overlapping crosses.

- Example 11 - a cross overlapping with a
hexagonal tessellation.

- Example 12 - two crosses overlapping with a
hexagonal tessellation.

- Example 13 - two crosses overlapping with a
hexagonal tessellation.

- Example 14 - one cross overlapping with two
hexagonal tessellations.

- Example 15 - two crosses overlapping with two
hexagonal tessellations.

- Example 16 - an Hnest, nested to depth 4.

- Example 17 - two overlapping Hnests.

- Example 18 - two Hnests and two crosses, all
overlapping.

Peter Fletcher.

Up to home page