Cédric Le Barz

Nicolas Thome

Matthieu Cord

Stéphane Herbin

Martial Sanfourche

EXEMPLAR BASED METRIC LEARNING FOR ROBUST VISUAL LOCALIZATION

Keywords: based image retrieval, supervised metric learning, visual localization, place recognition

published or not. The documents may come

CONTEXT

The problem tackled in this paper is visual localization at a street level [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF] [2] [START_REF] Liu | Finding perfect rendezvous on the go: accurate mobile visual localization and its applications to routing[END_REF]. Visual localization methods differ from each other by the type of features extracted online (2D only [START_REF] Vaca-Castano | City scale geo-spatial trajectory estimation of a moving camera[END_REF] and/or 3D [START_REF] Badino | Real-time topometric localization[END_REF]), the matching method (dedicated or not to large scale [START_REF] Schindler | City scale location recognition[END_REF] [START_REF] Zhang | Location-based image retrieval for urban environments[END_REF]), and the a priori information used (geo-referenced database image [START_REF] Vaca-Castano | City scale geo-spatial trajectory estimation of a moving camera[END_REF], 3D model [START_REF] Liu | Finding perfect rendezvous on the go: accurate mobile visual localization and its applications to routing[END_REF], 2D roadmap [START_REF] Brubaker | Lost! leveraging the crowd for probabilistic visual selflocalization[END_REF], mobile cell phone information [START_REF] Zhang | Location-based image retrieval for urban environments[END_REF],...). Our typical scenario is the precise localization of a vehicle whose approximate localization is known. Our problem is cast to an image retrieval (IR) problem using only 2D features extracted from acquired images and 2D geo-referenced database image (Fig. 1). Exploiting only image content is challenging because, even if query and database images depict the same scene, camera-view points, illumination and colorimetry are different, the scene itself may have changed over time and Fig. 1. Our system aims at answering the following question: knowing a rough position of the vehicle in a street and the scene being observed by the vehicle's camera, can we determine where is it exactly along the street? been occluded. Preliminary experiments made clear that standard image retrieval approaches may not always be selective enough for street areas because the same features tend to be shared by several neighbour images. Standard matching methods can be classified into voting-based strategies [START_REF] Lowe | Distinctive image features from scaleinvariant keypoints[END_REF] and methods relying on the Bag of Words (BOW) model [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. Voting-based methods [START_REF] Lowe | Distinctive image features from scaleinvariant keypoints[END_REF] search for each query image descriptor the N nearest descriptors belonging to database descriptors. Each of these N nearest descriptors votes for a database image. The images having the highest vote number are likely to be similar images. Ultimately, geometrical verification is often used to further improve performances. These methods are effective, but are very time consuming and do not scale well to large databases. BOW-based methods [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] quantify local descriptors of images with a codebook of visual words to generate a visual words histogram. The codebook is previously learned by clustering feature space of a learning image database in K visual words. Several extensions have been proposed, in terms of coding (Vector of Locally Aggregated Descriptors (VLAD) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] or Fischer Vector (FV) [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]), or pooling [START_REF] Avila | BOSSA: extended BoW formalism for image classification[END_REF], or integration of spatial information [START_REF] Lazebnik | Beyond bag of features: spatial pyramid matching for recognizing natural scene categories[END_REF]. BOW-based methods are fast, and have further been optimized to find images in huge database images.

The choice of the visual similarity is a key ingredient for effective image retrieval systems. A common choice is the Euclidean or χ 2 distance to find the images that are most sim-ilar to the query image. Another appealing solution is metric learning, which proves to be useful for many image processing tasks, such as image classification, retrieval or face verification. Metric learning algorithms learn a transformation of data which is optimized for a prediction task, such as nearest-neighbour classification. The metric learning literature is very abundant, and an exhaustive review of existing methods is outside the scope of the paper. The reader can refer to [START_REF] Kulis | Metric learning: A survey[END_REF]. Basically, methods can be classified according to the type of training data, e.g. pairs [START_REF] Xing | Distance metric learning, with application to clustering with side-information[END_REF], triplets [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] or quadruplets [START_REF] Law | Quadruplet-wise image similarity learning[END_REF], and the distance parametrization.

In this paper, we propose an exemplar-based metric learning framework, Exabal, dedicated to robust visual localization in complex scenes such as street images. Our solution is dedicated to street scale localization instead of city scale localization as proposed in [START_REF] Gronat | Learning and calibrating per-location classifiers for visual place recognition[END_REF]. The rationale of Exabal is to learn a local pseudo-distance matrix for each image of the database, so that the distance between a database image and the given query acquired from the same scene is smaller than the distance between this query and other (close) images in the database. To achieve this goal, our method encompasses the following contributions:

• During training, we generate sensible geometric and photometric transformations to model images similar to unknown query images. This offers the possibility to learn features able to discriminate a given dataset image from its neighbours, and at the same time to learn invariance to common transformations occurring at test time.

• The learning of a local metric for each dataset image is cast as a convex optimization problem, which is efficiently solved with a projected gradient descent scheme. Once this off-line procedure is carried out, computing the similarity at test time is very efficient, e.g. much faster than methods based on kNN votes like [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF]. It can also benefits from existing fast indexing structures (e.g. inverted files, search trees).

• Successful experiments reveal the ability of the method to effectively retrieve images in complex street scene. We show that the model learns sensible invariances and discriminating features for localization.

EXABAL METHOD FOR METRIC LEARNING

We consider here the widely used Mahalanobis distance metric D M that is parametrized by the positive semi-definite matrix (PSD matrix)

M ∈ S d + such that the distance between vectorial representations (x j , x k ) ∈ R d × R d of the images (I j ,I k ) is written as follows: D 2 M (x j , x k ) = (x j -x k ) M(x j -x k ) (1)
Learning a pseudo-distance matrix using Eq. ( 1) is equivalent to learning a linear transformation of data, since any PSD matrix M can be decomposed as: M = L L where L ∈ R e×d . The method can be easily extended to non-linear metric learning using kernel methods [START_REF] Kulis | Metric learning: A survey[END_REF].

The overall pipeline of the proposed metric learning scheme is illustrated in Figure 2. The rationale of the method is to learn a local distance matrix M k , as defined in Eq. ( 1), for each image of the database I k , leading to an exemplarbased metric learning scheme.

Exemplar-Based Constraints

Basically, we require that the distance between each image signature x k and other neighbour image signatures of the database x k , k = k, is larger than the distance between x k and a query signature x q representing the same scene as I k .

During training, the main challenge is to find images which are representative of the unknown query images that we have to localize. To achieve this goal, we propose to generate geometric and photometric transformations from I k as proxies for potential test query images.

Formally, let us denote as T the set of considered transformations. For (T

(i) s , T (i) d ) ∈ T ×T , we obtain the transformed images T (i) s (I k ) and T (i) d (I k ) for I k and I k , respectively. We note T s (x k ) and T d (x k ) the vectorial signature of T (i) s (I k ) and T (i) d (I k ), respectively.
During training, we enforce the following constraint:

D M k (x k , T d (x k )) ≥ D M k (x k , T s (x k )) + 1 (2)
The constraint in Eq. ( 2) promotes matrices M k that discriminate I k images from I k images, at the same time as taking into account potential transformations. An appealing property of our constraint generation approach is the ability to produce a large number of constraints by sampling different

T (i)
s and T (i) d transformations, making the optimization of M k (with a potentially large number of parameters) robust to over fitting.

In this paper, we focus on rotations and cropping operations, but T could easily been enriched if required. Each image I k is described by a feature x k corresponding to a BOW vector [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] encoding spatial information [START_REF] Lazebnik | Beyond bag of features: spatial pyramid matching for recognizing natural scene categories[END_REF]. We validate in the experiments (section 3) that the method learn a distance that selects discriminative and spatially localized features, making the similarity measure much more powerful than the distance in the input space.

Optimization

The objective of our learning scheme is to minimize the number of misclassified constraints in Eq. ( 2). Since the direct resolution of this problem is NP-hard, we introduce a standard hinge loss function d for penalizing the violation of each constraint in Eq. ( 2

): d (x k , T s (x k ), T d (x k )) = max [0, 1 -(D M k (x k , T d (x k )) -D M k (x k , T s (x k )))].
In addition, we incorporate into our objective function the following convex loss s for each pair (I k ,T (i)

s (I k )): s (x k , T s (x k )) = D M k (x k , T s (x k ))
. s aims at minimizing the distance between each image and its transformed version, i.e. between similar images. As in [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF], it can be interpreted as a regularization prior. Note that other regularization schemes could also be used, e.g. based on the Frobenius or nuclear norm [START_REF] Mcfee | Metric learning to rank[END_REF].

Our final objective P(M k ) function combines the loss s and d over the whole set of constraints, with a weighting parameter µ:

