Romain Giot
email: romain.giot@ensicaen.fr

Christophe Rosenberger
email: christophe.rosenberger@greyc.ensicaen.fr

Genetic Programming for Multibiometrics

Keywords: Multibiometrics, Genetic Programming, Score fusion, Authentication

Biometric systems suffer from some drawbacks: a biometric system can provide in general good performances except with some individuals as its performance depends highly on the quality of the capture... One solution to solve some of these problems is to use multibiometrics where different biometric systems are combined together (multiple captures of the same biometric modality, multiple feature extraction algorithms, multiple biometric modalities. . . ). In this paper, we are interested in score level fusion functions application (i.e., we use a multibiometric authentication scheme which accept or deny the claimant for using an application). In the state of the art, the weighted sum of scores (which is a linear classifier) and the use of an SVM (which is a non linear classifier) provided by different biometric systems provid one of the best performances. We present a new method based on the use of genetic programming giving similar or better performances (depending on the complexity of the database). We derive a score fusion function by assembling some classical primitives functions (+, * , -, ...). We have validated the proposed method on three significant biometric benchmark datasets from the state of the art.

Introduction

Objective

Every day, new evolutions are brought in the biometric field of research.

These evolutions include the proposition of new algorithms with better performances, new approaches (cancelable biometrics, soft biometrics, ...) and even new biometric modalities (like finger knuckle recognition [START_REF] Kumar | Human Identification Using KnuckleCodes[END_REF], for example).

There are many different biometric modalites, each classified among three main families (even if we can find a more precise topology in the literature) :

• biological : recognition based on the analysis of biological data linked to an individual (e.g., DNA analysis [START_REF] Hashiyada | Developement of biometric dna ink for authentication security[END_REF], the odor [START_REF] Korotkaya | Biometric person authentication: Odor[END_REF], the analysis of the blood of different physiological signals, as well as heart beat or EEG [START_REF] Riera | Unobtrusive biometric system based on electroencephalogram analysis[END_REF]);

• behavioural : based on the analysis of an individual behaviour while he is performing a specific task (e.g., keystroke dynamics [START_REF] Gaines | Authentication by keystroke timing: some preliminary results[END_REF], online handwritten signature [START_REF] Fierrez | On-line signature[END_REF], the way of using the mouse of the computer [START_REF] Weiss | Mouse movements biometric identification: A feasibility study[END_REF], voice recognition [START_REF] Petrovska-Delacretaz | Text-independent speaker verification: State of the art and challenges[END_REF], gait dynamics (way of walking) [START_REF] Nandini | Comprehensive framework to gait recognition[END_REF] or way of driving [START_REF] Benli | Driver recognition using gaussian mixture models and decision fusion techniques[END_REF]);

• morphological based on the recognition of different particular physical patterns, which are, for most people, permanent and unique (e.g., face recognition [START_REF] Turk | Face recognition using eigenfaces[END_REF], fingerprint recognition [START_REF] Maltoni | Handbook of fingerprint recognition[END_REF], hand shape recognition [START_REF] Kumar | Personal recognition using hand shape and texture[END_REF], or blood vessel [START_REF] Xu | The blood vessel recognition of ocular fundus[END_REF], ...).

Nevertheless, there will always be some users for which a biometric modality (or method applied to this modality) gives bad results, whereas, they are better in average. These low performances can be implied by different facts: the quality of the capture, the instant of acquisition and the individual itself but they have the same implication (impostors can be accepted or user need to authenticate themselves several times on the system before being accepted). Multibiometrics allow to solve this problem while obtaining better performances (i.e., better security by accepting less impostors and better user acceptance by rejecting less genuine users) and by expecting that errors of the different modalities are not correlated. In this paper, we propose a generic approach for multibiometric systems.

We can find different types of biometric multimodalites [START_REF] Ross | Handbook of multibiometrics[END_REF]. They use:

1. different sensors of the same biometric modality (i.e., capacitive or resistive sensors for fingerprint acquisition); 2. several different representations for the same capture (i.e., use of points of interest or texture for face or fingerprint recognition); 3. different biometric modalities (i.e., face and fingerprint recognition); 4. different instances of the same modality (i.e., left and right eye for iris recognition); 5. multiple captures (i.e., 25 images per second in a video used for face recognition); 6. an hybrid system composed of the association of the previous ones.

We are interested in the first four cases in this paper. Our objective is to automatically generate fusion functions which combine the scores provided by different biometric systems in order to obtain the most efficient multibiometrics authentication scheme.

Background 1.2.1. Performance Evaluation

In order to compare different multibiometrics systems, we need to present the how to evaluate them. Several works have already done on the evaluation of biometric systems [START_REF] Theofanos | Usability & Biometrics: Ensuring Successful Biometric Systems[END_REF][START_REF] Iso | Biometric performance testing and reporting[END_REF]. Evaluation is generally realized within three aspects:

• performance: it has for objective to measure various statistical criteria on the performance of the system (Capacity [START_REF] Bhatnagar | On estimating performance indices for biometric identification[END_REF], EER, Failure To Enroll (FTE), Failure To Acquire (FTA), computation time, ROC curves, etc [START_REF] Iso | Biometric performance testing and reporting[END_REF]);

• acceptability: it gives some information on the individuals' perception, opinions and acceptance regarding the system;

• security: it quantifies how well a biometric system (algorithms and devices) can resist to several types of logical and physical attacks such as Denial of Service (DoS) attack.

In this paper, we are only interested in performance evaluation (because the fusion approach is not modality dependant and perception and security depend on the used modalities). The main performance metrics are the following ones:

• FAR (False Acceptance Rate) which represents the ratio of impostors accepted by the system;

• FRR (False Rejection Rate) which represents the ratio of genuine users rejected by the system;

• EER (Error Equal Rate) which is the error rate when the system is configured in order to obtain a FAR equal to the FRR;

• ROC (Receiver Operating Characteristic) curve which plots the FRR depending on the FAR and gives an overall overview of system performance;

• AUC (Area Under the Curve) which gives the area under the ROC curve.

In our case, smaller is better. It is a way to globally compare performance of different biometric systems.

We can also present the HTER (Half Total Error Rate) which is the mean between the FAR and FRR for a given threshold (this error rate is interesting when we cannot get the EER).

Biometric Fusion

There are several studies on multibiometrics. The fusion can be operated on different points of the mechanism:

• template fusion: the templates captured by different biometric systems are merged together, then the learning process is realized on these new templates [START_REF] Raghavendra | Pso versus adaboost for feature selection in multimodal biometrics[END_REF][START_REF] Rattani | Robust multi-modal and multi-unit feature level fusion of face and iris biometrics[END_REF]. Figure 1 process is related to a feature selection in order to determine the most significant patterns to minimize errors.

• decision fusion: the decision is taken for each of the biometric authentication system, then the final decision is done by fusing the previous ones [START_REF] Ross | Multimodal biometrics: An overview[END_REF].

• rank fusion: the decision is done with the help of different ranks of biometric identification systems. The main method is the majority vote [START_REF] Zuev | The voting as a way to increase the decision reliability[END_REF].

• score fusion: the fusion is realized considering the output of the classifiers.

The Figure 1(b) presents this type of fusion.

Buyssens et al. [START_REF] Buyssens | Fusion of ir and visible light modalities for face recognition[END_REF] showed the interest of biometric fusion for face recognition combining the image in visible and infrared color spaces with convolutional neural networks. In [START_REF] Filho | Multimodal biometric fusion-joint typist (keystroke) and speaker verification[END_REF], Mantalvao and Freire have combined keystroke dynamics with voice recognition, it seems it is the first time that multibiometrics has been done with keystroke dynamics and another biometric modality. In [START_REF] Hocquet | Authentification biométrique adaptative application à la dynamique de frappe et à la signature manuscrite[END_REF], This method has been successfully applied on a multibiometric system using face and fingerprint recognition in a mobile environment (where acquisition and computation times are important) [START_REF] Allano | La biométrie multimodale : stratégies de fusion de scores et mesures de dépendance appliquées aux bases de personnes virtuelles[END_REF].

Hocquet
Another kind of architecture has been proposed: it is a hierarchical fusion scheme [START_REF] Teh | A multiple layer fusion approach on keystroke dynamics[END_REF] (called multiple layers by their authors). Shen et al. have presented this method with two different keystroke dynamics methods. The fusion is done at different steps, and involves different mathematical operations on scores (sum, weighted sum, product, min, max) and logical operations decision (comparison to a threshold, or, and) on differents templates extracted from the same capture. An extended version to any multibiometric system is presented in Figure 1(d). We think our work can be seen as a generalization of this paper.

It is also possible to model the distribution of the genuine and impostor matching scores, we talk about Density-based score fusion. In [START_REF] Nandakumar | Likelihood ratio-based biometric score fusion[END_REF], scores are modelled with a Gaussian Mixture Model and have been tested on three multibiometric databases involving face, fingerprint, iris and speech modalities.

