методы аппроксимации/интерполяции

← →
Unknown user © (2007-02-12 18:33) [0]

Какие имеются методы аппроксимации/интерполяции сложных кривых, не непрерывных на всем отрезке, заданных координатами точек, например окружность?

Требуется функция вида: Approximate(const InArray:array of TPoint; var OutArray:array of TPoint; Step:Single);

где Step -шаг точек в выходном массиве.

Математики, помогите :)

← →
Efir © (2007-02-12 20:15) [1]

В - сплайны

← →
PZ (2007-02-12 20:15) [2]

Я не математик, но у меня есть файлы к книге Фаронова Турбо Паскаль 5.5. на интересующую Вас тему. Если хотите, вышлю. 80 кб

← →
Efir © (2007-02-12 20:35) [3]

В принципе у меня есть алгоритм интерполяции методом Лагранжа. Если надо могу скинуть. Также есть алгоритм строящий линии по точкам из кривых Безье.

← →
Дункан (2007-02-13 03:30) [4]

Выложите пожалуйста на http://yourfilelink.com/
Потому, что это может быть интересно многим.

← →
Дункан (2007-02-13 06:16) [5]

Кстати, у кого нибудь есть метод Рунге-Кутта 4 на паскале?

← →
Unknown user © (2007-02-13 10:17) [6]

to PZ & Efir

Да, буду признателен. podgeokart@mail.ru

to Дункан и всем

Я довольно долго искал в инете завершенный, готовый к прктическому применению алгоритм аппроксимации/интерполяции но находил только функции, демонстрирующие работу того или иного метода, которые обычно требовали на входе массив точек, но спотыкались на реальных данных, когда кривая не определяется однозначно y=f(x), например, упомянутая окружность.

Догадываюсь, что кривую надо разбивать на отрезки, или переходить к параметрическому представлению, но как это сделать математически граммотно не знаю.

Неужели никто не стыкался с этой проблемой?

← →
<Efir> (2007-02-13 11:52) [7]

На счёт окружности, тут наверно подойдут только В - сплайны, т.к. в них исп. параметрическое задание кривых. А метод Лагранжа, Ньтона - это если точки графика отсортированы слева направо.

← →
PZ (2007-02-13 13:32) [8]

> [6] Unknown user © (13.02.07 10:17)

Отправил

← →
Sapersky (2007-02-13 14:06) [9]

Относительно просто считаются Catmull-Romm сплайны, но и результат интерполяции несколько хуже, по сравнению с B-Spline.

// Param = 0..1, Dest - результат (2D или 3D точка - определяется FDims)
// Points - опорные точки, FPCount - количество опорных точек,
// FClosed - замкнутая кривая или нет

procedure TBSpline.ValueCatRomm(Param : Single; Dest : PSingle);
var b : integer;
t,t2,t3,pr : Single;

procedure GetPoint(i : Integer; MulValue : Single);
Var i1 : Integer;
begin
i1:=i;
If FClosed then
If i<1 then i1:=i+FPCount else
If i>FPCount then i1:=i-FPCount;
Move(Points[i1]^,FBuf^,FOnePtSize);
VectorMulS(FBuf,MulValue,FDims);
VectorAdd(Dest, FBuf, FDims); // короче, Dest := Dest + Points[i1] * MulValue
end;

begin
ZeroMemory(Dest,FOnePtSize);
If FClosed then pr:=(FPCount)*Param
else pr:=(FPCount-1)*Param;
b:=trunc(pr);

t:=pr-b; t2:=Sqr(t); t3:=t2*t;

// положение каждой результирующей точки считается по 4-м опорным
GetPoint(b-1, -t + 2*t2 - t3);
GetPoint(b, 2 - 5*t2 + 3*t3);
GetPoint(b+1, t + 4*t2 - 3*t3);
GetPoint(b+2, -t2 + t3);
VectorMulS(Dest,0.5,FDims); // Dest := Dest * 0.5
end;

← →
Unknown user © (2007-02-13 19:08) [10]

to PZ

спасибо, буду разбираться

to Sapersky

Спасибо, опробовал предложенную процедуру. первая из тех что я встречал, способная работать с кривыми любого вида. Только в ней не проверяются краевые условия. При Param близком к 0 или 1, индекс Points может выходить за границы. Побольше бы таких готовых решений, можно было бы выбрать наиболее подходящее для конкретной задачи.

Предлагаю в этой ветке выкладывать используемые в практических программах процедуры интерполяции/аппроксимации. Думаю не только мне это сослужит пользу, многим будет интересно посмотреть.

← →
Efir © (2007-02-13 20:30) [11]

> Unknown user ©

Высылаю.

← →
Unknown user © (2007-02-14 11:27) [12]

to Efir

спасибо, получил. отдельное спасибо за статью, первый раз встречаю информацию по интерполяции написанную простым и доходчивым языком, без упрека на то что ты прогулял курс высшей математики...

← →
Sapersky (2007-02-14 15:12) [13]

При Param близком к 0 или 1, индекс Points может выходить за границы

Да, это я недосмотрел, т.к. использовал Catmull-Romm исключительно для замкнутых кривых.
Вот так вроде работает ("правильные" индексы массива точек - от 1 до FPCount):

