Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Fast Surface Interpolation Using Hierarchical Basis Functions

Richard Szeliski


The rapid solution of surface interpolation and other regularization problems on massively parallel architectures is an important problem within computer vision. Fast relaxation algorithms can be used to integrate sparse data, resolve ambiguities in optic flow fields, and guide stereo matching algorithms. In the past, multigrid techniques have been used in order to speed up the relaxation. In this paper, we present an alternative to multigrid relaxation which is much easier to implement and more generally applicable. Our approach uses conjugate gradient descent in conjunction with a hierarchical (multiresolution) set of basis functions. The resulting algorithm uses a pyramid to smooth the residual vector before the new direction is computed. We present simulation results which show the speed of convergence and its dependence on the choice of interpolator, the number of smoothing levels, and other factors. We also discuss the relationship of this approach to other multiresolution relaxation and representation schemes.


Publication typeArticle
Published inIEEE Transactions on Pattern Analysis and Machine Intelligence
PublisherIEEE Computer Society
> Publications > Fast Surface Interpolation Using Hierarchical Basis Functions