The core of smoothed particle hydrodynamics （SPH） is the nearest neighbor search subroutine. In this paper, a nearest neighbor search algorithm which is based on multiple background grids and support variable smooth...The core of smoothed particle hydrodynamics （SPH） is the nearest neighbor search subroutine. In this paper, a nearest neighbor search algorithm which is based on multiple background grids and support variable smooth length is introduced. Through tested on lid driven cavity flow, it is clear that this method can provide high accuracy. Analysis and experiments have been made on its parallelism, and the results show that this method has better parallelism and with adding processors its accuracy become higher, thus it achieves that efficiency grows in pace with accuracy.展开更多
This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteris...This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.展开更多
A fast encoding algorithm was presented which made full use of two characteristics of a vector, its sum and variance. In this paper, a vector was separated into two subvectors, one is the first half of the coordinates...A fast encoding algorithm was presented which made full use of two characteristics of a vector, its sum and variance. In this paper, a vector was separated into two subvectors, one is the first half of the coordinates and the other contains the remaining coordinates. Three inequalities based on the characteristics of the sums and variances of a vector and its two subvectors were introduced to reject those codewords which are impossible to be the nearest codeword. The simulation results show that the proposed algorithm is faster than the improved equal average eaual variance nearest neighbor search (EENNS) algorithm.展开更多
Nearest Neighbor （κNN） search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work...Nearest Neighbor （κNN） search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on κNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing κNN （κ≥ 1） search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPκNN and BFTκNN, which handle the κNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability.展开更多
Image matching refers to the process of matching two or more images obtained at different time,different sensors or different conditions through a large number of feature points in the image.At present,image matching ...Image matching refers to the process of matching two or more images obtained at different time,different sensors or different conditions through a large number of feature points in the image.At present,image matching is widely used in target recognition and tracking,indoor positioning and navigation.Local features missing,however,often occurs in color images taken in dark light,making the extracted feature points greatly reduced in number,so as to affect image matching and even fail the target recognition.An unsharp masking(USM)based denoising model is established and a local adaptive enhancement algorithm is proposed to achieve feature point compensation by strengthening local features of the dark image in order to increase amount of image information effectively.Fast library for approximate nearest neighbors(FLANN)and random sample consensus(RANSAC)are image matching algorithms.Experimental results show that the number of effective feature points obtained by the proposed algorithm from images in dark light environment is increased,and the accuracy of image matching can be improved obviously.展开更多
针对现有起重机路径规划效率低的问题,提出一种基于改进快速探索随机树(rapidly-exploring random tree,RRT)的起重机路径规划算法。将广义距离替代经典RRT中欧氏距离,解决多自由度(degree of freedom,DOF)下RRT中距离的定义不明确的问...针对现有起重机路径规划效率低的问题,提出一种基于改进快速探索随机树(rapidly-exploring random tree,RRT)的起重机路径规划算法。将广义距离替代经典RRT中欧氏距离,解决多自由度(degree of freedom,DOF)下RRT中距离的定义不明确的问题。基于降维概念的胞元法,将C构型空间(configuration space,C空间)划分为大小相等的单元格,解决经典RRT中最近邻搜索(nearest neighbor search,NNS)在计算时间和资源方面效率低的问题。实验结果表明:在相同实验条件下,改进的RRT算法比双向RRT算法计算时间减少89.5%,能提高计算时间效率和提升搜寻路径质量,具有一定的参考价值。展开更多
Product quantization is now considered as an effective approach to solve the approximate nearest neighbor(ANN)search.A collection of derivative algorithms have been developed.However,the current techniques ignore the ...Product quantization is now considered as an effective approach to solve the approximate nearest neighbor(ANN)search.A collection of derivative algorithms have been developed.However,the current techniques ignore the intrinsic high order structures of data,which usually contain helpful information for improving the computational precision.In this paper,aiming at the complex structure of high order data,we design an optimized technique,called optimized high order product quantization(O-HOPQ)for ANN search.In O-HOPQ,we incorporate the high order structures of the data into the process of designing a more effective subspace decomposition way.As a result,spatial adjacent elements in the high order data space are grouped into the same subspace.Then,O-HOPQ generates its spatial structured codebook,by optimizing the quantization distortion.Starting from the structured codebook,the global optimum quantizers can be obtained effectively and efficiently.Experimental results show that appropriate utilization of the potential information that exists in the complex structure of high order data will result in significant improvements to the performance of the product quantizers.Besides,the high order structure based approaches are effective to the scenario where the data have intrinsic complex structures.展开更多
针对当前发动机叶片损伤体积计算困难、误差较大的问题,提出一种基于点云的压气机叶片的损伤体积测量方法。首先,通过结构光扫描仪获取完整点云模型和损伤点云模型,配准分割得到缺损点云。其次,缺损点云经过姿态转换后与主成分轴对比分...针对当前发动机叶片损伤体积计算困难、误差较大的问题,提出一种基于点云的压气机叶片的损伤体积测量方法。首先,通过结构光扫描仪获取完整点云模型和损伤点云模型,配准分割得到缺损点云。其次,缺损点云经过姿态转换后与主成分轴对比分析、分层、切片、投影得到二维点云轮廓。最后,提出单向双次最近邻点搜索算法对二维点云的轮廓进行有序提取,使用坐标解析法求解投影面的面积,累加各层面积与切片间隔的乘积得到最终的体积。试验结果表明,提出的第一主成分轴方向切片体积计算效果更好,且轮廓提取算法对比凸包提取法、双向最近邻搜索和改进最近邻搜索算法(improved nearest point search,INPS)算法更准确,效率更高,与Geomagic软件结果相比平均相对误差不超过0.3%,证明了算法的高效性和有效性。展开更多
针对传统图像匹配算法计算量大、耗时长等缺陷,提出一种基于SURF(speeded up robust features)的图像特征点快速匹配算法.首先对图像采用SURF算法提取特征点;然后通过Haar小波变换确定特征点的主方向和特征点描述子,使用优化的最近邻搜...针对传统图像匹配算法计算量大、耗时长等缺陷,提出一种基于SURF(speeded up robust features)的图像特征点快速匹配算法.首先对图像采用SURF算法提取特征点;然后通过Haar小波变换确定特征点的主方向和特征点描述子,使用优化的最近邻搜索算法(best bin first,BBF)进行特征点匹配;最后根据实际需要选取相似度最高的前n对匹配点进行对比实验.实验结果表明:该算法鲁棒性强,速度快,匹配准确性高,具有较大的应用价值.展开更多
基金Project supported by the National Natural Science Foundation of China(Grant No.11002086)the Shanghai Leading Academic Discipline Project(Grant No.J50103)
文摘The core of smoothed particle hydrodynamics （SPH） is the nearest neighbor search subroutine. In this paper, a nearest neighbor search algorithm which is based on multiple background grids and support variable smooth length is introduced. Through tested on lid driven cavity flow, it is clear that this method can provide high accuracy. Analysis and experiments have been made on its parallelism, and the results show that this method has better parallelism and with adding processors its accuracy become higher, thus it achieves that efficiency grows in pace with accuracy.
文摘This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.
文摘A fast encoding algorithm was presented which made full use of two characteristics of a vector, its sum and variance. In this paper, a vector was separated into two subvectors, one is the first half of the coordinates and the other contains the remaining coordinates. Three inequalities based on the characteristics of the sums and variances of a vector and its two subvectors were introduced to reject those codewords which are impossible to be the nearest codeword. The simulation results show that the proposed algorithm is faster than the improved equal average eaual variance nearest neighbor search (EENNS) algorithm.
文摘Nearest Neighbor （κNN） search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on κNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing κNN （κ≥ 1） search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPκNN and BFTκNN, which handle the κNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability.
基金Supported by the National Natural Science Foundation of China(No.61771186)the Heilongjiang Provincial Natural Science Foundation of China(No.YQ2020F012)the University Nursing Program for Young Scholars with Creative Talents in Heilongjiang Province(No.UNPYSCT-2017125).
文摘Image matching refers to the process of matching two or more images obtained at different time,different sensors or different conditions through a large number of feature points in the image.At present,image matching is widely used in target recognition and tracking,indoor positioning and navigation.Local features missing,however,often occurs in color images taken in dark light,making the extracted feature points greatly reduced in number,so as to affect image matching and even fail the target recognition.An unsharp masking(USM)based denoising model is established and a local adaptive enhancement algorithm is proposed to achieve feature point compensation by strengthening local features of the dark image in order to increase amount of image information effectively.Fast library for approximate nearest neighbors(FLANN)and random sample consensus(RANSAC)are image matching algorithms.Experimental results show that the number of effective feature points obtained by the proposed algorithm from images in dark light environment is increased,and the accuracy of image matching can be improved obviously.
文摘针对现有起重机路径规划效率低的问题,提出一种基于改进快速探索随机树(rapidly-exploring random tree,RRT)的起重机路径规划算法。将广义距离替代经典RRT中欧氏距离,解决多自由度(degree of freedom,DOF)下RRT中距离的定义不明确的问题。基于降维概念的胞元法,将C构型空间(configuration space,C空间)划分为大小相等的单元格,解决经典RRT中最近邻搜索(nearest neighbor search,NNS)在计算时间和资源方面效率低的问题。实验结果表明:在相同实验条件下,改进的RRT算法比双向RRT算法计算时间减少89.5%,能提高计算时间效率和提升搜寻路径质量,具有一定的参考价值。
基金the National Natural Science Foundation of China(Grant No.61732011)Applied Fundamental Research Program of Qinghai Province(2019-ZJ-7017).
文摘Product quantization is now considered as an effective approach to solve the approximate nearest neighbor(ANN)search.A collection of derivative algorithms have been developed.However,the current techniques ignore the intrinsic high order structures of data,which usually contain helpful information for improving the computational precision.In this paper,aiming at the complex structure of high order data,we design an optimized technique,called optimized high order product quantization(O-HOPQ)for ANN search.In O-HOPQ,we incorporate the high order structures of the data into the process of designing a more effective subspace decomposition way.As a result,spatial adjacent elements in the high order data space are grouped into the same subspace.Then,O-HOPQ generates its spatial structured codebook,by optimizing the quantization distortion.Starting from the structured codebook,the global optimum quantizers can be obtained effectively and efficiently.Experimental results show that appropriate utilization of the potential information that exists in the complex structure of high order data will result in significant improvements to the performance of the product quantizers.Besides,the high order structure based approaches are effective to the scenario where the data have intrinsic complex structures.
文摘针对当前发动机叶片损伤体积计算困难、误差较大的问题,提出一种基于点云的压气机叶片的损伤体积测量方法。首先,通过结构光扫描仪获取完整点云模型和损伤点云模型,配准分割得到缺损点云。其次,缺损点云经过姿态转换后与主成分轴对比分析、分层、切片、投影得到二维点云轮廓。最后,提出单向双次最近邻点搜索算法对二维点云的轮廓进行有序提取,使用坐标解析法求解投影面的面积,累加各层面积与切片间隔的乘积得到最终的体积。试验结果表明,提出的第一主成分轴方向切片体积计算效果更好,且轮廓提取算法对比凸包提取法、双向最近邻搜索和改进最近邻搜索算法(improved nearest point search,INPS)算法更准确,效率更高,与Geomagic软件结果相比平均相对误差不超过0.3%,证明了算法的高效性和有效性。
文摘针对传统图像匹配算法计算量大、耗时长等缺陷,提出一种基于SURF(speeded up robust features)的图像特征点快速匹配算法.首先对图像采用SURF算法提取特征点;然后通过Haar小波变换确定特征点的主方向和特征点描述子,使用优化的最近邻搜索算法(best bin first,BBF)进行特征点匹配;最后根据实际需要选取相似度最高的前n对匹配点进行对比实验.实验结果表明:该算法鲁棒性强,速度快,匹配准确性高,具有较大的应用价值.
