Particle-SfT: A Provably-Convergent, Fast Shape-from-Template Algorithm

Abstract

The Shape-from-Template (SfT) problem is to recover the 3D shape of a deformable object from a single image, given a 3D template and a deformation constraint. We propose Particle-SfT, a new SfT algorithm which handles isometric and non-isometric deformations. We build Particle-SfT upon a particle system guided by deformation and reprojection constraint projections. Reconstruction is achieved by evolving particles to a globally attractive equilibrium, while taking observable external forces such as gravity into account, if any. Particle-SfT may be used to refine an existing initial shape. However, in practice we simply use the template as initial guess. This is because, as opposed to the existing refining methods, Particle-SfT has an extremely wide convergence basin. Particle-SfT is also faster than the existing refining methods. This is because it moves pieces of the shape’s mesh independently to achieve larger step size by optimal constraint projection. We proved its convergence to a fixed-point. We experimented it with synthetic and real data. It has the same accuracy as the best performing isometric method and consistently outperforms all existing elastic methods in almost all cases, while being much faster.

1 Introduction

A deformable object, like this paper that may be gently bent between your fingers, may take many different shapes whose projection produces the same image. Inferring the 3D shape of an object from a single image thus requires more constraints. SfT uses a 3D template of the object and a deformation constraint as priors to recover the unknown shape from the given input image. SfT has been well studied for the isometric deformation (Brunet et al. 2014; Chhatkuli et al. 2014; Bartoli et al. 2015; Östlund et al. 2012; Salzmann and Fua 2011) and marginally studied for elastic deformations (Malti et al. 2013, 2015; Haouchine et al. 2014). Because SfT is fundamentally a non-convex problem, an SfT method is either initializing or refining. An initializing method computes a suboptimal solution, which is iteratively improved by a refining method. One of the main current open problems in SfT is finding a refining method which would be fast and have a large convergence basin. This problem exists for both the isometric and non-isometric deformation cases.

We propose Particle-SfT, an SfT algorithm which uses a particle model guided by optimal constraint projections. We design our particle model specifically to embed the two fundamental constraint sets required in SfT to converge to the observed shape, the deformation constraints and the reprojection constraints. We assume that keypoint correspondences between the template and the image are given. These may be computed prior to shape reconstruction using for instance SIFT (Lowe 1999) followed by (Pilet et al. 2008; Pizarro and Bartoli 2012). Our SfT method then proceeds in two steps: instantiation and evolution. We first instantiate particles at the keypoint correspondences and, if necessary, add extra particles so that a homogeneous distribution is obtained on the template’s surface. Each particle has a position, a mass and is subject to a set of internal and external constraints and forces. The internal constraints are used to represent SfT’s deformation constraints. They are created by ‘sewing’ the particles to each other along a specific pattern, which is specifically designed to prevent effects such as folding of the object’s surface. The external constraints are used to represent SfT’s reprojection constraints. They are created as strong attractors between each particle and its corresponding sight-line traced from the perspective camera, modeling projection to the input image. We then evolve the particle system by recursively applying optimal constraint projections until equilibrium.

Particle-SfT has three strong features. First, it can be controlled both in position and in force, and can thus evolve under any known external forces such as gravity. Second, it can represent materials of various stiffness. In other words, Particle-SfT can represent very stiff objects such as a piece of paper and extensible objects such as cloth, in a unified framework. Existing algorithms are all specific to a type of deformation, whether isometric or elastic. In Particle-SfT, the internal constraints are expressed by two stiffness parameters, one for stretching and one for bending. In practice, in the isometric case, this reduces to a single parameter, the one which controls the bending stiffness, since there is no stretching. In the elastic case both stiffness parameters are lower than one and may usually be chosen equal. The design of Particle-SfT would allow it to handle objects with inhomogeneous stiffness, should a stiffness map be provided in the template. Reconstructing extensible objects requires one to provide boundary conditions, which fit easily as external constraints in Particle-SfT. Third, Particle-SfT is fast. This is because it handles the constraints independently and optimally. Therefore it takes large and precise steps. Existing methods use local approximation of all the constraints (for instance using Gauss-Newton (Brunet et al. 2014)). This limits them to take smaller steps and to converge more slowly.

From a practical standpoint, Particle-SfT has many advantages. First, it has an extremely wide convergence basin due to the globally attractive equilibrium of the involved iterations. Second, Particle-SfT is algorithmically simple, has linear complexity in the number of particles and the number of iterations, and its constraints can be separated into groups of parallelizable isolated constraints (i.e., constraints that do not have common particles). Third, Particle-SfT yields similar results in accuracy to the best performing isometric SfT method and outperforms all existing elastic SfT methods in almost all cases. Importantly, existing elastic SfT methods all require one to provide a very good initialization whereas Particle-SfT converges to a sensible solution even when initialized very far from the solution. Third, Particle-SfT runs about 15 times faster than the refining isometric SfT method (Brunet et al. 2014) and at least 4 times faster than the refining elastic methods (Malti et al. 2013; Haouchine et al. 2014).

2 Previous Work

Shape-from-Template SfT methods may be grouped by the type of deformation constraint they implement on the object’s surface. Many use isometry, which preserves geodesic distances (Östlund et al. 2012; Bartoli et al. 2015; Brunet et al. 2014; Chhatkuli et al. 2014; Perriollat et al. 2011; Salzmann and Fua 2009, 2011; Salzmann et al. 2008; Varol et al. 2012), and is by far the most studied model in SfT. Some complement this constraint by a learnt statistical model (Salzmann and Fua 2011). Others consider non-isometric models, namely conformity, which preserves angles (Bartoli et al. 2015), linear elasticity (Malti et al. 2013, 2015) and non-linear elasticity (Haouchine et al. 2014). The latter three methods depend on the material’s Young modulus. Stretchable surfaces were also reconstructed using shading (Moreno-Noguer et al. 2009).

SfT methods may be initializing or refining. Initializing methods have a convex formulation (Östlund et al. 2012; Perriollat et al. 2011; Salzmann and Fua 2009, 2011; Salzmann et al. 2008; Varol et al. 2012; Malti et al. 2015) or are analytical solutions (Bartoli et al. 2015; Chhatkuli et al. 2014). Refining methods use non-convex numerical optimization (Brunet et al. 2014; Malti et al. 2013; Haouchine et al. 2014). Initializing methods are typically less accurate than refining methods, and are often used to provide an initialization to a refining method. Particle-SfT is a refining method.

Physics- and particle-based methods In terms of physics-based models, the Finite Element Method (FEM) was used in tracking (Kass et al. 1988; Metaxas 1993), to reconstruct beam-like structures (Ilić et al. 2007), and in Non-Rigid Structure-from-Motion (Agudo et al. 2014) (NRSfM). Particle dynamics was used to track particle like rigid objects (e.g., billiard balls, basketballs) and articulated body motion in 3D using a learnt model (Salzmann and Urtasun 2011), and in NRSfM (Agudo and Moreno-Noguer 2015).

NRSfM and SfT are related but different problems. The NRSfM methods proposed in (Agudo et al. 2014, 2016; Agudo and Moreno-Noguer 2015) are template-free but reconstruct small incremental deformations. The NRSfM methods in (Agudo et al. 2014; Agudo and Moreno-Noguer 2015) need at least three sequential images. They work with the orthographic camera model and have non-convex cost functions requiring careful initialization for Levenberg-Marquardt refinement. The particle-based NRSfM method in (Agudo and Moreno-Noguer 2015) uses forces (Newtonian dynamics). The NRSfM method in (Agudo et al. 2016) works with the perspective camera model, needs two sequential images with previously reconstructed shape, and uses forces. Our method uses the perspective camera, a template, a single image, projections (projective dynamics) and reconstructs a large deformation.

In computer graphics, physics-based models (Provot 1996) and projective particle-based models (Müller et al. 2006) were used to produce highly realistic object deformations. The convergence of projective particle dynamics approaches was however not proved so far.

We use a projective particle-based model for the first time in SfT, and prove the convergence of Particle-SfT, the proposed companion algorithm, using the fixed-point theory (Agarwal et al. 2001) and contractive mappings (Rhoades 1977).

Particle Shape-from-Template compared to previous methods The Particle-SfT algorithm is refining, iterative and provably convergent. It is simple, fast and versatile (it handles isometric and non-isometric deformations) compared to other SfT methods. It is guided by optimal constraint projections and, if available, by external forces.

We present our contributions as follows. First, we give the reprojection and deformation constraints and their optimal projections. These projections are the key elements of Particle-SfT but they cannot be directly used as the deformation constraint is not position attractive. Second, we combine these reprojection and deformation constraint projections to obtain a particle-pairwise joint constraint mapping. This yields an attractive behavior on the particle pairs towards the sought-after shape of the deformed object. We then put forward three propositions and a new fixed-point theorem about the joint constraint mappings. These propositions and the new fixed-point theorem are necessary to show the convergence of Particle-SfT. We prove the convergence of Particle-SfT in Proposition 3, whose premises are established in Propositions 1 and 2, and Theorem 1. Proposition 1 proves the asymptotic regularity of a joint constraint mapping and this guarantees the minimization of its related cost function. Proposition 2 shows that a joint constraint mapping satisfies a generalized contractiveness condition which allows us to study the convergence of the set of joint constraint mappings. The new fixed-point theorem, Theorem 1, unifies a family of asymptotically regular mappings satisfying the same generalized contractiveness condition. It gives the necessary conditions on the uniqueness of the fixed-point solution. This shows that the solution is not always unique. Finally, we experimentally validate Particle-SfT against existing methods.

3 Problem Formulation

We first give the notation and assumptions, then define the particle system and finally formulate the problem.

Notation We use the following notation:

• $n\in \mathbb {N}$ is the number of particles.

• $\mathbf {x}\in \mathbb {R}^{3}$ is a 3D point, ${\underline{\mathbf{x}}} \,=\, [\,\mathbf {x}_{1}^{\top },\ldots ,\mathbf {x}_{n}^{\top }\,]^{\top }\in \mathbb {R}^{3n}$ is a 3D shape vector and ${\underline{\widehat{\mathbf{x}}}}\in \mathbb {R}^{3n}$ is its estimate. Positions are in meters.

• $\mathcal {M}$ is a closed and bounded (i.e., compact) subset of the Euclidean space $\mathbb {R}^{3n}$, and the metric $\,\,d~:~\mathcal {M}~\times ~\mathcal {M}~\,\rightarrow \,~\mathbb {R}_{+}~\,=\,[0,\infty )$ is defined as:

  $$\begin{aligned} d({\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}})\,\,=\,\, \sum _{i=1}^{n}\,||\,\mathbf {x}_{i} \,-\,\mathbf {y}_{i} \,||\,, \forall \,{\underline{\mathbf{x}}},{\underline{\mathbf{y}}}\,\in \,\mathcal {M}\,\subset \,\mathbb {R}^{3n} \end{aligned}$$

  (1)

  where $||\,\cdot \,||$ is the Euclidean norm.

• $\mathbf {u}\in \mathbb {R}^{2}$ is a 2D image point and ${\underline{\mathbf{u}}} \,=\, [\,\mathbf {u}_{1}^{\top },\ldots ,\mathbf {u}_{n}^{\top }\,]^{\top }\in \mathbb {R}^{2n}$ is an image shape vector. Image point coordinates are in pixels.

• $\mathbf {f}\in \mathbb {R}^{3}$ is a 3D external force vector and ${\underline{\mathbf{f}}} \,=\, [\,\mathbf {f}_{1}^{\top },\ldots ,\mathbf {f}_{n}^{\top }\,]^{\top }\in \mathbb {R}^{3n}$ is a shape force vector. Forces are in Newtons. Forces are given.

• $m\in \mathbb {R}_{+}$ is the mass of a particle and ${\underline{\mathbf{m}}} \,=\, [\,m_{1},\ldots ,m_{n}\,]^{\top }\in \mathbb {R}^{n}_{+}$ is the shape mass vector. Masses are in kilograms.

• $\mathbf {K} \in \mathbb {R}^{3\times 3}$ is the intrinsic parameter matrix of the perspective camera model for the input image. The intrinsic parameter matrix is known.

