Taking a Deeper Look at the Inverse Compositional Algorithm
Andreas Geiger
Autonomous Vision Group
University of Tübingen / MPI for Intelligent Systems

June 17, 2018

University of Tübingen
MPI for Intelligent Systems
Autonomous Vision GroupMaking Robust Image Alignment even more Robust
Andreas Geiger
Autonomous Vision Group
University of Tübingen / MPI for Intelligent Systems

June 17, 2018

University of Tübingen
MPI for Intelligent Systems
Autonomous Vision GroupMaking Robust Image Alignment even more Robust
but certainly not more Uncertain
Andreas Geiger
Autonomous Vision Group
University of Tübingen / MPI for Intelligent Systems

June 17, 2018

University of Tübingen
MPI for Intelligent Systems
Autonomous Vision GroupMaking Robust Image Alignment even more Robust
but certainly not more Uncertain
Andreas Geiger
Autonomous Vision Group
University of Tübingen / MPI for Intelligent Systems

June 17, 2018

University of Tübingen
MPI for Intelligent Systems
Autonomous Vision GroupTaking a Deeper Look at theInverse Compositional Algorithm[Lv, Dellaert, Rehg & Geiger, CVPR 2019]

A Seminal Paper

A Seminal Paper

Lucas and Kanade: An Iterative Image Registration Technique with an Application to Stereo Vision. IJCAI, 1981.

7

Applications of Image Registration

Feature Tracking and Optical Flow

SLAM

Panoramic Image Stitching
Lucas and Kanade: An Iterative Image Registration Technique with an Application to Stereo Vision. IJCAI, 1981.

8

Lucas-Kanade Algorithm

Objective: Minimize photometric error between template T and image I
min kI(ξ) − T(0)k22
ξ

I I(ξ): image I transformed by warp parameters ξ
I T(0): template
I Note: This is a non-linear objective

Lucas and Kanade: An Iterative Image Registration Technique with an Application to Stereo Vision. IJCAI, 1981.

9

Lucas-Kanade Algorithm
I Iteratively solve the task
ξ k+1 = ξ k ◦ ∆ξLucas and Kanade: An Iterative Image Registration Technique with an Application to Stereo Vision. IJCAI, 1981.

10

Lucas-Kanade Algorithm
I Iteratively solve the task
ξ k+1 = ξ k ◦ ∆ξI The warp increment ∆ξ is obtained by linearizing the objective
min kI(ξ k + ∆ξ) − T(0)k22∆ξusing ﬁrst-order Taylor expansion:∂I(ξ k )∆ξ − T(0)min I(ξ k ) +∆ξ∂ξLucas and Kanade: An Iterative Image Registration Technique with an Application to Stereo Vision. IJCAI, 1981.

2

2

10

Lucas-Kanade Algorithm
I Iteratively solve the task
ξ k+1 = ξ k ◦ ∆ξI The warp increment ∆ξ is obtained by linearizing the objective
min kI(ξ k + ∆ξ) − T(0)k22∆ξusing ﬁrst-order Taylor expansion:∂I(ξ k )∆ξ − T(0)min I(ξ k ) +
∆ξ
∂ξ

2

2

I ∂I(ξ k )/∂ξ must be recomputed at every iteration k
Lucas and Kanade: An Iterative Image Registration Technique with an Application to Stereo Vision. IJCAI, 1981.

10Inverse Compositional Algorithm
I Iteratively solve the task
ξ k+1 = ξ k ◦ (∆ξ)−1

Baker and Matthews: Lucas-Kanade 20 Years On: A Unifying Framework: Part 1. Technical Report, Carnegie Mellon University, 2003.

11

Inverse Compositional Algorithm
I Iteratively solve the task
ξ k+1 = ξ k ◦ (∆ξ)−1
I The warp increment ∆ξ is obtained by linearizing the objective
min kI(ξ k ) − T(∆ξ)k22∆ξusing ﬁrst-order Taylor expansion:∂T(0)∆ξmin I(ξ k ) − T(0) −
∆ξ
∂ξ

2

2

Baker and Matthews: Lucas-Kanade 20 Years On: A Unifying Framework: Part 1. Technical Report, Carnegie Mellon University, 2003.

11

