Elisa Fromont

Baptisete Jeudy

Tran Hoang Tung

It has been an

honor to be one of Elisa's first Ph.D. students. She has taught me, both consciously and unconsciously, how a good researcher should be. I appreciate all her contributions of time and ideas to make my Ph.D. experience productive and stimulating. I hope that I could be as lively, enthusiastic, and energetic as her and to someday be able to do research as well as she can. Baptiste

Résumé

Nous présentons dans cette thèse un système de correction automatique d'annotations (tags) fournies par des utilisateurs qui téléversent des vidéos sur des sites de partage de documents multimédia sur Internet. La plupart des systèmes d'annotation automatique existants se servent principalement de l'information textuelle fournie en plus de la vidéo par les utilisateurs et apprennent un grand nombre de "classifieurs" (potentiellement un par tag) pour étiqueter une nouvelle vidéo. Cependant, les annotations fournies par les utilisateurs sont souvent incomplètes et incorrectes. En effet, un utilisateur peut vouloir augmenter artificiellement le nombre de "vues" d'une vidéo en rajoutant des tags non pertinents ou peut simplement oublier une annotation évidente qui aurait pu être utilisée efficacement par un système d'indexation. Dans cette thèse, nous limitons l'utilisation de cette information textuelle contestable et nous n'apprenons pas de modèle pour propager des annotations entre vidéos. Nous proposons de comparer directement le contenu visuel des vidéos par différents ensembles d'attributs comme les sacs de mots visuels basés sur des descripteurs SIFT ou des motifs fréquents construits à partir de ces sacs. Nous proposons ensuite une stratégie originale de correction des annotations basées sur la fréquence des annotations des vidéos visuellement proches de la vidéo que nous cherchons à corriger.

Nous avons également proposé des stratégies d'évaluation et des jeux de données pour évaluer notre approche. Nos expériences montrent que notre système peut effectivement améliorer la qualité des annotations fournies et que les motifs fréquents construits à partir des sacs de motifs fréquents sont des attributs visuels pertinents. 1.10 Breadth-first search vs Depth-first search approaches. (source: [START_REF] Pang-Ning | Introduction to data mining[END_REF]) . . 1.11 Code table example (from [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF]). The widths of the codes indicate lengths.

The usage column is here only to demonstrate the more a code is used, the shorter it is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.12 A database example with its cover and encoded length derived from the code table shown in Figure 1.11. (source: [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF]) . . . . . . . . . . . . . .

A example of Standard Code Table with its cover and encoded length

derived from the database shown in Figure 1.12. (source: [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF]) . . . . .

Examples of different binarization techniques. From top to bottom:

SBin, multiple uniform intervals, non-uniform intervals and B2S. . . . . 1.15 A video is represented as an average of all its keyframes. . . . . . . . . . 1.16 The distance between two videos equals to the distance between two most similar keyframes (the red line in this example). . . . . . . . . . .

Introduction

It's now commonplace to say that the digital universe is rapidly growing. In fact, according to a market survey performed by IDC 1 , between 2009 and 2020 the amount of digital information will grow by a factor of 44. In the case of digital multimedia content, that trend is confirmed by the fact that video-sharing websites are growing very quickly. If we consider for example the particular case of YouTube, the statistics provided by that company 2 say that "over 6 billion hours of video are watched each month on YouTube -that's almost an hour for every person on Earth, and 100 hours of video are uploaded to YouTube every minute". Concerning the users of such services, YouTube says more than 1 billion unique users visit their servers each month, that shows there is a huge demand for such resources.

How can users retrieve interesting videos on the Web among this huge amount of data? This is a more and more difficult issue to handle. Multimedia content indexing has been a very active field of research in recent years as the benefits of such a research will have a strong impact on the usage which may be done by ordinary people of the internet tomorrow. The famous survey on visual content-based video indexing and retrieval from Weiming Hu [START_REF] Hu | Maybank. A survey on visual content-based video indexing and retrieval[END_REF] reflects the intensive research in this field. The difficulty of the task may be easily understood. Working on videos means dealing with huge quantities of keyframes (generally at least 24 per second) made up of hundreds of thousands pixels. Even if image indexing techniques begin to be efficient, there is still work to do to get such results with videos. In fact, textual document indexing is a far more mature domain and efficient algorithms have been provided for years in the field of information retrieval that were dedicated primarily to textual document retrieval [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF]. The most efficient tool available for ordinary people is without no doubt Google that allows to instantly find relevant documents from a huge set of documents stored on Google's servers. Even if many efforts are still needed to improve search engines such as Google to better search for textual documents, textual document indexing is far more advanced that video indexing at the moment.

Thus, the approach based on combining textual information and video resources has began to provide promising results [START_REF] Shen | Multimedia tagging: past, present and future[END_REF] and is widely used in most commercial video-sharing websites such as YouTube, DailyMotion, Wat TV, etc. The users of such websites generally have to manually annotate the videos while uploading them providing a small textual description or a set of keywords that are generally called tags. Those tags are then used to index the videos and make them available for the other users.

However, to allow the search engines underlying these websites to accurately index the extensive resource of online videos, each video has to be carefully annotated. Unfortunately these annotations are often incorrect. Indeed, users uploading videos might often want to rapidly increase their video's number-of-view by tagging them with popular tags such as "Harry Potter", even if those videos have nothing to do with this famous book series. Moreover the set of tags attached to a video is also generally incomplete that is, it is not sufficient to correctly characterize the video. The poor quality of the tags leads to a poor quality of video indexing and many videos are hidden to people just because their tags are not accurate.

To solve this problem, video-sharing websites might consider recruiting people whose job would be to annotate videos all day long. Given the amount of data, it would be very expensive, but this is not even the main issue. In fact, in the market survey performed by IDC presented previously, it was not only given facts about the growth of the digital information between 2009 and 2020, but also that, in the same time, the staffing and investment to manage it will grow by a factor of only 1.4. Given the growth of digital storage, there would never be enough human resources to annotate the uploaded videos and the resulting cost.

In fact, a major issue to make professional people annotate videos is that the annotation task is in essence subjective. This may result in a tag quality that may be dependent of the tagger, of his personal knowledge about the videos he has to tag, of the moment of the day he performs his task, etc. To solve this problem we may think about an automatic process to help people tagging videos. The first step would consist in manually tagging a not so huge quantity of videos, and the second step would be done by the machine that could learn (with supervised machine learning techniques) a classifier for each tag that has been used. Nevertheless this approach is not realistic because the number of tags used in websites like youtube may reach millions. Training millions of classifiers is not a solution.

In this thesis, in order to address these problems, we focus on improving the annotation of videos provided by users of video-sharing websites. There have been many

efforts to design algorithms to automatically annotate videos (see for example [START_REF] Shen | Multimedia tagging: past, present and future[END_REF] and [START_REF] Morsillo | Youtube scale, large vocabulary video annotation[END_REF]). However, most of the current approaches are based on supervised learning techniques which is not acceptable for scalability reasons.

Thus, we want to propose an unsupervised data mining approach based on the comparison of the visual content of the videos to propagate the tags of the most similar videos. There are two motivations for applying data mining techniques to design an unsupervised video tagging system. The first one is that despite the drawbacks of the user-provided annotations we previously talked about, these millions of tags result from the annotation of millions of videos by millions of users all around the world and it would be a pity not to use such a great source of information. Indeed, adequately processing the (eventually noisy) tags will certainly help a lot the video indexing task.

The idea we want to implement is that if people upload videos about a topic T, most people will tag that video with a tag "T". Then, if a new video about T is uploaded without that tag, and if we may find many similar videos with tag "T", that new video should automatically be tagged with "T".

The second motivation for applying data mining techniques in this thesis is that many success stories have been told about data mining techniques in the area of business and science. Many papers have also been published about using data mining techniques in the context of image/video processing in order to extract discriminative patterns. Applying data mining techniques in our context is just a natural step since we have large amount of data and we want to discover interesting information in it, that is knowledge about the way particular videos are associated to particular tags.

Of course, the problem we want to tackle is not simple because it confronts us with a number of challenges. The first one is related to the classical problem of computational cost while mining huge datasets. That cost becomes even higher with video datasets.

Indeed, as any video segment can be a candidate for a "good pattern", performing exhaustive search on all possible candidates at various locations (space) and lengths (time) will involve extremely huge computational cost. Of course, a second challenge is related to the fact that (pre-)processing videos is far more difficult than (pre-)processing transactional data stored into a relational database. Another important challenge is the classical problem of overwhelming amount of patterns resulting from the data mining step. As we said previously, other researches about automatic tagging of videos often rely on supervised approaches thus they can use supervised information (the class of the video) to post-process the extracted patterns and only keep those one that are discriminative for a given class. However, in our case, there is no such information, thus post-processing becomes a very important issue. Finally, another challenge is that we have some video datasets without any proper ground truth. This makes our approach difficult to compare with other state-of-the-art approaches.

Several contributions are presented in this thesis. First we look at the various features that could be used to design an efficient comparison function between videos.

Besides, we evaluate our approach and compare it with state-of-the-art techniques.

Then we propose a simple but effective tag propagation process and finally evaluate the entire system.

The remaining of the thesis is organized as follows. Chapter 1 describes the state of the art techniques that are useful for our research. It first describes the basic concepts in the image processing field and more specifically goes into more details about a classical visual feature called SIFT-BoW. It then presents some popular data mining techniques as well as how to apply them in the context of videos. The last section is about the tagging process and presents some current techniques. Chapter 2 presents an overview of our framework that aims to automatically tag videos. In that context, there are many parameters that need to be tuned, thus, extensive experiments with image datasets are performed to evaluate the impact of each one. Chapter 3 presents some experiments on various datasets in order to demonstrate the effectiveness of our approach. The two first datasets are quite simple with a limited number of videos or tags, the third one has nearly 700 videos with 150 tags. Finally we will conclude and propose some future developments.

Chapter 1

State-of-the-Art As explain in the introduction, our aim is to automatically correct and complete tags on large video datasets such as, for example, the Youtube dataset. To tackle this problem, we will follow a process very similar to the traditional knowledge discovery from databases (KDD) process as shown in Figure 1.1. In the first step, the video dataset undergoes a series of pre-processing substeps: selection and cleaning. For example the cleaning step could consist in filtering out the videos with a resolution too low to be processed, in cropping all videos to get a dataset of videos of the same size, in dividing the dataset into batches of manageable size, etc. These steps are not developed in this chapter and we will assume that the dataset we are using can undergo the subsequent processes (more details about our specific pre-processing steps are given in Chapter 4). Once done these first substeps, one has to convert the video dataset into a suitable format for the data mining process, this is the transformation step. In our case, the data mining step is then used to produce a set of Mid-level features that are, hopefully, more suitable than the low-level features that can be directly extracted by image processing algorithms. Then, a knowledge extraction step is performed. In our case, it is a tag propagation step based on the comparison of the videos described by the newly found mid-level features. This chapter focuses on the these three last steps.

Transformation Step

We call transformation step the process of extracting sets of features from a clean video dataset. To do that, one first needs to analyze the structure of the video and then, extract some features to describe it. The structure analysis consists in splitting the video into multiple frames. On the other hand, the feature extraction process aims at representing a frame (i.e an image) as a vector of visual features. However, since the structure analysis is also performed based on some features extracted from the frames, we start this section with a review of the different common features used in image and video analysis and we will then explain how the structure analysis is performed.

Video Features

This section will cover some visual features that are often used for video analysis.

Auditory features and text features are not considered here although they are combined with other features in some articles related to automatic tagging of videos [START_REF] Toderici | Finding meaning on youtube: Tag recommendation and category discovery[END_REF]. Different features are usually best suited for different tasks so the current trend is to concatenate all kinds of low level features and obtain a very high dimensional vector that will be used for video comparison. Another very popular technique is to construct a Bag-of-visual words [START_REF] Yang | Evaluating bagof-visual-words representations in scene classification[END_REF] (BOW) from the original low-level feature vectors. In this document, we will mainly rely on local features called SIFT (for Scale Invariant Feature Transform) [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and SIFT-Bag-of-words. The name SIFT applies both to an interest point detector method and a local feature used in image processing. It is robust and can be used to identify the same features in different images, even with large changes in scale and rotation. In this section, we will first classify the different group of video features then briefly explain how they can be extracted. We will focus on the particular case of the SIFT descriptors and SIFT bag-of-words since they are the ones used in the remainder of this document.

Feature Classification

Since a video is composed of frames (i.e. images), most of the traditional image features can also be used for video analysis. Features can be roughly classified as color-based, texture-based and shaped-based. For the specific case of videos, we add the motion features.

Color-Based Features. They include color histograms [START_REF] Amir | Ibm research trecvid-2003 video retrieval system[END_REF], color moment [START_REF] Yan | A review of text and image retrieval approaches for broadcast news video[END_REF], color correlograms, etc. These features depend on color spaces such as RGB (Red-Green-Blue), HSV (Hue-Saturation-Value, which is a representation of points in an RGB color model), YCbCr (this is another way of encoding RGB information: Y is luminance, Cb and Cr represent the chrominance i.e. differences between the luminance and the blue (resp. red) color channels), etc. The choice of color spaces depends on applications.

Color features can be extracted from the whole frame or from an image block. They are very simple but still efficient. is used in [START_REF] Moxley | Video annotation through search and graph reinforcement mining[END_REF], background features (8x8 Hue-Saturation) are used in [START_REF] Toderici | Finding meaning on youtube: Tag recommendation and category discovery[END_REF] and in [START_REF] Morsillo | Youtube scale, large vocabulary video annotation[END_REF],

frame features include LAB and HSV global color histograms. Texture-Based Features. Similar to color, texture is an important part of human visual perception and is another essential feature. Unlike color, texture spreads over a region instead of at a point. It is normally defined solely by grey levels and thus is orthogonal to color. Texture features contain important information about object surfaces as well as their correlations with the surrounding area. The most common texture features include Tamura feature [START_REF] Tamura | Textural features corresponding to visual perception[END_REF], co-occurrence matrix [START_REF] Robert | Statistical and structural approaches to texture[END_REF], and wavelet transformation-based features [START_REF] Mark R Turner | Texture discrimination by gabor functions[END_REF]. For example, Amir et al. [START_REF] Amir | Ibm research trecvid-2003 video retrieval system[END_REF] use Tamura and cooccurrence features for a video retrieval task in TRECViD-2003, Hauptmann et al. [START_REF] Hauptmann | Informedia at trecvid 2003: Analyzing and searching broadcast news video[END_REF] use Gabor wavelet filters for a video search engine. In the specific context of tagging,

Haar and Gabor wavelets are, for example used in [START_REF] Morsillo | Youtube scale, large vocabulary video annotation[END_REF] and in [START_REF] Toderici | Finding meaning on youtube: Tag recommendation and category discovery[END_REF].

Shape [START_REF] Moxley | Video annotation through search and graph reinforcement mining[END_REF] whereas Yang and Toderici [START_REF] Yang | Discriminative tag learning on youtube videos with latent sub-tags[END_REF] use HOG (Histograms of Oriented Gradient) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF].

