Svetlana Lazebnik
email: slazebni@uiuc.edu

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

Jean Ponce

A Sparse Texture Representation Using Local Affine Regions

Keywords: Image Processing and Computer Vision, Feature Measurement, Texture, Pattern Recognition

This article introduces a texture representation suitable for recognizing images of textured surfaces under a wide range of transformations, including viewpoint changes and non-rigid deformations. At the feature extraction stage, a sparse set of affine Harris and Laplacian regions is found in the image. Each of these regions can be thought of as a texture element having a characteristic elliptic shape and a distinctive appearance pattern. This pattern is captured in an affine-invariant fashion via a process of shape normalization followed by the computation of two novel descriptors, the spin image and the RIFT descriptor. When affine invariance is not required, the original elliptical shape serves as an additional discriminative feature for texture recognition. The proposed approach is evaluated in retrieval and classification tasks using the entire Brodatz database and a publicly available collection of 1000 photographs of textured surfaces taken from different viewpoints.

Introduction

The automated analysis of image textures has been the topic of extensive research in the past forty years, dating back at least to Julesz in 1962 [START_REF] Julesz | Visual pattern discrimination[END_REF]. Existing techniques for modeling texture include co-occurrence statistics [START_REF] Haralick | Statistical and structural approaches to texture[END_REF][START_REF] Julesz | Visual pattern discrimination[END_REF], filter banks [START_REF] Malik | Preattentive texture discrimination with early vision mechanisms[END_REF][START_REF] Randen | Filtering for texture classification: A comparative study[END_REF], and random fields [START_REF] Mao | Texture classification and segmentation using multiresolution simultaneous autoregressive models[END_REF][START_REF] Zhang | Random field models[END_REF].

