Anicet Kouomou-Choupo
email: anicet.kouomou_choupo@irisa.fr

Laure Berti-Équille
email: laure.berti-equille@irisa.fr

Annie Morin
email: annie.morin@irisa.fr

Optimizing Progressive Query-By-Example over Pre-Clustered Large Image Databases

The typical mode for querying in an image content-based information system is query-by-example, which allows the user to provide an image as a query and to search for similar images (i.e., the nearest neighbors) based on one or a combination of low-level multidimensional features of the query example. Off-line, this requires the time-consuming pre-computing of the whole set of visual descriptors over the image database. On-line, one major drawback is that multidimensional sequential NN-search is usually exhaustive over the whole image set face to the user who has a very limited patience. In this paper, we propose a technique for improving the performance of image queryby-example execution strategies over multiple visual features. This includes first, the pre-clustering of the large image database and then, the scheduling of the processing of the feature clusters before providing progressively the query results (i.e., intermediate results are sent continuously before the end of the exhaustive scan over the whole database). A cluster eligibility criterion and two filtering rules are proposed to select the most relevant clusters to a query-by-example. Experiments over more than 110 000 images and five MPEG-7 global features show that our approach significantly reduces the query time in two experimental cases: the query time is divided by 4.8 for 100 clusters per descriptor type and by 7 for 200 clusters per descriptor type compared to a "blind" sequential NN-search with keeping the same final query result. This constitutes a promising perspective for optimizing image query-byexample execution.

INTRODUCTION

The management of large collections of images adds the problem of efficiently handling and searching an overwhelming volume of digital contents and their associated descriptions. Challenges include balancing between rich content description and efficient storage with fast access methods at various levels (from pixels to semantics). Query-by-example exploits and combines visual descriptors whose computing costs increase proportionally to the database size. The exhaustive processing of a very great number of images with NN-searches turns to be quickly unaffordable to users desiring quick response time. Researchers from computer vision community have proposed a plethora of image description and retrieval methods that represent each image as a set of lowlevel features and provide users with a query-byexample similarity search to explore the database contents. However, the convergence between computer vision and database communities is not yet achieved regarding the two following points:

1. The main current research work trend deals with algorithmic approaches for nearest neighbors searches and early stopping approaches that focus on multidimensional but mainly monodescriptor datasets [START_REF] Berrani | Approximate k-Nearest Neighbor Searches: A New Algorithm with Probabilistic Control of the Precision[END_REF], [START_REF] Li | Clustering for Approximate Similarity Search in High-Dimensional Spaces[END_REF], [START_REF] Weber | Trading Quality for Time with Nearest Neighbor Search[END_REF].

2. Contrary to traditional databases where many works have been carried out on query optimization and more recently on adaptive query processing [START_REF] Babu | Adaptive Query Processing in the Looking Glass[END_REF], [START_REF] Gounaris | Adaptive query processing[END_REF], very few works have been proposed on image query-by-example optimization.

Motivated by such observations, we present in this paper a case study of how to apply a database optimization approach to an image query-by-example problem under the multi-descriptor paradigm. More recently, Kiranyaz and Gabbouj [START_REF] Kiranyaz | A novel multimedia retrieval technique: progressive query (why wait?)[END_REF] defined the notion of progressive query-by-example allowing intermediate results before the end of the whole database processing but the approach was limited to the periodic execution of the same sub-query with several descriptors on different portions of multimedia databases (images and videos) with no emphasis on scheduling the data subsets to process by NN-searches, or on merging the results from heterogeneous descriptors. Our research builds upon the implementation of progressive content-based image retrieval and upon previous experiments [START_REF] Kouomou-Choupo | Visual Feature Mining for Adapting Query-by-Example over Large Image Databases[END_REF] that extended the work of Kiranyaz and Gabbouj. For querying very large image databases, our assumption is that i) pre-clustering the image descriptions, ii) scheduling the NN-searches over the ranked set of relevant descriptors, and iii) presenting continuously the intermediate results during the running query should be more efficient and should offer more flexibility to users. We propose then a system of image retrieval that organizes image features into clusters and schedules their processing for progressive image retrieval. The system combines multiple visual global features and uses filtering rules to select the most relevant clusters to scan in priority.

The rest of the paper is organized as follows: Section 2 presents a synthesis of related work on indexing techniques, selection and scheduling clusters for image content-based retrieval. Our system is described in Section 3. Experiments and results are reported in Section 4. We conclude the paper in Section 5 and also present our research perspectives.

RELATED WORK

In computer vision community, many methods have been proposed to extract low-level visual images features. Some works deal with local descriptor extraction and try to build features that are invariant to geometric transformations and robust to illumination changes [START_REF] Schmid | Local Grayvalue Invariants for Image Retrieval[END_REF], [START_REF] Tuytelaars | Content-Based Image Retrieval Based on Local Affinely Invariant Regions[END_REF]. Others suggest global descriptors that are more simple information to cope with and less memory space and time consuming [START_REF] Obeid | Image indexing and retrieval using intermediate features[END_REF], [START_REF] Tao | Object-Based image retrieval using point feature maps[END_REF]. However, one of the basic questions to address in an image database system is to define when two images may be considered similar. Similarity of images has been characterized in the literature through three important features: colour, texture and shape [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] and systems that combine computer vision techniques to measure the similarity between images are also proposed [START_REF] Yamane | Multi-Vector Feature Space Based on Pseudo-Euclidean Space and Oblique Basis for Similarity Searches of Images[END_REF]. In this paper, we are essentially dealing with query-by-example on general real-world images. Global features remain best suited in this case and we privilege merging results of several descriptors instead of defining new distances on a combination of features. We assume that each feature is effective separately and that merging results is appropriate to answer multidescriptor queries. We then focus in this paper on the efficiency of our approach.

