Компания
41,71
рейтинг
5 декабря 2013 в 16:47

Разработка → Математический фокус для MP3, JPEG и Гомера Симпсона перевод

Девять лет назад я посещал курс физики в колледже, и мой профессор рассказал одну вещь, которая поразила меня. Я думаю, не будет преувеличением сказать, что это одно из наиболее широко используемых математических открытий — от оптики до квантовой физики, радиоастрономии, сжатия MP3 и JPEG, рентгеновской кристаллографии, распознавания голоса и МРТ. Этот математический инструмент называется преобразование Фурье, в честь французского физика и математика 18-го века Жозефа Фурье. Им пользовались даже Джеймс Уотсон и Фрэнсис Крик, чтобы декодировать структуру двойной спирали ДНК из рентгенограмм, произведенных Розалиндой Франклин. (Крик был экспертом по преобразованиям Фурье, он в шутку назвал свою книгу «Преобразования Фурье для орнитологов», чтобы объяснить суть Уотсону, заядлому любителю птиц).

Вы наверняка пользуетесь идеей Фурье каждый день, если слушаете MP3, смотрите картинки в Интернете, задаете вопрос Siri или ловите радиостанцию. (Фурье, кстати, очень любил работать. В дополнение к своей работе в области теоретической физики и математики, он также стал первым, кто открыл парниковый эффект [pdf ].)

Так в чем заключается открытие Фурье и почему оно так полезно? Представьте себе ноту на фортепиано. При нажатии клавиши фортепиано молоток ударяет по струне, которая вибрирует с определенной частотой (нота Ля — 440 раз в секунду). Пока струна вибрирует, молекулы воздуха вокруг нее двигаются взад и вперед, создавая волну из молекул, которую мы называем звуком. Если бы вы могли наблюдать за движением воздуха, то увидели бы гладкую, волнистую, бесконечно повторяющуюся кривую, которая называется синусоидой. (Пояснение: В примере с клавишей фортепиано на самом деле возникнет больше одной синусоиды. Богатство настоящих нот фортепиано заключено в большом количестве мягких обертонов, которые появляются в дополнение к основной синусоидальной волне. Нота приблизительно равна синусоиде, но при помощи камертона можно получить звук, который состоит из одной синусоиды).


Звуковую волну ноты можно рассматривать как простую синусоидальную волну. Milan B на Shuttershock

Теперь нажмите на три клавиши вместе, чтобы получить аккорд. Полученная звуковая волна получится не такой аккуратной – она будет более беспорядочной. Но в этой кривой звуковой волне скрыт простой рисунок. Ведь аккорд мы получили, нажав всего на три клавиши, так что эта звуковая волна состоит из трех нот (или синусоид ).


Звуковая волна, полученная с помощью аккорда фортепиано, может выглядеть беспорядочно, но это всего лишь сумма трех разных нот. Christine Daniloff / MIT

Фурье догадался, что это не просто особое свойство музыкальных аккордов, оно применимо в более общем виде к любой повторяющейся волне, квадратной, круглой, волнистой, треугольной, в общем – к любой. Преобразование Фурье похоже на математическую призму — вы подаете волну, а оно показывает ее составные части, то есть ноты (или синусоиды), которые при соединении воссоздадут волну.

Если это звучит немного абстрактно, вот несколько методов визуализации трюка Фурье. Здесь мы встречаем Лукаса В. Барбосу, бразильского студента-физика, который безвозмездно создает невероятные математические и научные анимации для Википедии под ником LucasVB.
Итак, давайте посмотрим на квадратную волну, пропущенную через призму Фурье, и увидим, что получилось на выходе.


Кадры из анимации LucasVB

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

Вот немного другой подход, представленный Мэтью Хендерсоном или «Matthen», студентом Кембриджского университета, который также создает анимации интересных математических фишек. Matthen объясняет трюк Фурье, используя круги вместо синусоид. На помощь ему приходит набор кругов различных размеров, центр каждого из которых находится на границе большего круга. Круги начинают вращаться, маленькие движутся вокруг больших и делают это быстрее. Если проследить движение одной точки на наименьшей окружности, можно реконструировать волну любой формы, как показано на анимации и на картинке. Опять же, преобразование Фурье говорит нам, как построить волну: какие круги и скорости использовать.


