Anne Amel

Hervé, Hichem, Itheri Esma Asma

Joost Jean-Paul Julien

Laurence

Marin, Mathieu, Mehdi, Michel, Mohamed, Nicolas, Olfa, Raffi, Riadh, Saloua, Sofiene Vincent Laurent

This thesis is an attempt to improve visual object retrieval by

Manners maketh man. William of Wykeham

This thesis would not have seen the light of day without the various contributions of many people who supported me financially, morally and scientifically. First, and from the bottom of my heart, I thank my beloved parents for their continuous encouragement. The distance which separated us didn't stop them from praying for me and giving me kind advice. I also treasure the kindness of my brother and sisters and all the members of my wider family, including my nephews and nieces.

My sincere gratitude goes to my main supervisor Nozha Boujemaa,

allowing users to interact with the system. Thanks to the advances in technology, content-based image retrieval has gained greater maturity over the last few years, and there have been a number of improvements in terms of image description and large scale real-time efficient search. However, current search engines haven't yet reached the point where they are able to correctly formulate and answer a user's mental query. This is the case, for example, when we wish to retrieve images that contain an object with specific characteristics. Unfortunately, and in practice, the results returned by state-of-the-art visual concept detectors are often difficult to interpret from a user's point of view. The visual models produced by statistical machine learning methods are indeed highly dependent on the training data and might convey a different semantic than the words used to describe the originally targeted concept. This often makes users uncomfortable with these technologies since they do not get what they expected from the textual description of the trained concept. It could well be of interest, therefore, to build systems that retrieve these concepts according to human perception. Our solution lies in constructing an interactive system that allows users to define their own visual concept from a concise set of visual patches given as input. These patches-which represent the most informative clues of a given visual category-are trained beforehand with a supervised learning algorithm in a discriminative manner. Then, and in order to specialize their models, users have the possibility to send their feedback on the model itself by choosing and weighting the patches they are confident of.

The real challenge consists in how to generate concise and visually interpretable models. Our contribution relies on two points. First, in contrast to the state-of-the-art approaches that use bag-of-words, we propose embedding local visual features without any quantization, which means that each component of the high-dimensional feature vectors used to describe an image is associated to a unique and precisely localized image patch. Second, we suggest using regularization constraints in the loss function of our classifier to favor sparsity in the models produced. Sparsity is indeed preferable for concision (a reduced number of patches in the model) as well as for decreasing prediction time. To meet these objectives, we developed a multiple-instance learning scheme using a modified version of the BLasso algorithm. BLasso is a boosting-like procedure that behaves in the same way as Lasso (Least Absolute Shrinkage and Selection Operator). It efficiently regularizes the loss function with an additive L 1 -constraint by alternating between forward and backward steps at each iteration. The method we propose here is generic in the sense that it can be used with any local features or feature sets representing the content of an image region. In addition, we extended the initial version (using single image features to describe image patches) to a geometrically consistent version using feature sets as patch descriptors. Quantitatively, our method achieves similar performances as current state-of-the-art systems but outperforms them when training very small objects in highly cluttered images. Qualitatively, the interpretability allows users to construct their own model from the original set of learned patches, thus allowing for more compound semantic queries. Furthermore, we developed a GUI that allows interaction with users and we showed how results might be improved. Finally, it is worth mentioning that our method can be applied to various multimedia sources including text, audio and video documents.

Résumé : L'objectif de cette thèse est d'améliorer la recherche d'objets visuels à l'aide de l'interactivité avec l'utilisateur. Grâce aux avancés technologiques durant les dernières années, la recherche d'images par le contenu a gagné davantage en maturité. En effet, il y a eu beaucoup d'amélioration concernant la description des images et la recherche à large échelle en tempsréel. Toutefois, les moteurs de recherche actuels n'ont pas encore atteint le point où ils peuvent facilement permettre de formuler et de répondre à une requête mentale de l'utilisateur. Il s'agit ici de chercher des objets avec des caractéristiques spécifiques. En pratique, les résultats retournés par les détecteurs de concepts visuels état-de-l'art sont souvent difficiles à interpréter de point de vue utilisateur. Les modèles visuels produits sont en effet fortement liés aux données d'apprentissage et peuvent par la suite apporter une sémantique différente des mots qui ont été utilisés pour décrire le concept visuel d'origine. Par conséquent, les utilisateurs sont souvent insatisfaits de cette technologie qui ne répond pas à leurs attentes à cause de l'infidélité à l'égard de la description textuelle. Il se trouve donc judicieux de fournir un système capable de retrouver un concept selon la perception humaine. Notre solution est de construire un système intéractif permettant aux utilisateurs de définir leurs propres concepts visuels à partir de certains mots clés visuels. Ces mots clés visuels, qui en théorie représentent les mots visuels les plus informatifs liés à une catégorie d'objets, sont appris auparavant à l'aide d'un algorithme d'apprentissage supervisé et d'une manière discriminative. Par la suite, pour personnaliser davantage leurs modèles, les utilisateurs ont la possibilité d'intéragir avec le modèle en choisissant en en pondérant les mots visuels auquels ils font confiance.

Le challenge est de construire des mots clés visuels concis et interprétables. Notre contribution repose sur deux points. D'abord, contrairement aux approches existantes qui utilisent les sacs de mots, nous proposons d'employer les descripteurs locaux sans aucune quantification préalable. Par conséquent, chaque composante du vecteur multi-dimensionnel utilisé pour décrire une image est associée à un patch unique et précisément localisé dans l'image. Deuxièmement, nous proposons d'ajouter une contrainte de régularisation à la fonction de perte de notre classifieur pour favoriser la parcimonie des modèles produits. La parcimonie est en effet préférable pour sa concision (nombre de mots visuels réduits) ainsi pour sa diminution du temps de prédiction. Afin d'atteindre ces objectifs, nous avons développé une méthode d'apprentissage à instances multiples utilisant une version modifiée de l'algorithme BLasso. BLasso est une forme de boosting qui se comporte similairement au lasso (Least Absolute Shrinkage and Selection Operator). Cet algorithme régularise efficacement la fonction de perte avec une contrainte additive de type L 1 et ceci en alternant entre des itérations en avant et en arrière. La méthode proposée est générique dans le sens où elle pourrait être utilisée avec divers descripteurs locaux voire un ensemble structuré de descripteurs locaux qui décrit une région locale de l'image. Notamment, nous avons étendu la version initiale (utilisant un descripteur local unique pour chaque patch décrit) à une version géométriquement consistente qui utilise un ensemble de descripteurs locaux pour chaque patch décrit. Quantitativement, notre méthode est comparable à l'état de l'art du point de vue des performances mais elle est meilleure quand il s'agit d'apprendre des petits objets dans des images fortement encombrées. Qualitativement, l'interprétabilité permet aux utilisateurs de construire des modèles personalisés à partir des patchs appris, favorisant ainsi la définition de requêtes sémantiques composées. Par ailleurs, nous avons développé une interface graphique qui permet d'intéragir avec le système et nous avons montré comment les résultats pourraient être améliorés. Nous notons enfin que notre méthode pourrait bien être appliquée à différente sources de données multimédia comme le texte, l'audio et la vidéo.

To my dear parents viii Preface Only two things are infinite, the universe and human stupidity, and I'm not sure about the former. Albert Einstein I sometimes wonder how fast and accurate machines will be in the future. Starting from the fact that computers can already carry out arithmetic operations very much faster than a human being can, and that humans are able to quickly and precisely recognize objects (including detecting their position and segments), how fast are machines going to be able to operate once an efficient object recognition algorithm has been developed? It has recently been claimed that the human brain is much more powerful than we had supposed, and that by exploiting the capabilities of the subconscious mind, we might be able to make use of this potential in any number of ways. One example is that of reading: in addition to the traditional method, which is taught in schools, we now have speed-reading, photo-reading and quantum-reading. These last two are extremely fast techniques which, if the claims are to be believed, allow people to "read" an entire book in less than five minutes. Of course, the word "read" may not be entirely appropriate here, but it seems that people who have mastered these techniques are able to recall whatever information they are looking for. Every day, we are learning more about human mental capabilities, and even if we don't feel like we have super powers, perhaps, in fact, we do! Thus, human brain power is increasing, side by side with the power of computers. Nowadays, we talk about intercloud computing and the possibility of moving data from one cloud to another-a notion that would, literally, have been considered 'castles in the air' just a few years ago. The next ten years will undoubtedly be revolutionary regarding this topic. At the same time, researchers are constantly trying new techniques to build more "intelligent"

x machines and, in this direction, a number of achievements have been made in computer vision. Yet exploring new ways to exploit collaboration between humans and computers through interaction may well be an equally promising approach to improving computer applications and making our lives easier.

Carrying out research can sometimes be very stressful but, at the same time, it can be a lot of fun-depending on how much time a researcher has to achieve the objectives. In fact, even when the current objectives have been met, the research continues. Working on this dissertation has been the longest writing process I have ever undertaken. Dear Reader, whichever kind of reader you may be, I hope you enjoy it...

List of Tables

Introduction

As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality. Albert Einstein

1.1 General introduction H AVE you ever woken up and started naming objects: "this is a clock, and I think that might be a chair over there. Oh, wait a second, indeed it is, I can sit on it! Well done, I'm on fire today!" As ridiculous as it sounds, people don't need to make much effort to recognize objects around them. It is trivial , straightforward and sometimes unconscious. In fact, we hardly ever question our recognition system: when we look, we see, and when we see, we recognize.

Although it is as simple as breathing for us, the recognition process is by far more complicated for machines, as is reflected by the fact that, object recognition by computers has been an active area of research for almost five decades. One of the many reasons that researchers have given so much attention to object recognition and detection is that we need machines to help us perceive information that we don't necessarily capture in the first place. For instance, fingerprint, face and iris identification have gained sufficient maturity to allow the correct match to be made from large image databases. Moreover, some applications in information retrieval cannot afford to spend time and effort on manual and textual annotations due to data deluge. For other applications, annotations are just nonsense. Consider, for example, a company that wants to collect statistics about the number of times its logo appears in web images. Another good reason lies in the fact that we need to interact with computers to analyze stored images. Nowadays, it is necessary to make the machine see what a human sees. Faced with the massive amount of information produced by the media every day, we can have no choice but to rely on computers to highlight the information we are looking for.

Since the previous decade, a number of applications have emerged such as Internet search engines, adult content filtering, face detection and recognition, video archiving and management, teaching and the management of self produced content. This thesis focuses on object-based image retrieval. An object is viewed as a tangible concept such as a flag, a car, a house, etc. Unlike traditional image retrieval systems CBIR where users search for looking-like images using global descriptors, in this PhD, the goal of object retrieval is to look for object instances or objects that semantically belong to the same category. or precise objects using a local description, An object can occupy the whole image or a small region of the image. In addition, some images may only include a few parts of the whole concept. Despite these variations, search engines must be effective and time-efficient.

Object retrieval issues

Unlike object recognition which consists in understanding the image scene in depth in order to know whether or not a given object is present, object retrieval aims at ranking the images that are most likely to contain the object in question. Retrieval is performed using object models which are learned a priori or online. Moreover, an object model must truly represent all of the different possible instances of the object.

Despite diverse studies on the subject [START_REF] Sivic | [END_REF], Lowe 2004[START_REF][END_REF][START_REF] Lazebnik | [END_REF], Opelt 2006[START_REF] Philbin | [END_REF][START_REF] Joly | [END_REF][START_REF] Wu | [END_REF][START_REF] Boureau | [END_REF][START_REF] Pineda | [END_REF], current search engines have not yet reached the point where they are able to correctly formulate and answer a mental user query. The first level of difficulty arises from the fact that computers look at visual content as digits (cf. figure 1.1). The theoretical formulation and design of object models is also far from obvious. In fact, these models are complex to understand and manipulate. They usually involve optimization, kernels and different parameters that need to be properly tuned.

Object retrieval involves many challenges starting with the definition of the training dataset and the choice of the visual descriptors, moving to the way the computer learns a reliable classifier. Some researchers prefer to use a bottom-up approach, tracing the very low information in the signal and trying to interpret it so as to get powerful models. Others find that it is more intuitive to use a top-down approach [START_REF] Agin | [END_REF][START_REF] Fischler | [END_REF], Cass 1997]. They try to characterize the signal by exploiting their knowledge of what the objects are. It is, however, unclear which of the two methods is the best or whether one should try a combination of both. This raises issues about visual stimulus and how we humans recognize things [Tarr 1995]. For example, is the contextual information always useful? Does it help recognition when scale change occurs or does it make the learning error-prone in the presence of occlusion and clutter? Is it useful in the case of deformable objects? Among the most important questions in object retrieval is how we define the global similarity between two objects. This question is applicationdependent and it is also related to the choice of the descriptors, to the distance function and to the model's construction. For this purpose, statistical machine learning offers powerful tools to deal with training data. However, these tools are statistical and consequently assume that the distribution of the training set is statistically similar to the prediction dataset.

In addition to that, the generated models are somehow fixed and largely dependent on the training set which makes it difficult to apply them on various data. In addition, they might convey a different semantic than the words used to describe the originally targeted concept. Therefore, and in practice, the results returned by state-of-the-art visual concept detectors are often difficult to interpret from a user point of view. This often makes users uncomfortable with these technologies since they do not get what they expected from the textual description of the trained concept. Moreover, the generated models are likely to be abstract. This may lead to confusion among researchers when they are faced with bad prediction performances because they don't really understand where the bad results come from.

Machine learning is also concerned by the computation time but it is not that important compared with the prediction time needed for retrieval. In fact and for a wide variety of applications, learning is done offline, or online with very little training data. Apart from some professional and research fields, all user-friendly online applications need to be as fast as possible. This includes object retrieval search engines. In this perspective, exhaustive windowed searches over location and scale is inappropriate.

Contributions

The major contribution of this thesis is to make a step forward in generating interpretable models for object retrieval. In doing so, we create a link between the numerical representation of objects and our visual representation of them. The proposed idea finds its roots in text documents. Just as when browsing a text file we obtain a lot of information simply by reading keywords, this could, by analogy, be applied to images. In fact, keywords in text can give an idea about the document type, the field it covers and an overview of the material you are going to process. They are also used to query search engines. With the spread of this technology, users are getting more familiar with formulating compound queries using a few keywords. This very basic principle also works with objects. Visual keywords can indeed give a great deal of meaning to visual content. Take for instance any object you want-say a keyboard or a salamander, and think for a moment about the characteristics that make it what it is. You will soon find out that, in most cases, even without any geometric relations between the parts you named, you can still recognize that object. Figure 1.2 presents four objects in order to illustrate this principle.

It is of interest to build systems that retrieve visual objects according to human perception. Our solution lies in constructing an interactive system that allows users to define their own visual concept from a concise set of visual patches given as input. These patches-considered as visual keywords-are trained beforehand with a supervised learning algorithm in a discriminative manner. They provide users with a better understanding of what this model is able to retrieve. Then, and in order to specialize their models, users have the possibility to return their feedback on the model itself by choosing and weighting the patches they are confident of.

The real challenge consists in how to generate concise and visually interpretable keyword-based models. Our contribution relies on two points. First, in contrast to the state-of-the-art approaches that make massive use of the bag-of-words model, we propose to embed local visual features without any quantization. Therefore, each component of the high-dimensional feature vectors used to describe an image is associated to a unique and precisely localized image patch. Second, we use regularization constraints in the loss function of our classifier to emphasize the sparsity of the models produced. Sparsity is indeed preferable for concision (a reduced number of patches in the model) as well as for decreasing prediction time. To meet these objectives, we developed a multiple-instance learning scheme using a modified version of the BLasso algorithm. BLasso is a boosting-like procedure that behaves in the same way as the lasso (Least Absolute Shrinkage and Selection Operator). It efficiently regularizes the loss function with an additive L 1 -constraint by alternating between forward and backward steps at each iteration. The method we propose here is generic in the sense that it can be used with any local features or feature sets representing the content of an image region. Notably, we extended the initial version (using single image features to describe image patches) to a geometrically consistent version using feature sets as patch descriptors. Quantitatively, our method achieves similar performances as current state-of-the-art methods but outperforms them when training very small objects in highly cluttered images. Qualitatively, the interpretability allows users to understand and construct their own model from the original set of learned patches, thus allowing more compound semantic queries. Users can perform object retrieval in large image collections which may contain heterogeneous data from different sources. For this purpose, we developed a GUI (Graphical User Interface) that allowed interactivity and we showed how results might be improved. Finally, it is worth mentioning that our method can be applied to various multimedia sources including text (e.g. topic discovery), audio and video documents.

Thesis outline

This thesis is organized into three parts, each of two chapters. The first part reviews some of the past and current methods used for training object models in still images. The second part covers the contributions we propose for object retrieval. Finally, the third part presents and discusses our experiments. From basic computer vision notions to our contributions in the domain, we have striven to make each of the chapters as self-contained as possible.

The next chapter begins with a review of local image features, and gives a brief introduction to machine learning and its applications. This chapter also explains some key notions used in the computer vision domain. Chapter 3 explores the state-of-the-art in object recognition as a combination of low feature image processing and machine learning techniques.

Chapter 4 starts by explaining what motivated us to undertake this work, and then presents our new method for training interpretable models consisting of visual keywords. Chapter 5 provides an in-depth account of interactive retrieval. Here, we discuss the prediction phase and the model representation, as well as the user interface.

Chapters 6 and 7 describe our experiments. In particular, the first one judges the overall performance, while the second one shows to what extent user interactivity improves retrieval quality.

Finally, chapter 8 sets out the conclusions and suggests new ways to achieve possible improvements.

Part I Visual Objects in Still Images

Chapter 2

Computer Vision: the Basics

Honesty is the best image.

Tom Wilson

O

BJECT recognition and scene understanding in still images is a computer science discipline that analyzes the digital image content in order to learn and understand what and where the objects in the image are. It has been widely studied in the field of computer vision [Roberts 1963, Grauman 2005b, Wang 2006] for over five decades, and methods that have been proposed are continually re-visited. They are essentially based on two approaches that are not necessarily independent: low level image processing and visual model construction. From the outset of object recognition and identification, there was a specific interest in geometric modeling [Hu 1962]. Many reasons can justify the use of geometry. Geometric description is indeed powerful because of its invariance to viewpoint and illumination. In addition, it is a well developed theory and there are many man-made objects that can be described by primitive geometric elements. For years, people attempted to model objects within a theoretical framework by applying formal mathematics. The idea was to simplify object representations to standard geometric shapes so as to be able to model objects under different perspectives with projective transformations. Among the most advanced and powerful systems developed at the time were the system proposed by [Roberts 1963] and the generalized cylinders originated by [START_REF] Binford | [END_REF]]. After that, researchers abandoned the methods based on geometric simplifications because there were simply too many assumptions, and they moved on to tackle objects in real world scenes. With the development of artificial intelligence and machine learning tools, there was ever-increasing wish to explore methods based on statistical learning and appearance features. This relies upon image signal processing and basic image feature extraction and description.

Low level image processing

An image contains a large number of pixels arranged in a 2D plane. The underlying information available is very rich due to the structure generated by the points. However, the information is not located in every pixel but rather in the way they are arranged (cf. figure 4.2). Added to that, it is neither effective nor efficient-in terms of processing-to consider all the pixels. It is therefore necessary to provide some statistical measures to describe and summarize the image content. One possible form of these measures (also called image signatures) is histograms that code some of the many image characteristics. Image signatures are meant to be invariant to a number of image transformations. Now the two eternal questions are what quantity to measure and where it should be applied. Even though they appear separate, these questions are usually dependent.

In general, the three main aspects that can be measured are color, shape and texture. Color histograms were the first descriptors used to summarize the content of images [START_REF] Swain | [END_REF]]. In the literature, various descriptors were proposed to deal with the degree of invariance sought. They mainly differ in the color system used and in the feature space quantization [START_REF] Fauqueur | [END_REF], Ferecatu 2005]. Color correlograms were proposed by [Huang 1998] as an attempt to improve description by considering the spatial distribution of color. The second main aspect that can be measured is shape information. This characterizes geometrical structures in images and mostly relies on edges and image gradients [START_REF] Jain | [END_REF], Ferecatu 2005]. Besides color and shape, texture is generally used to describe what is left. It relates to small scale parts which are roughly uniform entities having approximately the same dimension and which are repeated over a region. In reality, there is no universally accepted definition for texture. Some definitions, however, include the notion of order which consists in the non-random arrangement of the elementary parts. Texture can be described by Markovian analysis and spatial frequency techniques such Fourier transform, Gabor filters and wavelets [Ferecatu 2005[START_REF] Newsam | [END_REF][START_REF] Zhu | [END_REF]].

Color, shape and texture have been identified as the main low-level aspects that describe images globally. In other words, for a given image aspect, only one compact histogram is formed from the raw information that the image contains. These global histograms are still used in today's applications [Ellouze 2010[START_REF] Hamzaoui | [END_REF][START_REF] Vinh | [END_REF] particularly in large-scale content based image retrieval where users need to search for globally similar images. In fact, global histograms carry, on the one hand, a global statistical summary of the image content and on the other hand, they are concise which makes them well suited to efficient search. Although global approaches have proved their validity in some applications, they are not capable of solving other computer vision issues since they have low-level semantic content. In fact, the quality of the low-level descriptors used in a given system is dominant over any other component. For applications like automatic image annotation and object recognition, a richer description is needed. To this end, the visual content of an image is not described by a single signature but rather by a set of local signatures that pertain to various image regions. This precise description allows us to improve the overall effectiveness since small objects need to be described separately so as to be retrieved or learned more easily. In general, local features computation goes through interest features (i.e. points, regions) localization, support region definition and feature extraction.

Interest points detection

Interest points are effective in highlighting details for various types of images. In fact, the detection process is adapted to many contexts and gives good results with different scenes. This fact makes interest points well suited to locating specific objects and more generally, they are good at searching a specific region selected from the image. These local features gained popularity and were the solution to various matching problems (image retrieval [START_REF] Schmid | [END_REF]], object recognition [START_REF] Lazebnik | [END_REF], Lowe 1999], wide baseline matching for stereo pairs [Baumberg 2000], robotics [Folsom 2004], and motion tracking [START_REF] Etiévent | Assisted Video Sequences Indexing: Motion Analysis based on Interest Points[END_REF]. Using suitable local descriptors on these points gives a summary of the image representation, and so, only a limited number of points concentrates the most relevant information in the image.

Obviously, the greater the number of points, the richer the description generated.

Detecting interest points is not a trivial task since they have to be the most relevant features in the image. In fact, there is no absolute definition of an interest point. To be considered as an interesting feature, a point has to be robust: to scaling, rotation, shift, viewpoint and illumination changes.

informative: to carry enough information of the local neighborhood so that descriptors will be discriminative.

From previous related work [START_REF] Schmid | Appariement d'images par invariants locaux de niveaux de gris[END_REF], Loupias 2000], we can classify the detectors of interest points into two categories -Detectors using contours and curvatures.

-Detectors using feature representation. We distinguish here two different approaches; the first approach is based upon the information obtained directly from the signal content and the second approach deals with theoretical models.

Many existing techniques use the first category. Some detectors extract contours first and then detect points with maximal curvature. Others use a polygonal approximation in order to locate salient points. The method by [START_REF] Asada | [END_REF]] is essentially based on plane curves. They classify curvature changes into categories while using a multiscale approach. Mokhtarian and Suomela [START_REF] Mokhtarian | [END_REF]] use inflection points. Other studies were carried out in this field [Medioni 1986[START_REF] Horaud | [END_REF][START_REF] Deriche | [END_REF]]. The two major difficulties related to this type of detectors is that on the one hand, edge extraction is very sensitive to noise and, on the other hand, the contour chaining may not be well done in cluttered scenes. This is why these methods do not seem to be the most effective. After having been largely abandoned during the 90s, they regained some interest at the beginning of this century.

In [START_REF] Mikolajczyk | [END_REF]], Mikolajczyk et al. localize salient edge points through the maximization of a scale-normalized Canny edge detector function. The scale of the interest points is determined by maximizing the Laplacian. Jurie and Schmid [JUR 2004] propose an edge-based region detector that determines salient local space convexities over space and scale.

