| GISdevelopment.net ---> AARS ---> ACRS 1998 ---> Poster Session 2 |
Road Network Detection by
Mathematical Morphology
Shunji Murai, Chunsun
Zhang
Space Technology Applications and Research Program
Asian Institute of Technology
Klong Lunag, Pathumthani 12120, Thailand
E-mail: murai@ait.ac.th , chunsun@ait.ac.th
Space Technology Applications and Research Program
Asian Institute of Technology
Klong Lunag, Pathumthani 12120, Thailand
E-mail: murai@ait.ac.th , chunsun@ait.ac.th
Keywords: Road Detection, Mathematical
Morphology, Trivial Opening, Granulometry.
detection from high resolution digital image by
mathematical morphology operation is presented. The approach proposed in
this paper firstly classifies image to find road network region, then
morphological trivial opening is adopted to avoid noises. The developed
method has been tested on the simulated image with 1meter resolution. The
result shows that mathematical morphological provides an effective tool
for automated road network detection.
1. Introduction
The extraction of road from digital image has drawn considerable attention in the past years. The strategies fall into two broad categories. In semi-automatic schemes, an operator selects a few mark points of a road segment and then an algorithm based on dynamic programming or least square B-spline active contour model finds the roads (Gruen and Li, 1994, 1997, 1997). Other semi-automatic approach are based on road tracking (Makeown et al. 1988, Vosselman et al. 1995) that start from a given point and a given direction after extracting parallel edges or by extrapolating and matching of profiles. These semi-automatic approaches can be extended to fully automatic operation by means of automatic seed point detection (Zlotnic et al. 1993, Baumgarter et al. 1997, Mayer et al. 1997). Other fully automatic approaches are based on line extraction methods (Wang et al. 1992, Heipke 1995, Gong and Wang 1996) or knowledge-based methods (Stilla et al. 1994, Rusknone 1996, Marlies et al. 1996, Trinder et al. 1997).
Usually line extrapolation method works reasonably well on the low resolution image. However, there can be many other features with properties similar to road which will be extracted as well. Knowledge-base method involves the use of GIS and rules, but there are still a lot of problem to be solved to obtained satisfactory result from remote sensing data as digital images.
Several road models were developed by researchers. The road appearance in imagery depends on sensor sensitivity and its resolution. The authors' approach will restrict to high resolution gray scale image with 1meter resolution. A road in high resolution image is light continuous and homogeneous region so that a good contrast to its adjacent area. One road usually has a constant width, and road at different level has different width, roads from a network.
The objective of this study is to develop an algorithm for automated road network detection from 1meter high resolution image. After road is segmented from background Morphological trivial opening has been developed for the purposes: (!) to perform granulometry analysis and obtain size information of road network, and (2) to extract road network from preprocessed image and differentiate other feature with similar properties of road.
2. Morphological Trivial Opening and Granulometry
Mathematical morphology is a set theory approach, developed by Serra (1982). Based on a formal mathematical framework, mathematical morphology provides an approach to the processing of digital images that is based on geometrical shape.
2.1 Morphological Trivial Opening
Trivial opening (denoted hereafter TO) is defined by Serra and Vincent (1992). Let X be an image, {X(n)\n =1, 2, 3, …..N] be a series of connected components in the image, x(i0 be a point in X(i), we define the trivial opening with a criterion T, as follow < /DIV >
1. Introduction
The extraction of road from digital image has drawn considerable attention in the past years. The strategies fall into two broad categories. In semi-automatic schemes, an operator selects a few mark points of a road segment and then an algorithm based on dynamic programming or least square B-spline active contour model finds the roads (Gruen and Li, 1994, 1997, 1997). Other semi-automatic approach are based on road tracking (Makeown et al. 1988, Vosselman et al. 1995) that start from a given point and a given direction after extracting parallel edges or by extrapolating and matching of profiles. These semi-automatic approaches can be extended to fully automatic operation by means of automatic seed point detection (Zlotnic et al. 1993, Baumgarter et al. 1997, Mayer et al. 1997). Other fully automatic approaches are based on line extraction methods (Wang et al. 1992, Heipke 1995, Gong and Wang 1996) or knowledge-based methods (Stilla et al. 1994, Rusknone 1996, Marlies et al. 1996, Trinder et al. 1997).
Usually line extrapolation method works reasonably well on the low resolution image. However, there can be many other features with properties similar to road which will be extracted as well. Knowledge-base method involves the use of GIS and rules, but there are still a lot of problem to be solved to obtained satisfactory result from remote sensing data as digital images.
Several road models were developed by researchers. The road appearance in imagery depends on sensor sensitivity and its resolution. The authors' approach will restrict to high resolution gray scale image with 1meter resolution. A road in high resolution image is light continuous and homogeneous region so that a good contrast to its adjacent area. One road usually has a constant width, and road at different level has different width, roads from a network.
The objective of this study is to develop an algorithm for automated road network detection from 1meter high resolution image. After road is segmented from background Morphological trivial opening has been developed for the purposes: (!) to perform granulometry analysis and obtain size information of road network, and (2) to extract road network from preprocessed image and differentiate other feature with similar properties of road.
2. Morphological Trivial Opening and Granulometry
Mathematical morphology is a set theory approach, developed by Serra (1982). Based on a formal mathematical framework, mathematical morphology provides an approach to the processing of digital images that is based on geometrical shape.
2.1 Morphological Trivial Opening
Trivial opening (denoted hereafter TO) is defined by Serra and Vincent (1992). Let X be an image, {X(n)\n =1, 2, 3, …..N] be a series of connected components in the image, x(i0 be a point in X(i), we define the trivial opening with a criterion T, as follow < /DIV >
Trivial opening provides a practical mean for object
detection and identification. It does not affect the shape and size of the
connected regions that are preserved because it preserves the entire
connected regions. Since a road in high resolution image is appeared as a
narrow homogeneous area forming whole network, the criterion can be
selected as the long axes of minimum ellipse which encloses an object.
Trivial opening for road detection is expressed as TO_ROAD_DETECTION = { X
| Long axis of minimum ellipse enclosing X(i) >= T} The connected
components are reached by morphological reconstruction. Suppose one pixel
Y in Xi is searched, then reconstruction Xi from Y is obtained by
iterating elementary geodesic dilation of Y inside Xi until stability.
< /DIV>
2.2 Granulometry
The criterion used in trivial opening can be regarded as a threshold which should be determined from the image analysis with respect to granulometry or pattern spectrum. The idea is to apply opening operation to decompose an image through a series of structure elements with a specific shape. The opened image are compared with the original image to generate measures with respect to different size of structure element with same shape.
Let S(n) = 1,2, ………N be series of structure elements, and X be original image, A(n), n = 1,2, ……….N is a sequence of images being opened as follows < /DIV >
A(0) = AOS0, ……., A(n) = AOSn
The criterion used in trivial opening can be regarded as a threshold which should be determined from the image analysis with respect to granulometry or pattern spectrum. The idea is to apply opening operation to decompose an image through a series of structure elements with a specific shape. The opened image are compared with the original image to generate measures with respect to different size of structure element with same shape.
Let S(n) = 1,2, ………N be series of structure elements, and X be original image, A(n), n = 1,2, ……….N is a sequence of images being opened as follows < /DIV >
A(0) = AOS0, ……., A(n) = AOSn
Since opening is anti-extensive, A(n) < A(m) for
n>=m. let C[A(N)] be the measure of the cardinality of A(n), the
following relation are obtained. < /DIV>
C[A] > = C[A(0)]>= C[A(1)]>= C[A(2)]………>=C[A(N)]
Fig .1 Test Images and Historgram
C[A] > = C[A(0)]>= C[A(1)]>= C[A(2)]………>=C[A(N)]
Then the size distribution is defined as 
C[A(n)]/C[A] is percentage of the filtered objects. SD increases from 0 to 1 and can be regarded as a probability distribution function. C[A(n)]/C[A], SD therefore provide shape-size description of objects in image. Trivial opening can also be used to perform granulometery. However, the notion of structure element size must be reconciled with that of an increasing criterion T. this can be achieved by ordering a criterion T in a set of criteria T(i), I= 1,2,…..N under the following constraints: if a connected component CC does not satisfy Ti, it does not satisfy Ti+1.
3. Experiment on road detection
An experiment was designed and conducted to detect road network from a simulated 1m high resolution image in Toronto, Canada as shown in fig.1. Image is orthorectified and distributed by Earth Watch Inc. the roads in the image make continuous region which form a network, Houses are very dense in the image, some of which roofs almost similar spectral characteristics as roads, and trees are dark in the image along the road standing with the location close to houses.
C[A(n)]/C[A] is percentage of the filtered objects. SD increases from 0 to 1 and can be regarded as a probability distribution function. C[A(n)]/C[A], SD therefore provide shape-size description of objects in image. Trivial opening can also be used to perform granulometery. However, the notion of structure element size must be reconciled with that of an increasing criterion T. this can be achieved by ordering a criterion T in a set of criteria T(i), I= 1,2,…..N under the following constraints: if a connected component CC does not satisfy Ti, it does not satisfy Ti+1.
3. Experiment on road detection
An experiment was designed and conducted to detect road network from a simulated 1m high resolution image in Toronto, Canada as shown in fig.1. Image is orthorectified and distributed by Earth Watch Inc. the roads in the image make continuous region which form a network, Houses are very dense in the image, some of which roofs almost similar spectral characteristics as roads, and trees are dark in the image along the road standing with the location close to houses.
Fig .1 Test Images and Historgram
The first step is to separate road from background. As
the image resolution is high, road network appears to be area with certain
width rather than thin lines, this creates an opportunity for
classification based method (Benjamin et al. 1990, Gong and Wang 1996).
Image segmentation in this study is achieved through ISODATA (Iterative
Self Organizing Data Analysis Technique).
Morphological trivial opening is then applied with the long axis of minimum ellipse that encloses an object to eliminate houses. Granulometry analysis gives size distribution of objects in image as shown in fig.2 with C[A(n)]/C[A] against T. it can be seen with T>=110, the remaining objects are not changed until T>=440, all objects are filtered out. The trivial opening with this criterion T>=110 preserve the road area and filters out almost all the houses and small clusters of noises as well. Morphological closing is applied to fill small holes on the road caused by pixel spectral difference. An initially extracted road network image is then obtained as shown in fig. 3. Some houses are still remained connecting with road network via paths after trivial opening, further processingis needed to remove small paths and these houses.< /DIV>
Fig.2 Size Distribution of Test Image
Fig.3 Initially Extracted Road Network
Fig.4 Final Result of Road network Detection with Thinned Center Line Superimposed on Original Image
Morphological trivial opening is then applied with the long axis of minimum ellipse that encloses an object to eliminate houses. Granulometry analysis gives size distribution of objects in image as shown in fig.2 with C[A(n)]/C[A] against T. it can be seen with T>=110, the remaining objects are not changed until T>=440, all objects are filtered out. The trivial opening with this criterion T>=110 preserve the road area and filters out almost all the houses and small clusters of noises as well. Morphological closing is applied to fill small holes on the road caused by pixel spectral difference. An initially extracted road network image is then obtained as shown in fig. 3. Some houses are still remained connecting with road network via paths after trivial opening, further processingis needed to remove small paths and these houses.< /DIV>
Fig.2 Size Distribution of Test Image
Fig.3 Initially Extracted Road Network
Fig.4 Final Result of Road network Detection with Thinned Center Line Superimposed on Original Image
Since the width of path is less than that of the main
road, opening operation with the structure element whose size is smaller
than main road but slightly larger than that of path can remove paths.
Another effect of this operation is that houses connected with road
network via paths are separated. Again trivial opening is applied to
remove isolated houses. Since trees standing near road and cast shadow on
it, some road parts are partially invisible, these parts are thinner in
initially extracted road network image. The side effect of opening is that
it also removes these road parts. It is necessary to develop tools to
reconstruct these road parts. A window operation based on mathematical
morphology is designed for this purpose. The procedure is as follows: thin
Opened image to one pixel wide, locate endpoint pair in a given range,
decide a local window which includes endpoint pair, then recover contents
of this window from previous initially extracted road network image.
The final operation of thinning gives the approximate road line as shown in fig. Overlaid on the original image.
4. Discussion and Conclusion
line based method for automatic road network extraction from high resolution image involves the edge detection, thresholding and edges linking. The difficulties arise when threshold selection and linking based on conditions such as proximity, orientation and some geometrical constraints, with the complexity of image such as occlusions and difference of materials on both sides of road, these conditions normally are not satisfied. This makes line based method less effective for high resolution images.
In this paper we proposed an approach to detect road network from high resolution image using mathematical morphology operations, particularly trivial opening and its application to granulometry which have not been applied to remote sensing image for feature extraction by any other researchers. The algorithm is based as the connected components. Trivial opening has been developed to preserve the whole road network through filtering noises. Granulometry analysis was performed with trivial opening to provide size information of objects in image. The result showed that this approach can provide sufficient information about successive steps for automatic road extraction with better result as compared with the existing researches. The problem still remain for road surfaces that are completely broken caused by tree shadow, because there is no any other information in the area supporting to link it with road network. Difficulty also arise where a house is connected to road network through wider path. The proposed approach can be used as an initial step for automated road network extraction for providing the approximation and hence reducing searching space.
In conclusion, a combination of trivial opening and a new concept of granulometry was successfully demonstrated to automatically detect road network with the wider width from high resolution image.
References
The final operation of thinning gives the approximate road line as shown in fig. Overlaid on the original image.
4. Discussion and Conclusion
line based method for automatic road network extraction from high resolution image involves the edge detection, thresholding and edges linking. The difficulties arise when threshold selection and linking based on conditions such as proximity, orientation and some geometrical constraints, with the complexity of image such as occlusions and difference of materials on both sides of road, these conditions normally are not satisfied. This makes line based method less effective for high resolution images.
In this paper we proposed an approach to detect road network from high resolution image using mathematical morphology operations, particularly trivial opening and its application to granulometry which have not been applied to remote sensing image for feature extraction by any other researchers. The algorithm is based as the connected components. Trivial opening has been developed to preserve the whole road network through filtering noises. Granulometry analysis was performed with trivial opening to provide size information of objects in image. The result showed that this approach can provide sufficient information about successive steps for automatic road extraction with better result as compared with the existing researches. The problem still remain for road surfaces that are completely broken caused by tree shadow, because there is no any other information in the area supporting to link it with road network. Difficulty also arise where a house is connected to road network through wider path. The proposed approach can be used as an initial step for automated road network extraction for providing the approximation and hence reducing searching space.
In conclusion, a combination of trivial opening and a new concept of granulometry was successfully demonstrated to automatically detect road network with the wider width from high resolution image.
References
- Baumgartner, A., Steger, C., Mayer, H., Eckstein, W., (1997): Mulit-Resulotion, Semantic Objects, and context for Road Extraction. Workshop on semantic modeling for the acquisition of topographic information from images and maps, W. Forstner and L. Plumer (Editors), Birkhauser Verlag, Basel, pp. 140-156.
- Benjamin, S. and L.Gaydos, Spatial resolution requisition for automated cartographic road extraction, PE&RS, 56-1, 1990
- Gong, P., and J.Wang, Road network extraction from airborne digital cameral data. Proc. of the Second International Airborne Remote Sensing Conference and Exhibition, San Francisco, California, 27-27 June 1996
- Gruen, A., Li, H., Semi-automatic road extraction by dynamic programming, international Archives of photogrammetry and Remote Sensing, 1994, Vol. 30, part 3/1, pp. 324-332.
- Gruen, A., Li, H., Semi-automatic linear feature extraction by dynamic programming and LSB-Snakes, Photogrammetric Engineering and Remote Sensing, Vol. 63(8), pp. 985-995. 1997
- Gruen, A. and H.Li, Linear Feature Extraction with 3-D LSB-Snakes, Automatic Extraction of Man-Made Objects from Aerial and Space Image (II), A. Gruen, E.P. Baltsavias and O.Henricsson (Editors), Birkhauser Verlag, Ascona, 1997, 287-298
- Heipke, C., C.Steger, R.multhammer, a Hierarchical approach to automatic road extraction from aerial imagery, SPIE - Aerosense 1995 Symposium, proceeding, Orlando, USA, April 17-21, 1995, Vol. 2486, S. 222-231.
- Marlies de Gunst, Knowledge-based interpretation of aerial images for updating of road maps, PhD thesis, Delft University of Technology, the Netherlands, 1996
- Mayer, H., Laptev, I., Baumgartner, A., Steger, C., (1997): Automatic road extraction based on multi-scale modeling, context and snakes. INTERNATIONAL Archives of Photogrammetry and Remote Sensing, Vol. 32, part 3- 2W3,pp. 106-113.
- Ruskone, R., (1996): Road network automatic extraction by local context interpretation: application to the production of cartographic data. PhD thesis, Marne-La-Vallee University, France
- Serra, J., Image Analysis and Mathematical Morphology, Vol. 1, 2 Academic Press, London, 1982
- Serra, J., and L. Vincent, An Overview of morphological filtering, Circuits systems Signal Process 11, No.1 1992, 47-108
- Stilla, U., Hajdu, A., (1994): Map-aided structural analysis of aerial images. International Archive of photogrammetry and Remote Sensing, Vol.30, part 3/2, pp. 475-482.
- Trinder, J.C., Wang, Y., Sowmya, A., Palhang, M., (1997): Artificial Intelligence in 3-D Feature Extraction. Automatic Extraction of Man-Made objects from Aerial and Space Images (II), A. Gruen, E.P. Baltsavias and O. Henricisson (Editors), Birkhuser Verlang, Ascona, pp. 257-266.
- Vosselman, G., J..de Knecht, Road Tracing by Profile Matching and Kalman Filtering, Automatic Extraction of Man-Made Objects from Aerial and Space Image, pp. 265-274, Basel, 1995
- Wang, J., Treitz, P.M., Howarth, p.j., (1992); Road network detection from SPOT imagery for updating geographical information system in rural-urban fringe, Int. J. Geographical Information Systems, Vol. 6, no.2, pp.141-157.
- Zlotnick, A. and P.D.Carnine. Finding Road Seeds in Aerial Images, Computer Vision, Graphics, and Image Processing: Image Understanding, 57: 243-360, 1993