Optimal Linear Transformation
In shape matching problem between 3D point sets, Optimal Linear Transformation between point sets plays an important role. I'll follow notations in [1] as far as I can.
Problem
Let there be two 3D point sets, $p_i = [x_i, y_i, z_i]^t, p^{'}_i = [x^{'}_i, y^{'}_i, z^{'}_i]^t, i= 1,2,\cdots, N$.We want to find matrix $X$ that minimizes
$$
\begin{align}
\sum_{i = 1}^{N} \| p^{'}_i - Xp_i \|^2 = \sum_{i = 1}^{N} \{ \| p^{'}_i \|^2 - 2 p^{'}_i \cdot (X p_i) + \| Xp_i \|^2 \} \tag{1} \\
\end{align}
$$
Solution
We can easily find minimum of (1) by completing the square. First, from the fact that for some arbitrary column vector $k$, $ \| k \|^2 = k \cdot k = tr(kk^T) $, (1) can be rewritten as (2),$$
\begin{align}
\sum_{i = 1}^{N} tr( p^{'}_i (p^{'}_i)^T - 2 p^{'}_i (p_i)^T X^T + Xp_i (p_i)^T X^T )
= tr(A_{p^{'}} - 2MX^T + XA_p X^T ) \tag{2} \\
\end{align}
$$
where sum of outer products is defined as follows :
$$
A_p = \sum_{i = 1}^{N} p_i (p_i) ^T,
A_{p^{'}} = \sum_{i = 1}^{N} p^{'}_i (p^{'}_i) ^T,
M = \sum_{i = 1}^{N} p^{'}_i (p_i)^T
$$
Second, since that the trace of square matrix which is the product of two matrices can be rewritten as the sum of entry-wise products of their elements (implies $tr(A^TB) = tr(AB^T) = tr(B^TA) = tr(BA^T) \ \forall m \times n \ matrices \ A, B$. Then, we can rewrite expression (2) as follows
$$
\begin{align}
&tr(A_{p^{'}} - MA_p^{-1}M^T + MA_p^{-1}M^T - XM^T - MX^T + XA_pX^T) \\
&= tr(A_{p^{'}} - MA_p^{-1}M^T) + tr(MA_p^{-1}M^T - XM^T - MX^T +
XA_pX^T) \\
&= tr(A_{p^{'}} - MA_p^{-1}M^T) + tr((XA_p - M)(X - MA_p^{-1})^T)
\tag{3} \\
\end{align}
$$
Note that every positive semidefinite matrix can be written as a sum of outer products A = XX^T , and every invertible positive semidefinite is positive definite.
(Still working......)
Can't understand why?
- Chapter 4.A of [1] : "In fact, the matrix A; is positive definite, provided that at least four
measurements are available that are not collinear."
댓글
댓글 쓰기