Subsections

• Introduction
• Quantitative Evaluation Metric
• Standard Stereo Pairs
  • `Tsukuba'
  • `Map'
  • `Sawtooth'
  • `Venus'
  • `Cones'
  • `Teddy'
  • Comparison of disparity maps
  • 3D Visualisation
  
  
• Noisy Stereo Pairs
  • White Gaussian Noise
  • Contrast Variations
  
  
• Summary

---

Introduction

This chapter presents two groups of experiments to evaluate the performance of NCSM algorithms. The evaluation used quality metrics proposed by Scharstein and Szeliski [4]. The test data sets consisted of six stereo pairs of images shown in Figures  , , , ,   and  , `Tsukuba', `Map', `Sawtooth', `Venus', `Teddy' and `Cones', respectively. The data available on the Middlebury Website [76] include the left and right images of each pair and the ground truth (range images with grey-scale coding of disparities).

The first group of experiments involved these six ``standard" stereo pairs. Disparity Maps obtained by NCSM-SDPS and NCSM-ITER were compared both quantitatively and qualitatively with those produced by other stereo algorithms. The second group of experiments was conducted with same stereo images under extra synthetic noise that consisted of a contrast change and an additive White Gaussian Noise (WGN) in the right images. The ability of NCSM-ITER to handle images with large contrast deviations was compared with other stereo algorithms.

Quantitative Evaluation Metric

Recently, Scharstein and Szeliski augmented their initial taxonomy and then extended their objective comparison to more than thirty algorithms [4]. They proposed two methods for evaluating the accuracy of a stereo reconstruction, given the ground truth; namely, the Root Mean Square (RMS) error, between each computed disparity at position and the corresponding ground truth disparity :

The relative number of the poorly matching pixels in non-occluded regions, , is defined:

where , if and 0 otherwise.

The relative number of the poorly matching pixels in textureless regions, , is defined:

The relative number of the poorly matching pixels in regions of discontinuity, , is defined:

Definitions of the texturless, , occluded, and depth discontinuity, , regions take account of results of pre-processing of reference images and ground truth disparity [4]. The textureless region is that where the squared horizontal intensity gradient averaged over a square window of a given size is below a given threshold; the occluded region appears where the forward mapped disparity lands at a location of a larger disparity; the depth discontinuity region includes pixels whose neighboring disparity differ by more than a threshold [4].

An alternative method for evaluating the accuracy of a stereo reconstruction was used when there no ground truth is available. In this case, a qualitative evaluation uses the estimated disparity map to warp a reference image to a new view, and compares the resulting image to the actual image from the new viewpoint [4].

Standard Stereo Pairs

NCSM-SDPS and NCSM-ITER algorithms were tested on six stereo pairs. Below, examples of the first step of the NCSM based on two different noise estimation methods were illustrated for each stereo pair below by using -slices of the candidate volumes. The empirical noise distributions for these images were computed using the known ground truth. The subsequent surface fitting step was shown also by the -slices compared to ideal surfaces representing the known ground truth. The final disparity maps obtained by NCSM algorithms were compared to maps reconstructed by other stereo algorithms.

`Tsukuba'

The stereo pair, `Tsukuba', in Figure  originally prepared by Ohta and Nakamura, is a real indoor scene with several distinct layers of disparity. Object boundaries are relatively complex, e.g. the long thin structure of the lamp's arm. Figure  shows the distribution of noise for `Tsukuba'. Many of the algorithms cannot accurately find these disparities [4]. Results for this stereo pair have already been shown in Chapter  along with the description of NCSM algorithms.

`Map'

The greyscale stereo pair, `Map', in Figure  has two highly textured and slanted surfaces. The matching difficulties result from a significant occlusion on the background surface because of relatively large disparity difference between the two surfaces. Figure  shows the distribution of noise for `Map': note that most of pixels in this stereo pair do not match because of geometric and optical distortions caused by large occlusions. Figure  shows ideal -slices surfaces of `Map' based on its ground truth disparity map. Figures  and   present candidate volumes and surface fitting produced by NCSM-SDPS and NCSM-ITER, respectively.

`Sawtooth'

The stereo pair, `Sawtooth', in Figure  includes three textured slanted planes with a blue textureless background. Matching problems occur along the edges of slanted planes. Figure  shows the distribution of noise for `Sawtooth'. Figure  illustrates ideal surfaces of the `Sawtooth' based on its ground truth disparity map. Figures  and   present candidate volumes and surface fitting produced by NCSM-SDPS and NCSM-ITER, respectively.

`Venus'

The stereo pair, `Venus', in Figure  is very similar to `Sawtooth' and meets with the same matching problems. `Venus' includes more regions with virtually no texture, and a clear edge shared by two of the surfaces. Figure  shows the distribution of noise for `Venus'. Figure  illustrates ideal surfaces of `Venus' based on its ground truth disparity map. Figures  and  present candidate volumes and surface fitting produced by NCSM-SDPS and NCSM-ITER, respectively.

`Cones'

The stereo pair, `Cones', in Figure  is one of two new stereo sets in the Middlebury database [76] with more complicated surfaces. Since the previous four stereo sets are too simple to easily discriminate between more and more advanced algorithms, the stereo pair, `Cones', with a large disparity range includes much more textureless areas, curved surfaces and thin foreground objects in order to challenge stereo algorithms. Figure  shows the distribution of noise for `Cones', and for space limitations, Figure  illustrates only the main ideal surfaces for the `Cones' based on its ground truth disparity map. Also, Figures  and   present candidate volumes and surface fitting produced by NCSM-SDPS and NCSM-ITER, respectively.

