Как стать автором
Обновить

Быстрое умножение многочленов при помощи преобразования Фурье — это просто

Время на прочтение 9 мин
Количество просмотров 75K
Алгоритмы *
Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Читать дальше →
Всего голосов 112: ↑105 и ↓7 +98
Комментарии 38

Новый алгоритм MIT в десятки раз ускоряет быстрое преобразование Фурье

Время на прочтение 1 мин
Количество просмотров 21K
Алгоритмы *


На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.
Читать дальше →
Всего голосов 94: ↑65 и ↓29 +36
Комментарии 34

Нескучные интегралы

Время на прочтение 6 мин
Количество просмотров 170K
Математика *
Некоторые из вас, вероятно, видали на просторах сети эту задачку: какое число продолжает следующий ряд?

Предлагался такой очевидный правильный ответ:

Для тех, кому неочевидно, как он получен, предлагалось объяснение. Пусть (ну и 1 при x = 0, хотя неважно). Тогда каждый член ряда — это значение следующего интеграла в цепочке:

Пока всё идёт хорошо, но тут внезапно:

В принципе, этого достаточно, чтобы повеселить друзей-математиков, но мне захотелось узнать, как вообще считаются такие интегралы и почему получается такой смешной результат. Если кому-то ещё охота тряхнуть стариной и вспомнить матан с функаном, прошу читать дальше.
Читать дальше →
Всего голосов 263: ↑253 и ↓10 +243
Комментарии 62

Blind Deconvolution — автоматическое восстановление смазанных изображений

Время на прочтение 6 мин
Количество просмотров 144K
Алгоритмы *Обработка изображений *
Смазанные изображения — один из самых неприятных дефектов в фотографии, наравне с расфокусированными изображениями. Ранее я писал про алгоритмы деконволюции для восстановления смазанных и расфокусированных изображений. Эти, относительно простые, подходы позволяют восстановить исходное изображение, если известна точная траектория смаза (или форма пятна размытия).
В большинстве случаев траектория смаза предполагается прямой линией, параметры которой должен задавать сам пользователь — для этого требуется достаточно кропотливая работа по подбору ядра, кроме того, в реальных фотографиях траектория смаза далека от линии и представляет собой замысловатую кривую переменной плотности/яркости, форму которой крайне сложно подобрать вручную.


В последние несколько лет интенсивно развивается новое направлении в теории восстановления изображений — слепая обратная свертка (Blind Deconvolution). Появилось достаточно много работ по этой теме, и начинается активное коммерческое использование результатов.
Многие из вас помнят конференцию Adobe MAX 2011, на которой они как раз показали работу одного из алгоритмов Blind Deconvolution: Исправление смазанных фотографий в новой версии Photoshop
В этой статье я хочу подробнее рассказать — как же работает эта удивительная технология, а также показать практическую реализацию SmartDeblur, который теперь тоже имеет в своем распоряжении этот алгоритм.
Внимание, под катом много картинок!
Читать дальше →
Всего голосов 243: ↑239 и ↓4 +235
Комментарии 149

SmartDeblur 2.1 — восстановление смазанных и расфокусированных изображений

Время на прочтение 2 мин
Количество просмотров 30K
Я пиарюсь
Многие из вас уже читали серию моих постов про восстановление расфокусированных и смазанных изображений, а также пробовали бесплатные версии программы SmartDeblur, к одной из которых доступны исходники на GitHub
Программа и статьи вызвали большой интерес как в рунете, так и в других странах, поэтому мы рады представить коммерческую версию SmartDeblur.

Основные изменения:
— Поддержка больших изображений (до 36MP на 64-битной ОС и до 15MP на 32-битной)
— Возможность редактирования полученного kernel (траектории смаза)
— Увеличение скорости за счет оптимизаций и использования Intel IPP в качестве FFT
— Улучшение интерфейса

image

Адрес проекта: smartdeblur.net
Под катом много картинок!

Читать дальше →
Всего голосов 107: ↑102 и ↓5 +97
Комментарии 70

Простыми словами о преобразовании Фурье

Уровень сложности Средний
Время на прочтение 14 мин
Количество просмотров 990K
Математика *Визуализация данных *
Из песочницы
Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.

image (с) xkcd

