Based on the Hausdorff distance (HD), a star map recognition method was presented that did not depend on the rotation direction and focal length of the star sensor. When constructing the data point set of Hausdorff distance, the relative Euclidean distance corresponding to norm L2 was used as the set element to solve the influence of star sensor rolling angle on star pattern recognition. On the other hand, due to the influence of the focal length of star sensor, there were errors between the star sensor image and the standard reference image. When constructing standard data point elements, if a data point set contained another data point set, the L2 normal distance between at least two data points between the two data point sets was the same. Therefore, the relative distance was scaled, and the relative spatial distance in each set was divided by the smallest relative spatial distance in the set to form a new set of data points. This method was not necessary to calibrate the star sensor image due to different focal lengths influence. The calculation formula, implementation steps and the simulation results were presented. The experimental results show that the algorithm can obtain the star map recognition results correctly and get the attitude information of star sensor in the case of star sensor rotation, scale transformation, etc.