Basura Fernando

Elisa Fromont

Tinne Tuytelaars

Effective Use of Frequent Itemset Mining for Image Classification

In this paper we propose a new and effective scheme for applying frequent itemset mining to image classification tasks. We refer to the new set of obtained patterns as Frequent Local Histograms or FLHs. During the construction of the FLHs, we pay special attention to keep all the local histogram information during the mining process and to select the most relevant reduced set of FLH patterns for classification. The careful choice of the visual primitives and some proposed extensions to exploit other visual cues such as colour or global spatial information allow us to build powerful bag-of-FLH-based image representations. We show that these bag-of-FLHs are more discriminative than traditional bag-ofwords and yield state-of-the art results on various image classification benchmarks.

Introduction

Even though frequent itemset mining techniques (FIM) and variants thereof are well-established in the data-mining community [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF][START_REF] Uno | Lcm: An efficient algorithm for enumerating frequent closed item sets[END_REF], they are, to date, not commonly used in state-of-the-art image classification methods. This is surprising, since it has been shown that these mining methods allow the construction of high-level sets of compound features which can, in many cases, capture more discriminative information [START_REF] Cheng | Discriminative frequent pattern analysis for effective classification[END_REF]. Nevertheless, most attempts so far applying FIM to image classification [START_REF] Nowozin | Weighted substructure mining for image analysis[END_REF][START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF][START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF] were not able to demonstrate competitive results on standard datasets. In this paper, we propose a new and effective scheme for applying FIM to image classification by adapting the generic FIM tools to the specific context of visual features extracted from images.

