一种基于局部坐标的线性约束图像变形方法

摘要

本发明涉及一种基于局部坐标的线性约束图像变形方法。该方法将图像转换为对应的四边域网格，用仿射和角度的线性约束描述网格的几何特征，并根据用户指定的控制顶点构造边界约束条件，求解线性方程组，快速地计算出变形后的图像。本方法能以交互式的速度获得具有平移敏感性质的变形效果，能通过调节两种线性约束的权值，控制仿射变形的比重，实现了良好的弯曲、平移敏感、各向异性缩放等复杂的变形效果。

说明书

技术领域

本发明涉及二维图像的变形技术，具体地说是涉及到对描绘了动画形象的二维图像进行变形的动画制作技术。

背景技术

大量的艺术形象，如漫画人物等，以图像的形式保存。若能用简捷的方法控制它们变形，快速地生成各种新动作和表情，可以明显地提高动画制作效率，降低制作难度。这种需求具有以下几个特点：首先这种动画形象的变形属于非精确变形，无须使用物理模拟等方法获得精确结果，只要保持基本的几何特征；其次，用户希望通过简单的手段控制变形结果；另外，算法应具有较高的鲁棒性，能以交互式的速度返回运算结果。本发明提出一种方法，把图像变形问题转换为二维网格变形问题来处理：将图像转换为四边域网格，并对该网格进行变形来解决上述问题。

网格变形是近年来的热点问题，人们提出了多种方案，但仍有几个重要问题有待解决。第一，在大幅度的变形时网格的局部几何特征有可能出现严重失真；第二，有时用户只提供了少数控制顶点的坐标平移信息，而不包含旋转信息。这时需要算法自动产生适当的旋转信息，从而获得理想的变形结果，即“平移敏感”特性。第三，由于效率的缘故，算法应尽可能采用线性运算。可惜的是，一般的非刚体变换(如弯曲、不规则变形等)不能简单表示为顶点线性运算。

为解决上述变形难题，本发明提出一种基于局部坐标的网格变形方法，从而实现快速的图像变形。

发明内容

本发明提出了用线性的仿射和角度约束描述四边域网格顶点局部特征的变形方法，并将该方法用于图像的非精确变形。用户可以通过简单地指定少数控制顶点的位置，快速地获得变形结果。本方法采用了网格的局部坐标描述几何特征，具有平移敏感的特性，可以根据控制顶点的平移信息自动产生适当的旋转量，快速生成自然的扭曲效果。另外通过赋予不同的约束权重，可以控制仿射变形在结果中的比重。本方法能够以交互式的速度获得具有平移敏感性质的变形结果，通过一步的求解线性方程组运算，方便快捷地生成二维动画形象的多种复杂变形效果。

为达到上述的目的，本发明采用的技术方案是：一种基于局部坐标的线性约束图像变形方法，该方法包含以下步骤：

首先根据输入图像构造相应的四边域网格，则可将图像变形问题转换为二维网格变形问题来处理。一幅图像I(x)作为输入，并以像素间隔d构造变形区域$D\subseteq I$对应的四边域网格M₀。该网格化过程将D看作网格M₀上的贴图，并记录下每个网格顶点相应的贴图坐标。由于M₀的顶点规则地对应着I(x)中的若干像素，而且排列规整，所以该网格构造过程相对较快，而且只需在预处理阶段执行一次则可；

然后在M₀中指定少数顶点作为控制顶点，并将它们移动或旋转到新位置。本方法将根据控制顶点信息生成相应的位置约束条件，并结合M₀的几何特征构造相应的线性方程组，然后用基于局部坐标的线性约束变形方法求解出其余顶点的位置，得到新网格M₁；

最后根据M₀中顶点的原贴图坐标，将D映射到M₁中，获得变形后的图像结果。

本发明的技术特点主要体现如下：

1、本方法中的仿射约束和角度约束都是线性的，可以根据边界条件迅速求解新顶点位置，快速获得变形结果。

2、通过调节两种约束的权重，用户可以方便地控制网格仿射变形的程度，实现良好的弯曲、平移敏感、各向异性缩放等复杂的变形效果。

3、方法具有平移敏感性质，能产生自然的变形效果，无须显式指定旋转量的分布。

附图说明

图1为本发明方法的流程示意图；

图2为本发明方法在不同约束条件下产生的变形效果图；

图3为本发明方法控制顶点及权重对变形效果的影响图。

具体实施方式

下面结合附图对本发明做进一步的说明。