P(M k ) = (1 -µ) Ts∈T s (x k , T s (x k )) + µ k =k, (T d ,Ts)∈T ×T d (x k , T s (x k ), T d (x k )) (3)
The objective function in Eq. ( 3) is convex with respect to M k . To solve it, we use a stochastic projected gradient descent scheme. After each gradient computation1 , the matrix M k is updated and projected onto the PSD cone if necessary. The algorithm is guaranteed to converge to the global minimum, up to a well-chosen gradient step. In practise, the optimization is fast with reasonable number of constraints and quickly converges.

Localization Model

Once a metric M k is learned for each image I k of the database, the goal of our system at test time is to localize a given query image I q , with vectorial representation x q . To achieve this goal, we assume here that we want to match I q against N given images of the database {I 1 , ..., I N } (for example selected using GPS information). Our system thus output the image I k * , which is the closest to I q , as follows :

k * = arg min k∈{1;N } D M k (x k , x q ) ( 4
)
where D M k (x k , x q ) is the distance between representations of I q and I k images computed with the matrix M k , obtained after training as described in section 2.2. When computing the minimization in Eq (4), there is no obvious guarantee that the different distances D M k (x k , x q ) for different M k are comparable, since each optimization has been performed independently. To alleviate this problem, we normalize each M k , as a post-processing learning step, so that the Frobenius norm of M k is equal to 1. We could use more advanced normalization schemes as proposed in [START_REF] Gebel | Calibrating classifier scores into probabilities[END_REF], but we found it sufficient in our experiments.

EXPERIMENTAL RESULTS

Experimental setup

We built an image corpus from Google Pittsburgh dataset [START_REF]Pittsburgh dataset provided by google for research purposes[END_REF] for image database, and from Google Streetview images for query images [START_REF]Google street view API[END_REF]. These image dataset have been acquired at different time, resulting in strong visual changes for the same scenes. Camera fields of view are also different. From the original corpus, we keep one image every 5m resulting in a corpus of 2215 images. Query images are downloaded from Google Streetview website (resolution of 640x480, field of view of 100 o , camera tilt of 5 o .) We requested one image every 15m resulting in 846 query images. BOW are computed from SIFT descriptors densely extracted: four scales are used 1, 1.5, 2, 2.5 and the step between each descriptor is 4. BOW parameters are the followings: Hard assignment, Sum pooling, L2 Normalization, no tf-idf weighting. Spatial Pyramidal Matching configuration for BOW is 1x1, 2x2. The size of the codebook has been chosen to be 100. The trade-off parameter µ between the two terms s and d of the objective function, was set to 0.5. Image retrieval is performed among N=11 database images, which is equivalent to a localization uncertainty of 50m.

We compared our solution (Exabal) with state of the art IR solutions: a BOW based method with spatial pyramidal matching (BOW), and a kNN votes method like [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF] with and without a geometric consistency verification, respectively noted (kNN+RANSAC) and (kNN).

Results

Achieved performances using the previously described setup, are given in Tab. 1. These results show the interest of exemplar based local metric learning for visual localization.

Compared to (BOW) method, our solution achieves a substantial gain of 12% (from 48% to 60%). Fig. 3 presents some examples where Exabal makes it possible to find the database image (b) that depicts the same scene as the query image (a), whereas (BOW) solution can't (c). Achieved performances validate our objective function defined by Eq. transformations to database images in order to build representative images that likely look like to potential query images. The processing time is slightly higher as the Mahalanobis distance is more complex to compute than an Euclidean distance. Compared to effective but time consuming methods, the proposed solution achieved better performances than (kNN) (from 46% to 58%) and is even slightly better than (kNN+RANSAC) (from 58% to 60%). At the same time, our method is faster: the processing time to process one query (measured with Matlab) is roughly reduced by a 10 factor.

Thereafter, we analyse the reasons of performance improvements. We show that they are due to the selection of discriminative features, the selection of discriminative image area(s) and, the learning of invariance to photometric and geometric transformations.

• Selection of discriminative features and discriminative image area(s) The first advantage of our method is that it selects relevant, i.e. discriminative visual features. To visualize the most discriminative word for a given database image, we compute the eigenvector v 1 of the largest eigenvalue λ 1 of M k that represents the importance of each visual word2 . Fig. 4 shows the visual word having the highest value in vector v 1 . This visual word "window corner" makes it possible to retrieve the good image (b), although many features (the bricks of Fig. 4. The visual word "window corner", that has been learned to be discriminating, improves image retrieval task. the wall) were common between the query image (a) and a neighbour image (c). What's more, as the BOW hold spatial information, we also check that Exabal is able to learn where the most discriminative features are located in the image.

• Learning invariance to photometric and geometric transformations An other advantage of our method is that we learn invariance to photometric and geometric transformations. To demonstrate it, we selected randomly 1000 database images on which various transformations have been applied (i.e. various rotations from -18 • to +18 • around the 3 axes and various crops from 6 to 35 pixels). Thus we generate 10000 query test images I q = T (i) (I k ), that have not been used during training. The mean classification rates for these simulated query images are reported in Tab. 2 for (BOW) and (Exabal) solutions. A classification rate of more than 99% when learned Mahalanobis distance is used confirms our claim concerning invariance to photometric and geometric transformations.

Mean classification rates (BOW)

94.8% (Exabal) 99.1% Table 2. Mean classification rates computed for simulated test images.

CONCLUSION

We proposed a new image retrieval framework dedicated to applications for which geographical position (GPS) of database images are available as well as an a priori approximate localization of the query image. The proposed solution is simple and fast: for each query image, only one BOW has to be computed and N Mahalanobis distances. The proposed framework can also benefit from existing fast indexing methods. We compared our framework with state of the art image retrieval algorithms evaluated on a corpus of 846 queries and 2215 database images. Our solution improves accuracy from 48% for a traditional BOW solution to 60%, while maintaining the same processing time. We plan to incorporate this new framework improving local visual similarity measurements in the system exploiting spatio-temporal constraints induced by vehicle moving as proposed in [START_REF] Barz | Global robot ego-localization combining image retrieval and hmm-based filtering[END_REF]. Finally, even if we use BOW as visual signature, other visual signatures can be easily used, as the recently deep features [START_REF] Razavian | Cnn features off-the-shelf : An astounding baseline for recognition[END_REF] which have been demonstrated to be efficient.

Fig. 2 .

 2 Fig. 2. Creation of simulated similar and dissimilar examples in order to learn for each geo-referenced image database I k a metric M k .

Fig. 3 .

 3 Fig. 3. (a) Query images -(b) Images retrieved with (Exabal) solution -(c) Images retrieved with (BOW) solution.

Table 1 .

 1 3, as well as the way we generate the constraints, i.e. by applying various Mean localisation error, accuracy and time to process one query for state of the art IR algorithms based on Euclidean distance for visual similarity and for our solution (Exabal) based on local learned Mahalanobis distance.

	Method	Loc. error Accuracy Time
	(kNN)	9.5m	46%	16.1s
	(kNN+RANSAC)	6.0m	58%	21.5s
	(BOW)	9.6m	48%	2.1s
	(Exabal)	5.8m	60%	3.0s

This computation is easy since each term is (piece-wise) linear in M k .

M = λ 1 v 1 v T 1 is the nearest rank-1 matrix of M in the 2 norm. Thus D 2 M (x j , x k ) ≈ λ 1 (v T 1 (x j -x k ))[START_REF] Vaca-Castano | City scale geo-spatial trajectory estimation of a moving camera[END_REF] and therefore v 1 weights the importance of visual words.


Cédric Le Barz
email: cedric.lebarz@thalesgroup.com

Nicolas Thome
email: nicolas.thome@lip6.fr

Matthieu Cord
email: matthieu.cord@lip6.fr

Stéphane Herbin
email: stephane.herbin@onera.fr

Absolute geo-localization thanks to Hidden Markov Model and exemplar-based metric learning

This paper addresses the problem of absolute visual ego-localization of an autonomous vehicle equipped with a monocular camera that has to navigate in an urban environment. The proposed method is based on a combination of: 1) a Hidden Markov Model (HMM) exploiting the spatio-temporal coherency of acquired images and 2) learnt metrics dedicated to robust visual localization in complex scenes, such as streets. The HMM merges odometric measurements and visual similarities computed from specific (local) metrics learnt for each image of the database. To achieve this goal, we define some constraints so that the distance between a database image and a query image representing the same scene is smaller than the distance between this query image and other neighbor images of the database. Successful experiments, conducted using a freely available geo-referenced image database, reveal that the proposed method significantly improves results: the mean localization error is reduced from 12.9m to 3.9m over a 11km path.

Introduction

