E Kerrien

O Lévrier

MD R Anxionnat

MD S Sauty

J Knoplioch

Automated registration of 3D X-ray angiography images to magnetic resonance images

Keywords: 3D X-ray angiography, Magnetic Resonance Imaging, registration

An automated algorithm for frameless registration of intra-cranial 3D X-ray angiograms (3DXA) to Magnetic Resonance (MR) images is described and evaluated. The registration procedure starts with the manual designation of a pre-defined anatomical point in both modalities. Then, the registration is performed through an iterative process that alternatively estimates the rotation and translation using an original correlation optimization scheme. The evaluation procedure implied comparisons with both manual (11 cases) and stereotactic frame based (9 cases) registration. The results encompass that manual registration is not a viable method of reference for registering such volumes whereas stereotactic frame (or equivalent means) is acceptable for validation purpose. A maximum error of 4 mm was measured for our automated algorithm while variations of up to 5 mm were considered on the initial point location. Convergence time was below 1 minute while an average time of 30 minutes was required to perform manual registration. This validation procedure demonstrates a good precision for the automated algorithm when compared to a stereotactic frame based matching. Such an algorithm could make the intra-cranial pathology assessment more reliable, enable frameless radiotherapy planning of AVMs in 3D, ease biopsy planning in neurosurgery or be helpful for educational purpose.

Introduction

In the course of their dayly practice, interventional neuroradiologists and neurosurgeons make use of many different imaging modalities to diagnose pathologies, treat them and follow the patients up. In particular, the vascular pathologies, such as aneurysms, arterio-venous malformations (AVM) or fistulae, or related pathologies, such as intra-cranial tumors, demand that the surgeon has a precise knowledge of the vasculature, the tissues surrounding the pathology and the functional role of these regions. Since no single modality is able to provide all this information at once, the simultaneous analysis of multiple types of images is required. As a result, the need for registration algorithms is becoming more and more crucial for the healthcare community, especially for the management of neuropathologies.

Digital Subtracted Angiography (DSA) images are the cornerstone of interventional neuroradiology. Lately, neuroradiologists have been using in clinical routine Three-dimensional X-ray Angiography (3DXA) images of the brain vasculature. Such volumetric images have been proven to bring an actual supplementary help to the physician [START_REF] Anxionnat | 3D angiography: clinical interest and first applications in interventional radiology[END_REF][START_REF] Anxionnat | Clinical value of three-dimensional digital subtraction angiography (3D DSA) in the therapeutic decision and endovascular treatment of intracranial aneurysms[END_REF]. Even though some studies are still needed, many previous works are available in a view to perform the registration of a DSA image with a 3DXA volume [START_REF] Alperin | Retrospective registration of X-ray angiograms with MR images by using vessels as intrinsic landmarks[END_REF][START_REF] Feldmar | 3D-2D projective registration of free form curves and surfaces[END_REF][START_REF] Kita | Real-time registration of 3D cerebral vessels to X-ray angiograms[END_REF][START_REF] Liu | 3D/2D registration via skeletal near projective invariance in tubular objetcs[END_REF][START_REF] Kerrien | Fully automatic 3D/2D subtracted angiography registration[END_REF]. While DSA and 3DXA provide very precise and complete information on both the anatomo-morphology of the vasculature and the hemodynamics, no knowledge of the intra-cranial tissues can be extracted from such images.

On the other hand, Magnetic Resonance (MR) imaging is a powerful and unique tool that provides images with a very good spatial resolution and an excellent contrast on the soft tissues of the brain. However, the analysis of the vasculature is hindered by distortions, flow effects and the spatial resolution is still not high enough. Dedicated imaging protocols were developed to tackle part of these problems (Magnetic Resonance Angiography, MRA) but the price for these improvements is the loss of contrast on the brain tissue.

The ability to register a 3DXA volume and an MR exam would therefore help perform an accurate diagnosis of a vascular disease and provide complete information to the neurosurgeons to treat it. Furthermore, numerous works describe ways to match MRI data with Computed Tomography (CT) volumes, Positron Emission Tomography (PET) or Single Photon Emission Computed Tomography (SPECT) acquisitions and intra-cranial Echography (US) images. As a consequence, the MR modality appears as a footbridge to be used to match many imaging modalities, including 3DXA.

Material and Methods

Images

3DXA volumes are reconstructed using a tomography algorithm based on a set of about 50 DSA images. This set of images is acquired on a standard open C-arm (LCN+, GE Medical Systems) performing a rotation of about 200 degrees around the patient's head while a contrast dye is injected in the artery of interest. Reconstructions of both internal carotid and vertebral arteries are being considered.

The choice for the MR acquisition protocol was guided by two constraints:

in order for such images to be of interest, they have to show a good contrast for the brain soft tissues ; since a 3DXA volume only depicts the vasculature depending on the injected artery, the best possible accuracy on the brain vasculature was looked for so as to provide the registration algorithm with some information common to both modalities under study.

As previously stated, MRA cannot comply with the first requirement. As a result, we elected a T1 weighted protocol (giving good contrast on the brain tissue) enhanced by an intra-venous injection of gadolinium (highlighting the vasculature). MR images were acquired on two different systems (Signa 1.5T, GE Medical Systems and Magnetom Symphony, Siemens AG) to account for possible variations in image characteristics. High resolution images (512x512 or 256x256 matrix with a slice thickness of 1.5 mm) were used.

Registration techniques

Distortions in MR are known to be a potential problem. However, since the imaged portion of the body is relatively small (the head), we chose to neglect their possible impact on the registration. This mono-patient registration problem can therefore be seen as the search for a rigid-body transform. Basically, three groups of methods can be looked over: point-based, featurebased and voxel-based registration algorithms. The use of external markers presents many drawbacks, especially in terms of a higher complexity for the data acquisition and the impossibility to perform retrospective registration. On the other side, manual registration is particularly tedious in our case due to the difficulty to identify vessels in MR.

Since only blood vessels are visible in a 3DXA volume, a feature-based registration method would require the segmentation of vessels in both modalities. If this step would be rather straightforward in 3DXA, the difficulty of the task in a T1 weighted MR image is demonstrated by the lack of scientific work concerning this MR protocol on one side, and, on the other side, the many different solutions studied along the past few years to achieve this goal in MRA acquisitions, which yet depict the blood vessels in a rather clear manner [START_REF] Krissian | Model based detection of tubular structures in 3D images[END_REF][START_REF] Wilson | An adaptive segmentation algorithm for time-of-flight MRA data[END_REF][START_REF] Frangi | Model-based quantitation of 3-D magnetic resonance angiographic images[END_REF][START_REF] Chung | Fusing speed and phase information for vascular segmentation in phase contrast MR angiograms[END_REF].

Different robust similarity measures have been defined whose power has been demonstrated for registering MR, CT, PET and SPECT images [START_REF] Collignon | Automated multi-modality image registration based on information theory[END_REF][START_REF] Studholme | Automated 3D registration of MR and CT images of the head[END_REF][START_REF] West | Comparison and evaluation of retrospective intermodality brain image registration techniques[END_REF][START_REF] Roche | Towards a better comprehension of similarity measures used in medical image registration[END_REF]. If these modalities show sometimes important discrepancy, the depiction of global structures such as the skull, the cortex or the ventricles in all of them backs up the efficacy of such criteria in the neuro case. Similarity measures seemed the best available methods to perform 3DXA/MR registration. However, 3 problems had to be solved: initialization: the vasculature is literally drowned amidst the mass of information regarding soft tissues in MR, which requires a hint about where to find it in this modality; convergence: the tree-shape of the vasculature generates numerous local optima for the similarity measure; time: 3DXA volumes are coded on a 512 ¡ 512 ¡ 512 voxels cube and MR volumes are composed of either 124 or 174 images which are coded on a 512 ¡ 512 or 256 ¡ 256 matrix. This huge volume of data had to be processed in a very short time (less than 3 mn) for the algorithm to be acceptable in a clinical environment.

In the next section, the algorithm we designed to overcome these problems is described. Section 4 reports the study that was made to validate the use of a stereotactic frame and to reject the manual registration as a method of reference for the matching of a 3DXA volume with an MR acquisition. Section 5 provides the results of the evaluation of our registration algorithm in comparison with the technique using a stereotactic frame.

Registration algorithm

Initialization and hypothesis

The identification of a vessel bifurcation on the circle of Willis is very easy in MR as well as in 3DXA. This provides a fast and easy way to initiate the registration: the internal carotid bifurcation must be indicated in the case where the internal carotid artery is shown on the 3DXA volume, and the tip of the basilar tree has been chosen in the case where a vertebral artery was injected.

As a result, we can consider we have a good estimation of the translation part of the registration: an error of less than 3 mm should affect it (the size of the internal carotid artery is about 4-5 mm). Besides, the rotation is unknown but, except for very exceptional cases, its angle should be within ¢ 30 degrees.

Two other problems need to be addressed. On one hand, the convergence properties suffer from the sparseness of the vascular information in the volumes. On the other hand, the convergence time is likely to be long, due to the amount of data to process. As a consequence, the philosophy that we followed in designing the algorithm consisted in reducing the amount of data, through reducing their dimensionality, while preserving the relevant information.

Rotation estimation