Among the second category of detectors, the most popular is the Har-ris detector [Harris 1988]. It computes an autocorrelation function using the first derivative signal. This function locates local changes in the signal. The Harris detector is robust to image rotation, illumination changes, addition of noise and small scale variations [Schmid 2000]. This detector was improved in [START_REF] Gouet | [END_REF]] by extending the unique luminance information into a multi-channel scheme, namely color. It was proved that it is more robust to image transformations [START_REF] Gouet | [END_REF]]. This result was also confirmed in [START_REF] Stöttinger | [END_REF] where Stöttinger et al. show that using color information and boosting salient colors results in improved performance in retrieval tasks. Here, a new color scale selection method was presented and different color spaces were evaluated. [Rohr 1992] proposes an approach modelling the intersections of many lines to detect corners. His technique gives accurate detection. Also dealing with the corner concept, Smith and Brady [Smith 1997] propose the SUSAN detector. They assume that there are two different regions in the local neighborhood of a given point: one region is similar to that point (comparing illumination) and the other is different. So the interest value attributed to the pixel depends on the ratio between the two regions. After that, a threshold is applied to fix the maximum number of interest points to be retained. Here, the simplicity of the detection principle makes the running very fast compared to other detectors. Bres and Jolion [START_REF] Bres | [END_REF]] suggest a detector based on variations in the image contrast which computes the luminance difference between the local neighborhood and the background. The choice of the window size that defines the neighborhood depends on the scale of the image details, which is why a multiscale approach is used. Lowe [Lowe 1999, Lowe 2004] proposes a scale invariant detector called DoG. This detector locates keypoints using scale-space extrema in the difference-of-Gaussian function convolved with the image. It compares each point to its eight neighbors in the current image and to the nine neighbors in the scale above and below. A point is selected only if it is a maxima or a minima. The DoG operator is actually a blob detector approximating the Laplacian of the Gaussian. Yet it is faster. For more details on blob detection, the reader can refer to the work by [START_REF] Lindeberg | Feature Detection with Automatic Scale Selection[END_REF]]. The aforementioned DoG operator is invariant to four out of six parameters of an affine transform. Recently, Morel and Yu [Morel 2009] extended the previous work to achieve full affine invariance by varying the two camera axis orientation parameters (latitude and longitude). Mikolajczyk et al. [START_REF] Mikolajczyk | [END_REF]] extended the Harris detector to obtain a scale and affine invariant detector, the basic idea being to compute multiscale representation for the Harris detector. Subsequently, the algorithm selects only the points whose Laplacian is maximal over scales. This provides a scale invariant set of interest points each one characterized by its own scale. Using this scale, the affine shape of a point neighborhood is estimated, hence the affine invariance. The method described earlier was also applied by replacing the Harris detector by the Hessian detector. In the same direction, and using a fast Hessian detector, Bay et al. [START_REF] Bay | [END_REF][START_REF] Bay | [END_REF] propose a method called Speeded-Up Robust Features (SURF). The rapidity of this detector comes from the approximation of the Hessian matrix by convoluting the image with Haar wavelets, which in turn are approximated by Gaussian second order derivatives. Here, the extraction of interest point locations and scales is done at the same time by maximizing the determinant of the scale normalized Hessian matrix. Also using wavelets and curvelets, Tonnin and Gros [START_REF] Tonnin | [END_REF]] propose convolution kernels for detecting points with point and edge continuities. Still with wavelet methods, Sebe et al. [Sebe 2000[START_REF] Tian | [END_REF]] use an iterative procedure to determine the highest wavelet coefficients of the same region from coarser to fine scale. [START_REF] Kadir | Saliency, Scale and Image Description[END_REF]] proposed another type of scale-invariant detector which is basically a salient region detector. This approach finds its roots in information theory where the entropy measure is used. Salient points are indeed centers of regions with high entropy. The goal is to determine local maxima in the affine transformation space from the entropy of pixel intensity histograms whose supports are elliptical regions. Another method based on region detection was proposed in [START_REF] Matas | [END_REF]] under the name of Maximally Stable Extremal Regions (MSER). This algorithm uses a watershed segmentation that starts from local intensity extrema then connected regions grow over pixel intensity variations. A faster implementation of this algorithm was published in [START_REF] Nistér | Linear time maximally stable extremal regions[END_REF]]. It provides exactly identical results in true worst-case linear time according to the number of pixels.

Other methods simply use a random sampling on a regular grid [START_REF] Hervé | [END_REF]].

For a comparison and evaluation of some of the aforementioned detectors, the reader may refer to [Mikolajczyk 2005a, Mikolajczyk 2005b[START_REF] Salgian | [END_REF]].

Some research on interest point localization focussed on the biological aspect of detection and how interesting these points are according to human vision. In their seminal work, Loy and Zelinsky [Loy 2003] developed a fast radial symmetry for detecting the centers of small objects. Since our world is full of symmetric objects and since these objects have various sizes, Rebai et al. [START_REF] Rebai | [END_REF][START_REF] Rebai | [END_REF]] extended the previous work, first, to detect circular objects and estimate their corresponding radii, and second, to discover new types of symmetries and interest features including vanishing points. The detection of vanishing points makes it possible to infer the 3D structure from 2D images. That is why, when existing in a scene, a vanishing point belongs to the best interest points in that image, and so, it has a high visual interpretability. In this context, the approach developed by Stentiford [START_REF] Stentiford | Attention-Based Vanishing point detection[END_REF]] is based on a model of human visual attention. It computes the scarcity of a point according to its neighbors. A point that rarely occurs (i.e. unusual) will be attributed a high attention score.

Local feature descriptors

A multitude of local feature descriptors have been developed. However, there is no descriptor known to be suitable for all computer vision domains. Each proposed method is generally limited to a particular range of applications. Local descriptors are computed within support regions which pertain to interesting image primitives (i.e. interest points). Moreover, each key location helps to define one or many support regions. Some local descriptors are completely independent from the interest points detectors used. Other descriptors, however, exploit the underlying information driven by the detectors and incorporate it in the final description. Each technique provides different levels of robustness and the choice to be made is application dependent. According to existing algorithms, we can classify local descriptors as follows: distribution based descriptors, differential and moment descriptors and spatial frequency descriptors.

Distribution based descriptors are similar to global descriptors in that they are histograms that encapsulate the image characteristics related to shape and/or appearance. The only difference is the support region: rather than using the whole image, statistical measures are taken locally. For instance, Fauqueur et al. [START_REF] Fauqueur | [END_REF]] use a coarse segmentation to extract regions and apply a finer color description afterwards. The advantage of this method is to modify the color space quantization for each region (Adaptive Distribution) in order to provide a more accurate description, in contrast to the traditional color space subdivision which is useless in this case. Based on pixel intensities, [START_REF] Lazebnik | [END_REF]] proposed a histogram on point positions in the immediate neighborhood of an interest point. This representation is called spin image and was first suggested in [START_REF][END_REF]] in a 3D object context. The spin image descriptor is built from a two-dimensional histogram on the radius separating a point from the central interest point and its corresponding intensity value. Shape context is another type of a structured histogram proposed in [Belongie 2002] to describe edge distribution. This descriptor is mainly used in applications where images contain very stable edges. In fact, edges are first extracted using the Canny detector [Canny 1986] and then, locations are quantized into bins of a log-polar coordinate system. Another shape descriptor called the Directional Fragment Histogram (DFH) was suggested in [START_REF] Yahiaoui | Itheri Yahiaoui, Nicolas Hervé and Nozha Boujemaa[END_REF]], and was used to retrieve images in botanical databases. The DFH characterizes the outline of the shape of a plant by assuming that the contour is a succession of elementary components (i.e. segments), each of which has information on its length and direction. Ling and Jacobs [Ling 2005] defined a deformation invariant local descriptor named GIH (Geodesic-Intensity Histogram). Unlike usual descriptors, GIH automatically detects its support region and does not need an invariant deformation detector. The idea is to treat a deformation as a homeomorphism between two images, which means that pixel locations change but not their intensity values. They first find a deformation invariant neighborhood using geodesic distances and after that, they build a descriptor based on the intensities of sampled points. Cheng et al. [Cheng 2008] propose another local image descriptor that is robust to image deformations. They suggest using multiple support regions around an interest point and then concatenate the feature vectors computed for each support regions. These features are histograms of the gradient directions.

Lowe [Lowe 2004] proposed the SIFT descriptor (Scale Invariant Feature Transform) and he applied it on DoG points (cf. section 2.1.1). It can, however, be used with other point types. In its basic form, it is a 128-histogram storing the directions of local gradients weighted by their magnitudes. SIFT is constructed from 16 blocks (a 4 × 4 grid centered with respect to the interest point). Each block quantizes gradient directions into 8 bins. A smoothing Gaussian function is added, on the one hand, to emphasize the information situated in the immediate neighborhood of interest points, and on the other hand, to diminish errors due to side effects. To ensure robustness against rotations, the grid is adjusted according to the main direction of the interest point being described. Besides, SIFT makes a trilinear interpolation in order to eliminate errors due to the abrupt changes in the frontier of two adjacent blocks. This descriptor has been a success in the object recognition domain thanks to the rich information in gradient locations and orientations which makes it robust to small geometric distortions. Yet, the main drawback of SIFT is its relatively high dimensionality which increases the computation time in the matching step. To overcome this problem, Lowe [Lowe 2004] proposed the use of the best-bin-first method in the matching process. Ke and Sukthankar [Ke 2004a] applied PCA on the gradient image resulting in a 36dimensional descriptor called PCA-SIFT. Although faster in matching, this descriptor is slower to compute and proved to be less distinctive than the original SIFT. In order to increase the robustness and the distinctiveness of SIFT, Mikolajczyk et al. [Mikolajczyk 2005a] presented the GLOH descriptor (Gradient Location-Orientation Histogram). Here, SIFT descriptors are computed for a log-polar location grid with 3 bins in radial direction and 8 bins in angular directions for only the 2 nd and 3 rd radial bins, which results in 17 location bins. Knowing that gradient orientations are quantized into 16 bins, the resulting histogram contains 272 bins that are reduced with PCA to 128 bins. Some comparison results showed that GLOH might be more robust and distinctive than SIFT, but slower in computation. SIFT descriptors are robust to rotations, translations, scale changes and to a large range in viewpoint changes. However, they are not completely affine invariant. In order to achieve full affine invariance, Morel and Yu [Morel 2009] derived an algorithm named ASIFT. They basically keep the same mechanism for building SIFT descriptors, but, they apply them on DoG points extracted from multiple views of the same image. These views are obtained by varying longitudes and latitudes in order to simulate variations in the camera axes. Matching with ASIFT was shown to outperform the original SIFT as well as MSER [START_REF] Matas | [END_REF]], Harris-Affine and Hessian-Affine [START_REF] Mikolajczyk | [END_REF]].

Among various differential descriptors, we can cite the work by Koenderink and Doom [START_REF] Koenderink | [END_REF]] who studied the properties of local derivatives called "Local Jet". Various refinements on this basic scheme have been proposed. Gool et al. [START_REF] Gool | [END_REF]] proved that combining the components of the Local Jet can achieve invariance to photometric changes, image rotation and affine transformations. For instance, Florack et al. [Florack 1994] derived differential invariants (a kind of combination of the Local Jet components) to obtain rotation invariance. Also dealing with invariance to rotation, Freeman et al. [START_REF][END_REF]] use steerable filters. Given the Local Jet's components, these filters steer the derivatives in a particular direction. Other methods using complex linear filter were presented in [Baumberg 2000[START_REF] Schaffalitzky | Multi-view Matching for Unordered Image Sets, or "How Do I Organize My Holiday Snaps?[END_REF]]. Carneiro et al. [Carneiro 2003] proposed a phase-based local feature. It constitutes a complex representation of local image data obtained through the use of steerable quadrature filter pairs. They also used phase correlation to define a similarity measure between their local features.

Joly [Joly 2007] uses dissociated dipoles to build 20-dimensional normalized features. Dissociated dipoles are non local differential operators which are constructed from a pair of Gaussian lobes. Comparison with SIFT shows that the method performs better in web images search in terms of MAP while keeping a low matching time.

Generalized color moments can also be a good alternative to deal with some image transformations thanks to their properties of combination of shape and color information. Such moment invariants are explored in [Mindru 2003].

Finally, local descriptors can be constructed by exploiting the spatialfrequency information. To do so, one needs to transform the pixel values to some other domains by means of transformation kernels as wavelets, Fourier, DCT, Gabor, etc. Bay et al. [START_REF] Bay | [END_REF][START_REF] Bay | [END_REF] use Haar wavelets to build a 64-dimensional descriptor called SURF (i.e. Speeded Up Robust Features). In a way similar to SIFT, this descriptor splits the support window into 4 × 4 square sub-regions. Results showed that SURF outperformed all GLOH, SIFT and PCA-SIFT descriptors.

Feature matching

Local features carry two precious pieces of information: point coordinates and local descriptors. In general, each description method is associated with an adapted similarity measure that could be used to compare local signatures. Finding correct point matches is not as easy as finding the shortest distance. In fact, many interest points end up with no correct match because they are not common to the images being compared or because they simply belong to background clutter. Therefore, an appropriate matching scheme should be used.

In his paper [Lowe 2004], Lowe showed that it is not sufficient to use a predefined global threshold on the distance between two SIFT features because, on the one hand, some descriptors are more discriminative than others, and on the other hand, false matches may occur due to the high dimensionality of the feature space. Rather, he suggested-as a global threshold-the ratio between the first closest distance to the second closest distance. This formulation seems independent of the description type. To be considered as a correct match, any ratio must be less than or equal to the predefined threshold. With a PDF graph on the distance ratio, he showed that a value of 0.8 eliminated 90% of false matches while discarding 5% of correct matches. Figure 2.1 is an example of matching two images with this simple strategy using ASIFT descriptors [Morel 2009]. It demonstrates how powerful local descriptors are, even for matching deformed scenes.

In the literature, other matching methods that do not include any spatial registration have been proposed. We will refrain from discussing them here, but the interested reader may refer to [Ke 2004b, Mikolajczyk 2005b[START_REF] Boughorbel | [END_REF], Grauman 2005a[START_REF] Zhang | [END_REF].

The above-mentioned techniques use only descriptor information and discard interest point locations. Yet some of these methods add another spatial consistency step to check for local coherence. In fact, even rejecting many false matches using the previous techniques might still lead to "incorrect" matches due to the presence of other valid objects. [Lowe 2004] used, for ex- ample, the Hough transform to cluster features in pose space. When clusters of features are found to vote for the same pose of an object, the probability of the interpretation being correct is much higher than for any single feature.

Other research work [Ke 2004b[START_REF] Brown | [END_REF][START_REF] Philbin | [END_REF]] have been based upon the RANSAC (RANdom SAmple Consensus) algorithm [Fischler 1981]. Here, an affine transformation model (homography) with 6 degrees of freedom is estimated through an iterative process that selects a subset of the observed interest points as inliers and considers the rest of the points as outliers. Besides RANSAC which performs robust estimation, Joly and Buisson [START_REF] Joly | [END_REF]] add a contrario normalization of geometric consistency scores to further improve matching results.

Bag-of-features

Bag-of-features (BoF) is a technique that can be considered as an embedding of local features distribution into a single histogram. In fact, each image is described by one histogram vector which is usually high-dimensional and sparse, and whose bins are quantized positions belonging to a local featurespace. A local descriptor is then associated with the region of feature space to which it belongs. By analogy with text, the quantized positions in the featurespace are often referred to as visual words. The set of them all represents the visual vocabulary or codebook. Thus, an image descriptor characterizes the number of occurrences of the visual words contained in the image disregarding their underlying spatial structure. The term bag-of-features is sometimes referred to as bag-of-visual-words [Yang 2007, Tirilly 2008] or simply bag-ofwords [START_REF] Botterill | [END_REF][START_REF] Wu | [END_REF]] by analogy with the term used in the text retrieval community. [START_REF] Boureau | [END_REF]] presents a comprehensive study for constructing mid-level features.

BoF evolved from texton methods where textons, here, are the visual words. A texton (which is derived from the word texture) simply refers to one of the centers of clusters obtained after clustering the responses of linear texture filters. The various approaches proposed mainly differ in the local description or the clustering algorithm used. The codebook can be constructed using interest points [START_REF] Agarwal | [END_REF][START_REF][END_REF][START_REF][END_REF] or dense sampling [START_REF] Leung | [END_REF][START_REF][END_REF], Agarwal 2006]. For clustering, the two most commonly used algorithms are k-means [START_REF] Leung | [END_REF][START_REF][END_REF], Varma 2002, Bai 2010] and agglomerative clustering [START_REF] Lazebnik | [END_REF][START_REF] Pineda | [END_REF]].

Machine learning: Theory and applications

Machine Learning (ML) has grown over the past five decades alongside computer technologies. It can be defined as the process of gaining understanding through some observed data so as to construct models that help for further predictions. Scientists are still exploring new ways for computers to learn to play games, to recognize speech and visual objects and to do a variety of other tasks. This field stands at the crossroads of computer science and statistics.

Need for machine learning

ML is used when human expertise does not exist or when humans cannot formulate their expertise, as in speech recognition. It is also useful for solving problems where the optimal solution changes in time or when the solution needs to be adapted to particular cases. ML should definitely not be confused with logic, artificial intelligence and rule-based inference. It is divided into some canonical categories, each of which having its own specific problem to solve. Supervised learning techniques deal with knowledge extraction, typically, when we do know the desired outputs from the inputs and we want to generate rules to predict future cases. For instance, when we want the machine to decide whether an E-mail a spam or not or when we want it to recognize handwritten characters. Supervised learning also includes classification problems, regression and time series prediction. On the other hand, unsupervised learning is less well defined as there is no output (i.e. labels). The task consists in automatically discovering some features, representation or structure from the input data. For example, in marketing, we want the system to classify customers according to their preferences and similarities. Unsupervised learning also deals with association, clustering and density estimation. Fundamental categories of ML also include semi-supervised learning and reinforcement learning. Semi-supervised learning is proposed to alleviate the tedious task of labeling data. In fact, some of the data used is labeled and some of it is unlabeled. In reinforcement learning, there is no supervised output but delayed rewards or punishments. Here, the computer can take specific actions that affect the world and the next inputs. This kind of learning is used, for example, in game playing.

The key issue in ML is how to represent information numerically. Data can be organized as vectors, matrices, strings or as structured objects such as graphs. It is crucial to decide a priori which representation to choose because each one might bring its own problems. It is then of interest to find regularities or structure composing the data. To this end, taking the simplest hypothesis consistent with data seems a good idea. Generally speaking, applying ML algorithms in computer vision without considering the nature of images could lead to undesirable results. For example, consider the task of face registration. If we assume that the image window representing a face is just a two dimensional matrix without taking into account possible interpolation between pixels, then the system is bound to fail because not only does the face's appearance change when moving muscles, but also the task involves registration under different viewpoints, lightening conditions, etc.

Learning methods

In the computer vision domain, both supervised and unsupervised learning are considered to be the most important learning strategies. In this section, we focus on some notions used in supervised learning. For more in depth detail, the reader may refer to [START_REF] Sebe | [END_REF], Bishop 2007, Hastie 2009b].

Object models in supervised learning are built upon two main families: generative and discriminative. Generative methods try to model the prior probability p(image|object) within a maximum likelihood framework. In other words, they express the likelihood of an image given the object model. On the other hand, discriminative methods do not learn probabilistic class models but rather try to find boundaries between the categories to be learned. These boundaries, or rather the model parameters, are determined in such a way as to minimize a loss function. Because learning a mapping function is considered to be easier than estimating the prior probability, these methods can formulate complex relationships between the observed and target variables and have been shown to generally outperform generative methods in classification tasks [Mutter 2007[START_REF] Subramanya | [END_REF], Bar-Hillel 2008]. Simple methods are sometimes the most effective. Among the early powerful methods that were developed, we should mention the LDA (Linear Discriminative Analysis) approach [Fisher 1936] which finds the best linear transformation (discriminant function) that provides the optimal separation between two object categories. The use of kernel machines was suggested later. The kernel concept itself was introduced in pattern recognition by Aizerman [START_REF] Aizerman | [END_REF]]. The success of sparse kernel machines has been observed during recent years, mostly with the use of support vector machines (SVM).

A typical problem that may occur during learning is overfitting. This simply means that the relationships, which the algorithm suppose to be statistically significant, are noise. Consequently, the generated model will not be able to generalize to deal with similar data. To alleviate this problem, regularization is needed. Tibshirani [Tibshirani 1996] proposed an additive constraint with the L 1 -norm to shrink the model and favor sparsity. He termed the method lasso. Subsequent work [Meinshausen 2009[START_REF] Xu | [END_REF]] has shown the robustness properties and sparsity characteristics of lasso. In addition to these results, Xu et al. [START_REF] Xu | [END_REF]] proved a theorem stating that sparsity and algorithmic stability contradict each other. Therefore, lasso is not stable. We should emphasize here that stability differs from robustness. Stability means that when slightly varying the training data or the regularization amount, the algorithm will output a slightly different (i.e. similar) model. On the other hand, robustness means that applying such variations would not affect the prediction performance on test data (regardless of whether the model is slightly or completely altered). In reality, this result-proved by Xu et al.was somehow revealed by Meinshausen and Büehlmann in their paper 'stability selection' [Meinshausen 2009]. They addressed the problem of determining the proper amount of regularization for variable selection in high-dimensional data when the number of variables significantly outnumbers the number of observations-which is generally the case with local image features.

Variable selection, also known as feature selection or feature reduction, is a common ML task required when the number of variables is very large. It is achieved in order to highlight the most reliable data and could be done as a preprocessing stage in order to improve the performance of a learning algorithm. Some methods, however, can identify interesting features at the same time as training classifiers.

Supervised learning mostly relies on labeled data. Some problems in real life cannot provide exact information about the true labels either because it is technically impossible or because collecting labels demands a great deal of effort. In order to overcome this issue, Dietterich et al. [START_REF] Dietterich | [END_REF]] came up with a multiple-instance learning (MIL) scheme while investigating drug activity prediction. Since then, MIL has enjoyed success in many applications including image retrieval and categorization [START_REF] Maron | [END_REF], Andrews 2003, Zhou 2006, Li 2009[START_REF] Fu | [END_REF]. Rather than labeling each training sample, MIL only labels a group of samples (also instances) known as bags. A bag is positive if and only if it contains at least one positive instance and the task consists in predicting the labels of unseen bags.

Chapter 3

Object Recognition: the State-of-the-Art

Art is the imposing of a pattern on experience, and our aesthetic enjoyment is recognition of the pattern. Alfred North Whitehead I N different applications, there is a need to bring together objects that share the same characteristics or function. We talk about categorical object recognition or object categorization. A category can encompass objects that have no boundaries, objects that are purely conceptual but which are still tangible. In this chapter, we give key-notions on how objects are defined and dealt with in the literature. We provide an overview on how specific tasks are tackled and we explore some of the-state-of-the-art methods used for modeling and learning.

3.1 Objects: What and Where?

Object types

Depending on the far-end application, the definition of the concept to recognize may vary. Objects can be classified into bounded/unbounded, rigid/flexible. Bounded and rigid objects can have various shapes (e.g. car, chair), a fixed shape with different appearances (e.g. rugby ball, CD), or a fixed shape and appearance (e.g. landmark). On the other hand, bounded and flexible objects have various appearances (e.g. an open eye vs. a closed eye).

Dealing with objects that have a limited volume is still a formidable challenge. These are the objects that have been the most studied in the literature.

The easiest categories might be those that define rigid objects with a fixed shape. Yet, even with a shape that doesn't vary much from one instance to another, a deformable object easily adds another level of difficulty either by changing the pose, appearance or point of view (e.g. flag, face). Having a rigid object with different instances is another example that makes categorization difficult. The task can be even trickier when recognizing objects with different shapes and that can be easily deformed (e.g. carpet, handwritten digits).

Dealing with rigid objects, it is sufficient to use a robust interest point detector and descriptor coupled with an efficient matching algorithm. For example, object recognition performed in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], Morel 2009] uses a similarity matching algorithm. First, each keypoint is associated with its nearest candidate match (the closest neighbor according to the Euclidean distance). Then, a comparison to the second closest distance is performed. Applying a threshold on the ratio defined by the first closest distance over the second closest distance turns out to be a very useful means to discard many inconsistent matches. In addition, this ratio threshold is beneficial because it facilitates, in terms of efficiency, further processing steps. In fact, and for more accurate object recognition, a Hough transform is used in order to cluster the keypoints with same characteristics. After identifying at least three entries in a bin, an affine verification procedure is performed for additional geometric consistency.

