Open AccessArticle

An Autonomous Star Identification Algorithm Based on One-Dimensional Vector Pattern for Star Sensors

Liyan Luo

Luping Xu

^* and

Hua Zhang

School of Aerospace Science and Technology, Xidian University, Xi'an 710126, China

Authors to whom correspondence should be addressed.

Sensors 2015, 15(7), 16412-16429; https://doi.org/10.3390/s150716412

Submission received: 21 May 2015 / Revised: 24 June 2015 / Accepted: 2 July 2015 / Published: 7 July 2015

(This article belongs to the Section Physical Sensors)

Download

Browse Figures

Figure 1
Stellar image in star sensor. (a) Celestial sphere reference frame; (b) The imaging principle in star sensor; (c) The stars observed in FOV. "> Figure 2
The vector direction of the star pattern. (a) The alignment star; (b) The stellar image is rotated. "> Figure 3
Generation of the one-dimensional vector pattern. (a) The positions of the observed stars on oʹxʹ axis; (b) The plane included angles. "> Figure 4
Recognition rate with different neighborhood radiuses R. "> Figure 5
Recognition rates vs. positional noise (F: false star, L: lost star). "> Figure 6
Recognition rate vs. false stars. (a) Recognition rate with 1 false star; (b) Recognition rate with 2 false stars; (c) Recognition rate with 3 false stars. "> Figure 7
The recognition rates of different algorithm with false stars. (a) Recognition rate with 1 lost star; (b) Recognition rate with 2 lost stars. ">

Versions Notes

Abstract

In order to enhance the robustness and accelerate the recognition speed of star identification, an autonomous star identification algorithm for star sensors is proposed based on the one-dimensional vector pattern (one_DVP). In the proposed algorithm, the space geometry information of the observed stars is used to form the one-dimensional vector pattern of the observed star. The one-dimensional vector pattern of the same observed star remains unchanged when the stellar image rotates, so the problem of star identification is simplified as the comparison of the two feature vectors. The one-dimensional vector pattern is adopted to build the feature vector of the star pattern, which makes it possible to identify the observed stars robustly. The characteristics of the feature vector and the proposed search strategy for the matching pattern make it possible to achieve the recognition result as quickly as possible. The simulation results demonstrate that the proposed algorithm can effectively accelerate the star identification. Moreover, the recognition accuracy and robustness by the proposed algorithm are better than those by the pyramid algorithm, the modified grid algorithm, and the LPT algorithm. The theoretical analysis and experimental results show that the proposed algorithm outperforms the other three star identification algorithms.

Keywords:

star sensor; star identification; one-dimensional vector pattern; star pattern

1. Introduction

Celestial navigation has a broad application prospect in the automated sky survey system and the deep space exploration. Star sensors have good autonomy, high precision and work reliably, and they play an important role in the celestial navigation. In the “lost-in-space” mode, star sensors can automatically determine the spacecraft attitude [1,2,3] without a priori attitude information. The performance of the star identification algorithm directly affects the attitude determination of the spacecraft. The recognition accuracy of the star identification algorithm affects the system precision of star sensor, and the recognition speed of star identification affects the responsiveness of star sensor. Therefore, a rapid and robust star identification algorithm is necessary.

During the past few decades, many star identification algorithms have been created which are widely used in the spacecraft attitude determination and control when no a priori attitude information is available [4]. The star identification algorithms mainly include the polygon algorithm [5,6,7,8,9,10,11,12,13,14,15], the match group algorithm [16], the grid algorithm [17,18,19,20,21], the neural network algorithm [22,23,24], the genetic algorithm [25,26], and so on, which can be roughly classified into two basic categories [27]: subgraph isomorphism and pattern recognition.

The triangle algorithm [10,11] is a classical star identification algorithm and many other star identification algorithms are derived from it. In the triangle algorithm, every three observed stars forms a triangle and its angular distances are adopted as the feature for star identification. However, there are many stars existing at small angular distances which are difficult to distinguish from each other under the noise interference. In addition, the angular distance is sensitive to noise, which is easy to cause mismatching. The polygon algorithm is derived from the triangle algorithm. Since the dimension of the identification feature is limited in the polygon algorithm, a lot of the information of the stars observed in the field of view (FOV) cannot be efficiently used. Although the increase of the dimension of the identification feature can improve the utilization of the stars’ information, the recognition algorithm is complicated which is not good for star identification. Mortari et al. [7] used five observed stars to increase the dimension of the identification feature, which can reduce the redundant matching to some extent. Moreover, some improved algorithms have been proposed to solve the existing problem in the triangle star identification algorithm [12,13,14,15]. But the inherent shortcomings of the triangle algorithm cannot be solved thoroughly.

The pattern-based star identification algorithm has incomparable advantages compared with the subgraph-isomorphism-based star identification algorithm, and much effort has been made in research about the pattern-based star identification.

In 1997, Padgett et al. [17] proposed the grid algorithm for autonomous star identification in which the star recognition problem is converted into the comparison of the two 0–1 strings. In the grid algorithm, multiple pixels are divided into a grid cell, so this algorithm is insensitive to the positional noise. But the measurement precision of the magnitude and the choice of the subaltern star have great impact on the accuracy and reliability of the grid algorithm. Lee et al. [18,19,20,21] proposed a modified grid algorithm in which the recognition accuracy is better than that of the original one. Both the original grid algorithm and the modified grid algorithms need to store the entire star pattern, so they require more memory space to store the feature database. In addition, the size of the feature database increases with the increase of the grid cells.