Matthew Henderson

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

В общем, преобразование Фурье говорит нам, сколько каждого ингредиента «ноты» (синусоидальной волны или круга) содержится в общей волне. А вот почему это полезно. Представьте, что вы говорите со своим другом по телефону и хотите, чтобы он нарисовал эту квадратную волну. Можно использовать утомительный способ и зачитать длинный список цифр, которые показывают высоту волны в каждый момент времени. Учтя все эти цифры, ваш друг сможет создать исходную волну. Так работали старые аудио форматы, например, WAV. Но если ваш друг разбирается в преобразованиях Фурье, можно сделать все проще: вы можете просто назвать несколько чисел — размеров кругов на картинке выше. Эти круги можно использовать, чтобы восстановить исходную волну.

Это не какой-то сложный математический фокус. Преобразование Фурье используется почти везде, где есть волны. Вездесущий MP3 формат использует вариант трюка Фурье для достижения огромного сжатия по сравнению с файлами WAV (произносится как «вейв»), которые были до него. MP3 разбивает песню на короткие сегменты. В каждом сегменте преобразование Фурье разбивает аудио волну на составляющие ноты, которые хранятся вместо исходной волны. Преобразование Фурье также говорит нам, сколько и какой ноты используется в песне, чтобы знать, какие ноты важны. Очень высокие ноты не так важны (наши уши едва слышат их), поэтому МР3 выбрасывает их, добиваясь еще большего сжатия данных. Поэтому меломанам не нравится МР3 — это не lossless формат аудио, и они утверждают, что могут услышать разницу.

Приложение Shazam именно так распознает песни. Оно разбивает песню на куски, а затем использует преобразование Фурье, чтобы определить ноты, из которых состоит каждый кусок. Затем оно выполняет поиск по базе данных, чтобы проверить, похож ли этот «отпечаток» нот на какие-нибудь хранящиеся песни. Распознавание речи использует ту же идею, чтобы сравнить ноты в вашем голосе со списком известных слов.

Вы можете использовать преобразование Фурье для изображений. Вот отличное видео, которое показывает, как можно нарисовать лицо Гомера Симпсона с помощью кругов. Онлайн-энциклопедия Wolfram Alpha использует подобную идею, чтобы рисовать лица известных людей. Следующий факт пригодится, чтобы блеснуть знаниями на вечеринке: преобразование Фурье также используется для сжатия изображений в формат JPEG. В старые добрые времена Microsoft Paint изображения сохранялись в формате BMP, которые представляли собой длинный список чисел, кодирующих цвет каждого пикселя. JPEG – это MP3 изображений. Чтобы создать JPEG, надо разделить изображение на мелкие квадраты 8 на 8 пикселей. Чтобы воссоздать изображение, для каждой части нужно применить ту же идею круга, который рисует лицо Гомера Симпсона. Так же, как МР3 отбрасывает очень высокие ноты, JPEG отбрасывает очень маленькие круги. В результате мы получаем огромное уменьшение размера файла при небольшой потере качества, этот фокус подарил нам онлайн мир, который мы все любим (и благодаря которому у нас появились гифки с котиками).


Randall Munroe / XKCD

Как преобразование Фурье используются в науке? Через Твиттер я попросил ученых описать, как идеи Фурье помогли им в своей работе. Ответ поразил меня. Откликнувшиеся ученые использовали преобразование Фурье для изучения колебаний погружаемых конструкций, взаимодействующих с жидкостями, для предсказывания землетрясений, для определения составных частей очень далеких галактик, для поиска новых физических процессов в тепловых остатках Большого Взрыва, для определения структуры белков, для анализа цифровых сигналов НАСА, для изучения акустики музыкальных инструментов, для уточнения модели круговорота воды, для поиска пульсаров (вращающихся нейтронных звезд) и для определения структуры молекул с помощью ядерного магнитного резонанса. Преобразование Фурье даже использовалось для определения фальшивых картин Джексона Поллока через распознавание химических веществ в краске.

