oar 
ata 
ue 
gh 
Ire 
19 
to 
1d 
e, 
Edge Following as Graph Searching 
In this stage, Edge Following as Graph Searching 
(EFGS) algorithms (Wang and Howarth, 1987, 
1989; Wang, 1993) are applied to the combined 
channel to identify edges in the image. This 
involves three major steps. First, an "edge 
operator" is used to obtain the magnitude and 
direction of an edge. This is based upon 
determining the locations where maximum 
changes in digital values occur and what the 
directions of these changes are. The procedure 
can be applied to detect edges as well as light 
lines or dark lines, depending upon the 
appearance of the lineaments in the image. 
Second, the starting points for the edges are 
identified. The starting edge point selection 
algorithm identifies the most prominent edges 
and it is found that a large number of these 
correspond to parts of lineaments. Finally, EFGS 
is used to trace all the edges on the image. A 
graph can be formed from each starting edge 
point. Each arc in the searching graph is 
associated with a cost. The cost is a function of 
edge magnitude and direction, as well as the 
tracing direction. The EFGS algorithm may be 
summarized as follows: 
(1) Accept all starting points as edge elements. 
(2) If there are no more starting points, stop. 
Otherwise, assign the next starting point as 
the current node. 
(3) If there is no neighbor in front of the tracing 
direction of the current node, go to Step (2). 
(4) Compute the cost for the arc connecting the 
current node to each of its neighbors in the 
tracing direction. Accept the minimum cost 
neighbor as an edge element. If no neighbor 
is accepted, go to Step (2) Otherwise, 
assign this neighbor as the next current 
node and the direction of the arc from the 
previous current node to this node as its 
tracing direction. Go to Step (4). 
Hough Transform 
The edge image obtained from the EFGS 
algorithms contains edge pixels with a value of 1 
and background pixels with a value of 0. The 
problem in lineament detection is to locate the 
presence of groups of collinear or almost 
collinear edge pixels. The problem can be solved 
to any desired degree of accuracy by testing the 
lines formed by all pairs of points in the picture. 
751 
However, the computation required for n pixels 
is approximately proportional to n? , and may be 
prohibitive where n is large. Hough (1962) 
proposed an interesting and computationally 
efficient procedure for detecting lines in 
pictures. It has become known as the Hough 
Transform. The main advantages of the Hough 
Transform are that it is relatively unaffected by 
gaps in lines and by noise. In this paper, Hough 
Transform is applied to detect straight lines 
which represent geologic lineaments on the 
multispectral satellite images. The Hough 
Transform method described by Duda and Hart 
(1972) is used and modified for lineament 
detection. The procedure involves use of the 
Hough Transform, finding of local maxima, 
application of an inverse Hough Transform and 
straight line profile analysis (Wang and Howarth, 
1990). Geological lineaments are frequently 
discontinuous on the original image. However, the 
segments lying on the same line can be joined 
together if they are close enough to each other. 
In other words, certain gaps are allowed on a line 
in this straight line detection algorithm. The size 
of the gaps allowed for can be assigned by the 
user of the LINDA system (Wang, 1993). 
RESULTS 
To evaluate the performances of the lineament 
detection algorithms on multi-band remote 
sensing images versus on single band images, a 
study area of part of the Canadian Shield near 
Sudbury, Ontario has been selected. It includes 
part of the exposed Grenville Province. The 
dominant rocks in this area are middle 
Precambrian metasediments and an anorthosite 
suite of intrusive rocks. Structural control is 
suggested by the preponderance of elongate lakes 
confined to a few orientations. A subscene of a 
Landsat 5 Thematic Mapper (TM) image with 
seven channels over the study area is obtained. 
The procedure for lineament detection, including 
preprocessing, edge detection and Hough 
transform, has been applied to each of the seven 
Landsat TM channels. From a comparison of all 
the seven TM bands, it is observed that Band 4 
image (near infrared) displays the lineaments 
most clearly (shown in Figure 1) and that Band 4 
image also results in the best single-channel 
lineament detection (shown in Figure 2) among all 
seven Landsat TM bands. However, from Figure 
2, it can be seen that not all lineaments are 
detected. 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B7. Vienna 1996