Optimal Metric Projections for Deformable and Articulated Structure-from-Motion

This paper describes novel algorithms for recovering the 3D shape and motion of deformable and articulated objects purely from uncalibrated 2D image measurements using a factorisation approach. Most approaches to deformable and articulated structure from motion require to upgrade an initial affine solution to Euclidean space by imposing metric constraints on the motion matrix. While in the case of rigid structure the metric upgrade step is simple since the constraints can be formulated as linear, deformability in the shape introduces non-linearities. In this paper we propose an alternating bilinear approach to solve for non-rigid 3D shape and motion, associated with a globally optimal projection step of the motion matrices onto the manifold of metric constraints. Our novel optimal projection step combines into a single optimisation the computation of the orthographic projection matrix and the configuration weights that give the closest motion matrix that satisfies the correct block structure with the additional constraint that the projection matrix is guaranteed to have orthonormal rows (i.e. its transpose lies on the Stiefel manifold). This constraint turns out to be non-convex. The key contribution of this work is to introduce an efficient convex relaxation for the non-convex projection step. Efficient in the sense that, for both the cases of deformable and articulated motion, the proposed relaxations turned out to be exact (i.e. tight) in all our numerical experiments. The convex relaxations are semi-definite (SDP) or second-order cone (SOCP) programs which can be readily tackled by popular solvers. An important advantage of these new algorithms is their ability to handle missing data which becomes crucial when dealing with real video sequences with self-occlusions. We show successful results of our algorithms on synthetic and real sequences of both deformable and articulated data. We also show comparative results with state of the art algorithms which reveal that our new methods outperform existing ones.     

Maximum Likelihood Coordinates

Any point inside a d-dimensional simplex can be expressed in a unique way as a convex combination of the simplex's vertices, and the coefficients of this combination are called the barycentric coordinates of the point. The idea of barycentric coordinates extends to general polytopes with n vertices, but they are no longer unique if n > d+1. Several constructions of such generalized barycentric coordinates have been proposed, in particular for polygons and polyhedra, but most approaches cannot guarantee the non-negativity of the coordinates, which is important for applications like image warping and mesh deformation. We present a novel construction of non-negative and smooth generalized barycentric coordinates for arbitrary simple polygons, which extends to higher dimensions and can include isolated interior points. Our approach is inspired by maximum entropy coordinates, as it also uses a statistical model to define coordinates for convex polygons, but our generalization to non-convex shapes is different and based instead on the project-and-smooth idea of iterative coordinates. We show that our coordinates and their gradients can be evaluated efficiently and provide several examples that illustrate their advantages over previous constructions.     

联合LBS和Snake的3D人体外形和运动跟踪方法

为了解决基于多目视频轮廓信息的3D人体外形和运动跟踪问题,提出一种联合线性混合蒙皮和Snake变形模型的算法框架.首先建立人物对象的蒙皮模型,以每一帧多目同步视频的轮廓作为输入,采用一种基于剪影轮廓的可视外壳重建算法,使得作为3D特征的可视外壳保持了局部细节且更加光滑;并使用关节型迭代最近点算法进行匹配以捕获出每一帧骨架子空间下的人物3D外形及运动;再一次使用当前帧的多目轮廓信息,让Snake内外力共同作用于人物网格模型上的顶点,使之自由地趋近于目标对象.使用带ground-truth的合成数据进行对比实验的结果表明,该方法因同时使用3D误差约束和2D误差约束,提高了跟踪精度.     

A fast approach to deformable surface 3D tracking

Deformable surface 3D tracking is a severely under-constrained problem and great efforts have been made to solve it. A recent state-of-the-art approach solves this problem by formulating it as a second order cone programming (SOCP) problem. However, one drawback of this approach is that it is time-consuming. In this paper, we propose an effective method for 3D deformable surface tracking. First, we formulate the deformable surface tracking problem as a linear programming (LP) problem. Then, we solve the LP problem with an algorithm which converges superlinearly rather than bisection algorithm whose convergence speed is linear. Our experimental studies on synthetic and real data have demonstrated the proposed method can not only reliably recover 3D structures of surfaces but also run faster than the state-of-the-art method.     

Deformable model for estimating clothed and naked human shapes from a single image

