Как работает Шазам? Алгоритмы распознавания музыки, снятие отпечатков пальцев и обработка

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

Мобильные технологии, наряду с огромным прогрессом в обработке аудиосигналов, дали нам, разработчикам алгоритмов, возможность создавать распознаватели музыки. Одним из самых популярных приложений для распознавания музыки является Shazam. Если вы запишите 20 секунд песни, будь то вступление, куплет или припев, он создаст отпечаток пальца для записанного семпла, сверится с базой данных и использует свой алгоритм распознавания музыки, чтобы точно сказать вам, какую песню вы слушаете. .

Но как работает Shazam? Алгоритм Shazam был представлен миру его изобретателем Эйвери Ли-Чунг Ван в 2003 году. В этой статье мы рассмотрим основы алгоритма распознавания музыки Shazam.

Аналого-цифровой — выборка сигнала

Что такое звук на самом деле? Это какой-то мистический материал, к которому мы не можем прикоснуться, но который влетает в наши уши и заставляет нас слышать?

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

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

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

Теорема Найквиста-Шеннона говорит нам, какая частота дискретизации необходима для захвата определенной частоты в непрерывном сигнале. В частности, чтобы захватить все частоты, которые человек может слышать в звуковом сигнале, мы должны произвести выборку сигнала на частоте, в два раза превышающей диапазон человеческого слуха. Человеческое ухо может различать частоты примерно от 20 Гц до 20 000 Гц. В результате звук чаще всего записывается с частотой дискретизации 44 100 Гц. Это частота дискретизации компакт-дисков, а также наиболее часто используемая частота со звуком MPEG-1 (VCD, SVCD, MP3). (Эта конкретная скорость была первоначально выбрана Sony, потому что она может быть записана на модифицированном видеооборудовании, работающем со скоростью 25 кадров в секунду (PAL) или 30 кадров в секунду (с использованием монохромного видеомагнитофона NTSC) и охватывает полосу пропускания 20 000 Гц, которая считается необходимой для соответствуют профессиональному аналоговому записывающему оборудованию того времени.) Таким образом, при выборе частоты сэмпла, который необходимо записать, вы, вероятно, захотите выбрать 44 100 Гц.

Запись - Захват звука

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

 private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //mono boolean signed = true; //Indicates whether the data is signed or unsigned boolean bigEndian = true; //Indicates whether the audio data is stored in big-endian or little-endian order return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //Fill AudioFormat with the settings DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start();

Просто прочитайте данные из TargetDataLine . (В этом примере флаг running — это глобальная переменная, которая останавливается другим потоком — например, если у нас есть графический интерфейс с кнопкой STOP.)

 OutputStream out = new ByteArrayOutputStream(); running = true; try { while (running) { int count = line.read(buffer, 0, buffer.length); if (count > 0) { out.write(buffer, 0, count); } } out.close(); } catch (IOException e) { System.err.println("I/O problems: " + e); System.exit(-1); }

Временная и частотная области

В этом массиве байтов мы имеем сигнал, записанный во временной области. Сигнал во временной области представляет собой изменение амплитуды сигнала во времени.

В начале 1800-х годов Жан-Батист Жозеф Фурье сделал замечательное открытие, что любой сигнал во временной области эквивалентен сумме некоторого (возможно, бесконечного) числа простых синусоидальных сигналов, учитывая, что каждая составляющая синусоиды имеет определенную частоту, амплитуду, и фаза. Ряд синусоид, которые вместе образуют исходный сигнал во временной области, известен как его ряд Фурье.

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

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

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

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

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

Одним из наиболее популярных численных алгоритмов расчета ДПФ является быстрое преобразование Фурье (БПФ). На сегодняшний день наиболее часто используемым вариантом БПФ является алгоритм Кули-Тьюки. Это алгоритм «разделяй и властвуй», который рекурсивно делит ДПФ на множество меньших ДПФ. В то время как для вычисления ДПФ напрямую требуется O( n 2 ) операций, с БПФ Кули-Тьюки тот же результат вычисляется за O( n log n ) операций.

Нетрудно найти подходящую библиотеку для БПФ. Вот некоторые из них:

• С - ФФТВ
• C++ — собственное БПФ
• Java — JTransform
• Питон — NumPy
• Ruby — Ruby-FFTW3 (интерфейс к FFTW)

Ниже приведен пример функции БПФ, написанной на Java. (БПФ использует в качестве входных данных комплексные числа. Чтобы понять взаимосвязь между комплексными числами и тригонометрическими функциями, прочитайте формулу Эйлера.)

 public static Complex[] fft(Complex[] x) { int N = x.length; // fft of even terms Complex[] even = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft of odd terms Complex[] odd = even; // reuse the array for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); // combine Complex[] y = new Complex[N]; for (int k = 0; k < N / 2; k++) { double kth = -2 * k * Math.PI / N; Complex wk = new Complex(Math.cos(kth), Math.sin(kth)); y[k] = q[k].plus(wk.times(r[k])); y[k + N / 2] = q[k].minus(wk.times(r[k])); } return y; }

А вот пример сигнала до и после анализа БПФ:

Распознавание музыки: отпечаток песни

Один неприятный побочный эффект БПФ заключается в том, что мы теряем большое количество информации о времени. (Хотя теоретически этого можно избежать, накладные расходы на производительность огромны.) Для трехминутной песни мы видим все частоты и их амплитуды, но понятия не имеем, когда в песне они появились. Но это ключевая информация, которая делает песню такой, какая она есть! Каким-то образом нам нужно знать, в какой момент времени появилась каждая частота.

Вот почему мы вводим своего рода скользящее окно или фрагмент данных и преобразуем только эту часть информации. Размер каждого фрагмента можно определить несколькими способами. Например, если мы запишем звук в стереофоническом режиме с 16-битными сэмплами на частоте 44 100 Гц, одна секунда такого звука будет составлять 44 100 сэмплов * 2 байта * 2 канала ≈ 176 кБ. Если мы выберем 4 КБ для размера фрагмента, у нас будет 44 фрагмента данных для анализа в каждой секунде песни. Это достаточно хорошая плотность для детального анализа, необходимого для идентификации звука.

Теперь вернемся к программированию:

 byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i < sampledChunkSize; j++) { Complex[chunkSize] complexArray; for(int i = 0; i < chunkSize; i++) { complexArray[i] = Complex(audio[(j*chunkSize)+i], 0); } result[j] = FFT.fft(complexArray); }

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

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