Concerning non linear algorithms, Support Vector Machine (SVM) can also be used in a fusion process. Each score to combine is arranged in a vector and a training set is used to learn the SVM model. In [START_REF] Czyz | Decision fusion for face authentication 7[END_REF], the SVM fusion to improve face recognition gives slightly better performances than weighted sum. Voice and online signature have been fused with SVM in [START_REF] Garcia-Salicetti | Multimodal biometric score fusion: the mean rule vs. support vector classifiers[END_REF]. In this experiment, arithmetic mean gives best results with noise free data, while SVM gives equivalent results with noisy data.

Discussion

In this paper, we are interested in biometric modality independent transformationbased score fusion [START_REF] Nandakumar | Likelihood ratio-based biometric score fusion[END_REF] where the matching scores are first normalized and second combined. We have previously seen that in this case, arbitrary functions are often used. Our work is based on these various fusion architectures based on score fusion in order to produce a score fusion function automatically generated with genetic programming [START_REF] Koza | Genetic programming[END_REF].

By the way, the definition of a fusion architecture is still an open issue in the multibiometrics research field [START_REF] Ross | Multibiometric Systems: Overview, Case Studies, and Open Issues[END_REF], because the range of possible fusion configurations is very large. We think that using automatically generated fusion functions can bring a new solution to solve this kind of problems.

Material and Methods

In this section, we present all the required information in order to allow other researchers to reproduce our experiment.

Biometric databases

As it is well known that results can be highly related to the database, for this study, we have used three different multibiometric databases: the first one is the BSSR1 [START_REF]Nist biometric score set[END_REF] distributed by the NIST [START_REF]of Standards, Technology, Nist biometric score set[END_REF] (referenced as BSSR1 in the paper), the second one is a database we have created for this purpose (referenced as PRIVATE in the paper) and the third one is a subset of scores computed with the BANCA [START_REF] Bailly-Bailliere | The BANCA database and evaluation protocol[END_REF] database (referenced as BANCA in the text. In fact, BANCA database is composed of templates. We have used the scores available in [START_REF] Poh | Banca score database[END_REF]).

As all these databases are multi-modal, the scores are presented with tuples:

the ith tuple of scores is represented as s i = (s 1 i , s 2 i , ..., s n i ) for a database having n modalities (in our case, n ∈ {4, 5}).

The three databases are presented in detail in the following subsections while Table 1 presents a summary of their description.

BSSR1 database

The BSSR1 [START_REF]Nist biometric score set[END_REF] This database has been used several times in the literature [START_REF] Nandakumar | Likelihood ratio-based biometric score fusion[END_REF][START_REF] Sedgwick | Preliminary Report on Development and Evaluation of Multi-Biometric Fusion using the NIST BSSR1 517-Subject Dataset[END_REF].

PRIVATE database

The second database is a chimeric one we have created by combining two public biometric template databases: the AR [START_REF] Martinez | The ar face database[END_REF] for the facial recognition and the GREYC keystroke [START_REF] Giot | Greyc keystroke: a benchmark for keystroke dynamics biometric systems[END_REF] for keystroke dynamics.

The AR database is composed of frontal facial images of 126 individuals under different facial expression, illumination conditions or occlusions. This is a quite difficult database in reason of these specificities. These images have been taken during two different sessions with 13 captures per session. The GREYC keystroke contains the captures on several session during a two months period involving 133 individuals. Users were asked to type the password "greyc laboratory" 6 times on a laptop and 6 times on an USB keyboard by interleaving the typings.

We have selected the first 100 individual of the AR database and we have associated each of these individuals to another one in a subset of the GREYC keystroke database having 5 sessions of captures. We then used the 10 first captures to create the model of each user and the 16 remaining ones to compute the intra and inter scores.

