Using moment invariants for classifying shapes on large scale maps

1 USING MOMENT INVARIANTS FOR CLASSIFYING SHAPES ON LARGE_SCALE MAPS Laura Keyes 1BAdam Winstanley Department of Computer Science, National University of Ireland Maynooth Co. Kildare Ireland. HU[email protected]UH, HU[email protected]U 0BABSTRACT Automated feature extraction and object recognition are large research areas in the field of image processing and computer vision. Recognition is largely based on the matching of descriptions of shapes. Numerous shapes description techniques have been developed, such as scalar features (dimension, area, number of corners etc.), Fourier descriptors and moment invariants. These techniques numerically describe shapes independent of translation, scale and rotation and can be easily applied to topographical data. The applicability of the moment invariants technique to classify objects on large-scale maps is described. From the test data used, moments are fairly reliable at distinguishing certain classes of topographic object. However, their effectiveness will increase when fused with the results of other techniques. 1. INTRODUCTION Automatic structuring (feature coding and object recognition) of topographic data, such as that derived from air survey or raster scanning large-scale paper maps, requires the classification of objects such as buildings, roads, rivers, fields and railways. Shape and context are the main attributes used by humans. Our project combines shape recognition techniques developed for computer vision and contextual models derived from statistical language theory to recognise objects. This paper describes a measurement of shape to characterise features that will then be used as input into a graphical language model. The technology to capture paper-based cartographic data through scanning is well founded and the production of raster data relatively easy. The vectorisation of raster data, although not perfect, also is widespread in mapping organisations although it usually requires user intervention to ensure the quality of data. Vectorisation produces vector graphical data but most applications require the data to be structured so it models not only the geometry and topology but also logical contents often stored as a set of attributes attached to the geometry. These are usually captured manually by a human operator but this process of classifying and entering attributes can be a severe bottle-neck in the production flow. This can result in both a scarcity of suitable searchable data and/or a sparseness in its accuracy and detail. Automation of the recognition of objects is the obvious solution but this is a complex problem. 2 Increasing the speed and efficiency of the capture and structuring of data for various kinds of geographical information systems, reduces costs and increases the availability and quality of data. This bottleneck in data structuring has restricted the usefulness and commercial viability of installing and using graphical information systems for specialised applications in small and medium-sized companies. Techniques to overcome these problems will help expand the market for such systems. Feature extraction and object recognition are large research areas in the field of image processing and computer vision. Recognition is largely based on the matching of descriptions of shapes. Numerous shape description techniques have been developed, such as analysis of scalar features (dimensions, area, number of corners etc.), Fourier descriptors, moment invariants and boundary chain coding. These techniques are well understood when applied to images and have been developed to describe shapes irrespective of position, orientation and scale. They can be easily applied to vector graphical shapes. This paper describes experiments, which apply moment invariants to the problem. Experiments carried out to date include the application of Fourier descriptors as features of shape description and recognition. It is envisaged that the Fourier descriptor method can be combined with moment invariants and other techniques of object recognition to produce an optimal result for the problem of shape description of general cartographic shapes on maps. 2. MOMENT INVARIANTS 2.1 Background Moment invariants have been frequently used as features for image processing, remote sensing, shape recognition and classification. Moments can provide characteristics of an object that uniquely represent its shape. Invariant shape recognition is performed by classification in the multidimensional moment invariant feature space. Several techniques have been developed that derive invariant features from moments for object recognition and representation. These techniques are distinguished by their moment definition, such as the type of data exploited and the method for deriving invariant values from the image moments. It was Hu ( Hu, 1962), that first set out the mathematical foundation for two-dimensional moment invariants and demonstrated their applications to shape recognition. They were first applied to aircraft shapes and were shown to be quick and reliable (Dudani, Breeding and McGhee, 1977). These moment invariant values are invariant with respect to translation, scale and rotation of the shape. Hu defines seven of these shape descriptor values computed from central moments through order three that are independent to object translation, scale and orientation. Translation invariance is achieved by computing moments that are normalised with respect to the centre of gravity so that the centre of mass of the distribution is at the origin (central moments). Size invariant moments are derived from algebraic invariants but these can be shown to be the result of a simple size normalisation. From the second and third order values of the normalised central moments a set of seven invariant moments can be computed which are independent of rotation. 3 2.2 Theory Traditionally, moment invariants are computed based on the information provided by both the shape boundary and its interior region (Hu, 1962, Prokop and Reeves, 1992). The moments used to construct the moment invariants are defined in the continuous but for practical implementation they are computed in the discrete form. Given a function f(x,y), these regular moments are defined by: (1) Mpq is the two-dimensional moment of the function f(x,y). The order of the moment is (p + q) where p and q are both natural numbers. For implementation in digital from this becomes: (2) To normalise for translation in the image plane, the image centroids are used to define the central moments. The co-ordinates of the centre of gravity of the image are calculated using equation (2) and are given by: (3) The central moments can then be defined in their discrete representation as: (4) The moments are further normalised for the effects of change of scale using the following formula: (5) Where the normalisation factor:  = (p + q / 2) +1. From the normalised central moments a set of seven values can be calculated and are defined by: 1 = 20 + 02 2 = (20 - 02)2 + 4211 3 = (30 - 312)2 + (03 - 321)2 4 = (30 + 12)2 + (03 + 21)2 dxdyyxfyx qp pq ),(    ),( yxfyx qp pq     00 10   x 00 01   y     qp pq yyxx )()(      00 pq pq  4 5 = (330 - 312)(30 + 12)[(30 + 12)2 –3(21 + 03)2] + (321 - 03)(21 + 03)  [3(30 + 12)2 – (21 + 03)2] 6 = (20 - 02)[(30 + 12)2 – (21 + 03)2] + 411(30 + 12)(21 + 03) 7 = (321 - 03)(30 + 12)[(30 + 12)2 - 3(21 + 03)2] + (312 - 30)(21 + 03)  [3(30 + 12)2 – (21 + 30)2] (6) These seven invariant moments, I, 1  I  7, set out by Hu, were additionally shown to be independent of rotation. However they are computed over the shape boundary and its interior region. 2.3 New moments When dealing with shape recognition of objects on maps we are dealing with objects in isolation, where we only know information about the outline of the shape. For this purpose the moment invariants used in this paper are computed using the shape boundary only and are proven to be invariant under object translation, scale and rotation (Chaur-Chin Chen, 1993). Then, using the same notation for convenience, the moment definition in equation (1) can be expressed as: (7) For p, q = 0,1,2,3, where c is the line integral along the curve C and ds =  ((dx)2 + (dy)2). The central moments can be similarly defined as: (8) Given that the centroids are as in the regular method: (9) For a digital image, then equation (8) becomes (10) Thus the central moments are invariant to translation. These new central moments can also be normalised such that they are scaling invariant.   C qp pq dsyx  C qp pq dsyyxx )()(  00 10   x 00 01   y    C qp pq yyxx ),( )()(  5 (11) Where the normalisation factor is:  = p + q + 1. The seven moment invariant values can then be calculated as before using the results obtained from the computation of equation’s (7) to (11) above. 3. MOMENT INVARIANTS APPLIED TO TOPOGRAPHIC DATA The recognition and description of objects plays a central role in automatic shape analysis for computer vision and it is one of the most familiar and fundamental problems in pattern recognition. Common examples are the reading of alphabetic characters in text (Dehghan and Faez, 1997) and the automatic identification of aircraft (Dudani, Breeding and McGhee, 1997). Most applications using moment invariant for shape recognition deal with the classification of such definite shapes. To identify topographic objects each of the techniques need to be extended to deal with general categories of shapes, for example houses, parcels and roads. Figure 1: Section of a digital map plan The data used for the experiments described in the following sections was extracted from vector data sets (NTF level 2) representing large-scale (1:1250) plans of the Isle of Man (Kelly and Hilder 1998), an example of which can be seen in figure1. A preprocessing operation was required to transform the vector data from its original form to a new form suitable for further processing. In this case the data was pre-processed to extract closed polygons from lines with the same feature codes. After extracting the required polygonal data from the maps, an interpolation method was applied to sample the shape boundary at a finite number (N) of equi-distant points. . These points represent the x and y co-ordinates of the polygonal shape. The points are stored     00 pq pq  6 and then processed by a moment transformation on the outline of the shape, which produces seven moment invariant values that are normalised with respect to change of size (scale), change of position (translation) and change of orientation (rotation) and can be used to discriminate between shapes. Given two sets of moment invariant values, how do we measure their degree of similarity? An appropriate classification procedure is necessary if unknown shapes are to be compared to a library of known shapes. The moment invariant implementation produced sets of real values. If two shapes, A and B produce a set of values represented by a(i) and b(i) then the distance between them can be given as c(i) = a(i) – b(i). If a(i) and b(i) are identical then c(i) will be zero. If they are different then the magnitudes of the coefficients in c(i) will give a reasonable measure of difference enabling discrimination between shapes. It proves more convenient to have one value to represent this rather than a set of values that make up c(i). The easiest way is to treat c(i) as a vector in a multi-dimensional space, in which case it’s length, which represents the distance between the planes, is given by the square root of the sum of the squares of the elements of c(i). 4. RESULTS In this section a sample of the results produced by the application of the moment invariants technique is presented to evaluate their usefulness in shape discrimination of general cartographic features. Figure 2 plots the average values obtained for five categories of objects from the sample maps. This shows that in order to classify shapes with any degree of certainty, the variation within classes must be less than that between classes. Figure 2. Average moment invariants (IM) of five sample shapes To evaluate moments as a shape recognition technique, several shapes from the map (buildings, parcels and roads) were used as test images. As an example Figures 3 and 0.03 0.04 0.05 0.06 0.1 0.2 0 0.02 0.04 0.06 IM(0) IM(1) IM= (2) Building Parcel Road Railway Stream 7 4 show respectively building and parcels on a portion of one map. The moment invariants are computed from the equally spaced (x, y) points (512 sample points) along the boundary of each test shape using the formulae derived earlier. The following table is an example of a set of seven invariant moments (IM) obtained for a house and parcel shape (starting at index IM(0)). Buildings Roads Parcels IM(0) 0.00021913563 0.0191903068 0.19419031 IM(1) 1.4175713e-08 0.0028776518 0.0093515524 IM(2) 3.3163274e-12 0.0000022101 0.00055687797 IM(3) 7.332081e-14 0.0000002565 1.0685037e-05 IM(4) 2.4223892e-14 0.0000001930 5.696268e-05 IM(5) -7.51903311e-18 -3.7718e-08 -6.2343667e-07 IM(6) 2.12921403e-26 -1.5393e-14 3.212549e-11 Table 1: moment invariant values calculated for a house and a parcel shape. 3.43 3.4305 3.431 3.4315 3.432 3.4325 x 10 5 3.809 3.8095 3.81 3.8105 3.811 x 10 5 Figure 3: Sample data representing house shapes. 8 3.428 3.429 3.43 3.431 3.432 3.433 3.434 x 10 5 3.804 3.8045 3.805 3.8055 3.806 3.8065 3.807 3.8075 3.808 x 10 5 Figure 4: Sample parcel shapes. In this paper the moment invariants were calculated for three types of features namely buildings, parcels and roads in six different categories. These categories are buildings, defined natural land cover, multiple surface land, general unmade-land, made-road and roadside. Figure 5 shows a plot of the mean values for each of the above named categories in three-dimensional space. The results obtained for each data set were plotted in three-dimensional space using the features (IM(0),IM(1),IM(2)) to observe how well they separated or to see if they did separate using the moment invariants shape recognition method. Figure 6 shows the degree to which three of these data sets (unmade-land, surface land and buildings) cluster in (IM(0),IM(1),IM(2)) space. Figure 5. Average moment invariants (IM) of six shape categories 10-6 10-4 10-2 10-15 10-10 10-5 100 10-15 10-10 10-5 100 IM0 IM1 IM 2 + = building *= definedland <= surface land o = unmade-land = road x = roadside 9 Figure 6: Clustering of the polygon shapes in three-dimensional space of the features IM(0), IM(1) and IM(2). Figure 7(a). Clustering of the polygons, buildings and defined land cover, 7(b). Clustering of the polygons, defined land cover and unmade-land in three dimensional space of the features IM(0), IM(1) and IM(2). Figure 7(a) above shows the degree to which the data sets, building and defined land cover cluster and also in Figure 7(b), a cluster plot of the data sets, defined land cover 10-8 10-6 10-4 10-2 10-30 10-20 10-10 100 10-20 10-15 10-10 10-5 IM0 IM1 IM 2 unmadeland surfaceland building 10-10 10-5 100 10-30 10-20 10-10 100 10-20 10-15 10-10 10-5 IM0 IM1 IM 2 definedland buildings 10-5 100 10-15 10-10 10-5 100 10-20 10-15 10-10 10-5 definedland and unmadeland