一种鲁棒的可视外壳生成算法*

针对各种传统可视外壳生成算法中数据冗余、精确度低、健壮性不足等问题, 提出了一种新的可视外壳生成算法,即采用加权线段求交、线段集合中心线性过滤、多边形边界检测等方法重建物体模型。与传统方法相比,本算法能够更稳定地计算线段交集,表面边界提取更加准确,重建结果精确逼近真实物体。实验表明, 通过该算法计算的物体可视外壳能够更好地逼近真实模型,精度高。     

采用变形模型的图像序列可视外壳计算方法

针对基于图像序列变形模型三维重建中至关重要的初始模型计算问题,提出一种基于图像序列计算可视外壳的方法.该方法基于Snake活动轮廓变形模型,将真实物体可视外壳的计算问题转化为初始曲面通过内外力作用驱动收敛于目标物体的问题.以真实物体图像序列中提取的物体轮廓为输入,根据轮廓信息和光滑度信息计算内力及轮廓力大小,驱动球体初始曲面变形收敛于可视外壳;在变形过程中加入删除短边、分裂长边、对角线翻转等网格优化操作,以避免发生网格错乱.实验结果表明,文中方法有效地克服了传统的基于体元素细分产生网格算法网格质量不高的缺点,且参数可调,易于实现,占用内存少,生成的曲面更加光滑,细节恢复效果理想.     

基于链表的Dijkstra算法优化研究

迪杰斯特拉算法是图论中计算最短路径的经典算法,但在实际使用中该算法耗费大量的计算时间和存储空间。通过对传统迪杰斯特拉算法的深入分析,在计算时间和存储空间上对该算法提出了一种新的优化方案,并给出了优化后的详细算法。改进算法从消除冗余计算和冗余存储入手,采用链表数组作为存储结构。经算法复杂度分析,优化后的迪杰斯特拉算法在求解最短路径问题时在时间和空间复杂度上都有明显的提高。该优化算法操作性强,具有一定的实用价值。     

基于可视外壳的cage 生成

借助cage 作为代理几何来处理高精度复杂模型,正成为计算机动画与几何造型中的一种重要方法.目前,已有的cage 生成算法尚缺乏普适性,很大程度上依赖于几何的表示和模型的复杂度.因此,提出一种基于可视外壳的cage 生成算法.通过逆向模拟计算机视觉领域可视外壳的生成过程获取cage,以实现cage 生成与几何表示和模型复杂度无关的目标.实验结果表明,该方法易于实现且效率高.     

一种构造概念格的改进算法

Chein算法是一种批处理概念格构造算法,它构造过程中层次清楚,易于生成Hasse图,但是造格的过程中生成大量冗余的概念,降低了构造概念格的效率.提出一种对Chein算法的改进算法,保留了原算法层次清晰的优点,同时避免了冗余概念的产生,从而降低了构造概念格的时间复杂度.     

一种基于小生境策略的阴性选择算法

阴性选择算法是计算机人工免疫系统的传统核心算法之一,并以此为基础产生了许多改进算法,但这些算法大多存在计算时间过长以及空间资源消耗过大等问题。针对这些问题,提出了一种基于小生境策略的阴性选择算法,算法引入了小生镜策略,增强了检测器生成的多样性,降低了算法的复杂度并减少了检测器的生成时间,提高了阴性选择算法的生成效率。     

考虑多粒度属性约简的关联规则挖掘研究

大数据时代，人们获取所需信息的困难度提高，而数据挖掘是当下解决此问题的关键技术。Apriori算法作为数据挖掘中的常用算法，通过挖掘数据背后的潜在关联规则。考虑到传统Apriori算法执行过程中，数据扫描频繁、候选集获取繁琐等问题，提出采用加权Apriori算法，即将冗余记录存储一次，并将记录的重复次数占全部记录数的比值作为权重，压缩空间；采用二进制的布尔矩阵替代原有数据集，通过矩阵内部“与运算”，获取最大频繁集，降低时间复杂度。考虑到原始数据冗余性以及粗糙集属性约简的不精确性，在提取关联规则前，提出采用多粒度粗糙集的属性约简算法，通过知识粒度细化属性值来提高约简精度，降低空间复杂度。最后，将所提方法与基于频繁矩阵的Apriori算法以及原始Apriori算法进行比较，验证所提方法的实用性和有效性。     

改进A*算法的机器人全局最优路径规划

针对传统A^*算法规划的路径存在很多冗余点和拐点的问题,提出了一种基于A^*算法改进的高效路径规划算法。首先,改进评价函数的具体计算方式,减小算法搜索每个区间的计算量,从而降低寻路时间,并改变生成路径;其次,在改进评价函数具体计算方式的基础上,改进评价函数的权重比例,减少生成路径中的冗余点和拐点;最后,改进路径生成策略,删除生成路径中的无用点,从而提高路径的平滑性;此外,考虑到机器人的实际宽度,改进后算法引入障碍物扩展策略保证规划路径的可行性。将改进A^*算法与三种算法进行仿真对比,实验结果表明,改进后的A^*算法规划的路径更加合理,寻路时间更短,平滑性更高。     