The problem tackled in this paper is the visual geolocalization of a vehicle operating in an urban environment. Visual ego-localization is a key function for autonomous vehicles such as personal service vehicles, self-driving cars, and unmanned aerial systems, as it allows these systems to navigate autonomously within their environment in order to perform their mission. Visual geo-localization or vi- sual place recognition is a challenging task because two images of the same place acquired at different times and with different cameras may show huge appearance differences due to illumination and colorimetry variations (e.g. sunny or cloudy days), camera viewpoints changes, scene modifications (e.g. seasonal changes, building construction) and occlusions (e.g. by cars) (Fig. 2). Robustness to large variability in scene appearance is required for all autonomous systems aiming at long-term operations in both indoor and outdoor environments. It has to be noted that, even if it exists absolute localization systems like GPS, such systems are not robust and precise enough. Furthermore, even if odometric systems, IMU based or visually based, are able to provide relative localization information at low cost, their information is relative to a given position and suffers from drift especially on complex trajectories. It can only be used reliably on small portions of a trajectory and can't be the only source of measurement for absolute localization. We propose a visual geo-localization solution including a novel similarity estimator dedicated to applications for which geographical positions (GPS) of database images are available and an a priori approximate localization of query image is known. The solution aims at localizing precisely the vehicle so that it can follow the trajectory that has been previously defined (Fig. 1).

Related work

Visual geo-localization methods are mainly based on image retrieval (IR) algorithm [START_REF] Schindler | City scale location recognition[END_REF] [12] [START_REF] Knopp | Avoiding confusing features in place recognition[END_REF]. Most of them rely on the extraction of features, that are compared directly (kNN vote) or indirectly (Bag Of Words model) [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][13] [START_REF] Avila | Pooling in image representation: The visual codeword point of view[END_REF] to geo-referenced features database using a distance. Methods mainly differ on the type of features extracted online, the matching method, and the a priori information used (geo-referenced database image, 3D model, 2D roadmap,...). Three different targeted types of application can be distinguished, depending on the targeting localization precision, i.e. world scale localization ( [12][8]), city scale local-ization ( [START_REF] Schindler | City scale location recognition[END_REF] [START_REF] Gronat | Learning and calibrating per-location classifiers for visual place recognition[END_REF]) and street scale localization ( [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF]

[28][2] [3][22][19]).
Some examples of visual geo-localization methods are briefly described hereafter. Schindler et al. [START_REF] Schindler | City scale location recognition[END_REF] presented a method for city scale localization based on the Bag Of Words signature (BOW) using a dataset of street side images. They proposed a greedy algorithm in order to improve the accuracy of image retrieval for large scale database image by optimizing vocabulary trees. Zamir et al. proposed in [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF] a hierarchical method to localize a group of images. SIFT descriptors from database images are indexed using a tree. A nearest neighbor tree search is then computed for each SIFT query image feature. Weak votes are removed and each reliable feature votes for a location. All accumulated spatial votes are then filtered by a Gaussian kernel. The geo-referenced image with the highest number of votes determines the location. In [START_REF] Vaca-Castano | City scale geospatial trajectory estimation of a moving camera[END_REF], the method described in [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF] is improved by interpreting the 2D map votes as a likelihood. This likelihood is then used in a Bayesian tracking filter to estimate the temporal evolution based on the previous state. Both solutions are dedicated to web video annotation, and localization is not realized on the fly. In [START_REF] Badino | Real-time topometric localization[END_REF], the vehicle localization algorithm uses simple visual features and 3D features. The solution requires that a compact map described as a graph is built in a preliminary phase. Nodes include vehicle position at fixed distance interval and visual and 3D features. At runtime, a Bayesian filter is used to estimate the probability of the vehicle position by matching the features extracted from sensors with database features. Their solution uses two lateral cameras and two lateral LIDARs. The same sensors are used during the map building step and the localization step. In contrast, our solution is monocular and uses different cameras for acquisition and reference database. In [START_REF] Milford | Seqslam: Visual route-based navigation for sunny summer days and stormy winter nights[END_REF], the localization is achieved by recognizing temporal coherent sequences of local best matches. These local best matches are based on a Sum of Absolute Difference (SAD) on resolution-reduced and patch-normalized images between last acquire image and M previous images. The proposed solution is robust to extreme perceptual changes. In [START_REF] Pepperell | All-environment visual place recognition with SMART[END_REF], the solution has been improved to provide invariance to vehicle speed, but remains sensitive to important point of view variations. Our solution adresses this problem by learning. In [START_REF] Majdik | Mav urban localization from google street view data[END_REF], authors work on visual similarity for UAV ego-localization. They propose to generate artificial views of the scene in order to overcome the large view-point differences. Nevertheless, spatio-temporal constraint is not taken into account. Loop closure algorithms include place recognition functionnality. One state-of-the-art example is FAB-MAP [START_REF] Cummins | Fab-map: Probabilistic localization and mapping in the space of appearance[END_REF] [START_REF] Cummins | Appearance-only slam at large scale with fab-map 2.0[END_REF]. Authors propose a probabilistic model on the top of bag of visual words to compute the probability that two observations are collected from the same location. The model takes into account the correlation between visual words. Their solution remains sensitive to strong perceptual changes, and the same camera is used for database images and query images. Odometry information has been incorporated into FAB-MAP [START_REF] Maddern | Cat-slam: Probabilistic localisation and mapping using a continuous appearance-based trajectory[END_REF]. Another type of approach is to learn specificities of each place, as our solution that learns a visual similarity measure for each place. In [START_REF] Gronat | Learning and calibrating per-location classifiers for visual place recognition[END_REF], the problem is cast as a classification task, a classifier for each image in the database is trained using per-exemplar SVM approach. In [START_REF] Mcmanus | Scene signatures: Localised and point-less features for localisation[END_REF] the authors propose to learn a bank of detectors for each place, to identify specific scene structures instead of local features.

Our solution is dedicated to street scale localization. As in [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF] [28] [2] [START_REF] Milford | Seqslam: Visual route-based navigation for sunny summer days and stormy winter nights[END_REF] [23], our solution uses spatio-temporal coherency thanks to the use of a Bayesian filter enabling to take into account visual similarities and odometrics measurements. No assumption is done concerning the constant velocity of the vehicle, but as in [START_REF] Zhang | Locationbased image retrieval for urban environments[END_REF] we consider coarse position estimates provided by an odometric sensor and their uncertainties. As in [START_REF] Majdik | Mav urban localization from google street view data[END_REF], we generate artificial view from available geo-referenced database images. Our similarity visual solution, Exabal, uses these artificial views to learn offline, in a supervised way, a local similarity measure dedicated to robust visual localization in complex scenes such as street images. Exabal learns a local pseudo-distance matrix for each image of the database, so that the distance between a database image and the given query acquired from the same scene is smaller than the distance between this query and other (close) images in the database.

Our method encompasses the following contributions:

• We propose a novel local visual similarity measure included within a HMM. The learning of a local metric for each dataset image is cast as a convex optimization problem, which is efficiently solved with a projected gradient descent scheme. Once this off-line procedure is carried out, computing the similarity at test time is very efficient, e.g. much faster than methods based on descriptor votes like [START_REF] Zamir | Accurate image localization based on google maps street view[END_REF]. It can benefit from existing fast indexing structures (e.g. inverted files, search trees).

• During training, we generate sensible geometric and photometric transformations to model images similar to unknown query images. This makes possible the learning of features able to discriminate a given dataset image from its neighbors, and at the same time to learn invariance to common transformations occurring at test time.

• Successful experiments reveal the ability of the method to localize the vehicle within complex street scene. We show that the model learns sensible invariances and discriminating features for localization.

The effectiveness of our approach has been evaluated over a 11 km path using two kinds of images: Google Streetview images [START_REF] Company | Google street view API[END_REF] simulating images acquired online by the vehicle camera and Google Pittsburgh image dataset [START_REF] Company | Pittsburgh dataset provided by google for research purposes[END_REF] as geo-referenced image database.

Exabal-HMM solution

The learnt local visual similarities, provided by Exabal, are included within a Bayesian based solution, a HMM, which is described in details in section 3.1, while our similarity measures based on an exemplar-based metric learning solution is described in section 3.2. The HMM used is similar to the one described in [START_REF] Lebarz | Global robot ego-localization combining image retrieval and hmm-based filtering[END_REF]. It enables to filter out some wrong matches provided by standard image retrieval algorithms, by finding the trajectory that best explains the M past observations and, therefore, current vehicle position. Such solution is an hybrid framework allowing to take into account uncertainties of estimated position, odometric measurements, and visual similarity measurements. random variable setting where the vehicle location at time t is considered as a random variable q t taking values in a discrete set of possible location S j with j ∈ {1, ..., N }. The main modelling hypothesis is that its random behaviour is represented by a HMM.

Position tracking with HMM

Using the classical notations of [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF], the use of a HMM requires the definition of the adequate model λ = {N, M, Π, A, B} where N is the number of states, M is the number of observations, Π is the prior on the initial state (i.e. the estimated position), A is the transition probability matrix between the states and B is the observation probability matrix given some states.

The HMM approach provides a standard way to estimate the most likely state sequence Ŝk , i.e the M successive places, explaining the sequence of observations

