Keywords: détection d'objets, appariement de formes, caractéristiques de contours

D'images au modèles de forme pour la détection d'objets

Résumé : Nous proposons une nouvelle approche pour la détection de catégories d'objets qui intègre les avantages des méthodes de mise en correspondance de formes. D'une part, comme les détecteurs d'objets, notre approche est capable d'apprendre les modèles de classe directement à partir des images et de localiser de nouvelles instances malgré des variations intra-classe, des changements d'échelle ou la présence d'un fond encombré. D'autre part, tout comme les méthodes de mise en correspondance de formes, elle ne fournit pas simplement une boite englobante, mais parvient à extraire les frontières des objets. Ceci est possible grâce à une nouvelle technique d'apprentissage capable de construire le modèle de forme d'une catégorie d'objets, étant donné des images contenant des instances de cette catégorie. Afin de localiser le modèle dans des images test, nous combinons un algorithme de vote dans un espace de Hough à un algorithme de mise en correspondance de points pour les formes non rigides. Les résultats expérimentaux montrent que les frontières des objets sont localisées avec précision sans utiliser d'images d'apprentissage segmentées, les boites englobants seules suffisent.

Introduction

In the last few years, the problem of learning object class models and localizing previously unseen instances in novel images has received a lot of attention. While many methods use local image patches as basic features [START_REF] Fergus | Object Class Recognition by Unsupervised Scaleinvariant Learning[END_REF][START_REF] Leibe | Scale-Invariant Object Categorization using a Scale-Adaptive Mean-Shift Search[END_REF][START_REF] Torralba | Sharing Features: efficient boosting procedures for multiclass object detection[END_REF][START_REF] Winn | The Layout Consistent Random Field for Recognizing and Segmenting Partially Occluded Objects[END_REF], recently several approaches based on contour features have been proposed [START_REF] Berg | Shape Matching and Object Recognition using Low Distortion Correspondence[END_REF][START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF][START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF][START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF][START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF][START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]. In spite of their potential, even these contour-based methods usually localize objects up to a bounding-box, rather than delineating object outlines. We believe the main reason lies in the nature of the proposed models, and in the difficulty of learning them from real images (as opposed to hand-segmented shapes [START_REF] Cootes | Active Shape Models: Their Training and Application[END_REF][START_REF] Elidan | Learning Object Shape: From Drawings to Images[END_REF][START_REF] Hill | A Method of Non-Rigid Correspondence for Automatic Landmark Identification[END_REF][START_REF] Sebastian | Recognition of shapes by editing their shock graphs[END_REF]). The models are typically composed of rather sparse collections of contour fragments with a loose layer of spatial organization on top [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF][START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF][START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]. A few authors even go to the extreme end of using individual edgels as modeling units [START_REF] Berg | Shape Matching and Object Recognition using Low Distortion Correspondence[END_REF][START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF]. In contrast, an explicit shape model formed by continuous connected curves completely covering the object outlines is more desirable, as it would naturally support boundary-level localization in test images.

In order to achieve this goal, in this paper we propose an approach which bridges the gap between shape matching and object detection. Classic non-rigid shape matchers [START_REF] Belongie | Shape Matching and Object Recognition using Shape Contexts[END_REF][START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF][START_REF] Sebastian | Recognition of shapes by editing their shock graphs[END_REF] produce point-to-point correspondences, but need segmented shapes as input models, and need to be initialized near the object in the test image. In contrast, we build a shape matcher with the input/output behavior of a modern object detector: it learns complete shape models from images, and automatically matches them to cluttered images, thereby localizing novel class instances up to their boundaries.

Our approach makes three contributions. First, we introduce a technique for learning the prototypical shape of an object class as well as a statistical model of intra-class deformations, given image windows containing training instances (figure 3a; no segmented shapes are needed). The challenge is to determine which contour points belong to the class boundaries, while discarding background and details specific to individual instances (e.g. mug labels). Note how these typically form the majority of points, yielding a poor signal-to-noise ratio. The task is further complicated by intra-class variability: the shape of the object boundary varies across instances.