The second question to address is indexing highdimensional descriptors. Large image databases have to be indexed in order to make the retrieval efficient. The general principle of indexation schemes is to gather in the same cell all feature vectors that are collocated in the multidimensional space. Cells can then be included within a specific indexing structure like trees. Indexation techniques that are either based on data partitioning (such as R-Tree [START_REF] Guttman | R-trees: A dynamic Index Structure for Spatial Searching[END_REF]) or on space partitioning (such as k-d-Tree [START_REF] Bentley | Multidimensional binary search in database applications[END_REF] or GridFile [START_REF] Nievergelt | The GridFile: An adaptable, symmetric multikey file structure[END_REF]) are well adapted to low-dimensional vectors (≤ 16 dimensions according to [START_REF] Weber | A Quantitative Analysis of Performance Study for Similarity-Search Methods in High-Dimensional Spaces[END_REF]). High dimensional data spaces have some specific properties which severely affect retrieval methods, making a sequential search perform better. These property have been studied and reported in [START_REF] Beyer | When Is "Nearest Neighbor[END_REF], [START_REF] Weber | A Quantitative Analysis of Performance Study for Similarity-Search Methods in High-Dimensional Spaces[END_REF]. New indexation schemes have to be defined and adapted to the high-dimensional vectors. Cornacchia et al [START_REF] Cornacchia | A Case Study on Array Query Optimization[END_REF] propose a system based on Relational Array Mapping that naturally extends existing database functionalities in terms of indexing to cope with multidimensional arrays. The strength of the system lies on a specific algebra (Relational Array Mapping Algebra) to generate optimized query execution plans and to improve expressiveness of the database system. In our work however, we stay in multidimensional space: we organize images into clusters and we determine a ranked list of clusters per query for efficiently and effectively retrieving the most similar images according to all the available descriptors in the database. This ranked list of the most eligible clusters defines a query execution strategy for the given query-by-example.

Once the questions of similarity of images and indexing high-dimensional features have been addressed, the objective is to define and to elaborate efficient strategies for image retrieval. Retrieval methods are closely related to the underlying indexation schema. Nearest Neighbors algorithms typically use the geometrical properties of cells to eliminate those cells which can not have any impact on the result of the current query [START_REF] Böhm | Searching in Highdimensional Spaces: Index Structures for Improving the Performance of Multimedia Databases[END_REF]. Filtering rules are sometimes used for searching exact nearest neighbors and for eliminating irrelevant cells, avoiding the subsequent analysis of all the vectors they contain, which, in turn, reduces response time.

But the "curse of dimensionality" phenomenon makes these filtering rules ineffective on high-dimensional datasets [START_REF] Korn | On the 'Dimensionality Curse' and the 'Self-Similarity Blessing[END_REF], [START_REF] Weber | A Quantitative Analysis of Performance Study for Similarity-Search Methods in High-Dimensional Spaces[END_REF], [START_REF] Beyer | When Is "Nearest Neighbor[END_REF], [START_REF] Böhm | Searching in Highdimensional Spaces: Index Structures for Improving the Performance of Multimedia Databases[END_REF]. There is therefore an increasing interest in performing approximate NN-searches, where the quality of result is traded off against reduced query execution time. Weber and Böhm with VA-File [START_REF] Weber | Trading Quality for Time with Nearest Neighbor Search[END_REF] and Li et al. with Clindex [START_REF] Li | Clustering for Approximate Similarity Search in High-Dimensional Spaces[END_REF] perform approximate NN-searches by interrupting the search after having accessed an arbitrarily fixed number of cells. These two techniques are efficient in terms of response time, but give no clue on the quality of the result returned to the user. Berrani et al. [START_REF] Berrani | Approximate k-Nearest Neighbor Searches: A New Algorithm with Probabilistic Control of the Precision[END_REF] control the precision of the search by setting at run time the maximum probability for a vector that would be in the exact answer set to be missing in the approximate set of answers. They use approximated cells' radii which improve the effectiveness of filtering rules and speed up the NNsearch. Our work does not currently use approximate cells' radius for mono-descriptor NN-search. Our focus is at a higher multi-descriptor level over a preclustered large database. Our approach is nevertheless complementary. We defined approximate filtering rules over eligible clusters with all descriptors taken together and experimentally quantify the introduced approximation on the result quality.

PROGRESSIVE CONTENT-BASED IMAGE RETRIEVAL

Image query-by-example may use a combination of several types of visual descriptors whose timeconsuming computing costs increase proportionally to the database size. At the query-time, the exhaustive processing of a very great number of images with NN-search turns to be quickly unaffordable to users desiring quick response time. In this context, our twofold assumption is: i) pre-clustering the image features of large databases and scheduling the NNsearch over a ranked set of relevant clusters of descriptors should improve the performance of image query-by-example and ii) sending continuously the intermediate results of the search in progress should offer more flexibility to the users.

Image Database Pre-Clustering

Image files are gathered on the hard disk and global descriptions of the images are pre-computed for m types of descriptors d i (d i ∈ D, i=1,2,…,m). For each descriptors type d i , the image descriptions are organized into clusters with a k-means-like clustering method which reuse the k-means principle but replace the computed virtual centroid by the nearest existing image (which will be called centroid for the sake of simplicity). This approximation is introduced to allow an appropriate computing of distances between image query and clusters' centroids for a given descriptor type. Several clusters characteristics are stored in a binary file: their size in term of number of elements they contains, their centroid, and their position in the binary file. For each descriptor type, an image is described by a vector with variable length per descriptor type. On the one hand, the choice of the number of clusters as input for the k-means algorithm [START_REF] Jain | Algorithms for Clustering Data[END_REF] remains a well-known difficult problem. Our first experimental approach was to take a number of clusters per descriptor type in order to have clusters with almost the same size. Our previous experiments reported in [START_REF] Kouomou-Choupo | Visual Feature Mining for Adapting Query-by-Example over Large Image Databases[END_REF] show that the equal number of clusters per descriptor type does not change the results from one descriptor type to another. Section 4 will give details on this choice. On the other hand, k-means is not effective dealing with outliers, but our interest is focused on search strategies and outliers' management is not in the scope of this paper. Moreover, it has been shown that minimizing the search time suggests to generate uniformly sized clusters [START_REF] Sigurðardottir | A Case Study of the Quality vs. Time Trade-off for Approximate Image Descriptor Search[END_REF].

