We present an original multiview stereo reconstruction algorithm which allows the 3D-modeling of urban scenes as a combination of meshes and geometric primitives. The method provides a compact model while preserving details: Irregular elements such as statues and ornaments are described by meshes, whereas regular structures such as columns and walls are described by primitives (planes, spheres, cylinders, cones, and tori). We adopt a two-step strategy consisting first in segmenting the initial meshbased surface using a multilabel Markov Random Field-based model and second in sampling primitive and mesh components simultaneously on the obtained partition by a Jump-Diffusion process. The quality of a reconstruction is measured by a multi-object energy model which takes into account both photo-consistency and semantic considerations (i.e., geometry and shape layout). The segmentation and sampling steps are embedded into an iterative refinement procedure which provides an increasingly accurate hybrid representation. Experimental results on complex urban structures and large scenes are presented and compared to state-of-the-art multiview stereo meshing algorithms.

Since the initial comparison of Seitz et al., the accuracy of dense multiview stereovision methods has been increasing steadily. A number of limitations, however, make most of these methods not suitable to outdoor scenes taken under uncontrolled imaging conditions. The present work consists of a complete dense multiview stereo pipeline which circumvents these limitations, being able to handle large-scale scenes without sacrificing accuracy. Highly detailed reconstructions are produced within very reasonable time thanks to two key stages in our pipeline: a minimum s-t cut optimization over an adaptive domain that robustly and efficiently filters a quasidense point cloud from outliers and reconstructs an initial surface by integrating visibility constraints, followed by a mesh-based variational refinement that captures small details, smartly handling photo-consistency, regularization, and adaptive resolution. The pipeline has been tested over a wide range of scenes: from classic compact objects taken in a laboratory setting, to outdoor architectural scenes, landscapes, and cultural heritage sites. The accuracy of its reconstructions has also been measured on the dense multiview benchmark proposed by Strecha et al., showing the results to compare more than favorably with the current state-of-the-art methods.

Kernels are functions designed in order to capture resemblance between data and they are used in a wide range of machine learning techniques, including support vector machines (SVMs). In their standard version, commonly used kernels such as the Gaussian one show reasonably good performance in many classification and recognition tasks in computer vision, bioinformatics, and text processing. In the particular task of object recognition, the main deficiency of standard kernels such as the convolution one resides in the lack in capturing the right geometric structure of objects while also being invariant. We focus in this paper on object recognition using a new type of kernel referred to as "context dependent.” Objects, seen as constellations of interest points, are matched by minimizing an energy function mixing 1) a fidelity term which measures the quality of feature matching, 2) a neighborhood criterion which captures the object geometry, and 3) a regularization term. We will show that the fixed point of this energy is a context-dependent kernel which is also positive definite. Experiments conducted on object recognition show that when plugging our kernel into SVMs, we clearly outperform SVMs with context-free kernels.

We propose a multi-view stereo reconstruction algorithm which recovers urban scenes as a combination of meshes and geometric primitives. It provides a compact model while preserving details: irregular elements such as statues and ornaments are described by meshes whereas regular structures such as columns and walls are described by primitives (planes, spheres, cylinders, cones and tori). A Jump-Diffusion process is designed to sample these two types of elements simultaneously. The quality of a reconstruction is measured by a multi-object energy model which takes into account both photo-consistency and semantic considerations (i.e. geometry and shape layout). The sampler is embedded into an iterative refinement procedure which provides an increasingly accurate hybrid representation. Experimental results on complex urban structures and large scenes are presented and compared to multi-view based meshing algorithms.

We propose an original hybrid modeling process of urban scenes that represents 3-D models as a combination of mesh-based surfaces and geometric 3-D-primitives. Meshes describe details such as ornaments and statues, whereas 3-D-primitives code for regular shapes such as walls and columns. Starting from an 3-D-surface obtained by multiview stereo techniques, these primitives are inserted into the surface after being detected. This strategy allows the introduction of semantic knowledge, the simplification of the modeling, and even correction of errors generated by the acquisition process. We design a hierarchical approach exploring different scales of an observed scene. Each level consists first in segmenting the surface using a multilabel energy model optimized by -expansion and then in fitting 3-D-primitives such as planes, cylinders or tori on the obtained partition where relevant. Experiments on real meshes, depth maps and synthetic surfaces show good potential for the proposed approach.

