Alternative Approach

Due to the many limitations of our current approach, we have experimented with many other methods. These methods, properly developed may preset more robust analysis of our images. Below we discuss some of our work with edge detection, histogram of oriented gradients, and SIFT/SURF. We either encountered too many limitations or did not sufficiently develop the approach at this point that they are not included in our main driver but have merit for further exploration.

Edge Detection

Edge detection is a widely used image processing method. In this method, a filter is applied on the image and a matrix of gradient is calculated by the filter. The location where the gradient is larger than a certain value can be considered to be an edge. Our group did experiment of this method to process the satellite image and the road map. The results are shown in figures below.

The experiment can be easily done by Matlab with the edge() function. The left image is the edge detection result for a satellite image. The result looks messy and noisy. To make use of this, we may use filters to de-noise and apply certain transform method, like Hough transform, to get the pattern of the road.

Histogram of Oriented Gradients (HOG)

This method, used to find roads on the satellite image, is also explored in this project. In this method, the magnitude and the orientation of gradient is calculated of each location. Then, a ‘histogram’ of gradient orientations for a small region is generated. According to the 'histogram', we can estimate that the road has parallel orientation and find it. This is quite obvious when the gradient are depicted on the satellite image, which is shown below.

It is easy to tell where the road is by the parallelity of the gradients with human eyes. However, we don't find a effective way to do this in a computer software. This problem can probably solved by machine learning in future development

SIFT/SURT Correlation

Scale-Invariant Feature Transform method is an algorithm in computer vision to detect and describe local features in digital images. For this method, a specific filter, called Difference of Gaussian (DoG) is applied on the images. The local maximum and minimum is selected as key points. The descriptor of these key points are calculated by certain method. Since the descriptors won't change when the scale, orientation or shade, so the objects in different images can be matched with this method. SURF algorithm is a fast calculation method for SIFT. The following images shows the top 100 strongest key points in the satellite image and road map.

The complete key points set contain over 18000 key points, and the detection take a long time. Even the surf function takes about 20 seconds. The matching process takes even longer. To make this method effective, we should build a more efficient algorithm to shorten the time needed for calculation.