Yi Ren
email: yi.ren@labri.frdomaine

Aurélie Bugeau
email: aurelie.bugeau@labri.frdomaine

Jenny Benois-Pineau
email: jenny.benois-pineau@labri.frdomaine

Bag-of-Bags of Words Irregular graph pyramids vs spatial pyramid matching for image retrieval

Keywords: Content-based image retrieval, graph partitioning, Normalized Cuts, Bag of words

Papier soumis dans le

Introduction

Recent methods in Content-Based Image Retrieval (CBIR) mostly rely on the bag-of-visual-words (BoW) model [START_REF] Sivic | Video google : a text retrieval approach to object matching in videos[END_REF]. The idea, borrowed from document processing, is to build a visual codebook from all the feature points in a training image dataset. Each image is then represented by a signature, which is a histogram of quantized visual featureswords from the codebook. Image features are thus considered as independent and orderless. The traditional BoW model does not embed spatial layout of local features in image signature. However, this information has shown to be very useful in tasks like image retrieval, image classification, and video indexing. Ren et al. [START_REF] Ren | Learning a classification model for segmentation[END_REF] put forward a concept of grouping pixels into "superpixels". Leibe et al. proposed to adopt codebooks to vote for object position [START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF]. Lazebnik et al. [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF] partitioned an image into increasingly fine grids and computed histograms for each grid cell. The resulting spatial pyramid matching method (SPM) clearly improves the BoW representation. Nevertheless, this method relies on the assumption that a similar part of a scene generally appears at the same position across different images, which does not always hold. Graphs are versatile tools to conveniently represent patterns in computer vision applications and they have been vastly investigated. By representing images with graphs, measuring the similarities between images becomes equivalent to finding similar patterns inside series of attributed (sub)graphs representing them. Duchenne et al. [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF] introduced an approximate algorithm based on graph-matching kernel for category-level image classification. Gibert et al. [START_REF] Gibert | Graph embedding in vector spaces by node attribute statistics[END_REF] proposed to apply graph embedding in vector spaces by node attribute statistics for classification. Bunke et al. [START_REF] Bunke | Towards the unification of structural and statistical pattern recognition[END_REF] provided an overview of the structural and statistical pattern recognition, and elaborated some of these attempts, such as graph clustering, graph kernels and embedding etc., towards the unification of these two approaches. This paper presents a new approach for Content-Based Image Retrieval (CBIR) that extends the bag-of-words (BoW) model. We aim at embedding color homogeneity and limited spatial information through irregular partitioning of an image into a set of predefined number of graphs. Each partition results from applying graph partitioning methods to an initial full connected graph, in which nodes are positioned on a dense regular grid of pixels. We adopt the graph segmentation method called Normalized Cuts [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. The BoW approach is then applied to each of resulting subgraph independently. An image is finally represented by a set of graph signatures (BoWs), leading to our new representation called bag-of-bags of words (BBoW). As in the spatial pyramid matching approach [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF], we also consider a pyramidal representation of images with a different number of (sub)graphs at each level of the pyramid. The comparison of images in a CBIR paradigm is achieved via comparison of the irregular pyramidal partitions. We call this pyramidal approach Irregular Pyramid Matching (IPM). Hence in this paper, we try to address a challenging question : will an irregular segmentation-like partition of images outperform a regular partition (SPM) ? Intuitively, it is invariant to the rotation and reasonable shift transformations of image plane. Nevertheless, what can be its resistance to noise and occlusions ? How will it compete with SPM when embedded into pyramidal paradigm ?

The remainder of the paper is organized as follows. In section 2 we briefly introduce the notations and prerequisites. The proposed bag-of-bags of words model is discussed in section 3 and the irregular pyramid matching in section 4. Section 5 presents the experimental results and we conclude in section 6.

Terminology

The input database Ω = (I, V ) is composed of N RGB images I = {I 1 , . . . , I N } and of a visual codebook V = {V 1 , . . . , V B } of size B. The codebook is a collection of vector quantized features created by k-means clustering over local SIFT [START_REF] Lowe | Distinctive image features from scaleinvariant keypoints[END_REF] features. The latter are extracted from all the grid dense sampling points of the images in a randomly selected training sample. Let us denote by G j = (V j , E j , W j ) an undirected weighted graph constructed on the image I j . The set V of vertices contains a regularly sampled subset of pixels P of the image and at the limit can contain all of them. The graph edges E connect these vertices with a 8-connected neighbourhood system. The af-finity matrix W of size |V| × |V| is defined as :

Wpq = wpq if p, q ∈ E 0 if p, q ∈ E,
where w pq represents the edge-based similarity between two vertices p and q. For each image I j in the database, we aim to partition the graph G j into fixed K disjoint unconnected subgraphs {g j,1 , . . . , g j,K }, such that ∀k = l, g j,k ∩ g j,l = ∅ and Gj = { K k=1 g j,k } ∪ Ej, where E j ⊂ E j are removed edges to divide G j by graph cuttings. We denote this K-way partitioning by Γj,K = {gj,1, . . . , gj,K }. Graph partitioning is a labeling problem. Given a set of vertices V and a set of labels L = {1, 2, . . . , K}, for all node p ∈ V, we are looking for the optimal label l p ∈ L, such that the joint labeling L = {l 1 , . . . , l |V| } ∈ L |V| satisfies a specified objective function.

Bag-of-Bags of Words Model

Our BBoW model has been inspired by the bag-of-words model [START_REF] Sivic | Video google : a text retrieval approach to object matching in videos[END_REF] for image description and the idea that an irregular partition into a fixed number of graphs is a step inbetween an arbitrary regular partition as in [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF], and a segmentation of an image plane which can be redundant. The imperfections of this intermediate partition should be compensated by a statistical nature of the original BoW model for each graph in the partition. Furthermore, we embed BBoW into multi-resolution schemes as spatial pyramid matching [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF] for using image partitions in coarse to fine manner. For each image, the construction of a bag-of-bags of words (figure 1) can be decomposed into four steps :

1) Select a reduced number of pixels V.

