GISdevelopment.net ---> AARS ---> ACRS 1995 ---> Digital image Processing

Automation of Road Extraction from Space and Aerial Images

ArminGruen, Haihong Li
Institute of Gerodesy and photogrammetry
Swiss Federal Institute of Technology
ETH_Hoenggerberg
CH-8093 Zurich
Switzerland


Abstract
This paper deals with automation of monoscopic extraction of liner features, in particular roads ,from space or aerial images. The objective is to devise a digital photogrammetry strategy for the automation of object extraction and precise measurement during GIS data acquisition in order to facilitate and speed-up the GIC generation and updating processes .the proposed techniques can be either used in a monoplotting mode (combining one image with the underling DTM)or in multi-image mode. We will focus here on the first option.

We present some of the results which we obtained with various model-based features extraction techniques, e.g. dynamic programming , and LSB-snakes(Least Squares B-spline snakes).In these model-driven feature extraction schemes a road is represented by a generic model with various photometric and geometric properties .We will briefly report about the mathematical approaches from optimization and estimation that have been used and address also the implementation and application aspects.

1. Introduction
Of all parts in the process of GIS data generation from aerial photographs and satellite images ,the actual mapping phase is one of the most time consuming and expensive. Research is therefore increasingly focusing on the development of efficient methods to extract topographical features like houses and roads from digital images. As fully automatic methods from mapping are still out of reach ,semi-automatic methods for feature extraction that interact with a human operator are considered to be a good compromise , compromise ,combining the mensuration speed and accuracy of a computer algorithm with the interpretation skill of the operator

This paper deals with road extraction, a semi-automatic monoplotting approach to extract road network from digital images for GIS data capture ,where the identification takes is performed manually on a single image, while special automatic digital module performs the high precision road tracking . more specifically , a human operator is used to identify a road from belongs to and provides some very few seed points coarsely distributed. It is done through activation of a mouse in a convenient interaction graphics -images used interface . Subsequently , with these seed points as approximation of the position and shape ,the road will be extracted .these techniques can be either used in a monoplotting mode (combining one image with the underlying DTM)on in a multi -image mode

The next section provides an overview of our sequence of algorithms as it runs in monoplotting mode .section 3outlines the mathematical representation and implementation of our model driven road extraction algorithms . Section 4 presents some experimental result. Finally ,some Conclusion will be given in section 5

2. The Concept of Semi -Automatic Road Extraction
A semi-automatic scheme for the extraction of road network for digital images is shown in Figure 1. Its central procedure is a model driver feature extraction algorithm based on either dynamic programming or LSB-snakes (least squares B-spline snakes).


Fig 1 : A semi-automatic road extraction scheme

In the current implement , image preprocessing and sharpening are performed by two separate programs. The wall is used for preprocessing to enhance the image and facilitate the subsequent road extraction process by locally forcing the gray value mean and especially contrast (dynamic range )to fit certain target values (baltsavias,1991.)after the wallis filtering , wavelet transform is applied to the image is displayed in a convenient interactive graphics-image user interface. The road identification and classification are performed by the human operator . After some very few seed points have been given by the operator, through activation of a mouse on the displayed image , the road will be extracted automatically and precisely by a model driven feature extraction algorithm whose details will be given in the next sections . the algorithm derives either image coordinates (x,y) or orthoimage coordinates (x,y)or space coordinates(x,y,z)of the roads ,whereby the z- component comes from real -time interpolation within an underlying DTM.if an orthophoto is used this is simply done by a bi-linear interpolation . otherwise, a camera model or projection equation is applied , as illustrated in Figure2 , in an iteration procedure for the computation of (x, y ) coordinates and interpolation of the Z-component


Fig.2 : 3-D interpolation within the DTM

