基于积分不变量和特征敏感度量的的几何处理 
最新成果介绍
基于积分不变量和特征敏感度量的的几何处理
基于积分不变量和特征敏感度量，提出了一个新的特征敏感几何处理的研究框架，研究了鲁棒的几何特征分类与编辑、基于特征敏感参数化的表面拟合、特征敏感的网格模型分割、鲁棒的多尺度主曲率估计等，取得了国际领先的研究成果。其核心思想是将三维模型映射到高维空间，利用高维空间的特征敏感度量进行几何处理。 提出了一种新的鲁棒地处理特征的整体形状的方法，在三维模型上得到了尖边、脊、谷和刺等特征区域。我们利用网格重剖算法获得基于特征敏感度量的各向同性网格，在此基础上，可通过局部邻域内的积分不变量识别多尺度的特征区域。既而，使用数学形态学的方法以及平滑操作实现特征区域的提取并进一步分类为一些基本的类型，例如脊、谷和刺等。获得的特征区域的表示还可以应用于针对特定特征的曲面编辑操作。图1-1为特征分类和编辑的示例。
 |  | |
 |
||
 |  |
基于特征敏感参数化的表面拟合方面，对于采样数据的B-样条曲面最小二乘拟合的方法大多需要选择合适的节点向量并对数据点集进行适当的参数化。我们提出一种使用均匀节点向量和特征敏感的参数化方法进行B-样条拟合的方法。采用这种参数化方法，可以为高度弯曲的特征区域分配更多的参数空间，从而自动地在这些需要的区域添加更多的控制顶点。
| | |
 |
||
| |
在特征敏感几何处理框架下，研究网格模型分割，给出了基于聚类的、自顶向下的层次化聚类方法。通过改进特征敏感的各向同性网格重剖算法，可以将大模型进行多层次分割的网格多分辨率表示；由于使用积分不变量估计局部特征，方法非常鲁棒,并允许对具有不同几何特征或几何纹理的区域进行分割。
| | |
 |
||
| |
鲁棒的多尺度主曲率估计方面，提出了一种基于定义在局部邻域上的积分不变量来得到曲率信息的方法。对PCA的结果在局部邻域半径r趋于0的情况下进行了渐进分析，得到了其与主曲率的关系,并将该方法应用在网格特征提取和三角网格四边形化等方面。
| | |
 |
||
| |
上述成果分别发表于国际杂志IEEE Transactions on Visualization and Computer Graphics, Computer-Aided Design, ACM Solid and Physical Modeling和Eurographics Workshop on Geometry Processing等著名杂志和会议上。
上述成果可以访问网站 http://cg.cs.tsinghua.edu.cn/ 获得。
三维模型的拓扑修复
随着三维扫描技术的高速发展，人们已经能越来越多的获取大规模、高质量的三维模型。但是，通过扫描方式获取的三维模型往往具有信息不完整、存在各类错误等特征。其中，扫描数据的拓扑错误，是具有代表性的一类。这些拓扑错误常常以“环”为体现方式，会对扫描数据的利用和后处理产生不利的影响。
我们通过使用体数据的骨架来描述和测量“环”，实现了一种鲁棒快速的修复实体模型拓扑错误的方法。与前人的研究成果相比本文有以下两个主要优点：
1. 鲁棒性：移除环的过程能够保证不会引入错误的几何或者额外的环（错误的拓扑）
2. 高效性：通过使用一个多分辨率的方格结构表示体数据，我们的方法可以在高分辨率下高效的处理超大规模模型
图2-1显示了我们的算法对复杂模型的拓扑修复。
| | |
 |
||
| |
在实践中，我们发现自动化的拓扑修复方法具有种种不足，在很多时候，计算机无法像人一样的聪明的识别出模型固有的拓扑结构和扫描数据包含的拓扑噪声；因此，我们扩展了自动化拓扑修复方法。通过引入一个模型骨架绘制框架，我们让用户绘制出模型的骨架来约束最终模型的拓扑。通过融合拓扑修复算法和用户输入框架，我们设计了一个自动化的算法，能够将模型转化成用户需求的拓扑结构。图2-2显示了用户输入诱导的拓扑修复算法。
| | |
 |
