Keywords: Minimization, Cd: Concept Dependent Entropy Minimization and Cd (Av): Average Concept Dependent Entropy Minimization, precision = 60

List of Tables

3.1 Mean Average Precision for 20 concepts for baseline (K-means) and three entropy minimization based mapping criteria. Min Ent: Concept distribution Entropy

Abstract

Visual material comprising images and videos that surrounds us is growing ever so rapidly over the internet and in our personal collections. This necessitates automatic understanding of the visual content to conceive intelligent methods for correctly indexing, searching and retrieving images and videos. We have entered an age where the reliance of humanity on computing has never been felt so strongly before. However we still are not able to make our machines see and understand the world around us like we humans do. Initial successes in Computer Vision after the conception of the field some 50 years ago encouraged the then scientist to predict the successful resolution of the problem of automatic understanding of visual material with in some years. 5 decades on and our computers still achieve partial success in truly detecting the content depicted in an images, let alone a video.

The difficult task of automatic indexing and retrieval of videos based on their content is abundantly addressed by academic and industrial exploration. Decades of research on text based automatic retrieval and then content based methods to index videos has led to the development of ingenious systems. These complex systems mainly utilize image analysis and statistical learning tools and more or less comprise of several intricate steps to make the machine able to recognize the content. However unlike text based search, automatic understanding of the video content is far from solved with our machines today using the current methods. A vast amount of information is extracted from videos some of which is used efficiently and cleverly to achieve the target being mindful to the scalability and complexity of the system.

Understanding the importance of content based indexing and retrieval and after doing extensive research of the state of the art in the field we feel that the automatic system can be improved in many ways. We predominately target the information that is not used when building such a system, whilst its already there. This thesis aims at improving the automatic detection of concepts in the internet videos by exploring all the available information and putting the most beneficial out of it to good use. We look at it in the sense of cutting thicker slices from the vast world of visual information to build our categorization system.

Our contributions target various levels of the concept detection system in videos and propose methods to improve the global performance of the inter disciplinary system. The standard system extracts low level information from the videos and givens a decision about the presence of an entity in the video frame after a series of computing steps. Our contributions start with improving the video representation model employing some existing information from the Visual World. We then devise methods to incorporate knowledge from similar and dissimilar entities to build improved recognition models. Lastly we contrive certain semi-supervised learning methods to get the best of the substantial amount of unlabeled data.

During the latter half of 2010, owing to the unfolding of a series of unfortunate events, I had become quite clueless and disheartened. Fortunately enough, Professor Bernard Mérialdo hired me to do PhD research under his supervision, I was rescued. With computer vision being my research passion, finding a PhD thesis in the topic with an excellent professor was like a dream come true. I would like to start these acknowledgments by expressing my profound gratitude to professor Mérialdo for his continuous support, his careful guidance, his positive attitude, his advices, his patience and for some of the morale boosting sessions we had.

I would also like to thank Professor Lionel Prévost (UPMC, UAG) as he was always a source of inspiration for me for the very short period of time we worked together and played a very important role in getting me the PhD position at Eurecom. I felt at home in Eurecom right from the start. With a wonderful mix of people from beautiful and fabulous countries, having amazing and friendly personalities I felt welcomed since my first day. In the old campus we were five in a big room, including a Turkish, a Tunisian, an Italian and then a Cameroonian, an Argentinean and me, a Pakistani. The seniors were always ready to help and offered helpful advices. Then there was always someone bringing special treats from their respective countries, to share with everyone. Birthdays, pot de thèses and 'MMtalks' were another medium of getting everyone together. I wish to thank Claudiu and Miriam for their guidance and specially Miriam for her reassurances of, 'don't worry, Its going to be fine'. I can never forget the discussions I used to have with Claudiu about 'where we stand' (and where should we stand). I would like to thank Simon, Hajer, Neslihan, Huda, Federico, Gislain, Ravi, Giovanni, Leela, Christelle, José and of course my Pakistani friends in Eurecom Sabir and Imran. The role of all the secretaries, HR and the guys at IT help-desk, with whom we PhD students had frequent interaction, can not go unacknowledged. It is their excellent service, helpful attitude and proper guidance that makes them stand apart, making your life wonderful at Eurecom. Finally, life bound to be wonderful if you are working and living in one of the most enviable places in the world, specially Europe, the French Riviera. In the south of France enjoying around 300 days of sunlight a year gives one enough time and opportunities to relax, stay healthy and come to work with a fresh mind.

During my PhD at Eurecom I worked on the ANR's SUMACC project in collaboration with other expert partners. During the project meetings I had the chance to meet brilliant people and learn from them including professor Georges, Christophe, Claude, Clément, Mohamed and Richard.

Words aren't enough to encompass the immense gratitude i owe to my wonderful parents.

All I can do is thank them for always treating my worries as their top priorities. They've not only been my mentors but my friends and have always been a source of motivation, ii iii inspiration and guidance for me. I attribute much of the success in my life to my mother's prayers and her constant guidance. Not a single conversation with her ever ends without me learning something new, something useful. My father on the other hand see's things on the lighter side and encourages us to do the same as well. I believe it is the perfect parental combination one could hope for and it has worked perfectly for me (and my siblings) even though I was away from home for a long time, completing my higher studies.

And finally I cannot conclude without thanking the most important person who was there with me during a good part of my PhD, my wife Bushra. Since I've gotten to know her she's been a constant support in every aspect of my life. She's been with me through all the ups and downs, that come your way specially in pursuit of a PhD, far away from home, supporting me and proudly standing by my side, and I know that she'll always be there for me. She has always believed in me and cherished me with her amazing and supportive words and her beautiful smile.

Contents

Introduction

They say a picture is worth a thousand words but this is a mere understatement in computer vision. In fact, for vision scientists, a picture may contain millions of visual words. These visual words are built using various visual features capturing important measurements from images (color, texture, spatial arrangements, local patches, global statistics, etc. . . ). All this multitude of information is used to help computers capture the understanding of the content of images. It is an attempt to make machines see and understand the world like we do. However this multi-megabytes of information still achieves partial success and the recognition of content in the images continues to elude our intelligent machines.

Video analysis is a scaled-up version of the same problem where a series of images come into play bringing along the relation between frames and temporal dependencies. The core, however, still constitutes of analysis at frame level. Automatic image/video analysis consists of tasks like categorization, retrieval, copy detection, event detection etc., at the helm of which lies the ability to recognize the visual content based on image semantics. Manipulating images and video documents for automatic analysis is among the most difficult challenges faced in computer vision [1]. However the need for automatic recognition of visual content has never been felt more strongly before with the exponential increase in the amount of visual information spreading over the internet. Roughly 350 million new photos are uploaded to Facebook every day [2], and the number for Flickr is between 20 to 40 million per day [3].

Moreover Facebook boasts more than quarter of a trillion photos uploaded to their web site.

YouTube has an astounding 100 hours of new video uploaded every minute. The amount of users using these services is growing by day and this online medium of communication is now matching the importance of broadcast Television. This staggering amount of new information and its importance to users calls for reliable and efficient methods to analyze the visual content in order to develop methods to automatically search, index and browse these large databases.

In this introduction we start with explaining the pursued Video Concept Detection task which is also referred to as Semantic Indexing. We follow with an overview of the major 1 Chapter 1. Introduction 2 steps involved in achieving concept detection. Further we analyze the opportunities for improvements in the detection pipeline and present our motivations to work in the selected directions. The introduction lists, at the end, our contributions to the video concept detection pipeline.

Video Concept Detection (Semantic Indexing)

For years scientific research in image and video retrieval and indexing has been dominated by text or concept based approaches where the metadata or associated text based descriptions like title, an article or narrative and tags etc. are used to retrieve multimedia content from the internet. Practically this is the popular method these days to get images from the popular search engines and look for videos on video sharing services like YouTube and Dailymotion. Since the dawn of the century though research focus has been shifted to directly understanding the content of the multimedia documents and using the extracted information to build retrieval models. Textual descriptions associated with or surrounding the multimedia content on the internet are not always reliable. These are usually subjective to the uploader, personalized, misleading, incomplete and sometimes do not exist at all. Moreover annotating a large video database from scratch with manual human effort is laborious and could suffer from the similar incompleteness and bias. The content on the other hand is always right and we can safely rely on its authenticity, provided its correct use. Video Concept Detection or video categorization aims at automatically describing a video with semantic concepts that correspond to the content of the video, figure 1.1. These semantic concepts are high level descriptions of the video that directly depict the key information present in the content. The semantic concept can consist simply of labels like objects or people, can be depicted by a scene or can comprise of a situation with a complex interaction of different entities. The solution assigns a probability of presence to a concept or a label in the video frame (e.g. the video contains a "Bus" for sure and is less likely to contain a "Helicopter hovering"). The probability is assigned by a classifier which is trained for that concept. This classification model is built for each concept separately. The classification is not done for each frame of the video, rather a set of keyframes are extracted for each video [4,5]. These keyframes are representative of the video content. Video is first segmented into shots where a new shot location can be given with the video metadata or can be automatically detected [5]. Usually a single keyframe is then extracted from each video shot which is the most informative of the shot frames. Since analyzing videos with keyframes offer a convenient and effective alternative to analyzing video as a whole [4][5][6] we opt to work with keyframes throughout this thesis.

A semantic concept does not have a fixed description most of the times and there exists plenty of within class variations. The detection framework has to capture this intra-class variability when building classification models for concepts. The video concept detection system which starts to work with the raw pixel data from images and assigns probabilities to test images is very intricate and is composed of quite a few processing steps. These steps are detailed in the next section.

Video Concept Detection Pipeline

A video categorization system comprises a complex structure of more or less sequential elements which span over a number of scientific disciplines including image and signal processing, statistical analysis, mining and machine learning to name a few. Figure 1.2 presents the major components of the framework where we start with images (keyframes) assuming that video was already segmented into shots. Building different concept detection models and using them employs largely all the steps of the framework and only differ in the functionality of some of the stages.

The system extracts a number of different visual features from the provided images at the stage 1 of the framework. These raw features are usually not used directly and are rather transformed to an aggregated image specific representation in the stage 2 of the pipeline for further processing. A number of annotated images is usually available to learn the model which classifies the concept images from the rest. This makes the 3rd stage where the classification model is used to find predictions on the test images which depicts the prospects of existence of the concept in the corresponding video. The fourth stage is an additional but very useful step where predictions from different models are combined to unite the powers of the individual learners. We briefly describe each of the stages of the pipeline below before looking into the possible rooms for improvement in the components of the pipeline.

Stage 1: Feature Extraction and Description

An image in a typical video is composed of tens of thousands of pixels that are mere numerals but an enormous amount of information can be extracted from a single image. This step is the foundation of the detection or retrieval framework as features are expected to capture the essence of what the image represents. Humans can, most of the times, figure out the concept depicted in the image by just taking a look. The features are expected to encapsulate this essence of the image for machines. They capture the semantics of the image to make the machine understand the similarity or dissimilarity between the images.

A video frame can be described globally or can be bisected into regions before building descriptions for each region. These descriptors are called the visual features of the image.

While global features capture the qualities or properties of the image on the whole the local features work on a local neighborhood of the image to gather information about the targeted pixel. Global features can be computed for the whole image or parts of image by first segmenting the image into predefined parts and then building the feature for each segment. They describe global properties of the image (segment) like color, gist or some sort of spacial information. Local features may be described for predefined image locations and are sometimes only extracted for specific image points. These points are expected to contain rich information compared to the rest of the image. Methods are employed to find these critical points that are based on some maximization criterion. Statistics from the local --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- The features extracted should be relevant to the specific task of concept detection and should be robust. So if the appearance of e.g. an object changes in the image the features should still be able to capture the relevant and necessary information. They should also resist change to the accidental distortion of images from illumination variation, camera movement and other forms of distortions. A good knowledge of image processing is required to build such features.

Global and local image descriptors

Usually the features of a specific type are used to build the rest of the system but sometimes different types of features can be merged pre-hand to perform the task. More discussion on the use of the features is to follow.

Stage 2: Feature Coding and pooling

The different kinds of features extracted in the previous stage can be directly used to represent an image but their use is prohibitive due to their sheer size and huge number. This is more often the case for local image descriptors that are extracted at numerous image locations.

Furthermore the number of these features extracted from the images could be different as well which prohibits a unified representation for all the images. That is why the features are usually summarized into a single high dimensional feature vector of fixed length, figure 1.4.

To construct the unified representation first the features from the image are transformed or coded into a set of values. This projection of the feature onto the new representation has certain properties: two features that are close are encoded into the same representation, the representations are compact and most of them are zero for an image [7]. Some examples -------------------------------------------------------------------------------------------Coding Pooling

