Localization is one of the most important basic skills of a mobile robot. Most approaches, however, still rely either on special sensors or require artificial environments. In this article, a novel approach is presented that can provide compass information for localization, purely based on the visual appearance of a room. A robot using such a visual compass can quickly learn a cylindrical map of the environment, consisting of simple statistical features that can be computed very quickly. The visual compass algorithm is efficient, scalable and can therefore be used in real-time on almost any contemporary robotic platform. Extensive experiments on a Sony Aibo robot have validated that the approach works in a vast variety of environments.