Wilfried Glastre
email: wilfried.glastre@ujf-grenoble.fr

Olivier Jacquin

Olivier Hugon

Hugues Guillet De Chatellus

Eric Lacot

Synthetic aperture laser optical feedback imaging using a translational scanning with galvanometric mirrors

In this paper we present an experimental setup based on Laser Optical Feedback Imaging (LOFI) and on Synthetic Aperture (SA) with translational scanning by galvanometric mirrors for the purpose of making deep and resolved images through scattering media. We provide real 2D optical synthetic-aperture image of a fixed scattering target with a moving aperture and an isotropic resolution. We demonstrate theoretically and experimentally that we can keep microscope resolution beyond the working distance. A photometric balance is made and we show that the number of photons participating in the final image decreases with the square of the reconstruction distance. This degradation is partially compensated by the high sensitivity of LOFI.

1) Introduction

Making images with a good in-depth resolution through scattering media is a major issue, limited by a double problematic: first the scattering medium generally attenuates strongly the ballistic photons which enable to obtain resolved images and second, the wavefront is highly perturbed by scattered photons, degrading the quality of the resolved image. Several ways to overcome these problems have been proposed among which we can distinguish two main families. The first one uses pre-compensation of the wavefront before propagation, to improve the resolution. This technique is used successfully both with optics or acoustic modality [START_REF] Popoff | Measuring the Transmission Matrix in Optics : An Approach to the Study and Control of Light Propagation in Disordered Media[END_REF][START_REF] Pernot | In vivo transcranial brain surgery with an ultrasonic time reversal mirror[END_REF][START_REF] Vellekoop | Scattered light fluorescence microscopy : imaging through turbid layers[END_REF], but it requires an a priori knowledge of the medium. The second one selects ballistic photons while rejecting multidiffused parasitic photons: Optical Coherence Tomography (OCT) [START_REF] Dubois | Full-filed OCT[END_REF] and confocal microscopy associated [START_REF] Pantazis | Second harmonic generating (SHG) nanoprobes for in vivo imaging[END_REF] or not [START_REF] Minsky | Memoir on inventing the confocal scanning microscope[END_REF] to non linear effects belong to this family as well as tomographic diffractive microscopy [START_REF] Vertu | Improved and isotropic resolution in tomographic driffractive microscopy combining sample and illumination rotation[END_REF]. Our Laser Optical Feedback Imaging (LOFI) setup, based on optical reinjection in the laser cavity [START_REF] Lacot | Laser optical feedback tomography[END_REF][START_REF] Lacot | Coherent laser detection by frequency-shifted optical feedback[END_REF][START_REF] Otsuka | Self-Mixing Thin-Slice Solid-State Laser Metrology[END_REF] belongs to this second family. LOFI has the advantage of providing a self-aligned and very sensitive optical system limited by shot noise [START_REF] Lacot | Comparative study of autodyne and heterodyne laser interferometry for imaging[END_REF][START_REF] Jacquin | Experimental comparison of autodyne and heterodyne laser interferometry using Nd:YVO4 microchip laser[END_REF] whatever the detector noise is. It is a very simple (no alignment needed and transportable system) setup compared to many other interferometer. Losses in ballistic photons are compensated by this high sensitivity due to LOFI while multi-diffused photons are rejected by the confocal intrinsic feature of this technique. Furthermore it gives access to both amplitude and phase of the retrodiffused optical electric field.

In order to solve the issue of making in-depth images, we propose a new configuration based on synthetic aperture by translational scanning with galvanometric mirrors. The technique was introduced first in Synthetic Aperture Radar imaging (SAR) [START_REF] Curlander | Synthetic Aperture Radar: Systems and Signal Processing[END_REF][START_REF] Ja | Radar Imaging and Holography[END_REF] to overcome the fact that no large portable aperture component exists for radio waves. Synthetic Aperture consists in scanning the target with a diverging beam while recording amplitude and phase informations 3 (accessible thanks to LOFI in our case) on the movement of the laser spot with respect to the target. It enables to realize a numerical focusing to recover a good resolution. In the optical field, it has first been applied to optical wavelengths with CO 2 [START_REF] Aleksoff | Synthetic aperture imaging with a pulsed CO2 laser[END_REF] and Nd:YAG microchip laser sources [START_REF] Markus | Solid-state laser synthetic aperture radar[END_REF][START_REF] Green | Synthetic-aperture-radar imaging with a solidstate laser[END_REF][START_REF] Bashkansky | Two-dimensional synthetic aperture imaging in the optical domain[END_REF] in what is called Synthetic Aperture Laser (SAL). In all these previous pieces of work (SAR and SAL), the scanning was made only in one direction. The recovery of image resolution by synthetic aperture operation was performed in one direction (the scanning direction) whereas in the other direction only telemetry (a chirped signal is used instead of a monochromatic one, the frequency of the beating between the reinjected photons and the emitted signal depends on the round-trip length) is used to improve the resolution. Moreover at the beginning of SAL, the target itself was moved while the laser source was fixed. A setup presenting the advantage in terms of vibrations limitations and measurement speed, to have a fixed object and a scanning laser have been proposed in 2006 [START_REF] Beck | Synthetic-aperture imaging laser radar: laboratory demonstration and signal processing[END_REF]. However, it has the drawback to be quite complex and as we said before, presents anisotropic resolution due to 1D scanning. In our case, by using two dimensional scanning with galvanometric mirrors, we are able to recover an isotropic resolution with a complete 2D scanning. Here we demonstrate what we believe to be the first 2D optical synthetic-aperture image of a fixed, scattering target with a moving aperture and an isotropic resolution. This work is a continuation of [20,[START_REF] Witomski | Two dimensional synthetic aperture laser optical feedback imaging using galvanometric scanning[END_REF][START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF] where a galvanometric rotation scanning of a fixed object was performed with LOFI. The problem was that the object was scanned angularly, implying a degradation of the resolution with the reconstruction distance.

The setup we propose here is based on a translational scanning of the object and we show that it implies a conservation of the resolution whatever the reconstruction distance is.

In a first part we present our experimental setup and remind the principles of LOFI; in particular the translational laser scanning by galvanometric mirrors is introduced. We then present in a second part a complete study of synthetic aperture operation and show that we can keep microscope resolution beyond the working distance. To conclude, in a third and last part dedicated to photometric performances of the setup, we show that the final image quality degrades proportionally to the square of the distance of numerical refocusing. This drawback is partially compensated by the high sensitivity of LOFI.

2) Reminder on LOFI and presentation of the experimental setup

Experimental setup

