Tianjun Li

Lorène Champougny

Ludovic Bellon

Dynamic stiffness of the contact between a carbon nanotube and a flat substrate in a peeling geometry

We study the physics of adhesion and the contact mechanics at the nanoscale with a peeling experiment of a carbon nanotube on a flat substrate. Using an interferometric atomic force microscope and an extended force modulation protocol, we investigate the frequency response of the stiffness of the nano-contact from DC to 20 kHz. We show that this dynamic stiffness is only weakly frequency dependent, increasing by a factor 2 when the frequency grows by 3 orders of magnitude. Such behavior may be the signature of amorphous relaxations during the mechanical solicitation at the nano-scale.

I. INTRODUCTION

At the nanometer scale, the interaction between objects can be quite different from what expected at the macroscopic level: the large surface to volume ratio amplifies the effects of some phenomena, such as the Van der Waals forces. Adhesion is therefore ubiquitous, and impacts on the mechanical interaction between nanoobjects. It has for instance a strong influence in atomic force microscopy (AFM) 1 , where a nanometric tip is used to measure the topography by scanning a surface at constant interaction. It also drives the behavior of nanoparticules, nano-wires or nano-tubes in contact with a substrate 2 . Quantifying adhesion processes is thus important to understand the physics in the nano-world.

Atomic force microscopy, thanks to its ability to apply and measure forces and displacements in the nN and nm range respectively, is a first-choice tool to explore nano-mechanics. For example, the AFM has been successfully used to characterize the adhesion of one dimensional nano-object, such as carbon nanotubes [3][4][5][6] . In particular, in peeling experiments, one measures the force while the nanotube is pulled from a flat substrate [7][8][9][10][11][12][13][14] . The force versus distance curve displays a signature specific to this peeling process, and can be used to extract the energy of adhesion between the nano-object and the surface. Scanning electron microscopy has also been used to substantiate those conclusions by confirming the geometry of the contact during peeling 10,11,15,16 .

These peeling experiments are however restricted to the quasi-static mechanical behavior of the contact, since the time scales probed are of the order 1 s. In this article, we explore the dynamic response of the contact, which can be quite different. Indeed, in previous works 13,14 , we showed that at frequencies higher than 10 kHz, the adhesion processes can be considered as frozen: the nanotube a) Electronic mail: ludovic.bellon@ens-lyon.fr has no time to adhere to (or detach from) the substrate, leading to a dynamic stiffness which is greater than the static one. We are therefore interested in probing the intermediate frequency range: does any characteristic time scale govern this dynamic behavior ? What are the physical processes associated to this "freezing" of the adhesion ?

To explore this frequency range, we will extend one mode of operation of AFM, generally referred to as force modulation 17 . In this mode, one adds a small amplitude sinusoidal oscillation to modulate the force while the tip is in contact with the sample. Using an adequate model of the rheological behavior of the sample, the response of the AFM probe at this frequency leads to the ability of mapping rheological properties at the nanometer scale. In our case, such force modulation is tricky in two aspects. First, the amplitude of the modulation has to be extremely small to probe the linear response of the nanotube. Second, several frequencies should be measured at the same time, since the precise contact configuration can vary between successive experiments. We will introduce a protocol to address those two points, and measure the frequency behavior of the dynamic stiffness of the contact.

This article is organized as follows: in part II, we first describe the experiment and the quasi-static force curve measurements, leading to the characterization of the adhesion energy between an individual carbon nanotube and a substrate of mica. In part III, we study the dynamic stiffness, either using a thermal noise analysis of the AFM probe during the peeling process, or performing extended force modulation experiments. In the last part, we discuss the experimental results and suggest some physical interpretation of the weak frequency dependence of the dynamic stiffness of the contact.

II. QUASI-STATIC FORCE MEASUREMENTS

The nanotubes are grown directly 18 at the tip apex of AFM probes by Chemical Vapor Deposition (CVD): the bare silicon cantilevers are fully dipped into the catalyst solution, then gently dried in a nitrogen flux before being placed in the furnace. CNTs grow everywhere on the cantilever, and around 1 in 3 cantilevers has a CNT at the tip 14 . A typical sample is shown by the SEM (Scanning Electron Microscopy) image of figure 1(a). Growth parameters are tuned to produce mainly single wall CNTs, but the effective sample may slightly differ from this goal. It may consist of a bundle of a few single wall nanotubes, carry a significant amount of amorphous carbon 19 , or be a few-wall nanotube. No TEM (Transmission Electron Microscopy) images are available for our samples, since they tend to break during extensive testing, and thus no a posteriori imaging can be performed.

In the experiments, the nanotube is pushed against a flat mica substrate, as shown in the schematic diagram of figure 1(b). The translation of the substrate is performed with a piezo translation platform (Physik Instrumente -PI P527.3) operated in closed loop, featuring an accuracy of 0.3 nm rms thanks to its embedded capacitive sensor. We measure the deflection d of the AFM cantilever with a home-made highly sensitive quadrature phase differential interferometer, which detects the optical path difference between the sensing beam (focused on the cantilever tip) and the reference beam (focused on the static base) [20][21][22] -see sketch in figure 1 With both z s and d being calibrated, using a proper definition of the origins (z c0 , z s0 ) we can compute at any time the compression of the nanotube:

z c = z s -d cos θ (1)
where θ = 15 • accounts for the inclination of the cantilever with respect to the substrate. With the hypothesis that the horizontal forces acting on the nanotube are negligible, we can also compute the vertical force acting on the nanotube 13,14 :

F = - k 0 cos θ d (2)
with k 0 the static stiffness of the AFM cantilever (calibrated from its thermal noise 23 ). Using compression instead of sample position allows us to take into account the compliance of the cantilever, thus to focus on the nanotube properties only in the force versus compression curves. In the following, we will drop cos θ when writing the equations to ease their reading (thus taking θ = 0 • ), but taking into account this small correction is straightforward and has been done during the data analysis. • inclination of the AFM cantilever with the substrate), part of the nanotube adheres to the surface due to Van der Waals interactions. The shape of the CNT is fixed by an equilibrium between the adhesion of the part in contact and the bending of the free standing part of the nanotube. From the measurement of the AFM cantilever deflection d (using differential interferometry 20 ) and sample position zs, the force F acting on the nanotube and its compression zc can be recorded. (c) The system is modeled by the effective mass m of the cantilever being connected to two springs: the cantilever (spring constant k0) attached to the static reference, and the nanotube in contact with the substrate (effective stiffness kc). The sketch corresponds to the simplified equation where θ = 0 • and the origins are defined such as zc0 = zs0 = 0.

approach and retraction, with a plateau-like behavior of the force during retraction: this is the signature of an adhesion and peeling process of the nanotube on the surface 13,14 . The steep evolution at the largest compression corresponds to a hard contact between the AFM tip and the substrate, while the jumps between different plateaus during retraction are the signatures of defects in the nanotube. The shape of this force curve is robust to a few hundred cycles, showing an excellent reproducibility for different landing positions on the mica substrate. Other nanotubes present very similar features, except for the position of defects along their length which is naturally A strong hysteresis, due to the adhesion can be noted between approach (blue) and retraction (yellow/red). Plateaus in the force curve are characteristic of a peeling process 13 . (b) The ramp is designed to probe specifically the peeling configuration corresponding to compressions zc between 160 nm and 260 nm during retraction. (c) As shown by the PSD of the deflection S d , the thermal noise of the cantilever allows the measurement of the additional stiffness due to the contact: the resonant frequency is higher (red) when the nanotube is in contact with the substrate than before contact (blue).

S d (nm 2 /Hz) Frequency f (kHz) Force F (nN) Compression z c (nm) Time t (s) z s (nm) (a) (c) (b)
specific to each sample.

We focus our attention here on the longest force plateau during retraction of this nanotube, for compressions z c ranging between 160 nm and 260 nm. We therefore use a non uniform approach and retraction speed to enhance the resolution in this area of interest, with a slow ramp at 0.1 µm/s, as shown in figure 2(b). The force curve in this range of compression, though presenting some deviations to a perfect plateau, is rather flat: the local slope of the quasi-static force versus compression fluctuates around zero with a maximum slope below 3 × 10 -2 N/m. The quasi-static stiffness of the nanotube in contact with the sample, defined by this slope, is thus close to zero in average: k QS = dF/dz c = (4 ± 22) mN/m (mean and standard deviation).

III. CONTACT DYNAMIC STIFFNESS

As the compression ramp is sufficiently slow, we stay long enough around any compression z c to measure a spectrum of the deflection driven by the cantilever thermal noise or to probe the frequency response of the contact. The force acting on the AFM tip is no longer due to the deflection of the cantilever alone, since the nanotube touching the surface has to be considered as well. The mechanical oscillator (the first mode of cantilever) experience an effective stiffness k 0 + k c , shifting its resonance angular frequency 24 from ω 0 to ω c , as illustrated in figure 2(c) 13,14,25 . Dissipation is neglected in the following since the quality factor of the resonances is always large, above 20 at worse.

Let us model the system as sketched in figure 1(c): the cantilever's dynamics is that of a simple harmonic oscillator (SHO, effective mass m, stiffness k 0 ), while the nanotube in contact with the substrate adds a stiffness k c . The equation of motion of the tip can be written in the time space as:

m d = F ext -k 0 d + k c z c (3)
where F ext is an hypothetical external force acting on the tip. Moreover, the compression of the nanotube z c and the deflection of cantilever d are linked by

z c = z s -d (4)
Let us study two different cases, depending on whether z s is constant or externally driven.