`Teddy'

The stereo pair, `Teddy', in Figure  is the second new complicated scene with a large disparity range including a large number of surfaces and more complex structures from soft toys and plants. Figure  shows the distribution of noise for `Teddy'. Figure  illustrates only the main ideal surfaces of `Teddy' based on its ground truth disparity map. Also, Figures  and  present candidate volumes and surface fitting produced by NCSM-SDPS and NCSM-ITER, respectively.

Comparison of disparity maps

Figure  show the true disparity maps for these six stereo pairs along with the disparity maps reconstructed using NCSM-SDPS, NCSM-ITER, Graph Minimum Cut with occlusions (GCO) [1], Symmetric Belief Propagation (SBP) [54], Maximum Flow/Minimum Cut (MCS) [45] and Symmetric Dynamic Programming Stereo (SDPS) [40] algorithms.

The performance of these algorithms according to the evaluation metrics of Section 4.2 but with some differences is shown in Table . The ``nonocc'' entry presents the percentage of ``bad" pixels only in non-occluded regions. Compared to the ''nonocc'' entry, the ``all'' entry includes partially occluded regions, and the ``dist'' entry presents the percentage of ``bad" pixels for the regions near depth discontinuities, occluded and border regions. Also, the pairs, `Cones' and `Teddy', replaced the previously used pairs, `Map' and `Sawtooth', in order to evaluate the performance on complex 3D structures with a large disparity range. Detailed analysis of the experimental results show that the NCSM framework yields strongly competitive results compared to the best-performing conventional algorithms on test stereo pairs, except `Venus' and `Cones', which have many slanted and curved surfaces. The reason is that the surface fitting approach in NCSM-SDPS and NCSM-ITER, to date, has been restricted, for simplicity, to only surface patches, and thus it handles slanted surfaces relatively poorly. More general surface fitting technique should overcome this drawback.

3D Visualisation

Figure  presents 3D reconstruction views of these test sets. The first column lists all 3D reconstruction results based on ground truth disparity maps, and the second column and the third column include the results from NCSM-SDPS and NCSM-ITER disparity maps, respectively.

Noisy Stereo Pairs

In many practical cases, noisy images can be described by an additive noise model, where the noisy image is the sum of the true (noiseless) image under contrast, , and offset, , deviation and the noise :

In stereo pairs, the noise components in different pixels are statistically independent where as the contrast and offset are limited to a certain range for adjacent binocularly visible points along with each epipolar line in NCSM-SDPS or are fixed for all binocularly visible points at the same disparity level in NCSM-ITER.

White Gaussian Noise

In these experiments, is an additive Gaussian noise affecting the right image of a stereo pair. The noise `level' is defined by the standard deviation. The noisy right images in Figure  were obtained by increasing from to ; the images becoming more and more grainy with growing standard deviation.

Figure  and present disparity maps obtained by Graph-Cut and Belief Propagation respectively with stereo pairs distorted by Gaussian noise. The disparity maps show that these algorithms-the best performers for images with low noise-completely fail on noisy stereo pairs. Results from SDPS in Figure  are slightly better, but also fail for high noise. The disparity maps of NCSM-SDPS and NCSM-ITER in Figures  and  , respectively are visually better and quite similar, except for `Map' and 'Venus'. Figure ,  and  show the RMS error plots for each stereo pair under the different noise levels. Clearly, the RMS's of disparity maps for GC, BP and SDPS increase rapidly so that these algorithms fail for high noise, but RMS's for NCSM-SDPS and NCSM-ITER have a slow increase, so that results are almost same both before and after adding the synthetic noise, even at quite high noise levels.

Contrast Variations

Since stereo requires two images-taken by different cameras or by the same camera at different times-variations in contrast are a continuing problem in real systems. In this set of experiment, the contrast range of the right image of each stereo pair was changed to a new intensity range, e.g. the transformed right images in Figure  are obtained by varying the initial image contrast in the range . For example, for a contrast change, the range is shrunk by of the total range at each end, so that the range becomes .

Figure  and present disparity maps obtained by the Graph Minimum-Cut and Belief Propagation algorithms with varying contrast differences, respectively. These algorithms fail for both increased and reduced contrast range. Figure  shows that the performance of SDPS is slightly better, but also fails with large contrast variation. The disparity maps for NCSM-SDPS and NCSM-ITER are shown in Figures  and respectively. NCSM-ITER works slightly better than NCSM-SDPS on noisy image pairs of higher contrast. Figures ,  and  plot the RMS error for each stereo pair. Graph Minimum-cut and Belief Propagation algorithms obviously fail on noisy image pairs of both higher and lower contrast, NCSM-SDPS and NCSM-ITER are able to handle these noisy image pairs, the performance of NCSM-ITER is slightly better than of NCSM-SDPS.

Summary

Tables  and summarise the performance of these algorithms using the metrics of Section 4.2 for image pairs with an additive fixed Gaussian noise () and a fixed contrast change ( with respect to the initial image). Even for , which means that a ``bad" pixel is defined by a very stringent condition: the RMS between each computed disparity at position and the corresponding ground truth disparity , is greater than , the NCSM algorithm yields stable results for stereo pairs with both added noise and contrast changes.

These results show that, a family of the NCSM algorithms (NCSM-SDPS and NCSM-ITER) produces the high quality 3D reconstruction for various stereo pairs and under different image distortions. The NCSM framework is generally performs as well as the best-performing conventional algorithms on the test stereo pairs with no contrast and offset deviations but notably outperforms these algorithms in the presence of large contrast deviations and high additive noise.