Без использования сложных формул и матлаба я постараюсь ответить на следующие вопросы:
  • FT, DTF, DTFT — в чем отличия и как совершенно разные казалось бы формулы дают столь концептуально похожие результаты?
  • Как правильно интерпретировать результаты быстрого преобразования Фурье (FFT)
  • Что делать если дан сигнал из 179 сэмплов а БПФ требует на вход последовательность по длине равную степени двойки
  • Почему при попытке получить с помощью Фурье спектр синусоиды вместо ожидаемой одиночной “палки” на графике вылезает странная загогулина и что с этим можно сделать
  • Зачем перед АЦП и после ЦАП ставят аналоговые фильтры
  • Можно ли оцифровать АЦП сигнал с частотой выше половины частоты дискретизации (школьный ответ неверен, правильный ответ — можно)
  • Как по цифровой последовательности восстанавливают исходный сигнал


Я буду исходить из предположения что читатель понимает что такое интеграл, комплексное число (а так же его модуль и аргумент), свертка функций, плюс хотя бы “на пальцах” представляет себе что такое дельта-функция Дирака. Не знаете — не беда, прочитайте вышеприведенные ссылки. Под “произведением функций” в данном тексте я везде буду понимать “поточечное умножение”

Итак, приступим?
Всего голосов 203: ↑192 и ↓11 +181
Комментарии 188

Гармонические колебания

Время на прочтение 10 мин
Количество просмотров 256K
Математика *Визуализация данных *
На хабре было несколько статей по преобразованию Фурье и о всяких красивостях типа Цифровой Обработки Сигналов (ЦОС), но неискушённому пользователю совершенно не понятно, зачем всё это нужно и где, а главное как это применить.


АЧХ шума.

Лично мне после прочтения этих статей (например, этой ) не стало понятно, что это и зачем оно нужно в реальной жизни, хотя было интересно и красиво.
Хочется не просто поглядеть красивые картинки, а так сказать, ощутить нутром, что и как работает. И я приведу конкретный пример с генерацией и обработкой звуковых файлов. Можно будет и послушать звук, и поглядеть его спектр, и понять, почему это так.
Статья не будет интересна тем, кто владеет теорией функций комплексной переменной, ЦОС и прочими страшными темами. Она скорее для любопытствующих, школьников, студентов и им сочувствующих :).
Читать дальше →
Всего голосов 116: ↑111 и ↓5 +106
Комментарии 50

Дискретное преобразование Фурье фрактального броуновского движения

Время на прочтение 2 мин
Количество просмотров 14K
Алгоритмы *Математика *
Фрактальное броуновское движение (ФБД) относится к классу рассматриваемых функций, заданные на конечном интервале и равные нулю вне его, которые включают кусочно непрерывные функции, удовлетворяющие условию роста:
image,
где функция image, удовлетворяет условию: image

Преобразование Фурье
Для ФБД будем интерпретировать процесс image как временной процесс. Существует частотная область, в которой функция — сумма составляющих, имеющих определенную частоту. Функция image может быть разложена как image.
Составляющая image с частотой image имеет вид:

image, где image.

Функция image называется преобразованием Фурье.
Читать дальше →
Всего голосов 14: ↑10 и ↓4 +6
Комментарии 9

Поиск периодических элементов защиты Паспорта РФ с помощью преобразования Фурье

Время на прочтение 7 мин
Количество просмотров 31K
Блог компании Smart Engines Программирование *Алгоритмы *Обработка изображений *Математика *
Многие документы содержат защитные элементы, такие как голограммы, водяные знаки, гильош и т.д. В процессе сканирования таких документов возникает проблема — защитные элементы мешают системам распознавания (OCR). При разработке Smart PassportReader мы провели исследование, направленное на поиск и устранение подобных защитных элементов с изображений документов.

Рассмотрим пример паспорта гражданина РФ, на котором легко увидеть периодический голографический узор.



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

В статье мы расскажем о методе определения наличия (детектирования) периодических шаблонов, использующем преобразование Фурье, который показал хорошие результаты в детектировании голографического узора на Российских паспортах.
Читать дальше →
Всего голосов 35: ↑33 и ↓2 +31
Комментарии 18

Поиск периодических элементов защиты Паспорта РФ с помощью преобразования Фурье: часть вторая

Время на прочтение 8 мин
Количество просмотров 21K
Блог компании Smart Engines Программирование *Алгоритмы *Обработка изображений *Математика *
Многие документы содержат защитные элементы, такие как голограммы, водяные знаки, гильош и т.д. В процессе сканирования таких документов возникает проблема — защитные элементы мешают системам распознавания (OCR). При разработке Smart PassportReader мы провели исследование, направленное на поиск и устранение подобных защитных элементов с изображений документов.