Categorizing unbounded objects is certainly difficult. For example, scene categorization has been of interest in many research studies [START_REF] Lazebnik | [END_REF][START_REF] Jégou | [END_REF][START_REF] Gemert | [END_REF]]. Scenes can be classified into indoor/outdoor, day/night, urban/forest, etc. More specific topics can also be applied (e.g. class-room, bedroom). Recently, Xiao et al. [START_REF][END_REF]] have developed a database of 899 categories and 130, 519 images that is used for scene recognition. They gave it the name SUN (Scene UNderstanding). Within this same context, we can talk about event search. In fact, object classes may consist of specific events. Each event is defined by a place and a limited period of time (e.g. music concert, wedding, football match). Although searching for events is not well covered in the literature, it is an area of interest particularly for users who want to collect images for the events they pertain to.

Challenges

Object recognition tasks involve detection, classification and retrieval. Since our work focuses mostly on classification and retrieval, we just give a brief overview on detection, moving on after that to present some state-ofthe-art methods on the subject.

Detection

Object detection aims at identifying the position of any instance representing the object class. In other words, detection must provide answers to the two following questions: How many objects are there? Where are they? Detection may be achieved by indicating a bounding box in which the object is localized. For example, Laptev [START_REF] Laptev | Improvements of object detection using boosted histograms[END_REF]] uses a rectangular window search over positions and scales. Then, he clusters positively classified sub-windows in order to eliminate multiple detection. A similar approach based on an exhaustive scan of rectangular features is used by Viola and Jones [Viola 2004] for face detection. Osadchy et al. [Osadchy 2007] suggest a more precise delimitation and representation of faces by estimating relative pose. They used an oriented box as well as two axes: a "vertical" axis passing through the nose and a "horizontal" axis showing the position of the eyes. On the other hand, Tuzel et al. [START_REF] Tuzel | Pedestrian Detection via Classification on Riemannian Manifolds[END_REF]] use ellipses to represent detected pedestrians.

Since a bounding box might omit a part of the object or might be imprecise by including a great deal of context around the object, it is considered to be the easiest way for localization. A better way is to specify a segmented region which defines the boundaries of the object itself. For this purpose, Marszalek and Schmid [Marsza lek 2007] make use of shape masks to accurately locate object instances by defining outlines. Shape masks are considered to be a natural generalization of discrete binary segmentation masks.

Forssén and Moe [START_REF] Forssén | Autonomous Learning of Object Appearances using Colour Contour Frames[END_REF]] learn the appearance of objects. The goal is to allow robots to detect objects with little or no texture. In this case, detection results were evaluated by drawing a small symbol on the object's center. In order to locate an object, another technique consists in labeling the local image features (interest points) [Ulusoy 2006]. This method can be viewed as a classification of each local feature.

Classification and retrieval

Classification, also called object categorization, consists in classifying images into categories by giving them the labels of the objects they contain. It is only based on the presence or absence of the object. For each object category, images are attributed the value 1 or 0 depending on whether or not they contain the object.

Following the same idea, we can perform object retrieval. Users can query the system to retrieve images which contain the objects they are looking for. This should be based upon an efficient and fast prediction to ensure a reasonable response time, particularly when dealing with large databases and/or complex models.

Nowak and Jurie [START_REF] Nowak | [END_REF]] propose a framework where the notion of modeling an object category is absent. They compare never seen objects.

The training set comprises pairs of images all weakly labeled as being same or different. These are the only clues that are available for the learning algorithm. Given two test images, the task consists in labeling this pair of images as "same" if they contain the same object and "different" otherwise. The method is based on learning a similarity measure from equivalence constraints. The algorithm aims to learn the similarity between small patches as well as to characterize their local differences. This method is practical to tell whether two faces are different or not even under different appearance. It can also be used to cluster a bunch of images according to their similarity. On the other hand, all the experiments shown used images containing objects that mostly cover the whole image area and, it is unclear to what extent this method is still applicable when objects become smaller (with respect to the image size).

Although they represent an unstructured set of data, bag-of-features methods turn out to be very discriminant and they are considered to be effective tools for classification. The main choices that have to be made are about how to choose interesting local image regions, how to describe them and how to quantize the feature space. Several authors have attempted to use specific interest operators to extract image local features. However, Nowak et al. [START_REF] Nowak | [END_REF]] demonstrated an increase in performance when using a random sampling. They added that random sampling gives better classifiers and that interest operators are not suitable because they cannot provide enough patches. The more patches used, the more robust the classifiers will be. The reader can refer to [START_REF] Nowak | [END_REF]] and the references therein for a more in depth explanation.

Visual words carry much more information than textual words, hence more structure is needed. Moreover, with a bag-of-features method, the choice of the words is abstracted to the system. In this direction, a few attempts have been made to introduce some spatial consistency to bag-of-features. Philbin et al. [START_REF] Philbin | [END_REF]], for example, perform object retrieval by introducing a fast spatial matching. By object, they mean a query region selected by the user. After retrieving images using a bag-of-features scheme, they add a spatial verification stage and only re-rank the top-ranked results. In fact, they estimate a transformation between the query region and each target image using spatial constraints (based on how well feature locations are predicted by the estimated transformation) and apply the LO-RANSAC [Chum 2004] algorithm afterwards. On the other hand, Lazebnik et al. [START_REF] Lazebnik | [END_REF]] proposed a spatial pyramid matching in order to encode and bring more spatial structure to the unordered words. They partition the image into sub-regions at different levels, from coarse to fine. Their idea has its roots in the pyramid matching kernel [Grauman 2005b]. PMK represents a weighted sum of histogram intersections and the idea by [START_REF] Lazebnik | [END_REF]] consists in representing the image with multiple histograms each corresponding to a geometric location (i.e. image sub-region). Furthermore, the weights in PMK are computed so as to penalize matches found in larger cells because they involve increasingly dissimilar features. Yang et al. [START_REF][END_REF]] state that bag-of-features and spatial pyramid matching (SPM) should be used together with a particular type of non-linear Mercer kernels in order to obtain good performance. They added that this result has been empirically proved. Vedaldi et al. [START_REF] Vedaldi | [END_REF]] use dense and sparse visual words at different levels of spatial organization. Another work by [START_REF] Philbin | [END_REF]] uses an affine homography as a geometric relation built into a generative latent model. The method is an extension to LDA and was named gLDA (Geometric Latent Dirichlet Allocation). It is able to compute a matching score of the spatial consistency as well as an approximation to the transformation between two spatially distributed sets of bag-of-features.

Due to their simplicity and computational rapidity, using approaches that don't model relationships between parts of the object is appealing. For instance, Opelt et al. [Opelt 2006] propose training the classifier from weakly labeled images. The object class model is composed of a weighted sum of independent local features whose weights represent a degree of confidence in their reliability. Moreover, each local feature is characterized by a discriminative radius. Lin et al. [liu 2007] build an MRF graphical model to learn various local ensemble kernels and use an SVM classifier afterwards. Torresani et al. [START_REF] Torresani | [END_REF]] introduce a new representation called classemes to allow novel categories to be recognized. A classeme is a base classifier describing either an object similar to the category to be learned or an object which is often present in that category; the idea is to combine all these base classifiers. Frome et al. [Frome 2007] classify visual categories by learning an image-to-image distance function. The objective is to obtain smaller distances between images from the same category than any two images belonging to different categories. The distance function defined is a sum of weighted distances where each distance corresponds to a local patch belonging to the query image. Furthermore, the weights are attributed in a way to emphasize "relevant" features. Seinstra and Geusebroek [START_REF] Seinstra | [END_REF]] address the problem of recognizing objects by robots. They compute 37 local color-based histogram invariants on a hexagonal grid and object recognition is achieved by matching these histograms.

Geometric approaches consider objects as being an association of a set of parts whose relative positions are constrained by the model. Zha et al. [Zha 2008] build a model from a multi-label framework where they jointly learn connections between regions and their corresponding labels. Their probabilistic model is the sum of four potential functions. It formulates the association between a given region and its label, the coherence between regions and image labels, the spatial relation between region labels as well as the correlations of image labels. Here, the spatial relationships only take into account the neighborhood as a constraint and model each pair of labels separately. The potential function is a weighted sum of these pair-of-labels power indicators. [START_REF][END_REF]] model objects as a random constellation of P parts. A histogram (of length P ) is then constructed in order to associate each part to the number of its relative instances present in the image. The value 0 indicates that a part is missing. Moreover, these parts are modeled with a probabilistic representation that takes into account shape (Relationships between parts are represented by a shape model.), appearance, occlusion and relative scale. Epshtein and Ullman [START_REF] Epshtein | Semantic Hierarchies for Recognizing Objects and Parts. Computer Vision and Pattern Recognition[END_REF]] construct a probabilistic graphical model which encapsulates various appearances of the object in a semantic hierarchy. The graph is composed of hidden nodes that correspond to object parts. Each hidden node contains two variables specifying the appearance of the object part and the location in the image. [START_REF] Bar | Efficient Learning of Relational Object Class Models[END_REF] describe an efficient method to model object parts taking into account appearance, location, and scale as well as relations between the parts. These relations are related to one another through a hidden center. Li and Zhang [Li 2010] propose a method which is considered to be an improvement to traditional LDA. Unlike [START_REF] Philbin | [END_REF]], their method abandons the notion of bag-of-features and learns directly from SIFT descriptors.

The training takes into account the location coordinates of image features and employs prior spatial configurations and affine transformations to characterize spatial information. Amores et al. [Amores 2007] represent an image as a constellation of generalized correlograms (GC) that correspond to image parts together with their relative contexts. They use various interest operators to determine the location where to compute the GCs in order not to miss any informative location. A GC estimates a joint distribution of local and relational properties. Apart from characterizing spatial relations, their representation of correlograms also takes into account relations between local parts of the object.

Evaluation

Metrics

Various metrics have been developed to compare and judge the effectiveness of existing methods. For classification tasks, the basic measures used to evaluate and to derive, on a second level, other metrics are true positives, false positives, true negatives and false negatives. A true positive is equivalent to a hit while a true negative means a correctly rejected hypothesis. On the other hand, a false negative is equivalent to a miss (i.e. a falsely accepted negative hypothesis) and a false positive is equivalent to a false alarm. Many researchers plot ROC (Receiver Operating Characteristic) curves to report their results. The ROC curve is drawn from true positives as a function of false positives and the area under this curve is interpreted as the probability that a randomly chosen positive image will be ranked higher than a randomly chosen negative image.

For retrieval applications, the most common measure is precision. It is defined as the ratio of the number of correct answers to the number of the documents retrieved. Unless equal to one, this measure doesn't specify the order of good documents with respect to all the retrieved documents. Yet the notion of order is very important in retrieval. One way to encounter this problem is to define a precision at a cut-off level, so that, for instance, we can evaluate the precision for the first 5 documents, then for the first 10 documents, etc. On the other hand, the precision value only evaluates the documents retrieved and doesn't give any clue about the relevant documents that should have been retrieved and were not. Here comes another measure called recall which specifies the proportion of the relevant documents. It is defined as the ratio of the number of correct answers to the number of all the relevant documents in the database. Obviously, returning all the database documents results in a recall of 1, which is why, recall must be jointly used with precision to give a clear idea about the performance. To this end, a precision-recall curve can be derived (precision as a function of recall). The closer the area under the curve to one, the better the system is. But more generally, and for two equal areas, the system is better when the precision is higher at an early stage so that good results are shown in the first place.

Although a curve is more informative than any summarizing number, in many cases, it is tedious and time-consuming to compare several performances based on curves. In addition, the evaluation process moves from being quantitative to qualitative. For this reason, it is preferable to rely on one numerical measure to make it possible to rank different algorithms and/or different runs. Consequently, we can think of using the value of the area under the precisionrecall curve for the matter. This area can be approximated by the average precision measure (AP for short). The AP favors returning relevant docu-ments first while keeping some knowledge on recall. In fact, it is an average over precisions computed at each level where a relevant document is found. This means that when a relevant document is retrieved after many bad documents, the precision at this level is low and would consequently affect the final measure.

Databases and benchmarks

Databases are an essential ingredient to object recognition research. In fact, they play a key role in defining user needs as well as in evaluating existing algorithms. Consequently, appropriate datasets are required. To some extent, certain datasets are qualified as easy and inappropriate for a given challenge, while at the same time, they could represent a good means of evaluation for other tasks. That is why, different datasets may be complementary to one another.

Each far-end application is designed to meet one or many objectives (Video surveillance in a public street, video surveillance in a supermarket, detection of faces in a camera, copyright fraud detection, pedestrian detection when driving a car, retrieval of a specific image region, etc.). Some of these applications focus on speed rather than precision. Other applications may need to minimize false positives or rather, they may not tolerate false negatives. Since each application has its own specific requirements, algorithms should be compared depending on the goal they were designed to. Unfortunately, rare are the databases that are task specific except of some databases which were constructed within benchmarks 1 2 . Some researchers prefer to build their own dataset. For example, Fergus et al. [START_REF][END_REF]] use images directly provided from search engines to build their own training and test set.

Object characterization

Characterizing an object class is equivalent to making the right choice for description, model types, learning algorithms and similarity measures to name but a few. One of the important decisions is to choose an appropriate description. The next section summarizes some types of description used in object recognition.

Choosing a good description

Image descriptors are the raw material used to train, build models and predict on unseen images. It is usually necessary to proceed with a local description since objects may be small in size with respect to the image size. Using a local description allows us to capture subtle information in various image locations. A global description would be equivalent to a vague measure of image characteristics. Nonetheless, the question where to measure this information is no by means obvious and it is certainly task-related. The reader may refer to [START_REF] Salgian | [END_REF]] for a brief comparison on local descriptors applied to object recognition.

Interest points are usually more abundant in real images than straight edges and several research studies have used them as the basic image features. [Amores 2007] extract edges and corners (i.e. contour points) and then sample this set by keeping the points that have a maximum distance from each other. After that, and for each interest point, they use a correlogram representation to measure the distribution of neighboring points according to their positions and local properties. A difference-of-Gaussian interest point detector, alongside with the SIFT descriptor [Lowe 2004], are used in [Ulusoy 2006[START_REF] Jégou | [END_REF], Agarwal 2006, liu 2007, Li 2010]. Harris-Laplace and Affine-Hessian [START_REF] Mikolajczyk | [END_REF]] are respectively used in [Ulusoy 2006] and [START_REF] Jégou | [END_REF]]. [START_REF] Bouchard | [END_REF]] use the Harris detector [Harris 1988] and then apply an agglomerative clustering over 25 × 25 patches. Similarly, [START_REF] Weber | [END_REF]] use the Föstner detector [START_REF] Föstner | [END_REF]] and apply vector quantization over 11 × 11 patches for clustering. Support regions defined for interest points usually have a square shape. For a more accurate description, regions that capture exact shape and object structure are used. For example, Deng et al. [START_REF] Deng | [END_REF]] propose a region detector based on the principal curvature. They first extract curvilinear structures using the maximum or minimum eigenvalue of the Hessian matrix at each pixel. Then, they detect structural regions using a watershed transform of the principle curvature across scale-space. The method is fur-ther refined to avoid over-segmentation (due to small watershed regions) or unstable regions (due to low contrast segments). To capture more structure, research by [START_REF][END_REF], Bar-Hillel 2008] use the Kadir and Brandy region detector [START_REF] Kadir | Saliency, Scale and Image Description[END_REF]]. This is an entropy-based operator which finds regions that are salient over location and scale. Gosselin et al. [START_REF] Gosselin | [END_REF]] exploit a fuzzy-region segmentation approach for object retrieval. They use a watershed algorithm on the image of gradient norms. The cores of fuzzy regions are then deduced from uniform areas. To control the final number of regions, a merging step is performed afterwards. Possible overlaps between regions is stabilized through feature computation, which takes into account the membership degrees of the pixels.

In contrast to region detectors, [START_REF] Forssén | Autonomous Learning of Object Appearances using Colour Contour Frames[END_REF]] presented a method that computes invariant frames from color contour description. The method tackles the problem of learning texture-free objects and is robust to scale change. First, it extracts line segments and ellipses as the image primitives. Then, and for each of these primitives, it constructs an invariant frame defined by a similarity invariant transform. Feature vectors are computed afterwards by sampling the image orientations according to the similarity transform. [START_REF] Shotton | [END_REF]] proposed a method for detecting objects using local contour features. The feature detector is learned using a very small set of segmented images then it is applied to a larger training set. The model forms a constellation. It comprises many contour fragments arranged around a centroidal point. These models were compared using the chamfer distance, which is considered to be tolerant to misalignment in position, scale and rotation. Experiments were carried out on horses, cars (side), faces and motorbikes. However, no results were reported on whether the method would discriminate between objects with similar shapes (e.g. cat, puma, panther, jaguar, etc.). [Haugeard 2009] addressed the problem of window extraction from facades to retrieve buildings. They proposed an accurate detection of contours using the Canny detector by automatically adapting the parameter related to the size of the filter to the correct smoothing scale of analysis. Contour fragments are then matched using a graph matching technique with a kernel that takes into account orientations and proximity of contours in the structure.

Although interest operators have proven to be efficient in locating salient features, some scientists prefer to use a random or a regular sampling. For instance, [START_REF] Nowak | [END_REF]] stated that random sampling gives equal or better classifiers than sophisticated multi-scale interest detectors. [Viola 2004] noticed that rectangular features provide a rich image representation for effective training. In fact, rectangular features are considered to operate at a coarse level due to their sensitivity to edges, bars and other simple image structures. For face detection, they defined three kinds of features based on Haar basis functions and introduced a novel image representation called integral images for fast computation. In order to cover several parts of the object, [START_REF] Laptev | Improvements of object detection using boosted histograms[END_REF]] proposed using various rectangles in the normalized object window where he computed histograms of gradient orientation. Tuzel et al. [START_REF] Tuzel | Pedestrian Detection via Classification on Riemannian Manifolds[END_REF]] made use of integral images representation. They extracted a large number of descriptors with overlapping regions and showed that overlapping significantly contributes to increasing detection performance. Their method was applied to pedestrian detection. A region is represented by a covariance-matrix of image features and a human is represented by several covariance matrices of overlapping regions. Within this representation, the feature space created is viewed as a connected Riemannian manifold. Kokkinos and Yuille [Kokkinos 2008] convert image scalings and rotations into translations by combining grid log-polar sampling and spatially varying smoothing. Then, scale invariant descriptors (dim=128) are built using phase, orientation and amplitude features from the Fourier transform.

An alternative to using samples from images is to use the available information provided by all the pixels. Osadchy et al. [Osadchy 2007] propose a system that maps raw images to points in a low-dimensional space, where a face manifold is defined. The idea consists in mapping face images with known poses to points in that manifold and non-face images to points far away from the manifold. The training images used are 32 × 32 pixel-sized. Along with descriptor location, some research work has attempted to optimize the description generated through learning the parameters of the descriptors [START_REF] Winder | [END_REF]] or combining different feature representations [liu 2007].

Modeling and learning

Object modeling

Based on the search or classification method, objects are usually represented with a model-free representation, as an entire entity or with reference to their parts.

A model-free representation tries to characterize global statistics about objects in a way that allows the machine to guess the presence or absence of a particular object, regardless of relations between the object's parts. This representation is also called geometry-free. In fact, there is no related information to the positions of the characteristics being learned. The advantage of such methods is that they don't require a strongly labeled training set where the positions of the object, and probably its parts, are annotated. Computationally, they are generally the most efficient. On the other hand, it is unlikely they can successfully provide location. Some of these methods include, but are not limited to, geometry-free bag-offeatures [START_REF] Nowak | [END_REF], Opelt 2006, Frome 2007[START_REF] Nowak | [END_REF]].

Among geometry-free modeling, considerable attention has been given to the bag-of-features technique. Despite its simplicity, it shows very good performance. The success of this method may be due to its flexible representation which allows a wide range of visually different classes to be covered. The method essentially codes local image patches independently using statistical appearance models. Originally, bag-of-features mimicked text retrieval engines by using the concept of word search. In fact, the method consists in defining "visual" words from the feature space of description. Images are then described according to these words by building a relatively large histogram containing occurrences of each observed word (each local feature will be assigned to its closest visual word). Some methods model objects as whole entire entities that are inseparable. Such methods are mostly used in localization. Marsza lek and Schmid [Marsza lek 2007] define a shape mask function which is a generalization of the discrete binary segmentation mask. Using a bag-of-keypoints representation, the classifier is trained to distinguish between objects and background and the resulting model is a featured shape mask globally representing the object. Philbin et al. [START_REF] Philbin | [END_REF]] try to discover particular objects by first clustering similar images and then modeling objects along with their location and shapes. In order to detect humans, Tuzel et al. [START_REF] Tuzel | Pedestrian Detection via Classification on Riemannian Manifolds[END_REF]] use covariance descriptors [START_REF] Tuzel | [END_REF]]. They apply a classifier at all possible sub-windows in the image. Lowe [Lowe 2004] uses distance matching followed by a Hough transform to determine consistent features with the object geometry. For rigid objects, [START_REF] Philbin | [END_REF]] and [START_REF] Joly | [END_REF]] consider objects as image regions (i.e. query regions).

The third group of methods for forming object models is based on detecting object parts, including common shapes, and then assembling these local parts according to geometric constraints. These part-based methods usually model parts' appearance as well as invariant relations of location and scale between all parts. They can be good for dealing with intra-class variability but they may, however, be sensitive to missing parts. Shotton et al. [START_REF] Shotton | [END_REF]] use contour fragments as raw object parts and exploit their spatial position to build a class dictionary from segmentation masks. The model they propose admits a centroidal point that pulls together the different object parts. [START_REF] Bar | Efficient Learning of Relational Object Class Models[END_REF]] use a simple star-like Bayesian network whose parameters are learned through a discriminative optimization. Moreover, the model has a central hidden node describing objects' location and scale. [START_REF] Bouchard | Hierarchical Part-Based Visual Object Categorization[END_REF]] code visual object categories as a loose hierarchy of parts with probabilistic spatial relations linking parts to subparts. Similarly, [START_REF] Epshtein | Semantic Hierarchies for Recognizing Objects and Parts. Computer Vision and Pattern Recognition[END_REF]] constructs a semantic hierarchy of object parts. Here, part detection is obtained by a bottom-up top-down cycle. [START_REF][END_REF]] models objects as flexible constellations of parts. A probabilistic representation is used for all aspects of the object including shape, appearance and relative scale.

Object learning

Learning objects should be independent from the object design. Yet a learning strategy might be more suitable for certain models rather than for others. Under any circumstances, one has to consider the computational problems involved in using a particular method. This section addresses some of the state-of-the-art algorithms used for learning object models in a supervised manner. They are divided into two categories: generative and discriminative.

Generative-based approaches build a probabilistic model learned by maximizing likelihood. The likelihood ratio test is then used to classify new images. [START_REF][END_REF]] uses an expectation-maximization (EM) algorithm in a maximum-likelihood setting in order to estimate the model parameters. [START_REF] Epshtein | Semantic Hierarchies for Recognizing Objects and Parts. Computer Vision and Pattern Recognition[END_REF]] uses a probabilistic graphical model where the conditional distribution p(Image|Class) is modeled as a hierarchy of features and subfeatures, and the conditional distribution p(Image|N onClass) is modeled as a Naive Bayes model. In [START_REF] Philbin | [END_REF]], Philbin et al. develop a generative latent model with geometric relations at its core. The model is called gLDA as it brings geometry to traditional LDA. Similarly, Li and Zhang [Li 2010] incorporate the spatial structure of local features into LDA. They term the model the Affine Invariant Topic Model (AITM). The method models visual words with latent affine transformations as well as latent topics. Moreover, classification is performed using the Bayesian decision rule.

