Digital Video Processing, Second Edition

Appendix D. Optimization Methods

Several motion-estimation and segmentation problem formulations require minimization of a non-convex criterion function E(u), where u is some N-dimensional unknown vector. Then, the motion-estimation/segmentation problem can be posed so as to find

û = arg min_u E(u)

This minimization is exceedingly difficult due to large dimensionality of the unknown vector and the presence of local minima. With non-convex functions, gradient descent methods (reviewed in Section D.1) generally cannot reach the global minimum, because they get trapped in the nearest local minimum. In Section D.2, we present two simulated (stochastic) annealing algorithms, the Metropolis algorithm [Met 53] and the Gibbs sampler [Gem 84], which are ...