Thomas Hurtut

Haroldo Dalazoana

Yann Gousseau

Francis Schmitt

Spatial color image retrieval without segmentation using thumbnails and the Earth Mover's Distance

We introduce a spatial color image retrieval method which does not include any segmentation step. This method relies on small image thumbnails and the Earth Mover's Distance (EMD). We then derive an unsupervised matching criterion using an a contrario approach. Experiments are performed on a database of illuminated manuscripts.

Introduction

Color image retrieval methods that do not take into account any spatial layout miss important cues of human visual perception. Hence spatial color indexing retrieval has become a very active research area. Some approaches augment histograms with pixel localization or spatial color correlation, see e.g. [START_REF] Lambert | Image retrieval using spatial chromatic histograms[END_REF][START_REF] Ciocca | Image indexing and retrieval using spatial chromatic histograms and signatures[END_REF][START_REF] Huang | Image indexing using color correlograms[END_REF][START_REF] Pass | Comparing images using color coherence vectors[END_REF]. Other methods use points of interest in the image to include spatial features [START_REF] Grauman | Efficient image matching with distributions of local invariant features[END_REF][START_REF] Heidemann | Combining spatial and colour information for content based image retrieval[END_REF]. Region-based approaches first perform a segmentation of images which is then used for image comparison. The Blobworld image representation, for instance, uses multidimensional Gaussian mixtures as the image model [START_REF] Carson | Blobworld: image segmentation using EM and its application to image querying[END_REF]. Many other unsupervised segmentation methods have been used to index images, see e.g. [START_REF] Liu | Region-based image retrieval with high-level semantic color names[END_REF][START_REF] Rugna | Color coarse segmentation and regions selection for similar images retrieval[END_REF][START_REF] Prasad | Region-based image retrieval using intergrated color, shape, and location index[END_REF]. A matching step follows the segmentation and indexing steps, generally relying on a distance or a similarity measure. One of the most efficient distance to compare sets of features is the Earth Mover's Distance (EMD) [START_REF] Rubner | The earth mover's distance as a metric for image retrieval[END_REF], see e.g. [START_REF] Dvir | Context-Based image modelling[END_REF][START_REF] Liu | Region-based image retrieval with high-level semantic color names[END_REF].

We propose a retrieval method that rely on the spatial organization of colors. The plan of the paper as follows. We first define the features used to represent the spatial and color contents of images. We then introduce a distance derived from optimal transportation problems, the Earth Mover's Distance, and discuss its use for the comparison of images signatures. Next we derive an automatic criterion, enabling to decide whether two images should be matched or not, using an a contrario approach. We conclude with numerical experiments on a database of illuminated manuscripts.

Features

The proposed method uses coarsely sampled thumbnails to represent images (Fig. 1). The total number of pixels of these thumbnails is fixed to n, depending on the database content and on computing constraints. Image subsampling is achieved by averaging the image pixels. We choose the psychometric CIELab color space to represent thumbnails, in order to use the Euclidean distance to compare their color components. The signature for an image is composed of the n thumbnail pixel features

f i = {L i , a i , b i , X i ,Y i },

Distance

To measure the distance between two pixel features f i Q and f j T of a query image Q and a target image T respectively, a weighted exponential distance is used:

d e ( f i Q , f j T ) = α *   1 -e - (L i Q -L j T ) 2 +(a i Q -a j T ) 2 +(b i Q -b j T ) 2 δ 2 c    (1)
+(1 -α) *   1 -e - (X i Q -X j T ) 2 +(Y i Q -Y j T ) 2 δ 2 s    .
The parameter α balances color and spatial contributions. This weighted exponential distance supports the idea that beyond a certain distance, two different images are just considered as not similar. Parameters δ c and δ s are chosen according to the color and spatial dynamics. Typical values that will be used in this paper, are δ c = 15 and δ s a quarter of the thumbnails diagonal. This nonlinear distance is adapted to an image retrieval task, where a target image is close to a query, in which case the similarity is measured, or is simply different and penalized.

