Image Registration using Convex Analysis
Introduction
This project is joint work by Adam Oberman and Brittany Froese (M.S. at SFU)
In this project, which is motivated by the brain mapping problem we are given a small number of sampled values of a mapping, which is assumed to be diffeomorphism with a small distortion.
Our goal is to recover the mapping, and possibly its inverse.
We begin from the assumption that the mapping is the gradient of a convex function. This assumption is reasonable if we assume that simple geometric motions have been removed, so that the data is centered and lined up (i.e. eliminated translation and rotation). An alternative and popular method is to use optimal mass transportation to build a mapping. But this is better suited to densities, and not to sampled values.
Our idea is to set up a convex optimization problem to recover the convex envelope of the potential function whose gradient is the mapping. This convex optimization turns out to be linear program (LP) with a small number of variables. This LP can be solved easily using freely available LP solvers.
The problem in a nutshell: recovering the identity in one dimension
- here we show the problem in one dimension. Note that the convex envelope of a quadratic sampled at a few points is piecewise linear. So we smooth by adding the largest possible quadratic term at each point.
Building Mappings with good local properties
- consider the problem of moving a coordinate mesh to another coordinate mesh in some optimal way given certain constraints and a measure of quality.
- for example, suppose you have n points which must map to another n points, and you want to build a smooth mapping which interpolated the rest of the point in the domain. If there is one mapping, then there are many such mappings, so a measure of quality is needed to find the best one. For example, the measure of quality may be that the mapping is close to the identity, or the average map in some norm.
- these types of problems come up in Image Registration, say we take measurements of a brain at different times, and wish to compare them, or wish to compare them to a reference brain.
- it's fair to assume that the map is a diffeomorphism, in other words, nothing has broken.
- the matching criteria might be the pixel intensity, which we wish to match as much as possible.
- one property of a good mapping is that squares get mapped to squares. This can fail if the jacobian of the map ever changes sign. In fact, once we have substracted out the global rotation and translation, it's fair to assume that all eigenvalues of the jacobian are positive. Or, we can assume that the mapping is the gradient of a convex function.
- the property that the mapping is the gradient of a convex function can be written as a linear constraint, using the the subgradients, and so this restriction is a linear inequality, which is a convex constraint.
The convex optimization problem for recovering a convex function from its subgradient
Explain how (up to shifting the value at one point) convexity translates into a bunch of linear inequalitys for the supporting hyperplane. Given the values at the sample points, can recover the plane by solving the problem.