Keywords: arithmetic teaching, standard algorithm, mental calculation, addition, subtraction, gender difference

We would like

The final version of this paper was published as: Fischer, J.-P., Vilette, B., Joffredo-Lebrun, S., Morellato, M., Le Normand, C., Scheibling-Seve, C., & Richard, J.-F. (2019). Should we continue to teach standard written algorithms for the arithmetical operations? The example of subtraction. Educational Studies in Mathematics,101(1), 105-121. DOI: 10.1007/s10649-019-09884-9

Should we continue to teach standard written algorithms for the arithmetical operations? The example of subtraction Jean-Paul FISCHER*, Bruno VILETTE (a) , Sophie JOFFREDO-LEBRUN (b) , Mireille MORELLATO (c) , Céline LE NORMAND (d) , Calliste SCHEIBLING-SEVE (e) & Jean-François RICHARD (f) 1 Introduction Each proposal of a new curriculum for the primary school raises the question of the need for continuing to teach a standard written algorithm (SWA) for the four classical arithmetical operations: addition, subtraction, multiplication, and division. The question is of particular concern in countries where this teaching is fundamental by its presence in the early grades, as in France where the SWA for addition and subtraction/multiplication are taught in first grade and second grade, respectively.

The changes in society, notably the numerical revolution, challenge the necessity of teaching an exact paper-pencil algorithm for computing each arithmetical operation. The numerous arguments that can be put forward against the teaching of the SWAs are here presented in eight categories, even if these categories can support some interactions (section 1.1). However, there are also some arguments that come in defense of the teaching of these ancestral algorithms (section 1.2).

1.1 Arguments against teaching SWAs 1.1.1 The SWAs harm the number sense The SWAs, except that for division, impose beginning the computation with the smallest units. Therefore the magnitude of the numbers to add, subtract or multiply is masked. The persons engaged in the computation ignore the place value of the digit they manipulate. The consequences of such a practice are well summarized by Kamii and Dominick's (1997 p. 51) claim "that algorithms 'unteach' place value and hinder children's development of number sense".

1.1.2 The use of SWAs may lead to absurd results in arithmetical operations Selter (2001 p. 157) reproduced the written subtraction SWA for 701 -698 from many third or fourth graders who found a result higher than 701 (e.g., 701 -698 = 703; 701 -698 = 1903). In the present research, many second graders found 72 + 37 = 19. Whereas the latter result appears absurd, it may result rather logically from the columnar algorithm: In adding the tens, the students have 7 + 3 = 10 and write the 10 as 1 in the column of the tens.

The SWAs run against the direction of writing

Beginning with the smallest units implies beginning on the right in our culture. In first grade, this seems not well come because teachers emphasize that we read and write from left to right. The reversal of the digits, omnipresent in Kindergarten but not totally fade-out in first grade [START_REF] Fischer | Mirror writing in typically developing children: a first longitudinal study[END_REF], shows that many students are in struggle when the left-right orientation is not respected.

The SWAs negatively influence mental calculation

The premature learning of a SWA suggests and allows a "paper-and-pencil mental analogue" strategy in mental computation. The French national annual assessments show that girls perform better in the written algorithm than boys, but that boys outperform girls in mental computation [START_REF] Chesné | Ce que nous apportent les évaluations nationales sur les connaissances des élèves dans le domaine des nombres et du calcul à l'école primaire[END_REF][START_REF] Fischer | Les différences cognitives entre sexes : une autre approche et d'autres observations[END_REF]. This twofold observation is consistent with a greater use of a paper-and-pencil mental analogue strategy in mental calculation by girls than by boys. Because of their low performance in the written algorithm boys could be less inclined, or even unable to repeat it mentally, whereas the contrary holds for girls. Insofar as this mental analogue strategy repeats the SWA, the observation is also consistent with the findings that girls apply more frequently standardized strategies, while boys prefer various approaches [START_REF] Torbeyns | The use of number-based versus digit-based strategies on multi-digit subtractions: 9-12-year-olds' strategy use profiles and task performances[END_REF]. This interpretation predicts that boys will specifically perform better than girls in mental operations needing carrying, borrowing, bundling or unbundling because these complex transformations concern mainly the written algorithm. Indeed, Chesné and Fischer (2015, Appendix E) report many assessments, at the beginning of third grade and with a free choice of the method of computation, in which the 978 -765 subtraction problem was better solved by girls than boys, whereas the same girls performed lower than the boys on the 45 -27 subtraction problem.

1.1.5 The teaching of SWAs creates a bad didactical contract in problem solving When teachers attach importance to unimportant things, when they convey an erroneous conception of the functioning of mathematics, they implicitly establish a bad didactical contract [START_REF] Brousseau | Didactical contract and the teaching and learning of science[END_REF]. This is often the case in problem solving when the professors ask to present the response of a problem in the "Solution -Operation" format. This format emphasizes the computation of the arithmetical operation, which must be written to be presentable to the teacher, and thereby hides the heart of the problem solving activity, namely finding the operation that must be computed.

The SWAs are not always understandable by typical students

The subtraction SWA-let us write a2a1a0 -b2b1b0 the subtraction of two three-digit numbers-generally taught in second grade in France, needs borrowing or unbundling a higher order (i+1)-unit when bi cannot be taken away from ai. In the latter case the higher order (i+1)-unit is transformed in ten i-units through a sort of writing. Can a typically developing 7-year-old child understand this ingenious sort of writing? Even if the answer would be "yes", it remains that the 1 corresponding to the (i+1)-unit is misplaced in the i-unit column.

This may be particularly troubling for students because teachers repeat at length that when an operation is put down in columns, the i-unit must imperatively be written in the column of the i-units. Other "harmful effects of carrying and borrowing in grades 1-4" can be found in [START_REF] Kamii | The harmful effects of "carrying" and "borrowing" in grades 1-4[END_REF].

Furthermore, the SWA for subtraction directly confronts the students with impossible ab computations, if a < b. Both by facility and because the difference between a and b is the same as that between b and a in the vernacular language, students are then rushed into the error of computing ba rather than ab. This is, for example, supported by Csikos' (2016) finding that 193 is the most frequent erroneous answer in the computation of 701 -694 (15.4%).

The learning of SWAs implies learning through authority

Because of the difficulty of understanding and the impossibility of reinventing the SWAs, the latter must be taught with authority. "If the classroom is governed by the authority of the teacher, children will be encouraged to conform to the teacher's wishes, without separating sociomoral issues from purely intellectual ones", noted Kamii (1994 p. 63).

The use of the standard algorithms in adulthood borders on ridicule in many cases

The premature initial learning of the SWA by the children (as young as 6 years of age for addition) leads to deeply buried memories. Not surprisingly, [START_REF] Dewi | Strategies for written additions in adults[END_REF] found that adult students prefer the columnar strategy taught at school rather than more flexible mental strategies. Such behavior in adult persons borders on ridicule when problem solving is obvious through mental computation, as is the case for many problems in the research by Dewi et al. (e.g.,57 + 99,25 + 25).

