基于Quaternary编码的球面三角格网邻近搜索算法

分析了球面Quaternary编码的特点,给出了三角格网方向判断的规则,并对该算法与Bartholdi邻近搜索算法的时间复杂度进行了对比。结果表明,分解算法的平均时间耗时量约是Bartholdi邻近搜索算法的23.66%。

基于空间邻近搜索的移动轨迹相对时间模式挖掘方法

针对传统移动轨迹模式挖掘方法挖掘速度慢、占用最大内存大的问题,提出一种基于空间邻近搜索的移动轨迹相对时间模式挖掘方法。该方法包括5个阶段:1)对移动轨迹数据进行时空划分,并基于移动轨迹数据与时空格的匹配得到移动轨迹数据对应的时空格序列。2)扫描所有的时空格序列数据得到空间网格集合,并通过空间网格与时空格序列的包含运算得到所有的频繁空间网格。3)频繁空间网格转变为长度为1的频繁相对时间模式。4)基于空间邻近搜索的方式进行模式增长,得到以频繁空间网格为单元的候选相对时间模式,并通过相对时间模式与时空格序列的匹配运算,计算相对时间模式的支持度。5)基于设定的支持度阈值,得到所有频繁的相对时间模式。实验结果表明:所提方法由于采用了基于空间邻近搜索的方式进行模式扩展,大幅减小候选相对时间模式的搜索范围。与传统方法相比,所提方法具有挖掘速度快、占用最大内存少的优点。另外,方法在运行时间上具有更好的稳定性和可扩展性,而在占用最大内存上的稳定性与可扩展性与传统方法基本相近。该方法有助于移动轨迹模式挖掘方法提升挖掘速度、减少占用最大内存。

基于简单最邻近搜索算法的高维特征索引

研究了220 kV/330 kV高压带电清扫机器人的绝缘瓷瓶视觉识别系统中的高维特征索引问题.该系统采用了基于局部尺度不变性特征的方法,在生成匹配假设的过程中,尝试将简单最邻近搜索算法用于高维特征的索引.在离线阶段,对给定向量集合中每个向量的每一维进行排序,生成排序的数据结构.在线搜索阶段:①对排序数据结构的第一维确定位于边界条件内的所有向量,构成候选队列;②依次检查候选队列中向量的其他维,剔除不满足边界条件的向量;③采用穷举法寻找与查询向量最邻近的向量.比较了简单最邻近搜索算法和k-d树算法.实验结果证明,简单最邻近搜索算法用于具有更强的边界约束,通过选择合适的边界条件能够获得更高的运算效率.该算法能广泛用于基于高维特征的物体识别和定位.

基于覆盖树的可扩展邻近搜索方法

针对邻近搜索技术受限于网络协议的支持以及存在空间嵌入误差的问题,提出一种基于覆盖树的可扩展邻近搜索方法CPS,包括覆盖树构建与维护协议和k近邻搜索算法两部分。节点自主计算自身所处层次,构造一棵层次化树。邻居维护协议负责维护覆盖树结构,确保其适应动态的网络环境。k近邻搜索算法通过对覆盖树剪枝,构造各层候选节点集合,提高搜索效率。实验结果表明,CPS的搜索精度优于典型的邻近搜索方法Tiers。

基于双边最邻近搜索的光条中心线提取方法

线激光三维扫描系统中,灰度重心法作为光条中心线提取常用算法,具有速度快,计算简单等特点,为提高灰度重心法定位精度,往往需要计算中心线局部法线方向,而现有局部法线计算方法引入大量复杂计算,不利于算法整体性能提升。为此,提出光条双边最邻近搜索方法,实现简单、快速的局部法向计算。该方法先通过光条梯度局部极大值获取光条双边缘;再对左右双边缘采用最邻近搜索算法快速获取局部法向;最后,根据局部法向逐行进行灰度重心法计算,获取各行激光中心点亚像素坐标。实验结果显示,该方法中心线提取均方根误差为0.00496 pixel,相较于传统的Steger算法以及灰度重心法,不仅具有更好的中心线提取精度,同时也具备优秀的提取速度。

一种改进的体素化邻近点搜索算法