||
| |
上述成果分别发表于国际杂志IEEE Transactions on Visualization and Computer Graphics和国际顶级会议ACM SIGGRAPH。可以访问网站 http://cg.cs.tsinghua.edu.cn/ 获得。
视频处理
我们提出了一种新的视频完全化算法，通过使用跟踪以及片段合并，显著提高基于纹理合成的完全化算法的效率和合成质量；提出了基于图切分的交互式图像染色算法，在用户交互式地指定种子位置时，利用比较成熟的图切分技术快速有效地求得最佳分割；提出了将视频自动转换为矢量动画(Flash)的算法，使用改进的均值漂移算法，对整个视频进行颜色分割，得到三维视频分割结果，并通过边界追踪算法，用Bezier曲线对边界进行表示，完成色块边界平滑和矢量化；提出了瀑布等水流视频的水墨风格绘制算法，针对瀑布等水流视频的特点，提出此类视频的视频对齐算法，提出水流结构的提取算法，提出了基于水墨笔划库的水墨线条布置算法。这些工作发表于TheVisual Computers等国内外著名刊物上。
我们研究了针对去除了不希望出现的对象之后的视频进行补全的算法，通过使用跟踪(tracking)以及片段合并(fragment merging)，显著提高基于纹理合成的视频补全算法的效率和合成质量。该成果被Pacific Graphics 2005国际会议录取，并发表在The Visual Computer的专辑上，如图1所示。
| | |
 |
||
| |
我们研究了基于图切分的交互式图像染色算法。在用户交互式地指定种子位置时，利用比较成熟的图切分(graph cut)技术快速有效地求得最佳分割。在交互过程中，图切分可以很快地迭代计算，从而实现黑白图像快速、交互式地彩色化，该成果发表在计算机学报上，如图2所示。
| | |
 |
||
| |
我们研究了将视频自动转换为矢量动画(Flash)的算法，使用改进的均值漂移算法，对整个视频进行颜色分割，得到三维视频分割结果。然后通过边界追踪算法，用Bezier曲线对边界进行表示，完成色块边界平滑和矢量化，如图3所示。
| | |
 |
||
| |
我们还研究了瀑布等水流视频的水墨风格绘制算法，针对瀑布等水流视频的特点，提出此类视频的视频对齐算法，并利用光流变化图提出水流结构的提取算法，最后基于水墨笔划库的对水墨线条进行布置，生成不同水墨风格的水流动画。
| | |
 |
||
| |
内容敏感的视频缩放是指在视频缩放时重视保留视频中的重要内容的大小和纵横比例，而不是全部内容按照比例进行缩放。视频缩放问题看作是像素缩放的问题。不同像素根据其重要性来调整它们各自的大小，同时还要考虑视频的时空一致性。
我们提出一个基于“可伸缩性图”的视频尺寸调整的算法。这种方法的本质上是一种基于“纹理映射”的算法。
算法可以分为四个步骤：首先，针对输入视频，计算重要性图。接着，根据重要性图，通过随机游走模型，计算可伸缩性图。然后，根据目标尺寸和可伸缩性图，通过缩放函数计算出映射函数。最后，根据映射函数，用纹理映射的算法得到尺寸调整之后的视频。
本算法的特点在于：首先，算法的前两步（计算重要性图和可伸缩性图）的速度无法达到实时，但算法的后两步（计算缩放函数和纹理映射）的速度非常快。如果在预处理的时候将可伸缩性图计算好并和原始视频存放在一起，产生一个“多尺度视频”，就能实时的应用缩放函数和纹理映射，得到尺寸调整之后的视频。其次，随机游走模型可以用GPU 进行高效的求解，因此预处理的速度虽然不能达到实时，但也可以很快的计算（通常可以达到4 ? 5fps）。最后，产生的可伸缩性图非常平滑，所以可以很容易被高效的压缩，这样产生的“多尺度视频”通常只需要比原始的压缩视频多1 到2 倍的空间。
该工作被Pacific Graphics 2008录用，即将发表在Computer Graphics Forum 杂志。
| | |
 |
