Received 24 October 2014; revised 24 November 2014; accepted 23 December 2014

ABSTRACT

Some studies about road vector map change detection were done in this paper. Firstly, on the basis of old road vector data, the original high resolution remote sensing image was cut into segments. Then, gray analysis and edge extraction of those segments were done so that changes of roads could be detected. Finally, according to the vector data and gray information of roads which were not changed, road templates were extracted and saved automatically. This method was performed on the World View high resolution image of certain parts in the country. The detection result shows that detection correctness is 79.56% and completeness can reach 97.72%. Moreover, the extracted road templates are essentials for the template matching method of road extraction.

Keywords:

Road Vector, High Resolution Remote Sensing Image, Edge Extraction, Change Monitoring

1. Introduction

Nowadays, researchers tend to study the road information on remote sensing images from two aspects, road extraction and road change detection.

Considerable work on the study of road extraction has been done by domestic and foreign scholars. The ribbon snake and ziplock snake methods were used for extracting road line by Laptev I [1] . Xiangyun Hu [2] and S. R. Park and T. Kim [3] used the least squares template to detect road. After obtaining the center points of road line according to parallel lines information, the candidate points were extracted with a self-organizing road map (SORM) to connect to the road network [4] . As proposed by Q. P. Zhang [5] , the road cluster is automatically identified using a fuzzy classifier based on a set of predefined road surface membership functions. An iterative and localized Radon transform is developed for the extraction of road, which is grouped into a road network. M. Wang, C. J. Luo, C. W. Zhou, et al. [6] studied road geometry model as a recognition of the road and M. Barzohar and D. B. Cooper [7] build geometric-probabilistic models for road image generation. Z. J. Huang, J. F. Zhang and F. J, Xu [8] presented a multi-stage method, consisting of automatic information extraction and semi- automatic post-processing, which aimed to extract better road information from images. Although a lot of researches on the roads have been done, it is still difficult to extract various types of road completely because of the complexity of the road information.

In view of the difficulty of extracting the road, many researchers consider using existing road information to detect the change of road information. As pointed by [9] , there are two modes of road change detection: the first is detecting after change detection, and the second is detecting in synchronization with the image registration. Matching remote sensing images with the existing road vectors can be of help to detect the change of road information, according to M. Dong, H. T. Zhang, X. K. Zhu, et al. [10] . Also, H. J. Ma and N. Lu [11] implemented extraction of road segments in the earthquake disaster area by matching the new images with the old ones.

Road change detection includes two types, namely disappearance of the existed road and extraction of the new road. The method proposed by this paper mainly solves the change detection of the old roads. At the same time, this method extracts the road template library, which provides important information for detection and extraction of new roads.

The images and vectors used in this paper are processed by the method of automatic registration proposed by L. P. Lu, Y. Zhang, P. J. Tao, et al. [12] . In addition, in this paper, the Hough transform based on the infinite symmetric exponential filter (ISEF) is presented to gain road edges, and then road change detection follows.

2. Change Detection Method

This section introduces the detection algorithm for old vectors based on new high resolution remote sensing image. The specific process flow chart is shown as followed in Figure 1.

2.1. Douglas Peucker Algorithm for Vector Compression

The purpose of curve compression is to reduce the number of points required to present the line within the allowable error limit. Based on the idea of the curve compression, Douglas Peucker algorithm [13] was adopted in this paper. With referenced Figure 2, the compression of the vector P₁P_n is described as follows,

1) Calculate all the distances from vector nodes (P₂, P₃, …, P_n−1) to line P₁P_n;

2) Find the farthest point P_i and record the distance (D_i) from P_i to line P₁P_n;

3) Keep point P₁ and point P_n and remove all other points if D_i is less than the given threshold;

4) Iterate steps (1)-(3) for P₁P_i and P_iP_n respectively if D_i is more than given threshold.

The threshold is set to 3 pixels in this paper.

