n method is
erent scales
cting possi-
in order not
ites. Imple-
ng factor.
m based on
re our main
ficient and
symbols of
'jews previ-
yutlines our
letails. Sec-
d Section 6
)RK
for symbol
of previous
ion in gen-
studied, the
suitable for
cy, correct-
he previous
ext section
:h.
ably one of
ny arbitrary
ard, 1981).
rform map
1ally gener-
to complex
1986). The
as its com-
th the com-
he memory
required can quickly become unmanageable.
A lot of existing symbol recognition systems use
invarlant features for shape recognition. In (Wu, 1986),
Wu and Stark present an algorithm to recognize an object
in an image regardless of the object’s size and orientation.
They mainly use two features: a circular harmonic func-
tion that is rotation invariant and the Mellin transform
which is scale invariant. Other popular features are the
UNL Fourier features (Rauber, 1994), Wavelet transform
(Antonini, 1992), moment invariants (Reeves, 1988 and
Reiss, 1991) and Fourier descriptors (Jun, 1986 and Lin,
1987).
A set of features is usually used to classify symbols.
Since the instances of each symbol may vary, several
instances of each symbol are required in order to build a
representative training set that will produce reasonable
recognition rates. This training set is constructed dynami-
cally with the help of the user. At first, the user will inter-
actively correct the recognition when necessary. All the
symbols identified and corrected by the user will help con-
solidate the classification. Once the user is satisfied with
the classification, the system can then run stand-alone
without user interaction.
A good example is the system by Samet and Soffer
(Samet, 1994). It uses the (user-located) legend to initial-
ize a table of models to be found in the rest of the image.
Then the system divides an image into its constituent ele-
ments using a connected component labeling algorithm.
For each region a set of features is computed. The system
uses global and local shape descriptors identified as fea-
tures that best discriminate between geographic symbols
(Levine, 1982). These features are invariant to scale, ori-
entation and translation.
In general, however, a feature based approach is hard
to implement when symbols can overlap or touch each
other. Segmentation must then be performed before fea-
ture calculation and the resulting problems can rapidly
become very complex. In (Gorman, 1988), Gorman et al.
use a dynamic programming method to attack the segmen-
tation problem. Different segmentation possibilities are
tried depending on what is most likely to be recognized so
far. This method is mostly used for recognizing complex
shapes. For example, if one wishes to distinguish an
image of an airplane from that of a train and only a wing
with a reactor is showing, the system will easily recognize
the object as an airplane. However, it is not clear if the
method would yield good results if used to recognize very
small and similar symbols.
Several other authors have suggested approaches
using almost only heuristics. Kasturi has worked on the
problem of separating text from graphics (Kasturi, 1986,
Fletcher, 1988 and Kasturi, 1990) and also on locating
simple symbols consisting mainly of small loops like rect-
angles, circles, etc.
Yu et al. (Yu, 1994) and Shimotsujia (Shimotsuji,
1990) rely on simple heuristics to perform segmentation.
Based on features, shapes like lines, circles and arcs are
recognized and grouped. A simple matcher is used to per-
681
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
form recognition. The user can input any type of symbols.
Okazaki er al. (Okazaki, 1988) described a complete
system for electric circuit symbol recognition. Most sym-
bols in an electrical circuit diagram contain at least a
closed loop. An interesting feature about this system is its
hybrid approach. It first computes a set of features to iso-
late loops of interest. Then it uses another set of features
to recognize the exact symbol. This recognition is medi-
ated with a pattern matching attempt on the same symbol.
The two recognition schema collaborate in order to find
the right symbol.
Heuristic methods have several problems. First, they
are not general. They can be used to find only a small set
of symbols. Their major disadvantage is that they are very
sensitive to noise. If a symbol is incomplete, blurred,
touching or overlapping another one, it might be missed.
3. OUR APPROACH
The Hausdorff distance measures the degree of mismatch
between two sets of points by measuring the distance of a
point of one set that is farthest away from any point of the
other, and vice versa. Formally, the directed Hausdorff
distance h between a model M and an image / at a specific
point in the image is:
max ( min :
hM, I = [' (distance (m, 59) (1)
me M\iel
The Hausdorff distance H is defined as:
HM, I) 2 max(h((M,D,h(1, M))) (2)
This distance can be used to determine the degree of mis-
match between two objects that are superimposed on one
another.
One of the most interesting properties of the Haus-
dorff distance is that it obeys metric properties. The func-
tion is positive everywhere and has the properties of
identity, symmetry and triangle inequality. These proper-
ties correspond to our intuitive notions of shape resem-
blance, namely, that a shape is identical only to itself (and
not one having identical features), the order of compari-
son of two shapes does not matter, and two shapes that are
highly dissimilar cannot both be similar to some third
shape. This final property (the triangle inequality) is par-
ticularly important in pattern matching applications in
which several stored model shapes are compared with an
unknown shape. Thus, two highly dissimilar models can-
not both be similar to an unknown symbol.
However, the distance threshold alone is not good
enough to discriminate between good and bad matches.
When using a small (tight) distance threshold, a lot of
poorly drawn symbols can be missed. This is undesirable
in some applications. On the other hand, a lot of false
