V Ferrari

L Fevrier

F Jurie

C Schmid

Groups of Adjacent Contour Segments for Object Detection

Keywords: Local features, shape descriptors, object detection I

We present a family of scale-invariant local shape features formed by chains of k connected, roughly straight contour segments (kAS), and their use for object class detection. kAS are able to cleanly encode pure fragments of an object boundary, without including nearby clutter. Moreover, they offer an attractive compromise between information content and repeatability, and encompass a wide variety of local shape structures. We also define a translation and scale invariant descriptor encoding the geometric configuration of the segments within a kAS, making kAS easy to reuse in other frameworks, for example as a replacement or addition to interest points. Software for detecting and describing kAS is released on lear.inrialpes.fr/software.

We demonstrate the high performance of kAS within a simple but powerful sliding-window object detection scheme. Through extensive evaluations, involving eight diverse object classes and more than 1400 images, we 1) study the evolution of performance as the degree of feature complexity k varies and determine the best degree; 2) show that kAS substantially outperform interest points for detecting shape-based classes; 3) compare our object detector to the recent, state-of-the-art system by Dalal and Triggs [4].

is at the end of an edgel-chain directed towards the other segment (section III). The larger the number k of segments in a kAS, the more complex the local shape structures it can capture. 1AS are just individual segments, while 2AS include L shapes, and 3AS can form C, F and Z shapes (figures 2, 3). Along with the kAS features, we propose a low dimensional, translation+scale invariant descriptor designed to encode the geometric properties of the segments composing a kAS. . kAS have a several attractive properties. First, as both kAS and their descriptors cover solely short chains of connected segments, they have the ability to cover pure portions of an object boundary, without including clutter edges which very often lie in the vicinity. Second, for a sensible range of k, kAS have intermediate complexity, which makes them detectable repeatably while being informative at the same time. Third, connectedness is a natural grouping criterion to form kAS. It avoids the need for defining a 'grouping scale' or a 'grouping neighborhood' for a segment, and effectively constrains the features to be chains of segments, which are more likely to lie entirely on a boundary. Finally, kAS are complete local invariant features: each has a well defined location and scale, an invariant descriptor, and is detected based only on local properties of a single image. Hence, they can be reused effortlessly in a variety of recognition and image matching frameworks as a replacement or addition to interest points (such as [START_REF] Berg | Shape Matching and Object Recognition Using Low Distortion Correspondence[END_REF], [START_REF] Dorko | Selection of Scale-Invariant Parts for Object Class Recognition[END_REF], [START_REF] Fergus | Object Class Tecognition by Unsupervised Scale-invariant Learning[END_REF], [START_REF] Leibe | Scale-Invariant Object Categorization Using a Scale-Adaptive Mean-Shift Search[END_REF], [START_REF] Tuytelaars | Matching Widely Separated Views based on Affine Invariant Regions[END_REF]).

We demonstrate the power and flexibility of kAS within an object detection framework which brings together several successful ideas presented before. Following the 'bag of features' paradigm [START_REF] Csurka | Visual Categorization with Bags of Keypoints[END_REF], [START_REF] Jurie | Creating Efficient Codebooks for Visual Recognition[END_REF], [START_REF] Zhang | Local Features and Kernels for Classification of Texture and Object Categories: a Comprehensive Study[END_REF], we construct a codebook of kAS types, each capturing a different kind of local shape structure (figures 2 and 3). An image window is subdivided into tiles [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF] and each is described by a separate bag of kAS. In this fashion the window representation is composed of several bags of kAS spatially localized within the window. Adding this layer of spatial organization improves the discriminative power compared to a standard orderless bag of features over the entire window. We first train a classifier from example object and background windows, and then localize previously unseen instances in test images via a multi-scale slidingwindow mechanism [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], [START_REF] Viola | Rapid Object Detection using a Boosted Cascade of Simple Features[END_REF] coupled with the classifier. Our method is rendered computationally efficient by organizing all image kAS in an Integral Histogram [START_REF] Porikly | Integral Histogram: A Fast Way to Extract Histograms in Cartesian Spaces[END_REF], which is a recently developed datastructure supporting the rapid computation of multidimensional histograms.

During an extensive evaluation, involving eight diverse object classes and over 1400 images [START_REF] Jacobs | Robust and Efficient Detection of Salient Convex Groups[END_REF] DRAFT (section VI), we study several aspects of kAS. First, we analyze the object detection performance while varying k, thereby shedding light on the relation between repeatability and informativeness as k increases. Second, for each k, we vary the resolution of the window tiling, allowing to observe the trade-off between adding localization information and reducing tolerance to spatial variations within the class. Interestingly, we find the optimal window tiling to relate to the complexity of the features (k), with simpler features preferring finer tiling. Moreover, we thoroughly compare the performance of kAS against interest points, and against the state-of-the-art object detection technique by Dalal and Triggs [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF]. Their work is particularly relevant because it follows a similar detection framework (sliding-windows, tiles), but it applies different descriptors to the window tiles (simpler histograms of gradient orientations). Finally, we experiment with the application of kAS with different k at the same time, and with the combination of interest points and kAS.

II. RELATED WORKS

In the following we first review object detection techniques based on contour features, for which kAS offer an alternative, and then present works on the perceptual grouping of contours, upon which kAS build.

Contour features for object class detection: Selinger and Nelson [START_REF] Selinger | A Cubist Approach to Object Recognition[END_REF] detect key curves:

long segments of an edgel-chain bounded by two high curvature points. A key curve's size and orientation defines a square image patch, which is then described using all edgels falling within it. These edge patches attempt to strike a winning trade-off: be local, and hence bring robustness to occlusion and clutter, while also complex enough to be distinctive to some degree, enabling to match individual features, and opening the door to computationally efficient indexing schemes.

However, for key curves lying on the object boundary, these patches will include nearby clutter edgels, which corrupt their descriptors and makes them difficult to put in correspondence.

Selinger and Nelson's recognition system was demonstrated in controlled laboratory conditions, with clean images containing modest amounts of clutter, and mostly on the task of recognizing specific objects. Jurie and Schmid [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF] were among the first to propose local contour features for the detection of object classes, and to test their system on real, cluttered images.

Their scale-invariant feature detector responds to circular arcs of edgels, which are described by the spatial distribution of points in a thin annular neighborhood of the circle. This attempts April 9, 2007 DRAFT to exclude clutter from the descriptor by avoiding encoding points inside the circle. As one limitation, circular arcs only cover a fairly restricted class of shapes.

In their very recent works, 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] independently propose to construct contour fragments tailored to a specific class. The idea is to explicitly construct fragments to occur frequently in positive training images of a class, while seldom in negative ones. Both works employ boosting to select fragments from a large pool of candidates, but differ in the way these candidates are constructed (random rectangles sampled from training segmentation masks in [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF], whereas [START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF] grows fragments starting from random contour points, and optimizes their length so as to maximize Chamfer matching score and accuracy of object centroid prediction in validation images). Although they can be more discriminative for the learned class, these kind of fragments are harder to reuse within other recognition or image matching frameworks, compared to generic features which depend only on local properties of individual images. Moreover, the fragments of [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF], [START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF] are not scale-invariant, and those of [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] need segmented training images to be learned, which further limits their applicability. location and scale. Hence, they need to be associated to some external feature detector before being applicable within frameworks not based on sliding-windows.

Perceptual grouping: Perceptual grouping of contours has a long history in computer vision [START_REF] Estrada | Perceptual Grouping for Contour Extraction[END_REF], [START_REF] Jacobs | Robust and Efficient Detection of Salient Convex Groups[END_REF], [START_REF] Lowe | Perceptual Organization as a Basis for Visual Recognition[END_REF], [START_REF] Lowe | Three-Dimensional Object Recognition from Single Two-Dimensional Images[END_REF], [START_REF] Rothwell | Driving Vision by Topology[END_REF], [START_REF] Rothwell | Planar Object Recognition Using Projective Shape Representation[END_REF], [START_REF] Shashua | Structural Saliency: The Detection of Globally Salient Structures Using a Locally Connected Network[END_REF], [START_REF] Zerroug | Volumetric Descriptions from a Single Intensity Image[END_REF]. The idea behind these works is that pieces of contour related by some perceptually salient property are more likely to belong to the same object. The perceptual properties exploited include convexity [START_REF] Jacobs | Robust and Efficient Detection of Salient Convex Groups[END_REF], co-circularity [START_REF] Zerroug | Volumetric Descriptions from a Single Intensity Image[END_REF],

connectedness [START_REF] Rothwell | Planar Object Recognition Using Projective Shape Representation[END_REF], [START_REF] Shashua | Structural Saliency: The Detection of Globally Salient Structures Using a Locally Connected Network[END_REF], parallelism [START_REF] Lowe | Three-Dimensional Object Recognition from Single Two-Dimensional Images[END_REF], and proximity [START_REF] Lowe | Three-Dimensional Object Recognition from Single Two-Dimensional Images[END_REF].

