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.展开更多
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.展开更多
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.展开更多
针对当前发动机叶片损伤体积计算困难、误差较大的问题,提出一种基于点云的压气机叶片的损伤体积测量方法。首先,通过结构光扫描仪获取完整点云模型和损伤点云模型,配准分割得到缺损点云。其次,缺损点云经过姿态转换后与主成分轴对比分...针对当前发动机叶片损伤体积计算困难、误差较大的问题,提出一种基于点云的压气机叶片的损伤体积测量方法。首先,通过结构光扫描仪获取完整点云模型和损伤点云模型,配准分割得到缺损点云。其次,缺损点云经过姿态转换后与主成分轴对比分析、分层、切片、投影得到二维点云轮廓。最后,提出单向双次最近邻点搜索算法对二维点云的轮廓进行有序提取,使用坐标解析法求解投影面的面积,累加各层面积与切片间隔的乘积得到最终的体积。试验结果表明,提出的第一主成分轴方向切片体积计算效果更好,且轮廓提取算法对比凸包提取法、双向最近邻搜索和改进最近邻搜索算法(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.
文摘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.
文摘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.
文摘针对当前发动机叶片损伤体积计算困难、误差较大的问题,提出一种基于点云的压气机叶片的损伤体积测量方法。首先,通过结构光扫描仪获取完整点云模型和损伤点云模型,配准分割得到缺损点云。其次,缺损点云经过姿态转换后与主成分轴对比分析、分层、切片、投影得到二维点云轮廓。最后,提出单向双次最近邻点搜索算法对二维点云的轮廓进行有序提取,使用坐标解析法求解投影面的面积,累加各层面积与切片间隔的乘积得到最终的体积。试验结果表明,提出的第一主成分轴方向切片体积计算效果更好,且轮廓提取算法对比凸包提取法、双向最近邻搜索和改进最近邻搜索算法(improved nearest point search,INPS)算法更准确,效率更高,与Geomagic软件结果相比平均相对误差不超过0.3%,证明了算法的高效性和有效性。
文摘针对传统图像匹配算法计算量大、耗时长等缺陷,提出一种基于SURF(speeded up robust features)的图像特征点快速匹配算法.首先对图像采用SURF算法提取特征点;然后通过Haar小波变换确定特征点的主方向和特征点描述子,使用优化的最近邻搜索算法(best bin first,BBF)进行特征点匹配;最后根据实际需要选取相似度最高的前n对匹配点进行对比实验.实验结果表明:该算法鲁棒性强,速度快,匹配准确性高,具有较大的应用价值.
