Jieun Kim

Carole Bouchard

Hokyoung Ryu

Emotion finds a way to users from designers : Assessing product images to convey designer's emotion

Keywords: product image, emotion-driven design, cognitive responses, emotional responses, physiological responses, SAM (Self-Assessment Manikin), PCA (Principal Component Analysis), GSR (Galvanic Skin Response)

Along with a growing interest in emotional design and pleasurable products, it is necessary to understand how designers are able to maintain emotional impacts of their design solutions throughout the design process, and how these solutions can find a way to evoke the intended emotional feeling of the users. The present study first examined emotional responses to early design sketches, and how these responses could be used to check if the emotional impacts of their early sketches were observed in a combinative way of cognitive-linguistic and physiological approaches. Based on the findings of the empirical study, we further discussed how the emotional differences of product images would be generated by product forms. We figured out that good form factors of early design sketches might elicit positive feelings and high arousal states, thereby incorporating semantically meaningful features in the product images.

Introduction

Feelings are much like waves, we can't stop them from coming but we can choose which one to surf (Jonatan Mårtensson) Designers are naturally and intuitively conscious of the emotional impact of their product design during the whole design process (for example, [START_REF] Norman | Emotional Design: Why We Love (or Hate) Everyday Things[END_REF][START_REF] Desmet | Framework of product experience[END_REF][START_REF] Crilly | Shaping things: intended consumer response and the other determinants of product form[END_REF]Authors, 2010;[START_REF] Ho | Emotionalise design, Emotional Design, EmotionDesign: A new perspective to understand their relationships[END_REF][START_REF] Cuisinier | Emotions and design between feelings and emotions[END_REF]. It is, by and large, touted as a good design solution when it rightfully provokes emotional responses from consumers by developing the product image that satisfies or delights them (Crilly, Moultrie, and Clarkson, 2009, p.232). This interest is partly due to industrial context to develop more pleasurable products and mostly due to increase expressivity of products for consumers. The fact that one should include users' likely emotional responses to product design has been widely acknowledged in the design community, but how this can be done is still elusive.

Indeed, Kansei engineering firstly stressed on a semantic approach to characterise perception of the product (see [START_REF] Nagamachi | Kansei Engineering[END_REF]2001, Jindo, Hirasago, and[START_REF] Jindo | Development of a design support system for office chairs using 3D graphics[END_REF]. Since 1980s, it has evolved the semantic approach to product images and constantly influenced how to present emotiondriven product design (see [START_REF] Schütte | Designing Feelings into Products: Integrating Kensei Engineering Methodology in Product Development[END_REF]. Recently, emotional design has stressed on the relationship between the users' emotional responses and product images that are arisen from both the semantic and emotional dimensions of the product (see Overbeeke and Hekkert, 1999;[START_REF] Desmet | Wheelchairs can be fun: a case of emotion-driven design[END_REF][START_REF] Norman | Emotional Design: Why We Love (or Hate) Everyday Things[END_REF].

That said, one of the main concerns in the current design science is to generate early sketches through understanding a link between the formal attributes of products and a set of emotional terms (See [START_REF] Hsiao | Applying the semantic transformation method to product form design[END_REF][START_REF] Hsiao | A neural network based approach for product form design[END_REF]. In particular, the emotional values arsing from the early sketches need to be kept in the whole design process, also being observed in the final product image. However, most of previous studies have investigated how final products can provoke emotional differences and how this would be perceived by the users; very few attempts have been made on the emotional impact of early design solution [START_REF] Desmet | Wheelchairs can be fun: a case of emotion-driven design[END_REF]Authors, 2011). This new approach is referred to as an ''emotion-driven design'' in the work of [START_REF] Desmet | Wheelchairs can be fun: a case of emotion-driven design[END_REF], acknowledging that the development of an instrument to be sensitive to assess emotions is of great necessity.

In this context, the research questions concerned in the present study are ''how designers are able to manipulate the emotional impact of their design solutions, and how these design solutions are perceived by the users?'' Our research framework was then designed to establish a link between semantic and emotional responses and formal attributes of product in the early stages of design process (figure 1). Moreover, given that emotions elicited in the early representations (here, early sketches) might be hard to identify and quantify, we carried out an empirical study by employing both cognitive and physiological approaches to capture the emotional intents of the early sketches, and how this can be preserved in the whole design process.

Figure 1

The conceptual research framework: A designer wants to deliver her emotional intents throughout the design process.

In this paper, we first present theoretic literature reviews in Section 2. Next, two hypotheses are formulated to be tested in the present study. Then, Section 3 describes the empirical study, and the results and discussion are presented in Sections 4 and 5, respectively. Finally, Section 6 presents the general conclusions and further studies.

Projecting the designer's emotions onto product images: Communicating emotional intents with the users

Synchronising emotions between the user and the designer is an emerging research topic in design science. As some pioneers in the user experience (UX) design community, such as Norman's system image (1988), have incessantly proposed new theories and methods on how to ensure the delivery of emotional intents from the designer to the user. [START_REF] Ho | Emotionalise design, Emotional Design, EmotionDesign: A new perspective to understand their relationships[END_REF] have investigated some taxonomy related to the flow of emotion between the designer and the user through design outcomes. Especially, they argued that designers inject their emotions into a product, which is referred to as ''Emotionalise design''. According to the affective user-designer model proposed by [START_REF] Helander | Affective and pleasurable design[END_REF], there are two different systems of information processing and responses: affective system and cognitive system, as shown in figure 2. This implies that the two systems should not be separated to create the image of the product people are using, and feeling. [START_REF] Crilly | Seeing things: consumer response to the visual domain in product design[END_REF]2009) also developed a conceptual framework for establishing product images, representing the designer's intents and user responses, in terms of cognition, affect, and behaviour.

Figure 2. Coupling of affect and cognition [START_REF] Helander | Affective and pleasurable design[END_REF] In sum, the underlying theme of the three approaches above is that emotional design [START_REF] Norman | Emotional Design: Why We Love (or Hate) Everyday Things[END_REF] should project designer's emotional intents to the design outcomes and the users instantly perceive the designer's intents; however, there is still open to question as to how the product images can be projected on the product form, and how the designer's emotions can communicate with the users via the corresponding product form.

Differences in semantic and emotional responses from product forms

In the literature in design science, [START_REF] Bloch | Seeking the ideal form: Product design and consumer response[END_REF] emphasised that product image or form plays an important role as a precursor to the users' cognitive and affective responses to a product. For instance, [START_REF] Chuang | How to rate 100 visual stimuli efficiently[END_REF] selected 100 armchairs as stimuli and semantically categorised them by their product forms. The method used was a semantic difference (SD) with nine scales for five bipolar adjectives: traditional-contemporary, rational-emotional, complexsimple, heavy-light, exaggerate-realistic. Hsiao and Liu (2002) also investigated a link between semantic lexicons and product images in various design sectors by using such as soft -hard, complex -simple, casual -formal, and female -male. This approach has also been validated in many design practices including automotive design [START_REF] Hsiao | Applying the semantic transformation method to product form design[END_REF], LCD monitors, armchairs [START_REF] Hsiao | A neural network based approach for product form design[END_REF], door locks [START_REF] Hsiao | Use of Gray System Theory in product-color planning[END_REF], and coffee makers [START_REF] Hsiao | Product-form design model based on genetic algorithms[END_REF]. More recently, Authors (2010) carried out a novel study to identify emotional values from perfume bottles. Their research was further advanced in order to generate product form factors based on some given emotional attributes (e.g., a rounded shape might deliver pleasant feeling). [START_REF] Artacho | Analysis of the impact of slight changes in product formal attributes on user's emotions and configuration of an emotional space for successful design[END_REF] carried out an experiment with nine virtual computer loudspeakers having slightly different form attributes. They demonstrated that users are highly sensitive to product's form attributes and their changes can influence the user's emotional responses.

Although the studies above have been made on the high-fidelity product forms, very few have examined on early sketches or low-fidelity prototypes where designers firstly externalise their design concepts. This is very important in the sense that a first emotional impression of a product should be evolved throughout the whole design process, and as a consequence, this would ensure the delivery of emotional values to the user, at last.

How to measure emotional differences in product images

The modalities for expressing emotional responses are not all the same, and they can be presented in various levels such as semantic words, facial expressions, skin conduction or heart rates. Since the 1980s, many theoretical and experimental researchers from Psychology have introduced classification schemes for defining emotions (see [START_REF] Plutchik | Emotion: A psychoevolutionarysynthesis[END_REF][START_REF] Russell | A circumplex model of affect[END_REF][START_REF] Ekman | An argument for basics emotions[END_REF]. To our best knowledge, a most agreed notion is that emotions can be conceptualised along with the two dimensions: valence and arousal.

Here, a cognitive-linguistic method grounded on the semantic differential approach has been widely used to assess the emotional responses to product images. In particular, the Self Assessment Manikin (SAM) by [START_REF] Lang | International affective picture system (IAPS):Technical Manual and Affective ratings[END_REF] is a pictorial questionnaire in terms of arousal, valence, and dominance. In addition, lexical emotional feelings, including a list of 50 emotional reactions proposed by Geneva Emotion Research Group (1988) are often used to collect the emotional responses. However, given that emotional aspects of design are hard to express in a lexical way only, it is necessary to have more subtle modalities that can reflect the user's emotional state. Psycho-physiological methods have thus been emerging, along with the Kansei engineering field, by combining physiological techniques, such as electromyography (EMG), heart rate, electroencephalography (EEG), and so forth [START_REF] Nagamachi | Workshop 2 on Kansei engineering[END_REF][START_REF] Schütte | Designing Feelings into Products: Integrating Kensei Engineering Methodology in Product Development[END_REF][START_REF] Lévi | On Kansei and Kansei Design: A description of Japanese design approach[END_REF]Tomino et al., 2008).

Again, a cognitive-linguistic approach is relatively simple, cheap, and quick method. Especially subjective evaluations through questionnaires and interviews are convenient and easy to administer. In addition, they can detail secondary emotions in a lexical way [START_REF] Lang | International affective picture system (IAPS):Technical Manual and Affective ratings[END_REF][START_REF] Nagamachi | Workshop 2 on Kansei engineering[END_REF]. However, the cognitive-linguistic methods have some drawbacks. They do not enable real-time assessments and do normally capture subjective emotional responses in a holistic and reflective manner; therefore it lacks consistent evaluation thanks to respondent's different interpretations of the emotional adjectives. In addition, the use of emotional scales, which often contains a long list of emotional adjectives, might cause some fatigue for the respondents. Otherwise, a physiological approach can give real-time quantitative data and user's unconscious responses [START_REF] Tran | Advantages and disadvantages of physiological assessment for next generation control room design[END_REF]. However, emotional responses collected from physiological methods might not valid in that they are interfering with the designer's natural activity (SEAT Project D1.1, 2006;[START_REF] Feel Europe | Vision paper[END_REF] and certain physiological measurements (e.g., EEG) cannot be used for a long time duration [START_REF] Tran | Advantages and disadvantages of physiological assessment for next generation control room design[END_REF].

Having said that, some pioneers in the design community have offset the drawbacks of these two approaches, taking them together to explore the emotional states elicited in the product image. For example, [START_REF] Tomico | Kansei physiological measurements and constructivist psychological explorations for approaching user subjective, experience[END_REF] carried out a pilot study in order to explore the suitability of psychophysiological measures. They combined 2-point Electroencephalogram (EEG) and Repertory Grid Technique (RGT) interviews in order to measure the degree of comfort in terms of pleasantness and arousal (excitement). Jeskin et al. ( 2009) conducted a more rigorous experimentation for comparing Infrared Thermography (IRT), Electroencephalogram (EEG), and subjective measures of affective experience (ASR) to measure both cognitive and affective states.

Likewise, the present study also employs a mixed way: primary emotion by the physiological approach; secondary emotion by the cognitive-linguistic way. For the former, the Galvanic Skin Response (GSR) measure is applied and the latter for Self-Assessment Manikin (SAM) and twenty lexical terms (see Section 3 for detail).

The review of previous literature suggests that the product form in the early design process may play an important role in conveying the designer's intent (semantic and emotional). Thus, we developed the following two hypotheses:

 Hypothesis 1: Product forms in the early design process can generate emotional differences in the user's mind;

 Hypothesis 2: The emotional differences can be interpreted by conjoining both cognitive-linguistic and physiological way.

The following empirical study has been designed to address these two research questions and then how the emotional intents from the designer can be conveyed to the users via the product images at the earliest.

Method

To test the hypotheses above, a laboratory-based experiment was designed. Regarding a combination of cognitive-linguistic and physiological methods, we first employed a questionnaire developed by [START_REF] Mantelet | Prise en compte de la perception émotionnelle du consommateur dans le processus de conception de produits[END_REF], which has been validated as a mean to identify and quantify the semantic and emotional responses to trend boards and product images. The questionnaire consists of the valence/arousal dimensions of the Self-Assessment Manikin (SAM), and 5-point rating scales for ten semantic descriptors and ten emotional terms. The rating scales of the questionnaire were then compared with Galvanic Skin Response (GSR) measures.

Participants

A total of twelve French product designers took part in this experiment. The reason to employ only French product designers in the study was three-fold: i) to reduce the cultural issue only French-native speakers were invited to participate; ii) to significantly maximise the power of the sample size (i.e., 12), professional product designers were recruited instead of the general users that might not have sufficient experiences on early sketches; iii) we also assumed that most of design activities are made on the team-based, so the design team members should share the same emotional values from the design exercise.

