Pattern Matching Star Identification Algorithms: Comparison Of Speed And Accuracy
pattern matching algorithms
optimal algorithm for star sensor
The present study aimed to examine pattern-matching algorithms in star tracker sensors and compare previous algorithms with four newly proposed algorithms. The innovative algorithms proposed in this article included four pattern matching geometric algorithms, which require at least four or five stars in the sensor field of view. These algorithms were compared with angle, combined triangle, and pyramid algorithms in terms of speed, accuracy, required memory, and resistance to false stars by using simulation performed by MATLAB software. Except for angle algorithm, all proposed algorithms had a high precision and resistance to false stars. Also they had lower speeds than those of the algorithms which use fewer stars to form the pattern. The simulation was related to the stars brighter than magnitude 4, as well as a star sensor with a square-shaped field of view with a dimension of 20° × 20° similar to the CT-631 sensor manufactured by BALL company.
Nowadays, the tool for determining the attitude is regarded as one of the important components on every spacecraft 1,2,3. The need to know the attitude of the spacecraft has led to the innovation of many tools and algorithms, among which we can refer to gyroscope, earth sensor, solar sensor, magnetometers, and star trackers. The tools for measuring the attitude are usually called “attitude sensors” 4. Table 1 and Table 2 indicate the comparison of these sensors with each other and presents the reference frame 4, 5, 6,7. Selecting the appropriate reference frame is an important factor for determining the spacecraft attitude and this is only possible when the direction of spacecraft frame is specified with respect to the reference vectors. Among all the expressed attitude sensors, the star sensor technology is considered a new approach to determine the attitude of the spacecraft by using the star coordinate system as the reference frame. High accuracy (from the second of arc order), high reliability, the possibility to use in deep space exploration, automatic operation and no need for auxiliary sensors are among the significant features of the star sensors 4.
2. PRINCIPLE OF ATTITUDE CALCULATION BY STAR SENSOR
The basic concept used in the star sensor is to locate the local position by observing and analyzing the stars of the sky 4. The star sensor compares the extractable information from the stars in the field of view to a database containing the same information from the stars of the sky. This comparison leads to finding attitude information in the body frame of the star sensor, which can be converted to the body frame of the spacecraft or the Inertial frame of reference 6. Star sensor captures an image from the night sky by the CCD or CMOS. The star image has noises which can be removed by various types of filtering. In the next step, matching the stars related to the spacecraft field of view is performed through the database of information extracted from the
Table 1: Comparison of typical attitude sensors (4,5,6,7)
Disadvantage advandge Sensor
Lack of visibility in eclipse , limited accuracy, and non-precise reference Low weight and power consumption, cheap and simple Sun Sensor
The ability to search to find the horizon,
limited accuracy, non-precise reference,extremely expensive, and heavy and large in precise types Suitable for nearby satellites, easy analysis, integration capability with other sensors Earth Sensor
Low accuracy, usability near the earth, limited by magnetic field strength and modeling accuracy, non-precise reference Economical, low power consumption, usable in Leo orbit Magnetometer
Propagation of error over time, needed for other sensors to correct, and expensive High accuracy in short intervals Gyroscope
Complex, expensivene and time-consuming identification of stars High precision and usability at any point in the sky Star Sensor
identification algorithm. Based on the orientation vectors of the matched stars, the attitude of all three axes is calculated for the star sensor, and the spatial attitude of the spacecraft is determined 4. Fig. 1 illustrates the common process for a star sensor.However, how to extract information from the stars of the field of view is one of the most challenging topics in the software part of the star sensor, which has led to the emergence of many ideas including identification algorithms and search methods in the database.
3. PATTERN RECOGNITION ALGORITHMS
The first successful attempt to develop star identification algorithms was made in 1981 by publishing an article entitled “Star Pattern Recognition and Spacecraft Attitude Determination” 8 by Junkins et al .This paper used the sine of the angle which was formed by stars as a pattern. However, the sky was divided into sections to accelerate the calculations, which was necessary for a preliminary estimate of the spacecraft attitude. Then, Sasaki (1987) used the areas of the triangles formed by stars as an identification pattern 9, 10. In 1992, Liebe presented his algorithm 11. in Liebe method in which
Figure 1: star identification process (4)
Table 2: Reference frame and accuracy of typical attitude sensors (4,5,6,7)
Sensor Reference frame Attitude measurment accuracy
Sun Sensor Sun 1’Earth Sensor Earth horizon 0.3 degMagnetometer Geomagnetism 1 degGyroscope Inertial frame 0.01 deg/hourStar Sensor Star 1″after selecting a star, two other stars which were the closest neighbors to that star were selected. Identification parameters in the Libeh algorithm included the separation angle of each of neighboring stars with the selected star and the mid-angle of these three stars with the centrality of the selected angle. In 1996, Quine only addressed the problem of the search method in the database and proposed a binary search tree method 12. Further, Pedgett (1997) proposed grid algorithm for searching in the database 13. The cells of this grid were considered either on or off in the case of the presence or absence of a star. In the same year, Mortari proposed a new method called K-vector for searching in the database 14, which received a lot of attention. In another study, Hong (2000) suggested the idea of ??using the neural network and fuzzy logic to identify stars 15. Mortari et al. (2004) suggested a pyramid algorithm for star identification 16. In 2008, Kolomenkin conducted some modifications on the Mortari K-vector method 17. So far, the K-vector search method has been revised several times by Moratari et al. 18, 19. This method has the capability to be used for more than one field of view and one dynamic database. Among the geometric star identification algorithms, three well-known algorithms have been selected and compared with four innovative algorithms as follows.
Figure 2.Separation angle between two stars(20)
3. 1. Angle Method
In this method, the pattern matching is performed using the angle between the two-star vectors. Fig. 2 illustrates the way this method is used.
The database of this algorithm consists of the angle between the two stars from the sensor viewpoint. In order to find the angle between stars, the famous dot product Eq. (1) is used20.
Comparing to the other later-discussed algorithms, this algorithm forms the pattern with a minimum number of stars (two stars in the field of view) and requires the least memory for the database, which is, of course, the most important advantage of the algorithm. However, the most important problem of this algorithm is the lack of access to a unique solution in most cases .
3. 2. Combined Triangle Method
In this algorithm, there are three different features, which ultimately lead to the matching of five parameters. These
parameters are the area, polar moment, and the internal angles of the triangle. Fig. 3 demonstrates this algorithm. In this algorithm, the Heron formula was used to find the area of ??the triangle. If V1,V2,V3 indicate vectors from the origin to the corresponding stars in the applied coordinate frame, the sides and area of the triangle are calculated using the Eqs. (2) and (3), respectively. 21.
Figure 3. Combined triangle method (21)
Similar to the triangle area, the polar moment of the triangle is calculated only by knowing the length of the triangle sides and the Eq. (4) 21.
The third feature examined in this algorithm includes the inner angles of the triangle. The equations needed to calculate the internal angles of the triangle are obtained by using the Eq. (5) 20:
The simultaneous use of these three features of the triangle can increase the reliability of the algorithm because five features of three different types can be compared by using only three stars.
3. 3. Pyramid Method
This algorithm was proposed by Mortari in 2004 and required at least four stars in the field of view. In the first step, the algorithm selects three stars from the stars in the field of view to form a triangle. The internal angles of this triangle are calculated by using Eq .(5). The fourth star, called the reference star, is selected among other stars of the field of view. In the next step, the angle between this reference star and each of the stars located at the vertices of the triangle is calculated, and thus six parameters are examined. If this algorithm fails to obtain a unique response, another reference star is selected among other stars of the field of view. Fig. 4 represents this algorithm 16.
Figure 4: Pyramid method(16)
In this algorithm, the maximum information is extracted from the four stars of the field of view, which is the main advantage of this algorithm and significantly increases its reliability. This method has been tested on the HETE satellite 16.
4. NOVEL ALGORITHMS
In the following, the innovative algorithms for pattern matching are investigated and compared.
Similar to the pyramid algorithm, this algorithm can be used when there are at least four stars in the field of view of star sensor. In this algorithm, the internal angles of the stars are calculated (using Eq. (1)) on a plane containing four stars from the stars of the field of view, and thus, a quadrilateral is formed. The pattern matching can be performed by comparing the information obtained from the observation of the stars of the field of view with the database containing the information extracted from this algorithm.
4.2. Pentagon Algorithm
This algorithm is the simplest algorithm, which requires at least five stars in the field of view. In this algorithm, five stars are chosen from the stars of the field of view to form a planar pentagon. Each pair of neighboring stars specify a vector and the angle between two vectors is calculated by using the well-known dot product of vectors (Eq.(1)).
4.3.Square Pyramid Algorithm
This algorithm requires at least five stars to form the desired pattern. In this algorithm, four stars are selected from the stars of the field of view and form a quadrilateral. In the next step, the internal angles of this quadrilateral are calculated on the plane passing through these four stars.
Figure 5. Square pyramid method
Figure 6 .Flow diagram of square pyramid method
Further, another star is selected among the other stars of the field of view and the angle of this star is calculated with each of the stars located in the vertices of the quadrilateral (Fig. 5). The pattern matching is performed by comparing the information extracted from the stars of the field of view to the database. Fig. 6 depicts the flowchart of this algorithm.
4.4.Triangular di Pyramid Algorithm
The triangular di pyramid algorithm is the last algorithm, which requires at least five stars in the field of view to form a pattern. In the first step, a planar triangle is created using three stars among the stars of the field of view. The internal angles of this triangle are calculated using Eq. (5).
Figure 7 . Triangular di pyramid method
Then, two stars are selected from the other stars of the field of view to form the triangular di pyramid structure, and the angles of each of these two stars are calculated with the stars located at the vertices of the triangle from the sensor viewpoint (Fig. 6). This algorithm includes nine parameters, three of which are the internal angles of the triangle. The six remaining parameters are the angles of each of the two stars with stars located at the vertices of the triangle. Fig. 8 presents the steps for implementing this algorithm.
In the present study, simulations were performed for stars brighter than magnitude 4 with 200 repetitions for angle, combined triangle, pyramid, quadrilateral, pentagon, square pyramid and triangular di pyramid algorithms. The minimum stars required in the field of view are two for angle method, three for combined triangle method, four for quadrilateral and pyramid methods, and five for pentagon, square pyramid, and triangular di pyramid methods. The algorithms are compared with each other in terms of correct results, speed, resistance to false stars and required memory for database. The considered field of view is a square-shaped field of view with the dimension of 20° × 20° similar to that of the CT-631 star sensor manufactured by BALL Corporation (U.S.). For a better understanding of the distribution of stars in the sky Figs. 9 and 10 display two-dimensional and three-dimensional simulations, respectively .
Figure 8. Flow diagram of triangular di pyramid method
Figure 9.Star Catalog(2-Dimention)
Figure 10. Star Catalog (3-Dimention) in ECI
Figure 11. Real and False Stars in one Frame
The two-dimensional simulations were performed by using right ascension and declination angles (Fig. 9), while 3D simulation was carried out in the ECI coordinate system (Fig. 10). Fig. 11 shows false and real stars in the star sensor field of view, simultaneously. The error related to the false stars is one of the errors with which a star sensor may encounter. False stars are objects which appear in the sensor field of view but are not actually stars. These objects can be satellites or other objects which are wandering in space. In order to evaluate the resistance of algorithms against false stars, their number is equal to the stars of the field of view in the simulation process. Fig. 13 shows that the capability .
Figure 13. Comparison of algorithms in the absence of false stars
Figure 14. Comparison of algorithms in presence of false stars
of algorithms is investigated without regarding the false stars. The simulation results indicated that the angle algorithm fails to produce the correct results in most cases. Therefore, this algorithm is not appropriate to be used in the star sensor despite the minimum number of needed stars to form a pattern. In the following, the reliability of other algorithms is measured against false stars (Fig. 14). Based on the results, it is clear that all of these algorithms are resistant to false stars. Another important feature which is considered in the algorithms is their response speed. Fig. 15 demonstrates the average increase in the search time for combined triangle, quadrilateral, and pyramid algorithms for the magnitudes 1, 2, 3 and 4. Fig. 16 compares algorithms which need at least five stars in the field of view. Regarding the graphs presented in Figs. 15 and 16, it is clear that the response time for algorithms with five stars in the field of view is 10 times greater than that of the algorithms with 3 and 4 stars in the field of view. The required memory by an algorithm is regarded as the last examined feature.
Figure 15. Comparison of response time for algorithms
Figure 16. Comparison of response time for novel algorithms
Figure 17. Required memory for algorithms
This feature is very important because the memory capacity of a star sensor is not infinite, and the amount of its memory capacity should be considered in order to apply an algorithm to the star sensor. Fig. 17 represents the comparison of the required memory for the algorithms examined in this paper for a different number of available stars.
Table 3.Number of comparison parameters and needed stars
Algorithm Minumun number of stars
for algorithm Number of comparison
angle 2 1
Combined triangle 3 5
Pyramid 4 6
quadilateral 4 4
Pentagon 5 5
Square pyramid 5 8
Triangular di pyramid 5 9
Finally, Table 3 presents a general comparison between previous and innovative algorithms in terms of the number of needed stars in the field of view and the number of parameters that can be extracted from each of the algorithms.
In the present study, seven pattern-matching algorithms were investigated for a star sensor in terms of response time, correct results, memory capacity required for the database, and resistance to false stars. The angle algorithm failed to get a unique response in most cases because it only examined one parameter. In other algorithms, which needed 3, 4 and 5 stars to form a pattern, an increase in the number of stars for forming a pattern by one, decreased the number of unique responses by about 10%, which is related to the inadequate number of stars in the field of view to form the desired pattern. In addition, the average ratio of search time was about 10 times in algorithms, which required at least 5 stars to form a pattern with respect to the algorithms which required at least four stars to form a pattern. Among all simulated algorithms, the triangular di pyramid algorithm had the highest number of comparable parameters and compared nine parameters. This algorithm compared three parameters more than that of the accepted pyramid algorithm, although it only required one more star to form the pattern. Among all the algorithms mentioned above, combined triangle, pyramid and the innovative triangular di pyramid algorithms are more suitable for use in the star sensor, since they form the best structure and extract more information compared to the algorithms which require an equal number of stars to form a pattern (Table 3). These algorithms are all suitable for use in the star sensor although the best algorithm to be used in each sensor highly relies on the required accuracy, sensor technology, field of view dimensions, and search method.