理论基础
时域：以时间为横坐标
频域：以频率的倒数为横坐标，可以看出，频域更加简单。

相位：与时间差有关的一个概念。

傅里叶说，任何连续周期信号，可以由一组适当的正弦曲线组合而成。我们知道，正弦曲线可以转换为频域信号，所以：任何连续周期信号，都可以转换成频域信号。并且这个过程是可逆的。

程序实现
1. 傅里叶变换

numpy.fft.fft2
1
实现傅里叶变换。
返回一个复数数组。
numpy.fft.fftshift    效果如图所示
将零频率分量移到频谱中心。    
20*np.log( np.abs( fshift ) )
1
将傅里叶变换的计算结果映射到【0,255】这个区间内。

import cv2
import numpy as np
import matplotlib.pyplot as plt

o=cv2.imread('image\\equ2.bmp',0)
f=np.fft.fft2(o)                              #傅里叶变换
fshift=np.fft.fftshift(f)                     #零频率移到中心
result= 20 * np.log(np.abs(fshift))           #阈值转换
plt.subplot(121),plt.imshow(o,cmap='gray'),plt.title('original'),plt.axis('off')
plt.subplot(122),plt.imshow(result,cmap='gray'),plt.title('result'),plt.axis('off')
plt.show()

1
2
3
4
5
6
7
8
9
10
11
12

2. 逆傅里叶变换

numpy.fft.ifft2
1
实现逆傅里叶变换。
返回一个复数数组。
numpy.fft.ifftshift
1
fftshift的逆函数,将低频从中心移到左上角。

iimg=np.abs( 逆傅里叶变换结果)
1
设置值得范围

将图像进行傅里叶变换后，再进行逆傅里叶变换，与原图片对比。

import cv2
import numpy as np
import matplotlib.pyplot as plt

o=cv2.imread('image\\boat.bmp',0)
f=np.fft.fft2(o)
fshift=np.fft.fftshift(f)                     #傅里叶变换
ishift=np.fft.ifftshift(fshift)
io=np.fft.ifft2(ishift)
io=np.abs(io)                                 #逆傅里叶变换
plt.subplot(121),plt.imshow(o,cmap='gray'),plt.title('original'),plt.axis('off')
plt.subplot(122),plt.imshow(io,cmap='gray'),plt.title('result'),plt.axis('off')
plt.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14

本专栏主要介绍如果通过OpenCv-Python进行图像处理，通过原理理解OpenCv-Python的函数处理原型，在具体情况中，针对不同的图像进行不同等级的、不同方法的处理，以达到对图像进行去噪、锐化等一系列的操作。同时，希望观看本专栏的小伙伴可以理解到OpenCv进行图像处理的强大哦，如有转载，请注明出处(原文链接和作者署名)，感谢各位小伙伴啦！

前文参考：
《OpenCv视觉之眼》Python图像处理一 :Opencv-python的简介及Python环境搭建
《OpenCv视觉之眼》Python图像处理二 :Opencv图像读取、显示、保存基本函数原型及使用
《OpenCv视觉之眼》Python图像处理三 :Opencv图像属性、ROI区域获取及通道处理
《OpenCv视觉之眼》Python图像处理四 :Opencv图像灰度处理的四种方法及原理
《OpenCv视觉之眼》Python图像处理五 :Opencv图像去噪处理之均值滤波、方框滤波、中值滤波和高斯滤波

上次博客，我们讲解了OpenCV图像去噪的几种基本方法，包括均值滤波、中值滤波、高斯滤波等，也就是在图像时域上进行去噪的方法，其中，高斯滤波和中值滤波是需要重点掌握的图像去噪方法，因为对图像的高斯噪声和椒盐噪声去除的效果比较好；除了以上时域上的去噪方法之外，OpenCV也提供了对图像频域上的去噪的函数方法，例如高通滤波和低通滤波，通常用作图像除噪、图像增强和锐化等，因此，高通滤波和低通滤波也是我们学习OpenCV需要掌握的两种图像去噪的方法，但由于高通和低通滤波的实现原理是通过傅里叶变换后进行处理，然后通过傅里叶逆变换进行实现的，所以首先我们需要了解图像傅里叶变换和傅里叶逆变换的原理。