Wei et al. [28] used the Log-Polar transform to convert the rectangular coordinate system into the polar coordinate system in which the translation and rotation of the observed stars is simplified as the displacement operation. The LPT algorithm has a strong anti-interference ability against position noise and the magnitude noise. But a lot of time will be taken in the search for the matching star pattern of the observed star pattern in the feature database. In recent years, some novel star identification algorithms have been proposed, such as the singular value method [29], the vector pattern matching method [30], the pattern code method [31], and so on [16,32,33,34,35,36,37,38]. These algorithms have the same goal which is to identify the stars as quickly and robustly as possible and they solve the problem of star identification in different aspects. However, there still is no optimal star identification algorithm to date.

In order to reduce the time-consumed and enhance the robustness of star identification, we propose an autonomous star identification algorithm based on the one-dimensional vector pattern. In this method, the main star and the alignment star are chosen to reset the new coordinate axes firstly. That makes it possible to establish the one-to-one relationship between every navigation star and its one-dimensional vector pattern. Secondly, all stars observed in FOV are projected onto the new coordinate axes using the rotation matrix. Then the observed stars, locating in the neighboring region of the main star, are used to build the one-dimensional vector pattern of the main star. Finally, the feature vector of the main star can be achieved according to the one-dimensional vector pattern.

The one-dimensional vector pattern not only describes the position information of the observed stars, but also expresses the angular information between the observed stars and the horizontal axis. The one-dimensional vector pattern can fully express the space geometry information of the stars observed in FOV, which has greatly contributed to the star identification. In addition, the one-dimensional vector pattern of the same navigation star remains unchanged when the stellar image rotates, so there is a one-to-one relationship between the navigation star and its one-dimensional vector pattern, which makes it possible to identify the observed star quickly.

The rest of this paper is organized as follows. In Section 2, the one-dimensional vector pattern is introduced in detail. The star pattern generation and the identification process are described in Section 3. The simulation conditions are introduced in Section 4. In Section 5, the simulation results and the numerical analysis are given. Finally, in Section 6, the concluding remarks are made.

2. Description of the One-Dimensional Vector Pattern

Generally, the position information and the magnitude of the navigation star are considered as the basic characteristics of the navigation star. In many star identification algorithms, the position information is used to build the geometric feature to identify the navigation star. The magnitude of the navigation star also can be used to identify the navigation star. However, the magnitude is unstable and it is used only for the rough estimation. In this paper, only the position information of the navigation star is used to identify the navigation star.

2.1. The Imaging Principle in Star Sensor

The star catalog and astronomical almanac express a star’s position in terms of its right ascension α and declination β in the celestial sphere reference frame (see Figure 1a). The parallel light from stars is imaging on the focal plane of the charge-coupled device (CCD) in star sensor, so the position of the star in the celestial sphere reference frame is expressed in terms of pixels along the x and y axes on the stellar image (see Figure 1b). The light points on the stellar image are the stars observed in FOV (see Figure 1c), which are the research objects in star identification. Before the experiment, it needs to simulate the stellar image according to the information of the navigation stars in the star catalogue.

Figure 1. Stellar image in star sensor. (a) Celestial sphere reference frame; (b) The imaging principle in star sensor; (c) The stars observed in FOV.

Generally, only the plane position of the observed star can be achieved in star sensor. During the process of star recognition, the geometric position relationships among the observed stars are adopted to identify the positions of the observed stars in the celestial sphere reference frame. In the simulation experiments, the right ascension and declination of the navigation star in the celestial sphere reference frame need to be converted into the plane coordinates firstly. The transformation relation can be expressed as

\begin{array}{l} x_{r} = \frac{N_{x} cos β sin (α_{i} - α)}{2 tan (F O V_{x} / 2) (sin β_{i} sin β + cos β_{i} cos β cos (α_{i} - α))} \\ y_{r} = \frac{N_{y} (sin β_{i} cos β - cos β_{i} sin β cos (α_{i} - α))}{2 tan (F O V_{y} / 2) (sin β_{i} sin β + cos β_{i} cos β cos (α_{i} - α))} \end{array}

(1)

where (N_x, N_y) is the resolution of CCD in star sensor, (FOV_x, FOV_y) is the FOV of CCD, (α_i, β_i) is the right ascension and declination of the ith observed star, and (α, β) is the optical axis direction of CCD. The optical axis direction of CDD points to the position of the star in the celestial sphere reference frame, which is projected on the center of the stellar image. The centroid coordinates (x_r, y_r) are used as the actual centroid coordinates of the navigation star in the simulation experiments.

2.2. The One-Dimensional Vector Pattern

Aiming at the improvement of the speed of star identification, the one-to-one relationship between the navigation star and its one-dimensional vector pattern is built in the proposed algorithm. In order to achieve the unique pattern of the navigation star, the centroid coordinates of stars observed in FOV are reset. In the process of star identification, one of the observed stars is chosen as the main star, and the observed stars located in the neighboring region with a radius of R (see Figure 2) are called the neighbor stars of the main star. The star pattern of the main star consists of the main star and its neighbor stars. The nearest neighbor star is regarded as the alignment star of the main star. The direction from the main star to the alignment star is considered as the vector direction of the star pattern.

Figure 2. The vector direction of the star pattern. (a) The alignment star; (b) The stellar image is rotated.

In order to achieve the unique star pattern when the stellar image rotates, the centroid coordinates of the observed stars are reset based on the vector direction of the star pattern. The centroid coordinates of the star observed in FOV is expressed as (x, y) on the stellar image in oxy coordinates. The centroid coordinates of the main star and the alignment star are set to be (x_s, y_s) and (x_a, y_a), respectively. The direction from the main star to the alignment star is expressed as

