Quasi-perspective Projection Model: Theory and Application to Structure and Motion Factorization from Uncalibrated Image Sequences

This paper addresses the problem of factorization-based 3D reconstruction from uncalibrated image sequences. Previous studies on structure and motion factorization are either based on simplified affine assumption or general perspective projection. The affine approximation is widely adopted due to its simplicity, whereas the extension to perspective model suffers from recovering projective depths. To fill the gap between simplicity of affine and accuracy of perspective model, we propose a quasi-perspective projection model for structure and motion recovery of rigid and nonrigid objects based on factorization framework. The novelty and contribution of this paper are as follows. Firstly, under the assumption that the camera is far away from the object with small lateral rotations, we prove that the imaging process can be modeled by quasi-perspective projection, which is more accurate than affine model from both geometrical error analysis and experimental studies. Secondly, we apply the model to establish a framework of rigid and nonrigid factorization under quasi-perspective assumption. Finally, we propose an Extended Cholesky Decomposition to recover the rotation part of the Euclidean upgrading matrix. We also prove that the last column of the upgrading matrix corresponds to a global scale and translation of the camera thus may be set freely. The proposed method is validated and evaluated extensively on synthetic and real image sequences and improved results over existing schemes are observed.     

Nonrigid motion analysis based on dynamic refinement of finiteelement models

We propose new algorithms for accurate nonrigid motion tracking. Given an initial model representing general knowledge of the object, a set of sparse correspondences, and incomplete or missing information about geometry or material properties, we can recover dense motion vectors using finite element models. The method is based on the iterative analysis of the differences between the actual and predicted behaviors. Unknown parameters are recovered using an iterative descent search for the best nonlinear finite element model that approximates nonrigid motion of the given object. During this search process, we not only estimate material properties, but also infer dense point correspondences from our initial set of sparse correspondences. Thus, during tracking, the model is refined which, in turn, improves tracking quality. Experimental results demonstrate the success of the proposed algorithm. Our work demonstrates the possibility of accurate quantitative analysis of nonrigid motion in range image sequences with objects consisting of multiple materials and 3D volumes     

Shape and nonrigid motion estimation through physics-basedsynthesis

A physics-based framework for 3-D shape and nonrigid motion estimation for real-time computer vision systems is presented. The framework features dynamic models that incorporate the mechanical principles of rigid and nonrigid bodies into conventional geometric primitives. Through the efficient numerical simulation of Lagrange equations of motion, the models can synthesize physically correct behaviors in response to applied forces and imposed constraints. Applying continuous Kalman filtering theory, a recursive shape and motion estimator that employs the Lagrange equations as a system model is developed. The system model continually synthesizes nonrigid motion in response to generalized forces that arise from the inconsistency between the incoming observations and the estimated model state. The observation forces also account formally for instantaneous uncertainties and incomplete information. A Riccati procedure updates a covariance matrix that transforms the forces in accordance with the system dynamics and prior observation history. Experiments involving model fitting and tracking of articulated and flexible objects from noisy 3-D data are described     

Real-time data driven deformation with affine bones

Data driven deformation is increasingly important in computer graphics and interactive applications. From given mesh example sequences, we train a deformation predictor and manipulate a specific style of surface deformation interactively using only a small number of control points. The latest approach of learning the connection between rigid bone transformations and control points uses a statistically based framework, called canonical correlation analysis. In this paper, we extend this approach to a skinned mesh with affine bones, each of which conveys a nonrigid affine transformation. However, it is difficult to discover the underlying relationship between control points and nonrigid transformations. To address this issue, we present a two-layer regression framework; one layer being from control points to rigid and the other layer being from rigid to nonrigid transformations. Our contributions also include bone-vertex weight smoothing, enabling the distribution of each bone’s influence across neighboring vertices. We can alleviate distortion around regions where nearby bones undergo various transformations and improve deformations reaching beyond the learned subspaces. Experimental results show that our method can achieve more general deformations including flexible muscle bulges or twists. The performance of our implementation is comparable to the latest approach.     

Recovery of nonrigid motion and structure

The authors introduce a physically correct model of elastic nonrigid motion. This model is based on the finite element method, but decouples the degrees of freedom by breaking down object motion into rigid and nonrigid vibration or deformation modes. The result is an accurate representation for both rigid and nonrigid motion that has greatly reduced dimensionality, capturing the intuition that nonrigid motion is normally coherent and not chaotic. Because of the small number of parameters involved, this representation is used to obtain accurate overstrained estimates of both rigid and nonrigid global motion. It is also shown that these estimates can be integrated over time by use of an extended Kalman filter, resulting in stable and accurate estimates of both three-dimensional shape and three-dimensional velocity. The formulation is then extended to include constrained nonrigid motion. Examples of tracking single nonrigid objects and multiple constrained objects are presented     

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.     

Direct estimation of range flow on deformable shape from a videorate range camera

A method of estimating range flow (space displacement vector field) on nonrigid as well as rigid objects from a sequence of range images is described. This method can directly estimate the deformable motion parameters by solving a system of linear equations that are obtained from substituting a linear transformation of nonrigid objects expressed by the Jacobian matrix into motion constraints based on an extension of the conventional scheme used in intensity image sequences. The range flow is directly computed by substituting these estimated motion parameters into the linear transformation. The algorithm is supported by experimental estimations of range flow on a sheet of paper, a piece of cloth, human skin, and a rubber balloon being inflated, using real range image sequences acquired by a video rate range camera     

Recursive 3-D Visual Motion Estimation Using Subspace Constraints

A structure from motion algorithm is described which recovers structure and camera position, modulo a projective ambiguity. Camera calibration is not required, and camera parameters such as focal length can be altered freely during motion. The structure is updated sequentially over an image sequence, in contrast to schemes which employ a batch process. A specialisation of the algorithm to recover structure and camera position modulo an affine transformation is described, together with a method to periodically update the affine coordinate frame to prevent drift over time. We describe the constraint used to obtain this specialisation.Structure is recovered from image corners detected and matched automatically and reliably in real image sequences. Results are shown for reference objects and indoor environments, and accuracy of recovered structure is fully evaluated and compared for a number of reconstruction schemes. A specific application of the work is demonstrated—affine structure is used to compute free space maps enabling navigation through unstructured environments and avoidance of obstacles. The path planning involves only affine constructions.     

Merging artificial objects with marker-less video sequences based on the interacting multiple model method

Inserting synthetic objects into video sequences has gained much interest in recent years. Fast and robust vision-based algorithms are necessary to make such an application possible. Traditional pose tracking schemes using recursive structure from motion techniques adopt one Kalman filter and thus only favor a certain type of camera motion. We propose a robust simultaneous pose tracking and structure recovery algorithm using the interacting multiple model (IMM) to improve performance. In particular, a set of three extended Kalman filters (EKFs), each describing a frequently occurring camera motion in real situations (general, pure translation, pure rotation), is applied within the IMM framework to track the pose of a scene. Another set of EKFs,one filter for each model point, is used to refine the positions of the model features in the 3-D space. The filters for pose tracking and structure refinement are executed in an interleaved manner. The results are used for inserting virtual objects into the original video footage. The performance of the algorithm is demonstrated with both synthetic and real data. Comparisons with different approaches have been performed and show that our method is more efficient and accurate.     

Point set registration: coherent point drift

Point set registration is a key component in many computer vision tasks. The goal of point set registration is to assign correspondences between two sets of points and to recover the transformation that maps one point set to the other. Multiple factors, including an unknown nonrigid spatial transformation, large dimensionality of point set, noise, and outliers, make the point set registration a challenging problem. We introduce a probabilistic method, called the Coherent Point Drift (CPD) algorithm, for both rigid and nonrigid point set registration. We consider the alignment of two point sets as a probability density estimation problem. We fit the Gaussian mixture model (GMM) centroids (representing the first point set) to the data (the second point set) by maximizing the likelihood. We force the GMM centroids to move coherently as a group to preserve the topological structure of the point sets. In the rigid case, we impose the coherence constraint by reparameterization of GMM centroid locations with rigid parameters and derive a closed form solution of the maximization step of the EM algorithm in arbitrary dimensions. In the nonrigid case, we impose the coherence constraint by regularizing the displacement field and using the variational calculus to derive the optimal transformation. We also introduce a fast algorithm that reduces the method computation complexity to linear. We test the CPD algorithm for both rigid and nonrigid transformations in the presence of noise, outliers, and missing points, where CPD shows accurate results and outperforms current state-of-the-art methods.     

A model for compression and classification of face data structures

In this paper we present a 3-D model with physical properties which simplifies the analysis and the synthesis of deformable faces and solids. Our model presents three relevant particularities. First, it describes the external envelope of faces with 1-D finite elements assembled with a new 3-connected mesh topology. Second, the mesh deformations are analysed with a modal analysis. Because our model associates these two particularities, the number of rigid modes given by the modal analysis is equal to the number of 1-D finite elements, which is also the half of the number of Degrees of Freedom (DOF). This number of rigid modes is a basic characteristic of our model. The second half of modes constitutes the nonrigid modes. Third, we use these rigid modes and the first nonrigid mode to synthesize a mean face named a photo-fit identikit or class, around which we synthesize face varieties by action on secondary nonrigid modes. Our physical 3-D model allows compression of face data structures because a greater number of secondary nonrigid modes can be suppressed to define a class or its varieties, and because the synthesis of varieties does not need more information storage than their classes. Our physical 3-D model allows classification of face data structures because we can associate an objective measure to each synthesized face. We can measure the deformation between a variety and its photo-fit identikit.     

Real-time tracking of multiple objects in space-variant vision based on magnocellular visual pathway

In this paper, we propose a space-variant image representation model based on properties of magnocellular visual pathway, which perform motion analysis, in human retina. Then, we present an algorithm for the tracking of multiple objects in the proposed space-variant model. The proposed space-variant model has two effective image representations for object recognition and motion analysis, respectively. Each image representation is based on properties of two types of ganglion cell, which are the beginning of two basic visual pathways; one is parvocellular and the other is magnocellular. Through this model, we can get the efficient data reduction capability with no great loss of important information. And, the proposed multiple objects tracking method is restricted in space-variant image. Typically, an object-tracking algorithm consists of several processes such as detection, prediction, matching, and updating. In particular, the matching process plays an important role in multiple objects tracking. In traditional vision, the matching process is simple when the target objects are rigid. In space-variant vision, however, it is very complicated although the target is rigid, because there may be deformation of an object region in the space-variant coordinate system when the target moves to another position. Therefore, we propose a deformation formula in order to solve the matching problem in space-variant vision. By solving this problem, we can efficiently implement multiple objects tracking in space-variant vision.     

Three-dimensional human motion modeling by back-projection based on image-based camera calibration

This article proposes a back-projection technique for the modeling of 3-D human motion that performs camera calibration using the multiple video sequences obtained. This technique calculates an affine camera matrix by the factorization method, and performs back-projection under the affine camera model. The proposed technique needs neither a 3-D camera calibration tool nor markers for shape recovery, and can recover human motion from silhouette images. We also propose a shadow detector and eliminator using color information and normalized cross correlation for the robust extraction and elimination of shadows. Experimental results show the effectiveness of the proposed technique.     

Efficient planar object tracking and parameter estimation usingcompactly represented cubic B-spline curves

In this paper, we consider the problem of matching 2D planar object curves from a database, and tracking moving object curves through an image sequence. The first part of the paper describes a curve data compression method using B-spline curve approximation. We present a new constrained active B-spline curve model based on the minimum mean square error (MMSE) criterion, and an iterative algorithm for selecting the “best” segment border points for each B-spline curve. The second part of the paper describes a method for simultaneous object tracking and affine parameter estimation using the approximate curves and profiles. We propose a novel B-spline point assignment algorithm which incorporates the significant corners for interpolating corresponding points on the two curves to be compared. A gradient-based algorithm is presented for simultaneously tracking object curves, and estimating the associated translation, rotation and scaling parameters. The performance of each proposed method is evaluated using still images and image sequences containing simple objects     

一种新的FAST-Snake目标跟踪方法

提出一种新的FAST-Snake目标跟踪方法,利用改进的FAST角点特征匹配来估计目标轮廓在帧间的全局仿射变换,将投影轮廓点作为Snake模型的初始化轮廓.为提高跟踪实时性,在Snake能量模型中定义了先验约束能,并用限定搜索方向的贪婪算法（Greedy algorithm）实现局部轮廓优化.实验包括三维目标数据库及真实场景视频,验证了提出方法的均方误差（Means quare error,MSE）及收敛速度评估均优于对比算法,并具备对复杂运动及局部遮挡的适应能力.     

Tracking While Zooming Using Affine Transfer and Multifocal Tensors

This paper presents algorithms for tracking unknown objects in the presence of zoom. Since prior models are unavailable, point and line matches in affine views are used to characterize the structure and to transfer a fixation point into new images in a sequence. Because any affine projection matrix is permitted, the intrinsic camera parameters such as focal length may change freely. Also, since the techniques do not require long feature tracks, a further desirable property is insensitivity to partial occlusion caused, for instance, by part of the object falling off the image plane while zooming in. If only point matches are available, a previous method based on factorization is applied. When also incorporating lines, the affine trifocal and quadrifocal tensors are used for tracking in monocular and stereo systems respectively. Methods for computing the tensors, minimizing algebraic error, are developed. In comparison with their projective counterparts, the affine tensors offer significant advantages in terms of computation time and convenience of parameterization, and the relations between the different tensors are shown to be much simpler. Successful tracking is demonstrated on several real image sequences.     

TILT: Transform Invariant Low-Rank Textures

In this paper, we propose a new tool to efficiently extract a class of “low-rank textures” in a 3D scene from user-specified windows in 2D images despite significant corruptions and warping. The low-rank textures capture geometrically meaningful structures in an image, which encompass conventional local features such as edges and corners as well as many kinds of regular, symmetric patterns ubiquitous in urban environments and man-made objects. Our approach to finding these low-rank textures leverages the recent breakthroughs in convex optimization that enable robust recovery of a high-dimensional low-rank matrix despite gross sparse errors. In the case of planar regions with significant affine or projective deformation, our method can accurately recover both the intrinsic low-rank texture and the unknown transformation, and hence both the geometry and appearance of the associated planar region in 3D. Extensive experimental results demonstrate that this new technique works effectively for many regular and near-regular patterns or objects that are approximately low-rank, such as symmetrical patterns, building facades, printed text, and human faces.     

A factorization-based approach for articulated nonrigid shape, motion and kinematic chain recovery from video

Recovering articulated shape and motion, especially human body motion, from video is a challenging problem with a wide range of applications in medical study, sport analysis and animation, etc. Previous work on articulated motion recovery generally requires prior knowledge of the kinematic chain and usually does not concern the recovery of the articulated shape. The non-rigidity of some articulated part, e.g. human body motion with nonrigid facial motion, is completely ignored. We propose a factorization-based approach to recover the shape, motion and kinematic chain of an articulated object with nonrigid parts altogether directly from video sequences under a unified framework. The proposed approach is based on our modeling of the articulated non-rigid motion as a set of intersecting motion subspaces. A motion subspace is the linear subspace of the trajectories of an object. It can model a rigid or non-rigid motion. The intersection of two motion subspaces of linked parts models the motion of an articulated joint or axis. Our approach consists of algorithms for motion segmentation, kinematic chain building, and shape recovery. It handles outliers and can be automated. We test our approach through synthetic and real experiments and demonstrate how to recover articulated structure with non-rigid parts via a single-view camera without prior knowledge of its kinematic chain.     

Rigid body segmentation and shape description from dense opticalflow under weak perspective

We present an algorithm for identifying and tracking independently moving rigid objects from optical flow. Some previous attempts at segmentation via optical flow have focused on finding discontinuities in the flow field. While discontinuities do indicate a change in scene depth, they do not in general signal a boundary between two separate objects. The proposed method uses the fact that each independently moving object has a unique epipolar constraint associated with its motion. Thus motion discontinuities based on self-occlusion can be distinguished from those due to separate objects. The use of epipolar geometry allows for the determination of individual motion parameters for each object as well as the recovery of relative depth for each point on the object. The algorithm assumes an affine camera where perspective effects are limited to changes in overall scale. No camera calibration parameters are required. A Kalman filter based approach is used for tracking motion parameters with time     

Adaptive-size meshes for rigid and nonrigid shape analysis andsynthesis

A physically based modeling method that uses adaptive-size meshes to model surfaces of rigid and nonrigid objects is presented. The initial model uses an a priori determined mesh size. However, the mesh size increases or decreases dynamically during surface reconstruction to locate nodes near surface areas of interest (like high curvature points) and to optimize the fitting error. Further, presented with multiple 3-D data frames, the mesh size varies as the data surface undergoes nonrigid motion. This model is used to reconstruct 3-D surfaces, analyze the nonrigid motion, track the corresponding points in nonrigid motion, and create graphic animation and visualization. The method was tested on real range data, on simulated nonrigid motion, and on real data for the left ventricular motion