- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
傅里叶变换在几乎所有计算相关领域都有可能被使用到,例如通信领域的滤波、材料领域的晶格倒易空间计算还有分子动力学中的倒易力场能量项等等。最简单的例子来说,计算周期性盒子的电势能\(k\sum_i\frac{q_i}{r_i}\)本身就是一个类似于调和级数的形式,很难求得精确解。但是在Edward求和方法中使用傅里叶变换,可以做到在倒易空间进行能量计算,可以逼近精确解。本文主要介绍傅里叶变换的原理及相应的Python代码实现.
DFT计算的本质是一个矩阵运算:
如果写成一个矩阵的形式,那就是:
类似的,逆傅里叶变换的矩阵形式为:
如果记参数\(W_{N,n,k}=e^{-j\frac{2\pi}{N}nk}\),则其共轭\(W_{N,n,k}^*=e^{j\frac{2\pi}{N}nk}\)是逆傅里叶变换的参数。而且根据复变函数的性质,该参数具有周期性:\(W_{N,n+N,k}=W_{N,n,k+N}=W_{N,n,k}\),共轭参数同理。最后还有一个非常重要的性质:\(W_{N/m,n/m,k}=W_{N/m,n,k/m}=W_{N,n,k}\),根据这个特性,可以将大规模的运算变成小范围的计算。在不考虑这些参数特性的情况下,我们可以使用Python做一个初步的DFT简单实现.
这里没有做任何的优化,仅仅是一个示例:
import numpy as np
def dft(x):
y = np.zeros_like(x, dtype=np.complex64)
N = x.shape[0]
for k in range(N):
y[k] = np.sum(x * np.exp(-1j*2*np.pi*k*np.arange(N)/N))
return y
def idft(y):
x = np.zeros_like(y, dtype=np.float32)
N = y.shape[0]
for n in range(N):
x[n] = np.real(np.sum(y * np.exp(1j*2*np.pi*n*np.arange(N)/N)) / N)
return x
N = 128
x = np.random.random(N).astype(np.float32)
y0 = dft(x)
y1 = np.fft.fft(x)
print (np.allclose(y0, y1))
yr = np.random.random(N).astype(np.float32)
yi = np.random.random(N).astype(np.float32)
y = yr + 1j*yi
x0 = idft(y)
x1 = np.fft.ifft(y).real
print (np.allclose(x0, x1))
# True
# True
输出的两个结果都是True,也就说明这个计算结果是没问题的.
首先我们整理一下所有参数相关的优化点:
此时如果我们把原始的输入\(x_n\)拆分为奇偶两组(如果总数N不是偶数,一般可以对输入数组做padding):
则有:
如果我们把\(x_{2r}\)和\(x_{2r+1}\)看作是两个独立的输入数据,那么上述分解可以进一步优化:
同理可以得到:
这就是所谓的蝶形运算(图像来自于参考链接):
import numpy as np
def dft(x):
y = np.zeros_like(x, dtype=np.complex64)
N = x.shape[0]
for k in range(N):
y[k] = np.sum(x * np.exp(-1j*2*np.pi*k*np.arange(N)/N))
return y
def dft2(x):
y = np.zeros_like(x, dtype=np.complex64)
N = x.shape[0]
for k in range(N//2):
c1 = np.exp(-1j*2*np.pi*k*np.arange(N//2)/(N//2))
c2 = np.exp(-1j*2*np.pi*k/N)
y1 = np.sum(x[::2] * c1)
y2 = np.sum(x[1::2] * c1)
y[k] = y1 + c2 * y2
y[k+N//2] = y1 - c2 * y2
return y
N = 128
x = np.random.random(N).astype(np.float32)
y0 = dft2(x)
y1 = np.fft.fft(x)
print (np.allclose(y0, y1))
# True
运行输出为True,表示计算结果一致。需要注意的是,这里的代码未考虑padding问题,不能作为正式的代码实现,仅仅是一个算法演示。既然能够分割一次,那么就可以分割多次,直到无法分割为止,或者分割到一个指定的参数为止。这也就是多重蝶形运算的原理:
简单一点可以使用递归的方式进行计算:
import numpy as np
def dft(x):
y = np.zeros_like(x, dtype=np.complex64)
N = x.shape[0]
for k in range(N):
y[k] = np.sum(x * np.exp(-1j*2*np.pi*k*np.arange(N)/N))
return y
def dftn(x, N_cut=2):
y = np.zeros_like(x, dtype=np.complex64)
N = x.shape[0]
if N > N_cut:
y1 = dftn(x[::2])
y2 = dftn(x[1::2])
else:
return dft(x)
for k in range(N//2):
c2 = np.exp(-1j*2*np.pi*k/N)
y[k] = y1[k] + c2 * y2[k]
y[k+N//2] = y1[k] - c2 * y2[k]
return y
N = 1024
x = np.random.random(N).astype(np.float32)
y0 = dftn(x)
y1 = np.fft.fft(x)
print (np.allclose(y0, y1))
# True
这里的实现使用递归的方法,结合了前面实现的DFT算法和蝶形运算方法,得到的结果也是正确的。这里使用的蝶形运算优化方法,就是FFT快速傅里叶变换的基本思路.
所谓的N点FFT,其实就是每次只取N个数据点执行傅里叶变换。那么取数据点的方式就有很多种了,例如只取前N个数据点,或者降采样之后再取前N个数据点,再就是加窗,在经过窗函数的运算后,对每个窗体内的数据点做傅里叶变换。最简单的方式就是矩形窗,常见的还有汉宁窗和汉明窗,这里不做详细分析。值得注意的是,如果使用降采样的方法,采样率需要遵循奈奎斯特采样定理,要大于两倍的target frequency。尤其对于周期性边界条件和远程相互作用的场景,高频区域的贡献是不可忽视的.
至于为什么不使用全域数据点的傅里叶变换,即使我们可以用快速傅里叶变换把计算复杂度缩减到\(O(N\log N)\)(这里的\(N\)是数据点数)的级别,对于那些大规模数据传输和计算的场景,也是不适用的,因此使用降低傅里叶变换点数的思路对于大多数的场景来说可以兼顾到性能与精确度。而窗体函数的出现,进一步优化了截断处数据泄露的问题.
本文介绍了离散傅里叶变换和快速傅里叶变换的基本原理及其对应的Python代码实现,并将计算结果与numpy所集成的fft函数进行对比。其实现在FFT计算的成熟工具已经有很多了,不论是CPU上scipy的fft模块还是GPU上的cufft动态链接库,都有非常好的性能。但还是得真正去了解计算背后的原理,和相关的物理图像,才能更恰当的使用这个强大的工具.
本文首发链接为:https://www.cnblogs.com/dechinphy/p/fft.html 。
作者ID:DechinPhy 。
更多原著文章:https://www.cnblogs.com/dechinphy/ 。
请博主喝咖啡:https://www.cnblogs.com/dechinphy/gallery/image/379634.html 。
最后此篇关于Python计算傅里叶变换的文章就讲到这里了,如果你想了解更多关于Python计算傅里叶变换的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我正在寻找一种简单的解决方案来将对象从一个地方移动和缩放到另一个地方。 我做了一个JSfiddle用这个代码。问题是我需要它在某个时刻停止变小。所以它有一个最小尺寸,另一个问题是我希望它既缩小又向左移
我正在尝试通过沿 x 轴上下翻转(180 度)来为悬停时的图像设置动画。 就像here 除非我出于某种原因无法让它工作。 img { transition:all 2s ease-in-out
我想实例化一个 slider 约束,它允许 body 在 A 点和 B 点之间滑动。 为了实例化约束,我指定了两个物体进行约束,在这种情况下,一个动态物体被约束到静态世界,比如滑动门。 第三个和第四个
我想使用此功能旋转然后停止在特定点或角度。现在该元素只是旋转而不停止。代码如下: $(function() { var $elie = $("#bkgimg");
我正在尝试使用 CATransform3D 向 View 添加透视图。目前,这就是我得到的: 这就是我想要得到的: 我很难做到这一点。我完全迷失在这里。这是我的代码: CATransform3D t
我编写了一个图形用户界面,用户可以在其中在 (640x480) 窗口中绘制内容。它使该绘图成为一组存储在 Vector 数组中的点。 现在,我如何将这些点集平移到原点(0,0 窗口左上角)或将其放在指
我的应用程序中有两张图像相互叠加,分别表示为 foreground 和 background。对于这两个,我都使用 background-attachment: fixed 来确保图像始终彼此完全相同
如何在不损失质量的情况下应用旋转变换?我试过添加 translateZ(0) 但它无济于事。这是例子: svg { background-color: rgb(93, 193, 93); }
我有一个 div,我试图在悬停时缩放它(只是 Y)。问题是它在没有过渡的情况下运行良好。当我使用过渡时,div 在顶部缩放一点然后下降,检查 fiddle 。问题是如何防止 div 那样缩放?我希望它
我正在尝试使用 transform: scale 图像网格 http://movies.themodern-nerd.com/genre .从左向右滚动时它工作正常,悬停的图像将停留在其他图像之上,但
我正在查看 CSS3 Transform 并且想要一个既倾斜又旋转的盒子。 我试过使用: transform:rotate(80deg); -moz-transform:rotate(80deg);
当用户在图像父元素上执行 mousemove 时,我试图在 img 上添加平滑移动效果(此处为 .carousel-img)但我无法正常运行它。 我做错了什么? $('.carousel-img').
我有 div 元素在其他 div 元素中垂直对齐。 我使用以下方法对齐它们:position: relative;变换:翻译Y(-50%);顶部:50%。这很好用。 我现在想缩放元素(使用 jQuer
我在这个 fiddle 中使用 RotateX 后创建了 3D 效果: http://jsfiddle.net/vEWEL/11/ 但是,我不确定如何在这个 Fiddle 中的红色方 block 上实
使用 transform: scale(x.x) 而不是使用 width 和 height 属性进行传统的调整大小有什么缺点吗?缩放会产生质量较低的图像或其他什么吗? 最佳答案 Scale 生成总体上
我在一个点上有一个对象,比如相对于原点的 x、y、z。 我想对点应用一些变换,比如旋转和平移,并在变换后的点渲染对象。我正在使用 glTranslatef() 和 glRotatef() 函数。它看起
有没有办法将转换应用到插入了 :before 的元素上? 以下方法无效,但我愿意接受其他解决方案。 .itemclass:before { content: "➨"; transform:
我找到了这个:width/height after transform 和其他几个,但没有什么不是我正在寻找的。我想要的是将某些东西缩放到其大小的 50%(当然还有漂亮的动画过渡)并让页面布局重新调整
我想使用变换为元素位置设置动画。我怎么能在这个翻译中添加一些曲线(没什么特别的,只是不是一条完整的直线)?对于 jquery,我会使用效果很好的 easeInSine。 var a = documen
我试着写一个 TransformMesh功能。该函数接受一个 Mesh对象和 Matrix目的。这个想法是使用矩阵来转换网格。为此,我锁定了顶点缓冲区,并在每个顶点上调用了 Vector3::Tran
我是一名优秀的程序员,十分优秀!