平面离散点集的边界搜索算法

进行有限元仿真首先要建立有限元网格模型。使用不含有任何拓扑信息的离散点集直接进行网格划分可以快速、精确地建立网格模型。使用铺路法进行网格剖分是从边界开始向内生成网格单元。该文提出一种使用搜索盒的搜索平面离散点集边界的算法。该方法将离散点分配到搜索盒中，遍历位于边界的搜索盒，将其中的点连接成边界点链表。该算法能正确地搜索包含有凹点、孔洞特征的离散点集的边界，具有较强的通用性。文中介绍了算法的基本思想，并给出算例。     

地形漫游中数据块调度算法研究

在LOD(level-of-detail)算法基础上,提出处理视点相关的交互式大规模地形数据的方法.包括:分块策略对规则网格进行区域分割;通过输入的数据点构建自顶向下的四叉树结构,划分成不同的块层次;在实时漫游过程中,根据视点z轴坐标值的变化导致块层次的改变,重新调入相应数据块构造地形网格,以及当视点x,y轴坐标改变时进行块调度.实验证明了该算法的有效性.     

基于射线投影的多视场深度像融合

首先确定匹配好深度像的最小轴对齐包围盒.通过盒面,沿着x,y,z 3个轴方向投射3个均匀分布的射线组,计算得到与所有深度像的交点,并通过Dexel结构来存储射线组与交点.加入距离和法向夹角2个判断依据来去掉重叠点,从而将多个视场深度像融合为完整的、无冗余的三维模型.实验结果表明,该方法误差小、速度快,而且简单有效.     

利用峰值线交替扫描法实现曲面消隐

科学可视化将数据和图形图像有机地结合起来，用图形图像直观地展示数据。要生成直观的三维图形，必须进行消隐。对形如z=f(x，y)函数关系的图形，由于网格结点高度z(i，j)的任意性以及规则网格纵横截面的交错性，消隐有时比较困难，需要研究曲面消隐，找出一套有效的消隐算法。在峰值线法(浮动水平线算法)消隐的基础上，提出了一种用于实现形如z=f(x，y)函数关系的图形消隐的峰值线交替扫描法，给出了实施步骤和实例。用该集成消隐方法可方便地实现矩形域上函数z=f(x，y)的数据显示。     

快速动态优先搜索树的实现及其应用

对形如（x1：x2,[-∞：y]）的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O（n）,插入、删除操作的时间复杂度为O（10gn）,搜索复杂度为O（logn＋k）。     

基于八叉树空间分割的k近邻搜索算法

以三维扫描得到的散乱点云为基础,提出了一种基于空间八叉树的快速k近邻搜索算法,通过对点集建立包围盒,利用八叉树记录分割过程,从而使近邻点的搜索只局限于采样点所在的包围盒及其周围的包围盒,并通过剪枝策略使搜索范围进一步缩小。大量真实数据的实验结果表明：该算法可以很好地提高近邻点的搜索速度。     

接触面的一致性三角形网格生成算法*

为了简化数值模拟中三角形网格模型之间的接触问题,设计了在接触面上生成一致性三角形网格的算法,基本步骤为构造网格拓扑关系、搜索重叠网格、完善重叠网格、拷贝网格、修补边界空隙。采用面向配对顶点的搜索方法、点投影的判定方法、基于边界环的孔洞搜索方法,准确地确定了接触区域,利用最短对角线的方法修补了边界空隙,较好地生成了一致性网格,并采用三轴分块排序表提高了效率。实验结果表明,该算法准确、高效地实现了接触面上网格的一致性。     

三维空间坐标的旋转算法

在进行三维空间图形的显示以及动画处理时,经常需要对图形进行旋转处理。旋转可分为绕坐标轴的旋转以及绕任意轴的旋转。三维空间中的坐标点(x,y,z)经过旋转后其坐标值变换为(x′,y′,z′)。本文讨论(x′,y′,z′)与(x,y,z)之间的坐标变换关系。     

基于八叉树空间分割的三维点云模型密写

