形变

图形学上，形变包括几个控制点，这些控制点可以是点，线，甚至是三角形网格。形变算法的作用就是将物体进行形变以使得相应的控制点满足要求。

mls要解决的问题是，对于某个物体，假如其关键点需要变动到一个新的位置，那么这个物体的其他部分要怎样变动才能够显得自然真实呢？这就需要使用到image deformation这一个技术了。

mls算法

首先解释下moving这个名字的来历，由于mls针对每一个像素位置v都会独立算一个映射方式，因此被称为moving.
算法的目标是：
对于每一个像素位置v，优化一个映射函数$l_v(p_i)$，使得

$min\left[\sum_i w_i|l_v(p_i)-q_i|\right]$

其中$p_i$是第i个控制点的位置，$q_i$是控制点 $p_i$ 按照当前的$l_v$映射后的像素的位置，也就是用户将控制点移到的新位置。

$w_i = \frac{1}{|p_i-v|^{2\alpha}}$

控制点对当前点的权重由$\alpha$决定，这个映射要满足这样的条件：

$l_v(p_i) = q_i$

并且，如果控制点不动，那么这个算出来的映射关系也应该是一个等价映射，也就是

$if\ p_i=q_i, then\ l_v(x)=x\ for\ all\ x$

根据映射函数的种类不同，可以有多种mls

1. Affine transformation

假如$l_v$是一个仿射变换：

$l_v(x) = xM + T$

将这个形式代回

$min\left[\sum_i w_i|l_v(p_i)-q_i|\right]$

直接对T求导并使导数为0，得$T = q*-p*M$
其中:

$q_*=\frac{\sum_iw_iq_i}{\sum_iw_i} \\ p_*=\frac{\sum_iw_ip_i}{\sum_iw_i}$

求得T后代回$l_v$的表达式，我们可以获得$l_v$的最优解：

$l_v(x) = (x-p_*)M + q_*$

现在问题来了，T已经解出来了，那么M要满足什么条件呢？
还是之前的路子，先把这个解了T的$l_v$代回去最早的优化问题，我们得到：

$min \left[\sum_i w_i|\hat{p_i}M - \hat{q_i}|^2\right] \\ where\ \hat{p_i}=p_i-p_*, \hat{q_i} = q_i - q_*$

现在实际上$\hat{p_i}, \hat{q_i}$是已知的，那么这就是一个标准的线性最小二乘问题，变量是M。之前优化3DMM、优化摄像机矩阵的时候都用到线性最小二乘问题的解法，只不过当时变量是一个向量，而在这里M是一个矩阵。

故技重施，对M求导，令导数为0，我们得到：

$\hat{M} = (\sum_i \hat{p_i}^Tw_i\hat{p_i})^{-1}\sum_j\hat{p_j}w_j\hat{q_j}$

原论文漏写了右边的 $w_j$ ，相信应该是笔误。将M代入

$l_v(x) = (x-p_*)M + q_*$

我们得到

$f_a(x) = l_v(x) = (x-p_*) (\sum_i \hat{p_i}^Tw_i\hat{p_i})^{-1}\sum_j\hat{p_j}w_j\hat{q_j} + q_*$

下标a表示这个只是接近最优(approximate)。至此，我们已经获得了$l_v$的完整表达式，对每个像素位置v计算一个$l_v$就得到了全图的deformation formula.

在$l_v$是Affine Transformation的基础上，根据M的不同还能继续细分

Affine Transformation对M不作限制，因此M会包括切变。如果限制M只能包括旋转平移和scale，那么就称之为similarity deformations. 如果限制M只能够旋转平移，那么就称之为rigid deformations.

similarity deformation
限制shear, 也就是说M进行QP分解的时候，P只能是对角矩阵且对角线的值一致。原因很简单，假如M=QP, 那么xM = xQP, xQ表示旋转操作，xQP表示对旋转后的结果进行scale操作，此时P需要是uniform scale。在这样的条件下，$M^TM=P^TQ^TQP=\lambda I$，这就是M是相似变换需要满足的条件。多了这个条件后，M的自由度减少，假设将M写成以下两个列向量的区块形式： $M = (M_1\ M_2)$ 那么我们有 $M_1^TM_1=M_2^TM_2=\lambda^2, M_1^TM_2=0$ ，所以M可以仅由M1表示： $M = (M_1, M_1^\bot)$ .

由于我们实际要求M，所以会把$\bot$加到 $x-p_*$ 上面，所以

$min \left[\sum_i w_i|\hat{p_i}M - \hat{q_i}|^2\right]$

改为：

$min \left[\sum_i w_i\left|\left( \begin{array}{c} \hat{p_i} \\ -\hat{p_i^\bot} \end{array} \right)M_1 - \hat{q_i}^T\right|^2\right]$

同样的方法解即可，具体看论文，就不再进行推导了。负号的来源：
这里$\bot$的定义就是和原向量垂直的向量，也就是$(x, y)^\bot=(-y, x)$，那么

$pm^\bot = (p_1\ p_2)\left(\begin{array}{c} -m_2 \\ m_1 \end{array}\right) = -\left((-p_2\ p_1)\left(\begin{array}{c} m_1 \\ m_2 \end{array}\right)\right)^T = -p^\bot m$

因此

$min \left[\sum_i w_i\left|\hat{p_i}(M_1\ M_1^\bot) - \hat{q_i}\right|^2\right] \\ \Rightarrow min \left[\sum_i w_i\left|\left( \begin{array}{c} \hat{p_i} \\ -\hat{p_i^\bot} \end{array} \right)M_1 - \hat{q_i}^T\right|^2\right]$

rigid deformation

rigid就更进一步，不允许scale,也就是$M^TM=P^TQ^TQP=I$，这里论文作者用了一个简单结论从simiarity推广到了rigid.

使用线段控制deformation

使用控制线段的mls的开源实现不多，大多数都只是基于控制点的实现。

未完待续