本次博客，林君学长将带大家了解OpenCV图像的傅里叶变换和逆变换原理，通过原理编写傅里叶变换和逆变换的功能函数，并同时介绍OpenCV傅里叶变换和逆变换的库函数使用方法，一起学习吧！

在进行傅里叶变换学习时，我们必须要明白为什么要在频率域研究图像增强？

• 可以利用频率成分和图像外表之间的对应关系。一些在空间域表述困难的增强任务，在频率域中变得非常普通
• 滤波在频率域更为直观，它可以解释空间域滤波的某些性质
• 可以在频率域指定滤波器，做反变换，然后在空间域使用结果滤波器作为空间域滤波器的指导
• 一旦通过频率域试验选择了空间滤波，通常实施都在空间域进行

提示：傅里叶变换是为后面低通滤波或者说是高通滤波做准备哦，一般来说，处理的是灰度图像，通过上面的介绍我们也可以看出，但下面的原理我们通过处理彩色图像编写的，而OpenCV库函数是在处理灰度图像基础上实现的

一、傅里叶变换

• 傅里叶变换（Fourier Transform，FT）后，对同一事物的观看角度随之改变，可以从频域里发现一些从时域里不易察觉的特征。某些在时域内不好处理的地方，在频域内可以容易地处理。

1、傅里叶变换原理

1）、什么是傅里叶变换？
能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。傅里叶变换是一种分析信号的方法，它可分析信号的成分，也可用这些成分合成信号。许多波形可作为信号的成分，比如正弦波、方波、锯齿波等，傅里叶变换用正弦波作为信号的成分。
傅里叶变换的实质是将一个信号分离为无穷多多正弦/复指数信号的加成，也就是说，把信号变成正弦信号相加的形式——既然是无穷多个信号相加，那对于非周期信号来说，每个信号的加权应该都是零——但有密度上的差别，你可以对比概率论中的概率密度来思考一下——落到每一个点的概率都是无限小，但这些无限小是有差别的所以，傅里叶变换之后，横坐标即为分离出的正弦信号的频率，纵坐标对应的是加权密度。

2）、傅里叶变换作用？
傅里叶变换可以将一个时域信号转换成在不同频率下对应的振幅及相位，其频谱就是时域信号在频域下的表现，而反傅里叶变换可以将频谱再转换回时域的信号。最简单最直接的应用就是时频域转换。将图像时域处理上面复杂的特征转为频域实现简单化，对简单化的特征进行处理，然后再通过傅里叶逆变换回到原来的图像，如下所示：

3）、图像进行傅里叶变换原理
我们知道，灰度图像是由二维的离散的点构成的。二维离散傅里叶变换（Two-Dimensional Discrete Fourier Transform）常用于图像处理中，对图像进行傅里叶变换后得到其频谱图。频谱图中频率高低表征图像中灰度变化的剧烈程度。图像中边缘和噪声往往是高频信号，而图像背景往往是低频信号。我们在频率域内可以很方便地对图像的高频或低频信息进行操作，完成图像去噪，图像增强，图像边缘提取等操作，因此，对图像进行傅里叶变换的原理如下公式：
$$\begin{gathered} F(u,v)=\sum _{x=0}^{H-1}\sum _{y=0}^{W-1}f(x,y)e^{-2j\pi (ux/H+vy/W)} \\ 图像高H，宽W。F(u,v)表示频域图像，f(x,y)表示时域图像。u的范围为[0,H-1]，v的范围为[0,W-1]\uparrow \end{gathered}$$
那么怎么将上面的二维公式转为我们可以理解的二维图像呢？其实很简单，$f(x,y)$表示在(x，y)点上的图像的像素值，该像素值乘以后面的在(u,v)点的$e^{-2j\pi (ux/H+vy/W)}$处理出来的一个数，然后对图像所有像素进行遍历，最后求和，就得到在频域上该(u,v)点对应的值，通过该原理，我们就可以自己写出傅里叶变换的功能函数了，来看吧

