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

Функции окна

Если вы хотите получить частоту односекундного звука для каждой 0,1-секундной части, вам необходимо применить преобразование Фурье для первой 0,1-секундной части, второй, третьей и так далее частей — однако это вызывает несколько проблем: поступая таким образом, вы неявно применяете (прямоугольную) функцию окна:

• За первые 0,1 секунды вы применяете преобразование Фурье на полном односекундном сигнале, умноженном на функцию, равную 1 между 0 и 0,1 секундой, и 0 для остальных промежутков.
• В течение второй 0,1 секунды вы применяете преобразование Фурье на полном односекундном сигнале, умноженном на функцию, которая равна 1 между 0,1 и 0,2 секундой, и 0 для остальных промежутков.
• ...

Вот наглядный пример функции окна, применяемой к цифровому (выборочному) звуковому сигналу, чтобы получить первую 0,01-секундную часть:

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

Аналогично получаем частоты и для второй 0.01 секундной части:


То есть, посредством «оконного» аудиосигнала, вы умножаете свой сигнал Запись(t) на оконную функцию Окно(t) (Запись(t) и Окно(t) — это две функции, которые зависят от времени t, первая — синяя, вторая — зеленая). Эта функция окна создает спектральную утечку — то есть появление новых частот, которых нет в звуковом сигнале, иными словами мощности реальных частот просачиваются на другие частоты.

Этому есть неформальное (и достаточно простое) математическое объяснение. Предположим, вы хотите получить часть полного аудиосигнала. Вы будете умножать аудиосигнал на оконную функцию, которая пропускает звук только для той части аудиосигнала, которая вам нужна:

Часть_Записи(t) = Полная_Запись(t)*Окно(t)

Для получения частоты части записи мы применяем преобразование Фурье:

Фурье(Часть_Записи(t)) = Фурье(Полная_Запись(t)*Окно(t))

По теореме о свертке раскроем скобки (смысл в том, что Фурье для перемножения функций равно перемножению Фурье для каждой функции):

Фурье(Полная_Запись(t)*Окно(t)) = Фурье(Полная_Запись(t))*Фурье(Окно(t))

Тогда мы получаем, что:

Фурье(Часть_Записи(t)) = Фурье(Полная_Запись(t))*Фурье(Окно(t))

То есть частоты Части_Записи(t) зависят от используемой функции Окно(t), а, значит, спектральной утечки не избежать, но можно ее уменьшить, выбирая правильную функцию окна: вместо того, чтобы использовать прямоугольное окно, можно взять треугольное, окно Парзена, Блэкмена, Хэмминга и т.д. 

Сравнение различных типов окон

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

• Частота 40 Гц с амплитудой 2;
• Частота 160 Гц с амплитудой 0,5;
• Частота 320 Гц с амплитудой 8;
• Частота 640 Гц с амплитудой 1;
• Частота 1000 Гц с амплитудой 1;
• Частота 1225 Гц с амплитудой 0,25;
• Частота 1400 Гц с амплитудой 0,125;
• Частота 2000 Гц с амплитудой 0,125;
• Частота 2500 Гц с амплитудой 1,5.

В идеальном мире преобразование Фурье этого сигнала должно дать нам следующий спектр:

То есть в идеале мы получаем спектр только с 9 вертикальными линиями (по числу частот), а ось Y дает амплитуду в децибелах (дБ), то есть масштаб — логарифмический: звук с громкостью в 60 дБ в 100 раз громче, чем звук с громкостью в 40 дБ, и в 10000 раз громче, чем с 20 дБ. Для сравнения — когда вы говорите в комнате в тишине, звук, который вы производите, на 20-30 дБ выше (в 1 метре от вас), чем просто «громкость тишины».