• $\mathcal {E}\,=\,\{\,ij\,\}$ is the edge set containing the indices of connected pairs of particles.

• $\mathcal {S}\,=\,\{\, s_{_{ij}} \,\}$ is the set of the correction strengths of the edges defined in $\mathcal {E}$.

• $\mathcal {R}\,\subset \,\mathcal {M}\,\subset \,\mathbb {R}^{3n}$ is the reprojection constraint set of the particles.

• $\mathcal {D}_{\,ij} \,\subset \,\mathcal {M}\,\subset \,\mathbb {R}^{3n}$ is a deformation constraint set for one pair of particles $ij\,\in \,\mathcal {E}$.

• $\mathcal {T} \,=\,(\,{\underline{\mathbf{x}}}_{_{\mathcal {T}}},\,\rho _{_{\mathcal {T}}},\,s_{_{\mathcal {T}}},\,h_{_{\mathcal {T}}}\,)$ is the template with the shape ${\underline{\mathbf{x}}}_{_{\mathcal {T}}}$, density $\rho _{_{\mathcal {T}}}$, elasticity $s_{_{\mathcal {T}}}$ (e.g., Young’s modulus) and surface thickness $h_{_{\mathcal {T}}}$ parameters.

• $\mathcal {C}\,=\,\,\{\,(\mathbf {K},\,{\underline{\mathbf{u}}}),\,{\underline{\mathbf{f}}}\, \}$ is the external constraint parameter set.

Particle system The particle system $\mathcal {P}=(\,{\underline{\mathbf{x}}},\,\mathcal {E},\,\mathcal {S},\,{\underline{\mathbf{m}}}\,)$ is a model of the object. It imitates the behavior of the object by obeying the object’s internal deformation constraints as well as the object’s external constraints such as reprojection in the image and forces due to gravity. We instantiate the particle system’s shape with the template’s shape, i.e., ${\underline{\mathbf{x}}}\,=\,{\underline{\mathbf{x}}}_{_{\mathcal {T}}}$, the edge set $\mathcal {E}$ with the procedure described in Sect. 4.2, the correction strength set $\mathcal {S}$ as a function of the template’s elasticity parameter $s_{_{\mathcal {T}}}$ (the function is assumed to be known; this is discussed in Sect. 8), and masses ${\underline{\mathbf{m}}}$ from the template’s density parameter $\rho _{_{\mathcal {T}}}$ and the triangles issued of the particles’ Delaunay triangulation (Marton et al. 2009). More precisely, the mass of a particle is determined by summing one third of the mass of all triangles containing this particle. A triangle’s mass is the product of the material’s density and the triangle’s volume. In practice, for a set of particles homogeneously distributed on the template’s surface, a particle’s mass can be approximated well enough by dividing the object’s known mass by the number of particles.

Problem statement We look for a shape ${\underline{\mathbf{x}}}$ of particles $\mathcal {P}$ that best fits the deformation constraints and that satisfies the reprojection constraints:

$$\begin{aligned} \min _{{\underline{\mathbf{x}}}\,\in \,\mathcal {R}} \left( \,\, \sum _{ij\,\in \,\mathcal {E}} \ \ \min _{{\underline{\mathbf{y}}}\in \,\mathcal {D}_{\,ij}}\,\, d(\,{\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}}\,)\, \right) \end{aligned}$$

(2)

In this formulation, we chose to enforce perfect reprojection constraints. This is because they are provided by a direct measurement of the sought-after shape of the deformed object from an image. The deformation constraints however are approximate because, in reality, an object never deforms isometrically. There is always a non-isometric counterpart in the deformation, even if small. Enforcing perfect isometry on the deformed object would strongly push the object towards its rest shape. Another reason why we do not want to enforce perfect isometry is that the particle-based model is a discrete approximation of a surface and must not preserve the edges’ length exactly to be able to deform. Lastly, our experiments show that the obtained precision on the reconstructed 3D shapes is good, which confirms our modeling choice. We also prefer working on the constraints that are applied on the whole shape, although they affect only pairs of particles. This simplifies the formulation and derivation of equations. We solve problem (2) through an iterative algorithm, considering it as a common fixed-point problem of the joint constraint mappings i.e., reprojection and deformation constraint projections. We prove the convergence of our algorithm to a fixed point which is also a stable equilibrium point of problem (2). The solution provided by our algorithm is also robust to noise on the image points. This is because particles are connected to each other through multiple edges across the triangles of a triangulated surface mesh (shown in red in Fig. 2, left) forming a subset of the deformation constraints of the object. These larger distance connections across triangles make the particles less sensitive to depth errors induced by image noise, compared to the shorter ones (shown in black in Fig. 2, left).

4 Constraints and Mappings

4.1 Reprojection

Constraint We define the reprojection constraints between the particles’ positions and the shape reprojection set $\mathcal {R}$ as follows:

$$\begin{aligned} f_{\,_{i}}({\underline{\mathbf{x}}}) \,=\, ||\,\mathbf {x}_{i} \,-\, \mathtt {T}_{\, \mathtt {r}_{i}}\,\mathbf {x}_{i}\,||\,=\, 0 \,, i\,\in \,[1,\,n] \end{aligned}$$

(3)

where $\mathtt {T}_{\, \mathtt {r}}\in \mathbb {R}^{3\times 3}$ is an orthogonal projection of a particle onto its sight-line $\mathtt {r}\,\in \,\mathcal {R}$. We express a sight-line set as $\mathtt {r}_{i} = \{ \, \mathbf {O}\,+\,\theta \,{{\bar{\mathbf{p}}}_{i}}^{}\,\,|\,\,\theta \,\in \,\mathbb {R}\,\}$ where $\mathbf {O}\,=\,[0,0,0]^{\top }$ is the optical center of the camera and ${{\bar{\mathbf{p}}}_{i}}~=~\mathbf {p}_{i}~/~||\mathbf {p}_{i}||~\in \mathbb {R}^{3}$ are the known unit sight-line vectors obtained from the image shape vector ${\underline{\mathbf{u}}}$ as $\mathbf {p}_{i} \,=\, \mathbf {K}^{-1}\, \left[ \mathbf {u}_{i}^{\top },\, 1 \right] ^{\top }$, where $\mathbf {u}_{i}$ is the position of the i-th particle in the input image. Each sight-line $\mathtt {r}$ is a convex and linear set.

Fig. 1

Convex implicit signed distance function as deformation constraint

Mapping The orthogonal projection $\mathtt {T}_{\, \mathtt {r}}$, which solves the reprojection constraint (3) in one step by bringing the particle at $\mathbf {x}\notin \mathtt {r}$ back onto its sight-line $\mathtt {r}$, is defined as:

$$\begin{aligned} \mathtt {T}_{\, \mathtt {r}}\,\,=\,\, {{\bar{\mathbf{p}}}}^{}\,\,{{\bar{\mathbf{p}}}}^{\top } \end{aligned}$$

(4)

Note that $\mathtt {T}_{\, \mathtt {r}}\,\,\mathbf {x}$ always exists. Since a sight-line set $\mathtt {r}$ is convex and $\mathtt {T}_{\, \mathtt {r}}$ is its orthogonal projection (i.e., a nearest point mapping), then $\mathtt {T}_{\, \mathtt {r}}\,\,\mathbf {x}$ is a unique point. We handle the reprojection constraints of a pair of particles $p_{i}\,\in \,\mathcal {P}$ and $p_{j}\,\in \,\mathcal {P}$ in a shape ${\underline{\mathbf{x}}}\in \mathbb {R}^{3n}$ as:

$$\begin{aligned} {\underline{\mathbf{x}}} \,=\, \mathtt {T}_{\, \mathtt {R}_{\,ij}}\,\,\,{\underline{\mathbf{x}}} \end{aligned}$$

(5)

where $\mathtt {T}_{\, \mathtt {R}_{\,ij}} = \mathtt {diag}(\,\mathtt {I}_{3}\,,\,\ldots \,,\mathtt {I}_{3}\,,\, \mathtt {T}_{\, \mathtt {r}_{i}}\,,\,\,\mathtt {I}_{3}\,,\,\ldots \,,\mathtt {I}_{3}\,, \mathtt {T}_{\, \mathtt {r}_{j}}\,,\,\,\mathtt {I}_{3}\,,\,\ldots \,,\mathtt {I}_{3}\,)\in \mathbb {R}^{3n\,\times \,3n}$ with $\mathtt {I}_{3}$ being a $3\times 3$ identity matrix.

4.2 Deformation

Constraint We define a deformation constraint between a pair of connected particles at $\mathbf {x}_{i}$ and $\mathbf {x}_{j}$ of a shape ${\underline{\mathbf{x}}}$ through the following implicit convex signed distance function:

$$\begin{aligned} g_{_{ij}}({\underline{\mathbf{x}}}) \,=\, \,||\, \mathbf {x}_{i}\,-\,\mathbf {x}_{j} \,||\,-\, \ell _{ij} \,=\, 0 \,, ij\,\in \,\mathcal {E} \end{aligned}$$

(6)

where $\ell _{ij}$ is the known distance of the pair, obtained from the template. This deformation constraint tells us how far a deformed pair is from the closest equilibrium and also in which relative configuration (a positive value for a stretched pair and a negative value for a shrunk pair). An equilibrium is a relative placement of particles $p_{i}\,\in \,\mathcal {P}$ and $p_{j}\,\in \,\mathcal {P}$ anywhere in $\mathbb {R}^{3}$ such that $\,||\, \mathbf {x}_{i}\,-\,\mathbf {x}_{j} \,||\,=\, \ell _{ij}$.

Mapping Whenever $g_{_{ij}}({\underline{\mathbf{x}}})\,\ne \,0$, we would like to find the projection step $\vartriangle {\underline{\mathbf{x}}}$ which solves the deformation constraint as $g_{_{ij}}({\underline{\mathbf{x}}} \,\,+ \vartriangle {\underline{\mathbf{x}}})\,=\,0$. To do so, we fix one particle of a pair, say $p_{i}$ at $\mathbf {x}_{i}$, with respect to the other. This allows us to illustrate the convex signed distance function $g_{_{ij}}({\underline{\mathbf{x}}})$ as in Fig. 1. Remark that the shape of $g_{_{ij}}({\underline{\mathbf{x}}})$ between the positions of particles becomes linear. This is also true the other way around when the roles of particles $p_{i}$ and $p_{j}$ are exchanged.

Fig. 2

Meshing for deformation constraints (left). Parallelizable isolated constraints in red, green, blue and purple colors (right) (Color figure online)

Fixing one particle therefore lets us express $g_{_{ij}}({\underline{\mathbf{x}}}\,+\vartriangle {\underline{\mathbf{x}}}) = 0$ exactly with a first-order representation as:

$$\begin{aligned} g_{_{ij}}({\underline{\mathbf{x}}} \,+ \vartriangle {\underline{\mathbf{x}}})\,=\, g_{_{ij}}({\underline{\mathbf{x}}})\,+\,\nabla g_{_{ij}}({\underline{\mathbf{x}}})^{\top } \vartriangle {\underline{\mathbf{x}}} \,=\,0 \end{aligned}$$

(7)

Remark also that the gradient of $g_{_{ij}}({\underline{\mathbf{x}}})$ at a particle’s position is piecewise constant, and especially it does not vary between any point and the closest solution, e.g., the red circle in Fig. 1. We can thus solve constraint (7) with an exact projection step along the constant gradient direction:

$$\begin{aligned} \vartriangle {\underline{\mathbf{x}}}\,=\,-\, \frac{g_{_{ij}}({\underline{\mathbf{x}}})}{||\,\nabla g_{_{ij}}({\underline{\mathbf{x}}})\,||^{2}} \,\,\nabla g_{_{ij}}({\underline{\mathbf{x}}}) \end{aligned}$$

(8)

