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