| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Physically Based Adaptive Preconditioning for Early Vision
June 1997 (vol. 19 no. 6)
pp. 594-607
Abstract—Several problems in early vision have been formulated in the past in a regularization framework. These problems, when discretized, lead to large sparse linear systems. In this paper, we present a novel physically based adaptive preconditioning technique which can be used in conjunction with a conjugate gradient algorithm to dramatically improve the speed of convergence for solving the aforementioned linear systems. A preconditioner, based on the membrane spline, or the thin plate spline, or a convex combination of the two, is termed a physically based preconditioner for obvious reasons. The adaptation of the preconditioner to an early vision problem is achieved via the explicit use of the spectral characteristics of the regularization filter in conjunction with the data. This spectral function is used to modulate the frequency characteristics of a chosen wavelet basis, and these modulated values are then used in the construction of our preconditioner. We present the preconditioner construction for three different early vision problems namely, the surface reconstruction, the shape from shading, and the optical flow computation problems. Performance of the preconditioning scheme is demonstrated via experiments on synthetic and real data sets. We note that our preconditioner outperforms other methods of preconditioning for these early vision problems, described in computer vision literature.
[1] 594 B.K.P. Horn and B.G. Schunk, "Determining Optical Flow," Artificial Intelligence, vol. 17, pp. 185-203, 1981.[2] B.K.P. Horn and M.J. Brooks, eds., Shape from Shading.Cambridge, Mass.: MIT Press, 1989.[3] D. Terzopoulos, "Regularization of Inverse Visual Problems Involving Discontinuities," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 4, pp. 413-424, 1986.[4] D. Terzopoulos, "The Computation of Visible Surface Representations," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 10, no. 4, pp. 417-438, Apr. 1988.[5] B.C. Vemuri, A. Mitiche, and J.K. Aggarwal, "Curvature-Based Representation Of Objects From Range Data," Image and Vision Computing, vol. 4, no. 2, pp. 107-114, 1986.[6] R.M. Bolle and B.C. Vemuri, "On Three-Dimensional Surface Reconstruction Methods," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 1, Jan. 1991.[7] G.H. Golub and C.F. Van Loan, Matrix Computations. The Johns Hopkins University Press, second edition, 1989.[8] D. Terzopoulos, "Image Analysis Using Multigrid Relaxation Methods," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, pp. 129-139, 1986.[9] R. Szeliski, "Fast Surface Interpolation Using Hierarchical Basis Functions," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 6, pp. 513-528, June 1990.[10] A. Pentland, "Interpolation Using Wavelet Basis," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 4, pp. 410-414, 1994.[11] M.H. Yaou and W.T. Chang, "Fast Surface Interpolation Using Multiresolution Wavelet Transform," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 7, pp. 673-688, July 1994.[12] D. Suter, "Constraint Networks in Vision," IEEE Trans. Computers, vol. 40, no. 12, pp. 1359-1367, Dec., 1991,.[13] B.L. Buzbee, F.W. Dorr, J.A. George, and G.H. Golub, "The Direct Solution of the Discrete Poison Equation on Irregular Regions," SIAM J. Numerical Analysis, vol. 8, no. 4, pp. 722-736, Dec. 1971.[14] S.H. Lai and B.C. Vemuri, “An$o(n)$Iterative Solution to the Poisson Equation in Low-Level Vision Problems,” Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 9-14, June 1994 (also Technical Report 93-035, Dept. of Computer Information Science and Eng., Univ. of Florida). [15] T. Simchony, R. Chellappa, and M. Shao, "Direct Analytical Methods for Solving Poisson Equations in Computer Vision Problems," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 5, May 1990.[16] A.K. Chhabra and T.A. Grogan, "On Poisson Solvers and Semi- Direct Methods for Computing Area Based Optical Flow," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 11, Nov. 1994.[17] R. Szeliski, "Fast Shape From Shading," CVGIP: Image Understanding, vol. 53, no. 2, pp. 129-153, 1991.[18] H. Yeserentant, "On Multilevel Splitting of Finite Element Spaces," Numeriche Mathematik, vol. 49, pp. 379-412, 1986.[19] G. Beylkin, R.R. Coifman, and V. Rokhlin, "Fast Wavelet Transforms and Numerical Algorithm I," Comm. Pure and Applied Math., vol. 44, pp. 141-183, 1991.[20] G. Golub and J.M. Ortega, Scientific Computing. Academic Press, 1993.[21] S. Jaffard, "Wavelet Methods for Fast Resolution of Elliptic Problems," SIAM J. Numerical Analysis, vol. 29, no. 4, pp. 965-986, Aug. 1992.[22] B.K.P. Horn, "Height From Shading," Int'l. J Computer Vision, vol. 5, no. 1, pp. 174-208, 1990.[23] J.L. Barron, D.J. Fleet, and S.S. Beauchemin, "Performance of Optical Flow Techniques," Int'l J. Computer Vision, vol. 12, no. 1, pp. 43-77, 1994.[24] S.H. Lai and B.C. Vemuri, "Robust and Efficient Algorithms for Optical Flow Computation," Proc. Int'l Symp. Computer Vision,Coral Gables, Fla., 1995, pp. 455-460.[25] S.G. Mallat,“A theory for multiresolution signal decomposition: The wavelet representation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, no. 7, pp. 674-693, 1989.[26] O. Rioul and M. Vitterli, "Wavelets and Signal Processing," IEEE Signal Processing Magazine, vol. 8, pp. 14-38, 1991.[27] B.C. Vemuri and A. Radisavljevic, "Multiresolution Stochastic Hybrid Shape Models With Fractal Priors," ACM Trans. Graphics, vol. 13, no. 2, pp. 177-207, Apr. 1994.[28] M. Kass, A. Witkin, and D. Terzopoulos, "Snakes: Active Contour Models," Int'l.J. Computer Vision, vol. 1, pp. 321-331, 1987.
Index Terms:
Early vision, computational vision, adaptive preconditioning, wavelet transform, regularization, surface reconstruction, shape from shading, optic flow computation.
Citation:
Shang-Hong Lai, Baba C. Vemuri, "Physically Based Adaptive Preconditioning for Early Vision," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 6, pp. 594-607, June 1997, doi:10.1109/34.601247
