Mohamed Kharboutly

Michaël Gauthier

Nicolas Chaillet

Modeling and control of non-contact micromanipulations based on dielectrophoresis

Micro and nano-particles can be trapped by a non uniform electric field through the effect of the dielectrophoretic force. Dielectrophoresis (DEP) is used to separate, manipulate and sense micro particles in several domains, such as in biological or Carbon Nano-Tubes (CNTs) manipulations. This paper tackles the creation of a closed loop strategy in order to control, using DEP, the trajectory of micro objects using vision feedback. A modeling of the dielectrophoresis force is presented to illustrate the non linearity of the system and the high dynamics of the object under dielectrophoresis . A control strategy based on the generalized predictive control method is proposed with the aim of controlling the trajectory, taking advantage of the high dynamics despite the non linearity. Simulated results are shown to evaluate our control strategy.

I. INTRODUCTION

Manufactured products become always smaller and integrate more and more functionalities in small volumes. Several applications fields are concerned such as bioengineering, telecommunications or in a more general way Micro-Electro-Mechanical-Systems (MEMS). The assembly of these microproducts is a great challenge because of the microscopic sizes of the components. In fact, the major difficulties of micro-assembly come from the particularity of the micro-object's behaviours which are more function of the surface forces than the volumic forces [START_REF] Lambert | Capillary Forces in Micro-assembly[END_REF], [START_REF] Gauthier | Forces analysis for micromanipulations in dry and liquid media[END_REF], [START_REF] Zhou | Ambient environment effects in micro/nano handling[END_REF]. The manipulation of a micro-object requires its handling, positioning, and release without disturbances of the surface forces such as electrostatic forces, van der Waals forces or capillary forces. The release is the more critical phase which is usually perturbed by adhesion phenomenon.

Several methods have been proposed in the last ten years to improve micromanipulations [START_REF] Sariola | Hybrid microhandling: a unified view of robotic handling and self-assembly[END_REF], [START_REF] Lambert | A case study of surface tension gripping: the watch bearing[END_REF]. The first approach deals with contact manipulation where the adhesion should be reduced or could be directly used for manipulation [START_REF] Hériban | Robotic micro-assembly of microparts using a piezogripper[END_REF], [START_REF] Lambert | Surface and contact forces models within the framework of microassembly[END_REF], [START_REF] Driesen | Micromanipulation by adhesion with two collaborating mobile micro robots[END_REF]. The release is the more critical phase which requires innovative methods to control and guarantee it despite adhesion. Dielectrophoresis force, which is the force applied on a polarizable particle in a non uniform electric field, has been recently used to induce repulsive force on micro-objects in order to release them [START_REF] Gauthier | Submerged robotic micromanipulation and dielectrophoretic micro-object release[END_REF]. The second approach consists in using non-contact manipulations like laser trapping [START_REF] Dholakia | Tutorial reviewoptical micromanipulation[END_REF] and non-contact dielectrophoresis [START_REF] Hunt | Dielectrophoresis tweezers for single cell manipulation[END_REF]. These principles are not disturbed by adhesion but the blocking force remains low.

In this paper, modeling and closed loop strategy of DEP systems using vision feedback are proposed. By simulating the 3D behavior of micro particles under DEP force, in function of the electric potential applied on the electrodes and using the vision capture, the system is ready to include the feedback block. The problem which will be faced is the large difference between the high dynamics of the system (respond time ≃ 1ms) and the low speed rate of the vision capture (≃ 1 image per 10 ms). We are a predictive control strategy based on the feedback of the vision sensor and a model of the DEP force.

II. MODEL PRESENTATION

A. Dynamic Model

The general expression of the dielectrophoretic force, created by a non uniform electric field, applied to a micro bead submerged in a liquid medium is [START_REF] Chang | Multiple electrodes arrayeed dielectrophoretic chip with application on micro-bead manipulation[END_REF], [START_REF] Gascoyne | Dielectrophoresis-based sample handling in general-purpose programmable diagnostic instruments[END_REF] is:

---→

F DEP = 2πǫ 0 ǫ p r 3 Re[K(ω)] --→ ∇E 2 . (1)
K(ω) is the Clausius -Mossotti factor:

K(ω) = ǫ * p -ǫ * m ǫ * p + 2ǫ * m , (2)
and

ǫ * = ǫ + σ jω , (3)
where ǫ are the permittivities, σ are the conductivities, index 0 refers to the vacuum, index m refers to the medium and index p refers to the micro bead, r is the radius of the micro bead, ω is the angular frequency of the applied electric field, -→ ∇ is the gradient operator and E is the root mean square magnitude of the sinusoidal electric field.