We now propose to solve constraint (6) in one step by moving both particles simultaneously with respect to each other by sharing the projection step (8) rather than moving only one with respect to the other. This is possible because the gradient vectors of $g_{_{ij}}({\underline{\mathbf{x}}})$ at the particles’ positions are aligned on the same 3D line passing through the particles’ positions $\mathbf {x}_{i}$ and $\mathbf {x}_{j}$. We share the projection step between the particles with respect to their mass ratios $\alpha _{i}\,=\,m_{j}/(m_{i}+m_{j})$ and $\alpha _{j}\,=\,m_{i}/(m_{i}+m_{j})$. The heavier a particle, the smaller its $\alpha$ and therefore the smaller its displacement. Remark that $\alpha _{i}\,+\,\alpha _{j}\,=\,1$. Therefore the sum of the displacements of both particles remains equal to the exact projection step length. We rewrite Eq. (8) explicitly for the displacement of particles $p_{i}$ and $p_{j}$ only as:

$$\begin{aligned} \left[ \begin{array}{c} \vartriangle \mathbf {x}_{i} \\ \vartriangle \mathbf {x}_{j} \end{array} \right] \,=\, \left[ \begin{array}{c} -\,\alpha _{i}\,\frac{g_{_{ij}}({\underline{\mathbf{x}}})}{||\,\nabla _{i}g_{_{ij}}({\underline{\mathbf{x}}})\,||^{2}} \,\,\nabla _{i}g_{_{ij}}({\underline{\mathbf{x}}})) \\ -\,\alpha _{j}\,\frac{g_{_{ij}}({\underline{\mathbf{x}}})}{||\,\nabla _{j}g_{_{ij}}({\underline{\mathbf{x}}})\,||^{2}} \,\,\nabla _{j}g_{_{ij}}({\underline{\mathbf{x}}})) \end{array} \right] \end{aligned}$$

(9)

where $\nabla _{i}g_{_{ij}}({\underline{\mathbf{x}}}) \,=\, (\mathbf {x}_{i}\,-\,\mathbf {x}_{j})/ ||\,\mathbf {x}_{i}\,-\,\mathbf {x}_{j}\,||\,\in \,\mathbb {R}^{3}$ is the gradient vector of $g_{_{ij}}$ with respect to the particle at $\mathbf {x}_{i}$, and where $\nabla _{j}g_{_{ij}}({\underline{\mathbf{x}}}) \,=\, -\,\nabla _{i}g_{_{ij}}({\underline{\mathbf{x}}}) \,\in \,\mathbb {R}^{3}$ is the gradient vector of $g_{_{ij}}$ with respect to the particle at $\mathbf {x}_{j}$. We also scale the displacements of particles with a correction strength $s_{_{ij}}\,\in \,(0,1]$ to introduce an elastic behavior on their deformation. The correction strength is directly related to the object material’s stiffness, and is provided with the template as it represents a characteristic of the object, similarly to Young’s modulus or any other mechanical parameter. Consequently, we design for the deformed pair of particles two weighted gradient-based orthogonal projections $^{_{^{j}}}\mathtt {T}_{^{_{i}}}~\in ~\mathbb {R}^{3\times 3}$ and $^{_{^{i}}}\mathtt {T}_{^{_{j}}}~\in ~\mathbb {R}^{3\times 3}$ to solve their deformation constraint (6) using (9) as:

$$\begin{aligned} ^{_{^{j}}}\mathtt {T}_{^{_{i}}}= & {} \left( \mathtt {I}_{3} \,\,-\,\, s_{_{ij}}\,\,\alpha _{i}\,\,\, g_{_{ij}}({\underline{\mathbf{x}}})\,\,\, \,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}})\,\, \dfrac{\mathbf {x}_{i}^{_{\top }}}{||\,\mathbf {x}_{i}\,||^{2}} \right) \end{aligned}$$

(10)

$$\begin{aligned} ^{_{^{i}}}\mathtt {T}_{^{_{j}}}= & {} \left( \mathtt {I}_{3} \,\,-\,\, s_{_{ij}}\,\,\alpha _{j}\,\,\, g_{_{ij}}({\underline{\mathbf{x}}})\,\,\, \,\nabla _{j}\, g_{_{ij}}({\underline{\mathbf{x}}})\,\, \dfrac{\mathbf {x}_{^{j}}^{_{\top }}}{||\,\mathbf {x}_{^{j}}\,||^{2}} \right) \end{aligned}$$

(11)

Remark that the gradient vectors of the connected particles have unit norm, which was therefore crossed out from the denominators of the projections (10) and (11). If $s_{_{ij}}\,=\,1$, then the projections are isometric and otherwise they are non-isometric. The deformation constraint (6) is then solved in one step when the pair of connected particles is projected through mappings (10) and (11) at the same time:

$$\begin{aligned} {\underline{\mathbf{x}}} \,=\, \mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}} \end{aligned}$$

(12)

where $\mathtt {T}_{\, \mathtt {D}_{\,ij}} = \mathtt {diag}(\,\mathtt {I}_{3}\,,\,\ldots \,,\mathtt {I}_{3}\,,\,\, ^{_{^{j}}}\mathtt {T}_{^{_{i}}}\,,\,\,\mathtt {I}_{3}\,,\,\ldots \,,\mathtt {I}_{3}, ^{_{^{i}}}\mathtt {T}_{^{_{j}}}\,,\,\,\mathtt {I}_{3}\,,\,\ldots \,,\mathtt {I}_{3}\,)\in \mathbb {R}^{3n\,\times \,3n}$ is an orthogonal projection mapping of only one pair in a shape ${\underline{\mathbf{x}}}$. The deformation constraint set $\mathcal {D}_{\,ij}$, which first appeared in Eq. (2), can then be defined explicitly, using $\mathtt {T}_{\, \mathtt {D}_{\,ij}}$ as:

$$\begin{aligned} \mathcal {D}_{\,ij} \,=\, \{\, {\underline{\mathbf{x}}} \,\,|\,\, {\underline{\mathbf{x}}} \,=\, \mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}\,,\,\, {\underline{\mathbf{x}}}\,\in \,\mathcal {M}\,\} \end{aligned}$$

(13)

We note that if $\mathbf {x}_{i} \,\ne \, \mathbf {x}_{j}$ then $^{_{^{j}}}\mathtt {T}_{^{_{i}}}\,\mathbf {x}_{i}$ and $^{_{^{i}}}\mathtt {T}_{^{_{j}}}\,\mathbf {x}_{j}$ exist and are unique points in $\mathbb {R}^{3}$. Otherwise if $\mathbf {x}_{i} \,=\, \mathbf {x}_{j}$, then $^{_{^{j}}}\mathtt {T}_{^{_{i}}}\,\mathbf {x}_{i}$ and $^{_{^{i}}}\mathtt {T}_{^{_{j}}}\,\mathbf {x}_{j}$ still exist but this time they are set valued mappings in $\mathbb {R}^{3}$. More explicitly they map to concentric sphere sets and the center is the singular configuration. Remark that Eq. (5) keeps a pair away from the singular configuration of the deformation constraint. Meshing We used Delaunay triangulation (Marton et al. 2009) to obtain the edges defining the A-constraints shown in black in Fig. 2, left. The A-constraints preserve the topology of the particles and control the in-plane shear deformation of the model. We then complete the mesh by adding edges across the triangles, to form the B-constraints shown in red in Fig. 2, left. This was inspired by a procedure used for the mass-spring model (Provot 1996). This procedure was using a rectangular regular grid which we extended here to handle a non-regular particle system. The B-constraints control both out-of-plane bending and in-plane shear deformation of the model. Intuitively, B-constraints capture effects such as curvature, as they connect particles to their second-order neighborhood. Without them the model would be prone to fold, especially at its corners. Another important advantage of the B-constraints is to make the particles less sensitive to depth ambiguities which might occur due to noise on the image points. This is because they have larger distance connections than A-constraints.

Parallelization The constraints can be separated into groups of parallelizable isolated constraints (i.e., constraints that do not have common particles). Figure 2, right illustrates parallelizable constraints. Each color, except black, represents a group of isolated constraints which can be solved in one step in parallel. Groups are solved sequentially. For the larger meshes one typically uses in practice, the constraints are parallelizable to a good extent.

4.3 Joint Reprojection and Deformation

Motivation The motivation behind using a joint constraint mapping is that the reprojection constraints are position-attractive whereas the deformation constraints are not. This is because deformation is a relative configuration among the particles, that may hold independently from the particles’ positions in space. Applying each type of constraint independently on the particles makes convergence analysis tremendously difficult, because of the non-attractive behavior of the deformation constraints. Therefore, we combine a deformation constraint for a pair of particles with the reprojection constraints of the same pair in order to obtain a new position-attractive constraint on the pair, including both reprojection and deformation constraints.

Mapping A joint constraint mapping $\mathtt {T}_{^{_{ij}}}\,:\, \mathcal {M}\, \,\rightarrow \, \mathcal {M}$ is made up of the successive projections of a deformation constraint and then the reprojection constraints of a pair of particles:

$$\begin{aligned} {\underline{\mathbf{x}}}_{\,k+1} \,=\, \mathtt {T}_{^{_{ij}}}\,\,\,{\underline{\mathbf{x}}}_{\,k} \end{aligned}$$

(14)

with $\mathtt {T}_{^{_{ij}}} \,=\, \mathtt {T}_{\, \mathtt {R}_{\,ij}} \, \mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\in \mathbb {R}^{3\,n\,\times \,3\,n}$. The joint constraint mapping $\mathtt {T}_{^{_{ij}}}$ does not fall into a singular configuration of the deformation constraints if the initial shape is not singular. Therefore it yields continuous, uniquely defined constraint mappings. Subsequently, from Brouwer’s fixed-point theorem (Brouwer 1910), this implies the existence of fixed points of the joint constraint mappings.

We now give Proposition 1 on a property of a joint constraint mapping which is one of the premises of Proposition 3, for the proof of convergence of Particle-SfT.

Proposition 1

A joint constraint mapping $\mathtt {T}_{^{_{ij}}}$ is asymptotically regular on $\mathcal {M}$ and convergent. It also minimizes its associated deformation constraint when applied successively on a shape.

In order to prove Proposition 1, we need Lemma 1.

Lemma 1

If $\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,\,\rightarrow \, 0\,$, then $\,\,d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\, {\underline{\mathbf{x}}}_{\,k}\,) \,\,\rightarrow \, 0$.

Proof

Here d is the metric (1), the sum of distances between the corresponding particles. We write the explicit expression of the metric for the deformation mapping using projections (10) and (11) as:

$$\begin{aligned}&d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\, {\underline{\mathbf{x}}}_{\,k}\,) \,=\, ||\,s_{_{ij}}\,\,\alpha _{i}\,\,\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,\,\, \,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,||\nonumber \\&\quad \qquad \qquad \qquad \qquad \qquad +\, ||\, s_{_{ij}}\,\,\alpha _{j}\,\,\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,\,\, \,\nabla _{j}\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,||\end{aligned}$$

(15)

where $s_{_{ij}},\,\alpha _{i},\,\alpha _{j}\,\in \,\mathbb {R}_{+}$. Remember that $\nabla _{j}g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,=\, -\,\nabla _{i}g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})$ and subsequently their absolute values are equal. We rewrite Eq. (15) by replacing $||\nabla _{j}g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})||$ with $||\nabla _{i}g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})||$ as:

$$\begin{aligned} d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\, {\underline{\mathbf{x}}}_{\,k}\,) \,=\, s_{_{ij}}\,\,|\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,|\,\,||\,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,||\,\,(\alpha _{i} \,+\, \alpha _{j}) \end{aligned}$$

(16)

where $\alpha _{i} \,+\, \alpha _{j}\,=\,1$ by definition and $||\,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,||\,=\,1$ by construction. We are then left with:

$$\begin{aligned} d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\, {\underline{\mathbf{x}}}_{\,k}\,) \,=\, s_{_{ij}}\,\,|\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,|\end{aligned}$$

(17)

We conclude from Eq. (17) that if $\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,\,\rightarrow \, 0\,$, then $\,\,d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\, {\underline{\mathbf{x}}}_{\,k}\,) \,\,\rightarrow \, 0$, and vice versa. $\square$

Proof of Proposition 1

An asymptotically regular mapping is convergent (Belluce and Kirk 1969). We prove the asymptotic regularity of the joint constraint mapping $\mathtt {T}_{^{_{ij}}}$ using Lyapunov’s direct method. Let $\mathtt {V}\,:\,\mathcal {M}\,\rightarrow \,\mathbb {R}$ be a Lyapunov candidate function defined over the deformation error as:

$$\begin{aligned} \mathtt {V}(\,{\underline{\mathbf{x}}}_{\,k}\,) \,=\, \frac{1}{2}\,\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{2} \end{aligned}$$

(18)

Here $\mathtt {V}$ is a positive semi-definite and radially unbounded function:

$$\begin{aligned} \mathtt {V} \,=\, 0\iff & {} g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,=\, 0 \end{aligned}$$

(19)

$$\begin{aligned} \mathtt {V} \,>\, 0\iff & {} g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,\ne \, 0 \end{aligned}$$

(20)

$$\begin{aligned} \mathtt {V} \,\rightarrow \, \infty\iff & {} |\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,|\,\,\rightarrow \, \infty \end{aligned}$$

(21)

Afterward if $\dot{\mathtt {V}}\,<\,0$ when $\mathtt {V}\,>\,0\,$, and if $\dot{\mathtt {V}}\,=\,0$ when $\mathtt {V} \,=\, 0\,$, then $\mathtt {V} \,\rightarrow \, 0\,$ (Lyapunov 1892). Subsequently this implies that $g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,\,\rightarrow \, 0$ and from Lemma 1 that $d(\,{\underline{\mathbf{x}}}_{\,k},\, \mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k}\,) \,\,\rightarrow \, 0$. Differentiating $\mathtt {V}$ with respect to time yields:

$$\begin{aligned} \dot{\mathtt {V}} \,=\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,\,\dot{g}_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \end{aligned}$$

(22)

where:

$$\begin{aligned} \dot{g}_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,=\, \,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{\top }\,\, \dot{\mathbf {x}}_{i} \,\,+\,\, \,\nabla _{j}\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{\top }\,\,\dot{\mathbf {x}}_{j} \end{aligned}$$

(23)

Considering that time takes unit discrete steps, we estimate $\dot{\mathbf {x}}_{i}$ and $\dot{\mathbf {x}}_{j}$ from the displacement $\,{\underline{\mathbf{x}}}_{\,k+1} \,-\, \,{\underline{\mathbf{x}}}_{\,k}\,$ where $\,{\underline{\mathbf{x}}}_{\,k+1}\,=\,\mathtt {T}_{^{_{ij}}}\,\,{\underline{\mathbf{x}}}_{\,k}$, as:

$$\begin{aligned} \dot{\mathbf {x}}_{i}= & {} \,\,-\,\, \alpha _{i}\,\,\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,\,\,\mathtt {T}_{\, \mathtt {r}_{i}}\,\, \,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \end{aligned}$$

(24)

$$\begin{aligned} \dot{\mathbf {x}}_{j}= & {} \,\,-\,\, \alpha _{j}\,\,\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,\,\,\mathtt {T}_{\, \mathtt {r}_{j}}\,\, \,\nabla _{j}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \end{aligned}$$

(25)

Substituting Eqs. (23), (24) and (25) into Eq. (22) yields:

$$\begin{aligned} \dot{\mathtt {V}} \,\,\,=\,\,\,-\,\, \lambda \,\,\,\, g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{2} \,\,\,\leqslant \,\,\,0 \end{aligned}$$

(26)

with $\,\lambda \,$ being:

$$\begin{aligned} \lambda= & {} s_{_{ij}}\left( \, \alpha _{i}\,\,\,\,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{\top }\,\,\, \mathtt {T}_{\, \mathtt {r}_{i}}\,\,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\right. \nonumber \\&\left. +\, \alpha _{j}\,\,\,\nabla _{j}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{\top }\,\,\, \mathtt {T}_{\, \mathtt {r}_{j}}\,\, \nabla _{j}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \right) \end{aligned}$$

(27)

We note that $\,\lambda \,$ is positive because $\,s_{_{ij}},\,\alpha _{i},\,\alpha _{j}\,\in \,(0,1]$ and $\,\,\mathtt {T}_{\, \mathtt {r}_{i}},\,\mathtt {T}_{\, \mathtt {r}_{j}}$ are orthogonal projections with two distinct eigenvalues $\{0,1\}$ which cancel only some coordinates of the gradient vectors $\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})$ and $\nabla _{j}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})$. We also know that $||\,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}})\,||\,=\,1$ and $||\,\nabla _{j}\,g_{_{ij}}({\underline{\mathbf{x}}})\,||\,=\,1$. Subsequently this yields the following inequalities $0\,<\,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{\top }\,\,\,\mathtt {T}_{\, \mathtt {r}_{i}}\,\,\nabla _{i}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,<\,1$ and $0\,<\,\nabla _{j}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})^{\top }\,\,\, \mathtt {T}_{\, \mathtt {r}_{j}}\,\, \nabla _{j}\,g_{_{ij}}({\underline{\mathbf{x}}}_{\,k})\,<\,1$. Consequently, we have $\,\dot{\mathtt {V}} \,\,\,\leqslant \,\,\,0\,$.

Here $\dot{\mathtt {V}}$ is uniformly continuous everywhere in $\mathcal {M}$ except at the optical center $\mathbf {O}$ of the camera. In Eq. (26), if $g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,\ne \, 0\,$, then $\dot{\mathtt {V}}\,\,<\,\,0$, and if $g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,=\, 0$, then $\dot{\mathtt {V}} \,\,=\,\,0\,$. It follows that both $\mathtt {V} \,\rightarrow \, 0\,$ and $\dot{\mathtt {V}} \,\rightarrow \, 0\,$, consequently $g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,\rightarrow \, 0\,$ and therefore $d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\,\mathtt {D}_{\,ij}}\,\,\, {\underline{\mathbf{x}}}_{\,k}\,) \,\,\rightarrow \, 0$. From this result, we make the following conclusion:

$$\begin{aligned} d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k}\,) \,\,>\,\, d(\,{\underline{\mathbf{x}}}_{\,k+1},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k+1}\,)\,,\quad \forall \, k\,\geqslant \,0 \end{aligned}$$

(28)

for ${\underline{\mathbf{x}}}_{\,k},\,{\underline{\mathbf{x}}}_{\,k+1}\,\in \,\mathcal {R}$ and ${\underline{\mathbf{x}}}_{\,k+1}\,=\,\mathtt {T}_{^{_{ij}}}\,\,{\underline{\mathbf{x}}}_{\,k}$. Then we note that:

$$\begin{aligned} d(\,\mathtt {T}_{\, \mathtt {R}_{\,ij}}\,\,{\underline{\mathbf{x}}},\,\mathtt {T}_{\, \mathtt {R}_{\,ij}}\,\,{\underline{\mathbf{y}}}\,) \,\,<\,\, d(\,{\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}}\,)\,, \forall \, {\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}}\,\in \,\mathcal {M} \end{aligned}$$

(29)

for ${\underline{\mathbf{x}}}\,\in \,\mathcal {R}$ and ${\underline{\mathbf{y}}}\,\notin \,\mathcal {R}$. Figure 3 illustrates this case on two particles. We use Eq. (29) to write the following relation:

Fig. 3

Projection of two particles at $\mathbf {x}\in \mathtt {r}$ and $\mathbf {y}\notin \mathtt {r}$ onto the sight-line $\mathtt {r}$ which passes through the optical center $\mathbf {O}$

Fig. 4

The particle-SfT algorithm

$$\begin{aligned} d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k}\,) \,\,>\,\, d(\,\mathtt {T}_{\, \mathtt {R}_{\,ij}}\,\,{\underline{\mathbf{x}}}_{\,k},\,\,\mathtt {T}_{\, \mathtt {R}_{\,ij}}\,\, \mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k}\,) \end{aligned}$$

(30)

which is true when ${\underline{\mathbf{x}}}_{\,k}\,\ne \,\mathtt {T}_{^{_{ij}}}\,\,{\underline{\mathbf{x}}}_{\,k}$ or $g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,\ne \, 0$. Remark that:

$$\begin{aligned} \mathtt {T}_{\, \mathtt {R}_{\,ij}}\,\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k} \,\,=\,\, \mathtt {T}_{^{_{ij}}}\,\,{\underline{\mathbf{x}}}_{\,k} \,\,=\,\,{\underline{\mathbf{x}}}_{\,k+1} \end{aligned}$$

(31)

and when $\,{\underline{\mathbf{x}}}_{\,k}\,\in \,\mathcal {R}$ that:

$$\begin{aligned} \mathtt {T}_{\, \mathtt {R}_{\,ij}}\,\,{\underline{\mathbf{x}}}_{\,k} \,\,=\,\,{\underline{\mathbf{x}}}_{\,k} \end{aligned}$$

(32)

Therefore Eq. (30) can be rewritten as:

$$\begin{aligned} d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k}\,) \,\,>\,\, d(\,{\underline{\mathbf{x}}}_{\,k},\,\,{\underline{\mathbf{x}}}_{\,k+1}\,) \end{aligned}$$

(33)

Since $d(\,{\underline{\mathbf{x}}}_{\,k},\,\mathtt {T}_{\, \mathtt {D}_{\,ij}}\,\,\,{\underline{\mathbf{x}}}_{\,k}\,)\,\,\rightarrow \, 0$ for all ${\underline{\mathbf{x}}}\,\in \,\mathcal {M}$, then $d(\,{\underline{\mathbf{x}}}_{\,k},\,\,{\underline{\mathbf{x}}}_{\,k+1}\,)\,\,\rightarrow \, 0$ which implies $d(\,\mathtt {T}_{^{_{ij}}}^{\,k}\,{\underline{\mathbf{x}}},\,\,\mathtt {T}_{^{_{ij}}}^{\,k+1}\,{\underline{\mathbf{x}}}\,)\,\,\rightarrow \, 0$. Furthermore, the fixed points of $\mathtt {T}_{^{_{ij}}}$ are globally attractive since $\mathtt {V}$ is radially unbounded, and globally stable equilibrium points of $\mathtt {V}$ since both $\mathtt {V} \,\,=\,\,0$ and $\dot{\mathtt {V}} \,\,=\,\,0$ whenever $g_{_{ij}}({\underline{\mathbf{x}}}_{\,k}) \,=\, 0$. $\square$

5 Algorithm

The algorithm in Fig. 4 finds a stable equilibrium shape for problem (2). Line 01 initializes the shape, velocity, external forces and the masses of the particles as well as the iteration counter of the main loop. The initial shape must be a valid shape (non-singular). In practice, any initial shape in front of or behind the camera is a good starting point. Line 02 starts the main loop. Line 03 exerts the external forces, if known, on the shape with weight $\beta \,\in \,[0,1]$. In line 03, if the masses of particles are approximated, then $\beta$ also helps smoothing out these effects. Line 04 predicts the future pose using the damped velocities of the particles with the weight vector $\varvec{\underline{\kappa }}\,\in \,(\mathbf {0},\,\mathbf {1})$. Parameter $\varvec{\underline{\kappa }}\,=\,\mathbf {1}\,-\,\varvec{\underline{\mu }}$ weights the prediction using $\varvec{\underline{\mu }}\in \mathbb {R}^{n}$ the damping coefficient vector. $\varvec{\underline{\mu }}$ is made of $\mu _{i}\,\approx \,2\,\sqrt{s_{min}\,\,\min \,(m_{i},\,0.25-\epsilon )}\,$ coefficients where each critically damps a particle’s motion (Goldstein 1980). $s_{min}\,=\,\min \,\{\,s_{_{ij}} \,\,|\,\,ij\,\in \,\mathcal {E}\,\}$ is the minimum of all the elasticity parameters. If $\,0\,<\,s_{_{ij}}\,<\,1\,$ then the connected pair behaves elastically, and if $s_{_{ij}}\,\rightarrow \,1$ then the connected pair behaves isometrically. Line 05 applies successively the joint constraint mappings. Line 06 computes the new velocity. Line 07 updates the shape. Line 08 ends the algorithm either when the root-mean-squared (RMS) value of the shape velocity is lower than a very small positive threshold value $\epsilon$ or when the maximum number of loop iteration maxiter is reached. Finally, the shape might escape from one side to the other due to the prediction step in line 04. Line 09 brings the shape in front of the camera if required: if it is behind, then it is reflected about the optical center to its correct symmetrical pose. In all our experiments, we set $\epsilon =10^{-6}$ and $maxiter=10^{4}$.