2) Build an initial graph G.

3) Partition the graph G into K subgraphs.

4)

Compute a signature for each subgraph.

The signature of a subgraph is a histogram of codeword occurrences, i.e. obtained by assigning each feature node of this subgraph to the closest visual word in the codebook. Hence, an image being composed of K subgraphs is characterized by a set of K histograms. In the following, we detail each step of the method.

Graph nodes selection

We adopt a dense sampling strategy. All the areas contribute equally to the final image representation. We choose 8pixels spacing and 16-pixels patch size for the SIFT [START_REF] Lowe | Distinctive image features from scaleinvariant keypoints[END_REF] features, called Bag-of-Features Grid SIFT (BF-GSIFT) [START_REF] Tuytelaars | Dense interest points[END_REF].

Construct initial weighted graph

The set of nodes V of our initial graph G contains all the points resulting from the dense sampling. The edges E are obtained by linking these points with a 8-connected neighbourhood system. The weights on the edges are :

wpq = exp -λ Cp -Cq Σ -1 Cp -Cq T , (1)
where Cp accounts for the mean color vector over a n × n patch centred on point p = (x, y). λ is a parameter to differentiate color similarity. We use the YUV color space because it has independent color channels and allows to better deal with changes in lightning conditions. We denote Y p = Y (x, y) (respectively U p = U (x, y) and V p = V (x, y)) as the color channel value at point p. The mean color vector becomes Cp = ( Ȳp, Ūp, Vp) where :

Ȳp = 1 n 2 n u=-n n v=-n Y (x + u, y + v).
The covariance matrix

Σ = diag[σ 2 Y , σ 2 U , σ 2
V ] is diagonal because of channels' independence. As in [START_REF] Rother | Grabcut : Interactive foreground extraction using iterated graph cuts[END_REF], the channel covariance σ 2 Y , σ 2 U , σ 2 V are computed over all the edges (p, q) ∈ E of the graph G.

Graph Partitioning with NCuts

We now present how the initial connected full graph G is partitioned into K subgraphs. Let us denote links(A, B) to be the sum of the edge weights between nodes in two disjoint graph nodes' sets A and B :

links(A, B) = i∈A,j∈B wij.
Shi et al. introduced the Normalized Cuts (NCuts) [START_REF] Shi | Normalized cuts and image segmentation[END_REF], a graph-theoretic criterion for measuring the goodness of partitions. The algorithm optimizes two criteria, measuring the total dissimilarity between the different subgraphs

W N cuts(Gj) = min g j,1 , ..., g j,K K k=1 links(g j,k , Vj \ g j,k ) w(g j,k ) , (2)
as well as the similarity within each subgraph

