Weighted matchings for dense stereo correspondence

Gabriel Fielding, Moshe Kam

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1511-1524
Number of pages14
JournalPattern Recognition
Issue number9
StatePublished - Sep 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


  • Bipartite graph
  • Dynamic programming
  • Greedy matching
  • Matching algorithms
  • Stereo vision
  • Weighted matching


Dive into the research topics of 'Weighted matchings for dense stereo correspondence'. Together they form a unique fingerprint.

Cite this