Как сравнить кривые друг с другом?

[DmitriySidelnikov]

Есть две линии, они дискретны, координаты точек известны: имеем набор точек одной и второй. Линии - одна над другой, т.е. координаты плюс-минус схожие, но количество точек в линиях может быть разным.
Есть эталонная линия, скажем - правая, у неё как видно - 3 точки. Есть дополнительная линия - левая, которую нужно оценить: насколько велико сходство "визуально", не принимая в расчёт количество точек в обоих. Т.е. если у нас есть две идентичные горизонтальные линии, но в эталонной две точки (первая и последняя), а в рассматриваемой - 50 точек, но обе они идеально ровные, стартуют и заканчиваются одинаково - то они 100% визуально схожи.

Количество точек может быть как в эталонной быть больше, чем в рассматриваемой, так и в эталонной быть меньше. Мера сравнения нужно только для "визуального" сходства, не учитывая количества точек. Поворот: критичен; в идеале, одна линия не должна быть повёрнута относительно другой, при наложении друг на друга - визуально должны совпасть, чем меньше совпадают, тем хуже. В двух случаях (линиях) мы имеем только набор точек одной и второй.

[Munin]

Этим целая наука занимается, и даже не одна.

[arseniiv]

Если считать, что вы достаточно описали, что требуется (в чём можно посомневаться), то можно предложить, например, взять площадь фигуры, границей которой будет объединение интересующей и эталонной кривых (если у них совпадают концы). Или площадь выпуклой оболочки этих двух кривых. Или какой-нибудь хитрый интеграл от расстояний точек одной кривой до точек другой.

[Александрович]

DmitriySidelnikov, эталонная кривая всегда прямая линия?

[alcoholist]

в каком виде вам нужен ответ на вопрос

Цитата:

Как сравнить кривые два объекта одной природы друг с другом?

Простейший способ -- найти правило, ставящее в соответствие каждой паре объектов число. Да так, чтобы если число 0, то объекты совпадают. Чем больше число -- тем сильнее отличаются. Или уж хорошее правило: метрику ввести. И метрик таких, как заметил коллега Munin, до фига. Ими целые науки занимаются.

[Vince Diesel]

Вот, например, способ. Параметризовать обе кривые параметром $\psi_1, \psi_2: t\in [0,1]\to \mathbb R^2$ так, чтобы скорость движения по каждой была постоянна и, скажем, "сверху вниз". Поскольку для совмещения допускаются сдвиги на векторы $\bar c=(a,b)$, рассмотреть "невязку"

$$ I(a,b)=\int_0^1|\psi_1(t)-\psi_2(t)-\bar c|^2\,dt $$

$-$ что-то вроде среднего отклонения между кривыми при сдвиге второй на $\bar c$. Далее методом наименьших квадратов найти вектор $\bar c$, для которого невязка минимальна. В качестве меры непохожести взять полученное значение $I$. Или корень из него.

[dsmirnov]

С помощью расстояний Фреше, Хаусдорфа и Хаусдорфа-Громова. Есть даже обобщение расстояния Фреше - т.н. графовое расстояние Фреше, которое позволяет сравнивать графы, ребрам которых соответствуют кривые.

-- 29.11.2016, 17:57 --

Учтите, что для вычисления расстояния Фреше даже при фиксированном положении ломаных из $n$ точек потребуется порядка $n^2$ действий. При поиске аффинного преобразования, минимизирующего расстояние Фреше, потребуется перебрать перестановки проекций точек в при различных аффинных преобразованиях. Таких перестановок намного меньше $n!$ и перебираются они, например, с помощью сортирующих сетей.

[dimkadimon]

Есть несколько идей. Например можно найти самое близкое (или дальнее или среднее) расстояние между двумя кривыми. Для этого надо проверить все расстояния $mn$ между их точками. Проблема этого метода в том что угол кривых не учитывается.

Поэтому предлагаю еще один метод. Каждую кривую можно описать прямой линией (например используя линейную регрессию). Теперь находим расстояние между этими линиями. Если кривые не очень прямые то можно попробовать их описать параболами (тоже через регрессию).