procrustes分析原理与应用

procrustes问题

procrustes问题可以描述如下：给定两个矩阵\(\mathbf{A}\)和\(\mathbf{B}\)，寻找一个最佳的相似变换使得$$\|s\mathbf{R}\mathbf{A}-\mathbf{B}+\mathbf{T}\|$$最小，即
$$(s,\mathbf{R},\mathbf{T}) = \arg\min_{s,\mathbf{R},\mathbf{T}}\|s\mathbf{R}\mathbf{A}-\mathbf{B}+\mathbf{T}\|$$

问题求解与证明

矩阵\(\mathbf{A}\)和\(\mathbf{B}\)可以分别视为空间内的一组点，于是该问题可以理解为求解空间中两个几何体的最佳相似变换。最佳的缩放系数和平移量为平均半径之比和重心相对位移。以\(\mathbf{A}_j\)标记\(\mathbf{A}\)的列向量，则重心为$$\mathbf{G}_{\mathbf{A}} = \frac{1}{n}\sum_{j=1}^{n} \mathbf{A}_j := E(\mathbf{A})$$
平均半径为$$r_{\mathbf{A}} = \sqrt{\frac{1}{n} \sum_{j=1}^n \| \mathbf{A}_j - \mathbf{G}_{\mathbf{A}} \|^2}:= Var(\mathbf{A})$$
对于\(\mathbf{B}\)同理。
令\( s = r_{\mathbf{B}}/r_{\mathbf{A}}\)，\(T = E(\mathbf{B}) - s\mathbf{R}E(\mathbf{A})\)，目标函数得到化简
$$E = \|\mathbf{R}s(\mathbf{A}-E(\mathbf{A})) - (\mathbf{B}-E(\mathbf{B}))\| = \|\mathbf{R}\frac{\mathbf{A}-E(\mathbf{A})}{r_{\mathbf{A}}} - \frac{\mathbf{B}-E(\mathbf{B})}{r_{\mathbf{B}}}\| := \|\mathbf{R}\mathbf{P}-\mathbf{Q}\|$$
原问题转化成了正交procrustes问题，即求解$$R = \arg\min_{\mathbf{\Omega} \in \mathcal{SO}}\|\mathbf{R}\mathbf{P}-\mathbf{Q})\|$$
结论为\(\mathbf{R} = \mathbf{U}\mathbf{V}^T\)，其中\(\mathbf{U},\mathbf{V}^T\)是对\(\mathbf{M} = \mathbf{Q}\mathbf{P}^T\)的奇异值分解得到两个正交矩阵，即
$$\mathbf{M} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T$$
证明过程如下
$$\begin{aligned}
\mathbf{R}&=\arg \min _{\mathbf{\Omega} }||\mathbf{\Omega} \mathbf{P}-\mathbf{Q}\|_{F}^{2}\\&=\arg \min _{\mathbf{\Omega} }\langle \mathbf{\Omega} \mathbf{P}-\mathbf{Q},\mathbf{\Omega} \mathbf{P}-\mathbf{Q}\rangle \\&=\arg \min _{\mathbf{\Omega} }\|\mathbf{P}\|_{F}^{2}+\|\mathbf{Q}\|_{F}^{2}-2\langle \mathbf{\Omega} \mathbf{P},\mathbf{Q}\rangle \\&=\arg \max _{\mathbf{\Omega} }\langle \mathbf{\Omega} ,\mathbf{Q}\mathbf{P}^{T}\rangle \\&=\arg \max _{\mathbf{\Omega} }\langle \mathbf{\Omega} ,\mathbf{U}\Sigma \mathbf{V}^{T}\rangle \\&=\arg \max _{\mathbf{\Omega} }\langle \mathbf{U}^{T}\mathbf{\Omega} \mathbf{V},\Sigma \rangle \\&=\mathbf{U}\left(\arg \max _{\mathbf{\Omega}'}\langle \mathbf{\Omega}',\Sigma \rangle \right)\mathbf{V}^{T}\\&=\mathbf{U}\mathbf{V}^{T}.
\end{aligned}$$

应用

在CV中，procrustes分析可以应用在点云配准（Rigid ICP），轮廓对齐等。

最后送一波福利，基于dlib和procrustes分析的简易换脸术

未经允许不得转载：Charlie小站 » procrustes分析原理与应用