One major area of application for perceptual grouping is image segmentation, in which the task is to group together all elements belonging to individual, unspecified objects [START_REF] Estrada | Perceptual Grouping for Contour Extraction[END_REF], [START_REF] Jacobs | Robust and Efficient Detection of Salient Convex Groups[END_REF], [START_REF] Zerroug | Volumetric Descriptions from a Single Intensity Image[END_REF].

Moreover, perceptual grouping played an important role in the recognition of specific objects under varying viewpoint, particularly in the 80s and 90s. The focus was mainly on planar objects [START_REF] Rothwell | Planar Object Recognition Using Projective Shape Representation[END_REF] and polyhedra [START_REF] Gros | Matching and Clustering: Two Steps Toward Automatic Object Modeling in Computer Vision[END_REF], [START_REF] Lowe | Three-Dimensional Object Recognition from Single Two-Dimensional Images[END_REF].

The kAS features are motivated by the same general intuitions of earlier perceptual grouping works, and are most related to the ideas of Rothwell [START_REF] Rothwell | Driving Vision by Topology[END_REF], [START_REF] Rothwell | Planar Object Recognition Using Projective Shape Representation[END_REF], who advocated for the importance of connectedness and topological relations. We believe that connectedness is a fundamental, powerful driving force which is currently still underexploited in computer vision. In this paper, connectedness is brought to the domain of object class detection, and is exploited to define modern local invariant features: image elements with a well defined location, a scale and an invariant descriptor, ready to be used in many recent matching and recognition schemes.

III. k ADJACENT SEGMENTS (kAS)

A. Contour Segment Network

We summarize here the technique of [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF] to build the contour segment network (CSN) of the image, on which we will detect our kAS features. Edgels are detected by the excellent Berkeley natural boundary detector [START_REF] Martin | Learning to Detect Natural Image Boundaries Using Local Brightness, Color, and Texture Cues[END_REF], and then chained. The resulting edgel-chains are linked at their discontinuities, i.e. two edgel-chains c 1 and c 2 are linked if c 2 passes near an endpoint of c 1 , and if the ending of c 1 is directed towards c 2 (figure 1b). Informally, if c 1 were extended a bit, it would meet c 2 . These links are useful in two ways: they record that a contour might continue over the gap between two edgel-chains, and allow to capture junctions (L-junctions, T-junctions, and higher order junctions involving several edgel-chains). The edgel-chains are partitioned into roughly straight contour segments. The idea is to organize these segments in a network, by connecting them along the edgel-chains, and across their links (figures 1a and 1c). Since every edgel-chain can be linked to several others, the CSN is a complex branching structure. Intuitively, two segments are connected if the edgels provide evidence that they might be adjacent along some object contour, even when they are physically separated by a (small) gap, or when forming a junction. The key property of the CSN is to include paths going along the contours of the imaged objects [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF], which motivates kAS features.

B. Detecting kAS

The principal contribution of this paper is to propose a family of local features: paths of length k through the CSN. More formally, a group of k segments is a kAS iff they can be ordered so [START_REF] Jacobs | Robust and Efficient Detection of Salient Convex Groups[END_REF] DRAFT that the i-th segment is connected in the CSN to the (i + 1)-th one, for i ∈ {1, k -1}. Hence we call them k adjacent segments, and refer to their length k as degree. As k grows, kAS can form more and more complex local shape structures: individual segments for k = 1; L shapes and 2-segment T shapes for k = 2; C, Y, F, Z shapes, 3-segment T shapes, and triangles for k = 3 (figures 2, 3). The dimensionality of kAS descriptors also grows with k (next section), and we treat kAS of different degrees as different feature types, all united in one family by a shared crucial property: to be sequences of connected segments.

Connectedness provides a natural criterion for grouping segments into kAS. It avoids arbitrary definitions of the neighborhood of a segment, and constrains kAS to be chains of segments.

Compared to the broader class of groups of 'nearby' segments, they have higher chances to lie entirely on a portion of the object boundary. In constrast, the features of [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF] include disconnected sets of edgels which happen to be located along part of a circle. The key curves of [START_REF] Selinger | A Cubist Approach to Object Recognition[END_REF] are based on individual edgel-chains, and hence are less robustly detected in real images than kAS, which bridge gaps between edgel-chains.

kAS can be detected by a depth-first search started from every segment, followed by the elimination of equivalent paths (two different paths involving the same segments constitute the same kAS). This is computationally cheap for the small values of k corresponding to local features (about k ≤ 4). We disregard higher values of k because they result in large-scale structures, too specific to a particular image or object instance, and in an excessive number of detected features (several thousands already for k = 5). More precisely, the number of kAS in an image containing n segments grows quickly with k, as can be understood by the following observations. On average, each segment is connected to two to three others, because T and higher-orders junctions occur less frequently than simple 1-to-1 connections. As a consequence, as k grows, the number of paths of length k passing through a given branching point increases quickly. In practice, while the average number of 2AS is only about

C. Describing kAS

In order to compare different kAS, we need a numerical descriptor. As first step, it is important to order the kAS segments {s i } i=1..k in a repeatable manner, so that similar kAS have the same order. We select as first segment the one with midpoint closest to the centroid of all midpoints

{m i = (x i , y i )} i=1.
.k (when several segments have similar distances to the centroid, we pick the first one according to the order defined below). As we will see in the descriptor below, this centermost segment is the natural choice as reference point for measuring the relative location of the other segments. The remaining segments take up positions 2 through k, and are ordered from left to right, according to their midpoint. If two segments s i , s j have similar x coordinate, i.e.

|x i -x j | ≤ 0.2 (x i -x j ) 2 + (y i -y j ) 2
, then they are ordered from top to bottom. Note that this order is stable, as no two segments can have similar location in both x and y. Example orderings can be seen in figure 1c-e.

Once the order established, a kAS is a list P = (s 1 , s 2 , . . . , s k ) of segments. Let r i = (r x i , r y i ) be the vector going from the midpoint of s 1 to the midpoint of s i . Furthermore, let θ i and l i = s i be the orientation and length of s i respectively. The descriptor of P is composed of 4k-2 values1 (figure 1f):

r x 2 N d , r y 2 N d , . . . , r x k N d , r y k N d , θ 1 , . . . , θ k , l 1 N d , . . . , l k N d (1)
The distance N d between the two farthest midpoints is used as normalization factor, making the descriptor scale-invariant (hence, both the kAS features and their descriptors are scale-invariant).

While segment lengths are known to be often inaccurate, and each is based only on part of the kAS, the distance between the farthest midpoints makes a better choice for a reliable estimate of the kAS scale. In addition to a kAS scale, we also define its location to be the geometric center of the midpoints of its segments. Exact definitions of scale and location are useful when using kAS in higher level algorithms, such as in our sliding-window object detection scheme (next sections).

The proposed descriptor considers the segments as completely straight, so as to capture only the relevant information of the geometric configuration they form, and not the unreliable details of the weak curvature along them. Moreover, we stress that only the k segments are described, and not other nearby edgels. In this fashion, we can cleanly encode a portion of an object boundary, without including inner/outer clutter (unlike [START_REF] Selinger | A Cubist Approach to Object Recognition[END_REF]).

With its 4k -2 dimensions, the descriptor is also very compact. Indeed, since the intrinsic dimensionality of k straight segments is 4k, and the dimensionality of the desired scale+translation invariance space is 3, the lowest dimensionality of a complete descriptor is 4k -3. The only redundant degree of freedom we encode is embedded within the relative location vectors {r i } i=2..k .

Factoring it out would require representing them in a more complicated way 2 .

Interestingly, the kAS descriptor is of different nature than conventional local textured feature descriptors. While the latter encode the appearance of the pixel patch covered by the feature, the kAS descriptor encodes the geometric properties of the segments (orientation and length), and of their spatial arrangement ({r i } i=2..k ).

If desired, the descriptor can be easily made rotation-invariant, at the cost of some distinctiveness. In addition, for k ≥ 3 one can design descriptors with even higher degrees of invariance (affine, projective) to be used, e.g. for wide-baseline stereo [START_REF] Tuytelaars | Matching Widely Separated Views based on Affine Invariant Regions[END_REF], although we do not investigate this possibility further in this paper.

The orientation and lengths of all segments in a kAS can be reconstructed from the kAS descriptor and scale. In addition, the exact segment locations can be reconstructed by storing also the difference between the kAS' location and the midpoint of s 1 . This might be useful, e.g.

for synthesizing kAS for visualization.

D. Comparing kAS

We define here a measure D(a, b) of the dissimilarity between two kAS P a , P b of the same complexity k