Estimation of human shape from images has numerous applications ranging from graphics to surveillance. A single image provides insufficient constraints (e.g. clothing), making human shape estimation more challenging. We propose a method to simultaneously estimate a person’s clothed and naked shapes from a single image of that person wearing clothing. The key component of our method is a deformable model of clothed human shape. We learn our deformable model, which spans variations in pose, body, and clothes, from a training dataset. These variations are derived by the non-rigid surface deformation, and encoded in various low-dimension parameters. Our deformable model can be used to produce clothed 3D meshes for different people in different poses, which neither appears in the training dataset. Afterward, given an input image, our deformable model is initialized with a few user-specified 2D joints and contours of the person. We optimize the parameters of the deformable model by pose fitting and body fitting in an iterative way. Then the clothed and naked 3D shapes of the person can be obtained simultaneously. We illustrate our method for texture mapping and animation. The experimental results on real images demonstrate the effectiveness of our method.     

Multi-view Performance Capture of Surface Details

This paper presents a novel approach to recover true fine surface detail of deforming meshes reconstructed from multi-view video. Template-based methods for performance capture usually produce a coarse-to-medium scale detail 4D surface reconstruction which does not contain the real high-frequency geometric detail present in the original video footage. Fine scale deformation is often incorporated in a second pass by using stereo constraints, features, or shading-based refinement. In this paper, we propose an alternative solution to this second stage by formulating dense dynamic surface reconstruction as a global optimization problem of the densely deforming surface. Our main contribution is an implicit representation of a deformable mesh that uses a set of Gaussian functions on the surface to represent the initial coarse mesh, and a set of Gaussians for the images to represent the original captured multi-view images. We effectively find the fine scale deformations for all mesh vertices, which maximize photo-temporal-consistency, by densely optimizing our model-to-image consistency energy on all vertex positions. Our formulation yields a smooth closed form energy with implicit occlusion handling and analytic derivatives. Furthermore, it does not require error-prone correspondence finding or discrete sampling of surface displacement values. We demonstrate our approach on a variety of datasets of human subjects wearing loose clothing and performing different motions. We qualitatively and quantitatively demonstrate that our technique successfully reproduces finer detail than the input baseline geometry.     

A Super-Resolution Framework for High-Accuracy Multiview Reconstruction

We present a variational framework to estimate super-resolved texture maps on a 3D geometry model of a surface from multiple images. Given the calibrated images and the reconstructed geometry, the proposed functional is convex in the super-resolution texture. Using a conformal atlas of the surface, we transform the model from the curved geometry to the flat charts and solve it using state-of-the-art and provably convergent primal–dual algorithms. In order to improve image alignment and quality of the texture, we extend the functional to also optimize for a normal displacement map on the surface as well as the camera calibration parameters. Since the sub-problems for displacement and camera parameters are non-convex, we revert to relaxation schemes in order to robustly estimate a minimizer via sequential convex programming. Experimental results confirm that the proposed super-resolution framework allows to recover textured models with significantly higher level-of-detail than the individual input images.     

Surface deformation models for nonrigid 3D shape recovery

Three-dimensional detection and shape recovery of a nonrigid surface from video sequences require deformation models to effectively take advantage of potentially noisy image data. Here, we introduce an approach to creating such models for deformable 3D surfaces. We exploit the fact that the shape of an inextensible triangulated mesh can be parameterized in terms of a small subset of the angles between its facets. We use this set of angles to create a representative set of potential shapes, which we feed to a simple dimensionality reduction technique to produce low-dimensional 3D deformation models. We show that these models can be used to accurately model a wide range of deforming 3D surfaces from video sequences acquired under realistic conditions.     

Lossless convexification of a class of optimal control problems with non-convex control constraints

We consider a class of finite time horizon optimal control problems for continuous time linear systems with a convex cost, convex state constraints and non-convex control constraints. We propose a convex relaxation of the non-convex control constraints, and prove that the optimal solution of the relaxed problem is also an optimal solution for the original problem, which is referred to as the lossless convexification of the optimal control problem. The lossless convexification enables the use of interior point methods of convex optimization to obtain globally optimal solutions of the original non-convex optimal control problem. The solution approach is demonstrated on a number of planetary soft landing optimal control problems.     

A Family of Barycentric Coordinates for Co‐Dimension 1 Manifolds with Simplicial Facets

We construct a family of barycentric coordinates for 2D shapes including non‐convex shapes, shapes with boundaries, and skeletons. Furthermore, we extend these coordinates to 3D and arbitrary dimension. Our approach modifies the construction of the Floater‐Hormann‐Kós family of barycentric coordinates for 2D convex shapes. We show why such coordinates are restricted to convex shapes and show how to modify these coordinates to extend to discrete manifolds of co‐dimension 1 whose boundaries are composed of simplicial facets. Our coordinates are well‐defined everywhere (no poles) and easy to evaluate. While our construction is widely applicable to many domains, we show several examples related to image and mesh deformation.     

