Topographic Object Recognition Through Shape

- 1 - TOPOGRAPHIC OBJECT RECOGNITION THROUGH SHAPE Laura Keyes and Adam Winstanley Technical Report Submitted to Ordnance Survey, Southampton March 2001 Department of Computer Science National University of Ireland, Maynooth Co. Kildare Ireland - 2 - ABSTRACT 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. The recognition of objects in computer vision is largely based on the matching of descriptions of shapes. Fourier descriptors, moment invariants, boundary chain coding and scalar descriptors are methods that have been widely used and have been developed to describe shape irrespective of position, orientation and scale. The applicability of the above four methods to topographic shapes is described and their usefulness evaluated. All methods derive descriptors consisting of a small number of real values from the object’s polygonal boundary. Two large corpora representing data sets from Ordnance Survey maps of Purbeck and Plymouth were available. The effectiveness of each description technique was evaluated by using one corpus as a training-set to derive distributions for the values for supervised learning. This was then used to reclassify the objects in both data sets using each individual descriptor to evaluate their effectiveness. No individual descriptor or method produced consistent correct classification. Various models for the fusion of the classification results from individual descriptors were implemented. These were used to experiment with different combinations of descriptors in order to improve results. Overall results show that Moment Invariants fused with the “min” fusion rule gave the best performance with the two data sets. Much further work remains to be done as enumerated in the concluding section. - 3 - TABLE OF CONTENTS ABSTRACT Chapter 1: INTRODUCTION Chapter 2: SHAPE-BASED DESCRIPTION 2.1 Fourier Descriptors 2.2 Moment Invariants 2.3 Scalar Descriptors Chapter 3: CLASSIFICATION 3.1 Supervised v Unsupervised Classification 3.2 Classification using Bayes Theorem 3.3 Implementing Bayesian Classification Chapter 4: COMBINING CLASSIFIERS 4.1 The Fusion Model 4.2 Theory 4.2.1 The Product Rule 4.2.2 Sum Rule 4.3 Classifier Combination 4.3.1 Majority Vote Rule 4.3.2 Min Rule 4.3.3 Max Rule 4.3.4 Median Rule 4.4 Implementing Data Fusion Chapter 5: EXPERIMENTAL RESULTS 5.1 Individual descriptors Chapter 6: CONCLUSIONS REFERENCES - 4 - Appendix 1: Results from Purbeck data set Appendix 2: Results from Plymouth data set Appendix 3: Classification code Appendix 4: Data Fusion code Appendix 5: Summary of classifications by descriptor method and feature type - 5 - Chapter 1: INTRODUCTION The Intelligent and Graphical Research Group within the Department of Computer Science at National University of Ireland, Maynooth (NUIM) is researching into the automatic recognition of features and objects on topographic maps. The main application of this work is the automatic structuring of topographic data for computer cartography and GIS systems. The techniques being evaluated can be divided into two broad categories: • recognition based on isolated shape (described here), and • recognition based on context. In shape-based classification, the shape of each object is described using a small number of descriptor values (typically 7 to 15 real numbers). Recognition is based on matching the descriptors of each shape to standard values representing typical shapes and choosing the closest match. Several types of descriptor values have been developed (mostly in the field of computer vision). Research at NUIM so far has concentrated on four techniques: • scalar descriptors (area, dimension, elongation, number of corners etc.), • Fourier descriptors, • moment invariants and • boundary chain encoding. 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. Work carried out to date includes the object recognition and classification of buildings and parcels (from test data provided by the Isle of Man government) using three of the above mentioned techniques namely Fourier descriptors, moment invariants and scalar descriptors. Results indicate that no one shape technique alone is powerful enough for the task - in different situations one technique will perform better than the others and produce significant results (e.g. distinguishing buildings from linear features in built-up areas using the moment invariants method). In order to test these techniques further, they were evaluated on a corpus of topographic data provided by OSGB using the feature codes (object types) used in the large-scale OS GB topographic database. The most significant aims were to: • statistically analyse the range of descriptor values obtained by each method both within and between each OS feature type; • evaluate classification performance of each method on all polygons through comparison with original data; - 6 - • investigate possible improvement in performance by evaluating strategies of combining methods; and • evaluate performance of methods in detecting misclassified features in original data. This report describes the results of this exercise. It contains the following sections: 1. The main tasks and aims of the project; 2. A description of the implementation and integration of the software modules for individual methods; 3. An evaluation of each method; 4. A comparison between methods; 5. Combination and selection of methods for optimal results; 6. Conclusions; 7. Suggestions for future research derived from the conclusions. - 7 - Chapter 2: Shape-based Classification 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. This project uses shape recognition techniques borrowed from the field of computer vision to describe a measurement of shape to characterise and classify features on maps. The main application of this work is the automatic structuring of topographic data for computer cartography and Geographical Information Systems (GIS). Recognition of objects is largely based on the matching of description of shapes with a database of standard shapes. Numerous shape description techniques have been developed such as, Fourier descriptors, moment invariants and scalar features (area, number of points, etc.). Previous work has evaluated these techniques on topographic objects as depicted in large-scale mapping. Unlike many applications where the shape categories are very exact (for example, identifying a particular type of aircraft in a scene), this problem requires the classification of a particular shape into a general class of similar object shapes, for example, building, road or parcel. Each technique proved partially successful in distinguishing classes of object although no one technique provided a general solution to the problem. As part of this report these techniques are further evaluated on a real-world problem using a corpus of topographic data provided by Ordnance Survey in Great Britain (OS GB). The data set consists of the features codes (object types) used on the large-scale OS GB topographic database. This report 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 recognition techniques individually and describe how they are applied as general classifiers to broad classes of topographic shape (buildings, fields and road etc.). The overall implementation of the project and experiment is outlined and sets out the most significant aims of the report. An - 8 - evaluation and comparison is made of the effectiveness of each technique in recognising features and objects. A data fusion technique is then proposed and evaluated. This allows the combining of the results of the Fourier descriptor, moment invariants and scalar descriptor techniques respectively, to give an overall score for each candidate object category. The purpose of this report is to draw from our results the main conclusions and see if they are applicable to OS. 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 and the automatic identification of aircraft. Most applications using Fourier descriptors, moment invariants and scalar descriptors for shape recognition deal with the classification of such definite shapes. To identify topographic objects each of the techniques needs to be extended to deal with general categories of shapes, for example houses, parcels and roads. The data used for the experiments described in the following sections was extracted from vector data sets representing large-scale (1:1250) plans of the Purbeck and Plymouth areas in Great Britain (Ordnance Survey). The data had been pre-processed to extract minimal closed polygons and OS feature codes had been applied. An interpolation method was applied to sample the shape boundary at a finite number (N) of equidistant points. These points are then stored in the appropriate format for processing with each shape description technique. The shapes can then be described using a small set of descriptor values (typically 7 to 10 real numbers). The recognition is based on matching the descriptors of each shape to standard values representing typical shapes and choosing the closest match. 2.1 Fourier Descriptors 2.1.1 Background Fourier transform theory (Gonzalez and Wintz 1977) has played a major role in image processing for many years. It is a commonly used tool in all types of signal processing and is defined both for one and two-dimensional functions. In the scope of this paper, - 9 - the Fourier transform technique is used for shape description in the form of Fourier descriptors. The Fourier descriptor is a widely used all-purpose shape description and recognition technique (Granlund 1972, Winstanley 1998). The shape descriptors generated from the Fourier coefficients numerically describe shapes and are normalised to make them independent of translation, scale and rotation. These Fourier descriptor values produced by the Fourier transformation of a given image represent the shape of the object in the frequency domain (Wallace and Wintz 1980). The lower frequency descriptors store the general information of the shape and the higher frequency the smaller details. Therefore, the lower frequency components of the Fourier descriptors define a rough shape of the original object 2.1.2 Theory The Fourier transform theory can be applied in different ways for shape description. One method works on the change in orientation angle as the shape outline is traversed (Zahn and Roskies 1972), but for the purpose of this paper the following procedure was implemented (Wood 1986). The boundary of the image is treated as lying in the complex plane. So the row and column co-ordinates of each point on the boundary can be expressed as a complex number, x + jy where j is sqrt (-1). Tracing once around the boundary in the counter-clockwise direction at a constant speed yields a sequence of complex numbers, that is, a one-dimensional function over time. In order to represent traversal at a constant speed it is necessary to interpolate equi-distant points around the boundary. Traversing the boundary more than once results in a periodic function. The Fourier transform of a continuous function of a variable x is given by the equation: ( ) ( ) ∫ ∞ ∞− − =dxeufuF uxj π 2 (1) When dealing with discrete images the Discrete Fourier Transform (DFT) is used. So equation (1) transforms to: ( ) ( ) N N x xj euf N uF π 2 1 0 1− ∑ − =       = - 16 - Chapter 3: Classification 3.1 Supervised v Unsupervised Classification Shape description techniques, such as those described in chapter two, generally characterise an object’s shape as a set of real numbers. Classification of objects based on shape therefore consists of comparing these descriptors. Two general forms of classification are 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 identified. These are assumed to represent a class of similar objects. In this scheme, the classes identified emerge from the analysis of the data-set and can depend both on that analysis and the data-set in use. 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 of their descriptors to these characteristic values. Supervised learning therefore requires a way to determine some norms for the values of a particular class and a way to measure whether the descriptor values of an unclassified object belong to the group defined by those norms. A common method to determine the norms for a class is to take a sample of shapes we know to belong to that class and calculate the mean or median values for each descriptor. In addition, a measure of the distribution of values within the sample can be made. Classification then consists to comparing the values of its descriptors with that of the mean, possibly taking into account the distribution for the class. Given two sets of descriptors, how do we measure their degree of similarity? 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) - 17 - will be zero. If they are different then the magnitudes of the coefficients in c(i) will give a reasonable measure of the difference. It proves more convenient to have one value to represent this rather than the 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 its 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). In this way classification can be performed by choosing the class mean that is closest to the shape to be classified. Earlier work on this project used this distance measure in classification with some limited success (Keyes and Winstanley 1999, 2000). However, this method takes no account of the distribution of descriptor values for each class. Therefore it was decided to incorporate the information given by the distribution using Bayesian statistics. 3.2 Classification using Bayes Theorem 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 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 belongs to that class. We can calculate such a probability for each class. We then decide that the object belongs to the class for which it that descriptor gives the highest probability. The objective is to design classifiers that will classify an object in the most probable of the classes given. For example, in the experiment described later in this report, our classification task has six classes, Buildings, Defined Natural Land Cover, Multiple Surface Land, General Unmade Land, Made Road and Road Side, 61,..., ω ω respectively, and an unknown feature type taken from the data-set ( for example a building) represented by the feature vector x . From this the conditional or posteriori probabilities 1,2,...,6 i ),|( = xP i ω can be formed which represent the probability that the unknown feature type belongs to the respective class i ω given that the - 18 - corresponding feature vector takes on the value x . To calculate the posteriori probabilities, Bayes decision theory principles are applied. The first step involves the calculation of the prior probabilities )( i P ω for each class. Take for example the Building class 1 ω and Defined Natural Land Cover (Defined Land) class 2 ω . Then, )( 1 ω Pand )( 2 ω Pdenote the probabilities of a feature type belonging to either class 1 ω or 2 ω respectively before we have considered any descriptor values. As we have a previously classified data-set, we can estimate this priori probabilities as: rOFeaturesTotalNumbe ildingsNumberOfBu P=)( 1 ω rOFeaturesTotalNumbe findLAndNumberOfDe P=)( 2 ω Given these probabilities )( 1 ω Pand )( 2 ω P the first criterion for deciding whether an observed feature type is of type Building or Defined Land would simply be to take the class with the larger probability, which can be written as: 121 then )( )( ω ω ω PPif ≥ 221 then )( )( ω ω ω PPif < Better probability results can generally be obtained by considering additional information about the features such as the mean and standard deviation of each class. Let this additional information be identified by the descriptor vector x (using feature vector to represent more than one single measured feature). Using this information the conditional probabilities )|( xP i ω discussed earlier can be formed. The classification criterion can now be described as: 121 decide then )|( )|( ωωω xPxPif > and 212 decide then )|( )|( ωωω xPxPif > - 19 - Bayes laws can be applied to these conditional probabilities to redefine them in terms of their density functions, which are denoted by )|( 1 ω xf and )|( 2 ω xf . The derivation of the new classification criterion, now in terms of the conditional density functions )|( 1 ω xf and )|( 2 ω xf states that ∑ = =2 1 )()|( )()|( )|( k kk ii i Pxf Pxf xP ωω ωω ω So equation above can be rewritten as: then )()|( )|()( )()|( )|()( 1 2 1 22 2 1 11 ω ωω ωω ωω ωω ∑∑ == ≥ k kk k kk Pxf xfP Pxf xfP if then )()|( )|()( )()|( )|()( 2 2 1 22 2 1 11 ω ωω ωω ωω ωω ∑∑ == < k kk k kk Pxf xfP Pxf xfP if Bayes decision rule is obtained by eliminating the denominator and is as follows: 12211 then )|()( )|()( ωωωωω xfPxfPif ≥ 22211 then )|()( )|()( ωωωωω xfPxfPif < ? )|( )|( )( 1 2 ω ω xf xf xL = )( )( 2 1 ω ω P P T= From the conditional density functions a likelihood ratio )(hL and threshold T can be obtained. Using these functions the above criterion now be expressed as: - 20 - 1 then )( ω xLT ≥ 2 then )( ω xLT < which reads if 1 decide then )( ω xLT ≥2 decide ω else . This criterion can be generalised quite easily to situations involving more than two classes and multiple dimensional feature spaces. So, let k be the number of classes involved in this project which equals six and using the respective conditional density functions )|( i xf ω the Bayesian classification can now be written as follows: i ,1 )}()|({)()|( ωωωωω selectthenPxfMaxPxfif kk kk ki = = 3.3 Implementing Bayesian Classification Applying Bayes Theorem to classification therefore requires: • the calculation of prior probabilities of each class occurring • 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. - 21 - Chapter 4: Combining Classifiers When setting out to design a shape recognition system the ultimate goal is to achieve the best possible classification performance. Attaining this goal involves the application of suitable classification schemes/techniques to the problem. Traditionally an analysis of the results produced by each technique became the basis for choosing one of the classifiers as a final solution. However, it has been observed in many studies that although one technique would yield the best performance, the set of shapes miss-classified by the different classifiers would not necessarily overlap. This suggests that different classifier techniques can offer complementary descriptions of the shapes to be classified, which leads to the combining of the classifiers for improved performance. 4.1 The Fusion Model 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. Figure 1, illustrates the decision combination topology used in this report. Figure 1, Decision combination topology used for fusing the results of three shape recognition methods. Fourier descriptors Moment invariants Scalar descriptors Σ data fusion algorithm map feature data set classified feature - 22 - The approach taken here to the fusion of the recognition techniques used follows a classifier combination scheme developed by Kittler et al[1998]. 4.2 Theory The fusion of individual classifiers is based on a theoretical framework set out in Bayes theorem. Before fusion can take place probabilities must be assigned or calculated indicating the likelihood that a particular object belongs to each available class. Considering the classification problem, where Z is to be assigned to one of m possible classes ),...,( 1m ω ω ,assume there are R classifiers each representing the given pattern by a distinct measurement vector, the measurement vector used by the ith classifier being denoted by xi. In the measurement space each class k ϖ is modelled by the probability density function )|( ki xp ω and its priori probability of occurrence is denoted )( k P ω . The models are considered to be mutually exclusive which means that only one class can be associated with each object. According to Bayes theorem, given measurements i x, ,,...1 Ri = the pattern, Z, should be assigned to the class j ω provided the a posteriori probability of the interpretation is maximum, i.e. assign j Z ω → if ),...,|(max),...,|( 11 Rk k Rj xxPxxP ω ω = (15) The Bayesian decision rule (15) states that in order to use all the available information correctly to reach a decision, it is essential to compute the probabilities of the various hypotheses by considering all the measurements simultaneously. This is however a very expensive computation therefore rule (15) is simplified and expressed in terms of decision support computations performed by the individual classifiers, each exploiting only the information conveyed by the vector i x. Rewriting the a posteriori probability ),...,|( 1Rk xxP ω using Bayes theorem we have: - 23 - ) ),...,( )()|,...,( ),...,|( 1 1 1 R kkR Rk xxp Pxxp xxP ω ω ω = (16) where ),...,( 1R xxp is the unconditional measurement joint probability density. This can be expressed in terms of the conditional measurement distributions as follows: ∑ = =m j jjRR Pxxpxxp 1 11 )()|,...(),...,( ωω (17) Therefore, in the following placing the concentration only on the numerator terms of (16). 4.2.1 The Product Rule The measurement )|,...( 1kR xxp ω represents the joint probability distribution of the descriptor values extracted by the classifiers. Treating the representations used as conditionally statistically independent (as outlined by Kittler et al ), the following can be obtained, ∏ = =R i kikR xpxxp 1 1)|()|,...,( ωω (18) where )|( ki xp ω is the measurement model of the ith representation. Substituting from (18) and (17) into (16) gives: ∑∏ ∏ = = =m j R ijij R ikik Rik xpP xpP xxP 1 1 )|()( )|()( ),...,|( ωω ωω ω (19) and using (19) in (15) gives the following decision rule. assign j Z ω → if )|()(max)|()( 1 1 1 ∏∏ = = = =R i kik m k R i jij xpPxpP ωωωω - 24 - (20) Putting this in terms of the a posteriori probabilities yielded by the respective classifiers: assign j Z ω → if )|()(max)|()( 1 )1( 1 1 )1( ∏∏ = −− = = −− =R i ikk R m k R i ikj RxpPxpP ωωωω (21) The decision rule in (21) quantifies the likelihood of a hypothesis by combining the a posteriori probabilities produced by the individual classifiers by means of a product rule. It can be a severe rule of combining the classifier outputs as a single descriptor to inhibit a particular interpretation by outputting a close to zero probability for it. 4.2.2 Sum Rule Kittler et el [1998] developed a scheme for the fusion of individual classifiers called the sum rule which he based on the above theoretical framework. Considering the decision rule in (21) and based on the assumption that the a posteriori probabilities computed by the respective classifiers will not deviate dramatically from the prior probabilities, the posteriori probabilities can then be expressed as: )1)(()|( kikik PxP δ ω ω + = (22) where ki δ satisfies ki δ << 1. Substituting (22) for the posteriori probabilities in (21) gives: ∏∏ == −− += R i kik R i ikj RPxPP 11 )1( )1()()|()( δωωω (23) Expanding the product and neglecting any terms of second and higher order, we can approximate the right hand side of (23) as: ∏∑ == +=+ R i R i kikkkik PPP 11 )()()1()( δωωδω (24) - 25 - By substituting (24) and (22) into (21) the sum decision rule is obtained. assign j Z ω → if )]|()()1[(max)|()()1( 11 1ik R i k R i m k ikj xPPRxPPR ωωωω ∑∑ == =+−=+− (25) The sum of the classifiers R is obtained for each class ωk and the likelihood class computed by taking the maximum a posteriori probabilities produced by the sum combination scheme. 4.3 Classifier Combination The product and sum decision rules in (21) and (25) form the basic schemes for classifier combination. Many combination strategies can be developed from these rules by noting that: )|(max)|( 1 )|(min)|( 11 11ik R i R i ikik R i R i ik xPxP R xPxP ωωωω ∑ ∏== ==≤≤≤ (26) This shows that the product and sum rules can be approximated by the upper or lower bounds suggested by (26), as appropriate. Also the hardening of the a posteriori probabilities )|( ik xP ω to produce binary valued functions ki ∆ as          =∆ = = )|( 1 max) i x|( if 1 otherwise 0 i x j P R i k P ki ωω (27) result in the combining of a decision outcome rather than just the combining of posteriori probabilities. From these approximations the following rules can be constructed. All the combination schemes and their relationship are represented in Figure 2. - 32 - To evaluate each of the methods as shape recognition techniques, several shapes from the map (buildings, parcels and roads) were used as test shapes. For the Fourier descriptor and moment invariants methods, the descriptor values used to describe the objects are computed from the equally spaced (x,y) points along the boundary of each of the test shapes using the formulae derived in chapter 2. The scalar descriptors are calculated from the boundary of the objects also, using the scalar shape recognition aspects described in chapter 2. The aspects used are: area; perimeter length; elongation; and number of points. Table 3 is an example of the first 16 low-order Fourier descriptors obtained for a house shape, FD(0) represents the first descriptor value. 0 1.0000 0.0440 0.0415 0.0461 0.0283 0.0095 0.0050 0.0153 0.0013 0.0013 0.0067 0.0048 0.0006 0.0019 0.0043 Table 3: Fourier descriptor values calculated for a house shape. From inspection of the values produced for each polygon, most of the shape information is described by the first few descriptors and so only the first 16 terms were used for comparison, remembering that due to the normalization procedures, FD(0) and FD(1) are redundant. Table 4 is an example of a set of seven invariant moments (IM) obtained for a house, road and parcel shape (starting a 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 4: Moment invariant values calculated for house, road and parcel shapes. In this paper each of the shape description techniques, Fourier descriptors, moment invariants and scalar descriptors, were computed for three types of feature, namely buildings, parcels and roads in six different sub-categories used in Ordnance Survey large-scale data-sets (Table 1). - 33 - Figure 4, shows a plot of the mean values for each of these categories in threedimensional space (using the moments invariants method in this example). 10-6 10-4 10-2 10-1 5 10-1 0 10-5 100 10-1 5 10-1 0 10-5 100 IM 0 IM 1 IM 2 + = buildin g *= defin edland <= surface lan d o = unm ade-lan d = road x = roadside Figure 4: Average moment invariants (IM) of six shape categories (Purbeck data) A sample of the results produced by the application of the Fourier descriptors is presented to evaluate their usefulness in the shape discrimination. These results obtained for each data set were plotted using the Fourier descriptor s (FD(2), FD(3), FD(4)) to observe how well the formed separate groups. Figure 5 (a) and (b) and Figure 6 (a) and (b) below show the degree to which these data set cluster in FD(2), FD(3), FD(4) space. Note, that due to normalisation the first two terms obtained in the Fourier descriptors set, FD(0) = 0 and FD(1) = 1 are redundant. Figure 5 (a): Clustering of the polygon shapes, buildings and defined natural land cover in three-dimensional space of the features FD(2), FD(3) and FD(4), (b): 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0 0.1 0.2 0.3 0.4 0.5 FD(2) FD(3) FD (4) Definedland and buildings 0 0.1 0.2 0.3 0.4 0 0.1 0.2 0.3 0.4 0 0.05 0.1 0.15 0.2 FD(2) FD(3) FD (4) Building And Road - 34 - Cluster of the polygon shapes, buildings and made-road in three-dimensional space FD(2), FD(3) and FD(4 Figure 6 (a): Clustering of the polygon shapes, made-road and roadside in threedimensional space of the features FD(2), FD(3) and FD(4), (b): Clustering of the polygon shapes, surface land, unmade-land and buildings in three-dimensional space FD(2), FD(3) and FD(4). As thses plots show, often no two feature classes are completely distinct from each other. This evidence therefore indicates that Fourier descriptors are not very good for use in shape description where the data sets are of a very general shape. To show this mathematically the repeatability function was computed for each of the six map categories. Table 5 shows these measurements in FD(2) as it is the most significant descriptor value. The repeatability of the measurements of each class is represented as three times the standard deviation and can be seen in the shaded diagonal column of the table. The repeatability of each class is sizeably larger than the distance between the mean values for all the six classes which shows that the classes are not distince enough to conclude any significant positive results. Buildings Definedland Surfaceland Unmade-land MadeRoad Roadside No. polygons 7976 3147 3003 1251 487 458 Buildings 0.5166 0.0890 0.3590 0.1095 0.0495 0.0343 Definedland 1.1877 0.2700 0.0205 0.0395 0.0547 Surfaceland 1.7972 0.2495 0.3095 0.3247 Unmade-land 1.3156 0.0600 0.0752 MadeRoad 1.1323 0.0152 Roadside 0.7112 Table 5: Comparison of repeatability within feature classes and distance between classes for the Fourier descriptor technique in FD(1). A sample of the results produced by the application of the moment invariants technique was also evaluated. The Figure 7 shows plots obtained for the moment 0 0.2 0.4 0.6 0.8 0 0.1 0.2 0.3 0.4 0 0.05 0.1 0.15 0.2 Made-road Road side FD(4) 0 0.5 1 1.5 2 0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8 FD(2) FD(3) FD (4) Surface Land Unmade Land Building - 35 - invariants technique for a sample of each feature type, each plot showing the degree to which each set of objects cluster in their three-dimensional space. 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 10-10 10-5 100 10-30 10-20 10-10 100 10-20 10-15 10-10 10-5 IM0 IM1 IM 2 MadeRoad buildings Figure 7. Clustering of the polygon shapes, buildings and made-roads, in threedimensional space of the features IM(0),IM(1) and IM(2). Figure 7 shows the degree to which the data sets, building and defined land cover cluster and also in a cluster plot of the data sets, defined land cover and unmade-land. In contrast, it can be seen how the features buildings and roads separate when plotted. To measure the clustering obtained, the repeatability function and mean value measurements were computed for each set or the sample shapes. The results can be seen in table 6. Only the first moment invariants measure, IM(0) is used here to make it easier to read the table as it is the most significant moment result. Buildings Definedland Surfaceland Unmade-land MadeRoad Roadside No. polygons 7976 3147 3003 1251 487 458 Buildings 5.2005e-005 8.8572e-004 1.5488e-005 0.0034 0.0014 4.8116e-004 Definedland 0.0138 8.7023e-004 0.0025 5.5596e-004 4.0456e-004 Surfaceland 3.9330e-004 0.0033 0.0014 4.6567e-004 Unmade-land 0.0231 0.0019 0.0029 MadeRoad 0.0188 9.6051e-004 Roadside 0.0048 - 36 - Table 6: Comparison of repeatability within feature classes and distance between classes for the moment invariants technique in IM(0). Each output for the moment invariants method in the shape recognition of general shapes on maps, show that there is a significant separation occurring between most of the classes. Although overlap does exist (also seen by the human eye) good classification occurs. On examining Table 6 more closely it can be seen that the repeatability for the buildings is smaller than the distance between the mean values for all categories except for the surface land data set though these values are close. This is also true for the repeatability measure for the surface land class where the distance between the means values is larger except for buildings. Comparing the figures obtained for the other data sets we see that for many the repeatability measure is larger but still close to the mean distance for most cases. As presented above for the Fourier descriptor and moment invariants methods, a sample of the results produced by applying the scalar descriptor technique to the data set is evaluated also. Figures 8 to 11 show the resulting cluster graphs and the degree to which the features separate in the three-dimensional space of area, perimeter and number of points. 10 0 10 2 10 4 10 6 10 1 10 2 10 3 10 4 10 0 10 1 10 2 10 3 Defined land Building AREA PERIMETER NO OF POINTS - 37 - Figure 8 Clustering of the polygons, buildings and defined land cover, in the three-dimensional space area, perimeter and number of points 10 2 10 4 10 6 10 1 10 2 10 3 10 4 10 0 10 1 10 2 10 3 10 4 Figure 9 Clustering of the polygons, defined land cover and unmade-land, in the three-dimensional space area, perimeter and number of points 10 2 10 4 10 2 10 4 10 1 10 2 AREA PERIMETER NO OF POINTS Figure 10 Clustering of the polygons, buildings and made-road, in the threedimensional space area, perimeter and number of points Defined land and Unmade land Building Made-road AREA PERIMETER NO OF POINTS - 38 - 10 0 10 2 10 4 10 6 10 0 10 2 10 4 10 0 10 1 10 2 10 3 10 4 Figure 11 Clustering of the polygons, buildings, surface land and unmade land, in the three-dimensional space area, perimeter and number of points Figure 8 shows the cluster plot of the data sets defined natural land cover and buildings. In Figure 9 a cluster plot of the features defined natural land cover and unmade land. Figure 10 and Figure 11 show the degree to which the data sets buildings and made-roads cluster and the degree to which the data sets buildings, surface land and unmade land cluster. To analysis the results further the results are again represented mathematically, in this case by computing the repeatability function and mean value measurements for the area, which is considered the most significant feature descriptor for the scalars. The table for the repeatability and mean values is as follows: Buildings Definedland Surfaceland Unmade-land MadeRoad Roadside No. polygons 7976 3147 3003 1251 487 458 Buildings 962.3439 1.2793e+04 250.4747 3.8176e+04 1.0369e+03 255.5874 Definedland 1.0665e+05 1.2543e+04 2.5382e+04 1.1757e+04 1.2538e+04 Surfaceland 1.7478e+03 3.7925e+04 786.3982 5.1127 Unmade-land 1.1575e+05 3.7139e+04 3.7920e+04 MadeRoad 6.7577e+03 781.2856 Roadside 1.7528e+03 Table 7: Comparison of repeatability within feature classes and distance between classes for the scalar descriptor technique in area. Buildings Surface land Unmade land NO OF POINTS PERIMETER AREA - 39 - The outputs obtained for the scalar descriptor method of general shapes on maps show that there is a significant distinction between the majority of the classes. Some overlap exits but overall classification is good. On examination, table 7 shows, especially for the building features, that the repeatability is smaller than than the distance between the mean values which indicates good classification performance for the scalar method. As shape descriptor techniques the evidence published to date is that all three techniques evaluated, Fourier descriptors, moment invariants and scalar descriptors, are very good features to use when dealing with very specific shapes such as a particular aircraft or alphanumeric character. On investigation of their usefulness for the shape description of general shapes on maps, for example houses, roads, parcels etc. the Fourier descriptors do not appear to be very successful. However, the moment invariants technique proved to be significantly more successful in its task and specific scalar measures are also very discriminatory. This is illustrated by the pie charts in Figure 12 derived from the results summary in Appendix 5. Each chart shows the classification results on objects belonging to each of the six feature types considered. For example, scalar descriptors correctly classified almost 100% of buildings. 100% < 1%< 1%< 1%< 1%< 1% 59% 36% 3% 1% 84% 1% 15% < 1%< 1%< 1% < 1% 100% < 1%< 1%< 1%< 1% 72% < 1% 19% 8% 98% 2% Building DefinedLan d SurfaceLan d UnmadeLand MadeRoad RoadSide Scalar descriptor method Building Defined Natural land Surface Land General Unmade Land Made Road Road Side - 40 - 99% < 1%< 1%< 1%< 1%< 1% 92% 7% 1% 93% 4% 3% 100% < 1%< 1%< 1%< 1%< 1% 98% 2% 98% < 1%2% Building DefinedLand SurfaceLand UnmadeLand MadeRoad RoadSide Fourier Descriptor method Building Defined Natural Land Surface Land Unmade Land Made Road Road Side 100% < 1%< 1%< 1%< 1%< 1% < 1% 62% 16% 22% < 1%< 1% 13% 34% 53% < 1%< 1%< 1% < 1%< 1%< 1% 100% < 1%< 1% 63% < 1% 23% 3% 6% 3% 48% 8% 26% < 1%< 1% 18% Building DefinedLand SurfaceLand UnmadeLand MadeRoad RoadSide Moment Invariants method Building Defined Natural Land Surface Land Unmade Land Made Road Road Side Figure 12 Recognition performance of descriptor methods by feature type. - 41 - 5.2 Fusion methods Six methods of data fusion were implemented: majoity vote, max rule, min rule, median rule, sum rule and product rule). Two of these (sum and product) 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 (Table 8, section 7.3.1) • Each descriptor fused into its group (3 groups i.e. scalar, FD and MI) to obtain a result for each group (Table 8, section 7.3.2 – 7.3.4) • Each group result fused to obtain an overall result (Table 8, section 7.3.5). Table 8 shows that, 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 1998] which questions the theoretical basis of the sum rule. 7.3 Performance of fused descriptors over all selected features Number of polygons processed: 8837 7.3.1 All 25 Descriptors ALL majority max min median sum sum adj product product adj number 5978 5974 7047 5992 5992 186 6938 6603 percent 68 68 80 68 68 2 79 75 7.3.2 Scalar Descriptors SCALARS majority max min median sum sum adj product product adj number 6195 6010 6592 6223 6185 196 6381 6552 percent 70 68 75 70 70 2 72 74 7.3.3 Fourier Descriptors FOURIERS majority max min median sum sum adj product product adj number 5940 5958 5789 5921 5949 175 5837 5815 percent 67 67 66 67 67 2 66 66 7.3.4 Moment Invariants MOMENTS majority max min median sum sum adj product product adj number 6192 6051 7122 6281 6119 6026 7004 6973 percent 70 68 81 71 69 68 79 79 7.3.5 Majority of 3 methods MAJORITY majority max min median sum sum adj product product adj number 6102 6025 6544 6134 6076 198 6294 6419 percent 69 68 74 69 69 2 71 73 Table 8: Summary of performance of fusion of descriptors on all features in Plymouth data set showing number and percentage correctly classified.