Second, we localize the boundaries of novel class instances in test images by integrating a Hough-style voting scheme [START_REF] Leibe | Scale-Invariant Object Categorization using a Scale-Adaptive Mean-Shift Search[END_REF][START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] with a non-rigid shape matcher [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF]. This combination makes accurate, pointwise shape matching possible even in severely cluttered images, where the object boundaries cover only a small fraction of the contour points (figures [START_REF] Basri | Determining the Similarity of Deformable Shapes[END_REF][START_REF] Ferrari | Accurate Object Detection with Deformable Shape Models Learnt from Images[END_REF].

Third, we constrain the shape matcher [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF] to only search over transformations compatible with the learned, class-specific deformation model. This ensures output shapes similar to class members, improves accuracy, and helps avoiding local minima.

These contributions result in a powerful system, capable of detecting novel class instances and localizing their boundaries in cluttered images, while training from objects annotated only with bounding-boxes.

After reviewing related work and the local contour features used in the next two sections, we present our shape learning method in section 4, and the scheme for localizing objects in new test images in section 5. Section 6 reports extensive experiments. We evaluate the Figure 1: Example object detections returned by our approach (see also figure 13).

quality of the learned models and quantify localization performance at test time in terms of accuracy of the detected object boundaries. We also compare to previous works for object localization with training on real images [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] and hand-drawings [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF]. A preliminary version of this work was published at CVPR 2007 [START_REF] Ferrari | Accurate Object Detection with Deformable Shape Models Learnt from Images[END_REF].

Related works

A major challenge in computer vision is category-level object recognition, the ability of recognizing object instances different from those used to model a category. As pointed out by Hummel [START_REF] Hummel | Where view-based theories break down: The role of structure in shape perception and object recognition[END_REF], shape descriptors are particularly suited for achieving generalization: many categories are characterized by their shape rather than by color or texture. For this reason, many authors have used shape representations [START_REF] Basri | Determining the Similarity of Deformable Shapes[END_REF][START_REF] Belongie | Shape Matching and Object Recognition using Shape Contexts[END_REF][START_REF] Cootes | Active Shape Models: Their Training and Application[END_REF][START_REF] Felzenswalb | Representation and Detection of Deformable Shapes[END_REF][START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF][START_REF] Gdalyahu | Flexible Syntactic Matching of Curves and Its Application to Automatic Hierarchical Classification of Silhouettes[END_REF][START_REF] Gold | Graduated Assignment Algorithm for Graph Matching[END_REF][START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF][START_REF] Sebastian | Recognition of shapes by editing their shock graphs[END_REF].

In this section we briefly review some of the most important previous works relevant to this paper, i.e. on shape representation and matching, and their role in the modeling, recognition, and localization of object categories.

Structural descriptors Structural descriptors are one of the earliest representations of object shape. Objects are decomposed into rather complex volumetric parts, such as generalized cylinders [START_REF] Marr | Representation and Recognition of the Spatial Organization of Three-Dimensional Shapes[END_REF] or geons [START_REF] Biederman | Recognition-by-components: A theory of human image understanding[END_REF], and represented by their spatial relations. However, it is very difficult to generate structural descriptions from images. The resulting descriptions are highly sensitive to the way in which the image is segmented into parts, and the same image may give rise to very different descriptions [START_REF] Ullman | Aligning pictoral descriptions: An approach to object recognition[END_REF]. As a consequence, recent and successful shape based approaches describe objects by simpler, robust and stable features connected in a deformable configuration. These features are generic, such as edge points and lines, and easy to extract, but several of them must be grouped to describe (part of) a given object. A central issue is how simple individual features should be and how to group them. If too simple, they will not be informative enough, and raise the complexity of the matching process. If too complex (like geons), they will not be detectable reliably.

Contour features A common framework is to use edge points (edgels) grouped into silhouettes. As a silhouette has no internal information nor holes, it can be represented by a single closed curve, and described by simple global descriptors like circularity, eccentricity, INRIA major axis orientation, or bending energy. However, these can only discriminate between very different shapes, so more complex descriptors have been proposed, such as the curvature scale space [START_REF] Mokhtarian | Scale-based description and recognition of planar curves and two-dimensional shapes[END_REF], Fourier descriptors [START_REF] Zahn | Fourier Descriptors for Plane Closed Curves[END_REF], and the medial axis transform [START_REF] Sharvit | Symmetry-Based Indexing of Image Databases[END_REF].

As noticed by Belongie et al. [START_REF] Belongie | Shape Matching and Object Recognition using Shape Contexts[END_REF], silhouettes are fundamentally limited because they ignore internal contours and are difficult to extract. This explains why more recent works represent shapes as loose collections of 2D points [START_REF] Cootes | Active Shape Models: Their Training and Application[END_REF][START_REF] Gavrila | Multi-Feature Hierarchical Template Matching Using Distance Transforms[END_REF] or 2D features in general, e.g. [START_REF] Elidan | Learning Object Shape: From Drawings to Images[END_REF][START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF]. However, more informative structures than individual edgels are preferable, as they simplify matching. Belongie et al. [START_REF] Belongie | Shape Matching and Object Recognition using Shape Contexts[END_REF] propose the Shape Context, which captures for each point the spatial distribution of all other points relative to it on the shape. Shape Context is a good semi-local representation and supports recognition by allowing to establish pointto-point correspondences between shapes even under deformations. Leordeanu et al. [START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF] propose another way to go beyond individual edgels, by encoding relations between all pairs of edgels. Similarly, Elidan et al. [START_REF] Elidan | Learning Object Shape: From Drawings to Images[END_REF] use pairwise spatial relations between landmark points. Ferrari et al. [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] present a family of scale-invariant local shape features formed by short chains of connected contour segments, capable of cleanly encoding pure fragments of an object boundary. They offer an attractive compromise between information content and repeatability, and encompass a wide variety of local shape structures.

Modeling shape categories Edgels and other generic features can be directly used to model any object. An alternative is to learn features adapted to a particular object category. For instance, Shotton et al. [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] and Opelt et al. [START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF] automatically learn class-specific boundary fragments, i.e. local edgel groups. Moreover, the fragments are arranged in a star configuration, which is learned as well. In addition to their own local shape, such fragments store a pointer to the object center, enabling object localization in novel images using voting. Other methods [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF][START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] achieve the same functionality by encoding spatial organization by tiling object windows, and learning which features and tile combinations discriminate objects from background.

The overall shape model of the above approaches is either (a) a global geometric organization of edge fragments [START_REF] Belongie | Shape Matching and Object Recognition using Shape Contexts[END_REF][START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF][START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]; or (b) an ensemble of pairwise constraints between point features [START_REF] Elidan | Learning Object Shape: From Drawings to Images[END_REF][START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF]. Global geometric shape models are appealing because of their ability to handle deformations, which can be represented in several ways. The authors of [START_REF] Belongie | Shape Matching and Object Recognition using Shape Contexts[END_REF] use regularized Thin Plate Splines, found to be effective for modeling changes in biological forms. This generic deformation model can quantify dissimilarity between any two shapes, but does not allow to model shape variations within a specific class. In contrast, Pentland et al. [START_REF] Pentland | Closed-form solutions for physically based shape modeling and recognition[END_REF] learn modes of intra-class deformation of an elastic material using a set of training shapes. The most famous work in this spirit is Active Shape Models [START_REF] Cootes | Active Shape Models: Their Training and Application[END_REF], where the shape model in novel images is constrained to vary only in ways seen in a set of training shapes. The main deformation modes, accounting for most of the total variability over the training set, are learnt using PCA. More generally, non-linear statistics can be used to gain robustness to noise and outliers [START_REF] Cremers | Nonlinear Shape Statistics in Mumford-Shah Based Segmentation ECCV[END_REF].

A shortcoming of the above methods is the need for clean training shapes. This manual image segmentation quickly becomes intractable when hundreds of categories are considered.

Several researchers have tried to develop semi-supervised algorithms not requiring segmented training examples. The key idea is to find combinations of object features repeatedly occurring over the example images. Berg et al. [START_REF] Berg | Shape Matching and Object Recognition using Low Distortion Correspondence[END_REF] suggest to build the model by using pairs of images containing an object instance, by retaining parts matching across several image pairs. A similar strategy is used by [START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF], which initializes the model using all line segments from a single image and then use many other images to iteratively remove spurious features and add new good features. LOCUS [START_REF] Winn | LOCUS: Learning Object Classes with Unsupervised Segmentation[END_REF] is another model which can be learned in an semisupervised way, but needs the objects to be aligned in the training images and to occupy most of their surface.

One important limitation common to these approaches is the lack of modeling of intraclass shape deformations, assuming the same shape model is explaining all training images. Moreover, as pointed out by [START_REF] Chum | An Exemplar Model for Learning Object Classes[END_REF][START_REF] Winn | The Layout Consistent Random Field for Recognizing and Segmenting Partially Occluded Objects[END_REF], LOCUS is not suited for localizing objects in extensively cluttered test images. Finally, the models learned by [START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF] are sparse collections of features, rather than explicit shapes formed by continuous connected curves. As a consequence, [START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF] cannot localize objects up to their (complete) boundaries in test images.

Shape matching Object recognition using shape can be casted as a matching problem: find correspondences between model features and image features (e.g. edgels, groups of segments, shape contexts). This often costly combinatorial problem can be made tractable by accepting sub-optimal matching solutions.

When the shape is not deformable or we are not interested in recovering the deformation but only in localizing the object up to translation and scale, simple strategies can be applied, such as Geometric Hashing [START_REF] Lamdan | Affine invariant model-based object recognition[END_REF], Hough Transform [START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF], or exhaustive search (typically combined with Chamfer Matching [START_REF] Gavrila | Multi-Feature Hierarchical Template Matching Using Distance Transforms[END_REF] or classifiers [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]). In case of complex deformations, the parameter space becomes too large for these simple strategies. Gold and Rangarajan [START_REF] Gold | Graduated Assignment Algorithm for Graph Matching[END_REF] propose an iterative method to simultaneously find correspondences and the model deformation. The sum of distances between model points and image points is minimized by alternating a step where the correspondences are estimated while keeping the transformation fixed, and a step where the transformation is computed while fixing the correspondences. Chui and Rangarajan [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF] put this idea in a deterministic annealing framework and adopts Thin Plate Splines as deformation model (TPS). The great advantage of the deterministic annealing formulation is that it elegantly supports a coarse-to-fine search in the TPS transformation space, while maintaining a continuous soft-correspondence matrix. A related framework is adopted by Belongie et al. [START_REF] Belongie | Shape Matching and Object Recognition using Shape Contexts[END_REF], where matching is supported by shape contexts. Depending on the model structure, optimization scheme can be based on Integer Quadratic Programming [START_REF] Berg | Shape Matching and Object Recognition using Low Distortion Correspondence[END_REF], spectral matching [START_REF] Leordeanu | Beyond Local Appearance: Category Recognition from Pairwise Interactions of Simple Features[END_REF] or graph cuts [START_REF] Winn | LOCUS: Learning Object Classes with Unsupervised Segmentation[END_REF].

Our approach in context In this paper, we present an approach for learning and matching shapes which has several attractive properties, bridging the shortcomings of previous works. First of all, we build explicit shape models based on continuous connected curves, which represent the prototype shapes of categories. The training objects need only be annotated by a bounding-box, i.e. no precise segmentation is necessary. Our learning approach avoids the pairwise image matching used in previous approaches, and is therefore computationally cheaper and more robust to clutter edgels due to the 'global view' it has by considering all training images at once. Moreover, we model intra-class deformations and enforce them at test time, when matching the model to novel images. Finally, we introduce a two-stage technique that allows the deformable matching of these explicit shape models to extensively cluttered test images, and therefore to accurately localize the complete boundaries of previously unseen object instances.

Local contour features

In order to learn and detect shapes in cluttered images of real-world scenes, some kind of local contour features are necessary. Before explaining the contributions of this paper, we briefly introduce here the features we employ.

PAS features. We build on the scale-invariant local contour features recently proposed by [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF]. Edgels are found by the excellent Berkeley edge detector [START_REF] Martin | Learning to detect natural image boundaries using local brightness, color, and texture cues[END_REF], and then grouped into pairs of connected, approximately straight segments (figure 2a). Informally, two segments are connected if they are adjacent on the same edgel-chain, or if one is at end of an edgelchain directed towards the other segment. Each pair of segments forms one feature, called a PAS, for Pair of Adjacent Segments.

A PAS feature has a location (mean over the two segment centers), a scale (distance between the segment centers), a strength (average edge detector confidence over the edgels with values in [0, 1]), and a descriptor invariant to translation and scale changes. The descriptor encodes the shape of the PAS, by the segments' orientations θ 1 , θ 2 and lengths l 1 , l 2 , and the relative location vector r, going from the center of the first segment to the center of the second (a stable way to derive the order of the segments in a PAS is given in [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF]). Both lengths and relative location are normalized by the scale of the PAS.

PAS features are particularly suited to our needs. First, they are robustly detected because they connect segments even across gaps between edgel-chains. Second, as both PAS and their descriptors cover solely the two segments, they can cover pure portion of an object boundary, without including clutter edges which often lie in the vicinity (as opposed to patch descriptors). Hence, PAS descriptors respect the nature of boundary fragments, to be one-dimensional elements embedded in a 2D image, as opposed to local appearance features, whose extent is a 2D patch. Fourth, PAS have intermediate complexity. As demonstrated in [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF], they are complex enough to be informative, yet simple enough to be detectable repeatably across different images and object instances. Finally, since a correspondence between two PAS induces a translation and scale change, they can be readily used within a Hough-style voting scheme for object detection [START_REF] Leibe | Scale-Invariant Object Categorization using a Scale-Adaptive Mean-Shift Search[END_REF][START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF].

PAS dissimilarity measure. The dissimilarity D(P a , P b ) between two PAS P a , P b defined in [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] is

D(P a , P b ) = wr r a -r b + w θ 2 i=1 D θ θ a i , θ b i + 2 i=1 log l a i /l b i (1)
where the first term is the difference in the relative locations of the segments, D θ ∈ [0, π/2] measures the difference between segment orientations, and the last term accounts for the difference in lengths. In all our experiments, the weights w r , w θ are fixed to the same values used in [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] (w r = 4, w θ = 2).

PAS codebook. We construct a codebook by clustering the PAS inside all training bounding-boxes according to their descriptors. For each cluster, we retain the centermost PAS, minimizing the sum of dissimilarities to all the others. The codebook C = {T i } is the collection of these centermost PAS, the PAS types {T i } (figure 2b). A codebook is useful for efficient matching, since all features similar to a type are considered in correspondence. Note that the codebook is class-specific and built from the same images used later to learn the shape model. In our experiments we obtained better shape models when starting from this codebook, rather than from a universal codebook (as opposed to [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF]).

Learning the shape model

In this section we present the new technique for learning a prototype shape for an object class and its principal intra-class deformation modes, given image windows with example instances (figure 3a). To achieve this, we propose a procedure for discovering which contour points belong to the common class boundaries, and for putting them in full point-to-point correspondence across the training examples. For example, we want the shape model to include the outline of a mug, which is characteristic for the class, and not the mug labels, which vary from example to example. The technique is composed of four stages (figure 3b-e):

1. Determine model parts as PAS frequently reoccurring with similar locations, scales, and shapes (subsection 4.1).

2. Assemble an initial shape by selecting a particular feature for each model part from the training examples (subsection 4.2).

3. Iteratively match the shape back onto the training images and refine it using the resulting point-to-point correspondences (subsection 4.3).

4. Learn a statistical model of intra-class deformations from the different shape variations produced by stage 3 (subsection 4.4).

Finding model parts

The first stage towards learning the model shape is to determine which PAS lie on boundaries common across the object class, as opposed to those on the background clutter and those on details specific to individual training instances. The key insight is that a PAS belonging to the class boundaries will recur consistently across several training instances with a similar location, size, and shape. Although they are numerous, PAS not belonging to the class boundaries are not correlated across different examples. In the following we refer to any PAS or edgel not lying on the class boundaries as clutter.

Bounding-box alignment. The first step of the algorithm is to align the training examples by transforming each bounding-box into a zero-centered rectangle with unit height and width equal to the geometric mean of the training aspect-ratios (i.e. width over height).

In addition to removing translation and scale differences, this effectively cancels out shape variations due to different aspect-ratios (e.g tall Starbucks mugs versus coffee cups). This facilitates the learning task, because PAS on the class boundaries are now better aligned.

Voting for parts. The core of the algorithm consists of a voting process. We maintain a separate voting space for each PAS type, in which PAS from all training instances are accumulated. From its limited, local perspective, each PAS votes for the existence of a part of the class boundary with shape, location, and size like its own (figure 4). More precisely, each PAS P votes as follows. First, it is soft-assigned to all PAS types T i within a dissimilarity t (equation ( 1)). Each voting space corresponds to a different PAS type, and has three dimensions: two for location and one for size. For each type the PAS is assigned to, it casts a vote for its own location and size in the corresponding accumulator space. Votes are weighted proportionally to the edge strength e of P , and in inverse proportion to the shape dissimilarity to the type D(P, T i ). The soft-assign to types makes the voting process less sensitive to the exact shape of the PAS and the exact codebook types. Weighting by edge strength allows to take into account the relevance of the PAS. It leads to better results over treating edgels as binary features (as also noticed by [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF][START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF]).

Parts as local maxima. After all PAS have casted their votes, we search for local maxima in location and scale in the accumulator spaces. Each maximum yields a model part M , which has a specific location and size relative to the canonical bounding-box, and a specific shape (the codebook type corresponding to the accumulator space where the maximum was found). Moreover, the value of the local maximum provides a measure of the confidence that the part really belongs to the class boundaries.

Advantages. The success of this procedure is due in part to adopting PAS as basic shape elements. A simpler alternative would be to use individual edgels. In that case, there would be just one voting space, with two location dimensions and one orientation dimension. In contrast, PAS bring two additional degrees of separation: the shape of the PAS, expressed as the assignments to codebook types, and its size (relative to the bounding-box). Individual edgels have no size, and the shape of a PAS is more distinctive than the orientation of an edgel. As a consequence, it is very unlikely that a significant number of clutter PAS will accidentally have similar locations, scales and shapes at the same time. Hence, recurring PAS stemming from the desired class boundaries tend to form peaks in the accumulator spaces, whereas background clutter and details of individual training instances don't.

Intra-class shape variability is addressed partly by the soft-assign of PAS to types, and partly by applying a substantial spatial smoothing to the accumulator spaces before detecting local maxima. This effectively creates wide basins of attraction for PAS from different training examples to accumulate evidence for the same part. We can afford this flexibility while keeping a low risk of accumulating clutter because of the high separability discussed above, especially due to separate accumulator spaces for different codebook types. This INRIA yields the discriminativity necessary to overcome the poor signal-to-noise ratio, while allowing the flexibility necessary to accommodate for intra-class shape variations.

The proposed algorithm sees all training data at once, and therefore reliably selects parts and robustly estimates their locations/scales/shapes. In our experiments this was more stable and more robust to clutter than matching pairs of training instances and combining their output a posteriori. As another important advantage, the algorithm has complexity linear in the number of training instances, so it can learn from large training sets efficiently.

Assembling the initial model shape

The collection of parts learned in the previous section captures class boundaries well, and conveys a sense of the shape of the object class (figure 3b). The outer boundary of the mug and the handle hole are included, whereas the label and background clutter are largely excluded. Based on this 'collection of parts' model (COP) one could already attempt to detect objects in a test image, by matching parts based on their descriptor and enforcing their spatial relationship. This could be achieved in a way similar to what earlier approaches do based on appearance features [START_REF] Fergus | Object Class Recognition by Unsupervised Scaleinvariant Learning[END_REF][START_REF] Leibe | Scale-Invariant Object Categorization using a Scale-Adaptive Mean-Shift Search[END_REF], and also done recently with contour features by [START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF].

However, the COP model is not a shape. It is a loose collection of fragments not connected into a whole shape made of smooth, continuous lines. This can be seen in the multiple stokes along what should be a single line, such as on the top of the mug in figure 3b. Moreover, adjacent parts don't fit together in terms of their relative location and size. The COP model is missing a notion of shape on the global scale. Individual parts are learnt independently, each focusing on its own local scale. Going all the way to a proper whole shape is desirable, because it can be used to perform object detection using effective shape-matching techniques. This brings the advantage which motivates this paper: localize objects up to their boundaries, rather than up to a bounding box. In this subsection and the next we describe a procedure for constructing such a shape. 5ab). These occurrences offer roughly similar, yet different alternatives for the part's location, size, and shape. Hence, we can assemble several variants for the overall shape by selecting different occurrences for each part. The idea is to select an occurrence for each part so as to form larger aggregates of connected occurrences (figure 3c). This can be achieved by assembling occurrences coming from only a few images, since occurrences from the same image fit together naturally.

Shape variants. A model part occurs several times on different training images (figure

In this section we cast the problem of assembling a model shape as a combinatorial optimization problem. We introduce the concept of connectedness between model parts and between occurrences, and then select one occurrence for each part so as to obtain a well connected shape. In the following we start with a few definitions necessary to set up the optimization problem, then give the objective function, and present a simple way to maximize it.

below). b) All occurrences of all model parts on a few training images, colored by their confidence (increasing from blue to cyan to green to yellow to red). c) Two model parts with high connectedness (above) and two of their occurrences, which share a common segment (below).

