Pattern Matching Example Algorithm
Source File: matchdemo.c

This file describes the algorithm contained in the find() function of the
pattern matching demo program matchdemo.c.

The demonstration program matchdemo.c uses a combination of two methods for
pattern matching.  First, a block matching approach is used to determine which
region of the main image is most likely to correspond to the pattern image.
Then, a detailed search is performed around this region in an attempt to locate
the precise location of the pattern within the main image.  Limiting the
computationally intensive detailed search to a specific region of the main
image provides a significant saving in computation time.  A complete
description of this block matching/detailed search algorithm follows.

In the following description the main image is referred to as the "text" and
the pattern image as the "pattern".  By convention, we use the symbol n to
denote the size of the text and n to denote the size of the pattern.  When
working in two-dimensions, n is the width of the text image in pixels, and m is
the width of the pattern image.  For simplicity, we assume that both the
pattern and text are square, so the size of the text is n by n and the size of
the pattern is m by m.

To start with, both the text and pattern are divided into blocks (8 pixels
wide by default).  For each block in the text, the average of all pixels within
that block is computed.  This produces a smaller array containing text block
averages.  To smoothen the block matching, a second array containing blended
text block averages is then computed.  This computes the average of each text
block and three of its adjacent blocks.  Similar arrays of pattern block
averages and blended pattern block averages are also computed.  The remainder
of the algorithm works with these blended block averages, which we will simply
refer to as "block values" or "block colours" from this point forward.

Each text block has a block value and a pair of co-ordinates specifying its
location within the 2-dimensional array of text block values.  For each block
of text, a structure storing this information is created.  These strucutres are
placed in a 1-dimensional an array cblock[] representing all blocks of the
text.  This array is then sorted according to each structure's block value
(which can be thought of as a colour value).  Consequently, any blocks with the
same colour occupy the same region of the cblock[] array.  The minimum and
maximum index of this range is held in a structure corresponding to a
particular colour value.  Overall, an array crange[] of structures indexed by
colour is assembled, such that crange[c].min and crange[c].max specifies that
array entires cblock[crange[c].min ... crange[c].max] correspond to text blocks
of colour value c.  If there are no blocks for colour c, then this is indicated
by setting crange[c].min and crange[c].max to -1.

The core part of the block matching algorithm makes use of the crange[] and
cblock[] arrays to score regions (i.e. blocks) of the text image according to
how close these correspond with the pattern.  The scores assigned for each
block within the text image are accumulated in a two-dimensional array
score[][].  All entries of score are initially zero.  The scoring process works
by considering each block (i,j) of the pattern.  Suppose that pattern block
(i,j) has colour c.  Then any text block with colour c corresponds to a
potential placement for the pattern (at least for matching the colour of
pattern block (i,j)).  Matching block (i,j) in the pattern with a block (k,l)
in the text implies that the top left corner of the pattern lies at block
(k-i,l-j) in the text.  This potential pattern placement can be noted by
increasing the value score[k-i][l-j].  Those text blocks that match a colour c
are easily found by consulting the array entry crange[c] to get the min and max
indexes into the cblock[] array.  Thus, for every pattern block the algorithm
accumulates scores in the score[][] array based on the location of text blocks
with a matching colour.  To detect near matches better, the algorithm also
matches blocks with similar colours (within some bandwidth of the original
colours).  Further away colours result is a smaller addition to the
corresponding placement's score.  After accumulating scores based on the colour
of each pattern block, the maximum entry in the score[][] array indicates the
best matching pattern placement.

Block matching provides a rough match (by block) for the placement of the
pattern within the text.  To obtain a more precise match, the pixel details of
the pattern and text must be compared.  This is more computationally expensive
compared to block matching.  Fortunately, we can reduce the effort needed by
confining our search to a small region of text around the rough pattern
placement obtained by block matching.  Typically, one block width either side
of the rough patter placement is good enough.

Detailed search is performed by considering every possible pattern placement
and computing the relative error between the text and pattern pixels.  The
placement with minimum error corresponds to the best possible match between the
pattern and the text.  For each pattern placement there are m by m pairs of
text and pattern pixels to compare.  To speed this process up, we may first
filter out bad matches by comparing only a portion of the total pattern to the
text.  In this way, we can then perform a full detailed match only for those
matches that had the smallest amount of error.