O k = {O k-M +1 , ..., O k-1 , O k } : Ŝk = arg max S P (S|O k , λ) (1)
This can be solved with the Viterbi algorithm.

The question is now to design the HMM adapted to the estimate of the absolute vehicle location. This will be detailed in two steps: construction of the state transition matrix A and initial state vector, and computation of the conditional observation matrix B.

State transition matrix and initial state vector

The state transition matrix A and initial state vector are built from knowledge of the odometric system behaviour and vehicle kinematics. From the vehicle kinematics, images are approximately acquired every D meters 1 with an odometric uncertainty of ∆ meters. The image database consists of overlapping images acquired every D meters with D ≤ D. In this setting, the database is therefore assumed to have a bigger sampling rate than the online image acquisition rate. Each possible state location S j is uniquely defined by a geo-referenced database image I j .

The filtering capacity of the HMM depends on the number M of past observations. One critical parameter is the localization uncertainty U which defines the area where the vehicle is supposed to be. This localization uncertainty can be, for example, the initial position uncertainty when the vehicle starts its planned trajectory.

The number of states N , i.e. the number of potentially matching images in the database, the initial state probability Π and the state transition probability matrix A depend on U , D, ∆ and M . They are defined the following way:

• N : Given the putative position of the vehicle Sk , the localization uncertainty U , the approximate displacement D, and the observation number M , the potential states, i.e. the set of database images to consider for matching can be easily determined. 1 For simplicity, D is supposed to be constant, but it could be variable. • A: A = {a ij } where a ij = P [q t+1 = S j |q t = S i ],

1 ≤ i, j ≤ N : To take into account odometric uncertainty ∆ for a displacement D, we defined A as:

a ij = 1 2∆/D rect ∆/D (i -j -( D/D )) (2)

Observation matrix

The observation matrix

B = {b j (k)}, where b j (k) = P [O k at t|q t = S j ], 1 ≤ j ≤ N and 1 ≤ k ≤ M is the probability of observing O k when location is S j . The observation matrix B is computed from visual similarity be- tween the M past observations O k = {O k-M +1 , ..., O k-1 ,
O k } and the set of potentially matching database images I k associated to state/position S j (Fig. 4). Visual similarity is a critical module for such solution. We propose to compute this probability from the similarity measure using the following formula:

b j (k) = α • exp(-a • D 2 j (O k , I j )) (3)
where a is a constant, D j (O k , I j ) is the local visual similarity measure for image I j and α is a normalization con-stant to impose

P (O k |S, λ) • π 1 • k=M k=2 a k-1,k (4)
The first term of Eq. 4 refers to visual similarities between observations and the image database, whereas the second term refers to the dynamics of the vehicle and models spatio-temporal constraints.

Local visual similarity learning

We detail in this section our Exabal module that makes it possible to compute off line, i.e. in a pre-processing step, the local distance D j that is required to compute Eq. 3.

We consider here the widely used Mahalanobis distance metric D j = D Mj that is parameterized by the positive semi-definite matrix (PSD matrix) M j ∈ S d + such that the distance between vectorial representations (x j , x i ) ∈ R d × R d of the images (I j ,I i ) is written as follows: Exabal learns from artificial examples a local distance matrix M j , as defined in Eq. 5, for each image of the database I j , leading to an exemplar-based metric learning scheme. The overall pipeline of the proposed metric learning scheme is described by algorithm 2 and the examples generation is illustrated by Fig. 5.

D 2 j (x j , x i ) = D 2 Mj (x j , x i ) = (x j -x i ) M j (x j -x i ) (5)

Exemplar-Based Constraints

Basically, we impose that the distance between each image signature x j and other neighbor image signatures of the database x j , j = j, is larger than the distance between x j and a query signature x q representing the same scene as I j . Images, which are representative of the unknown query images, are required during training. To this end, we propose to apply geometric and photometric transformations on I j to generate proxies for potential test query images. We note T s (x j ) and T d (x j ) the vectorial signature of, respectively, T

D Mj (x j , T d (x j )) ≥ D Mj (x j , T s (x j )) + 1 (6)
The constraints in Eq. 6 promotes matrices M j that discriminate I j images from I j images, at the same time as taking into account potential transformations. An interesting property of our constraint generation approach is the ability to produce a large number of constraints by sampling different

T (i) s and T (i)
d transformations, making the optimization of M j (with a potentially large number of parameters) robust to over fitting. In this paper, we focus on rotations and cropping operations, but some other modes of scene variations could be explored, as lighting, shadow and seasonal variations.

Each image I j is described by a feature x j corresponding to a BOW vector [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] encoding spatial information [START_REF] Lazebnik | Beyond bag of features: spatial pyramid matching for recognizing natural scene categories[END_REF]. We validate in the experiments (section 4) that the method learns a distance and selects discriminative and spatially localized features, making the similarity measure much more powerful than the distance in the input space.

Optimization

To minimize the number of misclassified constraints in Eq. 6, we introduce a standard hinge loss function d for penalizing the violation of each constraint in Eq. 6:

d (x j , T s (x j ), T d (x j )) = max 0, 1 -D Mj (x j , T d (x j )) -D Mj (x j , T s (x j ))
, as well as the following convex loss s for each pair (I j ,T (i) s (I j )): s (x j , T s (x j )) = D Mj (x j , T s (x j )). s aims at minimizing the distance between each image and its transformed version, i.e. between similar images. It can be interpreted as a regularization prior. It is to be noted that other regularization schemes could also be used, e.g. based on the Frobenius, nuclear norm [START_REF] Mcfee | Metric learning to rank[END_REF] or methods giving an explicit control of the matrix rank as [START_REF] Law | Fantope regularization in metric learning[END_REF].

Our final objective P(M j ) function combines the loss s and d over the whole set of constraints, with a weighting parameter µ:

P(M j ) = (1 -µ) Ts∈T s (x j , T s (x j )) + µ j =j, (T d ,Ts)∈T ×T d (x j , T s (x j ), T d (x j )) (7)
Eq. 7 is convex with respect to M j . We can use a stochastic projected gradient descent scheme to solve it. After each gradient computation, the matrix M j is updated and projected onto the PSD cone if necessary. The algorithm is guaranteed to converge to the global minimum, up to a well-chosen gradient step. In practise, the optimization is fast with reasonable number of constraints and quickly converges.

Similarity measure within the HMM

Once a metric M j is learnt for each image I j of the database, it becomes possible for a given observation O k to compute b j (k) thanks to Eq. 8, where x k is the visual signature for observation O k and x j are the visual signatures of considered geo-referenced images.

b j (k) = α • exp(-a • (x j -x k ) T M j (x j -x k )) (8)
When computing similarities with Eq. 8, there is no obvious guarantee that the different distances D Mj (x j , x k ) for different M j are comparable, since each optimization has been 1 Select database geo-referenced neighbor images I j (j = j ); 2 Generate simulated images by applying some transformations on images I j and I j ; 3 Compute visual signatures of all simulated images, i.e.

T s (x j ) and T s (x j ); 4 From all visual signatures, learn metric M j by optimizing cost function (Eq. 6).

performed independently. To alleviate this problem, we normalize each M j , as a post-processing learning step, so that the Frobenius norm of M j is equal to 1. We could use more advanced normalization schemes as proposed in [START_REF] Gebel | Calibrating classifier scores into probabilities[END_REF], but we found it sufficient in our experiments.

Experimental results

Experimental setup

We built an image corpus from Google Pittsburgh dataset [START_REF] Company | Pittsburgh dataset provided by google for research purposes[END_REF] for image database, and from Google Streetview images for query images [START_REF] Company | Google street view API[END_REF]. These image dataset have been acquired at different time, resulting in strong visual changes for the same scenes (Fig. 2). Camera fields of view are also different. Pittsburgh dataset images have been resized to 640x480, so that their resolutions match the query image resolution. From the original corpus, we keep one image every D = 5m resulting in a corpus of 2215 images. Query images are downloaded from Google Streetview website (resolution of 640x480, field of view of 100 o , camera tilt of 5 o .) We requested one image every D = 15m resulting in 846 query images.

BOW are computed from SIFT descriptors densely extracted [START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF]: four scales are used 1, 1.5, 2, 2.5 and the step between each SIFT descriptor is 4. BOW parameters are the followings: Hard assignment, Sum pooling, L2 Normalization, no tf-idf weighting. Spatial Pyramidal Matching configuration for BOW is 1x1, 2x2. The size of the codebook has been chosen to be 100.

Concerning the parameterization of our software, localization uncertainty U is set to ±100m, which is equivalent to an uncertainty error of ±20 database image. Image retrieval is thus performed among N=41 database images. The odometric uncertainty is set to ∆ = 10m for a mean displacement between two queries of about 15m. The trade-off parameter µ between the two terms s and d of the objective function, was set to 0.5.

Results