2、自定义傅里叶变换功能函数

1）、自定义傅里叶变换函数

import cv2
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] #显示中文
#自定义傅里叶变换功能函数
def dft(img):
    #获取图像属性
    H,W,channel=img.shape
    #定义频域图，从公式可以看出为求出结果为复数，因此，需要定义为复数矩阵
    F = np.zeros((H, W,channel), dtype=np.complex)
    # 准备与原始图像位置相对应的处理索引
    x = np.tile(np.arange(W), (H, 1))
    y = np.arange(H).repeat(W).reshape(H, -1)
    #通过公式遍历
    for c in range(channel):#对彩色的3通道数进行遍历
        for u in range(H):
            for v in range(W):
                F[u, v, c] = np.sum(img[..., c] * np.exp(-2j * np.pi * (x * u / W + y * v / H))) / np.sqrt(H * W)
    return F

2）、读取图像，进行傅里叶变化并显示变换后的结果

#读取图像
img=cv2.imread("my.jpg")
#进行图像裁剪，加快傅里叶运算速率。将原始尺寸缩放为100*100的尺寸
img = cv2.resize(img, (100, 100), interpolation=cv2.INTER_CUBIC)
#BGR转换为RGB显示格式，方便通过matplotlib进行图像显示
img=cv2.cvtColor(img,cv2.COLOR_BGR2RGB)
#调用傅里叶变换函数
result =dft(img)
#将傅里叶频谱图从左上角移动到中心位置
fshift = np.fft.fftshift(result)
#将复数转为浮点数进行傅里叶频谱图显示
fimg = np.log(np.abs(fshift))
#图像显示
plt.subplot(121), plt.imshow(img), plt.title('原图像')
plt.axis('off')
plt.subplot(122), plt.imshow(fimg), plt.title('傅里叶变换')
plt.axis('off')
plt.show()

上图是将原图进行缩放之后进行傅里叶变换的，只为了降低函数运行时间，尽快的得出结果；当然，OpenCV中也提供了图像傅里叶变换的库函数，接下，我们介绍OpenCV中傅里叶库函数的使用！

3、OpenCV库函数实现傅里叶变换

OpenCV 中相应的函数是cv2.dft()和用Numpy输出的结果一样，但是是双通道的。第一个通道是结果的实数部分，第二个通道是结果的虚数部分，并且输入图像要首先转换成 np.float32 格式。
1）、函数原型：img=cv2.dft(src, flags=None, nonzeroRows=None)

• src表示输入图像，需要通过np.float32转换格式
• flags表示转换标记，其中DFT _INVERSE执行反向一维或二维转换，而不是默认的正向转换；DFT _SCALE表示缩放结果，由阵列元素的数量除以它；DFT _ROWS执行正向或反向变换输入矩阵的每个单独的行，该标志可以同时转换多个矢量，并可用于减少开销以执行3D和更高维度的转换等；DFT _COMPLEX_OUTPUT执行1D或2D实数组的正向转换，这是最快的选择，默认功能；DFT _REAL_OUTPUT执行一维或二维复数阵列的逆变换，结果通常是相同大小的复数数组，但如果输入数组具有共轭复数对称性，则输出为真实数组
• nonzeroRows表示当参数不为零时，函数假定只有nonzeroRows输入数组的第一行（未设置）或者只有输出数组的第一个（设置）包含非零，因此函数可以处理其余的行更有效率，并节省一些时间；这种技术对计算阵列互相关或使用DFT卷积非常有用

注意，由于输出的频谱结果是一个复数，需要调用cv2.magnitude()函数将傅里叶变换的双通道结果转换为0到255的范围
2）、cv2.magnitude()函数原型：cv2.magnitude(x, y)

• x表示浮点型X坐标值，即实部
• y表示浮点型Y坐标值，即虚部

最终输出结果为幅值，即：

$$img(I)=\sqrt{x(I{)}^2+y(I{)}^2}$$
3）、傅里叶库函数使用

#傅里叶库函数使用
import cv2
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] #显示中文
#读取图像
img=cv2.imread("my.jpg",0)
#进行图像裁剪，加快傅里叶运算速率。将原始尺寸缩放为100*100的尺寸
#OpneCV傅里叶变换函数
result =cv2.dft(np.float32(img),flags = cv2.DFT_COMPLEX_OUTPUT)#需要将图像进行一次float转换
#将频谱低频从左上角移动至中心位置
dft_shift = np.fft.fftshift(result)
#频谱图像双通道复数转换为0-255区间
result1 = 20*np.log(cv2.magnitude(dft_shift[:,:,0], dft_shift[:,:,1]))
#图像显示
plt.subplot(121), plt.imshow(img,'gray'), plt.title('原图像')
plt.axis('off')
plt.subplot(122), plt.imshow(result1,'gray'), plt.title('傅里叶变换')
plt.axis('off')
plt.show()

使用OpenCV函数需要先将图像转为灰度图，然后才能进行处理，这里林君学长再介绍一个Numpy库的傅里叶变换处理，给出相关代码，小伙伴们自己理解哈，不做说明哦！
4）、扩展：Numpy库的图像傅里叶变换

#Numpy傅里叶变换
import cv2 as cv
import numpy as np
from matplotlib import pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] #显示中文
#读取图像灰度图像
img = cv.imread('my.jpg',0)
#快速傅里叶变换算法得到频率分布
f = np.fft.fft2(img)
#默认结果中心点位置是在左上角,
#调用fftshift()函数转移到中间位置
fshift = np.fft.fftshift(f)       
#fft结果是复数, 其绝对值结果是振幅
fimg = np.log(np.abs(fshift))
#展示结果
plt.subplot(121), plt.imshow(img,'gray'), plt.title('原图像')
plt.axis('off')
plt.subplot(122), plt.imshow(fimg,'gray'), plt.title('傅里叶变换')
plt.axis('off')
plt.show()

二、傅里叶逆变换

1、傅里叶逆变换原理

1）、傅里叶反变换原理就是将图像频域还原为图像时域，具体原理公式如下所示：
$$\begin{gathered} f(x,y)=\sum _{u=0}^{H-1}\sum _{v=0}^{W-1}F(u,v)e^{2j\pi (ux/H+vy/W)} \\ 图像高H，宽W。f(x,y)表示时域图像,F(u,v)表示频域图像。x的范围为[0,H-1]，y的范围为[0,W-1]\uparrow \end{gathered}$$
对于公式的理解，和上面傅里叶变换公式理解一致

2、自定义傅里叶逆变换功能函数

1）、自定义傅里叶逆变换功能函数

import cv2 as cv
import numpy as np
from matplotlib import pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] #显示中文
#傅里叶反变换
def idft(G):
    H, W, channel = G.shape
    #定义空白时域图像
    out = np.zeros((H, W, channel), dtype=np.float32)
    # 准备与原始图像位置相对应的处理索引
    x = np.tile(np.arange(W), (H, 1))
    y = np.arange(H).repeat(W).reshape(H, -1)
    #通过公式遍历
    for c in range(channel):
        for u in range(H):
            for v in range(W):
                out[u, v, c] = np.abs(np.sum(G[..., c] * np.exp(2j * np.pi * (x * u / W + y * v / H)))) / np.sqrt(W * H)
    # 剪裁
    out = np.clip(out, 0, 255)
    out = out.astype(np.uint8)
    return out

2）、调用函数，先进行傅里叶变换，然后进行傅里叶逆变换并显示结果

#读取图像
img=cv2.imread("my.jpg")
#进行图像裁剪，加快傅里叶运算速率。将原始尺寸缩放为100*100的尺寸
img = cv2.resize(img, (100, 100), interpolation=cv2.INTER_CUBIC)
#BGR转换为RGB显示格式，方便通过matplotlib进行图像显示
img=cv2.cvtColor(img,cv2.COLOR_BGR2RGB)
#调用傅里叶变换函数,先将图像进行傅里叶变换，该函数上面我们通过原理写出了哦！
result =dft(img)
#将傅里叶频谱图从左上角移动到中心位置
fshift = np.fft.fftshift(result)
#将复数转为浮点数进行傅里叶频谱图显示
fimg = np.log(np.abs(fshift))
#调用傅里叶逆变换函数
result2=idft(result)
#图像显示
plt.subplot(131), plt.imshow(img), plt.title('原图像')
plt.axis('off')
plt.subplot(132), plt.imshow(fimg), plt.title('傅里叶变换')
plt.axis('off')
plt.subplot(133), plt.imshow(result2), plt.title('傅里叶逆变换')
plt.axis('off')
plt.show()

