Self-localization is an essential competence for mobile robot navigation. Due to the fundamental unreliability of dead reckoning, a robot must depend on its perception of external environmental features or landmarks to localize itself. A key question is how to evaluate landmark recognition systems for mobile robots. This paper answers this question by means of quantitative performance measures. An empirical study is presented in which a number of algorithms are compared in four environments. The results of this analysis are then applied to the development of a novel landmark recognition system for a Nomad~200 robot. Subsequent experiments demonstrate that the new system obtains a similar level of performance to the best alternative method, but at a much lower computational cost.