Extraction of High Resolution Remote Sensing Image Features Using Triangulation Method

Extraction of High Resolution Remote Sensing Image Features Using Triangulation Method

Parul Malhotra1

M.Tech Research Scholar, ECE Deptt.

Ambala College of Engg. & Applied Research (Kurukshetra University), Ambala

Saurabh Sharma2

M.Tech Research Scholar, CSE Deptt. MMEC (Maharishi Markandeshwar University Mullana), Ambala

Abstract

The project entitled Extraction of High Resolution Remote Sensing Image Features Using Triangulation Method plays an important role in extraction and updating of linear objects in cartographic processes. For extraction vectorization is performed using Constrained Delaunay Triangulation and triangles which are obtained from triangulation method are grouped into polygons that make up the vector image. The skeleton of these polygons represents the extracted linear structures which are obtained by using skeletonization. All works for this paper includes the following steps: Reading of image, Obtaining Correlation image, Obtaining vector image using Constrained Delaunay Triangulation (CDT) method, Canny edge detection, skeletonization to obtain morphological skeleton. The performance of the proposed algorithm is compared with the existing algorithm. The proposed algorithm is fast, automatic and has better results when tested.

Keywords- Vectorization, Skeletonization, Remote Sensing Image, CDT.

1. Introduction

   Road extraction is a fundamental step for the efficient uses of high resolution remote sensing images, such as updating GIS databases, registering image as references, mapping and so on. Besides, road extraction can also be helpful for the detection and identification of buildings, bridges, rivers and other ground features. It is rather hard to extract the different objects one by one and just do cost much time, and therefore, the extracting work can barely be set up in application. However, we all know that urban road is the main clue to analyze and interpret the city. So we can extract road information from remote sensing image first, and then analyze each district

   segmented by roads. By doing this, the analyzing work will be easier than before. There have been many researches on the approaches of road extraction. These can be divided into the semi-automatic type and totally automatic type. Semi-automatic extraction for road feature takes advantage of man-machine interactive form to recognize the objects.

   Traditional approaches on road extraction tend to extract the linear road. The accuracy is relatively low in extracting the urban road. There also exist omissions in some images because of the tiny, closed and preserved features. Sometimes the road in the image is close to the background, which could go against extraction. And a suitable algorithm for urban highways in modern days hasnt been applied in traditional approaches. Aiming to the shortfalls above, this paper proposes a new approach. That is road extraction based on Triangulation method. Not only be fit for the road extraction of general shapes, but also having certain superiority in the detection work of urban highways. The proposed method reduces various kinds of distortions and improves the Precision and Recall, compared with previous method.

   The remainder of this paper is organized as follows. Section II briefly describes the general approach of the method. Section III describes the Proposed Algorithm. Section IV describes the experimental results which includes correlation, canny edge detection process, Triangulation and skeletonization which is the final step of the algorithm.

2. General Approach

   Figure1 shows the flow diagram of our approach. First of all, reading of original image is done. After reading of image, preprocessing of image is done which includes correlation. Correlation refers to any of a broad class of statistical relationships involving dependence and dependence refers to any statistical

   relationship between two random variables or two sets of data.

   Read Original Image

   Correlation Image

   Canny Edge Detection

   Grouping of Polygons Obtained from Constrained Delaunay Triangulation

   Extraction of Skeleton of Obtained Polygon using Skeletonization

   Figure 1. The Flow Diagram of Our Method

   Canny Edge detection is performed to find the edges of the image. After detection of edges, vectorization is performed using Constrained Delaunay Triangulation and triangles which are obtained from triangulation method are grouped into polygons that make up the vector image. The final step in our algorithm is to extract the skeleton of the obtained polygons.

3. Proposed Algorithm

1. Original input image.

   Read input image I. If image I is 24 bits, convert

   to 8 bit grayscale image for edge detection.