In most state-of-the art image classification methods, images are represented with bag-of-visual-words (BOW), i.e. histograms over vector-quantised local features [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF]. These can be computed either globally (BOW) or locally in a neighbourhood around an interest point (LBOW, e.g. [START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Agarwal | Multilevel image coding with hyperfeatures[END_REF][START_REF] Sivic | Video data mining using configurations of viewpoint invariant regions[END_REF]). In the context of FIM-based image classification, local bag-of-words are usually preferred, since they result in sparse representations, a better signal-to-noise ratio and an increased robustness to image clutter. But before FIM can be applied, these bags (histograms) need to be converted into sets of items known as transactions. Usually [START_REF] Nowozin | Weighted substructure mining for image analysis[END_REF][START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Sivic | Video data mining using configurations of viewpoint invariant regions[END_REF][START_REF] Yuan | Mining compositional features for boosting[END_REF], this is done by considering each visual word as an item, ignoring how many times it appears in the bag (i.e. only considering the absence/presence of the visual word). This can lead to a loss of information.

Moreover, FIM typically generates a large number of patterns, of which only a subset is relevant for classification. Relevant pattern discovery is studied in the data mining community for the case where each transaction is generated from a different source [START_REF] Cheng | Discriminative frequent pattern analysis for effective classification[END_REF][START_REF] Cheng | Direct discriminative pattern mining for effective classification[END_REF]. However, when using local bag-of-words to create transactions, each source (image) generates multiple transactions and a pattern that is found only in a relatively small number of images can still be frequent. Applying standard relevant pattern discovery methods under these circumstances [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF][START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Gilbert | Fast realistic multi-action recognition using mined dense spatio-temporal features[END_REF] may not be the best strategy.

In this paper we also start from the local bag-of-words representation. Our three major contributions are the following: Firstly, we propose a method for histogram mining that discovers a novel set of local patterns called Frequent Local Histograms or FLH s, avoiding the loss of information during the conversion to transactions. We experimentally show that using less discriminative visual primitives and including histograms extracted from larger neighbourhoods result in larger and more discriminative FLH patterns. Secondly, we propose a new relevant pattern mining method to select discriminative, representative and nonredundant FLH patterns taking into account the fact that each image generates multiple transactions. Using this selected set of FLH patterns, we build a new image representation called bag-of-FLHs and we propose a suitable kernel for classification. The bag-of-FLHs creation process is shown in Figure 1. Thirdly, we propose a couple of variants to our basic scheme, integrating additional visual cues such as colour or global spatial information. The novel bag-of-FLHs and its variants yield powerful image representations, leading to state-of-the-art results on various image classification datasets.

The rest of the paper is organised as follows. First, we review related work in section 2. Section 3 provides details on the construction of relevant FLHs and shows how they can be used for image classification. In Section 4 we show how additional visual cues can be incorporated. Section 5 describes the experimental validation, demonstrating the power of our method for challenging image classification problems. Finally, Section 6 concludes the paper.

Related work

Frequent pattern mining techniques have been used to tackle a variety of computer vision problems, including image classification [START_REF] Nowozin | Weighted substructure mining for image analysis[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Yuan | Mining discriminative co-occurrence patterns for visual recognition[END_REF][START_REF] Kim | Disiclass: discriminative frequent pattern-based image classification[END_REF], action recognition [START_REF] Quack | Video mining with frequent itemset configurations[END_REF][START_REF] Gilbert | Fast realistic multi-action recognition using mined dense spatio-temporal features[END_REF], scene understanding [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF], object recognition and object-part recognition [START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF]. Apart from the application, these methods mostly differ in the image representation used, the way they select relevant or discriminative patterns, and the way they convert the original image representation into a transactional description suitable for FIM techniques.

Image representations

In [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF], Yao et al. present a structured image representation called group-lets. To find discriminative group-lets, they mine for frequent class association rules. Most other methods [START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Sivic | Video data mining using configurations of viewpoint invariant regions[END_REF][START_REF] Kim | Disiclass: discriminative frequent pattern-based image classification[END_REF][START_REF] Quack | Video mining with frequent itemset configurations[END_REF] start from local bag-ofwords as image representations. Spatial configuration mining based on LBOW was shown by Quack et al. [START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF], but they did not use these configurations for classification. More structured patterns such as sequences and graphs capturing the spatial distribution of visual words have been used by [START_REF] Nowozin | Weighted substructure mining for image analysis[END_REF], while [START_REF] Yuan | Mining compositional features for boosting[END_REF] uses boosting on top of binary sets of visual words discovered by FIM. Gilbert et al. [START_REF] Gilbert | Fast realistic multi-action recognition using mined dense spatio-temporal features[END_REF] have applied itemset mining to action recognition using rather primitive features like corners, while in [START_REF] Yuan | Mining discriminative co-occurrence patterns for visual recognition[END_REF] high level features such as attributes [START_REF] Farhadi | Describing objects by their attributes[END_REF] are successfully used with mining techniques.

Mining relevant patterns With an appropriate selection criterion, frequent patterns can be more discriminative than individual features (e.g. visual words), since a pattern is a combination of several primitives and therefore likely to capture more of the underlying semantics of the data. However, many works applying FIM in computer vision ignore issues such as redundancy and (lack of) repeatability across images of the mined patterns. They use simple class-based association rules [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF][START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Gilbert | Fast realistic multi-action recognition using mined dense spatio-temporal features[END_REF][START_REF] Quack | Video mining with frequent itemset configurations[END_REF] or other supervised methods [START_REF] Nowozin | Weighted substructure mining for image analysis[END_REF][START_REF] Yuan | Mining compositional features for boosting[END_REF]. In [START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF], Yuan et al. present a semantically meaningful visual pattern mining algorithm based on a likelihood ratio test to find relevant patterns in an unsupervised manner. However, none of these works considers the issue of repetitive structures in images, causing frequent yet not representative patterns.

Transforming bags to transactions As indicated earlier, most methods simply use individual visual word as an item in a transaction. Transactions are created in such a way that if a visual word is present in the histogram, then it is also present in the transaction (i.e. an itemset). In [START_REF] Kim | Disiclass: discriminative frequent pattern-based image classification[END_REF], Kim et al. use a new representation called Bag-to-set (B2S) to transform a histogram into a transactional form without loosing information. The B2S representation is, to our knowledge, the only unsupervised effort to explicitly avoid information loss in the conversion to transactions. However it can generate artificial visual patterns that do not exist in the image database. Another possibility could be to give each visual word a weight depending on how many times it appears in the histogram and apply weighted itemset mining [START_REF] Yun | Wfim: Weighted frequent itemset mining with a weight range and a minimum weight[END_REF]. However, this method only postpones the loss of information instead of really solving it, as it then simply sums all the itemset weights together to discover useful patterns.

Spatial configurations without mining Apart from pattern mining techniques, other methods have been proposed to exploit local spatial information as well. However, most of them are limited to the use of pairs or triplets of features. Only a few have used higher-order statistics (co-occurrence of visual words), either on a single image [START_REF] Yang | Spatial pyramid co-occurrence for image classification[END_REF] or pairs of images [START_REF] Zhang | Efficient kernels for identifying unbounded-order spatial features[END_REF]. Unlike FIM, they do not exploit database-wide statistics. FLH patterns are also somewhat similar to the mid-level features learnt by [START_REF] Boureau | Learning mid-level features for recognition[END_REF]. However, FLH patterns are loosely coupled to the local geometry and robust to spatial deformations, occlusions and image clutter.

Also related is the work on hyper-features of Agarwal and Triggs [START_REF] Agarwal | Multilevel image coding with hyperfeatures[END_REF]. Like us, they start from local-bag-of-words but cluster them recursively (in a hierarchical fashion) to find a new set of spatial features called hyperfeatures. Then they represent each image as a bag-of-hyperfeatures. While this also captures larger patterns, it does not have the same flexibility in local geometry as our scheme.

FLH-based Image Representation and Classification

After introducing some notations, we explain how we mine frequent local histograms (FLHs) (section 3.1). We then show how we select the most relevant set of FLHs for image classification (section 3.2) and present a suitable kernel for frequent relevant pattern-based image classification (section 3.3).

Each image I is described by a set of key points {f i |i = 1 . . . n I } and a class label c, c ∈ {1 . . . C}. We assume that all the descriptors have been clustered to obtain a set of so-called visual words. Then, each key point f i is given a label w i ∈ W known as the visual word index. |W | is the visual word dictionary size. In our approach, for each key point f i we compute a local histogram also called a local bag-of-words (LBOW), x i ∈ N |W | using the K nearest neighbours of f i (based on the distance between image coordinates and also including f i itself as a neighbour). The set of all the local histograms x i created from all images is denoted by Ω.

Frequent local histogram mining

Items, Transactions and Frequencies : In order to avoid loss of information during the transaction creation process we propose the following new definition of an item. An item is defined as a pair (w, s), w ∈ W and s ∈ N, with s being the frequency of the visual word w in the local histogram. Note that 0 < s ≤ K. We define Γ as the set of all possible items, so |Γ | = K • |W |. We create the set of transactions X from the set of local histograms Ω. For each x ∈ Ω there is one transaction x (i.e. a set of items). This transaction x contains all the items (w j , s j ) such that the bin corresponding to w j in x has the nonzero value s j . A local histogram pattern is an itemset t ⊆ Γ . For any local histogram pattern t, let X(t) = {x ∈ X|t ⊆ x} be the set of transactions that include the pattern t. The frequency of t is |X(t)| also known as the support of the pattern t or supp(t).

Frequent Local Histogram : For a given constant T , also known as the minimum support threshold, a local histogram pattern t is frequent if supp(t) ≥ T . Two patterns t and t are said to be equivalent if X(t) = X(t ). This implies that supp(t) = supp(t'). Each collection of equivalent patterns forms an equivalent class. The largest element (i.e. the one with the highest number of items) of an equivalent class is called a closed pattern. The set of frequent closed patterns is a compact representation of the frequent patterns (i.e we can derive all the frequent patterns from the closed frequent ones). In this work we refer to a frequent and closed local histogram pattern as a Frequent Local Histogram or FLH. Υ is the set of all FLHs.

FLH Mining: We can use any existing frequent mining algorithm to find the set of FLHs Υ . What is specific to our method is that i) the input of our algorithm is a set of local histograms Ω, and ii) a preprocessing step is performed building the set of transactions X from the local histograms x i as described above. Items (w k , s k ) in a transaction x ∈ X can then be regarded as standard items in itemset mining. To directly mine closed frequent histogram patterns we use the optimised LCM algorithm [START_REF] Uno | Lcm: An efficient algorithm for enumerating frequent closed item sets[END_REF].

Encoding local-bag-of-words using FLH: Given a key point, we compute a LBOW around it, considering its K nearest neighbours. Given this LBOW x, we convert it into a transaction x and check for each FLH pattern t ∈ Υ whether t ⊆ x. If t ⊆ x is true, then x is an instance of the FLH pattern t. The frequency of a pattern t in a given image I j (i.e., the number of instances of t in I j ) is denoted as F (t|I j ).

Finding the best FLHs for image classification

We want to use the FLH set Υ as a new set of mid-level features to represent an image. However, we first need to select the most useful FLH patterns from Υ because i) the number of generated FLH patterns is huge (several millions) and ii) not all discovered FLH patterns are equally relevant for the image classification task. Usually, relevant pattern mining selects those patterns that are discriminative and not redundant. On top of that, we introduce a new selection criterion, representativity, that takes into account that, when using LBOW, a single image generates multiple transactions. As a result, some patterns may be frequent and considered discriminative but they may occur in very few images (e.g. due to repetitive structures). We believe that such features are not representative and therefore not the best choice for image classification. A good FLH pattern should be at the same time discriminative, representative and non-redundant. In this section we discuss how we select such patterns.

Relevance criterion: We use two criteria for pattern relevance: a discriminativity score D(t) [START_REF] Cheng | Discriminative frequent pattern analysis for effective classification[END_REF] and a new representativity score O(t). The overall relevance of a pattern t is denoted S(t) where S(t) = D(t) × O(t). We claim that if a pattern t has a high relevance score S(t), it is likely to be discriminative and repeatable across images, hence suitable for classification.

Discriminativity score: To find discriminative patterns, we follow the entropybased approach of [START_REF] Cheng | Discriminative frequent pattern analysis for effective classification[END_REF], where a discriminativity score D(t) (0 ≤ D(t) ≤ 1) for pattern t is defined as :

D(t) = 1 -c p(c|t) • log p(c|t) log C , (1)
with p(c|t) the probability of class c given the pattern t, computed as follows :

p(c|t) = N j=1 F (t|I j ) • p(c|I j ) N i=1 F (t|I i ) . (2)
Here, I j is the j th image and N is the total number of images in the dataset. p(c|I) is 1 if the class label of I j is c and 0 otherwise. A high value of D(t) implies that the pattern t occurs only in very few classes. Note that in Eq. 1, the term log C is used to make sure that 0 ≤ D(t) ≤ 1.

Representativity score: We compare the distribution of the patterns over all the images with the optimal distribution with respect to a class c. This optimal distribution is such that i) the pattern occurs only in images of class c, i.e. P (c|t * ) = 1 (giving also a discriminativity score of 1), and ii) the pattern instances are equally distributed among all the images of class c, i.e. ∀I j , I k in class c, p(

I j |t * ) = p(I k |t * ) = (1/N c )
where N c is the number of images of class c. To find patterns with distributions close to the optimal one, we define the representativity score of a pattern t denoted by O(t). It considers the divergence between the optimal distribution P (I|t * c ) and P (I|t), and then takes the best match over all classes:

O(t) = max c (exp -[D KL (P (I|t * c )||P (I|t))]) (3)
where D KL (.||.) is the Kullback-Leibler divergence between two distributions, P (I|t * c ) is the optimal distribution for the class c and P (I|t) is the distribution for pattern t. P (I|t) is computed empirically from the frequencies F (t|I j ) of the pattern t.

Redundant patterns:

We propose to remove redundant patterns in order to obtain a compact representative set of FLHs. We take a similar approach as in [START_REF] Yan | Summarizing itemset patterns: a profile-based approach[END_REF] to find affinity between patterns. Two patterns t and s ∈ Υ are redundant if they follow similar document distributions, i.e if P (I|t) ≈ P (I|s) ≈ P (I|{t, s}) where P (I|{t, s}) gives the document distribution given both patterns {t, s}. We define the redundancy R(s, t) between two patterns s, t as follows :

R(s, t) = exp -[p(t) • D KL (P (I|t)||P (I|{t, s})) + p(s) • D KL (P (I|s)||P (I|{t, s}))]
(4) Note that 0 ≤ R(s, t) ≤ 1 and R(s, t) = R(t, s). For redundant patterns, D KL (P (I|t)||P (I|t, s)) ≈ D KL (P (I|s)||P (I|t, s)) ≈ 0 which increases the value of R(s, t).

Finding the most suitable patterns for classification: We are interested in finding the most suitable pattern subset χ where χ ⊂ Υ for classification. To do this we define the gain of a pattern t denoted by G(t) s.t. t / ∈ χ and t ∈ Υ as follows:

G(t) = S(t) -max s∈χ {R(s, t) • min(S(t), S(s))} (5)
In Eq. 5, a pattern t has a higher gain G(t) if it has a higher relevance S(t) (i.e. it is discriminative and representative) and if the pattern t is non redundant with any pattern s in set χ (i.e. R(s,t) is small ). To find the best k number of patterns we use the following greedy process. First we add the most relevant pattern to the relevant pattern set χ. Then we search for a pattern with the highest gain (non redundant but relevant) and add this pattern into the set χ until k number of patterns are added (or until no more relevant patterns can be found).

Kernel function for effective pattern classification

After computing the k most relevant and non-redundant FLHs, we can represent each image using a new representation called bag-of-FLHs by counting the occurrences of such FLHs in the image. Let L be such a bag-of-FLHs for the image I L and M be the bag-of-FLHs for the image I M . We propose to use the kernel function K(L, M ) = i min( L(i), M (i)) to find the similarities between the bag-of-FLHs of L and M . This kernel provides good classification accuracies for frequent pattern-based image representation. It is a standard histogram intersection kernel but with non-linear weighting. This reduces the importance of highly frequent patterns and is necessary since there is a large variability in pattern frequencies. Similar power-low normalization methods are used in improved Fisher-Vector based methods [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF].

Extending FLH

Exploiting both local and global spatial information using FLH: In order to take advantage of both global and local spatial information, we extend the FLH mining process. We build on the spatial pyramid idea [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] and apply it in our FLH mining framework. First we create LBOW for all features in the image. Then we discover grid-specific relevant FLHs by employing the process described in Section 3.2. Then, for each image, we concatenate these grid-specific bag-of-FLH representations to create a new representation called GRID-FLH. The GRID-FLH is a more structured local-global representation with a lot of flexibility.

Combining multiple cues using FLH:

The influence of color and shape is different for different object classes. We show two ways to fuse multiple cues such as shape and color using our FLH-based method. One way is to fuse shape-based bag-of-FLHs (denoted by F LH S ) with a color-based bag-of-FLHs (denoted by F LH C ) using a simple average Kernel. We denote this approach "F LH C +F LH S ". In the second approach, we concatenate a local color histogram with the corresponding local shape BOW and then mine the local color-shape BOW. After that we represent an image using a bag-of frequent local color-shape histograms.

We call this approach F LH CS . The advantage of F LH CS is that both color and shape information are fused spatially in local neighbourhoods. This allows us to discover useful combinations of local color-shape patterns with a high degree of flexibility.

Experimental Setup and Evaluations

In this section we introduce the datasets used to evaluate our F LH-based method; we compare our method with the most relevant baselines; and we present an analysis on parameter selections and design choices. Finally we compare the extensions proposed in Section 4 with the state-of-the-art.

Datasets and evaluation criteria

We evaluate the new bag-of-FLH (hereafter denoted by just FLH) approach on several challenging natural image datasets: GRAZ-01 [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF], Oxford-Flowers 17 [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF], 15-Scenes [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] and the PASCAL-VOC2007 dataset [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF]. Details of these datasets and evaluation criteria are summarised in Table 1.

For all experiments (and all the datasets), we start from SIFT descriptors [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] densely sampled over the image with 16 × 16 patches and a grid spacing of 8 pixels. For the Oxford-Flower dataset we experiment not only with SIFT but also with the ColorName descriptors of [START_REF] Van De Weijer | Applying color names to image description[END_REF]. We use the K-means algorithm to create visual dictionaries and LIBSVM3 to train an SVM using a constant cost parameter (C = 1). For our methods, the kernel used is the one presented in Section 3.3.

Comparison with baseline methods

We compare our FLH -based method using some default settings with BOWbased image classification, spatial pyramid matching (SPM) [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], visual wordbased standard frequent itemset mining called FIM (with binarized local bag-ofwords) and the B2S [START_REF] Kim | Disiclass: discriminative frequent pattern-based image classification[END_REF] representation. We also report results for the FLH -based method combined with BOW using an average Kernel (BOW+FLH). For the other baseline methods, we use an intersection kernel. The baseline results are shown in Table 2.

FIM is comparable with SPM while B2S (which is a lossless histogram transformation approach) slightly outperforms FIM. The FLH -based method outperforms all the baseline methods. This result shows the importance of not loosing information during the transaction creation time. We believe that our FLH-based method improves the results over B2S because it does not generate artificial visual patterns (i.e. patterns not actually present in the data set) while B2S does. The combination of BOWs and bag-of-FLHs gives better results compared to all other methods and is an indication of the complementary nature of both representations. Especially the increase for the case of SIFT features on the Flowers dataset is remarkable.

Parameter selection and optimization

In this set of experiments we analyse the effect of several parameters of our method: dictionary size, SIFT feature size, and local neighbourhood size. We use a three-fold cross-validation on training data to optimize our parameters. In the remaining experiments (sections 5.4 and 5.5), we then use the found optimal parameters to test our FLH-based methods on the test sets.

Smaller dictionaries:

We first evaluate the effect of the dictionary size on our FLH -based method using the Oxford-Flower dataset. We report results for FLH and FLH+BOW with different dictionary sizes (Table 3). Note that when combining FLH and BOW we do not reduce the dictionary size for BOW. For the CN descriptor, results improve when the dictionary size is reduced. For SIFT, we see the opposite trend. However, in both cases, the results improve with reduced dictionaries for FLH+BOW, indicating that with a smaller dictionary for FLH, the complementarity to BOW increases. Smaller dictionaries reduce the discriminativity of the visual primitives. However, this does not seem to affect the discriminativity of the FLH patterns, which may even become more robust and stable. Therefore, smaller dictionaries created using even less discriminative features might be better suited for FLH. This is tested in the next experiment.

Less discriminative features:

We evaluate the effect of less discriminative features on FLH using the Oxford-Flower dataset with a small dictionary of 100 words and a local neighbourhood size of 5 (Table 4). For this we use SIF T 32 features that are extracted like the standard SIFT (referred to as SIF T 128) but performing spatial binning of (2 × 2) instead of (4 × 4). Surprisingly, FLH using the less discriminative SIF T 32 features and a smaller dictionary performs as good as the ColorName descriptor in the previous experiment (72.0% for CN and 72.7% for SIF T 32). When combined with BOW (using SIFT128 and a 800 dimensional vocabulary for the BOW) we obtain a classification accuracy of 80.7%, outperforming the ColorName descriptor.

Larger local neighbourhoods

We believe that the use of smaller dictionaries and less discriminative SIFT features allows the FLH -based method to exploit larger neighbourhoods. To evaluate this relation, we run some further experiments on the Oxford-Flower dataset -see Fig. 5. The best results are obtained when reducing both SIFT feature size and dictionary size while increasing the neighbourhood size of the local spatial histograms. The best classification accuracy we obtain with SIFT features is 91.0% for a dictionary size of 100 words, SIF T 32 features and a neighbourhood size of 25. Note that this is a larger neighbourhood size (covering up to 48×48 pixels) than what is typically used in the literature [START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Gilbert | Fast realistic multi-action recognition using mined dense spatio-temporal features[END_REF].

We can conclude that the FLH -based method obtains its best results when exploiting larger local patterns with smaller dictionaries and less discriminative features. From now on, for all FLH -based experiments we propose to use the SIFT32 descriptor and a neighborhood size of 25 neighbours. For Oxford-Flower and PASCAL-VOC2007 datasets a SIFT32 dictionary of 100 words is used. For all other datasets we propose to use a SIFT32 dictionary of 25 words.

Effect of relevant pattern mining and of the kernel functions

FLH mining algorithms can generate a large number of FLH patterns (in our case, 1-20 million). Some of these patterns are not relevant for classification. Therefore, we select the most relevant-non-redundant ones, as described in Section 3.2. Here we evaluate the importance of this pattern selection step by comparing different criteria: the most frequent (Frq.), the most representative-nonredundant(Rps.)(eq. 3), the most discriminative-non-redundant (Disc.)(eq.1) and the most relevant-non-redundant (Rel.) (i.e. representative, discriminative and non-redundant) patterns (see Table 6). We always select the top 10.000 patterns for each criterion which we believe is sufficient to obtain good results. These results clearly show that only selecting the top-k most frequent patterns (as usually done) is not a good choice for classification. Both representativity and discriminativity criteria alone also do not provide the best results. It's the relevant non-redundant FLH patterns that are the most suitable for classification. Some of these relevant and non-redundant FLH patterns are shown in Fig. 2. These selected FLH patterns are semantically meaningful and capture most of the relevant shape information in an image.

In Table 7, we evaluate the effect of the square root intersection kernel using relevant non-redundant FLH patterns on Oxford-Flower and 15-Scenes. The proposed square-root weighting increases in both the linear kernel and the nonlinear intersection kernel the classification accuracy for both datasets.

Comparison to state of the art methods

In this section we compare FLH using the parameters optimised as above with, to the best of our knowledge, the best results reported in the literature. Here, we also evaluate the extensions proposed in section 4, integrating shape and color information, or local and global spatial information. Oxford-Flower: The results are reported in Table 9. Note that only using shape information (SIFT32 features) we get a classification accuracy of 92.5%, outperforming the state-of-the-art. Combining color and shape information further improves these results to 94.5 ± 1.5 (using F LH CS + SIFT-128 dictionary of 800 and ColorName dictionary of 300 words). Adding global spatial information on this dataset only gives an insignificant improvement of 0.4%.

15-Scenes:

Results are shown in table 10. This dataset is strongly aligned. FLH does not exploit this and therefore by itself cannot obtain state-of-the-art results. However, the GRID-FLH method described in section 4 does take the global spatial information into account and achieves close to state-of-the-art results (86.2%). This is only outperformed by [START_REF] Yuan | Mining discriminative co-occurrence patterns for visual recognition[END_REF] who report 87.8% using CENTRIST and SIFT features along with LLC coding. However, our method uses only simple SIFT features. As far as we know the previous best classification accuracy using SIFT features was reported by Tuytelaars et al. in [START_REF] Tuytelaars | The nbnn kernel[END_REF] combining a NBNN kernel and a SPM method.

Pascal-VOC2007: Results are reported in Table 11. FLH alone gives a mAP of 60.4. In combination with BOW of SIFT-128 and 5000 visual word vocabulary, we obtain a state-of-the-art mAP of 62.8. Note that the score for each individual class often varies a lot between the FLH+BOW and the Fisher Vector [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] method. Our method does especially well on what are known to be 'hard' classes: bottle (+34% improvement), dining table (+11%), potted plant (+16%), tv monitor (+23%). This suggests that both methods are complementary.

Conclusion

In this paper we show an effective method for using itemset mining to discover a new set of mid-level features called Frequent Local Histograms. Extensive exper- [START_REF] Tuytelaars | The nbnn kernel[END_REF] (AND/OR) [START_REF] Yuan | Mining discriminative co-occurrence patterns for visual recognition[END_REF] F LH FLH+BOW GRID-FLH 80.9 82.5 85.0 87.8 70.9 ± 0.4 83.0 ± 0.5 86.2 ± 0.4 Class FV [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF][START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] iments have proved that the proposed bag-of-FLH representation, the proposed relevant pattern mining method and the chosen kernel all improve the classification results on various datasets. We have also experimentally shown that the best results for FLH methods are obtained when exploiting a large local neighbourhood with a small visual vocabulary and less discriminative descriptors. Finally, we have shown that extending a local approach such as FLH to exploit other cues such as global spatial information or colour information allows us to obtain state-of-the-art results in many datasets. As future work we propose to investigate how to push the relevant and non redundant constraints directly into the local histograms mining process to make it particularly efficient.

Fig. 1 .

 1 Fig. 1. FLH mining and image representation

Fig. 2 .

 2 Fig.2. FLH patterns using shape information where each red dot represents the central location and the blue square represents the size of the FLH pattern Table1. Datasets

  78.8 67.4 51.9 70.[START_REF] Agarwal | Multilevel image coding with hyperfeatures[END_REF] 30.8 72.2 79.9 61.4 56.0 49.6 FLH 67.9 70.6 41.0 54.6 64.9 60.9 85.8 56.6 59.6 40.0 FLH+BOW 69.2 73.0 42.7 56.3 64.9 60.9 86.6 58.9 63.3 41.8 Class m.AP FV[23, 34] 58.4 44.8 78.8 70.8 85.0 31.7 51.0 56.4 80.2 57.5 61.7 FLH 64.7 47.3 56.6 65.7 80.7 46.3 54.6 71.0 77.6 60.4 FLH+BOW 74.3 48.4 61.8 68.4 81.2 48.5 41.8 60.4 72.1 80.8 62.8

Table 1 .

 1 Datasets

	Criterion

Dataset

# Classes # Train. Imgs per class # Test. Imgs per class Evaluation

Table 2 .

 2 Comparison with baseline methods. Classification accuracies for GRAZ-01 and Oxford-Flower for a local neighbourhood size of K=5. Flower-(SIFT) 200 56.4 ± 2.5 57.3 ± 2.3 54.7 ± 2.6 55.3 ± 2.9 59.0 ± 3.4 71.1 ± 2.4 Flower-(CN) 100 59.4 ± 1.7 61.5 ± 1.6 61.5 ± 2.7 62.4 ± 2.4 69.5 ± 2.5 72.9 ± 2.4

		Dict.	Baselines		Mining Methods
		size BOW	SPM	FIM	B2S	FLH	FLH + BOW
	GRAZ-Person 200 79.4 ± 1.1 79.7 ± 1.4 80.5 ± 2.2 81.8 ± 2.1 83.5 ± 1.8 84.0 ± 1.6
	GRAZ-Bike	200 76.8 ± 2.5 79.6 ± 2.1 78.0 ± 2.1 78.4 ± 1.9 81.3 ± 2.4 82.5 ± 2.2

Table 3 .

 3 The effect of dictionary size on FLH-based methods. Classification accuracy on Oxford-Flowers training data using cross-validation.

	Descriptor Dict. Size FLH	FLH + BOW Descriptor Dict. Size FLH	FLH + BOW
	SIFT	800	64.4 ± 2.9 64.8 ± 2.9	CN	300	69.1 ± 2.4 70.4 ± 2.2
	SIFT	200	56.2 ± 2.7 68.9 ± 2.7	CN	100	69.9 ± 2.1 71.1 ± 2.4
	SIFT	100	54.7 ± 2.6 70.3 ± 2.8	CN	20	72.0 ± 1.9 76.2 ± 2.3

Table 4 .

 4 Effect of SIFT feature size on FLH. Classification accuracy on Oxford-Flowers training data using cross-validation.

	SIFT-D Dict. Size FLH	FLH + BOW
	128	100	54.7 ± 2.6 70.3 ± 2.8
	32	100	72.

7 ± 1.8 80.7 ± 1.4

Table 5 .

 5 Effect of neighbourhood size(K), dictionary size (|W |) and SIFT descriptor size (B ) on classification accuracy for the Oxford-Flower training data using cross-validation.

Table 6 .

 6 Effect of relevant pattern mining using SIFT-32

	Criterion Frq. Rps. Disc. Rel.
	GRAZ-01 83.1 90.3 90.9 91.6
	Flower	65.6 84.2 90.9 92.5

Table 7 .

 7 Effect of the choice of the kernel in pattern classification using SIFT-32

	K(x, y) = x.y t √	x. √ y t P	i min(x i , y i )	P i min(	√ x i ,	√ y i )
	15-Scenes 80.4 81.3	85.9	86.2
	Flower	89.5 92.0	91.2	92.5

Table 8 .

 8 Equal Error Rate (over 20 runs) for categorization on GRAZ-01 dataset

		State-of-the-art			Our results
	Class SP CK+ [19] NBNN[30] HF[20]	FLH	FLH+BOW GRID-FLH
	Person	87.2	87.0	84.0 94.0 ± 1.8 95.0 ± 1.6 95.8 ± 1.8
	Bike	91.0	90.0	94.0 89.2 ± 1.6 90.1 ± 1.8 91.4 ± 1.1
	AVG.	89.1	88.5	89.0	91.6	92.6	93.8

Table 9 .

 9 Classification accuracy (over 20 runs) on the Flower dataset The results reported in Table8show that on average all FLH -based methods outperform the state-of-the-art. The GRID -F LH representation, combining local and global spatial information, yields the best results.

	Our results Using Shape -SIFT	Our results Using Color -ColorName
	F LH	F LH + BOW GRID -F LH F LH	F LH + BOW GRID -F LH
	92.5 ± 1.6 92.7 ± 1.2	92.9 ± 1.6	72.1 ± 1.9	74.4 ± 2.4	74.8 ± 1.9
		State-of-the-art	Our results Using Color and Shape
	Nilsback [26] CA[31]	L 1 -BRD[32] F LH C +F LH S F LH CS	F LH CS +BOW
	88.3 ± 0.3	89.00	89.02 ± 0.60	93.0 ± 2.0	93.4 ± 1.5	94.5 ± 1.5
	GRAZ-01:

Table 10 .

 10 Results on 15-Scenes datasetState-of-the-artOur results SP M SP CK ++[START_REF] Yang | Spatial pyramid co-occurrence for image classification[END_REF] NBNN Kernel+SPM

Table 11 .

 11 Results on PASCAL-VOC 2007 (Mean average precision)

http://www.csie.ntu.edu.tw/∼cjlin/libsvm/

Acknowledgements :

The authors acknowledge the support of the IBBT Impact project Beeldcanon, the FP7 ERC Starting Grant 240530 COGNIMUND and PAS-CAL 2 network of Excellence.


Fabien Diot

Elisa Fromont

Baptiste Jeudy

Emmanuel Marilly

Olivier Martinot

Graph Mining for Object Tracking in Videos

This paper shows a concrete example of the use of graph mining for tracking objects in videos with moving cameras and without any contextual information on the objects to track. To make the mining algorithm efficient, we benefit from a video representation based on dynamic (evolving through time) planar graphs. We then define a number of constraints to efficiently find our so-called spatio-temporal graph patterns. Those patterns are linked through an occurrences graph to allow us to tackle occlusion or graph features instability problems in the video. Experiments on synthetic and real videos show that our method is effective and allows us to find relevant patterns for our tracking application.

Introduction and Related Work

Object tracking in videos is a very popular research field in computer vision due to the numerous applications such as video-surveillance in very diverse environments (airports, cities, large public areas), pedestrian protection systems, automatic calibration methods using moving robots, tracking complicated surfaces, medical image applications etc. [START_REF] Goszczynska | Object Tracking[END_REF]. Most of the ongoing research [START_REF] Yilmaz | Object tracking: A survey[END_REF][START_REF] Goszczynska | Object Tracking[END_REF] makes strong assumptions about the objects to track (people, car, etc.) which are often modelled in advance, or about the tracking context (stable background, object moving in a single direction, stable lighting conditions, etc.) to perform an efficient tracking. These methods rely on two steps, the object detection in the frame and the tracking process. For detection, techniques are based on frame difference or the use of background subtraction [START_REF] Kim | Real time object tracking based on dynamic feature grouping with background subtraction[END_REF], optical flow (detection of the relative motion between a static camera and the filmed objects) [START_REF] Sun | Secrets of optical flow estimation and their principles[END_REF] or background information on the objects to track (skin color, shape etc.). For the tracking process, techniques consist in predicting the next region (or contour) of interest using probabilistic or deterministic methods [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] (and then possibly add another detection step). They use some discriminant features attached to the objects and/or use apriori learned models of the objects which can possibly be updated during the tracking step [START_REF] Kuo | Multi-target tracking by on-line learned discriminative appearance models[END_REF].

In this work, we would like to show how data mining and in particular graph mining can help to track multiple objects in a video in the specific case in which both the objects and the background are moving and when no supervised information about the objects to track is known in advance (which could allow to learn some models apriori). We regard a video as a dynamic graph, whose evolution over time is represented by a series of plane graphs, one graph for each video frame. The graph representing each frame is a region adjacency graph (RAG) [START_REF] Chang | Region-based image retrieval using edgeflow segmentation and region adjacency graph[END_REF]. In RAGs, the barycenters of the different regions in a frame are the nodes of the graph, and an edge exists between two nodes if the regions are adjacent in the frame. By representing a video as a series of plane labelled graphs, subgraph patterns in this series may correspond to objects that frequently appear in a video, such as the planes in the frames of Fig. 4.1 and 4.1.

This paper is based on [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] where we have already assessed the interest of our plane graph mining algorithm called Plagram compared to a generic graph mining algorithm such as gSpan [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] on which it is based. Plagram can efficiently mine a dynamic graph representing a video (i.e. a plane graphs database). Note that most existing algorithms which mine dynamic graphs (e.g., dynamic networks) consider graphs with only edges insertions or deletions i.e., the time series of graphs share the same set of nodes over time (see, e.g., [START_REF] Borgwardt | Pattern mining in frequent dynamic subgraphs[END_REF]), or in which nodes and edges are only added and never deleted (see, e.g., [START_REF] Berlingerio | Mining graph evolution rules[END_REF]). In [START_REF] Celik | Mixed-drove spatiotemporal cooccurrence pattern mining[END_REF][START_REF] Yang | A generalized framework for mining spatiotemporal patterns in scientific data[END_REF], the problem is to mine spatio-temporal relationships between moving objects (the mined relationships are restricted to some predefined graphs like cliques, star graphs or sequences). In our approach, however, there is no information about the correspondence between the nodes in one graph (video frame) and those in the others. In [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF], some simple constraints were used in a post processing step to obtain some so-called spatio-temporal patterns. However, the definition of spatiotemporal patterns (and especially, of the distance) was not anti-monotonic which prevented the computation of spatio-temporal patterns during the mining step. Moreover, the spatio-temporal patterns obtained were quite small in practice which led to a low recall when using them for object tracking. In this article, we present an extended version of the plane graph mining algorithm called DyPlagram st which can benefit from the spatio-temporal constraints to directly and thus more efficiently mine the spatio-temporal patterns. Besides, we propose a method based on a global occurrences graph to combine these patterns in order to build spatio-temporal paths that can be used to follow some objects in the videos. By allowing a pattern to change along a path, it is possible to take into account instability in the video or change of view point which improves the recall of the patterns.

The tracking methods presented at the beginning of this introduction typically do not consider moving objects in changing environments. When it is the case as in [START_REF] Cai | Multi-object detection and tracking by stereo vision[END_REF], multiple cameras are used to tackle object occlusions or features instability using stereo vision. The setting taken in [START_REF] Diego | Night-time outdoor surveillance by mobile cameras[END_REF] is close to the one we are interested in since they consider cameras embedded in surveillance cars but they rely on strong background information (here GPS position) to perform an effective tracking. Our method is also similar to [START_REF] Yu | Multiple-target tracking by spatiotemporal monte carlo markov chain data association[END_REF] but they do not use the topological information provided by the subgraph patterns and they use a spatio-temporal Markov Chain Monte Carlo algorithm to sample the possible paths represented in our occurrences graph.

The outline of this paper is the following. In Section 2, we recall some important definitions and explain the proposed extensions to the DyPlagram algorithm proposed in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF]. In Section 3 we show how to compute the spatio-temporal paths used for object tracking. Section 4 shows a large set of experiments on a synthetic and on a real video to assess both the efficiency of our new algorithm DyPlagram st but also the usefulness of the spatio-temporal paths to tackle the problem of object tracking in videos. We conclude in Section 5.

Spatio-Temporal Patterns Mining

Dynamic Plane Graphs

The definitions in this section are similar to those of [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF]. As in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF], our algorithm mines 2-connected plane graphs that satisfy various spatio-temporal constraints. The restriction to 2-connected plane graphs was motivated by the use of plane graphs in our video data and because it allows to test subgraph isomorphism in polynomial time. Moreover, this restriction also dramatically decreases the branching factor of the search space and improves the efficiency (as already shown in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF]).