3. Model Driven Optimization For Feature Extraction
Model driver optimization , or fitting models to photometry (suetens et al. 1992), is one of the classic approaches to feature extraction from digital images . In its basic from an objective function is defined as a matric or similarity measure of fitness between the model of the feature to be extracted and the image data and an algorithm is used to be perform the optimization , finding the maxima or minima of the objective function . There are many different optimization and Estimation techniques used for feature extraction for instance ,least square template matching (Gruen , Stallmann , 1991) , dynamic programming (Gruen ,Li,,,1994 ), active contour models (kass et al. 1988, Fua ,Leclerc , 1990 , Trinder ,Li 1995) edge relaxation graph and so on .The general consists of the following basic elements :
  1. A generic or specific object model to describe the geometric appearance of the object of interest in the digital image.
  2. An objective function to measure the fitness between the object model and the image data.
  3. An algorithm to evaluate the objective function and perform the optimization or estimation.
The effectiveness of the method depends strongly on the appropriateness of the modelling primitives that are searched for . if well-known object models are available ,they can be described by a limited of photometric and geometric constraints .

In large scale aerial images the details of a road surface are clearly evident , so that a liner elements can be decomposed into detectable primitives and a precisely road model could be defined with the exact knowledge of roads .In contrast satellite images contain a tremendous number of objects which , however , are imaged at a very small scale .In this case ,road extraction is usually viewed as liner feature extraction ,instead of the application of a precise object model which is difficult to realize with small scale images , a generic model which consists of a set of photometric and geometric constraints on road characteristics such as smoothness and homogeneity is used.

A road is a well -defined . its characteristics can be classified in five groups : photometric ,geometric , topological , functional and contextual characteristic (Vosselman ,knecht ,1995). In our semi -automatic road extraction scheme the high level knowledge ,which requires quite some intelligence for the image interpretation process , is used by the human operator to identify and classify the road networks. The generic road model involved in the model driven road extraction algorithms consists of some photometric and geometric characteristics (Gruen ,Li,1994,1995) Examples are:
  • a road surface often has a good contrast to its adjacent areas.
  • a road surface usually is homogeneous (at least in a certain portion of the image ).
  • a road is continuous and narrow region or liner feature ,
  • a road is smooth and does in general not have small wiggles.
  • the local curvature of a road has an upper bound ,
  • the width of a road segment does not change significantly.
These properties can be mathematically formulated and discretized by a merit function and an inequality constraint in the form of


This multistage optimization problem is efficiently solved by dynamic programming through the time -delayed algorithm (Gruen , Li,1994 ) .it's advantages stem fron its efficiency in handling long curves , robustness in the presence of noise and ability to bridge gaps.

For the LSB -snakes algorithm , we suppose a road can be approximated by a cubic splie as where X¡ and Y¡ are the parameter of the cubic spine in x and y direction respectively .In terms of spline concept , they from the coordination of the control polygon of the curve . N¡ (s) is the normalized 4th order B-spline between knots s¡ and s¡_4.


Thus road extraction can be treated here as the problem of the parameters X¡ and Y¡ of the spline . In least squares notation we use three types of observations , the region of the image and its photometric features as the observations of the initial curve formed by these seed points as the geometric model . a further development of these observation equations will result in the normal equations used for the estimation of the parameter as


In a semi -automatic feature extraction scheme , the human operator initially place some seed points near the image structure of interest . With these seed points , the approximations x º and yº of parameters x and y , an initial curve and the matrices Nx,Ny, and vectors x and y falls below a threshold (for details see Gruen,Li ,1995).

With B-splines as the approximation of snakes and least squares estimation of the pararmeters we have the advantage of local support , continuity control and especially quality control.

4. Experimental Results
The model driven optimization strategies for semi-automatic road extraction described in this paper have been successfully implemented at our institute on a digital workstation under X-Windows and OSF/Motif and tested on a number of real images. In this section , some typical examples will be given.

