R Laurent
email: remy.laurent@pu-pm.univ-fcomte.fr.

M Salomon

J Henriet

M Sauget

R Gschwind

L Makovicka

Dr Laurent

Data Processing using Artificial Neural Networks to Improve the Simulation of Lung Motion

Keywords: Respiratory motion prediction, Computer simulation, 4D-CT, Data processing

To optimize the delivery in lung radiation therapy, a better understanding of the tumor motion is required. On the one hand to have a better tumor-targeting efficiency, and on the other hand to avoid as much as possible normal tissues. The 4D-CT allows to quantify tumor motion, but due to artifacts it introduces biases and errors in tumor localization. Despite of this disadvantage, we propose a method to simulate lung motion based on data provided by the 4D-CT for several patients. To reduce uncertainties introduced by the 4D-CT scan, we conveniently treated data using artificial neural networks. More precisely, our approach consists in a data augmentation technique. The data resulting from this processing step are then used to build a training set for another artificial neural network that learns the lung motion. To improve the learning accuracy, we have studied the number of phases required to precisely describe the displacement of each point. Thus, from 1118 points scattered across 5 patients and defined over 8 or 10 phases, we obtained 5800 points of 50 phases. After training, the network is used to compute the positions of 40 points from five other patients on 10 phases. These points allow to quantify the prediction performance. In comparison with the original data, the ones issued from our treatment process provide a significant increase of the prediction accuracy: an average improvement of 16% can be observed. The motion computed for several points by the neural network that has learnt the lung one exhibits an hysteresis near the one given by the 4D-CT, with an error smaller than 1 mm in the cranio-caudal axis.

INTRODUCTION

The aim of radiation therapy is to provide the maximum radiation dose to a tumor, while delivering the lowest dose possible to the surrounding normal tissues. In case of lung tumors it is crucial to be able to track them precisely, otherwise the respiratory motion will be a major problem for the treatment process. A modality that allows to follow the position of lung tumors is 4D-CT imaging, nevertheless motion artifacts and other biases can degrade the acquired data. Today, 4D-CT has been adopted for routine clinical use; therefore, we propose a method based on these data. Note that we do not want to find the locations given by the 4D-CT, since the motion artifacts would be still present, but we rather want a smooth realistic and regular motion simulation.

The fourth dimension in a scanner enables temporal synchronization of respiratory acquisition. The quality of the resulting images depends mainly on two parameters: the period of the breathing for a patient, which can greatly vary due to the stressful situation; the rotation time of the tube that can range from 0.5 to 1 second, leading to kinetic blur. Usually, for each table position, the respiratory cycle is represented in 10 uniformly distributed "phases", each phase corresponding to an instant in the cycle. These images are then combined to produce the final scan, more precisely the different images corresponding to a same phase are concatenated together to form a single image. Thus, several respiratory cycles are needed and the slices corresponding to a 3D image at a specific phase might not belong to it. The phase values range from 0% to 100%, where 0% and 50% represent respectively the maximum exhalation and inspiration. Furthermore, since the respiratory cycle is periodic, 0% and 100% define the same phase.

Figure 1 shows the respiratory signal measured by RPM system (Varian) during the acquisition of a 4D-CT scan. The moments of data acquisition (beam on), the variations in the breathing period, and the phases calculated by RPM software are determined using the RPM respiration data file. The successive upper dots on the respiratory signal identify the 0% phases, while the lower ones correspond to the 50% phases. The figure also describes how the image for the 50% phase is built by concatenation of images obtained on several respiratory periods. The analysis of Fig. 1 shows that the patient's ability to achieve reproducible respiratory signals has a great impact on the temporal distribution of the phases. Thus, although phases 51, 59, and 44% are close to the target phase 50%, the corresponding amplitudes recorded by the RPM system are very different (a gap of more than 1.25 cm, whereas the average respiratory amplitude is 1.5 cm). These differences explain the kinetic artifacts observed on the superior/inferior axis, they are easily detected by the discontinuity in the anatomical structures being imaged.

As an illustration, the analysis of 50 4D-CT from different patients, presented in Ref. 19, has highlighted the presence of artifacts around the diaphragm or heart in 90% of the images. The impact on the measure of the tumor has been determined by Sarker et al. [START_REF] Sarker | Variations in tumor size and position due to irregular breathing in 4d-ct: A simulation study[END_REF] . Indeed, they established correlated variations of lung volume and discontinuities in the acquired 4D respiratory signal. Furthermore, using several maximal inspirations, they have measured for the average position of the center of the tumor mass a standard-deviation of 1 cm for a difference of 59.7% in lung volume. In fact, the smaller the tumor dimensions, the larger the error on the position of its center.

Kinetic blurs appear in the axial plane, they are characterized by a poor definition of anatomical structures. This kind of artifacts is not negligible, since Persson et al. [START_REF] Fredberg Persson | Deviations in delineated GTV caused by artefacts in 4DCT[END_REF] observed that, in addition to kinetic artifacts, blurring affects GTV (Gross Tumor Volume) delineation. Indeed, the authors have shown that the variation in GTV size throughout respiratory phases results from partial volume effects caused by kinetic blur due to large tumor motion. Together, kinetic artifacts and blurs lead to contouring error of the GTV, with size differences up to 90%.

Consequently, although 4D-CT is a commonly used modality, it leads to artifacted images because it fails to adapt to respiratory variations (period and magnitude), and also requires some time to record the data. Moreover, the spatial resolution is another limiting factor for the selection of anatomical landmarks. Hence, in spite of the fact that 4D-CT provides a measure, we can and we want to improve the quality and the accuracy of the motion information for each patient. This paper presents an original approach for real-time simulation of lung motion using a neural network. It focuses on the data processing method based on additional neural networks to improve the quality of the 4D-CT data used to learn the motion.

To simulate the lung motion, various approaches have already been proposed. Sarut et al. [START_REF] Sarrut | A comparison framework for breathing motion estimation methods from 4-D imaging[END_REF] and Villard [START_REF] Villard | Simulation du Mouvement Pulmonaire pour un Traitement Oncologique[END_REF] designed an algorithm based on continuum mechanics formalism. They studied the lung deformations induced by the diaphragm and the rib-cage, and obtained a subvoxel accuracy. However, as they build a three dimensional image using a model defined by many complex equations, their method has a high computational cost. Furthermore, some exams are required in order to carefully measure all tissue elasticity parameters. This approach can give an accurate prediction of the lung motion, but is not well suited for routine clinical use. Boldea et al. [START_REF] Boldea | 4D-CT lung motion models construction with deformable registration: estimation of motion nonlinearity and hysteresis[END_REF][START_REF] Boldea | Intégration de la respiration en radiothérapie : apport du recalage déformable d'images[END_REF] simulated a 4D scan during a respiratory cycle using two scanner images: one at the very beginning and another one at the very end of the inspiration. Nevertheless both precision and computation time are very similar to the former methods. The approach proposed by Hostettler et al. [START_REF] Hostettler | Real time simulation of organ motions induced by breathing: first evalution on patient data[END_REF] , which is based both on reference marks on patient skin and one scan, is interesting since it permit a low-dose exposition.

Unfortunately, it provides a low accuracy: 5 to 7 mm whatever the voxel dimensions are.

Studies also focused on the determination of the hysteresis of lung motion. In fact, a respiratory model that exhibits an hysteretic behavior of lung would allow to improve the accuracy in radiation therapy. Lung tumors are also prone to hysteresis [START_REF] Seppenwoolde | Precise and real-time measurement of 3D tumor motion in lung due to breathing and heartbeat, measured during radiotherapy[END_REF][START_REF] Wu | Hysteresis analysis of lung tumor motion in radiation treatment[END_REF] , hence this phenomenon must be considered during the treatments. In Ref. 11, a respiratory motion simulator into account this useful information has been built. It offers 5 degrees of freedom: tissues location at a specific phase, the tidal volume and airflow according to the breathing phase, and like the methods described previously uses 4D-CT scans. The gap between the measured and predicted points ranges from 0.75 to 1.55 mm.

Data augmentation techniques have already been used in many domains. Indeed, they represent an invaluable tool for Bayesian statistics, particularly to investigate posterior distribution using Markov chain Monte Carlo methods [START_REF] Gavin | Generalised data augmentation and posterior inferences[END_REF] . An expectation-maximization algorithm can also benefit from data augmentation [START_REF] Fraley | On computing the largest fraction of missing information for the EM algorithm and the worst linear function for data augmentation[END_REF][START_REF] Yang | A data-augmentation method for infectious disease incidence data from close contact groups[END_REF] . The relevance of increasing a limited data set in the context of Artificial Neural Networks (ANN) has been also studied in Ref. 6. In this work, we consider such an approach to effectively increase the size of the dataset and reduce the influence of artifacts and bias introduced by 4D-CT imaging. Precisely, the initial small and noisy dataset is used to train neural networks, from which a larger set is then built. In this way, we obtain smoothed data that allow to greatly improve the learning of lung motion by another neural network.

MATERIALS AND METHODS

Dataset construction

To simulate a patient's lung motion, we have proposed to use an artificial neural network that learns the motion of some anatomic characteristic points during the respiratory cycle [START_REF] Laurent | Utilisation d'un réseau de neurones artificiels pour la simulation des mouvements pulmonaires[END_REF] . The dataset used to train the neural network through a holdout validation approach is generated by plotting the motion of points in 10 discrete and regular phases of the breathing cycle in 4D-CT images from 5 patients (patients 0 to 4). The five remaining patients (patients 5 to 9) are used as a testing dataset. The characteristic points were determined by a radiation therapist in non-pathogenic areas and thus only the motion of normal tissues will be considered. This process leads to several biases and noise in the data: on the one hand, the phase in which a point is plotted is not always displayed by the scanner, and on the other hand the resolution of the CT images limits the accuracy of the plotted points. In fact, the considered 4D-CT images were obtained using different scanning devices and protocols, the points are marked in a system whose resolution is 1 × 1 × 2 mm 3 and 1 × 1 × 2.5 mm 3 . Table 1 shows the distribution of the 1518 points present in our dataset among the 10 patients. Two facts about the dataset should be noted. Firstly, patients 4, 7, 8, and 9 data subsets come from POPI-model developed by Vandemeulebroucke et al. [START_REF] Vandemeulebroucke | Point-validated pixel-based breathing thorax model[END_REF] . Secondly, two phases are missing for patient 0: phases 10% and 80%.