Figure 1 shows a description of the LOFI [START_REF] Lacot | Laser optical feedback tomography[END_REF][START_REF] Lacot | Coherent laser detection by frequency-shifted optical feedback[END_REF] experimental setup. The laser is a cw Nd:YVO 4 microchip emitting about 85 mW power at λ = 1064 nm. This laser has a relaxation frequency near F R ≈ 2 MHz. On its first pass, the laser beam is frequency shifted by a frequency F e /2 where F e is close to the relaxation frequency of the laser (F R ≈ F e ), and then sent to the bidimensional target by means of two rotating mirrors, respectively called M x and M y . The first one allows scanning of the target in the horizontal direction (x direction) and the second one in the vertical direction (y direction). The angular orientations of the galvanometric mirrors are given by the angles α x and α y , respectively. The beam diffracted and/or scattered by the target is then reinjected inside the laser cavity after a second pass in the galvanometric scanner and the frequency shifter. The total frequency shift undergone by the photons reinjected in the laser cavity is therefore F e which results in triggering relaxation oscillations of the microlaser and in amplifying the sensitivity of the device to the reinjected photons. A small fraction of the output beam of the microchip laser is sent to a photodiode. The delivered voltage is analyzed by a lockin amplifier at the demodulation frequency F e , which gives the LOFI signal (i.e. the amplitude and the phase of the electric field of the backscattered light). Experimentally, the LOFI images (amplitude and phase) are obtained pixel by pixel (i.e., point by point, line after line) by full 2D galvanometric scanning (α x , α y ). We must now consider two possibilities:

 "Conventional" LOFI (Figure 1 and Figure 2 with L = 0) where we scan the object with a focused beam. We can get an amplitude [START_REF] Lacot | Laser optical feedback tomography[END_REF][START_REF] Lacot | Coherent laser detection by frequency-shifted optical feedback[END_REF] |h(α X ,α Y )| or phase [START_REF] Hugon | Submicrometric Displacement and Vibration Measurement Using Optical Feedback in a Fiber Laser[END_REF][START_REF] Hugon | Coherent microscopy by laser optical feedback imaging (LOFI) technique[END_REF] image Φ S (α X ,α Y ).

 Synthetic Aperture (SA) imaging LOFI [20, [START_REF] Witomski | Two dimensional synthetic aperture laser optical feedback imaging using galvanometric scanning[END_REF][START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF] corresponding to imaging with a defocused beam (Figure 1 and Figure 2 with L ≠ 0). This raw complex image h(α X ,α Y ) must be filtered to realize a numerical post focusing. It has the advantage, as we will see to make images beyond the working distance of the lens.

In the following, whatever the target position is, we index all parameters related to an image without any post processing with "R" (Raw) and those associated with a numerical refocusing with "SA" (Synthetic Aperture).

Experimental scanning

In order to get 2D image we need to have a relative translation between the target and the laser beam. In our setup we choose to keep a fixed target and to use galvanometric mirrors. The main advantage of this approach is to avoid parasitic vibrations and to benefit from the scanning speed of the galvanometric mirrors. Synthetic Aperture using galvanometric mirrors has previously been presented in [20,[START_REF] Witomski | Two dimensional synthetic aperture laser optical feedback imaging using galvanometric scanning[END_REF][START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF]. The object was scanned angularly by the two galvanometric mirrors and we showed that it was possible to obtain a resolved image from a raw defocus image

L  Y  X Target M Y f 3 M x f 4 f 3 + f 4

Amplitude

Phase after numerical refocusing. The main drawback was that the final synthetic resolution was degrading linearly with working distance (distance between the mirrors and the target) [20,[START_REF] Witomski | Two dimensional synthetic aperture laser optical feedback imaging using galvanometric scanning[END_REF].

To avoid that problem we choose here a translational (instead of angular) scanning of the target and we will show in following parts that it implies a constant resolution independently from the working distance. In our scanning setup the two galvanometric mirrors (M X and M Y ) are conjugated by a telescope formed by lens L 3 and L 4 having the same focal length f 3 = f 4 = 50 mm leading to a magnification of 1 (see Figure 1); we call M X ' the image of M X through the telescope. To achieve a translational scanning in X and Y directions, the mirrors M X ' and M Y are placed in the focal object plane of lens L 5 (see Figure 2). Lens L 5 (focal length f 5 = 25 mm here) converts the angular movement of the collimated laser beam after mirrors M X ' and M Y into a movement of translation and focuses the beam with a waist radius r ≈ 13 μm in the focal image plane of L 5 . It is important to precise that we are scanning with low angular amplitude (around one hundred of miliradian corresponding to few mm of spatial field for f 5 ' = 25 mm) for the two galvanometric mirrors as a result we can neglect aberrations that telescope and lens L 5 could add. This result in a planarity of the displacement of the beam waist with an interferometric precision (important for Synthetic Aperture processing); this have been experimentally checked by scanning a plane mirror, we got white light fringe. To further simplify our problem we make in the following, the approximation of paraxial and Gaussian optical rays which seems reasonable considering our experimental values (waist r = 13.5 μm for λ = 1064 nm). The relations between the angular position (α X ,α Y ) of the mirrors M X and M Y and the position (x,y) of the laser in the focal image plane are then given by: Due to mechanical imprecision, there can be a slight misalignment d X and d Y between the laser beam axis and mirrors M X ' and M Y rotation axis. As a result the angles θ X and θ Y between laser beam axis and the Z direction ( Figure 2) are:

y x f y f x   5 5 2 2   (1)
5 5 f d f d Y Y X X     (2)

3) Point Spread Function (PSF) of the synthetic image

Raw paraxial impulse response

r x,y L 5 M X ', M Y f 5 f 5 L Target Waist displacement plane 2 X,Y d X,Y Lens axis z  X,Y
We consider the situation of Figure 1 and Figure 2 where the target plane is situated at a distance L from the waist plane (focal image plane of L 5 ) and is scanned by a defocused beam. Because the imaging system is linear (if the object is laterally translated, the raw acquired image is simply translated too), we only need to consider the case of the response h R (L,x,y) of a punctual object located on the beam axis for  X and  Y = 0. Then the target coordinates are (Lθ X , Lθ Y ). This is the Point Spread Function (PSF) of the imaging system at a distance acquisition of L from the waist plane. For a more complex image t(x,y), the signal given by the imaging system is simply t(x,y) * h R (L,x,y), where * is the convolution operator. The electric filed striking the target can be simply derived from the propagation of complex electric field over a distance L. h R (L,x,y) then corresponds to the square of this electric field because of the symmetry between emission and reinjection of electric field:

) 2 ) ( 2 ) ( ) ( 2 exp( ) ) ( exp( ) ) ( 2 ) ( ) ( 2 exp( ) ) ) ( 1 ( exp( ) , , ( 2 2 2 2 2 2 2 2 2 2 2 2         L R L y L x j L RES y x L R L y L x j Z L r y x y x L h y x R y x R R                          (3) With :                    2 2 2 1 ) ( ) ( 1 2 ) ( L Z L L R r Z Z L r L RES R R R R   (4)
The square caused by symmetrical coupling between the object and the laser mode was forgotten in [20, [START_REF] Witomski | Two dimensional synthetic aperture laser optical feedback imaging using galvanometric scanning[END_REF][START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF] an so an error of √2 was made on the resolution in these articles; we have corrected this error here. In these equations and in future equations, we only give proportional expressions because only the shape (related to resolution) is interesting. Considering far-field situation (L >> Z R ), h R (L,x,y) corresponds to a wavefront of lateral spatial width RES R (L) and a radius of curvature R(L) / 2 ≈ L / 2. It is interesting to see the spectral content of the signal. Using the stationary phase theorem [START_REF] Bleistein | Fourier Integrals and the Method of Stationary Phase[END_REF] on Eq. ( 3), we get H R (L,υ,μ) the Fourier transform of h R (L,x,y), where (υ,μ) are the spatial frequencies associated with (x,y):

) 2 ) ) ( ) (( exp( ) ) ( ) ( exp( ) , , ( 2 2 2 2 2 2 Y X Y X R F F L j F F L H                      (5) With: r F F Y Y X X        2 2 2       (6)
Here too, it is important to give a more physical interpretation: each plane wave in the signal corresponds to a different spatial Doppler frequency. As a result H R (L,υ,μ) represents the decomposition of the signal into plane waves (each couple υ,μ represents a plane wave). The first exponential term represents the plane waves content of the laser beam of widths Δυ and Δμ inversely proportional to the waist r and centered around central Doppler shift (F X and F Y proportional to θ X and θ Y as seen in Eq. ( 2)). The second exponential term (phase term) gives the phase shifts between these plane waves which are characteristic of the defocus of the laser beam.

More precisely, this second term corresponds to the free space transfer function over a distance L / 2 as expected.

Numerical refocusing process

It is possible to numerically refocus on the object by eliminating the quadratic dephasing between plane waves expressed in the second exponential term of Eq. ( 5). This is equivalent to multiply H R (L,υ,μ) by the free space transfer function over a distance -L / 2 (retropropagation) H filter (L,υ,μ) given by: ) 2

) ( exp( ) , , ( 2 2 filter
        L j L H (7)
After numerical filtering, we get a signal H SA (L,υ,μ) in the spatial frequency domain:

)) ( exp( ) ) ( ) ( exp( ) , , ( ) , , ( ) , , ( 2 2 2
filter

Y X y x R SA F F L j F F L H L H L H                     (8)
If we calculate the inverse Fourier transform of H SA (L,υ,μ) we obtain h SA (L,x,y) the final numerically refocused image in the plane of the target:

) ) 2 ( ) ) ( ) (( exp( )) ( 2 exp( )) ) ( ) (( exp( ) , )( ( ) , , ( 2 2 2 2 2 2 2 1 r L y L x yF xF j L y L x y x H TF y x L h y x y x y x SA SA                      (9)
The final resolution is thus r / √2 which implies by comparing to Eq. ( 4) (RES R (0) = r / √2) that the lens L 5 resolution is recovered despite defocused raw acquisition. It is important to note that after filtering, the resolution does not depend on L but only on the plane wave content of the signal and so on r.

Final image resolution and comparison with raw imaging

It has been previously shown that by numerically refocusing the raw image on the target plane, we get the same resolution RES R (0) as if we used a direct focusing on the object. The question we can now ask is what happens if we have a second object (object 2) in a plane at a distance δ from object 1 (see Erreur ! Source du renvoi introuvable. a)) and if we perform a numerical refocusing in the plane of object 1. What is the signal of object 2? Considering this, the new synthetic signal depends now on an additional parameter and is noted h SA (L-δ,L,x,y) where the first parameter is the distance between the laser waist and the plane of object 2 (here L-δ) and the second parameter the distance between the laser waist and the plane of refocusing containing objet 1 (here L). In the Fourier space, from the raw signal H R (L-δ,υ,μ) (see Eq. ( 5)), we get after filtering by H filter (L,υ,μ) (see Eq. ( 8)) the final signal H SA (L-δ,L,υ,μ) (the Fourier transform of h SA (L-δ,L,x,y)):

) , , ( ) , , ( ) , , , ( filter 
       L H L H L L H R SA    (10)
To avoid unnecessary and complicated calculations, it is more convenient to have a physical vision to get the expression of h SA (L-δ,L,x,y). We remind that h R (L-δ,x,y) corresponds to the expression of a wavefront which have been propagated from a waist r / √2 on a distance (L -δ) / 2 (width RES R (L-δ)), with angles (2θ X, 2θ Y / Z direction). As H filter is the free space transfer function over a distance -L / 2 (Eq. ( 7)), we immediately deduce: [START_REF] Lacot | Comparative study of autodyne and heterodyne laser interferometry for imaging[END_REF] with:

) ) ( ) ( ) ( exp( ) , ))( , , , ( ( ) , , , ( 2 2 1
       SA y x SA SA RES L y L x y x L L H TF y x L L h         
    2 2 ' ' 2 ' ) ' 2 ( 1 ' ) ( r Z r r Z r RES R R SA     (12)
RES SA (δ) is the resolution of the signal h SA (L-δ,L,x,y). By comparing Eq. ( 4) and Eq. ( 12) we note that RES SA (δ) = RES R (δ). This implies that, considering the resolution, the numerical filtering by H filter (L,υ,μ) transforms the system into an equivalent one where lens L 5 is turned into a lens L 5eq with a focal length f 5eq = f 5 + L but keeping the same Numerical Aperture (NA) (see Erreur ! Source du renvoi introuvable.). As a result it is possible to get a higher working distance keeping a constant resolution and depth of field. In addition to the capability of extending the working distance, this arrangement opens the possibility of fast 3D imaging since we are able to choose the plane of focusing numerically with a single X-Y object scanning. Further work about 3D imaging is planned in a close future.

Another thing to consider is the evolution of acquisition time and amount of data with the initial defocusing L. The number of data we have to store corresponds to the number of pixels in the raw image. The number of pixels needed corresponds to a correct sampling of the signal in the spacespatial frequency domain (the whole object field at Shannon frequency). In the case of the acquisition without defocusing (L = 0), since each raw pixel is acquired during an integration time T, the total acquisition T acq (L = 0) is:

2 R acq, ) 0 ( r T L L T L L L T Y X Y X        (13)



In this expression L X and L Y are respectively the length and width of the target. In the case where L ≠ 0, the raw initial defocus increases the spatial width of the signal by 2RES R (L) in both X and Y directions; the spectral content stays unchanged (and so the sampling rate). As a result the total acquisition time is changed into T acq (L):

2 acq )) ( 2 ))( ( 2 ( )) ( 2 ))( ( 2 ( ) ( r T L RES L L RES L T L RES L L RES L L T R Y R X R Y R X           (14)
As a conclusion, the ability of going beyond the working distance of L 5 while keeping the resolution is possible at the cost of an increase of both time acquisition and quantity of data to store. This can be compared to angular galvanometric scanning developed in [START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF], where the time measurement stays constant whereas the resolution degrades with working distance.

Until that point, calculations have been performed for paraxial rays but if we consider all physical interpretations in term of plane wave phase manipulations, we can easily understand that it is possible to extend the analysis and the refocusing to lenses L 5 with higher numerical aperture (microscope objectives for example) or with spherical aberration. Instead of using paraxial filter H filter we need to use a filter which eliminates the phase shifts between the plane waves in the raw signal (to eliminate the second exponential of Eq. ( 5)), this filter can be calculated exactly if we know the aberrations of the lens or objective L 5 .

Experimental validation

The setup described on Figure 1 has been built and tested. We then have chosen a target made of reflective silica beads of 40 μm diameter behind a circular aperture of 1 mm diameter (Figure 4 a). The raw acquisition performed at a distance L = 1 cm is given in Figure 4 We now have to experimentally check the theoretical prediction of Eqs. ( 4) and ( 12) about the resolution of the raw and synthetic signals. In order to measure the resolution versus the defocus, we consider single silica bead (object Figure 4 a)) and we fit a section along the X direction with a Gaussian function. This method is possible because, relatively to the laser, a silica (spherical) bead behaves like a punctual reflector located at the geometric center of the bead. The different experimental resolutions versus the defocus (Figure 5) are then fitted with the theoretical predictions (RES R (δ) and RES SA (δ) in Figure 5 We note that the theory is verified in both raw and synthetic cases. Fitting the experimental data leads to r / √2 ≈ 9.5 μm.

4) Photometric budget of the synthetic imaging setup

After the analysis of the resolution, we are now exploring photometric properties and more particularly the evolution of the signal power with the defocusing distance L (see Figure 1, Figure 2 and Erreur ! Source du renvoi introuvable.). First it is important to explain what we call "signal power": it corresponds to the number of photons reinjected in the laser and so which participate to the image. LOFI signal corresponds to an electric field and as a result, the signal power is given by the square of the modulus of the signal. Once again, we make the approximation of paraxial rays but we consider a uniform distribution of laser intensity instead of a Gaussian one to simplify the problem. We perform the calculations with a Lambertian diffusive target of albedo ρ and of surface S. In order to have all the signal power concentrated in one pixel when we are focused on its plane (numerically or during the acquisition), the surface S is chosen smaller than S R (0) = π RES R (0) 2 (the object is not resolved). S R (L) is the surface of the beam at a distance L from the beam waist as shown in Erreur ! Source du renvoi introuvable. a). We first present the calculation for the raw acquisition with L = 0 already done in [START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF], then we make the analysis for L ≠ 0 and to conclude we experimentally verify the theoretical expectations.

Direct focused LOFI

First we consider the case of raw acquisition directly in the target plane. The retrodiffused power P R in the only bright pixel of the image is given by [START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF]:

) 0 ( ) ( ) ( ) 0 ( 2 0 2 0 R R R R R R R S NA S P NA S S P G E G L P            (15)
L R is the luminance and E R the illuminance in the focal image plane of L 5 . G R is the geometrical extent, P 0 is the laser power sent on the object. S R (0) and the numerical aperture NA are given by :

) 0 ( 2 2 ) ( 2 ) 0 ( ) 0 ( 2 2 R Z R R R S r RES NA r RES S R                (16)
We finally rewrite Eq. ( 15) in this form:

Synthetic LOFI

We now turn to the total power P SA (L) in the refocused image of a raw acquisition at a distance L ≠ 0. It is a bit more complicated since this image is built with several pixels N pixels (L) of the raw image due to the defocused scanning beam of surface S R (L) > S R (0); the signal in each of the pixels of the raw image have a power P RawSA (L). After numerical refocusing the power from all these N pixels (L) pixels is concentrated in a single synthetic pixel. We have:

) ( ) ( ) ( L N L P L P pixels RawSA SA  (18) With: 2 0 ) 0 ( ) ( ) ( ) ( ) ( ) ( ) ( L SS L S P L G L E L G L L L P R R SA SA SA SA RawSA         (19)

20

L SA (L) is the luminance, E SA (L) the illuminance in the plane of object 1 (Erreur ! Source du renvoi introuvable. a)) and G SA (L) is the geometrical extent of the laser spot. The number of pixels in the raw image participating in the synthetic bright pixel is:

) 0 ( ) ( ) ( R R pixels S L S L N  (20)
By combining Eq. ( 18), Eq. ( 19) and Eq. ( 20), we get:

2 0 2 0 ) 0 ( ) ( ) 0 ( ) ( ) ( ) ( ) ( L S P S L S L SS L S P L N L P L P R R R R pixels RawSA SA        (21)
Finally we expect a decrease of the signal power proportional to L². Making images deeper than working distance of lens L 5 has a cost in terms of signal power and then of Signal to Noise Ratio (SNR). However if we compare to [START_REF] Glastre | Sensitivity of synthetic aperture laser optical feedback imaging[END_REF], translational scanning shows a slower decrease of power (~1 / L 2 ) than rotational scanning (~ 1 / L 4 ). The quick decrease of P RawSA (L) with L ( 1/L 4 ) is linked to the fact that we use LOFI microscope outside its confocal zone; we can say that we have lost confocal advantage of LOFI. As a result in addition to the target signal attenuation, we have got another problem: multi-scattered photons are not rejected anymore compared to the signal of interest. However we have noticed that the increase of the background due to multiscattered photons can be neglected compared to the attenuation of ballistic photons which is the true limitation for the accessible deepness through the scattering medium. We can think that it is due to low reflectivity of fatty milk particules (we use diluted milk as scattering medium).

Comparison between the two imaging modalities and discussion on the limitations

We have shown the asymptotic dependence of P SA with L. We now predict a more quantitative relation between P SA and P R . By definition:

        ) ( ) 0 ( 2 ) 0 ( 4 ) 2 ( 4 ) 2 ( ) ( ) ( 2 2 2 2 2 2 2 L S S L S L r L r L L RES L S R R R R R       (22)
By combining Eq. ( 17), Eq. ( 21) and Eq. ( 22), we finally get the following simple relation:

L P R R R R R R R R SA           (23)
The ratio between two images acquired with and without defocusing is simply given by the ratio of surfaces of the beam in the two target planes of acquisition (S R (0) and S R (L)). In the same manner than with the resolution (but now considering photometric balance) we can ask what the parasitic signal introduced by object 2 located at a distance L - from the waist will be, if we want to image object 1 (Erreur ! Source du renvoi introuvable.) considering that the two objects have the same albedo ρ and surface S. Similarly to the discussion on the resolution we need to introduce a new parameter in P SA (L) which become P SA (L-δ,L), the power from the object 2 in one pixel (which is perturbating the image of object 1) when we numerically refocus in the plane of object 1. The image of object 2 is then reduced to one pixel. We have the following relation:

L P R R R R R R R R R R R SA R R R SA SA SA                 (24)
Because of the defocusing effect we have:

) , ( ) ( ) 0 ( ) , (         L L P S S L L P SA R R SA (25)
In the last equality of Eq. ( 24), the first ratio corresponds to the defocus over a distance δ (Erreur ! Source du renvoi introuvable. b)) and the second factor of the final expression in Eq. ( 24) comes from Eq. ( 23) and is due to the total number of photons reinjected. It is important to remark that in the situation of a raw acquisition focused on object 2 (L - = 0), even if we refocus on object 1, the power of the parasitic signal in one pixel from object 2 in the synthetic image, is at the same level that the total power from object 1 (concentrated in only one pixel as we numerically refocus on it). As a result, in that situation, we are not able to separate object 2 from object 1 despite object 2 is defocused in the synthetic image; this is due to the excessive amount of power reinjected by object 2 during raw acquisition. Nevertheless, this situation is improved when both object 1 and 2 are acquired far from the waist (L is increased in Erreur ! Source du renvoi introuvable. a)). Indeed for high values of L (L >> δ), Eq. ( 24) is simplified in S R (δ) / S R (0) (> 1). However we showed in Eq. ( 21) that the total power reinjected by an object located at a distance L is degrading proportionally to L². As a result in order to have both a good separation between object 1 and 2 and a globally sufficient SNR, we must find a compromise for L.

