We present a new compression algorithm for video sequences of indoor scenes, or more generally, sequences containing mostly planar and near-planar surfaces. Our approach utilizes edge and optical flow information in order to segment selected keyframes into regions of general shape, such that the motion of each region is predicted well by a planar homography. With this kind of motion prediction, the errors between the predicted intermediate frames and the actual ones are very small, and can be compactly encoded. Our results demonstrate significant improvements in the accuracy of the compressed video sequences, compared to standard general-purpose video compression.