Discriminative methods try to extract or to separate useful information from the whole set: positive and negative images. Here, the term "useful information" refers to any image feature that helps to correctly classify a given object class, regardless of whether or not this feature is part of the background. One advantage of such methods is that the task lies in minimizing a loss function. Nevertheless, the statistical distribution of the test database must be the same as the statistical distribution used in the training set. [START_REF] Nowak | [END_REF]] uses a set of extremely randomized binary decision trees to compare never seen objects. This method focuses on speed and the random character involved decreases the risk of overfitting. Pham and Cham [START_REF] Pha | Online Learning Asymmetric Boosted Classifiers for Object Detection[END_REF]] seek to balance the skewness of the labels presented to the discrete-valued weak classifiers learned with AdaBoost in an online manner. [START_REF] Laptev | Improvements of object detection using boosted histograms[END_REF]] also uses AdaBoost in its offline version. Based on AdaBoost, Viola and Jones [Viola 2004] define a method that combines increasingly more complex classifiers of simple features in a cascade. The cascade is viewed as an object specific focus-of-attention since it quickly discards background regions of the image. Similarly, Zhu et al. [Zhu 2006] combine multiple classifiers, learned with AdaBoost, to form a rejection cascade such that if any weak hypothesis is negative, then it is considered to be a negative example. Tuzel et al. [START_REF] Tuzel | Pedestrian Detection via Classification on Riemannian Manifolds[END_REF]] keep the cascade mechanism but use LogitBoost instead. At each boosting step k, the best classifier corresponds to the classifier that minimizes the negative binomial log-likelihood to the cascade level k. [Osadchy 2007] detects faces and their poses using the minimum energy machine framework [START_REF] Huang | [END_REF]]. The method consists in mapping raw images to points in a low-dimensional space where a 'face manifold' is pre-defined. Images that contain faces with known poses are mapped to the face manifold. Inversely, non-face images are mapped to points that are far away from the manifold. The image-to-manifold mapping function uses a convolutional network as the basic architecture. To classify classemes, Torresani et al. [START_REF] Torresani | [END_REF]] combine 13 kernels using the LP-β kernel combiner [Gehler ] and try four different strategies for multi-class learning: multi-class SVM, neural networks, decision forests and nearest-neighbor classifier. Marsza lek and Schmid [Marsza lek 2007] evaluate their shape masks using a non-linear SVM with χ 2 kernel. Kumar and Sminchisescu [START_REF] Kumar | [END_REF]] advocate the transition from the use of SVMs to SKMs (Support Kernel Machines). SKM models estimate the parameters of a sparse linear combination of kernels as well as the parameters of a discriminative classifier. Lin et al. [liu 2007] carry out the recognition task with adaptive ensemble kernel machines. They construct a number of kernel matrices, each of which corresponds to a specific type of image feature. Then they fuse these features through kernel alignment [Cristianini 2002]. Yang et al. [START_REF][END_REF]] use the pyramid matching kernel for image classification. To remedy the problem of algorithm complexity during training (which is O(n 2 ∼ n 3 )) and prediction (O(n)), they develop an extension of the SPM method by generalizing vector quantization to sparse coding followed by multi-scale spatial max pooling. In addition, they propose changing the non-linear classifier by a linear classifier using a linear SPM kernel based on SIFT sparse codes. This approach reduces the training complexity to O(n) and prediction complexity to a constant. For object detection, Vedaldi et al. [START_REF] Vedaldi | [END_REF]] provide a cascade classifier made up of three stages including linear, quasi-linear and non-linear kernel SVMs. Rather than specifying a pre-defined kernel, they aim to learn a combination of given base kernels. Gemert et al. [van Gemert 2010] introduce another analogy to BoF models with text visual words for modeling ambiguous quantifiers such as "some", "much" and "-ish". They incorporate visual word ambiguity in the codebook model by softly assigning continuous image features to discrete visual words. Furthermore, and for classification, they use an SVM with a histogram intersection kernel. Some methods combine both generative and discriminative strategies. In [Ulusoy 2006], Ulusoy and Bishop argue that neither a generative approach nor a discriminative approach, alone, is sufficient for large scale object recognition. In addition, their results state that both approaches have complementary strengths and weaknesses. [START_REF] Bar | Efficient Learning of Relational Object Class Models[END_REF] propose a relational model that generatively models object classes using a simple Bayesian network. They use a loss function in order to optimize the parameters of the model.

Similarity learning

Similarity measures play a decisive role in the success or failure of building and using an object model. In high dimensional spaces, usual distances may fail to discern between features. This phenomenon is known as the curse of dimensionality. Yu et al. [START_REF] Yu | [END_REF]] suggest learning the appropriate distance function to alleviate the problem of having feature elements from heterogeneous sources and which may have different influences on similarity estimation. They experiment the method on various applications (image retrieval, stereo matching and motion tracking) and benchmarks. Nowak and Jurie [START_REF] Nowak | [END_REF]] propose learning a similarity measure that embeds domain specific knowledge. They state that standard distance functions, like the Euclidean distance in the original feature space, are often too generic and fail to encode this information. Jegou et al. [START_REF] Jégou | [END_REF]] present a contextual dissimilarity measure (CDM) that takes into account the local distribution of the vectors and iteratively estimates distance correcting terms. In contrast to the ε-search framework where the distance is symmetric, in a k-NN framework, it is not. Here, the CDM tries to improve the symmetry of the k-neighborhood relationship such that the average distance of a vector to its neighborhood is almost constant. Frome et al. [Frome 2007] determine similarity between images by learning local distance functions and then choosing the globally consistent distance functions to use them for comparison at test time.

Scalability and prediction efficiency

Image search techniques and image object retrieval in particular aim to answer a user query in a reasonable time (less than two seconds) when querying large collections of image databases (up to several million images). However, rare are the datasets that address this issue (e.g. the ImageNet database with over 12, 000, 000 images); most of them contain up to several thousand images (e.g. SUN (Scene UNderstanding) database with around 130, 000 images). The main problem, in reality, is the construction of a reliable ground truth for such a huge number of images.

Providing a relatively quick answer requires suitable access methods and scalable index structures. While text search engines can cope with very large databases, content-based image search hasn't yet gained enough maturity and is still facing new challenges, mostly because of the 2D-nature of images. In fact, tasks vary from retrieval to classification and detection, which provides an additional complexity to resolving similarity queries. Exhaustive search is the primitive technique to answer these queries; needless to say it is not efficient.

Most of the sophisticated techniques avoid a sequential scan of databases. Rather, they compress the feature space and use specific search methods. Two common types of queries are used: k-NN and range queries. A k-NN query consists in finding the k nearest neighbors of a given query object according to a given similarity measure. On the other hand, a range query consists in finding all elements within a given threshold (with respect to the query object).

Whether vectorial or metric, index structures usually rely on a treelike method. Although they will not be dealt with here, some references are given instead for guidance [Comer 1979, Henrich 1989, Berchtold 1996[START_REF] Henrich | The LSDh-Tree: An Access Structure for Feature Vectors[END_REF][START_REF][END_REF], Li 1999[START_REF] Manolopoulos | [END_REF][START_REF] Datar | [END_REF], Zhang 2004[START_REF] Wang | [END_REF]. Note that building an index structure has two types of cost: computation time and the disk size needed.

Equivalence between textual and visual keywords

Textual keywords carry information about the type of matter and the subject the document deals with. However, they don't express the writer's point of view. Similarly, our claim is that it suffices to determine a few visual keywords (of a given category) that allow the content of an image to be interpreted in order to correctly classify it. The task here is neither to determine the number of instances nor their relative poses and interaction with the rest of the other objects (In text documents, that would be equivalent to avoiding analyzing the writer's point of view and conclusions.). It is rather to label an image positively or negatively according to a visual category (In text documents, this is equivalent to knowing the document type and subject.).

It is certain that words in text documents have less structure than those in images. This shouldn't be a problem since our objective is retrieval. Therefore, there is no need to model relationships between object parts. Modeling these relations is an additive cost which is more appropriate for part identification and localization tasks.

Need for interpretability

Computer models are usually too abstract for users to understand where bad results might come from. By generating interpretable models, we try to create a link between the numerical representation of objects and our visual representation. Not only does interpretability enhance our understanding of output results, but it is also a very effective tool for user interactivity. It allows users to comprehend what the generic model is composed of and to choose, in different situations, the visual patches 1 that best match their needs. Therefore, interpretability is a means to achieve genericity. Users can perform object retrieval in large database collections which may contain heterogeneous data from different sources.

Requirements for interpretable visual keywords

As is the case with usual keywords (used for indexing and retrieving text documents), we would like our visual keywords to be easily interpretable by humans. We therefore introduce three requirements guiding the design of our method:

Readability: each visual keyword must be displayable, i.e. it has a uniquely defined visual representation that can be displayed in a GUI (typically as a thumbnail). The analogy to textual keywords would be that keywords must be readable regardless of whether they are understandable or not.

Conciseness: the set of the selected visual keywords must be as concise as possible. Conciseness is important for two reasons: first, it helps users to get a global overview from the very first glance and second, it increases the system's efficiency.

Disambiguation: each visual keyword must be as unambiguous as possible.

Clearly, having a unique semantic meaning for each keyword is not realistic. Textual words themselves are known to be ambiguous (the same word having different meanings). Nonetheless, reducing the ambiguity of the visual keywords produced should remain a crucial objective towards interpretability.

Using common visual words

The first intuitive approach to solving our problem would be to rely on commonly used visual words. The related methods usually involve vector quantization of the visual space as a preprocessing stage that aims to reduce the visual vocabulary. This formalism may not satisfy our readability and disambiguation requirements because it discards the local geometric positions of the features being learned. In fact, and with such a representation, the only local information preserved is the centers of clusters formed from the feature space. From a user point of view, this information is not useful because they have no idea whether these centers pertain to tangible parts of the objects (i.e eye, tooth, finger, etc.) or if they are just a statistical combination of some of these parts; hence the non-readability. Moreover, and assuming that the readability condition is satisfied, each visual word might refer to distinct parts in distinct images, consequently increasing its ambiguity.

Commonly used visual words should be considered as syllables rather than words. Cluster centers then represent the common root of the words. For example, and by analogy with text, the syllable "tor" can be the root of the words: torso, torsion and torpido, Using such visual words as querying keywords was explored by Fauqueur [START_REF] Fauqueur | [END_REF]] but with different local features and quantization (segmented regions, clustering). The centers of clusters are presented to users who are able to perform semantic queries through a Boolean composition. Logical queries are built by selecting-from the initial set-consistent regions and canceling out non-relevant regions. Besides non-readability, conciseness is not satisfied since all the centers of clusters are presented to users. In addition to that, these regions are generally textured which is considered to be a hindrance to clear interpretation.

Instead of using vector quantization, in our method, we choose to keep all local features as visual word candidates. Our representation is described in detail in section 4.2.

Using popular classifier models

To classify objects, many current state-of-the-art techniques use the bag-of-features method jointly with an SVM classifier [START_REF] Lazebnik | [END_REF][START_REF] Nowak | [END_REF], Yang 2007, Tirilly 2008[START_REF] Dardas | [END_REF], Raza 2010]. This method has proved to be very effective and achieved high classification scores, mostly because of the sparse representation it uses. However, it does not highlight the most interesting features that an object has. It discriminates objects by focusing on optimal separations in the feature space. In fact, the decision function of SVM classifiers is usually written as

f (x) = ∑ i α i κ(x i , x) + b
where κ(•, •) is the kernel function used to make a non-linear feature map. Moreover, generating a global descriptor for each image can be regarded as a weak point because it gives global statistics on the image scene. There is indeed no clear separation between an object and its context. Therefore, the model is stiff and cannot be used interactively. Furthermore, it is very likely that the performance drops when using test images with a different context than the context used in training (cf. figure 4.1).

Contextual information

Before introducing the details of our method, we discuss here the added value of using contextual information. In fact, the object context sometimes plays a primordial role in recognition. gives an insight into human recognition ability. Thanks to the context, it is easy to tell that there is a plane in the sky. It is even possible to guess the pose and the principle direction. The same image is shown in figure (4.2-b) but with a zoom effect and a crop around the plane. Due to JPEG compression, the aliasing effect is now noticeable. It is obvious that the object which we have already interpreted is hardly recognizable. This shows that the information is not localized in the pixels themselves but rather in the manner they are grouped together and that the context is vital for recognition. As a rule of thumb, using varied backgrounds during training improves the generalization ability of the classifier [START_REF] Ponce | [END_REF]].

Multiple-instance learning

Exploiting contextual information is possible by using a weak learning approach (also called multiple-instance learning: MIL). Indeed, each training image is labeled as a whole sample. MIL deals with uncertainty of instance labels (i.e. individual instances take no labels). An image is viewed as a bag of multiple features which are the local visual words. The bag will have only one label according to whether or not it includes at least one positive instance. It follows that it is only certain for a negative bag that there are no objects. Using an MIL approach has the luxury of unsupervised learning (i.e unlabeled data). It gives more freedom to the algorithm to select contextual information whenever it turns out to be useful to characterize the category. Furthermore, labeling images with a detailed hand segmentation is very labor intensive. So, using a weak learning approach also helps to train images without much knowledge about the objects inside.

Local description and multi-features

There are various reasons why one should rely on local features. First of all, variation of small patches is more robust to a multitude of image transformations. Second, the foreground is usually accompanied by background clutter and it is necessary to find the useful information. Relying on local features that are more related to human vision should normally favor both interpretability and classification. Therefore, it is preferable to use local detectors that preserve scale information. Figure (4.3) is an example which illustrates how important scale information is: a person would not be able to easily identify the coral snake with a low scale.

Despite the fact that the method we propose is generic-in the sense that it could be used with any local features or patterns, in our work, we preferred to use interest points (or structured sets of interest points) as the image primitives. In fact, multi-scale keypoint detectors have proven to be effective in matching applications [START_REF] Nowak | [END_REF]]. They are preferred over edges or other larger features [START_REF] Kerr | [END_REF]]. In addition, they can be extracted under severe transformations. On the other hand, contour techniques are usually used with images involving man-made objects (characterized by known geometric shapes) or with images that don't vary much in viewpoint (e.g. a horse taken from a side view). A shape-based detector will also fail to discriminate between categories originating from the same family as felidae within animals.

We believe that good recognition comes with a good description, specially one that uses multi criteria such as texture, scale and color. Image descriptors are indeed the raw material and the basic data for learning. In order to cover the difference in the nature of the objects to be learned and at the same time the intra-class variability of the same object, a multiple description scheme is needed. Moreover, the usefulness of a feature is often object-dependent and the best visual feature combination for classification could vary from object to object. It is then up to the learning algorithm to choose a descriptor or a combination of many descriptors that best suits a given category. Results reported by [liu 2007] show that the combination of various types of description, after an appropriate learning method, performs better than each single description alone. Similarly, [START_REF][END_REF]] showed that the combination of all features outperform the state-of-the-art.

Feature appearance and model specialization

Our work can be linked to [START_REF] Epshtein | Semantic Hierarchies for Recognizing Objects and Parts. Computer Vision and Pattern Recognition[END_REF]] where a semantic hierarchy was constructed for object parts. The results showed that using varied appearances of the same object part significantly decreases the error rate. However, rather than modeling a hierarchy of all possible appearances, we rely on the learning algorithm to select appropriate visual keywords based on sparsity. Note that part-based approaches are usually sensitive to missed part detection. We want here to change this weak point into a rather powerful clue. In fact, users, generally speaking, tend to have some preferences about the images they are looking for. When querying the retrieval engine, they might want to emphasize the presence of some details (like a specific object part, its relative scale, its context, etc.) and might be indifferent to other details. Allowing users to specialize their own model based on a variation of appearances will certainly provide better results.

To diminish the burden of computation complexity, the image representation we propose can be looked at as being part-based but with no geometry to model relationships between the parts. Our image representation is discussed in the next chapter.

The image representation proposed

For the sake of interpretability, the image representation is important because it is the key to building the components of the model. To reduce ambiguity, we consider the complete set of visual features included in all the training images without any quantization. We refer to our representation as bag-of-raw-visual-words (BoRW) to emphasize that all raw visual features are considered as visual words (without quantization).

A visual word σ k is a structured set of local features:

σ k = {F u , 1 ≤ u ≤ ς}.
A feature F u is a vector signature characterizing a local area of the image. σ k can be reduced to a singleton. In this case, we just refer to it as F k . For now, and without loss of generality, we consider that each visual word is made up of one single local feature. Structured sets are discussed in section 4.4.

Our image representation satisfies the readability requirement and it is well suited to the disambiguation requirement. In fact, visual words are mapped to their exact geometric locations in the training images. Therefore, the models generated represent true real entities of what is described and they are not a vague approximation of the image content. Each image I i is represented by a vector of size M features: (F k ) 1≤k≤M (cf. Figure 4.4). Note that the vector V may contain heterogeneous features, that is, features obtained with different types of description and/or with different dimensions thus resulting in various feature spaces. Even so, the method we propose is still applicable.

An object model is a weighted sum of our visual words. The models generated are extensible if we ever want to use additional training data. They are also shrinkable and can be modified according to the needs of a human operator. Users can query the retrieval engine using only the visual keywords that they think are the best for their purpose. The next section discusses how these visual keywords are trained in order to satisfy our second requirement: conciseness.

Training discriminative visual keywords 4.3.1 Specificity of discriminative training

The choice of using a discriminative training approach over a generative approach stems from the observation that, in practical applications, objects are neither infinite nor isolated. Thus, they can be modeled in relation to one another. Take for example two human languages you have never heard before. And for a while, listen carefully to each language from a given audio sequence. After that, it is not usually difficult to correctly classify some new excerpts from these same languages. This proves that, during listening, people do not try to understand what is going on but rather try to find some characteristics (pitch values, repeated patterns, phonemes, etc.) that could help them to distinguish between the languages in question.

The same schema can be applied to object retrieval. In fact, we might be tempted to know the characteristics that the machine judged as being salient or object-related rather than considering them as an unknown black box. The next paragraph discusses how it is possible to bridge the semantic gap that could exist between human knowledge and the computational representation of the models learned.

Keywords conciseness and model sparsity

Our claim is that conciseness-the faculty of being brief and informativecould be a result of using a sparse representation. Sparsity is also preferable because it reduces the complexity of the model and subsequently the prediction time. Furthermore, producing sparser solutions helps both researchers and users to understand what the model is composed of.

Constraining the loss function with an additive term, also known as regularization, is an effective tool to generate sparse models. Let β = (β 1 , • • • , β j , • • • ) T be the vector of parameters to estimate (i.e. the weights of the visual words, initially zeros). We denote by

S k = (I k , l k ) a training image I k labeled with l k ∈ {-1, 1}. S = {S 1 , • • • , S N }
represents the set of all the training data (N is the total number of the training images). The general form of the regularized loss function L R can be written as

L R (β, λ) = N ∑ n=1 L C (S n , β) + λ • ||β|| α (4.1)
where L C is a convex loss function, λ ≥ 0 is a tuning parameter and || • || α is the α-norm.

To obtain sparse solutions, one should consider setting α ≤ 1. In fact, minimizing eq. 4.1 is equivalent to minimizing ∑ N n=1 L C (S n , β) subject to ||β|| α < t with t ≥ 0. From a geometric perspective, the smaller α, the higher the chance that the solutions occur in intersections between the regularization volume and the space axes, leading to zero coefficients. Figure 4.5 presents unit balls for some values of α and figure 4.6 gives some insight into this idea.

In his thesis, Mairal [START_REF] Mairal | Sparse coding for machine learning, image processing and computer vision[END_REF]] states that, to encourage sparsity, a natural choice would be to take α = 0. Here, L 0 is the pseudo-norm originally proposed by Donoho and which counts the number of non-zero elements in β. He added that this solution is intractable because it necessitates the use of greedy algorithms. Note that the choice α = 1 gives the smallest possible convex so it is a good compromise between generating sparse solutions and keeping the minimization problem convex.

Background: training sparse models with boosting

Our method has its roots in boosting. The boosting mechanism was proposed by Schapire [Schapire 1990] in 1990. Since then, many algorithms have emerged [Freund 1997, Friedman 2000[START_REF] Singer | Leveraged Vector Machines[END_REF][START_REF] Tieu | Boosting Image Retrieval[END_REF], Opelt 2006, Saffari 2010] and boosting has become one of the most successful machine learning techniques. It was basically designed for classification tasks but it is also suited to regression. The theoretical foundations of boosting, including multiple references on the matter, can be found in [START_REF][END_REF]].

The underlying idea of boosting is to combine many weak classifierscalled hypotheses-in order to obtain one final "strong" classifier. Boosting is an additive model which builds up one hypothesis after another by reweighting the data for the next iteration-increasing the weights of misclassified images and decreasing those of well classified ones. This concept helps to generate different hypotheses, putting emphasis on misclassified examples, typically those located near the decision boundary in the feature space. In addition, boosting is able to build a model containing hypotheses of different natures in one learning stage. That is, the feature selection mechanism can process features which belong to different image descriptors. By the term "feature selection", we mean the process of selecting the most discriminant local signatures of the image.

Boosting has been considered as a stagewise gradient descent method in an empirical cost function. In particular, AdaBoost uses the exponential loss function [Friedman 2000[START_REF] Rätsch | [END_REF]]. Nonetheless, this view is continuously brought into question. For example, Wyner [Wyner 2003] presents a boosting algorithm which performs empirically like AdaBoost while stabilizing the exponential loss to a constant. The reader may also refer to the discussion in [START_REF] Mease | [END_REF]].

Although it is an intuitive algorithm, boosting may overfit the training data, particularly when it runs for a large number of iterations T in high dimensional space and with noisy data [START_REF] Rätsch | [END_REF][START_REF] Grove | [END_REF]]. Moreover, a large value of T implies a long prediction time. On the other hand, setting T to a small value may lead to underfitting. Therefore, the model may be non-discriminant, inconsistent and might not cover the variability inside the category itself. The boosting procedure can also be qualified as oblivious as it always functions in a forward manner aiming to minimize the empirical loss. Although the concept of re-weighting is interesting, at an iteration t + 1, we have no idea whether the t previous generated hypotheses are good enough or not versus the model complexity.

Training sparse classifiers with LARK

In this section, we explain our method LARK in detail. We use the BoRW with a multiple-instance learning scheme that regularizes the loss function through Lasso.

Lasso

Tibshirani observed that the ordinary least squares minimization technique is not always satisfactory since the estimates often have a low bias but a large variance. In 1996, he came out with Lasso [Tibshirani 1996] which shrinks or sets some coefficients to zero. Lasso stands for Least Absolute Shrinkage and Selection Operator. The idea has two goals: first to gain more interpretation by focussing on relevant predictors and, secondly to improve the prediction accuracy by reducing the variance of the predicted values. The Lasso loss function Γ can be deduced from eq. 4.1 by setting α to 1 and L C to the L 2 loss function. It is given by

Γ(β, λ) = N ∑ n=1 L 2 (S n , β) + λ • ||β|| 1 (4.2)
Using the L 1 norm shrinks some coefficients and sets others exactly to zero, putting the emphasis on the most important features. As discussed in section 4.3.2, L 1 regularization is the minimal possible convex that can lead to sparse solutions, and keeps, at the same time, the optimization problem convex. This lies at the heart of the method's success.

Recall that λ ≥ 0 is the parameter controlling the amount of regularization applied to the estimate. In order to obtain sparse solutions with an efficient shrinkage tradeoff, λ usually takes a moderate value since a large one may set these coefficients to exactly zero, leading to the null model. On the other hand, setting λ to zero reverses the Lasso problem to minimizing the unregularized empirical loss. The general Lasso estimate βλ is defined by:

βλ = min β Γ(β, λ) (4.3)
Lasso minimizes the L 2 loss function penalized by the L 1 norm on the parameters. This is a quadratic programming problem with linear inequality constraints and it is intractable when the vector of parameters is very large.

In the literature, some efficient methods have been proposed to solve the exact Lasso namely the least angle regression by Efron et al. [Efron 2004] and the homotopy method by Osborne et al. [Osborne 2000]. These methods were developed specifically to solve the least squares problem (i.e. using L 2 loss). They work well when the number of predictors is small. However, they are not well-suited to nonparametric and classification tasks.

BLasso

Since the exact Lasso minimization is not tractable for a very large vector of parameters, Zhao and Yu [Zhao 2007] suggested using a boosting-like procedure called BLasso (Boosted Lasso). This algorithm tries to find the same solutions as Lasso with more cautious steps. BLasso has been applied to various domains including text classification [START_REF] Gao | [END_REF]], intestinal motility analysis [Igual 2007] and handwritten character recognition [START_REF] Obozinski | [END_REF]]. However, and as far as we know, there have been no results reported on generic object recognition or retrieval.

The success of BLasso comes from its ability to converge to Lasso solutions while having the same computational advantages as boosting. In fact, it can deal with an infinite number of predictors and various loss functions. It can also perform variable selection given multiple image descriptors.

Unlike usual boosting procedures, and in order to approximate Lasso solutions, BLasso adds a backward step after each iteration of boosting. Thus, one is able to build up solutions in a coordinate descent manner and then take a look back at the consistency of these solutions regarding the model complexity. Forward steps are used to minimize the empirical loss. On the other hand, backward steps minimize the regularization. In fact, at each iteration, a coordinate β j is selected and updated by a small step size ±ε (with ε > 0). It has been shown [Zhao 2007] that it is preferable to choose a very small step size so that BLasso can approximate the Lasso path perfectly. In practice, ε should always be less than 0.1. Algorithm 1 gives an overview of the BLasso mechanism. Our learning algorithm will be reviewed in more detail in section 4.3.4.7.