Inverse Compositional Algorithm
I Iteratively solve the task
ξ k+1 = ξ k ◦ (∆ξ)−1
I The warp increment ∆ξ is obtained by linearizing the objective
min kI(ξ k ) − T(∆ξ)k22∆ξusing ﬁrst-order Taylor expansion:∂T(0)∆ξmin I(ξ k ) − T(0) −
∆ξ
∂ξ

2

2

I ∂T(0)/∂ξ does not depend on ξ k and can thus be pre-computed
Baker and Matthews: Lucas-Kanade 20 Years On: A Unifying Framework: Part 1. Technical Report, Carnegie Mellon University, 2003.

11

Comparison
Lucas-Kanade Algorithm

Inverse Compositional Algorithmξ k+1 = ξ k ◦ ∆ξ

ξ k+1 = ξ k ◦ (∆ξ)−1

min kI(ξ k + ∆ξ) − T(0)k22

min kI(ξ k ) − T(∆ξ)k22∆ξ∂I(ξ k )∆ξ − T(0)min I(ξ k ) +
∆ξ
∂ξ

∆ξ

2

2

∂T(0)
∆ξ
min I(ξ k ) − T(0) −
∆ξ
∂ξ

2

2

I The Inverse Compositional Algorithm is more computationally efﬁcient!

Baker and Matthews: Lucas-Kanade 20 Years On: A Unifying Framework: Part 1. Technical Report, Carnegie Mellon University, 2003.

12

Robust M-Estimation

I To handle outliers, robust estimation can be used:
min rk (∆ξ)T W rk (∆ξ)∆ξ

rk (∆ξ) = I(ξ k ) − T(∆ξ)

I The diagonal weight matrix W is determined by the implicit robust loss ρ(·)

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

13

Optimization
I The minimizer of rk (∆ξ)T W rk (∆ξ) leads to the Gauss-Newton update:∆ξ = (JT WJ)−1 T

J W rk (0)with Jacobian J = ∂T(0)/∂ξ

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

14

Optimization
I The minimizer of rk (∆ξ)T W rk (∆ξ) leads to the Gauss-Newton update:∆ξ = (JT WJ)−1 T

J W rk (0)with Jacobian J = ∂T(0)/∂ξ
I As the approximate Hessian JT WJ easily becomes ill-conditioned,
a damping term is added in practice, resulting in a trust-region update:−1 T∆ξ = (JT WJ + λ diag(JT WJ))J W rk (0)Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

14

Optimization
I The minimizer of rk (∆ξ)T W rk (∆ξ) leads to the Gauss-Newton update:∆ξ = (JT WJ)−1 T

J W rk (0)with Jacobian J = ∂T(0)/∂ξ
I As the approximate Hessian JT WJ easily becomes ill-conditioned,
a damping term is added in practice, resulting in a trust-region update:−1 T∆ξ = (JT WJ + λ diag(JT WJ))J W rk (0)I For different λ, the update varies between the Gauss-Newton direction andsteepest descent. In practice, λ is chosen based on simple heuristics.
Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

14

Robust Inverse Compositional Algorithm

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

15

What is the problem?
Limitations:
I Easily gets trapped in local minima as residuals often highly non-linear

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

16

What is the problem?
Limitations:
I Easily gets trapped in local minima as residuals often highly non-linear
I Choosing a robust loss function ρ is difﬁcult as residual distribution unknown

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

16

What is the problem?
Limitations:
I Easily gets trapped in local minima as residuals often highly non-linear
I Choosing a robust loss function ρ is difﬁcult as residual distribution unknown
I The objective does not capture high-order statistics of the inputs (W is diagonal)

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

16

What is the problem?
Limitations:
I Easily gets trapped in local minima as residuals often highly non-linear
I Choosing a robust loss function ρ is difﬁcult as residual distribution unknown
I The objective does not capture high-order statistics of the inputs (W is diagonal)
I Damping heuristics are suboptimal and do not depend on the input

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

16

What is the problem?
Limitations:
I Easily gets trapped in local minima as residuals often highly non-linear
I Choosing a robust loss function ρ is difﬁcult as residual distribution unknown
I The objective does not capture high-order statistics of the inputs (W is diagonal)
I Damping heuristics are suboptimal and do not depend on the input
Our Approach
I Unroll the algorithm into a parameterized feed-forward network

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

16