Projecting the descriptors into the coded space Aggregating the projections to aquire a fixed length feature of coding include vector quantization [8], soft assignment [9,[START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] and probability estimation for GMMs to generate Fisher vectors [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. The new representation or the codebook is constructed using features from some training images. After each image feature is coded, pooling aggregates the coded features into a single value for each of the codes. This results in a vector of values with length equal to the number of coded representations. Pooling can vary from averaging and taking the maximum value to parameter adaptation in the case of Fisher vectors [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF].

The benefit of these fixed length vectors is that they can be directly fed into a discriminative classifier and a model for the concept can be built. Moreover the reduced size helps in fast learning and efficient prediction of the test examples. On the other side of the picture the true discriminative power of the features that capture the image dynamics from specific locations is somewhat lost as the local features are aggregated. Extreme values may be diminished due to averaging or maximizing and geometrical structure can be no longer used. Refinements can be done to include some useful information that hints at some of the lost dynamics of the original image. The size of the coded representation can be increased to better distinguish the image features at the expense of increased training and prediction time and the risk of overfitting the parameters to the training images.

Stage 3: Model Learning

This stage is the brain of the pipeline where machine learns to correctly identify examples of a concept. This necessitates the presence of some annotated images that must be used for learning the model for a semantic concept. These images are treated as the positive examples and are used to train the classification model to distinguish them from the rest of the world.

To be able to achieve this intelligent behavior a great deal of number crunching is required and usually this step takes the most of the time in the pipeline. This time increases linearly with the number of concepts as in practice a separate model is learned for each concept.

------ ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------

Motivation

The information extracted from video frames at pixel level are low level descriptions of the image and this does not translate directly to the semantic meaning of the image. There exists thus a Semantic Gap [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] between the low level image description that the computer vision system uses, to learn about the higher level semantics that the image represents. There are various reasons for the existence of this gap. Foremost is the difference in the human perception of a concept and the representation suitable for our computers to understand. Then there is subjectivity [START_REF] Hanjalic | Affective video content representation and modeling[END_REF][START_REF] Snoek | Concept-based video retrieval[END_REF], i.e. when different users perceive similar content differently.

Lastly the semantic gap is widened by the within class diversity for many concepts. To highlight this problem consider an image of a chair placed inside an office and another image of a chair outside in a lawn. Though both images contain the concept Chair, the low level pixels would not agree for the most part of the two images. Research in automatic video content understanding has been focused to reduce this semantic gap.

The performance of a detection system depends on all the factors that make up the detection pipeline. For each of these steps we list below the main opportunities of improvement.

• Features extracted at pixel level

As the basis of the detection pipeline this phase receives considerable research attention in order to capture the most useful information with a manageable size from the images.

• Selecting and building the most informative mid-level representation

Summarizing the visual features is the most sensitive step in the pipeline as most of the raw low level information is lost here. Research in this area focuses on building comprehensive mid-level representations that successfully capture the image semantics.

• Refining the representation

Research has also been done to refine the mid-level representation to try to bridge the semantic gap by adding e.g. contextual, spatial or label specific information. training and refining them with feedback is important to the performance of the system. Moreover there always exist great amount of unlabeled examples to be discovered. New instances should be added to add diversity while increasing performance.

• Finding the best decision boundary

In the end it all comes to the classifier which distinguishes the positive instances from the negatives. Research is evolving in this area as well to build classifiers that generalize well on test examples and have lower complexity.

• Fusing the best classifiers effectively

Research continues to find new methods to select the best classifiers among the pool of multimodal classifiers and combine them in the most effective way.

Making the Slice Bigger

With the enormous amount of visual information extracted from the images, the various coding and pooling methods and the variety of strong classification techniques available, not everything is used to build the categorization system. If too many features or parameters are used to train the models for concepts there is a risk of overfitting on the training examples.

Moreover this would require loads of computing power and time as the feature representations are high dimensional and the current processing power limits the extravagance use of this visual information.

We can look at all this information as making a Visual World, figure 1.7, and usually a video concept detection system only takes a slice of this world with a number of annotated images, certain features and a classification algorithm that learns a model using this information. The amount of information going into the slice goes from raw image level information to classification decision which justifies the pyramidal structure. What we target in this thesis is how to make this slice bigger by exploring the Visual World in order to add extra and useful information with little effect on complexity of the task to improve video concept detection. So instead of cutting the standard slice from the Visual World we cut a bigger slice where we include additional information at various levels of the concept detection pipeline 1.2. Note that in terms of this Visual World, classifier fusion can be regarded as combining various slices. • We use state of the art features extracted from the images and work on their transformation into the mid-level representation. We use label information while building this representation in order to add some image and concept specific information into the feature.

Chapter 1. Introduction 10 ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ -
• We also enhance the standard image representation by encoding the feature with transformation specific information.

• To improve the classification performance for a concept we explore examples of other related concepts in order to add useful and diverse information. The idea is that common or close concepts share information among themselves and it should be put to use when learning the classification models.

• We extend the idea above to look at concepts that are not so close, rather that are different, to learn from the dissimilarity between concepts.

• Finally we try to explore the unlabeled examples in a semi supervised setting to increase the amount of annotated data and use the best information out of it to learn the concept models.

This concludes the introductory chapter of this manuscript which is followed by a brief review of the state of the art methods in video concept detection and retrieval in chapter 2.

We limit our discussion to methods important to the concept detection pipeline. Each of the rest of the chapters also include some review of popular methods as it makes more sense to describe the work that inspired us with the corresponding contributions. Chapter 3 includes the first of our contributions where we try to improve the mid-level video representation. In In the early 90s with the advent and increase of digital media and the availability of cheap media capturing devices research interest grew in the content based retrieval field [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF][START_REF] Snoek | Concept-based video retrieval[END_REF][START_REF] Zhang | Image search—from thousands to billions in 20 years[END_REF].

Research exploded after the dawn of the millennium when Google launched its text based image search. It was evident that directly understanding the content of the images was the new target. Around the same time National Institute of Standards and Technology (NIST) also jumped into the action and later in 2003 formed a dedicated research track allocated to video analysis based techniques called TRECVID [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF].

In terms of scalability of the content based image/video search problem the databases used have literally gone from indexing thousands [START_REF] Flickner | Query by image and video content: The qbic system[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] to millions [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF][START_REF] Joly | Robust content-based video copy identification in a large reference database[END_REF][START_REF] Quack | Cortina: A system for largescale, content-based web image retrieval[END_REF][START_REF] Torralba | Small codes and large image databases for recognition[END_REF][START_REF] Douze | Evaluation of gist descriptors for web-scale image search[END_REF][START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF] and now billions [START_REF] Wang | Arista -image search to annotation on billions of web photos[END_REF] of images in the last 20 years [START_REF] Zhang | Image search—from thousands to billions in 20 years[END_REF].

In the year 2000 Smeulders et al. [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] presented a review on content based image retrieval citing about 200 references. The problem of automatically understanding the visual content has received continued attention in the last 14 years with thousands of available works and many dedicated conferences and workshops. We only select some of those works that we feel are the most representative and cover more or less the stages of the concept detection pipeline presented in the figure 1.2.

Feature Extraction

Visual feature extraction converts an image to a mathematical representation and it forms the basis of any visual content analysis system. The features should capture enough information to differentiate the class instances from the non-class instances. Since the features are extracted from raw pixel values this step is susceptible to noise that may come from camera motion, variations in lighting, change in scale and viewpoint, occlusions, lower resolution, quality of the frame extracted or the movement of the objects in the frame themselves. The features extracted in this stage should be robust to all these noise and variations and should be compact. There is no winner when it comes to capturing the visual information due to the complex composition of data, the intra class diversity and the nature of the semantic concept to be detected. The features or image descriptors are mainly divided into two types:

global and local features.

Global Features

Global features describe the properties of the image as a whole summarizing the information into one compact description. They are faster to compute and are highly scalable compared to their counterpart but lack enough discriminatory information. Color seems to be an important and intuitive global choice when trying to predict the semantic concept in an image. Globally dominant colors can give indications about the concept like if an image contains large components of blue and green it is likely to be an outdoor scene [START_REF] Wang | Combining global, regional and contextual features for automatic image annotation[END_REF]. This is precisely true as color features have been there since the conception of the field of image analysis and are being used till date. The most straightforward use of color is in building the color histograms from the pixel values in the RGB space [START_REF] Han | Fuzzy color histogram and its use in color image retrieval[END_REF][START_REF] Chakravarti | A study of color histogram based image retrieval[END_REF]. To make the color histograms invariant to changes in light intensity and shadows, normalization is performed [START_REF] Gevers | Color image processing: methods and applications: color feature detection: an overview, chapter 9[END_REF][START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]. Color spaces other than the omnipresent RGB have also been used explicitly. Weijer et al. [START_REF] Weijer | Boosting color saliency in image feature detection[END_REF] build color histograms in the HSV space where the H bins are weighted by the saturation making the representation robust to changes in scale and shift.

Hays and Efros [START_REF] Hays | im2gps: estimating geographic information from a single image[END_REF] use the L*a*b* space to build 784 dimensional histograms with 4, 14 and 14 bins in the L, a and b respectively. Chang et al. [START_REF] Chang | Cbsa: Content-based soft annotation for multimodal image retrieval using bayes point machines[END_REF] build a 12 bin histogram for 11 colors and one outlier bin. They extend their feature by building histograms for each color at finer resolutions along with mean and variance of the HSV channels. [START_REF] Li | Automatic linguistic indexing of pictures by a statistical modeling approach[END_REF] extracts average color components of the LUV space (L:luminance, UV chrominance) of 16 pixels from the image divided into 4 X 4 blocks.

Color moments [START_REF] Stricker | Similarity of color images[END_REF][START_REF] Li | Automatic linguistic indexing of pictures by a statistical modeling approach[END_REF][START_REF] Mindru | Moment invariants for recognition under changing viewpoint and illumination[END_REF] are defined on the distribution of the RGB triplets. These are usually extracted up to the 2nd order, are rotation invariant and higher order moments also contain spatial information. Color map reflects the user's search intention with a small feature by allowing the user to indicate the spatial distribution of colors in the desired images [START_REF] Wang | Interactive image search by color map[END_REF].

Holistic representations capture dominant spatial structure of a scene into a low dimensional feature from a scaled down image [START_REF] Douze | Evaluation of gist descriptors for web-scale image search[END_REF]. Olivia and Torralba [START_REF] Oliva | Modeling the shape of the scene: A holistic representation of the spatial envelope[END_REF] proposed the GIST feature which summarizes Gabor filter responses, which was further compressed using different strategies [START_REF] Torralba | Small codes and large image databases for recognition[END_REF][START_REF] Weiss | Spectral hashing[END_REF]. GIST features have also been extracted from image regions by accumulating responses from filters at different orientations and scale [START_REF] Hays | im2gps: estimating geographic information from a single image[END_REF][START_REF] Hays | Scene completion using millions of photographs[END_REF].

Texture features capture important properties like smoothness, coarseness or some pattern that occurs repeatedly throughout the image. Pioneer textural features were extracted by Tamura et al. [START_REF] Tamura | Textural features corresponding to visual perception[END_REF] emulating the human visual perception. For outdoor scenes textural properties might be geographically correlated [START_REF] Hays | im2gps: estimating geographic information from a single image[END_REF] e.g. the building in a city's skyline or vegetation. A universal texton dictionary is a popular method that summarizes the pixel responses to a bank of orientation filters [START_REF] Hays | im2gps: estimating geographic information from a single image[END_REF][START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF][START_REF] Liu | Image retrieval based on multi-texton histogram[END_REF]. [START_REF] Chang | Cbsa: Content-based soft annotation for multimodal image retrieval using bayes point machines[END_REF] decomposes each image into four sub-images using discrete wavelet transform and build nine texture features with different compositions of the decomposed images. Li and Wang [START_REF] Li | Automatic linguistic indexing of pictures by a statistical modeling approach[END_REF] perform Haar transform on the L component of the LUV image space for each 4 X 4 block of the image. They use average of the 3 out of 4 wavelet components to build their feature containing 3 values for each 4 X 4

block. Recently discriminatory texture information is also extracted using Local Binary Patterns (LBP) from image patches and aggregating them into a global descriptor [START_REF] Ahonen | Face recognition with local binary patterns[END_REF]. LBP is extended by considering the distance between the center pixel and its neighbor for improved image retrieval [START_REF] Subrahmanyam | Local maximum edge binary patterns: A new descriptor for image retrieval and object tracking[END_REF] but with a higher dimensional feature. More recently [START_REF] Sinha | Novel color gabor-lbp-phog (glp) descriptors for object and scene image classification[END_REF] has extracted LBP for different color spaces.

Global edge distribution is another important piece of information gathered from images. Like color, edge histograms are the simplest representation capturing cumulative edge orientation information in images [START_REF] Won | Efficient use of MPEG-7 edge histogram descriptor[END_REF]. Wang et al. [START_REF] Wang | Automatic video annotation by semi-supervised learning with kernel density estimation[END_REF] build a global edge descriptor concatenating histograms from 5 over-lapping image regions.

Local Features

Global image descriptors sometimes do not capture the spatial relationship between image objects, often carry redundant information and are usually not invariant to photometric and geometric distortions. Local features are described at key image locations or interest points that are identified in the image and supposedly carry valuable local information [START_REF] Tuytelaars | Local invariant feature detectors: A survey[END_REF]. These points can be predefined though, e.g. in the form of a dense grid over the image [START_REF] Li | A bayesian hierarchical model for learning natural scene categories[END_REF][START_REF] Winn | Object categorization by learned universal visual dictionary[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Moosmann | Fast discriminative visual codebooks using randomized clustering forests[END_REF][START_REF] Gordoa | Leveraging category-level labels for instance-level image retrieval[END_REF][START_REF] Delhumeau | Revisiting the vlad image representation[END_REF].

The descriptor then calculates statistics based on the local neighborhood usually depicting the shape of the region.

The purpose of keypoint detection is to sample a sparse set of regions in the image that are invariant to geometric and photometric transformations. SIFT (Scale Invariant Feature Transform) detects interest points using Difference of Gaussian (DoG) operator but is only partially invariant to illumination changes and affine transformations. More robust detectors are proposed by [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] based on Harris-Affine detection, the Maximally Stable Extremal Region (MSER) detector [START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF] and [START_REF] Tuytelaars | Matching widely separated views based on affine invariant regions[END_REF] based on image edge and intensity based region detection.

SURF (Speeded Up Robust Features) [START_REF] Bay | Speeded-up robust features (surf)[END_REF] detects interest points using a Hessian-Laplace based detector working on integral images to reduce detection time.

The SIFT descriptor [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] posed as a breakthrough in describing local regions and is one of the most frequently occurring descriptors in research works to date. The feature induces a histogram on a local image region that was first detected using DoG operator and then described in terms of 8 dominant orientations of the gradient. The gradient is calculated in the neighborhood of 4 X 4 spatial grid and is thus a 128 dimensional feature. SIFT is robust to geometric and photometric transformations and is invariant to scaling, translation and rotation of the image. Gradient Location and Orientation Histogram (GLOH) extends SIFT to a 272 dimension histogram computing the descriptor for a log-polar location grid [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF]. PCA-SIFT [START_REF] Ke | Pca-sift: A more distinctive representation for local image descriptors[END_REF] increases the efficiency of retrieval by reducing the dimensions of the SIFT feature, while SURF [START_REF] Bay | Speeded-up robust features (surf)[END_REF] estimates the dominant orientation of the interest point neighborhood and accumulates the horizontal and vertical wavelet responses (w.r.t. the dominant orientation) of 16 regions around the interest pixel resulting in a 64 dimensional feature. Finally using a power normalization on the SIFT has also proven to be affective as in [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] and RootSIFT [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] where square rooted SIFT descriptors are stored.

Dalal and Triggs [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] came up with the Histogram of Oriented Gradients (HOG) descriptor which is among the most successful features used for visual recognition. HOG mainly follows SIFT methodology and captures the local distribution of edge orientations where the location information is generally lost. The descriptor aggregates the edge orientations of local patches that are regularly spaced into a histogram. Several extensions and improvements of HOG have also been successful where the feature is calculated on variable sized regions [START_REF] Qiang | Fast human detection using a cascade of histograms of oriented gradients[END_REF], calculated from segmented foreground and background images [START_REF] Ott | Implicit color segmentation features for pedestrian and object detection[END_REF] and from signed and unsigned gradient information [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]. [START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF] also augment the high resolution local HOG feature with LBP statistics.

Feature Coding and Pooling

Local features capture discriminatory visual information from all over the image but they are mostly not used directly for image categorization. The low level descriptors are summarized into an intermediate representation usually through a two-step coding and pooling method.

There is an unspoken rule for the successful working of such a representation: similar images should have similar representations but it should be discriminative enough to distinguish from instances of other classes. The low level visual information is somewhat lost but the new representation is compact, is of fixed size and is more robust to descriptor noise and small transformations in the image which helps the model to be generalized to test images.

This intermediate representation encoding local visual characteristics is closer to the human

visual perception of the image and thus helps reducing the semantic gap [8,[START_REF] Jing | Learning in region-based image retrieval[END_REF].

The breakthrough for representing visual information was achieved when vector quantization was used to build the Bag of Words (BOW) model [8,[START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. A universal codebook or visual dictionary is build using features from the training images by unsupervised vector quantization. Features are coded to the nearest code or visual word. Sometimes only the most informative features are used to construct the dictionary [START_REF] Schindler | City-scale location recognition[END_REF]. Average [8,[START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] or max pooling [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] is used to build the mid-level BOW feature vector. Multiple assignments encodes a visual feature as belonging to the k nearest visual words. Soft assignment further relaxes the coding process and probabilistically assigns a feature to the closest visual words [9,[START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Van Gemert | Visual word ambiguity[END_REF]. It can be seen as assigning a weight to each encoded feature. However authors in [START_REF] Chatzichristofis | Color visual words based on non-predefined size codebooks[END_REF] revert back to assigning a local feature to a single visual word with a degree of participation, that is calculated based on the previous assignments of local features to that visual word.

Grauman and Darrell [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF] presented a multi-resolution histogram to encode local features with out using a universal dictionary. The Bag of Words or Bags of Features models are orderless and do not contain any spatial or structural information about the image. Lazebnik at al. [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] inducted spatial information into the BOW framework by building histograms for specific image regions, which they named Spatial Pyramid Matching. Each feature is coded and pooled for each of the histograms and one representation is build for the image accumulating all the histograms. Locality-constrained Linear Coding (LLC) [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] improves the spatial pyramid approach by encoding each descriptor into a projected local coordinate system with a different basis. Sparse Coding [7,[START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF] also provides an alternative to vector quantization by relaxing the cardinality constraint and removing the extreme sparseness of the representation. Sparse coding is more general and is ironically usually less sparse than a vector quantized representation. Both these works use max pooling to obtain state of the art image classification results. Boureau et al. [START_REF] Boureau | Ask the locals: Multi-way local pooling for image recognition[END_REF] use local pooling in the feature space to avoid different features encoded with the similar code (vector quantized, sparse coded) to be pooled together.

The research in image representation is further carried to build higher level representations where visual words are supposed to co-occur for certain objects or concepts. Considering different visual words as a single unit will reduce ambiguity that may arise when different intended meaning of visual words are considered. This notion of inter-relation is captured in terms of visual phrases [START_REF] Yuan | Discovery of collocation patterns: from visual words to visual phrases[END_REF][START_REF] Zheng | Toward a higher-level visual representation for object-based image retrieval[END_REF] which consist of more than one visual words and help distinguish the object from non-class instances which do not contain those specific visual words.

Recently effective techniques have been shown to improve image retrieval by aggregating element wise differences of local descriptors [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF] and aggregating Tensor products of those differences [START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF]. This results in a larger feature vector for a small visual codebook capturing important statistics about the distribution of the descriptors inside the clustering cell.

The more general Fisher Vectors have been shown to capture vital higher level descriptors distribution statistics for visual recognition tasks [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF]. First the global density of the distribution of image descriptors is estimated using Gaussian Mixture Models (GMMs) trained on all the descriptors from the training images. An image signature is then calculated in terms of Fisher Vectors which indicate the direction in which the parameters of the image model to be changed in order to best fit the global distribution. The GMM can be regarded as a generative visual dictionary and each Gaussian is considered a visual word. Supervectors [START_REF] Zhou | Image classification using super-vector coding of local image descriptors[END_REF] work with a similarly trained GMM on the image features and encodes the first order difference with the mean of the cluster with the image representation.

Classification

The We briefly review some of the popular methods for both the categories in the sections that follow.

Generative Models

Generally once the joint probability is modeled maximum a posteriori (MAP) or maximum likelihood (ML) estimates are used to find the candidate class(es) for the new image. Some pioneering works in image classification directly employed Bayesian classification to classify images into indoor and outdoor scenes [START_REF] Vailaya | Image classification for contentbased indexing[END_REF][START_REF] Luo | Indoor vs outdoor classification of consumer photographs using low-level and semantic features[END_REF]. [START_REF] Vailaya | Image classification for contentbased indexing[END_REF] further classifies outdoor images as city and landscape and continues to classify landscape images into sunset, forest and mountain.

Mori et al. [START_REF] Mori | Image-to-word transformation based on dividing and vector quantizing images with words[END_REF] use a co-occurrence model to find the correspondence between image features and the text keywords. A more robust idea is to find the correspondence between test image and the labeled images using e.g. Cross Media Relevance Modeling (CMRM) [START_REF] Jeon | Automatic image annotation and retrieval using cross-media relevance models[END_REF]. The keywords associated with the labeled images are used to annotate the test image. Huang et al. [START_REF] Huang | Improve image annotation by combining multiple models[END_REF] combine CMRM with other correspondence models to improve image annotation.

Another direction is to include latent variables in the model to associate visual features with keywords, referred to as latent Semantic Analysis (LSA) or probabilistic LSA (pLSA) [START_REF] Bosch | Scene classification using a hybrid generative/discriminative approach[END_REF][START_REF] Quelhas | A thousand words in a scene[END_REF].

GMMs are also used to model the distribution of visual features [START_REF] Permuter | A study of gaussian mixture models of color and texture features for image classification and segmentation[END_REF][START_REF] Zhang | A probabilistic semantic model for image annotation and multi-modal image retrieval[END_REF]. Blei and Jordan [START_REF] Blei | Modeling annotated data[END_REF] The visual words are sampled as appearing from background distribution, image specific distribution and topic specific distribution if they appear in images with similar semantics.

Discriminative Models

Discriminative learning does not model the data distribution rather learns directly the classification rules or separating hyperplane using the input data.

Support Vector Machines (SVM) classifier tries to find a decision boundary that maximizes the margin or separation between the negative and the positive training class instances. SVMs can be used in their linear form or with a non-linear kernel which finds the decision boundary in the high dimensional space induced by the kernel. Kernel trick maps the input features into higher dimensions and allows the SVM to find a classification boundary within that space without actually explicitly doing any manipulations in that high dimensional space. SVMs have been widely used for classifying visual data in the binary classification framework and most of the times outperform their counterparts for recognition tasks [START_REF] Alham | Evaluating machine learning techniques for automatic image annotations[END_REF] due to their generalization abilities. Some notable kernels used to find the distances between images are the radial basis function (RBF) and the chi square kernel [START_REF] Niaz | EURECOM at TRECVID 2011: The light semantic indexing task[END_REF][START_REF] Niaz | EURECOM at TrecVid 2012: The light semantic indexing task[END_REF], Histogram Intersection kernel [START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF], Pyramid Match kernel [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF] and the Spatial Pyramid kernel [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF].

Other discriminative methods like Nearest Neighbor (NN) classification [START_REF] Vincent | K-local hyperplane and convex distance nearest neighbor algorithms[END_REF][START_REF] Boiman | In defense of nearest-neighbor based image classification[END_REF] and

Neural Networks [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] have also been used to learn concept classifiers. Moreover Zhang et al. [START_REF] Zhang | Svm-knn: Discriminative nearest neighbor classification for visual category recognition[END_REF]

Fusion

Fusion of visual features or multi-modal features is gaining importance these days in the field of video content analysis and retrieval as it benefits from diverse and complementary information from different media [START_REF] Atrey | Multimodal fusion for multimedia analysis: A survey[END_REF][START_REF] Snoek | Multimodal video indexing: A review of the state-of-the-art[END_REF][START_REF] Niaz | Fusion methods for multimodal indexing of web data[END_REF]. This comes with a certain cost due to the higher complexity of multi-modal analysis as the modalities involved have different characteristics.

There are various methods and different levels at which information from different media can be combined [START_REF] Atrey | Multimodal fusion for multimedia analysis: A survey[END_REF][START_REF] Snoek | Multimodal video indexing: A review of the state-of-the-art[END_REF][START_REF] Snoek | Early versus late fusion in semantic video analysis[END_REF][START_REF] Strat | Hierarchical late fusion for concept detection in videos[END_REF]. The important questions raised when combining multimodal information are when and how to fuse. Naturally each semantic concept or group of similar concepts exhibits different dynamics from others so their fusion pattern could be different also. This argument is strengthened by the fact that one classifier and one set of features does not perform the same for each concept [START_REF] Strat | Hierarchical late fusion for concept detection in videos[END_REF] as some concepts are easy to detect with visual features only while others may not be. We briefly review the state of the art multimedia fusion methods dividing them into early and late level of fusion.

Feature Level Fusion

To perform fusion in feature space also referred to as early fusion, unimodal features extracted from different data streams are integrated into the single large vector v for training. A certain pre-processing is performed like e.g. normalization so that features be on the same scale.

Classifiers are trained for a semantic concept using these large multi-modal feature vectors and usually there is only one learning phase handling all multi-modal features at once.

Different visual features are sometimes combined to increase the power of individual features [START_REF] Law | Hybrid pooling fusion in the bow pipeline[END_REF]. However combining textual features with the stream of visual data [START_REF] Snoek | Early versus late fusion in semantic video analysis[END_REF][START_REF] Guillaumin | Multimodal semi-supervised learning for image classification[END_REF],

as well as incorporating audio based features [START_REF] Kankanhalli | Experiential sampling in multimedia systems[END_REF][START_REF] Jiang | Consumer video understanding: A benchmark database and an evaluation of human and machine performance[END_REF][START_REF] Zou | Tracking humans using multi-modal fusion[END_REF] has also proven to be helpful for certain video analysis tasks.

Decision Level Fusion

Fusion can equally be performed at later stage integrating decisions of individual classifiers thus called decision level fusion, also semantic level fusion [START_REF] Snoek | Early versus late fusion in semantic video analysis[END_REF]. Classifiers are learned for features of different media separately giving a decision like yes/no or in the form of a score or probability of presence of a semantic concept. The independent decisions can be combined using different rules or classifiers can be built to learn from the output scores.

Fusion in decision space is easier to perform as the decisions from classifiers usually have similar format. Moreover scores from new sources of information can be easily added to the final decision with only re-training the fusion part.

Late fusion has been extensively used in the state of the art due its simplicity and scalability. Weighted linear combination is an easy and effective way to combine decision from different classifiers [START_REF] Niaz | EURECOM at TRECVID 2011: The light semantic indexing task[END_REF][START_REF] Niaz | EURECOM at TrecVid 2012: The light semantic indexing task[END_REF][START_REF] Strat | Hierarchical late fusion for concept detection in videos[END_REF][START_REF] Mcdonald | A comparison of score, rank and probability-based fusion methods for video shot retrieval[END_REF][START_REF] Hua | An attention-based decision fusion scheme for multimedia information retrieval[END_REF][START_REF] Liu | A selective weighted late fusion for visual concept recognition[END_REF]. The weights are usually learned using some part of the training data as a validation set. Another scheme is to learn a classification model from the decisions based on the training data like SVM [START_REF] Snoek | Early versus late fusion in semantic video analysis[END_REF][START_REF] Adams | Semantic indexing of multimedia content using visual, audio and text cues[END_REF] or the EM [START_REF] Yan | Learning query-class dependent weights in automatic video retrieval[END_REF].

Evaluation

There are many benchmark video datasets available to judge the performance of video concept detection but we limit our evaluations to the TRECVID benchmark [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF]. TRECVID organizes a workshop each year and addresses important video analysis tasks including Copy Detection, Event Detection, Event Recounting, Instance Search and Semantic Indexing (concept detection). Many research teams including universities, technical laboratories and certain enterprises participate in the tasks. With the difficulty and variety of their evolving datasets, their widespread acceptance, their evaluation procedures and the opportunity they provide to share the research and results among the participants TRECVID benchmark, for many years now, is considered the de facto standard to evaluate performance of various video analysis tasks [START_REF] Snoek | Concept-based video retrieval[END_REF]. Therefore we have opted to evaluate our propositions only on the TRECVID datasets. Specifically we evaluated our proposed methods on the Semantic INdexing (SIN) task where the data came from various years including 2007, 2010 and 2013.

The videos are pre-segmented into shots and a keyframe is provided for each shot along with the ground truth annotations for the training set and the old test set. The list of semantic concepts to be indexed is also pre-selected and defined by NIST.

We have used Average Precision (AP) to evaluate the performance of our video concept detection models, which is also the standard used in the TRECVID evaluations for Semantic

Indexing [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF]. where the number of all the relevant documents is known pre-hand.

The Average Precision, which is actually the area under the precision-recall curve, gives importance to the order of the retrieved result in the ranked prediction of the list containing test shots.

AverageP recision

= R r=1 precision(r) × relevance(r) |{relevantdocuments}|
where precision(r) is just the precision at the r'th result in the ranked list and the relevance(r)

gives a 1 if the keyframe is labeled positive with the concept. So the precision is calculated right from the start with the most importance given to the first (top) prediction and so on.

Chapter 3

Enhancing Video Representation

Learning to index general purpose videos automatically is a very hard problem. First of all the videos are mostly homemade or self-made uploaded by users on video sharing websites such as YouTube or Dailymotion and thus lack a proper defined structure, are poorly edited, suffer from camera motion and are sometimes of poor quality. Most of the times these videos are labeled or tagged by the uploader who is also sometimes the maker of the video.

More relevant tags are sometimes added by someone watching the video. Annotation of visual content as it is now suffers from problems of bias, lack of knowledge and user specific interests.

Coming to the content of a video itself and leaving aside the lighting, motion and quality concerns the definition of a semantic concept is itself very elaborate and also complicated increasing the difficulty to build a general model for the concept. Ranging from a mere object to a very complex scene comprising multiple objects a semantic concept can take any shape or form in the video frame or can contain multiple frames. Moreover the definition of a concept or a category could be vague due to the visual variations with which it can be represented in the video. It is true as stated in [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] that a certain level of abstraction is needed to represent a concept. Moreover there is always noise when visual information is extracted from the video frames. Further information loss is incurred when going from low level visual features to mid level count based (histogram) representation, referred to as the semantic gap.

In this chapter we strive to improve standard video representation models which consists of the second stage of the video recognition pipeline presented in the introduction. Specifically we improve the Visual Dictionary or the Bag of Words model which encodes keypoints to specific clusters and pools together all the keypoint descriptors assigned to the same clustering cell. In order to achieve this improvement we present two methods in this chapter, one functioning on the construction of the dictionary [START_REF] Niaz | Entropy based supervised merging for visual categorization[END_REF] and the other adding refinement to the signature [START_REF] Niaz | Exploring intra-bow statistics for improving visual categorization[END_REF]. We first present the Bag of Words model and discuss the short comings it faces for the visual indexing task before detailing the two proposals.

Visual Dictionary Construction/BOW Model

A variety of visual information is extracted from single images, a glimpse of which is presented in chapter 2 along with the state of the art. These visual features vary in size and contain significant information about the various aspects of the concepts depicted in the images.

However as usually they are high dimensional, high in count for a single image and are too specific for a certain image type they are aggregated to form a rather moderate midlevel representation before further processing and analysis. This caters for the abstraction that we talked about earlier, unifies the visual description and usually reduces the size of the representation for one image. Moreover the amount of visual features extracted can vary from image to image but the mid-level representation is of fixed length for each image.

However the precision is lost as the pooling usually averages or maximizes over a certain criterion and the concepts now have to rely on the overall effect of the features in the images instead of some truly discriminative individual features.

We consider the Bag Of Words (BOW) model which is a popular method to represent video frames, figure 3.1, based on quantization that is inspired from text retrieval [8,[START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. It Image description in the BOW framework generally faces two important issues. First is the selection of the appropriate dictionary size and the second is the loss of information as features from all the images are considered equally for dictionary construction. This loss is in the form of contextual information and descriptor specific information. We detail these issues in the subsections below. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The Dictionary Size

For video concept detection typical size of the BOW vector or visual dictionary varies from 200 to several thousands of words. This size is directly related to the categorization performance as well as retrieval efficiency. In figure 3.1 if we increase the number of features (LIDs) extracted from each image the final signature will remain the same. I.e. even if more and more visual content is extracted from each image the final representation will only show minor differences in the individual bin values as it is an approximation of the probability density of the LIDs in the descriptor space. Since we are dealing here with hard quantization we assume that this probability density is constant in each Voronoi cell. However it is obvious that a larger visual dictionary will approximate better this continuous density than a smaller one. This better approximation of the visual content thus increases the precision of the categorization.

However as the dictionary size increases there are more cells in the same clustering space and this affects the generalization ability of the model as noisy descriptors are miss-assigned.

On the other hand if the dictionary size is kept small the discrimination is low as patches belonging to significantly different parts from the images are assigned to the same cell. There is thus a need to find a compromise between the dictionary size, its discrimination ability and its generalization capability. Although BOW is a very sparse representation, and with the increase in size the sparsity increases nevertheless the training and prediction efficiency are also affected with this increase in size. Besides, the time taken by k-means to construct the dictionary is prohibitive for a large number of centers. Moreover more training data is required to train concept models for examples with larger BOW vectors as the classifiers will have more parameters. The matter of selecting the optimal visual dictionary size is thus crucial for the performance and efficiency of the concept detection system.

In this chapter, we present the work we did to increase the discriminative ability of a visual dictionary that is of small size. The first technique we present reduces the size of a large dictionary by merging Voronoi cells that result in minimum information loss while doing the approximation. Our second method adds refinement to a small dictionary to overcome the coarseness of the BOW model.

Loss of Contextual Information

Generating the visual vocabulary through unsupervised quantization from tens of thousands of low level descriptors does not capture semantic context as category information is not accounted for during clustering. Doing so, the expressive or discriminative power of the vocabulary is affected as only overall distortion is minimized and category information is not used increasing the semantic gap between the concept and the mid-level BOW feature.

Nevertheless this does make the visual representation independent of the knowledge of the categories to be detected. We are however compelled to look into using the label information during the dictionary construction since the final goal is to detect individual concepts and label information could be useful. We can, for example, consider using contextual information to build histograms where bins k and l for all the images of cats are high and the same bins for all the images of cars are low. We want such discriminative information to be encoded automatically using examples' label information during the dictionary construction.

Loss of Descriptor Specific Information

The orderless BOW representation does not account for the importance of a descriptor to a histogram bin. Information about the location and structure of the LIDs and the position of the descriptor in the Voroni cell is usually lost. Even an outlier increases the count of a bin as it was the closest cluster center and it is given equal importance as the descriptor closest to the same cluster center. Smaller dictionaries are adversely affected by this as the Voronoi cells are larger and so the difference in the descriptors assigned to the same cell gets larger also, reducing the discrimination power.

Some Relevant Works

The problem of increasing the discriminative power of BOW model has been attacked by many authors in the recent years. We briefly overview some works that address the three problems detailed above.

Wang [START_REF] Wang | Toward a discriminative codebook: Codeword selection across multiresolution[END_REF] builds a multi-resolution codebook by adding a new codeword at each step using hierarchical clustering and a selection criterion based on Boosting. This is done to find a compromise between a small codebook that lacks discriminative power and a large one that may result in overfitting. Perronnin et al. [START_REF] Perronnin | Adapted vocabularies for generic visual categorization[END_REF] represent each image with a bipartite histogram by building universal and class specific vocabularies using maximum likelihood estimation. Lin et al. [START_REF] Lin | Image classification using adapted codebook[END_REF] use a similar principle to bridge the semantic gap between the concept(s) depicted in the image and the low level features. k-means is used to generate separate class specific vocabularies followed by an agglomerative clustering on class codebooks to get the universal vocabulary. In both these works an image is represented by a set of histograms, one per class, using the amalgamated codebooks. Hao and Jie [START_REF] Hao | Improved bags-of-words algorithm for scene recognition[END_REF] present an improved BOW algorithm for scene recognition exploring discriminative power of codewords when representing different scene categories. They obtain a weighted histogram to code every image that highlights the discriminative capabilities of each codeword for each category.

To generate a discriminative codebook Winn et al. [START_REF] Winn | Object categorization by learned universal visual dictionary[END_REF] present a two step clustering framework, where they compress an initial large dictionary by optimizing a statistical measure of discrimination that finds a compromise between low intra-class variance and inter-class discrimination. Moosmann et al. [START_REF] Moosmann | Fast discriminative visual codebooks using randomized clustering forests[END_REF] build a set of randomized decision trees using the class labels with the leaf of a tree representing a spatial code (visual word). They calculate information gain of the split at each step of tree growing and use it as a threshold to split the tree based on the descriptor dimension at that level. Su and Jurie [START_REF] Su | Visual word disambiguation by semantic contexts[END_REF] improve the performance of the BOW model by disambiguating different meanings of the BOW using semantic context. The semantic context is embedded in the BOW histograms to generate context specific representations. An image is then represented by combining different context-embedded BOW histograms by selecting the most appropriate context for each visual word. Wang and Mérialdo [START_REF] Wang | Weighting informativeness of bag-of-visual-words by kernel optimization for video concept detection[END_REF] weigh the informativeness of different visual words in the framework of kernel optimization. Given a concept, usually only some of the visual words frequently appear while the presence of the others are nearly random.

In other words, some visual words are more informative or important for the detection of a specific concept, while the others may be noisy. In most current approaches, for different concepts, each visual word is treated equally. They find weights of each visual word for each concept by maximizing a Kernel Alignment Score giving larger weights to more important visual words. This improves the SVM performance for detecting that specific concept. Philbin et al. [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] improve object retrieval in large scale databases by recovering information from descriptors which were lost in quantization. They use soft assignment to assign a descriptor to r closest cluster centroids, instead of a single centroid, weighted by the inverse of distance to the centroids. They try to overcome the problem of descriptor noise where a descriptor of a similar image patch may be assigned to a completely different visual word due to some distortions. Nevertheless all the descriptors assigned to the same visual words are considered similar. Van Gemert et al. [START_REF] Van Gemert | Visual word ambiguity[END_REF] also study visual word ambiguity through different weighted soft assignment methods.

In [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] authors have localized each descriptor inside a Voronoi cell based on a Hamming Embedding mechanism to increase the precision of the BOW histogram for the image search task. They perform image classification in a similarity space adapted from the Hamming Embedding based precision mechanism [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF]. Jegou et al. [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF] perform large scale image search using a signature obtained from calculating statistics on a small dictionary. The signature, called Vector of Locally Aggregated Descriptors (VLAD), though obtained from a small dictionary is itself large and affects the problem efficiency. Their work is a nonprobabilistic approximation of the Fisher vectors [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] represented by the gradient vector of the log likelihood depicting the direction in which the parameters of the generative model of the data should be modified to best fit the data.

Entropy based Supervised Merging

Our first proposal [START_REF] Niaz | Entropy based supervised merging for visual categorization[END_REF] tackles the first two problems presented in the section above by constructing a relatively small dictionary from a larger one using category information. Since dictionary construction achieved through unsupervised clustering does not take any advantage of the relationship between the features coming from images belonging to similar concept(s), this enlarges the semantic gap. We believe that the category information should be used in the dictionary construction process to encode some contextual information. Since the final classification tries to identify each category differently, encoding contextual information into the visual representation from an early stage may help improving the final concept model. This information can be used to build concept specific visual words or even concept specific dictionaries.

We aspire to build visual dictionary where the clustering cells are more consistent with the label information. Consider for example that within our training set we have a few images of the concept Car and our local interest points detector always detects wheels as some of the interest points. Now wheels can vary in visual appearance due to changes in illumination, occlusion, perspective distortion etc.. Moreover wheels of different cars could have different appearances. During the clustering for codebook construction not all the wheels are necessarily assigned to the same visual words. Label information can be used to merge clusters which largely constitute of wheel LIDs, figure3.2. This can be extended to other concepts to group together for example wheels of Bus or Truck as shown in the bottom of the figure 3.2. However there may be cases where due to noise the visual word containing wheels also contains some instances of the visually close "windows" from the concept Building. Here we would like to partition the Voronoi cell into two cells maximizing the wheels and windows in Our proposal follows the first paradigm in figure 3.2 where we join two clusters accumulating all the assigned LIDs to the same histogram bin. We do the merging by designing a criterion that maximizes the information about the label distribution. We use a clustering method with only a few k-means' mean shift iterations using a better centers initialization based on K-means++ [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF] to generate a larger than required number of clusters before doing a supervised merging. This significantly reduces the number of clusters (visual words) for faster training and retrieval. We initially merge neighboring clusters based on entropy minimization criteria that allows the generation of non-convex connex clusters. We present three such merging criteria in order to increase the discriminative power of BOW with an increase in the retrieval performance over the baseline. We then relax certain constraints in our merging criteria to allow the generation of non-connex clusters. We have used SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] calculated on keypoints extracted from images (keyframes), contrary to dense sampling [START_REF] Winn | Object categorization by learned universal visual dictionary[END_REF][START_REF] Moosmann | Fast discriminative visual codebooks using randomized clustering forests[END_REF], labeled with one or more semantic concepts.

We also show that using our dictionary construction from supervised merging a smaller wheels and windows dictionary gives the performance comparable to the retrieval performance given by a dictionary upto 8 times its size.

Supervised Clustering Based on Entropy Minimization

In the two step clustering paradigm, Fig. In the second step the number of clusters is reduced by 1/p by merging neighboring clusters repeatedly based on entropy driven information loss minimization criterion.

Concept Distribution Entropy Minimization

For deriving this minimization criterion we have to work at the individual descriptor level;

i.e. we have to know the labels associated with each LID. We have m concepts (labels)

l k ∈ L, k = 1 .
. . m and we know with what concept(s) each image I is labeled with. Since video datasets are multi-label, each image can be associated with more than one concept.

Thus in the end we know the labels of each image descriptor (keypoint). Now suppose as a result of the initial clustering we have p * D clusters, and for each cluster

C i ∈ C, i = 1 . . . p * D
we know the labels of the keypoints assigned to it (we are only treating keypoints coming from labeled shots). For finding the number of keypoints belonging to a concept l in the cluster C i we keep in mind that there may exist images that are labeled with more than one concept. Also generally keypoints extracted from a single image are assigned to different centers. Thus we compute the number of occurrences of concept l in the cluster C i as:

|l ∈ C i | = Ilabeledwithl |LID(I) ∈ C i | |LID(I)| (3.1)

Unsupervised clustering p*D visual words

Supervised grouping D visual words We find next the conditional probability of the concept l given the cluster C i :

p(l/C i ) = |l ∈ C i | k |l k ∈ C i | (3.2)
The set N b{i} contains the neighbors of the cluster C i where two clusters are neighbors if the midpoint between their centers is closer to those two centers than to any other center.

When joining two neighboring clusters C i and C j , where j ∈ N b{i}, all the keypoints in C j are assigned to C i , and all the neighbors of C j are added to those of C i . C j is then deleted from the set of clusters i.e. C = C\C j .

The entropy of the concept distribution given the visual dictionary V = {C}:

H(L/V ) = - C p(C) L p(L/C) log p(L/C) (3.3)
Since we are making further approximation by reducing the set of clusters to represent the probability density of the LIDs we lose information when we merge two clusters. This loss in information is represented by the entropy which is increased when any two clusters are merged. There are times when the increase in entropy is zero when the two merged clusters only contained LIDs labeled with similar concepts.

Airplane Boat Hand

Playing Soccer Riding Bike

Initial Clustering

Concept-wise merging If we merge C i and C j , such that j ∈ N b{i}, the resulting dictionary is V ′ ij with one less visual word and entropy H(L/V ′ ij ).

V ′ ij = V C i ←C j
The combination C i ∪C j that minimizes the increase in entropy is our target combination and those two clusters are merged together. We select i and j to minimize the new entropy.

min i,j H(L/V ′ ij )
This step is repeated p * D -D times until the desired number of clusters D is reached.

Concept Dependent Entropy Minimization

The entropy minimization principle can be also used to find a merge of clusters independently for each concept using entropy of only that concept. This way we shall have one combination of clusters per concept and thus we will end up with a different BOW representation for each semantic concept, figure 3.5. Using the above notation, for the concept l k ∈ L the entropy is given by:

H cd (l k /C) = - C∈C p(l k , C) log p(l k /C) + p(l k , C) log p(l k /C) (3.4) where p(l k , C) = p(C) -p(l k , C) and p(l k /C) = 1 -p(l k /C).
Now for each possible combination of two neighboring clusters we will calculate the entropy to find the best merge by choosing the two clusters that result in minimum entropy increase, given by: min i,j

H cd (l k /V ′ ij ) (3.5)
This step is repeated, reducing the total number of clusters by one each time, until the desired number of clusters is reached. This whole process is repeated for each concept resulting in a different clustering for each concept as well as a different bag of words model. An image is thus represented by a set of histograms, one per concept.

Average Concept Entropy Minimization

Another possibility to obtain a clustering combination is by combining the output of the concept dependent clusterings. This is done by taking the sum of entropy of all concepts for a merge of two clusters and then minimizing that sum for every possible combination of clusters. This clustering of average over all concepts is given by:

min i,j l k ∈L H cd (l k /V ′ ij ) (3.6)
where

H cd (l k /V ′ ij )
is the concept dependent entropy as given in (3.4). The difference between this criterion and the one presented in equation 3.3 where we minimized the entropy of the concept distribution is that here we look at each label individually and minimize the sum of concept dependent entropies. With concept dependent entropies each label has the same effect irrespective of the number of LIDs labeled with that label present in the clusters to be merged and we minimize this effect on average. With the concept distribution entropy minimization the label with more LIDs in the two target clusters has more effect on the entropy than the ones having fewer LIDs.

Relaxing Constraints

Based on the results shown in Sect. 3.2.2 we select the best entropy minimization based clustering criterion and make few changes. We have so far only used keypoints from labeled images to minimize the entropy for merging clusters. However the labeled images represent only a certain percentage of the whole corpus which is used to construct the initial dictionary.

To reduce the bias of the labeled keframes over the unlableled ones we include all the keypoints in the second step of clustering. This is done by including all the unlabeled keypoints as the (m + 1) th concept during the calculation of the entropy of the concept distribution and recalculating the mapping based on entropy minimization over M + 1 concepts.

We further relax the constraint of merging only neighboring clusters where any two clusters (not necessarily neighbors) can be mapped together in the high dimensional disjoint clustering space. This allows the generation of a non-connex BOW model. These alterations are further explored in the Sect. 3.2.2 discussing the experiments and results.

Experiments

We present here experiments carried out on the TRECVID 2007 Sound and Vision database comprising 219 videos [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF][START_REF] Smeaton | High-Level Feature Detection from Video in TRECVid: a 5-Year Retrospective of Achievements[END_REF] with around 36,000 video shots. A keyframe is extracted from each shot and is the shot representative. The training corpus consists of 110 videos and the other half is used for tests. Twenty semantic concepts are used to demonstrate the results. We have used 1 vs all SVM classifiers with chi-square kernel of degree 2 using the LIBSVM [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] package for each concept.

Supervised Clustering Results

Initially we evaluate the performance of supervised clustering for a final dictionary of 500 visual words using the three types of entropy minimization criteria. In our experiments the maximum value of p, as described in Sect. 3.2.1, is 8. That is the maximum size of initial visual dictionary obtained through k-means is 8 times the size of the desired supervised dictionary. To obtain a large initial dictionary we have used k-means++ algorithm [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF] for a better initialization in order to avoid a large number of k-means iterations, which is costly for a large number of centers. K-means++ is an initialization method that selects initial seeds far from each other while minimizing the effects of outliers. This is done by choosing the new cluster centers with a probability proportional to its distance to the closest center already chosen. After the initialization only 10 normal k-means iterations are performed to generate initial visual dictionaries.

Three Entropy Minimization Criteria

Using these large dictionaries supervised mappings are done from clustering space with 1000, 2000 and 4000 centers to 500 centers by merging neighboring clusters using entropy minimization criteria. In all three cases the final dictionary generated is always 500-words big which is then used to represent images as histograms. SVM classifiers are trained for each concept and independently for each set of histograms obtained through entropy minimization based mappings. The Mean Average Precision (MAP) for all 20 concepts is shown in the Table 3.1 for the 3 mapping criteria and for the 3 initial cluster sizes, along with the MAP obtained using 500 visual words achieved directly through k-means (baseline).

From table 3.1 we can see that with the increase in the number of initial centers the individual concept dependent entropy minimization criteria for mapping suffers from overfitting as it generates dictionaries for each concept independently. The image level labeling does not translate well to increase the discriminative power of the BOW model built for This effect is carried on to the average (of concept dependent) entropy minimization as the retrieval performance is adversely affected with the increase in the number of initial cluster centers in the first step of clustering. Here however some loss is recovered due to averaging the concept dependent minimization, as evident from the last column of the table 3.1. Contrarily, merging neighboring clusters using minimization of the entropy of concept distribution given clustering improves retrieval performance with the increase in the size of the initial number of centers (Min Ent in table 3.1). This improvement is 10% overall when merging from an initial dictionary of 4000 visual words.

Concept-wise Performance for the Best Criterion

From table 3.1 we can select the best merging criterion which is the first criterion based on concept distribution entropy minimization. We use only this method to generate visual dictionaries of 1000 words obtained from larger dictionaries and check the performance on the similar dataset.

As it turns out the 1000 words merged dictionary outperforms the baseline of the same size and the performance increases as the initial dictionary size increases. as the number of initial centers is increased. The MAP for 1000-words dictionary increases from 0.0796 (baseline) to 0.0831 with 8000 initial centers.

Alternative Mappings

We test retrieval performance for three simple modifications in the merging criterion. To see the effect of including the unlabeled examples in the second step of our clustering framework we include all keypoints coming from the unlabeled keyframes as a new concept making the total number of concepts m + 1. The rest of the method remains the same which is the best performing entropy minimization criterion from the previous sub-section.

The second alternative is to allow the merging of non contiguous cells eliminating the constraint that only neighboring clusters can be merged, and the third version includes the unlabeled features while merging clusters over the whole clustering space. The MAP scores for a final dictionary of 500 words are presented in Table 3.2. Here we see good performance for the merging of 1000 initial clusters into 500 for the three alternatives and then a decline in the performance as the number of initial clusters is increased. This may be due to some overtraining as the number of choices for merging clusters are increased with the relaxation of constraints. The problem with including keypoints from unlabeled examples is that they overpower the entropy minimization criterion and some of the mergings ignore the information coming from keypoints labeled with true concepts. This increases with the number of initial centers and explains the decline in performance. However the performance is still better than the baseline results in each case.

Maximum Concept-wise Improvements

Finally we give upper bounds of improvement for each concept with highest average precision score selected from the retrieval results of different initial dictionary sizes for concept distribution entropy minimization with (i) neighboring constraint, (ii) inclusion of unlabeled features, (iii) relaxing the neighbor constraint and (iv) the inclusion of unlabeled features with the relaxation of neighbor constraint. Tables 3.3

Small and Informative vs Large Dictionaries

In the previous sub-sections we have shown results of our technique for building a visual dictionary and compared them to retrieval results of the baseline using a dictionary obtained through sufficient number of k-means iterations. In those cases the sizes of the baseline and supervised dictionaries were same (500 words and 1000 words). We claimed that the retrieval performance of using dictionary obtained through supervised merging matches that of using a larger dictionary which is evident from the results in the Table 3.4.

SVM classifiers were trained for larger dictionaries containing 1000, 2000, 4000 and 8000 visual words. These are the dictionaries obtained in the first stage of the supervised merging using k-means. The training and retrieval time for these larger BOWs is much higher and the performance is comparable to the smaller supervised BOW models. From tables 3.4

(A) and (B) we can see that the MAP score for the visual codebook with 2000 words is 0.0814% and the MAP score for the 500 words merged dictionary from an initial 4000 words dictionary is 0.0813%. Similarily the performance for the codebook of 4000 words is 0.0830% and that of a 1000 words merged one with 8000 initial centers 0.0831%. So we can safely say that supervised clustering builds discriminative models that achieve performance similar to a dictionary 4 times their size.

If we further increase the size of the baseline dictionary (to 8 times the merged one) the difference in performance is not so great. For example the 8 times smaller dictionary only results in 2% performance decrease as can be seen in the last two columns of the Table 3.4-(a) where we go from 4000 to 500 visual words and less than 2% performance decrease as evident in the last two columns of the Table 3.4-(b) where the size is reduce from 8000 To 1000.

The difference in performance will increase as the size of the first step dictionary increases as it becomes richer and richer. While merging helps to capture important semantic information the performance of the resulting supervised dictionary will be limited as the smaller dictionary will always be a coarser representation of the visual space. Although we are using the best merging criterion that minimizes the entropy of the whole concept distribution we still only calculate the mappings of the merging using only the training dataset and the resulting codebook still suffers from some overtraining.

As far as the computation overhead for supervised clustering is concerned it only uses the information from the image labels. Thus it does not perform any direct computation on the image features. The time complexity of supervised clustering is O(n 3 ), with n = p * D, which is the cost borne once at the clustering stage during training phase giving a mapping from p * D visual words to D visual words. After the two step clustering the costs of baseline and supervised dictionary for the remaining stages of video retrieval are similar.

Intra-BOW Statistics

Research in video retrieval systems is mainly inspired by the state of the art text retrieval where high dimensional descriptors are quantized to visual words making a Bag Of Words (BOW) histogram for an image. For a small BOW model potentially different descriptors could get assigned to the same visual word. Recently however refinements have been proposed

to recover some of this representation loss for this simplistic model of visual description of images by studying the distribution of descriptors within the visual words [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF][START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Jain | Hamming embedding similarity-based image classification[END_REF][START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF].

Following the same foot-steps we enhance the BOW by encoding [START_REF] Niaz | Exploring intra-bow statistics for improving visual categorization[END_REF] the position of each of the descriptor inside the quantized cell according to its centroid. Here a new small BOW is built by quantizing the differences between descriptors and their cluster centers. Embedding this new feature with the original to represent images increases precision of video concept detection. We compare our method to a BOW based baseline on the TRECVID 2007 and the TRECVID 2010 [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF][START_REF] Smeaton | High-Level Feature Detection from Video in TRECVid: a 5-Year Retrospective of Achievements[END_REF] datasets and show that adding the refinement proposed always improves the semantic indexing task. We also compare our method to that of [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] and show that it outperforms the Hamming Embedding Similarity based classification on the TRECVID 2007 dataset and illustrates comparable performance on the TRECVID 2010 set.

Our intention is to find a compromise between retrieval efficiency and discriminative power of the BOW model. We suggest to add important information to the coarse dictionary by exploring intra-BOW statistics rendering it more discriminative with a little increase in its size. We propose an enhancement of the traditional codebook by distinguishing the descriptors assigned to the same visual word, following the refinement proposed in [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]. We calculate the difference between descriptors and cluster centroids similar to [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF] but instead of summing them up along each dimension we quantize them to build a secondary signature to be used along with the primary BOW feature. Furthermore our signature is much shorter in length than that of [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF]. Our method is directly adaptable in the BOW framework as the added signature is easily computed directly from the quantization information as opposed to conversion into a similarity space [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF].

We compute the proposed refinement for visual dictionaries of varying sizes and prove that adding the new refinement based signature to the BOW model always significantly improves performance of the video indexing task for the TRECVID 2007 and TRECVID 2010 datasets. The results also indicate that adding the very small refinement signature to a smaller dictionary outperforms the performance of a much larger dictionary thus reducing the training overload, required for learning models for large dictionaries, and the retrieval time. We also show that the indexing performance is superior to or equal to the technique proposed in [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF].

Difference BOW

In the BOW framework all the image descriptors assigned to the same visual word are considered identical, irrespective of the difference between them in the high dimensional Voronoi cell. To make the visual dictionary more discriminative its size should be increased, however this affects the application efficiency along with the generalization capability of the dictionary. Furthermore the construction time of the dictionary increases with its size. On the other hand a small dictionary generalizes well to noisy descriptors but does not give good classification results. Using a coarse dictionary for classification precision is lost as potentially different image patches are assigned to the same visual word due to their somewhat similar appearance in an image. Consider as an example a visual word depicting tire in the visual space. Now this word may contain tires from cars, motor bikes or even bicycles. We intend to further subdivide the space inside a Voronoi cell so that the tires that are visually very close to each other group together.

We thus try to calculate the position of each descriptor inside the clustered cell respective to its centroid and encode it along with the BOW representation. This is done to refine the BOW representation by differentiating each descriptor inside the same Voronoi cell from the others. Differentiating descriptors inside the clustering cell increases precision of the indexing task. Doing this we also find a trade-off between training / retrieval efficiency and discriminative power of the visual dictionary as the information we encode is small in size compared to the BOW model but is meaningful.

To acquire this descriptor specific information the idea is to partition the high dimensional clustering space to measure the similarity between the local descriptors assigned to the same visual word. In Hamming Embedding [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] authors localize each descriptor inside the clustering cell and then generate a low dimensional binary signature capturing this localization. Following the same inspiration we employ a simple global mechanism to localize a descriptor inside a Voronoi cell focusing on the notion that two distinct descriptors inside the same cell should have a sub-signature different from each other.

Each Voronoi cell in the high dimensional clustering space has descriptors located all over.

We show distributions of Euclidean distances between the center and the assigned descriptors in the figure 3.7-(a) for a cluster (a Voronoi cell) with maximum number of descriptors, from a 500 words dictionary on TRECVID 2007 training data. The distance is also the magnitue of the difference vector between the descriptor and the cluster centroid. Although the distance is normally distributed the range of values for distance is very large and could be a good candidate to differentiate descriptors within the cell. But doing so does not include any location which can be recovered by considering difference vector as a whole instead of its magnitude. Also DBOW vectors should be given image specific weights as for an example image certain bins might dominate the others in BOW.

We use frequency of keypoints in BOW to weight DBOW bins. To achieve this each difference vector belonging to a cluster is assigned a weight equal to the number of descriptors belonging to that cluster, or the size of that BOW bin:

w x = |x ∈ c i |.
The weight of a DBOW word w d j is then calculated by adding the weights of all the difference vectors that are quantized to d j given by,

w d j = x∈d j w x
and normalized by the sum of weights for all DBOW bins. These weights are calculated for each image separately. We actually use square root of these weights in the experiments due to the high effect of the linear weights. [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] with which we compare our method.

Experiments

As clustering such a huge number of descriptors is a tedious task we have again employed k-means++ algorithm [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF] for a better initialization. K-means++ initialization is followed Classifiers: For all the experiments on the TRECVID 2007 dataset we have used nonlinear SVM classifiers from LIBSVM [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF]. In each setting, for each concept a 1 vs all SVM classifiers is used with chi-square distance using RBF kernel of degree 2. The SVM and kernel parameters are optimized by doing gridsearch on the development set. Contrarily for the TRECVID 2010 dataset we have used linear SVM to learn from a suitable feature map (homogeneous kernel map) built by the histogram intersection kernel [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF][START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF]. Here we only have to optimize the SVM parameter.

Hamming Embedding Similarity Feature

For comparison to the state of the art we have implemented the Hamming Embedding (HE)

Similarity based image classification framework for the TRECVID datasets based on [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF].

Jain et al. have embedded the HE based encoding into a similarity space for image classification [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF].We have followed the similar steps described in [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF].

In Hamming Embedding a short binary signature is added to each descriptor refining its location inside a Voronoi cell. A Voronoi cell is divided into 2 m portions by m hyperplanes.

Each hyperplane is described by a binary hamming bit. Two descriptors lie on the same side of the hyperplane if their corresponding hamming bit reflects the same value. Two descriptors match if they lie in the same cell of the clustering space and if the distance between their Hamming signatures is upto a threshold h t . Inferring from [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] we have used m = 64 and a fixed threshold of h t = 22 for all experiments. System details can be found in [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] and [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]. It is important to mention here is that we have used SIFT descriptors from the development sets of TRECVID 2007 and TRECVID 2010 datasets separately to generate the Hamming Embedding hyperplanes (the median values) for each cluster center. This is also done separately for each of the three dictionary sizes from 500 to 2000 as they embed different clustering spaces.

Hamming distance between signatures cannot be directly employed for image classification as it does not produce a global feature for each image like the BOW model, but instead measures distance between two images. Thus an image is represented in similarity space by calculating and aggregating Hamming distance between its descriptors and a set of reference images, as [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF]: To keep harmony we have used the number of random training images N to generate the HE similarity signature equal to the size of the underlying dictionary. So for calculating the HE similarity signature of size N = 500 we have used the BOW model with 500 visual words, for N = 1000 the underlying BOW model used is 1000 and so on for all experiments.

I HE = [
We do the power normalization of the HE similarity scores signature as described in [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] for values of α ∈ [0, 1] and obtain best results for the values 0.3 and 0.5 doing cross validation on the development set for both datasets.

Results

Results for three versions of each method are shown in the tables 3. to the BOW based feature for all dictionary sizes. Adding the DBOW bins to the BOW improves results significantly even with the addition of as little as 10 difference bins. Another important result produced is the performance of the small BOW-DBOW feature compared to that of a large BOW feature. As evident form table 3.5 Adding 100 difference words to the base dictionary of 500 words outperforms the performance given by a baseline dictionary almost twice and even four times its size.

We show the increase or decrease of the performance of the methods relative to the baseline methods. To this end for each of the methods in Table 3.5 we select the best score for each concept and show its difference from the score obtained by the baseline for that concept. Thus for HE similarity the best performance is chosen from the normalized and un-normalized versions of the method and for DBOW method the choice is made between the scores from varying sizes of DBOW. These relative scores are shown in figure 3.9. For shows that the DBOW performs comparable to the basic BOW double its size. The overall low scores are due to the linear SVM used on the complex dataset.

Conclusions

We have seen that the discriminative ability of the Bag of Words model increases when performing the two step supervised clustering. The performance of a much smaller dictionary obtained through supervised merging reaches that of larger dictionaries obtained through kmeans. The merging step is fast and incorporates already available label knowledge for calculation of the entropy. Although class specific merging of clusters overfits the BOW representation the performance is high as long as the initial number of clusters is kept low.

The introduction of DBOW bins encoding the position of descriptors inside the clustering subspace shows a lot of promise in rendering a compact dictionary more discriminative. We compared our method to a state of the art method for image classification [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] showing that it is consistently outperformed on two video datasets for the semantic indexing task. Here again we have seen a small dictionary with the added DBOW vector outperforming a much larger one. The performance of such a system is limited mainly because of the unavailability of sufficient annotated examples, descriptor noise and the semantic gap that is the representation difference between the high level concept and the low level feature. Finding the optimal parameters of the learner for each concept adds to the difficulty of this task. Since acquiring sane annotations for semantic concepts is expensive and some categories lack enough positive examples, we argue that making use of the multi-label nature of the video datasets and jointly training concepts together can positively affect the performance of the learning task [START_REF] Niaz | Leveraging from group classification for video concept detection[END_REF][START_REF] Niaz | Improving video concept detection through label space partitioning[END_REF].

This leads us to explore a new learning paradigm in which we try to combine concepts or labels and learn them together. A glimpse of this new paradigm can be seen in the figure 4.2 where all the concepts become part of some groups or meta-concepts. It is important to note here that the final classifier built based on joint concept information is a regular binary classifier as evident in the figure 4.3. Next we briefly describe some methods addressing multi-label classification and present some closely related domains before describing our methods to solve the problem.

Multi-label Classification

Content based retrieval, semantic indexing or concept detection can be naturally regarded as multi-label classification problems. In multi-label classification the aim is to learn from data labeled with possibly more than one label and predict a set of labels for an example.

This combination of labels in the predicted set could not be present at the time of training.

It is important to distinguish Multi-Class Classification, where each example is considered to have only one label while the classification results in one of more than two classes. As for the more general multi-label classification each instance can be predicted to have multiple classes.

[141] has divided the approaches to solve multi-label classification into two categories:

Algorithm

Knowledge Transfer and Semantic Sharing

Us humans have the great ability to recognize previously unseen objects by relating them to a known object. For example if someone sees a four legged animal (e.g. a puma) for the first time they can correctly identify the family (e.g. cat) and can make correct guesses about its characteristics (e.g. it is a mammal, carnivore etc.). This is possible because we identify the properties this new object shares with the other objects we know. This trend of sharing information between classes has been reflected in the research in computer vision to recognize unseen objects, classify objects with very few positive examples and to improve recognition of previously known classes. These techniques use similarity (or dissimilarity) between classes to build new features and are regarded as label sharing, knowledge transfer and feature adaptation in the literature.

Bart and Ullman [START_REF] Bart | Single-example learning of novel classes using representation by similarity[END_REF] propose to minimize the prohibitive cost of collecting annotated training data by learning new classes with only one example using similarity with other classes. In [START_REF] Bart | Cross-generalization: Learning novel classes from a single example by feature replacement[END_REF] they use information from previous classes to select features for the novel class, also with only one example. Fergurs et al. [START_REF] Fergus | Semantic label sharing for learning with many categories[END_REF] calculate semantic distance between two labels using the WordNet [START_REF] Miller | Wordnet: A lexical database for english[END_REF] hierarchy. The label sharing is used to build a semantic Chapter 4. Leveraging from Multi-label Data 54 matrix which reflects similarity between classes. This matrix is used in a semi-supervised learning framework to improve classification results on large image datasets. In [START_REF] Rohrbach | What helps where -and why? semantic relatedness for knowledge transfer[END_REF] authors use linguistic knowledge bases to automatically determine the knowledge that is to be shared among classes to recognize objects.

Following we review certain techniques that implicitly or explicitly share information among classes for visual processing. [START_REF] Zhang | Attribute-augmented semantic hierarchy: towards bridging semantic gap and intention gap in image retrieval[END_REF] take user feedbacks on images as well as attributes to refine search results of a content based retrieval system.

Parikh and Grauman [START_REF] Parikh | Relative attributes[END_REF] go beyond categorical labeling of attributes and present relative attributes. They learn a ranking function for each attribute that defines the degree to which the attribute is present in the image. These relative attributes are also used to define unseen categories in relation with the observed categories.

Use of attributes in large scale video retrieval or classification is rare, however [START_REF] Yu | Weak attributes for large-scale image retrieval[END_REF] describes a video concept sparsely from a set of around 6000 weak attributes. Such weak attributes include classifiers scores on low level visual features and classemes, image distance to some randomly selected images based on the visual features and some discriminative attributes. Weak attributes for a query concept are found through a semi-supervised graphical model using correlation between the concepts and the attributes labels.

Hashing and Binary Codes

Closely related to attributes is hashing [START_REF] Weiss | Spectral hashing[END_REF][START_REF] Salakhutdinov | Learning a nonlinear embedding by preserving class neighbourhood structure[END_REF] which tries to distinguish examples by assigning binary representations to individual images. The goal here is to distinguish the object classes while taking care of the within class variability. The solution assigns compact binary codes directly to the data points which are images in most cases. These codes are similar for semantically similar items and can be efficiently computed for new images. Retrieval is very fast as matching images is replaced with only calculating hamming distance between the binary codewords for images [START_REF] Weiss | Spectral hashing[END_REF][START_REF] Salakhutdinov | Semantic hashing[END_REF][START_REF] Jain | Asymmetric hamming embedding: Taking the best of our bits for large scale image search[END_REF].

The binary codes should be able to distinguish between classes, should be flexible to cater disparity within class and should be easily calculable for new images [START_REF] Weiss | Spectral hashing[END_REF][START_REF] Rastegari | Attribute discovery via predictable discriminative binary codes[END_REF][START_REF] Heo | Spherical hashing[END_REF].

Since finding binary codes for a dataset is an NP hard problem [START_REF] Weiss | Spectral hashing[END_REF] there have been many

techniques to efficiently compute these codes for a given problem. Spectral hashing [START_REF] Weiss | Spectral hashing[END_REF] calculates binary codes by thresholding a subset of eigenvectors of the Laplacian of the similarity graph.

Torralba et al. [START_REF] Torralba | Small codes and large image databases for recognition[END_REF] use two data dependent approaches working on image neighborhood information to generate binary codes for large scale image recognition. Raginsky and Lazebnik [START_REF] Raginsky | Locality-sensitive binary codes from shift-invariant kernels[END_REF] use random projections from a low dimensional mapping of the original high dimensional. Jégou et al. [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF] use binary codes to efficiently utilize memory for very large scale image search. They use an efficient quantization jointly with dimensionality reduction to obtain the binary codes.

Rastegari et al. [START_REF] Rastegari | Attribute discovery via predictable discriminative binary codes[END_REF] combine attribute learning with generating binary codes and jointly learn all the attributes (binary codes) together for all the training data. They also validate their method for novel category recognition where the test set contained different classes than those present at training. Spherical hashing [START_REF] Heo | Spherical hashing[END_REF] assigns each image a binary code by dividing the feature space into hyperspheres instead of hyperplanes. Each image can lie either inside or out of a hypersphere and each hypersphere is indexed by a bit of the binary code. Two images for which the corresponding bits lie in similar hyperspheres represent a stronger bound than their bits lying on the similar side of a hyperplane. Moreover the length of the codes are half as those in the predecessor with improved performance.

Repetetive Codes

We can also look into multi-class classification for getting hints to solve the more general classification problem at hand. Hastie and Tibshirani [START_REF] Hastie | Classification by pairwise coupling[END_REF] Ternary representation encompasses one-vs-all approach with one of the labels as +1 and all the rest are -1, and one-vs-one or the pairwise approach where apart from two labels all the rest are 0 in the dichotomies. Figure 4.4 shows an example of the M matrix for the binary and ternary ECOC and also shows a simple decoding using hamming distance HD.

Ternary ECOCs are also natural extension of ECOC methods for multi-label classification [START_REF] Armano | Error-correcting output codes for multi-label text categorization[END_REF][START_REF] Escalera | Separability of ternary codes for sparse designs of error-correcting output codes[END_REF][START_REF] Kajdanowicz | Multi-label classification using error correcting output codes[END_REF]. Authors in [START_REF] Mirza-Mohammadi | Ranking error-correcting output codes for class retrieval[END_REF] perform class retrieval using ECOC on multi-label datasets.

They use semantic distance and feature distance between labels in unison, and alter the ECOC decoding process to get ranked lists for each concept. Armano et al. [START_REF] Armano | Error-correcting output codes for multi-label text categorization[END_REF] take ECOC from binary to ternary representation to cater multi-label Text Categorization. The dichotomies are built in a straight forward manner by using all the present combinations in the training label set.

Ferg and Lin [START_REF] Ferng | Multi-label classification with error-correcting codes[END_REF] present an ECOC framework for multi-label classification problems and demonstrate its success on the Random K-labelset (RAKEL) algorithm. Contrarily [START_REF] Kajdanowicz | Multi-label classification using error correcting output codes[END_REF] did not find ECOC to be suitable for RAKEL but found good classification results with Bode-Chauduri-Hocquenghem (BCH) ECOC which outperformed the binary ECOC. However they did not test ternary ECOC. Pujol et al. [START_REF] Pujol | An incremental node embedding technique for error correcting output codes[END_REF] add dichotomies to an already generated ECOC setup with certain dichotomies by minimizing classification error on validation data.

Wang and Forsyth [START_REF] Wang | Large multi-class image categorization with ensembles of label trees[END_REF] partitions the label space of 1000 categories to generate binary trees for multi-class image categorization. They outperform random partitioning of label space with ensemble (forests) of label trees where for each category the highest score is selected among the trees of the forest as the classification result. In one ensemble the error from the previous tree is used to generate the next one by using some validation data.

More recently the trend has been to find the most representative set of binary classifiers in the ECOC framework. This necessarily means using the training data to generate the dichotomies. Rocha and Goldenstein [START_REF] Rocha | Multiclass from binary: Expanding one-versus-all, one-versus-one and ecoc-based approaches[END_REF] reduce the number of required learners and add new ones that complement the existing set.

Group SVM

Learning all possible label combinations is an insurmountable task and practically the label sets that actually exists are very sparse [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF][START_REF] Tsoumakas | Random k-labelsets for multilabel classification[END_REF]. This sparseness thus helps greatly to reduce the classifiers to be learned. Methods to find label sets to be learned can be divided into data or label dependent and data independent approaches [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF]. Data independent approaches randomly select label sets like RAKEL [START_REF] Tsoumakas | Random k-labelsets for multilabel classification[END_REF] while we propose a data dependent approach that exploits visual correlation between labels or concepts to find good label sets.

Our goal is to learn from multiple labels and minimize the number of multi-label classifiers [START_REF] Niaz | Leveraging from group classification for video concept detection[END_REF]. We try to find intelligently the sets of labels to be trained together for learning, building multi-label classifiers or group classifiers as we call them. We propose to use the visual similarity between concepts to partition the label space into multiple overlapping groups and then learn classifiers for those groups. Thus we achieve multi-label classification through group based classification. The groups learned are effectively binary classifiers that combine annotations from different concepts and learn a 1-vs-all classifier on the new set of annotations. Individual concept labels are then inferred from the multi-label group predictions.

The labels predicted are always the same and are defined at the time of making groups. The number of concepts belonging to one group is not similar.

Difference From Attributes and Hashing

Group based classification [START_REF] Niaz | Leveraging from group classification for video concept detection[END_REF] is different from attributes in that a concept is defined by a set of multiple attributes while a group contains multiple concepts. Looking at it in another way an attribute also contains many concepts, or more specifically it is present in many concepts, but the number of attributes to be learned is far greater than the expected number of groups to be learned. Furthermore each concept is identified by a unique combination of the groups. We are trying to improve video concept detection performance with using a small number of classifiers to be learned. Definition of attributes is very specific to the type of dataset and the task at hand. The number of object specific attributes increases rapidly with the addition of more diverse content. Also the attributes are usually named in advance but the groups of concepts or labels are not fixed or pre-defined.

In baseline with fusing information from as little as 10 group classifiers for a total of 50 concepts on the TRECVID 2010 dataset.

Group Based Classification

Similarity of concepts can be judged in many different ways, including web semantics information, ontology rules or relationships between concepts provided with some video databases like for example TRECVID 2010 [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF]. Example of such rules are Anchorperson is Adult and News Studio contains Anchorperson. To quantitatively express the similarity of concepts, intersection of common annotations can be used to find a similarity index between two concepts. Also feature vectors belonging to shots containing concepts can be used to find distance between two concepts. The criterion for clever grouping of concepts we do uses feature vectors for finding similarity between concepts to group them together.

After the concepts are grouped together into different groups, each concept is assigned to a number of different groups. The idea is that each concept is uniquely identified by a combination of outputs of certain groups. Thus if the concepts Car and Road appear in the same group, one of them should belong to at least one of the other groups to differentiate it from the other. In other words each concept is represented by a unique bit string with length equal to the number of total groups. Each bit of the bit string represents a group and the value of the bit is 1 if the concept belongs to the specified group.

Clever Grouping

We use average feature vector for each concept (label) to find the alikeness between concepts.

Average feature vectors v c for each concept l c ∈ L are obtained by averaging all the feature vectors for images containing the concept from our training set. The total number of labels is |L| and so is the number of average vectors. The feature vectors are Bag of Words histograms [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] as described later in the experiments section. Let (x i , y i ) be a training example where y i is a vector of labels in the multi-label setting. Average feature vector for a concept is given by:

v c = c∈y i x i |c ∈ y i | (4.1)
The clever grouping criterion we use is based on visual similarity between concepts i.e. we use the similarity or the inverse of the distance between the average features as the closeness. First we consider the scenario where where the number of groups is less than the number of concepts D < |L|.

Grouping for D < |L|

Groups are generated in a reverse mechanism. That is to say that concepts are assigned to the groups one by one. So for example we start with concept 1, assign it to the groups and carry on with the next concept. To start the C average vectors are first clustered into D centers using k-means clustering with random initial centers. After clustering we generate a list for each average feature vector containing top n closest centers. We follow with an allocation like soft assignment [START_REF] Van Gemert | Visual word ambiguity[END_REF].

For each concept the list is sorted with the closest center at the first rank, second closest ranking second and so on. Each concept is always assigned to the closest group. Next the concept is assigned randomly to the next closest center with decreasing probability. The decrease in probability is proportional to the increase in the distance to the next closest center. When each concept has been assigned, D groups are generated corresponding to the D cluster centers. Clustering is done so that the outliers (concepts whose average features are far from others) are considered for grouping as well when D < |L|.

Clustering the concept vectors

Assignment with decreasing probability Groups Group 1

Group 2 Group 3

Binary codes and conflict resolution

The concepts are assigned sequentially that is the bit strings are generated sequentially.

Each concept can be considered as represented by a binary code with each bit representing the corresponding group. A 1 indicates that the concept is present in the group and 0 is put in case the concept does not make part of the group. In case of a conflict between the assignment of two concepts, i.e. when two bit string are exactly the same, the two concerned bit strings are regenerated until the conflict is resolved. Since during assignment there is some randomness while keeping the visual similarity a priority we expect to resolve the conflict with a few retries. In this way each concept is uniquely identified by a different combination of groups. The case where D ≥ C there is rarely a conflict but if there is, the grouping is We then determine the labels of the members of the groups. All the examples belonging to those labels become part of that group. More specifically two examples that are visually very close do not necessarily end up in the same group unless their respective average feature vectors are close. Unlike attributes these groups are complex entities or complex attributes as they combine annotations from many objects (concepts).

Random Grouping

We compare clever grouping of concepts with random grouping. In random grouping no similarity criterion is used rather concepts are grouped randomly into groups. For each group n is randomly drawn and then n concepts are randomly selected from which bit strings are acquired for each concept. The process is repeated if there is a conflict between the bit strings of any two concepts. This process remains similar whether the number of groups is smaller or greater than the number of concepts.

Acquiring Concept Score

For both grouping criteria an example is considered positive if any of the participating labels

s g (f |c) = c∈g s(f |g)
giving the score of the frame f for concept c. We do not subtract the scores of negative groups i.e. the groups which do not contain c as we found experimentally that using this information worsens the results.

Experiments and Results

We present here experiments carried out on the TRECVID 2010 datasets.

Experimental Setup

Dataset and Features: We have used the TRECVID 2010 IACC [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF] We use 128 dimensional SIFT features [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] to describe local patches extracted using a Dense grid of points on the video keyframes [START_REF] Russell | Labelme: A database and web-based tool for image annotation[END_REF]. The points on the grid are distanced 8-pixels apart. All the SIFT descriptors from the training set are then used to build a 500 word visual dictionary using k-means. For classification we have used linear SVM to learn from a suitable feature map (homogeneous kernel map) built by the histogram intersection kernel [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF][START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF].

We have used Average Precision (AP) to measure concept detection performance as used in TRECVID semantic indexing benchmark [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF]. For the overall performance we use Mean Average Precision (MAP) of 50 concepts.

RAKEL: For RAKEL we fix the value of k = 3 which is also known to give the best results [START_REF] Tsoumakas | Random k-labelsets for multilabel classification[END_REF]. We adapt the RAKEL algorithm for Average Precision in that we generate score for each shot so that a sorted list can be generated for each concept. Each LP classifier is a multi-label classifier that gives classification scores for the k concepts. We call a k -labelset a group with k concepts and each group predicts scores for each of the k concepts.

In the end to obtain the score for each concept, scores from all the LP (group) classifiers, of which that concept is a part of, are added and normalized.

Late Fusion:

We have also used late fusion to combine the baseline results with the 3 group based approaches. Weighted linear fusion is used in order to obtain a single output score for each concept s(f |c) that is used to rank the video frame f for the concept c:

s(f |c) = w s s s (f |c) + w g s g (f |c)
where s s (f |c) and s g (f |c) are the concept scores acquired from the single label classification (baseline) and the group based approach respectively. The scores are rescaled according to one another using min-max normalization. The weights w s and w g are optimized over the development set.

As all the three approaches include some randomness we have repeated each experiment 5 times. We show the mean and standard deviation for the scores.

Results

The Semantic indexing results on the TRECVID 2010 test dataset for various approaches for the list of 50 concepts are presented in figure 4.9, containing: i) OVA: One vs All or single label classification which is also the baseline, ii) Random grouping, iii)Random-OVA: fusion of baseline with random grouping, iv) clever grouping, v) Clever-OVA fusion of baseline with clever grouping, vi) RAKEL, and vii) RAKEL-OVA: fusion of baseline with RAKEL. The circle in the center shows results for the One versus all classification which is our baseline.

For baseline each concept is treated as a separate label and a 1-vs-All SVM is trained for that label using all of its positive examples.

Performance of various grouping approaches increases almost linearly with the increase in the number of groups with random grouping of concepts performing better than RAKEL for almost every group size. Intelligent grouping significantly outperforms the other two techniques and approaches single label classification performance for training around 80 intelligently formed groups. Further increasing the number of groups increases marginally the performance over the baseline.

Figure 4.9 also presents the results of fusing various group based techniques with the baseline. Fusion with RAKEL improves concept detection performance over baseline and increases linearly with the increase in the number of groups. The best performance is acquired using 100 groups with 10% overall increase in the indexing performance over the baseline.

Clever grouping when fused with single label classification provided best improvement for a very few number of groups trained. This is observable in the upper left part of the figure 4.9

as fusing concept scores from only 10 clever groups with the baseline improves MAP score from 0.0527 to 0.0592 with 12% increase in performance. Using 20 intelligent groups the improvement is 15%. The fusion performance is good with clever grouping till the number of groups is 40 and after that the MAP decreases linearly, when the number of groups equals or is greater than the number of concepts. With random grouping the trend is somewhat similar to RAKEL as the fusion performance increases with the increase in the number of groups. Although the MAP here is better than that of RAKEL for every grouping. Fusion results with random grouping lingers close to the fusion results with intelligent grouping.

The performance is slightly inferior to intelligent grouping for up to 50 groups and then outperforms intelligent grouping as the number of groups increases further. Best MAP score is 0.0612 which is a 16% increase over the baseline observed with 100 random groups used (upper right corner). weights increase with the number of groups for the three approaches as more groups means better classification at concept level except when there is over-fitting or when the group based approach performs worse than the baseline for a certain concept. For clever grouping the average weight quickly reaches the level where both the group based and the single label approaches contribute almost equally to the final score. Thus when the number of groups equals 50 both approaches contribute exactly equally for the final performance and as the number of groups increases more weight is assigned to clever grouping on average. In figure 4.9 we see that the clever grouping approaches single label classification with the increase in the number of groups. Thus adding more and more groups with concepts grouped on visual similarity will always converge to single label concept wise classification and fusing those two together will only results in marginal improvement.

Analysis of Fusion

Average Fusion Weight

Number of Groups

Note that this is not the case for random grouping technique as the maximum weight assigned on average is around 46%. In other words random grouping contributes around 46% to the fusion even with 100 groups. Thus as the performance of random grouping is always inferior to baseline in figure 4.9, fusing it with baseline always brings in complimentary information and improves performance with the increase in number of groups. However clever grouping does bring more useful information in fusion than random grouping if number of groups is kept inferior to the number of concepts. Thus we are able to improve 12% and 15% over the baseline with only 10 and 20 new classifiers trained respectively in addition to 50 single-label classifiers.

One explanation for the not so good performance of RAKEL is that the label set in the TRECVID dataset we used is very sparse i.e. only a few combinations of labels are possible.

In the RAKEL mechanism each group has k = 3 and thus up to 8 single label classifiers are trained for each group. For good classification results the number of positive examples for each combination of labels should be adequate [START_REF] Tsoumakas | Random k-labelsets for multilabel classification[END_REF]. We have found that in the Label

Label Clustering and Repetitive Codes

Since classes share many examples with other classes it is reasonable to try to identify meaningful combinations among classes. These combinations are not mutually exclusive but are unique as each set encodes a specific partitioning of the labels. Looking at it differently each set adds or glorifies a certain aspect of the concept(s) within the combination. This is true for the group based classification presented in the previous section. Now we try to look at the similarity as well as the differences between the concepts. The concepts are divided into partitions rather than groups. In the previous section a concept was part of different groups and the combination was unique for each concept. So the difference between two close concepts was that they differed in at least one group. Here we rely on the information that a concept is like some concepts and not like or different from some others.

This kind of grouping and division is shown in figure 4.3-c, at the start of this chapter, where

positively labeled examples from certain concepts are placed on either side of the classifier.

We identify opposing partitions from the set of labels that satisfy some similarity criterion.

Labeled examples are then gathered for both the partitions and are trained with a binary classifier. Following questions are raised for a successful construction of such a system: (i)

How the labels should be divided in partitions, (ii) what should be the size of each partition, (iii) how many different divisions of the labels are required and (iv) how each label can be differentiated. We briefly answer these questions here before responding to them in detail with our proposed approach in the following subsections.

It is important to first recap about Error Correcting Output Codes (ECOC) that have been successfully employed to solve multiclass classification problems [START_REF] Dietterich | Solving multiclass learning problems via errorcorrecting output codes[END_REF] and are also making their way into multi-label classification [START_REF] Armano | Error-correcting output codes for multi-label text categorization[END_REF][START_REF] Escalera | Separability of ternary codes for sparse designs of error-correcting output codes[END_REF][START_REF] Kajdanowicz | Multi-label classification using error correcting output codes[END_REF]. The mechanism usually contains numerous suboptimal classifiers and a single label is repeated in many of those classifiers. The repetition tends to minimize the effect of the errors made by single classifiers by combining the predictions from all the classifiers for that label. Our partitioning and training proposal fits the ECOC mechanism as each division of partitions is a dichotomy where some labels lie on either side. Each row of the ECOC M-matrix represents a codeword for a label which we should enforce to be unique. A classifier is trained for each dichotomy and predictions from each dichotomy are combined to decode the final result.

While there have been approaches to randomly assign binary codes to classes and generate the ECOC M -matrix [START_REF] Allwein | Reducing multiclass to binary: A unifying approach for margin classifiers[END_REF] we use a data dependent approach exploiting the resemblance between concepts to generate the repetitive codes. Mohamadi et al. [START_REF] Mirza-Mohammadi | Ranking error-correcting output codes for class retrieval[END_REF] use semantic distance and feature distance between labels in unison for the ECOC decoding process to get ranked lists for each concept. We also use a combined similarity measure but contrarily we used is for the encoding. The similarity criterion is based on the distance between visual features of the concepts and the difference between the annotations. This similarity is used in a clustering framework to find partitions of the labels. Concepts that are visually or semantically close should be part of the same partition or should be on the same side of the dichotomy. Thus if we are to assign from the set of concepts {Car, Road, Beach} to two partitions, it is reasonable to assign Car and Road to the same partition.

We use parameters to change the similarity between concepts as well. As we generate more and more dichotomies it is important to differentiate between concepts that are too similar.

Carrying on with the previous example if Car and Road always lie in the similar partition they will not be distinguishable. So the similarity between Car and Road is diminished after they have been assigned to the similar partition. If they are assigned again to the same side of the dichotomy the similarity is further diminished. This is repeated until each concept has a unique codeword.

Difference From Group Classification, Attributes and Hashing

Proposal

We use the similarity between concepts to explore the hidden structure (relationship) between them. This exploits complementary information among concepts and improves classification.

The repetition is expected to further improve performance with error correction. In the training phase we build the codes for each class and then train classifiers for the dichotomies.

It is worth mentioning here that in our approach one dichotomizer does not divide all of the labels. This means that we are dealing with the ternary ECOC where the codeword for each class contains bits that can take values in {-1, 0, +1}. The bit value of 0 gives the flexibility to classical ECOC to cater multi-label data by not considering some of the labels in the dichotomies. So a dichotomizer for one bit of the code will only be trained to distinguish between examples of the participating labels whose corresponding bits are -1 and +1. This suits us perfectly as we want our partitions to be compact with a few similar concepts distinguished from the other dissimilar partition with also with a few concepts. The length of our class codeword is N bits and so we build N dichotomizers, or train N binary classifiers. For a test sample we acquire predictions from all the classifiers and generate score for each concept using our specific decoding.

Distance or similarity between classes can be calculated by using a number of relationships that exist between classes. Many classes share common examples in video datasets and this information can be used to find similarity e.g. the overlap or intersection of examples.

Linguistic knowledge bases have been used to find the information shared among classes [START_REF] Rohrbach | What helps where -and why? semantic relatedness for knowledge transfer[END_REF].

Ontological rules are usually given with datasets that dictate relationships between classes.

Furthermore these relationship can be hierarchical or direct. WordNet [START_REF] Miller | Wordnet: A lexical database for english[END_REF] has also been used to find the semantic distance between classes [START_REF] Fergus | Semantic label sharing for learning with many categories[END_REF]. We use the distance between features in unison with a semantic distance that we calculate directly from concept annotations. This distance (or similarity) is used to build a similarity vector for each concept which contains pairwise similarity values with all the other concepts. These similarity vectors are used to automatically find the codewords for each class. In addition we weight the similarity between every pair of concepts and these weights change dynamically during the construction of the codewords. Finally for each bit of the codeword we learn a binary classifier that separates examples for which the bit value is +1 from those for which the value is -1. Details of the system are presented in the next subsections followed by detailed experimentation.

Code Generation by Clustering

We calculate distance between the visual features of the labels using the training set as done in the group classification technique. For that we first calculate the average feature vector v c for each label l c as done in equation 4.1. Then d v (i, j) is the Euclidean distance between l i and l j which is referred to here as the visual distance since it finds the distance between the visual features of two labels.

This distance is combined with the semantic distance which is calculated using the intersection of positive annotations for the examples present in the training dataset. For each label c we have a set of positive annotations A c and since we are dealing with multi-label data the semantic similarity between two labels is given by:

sim s (i, j) = |A i ∩ A j | |A i ∪ A j | (4.2)
which is the ratio of common annotations between labels i and j. Here common annotations mean all the examples which are positive for the two labels in question.

Since we use the distance between concepts in the ECOC generation process we negate the semantic similarity to find the semantic dissimilarity as: d s (i, j) = -sim s (i, j). The total dissimilarity or distance between labels is the weighted sum of the two measures

d(i, j) = λ * d v (i, j) + (1 -λ) * d s (i, j) (4.3)
The factor λ weights the contribution from the visual and semantic similarities.

We use this distance between two labels directly to find the partitions of labels. The number of labels that make part of a partition depends on a measure of distortion within the partition. The weight we use to alter the similarity between two labels is called repulsion between the two labels. This repulsion is changed dynamically during the ECOC generation process to avoid the same labels going to the same partitions over and over again. As the name of the variable suggests repulsion is increased between labels that were in the same partition in the previous iteration. Similarly we reduce the repulsion between concepts that never fall in to the same partition. The factor repulsion ij that weights the distance between lablels l i and l j is multiplied by the distance from equation 4.3 to find the final distance:

dis(i, j) = d(i, j)repulsion ij (4.4)
The algorithm to build the ECOC is presented in the figure 4.11. The set of labels is repeatedly partitioned to generate dichotomies until all the labels have a unique ternary codeword b i . Repulsion is initialized as a value which is the same between all labels. To generate one set of opposing partitions or a dichotomy seed labels are selected that are the farthest from each other. The first seed is the one who has minimum cumulative repulsion with all other labels. This ensures the selection of the label that has never (or hardly ever) been selected before. The second seed is the farthest label according to the distance in equation 4.4. Two partitions L 1 and L 2 are maintained and closest labels are assigned at each iteration until the partitions are distorted. The closest label to a partition is found using the distance of label to the partition as:

dis(i, L k ) = j∈L k dis(i, j) |L k | (4.5)
where dis(i, j) comes from equation 4.4.

After the assignments the labels that distorted the partitions are removed. The labels in L 1 are assigned the bit value of +1 and those in L 2 get the value for the k'th bit -1. All the other labels are assigned 0 for their respective bit value. Repulsions are also updated after the assignments: repulsions between the labels of the same partition are increased by α -β and repulsions between other labels are decreased by β. β is usually smaller than α and could be 0 as the convergence can be solely controlled by α. We have experimentally fixed the values of α and β to 0.3 and 0.05 respectively. The partitioning stops when each label is assigned uniquely to partitions.

Figure 4.12 shows the procedure to find the distortion within a partition. Each partition is considered a cluster within the space represented by the distance between labels. As a partition grows more concepts are added that are far from the center of that cluster.

The distortion is controlled by the parameter Θ for which different values are tried in the Select q s.t. q : argmax q dis(q, p) 10:

L 1 ← p 11: L 2 ← q 12:
L ← L\p, q ⊲ Remove seeds from the full label set if DIST ORT ION (L 1 ) = 0 then 15:

L 1 ← L 1 ∪ argmin i dis(i, L 1 ), i ∈ L 16:
L ← L\i if DIST ORT ION (L 2 ) = 0 then 19:

L 2 ← L 2 ∪ argmin j dis(j, L 2 ), j ∈ L 20: L ← L\i 21:
end if

22:

until DIST ORT ION (L 1 ) = 1 and DIST ORT ION (L 2 ) = 1

23:

L 1 ← L 1 \i
⊲ Remove the labels that distorted the partitions 24:

L 2 ← L 2 \j 25:
M (t, i) ← 0, i ∈ L ⊲ Assign binary codes 26:

M (t, i) ← +1, i ∈ L 1 27: M (t, i) ← -1, i ∈ L 2 28:
repulsion ij ← repulsion ijβ, i, j ∈ L ⊲ Update repulsion values 29: dmin ← min dis(i, j) i, j ∈ L, i = j 5:

repulsion ij ← repulsion ij + α, i, j ∈ L 1 30: repulsion ij ← repulsion ij + α, i, j ∈ L 2 31: t ← t + 1 32: until ∃M (i, ) = M (j, ), i, j ∈ L, i = j
dmax ← max dis(i, j) i, j ∈ L, i = j 6:

if dmax > θdmin then

S + = {x i : y i ∈ L 1 } S -= {x i : y i ∈ L 2 } (4.6)
A binary classifier is then trained using S + and S -for each of the N dichotomies.

Decoding for Ranked Predictions

Using algorithm in figure 4.11 we have generated unique codewords of size N for each of the labels making up the M matrix, M ∈ {-1, 0, 1} |L|,N . Since we need to generate ranked lists we use the scores directly instead of classifier decisions for decoding purposes. Every classifier for a dichotomy n ∈ N gives us a score s n (+1|f ) for the test frame f which is first normalized. The score for each label is calculated as [START_REF] Armano | Error-correcting output codes for multi-label text categorization[END_REF][START_REF] Allwein | Reducing multiclass to binary: A unifying approach for margin classifiers[END_REF]

s(l|f ) = N n=1 s n (+1|f )M (l, n) (4.7)
so if a label lies in the second partition and is positive for the test example, the negative score of the classifier is multiplied by the -1 value of M (l, n) to make it a positive contribution for that example on that label.

We have also tried to weight the contribution of labels from the classifiers depending on the size of the partition. We believe that the number of labels in a partition affects the performance of a single label due to annotation noise and if the classifier is not strong enough it will not cater the diversity within a partition that comprises of a variety of labels. We thus give high weights to partitions with fewer labels while decoding. This is achieved by simply dividing the score in equation 4.7 by the size of the respective partition:

s(l|f ) = N n=1 s n (+1|f )M (l, n) |M (, n) = M (l, n)| (4.

Results and Experiments

Now we present results for the proposed ECOC generation method for Multi-label ranked predictions and see the effects of the parameters in various ensembles and the weighting strategy proposed in equation 4.8. We will also look at some of the ECOCs generated to see which criterion generates more intuitive partitions.

Datasets and Setup

We have performed experiments on the TRECVID 2010 (TV2010) and TRECVID 2013 (TV2013) [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF][START_REF] Over | Trecvid 2013 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF] dataset.

For the TV2010 containing 400 hours of 11,644 internet videos with 119,685 keyframes for development and 146,788 test keyframes we generate ranked lists for 50 concepts from the TRECVID 2011 Light Semantic Indexing task [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF]. The visual features used are 128 dimensional SIFT features [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] which are densely extracted [START_REF] Russell | Labelme: A database and web-based tool for image annotation[END_REF] and are used to build a 500 word visual dictionary using k-means. For classification we have used linear SVM to learn from a suitable feature map (homogeneous kernel map) built by the histogram intersection kernel [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF][START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF].

For the TV2013 dataset, which engulfs the TRECVID 2010, 2011 and 2012 datasets, consisting of 800 and 600 hours of videos for training and test respectively we extract dense SIFT features and generate a dictionary of 1000 visual words. Considering the huge amount of data the classifier used is a linear SVM trained on the homogeneous kernel map built on the input features where Pegasos training [START_REF] Shalev-Shwartz | Pegasos: Primal estimated sub-gradient solver for svm[END_REF] is used to minimize the training time. The development is done using the list of 60 concepts while 38 concepts were evaluated by NIST in the year 2013, for which results are presented.

Results

The video concept detection performance is judged by calculating Average Precision (AP) on the first 2000 shots returned for each label (concept) on the test datasets.

ECOC Generations

Since we are interested in looking at the performance of Ensembles of ECOC we do not discuss how each ECOC generation performs. We have generated many different ECOC matrices for different parameters as discussed in the last section. Adult

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 Airplane_Flying -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 Animal 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Asian_People 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Bicycling 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Boat_Ship 0 0 -1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Building 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 Bus 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 Car 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 Cheering 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 0 0 Cityscape -1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Classroom 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 Screens 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 0 Computers 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1 -1 0 -1 0 0 0 0 0 0 0 0 0 0 Dancing 0 0 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Dark_skinned 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Demonstration 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 Doorway 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 Explosion_Fire 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 1 0 0 0 Female_Closeup 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Female_Person 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Flowers 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 Ground_Vehicles 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 Hand 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 Hovering_Copter 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Indoor 0 0 0 0 0 0 0 1 -1 0 0 -1 0 0 -1 0 -1 0 -1 0 0 0 0 0 1 0 0 Indoor_Sports 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 Infants 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Instr_Musician 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 Landscape -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 Male_Person 1 0 0 0 0 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 Military_Base 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 Mountain 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 News_Studio 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 Nighttime 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 Old_People 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Plant 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 Road 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 Running 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 -1 -1 1 0 0 0 0 0 0 0 Scene_Text 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 0 Singing 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 -1 0 Sitting_Down 0 0 0 0 -1 -1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 Stadium 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 Swimming 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 Telephones 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 1 0 Throwing 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 Vehicle -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Walking 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 -1 1 0 0 0 0 0 0 Running 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 Waterscape 0 1 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0
1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 -1 1 -1 1 0 0 -1 0 0 0 0
Airplane_Flying -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 Animal

0 1 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 Asian_People 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 1 -1 0 Bicycling 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Boat_Ship 0 0 -1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Building 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -1 0 -1 1 -1 -1 0 -1 Bus 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Car 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 Cheering 0 0 0 0 1 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Cityscape 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 0 Classroom 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Screens 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 -1 1 0 0 0 0 0 Computers 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 1 1 0 0 0 -1 0 0 0 0 0 0 0 Dancing 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 1 1 0 0 0 0 0 0 0 Dark_skinned 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
Demonstration 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Doorway

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 Explosion_Fire 0 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0
Female_Closeup -1 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Female_Person 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 1 -1 0 0 Flowers

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Ground_Vehicles 0 0 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 Hand

0 0 0 0 0 0 0 0 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0
Hovering_Copter 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 Indoor We can see that the partitions generated when the criterion was semantic distance λ = 0, generates groups that are more coherent with intuition. As discussed above with bigger Θ more labels fall into the partitions and thus the number of dichotomies necessary to distinguish the labels are generally less. The performance of the best tree for TRECVID 2010 is a MAP of 2.33% and for TRECVID 2013 is 1.94%.

1 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 -1 -1 0 1 1 -1 1 0 0 0 0 0 0 0 Indoor_Sports 0 0 0 0 0 0 0 0 0 1 1 -1 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Infants 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Instr_Musician 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 -1 1 0 0 0 0 0 0 0 Landscape 0 0 -1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Male_Person 1 1 0 0 0 0 1 0 0 0 0 1 0 0 -1 0 0 1 0 1 0 0 -1 -1 1 0 0 0 0 -
Road 0 0 -1 1 -1 0 0 0 0 1 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Running 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 1 1 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 Scene_Text 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 Singing 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 1 1 0 0 0 1 0 0 0 Sitting_Down 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 -1 1 1 0 -1 -1 0 0 0 0 0 0 0 Stadium 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 1 -1 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 Swimming 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 Telephones 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 Throwing 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 Vehicle 0 0 -1 1 0 0 0 -1 0 1 1 0 0 0 0 0 -1 -1 0 1 -1 0 0 0 0 0 1 0 0 0 0 1 0 Walking 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 -1 -1 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 1 Running 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 Waterscape -1 0 -1 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Label Trees and Repetitive Codes

In this section we continue to work on the 3rd paradigm in the figure 4.3 where we partition concepts into groups using the similarity and the difference between labels simultaneously.

The goal is again to overcome sparse annotations problem by increasing the number of positive examples per concept with the number of classifiers per concept, though sub-optimal, augmented too.

We use identical similarity criterion between labels as in the previous section but the division in partitions is done differently. We divide the labels into binary partitions starting from the whole set of labels until each label is differentiated from the others. This induces a binary tree on the labels where each node splits the labels into two subsets and the leaves contain single labels [START_REF] Niaz | Improving video concept detection through label space partitioning[END_REF]. Based on the similarity criterion the labels that are similar are kept together till deep into the tree, until a time comes eventually where they are placed in the opposite sides of the partition. This way each label embodies a unique combination of partitions. Wang and Forsyth [START_REF] Wang | Large multi-class image categorization with ensembles of label trees[END_REF] also build trees by partitioning the label space, as they call it, using a similarity and error criterion on a validation set. Validation set is also employed by [START_REF] Pujol | An incremental node embedding technique for error correcting output codes[END_REF] to add nodes (dichotomies) to an already generated tree that partitioned the set of labels. We do not use any validation data rather rely directly on out similarity criterion to generate ensembles of trees. For combination we use weighted fusion to generate the final ranked list.

Each node of the binary tree divides the receiving set of labels into two disjoint partitions.

We divide the concepts or labels into partitions iteratively, until all the labels are divided.

Then we merge all the annotations on either side of the partition and train a single label binary classifier for that partition. In the end we trace back classification score for each label based on appropriate combinations of the scores of the partitions to which that label belongs. The label partitioning is viewed in terms of ECOC framework where a set of simple sub-optimal classifiers can achieve the performance of a good complex one. Then an effective weighting strategy is adopted while decoding to emphasize more on important partitions or dichotomies, generating list of scores for each label. Finally we build groups or ensembles of trees by varying the similarity criterion and fuse the information from trees to get the final classification score. We have performed experiments on the TRECVID 2010 the TRECVID 2013 dataset and we show that the proposed approach is complementary to single label classification by showing significant improvement on the TRECVID Semantic INdexing (SIN) task. We also shed some light on the importance of the number of labels to start the partitioning with and argue that more labels induce a better partitioning and thus improved classification results.

This approach is again different from group based classification, hashing and attribute learning for the similar reasons listed in the previous section, however it does differ from the label clustering based partitioning method. The main difference is that here the number of partitionings is limited. In label clustering many dichotomies were generated until each label is uniquely assigned to the partitions, but here the number of partitions is always |L| -1,

where |L| is total the number of labels as a binary tree is generated. Also the former could include any two labels in a partition based on the current similarity but for the later only the labels in the parent set are partitioned based on the depth of the tree.

Moreover there are partitions that only consist of only one label. This happens at each leaf of the tree which contains only one label in one partition against the other partition that may contain 1 or more labels. Thus each label enjoys being alone in a partition at the leaves of the tree. The similarity criteria and the generation of final scores for each label is done similar to the label clustering method but with a slightly different weighting strategy.

Another difference is that the distance is no longer weighted (with repulsion) dynamically.

Proposed Approach

Similarity or distance between labels or concepts can be calculated through different means like the distance between features or ontological graph distance. We build a tree in the label space, which is the space represented by the distances between the labels. We again use the visual distance and the semantic dissimilarity based on the common annotations ratio among labels to find this distance between labels. The two measures are used simultaneously to split nodes and construct the label tree. The root node splits the whole label set into two partitions. Each node then splits the receiving partition into two subsets until each leaf contains only one label. So in case of partitioning tree we ensure that each concept is eventually different from the most similar concept.

The partitioning criterion should be designed in a way to increase the learnability of the tree while maximizing the number of possible examples that can be assigned to either side of a tree node.

Learnability is the ability of the tree to learn from a particular partitioning of the labels and generalize on a test set [START_REF] Wang | Large multi-class image categorization with ensembles of label trees[END_REF][START_REF] Bengio | Label embedding trees for large multi-class tasks[END_REF]. So a tree with poor or counter intuitive partitioning will have low learnability and thus will perform poor on the test set. As an example a tree partitioning the labels {Car, Road, Anchorperson, News Studio} into {Car, Road }, {Anchorperson, News Studio} is more learnable than a tree splitting the initial set into {Car, News Studio}, {Anchorperson, Road }. Since dividing the label space at each node directly influences the learnability of the label tree [START_REF] Wang | Large multi-class image categorization with ensembles of label trees[END_REF] we use similarity measures that follow intuition by keeping two close labels in the same partitions till deep into the tree.

Tree Construction

Similar to the label clustering in the previous section we calculate the distance between visual feature vectors and the positive annotations and combine them to find the total dissimilarity between 2 labels at shown in the equation 4.3.

L l ← l 1 5: L r ← l 2 6: else 7: {i, j} ← argmax i,j d(i, j), i, j ∈ L ⊲ Select seeds 8: L l ← i L ← L\L l 9:
L r ← j L ← L\L r 10:

repeat 11: L l ← L l ∪ argmin d(i, L l ), i ∈ L 12: L r ← L r ∪ argmin d(i, L r ), i ∈ L 13:
L ← L\L l 14:

L ← L\L r 15: The parameter λ controls the contribution of the visual distance and the semantic dissimilarity. Since there is no repulsion to weight the distance between the labels we use d(i, j) directly to find the similarity between l i and l j . The distance between a partition L k and a single label l i is the average distance to all the labels actually present in the partition, as:

until L = ∅ 16: end if 17: M (t, i) ← +1, i ∈ L l ⊲ Assign binary codes 18: M (t, i) ← -1, i ∈ L r
d(i, L k ) = j∈L k d(i, j) |L k | (4.9)
where d(i, j) is taken from the equation 4.3.

Figure 4.17 shows the algorithm for splitting one node of the tree which receive a certain set of labels as input. The algorithm simply selects the two farthest labels as seeds and then builds two clusters (left and right) around those seeds. At each iteration the label closest to either cluster is assigned to that cluster until no more label is left to be assigned. Note that the new dissimilarity is calculated between the label and the cluster center but not the initial seed. Two partitions are generated each of which is further passed through the same procedure to complete the tree. Since its a binary tree we call the two partitions left and right. positive examples of concepts on either side. We borrow notation from [START_REF] Wang | Large multi-class image categorization with ensembles of label trees[END_REF] to build the two sets of examples as follows:

S + = {x i : y i ∈ L l } S -= {x i : y i ∈ L r } (4.10)
S + and S -are used to train the binary SVM classifiers. Since we are dealing with mutlilabel data as opposed to multi-class data, in case of contention the example is assigned to the partition containing the minority class. That is to say if an example belongs to more than one labels, and the two labels are divided by a node, the example will belong to the node with fewer total examples. This makes sense as in case of a multi-label example belonging to a general class, Vehicle and a specific class, Car the example should be for Car since it differentiates Car from the other Vehicles. For the other case of simple majority vs. minority it is better not to reduce the already limited number of examples for the minority class. This kind of contention normally occurs near the leaves of the tree since labels close to each other are kept in the same partitions until it is necessary to separate them to tell them apart.

Ternary Codes and Error Correction

The tree construction bears close resemblance to the multi-class classification approach Error Correcting Output Codes (ECOC) [START_REF] Dietterich | Solving multiclass learning problems via errorcorrecting output codes[END_REF][START_REF] Armano | Error-correcting output codes for multi-label text categorization[END_REF][START_REF] Allwein | Reducing multiclass to binary: A unifying approach for margin classifiers[END_REF][START_REF] Kajdanowicz | Multi-label classification using error correcting output codes[END_REF]. To look at the benefits of the repetitive codes for classification we first explain the resemblance. ECOC builds a set of suboptimal binary classifiers for each label where final prediction is obtained by simple pooling of the participating classifiers for that label. Each classifier epitomizes a dichotomy which partitions the label space just like a node of the tree built in the previous subsection.

The technique presented here is essentially ternary ECOC where a label can be either part of a dichotomy (-1,+1) or not (0). Note that the tree is binary as each node splits the labels it receives from its parent node into two partitions; left and right, which are +1 and -1 for the ECOC. All the other labels that are not received (and hence not split) by that node are 0 in the ECOC framework. The nodes or dichotomizers are built incrementally optimizing criterion in equation 4.3 to divide most profiting class labels. This code is also called the codeword for that category and the codewords for all the categories make up the rows of the ECOC M matrix, where M ∈ {-1, 0, 1} |L|,N . |L| is the number of labels and N is the length of each codeword or number of classifiers. Here this also represents the number of nodes of the label tree. Each class label encodes a unique code and the (hamming) distance between two classes that are close is low. Figure 4.18 depicts a multi-label tree and the corresponding M matrix [START_REF] Pujol | An incremental node embedding technique for error correcting output codes[END_REF].

As we are generating ranked lists for test frames again, every classifier n ∈ N gives us a score s n (+1|f ) for the test frame f . The score for each label is calculated as done in the equation 4.7. Since the dichotomies turn from general to more discriminative as the depth of the tree increases we have found that more weight assigned to the specific dichotomies

1 2 3 {l 1, l 2, l 3, l 4 } {l 1, l 4 } {l 2, l 3 } l 1 l 4 l 2 l 3 n 1 n 2 n 3 l 1 1 1 0 l 2 -1 0 1 l 3 -1 0 -1 l 4
1 -1 0 Each leaf of the label tree is a single label so s(l|f ) can also be regarded as the score at leaf corresponding to label l.

The first and foremost advantage of any technique augmenting labels is the increase in the number of examples per category which affects significantly performance of the categories with fewer positive examples. In ECOC this advantage is not limited to just the increase in training resources per category but also increases the error correcting capabilities of the system due to repeated classifiers [START_REF] Armano | Error-correcting output codes for multi-label text categorization[END_REF][START_REF] Ferng | Multi-label classification with error-correcting codes[END_REF][START_REF] Pujol | An incremental node embedding technique for error correcting output codes[END_REF]. Even if some dichotomies partition badly the label space others are expected to correct the mistakes due to repetition and provide reliable final results. This advantage is further strengthened when we use ensemble of trees for a single problem as described in the next subsection.

Ensemble of Trees, Forest

The label partitioning tree uses pre-computed information and is quick to build. We take the liberty to build multiple trees by varying our similarity criterion. This is done by changing the value of λ in equation 4.3. The trees can be combined by averaging the scores of the corresponding leaves, choosing the highest score [START_REF] Wang | Large multi-class image categorization with ensembles of label trees[END_REF] or finding a weighted combination of the corresponding outputs from the trees. For label (leaf) l the weighted combination from two trees t 1 and t 2 is learned as follows on the validation data:

s(l|f ) = w t 1 l * s t 1 (l|f ) + w t 2 l * s t 2 (l|f )
We have built ensembles of upto 6 trees using linear weighted fusion of trees. For each ensemble the parameter λ in equation 4.3 is varied from 0 to 1 uniformly. E.g. for an ensemble of 3 trees λ is 0, 0.5 and 1 for each of them.

Results and Experiments

Datasets and Setup

We have performed experiments on the TRECVID 2010 (TV2010) and TRECVID 2013 (TV2013) [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF][START_REF] Over | Trecvid 2013 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF] dataset with exactly the similar setup as in the previous section.

Results

The video concept detection performance is judged by calculating Average Precision (AP) on the first 2000 shots returned for each label (concept) on the test datasets.

Overall Results are positive examples for our approach. The increase is manifold from the original number of positives annotations per category on average. For the almost quadrupled TV2013 the number of labels is lower with respect to the dataset size so the label partitioning does not entirely capture the relationships between concepts as some counter intuitive partitions may be formed.

OVA (pos+neg) OVA (pos) One-Tree TV2010 45,000 1,600 9,500 TV2013 78,000 1,700 9,100

Reducing the set of labels

To further make our point we have performed an experiment with rather smaller label sets on the similar datasets. That is to say we make label partitioning trees for fewer labels. To achieve that we divided the set of 50 concepts randomly into 5 sets of 10 concepts each for TV2010 and then repeated the similar experiments. Similarly for TV2013 the 60 concepts set was divided into 6 sets of 10 and trees were generated separately for each of the 6 sets of labels. For both the datasets for every set of 10 concepts we generated 6 trees making one ensemble, finally making 5 ensembles for TV2010 and 6 ensembles for TV2013. Final classification scores were calculated separately for each ensemble and in the end we have AP scores for 50 and (38 evaluated out of 60) concepts for TV2010 and TV2013. Table 4.5 shows the MAP for the two datasets with divided label sets, which is considerably less than the MAP acquired using the full set of labels for a 6-tree ensemble, table 4.3. The number of total examples on average per classifier is also reduced, as understandable, to 6,400 for TV 2010 and 5,700 for the TV2013 dataset. Thus the performance of the label forests approach is critical to the number of labels used and increases with the increase in the label-set size.

LFO LFO-OVA TV2010 5.21 6.00 TV2013 3.12 7.01

Table 4.5: MAP scores for all concepts using subsets of concepts for tree generation

Concepts with Few Positives

To see the effect of concept detection performance on the concepts that have lesser positive annotations we select the 10 concepts from each dataset with fewest positive examples.

We compare performances of LFO with 6 trees and fusion of LFO and OVA and plot the performances on the log linear graphs in figures 4.19 and 4.20. LFO further improves performance except for "Throwing" and "Swimming" with a negligible drop.

For TV2013 the number of positive examples for the 10 concepts with fewest examples is 610 on average. Results are shown in figure 4.20 and here LFO is not as effective but the fusion tries to recover some of the loss. However LFO does bring more shots in the first 2000 for the concepts "Telephones" and "Bus" for which there was none or only a few previously with OVA.

Groups of Trees

Figures 4.21 and 4.22 show performance of various groups of trees for both the datasets. We build forests of 2 to 6 trees using the proposed method which is compared to random label partitioning for the same number of trees. Both methods are then fused with OVA for each group of trees. Since the tree generation using the algorithm in figure 4.17 generates balanced tree, the random tree generation is also done in a balanced way for a fair comparison. The depth of every tree is similar and so is the number of SVMs. The proposed method always outperforms random partitioning for single classification and also for fusion with OVA. The black box in both the figures represents MAP score for OVA. For TV2010, figure 4.21, every forest performs better than OVA and when fused the performance increases by around 30% for each forest. LF approaches do not perform as good as OVA for TV2013, 4.22, due to reasons listed earlier but again the fusion results in around 20% increase for every forest.

The improvements over the baseline are verified in their significance by randomization testing [START_REF] Smucker | A comparison of statistical significance tests for information retrieval evaluation[END_REF] for the proposed approach, for both the datasets.

Conclusions

In this chapter we have seen how explicit label sharing can benefit the video concept detection, particularly for the concepts with very few positive examples.

We have devised a quick way of grouping concepts together based on their visual similarity to train them together for concept detection in internet videos. The group making criterion is intuitive, very fast and each concept is represented by a unique combination of groups.

With the introduction of a little useful even random information we are able to improve concept detection performance on the TRECVID 2010 datasets for the list of 50 concepts.

We improve 12% and 15% over the baseline with only 10 and 20 new group classifiers formed on the clever criterion. Using random grouping we further improve but at a cost of training a total of twice as many classifiers as compared to the intelligent criterion.

We feel that this group based classification can help ultimately reduce the number of classifiers to be trained if effective combination techniques can be found. So far for the grouping of concepts we have only used visual similarity while there are other options that may be fruitful to explore. Grouping only on visual similarity results in overfitting as the number of groups increases. We would also like to add diverse information in the group or create groups from negative information. This may be achieved with using mutual information principles on negative and positive annotations for concepts. This information is inherently provided with TRECVID style multi-label datasets.

We then grouped concepts in partitions based on the similarities as well as differences from others, and proposed two techniques to achieve this partitioning. The proposed label partitioning methods use effective measures of similarities generating meaningful partitions.

This increases the learnability of the partitions which directly affects the performance. The techniques are complementary to single label classification, especially the tree-based method improves performance significantly with as little as only two trees in the forest when the two are fused. The error correcting capabilities of the tree increase as more labels are available.

During iterative tree generation to create a forest a part of validation data can be used to weight similarities between labels. Furthermore like [START_REF] Pujol | An incremental node embedding technique for error correcting output codes[END_REF] more nodes can be added to the already generated tree to further classify certain confusing labels. Since a label tree essentially results in unique codes for each category eventually other methods could be used to generate such unique codes.

Chapter 5

Leveraging from Unlabeled Data

In this thesis we are striving to improve video concept detection and we aspire to get a boost in performance by tapping into the vast resources of unlabeled data [START_REF] Niaz | Selective multi-cotraining for video concept detection[END_REF], as would be the case for any type of classification. Till this point we have only considered the annotated examples as positive and negative instances for a concept. We have also tried with borrowing examples from other concepts that are related or similar and receding from concepts that are different, but in those cases the examples from other concepts were annotated too. As stressed throughout the thesis there is always need for more annotated data to attempt to capture the variations with which a semantic concept occurs. Specifically for the TRECVID datasets we have used there is always a shortage of positive examples for most of the concepts, a good number of which is critical for the concept detection performance. Since the corpus in question is partly annotated we can always try to find useful examples to add to the training set for a concept for a better classification on the test set.

Semi-supervised Learning for Retrieval

Semi-supervised classification benefits from large number of unlabeled data where the tedious task of human intervention to annotate the data is minimized. These methods start with only a few labeled examples where the unlabeled data can be annotated iteratively to augment training resources. Learning from partially labeled data is gaining importance as unlabeled data is cheaply available and has proven to decrease classification error significantly [START_REF] Nigam | Analyzing the effectiveness and applicability of co-training[END_REF][START_REF] Yan | Semi-supervised cross feature learning for semantic concept detection in videos[END_REF][START_REF] Du | Adaptive feature split selection for co-training: Application to tire irregular wear classification[END_REF][START_REF] Blum | Combining labeled and unlabeled data with co-training[END_REF][START_REF] Xu | A survey on multi-view learning[END_REF]. Cotraining is a special case of using unlabeled examples which is useful when different feature representations of the data are available [START_REF] Blum | Combining labeled and unlabeled data with co-training[END_REF]. As the name suggests two learners trained on each data representation are used in unison to label training data for each other. This is done iteratively until training error is sufficiently reduced or all the data has been labeled. For final prediction both the classifiers are pooled together. It's a better way to find the new labels as diverse information is used from the representations and both the learners become powerful with time. There are however certain conditions that guarantee the successful working of the cotraining algorithm. Specifically it works when the different representations of data are different views and satisfy the cotraining properties. They should be conditionally independent given the class and each of them should be sufficient to learn, i.e. a learner on each view should predict the true class labels for the most part [START_REF] Blum | Combining labeled and unlabeled data with co-training[END_REF].

This comes naturally for some datasets where the features used are in fact complementary to each other and in combination reduce the classification error, however for others these conditions might be hard to satisfy. The text in the web pages and links to those pages are good examples of complementary features [START_REF] Blum | Combining labeled and unlabeled data with co-training[END_REF]. Another good example is multi-modal features where each feature represents a certain modality in learning from multimedia data.

We benefit from the situation where more than two views of the data are available and we have the liberty of choosing the best complementary view for each classifier.

Cotraining provides convergence guarantees provided the two views are sufficient and conditionally independent which is not always the case for video data (specifically visual features). Video concept detection is a hard task and the current classifiers (views) are not sufficient [START_REF] Yan | Semi-supervised cross feature learning for semantic concept detection in videos[END_REF][START_REF] Li | Co-labeling: A new multi-view learning approach for ambiguous problems[END_REF][START_REF] Zhang | Weighted co-svm for image retrieval with mvb strategy[END_REF][START_REF] Ewerth | Semi-supervised learning for semantic video retrieval[END_REF][START_REF] Zhang | Weighted co-svm for image retrieval with mvb strategy[END_REF][START_REF] Christoudias | Co-training with noisy perceptual observations[END_REF], i.e. the top ranked predictions contain an abundance of miss- We briefly overview some of the work in the literature that address this problem and offer solutions to avoid adding too much noise during cotraining.

Cotraining for Video Analysis: A review

Yan and Naphade [START_REF] Yan | Co-training non-robust classifiers for video semantic concept detection[END_REF] achieve improvement in video concept detection performance by using manual human effort to select from the most confident predictions for each cotraining view.

In another work [START_REF] Yan | Semi-supervised cross feature learning for semantic concept detection in videos[END_REF] they build classifiers separately on the newly labeled data and include them in the final prediction only if it performs well on the validation set. This restrains the learners to learn from noisy data and stops the cotraining when the predictions worsen on the validation set. Yasan and Cataltepe [START_REF] Yaslan | Random relevant and non-redundant feature subspaces for co-training[END_REF] propose methods for feature subspace selection and feature selection for cotraining. They use mutual information between class labels and features as a relevance measure to select the most relevant subspace and order the features in relevance to class labels. Li et al. [START_REF] Li | Feature selection for co-training: A qsar study[END_REF] perform feature selection for cotraining (FESCOT) by discarding the most irrelevant ones using classification accuracy on validation dataset. Features are iteratively disregarded whereas we select one complementary feature at each iteration. Zhang et al. [START_REF] Zhang | Weighted co-svm for image retrieval with mvb strategy[END_REF] find weights for Co-SVM [START_REF] Cheng | Active learning for image retrieval with co-svm[END_REF] classifiers using error on the validation set. this information is the basis for our two criteria presented later. One of the criteria proposed also selects automatically the number of new annotations to be added.

Selective Multi Co-training

Proposed Approach

Contrary to cotraining where we start with two views of the data distribution assuming that we have very little data to start the training with, here we have a good number of negative examples to start with. The number of positive examples is however very low and is in the orders of magnitudes less than the number of negative samples for each concept. All the views contain descriptors that are classifiers built on powerful visual descriptions. It is important to stress here that the difference in views is only in terms of the descriptor used.

The classification method is the same for all descriptors. So we try to add more annotations to the positive examples of a view using information from another view which is a classifier on a different visual descriptor. This other descriptor is selected out of the available ones which is expected to bring the most information to the target view. The information brought is new positive annotations which are then used to re-train the classifier using the target descriptor.

Selecting the Most Complementary View

A certain number of descriptors are available to start with. A classifier is trained on a particular descriptor which makes one view. A view thus classifies or labels a video frame, by assigning a score value to the frame. Our development data is divided into training and validation part. The final predictions are done on the test part which is independent of the development set.

Since we are using a validation set to find the most complementary view a good technique would be to find the view with minimum correlation on the ranked validation set. This will pick the view that is the most complementary to the targeted one, but this would be a good idea in the case where the initial classifiers are strong enough in terms of prediction accuracy.

In our case of video concept detection where we lag behind in terms of performance compared to other vision tasks, simply selecting the most complementary view would not do. We thus need to find the view that has minimum correlation to the targeted view and also identifies the mistakes (misclassifications) made by the targeted one. Two selection methods following these guidelines are presented later in the section.

As only the descriptor changes in a view, we call our views D. For the target view D i we try to find the one that brings the most valuable information in terms of annotations, figure 5.1. This is judged by the classification performance of the descriptors on the validation set. In the next iteration of the cotraining the training and validation sets are re-labeled for each descriptor and thus we start over the selection process for every descriptor with the newly obtained data. We call this process as Selective Multi Cotraining. It is important to mention here that in this selective multi cotraining features do not work in pairs, rather for each feature the most complementary is selected at each iteration.

Selection Methods

We present two methods to select the source view which is used to add annotations to the target classifier. We add k new positive annotations to the target classifier's training set using the selected view. For the first method k is fixed while for the next one k is found automatically per descriptor. The two methods are detailed in the next two subsections.

Positive Disagreement

To explain this selection method let's look at the left side of the figure 5. lists for all the descriptors, V D . The numbers represent the ids of the shots and the colors indicate the actual labels where green, red and black mean positive, negative and unlabeled respectively. Each shot S i in the list has a rank; rank V D (S i ) which is an integer value. The rank for the most confident prediction is 1 which is at the top of the ranked list. As the rank increases the prediction confidence decreases. So if a true positive example is predicted to have low confidence score for the concept, it would be ranked high somewhere at the bottom of the list and is treated as a misclassification. We define a function f returning 1 when the shot S i is annotated positive.

f (S i ) = 1 sign(S i ) = + 0 otherwise (5.1)
To select the most complementary view we look at the first k shots in the validation set of the target descriptor's classifier and the first k shots provided by the other views in a pairwise manner. Since we have the labels of the shots on the validation set we can calculate the disagreement between the pair: source D s and the target D t for a fixed value of k as:

DIS ts = i:rank V Ds (S i )<k ∧ rank V D t (S i )>k f (S i ) (5.2)
The disagreement counts for the source view D s how many labels are positive that did not appear in the first k shots for the validation shot list of the target view D t . This is essentially the information that is missed by D t for the top k shots. We select the D s with maximum DIS ts as it is understandable that the predictions done by this descriptor are the most complementary to D t . For figure 5.2 if k is fixed as 3, then DIS 12 = 0, DIS 13 = 1 and DIS 14 = 0 and D 3 is selected to add new labels for D 1 in the next iteration.

D 2 D 3 D 4
Precision Based Rank

Precision based Rank

The positive disagreement approach suffers from two setbacks. First is how to select the optimal value of k. For concepts with low initial positive examples, which is the case more often than not, 10% new labels are quite low while on the other hand for concepts with already abundant pool of positive examples 10% new examples may add noise. This noise will increase with k. The other predicament which is related to first one is how sure are we that the new labels added really bring valuable information. Furthermore and as more iterations are performed how useful the newly added labels are before they start to add wrong annotations and distort the data.

To cater these issues we need to find a source D s for D t that is expected to add up to a certain percentage of correct positive labels. So we add a restrained number of new examples to each view with a certain confidence. We use the precision on the classification results of the validation set for each of the source views to build this criterion. We restrict the classifiers to relabel only a certain number of examples some of which are expected to be correct with a certain confidence. Figure 5.2 is again used to explain this method. First for every ranked list we find k for a fixed precision value pr. That is to say using the true labels of the validation set we scroll down the ranked list calculating precision at every step and stop when the precision is lower than pr. The precision for the list V D for a value of k is

P k V D = k i=1 f (S i ) k (5.3)
and to find k for V D we maximize equation 5.3 for k as:

k s = argmax k P k V Ds s.t. P k V Ds >= pr (5.4)
So for the example in the figure 5.2 we find the values of k s for precision of 50%. k 3 = 4 and for the other three descriptors the value of k is 2. Note that k 1 is not an important factor here as the k for target descriptor is not used in the criterion presented just after.

Once k is determined for each source descriptor, for D t we simply select the D s that maximizes the average rank of the first k s shots on the validation set V Dt . Maximum rank means that those shots that are ranked as positive by the source classifier are at the bottom of the list V Dt . It means that this source classifier identifies the most serious misclassifications for the target on the validation set. We define this average rank for the source descriptor D s as:

P RR s = ks i=1 r V D t (S i ) k s (5.5)
where each source has a different P RR s for a unique k s and the D s which maximizes equation Again as the positive disagreement method this selection is done separately for each concept.

For further iterations of the process the modified training and validation lists are used from the previous iteration.

Results and Experiments

Experimental Setup

We have carried out experiments on the TRECVID 2013 [START_REF] Over | Trecvid 2013 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF] We have mainly extracted 2 kinds of descriptors from the video keyframes the SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and the color SIFT [START_REF] Van De Sande | Empowering visual categorization with the gpu[END_REF] which are all densely extracted. These extracted descriptors are then used to build visual dictionaries using k-means clustering. Using the above extractions we build 5 types of descriptors of varying lengths (dictionary sizes). For dense SIFT, dictionaries of 4000 and 10,000 are built and we get two descriptors: dsift4K and dsift10K. For color dense SIFT we have cdsift1K, cdsift4K and cdsift10K from dictionaries of 1000, 4000 and 10,000 visual words.

All the classifiers used are 1 vs. all SVM classifiers using homogeneous kernel maps [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF][START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF] built on the input features. We have used Pegasos training [START_REF] Shalev-Shwartz | Pegasos: Primal estimated sub-gradient solver for svm[END_REF] for speedy optimizations. We calculate the Average Precision (AP) for each concept and present the percentage Mean AP (MAP).

Results

We have conducted a certain number of experiments using the two proposed descriptor selection methods. For these experiments we have used all the labeled data provided by

Cotraining vs. 1 pass and selftraining

The two selection methods for multi-cotraining are compared with the single pass learning (Baseline) and also with selftraining or bootstrapping. Two kinds of selftrainings were done;

adding fixed percentage of positive examples and adding positive annotations using the precision method, where we first calculate k t for expected precision value using equation 5.3 and then add k t new positive labels to the training set of D t . Table 5.1 shows results for second kind of selftraining as it performs better among the two and compares it to the two proposed selective cotraining methods.

We show results for 3 iterations of relabeling and retraining in table 5.1 for all the semisupervised methods. Results that are significantly better with randomization testing [START_REF] Smucker | A comparison of statistical significance tests for information retrieval evaluation[END_REF] are underlined. Selftraining and positive disagreement (DIS) methods are mostly outperformed by the Maximum rank on precision based selection (PRR). This is true for further iterations as for DIS noise is added with a fixed value of k, and selftraining lacks complementarity of using other descriptors. When k is 10% the performance of DIS is good as few noisy labels are added and it sometimes shows better results than the PRR. For the PRR criteria as the precision increases the value of k s decreases and in many cases no new labels are added for certain categories, for example for pr = 70%. Though we see an improvement for most of the descriptors for DIS and PRR the color SIFT descriptors seem to absorb more noise than others.

Cotraining vs. Linear Fusion

To check the complementarity of descriptors we fused every possible pair of the 5 descriptors

Selected Views

Our goal was to select the most complementary view to label examples and PRR outperforms DIS for the major part. We have only used visual descriptors to generate our views with two slightly different categories of descriptors of varying sizes. Lets have a look at the views selected for the "cdsift10" and "dsift10k" that are the best descriptors in their categories.

We look at the view selected for each concept off the 38 evaluated concept. the different one most of the times. Moreover for "cdsift10k", "dsift10k" is selected the most out of the dsift's and also the vice versa is true. There are cases when no view is selected to do co-training when the precision criterion is not met on the validation set. This means that the particular descriptor for a concept did not achieve the required precision even for the first 2 shots on the validation set and re-training is not performed for that concept. Looking at the tables 5.2, 5.3 and 5.4, we can safely say that our method tends to select the best view to label new instances.

Adding a Different Descriptor

To further test our selection methods we add a more powerful descriptor, caffe1000 [START_REF] Yangqing | An open source convolutional architecture for fast feature embedding[END_REF] in the selective multi-cotraining mechanism. caffe1000 is a 1000 dimensional descriptor containing scores of 1000 concepts trained on the ImageNet [START_REF] Deng | ImageNet: A Large-Scale Hierarchical Image Database[END_REF]. We use the same SVM settings for the

Conclusions

We have demonstrated the effectiveness of selecting the appropriate feature to relabel a target learner for cotraining when different options are available. For each descriptor the best complementary descriptor is selected and the number of examples to label is also automatically selected which are expected to be correct up to a certain percentage. For future work it is required to find a successful weighing strategy to find relevance of the newly added labels.

The relevance scores for a category can be attached to each example and will highlight its importance in training [START_REF] Li | Classifying tag relevance with relevant positive and negative examples[END_REF]. Furthermore it is important to (i) refine the k new positive examples added by an automatic or manual [START_REF] Yan | Co-training non-robust classifiers for video semantic concept detection[END_REF] selection, and (ii) automatically identify the number of cotraining iterations for each concept. Eventually the selective cotraining can be used to find negatives by reversing the selection criteria. The former performs lower on the sift descriptors but shows better performance, though not statistically significant, to the later on the caffe1000. performance when using the information about the whole concept distribution to build the dictionary.

Restrained Multi-view Learning

Adding Refinement to the Video Representation

State of the art tells us that the orderless BOW histogram representation does not account for any specifics about the location of a keypoint inside the BOW clustering cell. This has certainly attracted some research attention and as a result we have seen methods proposing to include geometric, spatial and keypoint specific information that improved the discriminative power of the BOW model. We also focused our attention to this area and produced a method to add a descriptor's location specific information into the BOW representation. The extra information is fused into the BOW vector in terms of a very small vector capturing the difference of each keypoint from its cluster center which also resulted in better discrimination ability of the BOW model compared to the state of the art.

Using Multi-labeled Data: Similarity Among Concepts

This contribution challenged the normal practice when building the classification models for concepts where annotated data is used to construct the model for only that concept. We found similar concepts that are supposed to share certain visual properties, grouped their instances together and trained the classifiers on the combined set of examples. We demonstrated that the performance of these shared classifiers reached the performance of the single concept classifiers and also that this sharing does bring complementary information when fused with the single concept learning. We agree that the accomplishment was not as shiny as the idea but it was marred by many factors including the quality of the accumulated annotations, the method selected to find similarity, the overall low number of concepts and the increased complexity of the non-linear group classifier. However our intelligent grouping criterion proved to be better than random grouping of concepts and the RAKEL based grouping for video concept detection of TRECVID videos.

Using Multi-labeled Data: Similarity and Dissimilarity Among Concepts

Here we integrated dissimilarity in addition to similarity when grouping (rather partitioning) the set of concepts and observed that the shared classifiers matched and sometimes surpassed the performance of single concept learning with classifiers that were trained using considerably less training data than the norm. The overall number of classifiers trained were also less than the baseline which is important considering the complexity of machine learning methods.

Using Unlabeled Data: View Selection for Cotraining

Finally we turned our attention to the immense quantity of unlabeled video data that is readily available all over the internet and consists of a large part of TRECVID style partially annotated video datasets. We have studied the semi supervised learning methods and looked at the nifty method of cotraining to iteratively improve classifiers using unlabeled data but realized the sad reality of its disappointment for visual analysis methods, particularly video concept detection. With the gradual evolution of the field in terms of performance and scalability, semi-supervised learning is also gaining importance as it relieves us of manually and painstakingly labeling each and every keyframe of unlabeled videos. We deem that it is important to find the most useful of the information among the unknown and put it to good use. To that end we developed methods to select the most complementary cotraining view to increase the size of the training set of a classifier with the most constructive and informative examples.

Promising Directions

We divide the future perspectives into the work that extends the presented contributions and some general perspectives for content based indexing and retrieval.

Immediate Future Work

In the context of our proposals we have presented some future directions throughout the dissertation but here we would like to stress certain points that could lead to immediate future work. Addressing chapter 3 different kernel design should be envisaged for the DBOW bins as it models different information from the BOW histogram. Alternatively an effective weighting mechanism [START_REF] Wang | Weighting informativeness of bag-of-visual-words by kernel optimization for video concept detection[END_REF] for the DBOW could be developed as well as finding the optimal DBOW size for a given visual dictionary. Since each high dimensional Voronoi cell has distinct dynamics a cell based quantization would result in more precise representation but at a higher cost. Concept wise DBOW construction is also a possible refinement by making a DBOW histogram separately for each concept using descriptors from images labeled only with that concept.

A requirement that is felt throughout the thesis is the need to go bigger. Since the real world is way bigger than a list of tens of concepts what would happen if larger dataset with considerably more concepts and increased set of examples is used? Considering direct application of the proposed methods in chapter 4 we believe that sharing among classes will always help and with more classes present better choices of grouping and partitioning will be available to increase learnability of the system. The group based classification will not scale well to the larger pool of information but the partitioning based methods are scalable.

An example is to use the list of concepts from the full TRECVID Semantic Indexing task [START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF] to generate the partitions and train the classifiers, and then calculating the performance on the light task. As shown in the analysis in section 4. Pursuing more work in semi-supervised learning is interesting especially for finding the most useful and a minimum number of new labeled examples. From the selective cotraining and multi-view results in chapter 5 we saw that overall the views only agree to a very small degree on the relevance of the unlabeled examples. Still we saw improved performance for all the views. We believe that adding a much stronger view (a good descriptor with a strong classifier) in the selective cotraining mechanism would improve the results further by pointing the others into the right direction.

In the two view selection criteria we devised we always fixed the values which determined the number of new examples to be added. This could be changed so that the criterion dynamically updates according to the performance of the classifier (view) during the course of the retraining iterations. An example is staring with 30% new examples to be added for a concept and then decreasing this percentage along the way. This also makes sense as we have used a fixed dataset where only few of the unlabeled examples would benefit the concept classifier if at all. Furthermore using such a methodology would automatically include a stopping criterion when the performance on the validation set starts to decline.

Another extension is to revert back to a previous iteration if performance on the validation set declines, like the view validation in [START_REF] Yan | Semi-supervised cross feature learning for semantic concept detection in videos[END_REF].

General Perspectives

There exists still a huge gap in the improving scientific research published year by year and the acceptance of state of the art methods in industry or real applications. This disconnect between the research and its applicability in real life has been felt by many researchers and various applications are now emerging. Some popular examples for image based retrieval systems are the INRIA's IKONA [208], LIRE [START_REF] Lux | Content based image retrieval with lire[END_REF], pixolu, and the SHIATSU system [START_REF] Bartolini | Shiatsu: tagging and retrieving videos without worries[END_REF] for keyframe based video indexing. The importance of content cannot be denied and it is about time that industrial search engines replace keyword based search with content based indexing or at-least include it in their framework. Google and the Russian search engine Yandex led the pioneering work and offer online content based image search.

Scalability of the methods is also important to make them portable to be used on the numerous hand held devices. Smartphones and tablets are now equipped with high resolution cameras and sophisticated hardware with ample processing power. Applications like automatic recognition of commodities, etc. are already making wave in the online stores of various platforms.

Research work has continued to evolve and promising results are published on harder datasets every year. Lately the focus has been on de-correlating the training and the test set [START_REF] Lampert | Learning to detect unseen object classes by betweenclass attribute transfer[END_REF][START_REF] Farhadi | Attribute-centric recognition for cross-category generalization[END_REF][START_REF] Parikh | Relative attributes[END_REF] (training models that are not specific to the dataset used). This means the test set is taken from a different source which is generally not the case for the databases used in scientific research these days. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Global and local image descriptors

------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------

Coding Pooling

Projecting the descriptors into the coded space Aggregating the projections to aquire a fixed length feature une image [7]. Quelques exemples de codage comprennent la quantification vectorielle [8],

quantification 'soft' [9,[START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]

B.2.3 Motivation

Les informations extraites des images vidéo au niveau du pixel sont des descriptions de bas niveau de l'image, ce qui ne se traduit pas directement à la sémantique de l'image. Il existe donc un gap sémantique [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] entre les caractéristiques ou des descripteurs de bas niveau que le système de vision utilise, pour en apprendre sur la sémantique de haut niveau que l'image représente. Il ya plusieurs raisons pour l'existence de cet écart. Le plus important est la différence dans la perception humaine d'un concept et la représentation appropriée pour nos ordinateurs à comprendre. Ensuite, il ya la subjectivité [START_REF] Hanjalic | Affective video content representation and modeling[END_REF][START_REF] Snoek | Concept-based video retrieval[END_REF] La performance d'un système de catégorisation dépend de tous les éléments qui constituent le pipeline de détection. Pour chacune de ces étapes, nous énumérons ci-dessous les principales possibilités d'amélioration.

• Les caractéristiques extraites au niveau du pixel

Comme la base du pipeline de détection de cette phase reçoit une attention considérable de recherche afin de capturer l'information la plus utile avec une taille raisonnable à partir des images. • Nous étendons l'idée ci-dessus pour regarder concepts qui ne sont pas si proche, plutôt que sont différentes, afin d'apprendre de la dissemblance entre les concepts.

------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ - ------ -
• Enfin, nous essayons d'explorer les exemples non étiquetés dans une manière d'entraînement semi-supervisée. Nous augmentons la quantité de données annotées et utilisons les meilleures informations sur elles pour apprendre les modèles des concepts. ont été allouées dans les magasins en ligne de différentes plates-formes.

B.3 Nos Contributions

Les travaux de recherche ont continué à évoluer et des résultats prometteurs sont publiés sur ensembles de données plus difficiles chaque année. Récemment, l'accent a été mis sur la de-corrélation de la base d'entraînement et celui de teste [START_REF] Lampert | Learning to detect unseen object classes by betweenclass attribute transfer[END_REF][START_REF] Farhadi | Attribute-centric recognition for cross-category generalization[END_REF][START_REF] Parikh | Relative attributes[END_REF] (modèles d'entraînement qui ne sont pas spécifiques à l'ensemble de données d'entraînement). Cela signifie que l'ensemble de test est tirée d'une autre source qui n'est généralement pas le cas pour les bases de données utilisées dans la recherche scientifique de nos jours.

L'apprentissage zero-shot [START_REF] Farhadi | Describing objects by their attributes[END_REF][START_REF] Parikh | Relative attributes[END_REF][START_REF] Cissé | Learning compact class codes for fast inference in large multi class classification[END_REF] gagne également une importance car il aborde le problème de l'annotation de nouveaux concepts émergents. Le contenu de l'Internet continue de croître et c'est le même cas pour la liste des concepts sémantiques. En outre, les tendances sociales doivent être prises en compte comme quelque chose qui est pertinent aujourd'hui ne peut être inscrit dans le bar d'un moteur de recherche pour les années à venir.

Récemment l'apprentissage en profondeur deep-learning [START_REF] Ngiam | Multimodal deep learning[END_REF] a repoussé les limites de la performance sur la compréhension de la sémantique pour la détection de concept à l'aide de réseaux de neurones à convolution [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Socher | Convolutional-Recursive Deep Learning for 3D Object Classification[END_REF]. Ils ont la capacité à extraire automatiquement et concevoir des caractéristiques significatives des valeurs brutes de pixels des images.

Néanmoins, les réseaux de croyances profondes sont difficiles à former, nécessitent une grande quantité de données d'entraînement et, dans certains cas, un matériel spécial. Cela peut être considéré comme un autre peek dans les algorithmes de classification comme les réseaux de neurones de retour dans les années 80, mais pour l'instant rien ne correspond à leur exactitude et performance.

Pour conclure, il est sûr de dire que nous nous dirigeons dans la bonne direction pour rendre nos machines soient en mesure de comprendre le contenu visuel. L'information est là et il augment de plus en plus et est aussi la puissance de traitement de nos ordinateurs.

Il s'agit de l'utiliser correctement avec les bonnes méthodes. Nous avons également besoin d'élargir nos horizons en explorant d'autres indices qui peuvent être importants dans la compréhension du contenu. Donner un sens à l'interaction entre les entités sur l'Internet, l'activité sociale, modélisation de l'utilisateur pour obtenir un aperçu des connaissances et des intérêts de l'uploader de la matière [START_REF] Niaz | Improving video concept detection using uploader model[END_REF][START_REF] Merialdo | Uploader models for video concept detection[END_REF], la location de l'utilisateur et de l'intérêt mutuel entre les utilisateurs d'un services de partage de contenu sont quelques-uns des indices qui pourraient être exploitées pour faire plus de sens du monde visuel.

Abstract i to merge 4 . 5

 45 the Voronoi cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Unrelated keypoints in a clustering cell: label information from images is used to split the Voronoi cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Supervised merging of visual words . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Related keypoints in neighboring cells: label information from images is used to merge the Voronoi cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Supervised clustering scores for 20 concepts using the first (best) entropy minimization criterion for (a) 500 and (b) 1000 visual words dictionaries . . . 3.7 Distribution of Difference vectors in a Voronoi cell: (a) magnitude of Difference vectors, (b) quantized over a 50-centroid global difference dictionary . . . . . 3.8 Representation of BOW and DBOW . . . . . . . . . . . . . . . . . . . . . . . 3.9 Concept scores for TRECID 2007: increase/decrease in Average Precision score over the baseline for the best performing HE similarity and DBOW methods for the 3 base dictionary sizes. . . . . . . . . . . . . . . . . . . . . . 3.10 Concept scores for TRECID 2010: increase/decrease in Average Precision score over the baseline for the best performing HE similarity and DBOW methods for the 3 base dictionary sizes. . . . . . . . . . . . . . . . . . . . . . 4.1 Single Label Learning Paradigm or One vs. All Learning . . . . . . . . . . . . 4.2 Single Label learning vs Groups of Labels learning . . . . . . . . . . . . . . . 4.3 Single Label learning vs Groups of Labels learning . . . . . . . . . . . . . . . 4.4 M matrices for 4-class ECOC representations: (a) Binary ECOC design. The codeword for the new predicted example x is closest to class having label l 2 . (b) Ternary ECOC design where the gray entries correspond to the 0 in the dichotomies. Here x is assigned the label l 1 based on hamming distance. . . . ix List of Figures x Grouping of concepts into non mutually exclusive partitions: a) A simplified space is shown with some labeled (and multi-labeled examples. b) Grouping of concepts. Concepts may appear in multiple groups. c) Each concept is a unique bit string and no group is empty. . . . . . . . . . . . . . . . . . . . . . 4.6 Average visual features and the induced visual space. . . . . . . . . . . . . . . 4.7 Clever grouping when then number of groups is less than the number of concepts. 4.8 Clever grouping when then number of groups is greater than the number of concepts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Mean Average Precision for 50 concepts for different grouping criteria and their fusion with the baseline. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Evolution of the fusion weights with the increase in the number of groups. . . 4.11 ECOC construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Find the distortion within a partition of labels . . . . . . . . . . . . . . . . . 4.13 ECOC matrix generated for TRECVID 2010 dataset with λ = 0. . . . . . . . 4.14 ECOC matrix generated for TRECVID 2010 dataset with λ = 1. . . . . . . . 4.15 Average Precision for 50 concepts: Ensemble of 6 ECOCs, TRECVID 2010. . 4.16 Average Precision for 38 concepts: Ensemble of 6 ECOCs, TRECVID 2013. . 4.17 Node Splitting Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.18 A binary tree which partitions the label-set and the corresponding M -matrix with 3 dichotomies. Each node of the tree represents a column of the M-matrix 4.19 AP scores for 10 concepts with fewest positive annotations in TV2010 . . . . 4.20 AP scores for 10 concepts with fewest positive annotations in TV2013 . . . . 4.21 TRECVID 2010 (50 concepts). Performance (MAP) comparison of proposed label partitioning to random partitioning and single label classification, for various groups of trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.22 TREVID 2013 (38 concepts). Performance (MAP) comparison of proposed label partitioning to random partitioning and single label classification, for various groups of trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Selective Multi Cotraining: Identifying the best view at each iteration for retraining from a choice of views . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Selecting source view for Selective Multi Cotraining methods and adding new examples to the training set. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Linear fusion of every pair of descriptor for different methods . . . . . . . . . B.1 Détection de concept dans une vidéo . . . . . . . . . . . . . . . . . . . . . . . B.2 Le pipeline de détection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 L'extraction des caractéristiques locales et globales. . . . . . . . . . . . . . . . B.4 Codage et agrégation des caractéristiques de bas niveau pour généré un descripteur resumé de l'image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.5 (a) Un classificateur discriminatif distinguant les exemples positifs et négatifs. (b) Un classificateur generatif adapté à la distribution des exemples positifs. . B.6 La fusion précoce et tardive . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.7 Le monde visuel avec de nombreuses images, descripteurs et classificateurs. . Chapter 1

Figure 1 . 1 :

 11 Figure 1.1: Video Concept Detection

Figure 1 . 2 :

 12 Figure 1.2: Video Concept Detection Pipeline.

-Figure 1 . 3 :

 13 Figure 1.3: Global and local feature extraction example.

Figure 1 . 4 :

 14 Figure 1.4: Coding and pooling to generate the summarized feature for an image.

  State of the art in learning such kind of a model is mainly divided into two parallels: discriminative learning and generative learning, figure 1.5. Discriminative classifiers learn

Figure 1 . 5 :Figure 1 . 6 :

 1516 Figure 1.5: (a) A discriminative classifier separating positive and negative examples. (b) A generative classifier adapted to the positive concept examples.

Figure 1 . 7 :

 17 Figure 1.7: The Visual World with numberous images, feaures and classifiers.

chapter 4 Chapter 2

 42 we base our work on the similarities and differences between concepts to try to find useful new examples to perform improved concept detection. Chapter 5 explores the unlabeled examples and presents criteria to select the most useful new examples. Finally in chapter 6 we summarize our contributions and draw conclusions. We also list possible future avenues to explore for automatic analysis of video content especially leading to video concept detection.State of the ArtAutomatic analysis of video content is among the hardest problems faced by the computer vision and multimedia community. It receives a significant amount of dedicated research attention from academic and industrial research teams all over the globe due to its importance in the growing digital world. As pointed out in the introduction the research in this field is truly interdisciplinary and integrates works ranging from image and signal processing to statistical machine learning. Consequently it is imperative to review the state of the art in the vast field of visual content analysis specifically targeting video concept detection and retrieval. This chapter lists important contributions to each of the stages of the concept detection pipeline starting from raw feature extraction to fusing the high level decisions.

  problems of video concept detection and video/image retrieval generally fall under the paradigm of supervised learning where a number of annotated image instances are available to build the model for each semantic concept. The learned model is trained on the ground-truth images to classify new instances as belonging to the class or not. Supervised classification methods are divided into two broad categories; Generative Classifiers, which learn the joint probability distribution of the training examples and the outputs for each class and apply Bayes' rule to predict the class probability of the new instance, and Discriminative Classifiers, which directly learns the classification boundary using examples from both class and nonclass instances.

  is a histogram based representation of scene description obtained through vector quantizing thousands of visual descriptors into a discrete visual dictionary. The visual descriptors are usually patch based features describing key interest points in video frames and are referred to as Local Image Descriptors (LIDs). The interest points can be detected by maximizing some function to identify areas in the image containing rich visual information or can be densely sampled from the image at fixed points. LIDs are then computed for each of the interest points by analyzing their local neighborhoods and are usually high dimensional vectors of fixed length. The descriptor vectors from the training set are quantized using some unsupervised clustering process, like k-means, to divide the visual space into adjacent Voronoi cells. The centroids of the Voronoi cells in the visual space represents Visual Words. Each visual word corresponds to a bin of the final histogram that counts the number of features assigned to that cell (bin) for an image. The number of clusters and thus size of the histogram is fixed at the time of clustering. Each image is then represented by a fixed dimensional histogram, irrespective of the number of features extracted from the image as shown in the bottom right part of the figure 3.1. This histogram vector is computed for each image and can be directly fed into a discriminative classifier like Support Vector machines (SVM) to build a model for each category.

  2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11

Figure 3 . 1 :

 31 Figure 3.1: Visual Dictionary construction and histogram vector generation

Figure 3 . 2 :

 32 Figure 3.2: Related keypoints in neighboring cells: label information from images is used to merge the Voronoi cells

Figure 3 . 3 :

 33 Figure 3.3: Unrelated keypoints in a clustering cell: label information from images is used to split the Voronoi cell

3 . 4 ,

 34 first of all the descriptors from the training images are quantized into a large number of visual words using k-means. The number of initial visual words (k-means clusters) is p * D, where D is the size of the desired dictionary.

Figure 3 . 4 :

 34 Figure 3.4: Supervised merging of visual words

Figure 3 . 5 :

 35 Figure 3.5: Related keypoints in neighboring cells: label information from images is used to merge the Voronoi cells

Figure 3 . 6

 36 shows concept-wise Average Precision (AP) results along with the MAP for the two baselines of 500 and 1000 visual words and entropy minimization based mappings with the value of p selected from 2, 4 and 8. Concepts like Airplane Flying and Person Playing Soccer that have a very low number of positives in the training set are adversely affected in their performance

Figure 3 . 6 :

 36 Figure 3.6: Supervised clustering scores for 20 concepts using the first (best) entropy minimization criterion for (a) 500 and (b) 1000 visual words dictionaries

  -(a) and 3.3-(b) shows the upper bounds of improvements for the two step clustering performed with its alternatives showing significant increase in the individual score for each concept for 500 and 1000 word final dictionary sizes. Individual scores for each concept improve significantly with only the concepts Person eating and Traffic intersection showing little improvement as their performance is already quite high. An exception is the concept Airplane flying which shows a decrease in performance with supervised merging for 1000 words dictionaries as shown in Table 3.3-(b).

Figure 3 . 7 :

 37 Figure 3.7: Distribution of Difference vectors in a Voronoi cell: (a) magnitude of Difference vectors, (b) quantized over a 50-centroid global difference dictionary

Figure 3 . 8 :

 38 Figure 3.8: Representation of BOW and DBOW

  by 10 normal k-means iterations to generate visual dictionaries. Visual dictionaries with 500, 1000 and 2000 visual words are computed separately for both the datasets. The same dictionaries are used for all the experiments, namely: the BOW baseline, the Hamming Embedding Similarity based feature and the BOW-DBOW feature.The baseline comprise of classifiers trained on the simple BOW models. DBOWs of 10, 50 and 100 difference words are computed for each of the three visual dictionaries. Thus a total of 9 DBOW models are created for each dataset again using the rapid k-means method (k-means++ and 10 iterations of k-means). For calculating the HE Similarity Scores signature again the baseline dictionaries are used as described later.

  5 and 3.6 for TRECVID 2007 and 2010 respectively. For each size of base dictionary there are three versions of HE similarity score based classification. Version 1 is the performance of HE similarity score based feature without any normalization, version 2 represents results with normalized feature using α = 0.3 while version 3 uses α = 0.5. Similarly for DBOW based methods (DBOW and weighted DBOW) the versions 1, 2 and 3 show DBOW vector of size 10, 50 and 100 added to the (BOW of) base dictionary for all sizes. For baseline there is only version 1 which shows classification results on the base dictionary for the three sizes. TRECVID 2007 Table 3.5 shows the Mean Average Precision (MAP) scores for 20 concepts of the TRECVID 2007 dataset for the three versions of the HE similarity and DBOW based features and compares them to the baseline. It proves the discriminative power of DBOW bins added

Figure 3 . 9 :

 39 Figure 3.9: Concept scores for TRECID 2007: increase/decrease in Average Precision score over the baseline for the best performing HE similarity and DBOW methods for the 3 base dictionary sizes.

Figure 3 .

 3 Figure 3.10 shows the relative increase or decrease in performance of the 50 concepts for the best performing HE similarity and DBOW methods compared to the BOW baselines for the three dictionary sizes. Again the DBOW outperforms HE similarity based method for most of the concepts except Computer or Television Screens, Dark-skinned People, Doorway, Indoor, Military Base, News Studio, Road and Vehicle. DBOW performs better on average for the three cases. HE similarity occasionally performs worse than the base line. HE signature computes similarity to training images and is thus very dense. This adversely affects the SVM training time specially for the non-linear kernel used for TRECVID 2007 dataset. On the other hand DBOW signature is also dense due to its smaller size but the sparsity of BOW diminishes the dense effect and training the classifiers takes much less time than for HE similarity vectors.

Chapter 3 . 48 -Figure 3 . 10 :Figure 4 . 1 :

 34831041 Figure 3.10: Concept scores for TRECID 2010: increase/decrease in Average Precision score over the baseline for the best performing HE similarity and DBOW methods for the 3 base dictionary sizes.

Figure 4 . 3 :

 43 Figure 4.3: Single Label learning vs Groups of Labels learning

4 .Figure 4 . 4 :Chapter 4 .

 4444 Figure 4.4: M matrices for 4-class ECOC representations: (a) Binary ECOC design. The codeword for the new predicted example x is closest to class having label l 2 . (b) Ternary ECOC design where the gray entries correspond to the 0 in the dichotomies. Here x is assigned the label l 1 based on hamming distance.

Figure 4 . 5 :

 45 Figure 4.5: Grouping of concepts into non mutually exclusive partitions: a) A simplified space is shown with some labeled (and multi-labeled examples. b) Grouping of concepts. Concepts may appear in multiple groups. c) Each concept is a unique bit string and no group is empty.

Figure 4 . 5

 45 shows our intuition of the group based classification scheme. Ideally for C concepts log 2 C group classifiers are enough for learning as each concept can be identified with a unique bit string.

Figure 4 .Figure 4 . 6 :

 446 Figure 4.6 shows the average feature vectors and also the visual space. This is the space where the concept or label features are projected and represented by the distances between them.

  Figure 4.7 shows the 3 clusters generated for the dummy problem shown previously in the figure 4.6 with 6 concepts. The three cluster centers correspond to the 3 groups generated with different concepts. Note that each concept appears in different groups and this combination is unique, i.e. no two concepts appear in exactly similar groups all over, figure 4.7.

Figure 4 . 7 : 3 Figure 4 . 8 :

 47348 Figure 4.7: Clever grouping when then number of groups is less than the number of concepts.

4 .

 4 regenerated. The maximum value of n is fixed as 12 in our experiments with C = 50. It can be confirmed from figures 4.7 and 4.8 that each concept induced a unique combination of groups. For figure 4.7 where the number of groups is less than the number of concepts the Chapter Leveraging from Multi-label Data 64 bit strings for each concept are: (l 1 : 001), (l 2 : 110), (l 3 : 011), (l 4 : 010), (l 5 : 100) and (l 6 : 111). The maximum number of concepts represented by D is 2 D -1.

(

  concepts) is positive for that example. The number of positive examples increase rapidly for a group with concepts having disjoint positive annotations. All the remaining examples in the training dataset are treated as negative examples. Each group is then trained in a 1-vs-all fashion. Prediction on a test frame generates the score s(f |g) which is the score of the test frame f for the group g. Concept score is then calculated on the normalized groups scores as:

  dataset containing 11644 internet videos. This comprehensive dataset is divided into the training part with 3200 videos of 200 hours with a total of 119,685 keyframes. Rest of the approximately 8000 videos of 200 hours containing 146,788 keyframes are used for testing purposes. For testing the performance of various multi-label or group classification based systems on video concept detection we have used the list of 50 concepts from the TRECVID 2011 Light Semantic Indexing task.

Chapter 4 .Figure 4 . 9 :

 449 Figure 4.9: Mean Average Precision for 50 concepts for different grouping criteria and their fusion with the baseline.

  Weights: Although intelligent grouping outperforms random grouping for concept detection for all group sizes this does not stay the same when the group based scores are fused with single label classification scores. To further analyze this we look closer at the fusion and investigate the fusion weights assigned to the concepts for different number of groups.Figure 4.10 plots the evolution of the fusion weights for the three multi-label approaches for different group sizes derived from the training data. The figure shows the average of the weights assigned to each concept score derived from the group based approaches compared to concept scores from individual concept learning in the linear fusion. The fusion

Figure 4 . 10 :

 410 Figure 4.10: Evolution of the fusion weights with the increase in the number of groups.

  Powersets the number of examples for the label set {0, 0, 0} where all the 3 concepts are negative dominates the number of examples for other label sets. This complicates things as the label sets like {1, 0, 0} or {1, 0, 1}, where one concept is truly distinguished against others have very few positive examples for training. The final score for each concept in the end is thus dominated by the negative score of the classifier trained on examples from the label set {0, 0, 0}. From the TRECVID 2010 training data and our setting of the RAKEL algorithm we have on average 6188 positive training examples for the label set {0, 0, 0} for every LP classifier compared to only 168 positive examples for other label sets. Thus an LP classifier lacks the examples for the truly discriminative label combinations owing to the relatively poor performance.

  This technique adapts ECOC for multi-label classification and is essentially different from the group based classification presented before. In grouping only the similarity between concepts is used to build groups, for which classifiers are trained considering all the other examples as negatives. Here partitions are made based on similarity as well as dissimilarity among concepts. Moreover we do not use all the negative examples provided by the dataset rather only the positive examples from both the partitions lie on either side of the classifier. This is again essentially different from attributes as we do look at the properties that certain classes have but simultaneously these properties are absent from other classes. Moreover attributes require manual definition and labeling and also the knowledge of presence or absence in concepts. Hashing works at image level while here again we build codes for classes and all the examples of the said class should have the same code.

Figure 4 . 2 :

 42 Figure 4.11: ECOC construction

Figure 4 . 12 :

 412 Figure 4.12: Find the distortion within a partition of labels

8 ) 4 . 3 . 1 . 3

 84313 Ensemble of ECOCsEquation 4.3 gives us the choice to alter the similarity in favor of visual or semantic criterion and in result create many different partitionings. I.e. the value of λ is changed to generate many ECOC M matrices and this generation is very quick since it uses precomputed similarity information which itself takes only one pass over the training set. Furthermore with each value of λ we can change the distortion criteria using Θ to change the size of the partitions (and also the resulting M matrix). We combine the scores from each of the ECOC and combine it with others to generate ensembles of ECOCs. For combination we have used weighted linear fusion. If s k (l|f ) is the test frame score for the label l from the k'th ECOC then the fusion weights are calculated as follow from the K ECOCs: s(l|f ) = K k=1 w k l * s k (l|f ) to give the final ensemble score s(l|f ) for the test frame. This fusion is done separately for each label and fusion the weights are optimized on the training set. We have built varied combinations of ensembles from different ECOC generations. The value of λ is taken from {0, 2.5, 5, 7.5, 1} with λ = 0 dictating the generation of a semantic ECOC and λ = 1 leading to a visual ECOC construction. Θ take on from the following four values which are fixed through experimentation on the training set: Θ ∈ {1.25, 1.5, 2, 4}. We have built 9 ensembles by changing these parameters. First five ensembles have 4 ECOCs each where the value of λ is fixed and Θ is varied. Similarly four more ensembles are generated for fixed λ with 5 ECOCs owing to the changed λ.

Figure 4 . 13 :

 413 Figure 4.13: ECOC matrix generated for TRECVID 2010 dataset with λ = 0.

Figure 4 . 14 :

 414 Figure 4.14: ECOC matrix generated for TRECVID 2010 dataset with λ = 1.

Figure 4 . 15 :

 415 Figure 4.15: Average Precision for 50 concepts: Ensemble of 6 ECOCs, TRECVID 2010.

Figure 4 . 16 :

 416 Figure 4.16: Average Precision for 38 concepts: Ensemble of 6 ECOCs, TRECVID 2013.

Figure 4 . 17 :

 417 Figure 4.17: Node Splitting Algorithm

For training each node

  is considered one binary classifier since it partitions the labelset into two sets. All the examples belonging to the labels in the left partition are treated as positive examples and the examples belonging to labels in the right partition are considered negatives. So the positive and negative examples for each classifier are actually only the

Figure 4 . 18 :

 418 Figure 4.18: A binary tree which partitions the label-set and the corresponding M -matrix with 3 dichotomies. Each node of the tree represents a column of the M-matrix

For good error correction

  we argue that the label set should be dense in relation with the number of examples. Since we have established that related labels add examples for each other, a dense multi-label dataset induces a tree which in which partitions are more learnable. Thus if the label set is very sparse, unrelated labels are always forced to group together in partitions, and we will have fewer training examples per dichotomy and a poor per label classification in the end. We support these claims with experimentation later in the section 4.4.2.

Figure 4 .Figure 4 . 19 :Figure 4 . 20 :

 4419420 Figure 4.19 shows the AP scores for 10 concepts from TV2010 dataset with an average 82 positive examples per concept in the development set. All the concepts benefit from the addition of labels, even those that had an AP of 0 acquired with OVA. Fusing OVA and

Chapter 4 .Figure 4 . 21 :

 4421 Figure 4.21: TRECVID 2010 (50 concepts). Performance (MAP) comparison of proposed label partitioning to random partitioning and single label classification, for various groups of trees.

Figure 4 . 22 :

 422 Figure 4.22: TREVID 2013 (38 concepts). Performance (MAP) comparison of proposed label partitioning to random partitioning and single label classification, for various groups of trees.

A

  reasonable method is to find new training instances is to train on the provided training set and use this trained model to add the most confident predicted examples from the unlabeled set to the new training set and train the model again. This selftraining loop can be repeated until the performance on a validation set increases. Although it has worked before [105], the problem with this form of incremental learning is the potential lack of variability in the new examples added. The most confident examples added to the pool of positive instances have very little affect on the new decision boundary. Furthermore it may improve on the validation set but this could lead to over-fitting as no diverse information is added. Dealing with videos give us the liberty to have a variety of representations and for a single keyframe we can extract a number of different features. This give us the opportunity to go beyond self learning and use the diverse information to find new labeled examples for the classifiers with different descriptors, like in cotraining.

  classifications. This leads to noisy examples added to the training set and the classifiers deteriorate over time. This deterioration increases if the size of unlabeled set is large. No matter how diverse the views are, if one view always performs poorly it will adversely affect the overall performance. It is therefore important to select the best view and to select the best examples from the most confident ones for cotraining. A human annotator can be added in the cotraining loop to keep a check on some of the new examples to be added, but this shifts the paradigm towards active learning. The annotator can only be presented with a few most ambiguous examples but here we are trying to minimize (rather eliminate) the human effort, while trying to find the best new labeled examples.

  Li et al.[START_REF] Li | Co-labeling: A new multi-view learning approach for ambiguous problems[END_REF] validate the examples from different predictors before adding them to the training set for the learners. This is in fact multi-view learning in which predictions on unlabeled examples generate label candidate sets. These label sets are used in a Multiple Instance Learning (MIL) framework which identifies the best label for each example while training. They present three proposals to augment the label sets for each view improving upon each other. The first one simple uses the latest view predictions from each view while the second method uses predictions from all the previous iterations. Finally they add to the candidate label set by using classifiers with different biases for each view and adding predictions from all the different values of the bias. Authors in[START_REF] Gu | A multi-view approach to semi-supervised document classification with incremental naive bayes[END_REF] also perform multi-view learning and select the new examples by an uncertainty criterion based on KL divergence. Furthermore the new examples are added with a weight that is found using a methodology measuring confidence of the examples. Du et al. [108] identify feature splits for cotraining that satisfy the cotraining independence and sufficiency properties for tire wear classification from images. They use a set of 14 features with simple descriptors like mean and minimum values to more complex ones like DCT coefficients and KL divergence on features. They use clustering based on mutual information to identify pairs of features for cotraining and the confidence of other classifier to select unlabeled samples for the current one. [199] improve web page classification by introducing Local Cotraining. In this form of learning different local models are trained by dividing the instance space into partitions. This not only reduces the complexity of training by dividing and conquering but also gives the possibility of retraining only the dominant local models. Moreover they select different amount of unlabeled examples for each view.

[ 203 ]

 203 proposes to validate the cotraining views to see if single view learning is enough or does cotraining really bring improvement. Since the views are not always uncorrelated and compatible cotraining may lead to disastrous results if one view is weak and always feeds in wrong predictions. They use simple statistics like the number of training errors made by the view classifiers, the number of correct common predictions and classifier complexities to identify the unnecessary view. Guz at al. [204] add newly labeled examples to the training set of classifiers based on two strategies: Agreement, where only the high confident examples from both the classifiers are considered and Disagreement, where examples with high confidence scores on the other view and low scores on the target view are added to the training set of the target view. Disagreement outperforms agreement based approach for the sentence boundary classification problem.

  All this research points to one direction: find the best samples from unlabeled examples and add them to the classifier to increase classification performance iteratively. Our proposals add useful information to the annotation set of a classifier based on the cotraining principle to augment the training resources[START_REF] Niaz | Selective multi-cotraining for video concept detection[END_REF]. This is achieved by adding positive examples that are expected (or ensure to some degree) to improve the final classification result. We propose two methods to select the most complementary view among a certain available possibilities based on some statistics calculated on the validation set. We take inspiration from[START_REF] Li | Classifying tag relevance with relevant positive and negative examples[END_REF] to add the most relevant examples that were the most confusing for the classifier. Instead of negatives we focus on adding only positive examples since we already have a large number of negative examples available. Among other possibilities a relevant positive example for a classifier is the one which was previously misclassified by the same classifier. We adapt this setting in the cotraining framework where the most relevant positive examples are added to the annotation set of the target classifier based on the predictions from another classifier. This will tame the target classifier especially for the categories with few positive examples and huge number of unlabeled examples available. The classifier which identifies the largest number of misclassifications of the target learner is considered the most complementary and

Figure 5 . 1 :

 51 Figure 5.1: Selective Multi Cotraining: Identifying the best view at each iteration for retraining from a choice of views

Figure 5 . 2 :

 52 Figure 5.2: Selecting source view for Selective Multi Cotraining methods and adding new examples to the training set.

5. 5

 5 is selected for D t . So to summarize we use the positive labels to determine the value of k s but after we only used the average rank of shots ranked by D t in the first k s shots of V Ds . After determining D s we use it to re-label the training set and add k s new examples to the training set of D t . Using k s which had a precision greater than pr, it is expected that up to pr% correct labels are added to the training label set for D t . As shown in the figure 5.2, for pr = 50%, D 2 is selected with k 2 = 2 and then 2 new labels are added to the training set of D 1 with 1 unlabeled examples being labeled as positive and 1 negative's label flipped.

  dataset where the development set consists of about 800 hours of internet videos of lengths varying divided into training and validation parts. The test part contains 600 hours of slightly longer videos. Training is done on a list of 60 concepts out of which NIST has evaluated 38 for the 2013 Semantic INdexing (SIN) task.

Chapter 5 .Figure 5 . 3 :

 553 Figure 5.3: Linear fusion of every pair of descriptor for different methods

Tables 5 . 2 , 5 .

 525 3 and 5.4 show the distribution of the views selected for the two descriptors for the values of precision at 50, 60 and 70. It is clearly visible that the selected descriptor is

  Since we have a number of descriptors available and in the previous experiments we only discussed cotraining, we extend our conclusion by looking at what multi-view learning would give us with these descriptors. In multi-view learning all the available views (descriptors) are used to label examples. We perform this multi-view experiment to challenge our selective multi cotraining methods and test whether using all the information supersedes just selecting the best one.The principle of multi-view learning is very simple. All the views predict the unlabeled set and the most confident predictions are added in order to extend the learning set of the target view with diverse examples. To add to the training set of a view we consider three possibilities of finding new labeled examples: Intersection, Union and Weighted Combination. Intersection only adds the common examples out of the k most confident predictions from all the other views. Union adds all of the most confident k predictions while in Weighted Combination we again take a union of the most confident predictions but each view is allowed to add new labels proportional to its performance in the previous iteration. So if k new examples are to be added performance wise ratio of k examples are added by each view. Note that for Intersection the minimum number of new labels added is 0 when no common predictions are found among the views on the unlabeled set and the maximum number is k if all of the views agree on the predictions. For Union the minimum number is k in the case all the views have the same examples in their top k predictions and the maximum new examples added are |D| * k, where |D| is the number of views. For the third case of Weighted Combination the new examples added are always ≤ k. Here we take the percentage of top k from each view, so in the case of total disagreement on the unlabeled set k examples are added. The value of k is again decided in the two ways as for the selective multi cotraining: (i) fixed k as the percentage of positive examples for each concept in the previous training iteration and (i) precision based k s for each source descriptor, with different values of pr. Multiview Results Tables 5.6 (a) and (b) show multi-view learning results as the average for the 38 evaluated concepts on TRECVID 2013 dataset with the same SVM classifier settings as with the experiments done previously.From the results in the tables 5.6 it is evident that intersection suffers from disagreement among the views and union is affected by the large number of noisy labels added. Adding new examples based on the classifiers' performance is however the saner choice. Moreover precision based selection of k outperforms its counterpart for most of the cases as was the case with selective cotraining. Analyzing and comparing the results to selective cotraining in table 5.5 we can safely say that, for this problem of concept detection on the TRECVID-type datasets, multi-view training performs more or less similar to the selective multi cotraining.

  (a) k is fixed as the percentage of positive examples of the concept, (b) k is decided based on the precision of the concept classifier on the validation set.

4 . 2

 42 increasing the size of the list of concepts the performance of the label partitioning improves. Moreover the sections 4.3 and 4.4 show that the label space partitioning based methods generally use noticeably fewer examples with fewer classifiers to achieve the performance obtained by the single concept learning. So the presence of more information would actually benefit the system in terms of efficiency and performance.

Figure B. 2 :

 2 Figure B.2: Le pipeline de détection.

-

  Figure B.3: L'extraction des caractéristiques locales et globales.

Figure B. 4 :

 4 Figure B.4: Codage et agrégation des caractéristiques de bas niveau pour généré un descripteur resumé de l'image.

  , c'est à dire lorsque différents utilisateurs perçoivent différemment le contenu qui est similaire. Enfin, le gap sémantique est élargi par la diversité intra-classe, et cela arrive pour de nombreux concepts. Pour souligner ce problème envisager une image d'une chaise placée à l'intérieur d'un bureau et une autre image d'une chaise à l'extérieur dans une pelouse. Bien que les deux images contiennent le concept Chaise, les pixels de bas niveau ne seraient pas d'accord pour la plus grande partie des deux images. La recherche en interprétation automatique de contenu vidéo a été portée à réduire ce gap sémantique.

Figure B. 7 :••

 7 Figure B.7: Le monde visuel avec de nombreuses images, descripteurs et classificateurs.

  Compte tenu des propriétés et des éléments essentiels des systèmes de détection des concepts dans les vidéos, dans cette thèse, nous proposons un ensemble de nouvelles contributions pour augmenter la taille de la tranche coupée du monde visuel. Nous travaillons aux differentes étapes du pipeline de détection avec l'objectif d'améliorer l'analyse visuelle globale et la précision de détection.B.3.1 Pour une meilleure représentation de la vidéoNous commençons nos contributions avec le chapitre 3 dans lequel nous essayons d'améliorer les modèles de représentation de vidéo standard qui se compose de la deuxième étape du pipeline de catégorisation des vidéo présenté dans l'introduction. Plus précisément, nous améliorons le Dictionnaire Visuel ou le modèle de sac de mots Bag of Words (BOW)[8,[START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], qui attribue des points-clés (descripteurs) aux clusters spécifiques et regroupe l'ensemble des descripteurs assignés à la même cellule de clustering.La description de l'image dans le cadre de BOW est généralement confrontée à deux questions importantes. Premiere est la sélection de la taille du dictionnaire approprié et la seconde est la perte d'informations comme les caractéristiques de toutes les images dans la base d'entraînement sont considérées égales pour la construction du dictionnaire.La taille du dictionnaire est directement liée à la performance de catégorisation ainsi que de l'efficacité de recherche. Un modèle de BOW plus grand est plus discriminant mais l'efficacité d'entraînement de recherche du système est compromise avec un plus grand modèle. En Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du MondeVisuel 132 outre, lorsque la construction du modèle à partir des descripteurs nous n'incluons pas les informations sur la catégorie de l'image. Principalement dans le chapitre 3 nous proposons deux approches afin de rendre une représentation de BOW plus discriminantes et également plus courte.Notre première proposition[START_REF] Niaz | Entropy based supervised merging for visual categorization[END_REF] aborde les deux problèmes viennent d'être présentés par la construction d'un relativement petit dictionnaire d'une plus grande en utilisant de l'information de la catégorie. Puisque la construction du dictionnaire réalisée par classification non supervisée ne prend pas avantage de la relation entre les descripteurs qui viennent à partir d'images appartenant aux concepts similaire, cela agrandit l'écart sémantique. Nous utilisons explicitement les informations sur les étiquettes d'image pour construire un modèle de BOW supervisé en fusionnant des clusters voisins en utilisant le critère de minimisation de la perte de l'information. Nous améliorons également le modèle de BOW en codant la position de chacun des descripteurs à l'intérieur de la cellule de cluster quantifié en fonction de son centroide [126]. Ici un nouveau petit BOW est construit par la quantification des différences entre les descripteurs et de leurs centroides de clusters. L'intégration de ce nouveau petit descripteur, que nous apellons DBOW avec l'original pour représenter des images augmente la précision de la détection de concept dans les vidéos. En testant les méthodes nous avons vu que la capacité discriminative du modèle de sac de mots (BOW) augmente lors qu'on le construit utilisant la méthode de fusion supervisé proposé. La performance d'un dictionnaire beaucoup plus petit obtenu par fusion supervisé atteint la performance de détection des concepts avec un dictionnaire grand obtenu par k-means. L'introduction d'un nouveau descripteur DBOW basé sur la quantification des différences également rend un petit modèle de la représentation des vidéos plus discriminant. B.3.2 S'appuyant sur des données multi-étiquetés Dans le chapitre 4 nous travaillons sur un nouveau paradigme d'apprentissage dans lequel nous essayons de combiner les concepts ou les étiquettes et d'apprendre ensemble. Dans ce paradigme tous les concepts font partie de certains groupes ou des méta-concepts. Les classificateurs sont formés pour ces nouveaux groupes ou des méta-concepts et les résultats pour chaque concept sont en quelque sorte dérivés. Les Images et vidéos typiques sont multi-étiquettes dans la nature en ce que les classes (concepts) ne sont pas mutuellement exclusives. Le contenu visuel est très riche et comprend habituellement plusieurs objets ou concepts, dans un sens plus large, en une seule image ou une image-clé de vidéo. Une image de Skyline d'une ville, par exemple, contient de nombreux objets et une vidéo est généralement étiqueté avec plus d'un des concepts sémantiques. Nous utilisons cette multi-étiquetage intrinsèque avec un double objectif; (i) d'augmenter les ressources dans la base d'entraînement pour chaque étiquette (catégorie) et (ii) d'augmenter Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 133 le nombre de classificateurs par étiquette qui en fin de compte être combinés pour essayer de maximiser la performance de détection. Considérant les concepts ensemble signifie que si elles sont très similaires, ils doivent être entraînés ensemble pour augmenter les ressources de formation et en même temps ils doivent être classés les uns contre les autres afin de mettre en évidence leurs différences. Un exemple pourrait être de fusionner les exemples de la voiture et la route dans un ensemble pour en entraîner un classificateur groupe qui soit fort et en même temps organiser au moins un de ceux à tomber dans un autre groupe de sorte qu'ils peuvent être distingués les uns contre les autres pour les cas où la voiture est dans le garage par exemple, ou la route est vide ou est bondé que par des bus. Nous y proposons deux différents types d'approches. La première groupe les concepts ou les class qui sont similaires et la deuxième fait les groupe opposant avec les concepts qui sont différent. Ici pour le deuxième type les concepts dans les mêmes groupes doit être similaire. Nous proposons group-SVM [139], où nous devisons un critère pour grouper intelligemment les concepts basés sur la similarité entre eux. La similarité entre les concepts peut être calculée de différentes façons, y compris la distance entre les descripteurs, des informations de web sémantique, les règles de l'ontologie ou des relations prédéfinies entre les concepts. Nous ensuite essayons de regarder la similarité ainsi que les différences entre les concepts et les divisons dans des partitions [140]. Un classificateur est puis développé utilisant les exemples des deux partitions opposées. Nous regardons ce deuxième type d'approche dans le cadre du Error Correcting Output Codes (ECOC) où un ensemble de classificateurs sousoptimales peut atteindre les performances d'un classificateur complexe. Nous proposons un décodage de l'ECOC où nous pondérons la contribution de chaque classificateur basé sur la dynamique d'ECOC. Nous ensuite créons les ensembles d'ECOC afin de faire des prédictions plus fort. En réalisation du test, nous avons vu comment le partage explicite des étiquettes peut bénéficier de la détection de concept dans les vidéos, en particulier pour les concepts avec très peu d'exemples positifs. Nous avons vu également que les techniques sont complémentaires à la classification simple binaire quand nous avons fait la fusion tardive des classificateurs. B.3.3 Classification semi supervisé Dans cette thèse, nous nous efforçons d'améliorer la détection des concepts dans les vidéo et nous aspirons à obtenir un coup de pouce à la performance en puisant dans les vastes ressources de données non étiquetées, comme ce serait le cas pour n'importe quel type de classification. Jusqu'à ce point, nous n'avons considéré que les exemples annotés comme des instances positives et négatives pour un concept. Nous avons également essayé avec des exemples empruntés d'autres concepts qui sont similaire ou connexe et le recul de concepts qui sont différents, mais dans ces cas, les exemples d'autres concepts ont été également Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 134 annotés. Comme l'a souligné tout au long de la thèse, il ya toujours besoin de plus de données annotées pour tenter de capturer les variations avec laquelle un concept sémantique se produit. Spécifiquement pour les jeux de données TRECVID que nous avons utilisé, il ya toujours un manque d'exemples positifs pour la plupart des concepts, dont un nombre important qui est essentiel pour la performance de détection de concept. Puisque le corpus en question est annoté en partie nous pouvons toujours essayer de trouver des exemples utiles à ajouter à la base d'entraînement d'un concept pour une meilleure classification sur les exemples de test. Une méthode raisonnable pour trouver de nouvelles instances d'entraînement est de former un classificateur sur l'ensemble des exemples dans la base d'entraînement dispensée et d'utiliser ce modèle pour trouver les nouveaux exemples. Ce sont des exemples les plus confiants à la sortie du classificateur dans l'ensemble sans étiquette et ils sont ajoutés à la base d'entraînement pour ré-entraîner le classificateur. Cette selftraining boucle peut être répétée jusqu'à ce que la performance sur un ensemble de validation augmente. Bien qu'il ait travaillé avant [105], le problème avec cette forme d'apprentissage incrémental est le manque potentiel de variabilité dans les nouveaux exemples ajoutés. Les exemples les plus confiants ajoutés aux instances positives ont très peu d'effet sur la nouvelle frontière de décision. En outre, il peut améliorer sur l'ensemble de validation, mais cela pourrait conduire à un surajustement, aucune information diverse est ajouté. Quand on trait des vidéos nous avons la liberté d'avoir une variété de représentations d'une seule image-clé, nous pouvons donc extraire un certain nombre de caractéristiques différentes. Cotraining est un cas particulier d'apprentissage semi supervisé, qui ajoute d'exemples non étiquetés, et est utile lorsque les différentes représentations de données sont disponibles [191]. Comme son nom l'indique deux classificateurs formés sur chaque représentation de données sont utilisées à l'unisson pour étiqueter les données d'entraînement pour l'autre. Cela se fait de manière itérative jusqu'à ce que l'erreur de l'entraînement est suffisamment réduite ou toutes les données ont été étiquetées. La catégorisation des vidéos est une tâche difficile et les classificateurs actuels (les vus de cotraining) ne sont pas suffisantes [106, 107, 193-196], c'est à dire les prédictions les mieux classés contiennent une abondance de mal-classifications. Nos propositions dans le chapitre 5 ajoutent des informations utiles à la base d'entraînement d'un classificateur basé sur le principe de cotraining à but pour augmenter les ressources d'entraînement annotés [109]. Ce résultat est obtenu en ajoutant des exemples positifs qui devraient (ou assurer dans une certaine mesure) pour améliorer le résultat de la classification finale. Nous proposons deux méthodes pour sélectionner la vue la plus complémentaire entre certain possibilités disponibles en fonction des statistiques calculées sur la base de validation. Nous ajoutons k nouvelles annotations positives pour entraîner le classificateur cible à l'aide de la vue sélectionnée. Pour la première méthode k est fixe tandis que pour le prochain k est trouvé automatiquement par descripteur (vue). Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 135 Nous avons démontré utilisant une base de test l'efficacité de la sélection de la vue approprié à ré-étiqueter un apprenant cible pour cotraining lorsque différentes options sont disponibles. Pour chaque descripteur le meilleur descripteur complémentaire est sélectionné et le nombre d'exemples d'étiquette est automatiquement sélectionné qui devraient être correcte jusqu'à un certain pourcentage. B.4 Conclusions et Perspectives d'Avenirs Tout au long de cette thèse, nous avons examiné les moyens d'améliorer la détection de concept de la vidéo et développé des méthodes pour rendre la machine à comprendre et de mieux reconnaître le contenu visuel. Nous avons mis au point différentes méthodes pour rendre la tranche plus grande en intégrant des informations supplémentaires qui est à la fois important et utile du monde visuel lors de la construction des classificateurs pour la détection de concept de vidéo. Toutefois, le problème de la reconnaissance automatique du contenu des vidéos est une question difficile et est encore loin d'être résolu. Le nombre de catégories possibles est illimité qui entraîne un accroissement incessant des bases de données vidéos et images. En outre essayer d'accueillir toutes les variations d'un objet qui peut être présent dans une catégorie rend le problème encore plus difficile. Néanmoins la recherche progresse lentement et la vision de la machine s'améliore chaque année [12, 17, 18, 25, 26, 187].B.4.1 Les contributions clésDans ce manuscrit, nous avons apporté plusieurs contributions à résoudre le problème de la détection automatique des concepts dans des vidéos sur Internet. Nous avons étudié de près les étapes du pipeline de détection de concepts allant de l'extraction d'informations de bas niveau à partir des images brutes à la décision de haut niveau sur la présence du concept sémantique dans l'image de vidéo. Après un examen attentif et en raison de son importance dans l'état de l'art, nous avons choisi comme référence la tâche d'analyse vidéo, le TRECVID, et avons présenté l'expérimentation détaillée de nos méthodes proposées pour la tâche d'indexation sémantique. Pour conclure, nous réitérons d'abord nos principaux apports en quelques paragraphes ci-dessous. Améliorer la représentation de la vidéo Nous avons utilisé les principes de perte de l'information pour construire le Dictionnaire Visuel de manière supervisée. Après une analyse détaillée du modèle de BOW nous croyons que l'intégration des informations de catégorie tout en construisant la représentation de BOW fait en quelque sorte pour l'écart sémantique en incluant explicitement la sémantique dans le dictionnaire. Bien que cela puisse conduire à sur-apprentissage par la construction de dictionnaires qui sont spécifiques à un concept, nous avons observé une amélioration dans la performance lors de l'utilisation des informations sur la distribution de tous les concepts pour construire le dictionnaire. Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 136 Ajout de raffinement à la Représentation de la vidéo L'état de l'art nous dit que la représentation de l'histogramme désordonnée (BOW) ne tient pas compte des détails sur l'emplacement d'un point-clé à l'intérieur de la cellule de clustering de BOW. Cela a certainement attiré une certaine attention de la recherche et, par conséquent, nous avons vu des méthodes proposant d'inclure des informations spécifiques géométrique, spatiale et le point-clé que l'amélioration du pouvoir discriminant du modèle de BOW. Nous avons également porté notre attention sur ce domaine et produit une méthode pour ajouter des informations de localisation précises d'un descripteur dans la représentation de BOW. L'information supplémentaire est fusionnée dans le vecteur de BOW en termes d'un très petit vecteur qui capture la différence de chaque point-clé de son centre de cluster qui a également abouti à une meilleure capacité de discrimination du modèle de BOW par rapport à l'état de l'art. Utilisation les données multi-étiqueté: considérant la similarité entre concepts Cette contribution a contesté la pratique normale lors de la construction des modèles de classification des concepts où les données annotée sont utilisé pour construire le modèle pour ce concept. Nous avons trouvé concepts similaires qui sont censés partager certaines propriétés visuelles, regroupé leurs instances ensemble et formé les classificateurs sur l'ensemble combiné des exemples. Nous avons démontré que la performance de ces classificateurs partagés atteint la performance des classificateurs de concept seule et aussi que ce partage apport des informations complémentaires lorsqu'il est fusionné avec l'apprentissage du concept seul (l'apprentissage binaire). Nous sommes d'accord que la réalisation n'était pas aussi brillante que l'idée, mais il a été marqué par de nombreux facteurs, notamment la qualité des annotations accumulées, la méthode choisie pour trouver la similitude, le faible nombre de concepts globale et la complexité accrue du classificateur non-linéaire de groupe. Cependant, notre critère intelligente de regroupement s'est avéré être mieux que le regroupement aléatoire de concepts et le regroupement de RAKEL pour la détection de concept de vidéo TRECVID. Utilisation des données multi-étiquetés: considérant la similarité et la dissemblance entre les concepts Ici, nous avons intégré dissemblance en plus de la similarité lors du regroupement (plutôt partitionnement) l'ensemble des concepts et observé que les classificateurs partagés correspondent et parfois dépassent la performance d'apprentissage de concepts seule avec les classificateurs qui ont été formés à partir des données d'entraînement beaucoup moins que la norme. Le nombre total de classificateurs formés étaient également moins du baseline qui est important compte tenu de la complexité des méthodes d'apprentissage artificiel. Utilisation des données sans étiquette: la sélection de vue pour le Cotraining Enfin, nous avons porté notre attention sur l'immense quantité de données vidéo non étiqueté qui est facilement disponible partout sur l'internet et se compose d'une grande partie des base de donnés vidéos comme TRECVID qui sont partiellement annotées. Nous avons étudié les méthodes d'apprentissage semi-supervisé et regardé la méthode astucieuse de cotraining Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 137 d'améliorer itérativement classificateurs utilisant des données non marquées, mais a réalisé la triste réalité de sa déception pour les méthodes d'analyse visuelle, en particulier la détection du concept dans vidéos. Avec l'évolution progressive du domaine en termes de performances et d'évolutivité, l'apprentissage semi-supervisé est également gagne en importance car il nous soulage de la main pour soigneusement étiqueter chaque image-clé de vidéos non étiquetés. Nous estimons qu'il est important de trouver le plus utile de l'information entre l'inconnu et le mettre à bon usage. À cette fin, nous avons développé des méthodes pour sélectionner les vue de cotraining le plus complémentaire pour augmenter la taille de l'ensemble d'entraînement d'un classificateur avec les exemples les plus constructifs et instructifs. B.4.2 Des directions prometteuses Nous divisons les perspectives d'avenir dans le travail qui étend les contributions présentées dans cette thèse et des perspectives générales pour l'indexation et la recherche basé sur le conténu. B.4.2.1 Les perspectives d'avenir immédiat Dans le contexte de nos propositions, nous avons présenté des orientations futures à travers de la thèse, mais ici, nous tenons à souligner certains points qui pourraient conduire à un travail immédiat de l'avenir. S'adressant chapitre 3 la conception de noyau différent doit être envisagé pour le descripteur de DBOW comme il modélise l'information différent de l'histogramme de BOW. En variante, un efficace mécanisme de pondération [132] pour la DBOW pourrait être développé ainsi que de trouver la taille optimale de DBOW pour un dictionnaire visuel donné. Étant donné que chaque cellule de Voronoï de grande dimension a dynamiques distinctes une quantification sur la base de la cellule se traduirait par une représentation plus précise, mais à un coût plus élevé. Une construction DBOW différemment pour chaque concept est également une amélioration possible en faisant un histogramme DBOW séparément pour chaque concept en utilisant des descripteurs à partir d'images marquées seulement avec ce concept.Une exigence qui se fait sentir tout au long de la thèse est la nécessité d'aller plus. Puisque le monde réel est beaucoup plus grand que d'une liste de dizaines de concepts, qu'est-ce qui se passerait si une grande base de données avec beaucoup plus de concepts et un ensemble d'exemples augmenté est utilisé? Considérant l'application directe des méthodes proposées dans le chapitre 4 nous croyons que le partage entre les classes aidera toujours et avec plus de classes présentes meilleurs choix de regroupement et de partitionnement sera disponible pour augmenter la capacité d'apprendre du système. La classification de groupe ne se traduira pas bien pour le plus grand base d'entraînement, mais les méthodes de partitionnement s'adaptent. Un exemple est d'utiliser la grande liste des concepts de la tâche d'indexation sémantique full de TRECVID [18] pour générer les partitions et de former les classificateurs, Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 138 puis calcul de la performance sur la tâche light avec moins de concepts. Comme le montre l'analyse de la section 4.4.2 augmenter la taille de la liste des concepts, la performance de label partitioning s'améliore. En outre, les sections 4.3 et 4.4 montrent que les méthodes basées sur le partitionnement de l'espace de l'étiquette utilisent généralement nettement moins d'exemples avec moins de classificateurs pour atteindre les performances obtenues par l'apprentissage de chaque concept séparément. Donc la présence de plus d'informations serait effectivement bénéficier du système en termes d'efficacité et de performance. Poursuivant plus de travail dans l'apprentissage semi-supervisé est intéressant surtout pour trouver un nombre minimum de nouveaux exemples étiquetés qui seront les plus utiles. En voyant les résultats de cotraining sélectif et d'apprentissage dans le chapitre 5, nous avons vu que dans l'ensemble les différents vues ne conviennent d'un très petit degré sur la pertinence des exemples non-étiquetés. Pourtant, nous avons vu une amélioration des performances pour tous les vues de cotraining. Nous croyons que l'ajout d'une vue beaucoup plus forte (un bon descripteur avec un classificateur fort) dans le mécanisme de ce cotraining sélectif permettrait d'améliorer davantage les résultats en pointant les autres dans la bonne direction. Ici nous devrons faire des explorations dans le domaine multimodales pour bénéficier de la complémentarité des donnés très variés. Dans la thèse nous étions focalisé sur l'utilisation des descripteurs visuelles and nous avons testé les méthodes de sélection de vue pour le cotraining que pour ces descripteur visuelles. Nous admettons qu'ici il manqué de la variété car les descripteurs on étés plus ou moins de mêmes type. Mais le problème avec des base de donnés de type TRECVID est que d'autre modalités (notamment l'audio) ne fonctionnent pas bien pour la catégorisation. Pour conclure, nous devons utiliser très différents types de descripteurs avec des classificateurs forts (audio ou visuel) que ceux utilisés pour tester plus les méthodes de sélection. B.4.2.2 Les perspectives d'avenir générale Il existe toujours un écart énorme dans la recherche scientifique publiée chaque année qui s'améliore également et l'acceptation des méthodes de l'état de l'art dans l'industrie ou des applications réelles. Ce décalage entre la recherche et son application dans la vie réelle a été ressenti par de nombreux chercheurs et diverses applications sont en train d'émerger. Quelques exemples populaires pour les systèmes de récupération à base d'image sont l'IKONA de l'INRIA [208], LIRE [209], pixolu, et le système de SHIATSU [210] pour l'indexation des vidéos en fonction d'images clés. L'importance du contenu ne peut pas être nié et il est temps que les moteurs de recherche industrielle remplacent recherche par mot clé en fonction de l'indexation de contenu sur la base ou au-moins l'inclure dans leur système. Google et le moteur de recherche russe Yandex a conduit le travail de pionnier et offrent la recherche en ligne l'image basée sur le contenu. Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 139 L'évolutivité des méthodes est également important de les endre portables pour être utilisé sur les nombreux appareils portables. Les smartphones et tablettes sont maintenant équipés de caméras à haute définition et du matériel sophistiqué avec une grande puissance de traitement. Les applications telles que la reconnaissance automatique des produits, etc.

•

  Quality of annotations/ selecting the best examples The tedious work of extracting and summarizing features is of no use if representative examples are not used for concept model learning. Selecting the best examples for

  assumed a Dirichlet distribution is used to create the mixtures and used Latent Dirichlet

	categorization. The model learns the distribution of intermediate level themes and codewords
	and classifies new instances using Bayes' rule. Zhang et al. [95] further extend LDA in to
	an image decomposition model that identifies the important visual words from the image.
	Allocation (LDA) to generate the distribution of visual features and keywords. Fei Fei and
	Perona [52] use a modified LDA to model "'themes"' from image regions for natural scene

  The overall system performance is evaluated by calculating the Mean Average

	Precision (MAP) by averaging the concept APs. To understand the working and calculation
	of AP let us first look at the simple measure of Precision and Recall. We would like to know
	what is the performance of our concept model on a list of test frames. Let us say we know
	which frames in the test set are relevant and which are non-relevant, i.e. which contain the
	semantic concept and which do not, respectively. Then precision can be simply calculated
	as the ratio of the relevant documents that are predicted to be true to the total predicted
	documents:
	precision =	|{relevantdocuments} ∩ {retrieveddocuments}| |{retrieveddocuments}|
	As stated in the introduction a concept detection model predicts a new test frame and
	outputs a probability of presence of the concept in the frame. So the retrieved documents
	in the equation above mean some of the most confident predictions. More specifically the
	performance is only judged on the top R predictions with are the best predictions acquired
	from the concept model.The recall measure on the other hand finds out what percentage of
	the relevant frames have been retrieved by the model.
	recall =	|{relevantdocuments} ∩ {retrieveddocuments}| |{relevantdocuments}|

Table 3 . 1 :

 31 Mean Average Precision for 20 concepts for baseline (K-means) and three entropy minimization based mapping criteria. Min Ent: Concept distribution Entropy Minimization, Cd: Concept Dependent Entropy Minimization and Cd (Av): Average Concept Dependent Entropy Minimization. As the initial dictionary is made up using keypoints from all the images in the training set, generally the number of labeled is images is lower compared to the unlabeled images in the dataset. When merging visual words for each concept the number

	Dictionary Size K-means Min Ent	Cd	Cd (Av)
	500	0.0739
	1000 to 500	0.0795	0.0757	0.0792
	2000 to 500	0.0801	0.0758	0.0791
	4000 to 500	0.0813	0.0727	0.0775
	each concept separately.

of labeled keypoints is lower (very low for some concepts) and this overfits the merged BOW representation.

Table 3 . 2 :

 32 Mean Average Precision for 20 concepts using three alternatives of the concept distribution entropy minimization based mapping. Unlab: Inclusion of the unlabeled examples, All Space: Allow merging of non-contiguous cells and Unlab All Space: Noncontiguous merging allowed with unlabeled examples.

	Dictionary Size K-means Unlab All Space Unlab All Space
	500	0.0739
	1000 to 500	0.0803	0.0805	0.0794
	2000 to 500	0.0788	0.0795	0.0795
	4000 to 500	0.0777	0.0755	0.0780

Table 3 . 3 :

 33 Upperbounds of concept-wise improvements for dictionaries of (a) 500 visual words and (b) 1000 visual words

	(a)

Table 3 . 4 :

 34 Comparing MAP for 20 concepts using three large dictionaries vs corresponding smaller supervised dictionaries of (a) 500 and (b) 1000 visual words

			(a)
	1000	2000	4000
	k-means	500	k-means	500	k-means	500
	0.0796	0.0795	0.0814	0.0801	0.0830	0.0813
			(b)
	2000		4000		8000
	k-means 1000 k-means 1000 k-means 1000
	0.0814	0.0806	0.0830	0.0816	0.0847	0.0831

  HE sim (I, I 1 )HE sim (I, I 2 ) . . . HE sim (I, I N )]where HE sim (I, I i ) is the similarity computed by HE between images I and I

		Methods	1	2	3
		Baseline	0.0739	-	-
	Base Dictionary HE Similarity	0.0781	0.0741	0.0770
	500 Words	DBOW	0.0764	0.0796	0.0830
		DBOW weighted 0.0761	0.0810	0.0821
		Baseline	0.0796	-	-
	Base Dictionary HE Similarity	0.0815	0.0777	0.0820
	1000 Words	DBOW	0.0804	0.0831	0.0850
		DBOW weighted 0.0821	0.0845	0.0813
		Baseline	0.0814	-	-
	Base Dictionary HE Similarity	0.0737	0.0768	0.0801
	2000 Words	DBOW	0.0824	0.0835	0.0854
		DBOW weighted 0.0848 0.0868	0.0829
	Table 3.5: Mean Average Precision of all methods for 20 concepts (TRECVID 2007) for 3
		different dictionary sizes

i . N is the number of training images used for calculating the N dimensional HE similarity vector. The training images are chosen randomly form the development sets independently for the two datasets.

Table 3 .

 3

		Methods	1	2	3
		Baseline	0.0336	-	-
	Base Dictionary HE Similarity	0.0353	0.0364	0.0356
	500 Words	DBOW	0.0349	0.0359	0.0365
		DBOW weighted 0.0356	0.0352	0.0360
		Baseline	0.0368	-	-
	Base Dictionary HE Similarity	0.0406	0.0412	0.0420
	1000 Words	DBOW	0.0409	0.0413	0.0420
		DBOW weighted 0.0412	0.0413	0.0421
		Baseline	0.0403	-	-
	Base Dictionary HE Similarity	0.0447	0.0422	0.0445
	2000 Words	DBOW	0.0430	0.0419	0.0415
		DBOW weighted 0.0441 0.0459	0.0442
	Table 3.6: Mean Average Precision of all methods for 50 concepts (TRECVID 2010) for 3
		different dictionary sizes

6

shows results in similar fashion as table 3.5 and proves the effectiveness of adding the DBOW to the BOW representation. DBOW outperforms the baseline for all dictionary sizes and performs comparable to the HE similarity based method. Table

3

.6 also

  Classifiers are trained for these new groups or meta-concepts and results for each concept are somehow derived. The important questions raised here are: Can we group concepts together? Can we increase training resources for a concept by adding examples from a similar concept or a concept that shares some similarity and does it benefit? How do we define similarity between concepts? How do we differentiate two concepts or two meta-concepts? How do we acquire concept scores from the group scores? Can we decrease the eventual number of classifiers? In the sections that follow we set out to answer these questions by presenting Single Label learning vs Groups of Labels learning 4.1 Learning from Multi-label Datasets and State of the Art resources per label and to increase the number of classifiers per label which will in the end be combined to try to maximize the performance on the training set.Manually annotating the video data is a wearisome task and for many categories in the video datasets there is a lack of annotated examples. Also since manual annotations are distorted by the annotators point of view and are personalized important frames may be missed or in the worst case be wrongly annotated. But since most of the examples of a typical video dataset e.g. TRECVID are multi-labeled we can draw similarities between labels based on statistics calculated on the annotations or using some other similarity measures.The argument we present here is that since there exists many commonalities among labels different concepts can complement each other for training examples if they are considered together for training. Considering them together means that if they are very similar they should be trained together to augment training resources and simultaneously they should

	C1	C2	C3	C1	C2	C3
	C4	C5	C6	C4	C5	C6
	C7	C8	C9	C7	C8	C9
	Figure 4.2: Typical image and video datasets are multi-label in nature in that the classes are not mu-
	tually exclusive. The visual content is very rich and usually comprises multiple objects or
	concepts, in a broader sense, in a single image or a video frame. A city skyline picture,

some techniques to find similarities between concepts and combine them for training. We give detailed experimentation for each of them. We also briefly describe state of the art techniques working on multi-label datasets and multi-class classification specifically Hashing, Attribute learning, Binary Codes and Error Correcting Codes and describe the novelties in our methods. In what follows by concept we mean labels and also classes.

for example, contains many objects and any video is typically tagged with more than one semantic concepts. We use this intrinsic multi-labeling with a twofold objective; to increase the training be classified against each other in order to highlight their differences. An example could be to merge the examples of Car and Road together to train them as a strong group classifier and at the same time arrange for at least one of those to fall into another group so that they can be distinguished against each other for the cases when the car is in the garage for example or the road is empty or is crowded only by buses. Figure 4.3 differentiates the regular classification for video concept detection from joint group classification of concepts.

Moreover the group classification can be looked in two different ways: (i) where a group of concepts is trained against all other concepts, and (ii) where a group is trained against another distant group or a group with least resemblance.

  4.1.2.1 Visual Attributes[START_REF] Ferrari | Learning visual attributes[END_REF][START_REF] Farhadi | Describing objects by their attributes[END_REF][START_REF] Wang | Joint learning of visual attributes, object classes and visual saliency[END_REF] introduced attributes that describe visual objects. Attributes can be physical for example visually discriminative parts like leg and wheel, or descriptive like blue colored and striped or a property that some object might have and other do not. In image and video Third important contribution they believe attributes bring in is the ability to differentiate further among the objects of the same class, e.g. dogs with and without spots. For learning attributes they first select features that are able to distinguish the attribute within each containing class. For example to learn the attribute "'wheel"' they identify features to learn "wheel" of car, "wheel" of bike and "wheel" of cart etc.. Then all the features are use together to learn the "wheel" classifier over all the classes. Leveraging from Multi-label Data 55 where attribute-class relationships are fixed for both training and test classes and attributes are learned using the training classes only. In the second method the attributes act as a layer connecting labels from training classes to the test classes. The multiclass predictions from the training classes on the test set yields a labeling of the attributes which in turn produce a labeling of the test classes. Yang and Mori[START_REF] Wang | A discriminative latent model of object classes and attributes[END_REF] find correlations between pairs of attributes and model the attributes as continuous values. They build models for global attributes as well as class specific attributes. This allows to differentiate the attributes that are specific to each category and provide complementary information to the global attributes.Kumar et al.[START_REF] Kumar | Attribute and simile classifiers for face verification[END_REF] use 65 describable attributes for face verification which are represented by binary SVMs. Parikh and Grauman[START_REF] Parikh | Interactively building a discriminative vocabulary of nameable attributes[END_REF] discover new nameable attributes using human help that are discriminative. Russakovsky and Fei-Fei[START_REF] Russakovsky | Attribute learning in large-scale datasets[END_REF] mined relationships between object categories in the ImageNet[START_REF] Deng | ImageNet: A Large-Scale Hierarchical Image Database[END_REF] using a number of appearance-based attributes. Cai et at.[START_REF] Cai | Attribute-assisted reranking for web image retrieval[END_REF] use semantic attributes for image search re-ranking. The semantic attributes they used are histogram based visual features extracted from various image regions. Authors in

retrieval a concept or more specifically an object is composed of a set of attributes. The goal is to learn about the object's attributes that either replaces the need to learn directly an object classifier or help in identifying the object category with complementary information.

So if an image is predicted to contain so and so attributes it can point to a specific object or a class of related objects. Specifically an attribute can be represented by a binary classifier with 1 and 0 indicating whether the attribute is present in the object or not. An object can then be represented by a string or classifier outputs or a binary code. Each test image can then be associated with the closest object category based on its predicted binary code or the string of attribute classifiers output. Visual attributes have been used for object naming by being defined previously

[START_REF] Ferrari | Learning visual attributes[END_REF][START_REF] Farhadi | Describing objects by their attributes[END_REF][START_REF] Lampert | Learning to detect unseen object classes by betweenclass attribute transfer[END_REF][START_REF] Wang | Building text features for object image classification[END_REF][START_REF] Kumar | Attribute and simile classifiers for face verification[END_REF]

, however they can always be discovered on the go based on the training data

[START_REF] Berg | Automatic attribute discovery and characterization from noisy web data[END_REF][START_REF] Berg | Automatic attribute discovery and characterization from noisy web data[END_REF][START_REF] Parikh | Interactively building a discriminative vocabulary of nameable attributes[END_REF][START_REF] Rastegari | Attribute discovery via predictable discriminative binary codes[END_REF]

. Moreover they have been useful in the case where the classes in the training and test set are disjoint

[START_REF] Lampert | Learning to detect unseen object classes by betweenclass attribute transfer[END_REF][START_REF] Farhadi | Attribute-centric recognition for cross-category generalization[END_REF][START_REF] Parikh | Relative attributes[END_REF]

. Farhadi et al. [152] stress the importance of using attributes for describing objects with rare or no positive examples. So even if an object category had no examples for training a classifier, attributes can be identified for an example image explaining its properties and inferring important clues about the object's identity. Furthermore, learning objects in terms of attributes can overcome the intra class diversity. Thus if two examples of the same object (e.g. cars) are visually different they are most likey to contain similar key attributes that will help identifying the object. Lampert et al. [154] take attribute based classification a step further and perform learning for disjoint training and test datasets for object detection. They present two attribute learning methods to predict unseen test classes. The first is a straightforward mechanism Chapter 4.

1 :

 1 Input L: a set of labels 2: Output Error Correcting Output Code for each label M (l, n), l ∈ L, n ∈ {1, N }

	3: Initialize
	4: repulsion ij = 1, i, j ∈ L
	5: t ← 1
	6: repeat
	7:	∀i ∈ L repulsion i ← j∈L repulsion ij	⊲ Select seeds
	8:	Select p s.t. repulsion

p ≤ repulsion j , j ∈ L 9:

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Adult

	Concepts	1 2 3

To have an idea of how the labels are partitioned for ECOCs we present two examples in the pages below. We only show here ECOC matrices generated for the TRECVID 2010 database based on the training set.

Table 4 .

 4 1: MAP scores for various ensembles for TRECVID 2010

	Method ENS ENSw ENS-OVA ENSw-OVA
	OVA			6.91
	1	5.17	5.38	7.82	7.87
	2	3,74	4,04	7,52	7,66
	3	2.69	3.10	7.52	7.91
	4	3.39	3.92	7.67	7.66
	5	3.58	3.63	7.48	7.51
	6	4.35	4.41	8.06	8.02
	7	3.98	4.21	7.48	7.64
	8	3.70	3.75	7.47	7.59
	9	4.23	4.43	7.61	7.65
	10	4.35	4.39	8.01	8.10

Ensembles of ECOCs

We have generated 9 ensembles for the 20 ECOC generations. First 5 ensembles contain 4 trees each where λ is fixed and Θ is changed. Next 4 ensembles are generated for the four values of Θ where λ is fixed. We have also tested another ensemble of ECOC generations where we combine results from 6 best ECOCs based on the performance on the validation set. This 10'th ensemble is generated for both the TRECVID 2010 and 2013 dataset. We present the MAP score for all the concepts in the test set for the 10 ensembles (ENS), table 4.1 for TRECVID 2010 and table 4.2 for the TRECVID 2013 dataset. We also use the weighted decoding which weighs more the concept score from the partitions with fewer total concepts for an ECOC, equation 4.8. Different (ENSw) ensembles are generated for ECOCs with weighted decoding. The baseline is single concept learning or one-vs-all (OVA) classification where each concept is treated as a single labels and a classifier is learned using all the positives of only that concepts. Finally late fusion is done using the ensembles and the single label classification, ENS-OVA and ENSw-OVA.

Table 4 . 2 :

 42 MAP scores for various ensembles for TRECVID 2013

		100
		OVA	ENSw10	ENSw10-OVA
	Percentage Average Precision (log scale)	0,1 1 10
		0,01

1 :

 1 Input L: a (sub)set of labels. A node t 2: Output A division of L into left and right partitions 3: if |L| = 2 then

	4:

Table 4 .

 4

	the section 4.2 and the ECOC ensembles technique (ENSw) presented in 4.3. We take the
	best result from tables 4.1 and 4.2 for the ECOC based method where weighted decoding
	is used and an ensemble of 6 ECOC matrices is employed to generate the ranked lists. For
	the LF the scores from individual trees are maximized (LFM) for each concept as in [184],
	averaged (LFA) and fused with optimal weights (LFO). Trees are also build by partitioning
	the labels randomly dropping the visual and semantic closeness criterion, which are then
	fused by finding optimal weights (LFR). Furthermore LFO, GS and ENSw are fused with
	OVA using linear weighted fusion which further improves performance. For table 4.3 all the
	forests used contain 6 trees and for GS the best results are shown containing 100 groups for

3

shows the Mean AP (MAP) scores of the proposed label forest (LF) technique and compares them to the one-vs-all (OVA) classification, groupsvm (GS), which is presented in

Table 4 .

 4 3: MAP scores for TRECVID 2010 and 2013 Examples per Classifier Using binary dichotomies to train classifiers the number of labeled examples are considerably reduced when compared to the one-vs-all approach since the negative examples provided with the dataset are discarded and only positive examples are used for training. Table 4.4 shows the average number of examples per classifier for the two datasets, rounded to the closest

hundred, acquired from the development sets using all concepts (50 for TV2010 and 60 for TV2013). This removal of negatives comes with a cost which is visible in the performance of LFO for TV2013 where each classifier has almost 10 times few examples. However if we look in terms of number positive examples per label there is a considerable increase for both datasets. Since all the examples on either side of the dichotomy for the label tree are actually positive examples the numbers in the third column of the table 4.4

Table 4 . 4 :

 44 Average number of examples per classifier

Table 5 . 1 :

 51 Mean Average Precision for various methods for 38 evaluated concepts. Results underlined show statistically significant improvements over the baseline. NIST to train the initial classifiers. All the new labels are added either to the unlabeled examples or in some cases labels of negative examples are flipped. The results are detailed in the next few subsections.

				Selftraining				DIS				PRR
	Descriptor Baseline	pr	1	2	3	k	1	2	3	pr	1	2	3
			70	8.41	7.85	7.74	10	8.04	8.05	7.33	70	7.85	8.65	8.32
	cdsift1K	8.11	60 50	7.58 7.88	7.46 7.85	6.94 7.01	20 30	8.31 7.67	7.60 6.54	6.92 5.60	60 50	8.11 8.23	8.19 8.21	7.75 7.98
			70	8.42	8.56	8.21	10	8.60	8.72	8.34	70	8.58	8.61	8.40
	cdsift4K	8.12	60 50	8.45 8.19	8.13 8.15	8.14 7.56	20 30	8.58 8.54	8.58 7.79	7.75 6.75	60 50	8.33 8.44	8.33 8.51	8.17 8.09
			70	8.28	7.88	7.69	10	8.54	8.49	9.19	70	8.60	8.68	8.99
	cdsift10K	8.18	60 50	8.15 8.05	7.92 7.88	7.50 7.25	20 30	8.37 8.50	8.37 8.10	8.28 7.13	60 50	8.59 8.81	9.02 8.80	8.69 8.53
			70	7.87	7.76	7.50	10	7.68	7.91	8.16	70	7.59	7.77	7.40
	dsift4K	7.52	60 50	7.77 7.63	7.72 7.29	7.60 7.09	20 30	7.80 7.79	7.90 7.59	7.24 6.32	60 50	7.82 7.68	7.75 7.39	7.42 7.49
			70	7.94	7.86	7.98	10	8.31	8.27	8.40	70	8.02	7.96	7.75
	dsift10K	7.84	60 50	8.11 8.15	7.67 7.98	7.68 7.44	20 30	8.19 7.99	8.32 7.71	8.07 6.67	60 50	8.11 8.15	8.02 8.28	7.72 8.03

Table 5 . 2 :

 52 Views selected for PRR, precision = 50

			Iteration 1			Iteration 2			Iteration 3
	Descriptor cdsift dsift None cdsift dsift None cdsift dsift None
	cdsift10k	12	22	4	11	25	2	6	27	5
	dsift10k	32	2	4	32	4	2	26	6	6
			Iteration 1			Iteration 2			Iteration 3
	Descriptor cdsift dsift None cdsift dsift None cdsift dsift None
	cdsift10k	12	21	5	11	22	5	12	21	5
	dsift10k	30	4	4	27	6	5	26	6	6

Table 5 . 3 :

 53 Views selected for PRR, precision = 60

			Iteration 1			Iteration 2			Iteration 3
	Descriptor cdsift dsift None cdsift dsift None cdsift dsift None
	cdsift10k	11	19	8	11	18	9	13	17	8
	dsift10k	27	3	8	27	2	9	30	4	4

Table 5 . 4 :

 54 Views selected for PRR, precision = 70

Table 5 . 5 :

 55 Mean Average Precision for the selective multi cotraining methods with the added view based on the caffe1000 descriptor. Results underlined show statistically significant improvements over the baseline. caffe1000 as our visual descriptors and achieve a baseline score of 0.1198 for the 38 evaluated concepts on TRECVID 2013 test set, table 5.5. Even though caffe1000 is the descriptor selected most of the times (> 60%) for the other views based on visual descriptors the performance is not affected much. The best score achieved by PRR is 0.0919 for "cdsift10k", while "caffe1000" achieves a maximum of 0.121. The reason for this not-so-much increase in the performance is that though we do find the best view to re-label examples, our learners (and the descriptors) still lack the capability to capture the diversity in the examples.

Table 5 . 6 :

 56 MAP scores for multiview learning techniques for various views (descriptors):

  Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 120 automatique du contenu vidéo est loin d'être résolu avec les machines d'aujourd'hui et en utilisant les méthodes actuelles. Une grande quantité d'information est extraite des vidéos dont certains sont utilisés efficacement et intelligemment pour atteindre l'objectif en étant conscient de l'extensibilité et de la complexité du système. En comprenant l'importance de l'indexation et de la recherche par le contenu et après avoir fait des recherches approfondies sur l'état de l'art dans le domaine nous pensons que le système automatique peut être amélioré de nombreuses façons. Nous nous adressons principalement les informations qui ne sont pas utilisés lors de la construction d'un tel système, alors qu'ils sont déjà là. Cette thèse vise à améliorer la détection automatique des concepts dans les vidéos sur Internet en explorant toutes les informations disponibles et de profiter du plus bénéfique de cela. Nous la regardons comme faire une coupe pour avoir une tranche plus grande du monde visuelle. Cette grande tranche du monde visuelle est notre système de qui contient l'information plus utile et bénéfique. Cette thèse vise à améliorer la détection automatique des concepts dans les vidéos sur Internet. Nos contributions portent sur des différents niveaux dans le cadre de détection de concept et peuvent être divisés en trois parties principales. La première partie se focalise sur l'amélioration du modèle de représentation des vidéos "Bag-of-Words (BOW)" en proposant un nouveau mécanisme de construction qui utilise des étiquettes de concepts et une autre technique qui ajoute un raffinement à la signature BOW basée sur la distribution de ses éléments. Nous élaborons ensuite des méthodes pour intégrer des entités semblables Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 121 L'analyse vidéo est une version plus complexe du même problème où une série d'images entrent en jeu. Ici nous avons les relations entre les images de vidéo et les dépendances temporelles. Le coeur de traitement constitue pourtant l'analyse au niveau de l'image. Analyse d'images / vidéo automatique se compose des tâches diverses, comme la catégorisation, la recherche, la détection du copie d'une vidéo, la détection d'événements, etc., à la tête de laquelle se trouve la capacité de reconnaître le contenu visuel basé sur la sémantique de l'image. Manipulation des images et des documents vidéo pour l'analyse automatique est l'un des défis les plus difficiles dans le domaine du vision par ordinateur [1]. Cependant, la nécessité d'une reconnaissance automatique du contenu visuel n'a jamais été plus fortement ressenti avant avec l'augmentation exponentielle de la quantité de l'information visuelle sur Internet. Environ 350 millions de nouvelles photos sont mis sur Facebook chaque jour [2], et le nombre pour Flickr est de 20 à 40 millions par jour [3]. En outre Facebook possède plus d'un quart de billion de photos sur leur site web. Environs 100 heures de nouvelle vidéo est mises en ligne chaque minute sur YouTube. Le nombre d'utilisateurs qui utilisent ces services est de plus en plus par jour et ce moyen de communication en ligne maintenant correspond Pendant des années, la recherche scientifique dans le domaine de l'indexation des l'image et les vidéos a été dominée par des approches basées sur le texte ou un concept basé où les métadonnés comprenant du texte comme titre, un article ou un narratif et les étiquettes, etc. sont utilisés pour récupérer du contenu multimédia à partir de l'Internet. Pratiquement, cela est la méthode populaire ces jours-ci pour obtenir des images des moteurs de recherche populaires et regarder des vidéos sur des services de partage vidéo tels que YouTube et Dailymotion. Depuis l'aube du siècle le thème de recherche a été déplacé à comprendre directement le contenu des documents multimédia et en utilisant les informations extraites pour construire des modèles de récupération. Des descriptions textuelles associées à ou autour du Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 122 contenu multimédia sur Internet ne sont pas toujours fiables. Ce sont généralement subjective de l'uploader, sont des fois personnalisé, trompeuse, incomplète et parfois n'existent pas du tout. Annoter ailleurs une grande base de données vidéo à partir de zéro avec un effort humain manuel est laborieuse et pourrait souffrir de l'incomplétude et du préjuge. Le contenu, autrement, a toujours raison et nous pouvons compter en toute sécurité sur son authenticité, à condition de son utilisation correcte. Ces images-clés sont des représentant du contenu de la vidéo. Une vidéo est d'abord segmenté en des morceaux ou shots où un nouvel emplacement de shot peut être administré avec les métadonnées de la vidéo ou peut être détecté automatiquement [5]. Habituellement, une seule image-clé est alors extrait de chaque shot de vidéo qui est le Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 123 concept de vidéo qui commence à travailler avec les données brutes de pixel à partir d'images et attribue une probabilité d'existence d'un concept à une image de teste est très complexe et se compose de quelques étapes de traitement. Ces étapes sont détaillées dans la section suivante.

	B.2.2 Le Pipeline du détection
	Airplane Un système de la catégorisation des vidéos comprend une structure complexe d'éléments plus
	Boat/Ship ou moins séquentielles qui s'étendent sur un certain nombre de disciplines scientifiques ; y
	Bus compris le traitement du signal et de l'image, l'analyse statistique, l'extraction des données
	Cityscape et de l'apprentissage pour n'en nommer que quelques-uns. Figure B.2 présente les principaux
	Classroom éléments du pipeline où nous commençons avec des images (images-clés) en supposant que
	Singing la vidéo a déjà été segmentée en shots. La construction de différents modèles de détection
	Walking emploie plus ou moins toutes les étapes du pipline et ne diffèrent que par la fonctionnalité
	de certains des étages.
	Etape 1: L'extraction et la description des caractéristiques
	Une image dans une vidéo typique se compose de dizaines de milliers de pixels qui sont
	B.2 Introduction des chiffres simples, mais une énorme quantité d'informations 'disant les caractéristiques ou
	les traits visuels' peut être extrait à partir d'une seule image. Cette étape est à la base On dit qu'une image vaut mille mots, mais ce n'est qu'un euphémisme dans le domaine de du système de détection des concepts car ici on s'attend de capturer l'essence de ce que vision par ordinateur. En effet, pour les scientifiques de la vision, une image peut contenir l'image représente. L'homme peut, la plupart du temps, comprendre le concept représenté des millions de mots Visuel. Ces mots visuels sont construits en utilisant des divers éléments plus informatif des cadres de shots. Comme l'analyse des vidéos avec des images clés offrent dans l'image simplement en prenant un coup d'oeil. Les caractéristiques sont attendues pour visuels qui capturent des mesures importantes à partir d'images (couleur, texture, des ar-une alternative pratique et efficace pour l'analyse vidéo dans son ensemble [4-6] nous optons encapsuler cette essence de l'image pour les machines. Ils capturent la sémantique de l'image rangements spéciale, les statistiques globaux, etc. ...). Toute cette multitude d'informations Un concept sémantique ne possède pas une description fixé ou unique la plupart du est utilisé pour aider les ordinateurs à capturer la compréhension du contenu des images. Il pour travailler avec des images clés tout au long de cette thèse. pour rendre la machine comprendre la similitude ou de dissemblance entre les images.

et dissemblables pour construire des modèles de reconnaissance améliorés dans la deuxième partie. A ce stade-là, nous observons l'information potentielle que les concepts partagent et construisons des modèles pour les méta-concepts dont sont dérivés les résultats spécifiques de concepts. Cela améliore la reconnaissance des concepts qui ont peu d'exemples annotés. Enfin, nous concevons certaines méthodes d'apprentissage semi-supervisé pour bénéficier de la quantité importante de données non étiquetées. Nous proposons des techniques pour améliorer l'algorithme de cotraining avec une sélection optimale des classifieurs utilisés. s'agit d'une tentative de faire des machines à voir et comprendre le monde comme nous le faisons. Cependant cette multi-méga-octet d'information attend un succès partiel et la reconnaissance de contenu dans les images continuent d'échapper à nos machines intelligentes. l'importance de la diffusion de télévision. Cette énorme quantité de nouvelles informations et son importance pour les utilisateurs appels à des méthodes fiables et efficaces pour analyser le contenu visuel afin de développer des méthodes pour rechercher, indexer et parcourir automatiquement ces grandes bases de données. Dans cette introduction, nous commençons par expliquer la tâche de la détection de concepts dans les vidéos qui est aussi appelé l'indexation sémantique. Dans la suite nous présentons un aperçu général des principales étapes dans la réalisation de détection de concept. En outre, nous analysons les possibilités d'amélioration dans le pipeline de détection des concepts et présentons nos motivations pour travailler dans les directions sélectionnées. Nous listons à la fin nos contributions pour améliorer la performance de détection des concepts dans les vidéos.

B.2.1 La détection des concepts dans les vidéos, Indexation Sémantique

Waterfront

Figure B.1: Détection de concept dans une vidéo La détection des concepts dans les vidéos ou bien la catégorisation des vidéos vise à décrire automatiquement une vidéo avec des concepts sémantiques qui correspondent au contenu de la vidéo, figure B.1. Ces concepts sémantiques sont des descriptions de haut niveau de la vidéo qui représentent directement les informations clés présents dans le contenu. Le concept sémantique peut consister simplement d'étiquettes comme des objets ou des personnes, peut être représentée par une scène ou peut comprendre une situation avec une interaction complexe de différentes entités. La solution attribue une probabilité de présence d'un concept ou d'une étiquette dans le cadre de la vidéo (par exemple, la vidéo contient le concept "Bus" et est moins susceptible de contenir le concept "l'homme dansant"). La probabilité est assignée par un classificateur qui est fabriqué pour ce concept. Ce modèle de classification est construit pour chaque concept séparément. Le classement n'est pas fait pour chaque image de la vidéo, mais plutôt un ensemble de images-clés sont extraites pour chaque vidéo [4, 5]. temps et il existe de nombreuses variations au sein d'une classe, qu'on appelle les variations intra-classe . Le cadre de détection doit capturer cette variabilité intra-classe lors de la construction des modèles de classification pour les concepts. Le système de détection de Le système extrait un certain nombre de caractéristiques ou des traits visuels des images à l'étape 1 du cadre. Ces caractéristiques brutes sont généralement pas utilisées directement et sont plutôt transformées en une représentation spécifique de l'image agrégée à l'étape 2 de la canalisation pour un traitement ultérieur. Un certain nombre d'images annotées est généralement disponible pour apprendre le modèle qui classifie les images du concept du reste. Cela fait la 3ème étape où le modèle de classification est utilisée pour trouver des prédictions sur les images de teste qui décrire les perspectives de l'existence de ce concept dans la vidéo correspondante. La quatrième étape est une étape supplémentaire mais très utile lorsque les prédictions de différents modèles sont combinés pour unir les puissances des classificateurs individuels. Nous décrivons brièvement chacun des étages du pipeline en dessous avant la recherche dans les zones possibles pour l'amélioration des composantes du pipeline. Une image clé d'une vidéo peut être susceptible à extraction des caractéristiques globales ou peut être coupé en des petites régions avant de construire des descriptions pour chaque Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 124

  Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 125 région. Ces descripteurs sont appelés les caractéristiques visuels de l'image. Alors que caractéristiques globales capturent les qualités ou les propriétés sur l'ensemble de l'image, les caractéristiques locales travaille sur un voisinage local de l'image pour recueillir des informations pour le pixel traité. De l'autre coté les caractéristiques globales peuvent être calculées pour l'image entière ou une partie de l'image en segmentant l'image en plusieurs parties prédéfinies, puis la construction de la caractéristique pour chaque segment. Ils décrivent les propriétés globales de l'image (segment) comme la couleur, le gist ou de l'information spatiale. Caractéristiques locales peuvent être décrites pour les points prédéfinies dans les images et sont parfois extraites des points spécifiques de l'image. Ces points sont censés contenir des informations riches par rapport au reste de l'image. Il y a des méthodes qui sont utilisées pour trouver ces points critiques fondées sur un critère de maximisation. Le nombre de caractéristiques peut donc varier d'une image à l'autre si ce type d'extraction des points-clés est fait. Les statistiques locales incluent des propriétés comme les informations sur la forme et la géométrie, la structure locale, texture, etc .. Figure B.3 représente l'idée d'extraire des caractéristiques globales et locales à partir d'une image par exemple. Notez que la taille et le nombre de caractéristiques extraites sont différents pour les types de traits différents. Les différents types de caractéristiques extraites à l'étape précédente peuvent être directement utilisés pour représenter une image mais leur utilisation est prohibitive en raison de leur taille et le nombre énorme. C'est plus souvent le cas pour les descripteurs d'images locales qui sont extraites à de nombreux endroits de l'image. En outre, le nombre de ces caractéristiques extraites à partir des images pourrait être différente aussi qui interdit une représentation unifiée pour toutes les images. C'est pourquoi les caractéristiques sont généralement résumée ou agrégées en un seul vecteur de haute dimensions et de longueur fixe, figure B.4. Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 126

	Pour construire la représentation unifiée d'abord les caractéristiques de l'image sont trans-

Les caractéristiques extraites doivent être pertinentes à la tâche de détection de concept et devraient être robuste. Donc, si par exemple l'apparition de un objet change dans l'image les caractéristiques doivent toujours être en mesure de saisir l'information pertinente et nécessaire. Elles doivent également résister à la déformation, changement accidentel d'images, de variation d'illumination, le mouvement de la caméra et d'autres formes de distorsions. Une bonne connaissance du traitement de l'image est nécessaire pour construire de telles caractéristiques. Habituellement, les caractéristiques d'un type spécifique sont utilisées pour construire le reste du système, mais parfois différents types d'éléments peuvent être fusionnés pour effectuer la tâche. Plus de discussion sur l'utilisation des caractéristiques est à suivre. Etape 2: Codage et regroupment des descripteurs visuels formées ou codées dans un ensemble de valeurs. Cette projection de la fonction sur la nouvelle représentation a certaines propriétés: deux caractéristiques qui sont proches sont codés dans la même représentation, les représentations sont compacts et la plupart sont de zéro pour

  Des raffinements peuvent être faits pour inclure quelques informations utiles qui récupèrent une partie de la dynamique perdus de l'image originale. La taille de la représentation codée peut être augmentée afin de mieux distinguer les caractéristiques de l'image mais à la charge d'augmenter le temps d'entraînement et de prédiction et le risque de surapprentissage. Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 127 beaucoup de calculs est nécessaire et généralement cette étape prend la plupart du temps dans le pipeline. Ce temps d'entraînement augmente de manière linéaire avec le nombre de concepts dans la pratique comme un modèle distinct est appris pour chaque concept. Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 128 être envisagé et apparaît dans la littérature de temps en temps mais il est moins populaire en raison de la combinaison hétérogène et l'augmentation de la taille de la caractéristique combinée.

	Feature Extraction	Classifier 1
	Feature Extraction	Classifier 2	Decision Fusion
	Feature Extraction	Classifier n
	A discriminative classifier	A generative classifier
	Figure B.5: (a) Un classificateur discriminatif distinguant les exemples positifs et négatifs.
	(b) Un classificateur generatif adapté à la distribution des exemples positifs.
	Stage 4: Fusion
	Bien que le pipeline de détection concept à peu près est complété à l'étape précédente, combi-
	nant une variété d'apprenants sur différents descripteurs est toujours une option fructueuse.
	Etape 3: Modèle d'apprentissage Fusion permet aux classificateurs d'être construits pour différents types de caractéristiques
	Cette étape est le cerveau du pipeline où la machine apprend à identifier correctement des ex-de façon indépendante et seulement alors être combinés lors de la génération de la probabilité
	emples d'un concept. Cela nécessite la présence de certaines images annotées qui doivent être finale du concept. Les différents types de caractéristiques peuvent inclure d'autres modalités

et estimation de la probabilité de GMM pour générer des vecteurs Fisher

[START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]

. La nouvelle représentation ou le dictionnaire est construit en utilisant les caractéristiques de quelques images dans le base d'entraînement. Après chaque caractéristique d'image est codée, le pooling ou bien le regroupment regroupe les fonctions codées en une valeur unique pour chacun des codes. Il en résulte un vecteur de valeurs de longueur égale au nombre de représentations codées. L'opération de pooling peut varier par exemple de prenant la moyenne à prenant la valeur maximale de paramétrer l'adaptation dans le cas des vecteurs Fisher

[START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF]

. L'avantage de ces vecteurs de longueur fixe est qu'ils peuvent être directement utilisés pour construire un classificateur discriminant et comme ca un modèle pour un concept peut être construit. En outre, la taille réduite permet l'apprentissage rapide et rend la prédiction des exemples de teste aussi rapide. De l'autre côté la capacité des caractéristiques qui capturent les dynamiques de l'image à partir des endroits spécifiques est quelque peu perdu maintenant, car les caractéristiques locales sont agrégées. Les valeurs extrêmes peuvent être diminuées en raison de prendre la moyenne ou la maximisation et la structure géométrique ne peut être plus utilisé. utilisés pour l'apprentissage du modèle d'un concept sémantique. Ces images sont traitées comme des exemples positifs et sont utilisés pour former le modèle de classification pour les distinguer du reste du monde. Pour être en mesure d'atteindre ce comportement intelligent L'etat de l'art dans l'apprentissage de ce type de modèle est principalement divisé en deux parallèles: l'apprentissage discriminatif et d'apprentissage génératif, figure B.5. Les classificateurs discriminatifs apprennent à associer les exemples de la base d'entraînement x à l'étiquette de la classe y [13]. Ce résultat est obtenu par la modélisation de la probabilité conditionnelle P (y|x) directement à partir de l'exemples d'entraînements x et leurs étiquettes respectives y. D'autre part, les classificateurs Generatif apprennent la distribution de probabilité joint P (x, y). La règle de Bayes est utilisée pour trouver la probabilité conditionnelle P (y|x) de prédire l'étiquette la plus probable. Donc, pour reprendre un modèle génératif tente de savoir comment les données ont été générées, et peut être utilisé par exemple pour générer plusieurs échantillons de données, tandis que le modèle discriminant ne se soucie pas de la génération de données et apprend à classer directement. La qualité du classificateur appris dépend non seulement du type de méthode d'apprentissage utilisé et de ses paramètres, mais aussi sur le type de caractéristique sélectionnée et de la qualité des exemples positifs et négatifs acquises pour entraînement. Dans cette thèse, nous avons principalement mis l'accent sur les classificateur discriminatifs. comme l'audio et l'information textuelle avec des traits visuelles. Ce type de fusion est appelé fusion de décisions ou fusion tardive comme cela se fait au niveau de la décision, comme indiqué dans la figure B.6. Une fusion précoce au niveau des caractéristiques peut également

Final Decision Figure B.6: La fusion précoce et tardive

  Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 129• La sélection et la construction de la plus informative représentation (mi-niveau) agregéeRésumer ou agréger les caractéristiques visuelles est l'étape la plus sensible dans le pipeline comme la plupart des informations de bas niveau brut est perdu ici. La recherche dans ce domaine se concentre sur la construction des représentations de niveau intermédiaire détaillées qui capturent avec succès la sémantique de l'image.

	• Raffinement de la représentation agregée
	Recherche a également été fait pour affiner la représentation mi-niveau pour essayer de
	réduire l'écart sémantique en ajoutant par exemple contextuelle, l'information spatiale
	ou l'étiquette spécifique.
	• La fusion efficace des classificateurs
	La recherche continue pour trouver de nouvelles méthodes pour sélectionner les meilleurs
	classificateurs entre le pool des classificateurs multimodales et les combiner de la façon
	la plus efficace.
	B.2.4 Elargissant la tranche
	Avec l'énorme quantité d'informations visuelles extraites des images, les différentes méthodes
	de codage et de pooling et la variété des techniques de classification disponibles, tout n'est
	pas utilisé pour construire le système de catégorisation. Si trop des caractéristiques ou
	des paramètres sont utilisés pour former les modèles de concepts, il ya un risque de sur-
	apprentissage sur les exemples d'entraînement. De plus cela nécessiterait des tas de puissance
	et le temps de calcul car les représentations visuelles sont de grande dimension et la puissance

• Qualité des annotations / sélection des meilleurs exemples Le travail fastidieux d'extraction des caractéristiques et de les résumant n'est d'aucune utilité si des exemples représentatifs ne sont pas utilisés pour le modèle de l'apprentissage des concepts. Sélection des meilleurs exemples pour faire de l'entraînement et de les affiner avec le feedback est importante pour la performance du système. En outre, il existe toujours une grande quantité d'exemples non étiquetés à découvrir. Nouvelles instances devraient être ajoutées qui rehaussera la diversité tout en augmentant les performances. • La recherche du meilleur hyper-plan de décision Finalement le classificateur distingue entre les cas positifs et négatifs. La recherche continue à évoluer dans ce domaine a fin de construire des classificateurs généralisant bien sur des exemples de tests et avec moins de complexité. de traitement actuel limite l'utilisation de l'extravagance de cette information visuelle. Nous pouvons regarder toutes ces informations comme formant un Monde Visuel, figure B.7, et le plus souvent un système de détection de concept dans les vidéo ne prend qu'une Amélioration de la détection des concepts dans les vidéos par de plus grandes tranches du Monde Visuel 130

Acknowledgements

Acknowledgements ii

-----------------------------------------------------------------------------------------------------------------------------------------------------

Concept-wise Performance

We look at the performance of each concept for the [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]

Conclusions

Throughout this thesis we have looked at ways to improve video concept detection and developed methods to make the machine understand and recognize the visual content better.

We have devised various methods to make the slice bigger incorporating extra information which is both important and useful from the Visual World when building classifiers for video concept detection. However the problem of automatically recognizing the content of videos is a tough one and is still far from being solved. The number of possible categories is limitless which leads to ever increasing video and image datasets. In addition trying to accommodate all the variations an object can be presented in a category makes the problem even harder. Nonetheless research is slowly progressing and machine's vision is improving every year [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF][START_REF] Zhang | Image search—from thousands to billions in 20 years[END_REF][START_REF] Smeaton | Evaluation campaigns and trecvid[END_REF][START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Wang | Arista -image search to annotation on billions of web photos[END_REF][START_REF] Over | Trecvid 2013 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF].

Key Contributions

In this dissertation we have made several contributions to address the problem of automatic detection of concepts in Internet videos. We have closely studied the steps involved in the concept detection pipeline ranging from information extraction from the raw image pixels to high level decision about the presence of the semantic concept in the video frame. After careful consideration and due to its importance in the state of the art we selected the challenging benchmark TRECVID video analysis task and have presented the detailed experimentation of our proposed methods for the Semantic Indexing task. To conclude, we first reiterate our key contributions in a few paragraphs below.

Improving Video Representation

We have used information loss principles to construct the Visual Dictionary in a supervised manner. After detailed analysis of the BOW framework we believe that incorporating category information while building the BOW representation somehow makes up for the semantic gap by explicitly including the semantics into the dictionary. Though this may lead to overfitting by building dictionaries that are specific to a concept, we have observed improved Zero shot learning [START_REF] Farhadi | Describing objects by their attributes[END_REF][START_REF] Parikh | Relative attributes[END_REF][START_REF] Cissé | Learning compact class codes for fast inference in large multi class classification[END_REF] is also gaining importance as it tackles the problem of annotating new emerging concepts. The content on the internet continues to grow and so does the list of semantic concepts. Moreover the social trends have to be taken into account as something that is relevant now may not be entered into the bar of a search engine for years to come.

Recently deep learning [START_REF] Ngiam | Multimodal deep learning[END_REF] has pushed the limits of performance on understanding the semantics for concept detection using Convolutional Neural Networks [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Socher | Convolutional-Recursive Deep Learning for 3D Object Classification[END_REF]. They have the ability to automatically extract and devise meaningful features from the raw pixel values of the images. Nevertheless the deep belief networks are hard to train, require great amount of training data and in some cases special hardware. This may be regarded as another peek in the classification algorithms like Neural Networks back in the 80's but for now nothing matches their accuracy.

To conclude, it is safe to say that we are headed in the right direction to make our machines to be able to figure out the visual content. The information is there and is growing and so is the processing power of our computers. It is a matter of using it correctly with the correct methods. We also need to expand our horizons by exploring other cues that may be important in understanding the content. Making sense of the interaction among entities over the internet, the social activity, user modeling to get a glimpse of the knowledge and interests of the uploader of the material [START_REF] Niaz | Improving video concept detection using uploader model[END_REF][START_REF] Merialdo | Uploader models for video concept detection[END_REF], user's location and mutual interest among the users of content sharing services are some of the cues that could be mined to make further sense of the Visual World.