A mobile device uses vision and orientation sensor data jointly for six degree of freedom localization, e.g., in wide-area environments. An image or video stream is captured while receiving geographic orientation data and may be used to generate a panoramic cylindrical map of an environment. A bin of model features stored in a database is accessed based on the geographic orientation data. The model features are from a pre-generated reconstruction of the environment produced from extracted features from a plurality of images of the environment. The reconstruction is registered to a global orientation and the model features are stored in bins based on similar geographic orientations. Features from the panoramic cylindrical map are matched to model features in the bin to produce a set of corresponding features, which are used to determine a position and an orientation of the camera.