Weighted matchings for dense stereo correspondence

The calculation of matches between pixels, points, or other features in stereo images is known as the correspondence problem. This problem is ill-posed due to occlusions; not every pixel, point or feature in one stereo image has a match in the other. Minimization of a cost function over some local region and dynamic programming algorithms are two well-known strategies for computing dense correspondences. However the former approach fails in regions of low texture, while the latter imposes an ordering constraint which is not always satisfied in stereo images. In this study, we present two new techniques for computing dense stereo correspondence. The new methods are based on combinatorial optimization techniques which require polynomial computation time. The first method casts the selection of matches as the assignment problem, solved efficiently by finding a maximum weighted matching on a bipartite graph. The second is a greedy algorithm which computes suboptimal weighted matchings on the bipartite graphs. Both methods use occlusion nodes when no matches exist. The resulting disparity maps have desirable properties such as dense correspondence, while avoiding the drawbacks associated with ordering constraints. Three existing matching approaches are also reviewed for comparative purposes. We test all five techniques on real and synthetic stereo images using performance criteria which specifically measure occlusion detection.