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

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

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

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

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

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

Итог

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