Source-linked AI summary
Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach
Xiaowei Zhou, Menglong Zhu, Spyridon Leonardos, Kostas Daniilidis
TL;DR
Single-image 3D shape recovery from 2D correspondences is ambiguous, and sparse deformable models still require difficult joint estimation of shape and viewpoint. The paper replaces initialization-sensitive nonconvex optimization with a convex relaxation and efficient solver, reporting exact recovery, advantages over nonconvex methods, and applications to human poses and cars.
Problem
Single-image 3D shape estimation is ill-posed, while jointly estimating sparse shape coefficients and viewpoint produces a nonconvex optimization problem sensitive to initialization.
Method
The method uses rotatable basis shapes, relaxes the camera orthogonality constraint, solves the resulting spectral-norm-regularized convex program with ADMM, and models outlier correspondences.
Results
The method demonstrates exact recovery, advantages over alternative nonconvex methods especially with large shape variability and outliers, and reconstruction of human poses and car models from single images.
Takeaways & Limitations
The convex formulation provides a globally optimal framework for sparse 3D shape alignment and is applicable to human-pose and car-model reconstruction.
Takeaways & Limitations
The alternating baseline may get stuck at local minima with distant initialization, and rotation synchronization can fail when recovered rotations differ substantially.
Abstract
from arXiv · showhide
We investigate the problem of estimating the 3D shape of an object defined by a set of 3D landmarks, given their 2D correspondences in a single image. A successful approach to alleviating the reconstruction ambiguity is the 3D deformable shape model and a sparse representation is often used to capture complex shape variability. But the model inference is still a challenge due to the nonconvexity in optimization resulted from joint estimation of shape and viewpoint. In contrast to prior work that relies on a alternating scheme with solutions depending on initialization, we propose a convex approach to addressing this challenge and develop an efficient algorithm to solve the proposed convex program. Moreover, we propose a robust model to handle gross errors in the 2D correspondences. We demonstrate the exact recovery property of the proposed method, the advantage compared to the nonconvex baseline methods and the applicability to recover 3D human poses and car models from single images.
1 INTRODUCTION
The paper studies single-image 3D shape estimation using sparse deformable models, where shape and camera viewpoint must be inferred jointly despite an ill-posed, nonconvex problem. It proposes a convex relaxation with an efficient solver and outlier handling.
- Motivation: Single-image 3D estimation is ill-posed, motivating deformable shape models that use visual shape knowledge to constrain reconstruction.The paper represents shapes with landmarks and basis shapes, including sparse representations for complex human-pose variability.
- Problem: Jointly estimating shape and viewpoint creates a nonconvex problem with orthogonality constraints, while alternating methods can depend on initialization and lack global-convergence guarantees.The viewpoint is needed to fit the model to 2D observations, and the model is needed to estimate viewpoint.
- Approach: The proposed method uses an augmented shape space with rotatable basis shapes to represent intrinsic deformation and viewpoint changes linearly.It relaxes the camera orthogonality constraint and formulates the problem as a spectral-norm-regularized least-squares convex program.
- Approach: An ADMM-based algorithm solves the convex program efficiently, including a closed-form proximal operator for the spectral norm and an extension for outlier correspondences.The paper also reports additional rotation synchronization, experiments, and learned-detector examples relative to its earlier version.
2 RELATED WORK
Related work models 3D shapes with deformable or sparse representations and addresses reconstruction through specialized, nonconvex, nearest-neighbor, or domain-specific methods. The paper positions its convex formulation as a potential building block or initialization for existing approaches.
- Deformable models: Deformable-model methods fit 3D shapes to image features for applications including face modeling, car modeling, and fine-grained recognition.These approaches commonly use landmarks or other image-derived structures to connect 2D observations with 3D models.
- Sparse pose models: Sparse representations were introduced to model structural variability in human poses, with later work adding robust estimation, dictionary locality, or joint-angle constraints.These methods are primarily developed for human-pose reconstruction from still images or videos.
- Category-specific reconstruction: Category-specific reconstruction methods learn deformable models from collections of single images while fitting visual hulls or annotated landmarks.The paper's problem can be viewed as a subproblem of these broader model-inference approaches.
- Relation to prior optimization: Existing methods often rely on nonconvex optimization that may be initialization-sensitive, so the proposed convex formulation could provide a building block or better initialization.This is presented as a potential role rather than a demonstrated replacement for all related methods.
- Alternative approaches: Other approaches use nearest-neighbor retrieval followed by refinement or specialized human-pose models, but they trade generality against detailed reconstruction or object-specific design.Nearest-neighbor methods can produce detailed reconstructions, while human-pose alternatives are not straightforwardly generalizable to other objects.
- Nonrigid structure from motion: Nonrigid structure-from-motion methods address related deformable-shape variables from multi-frame correspondences, typically with unknown basis shapes and matrix-factorization or iterative procedures.The paper instead fixes basis shapes and updates the remaining variables in an analogous subproblem.
3 PROBLEM STATEMENT
The problem is to recover a landmark-defined 3D shape from single-view 2D projections using a sparse basis-shape model and a weak-perspective camera. Its joint coefficient-and-viewpoint optimization is nonconvex and can become trapped in local minima.
- Camera model: The weak-perspective camera projects a landmark-defined 3D shape into 2D, with calibration simplified when object depth is small relative to camera distance.The scalar calibration factor depends on focal length and object distance.
- Shape model: Because there are more unknowns than equations, the shape is constrained to a linear combination of predefined basis shapes with coefficients estimated from image landmarks.This reduces reconstruction to fitting several coefficients rather than estimating every 3D landmark independently.
- Projection constraints: The camera transformation includes rotation and translation, with rotation constrained to SO(3) by orthogonality and unit-determinant conditions.The formulation uses the first two rotation rows and eliminates translation by centralizing the data.
- Sparse representation: Sparse shape recovery penalizes the ℓ1 norm of the coefficient vector alongside reprojection error, using sparsity as a convex surrogate for coefficient cardinality.The basis dictionary can be over-complete because low-dimensional linear spaces may not capture complex variation such as human poses.
- Baseline optimization: The resulting joint optimization is nonconvex, so alternating minimization updates coefficients and camera rotation separately using ℓ1 solvers and SVD or local rotation optimization.The algorithm initializes both variables and iterates until convergence.
- Limitation: Because of nonconvexity, alternating minimization may get stuck at local minima when initialization is far from the true solution.This initialization sensitivity motivates the paper's convex alternative.
4 PROPOSED METHODS
The paper linearizes intrinsic shape deformation and viewpoint changes, then replaces orthogonality constraints with a spectral-norm convex relaxation for shape recovery. The resulting formulation is convex, supports global solution, and can accommodate noise and missing landmarks.
- 4.1 Convex relaxation: The augmented shape-space model represents 2D effects of intrinsic deformation and viewpoint changes linearly, removing the bilinear form needed for convexification.Each basis shape has an associated rotation, and M_i is formed from the coefficient and the first two rows of that rotation.
- 4.1 Convex relaxation: The orthogonality constraint is relaxed to spectral-norm bounds, yielding a convex program that estimates orthogonal matrices through a linear inverse formulation.The tightest convex relaxation imposes ∥M_i∥2 ≤ |c_i|, and the resulting formulation minimizes spectral norms.
- 4.1 Convex relaxation: The proposed convex program is theoretically linked to exact recovery conditions, with numerical experiments used to demonstrate its exact recovery property.
- 4.1 Convex relaxation: For noisy observations, the final formulation is a convex penalized least-squares problem solvable globally with an efficient algorithm developed using ADMM.The method derives an auxiliary-variable formulation and uses the proximal operator of the spectral norm within ADMM.
- 4.1 Convex relaxation: Spectral-norm minimization simultaneously encourages sparse basis activation and equal singular values, promoting orthogonal transformation matrices.The formulation can also incorporate observed-landmark weights for missing or invisible landmarks and hallucinate unobserved locations from the reconstructed model.
4.2 Proximal operator of the spectral norm
The spectral-norm proximal operator is derived by applying spectral-function properties and Moreau decomposition to the singular values. Its behavior both equalizes singular values toward orthogonality and drives sufficiently small matrices to zero.
- 4.2 Proximal operator of the spectral norm: The proximal operator of the spectral norm reduces the matrix problem to the proximal operator of the singular-value ℓ∞-norm.The ℓ1-norm projection appears through Moreau decomposition because ℓ1 and ℓ∞ are dual norms.
- 4.2 Proximal operator of the spectral norm: When the projection lies on the ℓ1-ball boundary, the singular-value differences become equal and the resulting matrix is orthogonal.
- 4.2 Proximal operator of the spectral norm: When the input singular values lie inside the ℓ1-ball, the projection leaves them unchanged and the proximal solution becomes the all-zero matrix.
4.3 Optimization
The proposed optimization uses ADMM to solve the convex formulation, with auxiliary-variable updates that converge to the original problem’s optimum.
- 4.3 Optimization: ADMM solves the convex formulation through alternating updates until convergence.An auxiliary variable and augmented Lagrangian organize the optimization steps.
- 4.3 Optimization: The M_i updates are separated into proximal problems based on the spectral-norm proximal operator.This enables each M_i to be updated independently.
- 4.3 Optimization: The remaining subproblem has a closed-form solution because its objective is quadratic.
- 4.3 Optimization: The generated sequences converge to the optimal solution of the reformulated problem and the original convex formulation.The implementation adopts standard convergence criteria and adaptive step-size tuning.
4.4 Reconstruction
The paper reconstructs 3D shape from the estimated matrices using direct or synchronized rotation-based procedures, with refinement available when synchronization is imperfect.
- 4.4 Reconstruction: Two reconstruction algorithms recover 3D shape after solving the convex matrix-estimation problem.
- 4.4 Reconstruction: Direct reconstruction recovers coefficients and rotations from each estimated matrix under a nonnegative coefficient convention.The convention removes the sign ambiguity by imposing c_i ≥ 0 during dictionary learning.
- 4.4 Reconstruction: Rotation synchronization estimates a coefficient vector and a single rotation from the recovered matrices.
- 4.4 Reconstruction: The synchronization step corresponds to metric projection and can be solved exactly by semidefinite programming or approximately by a faster algorithm.
- 4.4 Reconstruction: Because synchronization need not solve the original problem, its output can initialize alternating minimization, although dispersed rotations may yield a meaningless consensus.The paper reports that better initialization can improve alternating-minimization performance.
4.5 Outlier modeling
The method models gross correspondence errors explicitly with a sparse outlier matrix and learns compact shape dictionaries when many training shapes make direct basis selection impractical.
- 4.5 Outlier modeling: Gross errors in detected 2D correspondences are modeled explicitly with a sparse matrix E.The formulation is modified to incorporate outliers directly.
- 4.5 Outlier modeling: With outlier modeling, translation T cannot be eliminated by centralizing the data at the beginning.
- 4.5 Outlier modeling: The outlier-robust optimization problem can also be solved using ADMM.The corresponding algorithm is provided in the appendix.
- 4.5 Outlier modeling: Dictionary learning becomes necessary for very large shape collections because it summarizes training variability with a sparse representation.The learned basis shapes and coefficients jointly balance reconstruction error and representation sparsity.
- 4.5 Outlier modeling: Figure 3 reports exact-recovery frequency across varied problem settings using intensity to indicate success frequency.
5 EXPERIMENTS
Experiments show that the convex formulation can exactly recover sparse shapes in favorable regimes, outperform alternating and PMP baselines for human poses, and estimate car shapes from sparse visible landmarks. Its benefits include better initialization and robustness to noise and outliers, although refinement can worsen reconstructions when dictionary representation or initialization is inadequate.
- 5.1 Exact recovery: 100-trial simulations achieve exact recovery with frequency 1 when landmark counts are sufficiently large and true coefficients are sufficiently sparse.Recovery is exact when relative error is below 10^-3; performance decreases in more ill-posed settings with fewer observations or less sparsity.
- 5.2 Human pose estimation: The convex method consistently outperforms nonconvex methods across human motions, while convex initialization yields lower alternating-optimization objectives.The comparison uses 3D Euclidean joint-location errors, and the convex and convex+refine methods have comparable mean errors on average.
- 5.2 Human pose estimation: Refinement can worsen reconstruction when the convex solution is a poor initialization or the learned dictionary cannot represent the target pose well.This limitation is reported for rotation synchronization and refinement after convex estimation.
- 5.2 Human pose estimation: The convex method produces smoother human-pose reconstructions than nonconvex methods, which can become trapped at local optima and exhibit abrupt temporal changes.All methods perform well for walk and run examples, whereas more complex motions expose the instability of nonconvex optimization.
- 5.2 Human pose estimation: Under outlier corruption, robust models outperform original models, and the convex robust method performs better than the alternating robust method.Gaussian-noise experiments likewise report consistently better performance for convex methods across all tested noise levels.
- 5.3 Car model estimation: For car estimation, the proposed method succeeds with arbitrary initialization, whereas nonlinear optimization fails on SUV and truck examples that deviate far from the mean shape.The FG3DCar experiments use roughly 40 visible landmarks per image and compare sedan, SUV, and pickup-truck models.
6 DISCUSSION
The paper concludes that its convex formulation achieves global optimality, supports robust alignment under outliers, and applies to reconstructing human poses and car models.
- 6 DISCUSSION: The proposed method aligns sparse 3D deformable shapes to 2D correspondences through a globally optimal convex program.It uses augmented shape space and spectral-norm regularization, and extends the model to handle outliers.
- 6 DISCUSSION: The method demonstrates exact recovery and advantages over nonconvex alternatives, especially with large shape variability and outliers.
- 6 DISCUSSION: The framework reconstructs human poses and car models from image correspondences.Figure 10 shows qualitative car results using detected 2D landmarks, with inliers and outliers distinguished by landmark error.
APPENDIX A ALGORITHM TO SOLVE THE ROBUST MODEL
The robust-model solver rewrites the optimization with an auxiliary variable, iterates update steps, and uses soft-thresholding for an ℓ1-norm proximal subproblem.
- APPENDIX A ALGORITHM TO SOLVE THE ROBUST MODEL: The algorithm rewrites the robust-model problem by introducing an auxiliary variable and an augmented Lagrangian.
- APPENDIX A ALGORITHM TO SOLVE THE ROBUST MODEL: The solver iterates its update steps until convergence.
- APPENDIX A ALGORITHM TO SOLVE THE ROBUST MODEL: The ℓ1-norm proximal subproblem is solved with elementwise soft-thresholding.The operator applies sign-preserving thresholding to each matrix element.
- APPENDIX A ALGORITHM TO SOLVE THE ROBUST MODEL: There is no theoretical convergence guarantee for ADMM on the multi-block problem, although it converged in the reported experiments.
APPENDIX B ALGORITHM TO SOLVE DICTIONARY LEARNING
The dictionary-learning algorithm alternates nonnegative sparse coding with dictionary updates, using projected gradient descent until convergence.
- APPENDIX B ALGORITHM TO SOLVE DICTIONARY LEARNING: The dictionary-learning cost is rewritten using the concatenated basis matrix before optimization.
- APPENDIX B ALGORITHM TO SOLVE DICTIONARY LEARNING: Projected gradient descent minimizes the rewritten objective and produces the dictionary updates.
- APPENDIX B ALGORITHM TO SOLVE DICTIONARY LEARNING: The procedure alternates nonnegative sparse coding with dictionary updating until convergence.