Discrete Optimization for Optical Flow
Moritz Menze1

Christian Heipke1

Andreas Geiger2

1 Institute of Photogrammetry and GeoInformation

Leibniz Universität Hannover
2 Max Planck Institute for Intelligent Systems

Tübingen

7. October, 2015

1 / 24

Where is Sintel going?

2 / 24

Where is Sintel going?

2 / 24

Related Work - Variational Methods[Brox et al., ECCV 2004], [Sun et al., IJCV 2013]3 / 24

Related Work - Sparse Features[Brox et al., PAMI 2011][Revaud et al., CVPR 2015]
4 / 24

Related Work - Stereo Matching
KITTI Stereo Leaderboard

I Naı̈ve discretization of 2D flow space intractable
I 3 strategies enable discrete optimization for optical flow

5 / 24

Related Work - Discrete Optimization[Lempitzky et al., CVPR 2008][Mozerov, TIP 2013]6 / 24

Discrete Optical Flow

Optical flow as labeling task

E (l) =Xp∈PX
ψp,q (lp , lq )ϕp (lp ) +| {z } p∼q | {z }datasmoothness

I p, q: pixels
I l: discrete flow label

7 / 24

Discrete Optical Flow

I Robust data term based on DAISY descriptors d
ϕp (lp ) = min kdp − d0p (lp )k1 , τϕ

I Similar flow vectors f are encouraged byψp,q (lp , lq ) = wp,q · min kfp (lp ) − fq (lq )k1 , τψweighted by the edge strength [Dollár et al., ICCV 2013]:
wp,q = exp −α κ2p,q8 / 24

Strategies

Three strategies for efficient inference:

Diverse Flow Proposals

Truncated Penalty

BCD Optimization

v
142u

3

9 / 24

1. Diverse Flow Proposals
I Efficient search structure
I 300 nearest neighbors
I 200 proposals from neighboring pixels

I Reduction of proposals form 250.000 to 500 per pixel
10 / 24

2. Block Coordinate Descent
I Inference via Block Coordinate Descent (BCD)1142

3

I Alternating optimization of image rows and columns
I Sub-problems solved optimally via dynamic programming

1

Chen and Koltun, CVPR 201411 / 24

3. Truncated Pairwise Potential
I Evaluation of only a few combinationsvu

12 / 24

3. Truncated Pairwise Potential
Naı̈ve Dynamic Programming:C(x, l) = ϕ(x,y ) (l)13 / 24

3. Truncated Pairwise Potential
Naı̈ve Dynamic Programming:C(x, l) = ϕ(x,y ) (l)∗+ ψ(x,y ),(x,y −1) (l, lx,y−1 )∗+ ψ(x,y ),(x,y +1) (l, lx,y+1 )13 / 24

3. Truncated Pairwise Potential
Naı̈ve Dynamic Programming:C(x, l) = ϕ(x,y ) (l)∗+ ψ(x,y ),(x,y −1) (l, lx,y−1 )∗+ ψ(x,y ),(x,y +1) (l, lx,y+1 )

+ min

0≤k<L


ψ(x,y ),(x−1,y ) (l, k) + C(x − 1, k)

13 / 24

3. Truncated Pairwise Potential
Naı̈ve Dynamic Programming:|L|C(x, l) = ϕ(x,y ) (l)∗+ ψ(x,y ),(x,y −1) (l, lx,y−1 )∗+ ψ(x,y ),(x,y +1) (l, lx,y+1 )

+ min

0≤k<L


ψ(x,y ),(x−1,y ) (l, k) + C(x − 1, k)

13 / 24

3. Truncated Pairwise Potential
Efficient Dynamic Programming:|L|

C(x, l) = ϕ(x,y ) (l)∗+ ψ(x,y ),(x,y −1) (l, lx,y−1 )∗+ ψ(x,y ),(x,y +1) (l, lx,y+1 )14 / 24

3. Truncated Pairwise Potential
Efficient Dynamic Programming:| |C(x, l) = ϕ(x,y ) (l)∗+ ψ(x,y ),(x,y −1) (l, lx,y−1 )∗+ ψ(x,y ),(x,y +1) (l, lx,y+1 )+ minmink∈K(x,y ),(x−1,y ),l
ψ(x,y ),(x−1,y ) (l, k) + C(x − 1, k) , c



14 / 24

3. Truncated Pairwise Potentialv

Efficient Dynamic Programming:u

C(x, l) = ϕ(x,y ) (l)∗+ ψ(x,y ),(x,y −1) (l, lx,y−1 )∗+ ψ(x,y ),(x,y +1) (l, lx,y+1 )+ minmink∈K(x,y ),(x−1,y ),lwith:c = min
ψ(x,y ),(x−1,y ) (l, k) + C(x − 1, k) , c0≤k<L
w(x,y ),(x−1,y ) τϕ + C(x − 1, k)

