# A Star-Identification Algorithm Based on Global Multi-Triangle Voting
## 2 Algorithm Description
### Global Multi-Triangle Voting Algorithm
#### 2.3.2 Verification  
In this paper, a verification method based on the largest cluster is designed to eliminate wrong candidates in the initial match, retain correct identification results as much as possible, and then output them as the final identification results of the algorithm. The maximum cluster verification algorithm includes three steps: calculate the connection matrix, determine the core cluster, and expand the core cluster. The specific contents of the above three steps are as follows:  
Step 1: calculate the connection matrix  
Calculate the angular distance \(\theta^{c}\) between the candidate stars in the celestial coordinate system, and then compare \(\theta^{c}\) with the angular distance \(\theta^{s}\) of the corresponding observed stars in the star sensor coordinate system. If the error between \(\theta^{c}\) and \(\theta^{s}\) is less than a tolerance threshold \(\tau\), as described in Equation (5), the element in the corresponding position of the connection matrix is set to 1; otherwise, it is set to 0. The connection matrix is a square matrix of size D\(\times\)D, where D is the number of candidate stars in the initial match. For example, as shown in Figure 7, given that the angular distances between star-1 and star-2 meet the above requirement that the error between \(\theta^{c}_{12}\) and \(\theta^{c}_{12}\) is less than \(\tau\), then the elements in the position index (1, 2) and (2, 1) of the connection matrix are set to 1. Since the angular distances \(\theta^{C}_{14}\) and \(\theta^{S}_{14}\) between star-1 and star-4 do not meet the requirement of Equation (5), the elements in the position index (1, 4) and (4, 1) of the connection matrix are set to 0. It should be noted that the diagonal elements of the connection matrix are all set to 1. \[\left|\theta^{C}-\theta^{S}\right|\leq\tau \tag{5}\]  
Step 2: determine the core cluster  
The determination of the core cluster step includes two main parts, namely, searching the initial largest cluster and filtering the initial largest cluster elements. The specific contents are as follows:  
In the first part, the elements of the connection matrix are added in the column direction, the column with the largest summation value is determined, and then the candidate stars corresponding to the rows with the element value of 1 in this column are selected to generate the initial largest cluster. For example, as shown in Figure 8, the values after summing the elements in the column direction are 4, 5, 5, 5, 4, and 5, so the second column is of maximum value, and because its elements in rows 1 to 5 are 1, the initial largest clustering is {Star-1, Star-2, Star-3, Star-4, Star-5}. Figure 6: Vote process in the initial match step. In the second part, the elements in the initial largest cluster are filtered to determine the core cluster. As shown in Figure 9, * is the bitwise multiplication operator; we can bitwise multiply the corresponding column vector in the connection matrix where the initial largest cluster is located with the first column vector, and then bitwise multiply the result of the previous step with the second column vector, then repeat the same operation until the last column vector. Then, a column vector of size D\(\times\)1, defined as the filter vector, is obtained. Next, the candidate stars in the filter vector whose corresponding element value is 1 are selected in the core cluster. For example, the second column vector is bitwise multiplied by each column vector in the connection matrix, and the filter vector is [0 1 1 0 1]', so the core cluster is [Star-2 Star-3 Star-5]. Figure 8: Searching initial largest cluster. Figure 7: A connection matrix. Figure 9: Filtering initial largest cluster elements. Step 3: extend the core cluster  
After determining the core cluster, the core cluster is utilized to search for more correct candidates not included in the core cluster due to noise to improve the attitude accuracy of the star sensor, but at the same time, it has to be ensured that wrongly identified results must be excluded.