We describe an algorithm that takes as inputs a coarse3D model of an environment, and a video sequence acquiredwithin the environment, and produces as output an estimateof the camera’s 6-DOF egomotion expressed in the coordinatesof the 3D model. Our method has several novelaspects: it performs line-based structure-from-motion; italigns the local line constellation to the known model; andit uses off-line visibility analysis to dramatically acceleratethe alignment process.We present simulation results demonstrating themethod’s operation in a multi-room environment. We showthat the method can estimate metric egomotion accuratelyand could be used for for many minutes of operation andthousands of video frames.