A nearest neighbor search algorithm of high-dimensional data based on sequential NPsim matrix

Problems existin similarity measurement and index tree construction which affect the performance of nearest neighbor search of high-dimensional data. The equidistance problem is solved using NPsim function to calculate similarity. And a sequential NPsim matrix is built to improve indexing performance. To sum up the above innovations,a nearest neighbor search algorithm of high-dimensional data based on sequential NPsim matrix is proposed in comparison with the nearest neighbor search algorithms based on KD-tree or SR-tree on Munsell spectral data set. Experimental results show that the proposed algorithm similarity is better than that of other algorithms and searching speed is more than thousands times of others. In addition,the slow construction speed of sequential NPsim matrix can be increased by using parallel computing.

结合K均值聚类和KD-Tree搜索的快速分形编码方法

利用部分失真搜索求解传统K均值聚类算法中的最近邻搜索问题,显著地减少了传统算法的乘法次数,从而提高了聚类速度;然后用改进后的聚类算法来加速分形编码:首先将定义域块聚类并为每个类建立一棵KD-Tree,编码时对每个值域块先后用部分失真搜索与近似最近邻搜索得到与其距离最近的若干KD-Tree及其上的若干最近邻,而其最优匹配块即由后者产生.实验结果表明,相对于全局搜索,该方法能大幅度地提高编码速度和较大地提高压缩比,而解码质量只有很小的下降;相对于同类方法,在相同压缩比下有更好的加速效果和解码质量.

基于KD-Tree搜索和SURF特征的图像匹配算法研究

针对图像匹配时进行特征检测和匹配的搜索时间长的问题,文章研究了基于KD-Tree搜索和SURF特征的图像匹配算法。该算法首先提取得到图像的SURF特征并生成特征描述向量,然后为这些特征描述向量建立KD-Tree索引,最后通过计算每个特征点的与其距离最近的若干个KD-Tree上的最近邻点,完成特征匹配工作。实验结果表明,与SIFT算法相比,SURF算法进行特征检测的速度要快2～3倍;与全局最近邻搜索相比,基于KD-Tree索引的近似最近邻搜索大大减少了计算量,较大地提高了SURF算法的匹配速度。

基于KD树的海量图像匹配技术

针对海量图像匹配的速度瓶颈问题,提出一种结合图像SIFT特征和KD树搜索的图像匹配算法,并建立了适应有限内存环境的大型KD树混合存储模式。实验结果表明,该方法能显著提高图像搜索速度和图像库的可扩展性,查准率和查全率也明显高于其他搜索方法。

散乱点云的孔洞识别和边界提取算法研究

针对逆向工程中已有孔洞识别算法执行效率低、孔洞边界点提取不完整等问题,提出一种新的基于KD树和K邻域搜索的点云孔洞识别及边界提取算法。该算法首先利用KD树建立散乱点云的拓扑关系。其次,计算点云密度、定义距离阈值作为判别参数,利用K邻域搜索计算每个点与其K个邻域点的距离,距离大于阈值的点即为边界点。再次,采用单坐标搜索法去除外边界,保留孔洞边界。最后,利用边界追踪算法获取完整的孔洞边界点。以涡轮叶片和挖掘机斗齿为研究对象,对点云上的自然孔洞利用该算法进行识别。结果表明,该算法能够快速地识别出散乱点云中孔洞,并能完整地提取出孔洞边界点,实用性强。

基于最近邻搜索耦合近邻损耗聚类的图像伪造检测算法

目的为了解决当前图像伪造检测算法在对图像进行伪造检测时,主要依靠全局搜索的方式来完成特征点匹配,导致其检测效率较低,且在对复杂伪造图像进行检测时,易出现检测精度不高和检测错误的不足。方法提出基于最近邻搜索耦合近邻损耗聚类的图像伪造检测算法。首先引入积分图像的方法,对图像进行预处理,借助Hessian矩阵行列式来提取特征点。利用特征点构建圆形区域,通过求取圆形区域内Haar小波响应获取特征点的特征描述符。然后通过特征描述符建立KD树索引,利用最近邻搜索方法代替SURF中全局搜索的方法,对SURF进行改进,完成特征点的匹配。最后,利用特征点间的近邻关系求取近邻函数值,通过近邻函数值对特征点进行聚类,完成图像的伪造检测。结果实验结果显示,与当前图像伪造检测算法相比,所提算法具有更高的检测效率以及更高的检测正确度。结论所提算法具备较高的检测精度,在印刷防伪与信息安全等领域具有较好的应用价值。

基于改进SURF的图像配准关键算法研究

针对图像特征匹配算法维数高,实时性低的缺陷,研究了SURF特征匹配算法,并对其进行了改进。首先在图像的尺度空间中提取SURF特征点,并生成扩展的特征描述向量。然后建立KD-Tree特征结构,采用BBF查询机制进行最近邻查询实现特征点快速匹配。实验结果表明,SURF算法进行特征检测的时间是SIFT算法的1/3;使用BBF进行特征匹配,匹配速度提高了2—3倍。

Rao-Blackwellized滤波器实现机器人同时定位和地图创建

为了实现移动机器人仅依靠单目视觉和里程计创建可靠地图,本文提出了基于Rao-Blackwellized粒子滤波器的同时定位和地图创建方法.文中建立了鲁棒的运动模型和感知模型;通过有效的尺度不变特征变换方法提取环境特征,并采用基于KD-Tree的高维特征点最近邻快速搜索算法实现特征匹配;通过对匹配对的三维重建创建了密集的空间三维自然路标.实际实验表明本文方法能创建较高精度的地图.

基于三维激光雷达和反光柱的机器人定位

针对机器人在空旷缺少特征信息环境下,二维激光雷达的测距范围有限,且缺少高度信息,机器人定位精度不高的问题。提出了一种三维激光雷达和反光柱耦合定位算法。该算法利用激光雷达的反射强度信息对反光柱进行点云分割,采用ALOAM算法构建反光柱地图,利用曲率对每一帧激光进行特征提取,通过构建KD树最近邻域搜索和反光柱点云地图实现帧到地图的匹配,再通过列文伯格非线性优化,求解机器人的位姿。该算法分别在仿真和真实环境中进行了静态和动态定位实验测试,实验结果表明反光柱定位系统定位精度较高,定位稳定性较好。

基于三维激光点云的零件表面缺陷检测

为了获取零件表面缺陷的精确尺寸,提出了一种基于三维激光点云的零件表面缺陷检测方法。首先使用三维激光测量仪对受损零件进行三维测绘,对测得的原始点云经过离群点去除、RANSAC平面分割等操作后得到零件点云。通过基于SAC-IA的粗配准和基于Huber损失函数优化的ICP精确配准算法,将缺陷零件的点云和完整零件的点云(从CATIA中导出)进行配准,使2个点云对齐。最后利用kd-tree加速的最邻近查找算法得出零件缺陷部位点云。分别使用了含破洞、凹陷的零件验证算法的有效性。实验结果表明:论文提出的方法对零件表面缺陷的3D尺寸提取精准。为后续开展零件修复工作打下良好的基础。