Как работает Shazam: переход от цифрового звука к частотам

Егор
WCFuyx7MC9jAS7LHy6HJGQ-W9WF5xqj1RLNgbIJ1TxJtg-SZ_LOCKUP_MASTERBRAND_2000_copy.png
В первой части статьи мы поговорили о том, что же такое звук, и как он из аналогового превращается в цифровой. Теперь же поговорим о том, что такое квантование и модуляция — да, слова страшные, но на деле ничего трудного нет. Однако для лучшего понимания все же советую ознакомиться с первой частью статьи, ну а тем, кто это уже знает — ждать той части статьи, где уже будет описание алгоритмов работы Shazam.

Квантование

Мы видели, как оцифровываются частоты аналоговой музыки, но, как мы помним, есть еще одна немаловажная характеристика — громкость. Причем громкость — мера относительная: при той же громкости внутри сигнала, если вы увеличите размер динамиков, звук станет выше. Громкость измеряет разницу между самым низким и самым высоким уровнем звука в песне.

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

Ниже на рисунке приведен пример такого низкого квантования звукового сигнала:

8_level_quantization-min.png
На этом рисунке представлено квантование на 8 уровней, и, как видно, результирующий звук (красный) достаточно сильно изменен. Разница между реальным и квантованным звуком называется ошибкой (шумом) квантования. Также это 8-уровневое квантование называется 3-битным, так как нужно всего 3 бита для реализации всех 8 уровней (8= 23).

Вот тот же сигнал, но уже с квантованием на 64 уровня (6 бит):

64_levels_quantization-min.png
Как видно, тут результирующий звук уже гораздо ближе к реальному, однако все еще недостаточно близок. К счастью, у нас не очень чувствительные уши, поэтому стандартным является 16-битное квантование, что означает наличие 65536 уровней — в таком случае шум квантования является достаточно низким для человеческих ушей.

Однако, профессионалы никуда не делись, и они в своих студиях могут использовать 24-битное квантование с 16 миллионами колебаний громкости между самой низкой и самой высокой точкой звуковой дорожки.

Импульсно-кодовая модуляция

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

Поток ИКМ представляет собой поток организованных бит, который может состоять из нескольких каналов: к примеру, в стерео музыке их два. В потоке амплитуда сигнала делится на сэмплы (единицы, образцы, выборки), а их количество соответствует частоте дискретизации музыки: к примеру, сэмплированная музыка с частотой в 44.1 кГц имеет 44100 выборок в секунду. Каждая выборка дает (квантованную) амплитуду звука соответствующей доли секунды.

Существует несколько форматов ИКМ, но самым часто используемым является (линейная) ИКМ с частотой в 44.1 кГц и 16-битным квантованием в стерео. Каждая выборка содержит в нем 4 байта информации — по 2 байта (16 бит) на каждый канал:
pcm-min.png
От цифрового звука до частот

Мы наконец-то разобрались с тем, как перейти от аналогового звука к цифровому. Но как нам получить частоты внутри цифрового сигнала? Это очень важно для работы алгоритма Shazam по снятию «слепка» с песни, ведь он работает только с частотами. 

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

Но есть две проблемы:
  • Мы имеем дело с цифровыми, а значит — конечными (не непрерывными) звуками.
  • Чтобы лучше знать частоты внутри песни, нам нужно применить преобразование Фурье на небольших частях аудиосигнала — к примеру, длиной 0.1 с, чтобы мы точно знали, каковы частоты для каждой 0.1 с нашей звуковой дорожки.
К счастью, существует и дискретное преобразование Фурье (ДПФ), но оно работает с некоторыми ограничениями: в частности, его можно применять только на одном канале, а значит, если у вас стереофоническая песня, то ее сначала нужно преобразовать в монофоническую.

Дискретное преобразование Фурье

ДПФ применяется к дискретным сигналам и дает дискретный спектр (частот внутри сигнала). Вот волшебная формула преобразования цифрового сигнала в частоте (стойте, не закрывайте вкладку со статьей, я поясню):DFT-min.png
В этой формуле X(n) представляет n-ый бин частот (чуть ниже поясню), странная крякозябра (Σ) — значок суммы, N — размер окна (то есть количество выборок, составляющих сигнал), x(k) — k-ый образец аудиосигнала. К примеру, для окна с 4096 выборками эта формула должна применяться в сумме 4096 раз:
  • 1 раз для n=0 для вычисления 0-ого бина частоты
  • 1 раз для n=1 для вычисления 1-ого бина частоты
  • ...
