Fast joint estimation of silhouettes and dense 3D geometry from multiple images

We propose a probabilistic formulation of joint silhouette extraction and 3D reconstruction given a series of calibrated 2D images. Instead of segmenting each image separately in order to construct a 3D surface consistent with the estimated silhouettes, we compute the most probable 3D shape that gives rise to the observed color information. The probabilistic framework, based on Bayesian inference, enables robust 3D reconstruction by optimally taking into account the contribution of all views. We solve the arising maximum a posteriori shape inference in a globally optimal manner by convex relaxation techniques in a spatially continuous representation. For an interactively provided user input in the form of scribbles specifying foreground and background regions, we build corresponding color distributions as multivariate Gaussians and find a volume occupancy that best fits to this data in a variational sense. Compared to classical methods for silhouette-based multiview reconstruction, the proposed approach does not depend on initialization and enjoys significant resilience to violations of the model assumptions due to background clutter, specular reflections, and camera sensor perturbations. In experiments on several real-world data sets, we show that exploiting a silhouette coherency criterion in a multiview setting allows for dramatic improvements of silhouette quality over independent 2D segmentations without any significant increase of computational efforts. This results in more accurate visual hull estimation, needed by a multitude of image-based modeling approaches. We made use of recent advances in parallel computing with a GPU implementation of the proposed method generating reconstructions on volume grids of more than 20 million voxels in up to 4.41 seconds.     

Continuous global optimization in surface reconstruction from an oriented point cloud

We introduce a continuous global optimization method to the field of surface reconstruction from discrete noisy cloud of points with weak information on orientation. The proposed method uses an energy functional combining flux-based data-fit measures and a regularization term. A continuous convex relaxation scheme assures the global minima of the geometric surface functional. The reconstructed surface is implicitly represented by the binary segmentation of vertices of a 3D uniform grid and a triangulated surface can be obtained by extracting an appropriate isosurface. Unlike the discrete graph-cut solution, the continuous global optimization entails advantages like memory requirements, reduction of metrication errors for geometric quantities, and allowing globally optimal surface reconstruction at higher grid resolutions. We demonstrate the performance of the proposed method on several oriented point clouds captured by laser scanners. Experimental results confirm that our approach is robust to noise, large holes and non-uniform sampling density under the condition of very coarse orientation information.     

Optimization strategies for discrete multi-material stiffness optimization

Design of composite laminated lay-ups are formulated as discrete multi-material selection problems. The design problem can be modeled as a non-convex mixed-integer optimization problem. Such problems are in general only solvable to global optimality for small to moderate sized problems. To attack larger problem instances we formulate convex and non-convex continuous relaxations which can be solved using gradient based optimization algorithms. The convex relaxation yields a lower bound on the attainable performance. The optimal solution to the convex relaxation is used as a starting guess in a continuation approach where the convex relaxation is changed to a non-convex relaxation by introduction of a quadratic penalty constraint whereby intermediate-valued designs are prevented. The minimum compliance, mass constrained multiple load case problem is formulated and solved for a number of examples which numerically confirm the sought properties of the new scheme in terms of convergence to a discrete solution.     

Globally Optimal Estimates for Geometric Reconstruction Problems

We introduce a framework for computing statistically optimal estimates of geometric reconstruction problems. While traditional algorithms often suffer from either local minima or non-optimality—or a combination of both—we pursue the goal of achieving global solutions of the statistically optimal cost-function. Our approach is based on a hierarchy of convex relaxations to solve non-convex optimization problems with polynomials. These convex relaxations generate a monotone sequence of lower bounds and we show how one can detect whether the global optimum is attained at a given relaxation. The technique is applied to a number of classical vision problems: triangulation, camera pose, homography estimation and last, but not least, epipolar geometry estimation. Experimental validation on both synthetic and real data is provided. In practice, only a few relaxations are needed for attaining the global optimum.     

Global Minimization for Continuous Multiphase Partitioning Problems Using a Dual Approach