The electric field E is created by applying an electric voltages on pattern of electrodes as described in Fig. 1.

The dynamic model of the micro bead is defined by the Newton second's law. The force applied to the micro bead are the dielectrophoresis force, the Stokes drag force ---→ F drag and its own weight -→ P (see Fig. 1). If we consider that the position X(x, y, z) of the micro bead is defined by its center's coordinates, thus the -→ Ẋ is the velocity of the particle and the ---→ F drag verifies: where µ is the dynamic viscosity of the liquid medium. Using Newton's second law the particle's motion is defined by: ---→

---→ F drag = -6πµr -→ V = -k µ -→ Ẋ , (4)
F DEP + -→ P -k µ -→ Ẋ = M -→ Ẍ ( 5
)
where M is the mass of the micro bead and -→ Ẍ is the acceleration vector. We have shown in [START_REF] Kharboutly | Modeling the trajectory of a micro particle in a dielectrophoresis device[END_REF] that, in this situation, the inertial term M -→ Ẍ is a negligible volumic effect in the micro-world : the respond time corresponding to the acceleration term is negligible compared to the respond time corresponding to the fluid dynamic term. Thus, the particle's motion equation can be reduced as follows:

-→ Ẋ = ( ---→ F DEP + -→ P ) k µ (6)
A voltage vector U = [U 1 , U 2 , U 3 ] applied on the electrodes creates the non uniform electric field -→ E which creates the dielectrophoresis force used to manipulate the micro particle. Equation ( 6) manages the dynamical behavior of the micro particle under dielectrophoresis force. More information on this model can be found in [START_REF] Kharboutly | Modeling the trajectory of a micro particle in a dielectrophoresis device[END_REF].

B. Study of the micro bead behavior

In order to present our control strategy, we are focusing on the electrode's geometry described in Fig. 1 submerged in ultra pure water. We assume here that the micro bead only moves along the x axis, thus the position X of the micro bead is defined by (x, y = 0, z = r). Projecting (6) along the x axis, the velocity of the micro bead is ruled by:

ẋ = F DEP (x, U ) k µ (7)
In order to maintain the micro bead's center along the x axis, and taking into consideration the electrodes symmetry, the control input vector, which is the applied voltage vector U , proposed here is:

U = [U ref -δu, 0V, U ref + δu]. ( 8
)
where U ref is a fixed voltage, in this study it is equal to 75V , and δu is the single control variable. The electric field and the applied voltage on the electrodes are linearly related, due to the electrostatic superposition principle and the proportional relation between the electric potential and the charge density:

E = a(x)(U ref -δu) + b(x)(U ref + δu). (9)
This relation allows to replace the electric field E in (1) by a linear combination of the applied voltages. Thus, from [START_REF] Lambert | Surface and contact forces models within the framework of microassembly[END_REF] the velocity ẋ can be written as a second degree equation, coming from the electric field's square in the dielectrophoresis equation ( 1), with the respect to the control variable δu:

ẋ = f 1 (δu) = α(x)δu 2 + β(x)δu + γ(x) (10)
where α(x), β(x) and γ(x) characterize the dynamic model. They are function of the state variable x. The first problem to control this system is its non linearity which is shown in the equation [START_REF] Dholakia | Tutorial reviewoptical micromanipulation[END_REF]. The first non linearity of the system with respect to the control variable δu is due to the square term δu 2 . The second non linearity comes from the non linearity of the functions α(x), β(x) and γ(x). These functions characterize the system and they are identified using the hybrid simulation method, described in [START_REF] Kharboutly | Modeling the trajectory of a micro particle in a dielectrophoresis device[END_REF], which combines preprocessing FEM software simulated data and analytic equations. Fig. 2 shows the non linearity of these functions. In this figure, we clearly see that the functions α(x), β(x) and γ(x) are not linear with respect to the state variable x. This non linearity increases as the distance between the micro bead and the electrode's edge decreases. Fig. 2. The non linearity of the three functions α(x), β(x) and γ(x)

(U ref = 75V ) especially when x ≥ 50µm, respectively expressed in ms -1 V -2 , ms -1 V -1 and ms -1 .
Moreover, the micro bead reaches high speed motion when applying high voltages. Fig. 3 shows the step response for a micro bead starting from the initial position x 0 = 0µm and applying a voltage of δu = 70V , 60V , 50V and 40V . If we compare the time constant of the micro bead's response, which is close to 3ms, to a relatively high speed camera of 400 ips (images per second) we can note that during this time only two positions can be measured.

III. CONTROL STRATEGY

