• One of the most computationally-complex steps in star-image-based autonomous spacecraft attitude-determination is star identification, in which the corresponding catalog-stars must be found for the directions to observed stars. Previous star identification methods have relied on 1) one-dimensional database searches, 2) tree-based multidimensional database searches, or 3) massively parallel processing hardware. The use of a multi-dimensional database search running in O(d + k)- time (where d is the number of dimensions and k is the number of correct answers), such as the K-Vector ND, promises to revolutionize the time required for star identification, if a set of star pattern parameters which are nearly uniformlydistributed, required by the K-Vector ND, are found. New star-pattern parameters, meeting the above specification are presented and found to be directly extensible to star patterns containing any number of stars greater than 2. The algorithm uses a star pattern composed of a selected star and its closest stars. The choice of this pattern causes a number of computational and reliability issues, and for that reason it is frequently considered to be the "wrong answer." Methods of adding additional carefully-crafted "wrong" answers to the database to compensate for many of the issues are presented. Some issues require modification to the run-time algorithm, and the final run-time algorithm is presented. The finished Star-ND technique is evaluated both for execution-time performance in the presence of non-stars, and the growth of the database size for the false entries. Performance of the core algorithm is found to be as low as 1, 700 clock cycles. The required field-of-view size required for the algorithm to have enough stars to succeed in star identification is estimated and found to correspond with a simple mathematical expression.

published proceedings


author list (cited authors)

  • Spratling, B., & Mortari, D.

complete list of authors

  • Spratling, Ben||Mortari, Daniele

publication date

  • December 2010