6 Convergence Analysis

Proposition 1 showed that a joint constraint mapping is asymptotically regular and therefore convergent, and has globally attractive fixed-points. Furthermore, the fixed-points are globally stable equilibrium points of the associated deformation constraint of a joint constraint mapping. Problem (2) is the sum of the deformation constraints associated to these joint constraint mappings. We now propose a new fixed-point theorem and then two more propositions to develop the convergence proof of Particle-SfT. The new fixed-point theorem, Theorem 1, shows that a family of asymptotically regular mappings satisfying the same generalized contractiveness condition is convergent and has fixed-points. Theorem 1 also gives the uniqueness condition for the fixed-point solution. The solution may not always be unique. Afterward, Proposition 2 is given. It states that a joint constraint mapping satisfies the generalized contractiveness condition proposed in Theorem 1. Finally, Proposition 3 is given. It combines Propositions 1 and 2, and Theorem 1, and proves the convergence of Particle-SfT as given in Fig. 4.

Fig. 5

A configuration of pairs in the worst case. Grey pairs show the initial configuration on the sight-lines. Red pairs show the configuration after the joint constraint mappings (Color figure online)

Theorem 1

Let $(\mathcal {M},\,d)$ be a compact metric space and $\{\,\mathtt {Z}_{h}\,\}_{h=1}^{\infty }$ be a sequence of self-mappings of $\,\mathcal {M}$. Let each mapping $\mathtt {Z}_{h}\,:\, \mathcal {M}\, \,\rightarrow \, \mathcal {M}$ be asymptotically regular with a fixed point $\mathbf {x}_{h}\,$ and satisfy the following generalized contractiveness condition for all $\mathbf {x},\,\mathbf {y}\,\in \,\mathcal {M}$ and $h\,\geqslant \,1$:

$$\begin{aligned}&\gamma \,\left( \, d(\mathbf {x},\,\mathbf {y}) \,+\, \,d(\mathbf {x},\,\mathtt {Z}_{h}\,\mathbf {x}) \,+\,d(\mathbf {y},\,\mathtt {Z}_{h}\,\mathbf {y})\right. \nonumber \\&\left. \quad +\, d(\mathbf {x},\,\mathtt {Z}_{h}\,\mathbf {y}) \,+\, d(\mathbf {y},\,\mathtt {Z}_{h}\,\mathbf {x})\, \right) \,\,\geqslant \,\, d(\mathtt {Z}_{h}\,\mathbf {x},\,\mathtt {Z}_{h}\,\mathbf {y}) \end{aligned}$$

(34)

where $\,\,0\,\leqslant \,\gamma \,<\,\frac{1}{2}\,\,\,$. Suppose that the sequence $\{\,\mathtt {Z}_{h}\,\}$ converges pointwise to a mapping $\mathtt {Q}\,:\, \mathcal {M}\, \,\rightarrow \, \mathcal {M}\,$ and that $\mathbf {x}^{*}$ is any cluster point of the sequence $\{\,\mathbf {x}_{h}\,\}$ of fixed points of $\{\,\mathtt {Z}_{h}\,\}$. Then $\mathbf {x}^{*}$ is a fixed point of mapping $\mathtt {Q}\,$. Furthermore, if $0\,\leqslant \,\gamma \,<\,\frac{1}{3}\,\,\,$, then $\mathbf {x}^{*}$ is the unique fixed point of mapping $\,\mathtt {Q}\,$.

Proof

Since $\mathbf {x}^{*}$ is a cluster point of the sequence $\{\,\mathbf {x}_{h}\,\}$, there is a subsequence $\{\,\mathbf {x}_{h_{i}}\,\}$ of $\{\,\mathbf {x}_{h}\,\}$ which converges to $\mathbf {x}^{*}$ as $h_{i}\,\rightarrow \,\infty$. By contradiction, assume that $\mathtt {Q}\,\,\mathbf {x}^{*}\,\ne \,\mathbf {x}^{*}$. This subsequently implies $d(\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}\,)\,\,>\,\, 0$. We then write the following relation using the triangular inequality twice:

$$\begin{aligned}&d(\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}\,) \,\,\leqslant \,\, d(\,\mathbf {x}^{*},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}}\,)\nonumber \\&\quad +\, d(\,\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}},\,\mathtt {Z}_{h_{i}}\,\,\mathbf {x}^{*}\,) \,+\, d(\,\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}\,) \end{aligned}$$

(35)

and using Eq. (34) this leads to:

$$\begin{aligned}&d(\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}) \,\,\leqslant \,\, d(\mathbf {x}^{*},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}}) \nonumber \\&\quad +\,\gamma \,\,\left( d(\mathbf {x}_{h_{i}},\mathbf {x}^{*}) \,+\, d(\mathbf {x}_{h_{i}},\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}}) \,+\, d(\mathbf {x}^{*},\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*})\right. \nonumber \\&\quad \left. +\, d(\mathbf {x}_{h_{i}},\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*}) \,+\, d(\mathbf {x}^{*},\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}})\right) \nonumber \\&\quad +\, d(\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}) \end{aligned}$$

(36)

Since $\mathbf {x}_{h_{i}}$ is a fixed-point of $\mathtt {Z}_{h_{i}}$ then $\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}}=\mathbf {x}_{h_{i}}$. Therefore this implies $d(\mathbf {x}^{*},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}}) = d(\mathbf {x}^{*},\,\mathbf {x}_{h_{i}})$ and $d(\mathbf {x}_{h_{i}},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}_{h_{i}})=0$. Hence Eq. (36) becomes:

$$\begin{aligned}&d(\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}\,) \,\,\leqslant \,\, d(\,\mathbf {x}^{*},\,\mathbf {x}_{h_{i}}\,) \nonumber \\&+\,\, \gamma \,\,\,\left( d(\mathbf {x}_{h_{i}},\,\mathbf {x}^{*}) \,+\, 0 \,+\, \,d(\mathbf {x}^{*},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*}) \right. \nonumber \\&\left. +\,\, d(\mathbf {x}_{h_{i}},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*})+ d(\mathbf {x}^{*},\,\mathbf {x}_{h_{i}}) \right) \,\,\, \nonumber \\&+\, \, d(\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}) \end{aligned}$$

(37)

Since $\mathbf {x}_{h_{i}}\,\rightarrow \,\mathbf {x}^{*}$ and $\,\,\mathtt {Z}_{h_{i}}\,\rightarrow \,\mathtt {Q}\,$ as $h_{i}\,\rightarrow \,\infty$, then $\,d(\mathbf {x}^{*},\,\mathbf {x}_{h_{i}})\,\rightarrow \,0\,$ and $\,\,d(\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*})\,\rightarrow \,0\,$ and $\,d(\mathbf {x}^{*},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*})\,\rightarrow \,d(\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*})$ and $\,d(\mathbf {x}_{h_{i}},\,\mathtt {Z}_{h_{i}}\,\mathbf {x}^{*})\,\rightarrow \,d(\,\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}\,)$. Hence Eq. (37) yields:

$$\begin{aligned} d(\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}) \,\,\leqslant \,\, 2\,\gamma \,\,\,\,d(\mathbf {x}^{*},\,\mathtt {Q}\,\,\mathbf {x}^{*}) \end{aligned}$$

(38)

This is a contradiction since $\,\,0\,\leqslant \,\gamma \,<\,\frac{1}{2}\,\,$. It follows that $\mathbf {x}^{*}\,=\,\mathtt {Q}\,\mathbf {x}^{*}$. To see that $\mathbf {x}^{*}$ is unique, let there be another fixed point, say $\mathbf {y}^{*}$, with $\mathtt {Q}\,\mathbf {y}^{*}\,=\,\mathbf {y}^{*}$. By contradiction, assume that $\mathbf {y}^{*}\,\ne \,\mathbf {x}^{*}$ which implies $d(\,\mathbf {x}^{*},\,\mathbf {y}^{*}\,)\,>\,0$. We then write the following relation using the given generalized contractiveness condition:

$$\begin{aligned} d(\,\mathbf {x}^{*},\,\mathbf {y}^{*}\,)= & {} d(\,\mathtt {Q}\,\mathbf {x}^{*},\,\mathtt {Q}\,\mathbf {y}^{*}\,) \ \,\leqslant \, \gamma \,\left( \, d(\mathbf {x}^{*},\,\mathbf {y}^{*})\right. \nonumber \\&+ \, d(\mathbf {x}^{*},\,\mathtt {Q}\,\mathbf {x}^{*}) \,+\, d(\mathbf {y}^{*},\,\mathtt {Q}\,\mathbf {y}^{*})\nonumber \\&\left. + \, d(\mathbf {x}^{*},\,\mathtt {Q}\,\mathbf {y}^{*}) \,+\, d(\mathbf {y}^{*},\,\mathtt {Q}\,\mathbf {x}^{*})\, \right) \end{aligned}$$

(39)

and this yields:

$$\begin{aligned} d(\,\mathbf {x}^{*},\,\mathbf {y}^{*}\,) \,\,\leqslant \,\, 3\,\gamma \,\,\,\,d(\,\mathbf {x}^{*},\,\mathbf {y}^{*}\,) \end{aligned}$$

(40)

which is a contradiction for $\,\,0\,\leqslant \,\gamma \,<\,\frac{1}{3}\,$. It then follows that $\mathbf {y}^{*}\,=\,\mathbf {x}^{*}$ for $\,\,0\,\leqslant \,\gamma \,<\,\frac{1}{3}\,$. $\square$

We now give Proposition 2 on contractiveness of a joint constraint mapping.

Proposition 2

A joint constraint mapping $\mathtt {T}_{^{_{ij}}}$ conforms to the generalized contractiveness condition (34) proposed in Theorem 1 with $\,\,0\,\leqslant \,\gamma \,<\,\frac{1}{2}\,$.

Proof

We can write the following relations using the triangular inequality:

$$\begin{aligned} d(\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}})&\,\,\leqslant \,\, d(\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}}) \,+\, d({\underline{\mathbf{y}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}}) \,+\, d({\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}}) \end{aligned}$$

(41a)

$$\begin{aligned} d(\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}})&\,\,\leqslant \,\, d(\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}},\,{\underline{\mathbf{x}}}) \,+\, d({\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}}) \end{aligned}$$

(41b)

Summing Eqs. (41a) and (41b), we obtain:

$$\begin{aligned}&d(\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}}) \,\,\leqslant \,\, \frac{1}{2}\,\,\left( \, d({\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}}) \,+\, \,d({\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}}) \right. \nonumber \\&\left. \quad +\,\, d({\underline{\mathbf{y}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}})+ d({\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}}) \,+\, \,d({\underline{\mathbf{y}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}})\, \right) \end{aligned}$$

(42)

If ${\underline{\mathbf{x}}}\,\ne \,{\underline{\mathbf{y}}}$, then this becomes exactly the generalized contractiveness condition (34) with $\gamma \,\in \,[0,\,\frac{1}{2})$:

$$\begin{aligned}&d(\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}}) \,\,\leqslant \,\, \gamma \,\left( \, d({\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}}) \,+\, \,d({\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}})\right. \nonumber \\&\left. +\,\, d({\underline{\mathbf{y}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}}) \,+\, d({\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}}) \,+\, d({\underline{\mathbf{y}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}})\, \right) \end{aligned}$$

(43)

If ${\underline{\mathbf{x}}}\,=\,{\underline{\mathbf{y}}}$, then Eq. (43) turns to be:

$$\begin{aligned} 0 \,\,\leqslant \,\, 4\,\gamma \,\, d({\underline{\mathbf{x}}},\,\mathtt {T}_{ij}\,{\underline{\mathbf{x}}}) \end{aligned}$$

(44)

