Stable Matching for Stereoscopic Vision
Radim Sara
Center for Machine Perception
Czech Technical University in Prague
http://cmp.felk.cvut.cz
The Larch Grove Stereo Pair
(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
- binocularly visible
regions (and to find correspondences within them),
- half-occluded regions that have no correspondence in
the other image,
- 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
|
|---|
More
References
- Finding the Largest Unambiguous Component
of Stereo Matching. R. Sara. In Proceedings 7th
European Conference on Computer Vision (ECCV2002) vol. 2,
pp. 900-914, Springer-Verlag LNCS 2352, May 2002.
[Corrected paper, color version [PDF], Abstract+Paper (Springer)]
- Sigma-Delta Stable Matching for Computational Stereopsis
R. Sara. Research Report CTU-CMP-2001-25, Center for Machine
Perception, Czech Technical University, September 2001
[Sara-TR-2001-25.pdf]
- The Class of Stable Matchings for Computational Stereo.
R. Sara. Research Report CTU-CMP-1999-22, Center for Machine
Perception, Czech Technical University, November 1999.
[Sara-TR-1999-22.pdf, 2.5MB]
|
Radim Sara
|
Last modified: Tue Jun 25 13:47:47 CEST 2002
|