基于Galois联络的最小非冗余关联规则挖掘

关联规则挖掘是NP难题,关键是如何约简频繁项集。本文以Galois联络为理论基础,应用Galois联络的闭包运算及其性质定义数据库中的频繁项和封闭频繁项,提出了挖掘关联规则生成子、精确关联规则生成基和近似关联规则本征基的概念,并由此构造最小非冗余精确关联规则和近似关联规则挖掘的MNRM算法。该算法与Apriori算法相比较,挖掘的关联规则是最小非冗余的,降低了计算复杂度,而且规则具有不丢失任何信息、最小前件和最大后件以及对用户最实用和最相关等优点。     

基于蚂蚁路径的时序电路故障诊断算法

提出了一种VLSI时序电路自动测试型生成(Automatic test pattern generation，ATPG)的新算法。传统ATPG算法采用局部状态转换图或收集门级电路的知识以及提取电路规则来解决时序电路ATPG的困难。本算法引入新的模型，着重解决了ATPG中的计算冗余问题。在蚂蚁路径模型的基础上，前向搜索得到了重建，故障点的前向传输和回溯归结到了单一路径之上．而该路径上可能分布着许多待测的故障点，从而改善了以往时序电路ATPG算法中搜索重复而导致的计算冗余问题，同时，最小测试向量的获取为数学定理所证明。最后在Benchmark电路上进行的与ILP算法的比较试验表明，本算法具备同样的故障覆盖率，且速度更快。     

Efficient Polyhedral Modeling from Silhouettes

Modeling from silhouettes is a popular and useful topic in computer vision. Many methods exist to compute the surface of the visual hull from silhouettes, but few address the problem of ensuring good topological properties of the surface, such as manifoldness. This article provides an efficient algorithm to compute such a surface in the form of a polyhedral mesh. It relies on a small number of geometric operations to compute a visual hull polyhedron in a single pass. Such simplicity enables the algorithm to combine the advantages of being fast, producing pixel-exact surfaces, and repeatably yield manifold and watertight polyhedra in general experimental conditions with real data, as verified with all datasets tested. The algorithm is fully described, its complexity analyzed and modeling results given.     

一种基于网格索引的数据聚类算法

为了提高基于密度聚类算法的效率,避免算法在执行过程中的多余搜索,提出了一种基于DBSCAN算法的改进的空间数据聚类算法。该算法采用对象邻域空间进行划分的方法,将网格索引结构应用于该算法。在核心对象的邻域内选择八个方向上未标记且距离核心对象最边缘的对象来扩展种子对象,减少查询次数,降低聚类的时间复杂度。在实验中,利用海量数据集对算法进行测试,测试结果证明新算法在保证聚类精度的情况下时间效率显著高于DBSCAN算法。     

关键路径的稀疏矩阵求解算法

求解AOE网的关键路径算法一般基于拓扑排序，虽然具有较好的时间复杂度(O(n+e))，但由于必须进行拓扑排序，同时还要进行拓扑逆序扫描，使得算法本身比较复杂。针对这个问题提出了一个算法，算法采用了稀疏矩阵作为数据的存储结构，为防止关键路径丢失，采用队列方式进行操作。同经典算法相比，该算法简单，时间复杂度相近(O(n+e/n))。     

一种新的人眼视觉运动认知特性实验分析方法

视觉感知过程源于对象自身的大范围拓扑性质,而场景对象发生运动状态变化时,其所在空间的大范围拓扑关系也将随之改变。为探索大范围拓扑性质和运动性质同时改变时人眼视觉的认知优先特性,基于虚拟现实技术及眼动跟踪技术,通过构建虚拟驾驶及眼动轨迹分析实验平台,结合拓扑复杂度和空间拓扑关系概念分别探讨二维和三维空间中人眼视知觉对物体运动的认知特性。在此基础上,采用响应面分析方法设计场景中自变量因子的随机实验数值,通过可视化方法对比多组认知场景的无感反馈眼动监测结果。实验结果表明,在Tobii眼动仪采集的545个眼动数据中,发生在运动物体上的数据有516个,相比于物体自身属性的大范围拓扑性质变化,人眼视知觉过程更优先识别物体运动的大范围空间拓扑关系变化。该运动认知优先特性为可靠人工智能驾驶中的视觉注视预测技术提供了新的研究思路,同时验证了所提实验分析方法的有效性。     

Volumetric stereo and silhouette fusion for image-based modeling

