Eduardo Valle

David Picard
email: david.picard@lip6.fr

Matthieu Cord
email: matthieu.cord@lip6.fr

Geometric Consistency Checking for Local-Descriptor Based Document Retrieval

Keywords: H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval; I.4.8 [Image Processing and Computer Vision]: Scene analysis-motion, object recognition Algorithms, Design, Experimentation Image Retrieval, Local Descriptors, Geometric Consistency, Retrieval by Voting, CBIR

An efficient architecture, based on voting and local descriptors, has been proposed to retrieve multimedia documents. In this paper, we evaluate different geometric consistency schemes, which can be used in tandem with this architecture, and that, in many contexts, are essential to boost the retrieval performance. Our empirical results show however, that geometric consistency alone is unable to guarantee high-quality results in databases that contain too many non-discriminating descriptors.

INTRODUCTION

Many document retrieval applications are mainly based on "target identification", meaning that the user is not interested in retrieving a category of objects but in obtaining all information available about a specific target object. When dealing with visual documents (images, videos, 3D models, etc.) on this kind of context, there is a very effective architecture, based on a voting algorithm over local descriptors. This architecture was first described in [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF] and has been extensively used throughout the literature (e.g. [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Valle | Fast identification of visual documents using local descriptors[END_REF]).

To explain the architecture in a nutshell: we start by taking each visual document in the database and describing it using local descriptors. When the user performs a query, we also compute the local descriptor for the query document.

For each query descriptor, we look for the most similar descriptors in the database, and give a vote for the document to which it belongs. Then we count how many votes each document received and use this number as a criterion of similarity.

The method has several advantages. Compared to global descriptor techniques, it is robust because the descriptors are many: if some get too distorted or are completely lost, enough will remain to guarantee good results. Also, it is efficient, because pairwise image comparison is not necessary; we match the individual descriptors independently, and rely on the vote count to aggregate the results. This allows performing the search in sub-linear time.

On the other hand, the architecture is not without challenges. First and foremost, the multiplicity of descriptors penalizes the performance, since many descriptors must be matched in order to identify a single document. The whole scheme is feasible only if efficient indexing techniques are able to accelerate the similarity search used to match the descriptors. This problem has been extensively addressed in the literature, and today good indexing methods are available for multimedia descriptors [START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF][START_REF] Amsaleg | Content-based retrieval using local descriptors: Problems and issues from a database perspective[END_REF][START_REF] Valle | High-dimensional descriptor indexing for large multimedia databases[END_REF].

Another problem arises when matches are made incorrectly, giving votes for the wrong documents. If the number of query descriptors is large and the fraction of incorrect matches is small, then any incorrectly identified document will receive significantly less votes than the correct one. Otherwise, the reliability of the voting mechanism is compromised. If a significant fraction of matches is known to be incorrect, the reliability can be greatly improved by enforcing geometric consistency constraints. The idea is to scrutinize the list of images obtained by the vote counting algorithm and check, for each image, if the matches are compatible with the expected geometric transformation. The matches which do not follow the general trend are removed, the votes are recounted and the list is re-ranked.

In this paper, we evaluate the effectiveness of geometric consistency strategies in scenarios with an overwhelming fraction of incorrect matches, a situation which arises when either the query or the database images are of poor quality, or the deformation suffered by the query image is too strong.

APPLICATION: ITOWNS PROJECT

This study was motivated by the iTowns Project, which is defining a new generation of multimedia web tools that mixes a broadband 3D geographic image-based browser with an image-based search engine 1 . The first goal of this new type of search engine is to retrieve, in the high-resolution database, the scene corresponding to a given query image.

In a possible scenario, the users are looking for information about a restaurant in front of them (e.g., feedback from other patrons). They can take a picture of the restaurant with a cell-phone and, using the iTowns web server, obtain the desired information.

In order to accomplish this goal, there are basically three steps to perform:

1. Match the query document with the corresponding document in the database;

2. Find information associated with the database document and related to the query;

3. Retrieve only relevant information regarding the user interests. In this paper, we focus on the first step.

Since our problem involves target identification, we have decided to employ the efficient architecture based on voting over local-descriptors, which was described on the previous section. We have used SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] to describe the images, due to their robustness. In order to match the descriptors, we have used Multicurves, an indexing based on space-filling curves which is well adapted for very large databases [START_REF] Valle | High-dimensional descriptor indexing for large multimedia databases[END_REF].

Figure 1: Answering a user query -we want to retrieve the database document (right) corresponding to the user query (left: image taken with a cell phone). The retrieval is performed by matching the local descriptors (green lines). Though many matches may be found (left half ) few of them might be correct (right half ). Geometric con sistency helps to filter out the incorrect matches.

CONSISTENCY STRATEGIES

There are several different ways to perform the geometric consistency, but all of them fall on two general strategies: (1) estimate the geometric transformation by applying an (usually robust) estimator, and eliminating the matches incompatible with that transformation; (2) computing a statistical distribution of some geometrical transformation parameter (rotation, scale) of each match, and eliminating the matches which deviate too much from the mode of that distribution.

The first strategy is more precise, but also more complex to implement. In order to apply it, one has to choose the kind of transformation model whose parameters will be estimated (e.g., scale change, similarity transformation, affine 9 1 See http://itowns.ign.fr transformation, etc.) and the estimator used. Since many outliers are expected, the estimator has to be robust.

A usual combination is to use the RANSAC estimator [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] with a 2D affine transformation model. The RANSAC (RANdom Sample Consensus) is a Maximum Likelihood technique that is robust to the presence of a large fraction of outliers. It works by selecting (at random) a small set of samples and estimating the model parameters from them. The model so estimated is then used to count the inliers and the outliers. The process is iterated several times, selecting potentially different samples at each iteration. The model which generates the largest fraction of inliers is kept. The idea behind RANSAC is that, if it happens to select a sample exclusively composed of inliers, then there is a good chance that the estimated model will be compatible with all other inliers.

The 2D affine transformation model is a compromise between simplicity and comprehensiveness. It can model most, but not all, deformations suffered by the query. In particular, the viewpoint change, which is affine in the 3D spaces, generates a non-affine geometric transformation in the 2D plane. But the general 3D affine transformation is too complex, demanding a lot of samples to be reliably estimated, and thus it is ill adapted for RANSAC. Since viewpoint transformations can be locally modeled as 2D affine transformations, the model is able to match at least part of the image.

The second strategy, based on statistics, is less precise but much simpler. In our comparison we make the choices described in [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]. In order to apply it, we first choose which parameters of the transformation we will inspect -rotation and scale being the most common and then study the statistical behavior of that parameter. We inspect only the rotation (which is readily available as the difference between the principal direction of the query and target SIFT points), creating a histogram of the angles observed. We then consider as inliers only the matches corresponding to the highest peak (the mode) on that histogram.

EXPERIMENTS

We have compared the two consistency strategies (RANSAC and Rotation Histogram). To make the comparison more complete, we have also included the baseline method (using the brute vote count, without geometric consistency), and an alternative method using pairwise image comparison (as described in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]). The methods compared were thus:

• Voting algorithm with the RANSAC over 2D affine transform consistency criterion ("RANSAC").

• Voting algorithm with the Rotation Histogram consistency criterion ("Rotation Histogram").

• Pairwise comparison using a criterion of contrast in the distance between descriptors ("Pairwise Matching").

• Voting algorithm without geometric consistency ("Brute Vote").

We have tested the methods on two subsets of the iTowns database. The query sets of both tests contained images taken by a mobile phone in front of some of the shops on the street. The first dataset consisted of 82 images of a single street (about 350 000 descriptors). Since the images (both in the query set and in the database) were direct views of the buildings, the transformation between query and its corresponding target images was simple, and we have considered this test easy. The second dataset contained 300 images of a large boulevard (about 3.5 millions of descriptors). As the vehicle taking the pictures was in the middle of the street, the target regions on the images (a shop, for instance) were very small. Thus, few descriptor on each image were actually meaningful. Since the transformations were severe (scaling, viewpoint changes), we have considered this test difficult.