1.2 Arguments in defense of teaching SWAs 1.2.1 Students use SWAs more effectively and faster than mental computation Torbeyns andVerschaffel (2013, 2016) submitted two types of additive problems to 4 th grade students in Belgium (Flanders). The MC items were easy to solve with mental computation (e.g., 498 + 263, 963 -499), whereas the SA (standard algorithm) items were not (e.g., 456 + 266, 952 -474). Thus, the SA items evoked computation with the SWA more strongly than the MC items. Not surprisingly, the SA items were better solved through using the SWA than through mental computation (88% vs. 63% correct for the subtractions tested in [START_REF] Torbeyns | Mental computation or standard algorithm? Children's strategy choices on multi-digit subtractions[END_REF]; the first strategy was also faster than the second. However, very surprisingly, the MC items also were better solved through using the SWA than through mental computation (80% vs. 60% correct for the subtractions tested in [START_REF] Torbeyns | Mental computation or standard algorithm? Children's strategy choices on multi-digit subtractions[END_REF]; the first strategy was faster than the second for the MC items also. [START_REF] Dewi | Strategies for written additions in adults[END_REF] not only found that adult students prefer the written algorithm of the addition of two two-digit numbers (see section 1.1.8), but also that this strategy was run faster than other strategies, without detrimental effect on accuracy. However, because there was a majority of female students in the sample by Dewi

Students prefer SWA to mental computation

With the same sample of students as in section 1.2.1, [START_REF] Torbeyns | Mental computation or standard algorithm? Children's strategy choices on multi-digit subtractions[END_REF] also used a choice condition in which students could choose between mental computation and SWA as a function of the item. The students clearly preferred the SWA (79% choices), not only for the SA items (82% choices) as expected, but also for the MC items (77% choices). These choices by the students can be explained with the cognitive and conative attractiveness of the SWA.

SWAs raise cognitive attractiveness

Knowing an algorithm that can be applied to all multi-digit numbers has the advantage of drastically limiting the choice of the students. If they do not retrieve the result of a computation in their declarative memory they immediately know what to do. In analyzing this phenomenon further, one sees that in computing the result with the SWA students identically repeat the same procedure. They have nothing new to learn. On the contrary, in genuine new mathematical learning the children must implement a reflective abstraction [START_REF] Piaget | Recherches sur l'abstraction réfléchissante: 1/L'abstraction des relations logico-arithmétiques[END_REF]. Such new learning unbalances the children's cognitive structures and needs efforts to restore the equilibrium. It is understandable that students-and not only students!-avoid such efforts.

SWAs raise conative attractiveness

A unique mean to calculate the result from a problem is not only cognitively economic but also affectively reassuring. This reassuring character of a unique algorithm or representation is a very general phenomenon. It was experimentally demonstrated with an algorithmic instruction for solving percentage problems on seventh grade students in Midwestern USA [START_REF] Flores | Multiple representation instruction first versus traditional algorithmic instruction first: Impact in middle school mathematics classrooms[END_REF]. The order of teaching this algorithmic instruction with respect to a multiple representation instruction was manipulated. Although the results indicated a very small superiority in abilities to solve percentage problems among the students who received multiple representation first, the students' perception of the algorithmic instruction was more favorable compared to that of the multiple representation instruction. Furthermore, the sole teacher involved in this study indicated that she also experienced difficulty with motivating the multiple representation instruction in the group of students who had received the algorithmic instruction first. This may explain why the premature learning of the SWA hinders the learning of genuine mental computation.

Math anxiety-a feeling of tension, apprehension or fear that interferes with math performance-may be a conative consequence of mathematics learning. [START_REF] Ramirez | On the relationship between math anxiety and math achievement in early elementary school: The role of problem solving strategies[END_REF] work confirms that math anxiety in first and second graders is negatively related to their use of more advanced strategy in the computations 3 + 6, 9 + 8, 13 + 5, and14 + 19. Furthermore, and somewhat ironically, students who have the highest working memory capacity avoid using advanced problem-solving strategies when they are high in math anxiety. This can partially explain why students who spontaneously use the SWA perform better than students who use more advanced strategies, in the current observation as in others (e.g., [START_REF] Torbeyns | Efficient and flexible strategy use on multi-digit sums: a choice/nochoice study[END_REF][START_REF] Csíkos | Strategies and performance in elementary students' three-digit mental addition[END_REF].

Goal of the study

A "battle" of arguments alone cannot solve the question of whether to teach arithmetical algorithms in the first school-years. The lighting of experimental work would be welcome. However, given the complexity and versatility of the question, an experimental approach can only investigate some specific aspects. The particular importance of finding the arithmetical operation to be performed led us to study arithmetical problem solving.

The consequences of teaching or not teaching SWA on the solution procedures used by young students can then provide information to be included in an answer to our general research question about the effectiveness of SWA's teaching.

Method

The ACE program

The ACE (Arithmetic Comprehension at Elementary school) research program is a full arithmetic curriculum that was implemented during the first two years of France's school. In second grade, its efficiency was assessed with a pretest/posttest and control group design in 2015-2016 and 2016-2017. Here, the very similar data from the posttests 2016 and 2017 were merged. The posttest assessed mental computation, arithmetic writing, estimation, and mental arithmetic problem solving. These four arithmetical subdomains gave an arithmetic test score for each student. The posttest also included, at the end, a more complex arithmetic problem. The posttest data allowed then to relate the solving procedure used by the children for this problem not only with their response to the problem but also with their arithmetical level as measured by the arithmetic test (posttest without the problem).

Important for the present discussion, the ACE experimental program does not include the teaching of the SWA for computation. Hence, by comparison of the experimental and control groups, the ACE data are well suited for highlighting some of the consequences of teaching SWAs. The teaching of problem solving encouraged ACE students to examine the situation described in the problem and, if possible, to estimate an approximate result before trying to find the accurate answer.

Participants

The experiment involved 269 second-grade classes, which were divided between the experimental (147 classes) and control (122 classes) groups. Our analyses are based on 4720 students (Mage = 7.95, SD = 0.35), 2619 in the experimental group and 2101 in the control group, with an overall 48.6 % proportion of girls.

We recruited classes in the north, west, southeast, and center of France. Thanks to the support provided by France's Education Ministry, we were able to obtain all necessary administrative authorizations and to recruit a large number of classes. All the classes in the control group followed the French curriculum, which includes quasi-imperatively teaching an algorithm for addition, subtraction, and multiplication at this academic cycle. The algorithm is usually the classical computation in columns (see Fig. 1), which can be performed either through borrowing or unbundling for the subtraction. It is important to indicate that the curriculum at work in the control classes at the time of our tests emphasized the essential role of problem-solving in mathematical activity.

Furthermore, not to favor the experimental group, our test-problem was extracted from the French National assessments (a former version), both in its wording and format of presentation.

The posttest problem

The problem was presented in writing, but nevertheless read aloud by the experimenter. The statement of the problem was as follows (in French): "At recess, Dimitri play marbles. At the beginning of the game, he has 37 marbles. At the end, he has 72 marbles. How much has he won? ". Students were given 5 minutes to solve the problem, using a pencil and an empty 8.5 x 16.5 cm rectangular frame (included in the students' booklet) for research and computation. They should indicate the response on a location outside of this frame.

Students who think that the essential thing in a verbal problem is to find the arithmetic operation-as a result of the emphasis on SWA (which leads to a bad didactical contract)-rush to find the operation. A quick way to find it, which often leads to the correct answer, is to superficially interpret the terms of the problem formulation. In our problem, the verb "won" ("gagner" in French) suggests an addition.

Our problem was selected for its special ability to test this behavior of the students taught with a focus on the SWAs, as is the case in many of the non-experimental classrooms. A more basic formulation of a subtraction problem, using the (conjugated) verb "lose" ("perdre" in French), is unable to test the real understanding. This is because the students who only resort to the verb "lose" for carry out a subtraction will successfully solve the problem (i.e., carry out the correct operation and probably give the correct answer), but possibly on the basis of an incorrect reasoning.

We focused on this question because a lot of research shows that this answer mode, with an arithmetical operation induced by the terms of the problem's formulation (rather than by the understanding of the situation), is the main problematic behavior in arithmetical problem-solving (at least in France; see, for example, [START_REF] Ehrlich | Sémantique et mathématique: Apprendre/Enseigner l'arithmétique simple[END_REF]. Including a problem-item in which the terms of the formulation induce the correct arithmetical operation would blur our comparison between experimental and classic teaching, and make difficult to distinguish between a correct mode of solving and an incorrect one. Thus, our Dimitri-problem was the sole written verbal problem.

Categorization of the problem-solving procedure

The 11 categories of procedure were defined in the aim to study the efficiency of the SWAs. They can be succinctly described as follow (see also

Specific research questions

The data collected allow us to investigate many questions about the SWAs, here identified as the column procedure. A first question results from the observation that children who rush into the algorithmic computation, perhaps through a bad didactical contract (see 1.1.5), often choose a false operation. Furthermore, they cannot correct this initial error because they do not have a sufficient operation sense (see 1.1.2) to predict that the outcome of the problem cannot exceed the greatest number of the difference. Thus, a specific hypothesis is that the column procedure would more lead to the answer 109 (= 72 + 37) than any other procedure.

A second question concerns the effectiveness of the column procedure. This major argument in support of teaching the algorithms (see 1.2.1) can be investigated directly by studying the accuracy of the answers by the children who used that procedure. However, with this way of investigation, a correct computation of the false operation will debatably be categorized as inaccurate. Another mean of investigation is more indirect. It is based on the postulate that the best performers in arithmetic will use the most effective procedure.

The ACE data are particularly interesting for discussing these questions because the answers can often be qualified with the separate analysis of the experimental and control groups. Even if the absence of algorithms teaching in the experimental group does not result in a total absence of the column procedure in this group, it should result in a considerably less use of this procedure. We would then underline that such data allowing the comparison in the same culture of two substantial samples of 7-to 8-year-old students who were submitted, or not submitted to the teaching of SWAs, are rare.

Statistical processing

Because the scale of grading of the posttests 2016 and 2017 slightly differ, the scores of the arithmetic tests were standardized, using the mean and standard deviation of the year of assessment. These z-scores permit to indicate the mean arithmetic achievement of the students in Tables 1 and4, and, in Table 2 to distribute the students in 10 deciles of 472 students each in function of their arithmetic competence.

The subsequent analyses of procedures used by the students will be done at a participants' level.

However, the observations of the students were not independent because there were many students in a class (18.7 students per class in mean). This data structure requires a multilevel analysis in order to avoid the statistical nuisance introduced by the dependency of students clustered in their classroom. As we are mainly interested in the use, or not use of a column algorithm, we defined a binary variable whose outcomes are 1 if the student was categorized in the column or mulcol procedure user, and 0 if not. Then, the data could be modelled with a two-level (level 1: student; level 2: class) logistic regression analysis carried out following the procedure described in Sommet and Morselli (2017), using the R computer statistical language and environment (R Core Team, 2015).

3 Results

A preliminary multilevel logistic regression analysis.

First, a null model with no other variable than the Class as random intercept was run. This null model allowed to quantify the intra-class coefficient (ICC), that is, the proportion of observed variance in the outcome that is attributable to the effect of clustering. The ICC would be equal to one if the same value for the outcome variable would be attributed to all students in a same class (e.g., 1 for all students in the control classes, in which the column algorithm was taught; and 0 in the experimental classes in which the column algorithm was not taught).

The ICC = .46 found indicates that there was substantial intra-class homogeneity in the use of a column algorithm, justifying this preliminary analysis, but also that this homogeneity is not sufficient for limiting the analysis to teachers' level.

Departing from the null model, we included Gender (level-1 variable) and Group (level-2 variable) as fixed effects, which improved significantly the model,  2 (2) = 126.18, p < .001. Then, neither authorizing random slope variation of Gender in the classes, nor adding the interaction between Gender and Group as fixed variable improved significantly the model.

The final model yields a significant fixed effect of Group, z = -9.84, p < .001; the odd-ratio OR = 0.11, 95%CI = [0.07, 0.16], indicates that students in the experimental group are about 9.5 times less likely to use the written column representation than students in the control group. The fixed effect of Gender is also significant, z = -3.71, p < .001; OR = 0.66, 95%CI = [0.52, 0.82], indicates that boys are 1.5 times less likely than girls to use the written column representation.

Accuracy of the answers as a function of the procedure

The effectiveness of a procedure was first assessed by reporting the number of correct answers to the number of uses of this procedure. The resulting percentages and their association with the arithmetic achievement level of the students who used the procedure are unambiguous (see Table 1): Whereas the two multiple proceduresmulcol and muloth-were the most effective they were also mostly used by the high achievement students.

Procedure used as a function of arithmetical ability

Table 2 shows that the procedures are differently distributed in the decile groups,  2 (90) = 408.20, p < .001, Cramer's V = .098. The rank correlations between frequency of a procedure and decile differ considerably. The line, mulcol, and muloth procedures correlate positively, significantly and very strongly with the deciles, whereas the no and other procedures correlate negatively, significantly and very strongly with the deciles. In contrast, the correlation for the column procedure is approximately null. Therefore, the column procedure seems not related to the level of arithmetical ability, whereas line, mulcol, and muloth procedures are increasingly (and the no and other procedures decreasingly) used as the level of ability increases.

Types of response: column procedure versus all the other procedures

Table 3 shows the main types of final responses. The distribution of the students who used the sole column procedure and all the other students in the six types of response differs significantly 2 (5) = 607.04, p < .001, with a substantial effect size, Cramer's V = .359. For the column procedure, the "109" response percentage is strongly higher and the "None" response percentage strongly lower than these percentages for all other procedures together. Besides, the two main contributions to the chi-square statistics come from these "109" and "None" responses. This double observation suggests that a great number of students applied blindly the column procedure.

Comparison for the column procedure: experimental versus control group

Table 4 shows the comparison on three variables of the experimental and control groups for the column procedure. The difference in the uses of the column procedure is not only highly significant, but the  effect size of the group is impressive. Thus, the ACE experimental program reduces considerably the use of the column procedure. One can even wonder why this procedure, which was not taught, was nevertheless used at all in the experimental group. But students may learn the procedure at home, in first grade, or with teachers who taught it in addition to the experimental program (often under parental pressure). The significant higher z-score of the students in the experimental group who used the column procedure suggest that these students love arithmetic and have perhaps practiced the written algorithm at home, for themselves, with possibility to verify the answers on a computer or calculator. (a) The significance p and the effect size of the difference between the two groups were approximated with the chi-square statistic.

(b) The significance p and the generalized effect size (ges) of the groups were obtained through an ANOVA (the square root of ges was used for direct comparability with 

Comparison between genders

Table 5 shows that the distribution of boys and girls in the different categories of procedures differs significantly,  2 (10) = 42.58, p < .001, even if the effect size of gender is small, Cramer's V = 0.095. In addition, we verified that the statistical significance of the chi-square test results mainly from the column data. Indeed, girls used the column procedure more than boys,  2 (1) = 14.02, p < .001, = 0.055. Given the great proportion of unknown procedures it is possible that a preponderant internal procedure escapes our analysis. Students may also have used covertly one of the 9 relevant procedures, therefore invalidating the order of frequency of the procedures. However, the examination of the no procedure shows that it leads to the correct answer only in 13.05% of the students. Furthermore, these students performed below the mean at the arithmetical test (see Table 1) and were rather in the first deciles than in the last deciles (see Table 2). Therefore, a plausible hypothesis is that a majority of the students in the no procedure do not understand the problem.

Another limitation could arise from the statistical analysis mainly performed only at the students' level.

However, the preliminary two-level logistic regression analysis yielded, for the differentiated use of columnar computation in the two groups and in the two genders, convergent results with the analysis at the students' level.

Thus, we can think that the possible statistical nuisance induced by within-class homogeneity does not invalidate the results of our more complete analyses at the students' level.

4.2 Is the column procedure efficient in problem-solving?

Table 1 shows that the multiple procedures mulcol and muloth yielded the greatest percentage of success, 30.77 and 27.75% respectively. In comparison, the isolated column procedure, with 20.24% of successes (101 out of 499) holds only the 7 th position out of 11, behind the multiple procedures and also the line, numer, tree, and unit procedures; it clearly outperformed the no, other and box procedures. This result is difficult to interpret for two reasons. First, in defining efficiency of a procedure by the accuracy of the final response, students who compute correctly the false operation in columns will lead to an underestimation of the effectiveness of the column procedure. However, as argued in section 1.1.5, the teaching of the column procedure often leads to a bad didactical contract. Therefore, the inflation of the "109" response (see section 3.3), which typically results from the correct computation of 72 + 37, brings a negative support to the conceptual aspect of the column procedure.

Second, the procedure is not independent from the students' ability. For example, if gifted students use a certain procedure, this procedure will be effective. However, a procedure that does not lead to the correct answer must be considered as ineffective regardless of the level of ability of the students who used it. Thus, it is not surprising that the procedures no and other are among the three most ineffective procedures. The box procedure-the schematic drawing for combine problems [START_REF] Fuson | Second grader's use of schematic drawings in solve addition and subtraction word problems[END_REF])-was the most ineffective one (only 12.68% successes), and was almost exclusively used in the experimental group. Indeed, the teaching of this procedure is intended to find the correct arithmetic operation and does not provide a method for calculating this operation. Therefore only students who can calculate mentally 72 -37 in addition to correctly placing the numbers in the rectangular diagram can succeed.

The indirect mean to assess the relative efficiency of the procedures consists in looking at the procedures used by the most performing students in the arithmetical test. Table 1 shows that the most performing students, with a 0.462 mean z-score, were in the mulcol procedure. Table 2 is consistent with this finding because the frequency of use of the mulcol procedure increases when the level of arithmetic ability increases.

Among the other procedures, the muloth and line procedures were also more chosen by the students with high performance in the arithmetic test. Therefore, the two ways of determining the most efficient procedure seem converge toward designating the multiple procedures, particularly the mulcol procedure, as the most efficient.

4.3 Other empirical observations on the effectiveness of SWA [START_REF] Kamii | To teach or not to teach algorithms[END_REF] report the results of a computation given in 2 nd , 3 rd and 4 th grade classes in which the conventional algorithm was, or was not taught. The children were asked to solve the horizontally written problem 6 + 53 + 185 (in fact, 7 + 52 + 186 in grade 2) without using any pencil or paper during individual interview at the end of the school year. The authors found that those who had not been taught any algorithms produced much more reasonable errors than those who were taught a SWA. They concluded that "the time has come to stop teaching the algorithms" (p. 60, see also section 1.1.1). However, the comparison seems unfair because the students who were taught the algorithm could not use it, at least in its normal paper and pencil form, whereas the compared students could use their normal procedure of computation. Thus, no clear conclusion can be drawn from this data. [START_REF] Csíkos | Strategies and performance in elementary students' three-digit mental addition[END_REF] studied the relationship between students' performance in mental calculation and the strategies they use in a sample of 78 Hungarian fourth graders who solved three-digit addition problems (e.g., 342 + 235, 498 + 256) and two subtraction problems (e.g., 701 -694). Because the written algorithm is only introduced in the first half of grade 3 in Hungary, we can compare the frequency of use of the paper-and-pencil mental analogue strategy by the Hungarian students with that of students in countries where the written algorithm is introduced before grade 3. First, it is interesting to note that the paper-and-pencil mental analogue of the written algorithm seems a slower strategy than an indirect addition strategy (for subtraction): about 39 s versus 12 s2 . Second, Csikos found only 25% Hungarian children using this written algorithm induced strategy, whereas [START_REF] Foxman | Mental calculation methods used by 11-year-olds in different attainment bands: a reanalysis of data from the 1987 APU survey in the UK[END_REF] found 51% of 247 British (England, Wales and Northern Ireland) 11year-old students using this strategy in a comparable 238 + 143 task.

Thus, the research by Csikos (2016) on students following a curriculum in which the algorithms are introduced somewhat later than usually does not confirm the speed of the written algorithm. Therefore, it qualifies the empirical results for this speed in section 1.2 [START_REF] Dewi | Strategies for written additions in adults[END_REF][START_REF] Torbeyns | Efficient and flexible strategy use on multi-digit sums: a choice/nochoice study[END_REF][START_REF] Csíkos | Strategies and performance in elementary students' three-digit mental addition[END_REF]. Moreover, the comparison with [START_REF] Foxman | Mental calculation methods used by 11-year-olds in different attainment bands: a reanalysis of data from the 1987 APU survey in the UK[END_REF] finding suggests that the frequency of the paper-and-pencil mental analogue of the written algorithm strategy should decrease through delayed teaching of the written algorithm. This suggests that rather than "stop" the teaching as suggested by [START_REF] Kamii | To teach or not to teach algorithms[END_REF] a less radical but nevertheless effective option could be to delay this teaching.

4.4 A model of calculation learning without using or seeing the written algorithms

The ACE research provides some data that allow to anticipate what happens if students do not learn the classical algorithm in the first two years of school. However, how will older students or adult persons calculate, if they have never learned these algorithms despite living in our culture? Early blind individuals (EB) can provide a model to answer this question. Indeed, EB individuals have never seen the written algorithms and were probably not encouraged to use it. In consequence, they will not use a paper-and-pencil column mental analogue procedure in mental calculation. If the latter strategy really complicates the mental calculation through the complex operations of carrying and borrowing, early blind individuals should perform better than late blind individuals (LB) and sighted controls individuals (SC).

The research by [START_REF] Dormal | Early but not late blindness leads to enhanced arithmetic and working memory abilities[END_REF] suggests at least that our audacious hypothesis is not completely unrealistic. Indeed, the research by Dormal et al. allows to compare the three groups of individuals (EB, LB, and SC) on two types of addition and subtraction problems. In the first type of addition (e.g., 49 + 5) and subtraction (e.g., 61 -6) problems, the second operand leads to carrying (or borrowing, unbundling) when using a written algorithm (or analogue), whereas in the second type it does not lead to these complications (e.g., 52+2, 57-2, 42+12, and 66-12). Comparing the performance of the three groups of individuals shows that the EB group performs better than the two other groups specifically in the first type of problems. The finding is reinforced by the fact that there were a majority of men in the EB group and a majority of women in the LB and SC groups. This because other findings (see sections 1.1.3, 3.5., and Fischer, 2004) suggest that girls should use the paper-and-pencil mental analogue strategy more than boys. Finally, Dormal et al. found no straightforward relation between working memory and arithmetic performance in the EB group. As an efficient working memory may explain the enhanced performance of the EB individuals, this latter negative result encourages finding another explanation. This explanation could be that the calculation strategy of the EB individuals differs from that of the LB and SC individuals, and, further, that the complex operation of carrying or borrowing makes the mental calculation harder for the LB and SC individuals, but not for the EB individuals.

Conclusions

In its empirical part, the present research used a sole subtraction word-problem. However, in practice, this problem allowed a representation of the described situation and the development of solution procedures. Insofar that the effectiveness of the SWA was not studied per se, our empirical approach allows then some generalizations to other arithmetical operations and conclusions about the appropriateness of teaching SWA for arithmetical problem-solving in the first school years. The conclusions are as follows.

Firstly, the multiple procedures, particularly the mulcol procedure-that is, at least one complementary procedure added to the columnar algorithm-, seems very effective. The complementary procedure (number line for example) provides the students with a way to find the arithmetical operation and, then, the columnar algorithm proves to be a mean correctly carry out the operation. When the use of calculators and computers will replace the columnar algorithm, the emphasis should be on a procedure (e.g., nline, box) that leads to find the operation. The time saved through not teaching the algorithms could allow the teachers to reinforce the training in mental calculation. Thus, the students should higher perform in arithmetic problem solving and the negative effects of the algorithm, notably on mental calculation, will be avoided.

Secondly, our present research shows that students' use of the columnar algorithm increases the carrying out of the erroneous arithmetical operation, 72 + 37 instead of 72 -37. Of course, the presence of the verb "win" in the statement of the problem can also explain this erroneous choice of the operation. However, the students in the experimental group had the same verbal problem to solve, and, therefore, had to inhibit this misleading verbal inductor as well. Nevertheless, they found less frequently a result equal or greater than 72 (16% of the students) than the students in the control group (24%), particularly the result 109 (5% vs. 12%). This lower proportion of students who found a result that violates the sense of subtraction in the experimental group, in addition to their slightly higher success rate (20% vs. 18%), is important because some neuropsychologists have attributed this type of error to a right hemispheric dysfunction [START_REF] Rourke | Central processing deficiencies in children: Toward a developmental neuropsychological model[END_REF][START_REF] Strang | Arithmetic disability subtypes: The neuropsychological significance of specific arithmetical impairment in childhood[END_REF]. In showing that a change in teaching may be sufficient in many cases to remedy to this type of error, the present research contributes to eradicate this explanation through a putative neurological dysfunction.

Thirdly, this erroneous choice of the arithmetical operation, and the uniform use of the SWA according to the ability of the students, suggests that the SWA for subtraction should be well suited for the most advanced students in 2 nd grade, but used without reflection or understanding by many others. For the latter students it is a blind practice, imposed from outwards, and partially or incorrectly automatized by its repetition.

More generally, deciding whether or not to teach a SWA for an arithmetic operation is a multi-faceted undertaking that depends especially on children's skills. However, the present empirical research provides information to be taken into account in the decision-making process as it suggests that this teaching may have a rather negative effect on solving arithmetic verbal problems.

  et al. (42 out of 58 participants), the results reported in section 1.1.4 may partially explain the strategy choice of Dewi et al.'s participants.

  Figure 1. A sample of the relevant procedures (the no and other procedures are not shown)To examine coding reliability of the procedures by the first coders, other coders, independently of the firsts, have re-coded 20% randomly selected procedures from the 4720 students. Despite the large number of categories (n = 11), the agreement, estimated by Cohen's Kappa, is "substantial"[START_REF] Landis | The measurement of observer agreement for categorical data[END_REF]: K = .64, 95% CI = [0.60, 0.67]. As a consequence, the procedures of the 4720 students were analyzed with their initial coding.

Table 1 .

 1 Number of uses, percentage of correct answers associated, and mean z-score of the students who used

	that procedure, for the 11 procedures
	Procedure	Number of uses	Percentage of success	Mean z-score
	box	205	12.68	-0.077
	column	499	20.24	0.009
	line	741	24.29	0.292
	nline	426	20.19	0.154
	numer	188	23.94	-0.015
	tree	45	22.22	0.275
	unit	326	21.78	-0.175
	mulcol	104	30.77	0.462
	muloth	519	27.75	0.348
	no	1387	13.05	-0.272
	other	280	12.86	-0.268

Table 2 .

 2 Number of uses of a procedure as a function of the arithmetic ability level of the students (ability levels are in deciles: decile 1 = low; decile 10 = high), with their rank correlations (rS)

	Decile	1	2	3	4	5	6	7	8	9	10	rS	p
	Procedure
	box	18	23	27	21	23	21	22	16	15	19	-.500 .141
	column	52	51	52	58	43	40	44	53	55	51	-.006 .987
	line	28	45	62	71	83	79	82	87	88	116	.963 <.001
	nline	18	49	36	41	41	51	43	53	38	56	.584 .077
	numer	18	15	20	20	15	21	25	27	15	12	-.037 .919
	tree	2	2	3	5	6	7	5	4	6	5	.593 .071
	unit	36	38	39	29	30	36	45	36	27	10	-.485 .156
	mulcol	5	5	6	5	14	9	8	14	18	20	.899 <.001
	muloth	22	27	49	45	35	54	54	82	76	75	.900 <.001
	no	236	174	140	151	153	131	115	84	112	91	-.915 <.001
	other	37	43	38	26	29	23	29	16	22	17	-.857 .002
	z-score	-1.66 -1.11 -0.75 -0.45 -0.16	0.12	0.42	0.74	1.13	1.72 mean z = 0.00

Table 3 .

 3 Percentage response types for the students who used the column procedure contrasted with the response types of all the other students When these results are differentiated between the experimental and control groups, the data (not presented in Table3) 1 show that the students in the experimental group produced in total slightly more the correct response "35" than the students in the control group, 20.20% versus 18.23%,  2 (1) = 2.90, p = .089, = 0.025. However, they produced less the response "109", which results from carrying out of the false operation, 5.08% versus 12.33%,  2 (1) = 80.45, p < .001, = 0.131, and produced more a response below 72, which is consistent with the subtraction sense, 68.96% versus 57.02%,  2 (1) = 71.79, p < .001, = 0.123.

	Procedure	Number			Response
		students 35 (correct) 109 (=72+37)	45	< 72 (35, 45) ≥ 72 ( 109)	None
	column (sole)	499	20.24	35.67	9.82	21.64	9.02	3.61
	all others (together)	4221	19.21	5.07	6.75	39.09	11.21	18.67
	Total	4720	19.32	8.31	7.08	37.25	10.97	17.08

Table 4 .

 4 Number of uses, percentage of correct answer associated, and mean z-score of the students who used the column procedure, as a function of the group: experimental vs. control.

	Group	Number	p	Percentage	p	Mean z-	p
		of uses	 (a)	of success	 (a)	score	sqrt(ges) (b)
	Experimental	80	p < .001	22.50	p =.301	0.317	p = .003
	Control	419	.79	19.81	.02	-0.050	√𝑔𝑒𝑠 =.132
	Total or significance	499	signif.	20.24	not signif.	0.009	signif.

Table 5 .

 5 Percentage of use of the procedures as a function of gender

	Proc 	box	column	line	nline numer	tree	unit	mulcol muloth empty other
	Girls	4.54	12.30	14.04	8.63	4.19	1.05	8.11	2.53	11.34	27.13	6.15
	Boys	4.16	8.94	17.27	9.40	3.75	0.87	5.77	1.90	10.68	31.53	5.73
	Total	4.34	10.57	15.70	9.03	3.96	0.95	6.91	2.20	11.00	29.39	5.93
	4 Discussion
	4.1 A limitation of the current study

A complete table is available from the corresponding author of the article.

The author qualifies the differences in response time as "convincing". However, because students spontaneously used their strategies, one cannot exclude that the slow students choose the (eventually) slow strategy and rapid students chose the (eventually) fast strategy.

This research was supported by a grant from France's "Programme d'Investissements d'Avenir" (ANRU/DSDP/D14-2780). to thank all the children and teachers who took part in the experiment. We are also grateful to the experimenters, coders, and administrators for their invaluable help in organizing and conducting the experiment.


Guillaume Touya

Marion Dumont

Progressive Block Graying and Landmarks Enhancing as Intermediate Representations between Buildings and Urban Areas

Keywords: building generalization, landmarks, building classification, machine learning, multiple criteria decision

Geovisualization applications that allow the navigation between maps at different scales while zooming in and out often provide no smooth transition between the individual building level of abstraction and the representation of whole urban areas as polygons. In order to reduce the cognitive load of the user, we seek to add intermediate zoom levels with intermediate and progressive abstractions between buildings and urban areas. This paper proposes a method based on progressive block graying while enhancing building landmarks, to derive these intermediate representations from the individual buildings. Block graying is based on an automatic building classification, and a multiple criteria decision technique to infer inner city blocks. The landmarks identification relies on machine learning and several criteria based on geometry and spatial relations. The method is tested with real cartographic data between the 1:25k (with individual buildings) and the 1:100k scale (with urban areas): transitions with one, two, or three intermediate representations are derived and tested.

Introduction

Topographic maps are now more used in geovisualization applications, where they can be zoomed in and out, than on paper. However, the maps that are displayed in such applications are either derived from scanned paper maps independently generalized, or poorly generalized when directly produced for screens, and in both cases, the cognitive load of the user is quite significant, each time the scale changes. One of the causes for this cognitive load is the gap in abstraction in the representation of map objects: e.g. the buildings might be represented by individual polygons at one scale and by built-up areas at smaller scales (Dumont et al. 2016b). Even if most of traditional knowledge on how to make effective and beautiful maps still applies to these geovisualization applications, we do not know exactly what the best strategy is to generalize maps that enable a smooth navigation in such applications [START_REF] Dumont | Automated generalisation of intermediate levels in a Multi-Scale pyramid[END_REF]. One strategy to smooth the navigation across scales is to use a varioscale model with continuous representations of map objects (van Oosterom et al. 2014). Another one is to add small number of consistent intermediate scales that gradually change the levels of abstraction and generalization [START_REF] Dumont | Automated generalisation of intermediate levels in a Multi-Scale pyramid[END_REF]. This paper focuses on the latter strategy, as it is part of a broader research project that focuses on the derivation of intermediate scales. Comparing both strategies still is a future goal. The paper particularly deals with the specific abstraction gap between individual buildings that are often represented at scales around the 1:25k, and built-up areas represented at the 1:100k and smaller scales (Dumont et al. 2016b). What is the best strategy to gradually generalize the buildings into a built-up area to ease smooth zooming? The answer to this question can only be found by controlled usability tests (Šuba et al. 2016). For this we need some material to carry out the usability tests, i.e. map series from 1:25k to 1:100k that contain buildings that were differently generalized [START_REF] Dumont | Alternative Transitions Between Existing Representations in Multi-Scale Maps[END_REF]. We identified three main strategies to generalize buildings at such scales: the classical agent-based generalization [START_REF] Ruas | Strategies for automated generalization[END_REF][START_REF] Barrault | Integrating multi-agent, object-oriented, and algorithmic techniques for improved automated map generalisation[END_REF][START_REF] Duchêne | The CartACom model: transforming cartographic features into communicating agents for cartographic generalisation[END_REF]) that enlarges and then contextually eliminates and displaces buildings; building typification (Sester 2001, Burghardt and[START_REF] Burghardt | Mesh simplification for building typification[END_REF]; and the graying (or covering) of dense buildings blocks [START_REF] Stoter | Feasibility study on an automated generalisation production line for multiscale topographic products[END_REF]. This paper proposes a generalization method that follows the latter strategy, by gradually graying building blocks while highlighting the building landmarks.

The following section briefly describes the type of map that we seek to achieve with the gradual block covering. Section 3 explains how blocks are ordered to be covered in the intermediate scales between individual buildings and built-up areas. Section 4 details how building landmarks are automatically extracted from the buildings. Section 5 shows some experiments where block covering and landmarks highlighting are jointly used to derive intermediate scales. Finally, Section 5 draws some conclusions and describes possible further research.

Gradual Block Covering

We define block covering or graying (because of the color used in the IGN maps to cover blocks) the operation that replaces individual buildings in a block by a polygon that covers the extent of the built-up area in the block. The block covering generalization strategy proposed in this paper stems from the 1:50k maps from Kadaster Netherlands. In these maps, the dense blocks are represented by a colored polygon that replaces the individual buildings, but individual buildings are kept where the density is low (Fig. 1). A similar strategy was proposed at Ordnance Survey, the British NMA (Regnauld andRevell 2007, Revell et al. 2011), with the amalgamation of buildings to create large polygons that cover the built-up area inside each block. As the aim of the project compare several generalization strategies to derive gradual intermediate scales in a multi-scales map, we selected the Kadaster approach for its simplicity and the fact that it abstracts more the building than the amalgamation approach. This is a good intermediate abstraction between all individual buildings and only a built-up area, which could be even better by keeping the most important buildings in the dense blocks. To make this strategy gradual, we propose a three-step workflow (Fig. 2): inner city (very dense) blocks are identified to quickly cover them when zooming out of the 1:25k; buildings are classified to cover first urban and industrial buildings (i.e. the blocks that contain such buildings), and after suburban and rural buildings; landmarks are automatically inferred to keep them on the map even if their block is covered. Towns are automatically derived from a buildings dilatation (Gaffuri and Trévisan 2003), while blocks are computed inside these towns using the faces of the road-river-railroad network graph.

Inner City Generalization and Block Classification

This section describes how building blocks are gradually covered using a multiple criteria decision technique to identify inner city blocks that should first be covered, and using a building/block classification to cover blocks at smaller intermediate scales.

Inner City Generalization

The inner city blocks considered here do not necessarily follow the common geographical characteristics of inner cities, as we are interested in the small, dense blocks, populated by large complex buildings that can be found in inner cities. Several criteria were derived from these general characteristics: (1) area, i.e. small blocks tend to be covered first as there is no space inside to enlarge the buildings; (2) density, i.e. the block area divided by the sum of areas of buildings and roads symbols, as too dense blocks cannot allow the display of its contained buildings once they are enlarged; (3) building area, i.e. the distribution of building areas inside the blocks, as very large buildings in a block leave no space for the other buildings of the block to be displayed. To aggregate these criteria in the decision of characterizing a block as inner city block to cover, we used the ELECTRE TRI multiple criteria decision technique, which was successfully used to infer the level of detail of OpenStreetMap by combining geometric and semantic criteria [START_REF] Touya | Detecting Level-of-Detail inconsistencies in volunteered geographic information data sets[END_REF]. This technique does not aggregate the values for each criterion, because they are often hard to compare (how to compare an area to a density and to a distribution?), but makes order relations for each criterion (i.e. for this criterion, this block is more inner city than this one), and then aggregates the order relations: e.g. if all criteria give the same order relation, it is the global decision. This technique allows veto thresholds for criteria, i.e. the difference for a criterion is so important that the order relation derived from this criterion wins over the other criteria. Table 1 presents the criteria used in our method. Given the first results obtained with the first three criteria, two other criteria (centroid and neighborhood) were added with smallest weights to obtain more contiguous inner city blocks. Results obtained with the ELECTRE TRI method are presented in Fig. 3. The detected inner city blocks do not exactly correspond to the inner city space of the two cities, but match well with the inner city blocks that are too small and dense to preserve an individual building representation at scales smaller than 1:25k.

Building and Block Classification

The multiple criteria decision technique presented in the previous section does not provide any input to gradually cover the other blocks of the map, once the inner city blocks are covered. That is why we propose to use block classification, and to cover blocks based on this classification. The classes we used in our experiments derive from the building classification proposed by [START_REF] Steiniger | An approach for the classification of urban building structures based on discriminant analysis techniques[END_REF]: inner city, urban, suburban, industrial, rural, and hetero-geneous. We first classify buildings using the descriptors from Steiniger et al. ( 2008) (e.g. size, number of vertices, compactness, density around…) with a Support Vector Machine classifier (Fig. 4). The results are fair, but some strange artefacts remain, with similar and neighbor buildings having different classes, with sometimes jumps in classes. For instance, there is a building alignment in the upper part of Fig. 4 with all buildings classified as rural except two, one being suburban, and one urban. To avoid such artefacts, [START_REF] Steiniger | An approach for the classification of urban building structures based on discriminant analysis techniques[END_REF] used a spatial filter to homogenize the outputs of the classification, as similar neighbor buildings should be classified. We did not use this filter, because the homogenization is handled in the next step, and it can explain these artifacts, but there might be several ways to improve the classification, for instance by using the probability given by the learning algorithm.

Then, blocks are classified using the class of the majority of its inner buildings; if there is no class majority in the block, it is classified as heterogeneous. This step allows some kind of smoothing of the results of building classification, and replaces the spatial filter used by [START_REF] Steiniger | An approach for the classification of urban building structures based on discriminant analysis techniques[END_REF] to homogenize neighbor buildings.

Landmarks Automatic Inference

We make the assumption that landmarks can help the map readers to grasp the main spatial relations of the map across scales and to find their way when zooming in or out. "Landmarks are prominent, identifying features in an environment, which provide an observer or user of a space with a means for locating oneself and establishing goals." [START_REF] Sorrows | The nature of landmarks for real and electronic spaces[END_REF]. In this case, we consider that landmarks are buildings that are prominent due to their symbol (derived from their nature), their size or shape compared to their neighbors, or their position on the map. As our building landmarks are supposed to help the map user navigating across scales, they should somehow be displayed at all scales on top of the covered blocks. If necessary, building landmarks will be enlarged or displaced to be legible at all scales.

Landmarks automatic extraction methods exist in the context of route wayfinding [START_REF] Elias | Extracting landmarks with data mining methods[END_REF], and we tried to adapt this method based on machine learning. Table 2 describes the descriptors of the landmarks that are adapted from [START_REF] Elias | Extracting landmarks with data mining methods[END_REF], considering the characteristics of a landmark in our use case stated above. As proposed by [START_REF] Elias | Extracting landmarks with data mining methods[END_REF], a decision tree classification method was used, and the training dataset was the same as the one used in the building classification method presented in the previous section. The results obtained with this method are presented in Fig. 5, and match well with what we considered as landmarks, i.e. buildings different from their neighbors and/or that have a specific function (e.g. administrative buildings). The used classification method simply flags the buildings as landmarks or not, with a confidence ratio between zero and one, so the results can be adjusted by changing the confidence ratio threshold (a threshold of 0.97 was used to obtain the results presented in Fig. 5). Buildings with specific orientation compared to the others might be more salient granularity number of vertices of the building Buildings with more granularity might be more salient Fig. 6 shows a comparison between the automatic detection and manual selection of the landmarks in the map by a cartographer. Some landmarks chosen by the cartographer are not detected as landmarks by the proposed method, but most of all, there are too many landmarks detected compared to the manual selection that retains only the most salient landmarks. Fig. 6. Comparison between the automatic detection and a manual selection of landmarks: two of the manually selected landmarks are not automatically detected, but most of all, the number of automatically detected landmarks is much bigger.

Derivation of Intermediate Scales

In the presented maps, we used the initial 1:25k buildings at all scales, but we plan to use the buildings generalized by the agent-based or typification strategies we are developing in parallel. In this dataset, building semantics is minimal and related to buildings that are rendered differently: public buildings, industrial or commercial buildings, religious buildings, castles, and greenhouses. To be really effective, the intermediate maps should also have their road network generalized (as well as the other map themes), which is not the case here for time issues, so we only present buildings in the figure. The choice of three intermediate scales is quite arbitrary: as we intend to compare the different strategies to build the intermediate scales with a user experiment, it is not possible to test too many options that would make the experiment too long for the user.

Conclusions and Discussion

This paper proposes methods to gradually generalize an individual building layer into a built-up area by block covering and highlighting of the building landmarks. Although the methods may largely be improved, the first results are encouraging enough to consider once again machine learning in generalization, because of the recent advances in this domain, as claimed in [START_REF] Touya | Lessons learned from research on multimedia summarization[END_REF].

The proposed methods can all be improved by tuning their parameters, and by spending more time on creating better training datasets. For instance (Weng et al. 2017) proposes a multi-scale landmark extraction method that might better suits our purpose than the method from [START_REF] Elias | Extracting landmarks with data mining methods[END_REF] used in this paper. We have seen in Section 3.2 that a building classification was used to infer a block classification: the class of the block is the class of the majority of the buildings in the block (or heterogeneous if there is no class with majority). It might be more effective to directly classify blocks using a similar method. Finally, these gradual intermediate representations or abstractions of the individual buildings will be integrated in a user survey, with alternative methods, to verify that adding intermediate scales does improve the user efficiency while zooming in a geovisualization application, and to learn which generalization strategy is the most effective in this context [START_REF] Dumont | Alternative Transitions Between Existing Representations in Multi-Scale Maps[END_REF].

van Oosterom, P., Meijers, M., Stoter, J., Šuba, R. (2014). Data structures for continuous generalisation: tGAP and SSC. In D.

Burghardt, C. Duchêne, W. Mackaness (Eds.), Abstracting Geographic Information in a Data Rich . London: Springer International Publishing. Weng, M., Xiong, Q., Kang, M. (2017). Salience indicators for landmark extraction at large spatial scales based on spatial analysis methods. ISPRS International Journal of Geo-Information, 6(3), 72.

Fig. 1 .

 1 Fig. 1. Kadaster Netherlands 1:50k map extract: dense urban blocks are represented by colored areas, all buildings inside these blocks are removed (Stoter et al 2011).

Fig. 2 .

 2 Fig. 2. Workflow for gradual block covering: the intermediate building layers are composed from inner city blocks detection, building classification and landmarks inference.

Fig. 3 .

 3 Fig. 3. Inner city block detection with ELECTRE TRI (transparent dark gray blocks), for two towns where the inner blocks are not in the center of the town extent polygon (both are on the seaside).

Fig. 4 .

 4 Fig. 4. Building classification result: inner city (green), urban (blue), industrial (yellow), suburban (magenta), rural (gray).

Fig. 5 .

 5 Fig. 5. Result of landmarks automatic inference on 1:25k buildings from IGN (landmarks are displayed in red).

Fig. 6 .

 6 Fig.6. Gradual transition by block covering with three intermediate scales between 1:25k and 1:100k. The remaining buildings at each scale should be generalized in some way to finalize the building/block/built-up area layers.

Table 1 .

 1 Criteria used in the inner city detection algorithm

	Criterion	Description	Weight	Veto threshold	Preference
					threshold
	area	area of the block compared to	1.0	0.7	0.2
		the other blocks of the town
	density	density of the block using	1.5	0.4	0.2
		buildings and road symbols
	building area	area distribution of the inner	1.5	0.6	0.25
		building blocks compared to the
		distribution of building areas in
		the town
	centroid	distance to town centroid	0.5	0.95	0.2
	neighborhood	density of the neighbor blocks	0.8	0.4	0.3

Table 2 .

 2 Descriptors used to qualify buildings as landmarks.

	Descriptor name	Description	Why it is used
	category	Building semantic category (e.g. public,	Some categories are rendered with a spe-
		industrial, unknown…)	cific symbol making them more salient
	compactness	compactness of the building, Miller index	Buildings with salient shapes are more
		(MacEachran 1982)	likely landmarks than regular shaped
			buildings
	elongation	elongation of the building (length/width	Also characterizes building shape
		ratio of the minimum bounding rectangle)
	squareness	total deviation of angles to square angles	Also characterizes building shape
		(Lokhat and Touya 2016)
	density	density of buildings in a 100 m radius	Isolated buildings might be more salient
	adjacency	number of adjacent buildings	When attached to another building, a
			building is less salient
	neighbors	number of buildings in a 100 m radius	Isolated buildings might be more salient
	crossroad	distance to nearest crossroad	Crossroads are landmarks, so buildings
			near crossroads might be more salient
	size	area of the building	Large buildings might be more salient
	orientation	general orientation of the building, i.e.
		orientation of the longest side of the min-
		imum bounding rectangle (Duchêne et al.
		2003)

th ICA Workshop on Generalisation and Multiple Representation, Washington D.C., 2017

Acknowledgements

Our work is part of MapMuxing project, funded under grant ANR-14-CE24-0011-01 by French national agency for research.


Guillaume Touya

Thibaud Chassin

RJMCMC based Text Placement to Optimize Label Placement and Quantity

Keywords: label placement, optimization, RJMCMC, cartography

Label placement is a tedious task in map design, and its automation has long been a goal for researchers in cartography, but also in computational geometry. Methods that search for an optimal or nearly optimal solution that satisfies a set of constraints, such as label overlapping, have been proposed in the literature. Most of these methods mainly focus on finding the optimal position for a given set of labels, but rarely allow the removal of labels as part of the optimization. This paper proposes to apply an optimization technique called Reversible-Jump Markov Chain Monte Carlo that enables to easily model the removal or addition during the optimization iterations. The method, quite preliminary for now, is tested on a real dataset, and the first results are encouraging.

Introduction

Text placement is one of the longest tasks in map design, and many proposals have been made to automate the process with optimization techniques (see an exhaustive review in [START_REF] Rylov | A comprehensive multi-criteria model for high cartographic quality Point-Feature label placement[END_REF]. These methods are now quite effective, and they turn common quality criteria such as preferences on text position around the symbol, text overlaps with other map elements, or ambiguity between two labels, into numerical equations that are inserted into classical meta-heuristics such as simulated annealing to find the optimal placement. But most of existing techniques have one common drawback: the amount of labels to display is fixed at the beginning of the optimization. The optimized decision is the best position for the label, the label is never removed, even if there is no good location in the map. This paper proposes to use an optimization technique called RJMCMC for "Reversible-Jump Markov Chain Monte Carlo" [START_REF] Green | Reversible jump markov chain monte carlo computation and bayesian model determination[END_REF], able to include text placement and presence into the optimization. The second part of the paper briefly describes how we modelled label placement as a RJMCMC optimization, and the third part presents some preliminary results.

Description of the Optimization Method

The family of Reversible-Jump Markov Chain Monte Carlo optimization methods is composed of stochastic methods with a varying dimension solution space. Usually, stochastic optimization methods such as simulated annealing that was widely used in label placement [START_REF] Barrault | A methodology for placement and evaluation of area map labels[END_REF], pick a label to displace (with varying randomness) and evaluate the global satisfaction of the system with this new location for the label, and the systems stops when an optimal solution is achieved. The evaluation is made with a cost or energy function that summarizes label position and the conflicts with other labels. The solution space is very large, and if we use the standard 8-position model for one label (see Fig. 1), it counts 8 n configurations where n is the number of labels. With RJMCMC, we add, at each iteration, the possibility of "birth" or "death" for any label, reducing or increasing the dimension of the solution space. The global quality of the output is computed after each iteration, based on an energy function to minimize (Eq. 1).

(Eq. 1)

𝑒 𝑡𝑜𝑡𝑎𝑙 = 𝑒 𝑢𝑛𝑎𝑟𝑦 + 𝑒 𝑏𝑖𝑛𝑎𝑟𝑦 + 𝑒 𝑐𝑜𝑙𝑙𝑒𝑐𝑡𝑖𝑜𝑛 The unary energy sums for each label the satisfaction energy related to constraints that only affect one label, e.g. the position of the label around the point feature it labels. The binary energy sums for each label the satisfaction energy related to constraints of one label with its neighbors. For instance, the possible overlaps of two labels are evaluated by the binary energy. Finally, the collection energy is related to constraints on groups of labels, which allows, for instance, the preservation of density differences in the map. The use of three types of energies makes the process faster as when one label is displaced only the unary of this label, and the few binary and collection energies that involve this label are recomputed.

We used the different criteria listed by [START_REF] Rylov | A comprehensive multi-criteria model for high cartographic quality Point-Feature label placement[END_REF] that summarize the existing literature: position around the point (adapted here with continuous positions, Fig. 1 and Eq. 2) as the unary energy, overlaps with map symbols, ambiguity with nearby labels as binary energies, and label density as a collection energy. In order to make the system remove some labels, the cost of position around the point is made negative: well-placed texts help minimizing the total cost, but removing a poorly placed text does not penalize too much global quality. This criterion is weighted by label importance to prevent the system from removing important labels. The unary energy for label position uses a continuous model for label position (Fig. 1). We chose this model first because of the used implementation of RJMCMC [START_REF] Brédif | librjmcmc: An open-source generic c++ library for stochastic optimization[END_REF]) that requires real intervals to pick into rather than 8 integer values, and because it gives more flexibility to move a label, in order to avoid label overlaps. Eq. 2 shows the principles of this energy computation for the case of a label position between positions 1 and 7, and the interpolation is carried out similarly for the seven other quadrants.

Preliminary Results

We carried out experiments on a cartographic dataset that was generalized for 1:25k maps, but we tried to display all the labels and the map at a smaller scale where the label bounding box covers more space and the need for a reduction of the number of labels is significant. The size of the text is intentionally large to force conflicts with many labels (Fig. 2). Fig. 3 shows a zoomed extract of the same dataset for a large number of iterations (60,000,000). The placement is clearly better with a significant number of labels removed but the result is not optimal. This can partly be explained by the caricatural size of the text, and its unique size: with only the main labels with this large size and smaller sizes to illustrate decreasing importance, there would be fewer conflicts to solve. However, this preliminary results shows that there is much to do to improve the proposed method.

Conclusions

The first results presented here are encouraging as the removal of some labels really improves map legibility. But there is still a lot to do to improve the method, by running more tests to tune the parameters and the criteria. For instance, it would be useful to compare the results of our RJMCMC optimization compared to a simulated annealing optimization with the same criteria and the same cost function. We also want to include text placement for linear (e.g. river names), and for areal (e.g. forest names) labels in the method that currently only considers point labels. We also plan to test the method on dense OpenStreetMap areas, because they may contain a huge number of named elements that can be displayed and the reduction of this number is mandatory. Finally, the optimization is quite slow for now, and we want to improve our heuristics (e.g. no need to search for overlaps with distant labels).

Fig. 1 .

 1 Fig. 1. Modelling label placement priorities in the optimization model: (a) the position is encoded with an angle value and a radius that guarantees that the label is not too close or too far from the related point feature; (b) the classical 8-position priority model is used, and (c) translated into a continuous model where priority is interpolated using the angles.

Fig. 2 .

 2 Fig. 2. Initial text placement with everything at the top right position (184 labels) and the optimized placement on a 1:25k map (114 labels left @IGN).

Fig. 3 .

 3 Fig. 3. Zoomed extract of the test dataset for a large number of iterations (60,000,000) (@IGN).

Acknowledgements

Our work is part of MapMuxing project, funded under grant ANR-14-CE24-0011-01 by French national agency for research.