We compared our solution (Exabal+HMM) including the similarity measure described in section 3.2 used within a HMM filter described in section 3.1 with two state of the art IR solutions. The first one is a similarity measure based on L2 norm between query and database BOW (L2+HMM), and the second one is based on a similarity computed thanks to the number of SIFT descriptors that matches between the query image and each database images after a RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] geometric filter (Vote+HMM). We also report achieved performances when no HMM filter is used and for different BOW spatial configurations. Performances, i.e. mean localization error, IR accuracy an time to process one query, using the previously described setup, are given in Tab. 1.

These results show the interest of exemplar based local metric learning for visual geo-localization. Compared to (L2+HMM) method, our solution (Exabal+HMM) achieves a substantial accuracy gain of 8% (from 46% to 54%). At the same time, the mean localization error is reduced from 4.9m to 3.9m. Without HMM filter, achieved performances by our solution remains better than a standard IR solution based on BOW compared with Euclidean distance. In that case, Exabal improves performances by 8% (from 40% to 48%).

Achieved performances validate our objective function defined by Eq. 7, as well as the way we generate the constraints, i.e. by applying various transformations to database images in order to build representative images that likely look like to potential query images. The processing time is a slightly higher as the Mahalanobis distance is more com- plex to compute than an Euclidean distance, but at the same time it is less complex than a vote solution. Compared to a vote solution, the time to process one query (measured with Matlab) is roughly reduced by a factor 10. The use of the HMM reduces significantly the mean error localization, because HMM enables to filter out absurd match, i.e. those that do not respect spatio-temporal coherency of the query image sequence. It has to be noted that for the vote experiment, whereas mean error localization is reduced, IR accuracy is not improved: even if absurd matches are removed, correct matches are not found due to a bad similarity measure. The improvement provided by the HMM use confirms that exploiting the spatio-temporal constraint is essential. Furthermore, when the dimension of the visual signature increases (from 100 to 800 in our experiments), then results are slightly better, but this is not the main improvement factor. Fig. 6 are some examples where (Exabal) without HMM filtering makes it possible to find the database image (b) that depicts the same scene as the query image (a), whereas (L2) solution can't (c).

Further insight

Thereafter, we analyze the reasons of performance improvements by (Exabal) only. We first illustrate that learnt metrics make it possible to retrieve the good image database if the query image is close to one of the generated image. Then, we show that improvements are due to the selection of discriminative features and the learning of invariance to photometric and geometric transformations.

• Learnt metrics during training Fig. 7 shows the distances between all similar generated artificial BOW T s (x j ) and x j as well as x j BOW. The learnt metric enables to discriminate all potential generated query images from neighbor images, whereas it was impossible with the Euclidean norm. Indeed, whatever the query simulated image T s (x j ), D Mj (T s (x j ), x j ) remains inferior to D Mj (T s (x j ), x j ). This means that if the signature of the effective query at test time is close to one of the generated queries, then we will be able to retrieve the good image database thanks to the learnt metric. • Selection of discriminative features and discriminative image area(s) The first advantage of our method is that it selects relevant, i.e. discriminative visual features. To visualize the most discriminative word for a given database image, we compute the eigenvector v 1 of the largest eigenvalue λ 1 of M j that represents the importance of each visual word. 2 and therefore v 1 weights the importance of visual words. Fig. 8 shows the visual word having the highest value in vector v 1 . This visual word "window corner" makes it possible to retrieve the good image (b), although many features (the bricks of the wall) were common between the query image (a) and a neighbor image (c). What's more, as the BOW hold spatial information, we also check that Exabal is able to learn where are located the most discriminative features in the image.

M = λ 1 v 1 v T 1 is the nearest rank-1 matrix of M in the 2 norm. Thus D 2 M (x j , x k ) ≈ λ 1 (v T 1 (x j -x k ))
• Learning invariance to photometric and geometric transformations Another advantage of our method is that we learn invariance to photometric and geometric transformations. To demonstrate it, we selected randomly 1000 database images on which various transformations have been applied (i.e. various rotations from -18 • to +18 • around the 3 axes and various crops from 6 to 35 pixels). Thus we generate 10000 query test images I q = T (i) s (I k ), that have not

Conclusion

We proposed a new visual geo-localization solution for autonomous vehicle adapted to applications for which geographical positions (GPS) of database images are available as well as an a priori approximate localization of the vehicle. The proposed solution includes exemplar-based learnt metrics within a HMM. Similarities are simple and fast to compute: for each observation, only one BOW has to be computed and N Mahalanobis distances. Learning method is generic: depending of the final application, transformations used during training can be easily adapted. We demonstrate that learnt similarities select discriminating features, and are able to gain invariance to meaningful transformations. We compared our framework with state of the art image retrieval algorithms evaluated on a corpus of 846 queries and 2215 database images. Our solution improves accuracy from 40% for a traditional BOW solution to 54%, while maintaining the same processing time. At the same time, the mean localization error is reduced from 12.9m to 3.9m. Finally, even if we use BOW as visual signature, other visual signatures can be easily used, as the recently deep features [START_REF] Razavian | Cnn features off-the-shelf : An astounding baseline for recognition[END_REF] which have been demonstrated to be efficient.

Acknowledgment

This work results from a collaboration between UPMC University, Onera and Thales Services SAS.

Figure 1 .

 1 Figure 1. Our system aims at answering the following question: knowing a roughly position of the vehicle in a street and the scene being observed by the vehicle's camera, can we determine where is it exactly along the street?

Figure 2 .

 2 Figure 2. Vehicle images (a) and Google Streetview images (b). Note the impact of different focal lenses, weather conditions, viewpoint changes and the presence/absence of cars in the scene.

3. 1 . 1

 11 General principleAt each time t the vehicle acquires an image O k and receives an estimate of its current position Sk from the odometric system. The goal of the absolute localization algorithm is to produce a better estimate Ŝk of the current vehicle position from the past observations and odometric measurements (Fig.3). The estimator is a function of the M past observations O k = {O k-M +1 , . . . O k } (i.e. the current location estimate exploits a set of observations in a sliding window based approach of length M ) and the estimated position Sk . Estimation is realized in a classical

Figure 3 .

 3 Figure 3. System overview: from the M past observations and associated odometrics measurements as well as a rough position estimate Sk the system combines within a HMM all information to determine the corrected position Ŝk .

Figure 4 .

 4 Figure 4. Observation matrix B : the HMM enables to find the trajectory among these visual similarities taking into account uncertainties of initial estimated position (Π vector) and odometric measurements, i.e. possible transitions (A matrix). Red color means high similarity, while blue color means low similarity.

j=N j=1 b j (k) = 1 .Algorithm 1 :

 11 The determination of D j (O k , I j ) is explained in section 3.2. A summary of the general estimation scheme is presented in algorithm 1. Vision based absolute localization from odometric measurements and acquired images Input: M last past observations O = O k-M +1 , ..., O k , M odometrics measurements d k-M +1 , ..., d k , Estimated position of the vehicle Sk and localization uncertainty U , Odometric uncertainty model to compute ∆, Geo-referenced database images I j and associated metrics M j . Output: M corrected vehicle positions Ŝ = Ŝk-M+1 , ..., Ŝk . 1 Compute A and Π from Sk , U and ∆ and M as explained in section 3.1.2; 2 Select relevant geo-referenced database images from Sk , U , D, and M ; 3 Compute similarities between the M past observations and relevant database images as explained in section 3.1.3; 4 Compute B from similarities with Eq.(3); 5 Apply Viterbi algorithm to solve Eq.(4) to estimate the latest vehicle position Ŝk ; Given λ = {N, M, Π, A, B}, Eq. 4 can be solved. Ŝk = arg max S P (O k |S, λ) • P (S, λ)

Figure 5 .

 5 Figure 5. Creation of simulated similar and dissimilar examples in order to learn for each geo-referenced image database Ij a metric Mj.

  j ) and T (i) d (I j ) ,where T (i) s and T (i) d are a set of image transformations. During training, we enforce the following constraints:

Algorithm 2 :

 2 Local metric learning moduleInput: Database geo-referenced image I j Output: Local metric M j for geo-referenced database image I j .

Figure 6 .

 6 Figure 6. (a) Query images -(b) Images retrieved with (Exabal) solution -(c) Images retrieved with (IR-L2) solution.

Figure 7 .

 7 Figure 7. L2 and learnt Mahalanobis distances between potential query signatures Ts(xj) and xj signatures as well as x j , i.e. signature of neighbor images I j (j = j).

Figure 8 .

 8 Figure 8. The visual word "window corner", that has been learnt to be discriminating, improves image retrieval task.