本发明方法将图形的变形问题转化为对应网格M₀的变形问题。本方法首先把一幅图像I(x)作为输入，并以像素间隔d构造变形区域$D\subseteq I$对应的四边域网格M₀。为处理方便，该网格由若干边长为d的正方形构成。d选取得越小，M₀越接近D的外形，但也相应增加了运算量。由于本发明方法面向动画制作领域，D的外形细节并非关键，因而d可以选取较大的值，只要恰当地反映所需细节则可。该网格化过程将D看作网格M₀上的贴图，并记录下每个网格顶点相应的贴图坐标。由于M₀的顶点规则地对应着I(x)中的若干像素，而且排列规整，所以该网格构造过程相对较快，而且只需在预处理阶段执行一次则可。

用户随后在M₀中指定少数顶点作为控制顶点，并将它们移动或旋转到新位置。本方法将根据控制顶点信息生成相应的位置约束条件，并结合M₀的几何特征构造相应的线性方程组，然后用基于局部坐标的线性约束变形方法求解出其余顶点的位置，得到新网格M₁。

最后根据M₀中顶点的原贴图坐标，将D映射到M₁中，获得变形后的图像结果。

考虑到网格在大变形时局部特征变化很小，本方法采用局部坐标来描述网格的几何特征，即每个元素都用相邻元素的相对位置表示，那么这种描述在刚性变换和缩放时都保持不变，是平移、旋转和缩放无关的。平移敏感实质上是在满足边界顶点位置约束的前提下，使元素之间的相对旋转量尽可能小，这正是局部坐标所能办到的。采用局部坐标描述网格的几何特征，表示为下式：

$V^{*}=\underset{V^{\prime }}{\arg \min }\alpha \underset{v_i\in V}{\Sigma }{\left|\right|t\left({v_i}^{\prime }\right)-t\left(v_i\right)\left|\right|}^2$

$+\beta \underset{e_m,e_n\in E}{\Sigma }{\left|\right|r({e_m}^{\prime },{e_n}^{\prime })-r(e_m,e_n)\left|\right|}^2$

$+\omega \underset{v_k\in \Omega }{\Sigma }{\left|\right|v_k^{\prime }-u_k\left|\right|}^2$

其中v_i是原顶点位置，v_i′是新顶点位置，表示顶点在相邻标架中的局部坐标，e_m、e_n是相邻边，表示相邻边的旋转量，α、β、ω是相应的权重。

考察初始网格M₀的几何特征。它由若干相邻的正方形构成，每条边的长度相等，相邻边之间成直角或平角。因此，利用这些几何特征，可以构造良好的边长和角度约束，使变形目标网格M₁的邻边长度近似，夹角接近直角或平角。

本发明用M₀的横向边和相邻的纵向边构成一个局部直角标架f，然后用f去表示直接相邻的边，下面给出第一项约束的具体形式。

(1)仿射约束

由于M₀只由水平和垂直两个方向的边构成，而且长度相等，因此对于每个顶点，设为v₀，可以写出以下的线性关系：

$\left(\begin{array}{c}{v}_1-v_0=v_0-v_3\\ v_2-v_0=v_0-v_4\end{array}\right)$

于是新顶点在相邻局部坐标中的误差可写作：

$E_{1\left\{{v_0}^{\prime }\right\}}={\left|\right|{v_0}^{\prime }-({v_1}^{\prime }+{v_3}^{\prime })/2\left|\right|}^2$

$+{\left|\right|{v_0}^{\prime }-({v_2}^{\prime }+{v_4}^{\prime })/2\left|\right|}^2$

该误差实质上是新顶点的局部坐标到预期局部坐标的距离。则全局的仿射误差为

$E_1=\underset{{v_i}^{\prime }\in V^{\prime }}{\Sigma }{E}_{1\left\{{v_i}^{\prime }\right\}}.$

只要使得全局误差$E_1=\underset{{v_i}^{\prime }\in V^{\prime }}{\Sigma }{E}_{1\left\{{v_i}^{\prime }\right\}}$最小，则可以将边界顶点产生的误差均匀地分布到整个网格上，获得光顺的新网格。即通过求解下面带线性边界约束的最小二乘线性方程组

$V^{*}=\underset{V^{\prime }}{\arg \min }\mathrm{\alpha \Sigma }{\left|\right|H{V}^{\prime }\left|\right|}^2+\omega \underset{{v_k}^{\prime }\in \Omega }{\Sigma }{\left|\right|{v_k}^{\prime }-u_k\left|\right|}^2$

可求得使全局误差$E_1=\underset{{v_i}^{\prime }\in V^{\prime }}{\Sigma }{E}_{1\left\{{v_i}^{\prime }\right\}}$最小的新顶点位置V′。其中H是由$E_{1\left\{{v_0}^{\prime }\right\}}={\left|\right|{v_0}^{\prime }-({v_1}^{\prime }+{v_3}^{\prime })/2\left|\right|}^2$$+{\left|\right|{v_0}^{\prime }-({v_2}^{\prime }+{v_4}^{\prime })/2\left|\right|}^2$得到的权值矩阵，表示各顶点的相邻关系。

