鲁棒的满足误差约束的平面cage生成EI北大核心CSCD

Cage是基于广义重心坐标的形状编辑与变形应用的基本要素,但现有算法无法保证生成的cage与模型间的距离能够满足给定的误差约束.为此,提出一种鲁棒的平面cage生成算法,对于用户指定的平面网格模型和Hausdorff距离上界,首先生成初始cage,使其与平面网格模型边界间的双向Hausdorff距离在设定的界内;其次,通过拓扑优化和几何优化降低cage的复杂度,并保证cage满足距离上界约束.对于任意的平面网格模型,该算法能从理论上保证生成的cage满足约束.在包含大量平面网格模型的公开数据集上的实验结果表明,与现有方法相比,该算法生成的cage在相同的Hausdorff距离下顶点数更少,在相同的顶点数下Hausdorff距离更小.     

自交有理参数曲面网格生成

针对现有网格生成算法在处理自交曲面时出现的缺少交线表示、误差大以及交线附近三角形质量差的问题,提出一种针对自交有理参数曲面的网格生成算法.首先,利用动平面法计算曲面的奇异因子;其次,利用奇异因子和曲面的第一基本形式定位交线上的拓扑关键点;再次,基于动平面法设计了一种交线网格点配对生成算法,以保证网格交线的邻域协调性;最后,使用基于粒子的网格生成法生成参数域网格.在具有不同拓扑的自交曲面上进行网格生成实验,所提算法可保证网格交线拓扑正确性,且与未进行交线网格点配对的各类代表性各向同性网格生成算法相比,网格三角形最小角平均值平均高0.6%.     

平面阴影算法研究与实现

阴影对提升图形的真实感具有重要意义。探讨了平面阴影生成算法，针对平面阴影算法在实际应用中的缺点，利用OpenGL的模板缓冲技术实现阴影裁剪，利用基于截锥体的裁剪矩阵消除假影和反影现象，并利用OpenGL累积缓冲技术实现软阴影。较好解决了平面阴影算法的缺点，程序计算量小、效率高，图形的真实感和场景的可视化效果得以提升，达到良好的效果。     

平面连通域VORONOI图的算法

本文探讨了平面多边形的ＶＯＲＯＮＯＩ图的性质，研究了通过合并多边形边界的两个子集生成平面单连通域ＶＯＲＯＮＯＩ图的分治算法，以及合并外轮廓和“岛”轮廓的ＶＯＲＯＮＯＩ图来生成平面多连通域ＶＯＲＯＮＯＩ图的算法。     

基于位平面理论和奇异值分解的鲁棒零水印算法

针对灰度图像空域算法中水印鲁棒性较差的问题,提出了一种快速、鲁棒性强的零水印算法,并将该算法用于以数字图像为载体的信息隐藏,以实现水印信息的提取和认证。首先利用位平面(BP)理论将图像解析为不同的位平面层次,构造无权值的位平面矩阵,结合各位平面非零值个数生成图像的特征矩阵;然后对特征矩阵分块操作,利用奇异值分解(SVD)生成块最大奇异值矩阵,并通过对生成矩阵二维混沌加密得到注册零水印信息。仿真实验表明,所提算法具有较强的鲁棒性,在同类算法中对抗椒盐噪声攻击的性能提高了6%,对抗常见混合攻击的性能提高了12%。     

中点画线算法的三维推广

以往的中点画线算法仅适用于二维直线的生成一该文巧妙地利用直线在两个坐标平面内的投影，将二维中点画线算法推广到三维，用于空间直线的生成，给出了一个具体实例，并分析了计算误差和算法效率。结果表明，三维中点画线算法具有高效和高精度的特点，可在实际工作中用于空间直线生成、空间直线插补和运动控制等方面。     

一种基于图的平面点集Delaunay三角剖分算法

本文提出了一种基于图的平面点集Ｄｅｌａｕｎａｙ三角剖分算法。该算法首先求出平面点集的欧几里得最小生成树，然后逐次加入一边构造三角形网格，最后按最小内角最大的三角化准则，通过局部变换，得到平面点集的Ｄｅｌａｕｎａｙ三角剖分。本文同时阐述了它的对偶图；平面点集的Ｖｏｒｏｎｏｉ图的概念和性质。     

任意形状平面域的通用三角化算法

基于平面上散乱数据点的Ｄｅｌａｕｎａｙ三角剖分准则，提出了任意形状平面域的通用三角剖分算法。该算法不仅能用于Ｔｒｉｍｍｅｄ曲面的消隐显示及加工，也能用于有限元网格自动生成及其它领域。该算法已经成功应用于ＨＵＳＴＣＡＤＭ曲面造型及加工系统。     

移动视点视频的平面检测与跟踪

针对广泛存在的建筑物场景,提出了一种基于视频的平面检测与跟踪算法.算法分为3步,给定初始帧图像中的平面边界,第1步通过相邻2帧图像间的单应性矩阵跟踪平面边界,由于单应性矩阵跟踪会导致累积误差,首先采用RANSAC算法拟合边界线段,再使用绝对二次曲线约束和LM算法优化平面边界.第2步检测新出现的平面,根据原平面边界是由两组不同的平行线段组成提取该平面外围的第三类平行线段,由此判断是否有新的平面出现并检测新平面边界.第3步在检测到新平面边界后跟踪当前帧的所有平面到下一帧,当新出现的平面区域有增加或减少时,根据同一平面材质相似这一信息使用漫水填充和图像分割更新平面边界.最后,采用5个真实场景进行了实验,结果表明,文中算法能准确、稳定地在线检测与跟踪视频中的平面边界.     

