CNN Фурье с размером ядра 1024x1024 и больше

Многомерные преобразования Фурье в сверточных нейронных сетях

В наши дни широко распространены сверточные нейронные сети (CNN). Независимо от их успеха, свертки неэффективны. Скользящее окно требует большого количества вычислений и ограничивает размер ядра. В то же время небольшое ядро, обычно от [3,3] до [7,7], ограничивает поле восприятия, и требуется много слоев для захвата глобального контекста входного тензора (например, 2D-изображений). Чем больше изображение, тем хуже становится влияние маленьких фильтров. Вот почему вам будет трудно найти CNN, которые вводят изображения с высоким разрешением.

Что, если я скажу вам, что есть способ масштабировать размер ядра до [1024,1024] и выше, что есть способ увеличить размер ядра для заданного входного разрешения почти без влияния на время вывода, и что, если был бы способ резко уменьшить пространственное измерение карты объектов, не теряя почти никакой информации, в отличие от таких методов, как максимальное объединение?

Все эти обещания основаны на простом математическом свойстве: теореме свертки (точнее, теореме взаимной корреляции) преобразования Фурье, и я покажу вам, как правильно ее использовать!

Примечание: вместе с этой статьей я опубликовал блокнот на моем GitHub со всем кодом

Контур

1. Пороки сверток
2. Двухмерное дискретное преобразование Фурье на помощь
3. Открытие 2D FFT спектров
4. Реализация в TensorFlow
5. "Заключение"
6. Дополнительная литература и ссылки

Недостатки сверток

Давайте вспомним некоторые основы. Свертка — это математическая операция, применяемая к двум функциям. Начнем с одномерного случая:

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

Но почему я упомянул о взаимной корреляции раньше? Ну, это потому, что свертка и взаимная корреляция на самом деле вычисляются одинаково, с той лишь разницей, что фильтр переворачивается. На это указывает другой знак:

TensorFlow и PyTorch на самом деле вычисляют взаимную корреляцию входного сигнала и обучаемого фильтра, а не свертки. Это имеет значение? Не совсем! Поскольку фильтр изучается сетью, не имеет значения, перевернут фильтр или нет. Сеть сама разберется, что лучше. Это даже экономит некоторые вычисления, чтобы не переворачивать фильтр. Однако есть разница, если фильтр фиксирован, что означает, что если вы загружаете обученную модель, вы должны знать, была ли она обучена с использованием кросс-корреляции или свертки, и в конечном итоге должны изменить вес фильтра.

Две вещи, которые вы должны помнить из этого:

1. Для вычисления одной точки в выходной последовательности требуется много вычислений.
2. Чем больше входной сигнал (т.е. чем больше разрешение у изображения), тем чаще нужно смещать фильтр, следовательно, требуется больше вычислений. То же самое относится и к более крупному фильтру.

Больше вычислений означает больше памяти и большую задержку, пока результат не будет доступен. Последствия для CNN очевидны: более низкое входное разрешение и меньшие фильтры. Проблема: меньше пикселей означает меньше деталей, а меньший размер фильтра приводит к меньшим восприимчивым полям. Сети должны иметь несколько последовательных сверточных слоев, чтобы увеличить восприимчивое поле. Сети становятся более глубокими, что снова приносит новые проблемы во время обучения.

Двумерное дискретное преобразование Фурье на помощь

С математической точки зрения преобразование Фурье действительной или комплексной функции x(t) временной переменной t представляет собой комплексную функцию X(f) действительной частотной переменной f:

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