Experimental validation

To confirm the theoretical predictions of the previous section, we have experimentally measured the power in the image of the previous object made with silica beads (Figure 4 a)). What we call the total power corresponds to the sum of the square modulus of the signal coming from all pixels of raw (Figure 4 b)) or refocused image (Figure 4 c)). Indeed, according to Parseval's theorem and to Eq. ( 10) where the filter transfer function has a modulus equal to unity, the power in raw and refocused image is the same. We have experimentally measured the power in the signal versus the defocus of the raw acquisition, these points have then been fitted with the theoretical curve given by Eq. ( 3) and [START_REF] Lacot | Comparative study of autodyne and heterodyne laser interferometry for imaging[END_REF]. These results are presented in Figure 6. We can consider that our theoretical predictions describe relatively well the experimental results.

The main discrepancy arises for small defocus values, where there is a difference of a factor ~ 10. This could be explained by several approximations that have been made: we have neglected the small astigmatism of the laser beam that is important for low values of L and the nonlambertian nature of silica beads in the target.

5) Conclusion and future work

We have made the demonstration of a simple, self-aligned and very sensitive imaging system able to work beyond the working distance of an objective lens, which is particularly useful to make resolved image through deep turbid media. Theses performances have been reached by combining the use of the LOFI technology which gives the sensitivity and the self-alignment, with the original 2D translational scanning associated to aperture synthesis which keeps the resolution constant beyond the usual lens working distance. Thank to our simple 2D translational scanning with galvanometric mirrors, we realized, to our knowledge, the first imaging system based on synthetic aperture numerical treatment with a fixed target and an isotropic resolution.