Как вы заметили, я говорю не о частотах, а о бинах частоты. Причина в том, что ДПФ дает дискретный спектр, а бин частоты — это наименьшая единица частоты, которую можно вычислить с помощью ДПФ. Размер бина (называемый спектральным или частотным разрешением) равен частоте дискретизации сигнала, деленной на размер окна (N). В нашем примере, с окном в 4096 выборок и частотой дискретизации в 44.1 кГц, частотное разрешение составляет 10.77 Гц (кроме нулевого бина — он особенный):
  • 0-й бин представляет частоты между 0 Гц и 5,38 Гц;
  • 1-й бин представляет частоты между 5,38 Гц и 16,15 Гц;
  • второй бин представляет частоты между 16,15 Гц и 26,92 Гц;
  • третий бин представляет частоты между 26,92 Гц и 37,68 Гц;
  • ...
Это означает, что ДПФ не может отделить две частоты, которые находятся ближе друг к другу, чем на 10.77 Гц. Например, ноты на частотах в 27, 32 и 37 Гц попадают в один бин, и если нота на частоте в 37 Гц была громкой, то вы просто узнаете, что весь 3-ий бин был громким. Особенно это проблематично для определения нот на самых низких октавах: к примеру, A1 находится на частоте 55 Гц, тогда как B1 на 58.27 Гц, а G1 — на 49 Гц.

Можно улучшить частотное разрешение, увеличив размер окна, но это означает потерю частот или нот, звучащих очень быстро (непродолжительное время):
  • Аудиосигнал имеет частоту дискретизации 44.1 кГц.
  • Увеличение окна означает получение большего количества выборок, и, следовательно, увеличение времени звучания каждого окна.
  • С 4096 отсчетами продолжительность окна составляет 0.1 с, а частотное разрешение 10.7 Гц: то есть можно обнаружить изменения каждый 0.1 с.
  • С 16384 отсчетами продолжительность окна составляет 0.37 с, а частотное разрешение 2.7 Гц: то есть можно обнаружить изменения каждый 0.37 с — теряются «быстрые» звуки.
Еще одной особенностью звукового сигнала является то, что нам нужна лишь половина бинов, вычисленных с помощью ДПФ. В предыдущем примере частотное разрешение было 10.7 Гц, то есть 2047-ой бин представляет частоты от 21902.9 Гц до 21913 Гц. При этом:
  • 2048-ой бин даст ту же информацию, что и 0-ой бин;
  • 2049-ый бин даст ту же информацию, что и 1-ый бин;
  • ...
  • X+2048-ой бин даст ту же информацию, что и X-ый бин.
Поэтому алгоритм распознавания музыки в Shazam серьезно упрощен — в нем используется лишь первая половина бинов, что позволяет существенно экономить время и ресурсы устройства (вообще говоря преобразование Фурье — достаточно тяжелая вычислительная задача).

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

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

Будь в курсе последних новостей из мира гаджетов и технологий

Мы в соцсетях

Комментарии

Snegovik
+632
Даже с физико-техническим образованием.. маляш тяжеловат материал..
20 ноября 2017 в 17:13
#
Егор Морозов
+1764
Да, соглашусь, на гиктаймсе он смотрелся бы лучше, ig все же более "простой" ресурс... Ну уж начал — нужно закончить, поэтому если какие-то моменты тяжеловаты для понимания — пишите, буду пояснять.
20 ноября 2017 в 17:32
#
+714
Скорее "желтый" ресурс. Я уверен, только Ваша колонка, Егор, держит бОльшую часть читателей. Иначе этот ресурс погряз бы в безумных статьях Кузнецова и в рекламе от Сотникова
20 ноября 2017 в 19:35
#
Илья Жуйко
0
Супер, вспомнил 3 курс института...
25 мая 2018 в 16:04
#