Свёртка: главная операция ЦОС

Знакомимся со свёрткой — операцией, через которую работают почти все фильтры DSP.

Свёртка сигнала $x$ с ядром $h$ — это «скольжение и взвешенная сумма»: $y[n] = \sum_k x[k]\,h[n-k]$. Результат показывает, как сигнал $x$ «откликается» на короткий шаблон $h$.

$$y[n] = \sum_k x[k]\,h[n-k]$$

Свёртка — без преувеличения сердце ЦОС. Любой линейный фильтр — это свёртка сигнала с некоторым ядром. Размытие фото, шумоподавление, выделение краёв, эхо — всё это свёртки с разными ядрами. Освоив одну операцию, вы поймёте половину DSP.

Идея: скольжение и сумма

Представьте, что ядро $h$ — это маленькое «окошко с весами». Мы прикладываем его к сигналу в каждой позиции, перемножаем перекрытые отсчёты и складываем — получаем одно число выхода. Сдвигаем окошко на один отсчёт и повторяем. Скольжение даёт весь выходной сигнал.

def convolve(x, h):
    y = [0.0] * (len(x) + len(h) - 1)
    for i in range(len(x)):
        for j in range(len(h)):
            y[i + j] += x[i] * h[j]
    return y

x = [1, 2, 3]
h = [1, 1, 1]   # ядро-сумматор
print("x * h =", [round(v, 3) for v in convolve(x, h)])

Вывод:

x * h = [1.0, 3.0, 6.0, 5.0, 3.0]

Длина результата — len(x) + len(h) - 1. Значения нарастают и спадают: это «следы» окошка, въезжающего на сигнал и съезжающего с него.

Свёртка как выделение признака

Поменяем ядро на [1, 0, -1] — это детектор перепадов: он реагирует на разность соседей, то есть на края.

def convolve(x, h):
    y = [0.0] * (len(x) + len(h) - 1)
    for i in range(len(x)):
        for j in range(len(h)):
            y[i + j] += x[i] * h[j]
    return y

x = [0, 1, 2, 3, 0]      # сигнал с подъёмом и резким спадом
edge = [1, 0, -1]        # детектор краёв
print("края:", [round(v, 3) for v in convolve(x, edge)])

Вывод:

края: [0.0, 1.0, 2.0, 2.0, -2.0, -3.0, 0.0]

Там, где сигнал растёт, отклик положительный; на резком спаде — большой отрицательный. Так одно ядро превращает «значения» в «изменения». Меняя ядро, мы меняем, какой признак выделяет свёртка.

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

Почему в формуле $h[n-k]$ с минусом — ядро как бы развёрнуто? Это следствие смысла: чтобы вклад входа $x[k]$ попал на выход в момент $n$ через отклик системы, нужно взять часть отклика, прошедшую $n-k$ отсчётов после $k$. На практике в коде мы просто складываем произведения x[i]*h[j] в ячейку y[i+j] — это эквивалентная и более наглядная запись. Свёртка обладает важными свойствами: она коммутативна ($x * h = h * x$), ассоциативна и дистрибутивна относительно сложения. Коммутативность означает, что «кто на кого скользит» неважно — результат тот же; это упрощает рассуждения о цепочках фильтров.

def convolve(x, h):
    y = [0.0] * (len(x) + len(h) - 1)
    for i in range(len(x)):
        for j in range(len(h)):
            y[i + j] += x[i] * h[j]
    return y

print("x*h == h*x:", convolve([1, 2, 3], [4, 5]) == convolve([4, 5], [1, 2, 3]))

Вывод:

x*h == h*x: True

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

• Забыть про удлинение результата. Полная свёртка длиннее входа на $\text{len}(h)-1$; если нужен сигнал той же длины, его обрезают по центру.
• Путать свёртку и корреляцию. Они похожи, но в корреляции ядро не разворачивается; для симметричных ядер результаты совпадают, для несимметричных — нет.
• Свёртывать «в лоб» большие сигналы. Прямая свёртка — это $O(N\cdot M)$; для длинных сигналов её делают через БПФ (теорема о свёртке).

Итог

• Свёртка — «скольжение и взвешенная сумма» сигнала с ядром: $y[n] = \sum_k x[k]\,h[n-k]$.
• Меняя ядро, выделяем разные признаки: сумму, разность (края), среднее.
• Свёртка коммутативна, ассоциативна и дистрибутивна.
• Это базовая операция всех линейных фильтров DSP.