Date of Graduation


Document Type


Degree Type



Statler College of Engineering and Mineral Resources


Mechanical and Aerospace Engineering

Committee Chair

John A Christian

Committee Co-Chair

Thomas Evans

Committee Member

Jason Gross

Committee Member

Alfred Lynam


With the present interest in deep space missions by NASA and other space agencies, various techniques are continuously being developed and tested for accurate spacecraft attitude determination. One particularly important problem is the situation where the spacecraft has no a priori attitude information --- the so called "lost-in-space'' problem. This thesis presents a novel method for recognizing star patterns in an image with no a priori attitude information, with applications to spacecraft star trackers and other similar attitude sensors. Specifically, a geometric hashing approach is proposed that describes star patterns by the four interior star angles that form the perimeter of a star quad. A technique is presented for labeling these four interior star angles to make the hash code both unique as well as invariant to sensor attitude or star observation order. Using this approach, an index of star quad hash codes is created from a star catalog and the result is stored in a k-d tree. When an image of a star field is obtained, observed star quads are created and the index is searched for the best match using a nearest neighbor algorithm. A verification process is used to improve robustness. This thesis gives an extensive overview of the process that was created to recognize and disregard possible false positives in the star identification algorithm, while still producing accurate results and correctly identifying stars at a high success rate. Performance of the new star identification approach is demonstrated through a Monte Carlo analysis that considered 100,000 random attitudes. It is found that the proposed approach successfully identifies star patterns in 99.79% of the cases and decides that no match can be reliably made in 0.21% of the cases. Incorrect star match were observed in only 0.001% of the test cases. The effect of these very infrequent misidentifications on the resulting attitude estimate were found to be benign.