Issue |
JNWPU
Volume 36, Number 5, October 2018
|
|
---|---|---|
Page(s) | 988 - 994 | |
DOI | https://doi.org/10.1051/jnwpu/2018365988 | |
Published online | 17 December 2018 |
Fast Access for Star Catalog Based on Locality-Sensitive Hashing
基于局部敏感哈希的导航星库快速搜索算法
Department of Automation, Tsinghua University, Beijing
100084, China
Received:
18
September
2017
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.
摘要
为提高星图识别过程中导航星库的搜索速度,提出基于局部敏感哈希的导航星库快速搜索算法。通过分析星图识别原理,以角距误差限为基准,量化星角距,将有序星点集星图识别模式转换为具有局部敏感特性的整数数组。然后引用STLport中整数哈希函数对整数数组进行散列,得到哈希值以及对应的存储有序星点集模式中心星点编号的集合。实验结果表明:提出算法的时间复杂度为O(1),优于直接遍历搜索、二分查找搜索以及k-vector搜索算法。考虑实际工程应用情况,可以选择星角距误差限为1个像素对应角距,角距数量,此时星图识别过程中哈希表的冲突率为0.74%,平均搜索次数为1.007 4,星图平均识别时间22 μs。
Key words: star identification / ordered star points set / locality-sensitive hashing / quantized star angle distance / error limit of angle distance / design of experiments
关键字 : 星图识别 / 有序星点集 / 局部敏感哈希 / 星角距量化 / 角距误差限 / 仿真实验
© 2018 Journal of Northwestern Polytechnical University. All rights reserved.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.