Comments 35
Добавлю эту статью в папку «Ответы на вопрос, 'Нужна ли программистам математика'».
Спасибо за интересный перевод.
Спасибо за интересный перевод.
Если бы не Гомер, не прочитал бы! Спасибо Гомеру и автору(перевода), очень интересно и легко читалось. Респектую!
Минутку. Ну то есть основной принцип похож на некоторую декомпиляцию, когда по готовому результату воссоздаются «исходники». Если взять за пример «квадратную волну» приведенную в статье, то как именно получилось разобрать волну на «исходники»? Вариантов, которые в сумме дают квадратную волну может быть очень много.
Вариант один и использует бесконечно много волн…
Тут как бы ещё не помешает отметить, что преобразование Фурье бывает ещё и дискретным (это как раз случай mp3 и jpg), а оно является линейным преобразованием и однозначно переводит финитный дискретный сигнал в набор комплексных амплитуд, обратное преобразование — аналогично.
Тут как бы ещё не помешает отметить, что преобразование Фурье бывает ещё и дискретным (это как раз случай mp3 и jpg), а оно является линейным преобразованием и однозначно переводит финитный дискретный сигнал в набор комплексных амплитуд, обратное преобразование — аналогично.
Всегда немного завидовал людям, которые с легкостью, «интуитивно» представляют себе такие вещи. Я же не до сих пор не чувствую, что мозаика сложилась (особенно это касается свертки функций), нет того самого «щелчка». Наверное, поэтому так и остаюсь обычным бесталанным программистом.
Я им тоже немного завидую…
Вы знаете, что касается преобразования Фурье, то я много где о нем слышал: читал самостоятельно, встречал в разных статьях, слышал на парах в вузе… Но «щелчок» произошел именно на этой статье — наконец-то оно уложилось в моей голове так, как надо. Не сдавайтесь (с теми же свертками функций) — подождите еще немного, и, быть может, спустя некоторое время вы найдете еще чью-нибудь заметку, в которой автор использовал немного другие слова и примеры, и на вас снизойдет озарение.
Вариантов, действительно, в некотором смысле много. Вначале берут набор базисных функций и раскладывают требуемую функцию по ним. Для каждого базиса разложение функции единственно (если существует).
Например, в качестве базиса можно взять набор гармонических функций: fn(x) = einax, где a — некоторое число (основная частота). «Квадратная волна» разлагается по этим синусам в бесконечный ряд, но на практике приходится ограничиваться несколькими первыми коэффициентами, что дает не совсем квадратность (и на картинке это хорошо видно).
Например, в качестве базиса можно взять набор гармонических функций: fn(x) = einax, где a — некоторое число (основная частота). «Квадратная волна» разлагается по этим синусам в бесконечный ряд, но на практике приходится ограничиваться несколькими первыми коэффициентами, что дает не совсем квадратность (и на картинке это хорошо видно).
Тут волна не «разбирается на исходники», а «раскладывается по синусам». Можно раскладывать и по косинусам, и по степенным функциям, и еще бесконечным количеством разных способов.
Просто у разложения «по синусам» есть такой хороший бонус: Не смотря на то, что ряд на самом деле бесконечный, аналоговые сигналы «из жизни» очень хорошо приближаются первыми членами ряда, а остальные можно просто выбросить. Даже теорема есть, про количество значащих коэффициентов разложения сигнала и пропускную способность канала, откуда этот сигнал пришел.
Ну и изучено оно, понятное дело, вдоль и поперек — бери и пользуйся, думать не надо :)
Просто у разложения «по синусам» есть такой хороший бонус: Не смотря на то, что ряд на самом деле бесконечный, аналоговые сигналы «из жизни» очень хорошо приближаются первыми членами ряда, а остальные можно просто выбросить. Даже теорема есть, про количество значащих коэффициентов разложения сигнала и пропускную способность канала, откуда этот сигнал пришел.
Ну и изучено оно, понятное дело, вдоль и поперек — бери и пользуйся, думать не надо :)
UFO just landed and posted this here
UFO just landed and posted this here
Очень высокие ноты не так важны (наши уши едва слышат их), поэтому МР3 выбрасывает их, добиваясь еще большего сжатия данных.
Это не вполне корректное описание идеи того, как работает MP3. Само по себе преобразование Фурье* не дает сжатия, поскольку обратимо, но его результат имеет физический смысл. А именно, полученные коэффициенты Фурье — не просто данные, а величины, которые можно округлять (причем довольно грубо). В то время как wave-представление не допускает вольного обращения со своими данными — при небольших изменениях звучание может испортиться до неузнаваемости.
Наивный mp3-кодер так и поступает — отбрасывает заданное пользователем количество младших бит у всех коэффициентов (за счет этого происходит сжатие информации в разы), а затем напускает универсальный алгоритм сжатия данных без потерь (например, LZ), что дает еще примерно двойку. Более продвинутые кодеры, опираясь на псхиоакустическую модель (это, грубо говоря, описание того, как человек воспринимает и распознает звук), «понимают», какие именно коэффициенты можно огрублять сильнее, а какие лучше оставить поточнее. Действительно, высокие ноты менее информативны чем средние, но учитывается и множество других особенностей, например, когда одна «сильная» нота маскирует другую.
Еще надо заметить, что вся эта кухня применяется для обработки только гармонической составляющей звукового сигнала. Другие — шумовая и ударная — выделяются и обрабатываются отдельно совсем другими методами без фурьеподобных преобразований.
(*) Реально используется не в точности оно, а другие преобразования, например, MDCT, обладающие теми же полезными свойствами ПФ, но чуть более выгодные с вычислительной точки зрения.
Про Гомера Симпсона и JPG тоже не очень верное сравнение.
В случае с Гомером имеем функцию
t -> (x, y)
к которой применяем ПФ.
А в случае JPG имеется функция (от двух переменных !!!)
(x, y) -> color
к которой применяется ФП, при чем дважды, по обеим переменным
В случае с Гомером имеем функцию
t -> (x, y)
к которой применяем ПФ.
А в случае JPG имеется функция (от двух переменных !!!)
(x, y) -> color
к которой применяется ФП, при чем дважды, по обеим переменным
Было бы шикарно, если бы кто-либо с Хабра, подкованный в соответствующих знаниях, взялся и написал целый цикл статей на тему математических открытий, теорем и алгоритмов простым человеческим языком (можно и не простым, но хотя бы со ссылками на источники нужных знаний) и с примерами кода на каком-либо популярном ЯП или с указанием, в каких продуктах они используются (и как).
Далеко не все приходят к программированию через пятилетнее пережевывание гранита в техническом ВУЗ'е и могут банально не знать о некоторых математических операциях, которые могут значительно облегчить решение прикладных задач без изобретения велосипеда, полного багов.
А те, кто всё же отучился свою пятилетку, могли попросту забыть о существовании каких-либо преобразований (в виду их редкого применения в реальных проектах заказчиков), которые могут значительно облегчить жизнь программиста при решении каких-то специфических задач.
Думаю, что подобный цикл статей был бы крайне полезен.
P.S.
Часто сталкивался с мнением (в основном в среде всевозможных «джейКуэристов»), что математика программисту не нужна… Даже как-то аргументировать умудрялись. Но… программисту математика необходима, как воздух!
Далеко не все приходят к программированию через пятилетнее пережевывание гранита в техническом ВУЗ'е и могут банально не знать о некоторых математических операциях, которые могут значительно облегчить решение прикладных задач без изобретения велосипеда, полного багов.
А те, кто всё же отучился свою пятилетку, могли попросту забыть о существовании каких-либо преобразований (в виду их редкого применения в реальных проектах заказчиков), которые могут значительно облегчить жизнь программиста при решении каких-то специфических задач.
Думаю, что подобный цикл статей был бы крайне полезен.
P.S.
Часто сталкивался с мнением (в основном в среде всевозможных «джейКуэристов»), что математика программисту не нужна… Даже как-то аргументировать умудрялись. Но… программисту математика необходима, как воздух!
Да, было бы интересно узнать например о реакции на статьи Фурье в научном сообществе и первые попытки применения, ну и история дальнейших усовершенствований, которую не найти где-нибудь на вики, в отличие от формул и определений.
да! был на хабре человек который про CV писал понятным языком, хороший были статьи
Я бы с огромным удовольствием читал эти статьи :)
Без программирования, могу кое-что добавить по книгам:
За последние годы вышло несколько научно-популярных книг на английском с названиями типа «equations that changed the world», «100 greatest mathematical ideas», «algorithms that changed the world» и т.д. Правда, я не ручаюсь за качество материала, я их только бегло листал. Среди них встречаются с виду хорошие, с практическими иллюстрациями.
А вот проверенная временем интересная книга по одной из областей М.: Леонард Млодинов, «Походка Пьяницы».
Без программирования, могу кое-что добавить по книгам:
За последние годы вышло несколько научно-популярных книг на английском с названиями типа «equations that changed the world», «100 greatest mathematical ideas», «algorithms that changed the world» и т.д. Правда, я не ручаюсь за качество материала, я их только бегло листал. Среди них встречаются с виду хорошие, с практическими иллюстрациями.
А вот проверенная временем интересная книга по одной из областей М.: Леонард Млодинов, «Походка Пьяницы».
Согласен, хоть я и плохой математик. Может умение «реализовать разложение в ряд Фурье за 30 секунд» и не так нужно, но вот понимание что оно делает и знание о нем — очень нужно и повсеместно необходимо!
этот фокус подарил нам онлайн мир, который мы все любим (и благодаря которому у нас появились гифки с котиками).
Дезинформация. В GIF применяется алгоритм сжатия LZW, который аж никакого отношения к преобразованию Фурье не имеет.
Отличная статья
А у Яндекса к примеру другой подход к вычленению данных которые идентифицируют трек: habrahabr.ru/company/yandex/blog/181219/
вот «на сетке «частота-время»» — это же как я понимаю обычная «волна» которую мы видим в любом редакторе аудио? то есть без преобразования?
Приложение Shazam именно так распознает песни. Оно разбивает песню на куски, а затем использует преобразование Фурье, чтобы определить ноты, из которых состоит каждый кусок.
А у Яндекса к примеру другой подход к вычленению данных которые идентифицируют трек: habrahabr.ru/company/yandex/blog/181219/
Оказывается, хорошо работают пики спектрограммы, выделенные тем или иным способом — например как точки локального максимума амплитуды. Высота пиков не подходит (АЧХ микрофона их меняет), а вот их местоположение на сетке «частота-время» мало меняется при зашумлении. Это наблюдение, в том или ином виде, используется во многих известных решениях — например, в Echoprint. В среднем на один трек получается порядка 300 тыс. пиков — такой объём данных гораздо более реально сопоставлять с миллионами треков в базе, чем полную спектрограмму запроса.
вот «на сетке «частота-время»» — это же как я понимаю обычная «волна» которую мы видим в любом редакторе аудио? то есть без преобразования?
Нет, не так. Перво-наперво, слово «частота» уже говорит нам, что без Фурье не обошлось. Если точнее, спектрограмма строится так: в звуковом сигнале через равные промежутки времени вырезаются маленькие «окна», для каждого окна строится преобразование Фурье (читай АЧХ). То есть у вас есть для каждого момента времени своя АЧХ. Вот это и есть сетка «частота-время» (для каждого момента времени дана мощность сигнала данной частоты).
Если совсем подробнее, то мощность сигнала на данной частоте (эти мощности и формируют АЧХ)--это квадрат амплитуды преобразования Фурье на данной частоте. Еще Фурье просто по окну делать нельзя, надо сглаживать сигнал у границ окна (иначе появятся паразитные частоты, которых нет в сигнале). Иногда какие-то из этих операции делают через цифровые фильтры, но они по сути являются эффективной реализацией преобразования Фурье (и изменения АЧХ: сделать прямое преобразование Фурье, изменить АЧХ, сделать обратное преобразование Фурье).
Если совсем подробнее, то мощность сигнала на данной частоте (эти мощности и формируют АЧХ)--это квадрат амплитуды преобразования Фурье на данной частоте. Еще Фурье просто по окну делать нельзя, надо сглаживать сигнал у границ окна (иначе появятся паразитные частоты, которых нет в сигнале). Иногда какие-то из этих операции делают через цифровые фильтры, но они по сути являются эффективной реализацией преобразования Фурье (и изменения АЧХ: сделать прямое преобразование Фурье, изменить АЧХ, сделать обратное преобразование Фурье).
Сайт в тему: www.fourier-series.com/
На нем очень много интерактивных примеров, связанных с преобразованием Фурье и цифровой обработкой сигналов.
Можно посмотреть, как происходит обработка сигнала, как меняется выходной сигнал при изменении параметров входного сигнала.
На нем очень много интерактивных примеров, связанных с преобразованием Фурье и цифровой обработкой сигналов.
Можно посмотреть, как происходит обработка сигнала, как меняется выходной сигнал при изменении параметров входного сигнала.
Интересно, а что получится, если движение кругов из рисунка Симпсона отобразить синусоидой и проиграть ее как звуковую волну? Скорее всего, гармонии там не будет наблюдаться.
Отсюда вытекает еще вопрос: а можно ли придумать осмысленные картинки с осмысленным гармоничным звучанием?
Отсюда вытекает еще вопрос: а можно ли придумать осмысленные картинки с осмысленным гармоничным звучанием?
oscillofun, например.
Метод преобразования Фурье используется в радаре, используемом ГИББД. Радар отправляет порцию колебаний известной частоты, а затем принимает отражённый сигнал. Благодаря эффекту Доплера (не описанному в этой статье), частота отражённого сигнала меняется пропорционально скорости движущегося объекта. Зная разность частот отправленного и принятого сигнала, радар может очень точно вычислить скорость. Но объектов на трассе обычно бывает несколько, и на приёмный контур радара приходит несколько суммированных сигналов (колебаний) разной частоты, огибающая — как в примере с 3 клавишами рояля. Вот здесь-то и вступает в дело метод преобразования Фурье. Т.е. если по трассе едут 5 автомобилей с разной скоростью, радар выдаст 5 замеренных скоростей, заодно указав максимальную.
Слово «ноты» всюду используется неправильно.
Шкала частот гармоник преобразования Фурье арифметическая, нотная шкала геометрическая, они пересекаются чуть менее, чем нигде.
Шкала частот гармоник преобразования Фурье арифметическая, нотная шкала геометрическая, они пересекаются чуть менее, чем нигде.
Может тогда кто-нибудь упомянет вейвлет-преобразование?
Метод Фурье очень активно применяется в энергетике (там это называют разложение на гармонические составляющие, или на гармоники). Некоторые защиты (например, защиты высоковольтных трансформаторов) реагируют на определенную гармонику (например блокировка защиты при броске тока намагничивания трансформатора, которая происходит при включении трансформатора, реагирует на третью гармонику 3wt тока). Это на память из универских лекций.
Sign up to leave a comment.
Математический фокус для MP3, JPEG и Гомера Симпсона