Image Querying by Example

Based on the pre-clustering of the image database, our image retrieval process includes the following steps (Figure 1): (i) the user submits an image query to the system and all the features available for image description are computed from the image query; (ii) clusters characteristics related to the query are scanned. For example, distances from the centroid of clusters to the image query, maximum and minimum distances from the query to clusters are computed at this step; (iii) the clusters are ranked based on their characteristics; (iv) filtering rules are applied to select the most relevant clusters and to speed up the retrieval process; (v) clusters scanning is scheduled to provide to users the best results as soon as possible: progressive query is executed based on the scheduling of the clusters scan and intermediate results are continuously presented to the user ; the process loops from the step (iv) until there does not remain any cluster to analyze. In a query-by-example scenario with a similarity search target (comparable to searching similar images on the web), users submit an image as a query to the system to get in return the most similar images to the image-query according to particular visual criteria. Users may know how to choose visual descriptors. However, it generally happens that they do not have any idea of the most discriminating descriptor to use for their query. For such a case, our approach finds and assigns priorities on the clusters of image descriptions and, consequently, proposes continuously a list of ranked clusters for optimizing the query-by-example execution. The following section formalizes the key notions of our approach that are: the cluster eligibility criterion and the filtering rules upon which our method is based for significantly improving the performance of image query-by-example.

Selecting and Scheduling Feature Clusters

Let m be the number of features and n the number of clusters for each descriptor type. We choose to compute, for each cluster C ij (j=1, 2,..., n) of descriptor type d i (i=1,2,…,m), the distance from its centroid to the submitted image-query, noted I q . This distance is noted for simplification: Dist(I q ,C ij ). Computing the distance depends on the nature of the multidimensional feature. In the case of MPEG-7 global descriptors, the distance is generally a quadratic or a weighted Manhattan distance. We define the cost of a given cluster C ij , to be the vector dimension of the descriptor type d i multiplied by the number of vectors that the cluster C ij contains. This cost is noted Cost(C ij ). We normalize Dist(I q , C ij ) and Cost(C ij ) for all d i (i=1,2,…,m) in order to make them independently comparable. NormDist(I q ,C ij ) and NormCost(C ij ) indicate respectively the normalized distance and the normalized cost of the cluster C ij . These measures are defined by Eq. ( 1):

