Bagaimana cara kerja Shazam? Algoritma Pengenalan Musik, Sidik Jari, dan Pemrosesan

Anda mendengar lagu yang familiar di klub atau restoran. Anda mendengarkan lagu ini ribuan kali yang lalu, dan sentimentalitas lagu tersebut sangat menyentuh hati Anda. Anda sangat ingin memberinya hati besok, tetapi Anda tidak dapat mengingat namanya! Untungnya, di dunia futuristik kita yang menakjubkan, Anda memiliki telepon dengan perangkat lunak pengenalan musik yang diinstal, dan Anda diselamatkan. Anda dapat bersantai, karena perangkat lunak memberi tahu Anda nama lagunya, dan Anda tahu bahwa Anda dapat mendengarnya lagi dan lagi hingga lagu itu menjadi bagian dari diri Anda…atau Anda bosan karenanya.

Teknologi seluler, bersama dengan kemajuan besar dalam pemrosesan sinyal audio, telah memberi kami kemampuan kepada pengembang algoritme untuk membuat pengenal musik. Salah satu aplikasi pengenalan musik paling populer adalah Shazam. Jika Anda merekam 20 detik sebuah lagu, tidak peduli apakah itu intro, verse, atau chorus, itu akan membuat sidik jari untuk sampel yang direkam, berkonsultasi dengan database, dan menggunakan algoritme pengenalan musiknya untuk memberi tahu Anda dengan tepat lagu mana yang sedang Anda dengarkan .

Tapi bagaimana Shazam bekerja? Algoritme Shazam diungkapkan ke dunia oleh penemunya Avery Li-Chung Wang pada tahun 2003. Dalam artikel ini kita akan membahas dasar-dasar algoritme pengenalan musik Shazam.

Analog ke Digital - Pengambilan Sampel Sinyal

Apa itu suara sebenarnya? Apakah itu semacam bahan mistik yang tidak dapat kita sentuh tetapi terbang ke telinga kita dan membuat kita mendengar sesuatu?

Tentu saja, ini tidak sepenuhnya terjadi. Kita tahu bahwa pada kenyataannya, suara adalah getaran yang merambat sebagai gelombang mekanis tekanan dan perpindahan, melalui media seperti udara atau air. Ketika getaran itu sampai ke telinga kita, terutama gendang telinga, ia menggerakkan tulang-tulang kecil yang meneruskan getaran itu lebih jauh ke sel-sel rambut kecil jauh di dalam telinga bagian dalam kita. Akhirnya, sel-sel rambut kecil menghasilkan impuls listrik, yang ditransmisikan ke otak kita melalui saraf pendengaran telinga.

Alat perekam meniru proses ini dengan cukup dekat, menggunakan tekanan gelombang suara untuk mengubahnya menjadi sinyal listrik. Gelombang suara aktual di udara adalah sinyal tekanan kontinu. Dalam mikrofon, komponen listrik pertama yang menemukan sinyal ini menerjemahkannya menjadi sinyal tegangan analog - sekali lagi, terus menerus. Sinyal kontinu ini tidak begitu berguna di dunia digital, sehingga sebelum dapat diproses harus diterjemahkan ke dalam sinyal diskrit yang dapat disimpan secara digital. Hal ini dilakukan dengan menangkap nilai digital yang mewakili amplitudo sinyal.

Konversi melibatkan kuantisasi input, dan itu tentu saja memperkenalkan sejumlah kecil kesalahan. Oleh karena itu, alih-alih konversi tunggal, konverter analog-ke-digital melakukan banyak konversi pada potongan sinyal yang sangat kecil - sebuah proses yang dikenal sebagai pengambilan sampel.

Teorema Nyquist-Shannon memberi tahu kita kecepatan pengambilan sampel apa yang diperlukan untuk menangkap frekuensi tertentu dalam sinyal kontinu. Secara khusus, untuk menangkap semua frekuensi yang dapat didengar manusia dalam sinyal audio, kita harus mengambil sampel sinyal pada frekuensi dua kali lipat dari jangkauan pendengaran manusia. Telinga manusia dapat mendeteksi frekuensi kira-kira antara 20 Hz dan 20.000 Hz. Akibatnya, audio paling sering direkam pada frekuensi sampling 44.100 Hz. Ini adalah kecepatan pengambilan sampel dari Compact Disc, dan juga kecepatan yang paling umum digunakan dengan audio MPEG-1 (VCD, SVCD, MP3). (Tingkat spesifik ini awalnya dipilih oleh Sony karena dapat direkam pada peralatan video yang dimodifikasi yang berjalan pada 25 frame per detik (PAL) atau 30 frame per detik (menggunakan perekam video monokrom NTSC) dan mencakup bandwidth 20.000 Hz yang dianggap perlu untuk cocok dengan peralatan perekam analog profesional saat itu.) Jadi, ketika memilih frekuensi sampel yang diperlukan untuk direkam, Anda mungkin ingin menggunakan 44.100 Hz.