Flexible simulation of deformable models using discontinuous Galerkin FEM

We propose a simulation technique for elastically deformable objects based on the discontinuous Galerkin finite element method (DG FEM). In contrast to traditional FEM, it overcomes the restrictions of conforming basis functions by allowing for discontinuous elements with weakly enforced continuity constraints. This added flexibility enables the simulation of arbitrarily shaped, convex and non-convex polyhedral elements, while still using simple polynomial basis functions. For the accurate strain integration over these elements we propose an analytic technique based on the divergence theorem. Being able to handle arbitrary elements eventually allows us to derive simple and efficient techniques for volumetric mesh generation, adaptive mesh refinement, and robust cutting. Furthermore, we show DG FEM not to suffer from locking artifacts even for nearly incompressible materials, a problem that in standard FEM requires special handling.     

Model-based human shape reconstruction from multiple views

Image-based modelling allows the reconstruction of highly realistic digital models from real-world objects. This paper presents a model-based approach to recover animated models of people from multiple view video images. Two contributions are made, a multiple resolution model-based framework is introduced that combines multiple visual cues in reconstruction. Second, a novel mesh parameterisation is presented to preserve the vertex parameterisation in the model for animation. A prior humanoid surface model is first decomposed into multiple levels of detail and represented as a hierarchical deformable model for image fitting. A novel mesh parameterisation is presented that allows propagation of deformation in the model hierarchy and regularisation of surface deformation to preserve vertex parameterisation and animation structure. The hierarchical model is then used to fuse multiple shape cues from silhouette, stereo and sparse feature data in a coarse-to-fine strategy to recover a model that reproduces the appearance in the images. The framework is compared to physics-based deformable surface fitting at a single resolution, demonstrating an improved reconstruction accuracy against ground-truth data with a reduced model distortion. Results demonstrate realistic modelling of real people with accurate shape and appearance while preserving model structure for use in animation.     

Distributed algorithm for target localization in wireless sensor networks using RSS and AoA measurements

This paper addresses target localization problem in a cooperative 3-D wireless sensor network (WSN). We employ a hybrid system that fuses distance and angle measurements, extracted from the received signal strength (RSS) and angle-of-arrival (AoA) information, respectively. Based on range measurement model and simple geometry, we derive a novel non-convex estimator based on the least squares (LS) criterion. The derived non-convex estimator tightly approximates the maximum likelihood (ML) one for small noise levels. We show that the developed non-convex estimator is suitable for distributed implementation, and that it can be transformed into a convex one by applying a second-order cone programming (SOCP) relaxation technique. We also show that the developed non-convex estimator can be transformed into a generalized trust region sub-problem (GTRS) framework, by following the squared range (SR) approach. The proposed SOCP algorithm for known transmit powers is then generalized to the case where the transmit powers are different and not known. Furthermore, we provide a detailed analysis of the computational complexity of the proposed algorithms. Our simulation results show that the new estimators have excellent performance in terms of the estimation accuracy and convergence, and they confirm the effectiveness of combining two radio measurements.     

Waste minimization in irregular stock cutting

This paper addresses a category of two dimensional NP-hard knapsack problem in which a given convex/non-convex planner items (polygons) have to be cut out of a single convex/non-convex master surface (stock). This cutting process is found in many industrial applications such as sheet metal processes, home-textile, garment, wood, leather and paper industries. An approach is proposed to solve this problem, which depends on the concept of the difference between the area of a collection of polygons and the area of their convex hull. The polygon assignment inside the stock is subjected to feasibility tests to avoid overlapping, namely, angle test, bound test, point inclusion and polygon intersection test. An iterative scheme is used to generate different polygon placements while optimizing the objective function. Computer software is developed to solve and optimize the problem under consideration. Few examples are conducted for different combinations of convex, non-convex items and stocks. Well-known benchmark problems from the literature are tested and compared with our approach. The results of our algorithm have an interesting computational time and can compete with the results of previous work in some particular problems. The computational performance of the developed software indicates the efficiency of the algorithm for solving 2-D irregular cutting of non-convex polygons out of non-convex stock.     

Constrained Stochastic LQC: A Tractable Approach

