7

Logo matching

CONTENTS

7.1 Hausdorﬀ distance ........................................................ 98

7.2 Modiﬁed LHD (MLHD) ................................................... 100

7.3 Experimental results ...................................................... 105

7.3.1 Matching results ................................................... 107

7.3.2 Degradation analysis .............................................. 113

7.3.3 Results analysis with respect to the LHD and the MHD ......... 113

7.3.4 Discussion and comparison with other methods .................. 117

7.4 Summary .................................................................. 120

As stated in Chapter 3, there are ﬁve main shape recognition methods (i.e.,

statistical approach, syntactic/structural approach, template matching, neu-

ral network, hybrid method). However, not all methods are appropriate for

each type of shape and application, i.e., the method of choice depends on the

properties of the shape to be described and the particular application. The

presence of noise can also inﬂuence the choice of method. Since the structural

approach is based on the local shape features and robust to the noisy condi-

tion while template matching can achieve a high recognition rate, a hybrid of

structural and template matching can show strong potential for shape match-

ing. Sternby [193] presented a structurally based template matching method,

which utilizes the explicit structure of the samples to model the non-linear

global variations by a set of aﬃne transformations through a structural repa-

rameterization. Bruneli and Poggio [18] argued that successful object recog-

nition approaches may need to combine aspects of structural feature based

approaches with template matching methods. Based on these observations,

a hybrid method combining the structural approach and template matching,

i.e., the modiﬁed Line Segment Hausdorﬀ Distance (LHD), is presented for

logo matching in this study.

After the indexing process, the test logo is matched to all the likely mod-

els in a line-to-line matching manner. The matching is implemented as a dis-

similarity computation process. In this chapter, the modiﬁed Line Segment

Hausdorﬀ Distance (LHD) measure is proposed to match logos. The proposed

approach has better distinctive capability (especially for broken lines) than

the original LHD. Compared with other researches on logo recognition, this

approach has the advantage of incorporating structural and spatial informa-

tion to compute the dissimilarity between two sets of line segments rather than

97

98 Logo Recognition: Theory and Practice

two sets of points. The added information can conceptually provide more and

better distinctive capability for recognition.

7.1 Hausdorﬀ distance

The Hausdorﬀ distance is one of the commonly used measures for shape match-

ing. It is a distance deﬁned between two sets of points [173]. Unlike most shape

comparison methods that build a one-to-one correspondence between a model

and a test image, the Hausdorﬀ distance can be calculated without explicit

point correspondence. Huttenlocher et al. [88] argued that the Hausdorﬀ dis-

tance for shape matching is more tolerant to perturbations on the locations of

points than binary correlation techniques since it measures proximity rather

than exact superposition. Also, the Hausdorﬀ distance is simple in concept

and easy to implement.

GiventwosetsofpointsM = {m

1

, ..., m

p

} (representing a model in the

database) and N = {n

1

, ..., n

q

} (representing a test image), the Hausdorﬀ

distance is deﬁned as

H(M,N)=max(h(M, N),h(N,M)) (7.1)

where

h(M,N)= max

m

i

∈M

min

n

j

∈N

m

i

− n

j

(7.2)

and ·is some underlying distance function for comparing two points m

i

and n

j

(e.g., the L

2

or Euclidean norm). The function h(M,N) is called the

directed Hausdorﬀ distance from M to N. It identiﬁes the point m

i

∈ M that

is the farthest from its nearest neighbors in N. Thus, the Hausdorﬀ distance,

H(M,N), measures the degree of mismatch between two sets. Intuitively, if

the Hausdorﬀ distance is d,theneverypointofM must be within a distance

d of some point of N and vice versa. Belogay et al. [12] used the Hausdorﬀ

distance to compare curves. A method using the Hausdorﬀ distance for visually

locating an object in an image was developed in [172].

Dubuisson and Jain [49] investigated 24 forms of diﬀerent Hausdorﬀ dis-

tance measures and indicated that a Modiﬁed Hausdorﬀ Distance (MHD)

measure had the best performance. The directed MHD is deﬁned as

h(M,N)=

1

p

m

i

∈M

min

n

j

∈N

m

i

− n

j

(7.3)

where p isthenumberofpointsinM. The deﬁnition of the undirected MHD

is the same as (7.1).

The Hausdorﬀ distance deﬁned in (7.1) and (7.2) is very sensitive to outlier

points. A few outlier points, even only a single one, can perturb the distance

Start Free Trial

No credit card required