This paper is devoted to the optimization problem of continuous multi-partitioning, or multi-labeling, which is based on a convex relaxation of the continuous Potts model. In contrast to previous efforts, which are tackling the optimal labeling problem in a direct manner, we first propose a novel dual model and then build up a corresponding duality-based approach. By analyzing the dual formulation, sufficient conditions are derived which show that the relaxation is often exact, i.e. there exists optimal solutions that are also globally optimal to the original nonconvex Potts model. In order to deal with the nonsmooth dual problem, we develop a smoothing method based on the log-sum exponential function and indicate that such a smoothing approach leads to a novel smoothed primal-dual model and suggests labelings with maximum entropy. Such a smoothing method for the dual model also yields a new thresholding scheme to obtain approximate solutions. An expectation maximization like algorithm is proposed based on the smoothed formulation which is shown to be superior in efficiency compared to earlier approaches from continuous optimization. Numerical experiments also show that our method outperforms several competitive approaches in various aspects, such as lower energies and better visual quality.     

多视三维重构中连续能量模型的凸优化

利用融合了轮廓线及体视的序列图像信息,提出了一个面向多视三维重构的稳健能量模型;为了适配于可视性约束,提出一种针对该能量模型的连续全局优化方法;为了保证栅格连通性选择的一致性及独立性,实施了全局连续优化的超松弛离散化。实例证明,该方法的实用性好,极大地减少了算法处理的内存开销,实现了在更高分辨率上有效的多视重构。     

Brain state in a convex body

We study a generalization of the brain-state-in-a-box (BSB) model for a class of nonlinear discrete dynamical systems where we allow the states of the system to lie in an arbitrary convex body. The states of the classical BSB model are restricted to lie in a hypercube. Characterizations of equilibrium points of the system are given using the support function of a convex body. Also, sufficient conditions for a point to be a stable equilibrium point are investigated. Finally, we study the system in polytopes. The results in this special case are more precise and have simpler forms than the corresponding results for general convex bodies. The general results give one approach of allowing pixels in image reconstruction to assume more than two values.     

Auxiliary variables and two-step iterative algorithms in computer vision problems

We present a new mathematical formulation of some curve and surface reconstruction algorithms by the introduction of auxiliary variables. For deformable models and templates, the extraction of a shape is obtained through the minimization of an energy composed of an internal regularization term (not necessary in the case of parametric models) and an external attraction potential. Two-step iterative algorithms have been often used where, at each iteration, the model is first locally deformed according to the potential data attraction and then globally smoothed (or fitted in the parametric case).We show how these approaches can be interpreted as the introduction of auxiliary variables and the minimization of a two-variables energy. The first variable corresponds to the original model we are looking for, while the second variable represents an auxiliary shape close to the first one. This permits to transform an implicit data constraint defined by a non convex potential into an explicit convex reconstruction problem. This approach is much simpler since each iteration is composed of two simple to solve steps. Our formulation permits a more precise setting of parameters in the iterative scheme to ensure convergence to a minimum.We show some mathematical properties and results on this new auxiliary problem, in particular when the potential is a function of the distance to the closest feature point. We then illustrate our approach for some deformable models and templates.     

Graph Matching by Simplified Convex-Concave Relaxation Procedure

The convex and concave relaxation procedure (CCRP) was recently proposed and exhibited state-of-the-art performance on the graph matching problem. However, CCRP involves explicitly both convex and concave relaxations which typically are difficult to find, and thus greatly limit its practical applications. In this paper we propose a simplified CCRP scheme, which can be proved to realize exactly CCRP, but with a much simpler formulation without needing the concave relaxation in an explicit way, thus significantly simplifying the process of developing CCRP algorithms. The simplified CCRP can be generally applied to any optimizations over the partial permutation matrix, as long as the convex relaxation can be found. Based on two convex relaxations, we obtain two graph matching algorithms defined on adjacency matrix and affinity matrix, respectively. Extensive experimental results witness the simplicity as well as state-of-the-art performance of the two simplified CCRP graph matching algorithms.     

Carved Visual Hulls for Image-Based Modeling

This article presents a novel method for acquiring high-quality solid models of complex 3D shapes from multiple calibrated photographs. After the purely geometric constraints associated with the silhouettes found in each image have been used to construct a coarse surface approximation in the form of a visual hull, photoconsistency constraints are enforced in three consecutive steps: (1) the rims where the surface grazes the visual hull are first identified through dynamic programming; (2) with the rims now fixed, the visual hull is carved using graph cuts to globally optimize the photoconsistency of the surface and recover its main features; (3) an iterative (local) refinement step is finally used to recover fine surface details. The proposed approach has been implemented, and experiments with seven real data sets are presented, along with qualitative and quantitative comparisons with several state-of-the-art image-based-modeling algorithms.     