= = - = ) ( ) , ( ) ( ) ( ij ij q C Cost X or C I Dist X with X X E X NormX σ (1) ) (X E and ) (X σ
are respectively estimated by mean and standard deviation of X for the descriptor type d i . These normalized measures are combined to define the eligibility criterion of each cluster C ij for the image-query I q such as:

0 } 1 , 0 { , ) ( min ) ( ) , ( min ) , ( ) , ( .. 1 .. 1 .. 1 .. 1 ≠ + ∈ - + - = = = = = β α β α β α and with C NormCost C NormCost C I NormDist C I NormDist C I y eligibilit ij n j m i ij ij q n j m i ij q ij q (2)
This formula is limited to the extreme cases of behavior of normalized measures studied separately, and the equally weighted combination of theses measures. The study can be easily extended to the general case of a weighted combination.

We also propose two filtering rules in our retrieval process. More formally, for a descriptor type d i , let R ij be the radius of the cluster C ij . It is equal to the distance between the centroid of C ij and its farthest point. We define the minimum distance d min between the image query I q and the cluster C ij by Eq. ( 3):

> - = else R C I Dist if R C I Dist C I d ij ij q ij ij q ij q 0 ) , ( ) , ( ) , ( min (3)
The first rule (R1) has been adapted from [START_REF] Berrani | Approximate k-Nearest Neighbor Searches: A New Algorithm with Probabilistic Control of the Precision[END_REF]. It consists of discarding all clusters which the minimum distance to the image query I q is greater than a computed threshold. It is stated as follows:

R1 : If )) NN k , d(I ), R ) C , (Dist(I C I d q ip ip q k ) Card(C 1..n p ij q ip + ≥ ≥ = min min( ) , ( min then C ij is irrelevant (4)
where Card(C ip ) is the number of vectors of the cluster C ip (p=1,2,...,n), k the number of nearest neighbors to search, and d(I q , kNN) the distance between the image query I q and the current k th nearest neighbour. The rule (R1) simply exploits a shape property of clusters, ensuring the correctness of It is however possible to use a rule stronger than the rule (R1) which exploits the sensibility of the chosen clustering method regarding outliers in order to discard from the search, all clusters which the minimum distance to an image query is not null. This second rule is stated as follows:

R2: If 0 ) , ( min > ij q C I d then C ij is irrelevant (5)
If the query belongs to the image database, it then belongs to one cluster for a given descriptor and intuitively, it is very probable the cluster contains some neighbors of the query. According to the definition of d min (see Eq. ( 3)), the rule (R2) then indicates the condition under which a cluster may be supposed far from the query, and thus irrelevant.

Merging of Intermediate Query-byexample Results

Our content-based image retrieval system searches for the most similar images and gradually uses the available descriptors. Intermediate results are produced as soon as the NN-search has been done over one of the most eligible clusters and they are progressively merged together with the intermediate results of the previous searching phases. The fusion of the result lists obtained from the similarity search on various multidimensional descriptors is a complex problem. We use the merging function introduced in our previous work [START_REF] Kouomou-Choupo | Visual Feature Mining for Adapting Query-by-Example over Large Image Databases[END_REF].

Consider at a given searching phase p, the similarity search is done over the cluster C i 0 j of the descriptor type d i 0 . We note {d 1 , d 2 ,..., d m 1 } the subset of m 1 descriptors type corresponding to the clusters that have already been processed at the end of the searching phase p (m 1 ≤ m). The Top N list of intermediate results on the descriptor type d i is noted

l i , 1 ≤ i ≤ m 1 .
For the searching phase p, the list l i 0 is updated by taking into account the processing of cluster C i 0 j . Then, the list l i 0 is merged with the other

lists l i (1 ≤ i ≤ m 1 , i ≠ i 0 )

in order to obtain the final

Top N list of results. To cope with the problem of Top N lists fusion, we define a scoring function for an image I such as:

( ) ( ) ( ) ( ) ( ) [ ] ( )
1 l I if 0 1 , 1 , 0 2 1 1 1 1 i 1 = ∉ ∈ = ∈ + = = = m i i i d d m i d d i f and l I if I f I S with I S I f I S i i i i α α (6) ( ) I S i d
is the score of the image I for the descriptor type d i . It is proportional to the similarity between the query-by-example I q and I according to the descriptor type d i . α i (i=1..m 1 ) are weights of descriptors type d i .

This function takes into account the presence of an image in the list of results for a given descriptor type and the score of the image in that list. Hence, all images appearing more often and that having high scores in individual lists are relevant. The main advantage of the proposed fusion function is its granularity that allows merging intermediate result lists after each cluster scan whatever the descriptor type may be. Nevertheless, our experimental study on the efficiency is comparative: we use the same fusion function for both approaches, for the "blind" sequential search and for our progressive and selective execution strategy. No bias is introduced regarding to the fusion of results lists. Moreover, other methods of result aggregation as OMEDRANK [START_REF] Fagin | Efficient similarity search and classification via rank aggregation[END_REF] can be adapted and used.

EXPERIMENTS

To validate our propositions, we set up experiments with 110,291 still images and five global MPEG-7 descriptors of color (named ColorLayout, ScalableColor), texture (HomogeneousTexture, EdgeHistogram) and shape (RegionShape). In the following, descriptor types are abbreviated respectively as CLD and SCD for color, HTD and EHD for texture, and RSD for shape. CLD descriptor type uses L 2 distance but others are defined with L 1 distance. The images are gathered into clusters for each descriptor type with the k-means-like algorithm described in Section 3.1. The images of our database are provided by a photo agency. We do not have any detail on their source to consider a robust plan of sampling. The images are heterogeneous and mostly dedicated to press agencies and professional users. One hundred of images that do not belong to the database have been chosen randomly as queries examples for testing and evaluating our method implemented in C++ under Linux (Pentium 4, 3 GHz, with 1 Gb of main memory). The objective is to organize the image set for optimizing the image query-by-example execution. For each image query, we search for their 15 nearest neighbors. Without user's relevance feedback, it is meaningless to evaluate precision and recall and, also the subjective quality of the retrieved results with no prior knowledge on the application context or on the underlying search targets. For this reason, we mainly focused, in these experiments, on the problem of performance, and we proposed to measure quality relatively to the final result list obtained at the end of a "blind" sequential NN-search. This definition of the quality is of course relative but gives a good idea of the gain on query time of our approach without quality loss compared to the classical sequential search. The relative quality is computed by counting the number of common images in each intermediate result list and those in the final result obtained at the end of the "blind" sequential search.

In the following section 4.1, we test our method by first studying parameters α and β of the cluster eligibility formula in Eq. ( 2). Then, in the section 4.2, we evaluate the two filtering rules proposed in ( 4) and [START_REF] Böhm | Searching in Highdimensional Spaces: Index Structures for Improving the Performance of Multimedia Databases[END_REF]. A short study is made in section 4.3 to show the interest of combination of feature for content-based image retrieval.

Cluster Eligibility

We performed experiments on the eligibility measure for different values of the necessary number of clusters given as input to the k-means-like algorithm. For the sake of simplicity, we choose to detail the case of 100 clusters per descriptor type. Nevertheless, we made experiments on 10, 50 and 100 clusters per descriptor type that showed that the behavior we will describe further is similar over the database whatever the number of clusters may be. Figure 2 and Figure 3 represent respectively the variations of the relative quality (compared to a "blind" sequential NN-search) and the corresponding response time according to the searching phases. A searching phase corresponds to the end of a cluster scan with NN-search. Values in parenthesis correspond to different values for the parameters α and β in Eq. ( 2): (1,0) is associated to α=1 and β=0; (1,1) corresponds to α=1 and β=1; and (0,1) to α=0 and β=1.

The eligibility based on the distance from the cluster centroid to the image-query obviously improves the speed of the global search processing: the same result than the one obtained in a "blind" sequential search is reached much more quickly (as shown in Figure 2): a "blind" sequential search will be carried out over 500 clusters (100 clusters × 5 descriptors) before sending the final Top N list of results. In our approach, this final list of results can be reached after the scan of 110 clusters (see the grey circles and the intersecting dotted lines on the graphs). For the case of 100 clusters per descriptor type, this corresponds to a gain of about 77% on the average time (i.e., 3.5s instead of 15s) compared to a "blind" NN-search as it is shown in Figure 3.

Effectiveness of Filtering Rules

The effectiveness of the filtering rules defined previously by ( 4) and ( 5) has been compared using three values of the number of clusters per descriptor type, respectively 10, 100, and 200 clusters per descriptor type. We have then plotted variations of the relative quality and the corresponding cumulated time per searching phase in these three cases (Figure 4(a-c) and Figure 5(a-c)). Figure 4 confirms that the filtering rule (R1) assures the correctness of the retrieved results. Our experiments show that the approximation introduced by the filtering rule (R2) tends to be greater due the reduction of clusters radius as the number of clusters per descriptor increases.

Concerning the effect of using the filtering rules on the searching time, our experiments show that the searching time decreases as the number of clusters per descriptor increases. The filtering rules (R1) and (R2) are then more efficient with small clusters radius. For the case of 10 clusters per descriptor type, Figures 4(a) and 5(a) show that: i) using a "blind" sequential search, the system retrieves 15 nearest neighbors over 15 in 16.8 seconds as average time; ii) using the rule (R1), the system retrieves 15 nearest neighbors over 15 in 12 seconds, which represents the sequential searching time divided by 1.4; iii) using the rule (R2), the system retrieves 15 nearest neighbors over 15 in 10 seconds, which represents the sequential searching time divided by 1.68.

