# 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, 2019 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. Mar 17, 2019 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 Mar 17, 2019 at 22:28
• For such problems, if the function is not extremely unstable, it's always a good thing to test them against a finite difference method (at best, written by somebody else you trust). Apr 11, 2020 at 8:25
• In a rotation, the farther you are from the rotation center, the larger the motion. The motion amplitude is even unbounded, so don't be surprised.
– user16034
Apr 1, 2022 at 14:13

By the chain rule, for some parameter $$\xi$$,

$$\frac12\frac{\partial l}{\partial\xi}=\sum_{x,y}(f-g)\left(\frac{\partial g}{\partial \Psi_x}\frac{\partial \Psi_x}{\partial\xi}+\frac{\partial g}{\partial \Psi_y}\frac{\partial \Psi_y}{\partial\xi}\right).$$

Using complex numbers for convenience,

$$\Psi=e^{i\theta}z+t$$ and

$$\left|\frac{\partial\Psi}{\partial\theta}\right|=|ie^{i\theta}z|=|z|,\\ \left|\frac{\partial\Psi}{\partial t}\right|=1.$$

As you see, those derivatives don't have comparable magnitudes.

The moral of the story is that the steps used in the iterations should be adjusted accordingly. For instance, a unit step for translation will be coherent with an angular step that corresponds to an average translation of one unit for the whole image (so the step should be inversely proportional to the image size).

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$). Mar 17, 2019 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. Mar 17, 2019 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, 2019 at 3:42