alerts can occur when using a threshold large enough not
to miss any symbols. We have added a second threshold in
order to lower the number of false alerts. The percentage
of directly matching pixels from the model on the image
is also computed. A threshold on this percentage helps to
reject in some cases up to 75% of false matches.
The Hausdorff distance is not sensitive to symbols
touching or overlapping each other. It can thus naturally
be used to first locate possible candidates. As an extra ver-
ification step, any feature can be computed for recogni-
tion. In our approach, we have chosen to use the
Hausdorff distance in conjunction with a multi-layer neu-
ral network for recognition. The found candidates are
passed through the network for user-guided training or for
recognition once trained.
4. IMPLEMENTATION
‘4,1 Hausdorff distance
The Hausdorff distance is calculated for every symbol
according to Huttenlocher’s approach (Huttenlocher,
1993). Optimizations to prune the search area are
described. For example, suppose the Hausdorff distance
between a symbol and an image at a specific point (x, y) 1s
(d). When this distance is greater than the symbol’s
threshold (t), then a region of size (d - t) can be pruned
(not searched further) surrounding the point (x, y). This is
due to the fact that the Hausdorff distance cannot decrease
more rapidly than by 1. The only difference in our imple-
mentation, is that we start by looking for symbols at the
center of the image. We then proceed in the image in a
dichotomous way, searching in the middle of yet
unsearched region. Huttenlocher starts the search at the
top left corner and proceeds left to right, top to bottom. So
he can only prune smaller regions. Our method has con-
tributed to a 20% decrease in processing time.
Usually, when a match is found, the Hausdorff matrix
will contain not one but a whole region of positions that
are below the user’s threshold. For example, a small filled
circle can be placed at various locations inside a larger
one. Our algorithm will choose the position where there is
a maximum number of pixels matching, while surround-
ing matches will be eliminated. When a candidate is
found, its position, scale and orientation are passed to the
neural network.
4.2 Neural network classifiers
A set of neural network classifiers are used to validate or
reject the candidates found by the Hausdorff method. One
network per symbol is used for training and validation.
The regions of interest to be processed are all presented in
the same orientation and scaled down to a 20x20 matrix
that constitutes the input layer of the network. There is
only one hidden layer that is fully connected to the input
and to the output layer. The signal produced by the output
682
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
neuron is considered to be a measure of confidence that
the candidate presented to the network is a symbol or
whether it is just a false positive. The output is a floating
point number between 0 and 1. The closer it is to 1, the
more confident we are that the candidate is a symbol.
. The networks are trained using the error backpropa-
gation algorithm (Rumelhart, 1986, LeCun, 1990 and
Krzyzak, 1990) with a momentum term and an adaptive
learning rate, to which, we have added our own modifica-
tions (Said, 1995). While training the different networks
over their respective symbols, each network, as it con-
verges, chooses its own optimal parametric values (learn-
ing rate, momentum rate, and the sigmoidal activation
function's parameter) and the number of hidden neurons,
within a user specified range. While training, the error
function slope is examined to decide whether to decrease
or increase the current number of the hidden neurons, and
change the parameter' values. This technique helps in not
falling into a local minima along the error function's
graph, however, on the average, it results in more itera-
tions (epoch).
Training the system to recognize a new symbol
involves two steps. First, the user is asked to build a train-
ing set for the symbol, with the assistance of the system.
Instances are located by the Hausdorff method, and the
user flags each candidate as being valid or not. Second,
the network attached to this newly created symbol is
trained to differentiate between the symbol and its false
positives. The network is then ready to be used in recall
mode for automatic recognition.
4.3 Advantages of our approach
Combining the Hausdorff distance with neural networks
has several advantages:
« The Hausdorff distance performs segmentation. It
has no problem when symbols are touching or
overlapping. It also rotates all symbols to the same
orientation for easier use by the neural networks.
« The Hausdorff distance acts as a pre-filter. Not all
symbols in a map will be passed to a symbol's neu-
ral network, only the ones that are close enough.
This reduces the training set and augments accu-
racy.
* The advantage of using one neural net per symbol
is to have independent learning and recognition.
When a new symbol is added, training on others is
not affected.
4.4 Selection
The recognition of each symbol is performed indepen-
dently. Multiple candidates could thus appear at the same
location. À decision must be taken as to which symbol is
the best candidate.
All the found symbols are first sorted, the ones with
the most matching pixels appearing first. Then the sym-
bols are removed from the image one by one. However,
befor
rema
excel
list ©
card:
locat
most
rare
adjus
used
tO pri
resul
some
very
wher
The
badly
ing n
neur:z
denc:
great
high
to acc
misse
reflec
rectly
imag
not p
traini
7
netwe
didat
that t
symb
]
netw
candi
dence
ing t
almo:
more
is the
to rer
bols.
neces
filled
the tr:
lem.
F
ure 2
duced
nized,