An evaluation of prefiltered reconstruction schemes for volume rendering

In this paper prefiltered reconstruction techniques are evaluated for volume-rendering applications. All the analyzed methods perform a discrete prefiltering as a preprocessing of the input samples in order to improve the quality of the continuous reconstruction afterwards. Various prefiltering schemes have been proposed to fulfill either spatial-domain or frequency domain criteria. According to our best knowledge, however, their thorough comparative study has not been published yet. Therefore we derive the frequency responses of the different prefilteredreconstruction techniques to analyze their global behavior such as aliasing or smoothing. Furthermore, we introduce a novel mathematical basis to compare also their spatial-domain behavior in terms of the asymptotic local error effect. For the sake of fair comparison, we use the same linear and cubic B-splines as basis functions but combined with different discrete prefilters. Our goal with this analysis is to help the potential users to select the optimal prefiltering scheme for their specific applications.     

Deriving a particle system from continuum mechanics for the animation of deformable objects

Mass-spring and particle systems have been widely employed in computer graphics to model deformable objects because they allow fast numerical solutions. In this work, we establish a link between these discrete models and classical mathematical elasticity. It turns out that discrete systems can be derived from a continuum model by a finite difference formulation and approximate classical continuum models unless the deformations are large. In this work, we present the derivation of a particle system from a continuum model, compare it to the models of classical elasticity theory, and assess its accuracy. In this way, we gain insight into the way discrete systems work and we are able to specify the correct scaling when the discretization is changed. Physical material parameters that describe materials in continuum mechanics are also used in the derived particle system.     

Multi-label Depth Estimation for Graph Cuts Stereo Problems

We describe here a method to compute the depth of a scene from a set of at least two images taken at known view-points. Our approach is based on an energy formulation of the 3D reconstruction problem which we minimize using a graph-cut approach that computes a local minimum whose energy is comparable (modulo a multiple constant) with the energy of the absolute minimum. As usually done, we treat the input images symmetrically, match pixels using photoconsistency, treat occlusion and visibility problems and consider a spatial regularization term which preserves discontinuities. The details of the graph construction as well as the proof of the correctness of the method are given. Moreover we introduce a multi-label refinement algorithm in order to increase the number of depth labels without significantly increasing the computational complexity. Finally we compared our algorithm with the results available in the Middlebury database.     

Whole-body modelling of people from multiview images to populate virtual worlds

In this paper a new technique is introduced for automatically building recognisable, moving 3D models of individual people. A set of multiview colour images of a person is captured from the front, sides and back by one or more cameras. Model-based reconstruction of shape from silhouettes is used to transform a standard 3D generic humanoid model to approximate a person's shape and anatomical structure. Realistic appearance is achieved by colour texture mapping from the multiview images. The results show the reconstruction of a realistic 3D facsimile of the person suitable for animation in a virtual world. The system is inexpensive and is reliable for large variations in shape, size and clothing. This is the first approach to achieve realistic model capture for clothed people and automatic reconstruction of animated models. A commercial system based on this approach has recently been used to capture thousands of models of the general public.     

Continuous and Discrete Trajectory Models for Dynamic Traffic Assignment

A continuous trajectory model is presented in which transportation networks are represented as topological constructs. The general formulation enhances existing analytic dynamic traffic assignment models by incorporating continuous single-link traffic flow models in a general, coherent, and relatively intuitive manner. Specific exact formulation based on a simplified kinematic wave traffic flow model with physical queues is presented as well.A discrete trajectory model is proposed as an approximation of the continuous model. The discrete model provides wide flexibility in choosing the level of aggregation with respect to time intervals, ranging from several hours, as typical in current practice of long-term travel forecasting models, to one second or less, as in microscopic simulations. An algorithm to find discrete approximate solutions is presented as well as accuracy measures to evaluate them. The effect of time resolution on model performance is examined by a numerical example.     

Meshfree-enriched simplex elements with strain smoothing for the finite element analysis of compressible and nearly incompressible solids

