Jump to content
Compvision.ru
Nuzhny

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

Recommended Posts

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

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

Share this post


Link to post
Share on other sites

Нету, так как такая операция для кривовй уже на 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

Share this post


Link to post
Share on other sites

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

// МНК для полинома 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;

 

Share this post


Link to post
Share on other sites
1 hour ago, Pavia00 said:

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

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

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

Share this post


Link to post
Share on other sites
2 часа назад, Nuzhny сказал:

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

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

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

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

Share this post


Link to post
Share on other sites

Я пока попробовал 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).

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×