拓扑变换PPT

拓扑变换及其应用TopologicalTransformationandItsApplication一、五个有趣的拓扑变换问题•V.V.Prasolov的IntuitiveTopology一书中，第一章有五个非常经典的“拓扑变换”谜题。游戏规则：我们假设所有物体都是用橡胶做成的，可以随意地拉伸、挤压、弯曲，但不允许切断、粘连等任何改变图形本质结构的操作。•1.能否把左图连续地变形为右图？•这意味着，假如人类的身体可以像橡胶人一样任意变形，那么用两手的拇指和食指做成两个套着的圆环之后，我们可以不放开手指，把圆环给解开来。《AlgorithmicandComputerMethodsforThree-Manifolds》一书里画了一张非常漂亮的示意图：•答案是可以的，如下图所示：一、五个有趣的拓扑变换问题更加有趣的是，如果仅仅是手腕上多了一块手表，上述方案就不能得逞了。如右图所示。一、五个有趣的拓扑变换问题•2.能否把左图连续地变形为右图？•3.左图所示的立体图形表面画有一个圆。能否通过连续变换，把这个圆变到右图所示的位置？•答案是可以的，如下图所示：答案是可以的，如下图所示：一、五个有趣的拓扑变换问题•4.在一个轮胎的表面上打一个洞。能否通过连续变换，把这个轮胎的内表面翻到外面来？答案是可以的。首先，作出如下图所示的连续变换。可以看到，一个表面有洞的轮胎本质上等于两个粘在一起的纸圈！不过，注意纸圈1和纸圈2的地位不太一样：一个是白色的面（即最初轮胎的内表面）冲外，一个是阴影面（即最初轮胎的外表面）冲外。现在，把纸圈2当成原来的纸圈1，把纸圈1当成原来的纸圈2，倒着把它们变回轮胎形，轮胎的内外表面也就颠倒过来了。一、五个有趣的拓扑变换问题有趣的是，把轮胎的内表面翻出来之后，轮胎上的“经线”和“纬线”也将会颠倒过来：Wikimedia上有一个巨帅无比的动画，直接展示出了把一个圆环面的内表面翻到外面来的过程。此动画看着非常上瘾，小心一看就是10分钟！一、五个有趣的拓扑变换问题•5.能否把左图连续地变形为右图？答案是可以的。首先，作出如下图所示的连续变换，于是就变成了问题1中的图(a)，再利用问题1的办法，即可变出我们想要的形状来。二、基本概念•1.拓扑的含义•“拓扑（Topology）”一词来自希腊文，它的原意是“形状的研究”。拓扑学是几何学的一个分支，它研究在拓扑变换下能够保持不变的几何属性——拓扑属性。但是这种几何学又和通常的平面几何、立体几何不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。二、基本概念•在拓扑学里没有不能弯曲的元素，每一个图形的大小、形状都可以改变。例如，前面讲的欧拉在解决哥尼斯堡七桥问题的时候，他画的图形就不考虑它的大小、形状，仅考虑点和线的个数。BCADABCD拓扑等价二、基本概念•2.拓扑性质与拓扑等价•在拓扑学里不讨论两个图形全等的概念，但是讨论拓扑等价的概念。比如，尽管圆和方形、三角形的形状、大小不同，在拓扑变换下，它们都是等价图形。换句话讲，就是从拓扑学的角度看，它们是完全一样的。•在一个球面上任选一些点用不相交的线把它们连接起来，这样球面就被这些线分成许多块。在拓扑变换下，点、线、块的数目仍和原来的数目一样，这就是拓扑等价。一般地说，对于任意形状的闭曲面，只要不把曲面撕裂或割破，他的变换就是拓扑变换，就存在拓扑等价。直线上的点和线的结合关系、顺序关系，在拓扑变换下不变，这是拓扑性质。在拓扑学中曲线和曲面的闭合性质也是拓扑性质。二、基本概念•3.拓扑映射与拓扑变换•作为点集的几何图形，如果在变换时，正逆两方面两图形都是单值而又连续对应的，则这种对应称为拓扑映射。相应的几何变换称为拓扑变换。•举例：设想一块高质量的橡皮，它的表面是欧几里的平面，这块橡皮可以任意被拉伸、压缩，但是不能够被扭转或折叠。在橡皮的表面上有由结点、弧、环、面组成的可能任意图形。我们对橡皮进行拉伸、压缩，在橡皮进行这些变换的过程中，图形的一些属性消失，一些属性将继续保持存在。设想象皮表面有一个多边形，里面有一个点。当拉伸、压缩橡皮时，点依旧在多边形中，点和多边形的位置关系不会发生变化，但是多边形的面积会发生变化。所以：“点的内置”是拓扑属性，而面积不是拓扑属性，拉伸和压缩就是拓扑变换。•三、拓扑变换的应用•1.密码学•由李虹提出，发明专利：基于生物特征点拓扑结构的非对称加解密方法。•①指纹的特征包括总体特征和细节特征。指纹特征点包括端点、叉点等。•②数字指纹学运用拓扑数学理论,把传统指纹学的特征点转化为数字指纹特征点的拓扑构图,从而进行指纹模式识别与指纹比对。某类指纹特征点用不相交的线把它们连接起来,就构成了指纹的拓扑结构网格。对指纹拓扑结构网络进行平移、旋转的拓扑变换满足拓扑等价。•三、拓扑变换的应用•1.密码学——基于指纹特征点拓扑结构变换的非对称加解密方法•③方便算法研究起见,以指纹的特征端点、叉点做拓扑结构变换。指纹特征点和相应的拓扑结构图如下图所示:其中,分别连接图(a)和图(b)的小圈点构成指纹特征点拓扑结构，如图(c)和图(d)所示。•三、拓扑变换的应用•1.密码学——基于指纹特征点拓扑结构变换的非对称加解密方法•指纹特征点拓扑结构变换加解密原理•利用指纹特征端点的拓扑结构作为拓扑变换的原始结构,而同时利用另一类的指纹特征点(比如叉点)构成的向量元素数目为加密密钥来实现非对称加解密就是指纹特征点拓扑结构非对称变换加解密。这样实现的加解密是对指纹特征点拓扑结构做线性变换,具有方法简单,速度快,效率高的优势,兼具生物识别技术,抗抵赖性强,适合电子商务、政务等网络信息安全加解密。•三、拓扑变换的应用•1.密码学——基于指纹特征点拓扑结构变换的非对称加解密方法•指纹特征点拓扑结构变换加解密原理•借助指纹传感器等设备,针对某一幅具体的指纹提取一组指纹特征点拓扑结构的矩阵向量,如表1所示。•表1指纹特征点的拓扑结构数据指纹特征点特征点拓扑结构数据端点(39,39)(195,67)(95,100)(127,117)(108,126)(153,132)(57,208)(158,219)(70,224)(184,225)(65,235)(57,246)(115,253)(194,254)(44,272)(180,287)(65,292)(190,314)叉点(58,43)(178,80)(113,113)(171,129)(151,162)(200,166)(162,272)三、拓扑变换的应用•以指纹端点的拓扑结构数据作为拓扑结构变换的对象,用矩阵向量G[1]表示,即为指纹特征点拓扑变换的初始矩阵向量。则对指纹特征点拓扑结构的变换可转化为对矩阵向量的一系列相关的变换。约定矩阵向量的一次完整的运算(即指纹特征点拓扑结构的一次变换)为一轮次运算。•G[1]包含两个一维矩阵向量X和Y;X由G[1]的横坐标构成,Y由相对应的G[1]的纵坐标构成;则指纹特征点的拓扑结构变换转化为对两个一维矩阵向量X和Y的相关变换。•对矩阵进行平移变换和旋转变换，以增加拓扑结构变化的复杂度,增强加密效果。三、拓扑变换的应用•2.有限元网格划分•移除边和移除面是提高四面体网格划分质量的两个有效步骤。•在爬山方法（hill-climbingmethod,presentedbyJonathanRichardShewchuk，UniversityofCaliforniaatBerkeley）中，利用局部拓扑变换可以确定移除边和移除面的最优算法，从而优化网格质量。之所以是局部拓扑变换，是因为只有少量的单元（通常少于20个）被移除或替换。三、拓扑变换的应用•2.有限元网格划分•爬山法定义一个目标函数，该函数能将每个可能的网格映射为数值（或数值序列），这些数值或数值序列用来描述网格的质量。目标函数通常是平均单元质量或最差单元质量，如果稍微复杂点就可以是各个单元的质量的序列，该序列按照从差到优的顺序排列。如果局部单元通过拓扑变换后，其质量得到提高，那么该拓扑变换被采用，否则不被采用。当没有变换可是实现进一步的改进（网格质量达到局部最优），或者进一步改进消耗太多时间时，爬山过程就停止。三、拓扑变换的应用•2.有限元网格划分•移除边是指从四面体网格中移除一条边的变换，包括3-2和4-4的变换以及其他能够移除四面体的变换。所有包含这条边的面和四面体都将被移除，并且由其他的面和四面体来代替。图2演示了一次移除边的变换，该变换中，由10个新的四面体替换了原有的7个四面体。三、拓扑变换的应用•2.有限元网格划分•我们的目标是选择一种三角剖分，使网格划分的质量最优。这一选择过程是一个循环过程，通过尝试每一个可能的k值，找到最优解。