# Lost-in-Space Star Identification Using Planar Triangle Principal Component Analysis Algorithm

Authors: Fuqiang Zhou; Tao Ye
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

It is a challenging task for a star sensor to implement star identification and determine the attitude of a spacecraft in the lost-in-space mode. Several algorithms based on triangle method are proposed for star identification in this mode. However, these methods hold great time consumption and large guide star catalog memory size. The star identification performance of these methods requires improvements. To address these problems, a star identification algorithm using planar triangle principal component analysis is presented here. A star pattern is generated based on the planar triangle created by stars within the field of view of a star sensor and the projection of the triangle. Since a projection can determine an index for a unique triangle in the catalog, the adoption of thek-vector range search technique makes this algorithm very fast. In addition, a sharing star validation method is constructed to verify the identification results. Simulation results show that the proposed algorithm is more robust than the planar triangle and P-vector algorithms under the same conditions.


---

## Body

## 1. Introduction

Accurate attitude information is essential for spacecraft autonomous navigation. This plays a very important role in spacecraft control systems. Many different strategies can be employed to determine the attitude. One of the most widely used attitude measurement devices is a star sensor. Other sensors for determining attitude include a sun sensor and magnetometer [1–3]. A star sensor can provide precision attitude without prior information. It obtains the attitude directly from the stars within its field of view (FOV). As long as at least two stars in the FOV are identified in the predefined onboard star catalog, the attitude of the spacecraft can be determined using the TRIAD algorithm [4].A classic star sensor works in two basic modes. When it is first activated or after a system failure, it has no prior information regarding the attitude. This is called the “lost-in-space” (LIS) mode. Once the attitude is determined, the star sensor changes to the tracking mode. It employs previously obtained information to predict the current attitude. This paper addresses attitude determination in the LIS mode. The most important function for a star sensor to determine the attitude is star identification. Star identification in the LIS mode is much more difficult than in the tracking mode [5–8]. As a result, there are many different algorithms for star identification within an FOV (see review paper [9]). We focus our research on triangle algorithms. In this study, we explore a modified triangle algorithm employing a highly compressed feature catalog memory. It provides a significant improvement in terms of star identification time and rate.The first triangle algorithm was developed by Liebe [10]. Liebe stored guide triangles that are formed by guide stars. These are used for matching observation triangles within the FOV. If the guide triangle matches any observation triangle, then the star identification succeeds. Even though only 1,000 stars were selected from the Smithsonian Astrophysical Observatory (SAO) [11] star catalog to form the guide triangles in this algorithm, there are still 185,000 star triangles. The recognition rate for this algorithm is 94.6% and the all-sky star identification average time is about 10 s.Based on the traditional triangle algorithm, Mortari et al. proposed a pyramid algorithm [12] that matches four stars by ordering the angular distance between the stars to form an index. The adoption of the k-vector range search technique makes this algorithm fast. This algorithm can estimate the frequency of false matches, but no statistical analysis is given for the errors in the four stars’ angular distance measurements.Then, Cole and Crassidis made some changes in terms of feature selection for planar triangles method. The triangle is a combination of three stars, as shown in Figure1. The area and polar moment of the triangles are used to determine what triangle is being examined by the star sensor [13]. Using these two features, the number of similar solutions will be rapidly reduced. Unlike the pyramid algorithm, this algorithm can give precise statistical analysis of the polar moment or area errors and can thus provide an accurate range for the observation triangles matching the catalog triangles. However, there are certain drawbacks to this algorithm. A large memory is required to hold the triangle data. For example, when the star sensor has an 8 × 8-degree FOV, the area and polar moment calculated can generate a guide star catalog of 167 MB. In addition, this algorithm is affected by star positional noise in the image.Figure 1
Planar triangle from combination of three stars.Yang et al. developed aP-vector star identification algorithm [14]. The Quine method [15], which can determine a star with only one angular distance triangle, is assimilated in this algorithm. The three edges of the triangle are used to generate a parameter P. Comparison of the value of the parameter P of the observation triangle with a triangle in the catalog can identify the star. Considerable time and memory can be saved with this algorithm. However, it also has some drawbacks. Because the feature triangle is a combination of the guide star and the two brightest stars around the guide star, the star identification rate is easily affected by magnitude noise. Furthermore, if the stars within the star sensor FOV cannot form a triangle corresponding to a triangle in the catalog, the algorithm will not work.As mentioned previously, accurate error analysis, storage, speed, and the ability to manage noise are the main problems with traditional triangle star identification methods. In this study, we develop a star identification algorithm called the planar triangle principal component analysis (PTP) algorithm that performs well against star positional noise and magnitude noise. The algorithm, which incorporates the advantages of the planar triangles andP-vector algorithms, can calculate the range of the measurement error precisely and identify a star faster. It creates planar triangles from the stars in the FOV similar to the planar triangle algorithm and then employs the three sides of the triangles to build vectors projected on the projection line to compute the projection as in the P-vector algorithm. The stars selected to construct the planar triangle are satisfied with a specific condition that is more flexible than in the P-vector algorithm. Thus, less memory is needed to store the planar triangles in the catalog database. The number of reference triangles is sufficient to be used for matching the observed triangles in the FOV of the star sensor. The adoption of the k-vector range search technique makes the proposed algorithm very fast. In addition, the proposed sharing star validation method can effectively verify the identification results. In simulations, using the stars brighter than magnitude 6.0 Mv and 10 × 10-degree FOV, our algorithm obtains an identification rate of 96.79% from the statistics of 10,000 random sensor orientations at a positional noise level of 1 pixel and a magnitude level of 0.5 Mv.The rest of the paper is organized as follows. In Section2, the algorithm is described in detail, including guide star catalog construction, matching, star identification, and identification result validation. In Section 3, a simulation and an analysis of the results are provided. These focus on discussing the number of slave stars in guide database construction and comparing the robustness of the different algorithms (our PTP algorithm, P-vector algorithm, and planar triangle algorithm) with regard to the algorithm parameters, including positional noise, magnitude noise, and the number of stars in the FOV. We draw our conclusion in Section 4.


## 2. Algorithm Description

