COARSE-TO-FINE STRATEGY FOR EFFICIENT COST-VOLUME FILTERING
Ryosuke Furuta, Satoshi Ikehata, Toshihiko Yamasaki and Kiyoharu Aizawa
The University of Tokyo
ABSTRACT
Cost-volume filtering is one of the most widely known techniques to solve general multi-label problems, however it isproblematically inefficient when the label space size is extremely large. This paper presents a coarse-to-fine strategyof the cost-volume filtering that handles efficiently and accurately multi-label problems with a large label space size.
Based upon the observation that true labels at the same image coordinate of different scales are highly correlated, we
truncate unimportant labels for the cost-volume filtering byleveraging the labeling output of lower scales. Experimental results show that our algorithm achieves much higher efficiency than the original cost-volume filtering while enjoying
the comparable accuracy to it.
Index Terms— cost-volume filtering, Markov random
fields, label selection, coarse-to-fine
1. INTRODUCTION
Many low-level computer vision problems (e.g., stereo matching and optical flow estimation) are formulated as multi-label
problems where discrete labels (e.g., disparity and motion
vector) are assigned to pixels. There are generally two approaches to solve these problems: global and local. The
former models a labeling problem as a Markov random field(MRF) where global optimization techniques [1, 2, 3] areused to minimize the energy function. While effective, solving a large optimization problem makes the inference intractable when the image size is high or the label space islarge. More recently, Rhemann et al. [4] presented a local approach called cost volume filtering (CVF), which efficiently
solves general multi-label problems. The trick is that CVF
substitutes the fast local filtering of label costs for the global
smoothing in the MRF optimization. Since CVF is easy to implement yet provides high-quality results, it has been widelyused to solve various multi-label problems [5, 6, 7, 8, 9].
However, a limitation of CVF is that it does not scale to theextremely large label set (e.g., sub-pixel stereo matching andupsampling of the 16-bit depth map from the kinect sensor).
To tackle this difficulty, Lu et al. [10] have recently proposed PatchMatch Filter (PMF) algorithm which performs
CVF iteratively on local superpixels with compact label subsets instead of performing on the entire image coordinate.

Since the average size of local label subsets is generally muchsmaller than the size of the entire label subset, PMF is usually much more efficient than CVF while keeping its accuracy. Nevertheless, PMF relies on the complex patch-match
based global optimization to estimate a label subset for eachsuperpixel whose computational complexity increases in response to the number of superpixels, therefore less effective
when an image is divided into many superpixels.
This paper presents an alternative coarse-to-fine strategy
for efficiently estimating compact label subsets to solve thelabel space problem of the cost-volume filtering. Based upon
the observation that true labels at the same image coordinate
of different scales are highly correlated, we propose to leverage the labeling output of the lower scale for estimating local label subsets of the higher scale. Starting from the very
low-resolution image, we iteratively truncate unimportant labels of each higher scale and finally, we assign compact andapproximately optimal label subsets to local regions of theoriginal scale. The proposed framework benefits from simple, efficient coarse-to-fine strategy, which does not require
any global optimization like [10] and its computational complexity is less affected by the number of local regions. Extensive experiments in Sec. 3 show that our algorithm achieves
the higher efficiency than PMF and CVF while enjoying thecomparable or often superior accuracy to them.
2. COARSE-TO-FINE STRATEGY FOR EFFICIENTCOST VOLUME FILTERINGIn this section, we present a coarse-to-fine strategy of thecost-volume filtering (CVF) [4] for handling multi-label
problems with a large label space. Given a label set L ={l0 , · · · , lL−1 }, the goal of a multi-label problem is to assign
a label li ∈ L to each pixel i , [xi , yi ](i = 0, . . . , M − 1) in
the image coordinate I which minimizes the label costs thatare encoded in the energy function [4].
2.1. Cost-volume Filtering
CVF [4] solves multi-label problems by three steps. First,
a 3-D cost volume C is constructed as a collection of thecost for choosing label l at each pixel i which is based on
the data term in the energy function. Then each slice of thecost volume is independently filtered by an edge preservingIn-scale cost-volume filtering

Across-scale label propagation