Merekam - Menangkap Suara

Merekam sinyal audio sampel itu mudah. Karena kartu suara modern sudah dilengkapi dengan konverter analog-ke-digital, pilih saja bahasa pemrograman, temukan perpustakaan yang sesuai, atur frekuensi sampel, jumlah saluran (biasanya mono atau stereo), ukuran sampel (misalnya sampel 16-bit ). Kemudian buka saluran dari kartu suara Anda seperti aliran input apa pun, dan tulis ke array byte. Inilah cara yang bisa dilakukan di Jawa:

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

Baca saja data dari TargetDataLine . (Dalam contoh ini, bendera yang running adalah variabel global yang dihentikan oleh utas lain - misalnya, jika kita memiliki GUI dengan tombol 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); }

Domain-Waktu dan Domain-Frekuensi

Apa yang kita miliki dalam array byte ini adalah sinyal yang direkam dalam domain waktu. Sinyal domain waktu mewakili perubahan amplitudo sinyal dari waktu ke waktu.

Pada awal 1800-an, Jean-Baptiste Joseph Fourier membuat penemuan luar biasa bahwa setiap sinyal dalam domain waktu setara dengan jumlah beberapa (mungkin tak terbatas) jumlah sinyal sinusoidal sederhana, mengingat bahwa setiap komponen sinusoidal memiliki frekuensi, amplitudo, dan fase. Deret sinusoida yang bersama-sama membentuk sinyal domain waktu asli dikenal sebagai deret Fourier.

Dengan kata lain, dimungkinkan untuk merepresentasikan sinyal domain waktu dengan hanya memberikan himpunan frekuensi, amplitudo, dan fase yang sesuai dengan setiap sinusoid yang membentuk sinyal. Representasi sinyal ini dikenal sebagai domain frekuensi. Dalam beberapa hal, domain frekuensi bertindak sebagai jenis sidik jari atau tanda tangan untuk sinyal domain waktu, memberikan representasi statis dari sinyal dinamis.

Animasi berikut menunjukkan deret Fourier dari gelombang persegi 1 Hz, dan bagaimana gelombang persegi (perkiraan) dapat dihasilkan dari komponen sinusoidal. Sinyal ditampilkan dalam domain waktu di atas, dan domain frekuensi di bawah.

Menganalisis sinyal dalam domain frekuensi sangat menyederhanakan banyak hal. Lebih nyaman dalam dunia pemrosesan sinyal digital karena insinyur dapat mempelajari spektrum (representasi sinyal dalam domain frekuensi) dan menentukan frekuensi mana yang ada, dan mana yang hilang. Setelah itu, seseorang dapat melakukan penyaringan, menambah atau mengurangi beberapa frekuensi, atau hanya mengenali nada yang tepat dari frekuensi yang diberikan.

Transformasi Fourier Diskrit

Jadi kita perlu menemukan cara untuk mengubah sinyal kita dari domain waktu ke domain frekuensi. Di sini kami meminta bantuan Discrete Fourier Transform (DFT). DFT adalah metodologi matematika untuk melakukan analisis Fourier pada sinyal diskrit (sampel). Ini mengubah daftar terbatas sampel fungsi yang berjarak sama ke dalam daftar koefisien kombinasi terbatas sinusoidal kompleks, yang diurutkan berdasarkan frekuensinya, dengan mempertimbangkan apakah sinusoid tersebut telah diambil sampelnya pada laju yang sama.

Salah satu algoritma numerik yang paling populer untuk perhitungan DFT adalah transformasi Fast Fourier (FFT). Sejauh ini variasi FFT yang paling umum digunakan adalah algoritma Cooley-Tukey. Ini adalah algoritma bagi-dan-taklukkan yang secara rekursif membagi DFT menjadi banyak DFT yang lebih kecil. Sedangkan mengevaluasi DFT secara langsung memerlukan operasi O( n 2 ) , dengan FFT Cooley-Tukey hasil yang sama dihitung dalam operasi O ( n log n ) .

Tidak sulit untuk menemukan perpustakaan yang sesuai untuk FFT. Berikut adalah beberapa di antaranya:

• C – FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (Antarmuka ke FFTW)

