# A Star-Identification Algorithm Based on Global Multi-Triangle Voting
## 1 Introduction  
Attitude measurement devices are key for modern deep space tasks. Generally, star sensors supply arc-second attitude data, whose precise level is much higher than sun sensors, gyroscopes, or magnetometers [1, 2], and are now widely utilized in orbiting satellites and interplanetary spacecraft [3, 4]. During data processing in star sensors, the star-identification technique plays a decisive role in determining attitude when utilizing detected stars in an image. There are two working modes for star sensors: lost-in-space (LIS) and tracking [5]. When we turn on star sensors or miss attitude data, the working mode of sensor stars will be in LIS, in which prior attitude data are absent, so an autonomous algorithm designed for whole sky identification is running to establish attitude data. Sky region information is acquired after determining the initial attitude in LIS mode, and then the star sensors switch to tracking mode and need to implement star identification in a very small sky region. Therefore, algorithm research about star identification in LIS is important for star sensors. Star-identification methods for working in LIS mode can be divided into three classes [6]: pattern recognition, artificial intelligence, and subgraph isomorphism. In the pattern recognition methods, each guide star is assigned a unique signature or pattern that describes the geometric distribution feature of neighboring stars, and then identification is implemented by searching for a guide star in the catalog whose pattern is the most similar to a star pattern built from the captured star image. The grid algorithm [7] is the most typical pattern-based approach utilizing a grid pattern vector, but its performancein the identification rate is sensitive to noise due to the low probability of selecting the correct subalternon star. Although some optimal schemes are introduced in [8; 9; 10], the key drawback in the grid algorithm has not been resolved. [PERSON] et al. [11] present a pattern recognition method utilizing radial and cyclic pattern features by adding a cyclic feature to filter error candidates. Unfortunately, the cyclic pattern is also not reliable enough. By optimizing the generation steps of a cyclic pattern, star identification based on radial and dynamic cyclic patterns is proposed in [12], where the maximum cumulate method is utilized to measure the similarity between cyclic patterns. However, the star-identification rate is prone to be low when there is magnitude noise. There are also other pattern-based algorithms proposed to improve robustness, such as the recommended radial pattern [13], log-polar transform [14], redundant-coded pattern [15], label code [16], and triangle map matrix methods [17], but their performance is still poor when there is magnitude noise. Recently, artificial intelligence algorithms, especially those utilizing deep learning methods have been proposed for solving the LIS problem for star sensors. These include the Spider-CNN algorithm [18], RPNet algorithm [19], and 1D-CNN algorithm [20]. These algorithms have the parallel ability to process information and robustness to different types of errors, but considering the database size, the complexity of the model, and training time, these factors limit the application of deep learning methods in actual projects. In subgraph-isomorphism-based methods, stars in the captured image and the angular distances between them are regarded as graph vertices and graph sides, respectively. Then, a feature subgraph unit for the matching process is built to search for similar subgraphs stored in the database, including entire sky graphs. The triangle algorithm [21; 22; 23], pyramid algorithm [24], and geometric voting algorithm [25] are typical star-identification methods based on subgraph isomorphism, in which polygons, pyramids, and star pairs are used as feature subgraph units.