Sjk+1 = Sjk ↓s .2 In addition, we represent a label subset for Sjk
as Lkj and its size as Lkj . The entire computational complexityof CVF from the lowest scale (k = n) to the original scale(k = 0) is described asO(ℒ𝑗2 ← ℒ𝑗

𝐶𝑗2

ℒ𝑗1

𝐶𝑗1

ℒ𝑗0

𝐶𝑗0

Fig. 1. A framework of proposed method.

filter [11, 12] which substitutes for the smoothness term in
the energy function. Finally, the label at pixel i is simply chosen in a winner-take-all strategy. When O(1) edge preserving
filter (e.g., guided filter [11]) is used, the computational complexity of filtering an entire cost volume is O(M L): M is thenumber of pixels in I and L is the size of L, which leads tothe difficulty in handling an extremely large label space.
One possible strategy for handling a large label space
problem is to locally change the label space for reducing thesize of label space. Because the true label configuration is
generally smooth in space (e.g., disparities are smooth except for object boundaries), the necessary label space for
performing CVF on a local region should be much smaller
than the entire label space. However, the problem is of course
we do not know a priori which labels are important for each
local region, and thus the estimation of local label subsets isrequired [10].
2.2. Problem Statement
Here we present a simple but efficient label subset estimation algorithm. Unlike Lu et al. [10], we do not rely on the
global optimization for estimating local label subsets instead
leveraging the coarse-to-fine framework. The overview of the
proposed method is illustrated in Fig. 1. Our algorithm consists of mainly two steps (i) in-scale cost-volume filtering and(ii) across-scale label propagation. An essential ingredient is
the latter step, where a local label subset is estimated from the
CVF output at its lower resolution. Since the computational
cost of CVF for a low-resolution image is less noticeable, we
perform CVF with a large label space at low-resolution andthen truncate unimportant labels using the output.
Let I k (k = 0, . . . , n − 1) denote a cascade of imagesof decreasing resolution ranging from the original scale (i.e.,k
I k+1 = I↓swhere ↓ is a down-scaling operator with a scale
factor s ∈ (0, 1))1 and Lk denote a set of all possible labels
at k-th scale which is given by L. Then we divide I 0 (= I)
into m non-overlapping local regions Sj0 and then partition
I k (k ≥ 1) into local regions Sjk (j = 1, . . . , m − 1) such that
1 We used “buildPyramid” function in OpenCV to downsample images.

n X
m
X

Mjk Lkj ),(1)

k=0 j=0

