Jak działa Shazam? Algorytmy rozpoznawania muzyki, odciski palców i przetwarzanie

Słyszysz znajomą piosenkę w klubie lub restauracji. Słuchałeś tej piosenki tysiąc razy dawno temu, a sentymentalizm tej piosenki naprawdę porusza twoje serce. Desperacko chcesz go jutro poznać, ale nie pamiętasz jego nazwy! Na szczęście w naszym niesamowitym futurystycznym świecie masz telefon z zainstalowanym oprogramowaniem do rozpoznawania muzyki i jesteś zbawiony. Możesz się zrelaksować, ponieważ oprogramowanie podało Ci nazwę utworu, a Ty wiesz, że możesz go słyszeć raz za razem, aż stanie się częścią Ciebie… lub znudzi Ci się.

Technologie mobilne, wraz z ogromnym postępem w przetwarzaniu sygnału audio, dały nam twórcom algorytmów możliwość tworzenia rozpoznawania muzyki. Jedną z najpopularniejszych aplikacji do rozpoznawania muzyki jest Shazam. Jeśli przechwycisz 20 sekund utworu, bez względu na to, czy jest to wstęp, zwrotka czy refren, utworzy odcisk palca nagranej próbki, sprawdzi bazę danych i użyje algorytmu rozpoznawania muzyki, aby dokładnie powiedzieć, której piosenki słuchasz .

Ale jak działa Shazam? Algorytm Shazama został ujawniony światu przez jego wynalazcę Avery'ego Li-Chung Wanga w 2003 roku. W tym artykule omówimy podstawy algorytmu rozpoznawania muzyki Shazama.

Analogowo-cyfrowy — próbkowanie sygnału

Czym tak naprawdę jest dźwięk? Czy jest to jakiś mistyczny materiał, którego nie możemy dotknąć, ale który wlatuje do naszych uszu i sprawia, że ​​słyszymy różne rzeczy?

Oczywiście tak nie jest. Wiemy, że w rzeczywistości dźwięk jest wibracją, która rozchodzi się jako mechaniczna fala ciśnienia i przemieszczenia przez medium takie jak powietrze lub woda. Kiedy ta wibracja dociera do naszych uszu, szczególnie do błony bębenkowej, porusza małe kości, które przekazują wibracje dalej do małych komórek rzęsatych znajdujących się głęboko w naszym uchu wewnętrznym. Wreszcie, małe komórki rzęsate wytwarzają impulsy elektryczne, które są przekazywane do naszego mózgu przez nerw słuchowy ucha.

Urządzenia nagrywające dość ściśle naśladują ten proces, wykorzystując ciśnienie fali dźwiękowej do przekształcenia jej w sygnał elektryczny. Faktyczna fala dźwiękowa w powietrzu to ciągły sygnał ciśnienia. W mikrofonie pierwszy element elektryczny, który napotka ten sygnał, zamienia go na analogowy sygnał napięciowy – znowu ciągły. Ten ciągły sygnał nie jest tak przydatny w świecie cyfrowym, więc zanim będzie mógł zostać przetworzony, musi zostać przełożony na sygnał dyskretny, który można zapisać cyfrowo. Odbywa się to poprzez przechwycenie wartości cyfrowej, która reprezentuje amplitudę sygnału.

Konwersja obejmuje kwantyzację danych wejściowych i z konieczności wprowadza niewielki błąd. Dlatego zamiast pojedynczej konwersji przetwornik analogowo-cyfrowy wykonuje wiele konwersji na bardzo małych fragmentach sygnału – proces znany jako próbkowanie

Twierdzenie Nyquista-Shannona mówi nam, jaka częstotliwość próbkowania jest niezbędna do uchwycenia określonej częstotliwości w sygnale ciągłym. W szczególności, aby uchwycić wszystkie częstotliwości, które człowiek może usłyszeć w sygnale dźwiękowym, musimy próbkować sygnał z częstotliwością dwukrotnie większą niż zakres słyszany przez człowieka. Ludzkie ucho może wykryć częstotliwości z grubsza od 20 Hz do 20 000 Hz. W rezultacie dźwięk jest najczęściej nagrywany z częstotliwością próbkowania 44 100 Hz. Jest to częstotliwość próbkowania płyt Compact Disc, a także najczęściej stosowana w przypadku dźwięku MPEG-1 (VCD, SVCD, MP3). (Ta konkretna szybkość została pierwotnie wybrana przez firmę Sony, ponieważ można ją było nagrywać na zmodyfikowanym sprzęcie wideo pracującym z szybkością 25 klatek na sekundę (PAL) lub 30 klatek na sekundę (przy użyciu monochromatycznego rejestratora wideo NTSC) i pokrywać pasmo 20 000 Hz uważane za konieczne do dopasuj ówczesny profesjonalny analogowy sprzęt do nagrywania.) Tak więc, wybierając częstotliwość próbki, która ma być nagrana, prawdopodobnie będziesz chciał wybrać 44100 Hz.