The central concept of our PTP algorithm is that the planar triangles composed of the stellar unit vectors in the star-sensor-body coordinate system and the celestial coordinate system are congruent. The concept behind our PTP algorithm is to use the “three sides equal in congruent triangles” principle to recognize the pattern of the stars. Matching the three sides of the triangles simultaneously requires significant computation and results in a redundant match. However, by taking the three sides of the triangle as a three-dimensional vector and using the principal component analysis (PCA) algorithm [16] to compute the projector line, all planar triangles are projected to the projector line to compute the projections. By using the projection of the triangle in the image to find a matched triangle in the guide star database, the computation effort is greatly reduced. The simple diagram of the projection geometry is shown in Figure 2.Figure 2
The simple diagram of the projection geometry.Our PTP algorithm has three steps. First, the guide database is constructed using PCA to train the planar triangles. Second, the projection of the planar triangles is computed to search for the best candidate triangle in the guide database. The third step validates the star identification and reports the identification result or failure. The functional steps of our PTP algorithm are shown in Figure3.Figure 3
Functional steps of PTP algorithm.


### 2.1. Guide Database Construction

The guide database consists of two parts: reference catalog and feature pattern database. The basic information (ID, apparent position, and magnitude) of the stars is stored in the reference catalog. The stars are selected from the standard SAO Star Catalog J2000 [11]. The SAO catalog contains the information of 258,996 stars, including equatorial coordinates (including right ascension and declination), B1950 positions, proper motions, and apparent magnitude of the stars. The catalog is sorted by increasing ID number. For celestial navigation, we focus on the information about the equatorial coordinates and apparent magnitude of the stars. Given the attitude and the optical parameters of a star sensor, it is convenient for us to simulate a star image by using the catalog.Here we use a wide, 10 × 10-degree FOV and assume that the star sensor is capable of capturing stars brighter than 6.0 Mv. A total of 5103 stars were picked from the star catalog. The pattern database creation consists of three steps: (1) feature triangle selection; (2) computation of the projection line for all of the feature triangles; (3) pattern database creation.(1) Feature Triangle Selection. As shown in Figure 4, r1, r2, and r3 are three unit vectors to the stars within the FOV, allowing the sides of the planar triangle to be calculated by(1)a=r1-r22,b=r2-r32,c=r1-r32,where ·2 denotes the 2-norm of a vector.Figure 4
Three unit vectors of stars obtained for planar triangle.As mentioned previously, 5103 stars brighter than 6.0 Mv were selected from the standard catalog. We take these stars from the reference catalog as the master stars. As shown in Figure5, the apparent position of the master star is considered the optical axis of the star sensor that extracts the stars in a 10 × 10-degree FOV. We define the extracted stars as slave stars. The distance between the master star and an arbitrary slave star within an FOV can be calculated using (2), denoted by Dms. With the restriction of the circular field of view, the maximum angle between the master star and the slave star is 5°, and the value of Dms is very small. We will migrate the star database to hardware such as DSP6701; however, double-type data occupy 8 bytes and float-type data occupy 4 bytes in DSP memory. Multiplying by 10000 can facilitate the calculation and we can storeDms in float-type data in the DSP, which can save memory as well. To this end, 10000 can satisfy the requirements of calculation. Incorporating this, when the angle between the master star and the slave star is 5°, the value of Dms is 872.8. For the simulated star sensor with resolution of 1024 × 1024, we choose 0.05° as a lower limit to avoid double star interference in star identification. Consider(2)Dms=rm-rs2,where rm denotes the master star’s unit vector to the stars within the FOV and rs denotes the slave stars’ unit vector to the stars within the FOV.Figure 5
Star-sensor-capturing stars.The rule for feature planar triangle selection is as follows. First, we pick the slave stars that satisfy8.728≤Dms≤872.8 from the FOV and sort them by the distance between the master star and the slave stars. Second, the four nearest slave stars from the master star, denoted by s1,s2,s3, and s4, are kept. The first nearest slave star is denoted by s1, the second nearest slave star is denoted by s2, the same criteria apply for s3,s4, and so on. If there are less than four slave stars, they will all be kept. The four slave stars compose the planar triangles with the master star (denoted by m) as follows: Δms1s2, Δms1s3,Δms1s4, Δms2s3, Δms2s4, and Δms3s4.(2) Computation of Projection Line for All Feature Triangles. The arbitrary triangles constructed above can be uniquely identified by a vector denoted by Δi, where Δi=(ai,bi,ci)T. ai,bi, and ci denote the three sides of the triangle, and when 1≤i≤sn, i denotes the arbitrary triangle’s index and sn denotes the total number of triangles. All the triangles constructed above can then compose a matrix: M=Δ1,Δ2,…,Δn. The size of M is (3×n), where n=sn. Then, the PCA algorithm is applied to M, with the following procedure.(1)
Calculate the column meanΔ of the matrix M, where Δ=(1/n)∑i=1nΔi and n=sn.(2)
Construct the zero mean matrixQ=φ1,φ2,…,φn, where φi=Δi-Δ and 1≤i≤n,n=sn.(3)
Calculate the eigenvalue of the covariance matrixC, where C=QQT, and then take the eigenvector corresponding to the largest eigenvalue umax as the main component of the data’s direction. This is termed the “projection axis” in this paper.(3) Pattern Database Creation. For any arbitrary triangle, the projection corresponding to the projection axis can be found by using (3)pri=umaxTφi,where pri denotes the ith triangle’s projection, 1≤i≤sn.Then, each triangle can be assigned a unique index value in the projection axis. The projections of the triangles are sorted in order to generate ak-vector to locate a particular triangle in the pattern database. Table 1 presents a portion of this pattern database of the star triangle data matrix sorted in ascending order of minimum projection (pr). Columns 3–5 indicate the ID of the stars in the celestial sphere. Columns 6–9 represent the three sides of the planar triangle formed by the stars.Table 1
Portion of the feature star triangle data.
k
p
r
I
1
I
2
I
3
E
1
E
2
E
3
1481
−340.82761
196653
196659
196774
84.69942
302.27382
257.24929
1482
−340.67816
255962
255998
255973
222.12911
289.31676
211.56302
1483
−340.47604
195986
196061
196059
185.17209
235.82384
252.29448
1484
−340.31628
210501
210518
229285
241.14157
387.20251
156.38031
1485
−340.00249
77354
58280
58319
224.34569
377.17599
168.09326
1486
−339.97403
221998
221895
221910
259.94539
336.45580
174.71311
1487
−339.73879
238077
238222
238085
191.77735
192.40493
272.11040
1488
−339.73724
252293
252304
252400
24.56941
303.19337
280.94802
1489
−339.65092
94111
94095
94063
119.22040
269.02036
261.94229A spatial distribution projection of the triangles on the projection axis is shown in Figure6. The triangle indices corresponding to the projections are shown in Figure 7. In Figure 6, we can see that the projection values of some triangular eigenvectors on the projection axis are very close. Actually, each triangle vector corresponds to a unique projection value. In Figure 7, we can see that some of the projections are very close. These close projections, corresponding to the triangles, will be taken as the candidate triangles in the star identification stage. Moreover, from Figures 6-7, it can be seen that the data points are too close. It means that the PCA algorithm cannot separate the planar star triangles well. However, the main function of PCA in this paper is used to reduce the dimension of the triangle vector. The three dimensions of the triangle vector are used to generate a projection value, which can be used for fast triangle matching combining with the k-vector method and the three-side restriction of the planar triangles. Then, the validation method proposed validates the candidate matched triangles and makes the final identification of the stars.Figure 6
Spatial distribution projection of triangles on projection axis.Figure 7
Projection corresponding to the index of the triangles.


