Identification of spatial ob jects on digital maps

Abstract

The problem of identification of spatial objects on maps is considered in article. It is possible to solve it using topological information analysis and methods of persistent homology. Advantage of this approach is invariance to affine transformations and changes of scale. Results of the program operation developed on the basis of the offered algorithms are presented. Directions for improving and extension of presented algorithms are offered.

Keywords

• barcode
• different scales of maps
• identification of spatial objects
• topological consistency of spatial objects
• topological relationships
• topology

Introduction

Automation of information processes is complex and knowledge-intensive task. Its decision allows to facilitate operation of federal, regional and municipal management systems and to simplify transition to an electronic document management. Operation with geographic data assumes processing and the analysis of large volume of information as digital maps contain a huge number of objects. Data on these objects, their properties and relationships among themselves are also subject to the analysis. Identification of objects is an important processing stage of geographic data [ 1 ], [ 2 ]. It can include such stages as preliminary processing of geographic data and identification of spatial objects. Identification of cartographical objects can be made on the basis of geometrical, spectral, textural or topological features [ 3 ], [ 4 ], [ 5 ], [ 6 ].

Important detail except identification of objects is relationships of objects among themselves. They are named "topological relationships" [ 7 ], [ 8 ]. It allows to establish the topological relationships between objects, at first sight, which aren’t connected among themselves, but belonging to one structural group, and also type of objects [ 9 ]. The decision of this task will allow to facilitate classification of spatial objects [ 10 ] as external (on layers, containing different objects, for example, buildings, roads, the rivers, vehicles), and internal (on kinds of objects of one type, for example, industrial buildings, inhabited apartment houses, inhabited private houses). Establishing of the topological relationships for map objects is very complex task. After its execution it is possible to execute an acceleration of process of the analysis of cartographical information. It not only will increase the speed of object search [ 11 ], but also will improve its quality. Special attention should be paid to a question of identification of objects when scaling maps. Search of the same object on maps of different scales [ 12 ] also is the difficult task. The work presented in article will be devoted to its decision.

Mathematical description of the initial cartographical information Identification of spatial objects is made on digital images of map. For an example we will take a map of the conditional settlement K. It will consist n of squares with dimensionality m m. I.e., the map to will have the following appearance (Fig. 1). Let each square of map K will correspond to image made some flight vehicle (for example, drones). Each such image will be the source material for our algorithm. 3

The search algorithm of vehicles in high-precision pictures In [ 11 ] the analysis of the existing algorithms of allocation of objects in a raster image is made. The search algorithm of vehicles on the basis of the following actions is offered. The algorithm uses preliminary processing of the image, in particular, binarization and filtering. Sifting of contours is executed. Then they are drawn on the result image. Sifting happens on the basis of formulas 1, 2. where Pcontour is perimeter of the current contour; P is perimeter of minimum described rectangle around the current contour Pcontour; is threshold value for determination of compliance of the current contour to the form of rectangle; Pmin is minimum threshold value for the current perimeter; Pmin is maximum threshold value for the current perimeter.

The image with the spatial objects of the given type allocated on it is result of operation of an algorithm. In [ 11 ] given object type is vehicles.

a) Lack of an algorithm is not the highest accuracy of identification of objects [ 11 ]. Affine transformations also influence on the accuracy of an algorithm. For example, having changed a shooting angle (we will assume by default that shooting was carried perpendicularly to the plane), quality of identification noticeably will decrease. 4

Algorithm of identification of spatial objects on the basis of methods of persistent homology

Demands except high accuracy of identification are made to algorithms. Such demands as saving of high accuracy in case of different conversions, for example, affine transformations or changes of scale.

Approach on the basis of the analysis of topological information and methods of persistent homology allows to execute identification of objects, invariant to affine transformations [ 13 ], [ 14 ]. In [ 15 ] algorithms on the basis of this approach are presented and testing of their operation in real images of Murom (Fig. 3) is made.

a) b)

The task of identification of buildings as in a image of a map of large scale (Fig. 4a), and in a image of a map of smaller scale (Fig. 4b) is set.

The algorithm uses template of an object of required type for which characteristics of the image on the basis of Bettie’s numbers are calculated. For the presented situation a template is one of buildings of university (Fig. 5).

Computation of numbers of Bettie (Fig. 6, axis Oy) depending on intensity of color (Fig. 6, axis Ox) is made for this template. Quantity of components of connectivity (H0) and quantity of holes (H1) are presented in Fig. 6a and Fig. 6b respectively.

