Methods and apparatus for robust video stabilization. A video stabilization technique applies a feature tracking technique to an input video sequence to generate feature trajectories. The technique applies a video partitioning technique to segment the input video sequence into factorization windows and transition windows. The technique smoothes the trajectories in each of the windows, in sequence. For factorization windows, a subspace-based optimization technique may be used. For transition windows, a direct track optimization technique that uses a similarity motion model may be used. The technique then determines and applies warping models to the frames in the video sequence. In at least some embodiments, the warping models may include a content-preserving warping model, a homography model, a similarity transform model, and a whole-frame translation model. The warped frames may then be cropped according to a cropping technique.