Чтобы построить этот «идеальный» спектр, я применил преобразование Фурье с очень длинным окном: в целых 10 секунд. Использование очень длинного окна уменьшает спектральную утечку, но 10 секунд — это слишком большой промежуток времени, потому что в реальной песне звук меняется намного быстрее. Чтобы дать вам представление о том, как быстро меняется музыка:

• Вот видео с 1 изменением (или тактом) в секунду: оно звучит медленно, но это обычный ритм для классической музыки.
• Вот видео с 2.7 изменениями в секунду: оно звучит намного быстрее, но этот ритм распространен для музыки направления электро.
• Вот видео с 8,3 изменениями в секунду, это очень (очень) быстрый ритм, но и он возможен для небольших частей песен.

Чтобы зафиксировать эти быстрые изменения, вам нужно «нарезать» звук на очень мелкие детали, используя функции окна. Представьте, что вы хотите анализировать частоты звука каждые 1/3 секунды:
На этом рисунке показаны три различных окна: прямоугольное (синее), Хэмминга (зеленое) и Блэкмана (красное). Как я уже говорил, прямоугольное окно похоже просто на «нарезку» сигнала на промежутки, тогда как с окнами Хэмминга и Блэкмана вам нужно умножать окно на оконный сигнал.

Вот так выглядит спектр предыдущего аудиосигнала с выборкой в 4096 сэмплов в каждом окне:


Сигнал дискретизируется на частоте 44.1 Кгц, поэтому продолжительность каждого из 4096 сэмплов составляет 93 мс (4096/44100), а частотное разрешение составляет 10.7 Гц.

Этот рисунок показывает, что все окна изменяют реальный спектр звука. Мы ясно видим, что часть мощности реальных частот распространяется на своих соседей. Спектр, полученный с помощью прямоугольного окна, является наихудшим, поскольку спектральная утечка намного выше, чем у других. Это особенно верно между 40 и 160 Гц. Окно Блэкмана дает спектр, самый близкий к реальному.

Вот тот же пример преобразования Фурье, но уже с 1024 сэмплами:


Частота дискретизации та же, 44.1 кГц, поэтому каждое окно длится 23 мс и частотное разрешение составляет 43 Гц.

И тут получается интересная ситуация: прямоугольное окно дает лучший спектр. У окна Блэкмана почти потеряна частота в 160 Гц из-за спектральной утечки частот в 40 и 320 Гц. Также у этого типа окна теряется частота в 1125 Гц. 

Сравнение обеих фигур показывает, что утечка спектра увеличивается (для всех функций окна) по мере увеличения частотного разрешения. Алгоритм снятия «отпечатка» с песни, используемый Shazam, ищет самые громкие частоты внутри звуковой дорожки. Из-за утечки спектра мы не можем просто взять несколько самых высоких частот — в последнем примере три самые громкие частоты составляют приблизительно 320 Гц, 277 Гц (320-43) и 363 Гц (320 + 43), тогда как существует только частота 320 Гц.

Так какое окно лучше?

Нет «лучших» или «худших» окон. Каждое окно имеет свои особенности и в зависимости от типа мелодии вам может быть удобнее использовать то или иное окно.

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

Окна Блэкмана лучше подходят для случаев, когда утечка спектра сильных частот скрывает слабые частоты. Но эти окна плохо справляются с шумом, поскольку шум будет скрывать больше частот, чем прямоугольное окно. Это является огромной проблемой для алгоритма в Shazam, который должен отсекать шум (например, когда вы пытаетесь узнать с помощью Shazam, что за песня играет в баре или на улице).

Окно Хэмминга находится между этими двумя крайностями и является (на мой взгляд) лучшим выбором для такого алгоритма, как Shazam.

Быстрое преобразование Фурье и трудоемкость

Мужайтесь — это последняя теоретическая выкладка, и начнем мы ее с формулы преобразования Фурье (в последний раз, честно):

Если вы снова посмотрите на эту формулу, вы можете увидеть, что для вычисления одного бина вам нужно сделать N сложений и N умножений (где N — размер окна), то есть получение N бинов требует 2*N² операций, что много.