||
| |
| | |
 |
||
| |
半透明材质的编辑
半透明物体材质是在自然界中广泛存在的一类材质，如大理石、牛奶、面包、米饭、玉等。传统的真实感图形学只处理不透明物体，如金属、塑料等。半透明物体的光照特性相比不透明物体而言，更加复杂。我们提出一个实时编辑半透明物体材质的方法，并且基于该方法实现了一个复杂的光照条件下的半透明材质物体的编辑系统。该系统允许艺术家方便的修改和编辑半透明材质的各类参数和属性，并实时的给出高真实感的绘制效果的反馈，大大方便了艺术家编辑半透明材质的操作。
该工作是基于近年来全局环境光照的PRT绘制框架。通过将半透明衰减函数通过基函数的线性组合的形式表达，半透明材质的绘制被化简为简单的点积形式。另外，我们提出一种线性分段基函数用于表达半透明衰减函数。我们证明了该基函数在表达半透明衰减函数上比小波基函数和傅立叶基函数更加有效。
总的来说，我们的工作有三大贡献：
1. 将PRT框架首次应用到半透明材质编辑中；
2. 提出一种新型用于表达半透明衰减函数的基函数，线性分段基函数；
3. 实时的半透明材质编辑系统
| | |
 |
||
| |
图 4-1 半透明材质编辑
上述成果发表于欧洲图形学会议（Computer Graphics Forum杂志）上。论文及视频可以访问网站 http://cg.cs.tsinghua.edu.cn/ 获得。
三维数据的知识产权保护和虚假图像识别
三维数据的获取与建模需要大量的技术性工作，由此生成的三维数据具有重要的意义和价值。作为知识产权保护最为行之有效的技术之一，数字水印技术和数字版权管理技术是我们的重点研究对象。三维模型的数字水印技术是近年来国际上研究的热点问题之一。
主要面临的嵌入信息容量和鲁棒性两大问题。三维模型的数据量巨大，可望嵌入更多的水印信息，但由于三维模型顶点无序的特点，要实现数字水印的盲检测，需要嵌入大量的顺序信息，从而导致实际嵌入的水印信息量不大。同时，三维模型具有良好的可编辑能力，从另一个角度看来，三维模型水印面临的攻击种类较多，要对各种攻击达到较高的鲁棒性是非常困难的。
我们的工作以知识产权保护为目的，以脆弱、半脆弱的水印嵌入技术为核心，并进一步实现三维模型的数字版权管理体系。构造对恶意篡改敏感、对常见应用处理及噪声鲁棒的半脆弱关键特征，结合数字签名技术，对嵌入的水印进行预处理，增强版权认证的鲁棒性，实现具有实用价值的三维几何数据的版权认证方法。从而进一步结合信息加密技术、智能处理技术，研究数字版权管理新机制，改进目前数字版权管理系统，解决其存在的缺陷，建立三维模型的数字版权管理的体系结构。在三维几何数据的数字水印技术上，我们构造针对恶意篡改的脆弱、半脆弱关键特征，实现可应用于内容认证的数字水印嵌入技术。同时结合数字签名技术，实现三维几何数据的版权认证方法。在三维模型的数字版权管理技术（DRM）方面，我们研究结合信息加密和数字水印的数字版权管理新机制，包括方法、协议、原型系统，解决目前数字版权管理系统的缺陷，建立三维模型的数字版权管理的体系结构。我们在基于积分不变量的三维模型水印算法和三维模型水印不可见性评测取得了较好的成果。
与以上研究成果相关的两篇论文都已投往国际知名期刊/会议，一篇A new watermarking method for 3D model based on integral invariant投至IEEE transaction on Multimedia，另一篇Strain-based Evaluation for the 3D Models Watermarking投至Pacific Graphics 2007。
|
|
|
 |
