An efficient technique is presented for detecting, tracking and locating three-dimensional (3-D) line segments. The utility of this technique has been demonstrated by the SRI mobile robot, which uses it to locate features in an office environment in real time (one Hz frame rate). A formulation of Structure-from- Motion using line segments is described. The formulation uses longitudinal as well as transverse information about the endpoints of image line segments. Although two images suffice to form an estimate of a world line segment, more images are used here to obtain a better estimate. The system operates in a sequential fashion, using prediction-based feature detection to eliminate the need for global image processing.