We then use EMD [START_REF] Rubner | The earth mover's distance as a metric for image retrieval[END_REF] to measure the distance between the signature of a query image and the signature of a target image. EMD is defined as the minimum amount of work needed to map one signature onto the other. The notion of work is defined as the product of the ground distance d e and the feature weight. In our approach, each feature is given the same weight (since thumbnail pixels correspond to a fixed area in the original image). It may then be shown that each pixel of the query image is assigned to exactly one pixel of the target image, see Figure 2. In this particular case, the EMD distance between two images Q and T is equal to

d(Q, T ) = min φ n ∑ i=1 d e f φ (i) Q , f i T , ( 2
)
where φ belongs to the set of permutations of {1, . . . , n}. Computation of the EMD is therefore simplified and can be achieved by solving an optimal assignment problem. This problem is solved by the Hungarian method, also called the Kuhn-Munkres algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF], in O(n 3 ).

In contrast, when using EMD with region based methods, each region is usually weighted according to its area. In this case, EMD breaks apart the weights of the features when optimizing the cost of the mapping. Therefore, the usefulness of a segmentation step before EMD is questionable since pixels that have been grouped into regions can be mapped separately to different target regions by EMD. Indeed no constraints are included in EMD that take into account the fact that regions represent pixels groups. Besides, segmentation methods require complex tunings of the parameters. Furthermore, undersegmentation can yield regions that are not well represented by, e.g., their mean color, affecting the performances of the matching step. Our approach is simpler, more robust and takes full advantage of EMD : we somehow oversegment the image into small and regularly spaced regions, and then let the EMD distance resolve the matching problem. The number of regions that are considered is only limited by computation constraints.

Unsupervised matching criterion using an a contrario approach.

In this section, we present a method to answer the question of whether two color images should be matched or not. Our approach is similar to the one in [START_REF] Gousseau | Comparaison de la composition de deux images, et application la recherche automatique[END_REF][START_REF] Musé | An a contrario decision method for shape element recognition[END_REF] : we will match two images as soon as their proximity is unlikely to be due to chance. This is an application of the general principle of a contrario methods: we do perceive events that are unlikely in a white noise situation. Such methods have been successfully applied to several tasks in computer vision following the work of [START_REF] Desolneux | Meaningful alignments[END_REF], see [START_REF] Desolneux | Gestalt Theory and Image Analysis : A Probabilistic Approach[END_REF]. We now detail how this principle is used in the framework of the comparison of images.

Our setting is as follows. We write Q for a color query image, and B = {T 1 , . . . , T m } for a database composed of m color images. For two images Q and T , their EMD distance (as detailed in the previous section) is denoted as d(Q, T ). For each image T i , we want to develop a statistical test for the hypothesis H 1 = {T i is similar to Q} and we choose to rely on the quantity d(Q, T i ). A usual approach to this problem would be to have a probabilistic model for the images that are similar to the query and, for example, to perform a Bayesian test. This implies the development of specific models for each category of color images that we deal with. An a contrario approach to this test consists in relying on a background model M of generic images, and then to fix the number of false alarms when testing H 1 against H 0 = {T i follows the background model }. The general idea is that if an image has been generated by the model M , then it should not be paired with Q. Assume that we are able to compute the probability Pr H 0 (d(Q, T ) ≤ C), for any C ≥ 0. We will then say that

T i is an ε-meaningful match of Q if d(Q, T i ) ≤ C B , where C B is such that Pr(d(Q, T ) ≤ C B ) ≤ εm -1
, and where T is distributed according to M . It can be shown that if all images T i from the database B follow the model M , then the expectation of the number of ε-meaningful matches is less than ε (the proof of this fact relies on the linearity of the expectation, see [START_REF] Musé | An a contrario decision method for shape element recognition[END_REF]). In practice, we will always choose ε = 1, that is we will fix the expected number of false matches to one. In what follows, we use the term meaningful match instead of 1-meaningful match.