2.2. Coordinate Transformation for Segment

The original image is divided into segments based on vector segment’s bounding rectangle. After coordinate transformation, the horizontal axis parallels with the direction of vector segment and vertical axis is perpendicular to the direction of vector. In the new coordinates, direction of roads is approximately closer to horizontal axis, which provides convenient conditions for extracting edges and detecting changes.

2.3. ISEFHough Edge Extraction

2.3.1. ISEF Filtering Algorithm

The purpose of image preprocessing is to weaken false edges generated by the image noise and enhance right edge information. M. Sharifi, M. Fathy, M. T. Mahmoudi [14] discussed the advantages and disadvantages of some edge detection algorithms and showed that the infinite symmetric exponential filter (ISEF) exhibited better performances under noisy conditions. ISEF derives from IIR exponential smoothing filter, but it is not sensitive to noise and easy recursive. It can calculate the direction of edge while detecting edges [15] . Besides, ISEF extract less false edges and keep more significant ones, which are just what we need.

One-dimensional ISEF can be written as,

(1)

where, and

(2)

(3)

Exponential filter can be implemented using recursive algorithm, and for two-dimensional images: define the input image as s₀(x, y), a two-dimensional exponential filter as f(x, y) and the output image as s(x, y), so

(4)

Thanks to the separability of two-dimensional exponential filter, s(x,y) can be expressed as,

(5)

2.3.2. ISEFHough Line Extraction Algorithm

Hough transform edge detection takes advantage of voting statistics method, which avoids false edges caused by partial occlusion. ISEFHough not only extracts road edges, but also accurately computes gradient direction of edge points. s_x(x, y), s_y(x, y) can be derived from the Formula (5),as follows,

(6)

Therefore, it can be obtained that

Gradient Magnitude:

(7)

Gradient Angle:

(8)

The straight line detection algorithm is described as follows,

1) Calculate the partial derivatives s_x(x, y), s_y(x, y) of each pixel, according to the Formula (6).

2) Compute the Gradient Magnitude and Gradient Angle in accordance with the Formulas (6)-(7), and find edge point by determine whether the obtained point has maximum magnitude along the gradient direction.

3) Discretize parameter space (k, b), forming a two-dimensional M × N matrix accumulation para[i, j]. First, this accumulation matrix is initialized to zero for all the cells. Then, for each edge point, according to y = k × x + b, use increment iteration to obtain para[i, j]. Finally, do non maximum suppression for para[i, j].

4) If the value para[i, j] corresponding to the final vote (k, b) is less than a given threshold T, determine that there is no edge points. Otherwise, draw a straight line at the edge of the image space.

Figure 3 shows the results of ISEFHough line extraction process. In this experiment, ISEF is decomposed into forward and reverse recursive filtering in row and column respectively, which is used for preprocessing and Figure 3(b) shows the filter result of Figure 3(a). Compute the Gradient Magnitude and Gradient Angle for each pixel, and then do Non-maximum suppression processing for edge extraction. Figure 3(c) shows the edge extraction result. And Figure 3(d) is the final result with road edge line by ISEFHough extraction.

2.4. Vector Change Determination

Whether the road vector has changed or not can be determined with the help of extracted edge information in Section 2.3. The changes in vector unit and the entire road are discussed in this paper. For a vector unit, it is considered that the unit is not changed if the corresponding segment is with bilateral information in the horizontal direction (or nearly horizontal), in addition calculating percentage of the entire length nRoadRatio that its length occupies. For an entire road vector, if the accumulation (SumRoadRatio) of the unchanged vector’s ration

(nRoadRatio) is larger than a certain threshold (set as 0.6 in the experiment), it is considered to have not changed; otherwise, considered to have changed.

Single vector unit (S) change detection process is described as follows,

//ExtractLine(Segment) Function of extracting segment’s edge information, and //determining whether is bilateral edge.

