|
|
|
“Pyramid Implementation of Optimal Step Conjugate Search Algorithms for Some Computer Vision Problems”
by Tal Simchony, Rama Chellappa, H. Jinchi, and Zeev Lichtenstein
Optimization of a cost function arises in several computer vision problems. The cost functions in these problems are usually derived from discretization of functionals obtained from regularization principles or stochastic estimation techniques using Markov random field models. In this paper we present a parallel implementation on a pyramid of the line search conjugate gradient algorithm for minimizing the cost functions mentioned above. By viewing the global cost function as a Gibbs energy function, we efficiently compute the gradients, inner products and the optimal step size using the pyramid. The global Gibbs energy of a given configuration is broken into its basic energy terms associated with different cliques. We let each low level processor sum the energies associated with its cliques. The local energy terms are added by the intermediate levels of the pyramid to the top, where the step size is determined by an efficient univariate search. Such implementation allows us to calculate the global energy in 0(log n) operations, where n is the number of grid points in each direction. Implementation of this algorithm to shape from shading results in a multiresolution conjugate gradient algorithm. Robustness and efficiency of the algorithm are also demonstrated on edge detection using graduated non convexity algorithm, and estimation of gray level images degraded by multiplicative noise.