Of course, for this to be feasible, we need to choose a background model M . Since the distance d only take thumbnails into account, we seek a background model for thumbnails. The first model we tried was a uniform white noise model, in which all pixels of a thumbnail are drawn independently and uniformly in the Lab space. This was not satisfactory, since too many images were then meaningful matches of the query. Our interpretation of this fact is that, even when they are perceptually different, images share some common structure (e.g. the presence of homogeneous regions). Similar results were obtained with a model in which thumbnails are white noise with color marginal learned on the database B. We therefore need a more structured model, with geometric features similar to the ones encountered in real images, such as homogeneous regions and edges. The model we consider is a dead leaves model ( [START_REF] Matheron | Modèle séquentiel de partition aléatoire[END_REF]), consisting in the superimposition of random objects, together with a power law distribution for the size of objects. This model has been experimentally proved to be well adapted to the structure of natural images, [START_REF] Alvarez | The size of objects in natural and artificial images[END_REF][START_REF] Lee | Occlusion models for natural images: A statistical study of a scale invariant dead leaves model[END_REF]. For the sake of simplicity, we restrict ourselves to a model where objects are simply disks. The radius of these disks are random variable with density f (r) ∝ r -γ . The model is then characterized by three parameters : the scaling parameter γ, an dr 0 , r 1 the minimal and maximal sizes of objects 1 . We chose γ = 3, a typical value for natural images, r 0 = 1 and r 1 of the same magnitude as the dimensions of thumbnails. The distribution of the color of objects is learned from the color distribution of pixels from thumbnails of the database. Samples of the model (using color marginals from the database of illuminated manuscripts used in the experimental section) are displayed in Figure 3. The last point, in order to be able to compute meaningful matches of a given query image, is to compute the constant C B such that Pr(d(Q, T ) ≤ C B ) ≤ ε/m where T follows M . Since this quantity would be very tricky to compute exactly, we rely on numerical simulations. That is, we sample r realizations F j of the model and then approximate C B by the empirical quantile of order m -1 ε of {d(Q, F j )} j=1,...,r . The choice of r will be addressed in the experimental section.

Let us stress that an advantage of this approach to the matching problem is that the threshold automatically adapts to both the query and the database. In particular, the threshold is expected to get more conservative as the database gets larger, which can be crucial when dealing with very large databases. Also observe that the threshold is driven by parameter ε, which has the intuitive meaning of a number of false detections when submitting a query and is therefore easier to choose than a bound on distances. In all experiments to be performed in this paper, we choose ε = 1.

Experimental evaluation

Tests have been performed on an illuminated manuscript database provided by the Institut de Recherche et d'Histoire des Textes (IRHT) 2 . This database contains 1500 high quality and color-calibrated illuminations. Experiments use n = 150 (10×15 or 15×10 thumbnails). Tests are performed using a query image. We then compute the distances between the query thumbnail and all the thumbnails in the database and return the nearest matches. Except where mentioned, all tests are performed using α = 0.5, δ c = 15 and δ s = 5. Distances between the query thumbnail and the background model are also computed in order to estimate the matching criterion. The parameters of the background model we use are γ = 3, r 0 = 1 and r 1 = 30. A point that is rarely discussed and that concerns all spatial color methods is how to manage different image ratios. Various choices are available to handle this problem. In the experiments, we chose to treat separately portrait and landscape orientations. However EMD has no constraints on signature length and total weight, and therefore we could also compare images with different ratios. A query on a PC Pentium IV 4.3 gHz has a runtime of approximately 10 seconds. More results are visible on website [START_REF] Hurtut | More results web page[END_REF].

Distance

We use EMD to measure the distance between signatures of images. The weighting parameter α ∈ [0, 1] used in the distance between two features (see Eq. 1) allow us to support either spatial or color constraint. If the user wish to be severe on spatial organization (pixels cannot move freely on the image), α must be set to a low value. The higher the value, the more objects can move and be split apart. The extreme case where α = 1 is equivalent to a color histogram method, with EMD similarity measure. Two results are displayed on Fig. 4, using different α values.

Comparison with blobworld + EMD