In order to control the micro bead's trajectory along a reference trajectory w in a dielectrophoresis-based device using vision feedback, two main difficulties occur. The first problem is the non linearity of the system with respect to the control variable δu as the equation [START_REF] Dholakia | Tutorial reviewoptical micromanipulation[END_REF] shows and the non linearity in relation to the state variable x due to the non linearity of functions α(x), β(x) and as it is shown in Fig. 2. Moreover, the other problem is the high dynamics of the system which induces high speed motion of the micro bead compared to the camera speed rate, which is one of the most conventional way to measure the micro bead's position. Both non linearity and high dynamics led us to develop an appropriate control strategy (Fig. 4).

Control Strategy

A. Linear model

To resolve the non linearity problem, starting by the non linearity relative to the control variable δu, the first step consists of transforming this non linear system to another linear system relatively to a new control variable named ξ. Using the following variable transformation:

ξ = f 2 (δu) = δu + β(x) 2α(x) 2 , (11)
we are able to create a linear relation between the new control variable ξ and the velocity of the micro bead ẋ. The new linear dynamic equation is:

ẋ = α(x)ξ + ρ(x), (12)
where

ρ(x) = γ(x) - β 2 (x) 4α(x) . ( 13
)
Equation ( 12) solves the non linearity problem in relation to the new control variable ξ.

Concerning the non linearity in relation to the state variable, produced by the non linear functions α(x), β(x) and γ(x) (see Fig. 2), these functions can be estimated by using an estimated value of the state variable x. This estimated value is equal to the current position when it is available, and it is equal to the reference value w date when the state variable x is not available. This last case is based on the hypothesis that the reference trajectory is known at any time and the controlled position is relatively close to the desired position.

B. Generalized Predictive Control (GPC)

In order to control the high dynamics of the micro bead, a control strategy ables to apply a series of control variables while no position's informations are available between two successive camera acquisition is presented. One of the control strategy which fulfill these requests is the GPC. The goal of the generalized predictive control is to find the optimal future control actions that drive the future process output to track the reference trajectory as closely as possible in the presence of system constraints and disturbances [START_REF] Kansha | Adaptive generalized predictive control based on jitl technique[END_REF]. The generalized predictive control is used in several domains of applications such as solar power plants [START_REF] Gálvez-Carrillo | Nonlinear predictive control with dead-time compensator: Application to a solar power plant[END_REF], turbine engines [START_REF] Mu | Advanced controller design for aircraft gas turbine engines[END_REF] and robotic manipulators [START_REF] Temurtas | Application of neural generalized predictive control to robotic manipulators with a cubic trajectory and random disturbances[END_REF]. The main idea of the GPC is to find a future control sequence from a given time which minimizes the error between the predicted output and the reference.

Based on a numerical model, the GPC enables to calculate the optimal control sequence of N values ξ in the future which minimize the error between the output position and the reference w in N steps in the future.

The application of the GPC strategy on our system requires a discrete model. Considering that the camera acquisition period is T c which means the position's information is updated each T c seconds. During this period the controller calculates the appropriate control variable sequence of N values using the sample time T s in order to track the reference trajectory with N × T s ≥ T c .

The details of the control strategy is presented in [START_REF] Kharboutly | Predictive control of a micro bead's trajectory in a dielectrophoresis-based device[END_REF].

IV. RESULTS AND DISCUSSION

In order to test the proposed control strategy, the dielectrophoresis system described in Fig. 1 has been simulated, where the liquid medium is ultra pure water with ǫ m = 80ǫ 0 , σ m = 10 -16 Sm -1 and µ = 10 -3 kg(sm) -1 . The micro object is a silicium micro bead with radius r = 30µm, ǫ p = 8.4ǫ 0 and σ p = 10 -12 Sm -1 . The frequency 2πω of the applied voltage used to create the non uniform electric field is 10kHZ and U ref = 75V and the applied voltage on the electrodes is limited to U max = 150V . The sample time is chosen equal to 0.5ms and the camera has an acquisition sample time equal to 2.5ms. Thus, the minimum value of the prediction's horizon N is equal to 2.5/0.5 = 5 steps. In order to test the robustness of the control law, the model used in the GPC controller and the simulated model differs by adding errors of 20% on the electric permittivities of both medium and particle.

A. High dynamics

Firstly, the proposed control strategy has been tested on high dynamic reference trajectories. Considering a sinusoidal reference trajectory with period equal to 10 times the camera acquisition period, i.e. 25ms with a magnitude of 25µm around x = 0. In this range the model can be considered linear.