Multilayer perceptron neural networks

To reduce all potential sources of error and increase the number of points in the dataset, the plotted points are fitted using neural networks. The chosen network model is the feedforward MultiLayer Perceptron (MLP), which is a type of artificial neural network well-known for its universal approximation property 4 . We selected the classical single hidden layer topology. This one is composed of sigmoid-type hidden neurons, while the output neurons have a linear activation function. Our network has 4 inputs: the three dimensional coordinates of a point at phase 0% and the phase number for which its location must be predicted, and the output vector is also a three dimensional vector. For each point, the best network architecture is determined through an incremental approach 1 (successive addition of a a neuron into the hidden layer), according to the motion complexity. Thus, we obtain for each point a regular and smooth description of its trajectory, which does not depend on the scanner resolution and is less noisy. Moreover,we can complement the dataset with missing information (for example, we can add the two missing phases for patient 0) or with a finer description of motion, since the displacement of each point can be obtained for any phase. Thanks to this data processing, the learning set is less noisy and more realistic, which allows to improve the performance of the ANN learning the lung motion. Figure 2 describes the different steps of our approach: an appropriate data treatment through a collection of neural networks is done, followed by the motion learning using another ANN, these steps represent the learning process, then the resulting (trained) network is only used to predict the lung motion (normal execution). The neural network developed to learn the displacements of the lung is also a single hidden layer MLP. It is composed of neurons with activation functions (hidden / output) identical to those of the network model described above. The network has 8 inputs : the three dimensional coordinates of a point at both phases 0% and 50%, the lung volume to identify the patient, and finally the phase number for which the neural network must predict the point location. The network is trained through supervised learning by feeding it with the data resulting from the processing. More precisely, the training updates the synaptic weights and the biases of the neurons in order to minimize the Mean Squared Error (MSE) between the network outputs and the expected ones defined by the data. Hence, the training process consists in applying an optimization algorithm in order to minimize the MSE. In this work, we have chosen the self-scaling Limited-memory BFGS algorithm, a quasi-Newton algorithm [START_REF] Hsieh | Machine Learning Methods in the Environmental Sciences -Neural Networks and Kernels[END_REF] , in combination with Wolfe's linear search. It uses the classical backpropagation algorithm to calculate the gradient of the error. An incremental approach allows to fix the number of neurons in the hidden layer [START_REF] Bahi | An incremental learning algorithm for function approximation[END_REF] . Five network trainings were performed using data from 5 patients, these trainings differ from each other by the data used as validation set for overfitting control (holdout validation): each time the data from a different patient are considered. As long as the mean squared error obtained for the validation set decreases the training improves the network, whereas a long term increase means a loss of the generalization ability.

The resulting networks usually have 8 neurons on the hidden layer. Therefore, we decided to retain this topology for the remainder of our study. Our method to control overfitting consists in performing the training 1000 iterations (also called epochs) beyond the one for which a minimum MSE is achieved for the validation set. More precisely, 1000 iterations allow to verify that a divergence of several millimeters is observed for the validation set after the last minimum. After the study of the optimal number of phases to learn the lung motion, a comparison of different trainings will be done. This comparison will focus on the impact of both learning and validation sets quality: ILS and CLS will, respectively, denote the Initial and Corrected Learning Set, while IVS and CVS will represent their counterparts for the Validation Set. Let us note that the validation set will also be used as test set to assess the performances.

RESULTS

Once a training is completed, the network computes the displacements of the points belonging to one patient over 100 phases. In the less favorable case, which corresponds to patient 4, the average computation time is 205 ms (±32) on a typical personal computer (dualcore CPU running at 2.1 GHz). That means an almost real-time simulation of lung motion, since less than 3 ms are required to compute the positions of the 38 points.

Data processing

To ensure a good continuity between the adjacent simulated phases 99% and 0%, the phase domain is extended between -20% and 120%. Since the studied phenomenon is periodic, a correspondence between the phases of this new domain must be done. However, due to bias in some data, particularly between phases 90% and 0%, continuity is not fully guaranteed. For example, Fig. 3(b) shows that, according to the 4D-CT images, the point has a trajectory that covers 5 mm between two consecutive phases at the end of the exhalation. In other words, May 24, 2012 18:36 manuscript Data Processing using Artificial Neural Networks to Improve the Simulation of Lung Motion 5 a large movement is observed when the displacement of a point is theoretically very small. This gap is reduced to less than 1.8 mm, thanks to the processing. Figure 3 shows the noisy trajectories resulting from 4D-CT for points belonging to patients 0 (points 1 and 2; plots (a) and (b)) and 4 (point 3; plot (c)), and the smoothed ones obtained by our processing. The trajectories are given considering the z cranio-caudal axis. As a reminder, the points of patient 0 are only defined on 8 phases: phases 10% and 80% are missing. In particular, it can be seen that the displacement of point 1 is very noisy at phase 50%, clearly showing that data smoothing is relevant. In all cases, the smoothing induced by our processing does neither lead to a loss of information on the movement, nor alter the information. So, we obtain a more accurate and smoother description of the displacement of a point, which in consequences improves the convergence of the artificial neural network learning the lung motion. sponds to the 0% one, a point should come back to its initial position. Note that in this figure phases 10, 20, 30, and 40% give the point position for them and also, respectively, for phases 90, 80, 70, and 60%. Hence, this figure shows in addition to the bias between phases 90% and 0%, the hysteresis-like motion, for both 4D-CT and smoothed data. Consequently, the ANN learning the lung motion uses the data without any a priori information.

Optimizing the training process

In the following results, the ones corresponding to patient 1 are not given, because of the patient characteristics: the smallest lung volume and its points are the most scattered inside the lungs. The lung motion of patient 1 can be simulated, but we would obtain an approximative simulation because there is no similar case known.

The results are given according to the patient considered as the validation set to control overfitting, since we use a cross-validation process. Also, we do not give any indication on the trainings convergence because the training sets are quite different. We show the results gained once the trainings are performed. Thus, they present for the patient used as validation set the average distance between the expected positions and the ones predicted by the ANN for all phases. To compare the treated data with the originals, only 10 phases are considered to compute the average error, except for patient 0 which is defined by 8 phases. This last point explains why the errors for this patient are the smaller: a missing phase (80%) exhibits an important gradient of motion. Table 2 clearly highlights the impact of the missing phases.

Table 2 is devoted to the study of the number of phases used to describe the points motion according to the validation patient. Several observations can be made. First, patient 2 is characterized by a stable accuracy whatever the number of learnt phases, which is a consequence of the point locations: they are localized in a lung area with a simple motion. Secondly, conversely patient 4 has the largest errors because it is the patient that has the biggest lung volume. In this case the ANN extrapolates, since it predicts movements beyond the ranges of the training dataset. However, the neural network is able to correctly simulate the motion (with larger errors) of each point. Thirdly, the ideal number of phases is 50, whereas 100 phases induce a loss of generalization ability reflected by the increase of the average errors. In the following, we will retain the 50 phases setup for the motion description. Similarly, table 3 shows the evolution of the average error according to the training and validation sets for each test patient. Considering ILS trainings and both types of validation/test sets the noise resulting from each patient becomes quantifiable. Note that even without any data processing an artificial neural network smoothes the noise. This first comparison shows that the patient data are noisy, with a noise level that is not negligible: the average distance ranges from 3% to 8%. The neural network is not able to fully reduce the impact of the noise because we have a small learning set due to few patients. Therefore, a data processing is required. The last column, for each patient, in table 3 assesses the relevance of the processing on the learning set: both bias and noise are reduced such that the neural network converges to a smaller learning error. The estimated accuracy improvement between ILS/IVS and CLS/CVS varies between 16% and 42% according to the patient.

Simulation of the lung motion

As we can see in table 3, CLS/CVS is the optimal training setup for our neural network, so it was to retained to learn the lung motion. The neural network used is the one obtained with patient 2 as validation set. In this case the 1518 points of the dataset are used as follows:

• the learning subset is composed of 4600 points (patients 0, 1, 3, and 4; 50 phases);

• patient 2 (1200 points) defines the validation subset; • the remaining 400 points (patients 5 to 9; 10 phases) correspond to the test samples.

Thus, the learning, validation, and testing subsets represent, respectively, about 74%, 20%, and 6% of the whole dataset. Let us emphasize that the learning and validation points have been processed to improve the network training, whereas it is not the case of the test samples. Indeed, in normal execution the neural network is supposed to deal with original 4D-CT data. Table 4 presents the results obtained for the test patients for the initial dataset (ILS/IVS) and the ones (CLS/CVS) issued from our treatment method. The mean improvement of the prediction accuracy is about 16% and reaches 30% for patient 9. To validate our approach, we carried out a comparison of the results with a linear approximation of the motion. This approximation is obtained considering that the displacements remain constant whatever the phase, by applying a linear regression between the maximum exhalation and expiration phases (0% and 50%), and thus without taking into account the hysteresis.

Obviously, the linear interpolation leads to a symmetrical motion between the phase ranges 0-50% and 50-100%. Figure 4 shows the motion predicted for two distinct points issued from test subset, the first one belongs to patient 6 and the second to patient 8, the trajectories obtained by linear regression and from 4D-CT data are also plotted. We can notice that linear regression is not accurate enough to describe the motion. Indeed, as highlighted by the 4D-CT the motion gradient depends on the phase. By comparison with the linear approximation, our approach that considers hysteresis is more competitive, closer to the 4D-CT. This observation can also be made from Fig. 5, which presents the average prediction errors for the points belonging to patient 8. The data from phases 0% and 50% were not taken into account to compute the values presented in the histogram, because their errors for the linear regression are zero by construction. The positions predicted by our neural network are, on average, the nearest to the ones given by the 4D-CT. The lower standard deviations reflect the better fitting of the neural network, thanks to the simulation of the hysteresis, as suggested by Fig. 4. The error becomes favorable for the linear regression when the point motion is constant on 0-50% or 50-100%, or even for the whole phases. In that case, the neural network still simulates a small movement and thus gives an error. For the set of points from patient 8, the average error of the positions predicted by the ANN is, in comparison with the 4D-CT images, less than 2 mm (except point 2), which means lower than the z axis image resolution.

