Logo Recognition

3

Review of shape recognition techniques

CONTENTS

3.1 2D shape recognition ...................................................... 29

3.1.1 Shape representation .............................................. 30

3.1.1.1 Internal scalar methods .................................. 30

3.1.1.2 External scalar methods ................................. 32

3.1.1.3 Internal space domain methods ......................... 33

3.1.1.4 External space domain methods ......................... 33

3.1.1.5 Summary ................................................. 35

3.1.2 Shape recognition approaches ..................................... 35

3.1.2.1 Statistical approach ...................................... 35

3.1.2.2 Syntactic/structural approach ........................... 36

3.1.2.3 Template matching approach ............................ 39

3.1.2.4 Neural network approach ................................ 39

3.1.2.5 Hybrid approach ......................................... 40

3.1.2.6 Summary ................................................. 41

3.2 Logo recognition .......................................................... 42

3.2.1 Statistical approach ............................................... 42

3.2.2 Syntactic/structural approach .................................... 43

3.2.3 Neural network .................................................... 43

3.2.4 Hybrid approach .................................................. 44

3.3 Polygonal approximation .................................................. 47

3.4 Indexing ................................................................... 48

3.5 Matching .................................................................. 48

3.5.1 Distance measure .................................................. 49

3.5.2 Hausdorff distance ................................................. 50

3.6 Summary .................................................................. 51

The focus of this work is on 2D shape recognition. Other related areas of

interest are logo recognition, polygonal approximation, indexing and distance

measure. This chapter reviews the related works in these areas.

3.1 2D shape recognition

Shape recognition is an easy task for humans, but it is still quite difficult for

computers. After an object is rotated, translated and distorted, shape recog-

nition becomes more and more complicated. It is a challenge for researchers

29

30 Logo Recognition: Theory and Practice

[125, 211, 39, 104, 78, 112] to find a simple, less time consuming and highly

accurate method for shape recognition. Most researchers have judged their

proposals for shape recognition with the criteria described in Chapter 1. Gen-

erally speaking, to finish a recognition task, a shape is first represented by a

particular method, and then the matching procedure is applied.

3.1.1 Shape representation

Shape is a concept which is widely understood yet difficult to define. A shape

representation is a language for describing shape or some aspects of shape. It

includes a set of shape descriptors, and a mapping between shape descriptors

and shapes.

Shape descriptors may be classified as being either internal or external de-

scriptors depending on whether they code the boundary of a shape (external

descriptors) or the area within the boundary (internal descriptors). Descrip-

tors may also be classified as being either scalar transform or space domain.

Scalar transform methods generate shape descriptors which are mathematical

summations of the shape whereas space domain techniques comprise descrip-

tors which express the structural and relational properties of the shape. These

descriptors are reviewed with respect to scalar or space domain and internal

or external types in the following.

3.1.1.1 Internal scalar methods

Internal scalar methods use mathematical properties derived from the area

within a complete shape contour.

Moments of area. The standard 2D moment, m(u, v), of an image func-

tion, f(x, y), is defined as

m(u, v)=



∞

−∞



∞

−∞

f(x, y)x

u

y

v

dxdy (3.1)

The use of moments for shape description was initiated by Hu [87]. He proved

that moment-based shape description is information-preserving. Sardana et

al. [178] presented an efficient shape recognition method based on moment. In

their scheme, a set of circles is drawn around the centroid to map the area of

the shape into a set of concentric rings. The shape is then described in terms

of the area occupied with each ring. These area values form the n numerical

features of a shape. These features are then normalized with respect to the size

of the shape to achieve size invariance. The major advantage of this method

is that it is independent of rotation and scaling of shapes. Moments [220, 178]

have been used successfully as a technique for describing simple shapes but

they tend to fail for more complicated, occluded or distorted objects.

Morphological methods. Mathematical morphology has evolved as a

useful tool for various image processing applications. It is suitable for shape-

related processing since morphological operations are directly related to the