W N assoc(Gj) = max g j,1 , ..., g j,K K k=1 links(g j,k , g j,k ) w(g j,k ) . ( 3
)
where w(g j,k ) is the sum of edge weights in the subgraph g j,k . K is the number of subgraphs.

The principle is to find a minimal cut which is a combination of edges having minimal sum of edge values (i.e. find the least alike pairs of nodes). Removing these edges divides the graph G into unconnected subgraphs, such that the similarity between nodes within a subgraph is greater than the similarity between nodes in separated subgraphs. The advantage of the normalized cut method is that it considers two aspects of graph segmentation : minimal cut (i.e. better separation) and preferring segments of large size. In practice, we used the code from [START_REF] Shi | Normalized cuts and image segmentation[END_REF][START_REF] Cour | Normalized cut segmentation code[END_REF] to directly apply NCuts to partition a weighted graph G.

Signatures of subgraphs and BBoW

As in the standard BoW approach, we first build a codebook from all dense features in a training image dataset. The codebook is thus independent from any partitioning scheme. Let us denote H j,k , a signature of the subgraph g j,k , k = 1 . . . K in image I j . H j,k is a Bag of Words (BoW) histogram, obtained by assigning the SIFT features of all graph nodes within the subgraph to the nearest codeword (hard assignment). Hence, the signature of an image I j will be a histogram vector Hj = {Hj,1, . . . , Hj,K } of length K, normalized by the number of nodes in the initial image graph G j . With such a normalization, the larger subgraphs are privileged. We call H j "Bag-of-Bags of Words" (BBoW).

Irregular Pyramid Matching

Our model directly follows the strategy from Spatial Pyramid Matching [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF]. We consider several "resolutions" (r = 0 . . . R) of a partition pyramid. At each resolution r, the image graph G j is split into Kr = 2 2r subgraphs. Hence, the BBoW representation of image I j at resolution r is the vector H r j = {H r j,1 , . . . , H r j,Kr } of length K r . An example of subgraphs and BBoWs is given in figure 2. In order to compare two images I i and I j , we need to compare the histogram signatures of their subgraphs, and build a similarity measure upon them. For this purpose, we can use the histogram intersection function [START_REF] Jou | Efficient matching of large-size histograms[END_REF] :

I H r i,k , H r j,k = B b=1 min H r i,k (b), H r j,k (b) , (4)
where B is the codebook size.

In our method we cannot directly apply this function to match histograms of the subgraphs in the partition. At the end of the partitions steps, for two images, the two histograms H r i,k and H r j,k may not correspond one to the other. Indeed, after applying a graph partitioning method, the subgraph attributed to label k can be at any position in the image. The spatial arrangement is lost if an image in a database undergoes rotation, for instance. To overcome this issue, we first need to reorganize our histograms in BBoW to find an optimal matching of one partition to the other. We thus reorganize the labels between the two sets of histograms {H r i,k } k=1,...,Kr and {H r j,k } k=1,...,Kr . We call this step bipartite subgraphs matching. We are facing an assignment problem which requires the use of combinatorial algorithm. In our method, we rely on the Hungarian algorithm to minimize the discrete transport cost between the two sets of histograms. The cost matrix D r i,j between the pair of images Ii and Ij at level r reads :

D r i,j =    d 11 i,j . . . d 1Kr i,j
. . .

d Kr 1 i,j . . . d Kr Kr i,j    . (5)
where

d k,l i,j = B b=1 |H r i,k (b) -H r j,l (b)| is the L 1 distance bet- ween H r i,k and H r j,l
, which is equivalent to the histogram intersection kernel. The Hungarian algorithm finds the minimum cost assignment by associating each label k of subgraph g i,k in image Ii to one label k ′ = fi(k, r) of subgraph g j,k ′ in image Ij, thus the pairs of histograms to compare are identified. Now that bipartite subgraphs matching has been fulfilled, we can directly apply the level weighted intersection [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF] :

κ(Ii, Ij) = I H R i,k , H R j,k ′ + R-1 r=0 1 2 R-r I r -I r+1 = 1 2 R I H 0 i,1 , H 0 j,1 + R r=1 1 2 R-r+1 I H r i,k , H r j,k ′ .
The weight1 2 R-r allows for penalizing low resolutions of a partition, reflecting the fact that higher levels localize the features inside smaller graphs more precisely.