The average number of years of experience was 6.6 years. The age of the participants is ranged from 23 to 41 years (average age = 29.4 yrs.)

Apparatus

For the empirical study, ten low-fidelity sketches were collected. They were independently generated by other product designers as to ''Designing Nike vacuum cleaner'' (Authors, 2010). Initially, sixteen sketches were gathered, and the two external experts singled out ten quality sketches, as shown in Figure 3. All sketches were presented in a grey scale with a resolution of 1024×768.

Figure 3

Ten sketches selected for image stimuli (Design brief: Designing Nike vacuum cleaner)

The Self-Assessment Manikin (SAM) scales by [START_REF] Lang | International affective picture system (IAPS):Technical Manual and Affective ratings[END_REF] were employed to reveal both valence (like or dislike feelings) and arousal (intensity of emotions). To establish the battery of ten emotional terms, a list of 20 emotional terms from the Geneva Emotion Research Group (1998) was given to the two independent experts. They chose the most relevant ten terms out of the twenty emotional terms. Regarding the semantic terms, our previous study had identified most relevant semantic descriptors of each design sketch (Authors, 2010), and these were reviewed by the two experts to choose ten most relevant items. Since all participants were native French, the lexical corpus was only set in French. Table 1 enlists the original French terms that were used in the empirical study and the corresponding translated English terms are given in brackets. The twelve participants were then rated each sketch (Figure 1) in five-point Likert scales (from 1 = ''not at all'' to 5 = ''very much'') on each emotional and semantic term.

Table 1

List of emotional terms and semantic descriptors: original French terms (translated English terms) 10 emotional terms 10 semantic descriptors amusé (amused) stimulé (stimulated) apeuré (afraid) enthousiasme (enthusiastic) hésitant (hesitant) mal à l'aise (ill at ease) passionné (passionate), serein (serene) supris (surprised), impressionné (impressed) organique (organic) sympatique (appealing) intelligent (intelligent), léger (light) sportif (sportive) masculine (masculine) moderne (modern), rapide (rapid), dynamique (dynamic), rigide (rigid).

Procedure

Figure 4 illustrates the experimental procedure adopted in the present study. Following the Lang's method (1997), each test began with a preparation slide that lasts 5 seconds. Then, each stimuli slide (i.e., sketches) was presented for 6 seconds. Finally, the participants were asked to rate each sketch in a rating slide. Each cycle of the test continued until all the sketches were assessed.

Figure 4

The experimental procedure used in the study

The one cycle of the test consisted of the following three slides (figure 4):  The Preparation slide was a blank page in order for the participants to stabilise their emotional state before the main stimuli given;  The Stimuli slide held each image stimulus (i.e., sketch) chosen in figure 3;  The Rating slide consisted of three types of questions as described above.

-The Self-Assessment Manikin (SAM) -The list of 10 emotional terms to be rated on 5-point rating scales (see Table 1) -The list of 10 semantic descriptors to be rated on 5-point rating scales (see Table 1)

In order to collect SCR (Skin Conductance Response), the two GSR electrodes were placed on two fingers (the second and third finger) of the left hand as shown in Figure 4. Changes in the skin conductance were collected at 200Hz per second for 11 seconds, i.e., preparation slide (5 sec.) and stimuli slide (6 sec.) The GSR measures were analysed using BIOPAC acquisition unit and BSLPro 3.7.

On the Rating slide, a small thumbnail image was also presented for helping the evaluation process. At the end of the experiment, the participants were asked to rank the top three sketches, as an answer to the question "please rank from 1 to 3 the sketches being the most pertinent to the design brief Nike vacuum cleaner (ranking 1= most pertinent)".

Data gathering and analysis

Principal Component Analysis (PCA) was applied to reduce multidimensional data sets of SAM, 10 emotional and 10 semantic terms. The Galvanic Skin Response (GSR) measures were analysed at peak and troughs of Skin Conductance Response (SCR) during the preparation and stimuli slides. However, thanks to individual differences in SCR latency and rise [START_REF] Dawson | The electrodermal system[END_REF], the original SCR values were normalised, i.e., normalised SCR value = original SCR value/ maximum of SCR value, for the further analysis.

Results

The results are summarised in four subsections: Principal Component Analysis (PCA) of emotional terms, Skin Conductance Response (SCR) measures, PCA of semantic descriptors, and Ranking analysis.

Principal Component Analysis (PCA) of emotional terms

We first analysed the emotional terms used for assessing the sketches by PCA, as shown in figure 5. The contributions of the PCA sphere cumulated to 89.3% in the two first factors (F1 and F2). These principal axes can be interpreted as positive-negative valence and high-low arousal. Higher arousal ratings were observed in sketches N6, N8 and N5. In contrast, sketches N2, N10, and N9 were rated lower arousal loadings. High arousal was related to emotional terms such as 'impressed' and 'surprised'. In terms of valence, both N4 and N2 were positioned rightmost on the valence axis, which were highly linked with terms such as 'enthusiastic', 'passionate', 'stimulated' and 'amused'.

The PCA, in effect, points out that our participants perceived sketches N4, N5, N6 and N8 as positive and intensive. However, the higher valence of N2 was cancelled out by the lower rating in arousal.

Skin conductance response (SCR) measures

Figure 6 depicts the normalised skin conductance response during 11 seconds (5 seconds for the preparation slide and 6 seconds for the stimuli slide as indicated in dotted line). The SCR measures were averaged out for the twelve participants. Like the results above, the SCR changes were higher in N8, N6, N4, and N5 (in order). It implies that they may elicit some higher emotional arousal than the other sketches. On the other hand, the sketches N1, N2, N3, and N10 did not show any remarkable changes between the preparation and the stimuli slide. It is supposed that they elicited some lower emotional arousal, which is also supported by the previous outcomes.

Figure 6

Change in the average normalized skin conductance response (SCR) during 11 seconds

Principal Component Analysis (PCA) of semantic descriptors

The previous two results revealed that sketches N4, N5, N6, N8 would be highly differentiated in terms of the emotional dimension. However, N2 was somewhat mixed, that is it was low arousal but high valence. This perhaps comes from the fact that quality of design should be assessed by the "ideal" vision of "Nike vacuum cleaner", which needs to be analysed in the semantic dimension of the sketches.

That said, we again applied PCA analysis for the semantic descriptors of the ten sketches (figure 7). Given that the cumulative contribution of PCA showed the correlation between semantic descriptors, the contributions were focused on the first two axes F1 (55.2%) and F2 (31.2%), for a total contribution of 86.4% for the two principal factors. There are two groups of semantic descriptors as shown in figure 7. While sketches N4 and N8 have close semantic features related to 'appealing' and 'organic', and sketches N2, N5, and N6 were semantically closed to one after another, as being 'modern', 'rapid', 'dynamic', 'sportive' and 'light', which might well reflect the ideal vision of ''Nike vacuum cleaner''

The results, in effect, figured out that N2 seems to be highly appraised in terms of the ideal vision of Nike vacuum cleaner, and this can be separated out from the analysis of the emotion dimension.

Figure 7

PCA of semantic descriptors of Nike vacuum cleaner sketches: Semantic group 1 (appealing and organic), Semantic group 2 (light, modern, rapid, dynamic, and sportive)

Ranking analysis

Figure 8 shows the sum of the ranking points with weighted ranking values. That is, we assigned points from 1 to 3 according to the rank for example, rank 1 = 3 points, rank 2 = 2 points, and rank 3 = 1 point. Based on this analysis, we observed that the N4 and N2 got the highest score; the N5, N8 and N9 followed. Interestingly, we found that there was a disagreement in their ranking; for instance, most of the designer did not choose the N2 and N4 as their preference simultaneously. This result implies that those sketches were perceived differently by participants and had very distinct features that can express what would be a good ''Nike vacuum cleaner''.

In conjunction with both the emotional and semantic dimension, N2 and N4, N5, N6, and N8 were highly recognised by our participants.

Discussion

Based on the results described above, it seems that using both cognitive and physiological approaches would yield more accurate, simultaneous, and objective results. We further discuss the two hypotheses raised in section 2 and some of the methodological limitations.

5.1

