Stable Matching for Stereoscopic Vision

Radim Sara
Center for Machine Perception
Czech Technical University in Prague

The Larch Grove Stereo Pair

LarchGrove: left image     LarchGrove: right image
(suitable for cross-eyed viewing from about 15cm distance, click to download full-size rectified images)

Dense binocular stereo is a challenging problem, since the correspondence problem is generally of combinatorial complexity. Why? It has to segment the image to

  1. binocularly visible regions (and to find correspondences within them),
  2. half-occluded regions that have no correspondence in the other image,
  3. mutually occluded regions, they are regions in the left image that correspond to entire regions in the right image, but within these regions no correspondence can be found. This is a quite frequent event in general scenes, in the Larch Grove Example it is the region in between the two leftmost trees.
Current algorithms avoid the complexity by posing the stereo correspondence as an optimization problem with a cost functional, usually including a prior continuity term. They are (typically) not of combinatorial complexity at the price that where the image texture is insufficient, ambiguous, or correspondence does not exist the prior model prevails, which results in artifacts. The way out is to restrict admissible scenes to continuous surfaces without self-occlusions.

Another way to avoid the complexity is to use different notion for what is a good matching. We propose the game-theoretic notion of stability. Fortunately, it is possible to define stability in a way that (low-order) polynomial algorithm exists. We claim stability is a suitable and practical concept for stereoscopic matching.

We pose the correspondence as the confidently stable monotonic matching problem. Much of the matching artifacts is then avoided. The algorithm is parameter-free except for confidence level at which we wish to recover a matching. Results are not guaranteed to be dense but the density is high enough for the approach to be viable. Moreover, the density can be dramatically improved (even five-folds) if the matching process is stratified (ongoing work with Jana Kostkova).

Confidently stable matching results for increasing confidence interval width

assumes ordering, uses 5x5 matching window, Normalized Cross-Correlation (NCC), unmatched regions are gray, disparity is color-coded from blue (small disparity) to red (large disparity), click to get full-size disparity maps
0% of NCC range 0.5% of NCC range
1.5% of NCC range 5% of NCC range



Radim Sara
Last modified: Tue Jun 25 13:47:47 CEST 2002