MAP SYMBOL RECOGNITION USING DIRECTED HAUSDORFF
DISTANCE AND A NEURAL NETWORK CLASSIFIER
Eric Reiher*, Fady Said**, Ying Li*, and Ching Suen**
* Centre de recherche informatique de Montréal
1801 McGill College Avenue, Suite 800
Montréal, Québec, Canada, H3A 2N4
** Centre for Pattern Recognition and Machine Intelligence
1550 de Maisonneuve Blvd West, Suite GM-606
Montréal, Québec, Canada, H3G 1M8
Commission III, Theory and Algorithms
KEY WORDS: GIS, Cartography, Vision, Neural Networks, Pattern Recognition
ABSTRACT
A method for map symbol recognition is presented in this paper. Our objective in developing this recognition method is
“to make recognition efficient, robust and near perfect for handling very large maps with many symbols of different scales
and orientations. Our method first utilizes the directed Hausdorff distance as a measure of similarity for selecting possi-
ble candidates of user defined models of symbols. This selection will collect as many candidates as possible, in order not
to miss any symbols. Neural networks are then utilized to eliminate the false positives among those candidates. Imple-
mentation details and experiment results are presented.
1. INTRODUCTION
Currently, we are undertaking a pre-competitive research
project on converting paper maps to electronic format. A
potential application of our research result is to integrate
utility maps, hand drawn several decades ago, into current
geographic information systems (GIS). Integrating paper
maps into a GIS is a problem of central importance as
GIS become more widely used for representing spatial
data. On paper maps, graphical symbols are used to indi-
cate the location of various sites. Currently there are
research projects and commercial products on vectorizing
map images. However, it remains a research objective to
automatically locate and recognize user defined symbols,
given by a model, from images of scanned maps without
assumptions and constraints about the symbols. It is not a
trivial task because the symbols in the image can be
touching, overlapping, of different scales and orientations
from the model, or modified by noise such as that intro-
duced during scanning (Fig. 1). The task becomes even
harder when near perfect recognition is required with a
speed acceptable for commercial applications. The con-
version process consists of scanning the maps, extracting
all the information present in each map and storing it in a
fashion that it can be accessed and manipulated by target
applications. The quality and cost of this convention pro-
cess are determining factors for a company's decision
regarding the adoption of the process in its commercial
practice. This process is continuous as new areas or new
maps need to be incorporated in the GIS applications.
* This research is partially sponsered by M3i Systems
Inc, Longueuil, Québec, Canada.
680
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
Thus efficiency is also an important determining factor.
This paper presents a recognition algorithm based on
Hausdorff distance and neural networks, where our main
contribution is to make the recognition efficient and
robust for handling very large maps and many symbols of
different scales and orientations. Section 2 reviews previ-
ous work on symbol recognition. Section 3 outlines our
approach. Section 4 explains implementation details. Sec-
tion 5 presents some experimental results and Section 6
concludes.
2. REVIEW OF PREVIOUS WORK
Our decision of using the Hausdorff distance for symbol
recognition is based on our substantial survey of previous
work on symbol recognition and shape detection in gen-
eral. Among more than a dozen methods studied, the
Hausdorff approach stands out as the most suitable for
our objectives in terms of robustness, efficiency, correct-
ness and scope. This section briefly reviews the previous
work related to symbol recognition. The next section
introduces Hausdorff distance and our approach.
The generalized Hough transform is probably one of
the oldest and best known methods to detect any arbitrary
shape, of any orientation in an image (Ballard, 1981).
Although this approach could be used to perform map
symbol recognition, it seldom is because it usually gener-
ates a lot of false positives when applied to complex
images to detect complex shapes (Grimson, 1986). The
computation can also become quite expensive, as its com-
plexity and memory requirements increase with the com-
plexity of the shapes, and their orientation. The memory
requ
inva
Wu
in ai
The
tion
whi
UN]
(An
Reis
198
Sinc
inst:
repr
Teco
cally
acti
sym
solic
the
with
(Sar
ize:
Thei
men
For :
uses
ture:
(Lev
enta
to ir
othe
ture
becc
use €
tatio
tried
far. '
shap
imag
with
the «
meth
smal
usin;
prob
Fletc
simp
angle
1990
Base
reco
