Content-Based Image Retrieval with Cellular Automata - Cellular Automata in Image Processing and Geometry - page 142

search through a database of images to retrieve all other pictures of similar-looking
birds, in order to identify the bird in the original picture. Note that these searches
use the image itself and not the text name of the picture file to do the search—hence
the term content-based . Although trivial for humans, this process is algorithmically
significantly more difficult than text-based searches. The focus in this chapter will
be on similarity searches based on image properties such as colour, shape or tex-
ture [18].
In order to find similar-looking images, an image is typically separated into its
major regions—this process is known as segmentation. For example, a beach scene
might be separated into the sand, the sky, the sun, and a palm tree. Common ap-
proaches here are that of k -means clustering and normalised cuts [25]. Then, for
each region found in the segmentation process, the qualifying characteristics of the
image must be defined. For example, a dog has a body with four legs, and a head
with two ears. These characteristics are described mathematically (in terms of shape,
size, orientation, and so on) in a so-called feature vector (or set of feature vectors),
known as the signature or descriptor of the image. 1 All the images in the database
also have their pre-calculated feature vectors, so that the matching problem becomes
one of finding the distance between the feature vector of the input image, and the
feature vector of each of the images in the database. The reader must note that it
is important that the images in the database are mathematically described to be in-
variant to rotation, scaling, translation and reflection [34] (affine transformations).
Moreover, the image descriptors must be as compact as possible, since typical image
databases are huge [5]. The process of establishing a feature vector for an image is
known as feature analysis. In this chapter, the focus is on the use of cellular automata
for feature analysis.
In feature analysis, it is standard practice to first clean up the given image by
performing noise reduction. Then, in order to isolate the distinguishing shapes in
the image, edge detection is performed. Lastly, given the edges, one can perform
shape recognition. Colours and texture are also analysed, to aid in these procedures.
Colours are typically analysed with histogram-based techniques, while texture anal-
ysis is often based on wavelet transforms [17]. Shapes may be described by finding
the center point of a closed edge, and describing the outline of the shape relative to
this center point. Template matching can also be used to find similar shapes. This
involves matching a template picture of a certain shape, such as a circle, against the
given image. Better results are achieved if two or more components are combined in
the search, so that the matching takes place for example on both shape and texture,
or both texture and colour.
The actual image matching process involves a similarity comparison between the
features of the given image, and the features of the images in the database. This is
achieved by comparing the distance between their feature vectors. Typical distances
used are the Euclidean, the Hausdorff, and the Earth Mover's distance [33]. The
reader should note that, due to the size of the typical image database, it is impractical
to do a linear search through the pre-computed feature vectors of the database. The

1

If the vectors are weighted, and the weights sum to one, the signature may also be consid-
ered as a discrete distribution.