2. Pre-processing.

   Compute the correlation distance image. Compute the high correlation image.

   To each pixel having a coefficient higher than a threshold t is assigned the gray level of the reference pixel. In the case where the current pixel has a low correlation coefficient, its spectral value is examined. If it has the same gray level

   as the reference pixel, the point is deleted.

3. Canny edge detection.

   Obtain all canny edge points as a binary image maskedge image. Include all boundary pixels of edge image as edge pixels. Delaunay triangulation of the contour set to obtain a list of triangles tessellating the regions between contours.

   Obtain list of triples of indices of points

   constituting triangles.

4. Extraction of edges that belong to two triangles.

5. Extraction of vectors from two triangles.

   Both triangles have value either 0 or 1. If 1 comes then vectors are saved and if 0 comes then vectors are discarded in case of both triangles.

6. Thinning to find skeleton.

Thinning operation is applied on vectors to find skeleton.

1. Experimental Results

   1. Correlation

      Correlation is a broad class of statistical relationships between two or more random variables or observed data values. Correlation coefficients can range from -1 to +1. The value of -1 represents a perfect negative correlation while a value of +1 represents a perfect positive correlation. A value of 0 represents a lack of correlation.

      The correlation coefficient is defined as:

      i i i i

      Corr x, y y y * x x / y y 2 * x x 2

      where x: current pixel

      y: reference pixel

      Figure 2. The Original Image

      Figure2 shows the original image on which whole process is to be taken.

      Figure 3. Correlation Distance Image

      Figure3 shows the correlation distance image. To each pixel having a coefficient higher than a threshold t is assigned the gray level of the reference pixel.

      Figure4 shows the high correlation image. Computation of high correlation image is as follows:

      Input: Original image I, reference pixel y for every pixel x

      corrImg(x) = corr(x,y) end

      I = grayscale(I) for every pixel x

      if corr Img(x) > t highCorr(x) = I(x)

      elseif (I(x) == I(y))

      highCorr(x) = 0

      The result of applying an edge detector to an image may lead to a set of connected curves that indicate the boundaries of objects, the boundaries of surface markings as well as curves that correspond to discontinuities in surface orientation. Thus, applying an edge detection algorithm to an image may significantly reduce the amount of data to be processed and may therefore filter out information that may be regarded as less relevant, while preservin the important structural properties of an image. In this paper canny edge detection is applied at high correlation image. Figure5 shows the canny edge detection.

      Figure 5. Canny Edge Detection

      end end

      Figure 4. High Correlation

      Canny edge detection consists of following steps: Blurring of the image to remove noise.

      The edges should be marked where the gradients of the image has large magnitudes.

      Only local maxima should be marked as edges. Potential edges are determined by thresholding. Final edges are determined by suppressing all edges that are not connected to a very certain (strong) edge.

      4.3. Triangulation

      In the case where the current pixel has a low correlation coefficient, its spectral value is examined. If it has the same gray level as the reference pixel, the point is deleted. Thus the pixels that are highly correlated with the reference are emphasized.

      4.2. Canny Edge Detection

      Edge detection is important in image processing programs because it allows object separation and shape detection. Edge detection aims at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities.

      The construction of vector image starts with Canny edge detection followed by a constrained Delaunay triangulation (CDT) where the lines resulting from the preprocessing stage are used as constraints for Delaunay triangulation. A triangulation of a set S of points on the plane presents a partition of an area, surrounded by a convex hull. Triangles are composed by vertices, given as an input. But if the triangles fulfill additional condition of an empty circumcircle, they present a Delaunay triangulation Let G be a straight-line planar graph.

      Figure 6. (a): A Planar Straight-Line Graph G(S,Ec) (b): Conventional Delaunay Triangulation of the Point Set S (c): Ilustration of the Modified Circle Criterion for Constrained Delaunay Triangulation

      A triangulation T is a constrained Delaunay triangulation (CDT) of G if each edge of G is an edge of T and for each remaining edge e of T there exists a circle C with the following properties: 1) The endpoints of edge e are on the boundary of C, and 2) if any vertex v of G is in the interior of C then it cannot be seen from at least one of the endpoints of e (i.e., if you draw the line segments from v to each endpoint of e then at least one of the line segments crosses an edge of G).

      Figure7 shows the triangulation result. The presence of constraints in the CDT is ensured through local modifications where Delaunay edges are removed or flipped. CDTs solve the problem of enforcing boundary conformityensuring that triangulation edges cover the boundaries (both interior and exterior) of the domain being modeled.

      Figure 7. Triangulation Result

      4.4. Skeletonization

      Skeletonization plays an important role in digital image processing especially for the analysis and recognition of binary images. Skeletonization is the process for reducing foreground regions in a binary image to a skeletal remnant that largely preserves the extent and connectivity of the original region while throwing away most of the original foreground pixels. It is a global space domain technique for shape

      representation. The skeleton typically emphasizes the geometric properties and topological shape, such as connectivity, topology, length, direction, and width. There are two well-known paradigms for skeletonization methods: The first is iterative thinning of the original image until no pixel can be removed without altering the topological and morphological properties of the shape. The second definition used for a skeleton is that of the ridge lines formed by the centers of all maximal disks included in the original shape, connected to preserve connectivity. This leads directly to the use of distance transforms or similar measures which can be computed in only two passes on the image.

      The final step in our algorithm is to extract the skeleton of the obtained polygons. Figure8 shows the skeletonization result. The skeleton represents the extracted lines.

      Figure 8. Skeletonization Result