Table 1 .

 1 Mean localization error, accuracy and time to process one query with and without HMM for our solution compared to state of the art IR algorithms.

	Method Spatial conf.	Loc. error	Acc. Time
	L2 + HMM	1x1 1x1, 2x2 1x1, 2x2, 1x3 4.9m 46% 8.0m 42% 5.3m 44%	7.2s
	Exabal	1x1	4.5m 52%
	+	1x1, 2x2	4.1m 54%	8.6s
	HMM	1x1, 2x2, 1x3 3.9m 54%
	Vote + HMM		4.1m 50% 55,6s
		1x1	17.4m 34%
	L2	1x1, 2x2	14.6m 38%	6.8s
		1x1, 2x2, 3x1 12.9m 40%
		1x1	12.0m 42%
	Exabal	1x1, 2x2	11.3m 46%	8.2s
		1x1, 2x2, 1x3 10.1m 48%
	Vote		11.8m 50% 55,2s

Table 2 .

 2 Mean classification rates computed for simulated test images.


Arnaud Lienhard

Alice Caplier

Patricia Ladret

Fully Automated Facial Picture Evaluation Using High Level Attributes

People automatically and quickly judge a facial picture from its appearance. Thus, developing tools that can reproduce human judgments may help consumers in their picture selection process. Previous work mostly studied the position of facial keypoints to make predictions about specific traits: trustworthiness, likability, competence, etc. In this work, high level attributes (e.g. gender, age, smile) are automatically extracted using 3 different tools and are used to build models adapted to each trait. Models are validated on a set of synthetic images and it is shown that using attributes increases significantly the correlation between human and algorithmic evaluations. Then, a new dataset of 140 images is presented and used to demonstrate the relevance of high level attributes for evaluating faces with respect to likability and competence. A model combining both facial keypoints and attributes is finally proposed and applied to picture selection: which picture depicts the most likable face for a given person?

I. INTRODUCTION

Social psychology studies have shown that people evaluate faces automatically and quickly [START_REF] Willis | Making Up Your Mind After a 100-Ms Exposure to a Face[END_REF], and these first impressions predict social outcomes such as online dating [START_REF] Hancock | Putting Your Best Face Forward: The Accuracy of Online Dating Photographs[END_REF] or electoral success [START_REF] Todorov | Inferences of competence from faces predict election outcomes[END_REF], [START_REF] Berggren | The looks of a winner: Beauty and electoral success[END_REF]. If evaluating a person's expression is subjective and seems difficult to automatize, it is an active research domain leading to many concrete applications: industries may want to analyze people reactions and emotions to an advertisement or a new product.

With the widespread use of digital cameras and smartphones, selecting the best facial picture of a particular person for a given application is a time consuming challenge. Thus, a system providing automatic feedback about images would be an interesting and useful tool. Embedded algorithms such as automatic face and smile detection are already helping consumers to make satisfying shots. However, there are many other cues that have to be considered. A smiling face surrounded by a colorful background would certainly be a good choice when sharing images with friends, while pictures required for professional purposes (visiting cards, resumes) often show a straight face in front of a uniform background. Since these applications mostly imply frontal and good quality images, the proposed model is limited to frontal faces and to images of satisfying quality, for which facial feature detection is possible.

The global evaluation of a facial picture is the combination of all the subjective judgments that a person makes when looking at a face. Studies have shown that face evaluation can be approximated by two dimensions [START_REF] Nikolaas | The functional basis of face evaluation[END_REF], [START_REF] Todorov | Evaluating face trustworthiness: a model based approach[END_REF]: the first trait corresponds to trustworthiness, which is highly correlated to all positive judgments (likability, attractiveness). Dominance is the other dimension and describes how much a face is evaluated as threatening or mean.

In face images, the subject is evaluated with respect to his/her expression, face shape and other cues such as make-up or face adornments. However, at the best of our knowledge, many of these attributes are not considered in automatic face evaluation systems. A first attempt to create a data-driven model of several evaluation traits is discussed in [START_REF] Todorov | Modeling Social Perception of Faces[END_REF]. In their work, 300 faces are generated by the Facegen Modeller software (http://www.facegen.com) with different shape parameters. A subjective experiment is conducted, where participants evaluate each face with respect to a particular trait: aggressiveness, attractiveness, threat, etc. Finally, parameters are fitted to the ground truth scores provided by participants to build a regression model for each social judgment. Several sets of synthetic faces, generated with respect to the models created in [START_REF] Todorov | Modeling Social Perception of Faces[END_REF], are used for experiments and validation in this work.

Besides, behavioral studies have shown that shape is not enough to evaluate a face and reflectance (cues such as skin illumination and texture) plays an important role in face perception [START_REF] Blanz | A morphable model for the synthesis of 3D faces[END_REF]. A more complete model including reflectance parameters is elaborated and validated in [START_REF] Todorov | Validation of data-driven computational models of social perception of faces[END_REF]. However, the faces considered in all their experiments are synthetic and without facial hair, make-up or accessories. Real 3-D scanned faces have been used in [START_REF] Walker | Portraits made to measure: Manipulating social judgments about individuals with a statistical face model[END_REF] to identify relevant shape and reflectance features. Even in recent attempts of automated face expression evaluation in videos [START_REF] Masip | Automated prediction of preferences using facial expressions[END_REF], the use of facial keypoints is still predominant. The disadvantage of these models is that it only takes into account the position of facial keypoints and reflectance parameters.

High level attributes are defined as abstract and global concepts describing an image. They correspond to descriptors that cannot directly be obtained by extracting visual data due to the semantic gap between information contained in pixels and human analysis. A small set of attributes provides more significant information than the relative positions of many facial keypoints: converting pixel level information to high level attributes allows to fill the semantic gap between low level computer understanding and human comprehension. Smiles, presence of glasses, gender or age are example of these features in the particular case of facial images. In this article, evaluation is made with respect to a given context: does the face look friendly? Is it a straight face? Thus, the problem is slightly different from facial expression recognition and the proposed method considers high level attributes instead of low-level descriptors (e.g. Gabor wavelets) that are traditionally used in emotion recognition.

Our claim is that the addition of high level attributes significantly improves the models of facial picture evaluation, which are, at the best of our knowledge, only based on faces described by their keypoints and other pixel level information (texture, illumination). Thus, this work focuses on demonstrating the need of using high level attributes to build efficient facial picture evaluation models. Many attributes (age, gender, presence of glasses, beard, smile, etc) can be extracted automatically by machine learning algorithms. They have already been successfully used in various research domains such as face recognition or verification [START_REF] Kumar | Attribute and simile classifiers for face verification[END_REF] and portraiture aesthetics [START_REF] Li | Towards aesthetics: a photo quality assessment and photo selection system[END_REF]. 3 tools analyzing faces are considered: Betaface (http://betaface.com), SkyBiometry (http://skybiometry.com) and SHORE [START_REF] Ernst | A modular framework to detect and analyze faces for audience measurement systems[END_REF]. Each tool takes a picture as input and provides a set of attributes describing the face.

Sec. II introduces the main steps of the proposed method, including the presentation of databases, feature sets and learning algorithms. Sec. III demonstrates the relevance of high level attributes in the context of face evaluation and Sec. IV applies the method on natural images. Further analysis is given in Sec. V.

II. PROPOSED METHOD

In order to prove that high level attributes are efficient for automatic face evaluation, it is necessary to collect ground truth data and tools to compute the attributes. Synthetic and natural data are described below, followed by the list of attributes obtained from 3 different face analyzers. Learning algorithms are finally applied to fit attributes to the ground truth scores and build facial picture evaluation models.

A. Datasets 1) Synthetic Faces used for Validation: Many datasets containing facial pictures have been built and annotated with respect to criteria such as trustworthiness or dominance. In this section, only synthetic faces are considered, without any extra-facial cues such as hairstyle, beard, glasses or jewelry.

Using human-rated synthetic facial pictures, 7 models of face evaluation are computed in [START_REF] Todorov | Modeling Social Perception of Faces[END_REF] with respect to the following traits: attractive, competent, dominant, extroverted, likable, threatening, trustworthy. For each model, a dataset of 25 distinct faces is created. These faces are manipulated along the respective traits to generate seven variations corresponding to seven levels of the considered dimension, producing sets of 25×7 = 175 images. Subjective experiments revealed that these synthetic faces are greatly correlated with the models [START_REF] Todorov | Validation of data-driven computational models of social perception of faces[END_REF]. 3 variations of trustworthiness for a given face are presented in Fig. 1. In our experiments, 4 datasets corresponding to the following traits are considered: trustworthy, dominant, likable and competent.

2) Human Study on Natural Images: To evaluate our model on natural images, 140 frontal and centered pictures of 20 different persons1 (10 men and 10 women) have been gathered, mostly from the LFW [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF] dataset. A large variety of gaze and expression, facial hair styles or accessories are considered for each identity. Samples are shown in Fig. asked to evaluate each image in the same viewing conditions, with respect to either competence or likability. Images were presented in a random order, after a preliminary learning process where participants had to rate images that are not part of the dataset. A discrete scale from 1 (not at all competent/likable) to 6 (very competent/likable) has been considered, which appeared to be relevant since the Cronbach's Alpha [START_REF] Cronbach | Coefficient alpha and the internal structure of tests[END_REF] value is above 0.96 for both experiments. Finally, 27 participants aged from 20 to 55 rated each image for both criteria. Scores average and standard deviation are respectively 3.3 and 0.47 for competence evaluation, 3.37 and 0.79 for likability.

