Svetlana Lazebnik
email: slazebni@uiuc.edu

Cordelia Schmid
email: cordelia.schmid@inrialpes.frponce@cs.uiuc.edu

Jean Ponce

Semi-Local Affine Parts for Object Recognition

This paper proposes a new approach for finding expressive and geometrically invariant parts for modeling 3D objects. The approach relies on identifying groups of local affine regions (image features having a characteristic appearance and elliptical shape) that remain approximately affinely rigid across a range of views of an object, and across multiple instances of the same object class. These groups, termed semi-local affine parts, are learned using correspondence search between pairs of unsegmented and cluttered input images, followed by validation against additional training images. The proposed approach is applied to the recognition of butterflies in natural imagery.

Introduction

Achieving true 3D object recognition is one of the most important challenges of computer vision. As a first step towards this goal, it is necessary to develop geometrically invariant object models that can support the identification of object instances in novel images in the presence of viewpoint changes, clutter, and occlusion. To date, object representations based on distinctive local image regions (interest points) have shown great promise for recognizing different views of the same object [START_REF] Ferrari | Simultaneous object recognition and segmentation by image exploration[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF][START_REF] Rothganger | 3d object modeling and recognition using affine-invariant patches and multi-view spatial constraints[END_REF] as well as different instances of the same object class [START_REF] Agarwal | Learning a sparse representation for object detection[END_REF][START_REF] Fergus | Object class recognition by unsupervised scaleinvariant learning[END_REF][START_REF] Li | A Bayesian approach to unsupervised one-shot learning of object categories[END_REF][START_REF] Weber | Unsupervised learning of models for recognition[END_REF]. In the latter case, local regions play the role of generic object parts (e.g., eyes of a person or wheels of a car). In this paper, we propose a novel object recognition framework based on composite semi-local affine parts, or geometrically stable configurations of multiple elliptical local affine regions. We introduce methods for learning collections of such parts to represent 3D object classes, and for detecting part instances in test images. An important advantage of our learning method is that it is weakly supervised, i.e., it works with unsegmented, cluttered training images.

The parts proposed in this paper are affinely rigid by construction, i.e., the mapping between two different instances of the same part can be well approximated by a 2D affine transformation. Note that we do not make the overly restrictive assumption that the entire object is planar and/or rigid -it is sufficient for the object to possess some (approximately) planar and rigid components. Because of this non-global notion of affine invariance, our method is suitable for modeling a wide range of 3D transformations, including viewpoint changes and non-rigid deformations. This exceeds the capabilities of most existing part-based category-level recognition schemes [START_REF] Agarwal | Learning a sparse representation for object detection[END_REF][START_REF] Fergus | Object class recognition by unsupervised scaleinvariant learning[END_REF][START_REF] Li | A Bayesian approach to unsupervised one-shot learning of object categories[END_REF][START_REF] Weber | Unsupervised learning of models for recognition[END_REF], which are suited primarily for recognizing fronto-parallel views of objects.

The mechanism for learning semi-local affine parts, which is described in Section 2, is based on the idea that a direct search for visual correspondence is key to successful recognition. Thus, at training time we seek to identify groups of neighboring local affine regions whose appearance and spatial configuration remains stable across multiple instances. To avoid the prohibitive complexity of establishing simultaneous correspondence across the whole training set, we separate the problem into two stages: Parts are initialized by matching pairs of images and then matched against a larger validation set. Even though finding optimal correspondence between features in two images is still intractable [START_REF] Grimson | The combinatorics of object recognition in cluttered environments using constrained search[END_REF], effective sub-optimal solutions can be found using non-exhaustive constrained search. The promise of the proposed framework is demonstrated in Section 3 with an application to the automated acquisition and recognition of butterfly models in heavily cluttered natural images. Finally, Section 4 closes with a discussion of major conceptual issues raised in the paper.

Learning Semi-Local Affine Parts

This section presents the method for automatically identifying collections of semi-local affine parts to represent 3D object classes. The first step is feature extraction (Section 2.1), which consists of detection of local affine regions followed by computation of appearance descriptors. Next, candidate parts are formed by matching several pairs of training images (Section 2.2), and a validation step is used to discard spurious matches (Section 2.3).

Feature Extraction