Figure 3a shows portion of a preprocessed SPOT panchromatic image of Moudon, Switzerland. The seed points provided by the operator along the road which is to be extracted are marked by black discs. The white rectangles denote potential problematic areas, i. e. gaps due to the road going through forests areas. The road extracted by dynamic programming is shown in figure 3b in black. Obviously the algorithm bridges gaps in a robust manner.


Fig 3a A portion of a SPOT panchromatic image with seed points and potential problematic areas.


Fig 3b . The road extracted by dynamic programming

Figure 3c focuses in another portion from the same SPOT image. At this time, the problematic areas marked with white rectangles are intersections with other roads and a passage through an urban area, which might cause ambiguities and erroneous changes of direction. The result of Figure 3d shows that no problems are encountered in this case.


Fig 3c. A portion of a SPOT panchromatic image with seed points and potential problematic areas.


Fig 3d. The road extracted by dynamic programming

Figure 4a is apportion of a larger scale aerial image of Avenches, Switzerland. Roads in this image have different widths and are disturbed by buildings , trees , cars and other objects. The LSB-snakes algorithm is applied to this image. The extracted roads are shown in figure 4b . The snake does not follow the center line of the road in all cases because of disturbing vehicles. This kind of required high level knowledge is impossible to integrate into the objective function or energy of snakes . For this case, a special high level processing or postprocessing procedure should be developed.


Fig.4a: portion of an aerial image with seed points.


Fig. 4b: Roads extracted with LSB-snakes

Additional experiments with other images verified the efficiency and good accuracy performance of the technique .

5. Conclusions
The semi-automatic object extraction strategies presented here can be used for monoplotting on a digital photogrammetric station. A human operator is required to identify a road and give a few start points coarsely distributed. Such use of a human operator within a system is considered optimal because humans perform the identification task flawlessly and almost effortless. The precise road extraction, which experience shows to be a time consuming and error-prone part of photogrammetric data collection , is performed fully automatically and fast. It is possible to include in these optemization and extraction procedures the given camera models, such that we obtain a multi-image and fully 3-D geometrically constrained approach.

The technique can be extended and customized through the use of other specific photometric and geometric properties to extract various other types objects. Roads on large scale images have many details and are distributed other objects. For this case , a postprocessing procedure based on high knowledge should be developed .

6. References
  • E. P. Baltsavias, "Multiphoto" geometrically constrained Matching '. Mitteilungen Nr. 49, institute of Geodesy and photogrammetry , ETH Zueich,1991.
  • P. Fua and Y. leclerc,"model driven edge detection , machine vision and applications ,vol.3,pp.45-56,1990.
  • A Gruen and H.Li,'Semi-automatic road extraction by dynamic programming ",international archives of photogrammetry and remote sensing .vol,part3/1.pp.324-332,1994.
  • A. Gruen and H. Li, "'Semi-automatic road extraction as a model driven optimization procedure ,"SPIE Proceedings, St. Petersuburg-Great Lakes Conference on Digital photogrammetry and Remote Sensing 95,1995
  • A .Gruen and D.Stallmann, "high accuracy edge matching with an extension of the MPGC matching algorithim ,"SPIE Proceedings , industrial Vision metrology, Vol. 1526,pp . 42-45,1991.
  • Mkass, A. Witkim and D. Terzopoulos, " Snakes: Active contour models" , International Journal of Computer Vision , Vol. 1(4), pp.321-331, 1998.
  • P. Suetens, P. Fua and A.J. Hanson, "Computational strategies for object recognition" , ACM Computing Surveys, Vol. 24, No.1 , PP.5-61, 1992.
  • J. Trinder and H.Li, "Semi-automatic feature extraction by snakes" , Automatic extraction of man made object from Aerial and Space images, Birkhaeuser Verlag, pp.95-104, 1995.
  • G. Vosselman and J. De Knecht, "Road tracking by profile matching and Kalman filtering " , Automatic Extraction of Man-Made objects from aerial and Space images , Birkhaeuser Verlag , pp.265-274, 1995.