Перейти к содержимому
Compvision.ru
Nuzhny

Least squares fitting или метод наименьших квадратов

Recommended Posts

Приветствую!

А в OpenCV есть что-нибудь для аппроксимации набора точек полиномом произвольной степени? Есть fitLine для прямой, а что-то большее?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Нету, так как такая операция для кривовй уже на 5-7 степени упирается в точность Single.

По этмоу лучше использовать сплайны и кривые Безье.

 

Что есть в OpenCV?

Строим контур цепным кодом из него, получаем полигон путем оптимизации approxpolydp

https://docs.opencv.org/2.4/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html#approxpolydp

 

Тут лучше староннее что-то использовать к примеру

https://www.alglib.net/translator/man/manual.cpp.html#sub_spline1dfitpenalizedw

И для полиномов там тоже есть

https://www.alglib.net/translator/man/manual.cpp.html#sub_polynomialfit

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Да и самому не трудно написать.
 

// МНК для полинома B[0]+B[1]*x+B[2]*x^2+...+B[p]*x^p=y
// p -степень полинома
// Входные параметры:
// - точки в виде масивов их координат x,y
// - степень желаемого полинома p
// Выходные параметры:
// - коэффициенты полинома B
procedure PolyFit(y,x:TArrayReal; p:Integer; var B:TArrayReal);
var
  a,at,temp:TMatrixNM;
  Temp2:TMatrixNN;
  i,j,N:Integer;
  c:Real;
begin
if (Length(y)<>Length(x)) or (p<0) then exit;
N:=Length(Y);

// Минимизация коэффициентов полинома методом наименьших квадратов.

// Строим матрицу Вандерморда
SetLength(A,N,p+1);
for i:=0 to N-1 do
 begin
 c:=1;
 for j:=0 to P do
  begin
  a[i,j]:=c;
  c:=c*x[i];
  end;
 end;

// Применяем метод Moore–Penrose
at:=Transpose(A);

Temp2:=MatrixMulMatrix(At,A);
Temp:=Invert(Temp2);
B:=MatrixMulVector(MatrixMulMatrix(Temp,At),Y);

end;

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 hour ago, Pavia00 said:

Нету, так как такая операция для кривовй уже на 5-7 степени упирается в точность Single.

Всегда можно взять и double, если придётся (но вряд ли точности не хватит). Сплайны и Безье - это не то, что мне надо. Я бы хотел из траектории движения объекта за несколько секунд (скажем, 100 кадров) получить уравнение движения. Логично получить кубическое, чтобы ускорение тоже было не константным. Теоретически, в OpenCV это можно сдлать через Levenberg-Marquardt solver (cv::LMSolver), можно взять ceres solver, но там везде надо дописывать свои целевые функции. Или что-то с Гитхаба специализированное. Не сильно хочется самому тянуть дополнительные зависимости для, казалось бы, вполне типичной задачи.

За ссылки спасибо, посмотрю, потестирую, как оно работает.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 часа назад, Nuzhny сказал:

Сплайны и Безье - это не то, что мне надо. Я бы хотел из траектории движения объекта за несколько секунд (скажем, 100 кадров) получить уравнение движения. Логично получить кубическое, чтобы ускорение тоже было не константным.

Это меняет задачу.  В 3 строчки не сделать. Но прежде хочу сказать, следующее вам нужны именно Безье. Кривая Безье - это система из 2-х кубических полиномов. В противном случае будете иметь вот такие вот проблемы

https://forum.sources.ru/index.php?showtopic=416325&st=0&#entry3815075

Что касается вашей задачи. Набор данных надо сгладить  и вычислить производную найти участок с не более  2-мя изменениями знака производной.  Остальные выкинуть.  Использовать метод вернее эвристику максимального правдоподобия для улучшения МНК. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Просто чтобы не терялось: https://github.com/andrewwillmott/splines-lib

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я пока попробовал 2 репозитория (пока лень самому писать):

1. https://jugit.fz-juelich.de/mlz/lmfit

2. https://github.com/yinzixuan126/polynomial_fitting/blob/master/src/polyfit_node.cpp

Первый (Левенберга-Марквардта) работает точнее, второй быстрее. Нашёл ещё, но не пробовал ( https://github.com/gpufit/Gpufit, https://github.com/wojdyr/fityk).

Потестирую, если будет медренно, то надо будет реализовывать самому и оптимизировать.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×