International audience

This paper presents a new method to extract tubular structures from bi-dimensional images. The core of the proposed algorithm is the computation of geodesic curves over a four-dimensional space that includes local orientation and scale. These shortest paths follow closely the centerline of tubular structures, provide an estimation of the radius and can deal robustly with crossings over the image plane. Numerical experiments on a database of synthetic and natural images show the superiority of the proposed approach with respect to several method based on shortest paths extractions.

Existing algorithms for surface reconstruction from point sets are defeated by moderate amounts of noise and outliers, which makes them unapplicable to point clouds originating from multi-view image data. In this paper, we present a novel method which incorporates the input images in the surface reconstruction process for a better accuracy and robustness. Our approach is based on the medial axis transform of the scene, which our algorithm estimates through a global photo-consistency optimization by simulated annealing. A faithful polyhedral representation of the scene is then obtained by inversion of the medial axis transform.

We propose a new approach to the problem of robust estimation in multiview geometry. Inspired by recent advances in the sparse recovery problem of statistics, our estimator is defined as a Bayesian maximum a posteriori with multivariate Laplace prior on the vector describing the outliers. This leads to an estimator in which the fidelity to the data is measured by the $L_\infty$-norm while the regularization is done by the $L_1$-norm. The proposed procedure is fairly fast since the outlier removal is done by solving one linear program (LP). An important difference compared to existing algorithms is that for our estimator it is not necessary to specify neither the number nor the proportion of the outliers. The theoretical results, as well as the numerical example reported in this work, confirm the efficiency of the proposed approach.

Abstract We describe a robust but simple algorithm to reconstruct a surface from a set of merged range scans. Our key contribution is the formulation of the surface reconstruction problem as an energy minimisation problem that explicitly models the scanning process. The adaptivity of the Delaunay triangulation is exploited by restricting the energy to inside/outside labelings of Delaunay tetrahedra. Our energy measures both the output surface quality and how well the surface agrees with soft visibility constraints. Such energy is shown to perfectly fit into the minimum s − t cuts optimisation framework, allowing fast computation of a globally optimal tetrahedra labeling, while avoiding the “shrinking bias” that usually plagues graph cuts methods. The behaviour of our method confronted to noise, undersampling and outliers is evaluated on several data sets and compared with other methods through different experiments: its strong robustness would make our method practical not only for reconstruction from range data but also from typically more difficult dense point clouds, resulting for instance from stereo image matching. Our effective modeling of the surface acquisition inverse problem, along with the unique combination of Delaunay triangulation and minimum s − t cuts, makes the computational requirements of the algorithm scale well with respect to the size of the input point cloud.

This paper addresses the problem of segmenting an image into regions consistent with user-supplied seeds (e.g., a sparse set of broad brush strokes). We view this task as a statistical transductive inference, in which some pixels are already associated with given zones and the remaining ones need to be classified. Our method relies on the Laplacian graph regularizer, a powerful manifold learning tool that is based on the estimation of variants of the Laplace-Beltrami operator and is tightly related to diffusion processes. Segmentation is modeled as the task of finding matting coefficients for unclassified pixels given known matting coefficients for seed pixels. The proposed algorithm essentially relies on a high margin assumption in the space of pixel characteristics. It is simple, fast, and accurate, as demonstrated by qualitative results on natural images and a quantitative comparison with state-of-the-art methods on the Microsoft GrabCut segmentation database.

The success of kernel methods including support vector networks (SVMs) strongly depends on the design of appropriate kernels. While initially kernels were designed in order to handle fixed-length data, their extension to unordered, variable-length data became more than necessary for real pattern recognition problems such as object recognition and bioinformatics. We focus in this paper on object recognition using a new type of kernel referred to as ldquocontext-dependentrdquo. Objects, seen as constellations of local features (interest points, regions, etc.), are matched by minimizing an energy function mixing (1) a fidelity term which measures the quality of feature matching, (2) a neighborhood criteria which captures the object geometry and (3) a regularization term. We will show that the fixed-point of this energy is a ldquocontext-dependentrdquo kernel (ldquoCDKrdquo) which also satisfies the Mercer condition. Experiments conducted on object recognition show that when plugging our kernel in SVMs, we clearly outperform SVMs with ldquocontext-freerdquo kernels.

