A Survey on Star Identification Algorithms

Algorithms 2009, 2, 93-107; doi:10.3390/a2010093 OPEN ACCESS algorithms ISSN 1999-4893 www.mdpi.com/journal/algorithms Review A Survey on Star Identification Algorithms Benjamin B. Spratling, IV and Daniele Mortari ? Aerospace Engineering, Texas A&M University, College Station, 77843-3141 TX, USA E-mails: benspratling@tamu.edu; mortari@tamu.edu ? Author to whom correspondence should be addressed. Received: 30 October 2008; in revised form: 13 January 2009 / Accepted: 16 January 2009 / Published: 29 January 2009 Abstract: The author surveys algorithms used in star identification, commonly used in star trackers to determine the attitude of a spacecraft. Star trackers are a staple of attitude deter- mination systems for most types of satellites. The paper covers: (a) lost-in-space algorithms (when no a priori attitude information is available), (b) recursive algorithms (when some a priori attitude information is available), and (c) non-dimensional algorithms (when the star tracker calibration is not well-known). The performance of selected algorithms and support- ing algorithms are compared. Keywords: Star Identification; Attitude Estimation; Star Tracker Algorithms. 1. Introduction The requirement for attitude (orientation) information of a spacecraft has been the mother of invention of many devices and algorithms, notably the process of autonomously identifying stars (Star-ID). Though there is much history of devices used to identify stars and compute an attitude that do not use a star camera, this paper primarily analyzes algorithms that use a star camera with an imaging array and an algorithm to match observed (body) directions of stars with catalog (inertial) directions of stars without requiring reorienting the camera or the spacecraft. These algorithms fall into two basic categories, lost- in-space algorithms, in which no information regarding the attitude of the spacecraft is available, and recursive algorithms, in which some information regarding the attitude is available. These techniques typically use inter-star angles (the angle between the line-of-sight of two stars from the perspective of a camera), the brightness of the stars, and some computations of these values to distinguish stars. A further Algorithms 2009, 2 94 subcategory of both categories is non-dimensional Star-ID, in which the exact angular separations are not required but the values are normalized to be insensitive to poor camera calibration, or time-varying camera calibration parameters [1–3]. Figure 1. Typical Star-Tracker Image-based Attitude Determination Flow. Star-ID is just one step in the process of determining the attitude of a spacecraft, as depicted in Figure 1. The first algorithms in the sequence measure body-frame vectors for the locations to observed stars. The Star-ID process has as its primary purpose determining the inertial-frame vectors for some or all of the body-frame vectors given to it. Subsequent algorithms determine a suitable transformation that correctly maps the body vectors to the inertial vectors, thereby calculating the spacecraft’s attitude. When sensing the stars with a CCD imaging array, the information available for the identification process is the brightness of the star and the angular separation between stars. Figure 2. Typical Star-ID Process. Star-ID task has three basic pieces, with an optional fourth, as illustrated in Figure 2. First, an al- gorithm must extract features from a set of body vectors and associated brightness. Second, a database search matches a subset of the observations with entries in the database, and third makes some estimate as to the probability that they are correct. Optionally, the remaining body vectors are identified once an estimate of the attitude is available in a method called “recursive” Star-ID. This fourth step typically implements a variation of the “direct match” technique in which stars are identified by their close prox- imity to their predicted location. The recursive mode is typically much faster than the first two, and can usually be repeated successively for additional observations with an a priori estimate of the attitude. 1.1. Topics Covered, Notation, and Figures The algorithms surveyed in this paper are evaluated by the analytical asymptotic performance of 1. the feature extraction step, Algorithms 2009, 2 95 2. database search, and 3. their utilization of independent pattern features in the star features based on how many stars are used in a pattern. For all cases, the number of stars referenced in the star catalog is n, the average number of stars observed in the field of view of the camera is f , and the number of stars in a pattern is b. Although a star pattern containing b stars has b(b− 1) 2 inter-star angles which may be measured, the number of independent pattern features for a star pattern of b stars, is only (2b−3), since some inter-star angles are dependent on the values of others. By including star magnitude information, which is typically much less precise than inter-star angle information, an additional b independent pattern features may be used. Throughout this paper, the use of asymptotic notation, O(. . .), is used to indicate the highest order term in the running time of an algorithm. Algorithms are analyzed based on the described implementation in the referenced papers. Any assumptions drawn about their performance time, when not directly stated in the paper, is based on the progression and availability of certain algorithms at the time, although alternative running times are discussed if it seems likely they could have been implemented. Furthermore, the common computer science notation, “lg n” is used to mean “log2 n”. To preserve the original authors’ intent, the figures shown here are duplicated from the referenced papers. 2. The Beginning After the first CCD-based star tracker was developed by Salomon in 1976 at JPL [4], Junkins, Turner, Strikwerda [5, 6], and others began work on implementing an algorithm that could identify stars in real-time. While they realized the benefit of using the easily-computable sine of inter-star angles as a pattern feature, the key problem that arose was the matching of observed inter-stars to the items in the database. After several years of work and a few conference papers, Junkins et al. published “Star Pattern Recognition and Spacecraft Attitude Determination” in 1981 [7]. Although the algorithm was able to identify star triplets, it had the primary limitation of requiring an a priori estimate of the spacecraft’s attitude before it was able to perform in real-time. The reason is that Junkins had used “sub catalogs” of the sky, illustrated in Figure 3, each representing a portion of the sky, in order to accelerate the computation. Although the method was robust to non-stars because the catalog included all combinations of stars that might be observed, it only updated the attitude estimation algorithm once or twice a minute, as contrasted with the angular rate sensors, which updated at 1, 000 times per minute. The majority of the attitude estimation was propagation of the angular rate sensors, and periodic checks were established to confirm and improve the propagated attitude. Junkins’ feature extraction runs very fast, in O(b) time, since it may select any three of the observed stars and measure the sine of their inter-star angles. However, since his database search considers every possible permutation of stars available in a given region of sky, the search time is O(f 3), where f is the number of stars in a given sub-catalog, usually the same size of a given field of view. The time to perform Star-ID increases if the stars are not located in the predicted field of view as other sub-catalogs are searched. The database itself would grow as O(nf 2). In 1986, Groth [8] suggested that a faster way to search the sub-catalogs would be to sort the triangles sides in order based on permutation-invariant values such as the logarithm of the perimeter of a triangle. Algorithms 2009, 2 96 Figure 3. Field-of-view-sized sub-catalogs (reprinted from [7]). He admits, however, that his algorithm runs at high polynomial power of n, much as Junkins’ has. Groth’s algorithm differs in that the performance has a lower constant factor. While the asymptotic order of the database is identical to Junkins, there would be more data included, associated with the permutation-invariant values. In 1987, Sasaki [9] and others published a patent showing how to improve the search time by using the area of a star triangle and the sum of the luminous intensities as preliminary markers in performing the star identification, using O(b)-time for star feature extraction. His method does not discuss the way in which the database is searched, requiring only that a “number of stars” will be selected from the database by a method using “parallel, serial, or the like” processors. It is not noted whether his database indeed contains as many star triplets as does Junkins’ method, nor is the search procedure described. Later, in 1989, Van Bezooijen [2] suggested in his dissertation that the speed of the star pattern recog- nition algorithm could be improved by making more use of the available information in the star patterns. Van Bezooijen discussed directly the relationship between the number of stars and the amount of in- formation available from a star pattern with a given number of stars. His analysis also included a very detailed statistical probability that a star had been identified correctly. Unfortunately, Van Bezooijen’s method sometimes required the spacecraft to slew in order to detect stars for his Star-ID method, and as such, his work is not covered in depth here. In 1991, with Junkins on his advisory committee, David Anderson [10] addressed the ambiguity of the order of star triplets by proposing a permutation matrix, and the development of star pattern parameters that were independent of the order in which the stars are selected. Sticking with the tried-and-true star- triple pattern, Anderson also proposed the use of an array processor to handle the matrix multiplications required to use his permutation matrices. Unfortunately, the database storage remained O(nf 2), and there was no advance made on the database search. Anderson suggested that an array processor be used to perform the matrix multiplication, decreasing the running time of the Star-ID process. The design engineer should note that array processors, while performing a comparatively large number of computations when contrasted with a serial processor, also use a comparatively large amount of power, Algorithms 2009, 2 97 because they both tend to use identical amounts of energy to perform each computation. 3. Search Process Acceleration The next year, Liebe [11] made the critical connection of the feature selection process to the database search time, making the Lost-In-Space problem tractable. Liebe suggested the use of the two closest stars to a selected star as components of the star pattern, and the angular separations from the two closest stars and the angle between them as his parameters, as illustrated in Figure 4, and addressed the situations in which predicted stars would not be seen due to their magnitude being very close to the detection threshold. Liebe also address the situation in which small errors would cause the incorrect selection of the closest two stars when the distance to these stars were similar. Although Leibe’s feature extraction process now took O(f lg b)-time to compute, his database could be reduced to O(n), and subsequently, his database search could be performed much faster, though still linear-time. Liebe makes full use of the available angular independent pattern features, neglecting the stellar magnitudes. Liebe later implements the optional recursive direct match mode which could identify the remaining stars up to 20 times faster than the Lost-In-Space algorithm. Figure 4. Liebe’s parameters, 2 inter-star angles and 1 interior angle (reprinted from [11]). Then in 1993, Baldini [12] proposed a multi-step Star-ID method. Baldini’s method identifies the brightest b stars in a given image, requiring O(f lg b) time. He then measures the angular separation of the sequence of five stars, O(b) time. Baldini then proceeds through a linear search of the catalog search for every star in the catalog which falls within an acceptable tolerance range of the observed stars, requiring O(bn)-time, neglecting the time for dynamic list creation, although this step would be improved by other algorithms in the future. If we use the expression ∆m to represent the fraction of stars in the catalog that fall within the acceptable range, he has an intermediate result of O(∆mn) stars in each of b lists. He then compares the distance of each star in adjacent lists determining if any star cannot have an angular separation within the tolerance of the observed angular separation, requiring O (b(∆mn)2)-time, although as he points out, as items are eliminated the number of comparison at each iteration is reduced. Baldini is then left with b lists containing stars that meet their neighboring distance criteria, he then forms all combinations of the stars, discarding combinations whose sequence of angular separations does not match the observed stars. The running time of this step is represented analytically by O ( ab ) , assuming there are approximately a stars in each of b lists. It is certain that the rejection of certain combinations in the second or third step is sure to reduce the total number of comparisons, and Algorithms 2009, 2 98 Baldini is certain to conclude with only one or two possible combinations of stars. Baldini has used five stars, inherently containing twelve independent features, but uses only nine when performing his identification process, suggesting the required field of view may be larger for Baldini’s method when compared to other methods to be sure that there will be enough visible stars. Although non-stars will get weeded out in the process, the addition of non-stars to the algorithms increases most of the steps linearly or quadratically. In 1995 Ketchum [13] proposed a second sequential filtering algorithm, this time using the brightness of the brightest star to attempt to determine the likelihood of pointing in any particular direction. She then filters the list of possible stars using the brightness of the second brightest star. Although she admits the algorithm would need to search as much as 43% of the catalog for the appropriate stars, she notes that the storage space required by his algorithm is much less than required by Van Bezooijen’s method. Furthermore, Ketchum is one of few to give direct empirical data regarding the running-time of his algorithm, reporting it requires up to 63 seconds to run on a 50 MHz processor. Later in 1995, Scholl [14] published a more straightforward method. The inter-star angles were to be ordered by their relative brightness, eliminating the permutations that arise when considering the possible orders of three stars. Unfortunately, Scholl retains the O(n f 2)-sized catalogs, and does not specify the search technique used. While it’s true that his method uses less time to search the database when compared to Baldini, it is nonetheless still O(n f 2), since faster techniques were not proposed until the following year. 3.1. Search Time Dramatically Reduced In 1996, Quine [15] was the first to attack the database search problem head on, realizing that a binary search tree (see Figure 5) could be used to search the database in O(lg n)-time. He retains Liebe’s use of the two closest stars to a given star to form a pattern, resulting in a database of size O(n), instead of previous catalogs that used all observable combinations of stars. While this increases his feature extraction time to O(f lg b), the trade off is quite advantageous for large values of n. Figure 5. Quine’s Binary Tree (reprinted from [15]). Algorithms 2009, 2 99 3.2. Novel Grid Algorithm In 1997, Padgett [16] published perhaps the first novel star pattern recognition algorithm, which actually used a star “pattern.” Padgett’s grid algorithm cast the locations of neighboring stars as items on a loose grid (see Figure 6). Padgett solved the roll ambiguity by rotating the observed stars about a given star until the nearest star to the given star was aligned with the x axis. The cells in the grid were then considered to be “on” if there was a star located inside it, and “off” if there were not. The locations of the “on cells” then become the features, the indexes of the “on cells” were listed as items in a vector. His feature extraction time became O(f). Unfortunately, Padgett was unable to improve the database search time for his features beyond linear, and the resulting database search remained O(n). Further analysis indicated that Padgett’s method was quite robust to the presence of non-stars owing to its large grid cell size when compared to the angular error in star position. Figure 6. Illustration of Padgett’s Grid Algorithm (reprinted from [16]). 3.3. Search Time Reduced Much Further Later in 1997, Mortari [17, 18] proposed an even faster database search technique, the “Search-Less Algorithm,” (SLA). Mortari retained the approach of selecting any pair of stars in the field of view, O(b)- time, but he proposed using a “k-vector” to search the database in an amount of time independent of the size of the database [19]. Figure 7 shows the k-vector construction for a 10-element database. The small horizontal lines are equally spaced and they give the k-vector values: 0, 2, 2, 3, 3, 5, 6, 8, 9, 10. The search time for a single star-pair would be O(k), where k is the number of possible star pairs with Algorithms 2009, 2 100 Figure 7. Example of k-vector construction (reprinted from [19]). 0 2 2 3 3 5 6 8 9 10 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 K−vector Elements So rte d Da ta ba se s =y (I) y a yb 1 2 3 4 5 6 7 8 9 10 inter-star angles within the measurement tolerance. Unfortunately, the dominant time of the algorithm came when comparing multiple lists of stars returned for each inter-star angle. Since multiple stars had to have all their inter-star angles confirmed to be a match, the running time of the comparison would be O(bk2), and b is the number of stars in the pattern required to guarantee uniqueness. Even though the resulting value of k would be a number based on the uncertainty associated with the inter-star angle measurement and the number of observable star pairs, Mortari had made the first important step in breaking the dependence of the database search time on the size of the database. Mortari’s method could also reject a single non-star from a set of selected stars, without loosing the progress made in identifying the others. The resulting Search-Less Algorithm (SLA) was then successfully tested on orbit on an Indian satellite [20]. A few years later, realizing that the robustness to non-star “spikes” was essential towards reducing the number of iterations of his algorithm, Mortari developed the “Pyramid” algorithm [21] which uses an optimal permutation algorithm to exploit the ability of his algorithm to select which stars to match. This permutation is written to minimize the time spent considering stars that don’t match, fearing them to be non-star spikes. The code has been tested to reject non-stars in an image containing only five real star but with 63 non-stars thrown in. The Pyramid algorithm has been successfully tested on Draper’s “Inertial Stellar Compass” star tracker [22] and on MIT’s satellites HETE and HETE-2 [23]. This algorithm is presently under exclusive contract to StarVision Technologies. Neural networks, have been proposed for use in Star ID as early as 1989, [24]. In 2000, Hong [25], proposed using a neural network and fuz