关于深度学习:卷积神经网络中的傅里叶变换1024×1024-的傅里叶卷积

卷积神经网络 (CNN) 失去了宽泛的利用并且事实证明他是十分胜利的。然而卷积的计算很低效，滑动窗口须要很多计算并且限度了过滤器的大小，通常在 [3,3] 到 [7,7] 之间的小核限度了感触野（最近才呈现的大核卷积能够参考咱们以前的文章），并且须要许多层来捕捉输出张量的全局上下文（例如 2D 图像）。图像越大小核的的体现就越差。这就是为什么很难找到解决输出高分辨率图像的 CNN 模型。

有一种办法能够将核大小扩大到 [1024,1024] 及以上，并且这种办法能够减少给定输出分辨率的核大小并且对推理工夫简直没有影响，还能够大幅升高特色图的空间维度，并且不会失落简直任何信息，你置信吗？

所有这些特色都基于一个简略的数学性质：傅里叶变换的卷积定理（精确地说是相互关定理）

让咱们回顾一些基础知识。卷积是利用于两个函数的数学运算。让咱们从一维案例开始：

间断一维卷积

离散一维卷积

换句话说：取两个信号，保留一个而后围绕坐标轴翻转另一个信号。将固定信号上的翻转信号从负无穷挪动到正无穷（或直到信号的所有非零局部都已重叠）。对于每一步计算元素乘积并对所有值求和。后果值就是此步骤的卷积后果。

然而为什么我之前提到了相互关呢？那是因为卷积和相互关实际上是相以同的形式计算的，惟一的区别是过滤器（核）被翻转了。这由不同的符号示意：

TensorFlow 和 PyTorch 实际上是在计算输出信号和可学习卷积核的相互关，而不是卷积自身。因为卷积核是由网络学习的，因而卷积核是否翻转并不重要。网络会本人弄清楚什么是最好的后果。框架甚至能够节俭一些计算而不进行翻转操作。然而有一个区别，如果卷积核是固定的，当你加载一个训练好的模型时，应该晓得它是应用相互关还是卷积训练的，因为须要晓得最终是否翻转的权重。

下面说的次要总结为两个问题：

计算输入序列中的单个点须要进行大量计算。
输出信号越大（即图像的分辨率越高），核必须更频繁地挪动，因而须要更多的计算。同样实用于大核。

更多的计算意味着更多的内存和更大的计算提早。CNN 在较低的输出分辨率和更小的过滤器。更少的像素意味着更少的细节，更小的过滤器会导致更小的感触野。网络须要有多个间断的卷积层，以减少感触野。网络变得更深，这再次在训练期间带来了新的挑战。

从数学上讲，工夫变量 t 的实数或复数函数 x(t) 的傅里叶变换是实数频率变量 f 的复数函数 X(f)：

也能够说咱们将信号从时域投影到频域。通过这样做能够受害于傅里叶变换的非凡性质，即卷积定理和相干定理。

卷积定理

相互关定理

这些概念十分重要也是本文的根底：时域中的卷积 / 相干对应于频域中的简略元素乘法。但这有什么用的呢？如前所述，卷积须要很多计算，尤其是对于大像素图像和大核。它的复杂性与序列长度成二次方，即 O(N²)。依据卷积定理，咱们只须要对变换后的输出和变换后的核进行逐元素的乘法。并且计算傅里叶变换的高效算法，即疾速傅里叶变换 (FFT)可将复杂度升高到 O(N log(N))。而且更重要的是只有核比输出信号小，那么计算的复杂度就是恒定的。所以核大小是 [3,3] 还是 [1024, 1024] 并不重要。

傅里叶变换也实用于实数或复数离散信号 x[k]，它调配实变量 n 的复数离散信号 X[n]：

一维卷积

二维卷积

离散傅里叶变换 (DFT) 是用于数字信号处理，而计算机以离散值存储信号。所以在应用 DFT 时，咱们须要记住：

假如输出信号是周期性的，并且对整个周期进行采样
产生的频谱是周期性的

图像能够解释为空间信号而不是工夫信号。在计算机上图像是空间离散的，因为值存储在像素中这些像素从具备空间散布单元的图像传感器采样而被数字化。

二维 DFT（以及 2D 间断傅里叶变换）能够分成间断的 1D DFT，其中行和列能够别离计算。

