三角形和三角形相交测试技术研究

高效率的“三角形和三角形相交测试”对于提高碰撞检测算法效率,增强虚拟场景的真实感和沉浸感起着至关重要的作用。该文深入研究了“三角形和三角形相交测试”的基本原理和典型算法,根据算法思想提出两个概念：标量判别法和矢量判别法,并对两种算法进行验证,对仿真计算结果进行分析、比较得出：矢量判别算法是对标量判别算法的改进和优化,条件相同时检测效率提高约7％,算法更加简单快捷,具有较高的理论意义和实际工程应用价值。     

一种变形Fisher判别准则函数及最优判别向量集

基于Fisher判别准则函数式,提出了一种无约束的最优判别矢量集,并给出了求解算法,另外,当训练样本矢量数小于样本矢量维数（即小样本问题）,类内散布矩阵奇异,此时求F-S最优判别向量集及文中提出的无约束的最优判别矢量集都已不可行,对此提出了一种变形的Fisher判别准则函数,并给出了求解最优判别向量集算法。用ORL标准人脸库进行实验,实验结果表明,提出的两种最优判别向量集都有良好的分类能力。     

完备正交邻域保持判别嵌入的人脸识别

为解决邻域保持判别嵌入算法所面临的小样本问题,并充分利用类内邻域散度矩阵零空间和非零空间中的判别信息进行人脸识别,提出一种完备正交邻域保持判别嵌入的人脸识别算法。首先间接地利用特征分解方法去除总体邻域散度矩阵的零空间;然后分别在类内邻域散度矩阵零空间和非零空间中提取最优判别矢量。此外,为进一步提高算法的识别性能,给出了基于瘦QR分解的正交投影矩阵的求解方法。在ORL和Yale人脸库上验证了以上算法的有效性。     

计算SVM判别函数值的方法

当支撑矢量或待判别的样本很多时，支撑矢量机(SVM)算法对判别函数值的直接计算会影响整个SVM算法的速度．国外对于SVM的训练算法研究很深入，但判别函数值的算法研究很少．文中将从减少判别值计算的复杂性入手，提出矢量替换法(主要针对线性SVM)、正交矢量法(主要针对非线性SVM)的判别值计算算法．     

2D双树复小波与判别共同矢量结合的人脸认证

针对人脸认证中的小样本问题和Gabor小波特征提取的不足,提出一种有效的人脸认证算法。对预处理后的图像进行2D双树复小波变换,将每幅图像不同尺度下多个方向的小波系数幅值作为特征矢量,表征重要的局部信息;将提取的特征矢量向判别共同矢量空间投影,进一步提取具有判别能力的特征,同时进行降维;根据用户特定阈值进行认证。ORL人脸库和FERET子库上的实验结果验证了算法的有效性。     

块自适应标量-矢量量化算法压缩SAR原始数据

块自适应量化(BAQ)算法是目前比较成熟的一种合成孔径雷达(SAR)原始数据压缩算法,该算法以SAR原始数据块满足高斯分布为前提。由于SAR成像区域很复杂,有些数据块可能不满足高斯分布,因此提出了一种块自适应标量-矢量量化算法(BASVQ),当数据块满足高斯分布时,采用标量量化;当数据块不满足高斯分布时,采用矢量量化。实验结果表明,块自适应标量-矢量量化算法在性能上优于BAQ算法,具有一定的实用价值。     

虚拟漫游环境中基于矢量的快速碰撞检测算法

从虚拟漫游角度出发,将场景中的碰撞检测转化为视点与三角形的碰撞问题,提出一种基于矢量判别的快速碰撞检测算法.该算法通过位向因子和有向回路的方向来判断视点是否与三角形碰撞,从而避免复杂的余弦函数、移动距离等计算,加快检测速度.实验结果表明,对于大型复杂场景,该算法的检测效率优于其他基于余弦函数的视点与三角形碰撞检测算法.     

机会式电磁矢量传感器阵列互耦校正算法

针对电磁矢量传感器阵列中的互耦效应导致系统性能下降的问题,研究了一种分布式电磁矢量传感器机会式阵列互耦校正算法。首先建立可以从信噪比、波达方向估计精度和孔径扩展维数等性能方面分析线性阵列、三角形阵列和双三角形阵列等阵列结构特性的数学模型,然后根据性能分析结果构建了电磁矢量传感器机会式阵列架构,最后提出了适用于分布式电磁矢量传感器阵列的机会式互耦校正算法。实验结果从波达方向估计精度、空间谱估计精度和信噪比等方面证明了所提分布式电磁矢量传感器机会式阵列互耦校正算法比静态传感器阵列具有明显优势。     

