|
|
论文:2018,Vol:36,Issue(5):988-994 |
|
|
引用本文： |
|
|
朱海龙, 梁斌, 张涛. 基于局部敏感哈希的导航星库快速搜索算法[J]. 西北工业大学学报 |
|
|
Zhu Hailong, Liang Bin, Zhang Tao. Fast Access for Star Catalog Based on Locality-Sensitive Hashing[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 基于局部敏感哈希的导航星库快速搜索算法 |
|
| 朱海龙, 梁斌, 张涛 |
|
| 清华大学 自动化系, 北京 100084 |
| 摘要: |
| 为提高星图识别过程中导航星库的搜索速度，提出基于局部敏感哈希的导航星库快速搜索算法。通过分析星图识别原理，以角距误差限为基准，量化星角距，将有序星点集星图识别模式转换为具有局部敏感特性的整数数组。然后引用STLport中整数哈希函数对整数数组进行散列，得到哈希值以及对应的存储有序星点集模式中心星点编号的集合。实验结果表明：提出算法的时间复杂度为O（1），优于直接遍历搜索、二分查找搜索以及k-vector搜索算法。考虑实际工程应用情况，可以选择星角距误差限为1个像素对应角距，角距数量，此时星图识别过程中哈希表的冲突率为0.74%，平均搜索次数为1.007 4，星图平均识别时间22 μs。 |
| 关键词:
星图识别
有序星点集
局部敏感哈希
星角距量化
角距误差限
仿真实验
|
|
| Fast Access for Star Catalog Based on Locality-Sensitive Hashing |
|
| Zhu Hailong, Liang Bin, Zhang Tao |
|
| Department of Automation, Tsinghua University, Beijing 100084, China |
| Abstract: |
| 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. |
| Key words:
star identification
ordered star points set
locality-sensitive hashing
quantized star angle distance
error limit of angle distance
design of experiments
|
|
| 收稿日期: 2017-09-18
修回日期:
|
| DOI: |
| 通讯作者:
Email： |
| 作者简介: 朱海龙(1987-),清华大学博士研究生,主要从事航天器姿态控制和导航研究。
|
|
| 相关功能 |
|
|
|
|
| 作者相关文章 |
|
| 朱海龙 在本刊中的所有文章 |
| 梁斌 在本刊中的所有文章 |
| 张涛 在本刊中的所有文章 |
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] 张广军. 星图识别[M]. 北京:国防工业出版社,2011 Zhang Guangjun. Star Identification[M]. Beijing, National Defense Industry Press, 2011(in Chinese)
[2] Junkins J L, White W, Tunrner D. Star Pattern Identification for Real Time Attitude Determination[J]. Journal of Guidance, Control and Dynamics, 1977, 25:251-270
[3] Mortari D, Samaan M A, Bruccoleri C. The Pyramid Star Identification Technique[J]. Navigation, 2004, 51(3):171-184
[4] Padgett C, Delgado K K. A Grid Algorithm for Star Identification[J]. IEEE Trans on Aerospace and Electronics Systems, 1997, 33(1):202-213
[5] Liebe C C. Pattern Recognition of Star Constellations for Spacecraft Application[J]. IEEE Aeronautics Electronic System Magazine, 1992, 7(6):34-41
[6] Mortari D, Neta B. K-Vector Range Searching Techniques[J]. Adv Astronaut Sci, 2000, 105:449-464
[7] Zhang Guangjun, Wei Xinguo, Jiang Jie. Full-Sky Autonomous Star Identification Based on Radial and Cyclic Features of Star Pattern[J]. Image Vision Computing, 2008, 26(7):891-897
[8] Jiang Jie, Ji Feilong, Yan Jinyun, et al. Redundant-Coded Radial and Neighbor Star Pattern Identification Algorithm[J]. IEEE Trans on Aerospace and Electronic Systems, 2015, 51(4):2811-2822
[9] 梁斌, 杨君, 宋靖雁,等. 一种快速搜索导航星表的方法[R]. CN101995248A, 2011 Liang Bin, Yang Jun, Song Jingyan, et al. A Fast Method for Guide Star Search[R]. CN101995248A, 2011(in Chinese)
[10] 张磊, 何昕, 魏仲慧,等. 三角形星图识别算法的改进[J]. 光学精密工程, 2010, 18(2):458-463 Zhang Lei, He Xi, Wei Zhonghui, et al. Modification of Triangle Identification Algorithm[J]. Opt Precision Eng, 2010, 18(2):458-463(in Chinese)
[11] 熊雪, 王庆. 基于多视场星敏感器的三角形星图识别方法[J]. 计算机测量与控制, 2014, 22(1):225-228 Xiong Xue, Wang Qing. An Improved Triangle Star Identification Method Based on Multi-FOV Star Sensor[J]. Computer Measurement & Control, 2014, 22(1):225-228(in Chinese)
[12] Rao G N, Bhat M S, Alex T K. Fast Access Method for Onboard Star Catalog[J]. Journal of Guidance Control & Dynamics, 2005, 28(5):1032-1037
[13] 郭磊. 纳型星敏感器星图识别算法优化研究[D]. 北京:中国科学院国家空间科学中心, 2017 Guo Lei. Research on Optimization of Star Pattern Recognition Algorithm for Nano Star Tracker[D]. Beijing, National Space Science Center, University of Chinese Academy of Sciences, 2017(in Chinese) |
|
|
|
|
|
|
|
