# Derivative of mutual information in EMMA algorithm for image alignment

This question refers to the paper 'Alignment by Maximization of Mutual Information' by Paul Viola and William M. Wells III, published by International Journal of Computer Vision, 24(2) pg 137–154, 1997.

The paper introduces an algorithm EMMA (Empirical entropy manipulation and analysis) which relies on maximizing the mutual information between images in order to align them. Given two images $$U$$ and $$V$$ whose data is expressed as $$u(x)$$ and $$v(y)$$, find $$\tag{1} \hat{T} = \mathrm{arg\,max}_T I(u(x), v(T(x)).$$ Here $$x$$ is a random variable over coordinates of the model. In the case of digital images, it is a random variable over allowed indices of the model. The derivative of mutual information between the images with respect to the transformation $$T$$ is given by $$\tag{2} \widehat{\frac{dI}{dT}} = \frac{1}{N_B}\sum_{x_i \in B}\sum_{x_j \in A}(v_i - v_j)^T\left[W_v(v_i, v_j)\psi_v^{-1} - W_{uv}(w_i, w_j)\psi_{vv}^{-1}\right]\frac{d}{dT}(v_i - v_j).$$ This expression appears as equation (17) in the paper. I am facing difficulty in understanding this equation. If $$v \in \mathbb{R}^n$$ then $$w \in \mathbb{R}^{2n}$$ and hence the product $$(v_i - v_j)^T\psi_{vv}^{-1}\frac{d}{dT}(v_i - v_j)$$ is not defined. For $$(v_i - v_j)^T$$ is a row vector is an $$1 \times n$$ matrix and $$\psi_{vv}^{-1}$$ is a $$2n \times 2n$$ matrix. This is because the paper defines $$v = T(u)$$ and $$w = [u, v]$$, where $$u$$ is one of the images.

I also consulted Paul Viola's Ph.D. thesis. But the equation mentioned in it (topmost equation on page 101) is $$\tag{3} \widehat{\frac{dI}{dT}} = \frac{1}{N_B}\sum_{x_i \in B}\sum_{x_j \in A}(v_i, v_j)^T\left[W_v(v_i, v_j)\psi_v^{-1} - W_{uv}(w_i, w_j)\psi_{vv}^{-1}\right]\frac{d}{dT}(v_i - v_j).$$ In this case, the following terms cannot be evaluated because the matrices involved in their definition are incompatible.

Can anyone please point out where I am going wrong. This is a widely cited paper and there is a good chance that I am making a mistake in understanding it.

I am not an expert on mutual information but I understand a fair bit of the mathematics here.

So, I read the paper and indeed there seems some typo in the equation $$(17)$$. I am yet to figure that out.

But I have a way for you to compute the derivate as per equation $$(17)$$. So, if we go back to the equation, then it seems that equation $$17$$ is essentially subtraction of the two terms above. Now, the differentiation of $$\frac{d}{dT}h(v(T(x)))$$ and $$\frac{d}{dT}h(u(x),v(T(x)))$$ can be computed using equation $$16$$. So, you could develop a function (in Python or any language of your choice) as per equation $$16$$ and just use that function twice, once for $$h(v(T(x)))$$ and $$h(u(x),v(T(x)))$$. And then, subtract the two values. This way you wouldn't have the dimensionality issue.

Hope this was sufficient. On a side note, this is essentially an optimization problem where your cost function to optimize is the mutual information $$I$$. In my work on optimization problems we often do this function subtraction trick.

P.S. You can even reverse engineer and try different variations for equation $$17$$ and then, figure out your issue of dimensionality.