Di bawah ini adalah contoh fungsi FFT yang ditulis dalam Java. (FFT mengambil bilangan kompleks sebagai masukan. Untuk memahami hubungan antara bilangan kompleks dan fungsi trigonometri, baca tentang rumus Euler.)

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

Dan berikut adalah contoh sinyal sebelum dan sesudah analisis FFT:

Pengenalan Musik: Sidik Jari Lagu

Salah satu efek samping yang tidak menguntungkan dari FFT adalah kita kehilangan banyak informasi tentang waktu. (Meskipun secara teoritis ini dapat dihindari, overhead kinerjanya sangat besar.) Untuk lagu tiga menit, kita melihat semua frekuensi dan besarannya, tetapi kita tidak tahu kapan dalam lagu itu muncul. Tapi ini adalah informasi kunci yang membuat lagu itu seperti apa adanya! Entah bagaimana kita perlu tahu pada titik waktu berapa setiap frekuensi muncul.

Itu sebabnya kami memperkenalkan jenis jendela geser, atau potongan data, dan hanya mengubah bagian informasi ini. Ukuran setiap potongan dapat ditentukan dengan beberapa cara berbeda. Misalnya, jika kita merekam suara, dalam stereo, dengan sampel 16-bit, pada 44.100 Hz, satu detik dari suara tersebut akan menjadi 44.100 sampel * 2 byte * 2 saluran 176 kB. Jika kita memilih 4 kB untuk ukuran sepotong, kita akan memiliki 44 potongan data untuk dianalisis di setiap detik lagu. Itu kepadatan yang cukup baik untuk analisis rinci yang diperlukan untuk identifikasi audio.

Sekarang kembali ke pemrograman:

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

Di loop dalam kita menempatkan data domain waktu (sampel) ke dalam bilangan kompleks dengan bagian imajiner 0. Di loop luar, kita mengulangi semua potongan dan melakukan analisis FFT pada masing-masing.

Setelah kami memiliki informasi tentang susunan frekuensi sinyal, kami dapat mulai membentuk sidik jari digital kami dari lagu tersebut. Ini adalah bagian terpenting dari keseluruhan proses pengenalan audio Shazam. Tantangan utama di sini adalah bagaimana membedakan, di lautan frekuensi yang ditangkap, frekuensi mana yang paling penting. Secara intuitif, kami mencari frekuensi dengan magnitudo tertinggi (biasa disebut puncak).

Namun, dalam satu lagu rentang frekuensi kuat dapat bervariasi antara C - C1 rendah (32,70 Hz) dan C - C8 tinggi (4.186,01 Hz). Ini adalah interval yang sangat besar untuk dicakup. Jadi, alih-alih menganalisis seluruh rentang frekuensi sekaligus, kita dapat memilih beberapa interval yang lebih kecil, dipilih berdasarkan frekuensi umum dari komponen musik penting, dan menganalisis masing-masing secara terpisah. Misalnya, kita mungkin menggunakan interval yang dipilih orang ini untuk implementasi algoritme Shazam. Ini adalah 30 Hz - 40 Hz, 40 Hz - 80 Hz dan 80 Hz - 120 Hz untuk nada rendah (mencakup gitar bass, misalnya), dan 120 Hz - 180 Hz dan 180 Hz - 300 Hz untuk nada menengah dan tinggi (meliputi vokal dan sebagian besar instrumen lainnya).

Sekarang dalam setiap interval, kita dapat dengan mudah mengidentifikasi frekuensi dengan magnitudo tertinggi. Informasi ini membentuk tanda tangan untuk bagian lagu ini, dan tanda tangan ini menjadi bagian dari sidik jari lagu secara keseluruhan.

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

Perhatikan bahwa kita harus berasumsi bahwa perekaman tidak dilakukan dalam kondisi sempurna (yaitu, "ruang tuli"), dan sebagai hasilnya kita harus menyertakan faktor kabur. Analisis faktor fuzzy harus dilakukan dengan serius, dan dalam sistem nyata, program harus memiliki opsi untuk mengatur parameter ini berdasarkan kondisi perekaman.

Untuk memudahkan pencarian audio, tanda tangan ini menjadi kunci dalam tabel hash. Nilai yang sesuai adalah waktu set frekuensi ini muncul di lagu, bersama dengan ID lagu (judul lagu dan artis). Berikut adalah contoh bagaimana catatan ini mungkin muncul di database.

Jika kita menjalankan seluruh perpustakaan lagu melalui proses identifikasi musik ini, kita dapat membangun database dengan sidik jari lengkap dari setiap lagu di perpustakaan.

Algoritma Musik: Identifikasi Lagu