В нашей предыдущей статье по этой теме мы рассказали о первой половине решения задачи поиска — детектировании, т.е. определении наличия периодических элементов на изображении. Сегодня мы расскажем, как найти непосредственное положение периодических элементов на изображении, при условии, что детектирование прошло успешно: мы уверены, что элементы на изображении присутствуют. Вторая часть сильно зависит от первой, поэтому настоятельно рекомендуется сначала ознакомиться с первой, если вы этого еще не сделали.

Как и в прошлый раз, для этого будет использоваться преобразование Фурье.
Читать дальше →
Всего голосов 33: ↑32 и ↓1 +31
Комментарии 2

Практическое применение преобразования Фурье для анализа сигналов. Введение для начинающих

Время на прочтение 9 мин
Количество просмотров 256K
Математика *Визуализация данных *
Recovery mode
Из песочницы

1. Преобразование Фурье и спектр сигнала


Во многих случаях задача получения (вычисления) спектра сигнала выглядит следующим образом. Имеется АЦП, который с частотой дискретизации Fd преобразует непрерывный сигнал, поступающий на его вход в течение времени Т, в цифровые отсчеты — N штук. Далее массив отсчетов подается в некую программку, которая выдает N/2 каких-то числовых значений (программист, который утянул из инета написал программку, уверяет, что она делает преобразование Фурье).

Чтобы проверить, правильно ли работает программа, сформируем массив отсчетов как сумму двух синусоид sin(10*2*pi*x)+0,5*sin(5*2*pi*x) и подсунем программке. Программа нарисовала следующее:

image
рис.1 График временной функции сигнала

image
рис.2 График спектра сигнала

На графике спектра имеется две палки (гармоники) 5 Гц с амплитудой 0.5 В и 10 Гц — с амплитудой 1 В, все как в формуле исходного сигнала. Все отлично, программист молодец! Программа работает правильно.

Это значит, что если мы подадим на вход АЦП реальный сигнал из смеси двух синусоид, то мы получим аналогичный спектр, состоящий из двух гармоник.

Итого, наш реальный измеренный сигнал, длительностью 5 сек, оцифрованный АЦП, то есть представленный дискретными отсчетами, имеет дискретный непериодический спектр.
С математической точки зрения — сколько ошибок в этой фразе?

Теперь начальство решило мы решили, что 5 секунд — это слишком долго, давай измерять сигнал за 0.5 сек.
Читать дальше →
Всего голосов 51: ↑46 и ↓5 +41
Комментарии 66

Ограниченность преобразования Фурье или почему стоит доверять своему слуху

Время на прочтение 6 мин
Количество просмотров 15K
Алгоритмы *
Из песочницы
Последние несколько десятков лет задача распознавания аккордов музыкальной композиции ставилась довольно часто. Казалось бы, этот не столь оригинальный сервис был и остается довольно распространенным среди приложений, работающих со звуком (Ableton, Guitar Pro), однако универсального, срабатывающего всегда алгоритма не существует до сих пор. В этой статье я постараюсь раскрыть одну из множества причин неидеальной работы подобных сервисов на примере алгоритмов, использующих в своей основе преобразование Фурье.

Большинство аудиоформатов хранит информацию в виде зависимости амплитуды от времени (например, .wav) или в виде коэффициентов частотного преобразования (.mp3, .aac, .ogg), однако современные сложные алгоритмы цифровой обработки сигналов работают с частотной составляющей звуков. Приходится иметь дело с двойным переходом, из амплитудной области в частотную, затем обратно. На данный момент осуществление такого переход без потерь в качестве является достаточно распространенной проблемой с множеством неоднозначных решений.
Читать дальше →
Всего голосов 18: ↑13 и ↓5 +8
Комментарии 12

Ошибка процессора Intel Skylake приводит к зависанию компьютера во время сложных вычислений

Время на прочтение 2 мин
Количество просмотров 50K
Блог компании Positive Technologies


Группа немецких ученых из немецкого сообщества hardwaluxx.de обнаружила ошибку в работе процессоров Intel Skylake, приводящую к зависанию компьютера в процессе осуществления сложных вычислений. Позднее математики из проекта добровольных вычислений по поиску простых чисел Мерсенна (GIMPS) подтвердили наличие проблемы. Баг проявился в ходе работ по поиску простых чисел Мерсенна с помощью инструмента Prime95.
Читать дальше →
Всего голосов 37: ↑34 и ↓3 +31
Комментарии 36

Функции шума и генерирование карт

Время на прочтение 21 мин
Количество просмотров 31K
Разработка игр *Алгоритмы *
Перевод


