Distance regression by Gauss-Newton-type methods and iteratively re-weighted least-squares. (English) Zbl 1183.65014

Aigner, Martin; Jüttler, Bert

Computing 86, No. 2-3, 73-87 (2009).

A generalized problem of fitting a curve or surface to given measurement data is presented. The solution is focused on the situations when the usual least-squares approach is not suitable. The generalization of the fitting problem lies in minimizing the sum of the so called norm-like functions applied to the residual vectors that connect the measured points with associated points on the fitted curve or surface. This approach represents an extension of the iteratively re-weighted least-squares method (Gauss-Newton-type method) for minimizing a sum of norm-like functions of scalar residuals. The obtained results can be used in various applications of computational geometry – reconstruction of geometric models from point cloud data, regression analysis, image segmentation, pattern recognition, etc.

Reviewer: Ivana Linkeová (Praha)

MSC:

65D10	Numerical smoothing, curve fitting
65F20	Numerical solutions to overdetermined systems, pseudoinverses
65D18	Numerical aspects of computer graphics, image analysis, and computational geometry
62J05	Linear regression; mixed models
65C60	Computational problems in statistics (MSC2010)
68T10	Pattern recognition, speech recognition

Keywords:

curve fitting; surface fitting; least-squares; iteratively re-weighted least squares; Gauss-Newton method; computational geometry; regression analysis; image segmentation; pattern recognition

Software:

KELLEY

References:

[1]	Aigner M, Jüttler B (2007) Approximation flows in shape manifolds. In: Chenin P, Lyche T, Schumaker L (eds) Curve and surface design: Avignon 2006, Nashboro Press, pp 1–10
[2]	Aigner M, Šír Z, Jüttler B (2007) Evolution-based least-squares fitting using Pythagorean hodograph spline curves. Comput Aided Geom Des 24: 310–322 · Zbl 1171.65315 · doi:10.1016/j.cagd.2007.04.001
[3]	Al-Subaihi I, Watson GA (2004) The use of the l 1 and l norms in fitting parametric curves and surfaces to data. Appl Numer Anal Comput Math 1: 363–376 · Zbl 1071.65012 · doi:10.1002/anac.200410004
[4]	Alhanaty M, Bercovier M (2001) Curve and surface fitting and design by optimal control methods. Comput Aided Des 33: 167–182 · Zbl 1206.65043 · doi:10.1016/S0010-4485(00)00089-0
[5]	Atieg A, Watson GA (2003) A class of methods for fitting a curve or surface to data by minimizing the sum of squares of orthogonal distances. J Comput Appl Math 158: 277–296 · Zbl 1034.65007 · doi:10.1016/S0377-0427(03)00448-5
[6]	Blake A, Isard M (1998) Active contours. Springer, New York
[7]	Boggs PT, Byrd RH, Schnabel RB (1987) A stable and efficient algorithm for nonlinear orthogonal distance regression. J Sci Stat Comput 8(6): 1052–1078 · Zbl 0637.65150 · doi:10.1137/0908085
[8]	Bube KP, Langan RT (1997) Hybrid 1/ 2 minimization with application to tomography. Geophysics 62: 1183–1195 · doi:10.1190/1.1444219
[9]	Holland P, Welsch R (1977) Robust regression using iteratively re-weighted least-squares. Commun Stat Theory Methods 9(A6): 813–827 · Zbl 0376.62035
[10]	Hoschek J, Lasser D (1993) Fundamentals of computer aided geometric design. A K Peters, Wellesley · Zbl 0788.68002
[11]	Huber PJ (1981) Robust statistics. Wiley, New York · Zbl 0536.62025
[12]	Jüttler B (1998) Computational methods for parametric discrete 1 and curve fitting. Int J Shape Model 4: 21–34 · Zbl 0963.68208 · doi:10.1142/S0218654398000039
[13]	Kelley CT (1999) Iterative methods for optimization. Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0934.90082
[14]	Liu Y, Wang W (2008) A revisit to least squares orthogonal distance fitting of parametric curves and surfaces. In: Chen F, Jüttler B (eds) Advances in geometric modeling and processing, GMP 2008, Springer, pp 384–397
[15]	Mahadevan V, Narasimha-Iyer H, Roysam B, Tanenbaum HL (2004) Robust model-based vasculature detection in noisy biomedical images. IEEE Trans Inf Technol Biomed 8(3): 360–376 · doi:10.1109/TITB.2004.834410
[16]	McCullagh P, Nelder J (1998) Generalized linear models. Chapman & Hall, London · Zbl 0588.62104
[17]	Osborne MR (1985) Finite algorithms in optimization and data analysis. Wiley, New York · Zbl 0573.65044
[18]	Pottmann H, Leopoldseder S, Hofer M, Steiner T, Wang W (2005) Industrial geometry: recent advances and applications in CAD. Comput Aided Des 37: 751–766 · doi:10.1016/j.cad.2004.08.013
[19]	Rogers D, Fog N (1989) Constrained B-spline curve and surface fitting. Comput Aided Des 21: 641–648 · Zbl 0687.65008 · doi:10.1016/0010-4485(89)90162-0
[20]	Sarkar B, Menq CH (1991) Parameter optimization in approximating curves and surfaces to measurement data. Comput Aided Geom Des 8: 267–280 · Zbl 0746.65016 · doi:10.1016/0167-8396(91)90016-5
[21]	Speer T, Kuppe M, Hoschek J (1998) Global reparametrization for curve approximation. Comput Aided Geom Des 15: 869–877 · Zbl 0910.68214 · doi:10.1016/S0167-8396(98)00024-7
[22]	Wang W, Pottmann H, Liu Y (2006) Fitting B-spline curves to point clouds by curvature-based squared distance minimization. ACM Trans Graph 25(2): 214–238 · doi:10.1145/1138450.1138453
[23]	Watson GA (2000) Approximation in normed linear spaces. J Comput Appl Math 121: 1–36 · Zbl 0964.41020 · doi:10.1016/S0377-0427(00)00333-2
[24]	Watson GA (2001) On the Gauss–Newton method for 1 orthogonal distance regression. IMA J Num Anal 22: 345–357 · Zbl 1017.65004 · doi:10.1093/imanum/22.3.345
[25]	Wedderburn RWM (1974) Quasi-likelihood functions, generalized linear models, and the Gauss– Newton method. Biometrika 61(3): 439–447 · Zbl 0292.62050
[26]	Yamamoto T (2000) Historical developments in convergence analysis for Newton’s and Newton-like methods. J Comput Appl Math 124(1/2): 1–23 · Zbl 0965.65079 · doi:10.1016/S0377-0427(00)00417-9