投审稿平台
投稿指南
下载专区
地  址:北京市海淀区中关村科学院
南路6号中国科学院计算所342号 [地图]
《计算机辅助设计与图形学学报》编辑部
邮政编码:100190
电  话:010-62562491
          010-62600342
订阅信息
ISSN      1003-9775
CN        11-2925/TP
邮发代号:82-456
单    价:60.00元
全年订价:720.00元
学术资讯

清华大学在流形曲面测地度量下的几何结构分析研究中取得系列进展

发布时间: 2015-06-10 作者: 刘永进(清华大学)

  

清华大学图形学与几何计算课题组在2011-2014年期间,在国际上首先分析得到了二维流形网格曲面上测地Voronoi图的几何结构(IEEE Trans. Pattern Analysis & Machine Intelligence 2011, Computer-Aided Design 2013, Pacific Graphics 2014,并证明了该测地Voronoi图的组合复杂度(Information Processing Letter 2013)。在此基础上,2015年清华大学与新加坡南洋理工大学、香港中文大学、香港科技大学、中国科技大学等单位合作,在流形曲面测地度量下的几何结构分析研究中取得进一步的系列进展,研究工作在IEEE Trans. Pattern Analysis & Machine Intelligence上录取论文1篇,在IEEE Trans. Visualization and Computer Graphics上录取论文2篇。

系列研究工作获得国家自然科学基金优秀青年基金项目、国家973项目和清华信息科学与技术国家实验室(筹)的资助。

 

1)进展一:流形曲面上测地中轴的几何结构分析

形状的中轴(skeleton/medial axis)是一类基本的几何工具,在模式识别中具有广泛的应用。中轴的概念提出近40年以来,大部分的研究都集中在欧式空间。法国数学家、数学形态学创始人Georges Matheron1988年提出用开集来表征形状,并用hit-or-miss拓扑研究了欧式空间中的中轴特性,证明了欧式空间的中轴映射是下半连续函数这一重要定理。

2000Science期刊第290卷上的三篇论文,提出了视感知中的流形表达是一种重要的几何结构的观点,在全世界掀起了流形学习的研究热潮。然而直到目前,关于流形结构中的中轴表达研究成果很少,严重缺乏理论基础。研究中的难点主要在于流形上的测地度量随着流形的曲率张量不同而在所嵌入的欧式空间中具有不同的弯曲性质。

刘永进博士深入分析了低维流形空间中基于测地度量的中轴性质,得到以下系统性研究成果:

1)证明低维流形结构的中轴映射是hit-or-miss拓扑空间中的下半连续函数。

2)作为流形的特例,前人证明了欧式空间中连通开集的中轴也是连通的。但是,本文研究发现,在一般流形上,连通开集的中轴可以不连通。

3)在欧式空间中,前人证明了medial axis集合是skeleton集合的一个稠密子集。但是,本文研究发现,在一般流形上,skeleton集合中可以完全没有medial axis集合。

4)提出并建立用低维流形结构中离散点集的测地Voronoi图来无限逼近一个连通开集的中轴。

研究工作被IEEE Trans. Pattern Analysis & Machine Intelligence录取,论文的唯一作者为清华大学的刘永进博士。

 

  

2)进展二:流形网络曲面上的精确离散测地度量计算方法

由于数字化采样的普及,网格曲面在计算机图形学和计算机视觉中得到了广泛应用。测地度量是曲面上的内蕴度量形式,在几何计算中具有重要作用。目前在网格曲面上计算测地度量主要有两大类方法。第一类方法源自R. KimmelJA Sethian1998年提出的水平集(level set)数值解法。第二类方法源自Joseph S. B. Mitchell , David MountChristos H. Papadimitriou等人在1987年提出的计算几何解法。第一类方法计算速度快,但对网格的质量敏感。第二类方法不受网格质量的影响,在不考虑浮点型误差的情况下可以得到精确解,但这类方法计算非常耗时。

课题组提出了一种快速波前传播框架(Fast Wavefront Propagation FWP),在保持计算几何方法的高精度条件下提高了算法的时间效率,填补了两大类方法之间的鸿沟。课题组首先分析了传统的计算几何方法时间效率较低的原因,阐明了限制算法效率的相互矛盾的两个条件,即wavefront的质量和更新wavefront的成本,并据此提出了一种bucket数据结构用以平衡这两个限制条件。在理论上证明,应用了FWPMMPCH算法(分别称为FWP-MMPFWP-CH)能够保持原有的时间和空间复杂度。在实际应用中,FWP这一框架可以以较低的成本维护较高质量的wavefront质量。实验结果表明FWP-MMPFWP-CH两个算法在真实三维模型上的运行时间能够比传统的MMPCH算法快一个数量级。与已有的两大类计算测地线方法进行的详细比较中验证了FWP算法在不同方面具有较大的优势。

研究工作被期刊IEEE Transactions on Visualization and Computer Graphics录用。

该项工作由清华大学、中国科技大学和新加坡南洋理工大学合作完成,论文共同通讯作者为清华大学刘永进博士和南洋理工大学贺英教授,第一作者为清华大学博士生许春旭(指导教师刘永进),中国科技大学本科生王杨抟风和刘利刚教授为本文的共同作者。

 

  

3)进展三:面向服装设计的流形曲面上演化计算

演化计算是借鉴模拟自然界中的生物进化机理,延伸出的一类基于群体导向的随机搜索方法。近年来随着互联网上数据传播速度的飞速发展,大数据驱动的三维模型造型与设计方法得到了广泛关注。然而,已有的基于样例或数据驱动的模型演化方法,大多是在欧式空间中基于欧式度量的演化计算。

在本项工作中,我们将诸如服装这类柔性物体定义为流形曲面上基于测地度量的距离场模式,提出了一种流形曲面上的款式演化计算方法。该方法基于曲面上款式的曲线族表示和对偶的测地距离场,通过定义流形曲面上的杂交和突变等遗传操作,在一个客观衡量设计师的款式审美目标函数的驱动下,采用演化计算可以从已有大规模服装款式数据库中自动演化出符合人类审美标准的新款紧身服装。

研究工作被期刊IEEE Transactions on Visualization and Computer Graphics录用。

该项工作由香港中文大学、清华大学和香港科技大学共同完成,论文共同通讯作者为香港中文大学王昌凌教授和清华大学刘永进博士,第一作者为香港中文大学郭子豪博士(论文工作期间在清华大学访问),第二作者为清华大学硕士生张艳秋(指导教师刘永进)。

 

 

  

 

Copyright © 2004《计算机辅助设计与图形学学报》版权所有
电话:010-62600342 传真:010-62562491
E_mail:jcad@ict.ac.cn