Definition 1 (Plane graph).

A plane graph is G = (V, E, F, f e , L) where V is a set of nodes, E is a set of edges, F is a set of faces and L is a labeling function on V ∪ E. Exactly one of the faces f e ∈ F is called the external face, the other faces are the internal faces. The graph is 2-connected if each face is a simple cycle (the face does not use a node or an edge more than once).

Our aim is to find 2-connected plane subgraphs which satisfy some constraints in a database of graphs.

Definition 2 (Plane subgraph isomorphism, occurrence). Given two plane graphs G = (V, E, F, f e , L) and G ′ = (V ′ , E ′ , F ′ , f ′ e , L ′ ), G ′ is a plane subgraph of G if there is an injective function f from V to V ′ which preserves the edges, the internal faces of G ′ and the labels. The function f is called an occurrence of G ′ in G.

The frames in a video are ordered, and this order is taken into account when computing spatio-temporal patterns. We thus define a dynamic graph as an ordered set of graphs.

Definition 3 (Dynamic plane graph).

A dynamic plane graph D is an ordered set of plane graphs {G 1 , G 2 , .., G n }. Each node of these graphs is associated to spatial coordinates (x, y).

Example 1. In our video application, each plane graph G i represents a video frame. Each node in a graph represents a segmented frame region, and is associated to the coordinates (x, y) of the barycenter of this region. The labels on nodes are built either by a discretization of the size of the regions or of the color.

We define an occurrence of a plane graph in a dynamic plane graph and its frequency.

Definition 4 (Occurrences of a plane graph in a dynamic graph). Given a plane graph P and a dynamic graph D = {G 1 , ..., G n }, the set of occurrences of P in D is defined as Occ

(P ) = {(i, f ) | f is an occurrence of P in G i }.
Definition 5 (Frequency of a plane graph in a dynamic graph). The frequency freq(P ) of a plane graph P in a dynamic graph D is the number of graphs G i ∈ D in which there is an occurrence of P , i.e., | {i | ∃f, (i, f ) ∈ Occ(P )} |.

Occurrences Graph and Spatio-Temporal Patterns

In typical subgraph mining problems, where the input collection of graphs does not represent a dynamic graph, the frequency freq(P ) of a pattern graph P is computed regardless of the fact that its occurrences may be far apart w.r.t. time and/or space. To define a frequency that takes into account spatio-temporal distance between the occurrences, we define in this section the notion of an occurrences graph in which occurrences of the same pattern that are close to one another are linked. Then, we define spatio-temporal patterns in this occurrences graph and the associated frequency (called freq st ).

The definitions in this section, although similar to the one of [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF], have been changed to integrate the spatio-temporal patterns computation during the mining step instead of during a post-processing step. This offers more pruning opportunities.