Occurrences. A PAS P from a specific training image is an occurrence of a model part M if they have similar shape, location, and scale (figure 5a). The following function quantifies this similarity, and expresses the confidence that P is an occurrence of M (denoted M → P ):

conf(M → P ) = Pstr • D(M, P ) • min M scale P scale , P scale M scale • e -1 2σ 2 loc M loc -P loc 2 (2)
Essentially, the occurrences of M are the PAS that voted for it in section 4.1. The confidence (2) takes into account P 's relevance (edge strength, first factor), as well as how far P is from the peak in the voting space (second to last factors). Function (2) ranges in [0, 1], and we consider P an occurrence of M if conf(M → P ) > thresh.

Connectedness. Recall from section 4.1 that a model part M has a specific PAS type and a location and size within the canonical bounding-box. Hence, M has two contour segments M 1 , M 2 . An important observation is that two occurrences of different model parts might have a segment in common (figure 5c). This provides valuable evidence that the two parts explain connected pieces of the true class boundaries and hence should be connected in the model shape. Since every model part occurs in several training images, we can robustly estimate how likely they are to be connected, by counting how frequently their occurrences share segments. More formally, let the equivalence between two segments M i , N j from different model parts M, N be eq(Mi, Nj ) =

{s|M i →s,N j →s} conf(Mi → s) + conf(Nj → s) (3)
with i, j ∈ {1, 2} and s a segment on which both M i , N j occur (figure 5c). Two model segments have high equivalence if they frequently occur on the same training segments.

