как найти сдвиг по данным из двух массивов

[romsky]

Салют,

хочу разобраться в решении одной задачи.

Имеются два равновеликих массива вещественных чисел, размерами порядка 500~1000 значений.
Второй массив есть слегка изменённый и сдвинутый относительно второго.
Необходимо найти такой сдвиг при котором массивы максимально совпадают.

Индекс свдига нужно искать от 0 до 100 индеkcа.


Я попробовал считать сумму разностей(по модулю) для каждого сдвига. Минимальная сумма
будет соотвествовать лучшему индексу сдвига.

Порывшись в голове и интернете - набрёл на слова свёртка, автокорреляция, быстрое преобразоване Фурье.

Помогите решить задачу правильно и с правильной Математикой.

Всех благ!

[AKM]

romsky в сообщении #593524 писал(а):

Имеются два равновеликих массива вещественных чисел, размерами порядка 500~1000 значений.
............................
Индекс свдига нужно искать от 0 до 100 индеkcа.

Значит ли это, что мы игнорируем остальные элементы массивов, и можно было говориь о "двух равновеликих массивах размером 101"?
Уточните.

[romsky]

Данные в массивах сделаны независимыми наблюдателями для одного и того же источника событий.
Разница в данных обьясняется задержками в передаче данных и точностью замеров.
Максимальный индекс сдвига(100) соответсвует максимальной возможной рассинхронизации.
Первые 100 елементов и последние 100 елементов во втором массиве можно игнорировать.

romsky в сообщении #593524 писал(а):

Второй массив есть слегка изменённый и сдвинутый относительно второго.

Второй массив есть слегка изменённый и сдвинутый относительно первого.

[Евгений Машеров]

В ряде случаев поиск сдвига, доставляющего минимум сумме абсолютных величин разностей, является наилучшей тактикой. Вопрос, насколько это оправдано сравнительно с автокорреляцией, зависит от требований по времени и от того, что есть "искажение". Если оно включает в себя изменение масштаба и сдвиг нуля (т.е. $M_1(i)=aM_2(i+h)+b+\eps$), при неизвестных a, b, то нужна именно кросскорреляция, избавляющая от влияния этих неизвестных величин, если только сдвиг по времени (и шум), то она несколько излишне обща.
$C_{X,Y}(j)=\frac{\sum_i {X_iY_{i+j}}}{\sqrt{\sum_i {X_i^2} \sum_i{Y_{i+j}^2}}}$
(массивы в данной формуле предполагаются центрированными, иначе надо перед умножением и возведением в квадрат вычесть среднее)
Повторяющийся по числу возможных сдвигов расчёт требует вычислительного ресурса. Если сдвигов много - применение преобразования Фурье может быть оправдано (оно основано на том, что Фурье от свёртки есть произведение преобразований Фурье от свёртываемых), то есть надо вычислить два Фурье на входе, перемножить почленно и вычислить обратное Фурье от произведения. По-видимому, Фурье оправдано при сдвигах, диапазон изменения которых существенно превышает сотню, сдвиги до сотни - лучше считать "в лоб" (впрочем, это сильно зависит). Некоторые методы ускорения расчёта АКФ и ККФ можно найти в книге Рабинера и Шафера "Цифровая обработка речевых сигналов", приложение к гл. 4.
Надо отметить, что возведение в квадрат в ходе вычисления АКФ(ККФ) сильно уязвимо к "выбросам" ("грубым ошибкам"), модуль более устойчив.