积分商城

最新搜索： RFID SDK 应用分析精粹 编译软件 JESD79-3F 变送器
您现在的位置是：首页 > 技术资料 > 基于局部敏感哈希的导航星库快速搜索算法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

更新时间：2019-12-30 12:57:50 大小：2M 上传用户：IC老兵查看TA发布的资源 标签：星图识别快速搜索算法 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

为提高星图识别过程中导航星库的搜索速度,提出基于局部敏感哈希的导航星库快速搜索算法。通过分析星图识别原理,以角距误差限为基准,量化星角距,将有序星点集星图识别模式转换为具有局部敏感特性的整数数组。然后引用STLport中整数哈希函数对整数数组进行散列,得到哈希值以及对应的存储有序星点集模式中心星点编号的集合。实验结果表明:提出算法的时间复杂度为O(1),优于直接遍历搜索、二分查找搜索以及k-vector搜索算法。考虑实际工程应用情况,可以选择星角距误差限为1个像素对应角距,角距数量,此时星图识别过程中哈希表的冲突率为0.74%,平均搜索次数为1.007 4,星图平均识别时间22μs。


部分文件列表

文件名 大小
1577681863基于局部敏感哈希的导航星库快速搜索算法.pdf 2M

【关注视频号领20积分】   【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）
2018  
10  
Oct． 2018  
Vol．36 No．5  
年
月
西 北 工 业 大 学 学 报  
Journal of Northwestern Polytechnical University  
36  
5
期
第
卷第  
基于局部敏感哈希的导航星库快速搜索算法  
， ，  
朱海龙 梁斌 张涛  
(
，
清华大学 自动化系 北京  
100084)  
: ，  
要 为提高星图识别过程中导航星库的搜索速度 提出基于局部敏感哈希的导航星库快速搜索算  
摘
。 ， ， ，  
法 通过分析星图识别原理 以角距误差限为基准 量化星角距 将有序星点集星图识别模式转换为  
。
STLport  
，
中整数哈希函数对整数数组进行散列 得到哈希值  
具有局部敏感特性的整数数组 然后引用  
O
以及对应的存储有序星点集模式中心星点编号的集合 实验结果表明 提出算法的时间复杂度为  
。
:
( 1) ， 、  
优于直接遍历搜索 二分查找搜索以及  
k-vector  
。 ，  
搜索算法 考虑实际工程应用情况 可以选择星  
1 ， ，  
角距误差限为 个像素对应角距 角距数量 此时星图识别过程中哈希表的冲突率为  
0．74%，  
平均搜  
1．007 4，  
星图平均识别时间  
22 s。  
μ
索次数为  
: ; ; ; ; ;  
词 星图识别 有序星点集 局部敏感哈希 星角距量化 角距误差限 仿真实验  
关
键
: V249．323 : A : 1000-2758( 2018) 05-0988-07  
文献标志码 文章编号  
中图分类号  
、
星敏感器具有姿态测量精度高 自主工作能力  
，
建立星图识别数据库 通过直接遍历搜索进行星图  
［5］  
，
强和可靠性高等优点 已经成为各类航天器首选姿  
。 ，  
由于三角形识别模式维度较低 在导航星  
识别  
数量多的情况下会导致误匹配率高和识别速度慢  
，Mortari  
。
。 ，  
态测量设备 根据工作场景不同 星敏感器的工作  
2
模式可以分为全天球自主工作模式和星跟踪模式  
为提 高 星 图 识 别 的 鲁 棒 性  
等 人 提 出  
［1］  
。
，
在初次进入工作状态或者故障恢复后 星敏  
Pyramid  
，
星图识别算法 通过增加一个角距来判断  
种
，
感器没有任何先验姿态信息 进入全天球自主工作  
。
星图识 别 的 唯 一 性 为 了 提 高 星 图 识 别 速 度  
，
。 ，  
模式 此时星敏感器通过其光学系统获取星图 计  
Mortari ， k-vector  
等人对星角距升序排列 提出  
区域  
［6］  
， ，  
算出星点在星图中位置 然后构造出识别模式 并且  
，
搜索算法  
该算法的搜索速度比遍历查找算法提  
，
10～50  
。
张广军等人提出基于径向和环向  
与导航星数据库中存储的识别模式进行搜索匹配  
高了  
特征的星图识别算法  
个像素的情况下识别成功率达到  
倍
［7］  
，
识别出星图中的导航星 进而确定航天器瞬时姿态  
，
1
该算法在星点位置误差  
。 ，  
信息 在得到先验姿态信息后 星敏感器就进入星  
97．57%，  
并且通过  
，
跟踪工作模式 此时星敏感器可以利用在全天球自  
， 。  
线性数据库搜索方法 提高了星图识别速度 江洁  
［8］  
，
主工作模式下获取的先验姿态信息和航天器的运动  
等人对张广军等人提出算法进行改进  
提出冗余  
， ，  
径向和环向特征识别模式 通过冗余编码方式 降低  
， 。 ，  
方程 快速更新航天器姿态信息 可以看出 如何在  
，
星等和星点位置噪声对星图识别的影响 但是在识  
全天球自主工作模式下准确快速地识别出导航星是  
。
别速度方面略慢于张广军等人提出的算法 杨君等  
。
星敏感器稳定可靠工作的关键  
，
目前 已经有许多全天球自主工作模式下的星  
2
人通过 级压缩技术将导航星分布的二维数组压缩  
Hash  
映射实现导航星表快速  
，
图识 别 算 法 提 出 典 型 的 算 法 有 三 角 形 识 别 算  
，
成一维数组 然后建立  
［2］  
［3］  
［4］  
、Pyramid  
。
， ，  
搜索 实现了导航星表的无冗余存储 提高导航星的  
法
识别算法 和栅格识别算法  
等
［9］  
，
在这些算法及其改进算法中 导航星数据库的搜索  
。
张磊等人在改进三角形识别算法过  
搜索速度  
。Liebe  
， ，  
程中 用哈希方法散列星角距和相对星等差 提高了  
速度是决定星图识别算法效率的核心因素  
［10］  
" " ，  
提出的三角形算法中选用 边角边 识别模式 直接  
。
熊雪等人在研究多视场星图识别技  
识别速度  
: 2017-09-18  
收稿日期  
:
作者简介 朱海龙  
( 1987—) ， ， 。  
清华大学博士研究生 主要从事航天器姿态控制和导航研究  
5
， :  
朱海龙 等 基于局部敏感哈希的导航星库快速搜索算法  
第
期
·989·  
，
术中 利用哈希查找的方法快速访问分块存储的星  
。
特征  
［11］  
，
对角距 识别速度提高了  
11  
。Rao  
等人  
倍左右  
，
利用星角距值在坐标系 轴的投影建立哈希函数 进  
［12］  
。
而提高星角距数据库的搜索速度  
郭磊利用双  
，
哈希表方式存储和访问导航星数据库 利用拉链法  
， ，  
处理冲突 降低哈希表冲突率 并提高了搜索速  
［13］  
。
，
利用哈希表建立和访问导航星数据库 时间  
度
O( 1) ， 、  
明显优于遍历查找方法 二  
复杂度能够达到  
k-vector  
，
分查找方法和  
时间复杂度分别是  
是哈希搜索算法是一种典型的空间换时间的方法  
区域搜索方法 这些方法的  
O( n) ，O( log( n) ) O( k) 。  
和
但
，
导航星数据库的存储量会随着访问时间的降低而快  
。
速增加 因此如何在提高导航星数据库搜索速度的  
1
图
有序星点集星图识别模式  
，
同时尽可能降低导航星数据库的存储容量 是本文  
。
主要的研究方向  
s ， s ，  
在选定主星点 后 利用 近邻算法 选取  
0
0
，
由于星图成像存在各种噪声 在已有的星图识  
s ( s  
0
)
小于星敏感器视场角的一半 范围内到星点  
s
0
0
， “ ”  
别算法中 通常是建立 一对一 的星图识别模式数  
s
，
s
s
最近的 颗星 选择 颗星中距离星点 最近的星  
0
为参考星点  
，
0
0
，
据库 即在星图识别数据库中有且仅有一个识别模  
s 。  
0
s
，
为起点 按照顺时针顺序对  
s
以
0
0
。 ，  
式与星图中构造的识别模式对应匹配 因此 这种  
s
s 。  
对
0
颗星排序 就可以得到星点 的有序星点集  
0
，
方式建立的数据库在受到噪声影响时 不仅影响星  
s
s ，  
中每个星点 都可以用星点之间的角距表示  
0
于
0
， 。  
图识别成功率 还影响星图识别速度 本文选用有  
s 。  
0
:
可以分为以下几种情况  
其特征  
，
序星点集作为星图识别模式 考虑角距误差对星图  
= =  
{ e } ( i 1，…，k) ;  
0，i  
1)  
s
主星点 的特征为  
0
F
0
，
识别速度的影响 提出基于局部敏感哈希的快速星  
=
{ e ，e ，e } ;  
0，1  
2)  
s
参考星点 的特征为  
1
F
1
k，1  
1，2  
，
图识别算法 以角距误差限为基准对星图识别数据  
－
=
{ e  
3)  
s ( 2  
i
i
≤ ≤  
k
1) F  
的特征为  
，
－
i 1，i  
星点  
i
，
库中星角距进行量化 建立实际角距与待匹配角距  
e ，e  
0，i  
}
+
i，i 1  
，
之间的映射关系 利用整数哈希函数散列得到的映  
=
4)  
s
星点 的特征为  
k
F
{ e  
，e ，e }  
0，k k，1  
－
k
k
1，k  
，
射值 把每个识别模式的中心星点对应的编号对应  
，e ，  
其中 表示星点之间的距离星角距 下脚标表  
， “ ”  
于多个哈希值 建立 一对多 的星图识别模式数据  
。 S  
示星点的编号 按照星点有序集 中星点的顺序把  
， ，  
库 即在星图识别数据库中 存在多个识别模式与星  
F ， s  
每个星点的特征 组合起来 就可以得到星点 的  
0
i
，
图中构造的识别模式匹配 可以有效提高星图识别  
=
pat( s ，S，F ) ( i 0，…，  
i
有序星点集星图识别模式  
k) 。  
0
。
的速度  
1．2  
星图识别数据库  
1
，
在星敏感器光电系统探测范围内 按照一定原  
导航星库构建  
。
则筛选后的恒星是可用于星图识别的导航星 假设  
M，  
可用于星图识别的导航星的数量为  
按照恒星编  
星图识别模式及其数据库是影响搜索速度的基  
，
号顺序排列后 可以得到星敏感器的星图识别数据  
，
础因素 本文选用有序星点集  
( ordered star points  
2 。 1 ， 2  
库如图 所示 其中第 列为主星点的编号 第 列  
set，OSPS)  
，
作为星图识别模式 建立星图识别 数  
3 ， 4  
和第 列分别是主星点的赤经和赤纬 第 列为主星  
。
据库  
1．1  
=
F( i) ( i 1，…，M) 。  
点的有序星点集模式特征  
有序星点集星图识别模式  
s
星点 的有序星点集星图识别模式如图  
0
1
所
=
pat( s ，S，F ) ( i 0，…，k)  
i
，
示 定义  
s
为星点 的有序  
0
0
， s ，S  
星点集星图识别模式 其中 为主星点 为主星点  
0
=
，F ( i 0，…，k)  
i
s
S
为 中每个星点的  
的有序星点集  
0

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号