Abstract: This paper describes a system for structure from motion using vanishing points and three-dimensional lines extracted from omni-directional video sequences. To track lines, we use a novel dynamic programming approach to improve ambiguity resolution, and we use delayed states to aid in the initialization of landmarks. By reobserving vanishing points we get direct measurements of the robot's three-dimensional attitude that are independent of its position. Using vanishing points simplifies the representation since parallel lines share the same direction states. We show the performance of the system in various indoor and outdoor environments and include comparisons with independent two-dimensional reference maps for each experiment .