基于照片序列的多面体虚拟壳快速生成算法

介绍了一个基于照片序列的三维模型重构系统，通过照片图像中提取物体轮廓对应的光锥相交得到多面体虚拟壳，并介绍一个基于活性点列的快速相交算法。     

基于顶点索引的三维建模与可视化方法研究

分析了影响三维建模与可视化效率的主要因素,设计了一种新的基于顶点索引的三维模型数据组织方式,相对于传统的3DS模型文件,该方法避免了大量冗余数据的处理,并能充分发挥图形显卡高效的数据传输特性,经验证:显著提高了模型绘制的效率,较好地解决了复杂模型高效三维可视化的问题。     

Depth-based complexity traces of graphs

In this paper we aim to characterize graphs in terms of a structural measure of complexity. Our idea is to decompose a graph into layered substructures of increasing size, and then to measure the information content of these substructures. To locate dominant substructures within a graph, we commence by identifying a centroid vertex which has the minimum shortest path length variance to the remaining vertices. For each graph a family of centroid expansion subgraphs is derived from the centroid vertex in order to capture dominant structural characteristics of the graph. Since the centroid vertex is identified through a global analysis of the shortest path length distribution, the expansion subgraphs provide a fine representation of a graph structure. We then show how to characterize graphs using depth-based complexity traces. Here we explore two different strategies. The first strategy is to measure how the entropies on the centroid expansion subgraphs vary with the increasing size of the subgraphs. The second strategy is to measure how the entropy differences vary with the increasing size of the subgraphs. We perform graph classification in the principal component space of the complexity trace vectors. Experiments on graph datasets abstracted from some bioinformatics and computer vision databases demonstrate the effectiveness and efficiency of the proposed graph complexity traces. Our methods are competitive to state of the art methods.     

离散非线性时变凸多面体系统族的鲁棒正不变集

动态系统的状态约束和控制约束等问题可归结为状态空间中某些集合的正不变性.利用 混合单调分解方法研究离散非线性、时变凸多面体系统族的线性状态约束集合的鲁棒正不变性． 对由矩阵凸多面体和加性区间扰动描述的线性时变离散系统族,得到了鲁棒正不变集的充分必要 条件;对非线性系统族则得到有关充分条件.这些条件均由系统族的顶点表述,易于检验,同时给 出示例.     

基于顶点存储类型的多边形填充算法

提出了一种基于顶点存储类型的多边形填充算法。该算法将多边形顶点和新生成的交点划分为三种类型进行存储,然后由过顶点的扫描线将多边形分割成若干个梯形区域分别进行填充。此算法只涉及过顶点的扫描线,且多边行边上的像素点坐标可以直接从边的直线方程中获得,从而使得该算法大大降低了计算的复杂性。     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

一种新的基于顶点聚类的网格简化算法

在计算机图形学中,经常采用多边形网格来描述物体模型.由于绘制时间和存储量 与多边形的数量成正比,过于庞大的物体网格模型通常是不实用的.模型简化在计算机动画、 虚拟现实和交互式可视化等计算机图形应用领域有着广阔的应用前景.为此提出一种新的基 于顶点聚类的网格简化算法.该算法利用八叉树对网格进行自适应划分,给出了一种基于点 到平面距离的有效的误差控制方法,并能在用户指定的误差范围内通过使原始网格中的顶点 聚类达到大量简化的目的.该算法实现简单,速度快且能很好地保持边界特征.给出的一组图 例说明了该算法的有效性.     

基于头顶点三维运动轨迹的身份识别新方法

提出了一种基于头顶点三维运动轨迹的身份识别新方法,并对相关的基本问题进行了较为系统的研究.人在行走时,从头顶点三维运动轨迹中可提取出入体侧视平面上的身高波动信息和人体俯视平面上的摇摆运动信息.从身高波动信息可提取身高参数(身高均值、身高幅值)和步幅参数(步幅长度、步幅频率);这些参数已被证实可作为身份识别的特征参数.本...     

一种基于节点影响力的局部社区发现算法

为快速准确寻找社会网络中的社区结构,从节点影响力的角度出发,提出一种新的社区发现算法.算法设计过程中引入了点权,它能够衡量节点影响力的大小;首先根据＂种子＂节点的点权有选择地进行广度优先搜索,使点权较大的节点不断地影响点权较小的节点,进而得到＂种子＂节点所在的社区结构,然后再从已知的社区外任取一个新的＂种子＂节点,重复上述过程,就可得到整个网络的社区结构.对算法进行优化并应用到实际网络,实验结果验证了算法的可行性,与经典算法相比,该算法的准确性和计算速度都有所提高.     

基于顶点编码的多边形窗口线裁剪高效算法

从多边形窗口线裁剪的本质特征出发，首次提出窗口顶点编码的新概念。以被裁剪直线为参照系，将多边形窗口划分为正区、负区和近零区三类区域，从而快速完成多边形窗口顶点编码。通过窗口顶点编码与传统的线段编码相结合，无须求交即可快速排除大部分窗外线段；进一步可以直接得到与直线相交的窗口边，加快了求交进程。更有意义的是，通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况：裁剪直线通过多边形的顶点、裁剪直线通过多边形的边。实验结果表明，新算法提高了裁剪效率并具有很好的稳定性。