Supplementary Material: Deep Discrete Flow
Fatma Güney1 and Andreas Geiger1,2
1Autonomous Vision Group, MPI for Intelligent Systems, Tübingen
2
Computer Vision and Geometry Group, ETH ZürichAbstract. In this supplementary document, we first present additional experiments to show the convergence of training in Section 1.1and compare the performance of exact matching against a frequently
used approximate nearest neighbour search library in Section 1.2. We
then show the speed-ups we gain by the strided implementation of thepatch-based dilated convolutions in Section 2.1. We compare the runtime of forward propagating a full resolution image pair for the different
local and context architectures in Section 2.2 and then report the runtime for individual stages of our pipeline compared to Discrete Flow inSection 2.3. For reproducibility, we list the parameter settings of the different stages in Section 3. Finally, we show additional qualitative resultson the MPI Sintel and KITTI validation sets in Section 4.

1

Additional Experiments

1.1

Convergence(a) Local Network(b) Context NetworkFig. 1: Outlier ratio in non-occluded regions over training iterations.
This figure shows the average outlier ratio in non-occluded regions over thetraining iterations on KITTI.

In Fig. 1, we plot the average outlier ratio in non-occluded regions over thetraining iterations for both local and context networks on the KITTI training
and validation sets. As concluded in the main paper, we also note that training
the context network on top of the local network decreases outlier ratios significantly. Importantly, the training and validation curves behave similarly for bothnetworks, indicating that our Siamese architectures don’t suffer from overfitting.
In both plots, one iteration corresponds to one hundred thousand batch updates.

2Fatma Güney and Andreas Geiger

1.2Approximate vs. Exact Matching

Formulating optical flow as an approximate nearest neighbour (ANN) searchon the target image is a common way of dealing with the size of the search
space [1–3]. In this section, we show that exact matching can be done as efficiently
utilizing the GPU and show improved results compared to ANN.
We can perform exact matching for grid points on the reference image efficiently as matrix-matrix multiplication on the GPU. However, there are stillsome restrictions due to the limited memory which prevent performing the entire
computation at once. We show our experiments by dividing the set of grid point
into chunks and changing the number of chunks to find a compensation between
memory usage and run-time for different number of matches per grid point inTable 1.
Number of Chunks Memory Run-time
9
6.63
8.42
3.89
8.34
1845
2.25
3.03
1.71
3.58
90
180
1.43
4.52
306
1.32
6.94

Number of Chunks Memory Run-time
9
6.70
5.58
3.94
5.74
18452.296.53
1.74
6.94
90
180
1.46
7.36
306
1.35
8.42(a) Number of Matches = 1(b) Number of Matches = 1024

Table 1: Exact Matching. This table compares different number of chunks
used to compute the exact matching in terms of memory and run-time for two
different number of matches, 1 as in WTA and 1024 as used in BP.
For comparison, we use the popular FLANN library [4] (which has also beenused in [3]) to perform approximate nearest neighbor matching. We found that
the FLANN parameter “number of checks” which specifies the maximum numberof leafs to visit when searching for neighbors has a clear effect on the performance. Therefore, we vary the number of checks in Table 2, fixing the number ofsearch trees to 8. For both datasets, only using 1024 checks yields performancecomparable to exact matching. We also note that run-time for FLANN is muchhigher, 45 to 60 seconds depending on the number of checks, when using full
resolution images and a large number of feature maps, 256 as in case of context
architecture 12.
Matching Number of Checks Out-Noc
3230.25%FLANN
12821.21 %
1024
14.56 %
Exact
12.19 %

Matching Number of Checks Out-Noc
32
56.09%
FLANN
128
41.09 %
1024
26.19 %
Exact
20.28 %(a) MPI Sintel(b) KITTI

Table 2: Comparison to FLANN. This table compares the performance ofexact matching to approximate matching using the FLANN library [4], varying
the number of checks which specify the maximum number of leafs to visit.