### 2.2. Star Identification

Star identification consists of two steps. Step 1 focuses on obtaining the projection of the observed triangle and calculating an accurate projection deviation. Step 2 describes a quick solution to the triangle matching and star identification processes using the projection and projection deviation.(1) Projection of Observed Triangle. Using the guide database constructing process, we can obtain the mean vector Δ=(av,bv,cv)T of all the corresponding triangle vectors in the database as well as the direction vector umax=(w1,w2,w3)T of the projection line. Given the arbitrary three star unit direction vectors within the FOV corresponding to the star sensor coordinates, denoted by t1, t2, and t3, we can calculate the three sides of a triangle that is a combination of these three stars as shown in(4)a=t1-t22,b=t2-t32,c=t1-t32.Then, we can assume that the vector corresponding to the triangle is denoted by Δ~=(a,b,c)T, and the projection of the triangle on the projection line can be found using (5)pr=umaxTΔ~-Δ=aw1+bw2+cw3-avw1-bvw2-cvw3.The equation given is for the star sensor frame. It can be also used, however, in the Earth-centered inertial frame. To obtain a boundary for the measurement error, the standard deviation of the calculated projection can be calculated.Since the projection is a nonlinear function oft1, t2, and t3, a linearization approach can be used to determine its variance. To compute the variance, the following 1 × 9 partial derivative matrix is evaluated by (6)T=T1TT2TT3T=∂pr∂t1∂pr∂t2∂pr∂t3,where(7)T1T=∂pr∂a∂a∂t1+∂pr∂c∂c∂t1,T2T=∂pr∂a∂a∂t2+∂pr∂b∂b∂t2,T3T=∂pr∂b∂b∂t3+∂pr∂c∂c∂t3.The partials with respect toa, b, and c are given by(8)∂pr∂a=w1,∂pr∂b=w2,∂pr∂c=w3.The partials with respect tot1, t2, and t3 are given by(9)∂a∂t1=t1-t2Ta,∂a∂t2=-∂a∂t1,∂b∂t2=t2-t3Tb,∂b∂t3=-∂b∂t2,∂c∂t1=t1-t3Tc,∂c∂t3=-∂c∂t1.The unit direction vector of any starti, corresponding to the star-sensor-body coordinate system, can be found using the standard coordinate transformation equation: ti=Ari, where ri is the unit direction vector of the star in the Earth-centered inertial coordinate system and A is the direction cosine matrix. When measurement errors (a typical star sensor follows a nearly zero mean Gaussian white-noise distribution [17]) are removed, the probability of errors is concentrated on the direction of Ari [18]. Then, the sphere containing that point can be approximated by a tangent plane [13], characterized by(10)t~i=Ari+vi,viTAri=0,where t~i denotes the ith measurement and the sensor error vi is approximately Gaussian, which satisfies(11)Evi=0,Ri≡EviviT=σ2I-AriAriT,where σ2 denotes the variance of the star sensor noise and E denotes the expected sensor error. Additional details of this model are given in [19]. Since the direction cosine matrix A is unknown, we can substitute t~i for Ari [18], and then (11) can be reconstructed as(12)Ri≡EviviT=σ2I-t~it~iT.According to (4) to (12), the variance of the projection can be calculated by(13)σp2=TRTT,where (14)R≡R1000R2000R3,where 0 denotes a 3 × 3 matrix of zeros and R1, R2, and R3 are given by (12). Note that the matrices T and R cannot be evaluated at their respective true values; however, the errors that are generated by replacing the true values with the measured ones can be negligible compared with typical star sensor noise levels. Since the standard deviation σp is derived analytically, the range of the true projection can be determined precisely.(2) Star Identification Procedure. In the star identification phase, we number the stars to be identified in an image. Then, planar triangles are constructed for the numbered stars. We take each numbered star as a master star and select stars that satisfy the feature triangle construction criteria from the remaining stars as slave stars. After constructing the planar triangles, we can calculate the three sides of the triangle by using (1) and can also calculate the projection pr of the triangle using (3). Owing to the influence of noise, there must be a projection deviation. The standard deviation of the projection, σp, can be found using (13). Then, we can confirm that the boundaries of the true value of projection are in the range pr-ξ,pr+ξ, where ξ=3σp. As this range is chosen to be the measurement projection ±3 times the standard deviation of the measurement noise, 3σp, the true measurement is expected to be within this range 99.7% of the time. After the range of error is determined, we can use the k-vector method to quickly search and match in the pattern database. The k-vector method works as follows.(1)
Construct a linear equationz=mx+q, where q is the k-vector constant, m is the slope of the k-vector, z is the projection, and x is a function for the error. Each projection pr(k) corresponds to a triangle in Table 1 where the maximum projection pmax is denoted by pr(sn) and the minimum projection pmin is denoted by pr(1). Then, the step of the length d can be found using(15)d=pmax-pminnandq and m can be given by(16)q=pmin-m-d,m=pmax-pmin+2dn.(2)
Compute the projection of the trianglepr in the star image, and then, the true value ptrue is assumed to satisfy the boundaries ptrue∈[pr-ξ,pr+ξ]. We can then obtain the upper and lower limits of x using(17)xl=pr-ξ-qm,xh=pr+ξ-qm,wherexl denotes the lower limit of x, xh denotes its upper limit, and kl≤x≤kh.(3)
Substitutingxl and xh into the equation z=mx+q gives zl and zh.(4)
The range is delimited by a lower indexkl and a higher index kh:(18)prp≤zl<prp+1,prq≤zh<prq+1,wherep and q denote the index in Table 1. Consider(19)kl=p+1,kh=q+1.Obviously, all of the k-vector values should be computed offline. One lower or higher limit of x that is corresponding to a k-vector value can be computed offline. We can generate a k-vector search database. Table 2 shows a port of k-vector search data. Column 1 indicates the limit index that is obtained by (17). Column 2 represents the k-vector value corresponding to the limit index.Table 2
Portion ofk-vector value data.
Limit index
k-vector value
1909
1574
1910
1579
1911
1581
1912
1583
1913
1584
1914
1585When the searching range is determined, we can compare the three sides of the observed triangle with the reference triangle(s) within the boundary. If the three side errors are within a small range, only one triangle will meet the criteria, and so the observed triangle will match the reference triangle, and the stars corresponding to the triangle will also match. If there is more than one triangle that meets the criteria, we store the candidate triangles and initiate the validation procedure.


