Florent Perronnin

Yan Liu Is

A Similarity Measure Between Unordered Vector Sets with Application to Image Categorization

We present a novel approach to compute the similarity between two unordered variable-sized vector sets. To solve this problem, several authors have proposed to model each vector set with a Gaussian mixture model (GMM) and to compute a probabilistic measure of similarity between the GMMs. The main contribution of this paper is to model each vector set with a GMM adapted from a common "universal" GMM using the maximum a posteriori (MAP) criterion. The advantages of this approach are twofold. MAP provides a more accurate estimate of the GMM parameters compared to standard maximum likelihood estimation (MLE) in the challenging case where the cardinality of the vector set is small. Moreover, there is a correspondence between the Gaussians of two GMMs adapted from a common distribution and one can take advantage of this fact to compute efficiently the probabilistic similarity. This work is applied to the image categorization problem: images are modeled as bags of low-level features and classification is performed using a kernel classifier based on the proposed similarity measure. Experimental results on the PASCAL VOC 2006 and VOC 2007 databases show the excellent performance of our approach.

Introduction

There exist several pattern analysis problems where the objects of interest can be represented by unordered vector sets of variable cardinality. For instance, in computer vision, images are often represented as bags of low-level local feature vectors. Performing such tasks as retrieval or kernel-based learning on these representations requires the definition of a suitable measure of similarity. The application of interest in this work is the categorization of images.

While categorization systems based on the bag-of-features representation neglect the absolute or relative position of the feature vectors in the image, they have shown excellent performance on several benchmarks [START_REF] Everingham | The 2005 PASCAL visual object classes challenge[END_REF][START_REF] Everingham | The PASCAL visual object classes challenge 2006 results[END_REF][START_REF] Everingham | The PASCAL visual object classes challenge 2007 results[END_REF].

There are two broad classes of approaches to measure the similarity of vector sets: model-free approaches seek a direct measure of similarity while model-based approaches first estimate the distribution of a vector set and then measure the similarity between distributions.

A typical model-free approach is the pyramid match kernel of Grauman and Darrell [START_REF] Grauman | The pyramid match kernel: discriminative classification with sets of image features[END_REF][START_REF] Grauman | Approximate correspondences in high dimensions[END_REF]. The idea is to partition the feature space in a hierarchical manner and to count the number of correspondences between the two vector sets at each level of the hierarchy.

Model-based approaches can themselves be divided into two sub-classes as a vector set can be modeled with a discrete or a continuous distribution. In the first case, one makes use of an intermediate representation, generally referred to as a visual vocabulary in the context of images, which is obtained offline through the clustering of a large number of vectors. Each image is characterized by a histogram of visual word frequencies [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][START_REF] Csurka | Visual categorization with bags of keypoints[END_REF]. One of the main limitations of this approach is the assumption that the distribution of the features that can be encountered by the system is known a priori.

Of particular interest to us in this work are those approaches which model a vector set with a continuous distribution, generally a Gaussian mixture model (GMM) [START_REF] Jebara | Bhattacharyya and expected likelihood kernels[END_REF][START_REF] Jebara | Probability product kernels[END_REF][START_REF] Goldberger | An efficient image similarity measure based on approximations of KLdivergence between two Gaussian mixtures[END_REF][START_REF] Moreno | A Kullback-Leibler divergence based kernel for SVM classification in multimedia application[END_REF][START_REF] Vasconcelos | On the efficient evaluation of probabilistic similarity functions for image retrieval[END_REF][START_REF] Vasconcelos | The Kullback-Leibler kernel as a framework for discriminant and localized representations for visual recognition[END_REF]. The most commonly used measures of similarity between two GMMs are the Kullback-Leibler divergence (KLD) [START_REF] Goldberger | An efficient image similarity measure based on approximations of KLdivergence between two Gaussian mixtures[END_REF][START_REF] Moreno | A Kullback-Leibler divergence based kernel for SVM classification in multimedia application[END_REF][START_REF] Vasconcelos | On the efficient evaluation of probabilistic similarity functions for image retrieval[END_REF][START_REF] Vasconcelos | The Kullback-Leibler kernel as a framework for discriminant and localized representations for visual recognition[END_REF] and the probability product kernel (PPK) [START_REF] Jebara | Bhattacharyya and expected likelihood kernels[END_REF][START_REF] Jebara | Probability product kernels[END_REF]. These methods have however two main shortcomings.

First, to model accurately a vector set, one needs to train a sufficiently large number of Gaussians. The robust estimation of the GMM parameters may be difficult if the cardinality of the vector set is small. For instance, the number of local features extracted from an image typically varies from a few hundreds up to a few thousands. One could increase this number, e.g. by using a denser grid in the case of regular extraction or by lowering the detection threshold in the case of interest point detectors, but this would also significantly increase the cost of the feature extraction and the GMM estimation.

Second, as there is no closed form solution for the KLD or the PPK between two GMMs (except in special cases), approximate solutions have to be found. [START_REF] Moreno | A Kullback-Leibler divergence based kernel for SVM classification in multimedia application[END_REF][START_REF] Vasconcelos | The Kullback-Leibler kernel as a framework for discriminant and localized representations for visual recognition[END_REF] approximate the KLD using Monte Carlo (MC) sampling. However, the cost of this method is prohibitive as one has to randomly draw a large number of samples to obtain a reasonable estimate. [START_REF] Goldberger | An efficient image similarity measure based on approximations of KLdivergence between two Gaussian mixtures[END_REF] uses the the unscented transform, a deterministic approach which is reminiscent of MC sampling. As the cost of this method is quadratic in the number of Gaussians, it is impractical when the number of Gaussians is large. Goldberger et al. [START_REF] Goldberger | An efficient image similarity measure based on approximations of KLdivergence between two Gaussian mixtures[END_REF] and Vasconcelos [START_REF] Vasconcelos | On the efficient evaluation of probabilistic similarity functions for image retrieval[END_REF] proposed two very similar approximations of the KLD. They are based on a two-step approach: first find a matching between the Gaussians of the two distributions and then compute the KLD between the pairs of matched Gaussians. The cost of these approaches is still quadratic in the number of Gaussians.

The main contribution of this work is to model each vector set with a GMM adapted from a common "universal" GMM using the maximum a posteriori (MAP) criterion. This offers two main advantages:

• First, MAP estimation is more accurate than MLE in the challenging case where the training data is scarce as the universal model provides a priori information on the location of the parameters in the whole parameter space. We will show experimentally that this a priori information needs not to be exact: even if the universal model is learned on a set of images which is not directly related to the task at hand, excellent performance is obtained.

• Second, if two GMMs are adapted from a common distribution, there is a one-to-one correspondence between their Gaussians. We make use of this correspondence to derive approximations of the PPK and KLK with a cost linear in the number of Gaussians.

Note that the idea of learning visual vocabularies -modeled as GMMs -through the adaptation of a common universal vocabulary has already been used in [START_REF] Perronnin | Adapted vocabularies for generic visual categorization[END_REF]. However, in [START_REF] Perronnin | Adapted vocabularies for generic visual categorization[END_REF] the adapted vocabularies are class-GMMs and images are modeled with histograms of visual-word occurrences while in this article the adapted vocabularies are image-GMMs.

The remainder of the paper is organized as follows. In section 2 we describe the estimation of universal and adapted image models. In section 3 we present two similarity measures between distributions, the KLD and the PPK, and explain how they can be approximated in our case. Then in section 4 we provide experimental results on the PASCAL VOC 2006 and VOC 2007 databases and show the excellent performance of our system. Finally we draw conclusions in section 5.

Images as Adapted Mixtures of Gaussians

Let us first introduce our notation. The parameters of a GMM are denoted λ = {w i ,µ i , Σ i ,i =1 ...N } where w i , µ i and Σ i are respectively the weight, mean vector and covariance matrix of Gaussian i and N denotes the number of Gaussians. Let x be an observation vector and q its associated hidden variable. The likelihood that observation x was generated by the GMM is:

p(x|λ)= N i=1 w i p i (x|λ) .( 1 )
where p i (x|λ)=p(x|q = i, λ). Finally, γ i (x)=p(q = i|x, λ) is the occupancy probability, i.e. the probability that observation x was generated by Gaussian i. It is computed using Bayes formula:

γ i (x)= w i p i (x|λ) N j=1 w j p j (x|λ) . ( 2 )
We now describe the training of the universal model and the adapted image models.

Training the universal model

The universal GMM is supposed to describe the content of any image and, therefore, it should be trained offline on a varied set of images. Let λ u denote the parameters of the universal GMM. Let X = {x t ,t =1 ...T } be the set of training vectors. The estimation of λ u may be performed by maximizing the log-likelihood function log p(X|λ u ).T h e standard procedure for MLE is the Expectation Maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. For the E-step, the values γ i (x t ) are computed. We provide here for completeness the Mstep re-estimation equations [START_REF] Bilmes | A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models[END_REF]:

ŵu i = 1 T T t=1 γ i (x t ) ,( 3
)
μu i = T t=1 γ i (x t )x t T t=1 γ i (x t ) , ( 4 )
Σu i = T t=1 γ i (x t )x t x ′ t T t=1 γ i (x t ) -μu i μu i ′ .( 5 )

Training adapted image models

Our primary motivation for learning the image GMMs through the adaptation of a universal model is to overcome the scarcity of the training material. Indeed, only a small number of low-level feature vectors (typically from a few hundreds up to a few thousands) are extracted from one image. We will observe in section 4 that this is insufficient to train robustly a mixture with a large number of Gaussians (e.g. 100) for each image. In the following, λ a denotes the parameters of an adapted model.

Let X = {x t ,t =1 ...T } now denote the set of adaptation samples extracted from one image. We use the MAP criterion to adapt a GMM. The goal of MAP estimation is to maximize the posterior probability p(λ a |X) or equivalently log p(X|λ a ) + log p(λ a ). Hence, the difference with MLE is in the assumption of a prior distribution p(λ a ).T o perform MAP learning, one has to (i) choose the prior distribution family and (ii) specify the parameters of the prior distribution.