К примеру, у вас есть трехминутная песня с частотой дискретизацией в 44.1 кГц и 4096 выборками. Вам нужно вычислять по 10.7 преобразований Фурье (ПФ) в секунду, то есть 1938 для всей песни. Каждому преобразованию требуется 3.35*10⁷ операций (2*4096²), то есть для получения всей спектрограммы песни потребуется 6.5*10¹⁰ (65 миллиардов) операций, что крайне много.

А теперь представим, что у вас коллекция из 1000 таких песен. Для получения их спектрограмм вам потребуется уже 6.5*10¹³ операций, что даже с мощным процессором займет несколько дней, если не недель и месяцев.

К счастью, есть более быстрые реализации преобразований Фурье, которые так и называются — быстрые преобразования Фурье (БПФ). И тут для реализации задуманного потребуется «всего» 1.5*N*log(N) операций, что для нашей коллекции выльется в 1.43*10¹¹ операций — а столько хороший процессор обсчитает уже за минуты (ну максимум часы).

В этом примере показан другой компромисс: хотя увеличение размера окна улучшает частотное разрешение, оно также увеличивает время вычислений. Для той же музыкальной коллекции, если вы вычисляете спектрограмму с использованием окна с 512 сэмплами (частотное разрешение 86 Гц), вы получаете результат с помощью БПФ через 1,07*10¹¹ операций — примерно на четверть быстрее, чем с окном в 4096 выборок (частотное разрешение 10,77 Гц).

Уменьшение сложности важно, поскольку, когда вы «шазамите» звук, ваш телефон должен вычислить спектрограмму записанного звука, а мобильный процессор куда менее мощный, чем десктопный.

Снижение частоты дискретизации (даунсэмплинг)

К счастью, есть трюк, который позволяет снизить сложность обсчетов, но при этом поддерживает то же частотное разрешение и одновременно уменьшает размер окна. Он называется даунсэмплингом — то есть снижением частоты дискретизации. Давайте возьмем стандартную песню на частоте 44100 Гц, и изменим ее на 11025 Гц (44100/4) — вы получите такое же частотное разрешение, независимо от того, выполняете ли вы БПФ на 44,1 кГц песне с окном в 4096 сэмплов, или выполняете БПФ на 11 кГц песне с окном в 1024 сэмплов. Единственное различие заключается в том, что воспроизводимая песня будет иметь частоты от 0 до 5 кГц. Но ведь и самая важная часть песни лежит в этом же диапазоне — на самом деле, большинство из вас не услышит большой разницы между музыкой на 11 кГц и музыкой на 44,1 кГц. Таким образом, наиболее важные частоты все еще находятся в воспроизведенной песне, что важно для такого алгоритма, как Shazam.

Даунсэмплинг с 44,1 кГц до 11,025 кГц не очень сложный: простой способ сделать это — взять четыре последовательно идущих сэмпла и усреднить их в один. Единственная сложная часть состоит в том, что перед понижением частоты дискретизации сигнала вам необходимо отфильтровать более высокие частоты в звуке, чтобы избежать наложения частот (вспомните теорему Найквиста-Шеннона). Это можно сделать, используя цифровой фильтр нижних частот.

Но и это не все трюки, которые могут снизить сложность вычислений. Простейшей реализацией БПФ является алгоритм Кули-Туки. Его идея состоит в том, что вместо прямого вычисления ПФ в окне из N сэмплов, данный алгоритм:

• Делит окно из N сэмплов на два окна по N/2 сэмплов;
  
• Вычисляет (рекурсивно) БПФ для двух N/2-сэмпловых окон;
• Эффективно вычисляет БПФ для окна с N сэмплами из двух предыдущих БПФ.
  

Последняя часть состоит только из N операций, так как используется математический трюк с экспоненциальными членами.

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