What is the problem?
Limitations:
I Easily gets trapped in local minima as residuals often highly non-linear
I Choosing a robust loss function ρ is difﬁcult as residual distribution unknown
I The objective does not capture high-order statistics of the inputs (W is diagonal)
I Damping heuristics are suboptimal and do not depend on the input
Our Approach
I Unroll the algorithm into a parameterized feed-forward network
I Relax assumptions above but preserves advantages of robust estimation

Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

16

What is the problem?
Limitations:
I Easily gets trapped in local minima as residuals often highly non-linear
I Choosing a robust loss function ρ is difﬁcult as residual distribution unknown
I The objective does not capture high-order statistics of the inputs (W is diagonal)
I Damping heuristics are suboptimal and do not depend on the input
Our Approach
I Unroll the algorithm into a parameterized feed-forward network
I Relax assumptions above but preserves advantages of robust estimation
I Trained end-to-end from data
Baker, Gross, Matthews and Ishikawa: Lucas-Kanade 20 Years On: A Unifying Framework: Part 2. Technical Report, Carnegie Mellon University, 2003.

16

ApproachRobust Inverse Compositional Algorithm

18

Robust Inverse Compositional Algorithm

I Two-view feature encoder

Convolutional m-estimator

Trust-region network18

Two-View Feature Encoder

I ConvNet φθ for extracting:
I Image features Iθ = φθ ([I, T])
I Template features Tθ = φθ ([T, I])

19

Two-View Feature Encoder

I ConvNet φθ for extracting:
I Image features Iθ = φθ ([I, T])
I Template features Tθ = φθ ([T, I])

I Both views passed as input
I Features capture high-order spatial and temporal information
19

Convolutional M-Estimator

I Robust weight function parameterized by ConvNet ψθ
I Input: feature maps I, T and residual r
I Output: diagonal weight matrix Wθ = ψθ (I, T, r)

20

Convolutional M-Estimator

I Robust weight function parameterized by ConvNet ψθ
I Input: feature maps I, T and residual r
I Output: diagonal weight matrix Wθ = ψθ (I, T, r)

I Robust function is learned end-to-end from data
I Robust function conditioned on input image/template and pixel context
20Trust Region Network

I Compute hypothetical updates for a set of damping proposals:−1 T∆ξ i = (JT WJ + λi diag(JT WJ))J W rk (0)21Trust Region Network

I Compute hypothetical updates for a set of damping proposals:−1 T∆ξ i = (JT WJ + λi diag(JT WJ))J W rk (0)I Pass resulting residuals to a neural net which predicts damping parameters:

h
i
(1)
(N )
λθ = νθ JT WJ, JT Wrk+1 , . . . , JT Wrk+1

21

Trust Region Network

I Compute hypothetical updates for a set of damping proposals:−1 T∆ξ i = (JT WJ + λi diag(JT WJ))J W rk (0)I Pass resulting residuals to a neural net which predicts damping parameters:

h
i
(1)
(N )
λθ = νθ JT WJ, JT Wrk+1 , . . . , JT Wrk+1
I Our experiments show that residual maps indeed contain valuable information
21

Overview22Overview22

Experimental Evaluation

RGB-D Image Alignment

The rigid body transformation Tξ warps pixel x asWξ (x) = K Tξ D(x)K−1 x
with
I K: camera intrinsics

D(x): depth at pixel x

I Iθ (ξ) is obtained via bilinear sampling with z-buffering

24Training Objective
3D End-Point-Error Loss:L=

1 XX
kTgt p − T(ξ l ) pk22
|P|l∈L p∈Pwith
I p = D(x)K−1 x: 3D point corresponding to pixel x in I
I L: set of coarse-to-ﬁne pyramid levels
The EPE loss balances the inﬂuences of translation and rotation.

25

Datasets
Object Motion:
I MovingObjects3D (ShapeNet objects moving in static 3D room)

26

Datasets
Object Motion:
I MovingObjects3D (ShapeNet objects moving in static 3D room)
Camera Motion:
I BundleFusion [Dai et al., 2017]
I DynamicBundleFusion [Lv et al., 2018]
I TUM RGB-D SLAM [Sturm et al., 2012]
We subsample frames to increase the motion/difﬁculty.

26

Datasets27

