Svetlana Lazebnik
email: slazebni@uiuc.edu

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

Jean Ponce

A Sparse Texture Representation Using Affine-Invariant Regions

This paper introduces a texture representation suitable for recognizing images of textured surfaces under a wide range of transformations, including viewpoint changes and nonrigid deformations. At the feature extraction stage, a sparse set of affine-invariant local patches is extracted from the image. This spatial selection process permits the computation of characteristic scale and neighborhood shape for every texture element. The proposed texture representation is evaluated in retrieval and classification tasks using the entire Brodatz database and a collection of photographs of textured surfaces taken from different viewpoints.

Introduction

Over the past decade, computer vision literature has reported texture recognition schemes [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]] that perform impressively well on such challenging data sets as the Brodatz database [START_REF] Brodatz | Textures: A Photographic Album for Artists and Designers[END_REF]. Unfortunately, these schemes rely on restrictive assumptions about the input (e.g. texture must be stationary) and are not generally invariant with respect to 2D similarity and affine transformations, much less to 3D transformations caused by movement of the camera and non-rigid deformations of the textured surface. However, invariance to such transformations is desirable for many applications, including wide-baseline matching [START_REF] Mikolajczyk | An Affine Invariant Interest Point Detector[END_REF][START_REF] Schaffalitzky | Viewpoint Invariant Texture Matching and Wide Baseline Stereo[END_REF][START_REF] Tuytelaars | Matching Widely Separated Views based on Affinely Invariant Neighbourhoods[END_REF], texture-based retrieval [START_REF] Rubner | Texture-Based Image Retrieval Without Segmentation[END_REF][START_REF] Schmid | Constructing Models for Content-Based Image Retrieval[END_REF], segmentation of natural scenes [START_REF] Malik | Contour and Texture Analysis for Image Segmentation[END_REF], and recognition of materials [START_REF] Varma | Classifying Images of Materials: Achieving Viewpoint and Illumination Independence[END_REF].

In this paper, we design a texture representation that is invariant to any geometric transformations that can be locally approximated by an affine model. In practice, local affine invariants are capable of modeling not only global affine transformations of the image, but also perspective distortions and non-rigid deformations that preserve the locally flat structure of the surface (e.g. the bending of paper or cloth). Our goal is to develop a representation that addresses the problems of spatial selection (finding the most salient image locations for computing texture descriptors) and and shape selection (finding the characteristic size and shape of local texture neighborhoods).

The proposed method performs spatial and shape selec- tion by restricting the set of candidate texture elements to a sparse set of affine-invariant regions in the image. Several types of affine-invariant region detectors have recently been developed for applications of wide-baseline matching, indexing, and retrieval [START_REF] Mikolajczyk | An Affine Invariant Interest Point Detector[END_REF][START_REF] Tuytelaars | Matching Widely Separated Views based on Affinely Invariant Neighbourhoods[END_REF]. To us, these detectors represent powerful tools for creating sparse texture representations. In the current paper, we show how such representations may be built and investigate their effectiveness. The proposed method consists of four steps (see Figure 1):

1. Extract a sparse set of affine regions from a texture image (Section 2.1). 2. For each region, compute an intensity descriptor that is invariant to affine geometric and photometric transformations. In Section 2.2, we discuss a novel descriptor based on spin images [START_REF] Johnson | Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes[END_REF].

Perform clustering on the affine-invariant descriptors

and summarize the distribution of descriptors in the form of a signature consisting of cluster centers and relative weights (Section 2.3). 4. Compare signatures using the Earth Mover's Distance (EMD) [START_REF] Rubner | A Metric for Distributions with Applications to Image Databases[END_REF][START_REF] Rubner | Texture-Based Image Retrieval Without Segmentation[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 ¢¡ ¤£ ¦¥ ¨ § th entry is the distance between the signatures of the ¡ th and ¥ th image in the database. The EMD matrix can be used for retrieval and classification, as described in Section 3.1.

In Section 3, we evaluate the proposed texture representation on two data sets. The first set consists of photographs of textured surfaces taken from different viewpoints and featuring significant scale changes, perspective distortions, and non-rigid transformations. The second set is the Brodatz database, which has 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 framework to use neighborhood shape as an additional discriminative feature.

Building the Representation

Affine-Invariant Regions

Blostein and Ahuja [START_REF] Blostein | A Multiscale Region Detector[END_REF] have first introduced a multiscale blob detector based on maxima of the Laplacian of Gaussian. 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 maximum of a normalized Laplacian measure in scale space. 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 the characteristic scale. Lindeberg and Gårding [START_REF] Lindeberg | Shape-Adapted Smoothing in Estimation of 3-D Depth Cues from Affine Distortions of Local 2-D Brightness Structure[END_REF] have also shown how to design an affine-invariant blob detector using an affine adaptation process based on the second moment matrix. Mikolajczyk and Schmid [START_REF] Mikolajczyk | Indexing Based on Scale Invariant Interest Points[END_REF][START_REF] Mikolajczyk | An Affine Invariant Interest Point Detector[END_REF] have proposed alternative scale-and affine-invariant detectors that use a multi-scale version of the Harris interest point detector to localize interest points in space while employing Lindeberg's scheme for scale selection and affine adaptation.

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" 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 paper is designed to support multiple "channels" based on the regions found by different detectors. The four steps listed in Section 1 can be carried out separately for each available channel; at the final stage, the channels are combined as described in Section 2.3.

Our prototype implementation uses two channels: one based on the Harris-Affine detector of Mikolajczyk and Schmid [START_REF] Mikolajczyk | An Affine Invariant Interest Point Detector[END_REF], and the other on the affine-adapted Laplacian blob detector after Lindeberg and Gårding [START_REF] Lindeberg | Shape-Adapted Smoothing in Estimation of 3-D Depth Cues from Affine Distortions of Local 2-D Brightness Structure[END_REF]. From now on, the respective detectors will be dubbed H and L. Figure 2 shows the output of L and H on two natural images. Intuitively, the two detectors provide complementary kinds of information about the image: H responds to corners and other regions of "high information content" [START_REF] Mikolajczyk | An Affine Invariant Interest Point Detector[END_REF], while L responds to blob-like regions of relatively uniform intensity. Note that L tends to produce a denser set of regions than H, though the absolute number of regions extracted from an image is small in any case (for the experiments of Section 3, this number is thresholded at 800 for each detector).