D(a, b) = w r k i=2 r a i -r b i + w θ k i=1 D θ θ a i , θ b i + k i=1 log l a i /l b i (2)
2 One way of designing a minimal descriptor is to choose N d = l1 as scale normalization factor, and removing l1 from the descriptor. However, the length of a segment is often inaccurately determined. Moreover, basing the scale normalization on a single segment is a less stable choice for the overall scale of the kAS than the distance between the farthest midpoints (which spans the whole kAS).

April 9, 2007 DRAFT

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 summation accounts for the difference in lengths. As segment lengths are often inaccurate, we give higher weight to the two other terms of the comparison measure: in all our experiments w r = 4, w θ = 2. All r i and all lengths are normalized as in equation ( 1). [6], [START_REF] Jurie | Creating Efficient Codebooks for Visual Recognition[END_REF], [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF], [START_REF] Leibe | Scale-Invariant Object Categorization Using a Scale-Adaptive Mean-Shift Search[END_REF],

For clustering we use a clique-partitioning (CP) approach. Let G be a complete graph whose nodes are the training kAS, and arcs are weighted by d -D(a, b). We partition G into cliques so as to maximize the sum of intra-clique weights, using the clique-partitioning approximation algorithm of [START_REF] Ferrari | Real-time Affine Region Tracking and Coplanar Grouping[END_REF]. Each resulting clique is a cluster of similar kAS.

The choice of CP instead of K-means, commonly used for building visual codebooks, is appropriate in our context where the dissimilarity measure D makes the descriptor space circular (D θ terms). Moreover, the parameter d is easy to set, because it represents a rough indication of the acceptable intra-cluster dissimilarity (akin to the kernel-width in mean-shift clustering [START_REF] Jurie | Creating Efficient Codebooks for Visual Recognition[END_REF]).

K-means instead requires the number of clusters as input, which is unknown apriori and varies from dataset to dataset. Several experiments indicate that the exact choice of d has little impact on the overall system performance (section VI).

For each cluster, we select as a representative the kAS with the lowest sum of dissimilarities to all others (i.e. the one closest to the cluster center). The final codebook C is the collection of these representative kAS, the kAS types.

When constructing codebooks from different image sets, we observed that the kAS types occurring with a significant frequency were very similar. This confirms the intuition that kAS are generic features (certainly for the low values of k we consider). Hence, for each k we build a single codebook from 10 images and use it for all object classes in our experiments (section VI).

Figure 2 shows the 35 most frequent types in the 2AS codebook. As we can see, they have quite natural shapes: two collinear segments, L structures, and small T-junctions. Figure 3 displays the 35 most frequent 3AS types. They form more complex structures than 2AS: C, Y, F, Z shapes, larger T shapes, and triangles.

V. OBJECT CLASS DETECTION

In this section we present a scheme for detecting objects based on kAS. We first train a classifier to distinguish windows covering objects of a certain class from any other window, and then apply it for localizing novel instances in previously unseen test images, based on a sliding window mechanism. As in many of the existing approaches, we build a detector for a single viewpoint.

April 9, 2007 DRAFT When computing the kAS histograms, rather than assigning each kAS to the single closest type, it is soft-assigned to all types within dissimilarity d (same as in section IV). More precisely, each kAS P distributes a total sum P s among the types it is assigned to, in inverse proportions to the dissimilarity to the types' representative kAS. This makes the representation of a window less sensitive to the exact shape of the kAS it contains, and to the exact codebook types. This leads to smoother models, which better generalize to novel object instances, and to a more accurate, stable evaluation of test image windows (next subsection). In addition to a kAS' shape, we also consider its relevance: the total contribution of kAS P to a histogram is the average strength of its edgels P s ∈ [0, 1]. We experimentally observed a considerable improvement 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 by Contour Segment Networks[END_REF]).

Our window descriptor is a valuable choice for object class detection. It is distinctive, because it records which local shape structures (kAS) it contains, and roughly where they appear. At the same time, it is flexible thanks to the coarse tiling, and the continuous assignment of kAS to April 9, 2007 DRAFT types. Much of the power of our representation comes from organizing the image edges over two levels of spatial arrangements: contour segments within the kAS, and then the kAS within the overall object.

As the tiling resolution T increases, the spatial localization of kAS grows stronger, resulting in a more informative descriptor, but also a more rigid one, accommodating for less spatial variability of the class. Hence, there should be some optimal T , bringing the best trade-off between accuracy of localization information and tolerance to intra-class variation. Interestingly, our experiments show the optimal T to decrease with increasing k (section VI). With k = 1

the features are so uninformative that the window descriptor needs to be augmented with finegrained localization to be distinctive. While k grows, kAS become more complex, and the added value of localization gradually diminishes. In addition, we found the optimal T for interest points described by SIFT to be lower than that of any kAS we explored (k ≤ 4). Since SIFT descriptors of an image patch are richer features (and have a descriptor of much higher dimensionality), this further confirms the above subtle relation between feature complexity and localization resolution. object elements might be extremely simple (like the straight line on top of a comb, for which k = 1 is good), while others might be more sophisticated local structures (like a C-shaped mug handle, for which k = 3 is good). Hence, using multiple degrees simultaneously offers the SVM a larger, more diverse pool of parts to choose from.

B. Testing

Having trained a linear SVM window classifier, we can detect and localize novel object instances in a test image using a simple sliding-window mechanism [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], [START_REF] Viola | Rapid Object Detection using a Boosted Cascade of Simple Features[END_REF]. We slide a window of aspect-ratio M w /M h over the image at multiple scales 3 , compute the window descriptor at each location/scale and evaluate it with the SVM. This provides a 3D response map, whose local maxima give candidate object detections. The final set of detections are obtained after a last polishing: if two candidate detections overlap considerably, we filter out the weaker one.

This sliding window technique requires computing the histogram of kAS types within a large number of image windows (tiles). We achieve this efficiently by using an Integral Histogram [START_REF] Porikly | Integral Histogram: A Fast Way to Extract Histograms in Cartesian Spaces[END_REF] representation (IH). After building an IH where each dimension corresponds to a kAS type, it is possible to compute the histogram of kAS types in any window in 3|C| operations, independently of the total number of kAS in the image and of the number of kAS in the window. The cost 3 This is implemented simply by resizing the window to contain a varying portion of the image. It is not necessary to rescale the image, because the kAS features themselves automatically adapt to image structures of different scales. Although the kAS features are scale-invariant, we need to search over different window sizes to properly detect the object whose size in the image is unknown. In all our experiments the sliding step is 10 pixels is each direction, while the scale step is 2 . We consider all scale levels where the window's longer side is more than 50 pixels and still fits in the image. April 9, 2007 DRAFT of building the kAS IH is low 4 . Moreover, it is done only once for an image (as we adopt a single codebook for each k). A substantial share of the cost is computing the soft-assignments of the image kAS to types, which must be done in any case.

Our object detection procedure is very fast. After preprocessing (from edge detection to the kAS IH), it takes about 1 second to detect all instances in our C++ implementation on a standard workstation. Preprocessing takes longer, due the accurate, but slow, Berkeley edge detector (a few minutes). However, it only needs to be done once, so the cost is amortized when searching for several classes, or when using kAS of multiple degrees at the same time.

The main reason for preferring the Berkeley detector over the traditional Canny detector, is the inclusion of texture and color segmentation cues, in addition to brightness. Moreover, it treats edge detection as a pixel classification problem and trains a classifier from natural images with human-annotated boundaries. This results in less clutter edgels inside textured areas, and longer, smoother boundaries around textured objects (e.g. giraffes). Using this detector instead of Canny in our framework trades better object detection performance for higher preprocessing time. An exciting alternative is the very fast edge detector recently published by Dollar et al. [START_REF] Dollr | Supervised Learning of Edges and Object Boundaries[END_REF]. It performs as well as the Berkeley detector while taking mere seconds for an image, but is unfortunately not yet publicly available at the time of this writing. The release of this edge detector will enable our object detector to process an image from scratch in a few seconds.

VI. EXPERIMENTAL EVALUATIONS

A. Datasets and protocol

We present extensive experimental evaluations, involving several existing datasets covering 8 diverse shape-based object classes, for a total of more than 1400 test images. Here we briefly introduce these datasets, while the following sections report the experiments.

INRIA horses [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF]: This challenging dataset consists of 170 images containing one or more horses, seen from the side, and 170 images without horses. Horses appear at several scales, and against cluttered backgrounds (figure 8). We employ the first 50 positive and 50 negative images for training, and the remaining 120 + 120 images for testing. This dataset plays a special role in our evaluations, as we optimize the two free parameters of our detection system on it (the window tiling resolution T and the clustering threshold d).

The optimal setting established on this dataset is then used on all others. No tuning is applied to any other dataset, so the exact same system is run on all datasets.

Weizmann-Shotton horses [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]: Shotton et al. [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] propose another horse detection dataset, composed of 327 positive images containing exactly one horse each, and 327 negative images.

