ABSTRACT
This study presents a fast method for road network extraction in satellite images. Our approach comprises two essential phases: the first consists in extracting a curved object; the second phase makes it possible to generate the method of extraction defined in the first phase to be able to extract all the roads. The algorithm of detection consists of three successive stages: Passage of local information to the total information of road (by the detection of the homogeneous elements then linear components of road), optimization with the resolution of the large pixel (a large pixel is a whole of pixels in a window of the image) of which the objective is to obtain a binary vector X for the exact localization of a road at each couple of windows of the treated image and precise detection of the road network (a line determined by the points of passage which adjusts as well as possible on local detections of homogeneous elements of road, these points are detected in an automatic way). Consequently, an improvement of the algorithm defined above consists in applying a threshold to the image of homogeneous elements of road with an aim is to reduce the cost in computing times and to insulate the pixels which one regards as important. Lastly, we propose for the second phase a method based on the principle of the mathematical morphology which is based only on radiometric knowledge of the roads. This developed technique gives good results if the choice of points is made in an optimal manner that wants to say: to minimize the number of points in the linear shape and to maximize these points in the district circular. This algorithm of extraction can be applied to more figures than one will want to combine them and thus all the roads can be extracted.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/jas.2006.2185.2192
URL: https://scialert.net/abstract/?doi=jas.2006.2185.2192
INTRODUCTION
To develop geographical information system of a city passes in the first place by the obtaining of a card of the road network. In the case of card presence the obtaining of the road network takes place by hand that, this operation is expensive in time and risk to have mistakes by the lack of attention of the manipulator. In the case of the card lack (case of several Algerian cities) the manual technique becomes impossible. The remote sensing offers us of satellites images different spatial scales and for any places on earth. The reflection of several researchers is directly the extraction of the road network from satellites images (Postaire, 1987; Weber, 1995; Young and Fu, 1986). A satellite image is a numeric representation of a soil part. Every element of the image (pixel) presented by a numeric account that is according to properties radiometriques of soil, of the geometric, properties of image hold, of state of terrestrial atmosphere and the properties optics of the sensor. The automatic interpretations of the satellite image are a complex operation and require the specific algorithm development to applications wanted. The calm problem is to know is it possible the extraction of roads seen difficulties as the width reduced of roads by report has the size of the pixel, problem of shade and confusion radiometrique with other composing objects of soil. Two categories are generally distinguished. The local methods which are based on the radiometric criterion of the image, aim at the classification of the pixels as pertaining is at the zone road or the zone except road. One can quote: detectors of contours generic, detectors of watersheds, morphological operators (Daoud et al., 1989; Destival, 1986). The total methods which are based on the criteria radiometric and space of the image, aim at detection partial of the road network. One can quote: methods based on the graph theory and methods based on statistical and geometrical models (Jedynak, 1994; Merle and Zerubia, 1993; Airault and Jamet, 1995; Berzohar and Cooper, 1996).
Fig. 1: | General principle of the method of extraction |
METHODOLOGY OF EXTRACTION
Our approach is a development of the method suggested by B. Jedynak. It is summarized by the following diagram (Fig. 1). Knowledge which we used for the extraction of the road network rests at the same time on the radiometric aspect of the roads for the local calculation of the homogeneity and their space aspect (width, orientation and convexity) in order to supplement the process of extraction.
Algorithm of extraction
The algorithm of extraction comprises two essential phases: The first consists in generating a collection of possible ways and evaluating them thanks to a function cost on the homogeneity of elements of road in order to preserve the best way. Each way is composed of segments of line chosen locally according to the criterion of homogeneity. The fact of then optimizing this criterion on a whole of segments makes it possible to adapt to the form of the road. The optimal way is that which minimizes the variance calculated in the possible directions of propagation on lengthened vicinities length and width variables, which maximizes the distance covered and which is most rectilinear. With this intention, we must detect homogeneous elements then linear components of road. The second makes it possible to combine the results obtained in the first phase (set of ways of road) while being pressed on a morphological operator (transformations of wholes) in order to obtain an image whose objects are only the roads. To value the performance of the method developed we chose an image satellite to high spatial resolution.
Fig. 2: | Original image |
The chosen image represents a part of the Oran city (Algeria) acquired by the satellite Indian IRS1-C with a spatial resolution of 5 m to soil. She covers a region on the one hand strong urban density and composed of the variable landscape, the roads composite of this region is the main roads and the secondary roads (Fig. 2).
EXTRACTION OF A WAY OF ROAD
Local calculation of the homogeneity: The detection of homogeneous elements of road requires the construction of four masks for each direction: 0, π/4, π/2 and 3π/4. One recognizes for each mask a zone road and two zones out road. It is a question of measuring for each mask: the relative homogeneity inside the zone road of the mask and relative heterogeneity between the zone road of the mask and the zone out road. Consider S a system of neighbours. Clique c is a nonempty subset of S, such as two points distinct from c are neighbours. The various masks are represented in the following Table 1.
Table 1: | Various masks for any directions |
Criterion of homogeneity: Consider: P: set of sites pixels of the original image, xp: radiometric value of the pixel p, xp∈{0, ,255} and k: direction of propagation of p, k∈{0, π/4, π/2, 3π/4}.
In each site p we calculate value rp in the following way checking the criterion of homogeneity:
Consider: Rk, Rk and Rk: zone road, 1st zone out road and 2nd zone out road, respectively. Nk, Nk and Nk: numbers the cliques of the Rk zone, between the zone Rk and Rk and between the zone Rk and Rk, respectively. Sk, Sk et Sk: values allowing to measure the homogeneity inside Rk, relative heterogeneity between Rk and Rk and relative heterogeneity between Rk and Rk, obtained by:
(1) |
Where:
(2) |
In each direction of propagation k, one calculates the following minimal of value:
(3) |
Value rp corresponds to the maximum of the four values mink corresponding to the four directions of propagation: 0, π/4, π/2, 3π/4.
(4) |
In order to be able to eliminate the too low values from rp, one determines for each site p, the adjacent points which are in the same direction and around him. The number of the adjacent points corresponds to the parameter f which definite size of the window fxf as we will see it in the following section: If the site p corresponds to the maximum value of the radiometric values of all the adjacent points then its value rp is preserved if not it is put at zero.
Results: The result of this stage is a digital image where the roads present on the original image are detected but appear with difficulty because of the blur due to the other objects like the obstacles (trees, vehicles, etc.). The image of homogeneous elements of road (Fig. 3) obtained will be used on the one hand for the threshold (the goal: detection of the points of passage) and on the other hand for the detection of linear components of road (the goal: to have an indication on the localization and the orientation of the layout of road).
Fig. 3: | Image of homogeneous elements of road of the image of Fig. 3 with t = 40, f = 2 |
Fig. 4: | Threshold of the image of Fig. 3 between two thresholds 50 and 170 |
Threshold: With an aim of reducing the cost in computing times, we applied a threshold to the image of homogeneous elements of road obtained in the preceding section; this type of methods takes into account only the values of levels of grey of a point to decide on its membership of the way of road. Indeed, the idea is to segment the image in two areas: road and not road. The threshold requires two thresholds, because it is difficult to obtain a total threshold for all the image: If a point which one considers an element of road finds between the two selected thresholds its value is 0 if not its value is 255.
Result: The result of this stage is a binary image of values 0 and 255. The roads present on the original image are detected better if this one is an semi-urban image that in the case of an urban image (Fig. 4).
Detection of linear components of road
The principle of this stage is as follows: First of all one segments the image of homogeneous elements of road in windows of size fxf (each window will represent a point of passage of the layout of road), then one associates with each couple windows a line passing as well as possible by all the points of the two windows by using the transform of Hough:
(5) |
Where, ξ: signed orthogonal distance from the line at the point (x0,y0), it must be discredited in ξ1,, .,ξm. m is fixed. (x0,y0): origin point which we locate between the two windows. : angle formed by the line and the horizontal one, it must be discredited in θ1, ,θn. n is fixed.
Result: The result of this stage is a vector Y, information of probability for the presence of a segment of road, all the more near to value 1 that the extraction in each couple of windows was good; this information is obtained by standardizing the greatest value of the points having even angle θp∈{θ1, ,θn} and even distance ξq∈{ξ1,, .,ξm}, between 0 and 1.
Choice of the best way of road: A way of road will be defined by a line which is a chain of segments connected to each other. It is determined by the points of passage defining the segments, which adjust as well as possible on local detections of homogeneous elements of road. Indeed, one wants to reconstitute the shape of a curved object (traced road) after his digitalization. To solve this problem, it is necessary to find the means of building curves from smaller elements: segments of curves which could be drawn from small segments of line. The robustness of the algorithm of the choice of the best way of road is ensured by a module of treatment which uses two information coming on the one hand from the binary image obtained by threshold (determination of the points of passage) and on the other hand of the segmented image (an optimization of a function cost of which the objective is to obtain a binary vector X for the exact localization of a road at each couple of windows of the treated image).
Function cost and optimization: The function cost proposed by B. Jedynak is written in the following way:
(6) |
where: G (X, Y) = ∑s∈S XS (c-Ys)
c∈[0,1], s is a couple of site-windows and S is a graph made up of a whole of arcs joining two adjacent tops (a couple of windows).
V(X) is a function describing the constraints of regularity which one asserts a priori. V(X) = 0 for a configuration X which is a way on the graph S. λ∈[0,1] a parameter being used to force the convexity of a configuration in a site in spite of a bad detection of segment of road in this site. The algorithm of optimization results from the algorithms of research of the shortest way in a value graph.
Fig. 5: | Precise extraction of a way of road of the image of Fig. 3 |
It consists in optimizing the function cost defined above under constraint V(X) = 0 and calculating configuration X definite as follows: X=ArgminX,V(X)=0G(X,Y).
A configuration road carrying out the minimum of the function cost H(X,Y) in X is equivalent to the best probability of a probability P in X. The function P is defined in the following way:
(7) |
From where the algorithm of optimization is written as follows:
• | Choice of an initial value c, c∈[0,1]. |
• | Calculation of Xc = arg minX ∑s∈S Xs(c-Ys). |
• | If c = P(X'c) then X = Xc if not c = P(X'c) and go to 2. |
Precise extraction of the way of road: We propose at this stage a rather effective method which allows the precise
extraction of the way of road. The method is decomposed into two stages: determination of the points of passage of the layout of road and connection between each two points by the use of the concept of connectivity. First of all, the points of passage are given like those having a value of level of grey 0 (pixels coming from the binary image obtained by threshold and which are located on the layout of road) whose position is given by the manual seizure (the manual seizure of the nudes of the road network is fast compared to the other cartographic topics like buildings, vegetations, etc (Yu et al., 1999) although it presents the disadvantage not to be very powerful on the level of the reduction of the quantity of data) and who must satisfy the selection criterion (the points have the same direction of propagation and belong of a road ensured by the result of the optimization of the function cost). Then, the tracing of the curve is carried out by a modeling of this one by a sum of smaller segments of curves which could be drawn from small segments of line.
Modeling: Being given the P0(x0,y0), , Pn(xn,yn) points, one wishes to find a curve passing by these points (Couloignor and Ranchin, 2000). Consider f(z) this curve:
(8) |
where small segments.
Algorithm
• | To fix the number of nudes n. |
• | To enter the starting point P0 and the arrival point Pn. |
• | To repeat |
• | To determine the following point Pi. |
• | If the selection criterion is satisfied (of the same direction than the precedent and belongs to a window where there is an exact localization of a road) then one retains this point if not to choose another point. |
Until the arrival point is reached.
(9) |
Remarks: For the definition of the function φi,n(z), many polynomials exist, one can citer: Lagrange, Hermite, Bernstein, etc. For our case we chose Bernstein polynomial. The larger N is sufficiently, the more than there will be a good extraction. If the road were not limited with the two points (initial and final), the risk of assignment of points of image to an erroneous class could be important. This situation would lead to a bad extraction of the zone road.
Result: The result of this stage is an image comprising a way of road. It is a satisfactory result by comparing it with the original image (Fig. 5).
EXTRACTION OF THE ROAD NETWORKS
In order to be able to generate the method of extraction defined in the first phase, we propose in this part an approach based on the principle of mathematical morphology, (Destival, 1986; Haralick et al., 1987; Géraud and Mouret, 2004) which is based only on radiometric knowledge of the roads. Mathematical morphology consists in defining objects as sets of pixels and studying the shape of these objects and the relations which exist between them using sets transformations (dilation, erosion, opening, closing, union, intersection, etc), in this case we used the union operation.
Algorithm: The algorithm of the extraction is as follows:
• | To traverse all the images of which each one of them comprises only one way of road (result of the first phase) in parallel. |
• | To examine the corresponding nudes and to build the new image: If the nudes are black then the resulting nude is black. If the nudes are white then the resulting nude is white. If one of the nudes is black then the resulting nude is black. |
RESULTS AND DISCUSSION
The result of this phase is an image comprising more than one way of road (a road network). To display this result, first of all one will extract other ways of road of the one of the original images of Fig. 3. By taking for example the image of Fig. 3 and following the same stages of the algorithm of extraction, one obtains the following ways of road. Then, by applying the morphological operator the union, to figures chosen among the figures one obtains an image of road networks (Fig. 6).
We present two images: original image and road image (Fig. 7). By a visual comparison we can make the following remarks:
Road (1): The curve is similar to the real and same curve the shape of the circle dawned is visible (R1). As specifying points of the curve we took several points of the circle dawns to force the passage of the curve by these points. The result was good.
Road (2): The curve to the shape of the real curve on the other hand his/her/its shape takes the shape of the circle dawns (R2). As specifying points us was unaware of points of the circle dawns, the gotten curve is bad in this circular region. Points of different curve intersections are precise.
Fig. 6: | A network roads obtained by addicting all precedent images |
Fig. 7: | (1) Road 1, (2) Road 2, 1 Round dawns R1 and R2 Round dawns 2 |
This developed technique gives good results if the choice of points is made in an optimal manner that wants to say: to minimize the number of points in the linear shape and to maximize these points in the district circular. This algorithm of extraction can be applied to more figures than one will want to combine them and thus all the roads can be extracted.
CONCLUSIONS
We presented in this article an approach resulting from a development of the method of detection of road networks from satellite images suggested by B Jedynak. This approach is systematic; it currently brings solutions to the difficulties encountered in existing methods and takes account of the improvements made by the other researchers. It generally deals with the problem of extraction of the road network by taking account of the characteristics as well local as total of the road networks. The systematic method comprises two phases. The first phase consists in generating a collection of possible ways, sufficient length to be significant on a road scale and evaluating them thanks to a function cost on the homogeneity of elements of road in order to preserve the best way. Each way is composed of segments of line chosen locally according to the criterion of homogeneity. The fact of then optimizing this criterion on a whole of segments makes it possible to adapt to the shape of the road. The optimal way is that which minimizes the variance calculated in the possible directions of propagation on lengthened vicinities length and width variables, which maximizes the distance covered and which is most rectilinear. This way is extracted while being based on the one hand on external data, points of passage (points which are located on the layout of road of the image obtained by threshold) whose position is given by the manual seizure (the manual seizure of the nudes of the road network is fast compared to the other cartographic topics like buildings, vegetations, etc. although it presents the disadvantage not to be very powerful on the level of the reduction of the quantity of data) and who must satisfy the selection criterion (the points have the same direction of propagation and belong to the windows where there is an exact localization of a road ensured by the result of the optimization of the function cost). And in addition, by modeling the layout of road by a sum of smaller segments of curves which could be rawn from small segments of line (one connects very new point detected to the remainder of the way, at the point nearest in the direction to propagation). The second phase makes it possible to generate the method of extraction defined in the first phase whose objective is to obtain an image of road network while being based on the principle of the mathematical morphology which is based only on radiometric knowledge of the roads. This method can easily be adapted to other image processing fields where the recognition of curvilinear structures is involved.
REFERENCES
- Airault, S. and O. Jamet, 1995. Detection et restitution automatique du reseau routier sur des images Aeriennes [Detection and automatic restitution of the road network on pictures aerial]. Traitement Du Signal, 12: 189-200.
Direct Link - Barzohar, M. and D.B. Cooper, 1996. Automatic finding of main roads in aerial Images by using geometric stochastic models and estimation. IEEE Trans. Pattern Anal. Mach. Intell., 18: 707-721.
Direct Link - Daoud, M., C. Roux and A. Hillion, 1989. Une application de la theorie des graphes a l'extraction automatique des reseaux de communication dans les images SPOT [An application of the graph theory to the extraction automatic of networks of communication in the SPOTL image]. Technical Report, INRIA, 1989. pp: 699-701.
- Geraud, T. and J. Mouret, 2004. Fast road network extraction in satellite images using mathematical morphology and markov random fields. EURASIP J. Applied Signal Process., 2004: 2503-2514.
CrossRefDirect Link - Haralick, R.M., S.R. Sternberg and X. Zhuang, 1987. Image analysis using mathematical IEEE Trans. Pattern Anal. Mach. Intel., 9: 532-550.
CrossRef - Yu, S., M. Berthod and G. Giraudon, 1999. Toward robust analysis of satellite images using map information-application to urban area detection. IEEE Trans. Geosci. Remote Sens., 37: 1925-1939.
CrossRef