快速傅里叶变换（FFT）是如何工作的

Question

我正在学习Python，并且在做一个与图像分析相关的小项目。为了理解这个概念，我尝试去理解各种Python代码，但这次我遇到了困难。有没有人能帮我解释一下这段代码？特别是关于FFT的部分？

class HeartMonitor(object):

    def __init__(self, window_duration, fps = 30, min_bpm = 50, max_bpm = 200):
        """
        Class which detects heart-beats in a sequence of image colour samples.
        @param window_duration The number of seconds of samples to use
        @param fps             The nominal sample rate
        @param min_bpm         Minimum cut-off for possible heartrates
        @param max_bpm         Maximum cut-off for possible heartrates
        """

        self.min_bpm = min_bpm
        self.max_bpm = max_bpm

        # The maximum number of samples to buffer
        self.buf_size = int(window_duration*fps)

        # Buffer of (timestamp, value) tuples
        self.buf = []


    @property
    def fps(self):
        """
        The average framerate/samplerate of the buffer
        """
        return float(len(self.buf)) / (self.buf[-1][0] - self.buf[0][0])


    def get_fft(self):
        """
        Perform an Fast-Fourier-Transform on the buffer and return (magnitude,
        phase) tuples for each of the bins.
        """
        # Get the "ideal" evenly spaced times
        even_times = numpy.linspace(self.buf[0][0], self.buf[-1][0], len(self.buf))

        # Interpolate the data to generate evenly temporally spaced samples
        interpolated = numpy.interp(even_times, *zip(*self.buf))

        # Perform the FFT
        fft = numpy.fft.rfft(interpolated)
        return zip(numpy.abs(fft), numpy.angle(fft))

Answer 1

numpy.fft.rfft 是一个库函数，用来从真实的数据计算快速傅里叶变换（FFT）。

这些数据点需要在时间上均匀分布，也就是说，它们之间的间隔要相等。

因为有些数据点在 buf 中可能不是均匀分布的，所以我们使用 numpy.interp 来进行插值处理，确保它们均匀。

self.buf[0] 是 buf 的第一个数据点。
self.buf[-1] 是 buf 的最后一个数据点。
len(self.buf) 是 buf 中数据点的总数。

这样，你最终会得到相同数量的数据点，但它们在时间轴上被移动了，以便均匀分布（这些均匀分布的数据存储在变量 interpolated 中）。

现在可以将 interpolated 传递给 numpy.fft.rfft 进行进一步处理。