Когда я изучал обработку аудиосигналов, мой мозг начал проводить аналогии с процедурным генерированием карт. В статье излагаются принципы, связывающие обработку сигналов с генерированием карт. Не думаю, что открыл что-то новое, но некоторые выводы были для меня в новинку, поэтому я решил записать их и поделиться с читателями. Я рассматриваю только простые темы (частоту, амплитуду, цвета шума, использование шума) и не затрагиваю другие темы (дискретные и непрерывные функции, фильтры FIR/IIR, быстрое преобразование Фурье, комплексные числа). Математика статьи в основном связана с синусоидами.

Эта статья посвящена концепциям, начиная с самых простейших и заканчивая более сложными. Если вы хотите перейти сразу к генерированию рельефа с помощью функций шума, то изучите другую мою статью.
Читать дальше →
Всего голосов 30: ↑30 и ↓0 +30
Комментарии 6

Практическое применение преобразования Фурье для обработки сигналов

Время на прочтение 13 мин
Количество просмотров 48K
Программирование *Математика *Программирование микроконтроллеров *
Из песочницы
Введение

Книги и публикации по цифровой обработке сигналов пишут авторы зачастую не догадывающиеся и не понимающие задач, стоящих перед разработчиками. Особенно это касается систем, работающих в реальном времени. Эти авторы отводят себе скромную роль бога, существующего вне времени и пространства, что вызывает некоторое недоумение у читателей подобной литературы. Данная публикация имеет целью развеять недоумения, возникающие у большинства разработчиков, и помочь им преодолеть «порог вхождения», для этих целей в тексте сознательно используется аналогии и терминология сферы программирования.

Данный опус не претендует на полноту и связность изложения.
Читать дальше →
Всего голосов 30: ↑22 и ↓8 +14
Комментарии 51

Применение преобразования Фурье для создания гитарного тюнера на Android. Часть 1

Время на прочтение 5 мин
Количество просмотров 13K
Java *Разработка мобильных приложений *Алгоритмы *
Из песочницы

В основе спектрального анализа звуковых данных лежит алгоритм, который носит название преобразование Фурье. При раскладывании исходного звукового сигнала на частотные составляющие, отдельные частоты называются гармониками. Основная гармоника определяет высоту звучания, а второстепенные гармоники определяют его тембр. Есть достаточно много мобильных приложений, которые используют преобразование Фурье для того, чтобы отобразить весь спектр частот (гармоник). Так же, есть мобильные приложения, которые служат для настройки гитар. Они работают по принципу: основная гармоника находится по самому высокому значению амплитуды в спектре. Такое утверждение не совсем верно, потому что основная гармоника определяется самой наименьшей из всех кратных этой гармонике, либо шагом между гармониками. Возникает необходимость найти способ, который позволит отобразить значение основной гармоники в спектре звукового сигнала.

В первой части статьи мы рассмотрим принцип работы дискретного преобразование Фурье, а также возможность записывать звуковые данные с Android устройства с помощью класса AudioRecord.
Читать дальше →
Всего голосов 14: ↑14 и ↓0 +14
Комментарии 5

О классификации методов преобразования Фурье на примерах их программной реализации средствами Python

Время на прочтение 7 мин
Количество просмотров 26K
Python *Математика *Разработка под Windows *
Туториал

Введение


Публикации по методу Фурье условно можно разделить на две группы. Первая группа так называемых познавательных публикаций, например, [1,2].

Вторая группа публикаций касается применения преобразований Фурье в технике, например, при спектральном анализе [3,4].

Ни в коем случае не умоляя достоинства этих групп публикации стоит признать, что без классификации, или хотя бы попытки осуществить такую классификацию, получить системное представление о методе Фурье, по моему мнению, затруднительно.

Задачи публикации


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

Гармонический анализ и синтез


Гармоническим анализом называют разложение функции f(t), заданной на отрезке [0, Т] в ряд Фурье или в вычислении коэффициентов Фурье по формулам.

Гармоническим синтезом называют получение колебаний сложной формы путем суммирования их гармонических составляющих (гармоник).

Программная реализация
#!/usr/bin/python
# -*- coding: utf-8 -*
from scipy.integrate import quad # модуль для интегрирования
import matplotlib.pyplot as plt # модуль для графиков
import numpy as np # модуль для операций со списками и массивами
T=np.pi; w=2*np.pi/T# период и круговая частота
def func(t):# анализируемая функция
         if t<np.pi:
                  p=np.cos(t)
         else:
                  p=-np.cos(t)
         return p
def func_1(t,k,w):# функция для расчёта коэффициента a[k] 
         if t<np.pi:
                  z=np.cos(t)*np.cos(w*k*t)
         else:
                  z=-np.cos(t)*np.cos(w*k*t)
         return z