Motion Features. The previous features do not take into account the spatial-temporal relationship between video frames, which is the crucial property that distinguish videos from still images. Motion features fill this gap by presenting the temporal information.

In general, there are two types of motions: background motion caused by the camera movement, and foreground motion caused by moving objects. Thus motion features can be divided into 2 categories: camera-based and object-based. Within camera-based features, there are different camera motions such as "zooming in and out", " tilting up and down"etc. These features can not capture the motion of the important objects.

Object-based motion features are more interesting and thus more studied. A first approach consist in trying to model the distribution of global or local motions in videos.

For instance, Ma and Zhang [START_REF] Ma | Motion texture: a new motion based video representation[END_REF] convert the classic motion vectors into a number of directional slices, these slices in turn are used to create a multidimensional vector which is called motion texture. This approach has low computational complexity, but it lacks an accuracy representation for object actions. The second approach is modeling the motion trajectories of objects in videos [START_REF] Dao | Video retrieval using video object-trajectory and edge potential function[END_REF]. In [START_REF] Faisal I Bashir | Real-time motion trajectory-based indexing and retrieval of video sequences[END_REF], each trajectory is represented as temporal orderings of sub trajectories which are represented by their principle component analysis (PCA) coefficients. [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] proposed the SIFT interest point detector, to identify potential interest points by selecting the local extrema of an image filtered with differences of Gaussian. The output of a sift detector is a point, a scale which generates a patch around the point (depending on the scale of the image) and an orientation which corresponds to the dominant gradient in the patch. The orientation will provide rotation-invariance properties to the descriptors.

The key-points extracted from these detectors are then described (with some descriptors) and used as input for any image/video analysis tools. However, extracting a large number of interest points can be expensive and, not necessarily reliable if the images/videos are especially diverse. In 2006, [START_REF] Nowak | Sampling strategies for bagof-features image classification[END_REF] showed that for description purposes, one could use a simpler strategy that obtain comparable performance as detecting a set of interest points. This strategy is called dense sampling. It consists in uniformly selecting points in the image, for example on a regular grid, instead of focusing on particularly interesting ones. An example of these two methods are shown in figure 1.3. In the special case were the targeted descriptors are SIFT features, [START_REF] Jasper Rr Uijlings | Realtime visual concept classification[END_REF] proposed a very efficient dense sampling implementation written to avoid the computations of overlapping regions.

SIFT Descriptor

We will now focus on the particular case of the SIFT descriptors as they are the main features used in this thesis. A SIFT descriptor is a 128-Dimensional vector which describes weighted gradient information around a given point. To construct such a descriptor, one has to identify a neighborhood region (a patch) around a point given by a scale parameter and an orientation for this patch. These parameters are provided by a sift detector and should be chosen arbitrarily when using a dense sampling method

[43].

To compute the SIFT descriptor, the patch is encapsulated inside a 16x16 window (as in Figure 1.6) broken into sixteen 4x4 windows. Within each small window, gradient magnitudes and orientations are calculated. The gradient magnitude and orientation of a point (x, y) (see Figure 1.4) can be computed by:

m(x, y) = (L(x + 1, y) -L(x -1, y)) 2 + (L(x, y + 1) -L(x, y -1)) 2 θ(x, y) = tan -1 L(x, y + 1) -L(x, y -1) L(x + 1, y) -L(x -1, y)
These gradients are computed for all points (x, y) within the window. Then, a histogram is created for the orientations. By default, the 360 degrees are divided into 36 bins (each bin has 10 degrees): the first bin is from 0 to 9 degrees, the second bin As a result, one 4x4 window is equivalent to a 8-bin histogram or a 8-dimensional vector. The whole 16x16 window can now be presented as a (4 x 4 x 8 =) 128 dimensional vector. To make this feature rotation independent, the interest point's prominent rotation (the original orientation) is subtracted from each and every orientation (i.e.

all 128 values). A normalization step is done by dividing each bin by the root of the sum of the squared vector.

1.1.1.4 Bag-of-Word Construction
The bag-of-words model is a representation originally used in natural language processing [START_REF] Sabbetai | [END_REF]. In this model, a text (such as a sentence or a document) is represented as an unordered collection of words, disregarding grammar and word order. Recently, the bag-of-words model has also been adopted for computer vision. Thus some prefer calling this Bag-of-Visual-Word (BOW) instead, to emphasize that this technique is used in image processing, and the "word" is a "visual word" instead of a "text word". and an image may also consists of several hundreds interest points, thus the whole data set can be described as a huge set of points in this 128-D space. In this space, a large amount of those points might be close and could be described as an unique "point" (i.e a unique visual word) to obtain a description less sensitive to small variations.

Specifically, a clustering algorithm (e.g. K-means) is used to cluster the total amount of descriptors described in the SIFT 128-D space. The number of clusters determines the size of the visual vocabulary (i.e. the number of visual words), which can vary from hundreds to over tens of thousands. Each cluster has a prototype (typically its center points) called the visual word. All the points that belong to this cluster will be mapped to this prototype.

Finally, within an image, replacing all interest points with their corresponding visual words produces a set of visual words called the bag of visual words. This BOW representation can be converted into a visual-word vector by counting the number of appearance of each visual word within the image (or within the bag). [START_REF] Yuan | A formal study of shot boundary detection. Circuits and Systems for Video Technology[END_REF] but they all contain these three steps:

extracting the visual features from the frames, measuring the similarities between them, and detecting boundaries based on the dissimilarities.

Since the number of frames is often large (at least 24 frames per second) within a shot, the low-level features extracted should be simple and efficiently computable.

They often include color histogram [START_REF] Han | A shot boundary detection method for news video based on rough-fuzzy sets[END_REF], [START_REF] Steven | Chinese university of hongkong at trecvid 2006: Shot boundary detection and video search[END_REF], motion vectors [START_REF] Victoria | Video segmentation and indexing using motion estimation[END_REF], etc. Some authors even tried with more complex features such as SIFT features [START_REF] Chang | Unsupervised video shot detection using clustering ensemble with a color global scaleinvariant feature transform descriptor[END_REF] or other descriptors extracted with an interest points detector [START_REF] Gao | A video shot boundary detection algorithm based on feature tracking[END_REF]. However, in general, all these more complicated features can not outperform the basic color histogram [START_REF] Yuan | A formal study of shot boundary detection. Circuits and Systems for Video Technology[END_REF].

The similarities between the frame features can be measured using for example [START_REF] Camara-Chavez | Shot boundary detection by a hierarchical supervised approach[END_REF][START_REF] Cooper | Video segmentation via temporal pattern classification[END_REF][START_REF] Lu | Shot boundary detection using unsupervised clustering and hypothesis testing[END_REF]:

• the classic Euclidean distance: d(q, p) = n i=1 (q i -p i ) 2
• the intersection kernel:

k(q, p) = n i=1 min(q i , p i )
• the chi-squared metric:

d(q, p) = n i=1 (q i -p i ) 2 2(q i + p i )
The techniques include pair-wise measuring (compare successive frames) and window measuring (compare frames within a window). The window-based one is more effective but also more computational than the pair-wise one.

Then, once computed the features and their similarities, one has to detect the shot boundaries. Current approaches can be roughly divided into two types: threshold-based and learning-based approaches.

• Threshold-based Approach: the threshold can be global [START_REF] Cernekova | Information theory-based shot cut/fade detection and video summarization[END_REF], adaptive [START_REF] Xia | Shot boundary detection based on difference sequences of mutual information[END_REF], or combination of both [START_REF] Georges M Quśenot | Clips at trecvid: Shot boundary detection and feature detection[END_REF]. The global threshold is used for the entire video, and the adaptive threshold is calculated locally with a sliding window. The adaptive threshold often returns better performance compared to the global one. However, estimating the parameters for the adaptive threshold is more difficult.

• Learning-based Approach: the boundary detection problem is converted into a binary classification task in which frames are classified as boundary or not. Both supervised and unsupervised learning are used. Support Vector Machine (SVM) [START_REF] Camara Chavez | Shot boundary detection at trecvid 2006[END_REF], [START_REF] Zhao | Bupt at trecvid 2007: Shot boundary detection[END_REF] and Adaboost [START_REF] Zhao | Shot boundary detection algorithm in compressed domain based on adaboost and fuzzy theory[END_REF] are the two most commonly used supervised classifiers.

Keyframe Extraction

The next step after detecting shots is trying to succinctly represent each shot as one or several most informative frames. These frames are called keyframes. According to [START_REF] Ba | Video abstraction: A systematic review and classification[END_REF], there are many categories of keyframe extraction techniques.

The simplest technique consists in extracting the keyframes by evenly sampling the video (two keyframes a second, or two keyframes a shot [START_REF] Morsillo | Youtube scale, large vocabulary video annotation[END_REF], for instance).

Another commonly used technique consists in iteratively comparing each and every frame with the most recent keyframe until finding a frame that is very different. That frame then is selected as the next keyframe. Simple feature such as color histogram can be used with this technique [START_REF] Zhang | Dynamic selection and effective compression of key frames for video abstraction[END_REF]. Another similar technique is constructing a reference frame for each shot, it can be an average histogram [START_REF] Müfit | Two-stage hierarchical video summary extraction to match low-level user browsing preferences[END_REF], or a maximum occurrence frame [START_REF] Sun | Video key frame extraction based on spatial-temporal color distribution[END_REF]. Then, a distance is calculated between each frame in the shot and the constructed/reference frame. Keyframes are extracted using the distance curve (at the peaks, for example). Some researchers even consider both keyframe extraction and object detection to make sure that the keyframes will contain information about objects [START_REF] Kang | To learn representativeness of video frames[END_REF]. Clustering-based approach [START_REF] Zhuang | Adaptive key frame extraction using unsupervised clustering[END_REF] is another method to extract keyframes. After all frames are clustered, one representative frame is then extracted from each cluster to become the keyframe. The similarity function of clustering algorithm is calculated as the overlapping of two color histograms (i.e. using an intersection kernel).

Since the definition of a keyframe is subjective, there is no consistent method to evaluate the quality of these keyframes. However, the error rate and the video compression ratio are two popular measures that can be used as evaluations. In general,

given a video and a set of keyframes, a compromise between low error rate and high compression ratio is often taken.

Pattern Mining

The features presented before were the core of the research in computer vision for many years. However, many recent papers [START_REF] Agarwal | Hyperfeatures-multilevel local coding for visual recognition[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]82] have shown that global features (such as a single histogram per images), very local features such as SIFT descriptors or even BOW are not discriminative enough to tackle very challenging image or video analysis problems such as the ones provided for example in the PASCAL VOC challenges [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF] and in the TRECVid competition [START_REF] A F Smeaton | Evaluation campaigns and TRECVid[END_REF]. In particular, there has been a very recent focus on making use of pattern mining techniques to obtain more discriminative features from the BOW representation of images and videos (see Section 1.2.4).

In this section, we will start with a general introduction on pattern mining. Then, we will focus on two recent heuristic pattern mining algorithms based on the "minimum description length" principle: KRIMP and SLIM. The latter is the main algorithm that we will use in the following chapters. Finally, we will conclude with a bibliography on the pattern mining methods currently used in computer vision.

Overview

Pattern mining is a subfield of data mining which aims at finding regularities (patterns) in some given data. Depending on the type of data, these patterns can be sets (itemsets), sequences or graphs. We first provide the basic vocabulary used in the pattern mining field and we present in more details different itemset mining algorithms and their characteristics. Three of them are extensively used in the rest of this thesis.

Transaction ID

Attributes

Beer Bread Soda Diaper Milk

1 0 1 1 0 1 2 1 1 0 0 0 3 1 0 1 1 1 4 1 1 0 1 1 5 0 0 1 1 1
Table 1.1: A market basket record dataset.

Generalities over Pattern Mining Datasets

A dataset can be considered as a collection of data objects. There are many other names for data object, depending on the context: record, point, vector, pattern, event, sample, observation to name a few. Each data object, in turn, is described by multiple attributes such as the mass, or the availability of an object.Attributes are also named variables, characteristics, features or dimensions. Datasets can be roughly divided into three categories: record data, graph-based data, and ordered data.

Attributes An attribute is a property of an object that may vary from one object to another, or from one time to another. It can have a small number of possible values (categorical attributes) or unlimited ones. For example, the attribute "eye color" has a limited number of possible values that change from person to person, and the attribute "temperature" of an object has unlimited possible values that change over time. With the same dataset, there are many options to choose appropriate attributes.

For example, in table 1.2, the attributes are "the first item in the basket" etc. and the possible values are "Beer, Bread, Soda. . . " However, that dataset can be represented as in table 1.1, the attributes then are "whether Beer is bought or not", "whether Bread is bought or not". . . and the corresponding values are binary: "1" means yes and "0" means no.

Record and Transactional Data In the standard setting, the data set is a collection of records, each record contains a fix number of attributes. where the data contains information about some customer purchases in a supermarket (we call it market basket data).

In the case of market basket data, the number of possible items that a customer can purchase (the attributes of the table) is often much larger than the actual number of items in his/her basket. A Transaction table is a more "compact" representation of the record table where only the non-zero values are kept. In our market basket example, the products purchased by a customer constitutes a transaction, while each individual product is an item. Table 1.2 shows a sample transaction data set. Each row represents the purchases of a certain customer at a certain time. Note that to make it even more compact, the attributes name can be re-encoded using numbers.

Frequency and Apriori Principle

