Введение
Обзор литературы
Глава 1. Анализ существующих подходов и алгоритмов . . . 6
1.1 Алгебраический подход
1.2 Геометрический подход
1.3 Алгоритм 3L
1.4 Алгоритм Левенберга-Марквардта
Глава 2. Предлагаемый подход
Глава 3. Экспериментальные результаты
Заключение
Список литературы
В задачах аппроксимации точечных множеств многообразиями важное место занимает подбор неявных полиномов. Неявные полиномы широко используются в прикладных исследованиях, например, в задачах компьютерного зрения, распознавания или моделирования объектов благодаря
преимуществам перед другими способами представления данных в двумерном и трёхмерном пространствах. В частности, неявные полиномы не требуют параметризации и могут быть получены без предварительного анализа распределения данных, в отличие от сеток или B-сплайнов.
Обычно представление данных в виде неявных полиномов получают в результате процесса подбора (fitting process). Процесс подбора состоит в нахождении такой поверхности в трёхмерном пространстве и кривой в двумерном, которая будет наилучшим образом описывать заданный набор точек. Требуется найти наилучший неявный полином, который описывает заданный набор точек с помощью его корней. Другими словами, многочлен должен равняться нулю в заданных точках.
Пусть fc(X) – неявный многочлен степени d:
fc
(X) =
i+j+k≤d
X
i;j;k≥0
ci;j;k · xi · yj · zk (1)
Или в векторном виде:
fc
(X) = mT c; (2)
где c = [c0;0;0; c1;0;0; :::; c0;0;d]T – это вектор-столбец коэффициентов многочлена, у которого количество элементов равно Cd3+3 = (dd+3)! !3! ;
m – это вектор-столбец мономов, то есть m = m(X) = [x0y0z0; x1y0z0;
:::; x0y0zd]T.
Задача подбора состоит, во-первых, в выборе критерия близости множества корней найденного неявного полинома Zf = fX : fc(X) = 0g к
заданному множеству точек, а затем в минимизации этого критерия для нахождения лучшего вектора коэффициентов c.
2Пусть P = Γ0 = fpigN 1 - множество заданных точек, лежащих в R2
или в R3, тогда формально задачу подборки можно записать в виде:
c^ = arg mincDist(P; fc); (3)
где arg minc обозначает вектор c коэффициентов полинома, при которых выражение Dist (критерий близости, упомянутый выше) достигает минимального значения.
Для нахождения наилучшего вектора коэффициентов c^ можно использовать алгебраический или геометрический подход. Важную роль играет выбор критерия близости Dist(P; fc), который часто основан на применении формул оценки расстояния от точки до кривой или поверхности.
Задача данной работы состоит в применении новой формулы нахождения приближенного расстояния от точки до эллипсоида к задаче подбора неявных полиномов.
В работе выполнено сравнение новой формулы, полученной в результате развития исследований Утешева А.Ю. и Гончаровой М.В., с несколькими известными формулами. Основной упор сделан на работу в R3, так как для трёхмерного пространства, наиболее интересного с точки зрения приложений, известно ограниченное число методов нахождения приближённого расстояния. Была предложена методика сравнения с формированием тестовых данных и проведены количественные измерения по ряду критериев.