For both sets, we have manually built the ground truth by annotating which images corresponded to each query. We have used two criteria for the evaluation. The first consisted in measuring the rank of the first relevant image retrieved (averaged over the query set). The second measure was the evolution of the number of relevant image in the retrieved set, as the size of this set increased.

An example for a single query can be appreciated on Figure 2. The left image shows the retrieval attempt using the Brute Vote technique. Since the query image presents several distortions (occlusions, scale change, small viewpoint change) the retrieval is not perfect, but a relevant image is found in the 6th rank. Using the Rotation Histogram technique (middle image) the relevant image rank is improved to the 3rd position. Using the RANSAC technique (right image) three relevant images are found on the first three ranks -an improvement on both the rank of the first relevant image and the overall precision.

Results for the First Dataset

We have computed the mean best rank of relevant images for all four methods. The results are shown on Table 1. As we can see, the Pairwise Matching shows the worst results. The method by Brute Force has a much more reasonable time, but the quality is still not good. The Rotation Histogram scheme was able to cut the mean rank almost by half, but it was RANSAC who had the most impressive results. In our application context, the performances it obtained would be satisfactory from the user point of view.

Method

We also measured the evolution of the number of relevant images as the number of retrieved images increases on Figure 3. The RANSAC method outperforms the others for a small number of retrieved images, but then stops to progress at around 6 images. If the number of retrieved images is large, the Rotation Histogram technique is able to retrieve more relevant images than RANSAC. There are two reasons for the flat progression in RANSAC. First, it requires a minimum number of correct matches in order to evaluate the model. For the 2D affine transform, 7 matches are needed (though the strict minimum are 3 matches, this would lead to numerically unstable estimations). This means that if an image has less than 7 matches it is automatically discarded, since no model can be estimated. Second, if the number of outliers becomes too overwhelming, the probability of a reasonable model being estimated becomes too small and RANSAC fails.

Results for the Second Dataset

Like we have done for the first subset, we have compute the mean best rank of relevant images for all four methods, shown in Table 2 The results are unsatisfactory, especially when contrasted with the ones obtained on the (easier) dataset (Table 1). RANSAC still shows the best results, but its impact is now much subdued. For all methods, the first relevant image is so low on the ranking that probably it won't even show in the first page of results. From the point of view of the user, the results are highly inadequate. This low performance is confirmed on the graph of evolution of the number of relevant images (Figure 4). There is very little difference between the methods, and only as the number of retrieved images gets very large (over 30), RANSAC starts to show some advantage over the other methods.

DISCUSSION

Adding geometric consistency constraints seems to be essential to the success of document retrieval in our application context. Among the two strategies examined, RANSAC was the only able to provide satisfactory results. However, the technique seems to be highly dependent on the nature of the documents. In the case of a small database, with moderately distorted queries (like our first study) the results are good enough to be used in the intended application. In our second study (with more challenging conditions: larger database, problematic features, highly distorted queries) the quality of the results suffered.

It is probable that geometric consistency alone will not be enough to achieve high-quality results in contexts like ours, where a large number of non-discriminating descriptors are spawned by problematic image features like tree branches and complex shadows. Those descriptors, which match at random on the database, increase dramatically the number of false matches, inflating the rank of non relevant images (Figure 5). An important addition to architecture would be the ability to recognize and eliminate those noninformative descriptors. The fact that Pairwise Matching performed so badly was somewhat surprising, since it can benefit from a distance contrast criterion (explained in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]) aimed at automatically rejecting bad matches. The most probable explanation is that it does not benefit from the "dilution" of incorrect matches on the entire database (since those matches are made at random, they tend to get evenly distributed among all images).

To conclude, we consider extending the voting-based architecture to our application very challenging. Advances in the state of the art are needed both in terms of descriptors quality and matching accuracy. We intend to share our databases with the community in order to allow the benchmarking of those tasks on this difficult context.

Figure 3 :

 3 Figure 3: Evolution of the number of relevant images as the number of retrieved images grows.As we can see, the Pairwise Matching shows the worst results. The method by Brute Force has a much more reasonable time, but the quality is still not good. The Rotation

Figure 4 :

 4 Figure 4: Evolution of the number of relevant images as the number of retrieved images grows.The results are unsatisfactory, especially when contrasted with the ones obtained on the (easier) dataset (Table1). RANSAC still shows the best results, but its impact is now much subdued. For all methods, the first relevant image is so low on the ranking that probably it won't even show in the first page of results. From the point of view of the user, the results are highly inadequate.

Figure 2 :

 2 Figure 2: A sample query using the Brute Vote technique (left) and enhanced by geometric consistency by Rotation Histogram (middle) and RANSAC (right). The query image (red border) is followed by the ranked answers (right-left, top-down), some of which are relevant (green border).

Figure 5 :

 5 Figure 5: False matches between two images after geometric consistency check with RANSAC.

Table 1 :

 1 Mean best rank for the first dataset.

		mean best rank
	Image matching	27.09
	Brute vote	14
	RANSAC	1.09
	Rotation Histogram	7.91

Table 2 :

 2 . Mean best rank for the second dataset.

		Method					mean best rank
		Image matching				80.67
		Brute vote					98.80
		RANSAC					34.40
		Rotation Histogram			59.10
		1.6			Brute vote RANSAC
	Number of relevant images	0.4 0.6 0.8 1 1.2 1.4	Rotation Histogram Pairwise matching
		0.2
		0
			5	10	15	20	25	30	35	40	45	50
					Number of images retrieved


Anthony Martin

Olivier Alibart

Jean-Christoph Flesch

Joseph Samuel

Supurna Sinha

Sébastien Tanzilli

Anders Kastberg

J.-C Flesch

Non-local geometric phase in two-photon interferometry

