  This paper presents a rotation-search-based approach for addressing the star
identification (Star-ID) problem. The proposed algorithm, ROSIA, is a
heuristics-free algorithm that seeks the optimal rotation that maximally aligns
the input and catalog stars in their respective coordinates. ROSIA searches the
rotation space systematically with the Branch-and-Bound (BnB) method. Crucially
affecting the runtime feasibility of ROSIA is the upper bound function that
prioritizes the search space. In this paper, we make a theoretical contribution
by proposing a tight (provable) upper bound function that enables a 400x
speed-up compared to an existing formulation. Coupling the bounding function
with an efficient evaluation scheme that leverages stereographic projection and
the R-tree data structure, ROSIA achieves feasible operational speed on
embedded processors with state-of-the-art performances under different sources
of noise. The source code of ROSIA is available at
https://github.com/ckchng/ROSIA.
