Generalization-oriented
Pattern Recognition41(2008)1593–
1609
https://www.wendangku.net/doc/c35505519.html,/locate/pr
Generalization-oriented road line segmentation by means of an arti?cial neural network applied over a moving window
Francisco Javier Ariza López,JoséLuis García Balboa?
Grupo de Investigación en Ingeniería Cartográ?ca,Universidad de Jaén,23071Jaén,Spain
Received20April2007;received in revised form7November2007;accepted7November2007
Abstract
In line generalization,results depend very much on the characteristics of the line.For this reason it would be useful to obtain an automatic segmentation and enrichment of lines in order to apply to each section the best algorithm and the appropriate parameter.In this paper we present a methodology for applying a line-classifying backpropagation arti?cial neural network(BANN)for a line segmentation task.The procedure is based on the use of a moving window along the line to detect changes in the sinuosity and directionality of the line.A summary of the BANN design is presented,and a test is performed over a set of roads from a1:25k scale map with a recommendation of the value of the parameters of the moving window.Segmentation results were assessed by an independent group of experts;a summary of the evaluation procedure is shown.?2007Elsevier Ltd.All rights reserved.
Keywords:Arti?cial neural network;Cartographic generalization;Knowledge acquisition;Line segmentation;Machine learning
1.Introduction
Cartographic generalization can be de?ned as a process that aims to simplify the information content of geographical data whilst retaining the essential meaning inherent in the initial data [1].It is one of the main dif?culties when dealing with digital cartography;but nowadays it is also one of the most important cartographic processes,since its goal is the derivation of multi-scale products in an automated and instantaneous way.Lines are the most abundant elements in cartography[2].Lines are present as linear elements and also as perimeters of areal ele-ments.So the existence of adequate generalization techniques for linear elements is essential in the generalization of a map or geographic database.The?rst studies of automatic general-ization of linear elements were mainly devoted to simpli?ca-tion algorithms,their main target being to reduce the number of coordinates to be stored.But research on line generalization is still a burning issue in research(see Refs.[3–15]).A review of the development in digital map generalization can be found ?Corresponding author.Tel.:+34953212844;fax:+34953212854.
E-mail address:jlbalboa@ujaen.es(J.L.García Balboa).
0031-3203/$30.00?2007Elsevier Ltd.All rights reserved.
doi:10.1016/j.patcog.2007.11.009in Li[16]and a wide coverage of algorithms for line elements in Li[17].
Usually cartographic lines are not homogeneous,mainly be-ing a succession of sections with different geometric and vi-sual properties.The performance of a generalization algorithm varies with its control parameters and also depends very much on the line(homogeneity,sinuosity,and so on)to which it is applied.For this reason it would be useful to obtain an auto-matic segmentation and enrichment of lines in order to apply to each section the best algorithm and the appropriate parameters. Therefore,optimal segmentation and classi?cation methodolo-gies would be the?rst goals to achieve for adapting processes, algorithms and parameters to different line types,uses and scales,taking into account basic studies of the performance of line simpli?cation algorithms like Shi and Cheung[14]. Some authors note the importance of the segmentation process;Jasinski[18]indicates as an essential goal the identi-?cation of the graphical structure of the line;Butten?eld[19] and Dutton[20]propose dividing the line into homogeneous sections for a better algorithm and parameters selection;for Visvalingam and Williamson[21]automatic segmentation is a pending topic for research;Richardson and Mackaness[22] highlight the importance of segmentation techniques because of the sensibility of generalization methods to different line types;
1594F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–1609
and for Plazanet[23]segmentation is a process that must take place before generalization in order to take into account local characteristics of the feature.
For Müller[24]cartographers have always tended to preserve the degree of complexity of each perceived section of a line. Skopelity and Tsoulos[25]consider that segmentation can be achieved by using the same measures as those being used to characterize a line.The segmentation of a line is related to[26]:?Homogeneity:The conservation of certain characteristics along a section[25].
?Sinuosity:The character of a line having many(or few) changes of direction or speci?c curvature behaviour such as spirals,hairpins,and so on.
?Complexity:The character of a line being more or less sin-uous,homogenous or dense.
?Critical points:Those that mark changes in a line and can be used to limit sections.
Line segmentation methodologies developed in previous work can be classi?ed as:
?Point removal methods:Simpli?cation algorithms are used so that,after removal,the remaining points indicate section limits.Butten?eld[19],searching for the subdivision of a line into portions using the Douglas–Peucker algorithm,does not speak explicitly about segmentation,but her portions can be considered as sections.Visvalingam and Williamson
[21]point out the possibility of using the Visvalingam and
Whyatt[27]algorithm in a segmentation process.
?Measure-based methods:The idea is to use sound measures for detecting homogeneous sections.An example of this is the work of Skopeliti and Tsoulos[25],which applies the fractal dimension for natural linear elements segmentation.
In García and Fdez-Valdivia[28]a clustering procedure is developed,computing a set of statistical measures over a graph of the curvature values of the line.
?Critical point methods:A non homogeneous spatial distri-bution of critical points implies the presence of different sections.In Plazanet et al.[26,29]and Barillot and Plazanet
[30]a hierarchical segmentation method is proposed,based
on the studies of Mokhtarian and Mackworth[31,32],using in?ection points[23,33,34].
?Geometrical analysis methods:An example is the analysis of the distribution of intersections between the original line and its tendency(obtained by smoothing).It is understood that
a non homogeneous spatial distribution of the intersections
implies different sections.Burghardt[8,35]develops such a method as a previous step to smoothing.?Frequency-based methods:Line?ltering in a length-curvature space by wavelets coef?cients allows us to detect changes in the curvature behaviour of the line.When us-ing this method for line simpli?cation,García Balboa and Ariza[4]point out the possible use of wavelets for line segmentation.
In this article we propose a knowledge-based method,that is, a method in which machine learning is applied,attempting to emulate an expert human segmentation.The goal is to ob-tain an automatic segmentation of a line,from the application of an arti?cial neural network(ANN)for line classi?cation. Werschlein and Weibel[36]underlined the potential that ANNs have in cartographic generalization,emphasizing thematic clas-si?cation,structure recognition,and assessment of alternative generalization solutions.They also speci?cally quoted the pos-sibility of applying ANNs to the segmentation of linear fea-tures into homogeneous sections.Nevertheless,no example of AAN applied to line segmentation can be found,but several for amalgamation[37,38]or typi?cation operation[39].
Our method is part of a large scheme that pursues the auto-matic segmentation and classi?cation of road lines of a medium scale map[40].The choice of road line elements is not a co-incidence.Road lines are always among the main types of ob-jects to be taken into account in any kind of generalization in a national mapping agency[41,42].In this study we develop and apply a segmentation methodology based on a backpropaga-tion ANN(BANN)classi?cation over a moving window along a line.The work is the continuation of that explained in García Balboa and Ariza[15],where the BANN applied is presented. Our study represents a?rst approach to the application of this BANN,and the results could be used to improve the method-ology if deemed necessary.
The contents of this paper are divided into six sections.In Section2,the sample of roads used for this work is presented. Section3summarizes the development of the BANN for line classi?cation,including input and output data de?nition,the BANN design and training.In Section4the methodology for applying the BANN for line segmentation is explained.Results are shown in Section5,suggesting values for the parameters af-ter a tuning process and the corresponding segmentation of the sample;also a methodology and results from an expert assess-ment are included.Finally,discussion is included in Section5 and conclusions are presented in Section6.
2.Sample of road lines
A sample of road lines should be chosen carefully in order to ensure a representative study.So several criteria were taken into account.Lines should belong to the largest number of categories possible,with attention to administrative categories, design guidelines,etc.This would allow the differentiation of behaviours and characteristics according to the line type.For the same reason,in each category there should be,as far as is possible,variability in the routes.This is easier in byroads and tracks because the variations in sinuosity and complexity are more frequent,since their design is less restrictive.In relation to sample size,observing previous studies of line generalization, it is highly variable,from the three elements of Garrido et al.
[3],or the four elements of Jasinski[18],Barber et al.[43], Zhan and Butten?eld[44],Dutton[20]to those studies in which a large set of lines in a geographic scope is selected without specifying quantity[21,29,34,45–48].This last option seems more appropriate,since the validity of the results should be better and because it is closer to a real case of operating with a cartographic product(such as road elements of a sheet).
F .J.Ariza López,J.L.García Balboa /Pattern Recognition 41(2008)1593–1609
1595
Fig.1.Sample of road lines extracted from the 947sheets of the MTN25[66–69].
Table 1
Road sample used in this work Road network Road type Quantity Length (km)Road nomenclature State network
Motorway 125.4A-44Conventional 120.2N-323Andalusian basic network Motorway 18.4A-316A Conventional 116.6A-316
Andalusian regional network Conventional 331.7A-311,A-320,A-324Andalusian complementary network Conventional 115.7A-1102
Jaén provincial network Conventional 977.8JV-2222,JV-2223,JV-2224,JV-2225,JV-2226,JV-3012,JV-3241,JV-3242,JP-2332–
Track
7
65.4
P-CaminoAncho,P-CaminoAzadillas,P-CerroAlmadén,P-CerroJabalcuz,P-CerroSantín,P-Pegalajar-Central,P-SierraPe?aDeláguila
Following these criteria this work uses all tarmac roads and tracks in four sheets from the MTN25(National Topographic Map 1:25k)with a length of over 4km.MTN25series has been considered because it is not a cartography derived by general-ization,but comes directly from the photogrammetric process.Also it is the cartographic series at a larger scale which covers the whole of Spain,so in the future all series at a low scale could be derived from it (as is the new MTN50,National Topographic Map 1:50k).The sheets selected (four 947sheets from MTN25that correspond with one generalized sheet from MTN50)are the closest to our research centre,and contain a set of road lines that complies with planned criteria (see Fig.1and Table 1).
1596F .J.Ariza López,J.L.García Balboa /Pattern Recognition 41(2008)1593–1609
3.Backpropagation arti?cial neural network for generalization-oriented classi?cation
ANNs are part of the ?eld of arti?cial intelligence.ANN the-ory and modelling follow the structure and operation of nervous systems,where a neuron is the fundamental element.Arti?cial neurons try to assume the more important characteristics of bi-ological neurons.Their work is simple:to receive input stimuli from neighbouring neurons and to compute an output value,which is sent to other neurons.
In García Balboa and Ariza [15]a BANN for road line classi?cation was presented.The goal of this BANN is to obtain a classi?cation engine through a supervised learning process.In this section the main characteristics of that BANN are summarized.3.1.The BANN
One of the most widely used ANNs is the BANN.BANN was ?rst described by Werbos [49,50]and developed by Rumel-hart et al.[51].They proposed an ANN with more layers than Rosenblatt’s perceptron [52]in order to allow it to learn the association between the inputs and the corresponding classes using a feedforward structure.A more detailed explanation of the BANN can be found in the aforementioned reference of Werbos [50]and in Rumelhart et al.[53]
.
Fig.2.Segmentation of the sample of road lines.
3.2.Sample of homogeneous road sections for the BANN training
The sample of road lines could be enriched to proceed with the next step of the process,the data enrichment that allows feeding of the BANN.But in order to increase the purity of the classes the BANN is going to distinguish,a line segmenta-tion process is applied.After segmentation the sample of lines is divided into a sample of sections,each one more homoge-neous than the original line.These sections were derived from a semiautomatic segmentation of a set of roads.The segmen-tation method can be any with proven results,such as the one suggested by Plazanet [34],a wavelet ?ltering [4,26],those suggested by García Balboa [40]and so on.The method we used employs an accumulated sum of Visvalingam [27]effec-tive areas,detailed in García Balboa and Ariza [54]and García Balboa [40].So its application is guided,modifying parame-ters and visually inspecting the results,choosing a solution in which a clear difference in the planimetric route characteristics is appreciated and is assessed as valid.This segmentation (and the subsequent classi?cation)divides the line into several but not many sections.Segmentation over the sample of road lines can be observed in Fig.2,with a ?nal result of 73sections.Visual assessment during the semiautomatic segmentation is performed globally,observing the whole line,by means of the detection of sinuosity and directionality changes,as suggested
F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–1609
1597
Fig.3.Examples of visual segmentation,with indications of differences in sinuosity and directionality.
by McMaster[55].Visual analysis allows us to choose among different segmentations of the same linear element.A seg-mentation is preferred which detects variations,as obvious as possible,in sinuosity,directionality or both.Sinuosity has been evaluated by observing the bend size,radius,and the pres-ence of rectilinear stretches.Directionality originates with the presence of rectilinear stretches,but is based on a global ex-amination of the main trend of the line.Naturally,it is easier to compare segmentations in a not very homogeneous line, because the section changes are easier to locate.A more homogeneous line is more dif?cult to segment manually,and therefore it is more dif?cult to compare two different segmen-tations.Fig.3shows an example of segmentations that have been performed following this procedure,indicating whether the sinuosity and the directionality are higher or lower.
This segmentation has been assessed by a group of20in-ternational experts,belonging to different universities and na-tional mapping agencies(see Ref.[40]).They have evaluated the results,taking into account the aforementioned sinuosity and directionality changes,with very positive conclusions. 3.3.Input data de?nition(measures)
Knowledge is assimilated by the BANN when it learns to relate certain measures to the expected class.Therefore,a?rst step to performing every attempt at automatic classi?cation is to select those characterizing measures that are to be used to feed the classifying system.
There are abundant measures that can be employed when characterizing a line or section(see Ref.[56]).Common sense would dictate that the selected measures be signi?cant,not correlated and normalized.These three conditions make the classi?cation task easier.Intuition is also valuable,but a statis-tical study which supports the selection is essential.A princi-pal component analysis(PCA)has been applied,as suggested by McMaster[57],Jasinski[18],Skopeliti and Tsoulos[25], or Mustière[58],to a set of25measures computed over the 73sections of the road sample.Some of these measures have been previously referred to[18,25,26,33,34,56,57]and others have not.Most of them are central tendency(mean,median) and dispersion(coef?cient of variance)measures derived from computations performed on isolated bends.PCA results sum-marized in Ref.[15]and detailed in Ref.[40]allow the selec-tion of nine measures,described in Table2.
It is interesting to consider another type of information that is not quantitative,but qualitative,and is used to train the BANN. Each road belongs to an administrative category,and there is a certain type of implicit geometric knowledge,like the gen-eral criteria in the design of roads of this category,that usually introduces different constraints.Five different categories have been considered,as shown in Table3,and any road to be clas-si?ed should belong to one of these.
3.4.Output data de?nition(classes)
The output data are the classi?cation which the BANN is able to perform.An ambitious goal would be to try to set a high number of different classes.The general criterion should be to establish categories that do not cast doubts on a manual classi?cation by means of visual analysis.We must remember that,if it is dif?cult for a human being to perform the classi-?cation,it is more dif?cult for an ANN trying to emulate hu-man behaviour.Previous studies do not usually establish a high number of classes(see Refs.[25,29,33]).Table4summarizes several studies in which an unsupervised classi?cation has been performed with cluster analysis.It can be said that the number of classes varies between3and4,and that a sinuosity criterion has been applied.
For the de?nition of our classes,an intense visual analysis of the73sections sample has been carried out.Here we have attempted to establish groups of lines that represent classes that take into account differences in sinuosity and directionality. The criteria for this visual assessment are the same as those ap-plied to the semiautomatic segmentation process described in Section3.2.The methodology is based on a repetitive detailed examination and classi?cation of the sections set.Multiple re-visions of the classi?cation have been carried out,starting from a preliminary,coarse revision and re?ning it through section observation.On multiple occasions we found sections which combined properties from more than one class,causing a re-de?nition of the common characteristics of the sections of a class and a reclassi?cation of a certain number of sections. Visual analysis has been performed both on screen and on paper,at different zoom levels.This visualization has been per-formed in two ways:in the original relative location,making the comparison between consecutive sections of a line easier; and in class groupings,facilitating the comparison of sections grouped in the same class(see Fig.4).Also,original MTN25 sheets have been examined in order to understand the geograph-ical context of each line.In any case,we have realised that this task of classi?cation is not easy.Established classes are pre-sented in Table5.Each section of the sample belongs to one of these classes and this information is part of the expected out-put data for the BANN training.Fig.4show the classi?cation of the sections set.
1598F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–1609
Table2
Quantitative data:selected measures
Variable Name(dimension)Comentaries/information contribution References
LB Total length and baseline length ratio(di-mensionless)Relates the length of the line to a straight
line length between the start and the?nish. Enriches sinuosity information
–
l m Mean of the bend length(length)Shows the bend size.Thus contributes density
information on the direction change of the line.
Therefore enriches the sinuosity information
Plazanet[23,33,34]
b cv Coef?cient of variance of bend baseline
length(dimensionless)A homogeneity measure,which shows the dis-
persion of the direction change density
Plazanet[23,33,34]
lb me Median of the bend length and baseline length ratio(dimensionless)Parametrizes the bend shape,and so enriches
the sinuosity information
Plazanet[23,33,34],Plazanet et al.[29],
Skopeliti and Tsoulos[25]
lb cv Coef?cient of variance of the bend length and baseline length ratio(dimensionless)A homogeneity measure,which shows the dis-
persion of the ratio of the bends and baseline
length
Plazanet[23,33,34]
sb cv Coef?cient of variance of the bend area and the squared baseline length ratio(dimension-
less)This homogeneity measure indicates the dis-persion of the ratio between the area,closed
by the line and the baseline,and the squared baseline length
–
m Mean of the bend angularity(angle)Contributes to the angularity information of
the line microcurves,thus enriching the sinu-
osity information McMaster[57],Jasinski[18],Bernhardt [59],Skopeliti and Tsoulos[25]
a cv Coef?cient of variance of the bend angularity
(dimensionless)Homogeneity measure,shows the dispersion
of the bend angularity
Jasinski[18]
c cv Coef?cient of variance of the ben
d curvature
(dimensionless)Homogeneity measure,shows the dispersion
of the bend curvature
–
Table3
Qualitative data:road categories
Category Name Included road networks
1Motorways State network(motorways)
Andalusian basic network
(motorways)
21st order conventionals State network(conventional)
Andalusian basic network
(conventional)
32nd order conventionals Andalusian regional network 43rd order conventionals Andalusian complementary
network
Jaén provincial network
5Others No one.Tracks are included
3.5.BANN design and training
A three layer BANN has been used.The input layer size depends on the data considered to enrich every section,and the output layer size depends on the classes which have been identi?ed.Input layer is integrated by1unit for each measure selected with the PCA(9units,quantitative data,Table2), plus1unit for each category of road(5units,qualitative data, Table3),so14units have been considered.Output layer is integrated by1unit for each class to be recognized,so5units (Table5)have been considered.Only one hidden layer has been used,because there is no reason to expect problems in the BANN learning.The size of the hidden layer is not known at?rst,and several sizes should be tested.Preliminary results Table4
Classes established in previous work
Reference Classes
Plazanet[33]1—Straight
2—Sinuous
3—Strongly sinuous
Plazanet et al.[29]1—Less sinuous
2—Low sinuosity
3—Sinuous
4—Very sinuous
Skopeliti and Tsoulos[25]1—Very smooth
2—Smooth
3—Sinuous
4—Very sinuous with a strong arc show that1unit size and6unit size should be rejected,so the size of the hidden layer has been modi?ed between2and5units (four structures).Tests with two hidden layers would have been considered if poor results had been found.The learning process has been repeated over each structure with the quantitative and qualitative measures computed for73road sections(input)and the classes assigned from manual classi?cation(output).
73is a small number of cases to be divided into a learning pattern and a validation pattern.So a cross-validation process is applied in order to obtain a sounder result.Cross-validation was proposed by Geisser[60]and makes maximally ef?cient use of the available data.It entails the partitioning of the sample data into subsets.The learning is initially performed with all subsets except one,which is used for validation,that is,to
F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–1609
1599
Fig.4.Classi?cation of the section set.Grouped sections.
Table5
Established classes
Class Characteristics
1Very smooth Bend length and radius:high
Predominant direction:very evident
Usual road networks:State network;Andalusian Basic network
2Smooth Bend length and radius:variable
Predominant direction:very evident
Usual road networks:Andalusian Regional network;Jaén provincial network
3Sinuous,with stable directionality Bend length and radius:small
Predominant direction:evident
Usual road networks:Andalusian Complementary network;Jaén provincial network 4Sinuous,with variable directionality Bend length and radius:small
Predominant direction:not very evident
Usual road networks:Jaén provincial network;tracks
5Very sinuous Bend length and radius:very small
Predominant direction:not very evident
Usual road networks:tracks
check if the learning process is successful or not.This process is repeated with every subset.An example of the application of this technique in cartographic generalization can be found in Mustière[61].
Performing the classi?cation with the ANN,output unit val-ues can be used to estimate the probability of belonging to a https://www.wendangku.net/doc/c35505519.html,ing a simple criterion,the highest value of the?ve output units has been used to automatically assign the class.
1600F .J.Ariza López,J.L.García Balboa /Pattern Recognition 41(2008)1593–
1609
Fig.5.Final structure for the BANN in this work.
Once all 73sections have been automatically classi?ed with each structure,an error matrix has been developed to check results.An error or confusion matrix is usually used to assess classi?cation accuracy (see Ref.[62]).Here columns show the a priori classes,and rows the a posteriori classes assigned by the ANN.Diagonal values represent correctly assigned cases,while the remaining represent errors.For 2,3,4,and 5units in the hidden layer,the percentages of agreement (Pa)are,re-spectively,0.81,0.81,0.77,and 0.77.Pa can be considered as the global probability of a correct classi?cation [2].However,not only is it interesting to take into account the percentage of agreement,it is also valuable to compare the output layer unit values in order to evaluate the consistency of the classi?cation.Therefore we have differentiated strong,moderate and weak classi?cations.A strong classi?cation is one which shows a value close to 1in a unit and close to 0in the remaining units (whether the classi?cation is correct or not).A moderate classi?cation is one which shows a value clearly higher than the rest but where any of the classes have a non zero value,with a minimum difference (not less than,for example,
F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–16091601
0.7)with respect to the highest value.A weak value is set in the rest of the cases.It is also valuable to determine if there is interference between the classes when two or more units show similar values(for example,a difference below0.5).In order to select one of the structures presented,several criteria can be taken into account:
?BANN classi?cation should be as strong as possible,with few interferences.
?Correct classi?cations should be maximized and incorrect ones minimized.
?It is always preferable to reduce the quantity of units,in order to reduce the processing tasks in a software simulation[63]. Results indicate that the three hidden units BANN shows char-acteristics with a balance between the maximization of the cor-rect classi?cations and the minimization of the incorrect ones; the presence of interferences is not too high,and the quantity of neural links is more reduced than the4or5units structures (the BANN is more simple).So the three hidden units BANN is selected,with the?nal structure shown in Fig.5.
The?nal BANN de?nition can be any of the eight training processes performed over the three hidden units BANN in the process of cross-validation.Another use of the cross-validation processes is the selection of a subset of the input data.A subset with all the relevant data is quali?ed as good;a subset which exclusively contains the relevant data is quali?ed as the best [64].In this work one of the eight trainings is to be chosen as the de?nitive one.Con?icting cases(sections),those which have not been well classi?ed,are relevant data for the training and should be part of the training pattern.The validation pattern should include cases without confusion problems.This proce-dure,and a reduced error in the validation pattern,guarantees a high generalization capacity of the BANN.
Choosing the best of the eight training processes,the BANN is de?ned by a set of parameters:a threshold value for each unit and a weight value for each link between units(see Ref.[15]).Although they are not directly understandable for us,they mean the formalization of cartographic knowledge that allows the classi?cation of every road line.
4.Application of the ANN over a moving window for line segmentation
In the previous section a BANN has been formalized for road line classi?cation.This BANN is able to classify any road or road section of the MTN25.It is obvious that the classi?cation result is better if a homogeneous section is considered than in the case of a non homogeneous road.So before a classi?cation process of a set of lines,a segmentation process should be performed.However it can be thought that a tool for section classi?cation could be used to perform a segmentation task.Our proposal starts from this hypothesis:if segmentation is achieved by searching for changes in sinuosity,complexity,etc.,then it is really a search for different classes of our BANN output.
A simple way to achieve this is to segment a road line into several pieces of the same length and to classify them with the BANN.If two consecutive pieces belong to the same class, they belong to the same section;otherwise a section change is being detected.Nevertheless this idea constrains the section detection to a subset of points of the road line,this subset being formed by the extremes of the pieces classi?ed by the BANN.
A solution could be the reduction of the length of the pieces, but if the length is much lesser than the length of the sections used for the BANN training,results could be inappropriate. An improvement of this proposal of segmentation with the BANN is to relax the discretization of the potential points of section change,while guaranteeing that the length of the pieces is enough for the BANN classi?cation.This is possible if the BANN successively classi?es pieces derived with a moving window which is moved along the line with an increment of a certain length.As an example,if the length L of the piece(or length of the moving window)is established at1000m and the length l of the increment at200m,the?rst piece to extract for the BANN classi?cation is that from0to1000m in the road line,the following is that from200to1200m,and so on(see diagram of Fig.6).With l Continuing with this example,each piece of200m(which from now on we will also term“increment”)is classi?ed?ve times(L/l times).The mode of these?ve classes should indi-cate the?nal class of this increment.This process also makes the classi?cation sturdier.In Fig.6,increment5is classi?ed successively as class1,1,1,2,2;and?nally the mode is com-puted to assign the class1to this increment. In order to clarify the whole segmentation process of a line, we can summarize it in the following steps: (1)Select a value for L,length of the moving window along the road line,and l,length of the increment along the road line to move the moving window.L must be a multiple of l.Divide the road line into consecutive increments of length l. (2)Fix the moving window at the beginning of the line,and extract a piece of road line of length L composed of the ?rst L/l increments. (3)Characterize this piece with the quantitative and qualitative selected measures.Classify this piece with the BANN using these measures. (4)Store the class obtained from the BANN for each of the increments that form the road piece. (5)Move the moving window one increment,and extract a new piece of road line with L/l increments. (6)Repeat steps3–6until the end of the line is reached. (7)Compute the mode value of the class in each of the increments. (8)Detect the sections of the line,which are indicated by a change in the mode value of two consecutive increments. As can be seen,the moving window process is similar to a convolution,since the class of each increment comes from a central tendency measure from the classi?cation of pieces in which the increment is included. If there is no value for the mode of an increment(for example, if there are5values of one class and5values of another class), 1602F .J.Ariza López,J.L.García Balboa /Pattern Recognition 41(2008)1593– 1609 Fig.6.Diagram of the segmentation process with the moving window. we propose to operate in the following way: (a)Take the mode values of the previous and the subsequent increment (mode prev and mode subs )(b)If mode prev =mode subs ,then this value is assigned to the increment. (c)If mode prev =mode subs ,then the middle point of the in-crement is considered.Value of mode prev is assigned to F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–16091603 the?rst half of the increment,and value of mode subs is assigned to the second half. The method is improved if a minimum length for a section is established.In the case that a section length is less than the threshold,an operation similar to that explained for the mode value should be performed.But in this case the piece should be de?ned by those increments which form the section. 5.Results The proposed segmentation procedure has been applied to each road line of the sample.Visual analysis,maintaining the same criteria used in the semiautomatic segmentation or in the de?nition of classes,has been applied in this stage.The goal is to?nd values of the two parameters of the segmentation process that guarantee an automation of the segmentation of road lines from MTN25;parameters should be?xed in generalization in order to keep the use of algorithms as generic as possible[41]. As an evaluation of the results,a set of experts of different national mapping agencies and universities have assessed the segmentation of the sample of road lines with the proposed parameters. 5.1.Tuning of parameters and segmentation of the sample of road lines L,length of the moving window,and l,length of the incre-ment,are the two parameters of this segmentation methodol-ogy.l should be small enough to minimize its in?uence in the segmentation process,but not so small that it slows down the computation tasks.We have tested l from small values such as25m to large values like500m.Substantial differences are noted between25and500m,both in computation time and in the consequent segmentation.Values of200or250m cause satisfactory results in practically all the samples of road lines, with results very similar to those obtained with an l value of 25m.L,which?xes the length of the piece of line to be classi-?ed by the BANN,is the parameter with real importance.The value of L is related to the length of the sections which have been used to train the BANN.The smallest section length is 711m,and the average length of the set of sections is3578m, with a standard deviation of2272m.Different values have been tested searching for values which offer satisfactory results for most of the road sample,from1000to3500m.Visual analy-sis has shown that a value of about1500m is suitable for most of the lines,but it is advisable to increase it to about3000m for roads of categories1and2(see Table3),that is for lines A-44,N-323,A-316,and A-316A.Segmentation results from the application of these suggested parameters are presented in Fig.7:lines1–4are segmented with an L value of3000m, the remaining being segmented with a value of1500m;the pa-rameter l has been?xed at250m for every line. 5.2.Expert evaluation In the?eld of cartography there are many processes(de-sign,harmonization,generalization,etc.)which require a?nal assessment by humans.In this work an external evaluation of the results is also of great interest,and can even be labelled as essential.Expert estimates[2,p.25]do not allow quanti?-cation but they are a guide,although subjective and dependent on the expert’s knowledge of the theme on which his or her opinion is requested.Unfortunately there does not exist a spe-ci?c and standardized method for assessing the results in carto-graphic generalization,particularly in a segmentation process. In any case it is dif?cult to?x measures and criteria.Neverthe-less there are some proposals,such as the Standard ISO20462 [65]which can contribute with a general guide.This standard is about the estimation of image quality by experimental psy-chophysics methods and establishes general criteria which have been considered in our case.Here we present a summary of the applied methodology and part of the analysis;a sounder ex-planation and a more extended analysis is presented in García Balboa[40]. The main objectives for this expert valuation are the col-lection of information on the valuation of the results of both segmentations(semiautomated for the BANN training and the automated performed by the BANN)of each road line and the adaptation of each one to the different categories of road lines. The choice of the set of experts followed these criteria:they should be experienced in cartography,in a teaching,research or production context;also they should belong to different insti-tutions(universities and national mapping agencies)from dif-ferent countries;the number of experts should be large enough to guarantee that each line is assessed by several of them.The ?nal number of experts was19,12of them related to teaching, 14to research,and7to map production(an expert can perform more than one type of activity).This has allowed each line to be evaluated by almost four experts.With the assessment of each expert we obtain:an alternative segmentation of the road line,suggested by the expert;a quantitative valuation of each segmentation(semiautomated and automated);and a list of problems which have been detected in each segmentation. The design of the test is also an important aspect to be taken into account.A good design has to assure that the expert un-derstands the objectives of the evaluation,the tasks to be per-formed and the criteria to be taken into account.In this work the evaluation process was ordered in three consecutive phases: (a)Observation of the linear element.This is the?rst contact with the element under analysis.The expert becomes aware of the geometry of the line,noting the changes in sinuos-ity and directionality.The original line is presented to the expert on a sheet with no other information. (b)Manual segmentation by the expert.The expert suggests a proposal of segmentation according to the criteria indicated. This phase can be simultaneous to the previous and should be performed in the same sheet as in the previous phase. (c)Valuation of the presented segmentations.Once the expert knows the linear element and has proposed a segmentation of the road line,he or she is in an optimum situation to value other segmentations and to indicate problems.So now both segmentations,semiautomated and automated, are presented.It is important to notice that the expert does 1604F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–1609 Line 1: A-44 L = 3000 m; l = 250 m Line 4: A-316 L = 3000 m; l = 250 m Line 7: A-324 L = 1500 m; l = 250 m Line 2: N-323 L = 3000 m; l = 250 m Line 3: A-316A L = 3000 m; l = 250 m Line 5: A-311 L = 1500 m; l = 250 m Line 6: A-320 L = 1500 m; l = 250 m Line 8: A-1102 L = 1500 m; l = 250 m Line 9: JV-2222 L = 1500 m; l = 250 m Line 10: JV-2223 L = 1500 m; l = 250 m Line 11: JV-2224 L = 1500 m; l = 250 m Line 12: JV-2225 L = 1500 m; l = 250 m Fig.7.Segmentation of the sample of road lines with the suggested parameters.Relative size of lines can be seen in Fig.1.Nomenclature and the value of the parameters L and l are shown for each road line. not know which segmentation is the semiautomated or the automated one,in order not to be conditioned.To make this valuation work easier,an answer table is included(Table6). It is obvious that it is critical that the set of experts take into account the same criteria of sinuosity and directionality that we have used throughout the work.Fig.8is designed to in- crease the homogeneity of these criteria.This?gure is part of the instructions sheet which speci?es each of the tasks to be performed.A presentation letter is also included,which helps the expert to acquire a global perception of the research work,the objectives pursued and the bene?ts of the work. F .J.Ariza López,J.L.García Balboa /Pattern Recognition 41(2008)1593–16091605 Line 22: P-CerroSantin L = 1500 m; l = 250 m Line 13: JV-2226L = 1500 m; l = 250 m Line 16: JV-3242L = 1500 m; l = 250 m Line 23: P-Pegalajar-Central L = 1500 m; l = 250 m Line 24: P-SierraPe?aAguila L = 1500 m; l = 250 m Line 14: JV-3012L = 1500 m; l = 250 m Line 15: JV-3241L = 1500 m; l = 250 m Line 17: JP-2332L = 1500 m; l = 250 m Line 18: P-Camino Ancho L = 1500 m; l = 250 m Line 19: P-CaminoAzadillas L = 1500 m; l = 250 m Line 20: P-CerroAlmaden L = 1500 m; l = 250 m Line 21: P-CerroJabalcuz L = 1500 m; l = 250 m Fig.7.(continued ). Nevertheless four experts were eliminated during the analysis;they may have not applied the same criteria,or not understood the objective of the proposed segmentation,since their valua-tion is noisy in relation with the remaining experts. In Table 7we show a summary of the results,the mean of the valuations is presented for each road line,both for the semiautomated and the automated methodology. From Tables 7and 8,some conclusions of the results of the expert evaluation are: ?The BANN has been trained with a set of sections from a semiautomated segmentation which has been well eval-uated.The mean value is 3.8points in a range from 1to 5. 1606F .J.Ariza López,J.L.García Balboa /Pattern Recognition 41(2008)1593–1609 Table 6 Answer table for the expert valuation of the semiautomated segmentation (a)and the automated segmentation (b)of a road line CASE Mark with an “x”Detected problems/observations (a) 1—Not at all satisfactory Excessive number of sections 2—Not very satisfactory Insuf?cient number of sections 3—Satisfactory There are changes between sections in incorrect positions 4—Quite satisfactory There are sections which are too large 5—Very satisfactory There are sections which are too short Observation 1:—————————–Observation 2:—————————– (b) 1—Not at all satisfactory Excessive number of sections 2—Not very satisfactory Insuf?cient number of sections 3—Satisfactory There are changes between sections in incorrect positions 4—Quite satisfactory There are sections which are too large 5—Very satisfactory There are sections which are too short Observation 1:—————————–Observation 2: —————————– Fig.8.Guide ?gure for the expert evaluation.Example of segmentation attending to sinuosity and directionality changes. ?The automated segmentation by the BANN has been valu-ated with a mean value of 3.0in the range from 1to 5.?The semiautomated segmentation is preferred to the auto-mated in almost all the lines.But there are four exceptions:JV-2226,P-CerroAlmaden and P-CerroJabalcuz. ?Some road lines have a tendency to be well valuated (e.g.A-324,JV-2225)and others to be badly valuated (e.g.P-CerroAlmaden,P-CerroSantin). ?Regarding the category of the road lines,semiautomated and automated techniques show a different behaviour.In the semiautomated case,the valuation is higher for cate-gories 2and 3.In the automated case all categories receive a similar value except category 3which receives a higher valuation. 6.Discussion The methodology developed for automated road line seg-mentation with a BANN should be able to detect changes in sinuosity and/or directionality,in order to detect the different sections along the line.The sample of lines used has not been chosen searching for lines with clear changes that could make any segmentation easier.So the sample is heterogeneous and in some lines the sections to be detected could be more or less evident.In Fig.7we can see,as expected,that it is easy for the BANN to obtain a good segmentation if a line shows clear changes in sinuosity and/or directionality;that is the case of lines 2,4,13,14,15,17,21,or 24.On the contrary,if a line is complex and the changes are not easy to detect,the F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–16091607 Table7 Mean valuation of each road line segmentation(expert assessment) Road line Semiautomated Automated Difference Line1:A-44 3.0 2.3?0.8 Line2:N-323 4.5 2.5?2.0 Line3:A-316A 3.7 3.3?0.3 Line4:A-316 4.0 3.0?1.0 Line5:A-311 4.0 4.00.0 Line6:A-320 4.7 3.0?1.7 Line7:A-324 4.4 3.8?0.6 Line8:A-1102 3.3 2.7?0.7 Line9:JV-2222 4.5 3.0?1.5 Line10:JV-2223 3.7 2.3?1.3 Line11:JV-2224 3.0 2.0?1.0 Line12:JV-2225 4.0 3.5?0.5 Line13:JV-2226 3.3 3.80.5 Line14:JV-3012 4.5 3.3?1.3 Line15:JV-3241 4.5 3.0?1.5 Line16:JV-3242 3.7 2.3?1.3 Line17:JP-2332 4.0 3.5?0.5 Line18:P-CaminoAncho 4.0 4.00.0 Line19:P-CaminoAzadillas 4.3 1.7?2.7 Line20:P-CerroAlmaden 1.5 2.30.8 Line21:P-CerroJabalcuz 3.5 5.0 1.5 Line22:P-CerroSantin 3.0 2.0?1.0 Line23:P-Pegalajar-Central 4.3 3.3?1.0 Line24:P-SierraPe?aáguila 3.3 3.0?0.3 Mean value 3.8 3.0?0.8 Table8 Mean valuation of each road category(expert assessment) Category Name Semiautomated Automated Difference 1Motorways 3.3 2.8?0.5 21st order conventionals 4.3 2.8?1.5 32nd order conventionals 4.3 3.6?0.8 43rd order conventionals 3.8 2.9?0.9 5Others 3.4 3.0?0.4 segmentation is uncertain and could be adequate or not,as can occur with a manual segmentation by an experienced cartogra-pher;this is the case of lines20or22.Also,over-segmentation was found in lines6,8,or10.If a line is homogeneous enough, there are no sections to detect,which is the case of lines5 and23. Results can be compared with the semiautomated segmen-tation by means of effective areas that have been used for the BANN training.But this comparison is conditioned by the ob-jective of both segmentations.In the semiautomated technique the parameters are tuned by the cartographer for each road line; in this case the objective is to?nd the best segmentation of each road line in order to obtain a suitable population of ho-mogeneous sections for the BANN training.In the BANN seg-mentation procedure a general value for parameter L has been tuned because the objective is the automation of the whole pro-cess.A value of L for each road line could have been tuned, but this would not have allowed the desired automation. For this reason some results could be appreciated as better in the semiautomated case,since the tuning is individual for each line.So the semiautomated segmentation can be considered as a reference to evaluate the success of the BANN automated segmentation.This is con?rmed by the expert evaluation,with a mean valuation of3.8in the range1–5for the semiautomated segmentation,and a valuation of3.0in the BANN automated procedure.This decrease of0.8points is the“cost”of the au-tomation of the segmentation procedure. The valuation achieved by the automated segmentation should be considered as a good result if we note the dif?culty that the expert assessment entails.The choice of the more suitable number of sections,or the best location of the points which mark the section change,are not easy operations,even for an expert in map generalization.Therefore it is dif?cult to obtain a total agreement in the valuation from the experts and in the same way it is dif?cult that the expert agrees with the automated segmentation by the BANN. Results of the expert assessment can be analysed taking into account the different categories of roads.It can be appreci-ated that the cost of the automation(column of differences in Table8)is lower for categories1and5(?0.5and?0.4,respec-tively),medium for categories3and4(?0.8and?0.9)and higher for category2(?1.5).This means that is more or less easy for the BANN to automate the segmentation,depending on the category of the road line. As has been said,the automation of the segmentation starts from the tuning of the parameter to?nd a general value more or less suitable for the majority of roads.A general value im-plies that is probably not the best value for each line.So an improvement of the exposed segmentation methodology is the automation of selection of the parameter L by another BANN, which should be trained for this purpose. Our methodology is simple but effective.It is supported by three key elements:a tool for line classi?cation,a moving win-dow to apply the tool along the line,and an analysis of the frequencies(here the mode value)of the classes to detect the sections.In this work a trained BANN has been used as the classifying tool,but any other classifying tool,like an expert system or a cluster analysis,can be applied in a similar or other context. It is clear that in cartographic generalization the future de-velopment requires the formalization of knowledge.Nowadays computers allow us to face this challenge and this work is an example of progress in the automation of line generalization. Results have demonstrated that a BANN developed for road line classi?cation(the formalized knowledge)can be used for a segmentation purpose.The ability of the BANN to recognize different classes allows the detection of different sections with different properties using a moving window. The BANN,as is well known,is a powerful tool that learns from reality(in this case for classi?cation of road lines)by means of a set of examples chosen by a human expert.But it packs the knowledge acquired in a“black box”and it is dif?cult to translate what the BANN has learned to a language under-standable for a human.Optimally,this should be possible.As a starting point we could analyse the sensibility of the BANN 1608F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–1609 to the inputs,in order to?nd the most important measures in the classi?cation process.An important result of this work,de-spite the dif?culties involved in translating arti?cial knowledge into human knowledge,is the con?rmation that this“arti?cial”knowledge can be applied to a speci?c task,emulating and to an extent supplanting the human procedure. 7.Conclusions Segmentation is considered essential to improving the re-sults of automated line generalization,since some algorithms and parameter values are more suitable for certain line types.In this work we have proposed a methodology using arti?cial in-telligence,a backpropagation arti?cial neural network(BANN) over a moving window along the line,for this task.This is a novel application of AANs in the?eld of map generalization. The hypothesis is that a generalization-oriented BANN which is able to classify a line according to sinuosity and direction-ality is also able to detect changes along the line and therefore perform a generalization-oriented segmentation. A summary of the development of the BANN,presented in García Balboa and Ariza[15]has been included.Next the novel methodology for line segmentation has been presented. Our proposal uses a moving window along the line,with the BANN operating inside the window.Values of the parameters are suggested for an automated solution of the road lines seg-mentation from a1:25k scale map. The segmentation of a sample of roads with the suggested parameters and a semiautomated alternative as a reference have been evaluated through a questionnaire by a set of experts from universities and national mapping agencies.The results of this assessment indicate that the semiautomated option is preferred for most,but not all,of the road lines.But the automated seg-mentation works well enough,since it receives an intermediate valuation for any category of roads.This means that the fun-damentals of this automated methodology,which is an appli-cation of a formalization of cartographic knowledge,is valid for the segmentation task for line generalization.We think that such a tool for line segmentation will be of value for the study of the performance of line algorithms over detected sections and classes when deriving rules for an automatic generaliza-tion decision-making procedure based on the characteristics of a line section. Acknowledgment This work has been partially funded by the National Ministry of Sciences and Technology under Grant No.BIA2003-02234. References [1]A.Ruas,A method for building displacement in automated map generalisation,Int.J.Geogr.Inf.Sci.12(1998)789–803. [2]F.J.Ariza,Calidad en la Producción Cartográ?ca,Ra-Ma,Madrid,2002. [3]A.Garrido,N.Pérez de la Blanca,M.García-Silvente,Boundary simpli?cation using a multiscale dominant-point detection algorithm, Pattern Recognition31(1998)791–804. [4]J.L.García Balboa,F.J.Ariza,Frequency?ltering of linear features by means of wavelets.A method and an example,Cartographic J.37(2000) 39–49. [5]Z.Li,Y.H.Choi,Topographic map generalization:association of road elimination with thematic attributes,Cartographic J.39(2002)153–166. [6]P.M.van der Poorten,C.B.Jones,Characterisation and generalisation of cartographic lines using Delaunay triangulation,Int.J.Geogr.Inf.Sci. 16(2002)773–794. [7]E.Saux,B-spline functions and wavelets for cartographic line generalization,Cartography Geogr.Inf.Sci.30(2003)33–50. [8]D.Burghardt,Controlled line smoothing by snakes,GeoInformatica9 (2005)237–252. [9]A.Kolesnikov,P.Fr?nti,Data reduction of large vector graphics,Pattern Recognition38(2005)381–394. [10]L.Kulik,M.Duckham,M.Egenhofer,Ontology-driven map generalization,J.Visual Languages Comput.16(2005)245–267. [11]S.Mustière,Cartographic generalization of roads in a local and adaptive approach:a knowledge acquisition problem,Int.J.Geogr.Inf.Sci.19 (2005)937–955. [12]W.Mackaness,M.Steven,An algorithm for localised contour removal over steep terrain,Cartographic J.43(2006)144–156. [13]C.K.Cheung,W.Z.Shi,Positional error modeling for line simpli?cation based on automated shape similarity analysis in GIS,Comput.Geosci. 32(2006)462–475. [14]W.Z.Shi,C.K.Cheung,Performance evaluation of line simpli?cation algorithms for vector generalization,Cartographic J.43(2006)27–44. [15]J.L.García Balboa,F.J.Ariza,2007.Generalization-oriented road line classi?cation by means of an arti?cial neural network,GeoInformatica, doi:10.1007/s10707-007-0026-z. [16]Z.Li,Digital map generalization at the age of enlightenment:a review of the?rst forty years,Cartographic J.44(2007)80–93. [17]Z.Li,Algorithmic Foundation of Multi-Scale Spatial Representation, CRC Press,Boca Raton,2007. [18]M.J.Jasinski,The comparison of complexity measures for cartographic lines,Technical Report90-1,National Center for Geographic Information and Analysis,Buffalo,New York,1990. [19]B.P.Butten?eld,A rule for describing line feature geometry,in: B.P.Butten?eld,R.B.McMaster(Eds.),Map Generalization:Making Rules for Knowledge Representation,Lognman Scienti?c&Technical, Harlow,UK,1991,pp.150–171. [20]G.Dutton,Scale,sinuosity,and point selection in digital line generalization,Cartography Geogr.Inf.Sci.26(1999)33–53. [21]M.Visvalingam,P.J.Williamson,Simpli?cation and generalization of large scale data for roads:a comparison of two?ltering algorithms, Cartography Geogr.Inf.Syst.22(1995)264–275. [22]E.Richardson,W.A.Mackaness,Computational processes for map generalization,Cartography Geogr.Inf.Sci.26(1999)3–5. [23]C.Plazanet,Modelling geometry for linear feature generalisation,in: M.Craglia,H.Coucleis(Eds.),Geographic Information Research: Bridging the Atlantic,Taylor&Francis,London,1997,pp.264–279. [24]J.C.Müller,Fractal dimension and consistencies in cartographic line representations,Cartographic J.23(1986)123–130. [25]A.Skopeliti,L.Tsoulos,On the parametric description of the shape of the cartographic line,Cartographica36(1999)53–65. [26]C.Plazanet,J.G.Affholder,E.Fritsch,The importance of geometric modeling in linear feature generalization,Cartography Geogr.Inf.Syst. 22(1995)291–305. [27]M.Visvalingam,J.D.Whyatt,Line generalization by repeated elimination of points,Cartographic J.30(1993)46–51. [28]J.A.García,J.Fdez-Valdivia,Boundary simpli?cation in cartography preserving the characteristics of the shape features,Comput.Geosci.20 (1994)349–368. [29]C.Plazanet,N.Bigolin,A.Ruas,Experiments with learning techniques for spatial model enrichment and line generalization,Geoinformatica2 (1998)315–333. [30]X.Barillot,C.Plazanet,Analyse des Formes des Routes,in:A.Ruas (Dir.),Généralisation et représentation multiple,Lavoisier,Paris,2002, pp.203–223. F.J.Ariza López,J.L.García Balboa/Pattern Recognition41(2008)1593–16091609 [31]F.Mokhtarian,A.K.Mackworth,Scale-based description and recognition of planar curves and two-dimensional shapes,IEEE Trans.Pattern Anal. Mach.Intell.8(1986)34–43. [32]F.Mokhtarian, A.K.Mackworth,A theory of multi-scale,curvature based shape representation for planar curves,IEEE Trans.Pattern Anal. Mach.Intell.14(1992)789–805. [33]C.Plazanet,Measurements,characterisation and classi?cation for automated linear features generalisation,in:Proceedings AutoCarto12, vol.4,Charlotte,NC,1995,pp.59–68. [34]C.Plazanet,Enrichissement des bases de données geographiques:analyse de la géométrie des objets lineaires pour la généralisation cartographique (application aux routes),Ph.D.Thesis,Universitéde Marne la Vallée, France,1996. [35]D.Burghardt,Smoothing of line objects with optimization techniques, Abstract,ISPRS/ICA Workshop on Multi-Scale Representations of Spatial Data,Ottawa,2002. [36]T.Werschlein,R.Weibel,Use of neural networks in line generalization, in:Proceedings EGIS’94,Paris,1994,pp.76–85. [37]M.K.Allouche,B.Moulin,Una approcheàbase de cartes de Kohonen pour la généralisation cartographique de zones de points de forte densité, in A.Ruas(Dir.),Généralisation et représentation multiple,Lavoisier, Paris,2002,pp.337–352. [38]M.K.Allouche,B.Moulin,Amalgamation in cartographic generalization using Kohonen’s feature nets,Int.J.Geogr.Inf.Sci.19(2005)957–973. [39]M.Sester,Optimization approaches for generalization and data abstraction,Int.J.Geogr.Inf.Sci.19(2005)871–897. [40]J.L.García Balboa,Automatización de los procesos de segmentación y clasi?cación de vías de comunicación en generalización cartográ?ca, Ph.D.Thesis,Universidad de Jaén,Spain,2006.Available online at: http://coello.ujaen.es/investigacion/web_giic . [41]Eurogeographics,Generalisation processes.A benchmark study of the Expert group on Quality,Eurogeographics,Expert Group on Quality. Available online at: https://www.wendangku.net/doc/c35505519.html,/eng/05_quality_ reports.asp ,2005. [42]E.Spiess,U.Baumgartner,S.Arn, C.Vez,Map Graphics and Generalisation,Swiss Society of Cartography,Wabern,2005. [43]C.Barber,R.Cromley,R.Andrle,Evaluating alternative line simpli?cation strategies for multiple representations,Cartography Geogr. Inf.Syst.22(1995)276–290. [44]B.Zhan,B.P.Butten?eld,Multi-scale representation of a digital line, Cartography Geogr.Inf.Syst.23(1996)206–228. [45]F.Lecordix, C.Plazanet,https://www.wendangku.net/doc/c35505519.html,grange,A platform for research in generalization:application to caricature,GeoInformatica1(1997) 161–182. [46]Z.Wang,J.C.Müller,Line generalization based on analysis of shape characteristics,Cartography Geogr.Inf.Syst.25(1998)3–15. [47]H.Veregin,Line simpli?cation,geometric distortion,and positional error, Cartographica36(1999)25–39. [48]Z.Li,H.Sui,An integrated technique for automated generalization of contour maps,Cartographic J.37(2000)29–37. [49]P.J.Werbos,Beyond regression:new tools for prediction and analysis in the behavioural sciences,Ph.D.Thesis,Harvard University,1974.[50]P.J.Werbos,The Roots of Backpropagation,Wiley,New York,1994. [51]D.E.Rumelhart,G.E.Hinton,R.J.Williams,Learning representations by back-propagating errors,Nature323(1986)533–536. [52]F.Rosenblatt,The perceptron:a probabilistic model for information storage and organization in the brain,Psychol.Rev.65(1958)386–408. [53]D.E.Rumelhart,G.E.Hinton,R.J.Williams,Learning internal representations by error propagation,in:D.E.Rumelhart,J.L.McClelland (Eds.),Parallel Distributed Processing:Explorations in the Microstructure of Cognition,MIT Press,Cambridge,MA,1986,pp.318–362. [54]F.J.Ariza,J.L.García Balboa,Segmentación de elementos lineales mediante?ltrado de Douglas–Peucker aplicado a lasáreas efectivas de Visvalingam–Whyatt,Mapping97(2004)52–64.Available online at: https://www.wendangku.net/doc/c35505519.html,/plantilla-ante.asp?id_articulo=768 . [55]R.B.McMaster,Knowledge acquisition for cartographic generalization: experimental methods,in:J.C.Müller,https://www.wendangku.net/doc/c35505519.html,grange,R.Weibel(Eds.), Gis and Generalization,Taylor&Francis,London,1995. [56]AGENT,Selection of basic measures,Report D C1,Project AGENT (ESPRIT/LTR/24939),1999. [57]R.B.McMaster,A statistical analysis of mathematical measures for linear simpli?cation,Am.Cartographer13(1986)103–117. [58]S.Mustière,Mesures de la qualitéde la généralisation du linéaire, Rapport de Stage,DESS de Cartographie,UniversitéParis I,France, 1995. [59]M.C.Bernhardt,Quantitative characterization of cartographic lines for generalization,Report No.425,Department of Geodetic Science and Surveying,Ohio State University,1992. [60]S.Geisser,The predictive sample reuse method with applications, J.Am.Stat.Assoc.70(1975)320–328. [61]S.Mustière,Cartographic generalization of roads in a local and adaptative approach:a knowledge acquisition problem,Int.J.Geogr.Inf.Sci.19 (2006)937–955. [62]R.Congalton,K.Green,Assessing the Accuracy of Remotely Sensed Data:Principles and Practices,Lewis Publishers,Boca Raton,FL,1998. [63]J.R.Hilera,V.J.Martínez,Redes Neuronales Arti?ciales,Fundamentos, modelos y aplicaciones,Madrid,Ra-Ma,1995. [64]W.S.Sarle(Ed.),Neural Network FAQ.Available online at: ftp://ftp. https://www.wendangku.net/doc/c35505519.html,/pub/neural/FAQ.html ,1997. [65]ISO,International Standard ISO20462:2005,Photography— psychophysical experimental methods for estimating image quality, International Standardization Organization,2005. [66]Instituto Geográ?co Nacional,Mancha Real,Mapa Topográ?co Nacional de Espa?a1:25.000,Sheet947-II,Instituto Geográ?co Nacional,Madrid, 1996. [67]Instituto Geográ?co Nacional,Los Villares,Mapa Topográ?co Nacional de Espa?a1:25.000,Sheet947-III,Instituto Geográ?co Nacional, Madrid,1996. [68]Instituto Geográ?co Nacional,Cambil,Mapa Topográ?co Nacional de Espa?a1:25.000,Sheet947-IV,Instituto Geográ?co Nacional,Madrid, 1996. [69]Instituto Geográ?co Nacional,Jaén,Mapa Topográ?co Nacional de Espa?a1:25.000,Sheet947-I,Instituto Geográ?co Nacional,Madrid, 1997. About the Author—FRANCISCO JA VIER ARIZA LóPEZ is currently chair of Cartography at Jaén University(Spain).Dr.Ariza is the head of the“Ingeniería Cartográ?ca”Research Group,with research interests in map production(especially in the scopes of quality and generalization),GIS,remote sensing,and cadastre.He has over10books,20articles and more than80conference papers related on these topics.His research activity is also much compromised with new researchers and has been the advisor of6Ph.D.theses and supervisor of over40dissertations and18scholarships.He has participated in a large number of research projects,European and Spanish,and in R&I contracts with governments and private companies.He is the member of the148Technical Committee of AENOR(Spanish Association for Standardization)“Información Geográ?ca Digital”(Digital Geographic Information). About the Author—JOSéLUIS GARCíA BALBOA is currently a professor in the Department of Cartographic,Geodetic,and Photogrammetric Engineering at Jaén University,Spain.He received his engineering degree in Surveying and in Geodesy and Cartography from Jaén University,in1997and1998,respectively, both prize-winning,and also is the recipient of the1998Francisco Coello National Award for his end of degree project.He received his Ph.D.degree from University of Jaén in2006for a dissertation about road line segmentation and classi?cation for cartographic generalization.Dr.García Balboa is member of the“Ingeniería Cartográ?ca”Research Group and his research interests include cartographic generalization and quality evaluation on map production.He has a number of publications and conference papers on both the topics and he is the co-author of the book“Casos Prácticos de Calidad en la Producción Cartográ?ca”(practical cases about quality on map production).