2. Accuracy

   The proposed algorithm is fast and automatic with improved results when compared with previous results. To evaluate the obtained results we used the Precision and recall measures. Precision is defined as the number of relevant identified elements divided by the total number of retrieved elements, and Recall is defined as the number of relevant elements retrieved divided by the total number of existing relevant elements. The closer value to 1 indicates the better results.

   In order to evaluate the performances of our algorithm, Recall and Precision have been calculated using the following formulas:

   Precision = No. of relevant identified elements Total No. of retrieved elements

   Recall = No. of relevant elements retrieved Total No. of existing relevant elements

   We tested the algorithm on several high resolution satellite images containing road segment. The high

   resolution satellite image taken in this paper had a precision of 0.87 and a recall value of 0.89.

3. Conclusion

   This paper has realized features extraction from the high resolution remote sensing image, by the triangulation method. Our approach provides good recall and precision values when compared with previous methods. The algorithm is costly in terms of complexity and memory as it depends on the size of the CDT input set. The proposed work can also be extended for military purposes by carrying work on the region of interest.

4. References

1. P.N ANIL, Dr. S. NATARAJAN, Automatic Road Extraction from High Resolution Imagery Based On Statistical Region Merging and Skeletonization, International Journal of Engineering and Technology, 2010, pp. 165- 171.

2. HU Yang, ZU Ke-ju, Road Extraction from Remote Sensing Imagery Based on Road Tracking and Ribbon Snake, Pacific-Asia Conference on Knowledge Engineering and Software Engineering, China, 2009, pp. 201- 204.

3. Quoc Bao Truong, Byung Ryong Lee, Nam Geon Heo,Young Jim Yum, Jong Gook Kim, Lane Boundaries Detection Algorithm Using Vector Lane Concept, Intl. Conf. on Control, Automation, Robotics and Vision Hanoi, Vietnam, 2008, pp. 2319- 2325.

4. Hongbin Ma, Yahong Zhao, Qun He, Road Extraction from High Resolution Remote Sensing Image Based on Mathematics Morphology And Seed Growth, Journal of Surveying and Mapping Engineering Department of Northeastern University, 2007, pp. 523- 528.

5. Bai, X., Latecki, L.J. and Liu, W.Y., Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution, 2007, pp. 449-462.

6. E. Christophe and J. Inglada, Robust Road Extraction for High Resolution Satellite Images, 2007, pp. 437- 440.

