×

Three points method for searching the best least absolute deviations plane. (English) Zbl 1176.65017

A new method for estimating optimal parameters of a best least absolute deviations (LAD) plane is proposed, which is based on the fact that there always exists a best LAD plane passing through at least three different data points. A modification to the foregoing method is also proposed, that is especially adjusted to the case of a large number of data and the need to estimate parameters in real time [cf. M. A. Fischler et al., Graphics Image Process. 24, 381–395 (1981)]. These methods are illustrated and tested on several numerical examples.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Software:

KELLEY
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bloomfield, P.; Steiger, W., Least Absolute Deviations: Theory Applications and Algorithms (1983), Birkhauser: Birkhauser Boston · Zbl 0536.62049
[2] Brimberg, J.; Juel, H.; Schöbel, A., Properties of three-dimensional median line location models, Ann. Operat. Res., 122, 71-85 (2003) · Zbl 1038.90047
[3] D. Burschka, S. Lee, G. Hager, Stereo-based obstacle avoidance in indoor environments with active sensor re-calibration, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, USA, 2002, pp. 2066-2072.; D. Burschka, S. Lee, G. Hager, Stereo-based obstacle avoidance in indoor environments with active sensor re-calibration, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, USA, 2002, pp. 2066-2072.
[4] Castillo, E.; Mínguez, R.; Castillo, C.; Cofinño, A. S., Dealing with the multiplicity of solutions of the \(l_1\) and \(l_\infty\) regression models, European J. Oper. Res., 188, 460-484 (2008) · Zbl 1149.90369
[5] J. Corso, D. Burschka, G. Hager, Direct plane tracking in stereo images for mobile navigation, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, 2003, pp. 875-880.; J. Corso, D. Burschka, G. Hager, Direct plane tracking in stereo images for mobile navigation, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, 2003, pp. 875-880.
[6] R. Cupec, Scene reconstruction and free space representation for biped walking robots, Dr. Ing. Dissertation TU München, Fortschritt-Berichte VDI Reihe 8 Nr. 1066. Düsseldorf: VDI-Verlag, 2005.; R. Cupec, Scene reconstruction and free space representation for biped walking robots, Dr. Ing. Dissertation TU München, Fortschritt-Berichte VDI Reihe 8 Nr. 1066. Düsseldorf: VDI-Verlag, 2005.
[7] Demidenko, E. Z., Optimization and Regression (1989), Nauka: Nauka Moscow, (in Russian) · Zbl 0675.65060
[8] Y. Dodge (Ed.), Statistical data analysis based on the \(L_1 L_1\); Y. Dodge (Ed.), Statistical data analysis based on the \(L_1 L_1\)
[9] Faugeras, O., Three-Dimensional Computer Vision: A Geometric Viewpoint (1993), Cambridge, The MIT Press: Cambridge, The MIT Press Massachusetts
[10] Fischler, M. A.; Bolles, R. C., Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Graphics Image Process., 24, 381-395 (1981)
[11] Gurwitz, C., Weighted median algorithms for \(L_1\) approximation, BIT, 30, 301-310 (1990) · Zbl 0704.65044
[12] Hadeler, K. P.; Jukić, D.; Sabo, K., Least squares problems for Michaelis Menten kinetics, Math. Methods Appl. Sci., 30, 1231-1241 (2007) · Zbl 1114.92035
[13] Kelley, C. T., Iterative Methods for Optimization (1999), SIAM: SIAM Philadelphia · Zbl 0934.90082
[14] K. Konolige, Small vision systems: hardware and implementation in robotics research, in: The Eighth International Symposium, Springer-Verlag, 1997, pp. 203-212.; K. Konolige, Small vision systems: hardware and implementation in robotics research, in: The Eighth International Symposium, Springer-Verlag, 1997, pp. 203-212.
[15] Korneenko, N. M.; Martini, H., Hyperplane approximation and related topics, (Pach, J., New Trends in Discrete and Computational Geometry (1993), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0809.52013
[16] Lewvis, R. M.; Torczon, V.; Trosset, M. W., Direct search methods: then and now, J. Comput. Appl. Math., 124, 191-207 (2000) · Zbl 0969.65055
[17] Li, Y., A maximum likelihood approach to least absolute deviation regression, EURASIP J. Appl. Signal Process., 12, 1762-1769 (2004)
[18] K. Okada, S. Kagami, M. Inaba, H. Inoue, Plane segment finder: algorithm, implementation and applications, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, 2001, pp. 2120-2125.; K. Okada, S. Kagami, M. Inaba, H. Inoue, Plane segment finder: algorithm, implementation and applications, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, 2001, pp. 2120-2125.
[19] Osborne, M. R., Finite Algorithms in Optimization and Data Analysis (1985), Wiley: Wiley Chichester · Zbl 0573.65044
[20] Pinkus, A., On \(L^1\)-approximation (1993), Cambridge University Press: Cambridge University Press New York
[21] K. Sabo, R. Scitovski, The best least absolute deviations line – properties and two efficient methods, ANZIAM Journal, in press.; K. Sabo, R. Scitovski, The best least absolute deviations line – properties and two efficient methods, ANZIAM Journal, in press. · Zbl 1182.65023
[22] Schöbel, A., Locating Lines and Hyperplanes: Theory and Algorithms (1999), Springer-Verlag: Springer-Verlag Berlin · Zbl 0918.90102
[23] Schöbel, A., Anhored hyperplane location problems, Discrete Comput. Geometry, 29, 229-238 (2003) · Zbl 1032.90017
[24] Scitovski, R.; Ungar, Š.; Jukić, D., Approximating surface by moving total least squares method, Appl. Math. Comput., 93, 219-232 (1998) · Zbl 0943.65026
[25] Se, S.; Brady, M., Ground plane estimation error analysis and applications, Robot. Auton. Syst., 39, 59-71 (2002)
[26] Späth, H.; Watson, G. A., On orthogonal linear \(l_1\) approximation, Numer. Math., 51, 531-543 (1987) · Zbl 0633.65010
[27] Tarantola, A., Inverse Problem Theory and Methods for Model Parameter Estimation (2005), SIAM: SIAM Philadelphia · Zbl 1074.65013
[28] Wang, Z.; Peterson, B. S., Constrained least absolute deviation neural networks, IEEE Trans. Neural Networks, 19, 273-283 (2008)
[29] Watson, G. A., On the Gauss-Newton method for \(l_1\) orthogonal distance regression, IMA J. Num. Anal., 22, 345-357 (2002) · Zbl 1017.65004
[30] Watson, G. A., Approximation Theory and Numerical Methods (1980), Wiley: Wiley Chichester · Zbl 0442.65005
[31] Wesolowsky, G. O., A new descent algorithm for the least absolute value regression problem, Commun. Stat. Simulat. Comput., B10, 479-491 (1981) · Zbl 0463.65096
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.