Two distinct experiments involved participants that were

B. High Level Attributes for Face Evaluation

In this work, attributes extraction is performed by 3 applications provided "as is": the SHORE software [START_REF] Ernst | A modular framework to detect and analyze faces for audience measurement systems[END_REF] and two free cloud based applications: Betaface and SkyBiometry. Each tool T returns a total of N T distinct features. Values may either be discrete (is it a male or a female?) or continuous (how much is the person smiling?). Some features have both a discrete component ("yes" or "no") and a continuous component ("how much?"): Does this person smile (yes or no)? How much (from 0 to 1)?

A total of 63 attributes is gathered: 37 from Betaface, 20 from SkyBiometry and 6 from Shore. A simplified list of these attributes is given in Tab. I. Note that Betaface and SkyBiometry also return a list of facial keypoint positions (respectively 94 and 73 points); detection examples are given in Fig. 3. Thus, it is possible to compare the performance between the use of keypoints and high level attributes (III-B). Attribute sets are first tested separately (III-C) in order to compare the performance of each tool. Then, the 3 sets of values are fused with the keypoints to create a global model (III-D). This global model is finally tested and validated on natural images (IV).

C. Learning from the Data

The statistical models presented in this article have been computed by the OpenCV implementation of the Gradient Boosted Trees (GBT) algorithm. This choice was motivated by the fact that this algorithm is quite robust to the noise introduced in the datasets, including human subjective ratings and errors due to missing or erroneous attribute values. GBT has shown more promising results in our study than Neural Networks (NN), Random Forests (RF) and SVM (see discussion in Sec. V).

Testing the models is performed by 10-fold cross validations for both classification and regression problems. To avoid sampling bias, each experiment is repeated 10 times with randomly chosen images and the final average performance is reported.

III. VALIDATION ON SYNTHETIC FACES

In a first set of experiments, facial keypoints are used to create face evaluation models able to classify faces in seven categories, corresponding to seven levels of the considered trait. Since the synthetic faces are generated by keypoints distortion, models using these features should provide high classification performance (III-B).

Then, attributes provided by each library are tested separately on synthetic faces and compared to the reference models using keypoints (III-C). Attributes are finally concatenated and used to create a new and coherent model, confirming that high level features are promising in the case of facial picture evaluation (III-D).

A. Performance Criteria for Classification

Evaluating performance of classification algorithms needs the use of appropriate criteria, describing both the number and the type of errors that the classifier makes. In the case of multi-class categorization, performance is evaluated by the Cross-Category Error (CCE) and the Multi-Category Error (M CE)

CCE i = 1 N t Nt n=1 I(ĉ n -c n = i)
M CE = Nc-1 i=-(Nc-1) |i|CCE(i)
where N t is the number of test images, N c the number of classes, ĉn the ground truth class, c n the predicted class. i is the difference between ground truth and predicted class and I(.) is the indicator function. Finally, the Good Classification Rate (GCR) is defined by the ratio between the number of images that are correctly classified (CCE 0 ) and the total number of images (N t ). Ideally, GCR should be the highest (close to 1) and M CE the lowest possible (close to 0).

B. State of the Art : Key Points

The synthetic datasets described in Sec. II contain faces that are categorized in 7 levels of each considered traits: trustworthy, dominant, likable and competent. Our first attempt in creating a face model for each trait requires the facial keypoints provided by either Betaface or SkyBiometry. Applying the GBT algorithm to each dataset, the results presented in Tab. II are obtained.

The performance of a random classifier is approximately GCR = 14% and M CE = 400. Low M CE values reported in the table (between 100 and 150) and high GCR (between 30 and 50%) indicate that not only our classifier is able to classify correctly many faces (high GCR), but also makes only minor mistakes (low M CE). This is confirmed by the CCE measures, revealing that the classifier never makes errors of more than 2 levels. It is noticeable that SkyBiometry facial keypoints are slightly more efficient than Betaface's: there are significant differences between both detectors in the case of synthetic images (see Fig. 3). Finally, note that this process can be fully automated without the use of computed generated faces [START_REF] Todorov | Validation of data-driven computational models of social perception of faces[END_REF] or 3-D face scanners [START_REF] Walker | Portraits made to measure: Manipulating social judgments about individuals with a statistical face model[END_REF].

C. Contribution of High Level Features

The principal contribution of this article is the use of high level attributes (see Tab. I) for facial picture evaluation. In order to have an idea of the ability of high level attributes to classify face pictures, the datasets presented above are going to be tested using one tool at a time. Classification results are presented for each feature set in Tab. III. Again, results are significantly higher than chance. In all the experiments, the values of CCE i for i < -1 and i > 1 are very close to 0, showing that if there are some classification mistakes, they do not exceed one category. Note that Betaface and SkyBiometry produce equivalent results, while SHORE's attributes are less discriminant. This is due to the lack of many relevant facial attributes in SHORE, especially the presence of a smile. Performance is slightly lower using attributes instead of facial keypoints on synthetic datasets since they were originally created by keypoints manipulation and are therefore naturally efficiently described with keypoints. The following paragraph shows that global performance can be enhanced by concatenating the three sets of attributes and the keypoints information.

D. Combining Attributes to Enhance the Model

In the following experiments, high level attributes obtained from different tools are concatenated and used for learning. This is called "early fusion" and is opposed to "late fusion", which consists in getting first 3 models based on each set of features and combining the results. In our case, early fusion produces better results since each attribute set contains exclusive relevant attributes.

It is possible to increase global performance by adding the locations of the facial features in the global feature set, taking both low and high level features into account. Fig. 4 shows the classification errors for the model on Likable and Competent datasets and compares performance of keypoints, attributes and the entire set (both keypoints and attributes). Fused high level attributes are as efficient as facial keypoints, resulting in approximately the same good classification rate (GCR = 35%) and 1-category error (50%). Combining features increases performance for both datasets (GCR = 40%) and reduces 2-category error (from 10 to 2%). This last result is promising since it shows that high level attributes provide additional information on synthetic datasets that are based on keypoints manipulation, and are thus likely to be of great help for natural images.

IV. APPLICATION ON NATURAL IMAGES

The dataset of natural images presented in Sec. II provides a final validation of the proposed model. Likability and competence have been chosen as face evaluation criteria since we have the intuition that they fit to several applications: likable faces have more success on social media, while competent looks are likely to be used in professional networks. Since each picture has a ground truth likability or competence score, it is possible to build regression models. This section validates the use of high level attributes in the case of natural faces, and shows that facial keypoints are significantly less efficient (IV-B). An example of picture selection method is then presented, showing that it is possible to automatically and efficiently select or remove images fitting a given application (IV-C).

A. Performance Criteria for regression

Regression performance is measured by Pearson and Spearman correlations. Pearson correlation R is defined as N t (N 2 t -1) where d n = ŝn -s n is the rank difference between variables. Pearson's measure quantifies how much the data are linearly correlated and Spearman's rank correlation tells if the data are monotonically correlated. Values close to 1 result from correlated data and 0 means that the data are not correlated.

R = Nt n=1 (ŝ n -s) • (s n -s) Nt n=1 (ŝ n -s) 2 • Nt n=1 (s n -s) 2

B. Impact of High Level Attributes on Natural Images

In the case of natural pictures, it is much less efficient to rely exclusively on facial keypoints: many other facial cues play a role in face evaluation: hairs, beard, glasses, etc. This is confirmed by the experimental results presented in Tab. IV. For both likability and competence, using attributes instead of keypoints enhances the performance: correlation increases respectively from 0.6 to 0.8 and 0.4 to 0.5.

Another observation is that the performance of the competence model is lower than the likability model. Several reasons can explain this. First, likability scores present a higher standard deviation (0.8 versus 0.5 for competence), showing that even humans better identify likable faces than competent ones. Plus, in the case of likability, some of the high level attributes (smile, mood) are extremely discriminant, whereas many cues that play a significant role in competence evaluation are not considered in the feature set (eg. clothes, background). This is discussed in Sec. V. By combining attributes and facial keypoints, it is possible to enhance the competence evaluation model and obtain a correlation of 0.54 (0.5 with attributes only). Likability correlation between ground truth and predicted scores reaches a value of 0.84 (0.83 with attributes only). Fig. 5 presents the regression cloud points and shows the correlation between ground truth and predicted scores. In the case of likability, the prediction seems to be very accurate, even if there are still several outliers. These prediction errors are not only due to some missing attributes in the feature space (background or reflectance cues are not considered), but also to some erroneous measurements. Examples of erroneous measurements are given in the following paragraph, which presents an example of a possible application of this method and its limits.