Concerning the resolution, we have shown that performing a numerical refocusing enables to transform the initial real objective or lens into an equivalent objective with a higher focal length (thus a longer working distance) while keeping the initial numerical aperture (and so the resolution). But we demonstrated also that this advantage is at the cost of an increased acquisition time and data storage (proportional to L²) and reduced photometric performances (proportional to 1 / L²). We have characterized the 3D PSF of our synthetic microscope with 2D images (silica beads). In a future work, we plan to investigate real 3D imaging. Regarding the photometric performances, we explored the signal power reinjected versus the acquisition defocus and the influence of diffusers in different planes when we are numerically focusing in another plane. We also have to present the influence of all noises and perturbations on our final image in order to get the final accessible SNR; this will be presented in a companion paper.

Figure 1 :

 1 Figure 1 : Experimental setup of the synthetic aperture LOFI-based imaging system. The laser is a cw Nd:YVO 4 microchip collimated by lens L 1 . A beam splitter sends 10% of the beam on a photodiode connected to a lockin amplifier which give access to the amplitude and phase of the signal. The frequency shifter is made of two acousto-optic modulators which diffract respectively in orders 1 and -1 and gives a net frequency shift of F e / 2 = 1.5 MHz. X-Y plane is scanned (see Figure 2) by galvanometric mirrors M X (scan in the X direction) and M Y (scan in the Y direction) conjugated by a telescope made by lenses L 3 and L 4 . f 3 , f 4 and f 5 are the focal lengths of lenses L 3 , L 4 and L 5 . α X and α Y are the angular positions of galvanometric mirrors M X and M Y .