Fig. 5 shows the output position of the the micro bead's calculated by the real system using the control variable δu obtained from the control variable calculated by proposed GPC applied on the model. This control strategy is also compared to a regular PI corrector to demonstrate the efficiency of our strategy. The proportional constant of this PI corrector is equal to the inverse of the gain of the system considered as a first order linear system in this range. The gain of the system is calculated and it is equal to 1.610 -6 mV -1 . The integrator constant of the PI corrector is equal to the time constant of the system which is equal to 3.610 -3 s. Output trajectory of the system controlled by the generalized predictive control and compared to the PI control. The camera acquisition period is 2.5ms .

B. Non linearity

Secondly, we test the proposed control strategy in the non linear range, by tracking a trajectory which reaches position near the electrode's edges. In this case the sinusoidal reference trajectory changes in magnitude and period. Fig. 6 shows the output trajectory of the real system controlled by the proposed GPC strategy based on the model where the amplitude of the reference trajectory is 130µm and its period is 100ms.

In this example, the micro bead goes toward the electrodes. At the time t = 0.01s, the micro bead's position is near to x = 100µm, the control did not find any value of the control variable ξ which nullify the error between the calculated and the reference position. The controller determines the optimum value which maximizes the velocity of the beads.

V. CONCLUSIONS

We have proposed a model and a closed loop control strategy based on the generalized predictive control of a dielectrophoretic-based device. The behavior of a micro bead, driven by dielectrophoresis force, is characterized by its high dynamics compared to the capture speed rate and the non linearity of its dynamic equation in relation to both the voltage variable and the position. The control strategy proposed provides the optimal sequence of voltage values with a smaller sampling rate then the camera speed rate. It enables to minimize the error between the micro bead's position and the reference even when the micro bead is near the electrodes where the non linearity is strong. The proposed control strategy is tested and compared to other regular control strategy such as the PI controller and several results are presented.

Fig. 1 .

 1 Fig. 1. DEP-based device used in this study

Fig. 3 .

 3 Fig. 3. Step response for a micro bead starting form x 0 = 0µm, δu = 40V, 50V, 60V and 70V and U ref = 75V

Fig. 4 .

 4 Fig. 4. Summary of the control strategy

  Fig. 5.Output trajectory of the system controlled by the generalized predictive control and compared to the PI control. The camera acquisition period is 2.5ms

Fig. 6 .

 6 Fig.[START_REF] Hériban | Robotic micro-assembly of microparts using a piezogripper[END_REF]. Output trajectory of the Generalized predictive control tracking a long range reference trajectory using camera with acquisition period equal to 2.5ms.


Philippe Weinzaepfel

Hervé Jégou

Patrick Pérez Technicolor

Reconstructing an image from its local descriptors

. Top: the original picture. Bottom: the image reconstructed by our approach, which uses as only input the output of a standard local description software (position and shape of a number of "regions of interest" and for each of them a SIFT descriptor or the like).

Introduction

Image indexing and retrieval have received a considerable attention in the last few years, thanks to the generalization of digital personal devices. Existing systems now search in millions [START_REF] Quack | Cortina: a system for large-scale, content-based web image retrieval[END_REF][START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF] to hundred millions [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] of images on a single machine.