### 2.3. Validation

With respect to all the candidate matched triangles, we store the IDs of the stars in the star image corresponding to the catalog as follows:Pi-Ii, where Pi denotes the IDs of the star in the star image, Ii denotes IDs of the star in the catalog, and 1≤i≤n, where n denotes the total number of possible identified star IDs parts. Since there are redundant triangles existing in some cases, n is more than equal to the total number of stars in the star image. Then, we verify the identification result in the validation stage. The flow chart of the star identification and the validation is shown in Figure 8. From the feature planar triangles construction procedure, it can be seen that different planar triangles share stars, which indicates that a star can exist in different feature triangles within the star sensor’s FOV. Based on this, a validation method was constructed. As shown in Figure 9, Pi(k) and Ii(k) denote the star IDs in the star image and in the catalog of the ith star in the kth feature triangle, respectively. Δk and Δt represent the kth and tth feature planar triangles, respectively. If a star in different triangles has the same IDs in the star image and catalog, our PTP algorithm will successfully identify the star and the triangles with the star; otherwise, it will be determined as a failure. The following short example, whose results are shown in Table 3, demonstrates how the validation method works. The input image was generated by star image simulation procedure from the star catalog, the star sensor’s optical parameters, and its attitude. The resulting image contains 12 stars. Only 9 stars are extracted. The rest are too faint to be detected. Only identified stars participate in the validation stage. The first row of Table 3 shows the identified triangles. The identities of the stars in image corresponding to star catalog are shown in the second and the third rows of Table 3. It can be seen that the identified stars in different triangles share common identities in star image and catalog. The validation method determines that stars 3, 4, 5, 6, 7, 8, 10, 11, and 12 are correctly identified. Then, the attitude of the star sensor can be determined by the correctly identified stars’ coordinates in image and their matching positions in the catalogue.Table 3
The validation results of the identified stars.
Triangle
1
2
3
4
Star number
6
11
3
8
7
10
12
11
10
5
7
4
IDs
230523
230575
230492
230644
230667
230596
212793
230575
230596
230726
230667
230692Figure 8
Flow chart of star identification and validation algorithm.Figure 9
The diagram of star identification validation.


## 2.1. Guide Database Construction

The guide database consists of two parts: reference catalog and feature pattern database. The basic information (ID, apparent position, and magnitude) of the stars is stored in the reference catalog. The stars are selected from the standard SAO Star Catalog J2000 [11]. The SAO catalog contains the information of 258,996 stars, including equatorial coordinates (including right ascension and declination), B1950 positions, proper motions, and apparent magnitude of the stars. The catalog is sorted by increasing ID number. For celestial navigation, we focus on the information about the equatorial coordinates and apparent magnitude of the stars. Given the attitude and the optical parameters of a star sensor, it is convenient for us to simulate a star image by using the catalog.Here we use a wide, 10 × 10-degree FOV and assume that the star sensor is capable of capturing stars brighter than 6.0 Mv. A total of 5103 stars were picked from the star catalog. The pattern database creation consists of three steps: (1) feature triangle selection; (2) computation of the projection line for all of the feature triangles; (3) pattern database creation.(1) Feature Triangle Selection. As shown in Figure 4, r1, r2, and r3 are three unit vectors to the stars within the FOV, allowing the sides of the planar triangle to be calculated by(1)a=r1-r22,b=r2-r32,c=r1-r32,where ·2 denotes the 2-norm of a vector.Figure 4
Three unit vectors of stars obtained for planar triangle.As mentioned previously, 5103 stars brighter than 6.0 Mv were selected from the standard catalog. We take these stars from the reference catalog as the master stars. As shown in Figure5, the apparent position of the master star is considered the optical axis of the star sensor that extracts the stars in a 10 × 10-degree FOV. We define the extracted stars as slave stars. The distance between the master star and an arbitrary slave star within an FOV can be calculated using (2), denoted by Dms. With the restriction of the circular field of view, the maximum angle between the master star and the slave star is 5°, and the value of Dms is very small. We will migrate the star database to hardware such as DSP6701; however, double-type data occupy 8 bytes and float-type data occupy 4 bytes in DSP memory. Multiplying by 10000 can facilitate the calculation and we can storeDms in float-type data in the DSP, which can save memory as well. To this end, 10000 can satisfy the requirements of calculation. Incorporating this, when the angle between the master star and the slave star is 5°, the value of Dms is 872.8. For the simulated star sensor with resolution of 1024 × 1024, we choose 0.05° as a lower limit to avoid double star interference in star identification. Consider(2)Dms=rm-rs2,where rm denotes the master star’s unit vector to the stars within the FOV and rs denotes the slave stars’ unit vector to the stars within the FOV.Figure 5
Star-sensor-capturing stars.The rule for feature planar triangle selection is as follows. First, we pick the slave stars that satisfy8.728≤Dms≤872.8 from the FOV and sort them by the distance between the master star and the slave stars. Second, the four nearest slave stars from the master star, denoted by s1,s2,s3, and s4, are kept. The first nearest slave star is denoted by s1, the second nearest slave star is denoted by s2, the same criteria apply for s3,s4, and so on. If there are less than four slave stars, they will all be kept. The four slave stars compose the planar triangles with the master star (denoted by m) as follows: Δms1s2, Δms1s3,Δms1s4, Δms2s3, Δms2s4, and Δms3s4.(2) Computation of Projection Line for All Feature Triangles. The arbitrary triangles constructed above can be uniquely identified by a vector denoted by Δi, where Δi=(ai,bi,ci)T. ai,bi, and ci denote the three sides of the triangle, and when 1≤i≤sn, i denotes the arbitrary triangle’s index and sn denotes the total number of triangles. All the triangles constructed above can then compose a matrix: M=Δ1,Δ2,…,Δn. The size of M is (3×n), where n=sn. Then, the PCA algorithm is applied to M, with the following procedure.(1)
Calculate the column meanΔ of the matrix M, where Δ=(1/n)∑i=1nΔi and n=sn.(2)
Construct the zero mean matrixQ=φ1,φ2,…,φn, where φi=Δi-Δ and 1≤i≤n,n=sn.(3)
Calculate the eigenvalue of the covariance matrixC, where C=QQT, and then take the eigenvector corresponding to the largest eigenvalue umax as the main component of the data’s direction. This is termed the “projection axis” in this paper.(3) Pattern Database Creation. For any arbitrary triangle, the projection corresponding to the projection axis can be found by using (3)pri=umaxTφi,where pri denotes the ith triangle’s projection, 1≤i≤sn.Then, each triangle can be assigned a unique index value in the projection axis. The projections of the triangles are sorted in order to generate ak-vector to locate a particular triangle in the pattern database. Table 1 presents a portion of this pattern database of the star triangle data matrix sorted in ascending order of minimum projection (pr). Columns 3–5 indicate the ID of the stars in the celestial sphere. Columns 6–9 represent the three sides of the planar triangle formed by the stars.Table 1
Portion of the feature star triangle data.
k
p
r
I
1
I
2
I
3
E
1
E
2
E
3
1481
−340.82761
196653
196659
196774
84.69942
302.27382
257.24929
1482
−340.67816
255962
255998
255973
222.12911
289.31676
211.56302
1483
−340.47604
195986
196061
196059
185.17209
235.82384
252.29448
1484
−340.31628
210501
210518
229285
241.14157
387.20251
156.38031
1485
−340.00249
77354
58280
58319
224.34569
377.17599
168.09326
1486
−339.97403
221998
221895
221910
259.94539
336.45580
174.71311
1487
−339.73879
238077
238222
238085
191.77735
192.40493
272.11040
1488
−339.73724
252293
252304
252400
24.56941
303.19337
280.94802
1489
−339.65092
94111
94095
94063
119.22040
269.02036
261.94229A spatial distribution projection of the triangles on the projection axis is shown in Figure6. The triangle indices corresponding to the projections are shown in Figure 7. In Figure 6, we can see that the projection values of some triangular eigenvectors on the projection axis are very close. Actually, each triangle vector corresponds to a unique projection value. In Figure 7, we can see that some of the projections are very close. These close projections, corresponding to the triangles, will be taken as the candidate triangles in the star identification stage. Moreover, from Figures 6-7, it can be seen that the data points are too close. It means that the PCA algorithm cannot separate the planar star triangles well. However, the main function of PCA in this paper is used to reduce the dimension of the triangle vector. The three dimensions of the triangle vector are used to generate a projection value, which can be used for fast triangle matching combining with the k-vector method and the three-side restriction of the planar triangles. Then, the validation method proposed validates the candidate matched triangles and makes the final identification of the stars.Figure 6
Spatial distribution projection of triangles on projection axis.Figure 7
Projection corresponding to the index of the triangles.