Figure 2 :

 2 Figure 2 : Scanning mechanism of the setup of Figure 1 after lens L 4 . The collimated laser beam is focused by the final imaging lens L 5 in its focal image plane with a waist radius r. Mirror M X ' (image of M X through telescope, see Figure 1) and M Y are in the focal object plane of imaging lens L 5 , which implies a displacement of the beam waist in the image focal plane of L 5 . The laser beam presents a slight misalignment with L 5 optical axis and rotation axis of galvanometric mirror of d X in X direction and d Y in the Y direction. α X and α Y are the angular position of galvanometric mirrors M X ' and M Y . When α X = α Y = 0, the center of the beam is passing through the target (convention). x and y are the position of the waist in the focal image plane of L 5 . θ X and θ Y are the angles of the center of the beam relative to the direction normal to the focal image plane of L 5 (≠ 0 due to d X and d Y) . The target at a position (Lθ X , Lθ Y ) is scanned by a defocused beam at a distance L from the beam waist.

Figure 3 :

 3 Figure 3 : Comparison in terms of resolution of the a) : Raw acquisition and b) : after numerical refocusing in the plane of object 1. δ is the distance between two objects of interest. S R (L) = π RES R (L)² is the surface of the beam at a distance L from the beam waist and S SA (δ) = π RES SA (δ)² is the surface of the beam at a distance δ from the plane of refocusing (here plane of object 1).

  b), this image is enlarged compared to the object because of the defocusing; Figure 4 c) gives the modulus of its Fourier transform and Figure 4 d) the numerically refocused image. We successfully pass from a defocused image with a resolution RES R (L = 1 cm) = 180 μm to a numerically refocused image with a resolution RES SA (0) = RES R (0) = 9.5 μm. The optimal refocusing distance was determined by using the detection criteria described by Dubois et al. [0]. The acquisition time for this 512*512 pixels image was approximately one minute with an integration time of T = 50 μs by pixel.

Figure 4 :

 4 Figure 4 : example of synthetic aperture LOFI. a) Object under microscope. It is made of reflective silica beads of 40 μm diameter behind a circular aperture of 1 mm diameter. The bright field transmission image is made through a Zeiss microscope objective with a magnification of 10 and a 0.25 numerical aperture (focal length of 20 mm). b) : Raw image of the object with LOFI setup r = 13.5 μm, L = 1 cm, 512*512 pixels. The beam size on the target plane is equal to 180 μm: beads are not resolved. c) : Recorded image in the space frequency domain. d) : Image after numerical refocusing, a resolution RES R (0) = RES SA (0) = r / √2 = 9.5 μm is expected and verified experimentally.

  a) and Figure5 b)) respectively.

Figure 5 :

 5 Figure 5 : Evolution of the resolution in the X direction with the defocus δ, fitted by the theoretical expression of RES R (δ). The resolution is calculated by fitting a section along X of the image of one bead in the image of Figure 4 (which is the PSF since the bead can be considered as a punctual scatterer). a) : Raw case, the defocus correspond to the L = δ in Figure 1 and Figure 2. b) Synthetic case, the defocus corresponds to the difference between the parameter L during the acquisition and the numerical retro propagation distance L' : δ = L -L' (see Erreur ! Source du renvoi introuvable. b)).

Figure 6 :

 6 Figure 6 : Evolution of the signal power reflected by the object of Figure 4 a) versus the defocus L (see Erreur ! Source du renvoi introuvable. a)). Positive defocus corresponds to an increase of the distance between the object and the lens L 5 . The vertical axis has an arbitrary normalized unit.


Benjamin Bach

Es P R I T Z E R

Interactive Random Graph Generation with Evolutionary Algorithms

This paper introduces an interactive system called Graph-Cuisine that lets users steer an Evolutionary Algorithm (EA) to create random graphs that match user-specified measures. Generating random graphs with particular characteristics is crucial for evaluating graph algorithms, layouts and visualization techniques. Current random graph generators provide limited control of the final characteristics of the graphs they generate. The situation is even harder when one wants to generate random graphs similar to a given one, all-in-all leading to a long iterative process that involves several steps of random graph generation, parameter changes, and visual inspection. Our system follows an approach based on interactive evolutionary computation. Fitting generator parameters to create graphs with pre-defined measures is an optimization problem, while assessing the quality of the resulting graphs often involves human subjective judgment. In this paper we describe the graph generation process from a user's perspective, provide details about our evolutionary algorithm, and demonstrate how GraphCuisine is employed to generate graphs that mimic a given real-world network. An interactive demo of GraphCuisine can be found on our website http://www.aviz.fr/Research/Graphcuisine.