基于平面扫描的双线圆弧缓冲区生成算法

在GIS领域,线目标实体的缓冲区生成有很多算法,常见的双线圆弧法存在结果多边形自相交和失真问题,处理起来相当复杂。在双线圆弧法基础上提出一种基于平面扫描技术的线目标缓冲区生成算法,在扫描过程中处理多边形自相交问题,同时能够避免失真现象。算法的时间复杂度为O（nlbn）。     

高频时钟网络布线拓扑结构的曼哈顿平面切割线生成算法

在传统的Planar-DME拓扑划分算法的基础上,提出一种将欧几里德平面上的拓扑连接线转换成曼哈顿平面上的切割线并建立虚拟通道的算法,来进行连线调整,完成时钟网络的零时滞平面化布线．算法在开发软件原型Clockstar中得以应用。     

基于故障相关矩阵的最优测试序列生成方法

针对最优测试序列生成问题,采用与或图搜索生成测试序列,将系统故障与测试之间的关系作为节点生成的依据,在综合了信息论与启发式搜索理论的基础上,由霍夫曼编码和信息熵构成的启发式搜索函数来引导与或图的搜索生成诊断树,安排最优的测试顺序,实现用最少的代价隔离系统故障;在解决与或图搜索问题中应用了改进后的AO*算法,避免出现"NP-完全"的复杂计算问题,整个过程大大减少了生成节点的数量,提高了故障隔离效率。     

二叉树平面坐标网及其应用

二叉树平面坐标网、平面坐标网二叉树的定义及其基本定理在本文给出。利用该平面坐标网二叉树，把平面中的网络点一一映射到一个整数集合上，从而可以把平面中的任意点近似地映射为一个整数，而且可以任意精确，对任意平面图形图象的处理、储存和传输起着极其重要的作用。本文给出的应用例子是二维实体的近似表示、储存、处理和打打印。     

图的树分解及其算法应用研究进展

图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。     

基于二叉树的故障树画树算法研究

由于在故障树分析、故障诊断和可靠性分析中迫切要求故障树图形化显示,所以文中研究了故障树画树算法。故障树显示为多叉树,将故障树节点的下一级节点作为左节点,将故障树同级右侧节点作为右节点,就把多叉树转换为二叉树存于数据库中,需要显示时将故障树节点信息对应的存于多向链表中的节点,通过递归函数计算出每个节点的坐标位置,然后用画树函数将故障树画于图形显示区域。文中基于C Builder 6.0开发环境,实现了故障树的图形显示,这样就为基于故障树的故障诊断提供坚实基础。     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

Fast Frequent Free Tree Mining in Graph Databases

Free tree, as a special undirected, acyclic and connected graph, is extensively used in computational biology, pattern recognition, computer networks, XML databases, etc. In this paper, we present a computationally efficient algorithm F3TM (Fast Frequent Free Tree Mining) to find all frequently-occurred free trees in a graph database, . Two key steps of F3TM are candidate generation and frequency counting. The frequency counting step is to compute how many graphs in containing a candidate frequent free tree, which is proved to be the subgraph isomorphism problem in nature and is NP-complete. Therefore, the key issue becomes how to reduce the number of false positives in the candidate generation step. Based on our observations, the cost of false positive reduction can be prohibitive itself. In this paper, we focus ourselves on how to reduce the candidate generation cost and minimize the number of infrequent candidates being generated. We prove a theorem that the complete set of frequent free trees can be discovered from a graph database by growing vertices on a limited range of positions of a free tree. We propose two pruning algorithms, namely, automorphism-based pruning and canonical mapping-based pruning, which significantly reduce the candidate generation cost. We conducted extensive experimental studies using a real application dataset and a synthetic dataset. The experiment results show that our algorithm F3TM outperforms the up-to-date algorithms by an order of magnitude in mining frequent free trees in large graph databases.     

基于改进的遗传算法的多目标优化问题研究

研究多目标优化算法问题,针对传统的多目标优化算法由于计算复杂度非常高,难以获得令人满意的解等问题,在图论和遗传算法基础上,提出了一种改进的遗传算法求解多目标优化方法。首先采用二进制编码表示最小树问题,然后采用深度优先搜索算法进行图的连通性判断,给出了一种新的适应度函数,以提高算法执行速度和进化效率。最后仿真结果表明,与经典的Prim算法和Kruskal算法相比,新算法复杂度较低,并能在第一次遗传进化过程中获得一批最小生成树,适合于解决不同类型的多目标最小树问题。     

网络最小生成树更新策略

求解最小生成树问题被广泛应用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动。而一旦发生改变,传统算法必须要再次计算最小生成树。但是虽然节点发生了变动,最小生成树未必全部发生改变,这就造成了不必要的浪费。鉴于此提出一种基于Kruskal算法和Prim算法的最小树更新策略,对Kruskal算法和Prim算法做了改进,使其不必重新计算也能在连通图发生改变时更新最小生成树。     

利用Hash树生成频繁项目集的新方法

频繁项目集的生成是关联规则挖掘中的关键问题 .提出基于 Hash树的频繁项目集生成新方法 ,探讨了 Hash树中候选项目集的数据组织与建立算法 ,提出了利用 Hash树计算候选项目集支持数的算法 ,并用 Java语言实现了该算法 ,最后通过实验验证了利用 Hash树生成频繁项目集的有效性