Please cite this article as

Please cite this article as: M. Zahednamazi, A.Toloei, Pattern Matching Star Identification Algorithms: Comparison Of Speed And Accuracy, International Journal of Engineering (IJE), IJE TRANSACTIONS A: Basics Vol. 31, No. 4, (April 2018) 184-191

Pattern Matching Star Identification Algorithms: Comparison Of Speed And Accuracy
A B S T R A C T
P A P E R I N F O

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

Keywords: star sensor pattern matching algorithms optimal algorithm for star sensor reliability

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.

1. INTRODUCTION1

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
*Corresponding Author Email:[email protected] (M.Zahednamazi))
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
Economical,
low power

Magnetometer

M. Soolaki et al. / IJE TRANSACTIONS B: Applications Vol. 30, No. 2, (February 2017)
magnetic field strength
and modeling accuracy,
non-precise reference
consumption,
usable in Leo orbit
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 ����
Magnetometer Geomagnetism 1 ����
Gyroscope Inertial frame 0.01 ����/?���
Star 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.
cos(��)=(��? 1.��? 2)
?��? 1?.?��? 2? (1)

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

M. Soolaki et al. / IJE TRANSACTIONS A: Basics Vol. 31, No. 4, (April 2018) 184-191
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 ��?? �,��?? �,��?? � 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.

�=?��?? �?��?? �?,
�=?��?? �?��?? �?,
�=?��?? �?��?? �?
(2)

Figure 3. Combined triangle method (21)

�=1
2(�+�+�)
�����=?�(�?�)(�?�)(�?�)
(3)
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.
�������=�����?(�2+�2+�2)/36 (4)
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:

��1=arccos(�2?�2?�2
?2��) (5)
��2=arccos(�2?�2?�2
?2��)
��3=arccos(�2?�2?�2
?2��)

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.

4.1.quadirateral Algorithm

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

M. Soolaki et al. / IJE TRANSACTIONS B: Applications Vol. 30, No. 2, (February 2017)
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

M. Soolaki et al. / IJE TRANSACTIONS A: Basics Vol. 31, No. 4, (April 2018) 184-191
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.

5.SIMULATION
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

M. Soolaki et al. / IJE TRANSACTIONS B: Applications Vol. 30, No. 2, (February 2017)
.
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.

M. Soolaki et al. / IJE TRANSACTIONS A: Basics Vol. 31, No. 4, (April 2018) 184-191
Table 3.Number of comparison parameters and needed stars
Algorithm
Minumun number of stars
for algorithm
Number of comparison
parameters
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.

6.CONCLUTION
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.

x

Hi!
I'm Dora

Would you like to get a custom essay? How about receiving a customized one?

Check it out
x

Hi!
I'm Barry!

Would you like to get a custom essay? How about receiving a customized one?

Check it out