仅采用本线性约束并不能获得平移敏感效果。于是我们引入下面的第二项约束。

(2)角度约束

考虑到处理的是二维变形问题，在二维平面中互相垂直的等长向量的x和y分量可以构成以下的线性约束关系：

$\left(\begin{array}{c}{(v_1-v_0)}_x={(v_2-v_0)}_y\\ {(v_1-v_0)}_y=-{(v_2-v_0)}_x\end{array}\right).$

于是新顶点所构成的局部标架的误差为：

$E_{2\left\{{v_0}^{\prime }\right\}}={\left|\right|{(v_1-v_0)}_x-{(v_2-v_0)}_y\left|\right|}^2$

$+{\left|\right|{(v_1-v_0)}_y+{(v_2-v_0)}_x\left|\right|}^2.$

可见，该误差实质上也是新顶点的局部坐标到预期局部坐标的距离。相应得到全局角度误差为；

$E_2=\underset{{v_i}^{\prime }\in V^{\prime }}{\Sigma }{E}_{2\left\{{v_i}^{\prime }\right\}}.$

加上仿射约束，得到完整的带线性约束的最小二乘线性方程组：

$V^{*}=\underset{V^{\prime }}{\arg \min }\alpha \Sigma {\left|\right|H{V}^{\prime }\left|\right|}^2+\mathrm{\beta \Sigma }{\left|\right|K\left(\begin{array}{c}{V_x}^{\prime }\\ {V_y}^{\prime }\end{array}\right)\left|\right|}^2$

$+\omega \underset{{v_k}^{\prime }\in \Omega }{\Sigma }{\left|\right|{v_k}^{\prime }-u_k\left|\right|}^2$

其中K是由$E_{2\left\{{v_0}^{\prime }\right\}}={\left|\right|{(v_1-v_0)}_x-{(v_2-v_0)}_y\left|\right|}^2$$+{\left|\right|{(v_1-v_0)}_y+{(v_2-v_0)}_x\left|\right|}^2$得到的权值矩阵。

由于$V^{*}=\underset{V^{\prime }}{\arg \min }\alpha \Sigma {\left|\right|H{V}^{\prime }\left|\right|}^2+\mathrm{\beta \Sigma }{\left|\right|K\left(\begin{array}{c}{V_x}^{\prime }\\ {V_y}^{\prime }\end{array}\right)\left|\right|}^2$$+\omega \underset{{v_k}^{\prime }\in \Omega }{\Sigma }{\left|\right|{v_k}^{\prime }-u_k\left|\right|}^2$是线性最小二乘方程组，可写作：

其中$G=\left(\begin{array}{cc}H& 0\\ 0& H\end{array}\right),$U保存了边界顶点u_k的对应值，W是边界顶点的加权矩阵。为方便起见，通常使β＝1/α。

需要明确指出的是：虽然是线性方程组，但由于x、y分量被拆开来构造相应的约束关系，所以上式并不是顶点V′的线性方程组。由于采用了角度约束的这个技巧，从而使平移敏感性质得以实现，而且只需求解线性方程组一步则可，无须采用迭代运算。

由于为每个正方形的内角都构造了一条角度约束，因此K的秩为2‖V′‖-4。因为在边缘处的顶点比内部顶点缺少边长约束条件，或者边界顶点共线的缘故，G的秩必定小于K的秩。所以为使β不为零时方程组有解，必须至少指定2个边界顶点。可见，独立使用角度约束已可以求解顶点位置。但是仿射约束可以实现错切等仿射变形效果。用户可以通过调节α和β的比值平衡两种约束条件。

方程组是AV′＝b形式的超定线性方程组，可通过计算其法方程组A^TAV′＝A^Tb解出V′。我们采用了TAUCS方法求得A^TA的Cholesky分解，通过回代计算V′的最小二乘解。

本发明方法在应用不同约束条件时产生的变形效果如附图2所示。(a)是原网格。(b)是仅采用仿射约束产生的变形效果。增加角度约束后，相同的控制顶点位置产生了光滑的弯曲效果(c)。(d)是弯曲180度的效果。(e)是仅采用仿射约束产生的错切效果。增加角度约束后，可以产生平移敏感效果(f)和(g)。(h)是仅采用仿射约束生成的单向拉伸效果。(i)是采用了全部约束和2个控制顶点产生的(各向同性)放大效果。圆点是控制顶点。

本发明方法中控制顶点及权重对变形效果的影响如附图3所示。(a)是原图。(b)中用两个控制顶点将左侧缩小，并将右侧的一个控制顶点往右移，放大了右侧。(c)的α为10，β为0.1，获得接近于横向拉伸的仿射变形效果；(d)的α和β都为1，中部由于相互影响，出现放大。(e)将物体弯曲，中部出现一定程度的收缩。在中间增加一个控制点，将(e)拉长模拟保面积的效果(f)。