Как сравнить две кривые?

← →
CyberFreak (2004-01-17 20:22) [0]

Доброго времени суток, мастера.
Вопрос такой: есть некоторая абсолютно произвольная последовательность точек (x,y) с одной стороны и некая эталонная кривая, которая описана либо функцией, либо опять же последовательностью точек, с другой. Как мне с заранее определенной погрешностью определить одинаковые ли это кривые, ну т.е. в данном случае похожи они или не похожи.

← →
Yr2 (2004-01-17 20:40) [1]

Ответ на данный вопрос даёт "корреляционный анализ". см. на поисковиках математику. И ещё сначала определитесь с критерием "похожести". Понятно, что если функции стопроцентно похожи, то это значит, что они полностью совпадают. Хотя и это не всегда (например, график синусоиды, проходящей через ноль и тот же график синусоиды, но проходящей через +3). Они похожи или нет?
Сложнее с критерием "непохожести". Вы можете, например, представить два стопроцентно НЕ похожих человеческих лица? :)

← →
CyberFreak (2004-01-17 20:46) [2]

>Yr2

В моем случае две твои синусоиды похожи, меня интересует именно их форма, внешний вид так сказать, уж извините не знаю, как такая похожесть математически обзывается. А поповоду "непохожести": меня это какбы не интересует, мне надо установить именно "похожесть", причем не 100%-ую, а с установленной погрешностью, и если этого установить не удалось, значит они не похожи... во как!..

← →
TUser (2004-01-17 20:51) [3]

Если есть предположение, что кривые хоть немножко похожи (например, прямая и некая кривая, "зигзагообразно извивающаяся" вокруг прямой - пардон за нематематическую терминологию) - тогда, наверное, метод наименьших квадратов. А если они могут быть соверщенно непохожи - тогда сложнее. Возможно сравнивать смещения каждой точки относительно каждой предыдущей.
Кстати, 2 расположенных рядом круга - они похожи или нет?

← →
CyberFreak (2004-01-17 20:52) [4]

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

← →
TUser (2004-01-17 20:53) [5]

Ну вот и про 2 круга ответил. Такая похожесть называется подобие.
Вот у меня тут оказался какой-то конспект лекций (если не ошибаюсь с сайта "Замок Дракона"). Там вот что написано, может поможет.

Цепное кодирование.
Рассматриваем сетку, из каждой точки такой сетки можно двинуть-ся в восьми направлениях.
Из этих восьми точек выбираем наиболее близкую к кривой и переходим к ней, затем производим перекодировку (т.е. для этой новой точки нумеруем соседей 0,1,2…7 – против часовой стрелки). Таким образом, записывая номера в сетке точек, к которым переходим, строим ход.
Целью является последовательность точек a=a,…,an , а полученная цепь имеет вид b=b1,…,bn .
Рассмотрим корреляционную функцию
Cab=1/nЧSi=1aibi , cos(Рai -Рbi )
Если цепочки идеально совпадают, то Cab = (1+…+1)/n =1. Вообще, Cab Ј 1. Вокруг цепочки можно построить габаритный прямоугольник.
Изменение направления обхода означает перенумерацию, т.е. уве-личивается либо уменьшается или только x, или у, или x и y вместе (например, полученный код будет иметь вид 001120).
При цепном кодировании возможны следующие операции:
· Измерение длины цепи
· Описание прямоугольника
· Изменение направления обхода
· Площадь замкнутого контура
· Моменты инерции
· Кратчайшая цепь
· Расстояния между двумя точками
· Зеркальная цепь

Представление контура цепным кодом состоит из абсолютного ад-реса начальной точки и последовательности ключевых слов («0» – «7»), указывающих направления отрезков прямой, соединяющей соседние пикселы.
Существует дифференциальный код, при котором соседи кодиру-ются 0, ±1, ±2, ±3, 4, причем в целях экономии эти коды записывают как последовательности 0 и1:
‘0’ – 0;
‘+1’ – 01;
‘-1’ – 011;
‘+2’ – 0111;
‘-2’ – 01111; и т.д.
Возможны и другие варианты кодирования. «Соседи» номеруются также, но коды в 0 и 1 выглядят иначе:
‘0’ – 0;
‘+1’ – 100;
‘-1’ – 101;
‘+2’ – 1100;
‘-2’ – 1101;
‘+3’ – 1110;
‘-3’ – 1111, и т.д.

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