Newt we compared our method with a region-based method using EMD for the matching step. We chose Blobworld segmentation 3 [START_REF] Carson | Blobworld: image segmentation using EM and its application to image querying[END_REF] that represents regions as Gaussian mixtures. The original method uses texture and location to extract blobs. We only use color and location information to be directly comparable with our method. Nevertheless we observe similar retrieval results on the illuminations database when also using texture. Blobs tend to represent objects in the image. Hence the number of blobs to find in an image is an important parameter. This parameter is set by an MDL method (see [START_REF] Carson | Blobworld: image segmentation using EM and its application to image querying[END_REF] for details). For the sake of coherence, we also use EMD to measure the distance between two blob signatures. In this case, the weight of each blob is chosen as its area and EMD breaks apart the weights of the features when optimizing the cost of the mapping.

Two comparative results are displayed on Figure 5 and Figure 6. Among all our tests, the blobs+EMD method performs well on queries where simple objects stand on a homogeneous background. In this case our method will perform similarly because, as mentioned earlier, blobs will be split apart by EMD. Such an situation is displayed on Fig. 5. On the other hand, we observed that our method perform better on images where segmentation methods generally fail, i.e. quite complex and heterogeneous images. Indeed, wrong segmentation yield regions that are not well represented, highly affecting the performances of the matching step. Figure 6 illustrates this drawback.

Statistical framework

We analyze in this section the robustness of the proposed unsupervised matching criterion. We then present more image retrieval results using this criterion. Recall that C B the threshold on distances enabling to define meaningful matches, is estimated thanks to samples of the background model. In order to investigate the effect of the number of samples that are generated, we performed the following experiment. Background databases of m × N bg realizations of the background model M (m being the number of images in the database B) are synthesized, for N bg = 1, . . . , 9. Then, for a query image I Q , we count how many images from B are meaningful matches of I Q . Figure 7 shows the standard deviation of this number of meaningful images as a function of N bg , when considering ten background databases for each N bg . This experiment suggests that, despite the high variability of realizations of the dead leaves model, N bg = 3 is enough to obtain consistent results with different background databases, and is therefore the numerical value retained in this paper.

Retrieval results are displayed on Fig. 8 to Fig. 13. For each query we display the nearest target images and indicate the automatic threshold by a grey thumbnail. Let us stress that the threshold value can greatly vary from one query to the other. The number of returned results vary from 0 (second result of Figure 12) to 23 (Figure 10) according to the query and the content of the database. The criterion is not perfect: it sometimes stops beyond For each N bg , ten background databases have been generated in order to estimate the standard deviation.

or before where a human would exactly stops the list of results. It also moderately depends on the background model occurrence, see Fig. 7. But results are relevant most of the time. The criterion is a good indication of where the results should stop, and also inform the user on the quantity of relevant images present in the database. Here, we use a small database, and results seldom exceed a hundred, but this type of information can be crucial with much bigger databases.

Conclusion and future work

We propose a spatial color image retrieval method without initial segmentation, based on thumbnails and EMD. Its main interest is its robustness and its ability to fully use the EMD efficiency compared to region-based approaches. Experimental comparisons with a classic spatial color method is promising and confirm that complex segmentation methods are not necessary at best, misleading at worst. Future work will use more elaborated features for each thumbnail pixel including local vector quantization and texture characteristics. One drawback of our method is that EMD computing cost is high, and that querying can be slow for large databases. A possible solution could be to adapt a recent EMD approximation proposed in [START_REF] Indyk | Fast image retrieval via embeddings[END_REF] which claims a two order magnitude speedup. This would allow for fast retrieval in databases having several hundreds thousands images.

We also propose an automatic matching criterion relying on a contrario. Future work will study the behavior of the threshold on much larger databases, and investigate in more details the way it adapts to the query and database specificities.

  where L, a, b are the color coordinates and X,Y the spatial positions.

Figure 1 .

 1 Figure 1. A coarsely sampled thumbnail. Left: source image (3200 × 2200 pixels). Right: the thumbnail (10 × 15 pixels).

