singular value decomposition

In this post, I will describe some tips on SVD from a programmer point of view.

SVD is actually one of the most important and frequently invlolved technique in graphics and animation, as it is the way to compute the transformation between correspondences. To name just a few, we were curious as being reading papers regarding motion capture facial animation, as-rigid-as-possible surface modeling, registration in capturing, etc. Hope this post give a useful guide regarding the implementation behind.

Given a set of points, in their initial configuration $p_{i}$ and current configuration $p_{i}^{t}$ , the goal is to find the transformation $[R, T]$ such that the least suqares error is minimized:

$\sum \parallel p_{i}^{t}-(R^{t}p_{i}+T^{t})\parallel^{2}$

We need a local reference frame for the point cloud, nomally by defining the centroid. Let it be denoted by $p_{*}$ , so $p_{*}^{t}$ for the one at time $t$ . To this end, how to minimize the error? We change the least squares function

$\sum \parallel p_{i}^{t}-p_{*}^{t}+p_{*}^{t}-[R^{t}(p_{i}-p_{*}+p_{*})+T^{t}]\parallel^{2}$ $=\sum \parallel \overline{p_{i}^{t}} + p_{*}^{t} - R^{t}\overline{p_{i}^{t}} - (R^{t}p_{*}+T^{t})\parallel^{2}$ $=\sum \parallel \overline{p_{i}^{t}}- R^{t}\overline{p_{i}^{t}} - (R^{t}p_{*}+T^{t}-p_{*}^{t})\parallel^{2}$ $=\sum \parallel \overline{p_{i}^{t}}- R^{t}\overline{p_{i}^{t}} \parallel^{2} -2\sum (\overline{p_{i}^{t}}- R^{t}\overline{p_{i}^{t}})(R^{t}p_{*}+T^{t}-p_{*}^{t}) + \sum \parallel (R^{t}p_{*}+T^{t}-p_{*}^{t})\parallel^{2}$

A variety of centroid definition simplifies the minimization as to minimize $\sum \parallel \overline{p_{i}^{t}}- R^{t}\overline{p_{i}^{t}} \parallel^{2}$ and $\sum \parallel (R^{t}p_{*}+T^{t}-p_{*}^{t})\parallel^{2}$ . So means, first, to compute $R$ , and then $T$ . Minimizing the first term is to construct the convariance matrix

$\mathsf{S}=\sum \overline{p_{i}}\overline{p_{i}^{t}}^\intercal$

and then perform SVD on this matrix

$\mathsf{SVD(S)}=\mu\varepsilon\varphi^\intercal$ and $R^{t}=\varphi\mu^\intercal$ .

Takel care of the relection where $det(R^{t})<0$ . This issue is addressed by changing the sign of the column of $\mu$ corresponding to the smallest singular value (the third column), such that $det(R^{t})>0$ .

To this end, $T^{t}=p_{*}^{t}-R^{t}p_{*}$

Final, in this post, only described the solution to Absolute Orientation problem, but in practice, it is generalized to Weighted Absolute Orientation. But the core idear is the same, but different in the definition of centroid, in turn the convariance matrix.