Чувате позната песен в клуба или ресторанта. Слушали сте тази песен хиляда пъти отдавна и сантименталността на песента наистина докосва сърцето ви. Отчаяно искате да го почувствате утре, но не можете да си спомните името му! За щастие, в нашия невероятен футуристичен свят имате телефон с инсталиран софтуер за разпознаване на музика и сте спасени. Можете да се отпуснете, защото софтуерът ви казва името на песента и вие знаете, че можете да я чувате отново и отново, докато тя стане част от вас ... или не ви стане лошо от нея.

разпознаване

Мобилните технологии, заедно с огромния напредък в обработката на аудио сигнали, ни дадоха способността на разработчиците на алгоритми да създаваме разпознаватели на музика. Едно от най-популярните приложения за разпознаване на музика е Shazam. Ако заснемете 20 секунди на песен, без значение дали е интро, стих или припев, тя ще създаде пръстов отпечатък за записаната проба, ще направи справка в базата данни и ще използва нейния алгоритъм за разпознаване на музика, за да ви каже точно коя песен слушате.

Но как работи Shazam? Алгоритъмът на Shazam беше разкрит на света от изобретателя му Avery Li-Chung Wang през 2003 г. В тази статия ще разгледаме основите на алгоритъма за разпознаване на музика на Shazam.

Аналогово към цифрово - вземане на проби от сигнал

Какво всъщност е звукът? Дали това е някакъв мистичен материал, който не можем да докоснем, но който лети в ушите ни и ни кара да чуваме нещата?

Разбира се, това не е съвсем така. Знаем, че в действителност звукът е вибрация, която се разпространява като механична вълна на натиск и изместване, чрез среда като въздух или вода. Когато тази вибрация дойде до ушите ни, особено тъпанчето, тя движи малки кости, които предават вибрацията по-нататък на малки космени клетки дълбоко във вътрешното ни ухо. И накрая, малките космени клетки произвеждат електрически импулси, които се предават на нашия мозък чрез слуховия ушен нерв.

Записващите устройства имитират този процес доста отблизо, като използват налягането на звуковата вълна, за да я преобразуват в електрически сигнал. Действителната звукова вълна във въздуха е непрекъснат сигнал за налягане. В микрофона първият електрически компонент, срещащ този сигнал, го преобразува в аналогов сигнал на напрежение - отново непрекъснат. Този непрекъснат сигнал не е толкова полезен в цифровия свят, така че преди да може да бъде обработен, той трябва да бъде преобразуван в дискретен сигнал, който може да се съхранява цифрово. Това се прави чрез улавяне на цифрова стойност, която представлява амплитудата на сигнала.

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

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

Запис - улавяне на звука

Записването на дискретизиран аудио сигнал е лесно. Тъй като съвременните звукови карти вече се предлагат с аналогово-цифрови преобразуватели, просто изберете език за програмиране, намерете подходяща библиотека, задайте честотата на извадката, броя на каналите (обикновено моно или стерео), размера на извадката (например 16-битови проби ). След това отворете линията от звуковата си карта, точно както всеки входен поток, и напишете в байт масив. Ето как това може да се направи в Java:

Просто прочетете данните от TargetDataLine. (В този пример текущият флаг е глобална променлива, която се спира от друга нишка - например, ако имаме GUI с бутона STOP.)

Времева област и Честотна област

Това, което имаме в този байтов масив, е сигнал, записан във времевата област. Сигналът от времевата област представлява промяната на амплитудата на сигнала във времето.

В началото на 1800 г. Жан-Батист Жозеф Фурие прави забележителното откритие, че всеки сигнал във времевата област е еквивалентен на сумата от някакъв (вероятно безкраен) брой прости синусоидални сигнали, като се има предвид, че всеки компонент синусоида има определена честота, амплитуда, и фаза. Поредицата от синусоиди, които заедно образуват оригиналния сигнал от времева област, е известна като неговата серия на Фурие.

С други думи, възможно е да се представи всеки сигнал във времева област, като просто се даде набор от честоти, амплитуди и фази, съответстващи на всяка синусоида, съставляваща сигнала. Това представяне на сигнала е известно като честотна област. По някакъв начин честотната област действа като вид пръстов отпечатък или подпис за сигнала от времевата област, осигурявайки статично представяне на динамичен сигнал.

Следващата анимация демонстрира поредицата на Фурие на квадратна вълна от 1 Hz и как (приблизителна) квадратна вълна може да бъде генерирана от синусоидални компоненти. Сигналът е показан във времевия домейн по-горе и честотния домейн по-долу.

Анализът на сигнал в честотната област опростява изключително много неща. По-удобно е в света на цифровата обработка на сигнала, защото инженерът може да проучи спектъра (представянето на сигнала в честотната област) и да определи кои честоти присъстват и кои липсват. След това може да се направи филтриране, увеличаване или намаляване на някои честоти или просто разпознаване на точния тон от дадените честоти.

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