Based on this, we define the connectedness between two model parts M, N as conn(M, N ) = max(eq(M1, N1) + eq(M2, N2), eq(M1, N2) + eq(M2, N1))

INRIA which is the combined equivalence of their segments (for the best of the two possible segment matchings). Two parts have high connectedness (4) if their occurrences frequently share a segment. Two parts can even share both their segments. In this case, their connectedness is even higher, suggesting they explain the same portion of the class boundaries. Equivalent model segments cause the multiple strokes in the COP model (figure 3b). Equation ( 4) estimates part connectedness robustly because it integrates evidence over all training images.

Objective function. The occurrence selection task can now be formulated precisely: find the assignment A(M ) = P of occurrences to parts that maximizes the following objective function:

M conf (M → A(M )) + λconn M,N conn(M, N ) • 1img (A(M ), A(N )) -λimgNimg (5)
where the indicator function 1 img takes value 1 if two occurrences come from the same image, and 0 otherwise. N img is the number of images contributing occurrences to A, and λ img , λ conn are predefined weights. Exactly one occurrence is assigned to each part. The first term of the objective function prefers high confidence occurrences. The second favors assigning parts with high connectedness to occurrences from the same image. This pushes towards assigning connected occurrences to connected parts, because occurrences of parts with high connectedness are likely to be connected themselves if they lie in the same image (by construction of function 4). The last term discourages scattering occurrences across many images, as occurrences from the same image fit together naturally. This holds even for occurrences which are not directly connected, but lie on different portions of the shape. Hence, the last term encourages assignments concentrating on a few training images.

Overall, function [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF] encourages the formation of aggregates of good confidence and properly connected occurrences. In addition, the second and third terms push equivalent model segments to be assigned to the same actual image segments, hence suppressing multiple strokes.

Optimization. It is computationally expensive to optimize the objective function [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF] exactly, as the space of all possible assignments is huge. In practice, the following approximation algorithm brings satisfactory results. We start by assigning the part with the single most confident occurrence. Next, we iteratively consider the part most connected to those assigned so far, and assign it to the occurrence which maximizes [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF]. The algorithm iterates until all parts have been assigned to an occurrence Figure 3c shows the selected occurrences for our running example. The shape is composed of three blocks, each from a different training image. Within each block, segments fit well together and form continuous lines. Nevertheless, there are discontinuities between blocks, and some redundant strokes remains (lower half of the handle).

Model shape refinement

In this subsection we refine the initial model shape constructed above. This is achieved by treating it as a deformable point set and applying a non-rigid point matching algorithm to match it back onto the training images. For each image, we deform the model by establishing point correspondences with the edgels within the object's bounding-box (figure 6b). An improved model shape is obtained by averaging these backmatched shapes. The updated shape is then matched back on the training images, and the process iterates. This results in a succession of better models and better matches to the training data, as the point correspondence cover more of the true class boundaries of the training objects (figure 6c+d).

The proposed technique can be seen as searching for the model shape that best explains the training data, under the rather general assumption that smooth deformations account for the difference between the model shape and the class boundaries of the training objects.

Before explaining the algorithm in detail, notice that we work now at the level of individual image edgels, no longer with PAS features as in the previous stages. As a preprocessing step, we sample the initial model shape, thus obtaining a point set (figure 6a). The main algorithm iterates over the following three steps: INRIA 1. Backmatching. The current model shape is matched back to each training image in turn. We use an extension of the excellent non-rigid robust point matcher by Chui and Rangarajan [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF]. Following their naming, we refer to the algorithm by TPS-RPM (Thin-Plate Spline Robust Point Matcher).

TPS-RPM estimates a Thin-Plate Spline transformation between the model points and the image edgels while at the same time rejecting edgels not corresponding to any model point. This is an important ability, as only some of the image edgels lie on the object boundaries.

As with any shape matching technique, in order to work with noisy point sets TPS-RPM needs to start from a reasonable initial transformation. We initialize it by transforming the model shape so that its bounding-box aligns with the training bounding-box (figure 6b). This strong initialization makes TPS-RPM very likely to succeed. Subsection 5.2 presents this technique in more detail, as it will be used again for localizing object boundaries in test images.

2. Average shape. An important benefit of backmatching is that it generates shapes in full point-to-point correspondence, because they are all smooth deformations of the same initial shape (figure 6c). These correspondences allow us to manipulate the shapes as a set, and to analyze the variations in the point locations. We apply Cootes' variant of Procustes analysis [START_REF] Cootes | Active Shape Models: Their Training and Application[END_REF] to align them with respect to translation, scale, and orientation. The remaining differences are due to true (non-rigid) shape variations, which we will learn in the next subsection.