A mixed approach to specify emotion in product images: Cognitivelinguistic and physiological methods (Hypothesis 2)

Concerning Hypothesis 2, our empirical study showed that the combination of the cognitive-linguistic (questionnaire) and physiological method (GSR) allowed us to quantify emotional responses to early sketches. That is, the physiological measures would be quick to detect the arousal of the product image, but it cannot tell what makes this arousal in the product image. In contrast, the questionnaire method would be able to account for what emotional annotation could be associated with that emotional arousal.

Though the mixed approach would be able to detail emotional impacts of a product image given, some of the early sketches were hard to convey the designer's emotional intents through their product images. For instance, sketches N1, N3 and N10 elicited lower emotional arousal in both questionnaire and SCR measures. This means that these sketches were not able to deliver the emotional intents of the designer, if it was what they meant. Hence, it can be seen that the users could not share the same emotional impacts. This mixed approach thus can be easily applied in the early design stage to quickly detect whether or not the designer's emotional intents are conveyed to the user.

A positive correlation between the arousal of Self-Assessment Manikin (SAM) and changes of SCR has already been identified in a study on mobile phone design [START_REF] Mahlke | Consideration of Multiple Components of Emotions, Human-Technology Interaction[END_REF]. Though most of previous studies employed relatively high fidelity prototypes to see the emotional differences (perhaps it might come from colours and so forth), the present study used a low fidelity prototype, which has not been empirically demonstrated before. Indeed, the early sketches do not have many design attributes such as colours or material texture, so it is lesser used in the study of emotion. However, our study contributed that this early detection mechanism is possible with the mixed approach proposed in the whole design cycle.

Incorporating emotional impacts of early product image in the whole design process (Hypothesis 1)

As discussed above, the main contribution of the present study is to show how the mixed approach (SCR and questionnaire) can quickly detect the possible emotional impacts on the users along with early sketches. This is crucial in the design exercises in that this makes the whole design process much agile. Of course, our empirical study also showed that emotional impacts from product images are not the unique determinant of good design. The semantic impacts from product images are also crucial to perceive the product image.

This stance would further justify our mixed approach in conjunction with semantic descriptors. Take the example of the sketches N2 and N4, which were both highly ranked in the ranking analysis, but provoked a distant level of arousal. This emotional difference was understood as their different semantic features based on the results from PCA analysis of semantic descriptors. For instance, the sketch N4 was more appealing and organic, while the sketch N2 was more modern, rapid, dynamic, and sportive. This finding suggests that the emotional differences of product images would be also generated by semantically different product forms. It would help designers to define design specification (sematic features) on account of the different emotional values anticipated. Hence, the Principal Component Analysis (PCA) of emotional responses and Skin Conductance Response (SCR) changes would allow us to identify the different kinds of semantic and emotional responses to early sketches, including both primary and secondary emotions.

In addition, since every design activity is no longer an individual work, the awareness of the emotional impact of design solutions can help the designer herself and other collaborators involved in the early design process to share the emotional impact and communicate better with one after another. Indeed, constantly checking emotional values of the product image as a core part of user testing would be interesting to evolve the design concept and better reflect the user's perception from the product image.

In this study, we initially raised the research question about ''how designers are able to manipulate the emotional impact of their design solutions, and how these solutions are perceived by the user''. Hence, we focused on the early sketches. The results demonstrated that early sketches can sufficiently express designer's own semantic and emotional attributes. In particular, a 'good form' of sketches can elicit a positive feeling (valence) and a higher arousal state. In addition, we proposed a method combining cognitive and physiological approaches, including a web questionnaire and Galvanic Skin Responses (GSR). It enabled us to quickly check the emotional impacts and specify them with secondary emotional terms.

However, unlike what we have assumed, some participants had shown emotional detachment with early sketches, focussing on the semantic meaning of the ideal of the design. Indeed, this is very natural in any design practices, and both emotional and semantic design should work together for the final product image. Therefore, simply a product image with lesser emotional impact should not be undermined, but our claim in this article was to see how emotional impacts can be immersed at earliest in the whole design process.

Another limitation of the current study was not to involve the actual user group. In fact, this was deliberate to present stronger evidences and the designer would be more sensitive to the early sketches. However, to claim the way how the emotional impacts of the designer is transported to the user, it is still necessary to include the representative users, which is planned to carry out in the near future.

Finally, the apparatus used in the empirical study might constrain our interpretations. Though the web-based questionnaire method enabled an instant data collection the designer might be sensitive to sketches on a paper rather than on the screen. Furthermore, all sketches were presented in a single size on the screen (1024×768 resolutions), which might overlook the actual size of the product. For instance, the sketches of ''Nike vacuum cleaner'' involved various types of vacuum cleaners: small hand-held types (N2, N5), robotic types (N4, N7, and N8), an upright type (N3), canister types (N6, N9, and N10), and others (N1). We noticed that relatively big-size vacuum cleaners, such as an upright type and a canister type cannot sufficiently express their own semantic and emotional attributes in a given experimental condition. The results might suggest that smallsize vacuum cleaners, e.g., N2 and N5, have higher semantic and emotional response, in this respect. All these limitations would be fully addressed in a subsequent study.

Figure 5

 5 Figure 5PCA of emotional terms of Nike vacuum cleaner sketches: Positive valence group (enthusiastic, passionate, stimulated, and amused), High arousal (surprised and impressed)

Figure 8

 8 Figure 8 Ranking analysis


About multigrid convergence of some length estimators (extended version)

Loïc Mazo, Étienne Baudrier sgueD niversity of trsourgD gx QHH fd éstien frnt E g IHRIQ E TURIP svvusgrD pexgi Abstract. en interesting property for urve length digitl estimtors is the onvergene towrd the ontinuous length nd the ssoite onverE gene speed when the digitiztion step h tends to HF yn the one hndD it hs een proved tht the lol estimtors do not verify this onvergeneF yn the other hndD h nd wv sed estimtors hve een proved to onverge ut only under some onvexity nd smoothness or polygE onl ssumptionsF sn this frmeD new estimtor lssD the so lled semi-local estimatorsD hs een introdued y hurt et al. in RF por this lssD the pttern size depends on the resolution ut not on the digiE tized funtionF he semiElol estimtor onvergene hs een proved for funtions of lss C 2 with n optiml onvergene speed tht is O(h 1 2 ) without onvexity ssumption @hereD optiml mens with the est estiE mtion prmeter settingAF e semiElol estimtor sulssD tht we ll sparse estimatorsD is exhiited hereF he sprse estimtors re proved to hve the sme onvergene speed s the semiElol estimtors under the weker ssumptionsF fesidesD if the ontinuous funtion tht is digE itized is onveD the sprse estimtors re proved to hve n optiml onvergene speed in hF purthermoreD ssuming sequene of funtions G h : hZ → hZ disretizing given iuliden funtion s h tends to HD sprse length estimtion omputtionl omplexity in the optiml setting is O(h -1

2 )F

Introduction

The ability to perform the measurement of geometric features on digital representations of continuous objects is an important goal in a world becoming more and more digital. We focus in this paper on one classical digital problem: the length estimation. The problem is to estimate the length of a continuous curve S knowing a digitization of S. As information is lost during the digitization step, there is no reliable estimation without a priori knowledge and it is dicult to evaluate the estimator performances. In order to rene the evaluation of the estimators, a property, so called convergence property is desirable: the estimation convergence toward the true length of the curve S when the grid step h tends his work ws supported y the egene xtionle de l eherhe through ontrt exEPHIHEfvexEHPHSEHIF to 0. This property can be viewed as a robustness to digitization grid change.

The local estimators based on a xed pattern size do not satisfy the convergence property [13]. The adaptive estimators based on the Maximal Digital Straight Segment (MDSS) or the Minimum Length Polygon (MLP) satisfy the convergence property under assumptions of convexity, 4-connectivity for closed simple curves (also called Jordan curves) [?]. The semi-local estimators, introduced by Daurat et al [4] for function graphs, veries the convergence property under smoothness assumption but without convexity hypothesis. We present here a subclass of the semi-local estimators, the sparse estimators that only need information on a small part of the function values and keep the convergence property. Moreover they have a convergence speed in h for smooth concave function.

The paper is organized as follows. In Section 2, some necessary notations and conventions are recalled, then existing estimators and their convergence properties are detailed. In Section 3, the sparse estimators are dened, their convergence properties are given in the general case and then in the concave cases (we make a distinction between the concavity of the continuous function and the concavity of the piecewise ane function related to the discretization). An experiment exemplies the results. Section 4 concludes the article and gives directions for future works. Appendix A contains a few technical lemmas. In Appendix B two counterexamples about the concavity are exhibited. Appendix C presents a minimal error on the sparse estimation of the length of a segment of parabola.

Background

Discretization models

In this work, we have restricted ourselves to the digitizations of function graphs. So, let us consider a continuous function g : [a, b] → R (a < b), its graph C(g) = {(x, g(x)) | x ∈ [a, b]} and a positive real number r, the resolution. We assume to have an orthogonal grid in the Euclidean space R 2 whose set of grid points is hZ 2 where h = 1/r is the grid spacing. We use the following notations:

x h is the greatest multiple of h less than or equal to x, {x} h = x -x h . For i ≤ j two integers, [[i, j]] stands for [i, j] ∩ Z. Finally, for any function f dened on an interval, L(f ) denotes the length of C(f ), the graph of f (L(f ) ∈ [0, +∞]).

The common methods to model the digitization of the graph C(g) at the resolution r are closely related to each others.

In this paper, we assume an object boundary quantization (OBQ). This method associates to the graph

C(g) the h-digitization set D O (g, h) = {(kh, g(kh) h ) | k ∈ Z}.
The set D O (g, h) contains the uppermost grid points which lie in the hypograph of g, hence it can be understood as a part of the boundary of a solid object. Provided the slope of g is limited by 1 in modulus,

D O (g, h) is an 8- connected digital curve. Observe that if g is a function of class C 1 such that the set {x ∈ [a, b] | |g (x)| = 1}
is nite, then by symmetries on the graph C(g), it is possible to come down to the case where |g | ≤ 1. So, we assume that g is a Lipschitz function which Lipschitz constant 1. Hence, the set D O (g, h) is 8-connected for any h and the curve C(g) is rectiable (L(g) < +∞). Moreover, the h-digitization set D O (g, h) can be described by its rst point and its Freeman code [9], F(g, h), with the alphabet {0, 1, 7}. For any word ω ∈ {0, 1, 7} k (k ∈ N), we set ω = k 2 + j 2 where j is the number of letters 1 minus the number of letters 7 in the word ω.

Local estimators

Local length estimators (see [10] for a short review) are based on parallel computations of the length of xed size segments of a digital curve. For instance, an 8-connected curve can be split into 1-step segments. For each segment, the computation return 1 whenever the segment is parallel to the axes (Freeman's code is even) and √ 2 when the segment is diagonal (Freeman's code is odd). Then all the results are added to give the curve length estimation.