Эти свойства очень важны и являются основой этой статьи: свертка/корреляция во временной области соответствует простому поэлементному умножению в частотной области. Но что в этом такого захватывающего? Как упоминалось ранее, свертка требует большого количества вычислений, особенно для больших изображений и фильтров. Его сложность масштабируется квадратично с длиной последовательности, то есть O (N²). Следуя теореме свертки, нам нужно только выполнить поэлементное умножение преобразованного ввода и преобразованного фильтра. Существуют эффективные алгоритмы для вычисления преобразования Фурье, то есть быстрого преобразования Фурье (БПФ), которое снижает сложность до O(N log(N)). И что самое приятное, пока фильтр меньше входного сигнала, вычислительные требования остаются постоянными. Неважно, имеет ли наш фильтр размер ядра [3,3] или [1024, 1024]. Подробности в разделе о реализации в TensorFlow.

Преобразование Фурье также существует для действительных или комплексных дискретных сигналов x[k], которое присваивает комплексному дискретному сигналу X[n] вещественную переменную n:

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

Примечание. Дискретный сигнал является дискретным по времени и дискретным по значению. Дискретное по времени, потому что оно выбирается через определенные промежутки времени, и дискретное по значению, потому что каждое значение представлено определенным количеством битов, например. 32 бита для INT32.

Есть некоторые последствия, которые мы должны иметь в виду при работе с ДПФ:

1. Предполагается, что входной сигнал является периодическим, и что дискретизируется полный период.
2. Результирующий спектр является периодическим

Примечание. Изображение можно интерпретировать как пространственный сигнал, а не как сигнал времени. На компьютере изображение дискретно по пространству, потому что значения хранятся в пикселях, которые берутся с датчика изображения с пространственно распределенными ячейками или оцифровываются.

Двумерное ДПФ (а также двумерное непрерывное преобразование Фурье) можно разделить на последовательные одномерные ДПФ, где строки и столбцы можно вычислять отдельно.

Это имеет по крайней мере два преимущества: во-первых, можно повторно использовать алгоритм одномерного ДПФ, а во-вторых, это помогает создать интуитивное представление для двумерного ДПФ, поскольку строки и столбцы можно интерпретировать индивидуально.

Но, конечно, у дискретного преобразования Фурье есть одна небольшая деталь: теорема о свертке неверна для ДПФ.

Умножение двух ДПФ сигналов соответствует их круговой свертке, обозначаемой оператором ⊛, а не их линейной свертке.

Круговая свертка — это периодический сигнал, который повторяется с длиной сигнала N, тогда как линейная свертка имеет длину (N+F-1), где F — длина сигнала фильтра. Таким образом, если вы вслепую возьмете произведение в частотной области, вы сожмете свой сигнал длины (N+M-1) до длины N. Это можно рассматривать как наложение во временной области, которое создает нежелательные артефакты в конечном результате. К счастью, круговая и линейная свертки имеют общие значения, то есть (N-F+1). Остальные (F-1) значения накладываются друг на друга и мешают другим значениям сигнала.

Вот идея: что, если значения, которым мешают обернутые значения, будут равны нулю, что означает, что не с чем мешать? Это означало бы, что мы могли бы восстановить линейную свертку из круговой свертки. Когда сигнал дополнен как минимум (F-1) нулями, завернутые значения не мешают реальным значениям. Затем мы могли бы по кругу сместить завернутые значения обратно в их положение и обрезать дополненные значения. Подробности будут показаны в разделе реализации.

Я избавляю вас от всех математических подробностей и ссылаюсь на дополнительные ресурсы в конце статьи.

Открытие спектров 2D DFT

Теперь, когда мы рассмотрели теорию, давайте откроем некоторые 2D-преобразования Фурье и укрепим нашу интуицию для 2D-преобразования Фурье.

Фундаментальные тестовые сигналы и их влияние на CNN

Рассмотрим изображение, интенсивность пикселей которого соответствует диагональной синусоидальной волне. Какой амплитудный спектр вы ожидаете? Как упоминалось ранее, двумерное преобразование Фурье можно вычислить путем разделения двумерного преобразования Фурье на несколько одномерных преобразований Фурье по каждой оси изображения. Если вы представите себе ходьбу вдоль горизонтальной оси, вы столкнетесь с повторяющимся паттерном. То же самое верно, если вы представляете ходьбу вдоль вертикальной оси. Таким образом, естественно ожидать высокого значения спектра в пределах четвертого квадранта (внизу справа), квадранта с положительными частотными компонентами.

