A robust and fast star identification algorithm based on an ordered set of points pattern

A novel, robust, and fast star identification algorithm based on an OSP∗ pattern is presented in this paper. This new algorithm is appropriate for star sensors in the initial acquisition mode, in which no priori attitude information is available. The OSP pattern is constrained with the k-Nearest Neighbor algorithm with a specified order; hence, this pattern is very robust for star identification. In addition, a new hash search approach for accessing the star pattern database is proposed to improve identification speed. The proposed hash search approach is built on the identification error limit and quantified star angular distance. Analysis of numerical results shows that, with increases in the star centroid error, the ISR† of the proposed algorithm is high and stable, while the ISR values of the triangle algorithm, grid algorithm, and pyramid algorithm decrease rapidly. When the star centroid error is three pixels, the ISR of the proposed algorithm is 99.8%, which is 16% higher than the ISR values of the triangle algorithm and grid algorithm, and nearly 10% higher than that of the pyramid algorithm. Similarly, when the number of false stars is increased, the ISR of the proposed algorithm is high and stable, whereas the ISR values of the triangle algorithm, grid algorithm, and pyramid algorithm decrease rapidly. When there are three false stars in an image, the ISR of the proposed algorithm is 98.4%, which is 13% higher than the ISR values of the triangle algorithm and grid algorithm, and 3% higher than that of the pyramid algorithm. Furthermore, the time complexity of the proposed hash search approach is O(1), which is significantly faster than the time complexities of the linear search and k-vector search, which are O(n) and O(k), respectively. Compared with the traditional hash search approach, the proposed approach is much faster when using a compatible database.