Go to Paper
Return to GeoComputation 99 Index

Road Extraction from Digital Images Using Linear Programming and Cost Functions

CHALASANI, Venkat, (vsc4d@virginia.edu) and BELING, Peter (beling@virginia.edu), University of Virginia, ATTN: Systems Engineering, Olsson Hall, Charlottesville VA 22903

Key Words: road extraction, linear programming, classification, cost functions

Remote sensing data of the Earth's surface is readily available in digital format. These data can be used for identifying certain features of interest in the image with the assistance of computers. To identify a feature of interest we not only have to classify individual pixels as belonging to a specific class, but also identify a set of such pixels as a part of the feature. We refer to this process as feature extraction. Roads have certain interesting properties that can help us in extracting the roads from the image. This can be practical in terms of creating and updating digital maps.

In this paper we propose a two-step process for extraction of roads and demonstrate the results from an Airborne Visible Infra Red Imaging Spectrometer (AVIRIS) image of an area near Williamsburg, Virginia. The first step in our methodology is a classification step in which the bands of the image are treated as attributes. We create a training set by manually identifying certain coordinates as belonging to a specific class, such as road or soil, and then list the attributes for the specific coordinates obtained from the bands of the image. We use linear programming to create a discriminating surface between different classes. The linear program is formulated to find a surface in which all the points of one class in the training set are on one side of the discriminating surface, and all points of the other classes in the training set are on the other side of the surface. If it cannot find such a surface, it finds a surface that minimizes the average sum of errors, where an error is the distance to the separating surface if a point falls on the wrong side of the surface. By separating out the classes one after another, the separating surfaces form a decision tree. The decision tree is then applied to all the pixels of the image to identify pixels belonging to the class road. We use the distance to discriminant surfaces for each pixel to assign it a probability measure of being a road, which is then converted to a gray scale value and is used to rebuild the image with only roads. We also show results of using LP for feature selection in a nearest neighbor-based approach.

As a second step, certain properties of the roads, such as their elongation and contrast to the adjoining pixels, and the grayness measure created as a result of step one, are used to create cost functions. The function has a lower value if the configuration of pixels is closer to what we would expect from a road, and is higher otherwise. We then use dynamic programming to trace a minimum cost path through the pixels of the image produced by classification. We show that this approach is effective in tracing roads in a road network.