Algorithm 1 BLasso 1. Initialization: β = 0 Make a forward step and initialize λ 2. Backward and forward steps:

Find the backward step that leads to the minimal empirical loss. if the step decreases the Lasso loss then take it. else make a forward step and relax λ if necessary 3. Repeat step 2 until λ ≤ 0.

Note that a forward step consists in minimizing the current empirical loss. It changes one variable in the vector of parameters β by adding a value ω = ±ε. On the other hand, a backward step consists in finding the step (i.e. one of the previous forward steps) that leads to the minimal empirical loss. That is, to each non-null coordinate β i , add the value -sign(ω)ω while keeping all the other coordinates unchanged, then computing the empirical loss ϕ i . After processing all non-null coordinates, find the variable that led to the minimal loss. î = arg min i ϕ i (4.4)

Solving the multiple-instance problem

In our multiple-instance representation, we consider each image as a bag of instances (i.e a bag of local features). Only the image is labeled either positive or negative according to whether or not it contains the object. The instances themselves are not labeled and so we are not sure about their true labels. The task consists in selecting the positive instances because they represent some parts or a global view (in a coarser scale) of the object.

Since we don't know about the instance labels, one way to solve the feature selection problem is by discarding the instances that we are sure don't belong to the object. The idea is to reject any instance that belongs to a positive bag and that happens to exist in a negative bag. Hopefully, a sufficient number of training images would allow us to keep only the object features. Despite its simplicity, this idea cannot be directly applied to object categorization because the instances we are dealing with are visual features. In other words, given an instance in a bag, this same instance can exist in other bags under a different shape or appearance. This fact makes it impossible to identify negative instances; which leads us to the choice of using similarity measures. Knowing that each instance is a multidimensional vector in a high feature space, it is also difficult to define a good threshold of similarity due to the curse of dimensionality.

The solution proposed here is to rank the bags according to their best similarities to a given instance and then to attribute a score to this instance according to the ranking obtained (see the minimal distance matrix section 4.3.4.5). Scores must be attributed so as to favor the instances whose positive bags are ranked first. Here, and in order to assert the rejection of doubtful instances, it is necessary to rank a negative image before a positive image if these images have the same similarity score (or the same distance) to the instance.

Rejecting negative instances may theoretically keep several positive instances which results in a huge model. This is not practical if we wish to allow users to interact with the models. To remedy this problem, one must rely on a good feature selection mechanism that doesn't overtrain data. Overtraining should not be confused with overfitting. It simply means that the resulting models are very large and that similar prediction performance can be obtained with fewer instances.

Membership function

To decide whether or not a visual word F k belongs to a given image, we must define a membership function. An intuitive choice would be to consider a usual distance function like the Euclidean distance. The distance between any feature F ki belonging to the image I i and any image I j of the training set is defined by: d(F ki , I j ) = min

1≤k ′ ≤M j d(F ki , F k ′ j ) (4.5)
For each F ki , the images I j are then sorted with increasing distances.

The choice of the minimal distance in eq. 4.5 is open to debate, but it is, in fact a good measure because it takes into account objects detected in a very low scale (i.e. the object is only described by one or two image features). However, it is not robust in the presence of outliers, noisy data and/or when the descriptors used are not good enough.

Besides common distances, we can define other membership functions that don't have to satisfy the requirements of a distance, namely non-negativity, symmetry, triangle inequality and the assertion that d(a, b) = 0 iif a = b).

In fact, we can think of any function that attributes higher positive scores to higher similarities. In this case, and for the sake of the genericity of the method, we can multiply each score by -1 to be able to rank images in an increasing order (according to best similarities). This kind of membership function is used in section 4.4. Nonetheless, in the following sections, and without loss of generality, we denote any membership function by d(•, •).

Definition of a weak classifier

The final classifier (also called strong classifier) is a weighted sum of the weak classifiers learned during training. A weak hypothesis h k (i.e. weak classifier ) represents a coordinate of base learners. Its weight is strictly positive if it was chosen at least once during the boosting process and remains zero if not. In the context of object retrieval and categorization, the weak hypothesis h k is a visual word F k with a particular description ρ and which has an optimal radius r k (Opelt et al. [Opelt 2006]). h k is viewed as a hypersphere centered on the local image feature F k (cf. figure 4.4). For a test image x, h k will output +1 if the distance between x and F k is less than r k and -1 otherwise:

h k (x) = sign ( r k -d(x, F k ) ) (4.6)
Choosing hyperspheres over other representations like hyperplanes and decision stumps gives an easier interpretation to image features. It also guarantees a fast classification since we just need to compare the distance d(x, F k ) to r k .

The radius r k of a hypersphere is computed such that the classification error of F k is as small as possible. In order to compute the optimal r k , we need to precompute a minimal distance matrix between any image feature and the training images themselves. Let Ω = {e 1 , • • • , e E } be the set of all types of descriptions used and V i,ρ = {F i,ρ,k ; 1 ≤ k ≤ M i,ρ } the set of the local signatures belonging to the image I i according to the description e ρ . Now,

∀i ∈ {1, • • • , N } and ρ ∈ {1, • • • , E} ∀k ∈ {1, • • • , M i,ρ } -Minimal distance matrix: ∀j ∈ {1, • • • , N } compute the minimal distance d i,ρ,k,j between F i,ρ
,k and the image I j (i.e. the closest distance to I j )

d i,ρ,k,j = min 1≤k ′ ≤M j,ρ d(F i,ρ,k , F j,ρ,k ′ ) (4.7)
-Sorting: Let s be a permutation such that

d i,ρ,k,s(1) ≤ • • • ≤ d i,ρ,k,s(N ) (4.8)
Consequently, images are sorted increasingly according to their distances to F i,ρ,k -Radius computation: Select the index η where the sum of image labels is maximum

η = arg max 1≤η≤N η ∑ j=1 l s(j) (4.9)
The hypothesis radius r i,ρ,k is then given by:

r i,ρ,k = d i,ρ,k,s(η) + d i,ρ,k,s(η+1) 2 (4.10)
The distance matrix may sometimes be too large. This usually happens when the training set comprises many images and/or when there are many descriptions used. Two major problems are generated in this case: an excess use of the main computer memory and a slowness in the learning algorithm to determine the best hypothesis at each boosting iteration. One solution consists in reducing the size of the distance matrix by getting rid of the "bad" entries that we know will never be selected in the learning stage. For example, this is the case when the closest neighbor to a query feature belongs to a negative training image. It is certain that this kind of visual word will never generate good hypotheses. In addition, and as a second filter, we can apply the distance ratio proposed by [Lowe 2004] to discard bad matches. The method consists in rejecting a feature when the ratio between the distance to its first closest neighbor and the distance to its second closest neighbor is above some threshold. However, since a good match can be found in many positive images, the second closest distance is defined as the first closest distance to a negative image. Winder and Brown [START_REF] Winder | [END_REF]] reported that this simple optimization produces a boost in performance. [Mikolajczyk 2005a] showed that the matching gained by the nearest neighbor distance ratio varies according to the description used. In any case, there are fewer false matches and precision is improved.

In our experiments, we used hard weak classifiers as defined by eq. 4.6. We can also define soft weak classifiers. Consider, for example, the expectation

E ( h k (i) )
of the classification of the image i, which measures how likely an image contains the visual word F k . Take all the radii r ki of F k computed from the distance matrix. The task is to minimize the probability p k that the image does not contain the feature

F k p k = min i p ki (4.11)
where p ki is the probability that the image does not contain F k within the radius r ki It is given by

p ki = (ν -τ ν)! (ν -ν + )! ν! (ν -τ ν -ν + )! (4.12)
where 0 < τ ≤ 1 is a constant repeatability parameter, ν is the number of features in i and ν + is the number of the features in i within the radius

r ki . E ( h k (i) ) is written as E ( h k (x) ) = 1 -2 • p k (4.13)

Definition of the loss function and weight updates

Since the exact minimization of the loss function with a very large number of base learners is hardly practical, boosting-procedures try to find the solution with an iterative procedure. At each iteration, a weak hypothesis is chosen such that the strong classifier converges to the optimal solution. For classification tasks, various convex loss functions have been used such as exponential loss, logit loss, binomial deviance, etc. In our method, we use the exponential loss function L e as in AdaBoost. Let T be the maximum number of iterations. At an iteration t + 1 ≤ T , one minimizes:

L (t+1) e (β j ) = N ∑ n=1 exp(-l n • F (t+1) β j (I n )) (4.14)
where

F (t+1) β j (I n ) = β j • h t+1 (I n ) + ∑ t k=1 β k • h k (I n ) is the set of ensembles of base learners. β (t+1) = β (t) + β j • 1 j (4.15)
and 1 j is the j th standard basis vector with all 0's except for 1 in the j th coordinate.

