Algorithms for discrete energy minimization play a fundamental role
for low-level vision. Known techniques include graph cuts, belief
propagation (BP) and recently introduced tree-reweighted message
passing (TRW). So far, the standard benchmark for their comparison
has been a 4-connected grid-graph arising in pixel-labelling stereo.
This minimization problem, however, has been largely solved: recent
work shows that for many scenes TRW finds the global optimum.
Furthermore, it is known that a 4-connected grid-graph is a poor
stereo model since it does not take occlusions into account.
We propose the problem of stereo with occlusions as a new test bed
for minimization algorithms. This is a more challenging graph since
it has much larger connectivity, and it also serves as a better
stereo model. An attractive feature of this problem is that
increased connectivity does not result in increased complexity of
message passing algorithms. Indeed, one contribution of this paper
is to show that sophisticated implementations of BP and TRW have the
same time and memory complexity as that of 4-connected grid-graph
stereo.
The main conclusion of our experimental study is that for our
problem graph cut outperforms both TRW and BP considerably. TRW
achieves consistently a lower energy than BP. However, as
connectivity increases the speed of convergence of TRW becomes
slower. Unlike 4-connected grids, the difference between the energy
of the best optimization method and the lower bound of TRW appears
significant. This shows the hardness of the problem and motivates
future research.