Definition 6 (Distance between occurrences). The distance between two occurrences o = (i, f ) and o ′ = (i ′ , f ′ ) of a plane graph P = (V, E, F, f e , L) in a dynamic graph D is defined as: dist(o, o ′ ) = max s∈V d(f (s), f ′ (s)), where d denote the Euclidean distance between the nodes. This distance has an anti-monotonic property: Proposition 1. For any patterns P = (V, E, F, f e , L) and P ′ = (V ′ , E ′ , F ′ , f ′ e , L ′ ) such that P is a plane subgraph of P ′ and two occurrences

o 1 = (f 1 , i), o 2 = (f 2 , i) of P and two occurrences o ′ 1 = (f ′ 1 , i), o ′ 2 = (f ′ 2 , i) of P ′ such that f 1 is a restriction of f ′ 1 (i.e., f 1 = f ′ 1 on V ) and f ′ 2 is a restriction of f 2 , then we have dist(o 1 , o 2 ) ≤ dist(o ′ 1 , o ′ 2 )
. proof (sketch): the set from which the maximum is taken for dist(o 1 , o 2 ) is included in the set for which the maximum is taken for dist(o ′ 1 , o ′ 2 ). The depth first traversal of the search space by our mining algorithm define a parent relationship on patterns: Definition 7 (Parent of a pattern and of an occurrence). Given a pattern P with n ≥ 2 internal faces, the pattern p(P ) with n -1 faces from which P was built is called the parent of P . And given an occurrence o = (f, i) of P , we call the parent of o the occurrence p(o) = (f ′ , i) such that f ′ is the restriction of f to the nodes of p(P ).