Interactive image search or relevance feedback is the process which helps a user refining his query and finding difficult target categories. This consists in partially labeling a very small fraction of an image database and iteratively refining a decision rule using both the labeled and unlabeled data. Training of this decision rule is referred to as transductive learning. Our work is an original approach for relevance feedback based on Graph Laplacian. We introduce a new Graph Laplacian which makes it possible to robustly learn the embedding, of the manifold enclosing the dataset, via a diffusion map. Our approach is three-folds: it allows us (i) to integrate all the unlabeled images in the decision process (ii) to robustly capture the topology of the image set and (iii) to perform the search process inside the manifold. Relevance feedback experiments were conducted on simple databases including Olivetti and Swedish as well as challenging and large scale databases including Corel. Comparisons show clear and consistent gain, of our graph Laplacian method, with respect to state-of-the art relevance feedback approaches.

Interactive image search or relevance feedback is the process which helps a user refining his query and finding difficult target categories. This consists in a step-by-step labeling of a very small fraction of an image database and iteratively refining a decision rule using both the labeled and unlabeled data. Training of this decision rule is referred to as transductive learning. Our work is an original approach for relevance feedback based on Graph Laplacian. We introduce a new Graph Laplacian which makes it possible to robustly learn the embedding of the manifold enclosing the dataset via a diffusion map. Our approach is two-folds: it allows us (i) to integrate all the unlabeled images in the decision process and (ii) to robustly capture the topology of the image set. Relevance feedback experiments were conducted on simple databases including Olivetti and Swedish as well as challenging and large scale databases including Corel. Comparisons show clear and consistent gain of our graph Laplacian method with respect to state-of-the art relevance feedback approaches.

Kernel PCA has received a lot of attention over the past years and showed usefull for many image processing problems. In this paper we analyse the issue of normalization in Kernel PCA for the pre-image problem. We present a geometric interpretation of the normalization process for the gaussian kernel. As a consequence, we could formulate a correct normalization criterion in centered feature space. Furthermore, we show how the proposed normalization criterion improves previous pre-image methods for the task of image denoising.

The success of kernel methods including support vector machines (SVMs) strongly depends on the design of appropriate kernels. While initially kernels were designed in order to handle fixed-length data, their extension to unordered, variable-length data became more than necessary for real pattern recognition problems such as object recognition and bioinformatics.

In this paper, we propose a novel method for creating a high-quality texture atlas from a 3D model and a set of calibrated images. Our method focuses on avoiding visual artifacts such as color discontinuities, ghosting or blurring, which typically arise from photometric and geometric inaccuracies. We first compute a partition of mesh faces which realizes a good trade-off between visual detail and color continuity at patch boundaries: we efficiently obtain a close-to-optimal seam placement using graph cuts optimization. We then apply a pixel-wise color correction in the vicinity of patch boundaries with a principled 3D extension of multi-band image blending: we achieve faultless color continuity while avoiding ghosting artifacts. We demonstrate the effectiveness of our method on two real-world large-scale scenes.

Matching feature points between images is a key point in many computer vision tasks. As the number of images increases, this rapidly becomes a bottleneck. We here present how to use the power of GPUs to obtain image matching in typically 20 ms for one thousand points. This speedup makes applications like interactive image matching possible. Such a portable system, dedicated to 3D large scale reconstruction, is reported.

This paper addresses the recovering of 3D pose and animation of the human face in a monocular single image under uncontrolled imaging conditions. Our goal is to fit a 3D animated model in a face image with possibly large variations of head pose and facial expressions. Our data were acquired from filmed epileptic seizures of patients undergoing investigation in the videotelemetry unit, La Timone hospital, Marseille, France.