Однако в одной песне диапазон сильных частот может варьироваться между низким C-C1 (32,70 Гц) и высоким C-C8 (4186,01 Гц). Это огромный интервал для покрытия. Таким образом, вместо того, чтобы анализировать сразу весь частотный диапазон, мы можем выбрать несколько меньших интервалов, выбранных на основе общих частот важных музыкальных компонентов, и проанализировать каждый в отдельности. Например, мы можем использовать интервалы, которые этот парень выбрал для своей реализации алгоритма Shazam. Это 30 Гц - 40 Гц, 40 Гц - 80 Гц и 80 Гц - 120 Гц для низких тонов (например, охватывающих бас-гитару), и 120 Гц - 180 Гц и 180 Гц - 300 Гц для средних и высоких тонов. (кавер-вокал и большинство других инструментов).

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

 public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; // find out in which range is frequency public int getIndex(int freq) { int i = 0; while (RANGE[i] < freq) i++; return i; } // result is complex matrix obtained in previous step for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { // Get the magnitude: double mag = Math.log(results[t][freq].abs() + 1); // Find out which range we are in: int index = getIndex(freq); // Save the highest magnitude and corresponding frequency: if (mag > highscores[t][index]) { points[t][index] = freq; } } // form hash tag long h = hash(points[t][0], points[t][1], points[t][2], points[t][3]); } private static final int FUZ_FACTOR = 2; private long hash(long p1, long p2, long p3, long p4) { return (p4 - (p4 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR)) * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100 + (p1 - (p1 % FUZ_FACTOR)); }

Обратите внимание, что мы должны предполагать, что запись производится не в идеальных условиях (т. е. в «глухой комнате»), и в результате мы должны учитывать фактор размытия. К анализу фазз-фактора следует относиться серьезно, и в реальной системе программа должна иметь возможность устанавливать этот параметр в зависимости от условий записи.

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

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

Музыкальный алгоритм: идентификация песни

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

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

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

Например, если вы посмотрите на таблицу выше, вы увидите, что хэштег 30 51 99 121 195 соответствует и песне A, и песне E. Если через секунду мы сопоставим хеш 34 57 95 111 200 , это еще один совпадают с песней А, но в этом случае мы знаем, что и хэши, и разница во времени совпадают.

 // Class that represents specific moment in a song private class DataPoint { private int time; private int songId; public DataPoint(int songId, int time) { this.songId = songId; this.time = time; } public int getTime() { return time; } public int getSongId() { return songId; } }

Возьмем i 1 и i 2 за моменты в записанной песне, а j 1 и j 2 за моменты в песне из базы данных. Мы можем сказать, что у нас есть два совпадения с разницей во времени, если:

<span style=font-family: TimesNewRoman;> RecordedHash(i 1 ) = SongInDBHash(j 1 ) AND RecordedHash(i 2 ) = SongInDBHash(j 2 ) </span>

<span style=font-family: TimesNewRoman;>И</span>

<span style=font-family: TimesNewRoman;> абс (i 1 - i 2 ) = абс (j 1 - j 2 ) </span>

Это дает нам возможность записывать песню с начала, середины или конца.

Наконец, маловероятно, что каждый отдельный момент песни, которую мы записываем в клубе, будет соответствовать каждому соответствующему моменту той же песни в нашей библиотеке, записанной в студии. Запись будет содержать много шума, что внесет некоторую погрешность в матчи. Таким образом, вместо того, чтобы пытаться исключить все песни, кроме правильной, из нашего списка совпадений, в самом конце мы сортируем все совпавшие песни в порядке убывания вероятности, и наша любимая песня — первая в списке.

Сверху донизу

Чтобы ответить на вопрос «Как работает Shazam?» вот обзор всего процесса распознавания и сопоставления музыки сверху вниз:

Для системы такого типа база данных может стать довольно большой, поэтому важно использовать масштабируемую базу данных. Нет особой необходимости в отношениях, а модель данных оказывается довольно простой, поэтому это хороший случай для использования какой-либо базы данных NoSQL.

Как работает Шазам? Теперь ты знаешь

Такое программное обеспечение для распознавания песен можно использовать для поиска сходства между песнями. Теперь, когда вы понимаете, как работает Shazam, вы можете увидеть, как это может иметь приложения, помимо простого шазамирования той ностальгической песни, которая играет на радио такси. Например, это может помочь выявить плагиат в музыке или выяснить, кто был первоначальным источником вдохновения для некоторых пионеров блюза, джаза, рока, поп-музыки или любого другого жанра. Возможно, хорошим экспериментом было бы заполнить базу данных образцов классической музыкой Баха, Бетховена, Вивальди, Вагнера, Шопена и Моцарта и попытаться найти сходство между песнями. Можно подумать, что даже Боб Дилан, Элвис Пресли и Роберт Джонсон были плагиаторами!

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