The definition of the parent of an occurrence is then used to define the occurrences graph. The nodes of the occurrences graph are the occurrences of a pattern and the edges connect "close" occurrences. This graph is constructed for each pattern in the mining algorithm.

Definition 8 (Occurrences graph and Spatio-temporal pattern). Given a spatial threshold ǫ, a temporal threshold τ , a plane graph P = (V, E, F, f e , L) and a dynamic graph D, we define the occurrences graph of P as an oriented graph whose set of nodes is Occ(P ).

-If P has only one face, then there is an edge from

(f, i) to (g, j) if 0 < j -i ≤ τ and dist(f, g) ≤ ǫ.(j -i) and there is no (h, k) with i < k < j and dist(f, h) ≤ ǫ.(k -i).
-If P has more than one face, then there is an edge from o = (f, i) to o ′ = (g, j) if there is an edge (p(o), p(o ′ )) in the occurrences graph of p(P ) and dist(f, g) ≤ ǫ.(j -i). A spatio-temporal pattern S based on P is a connected component of the occurrences graph of P .

This definition is such that the occurrences graph of a pattern P is always a subgraph of the occurrences graph of its parent pattern p(P ) (if we identify the node o of the occurrences graph of P with the node p(o) of the occurrences graph of p(P )). This ensures that the spatio-temporal patterns based on P get "smaller" as the pattern P grows, and this ensures that the frequency of a spatio-temporal pattern defined below has the anti-monotonicity property. Example 2. Fig. 1 shows 11 occurrences of a pattern P in a video with five frames. freq(P ) = 5. Since occurrences 1 and 4 are close to each other, i.e., their spatial distance is lower than 2ǫ and their temporal distance is 2 ≤ τ , there is an edge [START_REF] Yilmaz | Object tracking: A survey[END_REF][START_REF] Cai | Multi-object detection and tracking by stereo vision[END_REF] in the occurrences graph of P . Conversely, the edges [START_REF] Borgwardt | Pattern mining in frequent dynamic subgraphs[END_REF][START_REF] Celik | Mixed-drove spatiotemporal cooccurrence pattern mining[END_REF] or [START_REF] Berlingerio | Mining graph evolution rules[END_REF][START_REF] Goszczynska | Object Tracking[END_REF] do not exist in the occurrences graph, as the spatial distance between 3 and 5 or the temporal distance between 2 and 11 are too large. There are 4 spatio-temporal patterns S 1 = {1, 4, 5, 7, 8, 10}, S 2 = {3, 6, 9}, S 3 = {2} and S 4 = {11}. The frequencies of these patterns are: freq st (S 1 ) = 4, freq st (S 2 ) = 3, and freq st (S 3 ) = freq st (S 4 ) = 1.

Proposition 2. Given a pattern P with more than one face, and given a spatiotemporal pattern S based on P then there is a spatio-temporal pattern S ′ based on the parent p(P ) of P with a larger freq st , i.e., freq st (S) ≤ freq st (S ′ ).

This proposition shows that, given a minimum threshold minfreq st on freq st , if a pattern does not have a frequent spatio-temporal pattern then any superpattern does not either. This allows to prune the search space.

DyPlagram st Algorithm

Given a frequency threshold minfreq (also called minimum support), a minimum threshold minfreq st for freq st a spatial threshold ǫ and a temporal threshold τ , the proposed algorithm DyPlagram st computes all spatio-temporal patterns with freq st ≥ minfreq st based on patterns with freq ≥ minfreq (the thresholds ǫ and τ are used in the construction of the occurrences graph, see Def. 8).

The proposed algorithm DyPlagram st is based on DyPlagram [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] which itself is based on gSpan. Its main characteristics are :

a recursive depth first exploration of the search space; -the use of canonical codes to avoid considering the same graph several times; -at each level, patterns are extended by adding a whole face to the current pattern.

The new definition of the freq st is now anti-monotonic, and we can use it in the DyPlagram st algorithm. However, this frequency is not defined on patterns but on spatio-temporal patterns. We must therefore also build the occurrences graph and the spatio-temporal patterns in the algorithm.

Given an occurrence o = (f, i) of a pattern P , an extension E of P is a set of edges such that P ∪ E has exactly one more face than P and there is an occurrence o ′ = (f ′ , i) of P ∪ E that extends o, i.e., such that f is the restriction of f ′ to P .

As its predecessors, DyPlagram st uses canonical codes to represents patterns and extensions. This allows to efficiently enumerate only the so called valid extensions of a pattern. Informally, a valid extension of a pattern is an extension that lead to a pattern not already considered by the algorithm. This is a very efficient way to avoid considering several times the same pattern. We do not detail here how these codes are built, the interested reader can refer to [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF].

The DyPlagram st algorithm first builds all frequent one face patterns and then calls the following recursive function mine for all of them. mine(P, minfreq, minfreq st , τ, ǫ, D) In this algorithm, lines 1, 3, 5, 6, 7, 8, and 9 were not in DyPlagram [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF]. Thanks to Prop. 2, this algorithm is correct and output exactly the spatiotemporal patterns whose freq st is above the user defined threshold σ.

1

Spatio Temporal Path

When tracking an object in a real video, we cannot expect that the object is represented by the same graph pattern during the whole video (e.g., due to changes in view point or instability of the segmentation). Thus, if we want to track it using spatio-temporal patterns, we propose to build a path in the union of all occurrences graphs. To allow this path to "jump" from a spatio-temporal pattern to another, similarity edges are added between overlapping occurrences of different patterns. Weights are also added on the edges so that minimum weight paths can then be computed in this global occurrences graph.

Definition 10 (Similarity of two occurrences). Let o = (i, f ) and o ′ = (i, f ′ ) be two occurrences of two different patterns P = (V, E, F, f e , L) and

P ′ = (V ′ , E ′ , F ′ , f ′ e , L ′
). The similarity between these occurrences is defined as

σ(o, o ′ ) = |f (V )∩f ′ (V ′ )| |f (V )| .
This similarity is not symmetric and it is used to weight the edges in the global occurrences graph.

Definition 11 (Global occurrences graph). Given a set of patterns P, temporal and spatial thresholds τ and ε, a similarity threshold σ, the global occurrences graph is a weighted oriented graph: its node set is V = ∪ P ∈P Occ(P ) and its edge set is E = E P ∪ E sim where :

-E P is the union of the edge sets of all patterns occurrences graphs. The weight of an edge

((i, f ), (i ′ , f ′ )) is w = (i ′ -i-1) τ . -E sim = {(o, o ′ , w)| o = (i, f ), o ′ = (i, f ′ ), σ(o, o ′ ) < σ} is the set of similarity edges with w = 0 if |V | < |V ′ | 1 2 ( 1-σ(o,o ′ ) 1-σ + d ǫ ) otherwise.
where V and V ′ are the node sets of the patterns corresponding resp. to occurrences o and o ′ , and d is the distance between the barycenters of o and o ′ .

A spatio-temporal path is a path in the global occurrences graph.

The edges in E P are edges between 2 occurrences of the same pattern that are in the same frame. If these two occurrences are in consecutive frame, the weight is 0 (when i ′ = i + 1) otherwise the weight increases with the number of frames between them (normalized by the temporal threshold τ ).

The edges in E sim are similarity edges between 2 occurrences of different patterns that are in the same frame and whose similarity is below σ. We want to favor paths that use large patterns, thus the weight of an edge from an occurrence of a small pattern to a larger one is 0. The weight of an edge from an occurrence of a large pattern to a smaller one increases as the similarity decreases and the spatial distance increases.

Experiments

Some experiments in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] have already assessed the efficiency of the plane graph mining algorithm called DyPlagram compared to a generic graph mining algorithm such as gSpan [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF]. The introduction of this plane graph mining algorithm was necessary to effectively mine the graphs extracted from videos. Experiments on a very simple video (one object, moving background, no occlusion, no disappearance) showed promising results for object tracking but the interest of the spatio-temporal patterns for more complex videos was not thoroughly evaluated. Besides, in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF], we did not present an effective way to use spatio-temporal constraints in DyPlagram nor a systematic method to combine the spatiotemporal patterns into spatio-temporal paths to track object in videos. Our proposed experiments aim to answer three main questions:

1. Are the spatio-temporal constraints well exploited by the new DyPlagram st algorithm compared to the process presented in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF]? 2. How are the results of the DyPlagram st algorithm where the spatial and the temporal constraints are pushed directly into the mining process compared to the post-processing experiments described in [14]? 3. How meaningful (in terms of precision and recall) are the spatio-temporal paths to track objects in a synthetic and in a real video?

Video Datasets

We used 2 datasets for these experiments. One was created from a synthetic video which allows us to avoid the possible segmentation problems. The second comes from a real (but simple) video with its possible segmentation issues.

For both videos, we used two possible labels on the nodes of the RAGs. The first possible one comes from a discretization of the size of the segmented regions (in pixels). The discretization uses 10 bins of equal size that were computed using all the possible region sizes (sorted for the discretization) for a given video. The second is a color discretization of the mean color of the segmented regions. We divided each of the 3 RGB channels in 3 parts, resulting in 27 bins of equal range.