We propose a new approach to compute non-linear, intrinsic shape statistics and to incorporate them into a shape prior for an image segmentation task. Given a sample set of contours, we first define their mean shape as the one which is simultaneously closest to all samples up to rigid motions, and compute it in a gradient descent framework. We consider here a differentiable approximation of the Hausdorff distance between shapes. Statistics on the instantaneous deformation fields that the mean shape should undergo to move towards each sample lead to sensible characteristic modes of deformation that convey the shape variability. Contour statistics are turned into a shape prior which is rigid-motion invariant. Image segmentation results show the improvement gained by the shape prior.

We propose a novel method for computing a four-dimensional (4D) representation of the spatio-temporal visual hull of a dynamic scene, based on an extension of a recent provably correct Delaunay meshing algorithm. By considering time as an additional dimension, our approach exploits seamlessly the time coherence between different frames to produce a compact and high-quality 4D mesh representation of the visual hull. The 3D visual hull at a given time instant is easily obtained by intersecting this 4D mesh with a temporal plane, thus enabling interpolation of objects' shape between consecutive frames. In addition, our approach offers easy and extensive control over the size and quality of the output mesh as well as over its associated re- projection error. Our numerical experiments demonstrate the effectiveness and flexibility of our approach for generating compact, high-quality, time-coherent visual hull representations from real silhouette image data.

We introduce a non-linear shape prior for the de- formable model framework that we learn from a set of shape samples using recent manifold learning techniques. We model a category of shapes as a finite dimensional manifold which we approximate using Diffusion maps, that we call the shape prior manifold. Our method computes a Delaunay triangulation of the reduced space, considered as Euclidean, and uses the resulting space partition to identify the closest neighbors of any given shape based on its Nystrom extension. Our contribution lies in three aspects. First, we propose a solution to the pre-image problem and define the projection of a shape onto the manifold. Based on closest neighbors for the Diffusion distance, we then describe a variational framework for manifold denoising. Finally, we introduce a shape prior term for the deformable framework through a non-linear energy term designed to attract a shape towards the manifold at given constant embedding. Results on shapes of cars and ventricule nuclei are presented and demonstrate the potentials of our method.

We present a novel method to reconstruct the 3D shape of a scene from several calibrated images. Our motivation is that most existing multi-view stereovision approaches require some knowledge of the scene extent and often even of its approximate geometry (e.g. visual hull). This makes these approaches mainly suited to compact objects admitting a tight enclosing box, imaged on a simple or a known background. In contrast, our approach focuses on large-scale cluttered scenes under uncontrolled imaging conditions. It first generates a quasi-dense 3D point cloud of the scene by matching keypoints across images in a lenient manner, thus possibly retaining many false matches. Then it builds an adaptive tetrahedral decomposition of space by computing the 3D Delaunay triangulation of the 3D point set. Finally, it reconstructs the scene by labeling Delaunay tetrahedra as empty or occupied, thus generating a triangular mesh of the scene. A globally optimal label assignment, as regards photo-consistency of the output mesh and compatibility with the visibility of keypoints in input images, is efficiently found as a minimum cut solution in a graph.

Closing the semantic gap in content based image retrieval (CBIR) basically requires the knowledge of the user's intention which is usually translated into a sequence of questions and answers (Q&A). The user's feedback to these questions provides a CBIR system with a partial labeling of the data and makes it possible to iteratively refine a decision rule on the unlabeled data. Training of this decision rule is referred to as transductive learning. This work is an original approach to relevance feedback (RF) based on graph-cuts. Training consists in implicitly modeling the manifold enclosing both the labeled and unlabeled dataset and finding a partition of this manifold using a min-cut. The contribution of this work is two-fold (i) this is the first comprehensive study of relevance feedback using graph cuts and (ii) our RF model exploits the structure of the data manifold by considering also the structure of the unlabeled data. Experiments conducted on generic as well as specific databases show that our graph-cut based approach is very effective, outperforms other existing methods and makes it possible to converge to almost all the images of the user's "class of interest" with a very small labeling effort. A demo is available through our image retrieval tool kit (IRTK).