The most successful frameworks rely on local descriptors, such as the popular scale invariant feature transform (SIFT) [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], attached to a number of "interest" regions extracted beforehand. For large scale image search, efficiency requires that geometry information (position and shape of interest regions) is first ignored and local appearance descriptors are aggregated, e.g., within a bag of visual words [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. However, the precision of search based on such global representations is often improved subsequently by getting back to the geometry information in a post-verification step that filters out wrong matches [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF].

One key application of such systems is near-duplicate detection [START_REF] Chum | Near duplicate image detection: min-hash and tf-idf weighting[END_REF][START_REF] Wu | Bundling features for large scale partial-duplicate web image search[END_REF], which is used in particular for detection of illegal copies. It is worth noting that the best performing approaches (e.g., [START_REF] Douze | An image-based approach to video copy detection with spatio-temporal postfiltering[END_REF]) in the copy detection task of TRECVID [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF] rely on local descriptors and use a postverification scheme. Recently, following a trend in watermarking system design, researchers realized that copy detection is a non-collaborative game: a pirate can lure the system by altering an image in a proper manner [START_REF] Kijak | Challenging the security of cbir systems[END_REF].

In this paper, we address another security aspect raised by image indexing: the privacy of images. When a copyright holder resorts to a third party content based image retrieval system, it would rather pass images' fingerprints to this third party than share its sensitive contents. This image information that allows efficient and accurate indexing and comparison of contents is typically composed of local appearance descriptors and additional meta-data, including geometrical information to allow post-verification, associated to detected regions of interest.

Nevertheless, a privacy threat remains: since the descriptors extracted from an image provide a "summary" of its visual properties over its most informative fragments, it might be possible to use them to interpret the image content or, even, to create a pirated copy. Such reconstructions were evidenced for features like filters, where they were used [START_REF] Jones | A computational framework for determining stereo correspondence from a set of linear spatial filters[END_REF][START_REF] Torralba | Depth estimation from image structure[END_REF] to visually represent the information conveyed by the features.

In this paper, we show that this is also the case for stateof-the-art descriptors. We present and demonstrate an algorithm for reconstructing an image from its local descriptors, here based on SIFT, and associated geometric information. Similar to [START_REF] Hayes | Scene completion using millions of photographs[END_REF] and [START_REF] Whyte | Get out of my picture! internet-based inpainting[END_REF], we use an external image database to help the reconstruction. However, in contrast to these approaches that are geared towards image editing and image generation, we are not interested in completing or inpainting images in a convincing way. Our main objective is to show how a simple technique could permit an "image hacker" to interpret the content of the original image, and this even if there is no similar image in his external database.

Our technique progressively builds an approximation of the unknown image by reconstructing its regions of interest one by one. First, for each region the nearest descriptor is searched in the external database and the corresponding image patch is extracted and reshaped according to geometric information attached to the region. This patch is subsequently pasted, after receiving a correction that makes it blend seamlessly in current reconstruction of the image. After all regions of interest have thus been approximately recovered and glued together, some image portions might still be missing. The absence of detected interest regions indicates that these portions should be fairly deprived of texture and structure. They are reasonably reconstructed by smooth interpolation from reconstructed boundary conditions. Not surprisingly, the resulting image is not perfect (see Figure 1 for a first illustration, and other examples presented in experimental section). However, it is visually close enough to the original unknown image to interpret its content. This makes explicit the privacy threat that lies in local image descriptions. Copyright holders, in particular, should thus be aware of the surprising amount of visual information given away when passing such descriptions to third party indexing and search systems.

The paper is organized as follows. Section 2 states more precisely the reconstruction problem that we address, with discussion of related works. The actual reconstruction algorithm is presented in Section 3. Experiments reported in Section 4 demonstrate the strengths of the algorithm as well as some of its limitations, which are discussed.

Problem statement

In this section, we first introduce the image information provided by a typical local description software. We then proceed with defining and analyzing the image reconstruction problem we want to solve based on such an information. Finally, we briefly discuss the relationship between this problem with other image manipulation tasks that aim at building images out of fragments.

Image description

A local description scheme, as depicted by Figure 2, is assumed in the rest of the paper. More precisely, an image with support Ω is described by a set of "interest regions" extracted by a detector. Each region is mapped to an intensity patch (a disc in our case, with regions being elliptically shaped1 ), whose appearance is summarized by a ddimensional descriptor v i ∈ R d . The number of regions of interest depends on the image size and content.

As the output of the local description program, we typically have the following information for i-th interest region:

• appearance descriptor v i ; • coordinates x i = (x i , y i ) ∈ Ω of region center;
• scale s i and dominant gradient orientation o i ; • symmetric definite matrix A i that defines the elliptic support of the region.

Geometric information (x i , o i , A i ) uniquely defines the affinity W i that maps elliptic image fragment to a centered normalized circular patch with dominant orientation 0. All or part of above quantities are needed by the indexing system, in particular geometrical information is used during the geometrical verification stage, as done in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. In the following, we denote R i = {v i , x i , s i , o i , A i } this set of quantities associated with an interest region. Abusing the terminology, we refer to it as the "descriptor" of this region.

In this paper, we focus on SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], though our method should work for most local descriptors. SIFT descriptors are invariant to image orientation and scale, and are robust to affine and perspective distortions. They come in the form of normalized positive 128-dimensional vectors (d=128). As for region detector, we use an Hessian-affine technique [START_REF] Mikolajczyk | scale and affine invariant interest point detectors[END_REF]. Both detection and description are provided by Mikolajczyk's software, which is used in many works on image indexing, e.g., in [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Jégou | Improving bag-offeatures for large scale image search[END_REF]. Given its output on an image, we aim at reconstructing this image approximately.

The reconstruction challenge

Reconstructing a single image patch from its local descriptor is impossible because local description drastically

→ → → R i = {v i , x i , s i , o i , A i } Figure 2
. Image analysis stage, as done by a typical local description software. Regions of interest are first detected and affine-normalized to a fixed-size square patch, which is subsequently described by a local descriptors and additional meta-data used in geometrical verification. Note that in our reconstruction approach (see Section 3), we will reconstruct elliptic patches out of normalized circular patches.