The regions localized by the H and L detectors can be thought of as ellipses defined by

¡ £¢ ¤ ¦¥ § ¨ § © £¢ ¤ ¥ §
, where ¥ is the center of the ellipse, and © is a sym- metric local shape matrix (see [START_REF] Lindeberg | Shape-Adapted Smoothing in Estimation of 3-D Depth Cues from Affine Distortions of Local 2-D Brightness Structure[END_REF][START_REF] Mikolajczyk | An Affine Invariant Interest Point Detector[END_REF] for details). We can perform affine normalization on the patch defined by © by applying to it any transformation that would map the ellipse onto a unit circle. It can be shown that if two image patches are initially related by an affine transformation, then the respective normalized patches are related by an arbitrary orthogonal transformation [START_REF] Lindeberg | Shape-Adapted Smoothing in Estimation of 3-D Depth Cues from Affine Distortions of Local 2-D Brightness Structure[END_REF][START_REF] Mikolajczyk | An Affine Invariant Interest Point Detector[END_REF]. To eliminate this remaining one-parameter ambiguity, we can represent each normalized patch by a rotationally invariant descriptor.

Spin Images as Intensity Descriptors

In this paper, we describe a novel intensity-based rotationinvariant descriptor inspired by the idea of 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. An intensity domain spin image is a two-dimensional histogram encoding the distribution of brightness values in an affine-normalized patch. The two dimensions of the histogram are ! , the distance from the center or the origin of the normalized coordinate system of the patch, and ¡ , the intensity value. The "slice" of the spin image corresponding to a fixed ! is simply the histogram of the intensity values of pixels located at a distance ! from the center. Since the ! and ¡ parameters are invariant to orthogonal transformations, spin images offer exactly the right degree of invariance for representing affine-normalized patches. To achieve invariance to affine transformations of the intensity (transformations of the form " # $ &% '" )( 10), it is sufficient to normalize the range of the intensity function within the support region of the spin image. We implement the spin image as a "soft histogram" where each pixel within the support region contributes to more than one bin. Namely, the contribution of a pixel having distance ! from the center and intensity value

¡ to the bin indexed by ! ¥ £ ¡ ¥ § is propor- tional to 2 43 '5 76 ¢ ! ¢ ! ¥ § ¨8 @9 BA 8 § C¢ ¢¡ B¢ ¡ ¥ § ¨8 D9 FE 8 § HG
, where A and E are "soft width" parameters. In our implementation, the distance between two spin images is given by the sum of squared differences (SSD), with the spin images normal- ized to have zero mean and unit Frobenius norm. Figure 3 illustrates the construction of spin images, and Figure 4 shows several examples. We have compared the effectiveness of spin images to descriptors based on outputs of rotation-invariant "Gaborlike" linear filters [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]. In a recent evaluation [START_REF] Varma | Classifying Images of Materials: Achieving Viewpoint and Illumination Independence[END_REF], Gabor-like filters had performance levels similar to those of several alternative filter banks. Therefore, they can be seen as fair representatives of currently used filter-based descriptors. Figures 6 (a) and (b) show the performance of spin images and Gabor-like filters on the data set described in Section 3.2. The fact that spin images perform better on our data makes intuitive sense: as a two-dimensional descriptor, the spin image is a richer representation of local appearance than a one-dimensional array of filter outputs.

Clustering and Signatures

Our method performs clustering to discover a small set of basic primitives in the set of descriptors (spin images) extracted from any single image. We use a standard agglomerative clustering algorithm [START_REF] Kaufman | Finding Groups in Data: An Introduction to Cluster Analysis[END_REF] that successively merges clusters until either the desired target number of clusters is reached (10 to 15 in the implementation), or the distance between clusters exceeds a pre-specified threshold. Agglomerative clustering takes as input not the descriptors themselves, but only a matrix of pairwise distances between descriptors. Thus, the running time of clustering is effectively independent of the dimensionality of the feature space (we use spin images of size ¡ ¢ , so technically we are work- ing with £ ¤ ¡ -dimensional features).