这有两个长处：首先，能够重用 1D DFT 的算法；其次，它有助于为 2D DFT 建设直觉，因为能够独自解释行和列。

但离散傅里叶变换有一个小细节：卷积定理不适用于 DFT。两个信号的 DFT 相乘对应于它们的循环卷积，由运算符 ⊛ 示意，而不是它们的线性卷积。

上图为 DFT 的循环卷积定理公式

循环卷积是一个以信号长度 N 的反复周期性信号，而线性卷积的长度为 (N+F-1)，其中 F 是滤波器信号（核）的长度。因而如果自觉地在频域中取乘积，会将长度为 (N+M-1) 的信号压缩到长度 N。它能够被视为时域中的混叠，从而在最终后果中产生不心愿的伪影。然而循环和线性卷积会共享的值，即 (N-F+1)。而残余的 (F-1) 值被包裹并干扰信号的其余值。

如果包裹烦扰的值为零，这不就意味着没有烦扰了吗？咱们能够从循环卷积重建线性卷积。当用至多 (F-1) 个零填充信号时，包裹的值就不会烦扰理论值。咱们能够循环地将包裹的值移回其地位并裁剪填充的值。

当初咱们曾经介绍了实践，让咱们看看一些 2D 傅里叶变换并增强咱们对 2D 傅里叶变换的了解。

思考一个像素强度遵循对角正弦波的图像。能够通过沿图像的每个轴将 2D 傅里叶变换拆散为多个 1D 傅里叶变换来计算 2D 傅里叶变换。如果沿着程度轴行走，就会遇到反复的图案。如果沿着垂直轴行走，状况也是如此。因而在第四象限(右下)，即频率重量为正的象限，很天然地会冀望频谱有一个高值。

注：二维幅度谱通常在绘制时应用对数函数进行缩放，无论图像内容如何图像都具备高偏移量，因为它们通常以无符号整数示意，仅示意正值。

当初，让咱们思考一个具备不同边长的矩形的输出图像。如果再次沿着每个轴行走，会遇到一个在程度轴上具备短脉冲宽度的矩形和一个在垂直轴上具备较宽脉冲宽度的矩形。如果相熟信号实践，会立刻想到的频谱具备某种 sinc 函数，其中 sinc(x)=sin(x)/x。

如果你想到的是一个 sinc 函数，那么你是完全正确的。频谱由沿两个轴的 sinc 函数组成。在这里能够做一个根本的察看：程度轴有更高的频率重量作为垂直轴，零穿插在程度轴上更扩散。这里有两个含意：

输出图像中的窄空间特色在幅度谱中具备高频重量，因而它们具备高带宽。高带宽滤波器容易产生噪声。
光谱与输出图像中特色的空间长度成反比。窄特色导致宽谱，宽特色导致窄谱。

这对咱们的带有小核的 CNN 意味着什么，比方 3×3 像素？依据咱们下面的察看，这应该意味着具备小核的 CNN 充当高带宽滤波器，因而容易产生输出噪声。核尺寸越大，滤波器的带宽越低，选择性越强。

咱们曾经探讨了一些根本信号，当初让咱们钻研实在图像的 2D DFT。

频谱的核心代表零频率，也称为偏移。离核心越远，输出中的频率重量就越高。思考到这一点，能够轻松导出高通滤波器和低通滤波器。

高通滤波器克制低频并保留高频重量。这种行为能够通过一个滤波器来实现，该滤波器在近核心的值设为 0，而将远离核心的值设为 1。滤波器的作用是将滤波器与频谱相乘，而后计算傅里叶反变换。

如上图所示，高通滤波器能够用作边缘检测器。图像中的边缘以像素值的忽然变动为特色，因而具备高梯度。梯度越高，波及的频率越高。

另一方面，低通滤波器克制高频重量并保留低频重量。低通滤波器能够通过在核心区域为 1 而在内部区域为 0 的掩码来实现。

低通滤波后的图像会变得含糊清晰度升高，计算机视觉中应用的一种典型滤波器是高斯滤波器。它也是一个低通滤波器，然而它并不是忽然截止频率，而是会随着频率的升高而逐步增，所以会使图像平滑。

上图的图像含糊，但失真较小。并且看起来更平滑。