Nagrywanie — przechwytywanie dźwięku

Nagrywanie próbkowanego sygnału audio jest łatwe. Ponieważ współczesne karty dźwiękowe są już wyposażone w przetworniki analogowo-cyfrowe, wystarczy wybrać język programowania, znaleźć odpowiednią bibliotekę, ustawić częstotliwość próbki, liczbę kanałów (zwykle mono lub stereo), wielkość próbki (np. próbki 16-bitowe ). Następnie otwórz linię z karty dźwiękowej, tak jak każdy strumień wejściowy, i zapisz do tablicy bajtów. Oto jak można to zrobić w Javie:

 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();

Wystarczy odczytać dane z TargetDataLine . (W tym przykładzie running flaga jest zmienną globalną, która jest zatrzymywana przez inny wątek - na przykład, jeśli mamy GUI z przyciskiem 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); }

Domena czasu i domena częstotliwości

To, co mamy w tej tablicy bajtów, to sygnał zarejestrowany w dziedzinie czasu. Sygnał w dziedzinie czasu reprezentuje zmianę amplitudy sygnału w czasie.

Na początku XIX wieku Jean-Baptiste Joseph Fourier dokonał niezwykłego odkrycia, że ​​każdy sygnał w dziedzinie czasu jest równoważny sumie pewnej (prawdopodobnie nieskończonej) liczby prostych sygnałów sinusoidalnych, biorąc pod uwagę, że każda sinusoida składowa ma określoną częstotliwość, amplitudę, i faza. Szereg sinusoid, które razem tworzą oryginalny sygnał w dziedzinie czasu, jest znany jako szereg Fouriera.

Innymi słowy, możliwe jest przedstawienie dowolnego sygnału w domenie czasu przez proste podanie zestawu częstotliwości, amplitud i faz odpowiadających każdej sinusoidzie, która tworzy sygnał. Ta reprezentacja sygnału jest znana jako domena częstotliwości. Pod pewnymi względami domena częstotliwości działa jako rodzaj odcisku palca lub sygnatury dla sygnału w dziedzinie czasu, zapewniając statyczną reprezentację sygnału dynamicznego.

Poniższa animacja pokazuje szereg Fouriera dla fali prostokątnej 1 Hz oraz jak (przybliżoną) falę prostokątną można wygenerować ze składowych sinusoidalnych. Sygnał jest pokazany w domenie czasu powyżej i w domenie częstotliwości poniżej.

Analiza sygnału w domenie częstotliwości znacznie upraszcza wiele rzeczy. Jest to wygodniejsze w świecie cyfrowego przetwarzania sygnałów, ponieważ inżynier może zbadać widmo (reprezentację sygnału w domenie częstotliwości) i określić, które częstotliwości są obecne, a których brakuje. Następnie można dokonać filtrowania, zwiększyć lub zmniejszyć niektóre częstotliwości lub po prostu rozpoznać dokładny ton z danych częstotliwości.

Dyskretna transformata Fouriera

Musimy więc znaleźć sposób na przekształcenie naszego sygnału z domeny czasu do domeny częstotliwości. W tym przypadku zwracamy się o pomoc do Dyskretnej Transformacji Fouriera (DFT). DFT to matematyczna metodologia wykonywania analizy Fouriera na dyskretnym (próbkowanym) sygnale. Konwertuje skończoną listę równomiernie rozmieszczonych próbek funkcji na listę współczynników skończonej kombinacji złożonych sinusoid, uporządkowanych według ich częstotliwości, poprzez rozważenie, czy te sinusoidy były próbkowane z tą samą częstotliwością.

Jednym z najpopularniejszych algorytmów numerycznych do obliczania DFT jest szybka transformata Fouriera (FFT). Zdecydowanie najczęściej stosowaną odmianą FFT jest algorytm Cooleya-Tukeya. Jest to algorytm dziel i zwyciężaj, który rekurencyjnie dzieli DFT na wiele mniejszych DFT. Podczas gdy ocena DFT bezpośrednio wymaga operacji O( n 2 ) , w przypadku FFT Cooleya-Tukeya ten sam wynik jest obliczany w operacjach O ( n log n ) .

Nie jest trudno znaleźć odpowiednią bibliotekę do FFT. Oto kilka z nich:

• C – FFTW
• C++ – Własna FFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (Interfejs do FFTW)