14 / 24

Post-Processing
I Inference yields integral flow

15 / 24

Post-Processing
I Inference yields integral flow
I Forward-backward consistency check

15 / 24

Post-Processing
I Inference yields integral flow
I Forward-backward consistency check
I Interpolation & subpixel refinement
I

Epicflow [Revaud, CVPR 2015]15 / 24

Quantitative Evaluation - MPI Sintel

All
Flow Fields [Bailer et al., ICCV 2015]
5.810
6.077
Ours+EpicFlow
DM+EpicFlow [Revaud et al., CVPR 2015]
6.285
TF+OFM [Kennedy et al., EMMCVPR 2015] 6.727
Deep+R [Drayer et al., BMVC 2015]
6.769

EPE (px)Noc
Occ
2.621 31.799
2.937 31.685
3.060 32.564
3.388 33.929
2.996 37.494

MPI Sintel final (48 methods listed online)

16 / 24Quantitative Evaluation - MPI Sintel

All
Ours+EpicFlow
3.567
3.748
FlowFields [Bailer et al., ICCV 2015]
DM+EpicFlow [Revaud et al., CVPR 2015] 4.115
PH-Flow [Yang et al., CVPR 2015]
4.388
AggregFlow [Fortun et al., ARXIV 2014]
4.754

EPE (px)Noc
Occ
1.108 23.626
1.056 25.700
1.360 26.595
1.714 26.202
1.694 29.685

MPI Sintel clean (48 methods listed online)

17 / 24

Qualitative Results - MPI Sintel

18 / 24

Qualitative Results - MPI Sintel

19 / 24

Qualitative Results - MPI Sintel

20 / 24

Quantitative Evaluation - KITTI
Outliers (%) EPE (px)Noc
All
Noc All
PH-Flow [Yang et al., CVPR 2015]5.76 10.57 1.3 2.9
FlowFields [Bailer et al., ICCV 2015]
5.77 14.01 1.4 3.5
5.93 11.96 1.6 3.8
NLTGV-SC [Ranftl et al., ECCV 2014]
DDS-DF [Wei et al., 3DV 2014]6.03 13.08 1.6 4.2
TGV2ADCSIFT [Braux-Zin et al., ICCV 2013] 6.20 15.15 1.5 4.5
Ours+EpicFlow
6.23 16.63 1.3 3.6
AnyFlow [Submitted to PAMI]
6.37 15.80 1.5 4.3
BTF-ILLUM [Demetz et al., ECCV 2014]6.52 11.03 1.5 2.8
CRT-TGV [Submitted to IJCV]
6.71 12.09 2.0 3.9
..
..
..
..
..
.
.
.
.
.
7.88 17.08 1.5 3.8
DM+EpicFlow [Revaud et al., CVPR 2015]

KITTI 3 px (69 methods listed online)

21 / 24

Quantitative Evaluation - KITTIOutliers (%) EPE (px)Noc
All
Noc AllOurs+EpicFlow
3.89 12.46 1.3 3.6
PH-Flow [Yang et al., CVPR 2015]
3.93 7.72 1.3 2.9
3.95 10.21 1.4 3.5
FlowFields [Bailer et al., ICCV 2015]
DDS-DF [Wei et al., 3DV 2014]4.41 10.41 1.6 4.2
NLTGV-SC [Ranftl et al., ECCV 2014]4.50 9.42
1.6 3.8
AnyFlow [Submitted to PAMI]
4.51 12.55 1.5 4.3TGV2ADCSIFT [Braux-Zin et al., ICCV 2013] 4.60 12.17 1.5 4.5
BTF-ILLUM [Demetz et al., ECCV 2014]
4.64 8.11
1.5 2.8
CRT-TGV [Submitted to IJCV]
5.01 8.97
2.0 3.9
..
..
..
..
..
.
.
.
.
.
5.36 12.86 1.5 3.8
DM+EpicFlow [Revaud et al., CVPR 2015]

KITTI 5 px (69 methods listed online)

22 / 24

Conclusions
I Three strategies to reduce computational complexity
I Enable discrete optimization for optical flow
I State-of-the-art performance with sub-pixel refinement

Outlook
I Integrate multiple frames
I Reason about multiple scales
I Include semantic knowledge

23 / 24

Discrete Optimization for Optical Flow

Thank you!

Project page:www.cvlibs.net/projects/discrete flow
24 / 24

Runtimes

Percentage Runtime:
40%

35%

Diverse Flow Proposals

Truncated Penalty

BCD Optimization

v
14

2u3

(remaining 25% for descriptor extraction and post-processing)
I Total runtime ∼3 minutes

1/4

Qualitative Results - KITTI

2/4

Qualitative Results - KITTI

3/4

Qualitative Results - KITTI

4/4