where Mjk is a number of pixels in Sjk (i.e., Mjk = s2k Mj0 ).
Therefore, our goal is to estimate compact label subsets Lkj
Pn Pmsuch that k=0 j=0 Mjk Lkj  M L while keeping the accuracy of CVF.
2.3. Across-scale Label Propagation
In this section, we present an algorithm to estimate compact
label subsets (Lkj ) which sufficiently reduce Eq. (1) without truncating important labels. Our algorithm is begun by
the coarsest scale (i.e., k = n − 1). At this scale, we set∀jLn−1← Ln−1 and simply perform CVF [4] to acquirejthe filtered cost volume C n−1 at (n − 1)-th scale3 . Notethat though we use a complete label set, the computational
complexity of CVF at this scale is O(s2(n−1) M L), whichis generally neglectable (e.g., if we set s by 0.5 and n by 4,O(s2(n−1) M L) ≈ O(10−2 × M L)). Then we initialize thelabel subset at the higher resolution (L̃jn−2 ) by merging labels
which have the smallest cost values in C n−1 at corresponding local regions Sjn−1 . Strictly speaking, the initializationis represented as[
L̃jn−2 =f (li ), li = arg min C n−1 (i, l), (2)i∈Sjn−1lwhere C n−1 (p, q) is a value of the cost volume at (n − 1)-thscale with regard to the position p and the label q, and f is a
projection function which normalizes the label space if necessary. The projection function is generally represented as aconstant scale factor giving f = s−1 . For instance, a disparity
l at the k-th scale corresponds to s−1 l at the (k − 1)-th scalein the stereo matching problem4 . The initialization method
based on the across-scale label propagation is motivated bya reasonable observation that true labels at the same image
coordinate of different scales are highly correlated, especiallythey are very close when the difference of scales is small.
While the initial estimation L̃n−2
is a good approximationjn−2of the optimal label subset Lj , the problem is that L̃jn−2
2 S 0 can be generated in various ways e.g., rectangular regular grids orjsuper-pixels [13] as shown in Sec. 3.
3 When local regions are not rectangular (e.g., superpixels with varying
shapes), we perform the edge-aware filter on the bounding-box containing
each region in the same manner with [10].
4 There are some cases where the label space does not need to be normalized since the scale of a label does not depend on the image coordinate. Some
examples are depth-map upsampling [9] and image segmentation [8].

3. RESULTS
Experiments were carried out to evaluate the performanceof proposed method using the Middlebury stereo matching
benchmark [14]. In stereo matching, the label l corresponds
to the integer disparity between a pixel i in the target image
I and the correspondence in the reference image I 0 shiftedby the disparity. The cost function is chosen in the samemanner with [4] where model parameters of α, τ1 and τ2 areset by 0.89, 0.0027, 0.0078 respectively5 . We divide eighttest image pairs in Middlebury stereo datasets [14] into two
categories with their size: small and large. The small category includes cones (450 × 375), teddy (450 × 375), tsukuba(384 × 288) and venus (434 × 383). And the large category
includes art (1390 × 1110), books (1390 × 1110), moebius(1390 × 1110) and reindeer (1342 × 1110). The label space
size L is set by 60 in the small datasets and 240 in the large
datasets. All experiments were performed on Intel Core i72600 (3.4GHz, single thread) machine with 16 GB of RAM
and were implemented in C++. Like the original work of
CVF [4], we use the guided image filter [11] to smooth thecost volume (the radius of the filter is fixed by 9).
3.1. Evaluation of Label Selection
We begin by evaluating the efficiency of our coarse-to-finestrategy comparing with CVF [4]. Here we apply our method
5 Parameters are given by authors of [4]Accumulated Time [s]does not consist of labels that are not included in f (Ln−1),
jwhich results in the aliasing artifacts when the intermediatelabels of Ln−1
should be included in Ln−2
(artifacts bej
jcome more problematic as the scale difference increases).
In addition, filtered cost volume C n−1 often contains numerical errors due to occlusion boundaries or insufficientenergy modeling. We overcome these difficulties by two
strategies. First, we downsample images with relatively large
scale factor (e.g., s ≥ 0.5), so that the scale difference between two layers becomes sufficiently small. Second, we
complete the initial label subset by adding the supportinglabels within ±1/(2s). We should note that our algorithm
supports floating labels (e.g., sub-pixel disparity values). For
instance, if the scale factor is 0.5 and the disparity unit is0.5, the initial estimation L̃n−2= {2, 5} is extended as
j
Ln−2
=
{1,
1.5,
2,
2.5,
3,
4,
4.5,
5,
5.5, 6}. Once a compactjn−2label subset Lj
has been constructed, the target layer isshifted to the higher scale (i.e., k ← n − 2). In the similarmanner with the coarsest scale, CVF is performed on Sjn−2
with regard to Ln−2
. Cost-volume filtering with respect tojk
L and the estimation of Lk−1 from C k are iterated n − 1times until L0j is acquired Then the final label at each pixelin Sj0 is selected by a simple winner-takes-all strategy in thesame manner with CVF [4].

800
600
400

Ours
CVF

200

0

1/16

1/8

1/4
1/2
Scale

1/1

Post

Fig. 2. Evaluation of the computation time. The results ofeight Middlebury stereo datasets are averaged. Post indicatesthe entire computational time after the weighted median filtering for the final disparity-map refinement.

(n = 5, s = 0.5, m = 30) and CVF [4] to both small andlarge datasets and results are averaged as shown in Fig. 2. We
observe that our coarse-to-fine strategy entirely takes muchless time than CVF [4]. As we expected, the computationaltime for small scales (e.g., 1/16, 1/8, 1/4×) is neglectably
smaller than that of the original resolution (1/1×).
However, one important question arises, “Estimated label
subsets of the original scale are really correct?” which directly addresses the accuracy of the final label selection. To
answer this question, we define two metrics for measuring thecorrectness of the final label subset as
P (j) =

|L0j ∩ Lj |,|L0j |

R(j) =|L0j ∩ Lj |
,
|Lj |

(3)

where Lj is the subset of ground truth labels at the original scale (i.e., a collection of ground truth disparity values
emerged in the j-th region) and we remind that L0j is the subset of estimated labels at the original scale. These two metrics evaluate the estimated label subset in two different aspects: P (j) ∈ [0, 1] measures the the precision of L0j which
implies how correctly unimportant labels are removed, andR(j) ∈ [0, 1] measures the recall of L0j which implies how
correctly important labels are maintained. Note that the ideal
situation of course occurs when ∀j L0j = Lj .
Using these metrics, we evaluate our method with varying scale factor s and number of layers n using only small
datasets as shown in Table 1 and Table 2. Here results areaveraged over all datasets in this category. In summary, weobserve that our algorithm successfully maintains more than
80% of ground truth labels and truncate more than 50% unnecessary labels in average while the original label subset
contains 90% of unnecessary labels. We also observe thatas expected, the improvement of the precision is generally
limited when the number of layers is too small or the scaledifferences between two layers are too large. Therefore in thefollowing experiments, we fix n by 4 and s by 0.5.

Table 1. Evaluation of the label subset estimation with fixed
lowest scale and varying scale differences.
Transition of scale
1/16→1/8→1/4→1/2→1/1(s=0.5,n=5)
1/16→1/4→1/1(s=0.25,n=3)
1/16→1/1(s=0.0625,n=2)
1/1(CVF[4])Ave.
Precision
0.58
0.48
0.23
0.13

Ave.
Recall
0.89
0.89
0.93
1.00

Table 2. Evaluation of the label subset estimation with fixedscale difference and varying number of layers.
Transition of scale

1/16→1/8→1/4→1/2→1/1(s=0.5,n=5)
1/8→1/4→1/2→1/1(s=0.5,n=4)
1/4→1/2→1/1(s=0.5,n=3)
1/2→1/1(s=0.5,n=2)
1/1(CVF[4])Ave.
Precision
0.58
0.58
0.57
0.49
0.13

Ave.
Recall
0.89
0.91
0.90
0.92
1.00

3.2. Comparison with PatchMatch Filter
Here we evaluate the performance of our method by a numerical comparison with PatchMatch filter (PMF) [10] using
both small and large datasets in Middlebury stereo benchmark [14]. For a fair comparison, our method and PMF are
performed with same superpixels clustered by SLIC [13],the cost function, and the post-processing based on left-rightcross-checking and median-filtering (see details in [4])6 . We
also evaluate the performance of our method based on the regular image grid with varying block size. Note that the numberof local regions is in inverse proportion to the block size.
The results are displayed in Table 3 and Table 4. Here thepercentage disparity errors (threshold is set by one for small,and one and four for large) are averaged over all images withthe same category. We observe that while the accuracy of our
method, PMF [10] and CVF [4] are almost same, our method
is most efficient method of all for both categories. Especiallyas for large datasets, our method achieves 6× faster performance than CVF [4] while keeping (or even better) accuracy.
We also observe that our method works when the number of
local regions is large (e.g., superpixels with K = 200, 500)
or when the image is divided into local regions as a simple
image grid. That is because unlike PMF [10], we do notconsider any spatial smoothness of label subsets within thescale, rather consider the cross-scale smoothness of the local
label subset which is independent of the spatial coherence.
Finally, we illustrate the estimated disparity maps of
Teddy dataset in Fig. 3. We observe that our method succceeds in estimating smoother and more reasonable disparity
maps than CVF and PMF in this condition.
6 Post-processing is performed on our method only in the original resolution.

Table 3. Comparison with PMF using small datasets.
Time[s]

MethodCVF[4]
PMF[10] (K=50)
PMF[10] (K=100)
PMF[10] (K=200)
PMF[10] (K=500)
Ours (Superpixels, K=50)
Ours (Superpixels, K=100)
Ours (Superpixels, K=200)
Ours (Superpixels, K=500)
Ours (Grid, 150x150)
Ours (Grid, 75x75)

35.38
23.43
28.97
43.14
73.21
15.98
16.56
18.48
23.55
17.67
12.47

Err. %: thre. = 1.0
nonocc
all
disc
3.30
6.17
9.74
3.19
5.97
9.56
3.23
6.03
9.32
3.27
6.04
9.36
3.30
6.08
9.31
3.51
6.31
10.8
3.46
6.23
10.7
3.69
6.48
11.3
4.15
7.03
12.2
3.11
5.98
10.1
3.22
6.02
10.4

Table 4. Comparison with PMF using large datasets.
Time[s]
MethodCVF[4]
PMF[10] (K=50)
PMF[10] (K=100)
PMF[10] (K=200)
PMF[10] (K=500)
Ours (Superpixels, K=50)
Ours (Superpixels, K=100)
Ours (Superpixels, K=200)
Ours (Superpixels, K=500)
Ours (Grid, 600x600)
Ours (Grid, 300x300)
Ours (Grid, 150x150)
Ours (Grid, 75x75)

Ours (Grid, 150×150)

1413
266
322
484
802
269
249
262
304
1186
796
371
246

Err. % (all)
Err.
Err.
thre.=1 thre.=4
21.5
14.8
22.7
15.6
22.5
15.5
22.5
15.6
23.3
16.2
22.5
15.3
23.0
15.7
23.6
16.0
24.5
17.2
21.1
14.4
20.5
13.4
21.6
14.4
25.2
17.6

Ours (Grid,
150×150)

CVF

Ground Truth

PMF(Superpixels,
K=500)

Fig. 3. Qualitative comparison with regard to estimated disparity maps of Teddy dataset.

4. CONCLUSION
In this paper, we have proposed a coarse-to-fine strategy to
reduce the large label space for the efficient cost volume filtering. Our proposed method has demonstrated the highest
efficiency, while keeping the accuracy in stereo matching. In
future work, we will apply our method to other applicationsof discrete labeling problems which is hard to solve for theoriginal cost volume filtering because of the huge label space.

5. REFERENCES[1] Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Trans.
PAMI, vol. 23, no. 11, pp. 1222–1239, 2001.
[2] J. Sun, H.-Y. Shun, and N.-N. Zheng, “Stereo matching
using belief propagation,” in ECCV, 2002.
[3] M. F. Tappen and W. T. Freeman, “Comparison of graphcuts with belief propagation for stereo, using identical
mrf parameters,” in Proc. of ICCV, 2003.
[4] C. Rhemann, A. Hosni, M. Bleyer, C. Rother, and
M. Gelautz, “Fast cost-volume filtering for visual correspondence and beyond,” in CVPR, 2011.
[5] Q. Yang, “A non-local cost aggregation method forstereo matching,” in CVPR, 2012.
[6] A. Hosni, C. Rhemann, M. Bleyer, and M. Gelautz,“Temporally consistent disparity and optical flow via
efficient spatio-temporal filtering,” in Advances in Image and Video Technology, pp. 165–177. Springer Berlin
Heidelberg, 2012.
[7] A. Brunton, J. Lang, and E. Dubois, “Efficient multiscale stereo of high-resolution planar and spherical images,” in 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT), 2012 Second International Conference on. IEEE, 2012.
[8] V. Kramarev, O. Demetz, C. Schroers, and J. Weickert,“Cross anisotropic cost volume filtering for segmentation,” in Computer Vision-ACCV 2012, pp. 803–814.
Springer Berlin Heidelberg, 2013.
[9] J. Cho, S. Ikehata, H. Yoo, M. Gelautz, and K. Aizawa,“Depth map up-sampling using cost-volume filtering,”
in Proc. of IVMSP Workshop, 2013.
[10] J. Lu, H. Yang, and N. D. Min, D. Minh, “PatchMatchfilter: Efficient edge-aware filtering meets randomized
search for fast correspondence field estimation,” in
CVPR, 2013.
[11] K. He, J. Sun, and X. Tang, “Guided image filtering,” in
ECCV, 2010.
[12] J. Lu, K. Shi, D. Min, L. Lin, and M. N. Do, “Crossbased local multipoint filtering,” in CVPR, 2012.
[13] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and
S. Süsstrunk, “SLIC superpixels compared to state-ofthe-art superpixel methods,” IEEE Trans. PAMI, vol. 34,
no. 11, pp. 2274–2281, 2012.
[14] “Middlebury stereo database,” http://vision.
middlebury.edu/stereo/.

[15] C. Barnes, E. Shechtman, A. Finkelstein, and D. B.
Goldman, “PatchMatch: A randomized correpondence
algorithm for structual image editing,” in Proc. of ACM
SIGGRAGH, 2009.