The positive images are derived from a dataset previously released by the Weizmann Institute for evaluating image segmentation algorithms [START_REF] Borenstein | Combining Top-down and Bottom-up Segmentations[END_REF]. In order to carry out proper comparisons, we follow the protocol of [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] strictly by using their scale-normalized images, and running our system at a single scale by sliding a window of fixed dimensions M w × M h . 5 . As in [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF], the first 50 positive and 50 negative images are used for training, the other 277 + 277 for testing (figure 8).

ETHZ shape classes [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF]: This dataset features five diverse classes (bottles, swans, mugs, giraffes, apple logos), containing a total of 255 images collected from the web by Ferrari et al. [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF]. It is the most challenging dataset we report on, as the objects appear in a wide range of scales, there are considerable intra-class shape variations, and many images are severely cluttered, with the objects comprising only a fraction of it (figure 10).

We train one detector per class, using the first half of the available positive images (there are 40 for apple-logos, 48 for bottles, 87 for giraffes, 48 for mugs, and 32 for swans). As negative training images, an equal number is taken, with each of the other 4 classes contributing 1/4 of them. For example, the training images for the bottle detector are 24 bottle images, plus 6

images from each of the other classes, totaling 24 negative training images. All other images are used for testing, so each class is searched for in images from every class.

Caltech 101 [START_REF] Fei-Fei | Learning Generative Visual Models from Few Training Examples: an Incremental Bayesian Approach Tested on 101 Object Categories[END_REF]: The last source of data we consider are three shape-based classes from the well-known Caltech-101 database [START_REF] Fei-Fei | Learning Generative Visual Models from Few Training Examples: an Incremental Bayesian Approach Tested on 101 Object Categories[END_REF]: anchors, chairs, and cups (42, 62, 57 positive images respectively). Although most images contain only limited clutter, the dataset offers substantial intra-class variation (figure 10). As for the ETHZ shape classes, we evaluate one class at a time.

We use the first half of the positive images for training, as well as an equal number of negative images from the Caltech-101 background set. The test set consists of the remaining positive images, plus the same number of negative ones.

Evaluation criterion: Performance is evaluated by plotting detection-rate (DR) versus the incidence of false-positives (false-positives per image, FPPI) while varying the detection threshold. We prefer these DR/FPPI plots over precision/recall ones for several reasons. FPPI has a clearer interpretation than precision, which is entangled with detection-rate. Moreover, FPPI is independent of the number of negative test images, and DR/FPPI plots are easier to read, because they increase monotonically.

Comparisons between different methods is mainly based on two points on the DR/FPPI plot, at 0.3 and 0.4 FPPI. These are especially relevant because they correspond to a rather low, but not extremely low, FP rate (around 1 FP every 3 images). Only on the Shotton horses dataset we report precision/recall plots, and compare methods based on equal-error rates, because [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] published their results in that form 6 . Hence, average detection-rates at a particular FPPI rate refer to means computed over 9 datasets, excluding Shotton horses.

For all datasets and methods, a detection is counted as correct if its bounding-box overlaps more than 20% with the ground-truth bounding-box, and vice-versa. Any other detection is counted as a false-positive. This is the criterion used in [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF], which provides 5 of the 10 considered datasets. In section VI-G we also report performance under the PASCAL criterion [START_REF]PASCAL Challenge 2006 Visual Object Classes[END_REF].

B. Degree of complexity of kAS

Impact of tiling and clustering threshold: Before comparing the performance of kAS of different degrees of complexity on all 10 datasets, we first optimize T, d for each k separately on the INRIA horses dataset (k ∈ {1, 2, 3, 4}). For several pairs of T, d, we reprocess the dataset and obtain a DR/FPPI curve. Figure 7 shows the impact of the tiling resolution, while keeping d fixed at the optimum. From the plots it clearly appears that subdividing the window into tiles makes a substantial difference for all k. Compared to a single bag-of-feature representation (no tiles), at 0.3 FPPI the optimal tiling brings improvements ranging from 20% (k = 1) to 13% (k = 4) detection-rate.

It is intriguing to observe that the optimal value of T decreases with increasing k. This confirms experimentally the subtle relation discussed in section V-A: as the features grow more complex and hence informative, a coarser spatial localization is sufficient, while at the same time a lower T yields better tolerance to intra-class variations. Individual segments benefit most from a very fine subdivision of 90 tiles, whereas the saturation point for localization information is already reached at 20 tiles for 3AS. Moreover, also the gain brought by tiling reduces as the features become more complex, because the added value of localization gradually diminishes (at 0.3 FPPI, it is of 20%, 16%, 16%, 13% detection-rate for k=1,2,3,4 respectively).

Varying the clustering threshold d has a smaller impact. Nevertheless, we observe the number [START_REF] Jacobs | Robust and Efficient Detection of Salient Convex Groups[END_REF] DRAFT of clusters corresponding to the optimal d to increase with k (4, 127, 255, 397 for k = 1, 2, 3, 4

respectively). This makes sense, because as the features becomes more complex, they can assume a wider variety of shapes. In particular, just 4 clusters are necessary for k = 1, corresponding roughly to four orientations separated by 45 degrees.

Following these observations, all further experiments are performed with the optimal parameters T, d for every k.

Degree k: We applied our object detection scheme to all 10 datasets, for the four degrees of kAS complexity we explore (k ∈ {1, 2, 3, 4}). Although there is no single degree producing the best results on all datasets, 2AS perform best overall (figure 9). The 2AS plot is above all others on 5 datasets, and its average detection-rate at 0.3 FPPI is 76.7%, versus 69.4%, 64.1%, 56.5% of 1AS, 3AS, 4AS respectively (table III). Hence, we conclude that 2AS are the kAS with the best intermediate complexity, offering the optimal compromise between being informative, repeatable, and generating a good ratio of pure boundary features versus mixed/clutter features (as discussed in subsection III-B). In the remainder of the paper, 2AS is the reference kAS for comparison to other methods, and will be referred to as P AS (pairs of adjacent segments).

Table III shows that by ranking kAS according to average detection-rate at 0.3, or 0.4 FPPI, the following order appears: 2AS > 1AS > 3AS > 4AS. This ranking is well confirmed by the overall relative heights of the DR/FPPI plots (clearest on mugs, applelogos). Surprisingly, the second best kAS are individual segments. Much of the reason is in the great impact of tiling on 1AS, where very fine-grained localization compensates for the feature's lack of distinctiveness (figure 7). Nevertheless, P AS do better, confirming it's advantageous to consider groups of April 9, 2007 DRAFT connected segments as features for object detection. Moreover, P AS, as well as kAS of higher degrees, are more reusable in other systems, where the discriminative power of individual features is more important, or where a feature correspondence must generate a higher order transformation than just translation (e.g. recognition systems using feature transformations [START_REF] Fergus | Object Class Tecognition by Unsupervised Scale-invariant Learning[END_REF], [START_REF] Leibe | Scale-Invariant Object Categorization Using a Scale-Adaptive Mean-Shift Search[END_REF], or for matching features between two images [START_REF] Mikolajczyk | Indexing Based on Scale Invariant Interest Points[END_REF], [START_REF] Tuytelaars | Matching Widely Separated Views based on Affine Invariant Regions[END_REF]).

In absolute performance terms, P AS work consistently well on all classes (detection-rates between 79% and 88% at 0.4 FPPI), with the exception of swans. This is especially remarkable when considering the low number of positive training images used in many datasets (e.g. 24 for bottles, see table I). P AS achieve particularly high performance on Shotton-horses, with 91.7%

precision-recall equal error-rate , in line with the state-of-the-art approach [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] (92.1%) 7 . 1AS

does even better, with 93.5%. Moreover, in contrast to their work, our method does not need any segmented training image (only bounding-boxes), and can detect objects at multiple scales.

The striking performance of 1AS on this dataset (the only one where they beat P AS) might be explained by the very low resolution of the images (horses are about 100 pixel wide), which favors simpler features.

We can also draw a loose comparison to [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF], on the INRIA horse dataset. Numerically, the performance of PAS is close to their work (e.g. PAS do 70.0% at 0.066 FPPI, which corresponds to 86.1% precision, while [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF] reports 70.4% recall at 87.7% precision). However, an accurate comparison is not possible, because the authors of [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF] have lost details of the particular test set on which results were reported. We adopt here the official release of the dataset, which should come quite close. As a reference, we also mention that [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF] obtains a similar level of performance as PAS on the ETHZ shape classes, although the two methods are not directly comparable since [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF] inputs hand-drawings as models.

In order to further strengthen our understanding of PAS performance, and properly set it in the context of alternative methods, in the following we perform an in-depth comparison to interest points, used within our object detection framework, and to the system of Dalal and Triggs [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF].

C. Comparison to interest points