\vec{s_{s} s_{a}}

, which is denoted as the oʹxʹ axis among the new coordinate axes (see Figure 2). The plane included angle θ_r between the ox axis and the oʹxʹ axis is expressed as

θ_{r} = 〈 \vec{s_{s} s_{a}}, \vec{o x} 〉 = arctan (\frac{y_{a} - y_{s}}{x_{a} - x_{s}})

(2)

The plane included angle θ_r is set to be positive from the ox axis to

\vec{s_{s} s_{a}}

on counterclockwise. The stellar image is rotated with the angle of θ_r, and the vector direction is denoted as the oʹxʹ axis. The right-hand rule is used to obtain the oʹyʹ axis, and then the centroid coordinates of the stars are expressed in terms of pixels along xʹ and yʹ axes in the oʹxʹyʹ coordinates. The new centroid coordinates of the observed stars in the oʹxʹyʹ coordinates will be achieved using Equation (3).

[\begin{array}{l} x^{'} \\ y^{'} \end{array}] = [\begin{array}{l} cos θ_{r} sin θ_{r} \\ - sin θ_{r} cos θ_{r} \end{array}] [\begin{array}{l} x \\ y \end{array}] + [\begin{array}{l} Δ x \\ Δ y \end{array}] = M [\begin{array}{l} x \\ y \end{array}] + [\begin{array}{l} Δ x \\ Δ y \end{array}]

(3)

where (x, y) are the centroid coordinates of the observed star in the oxy coordinates, and (xʹ, yʹ) are the new centroid coordinates of the corresponding observed star in the oʹxʹyʹ coordinates, and M is the rotation matrix. The offsets between the origin of the oxy coordinates and the origin of the oʹxʹyʹ coordinates can be expressed as

Δ x = x_{0} - x_{s}, Δ y = y_{0} - y_{s}

(4)

where (x₀, y₀) is the origin of the oxy coordinates. Generally, x₀ = 0 and y₀ = 0, so the offsets can be rewrote as

Δ x = - x_{s}, Δ y = - y_{s}

As described above, the new centroid coordinates of the observed stars can be achieved using Equation (5), when the stellar image rotates with the plane included angle of θ_r.

[\begin{array}{l} x^{'} \\ y^{'} \end{array}] = [\begin{array}{l} cos θ_{r} sin θ_{r} \\ - sin θ_{r} cos θ_{r} \end{array}] [\begin{array}{l} x \\ y \end{array}] + [\begin{array}{l} - x_{s} \\ - y_{s} \end{array}] = M [\begin{array}{l} x \\ y \end{array}] + [\begin{array}{l} - x_{s} \\ - y_{s} \end{array}]

(5)

The relative position of every two observed stars remains unchanged when the stellar image rotates. The main star locates on the origin of the oʹxʹyʹ coordinates. The horizontal axis coordinates of the observed stars in the star pattern indicate the positions of these stars on the oʹxʹ axis (see Figure 2a). Set the plane included angle between the neighbor star and the alignment star as θ, and the plane included angle along the counterclockwise as positive (see Figure 2b). The positions and the plane included angles of the observed stars in the star pattern are adopted as the characteristics of the star pattern. The one-dimensional vector pattern of the star pattern can be expressed

