论文部分内容阅读
摘 要：morphing，一般翻译为图形渐变，是指将一给定的初始图形在视觉上光滑、连续、自然的变化到目标图形。本文讨论一种基于“类人感知”的二维多边形渐变中顶点对应问题的解决方法，并用java语言对其进行实现测试。
关键词：morphing；多边形；java
中图分类号：TP391.41
图形渐变（morphing），顾名思义就是采用某种方法使初始物体在视觉上连续、光滑变化到目标物体。随着计算机技术的迅速发展，图形渐变技术广泛应用于计算机图形学、工业产品设计、计算机动画、虚拟现实、影视特技制作等领域。二维物体渐变是物体渐变的重要组成部分，不仅在关键帧动画、模式识别，而且在曲面重建和三维造型中也有重要意义。
二维物体渐变的研究包含两个问题：顶点对应问题和顶点插值路径问题。本文所采用的算法是由刘立刚教授等在2004年研发出来的算法，在该方法中，对于在源图形和目标图形中寻找顶点对应关系的这个过程主要着眼于人类对多边形形状改变的感知方法，并采用java语言进行具体实现。
1 算法分析
本文所讨论的方法可粗略的分为以下5个步骤：（1）把初始图形S和目标图形T定义为二维多边形；（2）对初始图形S和目标图形T进行特征点检测；（3）解决顶点对应问题；（4）解决顶点路径问题；（5）产生渐变序列并显示出来。
1.1 多边形的定义
在本文中，二维形状被定义为一个在二维水平面上的曲线，该曲线不可自交，可以是闭合的，也可以是非闭合的。多边形是图形的一个特例，多边形中用来连接顶点之间的函数被限制为直线，顶点的集合称为顶点集，顶点用Pi，表示，连接两个顶点之间的线段叫做边。
1.2 特征点的定义
在本文中，特征点描述的是在二维平面上的一个点。在特征点匹配的过程中，除了x和y坐标以外，还有一些其他的重要属性。每个特征点都是某一个图形的成员，每个图形都能够用隶属于它的特征点依次的表示出来，当然会损失一些图像信息。与平均分布采样点不同，特征点在图形上的分布并不是均匀的。在人类观察者对于的图形的感知中，具有高曲度的尖角点更容易引起注意，因此本文中的“类人感知”，就是获取高曲度的顶点作为特征点。
对于普通的二维图形，特征点需要通过采样，通过特征点检测函数进行判断，来确保特征点采选的准确性。由于本文讨论的对象是二维多边形，因此，可以默认所有的特征点均出自顶点集，无须进行采样只需判断。
1.3 特征点的对应
当初始图形和目标图形的特征点都已经确定，就要对这些特征点进行一一对应之后再morphing，为此我们需要一个对特征点进行判断的准则。为此我们定义如下一些术语和标准：
1.3.1 领域（Region of Support）
1.3.2 特征变分
特征点Pi的特征变分定义为：
，其中，λN为垂直特征值，λT为切线特征值，如果Pi是凸特征点，则ξ=1，如果Pi是凹特征点，则ξ=-1。特征变分产生的是ROSh（Pi）中的点相对于 的位置信息。如果Pi附近区域的图形相对扁平，临近点都落在Pi的切线方向。σ（Pi）的值在闭区间[-1，1]中，如果σ（Pi）的值逼近1，说明点Pi是在一个尖角的端点上；如果σ（Pi）逼近0，则点Pi周围的图形比较平缓。
1.3.3 特征侧面变分
特征侧面变分定义为：
其中ROL（Pi）和ROR（Pi）分别是点 的左领域和右领域。对于每一个ROL（Pi）和ROR（Pi），都需要计算其协方差，对于ROL（Pi）产生特征值λNL和λTL，ROR（Pi）产生特征值λNR和λTR。使用这几个特征值来定义σ（ROL（Pi））和σ（ROR（Pi）），定义 ， 。特征方面变分τ（Pi）用于获取点Pi的左邻域以及右邻域的外观信息。同特征变分相似，σ（ROL（Pi））和σ（ROR（Pi））的定义域是[0，1]（这里不用参数ξ以防出现负值）。如果 的值靠近0则说明区域图像比较平缓，如果τ（Pi）的值较高就表示ROL或者ROR弯曲程度较大。
1.3.4 特征规模
特征规模定义为：
其中ρL（Pi）和ρR（Pi）指的是ROL（Pi）和ROR（Pi）相对于图形周长的长度。ρ（Pi）实际上是一个指针，指示的是它在整个图形中的重要性：如果ρ（Pi）产生的值非常小，则说明Pi的邻域在整个图形中只是一个比较小的部分，甚至不能给人类观察者以明显的印象（如果τ（Pi）和ρ（Pi）都很高的话，Pi的邻域可能也不明显）。如果ρ（Pi）获得了一个很高的值，表明Pi的邻域是整个图形的重要部分，将会给观察者一个很强的印象。
根据以上的定义和参数，我们可以用S={Si|i=0，1，…m}来描述初始图形，用T={Tj|j=0，1，…n}来描述目标图形。当S0=Sm，T0=Tn的时候分别表示源图形和目标图形闭合。每一对特征点Si和Tj的相似度值定义为
如果初始图形和目标图形的特征点数不相等，就不能够做到初始图形和目标图形的特征点一一对应，此时就要舍弃掉不适合产生morphing序列的特征点。而且在寻找良好的morphing序列的过程中，也需要删除一些不适合进行对应的特征点。为了判定删除掉特征点对整个morphing序列的影响，我们引入一个价值函数。
通过计算如果Pi的抛弃代价非常小的话，那么说明Pi在整个图形中的地位不是很重要。
相似度价值函数不仅可以用来衡量两个特征点Si和Tj之间的相似度，而且可以为对应初始图形S和目标图形T整体赋值。在这里对应关系的意思就是从特征点S到特征点T的映射。如果我们把一个映射J看成：{Si}→{Tj}，就可以为S和T之间的映射建立一个相似度价值函数： ，
因为初始图形S中有m个不同的特征点，根据相似度函数的特性，我们假设映射J是对应问题的最优解决方案，只要使SimCosts（S，T，J）的结果最小即可。
2 程序设计
本程序采用java语言来实现。
2.1 类层次结构
整个程序根据算法的需要主要封装成7个包及40余个类，这7个包的名称分别为shapes，emath，featureDetection，tools，morphing，control和application。
其中，shape包只是用来处理多边形；emath包中包含的是计算算法中比较复杂的数学属性的工具，包括有协方差，特征向量，特征值和顶点内角的二分线等函数；featureDetection用来实现多边形中的特征点检测；tools包中的类都是其他类用作工具；controls包中大多数的类都是用来实现java.awt.event包中定义的ActionListener接口的，它们主要用来处理用户和应用程序之间的交互，同时也可以对其他的类进行扩展；morph包是用来处理创建渐变序列的；Application则是用来构建程序GUI的。
2.2 检测特征点
前文中，我们讨论了有关于特征点的检测的问题，本文中讨论的是二维图形的特例多边形，因此可以将算法进行简化。在多边形中，只有顶点可以作为特征点的候选，因此可以省略采样这个步骤。同样的，对于各种不同的三角形可以忽略本过程，因为三角形的构造直接就满足特征点对应的需求。
2.3 顶点对应问题
本文采用动态规划的方法来解决顶点对应问题的最优化。想要得到最优的顶点对应组合，合理的做法是事先把抛弃代价和相似度值计算出来并存储，然后用动态规划的方法进行多次调用，规划出最合理的顶点对应路径。下面代码中的函数calculateAllDeltaCosts（Polygon，Polygon，int）可以完成这项计算，参数skips制定了寻找动态规划图中的某一个结点的最佳前驱时，最多可以跳过的特征点的数目。整型变量dim1和dim2分别表示源图形和目标图形的特征点数目。接下来把所有的数据都保存在一个四维数组delta_field中，嵌套的for结构就是把各个变量的值一次的放到对应的数据域中去。源图形中的特征点 和目标图形中的特征点 的对应关系存储在deltaCosts[i][j][][]中。
3 结论和展望
3.1 测试结果
3.1.1 特征点检测对渐变序列的影响
3.1.2 跳点数（skip）对渐变序列的影响
在动态规划图中允许最大的跳点数目对渐变序列有着巨大的影响，图3对此进行了展示。所有的渐变序列除了最大跳点数以外的所有参数均采用相同的，图a）中的跳点数设为0，这就导致了多边形各部分的对应顶点移动距离都很大，同时由于使用的是直线路径，非常容易产生自交。图b）跳步数选择为1，成功的避免了产生自交，看上去比图a）效果要好很多，但在那个的上部依旧还是存在失真。图c）中，这些没必要的移动就完全的消失了，图c）的最大跳步数设为2，渐变序列的结果要比图a）和b）良好。
3.2 结论：特征点检测这个步骤不仅能优化算法，同时也能得到较好的渐变序列。适当的设置最大的跳点数目可以避免渐变序列图形产生自交，从而产生更优的渐变序列。
参考文献：
[1]Liu，Ligang，Wang，Guopu，Zhang，Bo，Guo，Baining，Shum，Heung-Yeung.Perceptually Based Approach for Planar Shape Mor-phing，2004：111-120.
[2]范自柱.一种图像morphing效果的客观度量方法[J].计算机工程与应用，2006（31）：37-39.
[3]赖志豪，康宝生.二维物体变形技术现状与发展[J].计算机技术与发展，2007（10）：120-121.
作者简介：袁媛（1981-），女，辽宁抚顺人，讲师，硕士，研究方向：计算机。
作者单位：抚顺职业技术学院，辽宁抚顺 113122
关键词：morphing；多边形；java
中图分类号：TP391.41
图形渐变（morphing），顾名思义就是采用某种方法使初始物体在视觉上连续、光滑变化到目标物体。随着计算机技术的迅速发展，图形渐变技术广泛应用于计算机图形学、工业产品设计、计算机动画、虚拟现实、影视特技制作等领域。二维物体渐变是物体渐变的重要组成部分，不仅在关键帧动画、模式识别，而且在曲面重建和三维造型中也有重要意义。
二维物体渐变的研究包含两个问题：顶点对应问题和顶点插值路径问题。本文所采用的算法是由刘立刚教授等在2004年研发出来的算法，在该方法中，对于在源图形和目标图形中寻找顶点对应关系的这个过程主要着眼于人类对多边形形状改变的感知方法，并采用java语言进行具体实现。
1 算法分析
本文所讨论的方法可粗略的分为以下5个步骤：（1）把初始图形S和目标图形T定义为二维多边形；（2）对初始图形S和目标图形T进行特征点检测；（3）解决顶点对应问题；（4）解决顶点路径问题；（5）产生渐变序列并显示出来。
1.1 多边形的定义
在本文中，二维形状被定义为一个在二维水平面上的曲线，该曲线不可自交，可以是闭合的，也可以是非闭合的。多边形是图形的一个特例，多边形中用来连接顶点之间的函数被限制为直线，顶点的集合称为顶点集，顶点用Pi，表示，连接两个顶点之间的线段叫做边。
1.2 特征点的定义
在本文中，特征点描述的是在二维平面上的一个点。在特征点匹配的过程中，除了x和y坐标以外，还有一些其他的重要属性。每个特征点都是某一个图形的成员，每个图形都能够用隶属于它的特征点依次的表示出来，当然会损失一些图像信息。与平均分布采样点不同，特征点在图形上的分布并不是均匀的。在人类观察者对于的图形的感知中，具有高曲度的尖角点更容易引起注意，因此本文中的“类人感知”，就是获取高曲度的顶点作为特征点。
对于普通的二维图形，特征点需要通过采样，通过特征点检测函数进行判断，来确保特征点采选的准确性。由于本文讨论的对象是二维多边形，因此，可以默认所有的特征点均出自顶点集，无须进行采样只需判断。
1.3 特征点的对应
当初始图形和目标图形的特征点都已经确定，就要对这些特征点进行一一对应之后再morphing，为此我们需要一个对特征点进行判断的准则。为此我们定义如下一些术语和标准：
1.3.1 领域（Region of Support）
1.3.2 特征变分
特征点Pi的特征变分定义为：
，其中，λN为垂直特征值，λT为切线特征值，如果Pi是凸特征点，则ξ=1，如果Pi是凹特征点，则ξ=-1。特征变分产生的是ROSh（Pi）中的点相对于 的位置信息。如果Pi附近区域的图形相对扁平，临近点都落在Pi的切线方向。σ（Pi）的值在闭区间[-1，1]中，如果σ（Pi）的值逼近1，说明点Pi是在一个尖角的端点上；如果σ（Pi）逼近0，则点Pi周围的图形比较平缓。
1.3.3 特征侧面变分
特征侧面变分定义为：
其中ROL（Pi）和ROR（Pi）分别是点 的左领域和右领域。对于每一个ROL（Pi）和ROR（Pi），都需要计算其协方差，对于ROL（Pi）产生特征值λNL和λTL，ROR（Pi）产生特征值λNR和λTR。使用这几个特征值来定义σ（ROL（Pi））和σ（ROR（Pi）），定义 ， 。特征方面变分τ（Pi）用于获取点Pi的左邻域以及右邻域的外观信息。同特征变分相似，σ（ROL（Pi））和σ（ROR（Pi））的定义域是[0，1]（这里不用参数ξ以防出现负值）。如果 的值靠近0则说明区域图像比较平缓，如果τ（Pi）的值较高就表示ROL或者ROR弯曲程度较大。
1.3.4 特征规模
特征规模定义为：
其中ρL（Pi）和ρR（Pi）指的是ROL（Pi）和ROR（Pi）相对于图形周长的长度。ρ（Pi）实际上是一个指针，指示的是它在整个图形中的重要性：如果ρ（Pi）产生的值非常小，则说明Pi的邻域在整个图形中只是一个比较小的部分，甚至不能给人类观察者以明显的印象（如果τ（Pi）和ρ（Pi）都很高的话，Pi的邻域可能也不明显）。如果ρ（Pi）获得了一个很高的值，表明Pi的邻域是整个图形的重要部分，将会给观察者一个很强的印象。
根据以上的定义和参数，我们可以用S={Si|i=0，1，…m}来描述初始图形，用T={Tj|j=0，1，…n}来描述目标图形。当S0=Sm，T0=Tn的时候分别表示源图形和目标图形闭合。每一对特征点Si和Tj的相似度值定义为
如果初始图形和目标图形的特征点数不相等，就不能够做到初始图形和目标图形的特征点一一对应，此时就要舍弃掉不适合产生morphing序列的特征点。而且在寻找良好的morphing序列的过程中，也需要删除一些不适合进行对应的特征点。为了判定删除掉特征点对整个morphing序列的影响，我们引入一个价值函数。
通过计算如果Pi的抛弃代价非常小的话，那么说明Pi在整个图形中的地位不是很重要。
相似度价值函数不仅可以用来衡量两个特征点Si和Tj之间的相似度，而且可以为对应初始图形S和目标图形T整体赋值。在这里对应关系的意思就是从特征点S到特征点T的映射。如果我们把一个映射J看成：{Si}→{Tj}，就可以为S和T之间的映射建立一个相似度价值函数： ，
因为初始图形S中有m个不同的特征点，根据相似度函数的特性，我们假设映射J是对应问题的最优解决方案，只要使SimCosts（S，T，J）的结果最小即可。
2 程序设计
本程序采用java语言来实现。
2.1 类层次结构
整个程序根据算法的需要主要封装成7个包及40余个类，这7个包的名称分别为shapes，emath，featureDetection，tools，morphing，control和application。
其中，shape包只是用来处理多边形；emath包中包含的是计算算法中比较复杂的数学属性的工具，包括有协方差，特征向量，特征值和顶点内角的二分线等函数；featureDetection用来实现多边形中的特征点检测；tools包中的类都是其他类用作工具；controls包中大多数的类都是用来实现java.awt.event包中定义的ActionListener接口的，它们主要用来处理用户和应用程序之间的交互，同时也可以对其他的类进行扩展；morph包是用来处理创建渐变序列的；Application则是用来构建程序GUI的。
2.2 检测特征点
前文中，我们讨论了有关于特征点的检测的问题，本文中讨论的是二维图形的特例多边形，因此可以将算法进行简化。在多边形中，只有顶点可以作为特征点的候选，因此可以省略采样这个步骤。同样的，对于各种不同的三角形可以忽略本过程，因为三角形的构造直接就满足特征点对应的需求。
2.3 顶点对应问题
本文采用动态规划的方法来解决顶点对应问题的最优化。想要得到最优的顶点对应组合，合理的做法是事先把抛弃代价和相似度值计算出来并存储，然后用动态规划的方法进行多次调用，规划出最合理的顶点对应路径。下面代码中的函数calculateAllDeltaCosts（Polygon，Polygon，int）可以完成这项计算，参数skips制定了寻找动态规划图中的某一个结点的最佳前驱时，最多可以跳过的特征点的数目。整型变量dim1和dim2分别表示源图形和目标图形的特征点数目。接下来把所有的数据都保存在一个四维数组delta_field中，嵌套的for结构就是把各个变量的值一次的放到对应的数据域中去。源图形中的特征点 和目标图形中的特征点 的对应关系存储在deltaCosts[i][j][][]中。
3 结论和展望
3.1 测试结果
3.1.1 特征点检测对渐变序列的影响
3.1.2 跳点数（skip）对渐变序列的影响
在动态规划图中允许最大的跳点数目对渐变序列有着巨大的影响，图3对此进行了展示。所有的渐变序列除了最大跳点数以外的所有参数均采用相同的，图a）中的跳点数设为0，这就导致了多边形各部分的对应顶点移动距离都很大，同时由于使用的是直线路径，非常容易产生自交。图b）跳步数选择为1，成功的避免了产生自交，看上去比图a）效果要好很多，但在那个的上部依旧还是存在失真。图c）中，这些没必要的移动就完全的消失了，图c）的最大跳步数设为2，渐变序列的结果要比图a）和b）良好。
3.2 结论：特征点检测这个步骤不仅能优化算法，同时也能得到较好的渐变序列。适当的设置最大的跳点数目可以避免渐变序列图形产生自交，从而产生更优的渐变序列。
参考文献：
[1]Liu，Ligang，Wang，Guopu，Zhang，Bo，Guo，Baining，Shum，Heung-Yeung.Perceptually Based Approach for Planar Shape Mor-phing，2004：111-120.
[2]范自柱.一种图像morphing效果的客观度量方法[J].计算机工程与应用，2006（31）：37-39.
[3]赖志豪，康宝生.二维物体变形技术现状与发展[J].计算机技术与发展，2007（10）：120-121.
作者简介：袁媛（1981-），女，辽宁抚顺人，讲师，硕士，研究方向：计算机。
作者单位：抚顺职业技术学院，辽宁抚顺 113122