The classification problem of spatial data is one of the most difficult challenges in the field of the analysis and processing of spatial information. A new approach to a solution of the classification problem of spatial data is presented in article. The offered classification technology of objects will be based on algebraic topology, namely on methods of persistent homology. A barcode is a qualifier of a spatial object. It is determined by computation of topological features of a classified object. The distinctive feature of the offered algorithm is its invariance to affine and topological transformations. The research on results of classification algorithm operation on a set of spatial objects of different classes is carried out.
Automatic digitization of maps is one of global problems in geographic information systems [
The method intended for work with topographic maps of average scale is presented in [
The problem of classification of spatial data is also relevant for control of information on
exhaustion of reservoirs or, on the contrary, – about their degradation [
The analysis of the image is applied in [
Processing of satellite images or images with high resolution is made in [
An approach using the example of digitizing distribution maps taken from plant-taxonomic atlases
is described in [
The purpose of work is creation of an algorithm for classification of cartographical information
which will make high-quality object classification of various spatial classes and also is invariant [
The offered algorithm of classification of objects is based on algebraic topology, namely by methods of persistent homology. Application of topological characteristics and their analysis is new area of theoretical researches for tasks of the analysis and processing of spatial information. Information from aircraft is processed and analyzed. The allocated objects are distributed on spatial classes in accordance with the classification of spatial information.
A barcode is taken as the qualifier of a class of a spatial object. It is formed by calculation of topological features of the classified object. Set of values of color intensity of all object points is created. Sorting of this set of values according to increase is made. Search of vertices of some intensity is run step by step. It is noted in the list of vertices when finding such point. If this vertice appeared in the neighborhood of Moore of already noted point, then they are connected a line. The triangle is formed at emergence of three such vertices. The number of components (vertices, lines and triangles) at such approach can change on each step of an algorithm. Emergence of vertice adds a component. Emergence of the line connecting different components leads to disappearance of component (two components unite in one). Pass in reversed sequence (on decrease) is the following stage of an algorithm. At the same time the number of holes and their existence time is counted. The hole is formed at emergence of a triangle. The filtration list for holes turns out depending on emergence of new components, their association and other operations. Search of the maximum number of holes and lines is made by the following step. Barcode of the image of an object is calculated on the basis of these numbers (fig. 1).
(a) (b) Figure 1. Barcodes: (a) – the car and (b) – the P-shaped building. The quantity of holes and intensity of points on the color model RGB are displayed on axis X and on axis Y.
A belonging of object to a spatial class is defined by comparing of barcodes of two objects.
Previously training on images of objects of differrent classes is made (fig. 2, a). Comparing represents
check of inclusion of Bettie numbers (the maximum numbers of holes and lines of the image of an
object) in the range which characterizes objects of a spatial class (fig.3). The algorithm is
complemented with the random forest method [
The random forest model is applied on the basis of values of Bettie numbers which are taken as
features. Random forest is the algorithm consisting of a set of decisive trees. It has been offered by
Leo Breiman and Adele Cutler [
Basic algorithms have to be unique. Each tree is formed on the training selection for this purpose.
There is an element of randomness at the choice of splittings.
The more trees, the quality is better. But time of control and work of Random forest increase in proportion. 2. Viewing of set of random features. It is made for realization of splitting of each branch of a tree. If the number of features for splitting increases, then time of creation of the forest increases, and trees become "more monotonous". 3. Choice of the best feature and of branch of a tree. Creation of trees is made until disappearance of elements from selection.
Creation of Random forest in direct ratio to selection depth. The selection is deeper, the algorithm is longer executed. The quality on training sharply increases at increase in selection depth. But it usually increases on control selection.
It is recommended to use the maximum depth of trees at realization of this algorithm. Change of the parameters connected with restriction of number of objects doesn't result in significant effect when using superficial trees. Each feature has different degree of importance therefore a part of features can not bear advantages.
The research of the offered algorithm is carried out. Testing of spatial information on the basis of images from aircraft from some height is executed. Classes of spatial objects such as vehicles and buildings are considered. The detailing is made on each class. Vehicles such ascars (are presented on fig.4,a-f), light commercial vehicles and minibuses(fig.4,g-j), buses (fig.4,k-l) are considered. Rectangular, G-shaped, P-shaped, private types of buildings are presented (fig.5).The quantity of the training and test selections in the sum is equal 100 images of objects.
(a) (d) (g) (j) (k) (l) Figure 4. Spatial class of objects "Vehicles". (a-f) – cars; (g-j) – light commercial vehicles and minibuses; (k-l) – buses. (c) (d) Figure 5. Spatial class of objects of "Building". (a) – rectangular; (b) – G-shaped; (c) – P-shaped; (d) – private houses.
Algorithm is invariant to affine transformations. Therefore tests with the different angles of shooting are carried out for the offered types of an object (90˚,180˚,270˚, 360˚– fig.6). Research results of invariancy of an algorithm to affine transformations are presented in table 2.
Object class Vehicles
Also an algorithm is invariant to scale. Therefore tests in images of the same area of different scales are carried out (table 3). The algorithm hasn't made mistake for two subclasses of vehicles (from three) and for two subclasses of buildings (from four).
Existing approaches of classification of spatial data are considered in article. New approach of realization of an classification algorithm on the basis of topological characteristics of the image is offered. At the heart of an algorithm methods of a persistent homology and the Random Forest method are put. Results of researches have shown expediency of application of the developed classification algorithm of spatial information as it invariant to affine transformations and changes of scale.
A deformation (distortion) of source data is one of problems of map object classification. A stretching of images of spatial objects is one of types of deformation.The solution of this problem is important within the solution of a problem of classification of spatial information and automatic digitization of maps.Algorithm modernization in the sphere of processing of spatial data with deformations of various types is the following step in improvement of work of the offered algorithm.
The reported study was funded by RFBR and Vladimir region according to the research project № 1747-330387. The reported study was funded by Vladimir region according to the research project № 326 of 29.09.2017.