This kind of local computation is the oldest way to estimate the length of a curve and has been widely used in image analysis. Nevertheless, it has not the convergence property. In [13], the authors introduce a general denition of local length estimation with sliding segments and prove that such computations cannot give a convergent estimator for straight lines whose slope is small (less than the inverse of the size of the sliding segment). In [16], a similar denition of local length estimation is given with disjoint segments. Again, it is shown that the estimator failed to converge for straight lines (with irrational slopes). This behavior is experimentally conrmed in [3] on a test set of ve closed curves. Moreover, the non-convergence is established in [5,17] for almost all parabolas.

Adaptative estimators: DSS and MLP

Adaptive length estimators gather estimators relying on a segmentation of the discrete curve that depends on each point of the curve: a move on a point can change the whole segmentation. Unlike local estimators, it is possible to prove the convergence property of adaptive length estimators under some assumptions. Adaptive length estimators include two families of length estimators, namely the Maximal Digital Straight Segment (MDSS) based length estimators and the Minimal Length Polygon (MLP) based length estimators.

Denition and properties of MDSS can be found in [12,7,3]. Ecient algorithms have been developed for segmenting curves or function graphs into MDSS and to compute their characteristics in a linear time [12,8,7]. The decomposition in MDSS is not unique and depends on the start-point of the segmentation and on the curve travel direction. The convergence property of MDSS estimators has been proved for convex polygons whose MDSS polygonal approximation 1 is also convex [11, Th. 13 and the proof]: given a convex polygon C and a grid spacing 1 hough the digitiztion of onvex set is digitlly onvexD it does not men tht polygonl urve relted to onvex polygonl urve vi wh segmenttion proess is lso onvexF h (below some threshold), the error between the estimated length L est (C, h) and the true length of the polygon L(C) is such that

|L(S) -L est (S, h)| ≤ (2 + √ 2)πh. (1)
Empirical MDSS multigrid convergence has also been tested in [3,6] on smooth nonconvex planar curves. The obtained convergence speed is a O(h) as in the convex polygonal case. Nevertheless it has not been proved under these assumptions. Another way to obtain an estimation of the length of a curve using MDSS is to take the slopes of the MDSSs to estimate the tangent directions and then to compute the length by numerical integration [2,3,14]. The estimation is unique and has been proved to be multigrid convergent for smooth curves (of class C 2 with bounded curvature in [3], of class C 3 with strictly positive curvature in [14]).

The convergence speed is a O(h

3 ) [14] and thus, worse than (1). Let C be a simple closed curve lying in-between two polygonal curves γ 1 and γ 2 . Then there is a unique polygon, the MLP, whose length is minimal between γ 1 and γ 2 . The length of the MLP can be used to estimate the length of the curve C. At least two MLP based length estimators have been described and proved to be multigrid convergent for convex, smooth or polygonal, simple closed curves, the SB-MLP proposed by Sloboda et al. [15] and the AS-MLP, introduced by Asano et al. [1]. For both of them, and for a given grid spacing h, the error between the estimated length L est (C, h) and the true length of the curve

L(C) is a O(h): |L(C) -L est (C, h)| ≤ Ah
where A = 8 for SB-MLP and A ≈ 5.844 for AS-MLP.

On the one hand, as estimators described in this section are adaptive, the convergence theorems are dicult to establish and rely on strong hypotheses. On the other hand, the study of the MDSS in [6] shows that the MDSS size tends to 0 and their discrete length tends toward innity as the grid step tends to 0. Thereby, one could ask whether combining a local estimation with an increasing window size as the resolution grows would give a convergent estimator under more general assumptions and/or with simpler proofs of convergence. The following sections explore this question.

Semi-local length estimators

The notion of semi-local estimator appears in [4]. At a given resolution, a semilocal estimator resembles a local estimator: it can be implemented via a parallel computation, each processor handling a xed size segment of the curve. Nevertheless, in the framework of semi-local estimation, the processors must be aware of the resolution from which the size of the segments depends.

More formally, let g : [a, b] → R be a 1-Lipschitz function2 . Hence, at any resolution, the Freeman's code describing the discretization of g belongs to the set P = n∈N {0, 1, 7} n .

