=Paper=
{{Paper
|id=Vol-1940/paper01
|storemode=property
|title=Identication of Spatial Objects on Digital Maps
|pdfUrl=https://ceur-ws.org/Vol-1940/paper01.pdf
|volume=Vol-1940
|authors=Dmitry Andrianov,Sergey Eremeev,Kirill Kuptsov
}}
==Identication of Spatial Objects on Digital Maps==
https://ceur-ws.org/Vol-1940/paper01.pdf
Identification of spatial objects on digital maps
Dmitry Andrianov, Sergey Eremeev, and Kirill Kuptsov
Murom Institute of Vladimir State University, Murom, Russia
andrianovde@inbox.ru, sv-eremeev@yandex.ru, kirill-kuptsov@rambler.ru
Abstract. The problem of identification of spatial objects on maps is
considered in article. It is possible to solve it using topological infor-
mation 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 pre-
sented algorithms are offered.
Keywords: barcode, different scales of maps, identification of spatial ob-
jects, topological consistency of spatial objects, topological relationships,
topology.
1 Introduction
Automation of information processes is complex and knowledge-intensive task.
Its decision allows to facilitate operation of federal, regional and municipal man-
agement systems and to simplify transition to an electronic document manage-
ment. 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 process-
ing 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 classifi-
cation of spatial objects [10] as external (on layers, containing different objects,
for example, buildings, roads, the rivers, vehicles), and internal (on kinds of ob-
jects 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
2 Dmitry Andrianov, Sergey Eremeev, and Kirill Kuptsov
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.
2 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).
Fig. 1. Settlement map
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
Identification of spatial objects on digital maps 3
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.
Pcontour
≥ , (1)
P
Pmin ≤ Pcontour ≤ Pmax , (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) b)
Fig. 2. Identification of vehicles
4 Dmitry Andrianov, Sergey Eremeev, and Kirill Kuptsov
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 exam-
ple, 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)
Fig. 3. Source (a) and result (b) images
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.
Identification of spatial objects on digital maps 5
a)
b)
Fig. 4. Source images
The algorithm uses template of an object of required type for which charac-
teristics 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).
Fig. 5. The building template
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)
Fig. 6. Barcodes of the building template
6 Dmitry Andrianov, Sergey Eremeev, and Kirill Kuptsov
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).
Fig. 7. Result image
5 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.
Identification of spatial objects on digital maps 7
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 classi-
fication 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 Mathe-
matical 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. Algo-
rithms, methods and data handling systems. 2015. No. 2. P. 50–58.
12. Andrianov, D. E., Eremeev, S. V., Kuptsov, K. V. Checking the toposlogical con-
sistency of maps of different scales. Supplementary Proceedings of the Fifth In-
ternational 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 So-
ciety. 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).