In this paper we introduce GraphCuisine,anovelinteractivesystemthatlets users steer an Evolutionary Algorithm (EA) to create random graphs that match user-specified properties. Our system provides three different approaches to the interactive generation of random graphs: (a) explicitly set desired graph measures (e. g., density of 5%), (b) select "good" exemplars from a set of generated graphs for further evolution, and (c) extract measures from a sample graph while still including the possibility of user control. To allow for these different modes of interactive random graph generation, GraphCuisine consists of an interactive interface and a graph generation model that combines different generators and optimizes their parameters with an EA. Graphs are created by traversing a pipeline of generators, each acting on the output of the previous one by adding or removing nodes and edges in very specific ways, according to each generator's input parameters. The EA then attempts to find sets of parameters that produce graphs that best match the user-defined properties.

GraphCuisine has been designed with three main scenarios in mind:

1. Generate graphs with specific graph measures. When designing a new technique or algorithm, being able to evaluate its behavior on graphs with different topological properties (e. g., density, diameter, clustering coefficient, etc.) is essential and almost impossible with current generators. 2. Generate graphs that resemble a target graph, not knowing the measures that contribute to its structure. Testing how appropriate an algorithm is can be difficult with only a few samples of real graphs available. Selecting the measures that best represent theses a m p l e s ,h o w e v e r ,i sn o tt r i v i a la n d requires a combination of visualization, interaction and human judgment. 3. Anonymize a specific graph by generating a graph with similar or identical measures. Collaboration with other researchers and specialists can be impossible if a graph contains confidential information (e. g., e-mail exchanges between employees, or telephone calls between possible suspects). As such, creating graphs that are as similar as possible to these in terms of their topological characteristics facilitates collaboration.

This paper is structured as follows: after reviewing related work (Section 2), with a focus on graph generation and network evolution, we present an overview of GraphCuisine from a user's perspective (Section 3). We then describe the graph generation and evaluation processes in detail (Section 4), followed by a usage scenario (Section 5) and a final section on conclusions and future work (Section 6).

2R e l a t e d W o r k

Random Graph Generation. Generators have been developed using different techniques to construct graphs with varying characteristics. Preferential attachment generators [START_REF] Erdös | On Random Graphs[END_REF][START_REF] Waxman | Routing of Multipoint Connections[END_REF][START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF][START_REF] Medina | On the Origin of Power Laws in Internet Topologies[END_REF][START_REF] Aiello | A Random Graph Model for Power Law Graphs[END_REF][START_REF] Pandurangan | Using PageRank to Characterize Web Structure[END_REF] add nodes to a network and connect each node with a particular probability to existing nodes, aiming at graphs with a power law node-degree distribution. Rewiring generators [START_REF] Watts | Collective Dynamics of 'Small-World' Networks[END_REF][START_REF] Kleinberg | Navigation in a Small World -It is easier to find Short Chains between Points in some Networks than Others[END_REF][START_REF] Eppstein | A Steady State Model for Graph Power Laws[END_REF] reconnect existing edges, being mostly used to create small-world networks. Some of them initially place all nodes in a 2D space and consider spatial distances when calculating the probability of creating an edge between each pair [START_REF] Watts | Collective Dynamics of 'Small-World' Networks[END_REF][START_REF] Kleinberg | Navigation in a Small World -It is easier to find Short Chains between Points in some Networks than Others[END_REF]. Structural generators aim at obtaining more realistic graphs by first creating higher-level structures, such as clusters, and recursively modeling details [START_REF] Doar | A better Model for Generating Test Networks[END_REF][START_REF] Calvert | Modeling Internet Topology[END_REF].

Techniques that treat graph generation as a global optimization problem [START_REF] Frank | Markov Graphs[END_REF][START_REF] Carlson | Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems[END_REF] or using local forces between nodes and edges by evolving the network [START_REF] Fabrikant | Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet[END_REF][START_REF] Berger | Competition-Induced Preferential Attachment[END_REF] have also been explored. Their goal is to circumvent the problem of generators producing networks that favor a few characteristics while disregarding all others. As an example for optimization techniques, R-MAT [START_REF] Chakrabarti | R-MAT: A Recursive Model for Graph Mining[END_REF] tries to model real graphs by recursively partitioning an adjacency matrix into cells and distributing edges within them with unequal probabilities. R-MAT features several graph characteristics and comes with an input parameter fitting function, but generates only one graph at a time and only matches a few properties.

Evolutionary Algorithms (EAs) are stochastic optimization heuristics that copy, in an abstract manner, the principles of natural evolution that let a population of individuals be adapted to its environment [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]. An EA treats potential solutions like a population of individuals that live, fight, and reproduce. Natural pressure from the environment is replaced by an abstract optimization pressure. Individuals representing the best solutions are reproduced and new solutions emerge by variation schemes known as genetic operators.I na n a l o g yt on a t u r e , variations are mutation to slightly change gene values, and crossover to combine genes from two parent solutions. A fitness function,whichcomputesafitness value to assess how good each solution is, is optimized by the EA.

Evolutionary optimization techniques are particularly well suited to complex problems where classical methods fail due to the irregularity of the function to be optimized or to the complexity of the search space. In this article, we deal with an interactive evolutionary algorithm (IEA) as it is applied to the optimization of a quantity that is partially specified by the user via an interactive interface.

EAs have been used in the field of Neuroevolution to evolve the topology and edge weights of neural networks in their creation and learning phase. Neuroevolution is concerned with two main problems: (1) how to encode neural networks in genes, and (2) how to design effective crossover operators that do not destroy desired sub-structures in the networks. Two common approaches are used: Direct Encoding,w h i c hr e q u i r e st h ed e s i g no fs p ecific genetic operators to ensure efficient exploration capabilities of the algorithm [START_REF] Stanley | Evolving Neural Networks through Augmenting Top ologies[END_REF], and Grammatical Encoding,w h i c hr e p r e s e n t st h en e t w o r k si nag e n e r a t i v ew a y[ 1 6 , 1 5 , 2 1 ] .R a t h e rt h e n encoding the graph topology in the chromosome, graph grammar based transformation rules are encoded and evolved. In GraphCuisine we take an approach similar to the latter, but different in that while Neuroevolution aims at optimizing and reproducing one single network that is in turn judged according to its functionality, we are interested in generating a wide diversity of solutions to give more options for human judgment.

UIs for Data Generation and Analysis. Few approaches exist that tightly involve the user in the data generation process. Wong et al. [START_REF] Wong | Generating Graphs for Visual Analytics through Interactive Sketching[END_REF] let users sketch graphs on adjacency matrices, adapting pixel-based drawing techniques to draw the edges. A node-link representation is provided, but only matrices are used for drawing. Except for drawing cliques, matrices make it hard to predict how a node-link representation of the final graph would look like, with its measures also being almost impossible to control. Albuquerque et al. [START_REF] Albuquerque | Synthetic Generation of High-Dimensional Datasets[END_REF] propose generators and sketching for 1D, 2D and 3D scatterplots to generate multivariate data sets. In general, such sketching interfaces do not create diverse data sets, but provide only one particular solution at a time. Biedl et al. [START_REF] Biedl | Graph Multidrawing: Finding Nice Drawings Without Defining Nice[END_REF] provide the user with drawing of different layouts for the same graph. The user can chose layouts he like and the system tries to interfere about the users layout preferences. In GraphCuisine the user can chose between multiple graphs, from which his preferences about graphs are interfered.

GraphCuisine