一种人脸姿势判别与正脸合成的新方法

人脸深度旋转是人脸识别领域的一个瓶颈问题．首先探讨了不同方向、尺度的Gabor滤波器对于判别不同朝向的人脸姿势的性能，然后提出了一个基于Gabor滤波和分数幂多项式核Fisher判别准则的人脸姿势判别方法，最后利用改进的点点对应算法和线性物体类的原理构造正脸合成的算法．实验结果表明，新提出的姿势判别和合成方法是有效的．     

线段相交性问题求解的新算法与原理

本文根据线段的半平面方程特性,提出了一种“多重半平面”原理来研究线段的相交性问题,建立了线段是否相交的判别准则,同时根据该原理给出了两线段求交的新算法－“曲线的双向裁剪算法”。     

Comparative investigation of GPU-accelerated triangle-triangle intersection algorithms for collision detection

Efficient collision detection is critical in 3D geometric modeling. In this paper, we first implement three parallel triangle-triangle intersection algorithms on a GPU and then compare the computational efficiency of these three GPU-accelerated parallel triangle-triangle intersection algorithms in an application that detects collisions between triangulated models. The presented GPU-based parallel collision detection method for triangulated models has two stages: first, we propose a straightforward and efficient parallel approach to reduce the number of potentially intersecting triangle pairs based on AABBs, and second, we conduct intersection tests with the remaining triangle pairs in parallel based on three triangle-triangle intersection algorithms, i.e., the Möller’s algorithm, Devillers’ and Guigue’s algorithm, and Shen’s algorithm. To evaluate the performance of the presented GPU-based parallel collision detection method for triangulated models, we conduct four groups of benchmarks. The experimental results show the following: (1) the time required to detect collisions for the triangulated model consisting of approximately 1.5 billion triangle pairs is less than 0.5 s; (2) the GPU-based parallel collision detection method speedup over the corresponding serial version is 50x - 60x, and (3) Devillers’ and Guigue’s algorithm is comparatively and comprehensively the best of the three GPU-based parallel triangle-triangle intersection algorithms. The presented GPU-accelerated method is capable of efficiently detecting the potential collisions of triangulated models. Overall, the GPU-accelerated parallel Devillers’ and Guigue’s triangle-triangle intersection algorithm is recommended when performing practical collision detections between large triangulated models.

     

判断两个凸多面体是否相交的一个快速算法

在机器人路径规划中,碰撞检测算法占有十分重要的地位.在智能机器人仿真系统中,碰撞检测耗用的时间在整个路径规划过程所用时间中占有相当大的比例.于是,如何进一步提高碰撞检测的速度在智能机器人路径规划系统中就起到了非常关键的作用.而碰撞检测问题最终转化为判断三维空间中两个凸多面体是否相交的问题.就这一问题,给出了一种新的算法,其思想是取一个从一个凸多面体指向另一个多面体的向量,根据两个多面体中的面与这一向量的相对位置关系来寻找相交的平面.即有两个多面体的交点位于这一平面,若能找到一个相交平面则可以断定两个多面体     

基于可区分度的连续空间属性约简算法研究

针对现有粗糙集属性约简方法中存在的连续数据处理时的信息丢失、粒化策略引入不一致信息、参数寻优困难等问题,提出一种适用于连续型数据、基于类别可区分度的非单调性启发式属性约简算法。首先以各样本的标签为依据对论域进行划分,同一标签的样本组合成一个簇,定义每个簇的类间可区分度和类内可区分度;其次,以最大化类间可区分度、最小化类内可区分度为约简原则,定义了一种新的属性重要性判别准则以确定最优约简集,从而提高后续分类器的分类性能。在十一个UCI数据集上与其他六种属性约简算法进行对比实验。结果表明,与六种算法相比,所提算法获得的约简集平均维度减小了1.16,平均分类精度提高了3.42%,其表现出更好的约简性能。     

APT样本的有效网络特征筛选算法

