Свёртка

Свёртка (лат. convolutio — свёртывание, свертывание) — это математическая операция, применяемая к двум функциям (или последовательностям), результатом которой является новая функция, показывающая, как форма одной функции изменяется под воздействием другой. В дискретном случае свёртка представляет собой сумму произведений значений одной функции на сдвинутые и отражённые значения другой. Операция широко используется в различных областях науки и техники, включая обработку сигналов, теорию вероятностей, компьютерное зрение и машинное обучение.

Определение

Непрерывная свёртка

Для двух функций \( f(t) \) и \( g(t) \), определённых на множестве действительных чисел, их свёртка \((f * g)(t)\) определяется интегралом:

\[ (f * g)(t) = \int_{-\infty}^{\infty} f(\tau) g(t - \tau) \, d\tau \]

Интеграл берётся по всем значениям \(\tau\), при которых обе функции определены. Результат — функция, зависящая от переменной \(t\). Операция коммутативна: \(f g = g f\).

Дискретная свёртка

Для двух дискретных последовательностей \( f[n] \) и \( g[n] \) (где \(n\) — целое число) дискретная свёртка определяется как:

\[ (f * g)[n] = \sum_{m=-\infty}^{\infty} f[m] \, g[n - m] \]

На практике последовательности обычно конечны, и суммирование ведётся по области их пересечения.

Свойства

Свёртка обладает рядом фундаментальных свойств, которые делают её удобной для анализа и вычислений:

• Коммутативность: \( f g = g f \)
• Ассоциативность: \( (f g) h = f (g h) \)
• Дистрибутивность относительно сложения: \( f (g + h) = f g + f * h \)
• Ассоциативность со скалярным умножением: \( a (f g) = (a f) g = f * (a g) \), где \(a\) — константа
• Сдвиг: если \( f(t) \) сдвинуть на \(a\), то \((f(t-a) g(t)) = (f g)(t-a)\)
• Дифференцирование: производная свёртки равна свёртке производной с другой функцией: \( \frac{d}{dt}(f g) = \frac{df}{dt} g = f * \frac{dg}{dt} \)

Связь с преобразованием Фурье

Одно из важнейших свойств свёртки — её связь с преобразованием Фурье. Согласно теореме о свёртке, преобразование Фурье свёртки двух функций равно поточечному произведению их преобразований Фурье:

\[ \mathcal{F}\{f * g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\} \]

Это свойство позволяет эффективно вычислять свёртку, заменяя интегрирование умножением в частотной области, что широко используется в цифровой обработке сигналов.

Применение

Обработка сигналов и изображений

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

Теория вероятностей

В теории вероятностей свёртка используется для нахождения распределения суммы двух независимых случайных величин. Если \(X\) и \(Y\) — независимые случайные величины с плотностями распределения \(f_X\) и \(f_Y\), то плотность распределения суммы \(X+Y\) равна свёртке \(f_X\) и \(f_Y\).

Машинное обучение

В глубоком обучении свёрточные нейронные сети (CNN) используют операцию свёртки для извлечения признаков из входных данных, таких как изображения, видео или тексты. Свёрточные слои применяют обучаемые фильтры (ядра) к входным данным, что позволяет сети автоматически обнаруживать пространственные иерархии признаков.

Дифференциальные уравнения

Свёртка применяется для решения линейных дифференциальных уравнений с постоянными коэффициентами. Решение может быть представлено как свёртка входного сигнала с импульсной характеристикой системы (функцией Грина).

Вычислительные аспекты

Прямое вычисление дискретной свёртки двух последовательностей длины \(N\) требует \(O(N^2)\) операций. Для ускорения вычислений используется алгоритм быстрого преобразования Фурье (БПФ), который позволяет выполнить свёртку за \(O(N \log N)\) операций. Этот метод применяется в большинстве современных программных библиотек для обработки сигналов и изображений.

Примеры

Сглаживание сигнала

Пусть \(f(t)\) — зашумлённый сигнал, а \(g(t)\) — гауссово ядро \(g(t) = \frac{1}{\sqrt{2\pi}\sigma} e^{-t^2/(2\sigma^2)}\). Свёртка \(f * g\) даёт сглаженный сигнал, в котором высокочастотные шумы подавлены.

Обнаружение границ на изображении

Ядро Собеля для обнаружения вертикальных границ имеет вид: \[ \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix} \] Свёртка изображения с этим ядром выделяет области с резким изменением яркости по горизонтали.

История

Понятие свёртки впервые появилось в работах математиков XVIII века, в частности, в трудах Леонарда Эйлера и Пьера-Симона Лапласа. Однако систематическое изучение и формализация операции связаны с развитием функционального анализа и теории интегральных преобразований в XIX—XX веках. Термин «свёртка» (convolutio) ввёл в обиход немецкий математик Густав Дирихле.

Интересные факты

• В русскоязычной литературе наряду с термином «свёртка» иногда используется устаревший вариант «свёртывание», а также калька с английского «конволюция».
• Операция свёртки является основой работы многих физических приборов, например, спектрометров, где измеряемый сигнал является свёрткой истинного спектра с аппаратной функцией прибора.
• В компьютерной графике свёртка используется для создания эффектов размытия, свечения и текстурирования.

Источники

• Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся втузов. — М.: Наука, 1986.
• Оппенгейм А., Шафер Р. Цифровая обработка сигналов. — М.: Техносфера, 2006.
• Гонсалес Р., Вудс Р. Цифровая обработка изображений. — М.: Техносфера, 2012.
• Гудфеллоу Я., Бенджио И., Курвилль А. Глубокое обучение. — М.: ДМК Пресс, 2018.