A Knowledge-based System for Automatic Extraction of Highway Network From Satellite Imagery

A Knowledge-based System for Automatic Extraction of Highway Network From Satellite Imagery

Md. Mijanur Rahman and Dr. Abdelhamid Abdesselam

Introduction
Road network being one of the most important topographic failures, its extraction from satellite imagery has drawn attention of many researchers from various disciplines. Fangju Wang et al [1] have developed a knowledge based system for highway network extraction extraction from Landsat TM imagery. Their system first enhances the edges in the three bands B1, B2, B3 by applying the Lapplacian operator. Then a k-means clustering is applied on the three enhanced bands to produces a binary image which highlights the road candidates. A tracing algorithm then extracts linear patterns from the binary image. These linear patterns are analyzed by an expert system to construct a complete highway network.

Rin-ichiro Taniguchi et al [2] knowledge-based system first extracts edge primitives which are then clustered into line segments. The clustering is based on edge strength and direction. These line segments are linked to form complete roads. The linking process takes into account line segment proximity and orientation. Spectral and spatial knowledge is then used to exclude similar patterns such as mountain valleys, ridges etc.

Many other approaches have been adopted. Kuo-Tu-Ko [3] and Julian E. Boggess [4] have developed artificial neural network based systems. Donald E. Brown et al [5] system is based on learning vector quantization method. Nicolas Merlet et al [6] adopted a dynamic programming approach. Jianying Hu et al [7] used a graph-based approach. However, systems developed so fat are limited in their scope and accuracy.

Road identification difficulties

Characterizing roads in satellite imagery is a very hard task:
The low resolution of the standard satellite imagery (SPOT [20x20, 10x10], Landsat TM [30x30] etc.] restrict their use to identification of highway networks only. Highways appear as 1 to 3 pixel-wide linear features generally contrasting in spectral value from background features. The presence of the noise in the image and the gaps between road pixels caused by overhanging trees and vehicles on the roads etc. make the linking process of road pixels very complex.

However, some properties of roads can be helpful to overcome these difficulties. Firstly, roads do not change direction frequently. Secondly small segments of roads are generally either straight or curved with only one bend and hence can be fitted well with conic curves. Conic curves are described by second degree equations and have a reasonable computational cost. Thirdly , different roads may have different spectral values (colors), but a single road generally possesses spectral similarity over its parts. And finally, Expert knowledge related to spectral and spatial characteristics of roads can greatly simplify the complexity of the task and produce reasonable results as human being can easily follow roads, even if they appear discontinuous in the satellite imagery (due to occlusion, spectral similarity with environment, etc.).

Major steps of our approach
Our automatic approach of highway network extraction consists of edge detection followed by construction of candidate road segments. A knowledge based system will link candidate road segments to form candidate roads and then exclude all non-road components (such as rivers, valleys, etc.) presents in the image.

Edge Detection
As roads contrast in spectral value from background, edge detection technique is quite suitable to extract road pixels from the image. Moreover, as road appear as linear patterns, applying line-edge detector is more appropriate than step-edge detector. We are using 5x5 line detection templates to extract candidate road pixels. On contrary to the step edge detectors extracting edges on both sides of linear strips, these templates extract pixels on the strip itself. 3x3 line detection templates are more sensitive to noise than 5x5 ones. Moreover, they can detect up to 3 pixels wide line strips. Because roads my appear in any orientation in the image, numerous templates would be required to extract all candidate road pixels. Experimental results show hat we can achieve satisfactory results with only four 5 x 5 templates oriented 45° apart from each-other [fig 2]. Convolved images are thresholded and ORed to get a single edge-image containing only candidate road pixels.

fig 2: 5x5 line detection templates

**Horizontal**
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
4	4	4	4	4
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1

**Vertical**
-1	-1	4	-1	-1
-1	-1	4	-1	-1
-1	-1	4	-1	-1
-1	-1	4	-1	-1
-1	-1	4	-1	-1