It was shown in [START_REF] Gauvain | Maximum a posteriori estimation for multivariate Gaussian mixture observations of Markov chains[END_REF] that the prior densities for GMM parameters could be adequately represented as a product of Dirichlet (prior on weight parameters) and normal-Wishart densities (prior on Gaussian parameters). When adapting a universal model with MAP to more specific conditions, it is natural to use the parameters of the universal model as a priori information on the location of the adapted parameters in the parameter space. As shown in [START_REF] Gauvain | Maximum a posteriori estimation for multivariate Gaussian mixture observations of Markov chains[END_REF], one can also apply the EM procedure for MAP estimation. The M-step re-estimation equations are provided here for completeness:

ŵa i = T t=1 γ i (x t )+τ T + N × τ , ( 6 )
μa i = T t=1 γ i (x t )x t + τµ u i T t=1 γ i (x t )+τ ,( 7
)
Σa i = T t=1 γ i (x t )x t x ′ t + τ [Σ u i + µ u i µ u i ′ ] T t=1 γ i (x t )+τ -μ a i μa i ′ .( 8 )
The relevance factor τ keeps a balance between the a priori information contained in the generic model λ u and the new evidence contained in X. If a mixture component i was estimated with a small number of observations T t=1 γ i (x t ), then more emphasis is put on the a priori information. On the other hand, if it was estimated with a large number of observations, more emphasis is put on the new evidence. Hence MAP provides a more robust estimate than MLE when little training data is available. The parameter τ is generally set manually [START_REF] Gauvain | Maximum a posteriori estimation for multivariate Gaussian mixture observations of Markov chains[END_REF][START_REF] Reynolds | Speaker verification using adapted Gaussian mixture models[END_REF].

For a given number of Gaussians, the cost of one EM iteration is (almost) identical for MLE and MAP. The only difference is the addition in the M-step of MAP of the a priori information in the statistics (compare equations 3, 4 and 5 to 6, 7 and 8 resp.) However, as MAP uses some a priori information on the location of the parameters, it requires a smaller number of EM iterations to reach an accurate estimate. Therefore, it is significantly faster compared to MLE. This statement will be verified experimentally.

We finally note that an adapted model contains the same number of Gaussians as the universal model from which it is adapted.

Measuring the Similarity of GMMs

In the following, we present two measures of similarity between distributions and show how to approximate them in our case.

Probability Product Kernel

The probability product kernel (PPK) [START_REF] Jebara | Probability product kernels[END_REF] between probability distributions p and q is defined as follows:

K ρ ppk (p, q)= x∈Ω p(x) ρ q(x) ρ dx .( 9
)
The PPK has two special cases. When ρ =1 , the PPK takes the form of the expectation of one distribution under the other:

K elk (p, q)=E p [q(x)] = E q [p(x)] . (10)
This is referred to as the Expected Likelihood Kernel (ELK) [START_REF] Jebara | Probability product kernels[END_REF]. When ρ =1 /2, it is known as the Bhattacharyya Kernel (BK).

There is a closed form solution for the PPK between two Gaussians:

K ρ ppk (p, q)=(2π) (1-2ρ)D/2 | Σ | 1/2 | Σ p | -ρ/2 | Σ q | -ρ/2 exp - ρ 2 µ ⊤ p Σ -1 p µ p - ρ 2 µ ⊤ q Σ -1 q µ q + 1 2 µ ⊤ Σµ , ( 11
)
where Σ=( ρΣ -1 p + ρΣ -1 q ) -1 , µ = ρ(Σ -1 p µ p +Σ -1 q µ q ) and D is the dimensionality of the feature vectors.

However there is no closed form solution for the PPK in the case of mixtures of Gaussians (except for the special case ρ =1). In the case of a mixture model, we have p(x)= N i=1 α i p i (x) and q(x)= M j=1 β j q j (x). In [START_REF] Jebara | Bhattacharyya and expected likelihood kernels[END_REF] (section 4) the following approximation is suggested:

K ρ ppk (p, q) ≈ N i=1 M j=1 α i β j K ρ ppk (p i ,q j ) . ( 12
)
When ρ ≤ 1 this approximation corresponds to an upperbound on the true value of K ρ ppk (p, q) and when ρ ≥ 1 it is a lower-bound.

The evaluation of the PPK between two GMMs which contain respectively M and N Gaussians requires the computation of M×N PPKs between individual Gaussians. This cost may be a handicap in the case of large values of M and N. We thus make use of the fact that two mixtures of Gaussians have been adapted from the same generic model to speed-up the computation. Indeed, Reynolds et al. [START_REF] Reynolds | Speaker verification using adapted Gaussian mixture models[END_REF] first noticed that there is a one-to-one correspondence between the i-th Gaussian of an adapted GMM and the i-th Gaussian of the GMM it is adapted from. By transitivity, it means that there is a one-to-one correspondence between the i-th Gaussians of two GMMs adapted from the same GMM (we recall that we necessarily have M = N in our adaptation framework). Consequently, in our case, the terms K ρ ppk (p i ,q i ) dominate the previous sum and the PPK may be further approximated as follows:

K ρ ppk (p, q) ≈ N i=1 α i β i K ρ ppk (p i ,q i ) . ( 13
)
This evaluation requires only the computation of N PPKs between individual Gaussians.

Kullback-Leibler Kernel

The Kullback-Leibler Divergence (KLD) between two continuous distributions is defined as follows:

KL(p||q)= x∈Ω p(x) log p(x) q(x) dx . (14)
There is also a closed form solution for the KLD between two Gaussians:

KL(p||q)= 1 2 log | Σ q | | Σ p | + Tr(Σ -1 q Σ p ) +(µ p -µ q ) T Σ -1 q (µ p -µ q ) -D . ( 15
)
However, no closed-form expression exists for the KLD between two GMMs. We follow the method of [START_REF] Goldberger | An efficient image similarity measure based on approximations of KLdivergence between two Gaussian mixtures[END_REF]. This approximation first consists in finding a mapping π from the Gaussians of p to the Gaussians of q as follows:

π(i) = arg min j (KL(p i ||q j ) -log β j ) . ( 16
)
Then π is used to approximate the KLD:

KL(p||q) ≈ N i=1 α i KL(p i ||q π(i) ) + log α i β π(i) . ( 17
)
This approximation is well motivated when Gaussians have little overlap, e.g. when the dimensionality D of the feature space is high. In our experiments, D =50(c.f. section 4.1).

If two GMMs contain respectively M and N Gaussians, computing the mapping function π requires the computation of M×N KLDs between individual Gaussians. Once again, we can make use of the fact that there is a one-toone correspondence between the Gaussians of two GMMs adapted from the same model to perform the following approximation: π(i)=i. Under this assumption, the KLD can be rewritten:

KL(p||q) ≈ N i=1 α i KL(p i ||q i ) + log α i β i . ( 18
)
Hence, the computation of the KLD requires only N Gaussian computations in our case. The Kullback-Leibler Kernel (KLK) can then defined by exponentiating the symmetric KLD SKL(p, q): SKL(p, q)=KL(p||q)+KL(q||p)

(19) K klk (p, q)=e x p ( -γSKL(p, q)) . ( 20
)
When choosing the value γ, one should take care that the kernel matrix is positive definite to ensure that K klk is a true kernel.

Experimental Results

We first describe our experimental setup. We then report results on two challenging datasets: the PASCAL VOC 2006 and VOC 2007 databases.

Experimental setup

Low-level feature vectors are extracted on regular grids at multiple scales in our experiments. On the average, on the order of 1, 000 feature vectors are extracted per image per feature type. We make use of two types of low-level features. The first features are based on local histograms of orientations as described in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] (128 dimensional features). The second ones are based on RGB statistics (96 dimensional features). In both cases, the dimensionality of the feature vectors is reduced to 50 through Principal Component Analysis (PCA).