最后我们可以看出，我们通过原理书写的傅里叶变换和傅里叶逆变换是没有问题的，因此，而且傅里叶反变换的结果是和之前的图像一模一样的，几乎没有什么损失，后面我们将会讲到在傅里叶变换的基础上实现高通或者说是低通滤波，来对图像去噪，记得收看啦！

3、OpenCV库函数实现傅里叶逆变换

OpenCV中也提供了傅里叶逆变换的库函数，我们一起看一下函数原型吧
1）、函数原型img=cv2.idft(src,flags,nonzeroRows)

• src表示输入图像，包括实数或复数
• flags表示转换标记
• nonzeroRows表示要处理的img行数，其余行的内容未定义

2）、OpenCV库函数实现傅里叶逆变换的完整代码如下所示：

#OpenCV实现傅里叶逆变换
import cv2 as cv
import numpy as np
from matplotlib import pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] #显示中文

#读取图像
img = cv2.imread('my.jpg', 0)
#傅里叶变换
dft = cv2.dft(np.float32(img), flags = cv2.DFT_COMPLEX_OUTPUT)#傅里叶变换库函数调用
dftshift = np.fft.fftshift(dft)#将傅里叶频域从左上角移动到中间
res1= 20*np.log(cv2.magnitude(dftshift[:,:,0], dftshift[:,:,1]))#双通道结果转换为0到255的范围用于图像显示
#傅里叶逆变换
ishift = np.fft.ifftshift(dftshift)#将频域从中间移动到左上角
iimg = cv2.idft(ishift)#傅里叶逆变换库函数调用
res2 = cv2.magnitude(iimg[:,:,0], iimg[:,:,1])#双通道结果转换为0到255的范围
#显示图像
plt.subplot(131), plt.imshow(img, 'gray'), plt.title('原图像')
plt.axis('off')
plt.subplot(132), plt.imshow(res1, 'gray'), plt.title('傅里叶变换')
plt.axis('off')
plt.subplot(133), plt.imshow(res2, 'gray'), plt.title('傅里叶逆变换')
plt.axis('off')
plt.show()

3）、扩展：Numpy库也提供图像了傅里叶变换，完整代码如下所示：

#Numpy库的傅里叶变换
import cv2 as cv
import numpy as np
from matplotlib import pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] #显示中文
#读取图像
img = cv.imread('my.jpg',0)
#傅里叶变换
f = np.fft.fft2(img) #Numpy的库函数傅里叶变换
fshift = np.fft.fftshift(f)
res = np.log(np.abs(fshift))
#傅里叶逆变换
ishift = np.fft.ifftshift(fshift)
iimg = np.fft.ifft2(ishift) #Numpy的库函数傅里叶逆变换
iimg = np.abs(iimg)#将复数变为实数
#展示结果
plt.subplot(131), plt.imshow(img,'gray'), plt.title('原图像')
plt.axis('off')
plt.subplot(132), plt.imshow(res,'gray'), plt.title('傅里叶变换')
plt.axis('off')
plt.subplot(133), plt.imshow(iimg,'gray'), plt.title('Inverse Fourier Image')
plt.axis('off')
plt.show()

以上就是本次博客的全部内容，遇到问题的小伙伴记得留言评论，学长看到会为大家进行解答的，这个学长不太冷！

任何的收获不是巧合，而是每天的努力与坚持得来的。人生因有梦想，而充满动力。
不怕你每天迈一小步，只怕你停滞不前；不怕你每天做一点事，只怕你无所事事。 坚持，是生命的一种毅力！执行，是努力的一种坚持！

