International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 1

ISSN 2229-5518

Road Network Extraction from High Resolution

Satellite Images based on LSE _ LBF Model

T Rajani Mangala, S G Bhirud

Abstract— Road information extraction from high resolution satellite images plays an important role because roads affect urban and rural land cover and usage. It is difficult and computationally intensive and expensive to extract roads due to presence of their road like features with straight edges. In this paper we have used the level segment evolution and local binary fitting based model for the extraction of roads. This algorithm followed by morphological operations gives satisfactory results.

Index Terms— Closing, Dilation, Gaussian Kernel Function, Morphological Operation, Level Segment Evolution, Local Binary Fitting, Road

Network Extraction

——————————  ——————————

I. INTRODUCTION

oads have played a central role in the lives of man since the beginning of time. Before the invention of sea, air and rail travel, roads were the solitary means of
transporting goods and people from one location to another. Even in today's modern society, roads are the
more frequently used mode of transport.
At present, data regarding road locations and their characteristics is stored within geographic databases which enable numerous Geographic Information Systems (GIS) applications. Road data enables GIS applications to facilitate a variety of services which include satellite navigation, route planning, transportation system modeling, health care accessibility planning, land cover classification and even infrastructure management. Road networks play an important role in a number of geospatial applications, such as cartographic, infrastructure planning and traffic routing software.
Road network extraction is classified as: manual process, semi-automated process and fully automated process. Manual extraction entails a human operator delineating roads from remotely sensed imagery, while semi- automated extraction requires some human input to guide a set of automated processes. The automated extraction process requires no human input and has a set of algorithms. [1] Fully automated road extraction systems comprise a variety of algorithms, which can be roughly classified into three levels of processing [2]:
- Low-level operations that work with the raw image data,
- The medium-level processes that further refine the

information gathered by the low-level algorithms, and

___ _ _ _ _ _ _ _ _ _ _ _ _ _

T Rajani Mangala is currently pursuing PhD from Mukesh Patel

School of Technology Management and Engineering, NMIMS, Mumbai, India. email id: rajani_mangala@yahoo.com

S G Bhirud is a Professor in Computer Department of Veer

Jijamata Technical Institute, Mumbai, India.

- The high-level algorithms that produce the final road networks.
The higher-level algorithms exhibit aspects of intelligence with ability to reason on the structure and location of road networks in a fashion similar to humans [1].
Different algorithms have been used for the extraction of road network data. Level set methods were used for capturing moving fronts and active contours model is used for segmenting objects in images using dynamic curves [3,
4]. Active contour models are of two types: parametric active contour models and geometric active contour. The parametric active contours are represented explicitly as parameterized curves in a Lagrangian framework, while the geometric active contours are represented implicitly as level sets of a two-dimensional function that evolves in an Eulerian framework. Geometric active contours models represent contours as the zero level set of an implicit function defined in a higher dimension, usually referred as the level set function, and to evolve the level set function according to a partial differential equation (PDE) [5]. The contours represented by the level set function may break or merge naturally during the evolution, and the topological changes are thus automatically handled and the level set function always remains a function on a fixed grid, which allows efficient numerical schemes.

II. BACKGROUND AND LITERATURE SURVEY:

Many papers are available on related topics; a few have been discussed here.
K. Vogt, et al, [6] proposed a method that extracts plantations from satellite imagery by finding and exploiting appropriate feature space projections. Segmentation is done using an automatic two-region segmentation based on the level set method. The behavior of this algorithm is defined

International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 2

ISSN 2229-5518