针对三维点云模型的信息隐藏,提出一种基于八叉树空间分割的空域密写算法。对经过主成分分析后的三维点云模型建立包围盒,利用八叉树空间分割得到小体元并记录分割过程,通过顶点位移将信息嵌入到小体元内的不同空间位置。实验结果表明,该算法在提取信息时不需要原始模型数据,具有嵌入量高、失真度低的特点,能够抵抗旋转、平移、均匀缩放和顶点重排序攻击,适合于任意网格的三维模型信息隐藏。     

曲面网格修复中的一种快速搜索方法

提出了一种应用于搜索曲面网格修复过程中缺陷网格的边搜索算法。为了提高算法的效率,采用了升高维数处理问题的方法,将三维空间中的边转换为六维空间中的点建立了单元边二叉树。同时将搜索分为全局和局部搜索两个部分,全局搜索中将三维空间中判断包围盒相交转换为六维空间中判断点在区域内。从而将时间复杂度降为O(nlog n)。并通过编程,用实例证明该算法可准确、快速搜索出缺陷网格单元。     

基于动态网格k邻域搜索的激光点云精简算法

由非接触式扫描方法获得的点云数据存在大量的冗余点,为便于模型重构, 提出一种新的基于动态网格k邻域搜索的点云精简方法.首先,对点云进行k邻域搜索,在k邻域搜索过程中采用动态网格的方法快速寻找k邻域点;然后,根据数据点的k邻域计算点的曲率、点与邻域点法向夹角的平均值、点与邻域点的平均距离,并利用这3个参数定义特征判别参数和特征阈值,比较大小,对特征点进行提取;最后,利用包围盒法对非特征点进行二次精简,将精简后的点云与特征点拼接,实现精简目的.实验结果表明,所提出方法与其他k邻域搜索方法相比,提高了计算效率,并且将特征提取与二次精简方法相结合,既可保留模型的几何特征,又能避免空洞区域的产生,在精度和速度上都取得了较好的效果.     

面向高维数据集的近邻顺序查询方法

对顺序索引方法进行了研究,提出一种基于向量近似的高维顺序索引结构,该结构顺序访问部分文件就能完成k近邻查询。在查询过程中依据投影值来终止查询过程,依据距离来排除不匹配的数据。为进一步降低数据访问率,采用椭圆体聚类算法对数据集进行划分。新索引结构支持以多个顺序访问过程完成k近邻查询,能够同时降低查询过程中的I/O开销和CPU开销。在大型高维图像特征库上的实验表明,新的高维索引结构的查询性能优于其他高维索引方法。     

基于[k]-近邻与局部相似度的稀疏子空间聚类

为了获得结构更加合理的仿射矩阵,提出了一种基于[k]-近邻与局部相似度的稀疏子空间聚类算法。该算法首先计算每个点的[k]-近邻,并对其用[k]-近邻数据点进行线性表示,使仿射矩阵在整体稀疏的情况下保证局部的强线性关系。基于图论知识,利用数据的实际分布情况对仿射矩阵进行约束,使仿射矩阵进一步合理地等价于待进行谱聚类的相似矩阵。在人造数据集、随机生成的子空间数据集、图像数据集以及真实数据集上进行了实验,结果表明该算法是有效的。     

一种自适应k-最近邻算法的研究

针对传统k-最近邻算法(k-Nearest Neighbor, kNN)存在搜索慢的缺陷,提出了一种改进型的自适应k-最近邻算法。该方法在以测试样本点为中心的超球内进行搜索,对超球半径的生长进行采样,建立半径生长的BP神经网络模型,逼近半径变化函数,并用该函数指导超球体的生长。该方法有效地缩小了搜索范围,减少了超球体半径生长的试探次数,对处理稀疏数据集有明显的优越性。     

一种去除机载LiDAR航带重叠区冗余点云的方法

