In the previous post the mutual information for a pair of images
was expressed in terms of the angle between the gradients of and :
Note that if both images are equal then everywhere and mutual information is not well defined in the form above. This can be fixed by adding a Gaussian error term to the Jacobian of as we will explore at the end of this post. Here we take a different approach that circumvents this problem altogether.
The goal of image registration is to position the reference image by shifting it relative to such that mutual information is maximized. At that position the reference image provides the most information about . This makes perfect sense for image registration. Note however that the formula above is rather expensive to use directly for this purpose since it has to be computed for every possible offset of the reference image . One way around this is to apply some algorithm to reduce the number of positions to inspect such as steepest ascend. This is not what we will do here. Instead we use an approximation for mutual information that is efficient to compute for all positions.
Observing that the integrand in the mutual information expression is a function of we will approximate it by trigonometric polynomials of the form
for some finite degree . The constant term is chosen such that
for each trigonometric polynomial, so the area below all these functions is the same on the interval . The chosen approximation method considers these functions as probability densities. In particular each approximation is chosen such that
- for all
- minimizes the Kullback-Leibler divergence among all such trigonometric polynomials of degree .
The first three approximations are:
Their graphs are shown below. Note that the peak around gets more pronounced with an increasing degree. Also turns out to be very close (up to a scalar multiple) to which is easier to remember and could be used as an alternative approximation.
Here is a plot of together with the actual distribution .
Instead of the actual distribution for mutual information we can use any of the approximations to compute the approximate mutual information
Moreover this value can be computed efficiently for every image offset of the reference image as a cross-correlation of vector fields as we will see now. Identify with the complex plane . The inner product on translates to complex numbers as
Write the gradients of and normalized to length one as complex fields and (so ). Then for the angle between these gradients and any integer we have
This shows that every term in is a cross-correlation between two fields ( and ) and hence can be computed efficiently using FFT. Since for the reference image everything can be pre-computed the approximate mutual information can be computed with real FFT computations: two per term for to compute its spectrum and one reverse transform to compute the cross-correlation from a linear combination of all these spectra.
As a bonus this method can be used without any modification to locate only a part of the reference image in : Simply mask out the part of to be ignored by setting its normalized gradient field to zero there. This works because the fields are normalized and are not affected by local variations in gain and offset when the masked reference image is matched with . (In contrast, such variations make this simple masking scheme useless for an ordinary cross-correlatin approach.)
A final remark about how, as mentioned in the beginning of this post, error terms can be introduced in mutual information to get rid of the singularity at . If the Jacobian appearing in the definition of mutual information is distorted by adding a Gaussian error term then mutual information is changed to
where is an error ratio. Note that for we regain the original mutual information while for the other extreme we have . Note that for the singularity at is resolved. For those who want to explore further in this direction I leave you with the remark that
which helps in treating the integrand as a probability density in the angle .