compacts appearance information for both invariance and robustness purposes. It typically captures some aspects of local contrast distribution. As a consequence the description function is a many-to-one mapping whose inversion is ill-posed, unless appropriate additional priors or constraints are used. An exemplar-based prior will be obtained in our approach, thanks to an external image database. From these images, possibly very different from the unknown image of interest, a large number of image patches and associated descriptors will be extracted to allow approximate and simple inversion of local description function.

In the case of SIFTs, only weighted histograms of intensity gradient orientations computed over a partition of the normalized image patch are accounted for. Hence, the following difficulties have to be overcome when using the regions of interest that have been approximately recovered from this type of descriptors:

• There is no chrominance information.

• Since the descriptors are normalized according to the Euclidean norm, the absolute contrast of a given interest region is not known.

Also, the image is unevenly described, see Figure 3. Indeed, interest region detectors aim at selecting informative image fragments, typically those with specific contrast patterns. Texture and structure free regions of the image are thus devoid of interest regions and do not get described at all. These regions are usually very smooth in intensity, uniform sky portions for instance. Conversely, structure and/or texture regions trigger lots of overlapping region detections. Some pixels in such regions can get covered by more than one hundred interest regions spanning a large range of scales, shapes and positions.

Link to image editing

Our image reconstruction problem bears connection with a number of image editing tasks where an image is built out of multiple images or image fragments, sometimes with some amount of interactivity: image composing and cloning where image cutouts are pasted in a new background; image completion and inpainting for restoration, correction or editing; stitching of multiple views from a scene to create panoramas for instance; automatic collage of multiple photos; "image analogy" (example-based image generation from auxiliary information such as low-res images for super-resolution or semantic segmentation for texture-by-number).

As we shall see, our reconstruction algorithm resorts to basic tools (harmonic correction or interpolation) that have extensively used within aforementioned image editing tasks. Addressing a completely different problem though, our work drastically departs from these research trends in several ways:

• Whereas in image editing problems information mostly remains attached to pixel grid (either in the color domain or in the gradient domain), the input data is, in our case, of a very different nature (compacted descriptor domain with spatial information partly lost), which makes the task especially challenging as explained earlier. In particular, as opposed to image completion and image inpainting contexts, we do not have initial image data to start with.

• Image stitching and exemplar-based image generation techniques, whether for inpainting, image analogy or photo-collage, rely on collections of images or of image fragments that are quite homogeneous: in patchbased inpainting, all patches come from the image itself and they are not normalized to a fixed size irrespective of their original size; in image completion from large photo collections and in photo collages, large fragments of real photos are used, which helps preserving both visual and semantic quality of final composite; in image analogy, example patches with auxiliary information have to be very consistent with the input to be processed; panorama stitching concerns only few images of very similar content. In our case, there is a very large number of fragments (several thousands), which drastically differ in size, detail level and color, to be assembled.

• The amount of overlap between fragments can be extremely large at some places in our case, with nested inclusions; in contrast, in all exemplar-based image generation or completion techniques, fragments only overlap over thin borders such that most pixels of final image belong to only one source fragment, others rarely belonging to more than two.

• If final evaluation remains subjective for both our work and mentioned tools, we are not aiming at excellent visual quality of assembled image, simply at semantic recovery of most visual content.

Reconstruction algorithm 3.1. Overview

As explained in Section 2, we consider an external database of color images I k , k=1 • • • M , from which a set of interest regions are extracted off-line and described as R j = {v j , x j , s j , o j , A j }, j=1 • • • m. We shall denote S j the pixel support of j-th region (ellipse centered at x j and with shape defined by A j ) and k(j) the index of the database image it stems from.

These regions and associated image patches will be used as a prior to invert local description function. Given a set of query descriptors

R i = {v i , x i , s i , o i , A i }, i = 1 • • • n,
extracted in the same way from an unknown color image I with support Ω, we aim at reconstructing this image approximately. The reconstruction proceeds as follows: 1. For each query appearance descriptor v i , search its nearest neighbor in the descriptor database

j * = arg max j∈{1•••m} v i -v j 2 , (1)
and recover the corresponding elliptic image patch

q * j = I k(j * ) (S j * ). (2)
Warp this patch such that it fits into the destination ellipse S i ⊂ Ω:

p i = W -1 i • W j * (q j * ). (3)
2. Seamlessly stitch all patches p i , i = 1 • • • n, together to obtain a partial reconstruction with support S = ∪ n i=1 S i ⊂ Ω (see details below) .

3. Complete remaining empty zone S = Ω \ S by smooth interpolation, as shown in Figure 4 (see details below).

Seamless stitching of patches

