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 <n^,nj>. 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.