[笔记] 二维FFT
阅读原文时间:2023年07月08日阅读:2

假设现在有2个矩阵a和b,分别是n行m列和x行y列,现在你要计算它们的二维卷积,也就是求出矩阵s满足:

\(s_{i,j}=\sum_{i'\leq i,j'\leq j}a_{i',j'}b_{i-i',j-j'}\)

先把两个矩阵的行数都扩展到不小于n+x的最小2的次幂数,列数同理,这个跟普通FFT一样。接下来分5步:

1.对a和b的每一行做普通DFT

2.对a和b的每一列做普通DFT

3.新建矩阵s,\(s_{i,j}=a_{i,j}b_{i,j}\)

4.对s的每一做普通IDFT(别忘了做完之后乘上每列长度的逆元)

5.对s的每一做普通IDFT(别忘了做完之后乘上每行长度的逆元)

然后s就是要求的结果了

证明:咕咕咕

例题

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章