# Image registration using gradient descent

I have a target image $$f(x,y)$$ (where $$x \in [0, 250]$$ and $$y \in [0,300]$$), and a source image $$g(x,y)$$

I want to align $$g$$ to $$f$$ using the transformation : $$\Psi(x,y;t_x, t_y, \theta) = \begin{pmatrix}\cos(\theta) & -\sin(\theta) & t_x \\ \sin(\theta) & \cos(\theta) & t_y\end{pmatrix}\begin{pmatrix}x \\ y \end{pmatrix}$$

I'm trying to do this by minimizing the squared error : $$l(p) = \sum_{x,y}{(f(x,y) - g(\Psi(x,y;p))}^2$$

I first computed the gradients : \begin{align} \frac{\partial l(p)}{\partial t_x} & = \sum_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial t_x}g(\Psi(x,y,p))\right)\right) \\ & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial t_x}g(\Psi(x,y,p))\right)\right) \\ & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi_x}g(\Psi(x,y,p))\frac{\partial \Psi_x}{\partial t_x}\right)\right)\\ & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi_x}g(\Psi(x,y,p))\right)\right)\\ \frac{\partial l(p)}{\partial t_y} & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi_y}g(\Psi(x,y,p))\right)\right) \end{align} However, for $$\theta$$, I find this : \begin{align} \frac{\partial l(p)}{\partial \theta} & = \sum_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\ & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\ & \text{by chain rule } \frac{\partial}{\partial \theta}g(\Psi(x,y,p)) = \frac{\partial}{\partial \Psi_x}g(\Psi_x(x,y;p), \Psi_y(x,y;p))\frac{\partial \Psi_x}{\partial \theta} + \\ & \frac{\partial}{\partial \Psi_y}g(\Psi_x(x,y;p), \Psi_y(x,y;p))\frac{\partial \Psi_y}{\partial \theta} \\ & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi_x}g_\Psi\frac{\partial \Psi_x}{\partial \theta} + \frac{\partial }{\partial \Psi_y}g_\Psi\frac{\partial \Psi_y}{\partial \theta}\right)\right) \end{align}

Since $$\frac{\partial \Psi_x}{\partial \theta} = -x\sin(\theta) - y\cos(\theta)$$, it can reach high values such as $$300$$ (depending on $$\theta$$). This means that $$\frac{\partial l(p)}{\partial \theta}$$ have values way bigger than $$\frac{\partial l(p)}{\partial t_x}$$ for instance, which feel quite wrong.

I think I did a mistake calculating the gradient, but I don't understand where?

• Something's wrong with the definition of your function $\Psi$; you can't multiply a $2\times 3$ matrix by a $2$-column-vector. I suspect you mean $\begin{pmatrix}x\\y\\1\end{pmatrix}$ instead of $\begin{pmatrix}x\\y\end{pmatrix}$. – D.W. Mar 17 at 21:46
• @D.W. Yes, I mean that but It's just a notation to avoid the dummy $1$ ! $g_\Psi$ is a notation to avoid writing $g(\Psi(x,y;p)$. It comes from $\frac{\partial}{\partial\theta}g(\Psi(x,y;p)) = \frac{\partial}{\partial\theta}(\Psi_x, \Psi_y)$ then I derivate a composition for a 2-variable function. – servabat Mar 17 at 21:55
• Chain rule states $f(g_x(u), g_y(u)) = f^{(1,0)}(g_x(u), g_y(u))\frac{\partial}{\partial u}g_x(u) + f^{(0,1)}(g_x(u), g_y(u))\frac{\partial}{\partial u}g_y(u)$ if I'm not mistaken – servabat Mar 17 at 22:28

It doesn't feel wrong to me.

A rotation by a small amount, say one degree, changes the location of an object in the image by many pixels. For instance, suppose you have a 1000x1000 image, and you rotate it by one degree around the upper-left corner. Then an object near the upper-right corner moves upward/downward by about 17 pixels. There is "leverage" proportional to the size of the image; rotate a long lever by a small rotation, and the end of the lever still moves a large way.

In contrast, a translation by a small amount, say one pixel, changes the location of an object in the image by only a little. For instance, if you have that same image and you translate by one pixel, then the object moves by only 1 pixel.

So it is not surprising (to me) that the gradient in the first case might be much larger than the gradient in the second case.

• Yes, I understand, however, it feels that something is wrong, because changing the coordinate system would not change the first two gradients value, but would change the last gradient value (say for instance, I normalize $x$ and $y$ between $0$ and $1$). – servabat Mar 17 at 21:59
• It means that when trying to apply a gradient descent algorithm, my $\theta$ value varies a lot (for instance, my image completely rotates when I just apply a translation to the target image). Actually, following that gradient just doesn't minimize my function at all, my loss function just keeps increasing. – servabat Mar 17 at 22:01
• @servabat, OK, interesting. I'm thinking it's possible that might be separate issue (but I don't really know, and I'm speculating wildly here). I expect it's tricky to use vanilla gradient descent for this, because the function you're minimizing probably won't be very linear (except for small step sizes). The general idea has been studied in the computer vision literature, under the name Lucas-Kanade, and there are a number of improvements and tricks people have studied. Maybe studying Lucas-Kanade might be helpful? – D.W. Mar 18 at 3:42