In this paper, we propose methods designed to automate vectorization of point objects at cartographic image digitizing. These methods are based on the analysis of the skeleton-contour image representation and allow to detect point objects, estimate their parameters, and restore a regular grid of points. The experiments show high accuracy of the developed methods, which results in the possibility of using them in order to accelerate the process of digitizing cartographic images.
At present, the problem of digitizing important information from paper carriers is of great urgency [
The simplest way to digitize paper maps is to scan them in bitmaps with subsequent coordinate binding in GIS. In such case, these data can be used as an underlying layer supplementing the information on a particular territory. However, they can not be used for solving any analytical tasks in GIS. For that, raster maps must be vectorized and become a part of the GIS database. In the past 20 years, a couple of methods and software tools were developed to simplify the process of digitizing bitmaps. For instance, we can mention such tools as ArcScan (in ArcGIS software), PowerTRACE (in CorelDRAW), EasyTrace, LineTracer, Spotlight, etc. However, cartographic images often contain various figures (topographic signs), and for their fast digitizing it is often necessary to develop new specialized methods and software tools.
The current paper is devoted to the development of methods for solving one of the particular problems in the described area:
vectorization of point objects. In general, all the objects plotted on the maps can be divided into two main groups. The first one
includes linear objects, defined by their axial line, drawing method, and thickness. At their digitizing, the most important task is
to restore the axial line with high precision. For that, there are used methods based on either raster skeletonization [
Point objects are quite common on paper maps. They are used, for example, for designation of plantations, bushes, elevations,
sand, orchards, etc. (see Figure 1) [
The paper is organized as follows. The second section describes the general technology of cartographic image digitizing that we use and also denotes its stages requiring the development of specialized methods for point objects. Section 3 contains a description of the methods developed to detect such objects, restore their radius, and localize them on a continuous or discrete grid. The results of experimental studies of the methods developed are presented in Section 4. The paper ends with the conclusion and acknowledgments.
In our work, we used a typical technology of cartographic image digitizing that includes the following stages:
Image Processing, Geoinformation Technology and Information Security / S. Rychazhkov, V. Fedoseev, R. Yuzkiv 1. Preprocessing a bitmap. 2. Transformation of the image into the skeleton-contour representation. 3. Classification of objects to be vectorized. 4. Type-adapted object vectorization. 5. Correction of vector results based on analysis of object groups.
At the first stage, the original color scanned image is converted into one or more binary images prepared for subsequent
vectorization. Thus, the mandatory procedures used at this stage are color segmentation and binarization. The need for color
segmentation is due to the fact that most maps contain several thematic layers displayed by predetermined colors (for example,
blue is used for hydrography, red or brown for relief, green for vegetation, etc.) [
The binary image obtained at the first stage can be considered as a set of figures. At the second stage, we estimate contours
n
and skeletons for each of these figures. According to [
The skeleton can be described by a flat graph [
Since different methods of processing the skeleton-contour data are required for different object types (linear, point, area), at
the third stage it is necessary to classify each object (figure) for correct processing performed at the fourth stage. The result of
the fourth stage is the vector data, which can be further corrected in the fifth stage based on a priori known constraints on the
geometry of similar objects. For example, many conventional topographic signs should have a constant size, and some groups of
symbols must also be located at the same distance from each other [
As studies have shown, to classify point objects (i.e. to check whether an object is point-like), it is useful to estimate the object radius. The initial approximation of the circle radius R0 can be calculated based on the skeleton edge lengths l j , j 1..N and radiuses rj,1 and rj,2 of maximal empty inscribed circles for corresponding vertices. Let L be the length of the entire figure skeleton:
Image Processing, Geoinformation Technology and Information Security / S. Rychazhkov, V. Fedoseev, R. Yuzkiv
N L = е l j .
j= 1 R0 = е i= 1 N ri,1 + ri,2 li 2
.
L
Further, two different methods can be used to refine the radius of the circle: the method based on contour length, and the one based on figure area.
a) minimizing the perimeter deviation
b) minimizing the area deviation
Method 1 is based on minimizing the deviation of the figure perimeter from the theoretical circumference based on the value of the radius r : (1) where D is the length of the figure contour.
The problem (1) can be solved numerically (for example, using the golden section search) with the initial approximation r = R0 . Method 1 is illustrated in Fig. 2a, where the figure contour (shown as a triangle) and the theoretical circumference are highlighted in color.
Method 2 is based on minimizing the deviation of the figure area from the theoretical value of circle area, determined by the radius r . Let S be the figure area, S I – the area of intersection of a circle with a figure, SF – the figure area that is outside of the circle, SC – the circle area that is outside of the figure (see Fig. 2b). We used the following accuracy characteristics:
a =
SI SI + SF =
S
I , b = S
SI SI + SC =
SI .
pr 2 g = 1 a 2 + 1 b =
2SI S + pr 2 .
Then the radius R can be calculated by minimizing the deviation of g from unity: The problem (2) can be solved by the same method as the problem (1).
To detect point objects on a map, we need to calculate some features and classify whether the object is from the point class. Our studies have shown that a set of only two features is sufficient and the linear separating function can be applied for
Image Processing, Geoinformation Technology and Information Security / S. Rychazhkov, V. Fedoseev, R. Yuzkiv classification. The first feature characterizes the deviation of the functional (1) (or (2)) from zero, thus, it can have one of two forms:
To reduce the computational complexity, it is preferable to use the feature f11 for the first method of a circle radius refinement and the feature f12 for the second one.
The second feature is defined as the ratio of the skeleton length to the radius estimation:
L f2 = .
R
In Section 1 it was noted that some point symbols (for example, orchards, wooded areas) on maps follow the same distance from each other. Thus, the resulting vector objects must also keep a regular layout. However, this requirement is not guaranteed when objects are processed individually. To restore a regular object grid, the following method is proposed.
Let one of the grid nodes is located in the origin of coordinates. Then a two-dimensional grid can be defined by two vectors ⃗⃗⃗1and ⃗⃗⃗2 (which are often orthogonal to each other) (see Fig. 4). Then the coordinates (x(i) , y(i) ) of a particular grid node can be found as follows: where are the indices of the grid node.
The initial approximation of the grid can be based on three adjacent support objects, one of which is central, and the other two specify the direction of the vectors ⃗⃗⃗1and ⃗⃗⃗2 (see Fig. 4). In practice, these support objects can be selected by the user. When reconstructing a regular grid of points, it is necessary to solve next three problems: refine the vectors ⃗⃗⃗1and ⃗⃗⃗2; detect all point objects lying on the grid correct the center coordinates of the found objects taking into account the refined vectors ⃗⃗⃗1and ⃗⃗⃗2
Here is the proposed algorithm: Step 0. Set the initial approximations of vectors ⃗⃗⃗1and ⃗⃗⃗2; add 3 reference objects to the set S .
Step 1. Find the theoretical coordinates of all grid nodes not yet added to the set S and having at least one neighbor in the set S by the rule of four neighbors.
Step 2. Among all the point objects of the map, find objects that are located at a distance no more than the threshold value d from the theoretical coordinates found in Step 1. If at least one object is found, go to Step 3, otherwise – to Step 5.
Step 3. Refine vectors ⃗⃗⃗1and ⃗⃗⃗2: where are the counts of vectors used to estimate the vectors; ⃗⃗⃗⃗1, ⃗⃗⃗⃗2 are the estimations of vectors ⃗⃗⃗1 and ⃗⃗⃗2 for current grid node by Eq. (3) and known indices k1 , k2 . If one of these indices is zero, then it is obvious that only one of the vectors ⃗⃗⃗1and ⃗⃗⃗2 is recalculated.
For the experiments, we primarily used a scanned image containing many regularly located point objects with some linear ones (see Fig. 5a). For this image, a manual vectorization was performed, as well as automatic vectorization using the proposed methods. The results of manual vectorization were considered as reference ones. Also, during the experiments, a synthesized image was used (see Fig. 5b), for which the exact number of point objects and their locations are known. a) scanned image
b) synthesized image
Since the average point size influence on the parameters of a point classifier and we had only two test images of different origin, we decided not to train a particular classifier (which would have to be trained on a fragment of the same image). Instead, several fixed threshold values ∆11 (or ∆12) and ∆2 for features f11 (or f12 ) and f 2 were considered, and the classification was performed according to the rule
During the experiment on the real image, for the refinement method 1, the largest value of F-measure was achieved at ∆11= 0.35, ∆2= 3.5 and was equal to 0.9943. For the refinement method 2, the largest value was achieved at ∆12= 0.2, ∆2= 4.5 and reached 0.9957. Fig. 6 shows how ∆11 (for the fixed) ∆2= 3.5 and ∆12 (for fixed) ∆2= 4.5 influence on F-measure. As can be seen from the graphs, for a wide range of values, the F-measure has very high values, which confirms the possibility of separation of point objects in this image.
Image Processing, Geoinformation Technology and Information Security / S. Rychazhkov, V. Fedoseev, R. Yuzkiv
In addition, Table 1 specifies some other statistics. As can be seen, the second method showed a somewhat higher accuracy both in detecting the points and in estimating their location.
1,00 0,99 e lu0,98 a v ru0,97 e s a em0,96 F 0,95 0,94 0,00 0,10 0,20 0,30 0,40 0,50 0,60 0,70 0,80 0,90
1,00
Treshold value Δ11 (Δ12) Method 1
Method 2
Testing of the grid reconstruction method was carried out using a fragment of the image from Fig. 5a, containing 147 circles, with d = 10 pixels. As the measure of the method effectiveness, the number of objects matched with the grid nodes and the total deviation of their centers from the grid nodes were used.
During the experiment, at the first iteration (steps 0-4, until the coordinates of the support objects were refined), all circles were found which should lie on the grid, and the total deviation was 11.02 pixels (for 147 objects). At the second iteration (after changing the coordinates of the reference object), the deviation was 6.47 pixels, and the total deviation was reduced to 6.41 pixels.
Figure 7 shows the results of processing after the first iteration (Fig. 7a) and the final result (Fig. 7b). For comparison, both figures show the initial contours of points before the procedure starts. The result in Fig. 7b has a smaller deviation than initial approximation on Fig. 7a.
In this paper we have proposed a number of algorithms which use the skeleton-contour image representation: 1. the algorithm for estimating the radius of a point object; 2. the algorithm for point objects classification; 3. The algorithm for reconstructing a regular grid of objects.
The experimental study has shown, that the proposed methods have high accuracy and allow significantly accelerate the process of raster map digitizing.
Research has been supported by the RFBR grants (projects No. 15-07-05576 and 16-41-630676). During the research,
BSTransLib library by Leonid Mestetskiy was used [
b) the result