<分区> 分区>
我正在为精准农业应用程序处理根据无人机照片创建的 map ,该应用程序使用 Rhino 6 中的 IronPython 2.7 脚本分析拥有 10,000 棵树的 Orchard 。我使用 FFT 来确定 Y&X 中树木的间距或间距方向。对于 FFT,我从 2015 年 5 月 25 日 StackOverflow 的一篇递归 FFT 帖子开始,该帖子将由 Mike Muller 在 Python 2.7 中运行,
def fft(x):
N = len(x)
T = exp(-2*pi*1j/N)
if N > 1:
x = fft(x[::2]) + fft(x[1::2])
for k in xrange(N/2):
xk = x[k]
x[k] = xk + T**k*x[k+N/2]
x[k+N/2] = xk - T**k*x[k+N/2]
return x
效果很好。玩代码一段时间后,我使用这段代码获得了超过 2 倍的加速:
from cmath import exp, pi
# Create dictionary for lookup of exp term.
def make_wm(N):
global Xwm
Xwm = {}
for i in range(N.bit_length()-1,0,-1): Xwm[N] = exp(-2j*pi/N); N //= 2
# FFT
def fft(x,N):
N2 = N // 2
if N > 2: x = fft(x[::2],N2) + fft(x[1::2],N2) # When N == 2, x = [x[0],x[1]] is processed below. Thus fft is never called with N = 1.
wm = Xwm[N]; w = 1 # Get initial exp value from dictionary lookup.
for k in xrange(N2): # This loop is executed a total of 0.5*N*log2(N) times.
kn = k + N2
xk = x[k]
t = w*x[kn]
x[k] = xk + t
x[kn] = xk - t
w *= wm # Use multiply to generate subsequent exp terms.
return x
# From the main code, fft is called with:
N = len(X)
make_wm(N)
F = fft(X,N)
# Note: 1 FFT can transform 2 real-data inputs by interleaving the inputs and separating the output:
X = map(complex,yi,xi)
N = len(X)
make_wm(N)
F = fft(X,N)
# Separate two complex outputs of length N/2 from the N-terms in the FFT result.
yfft,xfft = separate_output(F)
此版本消除了一半的递归调用,并从 fft 代码中删除了缓慢的 exp 和 power (T**k) 计算。由于 Y&X 方向的间距都需要,并且用于此计算的 FFT 输入数据是实数值,我通过使用一个 FFT 通过交错 Y&X 数据同时转换两个 Y&X 数据集,获得了另外 2 倍的加速设置使用:
# Interleave two real-data inputs.
X = map(complex,yi,xi)
然后使用以下方法将 FFT 结果分离为 Y&X 分量:
# Separate two N/2-point ffts from one N-point fft.
def separate_output(X):
N = len(X)
N2 = N // 2
# Extend X by copying 0th term to Nth entry so that extracting DC term (k=0) does not cause overflow.
X.append(X[0])
# Separate 2 ffts.
G = [(X[k].real + X[N-k].real + 1j*(X[k].imag - X[N-k].imag))/(2.*N) for k in xrange(N2)]
H = [(X[k].imag + X[N-k].imag - 1j*(X[k].real - X[N-k].real))/(2.*N) for k in xrange(N2)]
return G,H
我无法在 Rhino 6 的 IronPython 中访问 numpy 的 FFT,后者会快得多。
我的问题:
- 有没有办法进一步加速 Python 2.7 中的 fft?
- 非递归版本会更快吗?
- 是否有人拥有 split 基数 FFT 的代码,它的运算次数可以减少大约 2/3?