Baselines
Classical Methods:
I ICP implementation of Open3D [Zhou et al., 2018]
I RGB-D Visual Odometry [Steinbrücker et al., 2011]28

Baselines
Classical Methods:
I ICP implementation of Open3D [Zhou et al., 2018]
I RGB-D Visual Odometry [Steinbrücker et al., 2011]
Direct Pose Regression:
I Pose Regression with a FlowNetSimple backbone [Dosovitskiy et al., 2015]
I Cascaded Pose Regression
I Pose Regression with IC Reﬁnement [Li et al., 2018]28

Baselines
Classical Methods:
I ICP implementation of Open3D [Zhou et al., 2018]
I RGB-D Visual Odometry [Steinbrücker et al., 2011]
Direct Pose Regression:
I Pose Regression with a FlowNetSimple backbone [Dosovitskiy et al., 2015]
I Cascaded Pose Regression
I Pose Regression with IC Reﬁnement [Li et al., 2018]
Learning-based Optimization:
I LS-Net [Clark et al., 2018]
I DeepLK [Wang et al., 2018]28

Results on MovingObjects3D

Poi nt- Po i nt Po s e - CN N R . Clark et C. Wang etICP
al. 2018
al. 20 18

12.96

15.33

17.34

17.74

17.68

3D End Point Error ↓

Ours

29

Results on MovingObjects3D

T

I

I(ξ GT )I(ξ ∗ )
30

Results on TUM RGB-D

KEY FRAME 1

KEY FRAME 2

3.76

3.99

9.2

KEY FRAME 8

1.1

5.88
2.09

KEY FRAME 4

1.39
0.63

KEY FRAME 2

mRPE: rotation (deg) ↓

0.55
0.45

KEY FRAME 1

2.81
1.14

1.03
0.69

5.95

13.83

mRPE: translation (cm) ↓KEY FRAME 4

Steinbrücker et al, 2011

KEY FRAME 8

Ours
31

Ablation Study on DynamicBundleFusion

MethodNo learning
Ours (A)Ours (A)+(B)
Ours (A)+(B)+(C)Ours (A)+(B)+(C) (no WS)

3D EPE (cm)
8.58
7.11
6.88
4.64
3.82

32

Model Parameters and Inference Time

Model parameters (M)19Inference time (ms)
14.2
7.24

0.6
Pose-CNN

Ours

Pose-CNN (3iterations)

Ours (12 iterations)33

Summary
I Generalization of Lucas-Kanade algorithm lifting several assumptions

34

Summary
I Generalization of Lucas-Kanade algorithm lifting several assumptions
I 3 modules:
I Two-view Feature Encoder
I Convolutional M-Estimator
I Trust Region Network34

Summary
I Generalization of Lucas-Kanade algorithm lifting several assumptions
I 3 modules:
I Two-view Feature Encoder
I Convolutional M-Estimator
I Trust Region Network

I End-to-end trainable34

Summary
I Generalization of Lucas-Kanade algorithm lifting several assumptions
I 3 modules:
I Two-view Feature Encoder
I Convolutional M-Estimator
I Trust Region Network

I End-to-end trainable
I Evaluated on object motion and camera motion estimation tasks

34

Summary
I Generalization of Lucas-Kanade algorithm lifting several assumptions
I 3 modules:
I Two-view Feature Encoder
I Convolutional M-Estimator
I Trust Region Network

I End-to-end trainable
I Evaluated on object motion and camera motion estimation tasks
I Better generalization than image-to-pose regression models

34

Summary
I Generalization of Lucas-Kanade algorithm lifting several assumptions
I 3 modules:
I Two-view Feature Encoder
I Convolutional M-Estimator
I Trust Region Network

I End-to-end trainable
I Evaluated on object motion and camera motion estimation tasks
I Better generalization than image-to-pose regression models
I Higher accuracy compared to classical (non-learned) models

34

Summary
I Generalization of Lucas-Kanade algorithm lifting several assumptions
I 3 modules:
I Two-view Feature Encoder
I Convolutional M-Estimator
I Trust Region Network

I End-to-end trainable
I Evaluated on object motion and camera motion estimation tasks
I Better generalization than image-to-pose regression models
I Higher accuracy compared to classical (non-learned) models
Conclusion: Combining classical and deep methods increases robustness34

Thank you!
http://autonomousvision.github.io