//nChange(p) Judgement of vector’s state of change, FLASE represents unchanged, //TURE shows changed

Single road vector R change detection process is described as follows,

//s_i denote subsets of R

//n denotes the number of subset of R

//nRoadRatio(s) denote percentages of the entire length that subsets’ length occupies

//SumRoadRatio represents the sum of the ratio of unchanged road vectors

//threshold represents the threshold value of length ratio (set to 0.6 in this experiment)

2.5. Template Generation

As for unchanged vector unit, the b calculated as the steps described in Section 2.3.2 is as half-width for road template, and direction of vector as template direction. Define one of vector’s end points as base point, and set the average of the gray values along the perpendicular direction of vector as the corresponding template gray value. Figure 4 shows the template generation method.

3. Experimental Analysis

In this study, 0.5 m panchromatic WorldView images of a domestic area are used to detect change state of the old road vector. WorldView data include 1.85 m resolution multi-spectral image data and 0.5 m panchromatic

image data, which are characterized with the advantages of spectrum and high resolution. And this experiment only takes use of high resolution by using panchromatic image as experimental data. The analysis of the problems existed in experiment and the corresponding solutions were described in this article.

3.1. Images of Different Road Types

In high resolution images, urban main roads and suburban roads are considered as elongated homogeneous regions with almost constant width, but the gray information of blocks’ road images exhibit considerable variation because of occlusions of trees and buildings, which destroys road’s bilateral information.

In this study, the pyramid images are applied to detect change of different road types. It is found that: in the case of high resolution, segment images in urban include less buildings information, making it easier to detect the bilateral edges; When resolution is lowered appropriately, the extracted roads is under better continuity, but fail to extract local road edges when resolution is reduced too much. Comprehensively, choosing the appropriate resolution can effectively reduce detection error rates. In this experiment, the appropriate resolution reduced 3 times compared to the original image is chosen.

3.2. Occlusions of Road

Whether in the urban or rural, the roads may be subject to different degrees of occlusion. Shelter materials are mainly surrounding buildings and block of trees along both sides in the suburbs.

In the case of occlusion, general edge detection operators (Gradient, Canny operator, et al) mainly extract the edges of shelter materials but not straight road edges. The advantage of Hough transform is able to overcome the difficulties caused by partial occlusion and extract the correct linear road edges, as shown in Figure 5.

3.3. Display and Analysis of Experimental Result

Figure 6 shows the results of experiment, where red lines stand for unchanged road vectors and green lines for changed ones.

The detected result of the whole images shows in Table 1,

The definitions of completeness and correctness are presented in the following.

Experimental result shows that the correctness is 79.56%, and the completeness reaches 97.72%. Study of image information indicates that the reasons for the cause of the error appears in the followed three aspects: 1) Occlusions of roads; 2) Original vectors’ offsets to the correct position; 3) Contrast between road images and background is not obvious. It is can be inferred that the proposed approach to road change detection is practical.

4. Conclusions and Prospects

The ISEFHough road change detection method provides a simple and reliable way for updating vector data

based on high resolution remote sensing images. In this paper, the size of experimental data is 1.7 GB, with 2212 vectors which divide images into 4761 segments. It only takes 46 s to complete the whole process, including getting subset, coordinate transformation, filtering, Hough edges extraction and road change detection. Besides, the whole process is automatically done without manually setting parameters.

There are also several shortcomings in the ISEFHough road change detection method. We can know from the result of experiment, even Hough can avoid the situation of partial occlusion, but still extract false road edges in the case of the complete occlusion. Therefore, it is desirable to add some auxiliary information (such as DEM, DOM, etc.) in the post-processing, or to combine other methods (such as dividing the interested area, generating the shape factor of the interested area, etc.) to extract better road edges with less errors.

Acknowledgements

This work was supported by the National Basic Research Program of China (973 Program) with No. 2012CB 719900. We also thank Lu Luping for providing old vector files.

References