Experimental evaluation of IPM

In this section, we present the experimental evaluation on Caltech101 benchmark [START_REF] Fei-Fei | Learning generative visual models from few training examples : an incremental bayesian approach tested on 101 object categories[END_REF]. The Caltech101 dataset includes 101 objects categories such as faces, watches, ants, pianos, etc... and a background category for a total of 102 categories. Following the same setting as in [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF], we use the dense grid of points generated from their codes to build initial full connected graphs. The dictionary of size 400 is learnt over 30 sample images per class using k-means and query images are chosen from the rest of the dataset for retrieval.

Selection and impact of parameters

We first estimate the impact of the different parameters on image retrieval performance. Two parameters have been evaluated : the patch size n defined in section 3.2 and the parameter λ for the edges weight (equation 1). The mean Average Precisions (mAP) on Caltech101 are presented in tables 1 and 2. For efficiency, these experiments were conducted on smaller databases containing only 4 test images per category. The results highlight that these two parameters do not remarkably influence the quality of retrieval. Therefore, we decide to select n = 5 and λ = 5 for the following experiments. mAP for the IMP approach at 3 levels pyramid λ = 0 λ = 5 λ = 20 λ = 100 IPM 0.386 0.390 0.386 0.381

Image retrieval evaluation

The performance of our proposed IPM algorithm is measured by the mean Average Precision (mAP) and its standard deviation for each category and on the whole dataset, as described in TREC-style evaluation 1 . Table 3 presents this global mAP for Caltech101 at each level of the pyramid. We compare ours with SPM [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF] and with the bag-ofwords approach which simply corresponds to the results at level 0. SPM outperforms BBoW in general, but our method achieves better results than BoW (level 0) overall. By looking closer to the global mAPs, we can nevertheless observe that the pyramidal approach is not needed for SPM on this dataset. Indeed, the results at single level 2 are better than the ones with the pyramidal approach. These results have been obtained with the official codes of SPM. On the contrary, the pyramidal approach is a good strategy in our case, as it improves the retrieval performance with increasing levels. We then propose to investigate more details for fifteen typical categories of Caltech-101 dataset (figure 3), for which the mAP of IMP is contrast to that of SPM. There are seven categories in which SPM has notable better retrieval performance. These also explain why SPM is globally better than IPM on whole database. Nevertheless BBoW achieves comparative results with SPM for most of categories, and even outperforms it in eight categories.

Statistical (sub)graph analysis

In order to give a deeper understanding on why our method suits for certain categories and not for the others, let us go through three case studies : a "good" category (minaret), and two "bad" ones (cellphone, dollar_bill). Figures 4 and5 present our partitioning results at level 1, i.e. 4 subgraphs. Figure 4 illustrates good queries from minaret class in which BBoW outperforms SPM. As can be seen, our method is able to represent the minaret (object) with only one or two subgraph(s). The other subgraphs in the background are also stable in the sense that almost the same subgraphs can be found in each high-ranking retrieved image within minaret category. Figure 5 shows four bad queries from cellphone and dollar_bill categories in which SPM achieves better performance than our method. The obtained partitions almost do not exhibit any consistency across the images from the same category. The resulting histograms are therefore each time very different and we can obviously not expect any good retrieval. We now detail the retrieval performance and the statistics of the (sub)graphs for these eight query images. One can see in figure 6 that in "good" categories, our method outperforms SPM [START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF]. In this case, the partitions from NCuts are stable across the images of the same category. The mean number of nodes in "correctly" matched subgraphs together with the standard deviation are presented in figure 7. The standard deviation is high for "bad" categories, whereas it is more uniform for "good" category. In order to qualify performance of our approach, we also introduce a new measure. We call it Partition Precision (PP). For particular query image I j , we denote N rel as the number of relevant images rel for this query in the whole database Ω. If I j and I i are from the same category, then I i ∈ rel. We say g j,k , g i,k ′ are matched, if they are bipartite matching subgraphs after rearrangement of histograms via Hungarian algorithm, moreover they fall into same regions (background, sky, object etc.) of the image I j and I i respectively. Then we can define an N rel × K matrix M :

M d,k = 1 g j,k , g i,k ′ are matched, 0 Otherwise.
to describe the stability of partitioning G j into Γj,K = {gj,1, . . . , gj,K }. The Partition Precision (PP) for query image I j is thus given by a row vector of length K :

