Project topics and materials
Get Complete Project Material File(s) Now! »
Reviewing previous work
Dense image registration has been extensively studied since the inception of computer vision. We can find dense image registration problems in many fields such as medical and biology imagery, planetary sciences, industrial verificatio or video surveillance. We point the curious reader toward [23], [178], [45] and [138] for an extensive review on image registration.
Basics of convex optimization in a tiny nutshell
As a preamble, we remind some mathematical definitions useful in the context of this chapter. For an extended introduction on convex optimization, we refer the curious reader to Fundamentals of Convex Analysis by Hiriart-Urruty and Lemaréchal [78], Convex Optimization by Boyd and Vandenberghe [15] or Optimization. Applications in image processing. by Nikolova [133] from which we borrow the following definitions and theorems.
Conditioning and Auto tuning of step sizes Improving conditioning
The convergence speed of Algorithm 1 is tightly linked to the conditioning of th linear operator L since its norm impacts the step size parameters and . We can always make one of or larger, but this comes at the expense of reducing the other. Hence, improving the conditioning of L is critical. Fortunately, conditioning improvement has been studied for a long time and successfully applied to primal dual problems [143, 162]. In our context, we only investigate the simple case where the operator L can be written as a diagonal matrix D with strictly positive elements and a well conditioned linear operator G: L DG
Augmenting path solvers
Augmenting path solvers [147] are algorithms designed to solve the dual form of the max-flow / min-cut, i.e., problem (4.28). Here, we describe the augmenting path method of [17] that experimentally outperforms other variant for computer vision problems [166]. It sequentially alternates three stages:
1. Find an augmenting path: a chain subgraph A of the main graph G whose dual variables can be further optimized. For computer vision problems, this is generally done by growing two binary trees simultaneously from the source and sink by following edges that have positive capacities. An augmenting path is found when the two trees meet. If no augmenting path can be found, then the algorithm terminates.
2. The augmenting phase: optimize the dual variables of the chain subgraph A. Apply a re-parametrization of the problem as describe in paragraph 4.3.3.
3. Adopt orphan: An optional step that greatly speeds up augmenting path is to update dynamically the growing trees after the augmentation phase. During the augmentation the re-parametrization might have set the capacities of some edge to 0, potentially invalidating parts of the source and sink trees. The adoption phase corrects this phenomenon.
Table of contents :
1 Introduction partielle (en français)
1.1 Contexte
1.1.1 Vue du ciel
1.1.2 Applications à la géologie
1.1.3 Un problème d’appariement d’images
2 Introduction (English language)
2.1 Context
2.1.1 Monitoring from above
2.1.2 Application to geology
2.1.3 An image registration problem
2.2 Reviewing previous work
2.2.1 Priors
2.2.2 Framework
2.3 An approximate modeling
2.3.1 Mathematical modeling
2.3.2 Approximations
2.4 Thesis overview
2.4.1 Document organization
2.4.2 Contributions
2.4.3 List of publications
3 First order Primal-Dual techniques for convex optimization
3.1 Introduction and contributions
3.1.1 Introduction
3.1.2 Chapter organization
3.1.3 Contributions
3.2 Problem formulation
3.2.1 Basics of convex optimization in a tiny nutshell
3.2.2 Problem of interest
3.2.3 From a primal to a primal dual form
3.3 First order Primal Dual techniques
3.3.1 Smoothing: Moreau envelope and the proximal operator
3.3.2 Decoupling: Fenchel transform
3.3.3 Primal Dual algorithm
3.3.4 Conditioning and Auto tuning of step sizes
3.4 Reformulating `1 based functions, Proximal operators, and Fenchel transformations
3.4.1 On reformulating `1 based functions
3.4.2 Proximal operators
3.4.3 Fenchel transform
3.5 TV regularized problems
3.5.1 Notations
3.5.2 Some classic TV regularized problems
3.5.3 Truncation theorem for convex TV regularized problems
3.5.4 A hierarchy of optimal dual spaces for TV-`2
3.5.5 Intersection of optimal dual space
3.5.6 A new primal-dual formulation of the ROF model
3.5.7 Fused Lasso approximation on pairwise graph for various sparsifying strength
3.5.8 ROF model with a Global regularization term
3.6 Examples of application
3.6.1 Mincut/Maxflow
3.6.2 Image denoising
3.6.3 L-ROF model vs ROF model for denoising
3.7 Conclusion
4 Maxflow and Graph cuts techniques
4.1 Introduction and contributions
4.1.1 Introduction
4.1.2 Chapter organization
4.1.3 Contributions
4.2 Discrete optimization in a tiny nutshell
4.2.1 Sub-modularity
4.2.2 Problems of interest
4.2.3 Representation of pairwise binary sub-modular functions
4.2.4 A link between discrete and convex optimization through TV regularization
4.2.5 Primal dual scheme for integer Linear programming
4.3 Max-flow and min-cut problems
4.3.1 The max-flow / min-cut
4.3.2 From a min-cut problem to a max-flow problem
4.3.3 Simplified equations
4.3.4 Characterization of obvious partial primal solutions
4.3.5 ROF and Maxflow
4.4 Solvers for min-cut / max-flow problems
4.4.1 Solver for chain graphs
4.4.2 Iterative solvers
4.4.3 Augmenting path solvers
4.5 Graph-cuts for non convex problems
4.5.1 Alpha-expansion
4.5.2 Fast-PD
4.5.3 A note on Fast-PD implementation
4.6 Experiments
4.6.1 The stereo-Matching Problem
4.6.2 Maxflow experiments for 4 connected graph
4.6.3 Fast PD implementation experiments
4.6.4 Fast PD vs Alpha-expansion
4.7 Conclusion
5 Coarsening schemes for optimization techniques
5.1 Introduction and contributions
5.1.1 Introduction
5.1.2 Chapter organization
5.1.3 Contributions
5.2 Smoothing and Coarsening scheme for first order primal dual optimization techniques
5.2.1 Preliminary work
5.2.2 Approach
5.2.3 Surrogate function via Filtering scheme
5.2.4 Surrogate function via coarsening
5.2.5 Experiments
5.3 Coarsening scheme for Graph-Cuts solvers
5.3.1 Pairwise undirected discrete MRF
5.3.2 Image pyramid
5.3.3 Energy pyramid
5.3.4 Inference by Learning
5.3.5 Experiments
5.4 Conclusion
6 Applications
6.1 Introduction and chapter organization
6.1.1 Introduction
6.1.2 Chapter organization
6.2 Notations and Preliminaries
6.2.1 Images
6.2.2 Graph
6.2.3 LiDAR as elevation maps
6.2.4 Matching criterion
6.3 Stereo-matching
6.3.1 Camera models and Epipolar geometry
6.3.2 The stereo matching problem
6.3.3 Experiments
6.4 Simulated Earth crust deformation
6.4.1 Context
6.4.2 Model
6.4.3 Experiments
6.5 Damage detection in New-Zealand
6.5.1 Context
6.5.2 Model
6.5.3 Experiments
6.6 Chapter conclusion
7 Conclusions, limits and future work