a) b)

It is possible to define compliance of the identified object to the given type on the basis of comparing of barcodes of objects with barcodes of a template. Identification of objects (of buildings of university) executed successfully for the given image of smaller scale and turned on 180 (Fig. 7).

Conclusion and Future work

As a result, operation shows that the considered approach correctly identifies spatial objects of the given type and saves identification accuracy in case of affine transformations and changes of scale. Further enhancement of an algorithm is offered as progress of approach. It is possible to carry width and depth of search to such improvings, i.e., extension of classification on types of cartographical objects. For example, it is possible to add new object types or to execute more deep classification of some object types. It is possible to consider for buildings, such kinds as industrial, inhabited buildings etc.

It is also important to pay attention to the speed of operation of an algorithm. Now it is low as search is executed on all image. Perhaps, object search necessary execute only in those areas where contours remain after preliminary processing of a image. It will allow to increase the speed of operation of an algorithm, especially for that terrain where the small quantity of objects are on big square. One more problem which requires a research is the question of identification of objects on maps of different scales. At the moment the behavior of an algorithm in case of identification of buildings is checked, but it is necessary to study how he behaves in case of, first, identification of other object types, secondly, in case of more deep classification of buildings.

References

1. Andrianov , D. E. , Eremeev , S. V. , Kuptsov , K. V. Models of Complex Spatially Distributed Objects and their Features Calculation . International Conference on Mechanical Engineering, Automation and Control Systems (MEACS) . 2015 . P. 1- 5 .

2. Andrianov , D. E. , Eremeev , S. V. , Kuptsov , K. V. The review of spatial objects recognition models and algorithms . Procedia Engineering . 2015 . Vol. 129 . P. 374 - 379 .

3. Du , S. , Zhang , F. , Zhang , X. Semantic classification of urban buildings combining VHR image and GIS data: An improved random forest approach . ISPRS Journal of Photogrammetry and Remote Sensing . 2015 . vol. 105 . P. 107 - 119 .

4. Steiniger , S. , Lange , T. , Burghardt , D. , Weibel , R. An approach for the classification of urban building structures based on discriminant analysis techniques . Transactions in GIS . 2008 . vol. 12 ( 1 ), P. 31 - 59 .

5. Maruyama , Y. , Tashiro , A. , Yamazaki , F. Use of digital surface model constructed from digital aerial images to detect collapsed buildings during earthquake . Procedia Engineering . 2011 . vol. 14 . P. 552 - 558 .

6. Jin , X. , Davis , C. Automated building extraction from high-resolution satellite imagery in urban areas using structural, contextual, and spectral information . EURASIP Journal on Applied Signal Processing . 2005 . vol. 14 . P. 2196 - 2206 .

7. Edelsbrunner , H. Computational Topology : An Introduction. American Mathematical Society . 2009 .

8. Carlsson , G. Topology and data . American Mathematical Society . 2009 . vol. 46 ( 2 ). P. 255 - 308 .

9. Eremeev , S. V. , Andrianov , D. E. , Kuptsov , K. V. Method of identification of not crossed spatial objects on the basis of structural elements . Telecommunications . 2015 . No. 11. P. 39 - 43 .

10. Bosch , A. , Zisserman , A. , Munoz , X. Image classifcation using random forests and ferns . Proc. of the IEEE 11th International Conference on Computer Vision (ICCV). 2007 . P. 1- 8 .

11. Kuptsov , K. V. The search algorithm of vehicles in high-precision pictures. Algorithms, methods and data handling systems . 2015 . No. 2. P. 50 - 58 .

12. Andrianov , D. E. , Eremeev , S. V. , Kuptsov , K. V. Checking the toposlogical consistency of maps of different scales . Supplementary Proceedings of the Fifth International Conference on Analysis of Images, Social Networks and Texts (AIST 2016 ). Vol- 1710 . P. 124 - 133 .

13. Deng , M., Cheng, T., Chen , X. , Li , Z. Multi-level topological relations between spatial regions based upon topological invariants . GeoInformatica . 2007 . vol. 11 . N. 2. P. 239 - 267 .

14. Ghrist , R. Barcodes: the persistent topology of data . American Mathematical Society . 2008 . vol. 45 ( 1 ). P. 61 - 75 .

15. Andrianov , D. E. , Eremeev , S. V. , Kuptsov , K. V. , Kovalev , Yu. A. Algorithm of identification of spatial objects of a raster map on the basis of topological data analysis . Telecommunications . 2017 . No. 7 . (in printing).