In the seminal SIGMOD paper of Agrawal et.al. ([3] which introduced the first pattern mining algorithm, the patterns were used to create association rules. This first algorithm mined singleton patterns called itemsets (i.e. sets of items). An association rule is a rule I → J where both I and J are itemsets and which means that there is an "association" between the occurrence of an itemset I and of an itemset J in the database.

The number of transactions that include a particular itemset in a database is called the support of this itemset (written sup(I)). The frequency of an itemset (f req(I))

is its support divided by the number of transactions in the database. In the original paper, the authors were interested in mining association of products that were often bought together in a market basket database. They were thus interested in frequent association rules. The frequency of an association rule is defined as f req(I ∪ J). The association rule search problem boils down to finding the set of patterns I ∪ J that are frequent enough (according to a minsup or minfreq threshold). Note that the size of an itemset is the number of items it contains: a 1-length itemset is a single item.

A brute-force approach to find the frequent patterns (and then the association rules) would be to enumerate them all and test their frequency over the given dataset.

However, this approach is exponential in the number of possible items (i.e attributes)

in the database: with only 20 unique items, there are 2 20 ≈ 10 6 possible candidates frequent patterns for which a support must be computed. Besides introducing the first frequent itemset mining algorithm called APRIORI, the authors of [3] also used a simple anti-monotonic principle over the frequency of the itemsets which has been used subsequently in all other pattern mining algorithm. This principle (also known as the Apriori principle) states that if an itemset is frequent, then all of its subsets must also be frequent. In other words, if an itemset if found infrequent, all its supersets can not be frequent. This principle, illustrated in Figure 1.9 in the case of APRIORI, is used to drastically reduce the number of frequent candidates during a frequent pattern search and thus reduce the computation time of all algorithms. Besides, if the dataset is divided into several partitions, an itemset can be frequent only if it is frequent in at least one partition. This property opens the door to divide-and-conquer algorithms [START_REF] Han | Mining frequent patterns without candidate generation[END_REF][START_REF] Javeed | Scalable algorithms for association mining[END_REF] for finding frequent patterns. Apriori generates candidates and tests if they are frequent: both steps are expensive.

If there are 10 4 frequent 1-itemsets, the Apriori algorithm will need to generate more than 10 7 2-itemsets and test their frequencies. FP-Growth [START_REF] Han | Mining frequent patterns without candidate generation[END_REF] is proposed with these difficulties in mind: it allows discovering frequent patterns without explicit candidate generation. The crux of FP-Growth lies within a special representation of the dataset called a FP-Tree (for Frequent Pattern Tree). Once an FP-tree has been constructed, the algorithm uses a recursive divide-and-conquer approach to mine the frequent patterns.

The standard frequent pattern algorithms find all frequent patterns. Besides, if there is a frequent pattern of size k, then according to the Apriori principle, all its itemsets with no duplication. For all these reasons, we will use this very efficient and fast implementation when mining itemsets during this thesis.

Sequence Mining Algorithms

Subsequences are another very popular type of pattern. The sequential pattern mining problem was first stated by Agrawal and Srikant [START_REF] Agrawal | Mining sequential patterns[END_REF]. Each transaction is a set of items, and each sequence is a list of ordered transactions. A frequent sequential pattern is a sequence whose appearance in the dataset is greater than a pre-defined threshold. There are many applications involving sequence data such as temporal market basket analysis, telephone calling patterns, events in networking environment, biological sequences, time series analysis etc. A number of algorithms to tackle the problem of extracting the complete set of frequent sequences in a dataset has been developed over the years.

For example, SPADE (Sequential PAttern Discovery using Equivalence classes) [START_REF] Mohammed | Spade: An efficient algorithm for mining frequent sequences[END_REF] is based on the principles developed for the ECLAT algorithm [START_REF] Zaki | Scalable algorithms for association mining[END_REF] for frequent itemset mining. It adopts a divide and conquer strategy using tidlist for support counts.

SPAM [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF], PrefixSpan [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF][START_REF] Pei | Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth[END_REF] and Clospan (Closed Sequential pattern mining) [START_REF] Yan | Clospan: Mining closed sequential patterns in large datasets[END_REF] are other well known depth-first search sequential mining algorithms. They all try to implement smart strategies to enumerate the candidate subsequences while storing as few information as possible into main memory. The last one even limits the output of the algorithm to the closed sequences which are the sequences with no super-sequence with the same support. More information on those algorithms can be found in [START_REF] Carl | Sequential pattern miningapproaches and algorithms[END_REF]. The problem of mining sequential patterns using a heuristic such as the compression-based principle described in the next section has been tackle in [85]. However, to the best of our knowledge, this method is limited to a restricted case of episodes (sequences of items) and it cannot tackle sequences of itemsets.

KRIMP and SLIM Heuristic Algorithms

The output of standard frequent pattern miners is often a very large number of highly redundant patterns. This leads to one of the major problems with the classic frequent pattern mining: it is difficult to find a small but good and informative set of patterns from such a huge number of output. The MDL principle is a criterion to select a good subset of the complete set of patterns. MDL stands for "minimum description length", and its principle is that "the best set of frequent patterns is that set that compresses the database best".

Minimum Description Length (MDL)

MDL [START_REF] Peter D Grünwald | The minimum description length principle[END_REF] is a practical version of Kolmogorov Complexity [START_REF] Li | An introduction to kolmogorov complexity and its applications[END_REF]. They all follow the Induction by Compression philosophy. The principle of MDL can be described roughly as the following:

Given a set of model M, the best model M ∈ M is the one that minimizes Note that with MDL, the main concern is the code lengths, not the semantics of the code words.

L(M ) + L(D|M ) (1.
The key idea of the MDL-based pattern mining approach proposed by Siebes et. al. [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF] is the use of a code table . A code table is a simple two-column dictionary with item sets on the left-hand side and corresponding codes on the right-hand side (see Figure 1.11). The itemsets in the code table are ordered first descending on length, second descending on support, and third following alphabet order. And the code table must contain at least all single items constructing the whole database. As mentioned before, the actual codes in the right-hand side are not important, their lengths are. To explain how these lengths are computed, the second question must be answered first: how is a database encoded by using the code table ?   Figure 1.11: Code table example (from [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF]). The widths of the codes indicate lengths. The usage column is here only to demonstrate the more a code is used, the shorter it is.

Take an arbitrary transaction t as an example to be encoded by a code table. The first step is searching for the first item X in the code table such that X ⊆ t, the search order is the order of itemsets of the code table. The code of X then becomes a part of the encoding of t. If t\X = ∅, the search is repeated to encode t\X. The process keeps going on until t\X = ∅, and the set of itemsets that are used to encode transaction t is called its cover. Since the code table contains all singletons, this algorithm always guarantees returning an encoding to any transaction. Figure 1.12 gives an example of a database and its corresponding cover as well as encoded length.

Figure 1.12: A database example with its cover and encoded length derived from the code table shown in Figure 1.11. (source: [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF])

With this encoding knowledge is at hand, we can cover all transactions in the database, and computing code lengths becomes a feasible task. The concept is that:

the more often a code is used, the smaller its length should be.

The usage of an itemset X in the code table CT is the total number of transactions which contain X in the encoding process. Thus the relative usage of X is the probability that X is used to encode an arbitrary transaction t. Borrowing from information theory field, the Shannon entropy [START_REF] Thomas | Elements of information theory[END_REF] provides the length of optimal code for X:

L(X|D) = -log P r(X|D) where P r(X|D) = usage(X)
Y ∈CT usage(Y ) These optimal values help forming the right-hand side column of the code table, thus we can use L(X|CT ) and L(X|D) interchangeably. Note that the above model M is now become the code table CT . From this information, the length of the encoding of a transaction can be easily calculated as the sum:

L(t|CT ) = X∈t L(X|CT )
And thus, the second element of equation 1.1, or the size of the encoded database is:

L(D|CT ) = t∈D L(t|CT ) (1.2)
L(CT |D) = X∈CT (L(X|ST ) + L(X|CT )) (1.3)
With results from equation 1.2 and 1.3 the total size of the encoded database can be calculated: it is simply the size of the encoded database plus the size of the code table. That is, the criteria 1.1 can be rewritten as:

L(D, CT ) = L(CT |D) + L(D|CT )
The optimal set of item is the one that its corresponding code table minimize above criteria.

However, searching for this optimal set of items is not a simple task. First of all, the search space is too large to be considered exhaustively. Secondly, there is not a simple way to know what the effect will be on the compression before adding an element to a code table [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF]. Thus, making use of heuristics is a realistic option. Two following sections will devote to two prominent heuristic approaches to solve MDL problem: KRIMP and SLIM. KRIMP is Dutch for to shrink, and SLIM means smart.

KRIMP Algorithm

The KRIMP algorithm [START_REF] Vreeken | KRIMP: mining itemsets that compress[END_REF] needs a set of frequent patterns to be able to start with.

The main task of KRIMP is filtering a pre-mined set of candidates, trying to select the best set of itemsets which compress the original database well. The pre-mined set can be a set of classic frequent patterns, like closed frequent patterns or maximal frequent patterns.

The basic greedy heuristic strategy is following:

• Start with the standard code table ST which consists of all the single itemsets.

• Add the itemsets from the pre-defined set one by one into the code

CT c ← (CT ⊕ F ) 4: if L(D, CT c ) < L(D, CT ) then 5:
CT ← post-prune(CT c ) To answer the first question: the candidates are ordered first descending on support, second descending on length, and third in alphabet order (for line 2). The reasoning for it is that: long, frequently occurring itemsets should be given high priority. Itemsets with the highest support, those with potentially the shortest ones, end up at the top of the list. Of those, the longest sets are preferred, as they will be able to replace as many items as possible.

About the order in code table CT , the elements are ordered first descending on length, second descending on support, and third in alphabet order (for line 3). The reasoning is as follows. To obtain a good compression ratio it is desired to replace as many individual items as possible, using as few as possible codes. The above order gives priority to long itemsets, as these can replace as many as possible items by just one code. Also we prefer those itemsets that occur frequently in the database to be used as often as possible.

The next step is calculating the new compressed size, and the candidate is only accepted if the compression improves (line 4). Lastly, all elements X ∈ CT c are reconsidered to remove elements which are not improve the total compression (line 5).

Pruning itemsets from the code table CT is an important step. If the total encoded size decreases by pruning an itemset, that itemset is permanently removed from the code table. It help controlling the size of the code table, and retaining only the best set of items by removing not-useful itemsets. Its net result is a speed-up as code table is kept smaller and the whole process thus needs to consider fewer itemsets. Since the pruning process only apply if the candidate F is accepted, and only few candidates are, this effectively reduces the pruning search space. Also, not all subsets of CT is considered for pruning, only itemset whose usage decreases is considered for removal.

The rationale is that for itemsets whose code lengths have increased, there is a high chance that these sets now harm the compression.

The algorithm is simple and straightforward. It provides a solution to the wellknown explosion in the size of frequent patterns in pattern mining field. It reduces the huge number of highly redundant frequent patterns to only a small number of high-quality patterns.

However, KRIMP has some drawbacks originated from its simplicity. The first one is its input: the pre-mined set of candidates. This candidate set is often very large (millions of patterns), thus merely mining, sorting, storing them takes lots of time and effort, even before KRIMP can start its duty. Secondly, almost all of patterns will be rejected, very few patterns (out of millions) will be selected. Thus spending time checking a pattern while knowing the pattern is rejected with 99% probability is somehow irony. Lastly, KRIMP is a rough greedy heuristic approach, it considers each candidate only once, in a static order thus it sometime rejects candidates that could be useful later.

SLIM Algorithm

Unlike KRIMP, SLIM [START_REF] Smets | SLIM: Directly mining descriptive patterns[END_REF] does not need to start with a set of itemsets. Instead, SLIM adopts a bottom-up approach: it slowly add new itemset, which is a combination of current itemsets of the code table.

Algorithm 2 The SLIM Algorithm

Input: A database D Output: A heuristic optimal code table CT 1: CT ← ST 2: for each candidate F ∈ {X ∪ Y : X, Y ∈ CT } do 3: CT c ← (CT ⊕ F ) 4: if L(D, CT c ) < L(D, CT ) then 5:
CT ← post-prune(CT c ) The order of inserting candidate into the code table CT is exactly the same as with KRIMP case: first descending on length, second descending on support, and third in alphabet order. But the order of considered candidates is different, since there is not set of candidates in SLIM algorithm. This order is determined based on the gain in bits of the newly created code table: whatever pair X, Y ∈ CT that gives the highest gain when putting in the code table will be considered first. The most straightforward tactic is to calculate all gains for every possible candidates, and just select the best one. However, this approach is computationally expensive, since to compute the gain for a certain candidate, the whole database must be scanned.

One approach to partly solve this difficulty is to roughly estimate all the gains of all candidates first, and only calculate the exact gains for top-k candidates. The priority is finding an easily calculable estimate. Let X and Y be itemsets in CT , CT be the code table after adding X and Y (i.e. CT = CT ⊕ X ∪ Y ), ∆L be the difference in encoded size between CT and CT :

∆L = ∆L(CT ⊕ X ∪ Y, D) = L(CT, D) -L(CT ⊕ X ∪ Y, D) = [L(CT |D) + L(D|CT )] -[L(CT ⊕ X ∪ Y |D) + L(D|CT ⊕ X ∪ Y )] = ∆L(CT ⊕ X ∪ Y |D) + ∆L(D|CT ⊕ X ∪ Y )
Before developing this equation into details, several brief notations need to be defined for the sake of simplicity. Lower case, x, of an item X is used to indicates usage(X) in the code table

CT , x is usage(X) in the code table CT (= CT ⊕ X ∪ Y ).
s is the sum of all usages in CT , i.e. s = X∈CT x. Similarly, s is the sum of all usages in the code table CT . Consequently, many elements in two above equations will eliminated themselves, the rest can easily be shorten using following relations: x = x -xy , y = y -xy , and s = s -xy . In the end, a very easily calculable estimate is obtained by making use of a simple assumption.

The most attractive feature of SLIM is that it doesn't need a pre-mined set of candidates. This feature alone saves lots of time for mining, storing. . . patterns. Considering the same dataset, the number of candidates examined by SLIM is often much smaller than the size of the candidate set of KRIMP. Sometimes, SLIM might scan more candidates than KRIMP, and the reason usually is SLIM considers itemsets at lower support than KRIMP can handle.

SLIM doest not work well with sparse database. Both KRIMP and SLIM prefer dense data, in which finding structure seems easier.

Converting Image Descriptors into Binary Vectors

As explained before, our aim is to use existing pattern mining techniques on video datasets. Our first problem is thus to convert the original image representation into a suitable transactional or binary dataset usable by a pattern mining algorithm. In the rest of this document, we will mainly use SIFT-BOW histograms to describe the frames of our videos. We thus focus on the methods to convert such histograms into binary datasets. A SIFT-BOW histogram can be seen as a vector where the dimension is the number of visual words chosen during the BOW construction (see 1.1.1.4) and the value of each vector element (or bin) is the number of occurrences of the corresponding visual word in the considered image region.

The most naive way to do this conversion is to turn all different-from-0 values into ones, and keep the "0" values untouched. This discretization technique is denoted Simple-Binarization (SBin) in the rest of this manuscript. One variant is fixing the number of "1" by converting only top-K values into "1", and the remaining values into "0" [START_REF] Voravuthikunchai | Histograms of pattern sets for image classification and object recognition[END_REF]. However, we can notice that this procedure remove a lot of information. The B2S (Bag-to-Set) representation [START_REF] Kim | Disiclass: discriminative frequent pattern-based image classification[END_REF], in which all the frequency information of the histograms is kept, is another approach. Its name comes from the initial idea: In [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF] the authors chose another approach that we call Sparse-B2S (or SB2S) which is quite similar to B2S, but instead of using consecutive values "1" with "0" endings, they use only one value "1" and the rests are "0" for one bin. With the same example as above, the corresponding binary code is [001 10 0001 000 0100]. Moreover, if, for a given location, a value is never used in any histogram, the corresponding digit will always be a 0. It can thus be removed. For instance, if there is no histogram with value 3 at position 3, then the binary code is finally A SB2S = [001 10 001 000 0100].

The different approaches are shown in Figure 1.14.

Pattern Mining applied to Computer Vision

Even though frequent itemset mining techniques and variants thereof are well-established in the data-mining community [START_REF] Uno | LCM ver. 3: collaboration of array, bitmap and prefix tree for frequent itemset mining[END_REF], they are, to date, not commonly used in state-ofthe-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].

Frequent pattern mining techniques have been used to tackle a variety of computer vision problems, including image classification [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF][START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Yuan | Mining discriminative cooccurrence patterns for visual recognition[END_REF], action recognition [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],

scene understanding [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF], object recognition and object-part detection [START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF].

In the context of pattern mining-based image classification, local bag-of-words are usually preferred (e.g. in [START_REF] Kim | Disiclass: discriminative frequent pattern-based image classification[END_REF][START_REF] Quack | Video mining with frequent itemset configurations[END_REF][START_REF] Sivic | Video data mining using configurations of viewpoint invariant regions[END_REF]), since they result in sparse representations, a better signal-to-noise ratio, an increased robustness to image clutter and some low level spatial information (proximity). Spatial configuration mining based on local BOW was first shown by Quack et al. [START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF]. More structured patterns such as sequences and graphs capturing the spatial distribution of visual words have been used by [START_REF] Nilsback | Automated flower classification over a large number of classes[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 pattern mining.

Voravuthikunchai et al. [START_REF] Voravuthikunchai | Finding groups of duplicate images in very large dataset[END_REF] make use of closed frequent patterns to detect duplicate images in a very large dataset of one million images. 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 cooccurrence patterns for visual recognition[END_REF] high level features such as attributes [START_REF] Farhadi | Describing objects by their attributes[END_REF]

Current Tagging Methods

As explained in the introduction, our aim in this thesis is to automatically complete and correct tags provided by users for a given video uploaded on the Internet (e.g. on Youtube). According to [START_REF] Wang | Assistive tagging: A survey of multimedia tagging with human-computer joint exploration[END_REF], automatic tagging methods in which a computer provides or helps a user to provide tags for some given multimedia content can be referred to as assistive tagging methods. The authors of [START_REF] Wang | Assistive tagging: A survey of multimedia tagging with human-computer joint exploration[END_REF] divide the tagging tasks into 3 categories: 1) tagging with data selection and organization, which consists in organizing the data in such a way that only a small subset of it should be manually tagged to get some global information; (2) tag recommendation, which consists in suggesting relevant tags to a user while he is tagging his/her own video; and (3) tag processing, which consists in refining human-provided tags or adding more information to them. Our tagging problem relates to this last category.

Besides, the authors of the previously mentioned survey ( [START_REF] Wang | Assistive tagging: A survey of multimedia tagging with human-computer joint exploration[END_REF]) are covering several types of multimedia content ranging from images to videos through music and speech.

In this thesis, we focus on the video tagging problem. A video in itself (as opposed to images) contains multiple sources of information such as its metadata (i.e. texts embedded in videos which generally consist of a title, a list of authors, a copyright, etc.), an audio channel, sometimes a transcript (which can be obtained by speech recognition or by optical character recognition from caption texts) and the visual content included in the frames themselves which is temporally structured. In this thesis, we will only rely on the visual content of the frames and on the tags provided with the video. In this context, algorithms used on images and on videos mostly differ in the feature extraction and representation stages since both videos and images are often ultimately represented as feature vectors. Consequently, most tagging techniques in images processing can be safely applied to video tagging.

Assistive tagging methods are at the crossroad between automatic tagging and manual tagging methods. In the following, we thus first focus on automatic tagging methods and then on specific assistive ones in Section 1.3.3.

Comparing Videos

Even though a video is considered as a sequence of images, video comparison is a completely different problem from the image comparison one. Because each video has a different length, and also because the length of each scene/shot is different, the representations of different videos are usually not comparable. For example, when one wants to classify videos using a SVM classifier or cluster them using e.g. a k-means clustering algorithm, the inputs of the algorithms must have the same dimensions.

Whenever one wants to process videos, comparing videos is a mandatory step. Taking the average of the characteristics of the keyframes, comparing pairs of keyframes and make use of the identical frames are the three main trends to compare videos. The first naive method to compare videos is to average the descriptors of each keyframe extracted from the video (see Section 1.1.2 for the keyframe extraction) to produce a single representation for the whole video. This method is used, for example, in [START_REF] Toderici | Finding meaning on youtube: Tag recommendation and category discovery[END_REF] and [START_REF] Yang | Discriminative tag learning on youtube videos with latent sub-tags[END_REF] where a single bag-of-word histogram is produced and thresholded to remove potential noise in the video. In all cases, classical distance function such as the L1 or L2 distances can be used to estimate the similarity between videos. Even if this method is computationally effective, one loses a lot of the available information by averaging all the frames as can be seen in Figure 1.15. We nonetheless tried this method in our framework.

Averaging

Pairwise

The second most used method consist in measuring the similarity between two videos as the maximum of the pairwise similarity between two key-frames of those two videos (see e.g. [START_REF] Moxley | Video annotation through search and graph reinforcement mining[END_REF]). In other words, this method uses the similarity between the two most similar frames of two videos to represent the similarity between the videos themselves.

Again, the comparison of the two videos is made using a unique pair of frame and no sequential information is taken into account.

Automatic Tagging

Video annotation (and in particular tagging) and video classification are two very popular problems in video analysis. They are related to each other (so they are often described interchangeably) even if the video annotation problem can be considered more general than the second one. The video classification problem consists in assigning to videos some pre-defined categories or classes (e.g. news or football ). Video annotation consists in assigning to shots or video segments some pre-defined more general semantic concepts, such as person, sky, people running. Both problems share similar solving approaches: first, one needs to extract low-level features and then train some classifiers to map the features to the categories/concepts. The two problems of video indexing and video retrieval are also related to the above problems. In the video retrieval task, a query is given by a user and the retrieval system must effectively and accurately return the videos that match the query. To get this effective retrieval, a good indexing is needed which makes the two tasks dependent on one another. Besides, to match the results with the query, the retrieval system needs to compare the query with the meta-data of the already stored videos. This comparison is often made using distance functions which are also at the core of the machine learning methods used to solve the first two problems mentions. The methods presented in this section will thus cover all these different applications.

Automatic Tagging Benchmarks for Videos

The most common benchmarks used to evaluate automatic tagging methods (for video annotation, classification, retrieval or indexing) come from the TRECViD (Text Re-trieval Conference specialized on Video Retrieval Evaluation) competition [START_REF] A F Smeaton | Evaluation campaigns and TRECVid[END_REF]. The TRECViD campaign, sponsored by NIST (National Institute of Standards and Technology) since 2001, focuses on research related to videos. During each year competition, a large number of video collections is provided together with a number of tasks. These tasks are proposed by both NIST and participants and they are gradually changing over time depending on the needs of community: tasks with very few participants are eliminated, and tasks attracted to video researchers are added. TRECViD 2013 [START_REF] Over | Trecvid 2013 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF] had 5 main tasks: semantic indexing, interactive surveillance event detection, instance search, multimedia event detection, multimedia event recounting. As explained before, most algorithms used to tackle these tasks are relevant for our auto-tagging problem.

Note that there are many more benchmarks available in the context of image classification and retrieval but, as they do not consider videos, they are not specifically presented in this chapter.

Model-based methods

One of the most widely applied method for automatic tagging consists in learning a model for each tag (or learn a multi-class classifier) based on a trustworthy training set and use these models to predict the tags of new data. It is thus seen as a binary classification problem. The model can be learned using any learning algorithm.

However, most state-of-the-art papers claim a better accuracy using the well known Support Vector Machines (SVM) [START_REF] Dumais | Inductive learning algorithms and representations for text categorization[END_REF] Recent methods [START_REF] Yang | Effective transfer tagging from image to video[END_REF][START_REF] Yang | Robust semantic video indexing by harvesting web images[END_REF] have also studied how information learned from images (that are often easier to label) could be transferred to videos using a transfer learning algorithm. Using the same approaches, one can also detect events (i.e. series of concepts) in videos [START_REF] Duan | Visual event recognition in videos by learning from web data[END_REF][START_REF] Ulges | Learning automatic concept detectors from online video[END_REF]. This problem is called Concept-based event detection .

In the same context, Merler et .al [START_REF] Merler | Semantic model vectors for complex video event recognition. Multimedia[END_REF] introduced semantic model vectors which is an intermediate semantic representation between low-level features (SIFT) and high-level events (playing football). The authors propose to train hundreds of concept detectors from a collection of thousands of labeled web images represented by a concept vector.

A linear SVM classifier is then trained to recognize events from these concept vectors.

[37] focuses on the relationship between concepts and events, it studies to find a way to create an effective vocabulary (list of concepts) for event detection task.

Note that these methods suffer for one essential drawback: the number and the name of each tag has to be known in advance and one has to obtain a sufficient amount of tagged videos to train a classifier with each of these tag.

Nearest neighbors-based methods

Nearest neighbors-based methods predict the tags of a new example by comparing it to its nearest neighbors (NN) in the training sample. For example, Makadia et .al [START_REF] Makadia | A new baseline for image annotation[END_REF] pioneered this approach by constructing a NN-based baseline for image classification task. They introduced a simple method to propagate n tags to a test image from its visual neighbors: taking almost all tags from the closest image, and if there is still not enough n tags, they rank tags of the remaining neighbors and select top-ranked tags.

Later, Guillaumin et .al [START_REF] Guillaumin | Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation[END_REF] learned a weighted nearest neighbor model where a weigh π ij denotes the relevance of image j for predicting the tags of image i. These weights can be rank-based (π ij depends on the order of image j in neighborhood of image i) or distance-based (π ij depends on the distance between image j and i).

Again, all aforementioned methods need a training set with a sound ground truth i.e. the tags are not questioned and thus do not need any refinement. The main advantage of these approaches is that one does not need to know the tags in advance nor learn a particular model for each tag.

Tag Processing

As explained before, this section is devoted to techniques that are at the crossroad between automatic tagging and manual tagging methods. Our work relies on the fact that even if tags are often associate with web videos, or large-scale video collections, they are still often incomplete and incorrect. However, by refining noisy tags, adding new ones and removing irrelevant ones, the performance of tag-based search can be greatly improved according to [START_REF] Liu | Image retagging[END_REF]. For example, associating a tag with some information about the shot it refers to in the video (and thus have sequential information over the tags) can be of great value to improve retrieval tasks as shown in [START_REF] Wang | Active learning in multimedia annotation and retrieval: A survey[END_REF].

Another strategy consists in applying the automatic-tagging strategies mentioned above without relying entirely on the existing labels of the images/videos. For example, in [START_REF] Chen | Tag-based web photo retrieval improved by batch mode re-tagging[END_REF], each SVM classifier is trained for each tag from the loosely labeled samples.

These classifiers return an initial relevance score of the tags with respect to a picture.

The score is later refined based on the similarity between images and semantic relations of tags. For example, Liu et .al [START_REF] Li | Learning social tag relevance by neighbor voting[END_REF] use a nearest neighbor algorithm (voting system) in the visual neighborhood of an image to predict the relevance scores of some tags.

They later extend their work to multiple visual feature spaces (i.e. global features, local features. . . ) in [START_REF] Li | Unsupervised multifeature tag relevance learning for social image retrieval[END_REF]. Another example can be found in [START_REF] Uricchio | An evaluation of nearest neighbor methods for tag refinement[END_REF] where the author evaluates multiple nearest-neighbor approaches for tag refinement tasks.

Our aim is to take advantage of the nearest neighbor-based method and of the tags manually provided by users to improve the relevance of the tags in a video dataset. The method proposed in the following chapters can be seen as a nearest neighbors-based method on the visual content of the videos which take into account the uncertainty on the tags to propagate tags from the neighborhood videos.

Chapter 2

Our Tagging Framework we do not present any contribution on this particular step, we rely on some existing keyframe extraction algorithms (e.g. [START_REF] Dirfaux | Key frame selection to represent a video[END_REF]) or on the data provided by the authors for some benchmark datasets. In the second step, some classical visual features (in our case we rely on SIFT-BoW) are computed to describe the keyframes. We then propose to build more discriminant mid-level features from the SIFT-BOW using some itemset mining techniques. In step 3, the new mid-level features are used to compare the videos for the auto-tagging problem. The most relevant distance functions are discussed in this chapter. Finally, in step 4, tags are propagated from one video to others based on the visual similarity computed between the videos and the overall distributions of the tags in the dataset.

Parameters Evaluation

As explained in the previous chapter, one of the difficult part of this thesis is the lack of ground truth labels for the video datasets. This is especially true when the aim is not to classify a video with a single label but to tag it, i.e. to give all the tags that are entirely relevant for the video. To carry on with the entire video tagging process we thus choose to validate a number of hypotheses on a simpler, well defined and well studied problem: the image classification problem. In particular we would like to assess 3. (in step 3) we can already choose a good distance function to compare two high dimensional vectors describing a video (or some video frames);

Image Dataset

To validate our hypotheses, we use two well-known image datasets for which supervised label information is provided: the GRAZ dataset [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF] and the Oxford-Flower17 [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF] (some examples are shown in Figure 2. B2S and Sparse-B2S. As explained in Section 1.2, the main problem with pattern mining algorithms is the size of the output. Since our plan is to encode an image using those patterns, the number of kept patterns should not be too large not to suffer from the curse of dimensionality [START_REF] David L Donoho | High-dimensional data analysis: The curses and blessings of dimensionality[END_REF]. In the following, we will first show how to use patterns to represent images. After that, we rely on an existing method to chose some good patterns to answer the questions 1 and 3 asked in the previous section. This method is not usable for our target application since we cannot completely rely on the tag to post-process the patterns. We thus propose some unsupervised alternatives to do this post-processing step. The process is slightly more complex using local histograms (also called local BoW).

Encoding Images Using Frequent Patterns

In this case, one image consists of multiple local histograms (see Figure 2 We evaluate the accuracy of our method using a simple 1-Nearest-Neighbor (1-NN) algorithm with a L1 distance function over the proposed feature vectors (local histograms and FLH). Other distances were also tried and discussed later on. As it was reported to be successful for those two datasets, we also used a SVM with an intersection kernel to assess the results of the KNN classifier.

Table 2.1 reports the mean accuracy over all images in the 2 datasets using the L1 distance function. It shows that our simple setting is competitive with the SVM classifier for both datasets (better for GRAZ and a little bit worse for the Oxford-Flower17 dataset). The Local BOW and FLH seems to bring different information since the accuracy is sometimes better with the FLH (88 vs 79.7 for the GRAZ-Person dataset) and sometimes worse (82.0 vs 80.5 for the GRAZ-Bike dataset). This confirms that the frequent patterns (here FLH) can be interesting features compared to simple bag-of-words if they are carefully chosen. Also the overall good results compared to the SVM classifier confirm the relevance of our features and distance choices. Note that this supervised post-processing step is crucial to select patterns of high quality but it cannot be used in our video tag-correction problem since such class information is not available. In the following, we will thus show unsupervised processing methods to reduce the number of patterns.

Unsupervised Mined Patterns of Oxford-Flower17

Inspired by these positive results, we decided to perform more experiments with the Oxford-Flower17 dataset only using SIFT features since we also plan to use them as a baseline for our experiments on the video datasets. In these experiments, we did not use a SVM classifier nor the FLH patterns to be as close as possible to our video setting. Instead, we used a 1NN approach with a L1 distance function to evaluate the performance of the closed patterns computed directly by the LCM algorithm from both global and local histograms obtained using different binarization techniques. We started by densely sampling points over all images with overlapping patches of 16x16 pixels, and using a step size of 8 pixels (the distance between the centers of two successive patches is 8 pixels). Standard SIFT descriptors are calculated for each patch. A dictionary of 200 visual words is then constructed.

Global Histogram

At global scale, one image is a histogram of 200 visual words. The first step before finding frequent patterns consists in transforming the image histograms into transactions.

Because the value at each bin of each histogram is often significantly larger than 0, using the Simple-Binarization (0 becomes 0, larger than 0 becomes 1) is not recommended. Consequently, we decided to use the B2S and Sparse-B2S binarization approaches detailed in Section 1. To compute the patterns, we first set the lower support of the LCM algorithm to 10 (patterns that appear in less than 10 images out of 1360 images of Oxford-Flower17

might not contain enough information to be considered "good") and the upper support at half the number of images. The intuitive explanation is that if a pattern appears in more than 50% of the images, it is too frequent and thus too general to be a "good" candidate. Using the B2S binarization technique, LCM did not return any frequent patterns after one week running. On the other hand, with the Sparse-B2S binarization technique it returned too many patterns (billions). We try unsuccessfully to lower the upper frequency from 50% to less than 10% but LCM still returned millions of closed frequent patterns after several hours of running. Without any supervised information to post-process the patterns, these numbers were deemed unreasonable to describe an image.

Local Histograms

We then created local histograms as described in Section 1. Using only LCM, we expectedly encountered the same problem as with the global histograms. We arbitrary set the threshold for the upper support to 80000, which means that any selected patterns must appear in less than 80000 transactions (out of about 6 millions). If a pattern appears in more than 80000 transactions and if, on average, it appears 100 times in any images, 800 images would contain that pattern.

Since the dataset has 1360 images in total with 80 images per class, a pattern that is available in 800 images is not a good candidate for discriminate features. We also chose to set the lower threshold to 80 for the same reasons. With these two bounds, LCM returns less patterns than the above global case (there were millions), but these numbers are still too big to be effectively dealt with (see Table 2.2): encoding an image with hundred of thousands patterns leads to extremely sparse representations. The original size of the feature vectors is reduced to a given number of Principal Components (PC). Different number of PC were tried: from 2 to 10, 15, 20, 50, 100, 200, 500,1000, 2000, 5000 when applicable. The number of chosen PC is usually correlated with the explained variance of the dataset which thus can be used to set a reasonable number of PC without using a validation set. When 90% of the variance is explained by the components, one can stop adding new components. Figures 2.5 and 2.6 describe the evolution of the explained variance and of the accuracy with various number of PC. We can see that 100 PC seems a reasonable value to chose. It corresponds approximately to the number of original visual words. In Table 2.1, we chose this particular number of PC value to reduce the number of frequent patterns.

Pattern Reduction Techniques

However, using PCA does not improve the final outcome, the only benefit is reducing the computational expense. Thus, if the original sets of frequent patterns are not good enough, applying PCA is an unnecessary step. 2.3).

Even if these values are larger than the original 200-D BOWs, they are much smaller than when using only the LCM algorithm. Although the SLIM algorithm is designed to keep improving the set of patterns over time, we observed that after running 2 hours, the number of output patterns changes at a slow speed. We thus stop SLIM after three days (one day might be already enough) to have enough relevant patterns.

We further tried to improve the quality of the SLIM output by removing all patterns that are too frequent or too infrequent. The lower threshold is arbitrary selected at one-hundredth, and the upper bound at one-third of the images in the dataset.

Applying these two bounds, the number of SLIM patterns obtained with the Sparse-B2S binarization process is reduced from 5770 to 1651. With the B2S binarization process, it is reduced from 2513 to 415.

As explained before, we encode each image with a binary vector of patterns and evaluate the quality of our pattern encoding using a L1 based neighbors and show the results in Table 2.5. The results show better performance for this image dataset using only one neighbor. These encouraging results demonstrate the relevance of the patterns obtained with the SLIM algorithm from local histograms as new mid-level features to describe an image.

Distance Functions

We evaluated the quality of our patterns using a KNN algorithm with a L1 (Manhattan) distance function. In this section, we question this distance function and compare this distance in classification with the Euclidean distance and the Square root intersection similarity measure between histograms. Various other similarity measures such as the χ 2 , L 1 2 and L 2 3 were also tried but the performance were not satisfactory and are not reported here.

The Manhattan distance between two vectors p = [p 1 , p 2 , . . . p n ] T and q = [q 1 , q 2 , . . . q n ] T is defined as

d(p, q) = d(q, p) = |q 1 -p 1 | + |q 2 -p 2 | + • • • + |q n -p n | = n i=1 |q i -p i |
• The Euclidean distance function (or L2 distance) between two vectors p = [p 1 , p 2 , . . . p n ] T and q = [q 1 , q 2 , . . . q n ] T is defined as

d(p, q) = d(q, p) = (q 1 -p 1 ) 2 + (q 2 -p 2 ) 2 + • • • + (q n -p n ) 2 = n i=1 (q i -p i ) 2
Dist. Function • The square root intersection between two histograms is a disimilarity measure.

SBin

The disimilarity between two vectors p = [p 1 , p 2 , . . . p n ] T and q = [q 1 , q 2 , . . . q n ] T is defined as

d(p, q) = d(q, p) = 1 min(q 1 , p 1 ) + min(q 2 , p 2 ) + • • • + min(q n , p n ) = 1 n i=1 min(q i , p i )
The results are shown in Table 2.6. They show that with a KNN algorithm, the L1 distance seems to be the best strategy to compare vectors of patterns whatever the encoding. This is thus the strategy chosen in the next chapter.

Step 3: Video Comparison

As explained in Section 1.3.1, there are two popular approaches for comparing videos: either taking the average between all the keyframes or doing a pairwise comparison between all the keyframes of the two videos. In this section, we propose an asymmetrical similarity comparison inspired by the video pairwise comparison techniques to increase the relevance of the video comparison. The first step consists in calculating all the pairwise similarities between all the keyframes of two videos. After that, instead of taking the optimum value of all the pairwise similarity scores, we propose to take the average of all maximum similarities corresponding to one video. In other words, for each keyframe of a video A, we search in all the keyframes of video B for the highest pairwise matching score and we keep this value. Then, we take the average of all the computed values for all the keyframes of the video A to return the similarity score of video A towards video B. If we denote A(i) the i th keyframe of A and |A| the number predefined threshold will be considered as suitable tags for the video V . Others tags (with smaller scores) will be deleted if they are available in the original tag list.

For instance, given an arbitrary video and an arbitrary number of neighbors set to 30, we first compute the similarities between this videos and all the videos in the dataset and keep only the 30 most similar ones. If most of these 30 neighbor videos contain a tag that is not present in the original video, then the tag should be added in the video (as it might, with high probability, describe the same content as in the video). On the other hand, if that video includes a tag that does not appear in any of the 30 videos, then that tag might have been intentionally mis-added and should be deleted.

To tag a given video v ∈ V , we rely on the tags t ∈ T of the k most similar videos in its neighborhood. To propagate a given tag t to v, one need to set a threshold on the number of times t should appear in the neighbors. However, given the very different distribution of each tag, we decided to use two comparison statistical tests between the distribution of a tag in the entire dataset and its distribution in the k nearest neighbors.

The first one states that the probability of a given tag should be significantly greater

Chapter 3

Datasets and Tag Propagation Experiment Designs

Our framework is described in details in the previous chapter with some justifications about the parameters we use. In this chapter, we apply this framework to three different datasets with different characteristics. Note that, as explained in the first chapter, there are no dataset with a ground truth available for tag propagation problems (contrarily to classification problems) so, we had to create them manually and design our own evaluation procedure. This chapter presents our attempts in chronological order. The first dataset is a small dataset with 51 videos with few tags. The first idea was to assess if videos sharing the same topic would be visually close to each other and if the tag propagation would be beneficial in this case. However the results were not entirely satisfactory in both cases probably due to the small size of the dataset and the subjectiveness of the tags that were selected. We thus introduced a second 182-videos synthetic dataset created from cutting parts of 7 original videos (with one explicit tag per part) to ensure a strong correlation between the tags and the visual content of the videos. The experiments with this second dataset confirmed the validity of our framework but also showed that global SIFT-BoW features alone do not yield the best results as also confirmed in the previous chapter. The experiments on these first two datasets were carried out before trying the local SIFT-BoW features, therefore, all the results are reported using global features for these datasets. The third dataset is a real and significantly larger dataset with 668 videos and 150 tags. Many strategies with different settings were applied to evaluate our framework on this dataset.

3.1 A First Real Dataset (51 videos)

In the following experiments we use a 51-videos dataset taken from a benchmark dataset including 80, 031 of the most viewed videos for every month from Dec. 2008 to Feb.

2009 on YouTube [START_REF] Cao | MCG-WEBV: A benchmark dataset for web video analysis[END_REF]. We kept this dataset reasonably small to manually assess the relevance of the original tags and of the corrected ones for each video. We are interested in evaluating the interest of the frequent pattern-based features compared to the BOWbased features.

Dataset Description

Each of the 51 videos in our dataset is decomposed into key-frames based on [START_REF] Zhang | Automatic partitioning of full-motion video[END_REF]. An example of the keyframes for some of the videos are given in Figure 3 3.1.

Encoding Procedure

We first tried to find frequent sequential patterns in these videos. Note that in our cases, the original sequences are itemsets which limit the number of algorithms we can use to tackle the problem. We used the SPAM algorithm presented in the first chapter. Some keyframes of an anime video.

Some keyframes of a football video.

Some keyframes of a racing video. This number of patterns is still too large to encode videos without any post-processing step we just decided to abandon this strategy.

We then computed frequent itemsets from the global histograms associated to the 1895 keyframes using the LCM and the KRIMP algorithms as explained in the previous chapter. In both cases, the support threshold is set to

Evaluation Procedure

To evaluate the relevance of our itemsets, we recoded the video using the 82 KRIMP patterns. A video is represented by a histogram of KRIMP patterns where each histogram bin gives the number of keyframes containing a given pattern (as explained in the previous chapter, each pattern is only counted once per frame). To assess if videos sharing the same topic would be visually close to each other, we first did not used the tag and measured the distances between all possible pairs of the 51 videos. We calculated the distance within a class and outside a class. We then evaluate our tag propagation procedure by including the tags for each video as shown in Figure 3.1. To do so, we consider a video dataset as a triplet (V, T, tag)

where V is the set of videos V = {v 1 , ..., v n }, the set of possible tags is

T = {t 1 , ...t m }
and tag is a relation on V × T such that tag(v, t) is true if and only if the video v has the tag t.

Our evaluation procedure is then:

• add some noise on the tags, i.e, we choose a noise proportion 0 < p < 1 and we compute a noisy tag function tag noisy such that, for each t ∈ T and v ∈ V , with probability p we have: tag noisy (v, t) = ¬tag(v, t) (it means that we flip the value of a given tag with probability p);

• apply our tag correction technique, the output of the tag correction step is tag corr ;

• compute the proportion of the incorrect tags after the correction step as:

err(tag, tag corr ) = {(v, t) ∈ V × T | tag(v, t) = tag corr (v, t)} /( V . T )
The ideal case is of course when err(tag, tag corr ) = 0. Notice that err(tag, tag noisy ) ≈ p. This means that as soon as err(tag, tag corr ) < p, there is less incorrect tags after the tag propagation step than before on the noisy set. Therefore it means that our algorithm has decreased the number of incorrect tags. On the contrary, if err(tag, tag corr ) > p, it means that our algorithm has actually increased the number of incorrect tags. In the following figures, we plot the error err(tag, tag corr ) against the value of p. If this curve is below the diagonal line, it means that our algorithm has decreased the number of incorrect tags.

Results

The results on the first 51 videos dataset are presented in Figure 3.2. They are averaged over 100 runs for each noise level. Our algorithm does not improve the original tagging for almost all the noise levels:

the number of incorrect tags is higher after our correction algorithm than before. These errors can be the result of the correction algorithm or the fact that the computed distance between videos does not reflect the real similarity of the videos. The number of videos that we use is quite small. In a dataset of millions of videos (as the complete YouTube repository), the k nearest neighbors of a given video should be much more similar than in our small dataset (and thus have very similar tags).

Another problem lies in the tags themselves: our algorithm uses the visual similarity between videos to correct the tags. Thus, it can be efficient only on tags that are correlated with the visual content. For instance, tags such as "forest" or "sea" can be corrected because they are correlated with the visual content (green). A tag which describes a higher level concept (such as the name of a person in a video or the date when the video was shot) is probably not correlated enough with the visual content.

Synthetic 182 Videos Dataset

Since the results on the above small dataset were not satisfactory because of its too limited size and because of the quality of the tags, we proposed another synthetic dataset of 182 videos build from 7 very different videos from the previous dataset.

Some keyframes of a synthetic video with 3 tags: cat, football, news Some keyframes of a synthetic video with 2 tags: news, crowd Some keyframes of a synthetic video with 3 tags: moon, cat, anime

Dataset Design

To better control the similarity or dissimilarity of the videos and the tags, we build a synthetic dataset made of 182 videos. To construct this dataset, we first select 7 real videos A, B, . . . , G belonging respectively to the classes "moon", "crowd", "anime", "racing", "cat", "news" and "football". Note that if each synthetic video was given one of the tags, the total number of tags would be 182 * 7 = 1274. This means that when adding 5% of noise in the dataset, 63 (≈ 1274 * 5 100 ) tag values would be flipped (added or removed) in the dataset.

Then, to build each synthetic video we:

• choose randomly between 2 and 4 of the real videos;

• choose randomly frames from each of the chosen real videos. The set of frames thus obtained is concatenated to become the new synthetic video;

• tag this synthetic video with A if it contains frames from video A, with B if it contains frames from video B and so on. Each synthetic video has therefore between 2 and 4 tags out of the 7 possible tags.

Examples of some frames used for this dataset are shown in Figure 3.3. By construction, if two synthetic videos share for instance the tag A, it means that they both contain some frames (possibly the same ones) extracted from the real video A. Thus, we ensure that they contain similar frames. Moreover, by construction, each tag is correlated with the visual content of the video. We therefore avoid the last problem encountered with the previous small dataset. The design of this dataset allows us to build a perfect measure to assess the visual similarities between the videos. Suppose that a first video contains 3 tags A,B and C and a second video contains 4 tags A,D,E and F. The similarity between these two videos is defined as the number of common tags divided by the largest number of tags in the two videos i.e. similarity(ABC,ADEF) = |A| |ADEF | = 1/4. Intuitively, it means that ABC and ADEF have at least 1/4 of their keyframes that are similar (here with tag A). The distance between the two videos is the inverse of this similarity. This "ideal" distance function will be used as our baseline in the following experiments when computing the KNN matrix. Apart from this baseline, we use the same evaluation procedure as in Section 3.1.3.

Evaluation Procedure

Results

Figure 3.4 shows the tag propagation performance using the SIFT-BoW features and the L1 distance function between the histograms of patterns. In Figure 3.4, the lower the lines are, the more labels are corrected during the tag propagation process. We use two vocabulary size for the BoW: 400 and 2000 but obtain almost the same results (blue and green lines). The ideal case line is lower than our L1 distance function using the SIFT-BOW features. This means that these features or this distance function can still be improved to obtain a better tag propagation system. Figure 3.5 shows that the results for this dataset are however a lot better than with the simpler dataset presented in the previous section. For a noise level between 0 and 30%, we see on Figure 3.5 that the proportion of incorrect tags significantly decreases.

For instance, at a noise level of 20%, the error proportion after the tag correction is around 16%. This means that the algorithm has removed about one quarter of the errors introduced by the noise. Note that for a higher noise level, the number of incorrect tags is too important to hope improving the results by tag propagation. The number of neighbors considered for the tag propagation and the statistical tests are directly responsible for the propagation (or the removal) of a tag. To evaluate our choices experimentally, we selected a frequent tag ("amanda") in our video and 4 videos that should not be tagged with this particular tag 1 . Fig. 3.8 shows the number of nearest neighbor videos that contain the tag "amanda" for the 4 different videos (plain lines). It also shows how many nearest neighbor videos should contain the tag "amanda" to trigger the propagation step (dashed line). Since the tag should not be propagated to these videos, the plain lines should stay below their corresponding dashed line. This is correct for all 4 out of 4 videos for 30 nearest neighbors. It is not correct anymore when increasing the number of neighbors. This means that for this particular tag, increasing the number of neighbors will actually degrade the propagating system.

Other similar experiments tend to confirm the relevance of choosing 30 neighbors. 1 Amanda Holden is a TV show presenter that is often present in our video samples. both the local and global information into account.

Experiment Settings

As shown in the experiments using the image datasets (see Section 2.2.4.2), the global visual features (one histogram per image) do not provide enough information to obtain discriminant patterns after the mining phase. Therefore, we only implemented the local visual features (as explained in Section 1.1.1.4) with this real video dataset. Each keyframe is represented as multiple local histograms, and we constructed a dictionary of 1000 visual words. We choose this value which is significantly larger than the 200 visual words vocabulary that was used for the image datasets because of the larger number of keyframes (around 14000).

From this 668 videos and from the local SIFT-BOW feature vectors computed from the keyframes we created a dataset of about 6, 000, 000 local histograms. To reduce the computational load, we use the Simple Binarization strategy introduced in Section 1.2.3. or should contain the tag "amanda" to trigger the propagation step (dashed line) according to the number of nearest neighbors for 4 different videos. A video is described using an average of the histograms representing all its keyframes. The keyframes are described using one global SIFT bag-of-words. The videos are compared using a L1 distance function.

Consequently, the input data used for the data mining algorithms consists of 6, 000, 000 transactions where each transaction is a binary 1000-D vector. Different strategies were implemented to try to extract the most valuable frequent patterns and shown in Figure 3.9. In fact, a fifth strategy which consists in applying the SLIM algorithm directly from the 6 millions transactions (running for two weeks) was tried but the final results presented in Figure 3.10 were not better than the baseline. This strategy was thus abandoned.

As in Figure 3.9, we separate all experiments into two parts: one where do not use the tag information and another where we do.

Finding Patterns Without Tag Information

We run the LCM algorithm using the protocol described in Chapter 2 without any supervised information. The minimum frequency threshold used is 500 which is the lowest value we can set to be able to post-process the results in a reasonable amount of time and within a reasonable amount of memory (lower than 20 GB).

We compute both closed and maximal frequent patterns. The LCM algorithm returns about 700, 000 closed and 550, 000 maximal frequent patterns (these numbers are rounded for the sake of readability). These values are, not surprisingly, too large Figure 3.9: Four different strategies to obtain a discriminant set of frequent patterns. The two first ones use first the LCM algorithm on the dataset and compute the maximal or the closed patterns. Then the patterns are post-processed to keep the emerging ones (using the tag information) and further post-processed using the SLIM algorithm. In the third and fourth strategies, the tag information is not used. to be used directly for image encoding and thus, a post-processing step is needed to significantly reduce them.

Without any supervised information, we rely on SLIM MDL-based optimization criterion to find a reduced interesting set of patterns from the set of frequent patterns output by LCM. This means that the output from SLIM is a set of higher order patterns not a set of patterns build directly from the visual words. There is no straightforward around 10, 000 (6M/668) local histograms so each tag belonging to a video will appear in at least 10, 000 transactions.

We then use the tag information integrated into these classic frequent patterns to keep only the discriminant patterns. We use a method very similar to the one used for emerging patterns in a classification problem [START_REF] Dong | Efficient mining of emerging patterns: discovering trends and differences[END_REF]. We call F req in the frequency of a pattern FP only considering the transactions containing the tag T, and F req out the frequency of the pattern FP in all transactions that don't contain the tag T. We define a pattern FP as relevant for a certain tag T if F req in is 5 times larger than F req out . This simple strategy reduces the number of patterns significantly: there remains 34, 000 closed and 90, 000 maximal patterns. We then remove the tag information out of all patterns and apply the SLIM algorithm to post-process them further. SLIM returns 500 closed and 700 maximal patterns. Finally, we perform the tag propagation using these patterns as the main visual features for representing our videos.

Results

Figure 3.11 shows the results for the 5 experimental settings described above. Note that using less than 30 neighbors questions our statistical tests. On the contrary, using 100 videos out of 668 clearly introduces a lot of noise. The best results are obtained using the combination of LCM (closed), SLIM and the tag information (output 1 of Fig. 3.9). In this case for 30 neighbors, the system is able to produce around 65% of good corrections which means that 54 correct tags were added or deleted in the process (28 were wrong propagations). For the same setting, the baseline only allows us to produce 57% good corrections. Figure 3.12 and 3.13 focus on the baseline and the best case. It also shows the results when both vectors are concatenated. The concatenation produces worse results than the best case which means that the information given by the baseline is not complementary to the information given by the frequent patterns. Figure 3.14 shows a comparison between our proposed asymmetrical similarity measure and the basic method which consists in simply averaging for one video all the keyframe features and computing an histogram intersection between the feature vectors representing two videos. Our proposed method does give better results but the difference is not significant using 30 neighbors. The frame average method may thus be preferred for efficiency reasons.

Conclusion

We have presented the design of 3 datasets and the experiments conducted with the system described in the previous chapter to automatically correct and complete tags in a video dataset. The experiments show that the size of the dataset should be important enough for the system to be accurate. The experiments also show that the whole system greatly depends on the choice of the original features and on the encoding of the videos.

However, the experiments on the last bigger dataset showed that relying on good visual Local frequent patterns generation. Then, we have extracted frequent patterns in the set of transactions representing the videos. We use the existing LCM implementation to extract classic closed and maximal frequent patterns. However, the number of patterns is often extremely large (millions of patterns), and they can not be directly used to encode images or videos. By applying the minimum description length principle and combine it with some heuristic approaches (as done in by the KRIMP and SLIM algorithms), we are able to significantly reduce the number of patterns. We also make use of tag information to keep emerging patterns (in our case, patterns that are 5 times more frequent in the set of video having a given tag than in the set of videos without the tag). With this process, we succeeded in finding better mid-level visual features for a better propagation process. However, we have demonstrated that finding good patterns without supervised information is still a challenging problem. We tried different approaches of selecting the patterns without using the initial tag information but all these results are only comparable with the results obtained with primitive visual features.

Local is better than global. The experiments with the image dataset Oxford-Flower17 show that local features have more potential than global features when applying data mining tools: all global results are worse than our baseline, while all local results are better than the baseline (see e.g. Table 2.3 for global results, and Table 2.4 for corresponding local results). Moreover, with local histograms, the binarization is easier to implement without losing information.

Distance functions and video comparisons. Multiple distance functions, from simple the L1 distance to the more complex intersection kernel, are examined. With a pre-defined distance function, comparing two keyframes is effortless since a keyframe is often encoded as a vector. To compare two videos represented as a set of vectors we tried multiple comparison methods: from simply taking the average of all keyframes, to an asymmetric pairwise distance which compare all pairs of keyframes of two videos.

The simplest method is often selected for its good tradeoff performance/computation time.

Tag propagation procedure. We have presented an intuitive scheme to propagate the tags mainly based on the neighborhood of the videos. Our method takes into account both the global impact (the tag's distribution at the dataset level) and the local impact (the tag's distribution in the video neighborhood) when making the propagation decision. A tag of a video is removed if it never appears in the neighborhood of that video.

Dataset and evaluation. Due to the lack of properly labeled datasets and evaluation procedure, we have created multiple datasets, each one for a different purpose.

By using a synthetic dataset in Chapter 3, we undoubtedly prove that there is room for improvement towards primitive visual features like SIFT-BoW. With wisely chosen visual features, it is possible to construct a better neighborhood with really similar videos and thus obtain better propagated tags. The next video dataset of 668 videos with 150 tags is used to demonstrate our framework's effectiveness: considering 40 neighbors, the baseline returns 44% of good corrections while our patterns returns 64% of good corrections (see Figure 3.12). The size of our video datasets is still not comparable to, e.g. the number of Youtube videos but they are large enough to illustrate the complexity and difficulty of our problems.

Future Works

Working with a bigger dataset. 668 videos are a large number of videos, but this obviously does not reach the scale of video-sharing websites. Thus, using our framework on a bigger dataset is a straightforward perspective. With a larger number of videos, we expect to be able to find more similar videos while keeping the same number of nearest neighbors, which in return might increase the performance of the propagation step. However, with a larger dataset, several problems arise: visual words generation uses a clustering algorithm that may become intractable when the number of SIFT descriptors is too large. One way to solve this problem is to use a subset of the SIFT descriptors in this phase. Pattern mining itself can also become problematic, even if current mining algorithms scales well with respect to the number of transactions (and the number of attributes does not increase). Finally, the distance function between videos is expensive and we must compute, for each video, its nearest neighbors. In our experiments, we used a naive quadratic procedure to compute this neighborhood and this would not be tractable with millions of videos.

Incremental video dataset. Large video datasets are often build in an incre-mental fashion (In Youtube for instance, thousands of videos are added daily). Thus, being able to correct the tags of the videos as they are added would be a significant improvement on our framework. Given the visual features, it is easy to compute the description of a new video using them. Then, computing the nearest neighbors would still be a significant challenge. But how can we update the visual features that are used to describe our videos as new videos arrive ? If the new videos are very different than the videos already in the dataset, it would probably be interesting to update the visual features. However, doing so would imply to recompute the descriptors of all videos (including those already in the dataset), recompute all the neighborhoods and update the tags. The cost of such an operation would probably makes it impossible if done in a naive way.

Using different visual features. In this thesis, we tried with only one primitive visual feature: SIFT-BoW. Applying the same principle with different visual features might return better results. There is no limitation on choosing the primitive features to represent the videos, therefore high level features, such as human faces, car's wheel. . . can also be good candidates.

Applying sequence pattern mining. Even if we tried several sequence mining methods unsuccessfully (Section 3.1.3), applying sequence mining into videos feels so natural since a video is basically a time series data. With current sequence mining algorithm, the number of output patterns grows too fast, and they are often redundant.

By developing a SLIM-like sequence mining method, it might become possible to mine a reasonnable number of discriminative sequence patterns in videos. These patterns could then be used either alone, or combined with non sequencial patterns in our framework.

  3.1 A First Real Dataset (51 videos) . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Dataset Description . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Encoding Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Evaluation Procedure . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Synthetic 182 Videos Dataset . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Dataset Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi CONTENTS 3.2.2 Evaluation Procedure . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 A second real dataset (668 videos) . . . . . . . . . . . . . . . . . . . . . 3.3.1 Building Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Evaluation Procedure . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Experiment Settings . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3.1 Finding Patterns Without Tag Information . . . . . . . 3.3.3.2 Finding Patterns With Tag Information . . . . . . . . . 3.3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Conclusions and Future Works 4.1 Contributions & Conclusions . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References vii List of Figures 1.1 Knowledge Discovery in Databases (KDD) Process . . . . . . . . . . . . 1.2 An example of color histogram in RGB space. (source: [34]) . . . . . . . 1.3 Interest points (left) and dense sampling points (right). . . . . . . . . . 1.4 Gradient magnitude and orientation of a patch. . . . . . . . . . . . . . . 1.5 8-bin orientation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 128-D vector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Building bag of visual word. . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Building local BOW features. . . . . . . . . . . . . . . . . . . . . . . . . 1.9 An example of apriori principle based pruning. (source: [69]) . . . . . .

2. 1 52 2. 8 58 3. 2 62 3. 4 64 3. 6 67 3. 7 68 3. 8 69 3. 9

 1528582624646677688699 The Overall Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Class examples of Oxford-Flower17. . . . . . . . . . . . . . . . . . . . . . 2.3 Image representation from global histogram (global BoW) using frequent patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii LIST OF FIGURES 2.4 Image representation from local histograms (local BoW) using frequent patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5 Explained Variance according to the number of Principal Components . 47 2.6 Accuracy given by the 1-NN algorithm according to the number of Principal Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.7 A dense line is a distance from the one keyframe on the left to the most similar keyframe of the right video. The distance from the left video to the right video is the average of three dense lines. . . . . . . . . . . . . . An example of tag propagation: tag Harry Potter should be removed because it does not appear in the neighborhood, and tag football should be propagated because it appears in 5 over 6 neighbors. . . . . . . . . . 53 3.1 Several example keyframes of the 51-videos dataset. . . . . . . . . . . . Result of our tag correction algorithm on the small real video dataset. Our algorithm uses only bag of word features (solid line) or histograms of both words and frequent patterns (dotted line). . . . . . . . . . . . . 61 3.3 Several examples of keyframes of the synthetic 182 video dataset along with the tags associated with the video the keyframe belongs to. . . . . Percentage of wrong tags in the videos after one propagation step according to the percentage of noise introduced. The blue and green lines give the results of our method which compare histograms of SIFT-BOW using a L1 distance function. The red line gives the result of the propagation step starting from an ideal visual comparison. . . . . . . . . . . . 63 3.5 Percentage of wrong tags in the videos after one propagation step according to the percentage of noise introduced computed on a synthetic video dataset. Our algorithm uses only SIFT-BOW features, frequent patterns or both. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Distribution of the 150 kept tags over the 668 video dataset (top), and, for each video in the dataset, over all its 30 nearest neighbors videos (bottom). The nearest neighbors are computed using the SIFT-BOW baseline and the L1 distance function. . . . . . . . . . . . . . . . . . . . Several examples of keyframes of the real 668 videos dataset along with parts of the original tags and the complete pre-processed tags associated with the video the keyframe belongs to. The result of the tag propagation using our system and the tag ground truth is also given for these keyframes. Number of nearest neighbor videos that contain (plain line) or should contain the tag "amanda" to trigger the propagation step (dashed line) according to the number of nearest neighbors for 4 different videos. A video is described using an average of the histograms representing all its keyframes. The keyframes are described using one global SIFT bag-ofwords. The videos are compared using a L1 distance function. . . . . . . Four different strategies to obtain a discriminant set of frequent patterns. The two first ones use first the LCM algorithm on the dataset and compute the maximal or the closed patterns. Then the patterns are post-processed to keep the emerging ones (using the tag information) and further post-processed using the SLIM algorithm. In the third and fourth strategies, the tag information is not used. . . . . . . . . . . . . . 70 3.10 Percentage of good corrections according to the number of neighbors after one propagation step using a SIFT-BOW video encoding (baseline) and an encoding based on SLIM patterns derived directly from SIFT-BOW. The dataset is the 50 ground-truth sample taken from the 668 real video preprocessed dataset. . . . . . . . . . . . . . . . . . . . . . . . 71 3.11 Percentage of good corrections according to the number of neighbors in 50 videos represented with SIFT-BOW (baseline) and frequent patterns obtained LCM(closed and max)+SLIM and LCM(closed and max)+ SLIM+ tag information. . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.12 Percentage of good corrections according to the number of neighbors for a video dataset represented with 3 different features: SIFT-BOW (baseline) and frequent patterns obtained with LCM(closed) + SLIM + tag info, and the concatenation of both feature vectors. . . . . . . . . . 73 3.13 Percentage of good corrections when counting only the addition (dashed line with +), the deletion (dashed line with •) and both according to the number of neighbors for a SIFT-BOW (baseline), LCM(closed) + SLIM + tag info and the concatenation of both feature vectors. . . . . . . . . 74 3.14 Percentage of good corrections to the number of neighbors for a video

Figure 1 . 1 :

 11 Figure 1.1: Knowledge Discovery in Databases (KDD) Process

Figure 1 .

 1 2 shows an example of a color histogram. In the specific context of automatic tagging, color moment (together with other features)

Figure 1 . 2 :

 12 Figure 1.2: An example of color histogram in RGB space. (source: [34])

Figure 1 . 3 :

 13 Figure 1.3: Interest points (left) and dense sampling points (right).

Figure 1 . 4 :

 14 Figure 1.4: Gradient magnitude and orientation of a patch.

Figure 1 . 5 : 8 -

 158 Figure 1.5: 8-bin orientation.Figure 1.6: 128-D vector.

Figure 1 . 6 :

 16 Figure 1.5: 8-bin orientation.Figure 1.6: 128-D vector.

Figure 1 . 7 :

 17 Figure 1.7: Building bag of visual word 2 .

Figure 1 . 8 :

 18 Figure 1.8: Building local BOW features.

Figure 1 . 9 :

 19 Figure 1.9: An example of apriori principle based pruning. (source: [69])

Figure 1 .

 1 Figure 1.10: Breadth-first search vs Depth-first search approaches. (source: [69])

  1) in which L(M ) is the length of the description of M , and L(D|M ) is the length of the description of the data D when encoded with M . Both are measured in bits. In order to apply MDL to the pattern mining scenario, three questions need to be clarified: what the models M are (and in particular a model M ∈ M), how can M describe a database, and how can M and D be encoded in bits. These 3 questions can be paraphrased as: what is M , what is D|M , and how are L(M ), L(D|M ) calculated.

Figure 1 .

 1 Figure 1.13: A example of Standard Code Table with its cover and encoded length derived from the database shown in Figure 1.12. (source: [96])

Applying equation 1 .

 1 3 into the first element, and performing suitable transformations, we end up with:∆L(CT ⊕ X ∪ Y |D) = log xy -L(X ∪ Y |ST ) + C∈CT log c c + |CT | log s -|CT | log sLikewise, applying equation 1.2 into the second element, we have:∆L(D|CT ⊕ X ∪ Y ) =s log s -s log s + xy log xy -C∈CT (c log c -c log c )Calculating exact values for these equations is not an easy task. Besides, the current essential task is finding an effective technique to estimate values. The authors of SLIM then made an assumption that only the usage of X, Y , and X ∪ Y will change.

  There are several ways to overcome this limitation. The first one is to improve this simple method by discretizing the values in each histogram bin into multiple intervals (also called bins). For example, if the number of interval chosen for the discretization process is "4", one can represent each interval by one binary code: 00, 01, 10, 11. The discretization thresholds (that are used to create the bounds of the intervals) can be uniformly chosen (for example, [0 -2],[2 -4],[4 -6],[6 -8] if, for example, the values in the original bins can get up to 8 or depend on the distribution of the values that fall into each bin.

Figure 1 . 14 :

 114 Figure 1.14: Examples of different binarization techniques. From top to bottom: SBin, multiple uniform intervals, non-uniform intervals and B2S.

  converting a histogram-based bag representation (i.e. bag-of-word original principle) into a set representation. For instance, we want to convert the following histogram into a binary form: A = [3 1 4 0 2]. And suppose that C = [3 2 4 3 4] are the maximum values at each position over all histograms. Each value of A is replaced by consecutive values "1" with "0" ending (if applicable, so that the total number of binary digits is equal to the value of C at the corresponding location), for example, A[5] = 2 and C[5] = 4 then A[5] binary = [1100]. Applying this step for all values, we have A B2S = [111 10 1111 000 1100].

  are successfully used with mining techniques. In [107], Yao et al. present a structured image representation called group-lets. To find discriminative group-lets, they mine for class-based association rules [3]. Recently, [95] has used random projection to produce transactions from BoW histograms, and proposed an image presentation based on pattern sets instead of individual patterns. This HoPS (Histograms of Pattern Sets) representation is efficiently used for image classification and objection recognition tasks. Jain and Jawahar [47] represent a shot as a transaction of frames and perform frequent pattern mining to find frequent frames. Based on that information, they are able to extract characteristic scenes from movies.

Figure 1 .

 1 Figure 1.15: A video is represented as an average of all its keyframes.

Figure 1 . 16 :

 116 Figure 1.16: The distance between two videos equals to the distance between two most similar keyframes (the red line in this example).

Figure 2 . 1 :

 21 Figure 2.1: The Overall Framework

if: 1 .

 1 (in step 2) the frequent patterns (FP) are truly interesting features compared to simple bag-of-words if they are carefully chosen; 2. (in step 2) a standard Principle Component Analysis (PCA) can help reducing the number of frequent patterns used to describe each images (which is often huge if no post-processing step is carried on) without damaging the classification accuracy;

Figure 2 . 2 :

 22 Figure 2.2: Class examples of Oxford-Flower17.

2. 2

 2 Step 2: Feature Construction As explained above, this step aims at constructing mid-level features from SIFT-BOW (see Section 1.1.1.3 for a description of SIFT and Section 1.1.1.4 for a description of local and global BoW). To be able to use itemset mining techniques on these histograms, one has to convert the histograms into a transactional or a binary dataset. We used three binarization methods (see Section 1.2.3) for experiments: Simple-Binarization (SBin),

Figure 2 . 3 :Figure 2 .

 232 Figure 2.3: Image representation from global histogram (global BoW) using frequent patterns

Figure 2 . 4 :

 24 Figure 2.4: Image representation from local histograms (local BoW) using frequent patterns

  2.3. However, we simplified this process by discretizing the histogram values for each visual word into 10 evenly distributed bins to make those values more homogeneous. One image is then transformed from a 200-D vector (a histogram of 200 visual words) into a 2000-D binary vector.

2. 2 . 4 . 1

 241 PCA (for supervised case)To overcome this pattern explosion problem, we first decided to use a Principal Component Analysis (PCA)[START_REF] Abdi | Principal component analysis[END_REF]. Our aim is to reduce the number of patterns as well as (hopefully) the redundancy among them. PCA involves a mathematical procedure that converts a number of possibly correlated variables into a smaller number of uncorrelated variables called principal components. The first principal component explains as much of the variability in the data as possible, and each other component explains as much of the remaining variability as possible. The mathematical technique used in PCA is called eigen analysis: it finds eigenvalues and eigenvectors of a square covariance ma-trix. The eigenvector which has the largest eigenvalue has the same direction as the first principal component. The eigenvector having the second largest eigenvalue determines the direction of the second principal component. This mathematically costly operation prevents us to use the method when the number of patterns is too important. We thus only use it in the supervised case.

Figure 2 . 5 :

 25 Figure 2.5: Explained Variance according to the number of Principal Components

Figure 2 . 6 :

 26 Figure 2.6: Accuracy given by the 1-NN algorithm according to the number of Principal Components

Figure 2 . 8 :

 28 Figure 2.8: An example of tag propagation: tag Harry Potter should be removed because it does not appear in the neighborhood, and tag football should be propagated because it appears in 5 over 6 neighbors.

  .1. There are about 18 shots per video and 1.5 key-frames per shot, i.e. about 27 key-frames for one video. A visual vocabulary of 1000 words built from SIFT features is used to describe the video. A video is thus represented by a matrix which contains for all key-frames of the video the visual word histogram which describe the frame. The dataset contains 1895 keyframes in total. The 51 videos were chosen such that they belong to 4 topics to ensure that this dataset contains pairs of similar videos and pairs of dissimilar videos. The topics are anime (10 videos), football (17 videos), news (12 videos) and racing (12 videos). We chose the top-35 most frequent tags from all tags that were used for these videos in the original YouTube dataset. The 51 videos were then re-tagged using only these 35 tags to create a ground truth. The final tags associated to the videos are shown in Table

Figure 3 . 1 :

 31 Figure 3.1: Several example keyframes of the 51-videos dataset.

Figure 3 . 2 :

 32 Figure 3.2: Result of our tag correction algorithm on the small real video dataset. Our algorithm uses only bag of word features (solid line) or histograms of both words and frequent patterns (dotted line).

Figure 3 . 3 :

 33 Figure 3.3: Several examples of keyframes of the synthetic 182 video dataset along with the tags associated with the video the keyframe belongs to.

Figure 3 . 4 :

 34 Figure3.4: Percentage of wrong tags in the videos after one propagation step according to the percentage of noise introduced. The blue and green lines give the results of our method which compare histograms of SIFT-BOW using a L1 distance function. The red line gives the result of the propagation step starting from an ideal visual comparison.

Figure 3 . 5 :

 35 Figure 3.5: Percentage of wrong tags in the videos after one propagation step according to the percentage of noise introduced computed on a synthetic video dataset. Our algorithm uses only SIFT-BOW features, frequent patterns or both.

Figure 3 . 6 (

 36 Figure 3.6 (bottom) shows the distribution of the tags around the neighbors of a each video in the dataset. From both histograms in Figure 3.6, we can conclude that there is no direct correlation between the global and the local distributions of the tags which justifies the use of the propagation criteria presented in Section 2.4 which takes

Figure 3 . 6 :

 36 Figure 3.6: Distribution of the 150 kept tags over the 668 video dataset (top), and, for each video in the dataset, over all its 30 nearest neighbors videos (bottom). The nearest neighbors are computed using the SIFT-BOW baseline and the L1 distance function.

Figure 3 . 7 :Figure 3 . 8 :

 3738 Figure 3.7:Several examples of keyframes of the real 668 videos dataset along with parts of the original tags and the complete pre-processed tags associated with the video the keyframe belongs to. The result of the tag propagation using our system and the tag ground truth is also given for these keyframes.

Figure 3 . 11 :

 311 Figure 3.11: Percentage of good corrections according to the number of neighbors in 50 videos represented with SIFT-BOW (baseline) and frequent patterns obtained LCM(closed and max)+SLIM and LCM(closed and max)+ SLIM+ tag information.

80

  Figure 3.12: Percentage of good corrections according to the number of neighbors for a video dataset represented with 3 different features: SIFT-BOW (baseline) and frequent patterns obtained with LCM(closed) + SLIM + tag info, and the concatenation of both feature vectors.

90

  Figure3.13: Percentage of good corrections when counting only the addition (dashed line with +), the deletion (dashed line with •) and both according to the number of neighbors for a SIFT-BOW (baseline), LCM(closed) + SLIM + tag info and the concatenation of both feature vectors.

Figure 3 . 14 :

 314 Figure 3.14: Percentage of good corrections to the number of neighbors for a video dataset represented by frequent patterns obtained with LCM(closed) + SLIM + tag information using the asymmetrical similarity measure and simply averaging the keyframes features and computing an histogram intersection.

Table 1 .

 1 2:The transactional dataset corresponding to the record dataset shown in Table1.1.

	Transaction ID ITEMS
	1	Bread, Soda, Milk
	2	Beer, Bread
	3	Beer, Soda, Diaper, Milk
	4	Beer, Bread, Diaper, Milk
	5	Soda, Diaper, Milk

The data can thus be represented as m × n matrix where m is the set of objects or examples and n is the set of attributes. Figure 1.1 gives an example of such record data in the special case

  2 k -2 subsets are frequent. In many cases, only the frequent patterns that have the maximum number of items are needed, thus an exponential number of subsets are

wastefully generated. Such frequent patterns are called maximal frequent patterns. By definition, a pattern is maximal frequent if none of its supersets is frequent. The one downside of a maximal frequent pattern is that, even though all the subsets are frequent, the actual support of those are not available. That is how the closed frequent patterns came into picture: a pattern is closed if none of its supersets has the same support as the itself. Closed frequent patterns are more widely used than maximal ones because they contain the support of the subsets, so no additional information is needed to find the support of all frequent patterns. LCM

[START_REF] Uno | LCM ver. 3: collaboration of array, bitmap and prefix tree for frequent itemset mining[END_REF]

stands for Linear time Closed itemset Miner is one of the fastest implementations to mine closed frequent patterns. There are also LCMfreq and LCMmax implementations for mining normal frequent patterns and maximal frequent patterns, respectively. For the sake of simplicity, the term LCM is used to indicate all these three algorithms. Theoretically, the complexity of LCM is bounded by a linear function with respect to the number of closed frequent patterns, thus it is called Linear time Miner. LCM uses a prefix preserving closure extension to completely enumerate closed itemsets. This allows counting the support of an itemset efficiently during the mining process. It includes a strong pruning method to further reduce the computation time when the number of large frequent itemsets is small. It also generates closed

  The pseudo code of KRIMP is shown in Algorithm 1. It takes as input the database D and a set of pre-mined candidates F at a given support minsup, and the expected output is a heuristically optimal code table. The first step is assigning the Standard Code Table ST, which contains only singletons, to the code table (line 1). Then, each candidate F is considered one by one (line 2) by putting it into the code table CT (line 3). Two questions are raised here: in which order the candidate F ∈ F should be considered, and in which order the candidate F should be put in the code table CT ?

	6:	end if
	7: end for
	8: return CT

  The pseudo code of SLIM is shown in Algorithm 2. It is very similar to the pseudo code of KRIMP in Algorithm 1 with some slight differences. It takes only one input: the database D (it does not need candidate set), and the expected output is a heuristically optimal code table. SLIM start by assigning the Standard Code TableST, which contains only singletons, to the code table (line 1). Then, every iteration, all pairwise combination of X, Y ∈ CT is considered as candidate (line 2) by putting it into the code table CT (line 3). The next step is calculating the new compressed size, and the candidate is only accepted if the compression improves (line 4). Lastly, all elements X ∈ CT c are reconsidered to remove elements which are not improve the total compression (line 5).

	6:	end if
	7: end for
	8: return CT

Table 2 .

 2 1: Accuracy of the SVM and the 1-NN classifiers on the image datasets.[START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF]. At the end of the process 6000 patterns are kept to describe the images of the GRAZ dataset and 10000 for the Oxford-Flower17 one. These final patterns are called FLH (Frequent Local Histograms).

	2.2.2 Classification Using Supervised Mined Patterns (FLH Patterns)
	When dealing with an image classification problem, we can use the class information
	(for e.g. the class entropy) associated to the training examples to select the most
	meaningful patterns. Similarly to what has been done in [30], we use the exhaustive
	LCM algorithm [91] (see Section 1.2.1.3) to compute closed frequent patterns from the
	set of local BoW (binarized using the Sparse-B2S technique). We then post-process
	with a greedy method the patterns extracted using the relevance criteria proposed in

.4). As in the previous case, each local histogram is also converted into a binary format and all histograms are used during the mining phase. However, in this case, an image is represented as a non binary histogram of frequent patterns since one pattern can happen multiple time in the local histograms representing the original image.

Table 2 .

 2 2: Number of closed frequent patterns found with the support thresholds [80 -80000] for the Oxford-Flower17 dataset using local BoW and different discretization techniques. about 5000 local histograms (images have different resolutions, thus consist of different numbers of local histograms). These histograms were also converted into transactions (binary formats) using the three techniques explained in Section 1.2.3 The Oxford-Flower17 dataset of 1360 images is converted into 6507035 transactions.

	1.1.4 using 5 nearest neigh-

Table 2 .

 2 3: Different features at global scale of Oxford-Flower17 dataset. The filtered rows correspond to the number of pattern remaining after removing the too frequent or infrequent ones.

	Visual Features		Size Accuracy of 1NN with L1
	SLIM patterns using SB2S	5770	23.8 ± 11.4
	filtered SLIM patterns using SB2S 1651	25.7 ± 12.7
	SLIM patterns using B2S	2513	32.8 ± 15.9
	filtered SLIM patterns using B2S	415	33.2 ± 15.9
	global SIFT-BOW		200	36.4 ± 18.0
	Visual Features	Size Accuracy of 1NN with L1
	SLIM patterns using SBin 3206	40.5 ± 17.6
	SLIM patterns using SB2S 2734	40.9 ± 18.2
	SLIM patterns using B2S	2837	39.5 ± 18.3
	Local SIFT-BOW	200		36.5 ± 18.0

1-Nearest-Neighbor al-

Table 2 .

 2 4: Different features at local scale of Oxford-Flower17 dataset.gorithm. Notice that we did not try to obtain the best possible classification results or we would had use a SVN classifier. Instead, we were trying to compare different image encodings so a simple 1NN model is enough for the proof of concept. All results are shown in Table2.3. This table shows that it is better using SLIM patterns to set a frequency interval for all the patterns: it helps reducing the number of patterns greatly (around 4 times), and it improves the final performance. It also demonstrates that the redundancy between the SLIM patterns is still important.That might explain the fact that, unfortunately, the baseline performance with SIFT-BOW is still better than the SLIM patterns for this global encoding. ± 21.[START_REF] Amir | Ibm research trecvid-2003 video retrieval system[END_REF] 36.8 ± 22.3 32.9 ± 19.9 33.6 ± 20.1 30 36.8 ± 23.8 35.7 ± 24.1 33.9 ± 20.5 33.4 ± 22.6 50 35.4 ± 24.1 34.9 ± 23.6 32.6 ± 20.1 32.6 ± 21.7 100 34.6 ± 24.4 33.2 ± 24.5 32.9 ± 21.0 30.4 ± 21.8

	Local encoding for the Oxford-Flower17 dataset Using the SLIM algorithm
	on the 6 millions local histograms returns about 3000 patterns after 2 days with each
	binarization technique as shown in table 2.4. Again as explained before, we encode
	the entire image with a non-binary vector of patterns and evaluate their quality in
	classification using a 1NN algorithm with a L1 distance function. All results are shown
	in table 2.4. The table shows that, in this case, the results are better using the patterns
	than using only the SIFT-BOW baseline. We also performed experiments using multiple

Table 2 .

 2 5: Accuracy results for the KNN algorithm using different values of K (nearest neighbors) and with a L1 distance function at local scale on the Oxford-Flower17 dataset.

Table 2 .

 2 6: Different distance functions with 1-NN at local scale of Oxford-Flower17 dataset.

	Sparse B2S	B2S	SIFT-BOW

Table 3 .

 3 2: Number of frequent patterns from LCM and KRIMP patterns which covered 110 visual words. This seemed much already better than in the previous case. To increase the coverage, we could have lowered the size threshold to,

	80 frames (over 1895 frames, it

Table 3 .

 3 Table3.3 shows the final result. The values in the diagonal are the within-class distances and are expected to be the smallest value in the table (videos within the same class should be closer).These results are good for the anime class and quite good for the racing class, but they are not for the news and for the football classes. This phenomenon can be explained by the big difference between the anime videos (a kind of cartoon) and the rest of the videos (which are real life videos). The racing score is good probably because this class contains some video games, which should be also be different from the real 3: Mean of differences between videos of each class. In ideal case, bold numbers are the minimum values over column and row.

	Classes	Anime Football News Racing
	Anime	0.15	0.18	0.30	0.15
	Football	0.18	0.21	0.32	0.18
	News	0.30	0.32	0.40	0.30
	Racing	0.15	0.18	0.30	0.15
	Mean over all dataset		0.24
	life scenes.

Table 3 .

 3

	top-10		"top" 111 → 120	"top" 241 → 250
	frequency tag	frequency tag	frequency tag
	1288	the	140	pet	85	kristen
	1072	video	139	james	84	nick
	927	of	138	york	84	mobile
	912	funny	138	taylor	84	fun
	816	2009	138	part	84	family
	730	new	137	white	84	cosmetics
	508	to	137	full	84	channel
	486	music	137	episode	83	young
	464	world	136	your	83	ufo
	418	in	135	lol	83	piers

4: Examples of the top-500 most frequent tags present in a 10000 video-dataset extracted from the Youtube dataset. compare our system to them. The following experiments stand for a proof of concept of our system.

J. Gantz and D. Reinsel, "The Digital Universe Decade, Are You Ready?,"

http://www.emc.com/digital universe 2 http://www.youtube.com/yt/press/statistics.html

Acknowledgements

like to extend my thanks to the technicians of the laboratory of Hubert Curine Laboratory for their help in offering me the resources in running the program. I take this opportunity to sincerely acknowledge the Vietnam International Education Development (VIED), Government of Vietnam, Hanoi, for financial support during last 3 years. I would like to acknowledge the Caisse Allocations Familiales (CAF), French Government, Saint Etienne for providing financial assistance which buttressed me to have a comfortable life in France.

The similarity sim(A(i), B(j)) between frames is just the inverse of a distance between the vectors representing the frames. When the two frames are identical, this asymmetrical similarity is set to a maximal value. The relevance of this asymmetrical similarity measure compared to the two baseline proposed in the literature will be assessed in the next chapter together with the tagpropagation process.

Step 4: Tag Propagation

For each video V , a list of possible-relevant tags is obtained from the k most similar videos. After that, a score function is applied for each tag to estimate the relevance of that tag according to the query video V . This score function depends on the tag frequency (the higher the frequency, the higher the score), the number of tags associated to a video (the higher the number, the smaller the score), and the video similarity (the higher the similarity, the higher the score). Finally, all scores that are larger than a than 0 in the entire dataset to be propagated and the second one states that it should be significantly more present in the neighbors than in the entire dataset. Formally:

• (Global scale) A tag can be propagated if:

where p is the proportion of a tag over the whole dataset, N is the total number of videos, u α/2 is 1-α 2 percentile of a standard normal distribution.

where p1 is the proportion of a tag in the k neighbors.

We arbitrarily decide to remove a tag from a video if it is never present in its neighbors. Note that the central limit theorem applies whenever k ≥ 30 so without any background information on a dataset, this is the value used in most of the experiments.

Conclusion

In this chapter we presented the framework we use to tackle our video tag-correction problem. To set this framework, we made a number of hypotheses that were validated.

In particular, we showed that frequent patterns are good mid-level features to describe images (and hopefully frames of videos). We also show that a simple vector comparison using a L1 distance function can give good results in image classification and thus hopefully to compute a visual similarity between two videos. We have proposed an asymmetrical similarity measure and two tag propagation criteria. These two last contributions will be evaluated in the next chapter after defining our experimental set up on videos.

3.3 A second real dataset (668 videos)

Building Dataset

To illustrate our method, we pre-processed a Youtube dataset [START_REF] Cao | MCG-WEBV: A benchmark dataset for web video analysis[END_REF] with more than 10, 000 videos already decomposed into shots and keyframes. There are about 18 shots per video and 1.5 keyframes per shot, i.e. about 27 keyframes for one video. We first decided to focus on videos with some common tags to obtain an interesting sample of the original dataset. For that, we focused on the 500 most frequent tags in the original set. Table 3.4 shows some tags from this list from various locations. We can notice the tags frequency highly varies at the beginning of the list and becomes more stable when reaching a frequency under 100. Besides, the most frequent tags are mainly meaningless (e.g. "the", "of", "full", "lol" . . . ). We removed from this list of 500 frequent tags the articles, pronouns, prepositions, words with less than two letters and also the 100 most common tags in the remainder list (those, such as the word "video" who were considered too frequent to be informative). Finally, top-150 tags were selected. This 150-tags are meaningful and with a frequency still large enough to be able to select similar videos in the original corpus. We then kept the videos that contain at least 5 of those 150 tags and more than 1 keyframes. This process gave us a corpus of 668 videos with at least 5 meaningful tags per video. The global distribution of the 150 tags is given in Figure 3.6 (top).

Evaluation Procedure

To assess the accuracy of our system we need to manually check the 668 videos to remove all noisy (incorrect and incomplete) tags. Since this is not doable in practice, we randomly chose 50 videos from the original set, and tagged them by hand using the 150 pre-processed tags to obtain a reliable ground truth. We ran our tag propagation method on the 668 videos and reported the accuracy results for these particular 50 videos. This accuracy is measured in terms of "percentage of good corrections" (PGC).

Let T add,correct be the correctly added tags out of T add,total added tags and T remove,correct be the correctly removed tags out of T remove,total removed tags.

P GC = T add,correct + T remove,correct T add,total + T remove,total

If P GC is larger than 0.5, our system improves the tags in the videos. Note that since most existing tag correction systems use some supervised information, we do not connections between these "new" patterns and the original transactions. However, since the "new" patterns are the set that compresses the classic frequent patterns well, and since the classic frequent patterns are all extracted from the original transactions, the "new" patterns might contain some useful information of the original transactions.

Applying SLIM greatly reduce the number of patterns of two order of magnitude: from 700, 000 to 5, 500 for the closed and from 550, 000 to 5, 000 for the maximal ones.

These values can be used directly to re-encode our videos and then perform the tag propagation.

Finding Patterns With Tag Information

Even if the tags (that don't belong to the 50 ground truth videos) cannot be entirely trusted, they are still one important source of information. In fact, they are used in the tag propagation step to transfer tags to videos. Thus they could also be used as a measurement to choose the good patterns.

In addition to the 1000-D binary input vector, we add another 150 dimensions for the tag information. Each position in the last 150 dimensions symbolize one tag, and its value is 1 if that video contains the tag and 0 if otherwise. LCM is used first to find all closed and maximal frequent patterns from the set of 6 millions larger transactions.

It returns a very large number of patterns: 5 millions closed and 1.2 millions maximal frequent patterns. Note that this is not surprising since each video is described by Chapter 4

Conclusions and Future Works

This dissertation has presented new visual mining-based features, and evaluated their effectiveness when integrated in an auto tagging framework for video datasets. We conclude our work by summarizing our main contributions and drawing conclusions in Section 4.1. We then suggest several interesting directions for future research in Section 4.2.

Contributions & Conclusions

A simple but effective framework. Our first contribution is a general framework for unsupervised tag propagation in video datasets. This framework is modular and contains four independent blocks. Different visual features, distance functions, video comparison methods and propagation techniques can be used.

Videos to transactions conversion. Video data are specific in the sense that their structure is complex and they can be described by a large number of different visual features. Representing images and videos into a format suitable for existing pattern mining tools is not a trivial task. We chose to use Bag-of-Visual-Word computed from 128-D SIFT descriptors to convert images or frames into histograms. These histograms are more similar to the traditional pattern mining transactional format. Specifically, each keyframe is densely sampled into numerous local patches which are then represented by a SIFT descriptor. Inside this 128-D space, all SIFT descriptors from all keyframes of all videos are clustered into multiple (for example, 1000) groups. The center of each group is called a visual word, and all SIFT descriptors belonging to the group are associated to a unique visual word. Keyframes then become a set (bag) of visual words which can appear multiple times. There are two popular ways to generate