high performance computing on graphics processing units: hgpu.org

We provide an analysis of several linear programming relaxations for the problems of stereo disparity estimation and motion estimation. The problems are cast as integer linear programs and their relaxations are solved approximately either by block coordinate descent (TRW-S and MPLP) or by smoothing and convex optimization techniques. We include a comparison to graph cuts. Indeed, the best energies are obtained by combining move-based algorithms and relaxation techniques. Our work includes a (slightly novel) tight relaxation for the typical motion regularity term, where we apply a lifting technique and discuss two ways to solve the arising task. We also give techniques to derive reliable lower bounds, an issue that is not obvious for primal relaxation methods, and apply the technique of (Desmet et al., 1992) to a-priori exclude some of the labels. Moreover we investigate techniques to solve linear and convex programming problems via accelerated first order schemes which are becoming more and more widespread in computer vision.