Logo Recognition

7

Logo matching

CONTENTS

7.1 Hausdorff distance ........................................................ 98

7.2 Modified 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 five 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 influence 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 affine 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 modified Line Segment Hausdorff 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 modified Line Segment

Hausdorff 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 Hausdorff distance

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

ing. It is a distance defined 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 Hausdorff distance can be calculated without explicit

point correspondence. Huttenlocher et al. [88] argued that the Hausdorff 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 Hausdorff 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 Hausdorff

distance is defined 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 Hausdorff distance from M to N. It identifies the point m

i

∈ M that

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

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

the Hausdorff distance is d,theneverypointofM must be within a distance

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

distance to compare curves. A method using the Hausdorff distance for visually

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

Dubuisson and Jain [49] investigated 24 forms of different Hausdorff dis-

tance measures and indicated that a Modified Hausdorff Distance (MHD)

measure had the best performance. The directed MHD is defined as

h(M,N)=

1

p



m

i

∈M

min

n

j

∈N

m

i

− n

j

 (7.3)

where p isthenumberofpointsinM. The definition of the undirected MHD

is the same as (7.1).

The Hausdorff distance defined 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