Poniżej znajduje się przykład funkcji FFT napisanej w Javie. (FFT przyjmuje liczby zespolone jako dane wejściowe. Aby zrozumieć związek między liczbami zespolonymi a funkcjami trygonometrycznymi, przeczytaj o wzorze Eulera.)

 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; }

A oto przykład sygnału przed i po analizie FFT:

Rozpoznawanie muzyki: odciski palców w utworze

Jednym niefortunnym efektem ubocznym FFT jest to, że tracimy wiele informacji na temat synchronizacji. (Chociaż teoretycznie można tego uniknąć, koszty wykonania są ogromne.) W przypadku trzyminutowej piosenki widzimy wszystkie częstotliwości i ich wielkości, ale nie mamy pojęcia, kiedy w piosence się pojawiły. Ale to jest kluczowa informacja, która sprawia, że ​​piosenka jest tym, czym jest! W jakiś sposób musimy wiedzieć, w którym momencie pojawiła się każda częstotliwość.

Dlatego wprowadzamy rodzaj przesuwanego okna lub fragmentu danych i przekształcamy tylko tę część informacji. Rozmiar każdego kawałka można określić na kilka różnych sposobów. Na przykład, jeśli nagramy dźwięk w stereo, z 16-bitowymi próbkami, z częstotliwością 44100 Hz, jedna sekunda takiego dźwięku będzie 44100 próbkami * 2 bajty * 2 kanały ≈ 176 kB. Jeśli wybierzemy 4 kB jako rozmiar kawałka, będziemy mieli 44 porcje danych do analizy w każdej sekundzie utworu. To wystarczająca gęstość do szczegółowej analizy potrzebnej do identyfikacji dźwięku.

Wróćmy teraz do programowania:

 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); }

W pętli wewnętrznej wstawiamy dane z dziedziny czasu (próbki) do liczby zespolonej z częścią urojoną 0. W pętli zewnętrznej iterujemy przez wszystkie fragmenty i na każdym przeprowadzamy analizę FFT.

Gdy mamy już informacje o składzie częstotliwości sygnału, możemy zacząć tworzyć nasz cyfrowy odcisk palca utworu. To najważniejsza część całego procesu rozpoznawania dźwięku Shazam. Głównym wyzwaniem jest to, jak w oceanie uchwyconych częstotliwości odróżnić, które częstotliwości są najważniejsze. Intuicyjnie wyszukujemy częstotliwości o największej wartości (potocznie nazywane szczytami).

Jednak w jednym utworze zakres silnych częstotliwości może wahać się od niskiego C – C1 (32,70 Hz) do wysokiego C – C8 (4186,01 Hz). To ogromny okres do omówienia. Zamiast więc analizować cały zakres częstotliwości na raz, możemy wybrać kilka mniejszych interwałów, wybranych na podstawie wspólnych częstotliwości ważnych składowych muzycznych i analizować każdy z osobna. Na przykład możemy użyć interwałów wybranych przez tego faceta do implementacji algorytmu Shazama. Są to 30 Hz - 40 Hz, 40 Hz - 80 Hz i 80 Hz - 120 Hz dla niskich tonów (na przykład pokrycie gitary basowej) oraz 120 Hz - 180 Hz i 180 Hz - 300 Hz dla średnich i wyższych tonów (obejmujący wokale i większość innych instrumentów).

Teraz w każdym przedziale możemy po prostu zidentyfikować częstotliwość o najwyższej wartości. Te informacje tworzą sygnaturę dla tego fragmentu piosenki, a sygnatura ta staje się częścią odcisku palca całej piosenki.

 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)); }

Zwróć uwagę, że musimy założyć, że nagranie nie zostało wykonane w idealnych warunkach (tj. „głucho pokoju”), a co za tym idzie, musimy uwzględnić współczynnik rozmycia. Analizę współczynnika rozmycia należy traktować poważnie, aw rzeczywistym systemie program powinien mieć możliwość ustawienia tego parametru na podstawie warunków rejestracji.

Aby ułatwić wyszukiwanie audio, podpis ten staje się kluczem w tablicy mieszającej. Odpowiednia wartość to czas, w którym ten zestaw częstotliwości pojawił się w utworze, wraz z identyfikatorem utworu (tytułem utworu i wykonawcą). Oto przykład, jak te rekordy mogą wyglądać w bazie danych.

Jeśli uruchomimy całą bibliotekę utworów w ramach tego procesu identyfikacji muzyki, możemy zbudować bazę danych z kompletnym odciskiem palca każdej piosenki w bibliotece.

Algorytm muzyczny: identyfikacja utworu