## 2.2. Star Identification

Star identification consists of two steps. Step 1 focuses on obtaining the projection of the observed triangle and calculating an accurate projection deviation. Step 2 describes a quick solution to the triangle matching and star identification processes using the projection and projection deviation.(1) Projection of Observed Triangle. Using the guide database constructing process, we can obtain the mean vector Δ=(av,bv,cv)T of all the corresponding triangle vectors in the database as well as the direction vector umax=(w1,w2,w3)T of the projection line. Given the arbitrary three star unit direction vectors within the FOV corresponding to the star sensor coordinates, denoted by t1, t2, and t3, we can calculate the three sides of a triangle that is a combination of these three stars as shown in(4)a=t1-t22,b=t2-t32,c=t1-t32.Then, we can assume that the vector corresponding to the triangle is denoted by Δ~=(a,b,c)T, and the projection of the triangle on the projection line can be found using (5)pr=umaxTΔ~-Δ=aw1+bw2+cw3-avw1-bvw2-cvw3.The equation given is for the star sensor frame. It can be also used, however, in the Earth-centered inertial frame. To obtain a boundary for the measurement error, the standard deviation of the calculated projection can be calculated.Since the projection is a nonlinear function oft1, t2, and t3, a linearization approach can be used to determine its variance. To compute the variance, the following 1 × 9 partial derivative matrix is evaluated by (6)T=T1TT2TT3T=∂pr∂t1∂pr∂t2∂pr∂t3,where(7)T1T=∂pr∂a∂a∂t1+∂pr∂c∂c∂t1,T2T=∂pr∂a∂a∂t2+∂pr∂b∂b∂t2,T3T=∂pr∂b∂b∂t3+∂pr∂c∂c∂t3.The partials with respect toa, b, and c are given by(8)∂pr∂a=w1,∂pr∂b=w2,∂pr∂c=w3.The partials with respect tot1, t2, and t3 are given by(9)∂a∂t1=t1-t2Ta,∂a∂t2=-∂a∂t1,∂b∂t2=t2-t3Tb,∂b∂t3=-∂b∂t2,∂c∂t1=t1-t3Tc,∂c∂t3=-∂c∂t1.The unit direction vector of any starti, corresponding to the star-sensor-body coordinate system, can be found using the standard coordinate transformation equation: ti=Ari, where ri is the unit direction vector of the star in the Earth-centered inertial coordinate system and A is the direction cosine matrix. When measurement errors (a typical star sensor follows a nearly zero mean Gaussian white-noise distribution [17]) are removed, the probability of errors is concentrated on the direction of Ari [18]. Then, the sphere containing that point can be approximated by a tangent plane [13], characterized by(10)t~i=Ari+vi,viTAri=0,where t~i denotes the ith measurement and the sensor error vi is approximately Gaussian, which satisfies(11)Evi=0,Ri≡EviviT=σ2I-AriAriT,where σ2 denotes the variance of the star sensor noise and E denotes the expected sensor error. Additional details of this model are given in [19]. Since the direction cosine matrix A is unknown, we can substitute t~i for Ari [18], and then (11) can be reconstructed as(12)Ri≡EviviT=σ2I-t~it~iT.According to (4) to (12), the variance of the projection can be calculated by(13)σp2=TRTT,where (14)R≡R1000R2000R3,where 0 denotes a 3 × 3 matrix of zeros and R1, R2, and R3 are given by (12). Note that the matrices T and R cannot be evaluated at their respective true values; however, the errors that are generated by replacing the true values with the measured ones can be negligible compared with typical star sensor noise levels. Since the standard deviation σp is derived analytically, the range of the true projection can be determined precisely.(2) Star Identification Procedure. In the star identification phase, we number the stars to be identified in an image. Then, planar triangles are constructed for the numbered stars. We take each numbered star as a master star and select stars that satisfy the feature triangle construction criteria from the remaining stars as slave stars. After constructing the planar triangles, we can calculate the three sides of the triangle by using (1) and can also calculate the projection pr of the triangle using (3). Owing to the influence of noise, there must be a projection deviation. The standard deviation of the projection, σp, can be found using (13). Then, we can confirm that the boundaries of the true value of projection are in the range pr-ξ,pr+ξ, where ξ=3σp. As this range is chosen to be the measurement projection ±3 times the standard deviation of the measurement noise, 3σp, the true measurement is expected to be within this range 99.7% of the time. After the range of error is determined, we can use the k-vector method to quickly search and match in the pattern database. The k-vector method works as follows.(1)
Construct a linear equationz=mx+q, where q is the k-vector constant, m is the slope of the k-vector, z is the projection, and x is a function for the error. Each projection pr(k) corresponds to a triangle in Table 1 where the maximum projection pmax is denoted by pr(sn) and the minimum projection pmin is denoted by pr(1). Then, the step of the length d can be found using(15)d=pmax-pminnandq and m can be given by(16)q=pmin-m-d,m=pmax-pmin+2dn.(2)
Compute the projection of the trianglepr in the star image, and then, the true value ptrue is assumed to satisfy the boundaries ptrue∈[pr-ξ,pr+ξ]. We can then obtain the upper and lower limits of x using(17)xl=pr-ξ-qm,xh=pr+ξ-qm,wherexl denotes the lower limit of x, xh denotes its upper limit, and kl≤x≤kh.(3)
Substitutingxl and xh into the equation z=mx+q gives zl and zh.(4)
The range is delimited by a lower indexkl and a higher index kh:(18)prp≤zl<prp+1,prq≤zh<prq+1,wherep and q denote the index in Table 1. Consider(19)kl=p+1,kh=q+1.Obviously, all of the k-vector values should be computed offline. One lower or higher limit of x that is corresponding to a k-vector value can be computed offline. We can generate a k-vector search database. Table 2 shows a port of k-vector search data. Column 1 indicates the limit index that is obtained by (17). Column 2 represents the k-vector value corresponding to the limit index.Table 2
Portion ofk-vector value data.
Limit index
k-vector value
1909
1574
1910
1579
1911
1581
1912
1583
1913
1584
1914
1585When the searching range is determined, we can compare the three sides of the observed triangle with the reference triangle(s) within the boundary. If the three side errors are within a small range, only one triangle will meet the criteria, and so the observed triangle will match the reference triangle, and the stars corresponding to the triangle will also match. If there is more than one triangle that meets the criteria, we store the candidate triangles and initiate the validation procedure.


