Optimal Estimation of Contour Properties by Cross-Validated Regularization
June 1989 (vol. 11 no. 6)
pp. 600-610
DOI Bookmark:
http://doi.ieeecomputersociety.org/10.1109/34.24794
The problem of estimating the properties of smooth, continuous contours from discrete, noisy samples is used as vehicle to demonstrate the robustness of cross-validated regularization applied to a vision problem. A method for estimation of contour properties based on smoothing spline approximations is presented. Generalized cross-validation is to devise an automatic algorithm for finding the optimal value of the smoothing (regularization) parameter from the data. The cross-validated smoothing splines are then used to obtain optimal estimates of the derivatives of quantized contours. Experimental results are presented which demonstrate the robustness of the method applied to the estimation of curvature of quantized contours under variable scale, rotation, and partial occlusion. These results suggest the application of generalized cross-validation to other computer-vision algorithms involving regularization. [1] P. R. Adby and M. A. H. Dempster,Introduction to Optimization Theory. New York: Wiley, 1974.[2] R. S. Anderssen and P. Bloomfield, "A time series approach to numerical differentiation,"Technometrics, vol. 16, no. 1, pp. 69-75, Feb. 1974.[3] D. M. Bates and G. Wahba, "Computational methods for generalized cross-validation with large data sets," inTreatment of Integral Equations by Numerical Methods, C. T. H. Baker and G. F. Miller, Eds. New York: Academic, 1982.[4] D. M. Bates, M. J. Lindstrom, G. Wahba, and B. S. Yandel, "GCVPACK--Routines for generalized cross-validation," Dep. Statistics, Univ. Wisconsin, Tech. Rep. 775, Nov. 1985; also inCommun. Statist. Simul. Comput., vol. 16, pp. 263-297, 1987.[5] T. Boult, "What is regular in regularization," inProc. First Int. Conf. Computer Vision, London, 1987, pp. 457-462.[6] R. L. Brown, J. Durbin, and J. M. Evans, "Techniques of testing consistency of regression relationships over time,"J. Royal Stat. Assoc., vol. 70, pp. 70-79, 1975.[7] P. Craven and G. Wahba, "Smoothing noisy data with spline functions-Estimating the correct degree of smoothing by the method of generalized cross-validation,"Numerische Mathematik, no. 31, pp. 377-403, 1979.[8] J. Duchon, "Splines minimizing rotation-invariant semi-norms in Sobolev spaces," inConstructive Theory of Functions of Several Variables, W. Schempp and K. Zeller, Eds. 1976, pp. 85-100.[9] L. Elden, "Algorithms for the regularization of ill-conditioned least squares problems,"BIT, vol. 17, pp. 134-145, 1977.[10] L. Elden, "A note on the computation of generalized cross-validation function for ill-conditioned least squares problems,"BIT, vol. 24, pp. 467-472, 1984.[11] S. Geisser, "The predictive sample reuse method with applications,"J. Amer. Stat. Assoc., vol. 70, no. 350, pp. 320-328, 1975.[12] G. H. Golub, M. Heath, and G. Wahba, "Generalized cross-validation as a method for choosing a good ridge parameter,"Technometrics, vol. 21, no. 2, pp. 215-223, May 1979.[13] W. E. L. Grimson, "An implementation of a computational theory of visual surface interpolation,"Comput. Vision, Graphics, Image Processing, vol. 22, pp. 39-69, 1983.[14] W. J. Kennedy, Jr., and J. E. Gentle,Statistical Computing. New York: Dekker, 1980.[15] G. S. Kimeldorf and G. Wahba, "A correspondence between Bayesian estimation on stochastic processes and smoothing by splines,"Ann. Math. Stat., vol. 41, no. 2, pp. 495-502, 1970.[16] D. Lee and T. Pavlidis, "One-dimensional regularization with discontinuities," inProc. First Int. Conf. Computer Vision, London, 1987, pp. 573-577.[17] K. C. Li, "From Stein's unbiased estimate to the method of generalized cross validation,"Ann. Stat., vol. 13, no. 4, pp. 1352-1377, 1985.[18] A. A. Melkman and C. A. Micchelli, "Optimal estimation of linear operators in Hilbert spaces from inaccurate data,"SIAM J. Numer. Anal., vol. 16, pp. 87-105, 1979.[19] D. Nychka, G. Wahba, S. Goldfrab, and T. Pugh, "Cross-validated spline methods for the estimation of three-dimensional tumor size distributions from observations on two-dimensional cross-sections,"J. Amer. Stat. Assoc., vol. 79, pp. 832-846, 1984.[20] T. Poggio and V. Torre, "Ill-posed problems and regularization analysis in early vision," inProc. DARPA Image Understanding Workshop, 1984, pp. 257-263.[21] T. Poggio, V. Torre, and C. Koch, "Computational vision and regularization theory,"Nature, vol. 317, pp. 314-319, 1985.[22] T. Poggio, H. Voorhees, and A. Yuille, "A regularized solution to edge detection," Tech. Rep. MA, Rep. AIM-833, MIT Artificial Intell. Lab., May 1985.[23] D. L. Ragozin, "Error bounds for derivative estimates based on spline smoothing of exact or noisy data,"J. Approximation Theory, no. 37, pp. 335-355, 1983.[24] C. M. Reinsch, "Smoothing by spline functions,"Numerische Mathematik, vol. 10, pp. 177-183, 1967.[25] I. J. Schoenberg, "Spline functions and tbe problem of graduation,"Proc. Nat. Acad. Sci., vol. 52, pp. 947-950, 1964.[26] B. Shahraray, "Measurement of boundary curvature of quantized shapes: A method based on smoothing spline approximation," Ph.D. dissertation, Dep. Elec. Eng. Comput. Sci., Univ. Michigan, Ann Arbor, 1985.[27] B. Shahraray and D. J. Anderson, "Optimal smoothing of digitized contours," inProc. IEEE Comput. Soc. Conf. Computer Vision and Pattern Recognition, Miami, FL, June 22-26, 1986, pp. 210-218.[28] J. H. Shiau, "Smoothing spline estimation of functions with discontinuities," Ph.D. dissertation, Dep. Stat., Univ. Wisconsin, Madison, 1985.[29] B. W. Silverman, "A fast and efficient cross-validation method for smoothing parameter choice in spline regression,"J. Amer. Stat. Assoc., vol. 79, pp. 584-589, 1984.[30] M. Stone, "Cross-validatory choice and assessment of statistical prediction,"J. Roy. Stat. Soc. Ser. B, vol. 36, no. 2, pp. 111-147, 1974.[31] D. Terzopoulos, "Regularization of inverse visual problems involving discontinuities,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, no. 4, pp. 413-424, July 1986.[32] A. N. Tikhonov, "Regularization of incorrectly posed problems,"Sov. Math. Dokl., vol. 4, pp. 1624-1627, 1963.[33] A. N. Tikhonov and V. Y. Arsenin,Solutions of Ill-Posed Problems. New York: Wiley, 1977.[34] G. Wahba and S. Wold, "A completely automatic french curve: Fitting splines by cross validation,"Commun. Stat., vol. 4, no. 1, pp. 1-17, 1975.[35] G. Wahba and S. Wold, "Periodic splines for spectral density estimation: The use of cross validation for determining the degree of smoothing,"Commun. Stat., vol. 4, no. 2, pp. 125-141, 1975.[36] G. Wahba, "A survey of some smoothing problems and the method of generalized cross-validation for solving them," inApplications of Statistics, P. R. Krishnaiah, Ed. Amsterdam, The Netherlands: North-Holland, 1977, pp. 507-523.[37] G. Wahba, "Ill-posed problems: Numerical and statistical methods for mildy, moderately and severely ill-posed problems with noisy data," Dep. Stat., Univ. Wisconsin, Madison, Tech. Rep. 595, 1980; also inProc. Int. Symp. Ill-Posed Problems, Newark, DE, Oct. 2-6, 1979.[38] G. Wahba, "Constrained regularization for ill-posed linear operator equations with applications in meteorology and medicine," inStatistical Decision Theory and Related Topics III, vol. 2, S. Gupta and J. O. Berger, Eds. New York: Academic, 1982, pp. 383-418.[39] G. Wahba and J. Wendelberger, "Some new mathematical methods for variational objective analysis using splines and cross-validation,"Monthly Weather Rev., vol. 108, pp. 36-57, 1980.[40] G. Wahba, "A comparison of GCV and GML for choosing the smoothing parameter in the generalized spline smoothing problem,"Ann. Stat., vol. 13, no. 4, pp. 1378-1402, 1985.[41] J. Wendelberger, "The computation of Laplacian smoothing splines with examples," Dep. Stat., Univ. Wisconsin, Madison, Tech. Rep. 648, 1981.[42] J. Wendelberger, "Smoothing noisy data with multi-dimensional splines and generalized cross-validation," Ph.D. dissertation, Dep. Stat., Univ. Wisconsin, Madison, 1983.[43] E. T. Whittaker, "On a new method of graduation,"Proc. Edinburgh Math. Soc., vol. 41, pp. 63-75, 1923.[44] Y. Yasumoto and G. Medioni, "Robust estimation of three-dimensional motion parameters from a sequence of image frames using regularization,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, pp. 464-471, 1986.
Index Terms:
parameter estimation; computerised picture processing; pattern recognition; cross-validated regularization; continuous contours; robustness; smoothing spline approximations; curvature; occlusion; computer-vision; computer vision; computerised pattern recognition; filtering and prediction theory; parameter estimation
Citation:
B. Shahraray, D.J. Anderson, "Optimal Estimation of Contour Properties by Cross-Validated Regularization," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 6, pp. 600-610, June 1989, doi:10.1109/34.24794
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||