Thi Le Nhung Nguyen-Deroche

Mohamed Saad

Marie-Christine Gromaire

Laurent Moulin

Françoise Lucas

Quality of roof harvested rainwater from houses in Île-de-France area, France

Bacteriological and physico-chemical water quality parameters were measured in rainwater from 10 harvesting tanks, belonging to two types of rainwater harvesting systems (outside tanks for garden watering and underground tanks for both outdoor and indoor uses) in Île-de-France area (France). The presence of fecal coliforms, enterococci, Pseudomonas spp., coliforms, total flora at 22°C and 36°C and total DAPI direct counts showed a microbiological contamination in water and sediment samples for both tank types. However, the harvested rainwater quality suited some existing water quality guidelines for different non-potable purposes (bathing water or reused wastewater). To our knowledge, the presence of microorganisms in sediment compartment in rainwater harvesting tank has been studied for the first time here. Results showed that the sediment could be a reservoir of re-contamination for some microbial species, which would survive in the sediment and may be resuspended in the water column. In parallel, physical-chemical parameters (temperature, turbidity, conductivity, pH and dissolved organic carbon) of collected rainwater were found in the ranges reported in the literature. Algal blooms, principally green algae, occurred in the outside tanks during spring and summer as shown by the high chlorophyll levels (the highest chlorophyll content reached 209.8 µg/L with a water pH of 9.37). Nitrate and phosphate concentrations in water samples were low (respectively less than 5 mg/L and 0.5 mg/L) but high enough to support the development of microorganisms and especially photosynthetic microorganisms in the outside tanks. The difficulty to evaluate the microbial quality of roofharvested rainwater due to the lack of suitable quality standards is underlined. Depending on the usage of the harvested rainwater, some treatments may be needed to get a better microbial quality and direct measurements for pathogens may be also needed to establish whether or not such harvested rainwater is safe for different types of uses.

Introduction

Harvesting and stocking rainwater for household uses becomes popular in France, not only in rural but also in urban and suburban areas. The Paris region and its neighborhood (Île-de-France area) is no exception to this trend. The Île-de-France area is the most populated region (11.6 millions) accounting for 18.5% of the population of France and the most densely populated (966 residents/km 2 ) of France. There are an increasing number of individual houses equipped with tanks to harvest rainwater. Harvested rainwater is used for garden watering, [START_REF] Nguyen-Deroche | Quality of roof harvested rainwater from houses in Île-de-France area[END_REF]. Quality of roof harvested rainwater from houses in Île-de-France area, France.

2

floor and car washing or other advanced uses like toilet flushing, laundry washing and some other advanced uses. But little is known about the sanitary risk it represents. Microbiological and chemical quality of roof-harvested rainwater could be impaired by animal droppings, moss, lichens, windblown dust, and particulates from urban pollution. Knowledge on quality of roof-harvested rainwater and its evolution in tanks could help to prevent potential risks associated with its different uses. However, few data concern the microbiological quality of roof-harvested rainwater in France.

Our research project aims to measure the physical-chemical and microbial quality of collected rainwater and to evaluate their evolution depending on storing type and use. Two case studies will be discussed: the outside tanks for outdoor utilization and the underground tanks for outdoor and indoor utilizations (toilets flushing, laundry washing and other advanced uses). The presence of fecal coliforms, enterococci, Pseudomonas, coliforms, total flora at 22°C and 36°C and total DAPI counts will be analyzed in two types of samples collected (water and sediment). In parallel, physical-chemical parameters (temperature, turbidity, conductivity, pH, dissolved organic carbon (DOC) and chlorophyll content) of collected rainwater will be monitored in order to understand the evolution mechanism of water stored in tanks.

Description of the region and categories of tank