Detecting local affine regions. We use an affine-adapted Laplacian blob detector based on [START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF]. While a few other affine-and scale-invariant detectors are available in the literature [START_REF] Kadir | An affine invariant salient region detector[END_REF][START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighbourhoods[END_REF], we chose the Laplacian because it finds perceptually salient blob-like regions that tend to be centered away from object boundaries. This detector finds the locations in scale space where a normalized Laplacian measure attains a local maximum and then applies an affine adaptation process (see [START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] for details). The elliptical regions found as a result of this process can be normalized by mapping them onto a unit circle. However, the normalizing transformation has an inherent orthogonal ambiguity, since the unit circle is invariant under rotation and flipping. We resolve this ambiguity by representing the appearance of each normalized patch by rotation-invariant descriptors. Descriptors. In this work, we use two descriptors which complement each other by relying on different types of image information: spin images [START_REF] Johnson | Using spin images for efficient object recognition in cluttered 3d scenes[END_REF], which are based on normalized intensity values; and RIFT descriptors, which are based on gradient orientations. For details about descriptor computation, see [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF].

An intensity-domain spin image is a two-dimensional histogram with bins indexed by two parameters: The first is d, the distance from the center of the patch, and the second is i, the intensity. Thus, the "slice" of the spin image corresponding to a fixed d is simply the histogram of the intensity values of pixels located at a distance d from the center. In our implementation, we use ten bins each for d and i, resulting in 100-dimensional descriptors. To achieve invariance to affine transformations of the intensity, we normalize the range of the intensity function within the support region of the spin image.

The representation of local appearance of a normalized patch is augmented with an additional RIFT descriptor, which is a rotation-invariant generalization of SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The RIFT descriptor is constructed as follows. The circular normalized patch is divided into concentric rings of equal width, and within each ring, a gradient orientation histogram is computed. To maintain rotation invariance, this orientation is measured at each point relative to the direction pointing outward from the center. We use four rings and eight histogram orientations, yielding 32-dimensional descriptors (the original SIFT has 128 dimensions). Note that the RIFT descriptor as described above is not invariant to reflection of the normalized patch, which reverses the order of directions in the orientation histogram. Thus, when finding the distance between two RIFT descriptors, we must take the minimum over both orders.

The final issue is how to combine the two kinds of descriptors in determining the appearance-based dissimilarity or matching score between two patches. We set the matching score to be the minimum of the Euclidean distances between the two spin images or RIFT descriptors (note that both descriptors are normalized to have zero mean and unit norm, thus Euclidean distances between them lie in the same range and are comparable). Empirically, this approach performs better than other ways of combining descriptors, since it provides robustness against instabilities in region extraction and intensity normalization. The descriptors (particularly spin images) can be sensitive to transformations of the intensity values (i.e., noise, JPEG compression, sharpening) and to shifts in the position of the center of the normalized patch, so a large distance between two spin images or two RIFT descriptors is not always a reliable indication of perceptual difference. Thus, in determining the matching score between two patches, it makes sense to trust the descriptor that produces the lower distance.

Finding Candidate Parts

In this section, we describe the procedure for initializing local affine parts, which is based on determining correspondence between sets of regions in the two images. The space of all hypotheses is exponentially large, necessitating the use of constrained search [START_REF] Grimson | The combinatorics of object recognition in cluttered environments using constrained search[END_REF] with strong geometric and appearance-based consistency constraints to prune this space. Correspondence search begins by identifying a set of neighboring (or seed) triples of regions (ellipses) in the first image. The neighborhood of an ellipse is defined by "growing" the axes of that ellipse by a constant factor (typically 2 to 4). Given an ellipse with index i and an ordered set of neighbor indices, we generate a fixed number of seed triples of the form (i, j, k), where ( j, k) are all combinations of the first m (2 to 5) neighbors. For each seed triple (i, j, k) in the first image, we find all triples (i , j , k ) in the second image such that i (resp. j , k ) is a potential appearance-based match of i (resp. j, k), and j and k are neighbors of i . Potential matches are determined using a threshold on the matching score between the respective descriptors. Note that the total number of seed triples of matches is O n m 2 r 3 , where r is the maximum number of potential matches of a single ellipse and n is the total number of ellipses in the first image. This quantity is actually linear in n since m and r have fixed upper bounds in the implementation.

The next step is to judge the geometric consistency of each triple of matches. To do this, we determine the affine transformation mapping the three ellipse centers in the first image onto their putative correspondences in the second image. Once the two sets of ellipses have been aligned in the same coordinate system, their shape can be compared directly and consistency can be measured using thresholds on the difference of major and minor axis sizes, and the angle between major axes. Note that we cannot set an absolute threshold on the first quantity, which is measured in pixels and is therefore non-invariant. Instead, the threshold is defined as a fraction of a quasi-affine local scale, in our case, the average of the major axis lengths of all ellipses in the current hypothesis.

After finding a geometrically consistent triple of matches, the search algorithm attempts to extend it into a larger consistent hypothesis by searching for additional matches lying in the neighborhood of any of the original ellipses. We use a greedy strategy, where at each step, the most geometrically consistent pair of potential matches is selected, and the affine transform between corresponding ellipse centers is re-estimated using linear least squares. With four or more matches, the residual from this estimation is used as the measure of geometric consistency of the entire spatial configuration. The process continues until no match can be added without violating the consistency constraints. Note that the size of the final hypothesis is an indicator of its saliency. We have found that at least 6 to 8 matches are needed to represent a non-spurious correspondence. Therefore, we discard all hypotheses smaller than a certain minimum size. As a final step, we also merge hypotheses that overlap by a significant number of regions. Because it does not assume a global affine correspondence between two images, our matching procedure is applicable to general 3D objects, as demonstrated by the examples of Figure 1. In the case of cars, consistent hypotheses arise from structurally important areas such as wheels and the license plate. Figures 2 and3 show several matching hypotheses for faces and birds, which are non-rigid objects.

Interestingly, the above search procedure can be used to match an image to itself, and is thus applicable to the problem of detecting repeated structures and symmetries within an image [START_REF] Liu | A computational model for periodic pattern perception based on frieze and wallpaper groups[END_REF][START_REF] Turina | Grouping via the matching of repeated patterns[END_REF] (Figure 4). The only change necessary in the implementation is the addition of checks to prevent trivial hypotheses, i.e., hypotheses that match every region to itself. Note that our approach can discover patterns despite substantial clutter in the image, which is not possible with other, more specialized approaches, e.g., [START_REF] Liu | A computational model for periodic pattern perception based on frieze and wallpaper groups[END_REF].

From Hypotheses to Parts

The next step is to convert a matching hypothesis into a unique representation for a candidate semi-local affine part. Informally, we form a part by "averaging" the two sets of regions brought into correspondence by the hypothesis. Given two sets of ellipse centers {x i ↔ x i }, we want to find two point sets { xi } and { x i } that are exactly related by an affine transformation, such that the "Procrustean" distance

∑ i (x i -xi ) 2 +(x i -x i ) 2 is minimized.
The solution for { xi } and { x i } is easily obtained using 2D affine factorization [START_REF] Fitzgibbon | On affine invariant clustering and automatic cast listing in movies[END_REF]. Note that our representation derives its invariance from alignment, so it is not necessary to have an invariant representation of coordinates. Thus, either of the two affinely equivalent coordinate sets { xi } or { x i } can be used to represent the geometric configuration of the part. Next, pairs of corresponding ellipses are registered in the chosen coordinate system, and their attributes (descriptors, axis lengths, orientations) are averaged.

After initializing a candidate part as described above, we validate it by matching it to additional sample images of the object. The purpose of validation is to reject spurious hypotheses, or, less drastically, to remove individual correspondences arising from clutter. The process of detecting a part in a new image is much the same as two-image matching, made simpler and more efficient by the part's relatively small size and (presumed) lack of clutter. Note that the detections of the part in a validation image are allowed to have missing regions to account for occlusion or failure of the region detector. We define the repeatability of an individual region as the proportion of hypotheses in which the region was detected. Regions with repeatability below a certain threshold are rejected. Similarly, a repeatability score is defined for parts as the average number of detected regions per hypothesis. This score provides us a way to rank parts according to their "quality," so that we can take a fixed number of top parts to serve as a "vocabulary" for representing the object class, or simply to discard parts whose repeatability falls below a certain threshold.

Note that in principle, we can use the correspondences between the parts and the validation images to improve the parts by modifying their appearance and shape. At present, we have not implemented this extension, which would involve factorization in the presence of missing data. Moreover, in our experiments we have generally been satisfied with the quality of parts obtained following verification.

Recognition Experiments

In this section, we exercise the proposed part extraction method for the challenging application of identifying butterflies in natural imagery. We use an extremely simple recognition framework, so that the burden for achieving good performance is placed entirely on the expressiveness and invariance of semi-local affine parts. Briefly, the matching and validation procedures described in the previous section are used to identify a fixed-size collection of parts for representing the classes. We define a cumulative repeatability score that combines all part detections for a given class in a test image, which enables us to evaluate performance either using multi-class classification or binary detection.

Figure 5 shows a dataset composed of 619 images of seven classes of butterflies. The pictures, which are collected from the Internet, are extremely diverse in terms of size and quality. Motion blur, lack of focus, resampling and compression artifacts are common. This dataset is appropriate for exercising the descriptive power of local affine parts, since the geometry of a butterfly is locally planar for each wing (though not globally planar). In addition, the species identity of a butterfly is determined by a basically stable geometric wing pattern, though appearance can be significantly affected by variations between individuals, lighting, and imaging conditions. It is crucial to point out that butterfly recognition is beyond the capabilities of many current state-of-the-art recognition systems [START_REF] Agarwal | Learning a sparse representation for object detection[END_REF][START_REF] Fergus | Object class recognition by unsupervised scaleinvariant learning[END_REF][START_REF] Li | A Bayesian approach to unsupervised one-shot learning of object categories[END_REF][START_REF] Weber | Unsupervised learning of models for recognition[END_REF]. For example, the system developed by Fergus et al. [START_REF] Fergus | Object class recognition by unsupervised scaleinvariant learning[END_REF] is, according to its authors, limited to models consisting of up to 6 or 7 features learned from images containing 20 to 30 features. By contrast, a typical butterfly pattern is sufficiently complex to require at least a dozen regions to be adequately represented, while the clutter is measured by hundreds or even thousands of regions. Moreover, the levels of invariance (translation and scale) possessed by existing algorithms are clearly insufficient for recognizing butterflies, which can and do appear at a wide range of scales and orientations, and are rarely fronto-parallel with respect to the camera.

Candidate parts are formed by matching between eight randomly chosen pairs of training images. Ten verification images per class are used to rank candidate parts according to their repeatability score, and top ten parts per class are retained for recognition. The cumulative score for a given class is given by the relative repeatability of all its parts, or the total number of regions detected in all parts divided by the sum of part sizes.

For multi-class classification, each image is assigned to the class having the maximum relative repeatability score. Figure 6 (a) shows classification results obtained using the above approach (the average rate is 90.4%), and Figure 6 (b) shows how performance is improved by using multiple parts. We can get an alternative assessment of performance by considering the binary detection task, where for each image and each class, we ask whether an instance of the from this class is present. This decision can be made by setting a threshold on the relative repeatability. By considering all possible thresholds, we get an ROC curve, a plot of the true positive rate vs. the false positive rate. These curves, given in Figure 7 (c), also show ROC equal error rates (false positives = 1-true positives). The true positive rates range from 87% to 94.8%, showing that detection can indeed be performed successfully.

Discussion

In this paper, we have presented a weakly supervised framework for modeling 3D objects in terms of geometrically invariant semi-local affine parts. The two-image matching procedure that forms the core of our method is also applicable to identifying repeated structures and symmetries within a single image -an interesting application which is rarely treated in the same context as recognition. For our primary goal of 3D object recognition, the proposed approach has the advantages of robustness and flexibility. Namely, it is capable of learning multiple variable-sized parts from images containing a significant amount of noise and clutter. We conclude this presentation with a discussion of several conceptual issues relevant to our work. Probabilistic vs. geometric approaches. Recently, Bayesian approaches have shown considerable promise for weakly supervised learning of part-based models [START_REF] Fergus | Object class recognition by unsupervised scaleinvariant learning[END_REF][START_REF] Li | A Bayesian approach to unsupervised one-shot learning of object categories[END_REF][START_REF] Weber | Unsupervised learning of models for recognition[END_REF]. However, while the generative framework provides a principled way of modeling intraclass variability, it is not ideally suited for designing geometrically invariant representations. In particular, a rigorous probabilistic treatment of affine invariance is quite daunting [START_REF] Leung | Probabilistic affine invariants for recognition[END_REF]. In our own research, we have taken a direct geometric approach to invariance, thus greatly gaining in simplicity and flexibility. For example, our search method can automatically determine the number of regions in a semi-local affine part, something that is not straightforward to achieve in a probabilistic framework. EM vs. unique correspondence. Another practical limitation of Bayesian methods comes from the use of the Expectation Maximization (EM) algorithm to estimate model parameters. EM treats correspondence as missing data to be integrated out, which in principle involves computing expectations over the exponentially large space of all possible correspondences. Despite the use of various approximations, the combinatorics of EM severely limits the size of the model and the amount of clutter that can be tolerated during learning. By contrast, our approach is built on the idea that establishing unique correspondence between model and image features is central for successful recognition. Alignment. The search algorithm described in Section 2.2 is reminiscent of the alignment techniques used in model-based vision [START_REF] Grimson | The combinatorics of object recognition in cluttered environments using constrained search[END_REF][START_REF] Huttenlocher | Object recognition using alignment[END_REF]. While the process of detecting an existing part in a test image may indeed be thought of as affine alignment, our overall modeling approach follows a different strategy. Whereas in classical alignment globally rigid models are built manually and/or from segmented/uncluttered images, our method is capable of handling heavily cluttered input since it does not seek a global transformation between two images, nor does it assume that the entire object is either planar and/or (affinely) rigid. Instead, it exploits the fact that smooth surfaces are planar in the small, and that semi-local affine parts are sufficient to handle large viewpoint variations for approximately coplanar, close-by patches, as well as small non-rigid transformations.

Training set size. Our procedure for initializing semi-local affine parts uses only two images. Recently, it has been observed that very few training images are actually necessary for learning of object models provided the learner is equipped with a good prior on the parameters of the model [START_REF] Li | A Bayesian approach to unsupervised one-shot learning of object categories[END_REF]. In our case, the "prior" is the strong notion of visual similarity, making it possible to learn candidate parts from pairs of input images.

Modeling the background. Most object detection schemes, whether classifier-based (discriminative) or probabilistic (generative), require an explicit model of the background and a "negative" training set. By contrast, our approach avoids these requirements because of its reliance on strong geometric consistency constraints and the implicit assumption that the background is non-repeatable.

Relations between parts.

As a major extension of our method, which in its current form stops short of category-level recognition, we plan to develop a method for reasoning about the spatial relations between parts. Although we currently do learn multiple parts for the butterfly dataset, we do not define any relations between them. In this case, relations are not necessary because multiple butterfly parts are redundant, i.e., they all represent wings. In this case, one part is (in principle) sufficient for successful recognition, and the cumulative scoring scheme based on relative repeatability of all parts is appropriate. However, for more complicated 3D classes, parts may correspond to different structures (e.g., body parts), and certain parts may only be detected for some poses of the object, or only for some instances of the class. Thus, developing inter-part relations will be necessary for recognizing non-rigid and/or articulated objects such as animals and humans.

Figure 1 :

 1 Figure 1: Candidate parts for three 3D objects: (a) a salt can, (b) a shoe, and (c) a car. The two input images to the matching procedure are shown side by side, with the matched ellipses superimposed. For visualization purposes, we also show bounding boxes around the matched ellipses: the axisaligned box in the left image is mapped onto the parallelogram in the right image by the affine transformation that aligns the matched ellipses.

  (a) Alain Delon (b) Grace Kelly (c) Grace Kelly and Cary Grant

Figure 2 :

 2 Figure 2: Candidate parts for face images. (c) Curiously, the face of Grace Kelly in the left image fails to match to her face in the right image, but the matched regions do reveal a structural similarity between her face and Cary Grant's.

Figure 3 :

 3 Figure 3: Candidate parts for birds. Note that the hypotheses are confined to relatively rigid sections of the body (e.g., head, neck, breast, wing).

Figure 4 :

 4 Figure 4: Examples of symmetry and repetition detection in single images. (a) Note that because the geometry of this scene is not planar, multiple local symmetries are detected. (b) Reflective symmetry of the left badger's head. (c) A match between the heads of the two individuals.

Figure 5 :

 5 Figure 5: The butterfly dataset. Three samples of each class are shown in each column.

Figure 6 :

 6 Figure 6: Classification results for the butterflies. (a) The second column shows the total model size for each class (the sum of sizes of individual models), and the size of the smallest and the largest models are listed in parentheses. (b) Classification rate vs. number of parts.the parts for all classes are detected in each training image. Though multiple instances of the same part may be found, we retain only the single instance with highest number of detected regions. Figure7 (b)shows examples of part detections in individual test images. The cumulative score for a given class is given by the relative repeatability of all its parts, or the total number of regions detected in all parts divided by the sum of part sizes. For multi-class classification, each image is assigned to the class having the maximum relative repeatability score. Figure6(a) shows classification results obtained using the above approach (the average rate is 90.4%), and Figure6(b) shows how performance is improved by using multiple parts.We can get an alternative assessment of performance by considering the binary detection task, where for each image and each class, we ask whether an instance of the from this class is present. This decision can be made by setting a threshold on the relative repeatability. By considering all possible thresholds, we get an ROC curve, a plot of the true positive rate vs. the false positive rate. These curves, given in Figure7(c), also show ROC equal error rates (false positives = 1-true positives). The true positive rates range from 87% to 94.8%, showing that detection can indeed be performed successfully.

Acknowledgments. This research was partially supported by the National Science Foundation under grant IIS-0308087, the European project LAVA (IST-2001-34405), the UIUC-CNRS collaboration agreement, and the Beckman Institute for Advanced Science and Technology.


Jianguo Zhang
email: zhang@inrialpes.fr

Marcin Marszałek
email: marszale@inrialpes.fr

Svetlana Lazebnik
email: slazebni@uiuc.edu

Cordelia Schmid
email: schmid@inrialpes.fr

Local Features and Kernels for Classification of Texture and Object Categories: A Comprehensive Study

Recently, methods based on local image features have shown promise for texture and object recognition tasks. This paper presents a large-scale evaluation of an approach that represents images as distributions (signatures or histograms) of features extracted from a sparse set of keypoint locations and learns a Support Vector Machine classifier with kernels based on two effective measures for comparing distributions, the Earth Mover's Distance and the χ 2 distance. We first evaluate the performance of our approach with different keypoint detectors and descriptors, as well as different kernels and classifiers. We then conduct a comparative evaluation with several state-of-the-art recognition methods on 4 texture and 5 object databases. On most of these databases, our implementation exceeds the best reported results and achieves comparable performance on the rest. Finally, we investigate the influence of background correlations on recognition performance.

Introduction

The recognition of texture and object categories is one of the most challenging problems in computer vision, especially in the presence of intra-class variation, clutter, occlusion, and pose changes. Recent achievements in both texture and object recognition have demonstrated that using local features, or descriptors computed at a sparse set of scale-or affine-invariant keypoints, tends to be an effective approach [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF][START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF][START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF]. At the same time, Support Vector Machine (SVM) classifiers [START_REF] Schölkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond[END_REF] have shown their promise for visual classification tasks, and the development of specialized kernels suitable for use with local features has emerged as a fruitful line of research [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF]. To date, most evaluations of methods combining kernels and local features have been small-scale and limited to one or two datasets. This motivates us to build an effective image classification approach combining a bag-of-keypoints representation with a kernelbased learning method and to test the limits of its performance on the most challenging databases available today.

Our study consists of three components: Evaluation of implementation choices. We assess many alternative implementation choices, including keypoint detector type, level of geometric invariance, feature descriptor, and classifier kernel. This evaluation yields several insights of practical importance. For example, a combination of multiple detectors and descriptors usually achieves better results than even the most discriminative individual detector/descriptor channel. Also, for most datasets in our evaluation, local features with the highest possible level of invariance do not yield the best performance. Comparison with existing methods. We conduct a comparative evaluation with several state-of-the-art methods for texture and object classification on 4 texture and 5 object databases. For texture classification, our approach outperforms existing methods on Brodatz [START_REF] Brodatz | Textures: A Photographic Album for Artists and Designers[END_REF], KTH-TIPS [START_REF] Hayman | On the significance of real-world conditions for material classification[END_REF] and UIUCTex [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] datasets and obtains comparable results on the CUReT dataset [START_REF] Dana | Reflectance and texture of real world surfaces[END_REF]. For object category classification, our approach outperforms existing methods on Xerox7 [START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF], Graz [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF], CalTech6 [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF], CalTech101 [START_REF] Fei-Fei | Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories[END_REF] and the more difficult test set of the Pascal challenge [START_REF] Everingham | PASCAL visual object classes challenge[END_REF]. It obtains comparable results on the easier Pascal test set. The power of orderless bag-of-keypoints representations may be not surprising in the case of texture images, which lack clutter and have uniform statistical properties. However, it is not a priori obvious that such representations are sufficient for object category classification, since they ignore spatial relations and do not separate foreground from background features. Influence of background features. In many existing datasets, background features tend to be correlated with the foreground (e.g., cars are often pictured on a road, while faces appear in office environments). Since our bag-ofkeypoints method uses both foreground and background features to classify the image, it is important to investigate whether background features provide any "hints" for recognition. Using a novel methodology, we study the influence of background features on the diverse and challenging Pascal benchmark. Our experiments reveal that while background does contain some discriminative information for the foreground category, using foreground and back-ground features together does not improve the performance of our method. Thus, even in the presence of background correlations, the features on the objects themselves are the key to recognition. Moreover, our experiments also show the danger of using monotonous or highly correlated backgrounds for training, since this leads to poor recognition performance on test sets with more complex backgrounds.

We have deliberately limited our evaluations to the image-level classification task, i.e., classifying an entire test image as containing an instance of one of a fixed number of given object classes. This task must be clearly distinguished from localization, i.e., reporting a location hypothesis for an object. We demonstrate that, given the right implementation choices, simple orderless image representations can be surprisingly effective on a wide variety of imagery. Thus, they can serve as good baselines for measuring the difficulty of newly acquired datasets and for evaluating more sophisticated recognition approaches that incorporate structural information about the object.

The rest of this paper is organized as follows. Relevant previous work on texture and object recognition is discussed in Section 1.1. The components of our approach (keypoint detectors, descriptors, and classifier kernels) are described in Section 2. Section 3.1 describes our experimental setup and the nine databases included in the current study. Section 3.2 evaluates the implementation choices relevant to our approach. Sections 3.3 and 3.4 present comparisons with existing texture and object category classification methods, and Section 4 evaluates the effect of background correlations on recognition performance. Finally, Section 5 concludes the paper with a summary of our findings and future extensions.

Related Work

Texture recognition. Recently, there has been a great deal of interest in recognizing images of textured surfaces subjected to lighting and viewpoint changes [START_REF] Dana | Reflectance and texture of real world surfaces[END_REF][START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF][START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF]. The basic idea of these methods is to represent texture images as distributions or texton histograms over a universal texton dictionary. Several texton-based representations using features derived from filter bank outputs and raw pixel values were developed [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF], and further improvements were achieved by using SVM classifier with a kernel based on χ 2 histogram distance [START_REF] Hayman | On the significance of real-world conditions for material classification[END_REF]. However, a major shortcoming of these methods is that the underlying representation is not geometrically invariant. No adaptation is performed to compensate for changes in scale or surface orientation with respect to the camera. By contrast, Lazebnik et al. [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] have proposed an intrinsically invariant representation based on distributions of appearance descriptors computed at a sparse set of affine-invariant keypoints (as opposed to earlier dense approaches that compute descriptors at every pixel). We take this approach as a starting point and further improve its discriminative power with the help of a kernel-based learning method. Object recognition. The earliest work on appearancebased object recognition has utilized global descriptions such as color or texture histograms. The main drawback of such methods is their sensitivity to clutter and occlusions. For this reason, global methods were gradually supplanted by part-based methods, e.g. [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF], that combine appearance descriptors of local features with a representation of their spatial relations. While part-based models offer an intellectually satisfying way of representing objects, learning and inference problems for spatial relations are complex and computationally intensive, especially in a weakly supervised setting where the location of the object in a training image has not been marked. On the other hand, orderless bag-of-keypoints methods [START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF] have the advantage of simplicity and computational efficiency, though they fail to represent the geometric structure of the object or to distinguish between foreground and background features. For these reasons, bag-of-keypoints methods can be adversely affected by clutter, just as earlier global methods. To overcome this problem, novel SVM kernels that can yield high discriminative power despite noise and clutter have been proposed recently [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF]. While these methods have obtained promising results, they have not been extensively tested on databases with heavily cluttered, uncorrelated backgrounds, so the true extent of their robustness has not been conclusively determined. Our own approach is related to that of Grauman and Darrell [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF], who have developed a kernel that approximates the optimal partial matching between two feature sets. Specifically, we use a kernel based on the Earth Mover's Distance [START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF], i.e. the exact partial matching cost.

Components of the representation

Image representation

We use two complementary local region detector types to extract salient image structures: The Harris-Laplace detector [START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF] responds to corner-like regions, while the Laplacian detector [START_REF] Lindeberg | Feature detection with automatic scale selection[END_REF] extracts blob-like regions. These two detectors are invariant to scale transformations only -they output circular regions at a certain characteristic scale. We obtain rotation invariance by rotating the regions in the direction of the dominant gradient orientation [START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF] and affine invariance through the use of an affine adaptation procedure [START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF]. Affinely adapted detectors output ellipse-shaped regions which are then normalized, i.e., transformed into circles. In summary, our detectors offer different levels of invariance: scale invariance only (S), scale with rotation invariance (SR), and affine invariance (A). We denote the Harris detector with different levels of invariance as HS, HSR and HA and the Laplacian detector as LS, LSR and LA.

The normalized circular patches obtained by the detec-tors serve as domains of support for computing appearancebased descriptors. We use the SIFT descriptor [START_REF] Lowe | Distinctive image features form scale-invariant keypoints[END_REF] which computes a gradient orientation histogram within the support region and the SPIN descriptor [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] which is a rotationinvariant two-dimensional histogram of intensities within an image region. We consider each detector/descriptor pair as a separate "channel." The combination of multiple detector/descriptor channels is denoted by (detector + detector) (descriptor + descriptor), e.g., (HS+LS)(SIFT+SPIN) means the combination of HS and LS detectors each described with SIFT and SPIN descriptors.

Comparing distributions of local features

To compare sets of local features, we represent their distributions in the training and test images. One method for doing this is to cluster the set of descriptors found in each image to form its signature {(p 1 , u 1 ), . . . , (p m , u m )}, where m is the number of clusters, p i is the center of the ith cluster, and u i is the proportional size of the cluster. We extract 40 clusters with k-means for each image. Earth Mover's Distance (EMD) [START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF] has shown to be very suitable for measuring the similarity between image signatures. The EMD between two signatures S 1 = {(p 1 , u 1 ), . . . , (p m , u m )} and

S 2 = {(q 1 , w 1 ), . . . , (q n , w n )} is defined as D(S 1 , S 2 ) = m i=1 n j=1 f ij d(p i , q j ) / m i=1 n j=1 f ij ,
where f ij is a flow value that can be determined by solving a linear programming problem, and d(p i , q j ) is the ground distance between cluster centers p i and q j . We use Euclidean distance as the ground distance.

An alternative to image signatures is to obtain a global texton vocabulary (or visual vocabulary) by clustering descriptors from a training set, and then to represent each image as a histogram of texton labels [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF][START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF]. Given a global texton vocabulary of size m, the ith entry of a histogram is the proportion of all descriptors in the image having label i. To compare two histograms S 1 = (u 1 , . . . , u m ) and S 2 = (w 1 , . . . , w m ), we use the χ 2 distance defined as

D(S 1 , S 2 ) = 1 2 m i=1 (u i -w i ) 2 /(u i + w i ) .

Kernel-based classification

For classification, we use Support Vector Machines (SVM) [START_REF] Schölkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond[END_REF]. For a two-class problem the decision function has the form g(x) We use the two-class setting for binary detection, i.e., classifying images as containing or not a given object class. For multi-class classification, we use the one-against-one technique, which trains a classifier for each possible pair of classes. When classifying an image, we evaluate all binary classifiers, and perform voting [START_REF] Schölkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond[END_REF].

= i α i y i K(x i , x) -b, where K(x i , x)
To incorporate EMD or χ 2 distance into the SVM framework, we use generalized Gaussian kernels K(S i , S j ) = exp -D(S i , S j )/A where D(S i , S j ) is EMD (resp. χ 2 distance) if S i and S j are image signatures (resp. vocabulary histograms). The resulting kernel is the EMD kernel (or χ 2 kernel). The parameter A of the EMD (resp. χ 2 ) kernel is the mean value of the EMD (resp. χ 2 ) distances between all training images. To combine channels, we apply the generalized Gaussian kernel to the summed distance

D = n i D i
, where D i is the distance for channel i.

Empirical Evaluation

Experimental setup and datasets

For our experimental evaluation, we use 4 texture and 5 object category datasets, described below. For texture classification, we randomly select 100 different training/test splits and report the average classification accuracy, together with the standard deviation, over the 100 runs. For object classification, we use the same training and test sets as the publications with which we are comparing.

The UIUCTex dataset [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] (Fig. 1) contains 25 texture wood stone brick fabric 1 fabric 2 classes with 40 images per class. Textures are viewed under significant scale and viewpoint changes. Non-rigid deformations, illumination changes and viewpoint-dependent appearance variations are also present. The KTH-TIPS dataset [START_REF] Hayman | On the significance of real-world conditions for material classification[END_REF] (Fig. 4) contains 10 texture classes with 81 im- ture database [START_REF] Dana | Reflectance and texture of real world surfaces[END_REF] we use the same subset of images as [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF]. This subset contains 61 texture classes with 92 images for each class. These images are captured under different illuminations with seven different viewing directions. The changes of viewpoint, and, to a greater extent, of the illumination direction, significantly affect the texture appearance. The Xerox7 dataset [START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF] (Fig. 5) consists of of seven books buildings cars books buildings cars (as faces) (as trees) (as buildings) classes. It includes images with highly variable pose and background clutter, and the intra-class variability is large. We perform multi-class classification with the same setup as in [START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF]. The CalTech6 database [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF] contains six classes and a background set. We use the same training and test set for two-class classification (object vs. background) as [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF]. The Graz dataset [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF] (Fig. 6) contains persons, bikes and a bikes people recognized missed

Evaluation of parameters

Evaluation of different levels of invariance. First, we show the results of evaluating different levels of invariance (S, SR, A) of our two keypoint detectors on several datasets. The number of training images per class are 20 for UIUC-Tex, 3 for Brodatz, 100 for Graz bikes. For Xerox7, we use tenfold cross-validation. These settings are kept for all experiments reported in this section. In this test, all regions are described with the SIFT descriptor and the EMD kernel is used for classification. Xerox7 datasets, while for UIUCTex, rotation invariance (SR) is important. The reason is that Brodatz, Graz and Xe-rox7 have no rotation or affine changes, while UIUCTex has significant viewpoint changes and arbitrary rotations. Even in this case, affine-invariant features fail to outperform the scale-and rotation-invariant ones. The apparent superiority of scale-invariant detectors for recognition could be due to their greater robustness, as the affine adaptation process can often be unstable in the presence of large affine or perspective distortions.

Evaluation of different channels. Next, we compare the performance of different detector/descriptor channels and their combinations. We use the EMD kernel for classification. 3. Classification accuracy of different kernels.

Texture classification

In this section, we present a comparative evaluation of our approach with four state-of-the-art texture classification methods: Lazebnik [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF], VZ-joint [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF], Hayman [START_REF] Hayman | On the significance of real-world conditions for material classification[END_REF] and global Gabor as in [START_REF] Manjunath | Texture features for browsing and retrieval of image data[END_REF]. Table 5 shows the classification accuracy of the five different methods for 4 texture databases. We use (HS+LS)(SIFT+SPIN) as image description for all databases except for UIUC, for which we use the rotation invariant version. For the UIUCTex database we can observe that both our method and Lazebnik's method work much better than Hayman's method and VZ-joint, while Hayman's method works better than VZ-joint. Overall, the improved performance of our method over Lazebnik's and of Hayman over VZ-joint shows that discriminative learning helps to achieve robustness to intra-class variability. On this dataset, global Gabor features perform the worst, since they are not invariant and averaging the features over all pixels loses discriminative information. Overall, the three noninvariant dense methods in our evaluation have relatively weak performance on this database. For the KTH-TIPS database we can observe that our method works best, Hayman's comes second, and VZ-joint and Lazebnik's method are below them. Global Gabor filters come last, though they still give good results and their performance is significantly higher for this database than for UIUCTex. This may be due to the relative homogeneity of the KTH-TIPS texture classes. For the Brodatz our method performs best, closely followed by Hayman's method. We can see that Hayman's method performs better than VZ-joint, and our method better than Lazebnik's method, i.e. that kernel-based learning In conclusion, our method achieves the highest accuracy on three texture databases and comparable results on the CUReT dataset. Its robustness to viewpoint and scale changes has been clearly demonstrated on the UIUCTex and the KTH-TIPS datasets. Our results show that for most datasets, combining geometric invariance at the representation level with a discriminative classifier at the learning level results in a very effective system. Note that even though impressive results are obtained using VZ-joint (patch descriptors) on the CUReT and Brodatz datasets, this method does not perform as well on the other datasets, thus showing its limited applicability. An important factor affecting the performance of local feature methods is image resolution, since keypoint extraction tends to not work well on low-resolution images. This concurs with the previous results showing the advantage of the denser Laplacian detector over the sparser Harris-Laplace.

Object category classification

In this section we evaluate our approach for object category classification and compare it to the best results reported in the literature. Table 4 shows the results for different datasets. The EMD kernel and SVM are used. For details on the experimental setup see section 3.1.

Results for multi-class classification on Xerox7 show that our method outperforms the Xerox bag-of-keypoints method [START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF] in the same experimental setting. This is due to the fact that we use a combination of detectors and descriptors, a more robust kernel (see table 3) and scale invariance as opposed to affine invariance (see table 1). Fig. 5 shows a few results on Xerox7. Two-class classification (object vs. background) accuracy on the CalTech6 and Graz databases is reported with the ROC equal error rate. Our approach outperforms existing methods on both datasets. Note that results for CalTech6 are high, indicating the relatively low level of difficulty of this dataset. Fig. 6 shows some results for the Graz datasets. Misclassified bikes are either observed from the front, very small, or only partially visible. Misclassified people are either observed from the back, occluded, or very small. We also evaluate our approach for the object category classification task of the Pascal challenge [START_REF] Everingham | PASCAL visual object classes challenge[END_REF]. Table 4 shows ROC equal error rates of our method for detecting each class vs. the other best method reported in the Pascal challenge. For test set 1 the best results, slightly better than ours, were obtained by Jurie and Triggs [START_REF] Jurie | Creating efficient codebooks for visual recognition[END_REF]. This approach uses a dense set of multi-scale patches instead of a sparse set of descriptors computed at interest points. For test set 2 best results, below ours, were obtained by Deselaers et al. [START_REF] Deselaers | Discriminative training for object recognition using image patches[END_REF]. They use a combination of patches around interest points and patches on a fixed grid. Results for multi-class classification on Caltech101 show that our approach outperforms Grauman et al. [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF] for the same setup. The best results on this dataset (48%) are currently reported by Berg et al. [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF]. However, these results are not comparable to ours, since they were obtained in a supervised setting with manually segmented training images. Fig. 2 presents the categories with the best and worst classification rates. We can observe that some of the lowest rates are obtained for categories that are characterized by their shape as opposed to texture, such as anchors.

To conclude, our method achieves the best results on Xe-rox7, CalTech6, Graz, Pascal test set 2 and CalTech101 and is comparable for Pascal test set 1.

Object categories -influence of background

Our method recognizes object categories taking both foreground and background features as input. In most databases included in our evaluation, object categories have fairly characteristic backgrounds, e.g., most car images contain a street or a parking lot. In this section, our goal is to determine whether background correlations provide our method with additional cues for classification. In the following experiments, we use the (HS+LS)(SIFT) channels -SPIN is dropped for computational efficiency -and the EMD kernel. The signature size is set to 40 per image. Our test bed is the Pascal database, which comes with complete ground truth annotations (see Fig. 3). Using the annotations, we extract two sets of features from each image: foreground features (FF) that are within the ground truth object region, and background features (BF) that are outside. Throughout our experiments, we systematically replace the original background features from an image by two specially constructed alternative sets: random and constant natural scene backgrounds (referred to as BF-RAND and BF-CONST, respectively). BF-RAND are obtained by randomly shuffling background features among all of the images in the dataset. For example, the background of a face image may be re- placed by the background of a car image. BF-CONST are background features extracted from images captured by a fixed camera observing a natural scene over an extended period of time, so they include continuous lighting changes and the movement of trees and clouds.

Fig. 8 shows ROC curves obtained by training and testing on only the background features (BF). Judging by the shape of the ROC curves, the background features contain a lot of discriminative information for test set 1, and significantly less for test set 2 (e.g., the performance of background features for test set 2 bicycles is close to chance level). The performance curves of the BF-RAND and BF-CONST feature sets (not shown in the figure) are at chance level as one would expect, since BF-RAND and BF-CONST do not contain any information about the foreground object by construction. Fig. 7 evaluates combinations of foreground features with different types of background features. Due to space limitations only results for the people test set 1 are presented. Results for the other test sets are similar [START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An indepth study[END_REF]. AF denotes all the features extracted from the original image, AF-RAND denotes the combination of FF and BF-RAND and AF-CONST denotes the combination of FF and BF-CONST. Fig. 7 (left) shows ROC curves for a situation where training and testing are performed on the same feature combination. FF always gives the highest results, indicating that object features play the key role for recognition, and recognition with segmented images achieves better performance than without segmentation. Mixing back- Based on our evaluation of the role of background features in bag-of-keypoints classification, we can venture two general observations. First, while the backgrounds in most available datasets have non-negligible correlations with the foreground objects, using both foreground and background features for learning and recognition does not result in better performance for our method. In our experimental setting, the recognition problem is easier in the absence of clutter. Second, when the statistics of the test set are unknown at training time, it is usually beneficial to pick the most difficult training set available.

Discussion

In this paper, we have investigated the performance of an image classification approach combining a bagof-keypoints representation with a kernel-based learning method. Results on challenging datasets have shown that surprisingly high levels of performance can be achieved not only on texture images, which are clutter-free and relatively statistically homogeneous, but also on object images containing substantial clutter and intra-class variation.

One of the contributions of our paper is a comprehensive evaluation of multiple keypoint detector types, levels of geometric invariance, feature descriptors and classifier kernels. This evaluation has revealed several general trends. We show that to achieve the best possible performance, it is necessary to use a combination of several detectors and descriptors together with a classifier that can make effective use of the complementary types of information contained in them. Also, we show that using local features with the highest possible level of invariance usually does not yield the best performance. Thus, a practical recognition system should seek to incorporate multiple types of complementary features, as long as their local invariance properties do not exceed the level absolutely required for a given application.

In testing our method on 4 texture and 5 object databases, we have followed an evaluation regime far more rigorous than that of most other comparable works. In fact, our evaluation of multiple texture recognition methods highlights the danger of the currently widespread practice of developing and testing a recognition method with only one or two databases in mind. For example, methods tuned to achieve high performance on the CUReT database (e.g., the VZ method) have weaker performance on other texture databases, such as UIUCTex, and vice versa, methods tuned to UIUCTex and Brodatz (e.g., the Lazebnik method) perform poorly on CUReT.

Another contribution of our paper is our evaluation of the influence of background features. It shows the pitfalls of training on datasets with uncluttered or highly correlated backgrounds, since this yields disappointing results on test sets with more complex backgrounds.

Future research should focus on designing more effective feature detectors and descriptors, for example for representing shape, as well as designing kernels that incorporate geometrical relations between local features. In the longer term, successful category-level object recognition and localization is likely to require more sophisticated models that capture the 3D shape of real-world object categories as well as their appearance. In the development of such models and in the collection of new datasets, simpler bagof-keypoints methods can serve as effective baselines and calibration tools.

  is the value of a kernel function for the training sample x i and the test sample x. The y i ∈ {-1, +1} and α i are the class label and the learned weight of the training sample x i . b is a learned threshold parameter. The training samples with α i > 0 are usually called support vectors.

Figure 1 .

 1 Figure 1. Image examples of the UIUCTex dataset.

Figure 4 .Figure 2 .

 42 Figure 4. Image examples of the KTH-TIPS database. ages per class. Images are captured at nine scales spanning two octaves, viewed under different illumination directions and different poses. The Brodatz texture album [2] contains 112 different texture classes where each class is represented by one image divided into nine sub-images. Note that this dataset is somewhat limited, as it does not model viewpoint, scale, or illumination changes. For the CUReT tex-

Figure 3 .

 3 Figure 3. Image examples with ground truth object annotation of the bike categories of the Pascal challenge.

Figure 5 .

 5 Figure 5. Correctly recognized (first row) and misclassified (second row) Xerox7 images.

Figure 6 .

 6 Figure 6. Recognized and missed images of the Graz dataset.

Figure 7 .

 7 Figure 7. ROC curves for training and testing with four combinations of the foreground features with different types of background.

Table 1

 1

	HS+LS UIUCTex 92.2 ±1.4 Brodatz 94.4 ±0.7 Graz bikes 91.9 ±2.6 Xerox7 94.7 ±1.2	HSR+LSR 98.0 ±0.5 94.0 ±0.9 91.3 ±2.6 92.2 ±2.3	HA+LA 98.0 ±0.6 91.3 ±1.1 90.5 ±3.0 91.4 ±1.8

shows that pure scale invariance (S) performs best for the Brodatz, Graz bikes and

Databases

Scale Inv. Scale and Rotation Affine Inv.

Table 1 .

 1 Evaluation of different levels of invariance.

Table 2 .

 2 Table2shows results obtained for the UIUCTex dataset. We can see that the Laplacian detector tends to perform better than the Harris detector. The most likely reason for this difference is that the Laplacian detector usually extracts four to five times more regions per image than Harris-Laplace, thus producing a richer representation. Using the two detectors together tends to further raise performance. SIFT performs slightly better than SPIN. Combining SIFT with SPIN boosts the overall performance because the two descriptors capture different kinds of information Detector and descriptor evaluation on UIUCTex. representations, the χ 2 kernel performs better than linear. The performance levels of EMD kernel and the χ 2 kernel are comparable and either of them is a good choice in our framework provided that a suitable vocabulary can be built efficiently. To avoid the computational expense of building global vocabularies for each dataset, we use the EMD kernel in the following experiments. ± 3.0 89.2 ± 2.1 59.4 ± 4.1 92.4 ± 1.7 Table

	Channels HSR LSR HSR+LSR 98.0 ± 0.5 96.2 ± 0.8 SIFT SPIN 97.1 ± 0.6 93.9 ± 1.1 97.7 ± 0.6 93.9 ± 1.0	SIFT+SPIN 97.4 ± 0.6 98.2 ± 0.6 98.3 ± 0.5
	based classifiers (EMD-NN and EMD kernel), we use 40 clusters per im-age as before. For the other SVM kernels, which work on histogram representations, we create a global vocabu-lary by concatenating 10 clusters per class. For UIUCTex, Brodatz, Graz bikes and Xerox7, the vocabulary sizes are 250, 1120, 20 and 70, respectively. Table 3 shows classi-fication results for the LSR+SIFT channel, which are rep-resentative of all other channels. We can see that EMD-NN always performs worse than the EMD kernel, i.e., that a discriminative approach gives a significant improvement. The difference is particularly large for the Xerox7 database, which has wide intra-class variability. Among the vocabu-

(gradients vs. intensity values). These observations are confirmed by results on other datasets

[START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An indepth study[END_REF]

(omitted here for lack of space). Overall, the combination of Harris-Laplace and Laplacian detectors with SIFT and SPIN is the preferable choice in terms of classification accuracy, and this is the setup used in Sections 3.3 and 3.4.

Evaluation of different kernels. The learning ability of a kernel classifier depends on the type of kernel used. Here we compare SVM with three different kernels: linear, χ 2 , and EMD. As a baseline, we also evaluate EMD with nearest neighbor (NN) classification -the same setup as in Lazebnik et al.

[START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF]

. For the signature-

Table 5 .

 5 Comparison of different methods for texture datasets.

	Training set size	UIUCTex KTH-TIPS 20 40	Brodatz 3	CUReT 43
	ours Hayman Lazebnik VZ-joint G. Gabor	98.3 ± 0.5 92.0 ± 1.3 96.4 ± 0.9 78.4 ± 2.0 65.2 ± 2.0	95.5 ± 1.3 94.8 ± 1.2 91.3 ± 1.4 92.4 ± 2.1 90.0 ± 2.0	95.4 ± 0.3 95.3 ± 0.4 95.0 ± 0.8 98.6 ± 0.2 89.8 ± 1.0 72.5 ± 0.7 92.9 ± 0.8 96.0 ± 0.4 87.9 ± 1.0 92.4 ± 0.5

Table 4 .

 4 Comparison with the best reported results on several object datasets.improves the performance over 1-NN classification. For the CUReT database Hayman's method obtains the best results, followed by VZ-joint, our method, global Gabor filters, and Lazebnik's method. On this dataset, local feature methods are at a disadvantage. Since most of the CUReT textures are very homogeneous and high-frequency, lacking salient structures such as blobs and corners, keypoint extraction does not produce very good image representations. A simple patch descriptor seems to be more appropriate.

Acknowledgments

This research was supported by the French ACI project MoViStaR, the UIUC-CNRS-INRIA collaboration agreement and the European projects LAVA and PASCAL. M. Marszałek was supported by the INRIA student exchange program and a grant from the European Community under the Marie-Curie project VISITOR. Svetlana Lazebnik was supported by the National Science Foundation under grants IIS-0308087 and IIS-0535152.