Image segmentation with shape priors has received a lot of attention over the past years. Most existing work focuses on a linearized shape space with small deformation modes around a mean shape, which is relevant only when considering similar shapes. In this paper, we introduce a new framework that can handle more general shape priors. We model a category of shapes as a finite dimensional manifold, the shape prior manifold, which we approximate from the shape samples using dimensionality reduction techniques suchlike Laplacian eigenmaps. Unfortunately, this model does not provide an explicit projection operator onto the manifold. Our contribution is twofold. First, we calculate the low dimensional representation of any point not in the training set. Second, we properly define a projection operator onto the manifold by interpolating between shape samples using local weighted means. We show results both on synthetic and real shapes and demonstrate the potential of our method for segmentation tasks.

This article deals with statistics on sets of shapes. The approach is based on the Hausdorff distance between shapes, The choice of the Hausdorff distance between shapes is itself not fundamental since the same framework could be applied with another distance. We first define a smooth approximation of the Hausdorff distance and build non-supervised warpings between shapes by a gradient descent of the approximation. Local minima can be avoided by changing the scalar product in the tangent space of the shape being warped. When non-supervised warping fails, we present a way to guide the evolution with a small number of landmarks. Thanks to the warping fields, we can define the mean of a set of shapes and express statistics on them. Finally, we come back to the initial distance between shapes and use it to represent a set of shapes by a graph, which with the technique of graph Laplacian leads to a way of projecting shapes onto a low dimensional space

In this paper, we present a new variational method for multi-view stereovision and non-rigid three-dimensional motion estimation from multiple video sequences. Our method minimizes the prediction error of the shape and motion estimates. Both problems then translate into a generic image registration task. The latter is entrusted to a similarity measure chosen depending on imaging conditions and scene properties. In particular, our method can be made robust to appearance changes due to non-Lambertian materials and illumination changes. It results in a simpler, more flexible, and more efficient implementation than existing deformable surface approaches. The computation time on large datasets does not exceed thirty minutes. Moreover, our method is compliant with a hardware implementation with graphics processor units. Our stereovision algorithm yields very good results on a variety of datasets including specularities and translucency. We have successfully tested our scene flow algorithm on a very challenging multi-view video sequence of a non-rigid scene.

We propose a new approach to deal with the first and second order statistics of a set of images. These statistics take into account the images characteristic deformations and their variations in intensity. The central algorithm is based on nonsupervised diffeomorphic image matching (without landmarks or human intervention). As they convey the notion of the mean shape and colors of an object and the one of its common variations, such statistics of sets of images may be relevant in the context of object recognition, both in the segmentation of any of its representations and in the classification of them. The proposed approach has been tested on a small database of face images to compute a mean face and second order statistics. The results are very encouraging since, whereas the algorithm does not need any human intervention and is not specific to face image databases, the mean image looks like a real face and the characteristic modes of variation (deformation and intensity changes) are sensible.

This paper tackles an important aspect of the variational problems involving active contours, which has been largely overlooked so far: the optimization by gradient flows. Classically, the definition of a gradient depends directly on the choice of an inner product structure. This consideration is largely absent from the active contours literature. Most authors, overtly or covertly, assume that the space of admissible deformations is ruled by the canonical L2inner product. The classical gradient flows reported in the literature are relative to this particular choice. In this paper, we investigate the relevance of using other inner products, yielding other gradient descents, and some other minimizing flows not deriving from any inner product. In particular we, show how to induce different degrees of spatial coherence into the minimizing flow, in order to decrease the probability of getting trapped into irrelevant local minima. We show with some numerical experiments that the sensitivity of the active contours method to initial conditions, which seriously limits its applicability and its efficiency, is alleviated by our application-specific spatially coherent minimizing flows

The forward electroencephalography (EEG) problem involves finding a potential V from the Poisson equation inverted Delta x (sigma inverted Delta V) f, in which f represents electrical sources in the brain, and sigma the conductivity of the head tissues. In the piecewise constant conductivity head model, this can be accomplished by the boundary element method (BEM) using a suitable integral formulation. Most previous work uses the same integral formulation, corresponding to a double-layer potential. In this paper we present a conceptual framework based on a well-known theorem (Theorem 1) that characterizes harmonic functions defined on the complement of a bounded smooth surface. This theorem says that such harmonic functions are completely defined by their values and those of their normal derivatives on this surface. It allows us to cast the previous BEM approaches in a unified setting and to develop two new approaches corresponding to different ways of exploiting the same theorem. Specifically, we first present a dual approach which involves a single-layer potential. Then, we propose a symmetric formulation, which combines single- and double-layer potentials, and which is new to the field of EEG, although it has been applied to other problems in electromagnetism. The three methods have been evaluated numerically using a spherical geometry with known analytical solution, and the symmetric formulation achieves a significantly higher accuracy than the alternative methods. Additionally, we present results with realistically shaped meshes. Beside providing a better understanding of the foundations of BEM methods, our approach appears to lead also to more efficient algorithms.