Aby zidentyfikować piosenkę, która jest aktualnie odtwarzana w klubie, nagrywamy ją za pomocą naszego telefonu i przeprowadzamy nagranie przez ten sam proces odcisków palców, jak powyżej. Następnie możemy rozpocząć przeszukiwanie bazy danych w poszukiwaniu pasujących tagów hash.

Tak się składa, że ​​wiele hashtagów będzie odpowiadać identyfikatorowi muzycznemu wielu utworów. Na przykład może się zdarzyć, że jakiś utwór A brzmi dokładnie tak samo, jak utwór E. Oczywiście nie jest to zaskakujące – muzycy zawsze „pożyczali” od siebie zagrywki i riffy, a obecnie producenci samplują wszystkie inne utwory. czas. Za każdym razem, gdy dopasowujemy hash tag, liczba możliwych dopasowań zmniejsza się, ale jest prawdopodobne, że sama ta informacja nie zawęzi dopasowania do jednego utworu. Jest jeszcze jedna rzecz, którą musimy sprawdzić za pomocą naszego algorytmu rozpoznawania muzyki, a jest to czas.

Próbka, którą nagraliśmy w klubie, może pochodzić z dowolnego miejsca w piosence, więc nie możemy po prostu dopasować znacznika czasu dopasowanego skrótu do znacznika czasu naszej próbki. Jednak dzięki wielu dopasowanym haszom możemy analizować względny czas dopasowań, a tym samym zwiększyć naszą pewność.

Na przykład, jeśli spojrzysz w powyższą tabelę, zobaczysz, że hash tag 30 51 99 121 195 odpowiada zarówno utworowi A, jak i piosence E. Jeśli sekundę później dopasujemy hash 34 57 95 111 200 , to jest o jeden więcej pasuje do utworu A, ale w tym przypadku wiemy, że pasują zarówno skróty, jak i różnice czasowe.

 // 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; } }

Weźmy i 1 i i 2 jako momenty w nagranym utworze, a j 1 i j 2 jako momenty w utworze z bazy danych. Możemy powiedzieć, że mamy dwa mecze z różnicą czasu, jeśli:

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

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

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

Daje nam to elastyczność w nagrywaniu utworu od początku, środka lub końca.

Wreszcie, jest mało prawdopodobne, aby każdy moment piosenki, którą nagrywamy w klubie, pasował do każdego odpowiadającego mu momentu tego samego utworu w naszej bibliotece, nagranego w studio. Nagranie będzie zawierało dużo szumu, który wprowadzi pewien błąd w meczach. Tak więc zamiast próbować wyeliminować z naszej listy dopasowań wszystkie utwory poza właściwą, na samym końcu sortujemy wszystkie dopasowane utwory w porządku malejącym według prawdopodobieństwa, a naszą ulubioną jest pierwsza piosenka na liście rankingowej.

Od góry do dołu

Aby odpowiedzieć na pytanie „Jak działa Shazam?” oto przegląd całego procesu rozpoznawania i dopasowywania muzyki, od góry do dołu:

W przypadku tego rodzaju systemu baza danych może być bardzo duża, dlatego ważne jest, aby użyć jakiejś skalowalnej bazy danych. Nie ma specjalnej potrzeby tworzenia relacji, a model danych jest dość prosty, więc jest to dobry przypadek do użycia jakiejś bazy danych NoSQL.

Jak działa Shazam? Teraz wiesz

Tego rodzaju oprogramowania do rozpoznawania utworów można używać do wyszukiwania podobieństw między utworami. Teraz, gdy rozumiesz, jak działa Shazam, możesz zobaczyć, jak może to mieć zastosowanie poza zwykłym Shazamowaniem tej nostalgicznej piosenki granej w taksówkowym radiu. Na przykład może pomóc zidentyfikować plagiat w muzyce lub dowiedzieć się, kto był początkową inspiracją dla niektórych pionierów bluesa, jazzu, rocka, popu lub jakiegokolwiek innego gatunku. Może dobrym eksperymentem byłoby wypełnienie bazy próbek utworów muzyką klasyczną Bacha, Beethovena, Vivaldiego, Wagnera, Chopina i Mozarta i spróbowanie znalezienia podobieństw między utworami. Można by pomyśleć, że nawet Bob Dylan, Elvis Presley i Robert Johnson byli plagiatorami!

Ale nadal nie możemy ich skazać, ponieważ muzyka jest tylko falą, którą słyszymy, zapamiętujemy i powtarzamy w naszych głowach, gdzie ewoluuje i zmienia się, aż nagramy ją w studio i przekażemy kolejnemu wielkiemu muzycznemu geniuszowi.