V = {(x_{1}^{'}, θ_{1}), \dots, (x_{n}^{'}, θ_{n})} = {(x_{i}^{'}, θ_{i})}, i = 1, \dots, n

(6)

where

x_{i}^{'}

is the horizontal axis coordinate of the ith neighbor star, and θ_i is the plane included angle between the ith neighbor star and the alignment star, and n is the number of the observed stars in the star pattern.

According to the centroid coordinates of the observed stars in the star pattern, the plane included angle between the neighbor star and the alignment star can be achieved using Equation (7).

θ_{i} = {tan}^{- 1} (y_{i}^{'} / x_{i}^{'})

(7)

It should be noted that the plane included angle between the neighbor star and the alignment star ranges from −180° to +180°. The centroid coordinates of the main star is (0, 0) in oʹxʹyʹ coordinates, and the plane included angle of the alignment star is 0°.

The one-dimensional vector pattern not only expresses the position information of the observed stars, but also describes intuitively the information of the plane included angles between the neighbor stars and the alignment star, which can fully express the space geometry information of the observed stars in FOV.

3. Generation of the Feature Vector and the Process of Star Identification

3.1. Generation of the Feature Vector

In order to enhance the robustness of the proposed algorithm, the oʹxʹ axis within the scope of 2R is divided at regular intervals (see Figure 3b). Set the resolution of the oʹxʹ axis locating in the neighboring region of the main star be m, so the interval on the oʹxʹ axis will be 2R/m. The feature vector of the main star can be achieved according to the results of the one-dimensional vector pattern. So the feature vector of the main star can be expressed as

p a t (s) = (a_{1}, a_{2} \dots, a_{m}) = {a_{j}}, j = 1, \dots, m

(8)

As described above, the pattern of the main star is expressed as a 1 × m vector pat (s). Each value in pat (s) indicates that whether there are observed stars whose horizontal axis coordinates are located in the corresponding interval or not. For every value in pat (s), that is

a_{j} = {\begin{matrix} θ_{i}, & x_{i} \in [(j - 1) \times 2 R / m, j \times 2 R / m) \\ 0, & e l s e \end{matrix}, (x_{i}, θ_{i}) \in V, i \in (1, \dots, n), j \in (1, \dots, m)

(9)

where [(j − 1) × 2R/m, j × 2R/m) is the scope of the jth value in pat (s) on the oʹxʹ axis, and n is the number of the observed stars in the star pattern, and V is the one-dimensional vector pattern of the star pattern.

If there is more than one observed star whose horizontal axis coordinates locate in the jth interval of the oʹxʹ axis, the maximum plane included angle among these observed stars will be chosen as the value of a_j. That is

a_{j} = max {θ_{1}, \dots, θ_{p}}

(10)

where p is the number of the observed stars whose horizontal axis coordinates locate in the jth interval of the oʹxʹ axis. If there has no observed star whose horizontal axis coordinate locates in the jth interval, a_j = 0.

Figure 3. Generation of the one-dimensional vector pattern. (a) The positions of the observed stars on oʹxʹ axis; (b) The plane included angles.

3.2. Process of Star Identification

The feature vector of every navigation star can be achieved according to the extraction method of the feature vector described above, and all these feature vectors form the feature database of the navigation stars. During the process of star identification, one of the stars observed in FOV is chosen as the main star, which will be used to build the feature vector with its neighbor stars. Then the feature vector of the main star will be compared with the feature vectors in the feature database to find the matching star pattern.

Let the feature vector of the navigation star in feature database be pat(c), and the feature vector of the star observed in FOV be pat(s).The similarity between pat(s) and pat(c) is measured by the summation of the absolute differences of the two feature vectors. The summation of the absolute differences of the two feature vectors can be expressed as

d i f f (p a t (s), p a t (c)) = \sum a b s (p a t (s) - p a t (c)), c = 1, \dots, N

(11)

where N is the number of the navigation stars in the feature database. The smaller the summation, the more similar the two feature vectors become. As described above, the comparison of the two star patterns is converted into the comparison of the two vectors, which greatly simplifies the problem of star identification.

In order to accelerate star identification and avoid searching the entire feature database to find the matching star pattern, a search strategy is proposed to achieve the matching result as quickly as possible. That is the number of the non-zero values in the feature vector is used to constraint the search scope in the feature database.

Assume that the number of the non-zero values in pat(s) is L_s, then the feature vectors in the feature database with the number of the non-zero values between L_s − ε₁ and L_s + ε₂ will be compared with pat(s). Therefore, it can quickly achieve the matching result with fewer comparisons instead of the searching through the entire feature database. So the process of star identification can be expressed as

\begin{matrix} r e s u l t = min_{c} (d i f f (p a t (s), p a t (c))), L_{c} \in [L_{s} - ε_{1}, L_{s} + ε_{2}] \\ min_{c} (d i f f (p a t (s), p a t (c))) \leq ε_{0} \end{matrix}

(12)

where L_c is the number of the non-zero values in pat(c), ε₁ and ε₂ are the tolerances of the number of the non-zero values, and ε₀ is the pre-set value. The difference between the best matching pattern and the main star pattern is smallest among the comparison results. Meanwhile, the smallest difference is not larger than the pre-set value.

From the above description, the record of every star pattern in the feature database can be expressed as

m Re c o r d = {i d, L_{c}, p a t (c)}, c = 1, \dots, N

(13)

where id is the index of the navigation star.

4. Simulation Conditions

4.1. Parameter Setting for Star Sensor

The Tycho-2 catalogue is used as the source of the navigation stars data. Some stars in the star catalogue may be lack of brightness or location information, so that they cannot be chosen as the navigation stars. Due to the limitation of the resolution of CCD in star sensor, it cannot clearly distinguish the two stars when they appear too close. In this paper, two stars apart less than 20 pixels apart (about 0.39°) are considered binary stars, which cannot be chosen as the navigation star. Therefore, there are 6685 stars to be chosen as the navigation stars whose apparent magnitudes range from 1.0 Mv to 6.5 Mv. Each of the navigation stars is chosen in turn as the optical axis direction of CCD to implement the process of star identification. The resolution of the simulated stellar image is 1024 × 1024 pixels with a 20° × 20° FOV. The average number of the stars observed in FOV is 30.32, with 68 as the maximum and 3 as the minimum. The experiments are carried out using a microcomputer with a 3.20 GHz Pentium (R) Dual-Core, 1.96 GB RAMS. All tests are carried out in the same simulation conditions.

The achievable performance of the proposed algorithm is demonstrated via a comparison study between the pyramid algorithm [8], the modified grid algorithm [20] and the LPT algorithm [28]. This paper has revealed the influence of the positional noise, the false stars, and the lost stars on the star identification in the four star identification algorithms. The complexity of the proposed algorithm was also compared with that of the other three algorithms.

Due to the characteristics of the star pattern, the observed stars close to the center of FOV are chosen as the main stars to complete the star identification. The attitude of the spacecraft can be calculated based on the position information of every three observed stars [1]. Therefore, the identification process is considered to be unsuccessful when the number of stars observed in FOV is less than three.

4.2. Selection of the Identification Parameters

As is well known, a lot of the geometric information about the observed stars located on the edge of FOV is lost. In order to obtain the geometry information out of the observed stars as much as possible, the observed stars near the center of FOV are chosen as the main stars in this paper. The resolution of the oʹxʹ axis locating in the neighboring region of the main star is set to be m = 100. During the process of star identification, the tolerances of the number of the non-zero values are set to be ε₁ = ε₂ = 1, and the pre-set value ε₀ is set to be 172 in experience.

The number of the observed stars in the neighbor region is different with the different neighborhood radius for the same main star. So the choice of the neighborhood radius R will affect the number of the neighbor stars of the main star, so as to affect the star pattern of the main star. Therefore, it is necessary to choose an appropriate neighborhood radius R. If R is too small, much geometric information of the stars observed in FOV will be ignored, and it cannot be possible to structure the unique pattern for every navigation star. If R is too large, the amount of the geometric information of the observed stars is too large to be easily manipulated. In addition to this, the star pattern is sensitive to noise when R is too large, which is rather obvious when the main star locates on the edge of the FOV.

In this section, we discuss the recognition accuracy of the proposed algorithm under different neighborhood radiuses. Figure 4 shows the statistics results without any noise that every navigation star is adopted as the direction of the optical axis when R ranges from 3° to 10°. It can be found from Figure 4 that the recognition rate of the proposed algorithm changes with the increase of R. The recognition rate is very low when R is small, and subsequently the recognition rate increases with the increase of R. It achieves the largest recognition rate when R = 6°, then the recognition rate falls down with the increase of R. In the subsequent tests, the neighborhood radius is set to be R = 6°.

Figure 4. Recognition rate with different neighborhood radiuses R.

5. Experiment Results and Analysis

The evaluation criteria of the star identification algorithm mainly includes the influence of positional noise, false stars, lost stars on the recognition accuracy of star identification, the recognition speed of star identification, and memory usage. In this section, we describe the performance of the four star identification algorithms under the same simulation conditions.

5.1. Performance of Different Algorithms under Positional Noise

There are many different noises [39] in star sensors, and the positional noises are simplified in this paper. The positional noises are directly added into the actual centroid coordinates of the stars observed in FOV to investigate the robustness of the four star identification algorithms in terms of the positional noise.

Figure 4 shows the recognition rates of the four star identification algorithms in which only the positional noises are added. The results show that the anti-noise ability of the proposed algorithm is better than that of the pyramid algorithm, the modified grid algorithm, and the LPT algorithm. The recognition rate of the proposed algorithm is up to 98.55% when the positional noise is 0.5 pixels, while the recognition rates of the pyramid algorithm, the modified grid algorithm, and the LPT algorithm are just about 96.76%, 97.61%, and 91.76%, respectively.

It can be known from Figure 5 that the recognition rate of the proposed algorithm is higher than that of the other three algorithms, and the downtrend of the recognition rate of the LPT algorithm is greater than that of the other three algorithms. With the increase of the positional noise, the recognition rate of the proposed algorithm decreases just about 1.37%, while the recognition rates of the pyramid algorithm, the modified grid algorithm, and the LPT algorithm decrease about 3.06%, 1.43%, and 7.89%, respectively. From the analysis data, it can be found that the downtrend of the modified grid algorithm is similar to that of the proposed algorithm with the increase of the positional noise, and the LPT algorithm is sensitive to the positional noise which has the biggest decline of 7.89%.

As can be seen by the above description, the proposed algorithm outperforms the pyramid algorithm, the modified grid algorithm, and the LPT algorithm in terms of the positional noise.

Figure 5. Recognition rates vs. positional noise (F: false star, L: lost star).

5.2. Performance of Different Algorithms under False Stars

Space debris and spacecraft, which may be mistaken as the observed stars (false stars), will affect the performance of the star identification algorithm. In this section, false stars will be added on the simulated stellar image to verify the performance of the star identification algorithm. The positions of false stars are random on the simulated stellar image.

Figure 6 shows the statistical results of the recognition rates of the four algorithms for all 6685 navigation stars with the number of false stars ranging from 1 to 3. In Figure 6, without positional noise, the identification rate of the proposed algorithm decreases from 99.80% to 98.90% when the number of the false stars increases from 1 to 3. Under the same conditions, the rate of the pyramid algorithm decreases from 92.85% to 80.27%, and the rate of the modified grid algorithm decreases from 99% to 86.50%, and the rate of the LPT algorithm decreases from 98.47% to 95.46%. It can be found that the recognition rates of the four algorithms decrease 0.9%, 12.58%, 12.5%, and 3.01%, respectively.

As can be seen by the above analysis, the declines of the recognition rates of the pyramid algorithm and the modified grid algorithm are large with the increase of the number of the false stars, while the false stars have little impact on the recognition rate of the proposed algorithm. Therefore, the proposed algorithm outperforms the pyramid algorithm, the modified grid algorithm, and the LPT algorithm in terms of the false stars.

Figure 6. Recognition rate vs. false stars. (a) Recognition rate with 1 false star; (b) Recognition rate with 2 false stars; (c) Recognition rate with 3 false stars.

5.3. Performance of Different Algorithms under Lost Stars

Some stars in the sky may not be captured by CCD (lost stars) because of the obstruction of other spacecraft or the hardware failure of the star sensor. In tests, the observed stars on the simulated stellar image are deleted randomly. The observation is meaningless when excessive lost stars are deleted from the stellar image. So the number of the lost stars deleted from the stellar image ranges from 1 to 2 in this paper.

Figure 7 shows the statistical results of the recognition rates of the four algorithms for all 6685 navigation stars with the number of the lost stars ranging from 1 to 2. From the results it can be found that the recognition rate of the proposed algorithm decreases from 98.67% to 97.7% when the lost stars are deleted without any positional noise. While the recognition rate of the pyramid algorithm decreases from 91.59% to 84%, and the modified grid algorithm decreases from 97.4% to 96.8%, and the LPT algorithm decreases from 98.67% to 96.27%. The declines of the four algorithms are 0.97%, 7.59%, 0.6% and 2.4%, respectively. Based on the analysis results, the pyramid algorithm is sensitive to the lost stars. Although the decline of the proposed algorithm is not as good as that of the modified grid algorithm, the recognition rate of the proposed algorithm is better than that of the other three algorithms.

As can be seen by the above description, the proposed algorithm outperforms the pyramid algorithm, the modified grid algorithm and the LPT algorithm in terms of the lost stars.

Figure 7. The recognition rates of different algorithm with false stars. (a) Recognition rate with 1 lost star; (b) Recognition rate with 2 lost stars.

5.4. Identification Time and Memory Usage

The identification time and the memory usage should be taken into account in the practical application of the star identification algorithm. The identification times and the memory usages of the four star identification algorithms are summarized in Table 1.

Table 1. Identification time and memory usage of different algorithms.

**Table 1.** Identification time and memory usage of different algorithms.
Identification Algorithm	Max Time/s	Min Time/s	Average Time/s	Database Size
Pyramid	0.0610	4.0061 × 10⁻⁴	0.0275	130.57 KB
M. Grid	0.5886	0.0279	0.3946	7.38 MB
LPT	0.0811	0.0718	0.0738	665.89 KB
Proposed algorithm	0.0196	3.3496 × 10⁻⁴	0.0078	280.72 KB

The identification time of star identification is measured by the average identification time for the 3000 simulations. It can be found from the Table 1 that the proposed algorithm is most time-saving than the other three algorithms, which has an average identification time of 7.8 ms. In the proposed algorithm, the search scope of the matching pattern is constrained by the number of the non-zero values in the feature vector, which makes it able to achieve the identification result just with fewer comparisons. In addition, the feature vector of every star pattern is unique in the proposed algorithm, and the comparison of every two star pattern is simplified as the comparison of the two feature vectors.

In the modified grid algorithm, the comparison of two star patterns requires g × g logical AND operations, and the logical operations increase with the increase of the grid cells. Meanwhile, it needs to search the entire feature database to find the best matching pattern. Hence, the modified grid algorithm is time-consuming and its average identification time is longest at 0.3946 s.

The pyramid algorithm utilizes the k-vector approach to find the candidate matching results, which has no need to search the entire feature database to find the matching result, so it can accelerate the star identification to some extent.

The LPT algorithm has an average identification time of 73.8 ms, which is larger than that of the pyramid algorithm and smaller than that of the modified grid algorithm. The average identification time of the LPT algorithm is about 10 times of that of the proposed algorithm. In the Log-Polar algorithm, the feature vector needs to be shifted circularly for some time when two feature vectors are compared, which is time-consuming. Moreover, it needs to search the entire feature database to find the identification result.

In terms of the memory usage, the modified grid algorithm requires the most memory with a feature database of 7.38 MB, which will increase with the increase of the number of grid cells. The pyramid algorithm has the smallest feature database among these algorithms, because the dimension of its feature vector is lowest compared with the other algorithms. Although the feature database of the proposed algorithm is larger than that of the pyramid algorithm, it is acceptable and supported by the available hardware.

From the simulation results, we can make the conclusion that the proposed algorithm outperforms the pyramid algorithm, the modified grid algorithm, and the LPT algorithm in terms of positional noise, false stars, lost stars, and star recognition time. Despite the fact that the memory requirement for the proposed algorithm is more than that of the pyramid algorithm, it is supported by the available hardware.

6. Conclusions

An autonomous star identification algorithm has been proposed based on the one-dimensional vector pattern, in which the feature vector of the star pattern remains unchanged when the stellar image rotates. Compared with the pyramid algorithm, the modified grid algorithm, and the LPT algorithm, the star identification algorithm proposed in this paper has advantages of high recognition accuracy and good noise resistance ability. Moreover, the computational complexity of the proposed algorithm is lower than that of the other three star identification algorithms. The innovations of the proposed algorithm mainly include:

(1): Compared with the 0–1 string in the modified grid algorithm, the one-dimensional vector pattern can fully express the space geometry information of the stars observed in FOV, which makes a great contribution to star identification.
(2): The feature vector of the same observed star remains unchanged when the stellar image rotates, so the comparison of every two star pattern is simplified as the comparison of the two feature vectors, which can accelerate the speed of star identification.
(3): The utility of the number of the non-zero value in the feature vector can narrow down the search scope of the matching pattern, which can make it possible to achieve the matching result quickly in the feature database, instead of searching the entire feature database.
(4): Under the same conditions, the performance of the proposed algorithm is better than the other three star identification algorithms.
(5): Compared with the other three star identification algorithms, the proposed algorithm is simple and easy to replicate.

We have clearly validated the robustness and the effectiveness of the proposed algorithm by analyzing the experimental results and comparing the proposed algorithm with the other three star identification algorithms. Experiment results show that the proposed algorithm outperforms the pyramid algorithm, the modified grid algorithm, and the LPT algorithm in terms of identification time, recognition accuracy, and robustness. Moreover, the computational complexity of the proposed algorithm is lower than that of the other three algorithms. The proposed algorithm can promote the efficiency of the attitude determination for the spacecraft, which will expand the application of star sensors.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant No. 61172138, 61401340), the Natural Science Basic Research Plan in Shaanxi Province of China (Grant No. 2013JQ8040), the Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20130203120004), the Open Research Fund of The Academy of Satellite Application (Grant No. 2014_CXJJ-DH_12), the Xi’an Science and technology plan (Grant No. CXY1350 (4)), the Fundamental Research Funds for the Central Universities (Grant Nos. 201413B, 201412B, JB141303), and the Open Fund of Key Laboratory of Precision Navigation and Timing Technology, National Time Service Center, CAS (Grant No. 2014PNTT01, 2014PNTT07, 2014PNTT08). The authors would like to thank the anonymous reviewers for their critical and constructive comments to the manuscript.

Author Contributions

L.X., L.L. and H.Z. conceived and designed the research; L.L. performed the research; L.L. wrote the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

Liebe, C.C. Accuracy performance of star trackers—A tutorial. IEEE Trans. Aerosp. Electron. Syst. 2002, 38, 587–599. [Google Scholar] [CrossRef]
Liebe, C.C. Star trackers for attitude determination. IEEE Aerosp. Electron. Syst. Mag. 1995, 10, 10–16. [Google Scholar] [CrossRef]
Tsai, J.; Hsiao, F.Y.; Li, Y.J.; Shen, J.-F. A quantum search algorithm for future spacecraft attitude determination. Acta Astronaut. 2011, 68, 1208–1218. [Google Scholar] [CrossRef]
Spratling, B.B., IV; Mortari, D. A survey on star identification algorithms. Algorithms 2009, 2, 93–107. [Google Scholar] [CrossRef]
Accardo, D.; Rufino, G. Brightness-independent start-up routine for star trackers. IEEE Trans. Aerosp. Electron. Syst. 2002, 38, 813–823. [Google Scholar] [CrossRef]
Samaan, M.A.; Mortari, D.; Junkins, J.L. Recursive mode star identification algorithms. IEEE Trans. Aerosp. Electron. Syst. 2005, 41, 1246–1254. [Google Scholar] [CrossRef]
Mortari, D.; Junkins, J.L.; Samaan, M.A. Lost-in-space pyramid algorithm for robust star pattern recognition. In Advances in the Astronautical Sciences, Proceedings of the Annual AAS Rocky Mountain Guidance and Control Conference, Breckenridge, CO, USA, 31 January–4 February 2001; Volume 107.
Mortari, D.; Samaan, M.A.; Bruccoleri, C.; Junkins, J.L. The pyramid star identification technique. Navig. J. Inst. Navig. 2004, 51, 171–183. [Google Scholar] [CrossRef]
Wu, F.; Shen, W.M.; Zhou, J.K.; Chen, X.H. Design and simulation of a novel aps star tracker. In Proceedings of the 2008 International Conference on Optical Instruments and Technology: Optical Systems and Optoelectronic Instruments, Beijing, China, 16–19 November 2008; Volume 7156, p. 11.
Scholl, M.S. Experimental demonstration of a star-field identification algorithm. Opt. Lett. 1993, 18, 402–404. [Google Scholar] [CrossRef] [PubMed]
Scholl, M.S. Six-feature star-pattern identification algorithm. Appl. Opt. 1994, 33, 4459–4464. [Google Scholar] [CrossRef] [PubMed]
Jiang, M.; Ye, Y.Z.; Yu, M.Y.; Wang, J.X.; Li, B.H. A Novel Star Pattern Recognition Algorithm for Star Sensor; IEEE: New York, NY, USA, 2007; pp. 2673–2677. [Google Scholar]
Du, L.; Zhao, Y. An improved triangle star pattern recognition algorithm with high identification probability. In Proceedings of the International Symposium on Photoelectronic Detection and Imaging 2011: Advances in Infrared Imaging and Applications, Beijing, China, 24 May 2011; p. 819305.
Zhang, W.; Qi, S.X.; Zhang, R.; Yang, L.L.; Sun, J.F.; Song, L.Q.; Tian, J.W. A local-sky star recognition algorithm based on rapid triangle pattern index for iccd images. In Proceedings of the International Symposium on Photoelectronic Detection and Imaging 2013: Infrared Imaging and Applications, Beijing, China, 25–27 June 2013; Volume 8907, p. 10.
Zong, H.; Gao, X.Y.; Wang, B. Modification and implementation of a triangle star pattern recognition algorithm. In Proceedings of the 2013 32nd Chinese Control Conference (CCC), Xi’an, China, 26–28 July 2013; pp. 5182–5186.
Pei, R.; Hou, Y.S.; Hao, Y.; Xie, Y.E. A star identification algorithm based on group-matching. In Proceedings of the 2013 International Conference on Mechatronic Sciences, Electric Engineering and Computer (MEC), Shenyang, China, 20–22 December 2013; pp. 1502–1505.
Padgett, C.; Kreutz-Delgado, K. A grid algorithm for autonomous star identification. IEEE Trans. Aerosp. Electron. Syst. 1997, 33, 202–213. [Google Scholar] [CrossRef]
Lee, H.; Oh, C.S.; Bang, H. Modified grid algorithm for star pattern identification by using star trackers. In Proceedings of the RAST 2003: Recent Advances in Space Technologies, Istanbul, Turkey, 20–22 November 2003; Ince, F., Onbasioglu, S., Eds.; IEEE: New York, NY, USA; pp. 385–391.
Lee, H.; Bang, H. Star pattern identification technique by modified grid algorithm. IEEE Trans. Aerosp. Electron. Syst. 2007, 43, 1112–1116. [Google Scholar]
Na, M.; Zheng, D.N.; Jia, P.F. Modified grid algorithm for noisy all-sky autonomous star identification. IEEE Trans. Aerosp. Electron. Syst. 2009, 45, 516–522. [Google Scholar] [CrossRef]
Yi, W.J.; Liu, H.B.; Yang, J.K.; Jia, H.; Yang, L.X. Three-dimensional grid algorithm for all-sky autonomous star identification. In Proceedings of the 6th International Symposium on Advanced Optical Manufacturing and Testing Technologies: Optical System Technologies for Manufacturing and Testing, Xiamen, China, 26 April 2012; p. 84207.
Hong, J.; Dickerson, J.A. Neural-network-based autonomous star identification algorithm. J. Guid. Control Dyn. 2000, 23, 728–735. [Google Scholar] [CrossRef]
Kim, K.T.; Bang, H. Reliable star pattern identification technique by using neural networks. J. Astronaut. Sci. 2004, 52, 239–249. [Google Scholar]
Yang, J.; Wang, L. An improved star identification method based on neural network. In Proceedings of the IEEE 10th International Conference on Industrial Informatics, Beijing, China, 25–27 July 2012; pp. 118–123.
McClintock, S.; Lunney, T.; Hashim, A. A genetic algorithm environment for star pattern recognition. J. Intell. Fuzzy Syst. 1998, 6, 3–16. [Google Scholar]
Seisie-Amoasi, E.; Williams, B.G.; Schoen, M.P.; Asme. Optimization of a star pattern recognition algorithm for attitude determination using a multi-objective genetic algorithm. In Proceedings of the ASME 2005 International Mechanical Engineering Congress and Exposition, Orlando, FL, USA, 5–11 November 2005; pp. 913–920.
Padgett, C.; KreutzDelgado, K.; Udomkesmalee, S. Evaluation of star identification techniques. J. Guid. Control Dyn. 1997, 20, 259–267. [Google Scholar] [CrossRef]
Wei, X.G.; Zhang, G.J.; Jiang, J. Star identification algorithm based on log-polar transform. J. Aerosp. Comput. Inf. Commun. 2009, 6, 483–490. [Google Scholar] [CrossRef]
Juang, J.N.; Wang, Y.C. Further studies on singular value method for star pattern recognition and attitude determination. J. Astronaut. Sci. 2012, 59, 379–389. [Google Scholar] [CrossRef]
Yoon, H.; Paek, S.W.; Lim, Y.; Lee, B.H.; Lee, H. New star pattern identification with vector pattern matching for attitude determination. IEEE Trans. Aerosp. Electron. Syst. 2013, 49, 1108–1118. [Google Scholar] [CrossRef]
Yoon, Y. Autonomous star identification using pattern code. IEEE Trans. Aerosp. Electron. Syst. 2013, 49, 2065–2072. [Google Scholar] [CrossRef]
Zhao, L.; Hou, Y.; Hao, Y.; Wu, X. A novel star identification algorithm using pattern vector. In Proceedings of the 2014 33rd Chinese Control Conference (CCC), Nanjing, China, 28–30 July 2014; pp. 703–706.
Hang, Y.; Xin, S.; Ye, Y. Study on boundaries of eigenvalues in svd method for autonomous star identification. In Proceedings of the 2014 6th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, China, 26–27 August 2014; pp. 304–308.
Ji, F.L.; Jiang, J.; Wei, X.G. Unified redundant patterns for star identification. In Proceedings of IEEE International Conference on Imaging Systems and Techniques (IST), Beijing, China, 22–23 October 2013; pp. 228–233.
Quan, W.; Xu, L.; Fang, J. A new star identification algorithm based on improved hausdorff distance for star sensors. IEEE Trans. Aerosp. Electron. Syst. 2013, 49, 2101–2109. [Google Scholar]
Pham, M.D.; Low, K.-S.; Shoushun, C. An autonomous star recognition algorithm with optimized database. IEEE Trans. Aerosp. Electron. Syst. 2013, 49, 1467–1475. [Google Scholar] [CrossRef]
Luo, L.Y.; Xu, L.P.; Zhang, H.; Sun, J.R. Improved autonomous star identification algorithm. Chin. Phys. B 2015, 24, 064202. [Google Scholar] [CrossRef]
Zhang, P.; Zhao, Q.; Liu, J.; Liu, N. A brightness-referenced star identification algorithm for aps star trackers. Sensors 2014, 14, 18498–18514. [Google Scholar] [CrossRef] [PubMed]
Reibel, Y.; Jung, M.; Bouhifd, M.; Cunin, B.; Draman, C. CCD or CMOS camera noise characterisation. Eur. Phys. J. Appl. Phys. 2003, 21, 75–80. [Google Scholar] [CrossRef]

© 2015 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Luo, L.; Xu, L.; Zhang, H. An Autonomous Star Identification Algorithm Based on One-Dimensional Vector Pattern for Star Sensors. Sensors 2015, 15, 16412-16429. https://doi.org/10.3390/s150716412

AMA Style

Luo L, Xu L, Zhang H. An Autonomous Star Identification Algorithm Based on One-Dimensional Vector Pattern for Star Sensors. Sensors. 2015; 15(7):16412-16429. https://doi.org/10.3390/s150716412

Chicago/Turabian Style

Luo, Liyan, Luping Xu, and Hua Zhang. 2015. "An Autonomous Star Identification Algorithm Based on One-Dimensional Vector Pattern for Star Sensors" Sensors 15, no. 7: 16412-16429. https://doi.org/10.3390/s150716412

APA Style

Luo, L., Xu, L., & Zhang, H. (2015). An Autonomous Star Identification Algorithm Based on One-Dimensional Vector Pattern for Star Sensors. Sensors, 15(7), 16412-16429. https://doi.org/10.3390/s150716412

Article Menu