||
|
|
虚假图像识别是当前信息安全的一个热门研究领域。我们总结现有的虚假图像识别技术，改进现有的基于Denoise filter、CFA插值、图像信噪比等现有方法，发掘最新的相机特征，识别图像是否相机直接获取，甚至鉴别出使用了何种相机进行拍摄。通过调研，我们实现了Copy-Move检测算法。Copy-Move检测算法的思路为：首先将图像分成许多小块，然后计算块间的相关性。如果存在某一对连续区域，其所有对应块间的相关性都大于某一个阈值，则认为该连续区域是Copy-Move的。算法的核心是块间相关性的计算。我提出使用二维矩阵相关性的计算公式，提高了检测的准确性以及抗攻击性。下图是实验结果：
|
|
|
 |
||
|
|
随着互联网的迅速发展，越来越多的数字产品纷纷进入公开网络环境。为对数字产品进行保护，数字水印技术应运而生，成为近年来计算机科学研究的一个热点领域。随着CAD技术、生物医学技术及三维动画技术的发展，得到广泛应用的三维模型也进入了网络环境中，同样产生了如何有效地对其进行保护的问题。作为一种新的数字产品形式，针对三维模型的数字水印技术也开始得到关注。
积分不变量是一种新颖的模型表面特征量，它体现出了一些可以成为三维模型水印嵌入特征域的良好性质。以积分不变量作为水印嵌入的特征量，我们提出了一种三维模型水印算法。算法主要过程是通过调整模型顶点位置，将积分不变量的数值改变为期望的嵌入数据后的数值，达到水印嵌入的目的。
该算法为空域半脆弱盲水印算法，可以抵抗顶点乱序、RST变换、轻微噪声等非恶意攻击，并能够检测出局部的恶意攻击位置，具有较好的实用性。与前人的研究成果相比，我们明确区分了恶意攻击和非恶意攻击，对非恶意攻击鲁棒，而对恶意攻击则较为敏感，并对噪声攻击获得了更好的鲁棒性效果，在三维模型的认证方面具有良好的实用性。
另外，在实践过程中我们发现，已有的计算积分不变量的算法并不适合在水印算法使用。我们提出了一种快速计算三维模型积分不变量的方法。我们的算法采取较为直接的思路，试图由积分不变量的定义入手直接进行通过几何手段计算，取得了更快的计算速度。
上述成果被国际杂志IEEE Transactions on Visualization and Computer Graphics录用，预计于2009年2月发表。
|
|
|
 |
||
|
|
|
|
|
 |
||
|
|
基于反曲率映射的最优共形参数化
三角网格平面参数化问题是数字几何处理中研究的热点问题，由于三角网格本身没有规则的参数域，这给高效处理带来了很多困难。平面参数化的目的是建立从三角网格到二维平面参数域的映射关系。平面参数化的优化目标应当是保长度的。这就要求曲面本身是可展的，即曲面上每点的高斯曲率为0。这个约束通常都是不满足的，因此，需要考虑更弱一些的约束条件。共形映射 (conformal mapping) 是理论上和实践上都很重要的一类映射，它的特点是局部保角。如图1所示：
|
|
|
 |
||
|
|
可以看到棋盘格的纹理局部正交性质在参数化过程中并没有改变。而于此同时，共形参数化却带来了参数域的面积扭曲，这会直接影响到纹理映射、网格重采样等应用的效果。此外，网格具有拓扑连接信息，如何针对不同亏格（Genus）的网格模型采用统一的参数化方法，是另外一个重要的问题。
我们基于离散共形几何的基础理论，引入Circle Packing度量，证明了从网格顶点高斯曲率到覆盖圆半径对数的微分关系，是由一个动态的Poisson方程决定的。利用该微分关系，我们提出了反曲率映射的概念，即对一个给定的网格模型，当各顶点的高斯曲率处于“允许曲率空间”中，则唯一决定了可以诱导出该高斯曲率分布的平面欧式度量。基于反曲率映射，可以求解任意拓扑模型的平面共形映射，结果可见图2：
|
|
|
 |
