# A Star-Identification Algorithm Based on Global Multi-Triangle Voting
## 2 Algorithm Description
### Global Multi-Triangle Voting Algorithm
#### 2.3.1 Initial Match  
At the beginning of the initial match step, we select the eight brightest detected stars in the captured image as sensor stars to be identified according to their gray values, then a counter group (\(\rm CT_{1}^{i}\),\(\rm CT_{2}^{i}\)... \(\rm CT_{N_{c}}^{i}\)) including N\({}_{\rm c}\) counters, is assigned for every sensor star, in which each counter is responding to each guide star in the reference catalog, and N\({}_{\rm c}\) is the guide star number in the catalog. We can build triangle units from these bright sensor stars by selecting any three stars among them. As a result, there are \(C_{8}^{3}\) units involved in the initial match. For each triangle unit, \(p\
u_{1}\) and \(p\
u_{2}\) values are acquired by the feature extraction process described in Section 2.1. Here, an example is given to illustrate the GMTV algorithm work process in this step.  
We assume that unit k, including sensor star a, star b, and star c, is built, and its feature values \(p\
u_{\rm k1}\) and \(p\
u_{\rm k2}\) are also obtained. For database units whose feature value \(p\
u_{c1}\), (c = 1, 2, 3,..., N - 1, N, and N is the total number of triangle units) is close to the corresponding \(p\
u_{\rm k1}\), \(p\
u_{\rm k2}\), respectively, which can be described in Equation (4), these units in the database are considered as candidates of sensor unit k.  
\[\left\{\begin{array}{ll}abs(\hat{p}\
u_{\rm k1}-\hat{p}\
u_{c1})&\leq Th_{ \rm f}\\ abs(\hat{p}\
u_{\rm k2}-\hat{p}\
u_{c2})&\leq Th_{\rm f}\end{array}\right. \tag{4}\]  
where \(Th_{f}\) is the threshold for the feature value match. The above candidates searching process can be implemented by looking for an element where the row index is \(p\
u_{\rm k1}\) and the column index is \(p\
u_{\rm k2}\) in the lookup table, which greatly improves the efficiency of the GMTV algorithm in searching for matches in the database. In the real star image, some measurement errors will cause feature values to deviate from their true value, so the fuzzy search strategy is adopted in our algorithm to increase robustness; as shown in Figure 5, all elements in the shaded areas whose position index is close to \(\hat{p\
u}_{\rm k1}\) and \(\hat{p\
u}_{\rm k2}\), namely, where the row index is between \(p\
u_{\rm k1}-1\) and \(p\
u_{\rm k1}+1\) and the column index is between \(p\
u_{\rm k2}-1\) and \(p\
u_{\rm k2}+1\) simultaneously, are regarded as candidates of the sensor unit.  
A unit in the lookup table constructed by catalog stars whose index number is C\({}_{1}\), C\({}_{2}\), and C\({}_{3}\) in the SAO catalog is a candidate for sensor unit k (built by sensor star a, star b and star c). Then, the counter group belonging to the sensor star is selected, and the value of counters in (\(\rm CT_{1}^{i}\), \(\rm CT_{2}^{i}\)... \(\rm CT_{N_{c}}^{i}\)) corresponding to C\({}_{1}\), C\({}_{2}\), and C\({}_{3}\) add one; as shown in Figure 6, \(C\ell_{\rm C}^{ss}\) is a counter assigned for guide star C in the counter group belonging to sensor star a (ssa), the same meaning of \(C\ell_{\rm C}^{ssb}\) and \(C\ell_{\rm C}^{ssc}\). The same operation is completed for the other two counter groups belonging to sensor star b (ssb) and sensor star c (ssc), respectively. The above process is a vote of sensor unit k. We can repeat this voting process  
Figure 5: Fuzzy search strategy.  
until all sensor units are traversed. For each sensor star, the counters' values in the group are compared with the threshold \(T\!I\!f^{c}\), and the catalog stars associated with counters whose values are larger than \(T\!I\!f^{c}\) are considered as the candidates for this sensor star.