For the case of 100 clusters per descriptor type, Figures 4(b) and 5(b) show that: i) using a "blind" sequential search, the system retrieves 15 nearest neighbors over 15 in 16.8 seconds as average time; ii) using the rule (R1), the system retrieves 15 nearest neighbors over 15 in 8 seconds, which represents the sequential searching time divided by 2.1; iii) using the rule (R2), the system retrieves 14.5 nearest neighbors over 15 in 3.5 seconds, which represents the sequential searching time divided by 4.8.

For the case of 200 clusters per descriptor type, Figures 4(c) and 5(c) show that: i) using a "blind" sequential search, the system retrieves 15 nearest neighbors over 15 in 16.8 seconds as average time; ii) using the rule (R1), the system retrieves 15 nearest neighbors over 15 in 6.1 seconds, which represents the sequential searching time divided by 2.76; iii) using the rule (R2), the system retrieves 14 nearest neighbors over 15 in 2.4 seconds, which represents the sequential searching time divided by seven.

We then conclude that filtering rule (R2) is more efficient than filtering rule (R1) in terms of searching time according to Figure 5. Filtering rules (R1) and (R2) improve the efficiency of retrieval. While the rule (R1) preserves the correctness of results, the important gain of time obtained with using the rule (R2) is compensated by a light loss of result quality.

It is interesting to evaluate the impact of the rules on the clusters scanning for each descriptor type. Tables 1 and2 present the mean of scanned clusters at the end of NN-search for each descriptor type. Each row corresponds to one of the three cases of the given number of clusters per descriptor type (respectively 10, 100, and 200 per descriptor type). As one could expect, much less clusters are scanned using rule (R2) for the same result list.

We also realize that the rule (R1) is particularly inefficient on clusters of EHD and RSD showing in this way the sensibility of the rule to the descriptor upon which it is applied. The number of scanned clusters for the rule (R2) gives an idea of clusters overlapping. According to Table 2, clusters of descriptors EHD and RSD overlap more than others, which explain the inefficiency of the rule (R1). The rule (R2) may be used at the beginning of the search process providing the user with a first result near to the final one and then, the rule (R1) can be used to keep on the search.

Interest of the Combination of Global Features

This subsection aims at evaluating how the combination of descriptors type may be useful in the content-based image retrieval context. Images used to perform experimentations on the global descriptors type combination interest are provided by the database MOVI 1 which contains 32 sequences. Each sequence represents the same scene (2 or 3D) taken in different conditions (variation of the intensity of the main light source, rotation, occlusion …). MPEG-7 descriptors of images of the database MOVI are computed and added to that of 110,291 images used to evaluate the performance of our retrieval system. We arbitrarily choose one image in each MOVI's sequence as query and retrieved results for each descriptor type are merged using function defined by equation [START_REF] Cornacchia | A Case Study on Array Query Optimization[END_REF]. We then compute the traditional recall, precision and F-measure [START_REF] Rijsbergen | Information Retrieval[END_REF] of the merged results.

No standard method exists to choose the appropriate number of nearest neighbors to retrieve. As sequences are of different lengths (in term of the number of images they contain), we have chosen to retrieve for each query the number of nearest neighbors equals to the length of the sequence the query belongs to. In these conditions, recall, precision, and F-measure are all equal. In the following, we will only present results based on the F-measure.

According to table 3, SCD and EHD descriptors type have the best recognition rate. Hence, color and texture descriptors perform well on our data. To each descriptor type, we affected a weight proportional to its F-measure (see Table 3) and we computed F-measure of systems obtained by the combination of descriptor type. Results are consigned in Table 4. This table shows that combining 4 descriptors type like CLD-SCD-HTD-EHD or 5 descriptors type like CLD-SCD-HTD-EHD-RSD, one obtains a recognition rate of 63 %, which is better than using only SCD descriptor (60 % of recognition rate). We also remark that using combinations such that CLD-SCD or HTD-EHD does not yield better results than using SCD or EHD alone. Using HTD-EHD-RSD is not better than using HTD-EHD. We then conclude that in the CLD-SCD-HTD-EHD-RSD combination, descriptors SCD and EHD play the most interesting role in term of recognition. This conclusion confirms observations made with the table 3.

CONCLUSION

In this paper, we have presented a novel approach for improving the query-by-example execution performance over a large image database compared to a "blind" sequential NN-search using several lowlevel global features. The proposed approach is based on the pre-clustering of the database and on the use of the cluster eligibility measure and two filtering rules we defined to improve image query-by-example performances compared to the "blind" search while keeping the same quality of results.