**+45 degrees**
-1	-1	-1	-1	-4
-1	-1	-1	-4	-1
-1	-1	-4	-1	-1
-1	-4	-1	-1	-1
-4	-1	-1	-1	-1

**-45 degrees**
-1	-1	-1	-1	4
-1	-1	-1	4	-1
-1	-1	4	-1	-1
-1	4	-1	-1	-1
4	-1	-1	-1	-1

Candidate road segment construction
As mentioned earlier, presence of noise in the image, occlusion, spectral similarity of roads with other objects etc. make road segment tracing difficult. In order to overcome these problems, we have considered some road properties and proposed the following constraints in our tracing algorithm:

While tracing through pixels in the edge-image there can be at most two pixels gap between current pixel and he next pixel.
Change in direction within any three consecutive pixels should be within +45 degrees
A candidate road segment should be longer than some minimum length (10 pixels).
Pixels included in the same road segment should be spectrally similar.
A candidate road segment should be well fitted with some conic curve (parabola).

In our algorithm, linear patterns are first found be tracing through edge pixels with constrains (1) and (2). Each linear pattern longer tan certain minimum length (constraint 3) is ten checked to see whether it is spectrally uniform over its length (constraint 4) and whether it can be fitted with a conic curve (constraint 5). Linear patterns fulfilling these conditions are finally considered as candidate road segments.

Candidate road construction
In order to extract complete road network, candidate road segments need to be linked. We are developing a knowledge based system that will take into account spectral and spatial attributes of road segments such as mean spectral value, orientation, position, context etc. to determine which segments should be extended and connected together to form candidate roads.

Exclusion of non-rod linear components
Linear features extracted in previous steps are not all roads. Some of them may be rivers, mountain valleys, ridges etc. They need to be excluded. The rule-based sub-system mentioned earlier will decide which candidate roads are actually roads and exclude all non-rod linear features from the output image.

Experiments
We have already completed first two steps, namely edge detection and candidate road segments construction and we are now developing a knowledge based system for last two steps i.e. linking candidate road segments and excluding non-road linear features. However, we have applied our system developed so far on SPOT satellite imagery and obtained good initial results. A portion of a SPOT image is shown in fig 3. Fig. 4 sows output of edge detection. Candidate road pixels have been extracted quite well. But as expected, a lot of noise-pixels are also present in the edge image. In fig-5 is shown output of construction of candidate road segments. Most of the isolate dots and very short line segments (Extracted from nose and non-road background features) are eliminated. But still some non-road linear patterns are present in the image. They will be progressively excluded in next processing stages.

Fig-3: SPOT image

Fig-4: Image after edge detection

Fig-5: image after candidate road segment construction

References

Fangju Wang & Ross Newkirk "A Knowledge Based System for Highway Network Extraction" IEEE conference, Sept. 1988, Geoscience and remote sensing, volume 26, issue 5, pages 525-531.
Rin- ichiro Taniguchi & Eiji Kawaguchi "Road Network Extraction from LANDSAT TM Image" IEEE conference, July 1989, Image Processing and its Application, con. Pub. No. 307, pages 222-226.
Kuo-Tu-Ko "A Hybrid Road Identification System using Image Processing Techniques and Back-propagation Neura Networks" A masters thesis (1995), Dept. of Computer Science, Mississippi State University, USA.
Julian E. Boggess "Identification of Roads in Satellite Imagery using Artificial Neural Network : A Contextual Approach" Computer Science Department, Mississippi StateUniversity, USA.
Donald E. Brown & John Marin "Learning vector Quantization for road extraction from digital imagery" IEEE conference, Oct. 1995, Systems, man and cybernetics. Intelligent systems for the 21st century, volume 2, pages 1478-1481.
Nicolas Merlet & Josiane Zerubai. "New Prospects in Line Detection by Dynamic Programming" IEEE transactions on pattern analysis and machine intelligence, April 1996, volume 18, issue 4, pages 426-431.
Jianying Ho, Bill Sakoda & Theo Pavlidis "Interactive Road Finding for Aerial Images" IEEE conference, 1992, Applications of computer Vision, pages 56-63.