# A Voting-Based Star Identification Algorithm Using a Partitioned Star Catalog
## 3 Star Identification
### Construction of Navigation Feature Library  
The navigation feature library is a database that characterizes the information of the stars in a star catalog and their positional relationships, serving as the foundation for star identification. The construction quality of the navigation feature library directly impacts the performance of star identification algorithms. Subgraph isomorphism methods typically use the angular distances between two stars as a feature to build the navigation feature library. However, due to the vast number of stars in the star catalog, the navigation feature library generated from angular distances between any two stars will be extremely large. In the process of star identification, the high number of feature matches leads to slow matching speed and a high probability of redundant and false matching, significantly affecting the identification speed and rate. Therefore, we propose a method for constructing a navigation feature library based on the partitioned star catalog. In Figure 5, the red circle represents the field of view (FOV) of the star sensor. By selecting an appropriate parameter \(N\), the celestial sphere zone could include the FOV of the star sensor. The stars within the FOV of the star sensor generally belong to several celestial sphere zones rather than one zone, but it is evident from Figure 5 that the thirteen partitions around partition 0 can definitively contain all stars within the FOV. Therefore, by using thirteen partitions as a basic unit to construct the navigation feature library, the all-sky star identification can be simplified to star identification within the local celestial sphere, which will significantly simplify the navigation feature library and narrow the retrieval region during star identification, thereby markedly enhancing identification speed while effectively reducing the probability of redundant and false matching. The basic unit is constructed using the angular distance between two stars. Figure 4: The result of star catalog partitioning. Different colors are used to distinguish 20 divided regions of the star catalog. Firstly, two stars \(m\) and \(n\) are randomly selected from thirteen partitions. Then, the reference vectors of two stars are defined as follows:  
\[u_{m}= \begin{bmatrix}cos\alpha_{m}cos\delta_{m}\\ sina_{m}cos\delta_{m}\\ sin\delta_{m}\end{bmatrix} ,u_{n}= \begin{bmatrix}cos\alpha_{n}cos\delta_{n}\\ sina_{n}cos\delta_{n}\\ sin\delta_{n}\end{bmatrix}  \tag{7}\]  
where \((\alpha_{m},\delta_{m})\) and \((\alpha_{n},\delta_{n})\) are the right ascension and declination of stars \(m\) and \(n\). The angular distance between stars \(m\) and \(n\) is given by the following:  
\[\theta_{mn}=arccos\bigg{(}\frac{u_{m}\cdot u_{n}}{|u_{m}||u_{n}|}\bigg{)} \tag{8}\]  
where the symbol '\(\cdot\)' represents the dot product of the vectors, and '\(|\)'is the norm of the vector. Due to the limitation imposed by the FOV of star sensor, any angular distance within the basic unit that exceeds the FOV is considered as invalid information. Therefore, the constructed basic unit can be optimized based on Formula (9) by filtering out angular distances greater than the FOV. \[ \begin{cases}\theta_{mn}\
otin M_{\theta}^{i},\theta_{mn}\geq\theta_{FOV}\\ \theta_{mn}\in M_{\theta}^{i},\theta_{mn}<\theta_{FOV}\end{cases}  \tag{9}\]  
where \(\theta_{FOV}\) represents the FOV, and \(M_{\theta}^{i}\) refers to the basic unit \(i\). Since the arrangement of angular distances within the basic unit is somewhat disorganized, it makes it difficult to perform fast retrieval during star identification. To enhance the retrieval speed of angular distances in the basic unit, we sort the angular distances in ascending order and divide the basic unit into \(T\) blocks. Then, an index function as defined in Formula (10) is established to quickly locate the block of the angular distance.