## 2.3. Validation

With respect to all the candidate matched triangles, we store the IDs of the stars in the star image corresponding to the catalog as follows:Pi-Ii, where Pi denotes the IDs of the star in the star image, Ii denotes IDs of the star in the catalog, and 1≤i≤n, where n denotes the total number of possible identified star IDs parts. Since there are redundant triangles existing in some cases, n is more than equal to the total number of stars in the star image. Then, we verify the identification result in the validation stage. The flow chart of the star identification and the validation is shown in Figure 8. From the feature planar triangles construction procedure, it can be seen that different planar triangles share stars, which indicates that a star can exist in different feature triangles within the star sensor’s FOV. Based on this, a validation method was constructed. As shown in Figure 9, Pi(k) and Ii(k) denote the star IDs in the star image and in the catalog of the ith star in the kth feature triangle, respectively. Δk and Δt represent the kth and tth feature planar triangles, respectively. If a star in different triangles has the same IDs in the star image and catalog, our PTP algorithm will successfully identify the star and the triangles with the star; otherwise, it will be determined as a failure. The following short example, whose results are shown in Table 3, demonstrates how the validation method works. The input image was generated by star image simulation procedure from the star catalog, the star sensor’s optical parameters, and its attitude. The resulting image contains 12 stars. Only 9 stars are extracted. The rest are too faint to be detected. Only identified stars participate in the validation stage. The first row of Table 3 shows the identified triangles. The identities of the stars in image corresponding to star catalog are shown in the second and the third rows of Table 3. It can be seen that the identified stars in different triangles share common identities in star image and catalog. The validation method determines that stars 3, 4, 5, 6, 7, 8, 10, 11, and 12 are correctly identified. Then, the attitude of the star sensor can be determined by the correctly identified stars’ coordinates in image and their matching positions in the catalogue.Table 3
The validation results of the identified stars.
Triangle
1
2
3
4
Star number
6
11
3
8
7
10
12
11
10
5
7
4
IDs
230523
230575
230492
230644
230667
230596
212793
230575
230596
230726
230667
230692Figure 8
Flow chart of star identification and validation algorithm.Figure 9
The diagram of star identification validation.


## 3. Simulation and Analysis

In this section, we evaluate the star identification algorithm presented in this paper and compare it with theP-vector and planar triangle algorithms. We show the results for the simulated images. We tested the algorithm using MATLAB in a Microsoft Windows 7 environment on an i5-2400 3.10 GHz PC. The simulations focused on discussing the number of slave stars in guide database construction and the robustness of the key parameters of the algorithm, the number of stars in the FOV, the noise on the star position, and the noise on the star magnitude. For star position noise, it mainly comes from two sources: one comes from the precision of the star centroid algorithms [20, 21] and the other comes from lens distortion that brings lateral distortion and radial distortion to image. In addition, the star sensor’s sensitivity calibration error may bring in star magnitude noise. Most algorithms [6, 22–26] test their robustness by adding pixel and magnitude noise on the star image. In this paper, we still adopt this way to test the robustness of our algorithm.


### 3.1. Simulation Platform

For these experiments, a platform in a VC++ environment was designed to simulate the pictures taken by an onboard star sensor. The configuration of the star sensor is shown in Table4. Each test was performed using 10,000 uniform sensor orientations. The orientations were generated using a Monte Carlo method. For each orientation, stars within a 10° × 10° FOV were picked from the star catalog.Table 4
Star sensor characteristics used in the star image simulation.
Parameter
Value
Pixel resolution
1024 × 1024
Pixel size
12μm × 12 μm
Image center
(512, 512)
FOV
10
°
×
10
°
Focal length
70.2262 mm
Sensitivity of star magnitude
6.0 Mv
Point spread function
2 pixels


### 3.2. Discuss the Number of Slave Stars in Guide Database Construction