||
|
|
利用反曲率映射，我们还将求解最优共形参数化中面积扭曲极小的问题，转化为在允许曲率空间中求解使面积扭曲极小的高斯曲率分布问题，并找到了一种能量函数，称之为“曲率熵”，其在允许曲率空间中具有全局最小值，并提出了一种边界曲率扩散的快速求解该全局最小值的方法。在允许曲率空间中求解最优共形参数化的方法如图3所示：
|
|
|
 |
||
|
|
上述成果发表于国际杂志IEEE Transactions on Visualization and Computer Graphics。可以访问网站 http://cg.cs.tsinghua.edu.cn/ 获得。
使用单形变换的骨架变形动画
骨架变形是是流行商业软件中最重要的变形技术之一。传统的骨架变形技术中，皮肤上的点由几根相关分支控制，并分配有不同的权重。每个点在变形后的位置由相关分支发生刚体位移后加权平均得到。骨架动画制作效果好坏的关键是权重的选择。但是到现在为止，还没有一种能在各种情况下通用的权重选择方法，因而动画师在商业软件中使用该技术时常需要花费大量时间手工反复调节权重。
|
|
|
 |
||
|
|
在本项研究中，抛弃了传统骨架变形方法用分支直接控制顶点的思路，提出使用分支控制单形的几何变换，并通过几何变换能量函数的全局优化求解确定网格顶点变形后的位置。用本方法求解骨架变形问题，有如下优点：首先，使用分支控制单形，意味着直接使用了网格中顶点和顶点间的连接关系和网格的局部形状信息。传统骨架变形方法没有直接使用这一关系，面片间的连接关系只能通过权重的分配体现出来。其次，通过对几何变换能量函数的全局优化求解，可以将骨架连接处面片间的位置误差传播到邻近面片上。因而即便不使用权重，该算法也可以获得光滑、均匀的变形结果。此外，通过在优化方程的目标函数中引入单形变换的平移变量，本方法求解时无须固定任何顶点，并可保证网格变形结果与变形的骨架保持紧密一致，克服了以往单形变换的变形方法中变形结果与固定顶点选择相关的缺点。
|
|
|
 |
||
|
|
为获得骨架对网格面片的控制关系，本项研究中还提出了一种新的基于骨架的网格分片算法。基于给定骨架，该算法利用面片到分支的空间距离和面片到分支的网格上最短路径作为聚类准则，可以快速、鲁棒地计算网格分片。如果给定骨架的连接点位置不合理，本算法可以通过Graph-Cut方法对该连接点处的网格分片进行调整。
本项研究提出的骨架变形算法还可以扩展到用线段、点控制网格变形，以及使用线段控制网格扭转。
|
|
|
 |
||
|
|
上述成果发表于国际杂志IEEE Transactions on Visualization and Computer Graphics。可以访问网站 http://cg.cs.tsinghua.edu.cn/ 获得。
实时全局光照明
支持复杂光影效果，高真实感材质表现和纹理贴图的大规模动态场景的实时绘制，一直是真实感图形学中的热点问题。它在计算机图形学许多领域如电脑游戏制作、三维几何建模、光源设计和材质纹理设计等方面都有广泛和重要应用。
基于近年来全局环境光照的PRT绘制框架，我们提出了一种新型的基函数，球面分段常量基函数(Spherical Piecewise Constant Basis Functions)。该基函数可以同时支持全频率表达，易于旋转和高效多次相乘三种特性。通过使用该基函数，我们能够支持包含旋转和平移的物体的动态场景全频率光影效果。在我们的系统中，艺术家可以方便的进行全部的设计工作：动态的调节光源，动态的变换场景中物体的位置、方向，就可以立刻看到更新后的光影效果；同时，我们还将支持基于数据的复杂的材质模型的绘制效果；另外，在绘制的过程中，我们艺术家动态的编辑材质，这将极大方便艺术家进行实时的材质设计；最后，我们还进一步研究了算法在GPU上的性能，使得对于大规模动态场景，可以达到实时的绘制帧率。
|
|
|
 |
||
|
|
上述成果发表于国际杂志IEEE Transactions on Visualization and Computer Graphics。可以访问网站 http://cg.cs.tsinghua.edu.cn/ 获得。