A semi-local estimator is a pair (H, p) where H : ]0, ∞[→ N * gives the relative size of the segments given a grid spacing h and p : P → [0, ∞[ gives the estimated feature (here, the length) associated to a (nite) Freeman's code.

At a given grid spacing h, the Freeman's code describing the digitization of the curve C(g) is segmented in N h codes ω i of length H(h) and a rest ω * ∈ {0, 1, 7} j , j < H(h). Then, the length of the curve C(g) is estimated by

L SL (g, h) = h N h -1 i=0 p(ω i ).
In [4], the authors give a proof of convergence for functions of class C 2 .

Theorem 1 ([4,Prop. 1]). Let (H, p) be a semi-local estimator such that:

1. lim h→0 hH(h) = 0, 2. lim h→0 H(h) = +∞, 3. max p(ω) -ω | ω ∈ {0, 1} k = o(k) as k → +∞.
Then, for any function g ∈ C 2 ([a, b]), the estimation L SL (g, h) converge toward the length of the curve C(g). Furthermore, if the term o(k) in the third hypothesis is a constant and

H(h) = Θ(h -1 2 ), then L(g) -L SL (g, h) = O(h 1 2 ).
H(h) stands for the size of a Freeman's code ω while hH(h) is the real length of the computation step. In the above theorem, the rst hypothesis states that the real length hH(h) tends to 0. If instead of diminishing the grid spacing, we keep it constant while doing a magnication of the curve with a factor 1/h, the second hypothesis states that the size H(h) of a code tends to innity. Finally, and informally speaking, the last hypothesis states that the function p applied to a code ω must return a value close to the diameter 3 of the subset of D O (g, h) associated to ω.

Sparse estimators

In this section, we introduce a new notion, derived from semi-local estimators. Yet, on the contrary to semi-local estimators, we discard the information given by the codes ω i but their extremities. It is as if we had two resolutions, one for the space (the abscissas), one for the calculus (the ordinates).

We have noted earlier that the hypotheses about semi-local estimators in [4] are ambiguous. May be for the same reasons than Daurat et al., we are tempted to do so. Indeed, in all of our proofs, we do not need the "1" in the 1-Lipschitz hypothesis. But from a practical point of view, k-Lipschitz function for k > 1 may give non 8-connected digitization and it does not make a lot of sense to measure the length of a set of disconnected points (though we could dene a discrete curve as the curve, in the usual mathematical sense, of a function from Z to Z). Hence, in the following denition, as in the statement of our theorems, we assume a 1-Lipschitz function while we intentionally forget the "1" in the statements of the lemmas.

Denition

Denition 1. Let H : ]0, +∞[→ N * such that lim h→0 H(h) = +∞ and lim h→0 hH(h) = 0. We say that H is sparsity function. Let g : [a, b] → R be a rectiable function. The H-sparse estimator of the length of the curve C(g) is dened by

L Sp (g, h) = h N h i=0 ω i
where

ω i ∈ {0, 1, 7} H(h) for i = N h , ω N h ∈ {0, 1, 7} j with j ∈ (0, H(h)]
and the concatenation of the words ω i equals F(g, h).

An Illustration is given Figure 1.

(x) = √ 1 + x 2 . Thus, when g is of class C 1 , one has L(g) = b a ϕ • g (t) dt.
The proof of Theorem 2 can be split in three parts. The rst one gives a bound on the error due to the ignorance of the exact abscissas of the curve extremities. The second one evaluates the dierence between the length of the curve C(g h ) and the length of the curve of the piecewise ane function

g m dened on [Ah, Bh] by g m (x k ) = g(x k ) (0 ≤ k ≤ N ).
The third part evaluates the dierence between L(g m ) and the length of the piecewise ane function Lemma 1. For any sparsity function H and any Lipschitz function g, we have

g h m dened on [Ah, Bh] by g h m (x k ) = g m (x k ) h = g(x k ) h (0 ≤ k ≤ N ).
lim h→0 L(g m ) = L(g). Furthermore, L(g) ≤ ϕ(k)(b -a)
where k is a Lipschitz constant for g.

Proof. Since g is k-Lipschitz, the slope of any chord of C(g) is less than k in modulus. It follows that the length of any polyline tting C(g) is bounded by ϕ(k)(b -a). Then, according to Jordan's denition of arc length, we get

L(g) ≤ ϕ(k)(b -a).
For any partition σ of an interval I, we note L σ the length of the polyline associated to the partition. Remember that, from the Jordan's denition of the arc length and the triangle inequality, if σ and σ are two partitions of the interval I such that σ ⊆ σ and f is a rectiable function dened on I, then

L σ ≤ L σ ≤ L(f ). Let ε > 0 and σ 0 = (y i ) n i=0 be a partition of [a, b] such that L(g) -L σ0 < ε/4.
Since H is a sparsity function, there exists h 0 such that

0 < h 0 < ε 8ϕ(k) and ∀u ∈ (0, h 0 ), uH(u) < min ε 2(n -1)(ϕ(k) -1) , min{y i+1 -y i | 0 ≤ i ≤ n -1} Let h ∈ (0, h 0 ). We set σ 0,h = (σ 0 ∪ σ h ) ∩ [Ah, Bh], σ a = (σ 0 ∩ [a, Ah]) ∪ {Ah}
and

σ b = (σ 0 ∩ [Bh, b]) ∪ {Bh}.
Then we dene σ 1 = σ a ∪ σ 0,h ∪ σ b . Firstly, we observe that

L(g) -L σ 0,h ≤ (L(g) -L σ1 ) + (L σ1 -L σ 0,h ) ≤ (L(g) -L σ0 ) + L σa + L σ b ≤ ε 4 + 2ϕ(k)h (for g is k-Lipschitz) ≤ ε 2 (for h < h 0 < ε 8ϕ(k) ) (2)
Then we give an upper bound for Bh), there exists an integer that we note s(i) s.t.

L σ 0,h -L σ h . For any i in [[1, N -1]] such that y i ∈ (Ah,
y i ∈ [x s(i) , x s(i+1) ).
Since m < y i+1 -y i for any y i , y i+1 ∈ (Ah, Bh), one has s(i) < s(i + 1). Let P i , Q i and R i be respectively the points of C(g) with abscissas x s(i) , y i , x s(i)+1 . We have (remember that

x s(i)+1 -x s(i) = m), L σ 0,h -L σ h = yi∈(Ah,Bh) d(P i , Q i ) + d(Q i , R i ) -d(P i , R i ) ≤ yi∈(Ah,Bh) (ϕ(k) -1)m (for g is k-Lispschitz) ≤ (n -1) × (ϕ(k) -1)m ≤ (n -1) × (ϕ(k) -1) ε 2(n -1)(ϕ(k) -1) ≤ ε 2 .
Then,

L(g) -L σ h ≤ (L(g) -L σ 0,h ) + (L σ 0,h -L σ h ) ≤ ε 2 + ε 2 ≤ ε.
We conclude the proof straightforwardly.

From Lemma 1 we derive immediately a bound on the errors due to the loss of the true left and right extremities of the curve C(g).

Corollary 1. For any k-Lipschitz function g, we have

L(g a ) + L(g b ) ≤ 2ϕ(k)h.
When g is dierentiable and its derivative is Lipschitz continuous, the next lemma gives us a bound on the dierence between the length of the curve C(g h ) and the length of the polyline C(g m ).

Lemma 2. If g is dierentiable and its derivative is Lipschitz continuous, we have for any h > 0

L(g h ) -L(g m ) ≤ M (b -a) 2 m (3)
where M is a Lipschitz constant for g .

Proof. Let M be a Lipschitz constant for g . Since the function ϕ is 1-Lipschitz continuous, the function ψ = ϕ • g is M -Lipschitz continuous. Thanks to the mean value theorem, we can nd a sequence

(t k ) N -1 k=0 such that for any k ∈ [[0, N -1]], g (t k ) = g(x k+1 ) -g(x k ) x k+1 -x k .
Then,

L(g h ) -L(g m ) = Bh Ah ψ(t) dt - N -1 k=0 (g(x k+1 ) -g(x k )) 2 + (x k+1 -x k ) 2 = N -1 k=0 x k+1 x k ψ(t) -ψ(t k ) dt ≤ N -1 k=0 M (x k+1 -x k ) 2 2 ≤ M 2 N -1 k=0 (x k+1 -x k )m ≤ M (b -a) 2 m
A trivial maximization shows that the absolute dierence between L(g m ) and L(g h m ) is bounded by 2N h. The next lemma gives us a better bound and provides a relation that will serve as a starting point when we will consider the case of concave functions.

Lemma 3. Let f 1 and f 2 be two piecewise ane functions dened on

[c, d] ⊂ R (d > c) with a common partition having p steps. Suppose that f 1 ≤ f 2 and f 1 -f 2 ∞ ≤ e for some e ∈ R. Then |L(f 1 ) -L(f 2 )| ≤ p e.
Proof. Let σ = (x i ) p i=0 be the common partition for f 1 and f 2 . We write m i for x i+1 -x i and s 1,i , resp. s 2,i , for the slope of f 1 , resp. f 2 , on the interval

[x i , x i+1 ]. L(f 1 ) -L(f 2 ) = p-1 i=0 m i (ϕ(s 1,i ) -ϕ(s 2,i )) = p-1 i=0 s 1,i + s 2,i ϕ(s 1,i ) + ϕ(s 2,i ) m i (s 1,i -s 2,i ).
Note that, for any i < p,

m i (s 1,i -s 2,i ) = f 2 (x i+1 ) -f 1 (x i+1 ) -(f 2 (x i ) -f 1 (x i )).
Thus, as, by hypothesis,

f 1 ≤ f 2 and f 1 -f 2 ∞ ≤ e, we get -e ≤ m i (s 1,i -s 2,i ) ≤ e.
Let ρ : R → R be the function dened by ρ(x) = x ϕ(x) . We observe that, for any

i ∈ [[0, p -1]], min(ρ(s 1,i ), ρ(s 2,i )) ≤ s 1,i + s 2,i ϕ(s 1,i ) + ϕ(s 2,i ) ≤ max(ρ(s 1,i ), ρ(s 2,i )).
Thus, as ρ is continuous, for any i ∈ [[0, p -1]] there exists a real s 0,i between s 1,i and s 2,i such that

ρ(s 0,i ) = s 1,i + s 2,i ϕ(s 1,i ) + ϕ(s 2,i )
.

Thereby, we have

L(f 1 ) -L(f 2 ) = p-1 i=0 ρ(s 0,i ) m i (s 1,i -s 2,i ). (4)
As ρ ∞ = 1 we conclude that

|L(f 1 ) -L(f 2 )| ≤ p-1 i=0 |m i (s 1,i -s 2,i )| ≤ pe.
Thanks to Lemma 1, Lemma 2, and Lemma 3, which is applied to the piecewise ane functions g m and g h m (taking e = h), we can state our rst theorem on the convergence of Sparse length estimators.

Theorem 2. Let H be a sparsity function and g : [a, b] → R a 1-Lipschitz function. Then, the estimator L Sp converges toward the length of the curve C(g). Furthermore, if g is dierentiable and its derivative is Lipschitz continuous , we have

L(g) -L Sp (g, h) ≤ 2 ψ ∞ h + b -a 2 M hH(h) + (b -a) 1 H(h) (5)
where ψ = ϕ • g and M is a Lipschitz constant for g .

The rst term in the right side of Formula 5 is due to the error on the bounds of the curve. Indeed, the two bounds of the curve domain cannot be on the grid at any resolution when h tends to 0. Hence, we have an unavoidable error in O(h). Note that this error does not exist when one computes the length of the boundary of a solid object (for, in this case, the curve is closed). Formula 5 shows two opposite trends for the determination of the sparsity step H(h): the term in O(hH(h)) the discretization error corresponds to the curve sampling error and tends to reduce the step H(h) while the term in O 1 H(h) the quantization error corresponds to the error due to the quantization of the sample points and tends to extend the step. The optimal convergence speed in h

1 2 is then obtained taking H(h) = Θ(h -1
2 ). Thus, only one in about h -1 2 value is needed to make a sparse estimation (which justies the adjective sparse). Then, the complexity in the optimal case is a O(r 1 2 ).

Concave functions

In this section, we assume that the function g is concave on [a, b]. This implies in particular that g admits left and right derivatives, noted g l and g r , at any point of (a, b) and is Lipschitz continuous on any closed subinterval of (a, b). Under this new hypothesis, we can improve the bound on the convergence speed of the estimated length toward the true length of the curve C(g). The functions g m and g h m are those dened in Section 3.2. Lemmas 4 and 5 are improvements of Lemmas 2 and 3 for concave curves. Figure 3 shows some experiments that illustrate the convergence rate obtained with Theorem 3. Lemma 4. If g admits a right derivative in Ah and a left derivative in Bh and if there exists a real k > 0 such that g r (x) -g l (y) ≤ k(y -x) for any x, y such that Ah ≤ x < y ≤ Bh then

L(g h ) -L(g m ) ≤ k(b -a) 4 m 2 . ( 6
)
Proof. We dene the piecewise ane function g

+ m : [Ah, Bh] → R by g + m (x) = min g(x i ) + g r (x i )(x -x i ), g(x i+1 ) + g l (x i+1 )(x -x i+1 )
where [x i , x i+1 ] is the subinterval of the partition σ h that contains x. Note that gm + (x i ) (resp. gm + (x i+1 )) is uniquely dened and is equal to g(x i ) (resp. g(x i+1 )). Since g is concave, g m ≤ g h ≤ g + m so we can apply Lemma 7 on each subinterval of the partition σ h . Together with the hypothesis on the derivatives of g, this leads to the following inequalities.

L(g h ) -L(g m ) ≤ N -1 i=0 (x i+1 -x i ) (g r (x i ) -g l (x i+1 )) 2 4 ≤ N -1 i=0 k 4 (x i+1 -x i ) 3 ≤ k(b -a) 4 m 2 .
Hence, the result holds.

Observe that Inequality (6) corresponds to Inequality (3) that have been improved with m becoming m 2 under concavity assumption.

Lemma 5. Let f 1 and f 2 be two piecewise ane functions dened on [c, d] ⊂ R, (c < d), with a common partition σ having p steps and such that

f 1 ≤ f 2 ≤ f 1 + e for some constant e > 0. If furthermore f 2 is concave, then |L(f 1 ) -L(f 2 )| ≤ p M σ h e 2 + U e.
where M σ h is the harmonic mean of the lengths of σ subintervals and U = max(ϕ (s 2,0 ), ϕ (s 2,0 ) -2ϕ (s 2,p-1 ))) is a constant which depends on the slopes s 2,0 and s 2,p-1 of the rst and the last segments of f 2 .

Proof. Let σ = (x i ) p i=0 be the common partition for f 1 and f 2 . We write m i for x i+1 -x i and s 1,i , resp. s 2,i , for the slope of f 1 , resp. f 2 , on the interval [x i , x i+1 ]. Also, we recall that in Lemma 3 we proved (with weaker hypotheses) that

L(f 1 ) -L(f 2 ) = p-1 i=0 ρ(s 0,i ) m i (s 1,i -s 2,i ) = p-1 i=0 ρ(s 2,i ) m i (s 1,i -s 2,i ) + p-1 i=0 (ρ(s 0,i ) -ρ(s 2,i )) m i (s 1,i -s 2,i )
where s 0,i is between s 1,i and s 2,i and ρ

(x) = x ϕ(x) = x √ 1+x 2 = ϕ (x).
On the one hand, since the function f 2 is concave, the sequence (s 2,i ) p-1 i=0 is decreasing as is the sequence (ρ(s 2,i )) p-1 i=0 (for the function ρ is increasing). Hence, we can apply Lemma 8 with the settings

c i = m i (s 1,i -s 2,i ) = (f 1 (x i+1 ) -f 2 (x i+1 )) -(f 1 (x i ) -f 2 (x i )), u i = ρ(s 2,i ) -ρ(s 2,p-1 ), I = [-e, e].
Then, we get

p-1 i=0 ρ(s 2,i ) m i (s 1,i -s 2,i ) ≤ p-1 i=0 ρ(s 2,i ) -ρ(s 2,p-1 ) m i (s 1,i -s 2,i ) + p-1 i=0 ρ(s 2,p-1 ) m i (s 1,i -s 2,i ) ≤ (ρ(s 2,0 ) -ρ(s 2,p-1 ))e + |ρ(s 2,p-1 )| e ≤ U e.
where U = max(ρ(s 2,0 ), ρ(s 2,0 ) -2ρ(s 2,p-1 )).

On the other hand, the function ρ is 1-Lipschitz, so we have

|ρ(s 0,i ) -ρ(s 2,i )| ≤ |s 0,i -s 2,i | ≤ |s 1,i -s 2,i | . Then p-1 i=0 (ρ(s 0,i ) -ρ(s 2,i )) m i (s 1,i -s 2,i ) ≤ p-1 i=0 m i (s 1,i -s 2,i ) 2 ≤ p-1 i=0 (m i (s 1,i -s 2,i )) 2 m i ≤ pe 2 M σ h .
Eventually, we get

|L(f 1 ) -L(f 2 )| ≤ U e + p M σ h e 2 . ( 7
)
From Lemma 5 and Lemma 4, we derive the following bound on the speed of convergence when the function g is concave.

Theorem 3. Let H be a sparsity function and g : [a, b] → R a concave 1-Lipschitz function of class C 2 . Then, we have

L(g) -L Sp (g, h) = O(h 2 H(h) 2 ) + O 1 H(h) 2 .
Proof. On the one hand, since g is of class C 2 , it satises the hypothesis of Lemma 4. So we have

L(g h ) -L(g m ) ≤ k(b -a) 4 (hH(h)) 2
where k = g ∞ .

On the other hand, Lemma 5 applied with

f 1 = g h m , f 2 = g m , p = N and e = h gives L(g m ) -L(g h m ) ≤ N M σ h h 2 + U h
where M σ h is the harmonic mean of the lengths of σ h subintervals and the constant U can be taken as max(ϕ (a), ϕ (a) -2ϕ (b))). From N ≤ b-a hH(h) + 1 and

N M σ h = (N -1) 1 hH(h) + 1 B h-x N -1 we get L(g m ) -L(g h m ) ≤ b -a H(h) 2 + h 2 + U h.
Thus,

L(g) -L(g h m ) ≤ T h + k(b -a) 4 (hH(h)) 2 + b -a H(h) 2 + h 2 + U h where T = 2 ϕ • g ∞ . Observing that either (hH(h)) 2 ≥ h or 1 H(h) 2 ≥ h, the result holds.
The result given by Theorem 3 is illustrated on Fig. 3 with the natural logarithmic. Compared to Theorem 2, concavity allows squarring each term of the right hand side of the inequality, which does not change the optimal size for H(h) but improves the optimal convergence speed up to h.

H(h)=h^{-1/4} H(h)=h^{-1/3} H(h)=h^{-1/2} H(h)=h^{-2/3} @A L(gm) -L(g h m )
Fig. 3: An illustration of the various convergence rates. We have computed the length of the curve y = ln(x), x ∈ [1, 2], using the sparse estimators dened by

H(h) = h -α where α ∈ { 1 4 , 1 3 , 1 2 , 2
3 }, for the resolutions dened by r = 1.5 n , n ∈ [1, 40]. (a) Discretization error (the errors on the left and the right bounds of the interval have been withdrew). We observe the convergence in O(h 2 H(h) 2 ) which appears in Theorem 3. (b) Quantization error. For α ∈ { 1 4 , 1 3 , 1 2 }, we observe the convergence is a O(1/H(h) 2 ), which appears in Theorem 3. For α = 2 3 , the condition (iii) of Prop. 1 is satised and thus the piecewise ane function g h m is concave. Hence, we can observe that the convergence is a O(h) as deduced from Lemma 6.

Strong concavity

When the function g is concave, the piecewise ane function g m is clearly also concave. Nevertheless, the second piecewise function g h m is not necessary concave. Indeed, we exhibit in Appendix B a function g that is concave and for which the function g h m is nonconcave for any h below some threshold. This section gives some sucient conditions for g h m to be also concave and studies the consequences on the convergence speed of such an assumption. Proposition 1. Let H be a sparsity function and g : [a, b] → R a concave function of class C 2 . If one of the following condition holds, then there exists h 0 > 0 such that, for any h < h 0 , the piecewise ane function

g h m is concave on [Ah, (A + N 0 H(h))h] where A = a h and N 0 = b-a hH(h) . (i) H(h) = h -1 2 and max(g ) < -1. (ii) H(h) = h -1 2 and g(x) = ax 2 + bx + c where |a| ≥ 1 2 . (iii) hH(h) 2 → +∞ as h → 0 and max(g ) < 0.
Proof. The piecewise ane function

g h m is concave on [Ah, (A + N 0 H(h))h] i g h m (x i + m) + g h m (x i -m) -2g h m (x i ) ≤ 0 for any i ∈ [[1, N 0 -1]]. Let n be an integer in [[1, N 0 -1]].
We make Taylor expansions of g at x n to the second order.

g(x n + m) + g(x n -m) = 2g(x n ) + m 2 g (x n ) + o(m 2 ) Then, g h m (x n + m) + g h m (x n -m) -2g h m (x n ) = g(x n + m) + g(x n -m) -2g(x n ) + E h where |E| < 2 = m 2 g (x n ) + E h + o(m 2 ).
Thus, setting M = max(g ),

g h m (x n + m) + g h m (x n -m) -2g h m (x n ) h < -hH(h) 2 M + 2 + o(hH(h) 2 ). (8)
Thanks to Inequality (8), noting that its left hand side is an integer (also that when g is a 2-th order polynomial the term o(hH(h) 2 ) vanishes), the reader can easily check the three parts of the proposition.

The following lemma is an improvement of Lemma 5 for two concave piecewise ane functions. Lemma 6. Let f 1 and f 2 be two concave piecewise ane functions dened on

[c, d] ⊂ R such that f 1 ≤ f 2 ≤ f 1 + e
for some e > 0 and f 1 , f 2 have the same monotonicity on each subinterval on which they are ane. Then

|L(f 1 ) -L(f 2 )| ≤ U e.
where U is a constant dened as follows. Given a common partition σ = (x i ) p i=0 of the interval [c, d] related to the piecewise ane functions f 1 and f 2 , let s 1,0 , s 1,p-1 , resp. s 2,0 , s 2,p-1 , be the slopes of the rst and last segments of C(f 1 ), resp. C(f 2 ). Now, let α = s1,0+s2,0 ϕ(s1,0)+ϕ(s2,0) and β = s1,p-1+s2,p-1 ϕ(s1,p-1)+ϕ(s2,p-1) . Then,

U = max(α, α -2β).
Proof. Let σ = (x i ) p i=0 be a common partition for f 1 and f 2 . We write m i for x i+1 -x i and s 1,i , resp. s 2,i , for the slope of f 1 , resp. f 2 , on the interval [x i , x i+1 ]. Since f 1 and f 2 are concave, the sequences (s 1,i ) and (s 2,j ) are monotonically non-increasing. Furthermore, since f 1 and f 2 have the same monotonicity, s 1,i and s 2,i have the same sign for any i ∈ [[0, p -1]]. In Lemma 3 we proved (with weaker hypotheses) that

L(f 1 ) -L(f 2 ) = p-1 i=0 ρ(s 0,i ) m i (s 1,i -s 2,i ) (9) where ρ(x) = x ϕ(x) = x √ 1+x 2 and ρ(s 0,i ) = s1,i+s2,i ϕ(s1,i)+ϕ(s2,i) .
Firstly, we prove that the sequence (ρ(s 0,i )) is also monotonically non-increasing. Let i < j be two integers in [[0, p -1]].

ρ(s 0,i ) ≥ ρ(s 0,j ) ⇐⇒ s 1,i + s 2,i ϕ(s 1,i ) + ϕ(s 2,i ) ≥ s 1,j + s 2,j ϕ(s 1,j ) + ϕ(s 2,j ) ⇐⇒ s 1,i ϕ(s 1,j ) -s 1,j ϕ(s 1,i ) + s 2,i ϕ(s 2,j ) -s 2,j ϕ(s 2,i ) + s 1,i ϕ(s 2,j ) + s 2,i ϕ(s 1,j ) ≥ s 1,j ϕ(s 2,i ) + s 2,j ϕ(s 1,i ) ⇐⇒ ϕ(s 1,i )ϕ(s 1,j ) ρ(s 1,i ) -ρ(s 1,j ) + ϕ(s 2,i )ϕ(s 2,j ) ρ(s 2,i ) -ρ(s 2,j ) + s 1,i ϕ(s 2,j ) + s 2,i ϕ(s 1,j ) ≥ s 1,j ϕ(s 2,i ) + s 2,j ϕ(s 1,i )
The terms ρ(s 1,i ) -ρ(s 1,j ) and ρ(s 2,i ) -ρ(s 2,j ) are non-negative because (s 1,i ) and (s 2,j ) are monotonically non-increasing (and the function ρ is increasing). Hence,

ρ(s 0,i ) ≥ ρ(s 0,j ) ⇐ s 1,i ϕ(s 2,j ) + s 2,i ϕ(s 1,j ) ≥ s 1,j ϕ(s 2,i ) + s 2,j ϕ(s 1,i ) (10)
If s 1,j ≥ 0, and thus s 2,j , s 1,i , s 2,i ≥ 0, we can square the two terms of the inequality in the right hand side of ( 10)

ρ(s 0,i ) ≥ ρ(s 0,j ) ⇐ s 2 1,i (1 + s 2 2,j ) + s 2 2,i (1 + s 2 1,j ) + 2s 1,i s 2,i ϕ(s 1,j )ϕ(s 2,j ) ≥ s 2 1,j (1 + s 2 2,i ) + s 2 2,j (1 + s 2 1,i ) + 2s 1,j s 2,j ϕ(s 1,i )ϕ(s 2,i ) ⇐ s 2 1,i + s 2 2,i + 2s 1,i s 2,i ϕ(s 1,j )ϕ(s 2,j ) ≥ s 2 1,j + s 2 2,j + 2s 1,j s 2,j ϕ(s 1,i )ϕ(s 2,i ) ⇐ s 2 1,i + s 2 2,i + A ρ(s 1,i )ρ(s 2,i ) ≥ s 2 1,j + s 2 2,j + A ρ(s 1,j )ρ(s 2,j ) where A = 2ϕ(s 1,i )ϕ(s 2,i )ϕ(s 1,j )ϕ(s 2,j ) is clearly non-negative.
Since the function ρ is monotonically non-decreasing and odd, it is plain that the last inequality is true under all our assumptions.

The case where s 1,i ≤ 0, and thus s 2,i , s 1,j , s 2,j ≤ 0 is similar. The last case, where s 1,i ≥ 0 ≥ s 1,j , and thus s 2,i ≥ 0 ≥ s 2,j , is obvious. Thereby, we have proved that the sequence (ρ(s 0,i )) is monotonically non-decreasing. Now, from Lemma 8, taking

c i = m i (s 1,i -s 2,i ) = (f 1 (x i+1 ) -f 2 (x i+1 )) -(f 1 (x i ) -f 2 (x i )), u i = ρ(s 0,i ) -ρ(s 0,p-1 ) and I = [-e, e],
we derive from (9) that

|L(f 1 ) -L(f 2 )| ≤ (ρ(s 0,0 ) -ρ(s 0,p-1 ))e + |ρ(s 0,p-1 )| p-1 i=0 m i (s 1,i -s 2,i ) ≤ (ρ(s 0,0 ) -ρ(s 0,p-1 ))e + |ρ(s 0,p-1 )| e ≤ U e
where U = max(ρ(s 0,0 ), ρ(s 0,0 ) -2ρ(s 0,p-1 )).

Corollary 2. Let H be a sparsity function and g :

[a, b] → R a concave 1- Lipschitz function of class C 2 . If, for some h 0 > 0, the function g h m is concave on [Ah, (A + N 0 H(h))h] where A = a h and N 0 = b-a hH(h)
for any h < h 0 , then we have

L(g) -L Sp (g, h) = O(h 2 H(h) 2 ) + O(h).
Proof. From Corollary 1, we have

L(g a ) + L(g b ) ≤ 2 ϕ • g ∞ h. ( 11
)
From Lemma 4, we get

L(g h ) -L(g m ) ≤ (b -a) g ∞ 4 (hH(h)) 2 . ( 12
)
Let N 0 = b-a hH(h) . We write g m|1 and g m|2 , resp. g h m|1 and g h m|2 for the restrictions of the function g m , resp. g h m , to the intervals [A, (A + N 0 H(h))h] and

[(A + N 0 H(h))h, B h].
The functions g m|1 and g h m|1 are piecewise ane with subintervals of width m = hH(h) while, if N 0 = N , the functions g m|2 and g h m|2 are ane on an interval of width αh where α is an integer in

[1, m). It follows from Lemma 6 that L(g m|1 ) -L(g h m|1 ) ≤ U h (13)
where U is bounded by max(ϕ (g (a) + 1), ϕ (g (a) + 1) -2ϕ (g (b) -1)) which does not depend on h. Indeed, with the notations of Lemma 6, U = max(α, α -2β) where α = s1,0+s2,0 ϕ(s1,0)+ϕ(s2,0) lies between s1,0 ϕ(s1,0) and s2,0 ϕ(s2,0) , that is between ϕ (s 1,0 ) and ϕ (s 2,0 ). On the one hand ϕ (s 1,0 ) is lower than ϕ (g (a)) for ϕ is monotonically increasing and g m is concave. On the other hand, it can easily be proved that s 2,0 ≤ s 1,0 + 1 H(h) ≤ g (a) + 1. Hence, α ≤ ϕ (g (a) + 1).

Alike, we have

β ≥ ϕ (g (b) -1)
and thus

U ≤ max(ϕ (g (a) + 1), ϕ (g (a) + 1) -2ϕ (g (b) -1)).
Finally, we derive immediately from Lemma 3 that

L(g m|2 ) -L(g h m|2 ) ≤ h. (14)
As

L(g) = L(g a ) + L(g h ) + L(g b ),
L(g m ) = L(g m|1 ) + L(g m|2 ) and

L Sp (g, h) = L(g h m ) = L(g h m|1 ) + L(g h m|2 ),
the result follows readily from eqs. ( 11) to ( 14).

From Corollary 2, it follows that, to speed up the convergence, we shall take the smallest sparsity step H(h) provided the hypothesis about the concavity is satised. According to Proposition 1, this should lead us to choose the function H such that H dominates h -1 2 as h → 0. For instance, we can take

H(h) = h -1 2 -ε
where ε > 0 and ε ≈ 0. Then, the convergence speed is h 1-2ε . Note that h is a minimal error bound that cannot be improved in the general case since for the function g dened by g

(x) = ( 19 48 ) 2 -x 2 , x ∈ [ 1 16 , 19 48 ], we have shown that L(g) -L Sp (g, h) ≥ 0.06h (see Appendix C).

Conclusion

In this article, we have studied some convergence properties of a class of semilocal length estimators in the concave and the general cases. These estimators need few information about the curve: the proportion of points of the curve used for the computation tends to 0 as the resolution tends toward innity. That is why we propose to call them sparse estimators. In a future work, we plan to extend our estimators to the nD Euclidean space to compute k-volumes, k < n.

We have also to study how the material presented in this article behave with Jordan curves obtained as boundary of solid objects through various discretization schemes. Furthermore, the denition of the sparse estimators relies on Jordan's denition for curve length. It would be interesting to keep the main idea from these estimators while relying on the more general denition of Minkowski (as in [2]). This could be more realistic in the framework of multigrid convergence, since physic objects cannot be considered as smooth (nor convex, etc. ) at any resolution. Another extension of this work is to check whether the proofs of convergence obtained for sparse estimators can help to obtain new proofs for the convergence of adaptative length estimators as the MDSS. This could lead to the denition of a larger class of geometric feature estimators including sparse estimators and MDSS. Eventually, there is a need to nd how to estimate the resolution of a given curve.

A Technical lemmas Lemma 7. Let ABC be a triangle in R 2 (A = C) and Γ ⊂ R 2 be a rectiable curve from A to C included in the triangle ABC such that the set between the segment AC and the curve Γ is convex. Let B be an orthonormal basis of R 2 such that, in the coordinate system (A, B), the abscissa of C, noted m, is positive and the abscissa of B strictly lies between 0 and m. Let α, β, γ be the slopes, in the basis B, of the line from B to C, resp. from C to A, resp. from A to B. Then, the length of Γ , L Γ , is such that Proof. Since the set bounded by the segment AC and the curve Γ is convex and included in the triangle ABC, its perimeter is less than, or equal to, the perimeter of the triangle ABC (see [18,Part XII]). Thus, AC ≤ L Γ ≤ AB +BC. Since x B , the abscissa of the point B in the coordinate system (A, B) veries 0 x B < m, β lies between α and γ. Then there exists a real k ∈ [0, 1] such that β = kγ + (1 -k)α. It can be seen that the vectors AB, BC and AC have coordinates (km, kmγ), ((1 -k)m, (1 -k)mα) and (m, mβ). Thus,

AC ≤ L Γ ≤ AC + m (γ -α) 2 4 .
AB + BC -AC = m kϕ(γ) + (1 -k)ϕ(α) -ϕ(β) = m k ϕ(γ) -ϕ(kγ + (1 -k)α) + (1 -k) ϕ(α) -ϕ(kγ + (1 -k)α) = mk(1 -k)(γ -α) ϕ (ξ 1 ) -ϕ (ξ 2 ) = mk(1 -k)(γ -α)(ξ 1 -ξ 2 )ϕ (ξ).
where ξ 1 , ξ 2 , ξ lie between α and γ.

Hence,

AB + BC -AC ≤ m(γ -α) 2 4 ( 15
)
for ϕ ∞ = 1. So, the result holds.

Remark 1. We could improve the previous result by a factor 2 since it appears from the above calculus that AB+BC-AC m is the 'vertical distance' between the function ϕ and one of its chord (see Fig. 5) and is thus maximal when the chord is 'horizontal'. Lemma 8. Let (u n ) n∈N a monotonically non-increasing sequence of real non negative numbers and (c n ) n∈N a sequence of reals in an interval I such that j i=0 c i ∈ I for any integer j. Then, j i=0 c i u i ∈ u 0 I for any integer j. Proof. If u 0 = 0, then u n = 0 for any n and the result is obvious. From now, we assume u 0 > 0. Let n ∈ N and S = n i=0 c i u i . We set C j = j i=0 c i for any j ≤ n, p i = ui-ui+1 u0 for any i ≤ n -1 and p n = un u0 . The reals p i are all non-negative and their sum equals 1. We can easily check that

S = n-1 i=0 i j=0 c j (u i -u i+1 ) + n j=0 c j u n = u 0 n i=0 p i C i
The last equality above shows that the real 1 u0 S is the barycenter with nonnegative weights of numbers in the interval I. Thus, the result holds.

B Strong concavity: counterexamples

In this appendix, we show that a piecewise ane function can be concave and its digitization, beyond some resolution, never concave (that is, the piecewise ane function g h m dened in Sec. 3.2 is not concave for grid spacing h below some threshold). The rst counterexample uses a local estimator and the second one uses a sparse estimator. Both counterexamples rely on the following theorem proved in [17] (in fact, an extended version of the theorem is needed for the second counterexample). This theorem asserts that, given a function x → ax 2 + bx + c, the distribution in [0, h] of the values of the expression {a(kh) 2 + b(kh) + c} h , k ∈ N, which are the errors resulting from the quantization, tends toward the equidistribution. Theorem 4 ([17,Lemma 2 and Prop. 3]). Let a, b ∈ R, a < b. Let g : [a, b] → R be a polynomial function of degree 2. Then, for all interval I ⊆ [0, 1],

lim h→0 card{x ∈ hN ∩ [a, b] | g(x) mod h ∈ hI} card(hN ∩ [a, b]) = µ(I)
where µ(I) is the classical length of I.

B.1 Counterexample #1: local estimation

We digitize the parabola associated to the function g(x) = 2x -x 2 , x ∈ [0, 1] and we split this parabola into segments of size 5h. Thanks to Theorem 4, we prove that, for each grid spacing h below some threshold, we can choose an integer p such that the nite dierence g h m ((p + 5)h) -g h m (ph) is less than or equal to the grid spacing h while the nite dierence g h m ((p + 10)h) -g h m ((p + 5)h) is greater than or equal to twice the grid spacing h. Thus, the function g h m is not concave on [0, 1].

Detailed calculus

According to Theorem 4, it exists a real h 0 > 0 such that, for any h ∈ (0, h 0 ), one has

card n ∈ [[
g h m ((n 0 + 5)h) -g h m (n 0 h) < g((n 0 + 5)h) -(g(n 0 h) - 7 12 h) < 17 60 × 5h + 7 12 h < 2h.
As the term in the left hand side of the above inequalities is a multiple of h, we get g h m ((n 0 + 5)h) -g h m (n 0 h) ≤ h. In the same way, we obtain

g h m ((n 0 + 10)h) -g h m (n 0 h) > g((n 0 + 10)h) -h -(g(n 0 h) - 4 12 ) > 16 60 × 10h - 2 3 h > 2h.
Thus, g h m ((n 0 + 10)h) -g h m (n 0 h) ≥ 3h. Finally, we have

g h m ((n 0 + 10)h) -g h m (n 0 h) > 2 g h m ((n 0 + 5)h) -g h m (n 0 h) .
That is, the function g h m is strictly convex on [n 0 h, (n 0 + 10)h].

B.2 Counterexample #2 : sparse estimation

For the second counterexample, we discretize the parabola y = g(x) = 1 50 (2xx2 ), x ∈ [0, 1] and we use segments of size H(h) = h -1 2 . Substantially, this second counterexample is similar to the previous one though it requires the following extended version of Theorem 4.

Proposition 2. Let a, b ∈ R, a < b, and g : [a, b] → R a quadratic polynomial function. Let (J h ) h>0 a family of integer intervals such that hJ h ⊆ [a, b] for any h > 0 and lim h→0 card J h = +∞. Then, for any interval I ⊆ [0, 1], one has:

lim h→0 card{n ∈ J h | g(nh) mod h ∈ hI} card J h = µ(I)
Below, we present the sketch of the proof of Proposition 2. The formal proof will be given in a future work. Lemma 10. Let g : [a, b] → R be a quadratic polynomial function and (J r ) r>0 be an integer interval family such that ∀r > 0, rJ r ⊆ [a, b] and lim r→0 card J r = +∞. If for any real c = 0 is is true that lim r→0 L r,k = 0, then

Sketch of the proof

lim r→0 card{n ∈ J r | g(nr) mod r ∈ rI} card J r = µ(I)
The result follows immediatly.

Counterexample

We take g

(x) = 1 50 (2x -x 2 ), x ∈ [0, 1] and H(h) = h -1 2 . We set J h = 1 h - c √ h , 1 h - d √ h where c = 35, d = c -1
2 . The family of integer intervals (J h ) satises the hypotheses of Proposition 2: hJ h ⊂ [0, 1] (for small enough h) and card J r → ∞ as r → 0. Hence, there exists h 0 such that

∀h < h 0 , ∃n h ∈ {n ∈ J h | {g(nh)} h ∈ [αh, β h) } where α = 2 5 and β = 1 2 . Let h < h 0 and n h ∈ J h such that {g(nh)} h ∈ [αh, β h). The constants c and d are such that [n h h, n h h + 2m] ⊆ [1 -c √ h, 1 -(d -2) √ h], (d -2) √ h ≤ 25g (x) ≤ c √ h on [1 -c √ h, 1 -(d -2) √ h].
We can now compare the growth of g h m on [n h h, n h h+m] and

[n h h, n h h+2m]. g h m (n h h + m) -g h m (n h h) ≤ g(n h h + m) -g(n h h) + {g(n h h)} h < c 25 √ h × m + β h < 7 5 h -1 2 h -1 2 + 1 2 h < 2h (if h ≤ 1). Thus, g h m (n h h + m) -g h m (n h h) ≤ h. Alike, we have g h m (n h h + 2m) -g h m (n h h) ≥ g(n h h + 2m) -g(n h h) + {g(n h h)} h -{g(n h h + 2m)} h > d-2 25 √ h × 2m + αh -h > 2(d-2) 25 h -1 2 h -1 2 - 3 5 h > 2h.
Thus,

g h m (n h h + 2m) -g h m (n h h) ≥ 3h. Finally, we have proved that g h m (n h h + 2m) -g h m (n h h) > 2 g h m (n h h + m) -g h m (n h h) .
This last inequality shows that the function g h m is convex on [n h h, n h h + 2α]. Thereby, for any h < h 0 , there exists an interval [nh, nh + 2m] ⊂ [0, 1] on which the function g h m is convex.

C Inferior bound for the method error in the concave case

We give an inferior bound on the dierence between the true length L(g) of the parabola y = g(x) = ( 19 48 ) 2 -x 2 for x ∈ [ 1 16 , 19 48 ] and the length L Sp (g, h), obtained with the sparse estimator dened by the sparsity function H(h) = h -1 2 . Let g m and g h m be the piecewise ane functions dened in Section 3.2. Then the lengths of their curves satisfy L(g h m ) + 0.05h ≤ L(g m ) ≤ L(g) for any h = (12(8p + 1)) -2 where p ∈ N. Moreover, the bounds of the interval [ 1 16 , 19 48 ] are multiple of h. Hence, there is no error due to the bounds. Eventually, for any p ∈ N and h = (12(8p + 1)) -2 , we get L(g) -L Sp (g, h) ≥ 0.06h.

Detailed calculus

Let h = 1 144(8p+1) 2 (p ∈ N) and H(h) = h -1 2 = 12(8p + 1).
Thereby, here we have m = hH(h) = Furthermore, we have g(x 0 ) ≡ 0 (mod h)

and g(x i ) ≡ 1 2 ih (mod h) (16) We set c = h 2 = m 2 2 , z i = 1 2 (x i + x i+1
) and y i = g(x i+1 ) -g(x i ) = -2m z i . Then, from ( 16 By summing,

L(g m )-L(g h m ) ≥ m 2 16p+1 i=0 z 2i+1 1 + 4z 2i+1 2 - z 2i √ 1 + 4z 2i 2 - m 3 8 32p+3 i=0 1 √ 1 + 4z i 2 .
Since the function f 1 (x) =

x √ 1+4x 2 is monotonically increasing and concave, one has

16p+1 i=0 (f 1 (z 2i+1 ) -f 1 (z 2i )) ≥ 1 2 32p+3 i=0 (f 1 (z i+1 ) -f 1 (z i )) ≥ 1 2 (f 1 (z 32p+4 ) -f 1 (z 0 ))
Moreover, the function f 2 (x) = ) .

Since m ≤ 1 12 for any p ∈ N, we obtain

L(g m ) -L(g h m ) > 0.066m 2 .
Eventually, for any h = 1 (12(8p+3)) 2 , we have shown that L(g) ≥ L(g m ) ≥ L(g h m ) + 0.06h.

IF esnoD FD uwmurD FD uletteD FD yoktD uFX winimumElength polygons in pproximtion susgesF snX erelliD gFD gordellD vFD fjD qF @edsFA isul porm PHHID veture xotes in gomputer ieneD volF PHSWD ppF IHQ!IIPF pringer ferlin reidelerg @PHHIA PF goeurjollyD hFX elgorithmique et géométrie disrète pour l rtéristion des oures et des surfesF hFhF thesisD niversité vyon P @PHHPA QF goeurjollyD hFD uletteD FX e omprtive evlution of length estimtors of digitl urvesF siii rnsF ttern enlF whF sntellF PT@PAD PSP!PSU @PHHRA RF hurtD eFD jineD wFD ououiD wFX ves estimteurs semiEloux de périmètreF ehF repFD vss gxD w UHHSD niversité de trsourg @PHIIAD http:// hal.inria.fr/hal-00576881 SF hurtD eFD jineD wFD ououiD wFX tterns in disretized prols nd length estimtionF snX frlekD FD eutenuerD gFD rovençlD F @edsFA hqgsF veture xotes in gomputer ieneD volF SVIHD ppF QUQ!QVRF pringer ferlin reidelerg @PHHWA TF he ieillevilleD pFD vhudD tFyFD peshetD pFX gonvex digitl polygonsD mximl digitl stright segments nd onvergene of disrete geometri estimtorsF tournl of wthemtil smging nd ision PU@PAD IQW!IST @PHHUA UF heledEennessonD sFD eveillèsD tFFX e liner lgorithm for segmenttion of digiE tl urvesF snterntionl tournl of ttern eognition nd erti(il sntelligene HW@HRAD TQS!TTP @IWWSA VF horstD vFD meuldersD eFFX hisrete stright line segmentsX prmetersD primiE tives nd propertiesF ision geometryX proeedings of n ew speil session held ytoer PHEPID IWVWDt rookenD xew tersey IIWD RS!TP @IWWIA WF preemnD rFX yn the enoding of ritrry geometri on(gurtionsF iletroni gomputersD si rnstions on igEIH@PAD PTH!PTV @IWTIA IHF uletteD FD osenfeldD eFX higitl qeometryF worgn uufmn @PHHRA IIF uletteD FD D uni¢D tFX wultigrid onvergene of lulted fetures in imge nlE ysisF tournl of wthemtil smging nd ision IQ@QAD IUQ!IWI @PHHHA IPF uovlevskyD FX xew de(nition nd fst reognition of digitl stright segments nd rsF snX ttern eognitionD IWWHF roeedingsFD IHth snterntionl gonferene onF volF iiD ppF QI!QR volFP @IWWHA IQF uulkrniD FFD witterD FuFD ihrdsonD FtFD sitsiklisD tFxFX vol versus nonE lol omputtion of length of digitized urvesF siii rnsF ttern enlF whF sntellF IT@UAD UII!UIV @IWWRA IRF vhudD tFyFX ispes nonEeulidiens et nlyse d9imge X modèles déformles riemnniens et disretsD topologie et géométrie disrèteF rilittion à diriger des reherhesD niversité de fordeux I @héemre PHHTA ISF loodD pFD tkoD fFD toerD tFX yn pproximtion of plnr oneEdimensionl ontinuF edvnes in higitl nd gomputtionl qeometry ppF IIQ!ITH @IWWVA ITF jineD wFD hurtD eFX yn lol de(nitions of length of digitl urvesF snX xyströmD sFD di fjD qFFD venssonD F @edsFA hqgsF veture xotes in gomputer ieneD volF PVVTD ppF IIR!IPQF pringer ferlin reidelerg @PHHQA IUF jineD wFD hurtD eFX tterns for multigrid equidistriuted funtionsX eppliE tion to generl prols nd length estimtionF heoretil gomputer iene RIP@QTAD RVPR ! RVRH @PHIIA IVF lentineD pFeFX gonvex setsF wqrwErill @IWTRA

Fig. 1 :

 1 Fig. 1: Sparse estimation at two resolutions

  Figure 2 shows the three functions g, g m , g h m on an interval [x k , x k+1 ].

Fig. 2 :

 2 Fig.2: The two main parts of the estimation error: the curve g (in green, solid) to its chord g m (in magenta, dotted-dashed) then the curve chord to the chord g h m (in blue, dashed) of the digitized curve D O (g, h) (black points).

FigFig. 4 :

 4 Fig.4illustrates the conguration studied in Lemma 7.

Fig. 5 :

 5 Fig. 5: = AB + BC -AC.

  1. In [17, Lemma 2], we take k = 0 (we does not need other values) and we change the denition of A r and B r to [[A r , B r ]] = J r (thus, N r = card J r ). From rJ r ⊆ [a, b], the inequalities obtained under the hypothesis cα > 0 (instead of c > 0) become : -2cαrN r ≤ 2cα(b -a + r) ; -|θ| = |2cαr(A r + k) + cβ| ≤ 2cα |b| + 2cαr |k| + |cβ|. The remainder of the proof of [17, Lemma 2] is unchanged. Thus, we get a new version of the lemma (restricted to the case k = 0). Lemma 9. For any quadratic polynomial function g : [a, b] → R, for any real c = 0 and for any integer interval family (J r ) r>0 such that ∀r > 0, rJ r ⊆ [a, b] and lim r→0 card J r = +∞, one has

  For any i ∈ [[0, N ]], x i = 1 16 + i m = x 0 + i m (in particular, the last interval of the sparse estimation have size m).

  ), we deriveL(g m ) -L(g h m ) = 16p+1 i=0 m 2 + y 2i 2 + m 2 + y 2i+1 2 -m 2 + (y 2i -c) 2 + m 2 + (y 2i+1 + c) 2On the one handm 2 + y 2i 2 -m 2 + (y 2i -c) 2 = -On the other hand m 2 + y 2i+1 2 -m 2 + (y 2i+1 + c)

sn RD the hypothesis on g is not lerF yn the one hndD the ode F(g, h) is supposed to hve {0, 1} s lphetF yn the other hndD RD rop I does not retin ny hypothesis on g ut its lss of di'erentiilityF sndeedD in the proofD the derivtive of g needs not e positive nor limited y IF

[17, Property 3] does not depend upon the denition of A r and B r . So, we can state the following new version of the property.