Затова трябва да намерим начин да преобразуваме нашия сигнал от времевия домейн в честотния. Тук се обръщаме за помощ към дискретното преобразуване на Фурие (DFT). DFT е математическа методология за извършване на анализ на Фурие върху дискретен (изваден) сигнал. Той преобразува краен списък с еднакво разположени извадки на функция в списък с коефициенти на крайна комбинация от сложни синусоиди, подредени по техните честоти, като преценява дали тези синусоиди са взети проби със същата скорост.

Един от най-популярните числени алгоритми за изчисляване на DFT е бързото преобразуване на Фурие (FFT). Далеч най-често използваният вариант на FFT е алгоритъмът на Кули-Тюки. Това е алгоритъм за разделяне и завладяване, който рекурсивно разделя DFT на много по-малки DFT. Докато оценката на DFT директно изисква O (n 2) операции, с БПФ Cooley-Tukey същия резултат се изчислява в O (n log n) операции.

Не е трудно да се намери подходяща библиотека за БПФ. Ето няколко от тях:

  • ° С - FFTW
  • ° С++ - EigenFFT
  • Java - JTransform
  • Python - NumPy
  • Руби - Ruby-FFTW3 (Интерфейс към FFTW)

По-долу е даден пример за FFT функция, написана на Java. (FFT приема сложни числа като вход. За да разберете връзката между комплексни числа и тригонометрични функции, прочетете за формулата на Euler.)

И ето пример за сигнал преди и след FFT анализ:

Разпознаване на музика: Отпечатване на песен с пръстови отпечатъци

Един нещастен страничен ефект на FFT е, че губим много информация за времето. (Въпреки че теоретично това може да се избегне, режийните разходи за изпълнение са огромни.) За триминутна песен виждаме всички честоти и техните величини, но нямаме представа кога в песента са се появили. Но това е ключовата информация, която прави песента такава, каквато е! По някакъв начин трябва да знаем в кой момент от времето се е появила всяка честота.

Ето защо въвеждаме някакъв плъзгащ се прозорец или парче от данни и трансформираме само тази част от информацията. Размерът на всяко парче може да бъде определен по няколко различни начина. Например, ако запишем звука, в стерео, с 16-битови семпли, при 44 100 Hz, една секунда от такъв звук ще бъде 44 100 семпли * 2 байта * 2 канала ≈ 176 kB. Ако изберем 4 kB за размера на парче, ще имаме 44 парчета данни, които да анализираме във всяка секунда от песента. Това е достатъчно добра плътност за подробен анализ, необходим за аудио идентификация.

Сега да се върнем към програмирането:

Във вътрешния цикъл поставяме данните от времевия домейн (пробите) в комплексно число с въображаема част 0. Във външния цикъл ние итерираме през всички парчета и извършваме FFT анализ на всеки.

След като имаме информация за честотния състав на сигнала, можем да започнем да формираме цифровия си пръстов отпечатък на песента. Това е най-важната част от целия процес на разпознаване на аудио в Shazam. Основното предизвикателство тук е как да различим в океана от уловените честоти кои честоти са най-важни. Интуитивно търсим честотите с най-голяма величина (обикновено наричани пикове).

Въпреки това, в една песен диапазонът на силните честоти може да варира между ниски C - C1 (32.70 Hz) и високи C - C8 (4.186,01 Hz). Това е огромен интервал за покриване. Така че вместо да анализираме целия честотен диапазон наведнъж, можем да изберем няколко по-малки интервала, избрани въз основа на общите честоти на важни музикални компоненти, и да анализираме всеки поотделно. Например, можем да използваме интервалите, които този човек е избрал за изпълнението на алгоритъма Shazam. Това са 30 Hz - 40 Hz, 40 Hz - 80 Hz и 80 Hz - 120 Hz за ниските тонове (покриващи бас китара например) и 120 Hz - 180 Hz и 180 Hz - 300 Hz за средните и по-високите тонове (обхваща вокали и повечето други инструменти).

Сега в рамките на всеки интервал можем просто да идентифицираме честотата с най-голяма величина. Тази информация формира подпис за тази част от песента и този подпис става част от пръстовия отпечатък на песента като цяло.

Имайте предвид, че трябва да приемем, че записът не е направен в перфектни условия (т.е. „глуха стая“) и в резултат трябва да включим коефициент на размиване. Анализът на фазовия фактор трябва да се вземе на сериозно и в реална система програмата трябва да има опция за задаване на този параметър въз основа на условията на записа.

За да улесни търсенето на аудио, този подпис става ключът в хеш таблица. Съответната стойност е времето, в което този набор от честоти се е появил в песента, заедно с идентификатора на песента (заглавие на песента и изпълнител). Ето пример за това как тези записи могат да се показват в базата данни.