A. Quasi-static thermal noise measurement

If z s is constant (the substrate is static -or quasistatic), the equation of motion (3) reads in the Fourier space:

k 0 + k c (ω) -mω 2 d(ω) = F ext (ω) (5)
In this last equation, we explicitly allow k c to depend on frequency, but as the resonance is sharp enough, only its value close to the resonance matters to accurately describe the thermal noise peak. This equation thus corresponds to a simple harmonic oscillator of mass m and stiffness k 0 + k c (ω c ). The SHO parameters (mass, stiffness) are linked to the resonance frequency by the usual relation:

mω 2 0 = k 0 ( 6
)
mω 2 c = k 0 + k c (ω c ) (7)
We can thus easily compute the contact stiffness k c from the angular frequency ω c of the resonance 13,14,25 : and from thermal noise analysis (fc). The dynamic stiffness is higher than the quasi-static one, and is almost constant on the force plateau. Some small variation are visible along the nanotube length though, they are correlated between force and stiffness: the larger the adhesion, the larger the dynamic stiffness.

k c (ω c ) = k 0 ω c ω 0 2 -1 (8
The resonance frequency is measured from the noise spectrum of the cantilever 13,14,25 : the power spectrum density (PSD) of the fluctuations of deflection, induced by the thermal noise random forcing, is sharply peaked at ω c , as illustrated in figure 2(c). During the quasi-static ramp, we compute the PSD on a 0.4 s sliding time window, thus corresponding to only a 4 nm vertical translation of the sample. Using the procedure described above, we report figure 3(b) the measured values of the stiffness k c (ω c ) of the contact as a function of the nanotube compression z c . On the force plateau probed here, with this nanotube, we see that k c values at resonance are independent of the compression z c , thus quite flat: k c (ω c ) = (108 ± 12) mN/m (mean and standard deviation). This result contrasts singularly with the quasistatic measurement: k QS = (4 ± 22) mN/m.

B. Dynamic measurements

Thermal noise is a powerful tool to probe the contact dynamics, however it is limited to the resonant frequency of the micro-mechanical oscillator. To bridge the gap in the values of the contact stiffness between the quasi-static and the resonance conditions, we use an extended force modulation strategy: we shake the substrate vertically and test the response of the nanotube/substrate contact at various frequencies between 10 Hz and 10 kHz. The substrate translation stage being too massive to reach such high frequencies, we mount the mica surface on an additional dedicated small piezo actuator (Physik Intrumente -PICMA PL055, 5 mm × 5 mm × 2 mm, with an unloaded resonance above 300 kHz). The response function of this fast piezo to the driving voltage is calibrated using a stiff AFM probe in hard contact with the surface. It is flat at 16 nm/V in the frequency range probed here. From the driving voltage, we thus know precisely the induced displacement z s (ω): our resolution is equivalent to that given by the interferometer, far beyond the sensor embedded in the translation stage. We can finally measure the response function χ(ω) of the deflection d(ω) to z s (ω). Using equations 3 and 4 with F ext = 0, we easily get

χ(ω) = d(ω) z s (ω) = k c (ω) k 0 (1 -ω 2 /ω 2 0 ) + k c (ω) ( 9
)
This equation is transformed to express the dynamic stiffness as a function of the measured response function χ(ω):

k c (ω) = χ(ω) 1 -χ(ω) k 0 1 - ω 2 ω 2 0 (10)
To evaluate k c (ω) for different compression values of the nanotube during peeling, we add the periodic driving of z s on a ramp equivalent to that of used to test quasi-static and thermal noise properties of figure 2(b). This periodic driving is designed as the sum of 16 sinusoids at frequencies approximately logarithmically spaced between 10 Hz to 10 kHz, each having an amplitude of 0.1 nm rms (see figure 4). The response function χ(ω) is then evaluated as the ratio of the Fourier transforms of the measured data (d and z s ), at the driving frequencies only, each FFT being performed on a small 0.4 s sliding time window 26 . This strategy allows one to measure the response function in the whole frequency range in a single approach-retract cycle, avoiding any question about the reproducibility of the precise peeling configuration encountered during successive cycles if one had to test only one frequency at a time. Frequencies smaller than 10 Hz were too noisy to be useful (they would require slower ramps to test each compression longer), and above 10 kHz the transfer function of the piezo is not flat enough to ensure precise measurements. Moreover by staying below 10 kHz we avoid any overlap with the natural thermal noise which is peaked around 17 kHz with a rms amplitude of 0.1 nm, we thus keep a sufficient signal to noise ratio for each sinusoidal driving.

The result of this process is plotted on figures 3 to 5: k c as a function of nanotube compression for a few different frequencies in figure 3 compression as a function of frequency in figure 5. From these figures, we first observe that, at each frequency, the stiffness is roughly constant (the standard deviation is around 10 % of the mean value). The small variations with compression are correlated at every frequencies and linked to the value of the adhesion force: the larger the adhesion, the larger the dynamic stiffness. The behavior with frequency is also quite weak: the stiffness grows steadily by a factor of 2 when the frequency spans 3 orders of magnitude. The value at high frequency tends to that predicted by the thermal noise analysis, and the low frequency trend is compatible with a zero stiffness for a quasi-static driving. No characteristic time scale is evidenced on this curve, which can be fitted by a power law with a small exponent (∝ f 0.1 , black dashed line). The high frequency behavior is compatible with the thermal noise estimation of kc at resonance (from the resonance frequency shift, red diamond). The low frequency behavior as well is compatible with the quasi-static estimation of the stiffness near 0 (gray triangle). Note that the quasi-static point should be placed at f = 0, which cannot be seen on this logarithmic scale, so the reported point should be understood as the limit for f → 0. Error bars correspond to one standard deviation in the average over position along the nanotube compression. Larger uncertainties around 100 Hz are due to a slightly higher environnemental noise in this frequency range, degrading the signal to noise ratio of the minute solicitation we are applying.

IV. DISCUSSION AND CONCLUSION

When the nanotube is close to the substrate, it tends to adhere and maximize its contact length. An equilibrium spatial shape balancing the adhesion energy of the adhered part and the bending energy of the free standing part is reached. For a long nanotube free of defect, this equilibrium translates into a force plateau in the force versus compression curve. This force plateau should thus correspond to a zero spring constant during the contact: the force doesn't depend on the position, thus no stiffness is expected. However, as evidenced by the thermal noise analysis, the resonance frequency of the AFM probe is higher during the peeling than when there is no contact. This behavior can be understood as adhesion and peeling being "slow" processes: at the resonant frequency (over 10 kHz), if the contact between the nanotube and the substrate is seen as "frozen", then the free standing part of the nanotube is clamped on each side, and has a non zero stiffness. The question arising from this picture is then to understand what could impede the nanotube to relax quickly when it is retracted from or approached to the substrate, since the Van der Waals forces accounting for adhesion are an instantaneous interaction.

Using a direct excitation of the contact mechanics, we probe here its dynamic response. We find that the contact stiffness depends only weakly on frequency, as illustrated in figure 5: it can be approximated by a power law in frequency with a small exponent (∝ f 0.1 ). In this peeling configuration, we thus do not find any characteristic time scale for slow vs. fast adhesion processes. Such amorphous behavior of the mechanics could be linked to relaxation processes with widely distributed time scales. One hypothesis is for example that nanoscale rearrangement or diffusion of defects occur during the strong mechanical solicitation of the contact point (the radius of curvature is typically only 10 times the nanotube diameter 13,14 ). Such defects exist undoubtedly 16 , as shown by the irregularities in the measured quantities along the cantilever length, in the form of fluctuations around the plateaus, or more dramatic force jumps in the force curves. Another hypothesis is that some friction occurs at the contact point, dissipating part of the mechanical energy and leading to delays in the system response. The last question is the role of the amorphous carbon unavoidably left around the nanotube during the growth 19 , such as its plasticity during the mechanical solicitation and the friction that may occur at its interface with the nanotube or the substrate.

Answers to these questions may be found in the future by performing peeling experiments with simultaneous high precision force measurements and electronic microscopy visualisation of the nanotube configuration and of the contact shape at the nanometer scale. Comparison to experiments of peeling of other nano-objects (BN nanotubes, nano-wires) may also give interesting insights in the generality of the observed weak frequency dependence of the dynamic stiffness.

  (b). The deflection d and the sample vertical position z s are simultaneously recorded with high resolution acquisition cards (National Instruments -NI-PXI-446x) at 200 kHz.

Figure 1 (

 1 c) reports the sketch the simplified model. An example of a force curve is plotted in figure2(a). It presents a strong hysteresis due to the adhesion between

FIG. 1 .

 1 FIG. 1. (Color online) -(a)Scanning electron micrograph of a soft CNT grown directly on an AFM tip. The nanotube length is Lc ∼ 500 nm. (b) When the nanotube is pressed almost perpendicularly against a mica surface (θ = 15 • inclination of the AFM cantilever with the substrate), part of the nanotube adheres to the surface due to Van der Waals interactions. The shape of the CNT is fixed by an equilibrium between the adhesion of the part in contact and the bending of the free standing part of the nanotube. From the measurement of the AFM cantilever deflection d (using differential interferometry20 ) and sample position zs, the force F acting on the nanotube and its compression zc can be recorded. (c) The system is modeled by the effective mass m of the cantilever being connected to two springs: the cantilever (spring constant k0) attached to the static reference, and the nanotube in contact with the substrate (effective stiffness kc). The sketch corresponds to the simplified equation where θ = 0 • and the origins are defined such as zc0 = zs0 = 0.

FIG. 2 .

 2 FIG. 2. (Color online) -(a)Force F of a CNT as a function of its compression zc on a mica substrate. A strong hysteresis, due to the adhesion can be noted between approach (blue) and retraction (yellow/red). Plateaus in the force curve are characteristic of a peeling process13 . (b) The ramp is designed to probe specifically the peeling configuration corresponding to compressions zc between 160 nm and 260 nm during retraction. (c) As shown by the PSD of the deflection S d , the thermal noise of the cantilever allows the measurement of the additional stiffness due to the contact: the resonant frequency is higher (red) when the nanotube is in contact with the substrate than before contact (blue).

) 2 FIG. 3 .

 23 FIG. 3. (Color online) -(a) Position dependence of the quasistatic force. (b) Contact stiffness: quasi-static (Qs.), dynamic from response measurement (at 160 Hz, 1.6 kHz and 10 kHz) and from thermal noise analysis (fc). The dynamic stiffness is higher than the quasi-static one, and is almost constant on the force plateau. Some small variation are visible along the nanotube length though, they are correlated between force and stiffness: the larger the adhesion, the larger the dynamic stiffness.