After the clustering stage is completed, we form the final representation for the image: a signature ¥ §¦ ©¨£ ¨ § , where ¦ ¨i s the medoid (the most centrally located element of the where the ' 3" are flow values determined by solving a linear programming problem (see [START_REF] Rubner | A Metric for Distributions with Applications to Image Databases[END_REF] for details), and the 0 ¦ ¨£ ! " § are ground distances between medoids. In our case, ¦ ¨and ! " are spin images and the distance is SSD. For our application, the signature/EMD framework offers several important advantages. A signature is more descriptive than a histogram, and it does not require global clustering of the descriptors found in all images. EMD can match signatures of different sizes, and is not very sensitive to the number of clusters -that is, if one cluster is split into several, the magnitude of the EMD is not greatly affected [START_REF] Rubner | Texture-Based Image Retrieval Without Segmentation[END_REF]. This is an important property, since automatic selection of the number of clusters is generally difficult.

Recall that our texture representation involves multiple channels corresponding to different detectors. Each channel generates its own signature representation for each image in the database, and therefore its own EMD value for any pair of images. We have experimented with several methods of combining these separate values to obtain a cumulative inter-image distance measure. It was empirically determined that simply adding the separate distances with equal weights produces the best results.

Performance Analysis

Methodology

We have exercised the proposed texture representation in retrieval and classification tasks. For retrieval, we follow the procedure standardized in several previous studies [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 images from the database in increasing order of EMD. Each image in the database is used once as a query image. The performance is summarized in a plot of average recognition rate (number of images from the class retrieved so far over the total number of images in the class) vs. the number of closest images retrieved. Perfect performance would correspond to ¡ ¤4

recognition rate after 5 ¢ retrievals, where 5 is the number of images of the given class in the database.

In the above retrieval framework, we effectively treat each image as a model for its class, hoping that the rest of the images from the class will be very similar to this model. However, this reasoning does not work for databases with significant intra-class variability, where a given texture cannot be adequately modeled by any individual sample. To avoid this problem, we suggest classification as an addi- tional method for performance evaluation. In the classification framework, a model for a class is created not from a single (possibly atypical) image, but from several training images. As long as the training set adequately reflects the range of variation within the class, classification rate is not unduly affected by inhomogeneity.

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 are added to the test set. To eliminate the dependence of classification rates on the particular training images used, this procedure is repeated with different random training sets (we use 50 iterations).

Viewpoint-Invariant Texture Recognition

We have acquired a data set consisting of 20 samples each of ten different textured surfaces, for a total of 200 images (Figure 5). Significant viewpoint and scale changes are featured within each class. To push the limits of our system, we have allowed additional sources of variability: inhomogeneities in the texture pattern, non-rigid transformations, illumination changes, and unmodeled viewpoint-dependent appearance changes (these are the most severe for class T4, whose "textured" look is due largely to the pattern of light and shadow on a bumpy surface).

Figure 6 (a) shows retrieval results using spin images as intensity-based descriptors. Notice that for this data set, the H channel is more discriminative than the L channel. Nevertheless, adding the two EMD estimates results in improved performance. This "hyperacuity effect" is the strongest argument for combining the output of different feature extractors. Figure 6 (b) shows the results using Gabor-like filters as descriptors instead of spin images (see Section 2.2 for discussion). Figure 6 (c) summarizes the classification results obtained by using 5 samples from each class as training images. The classification rate for each class provides an indication of the "difficulty" of this class for our representation. The mean rate is ¡ ¢ ¤£ , with two classes achieving , showing the robustness of our system against a large amount of intra-class variability. In particular, performance is very good for relatively inhomogeneous textures T5 and T6. Class T4 has the lowest recognition rate, which is probably due to excessive variability in local appearance caused by the complex interaction between viewpoint, lighting, and fine-scale 3D structure. Indeed, about half of the signatures for this class are dominated by (roughly speaking) light center/dark surround blobs, while the remaining signatures are dominated by dark center/light surround blobs. The EMD between these two types of signatures is quite high, explaining the relatively low recognition rate.

Brodatz Database Evaluation

In the experiments shown in the previous section, we discard the information contained in the shape of the patches computed using affine adaptation (recall Section 2.1). However, shape can be a distinctive feature when affine invariance is not required. In this section, we present a modification of our system that takes advantage of affine shape for recognition, and evaluate it on the Brodatz database.

Let ¥ §¦ and ¥ 8 be two regions defined by local shape matrices © ¦ and © 8 . We eliminate the translation between ¥ ¨¦ and ¥ 8 by aligning their centers, and then com- pute the dissimilarity between the regions as

0 ¥ ©¦ £ ¥ 8 § C¢ § 2 ¥ ¨¦ ¥ 8 § 9 2 ¥ §¦ ! "¥ 8 §
. Notice that this measure takes into account the relative rotations of the two ellipses. We can achieve rotation invariance simply by aligning the major and minor axes of the ellipses before comparing their areas. In the experiments of this section, we use local shape to obtain one additional channel for each region detector. This involves a separate clustering stage for each set of regions based on the "ellipse distance"

0 ¥ ¦ £ ¥ 8 §
, as well as the computation of shape-based signatures and EMD's between all pairs of images. At the end, the shape-based EMD matrices are combined with the spin image-based EMD matrices through addition.

The Brodatz database is a widely used benchmark for texture recognition. 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 the classes by partitioning each of the 111 images into nine non-overlapping fragments, for a total of 999 images. As many authors have noted before, the wide variety of Brodatz textures, combined with a certain degree of subjectivity in assigned texture classes (some perceptually similar textures have different labels, while a few textures are too inhomogeneous to permit successful recognition) makes the Brodatz database a challenging platform for performance analysis. Parts (d) and (e) of Figure 6 show retrieval results using the shape channel alone, the spin image channel alone, and the two channels combined. By comparing the two plots, we can see that H and L spin image channels produce very similar results, but the shape information for H is much less descriptive than for L. As a result, the combined L channel outperforms the combined H channel, which is the reverse of the situation seen in Section 3.2. The final performance of the system, shown as the solid curve in Figures 6 (d) and (e), is obtained by combining the shape and spin image channels from both detectors.

Figure 6 (f) gives us a more detailed means of performance analysis. It shows a histogram of classification rates for all 111 classes obtained by putting three images from each class into the training set. The histogram reveals that the majority of textures are highly distinguishable, with only a few stragglers at the low end. In fact, 41 classes have classification rate, and the mean rate is ¢ ¢¡ . Three of these classes are shown in the top part of Figure 7, with the three bottom textures below. Not surprisingly, the bottom three textures are highly inhomogeneous. While the tests of Section 3.2 show that our method provides some robustness against inhomogeneity, textures with large amounts of spatial variation remain difficult to recognize.

The best performance curve of our system has about ¡ ¤£ ¡ recognition rate after 8 retrievals. This result is on par with Picard et al. [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 somewhat below Xu et al. [START_REF] Xu | Performance Analysis in Content-based Retrieval with Textures[END_REF], who report ¢ £ recognition rate using the multiresolution simul- taneous autoregressive (MRSAR) model [START_REF] Mao | Texture Classification and Segmentation Using Multiresolution Simultaneous Autoregressive Models[END_REF]. MRSAR is completely different from our method: it models texture as a stationary random field, uses a dense representation with fixed neighborhood shape and size, and has no scale, rotation, or affine-invariance. Traditional texture models such as MRSAR have been studied and perfected for at least a decade, while our method is built on new techniques that have not previously been applied to texture analysis. We believe that "mature" methods such as MRSAR have been pushed close to the intrinsic limit of their performance, while novel methods such as ours have a much greater potential for improvement in the future.

Discussion and Future Work

In this paper, we have introduced a non-parametric texture representation that provides several kinds of geometric invariance, does not make any statistical assumptions about the input texture, and applies spatial and shape selection to automatically determine the locations and support regions of salient texture neighborhoods.

In the future, we will pursue several avenues for improvement of our method. One important research direction is acquiring a better understanding of the relative expressiveness of the H and L detectors. In our experiments, H worked better for the data set of Section 3.2, while L gave better performance on the Brodatz database. We plan to conduct a more systematic study of the on larger databases, and to develop a quantitative measure of the discriminative power of different detectors on different types of texture. This study should also involve more detectors, e.g., the ones proposed by Tuytelaars and Van Gool [START_REF] Tuytelaars | Matching Widely Separated Views based on Affinely Invariant Neighbourhoods[END_REF].

Another issue worthy of further research is the method for combining channels. For our two data sets, the simple method of adding the individual EMD matrices has worked surprisingly well to improve average performance. However, as can be seen from Figure 6 (b), it is occasionally possible for the combined recognition rate to be lower than the single-channel rates. In the future, we plan to study more sophisticated methods for combining channels that would not suffer from similar detrimental effects.

Finally, we believe that a significant increase in discriminative power will come from using features based on spatial relationships between neighoring 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 significant 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.

Figure 1 :

 1 Figure 1: Outline of the proposed method.

Figure 2 :

 2 Figure 2: Left: original images, center: output of the H detector, right: output of the L detector.

Figure 3 :

 3 Figure 3: Spin image construction: three sample points in the normalized patch (left) map to three different locations in the spin image (right).

Figure 4 :

 4 Figure 4: Normalized patches (top) and spin images (bottom).

¡

  th cluster) and ¨is the weight (the size of the cluster divided by the total number of descriptors in the image). Signatures have been introduced by Rubner et al.[START_REF] Rubner | A Metric for Distributions with Applications to Image Databases[END_REF][START_REF] Rubner | Texture-Based Image Retrieval Without Segmentation[END_REF] as representations suitable for matching using the Earth Mover's Distance (EMD). The EMD between two signatures ¥ ¦ ¨£ ¨ § and ¥ ! #" £ $ %" § has the form & ¨& " (' )" 10 §¦ ¨£ 2! " § & ¨& " #' 3"

Figure 5 :

 5 Figure 5: Samples of the ten texture classes used in the experiments of Section 3.2.

Figure 6 :

 6 Figure 6: (a), (b), (c) Retrieval and classification performance for the data set shown in Figure 5. (d), (e) Retrieval using the Brodatz database. The solid black curve is the same in both plots. This curve represents the best performance of our system (see text). (f) Histogram of classification rates for all 111 classes.

D15(Figure 7 :

 7 Figure 7: Top: three of the 41 textures having classification rate of ¤¡ £ . Interestingly, the representation for D48 has an average of only 9 L and 5 H regions per sample. Bottom: three textures with the worst classification rates (shown in parentheses).

Acknowledgments. This research was partially supported by the UIUC Campus Research Board, by the National Science Foundation under grant IRI-990709, and by the European project LAVA (IST-2001-34405).


Svetlana Lazebnik
email: slazebni@uiuc.edu

Amit Sethi
email: asethi@uiuc.edu

Cordelia Schmid
email: cordelia.schmid@inrialpes.fr

David Kriegman
email: kriegman@uiuc.edu

Jean Ponce
email: j-ponce@uiuc.edu

Martial Hebert
email: hebert@ri.cmu.edu

On Pencils of Tangent Planes and the Recognition of Smooth 3D Shapes from Silhouettes

This paper presents a geometric approach to recognizing smooth objects from their outlines. We define a signature function that associates feature vectors with objects and baselines connecting pairs of possible viewpoints. Feature vectors, which can be projective, affine, or Euclidean, are computed using the planes that pass through a fixed baseline and are also tangent to the object's surface. In the proposed framework, matching a test outline to a set of training outlines is equivalent to finding intersections in feature space between the images of the training and the test signature functions. The paper presents experimental results for the case of internally calibrated perspective cameras, where the feature vectors are angles between epipolar tangent planes.

Introduction

Many recognition systems represent objects using features derived directly from image intensity patterns. These systems work well on textured animals [START_REF] Schmid | Constructing models for content-based image retrieval[END_REF] or objects with distinctive markings, like faces and cars [START_REF] Schneiderman | A Statistical Method of 3D Object Detection Applied to Faces and Cars[END_REF][START_REF] Weber | Towards Automatic Discovery of Object Categories[END_REF]. However, they are limited in their ability to distinguish between objects based on true 3D shape. They may fail, for instance, to tell the difference between a tiger and a tiger-skin rug. Another difficulty is that some classes of objects do not have intensity or color descriptors with sufficient discriminative power: in the absence of surface texture or markings, the silhouette becomes the main clue to the object's identity.

A common approach to silhouette-based matching consists of finding rich local descriptors for a set of contour points. This process may involve computing orientation information associated with pairs and triples of points [START_REF] Carlsson | Order Structure, Correspondence, and Shape Based Categories[END_REF] or attaching two-dimensional "shape context" histograms to each point [START_REF] Belongie | Shape Matching and Object Recognition Using Shape Contexts[END_REF]. An important advantage of these methods is that they do not require complete segmentation, working instead with a scattered set of edge points. However, most known contour descriptors are mainly suitable for 2D recognition -from a geometric point of view, it is hard to justify the appropriateness of arbitrary outline statistics for matching multiple views of the same 3D object.

In this paper, we present a true geometric approach to recognizing smooth 3D objects. We follow the general philosophy of deriving a rich silhouette description to build a highly descriptive feature space, while taking care to define features that have a rigorous 3D interpretation. In our framework, a potential match between two outlines is a hypothesis of a consistent epipolar geometry between the two respective viewpoints. Previous work on geometric silhouette matching has been limited, considering only weak perspective or restricting the set of allowable camera movements [START_REF] Basri | The Alignment of Objects with Smooth Surfaces[END_REF][START_REF] Jacobs | Judging Whether Multiple Silhouettes Can Come from the Same Object[END_REF][START_REF] Renaudie | Duals, Invariants, and the Recognition of Smooth Objects from their Occluding Contour[END_REF]. The approach proposed in this paper is fully general, encompassing the cases of uncalibrated and internally calibrated perspective projection, as well as affine projection. Our method is not restricted to outlines taken from nearby viewpoints, and explicitly accounts for self-occlusion.

In the following section, we give a conceptual introduction to our recognition framework. In Sections 3 and 4, we discuss the properties of the feature space and the conditions for matching outlines. In Section 5, we address implementation issues and report results from a preliminary recognition experiment.

Recognition Framework

Assume that we are given a training set of outlines of a single object. We want to construct a representation suitable for recognizing instances of this object based on outlines in test images from viewpoints not present in the training set. The key idea is the following: for each image, we associate a set of invariants with each possible baseline connecting its viewpoint to any other viewpoint. The baseline between two camera centers determines the epipolar geometry of the scene: the epipoles are the intersections of the baseline with the image planes, and the epipolar lines are intersections of the image planes with the pencil of epipolar planes passing through the baseline (Figure 2). The epipolar geometry does not change when we translate the camera centers while keeping the baseline fixed. We take advantage of this invariance property by introducing a signature function S that assigns a vector from some feature space F to each possible baseline. The feature vectors (to be defined precisely in Section 3.3) can be computed in the image given an outline and a hypothesized epipole, but they measure properties of the 3D object in space.

Let Γ denote the collection of the outlines in the training images (a discrete set of pictures or a video clip). Any point e on the projective image plane of some γ in Γ is a potential epipole, and is identified with a unique line (the line passing through the camera center and piercing the image plane at the epipole location). Thus, sampling all possible epipoles is equivalent to sampling the twodimensional set of all baselines passing through the camera center. Indeed, the space of all lines through the origin in 3-space is topologically equivalent to P 2 , the projective plane. The signature function S encapsulates the relationship between outlines and epipoles/viewing rays as follows:

S : Γ × P 2 → F (γ, e) → f .
Since the feature space F contains information about the 3D properties of the scene, it is actually possible to express S as a function of an object and a line in space. However, the definition above emphasizes the 2D information that is directly accessible to the recognition algorithm, namely, an outline and a point on the image plane.

Let γ and γ ′ denote a training and a test outline of the same object (keep in mind that the relative camera positions are unknown). Consider the baseline connecting the camera centers of γ and γ ′ . This baseline yields a pair of epipoles: e in the image plane of γ, and e ′ in the image plane of γ ′ . Since the training and the test images capture the same object and the two epipoles refer to the same line in space, we must have S(γ, e) = S(γ ′ , e ′ ) . Now, suppose that this equality holds for some particular γ, γ ′ , e, and e ′ . Then the two epipole positions define a baseline for which the two pictured outlines are consistent with a single object. If the feature space F is sufficiently highdimensional, then a match of signature functions is a strong indication that two outlines belong to a single object. Here is an alternative way to think about matching: the images of the whole signature functions for γ and γ ′ , denoted Σ = S({γ} × P 2 ) and Σ ′ = S({γ ′ } × P 2 ), form signature surfaces in the feature space F . If γ and γ ′ come from the same object, then the intersection Σ ∩ Σ ′ yields the consistency hypothesis between the training and test outlines, and its preimage yields the unique baseline joining the camera centers of the training and test images (Figure 1). Thus, a hypothesis of a possible match for recognition is equivalent to a hypothesis of the epipolar geometry of camera pairs in the scene.

So far, we have only discussed matching between a pair of outlines. In principle, since any two views of the same object can be connected by a baseline, it is always possible to match a novel view of an object given a single training image. In practice, however, a single view of an object may be ambiguous, and widely separated pairs of views may fail to produce descriptive features. For these reasons, we should collect training sequences consisting of a few representative views of each object. A recognition algorithm that works with multiple training outlines and a single test outline will have the following conceptual structure:

Σ ′ ∩ Σ ij . If γ ′ is a view of object i, then each Σ ′ ∩ Σ ij should
consist of a unique feature vector. Otherwise, each Σ ′ ∩ Σ ij should be empty.

Feature Space

Consider the set of all lines passing through the epipole that are also tangent to the contour. These lines back-project to planes passing through the baseline that are tangent to the object at isolated frontier points (Figure 2). The points of epipolar tangency on the image contour are projections of these frontier points, and it is well known that they are the only true stereo matches between a pair of view-dependent contours [START_REF] Porrill | Curve Matching and Stereo Calibration[END_REF]. Even though a single image does not constrain the depth of frontier points in space, it is still possible to reconstruct the tangent epipolar planes by back-projecting the observed tangent epipolar lines. Notice that the epipolar planes are defined by the baseline and the geometry of the object -they do not depend on image plane orientations or on the exact positions of the camera centers along the baseline. Thus, we can derive feature vectors for baselines by computing the tangent epipolar planes associated with them. The kinds of features we can use -projective, affine, or Euclidean -depend on the imaging model we wish to adopt. In the following subsections, we briefly review these three models in turn. Along the way, refer to Figure 3 for an example of each kind of feature vectors. These planes intersect the image plane in epipolar tangents l1, l2, l3, and l4. Note that the epipole e is hypothetical -it does not correspond to a second camera center.

Projective Cameras

When the internal camera parameters are unknown, a pinhole camera allows us to measure only the properties of the image that remain invariant under projective transformations. In particular, projective measurements are sufficient to define the epipolar geometry between pairs of cameras. For any two cameras along a fixed baseline, the pencil of epipolar lines tangent to the contour is the projection of the same pencil of planes through the baseline. The cross-ratio of four tangent epipolar planes through this baseline is the same as the cross-ratio of the corresponding epipolar lines observed by any camera along the baseline. Given four or more lines, we can compute all possible cross-ratios between each quadruple of lines and store these cross-ratios in a feature vector.

Affine Cameras

Affine cameras are cameras whose centers and focal planes are located on the plane at infinity in three-dimensional space [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. Affine projection preserves parallelism and maps points on the plane at infinity to points on the line at infinity. The notion of epipolar geometry still applies to the affine case: the baseline between two affine cameras is a line at infinity, and since all the epipolar planes intersect in this line, they are actually parallel to each other. In the image, epipolar lines are also parallel, and the epipoles can be thought of as direction vectors. An affine epipole has only one degree of freedom, instead of the two degrees of freedom in the perspective case, and this reduces the intrinsic dimension of the feature space [START_REF] Renaudie | Duals, Invariants, and the Recognition of Smooth Objects from their Occluding Contour[END_REF]. As for vectors of invariants in the feature space, they are naturally given by ratios of distances between parallel tangent epipolar planes. ). The angles are not between the lines themselves, but between the corresponding epipolar planes in space. Note that the different feature vectors have dimensions 1, 2, and 3, respectively.

Euclidean Cameras

Many reliable procedures exist for measuring the internal parameters of the camera (skew, magnification factors, and image center) [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. Internal calibration gives us a mapping from points in the image plane to lines through the camera center in three-dimensional Euclidean space, expressed in a canonical coordinate system attached to the camera. The projection matrix of the internally calibrated camera may be written as M = K[I | 0] where K is the 3 × 3 matrix of internal parameters. Then for each line l tangent to the contour and passing through a particular epipole position we obtain a plane

Π = M ⊤ l = K ⊤ l 0
in the canonical camera system. Given coordinate vectors of two tangent epipolar planes Π 1 = M ⊤ l 1 and Π 2 = M ⊤ l 2 , we may measure their angle as

cos θ = l ⊤ 1 (KK ⊤ )l 2 l ⊤ 1 (KK ⊤ )l 1 l ⊤ 2 (KK ⊤ )l 2 . ( 1
)
Given a contour γ and a fixed epipole position e, how do we define the corresponding value of the signature function? Consider the ordered set (l 1 , . . . , l n ) of lines that pass through e and are tangent to the contour (the ordering is circular about e, with l 1 serving as a specially chosen reference line). The planes formed by back-projecting the lines make up a corresponding ordered set, denoted (Π 1 , . . . , Π n ). Let θ i be the angle in space between Π 1 and Π i+1 , computed according to [START_REF] Basri | The Alignment of Objects with Smooth Surfaces[END_REF]. Finally, we are ready to define the value of the signature function as S(γ, e) = (θ 1 , . . . , θ n-1 ).

In stating the above definition, we have left a few things deliberately unspecified. For one, the order of the angles in the feature vector depends on the choice of the reference line and on the circular orientation convention (clockwise vs. counterclockwise). In addition, the number n of angles is not a global constant; it may vary for different contours and positions of the epipole. Because of self-occlusion, the number of tangent epipolar planes may actually vary for different camera positions along the same baseline. We will return to these issues in Sections 4.1 and 5.2.

Overall, angles have significant advantages over cross-ratios as primitives making up the feature space. We need fewer measurements to compute angles -only two epipolar tangents suffice, whereas we need at least four to get a cross-ratio. As a result, the "calibrated" feature space has higher dimension than the "uncalibrated" one, which improves the ability to discriminate between different objects at recognition time. For the rest of the paper, we will focus on the calibrated case.

Properties of the Signature Function

In the following sections, we briefly describe the smoothness and continuity properties of the signature function, and present informal arguments about the existence and uniqueness of matches in feature space.

Critical Events

For the rest of this section, let us regard the contour γ as being fixed, so that the signature function depends only on the epipole position e. For a given e, the number of angles in the feature vector (θ 1 , . . . , θ n-1 ) is one less than the number of epipolar tangents (l 1 , . . . , l n ), and n is also a function of e. For generic epipole positions, a contour will have an even number of epipolar tangents, so the corresponding feature vector will have odd dimension. This dimension will remain constant if we perturb the epipole a little, unless the epipole lies on a critical event boundary: the contour itself, an inflectional tangent, or a bitangent to the contour. Crossing an inflectional tangent or the contour itself will make a pair of lines appear or disappear (increasing or decreasing the dimension of F by two), while crossing a bitangent will reverse the order of a pair of lines (giving no net change in dimension). Away from critical boundaries, however, the values of the angles (θ 1 , . . . , θ n-1 ) vary smoothly as a function of the epipole position. Thus, even though the signature surface Σ ⊂ F may have a very complicated global structure, with different subsets immersed in spaces of a different dimension, its local structure is quite simple. If e is a generic epipole position giving rise to n epipolar tangents, then inside a sufficiently small neighborhood of e, S is an immersion of R 2 into R n-1 .

Matching and the Intersection of Signature Surfaces

Let us take two contours γ and γ ′ and consider the intersection Σ ′′ of their signature surfaces, Σ = S({γ} × P 2 ) and Σ ′ = S({γ ′ } × P 2 ). Take some f ∈ Σ ′′ where F is locally m-dimensional (that is, f ∈ R m ). Then there exist e, e ′ ∈ P 2 such that f = S(γ, e) = S(γ ′ , e ′ ). Moreover, we can find neighborhoods U and U ′ of e and e ′ , respectively, where F = S({γ} × U ) and F ′ = S({γ ′ } × U ′ ) are two-dimensional surfaces in R m . If we expect F and F ′ to intersect transversally, then additivity of codimension [START_REF] Guillemin | Differential Topology[END_REF] yields the following:

m -dim(F ∩ F ′ ) = m -dim F + m -dim F ′ = 2m -4 dim(F ∩ F ′ ) = 4 -m .
Thus, for m > 4, any transversal intersection of two signature surfaces would have to be empty (note that since m can only be odd, we need not be concerned with the case m = 4). In other words, if we take two arbitrary contours γ and γ ′ and a random feature vector f consisting of five or more angle values, we will not find e and e ′ such that S(γ, e) = S(γ ′ , e ′ ).

Observation 1. If the feature space has sufficiently high dimension, the possibility of "accidental" matches is in principle ruled out.

But what if γ and γ ′ are outlines of the same object seen from two different viewpoints? Then the baseline connecting these viewpoints gives two true epipole positions e and e ′ . Clearly, there exists a unique set of planes that are tangent to the object and pass through this baseline. If we assume the object is transparent, then we will be able to observe exactly the same planes for γ and γ ′ by looking at the respective epipolar tangents. In this case, we must have S(γ, e) = S(γ ′ , e ′ ).

Observation 2. For transparent objects, signatures will always match at true epipole positions for two different views of the same object.

Combined, the two observations above suggest that a match between signature functions for two epipoles in two images indeed offers strong evidence of consistency between two outlines. As long as the dimension of the feature space is high enough, our ability to discriminate approaches the idealization of Section 2. Nevertheless, we cannot claim that a signature match exists if and only if γ and γ ′ are two views of the same object, and e and e ′ are the projections of the camera centers that produced γ ′ and γ, respectively. Various non-generic properties of the contours, such as symmetries, may conspire to produce multiple signature matches. A far more important problem, however, is self-occlusion -as noted in Section 3.3, two camera positions along the same baseline may fail to see the same epipolar tangents, when some of them become obscured by parts of the surface. In the next sections, we discuss the implementation of our approach, and show how to deal with occlusion.

Implementation

Sampling of Epipoles

We represent signature functions for a small number of input pictures by sampling the two-dimensional space of possible epipoles. We find a set of uniformly distributed viewing directions by recursively tessellating a unit sphere, and then project these directions onto the image plane (directions lying on the focal plane project to epipoles at infinity). Figure 4 (a) shows a tessellation of the sphere projected onto the image plane. After choosing a sampling pattern of a given density, we find all epipolar tangents and compute the signature functions for each sample point. During a pre-processing step, contours are segmented using thresholding followed by Gaussian smoothing [START_REF] Renaudie | Duals, Invariants, and the Recognition of Smooth Objects from their Occluding Contour[END_REF]. To facilitate the computation of epipolar tangents, the contours are represented as cubic B-splines. Recall from Section 4.1 that for different epipole positions, the number of epipolar tangents and the dimension of feature vectors vary as certain critical boundaries are crossed. Patterns of sample points with feature vectors of different dimension shown in Figures 4 (b) and (c) reveal these boundaries. To visualize the computed signature functions, refer to Figure 5: part (a) shows a plot of the largest angle in the feature vector as a function of the epipole, and part (b) shows some patches of a 15-dimensional signature surface projected into three dimensions.

(a) (b) (c)

Ordering of Feature Vectors

Let us return to the definition of a feature vector given in Section 3.3. At that stage, we have not committed to a choice of a reference plane Π 1 or to the orientation of the circular ordering of planes around the baseline. However, for best recognition results, the choice of Π 1 should not be arbitrary. Whenever the baseline passes outside the convex hull of the object, we can identify two extremal planes that make contact with the object only at the respective frontier points. These planes are robust to self-occlusion in opaque objects -they will necessarily be observed between any two views on the same baseline. By contrast, frontier points due to non-extremal planes can become occluded (in addition, segmentation algorithms usually miss parts of the contour that are visible, but fall inside the silhouette). For these reasons, our implementation arbitrarily selects one of the two extremal planes as the reference, and computes the angles (θ 1 , . . . , θ n-1 ) with respect to this reference plane. While matching feature vectors from two images, it is impossible to determine whether the two reference planes correspond to each other in space, or whether the reference plane in one image corresponds to the second extremal plane in the other image. For each of the two possible orderings, we compute a matching cost as described in the next section, and select the smaller cost as the "winner". When the baseline enters the convex hull of the object, there are no extremal planes. In this case, matching becomes more combinatorially complex, and more difficult to implement. However, since only a small fraction of all sample epipoles fails to produce extremal planes, excluding these points from matching has a negligible effect on performance.

Matching Feature Vectors

In the idealized recognition framework of Section 2, matching reduces to finding intersections of signature surfaces. Unfortunately, this formulation is difficult to implement directly. Since we are using a sampled representation of signature surfaces, we cannot locate exact matches by simply comparing discrete feature vectors. Also, Observation 2 of Section 4.2 is not true for opaque objects. Selfocclusion can make some tangent planes invisible from a particular camera position along the baseline, and introduce T-junctions that show up as false frontier points on the silhouette. Because of these effects, a successful matching algorithm must be able to compare feature vectors with different numbers of components and find subsequences of these vectors that minimize some matching cost. To this end, we have implemented a dynamic programming algorithm that, given two feature vectors of length m and n, f = (θ 1 , . . . , θ m ) and f ′ = (θ ′ 1 , . . . , θ ′ n ), finds two subsequences of length k, f = (θ i1 , . . . , θ i k ) and f ′ = (θ ′ j1 , . . . , θ ′ j k ) that minimize the average distance function

D( f , f ′ ) = 1 k k l=1 |θ i l -θ ′ j l | . (2)
The subsequence length k can either be given to the matching algorithm as a parameter, or used as another optimization variable. The dynamic programming formulation is relatively efficient, and it is the natural way to enforce ordering constraints -e.g., the extremal angles always have to match, and the indices in the two subsequences must increase monotonically.

Matching Signature Surfaces

Once the matching score for a pair of feature vectors has been defined, we can proceed to match pairs of signature surfaces. In Section 4.2, we established that, provided the dimension of the feature space is sufficiently high, we can expect a unique match between two signature surfaces Σ = S({γ} × P 2 ) and Σ ′ = S({γ ′ } × P 2 ). Thus, in the implementation, it is sufficient to look for a single pair of "closest" feature vectors. The signature matching cost is then simply

C(Σ, Σ ′ ) = min f ∈Σ,f ′ ∈Σ ′ D(f, f ′ ) .
In practice, because of measurement noise and discretization error due to sampling, C will not vanish even if Σ and Σ ′ intersect. When comparing a test signature surface Σ ′ to training surfaces Σ 1 , . . . , Σ m , we can assign matches based on minimum cost:

Match(Σ ′ ) = arg min Σi C(Σ i , Σ ′ ) . (3)
Let f = S(γ, e) and f ′ = S(γ ′ , e ′ ) be two feature vectors giving the lowest-cost match. The two points e and e ′ represent a hypothesis of the epipolar geometry between the views that produced outlines γ and γ ′ . When full calibration is available, comparing the locations of these points to the true epipole positions allows us to verify the matching procedure. To conduct the verification, we experimented with a synthetic rhino data set (Figure 4 shows one of the rhino images). First, we computed matching costs for the signature of the true epipole in one view and the signatures of all sample points in a second view. Figure 6 shows the resulting plots for two different sampling resolutions. Well-defined local minima exist in the vicinity of the true epipoles, although the discrepancies between the minima and the true matches vary with the quality of the sampling. Next, we computed cost functions for all pairs of sample points whose viewing directions fall within 10 • of the true epipoles. The results are summarized in Table 1. Our experiments show that the minimum cost over all pairs of sampled feature vectors may be an order of magnitude larger than the cost for the true match (of course, the actual numerical values are an artifact of our definition of the cost function). However, as sampling density increases, the minimum cost computed over all pairs of sample points approaches the global minimum (compare rows 1 and 2 of the table). By examining row 3, we can also see that denser sampling improves the accuracy of hypothesized epipoles. Interestingly, though, the minimum cost match is not found at sample points that are closest to the true epipole directions. Overall, our results confirm that it is in principle possible to find reliable epipole estimates through matching signature surfaces -empirically, the cost of the true match always appears to be the global minimum. However, the actual quality of local minima found by our algorithm is dependent on the density of the sampling. The third row shows the angle differences between true epipoles and minimum-cost sample points in views 1 and 2, respectively.

Recognition

In this section, we present a matching experiment on a real data set containing two views each of three objects: a toy dinosaur, a gargoyle statuette, and a cowboy (see Figure 7). The data set shows a substantial amount of self-occlusion: notice, for instance, the tail and the forelegs of the dinosaur, and the left ear and wing of the gargoyle. For each input picture, signature surfaces were computed at 4 • resolution. As Table 1 indicates, the local minima of the cost function computed at this sampling density are not very reliable. To diffuse the sampling artifacts and to pool evidence from multiple locations in the cost landscape, we modified the matching criterion of Equation 3 to take the average of a fixed number of the lowest-cost feature matches. Specifically, to classify each outline, we computed the mean of the lowest 50 matching costs of its signature surface with the signature surfaces of every other outline, and picked the smallest-cost outline as the winner. Figure 8 presents the complete matching statistics. Note that each outline is correctly assigned to the other outline from the same object. Our recognition experiment allows us to draw several conclusions. First of all, dense sampling does not appear to be necessary for successful matching. Even though the lowest-cost matches may be far away from the true epipoles, the relative magnitudes of the costs give a good indication of proximity between different signature surfaces. Secondly, reliability of matching depends on the complexity of the contours. For instance, the toy outlines are the most complex, giving rise to the highest-dimensional signature surfaces. Feature vectors from these surfaces offer a large number of possible combinations for matching, raising the likelihood that a spurious low-cost match will be found.

Discussion and Conclusions

The preliminary implementation of Section 5 confirms the validity of our recognition framework, but it cannot serve as a prototype for a working real-world system. To make our method truly practical, we need to address several issues.

-Segmentation: since contour extraction is not the focus of the current paper, we assume that all input images can be segmented using naive techniques like thresholding. This restrictive assumption is not unique to our approach, but is common to most silhouette-based recognition or reconstruction schemes. Overall, the development of robust and general segmentation algorithms remains a significant challenge. -Occlusion and clutter: the feature matching algorithm of Section 5.3 only deals with measurement noise and self-occlusion. We are currently modifying our framework to account for occlusion of the target object by other objects, and for segmentation errors due to background clutter.

-Efficiency: our implementation involves sampling two-dimensional sets of epipoles, and matching between all pairs of feature vectors in two images. We need to optimize these computationally expensive tasks, or develop alternative signature function representations and matching procedures.

One interesting extension of our approach is to combine the discrete feature matching procedure with nonlinear optimization methods that solve for camera motion based on frontier points [START_REF] Cipolla | Motion from the Frontier of Curved Surfaces[END_REF]. The main problem with these methods is initialization -it is difficult to find an initial guess of epipole positions that would make the system converge to the right solution. We could start an opti-mization at the local minima produced by our matching algorithm, and use an iterative technique to improve the estimates of the epipoles.

Another important long-term direction is class-based object recognition. In this paper, we developed a representation framework that captures the geometric constraints between different views of a single object instance. A far more challenging question is, what geometric features derived from image data would allow us to classify pictures drawn from an object category? Developing algorithms that reason directly about 3D geometry, rather than about 2D image patterns, may be the key to building recognition systems that discriminate between classes of objects related by similarity of 3D shape.

Fig. 1 .

 1 Fig.1. Outlines γ and γ ′ are connected in space by the baseline through their respective camera centers, O and O ′ . This baseline intersects the image planes in epipoles e and e ′ . Computing signature functions S(γ, e) and S(γ ′ , e ′ ) yields a vector f in feature space F that lies on the intersection of the two signature surfaces Σ and Σ ′ .

1 .

 1 Training. (a) Feature Extraction. For each training object i, acquire a training set of outlines Γ i = {γ ij | j = 1, . . . , m i } and compute the signatures Σ ij = S({γ ij } × P 2 ). 2. Testing. (a) Feature Extraction. Acquire a test outline γ ′ and compute the signature function Σ ′ = S({γ ′ } × P 2 ). (b) Matching. For each training object i and outline j, compute the intersections

Fig. 2 .

 2 Fig. 2. (a) Epipolar geometry of frontier points. The epipolar plane Π is defined by camera centers O and O ′ , and the frontier point P.Π intersects the image planes in two lines l and l ′ that pass through the epipoles and are tangent to the respective contours at the projections p and q of the frontier point. (b) Planes Π1, Π2, Π3, and Π4 pass through the baseline and are tangent to the object at four frontier points. These planes intersect the image plane in epipolar tangents l1, l2, l3, and l4. Note that the epipole e is hypothetical -it does not correspond to a second camera center.

Fig. 3 .

 3 Fig. 3. An example of different kinds of feature vectors for an epipole with four tangents. (a) Projective (uncalibred cameras): f = (Cross(l1, l2, l3, l4)). (b) Affine: f = (Dist(l1, l2)/Dist(l1, l4), Dist(l1, l3)/Dist(l1, l4)). (c) Euclidean (calibrated cameras): f = (Angle(l1, l2), Angle(l1, l3), Angle(l1, l4)). The angles are not between the lines themselves, but between the corresponding epipolar planes in space. Note that the different feature vectors have dimensions 1, 2, and 3, respectively.

Fig. 4 .

 4 Fig. 4. (a) A synthetic image of a rhino with a projected 1313-vertex triangulation of the sphere overlayed. (b) Sample points from a 20609-vertex triangulation with 15dimensional feature vectors. (c) Sample points with 17-dimensional feature vectors.

Fig. 5 .

 5 Fig. 5. (a) Angle (in radians) between extremal planes as a function of epipole position (in pixel coordinates) for the rhino image shown in Figure 4. Note that the extremal angle approaches π as the epipole approaches the contour. (b) A three-dimensional immersion of a 15-dimensional subset of the signature surface for the rhino contour.

Fig. 6 .

 6 Fig. 6. Matching costs between true epipoles and sample points plotted on the sphere for directions within 10 • of the true match. Darker shading indicates lower cost. The local minimum of the sampled cost function is marked with a cross, and the true epipole location is marked with a diamond.

Fig. 7 .

 7 Fig. 7. Outlines of three objects used in the recognition experiment.

Fig. 8 .

 8 Fig. 8. Mean and standard deviation of matching costs for each test outline vs. all the other test outlines. The dashed horizontal lines indicate the lowest cost matches.

Table 1 .

 1 The effect of sampling density on local minima of the matching cost function.

		Sampling density 4 • Sampling density 2 • Sampling density 1 •
		(1313 points)	(5185 points)	(20509 points)
	Actual min. cost (×10 4 )	4.136	4.136	4.136
	Sampled min. cost (×10 4 )	20.078	12.147	4.803
	Angle discrepancy	7.34 • and 7.57 •	5.41 • and 4.99 •	3.91 • and 3.68 •

Acknowledgments. This work was supported in part by the Beckman Institute, the National Science Foundation under grants IRI-990709 and IIS 00-85980, and a UIUC-CNRS collaboration agreement. We would also like to thank Steve Sullivan for providing the data used in the experiment of Section 5.5.