by a statistical region model that describes the similarity of regions using distances in arbitrary feature spaces. Subsequently different feature spaces were evaluated regarding their plantation classification quality in an automatic fashion.
Chunming Li, et al [7], presented a formulation for geometric active contours that forces the level set function to be close to a signed distance function, and the need of the costly re-initialization procedure. Here an internal energy term that penalizes the deviation of the level set function from a signed distance function, and an external energy term that drives the motion of the zero level set toward the desired image features, like the object boundaries are found. The resulting evolution of the level set function gets the gradient flow that minimizes the overall energy functional. This method has three advantages: first, a significantly larger time step can be used for numerically solving the evolution partial differential equation, and speeds up the curve evolution. Second, the level set function can be initialized with general functions that are more efficient to construct and easier to use in practice than the widely used signed distance function. Third, it is easy to implement with a simple finite difference scheme and is computationally more efficient.
Chunming Li, et al [8], they proposed a region-based active contour model that is able to utilize image information in local regions. The local region image information is crucial for accurate segmentation of images with intensity inhomogeneity. But, image information in local region is not embedded in popular region-based active contour models, such as the piecewise constant models. Local binary fitting energy with a kernel function, which enables the extraction of accurate local image information was used. This algorithm segments the images with intensity inhomogeneity, which overcomes the limitation of piecewise constant models.
Chunming Li, et al, [9], presents an energy minimization method for simultaneous tissue classification and bias field estimation of magnetic resonance (MR) images. Based on local image intensities — the intensities of different tissues within a neighborhood form separable clusters, and the center of each cluster is well approximated by the product of the bias within the neighborhood and a tissue-dependent constant was found. A coherent local intensity clustering (CLIC) criterion function was used as a metric to evaluate tissue classification and bias field estimation. An integration of this metric defines energy on a bias field, membership functions of the tissues, and the parameters that approximate the true signal from the corresponding tissues.
M. Rajeswari [10], et al, proposed that the image should be preprocessed to improve the tolerance by reducing the noise (the buildings, parking lots, vegetation regions and other open spaces). Secondly roads are extracted based on Normalized cuts method and Mean Shift Method.
Thierry G´ eraud, et al, [11] present a transposition of the segmentation scheme “watershed transform + region adjacency graph + Markov random fields” to extraction of curvilinear objects. In potential image, the value assigned to a point is a measure of its likelihood to be located in the middle of a road. A filtering step applied on the potential image relies on the area closing operator followed by the watershed transform to obtain a connected line which encloses the road network. Then a graph describing adjacency relationships between watershed lines is built. Defining Markov random fields upon this graph, associated with an energetic model of road networks, leads to the expression of road network extraction as a global energy minimization problem. This method can easily be adapted to other image processing fields, where the recognition of curvilinear structures is involved.

III. EXTRACTION ALGORITHMS

The level-set method applies a function Φ (p; t) to the space the interface inhabits, where p is a point in that space, t a point in time. The function is initialized at t = 0, and then a scheme is used to approximate the value of Φ (p; t) over small time increments.
First a mesh or a grid of points that covers the image is selected. A fine mesh gives more accurate the level-set method.
Then the value of Φ (p; t) is initialized at each point of the mesh. The function Φ is defined as follows, for any point p in the mesh

Φ (p; t) = ±d (1)

Where d is the distance from the point p to the curve at the time t = 0. The positive sign is used if the point p is outside the closed curve; the negative sign is used if the point p is inside the closed curve.
A computationally intensive algorithm is used to set up the initial value of function Φ at each of the mesh point. For each mesh point, the distance between it and each point on the curve is determined and the minimum value is set as

International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 3

ISSN 2229-5518

the mesh point's Φ value. The number of points on the curve depends on the pixel resolution.
As the curve evolves in time, the value of the function Φ at each mesh point evolves. Now Φ is updated at each point using a standard method that gives small increments of time. A derivation that gives an expression for the time derivative of Φ follows. Consider a function p (t) that describes the path of a point on the curve through time. Then,

Φ (p (t); t) = 0 (2)

The chain rule yield

Φt + Φ p’ (t) = 0 (3)

image I(x) represented by the zero level set of a Lipschitz function u(x) : u(x) Ω. The total energy of LBF model, with respect to u(x), is defined by

E(u; f1; f2) = αL(u) + βD(u) + (9)

where α and β are nonnegative constants, L(u) is the length term of the zero level set of u, D(u) is a distance penalizing term to ensure stable evolution of level set function with- out re-initialization and ELBF (x) is local binary fitting energy defined. To minimize the total LBF energy function, the gradient descent flow is expressed as

Let be an outward directed normal to the contour. Then can be rewritten in terms of Φ as follows:

where,

(10)

= (4)

The speed function F,

F = p’ (t). (5)

Substituting in the equations for F and yields

Φt + F = 0 (6)

The speed function is F = F0 - єk , then