Unfortunately, most of these methods make restrictive assumptions about the nature of the input texture (e.g., stationarity), and they are not, in general, invariant with respect to 2D similarity and affine transformations, much less to 3D transformations such as viewpoint changes and non-rigid deformations of the textured surface. Invariance to such transformations is highly desirable for many applications, including wide-baseline stereo matching [START_REF] Baumberg | Reliable feature matching across widely separated views[END_REF][START_REF] Schaffalitzky | Viewpoint invariant texture matching and wide baseline stereo[END_REF][START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighbourhoods[END_REF], indexing and retrieval in image and video databases [START_REF] Mikolajczyk | Indexing based on scale invariant interest points[END_REF][START_REF] Schmid | Constructing models for content-based image retrieval[END_REF][START_REF] Schmid | Local greyvalue invariants for image retrieval[END_REF][START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF], and classification of images of materials [START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF][START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF].

In this article, we set out to develop a texture representation that is invariant to geometric transformations that can be locally approximated by an affine model. Since sufficiently small patches on the surfaces of smooth 3D objects are always approximately planar, local affine invariants are appropriate for modeling not only global 2D affine transformations of the image, but also perspective distortions that arise in imaging a planar textured surface, as well as non-rigid deformations that preserve the locally flat structure of the surface, such as the bending of paper or cloth. Specifically, our proposed texture representation is based on characterizing the appearance of distinguished local affine regions in the image.

Like other approaches based on textons, or primitive texture elements [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF][START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF][START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF][START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF], our method involves representing distributions of 2D image features; unlike these, however, it performs shape selection, ensuring that descriptors are computed over neighborhoods whose shape is adapted to changes in surface orientation and scale caused by viewpoint changes or scene deformations. In addition, our method relies on spatial selection by computing descriptors at a sparse set of image locations output by local affine region detectors. This is a significant departure from the traditional feature extraction framework, which involves processing every pixel location in the image. Apart from being memory-and computationintensive, this dense approach produces redundant texton dictionaries that may include, for instance, many slightly shifted versions of the same basic element [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF]. As Figure 1 illustrates, spatial selection is an effective way to reduce this redundancy.

Our approach consists of the following steps (see also Figure 2):

1. Extract a sparse set of affine regions2 in the shape of ellipses from a texture image.

The two region detectors used for this purpose are described in Section 3.1.

2. Normalize the shape of each elliptical region by transforming it into a circle. This reduces the affine ambiguity to a rotational one. Full affine invariance is achieved by computing rotation-invariant descriptors over the normalized regions. In Section 3.2, we introduce two novel rotation-invariant descriptors: one based on spin images used for matching range data [START_REF] Johnson | Using spin images for efficient object recognition in cluttered 3d scenes[END_REF], and one based on Lowe's SIFT descriptor [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].

3. Perform clustering on the affine-invariant descriptors to obtain a more compact repre-sentation of the distribution of features in each image (Section 3.3). Summarize this distribution in the form of a signature, containing a representative descriptor from each cluster and a weight indicating the relative size of the cluster.

4. Compare signatures of different images using the Earth Mover's Distance (EMD) [START_REF] Rubner | Texture-based image retrieval without segmentation[END_REF][START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF], which is a convenient and effective dissimilarity measure applicable to many types of image information. The output of this stage is an EMD matrix whose entries record the distances between each pair of signatures in the database. The EMD matrix can be used for retrieval and classification tasks, as described in Section 4.1. In Section 4, we will use two datasets to evaluate the capabilities of the proposed texture representation. The first dataset, introduced in Section 4.2, consists of photographs of textured surfaces taken from different viewpoints and featuring large scale changes, perspective distortions, and non-rigid transformations. Even though our method relies on implicit assumptions of local flatness and Lambertian appearance, and is thus theoretically applicable primarily to "albedo textures" due to spatial albedo variations on smooth surfaces, the results in Section 4.2 show that in practice it also tends to perform well on "3D textures" arising from local relief variations on a surface. Our second set of experiments, described in Section 4.3, is carried out on the Brodatz database [START_REF] Brodatz | Textures: A Photographic Album for Artists and Designers[END_REF], a collection of images that features significant inter-class variability, but no geometric transformations between members of the same class. Because affine invariance is not required in this case, we modify the basic feature extraction framework to use neighborhood shape as a discriminative feature to improve performance.

Previous Work

Before presenting the details of our approach (Section 3), let us briefly discuss a number of texture models aimed at achieving invariance under various geometric transformations.

Early research in this domain has concentrated on global 2D image transformations, such as rotation and scaling [START_REF] Cohen | Classification of rotated and scaled textured images using Gaussian Markov field models[END_REF][START_REF] Mao | Texture classification and segmentation using multiresolution simultaneous autoregressive models[END_REF]. However, such models do not accurately capture the effects of 3D transformations (even in-plane rotations) of textured surfaces. More recently, there has been a great deal of interest in recognizing images of textured surfaces subjected to lighting and viewpoint changes [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF][START_REF] Dana | Reflectance and texture of real world surfaces[END_REF][START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF][START_REF] Llado | Classification of textures seen from different distances and under varying illumination direction[END_REF][START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF][START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF][START_REF] Wu | Combining gradient and albedo data for rotation invariant classification of 3d surface texture[END_REF]. A few methods [START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF][START_REF] Llado | Classification of textures seen from different distances and under varying illumination direction[END_REF][START_REF] Wu | Combining gradient and albedo data for rotation invariant classification of 3d surface texture[END_REF] are based on explicit reasoning about the 3D structure of the surface, which may involve registering samples of a material so that the same pixel across different images corresponds to the same physical point on the surface [START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF] or applying photometric stereo to reconstruct the depth map of the 3D texture [START_REF] Llado | Classification of textures seen from different distances and under varying illumination direction[END_REF][START_REF] Wu | Combining gradient and albedo data for rotation invariant classification of 3d surface texture[END_REF]. While such approaches capture the appearance variations of 3D surfaces in a principled manner, they require specially calibrated datasets collected under controlled laboratory conditions. For example, the 3D texton representation of Leung and Malik [START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF] naturally lends itself to the task of classifying a "stack" of registered images of a test material with known imaging parameters, but its applicability is limited in most practical situations.

In this presentation, we are interested in classifying unregistered texture images. This problem has been addressed by Cula and Dana [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF] and Varma and Zisserman [START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF][START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF], who have developed several dense 2D texton-based representations capable of very high accuracy on the challenging Columbia-Utrecht reflectance and texture (CUReT) database [START_REF] Dana | Reflectance and texture of real world surfaces[END_REF]. The descriptors used in these representations are filter bank outputs [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF][START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF] and raw pixel values [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF]. Even though these methods have been successful in the complex task of classifying images of materials despite significant appearance changes, the representations themselves

Components

Previous work [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF][START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF][START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF][START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF] This article

Spatial selection

None: every pixel is considered Laplacian and Harris affine region detectors [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]

Neighborhood shape selection

None: neighborhood size is fixed Affine adaptation process [START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF] Descriptor computation Filter banks [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF][START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF][START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF], pixel values [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF] Novel descriptors: spin images, RIFT Finding textons Clustering, universal texton dictionaries

Clustering, separate texton representation for each image Representing/comparing texton distributions Histograms/χ 2 distance Signatures/Earth Mover's Distance [START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF][START_REF] Rubner | Texture-based image retrieval without segmentation[END_REF] Table 1: The components of our approach, contrasted with other 2D texton-based methods.

are not invariant to the changes in question. In particular, the support regions for computing descriptors are the same in all images; no adaptation is performed to compensate for changes in surface orientation with respect to the camera.

Because they lack representation-level invariance, the above methods require the use of multiple models or prototypes to represent a single texture. As long as the training set adequately samples all viewpoints and lighting directions that can be encountered at test time, the texture can be successfully recognized. On the other hand, when the test set contains images not represented in the training set (e.g., images at significantly different scales), performance drops dramatically [START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF]. In our work, we shift away from this dependence on representative training sets by developing a texture representation with built-in geometric invariance. Note, however, that our present method does not explicitly account for changes in lighting direction and associated 3D effects such as self-shadowing; therefore, to achieve robust recognition in the presence of such effects, we must still rely on multiple prototypes in the training set.

Table 1 summarizes the main components of our approach and contrasts it with other 2D texton-based methods. A preliminary version of this article has appeared in [START_REF] Lazebnik | A sparse texture representation using affineinvariant regions[END_REF].

3 Components of the Representation

Affine Regions

Conceptually, our approach may be traced back to early articles on the extraction of local features in natural images, where emphasis is placed on locating perceptually salient primitives such as blobs [START_REF] Crowley | A representation of shape based on peaks and ridges in the difference of low-pass transform[END_REF][START_REF] Voorhees | Detecting textons and texture boundaries in natural images[END_REF]. Blostein and Ahuja [START_REF] Blostein | A multiscale region detector[END_REF] were the first to introduce a multiscale blob detector based on maxima of the Laplacian. Lindeberg [START_REF] Lindeberg | Feature detection with automatic scale selection[END_REF] has extended this detector in the framework of automatic scale selection, where a "blob" is defined by a scale-space location where a normalized Laplacian measure attains a local maximum. Informally, the spatial coordinates of the maximum become the coordinates of the center of the blob, and the scale at which the maximum is achieved becomes its characteristic scale. Gårding and Lindeberg [START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF] have also shown how to design an affine blob detector using an affine adaptation process based on the second moment matrix. This process forms an important part of the affine-invariant region detection frameworks of Baumberg [START_REF] Baumberg | Reliable feature matching across widely separated views[END_REF] and Mikolajczyk and Schmid [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF]. Both of these methods rely on a multiscale version of the Harris operator [START_REF] Harris | A combined corner and edge detector[END_REF] to localize interest points in space. Alternative region extraction schemes include the "entropy detector" of Kadir and Brady [START_REF] Kadir | Scale, saliency and image description[END_REF], the difference-of-Gaussians (or DoG) detector of Lowe [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], the "maximally stable extremal regions" of Matas et al. [START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF], and the cornerand intensity-based operators of Tuytelaars and Van Gool [START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighbourhoods[END_REF]. Of the above, [START_REF] Kadir | Scale, saliency and image description[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] are scale-invariant, while [START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighbourhoods[END_REF] are fully affine-invariant. This proliferation of region detectors, motivated primarily by applications to wide-baseline stereo matching and image retrieval, attests to the increased importance accorded to the spatial and shape selection principles in the computer vision community.

In this work, we use two types of detectors: the Harris-affine detector of Mikolajczyk and Schmid [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] and the Laplacian blob detector of Gårding and Lindeberg [START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF]. 3 Figure 3 shows the output of the detectors on two sample images. Note that the Harris detector tends to find corners and points at which significant intensity changes occur, while the Laplacian detector is (in general) attracted to points that can be thought of as centers of roughly elliptical regions of uniform intensity. Intuitively, the two detectors provide complementary kinds of information about the image: The former responds to regions of "high information content" [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF], while the latter produces a perceptually plausible decomposition of the image into a set of blob-like primitives.

The technical details of automatic scale selection and affine adaptation, described in [START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF][START_REF] Lindeberg | Feature detection with automatic scale selection[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF], are beyond the scope of this article. For our purposes, it is sufficient to note that the affinely adapted regions localized by the Harris and Laplacian detectors are represented as ellipses. We can normalize these regions by mapping the corresponding ellipses onto a unit circle. Because the circle is invariant under rotations and reflections, it can be easily shown that the normalization process has an inherent orthogonal ambiguity. In some previous work, this ambiguity has been resolved by estimating a dominant gradient direction of the patch and aligning this direction with the positive x-axis [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF]. However, in our experience the dominant orientation estimates have tended to be unreliable, especially for Laplacian regions, which lack strong edges at the center. To avoid the potential instability and the computational expense of finding the dominant gradient, we have chosen instead to represent each normalized patch by a rotationally invariant descriptor. A similar strategy has been followed by [START_REF] Baumberg | Reliable feature matching across widely separated views[END_REF][START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?[END_REF].

Note. To achieve invariance to local affine transformations, as in the experiments of Section 4.2, we discard the information contained in the affine shape of the patches. However, as a glance at Figure 3 suggests, this shape can be a distinctive feature when affine invariance is not required. This point will be revisited in Section 4.3.

Rotation-Invariant Descriptors

In this article, we introduce two novel rotation-invariant descriptors: intensity-domain spin images, inspired by the method for matching range data developed by Johnson and Hebert [START_REF] Johnson | Using spin images for efficient object recognition in cluttered 3d scenes[END_REF];

and RIFT descriptors, based on the Scale-Invariant Feature Transform (SIFT) developed by Lowe [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. We will conclude this section by discussing the advantages of the proposed descriptors over the more traditional features like differential invariants [START_REF] Koenderink | Representation of local geometry in the visual system[END_REF][START_REF] Schmid | Local greyvalue invariants for image retrieval[END_REF] and filter banks [START_REF] Baumberg | Reliable feature matching across widely separated views[END_REF][START_REF] Cula | Compact representation of bidirectional texture functions[END_REF][START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?[END_REF][START_REF] Schmid | Constructing models for content-based image retrieval[END_REF][START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF]. Since the d and i parameters are invariant under orthogonal transformations of the image neighborhood, spin images offer an appropriate degree of invariance for representing affinenormalized patches. In the experiments reported in Section 4, we used 10 bins for distance and 10 for intensity value, resulting in 100-dimensional descriptors.

Intensity

We implement the spin image as a "soft histogram" where each pixel within the support region contributes to more than one bin. Specifically, the contribution of a pixel located in

x to the bin indexed by (d, i) is given by exp -

(|x -x 0 | -d) 2 2α 2 - |I(x) -i| 2 2β 2 ,
where x 0 is the location of the center pixel, and α and β are the parameters representing the "soft width" of the two-dimensional histogram bin. Note that the soft histogram can be seen To achieve invariance to affine transformations of the image intensity function (that is, transformations of the form I → aI + b), it is sufficient to normalize the range of the intensity function within the support region of the spin image [START_REF] Schaffalitzky | Viewpoint invariant texture matching and wide baseline stereo[END_REF]. To alleviate the potential sensitivity of the normalization to noise and resampling artifacts (these are particularly severe for patches that are only a few pixels wide), we slightly blur the normalized patches with a Gaussian kernel before computing the spin image.

RIFT descriptors. To obtain a complementary representation of local appearance of normalized patches, we have developed an additional rotation-invariant descriptor that generalizes Lowe's SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The original SIFT has been noted for its superior performance in retrieval tasks [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF]; however, we cannot use it directly in our work because it depends on finding the dominant orientation of the normalized patch. Our descriptor, dubbed Rotation-Invariant Feature Transform, or RIFT, is constructed as follows. The circular normalized patch is divided into concentric rings of equal width, and a gradient orientation histogram is computed within each ring (Figure 5). 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. 4 Note that the RIFT descriptor as described above is not invariant to flipping of the normalized patch, which reverses the order of directions in the orientation histogram. However, we are not concerned with this circumstance in our current work, since realistic imaging conditions do not involve reversing the orientation of a textured surface. Discussion. Both spin images and RIFT descriptors follow the same strategy as the original SIFT and other recently developed features like shape contexts [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]: They subdivide the region of support and compute a histogram of appearance attributes (most frequently, pixel values or gradient orientations) inside each subregion. Histogramming provides stability against deformations of the image pattern, while subdividing the support region offsets the potential loss of spatial information. In this way, a compromise is achieved between the conflicting requirements of greater geometric invariance on the one hand and greater discriminative power on the other. Intuitively, it seems plausible that descriptors based on this compromise would be simultaneously richer and more robust than traditional descriptors that compute functions of the entire region of support, namely, filter banks and differential invariants. Recent experimental data tends to support this intuition: SIFT descriptors have achieved better repeatability rates than filter banks and differential invariants in the comparative evaluations of Mikolajczyk and Schmid [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF], while shape contexts have performed remarkably well for the application of handwritten digit recognition [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]. In addition, at an earlier stage of this research [START_REF] Lazebnik | A sparse texture representation using affineinvariant regions[END_REF], spin images have achieved better results than rotation-invariant "Gabor-like" linear filters [START_REF] Schmid | Constructing models for content-based image retrieval[END_REF] (note that this filter bank is similar in terms of performance and dimensionality to several others in popular use [START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF], and superior to differential invariants [START_REF] Schmid | Constructing models for content-based image retrieval[END_REF]).

In this article, we perform a comparative evaluation of spin images and RIFT. As will be seen from Section 4, spin images tend to perform better (possibly due to their higher dimensionality). However, combining the two descriptors in a unified recognition framework generally produces better results than using either one in isolation. This may be a reflection of the fact that spin images and RIFT rely on complementary kinds of image information -the former uses normalized graylevel values, while the latter uses the gradient.

Signatures and the Earth Mover's Distance

One commonly thinks of a texture image as being "generated" by a few basic primitives, or textons [START_REF] Julesz | Textons, the elements of texture perception and their interactions[END_REF], repeated many times and arranged in some regular or stochastic spatial pattern. In the field of texture analysis, clustering is the standard technique for discovering a small set of primitives based on a large initial collection of texture element instances. Accordingly, we perform clustering on each texture image separately to form its

signature {(m 1 , u 1 ), (m 2 , u 2 ), . . . , (m k , u k )},
where k is the number of clusters, m i is the center of the ith cluster, and u i is the relative weight of the cluster (in our case, the size of the cluster divided by the total number of descriptors extracted from the image).

Signatures have been introduced by Rubner et al. [START_REF] Rubner | Texture-based image retrieval without segmentation[END_REF][START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF] as representations suitable for matching using the Earth Mover's Distance (EMD). The EMD between two signatures

S 1 = {(m 1 , u 1 ), (m 2 , u 2 ), . . . , (m k , u k )} and S 2 = {(n 1 , v 1 ), (n 2 , v 2 ), . . . , (n l , v l )} has the form d(S 1 , S 2 ) = i j f ij d(m i , n j ) i j f ij ,
where the scalars f ij are flow values that are determined by solving a linear programming problem, and the scalars d(m i , n j ) are the ground distances between different cluster centers.

The theoretical justification of this formula and the specifics of the optimization setup are beyond the scope of this paper; we refer the interested reader to [START_REF] Levina | The Earth Mover's distance is the Mallows distance: Some insights from statistics[END_REF][START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF] for more details. In our case, m i and n j may be spin images and RIFT descriptors, and the ground distance is simply the Euclidean distance. Since our descriptors are normalized to have unit norm, the ground distances lie in the range [0, 2]. We rescale this range to [0, 1], thus ensuring that all EMD's are between 0 and 1 as well.

For our application, the signature/EMD framework offers several advantages over the alternative histogram/χ 2 distance framework [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF][START_REF] Leung | Recognizing surfaces using three-dimensional textons[END_REF][START_REF] Varma | Classifying images of materials: Achieving viewpoint and illumination independence[END_REF][START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF]. A signature is more robust and descriptive than a histogram, and it avoids the quantization and binning problems associated with histograms, especially in high dimensions [START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF] (recall that our spin images and RIFT descriptors are 100-and 32-dimensional, respectively). The EMD has been shown to be (relatively) insensitive to the number of clusters, i.e., when one of the clusters is split during signature computation, replacing a single center with two, the resulting EMD matrix is not much affected [START_REF] Rubner | Texture-based image retrieval without segmentation[END_REF]. This is a very important property, since automatic selection of the number of clusters remains an unsolved problem. In addition, in several evaluations of colorand texture-based image retrieval [START_REF] Puzicha | Empirical evaluation of dissimilarity measures for color and texture[END_REF][START_REF] Rubner | The Earth Mover's distance as a metric for image retrieval[END_REF], EMD has performed better than other methods for comparing distributions, including χ 2 distance. Finally, the EMD/signature framework has the advantage of efficiency and modularity: It frees us from the necessity of clustering descriptors from all images together and computing a universal texton dictionary, which may not represent all texture classes equally well [START_REF] Cula | Compact representation of bidirectional texture functions[END_REF].

4 Experimental Evaluation

Evaluation Strategy

Channels. Tuytelaars and Van Gool [START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighbourhoods[END_REF] have articulated the goal of building an opportunistic neighborhood extraction system that would combine the output of several region detectors tuned to different kinds of image structure. In this spirit, the texture representation proposed in this article is designed to support multiple region detectors and descriptors.

Each detector/descriptor pair is treated as an independent channel that generates its own signature representation for each image in the database, and its own EMD matrix of pairwise inter-image distances. To combine the outputs of several channels, we simply add the corresponding entries in the EMD matrices. This approach was empirically determined to be superior to forming linear combinations with varying weights, or taking the minimum or maximum of the distances.

Since our experimental setup involves the evaluation of two region detectors and two descriptors, we end up with four channels: Harris regions and spin images (HS), Harris regions and RIFT descriptors (HR), Laplacian regions and spin images (LS), and finally, Laplacian regions and RIFT descriptors (LR). In addition, we will introduce in Section 4.3 the Harris and Laplacian ellipse channels, denoted HE and LE, respectively. To simplify the notation for combined channels, we will use (in a purely formal, "syntactic" manner) the distributive law: For example, we will write (H+L)R instead of HR+LR for the combination of the Harris/RIFT and Laplacian/RIFT channels, and (H+L)(S+R) for the combination of all four detector/descriptor channels.

Retrieval. We use the standard procedure followed by several Brodatz database evaluations [START_REF] Liu | Periodicity, directionality, and randomness: Wold features for image modeling and retrieval[END_REF][START_REF] Picard | Real-time recognition with the entire Brodatz texture database[END_REF][START_REF] Xu | Performance analysis in content-based retrieval with textures[END_REF]. Given a query image, we select other images from our database in increasing order of EMD, i.e., from the most similar to the least similar. Each image in the database is used as a query image once, and the performance is summarized as a plot of average recall vs. the number of retrievals. Average recall is defined as the number of images retrieved from the same class as the query image over the total number of images in that class (minus one to account for the query itself), averaged over all the queries. For example, perfect performance for a given class would correspond to average recall of 100% after n -1 retrievals, where n is the number of images in that class.

Classification. In effect, the evaluation framework described above measures how well each texture class can be modeled by individual samples. It is not surprising that retrieval can fail in the presence of sources of variability that are not fully accounted for by the invariance properties of the representation (recall that our representation provides invariance to local geometric deformations and affine illumination changes, but not to complex viewpoint-and lighting-dependent appearance changes). To obtain a more balanced assessment of performance, a texture representation should be evaluated using classification as well as retrieval.

In the classification framework, a model for a class is created not from a single (possibly atypical) image, but from a set of multiple training images, thereby compensating for the effects of intra-class variability.

In our implementation, we use nearest-neighbor classification with EMD. The training set is selected as a fixed-size random subset of the class, and all remaining images comprise the test set. To eliminate the dependence of the results on the particular training images used, we report the average of the classification rates obtained for different randomly selected training sets. More specifically, a single sequence of 200 random subsets is generated and used to evaluate all the channel combinations seen in Tables 2 and4. This ensures that all the rates are directly comparable, i.e., small differences in performance cannot be attributed to random "jitter".

Dataset 1: Textured Surfaces

To test the invariance properties of our proposed representation, we have collected a texture database consisting of 1000 uncalibrated, unregistered images: 40 samples each of 25 different textures. The database is publicly available at http://www-cvr.ai.uiuc.edu/ponce grp.

Figure 6 shows four sample images from each class (the resolution of the samples is 640 × 480 pixels). The database includes surfaces whose texture is due mainly to albedo variations (e.g., wood and marble), 3D shape (e.g., gravel and fur), as well as a mixture of both (e.g., carpet and brick). Significant viewpoint changes and scale differences are present within each class, and illumination conditions are uncontrolled. During data acquisition, we have taken care to exercise additional sources of variability wherever possible. These include non-planarity of the textured surface (bark), significant non-rigid deformations between different samples of the same class (fur, fabric, and water), inhomogeneities of the texture pattern (bark, wood, and marble), and viewpoint-dependent appearance variations (glass).

Each image in the database is processed with the Harris and Laplacian detectors. The median number of Harris (resp. Laplacian) regions extracted per image is 926 (resp. 4591).

The median number of combined regions is 5553, or about 1.8% of the total number of pixel locations in the image. Thus, we can see that the spatial selection performed by the detectors results in a drastic compression of the amount of data that needs to be handled by the subsequent processing stages, especially clustering, which is a notoriously memoryintensive operation. In our implementation, clustering was performed using the k-means 2 shows a comparison of 10-sample classification rates for different channel combinations. The same trends that were seen in Figure 7 are echoed here: Spin images perform better than RIFT, Laplacian regions perform better than Harris, and the combination (H+L)(S+R) has the highest performance.

We may wonder whether the superior performance of Laplacian points is due to the denser representation they afford (recall that the Laplacian detector finds almost five times as many regions as the Harris). and "full" Laplacian representations may be compared by looking at columns 3 and 4 of Table 3. Interestingly, while the rates may vary significantly for individual textures, the averages (bottom row) are almost the same: 91.93% and 91.96% for "truncated" and "full", respectively. Thus, recognition performance cannot be regarded as a simple function of the density of the representation.

Finally, Table 3 allows us to analyze the "difficulty" of individual textures for our system. To this end, the textures are arranged in order of increasing (H+L)(S+R) classification rate (last column). Roughly speaking, classification rate is positively correlated with the homogeneity of the texture: Some of the lowest rates belong to inhomogeneous coarse-scale textures like bark (T02, T03) and marble (T09), while some of the highest belong to homogeneous fine-scale textures like glass (T17), water (T07), and fabric (T20, T24). However, this relationship is not universal. For example, granite (T08), which is fine-grained and quite uniform, has a relatively low rate of 86.78%, while the large-scale, inhomogeneous wall (T13) has a relatively high rate of 95.92%. It is also interesting (and somewhat unexpected) that the performance of different classes does not depend on their nature as 3D or albedo textures. Overall, the intrinsic characteristics of the various textures do not seem to provide a clear pattern for predicting performance. This is not surprising if one keeps in mind that classification performance is not related directly to intra-class variability, but to the extent of separation between the classes in feature space. improve by over 11% to 75.89% and 77.21%, respectively, whereas the performance of our method changes by only 3.42% (from 92.61% to 96.03%).

The outcome of the comparison validates our intuition that intrinsic representation-level invariance is necessary to achieve robustness to large viewpoint and scale changes, especially in situations when the lack of invariance cannot be fully compensated by storing multiple prototypes of each texture. This is indeed the case for our dataset, which has relatively few sample images per class but high intra-class variability, including non-homogeneous textures and unconstrained non-rigid deformations. By contrast, the CUReT database lacks these sources of variability. In particular, CUReT images have no scale variation (all materials are held at the same distance from the camera, only the orientation is changed), limited in-plane rotation, and the same physical surface patch is represented in all samples. In addition, the appearance of each patch in that database is systematically sampled under different combinations of viewing angles and lighting directions, making it straightforward to select a fixed representative subset of samples for training, as is done in most CUReT evaluations. Our evaluation scheme is a lot more punishing in comparison, as it averages classification rates over many different randomly chosen training sets.

Dataset 2: Brodatz Database

The Brodatz database [START_REF] Brodatz | Textures: A Photographic Album for Artists and Designers[END_REF] is perhaps the best known benchmark for texture recognition algorithms. In recent years, it has been criticized because of the lack of intra-class variation that it exhibits. However, we feel that it is premature to dismiss the Brodatz database as a challenging platform for performance analysis. For one, relatively few publications actually report results on the entire database (the only studies known to us are [10, 25, database [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF], the best (to our knowledge) retrieval performance on the Brodatz database is around 84% [START_REF] Xu | Performance analysis in content-based retrieval with textures[END_REF]. The reason for this is the impressive diversity of Brodatz textures, some of which are quite perceptually similar, while others are so inhomogeneous that a human observer would arguably be unable to group their samples "correctly". The variety of the scales and geometric patterns of the Brodatz textures, combined with an absence of intraclass transformations, makes them a good platform for testing the discriminative power of an additional local shape channel in a context where affine invariance is not necessary, as described below.

The shape channel. The shape of an affinely adapted region is encoded in its local shape matrix, which can also be thought of as the equation of an ellipse. Let E 1 and E 2 be two ellipses in the image plane. We eliminate the translation between E 1 and E 2 by aligning their centers, and then compute the dissimilarity between the regions as

d(E 1 , E 2 ) = 1 - Area (E 1 ∩ E 2 ) Area (E 1 ∪ E 2 ) .
In the experiments of this section, we use local shape to obtain two additional channels, HE and LE, corresponding to the ellipses found by the Harris and Laplacian detectors, respectively. Notice that the ellipse ground distance, and consequently all shape-based EMD's, must be between 0 and 1. Because the descriptor-based EMD's lie in the same range, the shape-based EMD's can be combined with them through simple addition.

Finally, it is worth noting that the ellipse "distance" as defined above takes into account the relative orientations of the two ellipses. If it is necessary to achieve rotation invariance, we can simply align the major and minor axes of the two ellipses before comparing their areas.

Results. The Brodatz database consists of 111 images. Following the same procedure as previous evaluations [START_REF] Liu | Periodicity, directionality, and randomness: Wold features for image modeling and retrieval[END_REF][START_REF] Picard | Real-time recognition with the entire Brodatz texture database[END_REF][START_REF] Xu | Performance analysis in content-based retrieval with textures[END_REF], we form classes by partitioning each image into nine nonoverlapping fragments, for a total of 999 images. Fragment resolution is 215 × 215 pixels. By comparison with the texture database discussed in the previous section, relatively few regions are extracted from each image: The median values are 132 for the Harris detector, 681 for the Laplacian, 838 combined. Some images contain less than 50 regions total. Given such small numbers, it is difficult to select a fixed number of clusters suitable for all images in the database. To cope with this problem, we replace k-means by an agglomerative clustering algorithm that repeatedly merges clusters until the average intra-cluster distance exceeds a specified threshold [START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF]. This process results in variable-sized signatures, which are successfully handled by the EMD framework. An additional advantage of agglomerative clustering as opposed to k-means is that it can be used for the shape channel, since it can take as input the matrix of pairwise distances between the ellipses. recall is only 44.59%. However, adding these channels to (H+L)(S+R) boosts the recall from 70.94% to 76.26%.

The trends noted above are also apparent in the classification results presented in Table 4.

By looking at the first two rows, we can easily confirm the relatively strong performance of the RIFT descriptor (particularly for the Laplacian detector), as well as the marginal drop in performance of the L+H channels as compared to L alone. The latter effect is also seen in the last row of the We can get a more detailed look at the performance of our system by examining Figure 10, The best retrieval performance curve of our system, corresponding to the (H+L)(S+R+E) combination, has 76.26% recall after 8 retrievals. This is a slightly higher than the results reported in [START_REF] Liu | Periodicity, directionality, and randomness: Wold features for image modeling and retrieval[END_REF][START_REF] Picard | Real-time recognition with the entire Brodatz texture database[END_REF], but below Xu et al. [START_REF] Xu | Performance analysis in content-based retrieval with textures[END_REF], who report 84% recall using the multiresolution simultaneous autoregressive (MRSAR) model. MRSAR models texture as a stationary random field and uses a dense representation with fixed neighborhood shape and size. A known shortcoming of MRSAR is its limited ability to measure perceptual similaritythe method tends to confuse textures that appear very different to human observers [START_REF] Liu | Periodicity, directionality, and randomness: Wold features for image modeling and retrieval[END_REF].

which
Most significantly, the MRSAR model is difficult to extend with affine invariance. By contrast, our representation is specifically formulated with geometric invariance in mind, is non-parametric, and does not make any statistical assumptions about the input texture. In this article, we have introduced a sparse affine-invariant texture representation that applies spatial and shape selection to automatically determine the locations and support regions of salient local texture regions. In summary, the main contributions of our work are:

• A sparse representation: The experiments of Section 4 show that it is possible to successfully recognize many textures based on information contained in a very small number of image regions.

• Spatial and shape selection: These mechanisms provide robustness against viewpoint changes, non-rigid deformations, and non-homogeneity of the texture pattern. In addition, affine regions capture important perceptual characteristics of many textures.

• Novel intensity-based descriptors: Spin images and RIFT descriptors, presented in Section 3.2, provide a high degree of invariance while serving as a rich description of the intensity pattern of local texture patches.

• A flexible approach to invariance: Our system is flexible in that local shape information may either be discarded or used as a feature, depending on the degree of invariance required by the application.

In our experiments, we have evaluated two detectors and two descriptors on two datasets of about a thousand images each. The first dataset has tested the invariance of our proposed representation to viewpoint changes, as well as complex appearance changes and nonrigid deformations. A comparative evaluation with the VZ method [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF] has confirmed that representation-level affine invariance is necessary for achieving good performance on a relatively sparse dataset with high intra-class variability. However, it remains to be determined whether the advantage of our method will persist when the training set can be made to include representative samples of all variations that are likely to appear at testing time. In this case, it is possible that our approach, which throws away potentially useful information in the process of computing invariants, would prove less discriminative than an approach based on multiple view-dependent prototypes. We plan to investigate this possibility in future evaluations.

Our second set of experiments, carried out on the Brodatz database, has allowed us to test the descriptive power of the local shape information captured by the affine region detectors.

As shown in Figure 9 (d), augmenting our model with an additional shape channel has boosted the recall rate by almost 5%, from 70.94% to 76.26%. However, because these results are still somewhat inferior to those reported by a non-invariant method [START_REF] Xu | Performance analysis in content-based retrieval with textures[END_REF], one might wonder whether our strategy of factoring out shape in order to compute invariant appearance descriptors, and then adding it back in as a separate "ellipse channel," may actually produce a less expressive model (at least, for this particular database) than an approach that does not separate appearance and shape. Addressing this issue is another interesting direction for further research.

Next, let us briefly summarize the findings of Section 4. The Laplacian detector has shown better overall performance for both texture datasets; nevertheless, as can be seen from Table 3, the Harris detector can have superior performance for certain individual classes. The Harris detector also has the advantage of producing much sparser image representations than the Laplacian. As for descriptors, spin images won over RIFT for the texture database in Section 4.2, while RIFT worked slightly better for the Brodatz database in Section 4.3 (however, recall that the latter comparison is confounded by signature size variability). Despite these differences in performance, it is advantageous to retain both descriptors, as combining their outputs generally improves the accuracy of recognition.

Perhaps the most important high-level observation we can make is that both the descriptors and the detectors tend to fluctuate in performance from texture to texture and from database to database. Two lessons can be drawn from this. On the one hand, researchers working on specific applications of texture analysis should conduct comparative evaluations on representative data to discover which channels or channel combinations would work best in their case. On the other hand, to achieve a general understanding of the expressive power of different channels on different types of texture, it is necessary to conduct systematic studies using much larger databases (containing hundreds or even thousands of texture classes), as well as larger numbers of descriptors and detectors, or even parameterized descriptor/detector families. Such studies should focus on quantifying performance as a function of all sources of variability that may be of interest. Currently, our dataset includes some dimensions, like non-rigidity of the surface and inhomogeneity of the texture pattern, that seem difficult to quantify precisely. An important future research direction is the development of systematic evaluation techniques suitable for dealing with large-scale datasets featuring many degrees of freedom.

Another issue requiring further study is the method for combining channels. In our limited evaluation, the simple method of adding the individual EMD matrices has generally proven effective in boosting performance. However, as we have learned from our Brodatz experiments, it is occasionally possible for the combined recognition rate to actually be lower than the single-channel rates. We plan to study more sophisticated methods for combining channels that would not suffer from similar detrimental effects.

Finally, we plan to strengthen the proposed texture representation using spatial relationships between neighboring regions. A few recent representations [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF][START_REF] Schmid | Constructing models for content-based image retrieval[END_REF] have used a two-level scheme, with intensity-based textons at the first level and histograms of texton distributions over local neighborhoods at the second level. For many natural textures, the arrangement of affine regions captures perceptually important information about the global geometric structure. Augmenting our representation with such information is likely to increase its ability to distinguish textures that have similar local neighborhoods but different spatial layouts.

To date, we have conducted preliminary experiments in classification of individual texture regions using simple co-occurrence relations [START_REF] Lazebnik | Affine-invariant local descriptors and neighborhood statistics for texture recognition[END_REF]. We expect that a richer two-level texture representation will be useful for the problem of segmenting and classifying natural images that contain multiple texture categories such as sky, water, plants, and man-made structures.

At the feature extraction stage, all N × N pixel neighborhoods in an image are taken and reordered to form N 2 -dimensional feature vectors. In our implementation, N = 11 for 121-dimensional features. This was selected as the smallest neighborhood size to yield a feature space of higher dimensionality than spin images. To provide some invariance to illumination changes, the vectors are normalized to zero mean and unit norm. To compute the texton dictionary, five images per class are chosen at random, and 20% of all feature vectors extracted from these images are retained, also at random. This reduction in the number of feature vectors is motivated primarily by the memory limitations of our system.

The feature vectors for all 25 classes are clustered using k-means into 40 clusters each, resulting in a dictionary of 1000 textons. For the VZ-joint variant, each pixel in an image is labeled by its nearest texton center, and the distribution of all texton labels is represented using a 1000-dimensional histogram. For the VZ-MRF variant, an image is represented using a two-dimensional histogram: For each texton, a conditional distribution of the center pixel is stored as a histogram with 20 bins. This gives us a 20, 000-dimensional representation for each image. In both cases, histograms are compared using the χ 2 distance, and nearestneighbor classification is used.

Figure 1 :

 1 Figure 1: The effect of spatial selection on a texton dictionary. (a) Original texture image. (b) Top 20 textons found by clustering all 13 × 13 patches of the image. (c) A sparse set of regions found by the Laplacian detector described in Section 3.1. Each region is normalized to yield a 13 × 13 patch. (d) Textons obtained by clustering the normalized patches.1

Figure 2 :

 2 Figure 2: The architecture of the feature extraction system proposed in this article.

Figure 3 :

 3 Figure 3: Output of the Harris and Laplacian region detectors on two natural images. Left: original images, center: regions found by the Harris detector, right: regions found by the Laplacian detector. Note that the Laplacian detector tends to produce a denser set of regions than the Harris.

  -domain spin images. Our first rotation-invariant descriptor is inspired by the spin images introduced by Johnson and Hebert[START_REF] Johnson | Using spin images for efficient object recognition in cluttered 3d scenes[END_REF] for matching range data. The intensitydomain spin image proposed in this article is a two-dimensional histogram encoding the distribution of image brightness values in the neighborhood of a particular reference (center) point. The two dimensions of the histogram are d, distance from the center point, and i, the intensity value. 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.

Figure 4 :

 4 Figure 4: Construction of spin images. Three sample points in the normalized patch (left) map to three different locations in the descriptor (right).

Figure 5 :

 5 Figure 5: Construction of RIFT descriptors. Three sample points in the normalized patch (left) map to three different locations in the descriptor (right).

algorithm with k = 40 Figure 6 :Figure 7 :

 4067 Figure 6: Four samples each of the 25 texture classes used in the experiments of Section 4.2.The entire database may be downloaded from http://www-cvr.ai.uiuc.edu/ponce grp.

Figure 7

 7 Figure7shows retrieval results for the texture database. The first observation is that spin images perform better than RIFT descriptors, and the combination of the two descriptors performs slightly better than spin images alone. Next, Laplacian regions (part (b) of the figure) perform better than Harris (a), and the combination of the two (c) is slightly better than Laplacian alone. The solid curve in part (c) of the figure shows the retrieval performance obtained by combining all four detector/descriptor channels. The recall after 39 retrievals is 58.92%. This relatively low number is a reflection of the considerable intra-class variability of the database. As discussed in Section 4.1, we cannot expect that all samples of the same class will be well represented by a single prototype. Accordingly, the combined (H+L)(S+R) classification rate is only 62.15% for one training sample, but it goes up rapidly to 92.61% for 10 samples and 96.03% for 20 samples. Table2shows a comparison of 10-sample classification

Figure 8

 8 Figure 8 also confirms the reliance of the VZ methods on multiple prototypes: When the training set size is increased from 10 to 20, the classification rates of VZ-Joint and VZ-MRF

Figure 9 :

 9 Figure 9: Retrieval curves for the Brodatz database. (a) Harris descriptor channels. (b) Laplacian descriptor channels. (c) Combined Harris and Laplacian descriptor channels. (d) Comparison of combined performance with and without the ellipse channels (HE and LE).

Figure 9

 9 Figure 9 shows retrieval results for the Brodatz database. Similarly to the results of the previous section, the Laplacian channels, shown in part (b) of the figure, have better performance than the Harris channels, shown in part (a). Interestingly, though, for the Brodatz database RIFT descriptors perform better than spin images -the opposite of what we have found in Section 4.2. However, this discrepancy is due at least in part to the variability of signature size (due to the use of agglomerative clustering) in the experimental setup of this section. On average, the RIFT-based signatures of the Brodatz images have more clusters than the spin-based signatures, and we conjecture that this raises the discriminative power of the RIFT channel. Another interesting point is that combining the Harris and Lapla-

  shows a histogram of classification rates for all 111 classes using three training samples per class. The histogram reveals that the majority of textures are highly distinguishable, and only a few stragglers are located at the low end of the spectrum. In fact, 36 classes have 100% classification rate, 49 classes have classification rate at least 99%, and 73 classes (almost two thirds of the total number of classes) have rate at least 90%. The mean rate is 87.44%.

Figure 11 shows

 11 Figure11shows four textures that were classified successfully and four textures that were classified unsuccessfully. Not surprisingly, the latter examples are highly non-homogeneous.

Figure 10 :

 10 Figure 10: Histogram of classification rates for 3 training samples.

Figure 11 :

 11 Figure 11: Left: successes. Right: failures. The average classification rates are shown below the corresponding class labels. Note that the representation for D48 has an average number of only 27 combined Laplacian and Harris regions per sample.

Table 2 :

 2 To check this conjecture, we have repeated the recognition experiments after thresholding the output of the Laplacian detector so that equal numbers of Laplacian and Harris regions are produced for each image. The results of the "truncated" Classification results for 10 training samples per class. First column (top to bottom):

		H	L	H+L
	S	0.8332 0.8829 0.9015
	R	0.7927 0.8318 0.8547
	S+R 0.8814 0.9196 0.9261
	HS, HR, H(S+R). Second column: LS, LR, L(S+R). Third column: (H+L)S, (H+L)R,
	(H+L)(S+R).

Table 3 :

 3 Detailed breakdown of classification results summarized inTable 2. The classes are sorted in order of increasing classification rate (last column). See text for discussion. slightly outperforms VZ-Joint (64.75% vs. 66.09% for 10 training images), though this is considerably below the 92.61% rate achieved by our (H+L)(S+R) method. A closer look at

Table 4 :

 4 Brodatz database classification results for 3 training samples.

	table, where the (H+L)(S+R+E) classification rate is slightly inferior
	to the L(S+R+E) rate.
		H	L	H+L
	S	0.6136 0.7570 0.7531
	R	0.6000 0.8023 0.7640
	E	0.3678 0.4932 0.5413
	S+R+E 0.7761 0.8815 0.8744

For the sake of this illustration, we disregard the orthogonal ambiguity inherent in the normalization process (see Section 3.1 for details). Because we are clustering the normalized patches themselves, instead of rotation-invariant descriptors as in Section 3.2, the resulting description of patch appearance in this case is rotation-dependent. This can be seen from the fact that the second and third clusters of (d) are rotated versions of each other.

More accurately, they should be termed affine-covariant: In principle, the regions found in a picture deformed by some affine transformation are the images of the regions found in the original picture under the same transformation.

Note that we have implemented simplified versions of the algorithms given in[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]. In particular, the affine adaptation process is not iterated, and the local (differentiation) scale is fixed, instead of being automatically determined at each iteration. See also[1,

[START_REF] Schaffalitzky | Viewpoint invariant texture matching and wide baseline stereo[END_REF][START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?[END_REF] for related approaches to region extraction.

The original SIFT descriptor has 128 dimensions, as it is based on subdividing a square image patch into 16 smaller squares. To achieve rotation invariance, we must use concentric rings instead, hence the drop in dimensionality for RIFT.

Acknowledgments

This research was partially supported by the National Science Foundation under grant IIS-0308087, the European project LAVA (IST-2001-34405), the UIUC Campus Research Board, the UIUC-CNRS collaboration agreement, and the Beckman Institute for Advanced Science and Technology. We also wish to thank Andrew Zisserman and Manik Varma for many useful discussions, and the anonymous reviewers for their constructive comments that have helped us to improve this article.

Comparative evaluation. The results presented in this section clearly show that our local affine-invariant representation is sufficient for the successful recognition of textures on (possibly non-rigid) surfaces in three dimensions. To answer the question of whether its invariance properties are actually necessary, we have performed a comparative evaluation with the non-invariant algorithm recently proposed by Varma and Zisserman [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF]. This method, dubbed VZ in the following, uses a dense set of 2D textons; the descriptors are raw pixel values measured in fixed-size neighborhoods (perhaps surprisingly, this feature representation was found to outperform the more traditional filter banks). We chose the VZ method for comparison because it achieves the best classification rates to date on the CUReT database (up to 97.47%). We have tested two variants of VZ: In the first one, texture images are described by one-dimensional texton histograms encoding the joint distribution of all pixel values in the neighborhood; in the second, they are represented using two-dimensional histograms that encode the conditional distribution of the center pixel given its neighborhood.

Accordingly, the respective variants are dubbed VZ-joint and VZ-MRF (for Markov Random Field). The details of our implementation are given in the Appendix.

We have compared our method with with VZ-Joint and VZ-MRF using the randomized classification scheme described in Section 4.1. Figure 8 shows the results as a function of training set size. Consistent with the findings of Varma and Zisserman [START_REF] Varma | Texture classification: Are filter banks necessary?[END_REF], VZ-MRF


Fred Rothganger

Svetlana Lazebnik

Cordelia Schmid

Jean Ponce

Segmenting, Modeling, and Matching Video Clips Containing Multiple Moving Objects

This paper presents a novel representation for dynamic scenes composed of multiple rigid objects that may undergo different motions and be observed by a moving camera. Multi-view constraints associated with groups of affine-invariant scene patches and a normalized description of their appearance are used to segment a scene into its rigid parts, construct three-dimensional projective, affine, and Euclidean models of these parts, and match instances of models recovered from different image sequences. The proposed approach has been implemented, and it is applied to the detection and recognition of moving objects in video sequences and the identification of shots that depict the same scene in a video clip (shot matching).

Introduction

This paper addresses the problem of recognizing threedimensional (3D) objects in video clips. Viewpoint invariants (or invariants for short) provide a natural indexing mechanism for object recognition tasks. Unfortunately, although planar objects and certain simple shapes (e.g., bilaterally symmetric ones) 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]. We have shown in [START_REF] Rothganger | 3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints[END_REF] that invariants provide a valuable local description for 3D objects: Indeed, although smooth surfaces are almost never planar in the large, they are always planar in the smallthat is, sufficiently small surface patches can always be thought of as being comprised of coplanar points. The surface of a solid can thus be represented by a collection of small patches, their invariants, and a description of their 3D spatial relationship. Specifically, we proposed in [START_REF] Rothganger | 3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints[END_REF] to represent the surface of a solid by a collection of (small, planar) affine-invariant patches as proposed by Lindeberg and Gårding [START_REF] Lindeberg | Shape-adapted smoothing in estimation of 3-D shape cues from affine deformations of local 2-D brightness structure[END_REF] and Mikolajczyk and Schmid [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF], and a description of their 3D spatial relationship in terms of the multi-view geometric consistency constraints studied in the structure-from-motion literature [START_REF] Faugeras | The Geometry of Multiple Images[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF].

The approach proposed in [START_REF] Rothganger | 3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints[END_REF] was intended for tasks such as modeling rigid 3D objects from a few unregistered still pictures and identifying these models in photographs of cluttered scenes [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighborhoods[END_REF]. It is combined in this paper with the proven technology now available for tracking rigid and articulated objects [START_REF] Birchfield | KLT: An implementation of the Kanade-Lucas-Tomasi feature tracker[END_REF][START_REF] Bregler | Tracking people with twists and exponential maps[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF][START_REF] Zhang | Token tracking in a cluttered scene[END_REF] and a new (as far as we know) locally affine model of image projection, resulting in a novel algorithm for segmenting a dynamic scene into its rigid parts, constructing projective, affine and Euclidean models of these parts, and matching instances of the models recovered from different image sequences.

The proposed approach has been implemented, and it is applied to the identification of shots that depict the same scene in a film (shot matching) [START_REF] Aner | Video summaries through mosaic-based shot and scene clustering[END_REF][START_REF] Ardebilian | Video segmentation using 3D hints contained in 2D images[END_REF][START_REF] Benayoun | Structuration de vidéos pour des interfaces de consultation avancées[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], a fundamental task in the annotation/indexing context where videos are commonly segmented into shots [START_REF] Gargi | Performance characterization of video-shot-change detection methods[END_REF][START_REF] Lienhart | Reliable transition detection in videos: A survey and practitioner's guide[END_REF]. Preliminary results are presented using both laboratory videos and shots from the film "Run Lola Run".

Local Invariants and Global 3D Constraints

The approach proposed in [START_REF] Rothganger | 3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints[END_REF] combines a normalized representation of local surface appearance in terms of local affine-invariant patches [START_REF] Lindeberg | Shape-adapted smoothing in estimation of 3-D shape cues from affine deformations of local 2-D brightness structure[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] with the global 3D affine multi-view constraints studied in the structure-frommotion literature [START_REF] Faugeras | The Geometry of Multiple Images[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF] to effectively represent the surfaces of solids in modeling and recognition tasks. We briefly recall the main ideas of this approach in Sections 2.1 and 2.2 before introducing in Section 2.3 a new, locally affine model of the image formation process capable of handling the large global perspective distortions common in urban scenes for example.

Affine-Invariant Patches

Operators capable of finding affine-invariant [START_REF] Baumberg | Reliable feature matching across widely separated views[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF][START_REF] Pritchett | Wide baseline stereo matching[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighborhoods[END_REF] image descriptors in the neighborhood of salient image features ("interest points" [START_REF] Harris | A combined edge and corner detector[END_REF]) have recently been proposed in the context of wide-baseline stereo matching and image retrieval. We use an implementation of the affineinvariant region detector developed by Mikolajczyk and Schmid [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] for low-level image description. Its output consists of a set of image patches in the shape of parallelograms, together with the corresponding affine rectifying transformations. The transformation R associated with 1 each patch maps the corresponding parallelogram onto a square with unit edge half-length centered at the origin (Fig. 1). The rectified patch is a normalized representation of the local surface appearance that is invariant under planar affine transformations. Such transformations are induced by arbitrary changes in viewpoint under the affine (orthographic, weak-perspective, or para-perspective) projection model as well as the locally affine model introduced in Section 2.3. The rectifying transformation associated with a planar patch and its inverse can be represented by two 2 × 3 matrices R and S that map homogeneous (affine) plane coordinates onto non-homogeneous ones. The column vectors of the matrix S admit a simple geometric interpretation [START_REF] Rothganger | 3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints[END_REF]: The third column c of S is the coordinate vector of the patch center c, and its first two columns h and v are respectively the coordinate vectors of the "horizontal" and "vertical" vectors joining c to the sides of the patch (Fig. 1).

Affine Projection Constraints

Let us consider n patches observed in m images (we will assume for the time being that all patches are visible in all images), and denote by S ij the corresponding 2 × 3 matrices as defined in Section 2.1. Here i and j respectively serve as image and patch indices, with i = 1, . . . , m and j = 1, . . . , n. Under affine projection, the matrix S ij records the projection of a parallelogram drawn on the surface into the corresponding image. Thus it can be written as S ij = M i N j , where M i is the projection matrix associated with image number i and

N j = H j V j C j 0 0 1
gives the position and shape of patch j on the surface of the object. The vectors H j , V j , and C j are the 3D analogs of h j , v j , and c j and have a similar interpretation. We follow Tomasi and Kanade [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF] and pick the center of mass of the observed patches' centers as the origin of the world coordinate system, and the center of mass of these points' projections as the origin of every image coordinate system: In this case, the projection matrices reduce to

M i = [ A i 0 ],
where A i is a 2 × 3 matrix, and

S ij = A i B j , where B j = [H j , V j , C j ]. (1)
It follows that the reduced 2m × 3n matrix Ŝ = Â B, where

 def =   A 1 . . . A m   , B def = [ B 1 . . . B n ] ,
has at most rank 3. Singular value decomposition can be used as in Tomasi and Kanade [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF] to factorize Ŝ and compute estimates of the matrices  and B that minimize the squared Frobenius norm of the matrix Ŝ - B. The residual (normalized) Frobenius form | Ŝ - B|/ √ 3mn of this matrix can be interpreted geometrically as the root-meansquared distance (in pixels) between the predicted and observed values of of c ij , h ij , and v ij .

Locally Affine Projection Constraints

We assume in this section that the relief of each patch is small compared to the overall depth of the scene, so that an affine projection model is appropriate for each patch, yet a global affine projection model is inappropriate (this is the case for scenes with important perspective distortions such as the street scenes used in some of our experiments). A local affine model is obtained by linearizing the perspective projection equations in the neighborhood of the patch center. Consider the homogeneous projection equation

(a 3 • P + 1) p 1 = MP = A b a T 3 1 P ,
where M is the perspective projection matrix, A is a 2 × 3 sub-matrix of M, p is the non-homogeneous coordinate vector for the point in the image, and P is the homogeneous coordinate vector of the point in 3D. We can write the perspective projection mapping as

p = f (P ) = 1
a 3 • P + 1 (AP + b), (2)
and a Taylor expansion of order 1 of the function f in P yields f (P + δP ) = p + δp = f (P ) + f (P )δP , or

δp = f (P )δP = A(a 3 • P + 1) -(AP + b)a T 3 (a 3 • P + 1) 2 δP = 1 a 3 • P + 1 (A -pa T 3 )δP .
In particular, consider a patch defined by its center C and the directions H and V . Taking P = C and δP = H (resp. V ) and δp = h (resp. v) yields

(a 3 • C + 1) [ h v ] = (A -ca T 3 ) [ H V ] . (3)
Finally, taking c = p in (2) yields

c(a 3 • C + 1) = AC + b, c = (A -ca T 3 )C + b. (4)
Given a fixed projection matrix M, putting Eqs. ( 3) and ( 4) together now yields a system of 6 linear equations in the 9 unknown coordinates of H, V , and C:

  A -ca T 3 0 T -ha T 3 0 T A -ca T 3 -va T 3 0 T 0 T A -ca T 3   H V C = h v c - 0 0 b . ( 5
)
Given fixed vectors H, V , and C, Eqs. ( 3) and ( 4) also provide a system of 6 linear equations in the 11 unknown entries of M:

  H -hC T -cH T 0 2 V -vC T -cV T 0 2 C -cC T Id 2      a 1 a 2 a 3 b    =   h v c   , (6)
where 0 2 and Id 2 are respectively the 2×2 zero and identity matrices, a T 1 and a T 2 are the first two rows of M 1 , and

H = H T 0 T 0 T H T , V = V T 0 T 0 T V T , C = C T 0 T 0 T C T .
Given n patches observed in m images, we can use the following iterative process1 to solve for the corresponding matrices M i (i = 1, . . . , m) and vectors H j , V j , and C j (j = 1, . . . , n):

(1) Initialize the vectors Hj , V j , Cj (j = 1, . . . , n) using the affine method described in section 2.2.

(2) Repeat until convergence:

(a) For i = 1, . . . , m, use linear least-squares to solve for Mi by stacking the ni instances of Eq. ( 6) associated with the patches observed in image i.

(b) For j = 1, . . . , n, use linear least-squares to solve for Hj , V j , Cj by stacking the mj instances of Eq. ( 5) associated with the images containing patch j.

Given the ambiguity of projective structure from motion, we have 6mn equations in 11m + 9n -15 unknowns. These equations are redundant whenever n ≥ 2 image tracks share at least m ≥ 3 frames, and it is possible to judge whether the corresponding patches rigidly move together by solving for the structure and motion parameters and measuring as before the mean-squared distance in pixels between the predicted and measured values of the vectors c ij , h ij , and v ij . Note that, unlike factorization, this methods is readily adapted to the case where patches are only available in some of the images.

Model Construction and Motion Segmentation

Although it is relatively challenging to match patches between two widely separated views (such as discussed in [START_REF] Rothganger | 3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints[END_REF]), it is easy to match them in a continuous image sequence, thanks in part to the recent emergence of reliable techniques for tracking rigid and articulated objects [START_REF] Birchfield | KLT: An implementation of the Kanade-Lucas-Tomasi feature tracker[END_REF][START_REF] Bregler | Tracking people with twists and exponential maps[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF][START_REF] Zhang | Token tracking in a cluttered scene[END_REF], but also to the normalized appearance model of the patches themselves, which is (in principle) invariant under viewpoint and illumination changes. The remaining difficulties in this setting are the identification of groups of image patches that move rigidly together, and the effective estimation of the corresponding structure and motion parameters.

We propose in this section a simple approach to these two problems, assuming for simplicity that points moving rigidly together do so over all the frames in which they are visible (which may of course not be true in all videos). Our algorithm maintains a list M of growing models and a list T of unassigned tracks, updating the two lists and the structure and motion parameters associated with the elements of M at time stamps t 1 , . . . , t k regularly sampled over the m frames of the video. Here, a track is the set of images where a patch is visible, along with the corresponding matrices S ij , and a model is a set of tracks rigidly moving together, along with the corresponding structure and motion parameters. The algorithm outputs M after it has gone through all time stamps. It proceeds as follows:

(1) Initialize M to the empty set. Initialize T to all tracks found in the image sequence.

(2) For t = 1 to k do: -(a) Run the seeding procedure (described later in this section) on the subset of T visible at time t. For each new model found, add it to M , remove its associated tracks from T , and estimate its structure and motion parameters. The seeding procedure used to initialize new models follows the segmentation approach in [START_REF] Fitzgibbon | Multibody Structure and Motion: 3-D Reconstruction of Independently Moving objects[END_REF]: Given a set of points (in our case tracks), select the largest consistent subset, remove it, and repeat until no more large consistent subsets may be found. To select a consistent subset, we use a modified form of the RANSAC algorithm [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF]. It first deterministically grows small sets of tracks that are likely to be rigidly connected (analogous to the random sampling part of RANSAC), and then finds all other compatible tracks (exactly like the consensus part of RANSAC). It relies heavily on the fact that, as noted in the previous section, two overlapping tracks of patches rigidly moving together generally provide an over-constrained system of equations on the corresponding structure and motion parameters, so the consistency of a pair of tracks can be assessed by measuring the reprojection error. In addition, the motion parameters can be used to assess the consistency of other tracks. The algorithm proceeds as follows, starting with an empty M .

Grow seeds:

(1) S ← {}.

Form consensus:

(4) For each sufficiently large seed, find its consensus set, i.e., the tracks whose reprojection errors are below a second threshold E2, and add it to the seed.

(5) If the largest seed found is larger than some threshold, reestimate the corresponding structure and motion parameters, add it to M (permanently removing its components from the set of unassigned tracks), and go to (1). ( 6) Output M .

In practice, we use E 1 = 0.08pixel, and E 2 = 1pixel. The reason for picking such a small value for E 1 is to ensure that the corresponding structure and motion parameters are estimated precisely enough to bootstrap the modeling process. The sub-pixel tracking method used in our experiments (see Section 5) allows us to find numerous seeds with errors below this value. Note that the structure and motion parameters are kept fixed during the consensus formation phase (step 4) of our algorithm, as is customary in RANSAC. On the other hand, they are re-estimated at each stage of seed formation (step 3 of the algorithm) to increase the reliability of that stage at relatively low cost.

Given a set of tracks and an initial estimate of the structure and motion parameters, it is easy to update the parameters as new tracks are added. The iterative process described in Section 2.3 directly supports this, since it treats the patch and projection matrices independently. However, more work is required to form the estimate of structure and motion for the first time, because it must handle missing data (i.e., places where some images lack measurements for some patches). One solution is find full blocks (subsets of the images and patches such that all patches appear in all images), factorize each block, and then register the resulting sub-models into a single global model. Full blocks can be found efficiently using an interval graph algorithm similar to those described in [START_REF] Gupta | Efficient algorithms for interval graphs and circular-arc graphs[END_REF].

Once an affine or locally affine model is available, it is a simple matter to compute (if necessary) the corresponding Euclidean model when some of the camera intrinsic parameters are known using one of the self-calibration techniques available in that case for affine or projective cameras [START_REF] Poelman | A paraperspective factorization method for shape and motion recovery[END_REF][START_REF] Pollefeys | Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF].

Model Matching

We now assume that the technique described in the previous section has been used to create a number of 3D models for the rigid components of a scene observed in a video, and address the problem of matching the models associated with different video clips, or with different shots within a single video. The approach we have chosen is essentially a 3D affine or projective alignment method (see [START_REF] Faugeras | The representation, recognition, and locating of 3-D objects[END_REF][START_REF] Johnson | Surface matching for object recognition in complex three-dimensional scenes[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] for related work), aided by the facts that (1) the normalized appearance of affine-invariant patches can be used to select promising matches between tracks, and (2) a pair of matches is sufficient to estimate the affine or projective alignment transformation. A match is a pair of 3D patches, one in each model. Each 3D patch contains three points (its center and two corners), so each match provides three point matches, and a pair of matches provides six point matches. The algorithm is an application of the same modified RANSAC algorithm used in the seeding procedure described earlier, because the goal is similar: find the largest subset of consistent matches.

(1) Build a set T of potential matches by pairing each patch in the first model to the k closest patches in the second model, based on similarity of appearance.

RANSAC-like selection of consistent matches:

(2) For each match Ti in T , generate a new seed Si.

(3) For each seed Si, do: -(a) Find the match Tj not in Si, that, when used jointly with the matches in Si, minimizes the alignment error. -(b) If the error is below some threshold E1, add the match to Si, and goto (a). (4) For each sufficiently large seed, find its consensus set. Specifically, estimate the corresponding alignment transformation and select all matches whose error is below a second threshold E2.

(5) Retain the seed with the largest consensus set and recompute the aligning transformation. Expand the set of matches: [START_REF] Birchfield | KLT: An implementation of the Kanade-Lucas-Tomasi feature tracker[END_REF] Add more matches to the final result using the aligning transformation as a guide. New matches must have error below E2.

A notable difference between this algorithm and the seeding procedure used in segmentation and modeling is that candidate matches to be added to the support set are used to compute the alignment parameters before computing the corresponding error. This is because the projective alignment estimates obtained from only two matches have proved unreliable in our experiments. The threshold E 1 is chosen as the average of the alignment errors found by exhaustively checking all pairs of matches in T . The threshold E 2 is chosen as half the average distance between patch centers in the first model.

The job of the "expansion" phase is to find all possible true matches between the two models, including those that may have been missed by comparing patch appearance.

The number of true matches provides a similarity measure between the models. Specifically, we use the repeat rate M/ min(A, B), where M is the number of matches, A is the number of patches in one model, and B is the number of patches in the other.

Implementation and Results

We have implemented the proposed approach, and this section presents preliminary modeling and matching experiments. Affine-invariant patches are found and tracked using a variant of the Kanade-Lucas-Tomasi (KLT) feature tracker [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF], tuned to track affine-invariant patches with sub-pixel localization. Concretely, we have augmented Birchfield's implementation [START_REF] Birchfield | KLT: An implementation of the Kanade-Lucas-Tomasi feature tracker[END_REF] of the KLT tracker as follows: For each new frame i, we find points in the image that aren't currently being tracked and determine their patch parameters using the affine-adaptation process described in [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF], providing an initial value for the matrix S ij associated with each patch j. For all patches that are currently being tracked (i.e., that exist in frame i -1), we use the KLT tracker to update the location of the patch center in frame i, and then use non-linear least squares to refine the parameters of the patch, maximizing the normalized correlation between the patch in frame i and the same patch in the frame where it first appeared. In addition to the criteria that KLT itself uses to stop tracking a point, we also check whether the ratio of the dimensions of the patch exceed some threshold, and whether the correlation with the initial patch falls below some threshold (currently 0.95). It takes an average of 30 seconds to process one frame of video. In practice, this technique gives excellent results, yielding very robust tracking results as well as sub-pixel localization, which is crucial for the reliability of the multi-view constraints used in segmentation and modeling.

We have conducted preliminary experiments using both laboratory videos and shots from the film "Run Lola Run", and Figures 2 and3 below show some results. Representative videos are also available on our group web site.

Figure 2 show the results of our laboratory experiments using videos of stuffed animals. The top two rows show the result of a segmentation experiment using a bear and a dog rotating independently, but with similar speeds and axes of rotation. The segmentation program returns three models, one for the bear, and two for the dog. Essentially, it is unable to continue growing the first dog model when it presents its narrow side to the camera, and we obtain one model for each side of the dog. Slight over-segmentation due to rapid image changes, occlusion, or other factors is a recurring problem in our experiments, but it does not necessarily hamper applications such as shot matching since multiple models can in principle be matched independently. Representative frames of the video are shown in the figure, along with the corresponding patches and reprojections of the estimated models, surrounded by a black frame. The third row of Figure 2 shows a second segmentation experiment, where the head of the bear is moved by hand independently from its body. The head is found as one segment, and the body is (over) segmented into three components. The fourth row of the figure shows the bear models constructed from the bear-and-dog video and from a different video of the bear alone, along with the recovered cameras. The last row of the figure shows the result of matching. The model on the right has been aligned with the model on the left, and a red "+" marks the origin of the left model's coordinate system. It took about 210 seconds to match these two models.

Figure 3 shows similar results for several shots from the "Lola" video. The first two rows show two frames of a shot, along with the corresponding patches and reprojected models. Here, Lola runs around a street corner while a car drives down the street and toward the camera. The car is segmented correctly, while the rest of the street, which is static, is, as usual, slightly over-segmented. Note that Lola is not found as a part of any model. This is typical for nonrigid objects, since the motion segmentation algorithm is based on rigidity constraints. (We conjecture that such objects can be found by first subtracting all rigid components from the scene and then using a 2D motion coherence constraint, but we have not had a chance to experiment with this idea yet.) Also note that although the camera remains still in that particular part of the shot, it moves in earlier parts of the shot used to construct the street model shown in the figure. The third row shows the results of a matching experiment between the street model and another model computed from a different shot. The repeat rate is 17% in this case. The fourth row of the figure shows another segmentation experiment. In this case, the train is found as two distinct models by our program (only one of them is shown in the figure), and the static scene is found as 12 models. The camera is in constant and moderately complex motion. The last row shows the results of a matching experiment between models from the train scene taken from two different shots, with a repeat rate of 46%.

Although the segmentation, modeling, and matching results presented in this section are preliminary, we believe that they demonstrate the promise of the proposed approach with challenging datasets that include complex camera motions, multiple moving objects, large perspective distortions, and patches only visible in small parts of each shot. More experimental work is of course needed.

2 Figure 1 :

 21 Figure 1: Geometric interpretation of the rectification matrix R and its inverse S.

  -(b) Find the elements of T most consistent with each element Mi of M . If the reprojection error for a given element Tj relative to Mi is below some threshold, then add Tj to Mi and remove it from T . -(c) Update the structure and motion parameters associated with the elements of M . (3) Output M .

( 2 )

 2 For each track Ti in T , generate a new seed Si. (3) For each seed Si in S, do: -(a) Select the track in T most consistent with Si. -(b) If the reprojection error is below E1, add the track to Si, reestimate the model, and go to (a).

Figure 2 :

 2 Figure 2: Laboratory experiments using an affine projection model. See text for details.

Figure 3 :

 3 Figure 3: Experiments with shots from "Run Lola Run" using the locally affine projection model. See text for details.

See[START_REF] Mahamud | Provably-Convergent Iterative Methods for Projective Structure from Motion[END_REF] for related work in the purely projective structure-frommotion domain.

Acknowledgments. This research was supported in part by the National Science Foundation under grants IIS-0308087 and IIS-0312438, by the UIUC Campus Research Board and by the CNRS-UIUC Research Collaboration Agreements.