This paper presents a volumetric stereo and silhouette fusion algorithm for acquiring high quality models from multiple calibrated photographs. Our method is based on computing and merging depth maps. Different from previous methods of this category, the silhouette information is also applied in our algorithm to recover the shape information on the textureless and occluded areas. The proposed algorithm starts by computing visual hull using a volumetric method in which a novel projection test method is proposed for visual hull octree construction. Then, the depth map of each image is estimated by an expansion-based approach that returns a 3D point cloud with outliers and redundant information. After generating an oriented point cloud from stereo by rejecting outlier, reducing scale, and estimating surface normal for the depth maps, another oriented point cloud from silhouette is added by carving the visual hull octree structure using the point cloud from stereo to restore the textureless and occluded surfaces. Finally, Poisson Surface Reconstruction approach is applied to convert the oriented point cloud both from stereo and silhouette into a complete and accurate triangulated mesh model. The proposed approach has been implemented and the performance of the approach is demonstrated on several real data sets, along with qualitative comparisons with the state-of-the-art image-based modeling techniques according to the Middlebury benchmark.     

支持STL数据源的网格曲面动态空间索引

针对STL文件格式存在网格顶点数据冗余以及缺乏面片邻接信息等缺陷,提出一种基于多维动态空间索引的显式曲面拓扑重建算法,在消除网格顶点数据复本的过程中逐步构建网格曲面顶点的KD树,通过该索引提高顶点数据复本消除效率,并基于KD树叶节点层数据存储的开放性融入半边数据结构,实现曲面拓扑结构的快速重建。最后,对6个不同规模的数据模型进行实验:与采用R^*-Tree、数组、散列表作为索引等方法相比,所提出的KD树与半边结构融合的动态空间索引在处理近百万面片的数据文件时,去除冗余顶点用时11.93 s,拓扑重建仅仅需要2.87 s,大大减少了冗余顶点的去除时间和拓扑重建时间,并且有效支持网格曲面拓扑邻域信息的快速查询,查询时间在1 ms之内,远小于对比算法所用时间。实验结果表明:所提算法能够提高网格曲面冗余顶点去除效率和拓扑重建效率,实现网格曲面拓扑邻域信息的快速查询。     

Reduced Depth and Visual Hulls of Complex 3D Scenes

Depth and visual hulls are useful for quick reconstruction and rendering of a 3D object based on a number of reference views. However, for many scenes, especially multi‐object, these hulls may contain significant artifacts known as phantom geometry. In depth hulls the phantom geometry appears behind the scene objects in regions occluded from all the reference views. In visual hulls the phantom geometry may also appear in front of the objects because there is not enough information to unambiguously imply the object positions. In this work we identify which parts of the depth and visual hull might constitute phantom geometry. We define the notion of reduced depth hull and reduced visual hull as the parts of the corresponding hull that are phantom‐free. We analyze the role of the depth information in identification of the phantom geometry. Based on this, we provide an algorithm for rendering the reduced depth hull at interactive frame‐rates and suggest an approach for rendering the reduced visual hull. The rendering algorithms take advantage of modern GPU programming techniques. Our techniques bypass explicit reconstruction of the hulls, rendering the reduced depth or visual hull directly from the reference views.     

基于功率谱及有限穿越可视图的癫痫脑电信号分析算法

针对可视图（VG）算法存在噪声鲁棒性差的问题,提出一种改进的有限穿越可视图（LPVG）建网方法。该算法基于可视图（VG）算法的可视性准则,并设定有限穿越视距,将时间序列中满足条件的点连接起来,从而将时间序列映射为网络。首先,对LPVG算法进行性能分析;然后,将LPVG算法结合功率谱密度（PSD）算法应用到癫痫发作前、中、后脑电信号的识别上;最后,提取三种状态下癫痫脑电信号的LPVG网络特征参数,研究癫痫对网络拓扑结构的影响。仿真结果表明,与VG和水平穿越可视图（HVG）相比,虽然LPVG算法的时间复杂度较高,但是LPVG对信号中的噪声具有较强的鲁棒性：分别对周期、随机、分形和混沌四种时间序列进行LPVG建网,发现随着噪声强度增大,LPVG网络聚类系数的波动率均为最低,分别为6.73%、0.05%、0.99%和3.20%。接下来对脑电信号的PSD和LPVG建网分析结果表明,癫痫发作中,PSD值在delta频带下显著增强,而在theta频带下显著降低;LPVG网络拓扑结构有所改变,网络中各模块的独立性有所提高,网络的平均路径长度增大,复杂度降低。所提的功率谱密度和有限穿越可视图算法能够有效表征癫痫前、中、后三种状态下的脑电信号能量分布和单通道信号可视化后的网络拓扑结构的异常,为癫痫的病理研究和临床诊断提供帮助。     

一种改进的快速三维凸包生成算法及实现

本文阐述一种快速的三维凸包构造新算法,算法吸收了Quick Hull方法中每次选用凸包的极值点(Extremal-Point)来构造新凸包的思想,在此基础上改进为选用二次极值点的方法来构造新凸包,并结合"冲突图"(Conflict-Graph)来更新凸包外的点和当前凸包的拓扑结构关系,从而取得了快速排除凸包的内部点、缩小问题规模、实现高效构建凸包的效果。本文算法的时间复杂度为O(nlgr),通过实验证明本文算法与QuickHull算法相比平均执行消耗时间减少20%,因此本算法具有理论和实际应用价值。