def func_2(t,k,w):#функция для расчёта коэффициента b[k] 
         if t<np.pi:
                  y=np.cos(t)*np.sin(w*k*t)
         else:
                  y=-np.cos(t)*np.sin(w*k*t)
         return y
a=[];b=[];c=4;g=[];m=np.arange(0,c,1);q=np.arange(0,2*np.pi,0.01)# подготовка списков для численного анализа
a=[round(2*quad(func_1, 0, T, args=(k,w))[0]/T,3) for k in m]# интеграл для a[k], k -номер гармоники 
b=[round(2*quad(func_2, 0, T, args=(k,w))[0]/T,3) for k in m]# интеграл для b[k], k -номер гармоники
F1=[a[1]*np.cos(w*1*t)+b[1]*np.sin(w*1*t) for t in q]#функции для гармоник
F2=[a[2]*np.cos(w*2*t)+b[2]*np.sin(w*2*t) for t in q]
F3=[a[3]*np.cos(w*3*t)+b[3]*np.sin(w*3*t) for t in q]
plt.figure()
plt.title("Классический гармонический анализ функции \n при t<pi  f(t)=cos(t)  при t>=pi  f(t)=-cos(t)")
plt.plot(q, F1, label='1 гармоника')
plt.plot(q, F2 , label='2 гармоника')
plt.plot(q, F3, label='3 гармоника')
plt.xlabel("Время t")
plt.ylabel("Амплитуда А")
plt.legend(loc='best')
plt.grid(True)
F=np.array(a[0]/2)+np.array([0*t for t in q-1])# подготовка массива для анализа с a[0]/2
for k in np.arange(1,c,1):
         F=F+np.array([a[k]*np.cos(w*k*t)+b[k]*np.sin(w*k*t) for t in q])# вычисление членов ряда Фурье
plt.figure()
P=[func(t) for t in q]
plt.title("Классический гармонический синтез")
plt.plot(q, P, label='f(t)')
plt.plot(q, F, label='F(t)')
plt.xlabel("Время t")
plt.ylabel("f(t),F(t)")
plt.legend(loc='best')
plt.grid(True)
plt.show()

Читать дальше →
Всего голосов 14: ↑10 и ↓4 +6
Комментарии 1

Частотный метод идентификации линейных динамических систем: теория и практика

Время на прочтение 5 мин
Количество просмотров 6.5K
Математика *
Из песочницы
В практиктических приложениях ТАУ часто необходимо точно и качественно идентифицировать объект управления. В этой статье речь пойдет об идентификации объекта управления частотным методом. Данный метод применим, когда есть возможность физически протестировать объект управления синусоидальным входным воздействиямем, изменяя частоту в широком диапазоне. Если это условие соблюдено, то результат, как правило, оправдывает самые оптимистичные ожидания.
Полюса передаточной функции
Читать дальше →
Всего голосов 15: ↑14 и ↓1 +13
Комментарии 8

Стимпанк-компьютер Альберта Майкельсона

Время на прочтение 2 мин
Количество просмотров 13K
История IT Старое железо
Оказывается, ещё в 19 веке существовали вычислительные машины, способные осуществлять сложнейшие математические расчёты. Один из уникальных экземпляров — гармонический анализатор Альберта Майкельсона. Прибор выполнял преобразование Фурье. Эта функция сегодня широко используется в информатике, обработке сигналов, физике, теории чисел, комбинаторике, теории вероятностей, криптографии и других областях.

В честь 100-летия гармонического анализатора Майкельсона опубликована бесплатная электронная книга с великолепными иллюстрациями, где описывается принцип действия этого замечательного прибора.


Читать дальше →
Всего голосов 32: ↑31 и ↓1 +30
Комментарии 7

Невероятно эффектная цветомузыка на Arduino и светодиодах

Время на прочтение 4 мин
Количество просмотров 153K
DIY или Сделай сам Звук
С наступающим! Приближается Новый год, а значит, пора срочно создавать настроение! Ну и как всегда в это время года рождаются десятки электронных схем различных цветомузыкальных установок.

Чего только самобытные мастера не придумают. От трехцветных моргалок до лазерных многолучевых установок с управлением по MIDI интерфейсу.



Как большой поклонник, так называемых адресных светодиодов, хочу показать вам очень простую и удивительную цветомузыку. Я вообще такой ни разу не видел. Пока не собрал за один вечер. Итак, визуализатор звука!
Всего голосов 51: ↑46 и ↓5 +41
Комментарии 116
1