Abstract
We overview techniques for optimal geometric estimation from noisy observations for computer vision applications. We first describe estimation techniques based on minimization of given cost functions: least squares (LS), maximum likelihood (ML), which includes reprojection error minimization (Gold Standard) as a special case, and Sampson error minimization. We then formulate estimation techniques not based on minimization of any cost function: iterative reweight, renormalization, and hyper-renormalization. Showing numerical examples, we conclude that hyper-renormalization is robust to noise and currently is the best method.
Chapter PDF
Similar content being viewed by others
Keywords
- Mahalanobis Distance
- Generalize Eigenvalue Problem
- Bundle Adjustment
- Total Little Square
- Geometric Estimation
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Al-Sharadqah, A., Chernov, N.: A doubly optimal ellipse fit. Comp. Stat. Data Anal. 56(9), 2771–2781 (2012)
Bartoli, A., Sturm, P.: Nonlinear estimation of fundamental matrix with minimal parameters. IEEE Trans. Patt. Anal. Mach. Intell. 26(3), 426–432 (2004)
Chernov, N., Lesort, C.: Statistical efficiency of curve fitting algorithms. Comp. Stat. Data Anal. 47(4), 713–728 (2004)
Chojnacki, W., Brooks, M.J., van den Hengel, A.: Rationalising the renormalization method of Kanatani. J. Math. Imaging Vis. 21(11), 21–38 (2001)
Chojnacki, W., Brooks, M.J., van den Hengel, A., Gawley, D.: On the fitting of surfaces to data with covariances. IEEE Trans. Patt. Anal. Mach. Intell. 22(11), 1294–1303 (2000)
Godambe, V.P. (ed.): Estimating Functions. Oxford University Press, New York (1991)
Hartley, R., Kahl, F.: Optimal algorithms in multiview geometry. In: Proc. 8th Asian Conf. Comput. Vis., Tokyo, Japan, vol. 1, pp. 13–34 (November 2007)
Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press, Cambridge (2004)
Kahl, F., Agarwal, S., Chandraker, M.K., Kriegman, D., Belongie, S.: Practical global optimization for multiview geometry. Int. J. Comput. Vis. 79(3), 271–284 (2008)
Kanatani, K.: Renormalization for unbiased estimation. In: Proc. 4th Int. Conf. Comput. Vis., Berlin, Germany, pp. 599–606 (May 1993)
Kanatani, K.: Statistical Optimization for Geometric Computation: Theory and Practice. Elsevier, Amsterdam (1996); reprinted, Dover, New York (2005)
Kanatani, K.: Cramer-Rao lower bounds for curve fitting. Graphical Models Image Process. 60(2), 93–99 (1998)
Kanatani, K.: Ellipse fitting with hyperaccuracy. IEICE Trans. Inf. & Syst. E89-D(10), 2653–2660 (2006)
Kanatani, K.: Statistical optimization for geometric fitting: Theoretical accuracy analysis and high order error analysis. Int. J. Comput. Vis. 80(2), 167–188 (2008)
Kanatani, K., Al-Sharadqah, A., Chernov, N., Sugaya, Y.: Renormalization Returns: Hyper-renormalization and Its Applications. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) ECCV 2012, Part III. LNCS, vol. 7574, pp. 384–397. Springer, Heidelberg (2012)
Kanatani, K., Rangarajan, P.: Hyper least squares fitting of circles and ellipses. Comput. Stat. Data Anal. 55(6), 2197–2208 (2011)
Kanatani, K., Rangarajan, P., Sugaya, Y., Niitsuma, H.: HyperLS and its applications. IPSJ Trans. Comput. Vis. Appl. 3, 80–94 (2011)
Kanatani, K., Sugaya, Y.: Performance evaluation of iterative geometric fitting algorithms. Comp. Stat. Data Anal. 52(2), 1208–1222 (2007)
Kanatani, K., Sugaya, Y.: Compact algorithm for strictly ML ellipse fitting. In: Proc. 19th Int. Conf. Patt. Recog., Tampa, FL, U.S.A (December 2008)
Kanatani, K., Sugaya, Y.: Compact fundamental matrix computation. IPSJ Tran. Comput. Vis. Appl. 2, 59–70 (2010)
Kanatani, K., Sugaya, Y.: Unified computation of strict maximum likelihood for geometric fitting. J. Math. Imaging Vis. 38(1), 1–13 (2010)
Leedan, Y., Meer, P.: Heteroscedastic regression in computer vision: Problems with bilinear constraint. Int. J. Comput. Vis. 37(2), 127–150 (2000)
Lourakis, M.I.A., Argyros, A.A.: SBA: A software package for generic sparse bundle adjustment. ACM Trans. Math. Software 36(1), 2, 1–30 (2009)
Matei, J., Meer, P.: Estimation of nonlinear errors-in-variables models for computer vision applications. IEEE Trans. Patt. Anal. Mach. Intell. 28(10), 1537–1552 (2006)
Okatani, T., Deguchi, K.: On bias correction for geometric parameter estimation in computer vision. In: Proc. IEEE Conf. Comput. Vis. Patt. Recog., Miami Beach, FL, U.S.A, pp. 959–966 (June 2009)
Okatani, T., Deguchi, K.: Improving accuracy of geometric parameter estimation using projected score method. In: Proc. Int. Conf. Comput. Vis., Kyoto, Japan, pp. 1733–1740 (September/October 2009)
Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes in C: The Art of Scientific Computing, 2nd edn. Cambridge University Press, Cambridge (1992)
Rangarajan, P., Kanatani, K.: Improved algebraic methods for circle fitting. Electronic J. Stat. 3, 1075–1082 (2009)
Sampson, P.D.: Fitting conic sections to “very scattered” data: An iterative refinement of the Bookstein algorithm. Comput. Graphics Image Process. 18(1), 97–108 (1982)
Sturm, P., Gargallo, P.: Conic fitting using the geometric distance. In: Proc. 8th Asian Conf. Comput. Vis., Tokyo, Japan, vol. 2, pp. 784–795 (November 2007)
Taubin, G.: Estimation of planar curves, surfaces, and non-planar space curves defined by implicit equations with applications to edge and range image segmentation. IEEE Trans. Patt. Anal. Mach. Intell. 13(11), 1115–1138 (1991)
Triggs, B., McLauchlan, P.F., Hartley, R.I., Fitzgibbon, A.W.: Bundle Adjustment – A Modern Synthesis. In: Triggs, B., Zisserman, A., Szeliski, R. (eds.) ICCV-WS 1999. LNCS, vol. 1883, pp. 298–375. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kanatani, K. (2012). Optimization Techniques for Geometric Estimation: Beyond Minimization. In: Gimel’farb, G., et al. Structural, Syntactic, and Statistical Pattern Recognition. SSPR /SPR 2012. Lecture Notes in Computer Science, vol 7626. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34166-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-34166-3_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34165-6
Online ISBN: 978-3-642-34166-3
eBook Packages: Computer ScienceComputer Science (R0)