Experiments over 110,291 images and five global MPEG-7 descriptors have shown that our approach provides the following interesting insights: (i) the progressive query-by-example processing combines advantageously several descriptors without any knowledge on the descriptor types from users; (ii) relevant clusters are automatically selected, ranked and scheduled for NN-search using the cluster eligibility measure; (iii) the use of filtering rules over multi-descriptor clusters improves the query processing: for 100 clusters per descriptor type, by dividing by 4.8 the average time of a "blind" sequential NN-search and for 200 clusters per descriptor type, by dividing by 7 the average time, which are very promising results.

The originality of the proposed approach is that it can be applied to all kind of image databases with taking advantage of the combination of several low-level global features for query-by-example execution strategies. However, several interesting issues remain open. Our perspectives in convergence of image processing and database techniques are twofold: i) concerning the optimization of image query-byexample execution strategies over several descriptors without a priori knowledge on them, we are currently exploring the techniques of adaptive query processing and working on a query-by-example cost model for improving the query time. We will pursue our experimentations on data mining techniques introduced in [START_REF] Kouomou-Choupo | Visual Feature Mining for Adapting Query-by-Example over Large Image Databases[END_REF] to improve query performance. In addition, more formal study should be done to control approximations introduced by filtering rules we proposed; ii) concerning the evaluation of quality of results (and for extending the notion of relative quality we proposed by comparison to a "blind" NNsearch) without knowledge of user's search target, we are planning to extend our analysis and experiments to more general query scenarios with including precision, recall and users' relevance feedback tracking to have a more interactive system. This implies that query execution has to be dynamically adapted using optimal strategies of selecting and scheduling clusters.

Figure 1 .

 1 Figure 1. Steps in the progressive retrieval process.

  comparing to the sequential search.

Figure 2 .

 2 Figure 2. Relative quality of results depending on the eligibility of clusters: 100 clusters per descriptor type.

Figure 3 .

 3 Figure 3. Query by example execution time depending on the eligibility of clusters: 100 clusters per descriptor type.

Figure 4 .

 4 Figure 4. Comparison of the filtering rules on the average number of NN found.

Figure 5 .

 5 Figure 5. Comparison of the filtering rules on average time.

Table 1 . Number of scanned clusters for the filtering rule (R1)

 1

		CLD SCD	HTD EHD RSD
	10×5	10	10	7	10	10
	100×5	53	62	44	78	94
	200×5	83	103	72	144	190

Table 2 . Number of scanned clusters for the filtering rule (R2)

 2

		CLD SCD HTD EHD RSD
	10×5	8	9	6	8	10
	100×5	21	26	23	35	78
	200×5	23	32	27	46	141

Table 3 . F-measure of the system with one descriptor type

 3

	Descriptor type	F-measure
	CLD	0.40
	SCD	0.60
	HTD	0.23
	EHD	0.41

1

Available at: http://www.irisa.fr/texmex/base_images/index.html


Marc Lacruche

Noemie Beringuier-Boher

Jean-Max Dutertre

Jean-Baptiste Rigaud

Edith Kussener

On the Use of Forward Body Biasing to Decrease the Repeatability of Laser-Induced Faults

This paper presents a study on the effect of Forward Body Biasing on the laser fault sensitivity of a CMOS 90 nm microcontroller. Tests were performed on a register of this target, under several supply voltage and body bias settings, showing significant laser sensitivity variations. Based on these results, a method which aims at decreasing fault repeatability by using variable supply voltage and body bias settings is proposed. Finally, tests are performed on an implementation of this method on a temporally redundant AES and the results are presented.

I. INTRODUCTION

With the constant push for more power-efficient circuits, it is essential to make sure that low-power design techniques do not compromise the secure elements of the devices they are used in. Fault attacks are a particular concern as low-power devices are often vastly deployed, giving easy physical access to the attacker.

Fault attacks aim to disturb a device and exploit the resulting computation errors to recover secure informations. Existing attacks include the Differential Fault Analysis (DFA) [START_REF] Piret | A differential fault attack technique against spn structures, with application to the aes and khazad[END_REF] that uses the differences between a faulty cipher and the correct one to recover the key of an algorithm such as the AES [START_REF] Daemen | The design of Rijndael: AES-the advanced encryption standard[END_REF].

Many methods exist to perform fault attacks, including voltage or clock glitches [START_REF] Agoyan | When clocks fail: On critical paths and clock faults[END_REF], electro-magnetic pulses [START_REF] Dehbaoui | Injection of transient faults using electromagnetic pulsespractical results on a cryptographic system[END_REF] and more recently body biasing injection [START_REF] Maurine | Yet Another Fault Injection Technique : by Forward Body Biasing Injection[END_REF]. Laser fault injection is one of these methods, it was introduced in the field of hardware security by S. Skorobogatov and R. Anderson in [START_REF] Skorobogatov | Optical fault induction attacks[END_REF]. It uses the photoelectric effect to induce currents locally in a circuit to disturb its operation. [START_REF] Buchner | Pulsed-laser testing for single-event effects investigations[END_REF] This paper takes a look at the effect of Forward Body Biasing (FBB) [START_REF] De | Multiple well transistor circuits having forward body bias[END_REF] as a low-power design method on the vulnerability of a circuit to laser fault injection: first, FBB is briefly introduced. The next part presents the results of experiments where laser fault injection was performed on a register of a microcontroller embedding FBB capabilities. Then, a method based on the previous results is proposed, aiming at decreasing fault repeatability by using the sensitivity variations induced by the use of FBB and modified supply voltage values. Finally, in the last section, this method is applied to a temporally redundant hardware AES as a proof of concept and test results are presented.

II. TRIPLE WELL AND FORWARD BODY BIASING

In standard bulk CMOS architectures, NMOS transistors are located in the P-Substrate, and PMOS transistors are located in a N-Well itself located in the P-Substrate. Commonly, the P-Substrate is biased at ground voltage while the N-Well is biased at V dd .

