This work is devoted to comparative experimental analysis of different stochastic optimization algorithms for image registration in spatial domain: stochastic gradient descent, Momentum, Nesterov momentum, Adagrad, RMSprop, Adam. Correlation coefficient is considered as the objective function. Experiments are performed on synthetic data generated via wave model with different noise-to-signal ratio.
Digital image registration is a process by which the most accurate match is determined between two images, which may have been taken at the same or different times, by the same or different sensors, from the same or different viewpoints. The registration process determines the optimal transformation, which will align the two images. This has applications in many fields as diverse as medical image analysis, pattern matching and computer vision for robotics, as well as remotely sensed data processing. In all of these domains, image registration can be used to find changes in images taken at different times, or for object recognition and tracking.
Spatial domain methods operate directly on pixels, and the problem of the estimation of registration
parameters α becomes the problem of searching for the extreme point of a multi-dimensional
objective function J(Z, α) . The objective function measures the similarity between two images
Z(1) z (j1) and Z(2) z (j2) , where j are nodes of grid mesh on which the images are
defined. There is a wide variety of similarity measures that can be used as objective functions [
The choice of optimization search technique depends on the type of problem under consideration.
Traditional nonlinear programming methods, such as the constrained conjugate gradient, or the
standard back propagation in neural network applications, are well suited to deterministic optimization
problems with exact knowledge of the gradient of the objective function. Optimization algorithms
have been developed for a stochastic setting where randomness is introduced either in the noisy
measurements of the objective function and its gradient, or in the computation of the gradient
approximation. Stochastic gradient ascend (descend) is one of the most powerful technique of this
class [
The main disadvantage of this optimization algorithm is presence of a large number of local
extreme points of the objective function due to the use of small samples and relatively short working
range in terms of registration parameters to be estimated. To overcome these problems the number of
sample elements can be increased. However, this leads to significant increase in computational efforts.
Another significant problem is choosing the hyperparameter Λt as it largely affects not only the
convergence rate but also the estimation accuracy. Thus, the problem of optimization of stochastic
gradient algorithm for image registration is an important, especially for real-time processing systems.
To overcome the mentioned problems some modifications of the “classical” stochastic gradient
descent have been proposed. This paper is devoted to comparative experimental analysis of these
modifications: Momentum, Nesterov momentum, Adagrad, RMSprop, Adam. These algorithms are
very effective, especially in training artificial neural networks [
Let us consider the most popular modifications of stochastic gradient descent optimization algorithm which can be used for solving image registration problem.
The idea behind Momentum optimization is quite simple [
ˆt ˆt1 mt , where mt hmt1 Λt t (J(Zt , t1) .
One can easily verify that if the gradient remains constant, the terminal velocity (i.e. the maximum size of the weight updates) is equal to that gradient multiplied by the learning rate multiplied by 1 . For example, if h 0.9 , then the terminal velocity is equal to 10 times the gradient times the 1 h learning rate, so Momentum optimization ends up going 10 times faster than “classical” stochastic gradient descent. This allows Momentum optimization to escape from plateaus much faster.
In [
This small tweak works because in general the momentum vector will be pointing in the right direction (i.e., toward the optimum), thus it will be slightly more accurate to use the gradient measured a bit farther in that direction rather than using the gradient at the original position. Figure 1 shows this effect. Here 1 represents the gradient of the cost function measured at the starting point ˆt1 , and 2 represents the gradient at the point located at ˆt1 hmt . As one can see, the Nesterov update ends up faster optimizers slightly closer to the optimum. After a while, these small improvements add up and the procedure ends up being significantly faster than regular Momentum optimization. Moreover, we should note that when the momentum pushes the weights across a valley, 1 continues to push further across the valley, while 2 pushes back toward the bottom of the valley. This helps reduce oscillations and thus converges faster.
λβ1 m λβ2 λβ2 λβ1
J
If we consider the elongated bowl problem again: gradient descent starts by quickly going down the steepest slope, then slowly goes down the bottom of the valley. However, it would be better if the algorithm could detect this early on and correct its direction to point a bit more toward the global optimum.
The Adagrad algorithm [
ˆt ˆt1 Λt t JZt ,ˆt1 //ct 1 2 , where ct ct1 t JZt ,ˆt1 2 .
The first step of this algorithm on each iteration is accumulating the square of the gradients into the vector ct . If the cost function is steep along the i -th dimension, then cit will get larger and larger at each iteration. The second step is almost identical to “classical” stochastic gradient descent, but with one big difference: the gradient vector is scaled down by a factor of ct 1 2 (the // symbol represents the element-wise division, and is a smoothing term to avoid division by zero, typically set to 10–8). In short, this algorithm decays the learning rate, but it does so faster for steep dimensions than for dimensions with gentler slopes. This is called an adaptive learning rate. It helps point the resulting updates more directly toward the global optimum. One additional benefit is that it requires much less tuning of the learning rate hyperparameter.
Adagrad often performs well for simple quadratic problems, but unfortunately it often stops too early when training neural networks. The learning rate gets scaled down so much that the algorithm ends up stopping entirely before reaching the global optimum.
Although Adagrad slows down a bit too fast and ends up never converging to the global optimum, the
RMSProp algorithm [
c r t dc r t1 1 d t JZt ,ˆt1 2 where d is the decay rate and it is typically set to 0.9.
Except on very simple problems, this optimizer almost always performs much better than Adagrad.
It also generally performs better than Momentum optimization and Nesterov momentum. In fact, it
was the preferred optimization algorithm of many researchers until Adam optimization came around.
2.5. Adam
Adam [
1 d1 d2 c At1 1 d2 t JZt ,ˆt1 2
.
1 d2
One can notice the similarity of Adam update rule to both Momentum optimization and RMSProp. The only difference is that it computes an exponentially decaying average rather than an exponentially decaying sum for mAt and c At , but these are actually equivalent except for a constant factor as the decaying average is just 1 d1 and 1 d2 times the decaying sum respectively. The momentum decay hyperparameter d1 is typically initialized to 0.9, while the scaling decay hyperparameter d 2 is often initialized to 0.999. As earlier, the smoothing term ϵ is usually initialized to a tiny number such as 10–8. In fact, since Adam is an adaptive learning rate algorithm like both Adagrad and RMSProp, it requires less tuning of the learning rate hyperparameter Λ t .
For efficiency analysis of differentit optimization algorithms it is reasonable to use simulated images
whose intensity probability distribution function and correlation function can be priori defined during
their synthesis. In conducted experiments simulated images based on wave model [
In order to measure the performance of the optimization algorithms we tested them on images with
different noise-to-signal ratio and with different μ ‒ the number of points in the sample using for
estimation of the gradient of the chosen objective function. Correlation coefficient [
The number of iterations before convergence of mismatch Euclidean distance [
Figure 3 shows the convergence of mismatch Euclidean distance for the algorithms with different sample size μ . Hereafter, curve 1 corresponds to “classical” stochastic gradient descent, 2 ‒ stochastic gradient descent with Momentum, 3 – Nesterov momentum (plus markers), 4 – Adagrad (plus markers), 5 – RMSprop (dashed line), 6 – Adam (dashed line).
One can see that in both cases “classical” stochastic gradient descent shows the worst result as it starts to converge only after 800 iterations for μ 5 and after 700 iterations for μ 20 . Momentum optimization algorithm performs almost identically but slightly better for μ 20 . The best results in both cases are provided by Adam and RMSprop optimizations as they start to converge after 300 iterations for μ 5 and after 200 iterations for μ 20 . Moreover, it is obvious that Adam algorithm in both situations has less variance then RMSprop, thus we can conclude that it is more stable and hence preferable. Adagrad and Nesterov momentum algorithms show close results in terms of number of iterations before convergence (500 iterations for μ 5 and after 450 iterations for μ 20 ), but in the beginning Adagrad has much faster convergence rate and with some optimization (e.g. increasing or dropping learning rates after a number of iterations) it possibly can outperform Nesterov momentum.
Also, we can conclude that all of the algorithms have better convergence rate with bigger sample size. It is reasonable from theoretical point of view because the objective function gradient estimates become less noisy.
Let us test the algorithms in case of noisy images with different signal-to-noise ratio q . In this experiment we were using the sample size μ 5 for each algorithm and q . Figure 4 shows the convergence of algorithms for q 50 and q 2 .
As in the previous experiment, “classical” stochastic gradient descent shows the slowest convergence rate in both set-ups. Adam and RMSprop algorithms have the best result. For q 50 their curves are almost identical but when the noise increases Adam has much faster convergence rate in the beginning, hence it can potentially show better result. In addition, we can notice that with very intense noise ( q 2 ) Adagrad converges with bigger error in comparison with other algorithms and it performs almost the same as “classical” stochastic gradient descent. In order to reduce the error we can choose smaller learning rates. However, with smaller rate sometimes it was not able to converge at all.
Additionally, it is clear that noise affects not only the convergence rate but also the variance of estimates for all of the algorithms as the curves become less smooth.
Satellite images were used for the comparative analysis on real data. Figure 5 shows an example of the images taken in different weather conditions.
Figure 6 shows an example of mismatch Euclidean distance convergence of the algorithms for images shown in figure 5. For this experiment μ was set to 25 and the results were averaged by 100 realizations as them became more noisy in comparison with synthesized images, especially for the algorithms with adaptive learning rates.
One can easily notice that the results on real data are almost identical to the results on synthesized images. Again, Adam and RMSprop algorithms are the fastest in terms of convergence rate. However here we can see the algorithms with adaptive learning rates have much noisier curves that the others. It can be explained by the fact that when dealing with real images we have noisier gradient estimation, thus in these algorithms the learning rate estimation becomes less stable.
The comparative analysis of different optimization algorithms for solving image registration problem in spatial domain shows that in each case “classical” stochastic gradient descent shows the worst result in terms of the convergence rate of registration parameters’ estimates. Momentum optimization algorithm just slightly outperforms it. Adagrad and Nesterov momentum algorithms show close results in terms of number of iterations before convergence but except for the situation with intense noise Adagrad in the beginning has much faster convergence rate and with some optimization (e.g. increasing or dropping learning rates after a number of iterations) it possibly can outperform Nesterov momentum The best results are provided by Adam and RMSprop optimizations Moreover, it is obvious that Adam algorithm is almost always preferable as it has less variance then RMSprop.
Furthermore, we can conclude that all of the algorithms have better convergence rate with bigger sample size. It is reasonable from theoretical point of view because the objective function gradient estimates become less noisy. Additionally, it is clear that noise affects not only the convergence rate but also the variance of estimates for all of the algorithms as the curves become less smooth.
Experiments on real satellite images show mostly identical results.
This work was supported by the Russian Foundation for Basic Research, projects no. 16-41-732084 and 16-31-00468.