用于机器学习利用的一个十分乏味的核是矩形核。卷积神经网络通常会逐步减小空间宽度并减少通道数。池化，例如最大池化或均匀池化通常用于减小空间宽度。如果咱们在频域中进行池化是如何操作的呢？

通过在频域中利用矩形滤波器，咱们能够大幅去除频率重量，而不会对空间域中的图像品质产生很大影响。

DFT 对于理论输出有一个乏味的个性：它对于原点是共轭对称的。对称性意味着频谱蕴含在计算过程中能够省略这样能够进一步放慢计算。下图显示了这种变换及其从频谱重建的图像。

下面介绍了应用离散傅里叶变换实现线性卷积的理论知识。上面咱们进行实际操作

咱们须要实现以下 6 个步骤：

填充输出图像以防止时域中的混叠
将滤波器填充到图像大小筹备逐元素乘法
计算输出图像和滤波器的 2D rFFT
转换后的输出和转换后的过滤器的元素乘法
计算滤波输出的 2D 逆 rFFT 以取得循环卷积
从循环卷积重构线性卷积

1、填充输出图像

为了防止时域中的混叠效应，咱们须要用至多 (F-1) 个零填充图像，其中 F 是滤波器的边长。此外计算 DFT 的 FFT 算法对于 2 次方的信号长度（例如 128,512,1024）特地无效。

填充输出图像至多有两个选项：1、手动填充图像。2、将 FFT 的序列长度设置为填充信号的长度。

上面的代码手动填充图像。

def GetImagePadding(filterSize):
  '''returns the one sided padding to pad an image.'''
  return int((filterSize-1)/2)

def FillImageShapeToPower2(imageShape):
  '''
  fills the image shape to the next higher power of 2 value.
  imageShape: Expected to be of shape [batch, channels, height, width]
  '''
  width = imageShape[-1]
  log2 = np.log2(width)
  newPower = int(np.ceil(log2))
  newShape = 2**newPower
  newShape = (imageShape[0],imageShape[1],newShape,newShape)
  return newShape

def PadImage(image, filterShape):
  '''returns a padded image considering the size of the filter and the next higher power of 2 value'''
  input_shape = tf.shape(image)
  paddingFilter = GetImagePadding(filterShape[0])
  finalShape = FillImageShapeToPower2(input_shape+(0,0,2*paddingFilter,2*paddingFilter))
  final_padding = int((finalShape[-1]-input_shape[-1])/2)
  paddings = [[0,0],
             [final_padding,final_padding],
             [final_padding,final_padding],
             [0,0],
             ]
  image_padded = tf.pad(image,paddings)
  return image_padded

上面是我在计算 FFT 时指定更高序列长度的首选办法：

# 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、将滤波器填充到图像大小

因为须要计算变换后的图像与变换后的滤波器的元素乘积，因而咱们须要在计算傅里叶变换之前将滤波器用零填充填充图像。通过正确设置 FFT 计算的 fft_lenght 参数来填充滤波器，即

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

3、计算 2D rFFT

筹备好输出信号后，能够计算填充图像和填充滤波器的 FFT：

# 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]])

利用理论输出的共轭对称性，仅应用 rfft2d 计算 2D 信号的理论 FFT。输出未填充的信号并将 fft_length 设置为大于输出长度的值。这会主动用零填充信号。

提醒：TensorFlow 的 rfft2d 实现在输出的最初两个维度上计算 FFT。与 numpy 的实现不同，并且不能通过参数更改维度。因而图像的形态是 [batch, channel, height, width]，滤波器的形态是 [output_filter, input_filter, kernel_height,kernel_width]

如果咱们是在频域中实现卷积，这样的工作就实现了。因为 TensorFlow 实际上是应用的相互关，所以须要对变换后的滤波器进行共轭以取得统一的后果：

F_filter = tf.math.conj(F_filter)

4、元素乘法

如果咱们只有一个图像和一个核，那么逐元素乘法将只是 F_image*F_filter。但在理论场景中，通常以批处理的模式解决多个图像，并且并行利用多个核。所以须要重新排列输出信号的维度，并利用数组播送来执行此操作，这样不波及循环操作。

