Skip to main content

Superimposing shapes

In the previous video we have seen that if we are given shapes in correspondence, then computing a shape model is straight-forward. However, in our exposition we were a bit careless. Remember that shape is defined only up to translation and rotation. It could still be that the deformation fields contain translation and rotational components instead of pure shape changes.

An example of such a deformation field is shown in Figure 1. Before building the model, we therefore have to correct the pose of the shape. This is usually done using a method called Procrustes alignment, which we will introduce in this article. For the (rather gruesome) origin of the term Procrustes, see this Wikipedia article.

hand deformation field
Figure 1: a deformation field between two hand shapes, which does not only represent shape changes, but also rotational and translation components.

Procrustes alignment of two point sets​

If two shapes ΓR\Gamma_R and ΓT\Gamma_T are in correspondence, this means that for every point x∈ΓRx \in \Gamma_R, we can identify the corresponding point y∈ΓTy \in \Gamma_T. (In the preceding video, we said that the correspondence is induced by the deformation field uu, i.e. y=x+u(x)y = x + u(x).)

Let us pick two finite sets of points on the contour of the shape X={x1,…,xn}⊂ΓRX = \{x_1, \ldots, x_n\} \subset \Gamma_R

and the corresponding points Y={y1,…,yn}⊂ΓT.Y = \{y_1, \ldots, y_n\} \subset \Gamma_T.

To eliminate the effect of rotation and translation, we can minimise the following optimisation problem

(t∗,R∗)=arg mint∈R2,R∈R2×2∑i=1n∥xi−R(yi−t)∥2, s.t. RTR=I,  det⁡(R)=1(t^*, R^*) = arg\,min_{t \in \mathbb{R}^2, R \in \mathbb{R}^{2 \times 2}} \sum_{i=1}^n \|x_i - R(y_i - t)\|^2, \\ \text{ s.t. } R^T R = I, \, \, \det(R)=1

to obtain the translation t∗t^* and rotation RR, which we can use to superimpose the two shapes.

It turns out that this problem has a closed-form solution both in 2D and 3D, which can be efficiently computed using a singular value decomposition. We refer to the paper by Lorusso et al. for the mathematical details [1].

Generalised Procrustes alignment​

Given a set of shapes Γ(1),…,Γ(m)\Gamma^{(1)}, \ldots, \Gamma^{(m)}, we could pick one of the shapes as a reference shape, say ΓR=Γ(1)\Gamma_R = \Gamma^{(1)}, and align all the shapes to this reference using the above procedure. This choice of reference may seem a bit arbitrary. There is, however, a more principled way of doing this, which is usually referred to as generalised Procrustes alignment. The idea is that, since we have correspondence between all the shapes, we can compute a mean shape defined by Γμ={μ1,…,μn}\Gamma_\mu = \{\mu_1, \ldots, \mu_n\} with μi=1m∑k=1mxi(k), i=1,…,n.\mu_i = \frac{1}{m} \sum_{k=1}^m x_i^{(k)} , \, i =1, \ldots, n.

The generalised Procrustes alignment is obtained using the following procedure:

  1. Choose an arbitrary shape as the reference shape ΓR\Gamma_R.
  2. Align all shapes Γ(1),…,Γ(m)\Gamma^{(1)}, \ldots, \Gamma^{(m)} to ΓR\Gamma_R using the procedure above.
  3. Compute the mean shape Γμ\Gamma_\mu for the set of aligned shapes.
  4. Iterate using the mean shape as the new reference shape.

Generalised Procrustes alignment

Figure 2: An illustration of the generalised Procrustes alignment.

This procedure is illustrated in Figure 2, where the solid shape indicates the current reference. The leftmost image shows the initial situation, where an arbitrary shape is chosen as a reference. The shapes are aligned to the reference (2nd image) and the mean is recomputed (3rd image). The rightmost image shows the situation after an additional alignment step. We notice that already in this step only minor adjustments are made. Indeed, the procedure usually converges within a few iterations.

References​

[1] Lorusso, Adele, David W. Eggert, and Robert B. Fisher. A comparison of four algorithms for estimating 3-D rigid transformations. University of Edinburgh, Department of Artificial Intelligence, 1995.