The synthetic video has 721 frames in total. In average the RAGs are composed of 240.7 nodes with an average degree of 3.9. Three identical objects (X-wings) are moving in the video such that they may overlap or even get (partially) out of the field of view (this helped us to evaluate how well spatio-temporal patterns can be used to represent the trajectory of the X-wings individually). The 3 X-wings have different colors but this feature is not always used in the experiments. The real video is composed of 950 frames (25 frames per second), each RAG has on average 194.5 nodes with an average degree of 5.35. This video shows a drone flying across a covered parking lot. Before building the RAGs, we segmented each frame of the video independently using the algorithm presented in [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] and available on the web3 . This algorithm has 3 parameters for which we used standard values. This algorithm helps the merging of small regions which may result in an unstable segmentation when objects are getting close to or moving away from the camera. In order to prevent this behavior, we modified the code of this algorithm to make its second parameter independent from the size of the regions.

Evaluation of the Patterns

To evaluate our spatio-temporal patterns, we use some ground truth. For both the real and the synthetic videos, we have tagged the positions of the plane(s) (objects o) in each frame of the video.

We introduce two measures which assess how precisely a spatio-temporal pattern p corresponds to a given target object o in the video frames. These measures are adaptations of the popular precision and recall measures as described below:

-precision: fraction of the occurrences of p (in the target graphs) of which every node maps to o in the corresponding video frames. The intuition behind this measure is to evaluate the purity of p, that is, p has the maximum precision if it maps only to o and nothing else. -recall: Let n be the number of frames in which o is present. The recall is defined as the fraction of n in which there exists at least one occurrence of p where every node maps to o. Here, the intuition is to evaluate the completeness of p. More precisely, the idea is to check whether the occurrences of p map to all occurrences of o in the set of video frames.

Since our algorithm is exhaustive, that is, it mines for all frequent spatiotemporal patterns in the graph database without supervision, the mining result may consist of different spatio-temporal patterns corresponding to different objects, or even to no specific one (w.r.t. the proposed measures). To be able to evaluate the precision and recall of our spatio-temporal patterns for all 3 different planes (in the synthetic video) and for the drone (in the real video), we have considered that the spatio-temporal patterns starting in every frames of the video have been tagged according to the object it belongs to. In other words, we evaluate the precision and recall of each spatio-temporal patterns knowing in advance what the first occurrence of the pattern in each occurrences graph maps to.

Spatio-Temporal Paths for Object Tracking

To assess the effectiveness of the spatio-temporal paths for object tracking, we apply the following strategy. We first build the occurrences graph and then, for each target object, we select the occurrences matching them in the first frame and compute the path of lowest cost starting from those occurrences and reaching the last frame using Dijkstra's shortest path algorithm. In all experiments reported here we use a similarity of 2/3 (σ = 0.65).

In practice the minimum support threshold minfreq can be set, for example, to 1/5 of the total number of frames (to make sure that the patterns occur enough and help the mining process). By default, it will be equal to the minfreq st threshold. minfreq st should be set as low as possible (depending on available memory). The τ should, in general, be set as high as possible (as will be shown in the experiments). The ǫ constraint depends on the motion speed of the target object and on the resolution of the video. We most of the time use 20 pixels.

DyPlagram st vs DyPlagram

The experiments showed in Table 1 allow us to compare the DyPlagram algorithm presented in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] with our new upgraded algorithm, DyPlagram st, which uses the spatial and the temporal constraints directly in the mining process. These experiments are made with the same synthetic video as in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] and the same discretization procedure which uses only the size of the region. The same minimum support (minfreq = 721) has been used as well as the same gap constraint τ = 1 as in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF]. The minfreq seq threshold used in DyPlagram to prune part of the search space is not used by DyPlagram st which uses a different minfreq st threshold (explained in Sec. 2.2). However, in these experiments, we set the same threshold for freq seq and freq st . Note that the results for DyPlagram are not exactly the ones reported in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] because we found that the strategy proposed in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] was overly optimistic as far as precision was concerned. Indeed, the chosen spatio-temporal patterns (i.e., the connected components (CC)) were the ones for which the first occurrence matched a pattern that was selected in the first frame of the video. This means that a spatio-temporal pattern that also matched a chosen object but for which the first occurrence belongs to a pattern that was not selected in the first frame would not be taken into account to com- pute the precision of this object. Here we compute the precision and recall for all the CC whose first occurrence matches an object of interest. We expect the precision/recall results to be for both algorithms, although the CC computed by DyPlagram are expected to be more numerous than the ones computed by DyPlagram st.

As can be seen in Table 1, the connected component obtained with DyPlagram st are in general less numerous, more precise and have a better recall than the ones obtained with DyPlagram. As already discussed in [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF], the distance threshold ǫ has an important impact on the obtained results. Indeed, if it is set too low (to 10 pixels, in our example), we obtain spatio-temporal patterns with high average precision for each X-wing as different occurrences of patterns which map to different X-wing are very well distinguished. However, this leads to a low average recall: since only very close occurrences of the same pattern are linked, the spatio-temporal patterns tend to be short (i.e., have low freq st ). When using a distance threshold ǫ = 10, no spatio-temporal patterns with freq st ≥ 50 were found for X-wing2 for DyPlagram ( [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF]), which explains why we used a minfreq st of 10 in this case. Conversely, for a higher ǫ of 170 pixels, the average precision drops as the different X-wings are not well distinguished anymore. For example, it was possible to obtain spatio-temporal patterns with higher recall for the plane 1 (when comparing to the other experiments), but, they had low average precision. Since the plane 1 gets partially out of the video frames around 6 times, a higher number of spatio-temporal patterns were derived for this Xwing for minfreq st = 50 and ǫ of at least 20, which represent the different time intervals where this X-wing is visible through the video. As another example, the plane 2 is hidden only twice by the plane 3 (during around 15 frames) and never goes out of the video frames. This explains the lower number of patterns found for this object, also for minfreq st = 50 and ǫ ≥ 20. step allow us to generate less occurrences (especially for support < 350) in a lower time.

Evaluation of the Spatio-Temporal Path for Object Tracking

For both datasets, we report the precision and recall results for the spatiotemporal patterns (which have a first occurrence on the object of interest anywhere in the video) and for the spatio-temporal paths (which have a first occurrence on the object of interest in the first frame of the video). The spatiotemporal patterns or connected components (CC) correspond to the global occurrences graph without the similarity edges.

Synthetic Video

The experiments reported in Table 2 show the precision and recall results for the paths obtained on the synthetic video when varying the gap between 10 and 100. Results for the CC are similar to the ones reported in Table 1.

Because of the nature of the video, we use a global minimum support minfreq of 250 in order to prune the number of frequent patterns. Indeed, since the synthetic video has been especially made to produce stable graphs, DyPlagram st returns a lot of frequent patterns on this dataset which leads to a huge global occurrences graph that possibly does not fit into memory for processing. To be able to perform various experiments, especially with the size discretization which does not permit to distinguish the three planes at the mining step, we set the minfreq st to 150 (although as already discussed, it is better to set it as low as possible).

Overall, we obtain very good results for the first two planes (precision and recall close to 100%). We can clearly see the lack of discriminative power of the size discretization when the gap increases. Indeed the paths start to follow different planes, reducing their precision and their recall. For those two planes the color discretization always shows good results, with average precisions and recalls close to the ones of the best paths (values in brackets). Since the 3rd plane moves back and forth horizontally across the field of view (getting almost completely out every 120 frames), only few paths starting on the plane manage to reach the end of the video when we use a low gap. The paths which uniquely follow this plane are thus more expensive than other paths on which the algorithm can "jump" using the similarity edges decreasing the precision and recall. As we can see, increasing the gap allows to overcome this problem with the color discretization while keeping good results for the other two planes.

Real Video

The experiments reported in Table 3 and 4 were made without using a global minimum support threshold (which is equivalent to set minfreq = minfreq st ). Because of the segmentation, this dataset is a lot less stable than the synthetic one resulting in less frequent patterns. For this one, so far, only the color discretization gave good precision/recall results (we also tried the size and some other color discretization).

Connected Component (CC)

The results for the connected components are presented in Table 3. Those experiments have been obtained for ǫ = 10 and ǫ = 20, above that the precision started to drop significantly (which is expected for large ǫ values if other distracting objects are frequent). As expected, the precision is a little higher with ǫ = 10 (100% for ǫ = 10 when τ = 10 and minfreq st = 100 against 92.48% for ǫ = 20). The fact that the average recall also decreases with a higher distance is more surprising at first glance. This is explained by the fact that most of the time, ǫ = 10 is enough to follow the drone, but sometimes the drone or the camera movement accelerates. In those cases a higher distance might give longer and better CC but also might introduce some noisy ones which would decrease the average recall and precision.

The average recall also lowers when we lower minfreq st . This is due to the fact that when using a low minfreq st DyPlagram st outputs short spatio-temporal patterns that necessarily have a low recall. Lowering minfreq st slightly reduces the precision of the connected components but increases their number.