Φ t = - F0 + єk (7)

(11, 12, 13, 14)

Kσ(x) is the Gaussian kernel function with variance σ, and

σ(x) is Dirac function

and approximate the derivatives of the first term using an entropy satisfying scheme and approximate the derivative of the second term using a central difference approximation.
The value of Φ after a small time interval Δt is then

(15)

(16)

approximated using the first-order

Taylor expansion with respect to t:

(8)

For each point x on contour C, local binary fitting energy

ELBF (x) is defined as

In local binary fitting model [12] arbitrary grid point x

belong to image domain Ω : Ω R, and C be a contour in

International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 4

ISSN 2229-5518

over S B
is like performing the sliding window operation.

(17)

When point x is exactly on the object contour, LBF energy
Mathematically,

wi (z)  S(i /(M| SE1 | 1),z (i%(M| SE1 | 1)))SE1(z)

(18)

ELBF (x) achieves a minimization value. Otherwise, curve C

where,

wi ( z)

is the window of elements taken from the
is evolved by the two fitting values f1(x) and f2(x), until all
points of C are exactly on the contours of the object. Based
image

S B ;

i  0,1,, N w  1

and
on local information of images, LBF model can get accurate

z  0,1,,| S E1 | 1,

N w is the number of windows

object boundaries by optimizing global LBF energy. It can
partition the satellite images with intensity inhomogeneity,
which cannot be segmented accurately by region-based

determined from the image, which can be determined as N w  M ( N  | S E1 | 1) . Based on the window

model. It also can partition images with weak boundary object or road-like objects, which cannot be easily segmented by edge-based model.
elements, dilated window of pixels as follows:

di ( z)

are determined

IV. MORPHOLOGICAL OPERATIONS:

1;

di ( z)  

if wi (0.5 | S

E1 | )  1

(19)

Morphological operations are a broad set of image

0 ;

otherwise

processing operations that process images based on shapes. Morphological operations apply a structuring element to an input image, creating an output image of the same size. The value of each pixel in the output image is based on a comparison of the corresponding pixel in the input image with its neighbors. By choosing the size and shape of the neighborhood, one can construct a morphological operation that is sensitive to specific shapes in the input image.

In the proposed classification system, two morphological operations have been used, namely, dilation and morphological closing. The segmented image S ( x, y) ,

which is a binary image, is subjected to dilation and the resultant is morphologically closed. The morphological
From di ( z) , D is obtained by initially generating an empty matrix with image size and then placing the di ( z) window elements in D at the corresponding positions from which the elements are taken.
Morphological closing: The dilated image D is subjected to the morphologically close operation. A structuring element disk is selected with the properties of size d size . Mathematically,

(20)

operations are explained below
where,

S E 2

is the structuring element for morphological

Dilation: Dilation, which is one of the two fundamental

closing and

D' is the dilated image of D . Similarly as in

operators in mathematical morphology, broadens the boundaries of regions of white pixels. The white pixels get increased by its size whereas the holes get reduced. This is performed with the support of a structuring element S E1 .
Eq. (7), the window of elements is extracted from D'
using S E 2 . From the window of elements, the eroded pixels are determined as follows
The structuring element is line with the properties of width

1 ;

c S 

if wi  I

 and degree  . This structuring element can be defined

as a vector of size | S E1 | . In S E1 , there are | S E1 | elements

i (0.5 |

E 2 |)

0 ;

otherwise

(21)
with values of unity, where,

| S E1 | is odd. The dilation

where, I is the Identity matrix, which represents the size
process is performed by applying the structuring element
1 | S E 2 | and ci is eroded pixels of i th window. The final

S E1

over S B
and then a decision making process is
morphologically closed image C is obtained by initially
performed to get the dilated image D . Applying the

S E1

generating an empty matrix and then by placing ci at the corresponding positions in C .

International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 5

ISSN 2229-5518

The edges thus obtained from the edge detection algorithm are then coupled together by morphological operations.

The workflow of our extraction algorithm:
Find the initial contour, initial level set function
Adjust the contour to minimize the energy function of the region based on the iteration number
Update the values of f1 and f2 and the gradient of the region using LBF
Perform morphological operations on the level segmented image
Extracted road network