DISCUSSION

Table 1 shows great variations in the errors according to the patient. In fact, our method is sensitive to the lung volume, since the largest errors for patients 7, and 9 result from lung volumes distant from the ones of the patients used as learning and validation data. Obviously, a neural network can only give suitable predictions for unknown inputs when they are similar to some samples used during the training step. As a consequence, patients 5, 6 and 8, which have lung volumes of the same order than several training patients (see table 1), have the lowest errors. When a 4D-CT produces a point trajectory without hysteresis (see Fig. 4(a)), the artificial neural network simulates ones thanks to its ability to generalize from the given patients. More generally, for both points presented in Fig. 4 the trajectories predicted by the ANN reflect the 4D-CT ones, taking into account motion artifacts and hysteresis. The minimum position of these points is located between phases 50% and 60%, while we considered that phase 50% was the maximum inspiration. Note that we had no a priori knowledge on the points positions, but rather the data used to train the network have their minimum at phase 50% or 60%.

Our method is based on 4D-CT data and we have seen previously that these data contain artifacts. Consequently, finding suitable displacements for the different points is more difficult. Despite this, our approach uses this tool to accurately simulate the motion of points whatever the phase and considering hysteresis.

CONCLUSION AND FUTURE WORK

The simulation of lung motion is a difficult challenge, because breathing is a complex phenomenon which requires to consider, in addition to hysteresis, the various types of deformation induced by the different areas of the lung. Our approach consists in learning the lung motion using some patients data, so that the breathing of the unknown patients can be accurately simulated. Thus, once the data is pretreated to significantly reduce the noise resulting from the 4D-CT artifacts, we can produce in a realistic way for normal tissues, every deformation that belongs to our domain of definition (currently it does not cover the whole lung, due to lack of data). We have shown that the 4D-CT scans are noisy and that the proposed processing allows to improve the convergence of the neural network designed to learn the lung motion. An average accuracy improvement of 16% was observed. The results of our method are not limited by any constraint posed by the 4D-CT modality (such as a voxel size of 1×1×2.5 mm 3 ) or the only knowledge of ten discrete phases with an important uncertainty.

In the future, we plan a clinical evaluation so that we can differentiate the patients' sex, pathologies, and tissues in order to improve our approach for a possible use in clinical routine practice. Indeed, our method runs in almost real-time and thanks to a simultaneous acquisition of a patient respiratory phase, we will compute each time the tumors contours. To finalize our method, we will also extend the domain of definition to cover the whole lung by considering more points and more patients.

Fig. 1

 1 Fig.14D-CT imaging: reconstruction process of a 3D CT image at a discrete phase (50% in this example) for a patient according to its respiratory signal

Fig. 2

 2 Fig. 2 Schematic description of the proposed approach (ILS = Initial Learning Set; CLS = Corrected Learning Set; CVS = Corrected Validation Set)

Fig. 3 Figure 3

 33 Fig.3Processing impact on the motion of the three different points

Fig. 4

 4 Fig. 4 Motion simulated for two points, each belonging to a different patient

Fig. 5

 5 Fig.5Neural network versus linear regression: average prediction errors for all points of patient 8, considering all phases

Table 1

 1 Dataset points distribution

	Patient#	0	1	2	3	4
	Lung vol.	4.62	2.86	5.48	2.60	5.94
	Pts/Phase	21	25	24	8	38
	Phases	[0; 20 -70; 90] [0 -90] [0 -90] [0 -90] [0 -90]
	Total	168	250	240	80	380
	Patient#	5	6	7	8	9
	Lung vol.	3.10	4.42	3.72	4.91	4.05
	Pts/Phase	6	4	10	10	10
	Phases	[0 -90]	[0 -90] [0 -90] [0 -90] [0 -90]
	Total	60	40	100	100	100

Table 2

 2

			Average	errors	(standard	deviation)
	in	mm	according	to	the	number	of	phases
	that defines the motion of the different points
					Phases
	Patient#	10	20		50		100
	0		0.88 (0.83) 0.86 (0.82) 0.86 (0.82) 0.87 (0.80)
	2		1.01 (0.81) 1.05 (0.87) 1.00 (0.84) 1.02 (0.83)
	3		1.23 (0.80) 1.08 (0.63) 0.92 (0.68) 1.00 (0.65)
	4		1.35 (0.96) 1.36 (1.01) 1.27 (0.99) 1.27 (1.00)

Table 3

 3

		Average errors (standard de-
	viation) in mm obtained with the dif-
	ferent learning setups (Initial / Cor-
	rected -Learning / Validation Sets)
	Patient#	ILS/IVS	ILS/CVS	CLS/CVS
	0	1.47 (1.28) 0.97 (0.90) 0.86 (0.82)
	2	1.56 (0.92) 1.20 (0.76) 1.00 (0.84)
	3	1.43 (0.96) 1.15 (0.68) 0.92 (0.68)
	4	1.52 (1.08) 1.37 (1.00) 1.27 (0.99)

Table 4

 4

	Average errors (standard de-
	viation) in mm obtained for the dif-
	ferent test patients (Initial / Cor-
	rected -Learning / Validation Sets)
	Patient#	ILS/IVS	CLS/CVS
	5	1.15 (0.68) 1.02 (0.62)
	6	1.45 (0.55) 1.25 (0.72)
	7	2.30 (2.32) 2.00 (2.26)
	8	1.37 (0.96) 1.16 (0.83)
	9	2.18 (1.49) 1.53 (1.15)

ACKNOWLEDGEMENTS

The authors thank the LCC (Ligue Contre le Cancer), Région Franche-Comté and the PMA (Pays de Montbéliard Agglomération) for their financial support.


P Santagostini
email: pierre.santagostini@agrocampus-ouest.fr

S Demotes-Mainard

L Huché-Thélier

N Leduc

J Bertheloot
email: jessica.bertheloot@angers.inra.fr

V Guérin

J Bourbeillon
email: julie.bourbeillon@agrocampus-ouest.fr

S Sakr

R Boumaza
email: rachid.boumaza@agrocampus-ouest.fr

Assessment of the visual quality of ornamental plants: comparison of three methodologies in the case of the rosebush

Keywords: UPOV, rose, aesthetic quality, sensory analysis, floribundity

The quality of ornamental plants can be appraised with several types of criteria: tolerance to biotic and abiotic stresses, development potentialities and aesthetics. This last criterion, aesthetic quality, is specific to ornamental plants and objective measurements are required.

Three methodologies for measuring aesthetic quality have been proposed. The first involves classical measurements of morphological features, such as flower number and diameter or leaf size. The second is based on sensory methods recently adapted to ornamental plants. The third, used by the International Union for the Protection of New Varieties of Plants (UPOV) for distinctness, uniformity and stability (DUS) tests, is based on morphological characteristics calibrated on specific reference varieties. The aim of this work was to compare these three methodologies for assessing some flowering and foliage characteristics of rosebushes. Six plants from 10 rose varieties identified by UPOV as reference varieties were cultivated for two years in a greenhouse and outdoors in Angers, France. They were measured and photographed weekly during flowering. Photographs of the plants in full bloom were submitted to a panel of judges for sensory assessment. The results of the three assessment methodologies were compared. Sensory and morphometric measurements were highly correlated and sensory measurements confirmed UPOV scales, whereas some morphometric measures diverged slightly from UPOV scales. We discuss the advantages, disadvantages and complementarity of these three methodologies.

Introduction

Quality is defined by the ISO 8402-1986 standard as "the totality of features and characteristics of a product or service that bears its ability to satisfy stated or implied needs".

The quality of plants can be appraised with several types of criteria: tolerance to biotic and abiotic stresses, development potential and aesthetics, a criterion specific to ornamental plants [START_REF] Habib | La nutrition azotée des cultures et la qualité des produits[END_REF][START_REF] Dijkshoorn-Dekker | Crop quality control system: A tool to control the visual quality of pot plants[END_REF][START_REF] Heuvelink | Modelling Product Quality in Horticulture: an Overview[END_REF][START_REF] Giorgioni | Evaluation of Landscape Roses for Low-Maintenance Gardening[END_REF]. The measurement of aesthetic quality is necessary for objective studies, such as modelling or assessing the effects of various treatments. However, as pointed out by [START_REF] Boumaza | Visual characterization of the esthetic quality of the rosebush[END_REF], the multiple possibilities make it difficult to measure.

The characteristics of aesthetic quality to be taken into account depend on the type of ornamental plant considered: trees, shrubs, bushes or cut flowers. However, some of these characteristics may be common to several plant categories. We focus here on the rosebush, a model plant in ornamental horticulture, considering only visual aspects and ignoring all considerations relating to scent. Furthermore, we do not aim to characterise the visual quality of all the aerial parts of the plant. Indeed, this aspect has been dealt with in previous studies based on the use of tools and methods from the domain of sensory analysis [START_REF] Boumaza | Sensory profiles and preference analysis in ornamental horticulture: the case of the rosebush[END_REF][START_REF] Huché-Thélier | Nitrogen deficiency increases basal branching and modifies the visual quality of the rose bushes[END_REF] or architecture analysis [START_REF] Morel | Using architectural analysis to compare the shape of two hybrid tea rose genotypes[END_REF][START_REF] Crespel | Identification of relevant morphological, topological and geometrical variables to characterize the architecture of rose bushes in relation to plant shape[END_REF]. Instead, we focus on the partial evaluation of flowers and leaves, two of the principal determinants of the visual quality of the rosebush.