The number of the slave stars is very crucial for constructing the guide database. To obtain the proper number of slave stars for constructing our database, we set the limit number of the closet slave stars to 3, 4, 5, and 6 for testing, respectively. Then, we compare the memory size of these guide databases constructed by these limits. Also, 10,000 uniform sensor orientations are generated to test the star identification rate and average identification time with the different guide databases. The result is given with more than 5 stars in the FOV of star sensor, which is shown in Table5. Column 2 shows the memory size of the guide databases constructed under a different number of slave stars. The guide databases store the feature star triangle data, which are constructed as Section 2.1 demonstrates. Obviously, the larger the memory size of the guide database is, the more time the star identification will take. In turn, when the number of closet slave stars is 3, it obtains the smallest size memory of the guide database and achieves the lowest star identification rate, because the database is less sufficient than the other three databases. From the result, it can be seen that a good balance between memory size and average identification time can be achieved when the number of closet slave stars is set to 4.Table 5
The result with a different number of slave stars.
The number of slave stars
Memory size (MB)
Star identification rate (%)
Average identification time (ms)
3
0.436
97.92%
2.52
4
0.784
99.3%
3.11
5
1.128
99.32%
3.86
6
1.643
99.34%
4.94


### 3.3. Robustness against Number of Stars in FOV

The number of stars in the FOV has an impact on the identification rate. Figure10 shows the probability occurrences of the number of stars in the FOV for 10,000 apparent positions. The minimum number of stars in the FOV was 2, and the maximum was 45. The average number of stars was 14.18. In the FOV, the probability of more than eight stars was 96.47%.Figure 10
Probability occurrences of number of stars in the FOV.Generally, the more stars there are in the FOV, the higher the identification rate is. Figure11 shows the changes in the identification rate with the number of stars in the FOV for the three algorithms. From Figure 10, we can see that, in the case of fewer stars in the FOV, the planar triangle algorithm achieved a higher identification rate than the PTP and P-vector algorithms. Our PTP algorithm achieved a higher identification rate than the P-vector algorithm. When the number of stars in the FOV was more than seven, the PTP and P-vector algorithms achieved a higher identification rate, about 100%. The identification rate of the planar triangle algorithm tended toward 100% with some fluctuation. Figure 11 also shows that neither our PTP nor the P-vector algorithm ensured a high identification rate with less than five stars in the FOV. The reason is that our PTP and the P-vector algorithms could not cover all the feature triangles. However, we can see from Figure 10 that, in most cases, there are more than five stars within the FOV, which means that our PTP algorithm can work well in most cases. Our PTP algorithm achieves a balance between memory storage and star identification time.Figure 11
Identification rate versus number of stars in FOV.


### 3.4. Robustness against Star Positional Noise

To simulate the star positional error, a Gauss noise with a zero mean and a standard deviation ranging from 0 to 2 pixels was used. Figure12 shows the statistical results of the star identification process with more than five stars in the FOV for the three algorithms. All the algorithms were implemented under the same simulation conditions. It can be seen that when the standard deviation of the star positional error changed from 0 to 2 pixels, the identification rate of the planar triangle algorithm dropped from 99.1% to 92.1%, the identification rate of the P-vector algorithm dropped from 98.9% to 93.7%, and the identification rate of our PTP algorithm dropped from 99.3% to 95.5%. Compared with the other two algorithms, our PTP algorithm achieved a higher identification rate at the noise level of 2 pixels. Because of the star position noise, the redundant match and mismatch of star triangles will occur during the star identification process, which could reduce the success rate of the algorithms. The redundant rate of match and mismatch of triangles increases as the star position noise grows. However, the sharing star validation method proposed here can reduce the probability of the redundant match and mismatch triangles. Therefore, our PTP algorithm could be more robust than the other two algorithms towards star position noise.Figure 12
Identification rate versus star positional noise level.


### 3.5. Robustness against Star Magnitude Noise

In addition, a magnitude deviation of 0.5 Mv was added to each star in order to simulate the influence of brightness inaccuracy. Simulated sky images with more than five stars were selected to test the identification rate for the three algorithms. The statistical results with magnitude noise are shown in Figure13. As noise was added, the identification rate of the P-vector algorithm dropped from 98.9% to 93.7%. The magnitude noise impacted the P-vector algorithm’s ability to generate the pattern triangles, which in turn reduced the identification rate. The other two algorithms do not use the magnitude information to generate the pattern triangles. Because of the magnitude noise, some stars are missing or added in the star image, which could reduce the other two algorithms’ identification rate. It can be seen that the magnitude noise exerted less influence on the PTP and planar triangle algorithms than that on P-vector algorithm.Figure 13
Identification rate versus star magnitude noise level.


### 3.6. Comparison and Analysis

A comprehensive comparison of the three algorithms is presented in Table6. It indicates that the proposed algorithm was more robust than the other two. The memory size for the guide database of our PTP algorithm was 0.784 MB. Under similar conditions, 0.537 MB was required by the P-vector algorithm and 178 MB was needed by the planar triangle algorithm. This was more than 200 times larger than the equivalent PTP database. Moreover, the average time needed for the computation of the proposed algorithm was less than that for the other two. This is because a k-vector search technique is used in the proposed algorithm. The most important result was that the identification rate of our PTP algorithm was higher than those of the other two algorithms.Table 6
Comparison of the three algorithms (positional noise std. dev = 1 pixel, and magnitude noise std. dev = 0.5 Mv).
Algorithm
Identification rate
Average identification time
Memory requirement (MB)
PTP
96.79%
3.28 ms
0.784
P-vector
94.91%
7.63 ms
0.537
Planar triangle
93.25%
583.75 ms
178


## 3.1. Simulation Platform

For these experiments, a platform in a VC++ environment was designed to simulate the pictures taken by an onboard star sensor. The configuration of the star sensor is shown in Table4. Each test was performed using 10,000 uniform sensor orientations. The orientations were generated using a Monte Carlo method. For each orientation, stars within a 10° × 10° FOV were picked from the star catalog.Table 4
Star sensor characteristics used in the star image simulation.
Parameter
Value
Pixel resolution
1024 × 1024
Pixel size
12μm × 12 μm
Image center
(512, 512)
FOV
10
°
×
10
°
Focal length
70.2262 mm
Sensitivity of star magnitude
6.0 Mv
Point spread function
2 pixels


## 3.2. Discuss the Number of Slave Stars in Guide Database Construction