C. Application to Picture Selection

Automated picture selection of a given person for a particular application is a practical example that may benefit from the proposed method and its results. Some people have hundreds of pictures from which they want to select a small set that is relevant for a given application: facebook profile picture, professional purposes like visiting cards, etc.

While our model is accurate when dealing with likability (Pearson and Spearman correlations above 0.8), many biases make the competence evaluation more difficult (correlations between 0.5 and 0.6). This is discussed in Sec. V, and only the likability trait is considered in this section.

Scoring pictures with high level attributes enables the selection of a small number of images: what are the 10 most likable faces in the entire set? Using the dataset containing 7 different pictures for each of the 20 people, the following experiment is made. First, a model is learned using 19 persons (133 images). Then, the images of the last person are scored with respect to likability. Face likability ranking for a given person is displayed in Fig. 6 and Tab. V. It can be observed that a face judged as likable by humans is evaluated as likable by the algorithm (pictures d to f). Smiling faces are considered as likable by both humans and the algorithm. Even faces where there is no obvious smile (d, f) are correctly evaluated by the algorithm. This can happen thanks to the use of other criteria, such as eyebrows shape and position. Picture a predicted score is far from ground truth since the algorithm misreads the facial expression and considers the presence of a smile. Faces b and c, considered as not likable by humans with ground truth scores of respectively 1.96 and 2.22, are correctly evaluated by the algorithm (respectively 2.64 and 2.56). Using the model and a particular threshold corresponding to a given score or pictures to select, it is possible to automatically remove unwanted pictures (in this case, the 3 images in the left), or to select a few good-looking images. Only few images are not correctly scored (picture a) due to the errors made through feature computation, which is one of the limits to the proposed model.

V. DISCUSSION

If GBT provides the best regression performance in the case of natural images for the proposed dataset (0.83 for likability), models based on RF, SVM and NN can also be considered and obtain, in the same experimental conditions, correlations of 0.81, 0.74 and 0.72. The same observation can be made for competence evaluation: GBT and RF output the optimal performance (0.5), ANN and SVM are slightly below (0.46). Optimizing the parameters may enhance the performance since only OpenCV default parameters have been considered in our experiments.

Using high level attributes to learn about face social perception is not only efficient, but may also be used to see what kind of features are helpful to create good models. The knowledge of relevant attributes and facial keypoints positions may be of great help in other applications like photo editing. By rating pictures and telling which attribute is missing or makes the picture perfectible, it is possible to perform automated corrections and produce modified facial pictures that fit nicely to a given application. To have an idea The RReliefF algorithm is implemented as described in [START_REF] Robnik | Theoretical and empirical analysis of ReliefF and RReliefF[END_REF] and is able to deal with both discrete and continuous data, assigning a weight to each attribute. Higher weights mean discriminant attributes. Tab. VI presents the most discriminant attributes and their weights for likability and competence evaluation for natural images. Synthetic images are not considered because several facial cues are missing: glasses, mustache, eyes closeness, etc.

As it has been observed in Sec. III, smile and mood measures are by far the most discriminant in the case of likability evaluation, followed by age estimation and gender. It is even possible to make accurate predictions using only these measures, resulting in R = 0.76, instead of 0.84 for the entire set. This is an interesting result since computing only 2 measures is easier and quicker, leading to many concrete applications involving real-time detection.

Smiles and emotions also play a role in competence evaluation, as well as criteria such as glasses, beard, followed by age and gender evaluation. Values related to eyes are the most relevant attributes in the case of competence evaluation. This is not surprising: images with closed eyes are not used in any real life application, especially when a straight face is required. Note that high correlation between face evaluation and a particular attribute does not mean that people having this attribute are likely to be more competent or likable. It can only be concluded that the algorithm is able to reproduce human preconceptions about face evaluation. There may be biases in the dataset as well: if several men are presented wearing suits, the model will predict men as more competent, and this cannot be generalized. This kind of bias would be reduced by the introduction of new features taking clothes, jewelry or background into account.

VI. CONCLUSION AND FUTURE WORK

In this article, high level attributes are used to evaluate facial pictures. It has been shown that these features are more efficient than keypoints. Even on images created artificially using face grids based on keypoints, facial attributes perform as well as models based on keypoint positions. Plus, combining both facial keypoints and high level attributes increases the classification performance on synthetic faces.

In the case of natural images, accurate models can be elaborated to judge faces on different traits. Likability evaluation is precise enough to be used in real life applications. Our algorithm can automatically assess a face's likability, except for a few images where it is difficult to measure efficiently facial attributes.

Competence is harder to evaluate accurately since our perception relies on more subtle cues which are not encoded in the feature set: clothes and background have to be considered in future work. Note that performance can be increased by the use of bigger datasets since it is difficult to build a generic model with only 140 images.

Finally, combining the proposed method with models of image quality and aesthetics would enable to assess both face evaluation and image visual appeal. The development of a standalone and fully automated software able to both analyze and provide feedback about facial pictures would make this research helpful for various applications, from face social perception to automatic photo selection or editing.

Fig. 1 .

 1 Fig. 1. Examples of synthetic faces manipulated for trustworthiness. From left to right: untrustworthy, neutral and very trustworthy.

Fig. 2 .

 2 Fig. 2. Examples of faces considered in the proposed dataset.

Fig. 3 .

 3 Fig. 3. Examples of facial keypoint positions for synthetic and natural images. a) and c) show Betaface points, b) and d) SkyBiometry points.

Fig. 4 .

 4 Fig. 4. Classification errors (CCE) for likability and competence, using different feature sets: facial keypoints (red), high level attributes (green) and global feature set (attributes and keypoints, blue).

Fig. 5 .

 5 Fig. 5. Predictions for both competence and likability models.

Fig. 6 .

 6 Fig. 6. A set of 7 images from the same person (LF W dataset).

TABLE I SIMPLIFIED

 I LIST OF HIGH-LEVEL ATTRIBUTE CATEGORIES COMPUTED BY EACH TOOL. THE NUMBER OF VALUES (DISCRETE OR CONTINUOUS) DESCRIBING EACH CATEGORY IS REPORTED IN THE GREEN CELLS.

		Gender	Age	Smile	Mood	Beard	Mustache	Glasses	Eyes	Mouth	Eyebrows	Nose	Skin	Hair	Shape
	Betaface	2	1	3		3	3	3	4	3	3	2	2	5	3
	SkyBiometry	2		2	8			4	2	2
	SHORE	1	1		1				2	1

TABLE II EXPERIMENTAL

 II RESULTS FOR 7-CLASS CATEGORIZATION USING EITHER BETAFACE OR SKYBIOMETRY FACIAL KEYPOINTS

		Betaface	SkyBiometry
		GCR	M CE	GCR	M CE
	Trustworthy	0.40	128	0.39	116
	Dominant	0.39	117	0.49	92
	Likable	0.28	158	0.34	139
	Competent	0.31	152	0.39	121

TABLE III AVERAGE

 III EXPERIMENTAL RESULTS FOR 7-CLASS CATEGORIZATION. ONLY HIGH LEVEL ATTRIBUTES ARE CONSIDERED.

		Betaface	SkyBiometry	SHORE
		GCR	M CE	GCR	M CE	GCR	M CE
	Trustworthy	0.31	145	0.34	143	0.23	198
	Dominant	0.44	105	0.40	114	0.34	145
	Likable	0.30	159	0.36	137	0.19	230
	Competent	0.36	134	0.35	137	0.25	212

TABLE IV AVERAGE

 IV PERFORMANCE FOR NATURAL IMAGE REGRESSION, USING EITHER KEYPOINTS OR COMBINED HIGH LEVEL ATTRIBUTES

		B. Keypoints	S. Keypoints	HL Attributes
		R	ρ	R	ρ	R	ρ
	Likable	0.63	0.64	0.50	0.51	0.83	0.83
	Competent	0.36	0.38	0.38	0.40	0.5	0.53

TABLE V GROUND

 V TRUTH AND PREDICTION LIKABILITY FOR IMAGES IN FIG. 6.

	Image	a)	b)	c)	d)	e)	f)	g)
	Gr. Truth	1.59	1.96	2.22	3.38	3.56	3.59	4.04
	Prediction	3.15	2.64	2.56	3.33	3.72	3.42	3.94

TABLE VI RELIEF

 VI VALUES OF THE MOST DISCRIMINATIVE ATTRIBUTE CATEGORIES FOR BOTH LIKABILITY AND COMPETENCE EVALUATION.

		Smile	Mood	Eyes	Beard	Gender	Age
	Likability	0.14	0.19	0.08	0.08	0.09	0.08
	Competence	0.11	0.11	0.15	0.08	0.09	0.06
	about relevant features in our studies, dimension reduction
	algorithms have been applied and the most relevant features
	are presented below.

Unfortunately, the French law does not allow us to make this database publicly available.