Как определить кривизну линии?

Question

[anatoly60]

Есть набор точек в двухмерном пространстве, через которые проходит линия. Как определить что линяя не прямая, т.е. определить некий коэффициент кривизны?

Comments

[Mrrl]

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

[anatoly60]

1. прямую от дуги 2. научиться гарантированно отличать друг от друга изображения на примере

Answer 1

[Армянское Радио]

Посчитать коэффициент корелляции Пирсена между X и У этой линии. Чем ближе его модуль к 1, тем больше это похоже на прямую.

Comments

[Mrrl]

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

[Армянское Радио]

Mrrl: Очевидно, что если среднее квадратичное отклонение X или Y около 0, мы имеем дело с прямой линией. Этот случай нужно рассмотреть отдельно.

[Mrrl]

Армянское Радио: Если мы будем поворачивать почти прямую линию вокруг начала координат, то коэффициент корреляции будет меняться от почти единицы (когда линия идёт в направлении (1,1)) до нуля (когда оси координат направлены вдоль осей эллипса инерции) и обратно. Так что при любом пороге она будет оказываться то прямой, то не прямой. Хотя форма меняться не будет.

[Армянское Радио]

Mrrl: Это как это? У почти прямой линии коэффециент корелляции Пирсена между X и Y точек этой же линии никак не зависит от того, как линия наклонена.

Повторяю - мы проверяем гипотезу о линейной зависимости между X и Y.

Проведите эксперимент в Экселе и убедитесь.

[Mrrl]

Армянское Радио: Взял точки:

0 0.1
1 -0.1
2 0.1
3 -0.1
4 0.1

Коэффициент корреляции - 0.
Повернул на 45 гр:

0.070710678 -0.070710678
0.636396103 0.777817459
1.48492424 1.343502884
2.050609665 2.192031022
2.899137803 2.757716447

Коэффициент стал 0.99045.
Так что от наклона зависит.

[Армянское Радио]

Mrrl: Покажите пожалуйста графики этого безобразия

[Mrrl]

Пожалуйста (надеюсь, что загрузилось нормально). Оказалось, что это не поворот, а симметрия, но на корреляцию это не влияет.

[Армянское Радио]

Mrrl: Эксель такой эксель... в первом случае СКО обращается в 0, из чего следует, что знаменатель в формуле коэффициента корреляции становится равным 0. Случай с СКО равным 0 нужно рассматривать отдельно.

[Mrrl]

Армянское Радио: СКО в 0 не обращается. Для X оно равно sqrt(2), для Y - sqrt(6)/25=0.09798. А вот сумма (x-xm)*(y-ym) равна нулю. Так что всё честно.

[Армянское Радио]

Вот же лажа этот коэффициент корреляции Пирсена. Глазами линейную зависимость видно, а оно ноль показывает.

Тогда нужно решать геометрически. Искать методом наименьших квадартов прямую, реализующую наилучшее приближение точек и считать невязки.

[Mrrl]

Это и получится корень из меньшего собственного значения матрицы ковариации. Наилучшее приближение прямой - главная ось эллипса инерции.

Answer 2

[jcmvbkbc]

Может по-простецки сравнить расстояние между начальной и конечной точками с суммой длин всех отрезков ломаной между ними? Если эти значения близки -- значит издалека выглядит как прямая. Если нет -- значит кривая, и чем сильнее разница, тем кривее.

Answer 3

[Rsa97]

Пусть (x₀, y₀) и (x₁, y₁) крайние точки отрезка. Тогда коэффициенты общего уравнения прямой
Аx+By+C = 0
можно определить как
A = y₁-y₀; B = x₀-x₁; C = x₁y₀-x₀y₁
Расстояние от точки (x, y) до прямой
L = |Ax+By+C|/sqtr(A²+B²)
Дальше остаётся определить метрику отклонения, например среднее расстояние от промежуточных точек до отрезка, делённое на длину отрезка

Answer 4

[Mrrl]

Если надо проверить среднее отклонение от прямой, то можно посчитать матрицу ковариации:
xm=sum(x[i])/N; ym=sum(y[i])/N;
a=sum((x[i]-xm)^2); b=sum((x[i]-xm)*(y[i]-ym)); c=sum((y[i]-y0)^2);
и посчитать отношение собственных значений:
R=(a+c-sqrt((a-c)^2+4*b^2)/(a+c+sqrt((a-c)^2+4*b^2).
Если R достаточно мало (скажем, меньше 0.01), то считаем, что это прямая.

Если надо проверить, прямая это или дуга, то берём крайние точки (x0,y0) и (xn,yn). Пусть dx=xn-x0,dy=yn-y0.
Считаем для всех точек
z[i]=((x[i]-x0)*dx+(y[i]-y0)*dy)/sqrt(dx^2+dy^2), w[i]=((x[i]-x0)*dy-(y[i]-y0)*dx)/sqrt(dx^2+dy^2),
Теперь приближаем зависимость w(z) параболой (по методу наименьших квадратов): w=A*z^2+B*z+C. Величина A пропорциональна кривизне дуги, по которой идут точки.

Answer 5

[anatoly60]

Всем огромное спасибо за идеи и предложения. В настоящий момент я решил последовательно считать угол между 3мя точками. Для линии слева угол между любыми тремя точками будет близким к 180.