The model shape is now updated by setting it to the average of the aligned shapes (i.e. average coordinates of corresponding points; figure 6c). The combined effects of backmatching and computing the average shape are very beneficial (figure 6c). Segments of the model shape are moved, bent, and stretched so as to form smooth, connected lines, thus recovering the shape of the class well on a global scale (e.g. topmost and leftmost segments in figure 6c). The reason for these improvements is that backmatching deforms the initial shape onto the class boundaries of the training images, thus delivering a set of natural, well formed shapes. The averaging step then integrates them all into a generic-looking shape, and smoothes out occasional inaccuracies of the individual backmatches.

3. Remove redundant points. As another effect, the previous steps tend to crush multiple strokes (and other clutter points) onto the same points along the correct class boundaries. This results in redundant points, roughly coincident with other segments (figure 6c). We remove them by deleting a point if it lies very close to another point from a part with higher confidence (see subsection 4.1 for definition of the confidence of a part). If a significant proportion of points (> 10%) are removed, the procedure iterates to point 1 (figure 6d). Otherwise, it is completed.

Impact. As shown in figure 6d, the running example improves further during the second (and final) iteration. For example, the handle arcs becomes more continuous. The final shape is overall smooth and well connected, includes no background clutter and very little interior clutter, and, as desired, represents an average class member (a prototype shape). Notice how both large scale (the external frame) and fine scale structures (the double handle arc) are correctly recovered. The backmatched shapes also improve in the second iteration, because shape matching is easier given a better model. In turn, the better backmatches yield a better average shape (i.e. a better model). The mutual help between backmatching and updating the model is key for the success of the procedure.

In figure 7, we show examples of other models evolving over the three stages (sections 4.1 to 4.3). Notice the large positive impact of model shape refinement. Furthermore, to demonstrate that the proposed techniques consistently produce good quality models, we show many of them in the result section (figure 11).

Discussion. Our idea for shape refinement is related to a general design principle which recently emerged in different areas of vision. It involves going back to the image after building some intermediate representation from initial low-level features, to refine and extend it. This differs from the conventional way of building layers of increasing abstraction, involving representations of higher and higher level, progressively departing from the original image data. The traditional strategy suffers from two problems: errors accumulate from a layer to the next, and relevant information missed by the low-level features is never recovered. Going back to the image enables to correct both problems, and it has good chances to succeed since a rough model has already been built. Several different algorithms are instances of this strategy and have led to excellent results in various areas: human pose estimation [START_REF] Ramanan | Learning to parse images of articulated bodies[END_REF], appearance-based top-down segmentation [START_REF] Leibe | Scale-Invariant Object Categorization using a Scale-Adaptive Mean-Shift Search[END_REF], and recognition of specific objects [START_REF] Ferrari | Simultaneous Object Recognition and Segmentation by Image Exploration[END_REF].

Learning shape deformations

The previous subsection matches the model shape to each training image, and thus provides examples of the variations within the object class we want to learn. Since these examples are in full point-to-point correspondence, we can learn a compact model of the intra-class variations using the statistical shape analysis technique by Cootes [START_REF] Cootes | Active Shape Models: Their Training and Application[END_REF].

The idea is to consider each example shape as a point in a 2p-D space (with p the number of points on each shape), and model their distribution with Principal Component Analysis (PCA). The eigenvectors returned by PCA represent modes of variation, and the associated eigenvalues λ i their importance (how much the example shapes deform along them, figure 3e). By keeping only the n largest eigenvectors E 1:n representing 95% of the total variance, we can approximate the region in which the training examples live by x + E 1:n b, where x is the mean shape, b is a vector representing shapes in the subspace spanned by E 1:n , and b's i th component is bound by ±3 √ λ i . This defines the valid region of the shape space, containing shapes similar to the example ones. Typically, n < 15 eigenvectors are sufficient (compared to 2p ≃ 200).

Figure 3e shows the first two deformation modes for our running example. The first mode spans the spectrum between little coffee cups and tall Starbucks-style mugs, while the handle can vary from pointed down to pointed up within the second mode. In subsection 5.3, we exploit this deformation model to constrain the matching of the model to novel test images. Notice that previous works on these deformation models require at least the example shapes as input [START_REF] Hill | A Method of Non-Rigid Correspondence for Automatic Landmark Identification[END_REF], and many also need the point-to-point correspondences [START_REF] Cootes | Active Shape Models: Their Training and Application[END_REF]. In contrast, we automatically learn shapes, correspondences, and deformations given just images.

Object detection

In this section we describe how to localize the boundaries of previously unseen object instances in a test image. To this end, we match the shape model learnt in the previous section to the test image edges. This task is very challenging, because 1) the image can be extensively cluttered, with the object covering only a small proportion of its edges (figure 8a-b); and 2) to handle intra-class variability, the shape model must be deformed into the shape of the particular instance shown in the test image.

We decompose the problem into two stages. We first obtain rough estimates for location and scale of the object based on a Hough-style voting scheme (subsection 5.1). This greatly simplifies the subsequent shape matching, as it approximately lifts three degrees of freedom (translation and scale). The estimates are then used to initialize the non-rigid shape matcher [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF] (subsection 5.2). This combination enables shape matching in cluttered images, and hence localization of object boundaries. Furthermore, in subsection 5.3, we constrain the matcher to explore only the region of shape space spanned by the training examples, thereby ensuring that output shapes are similar to class members.

Initialization by Hough voting

In subsection 4.1 we have represented the shape of a class as a set of PAS parts, each with a specific shape, location, size, and confidence. Here we match these parts to PAS from the test image, based on their shape descriptors. More precisely, a model part is deemed matched to an image PAS if their dissimilarity ( 1) is below a threshold t (this is the same as used in section 4.1). Since a pair of matched PAS induces a translation and scale transformation, each match votes for the presence of an object instance at a particular location (object center) and scale (in the same spirit as [START_REF] Leibe | Scale-Invariant Object Categorization using a Scale-Adaptive Mean-Shift Search[END_REF][START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF][START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]). Votes are weighed by the shape similarity between the model part and test PAS, the edge strength of the PAS, and the confidence of the part. Local maxima in the voting space define rough estimates of the location and scale of candidate object instances (figure 8c).

The above voting procedure delivers 10 to 40 local maxima in a typical cluttered image, as the local features are not very distinctive on their own. The important point is that a few tens is far less than the number of possible location and scales the object could take in the image, which is in the order of the thousands. Thus, Hough voting acts as a focus of attention mechanism, drastically reducing the problem complexity. We can now afford to run a full-featured shape matching algorithm, starting from each of the initializations. Note that running shape matching directly, without initialization, is likely to fail on very cluttered images, where only a small minority of edgels are on the boundaries of the target object.

INRIA

Shape Matching by TPS-RPM

For each initial location l and scale s found by Hough voting, we obtain a point set V by centering the model shape on l and rescaling it to s, and a set X which contains all image edge points within a larger rectangle of scale 1.8s (figure 8c). This larger rectangle is designed to contain the whole object, even when s is under-estimated. Any point outside this rectangle is ignored by the shape matcher.

Given the initialization, we want to put V in correspondence with the subset of X lying on the object boundary. We estimate the associated non-rigid transformation, and reject image points not corresponding to any model point with the Thin-Plate Spline Robust Point Matching algorithm (TPS-RPM [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF]). In this subsection we give a brief summary of TPS-RPM, and we refer to [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF] for details.

TPS-RPM matches the two point sets V = {v a } a=1..K and X = {x i } i=1..N by applying a non-rigid TPS mapping {d, w} to V (d is the affine component, and w the non-rigid warp). It estimates both the correspondence matrix M = {m ai } between V and X, and the mapping {d, w} that minimize an objective function including 1) the distance between points of X and their corresponding points of V after mapping them by the TPS, and 2) the regularization terms for the affine and warp components of the TPS. In addition to the inner K × N part, M has an extra row and an extra column which allow to reject points as unmatched.

Since neither the correspondence M nor the TPS mapping {d, w} are known beforehand, TPS-RPM iteratively alternates between updating M , while keeping {d, w} fixed, and updating the mapping with M fixed. M is a continuous-valued soft-assign matrix, allowing the algorithm to evolve through a continuous correspondence space, rather than jumping around in the space of binary matrices (hard correspondence). It is updated by setting m ai as a function of the distance between x i and v a , after mapping by the TPS (details below). The update of the mapping fits a TPS between V and the current estimate Y = {y a } a=1..K of the corresponding points. Each point y a in y is a linear combination of all image points {x i } i=1..N weighted by the soft-assign values M (a, i):

