Abstract
To extract geometric primitives from edges, we use an incremental linear-time fitting algorithm, which is based on constructive polynomial fitting. In this work, we propose to determine the polynomial order by observing the regularity and the increase of the fitting cost. When using a fixed polynomial order under- or even overfitting could occur. Second, due to a fixed treshold on the fitting cost, arbitrary endpoints are detected for the segments, which are unsuitable as feature points. We propose to allow a variable segment thickness by detecting discontinuities and irregularities in the fitting cost. Our method is evaluated on the MPEG-7 core experiment CE-Shape-1 database part B [1]. In the experimental results, the edges are approximated closely by the polynomials of variable order. Furthermore, the polynomial segments have robust endpoints, which are suitable as feature points. When comparing adaptive constructive polynomial fitting (ACPF) to non-adaptive constructive polynomial fitting (NACPF), the average Hausdorff distance per segment decreases by 8.85% and the object recognition rate increases by 10.24%, while preserving simplicity and computational efficiency.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jeannin, S., Bober, M.: Description of core experiments for mpeg-7 motion/shape, Technical Report ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690 (1999)
Dorst, L., Smeulders, A.W.M.: Length estimators for digitized contours. Computer Vision, Graphics, and Image Processing 40(3), 311–333 (1987)
Debled-Rennesson, I., Reveills, J.-P.: A Linear Algorithm for Segmentation of Digital Curves. Int. J. of Pattern Recognition and Artificial Intelligence 9(4), 635–662 (1995)
Buzer, L.: An Incremental Linear Time Algorithm for Digital Line and Plane Recognition Using a Linear Incremental Feasibility Problem. In: Braquelaire, A., Lachaud, J.-O., Vialard, A. (eds.) DGCI 2002. LNCS, vol. 2301, pp. 372–381. Springer, Heidelberg (2002)
Piegl, L.: On NURBS: A Survey. IEEE Computer Graphics and Applications 11(1), 55–71 (1991)
Goshtasby, A.: Design and Recovery of 2D and 3D Shapes Using Rational Gaussian Curves and Surfaces. International Journal of Computer Vision 10(3), 233–256 (1993)
Turk, G., O’Brien, J.F.: Variational Implicit Surfaces. Technical Report GIT-GVU-99-15, Graphics, Visualization, and Usability Center, Georgia Technical Univ. (1999)
Taubin, G.: Estimation of Planar Curves, Surfaces and Nonplanar Space Curves Defined by Implicit Equations, with Applications to Edge and Range Image Segmentation. IEEE Trans. PAMI 13(11), 1115–1138 (1991)
Blane, M.M., Lei, Z., Civi, H., Cooper, D.B.: The 3L Algorithm for Fitting Implicit Polynomial Curves and Surfaces to Data. IEEE Trans. PAMI 22(3), 298–313 (2000)
Sahin, T., Unel, M.: Stable Algebraic Surfaces for 3D Object Representation. Journal of Mathematical Imaging and Vision 32(2), 127–137 (2008)
Keren, D., Gotsman, C.: Fitting Curves and Surfaces with Constrained Implicit Polynomials. IEEE Trans. PAMI 21(1), 31–41 (1999)
Keren, D.: Topologically Faithful Fitting of Simple Closed Curves. IEEE Trans. PAMI 26(1), 118–123 (2004)
Tasdizen, T., Tarel, J., Cooper, D.: Improving the Stability of Algebraic Curves for Applications. IEEE Trans. Image Processing 9(3), 405–416 (2000)
Helzer, A., Barzohar, M., Malah, D.: Stable Fitting of 2D Curves and 3d Surfaces by Implicit Polynomials. IEEE Trans. PAMI 26(10), 1283–1294 (2004)
Veelaert, P., Teelen, K.: Fast polynomial segmentation of digitized curves. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds.) DGCI 2006. LNCS, vol. 4245, pp. 482–493. Springer, Heidelberg (2006)
Deboeverie, F., Veelaert, P., Teelen, K., Philips, W.: Face Recognition Using Parabola Edge Map. In: Blanc-Talon, J., Bourennane, S., Philips, W., Popescu, D., Scheunders, P. (eds.) ACIVS 2008. LNCS, vol. 5259, pp. 994–1005. Springer, Heidelberg (2008)
Deboeverie, F., Teelen, K., Veelaert, P., Philips, W.: Vehicle tracking using geometric features. In: Blanc-Talon, J., Philips, W., Popescu, D., Scheunders, P. (eds.) ACIVS 2009. LNCS, vol. 5807, pp. 506–515. Springer, Heidelberg (2009)
Canny, J.F.: A computational approach to edge detection. IEEE Trans. PAMI, 679–698 (1986)
Yang, X., Koknar-Tezel, S., Latecki, L.J.: Locally Constrained Diffusion Process on Locally Densified Distance Spaces with Applications to Shape Retrieval. In: CVPR, pp. 357–364 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Deboeverie, F., Teelen, K., Veelaert, P., Philips, W. (2010). Adaptive Constructive Polynomial Fitting. In: Blanc-Talon, J., Bone, D., Philips, W., Popescu, D., Scheunders, P. (eds) Advanced Concepts for Intelligent Vision Systems. ACIVS 2010. Lecture Notes in Computer Science, vol 6474. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17688-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-17688-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17687-6
Online ISBN: 978-3-642-17688-3
eBook Packages: Computer ScienceComputer Science (R0)