which is still valid with $\gamma \,\in \,[0,\,\frac{1}{2})$. We give an example which illustrates the worst case scenario. The worst case, $\gamma \,\rightarrow \,\frac{1}{2}$, is observed when ${\underline{\mathbf{x}}}\,\ne \,{\underline{\mathbf{y}}}$, the line segments $\mathbf {x}_{i}-\mathbf {x}_{j}$ and $\mathbf {y}_{i}-\mathbf {y}_{j}$ intersect, both $g_{_{ij}}({\underline{\mathbf{x}}}) \,<\, 0$ and $g_{_{ij}}({\underline{\mathbf{y}}}) \,<\, 0$ and the intersection angle $\varphi \,\leqslant \,\pi -\theta$, where $\theta$ is the angle between the sight-lines of a pair. Figure 5 illustrates a configuration of pairs in the worst case. In Fig. 5, $\,d(\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}})~=~a+b+c+d+e+f$, $\,d({\underline{\mathbf{x}}},\,{\underline{\mathbf{y}}})\,=\,b+e$, $\,d({\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}})\,=\,c+d, \,d({\underline{\mathbf{y}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}})\,=\,a+f$, $\,d({\underline{\mathbf{x}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{y}}})\,=\,a+b+e+f, \,d({\underline{\mathbf{y}}},\,\mathtt {T}_{^{_{ij}}}\,{\underline{\mathbf{x}}})~=~b+c+d+e$. Hence the worst case conforms to the generalized contractiveness condition for all ${\underline{\mathbf{x}}},{\underline{\mathbf{y}}}\,\in \,\mathcal {M}$ with $\gamma \,\in \,[0,\frac{1}{2})\,$:

$$\begin{aligned}&a \,+\, b \,+\, c \,+\, d \,+\, e \,+\, f \,\,\leqslant \,\, \gamma \nonumber \\&\quad \left( \, 2\,a \,+\, 3\,b \,+\, 2\,c \,+\, 2\,d \,+\, 3\,e \,+\, 2\,f \right) \end{aligned}$$

(45)

This concludes the proof. $\square$

We finally give Proposition 3, built upon Propositions 1 and 2 and Theorem 1.

Proposition 3

Particle-SfT is convergent.

Proof

Let one cycle of joint constraint mappings in line 05 form a mapping $\,\mathtt {C}\,\triangleq \,\prod _{ij\in \mathcal {E}}\,\mathtt {T}_{^{_{ij}}}$. Then $\{\,\mathtt {C}_{k}\,\}_{k=1}^{\infty }$ can be considered as a sequence composed of sufficiently many mappings which are obtained by cycling the sequence of joint constraint mappings $\{\,\mathtt {T}_{^{_{ij}}}\}_{ij\in \mathcal {E}}$. Thanks to Propositions 1 and 2, the sequence $\{\,\mathtt {C}_{k}\,\}_{k=1}^{\infty }$ conforms to Theorem 1, therefore it is convergent. We next write one main loop iteration in the algorithm from lines 03 to 07 as a two-step update method:

$$\begin{aligned} {\underline{\mathbf{y}}}_{\,k}&\,=\, {\underline{\mathbf{x}}}_{\,k} \,+\, \mathtt {diag}(\,\varvec{\underline{\kappa }}\,)\,\left( \,{\underline{\mathbf{x}}}_{\,k} \,-\, {\underline{\mathbf{x}}}_{\,k-1} \,\right) \,+\, \mathtt {diag}(\,\varvec{\underline{\kappa }}\,)\,\beta \,\,{\underline{\mathbf{a}}} \end{aligned}$$

(46a)

$$\begin{aligned} {\underline{\mathbf{x}}}_{\,k+1}&\,=\, \mathtt {C}_{k}\,\,{\underline{\mathbf{y}}}_{\,k} \end{aligned}$$

(46b)

with the shape prediction matrix $\mathtt {diag}(\,\varvec{\underline{\kappa }}\,)\,=\, \mathtt {diag}(\,\kappa _{1}\,\mathtt {I}_{3},\,\ldots ,\,\kappa _{n}\, \mathtt {I}_{3}\,)\,\in \,\mathbb {R}^{3n\times 3n}$ and shape acceleration vector ${\underline{\mathbf{a}}}~=~{\underline{\mathbf{f}}}\,/\,{\underline{\mathbf{m}}}\,\in \,\mathbb {R}^{3n}$. We rewrite Eqs. (46a) and (46b) as the equivalent two-step update:

$$\begin{aligned} {\underline{\mathbf{x}}}_{\,k+1}&\,=\, \mathtt {C}_{k}\,\,{\underline{\mathbf{y}}}_{\,k} \end{aligned}$$

(47a)

$$\begin{aligned} {\underline{\mathbf{y}}}_{\,k+1}&\,=\, {\underline{\mathbf{x}}}_{\,k+1} \,+\, \mathtt {diag}(\varvec{\underline{\kappa }})\,\left( \,{\underline{\mathbf{x}}}_{\,k+1} \,-\, {\underline{\mathbf{x}}}_{\,k} \,\right) \,+\, \mathtt {diag}(\varvec{\underline{\kappa }})\,\beta \,\,{\underline{\mathbf{a}}} \end{aligned}$$

(47b)

By substituting Eq. (47a) into Eq. (47b), we obtain:

$$\begin{aligned} {\underline{\mathbf{x}}}_{\,k+1}&\,=\, \mathtt {C}_{k}\,\,{\underline{\mathbf{y}}}_{\,k} \end{aligned}$$

(48a)

$$\begin{aligned} {\underline{\mathbf{y}}}_{\,k+1}&\,=\, \mathtt {diag}(\mathbf {1}\,+\,\varvec{\underline{\kappa }})\,\, \mathtt {C}_{k}\,\,{\underline{\mathbf{y}}}_{\,k} \,-\,\, \mathtt {diag}(\varvec{\underline{\kappa }})\,\, {\underline{\mathbf{x}}}_{\,k}\nonumber \\&\quad +\, \mathtt {diag}(\,\varvec{\underline{\kappa }}\,)\,\beta \,\,{\underline{\mathbf{a}}} \end{aligned}$$

(48b)

with $\mathtt {diag}(\,\mathbf {1}\,+\,\varvec{\underline{\kappa }}\,)\,=\, \mathtt {diag}(\,(1+\kappa _{1})\,\mathtt {I}_{3},\,\ldots ,\,(1+\kappa _{n})\,\mathtt {I}_{3}\,)\,\in \,\mathbb {R}^{3n\times 3n}$. We rewrite Eqs. (48a) and (48b) in matrix form as:

$$\begin{aligned}&\underbrace{ \left[ \begin{array}{c} {\underline{\mathbf{y}}}_{\,k+1} \\ {\underline{\mathbf{x}}}_{\,k+1} \\ \beta \,\,{\underline{\mathbf{a}}} \end{array}\right] }_{{\underline{\mathbf{z}}}_{\,k+1}} \,=\, \left[ \begin{array}{ccc} \mathtt {diag}(\,\mathbf {1}\,+\,\varvec{\underline{\kappa }}\,)\,\, \mathtt {C}_{k} &{} \,-\,\mathtt {diag}(\,\varvec{\underline{\kappa }}\,) &{} \mathtt {diag}(\,\varvec{\underline{\kappa }}\,) \\ \mathtt {C}_{k} &{} \mathtt {0} &{} \mathtt {0} \\ \mathtt {0} &{} \mathtt {0} &{} \mathtt {I} \end{array} \right] \nonumber \\&\quad \qquad \qquad \qquad \qquad \underbrace{\left[ \begin{array}{c} {\underline{\mathbf{y}}}_{\,k} \\ {\underline{\mathbf{x}}}_{\,k} \\ \beta \,\,{\underline{\mathbf{a}}} \end{array}\right] }_{{\underline{\mathbf{z}}}_{\,k}} \end{aligned}$$

(49)

where ${\underline{\mathbf{z}}}\,\in \,\mathcal {M}\,\times \,\mathcal {M}\,\times \,\mathbb {R}^{3n}$ is an augmented state vector. Equation (49) can be rewritten as:

$$\begin{aligned}&\underbrace{ \left[ \begin{array}{c} {\underline{\mathbf{y}}}_{\,k+1} \\ {\underline{\mathbf{x}}}_{\,k+1} \\ \beta \,\,{\underline{\mathbf{a}}} \end{array}\right] }_{{\underline{\mathbf{z}}}_{\,k+1}} \,=\, \underbrace{\, \left[ \begin{array}{ccc} \mathtt {diag}(\,\mathbf {1}\,+\,\varvec{\underline{\kappa }}\,) &{} \,-\,\mathtt {diag}(\,\varvec{\underline{\kappa }}\,) &{} \mathtt {diag}(\,\varvec{\underline{\kappa }}\,) \\ \mathtt {I} &{} \mathtt {0} &{} \mathtt {0} \\ \mathtt {0} &{} \mathtt {0} &{} \mathtt {I} \end{array} \right] \,}_{\mathtt {A}}\nonumber \\&\qquad \qquad \qquad \quad \underbrace{\, \left[ \begin{array}{ccc} \mathtt {C}_{k} &{} \mathtt {0} &{} \mathtt {0} \\ \mathtt {0} &{} \mathtt {I} &{} \mathtt {0} \\ \mathtt {0} &{} \mathtt {0} &{} \mathtt {I} \end{array} \right] \,}_{\mathtt {B}}\, \underbrace{\left[ \begin{array}{c} {\underline{\mathbf{y}}}_{\,k} \\ {\underline{\mathbf{x}}}_{\,k} \\ \beta \,\,{\underline{\mathbf{a}}} \end{array}\right] }_{{\underline{\mathbf{z}}}_{\,k}} \end{aligned}$$

(50)

The last expression can be rewritten by expanding the mapping $\mathtt {B}$ as:

$$\begin{aligned} {\underline{\mathbf{z}}}_{\,k+1} \,=\, \mathtt {A}\,\,\left( \,\prod _{ij\in \mathcal {E}}\, \mathtt {diag}(\,\mathtt {T}_{^{_{ij}}},\,\mathtt {I},\,\mathtt {I}\,)\,\right) \,\,{\underline{\mathbf{z}}}_{\,k} \end{aligned}$$

(51)

where the identity matrix $\mathtt {I}\,\in \,\mathbb {R}^{3n\times 3n}$ is by definition asymptotically regular and satisfies the generalized contractiveness condition (34) with $\,\gamma \,\in \,[0,\frac{1}{3})$. The linear mapping $\mathtt {A}$ has eigenvalues $\,\varvec{\underline{\kappa }}\,$, repeated 3 times, and 1, repeated 6n times. If $\,\varvec{\underline{\kappa }}\,\in \,(\mathbf {0},\,\mathbf {1})$, then $\mathtt {A}$ is also asymptotically regular, satisfies the generalized contractiveness condition (34) with $\,\gamma \,\in \,[0,\frac{1}{3})$, and makes the algorithm take larger steps by extrapolation. Consequently, the augmented state sequence $\{\,{\underline{\mathbf{z}}}_{\,k}\,\}_{k=1}^{\infty }$ conforms to Theorem 1, and is therefore convergent. Since each ${\underline{\mathbf{x}}}$ in ${\underline{\mathbf{z}}}$ is obtained from a $\mathtt {C}$ mapping, then ${\underline{\mathbf{x}}}$ is a cluster fixed-point of the $\{\,\mathtt {T}_{^{_{ij}}}\}_{ij\in \mathcal {E}}$ mappings. $\square$

7 Experimental Results

We conduct three different types of experiments with Particle-SfT. First, we reconstruct isometric surfaces and compare the results with state-of-the-art methods. Second, we reconstruct elastic surfaces and again compare the results with state-of-the-art methods. Finally, we exploit the known gravity vector to reconstruct the shape of an object which is deformed by gravitational forces. In all experiments, we compute the 3D error in terms of RMS between the reconstructed shape ${\underline{\mathbf{x}}}$ and the ground truth shape ${\underline{\mathbf{x}}}^{*}$:

$$\begin{aligned} RMS(\,\,{\underline{\mathbf{x}}},\,\,{\underline{\mathbf{x}}}^{*}\,) \,=\, \sqrt{ \frac{1}{n}\,\sum _{i=1}^{n}\, ||\, \mathbf {x}_{i} \,-\, \mathbf {x}_{i}^{*} \,||^{2} } \ \ \end{aligned}$$

(52)

Synthetic data experiments are repeated four times and their 3D errors are averaged.

7.1 Isometric Surfaces

