Abstract: This paper presents a novel approach to stabilize video sequences based on a 3D perspective camera model. Compared to previous methods which are based on simplified models, our stabilization system can work in situations where significant depth variations exist in the scenes and the camera undergoes large translational movement. We formulate the stabilization problem as a quadratic cost function on smoothness and similarity constraints. This allows us to precisely control the smoothness by solving a sparse linear system of equations. By taking advantage of the sparseness, our optimization process is very efficient. Instead of recovering dense depths, we use approximate geometry representation and analyze the resulting warping errors. We show that by appropriately constraining warping error, visually plausible results can be achieved even using planar structures. A variety of experiments have been implemented, which demonstrates the robustness and efficiency of our approach.