GraphCuisine is a random graph generator for undirected graphs by evolving apopulationofgraphsencodedaschromosomes,w h i c hw orkas"reci pes"t ogenerate graphs. A graph is generated from a chromosome by passing a pipeline of generators, each reading its appropriate input parameters from the chromosome and modifying the graph by systematically adding or removing nodes and edges. GraphCuisine currently implements 12 graph generators, each using 2-5 input parameters and each creating basic network structures such as stars, clusters and several types of "noise". The target graph towards which the generated graphs are evolved is encoded as a set of weighted measures such as node count, density and clustering coefficient. The fitness of a generated graph is calculated as the distance between the measures of the generated graph and the target measures (Section 4.2).

Encoding the genome as a set of parameters for generators has two major advantages: (1) the genome size for all graphs remains constant and independent of the graph size, and (2) the measures used to optimize the graphs are independent from the number and parameters of the simple generators, allowing new measures and generators to be added easily. Having constant-size genomes facilitates crossover between chromosomes, which in turn increases the diversity of generated solutions.

The interface of GraphCuisine,s e e ni nF i g .1 ,i sm a d eu po ffi v em a j o r parts. The population view (Fig. 1(a)) shows 12 representative graphs from the current population, with users being able to switch between adjacency matrix and node-link representations. Users can select graphs, with the current selection being displayed enlarged in the detail view (Fig. 1(b)). If users decide to extract target measures from an imported graph, the graph is shown in the dataset view (Fig. 1)c)). The measures view (Fig. 1(d)) displays the distribution of measures in the whole population as an interactive parallel coordinates plot, with the polylines being the current population's graphs, and the vertical axes representing the value range of each measure as defined by the user. Each measure axis is drawn over a color-coded rectangle whose width represents the weight of its respective measure in the fitness computation (Section 4.2). The white adjustable circles seen on each axis indicate the desired target values for each measure, while horizontal ticks show the desired minimal and maximal values. On the right of the gray degree-axis in Fig. 1(d) a vertical line chart shows the distribution of node degrees for each graph. All values can be adjusted interactively by clickand-dragging. Below the measures view, the measures table (Fig. 1(e)) explicitly shows the values of all measures of each representative graph. Views are coordinated with brushing-and-linking: moving the mouse over a polyline highlights the corresponding graph in the population and table views, and vice-versa.

To start generating graphs, users can cho ose among the following options:

Random initialization : The population is created from a random set of generator parameters for each chromosome and random target measures, providing a base for a more exploratory generation. Set target measures directly : The values for the desired measures can be set interactively by adapting minimal, maximal, and target values as well as the measure weights directly in the measure view. Graph templates: Templates are predefined sets ofg e n e r a t o rp a r a m e t e r sa n d measures assembled to create graphs with particular characteristics such as small-sized, medium-sized or large-sized, dense or sparse, following a power law degree distribution, or being a small-world network. Templates are chosen from a menu where complementary templates can be selected at a time. New templates can be defined by the user for later reuse. Based on a template, an initial population is created. Load an existing graph : To mimic an existing graph, the graph is imp orted and shown in the dataset view (Fig. 1(c)). Its measures are computed, displayed in the measures view and serve as target values for the evolution. Users can modify the measures and their weights immediately or at any time during evolution; they can also be reset to the value of the loaded graph.

Generating graphs with GraphCuisine begins with the initialization and selection of the target measures, after which the evolution of generator parameters is started. An initial machine solution is created by optimizing the initial population of graphs to fit the target values. After five generations, 12 representative graphs are shown in the population view and their measures are shown in the table and the measures view. The heuristic used to select the representative graphs consists of selecting the three fittest graphs and nine at random. After this step, the measures view is updated to display the values of the entire population, and green bars appear on each graph in the population view. The saturation of the bars indicate the fitness of the graphs and is updated automatically whenever target measures are changed in the measures view so as to keep users aware of which graphs are considered similar by the system with the settings that are being used at that moment.

As an alternative to setting target measure values in the measures view manually, users can select graphs they consider good directly from the population view by clicking on them. Multiple graphs can be selected and the target values are updated to reflect the chosen graphs. Measure weights are updated according to the variance of their respective values in the selected graphs-the more a particular measure differs, the lower it is weighted and vice-versa (Section 4.3). The evolution can then run for another cycle of five generations with the new target values being taken into account. The number of generations and other parameters of the EA can be adjusted by the user at any time, allowing for control of evolution behavior (population size, generations, elitism, etc.). Disabling generators prevents the graph from containing particular characteristics and setting their parameters directly gives additional freedom in specifying graphs. Since GraphCuisine's fitness value reflects the difference between the measures of each graph and the target values, a lower value means a higher fitness. Behavior and convergence of the fitness of the whole population is monitored in the chart shown in Fig. 2(a). It shows the minimal (the best) and the average fitness in all generations using a logarithmic scale. In order to avoid previous graphs being lost during the evolution process, GraphCuisine can be reset to any generation to try alternative evolutions. Additionally, the chromosome of any generated graph can be saved as template to initialize new populations later on.

4G e n e r a t i o n a n d E v o l u t i o n

As explained in the previous section, each individual in GraphCuisine's EA corresponds to a graph. It is encoded in a generative way, that is its chromosome which fully specifies a sequence of generators and their parameters. The creation of a graph from a chromosome and the evaluation of its fitness is done in four steps as illustrated in Fig. 3. We implemented two typ es of generators in GraphCuisine:m o t i fg e n e r ators and noise generators. Motif generators create topological patterns, such as clusters, stars, paths, and cycles. The parameters of these generators specify specific motif properties, such as the degree of a star's central node, and how many instances of it should be created 1 . Noise generators are applied to break regularities, making structures more varied and less predictable by adding or removing nodes and edges. Nodes and edges can be inserted randomly with different node degree distributions: uniform, power law, logarithmic or exponential. Nodes and edges to be removed are either chosen randomly or according to some criterion, such as eliminating non-connected nodes. These two steps are conceptually similar to some structural generators but the motifs and noise we produce are more varied and generalized.

Parameters for noise generators define, for instance, how many nodes or edges the graph should have and help control the approximate size of the graph. More specific properties exist, such as the probability of connecting two given nodes by an edge. If applied in a different order, the same noise generators with the same parameters will produce different graphs.

Chromosome Structure: Encoding of a Graph

Each chromosome is divided into three blocks. The first is a single gene with an integer value, which serves as a seed for the random number generator that ensures consistent random values for the generation. The second and third blocks stand for the motif and noise generators, respectively. They are both represented in the same way: the first gene contains a Boolean value indicating whether the corresponding generator is active or not and the second gene contains a value specifying the execution order of the generator in the creation pipeline (Fig. 3). The remaining genes of each generator contain their input parameters.

Fitness Function: Quality Assessment of an Individual

The computation of the fitness of each chromosome/graph is based on the set of target graph measures M = {m i |m i ∈ R,i ∈ [0,n]},w i t ht o l e r a n c eb o u n d s m i ∈ [min i , max i ],a n di m p o r t a n c ew e i g h t sw i ∈ [0, 1].F o rag r a p hG k each measure in M is computed as: M k =( m 0,k ,...,m n,k ) where m i,k is the i th graph measure. The fitness(G k ) ∈ R + of the graph G k is its distance to the optimal solution, i. e., the following weighted sum:

fitness(G k )= i∈[0,n] w i * m i -m i,k max i -min i
Normalization is necessary to weight and sum up measures equally. Currently, GraphCuisine supports the following measures: node amount, edge amount, density, graph diameter, number of clusters, number of connected components, average clustering coefficient,a n daverage node degree. Some of the measures such as node amount, edge amount and density, are interdependent so that if the user restricts one measure, others are restricted automatically. It requires more investigation to provide appropriate interface components to communicate and manage such dependencies.

