A Centroid Coincidence Theorem
While reviewing shape matching problem between 3D point sets of rigid object using least squares approximation. I found A Centroid Coincidence Theorem, which interest me. So I organize the proof of the theorem and related notions in here.
I'll follow mathematical notation of [1] as possible as I can. But, since, the mathematical notations in [1] is to implicit, I write it more explicitly (because of my poor imagination and mathematical skills).
Problem
Let two 3-D point sets as $p_i = [x_i, y_i, z_i]^t, p^{'}_i = [x^{'}_i, y^{'}_i, z^{'}_i]^t, i= 1,2,\cdots,N$. Which is related by (1) where $R$ is $3\times 3$ rotation matrix, $T$ is $3\times 1$ translation vector, and $N_i$ a noise vector.$$
\begin{align}
p^{'}_i &= Rp_i + T + N_i \tag{1}
\end{align}
$$
And let mathematical formulation of shape matching of 3D point sets using least squares approximation as (2).
$$
\begin{align}
\underset{R, T} {\operatorname{argmin}} \sum_{i=1}^{N} \| p^{'}_i - (Rp_i + T) \|^2 \tag{2}
\end{align}
$$
Then the Theorem 1 is satisfied..
Theorem 1 (A Centroid Coincidence Theorem) Let $\hat{R}$ and $\hat{T}$ be the least-squares solution to (2). Then the centroids of $ \{ p^{'}_i \} $ and $ \{ \hat{R} p_i + \hat{T} \} $ coincide.
Proof
Let$$% '&=' sign in align region means align at equal sign. \begin{align}
p^{'}_i &= Rp_i + T + N_{i} \tag{3} \\
p^{''}_i &= [ x^{''}_i, y^{''}_i, z^{''}_i ] \triangleq \hat{R} p_i + \hat{T} \tag{4} \\
p &\triangleq \sum_{i=1}^{N} p_i \ (Centroid\ of\ \{ p_i \}) \tag{5} \\
p^{'} &\triangleq \sum_{i=1}^{N} p^{'}_i \ (Centroid\ of\ \{ p^{'}_i \}) \tag{6} \\
p^{''} &\triangleq \sum_{i=1}^{N} p^{''}_i \ (Centroid\ of\ \{ p^{''}_i \}). \tag{7} \\
\end{align}$$
We reformulate our problem as follows:
$$\begin{align}
\underset{ \{ p^{''}_i \} } {\operatorname{argmin}} \sum_{i=1}^{N} \| p^{'}_i - p^{''}_i \|^2 \tag{8}
\end{align}$$
\underset{ \{ p^{''}_i \} } {\operatorname{argmin}} \sum_{i=1}^{N} \| p^{'}_i - p^{''}_i \|^2 \tag{8}
\end{align}$$
subject to the rigidity constraints
\end{align}$$
Note that $p_i, p^{'}_i$ are known, and $p^{''}_i$ is unknown variable.
We can attempt to solve above problem with Lagrangian Multipliers.
Let
f( p^{''}_1 , \dots , p^{''}_N ) &= \sum_{i=1}^{N} w_i \| p^{'}_i - p^{''}_i \|^2 \tag{9} \\ g_{ij}( p^{''}_1 , \dots , p^{''}_N ) &= \| p^{''}_i - p^{''}_j \|^2 - \| p_i - p_j \|^2 \tag{10} \end{align} $$
Then, the equation for Lagrangian Multipliers can be formulated as follows:
$$\begin{align}\nabla f( p^{''}_1 , \dots , p^{''}_N ) = \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{ij} \nabla g_{ij}( p^{''}_1 , \dots , p^{''}_N ) \tag{11}\end{align}$$
where $\lambda_{ij} = \lambda_{ji}$ (because, obiviously, $g_{ij}$ and $g_{ji}$ are same function.)
Then, system of equations is derived from Equ. (11) as follows:
$$
\begin{align}
2w_{1}(x^{''}_1 - x^{'}_1) &= 4 \sum_{j=1}^{N} \lambda_{ij} (x^{''}_1 - x^{''}_j) \\
2w_{2}(x^{''}_2 - x^{'}_2) &= 4 \sum_{j=1}^{N} \lambda_{ij} (x^{''}_2 - x^{''}_j) \\
&\vdots \\
2w_{N}(x^{''}_N - x^{'}_N) &= 4 \sum_{j=1}^{N} \lambda_{ij} (x^{''}_N - x^{''}_j) \\
\end{align}
$$
Summation of equations in above system produces, $$ \begin{align} 2 \sum_{i = 1}^{N} w_i(x^{''}_i - x^{'}_i) &= 0 \\ \sum_{i = 1}^{N} w_i x^{''}_i &= \sum_{i = 1}^{N} w_i x^{'}_i \\ \end{align} $$ $$Q.E.D.$$
Insight
It shows that the determination of $R$ and $T$ can be decoupled by translating original point set with its center of mass.
댓글
댓글 쓰기