Despite the celebrated success of dynamic programming for optimizing quadratic cost functions over linear systems, such an approach is limited by its inability to tractably deal with even simple constraints. In this paper, we present an alternative approach based on results from robust optimization to solve the stochastic linear-quadratic control (SLQC) problem. In the unconstrained case, the problem may be formulated as a semidefinite optimization problem (SDP). We show that we can reduce this SDP to optimization of a convex function over a scalar variable followed by matrix multiplication in the current state, thus yielding an approach that is amenable to closed-loop control and analogous to the Riccati equation in our framework. We also consider a tight, second-order cone (SOCP) approximation to the SDP that can be solved much more efficiently when the problem has additional constraints. Both the SDP and SOCP are tractable in the presence of control and state space constraints; moreover, compared to the Riccati approach, they provide much greater control over the stochastic behavior of the cost function when the noise in the system is distributed normally.     

Monocular Template-based Reconstruction of Inextensible Surfaces

We present a monocular 3D reconstruction algorithm for inextensible deformable surfaces. It uses point correspondences between a single image of the deformed surface taken by a camera with known intrinsic parameters and a template. The main assumption we make is that the surface shape as seen in the template is known. Since the surface is inextensible, its deformations are isometric to the template. We exploit the distance preservation constraints to recover the 3D surface shape as seen in the image. Though the distance preservation constraints have already been investigated in the literature, we propose a new way to handle them. Spatial smoothness priors are easily incorporated, as well as temporal smoothness priors in the case of reconstruction from a video. The reconstruction can be used for 3D augmented reality purposes thanks to a fast implementation. We report results on synthetic and real data. Some of them are compared to stereo-based 3D reconstructions to demonstrate the efficiency of our method.     

An augmented Lagrangian approach to non-convex SAO using diagonal quadratic approximations

Successful gradient-based sequential approximate optimization (SAO) algorithms in simulation-based optimization typically use convex separable approximations. Convex approximations may however not be very efficient if the true objective function and/or the constraints are concave. Using diagonal quadratic approximations, we show that non-convex approximations may indeed require significantly fewer iterations than their convex counterparts. The nonconvex subproblems are solved using an augmented Lagrangian (AL) strategy, rather than the Falk-dual, which is the norm in SAO based on convex subproblems. The results suggest that transformation of large-scale optimization problems with only a few constraints to a dual form via convexification need sometimes not be required, since this may equally well be done using an AL formulation.     

可变形带洞形状的表示与检测

可变形形状(shape)的表示与检测是图像处理领域的重要研究内容。提出了一种关于可变形带洞形状表示与检测的方法,采用带洞形状多边形表示可变形带洞目标形状,有效地解决了带洞形状中不同封闭曲线之间位置的表示关系;通过在带洞形状多边形中添加辅助边,将每条辅助边看成两条完全不相交的边的方法,将带洞形状多边形转化成不带洞的简单多边形,运用受限Delaunay三角剖分法(CDT)剖分多边形,得到关于带洞形状多边形的完全删除序列,运用非序列动态规划实现可变形带洞形状检测。实验结果表明,与其他相关方法相比,本文方法能够较有效地检测带洞形状目标。     

Evolutionary approach on connectivity-based sensor network localization

The sensor network localization based on connectivity can be modeled as a non-convex optimization problem. It can be argued that the actual problem should be represented as an optimization problem with both convex and non-convex constraints. A two-objective evolutionary algorithm is proposed which utilizes the result of all convex constraints to provide a starting point on the location of the unknown nodes and then searches for a solution to satisfy all the convex and non-convex constraints of the problem. The final solution can reach the most suitable configuration of the unknown nodes because all the information on the constraints (convex and non-convex) related to connectivity have been used. Compared with current models that only consider the nodes that have connections, this method considers not only the connection constraints, but also the disconnection constraints. As a MOEA (Multi-Objective Evolution Algorithm), PAES (Pareto Archived Evolution Strategy) is used to solve the problem. Simulation results have shown that better solution can be obtained through the use of this method when compared with those produced by other methods.     

Optical Flow Constraints on Deformable Models with Applications to Face Tracking

Optical flow provides a constraint on the motion of a deformable model. We derive and solve a dynamic system incorporating flow as a hard constraint, producing a model-based least-squares optical flow solution. Our solution also ensures the constraint remains satisfied when combined with edge information, which helps combat tracking error accumulation. Constraint enforcement can be relaxed using a Kalman filter, which permits controlled constraint violations based on the noise present in the optical flow information, and enables optical flow and edge information to be combined more robustly and efficiently. We apply this framework to the estimation of face shape and motion using a 3D deformable face model. This model uses a small number of parameters to describe a rich variety of face shapes and facial expressions. We present experiments in extracting the shape and motion of a face from image sequences which validate the accuracy of the method. They also demonstrate that our treatment of optical flow as a hard constraint, as well as our use of a Kalman filter to reconcile these constraints with the uncertainty in the optical flow, are vital for improving the performance of our system.