针对多传感器同时建图与定位SLAM(simultaneous localization and mapping)系统,在室外大面积特征过多环境中,因为特征不匹配而导致的精度误差、系统缺失鲁棒性等问题,提出一种改进的体素化邻近点搜索(voxelized generalized iterative closest point)算法。首先利用激光-惯导-视觉各传感器分别对不同环境感知可以优势互补的特点,提出一种特征可信性筛选方法,给予系统一个精确的初始猜测。然后将视觉特征子集通过深度信息与点云数据关联,通过加入视觉约束筛选可观测性高的体素化的目标点云群,在减少计算复杂度的情况下,使定位建图更加精确。仿真实验证明,当运用此算法的多传感器融合SLAM系统在特征点云较多的环境中建图时,与LVI-SAM系统对比定位误差减少12.335%;在运行线速度超过10 m/s时,提升了系统的鲁棒性,具有较强的可行性。

球面退化四叉树格网单元的邻近搜索算法

为了克服传统经纬度格网与全球四元三角网(quaternary triangular mesh,QTM)存在的不足,提出了一种球面退化四叉树格网(degenerate quadtree grid,DQG)的剖分方法及相应的格网编码方案,分析了不同位置格网的邻近特征,给出了一套详细的DQG单元邻近搜索算法,并进行了相关实验与对比分析。结果表明,该算法的搜索速度比传统QTM格网的Bartholdi搜索算法和分解搜索算法分别提高了约100倍和30倍。

一种球面退化四叉树格网的多层次邻近搜索算法

格网单元的邻近搜索是聚类、索引、查询等空间操作的基础,但现有方法大都局限于单个剖分层次,无法直接满足全球多尺度数据集成查询和操作的应用需求。在球面退化四叉树格网（DQG）模型基础上,提出了一种基于多层次格网的邻近搜索算法。首先采用视点相关技术建立DQG格网的多层次模型,然后引入细分评价函数确定格网单元的邻近单元层次,设计并实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法,最后与单层次邻近搜索算法进行了对比实验。结果表明,搜索同一区域,该算法的耗时成本约为DQG单层次搜索算法的1/3（层次为11）;将该算法用于全球地形实时可视化表达,平均刷新帧率达到60帧/s。

球面四元三角网修正方向编码的邻近搜索算法

针对球体测地线八叉树网格(SGOG)采用的修正方向编码邻近关系复杂的问题,该文提出了其邻近搜索算法。先对修正方向编码特征进行分析,发现在递归剖分过程中,子三角形(剖分层次n≥3)相对于其二级父三角形的位置是固定的,随后给出了三角网格方向判断及邻近规则。结果表明,本文算法的效率大约为传统球面四元三角网(QTM)Bartholdi搜索算法的6倍。本研究对SGOG在时空大数据管理与建模中的应用具有重要意义。

规则格网内插中的J邻近点快速搜索算法

引入KD-Tree的二维索引结构,提出一种基于优先队列的改进J邻近点搜索策略,针对规则格网内插中的固定点数和固定距离这两种搜索原则,分别设计其J邻近点搜索算法,并以反距离加权法为例实现了整个内插过程。实验表明,该算法具有较高的运行效率,并在大数据量的情况下性能更优。

基于CUDA的邻近粒子搜索算法研究

在粒子方法中,运用邻近粒子搜索算法可以快速获取每个粒子的邻近粒子信息。由于粒子方法模拟一个体系的行为所采用的粒子数据是十分庞大的,对计算机的运算速度提出了挑战。研究了GPU的计算能力和CUDA开发环境,利用GPU的并行多线程处理技术,提出了一种并行邻近粒子搜索算法。实验结果表明,基于CUDA的并行邻近粒子搜索算法,加快了邻近粒子搜索过程,显著地减少了计算时间,成功实现了硬件加速,可获取290以上的加速比,对大规模粒子系统呈现出高效的处理能力。

一种改进的邻近粒子搜索算法

为提高SPH方法中邻近粒子的搜索效率,采用条形Point-In-Box(PIB)搜索法和邻域区域相关搜索法交替执行机制,实现了一种邻近粒子融合搜索算法.实验中,分别用融合搜索法的SPH方法和条形PIB搜索法的SPH方法对溃坝现象进行了模拟,并对条形PIB搜索法、邻域相关搜索法和融合搜索法在搜索时间和准确率上进行了比较,证明了融合算法的可行性和高效性.

无结构码的快速最邻近模式搜索

本文提出二进制超平面试验(BHT)方法,使最邻近模式搜索复杂性随比特率线性增长,远低于传统的随比特率及空问维数均指数增长的 EFS 方法的搜索复杂性.BHT 方法已成功地应用于实时语音波形矢量量化编码.

基于GPU的邻近粒子搜索优化算法