Recovered image patches are numerous, they span a large range of sizes and shapes and they overlap a lot. This makes their joint stitching difficult. We take instead a "dead leaves" approach by stacking patches one after another, newly added patch partly occluding the current reconstruction if it overlaps it. Since large patches are more likely to exhibit visual artifacts due to extreme stretching of original source patch, we want to favor the contribution of smaller patches. The order of sequential stitching is thus chosen according to decreasing support's sizes.

Such a simple stacking is not sufficient though to get a satisfactory reconstruction. Indeed, since patches originate from a large number of unrelated images, they usually exhibit very different appearances (chrominance, intensity and texture). This results in a disruptive patchwork effect as illustrated in Figure 5. If removing texture and structure discontinuities is difficult, this is not the case for color and intensity discontinuities. Such seams are easily concealed by Poisson image editing [START_REF] Pérez | Poisson image editing[END_REF], as routinely done for cloning, composing and stitching.

Consider the stage of sequential stitching where i-th image patch p i with support S i has to be incorporated. Denote {I(x), x ∈ T } the image reconstructed up to that point with T the union of supports of patches used so far. If S i ∩ T = ∅, the new patch is simply copied in place: I(x) = p i (x), ∀x ∈ S i . If S i overlaps T , the imported patch is modified by an additive harmonic (null Laplacian) correction such that it fits exactly current image I at the border of the overlapping regions. More precisely, let's denote ∂S i = {x ∈ S i ∩ T : N (x) ∩ (T \ S i ) = ∅}, the intersection of the inner border of S i (according to 4-nearest neighborhood N (.)) with T . Color values over ∂S i stay as in current reconstruction, whereas new values are computed over Si = S i \ ∂S i such that:

∀x ∈ Si , |N (x) ∩ S i |I(x) - y∈N (x)∩ Si I(y) = y∈N (x)∩∂Si I(y) + y∈N (x)∩Si [p i (x) -p i (y)]. (4)
These three discrete Poisson equations (one per channel) on domain Si with Dirichlet boundary conditions have unique solutions that are obtained efficiently with either direct or iterative sparse solvers. Note that for better results, we work in CIE-Lab color space that separates image intensity from chrominance while exhibiting good perceptual regularity. Clamping is performed if resulting values are not in the admissible range.

Final completion by interpolation

When all patches recovered from descriptors have been stitched together, the image reconstruction is complete over

S = ∪ n i=1 S i ⊂ Ω.
Fragments that are still missing are likely to exhibit only little texture and structure in the original image. Hence, they are simply approximated by harmonic interpolation of known reconstruction over ∂S. Mathematically it is the same problem as before but without imported patch information:

∀x ∈ S, |N (x)|I(x) - y∈N (x)∩ S I(y) = y∈N (x)∩∂S I(y). (5)
This system is solved as previous ones. Note however that, if S has more than one connected component, the system can be split into several independent subproblems, one per component, for sake of efficiency.

Experiments

In this section, after introducing the datasets used in our experiments, we present the reconstruction results for several images and underline the remaining weaknesses of the reconstruction. We then analyze the impact of the external database size on the final reconstruction.

Datasets

The experiments are carried out using two image datasets introduced for the evaluation of indexing systems: the IN-RIA Holidays [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] and Copydays [START_REF] Douze | Evaluation of GIST descriptors for web-scale image search[END_REF] datasets. Both are composed of holiday snapshots. The first one contains 1491 images grouped in 500 distinct sets, each of which is associated with the same scene or object. Different types of photos are included: natural images, man-made, crowd, etc. The entire dataset is described by 6 756 563 SIFT descriptors. The Copydays dataset is composed of 157 independent photos and several (artificially) transformed versions of these images, which were used as queries in [START_REF] Douze | Evaluation of GIST descriptors for web-scale image search[END_REF]. We do not use these synthetic transformed images in our paper.

Our goal is to measure to what extent the interpretation of the reconstructed image content is possible. Therefore, the performance of the algorithm is judged in a subjective manner, based on the quality of the reconstruction with respect to a possible interpretation by human. We there-fore present reconstruction results, and underline failure and pathological cases. Two scenarios are considered: Scenario I: The images of Copydays are reconstructed using Holidays. As there is no intersection (no common object or scene) between the two datasets, this scenario corresponds to the case where the image to be reconstructed has no corresponding image in the external database used to support the reconstruction. A few images of monuments downloaded from the web are also considered.

Scenario II: The queries of Holidays are reconstructed using the Holidays dataset. Each query is removed in a leave-one-out manner. This scenario reflects the case where the image to reconstruct is similar to some images of the external dataset, which is likely to happen on common objects, logos, or famous places if we use a large external set. There is at least one image similar to the image to reconstruct in the dataset.

Reconstruction results