The universal GMM is trained using the following iterative strategy inspired by HTK [START_REF] Young | The HTK book (version 3.2.1[END_REF]. We first train a GMM with a single Gaussian. We then split it into two by introducing a small perturbation in the mean parameter and retrain the GMM using several iterations of EM. The process of splitting and retraining is repeated until the desired number of Gaussians is obtained. To train the adapted image GMMs with MAP, the default value for the relevance factor is τ =10.

For the PPK, we choose ρ =1/2 (i.e. the Bhattacharyya Kernel) as this value lead to the best results in preliminary experiments. To set parameter γ for the KLK (c.f. equation 20) we followed [START_REF] Zhang | Local features and kernels for classification of texture and object categories: an in-depth study[END_REF]: γ is equal to the inverse of the mean of the symmetric KL divergence SKL(p, q) between two GMMs (c.f. equation 19) as estimated on a subset of the whole training set.

For classification we experimented with kernel logistic regression (KLR) and support vector machines (SVM). As we obtained very similar performance with both classifiers, in the following we report only the KLR results. One linear classifier is trained per class in a one-against-all manner.

We have two separate systems: one for each feature type. The end result is the average of the scores of the two systems.

VOC 2006 database

The PASCAL VOC 2006 database [START_REF] Everingham | The PASCAL visual object classes challenge 2006 results[END_REF] consists of 10 object classes: bicycle, bus, car, cat, cow, dog, horse, motorbike, person and sheep. There are 2,618 images for training and 2,686 for testing. During the VOC 2006 competition, the accuracy was primarily measured with the Area under the Curve (AUC). Therefore we also use the AUC (averaged over the 10 categories) to make our results easily comparable to the state-of-the-art.

In the following, we start with a comparative evaluation of the proposed approach. We then proceed with the analysis of the influence of parameter τ . We also carry out crossdatabase experiments showing that, even if the universal model is learned on a different database, the performance does not vary significantly. Finally, we analyze the computational cost of the proposed method on this database.

Comparative evaluation

We compare the performance of three systems:

(i) The proposed approach with MAP adaptation and the fast one-to-one mapping of Gaussian components (c.f. formula 13 for PPK and formula 18 for KLK). This system is later referred to as MAP OTO.

(ii) A system which learns the image GMMs with MLE (using the same iterative strategy which was employed to train the universal model) and the slow one-to-many mapping of Gaussian components (c.f. formula 12 for PPK and formulae 16 and 17 or KLK). This system is later referred to as MLE OTM.

(iii) An intermediate system which makes use of MAP adaptation as is the case of (i) but which uses the slow one-to-many scoring of (ii). This system is later referred to as MAP OTM.

Hence, when comparing (ii) and (iii), we can measure the benefit of MAP compared to MLE. When comparing (i) and (iii) we can measure the impact on the accuracy of the fast one-to-one scoring versus the slow one-to-many scoring.

Results are provided on figure 1. We can draw the following conclusions. First, MAP clearly outperforms MLE for both PPK and KLK. Especially the performance of the MLE OTM system starts to drop for more than 32 Gaussians while for MAP it continues to increase. This shows that we can learn robustly a larger number of Gaussians with MAP than with MLE. Second, the accuracy of PPK OTO is superior to that of PPK OTM. This observation came as a surprise as we first thought that by dropping terms in equation 12, we would lose information. Our best explanation is that the bound 12 is too coarse an approximation of the PPK. This suggests an alternative approach for computing the PPK similar to that used for KLK: first find a matching between the Gaussians of p and q and then approximate the PPK as a weighted sum of PPKs between the matched Gaussians. This approximation might be worth testing in the future. Third, the accuracy of KLK OTO is inferior to that of KLK OTM, but not significantly so, showing that our one-to-one approximation is a good one. Finally, PPK OTO and KLK OTO perform very similarly: the best results we obtained for both kernels was 0.945 for 128 Gaussian components. To the best of our knowledge, the best average AUC reported so far on this database was 0.936 (this was the accuracy of the winning QMUL LSPCH system [START_REF] Everingham | The PASCAL visual object classes challenge 2006 results[END_REF]).

Influence of MAP parameter τ

We now analyze the influence of the relevance factor τ . τ impacts two competing aspects of our system:

• First τ influences the robustness of the estimation.W e can consider two extreme cases. When τ =0 ,M A P turns into MLE and the parameters are not estimated robustly as was shown in the previous experiments. When τ = ∞, the image GMMs remain equal to the universal model. As the distance between any pair of images is constant no kernel classifier can be learned. The best performance will thus be obtained when an intermediate value between these two extremes is chosen.

• Second τ impacts the proposed fast scoring. Indeed, our fast scoring is only possible if there is a one-to-one correspondence between the Gaussians of two adapted GMMs. The strength of the correspondence will depend on τ .I f τ = ∞, the correspondence is maximized and the one-to-one mapping is exact. When τ =0, the correspondence is minimal.

Hence, the τ which optimizes the robustness (0 <τ < ∞) is necessarily different from the τ which optimizes the Gaussian correspondence (τ = ∞).

We present the result in figure 2. This analysis was performed on the 128 Gaussians model using the KLK kernel.

We can see that for small values of τ MAP OTM outperforms MAP OTO. This shows that, when τ is small the correspondence between the Gaussian of two adapted models is loose and that our one-to-one assumption is too naïve. However, as expected, as τ increases to more reasonable values, the difference between the two systems becomes narrower. For both systems the best performance is obtained for τ =10.

Cross database experiments

As the estimation of the image models with MAP relies on the a priori information contained in the universal model, it is important to understand how the performance of our approach is affected when the universal model is learned on another dataset. The alternate dataset we used to learn the visual vocabulary contains 120,000 unannotated images from a printing workflow of photo albums. We had a look at a small sample of these images to try to understand whether they were representative of the 10 categories found in the VOC 2006 database. While this set of images contains a very large number of photos of persons, it seems to contain very few (if no) occurrences of the 9 other classes. Hence, we believe that there is a strong mismatch between this dataset and VOC 2006. To learn a universal vocabulary, we took a random sub-sample of 2,000 images. This experiment was repeated 10 times with 10 different subsamples. We restricted this analysis to the case where we employ the fast scoring.

For both the PPK and the KLK kernels, the AUC (averaged over the 10 runs) did not change (0.945). What is interesting to notice is also that the AUC variation was very small from one sub-sample to another one: over the 10 runs, the worst performance obtained was 0.944 for PPK and 0.943 for KLK respectively.

Clearly, the proposed approach does not seem to be sensitive to the set of images used to train the universal model. Hence the same universal model can be used across different category sets. This is a clear advantage when one grows a category set incrementally as one does not need to relearn the universal GMMs, and thus the image GMMs, every time a new category is added.

Computational cost

We now perform a brief analysis of the computational cost of the proposed approach. For this analysis, we considered GMMs containing 128 Gaussians. The following durations were measured on a 2.4 GHz Opteron TM machine.

The cost of training the GMM of one image with MLE using the iterative strategy of [START_REF] Young | The HTK book (version 3.2.1[END_REF] is approximately 850 ms while it is only 30 ms for MAP. We recall that this difference is due to the greater number of EM iterations required for MLE compared to MAP. Note that, instead of the iterative approach of [START_REF] Young | The HTK book (version 3.2.1[END_REF], we could have used the alternative strategy which consists in starting from multiple random initializations of the parameters and picking the best one, i.e.the one which leads to the highest log-likelihood. However, the cost of this alternative would have been even greater.

We now consider the cost of the kernel computations. On the VOC 2006 database, classifying one image takes approximately 140 s for the PPK and 30 s for the KLK using the one-to-many scoring. With the proposed fast scoring based on the one-to-one correspondence, the classification cost is reduced to 1.3 s for PPK and 0.4 s for KLK. These figures are consistent with the fact that, for both kernels, we expect the proposed one-to-one scoring to be 128 times faster than the one-to-many scoring when GMMs contain 128 Gaussians (linear versus quadratic cost). It is also interesting to note that for both the fast and slow approaches, KLK is almost 5 times faster to compute than PPK. We also carried-out small-scale experiments using MC sampling to approximate the PPK and KLK. However, using MC sampling with 1,000 samples (a rather modest number) we estimated it would take on this database approximately 240 s to classify one image from this database.

VOC 2007 database

The PASCAL VOC 2007 database [START_REF] Everingham | The PASCAL visual object classes challenge 2007 results[END_REF] contains a total of 9,963 images: 5,011 images for training and 4,952 for testing. There are twenty object classes in this database: person, bird, cat, cow, dog, horse, sheep, aeroplane, bicycle, boat, bus, car, motorbike, train, bottle, chair, dining table, potted plant, sofa and tv monitor. During the VOC 2007 competition, the accuracy was primarily measured with the Average Precision (AP). Therefore, we also use the AP (averaged over the 20 categories) to make our results easily comparable to the state-of-the-art.

For these experiments, we used the proposed MAP OTO approach. Figure 3 shows that the performance of our systems (0.561 for PPK and 0.553 for KLK) is comparable to the performance obtained by the leading participants (the best reported result is 0.594). More details on the competition can be found in [START_REF] Everingham | The PASCAL visual object classes challenge 2007 results[END_REF].

Conclusion

In this article, we introduced a novel approach to compute the similarity between two unordered vector sets. The main contribution was to model each vector set with a generative model -a GMM in our case -adapted from a common universal model using MAP. We showed that this adaptation framework offers two major advantages compared to the case where the distributions are trained with MLE. First MAP provides a more accurate estimate compared to MLE when the cardinality of the vector sets is small. Second, there is a one-to-one correspondence between the components of adapted mixture models which may be used for fast scoring. This correspondence was used to derive efficient approximations for two kernels on distributions: the probability product kernel and the Kullback-Leibler kernel.

This approach was applied to the image categorization problem and it exhibited state-of-the-art results on the PAS-CAL VOC 2006 and VOC 2007 databases. We also showed that this approach is very practical. First, the classification cost is very reasonable. Second, the a priori information contained in the universal model needs not to be perfectly representative of the category set under consideration to obtain good results.

Future work could consider the use adaptation techniques other than MAP. Especially, techniques such as maximum likelihood linear regression (MLLR) [START_REF] Leggetter | Maximum likelihood linear regression for speaker adaptation of continuous density hidden Markov models[END_REF][START_REF] Gales | Maximum likelihood linear transformations for HMM-based speech recognition[END_REF], cluster adaptive training (CAT) [START_REF] Gales | Cluster adaptive training of hidden Markov models[END_REF] or "eigenvoices" [START_REF] Kuhn | Rapid speaker adaptation in eigenvoice space[END_REF] have been shown to yield significantly better results than MAP in the speech recognition literature when the amount of adaptation data is extremely scarce.

Figure 1 .

 1 Figure 1. Performance on the PASCAL VOC 2006 database of the PPK (top) and KLK (bottom) for a varying number of Gaussian components.

Figure 2 .

 2 Figure 2. Average AUC on the VOC 2006 database as a function of parameter τ .

Figure 3 .

 3 Figure 3. Comparison on the VOC 2007 database of the proposed approach (in white) with the leading participants (in black).


Christian Wolf
email: wolf@rfv.insa-lyon.fr

Jean-Michel Jolion
email: jean-michel.jolion@liris.cnrs.fr

Object count/Area Graphs for the Evaluation of Object Detection and Segmentation Algorithms 1

Keywords: Evaluation, object detection, text detection

Evaluation of object detection algorithms is a non-trivial task: a detection result is usually evaluated by comparing the bounding box of the detected object with the bounding box of the ground truth object. The commonly used precision and recall measures are computed from the overlap area of these two rectangles. However, these measures have several drawbacks: they don't give intuitive information about the proportion of the correctly detected objects and the number of false alarms, and they cannot be accumulated across multiple images without creating ambiguity in their interpretation. Furthermore, quantitative and qualitative evaluation is often mixed resulting in ambiguous measures.

In this paper we propose a new approach which tackles these problems. The performance of a detection algorithm is illustrated intuitively by performance graphs which present object level precision and recall depending on constraints on detection quality. In order to compare different detection algorithms, a representative single performance value is computed from the graphs. The influence of the test database on the detection performance is illustrated by performance/generality graphs. The evaluation method can be applied to different types of object detection algorithms. It has been tested on different text detection algorithms, among which are the participants of the ICDAR 2003 text detection competition.

Introduction

In the past, computer vision (CV) as a research domain has frequently been criticized for a lack of experimental culture [START_REF] Jain | Ignorance, Myopia and Naiveté in Computer Vision Systems[END_REF] [START_REF] Snyder | REPLY: A Commentary on the Paper by Jain and Binford[END_REF] [8] [START_REF] Bowyer | REPLY: Revolutions and Experimental Computer Vision[END_REF], which has been explained by the young age of the discipline. However, experimental evaluation of the theoretical advances is indispensable in all scientific work. We are currently trying very hard to establish a real experimental culture, and the need of strict experimental procedures in applying and evaluating algorithms is widely recognized [START_REF] Snyder | REPLY: A Commentary on the Paper by Jain and Binford[END_REF] [START_REF] Nagy | Candide's Practical Principles of Experimental Pattern Recognition[END_REF].

An important obstacle is the lack of common test databases and ground truth, which makes the comparison of different algorithms difficult. In some areas common test databases did emerge, as for instance the Brodatz test database for texture analysis, the NIST database for character recognition etc. However, the tuning of image processing algorithms to a small set of test databases is not undisputed. As Bowyer et al. put it [START_REF] Bowyer | REPLY: Revolutions and Experimental Computer Vision[END_REF], "the world is rich enough to provide infinitely interesting imagery".

For this reason, and because of their success in other disciplines, scientific competitions made their appearance during the last years. We may cite for example the TREC Video Track2 , a competition in the field of content based video indexing organized by NIST and held annually. The goal of the conference series is to encourage research in information retrieval from large amounts of text and video sequences by providing a large test collection, uniform scoring procedures, and a forum for organizations interested in comparing their results. The test collections are changed each year in order to avoid specialization to a single test database.

In the field of document image analysis, the ICDAR page segmentation competitions [START_REF] Antonacopoulos | ICDAR 2003 Page Segmentation Competition[END_REF], the ICDAR text detection competitions [START_REF] Lucas | ICDAR 2003 robust reading competitions[END_REF] and the GREC competition for line and arc detection [START_REF] Wenyin | A Protocol for Performance Evalution of Line Detection Algorithms[END_REF] should be mentioned (see section 3).

The introduction of the evaluation problem coincides largely with the emergence of the field of visual information retrieval. As a consequence, the first techniques have been naturally inspired by tools from this domain, as for instance precision/recall graphs which are frequently used in information retrieval. However, visual information has its own specificities, which need to be taken into account. This is the goal of this work.

In this paper we concentrate on the evaluation process, more specifically on the design of evaluation measures. Evaluation is a process which is often neglected by scientists, who spend most of their valuable time conceiving theories and designing solutions. However, in computer vision, a successful evaluation algorithm is rarely simple to design. Often it is necessary to conceive non-trivial algorithms in order to ensure an evaluation satisfying scientific requirements:

• A simple and intuitive interpretation of the obtained measures.

• An objective comparison between the different algorithms to evaluate.

• A good correspondence between the obtained measures and the objective performance of the algorithm to evaluate, taking into account its goal.

The latter point is particularly important. Aloimonos and Rosenfeld emphasize the purpose in CV [START_REF] Aloimonos | REPLY: A Response to "Ignorance, Myopia and Naiveté in Computer Vision Systems[END_REF]: "If we consider biological organisms that possess vision, we find that the visual system tends to be well matched to the environment of the organism and to the tasks that the organism performs. The paradigm purposive vision suggests that purpose should be a guiding principle in our study of vision". If we design CV systems according to a specific purpose, then it should be natural that we evaluate their performance according to this same purpose. This is the objective of "goal oriented evaluation".

A particular problem in computer vision, which has already given birth to a multitude of solutions is the problem of detecting objects in images. In this document, we introduce a new performance measure designed for the evaluation of object detection algorithms. In this context, by detection we also mean localization, thus tackling a two-part problem. We keep the general evaluation framework independent of the object type, defining an object as a visual entity with a spatial reality, and illustrate the concepts with experiments and examples from the field of text detection.

In the context of document image analysis, a similar problem is the one of document page segmentation. As in object detection, or more specifically in text detection, lists of rectangles need to be compared in order to evaluate these algorithms. However, although the two evaluation problems may be similar from a theoretical viewpoint, practically we need to emphasize some differences between page segmentation and text/object detection:

• The density of relevant information ("generality", see section 5) is higher for page segmentation problems. In text detection, on the other hand, text areas are not so much "classified" as "detected", i.e. that there can be and will be large areas which do not contain relevant material. This difference results in different evaluation techniques, which differ for instance in the way how the algorithms treats detection quality and detection quantity.

• In the page segmentation context, regions are possibly non-rectangular. The proposed evaluation algorithm, based on a rectangle representation of object reasons, is not applicable in this case.

The second point restricts the proposed evaluation systems to objects which are well represented by rectangles, which is the case for text, faces, people, generally speaking, compound objects. We therefore focus on these kind of problems, which are mostly encountered when evaluating systems working on natural scenes and video, but also systems which extract text from complex journals. However, this is not the case for some other problems encountered in document image analysis, notably curves as lines and arcs. These objects may overlap, therefore a single rectangle may contain several objects. While the general philosophy of the proposed system is applicable, i.e. the separation of detection quality and quantity and its representation as graphs, the object matching part itself is restricted to rectangle based representations.

The main contribution of this paper concerns the following issues:

• The separation of detection quality and detection quantity. New performance graphs allow us to easily perceive the detection quantity ("how many objects have been detected?" and "how many false alarms have been detected?") as well as detection quality ("how accurate is the detection of the objects?").

• The influence of the data base is evaluated, i.e. the relationship between the performance of the detection algorithms and the structure of the image test database is put forward. This makes it easier to grasp the advantage an object detection algorithm might have when it is tested on an image collection which a larger percentage of relevant information.

• The derivation of a single performance value which does not depend on quality related thresholds. Although this performance value, by definition, does not allow us to fully comprehend the behavior of a detection algorithm, it makes it easier to create a ranking of the algorithms to evaluate.

The reminder of this document is organized as follows: Section 2 gives an introduction to the problem and presents different evaluation modes on a hierarchy of different levels, which is formed by the different possible result representations.

Section 3 presents a survey on the previous work on the evaluation of object detection algorithms.

Section 4 introduces new performance graphs for an easy and intuitive interpretation of the detection performance as well as a new performance measure.

Section 5 demonstrates the dependence of evaluation algorithms on the structure of the test database and introduces a new evaluation graph which illustrates this dependence.

Section 6 applies the evaluation measure to two different text detection algorithms and illustrates its intuitive usage.

Finally, section 7 concludes.

Evaluation levels

Traditionally, object detection algorithms are evaluated using techniques developed for information retrieval systems. More specifically, the measures of precision and recall are widely used, since they intuitively convey the quality of the results:

In order to have a single performance value for the ranking of methods, the two measures are often linearly combined. The harmonic mean of precision and recall has been introduced by the information retrieval community [START_REF] Van Rijsbergen | Information Retrieval[END_REF]. Its advantage is that the minimum of the two performance values is emphasized:

Perf IR = 2 P IR • R IR P IR + R IR (2)
For the object detection problem, the measures of recall and precision are not directly applicable, since the decision whether an object has been detected or not is not a binary one. Object detection algorithms may be evaluated at different levels w.r.t. the representation of the detection results, corresponding to different phases of the detection algorithms (see figure 1). The evaluation measures of the different levels differ in their relevance to the goal of the application and in their coverage, i.e. in the detection phases which are evaluated by the measure: Feature discriminance at pixel level At this level, the quality of the chosen features is evaluated without taking into account the classification decision taken in a later phase. Therefore, the result evaluated for each pixel p is not a binary decision but a feature vector x p . Splitting the pixels into two populations, where the first population consists of the pixels labeled as "object" according to the ground truth, and the second population consists of the "non-object" pixels, the goal of the evaluation measure at this level is to assess whether the features are well separated between the two populations.

Assuming Gaussian distributions in both cases, an example of such a statistical separation measure is the Bhattacharyya distance [START_REF] Fukunaga | Effects of sample size in classifier design[END_REF]:

B = 1 8 (µ 2 -µ 1 ) T Σ 1 + Σ 2 2 -1 (µ 2 -µ 1 ) + 1 2 ln Σ 1 +Σ 2 2 |Σ 1 | |Σ 2 | (3)
where the µ j , j = 1..2 are the mean vectors of the two distributions and the Σ j are the covariance matrices.

Note, that the Bhattacharyya distance measures the separability of the features under the assumption of a linear decision function.

Alternatively, the classification error might be used for evaluation.

We note, that if the performance is evaluated at pixel level, then the ground truth must be very precise in order to get robust measures. This is rarely the case as ground truth is mainly obtained through interaction between the images and a human observer, which can easily detect an object but can rarely locate it with 1-pixel precision.

Detection at rectangle level From the end user's point of view, a more natural way is to ask the question whether an object has been detected correctly or not. On this level we still ignore domain specific knowledge from processing steps following the detection step, but we nevertheless evaluate the detection on a per object/rectangle basis. This assumes objects of compact shape, for which the rectangle approach makes sense. This is not appropriate for textures, or objects like snow, falling water, shadows, but does make sense for objects like humans, faces, text, tools etc. The reminder of this document deals with this evaluation level.

Goal oriented evaluation In many applications, object detection is performed for a specific reason which is beyond the pure localization of the object. For instance, face detection might be a preliminary step for face recognition, text detection might be a preliminary step for text recognition, etc.

In this case, in order to take into account the specific goal, the evaluation algorithm should resort to the results of the application specific processing. In the context of text detection, a goal oriented evaluation scheme for a system which exploits the text content (as opposed to its position) should penalize lost text characters as well as additional characters which are not present in the ground truth. Possibilities are recall and precision on character level, or the string edit distance [START_REF] Wagner | The string to string correction problem[END_REF].

In the case of text detection for indexing video broadcasts, one might consider evaluation on an even higher level by weighting words according to their usefulness for the indexing process [START_REF] Landais | A goal directed methodology for groundtruthing and evaluating a commercial OCR[END_REF].

The evaluation level to choose depends on the application and the purpose of the evaluation. The pixel based evaluation measures are easy to calculate and easy to interpret. However, they lack relevance to the goal of the process and are not very accurate. Very often they are used to guide the choice of features used for detection, since they are not influenced by later steps of the detection algorithm.

The goal directed approaches are natural methods to employ for the final evaluation of the algorithm's performance. They directly measure the success which can be expected by the algorithm. However, very often the localization of the object is the final goal of the application. For instance, in the case of face detection or text detection, recognition of the object might be impossible because of low data quality. In image and video indexing applications, the presence of a face or of text is valuable information which can be exploited. In this context, goal directed evaluation is equivalent with evaluation on rectangle level (figure 1c).

Evaluation levels (a), (b) and (d) are easy to calculate and easy to interpret, since they treat "items" which are directly comparable (pixels and characters, respectively). On the other hand, rectangle based evaluation (level (c)) is a non-trivial task: as the detection result is rarely exactly equivalent to the object as specified in the ground truth, we cannot easily say whether an object has been correctly detected or not. In the reminder of this work, we concentrate on the problem of evaluation on rectangle level.

Previous work

The goal of a rectangle based object detection evaluation scheme is to take a list G of ground truth object rectangles G i , i = 1..|G| and a list D of detected object rectangles D j , j = 1..|D| and to measure the quality of the match between the two lists. The quality measure should penalize information loss, which occurs if objects or parts of objects have not been detected, and it should penalize information clutter, i.e. false alarms or detections which are larger than necessary 3 .

Most algorithms are based on an extension of the recall and precision measures which are calculated on the area of two rectangles G i and D i and on the area of the overlapping region:

R AR (G i , D i ) = Area(G i ∩ D i ) Area(G i ) P AR (G i , D i ) = Area(G i ∩ D i ) Area(D i ) (5)
Recall illustrates the proportion of the ground truth rectangle which has been correctly detected, and precision decreases if the amount of additional incorrectly detected area increases. In the reminder of this work, we call these measures "area recall" and "area precision", respectively. Whereas calculating these figures for a single pair of result and ground truth rectangles is straightforward, the extension to the realistic case of two lists of rectangles is not as easy. The existing evaluation methods differ in the way they treat the correspondence problem between the two rectangle lists, i.e. whether they consider single matches only or multiple matches, and in the way they combine the figures in order to generate a single measure for multiple rectangles and multiple images.

Doermann et al. present a configurable ground-truthing and evaluation system with a graphical java interface [START_REF] Doermann | Tools and Techniques for Video Performance Evaluation[END_REF] for video segmentation. Their system also takes into account temporal matching of objects in videos and provides different temporal matching levels. However, the spatial matching algorithms supported by the tool are rather simple.

In [START_REF] Mariano | Performance Evaluation of Object Detection Algorithms[END_REF], Mariano et al. propose a set of evaluation measures, among which are the area measures on rectangle bases given in equation ( 5) as well as measures on pixel level. Several extensions to multiple rectangles are suggested: summing up thresholded values of these measures, which introduces a dependence on a threshold, and directly calculating the measures on sets of rectangles by combining the rectangles to larger surfaces, which gives rise to ambiguity problems (see section 4).

Antonacopoulos et al. propose an algorithm capable of comparing lists of rectangles [START_REF] Antonacopoulos | Methodology for Flexible and Efficient Analysis of the Performance of Page Segmentation Algorithms[END_REF] in the context of document page segmentation. Each ground truth rectangle or polygon is extended up to the borders of the surrounding rectangles or the page border and checks whether segmented rectangles fall into these "maximized ground truth polygons". "partial misses", "misses" and "merges" are considered. However, this approach may pose problems in the case of text/object detection, where there are not always surrounding text/object rectangles. Furthermore, the evaluation algorithm focuses on reporting the accuracy the detection/classification of each rectangle, the authors do not provide performance measures for a whole document.

A simple evaluation scheme has been used to evaluate the systems participating at the text locating competition in the framework of the 7 th International Conference on Document Analysis and Recognition (ICDAR) 2003 [START_REF] Lucas | ICDAR 2003 robust reading competitions[END_REF]. Each rectangle in one list is matched with the best match in the opposing list: identical to its bounding rectangle. In reality, a missed part of G i may not contain object pixels, or a part of a false alarm in D i may not contain detected pixels.

R ICD (G, D) = |G| i=1 BestM atch G (G i ) |G| P ICD (G, D) = |D| j=1 BestM atch D (D j ) |D| (6)
where BestM atch G and BestM atch D are functions which deliver the quality of the closest match of a rectangle in the opposing list:

BestM atch G (G i ) = max j=1...|D| 2 • Area(G i ∩ D j ) Area(G i ) + Area(D j ) BestM atch D (D j ) = max i=1...|G| 2 Area(D j ∩ G i ) Area(D j ) + Area(G i ) (7)
If a rectangle is matched perfectly by another rectangle in the opposing list, then the match functions evaluate to 1, else they evaluate to a value < 1. Therefore, the original measures taken from the information retrieval community, given by ( 1), are upper bounds for the new measures given by ( 6). Both, precision and recall given by ( 6), are low if the overlap region of the corresponding rectangles is small.

A disadvantage of the ICDAR evaluation scheme is that only one-to-one matches are considered. However, in reality sometimes one ground truth rectangle is "split" into several object rectangles or several ground truth rectangles are "merged" into a single detected object rectangle. This is a problem the authors themselves report in [START_REF] Lucas | ICDAR 2003 robust reading competitions[END_REF]. The problem is generally encountered in detection evaluation frameworks, which is due to the fact that we are interested in evaluating the solution of a detection problem but the ground truth is specified as the "correct" solution of a segmentation problem. However, an over-or under segmented solution may very well be a correct detection.

Liang et al. present a method for the evaluation of document structure extraction algorithms [START_REF] Liang | Performance evaluation of document layout analysis algorithms on the UW data set[END_REF]. From the two lists G and D of detected rectangles and ground truth rectangles, they create two overlap matrices σ and τ . The lines i = 1..|G| of the matrices correspond to the ground truth rectangles and the columns j = 1..|D| correspond to the detected rectangles. The values of these matrices correspond, respectively, to area recall and area precision between the row rectangle G i and the column rectangle D j :

σ ij = R AR (G i , D j ) τ ij = P AR (G i , D j ) (8)
Matching rectangles is done by thresholding the values in the two matrices and clustering them into groups. Different match types are supported: one-to-one matches, one-tomany matches (splits) and many-to-one matches (merges). See figure 2 for an illustration of these concepts.

Hua et al. [START_REF] Hua | An Automatic Performance Evaluation Protocol for Video Text Detection Algorithms[END_REF] also take into account splits and merges. They introduce two measures: "detection quality", which relates to recall, and "false alarm rate" which relates to (1 -precision). However, each measure is calculated as product of two factors: a factor which depends on the surface ratios -similar to the ICDAR solution -and a factor which measures the rectangle fragmentation. The latter factor decreases in the case of splits and merges. The measures are normalized according to a detection difficulty value, which is estimated from the ground truth image. It takes into account the rectangle size and the variance of the character height. The overall detection performance is weighted by a detection importance value, which is part of the ground truth.

The evaluation protocol used for the ICDAR 2003 Page segmentation contest [START_REF] Antonacopoulos | ICDAR 2003 Page Segmentation Competition[END_REF] is based on the same principles as Liang's method. The overlap matrices (they call them "MatchScore tables") are used to match ground truth entities to detected entities, where an entity (i.e., a region) may contain text, graphics, line-art, a separator or noise, which makes an adaptation of the overlap matrices necessary in order to evaluate the classification of each region. Splits and merges are supported. For each match, a performance value is calculated as the harmonic mean of a recall type measure and a precision type measure. The global performance value for all entities is a computed as a weighted sum of the individual scores.

This page segmentation protocol is very similar to the other rectangle methods described above, in particular to Liang's method, the difference being the evaluation of the region type classifier and some details in the computation of the recall and precision measures. However, it suffers from the same drawbacks: the lack of intuitivity and the ambiguity of the response due to the mixture of detection quality and detection quantity.

Landais et al. propose an evaluation measure which is not based on the overlap information [START_REF] Landais | A goal directed methodology for groundtruthing and evaluating a commercial OCR[END_REF]: they consider a pair of detected/groundtruth rectangles as matching if and only if the centroid of one rectangle is contained in the other rectangle. Although this solution is tempting since it avoids the usage of parameters, it tends to accept matches with very low area recall and/or precision and it does not give an information on the quality of the detection.

In the context of the Graphics Recognition Workshop (GREC) competitions, algo-rithms for the detection of lines and arcs are evaluated. Although these graphics objects are different from rectangles, the proposed evaluation algorithms do share common features with the algorithms designed for rectangle matching. In [START_REF] Wenyin | A Protocol for Performance Evalution of Line Detection Algorithms[END_REF], the GREC organizers describe two evaluation types, one on pixel level and one on vector level. The latter matches lines and arcs by comparing their endpoints and placing thresholds on the distances between these endpoints and the curves. For each matching pair of line/arc segments, a complex quality measure is proposed, which combines measures of endpoint distance, line overlap, line with quality, line style quality and line shape quality. For the ensemble of lines and arcs these measures are combined in order to form two classical measures: vector detection rate, which corresponds to a sort of recall measure, and vector false alarm rate, which relates to a sort of precision measure. Like the classical rectangle based protocols, this algorithm combines detection quality and detection quantity in a single measure, which makes it hard to understand the behavior of the algorithm to evaluate. Furthermore, the complexity of the quality measure is at the same time its main drawback: the performance values are difficult to understand.

Object count/Area graphs

Area recall and area precision are easy to interpret as long as there are only two rectangles involved: a single ground truth rectangle and a single detection result rectangle. However, in the case of multiple images or a single image with multiple text rectangles, a combination of the measures is not straightforward. This is the main drawback of the existing evaluation schemes described in the previous section: the way the overlap information is accumulated during the calculation of the evaluation measures leaves room for ambiguity. For instance, a recall of 50% could mean that 50% of the ground truth rectangles have been matched perfectly, or that all ground truth rectangles have been found but only with an overlap of 50%, or anything in between these two extremes. As a consequence, these recall and precision measures are not very intuitive: it is impossible to determine, how many text rectangles have been detected. Similarly, the quality of the detection is not apparent.

Requirements of an evaluation algorithm

We developed an evaluation scheme which addresses these problems. Its design has been guided by the following goals:

1. The approach should provide a quantitative evaluation: the evaluation measure should intuitively tell how many text rectangles have been detected correctly, and how many false alarms have been created.

The most important constraint of our design goals is the contradiction between goal (1), to be able to count the number of detected rectangles, and goal [START_REF] Antonacopoulos | Methodology for Flexible and Efficient Analysis of the Performance of Page Segmentation Algorithms[END_REF], to be able to measure detection quality. Indeed, the two goals are related: the number of rectangles we consider as detected depends on the quality requirements which we impose for a single rectangle in order to be considered as detected. For this reason we propose a natural way to combine these two measures: two-dimensional plots which illustrate their dependence. More precisely, on the y-axis we plot the two measures which are the most interesting for us: object counts, i.

As stated above, these two measures depend on the quality requirements, which are imposed using two measures: area recall and area precision. In other words, the detection performance is illustrated using two diagrams, where the first shows the dependence on area recall and the second shows the dependence on area precision. Each diagram, on the other hand, contains two graphs: one plots object recall, the other one object precision (see figure 5 in the results section for an example). The reminder of this section describes in detail how object recall and object precision are calculated given fixed constraints on area recall and area precision.

Rectangle matching

The computation of the measures given in (9) requires for each ground truth rectangle G i the determination whether it has been detected or not, and for each rectangle D i in the detection result the determination whether its detection is correct or not. These decisions are taken based on constraints imposed on the detection quality, i.e. the overlap between detection result and ground truth. In order to take into account oneto-one as well as one-to-many matches (splits) and many-to-one matches (merges), we calculate the overlap matrices σ and τ introduced by Liang et al. in [START_REF] Liang | Performance evaluation of document layout analysis algorithms on the UW data set[END_REF], as described in section 3.

The matrices are analyzed in order to determine the correspondences between the two rectangle lists. In general, a non zero value in an element with indices (i, j) indicates, that ground truth rectangle G i overlaps with result rectangle D j . However, the two rectangles are matched only if the overlap satisfies the quality constraints, i.e. if area recall and area precision are higher than the respective constraint:

(a) σ ij > t r (b) τ ij > t p ( 10
)
where t r ∈ [0, 1] is the constraint on area recall and t p ∈ [0, 1] is the constraint on area precision. In detail, the different matches are determined as follows:

one-to-one matches: one ground truth rectangle G i matches with a result rectangle D j if row i of both matrices contains only one element satisfying [START_REF] Jain | Ignorance, Myopia and Naiveté in Computer Vision Systems[END_REF] and column j of both matrices contains only one element satisfying [START_REF] Jain | Ignorance, Myopia and Naiveté in Computer Vision Systems[END_REF]. This situation is shown in figure 2a.

one-to-many matches (splits): one ground truth rectangle G i matches against a set S o of result rectangles D j , j ∈ S o if

• a sufficiently large proportion of the ground truth rectangle has been detected (condition (10a) in a "scattered" version):

j∈So σ ij ≥ t r , and

• each contributing result rectangle overlaps enough with the ground truth rectangle to be considered a part of it (condition (10b) in a "scattered" version):

∀j ∈ S o : τ ij ≥ t p .
Figure 2b illustrates this match type.

many-to-one matches (merges): one result rectangle D j matches against a set S m of ground truth rectangles if

• A sufficiently large portion of each ground truth rectangle is detected (condition (10a) in a "scattered" version): ∀i ∈ S m : σ ij ≥ t r , and

• Each ground truth rectangle has been detected with enough area precision (condition (10b) in a "scattered" version): many-to-many matches (splits and merges): this match type is currently not supported by our algorithm. Our experiments showed, that this situation does not occur very often in the case of text detection.

i∈Sm τ ij ≥ t p
If a situation occurs which requires simultaneous splits and merges, then the algorithm translates this situation into several splits or a set of splits and one-to-one matches: each ground truth rectangle in the matching set is either part of a split if it is matched against several detected rectangles, or it is part of a one-to-one match if it is matched against a single detected rectangle. The drawback of this implementation is a slight unjustified punishment of combined splits and merges, since detected rectangles may be part of several sets of splits. In each set, the part of the detected rectangle which covers a ground truth rectangle of another set, is falsely reported as "missing" in the original set.

Based on this matching strategy, the recall and precision measures which we intuitively described in [START_REF] Huijsmans | Extended Performance Graphs for Cluster Retrieval[END_REF], can be finally defined as follows:

R OB (G, D, t r , t p ) = i M atch G (G i , D, t r , t p ) |G| P OB (G, D, t r , t p ) = j M atch D (D j , G, t r , t p ) |D| (11)
where M atch G and M atch D are functions which take into account the different types of matches described above and which evaluate to the quality of the match:

M atch G (G i , D, t r , t p ) = =                1 if G i matches against a single detected rectangle 0 if G i does not match against any detected rectangle f sc (k) if G i matches against several (→ k) detected rectangles M atch D (D j , G, t r , t p ) = =               
1 if D j matches against a single detected rectangle 0 if D j does not match against any detected rectangle f sc (k) if D j matches against several (→ k) detected rectangles where f sc (k) is a parameter function of the evaluation scheme which controls the amount of punishment which is inflicted in case of scattering, i.e. splits or merges. If it evaluates to 1, then no punishment is given, lower values punish more. In our experiments we set it to a constant value of 0.8. Another possibility could be to use two different functions in the expressions M atch G and M atch D in order to punish over segmentation differently than under segmentation. This might be useful if text detection is followed by text recognition. Furthermore, more scattering might be punished more severely by adding a dependence to the number of rectangles k, for instance by setting f s c(k) = 1 1+ln(k) , which corresponds to the fragmentation index suggested by Mariano et al. [START_REF] Mariano | Performance Evaluation of Object Detection Algorithms[END_REF].

As a final remark, please note, that text which is only partly detected and therefore not matched against a ground truth rectangle, will correctly decrease the precision measure, in contrast to the ICDAR evaluation scheme described in section 3.

Multiple images

In the case of N images, we compare several lists G k ∈ G, k = 1..N of ground truth rectangles with several lists D k ∈ D, k = 1..N of result rectangles. As in information retrieval, the results on multiple images may not be accumulated by summing the recall or precision values. Instead, object recall and object precision are defined as follows:

R OB (G, D, t r , t p ) = k i M atch G (G k i , D k , t r , t p ) k |G k | P OB (G, D, t r , t p ) = k j M atch D (D k j , G k , t r , t p ) k |D k | (12)

Constructing the graphs

As explained before, the object related measures introduced in equation ( 12) depend on two constraints t r and t p which impose constraints on the detection quality. The performance diagrams are produced by fixing one constraint to a set value, varying the second one (assigned to the x-axis) and plotting object recall and object precision on the y-axis of two graphs. Figure 5 in the experimental section shows an example of the two diagrams obtained this way. The diagram shown in figure 5a is generated by varying the constraint on area recall, t r , while constraint t p is held to a fixed value. The diagram is composed of three graphs: object recall, object precision and the harmonic mean of the two measures. Similarly, figure 5b is created varying constraint t p while constraint t r is fixed.

The diagrams are easily interpreted by looking at the dynamics of the graphs: in this particular example, the fact that object recall never drops to zero when area recall approaches 1 means, that most of the text rectangles are detected with an area coverage of 100%, i.e. the detection rarely cuts parts of the ground truth rectangle. On the other hand, the fact that object recall does drop to zero when area precision approaches 1, means that all result rectangles exceed the ground truth boundaries. The particular amount of area which is detected additionally can be seen by the point/range where the object recall dramatically drops when area precision increases.

As stated above, during the creation of the graphs one of the two constraints is held fixed. The particular values assigned to the fixed constraints have been chosen empirically. However, we decided to pick different values for the two different constraints: while t r is fixed to 0.8, we chose the lower value of 0.4 for constraint t p . This decision is motivated by the fact that a detection result which cuts parts of the text rectangle is more disturbing than a detection which results in a too large rectangle. The value of 0.4 might seem very low, but keep in mind that the area of a rectangle grows with the square of the its side lengths. This fact is illustrated in figure 3, which shows a detection result with 50% area precision. The detected rectangle is twice as large as the ground truth rectangle, although the difference in the corner coordinates is quite small. Please refer to the discussion section for some remarks on the implications of this situation to text detection algorithms.

Three-dimensional graphs

An alternative presentation of the performance measures are three-dimensional plots of the three object related measures (recall, precision and the harmonic mean), respectively, on the z-axis, whereas t r is assigned to the x-axis and t p is assigned to the y-axis. Figure 6 shows an example of such a set of plots.

The advantage of a 3D plot is a gain in information: for each combination of thresholds t r and t p , i.e. for each conceivable combination of quality constraints, we are able to read the performance of the detection algorithm. However, this advantage is bought with several drawbacks, which severely hamper the usability of the plot:

• The 3D plots are more difficult and less intuitive to read. In particular, the actual performance value on one point of the performance is difficult to read.

• The different object related performance measures cannot be displayed in a single diagram comprising several plots, as in the 2D case, since the surfaces would be unreadable. Therefore, several diagrams need to be created, resulting in unnecessary need of space. This is illustrated in figure 6, which shows the plots for two detection algorithms, one column corresponding to one algorithm.

• The interpretation of a 3D graph is only possible if the function is smooth enough against changes of the quality parameters. This might not always be the case, depending on the behavior of the evaluated detection algorithm.

• The complexity of the calculations needed for the 3D plots is much higher. More precisely, complexity rises from O(N ) to O(N 2 ).

In general, we think that the gain in additional information is small compared to the drawbacks of the 3D plots.

A single performance value

The performance diagrams introduced above are an easy and intuitive way to illustrate the performance of an object detection algorithm. However, very often it is useful and desirable to determine a single performance value for an algorithm, either for direct comparison of the performances of different algorithms, or to optimize the parameters of the detection algorithm, or to control the algorithm, for instance in a reinforcement learning environment [START_REF] Taylor | Reinforcement Learning for Parameter Control of Text Detection in Images and Video Sequences[END_REF]. For the reasons laid out in sub section 4.1, an objective comparison of the algorithms by a single scalar value is difficult, up to impossible. A single value is hardly able to characterize the complex behavior of a detection algorithm, which makes it necessary to resort to compromises. At first sight, a simple solution might be to hold the quality constraints t p and t r at fixed values, calculate object recall and object precision and combine them in a harmonic mean. However, this evaluation would depend heavily on the particular chosen values. One algorithm could outperform another one for given quality constraints, while it could show a weaker performance for other constraints.

A special case of this solution would be the end points of the curves (t p = 1 and t r = 1, respectively). As for any other fixed value of t p and t r , this solution ignores the behavior of the algorithm for other detection quality constraints. It is immediately clear that this behavior is important when we look at figure 8. H.W.David's algorithm (displayed in the top row) and Todoran's algorithm (displayed in the 4 th row) share the same end point in the right diagram: Recall=Precision=0 for t r = 1. This means, that both algorithms detect rectangles which are larger than the ground truth rectangles, since not a single rectangle is considered as found if a precision of 100% is required. However, looking at the rest of the curve, we can see the difference in the behavior of the two detection algorithms: H.W.David's algorithm features a Recall of almost 60% across a large section of the precision quality constraint. Recall only drops rather sharply when a quality constraint of about 55% is reached. Summing it up, we might say that H.W.David's algorithm detects 60% of the rectangles with realistic assumptions on detection precision. On the other hand, Todoran's algorithm shows an almost linear dependance of Recall on detection quality. This tells us, that the differences in size between the ground truth rectangles and the detected rectangles are more equally distributed, the algorithm's behavior is therefore less predictable.

A good indicator should cover the performance of the evaluated algorithm across a whole range of quality constraints. We therefore propose the proportion of the graph area which is beneath the performance graphs as a reliable and objective measure, which is equivalent to the mean value of object measures over all possible constraint values.

More precisely, we first calculate the area proportion separately for object recall and object precision:

R OV = 1 2T T i=1 R OB (G, D, i/T, t p ) + + 1 2T T i=1 R OB (G, D, t r , i/T ) P OV = 1 2T T i=1 P OB (G, D, i/T, t p ) + + 1 2T T i=1 P OB (G, D, t r , i/T ) (13)
The final performance value is the harmonic mean of the two measures:

Perf OV = 2 P OV • R OV P OV + R OV (14)
The parameter T is a granularity parameter which controls the trade-off between the computational complexity of the evaluation algorithm and the precision of the integration approximation. However, it is not likely that the object related measures change sharply after changing the quality constraints in very small steps. Consequently, in our experiments, we set the parameter to T = 20.

Evaluating the influence of the test database

As for information retrieval (IR) tasks, the measured performance of an object detection algorithm highly depends on the test database. It is obvious, that the nature of the images determines the performance of the algorithm. As an example we could think of the object type (different poses for face detection, artificial text or scene text for text detection), its size, the image quality, noise, compression artifacts etc. For this reason, an objective comparison between different algorithms will only be possible if the respective communities decide on shared common test databases. Alternatively, we recommend tackling this problem partly by performing different experiments for different test databases with different difficulties.

On the other hand, the nature of the images is not the only variable which determines the influence of the test database on the detection performance. The structure of the data, i.e. the ratio between the relevant data and the irrelevant data, is a major factor which influences the results. This simple but important fact has been overlooked by the information retrieval community for a long time.

In [START_REF] Huijsmans | Extended Performance Graphs for Cluster Retrieval[END_REF], Huijsmans et al. call attention to this fact and adapt the well known precision/recall graphs in order to link them to the notion of generality for an IR system, which is defined as follows:

Generality IR = N.o. relevant items in the database n.o. items in the database (

Very large databases with low generality, i.e. much irrelevant clutter compared to the relevant material, produce results with lower precision than databases with higher generality. This makes sense, since the probability to retrieve a relevant item is lower if there is more irrelevant noise present in the database. A standard IR system presents the retrieved items to the user in a result set of predefined size. Since this size is fixed, with falling generality the amount of relevant material in the result set -thus the recall -will tend to be smaller. Thus, recall and precision depend on the generality of the database. In IR one is interested in the retrieval performance with respect to the generality as well as with respect to the size of the result set, which determines the search effort for the user. The dependence on two parameters makes three-dimensional performance graphs necessary. Alternatively, Huijsmans proposes two-dimensional graphs, which corresponds to a plane of the 3D space defined by Precision = Recall. Therefore, the graph plots Precision=Recall on the y-axis against generality on the x-axis. However, unlike IR tasks, object detection algorithms do not work with items (images, videos or documents). Instead, images (or videos) are used as input, and object rectangles are retrieved. Nevertheless, a notion of generality can be defined as the amount of objects which are present in the images of the database. We define it to be Generality = N.o. object rectangles in the database N.o. images in the database [START_REF] Nagy | Candide's Practical Principles of Experimental Pattern Recognition[END_REF] Note, that using this definition, generality may attain values ≫ 1. This is not a problem since the value is interpreted by humans or used in plots (see section 6.1). Another difference to IR systems is the lack of a result set window, because all detected items are returned to the user. Therefore, the generality of the database does influence precision, but not recall. Thus, the influence of the database structure on the system performance can be shown with simple two-dimensional precision/generality graphs. The graphs introduced by Huijsmans are displayed on a logarithmic scale, since the generality in very large IR databases may attain very low values. On the other hand, the amount of objects per image (or per video frame) should remain relatively high, therefore we decided to display the graphs on a linear scale.

A decision needs to be made concerning the generality level of the database when result tables or graphs are displayed which contain a fixed level of generality. In other words, it is necessary to decide how many images with zero ground truth (no object present) should be included in the database. The exact amount depends on the particular application. The a priori probability of an image to contain exotic objects, as for instance water falls or fire might be very low. Another determining factor is the type of medium. In most cases, for applications working on single images the probability is higher than for applications working on video sequences. In this document, where experiments were performed on images containing text objects (see section 6), we chose a mixture of 50% images with relevant objects and 50% images without relevant objects.

Experimental results

We tested our new evaluation metric on two different sets of text detection algorithms which have been applied to different image test databases, respectively.

Evaluating text detection in video frames

The first test dataset contains two algorithms, which have been developed by the authors. Details are given in [START_REF] Wolf | Extraction and Recognition of Artificial Text in Multimedia Documents[END_REF] and [START_REF] Wolf | Text Detection in Images taken from Videos Sequences for Semantic Indexing[END_REF], respectively. For the sake of brevity, in the reminder of this paper we call them algorithm 1 and algorithm 2. The two methods have been applied to a small set of video frames in the CIF format (384×288 pixels), which have been provided by INA4 and France Tï¿ 1 2 ï¿ 1 2 om. This small database contains only 14 images, which makes it possible to visually show the detection results superimposed on the images (see figure 4). Thus, a direct comparison can be made between the detected object rectangles and, respectively, the object/area performance graphs (figure 5) and the performance/generality graphs (figure 7).

The left column of figure 5 shows object recall and precision depending on the constraints imposed on area recall. Object recall and precision decrease only slowly when t r approaches 1, which means that most of the object rectangles are detected with their entire area. Note, that the object recall graph drops faster for algorithm 2, illustrating a lack of the algorithm to detect the whole area of each rectangle. This can be confirmed looking at the superimposed results in figure 4a and figure 4b, respectively.

The right column of figure 5 shows object recall and precision depending on the constraints imposed on area precision. Object recall and precision drop to zero when t p approaches 1, illustrating the fact that all object rectangles are larger than the corresponding ground truth rectangles. We can see that algorithm 1 is more precise, since object recall drops slower when the t p is increased. Again, this is confirmed looking at the superimposed results in figure 4.

Figure 7 shows the dependence of the performance on the database structure. In order to create graphs falling with lower generality, inverse generality has been assigned to the x-axis. More precisely, the left most value of the graph (1/Generality = 0.2) corresponds to a set with 7 images containing text only, whereas the right most value of the graph (1/Generality = 0.4) corresponds to a set with 7 images containing text and 7 images not containing text. In order words, the left most value is calculated using only the first column of images in figure 4, and as we traverse the x-axis to left, lowering generality, more and more non-text images taken from column 2 of figure 4 are added to the dataset. As we can see, object recall stays constant, since adding non-text images does not add any new ground truth images. However, precision decreases due to false alarms. We note that the graphs for algorithm 2 are flatter, illustrating the fact that this algorithm produces less false alarms in images not containing text -confirmed by [START_REF] Wolf | Extraction and Recognition of Artificial Text in Multimedia Documents[END_REF], bottom: detection algorithm 2 [START_REF] Wolf | Text Detection in Images taken from Videos Sequences for Semantic Indexing[END_REF]; Left: varying constraint t r (area recall) while t p is constant and equal to 0.4, right: varying constraint t p (area precision) while t r is constant and equal to 0.8; the fact that algorithm 1 is based on the hypothesis that the images used do contain text [START_REF] Wolf | Extraction and Recognition of Artificial Text in Multimedia Documents[END_REF].

Let us recall, that the values plotted on the y-axis of the generality graphs are consolidated performance values. For each value on the x-axis, i.e. for each generality value, and for each performance measure, i.e. precision, recall and their harmonic mean, we calculate a single value as given in equations ( 13) and ( 14).

The ICDAR 2003 text detection competition results

The second dataset consists of the text detection algorithms participating at the text detection competition organized in the framework of the 7 th International Conference on Document Analysis and Recognition (ICDAR), 2003 [START_REF] Lucas | ICDAR 2003 robust reading competitions[END_REF]. Simon Lucas, the organizer of the competition, kindly provided results of the participants in XML format. The test image database consists of various images taken with digital cameras. In contrast to the 4. From top to bottom: recall, precision, harmonic mean. Left: detection algorithm 1 [START_REF] Wolf | Extraction and Recognition of Artificial Text in Multimedia Documents[END_REF], right: detection algorithm 2 [START_REF] Wolf | Text Detection in Images taken from Videos Sequences for Semantic Indexing[END_REF]; first database, these images have been acquired in relatively high resolution: the image dimensions range between 1600×1200 pixels and 1000×800 pixels.

Four participants have been evaluated: Ashida's algorithm, H.W. David's algorithm, Wolf's algorithm, and Todoran's algorithm [START_REF] Lucas | ICDAR 2003 Robust Reading Competitions: Entries, Results and Future Directions[END_REF]. The third algorithm, developed by the authors of this document, corresponds to algorithm 2 evaluated in the last section. A fifth virtual participant combines the results of the other four methods using an algorithm proposed by the organizers of the competition. Descriptions of the methods can be found in [START_REF] Lucas | ICDAR 2003 Robust Reading Competitions: Entries, Results and Future Directions[END_REF].

Figure 8 shows the performance graphs for the five contestants. The clear winner seems to be Ashida's algorithm, which shows superior recall and precision across the whole range of quality requirements. Applying the same reasoning as in the last sub section, we clearly see the two leading algorithms differ in their detection approach: while Ashida's detected rectangles tend to be too small, H.W. David's detected rectangles tend to be too large. Method ICDAR Metric (eq. ( 6)) New Metric (eq. ( 13)) In general, the performance characteristics of the detection algorithms are well illustrated by the graphs: the proportion of "recalled" objects and the proportion of false alarms is immediately visible for the quality a user might want to impose. Inflection points in the performance curves show the precision of the detection algorithm. For instance, the inflection at point t r = 0.8 of the object recall graph of Ashida's algorithm (top row, left column), illustrates the fact that most objects are detected with about 80% of the object area. If the quality constraints are further increased, the number of objects considered as detected drops.

Table 1 presents the performance values for each algorithm compared to the original metric used during the ICDAR competition, introduced in section 3. The ranking of the algorithms stayed the same, although there are differences in the different performance values. More important, the interpretation of the values changes: recall according the ICDAR metric corresponds to the area recall, averaged across all images, which results in the ambiguity described in section 4. On the other hand, the new recall value corresponds to averaged object recall and may thus be interpreted as the proportion of correctly detected objects, averaged across the whole range quality constraints a user might want to impose. Precision is interpreted in a similar manner.

Discussion and Conclusion

In this paper we have presented a novel method to evaluate object detection algorithms. The proposed method is applicable to any kind of object, as long as the detection result may be represented by a list of rectangles.

We introduced diagrams containing two dimensional graphs which depict measures on object level depending on quality constraints, making easy a clear and intuitive interpretation. A clear distinction is made between a quantitative evaluation of the detection algorithm and a qualitative evaluation. The dynamics of the graphs illustrate the behavior of the detection algorithm against different quality constraints which might be imposed by a user, where inflection points correspond to the fundamental characteristics of the detection algorithm. The proposed evaluation method overcomes several shortcomings of the existing approaches, notably the ambiguity problem which follows from the direct accumulation of overlap proportions. Since the performance values are calculated on object level, a user can directly see the number of correctly detected objects and the amount of false alarms.

For the comparison of different detection algorithms we have proposed a single performance measure which is directly derived from the performance graphs. The integral of the object level performance across the full range of quality constraints gives an intuitive and objective measure of the detection algorithm's performance.

Additionally, a graph displays the dependence of the detection algorithm's performance on the generality of the test database, i.e. the amount of relevant information in the database. This often overlooked criterion significantly influences the measured performance of any object detection or information retrieval algorithm.

Our evaluation method is based on the amount of overlap between the ground truth rectangles and the result rectangles, not on the location of this overlap. In many applications, e.g. in the case of text detection, however, the amount of overlap between two rectangles is not a perceptively valid measure of quality, as can be seen in figure 9. Precision and recall are equivalent for both detection examples, but the detection shown in figure 9a might be considered as better, since the additional detected space is distributed over all sides of the ground truth rectangle.

As specified in section 4.4, in order to prevent the rejection of detection results as the one in figure 9a, the precision constraint t p is set to a very low value. This is necessary because the error surface grows with the square of the additional rectangle length (or height). However, we still might want to reject detections as the one illustrated in figure 9b.

One possibility to check whether the error space is equally distributed could be to estimate the distribution of the angles of the error pixels against the center of the ground truth rectangle. Unfortunately, the angle distribution of a perfectly aligned detection, e.g. the detection shown in figure 9a, is not a uniform distribution but a distribution resulting after a piecewise application of a tangent function. A statistical test (e.g. a Kolmogorov-Smirnov test) against such a distribution after an estimation of its parameters would be possible but not very robust.

Furthermore, a statistical test using all error pixels would be overkill given the fact that the functional form of the error distribution is known and that it depends on 4 parameters only: the absolute differences of the left (respectively right, upper and lower) coordinates of the rectangle pair. We chose therefore a simpler yet more effective method, which directly checks these parameters: the 4 values described above are checked against thresholds, which are calculated from the size of the rectangle.

In the more specific case of text detection, we are more interested in detecting a horizontal disequilibrium. Therefore, we concentrate on two of the differences measures: the absolute differences of the left (respectively right) coordinates of the rectangles to match need to be smaller than a constraint which depends on the width of the ground truth rectangle. This constraint, which does not depend on the overlap information, makes sure that a situation depicted in figure 9b is unlikely to occur.

Figure 1 :

 1 Figure 1: The different levels of evaluation for the example of text detection: (a) evaluation of the non-thresholded filter results (b) evaluation of the pixel classification results (c) evaluation on object level (d) goal oriented evaluation (depends on the application).

Figure 2 :

 2 Figure 2: Different match types between ground truth rectangles and detected rectangles: (a) one-to-one match; (b) a split: a one-to-many match with one ground truth rectangle; (c) a merge: a one-to-many match with one detected rectangle.

  e. the measures related to goal (1): R OB = N.o. correctly detected rectangles N.o. rectangles in the database P OB = N.o. correctly detected rectangles Total n.o. detected rectangles

Figure 2c illustrates this situation.

  Figure 2c illustrates this situation.

Figure 3 :

 3 Figure 3: An example rectangle detected with area recall = 100% and area precision = 50%.

Figure 4 :

 4 Figure 4: Some detection examples: (a) detection algorithm 1 [23] (b) detection algorithm 2 [22].

Figure 5 :

 5 Figure5: Results on the images shown in figure4. Top: detection algorithm 1[START_REF] Wolf | Extraction and Recognition of Artificial Text in Multimedia Documents[END_REF], bottom: detection algorithm 2[START_REF] Wolf | Text Detection in Images taken from Videos Sequences for Semantic Indexing[END_REF]; Left: varying constraint t r (area recall) while t p is constant and equal to 0.4, right: varying constraint t p (area precision) while t r is constant and equal to 0.8;

Figure 6 :

 6 Figure6: Results on the images shown in figure4. From top to bottom: recall, precision, harmonic mean. Left: detection algorithm 1[START_REF] Wolf | Extraction and Recognition of Artificial Text in Multimedia Documents[END_REF], right: detection algorithm 2[START_REF] Wolf | Text Detection in Images taken from Videos Sequences for Semantic Indexing[END_REF];

Figure 7 :

 7 Figure 7: Results on the images shown in figure 4, with varying generality: (a) detection algorithm 1 [23] (b) detection algorithm 2 [22].

Figure 8 :Figure 9 :

 89 Figure 8: Results on the ICDAR 2003 data set. Top row: Ashida's algorithm, 2 nd row:H.W.David's algorithm; 3 rd row: our algorithm; 4 th row: Todoran's algorithm; Bottom row: combined result; Left: varying constraint t r (area recall) while t p is constant and equal to 0.4, right: varying constraint t p (area precision) while t r is constant and equal to 0.8;

  If a non-linear decision function is used, e.g. by employing a MLP or kernel based classifier, then other distance measures are necessary. However, this is beyond the scope of this article.

	Classification at pixel level Once the classification decision for each pixel is avail-
	able, i.e. we know for each pixel whether it belongs to the object or not, the
	measures of recall and precision may be applied on pixel level:
	R P X =	N.o. correctly detected object pixels N.o. object pixels
	P P X =	N.o. correctly detected object pixels Total n.o. pixels classified as "object"

Table 1 :

 1 Single performance values on the ICDAR 2003 data set.

		Recall Precision H.Mean Recall Precison H.Mean
	Ashida	46.0	55.0	50.0	41.7	55.3	47.5
	H.W. David	46.0	44.0	45.0	46.6	39.6	42.8
	Wolf et al.	44.0	30.0	35.0	44.9	19.4	27.1
	Todoran	18.0	19.0	18.0	17.9	14.3	15.9
	All combined N/A	N/A	N/A	50.1	53.1	51.7

The work presented in this article has been conceived in the framework of two industrial contracts with France Télécom in the framework of the projects ECAV I and ECAV II with respective numbers 001B575 and 0011BA66.

http://www-nlpir.nist.gov/projects/trecvid

We should emphasize, that a comparison of the rectangles representing objects is not the same as comparing the objects themselves, since the rectangle based algorithm assumes that the object is

The approach should provide a qualitative evaluation: it should give an easy interpretation of the detection quality.

It should support one-to-one matches, one-to-many matches and many-to-one matches (splits and merges).

The measure must scale up to multiple images without losing its power and ease of interpretation.

The Institut National de l'Audiovisuel (INA) is the French national institute in charge of the archive if the public television broadcasts. See http://www.ina.fr