Let's first assume that the translation is perfectly known through the knowledge of a pair of homologous points in both modalities (user-defined). The rotation remains to be recovered. Let's call a thick shell any set of voxels located between two spheres centered on the homologous pair of points. Any such set is globally invariant under any rotation centered on this pair of points. We extract in both modalities one such set which we truncate by removing a cone in the direction of the nose: sinuses show a contrast uptake in MR, which creates a large zone in hypersignal that attracts the arteries in the optimization process. Figure 1 depicts such thick shells in a 3DXA and an MR volumes.

In both sets of voxels, arteries appear in hypersignal. In a second step, a radial Maximum Intensity Pixel (MIP) projection of each thick shell onto their external surface is performed (figure 2(a)). These two steps allow for a dramatic reduction of data (voxels selection in a thick shell and projection onto a surface) while preserving relevant information (radial MIP projection).

A planar mapping of the external spheres was used to store the information resulting from the MIP projection as regular images. Each truncated sphere can be spanned by two angles: θ varying in £ ¥¤ π¦ π § around the x axis and ϕ varying in £ 0¦ ϕ max § (see figure 2(b)). A straightforward representation would be to define pixel coordinates ¨i ¦ j© such that i ∝ θ and j ∝ ϕ. This representation entails important distortions and, as a result, disbalances the amount of contribution of each area of the image in the calculations of the similarity criterion. A so-called "polar" representation was preferred: the origin being at the center of the image, θ is the polar angle in the image plane and ϕ is proportional to the modulus (see figure 2(b)). If we consider a point P ¨x ¦ y¦ z© on the external sphere. The radius of the sphere is unimportant. As a result, the corresponding pixel ¨i ¦ j© is determined by (N is the size of the image in pixels):

x ¤ cos ϕ y ¤ sin ϕ cos θ z sin ϕ sin θ ϕ arccos¤ x© cos θ ¤ y sinϕ sin θ z sin ϕ i N 2 1 ϕ ϕ max cos θ! j N 2 1 ¤ ϕ ϕ max sin θ! (1)
In the case where ϕ 0, cos θ and sin θ are undefined but the singularity is easily overcome by setting the corresponding pixel at the center of the image The inverse formulae can be determined:

" P on the external sphere