In this paper, we overcome a major drawback of the level set framework: the lack of point correspondences. We maintain explicit backward correspondences from the evolving interface to the initial one by advecting the initial point coordinates with the same speed as the level set function. Our method leads to a system of coupled Eulerian partial differential equations. We show in a variety of numerical experiments that it can handle both normal and tangential velocities, large deformations, shocks, rarefactions and topological changes. Applications are many in computer vision and elsewhere since our method can upgrade virtually any level set evolution. We complement our work with the design of non zero tangential velocities that preserve the relative area of interface patches; this feature may be crucial in such applications as computational geometry, grid generation or unfolding of the organs' surfaces, e.g. brain, in medical imaging.

We present a common variational framework for dense depth recovery and dense three-dimensional motion field estimation from multiple video sequences, which is robust to camera spectral sensitivity differences and illumination changes. For this purpose, we first show that both problems reduce to a generic image matching problem after backprojecting the input images onto suitable surfaces. We then solve this matching problem in the case of statistical similarity criteria that can handle frequently occurring nonaffine image intensities dependencies. Our method leads to an efficient and elegant implementation based on fast recursive filters. We obtain good results on real images.

Approximations of shape metrics, such as the Hausdorff distance, to define similarity measures between shapes are proposed. Our approximations being continuous and differentiable, they provide an obvious way to warp a shape onto another by solving a partial differential equation (PDE), in effect a curve flow, obtained from their first order variation. This first order variation defines a normal deformation field for a given curve. We use the normal deformation fields induced by several sample shape examples to define their mean, their covariance "operator", and the principal modes of variation. Our theory, which can be seen as a nonlinear generalization of the linear approaches proposed by several authors, is illustrated with numerous examples. Our approach being based upon the use of distance functions is characterized by the fact that it is intrinsic, i.e. independent of the shape parametrization.

Curve evolution schemes for segmentation, implemented with level set methods, have become an important approach in computer vision. Previous work has modeled evolving contours which are curves in 2D or surfaces in 3D. Our objective is to explore recent mathematical work enabling the evolution of manifolds of higher co-dimension. We consider 1D curves in 3D (codimension-two) for the application of automatically, segmenting blood vessels in volumetric magnetic resonance angiography (MRA) images. This paper describes the theoretical foundations of our system, CURVES, then provides segmentation results compared against segmentation obtained interactively by a neurosurgeon. Segmentation of bronchi in lung computed tomography (CT) scans are also presented. The new experiments, comparisons to manual segmentation, and sample comparison to the use of a codimension-one regularization force are the primary contributions of this report.

We present a novel geometric approach for solving the stereo problem for an arbitrary number of images (= or >2). It is based upon the definition of a variational principle that must be satisfied by the surfaces of the objects in the scene and their images. The Euler-Lagrange equations that are deduced from the variational principle provide a set of partial differential equations (PDE's) that are used to deform an initial set of surfaces which then move toward the objects to be detected. The level set implementation of these PDE's potentially provides an efficient and robust way of achieving the surface evolution and to deal automatically with changes in the surface topology during the deformations, i.e., to deal with multiple objects. Results of an implementation of our theory also dealing with occlusion and visibility are presented on synthetic and real images.

In this paper, we begin to explore the evolution of curves of the projective plane according to a family of intrinsic equations generalizing a "projective heat equation". This is motivated by previous work for the Euclidean and the affine case, as well as by applications in the perception of two-dimensional shapes. We establish the projective arclength evolution and the projective curvature evolution. Among this family of equations, we point out the ones preserving an important property of the Euclidean and affine heat equations that was not preserved in the projective case: a curve with constant curvature should remain such a curve during its evolution.