陈一月的又一天编程岁月^ _ ^

原文首发于个人站点 图卷积网络GCN（Graph Convolution Network）（二）图上的傅里叶变换和逆变换
公众号：【DreamHub】

由于文章篇幅较长，因此将其分解为三部分：

• 图卷积网络GCN（Graph Convolution Network）（一）研究背景和空域图卷积
• 图卷积网络GCN（Graph Convolution Network）（二）图上的傅里叶变换和逆变换
• 图卷积网络GCN（Graph Convolution Network）（三）详解三代图卷积网络理论

背景知识

如要了解谱图卷积，首先需要学习图理论基础和图中如何进行傅里叶变换。

对于傅里叶变换，本文不再赘述。详细内容可以参考：

• 理解傅里叶变换 | 隐舍
• 深入理解傅里叶变换

图上的傅立叶变换

傅立叶变换是将时域的函数转换成频域上的函数，是对于同一个函数的不同视角，数学定义如下：
$$\mathcal{F}(w)=\mathcal{F}(f(t))=\int f(t)e^{-iwt}dt(1)$$
公式（1）表示的意义是傅立叶变换是时域信号 $f(t)$ 与基函数 $e^{-iwt}$ 的积分。

为什么选择$e^{-iwt}$作为基函数？原因有二：

• $e^{-iwt}$是正交函数系。
• $e^{-iwt}$是拉普拉斯算子$\Delta$的特征函数。

至于$e^{-iwt}$由何种推导得来的请参考： 理解傅里叶变换 | 隐舍

先解释下拉普拉斯算子$\Delta$的定义

在数学中，拉普拉斯算子（Laplacian）是由欧几里得空间中的一个函数的梯度的散度给出的微分算子，记为$\Delta f={\nabla }^{2}f=\nabla \cdot \nabla f$，表示$n$维空间笛卡尔坐标系$x_i$中所有非混合二阶偏导数之和，其数学定义为
$$\Delta =\sum _{i=1}^n\frac{{\partial }^2}{\partial {}^2{x}_i}(2)$$
这表达式什么意思呢？以二维空间为例：
$$\begin{array}{rl}\Delta f(x,y)& =\frac{{\partial }^{2}f}{\partial x^2}+\frac{{\partial }^{2}f}{\partial y^2}\\ & =[f(x+1,y)+f(x-1,y)-2f(x,y)]+[f(x,y+1)+f(x,y-1)-2f(x,y)]\\ & =f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y)\end{array}$$
上式中每一项的系数就是拉普拉斯在二维图像中的卷积核：

再解释下$e^{-iwt}$为何拉普拉斯算子$\Delta$的特征函数

拉普拉斯算子的特征方程为：
$$\Delta g=\lambda g(3)$$

代入函数$e^{-iwt}$可得：

$$\Delta e^{-iwt}=\frac{{\partial }^2}{{\partial }^2{x}_i}{e}^{-iwt}=\frac{{\partial }^2}{{\partial }^{2}t}{e}^{-iwt}=-w^2{e}^{-iwt}(4)$$

其中特征值 $\lambda =-w^2$ ，即 $w$ 和特征值 $\lambda$ 密切相关。

由上述证明可得结论：傅立叶变换是时域信号与拉普拉斯算子特征函数的积分。

从整体推特殊，将以上的结论推广到（离散）图中可知：图上的傅立叶变换就是时域信号与图拉普拉斯算子特征函数的求和！

对于傅里叶变换式（1），将特征函数转换为特征向量（特征函数可以认为是无限维的特征向量），将积分转换为求和，那么$N$个顶点图上的傅立叶变化表达式为：
$$\mathcal{F}({\lambda }_l)=\hat{f}({\lambda }_l)=\sum _{i=1}^{N}f(i)\ast u_l(i)(5)$$