$# ρ 2 2i N ¤ 1! 2 2 j N ¤ 1! 2 % '& 1 ϕ ρϕ max cos θ 1 ρ 2i N ¤ 1! sin θ 1 ρ 2 j N ¤ 1! (2)
Once again, these formulae are not determined at the center of the image (ρ 0) but the case is easily overcome. These direct and inverse formulae allow for a simple calculation of the warping implied in the image plane by a rotation of the external sphere: pixel ¨i ¦ j© in the image corresponds to point ¨x ¦ y¦ z© (inverse formulae) which is rotated to point ¨x( )¦ y( 0¦ z( ¥© which itself corresponds to pixel ¨i( )¦ j( 1© (direct formulae).

An example of the images obtained through this process is shown on figure 3(a) and 3(b): they appear as seen by an observer with a 2ϕ max vision angle, located at the center of the thick shells. We can see that the images are still somewhat different. In order to enhance their similarity, a simple tophat operator is applied, leading to images as shown on figure 3(c). The rotation is recovered by optimizing the centered normalized cross-correlation between the images, while spanning warpings corresponding to rotations in the 3D space.

Translation estimation

Now assuming we have a good estimate of the rotation, the error in the manual initialization of the translation must be corrected. In that case, there is no need for knowing the whole volume information to estimate the translation: a subvolume, if correctly chosen, should be enough. Since the homologous pair of point is required to correspond to some artery bifurcation, the local shape of the arteries constraints the translation to a unique value. As a consequence, a sub-cube is extracted surrounding the manually indicated points: the cube dimensions are chosen so that the bifurcation is fully contained in the sub-cube and so that a small error on the rotation can hardly be detected.

Once again, the amount of data is further reduced, while keeping all relevant information regarding arteries, thanks to a MIP projection of the cube along three orthogonal directions: axial, sagittal and coronal. Examples of the images obtained are shown on figure 4. Since the analysis is made locally, the background in MR is rather uniform. This results in very similar images that do not require any pre-treatment.

The similarity criterion we used is the sum of the three cross-correlation scores calculated for the axial, sagittal and coronal images respectively. The translation is recovered when this criterion is maximal.

Algorithm scheme

The Euler angles are used as parameters for the optimization steps of the rotation estimation. The thick shells are defined as lying between spheres centered on the homologous pair of points with radii of 20mm and 40mm. A value of 150 degrees is used for ϕ max . The translation vector is used as parameters for the translation recovery. Sub-cubes of 16mm ¡ 16mm ¡ 16mm are extracted. The overall algorithm scheme is the following: initialization: the user is asked to point the chosen artery bifurcation (internal carotid bifurcation or tip of the basilar artery) in both 3DXA and MR. This provides an initial translation and center points for the rotation. The rotation is estimated through an exhaustive search of the optimal criterion score between low resolution images of the thick shells (N 64) while each angle value vary in £ ¥¤ 30¦ 30 § degrees each 5 degrees. optimization: the translation and rotation are estimated in turn over three loops.

-translation: the similarity criterion is the sum of the three cross-correlation scores between the axial, sagittal and coronal images of the sub-cubes respectively. The cross-correlation scores are established in the Fourier space, which allows for a fast exhaustive optimization of the criterion: translation components are searched for in £ 2¤ 5¦ 5 § mm in a first step, the amplitude being divided by 2 at each loop.

-rotation: the similarity criterion is the normalized centered cross-correlation. The optimization is performed using a hill-climbing scheme also used by Studholme to optimize entropy-based criteria [START_REF] Studholme | Automated 3D registration of MR and CT images of the head[END_REF], which presents with very interesting convergence time. The initial step for the search is 5 degrees, divided by 2 at each loop. The projected image dimensions increase at each loop from N 128 to N 256 (last 2 loops).

The average computation time was estimated to be around 30 seconds (not counting the time necessary to load the volumes and manually indicate the initial pair of points), but no systematic measurements were performed since this time appeared to be far below our requirements (3 mn).

Repeatability

Determination of a registration method of reference

Prior to be able to validate this algorithm, we first need to define a measurement method that enables the comparison of the results of two different registration schemes. Then, a method of reference must be determined. In this regard, two point-based techniques were examined: the first requires the manual definition of pairs of homologous points in both modalities, the second is based on a stereotactic frame.

Measurement method

Since a priori the region of interest where the pathology lies in the images is unknown, we wish to be able to provide an upper limit on the error done over the whole volume of interest. This volume can be limited to the region of support of the 3DXA, which represents an intra-cranial artery and, as such, is always contained inside the region imaged in the MR volume.

As a consequence, the measure of comparison between two registration results is defined as the maximum registration error performed on the 8 corners of the cube enclosing the 3DXA volume (whose side is approximately 15 cm). In other words, if the ¨Ci © i3 54 16 6 87 are the 8 corners of the cube, the error between two registration results

D 1 8£ R 1 9 T 1 § and D 2 8£ R 2 9 T 2 § is: @ ¨D1 ¦ D 2 © A max i3 B4 16 6 87 DC FE R 1 C i T 1 ¤ R 2 C i ¤ T 2 E HG (3)

Evaluation of the manual registration as a method of reference

The manual registration allows for retrospective registration and do not require any special setup prior to data acquisition. These properties make such a method very attractive for validation purpose. However, this technique is very prone to error, in particular due to a lack of points and human errors in determining homologous points.

In order to evaluate if the manual method could be trusted in the 3DXA/MR registration case, an experiment was setup:

11 pairs of exams (3DXA/MR) were selected which presented with various pathologies (arterio-venous malformations, aneurysms, intra-cranial stenoses); three expert users, among which 2 senior neuroradiologists (EK, RA and OL) were asked to perform a manual registration on each case by indicating 5 pairs of homologous points; each user was required to perform two manual registrations on each case: a first pass was made over the whole set of 11 patients, then a second pass.

The repeatability was estimated by comparing registrations performed by the same user using the comparison measure defined in the previous paragraph (33 measures). The reproducibility was estimated by comparing registrations performed by different users (396 measures). The average, standard deviations and maximum errors are given in table 1 (in mm).

These results clearly show that the manual registration method cannot be used as a method of reference in order to validate an automated algorithm in the 3DXA/MR registration case.

Another interesting conclusion that can be drawn from this experiment is that two matches cannot be distinguished, in the average case, by a human operator, even a trained one, if the maximum registration error is below 5 mm.

Evaluation of the stereotactic frame as a method of reference

A database of 9 pairs of 3DXA/MR exams acquired with a stereotactic frame (Leksell frame) was built (8 patients). Automatic methods were used to detect the frame in both 3DXA and MR volumes. Nevertheless, the algorithm used in MR requires the user to point one of the markers on the frame (Leksell frame). As a result, some variability could be expected in that method.

In order to assess its extent, one user was asked to perform the frame detection five times on each MR exam. The registration results based on the frame detected were compared for each patient using the measurement defined above (10 measures per patient). The average measure, standard deviation and maximum value are reported on table 2 for each patient and the overall set of measures.

The results are very good: when evaluating a registration method using this frame-based matching technique as a reference, the amount of variation in the results that are due to the imperfections of the reference method do not exceed 0.1 millimeter, which allows for a high significance of an analysis of variance. In conclusion, the frame-based registration method is a good reference method for the 3DXA/MR registration problem.

However, these results do not demonstrate the absolute precision of the frame-based registration technique. Even though the frame-based method has been shown to be repeatable, there might exist some bias or imprecision in the detection of the markers. The distortions in MR are the major concern here. Luckily, the automatic detection algorithm provides us with some hint about the precision of the frame-based registration: the average error found on the frame markers is given as an output. Since the markers are located at the periphery of the head, this measure, though not exactly the same, can be linked with our measurement method. These figures are reported in table 3. These results are not surprising since the values are of the same magnitude as the resolution of the MR acquisitions (between 1 and 1.5 mm). However, they also mean that the comparison measure using the frame-based method as a reference has no absolute significance when the error found does not exceed 2 or 3 mm (the standard deviation of the error on the frame markers would be required to assess this more precisely).

Validation of the algorithm

Experimental setup

In the experiment, we used the same set of data as used to validate the stereotactic frame as a reference method. The initial point was indicated in each 3DXA volume on the predefined artery bifurcation. The homologous point in MR was calculated by applying the rigid-body transform making the match between the 3DXA and MR volumes according to the stereotactic frame. We call this point the ideal point.

A cloud of 50 points was generated for each patient, following a Gaussian random distribution with a standard deviation of 1.5 mm: at least one point in each cloud was located at more than 5 mm from the ideal point. These points simulate an expected user error when defining the initial point prior to running the algorithm. run for each simulated pair of points on each patient (450 runs) and the result compared to the registration obtained thanks to the stereotactic frame, using our measurement method.

Results

This experiment was designed to assess the performance of the algorithm in terms of precision and robustness.

We evaluated the robustness of the algorithm thanks to two figures. First, following the results on the manual registration evaluation, we defined a success threshold for the algorithm at 10 mm error: trials leading to an error above 10 mm are considered to have failed, others are successes. Second, the standard deviation of the error for the successful registrations provides us with a hint about the repeatability of the automated algorithm.

The precision of the algorithm was evaluated through the average error measured on the successful registrations. Table 4 reports the values obtained for each patient and the overall data set. The algorithm succeeded well for 6 patients out of 9, for a general success rate of 81.1%. The precision is very good on the successful patients, around 3 mm, and the algorithm robust: the standard deviation is below 0.5 mm for all successful patients except 1 (patient #6). If all successful registrations are included, the average error is of 3.31 mm for a standard deviation of 1.79 mm.

Patient #1 presents with a failure rate of 54%. A closer look at these data show a very bad MR image quality, in particular at the carotid bifurcation where the MR signal is almost totally lost. As a result, the translation estimation is perturbed a lot and fails most of the time.

Patients #4 and #8 present with a failure rate of 66% and 32% respectively. The situation here is different. The images used for the rotation estimation show two very close arteries (anterior cerebral arteries). Since only one of these arteries is imaged in the 3DXA volume, the criterion used for rotation estimation forms a surface with two main local optima (the artery seen in 3DXA is alternatively associated to one or the other anterior cerebral artery shown in MR). The algorithm is unable to differentiate between both optima at low resolution which implies that the initialization of the rotation leads to wrong angle values. In the case of patient #4, the local optima are further away from each other than for patient #8 which explains the higher failure rate in the first case, whereas the iterative optimization is able to correct for a wrong initialization in the second case and lower this rate.

Finally, patient #6 shows a large standard deviation (1.82 mm with respect to less than 0.5 mm). For this patient, 1 failure was reported (error above 10 mm) but the data show that 2 measures are above 9 mm, while the remaining 48 measures are below 3.25 mm. This false positive explains the outlier standard deviation.

Discussion

In the course of this study, we designed an original algorithm, based on the optimization of correlation based similarity measures, which addresses the problems the a priori analysis emphasized: initialization: the indication of a homologous pair of points by the user provides an easy way to obtain a pretty good estimate for the translation; convergence: the exhaustive search at low resolution on the mappings of the thick shells, enables to get close to the global optimal rotation; time: while we did not perform any specific study on the convergence time, the average time for the automated algorithm was below 30 seconds, while the expert users who contributed to the validation of the manual registration as a reference method, stated that a minimum time of 15 minutes was required to perform it on simple cases, with an average time of 30 minutes.

The automated algorithm was evaluated against a frame-based registration method on a set of clinical data (9 patients). Our algorithm presented with a good success rate and very good performances in terms of precision and robustness: the maximum registration error is below 4 mm with a standard deviation of less than 0.5 mm. Giving the intrinsic error estimated on the stereotactic frame arount 1 to 1.5 mm, this result makes our algorithm a valid way to perform 3DXA/MR registration.

As a conclusion, the algorithm we described in this paper is very promising for 3DXA/MR registration. However, our validation procedure pinpointed some remaining issues. The most important one that still needs to be addressed in further improvements concerns the management of local optima in the optimization of the rotation. Two ways are under study. On one hand, the tophat operator perturbs the correlation surface: other high-pass filters should be looked over. On the other hand, the low resolution image is obtained via a bilinear interpolation. Local optima should be better wiped out using Gaussian smoothing filter to lower down the resolution of images.

Figure 1 :

 1 Figure 1: Thick shell extraction

Figure 2 :Figure 3 :

 23 Figure 2: Mapping of a thick shell onto a plane

Figure 4 :

 4 Figure 4: Example results of MIP projections of subcubes in 3DXA (3 on the left) and MR (3 on the right)

Table 1 :

 1 Performance of the manual registration as a method of reference (figures are given in millimeters)

			Reproducibility	All
	Average error	4.48	4.94	4.85
	Standard deviation	3.08	3.75	3.62
	Maximum error	11.35	17.03	17.03

Table 2 :

 2 pat. #1 pat. #2 pat. #3 pat. #4 pat. #5 pat. #6 pat. #7 pat. #8 pat. #9 Performance of the frame-based registration as a method of reference (figures are given in millimeters)

	All

Table 3 :

 3 Average error on the frame markers at the end of the automatic detection of the frame in MR (figures are given in millimeters)

Table 4 :

 4 Performances of the automated registration algorithm compared with the stereotactic frame based method. Error measures (average and standard deviation) are given in millimeters and have been calculated by considering only the successful cases.

	The automated registration algorithm was

Proceedings of SPIE MedicalImaging 2001, K. Janson Ed., 18-22 February 2001, San Diego, vol. 4322 part 1, pp. 623-632.


Nathalie Fargier

In Search of a Sustainable Model for Digital Heritage Repositories: A Case Study

Introduction 1

A wide range of initiatives for developing research and data infrastructures have been funded in recent years. There is a growing concern amongst the academic community to maintain the resources invested beyond the period of the original research funding. If technical progress has been made to preserve the data themselves, few thinking and operational solutions exist for the institutions that create, disseminate, curate and preserve the data. How to ensure their existence over the medium or the long-term? This paper is a case study: it addresses the sustainability issues faced by Persée, a French platform dedicated to digitized documentary heritage that was launched in 2003. Through this example, the aim is to present, in practical terms, how an organization has to adapt and to change to sustain over time. Sustainability is a multi-faceted concept with no agreement on its means. For this paper, we define sustainability as "(a) the continued operation of an organization that offers data collections and services, (b) where operations relates to technology, preservation, users, institutional relations, business models, and other facets, (c) in the face of on-going internal and external challenges which may or may not be resolved, (d) where stakeholders recognize continuity in the mission, data sources, and value of the data repository, (e) while keeping in mind that each of those elements might evolve over time in response to (c)" [START_REF] Eschenfelder | Organizational Resilience in Data Archives: Three Cases Studies in Social Scien Data Archives[END_REF].

2

We will give some background elements about Persée (historical and institutional origins, main achievements). Then, we will examine the different and complementary aspects of the strategy that was implemented in 2011 after a major crisis. Persée responded to this funding and institutional challenge by enhancing its technical framework, by fostering the engagement of the research community and the collaboration with other platforms and infrastructures and by reshaping its strategy with the imperative to have reliable revenue sources to maintain its Open Access repositories. This experience shows that sustainability is not a steady situation but rather a continuous and resource intensive process for any organization.

Background elements

Persée was launched by the French Ministry of Higher Education and Research and Innovation (MESRI) in 2003 in order to develop a complete platform for the digitization, the documentation, the online publishing and the long-term preservation of back files of scientific journals in the field of humanities and social sciences. In 2005, the Persée portal ( www.persee.fr) opened with 7 journals. Currently, 184 partnerships exist with academic publishers and 740.000 full texts documents and 570.000 illustrations are available in open access.

The original purpose of Persée was expanded according two directions: a disciplinary openness (earth and life sciences in addition to HSS) and the offer of a new range of services. Persée provides software tools, its digital platform and expertise to the researchers and, leads some projects in the field of the Digital Humanities and Open Data.

• Perseids is the generic name of a range of websites developed by Persée in partnership with laboratories and heritage institutions as part of research projects. At the heart of a Perseid, there is a corpus that can be composed of primary sources, archives, grey literature, and published documents then, this content is digitized, precisely encoded and disseminated through a dedicated website with specialized index and tools for text analysis 1 . Emphasis is given to the standardization of item description and document structuring to ensure the use and the reuse of the data from the digitized sources.

• Data Persée (data.persee.fr) is the triplestore of Persée. All the metadata produced by Perséethrough the Persée portal or the Perseids -are available by exploring a graph. Some collections have been enriched with data from external repositories (idRef, GBIF, Geonames, BnF, Cairo Gazeetter, etc.) and the pairings are certified by the Persée team.

As far as the content is concerned, Persée focuses on the documentary heritage. As defined by the Memory of the Word Programme (UNESCO): a document is composed of the information content (signs, codes, sounds, images) and the support in which it is recorded (it can have a large variety of form, it can be conserved, reproduced and transported). These characteristics exclude elements that are part of a fixed structure such as a building or natural site. Persée deals mainly with the "collections of old, rare and valuable documents housed by the libraries" (Desgraves, 1982) that is to say printed document (in particular, but not exclusively, academic journals, books, proceedings), archives, grey literature, maps and iconography. Researchers' communities were closely associated to the definition of indexing methods and searching and visualization tools [START_REF] Fargier | Persée, for the promotion of French language scientific output in the human and social sciences[END_REF]. Therefore, the originality of the Persée portal relies on an accurate structured description at the article level and a set of tools that are similar to those associated to born-digital publications. Researchers can search full-text documents, browse through tables of content, articles layouts or lists of illustrations, use a cited-by linking service, export citations or explore different indexes.

Action plan in favor of sustainability

Point of crisis

Persée was launched as a project after a call for bids. It lasted beyond the start-up phase and entered an operational phase because it demonstrated the proof-of-concept and met the researchers' expectations. During this period, from a financial point of view, Persée was supported by the French MESRI and a host institution (a university). In 2011, this latter argued that it was not its mission to support a national platform as Persée, began to complain about the cost of such a support and cut funding. At the time, this university was covering approximatively 40% of Persée costs. There were two responses to this threat: an emergency one with actions taken by others outside of Persée and a long-term one with an internal change of strategy and governance. A consortium was set-up with the French MESRI and three academic institutions 2 . Complementary pathways ere identified to ensure Persée sustainability:

• the transformation from a digital library to a data and services infrastructure;

• a better inclusion within the existing landscape of research infrastructures, data repositories and digital platforms;

• the diversification of the financing resources.

This approach considered that various factors had to be combined (technical, social, financial, organizational) with reciprocal influence, to achieve sustainability [START_REF] Chowdury | Sustainability of digital libraries: a conceptual model and a research framework[END_REF].

Technical actions

Persée relies on open standards, open source technologies, open access and open data in order to warranty data storage, retrieval and preservation.

Considering that "technical sustainability is directly related to the standards and best practices followed when creating the digital files" (Fyffe and Warner, 2005), Persée developed an integrated open source software named jGalith. It manages every step of the process to convert printed documents to electronic format: from digitization, through documentation, quality control, XML schemas compliance check, to online publishing and long term preservation. Printed documents are collected from publishers then digitized in high quality resolution (400 dpi, bitonal and grayscale), post-processed (OCR, image quality improvement), encoded (toc, author, abstract, keywords, illustrations, footnotes, annexes...) and linked (crossRef). Each document (article, review, preamble...) is individually described and Author indexes created. The process ends with four outputs: the Persée portal or the Perseids (bibliographic data + image mode + TEI + enriched PDF + index), the triplestore (RDF), the OAI-PMH (METS, MODS, DC) and the long term archive (OAIS model with PNG and XML files). image which is based on quality and reliable service.

In Search of a Sustainable Model for Digital Heritage Repositories: A Case Study ELPUB 2018

Involving users' community

In 2011, the adequacy with researchers' needs was a key argument for maintaining Persée activity (the Persée Portal welcomed 17M visits in 2011 et 40M in 2017). The current phase is a further step to build a community that values, and not only uses, Persée services. It consists in setting up a large network of experts and a user committee. They will intervene at various levels: prioritization of materials to be digitized, feedback on new services and shared discussion about next steps. Users can be researchers or librarians and archivists from heritage institutions. In this way, Persée aims to show that its digitized content and services are clearly valuable and relevant for the academic community.

Another aspect to consider is the ability of Persée to develop relationships with other data repositories or infrastructures. Since the very beginning, a technical interoperability was established with the major francophone publishing platforms (Open Edition, Erudit and Cairn). The ongoing issue is to be interlinked with repositories and thesaurus more specialized 3 .

Strengthening institutional supports

Since 2011, Persée has been strengthening its lobbying. In 2013, Persée was created as a joint unit service supported by three major French universities and research organization. In 2016, Persée has been included in the French roadmap for the Research Infrastructures (RI) with CollEx (Collections of Excellence from academic and heritage libraries). This new infrastructure called CollEx-Persée aims at increasing the visibility, improving the access and promoting the use by researchers of the large collections held by research libraries and heritage institution. Persée is the key operator of this RI both for coordinating the digitization programs with researchers and managing scholarly enhancement and online dissemination of digitized corpora. In 2017, Persée was acknowledged as a French contributor to the European consortium DARIAH.

Towards a business model?

Developing a reliable revenue is the most challenging issue as Persée faces a twofold difficulty: building and maintaining, with an extensive level of curation, OA repositories of digitized documentary heritage without any payment-for-use.

We examine different funding models for OA digital data repositories (Kitchin, Collins and Frost-2015) and we identified four funding streams for Persée:

• Institutional revenue
The French MESRI provides the core operational costs through an annual subvention. And the members of the joint unit service pool human resources and funding, and facilitate capacity building.

• Philanthropic revenue

Persée applies for endowment for private companies.

• Research grants

Persée applies to research grants from national and European sources, with overheads to fund core services.

In Search of a Sustainable Model for Digital Heritage Repositories: A Case Study ELPUB 2018

• White-label development With the Perseids, Persée provides a customized service for the research laboratories and the heritage institutions. Each Perseid is powered by Persée (hardware, software and expertise) and, it is tailored and branded for a specific need and entity. The researchers pay one-off fee for subscription and includes maintenance and update costs. 17 In addition, Persée looks at another possibility with the fundraising on a voluntary basis including crowdsourcing.

ABSTRACTS

A wide range of initiatives for developing research and data infrastructures have been funded in recent years. There is a growing concern amongst the academic community to maintain the resources invested beyond the period of the original research funding. If technical progress has been made to preserve the data themselves, few thinking and operational solutions exist for the institutions that create, disseminate, curate and preserve the data. How to ensure their existence over the medium or the long-term? This paper is a case study: it addresses the sustainability issues faced by Persée, a French platform dedicated to digitized documentary heritage that was launched in 2003. Through this example, the aim is to present, in practical terms, how an organization has to adapt and to change to sustain over time. Persée tested and combined various mechanisms (technical actions, users' involvement, organizational evolution, marketing, funding models) with reciprocal influence, to achieve sustainability. Rather than a steady state, ensuring the long term existence of a data infrastructure is an ongoing and resource intensive process.

In Search of a Sustainable Model for Digital Heritage Repositories: A Case Study ELPUB 2018

  Conclusion 18 Launched in 2003, Persée is a French platform dedicated to the digitized documentary heritage. It produces, curates and disseminates online large amounts of digitized content for researchers' communities. It underwent different threats of funding by capitalizing on its technical ability and by changing its strategy. If Persée managed to exist beyond the first phase of its creation, its sustainability depends of a mix of technical, social, financial, marketing and political mechanisms strongly interconnected. Different fronts are openup simultaneously. The current situation can be described as a "temporary accomplishment" that is to say that "no institution is indefinitely sustainable (…) and sustainability is not a state of grace". Persée, as any institution, is always making adjustments to changing conditions and has more or less sustainable practices as far as funding, business planning, governance systems, organizational structure, etc. are concerned (Eschenfender, Shankar, 2017).

	French General Code of Public Entity Properties, L2112-1 10è.Available online: https://
	www.legifrance.gouv.fr/affichCodeArticle.do?
	idArticle=LEGIARTI000006361198&cidTexte=LEGITEXT000006070299
	Kitchin R., Collins S. , Frost D., (2015)."Funding models for Open Access digital data repositories",
	Online Information Review, vol. 39 Issue: 5: 664-681. https://doi.org/10.1108/OIR-01-2015-0031
	KnowledgeExchange.Sustainabilty Index (2012). Available online: http://
	repository.jisc.ac.uk/6223/1/OA_Sustainability_Index.pdf
	Maron, N. L., Pickle, S., & Marcum, D. (2013). Searching for Sustainability Strategies from Eight
	Digitized Special Collections. Ithaca, NY, 49p. https://doi.org/10.18665/sr.22647
	Rapport au directeur du livre et de la lecture sur le patrimoine des bibliothèques. In Bulletin des
	bibliothèques de France (BBF), 1982, n 12, 657-688. Available online: http://bbf.enssib.fr/consulter/
	bbf-1982-12-0657-001
	Unesco, Principes directeurs pour la sauvegarde du patrimoine documentaire, rédigés par Ray
	Edmondson, édition révisée 2002. Paris : UNESCO, 2002. 79 p.
	BIBLIOGRAPHY

NOTES 1. Example of a Perseid: athar.persee.fr 2. ENS de Lyon, CNRS and Université de Lyon 3. The Cairo Gazetteer (cairogazetteer.fr/invisu/) or GBIF (www.gbif.org)

Furthermore, Persée has established partnerships based on interoperability: Open Edition (link between the past issues available on the Persée portal and the current ones on Open Edition Journals), Erudit (mutual access), HumaNum (Isidore).


Stéphane Chatty
email: chatty@enac.fr

A unified framework for control structures in interactive software

Keywords: ACM Classification Keywords: H5.2 Information Interfaces and presentation: User Interfaces, D3.3 Programming Languages: Language Constructs and Features. General terms: design, human factors, languages interactive software, programming language, control structure, data flow, state machine, process

Control structures such as event passing, state machines and data flows help programmers express the behavior of interactive software. But used alone they cannot describe systems in their totality, and when combined with standard control structures their semantics becomes unclear. This article proposes a set of requirements for unifiying all control structures in a general framework. It then proposes a candidate framework in which all software components can be described by processes and their interactions by process couplings. Couplings are the basic block from which control structure such as state machines, data flow connectors, sequences and functions can be derived. We show how a wide variety of programming situations and architecture patterns can be described by combining these control structures. The power of expression and interoperability provided unlock possibilities such as interaction-oriented programming languages.

INTRODUCTION

Interactive software is long known as costly to produce [START_REF] Myers | Survey on user interface programming[END_REF]. This is harmful to high complexity sectors such as aeronautics, where the need for multiplying user interface prototypes to support validation processes comes up against the cost of creating prototypes. This also impacts end users, because programming their digital environment often involves interaction-related concepts [START_REF] Coutaz | Early lessons from the development of spok, an end-user development environment for smart homes[END_REF].

Various fields, from computation to distributed systems and artificial intelligence, have produced general purpose programming languages. Imperative, functional, object-oriented, reactive or logic-based, these languages have evolved until communities of programmers have considered them well founded and adequate for their goals. Interactive software, with its focus on states and events, seems singular enough to justify the emergence of interaction-oriented programming 2015 VERSION FILED IN 2018 AS hal-01800741 languages. However, most interactive software still relies on a mix of mainstream languages and user interface toolkits that provide additional concepts, with little theoretical foundation. This article is a contribution toward the emergence of generalpurpose interaction-oriented programming languages, in the hope that well defined semantics and wide expressivity will facilitate interactive software development. We focus here on execution control, and on the goal of unifying control structures in a single framework. We first contrast the status of standard and interaction-oriented control structures, and compare their evolutions. We formulate requirements for a control framework, that is a set of control structures that covers the needs of interactive software. We show how, using a process model, known control structures ones can be derived from a single primitive. Relying on an implementation of this control framework and its use in full-size applications, we follow Dix's recommendations for works on theories in HCI [START_REF] Dix | Research Methods for Human-Computer Interaction[END_REF] and demonstrate through examples how the framework meets the requirements. We conclude on the practical consequences for tools aimed at designers and programmers, including dedicated programming languages.

LIMITS OF HYBRID MODELS

User interface toolkits come with control structures, which are gaining importance as post-WIMP interaction requires designers and programmers to create interactors themselves. Formulating the internal behavior of a button is easier with a state machine than with function calls [START_REF] Appert | Swingstates: Adding state machines to Java and the Swing toolkit[END_REF], formulating how a window can be moved and zoomed at the same time is easier with data flows, and so on.

The role of control structures such as events, state machines and data flow has been well established by practice, but it has not replaced the use of traditional control structures. Programmers use mainstream languages such as Java or C++ not only to write the non-interactive part of their software, but also as a host infrastructure to combine control structures.

These hybrid solutions that combine models of execution have practical merits. Still, there would be benefits in having more integrated solutions that clarify the links between models and dispense from using host languages. One of the limits of hybrid models is that they are not self-sufficient and do not provide answers to questions such as:

• data flows and state machines both involve notification; what is the underlying mechanism that explains this? For example, why can pointer movements be used as sources to both data flows (to drive a cursor) and state machines (to implement drag and drop)?

• an on/off switch can be described with a state machine that emits events, but it also has a value (on or off) that could feed a data flow. Why and how can this be used?

• an animation trajectory has similarities with both a computation function and an iterator. What exactly is common, and can it be factorized?

In other contexts programmers are used to well founded models that give clear answers to such questions, and do so because they rely on a few independent primitives from which all other concepts are derived. A Smalltalk programmer who wonders about the similarities between expressions [3 + 5] and [myrect draw] can use the object and message concepts to understand the roles of 3 and +. A Lisp programmer can understand the similarities between (mapcar) and (reduce) by returning to functions and argument lists.

The benefits of such models go beyond mere comprehension, because they show how the constructs are interoperable, either to connect them or to replace one with another with minimal refactoring. For instance, understanding the links between (mapcar) and (reduce) allows to reuse functions and lists when modifying an algorithm. At the opposite:

• converting a pointer from event style to data flow style requires code written in the host language (eg. see [START_REF] Appert | Flowstates: prototypage d'applications interactives avec des flots de données et des machines à états[END_REF]);

• same for turning an on/off switch into a data flow brick;

• the similarity between animation, iteration and computation cannot be exploited easily in a sequential language.

By showing how standard constructs are made, these models also suggest other combinations and stimulate creativity. For instance, Python generators exploit the common roots of iterators and functions in the object-oriented model. Finally, being self-sufficient these models support the use of pivot formats for code analysis, MDE techniques, formal techniques, and graphical programming tools, all of which are partly defeated by the use of host languages in hybrid solutions.

COMPUTATION, INTERACTION: REPEATING HISTORY

Unified models are desirable, but available only when no interaction is involved. Comparing computation and interaction can provide lessons as to how unification can be attained.

Tracing the border between interaction and computation

The split between functional core (FC) and user interface (UI) proposed in the literature does not capture these situations: programmers more and more use hybrid solutions for both FC and UI. In addition, some FCs are interactive software, for instance a plant supervision system. And some interactive programs have no FC or UI worth mentioning, for instance one that says "stop the heating and email me when the temperature is above 20 • C".

Consequently, we define interaction-oriented and computation-oriented software using the following distinction: control is internal in computation, external or mixed in interaction [START_REF] Johnson | Designing Reusable Classes[END_REF]. Given this distinction, we can study the evolution of control structures in computation so as to establish requirements and research directions for interaction.

Control structures: from expressiveness to simplicity

Imperative and functional programming have been the dominant paradigms for a few decades. An imperative program is a series of instructions whose order describes their execution sequence. Over time, new control structures have been introduced so as to make algorithms easier to write and to provide simple support for more complex situations: loops, conditions, functions, coroutines, generators, aspects, etc. These extensions were often made at the expense of generality [START_REF] Fisher | A survey of control structures in programming languages[END_REF] and simplicity: it was expressiveness first.

In contrast, functional programming was advocated for its conceptual simplicity [START_REF] Backus | Can programming be liberated from the von Neumann style? a functional style and its algebra of programs[END_REF]. A program is a function that calls other functions, and control structures are provided as functions. Functions are the root primitive of the control framework, which gives strong internal consistency. Later, the introduction of object-oriented programming and prototypeoriented programming brought a similar measure of conceptual unification to imperative programming, all instructions being considered as message exchanged with objects [START_REF] Ungar | Self: The power of simplicity[END_REF].

This history of control structures can be analyzed as the progressive capture of the requirements of a population of users. First starts a process of identifying concerns and embedding them in a design. Then because conceptual simplicity is an important design feature [4, pp. 42-44], starts a second process of unification toward simplicity. This could have ended there, but then programs became interactive and the two design processes started again.

Interaction: new concerns, new control structures

At first, interaction was through terminals and this only required marginal changes, because the query-response style is compatible with standard control structures. Real changes came with graphical user interfaces. Drawing can still be described as sequences of instructions, but the execution of programs became more controlled by external input than by their own sequence of instructions. The concept of external control appeared [START_REF] Hartson | Human-computer interface development: Concepts and systems for its management[END_REF] and events became a new control structure, implemented with extensions such as callback functions or signal/slot patterns.

Then graphics became more and more encapsulated and algorithms disappeared from the concerns of programmers. The behavior and the reuse of interactive components became more central. Programmers started to face the spaghetti of callbacks [START_REF] Myers | Separating application code from toolkits: Eliminating the spaghetti of callbacks[END_REF], and new control structures were needed.

Because these new concerns were specific to user interfaces, they were not treated in programming languages but in graphics libraries. State management was one of the earliest, first to describe the global dialogue between the user and the program [START_REF] Jacob | Using formal specifications in the design of a human-computer interface[END_REF], then to describe the behaviors of individual components [START_REF] Myers | A new model for handling input[END_REF]. Attempts were also made at managing state in combination with another growing concern: the need to organize the complexity of programs, using hierarchical systems [START_REF] Harel | Statecharts: A visual formalism for complex systems[END_REF]. Other concerns appeared when the interaction styles became more continuous: animation, drag and drop, data visualization. Various forms of data flow control were proposed to support the description of data representation and graphics layout [START_REF] Myers | comprehensive support for graphical, highly interactive user interfaces[END_REF], animation [START_REF] Chatty | Extending a graphical toolkit for two-handed interaction[END_REF], and input [START_REF] Chatty | Extending a graphical toolkit for two-handed interaction[END_REF][START_REF] Dragicevic | Support for input adaptability in the icon toolkit[END_REF].

Interaction: seeking simplicity again

What interaction programmers have gained during this process for their specific needs, they have lost in simplicity. Various attempts have been made at getting consistency back.

Taking advantage of similarities between data flow and the flow of values in function calls, functional reactive programming combines some features of reactive programming with the syntax of functional languages [START_REF] Elliott | Functional reactive animation[END_REF]. Similarly, some have used the extensibility of the syntaxes of object-oriented languages to integrate the new control structures (mainly state machines) as much as possible [START_REF] Lecolinet | A molecular architecture for creating advanced GUIs[END_REF][START_REF] Appert | Swingstates: Adding state machines to Java and the Swing toolkit[END_REF], obtaining some form of syntactical consistency. The C# programming language also provides the same consistency for events.

Conversely, it has been proposed to structure programs using Petri nets and to use an object-oriented language for making computations when the transitions are fired [START_REF] Navarre | A model-based user interface description technique dedicated to interactive systems addressing usability, reliability and scalability[END_REF]. Similarly, several authors have proposed to combine data flows and state machines by letting the state machines control which data flows are active at a given time [START_REF] Chatty | Extending a graphical toolkit for two-handed interaction[END_REF][START_REF] Jacob | A software model and specification language for non-WIMP user interfaces[END_REF][START_REF] Colac ¸o | A conservative extension of synchronous data-flow with state machines[END_REF].

All these are partial solutions, that lead to the situation described earlier in this article. A more complete integration was described in [START_REF] Chatty | Revisiting visual interface programming: Creating GUI tools for designers and programmers[END_REF], where events and state machines are unified and data can be used as event sources and as data flow feeds, but the unification of states and values was incomplete and imperative programming was still required for some parts of programs. Full unification is still an open challenge, addressed in the rest of this paper.

REQUIREMENTS FOR CONTROL FRAMEWORKS

The above analysis allows to define a set of requirements for the design of a set of control structures, aimed at future languages for interactive software or at future tools for designers. All these requirements are met by functional languages and object-oriented languages for computation-oriented software, but not for interaction-oriented software.

Conceptual unification

The ability to place all control structures with regard to others or, even better, to understand how they all derive from a single primitive, is a major goal. It brings semantical interoperability and flexibility. It also brings conceptual integrity and simplicity, which are highly valued not only in computer science, but also in most science and design disciplines (eg. unification in physics). A number of other requirements depend on this one.

Additionally, the more the concepts are consistent with those used by programmers or designers in their daily life, the better. This was sought in the design of object-oriented languages, with explict references to philosophical concepts. For interactive software, this goal is challenging because it encompasses notions such as physical objects and human activities or procedures.

Coverage

The set of control structures must cover all the concerns usually met by programmers and designers, whatever the interaction style they choose. Sequences, functions, loops, and tests are needed for command line dialogs and for computation. State machines are used for widgets, direct manipulation and dialog design. Data flows are useful for visualization, animation and direct manipulation. Parallelism and synchronization primitives are required by multimodal interaction. Aspectlike control structures are useful for adaptive user interfaces [START_REF] Mathieu Magnaudet | What should adaptivity mean to interactive software programmers?[END_REF]. In addition, new domains such as the Internet of things will probably bring their own requirements.

Extensibility

Since new interaction styles bring new concerns, and possibly new control structures, the framework must be extensible. Given the diversity of possible interactions styles, programmers should be able to create control structures themselves with no need to use another language. This stresses the importance of organizing the set of control structures as a framework in which primitives can be combined at will.

Compatibility with development processes

The development processes of interactive software require cooperation between different disciplines; for instance a designer may need to modify a behavior written by a programmer. They involve concurrent engineering: designers can produce graphics and behaviors while programmers are writing algorithms, on the basis of a predefined application architecture. They also are iterative, with successive refinements and extensions of the same design. This variety of actors and tools (programming languages, graphical editors, transformation tools) pleads in favor of a further unification, available in languages such as LISP: common concepts for code and data, which favor the exchange of code between tools.

Support for formal analysis

A number of stakeholders are in demand of better support for analyzing interactive software and its behavior: safety experts who need to validate the software against a specification, programmers who want to check their code against various behavior requirements, human factors professionals who want to predict the performance of end-users with the software, etc. The closer the control structures are to a form that can be processed automatically, the better.

SELECTING AN EXECUTION MODEL

The rest of this article describes a control framework that meets the above requirement. We start by analyzing two design decisions on which the proposed solution relies: the use of the reactive programming paradigm, and an execution model that supports multiple scale analysis.

Formally describing the chosen execution model is beyond the goal of this article. Instead we highlight the reasons for our design decisions and outline the basic concepts of the execution model, in order to root the control framework in these concepts and to help the reader assess how the requirement of support for formal analysis can be met.

The role of the execution model

When using two sets of control structures, one for computation and one for interaction, it is sometimes difficult to understand how programs are executed. For instance, in the code below the two animation sequences and the message printing do not occur in the order that the inattentive reader would think: the done message is printed first. void sequence () { a1 = Animate (rect, 100, 100); a2 = AnimateAfter (a1, rect, 50, 50) printf ("done"); }

The reason is that the two Animate calls do not execute the whole animation sequences: they merely start them and return. There is no standard way in any sequential language to express ordering constraints between animation sequences.

Most control structures have a clear meaning in a given execution model only: loops and functions are derived from sequential programming, Prolog's cuts are meaningful only within its backtracking system, etc. The control structures used for interaction, such as state machines, events and data flows, are generally associated with reactive models, e.g. in Lustre [START_REF] Colac ¸o | A conservative extension of synchronous data-flow with state machines[END_REF]. This is consistent with the concurrency exhibited by user interface software: graphical components have concurrent behaviors with very few ordering constraints, animations need to execute in parallel, input and output devices have an intrinsically concurrent behavior, and so on.

Relying on the reactive paradigm for interactive software seems a natural choice to avoid the confusions described above. Not only does it provide the appropriate basis for interactive control structures, but since models of concurrency are supersets of sequential execution models [START_REF] Milner | Functions as processes[END_REF] it also provides appropriate semantics for classical control structures.

Choosing an execution model also has consequences on the development processes requirement. When working on a component, programmers and designers frequently need to shift from one level of granularity to another. For instance, designers sometimes improve graphical buttons by replacing their atomic state changes with more complex animation sequences. Similarly, an atomic value assignment can be replaced with a dialog that asks confirmation of the change. Therefore, it is desirable that the execution model allows to change the level of analysis without difficulty, like functional programming makes its easy to replace a literal expression with a function call.

A hierarchical process model

The model chosen here relies on a hierarchy of interacting processes, derived from common process algebras in which a process is an abstraction defined by the signals it exchanges with other processes [START_REF] Lee | Comparing models of computation[END_REF].

Everything is a process

All that happens on the computer can be modeled by a process. This includes the behavior of interactive components such as buttons and menus. This includes components themselves, made of all their internal processes. This includes animation as well. But this also includes many other things: entities as diverse as graphical objects, physical input devices, and memory cells can all be modeled as processes if need be. This helps meeting the conceptual unification requirement in its more ambitious version, because it covers both the software and its environment.

Hierarchy and couplings

Each process can be considered as made of other processes. This allows to describe all systems of interest at the chosen level of granularity, whether for hardware or software. For instance, graphical objects can be considered as atomic processes for some purposes. Alternatively, they can be modeled as a combination of memory cells and rendering routines. Some processes, such as the contact between two electrical conductors or the interconnection between two software components, belong to two or more parent processes. We call them couplings. Some couplings are predefined, such as the coupling between memory cells and rendering routines in a graphical object or the physical connections in an input device. Others are created by programmers. Dor instance a programming instruction that modifies a variable creates a coupling between a program and the computer memory.

Activation and interaction

The evolution of a system is described by the activation of its sub-processes. Activating a lamp makes it emit light, activating an assignment instruction modifies memory, activating a dialog box starts an interaction sequence.

When two processes are coupled, activating one can trigger the activation of the other through that of the coupling. This is called an interaction. Because processes are hierarchical, interactions are hierarchical too: a gesture on a touch screen is an interaction between the finger and the sensors of the touch screen, made of a series of shorter interactions. The smallest interactions between software components are named events.

In a computer, the hardware environment and the operating system already implement couplings. For instance, physical couplings in a mouse are designed so that movements of the hands trigger electronic sensors, and these sensors are coupled to software components that represent the mouse in the operating system. Couplings created by application programmers enrich the wealth of couplings that already constitute the user's environment. They define how programs become part of this interactive environment, and how the components inside the programs interact together.

AN INTERACTION-ORIENTED CONTROL FRAMEWORK

The proposed control framework relies on the above hierarchical process model. It is based on a single primitive that can be derived into all the required control structures by combining it with the basic operations on memory. We describe below how control structures from the literature are defined and demonstrate their use, thus showing how the coverage requirement is met. We also give an example of how new control structures can be created when required, so as to address the extensibility requirement.

All the examples in the rest of this article have been implemented using a component-based programming environment named djnn, available at http://djnn.net. djnn has three goals: supporting innovative interactive software, supporting modern development processes, and paving the way to interaction-oriented programming languages. djnn is available as a toolkit with APIs in C, C++, Java, Python and Perl. Alternatively, it can be used as an XML interpreter so as to implement components in a portable format. The contents of these XML files are hierarchies of components, and can be understood as abstract syntax trees resulting from the compilation of more usable notations.

In order to save space, the examples are formulated in compact pseudocode rather than in XML format or with any djnn API. For instance, we write: component c { rectangle r (0, 0, 10, 10); } instead of the following XML code: <djnn:component id="c"> <svg:rect id="r" x="0" y="0" width="10" height="10"/> </djnn:component>

Control structures as components

A component-oriented environment can be defined from the execution model defined above by considering that each component is the implementation of a given process. Programming then consists in creating components and couplings between them. Coupling components makes new interactions possible between them, thus defining the behavior of a program. For instance, by coupling the position of the mouse to a graphical object, one creates a cursor that is updated every time the mouse moves. Note that this coupling has the effect of creating an indirect coupling between the user and the graphical object, thus allowing the user to interact with the cursor. Similarly, one can create an animation sequence by coupling the completion of an animated effect to the start of another. By coupling operations to the start of an application, one can also create a traditional program that runs computations as soon as it starts.

All control structures are aimed at creating couplings, each control structure being dedicated to a pattern of coupling. In order to meet the development processes requirement as much as possible, control structures are defined as components themselves. This allows to manage them like any other components, thus contributing to requirement unification and allowing programmers to create programs by creating and assembling components. We will also see later that it contributes to unification and extensibility by allowing to create couplings between control structures.

Control primitive: the binding

The most elementary programming instruction consists of creating a single coupling: "when component A is activated, I want component B to be activated too". Component A is the trigger of the coupling and component B is its action. Trigger and action are just roles that any component can play. For instance, given an integer variable, one can decide to modify this variable as the action of a coupling, just as one can use modifications of the variable as the trigger of a coupling, making it an active value.

The component that manages the creation of a simple coupling is named binding1 . The following pseudocode gives various examples of bindings. It illustrates the variety of entities that can be considered as components: graphical objects, input devices, programmer-defined components, functions, and even components from other programs, resources from the operating system and from other computers. It also stresses the importance of having a complete and consistent system for addressing components. The naming system in djnn is not described in this article, but a hierarchical system similar to URIs can be used in most cases and actions can access their execution context, such as their trigger's properties, through the same naming system. Bindings are not only a very simple control structure. We will use them below to derive all other control structures, ensuring that no reference to the sequential execution model is ever required to explain the reactive behavior of programs. This makes them the root primitive of the control framework.

Since bindings are components, programmers can choose to activate them only at given times, thus creating conditional behaviors. For instance, in the pseudocode below that alternatively emits the sounds tick and tock, the activation status of bindings b1 and b2 is used to create a two-state system. The two states are implicit in this code. Initially b1 is active (line 7), and b2 is stopped (line 3). When the clock goes off, b1 is triggered; this activates tick (line 1) and b2 (line 5), and stops b1 (line 4), thus entering a second state. When the clock goes off again, lines 2, 6 and 1 ensure that tock is activated and the system returns to the initial state. Note how the hierarchical system is used when referring to the b1/run, b1/stop and b1/trigger subcomponents; here, the trigger subcomponent of b1 refers to the process of detecting that the trigger of b1 is activated.

State machines

State machine components are a more compact way of obtaining the same result as above. They are useful to describe the behavior of components with a reasonable number of states, such as buttons, menus, many existing post-WIMP components, and probably many that remain to be invented. For instance, the Pinch-Rotate-Zoom behavior on tablets is easily expressed with a state machine.

State machines can be built by combining bindings with components that are able to maintain a state. Being reducible to the same concept of coupling, they can be interchanged and combined at will with bindings. They just make it easier to describe collections of conditional couplings.

Finite state machine components (FSM) are composite components that contain other components named states and transitions. Transitions are special cases from bindings: they are defined with a trigger, and create the same type of coupling as a binding. What makes them special is that 1) each transition is defined relative to a state, named its origin, and is active only when its origin is active, and 2) the action of a transition is always a second state, named its destination. As a consequence, the triggers of the transitions constitute the inputs of the state machine: the machine changes state depending on the sequence of activation of triggers, ignores events that do not match the current state.

As an example, the code below describes the internal behavior of a software button designed for use with a mouse: component mybutton { rectangle r (0, 0, 100, 50); fsm f { state idle, pressed, out; transition press (idle, r/press, pressed); transition click (pressed, r/release, idle); transition leave (pressed, r/leave, out); transition enter (out, r/enter, pressed); } } Because states and transitions are components, they can be used as triggers in bindings and transitions from other FSMs. For instance, when properly renamed to be accessible as mybutton/click, the above click transition can be used to bind actions to the triggering of the button: binding (mybutton/hit, application/quit); This is the behavior of a Mealy machine. Alternatively, by binding actions to states rather than transitions, one can produce a state machine whose outputs depend only on the states that have been reached and not on the transitions (Moore machine). By combining the two systems, one can for instance produce the visual feedback for the behavior of a widget as well as the appropriate events to trigger other components. We will later see a switch component designed to make this easier.

Combining FSMs by coupling their transitions, or by controlling the activation of one by a state or a transition of another, makes it possible to create complex behaviors without having to introduce more complex structures such as hierarchical state machines. It also makes it easier to structure applications as collections of reusable components.

Properties: data primitives and control structures

The concept of memory is toned down in functional languages in favor of arguments and return values, to avoid socalled side effects. But in interactive software, it is important to explictly represent properties such as the label of a button. In addition, properties also play a role in control flows because their changes are events of interest.

We propose two equivalent definitions of properties. They can be defined as state machines with a large number of predefined states (2 64 states for an integer), and with no support for accessing individual transitions. The value of a property is its state. Properties can also be defined as primitive components that represent the physical memory of a computer, state transitions being implemented by the hardware like the rendering of a graphical object. This duality ensures both a proper foundation for a data model and consistency with the control framework, as illustrated below with data flow.

Data flow

In contrast to state machines, data flow is a programming style for when the flow of propagation of states is more important for programmers than the individual state changes. This often occurs when there are many states or very frequent changes, usually because the various states are just perceived as the result of sampling a value that changes continuously.

Since "value" and "state" are two aspects of the same thing, data flow can be interpreted as a special case of coupling state machines together. With state machines, the default principle is that every transition has a different action. With data flow, all transitions trigger the same action: propagating the new state, that is the new value, to other components. When the user's hand moves on a touch screen for instance, programmers are more interested in deciding what components will receive the flow of values and how they will route and filter it than by handling each event individually. We define two control structures to support such continuous behaviors.

Connecting components

Connector components allow the value of a component to propagate to another component whenever it changes. For instance, the two connectors below ensure that rectangle rect1 will move with the mouse.

connector (mouse/position/x, rect1/position/x); connector (mouse/position/y, rect1/position/y);

A connector is equivalent to a binding with a predefined action that copies the value from its source to its destination. This means that the first line in the above pseudocode is equivalent to the combination of two components below, in which we artificially introduce an "assignment" component to represent traditional assignment instructions.

# an assignment that sets rect1/position/x assignment c (rect1/position/x, mouse/position/x); # the assignment is bound to changes in mouse/position/x binding (mouse/position/x, c);

There are strong similarities between data flow and functional programming. Functional reactive programming can be interpreted as a syntax that disguises connectors as function calls, and functional programming per se can be seen as a chain of connectors that is only triggered once when the program is launched. To illustrate this, consider the following data flow chain to the functional expression that follows it. Both represent a simplified version of the chain of computations that transforms the actual data emitted by a physical mouse into what application programmers are used to: the relative movements are "accelerated", then compounded, then cropped to stay within the display area. connector (physmouse/position/x, mult/input2); connector (mult/result, add/input2); connector (add/result, max/input); connector (max/result, softmouse/position/x);

Synchronizing flows

The above example is a chain of connected components, used as data filters. Predefined filters can be used, but programmers often need to create their own, like for instance the multiplier component from above. This can be done by putting three numerical components named input1, input2 and output as well as a multiplication operation into a larger component, and adding two bindings on the two inputs. Unfortunately, this would have an undesired side-effect: when the two inputs are modified as the result of a single event, the output would be modified twice for that single event and this would lead to inconsistent behaviors. For instance, say that a beep is emitted every time the output changes, and that the inputs are computed from a key press; then there would be two beeps for each key press, where the user expects one.

For this, we introduce a second data flow-oriented structure: the watcher. A watcher is a binding with several triggers. It uses synchronization techniques similar to those of reactive languages [START_REF] Colac ¸o | A conservative extension of synchronous data-flow with state machines[END_REF] to ensure that its action is activated only once per asynchronous event, that is once for each event that has external causes. For instance, given a passive component named multiplication, the internals of the multiplier component would be as follows.

component multiplier { integer input1; integer input2; integer output; multiplication m (input1, input2, output); watcher (input1, input2, m); }

Composite flows

Finally, while we have only used data flow in conjunction with numerical components so far, this applies to other components as well. As already mentioned, the value of a numerical component is its current state. This definition extends to all components that have a state, including those that contain components that have a state. Therefore, connectors can be used between any pair of compatible components to synchronize their state. For instance, the mouse-rectangle connection from earlier can be written: connector (mouse/position, rect1/position);

Combining and extending

The components described so far, all built around the same basic blocks, provide unification of the most common control structures used for user interface programming: events, state machines and data flows. Combined together, they can also be used to create new control structures that extend the control framework.

To begin with, components named switches can be created to control what parts of a component are active at a given time. For instance we can enrich component mybutton from page 6 with one color for each state: A switch is an open collection of components, named its branches; the above switch has three branches. In addition, switches have a property named state and a watcher that activates the branch named in this property. When the state property is connected to the state of a compatible FSM, this ensures that the FSM controls which sub-component of the switch is active. Here, this makes the button changes color when it changes state.

Switches can be used to convert data flows to states when needed. For instance, in the pseudocode below the color of rectangle changes with the values of a number: This also allows for the creation of simple conditions. For instance, the following pseudocode emits a beep when the x coordinate of a pointer has a given value, which can be useful for debugging purposes. Other classical control structures can be obtained by combining the basic structures described above. For instance:

• sequences can be defined with bindings to the end of components that terminate on their own;

• a graphical scene graph can be considered as a control structure: it tells what graphical objects must be rendered and in which order. This can be defined by managing two sets of bindings: parent-child bindings that ensure that child objects are active only when their parents are active, and bindings that create a sequence between the activation of children so as to control their rendering order;

• a function call is a particular kind of interaction similar to a dialogue fragment: the caller activates the function with some context, the function computes a result, passes it to the caller, terminates, then the caller resumes its own activity. To reproduce this, we define functions as components that terminate their activation on their own. In an imperative setting, calling a function then consists of binding the activation of a function to the termination of the previous instruction in the sequence, and binding the next instruction to the termination of the function. In a functional setting, each function consists of series of function calls: first those needed to evaluate a series of arguments, then the main call performed with these arguments. This structure can be modeled as a simple sequence or a four-state FSM: start, activation of the functions used to compute the arguments, activation of the main function, then termination and return to start.

APPLICATION TO ARCHITECTURE SCENARIOS

Deriving control structures could be used to validate the proposed framework by establishing its Turing-completeness. However, the value of a theoretical result can also be established by selecting examples that demonstrate its applicability [START_REF] Dix | Research Methods for Human-Computer Interaction[END_REF]. For this reason, we now describe a few scenarios commonly encountered in interactive software programming, so as to illustrate how the control framework works in practical situations and to demonstrate its relevance.

Common architecture patterns

Creating a graphical application consists mostly of assembling components, connecting them, and organizing them to make their structure and their reuse more manageable. djnn supports this by encouraging programmers to create a hierarchy of components, each made of previously existing components. We describe below how a few common situations can be managed with the control framework described above.

Building and initializing components

We have already described how to build a component by assembling other components: mybutton is made of four components, a rectangle, a FSM, a switch and a connector. This button is simplistic, but improving it would just require elaborating on the number of states and the number of graphical components. To further illustrate how components can be combined recursively, the pseudocode below describes a dialog box made of two instances of mybutton.

component mydialogue { rectangle frame (0, 0, 300, 100); mybutton o ('ok', 30, 25); mybutton c ('cancel ', 170, 25); } This dialog box is made of a rectangle and two instances of mybutton. For this to work, two changes have to be made to mybutton: adding a text, and allowing the text and the rectangle of the button to be initialized with parameters.

The latter point underlines a situation in which programmers currently fall back to imperative or functional programming: initialization. Because in the case of initialization the flow of control is internal like in traditional computation scenarios, function calls are indeed appropriate and very few authors have felt the need to propose alternative solutions. Here, the initialization flow is derived from the relationship between a component and its sub-components: the activation hierarchy is managed by implicit bindings between the parent and each of is children. In this regard, the empty components that programmers can fill to build their own components can be considered as a specialized control structure.

In the new version of mybutton below, we represent the sharing of information between parent and children during initialization. We use a syntax similar to arguments in function calls. Note that this is just a syntactic convention: mybutton and rectangle are not functions, if only because they do not terminate spontaneously.

component mybutton (t, x, y) { text (t, x, y); rectangle r (x, y, 100, 50); ...

Reusing a component, event style

Programmer-defined components can be used as event sources, like basic components. For instance, the following additions to mydialogue show how one ensures that the dialog box disappears when either of its buttons is pressed.

Adapting components

Our dialog box can also be used as an event source, but programmers who reuse it expect ok and cancel events, not o/hit and c/hit. Such interface adapatations are one of the reasons why patterns such as the Functional Core Adapter and Presentation-Abstraction-Control had to be introduced [START_REF] Gram | Design Principles for Interactive Software[END_REF].

The following additions to the dialog box illustrate how the external interface of a component can be adapted using empty components and bindings. More complex adaptations can also be performed, relying for instance on their own state machine to translate events.

Communicating state machines

Describing the behavior of applications with Petri nets or extended state machines that communicate among themselves has often been proposed. This is what happens here when two components with state machines are bound, for instance when a button uses the press and release events that come from the state machine of an input device. We show below how this can occur inside components so as to express complex behaviors; for instance, the following pseudocode simulates a three-state lamp switch controlled by a push button.

Reusing a component, data flow style

Its is sometimes more practical to reason about the state of a component rather than its events, and some authors have suggested using a functional programming style to describe this: one reads the "value" of a toggle button by "calling" it, for instance. This can be reproduced using data flow. For instance, consider a toggle button that we want to use as a light switch: instead of reasoning about on and off events, one would rather reason about the state of the system, as below. Note how we export the state of the toggle and the light, like we did for the dialogue box.

Managing modalities and access to resources

After focusing on classical scenarios of graphical user interfaces, we describe here a few scenarios related to new interaction modalities or other computer resources.

Using alternative input

Tablets have an accelerometer to measure their orientation. The following pseudocode shows how one can use it in data flows. Here, we use it to control which part of a graphic scene loaded from a SVG file is visible through a clipping area. This illustrates how much the control model is independent from the event sources, whether they are classical input devices, new input devices, or any other compatible component.

Animation as components

Since all software entities, including data and control structures, are components, animation can also be expressed as components. For instance, in the pseudocode below we modify the application above so that the accelerometer does not control the horizontal position of the clipping zone but the way it drifts over time in an approximation of gravity. Note how the combination of connectors and bindings merges two asynchronous input sources (clock and sensor), and ensures multimodal fusion.

Interacting with the context

Future interactive software will not be limited to graphical interfaces. It will react to all sorts of sensors in the user's environment, whether physical or logical. Already, sensors are multiplying and applications are reacting to more and more context changes. To illustrate how this can be addressed with the control structures that we have described, the following code reacts to file creations in a directory. Data flow can also be used to similar purposes. For instance, assuming that directories have a copy child that copies files when it receives references to them, the following code copies files from a directory to another as soon as they are created. directory d1 (file://data); directory d2 (file://backup); connector (d1/new, d2/copy); Not only does this show how control structures originally applied to graphical user interfaces can apply to other types of interactive software. It also illustrates how more and more applications are becoming interactive in the general sense, that is they react to their environment.

CONCLUSION AND PERSPECTIVES

In this article, we have elicited requirements for a framework for control structures in interactive software, described a candidate solution, and provided elements to assess how this solution meets the requirements. The proposed framework constitutes a complete solution to the problem of unifying behavior descriptions in interactive software, and also encompasses control structures used in computation-oriented software. This unification allows programmers to combine control structures at will, and it provides them with an unambiguous model of how their programs are executed.

The djnn programming framework implements the proposed control framework. djnn is available in various languages for instantiating components from the djnn core, its graphical module and basic input support. djnn is already used in various applications, ranging from an experimental ground station for drones [START_REF] Mathieu Magnaudet | What should adaptivity mean to interactive software programmers?[END_REF] to the control of an interactive showroom and a multimodal aircraft cockpit prototype. Ongoing work includes the formal definition of the execution model, the modeling and implementation of various interaction modalities and bridges to computer resources.

Because it permits to describe programs and their control by solely instantiating components, the proposed framework can serve as the basis for graphical editors and visual languages in addition to textual programming languages. Future research includes the design of a collection of visual and textual programming languages that would each specialized in a different facet of interactive software (graphics, architecture, behaviors, etc) and that could be used by design teams to produce applications together.

  # beeping repeatedly binding (myclock, beep); # beeping when an numerical value changes binding (mygame/score, beep); # beeping when another application quits binding (system://application1/quit, beep); # launching a program when a file is modified binding (file://eics.tex, system://XLaTeX/reload);# controlling an animation with a mouse button binding (mouse/left/press, animation1/start); binding (mouse/left/release, animation1/stop); # displaying a help box when an 'h' gesture is made binding (gestures/h, myapplication/helpbox); # quitting the application upon a button press binding (quitbutton/hit, application/quit); # implementing part of the behavior of a button binding (quitbutton/rect1/enter, quitbutton/hovercolor); # chaining two animation sequences binding (animation1/end, animation2/start);

1

  binding b1 (myclock, tick); 2 binding b2 (myclock, tock); 3 binding (b1/run, b2/stop); 4 binding (b2/run, b1/stop); 5 binding (b1/trigger, b2/run); 6 binding (b2/trigger, b1/run); 7 b1/run;

  multiplier mult (3); adder add (512); maximum max (1024) # compute (max 1024 (+ 512 ( * 3 physmouse_position_x)))

  /remainder, s/state); rectangle r;

  /position/x, s/state)

  directory d (file://data); beep b; binding (d/new, b);

"binding" is closer here to the "bind" instruction in Tcl than to data bindings in XAML