Примечание: 2D-амплитудный спектр обычно масштабируется с помощью логарифмической функции при построении графика, поскольку изображения имеют большое смещение независимо от их содержимого, поскольку они обычно представлены целым числом без знака, которое представляет только положительные значения.

Теперь давайте рассмотрим входное изображение прямоугольника с разными длинами сторон. Если вы снова вообразите, что идете вдоль каждой оси, вы столкнетесь с прямоугольником с короткой шириной импульса по горизонтальной оси и прямоугольником с более широкой шириной импульса по вертикальной оси. Если вы знакомы с теорией сигналов, вы сразу же ожидаете, что ваш спектр будет иметь какую-то функцию sinc, где sinc(x)=sin(x)/x.

Если вы ожидали sinc-функцию, вы были совершенно правы. Спектр состоит из sinc-функций по обеим осям. Здесь вы можете сделать фундаментальное наблюдение:горизонтальная ось имеет более высокие частотные компоненты, такие как вертикальная ось и нулевая пересечения более распространены по горизонтальной оси. Это наблюдение имеет два следствия:

1. Узкие пространственные объекты на входном изображении имеют высокочастотные компоненты в амплитудном спектре, следовательно, они имеют большую полосу пропускания. Фильтры с высокой пропускной способностью подвержены шуму.
2. Спектр масштабируется обратно пропорционально пространственной длине объектов на входном изображении. Узкие признаки приводят к широкому спектру, а широкие признаки приводят к узкому спектру.

Что это означает для наших CNN с небольшими фильтрами, скажем, 3x3 пикселя? Согласно нашему наблюдению выше, это должно означать, что CNN с небольшими фильтрами действуют как фильтры с высокой пропускной способностью и, следовательно, склонны к входному шуму. Чем больше размер фильтра, тем ниже полоса пропускания фильтра и тем более избирательным он является.

2D ДПФ изображений и фильтрация в частотной области

Теперь, когда мы поговорили о некоторых фундаментальных сигналах, давайте исследуем двумерные ДПФ реальных изображений.

Центр спектра представляет нулевую частоту, также называемую смещением. Чем дальше от центра, тем выше частотная составляющая на входе. Имея это в виду, вы можете легко получить фильтр верхних частот и фильтр нижних частот.

Фильтр верхних частот подавляет низкие частоты и сохраняет высокочастотные составляющие. Такое поведение может быть реализовано с помощью фильтра, который имеет нули ближе к центру и единицы для значений дальше от центра. Фильтр применяется путем умножения фильтра на спектр и последующего вычисления обратного преобразования Фурье.

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

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

Изображение с фильтром нижних частот выглядит размытым и теряет резкость. Типичным фильтром, используемым в компьютерном зрении, является фильтр Гаусса. Это также фильтр нижних частот, но вместо резкой частоты среза эффект фильтра постепенно увеличивается для более высоких частот. Сглаживает изображение. Изображение ниже отфильтровано гауссовским фильтром, который имеет дисперсию (сигма в квадрате), равную частоте среза круглого фильтра нижних частот ранее.

Изображение размыто, но искажений меньше. Он кажется более гладким.

Довольно интересным фильтром для приложений машинного обучения является прямоугольный фильтр. Сверточные нейронные сети часто постепенно уменьшают пространственную ширину и увеличивают количество каналов. Объединение, такое как максимальное или среднее, часто используется для уменьшения пространственной ширины. Что, если бы мы объединились в частотной области?

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

ДПФ обладает интересным свойством для реальных входных данных: оно сопряжено симметрично относительно начала координат. Симметрия означает, что спектр содержит избыточность, которую можно исключить при расчете для дальнейшего ускорения процесса. На рисунке ниже показано это преобразование и обратное ему преобразование, восстановленное из спектра.

Вынесите из этого раздела:

1. Низкочастотные компоненты находятся в центре 2D-спектра, тогда как высокочастотные компоненты находятся дальше от центра.
2. Вы можете воспользоваться свойством симметрии ДПФ, чтобы уменьшить требуемые вычислительные ресурсы и вычислить только rДПФ.
3. Фильтры небольших размеров подвержены шуму из-за их высокой пропускной способности.

Вот блокнот, который я создал для создания графиков:

Реализация в TensorFlow

У нас есть все необходимое для реализации линейной свертки с использованием дискретного преобразования Фурье.

На высоком уровне нам необходимо реализовать следующие 6 шагов:

1. Заполните входное изображение, чтобы избежать алиасинга во временной области
2. Фильтр Pad по размеру изображения для подготовки поэлементного умножения
3. Рассчитать 2D rFFT входного изображения и фильтровать
4. Поэлементное умножение преобразованного ввода и преобразованного фильтра
5. Вычислите 2D-обратный rFFT отфильтрованного ввода, чтобы получить круговую свертку
6. Восстановите линейную свертка из круговой свертки

Шаг 1 — Входное изображение пэда

Чтобы избежать эффектов наложения во временной области, нам нужно дополнить изображение как минимум (F-1) нулями, где F — длина стороны фильтра. Кроме того, алгоритм БПФ, который вычисляет ДПФ, особенно эффективен для длин сигналов, имеющих степень 2 (например, 128 512 1024).

Есть как минимум два варианта заполнения входного изображения: во-первых, мы вручную дополняем изображение. Во-вторых, мы устанавливаем длину последовательности БПФ равной длине дополненного сигнала. Я предпочитаю более поздний.

Ниже приведен код, чтобы вручную заполнить изображение.

А вот мой предпочтительный способ указать большую длину последовательности при вычислении БПФ:

# image is of shape [b,c,h,w]
padding = GetImagePadding(filter_shape[0]) 
image_shape = (input_shape[0],
               input_shape[1],
               input_shape[2]+2*padding,
               input_shape[3]+2*padding)
image_shape = FillImageShapeToPower2(image_shape)

F_image = tf.signal.rfft2d(image, fft_length=[image_shape[-2],image_shape[-1]])

Шаг 2 — фильтр Pad по размеру изображения

Поскольку нам нужно вычислить поэлементное произведение преобразованного изображения с преобразованным фильтром, нам нужно дополнить фильтр до размера дополненного изображения, прежде чем мы вычислим преобразование Фурье. Фильтр заполняется нулями. Опять же, я бы предложил заполнить фильтр, правильно установив параметр fft_lenght расчета БПФ, т.е.

F_filter = tf.signal.rfft2d(filter, fft_length=[image_shape[-2],image_shape[-1]])

Шаг 3 — Рассчитайте 2D rFFT

Поскольку мы подготовили наши входные сигналы, теперь мы можем вычислить БПФ для дополненного изображения и дополненного фильтра:

# Image shape [b,c,h,w], Filter shape [out, in , k, k]
F_image = tf.signal.rfft2d(image, fft_length=[image_shape[-2],image_shape[-1]])
F_filter = tf.signal.rfft2d(filter, fft_length=[image_shape[-2],image_shape[-1]])

Мы используем сопряженную симметрию для реальных входных данных и вычисляем реальное БПФ только для 2D-сигналов, используя rfft2d. Чтобы быть конкретным, мы вводим незаполненные сигналы и устанавливаем для fft_length значение, превышающее длину ввода. Это автоматически дополняет сигнал нулями.

Важно: реализация TensorFlow rfft2d вычисляет БПФ по двум последним измерениям входных данных. В отличие от реализации numpy, вы не можете изменить размер через параметр. По этой причине форма изображения [пакет, канал, высота, ширина] и форма ядра [output_filter, input_filter, kernel_height,kernel_width]