Supplementary Material: Deep Discrete Flow2

Run-time Analysis

2.1

Run-time of Patch-Based Dilated Convolutional Networks

Naı̈veProposedContext Arch.
1
543.37 ms 15.17 ms
2
146.69 ms 4.80 ms358.37 ms 2.23 ms
4360.41 ms 6.40 ms
5195.22 ms 3.60 ms
663.47 ms 2.27 ms
7170.60 ms 7.30 ms
8646.11 ms 38.77 ms
91384.48 ms 11.00 ms

3Context Arch.
Naı̈veProposed
11823.37 ms 42.46 ms
12184.88 ms 9.28 ms
1369.17 ms 2.79 ms
14417.39 ms 11.42 ms
15207.55 ms 4.21 ms
1695.34 ms 4.41 ms
17201.37 ms 9.39 ms
18867.846 ms 55.78 ms
192335.74 ms 26.96 ms

Table 3: Patch-based Dilated Convolutions. This table compares the runtime of one batch update in milliseconds for the naı̈ve and the proposed implementations using different context architectures with dilated convolutions.

As mentioned in Section 3.1 of the paper, a naı̈ve implementation of patch
based dilated convolutions is computationally very inefficient. In Table 3, weshow the speed-ups we gain by the proposed strided convolution implementation. We measure the average run-time of forward and backward propagation ofa batch of 128 patch pairs followed by normalization and similarity score computation. As evidenced by our experiments, the proposed implementation leads torun-time gains up to two orders of magnitude compared to the naı̈ve implementation. In other words, using the naı̈ve implementation would require 200 days
for training a model which we train in 2 days using the proposed implementation
for some architectures.
2.2

Run-time Comparison of Different Architectures

In Table 4, we compare the run-time of different local and context architectures
for one forward pass of two full-resolution images. For context, we only report
the additional time after the local architecture 1. Note that this number wouldbe different depending on the number of feature maps in the last layer of thelocal architecture. Using the context architecture 12 on top of local architecture
1, run-time is approximately 2 seconds in total.
2.3

Run-time of Full Deep Discrete Flow Model

In Section 2.2, we compared the run-time of different architectures. In this section, we fix the local and context architectures to 1 and 12, respectively, andperform a run-time analysis of the following stages in our pipeline. In Table 5,
we list the run-time for different parts of the discrete inference together with4

Fatma Güney and Andreas Geiger

Local Arch. Run-time
11.27
2
1.89
3
2.08
42.52
52.62

Context Arch. Run-time
11.06
20.76
30.45
40.76
50.46
60.45
7
1.06
8
1.67
91.06

Context Arch. Run-time
11
1.63
120.87130.46
140.8815
0.46
160.51
17
1.13
18
2.10
19
1.46

Table 4: Run-time (in sec) of Different Local and Context Architectures
This table compares the run-time of forward propagating two full-resolution
Sintel images using different architectures.
the post-processing and the interpolation. Since these measurements are image
dependent, we take the average run-time per stage over a set of images in thevalidation set of each dataset.
We pre-compute pairwise term using parallelism and hashing as in [3], and use
an efficient implementation of Belief Propagation (BP) based on parallel checkerboard update scheme. The parallel BP has a comparable run-time to the Block
Coordinate Descent used in [3] which takes 20 to 25 seconds in total for inference
including the pairwise computation. As shown in Table 5, the slowest part isrefining the data term using non-maxima suppression and adding proposals fromthe neighbouring pixels. The post-processing and interpolation run-times arenegligible compared to the discrete inference.
Refining Pre-computing
BeliefPost-processing Interpolation
Data Term
Pairwise
Propagation
MPI Sintel
49.97
10.13
5.24
2.20
0.002
KITTI
35.42
14.17
10.54
1.66

Table 5: Run-time (in sec) Analysis of Individual Stages This table lists
the run-time for different parts of the discrete inference as average over a set ofvalidation images.

3Parameter Settings

