Developing.ru

Здравствуйте. Помогите пожалуйста, подкините идейку.

Есть два множества последовательностей вещественных чисел, каждая последовательность имеет свой определенный интервал, на котором она существует. Задача: определить наиболее похожие последовательности (искать сходство надо только между последовательностями из различных множеств).

Особенности:

1. При проверке на сходство мы проверяем только части, которые как бы перекрывают друг друга по X (если одна последовательность задана на 3..9, а другая на 7..15, то на проверку забираем часть на интервале 7..9 одной последовательности и на 7..9 другой последовательности).

2. Смещение по Y имеет значение. То есть, если производные последовательностей равны, то совсем не обязательно, что результат сопоставления будет наилучшим, может быть и совсем плохим.

3. Чем меньше значений участвуют в проверке на сходство - тем эта проверка должна быть строже.

4. Если наблюдается шум на какой-нибудь последовательности - то строгость проверки снизить.

Для лучшего понимания задачи прилагаю архив с изображениями последовательностей, считающихся похожими.
http://files.filefront.com/arar/;9638728;/fileinfo.html

Вот так. Вопрос: что делать, куда копать хоть, что набирать в гугле?)

PS: данная задача является подзадачей задачи некоторого сопоставления изображений.

Исходя из этих условий сравнение таких последовательностей могу порекомендовать по следущему алгоритму.
1) Выполняется эдакая "нормализая" каждого из векторов, а именно
1.1) Ищется максимальный модуль (М) и среднее геометрическое значений вектора (А)
1.2) А принимается за ноль, М за единицу
1.3) Считается разница между каждым значением вектора и А, затем делится на (М - А), т.о. выполняется нормализация.
2) Когда вектора нормализованы, начинаем считать среднее отношение значений двух векторов, т.е. С = (a[1]/b[1] + a[2]/b[2] + ... a[n]/b[n]) / n
При одникавых векторах С = 1, так же как и при смещеных по У на какое то число. Поскольку А это среднее геометрическое, то сильное изменение каких то "штучных" элементов вектора слабее отразиться на среднем, нежели среднее алгебраическое - как следствие, мало повлияет на результат.
Все же этот алгоритм я бы не рекомендовал использовать для сравнения изображений. Для этих целей у меня есть собственные наработки, которые основаны больше на психологии восприятия чем на математике. Для других целей, где преимущественно используются одномерные массивы алгоритм вполне дееспособен и используется мной в собственных целях в своих программах с небольшими адаптационными доработками.