After a boosting iteration, the training data are re-weighted. Initially, all image weights are set to 1 N (N is the number of the training images). Weights are updated so as to emphasize the misclassified images. The optimal solution to minimizing L e is βj such that βj = 1 2 log 1 -ε t+1 ε t+1 (4. [START_REF] Torresani | [END_REF] where

ε t+1 = N ∑ n=1 ln =h t+1 (In) w n (t+1) (4.17)
is the weighted training error (w n is the weight of the image I n ). AdaBoost runs until it reaches T iterations and stops earlier if ε = 0 or ε ≥ 0.5.

Boosting has been interpreted as a gradient descent method. Equation (4.16) gives the optimal βj that allows the algorithm converge as fast as possible (i.e. steepest descent). This formulation is utilized in AdaBoost. On the other hand, other varieties of forward stagewise additive modeling algorithms take more steps to converge but usually outperform the steepest descent method in prediction. Forward Stagewise Fitting (FSF, also called e-boosting) is one example. It adds new coefficients to the previous set with an infinitesimal fixed step size ε > 0. Yet it is unclear what criteria FSF optimizes. At each iteration, a coordinate is chosen and updated by ±ε. The fact that ε is very small imposes a local shrinkage on the variables. Hastie et al. [Hastie 2009a] (section 16.2) showed that forward stagewise can sometimes (but not always) approximate the effect of Lasso. Similar observations were noticed by Zhao et al. [Zhao 2007]. Their simulations concluded that FSF local regularization does not converge to the Lasso path in general. They also added that FSF solutions are less sparse than Lasso. To remedy this problem, they introduced the concept of backward steps which minimize the Lasso loss (i.e BLasso). By allowing backward steps, the algorithm goes back and forth in order to optimize the trade-off between penalty and empirical loss.

LARK: the algorithm

Our objective is to minimize

Γ(β, λ) = N ∑ n=1 L e (S n , β) + λ • ||β|| 1 (4.18)
and our method is based upon BLasso.

BLasso adds a backward step to take into account the regularization term in equation (4.18). Forward steps, however, are chosen so as to minimize the empirical loss of the training samples. Both of these steps use the same loss function.

Unlike BLasso, LARK's forward steps always add a positive value. Consequently, backward steps are those that shrink the model by subtraction. The choice made here is justified by the fact that the distance matrix defined earlier (cf. section 4.3.4.5) is computed only for the features belonging to the positive examples. Therefore, a selected hypothesis represents a visual feature that contributes to building the model of the object category. It must therefore have a positive weight. The reason for not computing the distances between negative features and the training images is that it does not help either user interactivity (i.e. ambiguity to define what a negative visual word is) or genericity (a negative visual word may be representative of one dataset but could not generalize to other databases). However, it is possible to learn a negative model against the object category. This idea is discussed in section 6.5.

In order to minimize the empirical loss, LARK uses a weighting scheme as in AdaBoost. In fact, adopting this strategy is more appealing. First because it is much faster and second, it benefits from the weight change. The slowness to overfitting of AdaBoost has been observed over recent years, and this property is incontestable. One of the reasons is that, at each iteration, AdaBoost gives more attention to the misclassified observations by increasing their respective weights. In order to take advantage of this principle, we decided to keep the same mechanism to select forward steps. At an iteration t, we compute the score s i,ρ,k of the base learner (F i,ρ,k , r i,ρ,k ) based on the image weights

s i,ρ,k = max m m ∑ c=1 w s(c) • l s(c)
Then, we select the base learner which obtains the highest score. In fact, when dealing with a very large or an infinite number of base learners, it is impractical or even impossible to try to minimize the loss function directly. In their seminal work, Opelt et al. [Opelt 2006] used a representation with infinite base learners. The radius r i,ρ,k of each weak hypothesis is not fixed a priori but takes into account the weight changes during AdaBoost iterations. It is computed after the algorithm selects the feature F i,ρ,k . Equation (4.9) then becomes:

η = arg max 1≤η≤N η ∑ j=1 w s(j) • l s(j) (4.19)
In LARK, since each visual word F i,ρ,k contributes to the final model by at most one hypothesis, we averaged out the different radii-of a given visual word-that were computed during forward steps. After LARK stops, the hypothesis radius is given by

r i,ρ,k = ε β i,ρ,k ∑ t r i,ρ,k,t (4.20)
where r i,ρ,k,t is the radius of F i,ρ,k computed at a previous iteration t.

Algorithm 2 summarizes our proposed feature selection mechanism. It has one input parameter ξ > 0 which is used as a tolerance level.

In order to illustrate the principle of BLasso, we present a simplified diagram (cf. figure 4.7) that shows how the procedure works. Without loss of Algorithm 2 LARK: The proposed learning algorithm 1. Initialization: set β = 0 and t = 1 -Set w

(1)

n = 1 N for n ∈ {1, • • • , N } -Train
the classifier and find the best hypothesis h

(1) κ (κ is the index which corresponds to the κ th entry of the vector β) -β(1) = ε • 1 κ -Calculate the initial regularization parameter

λ 1 = 1 ε ( N ∑ n=1 L(S n , 0) - N ∑ n=1 L(S n , β(1) ) ) (4.21)
-Set the active index set I

(1) A = {κ} 2. Backward and forward steps Find the backward step that leads to the minimal empirical loss. ĵ = arg min

j∈I (t) A N ∑ n=1 L(S n , β (t) -ε • 1 j ) (4.22)
This step is taken if it helps to decrease the Lasso loss. In other words: If

Γ(β (t) -ε • 1 ĵ , λ t ) -Γ(β (t) , λ t ) ≤ -ξ (4.23) then β (t+1) = β (t) -ε • 1 ĵ ; λ t+1 = λ t
Otherwise, we force a forward step and relax λ if necessary.

-Update weights

w (t+1) n = w (t) n • exp ( -ε • l n • h (t) κ I(n) ) τ (4.24)
where τ is a normalization constant such that ∑ N n=1 w (t+1) n = 1 -Train the classifier and get the best hypothesis h

(t+1) κ -β(t+1) = β(t) + ε • 1 κ -λ t+1 = min [ λ t , 1 ε ( ∑ N n=1 L(S n , β(t) - ∑ N n=1 L(S n , β(t+1) -ξ ) ] -I (t+1) A = I (t)
A ∪ {κ} 3. Increase t by one and repeat steps 2 and 3 until λ t ≤ 0 generality, we suppose that all the coordinates estimated have a positive value (as in LARK). In other words, the forward steps are always positive (w = ε), therefore, a backward step always decreases the coordinate found by a ε. Note that BLasso uses a tolerance parameter ξ > 0 to gain more stability. ξ should be set to a very small value. The figure is made up of repeated blocks of backward and forward steps. Each step uses boxes to encapsulate the status of the coordinates (β i ) i as well as the empirical loss L and the Lasso loss Γ. In addition, these losses are shown as a percentage of the initial loss. The numbers given here are not related to any real run with concrete data, but they are chosen in order to illustrate the behavior of BLasso in different situations.

Efficient implementation

The greediest block in the BLasso algorithm is the computation of the loss function. In fact, we need to compute both the empirical loss and the the Lasso loss many times during each iteration. The complexity increases every time BLasso chooses a new coordinate that was not selected before. Luckily, the Lasso loss can be deduced from the empirical loss. It follows that, in order to compute the current Lasso loss and the backward Lasso loss, we just need to compute their respective empirical losses. On the other hand, and at each iteration, only one coordinate is modified while all the other coordinates remain unchanged. Therefore, assuming that memory is cheaper than processing time, the computation of the empirical loss can be speeded up-at an iteration t-by keeping in memory the classification values of the previous state for each coordinate β j and for each image I n . The memory in use depends on the number of images in the training set as well as the number of the variables selected by the learning algorithm at a given step. Since BLasso favors sparsity, the number of hypotheses selected will be small enough for this method to be still applicable, even with a large number of images in the training set. Each image I n will have a storage vector ζ n . To simplify the notation, we will consider that the j th entry of the vector ζ n (i.e. ζ n (j)) refers to the classification value of the variable

β j ζ n (j) = β j • h j (I n ) 1 ≤ n ≤ N ; j ∈ I A (4.25) Algorithm 3 Exponential empirical loss C ← 0 For n=1 to N do c n ← 0 For each j in I A do c n ← c n + ζ n (j) Done C ← C + exp(-l n • c n ) Done
to update (if β k has already been selected before) or create new (if the index k is selected for the first time) N classification values. That is, we have to compute ζ n (k) for all 1 ≤ n ≤ N

The storage of the classification values is more important when searching for the backward step. The empirical loss is not computed just once but at least card{I A } times where card{I A } is the cardinal of the index set (It is computed card{I A } + 1 times if the coordinate is selected for the first time.) Given an image I n , for each coordinate j, we need to compute the empirical loss based on the coordinates β -ε1 j . Apart from the coordinate β j , the other classification values have already been computed and stored in ζ n (k) with k = j. Moreover, the absolute difference between ζ n (j) (already computed if the hypothesis is old) and the classification value δ nj that we need to compute is

ε if { ζ n (j) < 0 ⇒ δ nj = ζ n (j) + ε ζ n (j) > 0 ⇒ δ nj = ζ n (j) -ε (4.26)
It follows that the classification value of the image I n (i.e. ∑ k ζ n (k)) will only change by an absolute difference of ε. We denote by

ζ n (j) = ∑ k =j ζ n (k) + δ nj , that is: ζ n (j) = { ∑ k ζ n (k) + ε if ζ n (j) < 0 ∑ k ζ n (k) -ε if ζ n (j) > 0 (4.27)
This formulation helps to locate the backward step quickly. In fact, it only takes a linear time according to the number of the selected hypotheses. After subtracting the value ε from the coordinate β j , the empirical loss E j is computed as follows:

E j = N ∑ n=1 exp(-l n • ζ n (j)) (4.28)
The backward step ĵ is then defined by ĵ = arg min j E j (4.29)

When the algorithm proceeds and selects a coordinate g at the iteration t, the stored values will be altered as follows. If g is selected for the first time, then ∀n

ζ n (g) = ∑ k =g ζ n (k) ; ζ n (g) = ε • h g (I n ) (4.30)
and

ζ (t) n (j) = ζ (t-1) n (j) + ε • h g (I n ) ∀j = g (4.31)
Now, if g already belongs to the active index I A , then

ζ (t) n (g) = ζ (t-1) n (g) + sign(ζ (t-1) n (g)) • ε (4.32)
Equation (4.31) is valid for all j ∈ I A . Note that when j = g, this equation automatically takes into account the backward step (i.e the term -ε • 1 g ) because it was not added in the first place.

Including local geometric constraints

Feature selection, at each boosting iteration, is achieved according to the highest score of visual words. These scores are a measure that reflects how reliable a given feature is. They take into account image weights, but more importantly, they are computed with respect to the ranking of the training images (cf. Eq. 4.8) and don't need any additional information. Recall that image ranking is possible thanks to the membership function that computes similarities. Furthermore, each type of description e ρ may have its own membership function which is the best suited. Hence, and more specifically, various distance functions (L 1 , L 2 , Mahalanobis, etc.) can be used simultaneously. Also note that, for each membership function, distance computation can vary from exhaustive to more advanced accelerated techniques.

So far, each visual word has been considered to contain a unique local image feature. In this section, each visual word is a structured set of local image features as defined in section 4.2. Particularly, a visual word contains some interest points located within a neighborhood, and that preferably, capture the same structure. This kind of word is very helpful when there exist repeated patterns and/or when dealing with rigid objects.

The question on how to construct a query set from local image features may be resolved in various ways. However, and in order to form a structured set, local image features have to satisfy one or many neighborhood constraints related to the image space (and independently from the feature space). Therefore, we can ensure that the visual word concept still holds. Forming bigger image patches may transform these local patches into semilocal or even "global" patches. By analogy with text documents, a word may turn into a phrase or a sentence. This statement stresses that "big" visual words may include excessive information to the point where they become inflexible, hard to manipulate and are deemed to fail if glued together to build a richer semantic concept. In general, if the scale information of a local feature F is available, we think that is a good idea to use a surrounding region defined by a multiple factor of the scale, say three or four times. The query set is then formed from all the features belonging to this region. Otherwise, we may think of considering the kNN features of F . In reality, the scale information is preferable because it captures the local characteristics of a detected feature. It is also a good means to extract the same structure from different images.

Rather than using a metric distance for comparison, ranking images is achieved through a similarity matching score that summarizes geometric coherence between the query set (i.e. the visual word) and the best set that matches in a particular image x. This score is computed in two steps:

Feature matching Each feature F ku (belonging to a visual word σ k = {F ku , 1 ≤ u ≤ ς}) is matched in the database thanks to an efficient approximate similarity search [START_REF] Joly | [END_REF]].

Geometric consistency Using RANSAC, and for each image x i , we compute a geometric consistency score by estimating an affine transformation model (A ki , B ki ), with six degrees of freedom, between σ k and the matched points in x i .

We denote by Ψ k = {P ku , 1 ≤ u ≤ ς} the spatial points corresponding to the visual word σ k and Υ = {Q ku , 1 ≤ u ≤ υ} the spatial points matched.

We have υ ≤ ς. Without loss of generality, we suppose that the point P ku matched the point Q ku for u ∈ {1, • • • , υ}. The matching score Ξ between σ k and x i corresponds to the number of inliers in the model. It is given by

Ξ(σ k , x i ) = υ ∑ u=1 δ ( ||P ku -A ki Q ku + B ki || ≤ t ) (4.33) with δ(d ≤ t) = sign(t -d)
and t is a fixed tolerance threshold (t = 7).

Recall here that if two or more images had the same score, negatives would have to be ranked first (see Solving the multi-instance problem, section 4. 3.4.3).

Chapter 5

Interactive Retrieval

To manage a system effectively, you might focus on the interactions of the parts rather than their behavior taken separately. Russell L. Ackoff R ETRIEVING visual objects consists in attributing-to unseen images-scores according to the likelihood that they contain a particular object. The scores are obtained by comparing the visual keywords composing the object model with each image. Interactivity, however, adds the possibility to adjust the model according to user needs. The model itself has to have a clear view. In the next section, we provide detail about how to compute image scores.

Prediction

The strong classifier is the predictive function that computes scores. It may involve hypotheses originating from various types of descriptions (e c i ) 1≤i≤G with G ≤ E and can be written as:

H = ∑ j w j h j,e c 1 + ∑ j w j h j,c 2 + • • • + ∑ j w j h j,ec G
where each h j,e c i is a weak classifier (cf. definition of a weak classifier section 4.3.4.5) associated to one single visual keyword. Note that H is a realvalued classifier that allows images to be ranked according to their scores. We aim to compute the classification value of a given test image x from a retrieval point of view. There are two different ways to proceed: either by means of range queries or by using an exhaustive search. In any case, we need to compute the output of every weak hypothesis h j,ec i which is represented by the couple (F k,e c i , r k,ec i ). The cost of the prediction time is based on the number of distances to compute. Hence, the time complexity is linear with respect to the number of images (since images contain almost the same number of local features).

In the exhaustive mode, we begin by computing the minimal distance (using the membership function of the description e c i , and which can be either a usual distance or a matching score that takes into account local geometric constraints, cf. sections 4. 3.4.4 and 4.4) between x and any F k,ec i . Only the features that belong to x and with the description e c i are concerned:

d j = min Fz,e c i ∈x d(F z,e c i , F k,e c i )
The output of h j,ec i is then given by the formulation in equation (4.6) and the classification value of x is the weighted sum of all the outputs of the weak classifiers. The higher this value, the greater the likelihood that the image contains a given object. This formulation favors retrieving images according to the number of the visual patches they contain. It is, however, difficult to learn an effective threshold that separates object images from non-object images since the model may be specialized by users-implying that the number of visual keywords selected, as well as their confidence measures, may vary. Consider the case where the model comprises two visual keywords, each having the same weight 1. If an image contains both of the patches, its score will be 2 and vice versa. Inversely, if it doesn't contain either, its scores will be -2, and if it contains only one patch, its score will be zero. Now if we take the first case and add to the model eight other visual keywords having the same weight 1, the score of an image containing only two relevant patches is -6. Comparing with the first case when the image has a score of 2, we see the large interval the scores may belong to. Nonetheless, defining a fixed retrieving threshold is possible when considering normalization.

When using an index structure, the same scores are obtained but we proceed differently. Rather than predicting each image separately, all images in the database are predicted at the same time. In fact, we begin by initializing the prediction values of all the test images to zero. After that, for each weak hypothesis h j,ec i , we perform a range query over the database. That is, we query the search engine to retrieve all the images that fall into the hypersphere r j,ec i defined by h j,ec i . ∆ = range db (F j,e c i , r j,ec i ) = {F s.t. d(F j,ec i , F ) < r j,ec i }

(5.1)

The images belonging to ∆ are attributed the value +1 as the output of h j,ec i . Consequently, their respective prediction values, initially zeros, will each be incremented by the weight of this weak classifier. On the other hand, the images that don't belong to ∆ are attributed the value -1 and their prediction values are each decremented by the same weight of this classifier.

After looping through all the weak hypotheses, each test image ends up having a classification value.

The process can be relatively slow depending on the database size and the number of hypotheses constituting the model. For applications that have a fixed image database (not updated online), we can compute a priori the distances separating each weak classifier from each image and load them when the search engine starts. This could be achieved with no difficulty because the models used are concise and so will not consume too much computer memory. Moreover, since distances are computed offline, the process can be done either exhaustively or using an index structure. Unlike retrieval with range queries, to answer a given query, images are processed one by one. For each image, the distances to the model defined are obtained through a lookup table and the score is computed by comparing these distances to the corresponding classifier radii.

Visual keyword representation

The usefulness of the method we propose is that it allows user interaction. After being constructed, a model can be visualized by users as small image patches. Each patch corresponds to a local image feature, particularly, the description region of an interest point or a set of interest points. The visual representation takes into account the window size of the descriptor (in the case of one interest point, and respectively, the region including all the points in the case of a structured set) as well as the principal orientation of the interest point (respectively the principal orientation of the center interest point of the set). However, one may omit rotating the patches to the orientation of interest points so as to avoid introducing another level of difficulty to users. Indeed, humans are not familiar with upside-down positions, and rotating images adds complexity and slows down the understanding of objects' components. Our primary objective is to keep the visual keywords as interpretable as possible. In addition, and for the representation size, we chose to normalize all the patches to a constant width. Two reasons can justify this choice. First, it is better for users when a software interface presents choices (i.e. object parts) with a certain regularity-from an ergonomic point of view. Second, normalizing sizes has the same effect of a zoom-in or a zoom-out, therefore it preserves the knowledge of the scale of detection. This idea is illustrated in figure 5.1.

Comprehensibility of a full visual model

Object parts can be grouped together whenever they participate to form an understandable concept which can be easily described by a word or a phrase (e.g. a face includes two eyes, a nose and a mouth). From this perspective, an object model can have various interpretations. In other words, the visual Take for example a biologist who is looking for the visual relations and similarities that characterize a given species of vegetation or animal. Based on a robust descriptor for the task and assuming that the opposite category in the training set is well defined, there is a high chance that this scientist discovers new interesting visual clues. For computer-science researchers, they might be interested in improving a model of an object category by making it more generic for search engines or more specific for a particular purpose. On the other hand, end-users may profit from the model representation from another perspective. They can query the system only by selecting the most representative visual keywords and with whatever proportion they choose. For instance, and assuming that users are provided with a visual model of cars but with no model of tires, a user who is looking for images containing tires can choose only the relevant patches from the car model (which includes a priori some visual keywords of tires).

Interaction

Graphical User interfaces (GUI) are a key to interaction success. Advances in technology have made it possible to create friendly interfaces, particularly those that provide screen touch capabilities. Multimedia documents are becoming easy to display, manipulate and organize. Added to that, new options are constantly being suggested and integrated as other multimedia fields release new functionalities.

Figure 5.4 is a snapshot of our user interface. It gives an idea of what our interactive retrieval looks like. It is worth mentioning that, when designing the interface, the primary objective was not to encourage user-friendliness so much as to provide a functional prototype that illustrates the interactivity principle. In this sense, the interface is very basic since it does not include fancy options like a drag & drop facility, for example.

Constructing specialized visual models

Let us explore the capacities that the interface does provide. On the left side, users can choose a category from a list of predefined visual categories that have been trained with LARK-and that are available just below the word "Concepts". The corresponding model is then loaded. Consequently, users can browse the visual keywords displayed and start forming their own concept. Note that visual keywords are displayed with their relative weights learned during training. However, when building their models, users have the possibility to change these confidence measures according to their own perception. That is, the more relevant a feature is, the higher the weight it will be assigned. Each visual patch chosen as well as its weight are displayed in the middle panel which represents the specialized model. Between these panels we find four keys controlling patch selection. The right arrow allows users to move one or many patches (Multiple selection is possible when holding the Ctrl key.) to the middle panel. Inversely, the left arrow moves the selected visual keywords back from the specialized model to their original positions. The double right arrow and the double left arrows are respectively used for adding the whole model to the middle panel and for clearing it. After selecting some visual keywords, the query is ready and the search engine can be launched. The retrieved images are ranked according to the confidence scores given by eq. 5.1 where the weights w j are either initially trained or manually specialized. These images are displayed in the right panel together with some extra information about retrieval time and the total number of images returned.

Refining the visual model

In this section, we give visual illustrations on how user interaction is beneficial. User interaction is mostly based on target focus, context specialization and ambiguous keyword discard. A diagram showing user interaction is presented in figure 5.5.

The first example is given in figure 5.6. The model used for retrieval (shown at the top) comprises six patches. The choice to make for displaying patches in a way that truly takes into account the description involved is still challenging. Here, we display the patches in a gray-scale just to point out that the description is not color-related. They were taken from the sunflower model and they represent a global view of sunflowers within their context. Next, in fig.

(5.6-2), we show the first page search results. As we can see, the retrieved images match the query. They mostly contain sunflowers within a context (field, vegetation, sky). This result is due to the scale information brought by the patches. On the other hand, wa can notice the presence of an image containing tomatoes. Even though it is not appreciated, such a result explains some limitations of the description used. The image does indeed appear to have the form of a sunflower. Now, let's look at the example shown in figure 5.4 and notice the difference between the first ranked results. The model used is displayed in the middle panel. Unlike the previous example, the images retrieved here tend to occupy all the image area.

As a second example, we present two different queries and their respective results (cf. fig. 5.7 and 5.8). Both queries are related to the zebra category. The first query focuses on the zebra upper-front part (head) while the second query is rather a general and global view of a zebra.

Model specialization may also turn a positive visual keyword into a negative one by attributing a negative weight. This could be helpful whenever the user wants to avoid a particular context, although it may decrease overall retrieval performance.

(5.6-1) A specialized sunflower model used for retrieval.

(5.6-2) Search results.

Performance Evaluation

The great tragedy of science -the slaying of a beautiful hypothesis by an ugly fact.

T.H. Huxley E STABLISHING an objective evaluation is not easy since the algorithm's behavior must be analyzed under various conditions. Among the many aspects that must be considered are the types of objects, the types of descriptions, the number of categories involved, search efficiency on a large scale and comparison with state-of-the-art methods. To satisfy these requirements, we carried out our experiments on different datasets and local descriptors. The two questions that have to be answered are:

1. Is the method effective compared to state-of-the-art methods? 2. Are the visual keywords produced interpretable?

In this chapter, we evaluate the retrieval performance. We will answer the first question by comparing our method to Opelt's method [Opelt 2006], which uses the AdaBoost algorithm for feature selection and it outputs readable features. Therefore, it seems suitable for comparison since we also use a boosting-like procedure. Moreover, and apart from retrieval performance, the features selected by Opelt's method can be directly likened to our visual keywords both from model size and interpretability perspectives. The evaluation of user interactivity and visual keywords interpretability will be dealt with in the next chapter.

We begin this chapter by presenting the datasets we used as well as the local features, the algorithm parameters and the evaluation metrics. Then, in section 6.2, we compare our feature selection method with Opelt's method according to the average precision measure and the number of features in the model. After that, section 6.3 shows the extent to which our models can be generalized. Section 6.4 studies the benefits of combining multiple visual features. In section 6.5, we explore the effect of adding a counter-class model to the object class model. After that, we present the benefits of using the geometric consistency approach in section 6.6. Finally, we stress the merits of using an effective index structure in section 6.7.

Data preparation and test conditions 6.1.1 Datasets

In order to evaluate our method under different conditions, we carried out our experiments on eight different datasets, some of which correspond to benchmarks and/or are publicly available and some of which were manually constructed. They are BelgaLogos 1 , Caltech-256 2 , ImageNet 3 , ImagEval 4 , OxfordBuilding 5 , PascalVOC 6 , PlantLeaves V1 and PlantLeaves V2. Some images belonging to these datasets are shown in figures 6.1 and 6.2.

BelgaLogos, Caltech and OxfordBuilding are publicly available. However, they are provided with no ground truth specifying a clear decomposition between training and test data. Therefore, we managed to randomly split the data with approximately the same number of images used in training as for prediction. We should mention that OxfordBuilding contains some junk images explicitly identified in the ground truth files it comes with. We discarded all these images. There are also some images that are not annotated. These images contain relevant buildings from the eleven landmarks defined, which is why we chose to exclude them from the composition of the training/test sets.

ImageNet is a very large database (containing 12, 184, 107 images-at the time of writing this thesis-and 17, 624 different synsets) indexed with a hierarchy of concepts. Our research does not focus on large-scale concept numbers. From this original dataset, we considered only ten visual categories that in-tersect with some Caltech categories (i.e the same visual concepts). Since ImageNet comprises a large number of images, each training set was constructed from almost 700 images related to the concept. In our experiments, we refer to this dataset as ImageNetSmall.

ImagEval is a French initiative held in 2006 and it included participants from research teams as well as private companies. We used the images provided by this initiative, and which were dedicated to the task of object detection (task 4). The composition of the training/test sets is explicitly defined. Similarly, we used the training/validation images provided by the benchmark PascalVOC 2010 and we excluded the difficult images that are not taken into account in the final evaluation process (i.e. images labeled by 0 in the ground truth).

PlantLeaves V1 and PlantLeaves V2 are two manually constructed datasets built from an initial dataset named PlantLeaves which up to now has not been made publicly available. This dataset contains images that are natural scans of some plant leaves and it is constantly increasing thanks to the botanists' social network Telabotanica. It is being developed within the Pl@ntNet 7 project. Figure 6.2 shows some samples of this dataset.

The datasets we used differ fundamentally from various points of view, beginning with the number of visual object categories included in each database and the number of images used during training and prediction. Table 6.1 summarizes these differences. Note that the number of training images displayed corresponds to the number of positive images. Moreover, the negative image samples (i.e. counter-class) are randomly chosen from the opposite categories. (Ground truth files are necessary to check for possible overlaps when multiple objects happen to coexist in the same image.) For each object category we trained, we kept around the same number of positive and negative images. This decision is sometimes viewed as problematical since for a small number of positive training images, the number of the negative images will not be sufficient to cover the opposite categories. But in reality, it could be a good criterion to measure the capacity-of a given object class model-to generalize and to judge its discriminating ability. Moreover, and since the learning is completely statistical, maintaining a balance between the number of positive 7. http://www.plantnet-project.org/papyrus.php?langue=en and negative images may sometimes help to avoid possible problems which could derive from imbalanced or skewed data.

The other existing differences in the datasets include the types of objects dealt with (rigid or deformable), specificity (of the same appearance as in OxfordBuilding which is a collection of landmarks, or generic as in PascalVOC), object position and scale variation (BelgaLogos has small objects in different image positions while Caltech objects have almost the same scale and occupy the center of the image) and end-user type (PlantLeaves is mainly intended for botanists while ImagEval is aimed at web users).

Caltech-256 [START_REF][END_REF]] was particularly used in many of our experiments. It has the advantage of comprising many object categories, and thus inter-class variability is very high. Moreover, when dealing with object-based retrieval and for any object category, the average precision measure would be very low according to a random sorting of all the images in the database (i.e. low bias with a random prediction). In this perspective, BelgaLogos and OxfordBuilding use additional images as distracters in the prediction stage. However, the number of relevant images used in prediction is the same number used in training. For the training, we also included some distracters when constructing the negative sets.

Local features

In our experiments, we used five types of local descriptors. They are: SIFT [Lowe 2004], SURF [START_REF] Bay | [END_REF]], ASIFT [Morel 2009], DIPOLE [Joly 2007] and STD GLOBAL. Note that the source code we used (whether provided (i.e. publicly available) or developed) is in C++.

SIFT and SURF are two successful state-of-the-art descriptors used in object recognition. The implementation of SIFT is publicly available [START_REF] Vedaldi | [END_REF]]. The source code of SURF was provided by the OpenSURF library 8 .

ASIFT is an extension to SIFT. It was proposed to be a fully affine invariant descriptor.

The implementation is available at http://www.ipol.im/pub/algo/my affine sift/. DIPOLE refers to dissociated dipoles [Joly 2007]. It is mostly used in near duplicate search applications and is robust to many image distortions including partially affine transformation. We computed our descriptors on color Harris interest points [START_REF] Gouet | [END_REF]] using the source code developed by the Imedia team (INRIA). STD GLOBAL is the concatenation of three global descriptors used here locally: EOH (i.e. a classical edge orientation histogram which is a histogram computed from gradient directions quantized into 8 bins and whose points are located at Canny edge detector), Fourier and Hough based descriptors [Ferecatu 2005] were computed in a fixed window size 65 × 65 centered with respect to interest points extracted using the Harris detector. These descriptors were also developed by Imedia.

Details about the maximum number of descriptors per image used in each dataset and the dimension of the descriptors are given respectively in tables 6.2 and 6.3.

Algorithm parameters

The parameters of our method were tuned as follows ξ = 10 -6 and ε = 1 80

8. http://www.chrisevansdev.com/computer-vision-opensurf.html are given by:

P recision = (# relevant images) ∩ (# retrieved images) (# retrieved images) (6.1) Recall = (# relevant images) ∩ (# retrieved images) (# relevant images) (6.2) AP = ∑ N n=1 P (n) • rel(n) # relevant images ; rel(n) = { 1 if relevant 0 otherwise (6.3)
we also used the number of the visual keywords in the model to measure the reliability of feature selection. On the one hand, this number reflects the complexity of the model and consequently the prediction time. On the other hand, the lower this number is, the easier the interpretability of visual keywords. We discuss interpretability in the next chapter where we will also use the P@n measure to evaluate user interactivity. It is the precision computed at the cut-off rank n (i.e. after n retrieved images). This measure is also used in the formulation of AP. In equation 6.3, it is denoted P (n).

Comparison with [Opelt 2006]

In order to evaluate the L 1 -regularization and to test whether it is of interest in generating sparser models than standard boosting procedures, we compared our method LARK to [Opelt 2006] (hereafter referred to it as Opelt06, and which uses our own C++-based implementation). We carried out various experiments in order to compare performance, efficiency and some of the strong and weak points of each algorithm. We particularly stress the effectiveness vs. the number of features composing the model.

Average precision and prediction time

Table 6.4 gives the results obtained for all Caltech object categories but explicitly details twenty-six categories. It also shows the average performance measured over these categories as well as the average over all database object categories. On the right side of the table, we see the number of hypotheses used in each object model for both algorithms. Besides LARK and Opelt06, we compared the results to a random selector which builds a model from five hundred hypotheses for each category. The weights of these hypotheses are all equal to 1/500 and their respective radii are defined by Eq. (4.10). Note that the performance shown for the random selector is an average over three different runs.

LARK and Opelt06 results are divided into four groups. The first and the second groups are composed of object categories where LARK outperforms Opelt06 in AP, whereas the third and the fourth groups contain object categories where Opelt06 is better. The common point between the first and the third groups is that the number of features selected by LARK is fewer than that selected by Opelt06-which is not the case for the second and the fourth groups. On average, LARK outperforms Opelt06 in AP and selects fewer features to build the model.

The behavior we seek from LARK is illustrated by the first group: higher precision with fewer features. The second and the third groups are rather ordinary because we usually expect a higher performance when the model involves a large number of features. The two first groups also reflect the stop condition problem of AdaBoost. In fact, AdaBoost sometimes stops prematurely because one hypothesis fits the data well (i.e. the classification error is zero). On the other hand, it is sometimes forced to stop after reaching the limit of five hundred hypotheses. The prediction time results of the third group are presented in table 6.5. They highlight our high gain in time compared to the loss in precision shown in table 6.4. Note that the prediction method used here is exhaustive. This choice doesn't favor real-time interactive search applications but it was made here in order to compare the real performances of both algorithms without introducing any bias from index structures and range queries. It is worth pointing out that the prediction time is linear with respect to the model size. Finally, the fourth group (i.e. 043.coin and 177.saturn) behaves worse than Opelt06-with more features selected and a lower AP. This case is very rare (only 15 categories from the 256 categories) which explains the fact that, on average, LARK performs better both in average precision and prediction time. Yet the precision-recall curve, given by figure 6.3, shows that Opelt06 has a slightly better precision than LARK for the first images returned, then LARK becomes better. After presenting the results of the Caltech dataset in detail, we provide a summary of the results of all the datasets in table 6.6. This table shows that LARK AP is better than Opelt06 AP in five datasets. Moreover, in the three other datasets (i.e. where Opelt06 is better), we see that the average number of features in the Opelt06 model is always 500. This means that there were no categories that overfitted the training data. Despite this relatively high number of features, Opelt06 was only better by 1.6%, 1.3% and 1.5% respectively in ImageNetSmall, ImagEval and PascalVOC. Moreover, in these three datasets, the prediction time needed by Opelt06 is ten times the prediction time needed by LARK (on average). Looking closely at the precision-recall curves given in figure 6.4, we can see that apart from the datasets OxfordBuilding and PlantLeaves where Opelt06 performed very poorly, the retrieval performance of LARK and Opelt06 are almost equivalent with a slight superiority of Opelt06 for 40% recall noticeable in BelgaLogos and ImageNetSmall. Nonetheless, we judge that feature selection performed by LARK is always better with fewer visual keywords. It was only in PlantLeaves V2 that the number of features selected by LARK was greater than the number of features selected by Opelt06. Again, and from a retrieval perspective, it is clear in this case that the Opelt06 model is not optimal with a 40.2% AP less than LARK. Notice also that, on average, LARK AP exceeded Opelt06 AP by 11.1% and the prediction time needed by LARK models is one third the time needed by Opelt06 models. 6.2.2 Overtraining: the effect of increasing the model size This experiment is intended to measure the increase in performance that will normally occur when selecting more visual features in the model. It was carried out on four of our prepared datasets: Caltech, ImageNetSmall, ImagEval and PascalVOC. We made several prediction runs each with a limited number of features in the class model. At a given run k, we only kept the first k-hypotheses that had the strongest weights. We varied k from 1 to 500 and we registered the AP results as well as the number of features m ki used by the category i (m ki ≤ k ; 1 ≤ i ≤ N c where N c is the total number of the categories present in the dataset). Note that m ki is equal to k when the model comprises at least k hypotheses and it is strictly inferior otherwise. After that, and for each k, we computed the average number of hypotheses used:

q k = 1 N c N c ∑ i=1 m ki
This experiment was carried out with both LARK and Opelt06. The results are shown in figure 6.5 for comparison, and the different curves give a global overview of how each algorithm behaves. As expected, the more visual keywords we select, the higher the average precision. In general, AdaBoost continues to select more features even if the gain in AP is very small or insignificant. This is known as overtraining. In this situation, however, BLasso stops. This highlights the fact that BLasso judges the overall model consistency after each single step: any hypothesis to be added must significantly contribute to increasing the performance. This experiment, while not precisely giving the optimization path driven by BLasso, demonstrates the smooth behavior of our method. For Caltech and ImagEval, we notice that Opelt06 is slightly better than LARK in the early stage, and after that, LARK is better. On the other hand, for ImageNetSmall and PascalVOC, feature selection by LARK is clearly better from the very first visual keywords selected. Moreover, for Caltech and PascalVOC, LARK stops selecting features just a few steps before Opelt06 performance becomes nearly constant. In ImagEval, we remark that the curves of LARK and Opelt06 are very close until LARK stops. At this phase, we notice a sudden change in the Opelt06 curve: it moves from a nearly constant performance (along a segment of eight features) to an increase with a small slope, to become constant again.

In ImageNetSmall, we see that for a given number of features (in the model), LARK has a far higher performance than Opelt06. The gap takes its highest value 15.6% at the index 14. This observation shows another problematical side of AdaBoost's stopping condition. If we chose T < 200, Opelt06 would underfit the training data. In other words, the model would not be complete (i.e. small in size and not discriminant enough) and hence would not perform well on test data.

Overall, we see that the LARK selection is always satisfactory, achieving an adequate tradeoff between underfitting and overtraining.

Overfitting phenomenon

Looking back at the precision-recall curves presented in figure 6.4, the superiority in performance of LARK over Opelt06 in OxfordBuilding and PlantLeaves datasets is intriguing, particularly because their performance is quite similar in the other datasets. In this section, we will see that this result is due to the overfitting of AdaBoost. Although it was previously observed in Caltech, overfitting here is more noticeable. Table 6.7 is a comparison between LARK and Opelt06 on the OxfordBuilding dataset. It shows that for six object categories, Opelt06 stops after selecting only one visual feature. This phenomenon happens every time AdaBoost selects a hypothesis whose classification error is exactly zero. Therefore, it memorizes the training data perfectly rather than learning to generalize. We notice that, in general, when AdaBoost doesn't overfit (500 hypotheses), the number of visual keywords selected by BLasso is relatively small (apart from the "radcliffe camera" category). This explains the 5.7% increase in performance of Opelt06 (cf. table 6.7). On the other hand, looking closely at the precision-recall curve (cf. figure 6.6-a), we see that both algorithms behave nearly identically for 40% recall. This observation is also true for the PlantLeaves dataset. We will limit ourselves here to presenting only the results of PlantLeaves V1 (cf. table 6.8) since it has fewer categories than PlantLeaves V2, and hence the results are more readable. In this dataset, and for the categories where no overfitting was observed, Opelt06 outperforms LARK by 4.3%. This increase does not greatly affect the first images to be retrieved. In fact, the precision-recall curve (cf. figure 6.6-b) states that retrieval is the same for 20% recall. We also notice that, as in OxfordBuilding, when AdaBoost overfits, BLasso chooses more visual features than it "usually" does. This observation also coincides with using relatively few training images, and so we believe that when AdaBoost easily overfits, BLasso tries to generalize by selecting more visual features.

Generalization capabilities

This experiment aims to measure the extent to which the visual keywords generated by LARK can be generic. As we mentioned earlier, the selection of ImageNetSmall object categories was intended to be a subset of Caltech visual categories. Therefore, we can predict the same concepts belonging to Caltech using the visual keywords generated from ImageNetSmall. Results are presented in table 6.9. We notice that the visual keywords learned from the ImageNetSmall training set outperformed the Caltech models in six categories and that they also did better, on average. This proves that the models generated are generic in the sense that they don't degrade and even improve retrieval results. Therefore, they may be applied to various test databases. Our second experiment is an attempt to build a hierarchical search engine that can semantically provide models for top level concepts and their subconcepts. It was carried out using the ImageNetSmall dataset. The idea is to draw together the camel, penguin, snail and zebra categories under the concept animal, then the laptop, revolver, tennis racket and watch categories under the concept man-made and finally the sunflower and tomato categories under the concept vegetation. For training purposes, we used 30 images for each sub-concept. In summary, there were 120 images used in animal and man-made concepts and only 60 images used for vegetation. For prediction, we used a total of 13, 363 images. AP results are given in table

Combining multiple visual features

Using various description types is a major key to improving the prediction accuracy. The experiments presented here are intended to show to what extent this claim is true. They were carried out on four datasets: Caltech, OxfordBuilding, PlantLeaves V1 and PlantLeaves V2 (cf. table 6.2). For each dataset, we computed the AP of each visual descriptor individually and we compared them with the AP obtained by the combination of all the descriptors.

The AP results of Caltech are shown in table 6.11. They are clustered into two groups. The first group comprises the object classes where both descriptors (SIFT and SURF) combined together achieve higher performances than each single descriptor, whereas the second group is composed of classes where the combination works less well than at least one of the descriptors. It is worth mentioning that for some object classes, SIFT performs much better than SURF whereas, for other classes, the opposite is true. Table 6.11 presents eight categories where SIFT is better and four other categories where SURF is. On average, SIFT is better than SURF and the collaboration of both is even better. One may notice that, on average, the total number of the visual keywords selected when using both descriptors is greater than when each descriptor operates individually. However, we estimate that these results are satisfactory since the increase in AP (i.e. 30%) is higher than the increase in the number of features (i.e. 26%). Besides, keeping less than twenty visual keywords is suitable from an interpretability point of view.

The conclusions drawn from the results of Caltech are also the same for the other datasets. That is, the overall performance (i.e. the average on all object categories) of descriptor combinations is better than using one descriptor at a time and, the number of visual keywords selected with descriptor combinations is higher than the number of visual keywords selected by any descriptor used alone. Furthermore, for some object categories, a given de-scriptor combination may give a worse AP than one of the descriptors. Yet the reason for this behavior is unclear.

The results of OxfordBuilding, PlantLeaves V1 and PlantLeaves V2 are given respectively in tables 6.12, 6.13 and 6.14. For conciseness, and for each dataset, we only kept the average over all its object categories.

Adding a counter-class model

Discovering what is not the object may turn out to be a useful clue to knowing what the object is. From this perspective, apart from the object class model, we added a counter-class model. That is, we learned the negative class against the object class. The main drawback is that the number of visual keywords is nearly double. The final classifier is the resulting sum from both models: H(x) = H 1 (x) + H 2 (x) where H 1 is the strong classifier of the object category and H 2 is the strong classifier of the opposite model. Let us take a weak classifier h ′ belonging to the counter-class and suppose that it is associated with the feature F ′ and the discriminative radius R ′ . This classifier will output

H 1 (x) = ∑ i a i h i (x) and H 2 (x) = ∑ j b j h ′ j (x)
h ′ (x) = { -1 if d(F ′ , x) ≤ R ′ +1 otherwise
The experiment covered all the object categories of Caltech. For some object classes, the AP significantly increased or decreased. For others, it remained nearly constant. Table 6.15 illustrates some of the results where large changes occurred.

In fact, the changes recorded in AP may happen for various reasons. One of these is that the object doesn't always cover an entire test image. Sometimes, it constitutes only a small region. In this particular case, when adding a counter-class model for an image where there exists one or many negative objects-apart from the positive object we are looking for, weak classifiers of the counter-class model (i.e. h ′ j (.)) will output -1 because they will find objects inside their discriminant radii. In other words, saying that there are negative objects in the image doesn't necessarily mean that there are no positive ones. This behavior, although correct, raises a serious problem by neglecting the object we are looking for. Given a test image I t , four possible scenarios could occur:

-I t contains at least one object:

-

if d(F ′ , I t ) ≤ R ′ ⇒ bad classification -if d(F ′ , I t ) > R ′ ⇒ good classification -I t doesn't contain any objects -if d(F ′ , I t ) ≤ R ′ ⇒ good classification -if d(F ′ , I t ) > R ′ ⇒ bad classification

Geometric consistency

So far, we have only evaluated our method using simple visual keywords which are described by only one local descriptor. We now evaluate LARK taking into account the local geometric constraints described in section 4.4.

Here, each visual keyword is represented by a structured set of local features. To make a comparison with standard boosting, we also extended the work by Opelt [Opelt 2006] to a geometrically consistent matching. We will refer to this method as GC Opelt. The comparison results are given in table 6.16. They summarize the AP measured for LARK, Opelt06 and GC Opelt in all the datasets. Both BelgaLogos and OxfordBuilding datasets showed an increase in performance using the geometric approach either with LARK or GC Opelt. This result confirms that a geometric matching strategy is useful when dealing with rigid objects, regardless of their relative size and scale in images. We can also notice that GC Opelt AP is better than LARK AP by 2.7% in BelgaLogos and 1.4% in OxfordBuilding. Given the average number of features selected by GC Opelt, which were respectively 478 and 500 (cf. table 6.18), we conclude that the geometric consistency approach helps Ad-aBoost to overcome the overfitting phenomenon. This is because weak hypotheses (which consist in structured coherent sets of interest points) are more discriminant than those hypotheses built with one feature per visual word, and which allow an error rate of zero to be reached quickly. On the other hand, the average number of visual keywords selected by LARK drops from 78.4 to 44 and from 211.1 to 32.5 respectively in BelgaLogos and OxfordBuilding. This observation concurs with the results presented in section 6.2.3 and shows again that while AdaBoost is greedy, BLasso feature selection is more compact and meaningful.

Looking at the prediction time (cf. table 6.17), we conclude that the increase in the GC Opelt AP with respect to the LARK AP is not objectively advantageous since the prediction time needed by GC Opelt models is nine times (respectively almost thirteen times) more than the time needed by LARK models to predict on BelgaLogos (respectively OxfordBuilding). On average, the prediction time by GC Opelt models is seven times greater than the prediction time by LARK models. Table 6.16 also shows that using the simple approach gives better performances in Caltech, ImageNetSmall, ImagEval and PascalVOC. These datasets are characterized by generic object categories with no fixed appearance. However, applying geometric consistency on PlantLeaves V1 and PlantLeaves V2 gives better results with GC Opelt and lower results with LARK. On average, we see that the number of visual keywords selected by LARK using the geometric approach is always small. very short time. However, index structures are usually based on approximate range query search, and hence the retrieval performance may be reduced.

In our experiments, we relied on the state-of-the-art index structure presented in [START_REF] Joly | [END_REF]]. It is a multi-probe LSH that defines a reliable a posteriori model taking into account some prior knowledge about the queries and the objects to be retrieved. It is based upon a nearest neighbor search. The principle of this method is to visit the most probable hash buckets of a given hash function according to their posterior probabilities. More precisely, the method selects the minimal set of hash buckets such that the global probability is higher than a quality control parameter α. This parameter controls the retrieval quality with respect to the gain in search time.

The experiments presented here only deal with our method. Besides the exhaustive mode where α = 1, we carried out experiments with α = 0.8. Note that the same value of α used in training is also used in prediction. The results obtained are shown in tables 6.19 and 6.20. As expected, we notice that the performance of the exhaustive mode is always better with the simple approach (on average, a gain of 7.8% in AP). However, in the geometric approach, there were three datasets with the approximate search (i.e α = 0.8) that outperformed the exhaustive search. These were BelgaLogos, OxfordBuilding and ImagEval. From the previous section, BelgaLogos and OxfordBuilding showed an increase in the AP with the geometric approach because they categorize rigid objects with same shape and appearance. Here, the approximate search gave even better results than the exhaustive search. For ImagEval and with α = 0.8, notice that the AP with the geometric approach (cf.table 6.20) is slightly greater than the AP with the simple approach (cf.table 6.19). This was not the case with the exhaustive search where the simple approach clearly outperformed the geometric consistency approach.

In table 6.20, we can also notice that the average performance over all the datasets is almost equivalent between setting α to 1 and setting α to 0.8. Therefore, we conclude that approximate search is much more effective when using the geometric approach. This result supports the findings in [Law- Figure 6.8 presents the tradeoff between retrieval quality and search time when varying the control parameter α. The curves are generated using the simple approach and are an average over four datasets: BelgaLogos, ImagEval, OxfordBuilding and PlantLeaves V1. We see that when α varies from 0.2 to 0.6, the prediction time increases with a small slope (i.e quasi constant) while the AP increases significantly. In this case, there is no tradeoff since the gain in performance is worth the extra seconds needed in prediction. On the other hand, the tradeoff is clear when α > 0.6. In fact, we see that the search time increases with a very steep slope while the performance continues with almost the same slope. Chapter 7

Interpretability and Interactivity Experiments

The greatest challenge to any thinker is stating the problem in a way that will allow a solution. Bertrand Russell T HE main common measures used for evaluating the predictive accuracy of content-based image retrieval systems and the learning algorithms involved are precision and recall [START_REF] Dionysius | How to Complete Performance Graphs in Content-Based Image Retrieval: Add Generality and Normalize Scope[END_REF]]. However, understanding the models generated plays a key role for both computer vision experts and end-users. In fact, most shortcomings of computer vision techniques could be easily understood and corrected by end-users if we provided them with an intuitive visual representation of the trained object models. This chapter is intended to evaluate user interactivity. Since our interactive retrieval method is based upon visual keywords, we will first assess the merits of LARK feature selection from a comprehensibility perspective.

How interpretable are our visual keywords?

Beyond retrieval performance, an important advantage of selecting concise and meaningful visual keywords is to provide users with a better understanding of the retrieval capabilities of a given trained model. In this section, we present some of the visual keywords representing our models. Recall that these visual keywords are regions extracted around the selected interest points with a representation that takes into account the window size used in the description. Furthermore, they are presented in a descending order according to their prediction weights. The patches we present here are intended to shed some light on the numerical results given in the previous chapter.

Visual interpretation of the quantitative results

Interpretable models help to analyze quantitative results. In this section, we provide some explanations of the experiments described in the previous chapter.

Interpretability of overfitting and overtraining

We first compare the feature selection of LARK (which uses BLasso) with [Opelt 2006] (which uses AdaBoost and which is referred to as Opelt06). The visual keywords presented here correspond to some object categories of the Caltech dataset, and whose quantitative results were given in table 6.4. Figure (7.1-A) shows both models of the 137.mars class. We notice that among the large number of the visual keywords selected by Opelt06, many are repeated. However, each visual keyword corresponds to a separate hypothesis having its own discriminant radius. This observation doesn't exclude the fact that these components are highly correlated, thus resulting in a poor prediction compared to the twelve visual keywords provided by LARK. In addition, this case is a clear illustration of AdaBoost overtraining and concurs the quantitative results presented in the previous chapter (cf. section 6.2.2). On the other hand, and with the 037.chess-board category (cf. figure 7.1-B), Opelt06 failed to generalize. In fact, AdaBoost stopped quickly and couldn't prevent overfitting. As a result, the prediction results are poor compared to LARK. We can state that, in various cases, LARK selects the most interesting and reliable visual keywords of the object class. For the 037.chess-board category, although some visual keywords selected by LARK may seem to be somehow similar, they differ slightly by an affine geometric transformation (to which neither SIFT nor SURF is invariant). The question raised here then relates to the descriptor strength rather than the learning algorithm.

Interpretability of combining various types of description

Learning object categories and image features are definitely descriptorrelated. Theoretically, adding more descriptions should give better results as shown in the previous chapter. However, in general (i.e average on all the visual object categories), this was not the case for all the object classes. In fact, some classes underwent a big reduction in the model size (i.e. 146.mountainbike and 204.sunflower-101) which corresponds to a 20% loss in AP versus a 61% gain in reducing the number of visual keywords. For others, there is no clear answer: quantitatively, numbers don't reveal any improvement and qualitatively, interpreting an increase or a decrease in a descriptor performance by relying on visual patches is not obvious, mainly when these patches are parts from the object category. An illustrative example is given in figure 7.2.

Interpretability of adding a counter-class

Defining the opposite category in order to learn a visual concept is by no means trivial. We may speculate about the opposite of a motorbike or the opposite of the American flag! The choice of negative examples must certainly take into account the composition of the test database. In addition, this choice must be as varied as possible in order to cover all possibilities. Yet it is statistical learning and the training data distribution may differ from the data to be predicted.

Our visual keywords allow the counter-class effectiveness to be interpreted visually. To illustrate the idea, we selected four categories from the Caltech dataset, two of which showed a remarkable improvement in prediction results. Figure 7.3 presents the two successful categories: 067.eyeglasses and 177.saturn. For these categories, we notice a high contrast between the background and the parts of the object. This creates a high edge response. It follows that the corresponding signatures are very distinctive versus the signatures of the counter-class. In addition, the shapes included in the opposite model are easily distinguishable from those belonging to the category, and we believe that is the key to the increase in performance. On the other hand, both positive and negative models of 086.golden-gate-bridge category have some similarity (cf. figure 7.4). Some patches indeed look homogeneous and almost uniform (i.e. the norms of gradients are very small). This fact made it more difficult to discern between what the object is and what it is not. Finally, the last example we present is the model of the 150.octopus category. Here again we notice that negatives bear a resemblance to positives since the descriptors used are robust to the negative transformation (cf. figure 7.4.B-3). This example is a failure case where the negative model is not statistically discriminant. That is, the negative images which were randomly chosen formed a small set (not large enough to cover variability) and were in some way "similar" to the object category. Thus, the learning algorithm concentrated on discerning between these examples rather than on generalizing.

Hierarchical retrieval

In this section, we show visually how LARK is able to summarize the visual keywords of higher semantic concepts. Figure 7.5 presents the visual

Interpretability of visual keywords ambiguity

An ambiguous visual keyword is a visual keyword that can fit two or more visual concepts. In other words, and by analogy to text, it is a word that has more than one meaning. Ambiguity of visual keywords can be a major bottleneck for both prediction accuracy and human interpretation.

Two examples illustrating the influence of ambiguity on prediction are shown in figures 7.6 and 7.7. They present the model armoured vehicle belonging to the ImagEval dataset with the prediction matches in two (unseen) test images. The visual keywords were spread above and below the images to provide a better representation. In figure 7.6, we see that there are two visual keywords with a clear edge that matched the license plate of a car and the belt of a person. These same two patches matched, in figure 7.7, the roof of a building. Another ambiguous patch, which is highlighted in pink in figure 7.6, matched the head (hair) of a person. These "false" matches (i.e. they are numerically good and semantically correct but they are supposed to match armoured vehicle objects) can affect the retrieval accuracy by assigning high scores to images that are irrelevant to the concept being sought. Notice the windshield visual keyword, highlighted in light green in figure 7.7, that correctly matched the vehicle. Although correct, this visual keyword is still ambiguous without a context.

Description limitation

It happens that a visual keyword is perfectly understandable by humans but that it may sometimes fail to perfectly match the same visual concept. In fact, and in this case, the computational representation of the descriptor cannot encode the semantics behind the visual keyword. This semantic gap is shown in figure 7.7 where two visual keywords "tires" falsely match the headlights of the vehicle, although in this case, the retrieval performance of the concept armoured vehicle would not have been affected. A second example, which can however negatively affect retrieval results, is given in figure 7.8. Here, the clarity of the sunglasses patch didn't prevent the machine from confusing this object with the side of a stadium. Another case of description limitation is given in figure 7.9. The descriptor robustness allows all of the five sunglasses visual keywords to be matched with two pairs of spectacles. Despite the high semantic link, returning this image among the first ranked results is considered to be irrelevant to the query. Reducing the semantic gap can be achieved by considering geometric coherence between sets of interest points.

Applying geometric consistency

Applying the geometric approach described in section 4.4 can help to locate small and complex objects characterized by fixed shape and appearance. An example is given in figure 7.10. Note here that each visual keyword is composed of a structured set of interest points. Therefore, for a given patch, there is a set of interest points that is the best set that verifies the coherence of the affine transformation. In our representation, the position of the circle center corresponds to the central interest point belonging to the matched set.

Paradoxically, some objects are difficult to characterize due to their simplicity (i.e their lack of informative content). Take for instance the logo Nike. Using our BelgaLogos training dataset defined in the previous chapter, there were only eight relevant visual keywords to the concept (cf. figure 7.15), and in general, we were not able to correctly locate the logo in test images. This is because the maximum number of descriptors used per image is not sufficient to cover the particularity of this object (at most, there were three points that describe the object and its context). Therefore, we decided to carry out another experiment by keeping the same training data (i.e 58 images for the object class) but with a very high number of descriptors per image. We used the ASIFT descriptors with a maximum of 20, 000 points per image. This generated 1, 058, 455 local features belonging to the object category. It is actually of interest to test the sparsity of the feature selection given this high number of input features. There were 127 visual keywords selected, and they are presented in figure 7.11. From the patches displayed, we estimate that the selection result is good. This figure also illustrates the semantic gap discussed earlier. In fact, there are two logos on a soccer ball (i.e two patches) that matched an eyebrow and the bottom of the nose of the player.

Notice the confusion that the Nike shape can engender. The model includes some noses, a thumb, T-shirt creases, etc. Figure 7.12 shows how the eyebrow patch (4 th row, 4 th column) matched the logo on the player's wristband. We can also notice that the ASIFT descriptors used here are sensitive to color inversion (visual keywords with a white background match image features with a white background and vice versa). We can think of making them robust by taking into account the sign of the Laplacian of the blob detected, but this could be a double-edged sword (consider the example given in figure 7.4-B).

Interaction with the visual keywords

In the previous section, we showed that LARK visual keywords allow most of the known machine learning shortcomings (overfitting, opposite class, context, etc.) to be easily interpreted visually. In this section, we will try to evaluate the benefit of interactivity using our GUI interface described in chapter 5. As discussed, and as shown from some screenshots, users have the possibility to interact with the models by picking and re-weighting the visual keywords that best represent the visual concept they are looking for. They can indeed emphasize the object scale, context, relative pose and/or appearance. They can also discard ambiguous and contextual irrelevant words. Furthermore, they can create "sub-concepts" from the initially available patches.

For evaluation purposes, the problem is to create a ground truth for each user-specialized query. Suppose, for example, that the user chooses some visual keywords that correspond to "tires" from the initial model of the armoured vehicle concept. Images relevant to this query may include some images that are not related to the parent concept (cf. figure 7.6 and 7.13), and may exclude other images like those including caterpillar-tracked tanks or which contain armoured vehicles with no visible tires (i.e the image is cropped).

Generating a ground truth is labor intensive and error-prone considering the size of the datasets. Therefore, we decided to adopt the P@n measure (cf. section 6.1.4) to compare the performance with and without model specialization. To make the evaluation task easier, we avoided constructing sub-concepts. The idea is to keep, for a given visual category, only the relevant patches by discarding any contextual, ambiguous and/or irrelevant visual keywords. We present the results of three object categories: Adidas-text and Nike from the BelgaLogos dataset, and Magdalen from the OxfordBuilding dataset. The usual words used for querying the search engine are given respectively in figures 7.14, 7.15 and 7.16, and the results are presented in tables 7.1, 7.2 and 7.3. They all show that filtering out unrelated patches enhances the retrieval performance. The Adidas-text model was particularly good at all levels. Going from a cut-off of 10 to 50, the precision should normally decrease, which is not the case here. This is because-apart from a few irrelevant images-some of the top ranked images included the Adidas logo without the text (which is understandable from the visual keywords used for querying). For the two other categories, the precision at the first levels for the specialized models is always better. It outperformed the precision of the initial models up to P@30, then it became worse. From this observation, we understand that the full model is more generalizable. In fact, it summarizes intra-class variability better than the specialized model, which only allowed the images related to the keywords it comprises to be top ranked.

During our interactive experiments, we noticed that it is possible for a single patch not to perform well if it is used alone, even if it is interpretable enough for a human. There are two possible explanations for this. The first ALL visual keywords Specialized P@10 0.3 0.6 P@20 0.2 0.75 P@30 0.1333 0.8333 P@40 0.1 0.825 P@50 0.08 0.86 Table 7.1: Comparing precision with and without model specialization for the Adidas-text category (BelgaLogos, retrieval from 9, 476 images).

ALL visual keywords Specialized P@10 0.1 0.6 P@20 0.2 0.35 P@30 0.23 0.33 P@40 0.325 0.25 P@50 0.28 0.24 Table 7.2: Comparing precision with and without model specialization for the Nike category (BelgaLogos, retrieval from 9, 476 images).

ALL visual keywords Specialized P@10 0.9 0.9 P@20 0.7 0.8 P@30 0.56 0.6 P@40 0.525 0.475 P@50 0.46 0.38 possible cause is that our visual representation of the patch (gray-scale image corresponding to the description window of an interest point/a set of interest points) doesn't faithfully reproduce the information the descriptor characterized (i.e. semantic gap). The second explanation is that, statistically speaking, the database may be somehow skewed so that a single feature cannot be very discriminative. This problem is illustrated in figure 7.17 by the revolver category. The full model comprises only two visual keywords which are shown at the top of the figure and their corresponding precision-recall curves are given below. Compare the precision for the first ranked results (say 5% recall), we see that the full model behaves quite well while each feature, alone, does not.

Chapter 8

Conclusion

Success isn't permanent, and failure isn't fatal. Mike Ditka

Synthesis

T HIS thesis addresses the problem of building humanly interpretable visual models in the context of object retrieval in image collections.

Our motivation was that most shortcomings of computer vision techniques could be easily understood and corrected by end-users if we provided them an intuitive visual representation of the trained object models.

In that way, we first introduced the notion of visual keywords by analogy to visual words (used in many visual information retrieval systems) and to common keywords (used in text indexing and search) and we set our objectives as readability, conciseness and disambiguation. The idea is to represent a given object, object class or visual concept by a concise set of image patches that a user can easily handle and interpret. The problem is then to select, among all possible patches of the training images, the most discriminative subset, while meeting the constraint of conciseness in the number of patches.

We showed that, when using an appropriate high dimensional and sparse embedding of local features, this objective can be formulated as a discriminative learning problem with an L 1 -regularization cost to enforce conciseness. To efficiently solve this problem, we then adapted an existing algorithm called BLasso-that approximates the exact solution of the Lasso path with a boosting-like procedure-to deal with a discriminative and a multiple-instance learning problem rather than a common feature selection. We named this algorithm LARK. We showed in the experiments that, on average, the feature selection by our method is always better than the feature selection performed by a state-of-the-art method based on the AdaBoost algorithm. The reason for this is that the stop condition of AdaBoost is unclear and, in some ways, problematical. Choosing a large number of hypotheses normally leads to a better precision score but encourages overtraining. That means that many selected features happen to be correlated, and their joint collaboration which is intended to increase the average precision is almost always insignificant considering the linear increase in prediction time. AdaBoost sometimes avoids overtraining but tends to overfit, particularly with a reduced number of training images. In fact, it stops after selecting only few weak learners, which inevitably leads to a poor prediction. Using BLasso overcame this issue by stopping once the intra-class variability and inter-class differences have been efficiently learnt. Furthermore, we showed that both algorithms perform similarly for the top ranked images (from 20% to 40% recall) when AdaBoost doesn't overfit, and we registered a clear superiority of our method when it does. In this second case, we noticed a slight increase in the average of the total number of the visual words selected by BLasso. Here, BLasso tries to generalize considering the few images in the training set. We also concluded that it is always better to use various descriptor types to enhance the overall performance.

In order to reduce the ambiguity of the trained visual keywords, we then introduced an alternative approach, making use of local geometric constraints. We therefore replaced the single-feature representation of image patches by structured sets of local features. In this case, the membership function of a given patch in the other images is computed as a geometrically consistent matching in the whole dataset. Using this technique, we obtained a higher performance for rigid visual objects that don't vary much in appearance (e.g. logos), particularly when using an approximative search method. Moreover, we showed that, even with an extremely high number of descriptors, our feature selection performs very well in terms of quality and sparsity as long as the visual objects are encoded in some of these input descriptors. This highlights the interest of using a multiple-instance learning approach.

Finally, we focused our work on how to use the trained visual keywords for efficient retrieval and user interactivity. We first introduced several possible user interactions including eliminating ambiguous visual keywords and emphasizing some object parts and/or appearance. We also pointed out how the semantic gap can have an adverse effect on retrieval performance. Furthermore, we integrated the proposed interactions in GUI allowing for user experiments and we showed numerically that specializing models improves retrieval precision.

Along with the quantitative results, we presented some visual models in an attempt to explain the quantitative results. We showed how straightforward it is easy to manipulate concise models and how our visual keywords allowed for interpretability.

Applications

Visual keywords are a straightforward tool. Our research can be used in various computer vision applications including event retrieval and plant identification to name but two.

Organizing media according to real-life events is gaining ever-increasing interest in the multimedia community. Event-centric indexing approaches are indeed very promising for discovering more complex relationships between data. Time and geographic information, jointly provided with media content, has of course a major role to play, but using visual content as complementary information might solve several limitations of the approaches that rely only on metadata. A typical application would be the following: given a query event record, represented by a set of photos, the task is to retrieve other records of the same event, typically generated by distinct users. In this context, learning discriminative visual keywords representing the event is meaningful. An example of a geometrically consistent visual keyword belonging to a set of pictures representing the event "Myanmar protest" is given in Figure 8.1.

If agricultural development is to be successful and biodiversity is to be conserved, then accurate knowledge of the identity, geographic distribution and uses of plants is essential. Unfortunately, such basic data and information is often only partially available for professional stakeholders, teachers, scientists and citizens, and often incomplete. One noticeable consequence is that simply identifying plant species is often a very difficult task; even for botanists themselves (the so-called taxonomic gap). Computer vision and visual infor- mation retrieval are considered as very promising means of bridging this gap. However it is fundamental that botanists can interact on the trained visual models to control which plant's organs have been selected as an identification key. We believe that LARK is suitable for such supervised learning issues where end-users want to control and understand exactly what the machine did learn.

Perspectives

As we can learn from the experiments conducted, visual word ambiguity not only affects prediction accuracy but also human interpretation and subsequently user interactivity. In this direction, we have begun an experiment to measure the interpretability level of the visual keywords with respect to each type (or a combination of types) of descriptions. More precisely, the experiment consists in determining the rank of the visual keyword at which a given category is recognized by a human. The experiment is to be conducted with several users and various object categories. For this purpose, we built a user interface (cf. figure 8.2) that provides the visual keywords (of a random selected category, which is unknown to users) after selecting one or many description types. The visual keywords are displayed one by one each time users click the button "next". They are given in a descending order according to their predictive weights learned during training. Each time a patch is displayed, users can guess the visual concept these patches belong to. In fact, they can type whatever word comes in mind in a small box. The system automatically filters out the category names that don't match the input text. Along with the possible choices kept, a small picture is jointly displayed with each proposition for better understanding. This experiment is still in progress and should be concluded soon.

In our next work, we will carry out more in-depth tests on description combinations. Although it is more effective on average, we noticed that-for a particular object category-the combination of local descriptors may sometimes have lower precision than if one of these descriptors is used alone. This behavior is not expected since the feature selection mechanism may discard any unreliable descriptors. In addition, we will try other additive constraints than the L 1 -norm, particularly, the adaptive group lasso. The group lasso allows selection in a grouped manner. Therefore, we can focus on some image regions more than others. Yet this necessitates additional annotations and might affect the multiple-instance learning.

The performance of boosting procedures crucially depends on the choice of the weak learner. In this perspective, it is interesting to try out different discriminative boundaries. Rather than using hyperspheres, ellipsoids might, for instance, be used. This would only affect the classification error rate and would not change our image representation.

Since user interactivity is entirely based on visual words, it is necessary to provide a patch representation that faithfully reproduces the actual information which is coded by the descriptor. The intuitive idea is to use the aspects that the descriptor characterizes. However, coming up with an easily understandable representation is not always obvious and should probably be followed by the original image patch so that users can spot what is numerically coded through patch comparison.

The visual words learnt act separately in the sense that each visual word contributes to the classification score without considering the other components of the model. Although we suggested richer visual words built from sets of local features, we might consider a more complex representation that takes into account the spatial configuration between these words. This would allow higher semantical levels to be achieved.

Introducing geometric consistency was one way to demonstrate the flexibility of our method. It is based on the fact that we can choose any similarity measure to rank images, and this choice can vary and be specifically designed for each type of local descriptor. Such flexibility allows us to cope with other types of multimedia documents. We can indeed apply the same mechanism to text, audio and video data, either separately or in a multimodal fashion.

Although current methods used in solving text documents problems are very advanced, our method can still be applied to automatically discover topics and provide the keywords that go with them. Audio and video features can also be processed in the same way that images are. Moreover, indexing videos usually takes into account image frames and audio content simultaneously. Here, we can process each part of the content separately then consider formulating more compound and semantical queries using logical operators.

Web content usually contains documents including text, images and frequently audio and video information. The same mechanism could be utilized to retrieve multimodal documents. The keywords defining the model would be a mixture of all these types of media.

The design of multimodal interfaces is considered to be a separate research area since the interface has to be as interactive as possible, and designers must put a great deal of thought into facilitating human-machine communication. However, we believe that our simple design could work, at least to some extent. In addition to the visual keywords (i.e. image patches) that may originate from different types of description, we could provide textual, audio or video keywords provided that we make a clear separation for each type of media so that users could easily distinguish between the different keywords they are dealing with. Since documents are ranked according to the number of multimodal keywords found, two documents may have the same ranking score but be of different modes. Here, an additional option would be needed to help users to select one mode over another.

  -recall curves for the categories where no overfitting is observed with Opelt06. . . . . . . . . . . . . . . . . . . . . . . 6.7 Adding a counter-class: Precision-Recall curve of Caltech dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.8 Tradeoff between retrieval quality and search time. . . . . . . 7.1 Illustration of the stop condition problem in AdaBoost with two object categories. . . . . . . . . . . . . . . . . . . . . . . . 7.2 Visual patches of 224.touring-bike category. . . . . . . . . . . 7.3 Illustration of the case where adding a counter-class improves prediction. Visual keywords of 067.eyeglasses and 177.saturn categories presented with their respective counter-classes. . . . 7.4 Illustration of the case where adding a counter-class decreases results. Visual keywords of 086.golden-gate-bridge and 150.octopus categories presented with their respective counter-classes. 7.5 Visual keywords of higher semantic concepts. . . . . . . . . . . 7.6 Armoured vehicle model (ImagEval). . . . . . . . . . . . . . . 7.7 Armoured vehicle model (ImagEval). . . . . . . . . . . . . . . 7.8 Sunglasses model (ImagEval). . . . . . . . . . . . . . . . . . . 7.9 Sunglasses model (ImagEval). . . . . . . . . . . . . . . . . . . 7.10 Puma model (BelgaLogos). . . . . . . . . . . . . . . . . . . . 7.11 Nike model (BelgaLogos). . . . . . . . . . . . . . . . . . . . . 7.12 Nike model (BelgaLogos). . . . . . . . . . . . . . . . . . . . . 7.13 Armoured vehicle model (ImagEval). . . . . . . . . . . . . . . 7.14 Specialized Adidas-text model. . . . . . . . . . . . . . . . . . . 7.15 Specialized Nike model. . . . . . . . . . . . . . . . . . . . . . 7.16 Specialized magdalen model. . . . . . . . . . . . . . . . . . . . 7.17 Performance of the revolver category (ImageNetSmall). . . . . 8.1 Event search: an example of a geometrically consistent visual keyword. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Visual word interpretation. . . . . . . . . . . . . . . . . . . . .

Figure 1

 1 Figure 1.1: How computers look at images.

  Figure 1.2: Example of four object categories represented by visual keywords.

Figure 2

 2 Figure 2.1: Simple image matching with Lowe's strategy.

  Figure 4.1: Images taken from the BelgaLogos dataset http://wwwrocq.inria.fr/imedia/belga-logo.html (Nike category).

Figure 4 . 3 :

 43 Figure 4.3: Importance of scale information

Figure 4 . 4 :

 44 Figure 4.4: Image representation.

  Figure 4.5: Unit balls for some values of α.

Figure 4 . 6 :

 46 Figure 4.6: Illustration of the fact that it is preferable to choose a smaller α to get sparser solutions. The schemas are geometric representations in two dimensions showing a least square problem. Solutions occur where ellipses first hit the regularization area. The dashed ellipses show where the solutions would occur if a greater value of α was used. With a smaller α, some coefficients are set to zero.

Figure 5

 5 Figure 5.1: Discarding rotation and normalizing the representation of the patches.

Figure 5 . 2 :

 52 Figure 5.2: Example of an object model: 112.human-skeleton category (Caltech dataset). The visual keywords are displayed in decreasing order according to the predictive weights.

  Figure 5.2 gives an example of a human-skeleton model. The visual keywords are displayed in decreasing order according to the predictive weights. As we can see, the model can be viewed differently (cf. figure 5.3) according to the object parts chosen. This is what interpretability is. The visual representation by keywords, suggested here, is beneficial for both researchers and end-users. For researchers, they can study what the model is composed of. Sometimes, scientists cannot explain their expertise.

Figure 5 . 3 :

 53 Figure 5.3: Different interpretations of the same model.

Figure 5

 5 Figure 5.4: Example of an interactive search

Figure 5 . 5 :

 55 Figure 5.5: Diagram of user interaction.

Figure

  Figure 5.6: Retrieving sunflowers

Figure 5 . 8 :

 58 Figure 5.8: Example of patches to look for a global view of zebras.

Figure 6

 6 Figure 6.1: Sample images from some categories representing each dataset (Some objects are highlighted using a bounding box).

Figure 6 . 2 :

 62 Figure 6.2: Some images forming the PlantLeaves dataset.

Figure 6 . 4 :

 64 Figure 6.4: Precision-Recall curves.

Figure 6 . 5 :

 65 Figure 6.5: Increasing the model size.

Figure 6

 6 Figure 6.6: Precision-recall curves for the categories where no overfitting is observed with Opelt06.

Figure 6

 6 Figure 6.7: Adding a counter-class: Precision-Recall curve of Caltech dataset.

  Figure 6.8: Tradeoff between retrieval quality and search time.

  (a) SIFT-based visual keywords. (b) SURF-based visual keywords. (c) "SIFT+SURF"-based visual keywords.

Figure 7 . 2 :

 72 Figure 7.2: Visual patches of 224.touring-bike category.

Figure 7 . 7 :

 77 Figure 7.7: Armoured vehicle model (ImagEval).

Figure 7

 7 Figure 7.8: Sunglasses model (ImagEval).

Figure 7 . 9 :

 79 Figure 7.9: Sunglasses model (ImagEval).

Figure 7 .

 7 Figure 7.10: Puma model (BelgaLogos).

Figure 7 .

 7 Figure 7.11: Nike model (BelgaLogos).

Figure 7 .

 7 Figure 7.12: Nike model (BelgaLogos).

Figure 7 .

 7 Figure 7.13: Armoured vehicle model (ImagEval).

Figure 7 .

 7 Figure 7.14: Specialized Adidas-text model.

Figure 7 .

 7 Figure 7.15: Specialized Nike model.

Figure 7 . 16 :

 716 Figure 7.16: Specialized magdalen model.

Figure 7

 7 Figure7.17: Performance of the revolver category (ImageNetSmall).

Figure 8 . 1 :

 81 Figure 8.1: Event search: an example of a geometrically consistent visual keyword.

Figure 8

 8 Figure 8.2: Visual word interpretation.

  6.1 Composition of the datasets. . . . . . . . . . . . . . . . . . . . 100 6.2 The maximum number of descriptors per image used in each dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.3 Descriptor dimensions. . . . . . . . . . . . . . . . . . . . . . . 102 6.4 Comparing LARK with Opelt06 for Caltech dataset. . . . . . 105 6.5 Comparing LARK with Opelt06 according to the prediction Comparing the geometrically consistent approach to the simple strategy approach: number of visual keywords. . . . . . . . . . 121 6.19 Tradeoff between prediction quality and response time (Simple approach). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.20 Tradeoff between prediction quality and response time (Geometric approach). . . . . . . . . . . . . . . . . . . . . . . . . . 123

time (Caltech dataset). . . . . . . . . . . . . . . . . . . . . . 106 6.6 LARK vs. Opelt06: results summary. . . . . . . . . . . . . . . 107 6.7 Comparing LARK with Opelt06 (OxfordBuilding). . . . . . . 112 6.8 Comparing LARK with Opelt06 (PlantLeaves V1). . . . . . . 112 6.9 Illustration of prediction on a different dataset. . . . . . . . . 113 6.10 Results of top semantical concepts. . . . . . . . . . . . . . . . 114 6.11 AP measured in three cases: SIFT only, SURF only and the combination of both in Caltech dataset. . . . . . . . . . . . . 115 6.12 Combining visual descriptors (OxfordBuilding). . . . . . . . 116 6.13 Combining visual descriptors (PlantLeaves V1). . . . . . . . . 116 6.14 Combining visual descriptors (PlantLeaves V2). . . . . . . . . 116 6.15 Adding a counter-class model (using LARK). . . . . . . . . . . 117 6.16 Comparing the geometrically consistent approach to the simple approach: average precision. . . . . . . . . . . . . . . . . . . . 120 6.17 Comparing the geometrically consistent approach to the simple approach: prediction time results (in seconds). . . . . . . . . . 120 6.18 7.1 Performance of an Adidas-text specialized model. . . . . . . . 144 7.2 Performance of an Nike specialized model. . . . . . . . . . . . 144 Chapter 1

  Table 6.7: Comparing LARK with Opelt06 (OxfordBuilding).

	OxfordBuilding: categories that don't overfit	PlantLeaves V1: categories that don't overfit
	0.9 Category 0.7 0.8 all souls christ church hertford magdalen 0 0.1 0.3 0.4 0.5 0.6 Precision Opelt 06 0.2 LARK	# images (training) LARK Opelt06 LARK Opelt06 AP 1 # visual keywords 0.9 66 0.8983 0.9141 33 500 271 0.7197 0.8176 24 500 33 0.6474 0.7454 27 500 342 0.0484 0.1111 25 0.4 500 0.6 0.7 0.8 Precision Opelt 06 0.5 LARK
	radcliffe camera 0 0.2 Average	141 0.6 170.6 Recall 0.4	0.8	0.8106 0.8226 1 0 0.6249 0.6822	0.2	328 0.4 87.4 Recall 0.6	0.8 500 500	1
	ashmolean		97		0.7138 0.0127		164	1
	balliol		77		0.2769 0.0061		224	1
	bodleian		107		0.9952 0.0896		949	1
	cornmarket		29		0.5117 0.0047		291	1
	keble		60		0.5376 0.0423		105	1
	pitt rivers		54		1.0000 0.0359		152	1
	Average		70.7		0.6725 0.0319	314.17	1
	Average		116.1		0.6509 0.3275	211.1	227.8
			# images	AP		# visual keywords
	Category		(training) LARK Opelt06 LARK Opelt06
	Acer monspessulanum L	24		0.9983 0.9983	32	500
	Arbutus unedo L			34		0.7078 0.9158	47	500
	Paliurus spina-christi Mill	24		0.6466 0.6976	20	500
	Cercis siliquastrum L		29		0.8091 0.8510	27	500
	Nerium oleander			41		0.9975 0.9962	41	500
	Quercus ilex L			36		0.6584 0.6211	43	500
	Average			31.3		0.8030 0.8467	35	500
	Corylus avellana L			21		1.0000 0.3541	448	1
	Eriobotrya japonica			7		1.0000 0.0253	456	1
	Quercus pubescens			16		0.9589 0.4490	50	1
	Sorbus domestica			7		1.0000 0.8942	933	1
	Crataegus monogyna Jacq	13		0.6543 0.1548	20	1
	Robinia pseudoacacia L	22		0.9963 0.8580	176	1
	Average			14.3		0.9349 0.4559	347.2	1
	Average			22.8		0.8689 0.6513	191.1	250.5
	Table 6.8: Comparing LARK with Opelt06 (PlantLeaves V1).

  Table 6.9: Illustration of prediction on a different dataset. The third column presents AP results obtained by predicting on the Caltech test set with the visual keywords trained with ImageNetSmall training set.

			Average precision
	Category	Caltech model ImageNetSmall model
	028.camel	0.0056	0.0132
	127.laptop-101	0.0388	0.0382
	158.penguin	0.0100	0.0159
	172.revolver-101	0.0128	0.0096
	189.snail	0.0067	0.0178
	204.sunflower-101	0.5670	0.7590
	218.tennis-racket	0.0819	0.0170
	221.tomato	0.0156	0.1018
	240.watch-101	0.0458	0.0792
	250.zebra	0.0933	0.0787
	Average	0.0878	0.1130

  6.10. They are rather promising and demonstrate the feasibility of a hierarchical search engine with our method.

	Category	# features	AP
	animal	36	0.5516
	man-made	22	0.5536
	vegetation	33	0.4224
	Table 6.10: Results of top semantical concepts.

  Table 6.11: AP measured in three cases: SIFT only, SURF only and the combination of both in Caltech dataset.

			Average Precision	Number of visual keywords
		Category	SIFT	SURF SIFT+SURF SIFTSURF SIFT+SURF
		145.motorbikes-101 0.6349 0.7061	0.8068	41	75	76
		177.saturn	0.2890 0.0278	0.4741	34	1	39
	Increase	218.tennis-racket 0.0722 0.0675 232.t-shirt 0.0960 0.0899 251.airplanes-101 0.5368 0.5751 253.faces-easy-101 0.8515 0.7857	0.219 0.1490 0.7218 0.8641	9 52 35 78	24 48 45 61	25 98 56 58
		Average over 119 categories	0.0590	0.0464	0.0816	16.4 16.1	22.7
		146.mountain-bike 0.1243 0.0417	0.0511	32	29	15
		184.sheet-music 0.1910 0.1776	0.1746	29	55	27
	Decrease	204.sunflower-101 0.4251 0.0781 224.touring-bike 0.0809 0.1286 234.tweezer 0.0406 0.1010 235.umbrella-101 0.0775 0.0166	0.2149 0.0892 0.0808 0.053	15 17 4 19	28 22 82 11	5 27 13 25
		Average over 137 categories	0.0285	0.0247	0.0258	15.9 15.9	17.3
	All	Average over the 256 categories	0.0426	0.0348	0.0518	16.1 16.0	19.8

  Table 6.13: Combining visual descriptors (PlantLeaves V1).

			Combination ASIFT SIFT SURF
		AP	0.5672		0.4819 0.3121 0.5078
	# features	303.9		156.5	164.1	133.2
	Table 6.12: Combining visual descriptors (OxfordBuilding).
		Combination SIFT ASIFT SURF DIPOLE
	AP	0.8689	0.6999 0.5532 0.7642	0.6097
	# features	191.1	101.2	116.8	123.3	88.5
		Combination ASIFT SURF DIPOLE STD GLOBAL
	AP	0.6464	0.5810 0.5587	0.3081	0.5094
	# features	466.5		258.9	230.3	137.3	346.2
	Table 6.14: Combining visual descriptors (PlantLeaves V2).

Table 6 .

 6 In order to reduce the processing time in training and prediction, it is useful to use an index structure that can efficiently retrieve kNN objects in a 18: Comparing the geometrically consistent approach to the simple strategy approach: number of visual keywords.

		Simple approach Geometric approach
	Dataset	LARK Opelt06 LARK GC Opelt
	BelgaLogos	0.2008	0.1772	0.2320	0.2590
	Caltech	0.0518 0.0516	0.0450	0.0489
	ImageNetSmall	0.3979 0.4142	0.2234	0.2008
	ImagEval	0.2177 0.2306	0.1660	0.2131
	OxfordBuilding 0.6509	0.3275	0.6871	0.7015
	PascalVOC	0.1285 0.1437	0.0923	0.0965
	PlantLeaves V1 0.8689 0.6513	0.7069	0.8080
	PlantLeaves V2 0.6464 0.2744	0.6101	0.6886
	Average	0.3954 0.2838	0.3454	0.3777
	Table 6.16: Comparing the geometrically consistent approach to the simple
	approach: average precision.
		Simple approach Geometric approach
	Dataset	LARK Opelt06 LARK GC Opelt
	BelgaLogos	317	1, 244	21, 048	187, 990
	Caltech	359	411	42, 748	199, 752
	ImageNetSmall	45	154	2, 366	5, 086
	ImagEval	71	986	8, 992	51, 132
	OxfordBuilding	267	328	11, 433	145, 223
	PascalVOC	46	378	5, 244	33, 882
	PlantLeaves V1	7	12	80	689
	PlantLeaves V2	498	198	3, 049	32, 610
	Average	201	464	11, 870	82, 046
	Table 6.17: Comparing the geometrically consistent approach to the simple
	approach: prediction time results (in seconds).
	6.7 Using an efficient index structure

  To 2007].

		AP	Pred. Time (s)
	Dataset	α = 1 α = 0.8 α = 1 α = 0.8
	BelgaLogos	0.2008 0.1386	317	31
	Caltech	0.0518 0.0381	359	102
	ImageNetSmall	0.3979 0.2834	45	10
	ImagEval	0.2177 0.1878	71	14
	OxfordBuilding 0.6509 0.5672	267	36
	PascalVOC	0.1285 0.1104	46	12
	PlantLeaves V1 0.8689 0.6628	7	1
	PlantLeaves V2 0.6464 0.5457	498	43
	Average	0.3954 0.3167 201.3	31.1
	Table 6.19: Tradeoff between prediction quality and response time (Simple
	approach).

Table 7 .

 7 3: Comparing precision with and without model specialization for the Magdalen category (OxfordBuilding, retrieval from 3, 115 images).

Acknowledgements

Part II Contributions

Chapter 4

Learning Interpretable Models

A fact is a simple statement that everyone believes. It is innocent, unless found guilty. A hypothesis is a novel suggestion that no one wants to believe. It is guilty, until found effective. Edward Teller A S previously stated, our thesis proposes a new supervised object retrieval method, called LARK for "LAsso-Regularized Keywords", based on discriminative visual keywords trained through a LASSOregularized boosting algorithm. This chapter focuses on the learning stage (i.e. the supervised selection of relevant visual keywords from a set of labeled images). The following chapter focuses on the retrieval stage once the visual keywords of a given object class have been trained.

Towards interpretable visual keywords

Visual keywords

We consider a training set S of N images (I i ) 1≤i≤N provided with associated labels l i ∈ {-1, 1}. A training image is labeled as a whole sample. It takes the label +1 if it contains the targeted visual object, and -1 if not.

By analogy with text documents (and as originally suggested by [START_REF] Sivic | [END_REF]]), each image I i is supposed to be described by N i visual words. The definition of the visual vocabulary will be discussed later.