General points In order to reconstruct isometric shapes with Particle-SfT, we have two sets of parameters to choose, the A-constraint and B-constraint strengths. Since there should be no stretching in the isometric case, we set all the A-constraint strengths as $s_{A}=1$, and all the B-constraint strengths used for bending as $s_{B}=0.99$. We compare the results of Particle-SfT with (Brunet et al. 2014; Chhatkuli et al. 2014; Bartoli et al. 2015; Östlund et al. 2012; Salzmann and Fua 2011). The compared SfT methods can be grouped in two categories: four initializing methods Chhatkuli14 (Chhatkuli et al. 2014), Bartoli12i (Bartoli et al. 2015), Ostlund12 (Östlund et al. 2012), Salzmann11 (Salzmann and Fua 2011) and one refining method Brunet10 (Brunet et al. 2014). We recall that Particle-SfT is a refining method, but we will see that in practice it does not need an initial guess to estimate the shape, as opposed to Brunet10 which requires an initial guess close to the optimal shape. We start Particle-SfT from the known template shape in all experiments. We also remark that all the state-of-the-art isometric SfT methods, except Salzmann11, have at least two parameters to be tuned (e.g., the smoothness weight).

Synthetic Data [developable surface] We simulate 8 different isometric deformations of a flat template. We then generate synthetic images of size $640\times 480$ pixels (see Fig. 6) of these deformations using a pinhole camera model with focal length 500 pixels and principal point at (320, 240).

Fig. 6

Synthetic images of 8 isometric deformations and the 3D reconstructions seen from a different viewpoint. In this figure the reconstructions are performed with 300 random point correspondences under a 1 pixel Gaussian noise. The colder a point’s color, the smaller its reconstruction error

Noise and number of correspondences In order to test the robustness to noise of the SfT methods, we first randomly generate 100 point correspondences between the template and the image, and inject different levels of Gaussian noise to the positions of the image points with standard deviation $\sigma$ varying from 0 to 2.4 pixels with a step of 0.2 pixels. We then run the SfT methods on these noisy data. The left-most graph in Fig. 7 shows the 3D errors of the SfT methods versus noise level. We see that Particle-SfT yields the most accurate results with Brunet10 under different noise levels, and outperforms the other methods.

Second, we randomly generate N point correspondences varying from 50 to 300 points with a step of 50 points between the template and the image. We also inject Gaussian noise to the positions of these image points with standard deviation $\sigma \,=\,1$ pixel. We then run the SfT methods on these data. The right-most graph in Fig. 7 shows the 3D errors of the SfT methods versus the number of point correspondences. We see that Particle-SfT yields the most accurate results again with Brunet10 under different numbers of correspondences, and outperforms the other methods.

Fig. 7

3D errors of isometric SfT methods on synthetic data versus Gaussian noise levels (left) and number of correspondences (right)

Real Data [paper sheet] We use the CVLab’s paper dataset (Varol et al. 2012). This dataset consists of 191 images of a paper sheet being deformed. The images are taken with a fixed Kinect while the paper sheet is being moved and deformed. Some $1,300$ point features are detected per image. The left-most graph in Fig. 8 compares the SfT methods in terms of 3D error versus image number. Table 1 gives the mean 3D error values and run times of the compared methods. We observe from Fig. 8 and Table 1 that Particle-SfT outperforms the other methods in most of the frames, and yields the lowest mean 3D error over the whole CVLab’s paper dataset. Particle-SfT reconstructs shapes about 15 times faster than the refining method Brunet10.

Fig. 8

3D errors of isometric SfT methods on the CVLab’s paper dataset (left), mean 3D errors of isometric refining SfT methods versus perturbation level on the ground-truth shapes of CVLab’s paper dataset used as initial guesses (right)

Table 1 Mean errors and run times for CVLab’s paper dataset

Convergence basin We compare Brunet10 with Particle-SfT in terms of convergence basin using the CVLab’s paper dataset. To do so, we generate initial guesses by perturbing the known ground-truth shapes. Afterwards we let Brunet10 and Particle-SfT start from these guesses. A $1\%$ perturbation level corresponds to $1^{\circ }$ degree of rotation about a random axis, to a displacement along the same random axis with length $1\%$ of the distance from the center of gravity of the ground-truth shape to the camera and to a Gaussian noise with standard deviation 1 mm on the position coordinates. We increase the perturbation level from $0\%$ to $100\%$ with a step of 5 percentage points per shape. We repeat this experiment three times over the whole CVLab’s paper dataset. The right-most graph in Fig. 8 shows the mean 3D errors versus perturbation level. We observe that Brunet10 misses the solutions after $25\%$ perturbation on the ground-truth shapes whereas Particle-SfT still finds the expected solutions. The mean standard deviation of the errors at convergence is computed for Brunet10 as 215.44 mm and for Particle-SfT as 0.95 mm.

Fig. 9

Cushion dataset with non-planar template. The 3D reconstructions (black circles) of Particle-SfT are shown with the ground-truth shapes (green dots). The 3D errors are also given below the reconstructions (Color figure online)

Table 2 3D errors in millimeters for the cushion dataset

Real Data [cushion with non-planar template] Particle-SfT also works with non-planar templates. We apply Particle-SfT to a cushion dataset whose template is non-planar. This dataset contains images of 4 different deformations of a cushion, the cushion’s non-planar 3D template and the template image. The deformations are quasi-isometric on the surface of the cushion. The images are $3,456\,\times \,2,304$ pixels. The focal length of the camera is about $2,700$ pixels. Some $1,000$ feature correspondences are detected between the template image and an image of a deformation by combining SIFT (Lowe 1999) and KAZE (Alcantarilla et al. 2012). In Fig. 9, the first column shows the template image and its non-planar 3D template, and the rest of the columns show the input images, the 3D reconstructions (black circles) over the ground-truth shapes (green dots) and the 3D errors obtained by applying Particle-SfT directly with the non-planar 3D template. The results for the compared SfT methods can be found in Table 2. We observe in Table 2 that for the mean 3D errors over the whole cushion dataset Particle-SfT yields the second best result, after Chhatkuli14. Particle-SfT’s result is very close to Chhatkuli14, less than half a millimeter. Both Chhatkuli14 and Bartoli12i need flattening of the non-planar 3D template. Chhatkuli14 uses point correspondences and requires the first-order differential structure around these points.

Remark Brunet10 is initialized with Bartoli12i in all our experiments. The results are similar in accuracy and speed of convergence when Brunet10 is initialized with Chhatkuli14. This was shown in the results of (Chhatkuli et al. 2014). The Bartoli12i+Brunet10 method corresponds to the ReD method and the Chhatkuli14+Brunet10 method corresponds to the ReJ method in (Chhatkuli et al. 2014).

Fig. 10