In this section, we provide the details of the parameter settings used to produce
the results in the paper. Specifically, we list the parameters used in the feature
matching baseline, discrete optimization, and the post-processing.
Table 6 lists the parameters of the Daisy feature descriptor used as baseline
in Section 4.1 in the paper. The first column corresponds to the parameters usedin Discrete Flow [3] and the second column to the optimized parameters on MPI
Sintel.
Table 7 shows the parameters of the discrete optimization and the postprocessing. We optimized over these parameters using BCD on the validationSupplementary Material: Deep Discrete Flow

5ParameterDF [3] OptimizedRadius
510
Radius Quantization No.
44
Angular Quantization No.
48Histogram Quantization No. 48Normalization Type
22Table 6: Feature Matching Baseline Parameters. Here, we show the valuesof the parameters from Discrete Flow [3] and optimized for the feature matchingbaseline used in the paper.
sets as defined in the paper, to minimize EPE in case of MPI Sintel and theaverage outlier ratio in case of KITTI as evaluated by the benchmarks. We
empirically also tested larger values for the size of the label set by keeping
the ratio of number of proposals from neighbors fixed, but did not observe asignificant change in the performance, therefore we fixed the size of the label set
to 300 during the optimization. In addition, we kept the NMS radius and thestride fixed. We observed that more iterations or a larger truncation threshold of
the pairwise term give slightly better results, but at the cost of higher run-time.
For interpolation, we used the default values as defined in Epic Flow for eachdataset.
ValueParameter
Number of Initial Matches
1024
Size of the Label Set
300
210
Proposals from Neighbours
NMS Radius in Pixels
2Stride for Discrete CRF in Pixels
4-0.25
Truncation Threshold of the Data Term
Truncation Threshold of the Pairwise Term 15
0.009
Relative Weight of Pairwise Term
Number of Iterations
10(a) Discrete Optimization Parameters
Parameter
MPI Sintel KITTI
Similarity Threshold (fw-/bw-check)
7.63
2.83
Minimum Segment Size (outlier removal)
100
277.45
Consistency Threshold (outlier removal)
513.01
Epic Flowdataset(b) Post-processing ParametersTable 7: Model Parameters. Here, we list the parameter settings used fordiscrete optimization in (a), and for post-processing and interpolation in (b).

64Fatma Güney and Andreas Geiger

Additional Qualitative Results

In this section, we show additional qualitative results which we randomly
picked from the MPI Sintel and the KITTI validation sets. For each case, weshow the input image, ground-truth flow in the first row, results for Discrete
Flow with Daisy Proposals in the second row, local network in the third row,and the context network in the last row. The first double column shows the flow
result and corresponding error image for the WTA solution, the second double
column shows the results after discrete optimization and the last double column
shows the final results after post-processing and interpolation.

Fig. 2: Qualitiative Results. See text for details.

Supplementary Material: Deep Discrete Flow

Fig. 3: Qualitiative Results. See text for details.

7

8

Fatma Güney and Andreas Geiger

Fig. 4: Qualitiative Results. See text for details.

Supplementary Material: Deep Discrete Flow

Fig. 5: Qualitiative Results. See text for details.

910Fatma Güney and Andreas Geiger

Fig. 6: Qualitiative Results. See text for details.

Supplementary Material: Deep Discrete Flow

11References
1. Bao, L., Yang, Q., Jin, H.: Fast edge-preserving PatchMatch for large displacement
optical flow. In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition(CVPR). (2014)
2. Besse, F., Rother, C., Fitzgibbon, A., Kautz, J.: PMBP: PatchMatch Belief Propagation for correspondence field estimation. International Journal of Computer
Vision (IJCV) 110 (2014) 2–13
3. Menze, M., Heipke, C., Geiger, A.: Discrete optimization for optical flow. In: Proc.
of the German Conference on Pattern Recognition (GCPR). (2015)
4. Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional
data. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI) 36 (2014)
2227–2240