Interest point (IP) detectors respond to local pixel patterns with certain special properties (e.g. cornerness) and produce local features widely used for object class detection [START_REF] Dorko | Selection of Scale-Invariant Parts for Object Class Recognition[END_REF], [START_REF] Fergus | Object Class Tecognition by Unsupervised Scale-invariant Learning[END_REF], [START_REF] Leibe | Scale-Invariant Object Categorization Using a Scale-Adaptive Mean-Shift Search[END_REF]. IP descriptors capture the appearance of the image patches surrounding them. In order to support the claim that kAS are better suited to represent shape-based classes, we replace them by IPs in our object detection framework, and reprocess all 10 datasets. We experiment with three of the most widespread scale-invariant IPs: Harris-Laplace [START_REF] Mikolajczyk | Indexing Based on Scale Invariant Interest Points[END_REF], LoG [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF], and DoG [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF]. All IPs are described by the extremely popular 128-dimensional SIFT [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF].

Codebooks, tiling, and number of clusters:

The number of IP per image is about 1000 to 2000, larger than that of kAS (for k ≤ 4). In addition, we want to experiment with IP codebooks built from more than the 10 images used for kAS (details below). As a result, the total number of IPs to be clustered can grow beyond what CP can handle. Since CP builds a pairwise dissimilarity matrix, memory consumption limits the number of features to about 15000, while in several cases there are more than 50000 IPs. Hence, we build IP codebooks using k-means. Notice how the CP parameter d is now replaced by explicitly providing the number of clusters.

As done before for kAS, we optimize the number of tiles and of codebook clusters on INRIA horses (figure 11). The selected optimal T is 10, which confirms the trend observed on kAS: the richer the feature, the lower the value. Figure 11 shows the evaluation on Harris-Laplace, but similar optimal values are obtained for DoG or LoG.

The rationale behind using a single kAS codebook from a small set of 10 images is that the features are simple and generic enough. However, this might not hold for IPs. Since they are based on texture, and the SIFT descriptor captures an entire image patch, quite different codebooks might result from different image sets (e.g. giraffes versus horses). Therefore, we experimented with three kinds of codebooks, on the five ETHZ shape classes. The first is computed from the same 10 images used for kAS, the second is specific to a single class (computed from the same images used to train the SVM), and the last is based on images from all five classes (computed from all images used to train all 5 SVMs). From the results we obtained, it indeed appears that class-specific IP codebooks perform moderately better on average. Hence, all experiments below April 9, 2007 DRAFT which both shape and texture are characteristic, the results of PAS and the best IP are very close (especially in the range 0.3-0.4 FPPI).

Beyond PAS, one can compare kAS in general to IPs. In terms of average detection-rate at 0.3 -0.4 FPPI, all explored kAS do considerably better than any of the tested IPs (table III).

Only the performance levels of 4AS and Harris-Laplace are similar.

Inspecting the data, it is also possible to rank features among IPs. Although no single one works best on all datasets, on average Harris-Laplace stands out, followed by DoG and LoG, which are at about the same level (table III).

In conclusion, these experiments confirm that kAS are more appropriate features than IPs for shape-based classes.

D. Combining multiple kAS degrees

Even though PAS are better than kAS of other degrees on most datasets, 1AS and 3AS win on Shotton horses and anchors respectively. This suggests that using all three 1AS/2AS/3AS simultaneously might give an even better detector.

As explained in section V, we integrate kAS of multiple degrees by concatenating window descriptors computed separately for each k, and then training a single SVM on them. Each degree uses its own codebook and optimal tiling resolution. In this fashion, the SVM can choose from a very large pool of different local shape structures and tiling combinations.

The results can be seen in table II. For most datasets, performance is very similar to PAS. On

E. Combining PAS and Harris-Laplace

Following the approach as in the previous subsection, we have combined PAS and Harris-Laplace, as they are the best members of their respective feature families. This seems an exciting possibility, because PAS and Harris-Laplace exploit complementary image properties (contour and texture). Hence, the hope is to obtain a more generic object detector, which might autonomously determine which kind of feature is more appropriate for (part of) a given object.

The PAS+Harris detector does better than either component alone on giraffes and Shotton horses (table II). This is particularly meaningful since giraffes are defined by both shape and texture, so we expect their combination to reinforce the detector. Moreover, giraffes and Shotton horses are the only two classes on which PAS and Harris-Laplace work about equally well.

PAS+Harris now achieves an impressive 95.7% precision-recall equal-error-rate on Shotton horses. Furthermore, on INRIA horses, chairs, and swans, PAS+Harris exhibit the desired behavior: its performance aligns with the better of either PAS or Harris-Laplace. However, on the remaining 5 classes PAS+Harris only performs somewhere in between PAS and Harris-Laplace.

Again, a probable reason is overfit, and we observe a clear correlation between the performance improvement/loss of PAS+Harris and the number of training images in a class (table I). To confirm this further, we run tests with several randomized splits of the images in training and test subsets, and observed that the performance variations of PAS+Harris are far greater than those of either feature alone.

F. Comparison to Dalal and Triggs [4]

We conclude our series of evaluations by comparing against the object detection technique by Dalal and Triggs [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], which is currently the state-of-the-art in human detection, and has proven very competitive on other classes as well [START_REF]PASCAL Challenge 2006 Visual Object Classes[END_REF]. Like ours, their object detector is based on sliding a window subdivided into tiles, but uses histograms of gradient orientations as descriptors.

In an effort to perform a fair comparison, we discussed with the authors of [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], who recommended the following operations. First of all, we used the official software released by the authors. Moreover, we rescaled all training windows to make the longest side 100 pixels, which April 9, 2007 DRAFT and normalizing descriptors by the square root of the L1 norm (see [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF] for details).

The results are displayed in figure 13 (the system of [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF] is marked as HoG). Our detector achieves a substantially higher performance on 6 of the 10 datasets, while on mugs and cups the two methods are about equally good, and HoG obtains better results on applelogos and swans.

In terms of average detection-rate at 0.3 FPPI, PAS leads with a considerable margin of 20%

(table III).

The HoG curves abruptly stop growing after a rather low FPPI rate, due to the system returning no detection on several images. We tried to counter this by altering a parameter controlling the minimal score for windows to enter the non-maxima suppression stage, but it only resulted in lower curves (as Dr. Dalal also expected, when we asked about this issue). Besides, we observe that explicitly comparing performance at the point where HoG stops growing only makes a difference for cups. PAS still leads on 6 datasets, and give equivalent results on mugs.

In conclusion, our detection system compares favorably to [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF] in our experiments, which further consolidates PAS as excellent features for object detection.

G. Accuracy of detections

So far we adopted the criterion for counting a detection as correct that was used in our previous work [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF] (section VI-A). This is a sensible choice, as most datasets we experiment on were first released in [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF]. However, this criterion is rather loose and it might consider as correct also rather inaccurate detections. In this section, we investigate the performance of our system under the stricter PASCAL criterion: a detection is counted as correct if the area of intersection between its bounding-box and the ground-truth bounding-box exceeds 50% of their union [START_REF]PASCAL Challenge 2006 Visual Object Classes[END_REF].

This allows to understand in how many cases detections are truly accurate, and in how many others they cover the object more loosely.

Since PAS perform better than other kAS and than IPs also under the PASCAL criterion, we focus only on them here. Following the protocol applied before, we re-optimized T and d on INRIA horses for the PASCAL criterion. Interestingly, we found the optimal T = 48 to be higher than that for the criterion [START_REF] Ferrari | Object Detection by Contour Segment Networks[END_REF] (T = 30). This can be explained as a finer tiling enables better localization accuracy, at the cost of some generalization ability. As in the previous evaluations, all 10 datasets are re-processed, keeping all parameters fixed. Detection rates at 0.3 and 0.4 FPPI for all features we tested, as well as for the object detection system of [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF] (marked as HoG). The 'Shotton' column HoG's performance decreases as well in this setting: the average detection-rate at 0.4 FPPI decreases by 8% (from 57.5% to 49.6%). On average over 9 classes, PAS still achieves about 20% higher detection-rate at 0.4 FPPI, and performs substantially better on Shotton horses (91.7% vs 61.2%).

In addition to the above results based on the PASCAL criterion, for the sake of an exact comparison to [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF] we also report results on Shotton horses using their own criterion [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]: a detection is considered correct if its center lies within 25 pixels of the ground-truth center. Under this criterion, our PAS-based detector achieves 89.9% precision/recall EER, which is similar to its performance under PASCAL. Moreover, PAS+Harris, our best detector for Shotton horses, achieves 93.2% EER, which is better than the 92.1% of [START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF].

VII. CONCLUSIONS AND FUTURE WORK

