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

Given the pixels comprising a shape, a mathematical description has to be found
that is independent of rotation, translation and scaling. Moreover, the descriptor
should preferably have low memory usage and time complexity, while still retaining
high accuracy and fast retrieval and comparison rates. For an overview, the reader
may consult a standard text such as [26]. For interest's sake, note that Lin et al.
used the so-called mountain climbing sequence (MCS) [22], while the Hu set of
moments [1] was used in [2].

8.4 Practical Case Study: Recognition of LEGO Bricks

An example of a CBIR system that exploits the use of CA throughout most of the
CBIR pipeline, is described in [2, 32]. This seemingly innocuous application re-
quires that a query image of a LEGO brick is matched in a large image database
of LEGO bricks, for identification purposes. All the images of the bricks are of a
single brick photographed on a background LEGO base. Bricks can be matched by
colour and shape, or just shape (see Fig. 8.4). The semantics of a brick is given by
its three-dimensional form, as well as the arrangement of the studs on the brick. For
example, in Fig. 8.4, bricks number 1, 11 and 12 all have four studs on top, but the
shapes of the bricks are all different (slice, circle and square), and the arrangement
of the studs on brick 1 is different from that of bricks 11 and 12. Hence, the three
bricks are semantically distinct. To contain the number of variations, the initial pro-
totype system catered only for 'standard' bricks without multicoloured stickers or
odd shapes without studs (see Fig. 8.4 for examples of nonstandard special bricks).
The feature extraction phase of this CBIR system requires five steps:

• Segmentation: the baseboard plays no role in the semantic definition of the brick,

and is removed from the image.

• Edge detection: the edges of the brick will be used to define its form.

• Stud identification: the positions of the studs must be found.

Fig. 8.3 Floodfilling a shape (from [32]). The original image (left), the extracted edges (top
right), and the flood-filled top shape of the brick (bottom right).