Logo Recognition

5

Polygonal approximation

CONTENTS

5.1 Feature point detection overview ......................................... 60

5.2 Dynamic two-strip algorithm ............................................. 63

5.3 The proposed method ..................................................... 64

5.4 Results .................................................................... 73

5.5 Comparison with other methods .......................................... 78

5.6 Summary .................................................................. 79

Polygonal approximation is a process to approximate an arbitrary curve with

a sequence of straight lines which retain the overall shape of the original curve.

Such a process is useful in shape representation [23, 109, 140, 175, 236] or in

data reduction [168, 202]. Attneave [6] suggested that corners or high curva-

ture points of a curve provide important information during the recognition

process in the human visual system. When people look at an image, they

first capture such information. Such points (i.e., feature points) of a planar

curve capture crucial shape information and can potentially be detected con-

sistently. Based on this observation, one can argue that a planar curve can

be represented by another planar curve and still be recognized to have the

same shape by a human observer if the feature points remain invariant [117].

Thus the polygonal approximation can be formulated as a feature point detec-

tion problem. The approximated curve is one with the detected feature points

connected by straight line segments [82, 229]. In the logo recognition system,

feature point detection is one of the important modules. It is applied to the

contours of logos and extracts a set of consistent feature points of a contour.

Data reduction can be achieved by using line segments to connect these points

to represent shape efficiently. Computation time can thus be saved. In addi-

tion, consistent feature points can be used to aid the normalization process

which affects the recognition greatly.

A new feature point detection scheme is proposed here based on the dy-

namic two-strip algorithm (Dyn2S) [117]. In the following sections, Dyn2S will

be described and analyzed, and then the new scheme will be discussed.

59

60 Logo Recognition: Theory and Practice

5.1 Feature point detection overview

Feature point detection plays a crucial role in shape representation and object

recognition. It can be classified into two major categories: outline-based meth-

ods and gray-level methods. Outline-based methods detect feature points (i.e.,

corners) on the outlines of objects. Gray-level methods directly work on gray-

level images [11, 28, 43, 165, 232]. Feature points in gray-level images are

characterized by using the second derivatives of the image luminance func-

tion. Although this method does not require pre-segmented image contours,

it is sensitive to the noise amplification effects of the second-derivative op-

erators. The gray-level feature point detection algorithm can be divided into

two groups. The template based method [165] detects the similarity between

a given template of a specific angle for each image sub-window. Because mul-

tiple orientation templates are used, the technique is computationally expen-

sive. The gradient based method [43], on the other hand, relies on measuring

the curvature of an edge that passes through a neighborhood. Gradient based

methods are more likely to respond to noise than their contour-based coun-

terparts and often perform quite poorly [131].

In this study, our emphasis is on the outline-based approach to feature

point detection because it is easy to implement and has been successfully

used in many vision systems. A vision system, working with structural in-

formation, can capture the outline of an object, from which one can get its

shape information. A key requirement to deal with shapes for object recogni-

tion purposes is the ability to characterize the outline. This requirement leads

to the importance of the determination of useful and informative features

from the outline. These efficient features, besides being generally sufficient for

object discrimination, should also allow us to successfully describe an object

[217]. Object recognition through contour or outline can result in enormous

data reduction, and a further data reduction can be obtained by extracting

and connecting sequential feature points from the outline of the object. This

kindofmethodhasattractedwideinterestandvariousmethodshavebeen

presented [4, 10, 63, 142, 176, 201, 235].

A contour is a list of connected points representing the outline of an image.

It can be represented by a sequence of integer coordinate points as p

1

(x

1

,y

1

),

p

2

(x

2

,y

2

), ..., p

n

(x

n

,y

n

), where p

i

is connected to p

(i+1)

,1≤i≤n.Wehave

|x

i

−x

i+1

| and |y

i

−y

i+1

| both less than or equal to one but not both equal to

zero. A more compact way to represent a contour is by its chain code. Given

any pair of consecutive points on the curve, (x

i

,y

i

)and(x

i+1

,y

i+1

), there are

only eight possible locations for (x

i+1

,y

i+1

)relativeto(x

i

,y

i

), such that a

digitized curve can be represented by a sequence of direction changes. Several

authors [4, 5, 110] proposed their own feature point detection procedures for

chain coded curves. A review of chain code based methods can be found in

[128]. They implemented six existing feature point detection schemes on the