机载LiDAR系统在获取高密度地表点云的同时,也带来了数据冗余的问题,特别是在航带重叠区中尤为突出。旨在研究无完整航迹信息辅助下去除航带重叠点,提出了基于点云GPS时间直方图的去除航带重叠点的方法。该方法包括三个步骤:(1)建立点云的GPS时间直方图,并根据GPS时间直方图特点获取航带重叠区外包矩形以及外包矩形中的所有点云;(2)考虑到城市中高密度点云有助于建筑物的三维重建,通过滤波分类处理获取建筑物点并予以全部保留;(3)对重叠区中除建筑物点外的其他所有点进行格网数据组织并根据GPS时间直方图逐格网去除航带冗余点。实验结果表明,该方法能较好地保留建筑物点的同时高效去除航带重叠点且不依赖于航迹信息,提高了后续数据分析处理的效率。     

Efficient Near Neighbor Searching Using Multi-Indexes for Content-Based Multimedia Data Retrieval

Many content-based multimedia data retrieval problems can be transformed into the near neighbor searching problem in multidimensional feature space. An efficient near neighbor searching algorithm is needed when developing a multimedia database system. In this paper, we propose an approach to efficiently solve the near neighbor searching problem. In this approach, along each dimension an index is constructed according to the values of feature points of multimedia objects. A user can pose a content-based query by specifying a multimedia query example and a similarity measure. The specified query example will be transformed into a query point in the multi-dimensional feature space. The possible result points in each dimension are then retrieved by searching the value of the query point in the corresponding dimension. The sets of the possible result points are merged one by one by removing the points which are not within the query radius. The resultant points and their distances from the query point form the answer of the query. To show the efficiency of our approach, a series of experiments are performed to compare with the related approaches.     

多幅图像的自动拼接算法研究

提出一种基于特征点的多幅图像自动拼接算法。根据SIFT或SURF算法在图像的尺度空间中提取特征点,对特征点进行亚像素定位,并赋予主方向。根据特征点邻域信息分布计算得到特征向量后,基于k-d树进行最近邻和次最近邻搜索,利用最近邻特征点距离与次近邻特征点距离之比得到初始匹配点对。使用RANSAC（Random Sample Consensus）算法剔除错误匹配特征点对,同时对图像之间的变换参数进行鲁棒估计,使用多频带融合算法消除拼接痕迹。实验验证了该算法能够完成多幅图像的自动无缝拼接。     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

Point cloud simplification for the boundary preservation based on extracted four features

This paper proposes a simplification algorithm based on four feature parameters, aiming at solving the problem that the edge features cannot be retained due to the incompletely extracted sharp features during point cloud simplification. Firstly, K neighborhood searching is carried out for point cloud, and K neighborhood points are quickly found by a dynamic grid method. Then, four features including: the curvature of the point, the average of the normal angle of a point from a neighborhood point, the average distance between the point and the neighborhood point and the distance between the point and the center of gravity of the neighborhood point, are calculated according to the K neighborhood of the data point. The four parameters are used to define the feature discrimination parameters and feature thresholds, to compare the size and extract the feature points; finally, the non-feature points are reduced twice by the method of the bounding box, and the reduced point cloud and feature points are spliced to achieve the purpose of simplification. The experimental results show that the distance between the point and the center of gravity of the neighborhood has a great influence on the simplified model boundary, which effectively guarantees the accuracy of the simplified model.     

Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces

Range and k-nearest neighbor searching are core problems in pattern recognition. Given a database S of objects in a metric space M and a query object q in M, in a range searching problem the goal is to find the objects of S within some threshold distance to g, whereas in a k-nearest neighbor searching problem, the k elements of S closest to q must be produced. These problems can obviously be solved with a linear number of distance calculations, by comparing the query object against every object in the database. However, the goal is to solve such problems much faster. We combine and extend ideas from the M-tree, the multivantage point structure, and the FQ-tree to create a new structure in the "bisector tree" class, called the Antipole tree. Bisection is based on the proximity to an "Antipole" pair of elements generated by a suitable linear randomized tournament. The final winners a, b of such a tournament is far enough apart to approximate the diameter of the splitting set. If dist(a, b) is larger than the chosen cluster diameter threshold, then the cluster is split. The proposed data structure is an indexing scheme suitable for (exact and approximate) best match searching on generic metric spaces. The Antipole tree outperforms by a factor of approximately two existing structures such as list of clusters, M-trees, and others and, in many cases, it achieves better clustering properties.