In this paper, we propose a novel linear programming based method to estimate arbitrary motion from two images. The proposed method always finds the global optimal solution of the linearized motion estimation energy function and thus is much more robust than traditional motion estimation schemes. As well, the method estimates the occlusion map and motion field at the same time. To further reduce the complexity of even a complexity-reduced pure linear programming method we present a two-phase scheme for estimating the dense motion field. In the first step, we estimate a relatively sparse motion field for the edge pixels using a non-regular sampling scheme, based on the proposed linear programming method. In the second step, we set out a detail-preserving variational method to upgrade the result into a dense motion field. The proposed scheme is much faster than a purely linear programming based dense motion estimation scheme. And, since we use a global optimization method — linear programming — in the first estimation step, the proposed two-phase scheme is also significantly more robust than a pure variational scheme.