Page 259 -

6.1 Pattern Primitives 247

A particularly useful description can be obtained from line segments derived by
the application of the Hough transform, a transformation that maps a straight line y
= ax+b =p cos6' into a point in the (a, b) plane or the (p,@ plane. The straight line
Hough transform can also be applied to the description of arbitrary curves. Details
on how to use this technique can be found in Pao and Li (1992).

Regions

The segmentation of an image into distinct regions is often used as a means of
obtaining structural descriptions of images, e.g., based on proximity relations of
region centroids and using labels related to the image properties of the regions such
as perimeter, area, colour, light intensity and texture. This approach is used, for
instance, in image registration applications, such as the structural matching of
satellite images (see e.g., Ton and Jain, 1989), which we discuss in section 6.4.2.
Region primitives such as centroids and corners can also be obtained from
binary images by using morphologic operators (see e.g., Shapiro, 1988).

6.2 Structural Representations

The representation of a pattern in terms of its constituent elements can be done in
many ways. Here we will describe the most common ways of structural
representation.

6.2.1 Strings

A string is an ordered sequence of symbols, each symbol representing a primitive.
We denote by S the set of all possible strings that can be built with the elements of
a symbol set T. A string x is then a sequence of symbols of T represented as:

The number of symbols, m, is the string length, denoted 1x1. The string with no
symbols, m=O, is called the null string and denoted A.
We define the concatenation of strings x = ala 2...a, and y = b,b *... b, with m
symbols and n symbols, respectively, and denote this operation as x + y, yielding
the string with m+n symbols:

z = x + y = alaz ... a,, b,bz.., b, . (6-3)

Note that the null string is the neutral element for the concatenation: