3D Shape Estimation from 2D Landmarks: A Convex Relaxation Approach

1. Introduction

• Jointly estimating shape and pose is nonconvex, and alternating updates can be initialization-sensitive and reach locally optimal solutions.The parameters are coupled: pose is needed to deform the model, while the 3D model is needed to estimate pose.Source: §1 · p. 1
• The augmented shape-space model represents shapes as linear combinations of rotatable basis shapes, linearly representing intrinsic deformation and viewpoint changes.Shape-space fitting estimates weights on predefined basis shapes from image landmarks.Source: §1 · p. 1
• Relaxing the orthogonality constraint converts the problem into a convex, spectral-norm-regularized linear inverse problem.The proposed formulation addresses the nonconvex joint-estimation challenge.Source: §1 · p. 1
• The paper develops an efficient algorithm to globally solve the proposed convex program.The paper then evaluates the method's merits and applicability in human pose and car shape estimation.Source: §1 · pp. 1–2

2. Related Work

• Shape-space fitting to 2D landmarks has been applied to human poses [35], cars, and faces.These are presented as examples of reconstruction applications.Source: §2 · p. 2
• Prior methods include sparse human-pose reconstruction, detector-assisted robust fitting [35], locality-enhanced dictionaries, and car reconstruction.Other approaches jointly localize landmarks and fit models, or match video trajectories to spatio-temporal pose models.Source: §2 · p. 2
• Because 3D model fitting to landmarks is a common intermediate step, the proposed convex formulation could serve as a building block in existing methods.The cited prior methods usually rely on nonconvex formulations that may be sensitive to initialization.Source: §2 · p. 2
• Unlike this paper's fixed-basis setting, nonrigid structure from motion typically estimates unknown basis shapes along with shape and pose variables.The paper's problem is analogous to fixing the bases and updating remaining variables in iterative NRSfM methods.Source: §2 · p. 2

3.1. Problem Statement

• The unknown 3D shape is modeled as a weighted combination of learned basis shapes and fitted to 2D landmarks under a weak-perspective camera assumption.The camera model is described as a good approximation when object depth is much smaller than camera distance.Source: §3.1 · p. 2
• The model accounts for the camera-to-basis frame transformation, while centralizing the data eliminates translation and absorbs the calibration scalar into the coefficients.The camera model uses the first two rows of the rotation matrix after this simplification.Source: §3.1 · pp. 2–3
• For complex variation, an over-complete dictionary represents shape as a sparse combination of atoms, and the fitting objective balances reprojection error with coefficient sparsity.The sparsity assumption corresponds to the shape lying in a union of subspaces approximating a nonlinear shape manifold.Source: §3.1 · p. 3

3.2. Proposed Model

• The proposed augmented shape-space model gives each basis shape a rotation, representing intrinsic deformation and viewpoint changes linearly in 2D and removing the bilinear form.The augmented linear space can also represent projected shapes that may be invalid; orthogonality and sparsity constraints reduce that possibility.Source: §3.2 · p. 3
• The orthogonality constraint is relaxed to a spectral-norm bound, using the convex hull of the Stiefel manifold as the unit spectral-norm ball.The convex hull of a scaled orthogonality constraint is a spectral-norm ball with radius equal to the absolute scale.Source: §3.2 · p. 3
• For noiseless recovery, the formulation minimizes the coefficient vector’s ℓ1 norm; the resulting linear inverse problem has theoretically analyzed exact-recovery conditions.The formulation estimates transformation matrices by minimizing their spectral norms, and the paper reports numerical tests of exact recovery.Source: §3.2 · p. 4
• With noise, the final formulation is a convex penalized least-squares problem whose spectral-norm regularization promotes fewer active bases and equal singular values in each transformation matrix.Reprojection error may be restricted to visible landmarks; missing landmarks can be inferred from their known locations on the basis shapes.Source: §3.2 · p. 4

3.3. Reconstruction

• After optimization, each coefficient is recovered from its transformation matrix’s spectral norm, and the third rotation row is obtained by crossing the first two rows.The paper assumes nonnegative coefficients, enforced when training the shape dictionary, to resolve sign ambiguity.Source: §3.3 · p. 4

4.1. Proximal operator of the spectral norm

• The proximal operator for the spectral norm is computed through singular values and the Moreau decomposition.The passage identifies the spectral norm with the ℓ∞ norm of the singular values and uses an ℓ1-ball projection.Source: §4.1 · p. 4

4.2. Algorithms

• The ADMM iteration uses the spectral-norm proximal operator to update each M_i and a closed-form quadratic update for Z.An auxiliary variable Z is introduced before alternating the updates.Source: §4.2 · p. 5
• Figure 1 reports the frequency of exact recovery on synthesized data.Source: Figure 1 · p. 5
• ADMM iterates converge to optimal solutions of the primal problem, which are also optimal for the original problem.Source: §4.2 · p. 5

5.1. Simulation

• Exact recovery reaches frequency 1 when the number of landmarks is sufficiently large and the underlying coefficients are truly sparse.The study evaluates 10 random instances per setting; recovery frequency drops in more difficult settings.Source: §5.1 · p. 5

5.2.1 Human Pose Estimation

• The human-pose evaluation trains on Subject 86 and tests on Subjects 13, 14, and 15 using a learned dictionary of 64 basis shapes.The selected subjects perform varied activities; the model uses 15 joints.Source: §5.2.1 · p. 6
• On Subject 15, the convex method clearly outperforms the alternatives and remains stable across 14 test sequences, including poses far from the mean shape.For poses close to the mean, all methods perform well; alternative-method accuracy degrades on the other examples.Source: §5.2.1 · pp. 6–7, Figure 2 · p. 6, Figure 4 · p. 7
• Convex initialization lowers alternating minimization's mean objective from 0.24 to 0.17, while Alternate+ estimation error remains worse than the convex method.The convex formulation's objective is different and is not compared directly.Source: §5.2.1 · pp. 6–7

5.2.2 Car Reconstruction

• Using about 40 visible landmarks, the proposed method reconstructs sedan, SUV, and pickup examples, while the alternative performs poorly on the SUV and truck.The dataset's models are reconstructed rather than true CAD models, so the paper presents qualitative results only; the proposed method also works with arbitrary initialization.Source: §5.2.2 · pp. 7–8, Figure 5 · p. 8

5.3. Computational Time

• Human-pose computation takes 0.33 seconds per frame, versus 0.44 seconds for alternating minimization and 3.02 seconds for PMP.The ADMM algorithm generally converges within 500 iterations to a stopping criterion of 10^-4.Source: §5.3 · p. 8

• The convex program aligns a 3D shape-space model to 2D landmarks with global optimality, using augmentation and spectral-norm regularization to represent 2D variability and penalize invalid cases.Source: §6 · p. 8
• Prior work theoretically analyzes exactness under assumptions [13]; here estimates met original constraints in most cases, while non-tight relaxations were left unrefined in reported results.The authors note that projecting rotations to SO(3) or enforcing shared basis rotations may help in rigid-object applications, but they did not use these steps in their experiments.Source: §6 · p. 8
• The method assumes given 2D landmarks and 3D–2D correspondences; proposed extensions for localization errors include ℓ1 loss with ADMM or RANSAC.The authors also identify integrating the shape model with landmark-localization methods as a possible way to localize landmarks and recover shapes simultaneously.Source: §6 · p. 8