101
ng is to fit
:ing an ideal
pixels from
can then be
have proposed
can be found
iralick (1980)
; basis of a
a statistical
involves the
image model
ities of edge
hods such as
in be used to
Chen and
edge of the
to produce a
to regions of
obably exist
template and
et threshold,
¡tecting very
and aircraft
nplate may be
j the desired
such as the
attempt to
:ing line and
' orientated
late matching
is the Hough
962)) later
i) . For grey
ces peaks and
ding to light
space. These
ected and the
g traditional
sform can be
e which has a
s the conic
and has been
sctiveness in
mages (see
images the
at detecting
lative to the
L985)) . More
orm, the MUFF
een developed
:ric form for
short lines,
be equivalent
(1981) is an
been used for
as shown by
fes and for
in simulated
strated by
que comprises
ted transform
filter in the
transform domain. The most common transform
is the Fourier which when combined with a
high pass filter and thresholding process
produces an edge map equivalent to that
produced by local operators. Various
transforms and filtering strategies exist.
Unfortunately even the most sophisticated
processes fail at detecting thin line
structures in noisy environments.
2.4 Graph Search Methods
A graph is a mathematical object that
consists of a set of nodes {n^} and arcs
between nodes . Associated with each
arc is a cost . The edge or line search is
then seen as a search for the minimum-cost
path between two nodes of a suitably weighted
graph. If some measure of a best line is
known then the search may be optimal and the
solution found by dynamic programming as
demonstrated by Montanari(1971) otherwise the
solution may only be satisficing
(Palay(1985)) . Martelli (1972) demonstrated
the usefullness of this class of technique
for noisy images by using heuristics to
guide the search.
3 DISCUSSION
Local operators as a method of edge detection
are typically deterministic and aim to
calculate the local gradient image. This
approach involves difference operations and
is thus susceptible to high spatial frequency
noise. Other operators aim to reduce this
susceptibility by combining noise suppression
with edge detection but with derogatory
effects on thin lines and the most
sophisticated techniques prove unsuccessful
in low signal to noise environments. Image
modelling techniques offer some improvement
but parametric modelling exhibits many of the
disadvantages of local operators. Statistical
modelling methods can be global but need
accurate image and noise models. Consequently
they work well for synthesised images with
known noise distributions. Template matching
algorithms are excellent for extracting
specific feature shapes but still suffer from
being local in nature. Hough transforms
embody more global concepts but cannot be
fully generalised. Spatial frequency
techniques are insensitive to fine structures
and do not distinguish between signal and
noise. Graph search strategies can have both
global or local predicates built into an
evaluation function and so may be made robust
to noise. They are flexible and can provide
optimal or good satisficing solutions.
Usually they embody both serial and parallel
processes and thus may incorporate any level
of knowledge. Their disadvantage is the
extensive computation involved which may grow
exponentially with scene size so that
practical applications usually require an
initial boundary estimate to be manually
provided. However Bertolazzi and Pirozzi
(1984) has developed a parallel algorithm for
this class of problem offering much improved
sfficiency.
We may now think of the ideal technique for
thin line feature extraction and its
characteristics. For this one looks to the
human visual system to suggest the following
criteria.
1) Global predicates must be used.
2) The probability of an edge or line
existing at a certain pixel location is
dependent on other possible edges in the
scene.
3) Noise models should not be needed.
4) Only simple models of features should be
used.
5) The technique should allow for
generalisation.
6) Computational effort involved should be
related to the signal to noise level.
The published research indicates that thé
graph searching approach to thin line
detection is the most appropiate for noisy
scenes. The important problem that remains
however is how to devise a suitable
evaluation function which will encompass the
criteria listed above. Various evaluation
functions are currently being devised and
studied. This is an important continuing part
of the research.
The sophistication of this type of approach
implies that very intensive computation is
required but it is felt that recent advances
in computer technology such as parallel
processors & transputers render such concerns
irrelevant . It is more important that the
problems of feature extraction be tackled,
rather than the specific dificulties of
implementation on current computers.
4 CONCLUDING REMARKS
The major classes of thin line feature
extraction techniques have been reviewed with
emphasis placed on their suitability for line
extraction in the presence of image noise.
The decision has been taken to pursue the
graph search strategy and to develop and test
a generalised algorithm. Finally a successful
line feature algorithm may be synergistically
combined with an area based segmentation
technique to produce the mythical perfect
image segmentation. Such a technique may then
be easily integrated into an automatic
interpretation schema.
REFERENCES
Ballard, D.H. & Brown, C.M. 1982. Computer
Vision.
Bertolazzi, P. & Pirozzi, M. 1984. A Parallel
Algorithm for the Optimal Detection of a
Noisy Curve. Computer Vision, Graphics &
Image Processing. 27:380-386.
Carlotto, M.J etal. 1984. Feature Extraction
Assesment Study. Report no. ETL 0377 DACA76
82C 0004.
Chen, P.C. & Pavlidis, T. 1980. Image
Segmentation as an Estimation Problem. In
Rosenfeld(1981).
Chittineni, C.B. 1983. Edge and Line
Detection in Multidimensional Noisy Imagery
Data. IEEE Transactions on Geoscience and
Remote Sensing. 21,2:163-174.
Davis, L.S. 1975. A Survey of Edge Detection
Techniques. Computer Graphics and Image
Processing. 4:248-270.
Deans, S.R. 1981. Hough Transform from the
Radon Transform. IEEE Transactions on
PAMI.3,2:185-188.
Duda, R.O. & Hart, P.E. 1972a. Use of the
Hough Transformation to Detect lines and
Curves in Pictures. Communications of the
ACM. 15,1:11-15.
Duda, R.O & Hart, P.E. 1972b. Pattern
Classification And Scene Analysis. Wiley
Interscience.