Untuk mengidentifikasi lagu yang sedang diputar di klub, kami merekam lagu tersebut dengan ponsel kami, dan menjalankan perekaman melalui proses sidik jari audio yang sama seperti di atas. Kemudian kita dapat mulai mencari database untuk tag hash yang cocok.

Seperti yang terjadi, banyak tag hash akan sesuai dengan pengenal musik dari beberapa lagu. Misalnya, mungkin beberapa lagu A terdengar persis seperti beberapa lagu E. Tentu saja, ini tidak mengejutkan - musisi selalu "meminjam" lick dan riff satu sama lain, dan akhir-akhir ini produser mencoba semua lagu lain. waktu. Setiap kali kami mencocokkan tag hash, jumlah kemungkinan kecocokan semakin kecil, tetapi kemungkinan informasi ini saja tidak akan mempersempit kecocokan menjadi satu lagu. Jadi ada satu hal lagi yang perlu kita periksa dengan algoritma pengenalan musik kita, dan itu adalah waktunya.

Sampel yang kami rekam di klub mungkin berasal dari titik mana pun dalam lagu, jadi kami tidak bisa begitu saja mencocokkan stempel waktu hash yang cocok dengan stempel waktu sampel kami. Namun, dengan beberapa hash yang cocok, kami dapat menganalisis waktu relatif kecocokan, dan karenanya meningkatkan kepastian kami.

Misalnya, jika Anda melihat tabel di atas, Anda akan melihat bahwa tag hash 30 51 99 121 195 sesuai dengan Lagu A dan Lagu E. Jika, satu detik kemudian, kami mencocokkan hash 34 57 95 111 200 , itu satu lagi cocok untuk Lagu A tetapi dalam kasus ini kita tahu bahwa hash dan perbedaan waktu cocok.

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

Mari kita ambil i 1 dan i 2 sebagai momen dalam lagu yang direkam, dan j 1 dan j 2 sebagai momen dalam lagu dari database. Kita dapat mengatakan bahwa kita memiliki dua pertandingan dengan perbedaan waktu yang cocok jika:

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

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

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

Ini memberi kita fleksibilitas untuk merekam lagu dari awal, tengah, atau akhir.

Akhirnya, tidak mungkin bahwa setiap momen dari lagu yang kami rekam di klub akan cocok dengan setiap momen yang sesuai dari lagu yang sama di perpustakaan kami, yang direkam di studio. Rekaman akan menyertakan banyak noise yang akan menimbulkan beberapa kesalahan dalam pertandingan. Jadi, alih-alih mencoba menghilangkan semua kecuali lagu yang benar dari daftar kecocokan kami, di bagian paling akhir, kami mengurutkan semua lagu yang cocok dalam urutan kemungkinan yang menurun, dan favorit kami adalah lagu pertama di daftar peringkat.

Dari atas ke bawah

Untuk menjawab pertanyaan, “Bagaimana cara kerja Shazam?” berikut adalah ikhtisar dari seluruh proses pengenalan dan pencocokan musik, dari atas ke bawah:

Untuk sistem semacam ini, database bisa menjadi sangat besar, jadi penting untuk menggunakan semacam database yang dapat diskalakan. Tidak ada kebutuhan khusus untuk relasi, dan model data akhirnya cukup sederhana, jadi ini adalah kasus yang baik untuk menggunakan beberapa jenis database NoSQL.

Bagaimana Shazam Bekerja? Sekarang kamu tau

Perangkat lunak pengenalan lagu semacam ini dapat digunakan untuk menemukan kesamaan antar lagu. Sekarang setelah Anda memahami cara kerja Shazam, Anda dapat melihat bagaimana ini dapat memiliki aplikasi lebih dari sekadar Shazam lagu nostalgia yang diputar di radio taksi. Misalnya, dapat membantu untuk mengidentifikasi plagiarisme dalam musik, atau untuk mengetahui siapa yang menjadi inspirasi awal bagi beberapa pelopor musik blues, jazz, rock, pop, atau genre lainnya. Mungkin eksperimen yang baik adalah mengisi database sampel lagu dengan musik klasik Bach, Beethoven, Vivaldi, Wagner, Chopin dan Mozart dan mencoba menemukan kesamaan di antara lagu-lagu tersebut. Anda akan berpikir bahwa bahkan Bob Dylan, Elvis Presley dan Robert Johnson adalah plagiator!

Tapi tetap saja kita tidak bisa menghukum mereka, karena musik hanyalah gelombang yang kita dengar, hafal dan ulangi di kepala kita, di mana ia berkembang dan berubah sampai kita merekamnya di studio dan meneruskannya ke jenius musik hebat berikutnya.