Svetlana Lazebnik
email: slazebni@uiuc.edu

Cordelia Schmid
email: cordelia.schmid@inrialpes.fr

Jean Ponce
email: ponce@cs.uiuc.edu

Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories

This paper presents a method for recognizing scene categories based on approximate global geometric correspondence. This technique works by partitioning the image into increasingly fine sub-regions and computing histograms of local features found inside each sub-region. The resulting "spatial pyramid" is a simple and computationally efficient extension of an orderless bag-of-features image representation, and it

shows significantly improved performance on challenging scene categorization tasks. Specifically, our proposed method exceeds the state of the art on the Caltech-101 database and achieves high accuracy on a large database of fifteen natural scene categories. The spatial pyramid framework also offers insights into the success of several recently proposed image descriptions, including Torralba's "gist" and Lowe's SIFT descriptors.

Introduction

In this paper, we consider the problem of recognizing the semantic category of an image. For example, we may want to classify a photograph as depicting a scene (forest, street, office, etc.) or as containing a certain object of interest. For such whole-image categorization tasks, bag-offeatures methods, which represent an image as an orderless collection of local features, have recently demonstrated impressive levels of performance [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF][START_REF] Wallraven | Recognition with local features: the kernel recipe[END_REF][START_REF] Willamowski | Categorizing nine visual classes using local appearance descriptors[END_REF][START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An in-depth study[END_REF]. However, because these methods disregard all information about the spatial layout of the features, they have severely limited descriptive ability. In particular, they are incapable of capturing shape or of segmenting an object from its background. Unfortunately, overcoming these limitations to build effective structural object descriptions has proven to be quite challenging, especially when the recognition system must be made to work in the presence of heavy clutter, occlusion, or large viewpoint changes. Approaches based on generative part models [START_REF] Fei-Fei | Learning generative visual models from few training examples: an incremental Bayesian approach tested on 101 object categories[END_REF][START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF] and geometric correspondence search [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF][START_REF] Lazebnik | A maximum entropy framework for part-based texture and object recognition[END_REF] achieve robustness at significant computational expense. A more efficient approach is to augment a basic bag-of-features representation with pairwise relations between neighboring local features, but existing implementations of this idea [START_REF] Lazebnik | A maximum entropy framework for part-based texture and object recognition[END_REF][START_REF] Sivic | Discovering objects and their location in images[END_REF] have yielded inconclusive results. One other strategy for increasing robustness to geometric deformations is to increase the level of invariance of local features (e.g., by using affine-invariant detectors), but a recent large-scale evaluation [START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An in-depth study[END_REF] suggests that this strategy usually does not pay off.

Though we remain sympathetic to the goal of developing robust and geometrically invariant structural object representations, we propose in this paper to revisit "global" non-invariant representations based on aggregating statistics of local features over fixed subregions. We introduce a kernel-based recognition method that works by computing rough geometric correspondence on a global scale using an efficient approximation technique adapted from the pyramid matching scheme of Grauman and Darrell [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF]. Our method involves repeatedly subdividing the image and computing histograms of local features at increasingly fine resolutions. As shown by experiments in Section 5, this simple operation suffices to significantly improve performance over a basic bag-of-features representation, and even over methods based on detailed geometric correspondence.

Previous research has shown that statistical properties of the scene considered in a holistic fashion, without any analysis of its constituent objects, yield a rich set of cues to its semantic category [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF]. Our own experiments confirm that global representations can be surprisingly effective not only for identifying the overall scene, but also for categorizing images as containing specific objects, even when these objects are embedded in heavy clutter and vary significantly in pose and appearance. This said, we do not advocate the direct use of a global method for object recognition (except for very restricted sorts of imagery). Instead, we envision a subordinate role for this method. It may be used to capture the "gist" of an image [START_REF] Torralba | Context-based vision system for place and object recognition[END_REF] and to inform the subsequent search for specific objects (e.g., if the image, based on its global description, is likely to be a highway, we have a high probability of finding a car, but not a toaster). In addition, the simplicity and efficiency of our method, in combination with its tendency to yield unexpectedly high recognition rates on challenging data, could make it a good baseline for "calibrating" new datasets and for evaluating more sophisticated recognition approaches.

Previous Work

In computer vision, histograms have a long history as a method for image description (see, e.g., [START_REF] Schiele | Recognition without correspondence using multidimensional receptive field histograms[END_REF][START_REF] Swain | Color indexing[END_REF]). Koenderink and Van Doorn [START_REF] Koenderink | The structure of locally orderless images[END_REF] have generalized histograms to locally orderless images, or histogram-valued scale spaces (i.e., for each Gaussian aperture at a given location and scale, the locally orderless image returns the histogram of image features aggregated over that aperture). Our spatial pyramid approach can be thought of as an alternative formulation of a locally orderless image, where instead of a Gaussian scale space of apertures, we define a fixed hierarchy of rectangular windows. Koenderink and Van Doorn have argued persuasively that locally orderless images play an important role in visual perception. Our retrieval experiments (Fig. 4) confirm that spatial pyramids can capture perceptually salient features and suggest that "locally orderless matching" may be a powerful mechanism for estimating overall perceptual similarity between images.

It is important to contrast our proposed approach with multiresolution histograms [START_REF] Hadjidemetriou | Multiresolution histograms and their use in recognition[END_REF], which involve repeatedly subsampling an image and computing a global histogram of pixel values at each new level. In other words, a multiresolution histogram varies the resolution at which the features (intensity values) are computed, but the histogram resolution (intensity scale) stays fixed. We take the opposite approach of fixing the resolution at which the features are computed, but varying the spatial resolution at which they are aggregated. This results in a higher-dimensional representation that preserves more information (e.g., an image consisting of thin black and white stripes would retain two modes at every level of a spatial pyramid, whereas it would become indistinguishable from a uniformly gray image at all but the finest levels of a multiresolution histogram). Finally, unlike a multiresolution histogram, a spatial pyramid, when equipped with an appropriate kernel, can be used for approximate geometric matching.

The operation of "subdivide and disorder" -i.e., partition the image into subblocks and compute histograms (or histogram statistics, such as means) of local features in these subblocks -has been practiced numerous times in computer vision, both for global image description [START_REF] Gorkani | Texture orientation for sorting photos "at a glance[END_REF][START_REF] Squire | Content-based query of of image databases, inspirations from text retrieval: inverted files, frequency-based weights and relevance feedback[END_REF][START_REF] Szummer | Indoor-outdoor image classification[END_REF][START_REF] Torralba | Context-based vision system for place and object recognition[END_REF] and for local description of interest regions [START_REF] Lowe | Towards a computational model for object recognition in IT cortex[END_REF]. Thus, though the operation itself seems fundamental, previous methods leave open the question of what is the right subdivision scheme (although a regular 4 × 4 grid seems to be the most popular implementation choice), and what is the right balance between "subdividing" and "disordering." The spatial pyramid framework suggests a possible way to address this issue: namely, the best results may be achieved when multiple resolutions are combined in a principled way. It also suggests that the reason for the empirical success of "subdivide and disorder" techniques is the fact that they actually perform approximate geometric matching.

Spatial Pyramid Matching

We first describe the original formulation of pyramid matching [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF], and then introduce our application of this framework to create a spatial pyramid image representation.

Pyramid Match Kernels

Let X and Y be two sets of vectors in a d-dimensional feature space. Grauman and Darrell [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF] propose pyramid matching to find an approximate correspondence between these two sets. Informally, pyramid matching works by placing a sequence of increasingly coarser grids over the feature space and taking a weighted sum of the number of matches that occur at each level of resolution. At any fixed resolution, two points are said to match if they fall into the same cell of the grid; matches found at finer resolutions are weighted more highly than matches found at coarser resolutions. More specifically, let us construct a sequence of grids at resolutions 0, . . . , L, such that the grid at level has 2 cells along each dimension, for a total of D = 2 d cells. Let H X and H Y denote the histograms of X and Y at this resolution, so that H X (i) and H Y (i) are the numbers of points from X and Y that fall into the ith cell of the grid. Then the number of matches at level is given by the histogram intersection function [START_REF] Swain | Color indexing[END_REF]:

I(H X , H Y ) = D i=1 min H X (i), H Y (i) . ( 1
)
In the following, we will abbreviate I(H X , H Y ) to I .

Note that the number of matches found at level also includes all the matches found at the finer level + 1. Therefore, the number of new matches found at level is given by I -I +1 for = 0, . . . , L -1 . The weight associated with level is set to 1 2 L-, which is inversely proportional to cell width at that level. Intuitively, we want to penalize matches found in larger cells because they involve increasingly dissimilar features. Putting all the pieces together, we get the following definition of a pyramid match kernel:

κ L (X, Y ) = I L + L-1 =0 1 2 L-I -I +1 (2) = 1 2 L I 0 + L =1 1 2 L-+1 I . ( 3
)
Both the histogram intersection and the pyramid match kernel are Mercer kernels [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF].

Spatial Matching Scheme

As introduced in [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF], a pyramid match kernel works with an orderless image representation. It allows for precise matching of two collections of features in a highdimensional appearance space, but discards all spatial information. This paper advocates an "orthogonal" approach: perform pyramid matching in the two-dimensional image space, and use traditional clustering techniques in feature space. 1 Specifically, we quantize all feature vectors into M discrete types, and make the simplifying assumption that only features of the same type can be matched to one another. Each channel m gives us two sets of two-dimensional vectors, X m and Y m , representing the coordinates of features of type m found in the respective images. The final kernel is then the sum of the separate channel kernels:

K L (X, Y ) = M m=1 κ L (X m , Y m ) . ( 4
)
This approach has the advantage of maintaining continuity with the popular "visual vocabulary" paradigm -in fact, it reduces to a standard bag of features when L = 0.

Because the pyramid match kernel (3) is simply a weighted sum of histogram intersections, and because c min(a, b) = min(ca, cb) for positive numbers, we can implement K L as a single histogram intersection of "long" vectors formed by concatenating the appropriately weighted histograms of all channels at all resolutions (Fig. 1). For L levels and M channels, the resulting vector has dimensionality

M L =0 4 = M 1 3 (4 L+1 -1)
. Several experiments reported in Section 5 use the settings of M = 400 and L = 3, resulting in 34000-dimensional histogram intersections. However, these operations are efficient because the histogram vectors are extremely sparse (in fact, just as in [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF], the computational complexity of the kernel is linear in the number of features). It must also be noted that we did not observe any significant increase in performance beyond M = 200 and L = 2, where the concatenated histograms are only 4200-dimensional. The final implementation issue is that of normalization. For maximum computational efficiency, we normalize all histograms by the total weight of all features in the image, in effect forcing the total number of features in all images to be the same. Because we use a dense feature representation (see Section 4), and thus do not need to worry about spurious feature detections resulting from clutter, this practice is sufficient to deal with the effects of variable image size.

Feature Extraction

This section briefly describes the two kinds of features used in the experiments of Section 5. First, we have socalled "weak features," which are oriented edge points, i.e., points whose gradient magnitude in a given direction exceeds a minimum threshold. We extract edge points at two scales and eight orientations, for a total of M = 16 channels. We designed these features to obtain a representation similar to the "gist" [START_REF] Torralba | Context-based vision system for place and object recognition[END_REF] or to a global SIFT descriptor [START_REF] Lowe | Towards a computational model for object recognition in IT cortex[END_REF] of the image.

For better discriminative power, we also utilize higherdimensional "strong features," which are SIFT descriptors of 16 × 16 pixel patches computed over a grid with spacing of 8 pixels. Our decision to use a dense regular grid instead of interest points was based on the comparative evaluation of Fei-Fei and Perona [START_REF] Fei-Fei | A Bayesian hierarchical model for learning natural scene categories[END_REF], who have shown that dense features work better for scene classification. Intuitively, a dense image description is necessary to capture uniform regions such as sky, calm water, or road surface (to deal with low-contrast regions, we skip the usual SIFT normalization procedure when the overall gradient magnitude of the patch is too weak). We perform k-means clustering of a random subset of patches from the training set to form a visual vocabulary. Typical vocabulary sizes for our experiments are M = 200 and M = 400.

Experiments

In this section, we report results on three diverse datasets: fifteen scene categories [START_REF] Fei-Fei | A Bayesian hierarchical model for learning natural scene categories[END_REF], Caltech-101 [START_REF] Fei-Fei | Learning generative visual models from few training examples: an incremental Bayesian approach tested on 101 object categories[END_REF], and Graz [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF]. We perform all processing in grayscale, even when color images are available. All experiments are repeated ten times with different randomly selected training and test images, and the average of per-class recognition rates2 is recorded for each run. The final result is reported as the mean and standard deviation of the results from the individual runs. Multi-class classification is done with a support vector machine (SVM) trained using the one-versus-all rule: a classifier is learned to separate each class from the rest, and a test image is assigned the label of the classifier with the highest response.

Scene Category Recognition

Our first dataset (Fig. 2) is composed of fifteen scene categories: thirteen were provided by Fei-Fei and Perona [START_REF] Fei-Fei | A Bayesian hierarchical model for learning natural scene categories[END_REF] (eight of these were originally collected by Oliva and Torralba [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF]), and two (industrial and store) were collected by ourselves. Each category has 200 to 400 images, and average image size is 300 × 250 pixels. The major sources of the pictures in the dataset include the COREL collection, personal photographs, and Google image search. This is one of the most complete scene category dataset used in the literature thus far.

Table 1 shows detailed results of classification experiments using 100 images per class for training and the rest for testing (the same setup as [START_REF] Fei-Fei | A Bayesian hierarchical model for learning natural scene categories[END_REF]). First, let us examine the performance of strong features for L = 0 and M = 200, corresponding to a standard bag of features. Our classification rate is 72.2% (74.7% for the 13 classes inherited from Fei-Fei and Perona), which is much higher than their best results of 65.2%, achieved with an orderless method and a feature set comparable to ours. We conjecture that Fei-Fei and Perona's approach is disadvantaged by its re- liance on latent Dirichlet allocation (LDA) [START_REF] Blei | Latent Dirichlet allocation[END_REF], which is essentially an unsupervised dimensionality reduction technique and as such, is not necessarily conducive to achieving the highest classification accuracy. To verify this, we have experimented with probabilistic latent semantic analysis (pLSA) [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF], which attempts to explain the distribution of features in the image as a mixture of a few "scene topics" or "aspects" and performs very similarly to LDA in practice [START_REF] Sivic | Discovering objects and their location in images[END_REF]. Following the scheme of Quelhas et al. [START_REF] Quelhas | Modeling scenes with local descriptors and latent aspects[END_REF], we run pLSA in an unsupervised setting to learn a 60-aspect model of half the training images. Next, we apply this model to the other half to obtain probabilities of topics given each image (thus reducing the dimensionality of the feature space from 200 to 60). Finally, we train the SVM on these reduced features and use them to classify the test set. In this setup, our average classification rate drops to 63.3% from the original 72.2%. For the 13 classes inherited from Fei-Fei and Perona, it drops to 65.9% from 74.7%, which is now very similar to their results. Thus, we can see that latent factor analysis techniques can adversely affect classification performance, which is also consistent with the results of Quelhas et al. [START_REF] Quelhas | Modeling scenes with local descriptors and latent aspects[END_REF].

Next, let us examine the behavior of spatial pyramid matching. For completeness, Table 1 lists the performance achieved using just the highest level of the pyramid (the "single-level" columns), as well as the performance of the complete matching scheme using multiple levels (the "pyramid" columns). For all three kinds of features, results improve dramatically as we go from L = 0 to a multi-level setup. Though matching at the highest pyramid level seems to account for most of the improvement, using all the levels together confers a statistically significant benefit. For strong features, single-level performance actually drops as we go from L = 2 to L = 3. This means that the highest level of the L = 3 pyramid is too finely subdivided, with individual bins yielding too few matches. Despite the diminished discriminative power of the highest level, the performance of the entire L = 3 pyramid remains essentially identical to that of the L = 2 pyramid. This, then, is the main advantage of the spatial pyramid representation: because it combines multiple resolutions in a principled fashion, it is robust to failures at individual levels.

It is also interesting to compare performance of different feature sets. As expected, weak features do not perform as well as strong features, though in combination with the spatial pyramid, they can also achieve acceptable levels of accuracy (note that because weak features have a much higher density and much smaller spatial extent than strong features, their performance continues to improve as we go from L = 2 to L = 3). Increasing the visual vocabulary size from M = 200 to M = 400 results in a small performance increase at L = 0, but this difference is all but eliminated at higher pyramid levels. Thus, we can conclude that the coarse-grained geometric cues provided by the pyramid have more discriminative power than an enlarged visual vocabulary. Of course, the optimal way to exploit structure both in the image and in the feature space may be to combine them in a unified multiresolution framework; this is subject for future research.

Fig. 3 shows a confusion table between the fifteen scene categories. Not surprisingly, confusion occurs between the indoor classes (kitchen, bedroom, living room), and also between some natural classes, such as coast and open country. Fig. 4 shows examples of image retrieval using the spatial pyramid kernel and strong features with M = 200. These examples give a sense of the kind of visual information captured by our approach. In particular, spatial pyramids seem successful at capturing the organization of major pictorial elements or "blobs," and the directionality of dominant lines and edges. Because the pyramid is based on features computed at the original image resolution, even high-frequency details can be preserved. For example, query image (b) shows white kitchen cabinet doors with dark borders. Three of the retrieved "kitchen" images contain similar cabinets, the "office" image shows a wall plastered with white documents in dark frames, and the "inside city" image shows a white building with darker window frames.

Caltech-101

Our second set of experiments is on the Caltech-101 database [START_REF] Fei-Fei | Learning generative visual models from few training examples: an incremental Bayesian approach tested on 101 object categories[END_REF] (Fig. 5). This database contains from 31 to 800 images per category. Most images are medium resolution, i.e., about 300 × 300 pixels. Caltech-101 is probably the most diverse object database available today, though it is not without shortcomings. Namely, most images feature relatively little clutter, and the objects are centered and occupy most of the image. In addition, a number of categories, such as minaret (see Fig. 5), are affected by "corner" artifacts resulting from artificial image rotation. Though these artifacts are semantically irrelevant, they can provide stable cues resulting in misleadingly high recognition rates. We follow the experimental setup of Grauman and Darrell [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF] and J. Zhang et al. [START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An in-depth study[END_REF], namely, we train on 30 images per class and test on the rest. For efficiency, we limit the number of test images to 50 per class. Note that, because some categories are very small, we may end up with just a single test image per class. Table 2 gives a breakdown of classification rates for different pyramid levels for weak features and strong features with M = 200. The results for M = 400 are not shown, because just as for the scene category database, they do not bring any significant improvement. For L = 0, strong features give 41.2%, which is slightly below the 43% reported by Grauman and Darrell. Our best result is 64.6%, achieved with strong fea-tures at L = 2. This exceeds the highest classification rate previously published,3 that of 53.9% reported by J. Zhang et al. [START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An in-depth study[END_REF]. Berg et al. [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF] report 48% accuracy using 15 training images per class. Our average recognition rate with this setup is 56.4%. The behavior of weak features on this database is also noteworthy: for L = 0, they give a classification rate of 15.5%, which is consistent with a naive graylevel correlation baseline [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF], but in conjunction with a four-level spatial pyramid, their performance rises to 54% -on par with the best results in the literature.

Fig. 5 shows a few of the "easiest" and "hardest" object classes for our method. The successful classes are either dominated by rotation artifacts (like minaret), have very little clutter (like windsor chair), or represent coherent natural "scenes" (like joshua tree and okapi). The least successful classes are either textureless animals (like beaver and cougar), animals that camouflage well in their environment minaret (97.6%) windsor chair (94.6%) joshua tree (87.9%) okapi (87.8%) cougar body (27.6%) beaver (27.5%) crocodile (25.0%) ant (25.0%) (like crocodile), or "thin" objects (like ant). Table 3 shows the top five of our method's confusions, all of which are between closely related classes.

To summarize, our method has outperformed both stateof-the-art orderless methods [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF][START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An in-depth study[END_REF] and methods based on precise geometric correspondence [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF]. Significantly, all these methods rely on sparse features (interest points or sparsely sampled edge points). However, because of the geometric stability and lack of clutter of Caltech-101, dense features combined with global spatial relations seem to capture more discriminative information about the objects.

The Graz Dataset

As seen from Sections 5.1 and 5.2, our proposed approach does very well on global scene classification tasks, or on object recognition tasks in the absence of clutter with most of the objects assuming "canonical" poses. However, it was not designed to cope with heavy clutter and pose changes. It is interesting to see how well our algorithm can do by exploiting the global scene cues that still remain under these conditions. Accordingly, our final set of experiments is on the Graz dataset [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF] (Fig. 6), which is characterized by high intra-class variation. This dataset has two object classes, bikes (373 images) and persons (460 images), and a background class (270 images). The image resolution is 640 × 480, and the range of scales and poses at which exemplars are presented is very diverse, e.g., a "person" image may show a pedestrian in the distance, a side view of a complete body, or just a closeup of a head. For this database, we perform two-class detection (object vs. background) using an experimental setup consistent with that of Opelt et al. [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF]. Namely, we train detectors for persons and bikes on 100 positive and 100 negative images (of which 50 are drawn from the other object class and 50 from the background), and test on a similarly distributed set. We generate ROC curves by thresholding raw SVM output, and report the ROC equal error rate averaged over ten runs.

Table 4 summarizes our results for strong features with M = 200. Note that the standard deviation is quite high because the images in the database vary greatly in their level of difficulty, so the performance for any single run is dependent on the composition of the training set (in particular, for L = 2, the performance for bikes ranges from 81% to 91%). For this database, the improvement from L = 0 to L = 2 is relatively small. This makes intuitive sense: when a class is characterized by high geometric variability, it is difficult to find useful global features. Despite this disadvantage of our method, we still achieve results very close to those of Opelt et al. [START_REF] Opelt | Weak hypotheses and boosting for generic object detection and recognition[END_REF], who use a sparse, locally invariant feature representation. In the future, we plan to combine spatial pyramids with invariant features for improved robustness against geometric changes.

Discussion

This paper has presented a "holistic" approach for image categorization based on a modification of pyramid match kernels [START_REF] Grauman | Pyramid match kernels: Discriminative classification with sets of image features[END_REF]. Our method, which works by repeatedly subdividing an image and computing histograms of image features over the resulting subregions, has shown promising re-bike person background Figure 6. The Graz database.

sults on three large-scale, diverse datasets. Despite the simplicity of our method, and despite the fact that it works not by constructing explicit object models, but by using global cues as indirect evidence about the presence of an object, it consistently achieves an improvement over an orderless image representation. This is not a trivial accomplishment, given that a well-designed bag-of-features method can outperform more sophisticated approaches based on parts and relations [START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An in-depth study[END_REF]. Our results also underscore the surprising and ubiquitous power of global scene statistics: even in highly variable datasets, such as Graz, they can still provide useful discriminative information. It is important to develop methods that take full advantage of this information -either as stand-alone scene categorizers, as "context" modules within larger object recognition systems, or as tools for evaluating biases present in newly collected datasets.

Figure 1 .

 1 Figure 1. Toy example of constructing a three-level pyramid. The image has three feature types, indicated by circles, diamonds, and crosses. At the top, we subdivide the image at three different levels of resolution. Next, for each level of resolution and each channel, we count the features that fall in each spatial bin. Finally, we weight each spatial histogram according to eq. (3).

Figure 2 .

 2 Figure 2. Example images from the scene category database. The starred categories originate from Oliva and Torralba [13].

Figure 3 .

 3 Figure 3. Confusion table for the scene category dataset. Average classification rates for individual classes are listed along the diagonal. The entry in the ith row and jth column is the percentage of images from class i that were misidentified as class j.

Figure 4 .

 4 Figure 4. Retrieval from the scene category database. The query images are on the left, and the eight images giving the highest values of the spatial pyramid kernel (for L = 2, M = 200) are on the right. The actual class of incorrectly retrieved images is listed below them.

Figure 5 .

 5 Figure 5. Caltech-101 results. Top: some classes on which our method (L = 2, M = 200) achieved high performance. Bottom: some classes on which our method performed poorly.

Table 1 .

 1 Classification results for the scene category database (see text). The highest results for each kind of feature are shown in bold.

L Single-level Pyramid Single-level Pyramid Single-level Pyramid 0 (1 × 1) 45.3 ±0.5 72.2 ±0.6 74.8 ±0.3 1 (2 × 2) 53.6 ±0.3 56.2 ±0.6 77.9 ±0.6 79.0 ±0.5 78.8 ±0.4 80.1 ±0.5 2 (4 × 4) 61.7 ±0.6 64.7 ±0.7 79.4 ±0.3 81.1 ±0.3 79.7 ±0.5 81.4 ±0.5 3 (8 × 8) 63.3 ±0.8 66.8 ±0.6 77.2 ±0.4 80.7 ±0.3 77.2 ±0.5 81.1 ±0.6

Table 2 .

 2 Classification results for the Caltech-101 database.

	L	Single-level	Pyramid	Single-level	Pyramid
	0	15.5 ±0.9		41.2 ±1.2
	1	31.4 ±1.2	32.8 ±1.3	55.9 ±0.9	57.0 ±0.8
	2	47.2 ±1.1	49.3 ±1.4	63.6 ±0.9	64.6 ±0.8
	3	52.2 ±0.8	54.0 ±1.1	60.3 ±0.9	64.6 ±0.7
				class 1 mis-class 2 mis-
		class 1 / class 2	classified as classified as
				class 2	class 1
		ketch / schooner	21.6	14.8
		lotus / water lily	15.3	20.0
	crocodile / crocodile head	10.5	10.0
		crayfish / lobster	11.3	9.1
		flamingo / ibis	9.5	10.4

Table 3 .

 3 Top five confusions for our method (L = 2, M = 200) on the Caltech-101 database.

	Class	L = 0	L = 2	Opelt [14] Zhang [25]
	Bikes	82.4 ±2.0 86.3 ±2.5	86.5	92.0
	People	79.5 ±2.3 82.3 ±3.1	80.8	88.0

Table 4 .

 4 Results of our method (M = 200) for the Graz database and comparison with two existing methods.

In principle, it is possible to integrate geometric information directly into the original pyramid matching framework by treating image coordinates as two extra dimensions in the feature space.

The alternative performance measure, the percentage of all test images classified correctly, can be biased if test set sizes for different classes vary significantly. This is especially true of the Caltech-101 dataset, where some of the "easiest" classes are disproportionately large.

See, however, H. Zhang et al.[START_REF] Zhang | SVM-KNN: Discriminative nearest neighbor classification for visual category recognition[END_REF] in these proceedings, for an algorithm that yields a classification rate of 66.2 ± 0.5% for 30 training examples, and 59.1 ± 0.6% for 15 examples.

Acknowledgments. This research was partially supported by the National Science Foundation under grants IIS-0308087 and IIS-0535152, and the UIUC/CNRS/INRIA collaboration agreement.


Fred Rothganger
email: rothgang@uiuc.edu

Svetlana Lazebnik
email: slazebni@uiuc.edu

Cordelia Schmid
email: cordelia.schmid@inrialpes.fr

Jean Ponce
email: jponce@uiuc.edu

3D Object Modeling and Recognition from Photographs and Image Sequences

This chapter proposes a representation of rigid three-dimensional (3D) objects in terms of local affine-invariant descriptors of their images and the spatial relationships between the corresponding surface patches. Geometric constraints associated with different views of the same patches under affine projection are combined with a normalized representation of their appearance to guide the matching process involved in object modeling and recognition tasks. The proposed approach is applied in two domains: (1) Photographs -models of rigid objects are constructed from small sets of images and recognized in highly cluttered shots taken from arbitrary viewpoints. (2) Video -dynamic scenes containing multiple moving objects are segmented into rigid components, and the resulting 3D models are directly matched to each other, giving a novel approach to video indexing and retrieval.

Introduction

Traditional feature-based geometric approaches to three-dimensional (3D) object recognition -such as alignment [START_REF] Huttenlocher | Object recognition using alignment[END_REF][START_REF] Lowe | The viewpoint consistency constraint[END_REF] or geometric hashing [START_REF] Lamdan | Geometric hashing: A general and efficient modelbased recognition scheme[END_REF] -enumerate various subsets of geometric image features before using pose consistency constraints to confirm or discard competing match hypotheses. They largely ignore the rich source of information contained in the image brightness and/or color pattern, and thus typically lack an effective mechanism for selecting promising matches. Appearance-based methods, as originally proposed in the context of face recognition [START_REF] Turk | Eigenfaces for recognition[END_REF] and 3D object recognition [START_REF] Murase | Visual learning and recognition of 3-d objects from appearance[END_REF], prefer a classical pattern recognition framework that exploits the discriminatory power of (relatively) lowdimensional, empirical models of global object appearance in classification tasks. However, they typically de-emphasize the combinatorial aspects of the search involved in any matching task, which limits their ability to handle occlusion and clutter.

Viewpoint and/or illumination invariants provide a natural indexing mechanism for object recognition tasks. Unfortunately, although planar objects and certain simple shapes-such as bilateral symmetries or various types of generalized cylinders-admit invariants, general 3D shapes do not [START_REF] Burns | View variation of point-set and line-segment features[END_REF], which is the main reason why invariants have fallen out of favor after an intense flurry of activity in the early 1990s [START_REF] Mundy | Geometric Invariance in Computer Vision[END_REF][START_REF] Mundy | Applications of Invariance in Computer Vision[END_REF]. In this chapter, we revisit invariants as a local description of truly three-dimensional objects: Indeed, although smooth surfaces are almost never planar in the large, they are always planar in the small -that is, sufficiently small patches can be treated as being comprised of coplanar points. Concretely, we propose to capture the appearance of salient surface patches using local image descriptors that are invariant under affine transformations of the spatial domain [START_REF] Lindeberg | Shape-adapted smoothing in estimation of 3-D depth cues from affine distortions of local 2-D brightness structure[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] and of the brightness signal [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], and to capture their spatial relationships using multi-view geometric constraints related to those studied in the structure from motion literature [START_REF] Tomasi | Shape and motion from image streams: a factorization method[END_REF]. This representation is directly related to a number of recent schemes for combining the local surface appearance at "interest points" [START_REF] Harris | A combined edge and corner detector[END_REF] with geometric constraints in tasks such as wide-baseline stereo matching [START_REF] Tuytelaars | Matching widely separated views based on affine invariant regions[END_REF], image retrieval [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], and object recognition [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. These methods normally either require storing a large number of views for each object, or limiting the range of admissible viewpoints. In contrast, our approach supports the automatic acquisition of explicit 3D object models from multiple unregistered images, and their recognition in photographs and videos taken from arbitrary viewpoints.

Section 2 presents the main elements of our object representation framework. It is applied in Sections 3 and 4 to the automated acquisition of 3D object models from small sets of unregistered images and to the identification and localization of these models in cluttered photographs taken from arbitrary and unknown viewpoints. Section 5 briefly discusses further applications to the video indexing and retrieval domain, including a method for segmenting dynamic scenes observed by a moving camera into rigid components and matching the 3D models recovered from different shots. We conclude in Section 6 with a short discussion of the promise and limitations of the proposed approach.

Approach

Affine Regions and their Description

The construction of local invariant models of object appearance involves two steps, the detection of salient image regions, and their description. Ideally, the regions found in two images of the same object should be the projections of the same surface patches. Therefore, they must be covariant, with regions detected in the first picture mapping onto those found in the second one via the geometric and photometric transformations induced by the corresponding viewpoint and illumination changes. In turn, detection must be followed by a description stage that constructs a region representation invariant under these changes. For small patches of smooth Lambertian surfaces, the transformations are (to first order) affine, and we use the approach recently proposed by Mikolajczyk and Schmid to find the corresponding affine regions: Briefly, the algorithm iterates over steps where [START_REF] Aner | Video summaries through mosaic-based shot and scene clustering[END_REF] an elliptical image region is deformed to maximize the isotropy of the corresponding brightness pattern (shape adaptation [START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF]); (2) its characteristic scale is determined as a local extremum of the normalized Laplacian in scale space (scale selection [START_REF] Lindeberg | Feature detection with automatic scale selection[END_REF]); and (3) the Harris operator [START_REF] Harris | A combined edge and corner detector[END_REF] is used to refine the position of the the ellipse's center (localization [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF]). The scale-invariant interest point detector proposed in [START_REF] Mikolajczyk | Indexing based on scale invariant interest points[END_REF] provides an initial guess for this procedure, and the elliptical region obtained at convergence can be shown to be covariant under affine transformations. The affine region detection process used in this chapter implements both this algorithm and a variant where a difference-of-Gaussians (DoG) operator replaces the Harris interest point detector. Note that this operator tends to find corners and points where significant intensity changes occur, while the DoG detector is (in general) attracted to the centers of roughly uniform regions (blobs): Intuitively, the two operators provide complementary kinds of information (see Figure 1 for examples). The affine regions output by our detection process are ellipses that can be mapped onto a unit circle centered at the origin using a one-parameter family of affine transformations. This ambiguity can be resolved by determining the dominant gradient orientation of the image region, turning the corresponding ellipse into a parallelogram and the unit circle into a square (Figure 2). Thus, the output of the detection process is a set of image regions in the shape of parallelograms, together with affine rectifying transformations that map each parallelogram onto a "unit" square centered at the origin (Figure 3).

A rectified affine region is a normalized representation of the local surface appearance. For distant observers (affine projection), it is invariant under arbitrary viewpoint changes. For Lambertian patches and distant light sources, it can also be made invariant to changes in illumination (ignoring shadows) by subtracting the mean patch intensity from each pixel value and normalizing the Frobenius norm of the corresponding image array to one. The Euclidean distance between feature vectors associated with their pixel values can thus be used to compare rectified patches, irrespective of viewpoint and (affine) illumination changes. Other feature spaces may of course be used as well. As many others, we have found the Lowe's SIFT descriptor [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] -a histogram over both spatial dimensions and gradient orientations-to perform well in our experiments, along with a 10 × 10 color histogram drawn from the UV portion of YUV space when color is available.

Geometric Constraints

Given an affine region, let us denote by R the affine transformation from the image patch to its rectified (normalized) form, and by S = R -1 the affine transformation from the rectified form back to the image patch (Figure 3). The 3 × 3 matrix S has the form

S = h v c 0 0 1 ,
and its columns enjoy the following geometric interpretation: The third column gives the homogeneous coordinates of the center c of the corresponding image parallelogram, while h and v are the vectors joining c to the midpoints of the parallelogram's sides (Figure 3). The matrix S effectively contains the locations of three points in the image, so a match between m ≥ 2 images of the same patch contains exactly the same information as a match between m triples of points.

It is thus clear that all the machinery of structure from motion [START_REF] Tomasi | Shape and motion from image streams: a factorization method[END_REF] and pose estimation [START_REF] Huttenlocher | Object recognition using alignment[END_REF][START_REF] Lowe | The viewpoint consistency constraint[END_REF] from point matches can be exploited in modeling and object recognition tasks. Reasoning in terms of multi-view constraints associated with the matrix S provides a unified and convenient representation for all stages of both tasks. Suppose there are n surface patches observed in m images, and that we are given a complete set of measurements S ij as defined above for image indices i = 1, . . . , m and patch indices j = 1, . . . , n. (Later, we will show how to handle the "missing data" problem that results when not all patches are visible in all views.) A rectified patch can be thought of as a fictitious view of the original surface patch (Figure 3), and the mapping S ij can thus be decomposed into an inverse projection N j [START_REF] Faugeras | The Geometry of Multiple Images[END_REF] that maps the rectified patch onto the corresponding surface patch, followed by a projection M i that maps that patch onto its projection in image number i. In particular, we can write

Ŝ def =   S 11 . . . S 1n . . . . . . . . . S m1 . . . S mn   =   M 1 . . . M m   [ N 1 . . . N n ] .
The inverse projection matrix can be written as

N j = H V C 0 0 1 j ,
and its columns admit a geometric interpretation similar to that of S ij : the first two contain the "horizontal" and "vertical" axes of the surface patch, and the third one is the homogeneous coordinate vector of its center.

To extract the matrices N j (and thus the corresponding patches' geometry) from a set of image measurements, we construct a reduced factorization of Ŝ by picking, as in [START_REF] Tomasi | Shape and motion from image streams: a factorization method[END_REF], the center of mass of the surface patches' centers as the origin of the world coordinate system, and the center of mass of these points' projections as the origin in each image. In this case, the projection equation

S ij = M i N j becomes D ij 0 0 1 = A i 0 0 T 1 B j 0 0 1 , or D ij = A i B j ,
where

A i is a 2 × 3 matrix, D ij = [h v c] ij is a 2 × 3 matrix, and B j = [H V C] j is a 3 × 3 matrix. It follows that the reduced 2m × 3n matrix D = Â B, where D def =   D 11 . . . D 1n . . . . . . . . . D m1 . . . D mn   , Â def =   A 1 . . . A m   , B def = [ B 1 . . . B n ] ,
(1) has at most rank 3. Following [START_REF] Tomasi | Shape and motion from image streams: a factorization method[END_REF] we use singular value decomposition to factorize D and compute estimates of the matrices  and B that minimize the squared Frobenius norm of the matrix D - B. Geometrically, the (normalized)

Frobenius norm d = | D -Â B|/
√ 3mn of the residual can be interpreted as the root-mean-squared reprojection error, that is, the distance (in pixels) between the center and side points of the patches observed in the image and those predicted from the recovered matrices  and B. Given n matches established across m images (a match is an m-tuple of image patches), the residual error d can thus be used as a measure of inconsistency between the matches.

Matching

Matching is a fundamental process in both modeling and recognition. An image can be viewed as simply a collection of 2D patches, and likewise a 3D model is a collection of 3D patches. There are three steps in our general procedure for matching between two such patch sets A and B:

Step 1 -Appearance based selection of potential matches. For each patch in set A, this step selects one or more patches in set B with similar appearance, as measured by the descriptors presented in Section 2.1. Mismatches might occur due to measurement noise or confusion of similar (for example, repetitive) structures.

Step 2 -Robust estimation. Using RANSAC, alignment, or other related techniques, this step selects a geometrically consistent subset of the match hypotheses. Our assumption is that the largest such consistent set will contain mostly true matches. This establishes the geometric relationship between the two sets of patches A and B.

Step 3 -Geometry-based addition of matches. This step seeks a fixed-point in the space (A × B) of matches by iteratively estimating a geometric model based on the current set of matches and then selecting all match hypotheses that are consistent with the model. At the same time it adds new match hypotheses guided by the model. Generally, the geometric model will not change much during this process. Rather, the resulting maximal set of matches benefits recognition, where the number of matches acts as a confidence measure, and modeling, where it produces better coverage of the object.

3D Object Modeling from Images

There are several combinatorial and geometric problems to solve in order to convert a set of images into a 3D model. The overall process is divided into four steps: (1) matching: match regions between pairs of images; (2) chaining: link matches across multiple images; (3) stitching: solve for the affine structure and motion while coping with missing data; (4) Euclidean upgrade: use constraints associated with the intrinsic parameters of the camera to turn the affine reconstruction into a Euclidean one. In the following we describe each of these steps. We will use a teddy bear to illustrate some of the steps of the modeling process. Additional modeling experiments will also be presented.

Matching. The first step is to match the regions found in a pair of images. This is an instance of the wide-baseline stereo matching problem which has been well studied in the literature [START_REF] Baumberg | Reliable feature matching across widely separated views[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] Pritchett | Wide baseline stereo matching[END_REF][START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "how do i organize my holiday snaps?[END_REF][START_REF] Tell | Wide baseline point matching using affine invariants computed from intensity profiles[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affine invariant regions[END_REF]. Any technique that generates a set of matches between affine regions in a pair of images is appropriate, including the general matching procedure (Section 2.3). This algorithm appears in three different contexts in this work, so we have chosen to give the details of its application only in the object recognition case (Section 4). Here we give a very brief sketch of its application to 2D matching. For the appearance-based matching (Step 1) we compare SIFT descriptors. For robust estimation (Step 2) we take advantage of the normalized residual d = | D -Â B|/ √ 3mn to measure the consistency of subsets of the matches. Finally, in Step 3 we use an estimate of the epipolar geometry between the two images to find additional hypothetical matches, which are again filtered using the consistency measure. For details on the 2D matching procedure, see [START_REF] Rothganger | 3d object modeling and recognition using local affine-invariant image descriptors and multi-view spatial constraints[END_REF].

Chaining. The matching process described in the previous section outputs affine regions matched across pairs of views. It is convenient to represent these matches by a single (sparse) patch-view matrix whose columns represent surface patches, and rows represent the images in which they appear (Figure 5).

There are two challenges to overcome in the chaining process. One is to ensure that the image measurements S ij are self-consistent for all projections of a given patch j. To solve this, we choose one member of the corresponding column as reference patch, and refine the parameters of the other patches to maximize their texture correlation with it (Figure 6). The second challenge is to cope with mismatches, which can cause two patches in one image to be associated with the same column in the patch-view matrix. In order to properly construct the matrix, we choose the one patch in the image whose texture is closest to the reference patch mentioned above. Stitching. The patch-view matrix is comparable to the data matrix used in factorization approaches to affine structure from motion [START_REF] Tomasi | Shape and motion from image streams: a factorization method[END_REF]. If all patches appeared in all views, we could indeed factorize the matrix directly to recover the patches' 3D configurations as well as the camera positions. In general, however, the matrix is sparse. To cope with this, we find dense blocks (sub-matrices with complete data) to factorize and then register ("stitch") the resulting sub-models into a global one. The problem of finding maximal dense blocks within the patchview matrix reduces to the NP-complete problem of finding maximal cliques in a graph. In our implementation, we use a simple heuristic strategy which, while not guaranteed to be optimal or complete, generally produces an adequate solution: Briefly, we find a dense block for each patch-that is, for each column in the patch-view matrix-by searching for all other patches that are visible in at least the same views. In practice, this strategy provides both a good coverage of the data by dense blocks and an adequate overlap between blocks.

The factorization technique described in Section 2.2 can of course be applied to each dense block to estimate the corresponding projection matrices and patch configurations in some local affine coordinate system. The next step is to combine the individual reconstructions into a coherent global model, or equivalently register them in a single coordinate system. With a proper set of constraints on the affine registration parameters, this can easily be expressed as an eigenvalue problem. In our experiments, however, we have found this linear approach to be numerically ill behaved (this is related to the inherent affine gauge ambiguity of our problem). Thus, in practice, we pick an arbitrary block as root, and iteratively register all others with this one using linear least squares, before using a non-linear bundle adjustment method to refine the global registration parameters.

Euclidean Upgrade. It is not possible to go from affine to Euclidean structure and motion from two views only [START_REF] Koenderink | Affine structure from motion[END_REF]. When three or more views are available, on the other hand, it is a simple matter to compute the corresponding Euclidean weakperspective projection matrices (assuming zero skew and known aspect ratios) and recover the Euclidean structure [START_REF] Tomasi | Shape and motion from image streams: a factorization method[END_REF][START_REF] Ponce | On computing metric upgrades of projective reconstructions under the rectangular pixel assumption[END_REF]: Briefly, we find the 3 × 3 matrix Q such that A i Q is part of a scaled rotation matrix for i = 1, . . . , m. This provides linear constraints on QQ T , and allows the estimation of this symmetric matrix via linear least-squares. The matrix Q can then be computed via Cholesky decomposition [START_REF] Poelman | A paraperspective factorization method for shape and motion recovery[END_REF][START_REF] Weinshall | Linear and incremental acquisition of invariant shape models from image sequences[END_REF].

Modeling results. Figure 7 shows a complete model of the teddy bear, along with the directions of the affine cameras. Figure 8 shows the models (but not the cameras) for seven other objects. The current implementation of our modeling approach is quite reliable, but rather slow: The teddy bear shown in Figure 7 is our largest model, with 4014 model patches computed from 20 images (24 image pairs). Image matching takes about 75 minutes per pair using the general matching procedure (Section 2.3), for a total of 29.9 hours. (All computing times in this presentation are given for C++ programs executed on a 3Ghz Pentium 4 running Linux.) The remaining steps to assemble the model run in 1.5 hours. The greatest single expense in our modeling procedure is patch refinement, and this can be sped up by loosening convergence criteria and reducing the number of pixels processed, at the cost of a small loss in the number of matches.

3D Object Recognition

We now address the problem of identifying instances of 3D models in a test image. This is essentially a matching process, and we apply again the general matching procedure (Section 2.3). The rest of this section describes the specifics of each step of the procedure.

Step 1 -Appearance based selection of potential matches. When texture patches have high contrast (that is, high variance in the intensity gradient) the SIFT descriptor does a good job of selecting promising matches. When the patches have low contrast SIFT becomes less reliable, since the intensity gradient field forms the basis for both the characteristic orientation and the histogram entries. In some situations, SIFT will even place the correct match in the bottom half of the list of candidates (Figure 9). For better reliability, we pre-filter the matches using a color descriptor: a 10 × 10 histogram of the UV portion of YUV space. We compare the color descriptors using χ 2 distance and eliminate those below a threshold. Unfortunately, color is also unreliable due to variation in the spectral content of light sources and in the spectral response of sensors. Therefore we use a contrast measure to guide the choice between tight and loose thresholds in the color filtering step. This effectively shifts credence between the color and SIFT descriptors on an individual patch basis. Step 2 -Robust Estimation. This step finds the largest geometrically consistent set of matches. First, we apply neighborhood constraints to discard obviously inconsistent matches (Figure 10): For each match we construct the projection matrix (since a Euclidean model is available and a match contains three points) and use it to project the surrounding patches. If they lie close, the match is kept. Second, we refine the matched image regions with non-linear least squares to maximize their correlation with the corresponding model patches. This is the most expensive step, so we apply it after the neighborhood constraint. Various methods for finding matching features consistent with a given set of geometric constraints have been proposed in the past, including interpretation tree (or alignment) techniques [START_REF] Ayache | Hyper: a new approach for the recognition and positioning of two-dimensional objects[END_REF][START_REF] Faugeras | The representation, recognition, and locating of 3-D objects[END_REF][START_REF] Grimson | Localizing overlapping parts by searching the interpretation tree[END_REF][START_REF] Huttenlocher | Object recognition using alignment[END_REF][START_REF] Lowe | The viewpoint consistency constraint[END_REF], geometric hashing [START_REF] Lamdan | Geometric hashing: A general and efficient modelbased recognition scheme[END_REF][START_REF] Lamdan | On the error analysis of 'geometric hashing[END_REF], and robust statistical methods such as RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with application to image analysis and automated cartography[END_REF] and its variants [START_REF] Torr | Mlesac: A new robust estimator with application to estimating image geometry[END_REF]. Both alignment and RANSAC can easily be implemented in the context of the general matching procedure (Section 2.3). We used several alternatives in our experiments, and found that the following "greedy" variant performed best: Let M be the number of matches found by appearance (typically limited to 12,000). For each match, we construct a "seed" model by iteratively adding the next most compatible match, just as in alignment, until the total matches in the seed reach a limit N (typically set to 20). Then we use the model constructed from this seed to collect a consensus set, just as in RANSAC. Thus, the "greedy" variant is a hybrid between alignment and RANSAC.

Step 3 -Geometry-Based Addition of Matches. The matches found by the estimation step provide a projection matrix that places the model into the image. All forward-facing patches in the model could potentially be present in the image. Therefore, we project each such model patch and select the K (typically 5 or 10) closest image patches as new match hypotheses.

Object Detection. Once an object model has been matched to an image, some criterion is needed to decide whether it is present or not. We use the following one:

(number of matches ≥ m OR matched area/total area ≥ a) AND distortion ≤ d, where nominal values for the parameters are m = 10, a = 0.1, and d = 0.15. Here, the measure of distortion is

a T 1 a 2 |a 1 ||a 2 | + 1 - min(|a 1 |, |a 2 |) max(|a 1 |, |a 2 |) ,
where a T i is the ith row of the leftmost 2 × 3 portion A of the projection matrix, and it reflects how close this matrix is to the top part of a scaled rotation matrix. The matched surface area of the model is measured in terms of the patches whose normalized correlation is above the usual thresholds, and it is compared to the total surface area actually visible from the predicted viewpoint.

Recognition results. Our recognition experiments match all eight of our object models against a set of 51 images. Each image contains instances of up to five object models, though the typical image only contains one or two. Using the nominal values for the detection parameters given above, the method gives no false positives and a recognition rate (averaged over the eight object models) of 94%.

Figure 11 shows a comparison study including our method and several other state-of-the-art object recognition systems. Our dataset is publicly available at http://www-cvr.ai.uiuc.edu/ponce grp/data, and several other research groups graciously provided test results on it using their systems. The specific algorithms tested were the ones proposed by Ferrari, Tuytelaars & Van Gool [START_REF] Ferrari | Simultaneous object recognition and segmentation by image exploration[END_REF], Lowe [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], Mahamud & Hebert [START_REF] Mahamud | The optimal distance measure for object detection[END_REF], and Moreels, Maire & Perona [START_REF] Moreels | Recognition by probabilistic hypothesis construction[END_REF]. In addition, we performed a test using our wide-baseline matching procedure between a database of training images and the test set, without using 3D models. For details of the comparative study, see [START_REF] Rothganger | 3d object modeling and recognition using local affine-invariant image descriptors and multi-view spatial constraints[END_REF].

Figure 12 shows sample results of some challenging (yet successful) recognition experiments, with a large degree of occlusion and clutter. Figure 13 shows the images where recognition fails. Note the views where the shoe fails. These are separated by about 60 • from the views used during modeling. The surface of the shoe has a very sparse texture, so it is difficult to reconstruct some of the shape details. These details become more significant when the viewpoint moves from nearly parallel to the surface normal to nearly perpendicular.

Video

Modeling from video (contiguous image sequences) is similar in many respects to modeling from still images. In particular, we can use the same methods for describing the appearance and the geometric structure of affine-covariant patches. Establishing correspondence between multiple views of the same patch is actually easier in video sequences, since successive frames are close to each other in space and time, and it is sufficient to use tracking rather than wide-baseline matching. On the other hand, the problem of modeling from video is made much more difficult by the presence of multiple independently moving objects. To cope with this, we take advantage of the factorization and error measure presented in Section 2.2 to simultaneously segment the moving components and build their 3D models. The resulting piecewise-rigid 3D models can be directly compared using the general matching procedure (Section 2.3), promising a method for video shot matching [START_REF] Aner | Video summaries through mosaic-based shot and scene clustering[END_REF][START_REF] Schaffalitzky | Automated scene matching in movies[END_REF][START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Yeung | Efficient matching and clustering of video shots[END_REF]. The modeling process for video starts by extracting affine regions from the first frame and tracking them through subsequent frames. It continues to add new affine regions in each subsequent frame as old ones move out of view or die off for various reasons. The collection of all the tracked patches again forms a patch-view matrix. This matrix will in general contain more than one rigid component. Each rigid component has a different motion, producing a different set of projection matrices. If we attempt to construct a 3D patch for a track (column) using a set of cameras from a different rigid component, the reprojection error will be high, while constructing a 3D patch using cameras from the same rigid component will produce a low error. This fact leads to a motion segmentation technique based on RANSAC [START_REF] Fitzgibbon | Multibody structure and motion: 3-d reconstruction of independently moving objects[END_REF][START_REF] Torr | Motion Segmentation and Outlier Detection[END_REF]. The basic procedure is to locate a section of the video with a large number of overlapping tracks (that is, a large number of visible patches), select a random pair of them to reconstruct a set of cameras, and then construct a consensus set by measuring the reprojection error associated with each of the remaining tracks and adding those below a threshold. The largest consensus set becomes the basis of a new rigid component. The new model is propagated forward and backward through time, adding all compatible tracks. Finally, we remove the entire set of tracks, and repeat the procedure until all components of reasonable size have been found.

Rigid motion consistency may not be measured directly if two patches are not visible at the same time in the video. It is therefore necessary to extend the range of frames in the video covered by the working model as more consistent patches are found. The stitching method described in Section 3, while very accurate, is too expensive and not suited for building a model incrementally. Instead, we use a method called "bilinear incremental SFM" to add sparse measurements from the patch-view matrix to an existing model. Essentially, the method adds one row or column at a time from the patch-view matrix to a model, reconstructing one camera or patch respectively. It reconstructs patches using known cameras associated with the sparse set of image measurements in the new column, and similarly it reconstructs cameras using known patches associated with the image measurements in a row. At each step it always selects the next row or column that has the most image measurements overlapping the current model. In order to propagate the effects of new data, it periodically re-estimates all the cameras and patches currently in the model, exactly as in the resection-intersection method of bundle adjustment [START_REF] Triggs | Bundle adjustment -a modern synthesis[END_REF].

Experimental results. Figure 14 shows results of segmenting and modeling shots from the movies "Run Lola Run" and "Groundhog Day". These movies contain significant perspective effects, so we have used a more general projection model that is beyond the scope of this chapter, see [START_REF] Rothganger | Segmenting, modeling, and matching video clips containing multiple moving objects[END_REF] for details. The first row of the figure shows a scene from "Run Lola Run" where a train passes overhead. The detected components are the train and the background. The second row shows a corner scene from the same movie. The two rigid components are the car and the background. The third row of Figure 14 shows a scene from "Groundhog Day". The rigid components are the van and the background. Later, another vehicle turns off the highway and is also found as a component. The last row of the figure is a reprojection of the 3D model of the van. Note that the viewpoint of the reprojection is significantly different than any in the original scene.

Figure 15 shows the results of a recognition test over a set of 27 video shots collected from various sources: the movies "Run, Lola, Run" and "Groundhog Day", as well as several videos taken in the laboratory. Each scene appeared in Fig. 14. Segmentation and modeling of shots from "Run Lola Run" and "Groundhog Day".

2 or 3 of the shots. We selected 10 different 3D components in turn to act as queries, and used the general matching procedure (Section 2.3) between each query model and the rest of the set, see [START_REF] Rothganger | Segmenting, modeling, and matching video clips containing multiple moving objects[END_REF] for details. Figure 16 shows some of the correctly matched models. It shows a video frame from the recognized shot and a projection of the 3D model of the query shot. This demonstrates how well the two models are registered in 3D. These results are best viewed in motion, and sample videos appear on our web site: http://www-cvr.ai.uiuc.edu/ponce grp/research/3d.

Discussion

We have proposed in this article to revisit invariants as a local object description that exploits the fact that smooth surfaces are always planar in the small. Combining this idea with the affine regions of Mikolajczyk and Schmid [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] has allowed us to construct a normalized representation of local surface appearance that can be used to select promising matches in 3D object modeling and recognition tasks. We have used multi-view geometric constraints to represent the larger 3D surface structure, retain groups of consistent matches, and reject incorrect ones. Our experiments demonstrate the promise of the proposed approach to 3D object recognition. We have extended our approach to automatically perform simultaneous motion segmentation and 3D modeling in video sequences containing multiple independently moving objects. Multi-view geometric constraints guide the selection of patches that move together rigidly and again represent their 3D surface structure, resulting in a set of rigid 3D components.

We have reduced 2D images, 3D models, image sequences and video scenes to a simple representation: a collection of affine patches. Any such collection may be matched to any other, aided by a representation of the geometric relationship between the two. We have presented three examples of such matching: between a pair of images (wide-baseline matching), between a 3D model and an image (object recognition), and between two 3D models (shot matching). In all cases, we first select match hypotheses based on appearance similarity and then find a subset that are geometrically consistent; and finally expand this set guided by both geometry and appearance.

Let us close by sketching several directions for improvement of the existing method. One such direction is increasing the computational efficiency of our current implementation. Two key changes would be to use a voting or indexing scheme rather than naive all-to-all matching, and to avoid patch refinement by developing more robustness to noise in the image measurements. Next, we plan to pursue various improvements to the feature extraction method. The current scheme depends in large part on corner-like Harris interest points, which often fall across object boundaries, and therefore cannot be matched or tracked reliably. To help overcome this problem, we could use maximally stable extremal regions [START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF], which tend to be detected on relatively "flat" regions of an object's surface. More generally, some 3D objects, such as bicycles and lamp-posts, are not amenable to representation by planar patches at all. In such cases, a hybrid system that models point, edge, and planar features would be more suitable. Finally, many interesting objects are non-rigid, the prime example being human actors. Thus, an important future research direction is extending our approach to deal with non-rigid, articulated objects.

Fig. 1 .

 1 Fig. 1. Affine regions found by Harris-Laplacian (left) and DoG (right) detectors.

Fig. 2 .

 2 Fig. 2. Normalizing patches. The left two columns show a patch from image 1 of Krystian Mikolajczyk's graffiti dataset (available from the INRIA LEAR group's web page: http://lear.inrialpes.fr/software). The right two columns show the matching patch from image 4. The first row shows the ellipse determined by affine adaptation. This normalizes the shape, but leaves a rotation ambiguity, as illustrated by the normalized circles in the center. The second row shows the same patches with orientation determined by the gradient at about twice the characteristic scale.

Fig. 3 .

 3 Fig. 3. Geometric structure. Top left: A rectified patch and the original image region. Bottom left: Interpretation of the rectification matrix R and its inverse S. Right: Interpretation of the decomposition of the mapping Sij into the product of a projection matrix Mi and an inverse projection matrix Nj.

Fig. 4 .

 4 Fig. 4. Some of the matches found in two images of the bear (for readability, only 20 out of hundreds of matches are shown here). Note that the lines drawn in this diagram are not epipolar lines. Instead they indicate pairs of matched affine regions.

Fig. 5 .

 5 Fig. 5. A (subsampled) patch-view matrix for the teddy bear. The full patch-view matrix has 4,212 columns. Each black square indicates the presence of a given patch in a given image.

Fig. 6 .

 6 Fig. 6. Refining patch parameters across multiple views: rectified patches associated with a match in four views before (top) and after (bottom) applying the refinement process. The patch in the rightmost column is used as a reference for the other three patches. The errors shown in the top row are exaggerated for the sake of illustration.

Fig. 7 .

 7 Fig. 7. The bear model, along with the recovered affine viewing directions. These cameras are shown at an arbitrary constant distance from the origin.

Fig. 8 .

 8 Fig. 8. Object gallery. Left column: One of several input pictures for each object. Right column: Renderings of each model, not necessarily in the same pose as the input picture. Top to bottom: An apple, rubble (Spiderman base), a salt can, a shoe, Spidey, a toy truck, and a vase.

Fig. 9 .

 9 Fig.9. Comparing SIFT and color descriptors on low-contrast patches. The center column is the model patch. The left column is the correct match in the image. The right column is the match in the image ranked first by SIFT (but that is in fact an incorrect match). The top row shows the patch, the middle row shows the color histogram, and the bottom row shows the SIFT descriptor. The incorrect match has a Euclidean distance of 0.52 between SIFT descriptors and a χ 2 distance of 1.99 between the corresponding color histograms; and the correct match has a SIFT distance of 0.67 and a color distance of 0.03. The two patches on the left are red and green, while the patch on the right is aqua.

Fig. 10 .

 10 Fig.10. An illustration of the neighborhood constraint. The small parallelogram in the upper center is the one used to estimate the projection matrix. The white parallelograms are projections of other forward-facing patches in the 3D model. The "×" surrounded by a circle is the center of one of the patches being tested, and the other "×" within the circle is its match in the image.

Fig. 11 .

 11 Fig. 11. True positive rate plotted against number of false positives for several different recognition methods.

Fig. 12 .

 12 Fig. 12. Some challenging but successful recognition results. The recognized models are rendered in the poses estimated by our program, and bounding boxes for the reprojections are shown as rectangles.

Fig. 13 .

 13 Fig. 13. Images where recognition fails.

Fig. 15 .

 15 Fig. 15. Recognition rate versus false positives for a shot-matching test.

Fig. 16 .

 16 Fig. 16. Some correctly matched shots. The left image is the original frame of the test shot. The right image shows the query model reprojected into the test video.

Acknowledgments. This research was partially supported by the National Science Foundation under grants IIS-0308087 and IIS-0312438, Toyota Motor Cor-poration, the UIUC-CNRS Research Collaboration Agreement, the European FET-open project VIBES, the UIUC Campus Research Board, and the Beckman Institute.