[закрытое] понимание fft

EDIT: Есть отличное введение в концепции здесь.

За этим вопросом стоит довольно много математики. Проще говоря, рассмотрим одномерную функцию, например, аудиоклип. Преобразование Фурье определяет частоты, присутствующие в этом сигнале. Каждый образец в исходном аудиоклипе соответствует амплитуде звуковой волны в любой момент времени. В отличие от этого, каждый образец в преобразовании Фурье определяет амплитуду определенной частоты колебаний. Например, чистая синусоидальная волна с частотой 1 кГц будет иметь преобразование Фурье с одним пиком на отметке 1 кГц. Звуковые волны представляют собой комбинацию множества различных синусоид, и преобразование Фурье позволяет определить, какие синусоиды и в какой степени вносят свой вклад. (Обратите внимание, что настоящее объяснение требует углубления в комплексные числа, но вышесказанное дает представление о сути происходящего).

Преобразование Фурье изображения является простым расширением одномерного преобразования Фурье на два измерения и достигается простым применением одномерного преобразования к каждой строке изображения, а затем преобразованием каждого столбца полученного изображения. Получается, по сути, то же самое. Изображение гладких волн воды, движущихся по диагонали, преобразуется в серию пиков вдоль той же диагонали.

Преобразование Фурье определено над непрерывными функциями. БПФ - это метод эффективной оценки преобразования Фурье над дискретными наборами данных.