ya = N i=1 maixi (6)
The TPS fitting maximizes the proximity between the points Y and the model points V after TPS mapping, under the influence of the regularization terms, which penalize local warpings w and deviations of d from the identity. Fitting the TPS to V ↔ Y rather than to V ↔ X, allows to harvest the benefits of mantaining a full soft-correspondence matrix M . The optimization procedure of TPS-RPM is embedded in a deterministic annealing framework by introducting a temperature parameter T , which decreases at each iteration. The entries of M are updated by the following equation:

mai = 1 T exp (xi -f (va, d, w)) T (xi -f (va, d, w)) 2T (7)
where f (v a , d, w) is the mapping of point v a by the TPS {d, w}. The entries of M are then iteratively normalized to ensure the rows and columns sum to 1 [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF]. Since T is the bandwidth of the Gaussian kernel in equation ( 7), as it decreases M becomes less fuzzy, progressively approaching a hard correspondence matrix. At the same time, the regularization terms of the TPS is given less weight. Hence, the TPS is rigid in the beginning, and gets more and more deformable as the iterations continue. These two phenomena enable TPS-RPM to find a good solution even when given a rather poor initialization. At first, when the correspondence uncertainty is high, each y a essentially averages over a wide area of X around the TPS-mapped point and the TPS is constrained to near-rigid transformations. This can be seen as a large T in equation ( 7) generates similar-valued m ai , which are then averaged by equation [START_REF] Chum | An Exemplar Model for Learning Object Classes[END_REF]. As the iterations continue and the temperature decreases, M looks less and less far, and pays increasing attention to the differences between matching options from X. Since the uncertainty diminishes, it is safe to let the TPS looser, freer to fit the details of X more accurately. Figure 9 illustrates TPS-RPM on our running example.

We have extended TPS-RPM by adding two terms to the objective function: the orientation difference between corresponding points (minimize), and the edge strength of matched image points (maximize). In our experiments, these extra terms made TPS-RPM more accurate and stable, i.e. it succeeds even when initialized farther away from the best location and scale.

Constrained shape matching

TPS-RPM treats all shapes according to the same generic TPS deformation model, simply preferring smoother transformations (in particular, low 2D curvature w, and low affine skew d). Two shapes with the same deformation energy are considered equivalent. This might result in output shapes unlike any of the training examples. In this section, we extend TPS-RPM with the class-specific deformation model learned in subsection 4.4. We constrain the optimization to explore only the valid region of the shape space, containing shapes plausible for the class (defined by x, E 1:n , λ i from subsection 4.4).

At each iteration of TPS-RPM we project the current shape estimate Y (equation ( 6)) inside the valid region, just before fitting the TPS. This amounts to: The assignment Y ← Y c imposes hard constraints on the shape space. While this guarantees output shapes similar to class members, it might sometimes be too restrictive. To match a novel instance accurately, it could be necessary to move a little along some dimensions of the shape space not recorded in the deformation model. The training data cannot be assumed to present all possible intra-class variations.

To tackle this issue, we propose a soft-constrained variant, where Y is attracted by the valid region, with a force that diminishes with temperature: Y ← Y + T Tinit (Y c -Y ). This causes TPS-RPM to start fully constrained, and then, as temperature decreases and M looks for correspondences closer to the current estimates, later iterations are allowed to apply small deformations beyond the valid region (typically along dimensions not in E 1:n ). As a result, output shapes fit the image data more accurately, while still resembling class members. Notice how this behavior is fully in the spirit of TPS-RPM, which also lets the TPS more and more free as T decreases.

The proposed extension to TPS-RPM reaches deep into its heart as it alters the search through the transformation and correspondence spaces. Beside improving accuracy, it can help TPS-RPM to avoid local minima far from the correct solution, thus avoiding gross failures.

Figure 8e shows the improvement brought by the proposed constrained shape matching, compared to TPS-RPM with just the generic TPS model (figure 8d). On the running example, the two versions of TPS-RPM diverge crucially after the eight iteration, as shown in figure 9.

Detections

Every local maximum in Hough space constitutes an initialization for the shape matching, and results in different shapes (detections) localized in the test image. In this section we score the detections, making it possible to reject detections and to evaluate the detection rate and false-positive rate of our system. We score each detection by a weighted sum of four terms:

1) the number of matched model points, i.e. for which a corresponding image point has been found with good confidence. Following [START_REF] Chui | A new point matching algorithm for non-rigid registration[END_REF], these are all points v a with max i=1..N (m ai ) > 1/N .

2) the sum of squared distances from the TPS-mapped model points to their corresponding image points. This measure is made scale-invariant by normalizing by the squared range r 2 of the image point coordinates (width or height, whichever is larger). Only matched model points are considered.

3) the deviation i,j∈ [START_REF] Basri | Determining the Similarity of Deformable Shapes[END_REF][START_REF] Berg | Shape Matching and Object Recognition using Low Distortion Correspondence[END_REF] This score integrates the information a matched shape provides. It is high when the TPS fits many (term 1) points well (term 2), without having to distort much (terms 3 and 4). In our current implementation, the relative weights between these terms have been selected manually, they are the same for all classes, and remain fixed in all experiments.

I(i, j) -d(i, j)/ |d|
As a final refinement, if two detections overlap substantially, we remove the lower scored one. Notice that the method can detect multiple instances of the same class in an image. Since they appear as different peaks in the Hough voting space, they result in separate detections.

Experiments

We present an extensive experimental evaluation involving six diverse object classes from two existing datasets [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF][START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF]. After introducing the datasets in the next subsection, we evaluate our approach for learning shape models in subsection 6.2. The ability to localize objects in novel test images, both in terms of traditional bounding-boxes and precise object boundaries, is measured in subsection 6.3. All experiments are run with exactly the same parameters (no class-specific nor dataset-specific tuning is applied).

Datasets and protocol

ETHZ shape classes [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF]. This dataset features five diverse classes (bottles, swans, mugs, giraffes, apple-logos) and contains a total of 255 images collected from the web by Ferrari et al. [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF]. It is highly challenging, as the objects appear in a wide range of scales, there is considerable intra-class shape variation, and many images are severely cluttered, with objects comprising only a fraction of the total image area (figures 16, 13).

For each class, we learn 5 models, each from a different random sample containing half of the available images (there are 40 for apple-logos, 48 for bottles, 87 for giraffes, 48 for mugs and 32 for swans). Learning models from different training sets allows to evaluate the stability of the proposed learning technique (subsection 6.2). Notice that our method does not require any negative image for training, i.e. images not containing any instance of the class.

The test set for a model consists of all other images in the dataset. Since this includes about 200 negative images, it allows to properly estimate false-positive rates. Table 6 gives an overview of the composition of all training and testing sets. We refer to learning and testing on a particular split of the images as a trial.

INRIA horses [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF]. This challenging dataset consists of 170 images with one or more horses viewed from the side and 170 images without horses. Horses appear at several scales, and against cluttered backgrounds.

We train 5 models, each from a different random subset of 50 horse images. For each model, the remaining 120 horse images and all 170 negative images are used for testing, see table 6.

Learning shape models

Evaluation measures. We assess the performance of the learning procedure of section 4 in terms of how accurately it recovers the true class boundaries of the training instances. For the purpose of this evaluation, we have manually annotated the boundaries of all object instances in the ETHZ shape classes dataset.

