GRNTI 50.07 Теоретические основы вычислительной техники
BBK 3297 Вычислительная техника
The application of a new approximate point-to-algebraic manifold distance formula is suggested to the geometric approach to curve fitting and surface reconstruction using implicit polynomial manifolds. A brief overview of the fitting methods features for implicit algebraic manifolds is given. To illustrate the possibilities of a new approximate point-to-manifold distance formula, the equidistant curves of the exact distance, Samson’s distance and the present formula are given. A four-step algorithm for implicit algebraic manifold fitting is proposed, using one of the algebraic fitting methods at the initial step, the present approximate formula for the distance finding to calculate the geometric criterion of approximation quality and an optimization method for updating the value of the vector of coefficients of the manifold. The first results of the proposed algorithm on test data are briefly characterized. In conclusion, the tasks and directions for further research are described.
distance, distance approximation, implicit polynomial manifold, curve and surface fitting
1. S. Ahn, W.Rauh, H. Cho, and H. Warnecke, Orthogonal Distance Fitting of Implicit Curves and Surfaces. IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, no. 5, pp. 620-638, 2002.
2. M. Aigner and B. Jutler, Gauss-Newton-type Technique for Robustly Fitting Implicit Defined Curves and Surfaces to Unorganized Data Points. Proc. IEEE Int. Conf. Shape Model. Appl., New York, pp. 121-130, 2009.
3. M. Blane, Z. Lei, H. Civil, and D. Cooper, The 3L Algorithm for Fitting Implicit Polynomials Curves and Surface to Data. IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 3, pp. 298-313, 2000.
4. S.-W. Cheng and M.-K. Chiu, Implicit Manifold Reconstruction. Proceedings of the TwentyFifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 161-173, 2014.
5. R. Fletcher, Practical Methods of Optimization, 2nd ed. New York: Wiley, 1990.
6. A. Gomes, I. Voiculescu, J. Jorge, B. Wyvill, and C. Galbraith, Implicit Curves and Surfaces: Mathematics, Data Structures and Algorithms. 1st ed. SpringerVerlag London, 2009.
7. R. Interian, J. Otero, C. Ribeiro, and A. Montenegro, Curve and Surface Fitting by Implicit Polynomials: Optimum Degree Finding and Heuristic Refinement. Comp. Graph., vol. 67, pp. 14-23, 2017.
8. M. Rouhani and A. Sappa, Implicit Polynomial Representation Through a Fast Fitting Error Estimation. IEEE Trans. Image Process., vol. 21, pp. 2089-2098, 2011.
9. P. Sampson, Fitting Conic Sections to Very Scattered Data: an Iterative Refinement of the Bookstein Algorithm. Comput. Gr. Image Process., vol. 18, pp. 97-108, 1982.
10. G. Taubin, Estimation of Planar Curves, Surfaces, and Nonplanar Space Curves Defined by Implicit Equations with Applications to Edge and Range Image Segmentation.IEEE Trans. Pattern Anal. Mach. Intell., vol. 13, no. 11, pp. 1115-1138, 2002.
11. G. Taubin, Distance Approximations for Rasterizing Implicit Curves. ACM Trans. Graph., vol. 13, no. 1, pp. 3-42, 1994.
12. G. Taubin, F. Cukierman, S. Sullivan, J. Ponce, and D. Kreigman, Parameterized Families of Polynomials for Bounded Algebraic Curve and Surface Fitting. IEEE Trans. Pattern Anal. Mach. Intell., vol. 16, pp. 287-303, 1994.
13. A. Uteshev and M. Goncharova, Metric Problems for Algebraic Manifolds: Analytical Approach. Constructive Nonsmooth Analysis and Related Topics (Dedicated to the Memory of V.F. Demyanov), CNSA 2017 - Proceedings, 7974027, 2017.
14. A. Uteshev and M. Goncharova, Point-to-Ellipse and Point-to-Ellipsoid Distance Equation Analysis. J.Comput. Appl. Math., vol. 328, pp. 232-251, 2018.
15. A. Uteshev and M. Goncharova, Approximation of the Distance from a Point to an Algebraic Manifold. Proceedings of the 8th International Conference on Pattern Recognition Applications and Methods - Vol. 1: ICPRAM, pp. 715-720, 2019.
16. A. Uteshev and M. Yashina, Metric Problems for Quadrics in Multidimensional Space. J.Symbolic Computation, vol. 68, no. 1, pp. 287-315, 2015.