Data Fusion for Topographic Object Classification

Data Fusion for Topographic Object Classification Laura Keyes and Adam Winstanley Department of Computer Science, National University of Ireland, Maynooth. Co. Kildare, Ireland. [email protected]e; [email protected] Abstract - This paper presents research conducted into the automatic recognition of features and objects on topographic maps (for example, buildings, roads, land parcels etc.) using a selection of shape description methods developed mostly in the field of computer vision. In particular the work here focuses on the proposal and evaluation of fusion techniques (at the decision level of representation) for the classification of topographic data. A set of Ordnance Survey large-scale digital data (1:1250 and 1:2500) was used to evaluate the classification performance of the shape recognition methods used. Each technique proved partially successful in distinguishing classes of objects, however, no one technique provided a general solution to the problem. Further outlined experiments combine these techniques, using a data fusion methodology, on the real-world problem of checking and assigning feature codes in large-scale Ordnance Survey digital data. I. INTRODUCTION Topographic data capture for large-scale maps, (typically depicted at 1:1250 and 1:2500) consists of two parts: the digitisation of the geometry and the addition of attributes indicating the feature and/or object type being depicted. Whereas the former can be automated using image processing and similar techniques, the latter is often a manual task. One possible means of automation is object recognition through shape. To date we have concentrated our research on the task of automating the structure of topographic data, using a variety of shape description methods borrowed from the field of computer vision. The results proved partially successful in distinguishing the different classes of objects although no one technique provided a general solution to the problem. This prompted us to investigate the possibility of combining the individual classifiers, using fusion, to obtain an improved overall classification. Automating the structure of topographic data requires the classification of objects such as buildings, roads, fields, rivers and railways. Recognition of objects is largely based on the matching of numerical descriptions of shapes with a database of standard shapes. The shape description methods used include Scalar Descriptors (SD) (area, dimension, elongation, number of corners etc.), Fourier Descriptors (FD) and Moment Invariants (MI). Traditionally these methods are applied to specific shapes (for example, a particular make and model of aircraft), here we evaluate their effectiveness on the more general categories of shapes on maps. These techniques can be applied to object boundaries extracted from remotely sensed data represented either as raster images or vector descriptions. We apply a fusion methodology to combine the results of the individual classifiers to derive an overall consensus decision. The fusion technique we employ in this paper, was developed by Kittler et al [1], and utilises a decision combination topology with a Bayesian approach. In his work Kittler developed a scheme for the fusion of individual classifiers called the product and sum rule. From these schemes he further developed the combination strategies referred to as the majority-vote rule, the max, min and median rules. We test each of these strategies and evaluate how they influence the classification performance of our overall system for the task of recognising general shapes on maps. This paper builds on previous work carried out to produce an accurate combined methodology for the classification of general shapes on maps. The following sections introduce each of the above named shape description techniques and how they are applied as general classifiers to broad classes of topographic shape. The overall implementation of the project and experiment is outlined and sets out the most significant aims of the work. The data fusion technique (at the decision level of representation), is then investigated and evaluated on a corpus of data based on urban areas in the UK. Results and conclusions are presented. II. OBJECT CLASSIFICATION In shape-based classification, the shape of each object is described using a small number of descriptor values (7 to 15 real numbers in our case). Recognition is then based on matching the descriptors of each shape to standard values representing typical shapes and choosing the closest match. Several types of shape recognition methods have been developed including Fourier descriptors [2-10], moment invariants [9-16], and scalar descriptors [9-10], [17]. These techniques are well understood when applied to images and can be normalised to describe shapes irrespective of position, scale and orientation. They can also be easily applied to vector graphical shapes. The data used for the experiment described in the following sections was extracted from vector data sets representing large-scale (1:1250) plans of Basingstoke and Scotland areas in Great Britain (Ordnance Survey GB). The data had been pre-processed to extract minimal closed polygons and OS feature codes had been applied. We applied an interpolation method to sample the shape boundary at a finite number of equi-distant (N) points. These points are  Acknowledgement: This project is supported by Ordnance Survey (GB) and builds on earlier work supported by Enterprise Ireland’s Strategic Research Grants scheme 1998, proposal number ST/98/021. then stored in the appropriate format for processing with each shape description technique. The method of Fourier descriptors is well known and is a frequently used method for the identification of objects with the aid of the boundary. To compute the Fourier descriptor values the Fourier analysis technique is applied to the boundary co-ordinates expressed as complex numbers. The shape descriptors generated from the Fourier coefficients numerically describe the shape Moments can provide characteristics of an object that uniquely represent its shape. Traditionally, they are computed based on the information provided by both the shape boundary and its interior region. For the purpose of this paper, however, the moment invariants are computed using the shape boundary only. This moment invariant technique generates seven real descriptor values, which numerically describe the given shape. Scalar descriptors are based on scalar features derived from the boundary of an object. They use numerous aspects of the object for performing shape recognition. Simple examples of such features include: the perimeter length; the area of the shape; the ratio of the shape to the square of the length of its perimeter (A/P2); the number of nodes and the number of corners. Fig.1. shows the steps involved the shape description process. The results produced by each of these techniques are used in the classification process. There are two general forms of classification possible: unsupervised and supervised. Unsupervised learning occurs where the distribution of descriptor values of objects in a data set is analysed. Clusters of objects of similar shape are assumed to represent a class. Supervised learning occurs when the classes to which objects are to be assigned are decided beforehand. Values of descriptors that characterise each object class are determined in some way and objects are classified through the similarity or their descriptors to these characteristic values. In this work we are using supervised classification through Bayesisn statistics [1]. Bayesian statistics allows us to use the distribution of the values for each descriptor for each class of object in determining the probability that a particular object belongs to Fig. 1. Each shape description technique produce a set of real descriptor values that are used for the shape description of topographical objects Fig. 2. Implementation of Bayes classification scheme likelihoods Descriptor value probabilities distributions a priori probability . . . . . . Bayesian classifier Normal pdf that class. Given a particular value for a descriptor, we can calculate the likelyhood of that value occurring in the distribution of values for a particular class. Applying Bayes theorem, we can calculate from this the probability of the object belonging to that class. We can calculate such a probability for each class. We then decide that the object belongs to the class for which that descriptor gives the highest probability. Applying Bayes theorem to classification requires: the calculation of prior probabilities of each class occurring and the modelling of a distribution function of the likelihoods of values occurring for each class. Both of these were estimated through an analysis of the classification of a data-set provided by Ordnance Survey. The distribution function for each descriptor was approximated as a normal curve, modelled from the means and standard deviations calculated from the data-set. Using Bayesian classification a class can be assigned to each object based on the value of one descriptor. This is accompanied by a probability estimate that the classification is correct. We are evaluating three shape description methods, each containing several descriptors (25 descriptors in all). If, as is likely, these disagree as to the classification, we require a method of combining them to produce an overall consensus as to the correct classification. III. THE FUSION MODEL Pre-processed Using and combining multiple learned classification models for increasing accuracy and efficiency is an area attracting much interest recently. The central problem involved is how to integrate several classifiers (or “experts”) to produce a single final classification. Fig. 3. illustrates the decision combination topology used in this paper. The approach taken here for the fusion of the recognition techniques used, follows a classifier combination scheme developed by Kittler et al [1]. In his work Kittler devised a scheme for the fusion of individual classifiers called the product and sum rule. The Bayesian reasoning searches for an a-posteriori probability of a hypothesis based on the set of standard shapes. This gives us the probability of an input feature belonging to each of the classes. Using this information the above data fusion schemes can be derived. Data Boundary Sampling Shape description techniques FD MI SD Descriptor values Fig. 3. Decision combination topology used for fusing the results of three shape recognition methods areas while Basingstoke is composed of urban and rural areas. Because supervised learning was being used, it was necessary to have an example data set to derive the statistics to provide the likelihood distributions for each descriptor for each class of object. In the early stages of the experiment it was decided to use Purbeck for this purpose. All polygons for each of the feature codes in the Purbeck data were statistically analysed to obtain measures of the mean and standard deviation. A normal distribution was assumed. These distributions were then used to classify each polygon in both the Purbeck and Plymouth data sets using each individual descriptor (i.e. twenty-five results per polygon). The same process was performed using Basingstoke as the training set to allow for the classification of the rural feature type found. Table 1. Shows an example of the object types for Purbeck used in the classification experiment. In Basingstoke this set is extended to include details of other rural feature types found. (for example, varied types of parcel types ). The product of the a-posteriori probabilities generated by the individual classifiers is computed. The class corresponding to the maximum product value is then selected as the decision. Similarly the sum of the a-posteriori can be computed and the class represented by the maximum sum value is taken as the decision. These schemes are further developed into classifier combination strategies, referred to as the majority-vote rule, the max, min and median rules. For the majority vote rule the number of votes received for each individual classifier methods are counted. The class, which receives the largest number of votes, is selected as the majority decision. The max, min and median rules obtain a decision by computing the maximum/minimum/median a-posteriori probabilities for each class, taking the maximum of these values as the combined result. All the methods of data fusion described above were implemented. Each or the shape was classified by individual descriptors with an accompanying measure of certainty or confidence. These were then fused in each of 8 methods and then the resulting classifications measured against the known classes the object belonged to. The individual results from individual descriptors for each polygon were then fused using each method described in section 3 above, producing an overall result treating all IV. EXPERIMENTAL RESULTS TABLE I OBJECT TYPES USED IN THE CLASSIFICATION EXPERIMENT Three data sets were provided by Ordnance Survey (OS) to evaluate shape classification on topographic data: Purbeck, Plymouth and Basingstoke. The data for all the polygons representing the OS feature codes were extracted. The three shape description techniques were calculated from the object boundaries. For the Fourier descriptors most of the shape information is contained in the first few. Therefore the first sixteen were used with FD(0) and FD(1) redundant due to normalisation. So, for each polygon in the set we have twenty-five descriptor values (four scalars, seven moment invariants and fourteen Fourier descriptors (FD(2) to FD(16)). Label used here OS Type OS Description 1 building 2210321 Building (Type A) 2 defined land 1900300 Defined Natural Land Cover 3 multiple surface land 2400339 Multiple Surface Land 4 unmade land 1400342 General Unmade Land 5 road 2610330 Made Road 6 roadside 2610331 Roadside Unknown Land The three data sets used represent mainly two different types of area in the UK. Purbeck and Plynouth are urban twenty-five descriptors equally. This was also done for each of the three descriptor types. Finally the results for each descriptor type were then fused to produce an overall result from all descriptors. Six methods of data fusion were implemented: majorityvote, max rule, min rule, median rule and product rule. Two of these (product and sum) had two versions whether they included or excluded the adjustment for normalisation. They were applied to fuse the classification results given by the descriptors obtained from each polygon in three ways:  Each descriptor (25 in all) treated equally to obtain a global result;  Each descriptor fused into its group (3 groups i.e. scalar, FD and MI) to obtain a result for each group and  Each group result fused to obtain an overall result. Figs. 4, 5 and 6 show the performance for the fused classifications obtained. Fig. 4 represents the results obtained using the urban data sets Purbeck and Plymouth where Purbeck is the training set. Fig.5. Shows the results obtained for Basingstoke as the test and training data set, and Fig. 6 shows Plymouth and Basingstoke with Basingstoke the training data set. Fig. 4. Summary of performance of fusion descriptors on all features in Plymouth data set showing the percentage correctly classified Fig. 5. Summary of performance of fusion descriptors on all features in Basingstoke data set showing the percentage correctly classified Plymouth with Basingstoke 0 10 20 30 40 50 60 70 80 majori ty ma x mi n medi an su m sum a dj produ ct product ad Fusion method Percentage ALL SCALARS FOURIERS MOMENTS MAJORITY Fig. 6. Summary of performance of fusion descriptors on all features in Plymouth data set showing the percentage correctly classified The results in Fig. 4 show with notable exceptions, the classification accuracy obtained was fairly consistent no matter which was used. Best performer was the min rule followed by the product rule. Worst performer by far was the normalised sum rule. This confirms the arguments in Kittler [] which questions the theoretical basis of the sum rule. The classification results in Fig. 5. for Basingstoke (with Basingstoke as the training set) are less successful with the product rule showing the best fused results. The lower percentage of classification may be due to the extra rural feature types used. As we see in Fig. 6 the results improve again for the mainly urban Plymouth data set. Plymouth with Purbeck 0 20 40 60 80 100 majori ty ma x mi n media n su m sum a dj produ ct product adj Fusion method Percentage ALL SCALARS FOURIERS MOMENTS MAJORITY V. CONCLUSION Based on the results presented here, we can claim partial success in demonstrating the application of shape classification to the recognition and feature coding of objects on large-scale topographic maps. We have identified that performance is variable depending on the descriptors used and the object types we are trying to distinguish. Basingstoke with Basingstoke 0 10 20 30 40 50 60 majority max min median sum sum adj product product adj Fusion method Percentage ALL SCALARS FOURIERS MOMENTS MAJORITY VI. REFERENCES [1] Kittler, J., Hatef, M., Duin, R.P.W., and Matas, J., "On Combining Classifiers", IEEE Transactions on Pattern Analysis and Machine Intellegence, Vol. 20, No. 3. 1998 [2] Granlund, G.H., "Fourier Pre-processing for Hand Print Character Recognition", IEEE Transactions on Computers, Vol. C-21, 1972, 195-201. [3] Persoon, E. and Fu, K-s., "Shape Discrimination Using Fourier Descriptors", IEEE Transactions on Pattern analysis and Machine Intelligence, Vol. PAMI-8, No. 3, 1986, 388-397. [4] Reti and Czinege, "Generalized Fourier Descriptors for shape analysis of 3-D closed curves", Acta Stereol, Vol. 12, 1993, pp. 95-102. [5] Keyes, L., Winstanley, A. C., "Fourier Descriptors as A General Classification Tool for Topographic Shapes", in Proceedings of the 1999 Irish Machine Vision and Image Processing Conference (IMVIP), pp. 193-203. [6] Wallace, T. P. and Wintz, P. A., "An Efficient ThreeDimensional Aircraft Recognition Algorithm Using Normalised Fourier Descriptors", Computer Graphics and Image Processing, Vol. 13, 1980, 99-106. [7] Wood, S. L., "Fourier Analysis of Object Boundaries From Two Dimensional Digitised Images", ICASSP 1986, TOKYO. [8] Zahn, C.T. and Roskies, R.Z., "Fourier Descriptors for plane closed curves", IEEE Transaction on Computers, Vol.21, 1972, pp. 269-281. [9] Winstanley, A.C., Automatic Shape Recognition in a Machine Vision System, Dissertation for the degree of Master of Science, Faculty of Science, The Queen’s University Belfast, 1987,. [10] Winstanley, A. C., "Structuring Vector Maps using Computer Vision Techniques", in Conference of the 1998 Association of Geographic Information, Birmingham, pp. 8.11.1-8.11.2. [11] Chaur-Chin Chen, "Improved Moment Invariants for Shape Recognition", Pattern Recognition, Vol. 26, No. 5, 1993, pp. 683-686. [12] Belkasim, S. O. Shridhar, M. and Ahmadi, M. "Pattern Recognition with Moment Invariants: A Comparative Study and New Results", Pattern Recognition, 24: 1991, 1117-1138. [13] Dudani, S. A., Breeding, K.J. and McGhee, R. B., "Aircraft Identification by Moment Invariants", IEEE Transactions on Computers, Vol. C-26. No. 1, 1977, pp 39-45. [14] Hu, M. K., "Visual Pattern Recognition by Moment Invariants", IRE Transactions on Information Theory, Vol, IT-8, 1962, pp. 179-187. [15] Keyes L. and Winstanley A.C., "Using Moment Invariants for Classifying Shapes on Large-scale Maps", Computers Environment and Urban Systems, 25, 2001, 119-130,. [16] Prokop, R .J. and Reeves, A. P., "A Survey of Moment Based Techniques for Unoccluded Object Representation and Recognition", CVGIP: Graphical Models and Image Processing 54: 1992, 438-460. [17] Vernon, D. S. G., Machine Vision, Prentice Hall, 1991. [18] Longley, P. A., Goodchild, M. F., Maguire, D. J., Rhind, D. W., Geographical Information Systems, Wiley 2nd ed, 1999. [19] Gonzalez, R.C. and Wintz, P., Digital Image Processing, Addison-Wesley Publishing Company, 1977.