From Images to Shape Models for Object Detection

We present an object class detection approach which fully integrates the complementary strengths offered by shape matchers. Like an object detector, it can learn class models directly from images, and can localize novel instances in the presence of intra-class variations, clutter, and scale changes. Like a shape matcher, it finds the boundaries of objects, rather than just their bounding-boxes. This is achieved by a novel technique for learning a shape model of an object class given images of example instances. Furthermore, we also integrate Hough-style voting with a non-rigid point matching algorithm to localize the model in cluttered images. As demonstrated by an extensive evaluation, our method can localize object boundaries accurately and does not need segmented examples for training (only bounding-boxes).     

DanVideo: an MPEG-7 authoring and retrieval system for dance videos

A well-annotated dance media is an essential part of a nation’s identity, transcending cultural and language barriers. Many dance video archives suffer from problems concerning authoring and access, because of the complex spatio-temporal relationships that exist between the dancers in terms of movements of their body parts and the emotions expressed by them in a dance. This paper presents a system named DanVideo for semi-automatic authoring and access to dance archives. DanVideo provides methods of annotation and authoring and retrieval tools for choreographers, dancers, and students. We demonstrate how dance media can be semantically annotated and how this information can be used for the retrieval of the dance video semantics. In particular, DanVideo offers an MPEG-7 based semi-automatic authoring tool that takes dance video annotations generated by dance experts and produces MPEG-7 metadata. DanVideo also has a search engine that takes users’ queries and retrieves dance semantics from metadata arranged using tree-embedding technique and based on spatial, temporal and spatio-temporal features of dancers. The search engine also leverages a domain-specific ontology to process knowledge-based queries. We have assessed the dance-video queries and semantic annotations in terms of precision, recall, and fidelity.     

Supervised image segmentation using Q-Shift Dual-Tree Complex Wavelet Transform coefficients with a texton approach

In this study, we propose a simple and efficient texture-based algorithm for image segmentation. This method constitutes computing textons and bag of words (BOWs) learned by support vector machine (SVM) classifiers. Textons are composed of local magnitude coefficients that arise from the Q-Shift Dual-Tree Complex Wavelet Transform (DT-CWT) combined with color components. In keeping with the needs of our research context, which addresses land cover mapping from remote images, we use a few small texture patches at the training stage, where other supervised methods usually train fully representative textures. We accounted for the scale and rotation invariance issue of the textons, and three different invariance transforms were evaluated on DT-CWT-based features. The largest contribution of this study is the comparison of three classification schemes in the segmentation algorithm. Specifically, we designed a new scheme that was especially competitive and that uses several classifiers, with each classifier adapted to a specific size of analysis window in texton quantification and trained on a reduced data set by random selection. This configuration allows quick SVM convergence and an easy parallelization of the SVM-bank while maintaining a high segmentation accuracy. We compare classification results with textons made using the well-known maximum response filters bank and speed up robust features features as references. We show that DT-CWT textons provide better distinguishing features in the entire set of configurations tested. Benchmarks of our different method configurations were made over two substantial textured mosaic sets, each composed of 100 grey or color mosaics made up of Brodatz or VisTex textures. Lastly, when applied to remote sensing images, our method yields good region segmentation compared to the ENVI commercial software, which demonstrates that the method could be used to generate land cover maps and is suitable for various purposes in image segmentation.     

The medial scaffold of 3D unorganized point clouds

We introduce the notion of the medial scaffold, a hierarchical organization of the medial axis of a 3D shape in the form of a graph constructed from special medial curves connecting special medial points. A key advantage of the scaffold is that it captures the qualitative aspects of shape in a hierarchical and tightly condensed representation. We propose an efficient and exact method for computing the medial scaffold based on a notion of propagation along the scaffold itself, starting from initial sources of the flow and constructing the scaffold during the propagation. We examine this method specifically in the context of an unorganized cloud of points in 3D, e.g., as obtained from laser range finders, which typically involve hundreds of thousands of points, but the ideas are generalizable to data arising from geometrically described surface patches. The computational bottleneck in the propagation-based scheme is in finding the initial sources of the flow. We thus present several ideas to avoid the unnecessary consideration of pairs of points which cannot possibly form a medial point source, such as the "visibility of a point from another given a third point and the interaction of clusters of points. An application of using the medial scaffold for the representation of point samplings of real-life objects is also illustrated     

Quantum Complexity of Testing Group Commutativity

We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in . The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of , we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.     

Locality-Sensitive Hashing for Chi2 distance

In the past 10 years, new powerful algorithms based on efficient data structures have been proposed to solve the problem of Nearest Neighbors search (or Approximate Nearest Neighbors search). If the Euclidean Locality Sensitive Hashing algorithm, which provides approximate nearest neighbors in a euclidean space with sublinear complexity, is probably the most popular, the euclidean metric does not always provide as accurate and as relevant results when considering similarity measure as the Earth-Mover Distance and 2 distances. In this paper, we present a new LSH scheme adapted to 2 distance for approximate nearest neighbors search in high-dimensional spaces. We define the specific hashing functions, we prove their local-sensitivity, and compare, through experiments, our method with the Euclidean Locality Sensitive Hashing algorithm in the context of image retrieval on real image databases. The results prove the relevance of such a new LSH scheme either providing far better accuracy in the context of image retrieval than euclidean scheme for an equivalent speed, or providing an equivalent accuracy but with a high gain in terms of processing speed.     

Fast Minor Testing in Planar Graphs

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C _u and C _v . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming.     

Reorientation patterns in central-place foraging: internal clocks and klinokinesis

We study central-place foraging patterns of Aphaenogaster senilis ants at a population level by video framing individual ant trajectories in a circular arena with a nest connected to its centre. The ants naturally leave and enter the nest and forage generating non-trivial movement patterns around the nest. Our data analysis indicated that the trajectories observed can be classified into two strategies: the risk-averse strategy, which involves wandering around the nest without departing far from it and the risk-prone strategy, which involves long exploration paths with periodic returns to the central region, nearby the nest. We found that both risk-prone and risk-averse strategies exhibit qualitatively the same reorientation patterns, with the time between consecutive reorientations covering a wide range of scales, and fitting a stretched exponential function. Nevertheless, differences in the temporal scales and the time variability of such reorientation events differ, together with other aspects of motion, such as average speed and turns. Our results give experimental evidence that the internal mechanisms driving reorientations in ants tend to favour frequently long relocations, as theory predicts for efficient exploration in patchy landscapes, but ants engaged in central-place foraging can modulate such behaviour to control distances from the nest. Previous works on the species support the idea that risk-prone and risk-averse strategies may reflect actual differences between individuals age and experience; these factors (age and experience) should be then relevant in modulating the internal reorientation clocks. To support the validity of our findings, we develop a random-walk model combining stretched exponential reorientation clocks with klinokinesis that fits the time length and the travelled distance distributions of the observed trajectories.