Partially stretched elastic material. Three frames ($\#1,\#25,\#50$) from a continuous deformation sequence. From left to right the extensibility ratios are 0, 33, $66\%$. This data can be downloaded from http://isit.u-clermont1.fr/~ab/Research

Fig. 11

Reconstructed shapes (black circles) using 20 boundary points (red dots) for the ground-truth shape (green dots) with extensibility ratio 66%. Each column shows the same reconstructed shape from two different viewpoints, and gives the 3D errors in millimeters (mm) (Color figure online)

7.2 Elastic Surfaces

General points

In order to reconstruct elastic shapes with Particle-SfT, we set the distance correction strengths as $0<s_{A}<1$ and $0<s_{B}<1$. All the A-constraint strengths $s_{A}$ use the same value for a given material. Similarly all the B-constraint strengths $s_{B}$ use the same value for a given material but might be different to what A-constraints use. In practice, the values of $s_{A}$ and $s_{B}$ were found on test data and included as known parameters in the template. We need to add boundary conditions into the deformation constraints to resolve the unknown shape. In our case, these boundary conditions are known points $\mathbf {x}^{*}_{i}$ of the ground-truth shape as for the other elastic SfT methods (Haouchine et al. 2014; Malti et al. 2013, 2015). Those known points are integrated as deformation constraints by setting the position of the corresponding particles simply as $\mathbf {x}_{i}=\mathbf {x}^{*}_{i}$ in each iteration. We compare the results of Particle-SfT with (Haouchine et al. 2014; Malti et al. 2013, 2015; Bartoli et al. 2015). The first elastic SfT method, Haouchine14 (Haouchine et al. 2014), is based on non-linear elasticity and the second elastic SfT method, Malti13 (Malti et al. 2013), on linear elasticity. They both minimize a non-convex energy function. Haouchine14 and Malti13 are refining elastic SfT methods. The third elastic SfT method, Malti15 (Malti et al. 2015), is based on linear elasticity and minimizes a convex energy function. Malti15 is an initializing elastic SfT method. Malti15 uses reprojection boundary constraints and is designed to work with a rigid frame (undeformed border points) around the shape. We adapt Malti15 to work with the known 3D boundary points of the ground-truth shape and with a non-rigid frame around the shape. The fourth SfT method, Bartoli12c (Bartoli et al. 2015), is for conformal deformations and yields a set of analytic solutions up to scale which are later refined through non-linear optimization. Bartoli12c does not need boundary constraints, however its solutions need to be correctly scaled with respect to the ground-truth shape for comparison purposes. We choose the best solution from the solution set of Bartoli12c.

All the state-of-the-art elastic SfT methods use the material’s Young modulus and/or Poisson’s ratio. The parameters of all the compared SfT methods are tuned by trial and error to give the best results. The ground-truth shapes of real data experiments are obtained using the PhotoScan software. PhotoScan reconstructs the 3D scene from multiple images using Structure-from-Motion.

Synthetic Data [partially stretched surface] We use Blender to simulate a rubber like material. The template shape is a rectangular flat surface and its size is $300\times 400$ mm. We partially stretch this surface from its longest side in a continuous manner up to $66\%$ extensibility ratio as shown in Fig. 10. We sequentially pick 50 ground-truth shapes from this continuous deformation. We then generate synthetic images of size $1,024\times 1,024$ pixels of these ground-truth shapes using a pinhole camera model with focal length 770 pixels and principal point at (512, 512). In order to reconstruct the shapes, we choose 20 boundary points where the pulling forces are applied on the deformed ground-truth shapes. Figure 11 shows the reconstructed shapes from the noisy synthetic image with extensibility ratio $66\%$ from Fig. 10. We observe that Particle-SfT yields a better reconstructed shape than the other methods. Malti13 and Haouchine14 give similar results, less accurate at the lower-right corner of the shape compared to Particle-SfT. Bartoli12c gives a worse result, since it can only handle conformal deformations but not general elastic ones. Malti15 gives the worst result, since it is a convex approximation with a linear elasticity model of a non-convex problem with nonlinear behavior.

Fig. 12

3D errors of elastic SfT methods versus extensibility ratio, Gaussian noise level, and number of correspondences. The 3D error for Malti15 is off the graphs’ axis limits

Table 3 Mean error and run time for the varying extensibility ratio results of Fig. 12

Fig. 13

Reconstructed shapes (black circles) with extensibility ratio $66\%$ and the ground-truth shapes (green dots). The 20 boundary points (red dots) are chosen on the lateral sides of the ground-truth shape where no pulling forces are applied. Each column shows the same reconstructed shape from two different viewpoints, and gives the 3D errors in millimeters (mm) (Color figure online)

Noise and number of correspondences We test the robustness of the shape reconstruction methods against three varying parameters: extensibility ratio, noise level and number of correspondences. The extensibility ratio varies from $0\%$ to $66\%$ with a step of about $1.32\%$. The standard deviation $\sigma$ of Gaussian noise varies from 0 to 2 pixels with a step of 0.2 pixels. Correspondences are selected randomly. The number of correspondences varies from 50 to 300 points with a step of 50 points. While one of the parameters is varied, the other two are kept fixed. Fixed default values are $66\%$ extensibility ratio, 100 random correspondences and $\sigma = 1$ pixel. Figure 12 shows the 3D errors of the SfT methods versus extensibility ratio, Gaussian noise level and number of correspondences. Table 3 lists the mean of 3D errors and run times of the compared methods on the varying extensibility ratio experiments whose results are shown in Fig. 12. We observe from Fig. 12 and Table 3 that Particle-SfT yields about 3 times more accurate results than the other methods in almost all configurations except at very small extensibility ratios. On less deformed surfaces all methods perform with about the same order of accuracy.

Fig. 14

Real elastic datasets. In each box, the left image shows the template image and the right image shows the input image used in SfT

Fig. 15

SfT results for an underfoot surface reconstruction of foot size 41 wearing a sock for foot size 37. The first column shows the input image. Red markers on the input image show the point correspondences used in SfT. The last 5 columns show the reconstructed shapes (black circles) on the ground-truth shapes (green dots) with front and side views. The 3D reconstruction errors are also given for each method (Color figure online)

Change of boundary locations We reconstruct the shape which has extensibility ratio $66\%$ seen in Fig. 10 from the noisy synthetic image. We choose, this time, the 20 boundary points on the lateral sides of the deformed ground-truth shape where no pulling forces are applied. For all elastic methods, except Malti15, the reconstructions are now worse than the previous case where the boundary points are chosen about the locations of the pulling forces. Figure 13 shows the results of Bartoli12c, Malti13, Malti15, Haouchine14 and Particle-SfT for this new case. Since Bartoli12c does not need boundary conditions, its result is the same as in Fig. 11 and here becomes the most accurate solution when no strong priors on boundary conditions are exploited. However remark that Bartoli12c needs the correct scale with respect to the ground-truth shape and one should know how to choose the best solution from its multiple solutions. We observe that Particle-SfT yields once more a better reconstructed shape than the other elastic methods. However the difference in results is less significant because the new boundary locations introduce ambiguities for all elastic methods.

Real Data [foot] We use a sock for foot size 37 as a template. We then put this sock on a foot whose size is 41, and take its image to be used as input for SfT. In Fig. 14, the left box shows the template and the input images of this sock. We match 137 point correspondences between the template image and the input image. We choose 37 of the 137 points as the known boundary conditions from the border points of the ground-truth shape. Figure 15 shows the reconstructed shapes of the compared methods and lists the 3D errors. We observe that all the refining methods perform better than the initializing methods, and that the performances of refining methods are similar in accuracy. However, Particle-SfT outperforms all the other methods.

Real Data [pocket] We use a piece of elastic cloth, whose size is $20\times 14$ cm, to make a pocket for holding objects. The cloth is fixed on a cork board with 5 pins, where it was laid flat as in the template image shown in Fig. 14, middle. We then insert a bottle of water and a magazine in the pocket. The distances between the fixing pins before the objects were put inside and after, are the same. The elastic deformation on the pocket due to inserted objects is stronger at the borders between the pins. The elastic deformation on the surface, where the grid is drawn, is moderate. The pocket grid contains 88 points. We use these 88 points as correspondences for reconstruction. 25 boundary points obtained from the left, bottom and right sides of the grid, are used as boundary constraints. Figure 16 shows the reconstructed shapes for the compared methods and lists the 3D errors. We observe that again all the refining methods perform better than the initializing methods, and their performances are similar in accuracy. Once more, Particle-SfT outperforms the other methods.

Fig. 16

SfT results for the pocket data. The input image shows a pocket filled by a bottle of water and a magazine. The last 5 columns show the reconstructed shapes (black dots) on the ground-truth shapes (green mesh) with front and bottom views. The 3D reconstruction errors are also given for each method (Color figure online)

Fig. 17

SfT results for a piece of fabric which has large lateral stretching and a mild central pushing deformation. The left most column shows the deformed fabric. The last 5 columns show the reconstructed shapes (black dots) on the ground-truth shapes (green mesh) with front and side views. The 3D reconstruction errors are also given for each method (Color figure online)

Real Data [extensible fabric] We draw a regular grid on a piece of extensible fabric. The size of the grid is $15\times 20$ cm. We then pin this fabric from its upper and lower parts down to a fixed cork board, and insert an object between the fabric and the board to create extension and curvature, as shown in Fig. 14, right. The grid extension is $33\,\%$ along the vertical axis between the upper and lower parts. This extension causes shrinking of $20\%$ of the grid along the lateral axis. The grid contains 336 points. We use these 336 points as correspondences for reconstruction. 42 of them are used as boundary constraints. These 42 boundary points are located on the upper and lower edges of the grid. Figure 17 shows the reconstructed shapes of the compared methods and lists the 3D errors. We observe that again all the refining methods perform better than the initializing methods, and their performances are similar in accuracy. This time, Particle-SfT yields the second best result, after Haouchine14.

As a general conclusion, we observe from Figs. 15, 16 and 17, that the refining methods Malti13, Haouchine14 and Particle-SfT reconstruct shapes quite well. The extensibility ratio results with synthetic data in Fig. 12 also confirm that conclusion. In synthetic data results, we see that Particle-SfT outperforms the other methods. In Figs. 15 and 16, in real data results, Particle-SfT also outperforms the other methods and improves the results of other refining elastic methods of at least $15\%$. Only in Fig. 17 Particle-SfT yields the second best result, after Haouchine14.

Convergence basin We compare the refining methods Malti13 and Haouchine14 with Particle-SfT in terms of convergence basin using the simulated rubber like material shown in Fig. 10 with extensibility ratio $66\%$ and using the real elastic datasets (foot, pocket, extensible fabric) shown in Fig. 14. For real elastic datasets, we use the same correspondences and boundary points as for the above elastic SfT experiments. For the simulated rubber, we take its synthetic image and randomly select 120 point correspondences between the template and the image. We also add Gaussian noise with $\sigma = 1$ pixel to the image points. We choose 20 of the 120 points as the boundary points located exactly at the same places as shown in Fig. 11. We then generate initial guesses by perturbing the ground-truth shapes of the real elastic datasets and the simulated rubber. Afterwards we let Malti13, Haouchine14 and Particle-SfT start from these guesses. A guess with $1\%$ perturbation level is equal to the ground-truth shape multiplied by a scale factor 1. It is multiplied by 10 for $10\%$ perturbation level and so on. We increase the perturbation level from $1\%$ to $100\%$ with a step of $10\%$. Figure 18 shows the datasets used in the convergence basin experiment and the mean 3D error of SfT methods versus perturbation level on the ground-truth shapes used as initial guesses. We observe that Haouchine14 and Particle-SfT come back to the expected solutions, while Malti13 starts diverging after $30\%$ perturbation level.

Fig. 18

3D errors of SfT methods versus perturbation on the ground-truth shapes used as initial guesses

Fig. 19

3D errors of SfT methods versus perturbation on the ground-truth shape used as an initial guess

We repeat this experiment for another deformed shaped. This time, the rubber like material is pushed up from below by a cube by about 200 mm with its corners kept fixed. We take a synthetic image of this ground-truth shape and randomly select 200 point correspondences between the template and the image. We also add Gaussian noise with $\sigma = 1$ pixel to the image coordinates. We choose 35 of 200 points as the boundary points which correspond to the fixed corners of the rubber material and to the border contact points between the pushing cube and the rubber material. We generate initial guesses by perturbing this ground-truth shape. Afterwards we let Malti13, Haouchine14 and Particle-SfT start from these guesses. A guess with $1\%$ perturbation level is equal to the ground-truth shape multiplied by a scale factor 1.01. It is multiplied by 1.02 for $2\%$ perturbation level and so on. We increase the perturbation level from 0 to 100% with a step of $1\%$. The graph in Fig. 19 shows the 3D errors versus perturbation level for this inner pushing. We observe that Malti13 and Haouchine14 miss the solution after $10\%$ perturbation on the ground-truth shape whereas Particle-SfT still finds the expected solution. This is a special case where Haouchine14 cannot refine the initial solution in any case, while Malti13 can only refine it for very small perturbations. The low error observed at the beginning of the error graph in Fig. 19 for Haouchine14 is because of the initial guess being equal to the exact ground-truth shape without any perturbation.

Fig. 20

Particle-SfT recovers the hidden part using gravity as measured by a smartphone (Color figure online)

Fig. 21

Particle-SfT recovers occluded part using gravity as measured by a smartphone. The second and third columns show the reconstruction (black mesh) overlaid on the ground-truth shape (green mesh) without and with gravity respectively from two different viewpoints (Color figure online)

Table 4 The template’s data structure in Particle-SfT

7.3 Hidden Parts from Gravity

In gravity based experiments, we consider objects with textureless, hidden or occluded parts in the image. We assume that these parts are deformed by the gravitational force. Our objective is then to reconstruct the full shape of the object from its partly textureless/hidden/occluded image and the known gravity vector. We use a smartphone’s camera to take the input image of the deformed object and the smartphone’s accelerometer to measure the direction of the gravity vector. We achieve the full shape reconstruction by setting the force vector in Particle-SfT to the gravity vector for all the textureless/hidden/occluded particles. The reconstruction errors in the experiments below may be explained by the particle model not modeling the deformed object perfectly and the noise on the gravity vector measured by the accelerometer. Particle-SfT is the first SfT method which allows one to use gravity.

Gravity experiment 1 In this scenario, we have a piece of cloth laid on a table with a visible part and a hidden part in the image. The hidden part is deformed by the gravitational force. The deformation correction strengths are chosen as $s_{A}=1$ and $s_{B}=0.2$. Figure 20 shows this experimental scenario. The cloth’s size is $30\times 30$ cm. An 11 by 11 regular grid is sketched onto the surface of the cloth. In the input image we use the visible 77 grid points as point correspondences between the template and input image. Figure 20 contains respectively the template shape of the cloth, the input image, the fully reconstructed shape and an image revealing the whole cloth. We also reconstruct the ground-truth shape from the right image shown in Fig. 20 and compare it to the shape reconstructed from the input image. The 3D error between the corresponding ‘hidden part’ of the ground-truth shape and the reconstructed shape is found as 8 mm. This corresponds to a $2.6\%$ error with respect to the size of the cloth.

Gravity experiment 2 In this scenario, we have a piece of cloth hanged on a laundry holder. The cloth has a visible part and an occluded part in the image. The occluded part is deformed by the gravitational force. The deformation correction strengths are chosen as $s_{A}=1$ and $s_{B}=0.1$. Figure 21 shows this experimental scenario. The cloth’s size is $40\times 20$ cm. We have 36 point correspondences between the template and input image. Figure 21 in its first column shows the input image and template, in the second and third columns the reconstructed shape (black mesh) overlaid on the ground-truth shape (green mesh) without gravity and with gravity from two different viewpoints, and in the last column an image revealing the whole cloth and its reconstructed shape which is used as ground-truth shape for comparison. We compare the ground-truth shape with the shapes reconstructed without and with gravity from the occluded input image. The 3D errors are listed below the reconstructions in Fig. 21. We observe that Particle-SfT with gravity reconstructs the correct shape to a good extent but misses it without gravity.

8 Conclusions

We have proposed Particle-SfT, the first SfT algorithm guided by constraint projections and forces, and capable of reaching a highly accurate solution without an initial guess. Because Particle-SfT has low complexity and is generic in the types of deformation constraints it uses, it may be used in place of any other existing refinement algorithm. Our experimental results show that Particle-SfT reaches the same accuracy that the best performing isometric SfT method while consistently outperforming existing non-isometric SfT methods in almost all cases. The core of Particle-SfT is to enforce constraint subsets independently and optimally, allowing it to converge faster. Particle-SfT is provably convergent.

Remark that the template of Particle-SfT includes more information than previous SfT methods so that it can cope well with both isometric and elastic deformations. We list in Table 4 the template’s exact data structure and how each field is obtained. The template’s shape and texturemap are obtained from multiple images of the object at rest using Structure-from-Motion. The density of the material of which the object is made is known from the material’s properties. The object’s surface thickness can be precisely measured beforehand. Only the stretching and bending correction strengths need tuning. We set $s_{A}=1$ for the isometric deformations since there is no stretching, and therefore only $s_{B}$ needs tuning. We tune both $s_{A}$ and $s_{B}$ for the elastic deformations. One of the perspectives of our future work is to be able to compute these two correction strengths automatically from the material’s mechanical parameters such as Young’s modulus and/or Poisson’s ratio since those parameters encode the material’s elasticity behavior. Our second perspective is to extend Particle-SfT to volumetric objects, and the third one is to investigate Particle-SfT for objects made of mixed materials, thus having inhomogeneous stiffness.