7. Zu Kim, Real-time lane tracking of curved local road, 2006, pp. 11491155.

8. Gavlasova, A., Prochazka, A. and Mudorva, M.,

   Wavelet Based Image Segmentation, 2006, pp. 1-7.

9. Muneeswaran, K., Ganesan, L., Arumugam, S., Ruba, K. and Soundar, Texture Image Segmentation using Combined Features from Spatial and Spectral Distribution, 2006, pp. 755-764.

10. Lin Wang, Qiming Qin, Shihong Du, dezhi Chen, Jianwei Tao, Road Extraction from Remote Sensing Image Based on Multiresolution Analysis, International Journal of Remote Sensing and GIS, 2005, pp. 86-89.

11. Haitao ZHANG, Zhou XIAO, Qing ZHOU, Research On Road Extraction Semi-Automatically From High Resolution Remote Sensing Images, International

    Journal of Beijing Institute of Surveying and Mapping, 2004, pp. 535- 538.

12. Aaron K. Shackelford, Urban Road Network Extraction from High Resolution Multispectral Data, 2nd GRSS/ISPRS Joint Workshop on Data Fusion and Remote Sensing Over Urban Areas, 2004, pp. 142-146.

13. Deng Nai-yang, Tian Ying-jie, The new method in data mining, 2004, pp.64-196.

14. Zhu C.Q., Wang Y.G., Ma Q.H., Shi W.Z., Road Extraction from High-resolution Remotely Sensed Image Based on Morphological Segmentation, 2004, pp.347-P351.

15. Nock, R. and Nielsen, F., Statistical Region Merging, 2004, pp. 1452-1458.

16. Tie Liu, Nanning Zheng, Hong Cheng, Zhengbei Xing.

    A Novel Approach of Road Recognition Based on Deformable Template and Genetic Algorithm, 2003, pp. 12511256,.

17. Galun, M., Sharon, E., Basri, R. and Brandt, A.,

    Texture Segmentation by Multiscale Aggregation of Filter Responses and Shape Elements, 2003, pp. 716- 725.

18. Mostafa, M.G., Gharib, T.F., Tolba, M.F. and Megeed, M.A., Medical Image Segmentation using a Wavelet Based Multiresolution EM algorithm, 2001, pp. 112- 117.

19. Malik, J., Belongie, S., Leung, T., and Shi, J., Contour and Texture Analysis for Image Segmentation, 2001, pp. 7-27.

20. Mirmehdi, M. and Petrou, M., Segmentation of Color Textures, 2000, pp. 142-159.

Parul Malhotra was born at H.No. 228/3 Jail Road,

Mandi(Himachal Pradesh) in India, on Sep. 13, 1988. She graduated from Indo Global College of Engg., Abhipur, Distt. Mohali (Punjab), India, and completed her Masters of Technology (batch 2009- 11), ECE Deptt, from ACE&AR, Ambala (Haryana), INDIA. She

has successfully completed her Six Weeks Industrial training from (18 June 2007 to 30 July 2007) at BSNL, Bhiuli, Mandi (Himachal Pradesh), India. Also during her Six Month Industrial Project she worked on Fake Currency Detector from (1 July2008 to 31Dec 2008) at Central Scientific Instruments Organization (CSIO), Sector-30C, Chandigarh- 160030, India.

Saurabh Sharma was born at H.No. 70/11, Chougan, SunderNagar, Distt. Mandi (Himachal Pradesh) in India, on May 21, 1987. He

graduated from Dr. JJMCOE Jaysingpur, Distt. Kolhapur (Maharashtra), India, and completed his Masters of Technology(batch 2009-11), CSE Department, from Maharishi Markandeshwar Engg.

College, MMU, Mullana, Ambala(Haryana), INDIA. He has successfully completed his B.E. Final Year Project- Multi-layer Database Access Control Architecture(MDACA).