Hereafter, we analyze the impact of the evaluation scenario and of the external database size on the reconstruction. We also underline some limitations of the algorithm, most of which are inherent to the description used as input. Scenario I vs Scenario II. Reconstruction results for various types of scenes are presented in Figure 6 and Figure 7, for Scenario I and II, respectively. In both cases, the humans (the man on the bike in Figure 6, and the Asian women in Figure 7) are not very well reconstructed, and require an interpretation effort to distinguish the person. However, it is still possible to recognize the person if the face is large enough, see the dictator in Figure 10. Natural (trees, leaves) and man-made objects can be recognized to some extent: the cars can be localized in the left-most image of Figure 6. However it is not possible to recognize their brands. Overall, the buildings and text look better than vegetation or human beings. Famous monuments are easily recognized from the reconstructed images, see Figure 8.

Comparing the results from Scenario I (Figure 6) to those of Scenario II (Figure 7), the reconstruction is slightly improved if similar images are contained in the database. Note that if the image to reconstruct is in the external database, then the reconstructed image is almost perfect (except for the uncovered areas, which are interpolated): only interpolation artifacts are observed.

Limitations: Although our method reconstructs an interpretable image, the reconstruction is imperfect. Hereafter we focus on the main artifacts and why they appear.

Color. The fact that color is poorly reproduced is not surprising because SIFT descriptors do not contain any color or absolute photometric information. In some cases, as for vegetation, texture and color are related and the dominant color remains satisfactory. However, this is not the case in general. Looking at Figure 10, it appears that a black and white image is reconstructed with colors, and the dominant color varies from one reconstruction to another. This is because the algorithm is sensitive to the selection of the first patches (which are different in Figure 10 because the database is not the same), which have a significant impact on the dominant color. In our opinion, the best way to handle color would be to insert the user in the loop by using a weakly supervised reconstruction, or by using a dedicated colorization technique, as the one proposed in [START_REF] Levin | Colorization using optimization[END_REF].

The richness of the image description has a strong impact on the reconstruction quality. Images described by few descriptors (less than 100) are poorly reconstructed in general, as shown by Figure 9, where the original image is described by a limited number of salient regions. Moreover, most of the image pixels are not covered at all. In that case, interpolation over large areas with few boundary conditions fails to invent the missing area, for instance the clouds in the sky. Even if the uncovered regions contain a limited amount of visual information, the overall rendering severely impacts the interpretation of the image.

Finally, pixelization occurs when large regions are reconstructed from small ones. The absolute photometric intensity is often quite different from the original image, and spurious edges and lines appear.

Impact of the size of the database. Intuitively, the larger the external database, the better the reconstruction: in that case more tuples (descriptors,patches) are available and the probability to find a better patch is higher. This is confirmed by Figure 10, where two images are reconstructed using an external database of increasing size. As the database grows, the artifacts tend to disappear and the details are reproduced with higher fidelity.

Conclusion

This paper, by showing that an image can be reconstructed from its local descriptors in a way that allows interpretation of its content by human, raises the problem of privacy of image description by state-of-the-art local descriptors. To our knowledge, this issue is ignored in existing indexing systems, despite the value of the indexed content. The proposed method is entirely automatic, which suggests that much better reconstruction could probably be obtained with user interaction, in particular to overcome the lack of color information. Doing so, it is still not clear, however, to which extent the images could be reconstructed with sufficient commercial value and become pirated copies. Content providers should take care of this issue.

Figure 3 .

 3 Figure 3. Number of (elliptical) regions of interest covering each pixel of the original image. Some pixels belong to many regions, but many locations are not or poorly described.

Figure 5 .

 5 Figure 5. Reconstruction without blending: the patches are here copied without being adapted, yielding poor reconstruction. See Figure 4 for the original image.

Figure 4 .

 4 Figure 4. From left to right: the original picture and the reconstruction before and after completion of uncovered regions.

Figure 8 .

 8 Figure 8. Reconstruction of famous buildings (Scenario I).

Figure 6 .

 6 Figure 6. Scenario I: Reconstructions of images from Copydays using the external dataset Holidays.

Figure 7 .

 7 Figure 7. Scenario II. Reconstructions of images from Holidays using Holidays deprived of query image as external dataset.

Figure 9 .

 9 Figure 9. An example of a picture with only 63 regions of interest: (left) original picture; (right) reconstruction before completion

Figure 10 .

 10 Figure 10. Left to Right: original image and its reconstruction based on an external image set of increasing size: 12, 52 and 1491 images.

Note that the descriptor v i is computed on a normalized square patch. However, to avoid corner artifacts, only the pixels of the inscribed disc are used at reconstruction time.

Acknowledgements

This work was partly realized as part of the Quaero Project, funded by OSEO, French State agency for innovation.