In a triple-well architecture (figure 1), NMOS may be located in a P-Well isolated from the P-Substrate by a deep N-Well layer underneath and an additional N-Well on the side. Having an isolated P-Well for NMOS transistors allows the use of body biasing on both NMOS and PMOS (as opposed to only the PMOS when using bulk technology). The NMOS body bias voltage is set at V bbN = V bb and the PMOS body bias voltage at V bbP = V dd -V bb . Using a positive V bb value, is called Forward Body Biasing (FBB) while using a negative V bb value is referred at as Reverse Body Biasing (RBB). Using FBB or RBB allows to adjust the leakage and frequency of the transistors by acting on their threshold voltage (V T ) [START_REF] Tschanz | Adaptive body bias for reducing impacts of dieto-die and within-die parameter variations on microprocessor frequency and leakage[END_REF]. FBB allows to increase frequency at the expense of leakage while RBB has the opposite effect.

This paper is focused on the use of FBB as a low-power design method. Indeed, FBB can be used to reduce power consumption at equivalent timing performance by lowering supply voltage and using FBB to offset the performance hit.

III. PRELIMINARY EVALUATIONS

The first evaluation step was to test whether V dd variations and FBB had an effect on the sensitivity of a chip to laser fault injection. To do so, a 32-bit register located on a CMOS 90 nm microcontroller with V dd scaling and FBB capabilities was targeted. Possible core V dd values were 1.13 V, 1.26 V and 1.32 V and FBB could be either set to FBB ON (V bb =400 mV) or FBB OFF (V bb =0 mV).

A. Test Setup

The laser test bench used has its objective mounted on a motorized XYZ table, allowing the automation of the mapping process. The register covers a 70 µm by 80 µm area out of which a 25 µm by 25 µm square in the middle of it was targeted (due to mapping time constraints) and mapped with a 0.5 µm step grid. For each position fault injection was performed while using every possible V dd /FBB combination and the register set to 0xFFFFFFFF and 0x00000000.

The injection was done through the backside of the chip using a 1064 nm wavelength laser (IR). Laser pulse duration was 50 ns and the size of the spot was 1 µm. The targeted chip was thinned to a substrate thickness of 140 µm.

B. Results

1) Laser-Sensitive Area: The first tested metric was the evolution of the laser-sensitive area depending on the V dd /FBB configuration for a fixed laser power of 0.6 W. This power is just under the cell destruction threshold.

Since the mapped area has the same fixed number of points for every configuration, the evolution of the laser-sensitive area can be measured by looking at the number of faults that were recorded on the map for a given V dd /FBB configuration. Figure 2 summarizes the sensitive area for each V dd /FBB pair.

The first trend that we can extract from the histogram is that lowering V dd increases the sensitive area and turning FBB ON results in another sharp increase in sensitivity. Overall, the fault count for the most sensitive configuration (V dd =1.13 V and FBB ON) is about twice as important as the sensitive area of the least sensitive configuration (V dd =1.32 V and FBB OFF).

2) Laser Power Influence: The second step was repeating the experiment with several laser power values. The goal was to find the laser power threshold from which faults start to appear as well as the rate at which sensitivity increases depending on power for each V bb /FBB pair.

For each position of the map, tests were performed with laser power varying from 0.25 W to 0.40 W with a step of 0.02 W. Table I displays the obtained laser power thresholds. Similarly to the previous results, a lower V dd is linked to a higher laser-sensitivity (ie. a lower fault injection threshold) and activating FBB further increases the sensitivity. The same trend can be observed on the graph showing the fault count versus the laser power (figure 3).

V dd FBB OFF FBB ON (400mV) While they will obviously vary depending on the technology used, these results give a good overview of the trends that can be expected when applying a reduced V dd and using FBB. Lowering V dd increases the laser sensitivity, and turning FBB ON introduces another sharp increase in sensitivity.

However, these results do not introduce any new major security vulnerability as the laser power threshold variations are still in the power range of common laser power sources. The main concern is that the sensitivity increase diminishes the efficiency of sensors-based countermeasures as lowering the fault threshold can push it under the detection threshold of the sensors. When performing fault-attacks, fault repeatability and predictability are important factors for the success of many attacks such as the ones described in [START_REF] Fuhr | Fault attacks on aes with faulty ciphertexts only[END_REF]. They also help breaking redundancy-based countermeasures. As such, it is the defender's best interest to minimize those parameters.

Although the previous results should have a limited impact on device vulnerability, the following section is going to show how the varying sensitivity when using different V dd /FBB configurations can be used to harden a circuit against laser fault injection by reducing fault repeatability.

A. Principle

When performing laser fault injection with increasing laser power, it is possible to distinguish different laser power ranges for which different fault types are injected. For very low laser power values, no faults will be induced, then when attaining the fault threshold, limited faults will appear (single bit/byte faults). Further increasing the power will eventually induce multi bit/byte faults, and finally a threshold leading to permanent chip damage will be attained.

As shown in section III-B2, it is possible to use V dd /FBB to modify the threshold at which faults appear and increase or decrease the laser sensitivity of a circuit.

Figure 4 depicts how the sensitivity of the cell will vary when using different V dd /FBB settings, effectively moving the laser power thresholds up or down the laser power scale. Using this, it is possible to decrease the repeatability and predictability of laser induced faults by using varying V dd /FBB settings over time.

B. Proof of Concept Implementation

As a proof of concept, we applied this technique to temporal redundancy which consists in computing two (or more) identical encryptions one after the other using the same hardware and comparing the results. If the outputs of both encryptions are identical the result is returned, otherwise the error is detected and an action can be taken (block the output, return a random cipher, raise an alarm etc.). This means that an attacker would have to inject two identical faults consecutively to retrieve a faulty cipher, rendering fault attacks much more complex to implement. It also has the advantage of being simple to implement and is a quite immediate application of the proposed method. To do so, the same microcontroller as in the previous tests is used as it includes a hardware cryptoaccelerator that can perform AES calculations.

