The speed of star map recognition determines the attitude update rate. To solve the time-consuming problem of cyclic displacement in the star map recognition algorithm based on log-polar transformation, we improve the algorithm. First, we search for the star point nearest to the center of the field of view, and construct a new rectangular coordinate system. The rectangular coordinates are then converted to polar coordinates. After projecting the star coordinates onto the distance axis, we construct a feature vector of star patterns. Because the polar coordinate transformation is rotationally invariant on the distance axis, the time-consuming problem causing by the cyclic displacement is avoided. In a simulation evaluation, the average recognition time of the proposed algorithm was reduced to 8.4% that of the traditional method, but this performance was slightly degraded by positional noise. The recognition rate of the proposed algorithm was higher than that of the traditional algorithm when the data were affected by pseudostars and missing stars. Under the influence of noise, star patterns are more changeable than triangle patterns, so the ecognition rate of the proposed algorithm is generally lower than that of the triangle-recognition algorithm.