Hash Tag Time в секунди Песен
30 51 99 121 195 53,52 Песен А от изпълнител А
33 56 92 151 185 12.32 Песен Б от изпълнител Б
39 26 89 141 251 15.34 Песен C от изпълнител C
32 67 100 128 270 78.43 Песен D от изпълнител D
30 51 99 121 195 10,89 Песен Е от изпълнител Е
34 57 95 111 200 54,52 Песен А от изпълнител А
34 41 93 161 202 11,89 Песен Е от изпълнител Е

Ако стартираме цяла библиотека с песни през този процес на идентификация на музиката, можем да изградим база данни с пълен пръстов отпечатък на всяка песен в библиотеката.

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

За да идентифицираме песен, която в момента се възпроизвежда в клуба, записваме песента с телефона си и стартираме записа през същия аудио процес на пръстови отпечатъци, както по-горе. След това можем да започнем да търсим в базата данни за съвпадение на хеш тагове.

Както се случва, много от хеш таговете ще съответстват на музикалния идентификатор на множество песни. Например може да се окаже, че някое парче от песен А звучи точно като някакво парче Е. Разбира се, това не е изненадващо - музикантите винаги са „взаимствали“ близки и рифове един от друг, а в наши дни продуцентите вземат проби от всички песни времето. Всеки път, когато съвпадаме с хеш-маркер, броят на възможните съвпадения става по-малък, но е вероятно само тази информация да не ограничи съвпадението до една песен. Така че има още едно нещо, което трябва да проверим с нашия алгоритъм за разпознаване на музика, а това е времето.

Пробата, която записахме в клуба, може да е от която и да е точка в песента, така че не можем просто да съпоставим клеймото на съответстващия хеш с клеймото на нашата проба. Въпреки това, с множество съвпадащи хешове, можем да анализираме относителното време на мачовете и следователно да увеличим нашата сигурност.

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

Да вземем i 1 и i 2 като моменти в записаната песен и j 1 и j 2 като моменти в песента от базата данни. Можем да кажем, че имаме два мача с времева разлика, ако:

RecordedHash (i 1) = SongInDBHash (j 1) И RecordedHash (i 2) = SongInDBHash (j 2)

абс (i 1 - i 2) = abs (j 1 - j 2)

Това ни дава гъвкавост да записваме песента от началото, средата или края.

И накрая, малко вероятно е всеки един момент от песента, която записваме в клуба, да съответства на всеки съответстващ момент на същата песен в нашата библиотека, записана в студиото. Записът ще включва много шум, който ще внесе известна грешка в мачовете. Така че вместо да се опитваме да елиминираме всички освен правилната песен от нашия списък със съвпадения, в самия край, ние сортираме всички съвпадащи песни в низходящ ред на вероятност и нашата любима е първата песен в класацията.

От горе до долу

За да отговорите на въпроса „Как работи Shazam?“ ето преглед на целия процес на разпознаване и съвпадение на музиката, отгоре надолу:

За този вид система базата данни може да стане доста огромна, така че е важно да се използва някаква скалируема база данни. Няма специална нужда от връзки и моделът на данни в крайна сметка е доста прост, така че е добър случай за използване на някаква база данни NoSQL.

Как работи Shazam? Сега знаеш

Този вид софтуер за разпознаване на песни може да се използва за намиране на приликите между песните. Сега, след като разбрахте как работи Shazam, можете да видите как това може да има приложения, освен просто Shazaming, тази носталгична песен, която звучи по радиото на такси. Например, това може да помогне да се идентифицира плагиатството в музиката или да се разбере кой е бил първоначалното вдъхновение за някои пионери на блуса, джаза, рока, попа или друг жанр. Може би добър експеримент би бил да се попълни базата данни от песни с класическата музика на Бах, Бетовен, Вивалди, Вагнер, Шопен и Моцарт и да се опита да намери приликите между песните. Бихте си помислили, че дори Боб Дилън, Елвис Пресли и Робърт Джонсън са били плагиатори!

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

Разбиране на основите

Как работи алгоритъмът Shazam?

Алгоритъмът Shazam дестилира проби от песен в пръстови отпечатъци и съпоставя тези пръстови отпечатъци с пръстови отпечатъци от известни песни, като взема предвид тяхното време спрямо песента.

Какво е аудио пръстов отпечатък?

Звуковият пръстов отпечатък е колекция от хеш тагове или подписи на образци на песен. Те измерват кои честоти във всяка проба са най-силни.

Как Shazam намира музика?

Shazam намира музика, като сравнява звуковия пръстов отпечатък на предоставен от потребителя запис с пръстови отпечатъци на известни песни от своята база данни.