Корреляция и согласованная фильтрация

Учимся находить известный образ внутри сигнала — основа радара, GPS и распознавания.

Корреляция измеряет похожесть двух сигналов при разных сдвигах. Согласованный фильтр — оптимальный способ обнаружить известную форму (шаблон) в зашумлённом сигнале.

Как радар находит самолёт? Как GPS-приёмник ловит спутник в шуме в миллионы раз сильнее сигнала? Как найти повтор в музыке или период в пульсе? Везде работает одна идея — корреляция: «сдвигаем шаблон вдоль сигнала и смотрим, где он лучше всего совпал». Это мощнейший детектор образов.

Взаимная корреляция: ищем шаблон

Взаимная корреляция скользит шаблоном t по сигналу и в каждой позиции считает «оценку совпадения» (сумму произведений). Где оценка максимальна — там шаблон нашёлся.

def cross_correlate(sig, t):
    out = []
    for i in range(len(sig) - len(t) + 1):
        score = sum(sig[i + j] * t[j] for j in range(len(t)))
        out.append(score)
    return out

signal = [0, 0, 1, 2, 3, 0, 0, 1, 2, 3, 0]   # шаблон [1,2,3] встречается дважды
template = [1, 2, 3]
scores = cross_correlate(signal, template)
print("Оценки совпадения:", scores)
print("Лучшее совпадение на индексе:", scores.index(max(scores)))

Вывод:

Оценки совпадения: [3, 8, 14, 8, 3, 3, 8, 14, 8]
Лучшее совпадение на индексе: 2

Максимальная оценка 14 — на индексах 2 и 7, ровно там, где в сигнале сидит шаблон [1,2,3]. Корреляция нашла образ, несмотря на нули и повторы вокруг.

Автокорреляция: ищем период

Автокорреляция — это корреляция сигнала с самим собой при разных сдвигах (лагах). Она выявляет скрытую периодичность: на лаге, равном периоду, сигнал «совпадает с собой» и даёт пик. Так находят высоту голоса (pitch) и периоды в данных.

import math

sig = [math.sin(2 * math.pi * n / 8) for n in range(32)]   # период = 8

def autocorr(x, lag):
    return round(sum(x[n] * x[n + lag] for n in range(len(x) - lag)), 2)

acs = [autocorr(sig, lag) for lag in range(10)]
print("Автокорреляция по лагам 0..9:", acs)
# первый положительный пик после лага 0
best = max(range(1, 10), key=lambda l: autocorr(sig, l))
print("Период сигнала:", best)

Вывод:

Автокорреляция по лагам 0..9: [16.0, 11.31, 0.5, -9.9, -14.0, -9.9, -0.5, 8.49, 12.0, 8.49]
Период сигнала: 8

На лаге 0 максимум (сигнал всегда совпадает с собой). Затем спад в минус (противофаза на лаге 4 — половина периода), и снова рост к пику на лаге 8 — это и есть период. Автокорреляция «нащупала» периодичность 8.

Согласованный фильтр

Согласованный (matched) фильтр — это и есть корреляция с шаблоном, оформленная как фильтр: его ядро — это перевёрнутый шаблон. Теория доказывает, что он даёт максимально возможное отношение сигнал/шум при обнаружении известной формы. Поэтому радар коррелирует эхо с излучённым импульсом, а GPS — принятый шум с известным кодом спутника. Даже если сигнал утонул в шуме, в точке совпадения корреляция даёт чёткий пик.

Как работает под капотом

Корреляция почти тождественна свёртке: corr(x, t) равна conv(x, перевёрнутый t). Разница лишь в развороте шаблона. Поэтому всё, что мы знаем о свёртке (включая быстрый расчёт через БПФ), применимо и к корреляции — длинные корреляции считают в частотной области за O(N log N). Почему согласованный фильтр оптимален? Он «концентрирует» всю энергию шаблона в один отсчёт выхода (в точке совпадения фазы складываются), тогда как случайный шум, не совпадающий с формой шаблона, складывается вразнобой и частично гасится. Чем длиннее и «уникальнее» шаблон, тем выше пик относительно шума — поэтому GPS использует длинные псевдослучайные коды: они дают острый, ни с чем не путаемый пик корреляции.

Частые ошибки

• Не нормировать корреляцию. Сырая оценка растёт с амплитудой сигнала; для честного сравнения используют нормированную корреляцию (коэффициент от -1 до 1).
• Путать корреляцию и свёртку. В корреляции шаблон НЕ переворачивается; для несимметричных шаблонов результат другой.
• Брать слишком короткий шаблон. Короткий образ часто «случайно» совпадает с шумом; длинный уникальный шаблон даёт надёжный пик.

Итог

• Корреляция измеряет похожесть сигналов при сдвигах; пик указывает на совпадение.
• Автокорреляция выявляет период сигнала (пик на лаге, равном периоду).
• Согласованный фильтр (корреляция с шаблоном) оптимально обнаруживает форму в шуме.
• Корреляция = свёртка с перевёрнутым шаблоном, поэтому ускоряется через БПФ.