Let B gt be the ground-truth boundaries, and B model the backmatched shapes output by the model shape refinement algorithm of subsection 4.3. The accuracy of learning is quantified by two measures. Coverage is the percentage of points from B gt closer than a threshold t from any point of B model . We set t to 4% of the diagonal of the bounding-box of B gt . Conversely, precision is the percentage of B model points closer than t from any point of Models from the full algorithm. Table 2 shows coverage and precision averaged over training instances and trials, for the complete learning procedure described in section 4. With the exception of giraffes, the proposed method achieves very high coverage (above 90%), demonstrating its ability to discover which contour points belong to the class boundaries. The precision of apple-logos and bottles is also excellent, thanks to the remarkably clean prototype shapes learned by our approach (figure 11). Interestingly, the precision of mugs is somewhat lower, because the learned shapes include a detail not present in the ground-truth annotations, although it is arguably part of the class boundaries: the inner half of the opening on top of the mug. A similar phenomenon penalizes the precision of swans, where our method sometimes includes a few water waves in the model. Although they are not part of the swan boundaries, waves accidentally occurring at a similar position over many training images are picked up by the algorithm. A larger training set might lead to the suppression of such artifacts, as waves have less chances of accumulating accidentally (we only used 16 images). The modeling performance for giraffes is lower, due to the extremely cluttered edgemaps arising from their natural environment, and to the camouflage texture which tends to break edges along the body outlines (figure10).

Models without assembling the initial shape. One could design a simpler scheme for learning shape models by skipping the procedure for assembling the initial shape (section 4.2). An alternative initial shape could be obtained directly from the COP model (section 4.1) by picking the highest confidence occurrence for each part independently (i.e. the single occurrence maximizing equation ( 2)). This initial shape could then be passed on to the shape refinement stage as usual (section 4.3). For each object class and trial we have rerun the learning algorithm without the assembly stage, but otherwise keeping identical conditions (including using exactly the same training images). Many of the resulting prototype shapes are moderately worse than those obtained using the full learning scheme (figure 11 bottom row). However, the lower model quality only results in slightly lower average coverage/accuracy values (table 2). These results suggest that while the initial assembly stage does help getting better models, it is not a crucial step. Interestingly, this suggests that the shape refinement stage proposed in section 4.3 is robust to large amounts of noise, and delivers good models even when starting from poor initial shapes.

INRIA

Object detection

Detection up to a bounding-box. We first evaluate the ability of the object detection procedure of section 5 to localize objects in cluttered test images up to a bounding-box (i.e. the traditional detection task commonly defined in the literature).

Figure 12 reports detection-rate against the number of false-positives averaged over all test images (FPPI) and averaged over the 5 trials. As discussed above, this includes mostly negative images. We adopt the strict standards of the PASCAL Challenge criterion (dashed lines in the plots): a detection is counted as correct only if the intersection-over-union ratio Figure 12: Object detection performance (models learnt from real images). Each plot shows five curves: the full system evaluated under the PASCAL criterion for a correct detection (dashed, thick, red), the full system under the 20%-IoU criterion (solid, thick, red), the Hough voting stage alone under PASCAL (dashed, thin, blue), [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] under 20%-IoU (solid, thin, green) and under PASCAL (dashed, thin, green). The curve for the full system under PASCAL in the apple-logo plot is identical to the curve for 20%-IoU.

(IoU) with the ground-truth bounding-box is greater than 50%. All other detections are counted as false-positives. In order to compare to [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF][START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF], we also report results under their somewhat softer criterion: a detection is counted as correct if its bounding-box overlaps more than 20% with the ground-truth one, and vice-versa (we refer to this criterion as 20%-IoU).

As the plots show, our method performs well on all classes but giraffes, with detectionsrates around 80% at the moderate false-positive rate of 0.4 FPPI (this is the reference point for all comparisons). The lower performance on giraffes is mainly due to the difficulty of building shape models from their extremely noisy edge maps.

It is interesting to compare against the detection performance obtained by the Hough voting stage alone (subsection 5.1), without the shape matcher on top (subsections 5.2, 5.3). The full system performs substantially better: the difference under PASCAL criterion is about 30% averaged over all classes. This shows the benefit of treating object detection fully as a shape matching task, rather than simply matching local features, which is one of the principal points of this paper. Moreover, the shape matching stage also makes it possible to localize complete object boundaries, rather than just bounding-boxes (figure 13).

The difference between the curves under the PASCAL criterion and the 20%-IoU criterion of [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF][START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] is small for apple-logos, bottles, mugs and swans (0%, 1.6%, 3.6%, 4.9%), indicating that most detections have accurate bounding-boxes. For horses and giraffes the decrease is more significant (18.1%, 14.1%), because the legs of the animals are harder to detect and cause the bounding-box to shift along the body. On average over all classes, our method achieves 78.1% detection-rate at 0.4 FPPI under 20%-IoU and 71.1% under PASCAL.

For reference, the plots also show the performance of [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] on the same dataset, using the same number of training and test images. An exact comparison is not possible, as [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] reports result based on only one training/testing split, whereas we average over 5 random splits. Under the rather permissive 20%-IoU criterion, [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] performs a little better than our method on average over all classes. Under the strict PASCAL criterion instead, our method performs substantially better than [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] on two classes (apple-logos, swans), moderately worse on two (bottles, horses), and about the same on two (mugs, giraffes), thanks to the higher accuracy of the detected bounding-boxes. Averaged over all classes, under PASCAL our method reaches 71.1% detection-rate at 0.4 FPPI, comparing well against the 68.5% of [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF]. Notice how our results are achieved even without the beneficial discriminative learning of [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF], where a SVM learns which PAS types at which relative location within the training bounding-box best discriminate between instances of the class and background image windows. Our method instead trains only from positive examples. Beyond this evaluation, the method presented in this paper offers two important advantages over [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF]. It localizes object boundaries, rather than just bounding-boxes, and can also detect objects starting from a single hand-drawing as a model (see below).

Localizing object boundaries. The most interesting feature of our approach is the ability to localize object boundaries in novel test images. This is shown by several examples in figure 13, where the method succeeds in spite of extensive clutter, a large range of scales, and intra-class variability. In the following we quantify how accurately the output shapes match the true object boundaries. We use the coverage and precision measures defined above. In the present context, coverage is the percentage of ground-truth boundary points recovered by the method and precision is the percentage of output points that lie on the ground-truth boundaries.

Table 3 shows coverage and precision averaged over trials and correct detections at 0.4 FPPI. Coverage ranges in 78 -92% for all classes but giraffes, demonstrating that most of the true boundaries have been successfully detected. Moreover, precision values are similar, indicating that the method returns only a small proportion of points outside the true boundaries. Performance is lower for giraffes, due to the more noisy models and difficult edgemaps derived from the test images.

Figure 13: Example detections (models learnt from images). Notice the large scale variations (especially in apple-logos, swans), the intra-category shape variability (especially in swans, giraffes), and the extensive clutter (especially in giraffes, mugs). The method works for photographs as well as paintings (first swan, last bottle). Two bottle cases show also false-positives. In the first two horse images, the horizontal line below the horses' legs is part of the model and represents the ground. Interestingly, the ground line systematically reoccurs over the training images for that model and gets learned along with the horse.