This paper presents a meshfree-enriched finite element formulation for triangular and tetrahedral elements in the analysis of two and three-dimensional compressible and nearly incompressible solids. The new formulation is first established in two-dimensional case by introducing a meshfree approximation into a linear triangular finite element with an enriched node. The interpolation functions of the four-noded triangular element are constructed by the meshfree convex approximations and are completed to a polynomial of degree one. The reference mapping using the constructed interpolation functions is shown to be invertible everywhere in the element and the global element area is proven to be conserved under a standard three-point integration rule. The triangular element formulation is extendable to the tetrahedral element in three-dimensional case. To provide a locking-free analysis for the nearly incompressible materials, an area-weighted strain smoothing is developed in conjunction with the enriched interpolation functions to yield a discrete divergence-free property at the integration point. The resultant element formulation with strain smoothing is shown to pass the patch test. To introduce the smoothed strain into Galerkin formulation, a modified Hu–Washizu variational principle is adopted to formulate the discrete equations. Since the Kronecker-delta property in element interpolation is held along the element boundary using meshfree convex approximation, boundary conditions can be treated in a standard way. Several numerical benchmarks are provided to demonstrate the effectiveness and accuracy of the proposed method.     

Minimal Basis Subspace Representation: A Unified Framework for Rigid and Non-rigid Motion Segmentation

Motion segmentation and non-rigid structure from motion are two challenging computer vision problems that have attracted numerous research interests. While the previous works handle these two problems separately, we present a general motion segmentation framework in this paper for solving these two seemingly different problems in a unified manner. At the heart of our general motion segmentation framework is a model selection mechanism based on finding the minimal basis subspace representation, by seeking the joint sparse representation of the data matrix. However, such formulation is NP-hard and we solve the convex proxy instead. Unlike other compressive sensing related works, this convex proxy solution is insufficient for our problem. The convex relaxation artefacts and noise yield multiple subspace representations, making identification of the exact number of motion subspaces challenging. We solve for the right number of subspaces by transforming this problem into a Facility Location problem with global cost and solve the factor graph formulation using max product belief propagation message passing.     

DISCRETE AND CONTINUOUS MODELS

Abstract

The growing influence of digital computing in systems modelling and simulation is leading to an increase in the use of discrete mathematical structures for describing models. While it is generally recognized that discrete methods and classical continuous methods both provide valuable tools for modelling, strong biases exist which depend on the modelling techniques that are traditional within specific disciplines. The choice of a modelling approach sometimes reflects the background of the model builder more strongly than it reflects the character of the problem to be solved. Since continuous methods have played the dominant role in scientific education, there are aspects of discrete modelling techniques and their relationship to continuous methods that are not widely recognized. The purpose of this article is to discuss some of these issues in order to dispel common criticisms of discrete techniques which are the result of unfamiliarity with discrete styles of mathematical thinking and a tendency to underestimate the degree of abstraction used in continuous approaches.     

Analysis and Approximation of Some Shape-from-Shading Models for Non-Lambertian Surfaces

The reconstruction of a 3D object or a scene is a classical inverse problem in Computer Vision. In the case of a single image this is called the Shape-from-Shading (SfS) problem and it is known to be ill-posed even in a simplified version like the vertical light source case. A huge number of works deals with the orthographic SfS problem based on the Lambertian reflectance model, the most common and simplest model which leads to an eikonal-type equation when the light source is on the vertical axis. In this paper, we want to study non-Lambertian models since they are more realistic and suitable whenever one has to deal with different kind of surfaces, rough or specular. We will present a unified mathematical formulation of some popular orthographic non-Lambertian models, considering vertical and oblique light directions as well as different viewer positions. These models lead to more complex stationary non-linear partial differential equations of Hamilton–Jacobi type which can be regarded as the generalization of the classical eikonal equation corresponding to the Lambertian case. However, all the equations corresponding to the models considered here (Oren–Nayar and Phong) have a similar structure so we can look for weak solutions to this class in the viscosity solution framework. Via this unified approach, we are able to develop a semi-Lagrangian approximation scheme for the Oren–Nayar and the Phong model and to prove a general convergence result. Numerical simulations on synthetic and real images will illustrate the effectiveness of this approach and the main features of the scheme, also comparing the results with previous results in the literature.