Figure 2 .

 2 Figure 2. Two images (left) and the associated thumbnails (middle), made of n = 10 × 15 pixels. Each pixel of a thumbnail is associated to a feature in 5 dimensions (L, a, b, X,Y ). All of them have the same weight. In this context, EMD is equivalent to an assignment problem. Each pixel of the query image (top left) is assigned to exactly one pixel of the target image. To illustrate the EMD operation, the thumbnail on the right represents the optimal permutation of the query pixels to match the target. The query pixels of the red region are moved towards their location in the target image. The white column of paper is also correctly moved from right to left.

Figure 3 .

 3 Figure 3. Samples of the background model M using color marginals from the illuminated manuscript database used in the experimental section.

  2 IRHT, CNRS, 40 avenue d'Iena, 76116 Paris.3 Code available at URL: http://elib.cs.berkeley.edu/blobworld/ a) b)

Figure 4 .

 4 Figure 4. Color spatial weighting using parameter α. A query image (red framed on the left) is followed by its three nearest matches on first lines of figure a) and b), with α = 0.5. The same query is visible on the second line of figure a) et b) with α = 1 (no spatial constraint). This situation is equivalent to color histogram retrieval methods with EMD distance. We clearly see on these last examples that the color content remains constant, but the spatial organization is lost.

Figure 5 .

 5 Figure 5. Comparison between a blobs + EMD method, and our method. A query image (red framed) followed by its three nearest matches are shown on first lines of figure a) and b), according to each method. The blob representations and the thumbnails (10 × 15) of respective images are shown on the second line of figure a) and b) respectively. Here the blob segmentation is relatively satisfactory and our method performs similarly.

Figure 6 .

 6 Figure 6. Same layout as on Figure 5. Here the blob segmentation fails to give a satisfactory representation of the color spatial organization of each image. Images are clearly undersegmented, yielding large regions with average colors of different patterns, leading to unsatisfactory matching.

Figure 7 .

 7 Figure 7. Variability of the automatic threshold. Each colored line correspond to a different query image. The retrieval is made on a database of m images. The (empirical) standard deviation of the rank of the last meaningful match is shown for background databases of size m × N bg , for N bg = 1, . . . , 9.

Figure 8 .

 8 Figure 8. The query image is red framed on top left in figure a) and is followed in scanline order by the nearest retrieved images. Meaningful matches are displayed before the grey image which corresponds to the automatic criterion. Beyond this limit, the next five nearest retrieved images are shown. Except the second one, their content is clearly not relevant according to the query. The corresponding features (10 × 15 thumbnails) are shown on figure b). The last thumbnail (blue framed) is the background model thumbnail found and used as a criterion for this query. As the query, this background model thumbnail is quite homogeneous.

Figure 9 .

 9 Figure 9. The query image is red framed on top left and is followed in scanline order by the nearest retrieved images. As in Figure 8, meaningful matches are obtained before the grey image corresponding to the unsupervised criterion and lress relevant images beyond it (except image in line 3 first column).

Figure 10 .

 10 Figure10. Same layout as on Figure9. We see here that the automatic criterion allows very variable rank limit, according to the database content and the query. Spatial organization is also important here, and one could wonder if the database contains only 23 white illuminations with a blue rectangle. Actually, the database roughly contains a hundred of this kind of illumination. On others, the blue rectangle has a different size and/or is not at the same location as the query.

Figure 11 .

 11 Figure 11. Same layout as on Figure 9. Two examples where the unsupervised matching criterion provides very few results according to the database content and query. On the second example, it rightly gives no result. We see that the five closest results are not relevant according to the query.

Figure 12 .

 12 Figure 12. Same layout as on Figure 9.

Figure 13 .

 13 Figure 13. Same layout as on Figure 9.

One can get rid of r 0 by considering a limit model yielding the same small scale structure as natural images,[START_REF] Gousseau | Modeling occlusion and small scales behavior in natural images[END_REF], but this model is too involved for the modeling of coarse representations of images.

Acknowledgments

We thank Gilles Kagan from IRHT for providing us the IRHT database and for his helpful comments. We also thank Farida Cheriet for her suggestions. This work was supported by a CNRS ACI supervised by Anne-Marie Edde and Dominique Poirel from IRHT, and by a grant from the LIV4D laboratory.