Keywords: 03, 65, Vf -Phases: geometric; dynamic or topological 42, 50, -p -Quantum Optics 42, 50, Ar -Photon statistics and coherence theory 42, 25, Ja -Polarization

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction. -Quantum interference is one of the most delicate and intriguing aspects of quantum theory. A subtle interference effect, discovered surprisingly late, is due to the geometric phase [1,[START_REF] Shapere | Geometric Phases in Physics[END_REF]. It was soon realized [START_REF] Ramaseshan | [END_REF] that Berry's discovery had been anticipated by Pancharatnam's work on the interference of polarized light [START_REF] Pancharatnam | Proc. Indian Acad. Sci[END_REF]. Pancharatnam's work is now widely recognized as an early precursor and optical analog of the geometric phase [START_REF] Ramaseshan | [END_REF][START_REF] Samuel | [END_REF].

Studies of the geometric phase usually deal with amplitude interferometry, which describes the interference of particles from coherent sources. Of particular interest to us here are multiparticle interference effects, discovered by Hanbury Brown and Twiss (HB-T), who performed intensity interferometry experiments using incoherent thermal sources [6]. In a previous paper [7], an experiment was proposed to detect a nonlocal Pancharatnam phase in polarized intensity interferometry. The idea of the experiment, c.f. Fig. 1, is to have two thermal sources of opposite circular polarizations, P R and P L , where R and L describe right and left hand circular polarizations respectively. These illuminate two detectors that are covered by linear polarization analyzers, P 3 and P 4 . A theoretical analysis of the experiment reveals that as the relative angle between the two linear polarizations, ϕ 34 , is changed, the rate of coincidence counts between the arrival time of photons at the two detectors varies sinusoidally [7].

In recent years there have been many interferometric studies involving pairs of photons [8][9][START_REF] Shih | An Introduction to Quantum Optics : Photon and Biphoton Physics[END_REF][START_REF] Brendel | [END_REF][START_REF] Hariharan | Optical Interferometry 2nd Edition[END_REF]. Most of these studies use entangled photon pairs generated by spontaneous parametric down conversion and address effects like teleportation and Bell's inequality. There has been one study of geometric phases in two-photon interference [START_REF] Brendel | [END_REF] involving parametrically down converted photon pairs focussing on the interplay between geometric and dynamic phases. In contrast, in our work work we use thermal sources to generate photon pairs and study the role of the geometric phase in inducing non-local cross correlations.

Entanglement lies at the very heart of quantum physics. It is now widely recognized as a fundamental resource in the growing field of quantum information, regarding both quantum computation and communication protocols [START_REF] Tittel | [END_REF][START_REF] Nielsen | Quantum Computation and Quantum Information 10th Edition[END_REF]. As with any resource, effective use requires control, and quantum information applications are especially concerned with the degree of entanglement between spatially separated quantum channels or systems. A multiparticle Aharonov-Bohm effect was discussed theoretically by Büttiker [START_REF] Büttiker | [END_REF] who noted in the context of electronic charge transport that two-particle correlations can be sensitive to a magnetic flux even if the single particle observables are flux insensitive. The effect of the flux is visible only in current cross correlations and is a genuinely nonlocal and multiparticle Aharonov-Bohm ef-Fig. 1: General scheme for the Pancharatnam phase dependent two-photon intensity interferometry. Two sources illuminate two detectors by direct processes (blue, dotted lines), and by exchange processes (red, dashed-dotted lines). The sources are respectively followed by analyzers for opposite circular polarization, and analyzers for different linear polarizations are placed in front of the detectors.

fect [16]. This has been experimentally seen in intensity interferometry experiments carried out using edge currents in quantum Hall systems [17], and the theory is further developed in [18,19]. These authors propose an experiment in which Aharonov-Bohm fluxes may be used to control the orbital entanglement of electronic states. While this proposal is sound in principle, in practice, such experiments may be afflicted by decoherence [START_REF] Tittel | [END_REF][START_REF] Nielsen | Quantum Computation and Quantum Information 10th Edition[END_REF]. In contrast to electronic states, photonic states are easier to generate, manipulate and distribute. Most studies related to quantum communication protocols use photons rather than massive particles. However, photons are neutral and unaffected by the magnetic fields needed in the Aharonov Bohm effect. The idea here is to use the geometric phase as an effective magnetic field to control the degree of photonic entanglement [7].

As a step towards achieving this goal, we report in this letter an experiment based on two independent polarized thermal sources for a demonstration of the nonlocal Pancharatnam phase effect. Such a nonlocal effect can only be observed in the intensity cross correlations G (2) . A previously reported experiment involving single photons prepared in mixed polarization states led to lower order correlations G (1) [20]. Here we take advantage of the setup suggested in [7] and show that the geometric phase effect only appears in the coincidence counts between spatially separated detectors when the relative angle between the polarization analysers is tuned. The two photon Pancharatnam phase is nonlocal in the precise sense that it cannot be observed when local measurements at either detector are performed. The coincidence counts between the two detectors are modulated by a phase which has a geometric component as well as a dynamical (or propagation) phase.

Ideally, the experiment should use a priori incoherent thermal sources, as in the HB-T experiment. However, natural thermal light sources would necessitate very short integration times (shorter than the coherence time), which is hard to implement experimentally. Standard laser sources, which are usually used in amplitude inter-ferometry, are unsuitable since they are coherent and do not show the HB-T effect. In this experiment, we use a laser source and introduce incoherence by passing the laser beam through a ground glass plate [21]. This gives us a source of light in which the amplitude and phase are randomly varying, mimicking a thermal light source intensity distribution. Using such a (pseudo-thermal) source, we demonstrate the nonlocal Pancharatnam phase [7].

Theory. -The central quantity of interest is the polarized intensity-intensity correlation function measured by the coincidence counts for the detectors D 3 and D 4 , given by:

C = G (2) 34 = N 3 N 4 N 3 N 4 , (1)
N 3 and N 4 being the photon numbers detected at D 3 and D 4 per time per bandwidth. The detailed theory is outlined in [7]. The theoretical prediction for C is:

C = 3 2 + 1 2 cos k[(r 13 -r 14 ) -(r 23 -r 24 )] + Ω 2 , (2)
where r ij , with i = 1, 2 and j = 3, 4, denote the optical path lengths between the sources S 1 and S 2 and detectors D 3 and D 4 . Ω is the solid angle enclosed by the geodesic path shown in Fig. 2. This theoretical calculation can be summarized as follows. There is a process in which a photon from S 1 reaches detector D 3 and a photon from S 2 reaches D 4 (direct process, shown in blue). There is also a corresponding exchange process in which a photon from S 1 reaches D 4 and one from S 2 reaches D 3 (exchange process, shown in red). These two processes are indistinguishable, and in the absence of any 'welcherweg' information, we have to combine the amplitudes for these processes with a relative phase φ, which depends on the optical path difference between the two processes. The quantum interference between these processes causes the HB-T effect. Only the interference between direct and exchange processes gives rise to oscillations; the remaining terms providing the background of 1 in G (2) . We expect the coincidence counts to vary with the propagation phases and thus, the counts should depend on the detector separation d D and the wavelength λ of the light. The new effect that is present in this polarized version of HB-T is that the coincidence counts also depend on the difference between the linear polarization angles for P 3 and P 4 , ϕ 34 , and is modulated by a geometric phase of half the solid angle Ω covered on the Poincaré sphere by the four polarizations involved (see Fig. 2). The closed path on the Poincaré sphere is a property of a pair of photons. The effect of the geometric phase on the coincidence rates of photons at the detectors D 3 and D 4 is what we measure in the experiment below.

Experiment. -Our experimental realization of Fig. 1 is schematically shown in Fig. 3. Two independent pseudothermal light sources (S 1 and S 2 ) are spatially filtered using single mode fibers, and their polarizations are adjusted to right-hand and left-hand circular (P R and P L for S 1 and S 2 , respectively) using polarizing beamsplitters (PBS) and quarter-wave plates. The output photons from the sources are first directed towards a set of non-polarizing beamsplitters (BS) in order to split each source into two paths. The four resulting paths are led towards the linear polarization analyzers P 3 and P 4 . A second set of BS is then used to recombine, before each analyzer, two paths, with identical probability amplitudes, emanating from S 1 and S 2 . The linear analyzers are each a half-waveplate and a PBS, and the detectors are two independent silicon avalanche photodiodes (APD), featuring 5% detection efficiencies and dark count rates on the order of 100/s.

Our pseudo-thermal sources emit monochromatic, thermal light, with an adjustable coherence time. This is accomplished by focusing a 852 nm external cavity diode laser on a rotating, ground glass disk, producing time dependent fluctuations in the beam [22,23]. The scattered light is then collected using two single-mode optical fibers, which provide suitable spatial mode selections. The light arrives at the observation point, P, scattered through different routes. The electric field intensity received can be written as a sum over scatterers E = Σ i E i exp (iφ i ), where the phase φ i and the amplitude E i due to the i th scatterer are both random. The statistics of the intensity fluctuations is given by a Rayleigh distribution [21,[START_REF] Loudon | The Quantum Theory of Light 3rd Edition[END_REF]

P (I) = 1 I 0 exp - I I 0 . (3)
The light received at P becomes uncorrelated with itself as the the beam traverses the plate. For a Gaussian beam profile incident on the glass plate, we expect the intensity autocorrelation function G (2) (τ ) = I(0)I(τ ) /( I(0) I(0) ) to show a Gaussian decay in time [START_REF] Loudon | The Quantum Theory of Light 3rd Edition[END_REF]. More precisely, G (2) (τ ) = 1 + exp (-π(τ /τ c ) 2 ), where the coherence time τ c is on the order of the time taken by a point on the glass plate to traverse the beam width. Such a Gaussian decay of correlations is indeed observed in our experiment. The average intensities have been chosen such that both the probability of having more than one photon during the dead-time of the APDs (45 ns), and the probability of having a dark count, are negligible. The effective coherence times of the sources, and the absence of correlations between them, have been tested by measuring their autocorrelations (G [START_REF] Shapere | Geometric Phases in Physics[END_REF] ii (τ )) and the crosscorrelation function (G (2) ij (τ )). The corresponding experimental results are shown in Fig. 4. As predicted, both sources feature a Gaussian correlation decay as a function of time, associated with coherence times of about 7-800 µs. In addition they exhibit no crosscorrelation, proving they are actually independent. Therefore, we have estimated that sampling frequencies down to 100 kHz will ensure good measurements of G (2) (0), while 10 5 samples give us a negligible error. These parameters have been chosen in order to minimize the measurement time, and thus avoiding any unwanted path length fluctuations in the interferometer, as well as frequency drifts of the laser.

To observe the interference pattern in the coincidence counts C (see Eq. 2), we rotate the P 3 analyzer's halfwaveplate by an angle θ from 0 to 2π, thereby continuously scanning the polarization (and thus the angle ϕ 34 , from 0 to 4π). The recorded signal is shown in Fig. 5, as well as the expected fringe pattern with an ideal visibility.

Discussion. -Apart from its intrinsic interest as a demonstration of the nonlocal geometric phase in optics, one of our prime motivations is to realize a controllable and reconfigurable circuit enabling the generation and the manipulation of all the four photonic entangled Bell states [START_REF] Nielsen | Quantum Computation and Quantum Information 10th Edition[END_REF]. This can be done by extending our experiment in the following way. Let us first replace the two thermal sources of Fig. 1 by two simultaneously heralded single photon sources. We suppose that when two photons are emitted at the same time, i.e., one per source, they have opposite circular polarization. Second, we interface these polarized single photon emitters and the current setup by a time-bin preparation circuit acting on the two photons [START_REF] Tittel | [END_REF], where time-bin here is the means for creating coherent superpositions of states in the time domain. This way, using beamsplitters and identical delay lines for

τ (µs)

G (2) 11 G (2) 22 G (2) 12
Fig. 4: Autocorrelation functions (G the two photons, we can make these photons travel over short, | s , or long, | l , paths, with certain probability amplitudes, and accordingly prepare time-bin input qubits for the geometric phase setup. We prepare incident photons initially with P R and P L polarization in the time-bin superpositions | ϕ = α| s + β| l and | ψ = α ′ | s + β ′ | l , respectively. Here, α, β, α ′ , and β ′ are complex numbers related to the beamsplitting ratios. In this configuration [23], the output state is given by:

| Υ = 1 √ 2 | ϕ 3 | ψ 4 + e iφ | ψ 3 | ϕ 4 , (4)
where φ can be tuned using the geometric phase. On one hand, simply setting the input states to | ϕ = | s and | ψ = | l permits preparing time-bin entangled states of the form (| sl + e iφ | ls )/ √ 2. Such states are otherwise non trivial to produce by usual experimental means based on pulsed parametric down-conversion associated with a preparation interferometer [START_REF] Brendel | [END_REF]. Here, the geometric phase allows switching between the | Ψ + and the | Ψ -Bell states.

On the other hand, substituting in Eq. 4 superposition input states of the form

| ϕ = (| s + e iφ1 | l ) √ 2 and | ψ = (| s +e iφ2 | l )/ √ 2,
where φ 1 and φ 2 are the relative phases between short and long time-bin paths for either photon, leads to:

| Υ = 1 √ 2 | Φ(π + 2φ 1 ) cos φ 2 + e i 2 (φ+π+2φ1) | Ψ -sin φ 2 , (5)
in which we have set φ 2 = π + φ 1 . By setting φ = 0, and changing the two other phases, we have access to any superposition of | Φ -and | Φ + , and to these two basis states as well. This simple scheme therefore leads to the possibility of acting on and/or controlling the degree of entanglement. Regarding experimental realizations, note that the heralded photon sources and the entanglement preparation and control circuits could be realized in the near future using integrated optics, as discussed in [START_REF] Tanzilli | Laser & Photonics Reviews[END_REF]. This would make our scheme particularly suitable for practical realizations.

In the example above entanglement is generated by particle exchange effects rather than by interactions. The latter degree of entanglement can be quantified either using Bell's inequality or by the von Neumann entropy of the reduced density matrix, after tracing over one of the subsystems (3 or 4). A straightforward calculation of the von Neumann entropy shows that it does depend on the geometric phase. Since the geometric phase is achromatic, we can apply the same phase over all the frequencies in the band of interest by tuning ϕ 34 and generate entangled photon pairs with the degree of accuracy and the control needed for a source of photonic entanglement.

There have been measurements [START_REF] Brendel | [END_REF] of the geometric phase in intensity interferometry reported previously, where the geometric phase is also manifest in the lower order correlations, and local in effects at each detector. This may be viewed as two copies of the single photon geometric phase, which either add or cancel (depending on their relative sign) rather than a genuine two particle phase. As a result the phase observed in this experiment is not half the solid angle on the Poincaré sphere, but twice this value or zero. There is also a difference in the nature of the source. The experiment described in [START_REF] Brendel | [END_REF] uses a pair of entangled photons as a source, while our sources are incoherent and thermal, just like in the original HB-Texperiment.

Conclusion. -To conclude, we have experimentally demonstrated a simple generalization of the HB-T effect, making use of the vector nature of light in order to produce a nonlocal geometric phase. The only conceptual difference between the proposed experiment and the classic HB-T experiment is the presence of polarizers at the sources and detectors. These polarizers cause a geometric phase to appear in the coincidence counts between the two detectors that receive linearly polarized light. Neither the single count rates, nor the self correlations of individual detectors show any geometric phase effects. These appear solely in the cross correlation between the count rates of the detectors. This experimental demonstration will open up possibilities for entanglement tuning via the geometric phase.

Fig. 2 :

 2 Fig. 2: Path on the Poincaré sphere determining the detected geometric phase. The relative angle ϕ34 between the linear polarizers P3 and P4 sets the angular width of the enclosed surface on the sphere. Ω = 4ϕ34 corresponds to the solid angle defined by the geodesic path R → P3 → L → P4 → R.

Fig. 3 :

 3 Fig. 3: Experimental setup for demonstrating the Pancharatnam phase at the two-photon level. S1 and S2 : independent pseudo-thermal light sources; SMF: single-mode optical fibre; L: lens; PBS: polarizing beamsplitter; λ/4 and λ/2: quarterand half-waveplates, respectively; BS: non-polarizing beamsplitter; APD: avalanche photodiode.

  )) of the pseudo-thermal light sources S1 and S2 (red and green), and their crosscorrelation function (G (2) 12 (τ ) -blue), as functions of time using sampling frequency of 1 MHz.

Fig. 5 :

 5 Fig. 5: Crosscorrelation function C = G (2) 34 (0), as function of the angle ϕ34 = 2θ between the polarizations P3 and P4.

We acknowledge support from the CNRS, the University of Nice -Sophia Antipolis, the Agence Nationale de la Recherche (ANR) for the 'e-QUANET' project (grant agreement ANR-09-BLAN-0333-01), the European ICT-2009.8.0 FET Open program for the 'QUANTIP' project (grant agreement 244026), and the Conseil Regional PACA, for financial support.


MATJA Ž KOV Sylvain Gravier
email: sylvain.gravier@ujf-grenoble.fr

Michel Še

Julien Mollard

Aline Moncel

Parreau

Matjaž Kovše
email: matjaz.kovse@gmail.com

Michel Mollard
email: michel.mollard@ujf-grenoble.fr

Julien Moncel
email: julien.moncel@iut-rodez.fr

Aline Parreau
email: aline.parreau@ujf-grenoble.fr

NEW RESULTS ON VARIANTS OF COVERING CODES IN SIERPI ŃSKI GRAPHS

Keywords: codes in graphs, identifying codes, locating-dominating codes, totaldomination, Sierpiński graphs AMS subject classification (2010): 05C78, 94B25, 05C69

In this paper we study identifying codes, locating-dominating codes, and total-dominating codes in Sierpiński graphs. We compute the minimum size of such codes in Sierpiński graphs.

Introduction and notations

1.1. Sierpiński graphs. Motivated by topological studies from [START_REF] Lipscomb | Lipscomb's L(A) space fractalized in Hilbert's l 2 (A) space[END_REF][START_REF] Milutinović | Completeness of the Lipscomb space[END_REF] graphs S(n, k) have been introduced in [START_REF] Klavžar | Graphs S(n, k) and a variant of the Tower of Hanoi problem[END_REF] and named Sierpiński graphs in [START_REF] Klavžar | 1-perfect codes in Sierpiński graphs[END_REF]. In the book [START_REF] Lipscomb | Fractals and Universal Spaces in Dimension Theory[END_REF] these graphs are called Klavžar-Milutinović graphs. For n ≥ 2 and k ≥ 3, the graph S(n, k) is defined on the vertex set {0, 1, 2, . . . , k -1} n (see Figure 1 for S(3, 3) and S(2, 4)), where two different vertices (i 1 , i 2 , . . . , i n ) and (j 1 , j 2 , . . . , j n ) are adjacent if and only if there exists an index h in {1, 2, . . . , n} such that (i) i t = j t , for t = 1, . . . , h -1; (ii) i h = j h ; and (iii) i t = j h and j t = i h for t = h + 1, . . . , n.

A vertex of the form (i, i . . . , i) of S(n, k) is called an extreme vertex , all other vertices of S(n, k) are called inner vertices. The extreme vertices of S(n, k) are of degree k -1 while the degree of the inner vertices is k. Note also that there are exactly k extreme vertices in S(n, k), and that S(n, k) has k n vertices. Let u = (i 1 , i 2 , . . . , i n ) be an arbitrary vertex of S(n, k). We denote by K(u) the k-clique induced by vertices of the form (i 1 , i 2 , . . . , i n-1 , j), 1 ≤ j ≤ k. Notice that the neighbourhood of an extreme vertex u is K(u) \ {u}, and that an inner vertex u has only one neighbour that does (0, 0, 0) (0, 0, 2) (0, 0, 1)

(0, 1, 0) (0, 2, 0) (0, 1, 1) (0, 2, 2) (0, 2, 1) (0, 1, 2) (1, 0, 0) (1, 0, 1) (1, 0, 2) (2, 0, 0) (2, 0, 2) (2, 0, 1) (2, 1, 0) (1, 2, 0) (1, 1, 0) (1, 1, 1) (2, 2, 2) (2, 2, 0) (2, 2, 1) (2, 1, 2) (2, 1, 1) (1, 2, 2) (1, 2, 1) (1, 1, 2) (0, 0) (0, 1) (0, 2) (0, 3) (3, 0) (3, 1) (3, 3) (3, 2) (1, 0) (1, 1) (1, 2) (1, 3) (2, 0) (2, 1) (2, 2) (2, 3)
Figure 1. The Sierpiński graphs S(3, 3) and S(2, 4), together with the corresponding vertex labelings. The extreme vertices of S(3, 3) are (0, 0, 0), (1, 1, 1) and (2, 2, 2), whereas the extreme vertices of S(2, 4) are (0, 0), (1, 1), [START_REF] Ben-Haim | Adaptive identification in torii in the king lattice[END_REF][START_REF] Ben-Haim | Adaptive identification in torii in the king lattice[END_REF], and [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]. Notice that each inner vertex u has exactly one neighbour outside the k-clique K(u), and that the set of edges {uv edge of S(n, k) | K(u) = K(v)} is a matching. not belong to K(u). Moreover, the set of edges {uv edge of S(n, k) | K(u) = K(v)} is a matching. These properties will be extensively used in the sequel.

Notice that the Sierpiński graph S(n, k) can be constructed inductively as follows. We start the construction with a k-clique, that can be seen as the Sierpiński graph S(1, k). To construct S(2, k), one has to make k copies of the k-clique, that will be connected to each other with an edge set in 1-to-1 correspondence with the edges of a k-clique. By repeating this procedure, we can then recursively construct S(n, k) by connecting k copies of S(n -1, k) with a set of k(k-1) 2 edges (see Figure 2). Sierpiński graphs S(n, 3) coincide with the so-called Tower of Hanoi graphs, which are studied in details in the forthcoming book [START_REF] Hinz | The Tower of Hanoi: Myths and Maths[END_REF]. Another family of graphs related to Sierpiński graphs are the so-called Sierpiński gasket graphs, where all edges which are themselves maximal cliques are contracted. Some more variations of graphs that can be obtained from Sierpiński graphs have been considered in the papers [START_REF] Jakovac | A 2-parametric generalization of Sierpiński gasket graphs[END_REF][START_REF] Klavžar | Crossing numbers of Sierpiński-like graphs[END_REF][START_REF] Teguia | Sierpiński gasket graphs and some of their properties[END_REF]. Recently generalized Sierpiński graphs have been introduced in [START_REF] Gravier | Generalized Sierpiński graphs[END_REF]. They are defined in a similar way as Sierpiński graphs, the difference lying in the fact that the starting graph can be any graph and not just a clique. Extending the result about the existence of 1-perfect codes in the Tower of Hanoi graphs from [START_REF] Cull | Error-correcting codes on the Towers of Hanoi graphs[END_REF] and [START_REF] Li | Perfect codes on the Towers of Hanoi graphs[END_REF], it has been shown in [START_REF] Klavžar | 1-perfect codes in Sierpiński graphs[END_REF] that 1-perfect codes exist for all graphs S(n, k). More precisely it is shown in [START_REF] Klavžar | 1-perfect codes in Sierpiński graphs[END_REF] that

γ(S(n, k)) = k • k n-1 +1 k+1 , if n is even k n +1 k+1 , if n is odd
where γ(G) denotes the domination number of a graph G. This result has been further generalized in [START_REF] Beaudou | Covering codes in Sierpiński graphs[END_REF], where all existing (a, b)-codes of Sierpiński graphs have been characterized. Sierpiński graphs have also been studied for L(2, 1)-labelings [START_REF] Gravier | Codes and L(2, 1)-labelings in Sierpiński graphs[END_REF], crossing numbers [START_REF] Klavžar | Crossing numbers of Sierpiński-like graphs[END_REF], and different types of colorings [START_REF] Klavžar | Coloring Sierpiński graphs and Sierpiński gasket graphs[END_REF][START_REF] Klavžar | Vertex-, edge-, and total-colorings of Sierpiński-like graphs[END_REF].

In this note we compute the minimum size of identifying codes, locating-dominating codes, and total-dominating codes in Sierpiński graphs.

Codes in graphs.

In a simple undirected graph G, let d(u, v) denote the minimum number of edges of a path having u and v as extremities. Let C be a subset of vertices of G, we call C a code of graph G. For a vertex u of G, let us denote

I(u, C) = {v ∈ C | d(u, v) ≤ 1}. We say that C covers a vertex u if we have I(u, C) = ∅.
In other words, C covers u if and only if we either have u ∈ C, or there exists v ∈ C such that u and v are neighbours. The code C is said to totally cover a vertex u if we have

I(u, C)\{u} = ∅. We say that C separates two distinct vertices u, v if I(u, C) = I(v, C).
The code C is a covering code (or a dominating code) of G if C covers all the vertices of G. It is a total-dominating code of G if it totally covers all the vertices of G. It is an identifying code if it is a covering code of G that separates all pairs of distinct vertices of G. It is a locating-dominating code if it is a covering code of G that separates all pairs of distinct vertices of G, where neither of the vertices of a pair belongs to C. This terminology is standard, see [START_REF] Cohen | Covering codes[END_REF] for more about covering codes and [START_REF] Lobstein | Watching systems, identifying, locating-dominating and discriminating codes in graphs[END_REF] for a bibliography of problems about identifying codes and locating-dominating codes.

Many papers in the recent literature deal with these codes considered in regular structures, such as hypercubes [START_REF] Charon | New Identifying Codes in the Binary Hamming Space[END_REF][START_REF] Exoo | Improved bounds on identifying codes in binary Hamming spaces[END_REF][START_REF] Moncel | Monotonicity of the minimum cardinality of an identifying code in the hypercube[END_REF], lattices [START_REF] Ben-Haim | Adaptive identification in torii in the king lattice[END_REF][START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Charon | The minimum density of an identifying code in the king lattice[END_REF][START_REF] Honkala | On identifying codes in the king grid that are robust against edge deletions[END_REF], cycles [START_REF] Bertrand | Identifying and locating-dominating codes on chains and cycles[END_REF][START_REF] Chen | Identifying codes and locating-dominating sets on paths and cycles[END_REF][START_REF] Gravier | Identifying codes of cycles[END_REF][START_REF] Junnila | Optimal identifying codes in cycles and paths, to appear in Graph[END_REF][START_REF] Roberts | Locating sensors in paths and cycles: The case of 2-identifying codes[END_REF][START_REF] Xu | Identifying codes of cycles with odd orders[END_REF], and Cartesian products of graphs [START_REF] Gravier | Identifying codes of cartesian product of two cliques of the same size[END_REF][START_REF] Mollard | On perfect codes in Cartesian product of graphs[END_REF]. In the present paper we propose to address the computation of the minimum cardinality of such codes in Sierpiński graphs.

Identifying codes in Sierpiński graphs

Theorem 2.1. The minimum cardinality of an identifying code in a Sierpiński graph

S(n, k) is k n-1 (k -1).
Proof. We shall first prove that for any identifying code C of S(n, k), we have |C| ≥ k n-1 (k -1). For each inner vertex u of S(n, k), let m(u) denote the unique neighbour of u which does not belong to K(u). For each k-clique K of S(n, k), let us consider the set M (K) = {m(u) | u is an inner vertex of K}. Clearly, the M (K)'s are all disjoint, and the number of such sets is k n-1 . Now, by way of contradiction, assume that there exist two inner vertices u, v of a given k-clique K such that m(u) and m(v) do not belong to C. Then u and v would not be separated, a contradiction. Moreover, if K contains an extreme vertex, all the vertices of M (K) must be in C to separate the extreme vertex from the other vertices of K. Hence, for each k-clique K, there are at least k -1 vertices of M (K) that belong to C. Since there are k n-1 sets M (K), and they are all disjoint, this implies that the cardinality of C is at least k n-1 (k -1). Now, observe that if n = 2, then the set of inner vertices of S(2, k) is an identifying code of S(2, k), of cardinality k(k -1). Hence the minimum cardinality of an identifying code of S(2, k) is k(k -1). Now let us consider the general case S(n, k), with n ≥ 2. Let C be the subset of vertices of S(n, k) such that, for any subgraph S of S(n, k) which is isomorphic to S(2, k), the vertices of S that belong to C are exactly the inner vertices of S. It is easy to see that C is an identifying code of S(n, k), of cardinality k n-1 (k -1).

Locating-dominating codes in Sierpiński graphs

Theorem 3.1. The minimum cardinality of a locating-dominating code in a Sierpiński graph S(n, k)

is k n-1 (k-1) 2 . Proof. Let us first show that if C is a locating-dominating code of S(n, k), then |C| ≥ k n-1 (k-1) 2
. Let C be a locating-dominating code. We call an edge uv a crossing edge if it is a maximal clique itself, that is to say K(u) = K(v). The set of crossing edges is a matching and each inner vertex belongs to exactly one crossing edge. Consider now the following partition P of the vertices of S(n, k): Each extreme vertex is itself a part of P and each pair of vertices {u, v} forming a crossing edge is a part of P. For each vertex u of S(n, k), let P (u) be the set of P containing u.

By way of contradiction, assume that there exist two vertices u, v of a given k-clique K such that P (u) ∪ P (v) contains no element of C. Then u and v are not in the code and not separated, a contradiction. Hence, for any k-clique K, at least k -1 sets among the k sets of P containing one vertex of K must contain a vertex of C. A set of P can contribute to at most two different k-cliques and there are k n-1 k-cliques. Therefore,

|C| ≥ k n-1 (k-1)
2 . Now, let us consider any code C such that for each k-clique K, k -1 of the sets of P containing a vertex of K contain at least one vertex of C. It is easy to see that if this code C is such that each k-clique of S(n, k) contains at least one vertex of C, then C is a locating-dominating code of S(n, k). One can construct such a code C of cardinality

k n-1 (k-1) 2
with the following process.

• For n = 2, consider any code C with exactly one vertex on each crossing edge and at least one vertex on each clique. To construct such a code, one can for example take an hamiltonian cycle of K k , and for the corresponding crossing edge (there is a natural bijection between the crossing edges of S(2, k) and the edges of a k-clique), take every second vertex. Clearly, this code has size k(k-1)

2

. • For n ≥ 3, on each subgraph S of S(n, k) which is isomorphic to S(2, k), we put in the code C the vertices of S corresponding to the previous code of S(2, k).

There are k n-2 such (disjoint) subgraphs S, hence, C has size k n-1 (k-1)

2

.

For n = 3 we choose in each copy of S(2, k) inside S(3, k), a subset of vertices induced by a maximum matching of K k and put them in the set C. For a k-clique that is not dominated, we choose the extreme vertex of S(2, k) and put it in set C. We can choose k-cliques belonging to different copies of S(2, k) so that they induce a maximum matching in K k , and choose corresponding extreme vertices and put them into C. Similarly as in the case n = 2, one k-clique remains which has only one vertex in C and therefore we must add one more vertex from this k-clique to C in order to get a minimum total-dominating code of S (3, k). By iteratively repeating this procedure we construct a minimum total-dominating code of S(n, k), for any given n ≥ 4. Therefore it follows that γ t (S(n, k)) = k n-1 + 1, when k is odd.

Remarks

Foucaud et al. [START_REF] Foucaud | Bounds on the size of identifying codes in triangle-free graphs[END_REF] propose the following conjecture about an upper bound of the cardinality of a minimum identifying code of a given graph in terms of its number of vertices and maximum degree. We recall that two adjacent vertices are said to be twins if they have the same neighbourhood. A graph having no twins is said twin-free. A graph admits an identifying code if and only if it is twin-free. From the results of this paper it follows that Sierpiński graphs attain this bound. It might be interesting to consider another families of graphs attaining this bound that might be constructed in a similar manner as Sierpiński graphs or to provide a counterexample to the given conjecture.

  Partially supported by ANR/NSC Project GraTel, ANR-09-blan-0373-01 and NSC99-2923-M-110-001-MY3, 2010-2013. Partially supported by ANR Project IDEA, ANR-08-EMER-007, 2009-2011.

Figure 2 .

 2 Figure 2. Illustration for k = 4 of the recursive procedure that enables to construct a Sierpiński graph S(n, k) from k copies of S(n-1, k). From left to right are represented the starting graph K 4 , then S(2, 4) and S(3, 4).

Conjecture 5 . 1 (

 51 [START_REF] Foucaud | Bounds on the size of identifying codes in triangle-free graphs[END_REF]). For every connected twin-free graph G of maximum degree ∆ ≥ 3, the minimum cardinality of an identifying code of G is less than or equal to |V (G)| -|V (G)| ∆(G) .

Total-dominating codes in Sierpiński graphs

Theorem 4.1. Let γ t (G) denote the minimum cardinality of a total-dominating code in a graph G. Then we have γ t (S(n, k)

Proof. We first show that in any subgraph isomorphic to S(2, k), at least k vertices must belong to a total-dominating code. Let S be a subgraph isomorphic to S(2, k) and let C be a total-dominating code of S(n, k). If all the k-cliques of S contain at least one vertex of C, then we are done. Hence, let us assume that there is a k-clique K of S containing no vertex of C. This implies that K does not contain any extreme vertex. Then each vertex u of K has exactly one neighbour m(u) that is not in K, and must therefore be in C. In addition, at least one neighbour of m(u), which is in

), must also be in C. Each other k-clique of S must then contain at least two vertices of C. Hence S contains at least 2(k -1) ≥ k vertices of C, and we are done. This proves that the cardinality of a total-dominating code is greater than or equal to k n-1 . Now we distinguish two cases. First let k be an even number. Let C bet the set of vertices of S(2, k) induced by a perfect matching of K k , such that vertices (i, j) and (j, i) of S(2, k) belong to C if and only if edge {i, j} of K k belongs to the perfect matching. Set C covers all vertices of S(2, k), and since any vertex from C has also a neighbour from another clique which is also in C, then the set C is a total-dominating code. Hence C is a minimum total-dominating code of S(2, k). Using the same arguments for each copy of S(2, k) in S(n, k) it follows that γ t (S(n, k)) = k n-1 , when k is even. Note that since each vertex of a total-dominating code C must be a neighbour of another vertex of C, then all minimum total-dominating codes can be constructed in such a way.

When k is odd, it is impossible to find a total-dominating code of k n-1 vertices intersecting each k-clique exactly once. Indeed, in this case, each vertex of C would be neighbour to exactly one another vertex of C. Hence there would be a perfect matching running on an odd number of vertices, which is impossible. Hence, when k is odd, the cardinality of a total-dominating code is greater than or equal to k n-1 + 1.

Let us first consider the case n = 2. To construct a minimum total-dominating code, we can similarly take a maximum matching of K k , and build set C in the same way as in the previous case. In this case one k-clique of S(2, k) is not dominated by C and we must add two of its vertices to C to get a minimum total-dominating code. This gives altogether one additional vertex in C compared to the size of C in the even case.


Antoine De Rengervé

Pierre Andry
email: andry@ensea.fr

Philippe Gaussier
email: gaussier@ensea.fr

A developmental approach of imitation to study the emergence of mirror neurons in a sensory-motor controller

Mirror neurons have often been considered as the explanation of how primates can imitate. In this paper, we show that a simple neural network architecture that learns visuo-motor associations can be enough to let low level imitation emerge without a priori mirror neurons. Adding sequence learning mechanisms and action inhibition allows to perform deferred imitation of gestures demonstrated visually or by body manipulation. With the building of a cognitive map giving the capability of learning plans, we can study in our model the emergence of both low level and high level resonances highlighted by

Introduction

Imitation is an important feature providing individuals with the ability to learn from others but also (and perhaps mainly) to communicate with others. Rizzolatti and al. [START_REF] Gallese | Action recognition in the premotor cortex[END_REF] [START_REF] Rizzolatti | THE MIRROR-NEURON SYSTEM[END_REF] discovered in monkeys some neurons activated both when a monkey performs an action and when it observes another monkey or a human doing the same action. These mirror neurons were originally found in the area F5 of the premotor cortex. Yet the mirror system spreads over several cortical structures. The Inferior Parietal Lobule (IPL) also presents some neurons with mirror pattern activation whereas in the Superior Temporal Sulcus (STS), some neurons are more sensitive to observation of actions performed by others and thus support learning by imitation features. In monkeys, the mirror neuron activities are related to actions like grasping and placing objects. An observed action can produce activation even if it is partially occluded. It has been hypothesized that the role of mirror neurons is to enable the recognition of actions that are performed by others. The development of this feature would be an adaptation of evolution as it allows better social collaboration and imitation. Several models have considered this hypothesis as a justification to action recognition capabilities and learning by imitation in robots [START_REF] Demiris | Imitation, Mirror Neurons, and the Learning of Movement Sequences[END_REF]. Yet the role of mirror neurons in task learning can be questioned since it is not clear if these neurons are the cause or the consequence of skill learning. Even if some proto-imitation of tongue protrusion was observed in neonates [START_REF] Meltzoff | Imitation of facial and manual gestures by human neonates[END_REF], it can not be advocated that it reflects inherited imitation capabilities [START_REF] Jones | The development of imitation in infancy[END_REF]. How can mirror neurons learn associations between visual information and the correct action ? If mirror neurons have to be learned, the imitated actions need to be already known. At the opposite of these models, we will advocate the hypothesis that mirror neurons are a side effect of some sensory-motor learning. They can next be used for social interactions (communication) but not primarily for learning by imitation.

Recently, several works have proposed models that aims at explaining how mirror neurons can emerge from sensory-motor associations learning [START_REF] Metta | Understanding mirror neurons: A biorobotic approach[END_REF] [START_REF] Nishimoto | Learning Multiple Goal-Directed Actions Through Self-Organization of a Dynamic Neural Network Model: A Humanoid Robot Experiment[END_REF]. These works focus on the emergence of action recognition capabilities. In early work [START_REF] Gaussier | From Perception-Action loops to imitation processes: A bottom-up approach of learning by imitation[END_REF], we showed how some imitation behaviors can be obtained from simple sensorymotor associations. Without the capability of recognizing the action of others and without even the capability of discriminating others from himself, the robot could already exhibit a low level imitation behavior.

In this paper, we start from a minimal Neural Network [START_REF] Andry | Learning Invariant Sensorimotor Behaviors: A Developmental Approach to Imitation Mechanisms[END_REF] to study from a developmental perspective how low level imitation (mimicry), sequence learning and then action selection behaviors can be exhibited, without a priori mirror neurons. Starting from sensorymotor controller that let low level imitation emerge, the model was then enhanced by including a module for sequence learning. The robot can reproduce sequences observed (Sec. 2) or demonstrated through physical manipulation (Sec. 3). This system can also learn and plan different actions according to different goals. In Sec. 4, we conclude on the "mirror" like properties of the neurons present in the different structures of the model. Mirror neuron activities are induced by reentrant learning first between visual and proprioceptive motor signals, next between objects and actions. This representation is based on [START_REF] Alexander | Parallel organization of functionally segregated circuits linking basal ganglia and cortex[END_REF] .

Learning tasks on the basis of low level visuo-motor associations

Starting from the coupling of a homeostatic system with perceptual ambiguity, we can obtain the emergence of a low level imitation behavior [START_REF] Gaussier | From Perception-Action loops to imitation processes: A bottom-up approach of learning by imitation[END_REF]. Initially, the robot learns visuo-motor associations between the detected position of its hand in its visual field and the motor configuration of its arm. The associative learning would be done in the supplementary motor area (SMA) and the premotor (PM) cortex (Fig. 1). Because of the limitations of the robot perception, there is an ambiguity between the robot hand and the human hand in front of the robot. The robot can look at the human hand and believe that it is its own hand. As the homeostatic system tries to maintain an equilibrium between the visual information and the motor information, the robot arm is moved into the motor configuration that corresponds to the visual input. An exterior observer sees a robot imitating the gestures of the human partner. Low level imitation can be a side effect of the perceptual ambiguity [START_REF] Andry | Learning Invariant Sensorimotor Behaviors: A Developmental Approach to Imitation Mechanisms[END_REF]. This visuo-motor controller has been implemented on a robot composed of an electrical arm (Katana from Neuronics AG) and a monocular camera mounted on pan-tilt servo motors (see [START_REF] De Rengervé | Emergent Imitative Behavior on a Robotic Arm Based on Visuo-Motor Associative Memories[END_REF] for details about the model). With this simple model, the robot can only reproduce meaningless gestures directly observed. By adding two other mechanisms, some deferred imitation of a demonstrated task can be obtained. First the robot can inhibit its own Figure 2: In a first phase, the robot inhibits its movement and memorizes the visual sequence of the perceived positions of the hand of a human who demonstrates the action of picking and placing a can. The experiment was realized with a small number of adequately chosen states. movements while it is observing the demonstration of the task. Next, the robot can memorize an observed sequence. The visual field of the robot is categorized into discrete areas or states. The observed sequence is the succession of the different visual states. Given an activated visual state, an internal rehearsal of the memorized sequence predicts the next visual state in the sequence. As a result of the visuo-motor learning, the predicted visual position is transformed into a predicted motor position that attracts the robot arm into the stored motor configuration. The robot reproduces the observed demonstration according to its learning (Fig. 2). The correspondence problem [START_REF] Nehaniv | The correspondence problem[END_REF] does not limit our system in that experiment. As only the arm end effector position is considered, the visuo-motor map and the regulation system directly find a motor configuration that corresponds to the final desired position.

The prefrontal cortex can detect and maintain the goals of the system thus it can generate the necessary signals to inhibit and select the actions and also to bias the attention of the system (Fig. 1). Novelty detection in the Hippocampus can trigger the encoding of the states and the transitions used to memorize sequences (Fig. 3). Neurons in the visuo-motor map are activated during the observation and the reproduction of the sequences. Their activation pattern is similar to the activation of the "low level resonance" mirror neurons. However, as their activities are not related to goals, these neurons cannot explain "high level resonance" mirror neurons. The only goal of the robot is to reproduce the demonstrated visual sequence (Fig. 2). The robot arm catches the can only because of a reflex behavior that is triggered when an object is detected within reach of the gripper.

Arm gesture planning

In Fig. 4, the robot possesses two different contextual goals associated to two types of objects (red or green). The focal vision of the robotic system categorizes the visual scene using color detection. When a red can is presented to the visual system, the corresponding goal is activated and stay active until another object is presented. If the new can is green, the red goal will be inhibited and the green goal will stay active.

These goals can be associated with sequences of proprioceptive states acquired through passive manipulation of the arm [START_REF] De Rengervé | On-Line Learning and Planning in a Pick-and-Place Task Demonstrated Through Body Manipulation[END_REF]. When the robotic arm moves, its proprioception (joint angles, gripper infrared and force sensor values) is categorized into distinct states. Each state is associated to a prototypical joint/gripper configuration. The categorization of the states is based on a recruitment of new states depending on a vigilance threshold. The states are encoded on the weights of the input links of recruited neurons. The information about the newly entered state and the former state are received and processed in the Hippocampus (see Fig. 3). The possible transitions between states are then learned when the arm moves from one state to the next. The transition activity is transmitted to a cognitive map spreading on the prefrontal cortex and the premotor area. A graph of the different transitions is created. The cognitive map encodes information about all possible paths by linking subsequent transitions.

The association between an active goal and the last performed transitions is made when a reward is received by the system. When a goal is set, the associated transition is also activated. There is a diffusion of this activation in the cognitive map from node to node with a max operator on the propagated activities and links with weights w < 1. As a result, transition neurons in the cognitive map have an activity proportional to their distance (in terms of number of transitions) to the transitions directly associated to the activated goals. The map gives the shortest path to the strongest or closest goal. In any given state, the system predicts all possible transitions. The activity in the cognitive map is used to Figure 4: A cognitive map can be used to learn a pickand-place task with different goals. Left: Experimental setup. Right: Projection of the cognitive map in the Cartesian space. The gradient toward the goal place follows the blackness and the thickness of the links between state nodes. The links are bias the selection of a particular transition in the Basal Ganglia (Fig. 3). The transition that has the highest potential, ie. that corresponds to the shortest path to get the reward, is selected. When a transition is selected after competition, the prototypical motor configuration learned with the final state of this transition is given as the target position to the motor regulation (M1 and subcortical structures involved in muscular control). This system has been tested on the same robot than in section 2 to learn a pick-and-place task through body manipulation (Fig. 4). Depending on the detected object (e.g. red can), a gradient of activity is propagated from the transition corresponding to drop the can at the correct place to the current state of the robot. The task can also be adapted on-line. A new sequence can be demonstrated (e.g. putting red cans in place 2 instead of place 1) and rewarded. Each time a reward is received, the current association is reinforced whereas the previous ones decay. The stability of a policy depends on how much it was rewarded. Typically learning can be done with about 2 trials and rule switching can be as fast.

In the cognitive map, the transitions neurons are activated when a goal is recognized. Their activities are similar to the activities of canonical neurons that are activated by just the perception of the object that determines the goal (here, the presence of the red can will activates the different transitions expected to be done). As a result of this activity diffusion in the cognitive map, the action is facilitated: the robot can choose the correct transitions among the possible ones. However, these neurons lack of selectivity as they can activates for affording objects and not only actions.

Conclusion

In this paper, we have followed a developmental approach of imitation validated on a real robot. Without embedding any a priori mirror neurons, our model enables the robot to display low level imitation of meaningless gestures. These gestures can be learned together as sequences. With a reward based associative learning, the sequences can become simple goal directed sequences (e.g. sorting cans according to their colors) still without involving the use of "high level" mirror neurons. Mirror neurons should not be used in robotics to justify some ad hoc skill transfer.

The sensory-motor structures involved in the development of imitative capabilities can explain the mirror neurons properties observed in the premotor cortex of primates. The visuo-motor associative maps display low level resonance that was found in humans [START_REF] Rizzolatti | From mirror neurons to imitation: Facts and speculations[END_REF]. In our model, premotor neurons can be activated when a specific object is presented, thus matching the canonical neurons found in the premotor areas. Yet, in our model, there is no neuron selective to the observation of high level actions. In order to learn more complex behaviors, the system should build chunks merging information about both recognizing an object and determining the context of the task i.e. the expected use of the object. According to our model (Fig. 1), the chunks would first be learned at the level of the prefrontal cortex. As the behavior becomes more automated, the management of the control should move onto the Basal Ganglia.

If our approach is correct, mirror neurons are first a side effect of previous learning. Yet, we believe mirror neurons are certainly very important for synchronization and communication during social interactions. Taking into account the resonance between two interacting partners in order to provide a good feedback to modulate learning in an interactive and autonomous way.

Figure 1 :

 1 Figure 1: Model of the brain structures and their connections corresponding to our implemented models for the development of imitative behaviors. The prefrontal (PF) structures are important for the control of the different phases of the behavior (observation, imitation).Mirror neuron activities are induced by reentrant learning first between visual and proprioceptive motor signals, next between objects and actions. This representation is based on[START_REF] Alexander | Parallel organization of functionally segregated circuits linking basal ganglia and cortex[END_REF] .

Figure 3 :

 3 Figure 3: Cortico-hippocampo-striatal loop modeled for the learning of sequences.

Acknowledgment

This work was supported by the INTERACT french project (referenced ANR-09-CORD-014).