See discussions, stats, and author profiles for this publication at: [Link]
net/publication/4245700
Local Stereo Matching with Segmentation-based Outlier Rejection
Conference Paper · July 2006
DOI: 10.1109/CRV.2006.49 · Source: IEEE Xplore
CITATIONS READS
120 944
2 authors, including:
Philippe Bekaert
Hasselt University
210 PUBLICATIONS 5,590 CITATIONS
SEE PROFILE
All content following this page was uploaded by Philippe Bekaert on 01 June 2014.
The user has requested enhancement of the downloaded file.
Local Stereo Matching with Segmentation-based Outlier Rejection
Mark Gerrits and Philippe Bekaert
Hasselt University
Expertise Centre for Digital Media
and transnationale Universiteit Limburg
School of Information Technology
Wetenschapspark 2, 3590 Diepenbeek, Belgium
{[Link], [Link]}@[Link]
Abstract Fast area-based approaches will focus mostly on the ag-
gregation step and utilize straightforward techniques, such
We present a new window-based stereo matching algo- as simple Winner-Takes-All, to determine the disparities.
rithm which focuses on robust outlier rejection during ag- Unfortunately, they run into problems when deciding the
gregation. The main difficulty for window-based methods window size to be used during cost aggregation. Small win-
lies in determining the best window shape and size for each dows do not contain enough information and lead to noisy
pixel. Working from the assumption that depth disconti- results, while large windows contain enough texture infor-
nuities occur at colour boundaries, we segment the refer- mation but encompass pixels at different depths near depth
ence image and consider all window pixels outside the im- discontinuities, which leads to overblown foreground ob-
age segment that contains the pixel under consideration as jects, the foreground fattening effect[11].
outliers and greatly reduce their weight in the aggregation To obtain better results, most recent techniques have fo-
process. We developed a variation on the recursive mov- cused on better global optimisation algorithms to calcu-
ing average implementation to keep processing times inde- late the disparities. In this, they have been successful.
pendent from window size. Together with a robust match- The newest techniques such as Bleyer and Gelautz’ lay-
ing cost and the combination of the left and right disparity ered stereo algorithm[1] can generate high-quality dispar-
maps, this gives us a robust local algorithm that approxi- ity maps. However, these techniques are often quite slow,
mates the quality of global techniques without sacrificing making them unsuitable for most interactive applications or
the speed and simplicity of window-based aggregation. for processing large amounts of high resolution data (such
as would be necessary for video based rendering/animation
applications). Furthermore, their complexity makes them
inflexible and therefore difficult to implement in a scalable
1. Introduction manner, on distributed systems or on specialized hardware,
hampering their practical usability.
The stereo correspondence problem is an important chal- We focus on improving the aggregation step in order to
lenge in computer vision. Much work is increasingly be- develop an algorithm with the time complexity and relative
ing done on stereo algorithms that produce dense dispar- simplicity of local techniques, but which approaches the
ity maps, as these can be used for view synthesis and accuracy of the global techniques. We assume that depth
video based rendering. A thorough survey and taxonomy discontinuities coincide with colour boundaries, a common
of dense stereo techniques was provided by Scharstein and enough assumption. Working from this assumption, we will
Szeliski[11]. Their work illuminates an important distinc- use a segmentation of the reference image to reject outliers
tion between fast local methods and high quality global in the aggregation window. Any pixels outside the image
methods. segment belonging to the central pixel are weighted by a
Most stereo algorithms work in four steps: (1) comput- small value to reduce their influence. This allows us to avoid
ing a matching cost for each pixel at each disparity, (2) the foreground fattening effect while still being able to use
aggregating the costs across pixels at the same disparity, large windows which contain enough texture information to
(3) calculating the best disparities based on the aggregated avoid ambiguities. To exploit this, we developed a variant of
costs and (4) optionally refining the disparities. the recursive moving average filter to keep execution times
independent of the window size and maintain high perfor- warping step. The results produced by this approach clearly
mance rates. maintain the depth discontinuities. Bleyer and Gelautz [1]
expanded this technique to allow pixels to change segments
2. Related Work for better results.
Zhang and Kambhamettu[17] presented a stereo match-
ing algorithm with integrated 3D scene flow computation.
In 2001, Scharstein and Szeliski published a taxonomy
The algorithm consists of a hierarchical rule-based match-
and evaluation of dense stereo algorithms [11]. This work
ing scheme employing color segmentation to enforce depth
further illustrated the intuitive notion that while local tech-
discontinuities. The set of rules adaptively guides the inter-
niques excell at achieving high speeds, global techniques
polation within each segment and helps find occluded areas.
are better suited to generate high quality disparity maps.
Scene flow is estimated via an energy minimization proce-
Consequently, most recent work has focused on develop-
dure and later applied as constraints on the depth estimation
ing global algorithms. But significant work has also been
to make it more accurate and robust.
done on local methods.
Zitnick et al.[3] employed a two-layered depth represen-
Adaptive-window methods change the size and shape of
tation. Their focus is on video based rendering. Depth
their window adaptively for each pixel. Kanade and Oku-
values are estimated for each input frame using a matching
tomi [7] evaluated the local variation of intensity and dis-
scheme based on color segmentation. While this method is
parity at each pixel to select an appropriate window. Their
capable of rendering high-quality disparity maps and ren-
window shape was limited to rectangles and therefore ran
derings, the computation of depth values for each input
into problems near arbitrarily shaped depth discontinuities.
frame required intensive processing times.
The method was also computationally expensive and re-
lied heavily on a sufficiently accurate initial disparity es-
timation. Veksler [13][14] developed a new window cost 3. Approach
which allowed for efficient evaluation across a range of
window shapes and sizes. However, the window shapes 3.1 Overview
were still constrained and the method required many user-
specified parameters. To improve performance, multiple-
window methods [4][8] use a small number of predefined We start out by applying a robust function to our per-
windows amongst which they choose the optimal one. But pixel matching costs to reduce the influence of all outlier
as with the other methods, the window shapes are still not pixels. This gives us the disparity volume to aggregate over.
general enough to adapt to arbitrary depth discontinuities. During aggregation, all pixels inside the window whose
By assigning different support-weights to different pix- disparities differ greatly from the central pixel under consid-
els in the window, Prazdny [10] and Xu et al. [15] tried eration, should be considered as outliers. But it is exactly
to overcome this problem. The former assigned weights these disparities we are trying to determine. We solve this
to neighbouring pixels iteratively while the latter used ra- problem by making the assumption that depth discontinu-
dial computations. Both these methods are dependent on ities occur across colour discontinuities and use a segmen-
an initial disparity estimation, which needs to be accurate tation of the image to ignore outliers.
enough. Yoon and Kweon [16] eliminated this reliance by Finally we improve our results by combining the left and
using a non-iterative approach. They based their weights on right disparity maps.
the photometric and geometric relationship with the pixel
under consideration. They achieved good results but at a 3.2 Robust Matching Costs
high computational cost. Their technique was also suscep-
tible to image noise. The need for robust matching costs becomes clear when
In recent years, segmentation-based techniques have we look at the problem as one of pure outlier contamination.
proven adept at correctly handling edges. Though they of- After all, when aggregating the matching costs, pixels with
ten come at a computational cost, they have proven to be very high matching costs will disrupt the average, especially
some of the highest quality algorithms to date. near depth discontinuities where they will exert too much
Tao et al.[12] proposed an analysis-by-synthesis method influence. Scharstein and Szeliski[11] noted this and exper-
to maintain depth discontinuities. A reference image is seg- imented with truncated matching costs, which provided a
mented based on color and each image segment is then it- small improvement. We chose to use the Geman-McClure
eratively warped to the other views. The depth within an function[5], illustrated in Figure 1, a proven technique to
image segment is assumed to be smooth and representable handle outliers:
by a plane-plus-parallax model. The depth model of each x2
segment is refined based on the prediction error after each ρ(x) = 2
x + σ2
1
depth discontinuities occur on segment boundaries does not
0.9
imply that all adjoining segments lie on different depths. In
0.8 fact, in any moderately textured region, this will most likely
0.7 not be the case. These areas produce lots of small image
0.6
segments which, taken on their own, wouldn’t provide suf-
ficient information for aggregation. By weighing the pixels
0.5
outside of the window with a small weight λ, we can aggre-
0.4
ó = 0.001
gate enough information in these areas while still remaining
ó = 0.05
0.3 ó = 0.1
ó = 0.2
accurate around depth discontinuities.
0.2 Because we aggregate across a window and thus not nec-
0.1
essarily across all pixels in a segment, we are protected
0
from some artefacts of undersegmentation, where depths
0 5 10 15 20 25 30 35 40 45
from one object will cut into another object because an im-
age segment crosses an object boundary. In the hypothet-
Figure 1. The Geman-McClure function ical worst-case scenario where the whole image is one big
segment, our technique will still score equally well as the
Beyond a certain point, determined by σ, its influence be- normal aggregation technique combined with the Geman-
gins to descend and smoothly converges to zero. The trans- McClure function, whereas other segmentation based tech-
formed matching cost ρ(x) converges to 1. Therefore, niques would run into severe problems.
no matter how large the raw costs become, after applying
Geman-McClure, they will never exceed 1. 3.4 Disparity Map Combination
3.3 Segmentation Based Outlier Rejection To improve the accuracy of our results, we calculate
a depth image for both stereo images and combine them
to eliminate some final oversegmentation artefacts. De-
Because window-based stereo aggregation methods (im-
pending on which view we are computing the disparity
plicitly) assume that all pixels within the window have
map for, we will warp the other disparity map back to this
similar disparities, they run afoul when windows strad-
view. Undersegmentation faults will lead more frequently
dle depth discontinuities. As discussed by Scharstein and
to overly high disparities than overly low disparities (be-
Szeliski’s[11], this results in a foreground fattening effect,
cause of the foreground fattening effect). Therefore, assum-
as pixels near depth discontinuities become bimodal and
ing that the undersegmentation fault only occurs in one of
will display a strong preference towards the foreground dis-
the two views, we take the minimum of both disparity maps.
parity, even if they are in the background.
An example of an undersegmentation mistake can be seen
We assume that depths vary smoothly within any image
on the left of the sculpture in Figure 5(e). It has disappeared
segment with homogeneous colour. Based on this assump-
in Figure 5(a) after the two disparity maps have been com-
tion, we can disregard or diminish the influence of those
bined.
pixels within the aggregation window which fall outside the
This technique has the added advantage of improving
image segment that contains the central pixel under consid-
disparities in occluded areas, as pixels in these areas will
eration. We use Comaniciu and Meer’s mean shift algo-
usually have too high disparities as they try to move out
rithm [2] to segment the reference image. Their implemen-
from under the occluding object to match with similar pix-
tation generates segmentations of a sufficiently high quality
els in the background object.
at acceptable speeds for our purposes but any segmentation
method which is accurate enough around colour boundaries
would do. 4. Implementation
Unlike other segmentation based techniques we do not
impose that all pixels in the same segment must share the Most window-based aggregation techniques thank their
same depth or lie on a simple, locally fitted surface such as high performance speeds to the fact that they can be im-
a plane. Instead, we use the segmentation as a guide for plemented as recursive moving average filters with running
robust aggregation. Ideally, any pixels outside the image times independent of the window size.
segment should be considered outliers. However, these out- While our segmentationbased outlier rejection allows for
lier pixels are not completely ignored in our aggregation but windows of arbitrary size without suffering from the fore-
receive a small weight λ compared to the pixels inside the ground fattening effect, the recursive moving average filter
image segment. We do this to protect our algorithm from implementation will no longer work in this case. When ag-
oversegmentation artefacts. After all, the assumption that gregating the disparity rows in the classic recursive imple-
mentation of the moving average filter, the aggregated value
Ai+1 for pixel i + 1 equals Ai - Ci−w/2 + Ci+w/2 , where
Cx is the matching cost at pixel x. Unfortunately, when
working with segments, pixels i, i + 1, i − w/2 and i + w/2
can all fall in different segments.
Algorithm 1 Segmented Moving Average
1. For each row:
(a) For each segment s: Ts = 0
(b) For each pixel i in row j:
i. Tsi+w/2,j = Tsi+w/2,j + Ci+w/2,j
ii. Tsi−w/2,j = Tsi−w/2,j − Ci−w/2,j
(a) Teddy, 30 disparities
iii. Ari,j = Tsi,j
iv. Asi,j = Asi−1,j + Ci+w/2,j − Ci−w/2,j
2. For each column:
(a) For each segment s: Ts = 0
(b) t = 0
(c) For each pixel j in column i:
i. Tsi,j+w/2 = Tsi,j+w/2 + Asi,j+w/2
ii. Tsi,j−w/2 = Tsi,j−w/2 - Asi,j−w/2
iii. t = t + Ari,j+w/2 - Ari,j−w/2
iv. Ai,j = λ × (t − Tsi,j ) + Tsi,j
(b) Cones, 16 disparities
A brute force implementation of the segmentation-based
moving average filter would be far too slow to be of any
practical use. Therefore we developed a variation on the Figure 2. Results of our algorithm on some of
moving average algorithm, so that our aggregation speeds the Middlebury datasets
are again independent from the window size, allowing us to
use large windows without any speed penalties.
Our solution is explained in simplified form in Algorithm cantly faster and less complex, our results approach those
1. Trivial precautions that need to be taken at the borders of of global correspondence techniques. Calculating the final
the image are left out for clarity. For each segment s, we disparity map with 51 × 51 windows and λ = 0.01 for the
keep track of a running average Ts . As the edges of our Tsukuba stereo pair took 1.26 seconds in a C++ implemen-
aggregation interval move through different segments, we tation on a 3 GHz Pentium 3 computer. Approximately 35%
update the corresponding averages. To find the aggregated of that time was spent on segmentation, 20% on calculating
cost Ar of the central pixel in the interval, we simply check the per-pixel matching costs, 25% on aggregation and 15%
which segment the pixel falls into and look up its average. on combining the two disparity maps.
At the same time, we also perform regular recursive moving
Even on cases which do not lend themselves well to seg-
average computation (As ) so we can combine the aggre-
mentation at all, our technique still produces respectable re-
gated value inside the segment with the aggregated value
sults. We illustrate this in figure 4. In this artificial example,
outside the segment, weighed by a factor λ.
the background plane is filled with random noise in front of
which lies a square, also textured with random noise. Even
5. Results in these strained circumstances, we still manage to extract
the general shape of the square.
Figure 3 shows some results of our algorithm. Figure 3 Figure 5 shows the disparity maps look with each part
and Table 1 show our result on the Tsukuba data compared of our algorithm left out, to illustrate how they complement
to other techniques. Even though our algorithm is signifi- each other to achieve robust disparity estimation.
(a) Ground truth (b) SSD + MF from [11] (c) State of the art, [1] (d) Our method
Figure 3. Comparison of our technique with others
Algorithm Tsukuba Venus Teddy Cones
Segm+visib [1] 1.57 1.06 6.54 8.62
AdaptWeight [16] 1.85 1.19 13.3 9.79
GC+occ [9] 2.01 2.19 17.4 12.4
Our method 2.27 1.22 19.4 17.4
Reliablty-DP [6] 3.39 3.48 16.9 19.9
GC [11] 4.12 3.44 25.0 18.2 (a) Left view (b) Right view
SSD+MF [11] 7.07 5.16 24.8 19.8
Table 1. Percentage of badly labeled dispari-
ties of several techniques, including ours, on
the Middlebury test case
6. Conclusion
In this paper, we have shown how local, window based
stereo aggregation can be performed with arbitrarily sized
windows without suffering from the foreground fattening
effect. We used a combination of robust matching costs (c) Disparity map
based on the Geman-McClure function, and segmentation-
based outlier rejection. We developed a variation on the Figure 4. Results on a randomly textured
recursive moving average filter to keep running times inde- square in front of a randomly textured back-
pendent of the window size. By combining the left and right ground plane. This illustrates that our tech-
disparity map, we further improved our results. nique degrades gracefully in cases unsuit-
Using these techniques, we approach the results of global able for segmentation.
methods without sacrificing the simplicity, flexibility and
speed of local aggregation methods. This opens interesting
perspectives for distributed or hardware specific implemen-
tations. nology (IBBT), and from a research grant by the EU (IST-
In the future, we plan to investigate some of these av- 2-511316-IP ”Racine-IP”)
enues as well as try out different segmentation algorithms Furthermore we would like to thank Tom Mertens for
in order to achieve interactive speeds. We also plan to im- providing the impetus for this research and Tom Haber and
prove our disparity map combination by taking into account Cedric Vanaken for their help.
matching costs.
References
Acknowledgements The authors acknowledge financial
support on a structural basis from the ERDF (European Re- [1] M. Bleyer and M. Gelautz. A layered stereo algorithm using
gional Development Fund), the Flemish Government and image segmentation and global visibility constraints. ICIP,
the Flemish Interdisciplinary institute for BroadBand Tech- 2004.
[2] D. Comaniciu and P. Meer. Mean shift: A robust approach
toward feature space analysis. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 24, 2002.
[3] L. Z. et al. High-quality video view interpolation using a
layered representation. Siggraph, 2004.
[4] A. Fusiello, V. Roberto, and E. Trucco. Efficient stereo with
multiple windowing. Proc. IEEE Conf. Computer Vision and
Pattern Recognition, 1997.
[5] S. Geman and D. McClure. Statistical methods for tomo-
graphic image reconstruction. Bulletin of International Sta-
tistical Institute, 1987.
[6] M. Gong and Y. Yang. Near real-time reliable stereo match-
ing using programmable graphics hardware. CVPR, 2005.
[7] T. Kanade and M. Okutomi. A stereo matching algorithm
with and adaptive window: Theory and experiments. IEEE
Trans. Pattern Analysis and Machine Intelligence, 16(9),
1994.
[8] S. B. Kang, R. Szeliski, and C. Jinxjang. Handling occlu-
sions in dense multi-view stereo. Proc. IEEE Conf. Com-
puter Vision and Pattern Recognition, 1, 2001.
[9] V. Kolmogorov and R. Zabih. Computing visual correspon-
dence with occlusions using graph cuts. ICCV, 2001.
[10] K. Prazdny. Detection of binocular disparities. Biological
Cybern, 52, 1985.
[11] D. Scharstein and R. Szeliski. A taxonomy and evaluation
of dense two-frame stereo correspondence algorithms. IJCV,
47, 2002.
[12] H. Tao, H. Sawhney, and R. Kumar. A global matching
framework for stereo computation. In International Con-
ference on Computer Vision, 1, 2001.
[13] O. Veksler. Stereo correspondence with compact windows
via minimum ratio cycle. IEEE Trans. Pattern Analysis and
Machine Intelligence, 24(12), 2002.
[14] O. Veksler. Fast variable window for stereo correspondence
using integral images. Proc. IEEE Conf. Computer Vision
and Pattern Recognition, 1, 2003.
[15] Y. Xu, D. Wang, T. Feng, and H. Shum. Stereo computa-
tion using radial adaptive windows. Proc. Int’l Conf. Pattern
Recognition, 3, 2002.
[16] K.-J. Yoon and I.-S. Kweon. Adaptive support-weight ap-
proach for correspondence search. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 2006.
[17] Y. Zhang and C. Kambhamettu. Stereo matching with
segmentation-based cooperation. ECCV, 2002.
(a) Result of our technique (b) Ground truth
(c) Without giving a small weight to pixels outside the segment (d) Without robust matching costs
(e) Without combining the disparity maps (f) Without segmentation-based outlier rejection
Figure 5. Each part of our algorithm contributes to the robustness of the disparity maps
View publication stats