## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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
ﬁrst 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 eﬃciently. Computation time can thus be saved. In addi-
tion, consistent feature points can be used to aid the normalization process
which aﬀects 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 classiﬁed 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 ampliﬁcation eﬀects 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 speciﬁc 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 eﬃcient features, besides being generally suﬃcient 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)
,1in.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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required