As also expected, higher gaps lead to better recall (38.21% for τ = 100 when ǫ = 10 and minfreq st = 100 against 26.18% for τ = 10) as well as improve the coverage of the spatio-temporal patterns in the whole video. The precision doesn't seem to be influenced by τ when we allow small spatio-temporal patterns (i.e., a low minfreq st ). Spatio-Temporal Paths Table 4 shows the results for the CC on the real dataset for the color discretization.

A distance ǫ equal to 20 gives the best results in most cases with high precision and good recall (99.03 for precision and 80.63 for the recall for ǫ = 20, τ = 25 and minfreq st = 10 for example). However, the values for τ = 10 show the limits of the use of the shortest path algorithm to tackle our problem. Similarly to what was happening with the third plane in the synthetic video, the shortest path might not always be following the object we want to track if elements in the background or other objects offer better stability than the object we want to track and are close enough to "jump" on them.

The results with our preferred setting (low minfreq st = 10, high τ = 100 and a distance ǫ = 20) show that the spatio-temporal paths can indeed be used to follow an object in the video. The similarity edges introduced are very useful to increase the recall of the patterns and experiments with a higher similarity constraint (for example with σ = 0.8) show worst results. This shows the importance of this "inexact" matching phase in the process. On the downside, the choice of the labels on the node (here it is a color information) seems to play a very important role to get interesting spatio-temporal patterns although it is difficult to evaluate in an unsupervised setting what could be the best ones. One solution could be to attach more diverse information on the labels of the nodes to overcome this problem.

Conclusion

We have presented an unsupervised method based on graph mining to track objects in videos. More precisely, we have used paths computed in an occurrences graph of these frequent graph patterns. The graph is created by linking through spatial, temporal and similarity constraints the frequent patterns to follow one or multiple objects simultaneously in a video. The results on a synthetic and on a real video show that this method is effective to tackle our tracking problem. However, it strongly relies on the labels of the nodes (discretization and chosen features). This problem could be tackled by taking into account multiple and diverse ordered information on the nodes to automatically select the best features depending on the video. Some future work could also be done on the computation of the best paths in the video as the current shortest path algorithm assumes that our objects of interest are followable from the first to the last frame of the video. Although still naive, we believe that our method could be useful to tackle the difficult problem of tracking multiple objects in the specific case in which both the objects and the background are moving and when no supervised information about the objects to track is known in advance. The proposed method could also benefit from the very recent work which uses supporters (points or objects moving in a correlated way with the tracked objects) or distracters (objects which should not be confused with the objects to track) for example presented in [START_REF] Dinh | Context tracker: Exploring supporters and distracters in unconstrained environments[END_REF] as these would typically represent correlated frequent subgraphs.

Definition 9 (

 9 Frequency of a spatio-temporal pattern). The frequency of a spatio-temporal pattern S based on a graph pattern P in a dynamic graph D is freq st (S) = | {i | ∃f, (i, f ) ∈ S} |.

Fig. 1 .

 1 Fig. 1. Occurrences of a pattern and occurrences graph of this pattern (temporal threshold τ = 2 and distance threshold ǫ).

Fig. 2 .Fig. 3 .

 23 Fig. 2. Example of RAGs obtained from the synthetic video

Fig. 4 .

 4 1 show three examples of RAGs we obtained for this dataset.

Fig. 4 .

 4 [START_REF] Yilmaz | Object tracking: A survey[END_REF] show three examples of RAGs we obtained for this video.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Time(s) taken by both versions of the DyPlagram algorithm, with τ = 1, minfreq st = 50 and ǫ = 20 to generate all the occurrences (red vs blue line) and to generate the occurrences graph ((red vs green line)

Fig. 4

 4 Fig. 4 and 5 show efficiency results comparing DyPlagram [14] and Dy-Plagram st. As expected, pushing the spatial constraints during the mining

  Computes the edges of occurrences graph(P ) (using ǫ and τ ) 6 Computes all spatio-temporal patterns based on P 7 for each spatio-temporal pattern S based on P do 8 if freq st (S) ≥ minfreq st then output(S) 9 if there is no frequent spatio-temporal pattern then return 10 else 11

		occurrences graph(P ) = empty graph
	2 for each occurrence of P in D do
	3	Add this occurrence to occurrences graph(P )
	4	Computes all valid extensions of this occurrence
	5

for each extension E of P do 12 if the code of E ∪ P is canonical and freq(E ∪ P ) ≥ minfreq then 13 mine(P ∪ E, minfreq, minfreq st , τ, ǫ, D) 14 return

Table 1 .

 1 Evaluation of the connected components (CC) issued from all patterns with minfreq = 721 and τ = 1 for DyPlagram and for DyPlagram st. The labels are created from the size of the region.

		DyPlagram with post-processing		DyPlagram st
				ǫ = 10, minfreq st = 10
		Precision(%) Recall(%) Number of CCs Precision(%) Recall(%) Number of CCs
	plane 1	78	7	151	78	7	114
	plane 2	72	3	129	95	3	71
	plane 3	87	2	131	88	2	84
				ǫ = 20, minfreq st = 50
		Precision(%) Recall(%) Number of CCs Precision(%) Recall(%) Number of CCs
	plane 1	77	15	73	82	17	65
	plane 2	93	26	43	100	29	39
	plane 3	100	10	60	100	10	60
				ǫ = 170, minfreq st = 50
		Precision(%) Recall(%) Number of CCs Precision(%) Recall(%) Number of CCs
	plane 1	45	38	27	51	42	24
	plane 2	51	10	15	49	8	17
	plane 3	60	12	21	69	13	19

Table 2 .

 2 Evaluation of the spatio-temporal path with minfreq = 250, minfreq st = 150, σ = 0.65, ǫ = 20. The numbers between parenthesis correspond to the best precision and recall of the best path in term of recall, and the emphasized results are the best results for each plane

			Size Discretization		Color Discretization
		τ Precision(%)	Recall(%) Paths Precision(%)	Recall(%) Paths
	plane 1		98.32 (99.72) 97.50 (99.30) 34	93.92 (99.74) 93.60 (99.86) 21
	plane 2	10	99.63 (99.73) 97.26 (98.19) 24	98.65 (100) 96.82 (99.02) 17
	plane 3		9.49 (16.64) 8.70 (15.39)	4	-(-)	-(-)	0
	plane 1		95.79 (100) 94.59 (99.02) 38	99.17 (99.73) 98.40 (100)	21
	plane 2	25	65.66 (99.61) 64.61 (98.05) 32	98.54 (100) 96.34 (99.02) 20
	plane 3		2.93 (9.09)	2.50 (8.59)	29	31.95 (31.95) 29.54 (29.54)	2
	plane 1		79.05 (100) 74.37 (94.31) 42	97.76 (100) 95.36 (99.30) 29
	plane 2	100	72.57 (97.53) 67.05 (93.62) 35	98.87 (100) 96.30 (99.02) 39
	plane 3		5.42 (18.46) 4.82 (16.36)	31	86.27 (90.52) 75.92 (82.80) 23

Table 3 .

 3 Precision, recall and coverage recall computed for the connected components computed and for the real video with minfreq = minfreq st , and σ = 0.65

				ǫ = 10			ǫ = 20
	τ minfreq st Precision(%) Recall(%) CC Precision(%) Recall(%) CC
		100	100	26.18	10	92.48	22.97	13
	10	50	93.55	17.40	20	91.35	15.44	25
		10	89.78	2.87	294	89.70	2.72	334
		100	91.28	35.34	11	89.02	30.03	14
	25	50	90.28	25.12	18	83.79	20.14	24
		10	88.90	3.18	307	89.47	2.94	358
		100	89.52	38.21	14	89.02	31.03	19
	100	50	92.27	24.38	27	90.30	22.45	30
		10	89.01	4.03	258	89.88	3.63	302

Table 4 .

 4 Precision and recall computed for the spatio-temporal paths for the real video with minfreq = minfreq st and σ = 0.65.

				ǫ = 10			ǫ = 20
	τ minfreq st Precision(%) Recall(%) Paths Precision(%)	Recall(%)	Paths
		100	96.30 (96.30) 67.89 (67.89)	1	98.23 (100)	80.94 (82)	2
	10	50	98.25 (100) 70.00 (71.26)	2	26.16 (38.96) 24.03 (36.21)	3
		10	91.93 (93.34) 69.60 (70.63)	8	18.75 (36.09) 17.88 (34.73)	8
		100	98.43 (100)	68.89 (70)	6	98.51 (100) 78.68 (79.68)	6
	25	50	98.66 (100)	69.05 (70)	7	98.72 (100) 78.82 (79.68)	7
		10	99.06 (100) 69.36 (70.21) 10	99.03 (100) 80.63 (81.36) 10
		100	100 (100) 67.42 (67.78)	8	100 (100)	77.52 (79.68)	9
	100	50	100 (100) 67.36 (67.68)	9	100 (100)	77.54 (79.68)	9
		10	100 (100) 67.21 (67.78) 10	99.26 (100) 79.17 (79.78)	10

http://www.cs.brown.edu/∼pff/segment/