The number of the slave stars is very crucial for constructing the guide database. To obtain the proper number of slave stars for constructing our database, we set the limit number of the closet slave stars to 3, 4, 5, and 6 for testing, respectively. Then, we compare the memory size of these guide databases constructed by these limits. Also, 10,000 uniform sensor orientations are generated to test the star identification rate and average identification time with the different guide databases. The result is given with more than 5 stars in the FOV of star sensor, which is shown in Table5. Column 2 shows the memory size of the guide databases constructed under a different number of slave stars. The guide databases store the feature star triangle data, which are constructed as Section 2.1 demonstrates. Obviously, the larger the memory size of the guide database is, the more time the star identification will take. In turn, when the number of closet slave stars is 3, it obtains the smallest size memory of the guide database and achieves the lowest star identification rate, because the database is less sufficient than the other three databases. From the result, it can be seen that a good balance between memory size and average identification time can be achieved when the number of closet slave stars is set to 4.Table 5
The result with a different number of slave stars.
The number of slave stars
Memory size (MB)
Star identification rate (%)
Average identification time (ms)
3
0.436
97.92%
2.52
4
0.784
99.3%
3.11
5
1.128
99.32%
3.86
6
1.643
99.34%
4.94


## 3.3. Robustness against Number of Stars in FOV

The number of stars in the FOV has an impact on the identification rate. Figure10 shows the probability occurrences of the number of stars in the FOV for 10,000 apparent positions. The minimum number of stars in the FOV was 2, and the maximum was 45. The average number of stars was 14.18. In the FOV, the probability of more than eight stars was 96.47%.Figure 10
Probability occurrences of number of stars in the FOV.Generally, the more stars there are in the FOV, the higher the identification rate is. Figure11 shows the changes in the identification rate with the number of stars in the FOV for the three algorithms. From Figure 10, we can see that, in the case of fewer stars in the FOV, the planar triangle algorithm achieved a higher identification rate than the PTP and P-vector algorithms. Our PTP algorithm achieved a higher identification rate than the P-vector algorithm. When the number of stars in the FOV was more than seven, the PTP and P-vector algorithms achieved a higher identification rate, about 100%. The identification rate of the planar triangle algorithm tended toward 100% with some fluctuation. Figure 11 also shows that neither our PTP nor the P-vector algorithm ensured a high identification rate with less than five stars in the FOV. The reason is that our PTP and the P-vector algorithms could not cover all the feature triangles. However, we can see from Figure 10 that, in most cases, there are more than five stars within the FOV, which means that our PTP algorithm can work well in most cases. Our PTP algorithm achieves a balance between memory storage and star identification time.Figure 11
Identification rate versus number of stars in FOV.


## 3.4. Robustness against Star Positional Noise

To simulate the star positional error, a Gauss noise with a zero mean and a standard deviation ranging from 0 to 2 pixels was used. Figure12 shows the statistical results of the star identification process with more than five stars in the FOV for the three algorithms. All the algorithms were implemented under the same simulation conditions. It can be seen that when the standard deviation of the star positional error changed from 0 to 2 pixels, the identification rate of the planar triangle algorithm dropped from 99.1% to 92.1%, the identification rate of the P-vector algorithm dropped from 98.9% to 93.7%, and the identification rate of our PTP algorithm dropped from 99.3% to 95.5%. Compared with the other two algorithms, our PTP algorithm achieved a higher identification rate at the noise level of 2 pixels. Because of the star position noise, the redundant match and mismatch of star triangles will occur during the star identification process, which could reduce the success rate of the algorithms. The redundant rate of match and mismatch of triangles increases as the star position noise grows. However, the sharing star validation method proposed here can reduce the probability of the redundant match and mismatch triangles. Therefore, our PTP algorithm could be more robust than the other two algorithms towards star position noise.Figure 12
Identification rate versus star positional noise level.


## 3.5. Robustness against Star Magnitude Noise

In addition, a magnitude deviation of 0.5 Mv was added to each star in order to simulate the influence of brightness inaccuracy. Simulated sky images with more than five stars were selected to test the identification rate for the three algorithms. The statistical results with magnitude noise are shown in Figure13. As noise was added, the identification rate of the P-vector algorithm dropped from 98.9% to 93.7%. The magnitude noise impacted the P-vector algorithm’s ability to generate the pattern triangles, which in turn reduced the identification rate. The other two algorithms do not use the magnitude information to generate the pattern triangles. Because of the magnitude noise, some stars are missing or added in the star image, which could reduce the other two algorithms’ identification rate. It can be seen that the magnitude noise exerted less influence on the PTP and planar triangle algorithms than that on P-vector algorithm.Figure 13
Identification rate versus star magnitude noise level.


## 3.6. Comparison and Analysis

A comprehensive comparison of the three algorithms is presented in Table6. It indicates that the proposed algorithm was more robust than the other two. The memory size for the guide database of our PTP algorithm was 0.784 MB. Under similar conditions, 0.537 MB was required by the P-vector algorithm and 178 MB was needed by the planar triangle algorithm. This was more than 200 times larger than the equivalent PTP database. Moreover, the average time needed for the computation of the proposed algorithm was less than that for the other two. This is because a k-vector search technique is used in the proposed algorithm. The most important result was that the identification rate of our PTP algorithm was higher than those of the other two algorithms.Table 6
Comparison of the three algorithms (positional noise std. dev = 1 pixel, and magnitude noise std. dev = 0.5 Mv).
Algorithm
Identification rate
Average identification time
Memory requirement (MB)
PTP
96.79%
3.28 ms
0.784
P-vector
94.91%
7.63 ms
0.537
Planar triangle
93.25%
583.75 ms
178


## 4. Conclusion

An effective algorithm for star identification has been developed using the three sides of planar triangles that also incorporates principal component analysis (PCA) and ak-vector technique (PTP). The algorithm generates the star pattern in a projection that is computed using the three sides of the triangle projected on a projection line. The guide database is constructed similarly. For reliability, a projection is used for the initial match, and the adoption of the k-vector range search technique makes this algorithm very fast. Moreover, a sharing star validation method is adopted for the final match. The algorithm presented here can be used in the lost-in-space mode to determine the attitude for a star sensor that has no prior attitude information. Simulation results indicate that our PTP algorithm is more robust against noise than are the P-vector and planar triangle algorithms. In addition, it is seen from the simulation results that the identification rate of the proposed algorithm is comparatively high and the storage of the guide database and the identification speed are both acceptable. The algorithm should be transplanted to a star sensor immediately for supporting a wide variety of missions. However, the algorithm proposed here was not tested on real sky images. We will try to acquire the real images to test the robustness of the algorithm in the future. Another future direction is to track and locate the space object using star sensor technique.



---

*Source: 982420-2015-06-08.xml*