{P (g j,k )} k=1,...,K = 1 |N rel | d=1...|N rel | M d,k
where M d,k is an element of matrix M . The above vector thus characterizes the goodness of match of each subgraph in a query image to the subgraphs of images of the same category in the database Ω. Table 4 and 5 show figures for the partition precision of 4 typical queries of a "good" category and of two "bad" categories. One can see that in the "good" categories, the worst matching percentage (in bold) is better than that in "bad" queries. Hence, this correlates with better stability of nodes' numbers, as in figure 7.

Query image

Conclusion and perspectives

In this paper, the bag-of-bags of words model over irregular image partition via Normalized Cuts and its pyramidal extension, the irregular pyramid matching (IPM) have been introduced. Normalized Cuts method is used to separate the graph of an image, which is composed of full connected dense grid-points, into several subgraphs. Each subgraph is then described by a bag-of-words model. Our approach incorporates color and limited spatial information into image representation for image retrieval. The obtained results are encouraging, especially when the partitions obtained are stable across the images from the same category. A criterion for measuring the stability of subgraphs has been defined in the experimental section. The stability is nevertheless not always insured with the aforementioned graph weights functions. In the future, we consider embedding more image descriptors in graph weights and bipartite subgraphs matching process in order to reach more stability.

FIGURE 1 -

 1 FIGURE 1 -Bag-of-bags of words pipeline

FIGURE 2 -

 2 FIGURE 2 -A schematic illustration of the BBoW representation at each level of the pyramid. At level 0, the decomposition has a single graph, and the representation is equivalent to the classical BoW. At level 1, the image is subdivided into four subgraphs, leading four features histograms, and so on. Each subgraph is represented by its own color.

FIGURE 3 -

 3 FIGURE 3 -mAP at 3 levels pyramid for 15 typical categories in Caltech101. SPM outperforms IPM considerably in 7 categories.

FIGURE 4 -

 4 FIGURE 4 -The 4 irregular subgraphs (in red, blue, green, brown colors) from "good" query images at level 1.

FIGURE 5 -

 5 FIGURE 5 -The 4 irregular subgraphs (in red, blue, green, brown colors) from "bad" query images at level 1.

FIGURE 6 -

 6 FIGURE 6 -The precision of 8 typical query images : 1st-4th query images are from a "good" categoryminaret, 5th-8th query images are from "bad" categories : cellphone and dol-lar_bill.

FIGURE 7 -

 7 FIGURE 7 -The mean and standard deviation of nodes' numbers of corresponding subgraphs for intra-category, for 8 typical queries in Caltech-101 dataset -at single level 1, i.e. 4 subgraphs.

TABLE 1 -

 1 Influence of parameter λ (equation 1) on image retrieval. For each value, the mean average precision is given. For this experiment, mAP(SPM)=0.409, the patch size is set to n = 5.

		mAP for the IMP approach at 3 levels pyramid
		n = 3	n = 5	n = 7	n = 9
	IPM	0.381	0.389	0.389	0.388

TABLE 2 -

 2 Influence of parameter n (section 3.2) on image retrieval. For each value, the mean average precision is given. For this experiment, mAP(SPM)=0.409, λ = 5.

TABLE 3 -

 3 Retrieval performance (mAP and its standard deviation) on the whole Caltech-101 dataset.

TABLE 4 -

 4 The {P (g j,k )} k=1,...,4 of corresponding subgraphs for 4 typical "good" queries.

	Ij	gj,1	gj,2	gj,3	gj,4
	minaret0036	0.773 0.746 0.626	0.6
	minaret0037	0.786	0.72	0.626	0.6
	minaret0069	0.773	0.44	0.6	0.613
	minaret0071	0.8	0.506	0.6	0.413
	Query image Ij	gj,1	gj,2	gj,3	gj,4
	cellphone0034	0.724 0.638 0.569 0.241
	cellphone0045	0.724 0.362 0.569 0.552
	dollar_bill0035 0.431 0.686 0.392 0.176
	dollar_bill0039 0.275 0.824	0.06	0.418

TABLE 5 -

 5 The {P (g j,k )} k=1,...,4 of corresponding subgraphs for 4 typical "bad" queries.

http ://trec.nist.gov/

Acknowledgment

This research is supported by CNRS (Centre national de la recherche scientifique) & Region of Aquitaine Grant.