procedure TBSpline.ValueCatRomm(Param : Single; Dest : PSingle);
var b : integer;
t,t2,t3,pr : Single;

procedure GetPoint(i : Integer; MulValue : Single);
Var i1 : Integer;
begin
i1:=i;
If FClosed then begin
If i1 < 1 then i1 := i1 + FPCount else
If i1 > FPCount then i1 := i1 - FPCount;
end else
If (i1 < 1) then i1 := 1 else
If (i1 > FPCount) then i1 := FPCount;

Move(Points[i1]^, FBuf^, FOnePtSize);
VectorMulS(FBuf, MulValue, FDims);
VectorAdd(Dest, FBuf, FDims);
end;

begin
ZeroMemory(Dest, FOnePtSize);
If (FPCount <= 1 ) then begin
If (FPCount = 1) then Move(Points[1]^, Dest^, FOnePtSize);
Exit;
end;

If FClosed then pr:=(FPCount)*Param else pr:=(FPCount-1)*Param;
b:=trunc(pr);
t:=pr-b; t2:=Sqr(t); t3:=t2*t;

GetPoint(b, -t + 2*t2 - t3);
GetPoint(b+1, 2 - 5*t2 + 3*t3);
GetPoint(b+2, t + 4*t2 - 3*t3);
GetPoint(b+3, -t2 + t3);
VectorMulS(Dest,0.5,FDims);
end;

Кстати, от внятной статьи по B-Spline сам бы не отказался, т.к. до сих пор не понял, можно ли, например, сгенерировать замкнутый B-Spline каким-то менее топорным способом, чем "сдваивание" массива опорных точек. Можно в виде ссылки или выложить на slil.ru или другой подобный сайт.

to Sapersky

спасибо функция действительно работает и не нужно думать о том чтобы цепочка точек была функционально зависимой, то есть везде однозначно определялась функцией y=f(x). хотелось бы еще увидеть алгоритм аппроксимации, работающий для таких же входных данных.

to All

однако проблема которую я поднял при ближайшем рассмотрении оказалась не столь простой и не решается чисто математическими методами, как я думал вначале. наткнулся на нужные мне алгоритмы аппроксимации в исходниках библиотеки OpenCV от Intel (модуль cvapprox.cpp) где используется алгоритм Ramer U. An Iterative Procedure for the Polygonal Approximation of Plane, описание которого я найти не смог, с самой реализацией алгоритма еще тоже не разобрался. существует еще алгоритм Pavlidis Т., Horowitz S. L., Segmentation of Plane Curves описание которого тоже не так посто раздобыть. если кто знаком с данными методами апроксимации кривых, или быть может схожими, поделитесь опытом...

и еще вопрос: кто-то работал с OpenCV в Delphi, существуют ли для этой библиотеки wrappers для вызова функций из Delphi программ?

← →
Sapersky (2007-02-20 15:22) [15]

хотелось бы еще увидеть алгоритм аппроксимации

Что-то я плохо помню, чем аппроксимация от интерполяции отличается. Нашёл: "Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных". Т.е. при аппроксимации не обязана проходить?
Ну так, например, B-сплайны по определению не проходят через контрольные точки, хотя во многих реализациях их "притягивают" к этим точкам:

http://www.torry.net/quicksearchd.php?String=B-Spline&Title=Yes

но это "притяжение" легко отключить (пробовал на своем модуле, который писался на основе какой-то из старых версий этого компонента - просто убирал Interpolate, и получалась "приблизительная" кривая).

Ещё кривые Безье не проходят через контрольные точки.

алгоритм Ramer U. An Iterative Procedure for the Polygonal Approximation of Plane

Нашёл там только "Ramer-Douglas-Peucker algorithm for polygon simplification". Но simplification - это вроде как не то (упрощение ломаной/полигона):
http://www.geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm

кто-то работал с OpenCV в Delphi, существуют ли для этой библиотеки wrappers для вызова функций из Delphi программ?

Я ничего не нашёл, сам конвертировал нужные фрагменты заголовков (не относящиеся к аппроксимации).

to Sapersky

спасибо за помощь. компонент TSpline, действительно работает, но к сожалению, результаты его работы меня не устраивают. для таких входных данных, которые имеются у меня он мало пригоден, его алгоритм хорошо работает для кривых заданных точками с большим шагом и желательно равномерным, у меня же шаг маленький и не всегда постоянный. (могу выслать пример входных данных и того что требуется получить на выходе в формате Excel)

и отдельное спасибо за ссылку на Ramer U. An Iterative Procedure for the Polygonal Approximation of Plane. какие еще есть полезные ресурсы хранящие алгоритмы в области компьютерного зрения? можно ли получить доступ к статьям на сайте IEEE? (платить за каждую статью по 30$ не очень хочется)

← →
Sapersky (2007-02-21 20:28) [17]

какие еще есть полезные ресурсы хранящие алгоритмы в области компьютерного зрения?

http://homepages.inf.ed.ac.uk/rbf/HIPR2/index.htm
http://cgm.graphicon.ru/

← →
Жуков Олег (2007-02-21 20:57) [18]

Вот здесь несколько готовых кодов и алгоритмов
http://local.wasp.uwa.edu.au/~pbourke/other/interpolation/

методы аппроксимации/интерполяции Найти похожие ветки