在研究APT攻击的防御方案过程中，针对提取APT样本网络特征的维数过高问题，提出一种基于[k]-means++聚类的APT样本有效网络特征筛选算法。该算法的思路是首先基于聚类的思想将提取的原特征集划分成APT流量特征集与背景流量特征集，然后计算去掉某一维特征向量后聚类性能的变化程度，最后根据该结果评价该特征向量的区分度。其中，有效特征向量即为区分度超过设定阈值的特征向量。目的就是从提取的原特征集中筛选出有效特征，达成对特征的降维，从而降低后续威胁情报形成和部署检测工作的时空开销。实验结果表明，该算法具有一定可行性，针对此问题相比于其他筛选算法具有一定的优势。     

Discrimination Structure Complementarity‐Based Feature Selection

Feature selection is crucial, particularly for processing high‐dimensional data. Existing selection methods generally compute a discriminant value for a feature with respect to class variable to indicate its classification ability. However, a scalar value can hardly reveal the multifaceted classification abilities of a feature for different subproblems of a complicated multiclass problem. In view of this, we propose to select features based on discrimination structure complementarity. To this end, the classification abilities of a feature for different subproblems are evaluated individually. Consequently, a discrimination structure vector can be obtained to indicate if the feature is discriminative respectively for different subproblems. Based on discrimination structure, indispensable and dispensable features (ID‐features for short) are defined. In selection process, the ID‐features, which are complementary in discrimination structure to the selected ones, are selected. The proposed method tries to equally treat all subproblems and hence can avoid falling into the pitfall that the discriminative features for difficult subproblems are prone to be covered by the features for easy ones in multi‐class classification. Two algorithms are developed and compared with several feature selection methods using some open data sets. Experimental results demonstrate the effectiveness of the proposed method.     

Parameter identification of wiener models by multi-innovation algorithms

An output nonlinear Wiener system is rewritten as a standard least squares form by reconstructing the input-output items of its difference equation. Multi-innovation based stochastic gradient (MISG) algorithm and its derivate algorithms are introduced to formulate identification methods of Wiener models. In order to increase the convergence performance of stochastic gradient (SG) algorithm, the scalar innovation in SG algorithm is expanded to an innovation vector which contains more information about input-output data. Furthermore, a proper forgetting factor for SG algorithm is introduced to get a faster convergence rates. The comparisons of convergence performance and estimation errors of proposed algorithms are illustrated by two numerical simulation examples.     

Parallel Recurrence Solvers for Vector and SIMD Supercomputers

In this paper we present two algorithms for the parallel solution of first-order linear recurrences, We show that the algorithms can be used to efficiently solve both scalar and blocked versions of the problem on vector and SIMD architectures. The first algorithm is a parallel approach whose resulting code can be explicitly vectorized, making it suitable for efficient execution on vector architectures such as the Cray 2. The second algorithm is a modified recursive approach designed to reduce the communication overhead encountered in SIMD architectures such as the Connection Machine 2 (CM-2). We present the performance exhibited by the parallel algorithm implementations on the Cray 2 and CM-2 for both scalar and blocked versions of the recurrence problem.     

Nonparallel least square support vector machine for classification

Nonparallel support vector machine based on one optimization problem (NSVMOOP) aims at finding two nonparallel hyper-planes by maximizing the intersection angle of their normal vectors w₁ and w₂. As maximum intersection angle preserves both compactness and separation of data, NSVMOOP yields good forecasting accuracy. However, as it solves one large quadratic programming problem (QPP), it costs high running time. In order to improve its learning speed, a novel nonparallel least square support vector machine (NLSSVM) is proposed in this paper. NLSSVM solves a linear system of equations instead of solving one large QPP. As both intersection angle and least square version are applied on our NLSSVM, it performs better generalization performance than other algorithms. Experimental results on twenty benchmark datasets demonstrate its validity.     

基于AABB树的碰撞检测算法的内存优化

介绍了从存储空间角度来改进基于AABB树的碰撞检测算法的方法.根据有关三角形间快速相交测试算法和三角形与包围盒间的快速相交测试算法,略过包围盒间的相交测试,从叶节点结构里去掉包围盒信息,将叶节点从存储结构中删除.对一棵含有N个节点的 AABB 树而言,可以节约一半节点的内存空间.实验表明,利用 AABB 树叶节点的内存优化,减少了算法所需的内存空间且加快了算法的执行时间.