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

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.