2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Как сравнить кривые друг с другом?
Сообщение01.09.2016, 17:46 


01/09/16
3
Изображение

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

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

 Профиль  
                  
 
 Re: Как сравнить кривые друг с другом?
Сообщение01.09.2016, 18:19 
Заслуженный участник
Аватара пользователя


30/01/06
61241
Этим целая наука занимается, и даже не одна.

 Профиль  
                  
 
 Re: Как сравнить кривые друг с другом?
Сообщение01.09.2016, 18:20 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как сравнить кривые друг с другом?
Сообщение01.09.2016, 19:14 
Аватара пользователя


21/01/09
2832
Дивногорск
DmitriySidelnikov, эталонная кривая всегда прямая линия?

 Профиль  
                  
 
 Re: Как сравнить кривые друг с другом?
Сообщение01.09.2016, 22:06 
Заслуженный участник
Аватара пользователя


22/01/11
1851
СПб
в каком виде вам нужен ответ на вопрос
Цитата:
Как сравнить кривые два объекта одной природы друг с другом?

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

 Профиль  
                  
 
 Re: Как сравнить кривые друг с другом?
Сообщение01.09.2016, 22:18 
Заслуженный участник


25/02/11
1424
Вот, например, способ. Параметризовать обе кривые параметром $\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$. Или корень из него.

 Профиль  
                  
 
 Re: Как сравнить кривые друг с другом?
Сообщение29.11.2016, 17:46 


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

-- 29.11.2016, 17:57 --

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

 Профиль  
                  
 
 Re: Как сравнить кривые друг с другом?
Сообщение09.12.2016, 13:01 
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group