ГРНТИ 50.07 Теоретические основы вычислительной техники
ББК 3297 Вычислительная техника
В работе описано применение новой формулы нахождения приближенного расстояния от точки до алгебраического многообразия в геометрическом подходе к подбору кривых и реконструкции поверхностей с помощью неявных алгебраических многообразий. Приведен краткий обзор особенностей методов подбора неявных алгебраических многообразий. Для иллюстрации возможностей новой формулы нахождения приближенного расстояния приведены изоконтуры точного расстояния, расстояния Самсона и оригинальной формулы. Предложен четырехшаговый алгоритм подбора неявных алгебраических многообразий, использующий один из алгебраических методов подбора на начальном шаге, оригинальную формулу нахождения расстояния для вычисления геометрического критерия качества приближения и оптимизационный метод для обновления значения вектора коэффициентов подбираемого многообразия. Кратко охарактеризованы первые результаты работы преложенного алгоритма на тестовых данных. В заключении описаны требующие решения задачи и направления для продолжения исследований.
расстояние, приближенное расстояние, неявные алгебраические многообразия, подбор кривых и поверхностей
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.
