Здравствуйте. Помогите пожалуйста, подкините идейку.
Есть два множества последовательностей вещественных чисел, каждая последовательность имеет свой определенный интервал, на котором она существует. Задача: определить наиболее похожие последовательности (искать сходство надо только между последовательностями из различных множеств).
Особенности:
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, так же как и при смещеных по У на какое то число. Поскольку А это среднее геометрическое, то сильное изменение каких то "штучных" элементов вектора слабее отразиться на среднем, нежели среднее алгебраическое - как следствие, мало повлияет на результат.
Все же этот алгоритм я бы не рекомендовал использовать для сравнения изображений. Для этих целей у меня есть собственные наработки, которые основаны больше на психологии восприятия чем на математике. Для других целей, где преимущественно используются одномерные массивы алгоритм вполне дееспособен и используется мной в собственных целях в своих программах с небольшими адаптационными доработками.
1) Выполняется эдакая "нормализая" каждого из векторов, а именно
1.1) Ищется максимальный модуль (М) и среднее геометрическое значений вектора (А)
1.2) А принимается за ноль, М за единицу
1.3) Считается разница между каждым значением вектора и А, затем делится на (М - А), т.о. выполняется нормализация.
2) Когда вектора нормализованы, начинаем считать среднее отношение значений двух векторов, т.е. С = (a[1]/b[1] + a[2]/b[2] + ... a[n]/b[n]) / n
При одникавых векторах С = 1, так же как и при смещеных по У на какое то число. Поскольку А это среднее геометрическое, то сильное изменение каких то "штучных" элементов вектора слабее отразиться на среднем, нежели среднее алгебраическое - как следствие, мало повлияет на результат.
Все же этот алгоритм я бы не рекомендовал использовать для сравнения изображений. Для этих целей у меня есть собственные наработки, которые основаны больше на психологии восприятия чем на математике. Для других целей, где преимущественно используются одномерные массивы алгоритм вполне дееспособен и используется мной в собственных целях в своих программах с небольшими адаптационными доработками.
It's a long way to the top if you wanna rock'n'roll