Floribundity is defined as "the capacity of a plant to produce abundant flowers at high density on each of its branches" (http://fr.wiktionary.org/, 10/11/2012). However, should we take into account the number of flowers at peak flowering or throughout the year? In its guidelines, UPOV specifies that all observations should be made when the plant is in full flower [START_REF] Upov | Guidelines for the Conduct of Tests for Distinctness, Homogeneity and Stability[END_REF]. Hereafter, we refer to this measurement as the peak floribundity index.

The longitudinal floribundity index is the variation of the floribundity index during a season.

Another related question concerns the stage at which flowers should be counted. Should we count all flowers, regardless of their stage of development (buds, opened, withered, rose hips) or only fully opened flowers? If we focus on the vitality of the plant, it would be tempting to consider all the flowers. However, if we are more concerned about visual quality, we may wish to restrict the flower count to opened flowers -that is, flowers with visible petals -and rosehips. Indeed, these two types of organ are brightly coloured and stand out from the foliage of the rosebush, which is usually green once the leaves have fully emerged. The peak floribundity index reported here takes into account all flowers but not the rosehips, whereas the longitudinal floribundity index takes only open flowers into account. We characterised floribundity by three types of methods or methodologies: the morphometric methodology, the sensory methodology and the UPOV methodology. The flower and leaf dimensions were characterised by the morphometric and UPOV methodologies.

The morphometric methodology is classically used in agronomy. It includes all methods based on counting, such as flower, leaf or axis counts, methods based on the measurement of dimensions, such as the diameters and heights of flowers, the lengths and widths of leaflets and stem length, and methods based on image analysis.

The sensory methodology involves the methods and tools initially used in sensory analysis. These methods were originally developed in the agro-food industry and have since been extended to other domains. They have recently been adapted for the objective characterisation of the visual quality of ornamental plants, as perceived by the human eye, which can be considered as a measurement instrument in this context [START_REF] Boumaza | Visual characterization of the esthetic quality of the rosebush[END_REF].

These methods require the choice of appropriate descriptors, the constitution of a jury of about 15 judges and the evaluation of each descriptor for each product. Two applications [START_REF] Boumaza | Sensory profiles and preference analysis in ornamental horticulture: the case of the rosebush[END_REF][START_REF] Huché-Thélier | Nitrogen deficiency increases basal branching and modifies the visual quality of the rose bushes[END_REF] have demonstrated the relevance of such methods to ornamental horticulture, a sector in which visual quality is an important component of the commercial value of the products.

The UPOV methodology is based on the DUS (distinctness, uniformity and stability) requirements laid down by UPOV in 1990 for the examination of cultivars or varieties for the acquisition of plant breeders' rights. This method is based on scoring rosebushes on a scale of 1 to 9 for characters identified as useful for distinguishing between varieties or for evaluating the uniformity and stability of a variety. Scores of 1, 3, 5, 7 and 9 correspond to examples of varieties that will be referred hereafter as reference varieties (Table 1). The most important feature of this method is that the relative behaviour of the reference varieties is identical in all environments. In some ways, this renders this approach almost international. In this study, we also considered the relevance of this approach, although this was not the principal objective.

The reference varieties studied here were those used between 1990 and 2010. The recommendations for the DUS examination were subsequently modified in 2010 [START_REF] Upov | Guidelines for the Conduct of Tests for Distinctness, Homogeneity and Stability[END_REF]. This modification led to changes in the reference varieties for the two characters considered. However, this does not undermine the importance of this work, which was begun in 2008 and focuses on a key question: Is it possible to decrease the costs of rosebush evaluation when using a sensory method, and if so, how? Indeed, if the requirements for the reproducibility and repeatability of measurements are to be respected, the sensory method is more expensive than morphometric analyses. Furthermore, neither of these two methods has the almost international nature of the UPOV method.

The aim of this study was, therefore, to compare these three methodologies. We evaluated floribundity, and the flower and leaf dimensions of UPOV reference roses, and then compared the results obtained and considered the advantages and disadvantages of each methodology.

For validation of some of the findings of these comparisons, we also considered the data obtained for rosebushes by [START_REF] Boumaza | Sensory profiles and preference analysis in ornamental horticulture: the case of the rosebush[END_REF], referred to hereafter as supplementary data.

2 Materials and Methods

Plant material and growing conditions

Ten rosebush varieties, listed in Table 1, were cultivated at Angers, France (latitude: 47° 30' N; longitude: 0° 35' W; altitude: 56 m). The rosebushes were grafted onto Rosa corymbifera 'Laxa', except for the 'Sweet Promise' variety, which was grafted onto Rosa canina 'Schmids Ideal'. Experiments were conducted in a greenhouse from November 2008 to April 2010 and outdoors from April 2010 to September 2011.

Growing conditions in the greenhouse

In November 2008, 60 rosebushes (6 per variety) were planted in 7-litre pots, in a substrate composed of peat, coconut fibre and perlite (60/30/10, v/v/v). The pots were randomly placed on a shelf in six rows, 0.75 m apart and then pruned. The plants were drip fertiirrigated with a liquid fertiliser (Servital®, with a 3-2-6-0.6 balance of N-P 2O5-K2O- MgO, a pH of 5.8 and a mean electrical conductivity (EC) of 1.8 mS cm -1 , including the EC of water, which was 0.3 mS cm -1 ). Each plant received between 330 mL of solution every two days in winter and 1330 mL per day in summer. Pests and diseases were controlled.

Additional lighting (60 µmol m -2 s -1 of photosynthetically active radiation) was provided by sodium vapour lamps when total radiation levels outside the greenhouse fell below 200 W m -approximately to the measurement period, mean diurnal temperature was 25.6 °C (minimum:

18.4 °C and maximum: 45.0 °C) and mean humidity was 48% (minimum: 15% and maximum: 85%).

Outdoor growing conditions

In mid-April 2010, the 53 surviving rosebushes (7 had died) were transferred outside, together with new rosebushes to replace those that had died, to obtain six replicates per variety. They were planted randomly in six blocks, 2 m apart, on a silty clay soil covered by a porous plastic mulching film. They were drip irrigated with 500 mL of water per plant every non-rainy day, from April to September. Pests and diseases were controlled. As reported for the 'Radrazz' variety by [START_REF] Demotes-Mainard | Coordinated development of the architecture of the primary shoot in bush rose[END_REF], the length of the terminal leaflet was correlated with all the other leaf measurements taken, regardless of the variety considered. We therefore chose to use this character for comparisons of leaf dimensions.

Flowers

Measurements of flower diameter were made on the UPOV reference varieties: to that covered by the entire plant (Figure 1), was determined with ImageJ [START_REF] Rasband | ImageJ[END_REF].

This ratio and the number of flowers were considered as floribundity indices.

Sensory measurements

These measurements were carried out on the reference varieties 'Meichim', 'Kolima', 'Sweet Promise' and 'Meiburenac'. One field-grown plant per variety was photographed about once weekly, and we selected three photographs for each plant, some of which were taken at peak flowering. We trained a jury of 16 assessors, to ensure that they interpreted the overall level of flowering in the same way, and established a structured nine-level scale with three photographs for each odd-numbered level (Figure 2). The photographs used for training purposes were, of course, different from those subsequently used for assessment. After the training session, the assessors were asked, individually, (i) to sort the 12 chosen photos into ascending order of flower quantity, taking into account buds and withered flowers, (ii) to sort them according to the relative area occupied by the open flowers, that is the ratio of coloured flower area to total plant area, (iii) to score the level of flowering on the nine-level scale they had previously established (Figure 2). Each assessor carried out three scoring sessions, at oneweek intervals.

Supplementary data

As part of the sensory evaluation carried out by [START_REF] Boumaza | Sensory profiles and preference analysis in ornamental horticulture: the case of the rosebush[END_REF], 10 rosebush photographs (Fig. 3) were evaluated by 14 judges in three sessions. The judges provided scores for some descriptors, three of which were related to floribundity: "Number of flowers", "Flower enhancement" and "Number of buds". These scores were used to rank the 10 rosebushes for each descriptor/session/judge. Then, for each descriptor, we averaged the 42 ranks of each rosebush to get a mean rank per rosebush/descriptor. The relative flower area of each rosebush was measured independently, with the image analysis method described in section 2.3. All these data are reported in the table associated with figure 3.

Statistical analyses

All statistical analyses were carried out in the R environment (R Development Core Team, 2011), with the stats, graphics and agricolae packages. Analysis of variance was used for variety comparisons. When the conditions for the application of this method were not fulfilled, nonparametric tests (Kruskal-Wallis or Friedman test) were used [START_REF] Conover | Practical Nonparametric Statistics[END_REF].

3 Results

Leaf dimensions

Both in the greenhouse and outdoors, the ranking of varieties (Table 2) matched that of the UPOV scale (Table 1), except for 'Mullard Jubilee', the level 7 (large leaves) reference variety. It was not possible to distinguish this variety from the 'Tancary' and 'New Daily

Mail' varieties, level 9 (very large leaves) reference varieties on the basis of our morphometric measurements. We were therefore able to construct a four-level scale for leaf dimensions, with specific reference varieties: "very small" with 'Meiblam', "small" with 'Starina', "medium" with 'Kolima' and "large or very large" with 'Mullard Jubilee', 'New Daily Mail' and 'Tancary'.

Flower dimensions

The diameters of the terminal flowers were found to be significantly greater than those of the other flowers for the 'Starina' and 'Meiburenac' varieties. We therefore excluded the terminal flowers of plants of these two varieties from the calculations of mean diameter, as recommended by [START_REF] Upov | Guidelines for the Conduct of Tests for Distinctness, Homogeneity and Stability[END_REF]. By contrast, for 'Pink Wonder', we found no difference between the diameters of terminal and non-terminal flowers, and the difference between these two types of flowers was very small for 'Kolima'. Hence, as fewer data were available for these two varieties, we considered all the flowers, both terminal and non-terminal, in the calculation of mean flower diameter.

The mean flower diameters for each variety (Table 3), obtained in two consecutive years in very different growing conditions (one year in the greenhouse and the second year outdoors), were of the same order of magnitude. The largest difference was that for 'Kolima', which produced flowers with a mean diameter of 74 mm in the greenhouse and 83 mm outdoors. Pairwise comparisons of rosebushes growing outside led to the identification of two groups. The first consisted of the varieties 'Starina' and 'Meiburenac', the reference varieties for level 1 (very small) and level 3 (small), respectively, on the UPOV scale (Table 1). The second group consisted of the varieties 'Kolima' and 'Pink Wonder', the reference varieties for level 5 (medium-sized) and level 7 (large), respectively. Three groups were identified in greenhouse conditions: the first consisted of 'Starina' and 'Meiburenac', the second of 'Kolima' and the third of 'Pink Wonder'.

Thus, flower diameter measurements did not discriminate between reference varieties with very small and small flowers either in the greenhouse or outdoors, or between reference varieties with medium-sized or large flowers outdoors. It was therefore possible to construct a two-level scale for rosebush flower diameter from morphometric measurements: very small or small flowers, with 'Starina' and 'Meiburenac' as the reference varieties, and medium-sized or large flowers, with 'Kolima' and 'Pink Wonder' as the reference varieties. This scale partly confirms the UPOV scale but, with only two levels, it is not suitable for use in practice.

Floribundity

Number of flowers

When we considered the number of flowers during the first full flowering of each plant, the ranking of the varieties (Table 4) did not perfectly match the UPOV classification (Table 1). Indeed, our measurements suggest that 'Meiburenac' is a highly floriferous variety (105 flowers/plant in the greenhouse and 213 flowers/plant outdoors), followed at some distance by 'Kolima' (24 and 33 flowers/plant, respectively). 'Sweet Promise' systematically produced fewer flowers (15 and 17 flowers/plant, respectively) than these two varieties. However, 'Meichim', the least floriferous variety according to UPOV, behaved inconsistently, producing a similar number of flowers to Sweet Promise in the greenhouse (12 flowers/plant), but a number of flowers between the values obtained for 'Kolima' and 'Sweet Promise' outdoors (23 flowers/plant).

Sensory data

When dealing with sensory data, the first step is the use of several techniques to evaluate jury repeatability and reproducibility [START_REF] Dijksterhuis | Assessing panel consonance[END_REF][START_REF] Rossi | Assessing sensory panelist performance using repeatability and reproducibility measures[END_REF]. The detailed results of this process are not shown. From the analysis of sensory data through studies of the distribution of ranks or scores, we noted that the consensus between the judges was best for classification by number of flowers and slightly weaker for scores of flowering level and for classification by the ratio of flower area to total plant area, but the use of these results did not affect the principal findings for variety classification.

For each of the three previous sensory evaluation tests (classification by number of flowers, area of the photograph covered by flowers and scores for flowering level), comparisons of varieties gave identical results (Table 5), confirming the UPOV classification for the number of flowers per flowering branch: few (with 'Meichim' as the reference variety), medium ('Sweet Promise'), many ('Kolima') and very many ('Meiburenac'). Thus, the perception of floribundity by the human eye is entirely consistent with UPOV measurements.

Morphological measurements and their relationship to sensory data

For the 12 photographs of rosebushes used for sensory evaluation, we determined the coefficients of correlation between the relative flower area, the number of flowers counted in the field and the mean scores provided by the jury (Table 6). These correlations were found to be strong. This finding opens up interesting new possibilities, in that it suggests that floribundity, as perceived by the human eye, can be assessed simply from a photograph. We will consider this aspect further.

Longitudinal floribundity

In the previous sections, only the instantaneous measurements of floribundity were considered, in analyses of measurements corresponding to peak flowering. So, what about the longitudinal floribundity (i.e. changes in floribundity over time)?

For one rosebush per variety, we plotted changes in relative flower area and in number of flowers over time (Fig. 4; graphs on the left). The two curves had the same shape, with peaks occurring at approximately the same dates. Similarly, the times at which the area was null or small corresponded to periods in which there were few, if any, flowers. The Spearman's rank correlation coefficients for the relationship between these two measurements were high (Fig. 4; graphs on the right).

If we consider the longitudinal floribundity obtained by counting the number of flowers (Fig. 5), then 'Meiburenac' appeared to be much more floriferous than the other varieties.

Similarly, 'Kolima' produced more flowers at peak flowering than 'Sweet Promise' or 'Meichim', but this was not always the case for other rosebushes from the same varieties, as some 'Meichim' rosebushes (not shown here) had larger numbers of flowers than 'Kolima' rosebushes in early autumn.

Supplementary data

Relative flower area was strongly correlated with the mean rank inferred from the descriptor "Number of flowers" (Spearman's rank correlation coefficient (R S): 0.78, n = 10, p = 0.01). It was not correlated with the mean rank inferred from the descriptors "Flower enhancement" (RS = 0.45, p = 0.19) and "Number of buds" (RS = -0.14, p = 0.70).

Discussion

We used all three methodologies to assess floribundity, whereas only the UPOV and morphometric methodologies were used to assess the dimensions of leaves and flowers. This study focused on the choice of methodology for the simple assessment of these features in the most universal and efficient manner possible.

Leaflet and flower dimensions: can we propose classes of values?

Based on the measurement protocol proposed by UPOV and specified in the materials and methods section, the use of value classes, corresponding to the UPOV scores for terminal leaflet length or flower diameter, would greatly simplify the evaluation of leaves or flowers by the sensory methodology. We initially planned to define such classes on the basis of the mean characteristics (terminal leaflet length and flower diameter) of the UPOV reference classes. Despite the high degree of consistency of the mean characteristics obtained in different growing conditions, the results obtained raise questions about this approach, in that the varieties did not behave in the expected manner. The 1990 UPOV reference varieties do not appear to be appropriate for the constitution of these classes, because there was insufficient discrimination between the reference varieties, particularly for flower diameter.

Two alternative strategies are possible. The first would involve repeating the experiments with the 2010 reference varieties (UPOV, 2010), checking that the relative behaviour of these new reference varieties matched UPOV descriptions and determining whether these classes of values could be considered valid for the Angers region. Given the cost of the experiment, an alternative strategy, based on arbitrarily fixing five classes on the basis of the lengths or diameters reported in tables 2 and 3, respectively, might be preferable. We chose to use the same number of classes as the UPOV protocol: very small, small, medium, large, and very large. For example, in outdoor conditions, the classes for terminal leaflet length could be <25 mm (very small), 25-40 (small), 40-55 (medium), 55-70 (large), >70 mm (very large); those for flower diameter could be <50 mm (very small), 50-65 (small), 65-75 (medium), 75-90 (large), >90 mm (very large). These empirically and somewhat arbitrarily defined classes have the advantage of simplicity and are suitable for use in the Angers region. However, they are not valid for all conditions, because the upper limits of the very small and large classes defining the limits of the three central classes, are not exactly the same in the greenhouse and outdoors.

4.2. Which measurements best reflect the level of flowering of a rosebush?

Given the importance of flowering in ornamental plants, it would appear surprising that UPOV considers only one flowering characteristic in its classification: the number of flowers per flowering branch. Furthermore, the way in which this character should be assessed is not specified in the UPOV guidelines, leaving plenty of room for differences in interpretation.

However, all the possible ways of assessing this character that we tested were sufficiently highly correlated (Table 6), generating a consensus. Nevertheless, although the sensory evaluations fully confirmed the UPOV scale, the morphometric measurements (number of flowers and relative flower area) only partially confirmed the UPOV scale.

The main advantage of the sensory method is that it focuses on the consumer's perception of the plant. Furthermore, the scoring scale can be refined and adapted for the products that the jury is asked to assess. However, it is cumbersome to implement and very timeconsuming, due to the requirement for jury recruitment and training, for example.

Morphometric methods are less subjective than sensory methods, although flower counting may be tedious. By contrast, the relative flower area on a photograph proved to be a suitable indicator of the level of flowering of the plant perceived by an observer. However, this measurement does not match the definition of floribundity, in that two rosebushes may have equivalent ratios but very different numbers of flowers. For example, figure 6 shows two rosebushes: 'Sweet Promise' and 'Meiburenac', corresponding to the "medium" and "very many" categories of the UPOV (1990) scale. Their peak flowering area ratios were 45%, with 30 flowers, for the 'Sweet Promise' rosebush and 47%, with 205 flowers, for the 'Meiburenac' rosebush. This problem can be alleviated, for example by dividing the ratio by an estimate of the area of a flower from the corresponding variety. The advantage of this approach is that the calculation of ratios from photographs can be automated, and this would accelerate the analysis, provided that all the photographs analysed were taken in good lighting conditions. This is a necessary condition to ensure that the colour of the flowers is reproduced accurately on the photograph. Another advantage of this approach is that it is not necessary to photograph the entire rosebush, as this measurement is a ratio that could be estimated on the basis of a photograph of the heart of the rosebush alone. Image analysis would therefore be a useful tool for estimating floribundity and changes in floribundity over time.

4.3. Is the relationship between the results of sensory methods and image analysis confirmed?

The results obtained for the supplementary data highlighted the link between the descriptor "Number of flowers" and relative flower area. They thus provide an additional argument for using the relative flower area measured by image analysis as a possible measurement of rosebush floribundity.

There was no link between the descriptor "Number of buds" and relative flower area. This is not surprising as it no buds were visible on the photograph (if the petal colour was not visible) or only a very small proportion of the area was covered by buds (when the petal colour first became visible).

Conclusion

We compared the results of morphometric and UPOV methodologies for classifying varieties on the basis of flower diameter and leaf dimension, and we identified several discrepancies. We also compared these two methodologies with sensory methodology for floribundity assessment. Our analysis highlighted a convergence of the results obtained with the various methods and suggested that it should be possible to assess floribundity as perceived by the human eye, by image analysis techniques. The main advantages of image analysis methods over sensory methods are their rapidity and universal nature. Such methods, which would be relatively simple to carry out, might prove very useful for quantitative and objective measurements on large samples. This method would therefore be useful for studying processes such as the progression of flowering, which is currently being studied in relation to the genetic determinism of flowering [START_REF] Kawamura | Quantitative trait loci for flowering time and inflorescence architecture in rose[END_REF] and is of interest to rose breeders for the assessment of new cultivars. the proportion of the picture area covered by the plant is calculated (0.28). A threshold is then set on the colour (here, red) to separate the flowers from the foliage (c), and the proportion of the picture area covered by the flowers is calculated (0.12). The relative area of the plant covered by the flowers is the ratio 0.12/0.28 = 0.45 in this case. a The variety Meinatac corresponding to a score of 9 was not found in the market.

b A score of 1 has not been assigned to any variety.

  From mid-April to September 2010, corresponding approximately to the measurement period for 2010, mean diurnal temperature was 19.5 °C (minimum: 3.1 °C; maximum: 36.7 °C) and total rainfall was 156 mm. During the 2011 measurement period, corresponding approximately from April to September, mean diurnal temperature was 19.1 °C (minimum: 6.2 °C; maximum: 35.on the UPOV reference varieties for leaf dimension: 'Tancary', 'Mullard Jubilee', 'Kolima', 'New Daily Mail', 'Starina' and 'Meiblam', from 12 April to 10 August 2009 in the greenhouse and from 3 May to 10 August 2010 outdoors. The length of the rachis, and the length and width of all leaflets of the leaves located in the central third of each flowering shoot were measured when the terminal flower carried by this shoot withered.

'

  Meichim', 'Pink Wonder', 'Kolima', 'Sweet Promise', 'Starina' and 'Meiburenac', from 3 April to 2 September 2009 in the greenhouse and from 8 April to 29 September 2010 outdoors. We measured the diameter and height of almost all the flowers at anther dehiscence during the first flush of flowering (ending in mid-July). The numbers of flowers (buds, open and withered flowers) were counted on the rosebushes of the UPOV reference varieties for flower number ('Meichim', 'Kolima', 'Sweet Promise' and 'Meiburenac') during the first flowering period, on days determined according to plant development, generally when withered flowers were observed on the rosebush. Almost all the replicates of the varieties used for floribundity measurements in the greenhouse (in 2009) and a single rosebush per variety outside (in 2010 and 2011), were photographed, about once per week. The relative flower area, that is the ratio of the area covered by flowers

Figure captions Figure 1 .

 captions1 Figure captions

Figure 2 .Figure 3 .

 23 Figure 2. The structured nine-level scale established by the jury for the assessment of floribundity by the sensory methodology. Each odd-numbered level is illustrated by three examples.

Figure 4 .Figure 5 .

 45 Figure 4. In the left column, for one plant (outdoors, 2010) per variety, we have plotted changes in relative flower area (•) and in the number of open or withered flowers (▲) over time. Time is shown on the x-axis (indicated by date). The left y-axis scale corresponds to relative flower area and the right y-axis scale, to flower number. In the right column, the relative flower area is plotted against the number of open or withered flowers, when these two measurements were made on the same date. Rs denotes Spearman's rank correlation

Figure 6 .

 6 Figure 6. Each photograph corresponds to the maximum ratio of areas shown on the corresponding graph. For this 'Meiburenac' rosebush, the maximum was 45%, with 205 open and withered flowers. For this 'Sweet Promise' rosebush, the maximum was 47%, with only 30 flowers.

Figure_3

  Figure_3

Figure 4 Figure_4Figure 5 Figure_5Figure 6

 456 Figure 4

Figure_6

  Figure_6

Table 1 .

 1 The reference varieties of the UPOV scales for the studied characteristics: flower diameter, leaf size and number of flowers (UPOV, 1990).

	Characteristics				UPOV score
		1		3	5	7	9
	Leaf: size	Meiblam Starina	Kolima	Mullard	-Tancary
						Jubilee	-New Daily Mail
	Flower: diameter	Starina	Meiburenac Kolima	Pink	-	a
						Wonder
	Flowering shoot:	-	b	Meichim	Sweet	Kolima	Meiburenac
	number of				Promise
	flowers

Table 2 .

 2 Leaf dimensions: average length (mm) and confidence interval (at 95% level) of the terminal leaflet per variety. For each year, the letters indicate significant differences between the varieties (LSD method, p < 5%).

	Variety		2009, greenhouse		2010, outdoors
		Number	Mean Confidence	Number	Mean Confidence
		of plants		interval	of plants	interval
	Tancary	6	79.9	[74.7 , 85.1] a	6	72.8 [71.4 , 74.2] a
	New Daily Mail	6	80.3	[78.1 , 82.4] a	6	71.1 [65.1 , 77.1] a
	Mullard Jubilee	3	83.7	[74.1 , 93.3] a	6	67.5 [61.6 , 73.4] a
	Kolima	6	48.7	[45.5 , 52.0] b	6	53.5 [48.7 , 58.4] b
	Starina	5	34.0	[32.7 , 35.2] c	6	30.0 [26.8 , 33.3] c
	Meiblam	5	27.1	[24.5 , 29.7] d	6	23.4 [20.2 , 26.5] d

Table 3 .

 3 Flower diameter (mm): mean and confidence interval (at 95% level) per variety. For each year, the letters indicate significant differences between varieties (LSD method, p < 5%).For Starina and Meiburenac, we considered all the flowers except the terminal ones. For Pink Wonder and Kolima, we considered all the flowers.

	Variety		2009, greenhouse		2010, outdoors
		Number	Mean Confidence	Number	Mean Confidence
		of plants		interval	of plants	interval
	Pink Wonder	6	84.8	[78.9 , 90.6] a	6	83.7 [80.3 , 87.1] a
	Kolima	6	73.9	[69.6 , 78.1] b	6	82.5 [80.1 , 85.0] a
	Starina	5	48.9	[46.3 , 51.5] c	6	46.5 [45.2 , 47.8] b
	Meiburenac	5	47.1	[46.5 , 47.8] c	6	46.2 [44.2 , 48.3] b

Table 4 .

 4 Number of flowers (buds, open or withered flowers) per plant at the first flowering peak. Mean values with the same letters indicate that the corresponding varieties do not differ significantly at p<5%, using non-parametric test on ranks.

	Variety	2009, greenhouse			2010, outdoors
		Number	Mean (standard		Number	Mean (standard
		of plants	deviation)		of plants	deviation)
	Meiburenac	5	104.5 (30.3) a	6	212.7 (94.2)	a
	Kolima	6	23.7 (2.3)	b	6	32.7 (8.0)	b
	Meichim	5	11.6 (4.9)	c	6	23.3 (13.9)	bc
	Sweet Promise	6	15.2 (3.1)	c	6	17.2 (5.3)	c

Table 5 .

 5 Floribundity measurements of 3 rosebushes per variety (2010, outdoors) using the sensory methodology: mean rank according to the quantity of flowers, mean rank according to the relative area occupied by the open flowers and mean score for the flowering level. Mean values with different letters indicate that the corresponding varieties are significantly different at p<5%, using non-parametric tests on ranks.

	Variety	Number		Mean rank	Mean score (1 to 9
		of	(increasing order from 1 to 12)	scale) for flowering
		measures	Quantity	Relative area occupied	level
			of flowers	by the open flowers
	Meiburenac	48	10.8	10.0	7.8 (1.0)	a
	Kolima	48	6.9	7.0	6.7 (1.2)	b
	Sweet Promise	48	4.3	4.9	4.8 (2.1)	c
	Meichim	48	4.0	4.1	4.4 (2.2)	d

. Daylength was extended to 16 h. From March to September 2009, corresponding

Acknowledgements

We thank the experimental domain team (INEM) of Agrocampus Ouest, Angers, who took great care of the roses, the people who helped us to take the photographs, all the judges who assessed the rosebushes, Morgan Garbez who introduced us to the use of ImageJ software for our image analyses and Michel Laffaire, recently retired, for his work and advice during the three years of experimentation.

Abbreviations

UPOV: International Union for the Protection of New Varieties of Plants Table 6. Spearman correlations between the 3 sensory measurements on photographs of the plants (Table 5), the relative area occupied by the flowers measured by ImageJ and the number of flowers counted on the real plants on the days when the photographs were taken.

Measurement

(


Nicolas Durand
email: durand@tls.cena.fr

Jean-Marc Alliot
email: alliot@tls.cena.fr

Une méthode de Branch and Bound par Intervalles appliquée à la résolution en vitesse de conflits aériens

Introduction

Deux avions en croisière à la même altitude séparés de moins de 5 miles nautiques sont dits en conflit. Le rôle du contrôleur aérien est d'éviter les situations de conflits en anticipant des manoeuvres de séparation (changement de cap ou de niveau de vol de l'un des deux avions). En modifiant légèrement les vitesses des avions, on peut résoudre les conflits aériens en amont, et ce à l'insu du contrôleur qui n'est pas perturbé par ce prétraitement. Le projet ERASMUS [START_REF] Bonini | How erasmus can support an increase in capacity in[END_REF] qui a introduit ce concept se base actuellement sur un algorithme évolutionnaire développé dans les années 90 sur le simulateur CATS [START_REF] Granger | Optimal resolution of en route conflicts[END_REF]. Le problème de résolution de conflits est un problème très combinatoire. La littérature ne propose que deux approches efficaces pour résoudre de façon centralisée des problèmes de grande taille (plus d'une vingtaine d'avions). L'approche de [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF] utilise la programmation linéaire mixte, mais requiert des hypothèses fortes sur les trajectoires (vitesses constantes, manoeuvres exécutées en même temps). L'approche par algorithme évolutionnaire [START_REF] Durand | Genetic crossover operator for partially separable functions[END_REF] est plus ancienne et permet de prendre en compte des trajectoires issues d'un simulateur de trafic. Ce résumé a pour but de présenter un algorithme de Branch and Bound par Intervalle, tel que décrit par exemple par [START_REF] Hansen | Global optimization using interval analysis[END_REF], adapté à un problème de résolution de conflits en vitesse. Un problème "jouet" est utilisé pour tester l'algorithme. n avions sont disposés sur un cercle et se dirigent vers le centre du cercle.

Modélisation du problème

Les avions volent à vitesse et altitude constante, et on peut modifier à l'instant 0 leur vitesse en restant à l'intérieur d'un intervalle autour de la vitesse nominale de l'avion (par exemple dans une fenêtre allant de -6% à +3% si l'on reprend les hypothèses du projet ERASMUS). On veut minimiser le changement de vitesse de chaque avion, tout en respectant les contraintes de séparation entre les avions. Si l'on note pour chaque avion i, v i sa vitesse, et m i le pourcentage de modification de sa vitesse, on veut minimiser f (m 1 , m 2 , ..m n ) = n i=1 m 2 i , tout en respectant les contraintes de séparation des trajectoires. La fonction d'inclusion naturelle de f utilisée pour l'algorithme de Branch an Bound peut s'exprimer :

F (M 1 , M 2 , ..M n ) = n i=1 M 2
i où M i est un intervalle de modification de vitesse possible pour l'avion i.

On veut garantir que pour tout couple d'avions (i, j) et tout temps t ≥ 0, les positions x i (t) et x j (t) sont séparées d'une distance d appelée norme de séparation. Si on note p i et p j les positions des avions i et j à t = 0 alors x i (t) = p i + t m i v i et la contrainte s'exprime : ( x i (t) -x j (t)) 2 -d 2 ≥ 0. Il ne reste alors plus qu'à résoudre une équation du second degré pour vérifier qu'il n'y a pas de racine positive. L'algorithme de Branch and Bound doit être capable de déterminer si un vecteur d'intervalles :

-satisfait les contraintes de séparation : il faut que pour tous les couples (i, j) et les modifications de vitesses dans les intervalles M i et M j , les avions soient séparés. On peut alors réduire (M 1 , M 2 , ..., M n ) au point qui minimise f dans (M 1 , M 2 , ..., M n ). -ne satisfait pas les contraintes de séparation : il suffit que pour un couple (i, j) et toute modification de vitesse dans les intervalles M i et M j , les avions i et j soient toujours en conflit. On peut supprimer le vecteur d'intervalles concerné. -n'est pas dans l'un des deux précédents cas : il faut alors conserver le vecteur d'intervalles tout entier, il sera subdivisé en deux nouveaux vecteurs d'intervalles. Vérifier la contrainte de séparation pour deux intervalles M i et M j est assez simple. Il s'agit de mesurer la distance entre deux segments dont la taille augmente linéairement avec le temps et qui se déplacent à vitesse constante sur deux droites représentant les trajectoires des avions. La comparaison des positions extrêmes des segments et un test de croisement permettent de calculer rapidement les distances de séparation minimales et maximales atteintes.

RésultatsL'algorithme de Branch and Bound par Intervalles permet de résoudre efficacement des instances de problème allant jusqu'à six ou sept avions. Au-delà, les temps de calcul deviennent très importants. Plusieurs stratégies ont été testées pour calculer l'estimateur du meilleur point atteint et aussi pour classer les vecteurs d'intervalles dans la liste des intervalles restant. Il reste de nombreuses pistes à explorer pour essayer d'atteindre des performances au moins égales à celles des autres approches citées en introduction, on peut notamment s'intéresser à des stratégies spécifiques de découpage et de classement des intervalles qui favorisent l'emergence de la solution optimale.


Pietro Belotti

Sonia Cafieri
email: sonia.cafieri@enac.fr

Jon Lee

Leo Liberti
email: liberti@lix.polytechnique.fr

On the convergence of feasibility based bounds tightening

Keywords: spatial Branch-and-Bound, range reduction, lattice, fixed point, MINLP, global optimization, constraint programming

Introduction

Global Optimization and Mixed-Integer Nonlinear Programming problems such as min{f (x) | g L ≤ g(x) ≤ g U ∧ x L ≤ x ≤ x U ∧ ∀j ∈ Z (x j ∈ Z)}, where f : R n → R, g : R n → R m , g L , g U ∈ R m , x L , x, x U ∈ R n and Z ⊆ {1, . . . , n}, ⋆ Financial support by grants System@tic "EDONA", ANR 07-JCJC-0151 "Ars", ANR 08-SEGI-023 "Asopt", Digiteo Emergence "Paso" is gratefully acknowledged.

are usually solved to ε-guaranteed approximation by the spatial Branch-and-Bound (sBB) algorithm [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF], a variant of the usual Branch-and-Bound for dealing with nonlinear, possibly nonconvex f, g. Since the gap between the original problem P and its convex relaxation P is both to integral variable restrictions being lifted as well as nonconvex functions being replaced by a convex relaxation, sBB is able to branch at continuous variables as well as integer ones. If x solves P , the standard disjunction used at a node in the sBB search tree is x j ≤ xj ∨ x j ≥ xj , the more usual one x j ≤ ⌊x j ⌋ ∨ x j ≥ ⌈x j ⌉ being used only if j ∈ Z.

At any sBB node, it is important to make sure that the variable ranges x L ≤ x ≤ x U for that node are as tight as the constraint restrictions g L ≤ g(x) ≤ g U allow. Letting F(P ) be the feasible region of P , we would wish to replace

X 0 = [x L , x U ] with X = [x L , xU ] such that xL i = min x∈F (P )
x i and xU i = max x∈F (P ) x i for all i ≤ n. Since these 2n problems are as hard as P , we relax these requirements. There are two standards relaxations: Optimization Based Bounds Tightening (OBBT) [START_REF] Caprara | Global optimization problems and domain reduction strategies[END_REF][START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF] and Feasibility Based Bounds Tightening (FBBT) [START_REF] Andersen | Presolving in linear programming[END_REF][START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF]. The former consists in replacing F(P ) with F( P ). The latter, whose convergence properties are the object of this paper, is also known in Constraints Programming as a range reduction device. FBBT relies on interval arithmetic to derive the constraint ranges Ḡ = [ḡ L , ḡU ] implied by the variable ranges X 0 at a given sBB node

; if Ḡ G 0 = [g L , g U ],
FBBT uses inverse interval arithmetic to propagate G 0 back to tightened variable ranges X ′ . This basic FBBT step is iterated until convergence, generating an interval sequence X 0 , X 1 , . . .. Since OBBT is usually slower than FBBT, OBBT is only applied at the root sBB node and FBBT is applied at each node. Furthermore, to simplify inverse interval arithmetic, FBBT often only considers a subset of linear constraints in g. We shall therefore make the assumption -without excessive loss of generality -that the symbol g denotes the linear constraints of P , which we denote as g L ≤ Ax ≤ g U for some m × n matrix A.

The main trouble with FBBT is that its worst-case running time is infinite in the size of its input (m, n, X 0 , A, G 0 ). For example, on the instance (2, 2, ([0, 1], [0, 1]), ( a -1 1 -a ), ([0, 0], [0, 0])), FBBT yields the infinite interval sequence ([0, 1/a 2k-1 ], [0, 1/a 2k ]) whenever a > 1. Enforcing finite convergence by terminating at the first iteration k such that L (X k-1 △X k ) ≤ ε, where ε > 0 is given and L is the Lebesgue measure in R, yields a finite but unbounded worst-case time complexity: given a fixed iteration bound K there are always instances where the FBBT takes longer than K iterations to reach the ε termination condition (it suffices to decrease the value a appropriately). In practice, such occurrences are far from rare, specially when the coefficients of Ax are obtained by previous floating point operations, which might cause a small but positive |a i -a j | even if a i , a j are supposed to be equal.

In this paper we propose a new method for finding the limit point of the FBBT sequence in polynomial time, based solving a Linear Program (LP) modelling the greatest fixed point of the FBBT in the interval lattice.

Fixed points in the lattice

A lattice is a set Λ partially ordered by the relation ⊑ endowed with two operations ⊔ (join), ⊓ (meet) such that x ⊑ x ⊔ y, y ⊑ x ⊔ y and x ⊓ y ⊑ x, x ⊓ y ⊑ y. A lattice is complete if there exist elements ⊥, ⊤ such that ⊥ ⊑ x ⊑ ⊤ for all x ∈ Λ. An operator F : Λ → Λ is monotone if x ⊑ y implies F (x) ⊑ f (y) and deflationary if F (x) ⊑ x for all x ∈ Λ. The set of all real intervals forms a lattice I under set inclusion ⊆, with set intersection ∩ as meet and interval union (smallest interval including two intervals) ∪ as join. The lattice structure is extended to arrays of intervals in the standard way. In the rest of the paper, we let X be the interval vector (X 1 , . . . , X n ) ∈ I n and

G = (G 1 , . . . , G m ) ∈ I m .
FBBT consists of two phases: upwards and downwards propagation. We define up : I n → I m and down : I m → I n as:

up(X) = (G 0 i ∩ j≤n a ij X j | i ≤ m) (1)
down(G) = i≤m (X j ∩ 1 a ij (G i - ℓ =j a iℓ X ℓ ) | j ≤ n), (2)
where all arithmetic operators have interval semantics [START_REF] Moore | Introduction to Interval Analysis[END_REF]. We now define the FBBT iteration as an operator fbbt : I n → I n by fbbt(X) = down(up(X ∩ X 0 )) (we remark that our definition of fbbt depends on the initial interval vector X 0 ). Because all linear interval arithmetic and lattice operators are monotone [START_REF] Moore | Introduction to Interval Analysis[END_REF] and the composition of monotone operators is monotone [START_REF] Roman | Lattices and Ordered Sets[END_REF], fbbt is a monotone operator. Furthermore, because of the intersections, intervals are changed only if the up and down actions make them smaller. Again, the composition of deflationary operators is deflationary [START_REF] Roman | Lattices and Ordered Sets[END_REF]: hence fbbt is deflationary. By applying Thm. 12.9 in [START_REF] Roman | Lattices and Ordered Sets[END_REF] to the dual lattice obtained by inverting ⊤ and ⊥, ⊑ and ⊒, meet and join, we have that the sequence (fbbt k (X) | k ≥ 0) converges to the greatest fixed point (gfp) of fbbt, i.e. the largest (in the lattice order) interval vector X such that fbbt(X) = X. In other words gfp(fbbt) = sup{X | X = fbbt(X)}. By Tarski's Fixed Point Theorem [START_REF] Tarski | A lattice-theoretical fixpoint theorem and its applications[END_REF], equality can be replaced with ⊆. Furthermore, the operator | • | : I n → R given by |X| = j≤n (x U j -x L j ) is monotone with the lattice order; since the lattice is complete, we obtain:

gfp(fbbt) = argmax{|X| | X ⊆ fbbt(X)}, (3)
which we state as the following "interval linear problem" with parameters (m, n, X 0 , A, G 0 ) and interval decision variable arrays X, G:

max{|X| | X ⊆ X 0 ∧ G ⊆ up(X) ∧ X ⊆ down(G)}, (4)
It is possible to write an ordinary LP whose optimal solution is same as (4).

Computational validation

By way of preliminary computational validation of our approach, we solved four significant instances using CPLEX 11.0 [START_REF] Ilog | ILOG CPLEX 11.0 User's Manual[END_REF] on an Intel Core 2 Duo 1.4GHz with 3GB RAM running Linux. For each instance we record the gfp, the seconds of user CPU time to solution with either method, the absolute error E = j≤n L (X * △gfp(fbbt)) where X * is the output of either method (ε FBBT = 10 -6 ), and the relative error R of the FBBT obtained by letting it run only for as long as the LP method takes to converge to the (precise) gfp's.

Instance x 1 -1.01x 2 = 0 -1.01x 1 + x 2 = 0 x 1 , x 2 ∈ [-1, 1] x 1 -1.01x 2 = 1 -1.01x 1 + x 2 = -1.01 x 1 , x 2 ∈ [-1, 1]
x 1 -1.01x 2 = 0 -1.01x 1 + x 2 = 0 x 3 + 100x 1 ≥ -100

x 1 , x 2 ∈ [-1, 1], x 3 ∈ [-10, 1]
x 1 -1.01x 2 = -1.01 -1.01x

  1 + x 2 = 1 x 3 + 100x 1 ≥ -100 x 1 , x 2 ∈ [-1, 1], x 3 ∈ [-10, 1]

	gfp	([0,0],[0,0])	([1,1],[0,0])	([0,0],[0,0],[-10,0])	([0,0],[1,1],[-10,0])
	CPU FBBT	0.04	0.04	0.06	0.06
	CPU LP	0	0	0.004	0.004
	E FBBT	1e-4	5e-5	1.5e-6	5e-5
	E LP	0	0	0	0
	R FBBT	2.29	1.47	2.33	1.21


Mathieu Rayna1
email: raynal@irit.fr

Jean-Luc Vinot
email: vinot@cena.fr

Philippe Truillet
email: truillet@irit.fr

Fisheye Keyboard: Whole Keyboard Displayed on Small Device

Keywords: ACM Classification: H5.2 [Information interfaces and presentation]: User Interfaces. -Graphical user interfaces, Input devices and strategies, Interaction styles soft keyboard, ultra mobile PC (UMPC), fisheye view

In this article, we propose a soft keyboard with interaction inspired by research on visualisation information. Our goal is to find a compromise between readability and usability on a whole character layout for an Ultra mobile PC. The proposed interactions allow to display all keys on a small screen while making pointing easier for the user by expanding any given key as a function of its distance from the stylus.

INTRODUCTION

With the widespread use of mobile devices, text input technique has become an active research area and new constraints have appeared: restricted display, devices intended for single hand use, etc. As yet, these systems lack a dominant technique for text input. There are two principal research directions: on the one hand, systems based on gestures recognition similar to handwriting; on the other hand, soft keyboards for touch screens. For soft keyboard, stylus interaction consists of either typing on the keys like the Metropolis keyboard [7], or producing gestures like Quikwriting [5].

Both gesture recognition and soft keyboard present disadvantages. For recognition systems, handwriting requires learning a gesture alphabet, which can be a huge limit for novices. For soft keyboards, novice users have difficulties finding and/or tapping characters (especially for non alphabetic characters) on the device. When all characters are displayed, reduced space in the screen of an UMPC (7" of diagonal), makes pointing difficult. One solution is to display the entire keyboard on different pages accessible by tapping on a special key. With this method, keys are bigger but novice users waste time to find characters on the different pages.

In order to avoid this drawback, we propose new interactions on whole soft keyboard based on animation (as expanding targets or fisheye view) in order to reduce pointing time and error rate. Our hypothesis rests on the fact that a user might well prefer to enter text on a known character layout rather than on a minimal soft keyboard where he must sometimes search for a character or press several keys to enter one given character. Moreover, several studies as [4] show that we can reduce pointing time by using expanding target. Two text input systems used expanding targets [START_REF] Cechanowicz | Stylus based text input using expanding CIRRIN[END_REF]6] but the character layouts are not the classic AZERTY or QWERTY and do not display all characters in the same page.

FISHEYE KEYBOARD

We reproduced a whole soft keyboard (see Figure 1) while keeping analog characters layout as Windows soft keyboard. Each "classic" key measure 10x10 pixels: the width of our whole keyboard is 240 pixels. In the passive state, characters are too small to be legible for the user. Nevertheless, the characters layout on the keyboard being known, an expert user is able to locate a character approximately. When the stylus is in contact with the screen, keys expand as a function of their distance from the stylus: the closer the stylus, the larger the key.

We tested two animation types for expanding keys. The first one was based on the principle of the expanding targets suggested by [4]. The first proposition was to expand each key according to the distance between its center and the stylus. The biggest keys were displayed in the foreground. In order to prevent the biggest keys from covering up others keys, the latter were moved slightly aside. Thus, users could easily read characters that were close to the stylus.

The second animation was based upon researches on visualization information, most notably on fisheye view [START_REF] Carpendale | A Framework for Unifing Presentation Space[END_REF]. Separate keys were not enlarged as a whole but each vertex and main points of the soft keyboard were translated. The translation is bounded by 0 and the distance between the stylus and the point under consideration.

We chose, for expanding the keys, a technique at the intersection of the two techniques presented above, because both presented a major disadvantage: with the first technique, the keys which were farther from the pointer were partly covered by the largest keys; with the second technique, the keys were not covered up by other keys, but, certain keys could be tilted, and then the characters on these keys were not readable.

In our final design, neighboring keys are expanded according to the distance which separates the center of the target key and the stylus hovering over the screen. The spacing of the keys is calculated by using a Gaussian function: thus, the keys are always flat and outspread for a better legibility. In order to test this last design, we conducted an experiment comparing our prototype with typical AZERTY keyboard. The main hypothesis was that the deformation of the keys when the stylus is close would not reduce users' performances. We define as performance of the user his text input speed and his accuracy.

EXPERIMENT FISHEYE KEYBOARD

Six participants, three female and three male, took part in the experiment. They ranged in age from 20 to 38. There were five right-handers and five computer specialists. The experiment was conduct on an OptiPlex GX620 DELL PC running Microsoft Windows XP. A tablet Wacom was attached to the system and was the only device used by participants. Users used a stylus to interact with the soft keyboard. We chose for this experiment to restrict us to a soft keyboard which contained only the 26 characters of the Latin alphabet and the space bar. The soft keyboard was developed with Java. First, in the training session, subjects had to type 12 words with fisheye system. Then, they realized two exercises of word copy: one exercise with the AZERTY keyboard without fisheye animation, and the other with Fisheye. For each exercise, the subject had to copy out 30 words, which were the same for the two exercises. Words were chosen as the most usually used in French and as to represent a maximum of different co-occurrences. The six subjects were divided in two groups in order to counter-balance the order of the exercises. The word to be copied was presented on a line, and the word being typed by the user appeared on the line below. The text entry errors were not displayed on the screen. Instead there was a visual and audio feedback signaling the error and the strip did not move until the subject entered the right character. At the end of each word, participants had to hit the space bar.

RESULTS AND DISCUSSION

Data show that the order in which the exercises were performed had no impact on the results. On average, participants entered the twenty words in 225 seconds (that is to say 1.02 cps) with the soft keyboard without animation, whereas they needed only 153 seconds (1.5 cps) with the Fisheye keyboard. Thus they gain on average 25% of time with the keyboard fisheye relatively to the standard keyboard. Moreover, 5 subjects out of 6 had better performances with the keyboard fisheye. During the exercises, when the current character differed from the expected character, the error was recorded. The average was 15.67 errors for soft keyboard without animation (that is to say an error rate of 6.81%) and 11.67 errors (5.07 %) with fisheye keyboard. Distance (in pixels) was also computed in every situation: results show that distance was 14.85% less with fisheye keyboard than standard keyboard (11256 pixels versus 13219). Thus, for each participant, distance was minimized with Fisheye keyboard.

FUTURE WORK

Figure 1 :

 1 Figure 1: animation applied on fisheye keyboard when the stylus is closest to the key 'T'

  These animations are intended for use on several hand-held devices. For technical reasons, we implemented this first version of our prototype on a Tablet PC. At the present time, we are working on a PDA version. Continuous stylus-based text entry. In Proceedings of the 11e annual ACM symposium on User Interface Software and Technology -UIST'98, 1998, pp. 215-216, ACM Press 6. Ward, D. J., Blackwell, A. F., MacKay, D. J.: Dashera data entry interface using continuous gestures and language models. In Proceedings of the 13th Annual ACM Symposium on User interface Software and Technology -UIST'00 7. Zhai, S., Hunter, M. & Smith, B.A. The metropolis keyboard -an exploration of quantitative techniques for keyboard design. In Proceedings of the 13th virtual annual ACM symposium on User Interface Software and Technology -UIST'00, ACM Press, 2000, pp. 119-128

	4. McGuffin, M., Balakrishnan, R.: Acquisition of
	expanding targets. In Proceedings of the ACM
	Conference on Human Factors in Computing Systems -
	CHI'02, 2002, pp. 57-64, ACM Press
	5. Perlin, K.: Quikwriting :