Two power supply configurations are defined: a lowsensitivity configuration using V dd =1.32 V and FBB OFF and a high-sensitivity configuration using V dd =1.13 V and FBB ON. The first calculation of the redundancy is performed using the low-sensitivity configuration and the second one using the high-sensitivity configuration. The assumption is that two different faults will be induced, leading to the detection of the attack, even if the attacker is able to perform two consecutive laser shots at the exact same instant of the algorithm.

C. Test Setup and Procedure

Using the same laser test bench as previously described, the test is set up as follows:

• The map covers a region of 200 µm x 300 µm inside the hardware AES of the microntroller with a step of 5 µm. • In order to speed up the mapping, one encryption is performed on each position, if a fault is injected, the mapping stops and performs 2000 encryptions on the current position (1000 times one low-sensitivity encryption followed by one high-sensitivity encryption) before continuing with the rest of the map. • The crypto-accelerator clock runs at 50MHz.

• The microcontroller sends a trigger signal to the laser before each encryption, targeting the second to last round of the AES (the laser shoots after a fixed delay after receiving the trigger signal). • Laser power is fixed at 0.7W and pulse duration at 50 ns (the minimum pulse duration of the laser source).

As described in figure 5, the results of consecutive encryptions are compared in order to obtain what would have been the output of different redundancy types: a hardened redundancy (one computation with each sensitivity setting), a simple redundancy with both computations in the high-sensitivity mode and a simple redundancy with both computations in the low-sensitivity mode. • Double fault: a successful injection of the same fault on two consecutive AES computations. In which case the redundancy is broken and the faulty cipher is returned. • Two different outputs: either two different faults or only one of the two computation is faulted. Here, the AES is safe thanks to the redundancy and the attack is detected. • No fault: no faults were injected on either computations.

AES AES

Here, the system is safe but the attack is not detected. II reports the results obtained over all the tested positions. When looking at double fault-rate, the hardened redundancy is more resistant to double faults than the other two configurations. The difference is especially important compared to the high-sensitivity configuration which is the FBB use-case that was considered early on in this paper. The hardened redundancy also has the highest rate of two different output results by a large margin which makes it the best at both preventing double faults and detecting unsuccessful attacks.

While the results of the two first rows from the table were foreseeable, the last one is a bit unsuspected. The lowsensitivity mode has the highest no-fault rate as expected, but the hardened redundancy is lower than the high-sensitivity mode, which means that there are a non-negligible number of cases where a fault appears on the low-sensitivity configuration and not on the high-sensitivity configuration.

Overall the proposed method looks quite effective at both limiting the ease of creating a double fault and increasing the ability to detect the attack.

2) Result Maps: We drew maps out of the results, but no particular spatial tendencies were observed. All the redundancies performed equally over the tested surface. The only interesting information was that for a few number of points faults would appear in low-sensitivity mode and not in highsensitivity mode.

3) Positional Comparisons: The last evaluation parameter is the effectiveness of the counter-measure on a position by position basis. Figure 6 shows the comparison location by location between the hardened redundancy and the highsensitivity redundancy. Each point represents a tested position from which the x coordinate is the hardened redundancy double fault rate and the y coordinate is the high-sensitivity redundancy double fault rate. For example, a point located in the top left corner of the chart represents a tested location for which the double fault rate was 100% using the highsensitivity redundancy and 0% using the hardened redundancy (ie. the ideal case). Points on the diagonal are positions for which both redundancies are as effective as each other. Hence, points above the diagonal are the positions for which the hardened redundancy performs better than the high-sensitivity one and the points below are the positions for wich the hardened redundancy is worse. Fig. 6: Double fault sucess rates (hardened vs. high-sensitivity)

Figure 7 is the same graph but shows the detection rate instead. In this case, a higher rate is desired as it represents the ability to detect an unsuccessful attack. These two graphs show that there are actually a few points for which the hardened redundancy performs worse than the high-sensitivity redundancy by a small margin, which was not evident by looking at the results so far. Still the overall results are largely in favor of the hardened redundancy.

V. CONCLUSION This paper started by providing an evaluation of the effects of FBB on the sensitivity of a register to laser fault injection showing that FBB and a lower V dd value increased the sensitivity of the register. Based on these results a method using sensitivity variations to decrease fault repeatability by using variable V dd /FBB configurations was proposed, implemented and tested. The obtained results showed that the method was effective both at decreasing double-fault injection rate as well as increasing attack detection rate.

All in all, these results show that low-power technologies can induce security risks if not carefully accounted for. But when planned for they can be used to enhance security.

We insist on the fact that temporal redundancy is only one application that we used as a proof of concept. However, this is something that is easily implemented on circuits that already FBB capabilities available and further increases the complexity of the attacker's work. Other applications of the method will be evaluated in the future.

Further works will also include evaluating the use of Reverse Body Biasing in order to increase the sensitivity range, as well as investigating the physical phenomenons and trying to understand the cases where faults appear in low sensitivity mode and not in high sensitivity mode.

Fig. 1 :

 1 Fig. 1: Cross-sectional view of CMOS Triple-Well process

Fig. 2 :

 2 Fig. 2: Total faults per map for each tested power configuration

Fig. 3 :

 3 Fig. 3: Faults for different laser power values IV. EXPLOITING SENSITIVITY VARIATIONS

Fig. 4 :

 4 Fig. 4: Laser power fault thresholds variations

Fig. 5 :

 5 Fig. 5: Testing Procedure

Fig. 7 :

 7 Fig. 7: Detection rates (hardened vs. high-sensitivity)

TABLE I :

 I Laser power fault injection threshold C. Conclusion

TABLE II :

 II Occurrence rate of the different cases Table