5 Automated Point Pattern Recognition in a Raster Map

In this section we present an alternative solution for the problem of automated recognition of point patterns in a raster map digitized in color. For this we use correlation, skeleton extraction and a neural wave propagation network. We asume that the point patterns to be recognized are relatively invariant in scale and rotation.

5.1 Introduction

We consider a thematic raster map (Fig. 1) with point objects (Fig. 2). These objects represent different types of cartographic patterns in the map. The sizes of these objects are small in relation to the size of the territory represented in the map. The point patterns considered are relatively invariant in scale and rotation.

The principal problems we find in comparing a pattern of a point object to objects of the same type in the map are differences in color between occurences of the object, and color deformations in the objects (Fig. 3). The main causes of this are the overlapping of a point object with other object(s), printing variations in the scanned paper map, noise in the digital image of the map and errors in the map digitization stage.

Note that a particular problem exists for certain maps, namely that they do not contain a standard point object symbology, presenting a disadvantage in the application of the solution proposed here, as the neural network must be previously trained with the patterns which it is to recognize. If some patterns can be found in the map which were not considered in the training of the neural network in the recognition stage, the system will produce errors. Nevertheless, if the network is trained with a sufficient range of patterns, the system will work correctly for wide classes of different maps.

Our system comprises four main stages; (i) extraction of skeletons of certain patterns (pre-processing), (ii) identification of possible candidates to be the point object searched for by correlation (pre-processing), (iii) discrimination and selection of objects identified in stage (ii) by the application of a wave propagation neural network (processing), and (iv) automated correction of recognition errors if necessary (post-processing). 

In the following sections we elaborate on each of these stages and show an example of the application of the proposed method.

5.2 Training of the Wave Propagation Neural Network

To train the wave propagation neural network we select the set of point patterns which we wish the system to be able to recognize. We then select samples of each object obtained from the map and store them in separate files. Each file is a matrix of binary values in which the shape of the pattern is described (Fig. 4) by a "1" (one) to represent information and a "0" (zero) to represent the absence of information. This matrix is input to a network training program which outputs values of the weights for the network.

5.3 Selection of the point pattern

The recognition task starts with choosing the point pattern which we wish to find on the map. The pattern is selected by the user and enclosed in rectangular masks of equal size. In order to obtain good final results it is recommended that the pattern be taken from some part of the map or from the map legend where noise is minimized as much as possible and the pattern does not overlap with any other object(s).

5.4 Binarization

Having isolated the point pattern, we derive the range of its color tones and binarize it (Fig. 5). 

Since color maps use the RGB model, it is convenient to convert to the HSI model. For this we apply the following equations; for given RGB components of the image, its HSI components are [14]:
 

Once the range of color tones is obtained we apply chromatic filtering (Fig. 6), which consists in the elimination of those color tones that do not belong to the established range. The map is then binarized (Fig. 7).

5.5 Extraction of the skeleton of the point pattern

For certain point patterns, we extract their skeletons prior to selecting candidates (Fig. 8). Better final results are obtained with this type of pre-processing. Lantunéjoul's equation [14] is used to extract the skeleton of the pattern. The operations of erosion and opening of the mathematical morphology are given by:

where B is a structure element and (AQkB)  indicates k subsequent erosions of A; this is:

k times where K is the last iterative erosion step, when an empty set is obtained. In other words:

where the symbol (°) denotes the opening operation.

5.6 Selection of candidates

Once the point pattern to be recognized is selected, we proceed to identify possible candidates distributed in the map which could be the same type as the selected point pattern (Fig. 9). The principal problem consists in finding from a set of samples on the map the patterns which are most similar to the mask of the selected pattern. Each sample is a partition of the map by the equal-size masks obtained by scanning the entire map. The solution of the problem is obtained by calculating the correlation between the mask of the known pattern and the samples on the map. The candidates will be those objects which maximize the correlation function. Although the correlation approach can be formulated in vector form when we have vector functions, in our case it is much simpler to work directly with the format of images and subimages.

The correlation allows us to find copies of a subimage w (x, y) of size J x K inside an image f (x, y) of dimension N x M, where J£M and K£N. In its simplest form, the correlation between f (x, y) and w (x, y) is [14]:

where s = 0, 1, 2, ..., M-1; t = 0, 1, 2, ..., N-1 and the sum is calculated over the region where w and f overlap.

For any value (s,t) inside the map image, applying the above equation gives a value for c(s,t). Varying s and t, the subimage (pattern) is displaced along the surface of the image (map), given the function c(s,t). The maximal value of c(s, t) indicates the positions where the greatest correspondence is observed between w(x, y) and f(x, y), resulting in the identification of the candidates.

5.7 Selection of the objects of interest

Once, the candidates have been selected it is necessary to establish discrimination criteria that allow efficient extraction of the objects of interest (Fig. 10). The tool used for this is a wave propagation neural network. The principal motivation for this choice is the capacity of such a network for automated adaptation of the weights of the neurons of the intermediate layers, permitting understanding of the relationship between a given set of samples of patterns and their corresponding outputs [15]. This relation is applied to new input vectors which may contain noise or be incomplete, giving an active output if the new input is similar to the vectors introduced during the neural network training (see Section 5.2). The architecture of the neural network model consists of three layers of calculating nodes (neurons). The number of neurons in the first layer, called the input layer, corresponds to the maximum number of pixels that conform to the patterns under analysis. The number of neurons in the output layer is the number of classes of patterns that the neural network is capable of recognizing based on its training. In the intermediate layer, called the hidden layer, we use the activation sigmoid function: 

5.8 Calculation of pixel coordinates

Our program calculates the pixel coordinates of the detected patterns (see Fig. 11). Note that these coordinates can easily be converted to normal geographic coordinates.

5.8 Discussion

The results obtained show that our method is a good alternative for the solution of the problem of automated point pattern recognition. Nevertheless, it is important to note that the neural network must be trained with a large number of point patterns if they are to be recognized in all types of map that might be considered, with a minor number of errors. In the example described above, our system recognized 100% of the "blue palms" present in the map (Fig. 1). Hence in this case we can omit the post-processing stage. For other types of point patterns (Fig. 1 and Fig. 2), our system recognizes more instances of the pattern than actually are present (for example, it finds 17 "triangle patterns" while their true number is 15). We do not discuss here the reasons for this "overshooting error"; however we believe an error in this direction is a sufficiently good result, and consistent with the general goals of our system as described in the present paper (see above).

The results could be improved if we can improve the scanning of the raster image and all stages of its processing (pre-, processing and post-). For example, one could consider other method(s) more efficient than correlation for improving the candidate selection stages, as well as the use of fuzzy logic tools in the decision stage. These could function interactively with the neural network. Moreover the problem could be extended to recognition of point patterns which vary in scale and orientation.

Dirección General de Servicios de Cómputo Académico-UNAM
Ciudad Universitaria, México D.F.