References

[1] N. Sabater, A. Almansa et J.-M. Morel, Rejecting Wrong Matches in Stereovision. CMLA preprint 2008-28.

[2] Middleburry dataset. http://vision.middlebury.edu/stereo/.

Experiments

Simulated Pair:

First image

Disparity. Red pixels aren’t matched (rejected by the a contrario method or the fattening correction.)

Groundtruth

Noise error estimation at each point. The darker the pixel, the higher the error.

SNR RMSE Matches Bad matches Predicted noise error
∞ 0.023 70.6%  0%  0
357.32 0.033 63.3%  0%  0.023
125.06 0.058 41.5%  0.02%  0.065

Root Mean Squared Error for different Signal to Noise Ratios.

Lion Experiment:

First image

Upper view of the 3D rendering of the computer surface

Disparity map

Slanted view of the computed surface with the reference image

Stereo benchmark: The Middlebury dataset [2] provides 9 orthorectified views at uniform intervals of piecewise planar scenes. A cross-validation is done taking the central view as reference:

Matches Bad Matches RMSE Predicted noise error
Sawtooth 45.2 % 0.1 % 0.090  0.081
Venus 47.2 % 0.1 % 0.056  0.061

First image  Groundtruth  Disparity map

Correcting the Fattening Effect

• Dilation of the size of the patch of structures with boundaries coinciding with depth discontinuities.

• PROPOSED APPROACH: Compute a new disparity map which considers the disparity computed at pixel x as a feasible disparity for a whole set of pixels: namely, all pixels in the patch with best matching gradient angle. Reject the match when the two solutions differ by more than the allowed precision.

Subpixel Accuracy:

• Once a meaningful match have been found in x_{0} its disparity is refined.

μ^{d}(x_{0}) := arg min_{μ∈ℝ} e_{x_{0}}^{d}(μ), e_{x_{0}}^{d}(μ) := ∥τ_{μ}u − ũ∥_{φ_{x_{0}}}^{2} ,

where ⟨ u, v⟩_{φ_{x_{0}}} is the weighted discrete scalar product and ∥·∥_{φ_{x_{0}}} the corresponding weighted norm. We write τ_{μ}u(x) = u(x + μ), and φ_{x_{0}} = φ(x − x_{0}) is a symmetric and normalized window in a compact support (e.g. prolate). Theorem 2. Assuming that ũ(x) = u(x + ε(x)) + n(x) where the noise n ∼ N(0, σ) . Then

μ^{d}(x_{0})−ε(x_{0}) = \underbrace{\frac{⟨ u^{′2}, ε⟩_{φ_{x_{0}}}}{∥u′∥_{φ_{x_{0}}}^{2}} − ε(x_{0})}_{fattening error} + \underbrace{\frac{⟨ u′, n⟩_{φ_{x_{0}}}}{∥u′∥_{φ_{x_{0}}}^{2}}}_{noise error∼N(0,\frac{σ∥u′∥_{φ{2 \atop x_{0}}}}{∥u′∥{2 \atop φx_{0}}})} +o(|μ^{d}−ε|^{2})

Remark By Thm 2 the noise error is estimated at each point x_{0}.

Full Control of False Matches

• Feature Extraction: Local PCA. The patch features are the PCA coefficients trained separately for patches with similar mean and variance. ADVANTAGE: More precise results in regions with lack of information (shadows and saturated regions).

• The a contrario model is a statistical model for image patches deriving from the Helmholtz Principle: A geometric structure is meaningful if the expected number of occurrences is very small in white noise. In our case: An empirical background model is fixed from the images. The relevant matches are detected as rare events for this model.

- Let B_{q} be a block in the reference image. The empirical probability that an observed block B_{q′} in the secondary image be similar to B_{q} for the feature i is

{ \atop p^{i}(q, q)} = 2 · |H_{i}(q) − H_{i}(q′)| ,

where H_{i} is the cumulative histogram of the principal components coefficients for the secondary image.

- The Number of False Alarms (NFA) is the expected number of appearances of the match (q, q′) :

NF A_{q,q′} = N_{test} · ∏_{i=1}^{N} p_{q,q′}^{i} ,

where N_{test} is the number of matches to be tested, N is the number of principal components considered and p_{q,q′}^{i} is a quantification of p̂_{q,q′}^{i} and is imposed to be non-decreasing in i.

- A match (q, q′) is ϵ-meanigful when NF A_{q,q′} < ϵ.

Theorem 1. Under the a contrario assumption that all principal components are independent, 𝔼#{ε − meaningful matches} ≤ ε.

CAUSE OF FALSE MATCHES PROPOSED SOLUTIONS
Occlusions , moving objects and noise  a contrario model
Poor textured regions  Local PCA
Stroboscopic effects  Self-similarity threshold

Summary

A new parameterless method for detecting matches in pairs of stereo images with virtually no false matches [1] is proposed. A very precise disparity map is provided avoiding the fattening effect. Matches are found a contrario and Principal Component Analysis (PCA) is used to extract a feature vector in each point. The subpixel accuracy is obtained by interpolating and minimizing the quadratic distance under Shannon conditions.

Neus Sabater

Sabater@cmla.ens-cachan.fr

ERROR-FREE STEREO REACHES OPTIMAL THEORETICAL ACCURACY