These scores have been computed by using two different methods for the face recognition (the scores s 1 private and s 2 private and three different ones for the keystroke dynamics (s 3 private , s 4 private and s 5 private scores). The face recognition algorithms are based on eigenfaces [START_REF] Turk | Face recognition using eigenfaces[END_REF] and SIFT keypoints [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] comparisons between images from the model and the capture [START_REF] Rosenberger | Similarity-based matching for face authentication[END_REF]. Keystroke dynamics scores have been computed by using different methods [START_REF] Giot | Keystroke dynamics with low constraints svm based passphrase enrollment[END_REF] based on SVM, statistical information and rhythm measures.

BANCA database

The lastest used benchmark is a subset of scores produced by the help of the BANCA database [START_REF] Poh | Banca score database[END_REF]. The selected scores correspond to the following We have empirically chosen this subset. G1 set is used as the learning set, while G2 set is used as the validation set. Users from G1 are different than users from G2.

Discussion

The main differences between these three benchmarks are:

• the biometric modalities used in BSSR1 and BANCA have better performances than the ones in PRIVATE;

• the quantity of intra-scores is more important in PRIVATE (only one tuple of intra-score per user in BSSR1 instead of several in PRIVATE);

• BSSR1 and BANCA are databases of scores (by the way, we do not know the biometric systems having generated them) whereas PRIVATE is a database of templates (we had to compute the scores);

• BSSR1 and BANCA are more adapted to physical access control applications (i.e., a building is protected by a multi-modal biometric system), while PRIVATE is more adapted to logical access control (i.e., the authentication to a Web service is protected by a multi-modal biometric system).

In the following subsections, we describe the proposed methodology to automatically generate a score fusion function with genetic programming. We adopt the classical score fusion context described in Figure 1(b). Before using the scores provided by different biometric systems, we need to normalize them.

Score Normalization

It is necessary to normalize the various scores before operating the fusion process: indeed, these scores come from different classifiers and their values do not necessarily evolve within the same interval. We have chosen to use the tanh [START_REF] Hampel | Robust statistics: the approach based on influence functions[END_REF] operator to normalize the scores of each modality. Equation ( 1

score ′ = 1 2 tanh 1 100 ( score -µ m gen σ m gen + 1 (1)
We have selected this normalization procedure from the state of the art because it is known to be stable [START_REF] Jain | Score normalization in multimodal biometric systems[END_REF] and does not use impostors patterns which can be hard or impossible to obtain in a real application. The aim of this paper is not to analyse the performance of biometric systems depending on the normalization procedure, but to present a new multibiometrics fusion procedure.

The scores of each modality have been normalized using this procedure.

Fusion Procedure

In this study, we have chosen to use genetic programming [START_REF] Koza | Genetic programming[END_REF] in order to generate score fusion functions. Genetic programming belongs to the family of evolutionary algorithms and its scheme is quite similar to the one of genetic algorithms [START_REF] Mitchell | An introduction to genetic algorithms[END_REF] 1. An initial population is randomly generated. This population is composed of computer programs using the available functions and terminals. The trees are built using a recursive procedure. (c) Creation of the new generation of programs by applying the following genetic operations (depending on their probabilities) to the previously selected programs:

• Reproduction: the individual is copied to the new population.

• Crossover: A new offspring program is created by recombining randomly chosen parts from two select programs. An example is provided in Figure 2.

• Mutation: A new offspring program is created by mutating one node of the selected program at a randomly chosen place. An example is provided in Figure 3.

3. the single best program of the whole population is designated as the winner. This can be the solution or an approximate solution to the problem. Different applications to genetic programming are presented in [START_REF] Poli | A field guide to genetic programming[END_REF] as well as their bibliographic references. The fields of these applications can be listed in curve fitting, data modelling, symbolic regression, image and signal processing, economics, industrial process control, medicine, biology, bioinformatics, compression... but, it seems, so far of our knowledge, that it has not been yet applied to multibiometrics. We only found one reference on genetic programming in the biometrics field. In this paper [START_REF] Day | Robust text-independent speaker verification using genetic programming[END_REF], authors have used genetic programming to learn speaker recognition programs. They have used an island model where different islands operate their genetic programming evolution, and, after each generation some individuals are able to leave to another island. The obtained performance was similar to the state of the art in speaker recognition in normal conditions, but, the generated systems performed better in degraded conditions.

More information about the configuration of the genetic programming system is presented in the next section.

Parameters of the Genetic Programming

We want to use a score fusion function that returns a score related to the performance of a multibiometric system. This score has to be compared with a threshold in order to make the decision of acceptance or rejection of the user.

In this case, none logical operation is required in the generated programs and different information can be extracted from the result of the fusion function (we can compute the ROC curve, the EER, ...).

Fitness Function

The EER (Error Equal Rate) is usually used to compare the performance of different biometric systems together. A low EER means that FAR and FRR are both low and the system has a good performance if its threshold is configured accordingly to obtain this value. For this reason, we have chosen to use this running point to evaluate the performance of the generated score fusion functions.

To compute the EER, we consider the highest and lowest values in the final scores generated by the genetic programming. Then, we set a threshold at the lowest score and linearly increment it until obtaining the highest score value in 1000 steps. For each of these steps, we compute the FAR (comparison between the threshold and the inter scores) and FRR (comparison between the threshold and the intra scores). The ROC curve can be obtained by plotting all these couples of (FAR, FRR), while the EER is the mean of FAR and FRR for the couple having the lowest absolute difference. So, the fitness function is f itness = (F AR i + F RR i )/2, where i is the threshold for which abs(F AR i -F RR i ) is minimal.

Genetic Programming Parameters

In this section, we present the various parameters used in the genetic programming algorithm. Table 2 presents the various parameters of the evolutionary algorithm.

To achieve this experiment, we used the PySTEP [START_REF] Khoury | Python strongly typed genetic programming[END_REF] library. The generated programs contain basic functions (+, -, * , /, min, max, avg). The terminals are the scores of the biometric systems and random constants between 0 and 1.

The whole fitness cases are completed with a single tree evaluation, thanks to the numpy [START_REF] Oliphant | Guide to NumPy[END_REF] library. Each fitness case is a tuple of scores (where each score

Termination criterion

Best individual has a fitness inferior at 0.001 (by the way, this value would never be met . . . ) or maximal number of generations reached.

Learning set

First half of the intra-scores tuples and first half of the inter-scores tuples.

Validating set

Second half of the intra-scores tuples and second half of the inter-scores tuples.

comes from a different biometric modality) and its result value is the score returned by the generated multimodal system. The global fitness value of a tree is the EER value computed with the previously generated scores (computation of the ROC curve, then reading of the EER value from it).

PySTEP is a strongly typed genetic programming engine, but, in our case, we do not use any particular constraints: the root node can only have a function as child (no terminal in order to avoid an unimodal system, and any function of the set), while the other function nodes can have any of the functions as children as well as any of the terminals.

The maximal depth of the generated trees is set to 8. In order to avoid to stay in a local minimal solution, the mutation probability is set to 50%. 500 individuals evolve during 50 generations. We have set this few quantities, because during our investigations, using a population of 5000 individuals on 100 generations did not give so much better results (gain not interesting in comparison to the computation time). Each database has been splitted in two sets of equal size: the first half is the learning set and the second half is the validation set.

The mutation rate is set to 50%, the cross-over rate to 45% and the reproduction rate to 5%. For mutation and cross-over the individuals are selected with a tournament of size 10 with a probability of 80% to select the best individual. The same individual can be selected several times. For the reproduction, the individuals are selected with an elitism scheme: the 5% best individuals are copied from generation n -1 to generation n. During a crossover, only the first offspring (of the two generated ones) is kept.

Results

In this section, we present the results of the generated fusion programs on the three benchmark data sets.

The results are compared to other functions from the state of the art: (a)

the min rule which returns the minimum score value, (b) the mul rule which returns the product of all the scores, (c) the sum rule which returns the sum of the scores, (c) the weight rule which returns a weighted sum, and (d) an SVM implementation. The weighs of the weighted sum have been configured by using genetic algorithm on the training sets [START_REF] Giot | Fast learning for multibiometrics systems using genetic algorithms[END_REF][START_REF] Giot | Low cost and usable multimodal biometric system based on keystroke dynamicsand 2d face recognition[END_REF] (in order to give the best results as possible). The fitness function is the value of the EER and the genetic algorithm engine must lower this value. Table 3 presents the configuration of the genetic algorithm. For the SVM, we have computed the best parameters (i.e., search the C and γ parameter giving the lowest error rate) using the learning database on a 5-fold cross validation scheme. We have used the easy.py script provided with libSVM [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF] for this purpose. We have then tested the performance on the validation set. We only obtain on functional point (and not a curve) when using an SVM. That's why we have used the HTER instead of the EER.

Table 4 presents the performances, for the three databases, of each biometric systems, fusion mechanisms from the sate of the art, and our contribution.

Concerning the state of the art performances, can see that the simple fusion functions sum and mul tend to give better performances compared to the best biometric method of each database, but they are outperform by the weight rule.

The min operator gives quite bad results (it does not improve the best biometric system). The SV M method gives good results but is outperform by the weight method.

Table 5 presents the gain of performance against the weight operator (which gives the best results in Table 4) in term of EER and AUC.

This gain is computed as following:

gain = 100 (EER weight -EER gpf unc ) EER weight (2)
where EER weight and EER gpf unc are respectively the EER values of the weighted fusion and the generated score fusion function (the same procedure is used for the AUC). Better values than the weighted sum are represented in bold. The EER gives a local performance for one running point (system configured in order to obtain an FAR equal to the FRR), while the AUC gives a gives a global performance of the whole system. These two information are really interesting to use when comparing biometric systems. Figure 4 presents the ROC curves of the generated programs against the weighted sum. Performance of the initial biometric systems are not represented, because we have already seen that they are worst than the weighted sum (same remark for the other fusion functions).

Logarithmic scales are used, because error rates are quite small.

We can see from Table 5 and Figure 4 that most of the time, the automatically generated functions with genetic programming give slightly better results than the weighted sum. These improvements can be local and global and vary between 16% and 59% for the EER and 0.05% and 76% for the area under the curve. When there is no improvement, the results are equal or (in one case) slightly inferior. Even if there is some difference between training (not represented in this paper) and validating sets, we cannot observe overfitting problem. The BSSR1 dataset presents the largest difference of performance between training and validation sets, but, the results are still better than the ones from the state of the art (and the same problem can be observe with the weighted sum). By the way, the fitness criterion has never been met, we did not achieve to obtain fusion functions doing no error. So, the evolution always

Discussion

The score fusion functions generated by the proposed approach give a slightly better performance than the fusion functions used in the state of the art in multibiometrics. We can argue that genetic programming is adapted to automatically define score fusion functions returning a score. The tradeoff of this performance gain is the need of training patterns which are not necessary for sum, mul or min (but this requirement is already present for the weighted sum or the use of an SVM). By the way, this is not really a problem, because we already need training patterns to configure the threshold of decision (if we do not want to do it empirically) or if we need to normalize the scores before doing the fusion.

Another problem inherent to genetic programming is the complexity of the generated programs. It is probable that some subtrees could be pruned or simplified without loosing performance. Another trail would be to add regularization parameter to the fitness function (for example, the number of nodes or the depth of the tree). Generated programs would be more readable by an human and quicker to interpret. Figure 6 presents a simple generated tree (depending on the database, they can be more or less complex). Even if the program is quite short (comparing to the other generated functions), it includes useless code (e.g., the subtree avg(a, a -1/12) could be simplified by a -1/24). Some generated trees include preprocessing steps by not using all the modalities in the terminal set.

Genetic programming generated score fusion functions give performance slightly equal or better than genetic algorithm configured weighted sum. Even if computation time is more important than for genetic algorithm, we can think that the gain is not really important between the two methods, but, to obtain these results, genetic programming needed a population ten times smaller and ten times less of generations.

Conclusion

We propose in this paper a new approach for multibiometrics based on the automatic generation of score fusion functions. We have seen interesting approaches in the state of the art and decided to improve them by automatically generated score fusion programs by the help of genetic programming.

Our contribution concerns the designing of multibiometric systems while using a generic approach based on genetic programming (and is inspired from the state of the art architectures). The proposed method returns a multibiometrics score to be compared with a defined threshold. The proposed multibiometric system has been heavily tested on three different multibiometric databases. We obtained great improvements compared to classical fusion functions used in the state of the art. We hope to have opened a new path in the fusion of biometric systems thanks to genetic programming.

  (a) presents this type of fusion. The fusion (a) Template fusion. (b) Classical score fusion. (c) Cascade fusion. (d) Hierarchical fusion.

Figure 1 :

 1 Figure 1: Illustration of different fusion mechanisms.

  database consists of an ensemble of scores sets from different biometric systems. In this study, we are interested in the subset containing the scores of two facial recognition systems and the two scores of a fingerprint recognition system applied to two different fingers for 512 users. We have 512 tuples of intra-scores (comparison of the capture of an individual with its model) and 512 * 511 = 261, 632 tuples of inter-scores (comparison of the capture of an individual with the model of another individual). Each tuple is composed of 4 scores: s = (s 1 bssr1 , s 2 bssr1 , s 3 bssr1 , s 4 bssr1 ), they respectively represent the score of the algorithm A of face recognition, the score of algorithm B of face recognition (the same face image is used for the two algorithms), the score of the fingerprint recognition with left index, the score of fingerprint recognition with right index.

  one labelled: IDIAP voice gmm auto scale 25 100 pca.scores for s 1 banca , SUR-REY face nc man scale 100.scores for s 2 banca , SURREY face svm man scale 0.13.scores for s 3 banca and UC3M voice gmm auto scale 10 100.scores for s 4 banca .

  ) presents the normalization method, where µ m gen and σ m gen respectively represents the average and standard deviation of the genuine scores of the modality m. The genuine scores are obtained by comparing the model and the capture of the same user: they are also called the intra scores. In opposition, the inter scores are obtained by comparing the model of a user with the capture of other users. score ′ and score respectively represents the scores after and before normalisation.

  : a population of computer programs (possibly represented by a tree) evolves during several generations; different genetic operators are used to create the new population. Programs are evaluated by using a fitness function which produces a value that is used for their comparisons and gives a probability of selection during the tournaments. In a system where the computer programs are represented by trees, their leaves mainly represent the entries of the problem, the root gives the solution to the problem and the other nodes are the various functions taking into arguments the values of their children nodes. The leaves are called terminals and can be of several kinds: (a) pseudovariables containing the real entries of the problem (in our case, the list of scores of each modality), (b) some constants possibly randomly generated, (c) functions without any arguments having any side effect, or (d) some ordinary variables. The different genetic operators usually used during the evolution are (a) the crossover, where randomly choose sub-trees have two different trees are exchanged, (b) the mutation, where a sub-tree is destroyed and replaced by another one randomly generated, or (c) the copy, where the tree is conserved in the next generation. The different steps of a genetic programming engine are presented as following:

2 .

 2 The following steps are repeated until the termination criterion is satisfied (the fitness function has reached the right value, or we reached the maximum number of generations). (a) Computation of the fitness measure of each program (the programming is evaluated according to its input data). (b) Selection of programs with a probability based on their fitness to apply them the genetic operations.

2 Figure 2 :

 22 Figure 2: Crossover in genetic programming: node C from tree 1 is exchanged with node 2 from tree 2. Program result 1 is the new individual to add to the new generation.

Figure 3 :

 3 Figure 3: Mutation in genetic programming: node B is replaced by another sub-tree.

Figure 5

 5 Figure5represents the fitness evolution during all the generations of one genetic programming run on the BSSR1 database. A logarithmic scale has been used to give more importance to the low values and track easier the fitness evolution of the best individual of each generation. We can observe the same kind of results with the other databases. The fitness convergence appears several generations before the end of the computation. The worst program of each generation is always very bad which implies that the standard deviation of the fitness is also always quite huge. This can be explained by the high quantity of mutation probability and the low quantity of good programs kept for the next generation. When running the experiment several times, we obtain the same convergence value. We can say that we reach the maximum performance of the system.

Figure 4 :

 4 Figure 4: ROC curves of the fusion systems from the state of the art and with genetic programming. The EER of each fusion function is presented in the legend. Note the use of a logarithmic scale.

Figure 5 :

 5 Figure 5: Fitness evolution of one run of the genetic programming evolution. The max, min, mean and std values of the fitness are represented. We want to minimize the fitness value, so lower is better.

Figure 6 :

 6 Figure 6: Sample of a "simple" generated program. We can observe the complexity of the generated fusion function.

Table 1 :

 1 Summary of the different databases used to validate the proposed method

	Nb of	BSSR1 PRIVATE BANCA
	users	512	100	208
	intra tuple	512	1600	467
	inter tuple	261632	158400	624
	items/tuples	4	5	4

Table 2 :

 2 Summary of the configuration of the genetic programming iterations. Numbers used in function set can be scores or constants.

	Configuration		Values
	Objective		Generates a function producing a multibiometrics score.
	Functions set
				• +: addition of two numbers,	two numbers,
				• -: subtraction of two numbers, • * : multiplication of two num-bers, • /: division of two numbers,	• max: returns the maximum of two numbers, • avg: returns the mean of two
				• min: returns the minimum of	numbers
	Fitness function	Computes the EER of the multibiometric system
	Terminal set
				BSSR1	PRIVATE	BANCA
				• a: s 1 bssr1 , • b: s 2 bssr1 , • c: s 3 bssr1 , • d: s 4 bssr1 , • 50 constants lin-scores from scores from scores from scores from early distributed between 0 and 1.	• a, b, c: keystroke dynamics scores (s 3 private , s 4 private , s 5 private ), • d, e: face recog-nition scores (s 1 private , s 2 private ), • 50 constants lin-early distributed between 0 and 1.	• a: s 1 banca , scores from • b: scores from s 2 banca , • c: scores from s 3 banca , • d: scores from s 4 banca , • 50 constants lin-early distributed between 0 and 1.
	Initial	popula-	500 random trees with a depth between 2 and 8 built with the ramped half and
	tion			half method.
	Evolution	pa-
	rameters
				• Number of individuals: 500, • Maximal number of generations: 50, • Depth limited to: 8, • Probability of crossover: 45%, • Probability of mutation: 50%	• Probability of reproduction: 5% (with elitism), • Selection: tournament of size 10 with a selection probability of 80%.

Table 3 :

 3 Configuration of the genetic algorithm to set the weights of the weighted sum

	Parameter	Value
	Population	5000
	Generations	500
	Chromosome signification	weights of the fu-
		sion functions
	Chromosome values interval [-10; 10]
	Fitness	EER on the gen-
		erated function
	Selection	normalized	ge-
		metric selection
		(probability	of
		0.9)
	Elitism	True

Table 4 :

 4 Performance (HTER in %) of the initial methods (s 1 * , s 2 * , s 3 * , s 4 * , s 5 * ), the state of the art fusion functions (sum, min, mul, weight) and our proposal on the three databases. Bold values represent better performance than the initial biometric systems, and * represents fusion results better than state of the art.

		(a) BSSR1
	Method		HTER
			BSSR1
		s 1 bssr1	04.30%
	Biometric systems	s 2 bssr1 s 3 bssr1 s 4 bssr1	06.19% 08.41% 04.54%
		sum	00.70%
		min	05.04%
	Fusion functions	mul	00.70%
		weight	00.38%
		SV M	0.77% (FAR=1.16%, FRR=0.39%)
	Proposal	gpI	0.40%
		(b) PRIVATE
	Method		HTER
		PRIVATE
		s 1 private	8.92%
	Biometric systems	s 2 private s 3 private	11.53% 15.69%
		s 4 private	06.21%
		s 5 private	31.43%
		sum	02.70%
		min	13.72%
	Fusion functions	mul	02.67%
		weight	02.26%
		SV M	05.47% (FAR=10.87, FRR= 0.07%)
	Proposal	gpA	01.57%*
		(c) BANCA
	Method		HTER
			BANCA
		s 1 banca	04.38%
	Biometric systems	s 2 banca s 3 banca s 4 banca	11.54% 08.97% 07.32%
		sum	01.28%
		min	04.38%
	Fusion functions	mul	01.28%
		weight	00.91%
		SV M	01.01% (FAR= 1.71 %, FRR=0.32%)
	Proposal	gpΦ	00.75%*

Table 5 :

 5 Performance gain betwain our proposal and the weighted sum (which gives the best results in the methods of the state of the art).

	Database	EER	AUC
	BSSR1	-5.26%	0.05%
	PRIVATE 34.85% 23.85%
	BANCA	17.58% 76.74%
	ended when reaching the 50 th generation.

Results could surely be improved by using different parameters in the genetic programming engine (i.e., more individuals and generations, different range of constants, different functions, . . . ). It could be interesting to test other performance metrics could be improved by adding quality measures of the capture, and if genetic programming could produce template fusion programs.

Acknowledgment

The authors would like to thank: the author of pySTEP [START_REF] Khoury | Python strongly typed genetic programming[END_REF], the library used during the experiment, for his helpfull help when encoutering problems with it, the authors of the various biometric databases used in this experiment, as well as the French Basse-Normandie region for its financial support.


Member, IEEE B Tamadazte
email: brahim.tamadazte@ens2m.fr.

N Le-Fort

S Piat

Dembélé

Robotic Micromanipulation and Microassembly using Mono-view and Multi-scale Visual Servoing

Keywords: Microassembly, micromanipulation, microrobotic, multiple scale visual servoing, depth-from-focus. I

This paper investigates sequential robotic micromanipulation and microassembly in order to build 3-D microsystems and devices. A mono-view and multiple scale 2-D visual control scheme is implemented for that purpose. The imaging system used is a photon video microscope endowed with an active zoom enabling to work at multiple scales. It is modelled by a non-linear projective method where the relation between the focal length and the zoom factor is explicitly established. A distributed robotic system (xyθ system, φz system) with a twofingers gripping system is used in conjunction with the imaging system. The results of experiments demonstrate the relevance of the proposed approaches. The tasks were performed with the following accuracy: 1.4 µm for the positioning error, and 0.5 • for the orientation error.

in the microdomain [START_REF] Tamadazte | Real-time vision-based microassembly of 3d mems[END_REF], [START_REF] Devanathan | Multi view and multi scale image based visual servo for micromanipulation[END_REF], [START_REF] Fatikow | Microrobot system for automatic nanohandling inside a scanning electron microscope[END_REF], [START_REF] Feddema | Parallel assembly of high aspect ration microstructures[END_REF], [START_REF] Ralis | Micropositioning of a weakly calibrated microassembly system using coarse-to-fine visual servoing strategies[END_REF], [START_REF] Ferreira | Automatic microassembly system assisted by vision servoing and virtual reality[END_REF]. Also, in the literature, it was shown that vision feedback control is an appropriate solution in the automation of microhandling and microassembly tasks. However, a large part of the control laws presented in the literature are of image-based visual servoing type; few works deal with the use of pose-based visual control techniques and still less concern multiple scale control laws approaches. In [START_REF] Devanathan | Multi view and multi scale image based visual servo for micromanipulation[END_REF] and [START_REF] Sun | Image-based visual servo for micromanipulation : a multiple-view and multiple-scale approach[END_REF], the authors proposed the use of a distributed imaging system: a high resolution optical microscope delivering a local view and a camera equipped with standard lens delivering a global view of the workscene. That dual system was, then, used to realize a multi view and multi scale image-based visual servo. However, multiple scale approaches can be computed and implemented using a single imaging system. This one have to be equipped with an electronically controllable zoom (active zoom). An illustration is stated in [START_REF] Tao | Microassembly of peg and hole using active zooming[END_REF], where a multiple scale image visual control using active zooming prevents the target to go out of the field of view.

In this paper, a full automatic micromanipulation and microassembly have been investigated. Our contribution concerns the design of a new visual feedback method. This method is based on a mono-view and multiple scale image-based visual servo using dynamic zoom and focus and is decomposed in two mains parts. The first part is the definition of a multiscale model of the video microscope that the parameters are obtained by applying a new calibration method. The originality of this method lies especially in the computation of the multiple scale (for each magnification step) model of the optical microscope using a 2D virtual template. Thus, the relation between the focal length and the zoom factor is established and introduced in the visual control law. The second part concerns the development of the visual-based control law using only a single view. Due to the weak depth of field of the video microscope, a depth-from-focus method is used to compute the depth information between the microscope and the gripper. This information is used in the visual control law in order to maintain the focusing of the video microscope on the micromanipulator during the micromanipulation or microassembly process.

This new approach is well appropriated for the performing of micromanipulation and microassembly processes needed a very high precision. The method and algorithms proposed had been implemented on an experimental setup including a five degrees of freedom (dof) distributed robotic system (three dof (xyθ) dedicated to the mobile platform and two dof (zφ) dedicated to the manipulator), a gripping system, an imaging system and a clean environment. The micro-objects to handle or assemble consist of 400 µm × 400 µm × 100 µm silicon components.

This paper is structured as followed: Section II presents the decomposition of the robotic micromanipulation process as a sequence of basic tasks. Section III develops the concepts of the mono view multiple scale visual control. A multiple scale modelling of the photon video microscope is proposed in section IV. The corresponding calibration approach combining robotic and vision is also presented. Section V exposes the vision algorithms used in the experiments. They include the tracking of the micro-object and of the gripper in the images of the scene, the autofocus achievement and the recovery of depth. The experimental setup and related results are presented in section VI. They show the relevance of the proposed concepts.

II. TASK PLANNING OF ROBOTIC MICROMANIPULATION

Robotic manipulation corresponds to the handling and positioning of microparts by means of a robotic system in conjunction with a gripping system and an imaging system.

Let the purpose of the primary (manipulation) task be a cyclical pick up of microparts from the initial locations and their place in target locations. The function chart of Fig. 1 is the representation of a sequence enabling the achievement of the pick-and-place process. Some tasks require high accuracy, so it is recommended to check up on their success rate. The chart representing the sequence can include this possibility as illustrated in Fig. 1.

• task 1: autofocusing. This task enables to keep the micro-object focused in the images of the scene during the process. • task 2: detection of the component. The gripping of the part assumes its recognition and localization in the scene. • task 3: aligning of the component in parallel to the axis. This task includes the increasing of the scale. • task 4: positioning and centering of the component under the gripper. This task includes the increasing of the scale. • task 5: opening of the gripper fingers.

• task 6: descent of the gripper.

• task 7: closing of the gripper fingers. Every finger-tip (p1 and p2 for the upper and lower tip, respectively) is displaced into a contact point (p * 1 and p * 2 , respectively) located in the gripping plane of the micropart.

• task 8: grasping of the component. This task is performed using a vision-based control law. • task 8: ascent of the gripper with the component.

• task 9: positioning of the component in the target place.

• task 10: descent of the gripper with the component.

• task 11: opening of the gripper in order to release the component. This task is decisive in the process, because of the high level of capillary forces [START_REF] Fearing | Survey of sticking effects for micro parts handling[END_REF]. The micro-object tends to stick on the fingers after their opening. • task 12: positioning of the gripper back to its initial place.

The sequence of tasks can be considered as a model for the behavior of the systems dedicated to perform the manipulation task. Consequently, it can be used as means to perform the control of these systems. The manipulation appears as a sequence of servo controls including visual controls. As the optical microscope used is a multiple scale imaging systems (equipped with a dynamic zooming system), dynamic and multiscale visual servoings are developed here.

III. MULTIPLE SCALE VISUAL CONTROL

Image-based visual control, more particularly 2-D visual servoing is accurate and robust towards the errors of modelling of the imaging and the robotic systems [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF]. Thus, this kind of servoing is suitable for the achievement of basic manipulation tasks. Among the various choices of control laws, exponential and polynomial decrease of error exhibit high efficiency.

A. Modelling of image-based visual control law integrating the zoom control

From a general point of view, the aim of vision-based control schemes is to minimize the error e(t) [START_REF] Hutchinson | A tutorial on visual servo control[END_REF] typically defined by:

e(t) = s(m(t)) -s * (1)
where m is a set of visual information s extracted from the image (e.g. the image coordinates of interest points) and s * the desired visual features. In our case, the vector e contains the coordinates of the four corners of the bonding box (tracking windows) delimiting the micro-object to be handling. The introduction of the zoom control in the final visual control law can be summarized by adding a new degree of freedom.

In multiple scale visual control laws, the focal length f , the desired value of the visual feature points s * and the current value of these points s are functions of the zoom factor ζ: f (ζ), s * (ζ) and s(ζ), (Fig. 2). Therefore, (1) becomes:

e(t) = s(m(t, ζ)) -s * (ζ) (2)
Fig. 1. Sequential function chart of the picking and placing of a microcomponent.

Designing the control scheme requires the computation of the relationship between the time variation of s(ζ) and the camera velocity. Let the spatial velocity of the camera (optical microscope) be denoted by v = (v, ω): v is the instantaneous linear velocity and ω is the instantaneous angular velocity. In the case of controlling a 6 dof robot, v = (v x , v y , v z ) and ω = (ω x , ω y , ω z ) . In our case, a 5 dof microrobot is considered e.g., 3 dof (x, y, θ) for the positioning platform and 2 dof (z, φ) for the micromanipulator, so v = (v x , v y , v z ) and ω = (ω θ , ω φ ) . In [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF], the relationship between the velocity variations of ṡ and v is given by:

ṡ = L s v (3)
where L s (L s ∈ R n×6 ) is the interaction matrix (also called jacobian image) related to s. The parameter n represents the number of visual features used.

In our case, L s is function of s, ζ and Z * , so the (3) becomes:

ṡ = L s (s, Z * , ζ)v (4)
where Z * is the desired depth information processed by the depth-from-focus method presented in the section V-B. If we consider a 3-D point P with the coordinates (X, Y, Z) in the camera frame R c , which can be projected in the image frame R I with the coordinates p = (x, y), we obtain:

x = X/Z = (u -x 0 ) /f (ζ) (5) y = Y /Z = (u -y 0 ) /f (ζ) (6)
where (x 0 , y 0 ) and f (ζ) are the optical microscope intrinsic parameters (these parameters are computed using the calibration method presented in the section IV). More precisely, (x 0 , y 0 ) are the coordinates of the principal point and (u, v) are the coordinates of the image point p expressed in pixel units.

Performing time derivation of ( 5) and ( 6), with some handling (more details can be found in [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF]) we obtain:

L s = L s (x(n), Z * , ζ) L s (y(n), Z * , ζ) (7)
where:

Ls(x(n), Z * , ζ) =     -1 Z * 0 x 1 (ζ) Z * x1(ζ)y1(ζ) -1 -x 2 1 (ζ) y1(ζ) -1 Z * 0 x 2 (ζ) Z * x2(ζ)y2(ζ) -1 -x 2 2 (ζ) y2(ζ) -1 Z * 0 x 3 (ζ) Z * x2(ζ)y2(ζ) -1 -x 2 3 (ζ) y3(ζ) -1 Z * 0 x 4 (ζ) Z * x2(ζ)y2(ζ) -1 -x4(ζ) 2 y4(ζ)     (8)
Ls(y(n), Z * , ζ) =     0 -1 Z * y 1 (ζ) Z * 1 + y 2 1 (ζ) -x1(ζ)y1(ζ) -x1(ζ) 0 -1 Z * y 2 (ζ) Z * 1 + y 2 2 (ζ) -x2(ζ)y2(ζ) -x2(ζ) 0 -1 Z * y 3 (ζ) Z * 1 + y 2 3 (ζ) -x3(ζ)y3(ζ) -x3(ζ) 0 -1 Z * y 4 (ζ) Z * 1 + y 2 4 (ζ) -x4(ζ)y4(ζ) -x4(ζ)     (9)
We can define the relationship between the camera velocity and the time variation of e given by ( 1). This relation is:

ė = L s v (10)
If we want to ensure an exponential decoupled decrease of the error e, we can write:

ė = λe (11)
where λ is a positive gain. Therefore, from ( 10) and ( 11), the control law can be deduced.

v = -λL + s e (12)
with L + s is the pseudo-inverse of L s . If det(L s ) = 0 it is possible to use directly the inverse L -1 s of the interaction matrix L s , giving the control law:

v = -λL -1 s e (13)
To improve the convergence rate and the stability of the developed control law, we have implemented an adaptive gain (the gain decreases when the error decreases). Therefore, the positive gain λ is replaced by the adaptive gain λ a processed as follows:

λ a = (λ min -λ max )exp -ρ e + λ max (14)
where λ max and λ min are the maximum and minimum values of λ a . The experimental results presented in this paper are obtained with λ min = 0.1 and λ max = 1. The parameter ρ allows the tuning of the exponential decreasing rate of the error and e is its related norm. The evolution of the λ a during a micromanipulation task is shown in Fig. 10. The multiple scale visual servoing scheme can be represented by the function chart given in Fig. 2.

+ s * (ζ)

B. Gripper closing controlled by visual servoing

Once the micro-object and the gripping end-effectors are positioned to their respective desired positions, it is necessary to control the gripping system in the aim to grip the microobject (gripping task). An appropriate tightening force is required, which would enable the gripping without destruction of one or both the micro-object and the gripper tips. In this case, a control approach based on microforce feedback control law is used. Our gripping system is not equipped with a microforce sensor, so the gripping task is ensured by a visionbased control technique. This control law consists of regulating towards zero the distance between the desired value s * f and the current value s f of the image points.

Let the distance corresponding to the task function be e 1 (t):

e 1 (t) = ∆(s * f -s f (t)) (15)
The polynomial decrease of the error e 1 (t) leads to the following control:

v d1 (t) = e 1 (t) N (16)
where v d1 (t) is the input for the actuator of the first fingertip of the gripper and N is a constant integer. For the second finger tip, the input v d2 (t) is deduced by symmetry and it is given by:

v d2 (t) = -v d1 (t) = e 1 (t) N (17)

IV. MULTISCALE MODELLING OF THE PHOTON VIDEO MICROSCOPE

A. Basic model

The standard lens based image source is modelled by the non linear projective model. The latter includes: the intrinsic parameters inherent to the imaging system (i.e. the focal length f , the scale factors k x , k y in x and y directions), the principal point coordinates (x o , y o ), the extrinsic parameters corresponding to the position and orientation of the focusing element frame (usually called camera) with respect to the scene frame i.e. the translation components T x , T y , and T z , and for example, Euler angles α, β and γ, and the distortion parameters: the radial (r 1 , r 2 , ...) and tangential (t 1 , t 2 , ...) distortion coefficients.

The improvement of technology enables the manufacturing of isotropic image sensors in which the scale factors along x and y are identical:

k x = k y = k (18)
The microscope-based image source is an optical imaging and thus can be modelled by the non linear projective model. However, the quality of a laboratory microscope is usually better than that of a standard lens, so experimental values of distortion parameters are very weak. They range from 10 -8 µm -2 to 10 -10 µm -2 [START_REF] Zhou | Calibration of a parametric model of an optical microscope[END_REF], [START_REF] Ammi | Flexible microscope calibration using virtual pattern for 3-d telemicromanipulation[END_REF]. As a consequence the distortion can be neglected and so the video microscope can be modelled by the linear projective model. This model consists of a perspective projection of a scene point P onto a pixel p in the retinal plane through the optical center.

Let P and p be represented by the homogeneous vector (X, Y, Z, 1) and (x, y, w) , respectively. The model can be written:

p = QP ( 19
)
where Q is the 3×4 homogeneous projection matrix of the image source. It is written:

Q = K   1 0 0 0 0 1 0 0 0 0 1 0   D (20)
The general form of the matrix K is given by:

K =   k x f -k x f cos(ψ) x o 0 k y f / sin(ψ) y o 0 0 1   ( 21
)
where ψ is the angle between the image axes u and v. In general, the pixels are square, so ψ = 90 • .

Taking into account all the simplifications presented above, the matrix K becomes:

K =   kf 0 x o 0 kf y o 0 0 1   (22)
Concerning the matrix D, it combines the rotation matrix R and the translation vector T as follows:

D = R 3×3 T 1×3 0 1 (23)
The rotation matrix which gathers the three rotation angles (if the Euler angles α, β, and γ are considered) is given by:

R = R x R y R z (24)
where:

Rx =   1 0 0 0 cos α -sin α 0 sin α cos α   (25)
Ry =   cos β 0 sin β 0 1 0 -sin β 0 cos β   ( 26
)
Rz =   cos γ -sin γ 0 sin γ cos γ 0 0 0 1   (27)

B. Multiscale model

Multiscale calibration is required because the video microscope works at multiple zoom or magnification. Thus, it is necessary to introduce the zoom factor ζ in the previous intrinsic model:

K(ζ) =   f (ζ)k 0 x o 0 f (ζ)k y o 0 0 1   (28)
It can be noticed that the principal point (center of the zooming) coordinates (x 0 , y 0 ) do not change during the decreasing and the increasing of magnification (see, Fig. ??). The coordinates of the principal point are computed by tracking the displacements of a micro-object placed on the positioning platform. The displacements of the micro-object are directly linked to the magnification changes.

In a microscope where a tube is associated with the lens, the parameter f in the previous equations becomes the sum of the objective focal length f ob and the length of this tube l t [START_REF] Zhou | Calibration of a parametric model of an optical microscope[END_REF]: The relationship that links f with ζ is given by:

f = f ob + l t (29)
ζ = l t f ob (30)
Knowing l t , it is possible to compute the objective focal length f ob by:

f ob = l t ζ (31)
From ( 29) and (30), a relationship can be established between f and ζ. This relationship is given by:

ζ = l t f -l t (32)
then,

f = 1 + 1 ζ (33)
It is also possible to generalize the expression of f according to the variation of ζ. Therefore, a non linear relation links the zoom factor ζ with the focal length f is established. This relation can be represented by a polynomial relation as follows:

f = l t + l t a i ζ 10 ζ 9 • • • 1 a i . ζ 10 ζ 9 • • • 1 (34) then, f = lt 1 + 1 a i ( ζ 10 ζ 9 • • • 1) (35)
where:

a i = [a 1 a 2 • • • a 11 ] (36)
is (1 × 11) vector whose elements are polynomial coefficients.

C. Computing the parameters at multiple scale

There are similarities between vision sensing at the macro, meso and microscales. For each scale a 2-D image is formed from a 3-D object through an optical lens system. As they are modelled by the same method, the same approaches of calibration can be achieved. These techniques are roughly classified into two families: photogrammetric calibration approaches and self calibration approaches. In the first method, the model parameters are computed by observing a calibration object (3-D pattern) whose geometry is known with high accuracy. The calibration object usually consists of 2 or 3 planes, ones orthogonal to each other. An unique plane object is also used, but in this case, several images at different 3-D orientations are considered [START_REF] Tsai | A versatile camera calibration technique for high-accuracy 3d machine vision metrology using off-the-shelf tv cameras and lenses[END_REF], [START_REF] Tiggs | Autocalibration from planar scenes[END_REF]. In the second method, it is not necessary to use a calibration pattern. The correspondences between images of a static scene are enough to recover both intrinsic and extrinsic parameters. In this case the accuracy is not as good as in the previous approaches [START_REF] Tiggs | Autocalibration from planar scenes[END_REF].

In any case, an important number of correspondences p -P are required. Calibration is performed in two stages. The first stage consists of roughly estimating the projection matrix Q by resolving the DLT (Direct Linear Transformation) which is obtained by combining the projection equations for points of correspondence. The second stage enables the fine estimation of the parameters by minimizing a criterion, usually the geometric error δ.

δ = i d(p i , QP i ) (37)
Even if the same algorithm can be implemented both in macro and microscales, there are some fundamental differences between a standard lens and a high magnification lens. A microscope is characterized by weaker DOF (Depth-Of-Field) and F OV (Field-Of-View).

As a consequence of these limitations, a 3-D calibration template cannot be used. The pattern is reduced to a planar object that should be almost parallel to the lens. A video microscope is heavy and cumbersome and is thus not easy to manipulate. These constraints complicate the calibration of the video microscope. On the other hand, the presence of accurate motion sources like xyz stages enables accurate motions of the calibration sample plane and facilitates the calibration.

Instead of using a real pattern or virtual points, the proposition is to use the power of image processing: the center of gravity of a micrometric part is tracked in the images of the scene. The micropart is moved accurately (with steps of 300 µm) by a xyz stage, so its central position in the scene is known with high accuracy using an autocorrelation detection method. These positions are used to synthesize a virtual image which is used in the algorithm presented previously. This approach enables high accuracy in computing of the model parameters. The approach is also simple, as it does not require the micromachining of any particular pattern. The components necessary for the assembly are directly used.

V. VISION ALGORITHMS

A. Tracking of micro-objects and end-effectors

Image processing and vision are very important in visual servoing. The following conditions are essential for the success of the control:

• Vision should be able to deliver visual information at a rate close to the sampling frequency of the robot control; • Interaction matrix should be explicitly calculated;

• Control must be robust to little occlusions (like the passage of the micro-object under the gripper). There are several methods of visual tracking which are usually classified into two groups. The first group consists of the tracking of local features like lines, segments, points, edges, etc. [START_REF] Liu | Robust contact detection in micormanipulation using computer vision microscopy[END_REF]. The results of these techniques highly depend on the quality of the images and remain very sensitive to feature detection [START_REF] Malis | Improving vision-based control using efficient second-order minimization techniques[END_REF]. The other group contains methods that perform a comparison between two frames in the image sequence by minimizing an error based on the image brightness. These methods take into account some parameters like motion, deformation or illumination parameters between the two frames or the frame and a template.

Images of the planar silicon microparts as well as those of the gripper tips are not very sharp because of the properties of the microscope. Consequently, a robust tracking algorithm able to work in real-time is required. The tracking is achieved by an algorithm proposed in [START_REF] Malis | Improving vision-based control using efficient second-order minimization techniques[END_REF] and [START_REF] Silveira | Real time tracking under arbitrary illumination changes[END_REF]. This algorithm is based on the second-order-minimization. It has a far superior convergence rate than other techniques, which is an important property for real-time tracking. For instance, if we consider the window I * of m pixels which contains the micro-object as the reference, then tracking I * in the global current image I consists in computing a vector V . This vector of (8 × 1) size includes the parameters of the projective transformation H. It transforms each pixel p * from the reference image I * to the current image I using the following relationship:

I (w(H)(p * i )) = I * (p * i ) (38)
In the reference [START_REF] Benhimane | Homography-based 2d visual tracking and servoing[END_REF], for an approximation V of V , or Ĥ of H, the problem is to find an incremental transformation H(V ) such as the difference between the region image I transformed with the composition w( Ĥ)•w H(V ) , and the corresponding region in the image I * is zero. It involves to find the vector V such that ∀i ∈ (1, 2, ..., q), we have:

y i (V ) = I w( Ĥ) • w (H(V )) (p * i ) -I * (p * i ) = 0 (39)
where w(H) represents an automorphism transformation. Let be the (q × 1) vector y(V ) which represents these differences between I and I * . Therefore, we can write:

y i (V ) = [ y 1 (V ), y 1 (V ), • • • y q (V ) ] (40)
The solution of the equation ( 40) can be computed by finding V = Ṽ which verifies the following system:

y( Ṽ ) = 0 (41)
In our case, for the micro-object, the coordinates of the four points delimiting the bounding box (searching template W 1 ) of the micropart is estimated (Fig. 4). For the above finger the coordinates of the tip (point p 1 = (u 1 , v 1 )) is estimated. This point is the bottom left point of the searching template W 2 delimiting the gripper tip. The coordinates of the below tip (point p 2 = (u 2 , v 2 )) is deduced by symmetry.

B. Autofocus achievement and depth recovery

Because of the weakness of the DOF , an autofocus method is implemented in order to guarantee focused images during the experiments. The depth of the scene is scanned step by step, images are acquired and the focus is estimated. The system is repositioned at the position where the focus estimation is the highest. Three focus estimators (presented in [START_REF] Sun | Autofocusing algorith selection in computer microscopy[END_REF]) have been tested: the variance, the intercorrelation and the Brenner gradient. The variance focus estimator given by (42), is selected as it makes a trade off between resolution and computing time.

F Var = 1 H.W.µ H W (i(x, y) -µ) 2 (42)
where H and W are the image height and width, i is the (x, y) pixel intensity and µ is the mean of image intensity, respectively. The representation of the focus estimation according to z motion gives two peaks (Fig. 5). The low peak corresponds to the gripper and the high peak corresponds to the platform and the component. Therefore, it is possible to determine the depth Z * between the camera and the micro-object:

Z * = Z o -Z g (43)
where Z o is the distance between the micro-object and the gripper and Z g represents the distance between the camera (microscope) and the gripper. This depth information Z * is used to servo the motion of the video microscope on the motion of the gripper, see Fig. 6.

VI. EXPERIMENTAL SETUP A. Micromanipulation and microassembly workcell

The above concepts were validated using the microassembly workcell shown in Fig. 7.(a). The complete workstation Fig. 6. Focus-based gripper tracking includes a robotic system in combination with a gripping and an imaging system. The whole setup is located inside a controlled environment and posed on a vibration-free table. Two PCs connected by an Ethernet link process the information, the first (Pentium (R) D, CPU 2.80 G Hz, 2 Go of RAM) is dedicated to vision algorithms while the second (Pentium (R) 4, CPU 3.00 G Hz, and 1 Go of RAM) is used for control algorithms. In a kinematic point of view, the workstation is a five dof robotic system. Three dof (x, y and z) in translation are achieved by three high accuracy linear stages and two dof (θ and φ) in rotation are achieved by two high accuracy angular stages (all from Polytec PI). The translation motions x,y, and z are characterized by a resolution r = 0.007 µm, an increment i = 0.05 µm, a velocity v t = 1.5 mm/s, a stroke of s t = 25 mm. The specifications of the angular motions are: r = 26 µrad, i = 26 µrad and speed v r = 45 deg/s. These dof are distributed into two robotic systems: a xyθ system and a zφ system. The former system (the positioning platform) is equipped with a compliant table (the table is supported by three springs) and enables the positioning in the horizontal plane. The latter system (the manipulator) supports the gripper and enables the vertical positioning and spatial orientation of micro-objects.

A Microrobotic Microprehensile On Chip (MMOC) gripper (Fig. 8) developed in the department AS2M of FEMTO-ST Institute is used for the handling of micro-objects [START_REF] Agnus | Overview of microgrippers and design of a micromanipulation station based on mmoc microgripper[END_REF]. It is a two-fingers gripping system with four dof (two dof by finger). It enables open-and-close motions as well as up-and-down motions. Every finger is a piezoelectric bimorph with two end-effectors made of silicon layers (12 µm and 400 µm) separated by an oxide layer (1 µm) (Fig. 8). Modularity was an important design criterion during development, and the MMOC microgripper has been designed in order to use different end-effectors, e.g. silicon finger tips, nickel finger tips. It can grab a high variety of objects according to the type of material and the end-effectors shape: planar silicon micro-objects, balls, gears, optical fibers etc. The imaging system is a video stereo microscope of the type LEICA MZ 16 A. It delivers a top view of the work scene. The zoom (and thus the magnification) and the focus are motorized and controlled by a PC. The F OV varies from 700 µm × 900 µm (with a resolution of 1.4 µm) at the maximum magnification to 20 mm × 25 mm (with a resolution of 21 µm) at the minimum magnification. The DOF varies from 2.9 mm to 0.035 mm and the work distance is approximately 130 mm. The workcell is also equipped with a long tube video microscope for the side view but this latter is not considered in this paper.

The objects to manipulate are structures etched in a silicon wafer of different sizes (see Fig. ??). They have at least a notch of 100 µm on each side enabling them to be assembled to each other to form 3-D structures.

B. Optical microscope calibration results

The optical microscope calibration involves two stages: the establishment of the relation between the scale k and zoom ζ factors and the computing of the intrinsic parameters K at a given zoom factor ζ.

A metal object with three holes is used in this stage. The diameters of the holes are estimated to d 1 = 1961.5 µm, d 2 = 1037.5 µm and d 3 = 429.85 µm using a SEM (Scanning Electron Microscope) of r = 10 nm resolution. According to the zoom factor the relevant hole image is considered.

The zoom factor ζ (called magnification according to the supplier) is modified with a step of 0.05× and then 172 images are acquired. In every image the relevant hole is detected using the normalized correlation and the scale factor k corresponding to the ratio of the diameter (d 1 , d 2 or d 3 ) of the hole in µm and in pixel is computed.

For the second stage of calibration, a planar virtual pattern is achieved from the tracking of a silicon micro-object of 400 µm × 400 µm × 100 µm.

Using the calibration method presented above, it is possible to compute the extrinsic parameters α, β, γ, T x and T y and the intrinsic parameters k x , k y , f and the coordinates of the principal point (x o , y o ). It remains to define the third component of the translation vector T z and the optical microscope working distance d. The T z can be computed using the relationship given in [START_REF] Zhou | Calibration of a parametric model of an optical microscope[END_REF]:

T z = f ob ζ + 1 ζ . ( 44
)
It is also possible to write the following approximation:

T z ≈ f + d (45)
From (45), it is possible to compute the working distance d:

d ≈ T z -f (46)
Now, all the calibration parameters (intrinsic and extrinsic) of the optical microscope are computed. These parameters are summarized in the Table I for the zoom factor position ζ = 38×.

C. Micromanipulation and assembly results

As presented previously, the basic tasks of aligning (task 5) and centering (task 6) are performed by visual servoing with the exponential decrease of error and adaptive gain, while the task of closing (task 9) is performed by another visual control with a polynomial decrease of error. Figure 10.(a) shows the result of the centering of the micropart with respect to the gripper (basic task 6). It can be seen that the implementation of an adaptive gain prevents the overshoot of the reference position. The final error is about 0.2 pixel (0.28 µm) in x and y directions. Figure 10.(b) shows the result of the microobject alignment parallel to the x axis (basic task 5). It can be seen that the angle decreases exponentially to zero. The final error is about 0.5 degrees. This very small value shows the relevance of the control law.

D. Pick-and-place cycle results

The sequence of tasks represented in Fig. 1 which models the pick-and-place of a silicon micropart, is performed several

Several conclusions can be made from these experiments; the first lesson is the robustness of the visual tracking used. Despite the weak quality of the scene images and a great occlusion, the algorithm can track the micropart. It continues to work for an occlusion of 1/4 of the micropart by the gripper or when the micro-object is outside the field-of-view of the imaging system (case 3 of Table II). Occlusions are responsible of about 17 % of failures (case 5 of Table II). The second lesson that can be retrieved is the accuracy of the visual control: the mean and standard deviations of error are summarized in Table III. There are a couple overshoots, and they do not lead to failures.

The success rate obtained is about 72 %. Error of control is the cause for around 22 % of failures (case 4 of Table II). The third conclusion to be drawn from the previous results is the importance of physical phenomena such as electrostatic and capillary forces. The presence of electric charges on both parts and fingers causes the former to move to the latter during the gripper closing and leads to the failure of the cycle. The electrostatic force is responsible for about 37 % (case 6 of Table II) of failures. Hydrometries are high enough in the scene to prevent the unsticking of the micropart on the gripper fingers because of capillary force. This phenomenon is responsible for about 24 % of failures (see case 7 of Table II of failure due to electrostatic force).

E. Microassembly results

Two types of 3-D devices were assembled. Each type of these devices is performed ten times. In the first hand, the assembly process targets the insertion in each other of two micro-objects (the same as those used in the micromanipulation tasks validation). More precisely, these microcomponents are assembled by their respective notches (100 µm × 100 µm × 100 µm). The mechanical play (insertion tolerance) is estimated to 3 µm. The low level of positioning and orientation errors (translation error is about 1.4 µm and orientation is about 0.5 • ) enabled the insertion despite the mechanical play of 3 µm. Therefore, the 3-D microstructures built are solid without requiring external fixing process (see, Fig. 12).

It is also possible to assemble 3-D microstructures much more complex. For instance, it can be possible to assemble five micro-objects and to build a solid 3-D MEMS on 3-levels as illustrated in figure 13 (this image is acquired with the second imaging system which equipped the microassembly workcell). Even without external fixing the structure assembled is solid. Concerning the mean cycle time necessary to assemble two microparts (including positioning of the micropart one, positioning of the micropart two and the insertion of the micropart one into the micropart two) is about 40.8 seconds. Such precise assembly at real time has never been presented in the literature. With these performances, it also possible to envisage such concepts for industrial use.

VII. CONCLUSION

The problems of robotic micromanipulation and microassembly of micrometric devices were studied through this paper. Despite the wealth and importance of scientific contributions in this field, there are still many efforts to get the famous flexible, modular, versatile, repeatable and precise process. In this paper, we are more interested in performing high precise micromanipulation and microassembly processes using vision feedback controls. The vision system delivers images from which a lot of information can be extracted. The problem is that high resolution (local view) and low resolution (global view) information must be caught at the same time. An interesting solution to this problem is the multiple scale imaging using a photon video microscope equipped with a tunable zoom. This multiple scale model of the video microscope is used in the visual control law.

The analysis of a complex micromanipulation or microassembly tasks leads to its decomposition into a set of basic tasks like orientation, positioning, centering, gripping, transfer, insertion, release of the micro-object. The concepts developed in this paper are validated by full-automatic pick-and-place cycles and by the assembly of 400 µm × 400 µm × 100 µm silicon micro-objects. These processes are realized using a five dof workcell which integrates a robotic system including a xyθ and a φz sub-systems, a two-finger gripper, a photon video microscope with controllable zoom (magnification from 0.71× to 11.5×) and focus. The results of experiments demonstrate the relevance of the proposed concepts. For example, the tasks were performed with the following accuracy: the positioning error reaches 1.4 µm (for x, y and z stages) and 0.5 • for the orientation θ and φ stages.

Further work will concern the efficiency improvement of the previously proposed concepts by increasing the complexity of the operations in order to built MEMS more compact. It would also be interesting to reduce the size of these micro-objects to few micrometers and to detect the limitation of the use of the vision control feedback in the MEMS microassembly domain.

Fig. 2 .

 2 Fig. 2. Multiple scale image-based visual servoing scheme.

Fig. 3 .

 3 Fig. 3. Center of zooming.

Fig. 4 .

 4 Fig. 4. Image captured during the micro-object tracking.

Fig. 5 .

 5 Fig. 5. Focus estimation result.

Fig. 7 .

 7 Fig. 7. Microassembly workcell. Image (a) illustrates a global view of station and image (b) shows a zooming view in the MMOC.

Fig. 8 .

 8 Fig. 8. Photography of the MMOC gripping system.

Fig. 9 .

 9 Fig. 9. Silicon microcomponents of experiments.

Fig. 10 .

 10 Fig. 10. Centering and orientation errors versus the number of iterations.

Fig. 11 .

 11 Fig. 11. Some shots during the aligning, positioning, centering, gripping and rising of the micro-object. Image (a) illustrates the initial position of the microobject with a low magnification, images (b), (c) and (d) show intermediate positions during the control of the positioning platform.

Fig. 12 .

 12 Fig. 12. Some SEM views of the 3-D structure after assembly. We can see the size of the mechanical play (insertion tolerance of the assembly) in the zoomed image (3).

Fig. 13 .

 13 Fig. 13. Zooming picture of the complex 3-D structure assembled.

  [E.F.] indicates the presence of important electrostatic effects between the gripper and the micro-object f [C.F.] indicates the presence of important capillary forces preventing the release of the micro-object times (fifty cycles) in order to estimate the relevance of concepts. Initial and final positions and orientations of the micropart change from cycle to cycle in order to take into account the maximum of possible cases. Let the success rate be:

			TABLE II
	RESULTS CHOSEN TO REPRESENT DIFFERENT SCENARIOS ENCOUNTERED
			DURING THE EXPERIMENTS.
	N •	task	init. pos.		prec.	note	result
		aligning (θ)	14 •		0.09 •		success
		centering (x, y) 1029 µm		0.43 µm		success
	1	closing (e 1 ) ascent	163 µm		1.72 µm a		success success
		transfer					success
		release					success
		aligning (θ)	32 •		0.61 •		success
		centering (x, y) 1015 µm		4.91 µm		success
	2	closing (e 1 )	163 µm		1.77 µm Ov. b	success
		ascent					success
		transfer					success
		release					success
		aligning (θ)	21 •		0.27 •		success
		centering (x, y) 1321.5 µm 0.77 µm Oc. c	success
	3	closing (e 1 )	163 µm		1.44 µm		success
		ascent					success
		transfer					success
		release					success
		aligning (θ)	7.53 •		0.68 •		success
		centering (x, y) 992.5 µm	6.16 µm		failure
	4	closing (e 1 )	× d		×		failure
		ascent	×		×		failure
		transfer	×		×		failure
		release	×		×		failure
		aligning (θ)	33.8 •		×	Oc.	failure
		centering (x, y) 1.75 µm		×		failure
	5	closing (e 1 )	163 µm		×		failure
		ascent	×		×		failure
		transfer	×		×		failure
		release	×		×		failure
		aligning (θ)	13 •		0.24 •		success
		centering (x, y) 560.7 µm	0.86 µm		success
	6	closing (e 1 )	163 µm		×	E.F. e	failure
		ascent	×		×		failure
		transfer	×		×		failure
		release	×		×		failure
		aligning (θ)	15.5 •		0.52 •		success
		centering (x, y) 348.2 µm	0.64 µm		success
	7	closing (e 1 )	163 µm		1.11 µm		success
		ascent					success
		transfer					success
		release	×		×	C.F. f	failure
		success rate =	succeed cycles total cycles

a [ ] represents the success of the task b [Ov.] indicates the presence of an overshoot in the control c [Oc.] represents the case when the micro-object passed under the gripper d [×] represents the failure of the task e

This work is partially conducted with financial support from the project "Hybrid Ultra Precision Manufacturing Process Based on Positional and Self assembly for Complex Micro-Products (HYDROMEL NMP2-CT-2006-026622)" funded by the European Commission.

Manuscript received .