12 FIG. 4 .

 124 FIG. 4. (Color online) -(a) Frequency and position dependence of the contact stiffness from the response measurement. (b) During the slow peeling ramp, a small amplitude vertical oscillation is applied to the sample: it consists in the sum of 16 sinusoids from 10 Hz to 10 kHz of 0.1 nm rms amplitude. (c) At the excitation frequencies (evidenced with filled circles on the PSD of the excitation), the response function χ(ω) from this applied oscillation to the deflection of the cantilever is measured and translated into the equivalent contact stiffness. kc(ω) depends slightly on the position along the nanotube, and is slowly increasing with frequency.

12 FIG. 5 .

 125 FIG.5. (Color online) -Frequency dependence of the average contact stiffness. Averaging the stiffness along the positions on the force plateau, we get this slowly increasing behavior of kc as a function of frequency (blue circles): it doubles when f increases by 3 orders of magnitude. No characteristic time scale is evidenced on this curve, which can be fitted by a power law with a small exponent (∝ f 0.1 , black dashed line). The high frequency behavior is compatible with the thermal noise estimation of kc at resonance (from the resonance frequency shift, red diamond). The low frequency behavior as well is compatible with the quasi-static estimation of the stiffness near 0 (gray triangle). Note that the quasi-static point should be placed at f = 0, which cannot be seen on this logarithmic scale, so the reported point should be understood as the limit for f → 0. Error bars correspond to one standard deviation in the average over position along the nanotube compression. Larger uncertainties around 100 Hz are due to a slightly higher environnemental noise in this frequency range, degrading the signal to noise ratio of the minute solicitation we are applying.

ACKNOWLEDGMENTS

We thank F. Vittoz and F. Ropars for technical support, A. Petrosyan, S. Ciliberto, M. Geitner for stimulating discussions. We thank Anthony Ayari and the Plateforme Nanofils et Nanotubes Lyonnaise of the University Lyon 1 for the assistance in preparing the nanotubes. This work has been supported by the ANR project HiRe-sAFM (ANR-11-JS04-012-01) of the Agence Nationale de la Recherche in France. Finally, T. J. Li acknowledges the support from ZPNSFC (No. LQ16A020003), NFSC (No. 11547120), CPSF (147899), and the Sci-entific Research Foundation for the Returned Overseas Chinese Scholars (MOE of P. R. C.).


Nathalie Carrasco

David Dubois

Audrey Chatain

Ludovic Vettier

Guy Cernogora

N Carrascop

Molecules, Radicals and Ions produced in an N2-H2 CCP RF plasma

come   L'archive ouverte pluridisciplinaire

Introduction

A Capacitively Coupled Plasma in N 2 -CH 4 mixture is used for the formation of dust to simulate the formation of solid aerosols in Titan's atmosphere. Details of this experimental device are described in details in [1]. The dissociation of CH 4 produces H 2 molecules. In order to understand the complex chemistry occurring in the N 2 CH 4 mixture, study of the N 2 H 2 mixture is developed as a first step.

Experimental device.

Experimental device

The CCP discharge is confined in a metallic cylindrical box of 13.6 cm in diameter. Two slots, diametrically opposed are managed in the cylindrical box. This box is placed into a 30 cm in diameter and 40cm height stainless steel reactor fitted with two KBr windows diametrically opposed. Gas mixture is injected continuously in the plasma and pumped with a rotary pump. The amount of H 2 in N 2 is tuned from 1 to 5%. Pressure in the plasma discharge is maintained at 1 mbar. Between the discharge and the pump, a trap cooled by liquid nitrogen condenses molecules produced in the discharge.

Measurements.

The neutral molecules, radicals and positive ions are measured using a mass spectrometer EQP Hiden placed in front of one of the slot. After few hours of plasma run, the gas injection is turned off, valves upstream and downstream the cold trap are closed and the trap is slowly warmed up to the room temperature. Then the condensed gases are reinjected in the reactor. The molecules densities are measured using a Nicolet 6700 Fischer FTIR spectrometer through the 40 cm of in diameter of the reactor [2]. Focus is done on the NH 3 molecule measured in the 967 cm -1 band. In our experimental conditions, the NH 3 density is on the order of 10 12 cm -3 .

4-Perspectives

These results obtained are now to be compared with the modelling of the plasma in our experimental conditions. The major point is the relative contribution of volume reactions versus catalytic ones for the formation of NH 3 .

  [1] Alcouffe, G. , M. Cavarroc, G. Cernogora, F. Ouni, A. Jolly, L. Boufendi and C. Szopa (2010),. Plasma Sources Sci. Technol. 19(1): 015008. [2] Dubois D., Carrasco N., Petrucciani M., Tigrine S., Vettier L Neutral Chemistry in Titan's Ionospheric Simulated Conditions, Dubois D., et al., DPS-EPSC 2016, Oct 2016, Pasadena, USA


Léo Nicolle
email: leo_nicolle@etu.u-bourgogne.fr

Julien Bonneton
email: julien.bonneton@liris.cnrs.fr

Hubert Konik
email: hubert.konik@univ-st-etienne.fr

Damien Muselet
email: damien.muselet@univ-st-etienne.fr

Laure Tougne
email: laure.tougne@liris.cnrs.fr

Towards an electronic orientation table: using features extracted from the image to register Digital Elevation Model

Keywords: skyline detection, Digital Elevation Model, line matching, color edges

Looking at a countryside, human has no difficulty to identify salient information such as skyline in case of benign weather. At the same time, during the last decade, smartphones are more and more abundant in our daily life with always new efficient proposed services but augmented reality systems suffer from a lack of performance to offer a well adapted tool in this context. The aim of this paper is then to propose a new approach coupling image processing and Digital Elevation Model (DEM) exploitation to remedy that shortcoming. The proposed method first discriminates skyline and non-skyline pixels and then introduces a realtime matching between previously extracted map and DEM. In order to evaluate objectively each step and our finalized tool, a new tagged dataset with ground-truth is created and will benefit the entire scientific community.

INTRODUCTION

People hiking in the mountains or simply walking are always looking for information about what they are seeing : mountain names, elevations, village names, hiking trails, tourism information, etc. Even if hiking maps can provide such information, they require the hiker to match the 2D data he has on the sheet with the 3D landscape he can see and this is not that always easy for no experts. Orientation tables also help for such problems but they are located at some too rare points in the mountains. As nowadays everyone or almost has in his pocket a smartphone that integrates instruments such as compass, accelerometer, GPS, etc., with more and more memory and computing power, the idea of this work is to create a smartphone application that provides as much information as possible to the people looking at a mountain landscape. The idea consists in visualizing the landscape with the smartphone camera and the desired information will be displayed on the screen thanks to augmented reality tools. Objectively, some smartphone applications already provide information about mountains peaks around a user, but the data are mostly displayed as maps on the screen (Peakfinder, 2016;pointdevue, 2015;swissmap, 2016) or, for few of them, they are superimposed on the screen image (Peakscanner, 2016;Peak.AR, 2010). Figure 1 shows two examples of screenshots of such applications.

None of these applications is exploiting the image content in order to help the data registration. Indeed, the mountains peaks are reconstructed from the available digital elevation model (DEM.) and from the smartphone sensors (GPS and digital compasses). The poor accuracy of such sensors badly impact the augmented reality results, making these applications almost unusable. This is in fact the main comments done by the users on the stores. In recent years, many approaches have been proposed to compensate the lack of performance of such sensors, particularly in constrained environment, but none our way.

Thus, we propose a new approach in order to cope with this problem. Our solution consists in extracting a probability map of skyline in the image acquired by the smartphone camera and then, to match these data with the 3D data available from the DEM. To avoid Internet connection problems, it is directly stored in memory before its utilization.This matching step allows to display the data on the screen with high accuracy.

Our contributions are threefold: • Unlike the classical skyline detection algorithms that are based on channel-wise edge detector, we fully exploit the 3D color information of the pixels by learning a color metric that helps in discriminating skyline edges from non-skyline edges.

Figure 1: Screenshots of two existing applications, namely "Peakfinder" and "Point de vue", that display local maps on the screen without registration.

• Because the time response and the accuracy of the application is crucial, we propose a fast matching between the probability map and the 3D data available from the DEM. • Since other applications exist in order to provide information about peak mountains, we created a new tagged dataset with ground-truth so that the accuracy of the different approaches can be assessed and compared. This dataset as well as the ground-truth data will be publicly available.

