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.