Вот так! Немало для одного математического фокуса.

Аатиш Бхатиа недавно получил степень кандидата физических наук в университете Принстона, занимаясь популяризацией науки и инженерии. Он — автор признанного блога Empirical Zeal, аккаунт в твитере — @aatishb.
Автор: @notPETR Aatish Bhatia
Achiever
рейтинг 41,71
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Комментарии (35)

  • +11
    Добавлю эту статью в папку «Ответы на вопрос, 'Нужна ли программистам математика'».

    Спасибо за интересный перевод.
    • +5
      Можете папку расшарить? :)
  • +4
    Если бы не Гомер, не прочитал бы! Спасибо Гомеру и автору(перевода), очень интересно и легко читалось. Респектую!
    • 0
      Вот так и выходит, что истинный популяризатор науки — Гомер Симпсон )
      • 0
        Не только!)) Ещё есть Щекотка и царапка! ))
  • 0
    Минутку. Ну то есть основной принцип похож на некоторую декомпиляцию, когда по готовому результату воссоздаются «исходники». Если взять за пример «квадратную волну» приведенную в статье, то как именно получилось разобрать волну на «исходники»? Вариантов, которые в сумме дают квадратную волну может быть очень много.
    • +8
      Вариант один и использует бесконечно много волн…
      Тут как бы ещё не помешает отметить, что преобразование Фурье бывает ещё и дискретным (это как раз случай mp3 и jpg), а оно является линейным преобразованием и однозначно переводит финитный дискретный сигнал в набор комплексных амплитуд, обратное преобразование — аналогично.
      • +2
        Всегда немного завидовал людям, которые с легкостью, «интуитивно» представляют себе такие вещи. Я же не до сих пор не чувствую, что мозаика сложилась (особенно это касается свертки функций), нет того самого «щелчка». Наверное, поэтому так и остаюсь обычным бесталанным программистом.
        • +7
          Я им тоже немного завидую…
        • +2
          Вы знаете, что касается преобразования Фурье, то я много где о нем слышал: читал самостоятельно, встречал в разных статьях, слышал на парах в вузе… Но «щелчок» произошел именно на этой статье — наконец-то оно уложилось в моей голове так, как надо. Не сдавайтесь (с теми же свертками функций) — подождите еще немного, и, быть может, спустя некоторое время вы найдете еще чью-нибудь заметку, в которой автор использовал немного другие слова и примеры, и на вас снизойдет озарение.
    • +2
      Вариантов, действительно, в некотором смысле много. Вначале берут набор базисных функций и раскладывают требуемую функцию по ним. Для каждого базиса разложение функции единственно (если существует).

      Например, в качестве базиса можно взять набор гармонических функций: fn(x) = einax, где a — некоторое число (основная частота). «Квадратная волна» разлагается по этим синусам в бесконечный ряд, но на практике приходится ограничиваться несколькими первыми коэффициентами, что дает не совсем квадратность (и на картинке это хорошо видно).
    • 0
      Тут волна не «разбирается на исходники», а «раскладывается по синусам». Можно раскладывать и по косинусам, и по степенным функциям, и еще бесконечным количеством разных способов.

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

      Ну и изучено оно, понятное дело, вдоль и поперек — бери и пользуйся, думать не надо :)
  • НЛО прилетело и опубликовало эту надпись здесь
  • НЛО прилетело и опубликовало эту надпись здесь
  • +13
    Очень высокие ноты не так важны (наши уши едва слышат их), поэтому МР3 выбрасывает их, добиваясь еще большего сжатия данных.

    Это не вполне корректное описание идеи того, как работает MP3. Само по себе преобразование Фурье* не дает сжатия, поскольку обратимо, но его результат имеет физический смысл. А именно, полученные коэффициенты Фурье — не просто данные, а величины, которые можно округлять (причем довольно грубо). В то время как wave-представление не допускает вольного обращения со своими данными — при небольших изменениях звучание может испортиться до неузнаваемости.

    Наивный mp3-кодер так и поступает — отбрасывает заданное пользователем количество младших бит у всех коэффициентов (за счет этого происходит сжатие информации в разы), а затем напускает универсальный алгоритм сжатия данных без потерь (например, LZ), что дает еще примерно двойку. Более продвинутые кодеры, опираясь на псхиоакустическую модель (это, грубо говоря, описание того, как человек воспринимает и распознает звук), «понимают», какие именно коэффициенты можно огрублять сильнее, а какие лучше оставить поточнее. Действительно, высокие ноты менее информативны чем средние, но учитывается и множество других особенностей, например, когда одна «сильная» нота маскирует другую.

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

    (*) Реально используется не в точности оно, а другие преобразования, например, MDCT, обладающие теми же полезными свойствами ПФ, но чуть более выгодные с вычислительной точки зрения.
    • 0
      Про Гомера Симпсона и JPG тоже не очень верное сравнение.
      В случае с Гомером имеем функцию
      t -> (x, y)
      к которой применяем ПФ.

      А в случае JPG имеется функция (от двух переменных !!!)
      (x, y) -> color
      к которой применяется ФП, при чем дважды, по обеим переменным
      • 0
        Да, только не ФП применяется дважды, а один раз применяется двумерное ФП. (Впрочем, в многомерном ФП интеграл вроде всегда распадается на произведение.)
        • +1
          Двумерное дискретное преобразование выводится из одномерного сначала по одной, затем по другой переменной. Можно использовать готовую формулу, но, все-таки, просто используют одномерное дважды, применяя быстрое преобразование Фурье.
      • 0
        Про ZIgZag забыли?
  • +28
    Было бы шикарно, если бы кто-либо с Хабра, подкованный в соответствующих знаниях, взялся и написал целый цикл статей на тему математических открытий, теорем и алгоритмов простым человеческим языком (можно и не простым, но хотя бы со ссылками на источники нужных знаний) и с примерами кода на каком-либо популярном ЯП или с указанием, в каких продуктах они используются (и как).

    Далеко не все приходят к программированию через пятилетнее пережевывание гранита в техническом ВУЗ'е и могут банально не знать о некоторых математических операциях, которые могут значительно облегчить решение прикладных задач без изобретения велосипеда, полного багов.

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

    Думаю, что подобный цикл статей был бы крайне полезен.

    P.S.
    Часто сталкивался с мнением (в основном в среде всевозможных «джейКуэристов»), что математика программисту не нужна… Даже как-то аргументировать умудрялись. Но… программисту математика необходима, как воздух!
    • +1
      Да, было бы интересно узнать например о реакции на статьи Фурье в научном сообществе и первые попытки применения, ну и история дальнейших усовершенствований, которую не найти где-нибудь на вики, в отличие от формул и определений.
    • +1
      да! был на хабре человек который про CV писал понятным языком, хороший были статьи
    • 0
      Я бы с огромным удовольствием читал эти статьи :)

      Без программирования, могу кое-что добавить по книгам:
      За последние годы вышло несколько научно-популярных книг на английском с названиями типа «equations that changed the world», «100 greatest mathematical ideas», «algorithms that changed the world» и т.д. Правда, я не ручаюсь за качество материала, я их только бегло листал. Среди них встречаются с виду хорошие, с практическими иллюстрациями.
      А вот проверенная временем интересная книга по одной из областей М.: Леонард Млодинов, «Походка Пьяницы».
    • 0
      Согласен, хоть я и плохой математик. Может умение «реализовать разложение в ряд Фурье за 30 секунд» и не так нужно, но вот понимание что оно делает и знание о нем — очень нужно и повсеместно необходимо!
  • +6
    этот фокус подарил нам онлайн мир, который мы все любим (и благодаря которому у нас появились гифки с котиками).

    Дезинформация. В GIF применяется алгоритм сжатия LZW, который аж никакого отношения к преобразованию Фурье не имеет.
  • –1
    Отличная статья
    Приложение Shazam именно так распознает песни. Оно разбивает песню на куски, а затем использует преобразование Фурье, чтобы определить ноты, из которых состоит каждый кусок.

    А у Яндекса к примеру другой подход к вычленению данных которые идентифицируют трек: habrahabr.ru/company/yandex/blog/181219/
    Оказывается, хорошо работают пики спектрограммы, выделенные тем или иным способом — например как точки локального максимума амплитуды. Высота пиков не подходит (АЧХ микрофона их меняет), а вот их местоположение на сетке «частота-время» мало меняется при зашумлении. Это наблюдение, в том или ином виде, используется во многих известных решениях — например, в Echoprint. В среднем на один трек получается порядка 300 тыс. пиков — такой объём данных гораздо более реально сопоставлять с миллионами треков в базе, чем полную спектрограмму запроса.

    вот «на сетке «частота-время»» — это же как я понимаю обычная «волна» которую мы видим в любом редакторе аудио? то есть без преобразования?
    • +2
      Нет, не так. Перво-наперво, слово «частота» уже говорит нам, что без Фурье не обошлось. Если точнее, спектрограмма строится так: в звуковом сигнале через равные промежутки времени вырезаются маленькие «окна», для каждого окна строится преобразование Фурье (читай АЧХ). То есть у вас есть для каждого момента времени своя АЧХ. Вот это и есть сетка «частота-время» (для каждого момента времени дана мощность сигнала данной частоты).

      Если совсем подробнее, то мощность сигнала на данной частоте (эти мощности и формируют АЧХ)--это квадрат амплитуды преобразования Фурье на данной частоте. Еще Фурье просто по окну делать нельзя, надо сглаживать сигнал у границ окна (иначе появятся паразитные частоты, которых нет в сигнале). Иногда какие-то из этих операции делают через цифровые фильтры, но они по сути являются эффективной реализацией преобразования Фурье (и изменения АЧХ: сделать прямое преобразование Фурье, изменить АЧХ, сделать обратное преобразование Фурье).
  • 0
    Сайт в тему: www.fourier-series.com/
    На нем очень много интерактивных примеров, связанных с преобразованием Фурье и цифровой обработкой сигналов.
    Можно посмотреть, как происходит обработка сигнала, как меняется выходной сигнал при изменении параметров входного сигнала.
  • +1
    Интересно, а что получится, если движение кругов из рисунка Симпсона отобразить синусоидой и проиграть ее как звуковую волну? Скорее всего, гармонии там не будет наблюдаться.
    Отсюда вытекает еще вопрос: а можно ли придумать осмысленные картинки с осмысленным гармоничным звучанием?
  • +14
    Метод преобразования Фурье используется в радаре, используемом ГИББД. Радар отправляет порцию колебаний известной частоты, а затем принимает отражённый сигнал. Благодаря эффекту Доплера (не описанному в этой статье), частота отражённого сигнала меняется пропорционально скорости движущегося объекта. Зная разность частот отправленного и принятого сигнала, радар может очень точно вычислить скорость. Но объектов на трассе обычно бывает несколько, и на приёмный контур радара приходит несколько суммированных сигналов (колебаний) разной частоты, огибающая — как в примере с 3 клавишами рояля. Вот здесь-то и вступает в дело метод преобразования Фурье. Т.е. если по трассе едут 5 автомобилей с разной скоростью, радар выдаст 5 замеренных скоростей, заодно указав максимальную.
    • 0
      Если быть более точным, обратно возвращается смесь сигналов с различным значением смещения несущей частоты (как правило, объектов, отражающих сигнал бывает много). Тут еще есть задача выделения «гармоники» с наибольшей амплитудой.
  • +5
    Слово «ноты» всюду используется неправильно.
    Шкала частот гармоник преобразования Фурье арифметическая, нотная шкала геометрическая, они пересекаются чуть менее, чем нигде.
  • 0
    Может тогда кто-нибудь упомянет вейвлет-преобразование?
  • 0
    Метод Фурье очень активно применяется в энергетике (там это называют разложение на гармонические составляющие, или на гармоники). Некоторые защиты (например, защиты высоковольтных трансформаторов) реагируют на определенную гармонику (например блокировка защиты при броске тока намагничивания трансформатора, которая происходит при включении трансформатора, реагирует на третью гармонику 3wt тока). Это на память из универских лекций.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка