J. Software Engineering & Applications, 2010, 3: 34-38
doi:10.4236/jsea.2010.31004 Published Online January 2010 (http://www.SciRP.org/journal/jsea)
A Polar Coordinate System Based Grid Algorithm
for Star Identification
Hua ZHANG1, Hongshi SANG1*, Xubang SHEN2
National Key Laboratory of Science and Technology on Multispectral Information Processing technologies, Huazhong University of
Science and Technology, Wuhan, China; 2Xi’an Microelectronics Technology Institute, Xi’an, China.
Received September 3rd, 2009; revised September 28th, 2009; accepted October 6th, 2009.
ABSTRACT
In Cartesian coordinate systems, the angular separation-based star identification algorithms involve much trigon-
ometric function computing. That delays the algorithm process. As in a polar coordinate system, the coordinates are
denoted by angular values, it is potential to speed up the star identification process by adopting a polar coordinate sys-
tem. An angular polar coordinate system is introduced and a grid algorithm based on the coordinate system is proposed
to enhance the performances of the star identification process. The simulations demonstrate that the algorithm in the
angular polar coordinate system is superior to the grid algorithm in the rectangle Cartesian coordinate system in com-
puting cost and identification rate. It can be used in the star sensors for high precision and high reliability in spacecraft
navigation.
Keywords: Star Identification, Grid Algorithm, Polar Coordinate System, Star Sensor
1. Introduction
As the star sensors are used widely in autonomous
spacecraft navigation, the star identification algorithm
must be of time efficiency and high identification rate.
Most star identification algorithms employ the angular
star pair distance or polygon to build the guide database.
These algorithms include polygon match algorithm, tri-
angle algorithm [1–4] and group match algorithm [5–7],
etc. Another class of star identification algorithms ac-
complishes star identification in terms of pattern recogni-
tion or best match. These algorithms associate each star
with a pattern or signature determined by its surrounding
star field. Then the star identification process can be
treated as finding the closest match between the observed
patterns and the catalog patterns. The most representative
algorithm in this class is grid algorithm [8]. Compared
with other algorithms, grid algorithm is an excellent al-
gorithm with a higher identification rate and smaller
memory requirement, as well as it is computationally
efficient [9]. However, this algorithm needs to find the
closest neighboring star of the reference star to generate a
star pattern. As many fixed stars are variable in visual
brightness and the measuring noises exist in measure-
ment, the identification probability for the closest
neighboring star is comparatively low. That leads to
identification failure resulting from misidentifications.
The literature [10] proposes a new grid algorithm adopt-
ing the radial and cyclic features of the stars in star iden-
tification. The algorithm demonstrates excellent per-
formance in identification rate.
Recently, almost all the star identification algorithms
are based on the Cartesian coordinate system. Imper-
fectly, the angular separations must be computed by us-
ing trigonometric functions. That delays the star identi-
fication process. As is known, the polar coordinate
system involves the angular information in the coor-
dinates. It is potential to improve the star identification
algorithm in the round polar coordinate system. In this
paper, an angular polar coordinate system is proposed for
the star sensor and a grid algorithm in the proposed polar
coordinate system is introduced. In the simulations, the
algorithm proposed is compared with the grid algorithm
in the Cartesian coordinate system introduced in the
literature [10]. As the simulations demonstrate, the
algorithm in the angular polar coordinate system is
superior to that in the Cartesian coordinate system.
The paper is separated into four major sections as fol-
lows: the angular polar coordinate system for the star
sensor is introduced in the second section, and the grid
algorithm for star identification in the angular polar co-
ordinate system is introduced in the third section. In the
last two sections, the simulations are presented and the
results are discussed.

A Polar Coordinate System Based Grid Algorithm for Star Identification35
2. Angular Polar Coordinate System for Star
Sensor
The polar coordinate system is well known and used
widely. The proposed coordinate system is derived from
the conventional polar coordinate system to be used in
focal length related image processing field, in that the
radial coordinate is denoted by an angular value, so
named angular polar coordinate system. As shown in
Figure 1, the radial coordinate is denoted by φ, which is
the view angle from the focus of the lens physically. And
the angular coordinate is denoted by θ, just the same as
the angular coordinate in the conventional polar coordi-
nate system [11]. The coordinate angles in the polar no-
tation are expressed in either degrees or radians (2π rad
being equal to 360°), and the angular coordinate θ is
measured counterclockwise from the axis and limited to
be non-negative values. The axis for 0

 is chosen to
be the same as the direction of the X axis of the image
sensor in the Cartesian coordinate system. Then the two
polar coordinates φ and θ can be converted to the
Cartesian coordinates x and y by using the trigonometric
functions,
tan cos
tansin








xf
yf (1)
where f is the focal length of the sensor lens.
In the Cartesian coordinate system, if the coordinates
of the two stars in the planar frame of the star sensor are
( ,) and (,), the two unit vectors below can de-
note the stars in the body coordinate of the star sensor,
i
xi yj
xj y
2222 22
11










 








j
i
iij
iij j
j
x
x
vyv
xy fxyf
f
y
f
，
(2)
where f denotes the focal length of the optical lens in the
star sensor. Then the angle between the two vectors can
be computed,
arccos( )


iji j
evv
(3)
In star identification process, the two stars are called a
star pair, and the angle between the two stars is called the
angular separation or angular distance between the star
pair. The principle of angular separation matching is that
the angular separations between the star pairs in the star
image are computed and compared with those stored in
the guiding catalog. If the differences is within an error
bound on the expected errors, the angular separation pat-
tern is considered matched and the stars made up of the
star pair can be determined.
While in the angular polar coordinate system, if one
star is located at the polar point, the radial coordinate of
another star is just the angular separation between the
two stars. And the angular coordinate can represent the
distribution of the star relatively, as shown in Figure 2.
Therefore, it is potential to use the angular polar coordi-
nate system for star identification to avoid computing the
angular separations.
In the polar coordinate system, the polar grids are used.
As shown in Figure 2, the planar image frame is divided
into mean radial and cyclic angular grids. In both coor-
dinate directions, the frame can be divided by mean an-
gular distance. The distribution of the stars in the frame
can be denoted by the angular grids. We use the concepts
of the radial and cyclic feature in the literature [10] and
realize a grid algorithm for star identification in the an-
gular polar coordinate system to improve the perform-
ance of the algorithm.
3. Star Identification Algorithm in the Polar
Coordinate System
The concept of the algorithm we propose is to implement
fast coarse star identification by using the distribution of
the observed stars in the FOV (field of view) of the star-
φ
φ
φ
Figure 1. Angular polar coordinate system for star sensor

A Polar Coordinate System Based Grid Algorithm for Star Identification 36
φ
i
φ
N
Figure 2. The round grid in the polar system
sensor, without the need for computing the angular sepa-
rations. The algorithm involves three steps: first, an an-
gular polar coordinate system is built to denote the loca-
tions of the stars, and second, the star patterns are gener-
ated in the angular polar coordinate system. Then the
coarse star pattern matching is performed and the accu-
rate star identification is realized by checking the angular
separations between the stars.
3.1 Angular Polar Coordinate Frame Building
As the locations of the stars captured in the FOV are ex-
tracted, the brightest star S near the center of the FOV is
chosen as a reference star. The other stars around the
reference star S are called the neighbor stars of S. An
angular polar coordinate system is generated with the
polar point at the center of the reference star S and the
polar axis same as the direction of the X axis of the im-
age sensor in the Cartesian coordinate system. To avoid
computing the trigonometric functions in Equation 1, a
lookup Table (LT) is used to map the coordinates of the
stars in the planar image frame to the angular polar coor-
dinate system.
A round neighbor area of the reference star S is gener-
ated in the new coordinate system, as shown in Figure 2,
with the radius of the round area covering all the stars in
the FOV of the star sensor. Then the polar grids are parti-
tioned by mean radial angles and mean angular distance.
To reduce the redundancy of the computing cost, the
radial pattern and the angular pattern are generated sepa-
rately.
3.2 Star Pttern Gneration
3.2.1 Radial Feature Pattern
Evenly partition the round neighbor area of the star S
into N ring strips, where each ring strip represents an
angular distance of 0.01 degree. As for the sensor pattern,
the number of N is determined by the location of the star
S in the star image, equal to the largest number of ring
strip where there is at least one star within the ring strip.
Then the radial pattern of the star S, , is deter-
mined by
()
r
pat S
12
()( ,,...,)
rN
p
atSB BB

(5)
where
i-1 i
1,if there is at least a star between the radial grid and;
0, else.
i
B

  



(6)
The catalog radial patterns are generated just as the
process of generating the sensor radial pattern. To com-
patible with the unusual conditions that the reference star
is near the brim of the FOV, the number of N in generat-
ing the catalog radial patterns is so set that the radius of
the round area is twice the size of the FOV, i.e. N=100×θ
where θ is the angle of the FOV in degree. Therefore the
number of the bits in a catalog radial pattern is larger
than that in a sensor radial pattern. Accordingly, in the
radial pattern matching process, when the numbers of the
catalog radial pattern is longer than that of the sensor
radial pattern, the extra bits are neglected.
To reduce the memory requirements of the star catalog,
the radial patterns can be expressed by numbers of bytes

A Polar Coordinate System Based Grid Algorithm for Star Identification37
where every is denoted as a bit.
i
B
3.2.2 Angular Feature Pattern
Evenly partition the round neighbor area of S into 8 an-
gular sectors, with each sector representing an angular
distance of 45 degree in the angular direction, as shown
in Figure 2. A vector 12 8
( ,,...,)vAA A

is obtained from
the neighbor stars’ distribution in the angular sectors in
an anticlockwise direction, where
i-1 i
1,if there is at least one star between the angle grid and;
0, else.
i
A

  



(7)
When two or more stars lie in the same sector, the corre-
sponding bit of this sector is set to 1 just like the situation
that only one star lies in the sector. Shift to the left
circularly to find the maximum byte formed by
where each
v
v
i
A
is treated as a bit sequentially. As a re-
sult, the maximum byte is defined as the angular pattern
of the star S. For instances, when there is only one star
within the round area, the angular pattern of the star,
. Especially when there is no neighbor star
within the round neighbor, .
( )
a
patS128
() 0
a
patS 
The catalog angular patterns are generated just as the
process of generating the sensor angular patterns de-
scribed above. However, the radius of the round area
around the reference star is twice of the size of the FOV
of star sensor.
3.3 Star Pattern Matching
In the pattern matching process, a counter is used to rep-
resent the likeness between the observed sensor patterns
and the catalog patterns. For every catalog radial pattern,
if any i=1 both in the sensor pattern and in the catalog
pattern, the likeness counter plus one. The counter re-
mains invariable whenever i
B
B
=0 or the responding i
B
in the sensor pattern is not as same as that in the catalog
pattern. The star with the highest counter value is con-
sidered as the candidate star. In the same way, for every
angular pattern in the catalog, if any bit equals to one
both in the sensor angular pattern and in the catalog an-
gular pattern, the likeness counter plus one. As the angu-
lar distribution of the neighbor stars is invariant of rota-
tion, the sensor angular pattern is shifted circularly till a
maximal likeness counter value is gotten. And the star
with the highest counter value is considered as the
coarsely-matched star. Then the angular separations
among the stars are computed to make sure exactly
which star is in the FOV.
In short, the star identification algorithm proposed can
be described as below:
1) Choose a brightest star S near the center of the FOV
as the reference star and the polar point, then an angular
polar coordinate frame is built around the reference star
S.
2) A round area around the star S is generated and par-
titioned into N ring strips and 8 angular sectors.
3) The sensor radial pattern is generated and matched
with the patterns in the star catalog. If there is only one
candidate star, the coarse identification process is com-
plete. The candidate star is considered as the coarsely-
matched star, and the algorithm goes to step (5). On the
contrary, if there are more than one candidate star, the
following step are carried out.
4) For each candidate star, the angular pattern is gen-
erated and matched with the catalog angular patterns.
The star with the highest likeness counter value is con-
sidered as the coarsely-matched star.
5) If there is only one coarsely-matched star, the an-
gular separations between the neighbor stars and the ref-
erence star is computed and checked with the angular
separations in the catalog to distinguish each star. If there
is more than one coarsely-matched star, the angular
separations among the neighbor stars are computed to
eliminate the false coarse matches. Then the angular
separations between the neighbor stars and the reference
star is computed and checked to distinguish each star.
4. The Simulations and Discusses
The algorithm proposed has proven successful in night
sky tests. The star sensor used for the experiments is a
prototype star sensor, which uses STAR250, a 512×512
pixels APS (active-pixel sensor) image sensor manufac-
tured by Cypress (Fillfactory). To evaluate the algorithm
presented in the paper, Monte-Carlo simulations are per-
formed on the virtual photos taken on the full celestial
sphere with various noises inserted into the centroids of
the stars in the virtual star images. The star sensor con-
figuration used for the simulations makes use of an
18×18 degree FOV with an image resolution of 1024 ×
1024 pixels. The focal length of the lens is 50 mm, and
the sensitivity of star magnitude is 5.5 Mv. The locations
of the stars in the star images are converted to the refer-
ence star centered angular polar coordinate system and
the algorithm in the paper is compared with the grid al-
gorithm in the Cartesian coordinate system in literature
[10]. The algorithm is operated in an Intel PIII-800 PC,
and the statistical comparative results are shown in Table
1 below.

A Polar Coordinate System Based Grid Algorithm for Star Identification 38
Table 1. The results of the simulations
Performances of the algorithm Algorithm in [10] Algorithm in this paper
Rate of successful identification 99.36% 99.74%
Mean time spent by the algorithm 18.50 mS 11.40 mS
Memory for star catalog About 0.5 MB About 0.7 MB
As demonstrated in Table 1, the algorithm presented in
the paper is superior to the algorithm in the Cartesian
coordinate system in both the identification rate and the
time spent. The improvement in rate of success results
from the consideration that the reference star may be near
the brim of the FOV, as well as from the smaller radial
grids adopted. The failure cases are associated with the
noises inserted into the centroids of the stars.
Another improvement of the algorithm is to use the
pixel-distribution of the stars in an angular polar coordi-
nate system to coarsely identify the reference star. As the
coordinates of the stars are denoted by angles, the time-
consuming trigonometric functions and vector functions
are not needed to compute the inter-star angles. However,
as the smaller grids are adopted, the memory required for
the catalog patterns enlarges. For the radial pattern
represents the angular separations between the reference
star and the neighbor stars, the smaller grids are neces-
sary to guarantee the rate of success and the robustness.
As in the most patterns, there is no star in most of the
radial ring strips, so most of the radial patterns include
many zero bits. A data compressing method can be
adopted to reduce the memory requirement for the star
catalog. Nevertheless, that may somewhat delay the al-
gorithm.
5. Conclusions
To speed up the star identification algorithm, an angular
polar coordinate system is adopted in star sensor and a
grid algorithm in the polar coordinate system is intro-
duced. As in the angular polar coordinate system, the
coordinates are all angular representations, the algori-
thms in the coordinate system are potential to be compu-
tationally efficient and of high identification rate. As the
night sky tests and the simulations demonstrate, the algo-
rithm proposed is excellent in both computational effi-
ciency and identification rate. It can be used in the star
sensors for high precision and high reliability in space-
craft navigation.
6. Acknowledgements
The work was supported by the key program of National
Natural Science Foundation of China under grant
No.60736010.
REFERENCES
[1] C. C. Liebe, “tar trackers for attitude determination,” EEE
Aerospace and Electronics Systems Magazine, Vol. 10,
No. 6, pp. 10–16, June 1995.
[2] C. C. Liebe, “Accuracy performance of star tracker-a
tutorial,” IEEE Transactions on Aerospace and Electronic
Systems, Vol. 38, No. 2, pp. 587–589, April 2002.
[3] A. Domenico, R. Giancarlo, “Brightness-independent
start-up routine for star trackers,” IEEE Transactions on
Aerospace and Electronic Systems, Vol. 38, No. 3, pp.
813–823, July 2002.
[4] D. Mortari, M. A. Samaan, and C. Bruccoleri, et al, “The
pyramid star identification technique,” Journal of The In-
stitute of Navigation, Vol. 51, No. 3, pp. 171–184, 2004.
[5] S. C. Daniel, W. P. Curtis, “Small field-of-view star iden-
tification using bayesian decision theory,” IEEE Transac-
tions on Aerospace and Electronic Systems, Vol. 36, No.
3, pp. 773–783, July 2000.
[6] M. A. Samaan, D. Mortari, and J. L. Junkins, “Non-di-
mensional star identification for uncalibrated star cam-
eras,” AAS/AIAA Space Flight Mechanics Meeting,
Ponce, Puerto Rico, Paper No. AAS 03-131, February,
2003.
[7] M. A. Samaan, D. Mortari, and J. L. Junkins, “Recursive-
mode star identification algorithms,” IEEE Transactions
on Aerospace and Electronic Systems, Vol. 41, No. 4, pp.
1246–1254, October 2005.
[8] C. Padgett and K. Kreutz-Delgado, “A grid algorithm for
autonomous star identification,” IEEE Transactions on
Aerospace and Electronics Systems, Vol. 33, No.1, pp.
202–213, January 1997.
[9] C. Padgett, K. Kreutz-Delgado and S. Udomkesmalee,
“Evaluation of star identification techniques,” Journal of
Guidance, Control and Dynamics, Vol. 20, No. 2, pp.
259–267, 1997.
[10] G. Zhang, X. Wei and J. Jiang, “Full-sky autonomous star
identification based on radial and cyclic features of star
pattern,” Image and Vision Computing, Vol. 26, No. 7, pp.
891–897, July 2008.
[11] G. B. Richard, M. G. Andrew, et al, “Advanced mathe-
matics: precalculus with discrete mathematics and data
analysis,” Boston: Houghton Mifflin, 1994.