@tf.function
def ElementwiseProduct(a, b):
  '''
  calculates the elementwise product multiple times taking advantage of array broadcasting. 
  Is slower as the matrix multiplication, but requires less memory!
  '''a = tf.einsum("bihw->bhwi",a)
  a = tf.expand_dims(a,-1)      #[b,h,w,in,1]
  b = tf.einsum("oihw->hwio",b) #[h, w, in, out]
  
  c = a*b                       #[b,h,w,in,out] due to broadcasting
  c = tf.einsum("bhwio->bohwi",c)

  c = tf.math.reduce_sum(c, axis=-1) #[b, out, h, w]
  return c

TensorFlow 的 einsum() 函数可用于重塑维度。箭头左侧的字符形容输出形态，右侧的字符形容输入形态。图像和过滤器的尺寸进行从新对齐，当计算元素乘积时，所有批次和所有输入过滤器都将被播送。在乘法之后，通过从新重塑维度和减小输出滤波器的维度来复原初始形态。

5、计算 2D 逆 rFFT

逆 FFT 具备与 FFT 雷同的 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]]
               )

所有步骤就实现了，上面的代码汇总了整个实现:

def CalcDFT2D(image, filter):
'''
Calculates the cross-correlation in the Frequency domain
image: [batch, channel, height, width]
filter: [height, width, inp_filter, out_filter]
'''
  # 0. Preprocess Inputs
  input_shape = tf.shape(image) #[batchsize, im_channel, im_height, im_width]
  filter_shape = tf.shape(filter) #[kernel_H, kernel_W, inp_filter, out_filter]
  filter = tf.einsum("hwio->oihw",filter) # [kernel,kernel,inp_filter,out_filter]->[out_filter, inp_filter, kernel, kernel]
  
  # 1. & 2. Pad image and Filter: 
  # Required to avoid aliasing in spatial domain: circular convolution
  # calculates padding which is used to update image shape. Padding happens during FFT by setting fft_length  
  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)

  # 3. Fourier Transform image and filter
  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]])
  F_filter = tf.math.conj(F_filter) #to be equvivalent to the cross correlation

  # 4. Apply filter by elementwise Multiplication
  filterd_image = ElementwiseProduct(F_image,F_filter)

  # 5. inverse DFT on filtered image
  out = tf.signal.irfft2d(filterd_image, fft_length=[image_shape[-2],image_shape[-1]])
  
  # 6. Reconstruct linear convolution from circular convolution
  out = tf.roll(out,shift = [2*padding,2*padding],axis = [-2,-1]) 
  out = tf.slice(out, begin = [0, 0, padding, padding], size=[input_shape[0], filter_shape[-1], input_shape[2], input_shape[3]])
    
  return out

咱们这写操作这真的有用吗? 让咱们来验证一下

首先，咱们将查看两个函数 (tf.nn.conv2d() 和咱们的实现)在不同的核大小中的执行工夫(以秒为单位)。

2D 卷积的执行工夫随着核大小的减少而一直增长。而 2D DFT 卷积在执行工夫上是恒定的，与滤波器的大小无关。这是因为滤波器被填充到图像的大小。如果滤波器更大，则填充的值能够更少。

当初让咱们来看看后果的差别。咱们在 720×720 像素的图像上利用一个 3 ×3 大小的核函数，并应用 8 个核。通过两种算法运行它，并计算相对差的平均值和标准差。

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

均值和标准差都很低。这种差别来自于数字的不准确性。当察看滤波后的图像及其对应的振幅谱时，咱们能够看到它们是根本是统一的。

间接比拟滤波后的图像和二维光谱。

2D 线性卷积后果

2D DFT 卷积后果

本文介绍了卷积和 DFT 背地的数学实践，通过观察不同的光谱取得了一些想发，并且通过 TensorFlow 进行了实现，并验证了后果的正确性。

本文的设计在频域而不是空间域工作的，可能还不欠缺然而却给出了一些新的想法，特地是对于大输出图像和大尺寸核的解决上。在应用频域仿佛有违现有的实践，但实际上能够放慢计算速度。

本文的残缺代码请参考上面地址

https://avoid.overfit.cn/post/503f3087e31c4b8fa6b53fee007559a0

作者：Sascha Kirch

关于深度学习:卷积神经网络中的傅里叶变换1024×1024-的傅里叶卷积

卷积的问题

二维离散傅里叶变换

根本测试信号及其对 CNN 的影响

图像的二维 DFT 和频域滤波

TensorFlow 中的实现

验证

论断