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

[Nuzhny 243]

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

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

[Pavia00 32]

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

[Pavia00 32]

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

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

 

[Smorodov 578]

С регуляризацией: 

https://ardianumam.wordpress.com/2017/09/22/deriving-polynomial-regression-with-regularization-to-avoid-overfitting/

[Nuzhny 243]

1 hour ago, Pavia00 said:

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

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

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

[Pavia00 32]

2 часа назад, Nuzhny сказал:

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

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

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

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

[Smorodov 578]

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

 

[Nuzhny 243]

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

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