Если бы мы реализовали свертку в частотной области, мы бы закончили. Поскольку TensorFlow на самом деле реализует взаимную корреляцию, нам нужно связать преобразованный фильтр, чтобы получить согласованные результаты:

F_filter = tf.math.conj(F_filter)

Шаг 4 — Умножение преобразованного изображения и преобразованного фильтра

Если бы у нас было только одно изображение и один фильтр, поэлементное умножение было бы просто F_image*F_folter. В реальном сценарии у нас обычно есть несколько изображений в виде пакета, и мы применяем несколько фильтров параллельно. Нам нужно изменить размерность входных сигналов и воспользоваться преимуществами широковещательной передачи массива, чтобы выполнить эту операцию без каких-либо петель.

Функцию einsum() TensorFlow можно использовать для простого изменения размеров. Символы слева от стрелки описывают входную форму, а символы справа — выходную форму. Размеры изображения и фильтра перестраиваются таким образом, что все пакеты и все выходные фильтры будут транслироваться при расчете поэлементного произведения. После умножения исходная форма восстанавливается путем изменения формы и уменьшения размерности входного фильтра.

Шаг 5 — Рассчитайте обратный 2D rFFT

Обратное БПФ просто берется из отфильтрованного сигнала с тем же параметром fft_length, что и для БПФ:

out = tf.signal.irfft2d(filterd_image, fft_length=[image_shape[-2],image_shape[-1]])

Шаг 6. Реконструируйте линейную свертка из круговой свертки

Помните, что для восстановления линейной свертки из круговой свертки нам нужно выполнить два шага: во-первых, нам нужно циклически сдвинуть результат на величину заполнения. Во-вторых, нам нужно обрезать до интересующей нас области исходную форму изображения для всех пакетов и новое количество каналов.

#Circular shift
out = tf.roll(out,shift = [2*padding,2*padding],axis = [-2,-1]) 
#Truncation
out = tf.slice(out, 
               begin = [0, 0, padding, padding], 
               size=[input_shape[0], 
                     filter_shape[-1],  
                     input_shape[2], 
                     input_shape[3]]
               )

И это все!
В приведенном ниже коде показана полная реализация шагов с 1 по 6:

Примечание. Свертка в области Фурье также реализована в виде слоя TensorFlow как часть моего пакета DeepSaki, и ее можно найти на GitHub или загрузить с PyPi.

Проверка

Вы можете спросить себя: Но действительно ли это работает? Давайте выясним! Все этапы проверки включены в блокнот для этой статьи.

Во-первых, мы посмотрим на время выполнения в секундах по размеру ядра для обеих функций: tf.nn.conv2d() и нашей реализации.

Как и следовало ожидать, время выполнения 2D-свертки продолжает расти с увеличением размера ядра. С другой стороны, свертка 2D DFT постоянна во времени выполнения независимо от размера фильтра. Это происходит из-за того, что фильтр подстраивается под размер изображения. Если фильтр больше, дополняется меньшее количество значений.

Теперь давайте взглянем на исследование разницы в результате. Для этого применяем ядро ​​размером 3х3 с 8 фильтрами на изображение 720х720 пикселей. Мы запускаем его через оба алгоритма и вычисляем среднее значение и стандартное отклонение абсолютной разницы.

convResult = CalcConv(image, filter)
dftResult = CalcDFT2D(image, filter)

error = tf.math.abs(convResult-dftResult)
mean = tf.math.reduce_mean(error)
std = tf.math.reduce_std(error)
# Mean Absolute Error: 0.001560982083901763
# Standard deviation: 0.0015975720016285777

И среднее значение, и стандартное отклонение довольно низкие. Разница возникает из-за числовых неточностей. При просмотре отфильтрованных изображений и соответствующих амплитудных спектров видно, что они неразличимы.

Заключение

Мы увидели математическую основу сверток и ДПФ, получили некоторую интуицию, наблюдая за различными спектрами, просмотрели код в TensorFlow и, наконец, подтвердили правильность результатов.

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

Дополнительная литература и ссылки