其中， ${\lambda }_l$ 为图拉普拉斯算子第 $l$ 个特征值， $u_l$ 为第 $l$ 个特征值对应的特征向量，公式（5）是
${\lambda }_l$ 对应的傅立叶变换，对于图拉普拉斯算子，具有$N$个特征值，将式 (5) 全部分量展开可得：
$$\left(\begin{array}{c}\hat{f}\left({\lambda }_1\right)\\ \hat{f}\left({\lambda }_2\right)\\ ⋮\\ \hat{f}\left({\lambda }_N\right)\end{array}\right)=\left(\begin{array}{cccc}{u}_1(1)& u_1(2)& \dots & u_1(N)\\ u_2(1)& u_2(2)& \dots & u_2(N)\\ ⋮& ⋮& \ddots & ⋮\\ u_N(1)& u_N(2)& \dots & u_N(N)\end{array}\right)\left(\begin{array}{c}f(1)\\ f(2)\\ ⋮\\ f(N)\end{array}\right)(6)$$

将公式（6）写成矩阵形式即为：
$$\hat{f}=U^{T}f(7)$$
此处$U$为拉普拉斯谱分解的正交矩阵。

最后再来看看图中拉普拉斯算子的定义：
$$L=D-W(8)$$
其中$W$是邻接矩阵，$D$是度矩阵，$D_{i,i}$等于$W$矩阵的第$i$行的和，非对角线上元素为0，$D$是个对角矩阵，这个图谱理论关于图拉普拉斯算子的的定义。详细推到过程参考：图拉普拉斯算子为何定义为D-W

拉普拉斯矩阵是实对称矩阵，实对称矩阵一定可以用正交矩阵进行正交相似对角化（特征分解）：

$$L=U\left(\begin{array}{ccc}{\lambda }_1& & \\ & \ddots & \\ & & {\lambda }_N\end{array}\right)U^{-1}=U\left(\begin{array}{ccc}{\lambda }_1& & \\ & \ddots & \\ & & {\lambda }_N\end{array}\right)U^T(9)$$

$U$ 为特征向量构成的正交矩阵，而正交矩阵的逆等于正交矩阵的转置：$U^{-1}=U^T$

假定 ${\lambda }_1,\cdots ,{\lambda }_n$ 从小到大排序，其对应的特征向量为 $u_1,\cdots ,u_n$，特征值越小，对应的特征向量越平稳，这和傅立叶变换中频率的定义是类似的。下图是对 random sensor network 做特征值分解后的特征向量分布展示，可以看到特征值越小，对应的特征向量越平滑。

图上傅里叶逆变换

有了傅立叶变换，如何将频率函数变换为时域函数呢？这是傅立叶逆变换需要干的事情，公式如下：

$${\mathcal{F}}^{-1}[\mathcal{F}(w)]=\frac{1}{2\pi }\int \mathcal{F}(w)e^{-iwt}dw(10)$$

公式（10）和公式（1）类似，差一个常数系数。公式（1）积分之后是一个关于 $w$ 的函数，公式(10) 对 $w$ 积分后是关于 $t$ 的函数，从频域变换到了时域，图上傅立叶变换类似为：
$$\left(\begin{array}{c}f\left({\lambda }_1\right)\\ f\left({\lambda }_2\right)\\ \cdots \\ f\left({\lambda }_N\right)\end{array}\right)=\left(\begin{array}{cccc}{u}_1(1)& u_1(2)& \dots & u_1(N)\\ u_1(1)& u_1(2)& \dots & u_1(N)\\ \cdots & \dots & & \dots \\ u_1(1)& u_1(2)& \dots & u_1(N)\end{array}\right)\left(\begin{array}{c}\hat{f}\left({\lambda }_1\right)\\ \hat{f}\left({\lambda }_2\right)\\ \dots \\ \hat{f}\left({\lambda }_N\right)\end{array}\right)(11)$$

写成矩阵形式：
$$f=\mathbf{U}{\mathbf{U}}^{-1}f=\mathbf{U}{\mathbf{U}}^{T}f=\mathbf{U}\hat{f}(12)$$

上述内容详述了如何在图中进行傅里叶变换和逆变换，下面就是主角图卷积网络GCN上场了！

下篇更新的文章将讲述三代图卷积网络的前世今生！

关注作者