← →
CyberFreak (2004-01-17 20:55) [6]

>TUser

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

← →
TUser (2004-01-17 21:02) [7]

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

← →
CyberFreak (2004-01-17 21:03) [8]

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

← →
Vit@ly (2004-01-17 21:07) [9]

<Да, два круга, расположенных рядом тоже похожи, причем даже если имеют абсолютно разные радиусы.>
Совершенно верно. Автору необходимо определиться с понятием "похожесть". Это не есть вопрос программирования. Если он определится с этим (ну и соответсвенно нам расскажет), то с тем как реализовать это проблем не будет

← →
CyberFreak (2004-01-17 21:17) [10]

>Vit@ly

Дык я вроде как определился уже... или нет?

← →
Yr2 (2004-01-17 21:17) [11]

to CyberFreak:

А Вы зря так халатно отнеслись к "непохожести". На самом деле "похожесть" и "непохожесть" - это одно и тоже. Поэтому всё же определитесь, как Вы будете сравнивать свои объекты. А подобие везде разное:
1. Синусоиды.
Имеют амплитуду, частоту, фазу, постоянную составляющую. Вот, например, если по амплитуде одна больше другой в два раза, то они похожи? А если по частоте? – боюсь, что разные. И причём тут "не может быть циклически-бесконечной"? - естественно, что всё рассматривается на определённом участке (оси или плоскости).

2. Геометрические Фигуры.
Да, два круга, расположенных рядом тоже похожи, причем даже если имеют абсолютно разные радиусы
а чем тогда они отличаются? Радиусом? А если один из них "чуть-чуть" "эллиптичен"?

3. Изображения (" картинки").
Если цвет пикселей отличается на пару бит в зелёном канале - это похожие изображения или нет?

Таким образом, пользуясь Вашей терминологией, если Вы, например, указали "установленную погрешность" = 67, то попадает в этот строб квадрат при сравнении с треугольником?

← →
Vit@ly (2004-01-17 21:47) [12]

В первом посте речь и дет о <есть некоторая абсолютно произвольная последовательность точек (x,y)>, т.е. не упоминается о том , что это может быть расчет по какой-либо формуле (синусоида и какая-либо другая формула). В этом случае, ни две синусоиды (с разными периодами или раззными амплитудами) ни две окружности (с разными радиусами) непонятно каким образом считать "похожими". Повторюсь, это математика, а не программирование. Определитесь с "похожестью" <есть некоторая абсолютно произвольная последовательность точек (x,y)>

← →
CyberFreak (2004-01-17 23:06) [13]

> Vit@ly

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

Может я немножко не правильно вставил слово "сравнить"... попробуем по другому. мне надо определить, что за фигуру описывает произвольная последовательность точек: круг, квадрат, треугольник, букву B, букву W, вертикальную палку, горизонтальную палку, и еще всякие символы, которые можно описать непрерывной кривой. Набор фигур заранее определен.

Я понимаю что это математика, а не программирование. Я на самом деле гораздо умнее, чем может показаться на первый взгляд... =)

> Yr2

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

← →
Vit@ly (2004-01-17 23:22) [14]

Откровенно говоря я не врубился в проблему (задачу). Извиняюсь за предыдущие посты. Сорри

← →
CyberFreak (2004-01-17 23:29) [15]

> Vit@ly

Да ничего страшного.

← →
Yr2 (2004-01-17 23:41) [16]

to CyberFreak
уж не распознавание ли рукописного текста Вы хотите сделать?

← →
CyberFreak (2004-01-17 23:52) [17]

> Yr2

Да не, круче =)))

← →
Alexander666 (2004-01-18 03:26) [18]

А что может быть круче? Трехмерный сканер что ли?

← →
TUser (2004-01-19 07:31) [19]

Круче - распознавание рукописных китайских иероглифов без предварительного знания китайской письменности :)

Как сравнить две кривые? Найти похожие ветки