We have introduced the kAS family of local contour features and their application to object detection. kAS are able to cover pure portions of an object boundary, without including nearby spurious edgels. Moreover, they can form a wide variety of local shape structures, combine informativeness and repeatability, and constitute complete, scale-invariant local features ready to April 9, 2007 DRAFT when the localization constraints are weaker or absent and hence the discriminative power of individual features might become more important [START_REF] Berg | Shape Matching and Object Recognition Using Low Distortion Correspondence[END_REF], [START_REF] Dorko | Selection of Scale-Invariant Parts for Object Class Recognition[END_REF], [START_REF] Leibe | Scale-Invariant Object Categorization Using a Scale-Adaptive Mean-Shift Search[END_REF], or when higher degrees of geometric invariance are required (e.g. image matching [START_REF] Mikolajczyk | Indexing Based on Scale Invariant Interest Points[END_REF], [START_REF] Tuytelaars | Matching Widely Separated Views based on Affine Invariant Regions[END_REF]). Besides, since our object detector is restricted to a single viewpoint, it is unclear how well kAS would work in a multiview setting. Finally, effective ways to combine appearance features with kAS remain to be investigated. One option would be to integrate both tightly, by augmenting kAS with appearance information (e.g. by describing color or texture properties on either side of a L-shaped PAS).

VIII. ACKNOWLEDGMENTS

This research was supported by the EADS foundation, INRIA and CNRS. Vittorio Ferrari was funded by a postdoctoral fellowship of the EADS foundation.

Fig. 1 .

 1 Fig. 1. a) An example image, with three 2AS and the underlying CSN connections (arrows). Notice how one 2AS lies entirely on the boundary of a mug. b) Three edgel-chains, with five segments and their inter-connections (arrows) in the network. c) Two detected 2AS (B, C) and (D, E). The order of each segment in the descriptor is marked next to it (see section III-B). Notice that (A, B), (A, C), (C, E) are also detected, though not displayed because they overlap with (B, C) and (D, E). d) 3AS (C, A, E). e) 4AS (E, B, C, D). f) r i vectors involved in the description of the 4AS in d).

Fig. 2 .

 2 Fig. 2. The 35 most frequent 2AS types from the codebook we use in all experiments, constructed from 10 outdoor images (5 positive and 5 negative images from the INRIA horses dataset, section VI). For each cluster, we display the single 2AS with the lowest sum of dissimilarities to all others in the cluster.

Fig. 3 .

 3 Fig. 3. The 35 most frequent 3AS from our codebook.

Fig. 5 .

 5 Figures 5 and 6 show a few kAS automatically selected by the SVM for a few classes (i.e. the 'kAS type + tile' combinations corresponding to the highest weighted window descriptor dimensions). Among the large number of kAS composing each example, several lie on the object boundary, and are picked up by the SVM as local shape structures common to multiple training examples.Using multiple kAS degrees at once.: Our framework includes the possibility of using multiple degrees of kAS at the same time (e.g. 2AS and 3AS). In this case the different sets of kAS are treated separately: there is a codebook and tiling resolution for each value of k. Window descriptors obtained for different k are then concatenated to give a large descriptor which is fed to the SVM.Using kAS of different degrees at the same time is an interesting option. Some characteristic

Fig. 6 .

 6 Fig. 6. One of the descriptor dimensions which are given the highest weight by the SVM (one for each of three classes, with k = 3).

4 2 +

 2 It is O(|C| W ×H r N |C|k), for an image of width W and height H, containing N kAS. r is the spatial resolution of the histogram, with r = 1 being the highest possible. In all our experiment r = 10. O(N |C|k) is the cost of soft-assigning the image kAS to the codebook types. April 9, 2007 DRAFT

Fig. 7 .

 7 Fig. 7. Impact of window tiling resolution T at the optimal clustering threshold d. The optimum is T = 90 for 1AS, T = 30 for 2AS, and T = 20 for 3AS and 4AS.

Fig. 8 .

 8 Fig. 8. Top row: detections at 0.4 FPPI for the INRIA horses dataset. The rightmost image shows a missed detection and a false-positive. Bottom: detections at the equal-error rate for the Shotton horses dataset.

Fig. 9 .

 9 Fig. 9. Performance of kAS, for varying degrees of complexity k. Top row: the two horses datasets: INRIA horses and Shotton horses. Second row: the three classes from Caltech 101. Third row: the five ETHZ shape classes. All performance comparison figures in the paper follow this layout.

Fig. 10 .

 10 Fig. 10. All detections at 0.4 FPPI on some example images. Top 3 rows: ETHZ shape classes. Bottom row: Caltech 101.

Fig. 11 .

 11 Fig. 11. Optimizing T with the number of clusters fixed at 140 (which is the optimum in the tested range 100-300).

TABLE I

 I Number of positive+negative training and testing images for all datasets.

		INRIA	Anchor	Chair	Cup	Applelogo	Bottle	Giraffe	Mug	Swan	Shotton
	Train	50+50	21+21	31+31 29+29	20+20	24+24	44+44	24+24	16+16	50+50
	Test	120+120	21+21	31+31 28+28	20+215	24+207 43+167 24+207 16+223	277+277

  reports recall at equal error-rate for the Shotton horses dataset. It is included here for homogeneity of presentation.The results are reported in table IV. The difference in detection-rate at 0.4 FPPI compared to the previous setting varies largely from class to class: it goes from an improvement of 4% on bottles to a decrease of 28% on giraffes. On average, the detection-rate at 0.4 FPPI moderately decreases by 11% to 70.1%. Besides, on Shotton horses the precision/recall EER remains unchanged at the rate of 91.7%. Hence, over all datasets, the majority of detections does meet the strict standards defined by the PASCAL criterion.For comparison, table IV also reports the performance of HoG under the PASCAL criterion.

	Detection rate	INRIA	Anchor Chair Cup	Applelogo Bottle Giraffe Mug Swan	Shotton
	PAS (0.3 FPPI)	85.4	76.2	78.1	78.6	65.0	89.3	72.3	80.6	64.7	91.7
	1AS (0.3 FPPI)	86.2	85.7	81.2	75.0	55.0	78.6	59.6	67.7	35.3	93.5
	3AS (0.3 FPPI)	79.2	90.5	75.0	71.4	35.0	67.9	61.7	54.8	41.2	90.3
	4AS (0.3 FPPI)	76.9	57.1	71	71.4	30.0	60.7	63.8	41.9	35.3	90.3
	Harris (0.3 FPPI)	63.1	47.6	50.0	42.9	60.0	39.3	70.2	45.2	76.5	91.0
	Dog (0.3 FPPI)	42.3	23.8	53.1	78.6	45.0	17.9	55.3	22.6	47.1	89.2
	Log (0.3 FPPI)	50.8	23.8	31.2	57.1	30.0	25.0	72.3	38.7	58.8	90.3
	{1,2,3}AS (0.3 FPPI)	86.2	76.2	77.4	82.1	70.0	85.7	68.1	80.6	47.1	94.2
	PAS + Harris (0.3 FPPI)	84.6	61.9	83.9	67.9	60.0	57.1	80.9	51.6	82.4	95.7
	HoG (0.3 FPPI)	74.6	9.5	32.3	78.6	85.0	17.9	48.9	80.6	82.4	70.1
	PAS (0.4 FPPI)	87.7	81.0	87.5	82.1	85.0	89.3	78.7	80.6	64.7	91.7
	1AS (0.4 FPPI)	86.9	90.5	84.4	82.1	65.0	85.7	61.7	71.0	58.8	93.5
	3AS (0.4 FPPI)	85.4	90.5	84.4	75.0	40.0	78.6	72.3	64.5	41.2	90.3
	4AS (0.4 FPPI)	80.8	71.4	90.3	78.6	30.0	64.3	68.1	51.6	41.2	90.3
	Harris (0.4 FPPI)	73.8	47.6	62.5	53.6	70.0	39.3	72.3	45.2	82.4	91.0
	DoG (0.4 FPPI)	49.2	28.6	71.9	92.9	45.0	17.9	59.6	29.0	58.8	89.2
	LoG (0.4 FPPI)	56.2	38.1	34.4	60.7	35.0	25.0	74.5	48.4	58.8	90.3
	{1,2,3}AS (0.4 FPPI)	87.7	85.7	87.1	82.1	80.0	85.7	74.5	83.9	58.8	94.2
	PAS + Harris (0.4 FPPI)	87.7	71.4	90.3	75.0	75.0	64.3	80.9	64.5	82.4	95.7
	HoG (0.4 FPPI)	74.6	9.5	32.3	78.6	85.0	17.9	53.2	83.9	82.4	70.1
	April 9, 2007										DRAFT

TABLE III

 III All features and combinations tested, ranked according to their detection rates at 0.3 and 0.4 FPPI, averaged over all datasets but Shotton (for which we evaluate in terms of precision/recall).

	Method	Average DR at 0.3 FPPI Average DR at 0.4 FPPI
	PAS	76.7	81.8
	{1,2,3}AS	74.8	80.6
	PAS + Harris	70.0	76.8
	1AS	69.4	76.2
	3AS	64.1	70.2
	4AS	56.5	64.0
	HoG	56.6	57.5
	Harris	55.0	60.7
	DoG	42.9	50.3
	LoG	43.1	47.9