Our objective is to train a discriminative subset of visual words that are supposed to be the most representative words of the targeted visual object. We refer to these automatically selected visual words as visual keywords.

Initial status: all coordinates are zeros and both of the empirical and the Lasso losses are maximal. (L = Γ). We suppose that the vector of parameters β comprises 7 variables.

Make a forward step

(1)

The second coordinate is chosen. It is incremented by ε which is represented by a small red box. λ = λ 1 : λ is initialized such that L = Γ. The active index set I A = {2}.

Backward and forward

We look for the backward step (Only one choice is available.), then we compute the backward losses (i.e. L

(1) B

and Γ

(1) B ). The last forward step decreased the Lasso loss (Γ (1) ≤ Γ

(1) B + ξ) so we force a forward step.

Make a forward step

(2)

The 6 th coordinate is chosen. The active index set 2) and Γ (2) using λ 2 .

Algorithm 3 summarizes the use of ζ n for computing the empirical loss.

Thus, when changing a hypothesis h k in the next iteration, we only need Backward and forward

There are two possibilities for the backward step. Take the one that corresponds to the minimal empirical loss then compute the backward Lasso loss using λ 2 (say the 6 th coordinate). We have Γ (2) ≤ Γ

(2)

The second coordinate is chosen again.

Compute L (3) and Γ (3) .