INRIA default TPS default TPS shape constrained shape constrained Figure 14: (left) typical improvement brought by constrained shape matching over simply using the TPS deformation model. As the improvement is often a refinement of a local portion of the shape (the swan's tail in this case), the numerical differences in the evaluation measures is only modest (in this case less than 1%). (right) an infrequent case, where constrained shape matching fixes the entirely wrong solution delivered by standard matching. The numerical difference in such cases is noticeable (about 6%).

Although it uses the same evaluation metric, the experiment carried out at training time in subsection 6.2 differs substantially from the present one, because at testing time the system is not given ground-truth bounding-boxes. In spite of the important additional challenge of having to determine the object's location and scale in the image, the coverage/precision scores in table 3 are only moderately lower than those achieved during training (table 3; the average difference in coverage and precision is 7.1% and 2.1% respectively). This demonstrates that our detection approach is highly robust to clutter.

As a baseline, table 3 also reports coverage/precision results when using the groundtruth bounding-boxes as shapes. The purpose of this experiment is to compare the accuracy of our method to the maximal accuracy that can be achieved when localizing objects up to a bounding-box. As the table clearly shows, the shapes returned by our method are substantially more accurate than the best bounding-box, thereby proving one of the principal points of this paper. While the average difference is about 35%, it is interesting to observe how the difference is greater for less rectangular objects (swans, giraffes, apple-logos) than for bottles and mugs. Notice also how our method is much more accurate than the groundtruth bounding-box even for giraffes, the class where it performs the worst.

Finally, we investigate the impact of the constrained shape matching technique proposed in subsection 5.3, by re-running the experiment without it, simply relying on the deformation model implicit in the thin-plate spline formulation (table 3, second row). The coverage/precision values are very similar to those obtained through constrained shape matching. The reason is that most cases are either already solved accurately without learned deformation models, or they do not improve when using them because the low accuracy is due to particularly bad edgemaps. In practice, the difference made by constrained shape matching is visible in about one case every six, and it is localized to a relatively small region of the shape (figure 14). The combination of these two factors explains why constrained shape have been computed using the 20%-IoU criterion of [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF]. matching appears to make little quantitative difference, although in many cases the localized boundaries improve visibly.

Detection from hand-drawn models. A useful characteristic of the proposed system is that, unlike most existing object detection approaches, it can take a hand-drawing as a model, as well as training from real images. In the hand-drawing case, the modeling stage simply decomposes the hand-drawing into PAS. Object detection then uses these PAS for the Hough voting stage, and the hand-drawing itself for the shape matching stage. As no deformation model can be learnt from a single example, our method naturally switches to the standard deformation model implicit in the Thin-Plane Spline formulation.

Figure 15 compares our method to [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF] using their exact setup, with a single handdrawing per class as model and all 255 images of the ETHZ shape classes as test set. Our method performs better than [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF] on all 5 classes, especially in the low FPPI range, and substantially outperforms the oriented chamfer matching baseline (details in [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF]).

Beside this quantitative evaluation, our approach offers three additional advantages over [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF]: it can train from real images, it supports branching and self-intersecting input shapes, and it does not need the test image to contain long chains of contour segments around the object (and is therefore more robust).

Interestingly, hand-drawings lead to a moderately better detection results than when learning models from images. This is less suprising when considering that hand-drawings are essentially the prototype shapes the system tries to learn. [START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF] as models.

Conclusions and future work

As confirmed by the experiments, we have proposed an approach capable of learning classspecific explicit shape models from images annotated by bounding-boxes, and then localize the boundaries of novel class instances in the presence of extensive clutter, scale changes, and intra-class variability. In addition, the approach operates effectively also when given hand-drawings as models. Interestingly, the ability to input both images and hand-drawings as training data is a consequence of the fundamental design of our approach, which is meant to bridge the gap between shape matching and object detection.

The presented approach can be extended in several ways. First, the training stage models only positive examples. This could be extended by learning a classifier to distinguish positive and negative examples, which might reduce false-positives. One possibility could be to train both our shape models and the discriminative models of [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF]. At detection time, we could then use the bounding-box delivered by [START_REF] Ferrari | Groups of Adjacent Contour Segments for Object Detection[END_REF] to initialize shape matching based on our models. Moreover, the current method exploits only image contours, discarding valuable information such as texture and color. To further improve discriminative power, the representation could be augmented with appearance features. Finally, our approach assumes that all training objects for a class are seen from approximately the same viewpoint. It would be interesting to add a clustering stage to automatically group objects by viewpoint, and learn separate shape models.

Figure 2 :

 2 Figure 2: Local contour features. a) three example PAS. b) the 12 most frequent PAS types from 24 mug images.

Figure 3 :

 3 Figure 3: Learning the shape model. a) 4 out of 24 training examples. b) Model parts. c) Occurrences selected to form the initial shape. d) Refined shape. e) First two modes of variation (mean shape in the middle).

INRIA

Figure 4 :

 4 Figure 4: Finding model parts. On the left, we show a few training instances with two recurring PAS. On the right, we show four slices of the accumulator space for the upper-L shape PAS type (each slice corresponds to a different size). The two recurring PAS form peaks at different locations and sizes. Our method allows for different model parts with the same PAS type.

Figure 5 :

 5 Figure 5: Occurrences and connectedness. a) A model part (above) and two of its occurrences (below). b) All occurrences of all model parts on a few training images, colored by their confidence (increasing from blue to cyan to green to yellow to red). c) Two model parts with high connectedness (above) and two of their occurrences, which share a common segment (below).

Figure 6 :

 6 Figure 6: Model shape refinement. a) sampled points from the initial model shape. b) after initializing backmatching by aligning the model with the image bounding-box (left), it deforms it so as to match the image edgels (right). c) the first iteration of shape refinement. d) the second iteration.

Figure 7 :

 7 Figure 7: Evolution of shape models over the three stages of learning. Top row: model parts (section 4.1). Second row: initial shape (section 4.2). Bottom row: refined shape (section 4.3).

INRIA

Figure 8 :

 8 Figure 8: a) A challenging test image and its edgemap b). The object covers only about 6% of the image surface, and only about 1 edgel in 17 belongs to its boundaries. c) Initialization with a local maximum in Hough space. d) Output shape with unconstrained TPS-RPM. It recovers the object boundaries well, but on the bottom-right corner, where it is attracted by the strong-gradient edgels caused by the shading inside the mug. e) Output of the shape-constrained TPS-RPM. The bottom-right corner is now properly recovered.

1 )

 1 align Y on x w.r.t. to translation/rotation/scale 2) project Y on the subspace spanned by E 1:n : b = E -1 • (Y -x) , b (n+1):2p = 0 3) bound the first n components of b by ±3 √ λ i 4) transform b back into the original space: Y c = x + E • b 5) apply to Y c the inverse of the transformation used in 1)

  with class-specific shape constraints

Figure 9 :

 9 Figure 9: Three iterations of TPS-RPM initialized as in figure 8c. The image points X are shown in red, and the current shape estimate Y in blue. The green circles have radius proportional to the temperature T , and give an indication of the range of potential correspondence considered by M . This is fully shown by the yellow lines joining all pairs of points with non-zero mai. Top: unconstrained TPS-RPM. Bottom: TPS-RPM with the proposed class-specific shape constraints. The two processes are virtually identical until iteration eight, when the unconstrained matcher diverges towards interior clutter. The constrained version instead, sticks to the true object boundary.

2

  of the affine component d of the TPS from the identity I. The normalization by the determinant of d factors out deviations due to scale changes. 4) the amount of non-rigid warp w of the TPS trace(w T Φw)/r 2 , where Φ(a, b) ∝ ||v av b || 2 log ||v av b || is the TPS kernel matrix [5].

Figure 10 :

 10 Figure 10: A typical edgemap for a Giraffe training window is very cluttered and edges are broken along the animal's outline, making it difficult to learn clean models.

Figure 11 :

 11 Figure11: Learned shape models (three out of total five per class). Top three rows: models learnt using the full method presented in section 4. The first 5 columns show models learned from the ETHZ shape classes dataset, while the last column models from the INRIA horses dataset. Last row: models learnt using the same training images used in row 3, but skipping the procedure for assembling the initial shape (subsection 4.2; done only for ETHZ shape classes).

  . PAMI 08 (PASCAL) Full system (20% IoU) Full system (PASCAL) Hough only (PASCAL) Ferrari et al. PAMI 08 (20% IoU)

Figure 15 :

 15 Figure 15: Object detection performance (hand-drawn models). To facilitate comparison, all curves

INRIA

Figure 16 :

 16 Figure 16: Example detections. Results are based on hand-drawings from[START_REF] Ferrari | Object Detection with Contour Segment Networks[END_REF] as models.

Table 1 :

 1 Number of training images and of positive+negative test images for all datasets.

		apple-logo	bottle	giraffe	mug	swan	INRIA
	Training	20	24	44	24	16	50
	Test	20+215	24+207	43+167	24+207	16+223	120+170

Table 2 :

 2 Accuracy of learned models. Each entry is the average coverage/precision over trials and training instances.

	INRIA

Table 3 :

 3 Accuracy of localized object boundaries at test time. Each entry is the average coverage/precision over trials and correct detections at 0.4 FPPI.

	INRIA

RR n°6600