The case k = 1 is an exception. The descriptor is composed only of θ1, and the scale of 1AS is defined as l1.April 9,

DRAFT

In all other experiments the system is run at multiple scales as detailed in section V-B.April 9, 2007 DRAFT

Note that our criterion for a correct detection is somewhat different from that of[START_REF] Shotton | Contour-Based Learning for Object Detection[END_REF]. This has only a minor influence on the results, as we discuss in section VI-GApril 9, 2007 DRAFT

As shown in section VI-G, this result holds also under stricter criteria for considering a detection as correct.April 9, 2007 DRAFT

are performed with class-specific codebooks.

Performance: The plots in figure 12 and the average detection-rates in table III clearly show that PAS substantially outperform all tested IPs. Only on two datasets IPs achieve a moderately better performance than PAS (Harris-Laplace on swans, and DoG on cups). Besides, we notice IP's uneven performance across different classes (compare DoG on cups and bottles).

The performance of PAS instead, is quite stable. Finally, it's worth noting that on giraffes, for is about the resolution their system is tuned to. Finally, following the protocol applied for PAS, we optimized the two most important parameters on INRIA horses. They are the preprocessing applied before computing gradients, and the block normalization scheme applied after collecting HoG descriptors. The difference between the best and the worst combination of preprocessing and normalization turned out to be moderate: 4.5% detection-rate at 0.3 FPPI. Nevertheless, we processed all datasets with the best combination: converting to Lab color space as preprocessing, [START_REF] Jacobs | Robust and Efficient Detection of Salient Convex Groups[END_REF] DRAFT

TABLE IV

Performance under PASCAL criterion. Detection rates at 0.4 FPPI for PAS and for the object detection system of [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF] (marked as HoG). The 'Shotton' column reports recall at equal error-rate for the Shotton horses dataset. be used in many recognition or image matching frameworks.

We have demonstrated kAS within a sliding-window object detector, where windows are subdivided into tiles, each described by a bag of kAS. Extensive evaluations brought several interesting conclusions. First, the optimal number of tiles decreases with increasing complexity k, due to a trade-off between accurate localization information and rigidity of the representation.

Second, PAS perform better than other kAS, as they bring the best compromise between distinctiveness and repeatability, while also yielding a good proportion of pure boundary features.

Third, kAS work substantially better than interest points for shape-based classes, and, finally, our PAS-based object detection system compares favorably to the state-of-the-art method [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF].

The simple object detection framework developed in this paper is meant as a tool for analyzing the properties and performance of kAS. We believe that considerable gains in object detection performance can be achieved by making the framework more sophisticated. Each kAS could be soft-assigned to several neighboring tiles, rather than just to the tile containing its centerpoint.

This would result in smoother window descriptors, more stable wrt the exact localization of kAS on the object. However, it's unclear how to properly implement spatial soft-assigning using Integral Histograms. Moreover, the scale of kAS relative to the window could be encoded in the window descriptor, thus improving discriminative power. Other enhancements include re-training on hard examples [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], better non-maxima suppression of the SVM responses [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF], and automatic selection of the optimal number of tiles for each class (e.g. using a validation set).

The use of kAS in this paper is limited to a rather simple detection framework. However, we expect kAS to be useful in other systems and tasks [START_REF] Ferrari | Accurate Object Detection with Deformable Shape Models Learnt from Images[END_REF], with possibly other behaviors. For example, although in our analysis 2AS worked best, kAS of higher complexity are attractive April 9, 2007 DRAFT


Eric Falcon

Sébastien Aumaître

Claudio Falcón

Claude Laroche

Stéphan Fauve

Éric Falcon

Fluctuations of energy flux in wave turbulence

Keywords: numbers: 47.35.+i, 92.10.Hm, 47.20.Ky, 68.03.Cd

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

When a dissipative system is driven in a statistically stationary regime by an external forcing, a given amount of power per unit mass, ǫ, is transfered from the driving device to the system and is ultimately dissipated. In fully developed turbulence, a flow is driven at large scales and nonlinear interactions transfer kinetic energy toward small scales where viscous dissipation takes place. In the intermediate range of scales (the inertial range) the key role of the energy flux ǫ has been first understood by Kolmogorov [START_REF] Kolmogorov | Proc. Roy. Soc. Lond. A[END_REF]. Using dimensional arguments, he derived the law E(k) ∝ ǫ 2/3 k -5/3 for the energy density E(k) as a function of the wavenumber k. Kolmogorov type spectra have been derived analytically in wave turbulence, i.e. in various systems involving an ensemble of weakly interacting nonlinear waves (see for instance [START_REF] Connaughton | [END_REF] for a review). In all cases, it has been assumed that ǫ is a given constant parameter. However, it should be kept in mind that ǫ is not an input parameter in most experiments or simulations of dissipative systems. Its value is not externally controlled but determined by the impedance of the system. In addition, as we have already shown for a variety of different dissipative systems [3,4,5], the energy flux or related global quantities, strongly fluctuate in time although being averaged in space on the whole system or on its boundaries. These fluctuations should not be confused with small scale intermittency which occurs in fully developed turbulence. The later is related to the spotness of dissipation in space [6] and its description does not involve a time dependent ǫ.

Here we study the fluctuations of the injected power in wave turbulence. Gravity-capillary waves are generated on a fluid layer by low frequency random vibrations of a wave maker. By measuring the applied force on the wave maker and its velocity, we determine the instantaneous power I(t) injected into the fluid. We observe that it strongly fluctuates. Its most probable value is 0. rms fluctuations σ I up to several times the mean value I are observed, and the probability density function (PDF) of I displays roughly exponential tails for both positive and negative values of I. These negative values correspond to events for which the random wave field gives back energy to the driving device. We show how fluctuations of the injected power depend on the system size and on the mean dissipation and we study their statistical properties. The experimental setup, described in [7], consists of a rectangular plastic vessel, with lateral dimensions 57×50 or 20 × 20 cm 2 , filled with water or mercury (density 13.6 times larger than water) up to a height, h = 1.8 or 2.3 cm. Surface waves are generated by the horizontal motion of a rectangular (L × H cm 2 ) plunging PMMA wave maker driven by an electromagnetic vibration exciter. We take 1.2 < L < 25 cm and H = 3.5 cm. The wave maker is driven with random noise excitation below 4 or 6 Hz.

The power injected into the wave field by the wave maker is determined as follows. The velocity V (t) of the wave maker is measured using a coil placed on the top of the vibration exciter. The voltage induced by the moving permanent magnet of the vibration exciter is proportional to V (t). The force F A (t) applied by the vibration exciter on the wave maker is measured by a piezoresistive force transducer (FGP 10 daN). The time recordings of Typeset by REVT E X V (t) and F A (t) together with their PDFs are displayed in Fig. 1. Both V (t) and F A (t) are Gaussian with zero mean value. For a given excitation bandwidth, the rms value σ V of the velocity fluctuations of the wave maker is proportional to the driving voltage U applied to the electromagnetic shaker and does not depend on the fluid density ρ. On the contrary, the standard deviation σ FA of the force applied to the wave maker is decreased by the density ratio (∼ 13) when mercury is replaced by water. We have checked that σ FA ∝ ρS P σ V where S P = Lh is the immersed area of the wave maker. This linear behavior has been measured on one decade up to σ FA ∼ 2 N and σ V ∼ 0.1 m/s. When the wave maker inertia is negligible, the power I(t) injected into the fluid is roughly given by F A (t)V (t) (see below). The time recording of I(t) is shown in the inset of Fig. 2. Contrary to the velocity or the force, the injected power consists of strong intermittent bursts. Although the forcing is statistically stationary, there are quiescent periods with a small amount of injected power interrupted by bursts where I(t) can take both positive and negative values. The PDFs of I/ I are displayed in Fig. 2. They show that the most probable value of I is zero and display two asymmetric exponential tails (or stretched exponential in the smaller container). We observe that events with I(t) < 0, i.e. for which the wave field gives back energy to the wave maker, occur with a fairly high probability. The standard deviation σ I of the injected power is much larger than its mean value I and rare events with amplitude up to 7 σ are also detected. Typical values obtained when σ V ∼ 0.05 m/s are σ FA ∼ 1 N, I ∼ 30 mW, σ I ∼ 100 mW for mercury. Our measurements also show that σ I ∝ I = cρS P σ 2

V , where c has the dimension of a velocity (c ∼ 0.5 m/s and slightly increases when the container size is increased).

We also observe in Fig. 2 that the probability of negative events strongly decreases when the container size is increased whereas the positive fluctuations are less affected. This shows that the backscattering of the energy flux from the wave field to the driving device is related to the waves reflected by the boundary that can, from time to time, drive the wave maker in phase with its motion. We note that we have less statistics for the negative tail of the PDF when the size of the container is increased.