Île-de-France area has a temperate climate and its precipitation is close to 600 mm. A total of ten individual houses were chosen to conduct all sampling campaigns: five houses in Champigny-sur-Marne (Val de Marne, France) and five houses in Chaumontel (Val d'Oise, France). These sites represented interesting model situations for evaluating rainwater quality. In Champigny-sur-Marne, the county administration installed unique model of outside tanks in 30% houses for roofs rainwater harvesting. In Chaumontel, all houses of a recent block were equipped with an underground tank. For each category of tank (outside or underground), all sampled houses uniformly endured the same weather condition during sampling period.

For outside tanks, rainwater was harvested in a four year old model of 800 litters made of polyethylene high density -PEHD for different outdoor uses. For underground tanks, two to four year old PEHD models had volumes varying from 3 000 litters to 5 000 litters and possessed a screening box at the entrance. The harvested rainwater was used for outdoor use, toilet flushing, laundry washing, bathing (in one house) and swimming pool filling (in one house). All houses possess a tiled roof which was not cleaned and chemically treated.

Materials and methods

Rainwater sampling was processed after cleaning the tap three times with ethanol. The sediment was sampled using the Sigma SD900 Potable Sampler. A plastic pipe was inserted into the tank to reach the sediment which was sucked by the pump and collected in a sterile plastic tube. For outside tanks, sampling campaigns were carried out in the period from April to October when harvested rainwater was frequently used. For underground tanks, samples were performed in the period from December to February.

The physical-chemical parameters were only performed in rainwater. Some parameters (temperature, conductivity and pH) were measured in situ by using the WTW Multi 340i/SET. Dissolved organic carbon concentration was evaluated using a1010 O.I.Analytical total Organic Carbon Analyzer. Nitrate and phosphate contents were estimated by the Palintest Photometer 7000se, after sample filtration on Whatman GF/F membrane (0.7 µm pore size, 47 mm diameter). Turbidity measurement was performed by the HACH 2100p turbidimeter in the laboratory. For rainwater samples of outside tanks, the chlorophyll content was measured using Lorenzen method and performed by the JASCOFP-750 spectrofluorometer and the PERKLIN ELMER UV/VIS Spectrometer lambda 11.

For bacterial parameters, all samples (rainwater and sediment) were collected and analysed in sterilized equipments. The samples were transported in cool isothermal boxes and processed within 24h. Fecal coliforms and coliforms, intestinal enterococci and Pseudomonas were analyzed by membrane filtration following the international standard methods ISO 9308-1, ISO 7899-2 and ISO 16266 respectively. Results were expressed as colony-forming units (CFU) per 100 ml of sample. When necessary, dilution was done to reach a countable number of colonies on plate. For culturable microorganisms, the standard method ISO 6222 was performed by counting the colonies formed in nutrient agar medium culture after aerobic incubation at 36°C and 22°C. Results were expressed as CFU per ml of sample. Total cells were directly counted on black polycarbonate filters (0.2 µm pore size) by fluorescent microscopy after staining with 4′, 6-diamidino-2-phenylindole (DAPI). All parameters were evaluated over a total of at least five houses. All results were statistically analysed using PAST software 1.88 [START_REF] Hammer | PAST: Paleontological Statistics Software Package for Education and Data Analysis[END_REF].

Results

Physical-chemical parameters measurements

Results for physical-chemical parameters of rainwater from outside and underground tanks showed high variability between houses and tanks (table 1). The temperature of rainwater stocked in underground during winter sampling campaigns was around 8°C. The average pH value measured in rainwater of outside tanks was at a base level, 8.67 (7.64 minimum and 9.38 maximum), while the average pH of rainwater from underground tanks was lightly acidic, 6.21 (5.49-6.8). The nitrate content was within the same range in both types of tank. The average amount of chlorophyll content in rainwater from outside tanks was 57.4 µg/L (0.3 minimum and 209 maximum). 4

Results for indicator of faecal contamination and total DAPI counts of rainwater and sediment from two types of tank were presented in table 2. For outside tanks, the average means for each indicator bacterial group (total coliforms, fecal coliforms and enterococci) were respectively 303, 2 and 2 per 100 ml for rainwater and 24004, 67 and 0 per 100 mL for sediment. The presence of Pseudomonas spp. was high in sediment (table 2). For underground tanks, the rainwater was characterized by an average mean level of 373 cfu/100 mL for total coliforms, 31 cfu/100 mL for fecal coliforms and 109 cfu/100 mL for enterococci. The level was high for sediment samples: 19041, 667 and 61 cfu/100 mL for total coliforms, fecal coliforms and enterococci, respectively. The presence of Pseudomonas was very important in both rainwater and sediment. The total DAPI count was at the same range of rainwater sampled in both types of tanks. Overall the concentration of microbes was generally higher in sediment than in rainwater whether outside tanks or underground tanks. We found a difference in the level of total coliforms, fecal coliforms, culturable microorganisms at 22°C and culturable microorganisms at 36°C between rainwater from outside tanks and from underground tanks.

Discussion and conclusion

The importance of individual houses in Île-de-France (about 30%) makes this region the greatest potential for development of installations of rainwater collection systems. In France, harvested rainwater is used not only for garden watering and floor cleaning but also for toilet flushing, laundry washing and other advanced uses. In this study, harvested rainwater of all our sampling sites is not used for drinking purpose. Since there is no standard for the microbiological quality applied for harvested rainwater, the comparisons of rainwater quality between studies become difficult. We thus compare harvested rainwater quality to some existing microbiological water quality levels required in France and Europe for potable and non-potable uses and some examples of rainwater quality for toilet flushing (in Canada, Japan, Germany, United Kingdom and United Stated of America) (table 3).

The high level of pH around 8.67 of rainwater harvested from outside tanks could be due to the algal development throughout the photosynthesis. This phenomenon was confirmed by the presence of algae and high content of chlorophyll in rainwater. In one outside tank where pH was 9.37 and the chlorophyll content was 209.8 µg/L, we observed the green coloration of stocked rainwater. This chlorophyll content was high in comparison to the one found in water from the trophic lake (2-90 µg/L; [START_REF] Thiemann | Determination of Chlorophyll Content and Trophic State of Lakes Using Field Spectrometer and IRS-1C Satellite Data in the Mecklenburg Lake District, Germany[END_REF]. The algal development could be promoted by the elevated level of temperature and light because all outside tanks were installed along the house wall and without protection against the sun. Algal blooms occurred in outside tanks during the spring and summer as shown by the chlorophyll levels.

The cyanobacteria were always under represented; mainly green algae dominated the bloom (data not shown). The average pH of rainwater from underground tanks was slightly higher than the level of ambient rainwater (5.9) measured by [START_REF] Mendez | The effect of roofing material on the quality of harvested rainwater[END_REF] showing that tile-roof runoff and stagnation in PEHD tanks only slightly changed the pH. Conductivity remained at low level in both types of tank which showed that harvested rainwater was not very charged by dissolved salts or other impurities from the tile-roof, gutters and pipes. Turbidity seemed more acceptable in rainwater harvested from underground tanks compared to outside tanks, being below the values were reported by other authors (10-56 NTU by [START_REF] Yaziz | Variations in rainwater quality from roof catchments[END_REF]5-35 NTU Mendez et al., 2011). DOC was found in low levels in comparison with literature results which varied from 2 to 56 mg/L [START_REF] Mendez | The effect of roofing material on the quality of harvested rainwater[END_REF][START_REF] Yaziz | Variations in rainwater quality from roof catchments[END_REF]). The nitrate and phosphate contents were also low but this level of nitrate and phosphate were high enough to support the development of microorganisms and especially photosynthetic organisms in the outside tanks.

The average of each indicator bacterial group (total coliforms, fecal coliforms and enterococci) measured in rainwater in both types of tank was found in ranges reported in previous studies [START_REF] Savill | Enumeration of Campylobacter in New Zealand recreational and drinking waters[END_REF][START_REF] Simmons | Contamination of potable roof-collected rainwater in Auckland, New Zealand[END_REF][START_REF] Vasudevan | Bacteriological Quality of Water in DRWH[END_REF][START_REF] Evans | Wind, rain and bacteria: The effect of weather on the microbial composition of roof-harvested rainwater[END_REF][START_REF] Evans | Rainwater tanks and microbial water quality: Are the indications clear[END_REF][START_REF] Vialle | Evaluation of a household rooftop rainwater harvesting system in France: qualitative and quantitative monitoring of water used for authorised applications-Fist results[END_REF][START_REF] Mendez | The effect of roofing material on the quality of harvested rainwater[END_REF]. These levels all [START_REF] Nguyen-Deroche | Quality of roof harvested rainwater from houses in Île-de-France area[END_REF]. Quality of roof harvested rainwater from houses in Île-de-France area, France.

6

exceeded the mean guideline for drinking water purpose but it was below the level of guidelines for bathing water and reuse water (table 3). The average of total flora at 22°C and 36°C was within the levels found by [START_REF] Rosillon | Survey relating to the quality of rainwater stored in cistern for domestic use in Wallonia (Belgium)[END_REF] an [START_REF] Amin | Roof-harvested rainwater for potable purposes: Application of solar collector disinfection (SOCO-DIS)[END_REF] but remained low in comparison with the levels found by [START_REF] Simmons | Contamination of potable roof-collected rainwater in Auckland, New Zealand[END_REF], [START_REF] Birks | Microbiological water quality in a large in-building, water recycling facility[END_REF] and de [START_REF] De Gouvello | Récupération et utilisation de l'eau de pluie dans les opérations de construction[END_REF], demonstrating the importance of other external parameters on the evolution of water composition (i.e. rain quality, geographic area, tank composition, intrinsic bacterial flora…). The presence of Pseudomonas observed in our study remained lower than in previous reports [START_REF] Uba | Rainwater quality from different roof catchments in the Port Harcourt district, Rivers State, Nigeria[END_REF][START_REF] Evans | Rainwater tanks and microbial water quality: Are the indications clear[END_REF] even for sediment samples. The levels of total coliforms, fecal coliforms, enterococci and total flora at 22°C and 36°C found different between outside tanks and underground tanks could indicate the role of environmental conditions in the survival of these microorganisms however the samples were collected at different seasons, which made difficult to compare the two kinds of tanks. The level of faecal indicators remaining lower in outside tanks than underground tanks supposed that this could be reduced in such condition. In our case, we thought the variation of temperature, high pH and the presence of microalgae could play an important role in reducing these microorganisms. However, the total flora at 22°C and 36°C remaining lower in underground tanks than in outside tanks could be due to stable and low temperature in inside of this last one. Although the levels of total flora at 22°C and 36°C were changed, total DAPI counts were comparable in both types of tanks. This indicated that the different environmental conditions in two types of tanks changed the microbial composition in stocked rainwater. For the first time to our knowledge, the presence of microorganisms in sediment compartment in rainwater harvesting tank has been studied. We observed a correlation between fecal coliforms and Pseudomonas spp. densities in sediments and water supported the hypothesis that the sediment compartment could be a reservoir of recontamination for some microbial species which would survive in the sediment and may be resuspended in the water column. However, we need more data analysis to confirm this statement.

Statistical comparison between the physico-chemical and bacterial parameters did not show significant correlation ship between nitrate content and bacterial parameters (data not shown).

No solid conclusion could be made if the higher nitrate content is correlated with higher levels of some bacterial parameters. Further analysis with more samples is needed in order to establish a better understanding of the correlation between the parameters in rainwater and in sediment and between the physical-chemical parameters and bacterial parameters in rainwater.

In our study, the harvested rainwater was used only for non-drinking purpose. In general, the microbiological analysis of harvested rainwater seemed in accordance with some existing guidelines for non-potable uses. Faecal indicators presence could indicate animal dropping contamination; however these indicators could not indicate the presence of human pathogens and especially environmental waterborne pathogens such as legionella or non-tuberculous mycobacteria and parasitic protozoa. So, it could be inadequate to use the indicators of faecal contamination for roof-harvested rainwater quality which is not probably polluted by human waste contamination. Moreover, it is very difficult to confirm whether such roof-harvested rainwater has a good quality or not if we could simply use some existed standards for other types of water such as bathing or reused waters. This showed that there is a lack of a suitable standard for roof-harvested rainwater quality corresponding to different uses. We also need a harmonized standard for European community for the roof-harvested rainwater quality in function of its uses. The chemical analysis and direct identification of pathogens may be warranted to establish whether or not such harvested rainwater is safe for different uses.

Table 1 :

 1 Average levels of physical-chemical parameters of rainwater measured from outside and underground tanks (n corresponds to the number of samples; numbers in parenthesis correspond to minimum and maximum values)

		Outside tank	Underground tank
	Physical-chemical parameters	n = 6 -9	n = 5 -6
	pH	8.67 (7.64-9.38)	6.21 (5.49-6.8)
	Conductivity (µS/cm)	34.29 (10-80)	50.2 (22-88)
	Turbidity (NTU)	2.96 (0.95-6.20)	1.31 (1.06-1.69)
	DOC (mg/L)	1.93 (0.5-4.55)	1.09 (0.73-1.61)
	Nitrate (mg/L)	2.29 (1.29-3.90)	2.67 (1.26-4)
	Phosphate (mg/L)	0.23 (0.12-0.34)	0.068 (0.03-0.12)
	4.2. Microbial analysis

[START_REF] Nguyen-Deroche | Quality of roof harvested rainwater from houses in Île-de-France area[END_REF]

. Quality of roof harvested rainwater from houses in Île-de-France area, France.

Table 2 :

 2 Average levels of faecal indicators and total DAPI counts of rainwater and sediment measured from outside and underground tanks (n corresponds to the number of samples; numbers in parenthesis correspond to minimum and maximum values).

	Outside tank (n = 5)	Water	Sediment
	Coliforms (cfu/100mL)	303 (0-1700)	24004 (0-144000)
	Fecal coliforms (cfu/100mL)	2 (0-7)	67 (0-200)
	Enterococci (cfu/100mL)	2 (0-10)	0
	Total flora at 22 °C (cfu/1mL) 1280 (420-2330) 327500 (23500-888000)
	Total flora at 36 °C (cfu/1mL) 1528 (170-2880) 32167 (29000-36500)
	Pseudomonas spp. (cfu/100mL) 87 (3-240)	3233 (0-10000)
	Total DAPI count (x10	6 cells/mL) 1.4 (0.6-2.3)	104 (36.5-234)
	Underground tank (n = 5)	Water	Sediment
	Coliforms (cfu/100mL)	373 (75-875)	19041 (3000-54833)
	Fecal coliforms (cfu/100mL)	31 (3-127)	667 (0-1217)
	Enterococci (cfu/100mL)	109 (0-282)	61 (0-167)
	Total flora at 22 °C (cfu/1mL)	374 (21-1291) 102693 ( 13135-436364)
	Total flora at 36 °C (cfu/1mL)	201 (41-467)	187025 (1 2727-860000)
	Pseudomonas spp.(cfu/100mL) 1618 (11-7567)	81210 (4636-324324)
	Total DAPI count (x10	6 cells/mL) 1.6 (1.2-2.1)	53.8 (6.8-103.0)

Table 3 :

 3 Summary of microbiological water quality requires for potable and non-potable use

		Drinking water	Bathing water	Reuse water	Examples of international
	Indicators	French minister's	European directive	French minister's	microbiological water quality
		order (Jan/11/2007)	(CE/Jul/2006)	order (Aug/02/2010)	criteria for toilet flushing
							O a* (US)
							O b* (UK)
	Escherichia coli			0	900*	<250	d	10 b (Japan)
							100	b (Germany)
							200	c (Canada)
	Intestinal enterococci			0	330*
							240	a* (US)
	Total coliforms			0			500	b (Germany)
							10 b (Japan)
	* 90th percentile evaluation;	a U-S Environmental Protection Agency, 2004;	b Birks et al., 2004;
	c Canadian guidelines, 2007;	d good quality level of reuse water for irrigation

th International Rainwater Catchment Systems Conference, March 28-April 4, 2011, Taiwan, R.O.C. NGUYEN-DEROCHE et al., 2011. Quality of roof harvested rainwater from houses in Île-de-France area, France.

Acknowledgement

We would like to thank the private partner (Aqualive society) and French industrial association of rainwater (IFEP). In particular, we also would like to thank the particulars who gently accepted to let us perform all samplings. The research project QUALICO was supported by Administration Council of Val-de-Marne department, Research Network on Sustainable Development (R2DS Île-de-France). This project was also an axis of OPUR (Observatoire des Polluants URbains en Île-de-France).


Gaurav Sharma
email: gaurav.sharma@unicaen.fr

Frederic Jurie
email: frederic.jurie@unicaen.fr

A Novel Approach for Efficient SVM Classification with Histogram Intersection Kernel

The kernel trick -commonly used in machine learning and computer vision -enables learning of non-linear decision functions without having to explicitly map the original data to a high dimensional space. However, at test time, it requires evaluating the kernel with each one of the support vectors, which is time consuming. In this paper, we propose a novel approach for learning non-linear SVM corresponding to the histogram intersection kernel without using the kernel trick. We formulate the exact non-linear problem in the original space and show how to perform classification directly in this space. The learnt classifier incorporates non-linearity while maintaining O(d) testing complexity (for d-dimensional input space), compared to O(d × N sv ) when using the kernel trick. We show that the SVM problem with histogram intersection kernel is quasi-convex in input space and outline an iterative algorithm to solve it. The proposed approach has been validated in experiments where it is compared with other linear SVM-based methods, showing that the proposed method achieves similar or better performance at lower computational and memory costs.

Introduction and related work

The two main ingredients of most of the successful approaches for visual recognition are (i) the representation of images by distributions (i.e. histograms) of visual features e.g. bag-offeatures [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF] and HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and (ii) the use of margin maximizing classifiers such as support vector machines (SVM) [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF]. Systems built on them have led to state-of-the-art performance on image classification [START_REF] Krapac | Modeling spatial layout with Fisher vectors for image categorization[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Sharma | Discriminative spatial saliency for image classification[END_REF] and object detection [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF].

The standard formulation for learning classifiers is the SVM primal formulation (Eq. 1, see [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF] for more details) which allows the learning of a linear classification boundary in the space of (images represented as) distributions. However, general visual tasks e.g. scene or object based classification of unconstrained images, are very challenging due to the presence of high variability due to viewpoint, lighting, pose etc. and linear decision boundaries are not sufficient. Many competitive methods in image classification [START_REF] Everingham | The PAS-CAL Visual Object Classes Challenge[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] and object detection [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF], thus, use non linear classifiers. Such non linear classifier are obtained by using the kernel trick with the dual formulation (Eq. 2) of the SVM. The SVM dual formulation only requires the dot products between the vectors and so a nonlinear kernel function K(x 1 , x 2 ) is used which implicitly defines a (non linear) mapping φ : R d → F of input vectors to a high (potentially infinite) dimensional feature space with K(x 1 , x 2 ) = φ (x 1 ), φ (x 2 ) . With the kernel trick a linear decision boundary in the feature space is learned which corresponds to a non linear decision boundary in the input space. Such kernel based SVMs have been shown to improve the performance of linear SVMs in many visual tasks (e.g. classification and detection) by a significant margin e.g. [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF].

While the dual formulation allows the learning of non linear decision boundaries, the computation of classifier decision for a test vector x, f (x) ∝ ∑ i c i K(x, x i ) (c i being the model parameters), depends on kernel computation with all support vectors {x i ∈ R d |i = 1 . . . N sv }. Hence, the test time and space complexities becomes O(d × N sv ) vs. O(d) for the linear case i.e. f (x) = w T x. In practice, N sv is of the order of number of training examples, and this leads to significant cost in terms of time and space. Such high cost makes it impractical for kernel based classifiers to be used for large scale tasks e.g. object detection, in which the classifier has to be applied to more than 100,000 windows per image [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF] or large scale image classification [START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF] with thousands of classes. Similarly, it makes them impractical to use with limited capability mobile devices in consumer applications e.g. smart-phone/tablet applications for object or landmark recognition or for real time object based video editing.

The second component of successful approaches for visual recognition, relies on the use of distributions of features for representing the images. The two of the most popular/successful of such features being the Histogram of Oriented Gradients (HOG) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] capturing shape information and bag-of-features [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] capturing the appearance. The related histogram intersection kernel [START_REF] Michael | Color indexing[END_REF] x and y (e.g. [START_REF] Grauman | The pyramid match kernel: Efficient learning with sets of features[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]). Being positive definite, it can be used directly as a kernel with SVM. However, recall that using kernel SVM leads to high i.e. O(d × N sv ), time and memory requirement as a result of using the kernel trick. This has led to many recent works proposing faster ways to compute the classifier and/or the decision function corresponding to the histogram intersection kernel e.g. [START_REF] Maji | Max-margin additive classifiers for detection[END_REF][START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF][START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF].

Traditionally, the kernel based classifiers having led to the best results on image classification problems with the standard bag-of-features [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] image representation (e.g. the high ranking entries of the PASCAL VOC 2007 competition [START_REF] Everingham | The PAS-CAL Visual Object Classes Challenge[END_REF]) used classifiers based on nonlinear kernels with support vector machine (SVM) classifiers [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF]. While the kernel-SVMs perform well they incur a very high testing cost, as explained above. To overcome this limitation, Maji et al. [START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF] showed that SVM classifier decision corresponding to the histogram intersection kernel can be computed in logarithmic (wrt N sv ) time and also proposed a constant (wrt N sv ) time and space approximation for the same. More recently progress has been made in approximating the mapping to high dimensional feature spaces corresponding to commonly used kernels e.g. Maji and Berg [START_REF] Maji | Max-margin additive classifiers for detection[END_REF] approximate the feature map corresponding to the intersection kernel and Vedaldi and Zisserman [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] approximate general additive kernels. The advantage of doing such mappings is that they allow the use of linear classification methods with the feature mapped vectors, but the drawback is that each data point has to be explicitly mapped, which has a cost.

In this paper, we take an (as far we know) unexplored route and show that it is possible to learn a nonlinear classifier implementing the histogram intersection kernel directly in the input space without using the dual formulation and the kernel trick, while achieving similar classification performance. We work with the primal optimization problem (Eq. 1) and view the kernel as a parametrized scoring function inducing a nonlinear boundary in the input space. As a result, the problem we solve becomes non convex, but remains quasi convex. To solve the problem, we outline an approximate optimization algorithm which starts by solving a, highly smoothed, convex approximation of the objective and then successively solves less smoothed objectives, initialized with the solution of the previous one, converging to the current objective. In practice, however, we find that a simple stochastic sub-gradient descent solver, working with the sub-gradient of the non convex objective, with very small steps and multiple passes over the data achieves competitive performance. While with the current approaches [START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF][START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] two costs are incurred at test time, (i) mapping the test vector and (ii) computing O(d ′ ) dot product, in higher d ′ -dimensional feature space, with the proposed method we only need to perform O(d), with d < d ′ , operations in original space. Along with being conceptually interesting, our method thus leads to reduced space and time complexities.

Approach

A standard formulation for learning linear classifier is the SVM primal optimization, min

w λ 2 ||w|| 2 2 + 1 |I t | ∑ i ξ i , s.t. y i w T x i ≥ 1 -ξ i and ξ i ≥ 0, (1)
where w is the normal to the linear decision hyperplane and {(x i , y i )|x i ∈ I t , y i ∈ {-1, +1}} are the training vector and label pairs. The optimization problem is convex and well studied, and many standard libraries (e.g. liblinear [START_REF] Fan | LIBLINEAR: A library for large linear classification[END_REF]) exist for solving it. However, only a linear decision boundary (i.e. a hyperplane parametrized by w) can be learnt with this formulation.

In general the classes may not be separable by linear boundaries and to allow learning more complex nonlinear decision boundaries, the dual formulation of the problem, given by max

α ∑ i α i + 1 2 - 1 λ ∑ i, j α i α j y i y j x T i x j , s.t. 0 ≤ α i ≤ 1 |I t | . (2)
is used. The dual formulation allows the use of the kernel trick, where a kernel function is defined as K(x i , x j ) = φ (x i ), φ (x j ) with φ : R d → F being a feature map, mapping the vector x ∈ R d in the input space to a high (potentially infinite) dimensional feature space F, where the classes are hoped to be linearly separable. Since in the dual formulation (Eq. 2) only the dot products (i.e. the kernel functions) are required, φ is only implicitly defined via the kernel function (see [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF] for detailed discussion). Towards the goal of learning a nonlinear classifier in input space, we start with the SVM problem (unconstrained formulation equivalent to Eq. 1) in feature space, obtained by mapping the input space vectors using the feature map φ : R d → F,

L φ (w φ ) = λ 2 ||w φ || 2 2 + 1 |I t | ∑ i max(0, 1 -y i w φ , φ (x) ) (3)
where w φ ∈ F denotes the (parameters of the) linear decision boundary in the feature space.

While noting that exact pre-images of vectors in feature space might not exist in general [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF], we assume that the pre-image of the vector w φ exists i.e. ∃w ∈ R d such that w φ = φ (w) (in case an exact pre-image does not exist, consider w to be the best approximation of the preimage of w φ ). We can now write the objective function as,

L(w) = L φ (w φ ) = λ 2 ||φ (w)|| 2 2 + 1 |I t | ∑ i max(0, 1 -y i φ (w)φ (x) ). (4)
Although we are working with non-negative bag-of-features histograms {x ∈ R d + } in input space, we expect the vector w to be negative as well in general. We could see the w vector as a combination of two non-negative vectors w = w +w -∀w + , w -∈ R d + where the w + (w -) capture the discriminative information supporting the positive (negative) class.

We now focus our interest on the feature map corresponding to the generalized intersection kernel i.e.

φ (x), φ (y) = K(x, y) = ∑ d x d y d |x d ||y d | min(|x d |, |y d |) ∀ x, y ∈ R d . (5)
With this map, the regularization term in Eq. 4 becomes

||φ (w)|| 2 2 = φ (w), φ (w) = K(w, w) = ∑ d w 2 d |w d | 2 min(|w d |, |w d |) = ∑ d |w d | = ||w|| 1 , (6)
and part of the second term can be written as

y i φ (w), φ (x) = y i f (w, x i ) with f (w, x) = K(w, x)
acting like a scoring function inducing a non-linear decision boundary in the input space.

Hence, the complete feature space optimization can be written in input space as

L(w) = λ 2 ||w|| 1 + 1 |I t | ∑ i max(0, m -y i f (w, x)) (7a) f (w, x) = ∑ d w d |w d | min(x d , |w d |) (as x ∈ R d + ) (7b)
where we have replaced the constant 1 (in the hinge loss term) with a free variable m as a unit distance in feature space will, in general, does not correspond to a unit distance in the input space.

Minimizing L φ w.r.t. w φ in the feature space is a convex problem. It is solved using the kernel trick which evades the need of explicitly specifying φ . However, at test time, to compute the prediction for a test image, computing kernels with all the support vectors (which are of the order of number of training images) is required.

In this paper, instead of minimizing the convex objective L φ (Eq. 4) in feature space, we propose to directly minimize the non linear and non-convex objective L (Eq. 7a). Towards this goal we now analyze the nature of the objective function L.

Quasi convexity of the objective function

The objective function we propose to solve i.e. L(w), ∀w ∈ R d (Eq. 7a) is quasi-convex. Quasi-convexity requires that the function is only locally flat, more formally all the level sets of the function S α = {x| f (x) ≤ α}∀α ∈ R are convex sets. The ℓ 1 regularization term is convex and hence quasi convex (QC). To see the QC of the second term we note that it is a max over per example loss. mf (w, x) is QC (as a function of w with fixed x) as it is piecewise affine and monotonic (albeit not strictly). Fig. 1 shows the decision function f (w, x) for one and two dimensional spaces as a function of w. Constant function is also QC and hence the per example loss, being a max over QC functions is also QC. As weighted sum of QC functions with positive weights is also QC, the loss over all examples is thus QC. Hence, we have to minimize a QC objective L (Eq. 7a) in input space.

Linear decision function as a convex relaxation

A standard approach to deal with non-convex optimization is to resort to approximation and solve a convex relaxation of the objective instead. Fig. 2 shows how a series of relaxations of the intersection based decision function (Eq. 7b) can be constructed, with final convergence to linear, and hence, convex decision function (convex optimization problem). An algorithm could, thus, be designed to solve the nonlinear optimization by successive smoothing. The algorithm would proceed by first solving a highly smoothed convex problem (corresponding to linear decision function) and then iteratively solving less smoothed versions, of the objective, initialized with the solution of previous ones. The intersection decision function (for single dimensional feature x ∈ R) could be relaxed with the following function, parametrized by t,

f t (w, x) = wx/t if w ≤ t, w tan tan -1 (x).(t -x)/(1 -x) otherwise, (8)
for x ∈ R + (the function is odd i.e. f (w) = -f (-w) ∀w ∈ R -). The parameter t ∈ [x, 1] (x ≤ 1
as it is a component of ℓ 1 normalized BoF histogram) controls the amount of smoothness on the objective function, Fig. 2 illustrates the smoothed versions of the function for one dimensional w. We have no smoothing when t = x, while t = 1 leads to heavily smoothed linear decision function. When the decision function is linear i.e. t = 1, the optimization problem becomes convex. When using this function for the sum of hinge losses for all d dimensional examples (i.e. many different x ∈ R d ) t is replaced with max(t, x d ) for each dimension of each example. The discussion above, pertaining to the convex relaxation of the objective, changes accordingly. if iter = 50 do r ← r/10 end if 9: end for

Stochastic subgradient based solver

In practice, we find that a simple stochastic solver using the subgradient of the objective function, Eq. 7a, performs well in practice. Eq. 7a can be seen as a ℓ 1 regularized hinge loss minimization, albeit with non-convex scoring function. ℓ 1 regularization with convex losses is a well studied topic (e.g. [START_REF] Schmidt | Fast optimization methods for L1 regularization: A comparative study and two new approaches[END_REF]). While the problem is non-convex, systems learned with ℓ 1 regularization perform well in practice (and are specially interesting for their sparsity inducing effects). We tried a stochastic (sub) gradient based algorithm, outlined in Alg. 1 (✶(c) = 1 if condition c is true, 0 otherwise), to solve Eq. 7a. We formulated the update steps analogous to other recent work in computer vision using stochastic gradients [START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF][START_REF] Sharma | Discriminative spatial saliency for image classification[END_REF]. There are two update steps, first (line 5, Alg. 1) updates w based on subgradient of the loss (denoted L s ) of the current example x, given by (for each coordinate)

∇ L s (x d ) = -y i if y i f (w, x i ) < m and abs(w d ) < x d 0 otherwise (9)
and the second update (line 6, Alg. 1) is based on the sub gradient of the regularization term, simply the sign of w for each dimension. We clip the update step due to the second term to avoid zero crossing. The two step update in Alg. 1 does not correspond to the accurate sub gradient of the objective in Eq. 7a (see §2.1 in [START_REF] Schmidt | Fast optimization methods for L1 regularization: A comparative study and two new approaches[END_REF] for full subgradient). We assume λ ≪ 1, which is true in practice, and thus ignore some effects of λ in the subgradient based updates. We find that the proposed algorithm performs well in practice. We choose to use this algorithm for its simple implementation and report results using it in the experimental section.

Experiments

We now report results for the nonlinear SVM learned in the original space directly using the Alg. 1. In the following we call the proposed method non-linear SVM as nSVM. We report results on experiments designed to study the parameter sensitivity, speed and memory gains and the ability to achieve competitive performance.

Experimental setup

We report results on two standard computer vision benchmark datasets, (i) PASCAL VOC 20071 object image classification dataset [START_REF] Everingham | The PAS-CAL Visual Object Classes Challenge[END_REF] with 20 classes and 9963 images and (ii) Scene-15 database2 [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] with 15 scene classes with 4492 images. We report results with standard protocol i.e. train+validation sets for training and test set for reporting performance for PASCAL VOC 2007 dataset and 100 random images per class for training and rest for reporting performance for Scene-15 dataset, and evaluation metrics for the datasets i.e. per-class and mean average precision (AP) for PASCAL VOC 2007 dataset and per-class and mean (over classes) accuracy for Scene-15 dataset. We fix the image representation and compare classifiers (after feature mapping) on top of the representation. The image representation used (for both the proposed and compared methods) is the bag-of-features representation. We extract dense SIFT [START_REF] Lowe | Distinctive image features form scale-invariant keypoints[END_REF] features at 4 scales with a step size of 3 pixels with grayscale images. We learn a visual word vocabulary of size 1024 using k-means algorithm with 500,000 randomly sampled SIFT features from the training images. We use standard spatial pyramid representation [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] with the vector quantized features. We use 1 × 1, 2 × 2 and 3 × 1 (4 × 4) spatial cells for PASCAL VOC 2007 (Scene-15) dataset.

We compare with a closely related, recently proposed method of explicit feature maps by Vedaldi and Zisserman [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] which computes finite dimensional mappings corresponding to the histogram intersection kernel. Such mappings thus enable us to compute linear classifiers in the mapped space. It was shown by Vedaldi and Zisserman [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] that this feature mapping obtains better results that the one by Maji and Berg [START_REF] Maji | Max-margin additive classifiers for detection[END_REF]. We use 3D features for the explicit feature map as this gave the best result in [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF].

We use VLFeat library [START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF] to (i) compute SIFT descriptors, (ii) do k-means and (iii) compute the feature map corresponding to Vedaldi and Zisserman's method [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF]. We use liblinear [START_REF] Fan | LIBLINEAR: A library for large linear classification[END_REF] (with ℓ 2 regularized ℓ 1 loss option) to learn SVM with the feature mapped vectors. (image classification task) for the proposed method (nSVM) and the explicit feature mapping of Vedaldi and Zisserman [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] (for histogram intersection kernel with linear SVM).

Performance comparison

Fig. 4 and3 show the per class performances of our method vs. explicit feature map [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] with linear SVM, on the two datasets. We get similar performance, on an average, compared to feature maps with mean average precision of 50.5 (present) vs. 49.7 (feature map) on PASCAL VOC 2007 dataset and mean class accuracy (over 10 random runs) of 84.0 ± 0.5 (present) vs. 84.7 ± 0.4 (feature map). We conclude that our method for learning a classifier directly in original space achieves competitive performance.

Test time and space complexities

We compare the test time speedup and the memory usage reduction (Tab. 1) compared to the explicit feature map [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] which is already more than three orders faster than the kernel SVM (there are O(10 3 ) support vectors and the scoring a new image/vector requires computing the histogram intersection kernel with each of them). We used the 3D features for explicit feature maps, as they were reported to give best results, which results in features of 7d dimensions for d-dimensional bag-of-features with spatial pyramid. While our method performs a linear scan on the d-dimensional features to calculate the test score (Eq. 7b), for explicit feature maps we have to, first, compute the mapping to 7d space and then compute a dot product in that space. Hence the model is 7× bigger for explicit feature map compared to our method and (empirically) our method is about 19× faster than explicit feature maps with linear SVM (the time is only due to classifier score computations and excludes the bag-of-features construction time for both methods). The training is also fast e.g. it takes about 45 secs to train a model for one class of PASCAL VOC 2007 dataset. We resorted to a conservative training strategy with multiple passes over the data and our training time can be arguably improved quite a bit.

Sensitivity to parameters

Fig. 5 shows the test average precision (AP) for the aeroplane class of the PASCAL VOC 2007 dataset with the iterations for the learning algorithm. We found that having a higher rate initially and then annealing by decreasing the learning rate midway was helpful for convergence, notice the convergence before and after iteration 50. The method converges for a range of λ and m parameters. While, the convergence happens for a range of values, cross validation is suggested for competitive performance.

Conclusion

Making non-linear classification efficient is advantageous for many applications specially with large number of images and categories e.g. large scale classification, and with limited computing resources e.g. in consumer devices like cameras or smart phones.

  ∑ d x d y d |x d ||y d | min(|x d |, |y d |) ∀ x, y ∈ R d has thus been a natural choice, in visual tasks, for measuring the similarity between image representations

Figure 1 :

 1 Figure 1: The scoring function for one dimension (left) and in the positive quadrant in two dimensions (right).

Figure 2 :Algorithm 1 4 :

 214 Figure 2: The linear decision function (green) can be seen as a convex relaxation of the histogram intersection like decision function (blue). If we introduce a parameter t ∈ [x, 1],we can construct series of relaxations of the intersection like decision function converging to the convex linear decision function as t varies from x to 1, shown in red in here. Only the first quadrant is shown, the graphs in the third quadrant are obtained by mirroring about the two axes i.e. all functions are odd functions with f (-x) =f (x).

Figure 3 :

 3 Figure3: The accuracies for different classes (mean and std over 10 splits) of the Scene 15 dataset[START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] for the proposed method (nSVM) and the explicit feature mapping of Vedaldi and Zisserman[START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] (for histogram intersection kernel with linear SVM).

Figure 4 :

 4 Figure 4: The average precisions for different classes of the Pascal VOC 2007 dataset[START_REF] Everingham | The PAS-CAL Visual Object Classes Challenge[END_REF] (image classification task) for the proposed method (nSVM) and the explicit feature mapping of Vedaldi and Zisserman[START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] (for histogram intersection kernel with linear SVM).

Figure 5 :

 5 Figure 5: The average precisions for different values of (left) regularization parameter λ and (right) hinge loss parameter m, for a typical convergence of the proposed method.

Table 1 :

 1

			Time		Memory
		Secs Speedup Kbytes Reduction
	Vedaldi and Zisserman [20] 3.8	1 (ref)	448	1 (ref)
	Nonlinear SVM (present)	0.2	19×	64	7×

Testing time, for aeroplane class of Pascal VOC 2007 dataset

[START_REF] Everingham | The PAS-CAL Visual Object Classes Challenge[END_REF]

(on the full test set), averaged over 10 runs and memory usage (for keeping model in memory) comparison for the proposed model and the feature mapping method of Vedaldi and Zisserman

[START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF]

.

http://pascallin.ecs.soton.ac.uk/challenges/VOC/voc2007/

http://www.featurespace.org/data.htm

In the present paper we proposed a method for learning non-linear classifier corresponding to the histogram intersection kernel directly in the original space i.e. without using the kernel trick nor mapping the features explicitly to high dimensional space corresponding to the kernel. We formulated the non-linear optimization in the original space which corresponds to the linear optimization problem in the high dimensional feature space. We analyzed the objective function and proved that it is quasi-convex. We outlined an algorithm to optimize the quasi convex objective using successive relaxations, starting from a highly smoothed convex objective and iteratively solving less smoothed versions of the objective. We showed experimentally that a stochastic algorithm with subgradients works well in practice. Compared to a recent method for making non linear classification efficient, the proposed method is 19× faster and requires 7× less memory.

As future work, we plan to improve the training and use the system for applications mentioned above. Exploring similar learning strategies for kernels other than that based on the histogram intersection distance is also an interesting direction.

Aknowledgements

This research was supported by a grant from the Conseil Régional de Basse-Normandie (CRBN/11P01269/REPERE).


Alexis Mignon
email: alexis.mignon@unicaen.fr

Frédéric Jurie
email: frederic.jurie@unicaen.fr

RECONSTRUCTING FACES USING RBF REGRESSION

The increasing popularity of social networks raises critical issues regarding privacy and protection of personal information. One typical example -which is the motivation of the paper -is face images and face recognition, face recognition being ubiquitous on the web now. Assuming someone with bad intentions steals a database containing face signatures, would it be possible to reconstruct the corresponding face images, revealing who was in the database? Would these reconstructed images be good enough to allow them to gain access via a face recognition system? This paper brings a contribution to this topic by proposing a face reconstruction algorithm, based on RBF-regression in eigenspace, which is able to reconstruct face images from their signatures (i.e. neither knowing the identity of the persons nor their true facial appearance). We show that in addition to being visually realistic, the images generated by the proposed method can fool a state-of-the-art face recognition algorithm.

Introduction

Faces are now omnipresent on the Internet (Facebook profiles, photo sharing sites, etc.), and so are face recognition technologies (Google, Facebook, etc. now use face recognition to automatically tag people). Even if the identity/name of the persons appearing in most of the photographs are not explicitly given, face matching technologies have become powerful enough to discover the links between people through faces and, thus, are able to aggregate the information scattered at different places. Such databases use and store face signatures (or face templates as they are called in the biometrics literature) as keys for organizing the data.

One important question related to privacy is to know if the information encoded by such templates might be reverse engineered, revealing the identities of the persons in case the database is stolen or made publicly available by mistake. In other words, do face signatures (or face templates, we interchangeably use the two expressions) contain personal information?

This is also a topic of interest for biometric applications where the way templates are encoded is critical [START_REF] Rathgeb | Multi-Biometric Template Protection: Issues and Challenges, New Trends and Developments in Biometrics[END_REF]. Indeed, stolen templates should not allow reconstruction of images that can be used to break in a system. People have believed for a while that reconstructing images from their signatures was impossible, but several researchers have shown recently it is actually feasible (e.g. [START_REF] Adler | Images can be regenerated from quantized biometric match score data[END_REF]). As face representation and face verification technologies have progressed a lot during the last five years, we believe it is important to know, if and to what extent, people can be recognized from their face templates once their face has been reconstructed.

In this context, the objective of this paper is twofold: (i) to propose a simple but efficient method for reconstructing face images from face templates with unknown identities and (ii) to show that these reconstructed images allow the recognition of people and can fool modern face recognition algorithms. We believe that the proposed approach could be used, each time a new method for representing faces is proposed, to evaluate how anonymity is preserved by the encoding.

In practice, we chose to use the I-LPQ approach of [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF] -which was, at the moment we wrote the paper, the state-of-the-art unsupervised approach on the LFW [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF] and FERET [START_REF] Phillips | The FERET Evaluation Methodology for Face-Recognition Algorithms[END_REF] datasets -as a baseline approach for computing face templates. Another reason for using this approach is that it is a good representative of modern approaches for face recognition, most of them being based on histograms of LBP/SIFT/Gabor-like features computed on a regular grid [START_REF] Cao | Face recognition with learning-based descriptor[END_REF][START_REF] Nguyen | Cosine Similarity Metric Learning for Face Verification[END_REF][START_REF] Yin | An associate-predict model for face recognition[END_REF].

The proposed reconstruction method is based on radial basis function regression in the face eigenspace. During a training phase, face/signature pairs are used to learn a non linear mapping between images and their signatures. This mapping minimizes the reconstruction error of the eigenface representations of the training images. The mapping can then be used directly to reconstruct faces from their signatures.

In addition of showing reconstructed images and comparing them with the original ones, the proposed approach is experimentally validated on the two aforementioned datasets, i.e. LFW and FERET. For these two datasets, we have reproduced the standards protocols of evaluation defined by the datasets, with the difference that instead of using original images we used reconstructed images. We show that the drop in performance is rather low, allowing us to conclude that the signatures do contain enough information to reconstruct face images that can fool -with a good chance -an automatic face recognition system.

Related Work

Face templates are compact digital representations of the essential features of facial images. Early works in face representations were mainly relying on global image transformations, projecting faces into meaningful subspaces by the means of PCA or LDA [START_REF] Belhumeur | Eigenfaces vs. fisherfaces: Recognition using class specific linear projection[END_REF][START_REF] Turk | Face recognition using eigenfaces[END_REF]. These representations, so-called e.g. Eigen and Fisher faces, were encoding the coordinates of faces with respect to these subspaces. Most of the face reconstruction methods have been experimented in this context (e.g. [START_REF] Adler | Sample images can be independently restored from face recognition templates[END_REF][START_REF] Adler | Images can be regenerated from quantized biometric match score data[END_REF][START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF]), explaining why they observed that simple gradient based optimization allows to reconstruct faces easily in their cases.

However, the majority of best performing modern methods use distributions of local features for characterizing the facial traits, such as [START_REF] Cao | Face recognition with learning-based descriptor[END_REF], which vector quantizes local pixels and aggregates local histograms, or [START_REF] Pinto | Beyond simple features: A large-scale feature search approach to unconstrained face recognition[END_REF][START_REF] Pinto | How far can you get with a modern face recognition test set using only simple features[END_REF] which use spatially localized Gabor filters in multilayer frameworks. Histograms of LBPs, LTPs or LQPs are also commonly used in recent approaches, either extracting them from raw pixel intensities [START_REF] Ahonen | Face description with local binary patterns: Application to face recognition[END_REF][START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF][START_REF] Wolf | Similarity scores based on background samples[END_REF] or from images of gradient orientations [START_REF] Nguyen | Local gabor binary pattern whitened PCA: A novel approach for face recognition from single image per person[END_REF][START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF][START_REF] Vu | Enhanced patterns of oriented edge magnitudes for efficient face recognition[END_REF][START_REF] Zhang | Local Gabor Binary Pattern Histogram Sequence (LGBPHS): A Novel Non-Statistical Model for Face Representation and Recognition[END_REF]. These features (LBP, SIFT, etc.) can be also combined, at the decision level (e.g. using Multiple Kernel Learning) to improve the performance of the final classifier [START_REF] Cao | Face recognition with learning-based descriptor[END_REF][START_REF] Kumar | Attribute and simile classifiers for face verification[END_REF][START_REF] Pinto | Beyond simple features: A large-scale feature search approach to unconstrained face recognition[END_REF][START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF][START_REF] Wolf | Similarity scores based on background samples[END_REF][START_REF] Ying | Distance metric learning with eigenvalue optimization[END_REF]. To our knowledge, no face reconstruction approaches have considered such modern representations using histograms of local features.

Regarding the question of reconstructing face images from face templates, it has been claimed in the past that biometrics data such as fingerprints or face templates can be consid-ered as non-identifiable data, allowing to allay concerns about privacy. However, since the beginning of the 2000's, several authors have proposed reconstruction approaches, following the hill-climbing approach of [START_REF] Adler | Sample images can be independently restored from face recognition templates[END_REF][START_REF] Adler | Images can be regenerated from quantized biometric match score data[END_REF]. Starting from a generic initial image, these approaches update iteratively the initial image in such a way that the match score is increasingly better (i.e. in such a way that the similarity between the target template and the template of the reconstructed image is higher). Different variants of this approach have been applied to different biometric tasks [START_REF] Galbally | Hill-climbing attack to an eigenface-based face verification system[END_REF][START_REF] Galbally | Bayesian hill-climbing attack and its application to signature verification[END_REF][START_REF] Martinez-Diaz | Hill-climbing and brute force attacks on biometric systems: a case study in match-on-card fingerprint verification[END_REF][START_REF] Uludag | Attacks on biometric systems: a case study in fingerprints[END_REF].

However, as pointed out by [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF], this hill-climbing optimization is rather inefficient as it involves the optimization of a non-convex criterion and requires a large number of attempts before succeeding. Consequently, [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF] proposed to use a different paradigm. They first model the face recognition algorithm by an affine transformation approximating the distances between pairs of training faces by applying multi-dimensional scaling (MDS). The training templates embedded in this affine space are then linearly fitted to the face images represented in their eigenspace. The distance between the templates to be reconstructed and templates coming from the set of training faces are then computed, allowing to embed targeted templates in an affine space. The image of the targeted template is then reconstructed using a linear transformation, obtaining better results than hill-climbing, and at a lower cost.

Building on the pioneering work of [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF], our reconstruction method gets inspiration from the literature on radial basis function (RBF) least squares. The different RBF methods differ from each other mainly by (i) the presence or absence of regularization or bias terms, (ii) the nature of the basis functions and (iii) how the centroids are chosen.

One of the first RBF least squares method [START_REF] Hardy | Multiquadric Equations of Topography and Other Irregular Surfaces[END_REF], known as the multiquadric interpolation, has been inroduced to model the topography of fields. Its name comes from the use of the so-called multiquadric function. It has been used in various applications [START_REF] Hardy | Theory and applications of the multiquadric-biharmonic method. 20 years of discovery 1968-1988[END_REF], from surface interpolation [START_REF] Franke | A Critical Comparison of Some Methods for Interpolation of Scattered Data[END_REF] to numerical solutions of differential equations [START_REF] Kansa | Multiquadrics-A scattered data approximation scheme with applications to computational fluid-dynamics-II solutions to parabolic, hyperbolic and elliptic partial differential equations[END_REF][START_REF] Kansa | Numerical simulation of two-dimensional combustion using mesh-free methods[END_REF]. In addition, Micchelli showed that the problem was solvable for any conditionally positive (or negative) definite kernels among which is the mutiquadric function [START_REF] Micchelli | Interpolation of scattered data: Distance matrices and conditionally positive definite functions[END_REF]. Some studies have shown that multiquadric interpolations tend to be more robust than interpolations based on others RBF kernels, especially than the widely used Gaussian kernel [START_REF] Franke | Scattered Data Interpolation: Tests of Some Method[END_REF]. More generally the advantage of using RBF kernels is that they allow to approximate any functions or boundaries [START_REF] Park | Universal approximation using radial-basis-function networks[END_REF].

When applied to noisy data, RBF interpolation might suffer from over-fitting. Broomhead et al. [START_REF] Broomhead | Multivariable Functional Interpolation and Adaptive Networks[END_REF] tried to overcome this issue by reducing the number of centroids with respect to the number of data points. They also give an interpretation of the approach as a neural network and called their model RBF networks.

Other methods use regularization to handle over-fitting. This is the case, for instance, of the least squares support vector regression (LS-SVR) method proposed by Suykens et al. [START_REF] Suykens | Least Squares Support Vector Machines[END_REF] and the kernel ridge regression (KRR) of Saunders et al. [START_REF] Saunders | Ridge Regression Learning Algorithm in Dual Variables[END_REF]. KRR differs from LS-SVR in the absence of the bias term.

Contrasting with the MDS-based method of [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF], our approach (i) allows to learn efficiently non-linear relationships between faces and templates and (ii) does not need to build an intermediate Euclidean space since it (iii) models directly the transformation from templates to images in the eigenspace, leading to a much more efficient reconstruction framework.

Reconstructing faces from templates

Formally, the problem we address can be stated as follows. We assume having a face encoder working as a black box (i.e. the way it encodes faces is not known). This encoder performs a mapping between the image and template space, denoted as the function f :

I w×h → R D .
This function takes an image y of size w × h and computes its corresponding D-dimensional template x = f (y). In the following (and to simplify the notations) images are considered as P-dimensional vectors of raw pixel intensities, with P = w × h, obtained by concatenating image rows. If images are in color, they are converted to grayscale

We also assume that the similarity between two faces is measured as the Euclidean distance between their templates, which is the case for recent face recognition approaches such as [START_REF] Cao | Face recognition with learning-based descriptor[END_REF] or [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF]. In addition and in any case, this is not an unrealistic assumption since for positive definite metrics face templates can always be embedded into an Euclidean space, e.g. by using kernel PCA. Furthermore, when the similarity measure does not correspond to a valid metric, approaches such as the ones proposed in [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF] can be used to enforce the desirable properties.

Our approach relies on the use of training faces, which can be any set of face images (obviously, it is even better if the training faces have same illumination, range of pose or scales as the images to be reconstructed). Since the encoder f is provided, pairs of image/templates denoted (y i , x i ) can be computed from the training images. These pairs will allow us to learn the decoding map ϕ(x) ≃ f -1 (x), which will approximate the inverse of the mapping f . RBF least squares reconstruction. Given a set of N samples x i ∈ X = R D with associated target values y i ∈ Y = R P , RBF least squares models the mapping ϕ : X → Y as a set of P independent functions ϕ k (one different function per pixel):

ϕ k (x) = w 0k + M ∑ j=1 φ j ( x -c j )w jk ( 1
)
where the scalars w jk (k ∈ [0 . . . N]) are the parameters of the model, the vectors c j are a set of centroids and φ j are functions associated to each centroid. By using the following notations,

Y = [y 1 . . . y N ] T Φ =    φ 1 ( x 1 -c 1 ) . . . φ M ( x 1 -c M ) . . . . . . . . . φ 1 ( x N -c 1 ) . . . φ M ( x N -c M )    W =    w 11 . . . w 1P . . . . . . . . . w M1 . . . w MP    w 0 = [w 01 . . . w 0P ] T
W and w 0 can be estimated by solving the following optimization problem: min

W,w 0 ΦW + 1 M w T 0 -Y 2 F + R(W ) (2)
where . F is the Frobenius norm, R(W ) is a regularization term and 1 M is the M-dimensional vector with all elements equal to 1.

As stated in the previous section, this model generalizes several least-square based methods. For instance, multiquadric interpolation [START_REF] Hardy | Multiquadric Equations of Topography and Other Irregular Surfaces[END_REF] is a special case of equation ( 2), with no regularization term and centroids c j chosen as the training samples x i . The functions φ j correspond in this case to the multiquadric function φ j (x) = s 2 j + x 2 where s j is a scale parameter chosen to reflect the distribution in the local neighborhood of each centroid.

On the other hand, generalizing LS-SVR to deal with vector valued targets would lead to the following optimization problem: min

W,w 0 ΦW + 1 N w T 0 -Y 2 F + λ Tr[W T ΦW ] (3)
where the scalar λ > 0 controls the amount of regularization. The centroids are chosen the same way as for multiquadric interpolation but, in this case, the functions φ j are all the same, a common choice being the gaussian kernel. However, in practice, the reconstructions obtained this way suffer from the fact that pixels are reconstructed independently from each other, which motivates what follows.

Face reconstruction in the eigenspace. As explained before, we believe that reconstructing pixels independently is not optimal, and suggest instead to reconstruct faces as linear combination of eigenfaces. The reconstruction is then the set eigenface weights. In the eigenspace, most of the energy lies in the first few eigenfaces, which roughly correspond to the macro details of the faces. However, recent face recognition algorithms are usually based on tiny local features (e.g. LBPs computed on 3 × 3 neighborhoods). Consequently, and to encode more accurately those local features, we instead work in the whitened eigenspace. We remind that the whitening transformation transforms random variables (of known covariance matrix) into random variables whose covariance is the identity matrix.

Let us start by centering Y and Φ, which can be done by computing Ȳ = J N Y and Φ = J N ΦJ N , with J N = I N -1 N 1 N 1 T N being a centering matrix with I N the identity matrix of size N × N.

If the singular value decomposition of Ȳ is denoted as Ȳ T = USv T , our reconstruction is done by solving the following problem:

min W ΦW -ȲUS -1 2 F = min W ΦW -v 2 F ( 4
)
If Φ i j = s 2 + x ix j 2 (multiquadric kernel), the literature on radial basis function (RBF) least squares has demonstrated that matrix Φ is invertible [START_REF] Micchelli | Interpolation of scattered data: Distance matrices and conditionally positive definite functions[END_REF]. Because of the centering, Φ is of rank N -1 and W is given by (in the least squares sense):

W = Φ+ v (5)
where Φ+ denotes the pseudo-inverse of Φ. Once W is computed, the reconstruction of new faces from their templates is done as follows. Let x ′ i be the set of M templates for which we want to synthesize images, Φ ′ is computed as

Φ ′ i j = s 2 + x ′ i -x j 2 . Centering Φ ′ with respect to Φ gives Φ′ = (Φ ′ -1 N 1 M 1 T N Φ)J N . The corresponding images Y ′ are then given by Y ′ = Φ′ W v T Y + 1 N 1 M 1 T N Y . Hence: Y ′ = Φ′ ( Φ+ vv T ) + 1 N 1 M 1 T N Y (6)
The choice of the multiquadric kernel was guided by Franke's observations [START_REF] Franke | A Critical Comparison of Some Methods for Interpolation of Scattered Data[END_REF], which led to the conclusions that the multiquadric kernel is more robust and less sensitive to the choice of the scale parameter than other kernels such as the Gaussian Kernels. In the following experiments, s has been fixed to 1.

Experiments

The first motivation of the paper is to investigate whether people can be recognized from their template, once an image of their face has been synthesized by the proposed approach. We therefore present some qualitative results comparing original images with their reconstructions.

In addition, and in order to have an objective measure of the quality of the reconstruction, we also performed face recognition experiments in which the reconstructed faces are used instead of the real images, and evaluated how this replacement affects the recognition rates. Good performances would mean that synthesized images are good enough to break in a system which uses this face recognition technology to control access.

As stated in the introduction, we have used the face encoder of [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF] for these experiments. The face template is thus a vector containing histograms of Local Quantized Patterns (LQP) computed over a grid centered on the face, resulting in vectors of 1100 and 1400 dimensions respectively for FERET and LFW. We have used our own implementation of the encoder based on the details given in [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF]. This particular encoder was chosen because it is unsupervised (i.e. the representation is independent of the task) and because it gives state-of-the-art results (unsupervised settings) on the LFW dataset.

Datasets and protocols

The experimental validation is done on two datasets: (i) FERET which is a good representative of biometrics data and (ii) LFW which contains the same type of real images that can be found on the Internet. We start by presenting these datasets and give some implementation details (settings, etc.) specific for each dataset.

FERET. The FERET database [START_REF] Phillips | The FERET Evaluation Methodology for Face-Recognition Algorithms[END_REF] was released as a benchmark for face recognition algorithms. FERET is made of different views of 1195 persons, split into different non overlapping subsets. One of these subsets is used as the gallery (i.e. the set representative of the enrolled faces in an actual biometric scenario) and the others are used as probes (i.e. the collection of images that need to be recognized or identified by matching). In practice, we used the fb set as the probe, reproducing exactly the experimental protocol of [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF]. The encoder [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF] is trained on the gallery set and then used to encode the whole set of faces. Matching probe faces with gallery faces, with our implementation, gives a recognition accuracy of 99.2%. This is consistent with the results of [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF] and thus validates our implementation.

To learn the face decoder, we have used images from an external database. This ensures that our face decoder is trained with completely different people from FERET (otherwise the reconstruction would be made artificially too easy). The external database is MultiPIE [START_REF] Gross | Multi-pie[END_REF] from which we have selected the image folds acquired under similar conditions as those from FERET (frontal poses with same lighting conditions). Face templates are extracted with the same encoder as the one used for the FERET images, giving the image/template pairs needed for learning our decoder. We have trained the face decoder with different amount of training data in order to evaluate the amount of training images required to obtain accurate reconstructions. In practice, we have used 300, 400, 600 and 921 (i.e. all MultiPIE images) images.

Labeled Faces in the Wild. Labeled Faces in the Wild [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF] is a widely used database to benchmark face recognition algorithms. While in FERET faces are acquired with normalized poses and lighting conditions, LFW faces are captured in the wild, exhibiting large variations in pose, expressions and lighting conditions. This makes LFW much more challenging than FERET.

The recognition task on LFW consists of predicting if pairs of face images represent the same person or not (so called face verification). The performance is reported as the average accuracy of pairs classification.

Here again, we follow the experimental protocol and settings given in [START_REF] Hussain | Face Recognition using Local Quantized Patterns[END_REF]. The view2 of LFW is divided in 10 folds. People present in one fold are never occurring in any of the other 9 folds. Each fold contains 300 positive pairs (same person) and 300 negative pairs (different persons). Performances are evaluated as a 10 fold cross validation process. For each round, a different fold is used for testing while the 9 remaining ones are used for training.

Our decoder is trained with images coming from the folds used for training, and is used to reconstruct images of the remaining fold, giving the guarantee that people whose faces are used to train the decoder are not in the set of images to be reconstructed. At test time, the first element of each pair of the test set is replaced by the image reconstructed from the corresponding descriptor.

As with FERET, we have reconstructed face images using different numbers of training images. We have used more images than with FERET, due to the greater variability in face appearances, i.e. 500, 1000, 2000 and 3000 images.

Visual comparison of original images and their reconstructions

Figure 1 presents pairs of original/reconstructed images. The reconstructions are computed from the 1100-dimensional templates using the proposed method.

One can notice strong artifacts, which make the reconstructed faces difficult to confuse with real images, at least for a human being. The most obvious artifact seems to be due to the presence of a lot of people wearing different kind of glasses in the MultiPIE database (we remind that MultiPIE is used to learn the face decoder). As a consequence, some shadowed glasses are visible on each synthesized image, even when no glasses are present on the original image. However, some specific traits of the face such as the shape of the nose or the line of the eyebrows are rather well reconstructed.

One would expect that using training images with a broader variability, more realistic results would be obtained.

While MultiPIE and FERET are rather homogeneous with respect to the acquisition conditions, LFW exhibits a large range of pose and lighting conditions. Figure 2, shows some sample images from the LFW database with their reconstructions. While, as for FERET, the reconstructions can not be confused with real photographs, the final result is much more realistic and, in most of the cases, the persons can be easily identified from the reconstructed images. As expected, the quality of the reconstruction mainly depends on the amount of training images available. This is illustrated by Figure 3 which shows some reconstructions given by a decoder trained with different number of images; reconstructed faces become visually very close to original images when a sufficiently large number of training images is used.

Face recognition using reconstructed images

One interesting question is to know whether a set of face templates can be used to break in a face recognition system, by using the images synthesized from the templates. For doing these experiments we substitute the original probe images (with FERET) or one of the two test images (with LFW) with images synthesized using their corresponding template, and see how the performance of the face recognition is affected. We also provide comparison with the reconstructions given by the approach of [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF], which is the state-of-the-art approach at the moment. In the following, we denote [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF] as MDS, as the approach is based on multidimensional scaling. Our approach is denoted as RBF. Figure 4(a) gives the classification error rate obtained using our reconstructed faces as probes on FERET, and compares it with [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF]. One can see that the performance of MDS dramatically drops when the number of training images raises, while the error rate of our method regularly decreases, as expected. The bad behavior of MDS seems to be due to numerical instabilities since the range of gray levels in the output images diverges from the acceptable values (typically 0-255) when the number of training images increases. The error rate of 0.20, obtained by our method (with a face decoder trained with 921 images from MultiPIE), is to be compared with the error rate of 0.08, obtained with the original face images.

Figure 4(b) presents the classification error rates obtained on LFW. As in the experiments on FERET, the performance of our method (RBF) improves when the number of training images decreases and remains significantly better than the one obtained with MDS [START_REF] Mohanty | From scores to face templates: A model-based approach[END_REF]. Unlike what was observed on FERET, the performance of MDS does not drop when the number of training images increases. This may be due to the regularization effect induced by the variability of the LFW database. Finally, when training our decoder with 3000 training images, the classification error rate is of 0.29, which is to be compared with 0.18,obtained using the original images.

In conclusion, for both datasets, even if reconstructed images can not be recognized as well as the original ones, the error rate is low enough to prove that the chance to break in a system using synthesized images is significant.

Conclusions

At a time when more and more face images are available on-line on the Internet and when face technologies are spreading quickly, it is important to understand to what extent the face signatures manipulated and stored by face recognition applications respect user's privacy. In other words, we wanted to know if the information encoded in face signatures was sufficient to allow the reconstruction of face images and to allow the recognition of the persons they represent. For this purpose, we have proposed a simple and original reconstruction method based on RBF regression in the face eigenspace. The method has been experimentally validated on two datasets, on which we have shown that the reconstructed images (i) can be surprisingly visually similar to original ones and (ii) can fool a modern face recognition algorithm.

Figure 1 :

 1 Figure 1: Reconstructing FERET images. Top rows are real faces while bottom ones are faces reconstructed with a decoder trained with 921 training images.

Figure 2 :

 2 Figure 2: Reconstructing LFW images. Top rows are real faces while bottom ones are faces reconstructed with a decoder trained with 3000 training images.

Figure 3 :

 3 Figure 3: Reconstructing LFW images. For each face and from left to right: reconstructions with 300, 500, 1000, 2000, 3000 training images, and, finally, the real image.

Figure 4 :

 4 Figure 4: Classification results on FERET and LFW using the images synthesized from the templates.

Acknowledgments. This work was realized as part of the SECULAR program funded by the French National Research Agency (ANR), grant reference ANR-12-CORD-0014.