RELATED WORKS

There is in the literature few articles dealing with the extraction of the skyline. The purpose of some of them is the extraction of this line from the image data only. However others exploit the smartphone sensors such as GPS and compasses in order to superimpose the data. But the accuracy of these sensors is small and do not have very satisfactory results from the users point of view. This is the reason why we recommend to exploit the image data in order to improve the quality of the registration step. And the main image information that can be matched with the DEM is the skyline. Some papers have already proposed approaches in this direction as we shall see below but in different contexts and with slightly different constraints.

Skyline detection

Lie et al. [START_REF] Lie | A robust dynamic programming algorithm to extract skyline in images for navigation[END_REF] and [START_REF] Kim | Skyline extraction using a multistage edge filtering[END_REF] consider that the skyline is constituted by the strongest edges in the image. So, they propose first to extract the edges with the classical Canny detector. Lie et al. apply a threshold on the edge image to obtain a binary edge map, which is the input of a dynamic programming search. The idea is to connect the candidate edges that respect some criteria whose aim is to preserve local smoothness and to satisfy geometrical preferences [START_REF] Lie | A robust dynamic programming algorithm to extract skyline in images for navigation[END_REF]. Kim et al. propose to select the best skyline candidate among the output of the Canny detector as the one that is mostly flat and symmetric (Byung-Ju [START_REF] Kim | Skyline extraction using a multistage edge filtering[END_REF].

Hung et al. also apply the Canny detector as a first step and then learn a SVM classifier on these edge pixels to classify them into skyline edges and no-skyline edges [START_REF] Hung | Skyline localization for mountain images[END_REF]. For this classification, they are using a 210-D feature vector for each edge pixel, that represents color and texture information extracted from the local neighborhood of this edge pixel. At test time, they create a map for each image in which each pixel is characterized by a value related to its probability not to be a skyline pixel. Then they propose a recursive algorithm that finds the shortest path in the image, from left to right, that minimizes the cumulative energy. This path is the detected skyline.

Likewise, Ahmad et al. also propose to learn a classifier on the pixels in order to classify them into skyline pixels and no-skyline pixels [START_REF] Ahmad | An edge-less approach to horizon line detection[END_REF]. The input of the classifier is a 256-D feature vector characterizing the local neighborhood of the considered pixel. The difference with [START_REF] Hung | Skyline localization for mountain images[END_REF] is that they are classifying all the pixels, and not only the edge pixels, because they argue that true skyline pixels may be not detected by the Canny edge detector. Then each image is transformed into a classification score map which is informing about the probability of each pixel to be a skyline pixel. Finally, they also find the shortest path with highest cumulative energy in this map.

The approach of Saurer et al. is a bit different from the previous ones [START_REF] Saurer | Image based geo-localization in the alps[END_REF] because they classify all the pixels of the image into sky and non-sky pixels. The feature vector characterizing each pixel is a concatenation of 4 bags of words (textons, local ternary patterns, self-similarities and SIFT), each one being quantized to 512 clusters and independently in 5 different color spaces. After running the classifier on all pixels of the image, they determine the skyline as the line that maximizes along the columns the number of pixels being classified as sky above the line and as non-sky below the line, regularized by a smoothness term that helps the line to be smooth.

The output of all these works is a binary image in which each pixel is classified as skyline or non-skyline. In order to improve the accuracy of the matching between the DEM and our image, we will show in the experimental results that it is better to work with a classification score map, where each pixel is associated with its probability to be a skyline pixel, instead of a binary map (skyline vs noskyline). Consequently, these approaches would not help to solve our problem as they are actually proposed. Nevertheless, the classification step of some of them could have been interesting for our work, but it is clear that the size of the proposed feature vectors and their extraction time are not adapted to our problem. Indeed, we are looking for features that do not require too much memory place and that are very fast extracted.

Some other works also propose solutions to match the detected 2D skyline with 3D data extracted from the available digital elevation model.

Matching the detected skyline with 3D DEM data

Baboud et al. propose a solution to automatically annotate mountain pictures [START_REF] Baboud | Automatic photo-to-terrain alignment for the annotation of mountain pictures[END_REF]. Their idea is to detect edges in the mountain pictures and to match these edges with silhouettes extracted from the 3D DEM. The originality of this work is to introduce a vector field cross correlation that accurately match 2 sets (from image and from DEM) of local edges. Unfortunately, this processing can not be adapted to our problem since it requires 2 minutes per image. Indeed, for image annotation problems, the processing time is not as crucial as for smartphone applications. So they rather concentrate on accuracy matching and do not use only the skyline in the image but all the edges that could help for the matching. Fedorov et al. exploit the skyline detection algorithm from [START_REF] Lie | A robust dynamic programming algorithm to extract skyline in images for navigation[END_REF] and match this skyline with 3D DEM data [START_REF] Fedorov | Mountain peak identification in visual content based on coarse digital elevation models[END_REF]. Their aim is also to annotate mountain pictures and so they do not try to improve the processing time. Thus, they apply a high number of successive steps in order to improve the matching. After extracting the skyline with [START_REF] Lie | A robust dynamic programming algorithm to extract skyline in images for navigation[END_REF], they apply the vector field cross correlation from [START_REF] Baboud | Automatic photo-to-terrain alignment for the annotation of mountain pictures[END_REF] in order to find 3D skyline candidates in the DEM. Then, for each candidate they evaluate a Hausdorff distance with the image skyline in order to find the best candidate. Finally, they resort to a local alignment step by applying again vector field cross correlations locally at different positions of the skyline. It is clear that this multiple stage approach can not reach the processing time constraint required by our application.

The aim of the work of Saurer et al. is to geo-localize an image that has been acquired in the Alps [START_REF] Saurer | Image based geo-localization in the alps[END_REF]. So, from an image, they first extract the skyline as described below and try to find the most similar skyline in the DEM data they have. So their work is more about skyline retrieval than skyline matching. Hence, they propose an invariant and a compact skyline descriptor and, try to retrieve the image skyline in a dataset of skylines, in order to deduce coarse GPS position of the considered image. Consequently, their work can not help our skyline matching step.

Finally, Zhu et al. propose an image/DEM registration system based on skyline [START_REF] Zhu | Video/gis registration system based on skyline matching method[END_REF]. This work is interesting because of its real-time constraint but unfortunately, it is only adapted to urban environment and requires the presence of buildings in the image in order to detect the vanishing point. Consequently, this approach can not be used in our context.

FAST AND ACCURATE SKYLINE EXTRACTION AND MATCHING WITH DEM

For our electronic orientation table, we propose a two-steps solution. First, in a similar way as previous works, we resort to a classification step in order to extract the skyline from the image. But, unlike all the other previous approaches, we use very simple color features that are adapted to our problem thanks to a metric learning algorithm. Then, we propose to match the detected skyline with the extracted skyline from the DEM and project it in the image space.

Skyline extraction

In order to fulfill our time constraints, we propose to use the RGB data available in the image instead of extracting some complex features. Instead of classical previous skyline detectors based on edges, we propose to exploit the simple color difference in order to detect the skyline. Of course the single color difference is not enough to classify all the edges, but the robustness of the approach mainly depends on the variability of the learning data. So, during the learning step, it is important to consider images under a lot of different conditions (weather, illumination, , etc.). Evaluating accurate color differences from uncalibrated JPEG images is not an easy task (Perrot et al., 2014) but our aim here is rather to evaluate discriminative color differences, i.e. color differences that help to discriminate skyline edges from non-skyline edges. For this purpose, we resort to metric learning tools applied in the color RGB space.

Color metric

Most of the existing works in metric learning are focused on learning a Mahalanobis-like distance between 2 vectors C 1 and C 2 in the form:

d M (C 1 , C 2 ) = (C 1 -C 2 ) T M(C 1 -C 2 ), (1)
where M is a positive semi-definite (PSD) matrix to optimize [START_REF] Bellet | A survey on metric learning for feature vectors and structured data[END_REF].

In our case, the vectors are the 3D colors denoted by

C 1 = R 1 G 1 B 1 T and C 2 = R 2 G 2 B 2 T of the two compared pixels. Let denote dk = k 1 -k 2 , k ∈ {R, G
, B}, the difference between the components k of the two considered pixels. Thus the matrix M is a 3x3 symmetric matrix such that each coefficient m kk ′ represents the weight associated to each quantity dk.dk ′ :

M =   m RR 1 2 m RG 1 2 m RB 1 2 m RG m GG 1 2 m GB 1 2 m RB 1 2 m GB m BB   . (2)
Indeed, from eq.( 1) and eq.( 2), we can evaluate

d 2 M (C 1 , C 2 ) as: d 2 M (C 1 , C 2 ) = m RR .dR 2 + m RG .dR.dG + m RB .dR.dB + m GG .dG 2 + m GB .dG.dB + m BB .dB 2 . ( 3
)
Note that if M is the identity matrix, the distance d M is the simple color Euclidean distance. The aim of metric learning is to learn the matrix M that meets the problem constraints. In the case of skyline extraction, we evaluate the distance between each vertical pair of neighbor pixels and the constraint is that this distance d M (C 1 ,C 2 ) have to be higher between two pixels on both sides of the skyline than between two pixels that are both in the sky or both in the mountain. Thus, learning M from ground truth data (skyline vs nonskyline edges) allows us to find which components are important in the color differences to discriminate between skyline and non-skyline.

Learning phase

Practically, in order to learn the 6 coefficients of the matrix M, we re-formulate the problem as a max-margin problem and solve it with a linear SVM. Indeed, d 2 M (C 1 , C 2 ) can be expressed as a dot product:

d 2 M (C 1 , C 2 ) =        dR 2 dR.dG dR.dB dG 2 dG.dB dB 2        T .        m RR m RG m RB m GG m GB m BB        , d 2 M (C 1 , C 2 ) =dC T .H M (4)
i.e. as a projection of the pair difference vector dC on a 6D classifier H M .

By looking at mountain landscapes it appears that the strongest edges, despite the skyline, are mostly in the mountains and not in the sky. So we propose to account the edge position when detecting the skyline so that the top edges in the image have more chance to be classified as skyline than the bottom edges. This is done thanks to a weighted step that is detailed in the next paragraph. Consequently, the main aim of our learning step is to remove the strong edges in the sky so that the skyline appears as the first strongest edge in each column when visiting the pixel from top to bottom. Thus, we create two sets of edges:

• the positive edges P + that are constituted by the two neighbor colors that lie on both sides of the skyline,

• the negative edges P -that are constituted by two neighbor colors that lie above the positive edge of the same column in the same image and whose euclidean distance in the RGB color space is higher than the one between the positive pair of the same column. If in one column, no edge fulfills this condition, we randomly pick a non-skyline edge above the positive pair of this column, so that the positive and negative data are well balanced.

From this definition of the learning data, the aim of our learning step is to learn the Mahalanobis matrix M (or the classifier H M ) so that, given two corresponding positive and negative pairs from the same column and same image P + i and P - i , we have

d 2 M (P + i ) > d 2 M (P - i ).
Thus, if the respective pair difference vectors are denoted dC i + and dC i -, we are looking for H M so that (dC i + ) T .H M > (dC i -) T .H M . This can be done by finding the classifier H M and the bias b so that (dC i + ) T .H M +b > 0 and (dC i -) T .H M + b < 0. With a classical linear SVM, it corresponds to maximize the margin between the two sets of pairs. The bias is just translating all the distances, which are initially positive, around 0, where skyline scores are positive and non-skyline scores are negative.

Inference

After the learning step, we get the 6 parameters of H M and use them to obtain the Mahalanobis matrix M (see eq. ( 2)). If this matrix is positive semi definite (PSD), it can be decomposed thanks to the Cholesky factorization as:

M = L T .L, ( 5
)
where L is a 3x3 lower triangular matrix. In this case, eq.( 1) can be expressed as:

d M (C 1 , C 2 ) = (C 1 -C 2 ) T L T .L(C 1 -C 2 ) = (L.C 1 -L.C 2 ) T (L.C 1 -L.C 2 ), (6)
which is the Euclidean distance between the two colors L.C 1 and L.C 2 . Thus, from a PSD Mahalanobis matrix M, we can deduce a matrix L that projects the RGB colors into a new color space in which the skyline edges can be easily detected thanks to a simple euclidean distance. Consequently, at test step, we just have to project the RGB color vectors of each pixel on the new learned discriminate color space thanks to a simple matrix multiplication L.C 1 and L.C 2 and, to evaluate a simple Euclidean distance between the new colors of neighbor pixels in order to detect the skyline. Hence, for each pixel pair, we get a distance that is related to the chance of each edge to be on the skyline. Note that, for all the tests we run, we always got a matrix M that was PSD. If the matrix M is not PSD, we have to project it on the PSD cone matrix in order to get the nearest PSD matrix that fulfills our learning constraints.

After evaluating the Euclidean distance in the new learned color space, we get a map of "scores" (chance to be on the skyline), that we call the score map. Note that, with the bias of the SVM added, the score s(i, j) should be positive if the edge at position (i, j) is on the skyline and negative if it is not on the skyline. Since during the learning step, we have not considered strong edges below the skyline on each column (we have just removed edges in the sky, not in the mountain), we have to remove these strong edges. Our simple but efficient solution consists in weighting the scores s(i, j) in the column j as follow:

sw(i, j) = s(i, j) 1 + ∑ i row=0 s(row, j)(s(row, j) > 0) , (7)
where the row= 0 is the top row, and (s(row, j) > 0) is a test that returns 1 if s(row, j) > 0, 1 otherwise. By this way, we consider that, by visiting each column from top to bottom, the first strong positive edge has a high chance to be on the skyline. This is due to our learning process whose aim was to remove the strong edges that were above the skyline. After this step, we get a weighted-score map illustrated in Figure 2. In this figure, we compare the results obtained by our metric learning approach with the ones obtained with the classical Euclidean distance in the RGB color space. We can see that since the edges along the skyline are not strong in the RGB space, they are not detected with the Euclidean distance. Fortunately, the metric we have learned clearly identifies these edges as strong ones. The images on the right show the weighted maps obtained from either the Euclidean distance map or from the learned color metric. We can see that this step helps in removing most of strong edges that are below the skyline in the color metric map.

Nevertheless, it is clear that the information provided by an image can not be sufficient to get a perfect match between the detected pixels and the true skyline. Consequently, after this fast color detection, we propose to exploit the available DEM in order to refine the results. Our aim consists in registering the DEM with the obtained weighted-score map.

Skyline matching

Using the score map previously obtained that indicates the chance for each pixel to be on the skyline, our goal is now to register correctly the DEM on this map. Figure 3 shows, for two images, the weighted score maps as well as the information we have extracted from the available DEM and projected in the 2D image space from the data provided by the smartphone (GPS. and digital compasses) without using the image features. In these images, the brightness of the green is related to the altitude of the points. It is worth mentioning that the DEM we used is free, so its resolution is coarse 1 . This figure clearly illustrates the interest of combining the both data to detect the skyline: color edges and DEM.

More precisely, using the GPS coordinates and the intrinsic camera parameters, the DEM can be visualized from the camera point of view. The figure 4 1 http://www.cgiar-csi.org/data/srtm-90m-digitalelevation-database-v4-1

shows an example of such a visualization. But as we can see on this figure, the projection is not perfect due to smartphone's measure instruments error. So let explain now how we can exploit the previous score map to obtain a more reliable user's orientation estimation. such a problem is a 6-dimensional problem (considering we know camera's intrinsic parameters) as explained in [START_REF] Zhu | Video/gis registration system based on skyline matching method[END_REF] because the parameters that have to be adjusted are the position (three parameters) and the orientation (three parameters too) of the camera. Trusting the GPS position and considering the projection of the DEM onto a 2D image, we reduce the problem into one that consists in finding the best 2D transformation to match our scoremap with the DEM projection. This transformation is composed of one 2D translation and one rotation only. We do not have to seek for the right scale to apply to our DEM, this information is contained into camera's intrinsic parameters. In practice, we consider an angle a bit larger that the real field of view to deal with the lack of precision of the compass.

Let us denote by S DEM the skyline extracted from the projection of the DEM in the image. Notice that to quickly perform translations and rotations, this skyline is stored as a set of 2D vectors, corresponding to the relative positions of the points in the image, with respect to the left-most point:

ŜDEM = {v k | v k = DEM (k) -S DEM (0)}
where v k is the k th vector of the vectorized skyline ŜDEM , and S DEM (i) is the 2D position of the theoretical skyline at the column i.

To find the best registration between the DEM skyline and the weighted-score map sw, we define the energy function E( ŜDEM , T ) as follow:

E( ŜDEM , T ) = n ∑ k=0 sw(v k * M)
where T is a 3x3 matrix consisting in a translation and a rotation and sw(p) the value of the weighted score map at point p. The matrix M satisfying argmax T (E( ŜDEM , T )) is the best transformation to apply to the DEM skyline to match with weightedscore map sw (see Fig. 6). In order to find the best transform matrix T , the brute force approach would have consist in testing all the possible T and keeping the one that maximizes the previous energy function E( ŜDEM , T ). The parameters of T are the translation t x along the horizontal axis, the translation t y along the vertical axis and the rotation angle α around the left-most point. We call P the set of possible solutions defined as:

         P = {p = (t x ,t y , α)} t x ∈ [t x min ; t x max ] t y ∈ [t y min ; t y max ] α ∈ [α min ; α max ]
So, we have a 3D search space, and given our discretization choice, we have card(P) = 3.6 millions of possible solutions to test.

In order to reduce the complexity of the algorithm, we resort to an original multi-resolution approach. The idea consists in:

• testing all the solutions in the search space for few points of the skyline,

• among these solutions, keeping only the ones that provide the top values for the energy function (the other solutions are definitively removed from the search space),

• adding few points to the skyline and testing the selected solutions of previous step for these points,

• iterating the two previous steps until the fullresolution skyline is tested.

Practically, we propose an algorithm in log 2 (n) steps, where n is the number of points in the DEM (close to image width), i.e. 10 steps for our 1024x768 images. At each step i, we consider only 2 i points uniformly picked in the DEM and evaluate the energy function only for these DEM points. Let denote u, a geometric series such that u 0 = card(P) and u log 2 (n) = 1. So, at each step i, we keep only the u i best transforms T that will be tested in the next step. Thus, at each step, we reduce exponentially the number of solutions to test while we increase the precision of the DEM. Our matching algorithm takes 0.5 second for a 1024x768 image on a computer Intel Core i5 1.3GHz.

EXPERIMENTAL RESULTS

Since there is no dataset with the information required by our system (pictures with GPS coordinates and camera orientations), we created one which will be publicly available. Below, we will first present this dataset and the necessary meta data. Then, we will present the results on this database evaluating in particular the distance between the skyline in the ground-truth images and the one extracted from projected DEM in image without and with registration step.

Our dataset

To create the dataset, we developed a smartphone application which allows to take a picture of a landscape and meanwhile to record the geographic position of the user and the value of the various instruments that are available in the smartphone. More precisely, the data stored are the following:

• latitude, longitude, altitude,

• angle with north and magnetic north,

• tilts Y and Z. Some of these parameters are already provided by some datasets, but the ones concerning the orientation of the camera are not available. All these elements are stored in a JSON file.

Furthermore, for each acquired image, we created a ground truth and so we manually segmented the skyline. Hence, JSON file is accompanied by a binary file in which the pixels of the skyline are marked.

For the tests, about twenty images are taken into account. We will enrich the dataset over time.

Results

In order to assess the quality of our algorithm, we propose to test it on our dataset and to evaluate the average distance (in pixels) over all the images between the skyline we obtain and the ground-truth skyline. Of course this distance is relative to the image size 1024x768. The results are shown in figure 7.

In order to check the relevance of each contribution of our algorithm, we have run several tests by removing each single step from the whole process and check the results for each. We recall that the main contributions of our algorithm are : color metric learning, score weighting and matching with DEM. In figure 7, we clearly see the relevance of each individual step, since the average distance dramatically increases (from 3 pixels to 14 or even 23) when we remove one of them. It is worth mentioning that our learning step has been run on the CH1 dataset described in [START_REF] Saurer | Image based geo-localization in the alps[END_REF] and not on our dataset. The CH1 dataset consists of images of mountains in which the skyline has been manually segmented (unfortunately, no geographic information are provided with this dataset, so that we can not extract the correct DEM to run our algorithm on these images). This shows that our new color metric has been learned once on one dataset and can be used on any other dataset without fine-tuning it to the new considered images.

Furthermore, in figure 7, we show the results obtained by our algorithm when the score map is binarized before the DEM matching. The binarization consists in only keeping the highest score in each column. We can see that this binarization does not help the matching step (and even slightly increases the distance). This is interesting to see that our matching algorithm is performing better with a dense score map (where each pixel is characterized by a score) than with a binary skyline detection. Finally, we also show the results provided by a baseline method which con-sists in evaluating column-wise the RGB distances in the image and to match the DEM with this score map (without weights and without ad-hoc color metric). Figure 7 shows that this approach provides poor results since the average distance between the detected and the ground-truth skylines is around 18 pixels.

We can see that by combining all our contributions, we obtain an average distance equals to 3 pixels, which is negligible with respect to the size of the images (0.4 %) . This shows that the proposed skyline detection is the perfect candidate to be integrated in an electronic orientation table.

In figure 8, there are some visual results. We have zoomed on some examples of mountains to show in detail the obtained registration. The two original registrations using only the DEM and the smartphone localization objectively completely fail but the result is better by coupling DEM and image processing.

CONCLUSION

This paper presented a robust two-steps method able to create a smartphone application identifying instantaneously the skyline in an image. The proposed method starts by image simplification based on efficient color difference between aligned pixels giving rise to a score map between sky and non-sky pixels. Then, based on available data directly from the smartphone offering a coarse localization, a second step matches extracted skylines from the digital elevation model with this map to identify precisely the real skyline. The interest of this couple between image processing and digital elevation model is twofold: it gives an efficient tool in this context of electronic orientation table, and it allows to improve augmented reality tools based on smartphones using image processing techniques. Moreover, the tagged dataset built in this paper will benefit the entire community in this field. Future works will first consist in analyzing robustness to meteorologic conditions and then in detecting other notable elements in the image using image analysis but also the DEM. Let us remember that our final goal is to present to the user information concerning points of interest in the image using augmented reality. For this, we also intend to use databases containing monuments, roads, etc.

There is still an immense potential in this field because of its utility in many areas like in tourism of course but also, for example, for hikers who want to visualize hiking trails, for persons interested in geology because it would be possible to show them the structure of the ground also and so on. Smartphones are today abundant in our daily life and augmented reality systems could be developed by mixing their instruments with image processing algorithms.

Figure 2 :

 2 Figure 2: Comparison between the classical Euclidean distance in RGB and our color metric learning approach (see text for details).

Figure 3 :

 3 Figure 3: Two color images from our dataset along with their respective weighted color map and their relief map extracted from DEM.

Figure 4 :

 4 Figure 4: Example of DEM projection, before registration with the skyline.

Figure 5 :

 5 Figure 5: From the field of view provided by the smartphone, we can reduce the search space.

Figure 6 :

 6 Figure 6: Illustration of the registration between the detected skyline (grey-level image) and the DEM (red curve).

Figure 7 :

 7 Figure 7: Average distances for the tested methods between detected and ground-truth skylines (lower is better).

Acknowledgement

The authors acknowledge the support from Le Programme Avenir Lyon Saint-Etienne Image et Perception Embarquées (PALSE IPEm -ANR-11-IDEX-0007). They also would like to thank Thierry Joliveau for his help in this work.


Xiaohu Song

Damien Muselet
email: damien.muselet@univ-st-etienne.fr

Alain Tremeau
email: alain.tremeau@univ-st-etienne.fr

Color-based and rotation invariant self-similarities

Keywords: Color descriptor, self-similarity, classification, invariance

One big challenge in computer vision is to extract robust and discriminative local descriptors. For many applications such as object tracking, image classification or image matching, there exist appearance-based descriptors such as SIFT or learned CNN-features that provide very good results. But for some other applications such as multimodal image comparison (infra-red versus color, color versus depth, ...) these descriptors failed and people resort to using the spatial distribution of self-similarities. The idea is to inform about the similarities between local regions in an image rather than the appearances of these regions at the pixel level. Nevertheless, the classical self-similarities are not invariant to rotation in the image space, so that two rotated versions of a local patch are not considered as similar and we think that many discriminative information is lost because of this weakness. In this paper, we present a method to extract rotation-invariant self similarities. In this aim, we propose to compare color descriptors of the local regions rather than the local regions themselves. Furthermore, since this comparison informs us about the relative orientations of the two local regions, we incorporate this information in the final image descriptor in order to increase the discriminative power of the system. We show that the self similarities extracted by this way are very discriminative.

INTRODUCTION

Evaluating self-similarities within an image consists in comparing local patches from this image in order to determine, for example, the patch pairs that look similar. This information is used for superresolution [START_REF] Glasner | Superresolution from a single image[END_REF][START_REF] Chih-Yuan | Exploiting self-similarities for single frame superresolution[END_REF], denoising (Zontak and Irani, 2011), inpainting [START_REF] Wang | Robust object removal with an exemplar-based image inpainting approach[END_REF], ... The spatial distribution of the self-similarities within each image is also a robust and discriminative descriptor that is very useful in some applications. Indeed, in order to compare images that look very different because of light variations, multi-modality (infrared versus color sensors) or, for example, the images of figure 1, the appearance-based descriptors such as SIFT [START_REF] Lowe | Object recognition from local scaleinvariant features[END_REF] or Hue histograms (van de [START_REF] Van De Weijer | Coloring local feature extraction[END_REF] completely fail whereas the self-similarities provide accurate information [START_REF] Kim | Dasc: Dense adaptive self-correlation descriptor for multi-modal and multi-spectral correspondence[END_REF]. We can note that CNN features [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] do not cope with this problem because they are based on learned convolutional filters that can not adapt themselves alone to a new modality. Consequently, these deep-features have been recently mixed with self-similarities in order to improve the results [START_REF] Wang | Self-tuned deep super resolution[END_REF].

The idea of self-similarity consists in describing the content of the images by informing how similar are some local regions from each other [START_REF] Shechtman | Matching local selfsimilarities across images and videos[END_REF][START_REF] Chatfield | Efficient retrieval of deformable shape classes using local self-similarities[END_REF][START_REF] Deselaers | Global and efficient self-similarity for object classification and detection[END_REF]. By this way, when two red and textured regions are similar in an image, their contribution to the final descriptor will be the same as this of two green and homogeneous regions. This representation is also invariant to any illumination condition variations, to changes in the colors of the objects (a red bike will have the same description as a blue one) and to modifications of the textures. For example, the figures {1(c), 1(e), 1(g)}, {1(j), 1(l), 1(n)} and {1(q), 1(s), 1(u)} show some self-similarities we have evaluated from the 3 images 1(a), 1(h) and 1(o) respectively. For this aim, we have extracted 3 patches {1(b), 1(d), 1(f)}, {1(i), 1(k), 1(m)} and {1(p), 1(r), 1(t)} at corresponding positions in each image 1(a), 1(h) and 1(o) repectively and we have evaluated the similarities between each of this patch with all the patches in the corresponding images. We can see that the similarities remain stable across variations in colors and textures and consequently their local [START_REF] Shechtman | Matching local selfsimilarities across images and videos[END_REF][START_REF] Chatfield | Efficient retrieval of deformable shape classes using local self-similarities[END_REF] or global [START_REF] Deselaers | Global and efficient self-similarity for object classification and detection[END_REF]) spatial distribution can be used to efficiently describe the contents

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o) (p) (q) (r) (s)
(t) (u) Figure 1: The images 1(a), 1(h) and 1(o) represent the same symbol but do not share any shape or color information at the pixel level. The local patches numbered 1 (1(b), 1(i), 1(p)), 2 (1(d), 1(k), 1(r)) and 3 (1(f), 1(m) and 1(t)) are extracted from similar relative positions in these 3 images. The figures 1(c), 1(j), 1(q), 1(e), 1(l), 1(s), 1(g), 1(n) and 1(u) represent the similarities (evaluated with our method) between these respective patches and the image from where they have been extracted. They represent self-similarities. of the images.

In this context, the classical approaches propose to extract the similarity between two local patches by evaluating their correlation [START_REF] Shechtman | Matching local selfsimilarities across images and videos[END_REF][START_REF] Chatfield | Efficient retrieval of deformable shape classes using local self-similarities[END_REF]. The drawback of the correlation is that it is based on a pixelwise multiplication and hence is not invariant to rotation. Indeed, the similarity between two patches can be very low if the first one of these patches is a rotated version of the second one. The image 2(c) represents the similarities between the patch 2(b) extracted from the image 2(a) and all the patches in the image 2(a) with the correlation-based method. We can see that only a part of the bike frame is detected by this way because the orientations of the other parts of the frame are different.

In this paper, we propose to associate each patch in an image with one particular spatio-colorimetric descriptor and to evaluate the similarity between two patches by comparing their descriptors. The proposed descriptor represent both the colors of the pixels in the patch and their relative spatial positions while being invariant to rotation. In order to design this descriptor we exploit the work from Song et al. [START_REF] Song | Local color descriptor for object recognition across illumination changes[END_REF]. The similarities evaluated by this way are displayed in the image 2(d). In this case, we can see that almost the whole frame of the bike can be detected whatever the orientation of each part. Furthermore, we will show that our descriptor-based self-similarity evaluation provides us the information of the angle difference between the orientations of the two compared patches and that this information can be introduced in the representation of the spatial distribution of the self-similarities in an image.

In the second part of this paper, we present how the classical approaches extract the self-similarities from the images and how they represent their spatial distribution. Then, in the third part, we introduce our new local spatio-colorimetric descriptor on which is based our self-similarity evaluation. We propose to represent the spatial distribution of the selfsimilarities by a 3D structure presented in the fourth part. The fifth part is devoted to the experimental results obtained in object classification task and we conclude in the sixth part. [START_REF] Kim | Dasc: Dense adaptive self-correlation descriptor for multi-modal and multi-spectral correspondence[END_REF]. Considering one patch, the idea consists in measuring the similarity between it and its surrounding patches. To determine the similarity between two patches, they propose first to evaluate the pixelwise sum of square differences (SSD) and second they transform this distance to a similarity measure SM = exp(-SSD σ ) where σ is related to the variance of all the SSD locally evaluated. Then, the neighborhood of the considered patch is discretized on a log-polar grid and the maximal value of SM is stored within each bin grid. Chatfield et al. have also shown that the use of this local description provide better results than appearance-based descriptors such as SIFT for matching non-rigid shape classes [START_REF] Chatfield | Efficient retrieval of deformable shape classes using local self-similarities[END_REF].

RELATED WORKS

Deselaers et al. argue that in the context of object classification and detection, the self-similarities should be evaluated globally rather than locally (Deselaers and Ferrari, 2010). Thus, they propose to compare each patch with all the patches in the image. Since this approach is highly time consuming, they propose an alternative to the classical pixelwise similarity evaluation that is based on the bag-of-words approach. Indeed, they associate each patch with a vector which can be its discrete cosine transform (DCT) or the patch itself (reshaped into a vector) and apply a k-means clustering in this vector space in order to get the most frequent vectors. Then, giving a patch, they evaluate its distance with all the cluster representatives and associate it with the nearest neighbor. By this way the similarity measure between two patches is a binary value, 1 if the patches are associated with the same cluster representatives and 0 if not. In order to design their global descriptor, called SSH for Self-Similarity Hypercube, Deselaers et al. first propose to project a regular D 1 xD 2 grid onto the image. Then, they evaluate the similarity between all the patches in one grid cell GC i and all the patches in the image. This returns a correlation surface whose size is the same as the image size. Then, they sub-sample this correlation surface to the size D 1 xD 2 and put it in the grid cell GC i . By doing that for all the grid cells GC i , i = 1, ..., D 1 xD 2 , they obtain their 4D SSH of size D 1 xD 2 xD 1 xD 2 which represent the global repartition of the self-similarities in the image.

In these main works, the self-similarities are evaluated either by using pixelwise correlation between patches or by comparing the indexes of the associated cluster representatives of the two patches. In the first case, the extraction of the self-similarities can be highly time consuming and in the second case, the similarity between two patches is a binary value, 0 or 1. Furthermore, the results provided by the second approach are highly dependent on the quality of the clustering step. Consequently, we propose another approach that speed up the self-similarity evaluation while giving a real value as similarity measure between two patches. Therefore, we propose to evaluate a color descriptor of each patch and then to evaluate a similarity measure between these descriptors. Since these descriptors are not dependent on the orientations of the patches, our self similarities are rotation invariant. This is illustrated in Fig. 2, where we can see that the classical correlation-based approaches (image 2(c)) can not detect all the self-similarities in the image whereas the self-similarities detected by our approach in image 2(d) clearly underline the discriminative power of the proposed color descriptor as well as its rotation invariance. Our local descriptor is introduced in the next section.

ROTATION INVARIANT DESCRIPTOR

In this section, we present our spatio-colorimetric descriptor used to evaluate the self-similarities. Therefore, we propose to exploit the paper from Song et al. [START_REF] Song | Local color descriptor for object recognition across illumination changes[END_REF]. The main idea of this paper, presented in the next paragraph, consists in applying an affine transform from image space to color space in order to design a local descriptor. Nevertheless, this descriptor requires a rotation invariant local region detection in order to be invariant to rotation. In the context of self similarity extraction, the image (or a part of the image) is dense sampled in order to extract patches at regular positions and to evaluate the similarity between each pair of patches. If the descriptor of each patch is not stable across rotation in the image, the extracted self-similarities will not be invariant to rotation. Consequently, in the second paragraph we propose to extend the approach of Song et al. in order to design a new rotation invariant descriptor.

The spatio-colorimetric descriptor from Song et al. (Song et al., 2009)

Song et al. have proposed a way to extract a descriptor from each detected local region (patch) in an image. The main idea consists in applying an affine transform to the pixels of the considered patch, from the image space to a color space. Thus, considering a pixel P i characterized by the 3D-position

{x Co i , y Co i , z Co i } = {c R i , c G i , c B i }
in the color space Co and the 2D-position {x Pa i , y Pa i } in the patch-relative space Pa so that the center of the patch has {0, 0} for coordinates. Song et al. propose to define an affine transform from the patch space to the color space as:

  m 1 m 2 t x m 3 m 4 t y m 5 m 6 t z     x Pa i y Pa i 1   =   x Co i y Co i z Co i   (1)
where t x , t y and t z are the translation parameters and the m i are the rotation, scale and stretch parameters. This equation can be re-written as follows:

[A f ] × [Pa] = [Co] .
It is based on the coordinates of one pixel but all the pixels of the patch can be accounted by adding columns in the matrices [Pa] and [Co]. Since there exists no such affine transform from the image space to a color space, Song et al. propose to estimate the best one as the least-squares solution:

A f = Co[Pa T Pa] -1 Pa T .
(2)

Once the transform parameters have been determined, they apply the transform to the 4 pixels corresponding to the corners of the patch and whose coordinates in the patch space are {-sx/2, -sy/2}, {sx/2, -sy/2}, {-sx/2, sy/2} and {sx/2, sy/2}, where sx and sy are the width and height of the patch, respectively. The positions of these corners in the color space after applying the affine transform constitute the descriptor:

Descriptor = A f ×   -sx/2 sx/2 -sx/2 sx/2 -sy/2 -sy/2 sy/2 sy/2 1 1 1 1   .
(3) The use of the least-squares solution method provides the discriminating power of the descriptor. Indeed, the resulted destination position of a pixel depends not only on its color but also on the colors and the relative positions of the other pixels of the local region. Thus, considering two patches characterized by the same colors but by different spatial color arrangements, the resulted descriptors will be different. This characteristic is very interesting in the context of object recognition.

Nevertheless, in the context of self-similarity evaluation, the patches are dense sampled without any information about their orientation. So, the x and y axis of the patches are all oriented along the horizontal and vertical directions respectively. In this case, this descriptor is not stable across rotation in the image space and we show in the next paragraph the way to reach this invariance.

The proposed rotation invariant descriptor

We consider two patches Pa 1 and Pa 2 so that the second one is a rotated version of the first one:

x Pa 2 i y Pa 2 i = Rot × x Pa 1 i y Pa 1 i . ( 4
A f 2 = Co[Pa T 2 Pa 2 ] -1 Pa T 2 A f 2 = Co[(Rot.Pa 1 ) T (Rot.Pa 1 )] -1 (Rot.Pa 1 ) T A f 2 = Co[Pa T 1 .Rot T .Rot.Pa 1 ] -1 Pa T 1 .Rot T A f 2 = Co[Pa T 1 .Pa 1 ] -1 Pa T 1 .Rot T A f 2 = A f 1 .Rot T ,
(5) because for any rotation matrix Rot, Rot T .Rot = Identity.

By using these two transforms A f 1 and A f 2 in the equation (3), we can see that the descriptors of the two patches Pa 1 and Pa 2 are different. So these descriptors can not be used directly in order to find rotation invariant self similarities in images.

However, the equation ( 5) shows that the transforms obtained for two patches, the second patch being a rotated version of the first, are related to each other by the rotation applied in the patch space. Our intuition is to use this transform itself as a descriptor after removing the rotation from it. Since this rotation is applied in the patch space, it is a 2D rotation and can be represented by a 2x2 matrix Rot 2x2 . Thus, we propose to rewrite the transform A f k of the patch Pa k , k = 1 or 2, as follows:

A f k   x Pa k i y Pa k i 1   =   mk 1 mk 2 tk x mk 3 mk 4 tk y mk 5 mk 6 tk z     x Pa k i y Pa k i 1   =   mk 1 mk 2 mk 3 mk 4 mk 5 mk 6   x Pa k i y Pa k i +   tk x tk y tk z   = Mk 3x2 x Pa k i y Pa k i + T k 3x1 . (6)
Since each transform A f k is evaluated in the corresponding patch Pa k relative coordinates system (where the center of the patch has {0, 0} for coordinates), the translation parameters in T 1 3x1 and T 2 3x1 are the same and the only variation between A f 1 and A f 2 holds in the Mk 3x2 matrices. Furthermore, from equation ( 5), we can deduce that M2 3x2 = M1 3x2 Rot T 2x2 . Our aim is to remove the rotation term from the Mk 3x2 matrices so that they become identical. Therefore, we propose to use the QR factorization tool. This factorization decomposes a matrix Mk 3x2 into a product of a rotation matrix Qk 3x3 and a triangular upper right matrix Rk 3x2 so that Mk 3x2 = Qk 3x3 Rk 3x2 . Since the rotation matrix is applied in the 2D patch space, it is a 2D rotation and so can be represented by a 2x2 matrix. So we rather propose to apply the QR factorization on the transpose of the Mk 3x2 matrix. By this way, we will obtain Mk T 3x2 = Qk 2x2 Rk 2x3 and hence Mk 3x2 = Rk T 2x3 Qk T 2x2 where the matrix Qk 2x2 contains the rotation part of the matrix Mk 3x2 . Since the matrix Rk 2x3 is not sensitive to rotation variation we have R1 2x3 = R2 2x3 .

To summarize, considering two patches, we propose to:

• evaluate the affine transforms (from image space to color space) A f 1 and A f 2 of the patches by using the Song et al. method (Song et al., 2009) (equation ( 2)), • decompose each transform A f k into two transforms Mk 3x2 (rotation, scale, stretch) and T k 3x1 (translation) (equation ( 6)), • apply the QR factorization on the transposes of the Mk 3x2 matrices giving two matrices Rk 2x3 and Qk 2x2 .

Previously, we have shown that if the second patch Pa 2 is a rotated version of the first one Pa 1 , we have T 1 3x1 = T 2 3x1 and R1 2x3 = R2 2x3 . Consequently, we propose to take these two matrices T k 3x1 and Rk 2x3 as the rotation invariant descriptor for the patch Pa k . Since the matrix Rk 2x3 is a triangular upper right matrix, we consider only the 5 non-zero values among its 6 values. Thus, the descriptor we propose in this paper is constituted by only 3 + 5 = 8 values.

Thus, the advantages of our descriptor is threefold. First since it represents both the colors and their relative spatial distribution in the patch space, it is highly discriminative and so can determine if two patches are similar or not. Second, the time processing required to evaluate the similarity between two patches is very low since each descriptor is constituted by only 8 values. Third, this descriptor is fully invariant to rotation in the patch space. The discriminative power and the rotation invariance property of our descriptor can be checked in the figures 1 and 2.

REPRESENTATION OF THE SPATIAL DISTRIBUTION OF THE ROTATION INVARIANT SELF-SIMILARITIES

We consider one patch Pa 0 in an image and we want to represent the spatial distribution of the selfsimilarities around this particular patch. If in its surrounding, one other patch Pa 1 has similar colors spatially arranged in a similar way as Pa 0 , the similarity between their descriptors will be high, even if there exists a rotation between them in the image space. In this case, 3 values can be used to represent the relative position and orientation of these patches: 2 values ∆x and ∆y represent the translation along the x and the y axis respectively, and 1 value ∆θ represents the rotation angle between these two patches. The translation values are easily obtained by evaluating the differences between the x and y coordinates of the centers of the patches. The ∆θ can be obtained from their respective Qk 2x2 matrix introduced in the previous section. Indeed, these matrices represent the rotation in the image space applied to each patch so that they match the same position in the color space. Consequently if the patch Pa 0 is rotated by an angle θ 0 and the patch Pa 1 by an angle θ 1 in order to match the same position, the ∆θ is just the difference between these two angles. Consequently, we propose to create a 3D structure around the patch Pa 0 whose axis are ∆x, ∆y and ∆θ and to put the value of the similarity between Pa 0 and Pa 1 in the cell whose coordinates are {x 1x 0 , y 1y 0 , θ 1 -θ 0 }, where x k and y k are the position in the image space of the center of the patch Pa k , k = 0 or 1. Likewise, we can do the same for all the patches Pa i , i > 0, around Pa 0 in order to represent the spatial distribution of the self-similarities around Pa 0 . For this, the neighborhood of the patch Pa 0 is discretized into a grid of size 5x5 and the angle axis is discretized into 4 values. The maximal similarity is stored within one cell if several similarities are falling in the same position. This representation is similar to this proposed by [START_REF] Shechtman | Matching local selfsimilarities across images and videos[END_REF]) but since we can find similarities between patches with different orientations, we have added a third dimension for the angle. The dimension of the feature of Shechtman et al. was 4 radial intervals x 20 angles = 80 while our is 100 (5 ∆x intervals x 5 ∆y intervals x 4 angles).

EXPERIMENTS

Experimental approach

The rotation invariance of our self-similarity having been theoretically demonstrated, we propose to assess the discriminative power of the final descriptor and to compare it with the other self-similarities that are classically used in many applications, as mentioned in the introduction. For this purpose, we consider the context of object classification by using the PAS-CAL VOC 2007 dataset (Everingham et al., ). This dataset contains 9963 images representing 20 classes. The aim of this experiment is not to get state-of-theart classification score on the considered dataset, but rather to fairly compare the discriminative powers of the different self-similarity descriptors. In order to test our self-similarity, we propose to use the Bagof-words approach which is based on the following successive steps:

• keypoint detection (dense sampling is used for all tested methods), • local descriptor extraction around each keypoint (we use the 3D structures presented in the previous section for our method), • clustering in the descriptor space, the cluster representatives are called visual words (k-means is used with 400 words for all tested methods), • in each image, each local descriptor is associated with the nearest visual word, • each image is characterized by the histogram of visual word, • learning on the train images and classification of the test images (linear SVM is used for all tested methods). Furthermore, we propose to compare our results with the local self-similarity descriptor [START_REF] Shechtman | Matching local selfsimilarities across images and videos[END_REF] and with the global self-similarity descriptor [START_REF] Deselaers | Global and efficient self-similarity for object classification and detection[END_REF]. For both, we use the codes provided by the authors. For the global self-similarity descriptor, we have constructed the SSH (with D 1 = D 2 = 10) from the image and consider each grid cell as a feature. So, this feature is also of dimension 100. For all the approaches, we reduce the dimension of the features to 32 by applying PCA.

Results

The results are shown in figure 3. In this figure, BOCS stands for Bag Of Correlation Surfaces [START_REF] Deselaers | Global and efficient self-similarity for object classification and detection[END_REF], BOLSS stands for Bag Of Local Self Similarities and BORISS is our proposed approach and means Bag Of Rotation Invariant Self Similarities.

In this figure, we can see that our approach outperforms the two other ones for most of the 20 classes. Furthermore, the Mean Average Precision (MAP) provided by our BORISS is 25% while it is around 18% for the two other approaches. This experiment shows that the self similarities are more efficient to characterize the content of an image if they are invariant to the rotation. Of course, these results are not competitive with the ones provided by SIFT or CNN features, but the aim of these experiments was to show that adding color and rotation invariance into the self-similarity descriptors improves the discriminating power of the final features. These results clearly show that our self-similarity representation is a good candidate to be used as complementary information with the appearance-based features.

CONCLUSION

In this paper, we have presented a new method to represent the spatial distribution of the selfsimilarities in an image. First, we have proposed to extract rotation invariant self-similarities. This extraction is based on a comparison of new spatiocolorimetric descriptors. We have shown that these descriptors extract discriminative information from local regions while being very compact and invariant to rotation. Then, we have proposed a 3D structure to represent the spatial distribution of these selfsimilarities. This structure informs about the translation and rotation there exist between two similar local regions. The experimental results provided by this method outperform those of the classical selfsimilarity based approaches. In this work, we found a way to represent translation and rotation that occur between self-similar regions and as future works we are trying to add the other possible transformation such as scale variation or stretch. Finally, the discriminative color descriptors introduced in this paper could be used as a color texture descriptor since it is representing both the colors and their spatial distributions within the local neighborhood.

  The images 2(c) and 2(d) represent the similarities between the patch 2(b) extracted from the image 2(a) and all the patches in the image 2(a) with the correlation-based method (2(c)) and with our descriptor-based method (2(d)).

)

  By applying the approach of Song et al. on these two patches, we can determine one affine transform for the first patch A f 1 = Co[Pa T 1 Pa 1 ] -1 Pa T 1 and one for the second patch A f 2 = Co[Pa T 2 Pa 2 ] -1 Pa T 2 . From equation (4), we have Pa 2 = Rot.Pa 1 and then:

Figure 3 :

 3 Figure 3: Mean average precision obtained by the three tested approaches on the VOC 2007 database.