Figure 1: Flow Chart of W ork

V. RESULTS AND DISCUSSION

The proposed classification system is implemented in the working platform of MATLAB(7.4).
For different values of c0, mask w, iteration values, we have tested on different satellite images and have obtained the following results.
To evaluate the performance of the proposed system, for different c0 values and mask sizes and scale parameter in Gaussian Kernel of 3.0 was taken and then the numbers of iterations were varied, as 100,150, 200, 250, 300, 350, 400,
450, 500 and 550 respectively. To extract the road network
from the given image, we have performed image dilation
and erosion based on the area of the objects. All the objects above an area of 40 have been taken as road.

Figure 2: Original Image

Figure No.3 co=2,w=200,it=400

Figure No.4 co=2,w=300,it=400

International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 6

ISSN 2229-5518

A method based on level segment evaluation and local binary fitting has been used to extract road network from high resolution satellite images. Using morphological operations after the LBF model aids the road network extraction. In this model the unwanted background regions are made to look black in colour and the extracted network is white in colour.

REFERENCES:

Figure No.5 co=4,w=200,it=400

Figure No.6 co=4,w=300,it=400

VI. CONCLUSIONS

[1] Automatic Road Network Extraction from High Resolution Satellite Imagery using Spectral Classification Methods by Andries Carl Haupteisch, Submitted in partial fulfilment of the requirements for the degree Magister Scientae in the Faculty of Engineering, Built Environment and Information Technology, Feb 2010

[2] J. B. Mena. State of the art on automatic road extraction for GIS

update: A novel Classification. Pattern Recognition Letters,

24:3037{3058, 2003}.

[3] S. Osher, J. A. Sethian, “Fronts propagating with curvature

dependent speed: algorithms based on Hamilton-Jacobi formulations”,

J. Comp. Phys., vol. 79, pp. 12-49, 1988. [4] M. Kass, A.Witkin, and D. Terzopoulos, “Snakes: active contour models”, Int’l J. Comp. Vis., vol. 1, pp. 321-331, 1987.

[5] J. A. Sethian, Level set methods and fast marching methods, Cambridge:

Cambridge University Press, 1999.

[6] K. Vogt, B. Scheuermann, C. Becker, T. B¨uschenfeld, B. Rosenhahn,

J. Ostermann , Automated Extraction Of Plantations From Ikonos

Satellite VII Symposium – 100 Years ISPRS, Vienna, Austria, July 5–7,

2010, IAPRS, Vol. XXXVIII, Part 7A.

[7] Chunming Li , Chenyang Xu , Changfeng Gui, and Martin D. Fox, Level Set Evolution Without Re-initialization: A New Variational Formulation, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05)

[8] Chunming Li, Chiu-Yen Kao , John C. Gore, and Zhaohua Ding ,

Implicit Active Contours Driven by Local Binary Fitting Energy, IEEE

transactions , 2007.

[9] Chunming Li, ChenyangXu, Adam W. Anderson, and John C. Gore, MRI Tissue Classification and Bias Field Estimation Based

on Coherent Local Intensity Clustering: A Unified Energy

Minimization Framework, IPMI 2009, LNCS 5636, pp. 288–299, 2009. [10] M. Rajeswari, K.S.Gurumurthy , S.N. Omkar, J. Senthilnath, L. Pratap Reddy, Automatic Extraction Of Road Networks Based On Normalized Cuts And Mean Shift Method For High Resolution Satellite Imagery, International Journal Of Advanced Engineering Sciences And Technologies Vol No. 3, Issue No. 2, 115 – 121,2011.

[11] Thierry G´ eraud, Jean-BaptisteMouret, Fast Road Network

Extraction in Satellite Images Using Mathematical Morphology and Markov Random Fields EURASIP Journal on Applied Signal Processing 2004 :16, 2503–2514

[12] Liu Jun-Wei, Feng Huan-Qing, Zhou Ying-Yue, Li Chuan-Fu, A

Novel Automatic Extraction Method of lung texturetree from Hrct

Images, Acta Automatica Sinica April 2009

International Journal of Scientific & Engineering Research Volume 2, Issue 10, October-2011 7

ISSN 2229-5518

1-BER IS)2011

http:1/www.ijserorg