Backward and forward

Find the backward step and compute Γ

(3) B using λ 3 . It is correct to suppose that that Γ

(3) B < Γ (2) because λ 3 ≤ λ 2 (even though β is the same). The current Lasso loss Γ (3) is however greater than the backward loss so we take the step.

Take the backward step ( 4)

Backward and forward

Search for the backward step. There are m possibilities with

< Γ (k-1) -ξ then take this step, otherwise force a forward step (k) Compute L (k) , λ k and Γ (k) .

Backward and forward

Find the backward step.

Make a forward step (T )

The 7 th coordinate is chosen. The active index set I A = {2, 3, 6, 7}. Relax λ if necessary. λ = λ T ≤ 0 so break. They were empirically determined after several runs on some object categories.

Recall that ε is the forward step attributed to each selected variable. This parameter directly affects the computational complexity: O(1/ε). That is, the smaller ε is, the larger the number of iterations needed for convergence. Our observations revealed that choosing a small ε didn't necessarily lead to better prediction. However, in theory, choosing a large value for ε would not lead exactly to lasso solutions.

ξ is a tolerance parameter, strictly positive, used for algorithm stability (cf. Eq. 4.23). It is decisive for determining backward steps and should be set to a small value. For Opelt's method, we fixed the number of iterations of AdaBoost to T = 500.

Evaluation metrics

To evaluate the retrieval performance, we used the common measures used in information retrieval: precision, recall and average precision (AP). They keywords of the concepts animal, man-made and vegetation which were defined in section 6.3. From a global view, we see that the visual keywords are well related to the concepts defined. However, the proportion of the visual keywords attributed to each sub-concept differs. This is to be expected because the algorithm has to cover the intra-variability which may differ from one sub-concept to another. By analogy to usual categories, say bike for instance, the algorithm learns which parts of the object vary the most. Yet it should be noticed that all of the sub-categories were represented by at least two informative patches despite the model concision-particularly for the concepts where the number of sub-categories is relatively high. Notice, for instance, tentacles of snails in the animal concept and a trigger and a percussion cap in the man-made concept.