Interactive Evolution

As mentioned in Section 3, the population view allows selecting good solutions by visual inspection. This feature is based on the assumption that visual node link or matrix representations allow humans to compare graphs and match some of their visible structure effectively. When selecting multiple graphs S with G k ∈ S, GraphCuisine tries to infer what graph characteristics are important to the user. The target valueforeachmeasurem i is taken to be the average of measures of all selected graphs: m i = m i,k .T h ew e i g h t sw i are adjusted to reflect the diversity or similarity of the single graph measures using the standard deviation of the normalized graph measures m i,k :

w i = stddev(m i,0 ,...,m i,s ) with m i,k = m i -m i,k max i -min i
When users change the target measures or their weights, we increased the mutation rate for one generation in order to yield a larger variety of new solutions.

Implementation

GraphCuisine is implemented in Java using the JGAP library2 .B yd e f a u l t , the graph generation process begins with a randomly generated population of 50 individuals, which then is evolved for five generations. Population size and generations were chosen to keep a balance between population diversity and acceptable running time for each cycle, an important issue for interactive applications. In order not to lose good solutions over time, we guarantee that each generation keeps the 30% fittest individuals from the previous generation (elitism). Fig. 2(b) illustrates how one generation is evolved; a set of fit graphs is selected (parents )t oc r e a t en e wi n d i v i d u a l sb yt h ea p p l i c a t i o no ft h eg e n e t i c operators. The components of the evolutionary algorithm are the following:

-A tournament selection of size five, meaning that five individuals are randomly chosen with uniform probability, with the best one being kept as a parent. The process is repeated twice to select two parents for a crossover. -Ao n e -p o i n tc r o s s o v e rthat creates two offsprings by swapping all the genes of the parents that come after a randomly selected position in the genome. -As i m p l er a n d o mm ut a t i o nthat takes 5% of the genes of each individual and replaces them with random values. Crossover and mutation are applied in a cascade. First new individuals are created by applying a crossover, then all new individuals undergo a mutation that alters 5% of their genes. The configuration of GraphCuisine's EA is based on the specific problem we approach and on results obtained from experimentation with the different parameters.

Performance of the generation and evaluation process is essentially limited by the computation time for the graph measures (in particular those related to clusters), with creation, mutation, and crossover times being negligible. Measure weights can be set to 0 which accelerates the process by not computing this measure.

Adding new measures or generators to GraphCuisine consists of adding the new implementations and update the user interface. Measures must be added to the fitness function, while new generators require that their parameters be included in the chromosome structure. Integrating new measures into the interface amounts to adding columns to the table and dimensions to the parallel coordinates plot.

5E x a m p l e S c e n a r i o : A n o n y m i z i n g a N e t w o r k

Imagine an HIV contamination network must be anonymized while keeping the characteristic structures present so that it can be given to students in epidemiology for analyses. By importing the network in GraphCuisine,i t sm e a s u r e s are calculated and automatically set as target measures. The graph population is randomly initialized to guarantee diversity. After a first evolution step of five generations, the representative graphs are shown in the population view and the measures table. The parallel coordinates in the measures view shows that the distribution of measure values for all the 50 graphs in the current population has already converged well towards the target values.

The user can then decide to increase the graph size and, proportionally, the number of clusters. This is done by setting the desired size and the number of clusters in the measures view. Since these two seem to be the most important measures for this evolution, the user slightly increases their weight by varying the width of the colored rectangles in the parallel coordinates plot. After another evolution cycle, the graphs have grown and show a proportionally higher number of clusters. The degree of optimization and similarity between the generated graphs and the original one can be controlled by adjusting the number of generations in the evolution step.

If desired, the user can continue to refine the graphs, by, for example, selecting their favorite representative graphs from the population view and running another evolution cycle to obtain graphs similar to the ones they chose. Since selecting graphs causes the target measures to reflect the measures of the selection, they might slightly diverge from those of the imported graph. When a desired result has been reached, generated graphs can then be exported. Fig. 1 shows the imported HIV network (right), the generated graphs (left), as well as ap a r t i c u l a rs e l e c t e dg r a p h( c e n t e r )w i t hits measures highlighted in red in the measures view. The fitness view (Fig. 2(a)) shows the convergence of the population fitness declining, except where the target measures have been changed by the user. The pure evolution time with 50 individuals for 20 generations was 6.52 minutes.

6C o n c l u s i o n a n d F u t u r e W o r k

This article introduces GraphCuisine,as y s t e mt h a tu s e sE v o l u t i o n a r yA l g orithms to generate random graphs according to user-specified graph measures. We enco de graphs using a generative mo del where several generators are run in sequence, each taking as input a set of parameters. We store the parameters and execution order in the genome of the EA engine and evolve it to produce graphs matching the set of target measures.

GraphCuisine's parameter encoding has several advantages for our specific goal compared to directly encoding graphs in the genome: it is efficient, both in space and computation time. One genome can potentially generate an unlimited number of similar random graphs. Changing the parameters through mutation generates more diversity than direct encoding. Diversity, in turn, leads to faster convergence of the evolution and can introduce interesting unexpected results that still match the constraints.

From a practical p ersp ective, the computation of some of the measures is expensive but cannot be avoided if they play a role in the fitness function. However, although we designed GraphCuisine for interactive manipulation, it can run for as many generations as needed without human intervention, freeing users from the trials and errors that are usually necessary to generate graphs with specific characteristics. Furthermore, simple strategies can be used to first generate smaller graphs with the requiredc h a r a c t e r i s t i c s ,a n dt h e ng r o wt h e m while assuring that their measures still match the requirements.

GraphCuisine's implementation includes a small set of well-defined generators and measures that is easily extensible, with new generators and measures being investigated and considered for future inclusion. One extension we are working on is to express and match measure distributions such as power law node degrees. The EA would require little change to support this, but the interface would need more work to effectively let the user specify the distributions.

In our experience GraphCuisine's EA converges rapidly. However, we want to conduct more formal studies to better understand the behavior of our generators compared to existing ones in terms of convergence and expressive power. Such a formal study would also help to balance speed of convergence of the evolution against diversity in the population. In addition, we will conduct usability evaluations to assess and potentially improve interaction in terms of user control and expressive power on the generation process.

Fig. 1 .

 1 Fig. 1. User Interface of GraphCuisine showing (a) the population view,d i s p l a y i n g representative graphs of the current population; (b) the detail view of the selected graph; (c) an imported graph in the dataset view,( d )ap a r a l l e lc o o r d i n a t e sp l o ti n the measurement view showing the distribution of measures in the population, and (e) the measures table with an entry for each representative graphs. In the measures view, the target measures are indicated by the position of the white markers, while black polylines line show the measures of the selected graph.

Fig. 2 .

 2 Fig. 2. (a) Fitness values on a logarithmic scale. Better fitness values are closer to 0. The blue line shows the fitness of the fittest individual, while black shows the population mean. Salient vertical lines indicate generations that have been displayed to (and possibly changed by) the user. Brusque upwards changes in the blue curve indicate that the user has changed the target measures, leading to decreased fitness of the current population. (b) Evolution process for one generation in GraphCuisine.

For a complete list of generators and their parameters, see our http://www.aviz.fr/Research/Graphcuisine

http://jgap.sourceforge.net