We recall that the statistical properties of the fluctuations of the surface height have been studied in [7]: they involve a large distribution of amplitude fluctuations. Their frequency spectrum is broad band and can be fitted by two power laws in the gravity and capillary regimes. The power law exponent in the capillary range is in agreement with theoretical predictions. The one in the gravity range depends on the forcing, as also shown in [8]. The scaling of the spectrum with respect to the mean energy flux I is different from the theoretical prediction both in the gravity and capillary ranges. These discrepancies can be ascribed to finite size effects [7,8]. Water FIG. 3: (color online) Effect of the inertia of the wave maker: PDF of FAV (black) and of (FA -M V )V (red) for mercury (h = 23 mm) (left) and for water (h = 23 mm) (right). Using FAV to estimate I leads to an error on the standard deviation σI that is less than 5% for mercury but that reaches 50% for water.

We first emphasize the bias that can result from the system inertia when one tries a direct measurement of the fluctuations of injected power. The equation of motion of the wave maker is

M V = F A (t) + F R (t), ( 1
)
where M is the mass of the wave maker and F R (t) is the force due to the fluid motion ( V ≡ dV /dt). The power injected into the fluid by the wave maker is

I(t) = -F R (t)V (t)
. When M V is not negligible, I(t) generally differs from F A (t)V (t) which is experimentally determined. This obviously does not affect the mean value I but may lead to wrong estimates of fluctuations. Using an accelerometer, we have checked that M V is negligible compared to F A when the working fluid is mercury. This is shown is Fig. 3 (left) where the PDF of F A V and F R V = (F A -M V )V are compared. On the contrary, inertia cannot be neglected for experiments in water for which an error as large as one order of magnitude can be made on the probability of rare events if one use F A V to estimate I (right). Thus, the correction due to M V has been taken into account in water experiments. There exist only a few previous direct measurements of injected power in turbulent flows and those type of inertial bias have never been taken into account [9]. The PDFs of injected power for the same driving in the same container for water and mercury are displayed in Fig. 4. The asymmetry of the PDF is much larger with mercury. This is related to its larger mean energy flux, i.e., mean dissipation, as shown below.

The qualitative features of the PDF of injected power can be described with the following simple model. Guided by our experimental observation of the linearity of σ FA in σ V , we assume that the force F R due to the fluid can be roughly approximated by a friction force -M γV where γ is a constant (the inverse of the damping time of the wave maker). We are aware that a better approximation to the force due to the fluid should involve both V and an integral of V (t ′ ) with an appropriate kernel. Thus we only claim here to give a heuristic understanding of the qualitative properties of the PDF of I. Modelling the forcing with an Ornstein-Uhlenbeck process, we obtain

V = -γV + F, Ḟ = -βF + ξ, ( 2
)
where β is the inverse of the correlation time of the applied force (F = F A /M ) and ξ is a Gaussian white noise with ξ(t)ξ(t ′ ) = Dδ(t -t ′ ). The PDF P (V, F ) is the bivariate normal distribution [START_REF] Risken | The Fokker-Planck Equation[END_REF][START_REF]Describing the PDF of the injected power using two correlated normal variables has been also proposed independently by M. Bandi and C. Connaughton[END_REF]

P (V, F ) = exp -1 2(1-r 2 ) V 2 σ 2 V -2rV F σV σF + F 2 σ 2 F 2πσ V σ F √ 1 -r 2 , (3)
with σ F = D/2β, σ V = D/(2γβ(γ + β)) and r = γ/(γ + β). Changing variables (V, F ) to ( Ĩ = F V = I/M, F ) and integrating over F gives

P ( Ĩ) = exp r Ĩ (1-r 2 )σV σF πσ V σ F √ 1 -r 2 K 0 | Ĩ| (1 -r 2 )σ V σ F , (4)
where K 0 (X) is the zeroth order modified Bessel function of the second kind. Using the method of steepest descent, this predicts exponential tails, P (X) ∼

(1/ |X|) exp(rX -|X|) where X = Ĩ/[(1-r 2 )σ V σ F ]. In addition, we have Ĩ = D/[2β(γ + β)] = rσ V σ F . Thus, (4)
is determined once I , σ V and σ F have been measured and can be compared to the experimental PDF without using any fitting parameter. This is displayed with dashed lines in Fig. 2. Taking into account the strong approximation made in the above model, we observe a good agreement in the larger container. More importantly, this model captures the qualitative features of the PDF: its maximum for I = 0 and the asymmetry of the tails that is governed by the parameter r = γ/(γ + β) = I /(σ V σ FA ). For given σ V and σ FA , the larger is the mean energy flux, i.e., the dissipation, the more asymmetric is the PDF. For mercury, direct determination of r from the measurement of I , σ V and σ FA gives r ∼ 0.7 for the large container and r ∼ 0.6 for the small one, in qualitative agreement with the different asymmetry of the PDF in Fig. 2. Smaller values of r are achieved in water for which the dissipation is smaller. The PDFs are more stretched for water in particular in the smaller container. We now consider the injected power averaged on a time interval τ

I τ (t) = 1 τ t+τ t I(t ′ )dt ′ . (5)
The PDFs of I τ for τ /τ c = 1, 3, 11 and 50 where τ c is the correlation time of I(t), are displayed in Fig. 5. They become more and more peaked around I τ ≃ I as they should. However, one needs to average on a rather large time interval (τ ∼ 50τ c ) in order to get a maximum probability P (I τ ) for I τ = I (Fig. 5, bottom right). Then, the probability of negative events become so small that almost none can be observed. Fig. 6 shows that the quantity, 1 τ log P (Iτ / I ) P (-Iτ / I ) for different values of τ that has been predicted to be linear in I τ / I when the hypothesis of the fluctuation theorem (in particular time reversibility) are fulfilled [START_REF] Evans | [END_REF]13]. As we clearly observe in Fig. 6, this is not the case in general for dissipative systems. As already mentioned [4] and studied in details [14], the linear behavior reported in several experiments or numerical simulations results from the too small values of I τ / I that are probed when τ ≫ τ c . Large enough values are obtained in the present experiment and the expected nonlinear behavior is thus reached. The shape of the curve in Fig. 6 is found in good agreement with the analytical calculation [15] performed with a Langevin type equation with white noise. Finally, we emphasize that a fluctuating injected power implies fluctuations of the energy flux at all wave numbers in the energy cascade from injection to dissipation. In any system where an energy flux cascades from the injected power at large scales to dissipation at small scales, one has for the energy E < for wave numbers smaller than k within the inertial range, Ė< = I(t) -Φ(k, t) ≡ R, where Φ(k, t) is the energy flux at k toward large wave numbers. Thus ∞ 0 R(τ )R(0) dτ = 0 in order to prevent the divergence of E 2 < . Dimensionaly, this implies that σ 2 Φ τ k does not depend on k [5], where σ Φ is the standard deviation of the energy flux and τ k is its correlation time. If this dimensional scaling is correct, fluctuations of the energy flux are expected to increase during the cascade from large to small scales since τ k decreases (for instance, σ Φ ∝ k 1/3 for hydrodynamic turbulence). Such fluctuations have been found numerically and experimentally in hydrodynamic turbulence [16]. To which extent, this is related or modified by small scale intermittency [17] remains an open question.

FIG. 1 :

 1 FIG.1:(color online) Time recordings of the velocity of the wave maker and the force applied to the wave maker by the vibration exciter. The fluid is mercury, with h = 23 mm. Both PDF are Gaussian (dashed lines) with zero mean value.

FIG. 2 :

 2 FIG.2:(color online) PDF of I(t)/ I for mercury: container size 57 × 50 cm 2 (red) and 20 × 20 cm 2 (black) (h = 18 mm). Dashed lines are the related predictions from equation (4) without fitting parameter. Inset: time recording of I(t).

FIG. 4 :

 4 FIG. 4: (color online) Effect of fluid properties on the PDF of the injected power: (red) mercury; (black): water (h = 18 mm; 20×20 cm 2 container). Solid lines indicate the value of I /σI .

FIG. 5 :

 5 FIG. 5: (color online) PDFs of the injected power Iτ averaged on a time interval τ : τ = 1, 3, 11 and 50τc, where τc = 0.03 s is the correlation time of I(t). Solid lines indicate the value of I (water, h = 23 mm).

FIG. 6 :

 6 FIG. 6: (color online) Plot of 1 τ log P (Iτ / I ) P (-Iτ / I ) for 16 < τ /τc < 39 [τ /τc = 17 ( * ), 19.5 (•), 22 ( ), 25 (♦), 28 (pentagram), 30.5 (▽), 33.5 (hexagram), 39 (⊳)]. Langevin model of reference [15]: 4γ for ǫ = Iτ / I ≤ 1/3 (dashed line) and 7γǫ/4 + 3γ/2 -γ/(4ǫ) for ǫ ≥ 1/3 (solid line) with γ = 5 Hz.

We acknowledge useful discussions with F. Pétrélis. This work has been supported by ANR turbonde BLAN07-3-197846 and by the CNES.