基于局部敏感哈希的导航星库快速搜索算法  

Fast Access for Star Catalog Based on Locality-Sensitive Hashing

作　　者：朱海龙[1] 梁斌[1] 张涛[1] Zhu Hailong;Liang Bin;Zhang Tao(Department of Automation,Tsinghua University,Beijing 100084,China)

机构地区：[1]清华大学自动化系,北京100084

出　　处：《西北工业大学学报》2018年第5期988-994,共7页Journal of Northwestern Polytechnical University

摘　　要：为提高星图识别过程中导航星库的搜索速度,提出基于局部敏感哈希的导航星库快速搜索算法。通过分析星图识别原理,以角距误差限为基准,量化星角距,将有序星点集星图识别模式转换为具有局部敏感特性的整数数组。然后引用STLport中整数哈希函数对整数数组进行散列,得到哈希值以及对应的存储有序星点集模式中心星点编号的集合。实验结果表明:提出算法的时间复杂度为O(1),优于直接遍历搜索、二分查找搜索以及k-vector搜索算法。考虑实际工程应用情况,可以选择星角距误差限为1个像素对应角距,角距数量,此时星图识别过程中哈希表的冲突率为0.74%,平均搜索次数为1.007 4,星图平均识别时间22μs。In order to improve the access speed and robustness of star catalog database during star identification,an algorithm based on locality-sensitive hashing is proposed.First,according to principle of star identification,the angle distances are quantified on the basis of angle distance error limit,and the order star set pattern is transformed into an array of integers,which has locally sensitive hash characteristics.Then key of hash obtain by hashing the array of integers with Stlport,and the value of hashing is a set of central star number in the ordered star point set pattern.Numerical simulation results indicate that the time complexity of proposed algorithm is O(1),which is much better than direct search,binary search and k-vector search technology.In addition,the proposed algorithm is robustness due to the affect is not significant as the performance influenced by angle distance error limit.Considering practical application,the error limit of angle distance could be chose as 1 pixel,the number of quantified angle distances could be chosen as 3.Under this condition,the collision rate in hashing table is 0.74%,the average searching time is 1.007 4 and the average consuming time is 22μs during star identification.

关 键 词：星图识别 有序星点集 局部敏感哈希 星角距量化 角距误差限 仿真实验 

分 类 号：V249.323[航空宇航科学与技术—飞行器设计]