基于三角形匹配的星图识别算法及优化

Star map recognition algorithm based on triangle matching and optimization

星图识别算法中三角形算法应用最为成熟和广泛,但作为算法识别基元的三角形由于特征维数低,导致冗余匹配和错误识别几乎不可避免。鉴于传统三角形算法识别成功率较低,新算法对传统算法进行了针对性改进,增加了检测第四颗星操作,特征维数由三维变成了四维,并对其它待测星进行逐一验证,大幅提高了识别成功率;但随之增加的大量运算降低了算法运行效率,因此新算法在最核心三角形匹配中构造了哈希表,并将待匹配星对按照星角距排序运用二分查找极大程度减少了特征量的比较次数,一改经典算法中遍历的低效。同时巧妙利用导航星数较少的特点,用短整数代替整数存储使导航星库的存储容量降低1/3的同时提高了CPU中cache的命中率,从硬件层次上提升了算法效率。仿真试验表明:改进后的算法识别成功率和运行效率均明显由于传统三角形算法。

As one of the earliest star pattern recognition algorithms, the triangle star identification algorithm is the most mature and widely used. But as the algorithm recognition based on triangular element due to the characteristics of low dimension , redundancy and error recongnition is almost inevitable. Because of the low recognition success rate of the traditional triangle algorithm , the four-th measured star has been added and the dimension of feature has changed to four-dimensional, and all the other stars will be verified one by one, which greatly improves the recognition success rate; However, large number of operations increased to reduce the operating efficiency of the algorithm, to solve it , the hashtable are constructed, and the use of ordered satellite for bineary search are proved to greatly reduce the number of comparisons of the angular distance of stars; at the same time , making ingenious use of navigation star number lesss, with a short integer instead of integer storage, reduces the storage capacity of the navigation star database and improves the hit rate of CPU in cache to improve the efficiency of the algorithm from the hardware level . The simulation results show that the improved algorithm is more efficient than the traditional triangulation algorithm in both the success rate and the efficiency.