为提高邻近粒子的搜索速度,基于硬件图形处理器(GPU),采用SPH方法中交替使用邻域区域相关搜索法和条形Point-In-Box(PIB)搜索法的机制,实现一种基于GPU的邻近粒子融合搜索算法。利用该方法对典型的流体溃坝现象进行模拟,在搜索效率和搜索准确率方面,与基于CPU的融合搜索法和基于GPU的多维树搜索法进行对比。实验结果表明,该算法的性能随着粒子数的增多,表现更优。

基于SURF和快速近似最近邻搜索的图像匹配算法

针对高维特征向量存在的最近邻匹配正确率低的问题,提出了一种基于SURF和快速近似最近邻搜索的图像匹配算法。首先用Fast-Hessian检测子进行特征点检测,并生成SURF特征描述向量;然后通过快速近似最近邻搜索算法得到初匹配点对,再对得出的单向匹配结果进行双向匹配;最后采用鲁棒性较好的PROSAC算法进一步剔除误匹配点对。实验证明了该算法不仅提高了SURF算法匹配的正确率,还保证了算法的实时性。

基于空间划分的海量数据K邻近新算法

逆向工程中,对测量数据的处理首先要建立数据点之间的拓朴结构,这通常通过计算点的K邻近来实现.文中在分析现有算法的基础上,提出了一种新的基于空间划分的海量数据K邻近算法.该算法综合考虑了点云密度、点云数量以及K值对小立方体栅格边长的影响,通过确定合适的小立方体栅格边长以及排除不包含点云数据的小立方体栅格来确定邻近点最佳搜索范围,从而提高了搜索速度,保证了搜索结果的正确性.最后通过逆向软件的二次开发编程验证了算法.

一种基于平均垄间距的视觉导航垄线识别算法

通过对经过灰度二值化处理后的田间农作物图像进行基于平均垄间距行向连续区域中点提取(行提取)和基于平均垄间距列向最近邻搜索目标点提取(列提取),实现农作物图像垄行结构的识别。行提取为基于垄间距一致性特点,通过连续区域聚类求中点以消除大面积杂草等噪声影响;列提取为基于垄列向的连续性,在行提取的基础上对所得中点在垄间距范围进行最近邻搜索,以减少非垄孤立点干扰因素的影响。通过最小二乘法拟合获得各垄线段,以克服失垄、断垄等田间自然光照条件下对垄线图像识别的影响。实验1采用30幅单垄图像,垄行方向角平均误差为-0.66°;实验2采用20幅多垄图像,垄行方向角平均误差为1.31°,最长时耗约为6ms,满足田间视觉导航系统实时性、准确性要求。

基于菱形块的全球离散格网层次建模

在球面四元三角格网(QTM)基础上,以“菱形”块(Diamonds)作为基本单元,构建了全球离散格网的分块层次模型.用线性四叉树成熟的Morton编码作为关键字来标识菱形块,发展了具有固定方向(fixed orientation)的“块”层次编码技术及邻近搜索算法.利用地址码的邻近特征,建立了块层次之间、块与格网之间和格网层次之间的关联关系,并设计了全球多层次“菱形块”的层次操作和动态调用方法.研究结果表明:该模型在保持原有精度基础上,几何结构更简单;既避免了传统算法各层次间数据存储冗余问题,又使邻近搜索、数据更新和显示操作变得方便易行.

基于球面QTM的大范围有源淹没算法研究

面对海平面上升后沿海区域大范围淹没模拟的应用需求,提出了一种基于球面QTM的大范围有源淹没算法,首先构建了研究区域的QTM三角格网集,并利用海陆分离的思想确定了初始淹没单元;然后基于QTM的12邻近搜索设计了面向多目标三角格网的淹没范围扩张方法,将初始淹没单元递归扩张得到最终的淹没范围;最后应用Visual C#语言及Microsoft Direct X三维图形接口设计开发了相应的试验原型系统,并利用天地图高分辨率影像和SRTM地形数据对试验区域进行了海平面上升后的大范围淹没模拟试验。结果表明,该算法具有较好的实用性,可以有效地对海平面上升后的大区域范围进行动态地淹没模拟,对辅助防灾减灾具有一定意义。

一种海陆部水域面DEM自动填平方法研究

本文针对海陆部水域面区域格网点高程填平对数字高程模型（DEM）生成的影响，分析归纳了海陆部水域面DEM高程填平应遵循的相关规则，提出了一种海陆部水域面DEM自动填平方法。介绍了该方法的总体思路，并利用该方法进行海陆部水域面自动选取、水域面高程自动核查和水域面格网点高程值自动赋值填平实验。实验结果表明，该方法简洁实用，生成的DEM符合实际地表形态。