Cara Kerja Shazam (2022)

 (cameronmacleod.com)
2 poin oleh GN⁺ 2023-12-06 | 1 komentar | Bagikan ke WhatsApp
  • Untuk menemukan lagu hanya dari rekaman mikrofon beberapa detik, Shazam tidak membandingkan seluruh audio, melainkan membuat sidik jari audio (fingerprint) dan mencarinya di database
  • Metode membandingkan gelombang dengan menggesernya secara langsung tidak realistis untuk skala 10 juta lagu, serta karena noise mikrofon, perubahan volume, dan efek frekuensi
  • Alur intinya adalah mengubah audio menjadi spectrogram, menemukan peak frekuensi yang kuat, lalu menyimpan pasangan peak sebagai hash agar bisa dibandingkan dengan cepat
  • Peak relatif tetap terlihat meski ada noise dan mengurangi jumlah data yang disimpan, tetapi harus tersebar merata dalam waktu dan frekuensi agar lagu bisa dikenali dari bagian mana pun
  • Pada tahap pengenalan, selisih Track time - Sample time dari hash yang cocok dikelompokkan menjadi histogram, lalu lagu dengan konsentrasi terbesar pada satu bin dipilih sebagai jawaban

Masalah yang Harus Dipecahkan Shazam

  • Shazam adalah aplikasi yang merekam lagu yang sedang diputar di sekitar selama beberapa detik, lalu mencarinya di database dan menampilkan hasilnya
  • Sebelum menjadi aplikasi, Shazam adalah layanan berbasis nomor telepon
    • Pengguna harus menelepon sebuah nomor dan mengarahkan mikrofon ponsel ke musik
    • Setelah 30 detik, Shazam menutup panggilan dan mengirimkan informasi lagu yang sedang didengar lewat SMS
    • Pada 2002, kualitas panggilan ponsel saat itu membuat pengenalan lagu menjadi lebih sulit
  • Untuk contoh kecil, potongan audio bisa digeser sedikit demi sedikit di atas seluruh track untuk memeriksa apakah ada kecocokan
    • Namun jika harus mencari di database 10 juta lagu tanpa mengetahui lagunya, waktu yang dibutuhkan akan meningkat drastis
  • Sampel mikrofon nyata dapat memiliki bentuk gelombang yang berbeda karena noise latar, efek frekuensi, dan perubahan volume, sehingga perbandingan sliding sederhana tidak cocok dengan baik

Alur Sistem Keseluruhan

  • Pendekatan Shazam dibagi menjadi alur register dan recognise
    • register adalah alur untuk menyimpan lagu agar dapat ditemukan nanti
    • recognise adalah alur untuk mencari lagu dari potongan audio singkat
  • Kedua alur melewati tahap prapemrosesan yang sama
    • Menghitung spectrogram audio
    • Menemukan peak, yaitu komponen frekuensi terkuat pada spectrogram
    • Mengelompokkan peak menjadi pasangan untuk membuat hash
  • Alur register menyimpan hash yang dihitung ke database
  • Alur recognise membandingkan hash yang dibuat dari audio baru dengan hash di database, lalu mengidentifikasi lagu pada tahap matching

Perhitungan Spectrogram

  • Fourier transform memberi tahu frekuensi apa saja yang ada di dalam audio
    • Jika Fourier transform diterapkan pada sine wave 20Hz, spike besar akan muncul di sekitar 20Hz
    • Karena sine wave hanya berisi satu frekuensi, ini juga disebut pure tone
  • Hasil Fourier transform adalah frequency spectrum
    • Representasi yang berpusat pada sumbu waktu disebut time domain
    • Representasi yang berpusat pada sumbu frekuensi disebut frequency domain
    • Sumbu Y pada frequency spectrum menunjukkan kekuatan setiap komponen frekuensi; semakin kuat komponennya, semakin jelas terdengar dalam sinyal time-domain
  • Jika beberapa sine wave dijumlahkan, komponen frekuensi dari tiap wave akan tergabung
    • Jika sine wave 50Hz dengan setengah intensitas ditambahkan ke sine wave 20Hz, akan muncul spike 20Hz dan spike 50Hz yang lebih kecil
    • Semua sinyal audio dapat direkonstruksi dari wave-wave seperti ini
  • Frequency domain mengungkap informasi yang tidak terlihat jelas di time domain
    • Meski noise ditambahkan dan bentuk time-domain berubah, spike frekuensi utama masih bisa tampak jelas di frequency domain
  • Jika Fourier transform diterapkan sekali saja pada seluruh lagu, yang terlihat hanya kekuatan frekuensi keseluruhan, padahal frekuensi pada lagu nyata berubah seiring waktu
    • Jika lagu dibagi menjadi potongan-potongan kecil, Fourier transform diterapkan pada setiap potongan, lalu hasilnya digabungkan, hasilnya menjadi spectrogram
    • Spectrogram merepresentasikan waktu, frekuensi, dan kekuatan sekaligus; kekuatan dapat ditampilkan dengan warna
  • Pada spectrogram contoh “Like a Stone”, titik paling terang, yaitu sebagian besar frekuensi yang kuat, muncul di bawah 5000Hz
    • Distribusi seperti ini umum pada musik, dan sebagian besar rentang frekuensi piano berada di 27Hz-4186Hz

Fingerprint Berbasis Peak

  • Fingerprint audio dimulai dari menemukan peak pada spectrogram
    • Peak adalah komponen frekuensi terbesar pada titik waktu tertentu
    • Dalam musik, nada terkuat pada saat tertentu, seperti nada kuat dalam solo gitar, dapat menjadi peak
  • Peak relatif lebih tahan terhadap pengaruh noise
    • Agar peak tidak lagi dapat dikenali, noise harus lebih besar daripada peak tersebut
    • Peak spectrogram adalah komponen frekuensi terkuat pada track
  • Jika hanya peak yang disimpan, jumlah data yang dibutuhkan untuk fingerprint berkurang
    • Tidak semua informasi frekuensi disimpan; hanya komponen frekuensi terbesar yang dipertahankan
    • Data yang perlu dicari menjadi lebih sedikit, sehingga pencarian fingerprint lebih cepat
  • Peak harus tersebar merata baik dalam waktu maupun frekuensi
    • Jika hanya terkonsentrasi di satu bagian waktu, sampel dari bagian lain lagu tidak dapat dikenali
    • Jika terkonsentrasi pada pita frekuensi yang sempit, noise keras pada pita tertentu seperti klakson mobil dapat mengubah pemilihan peak dan membuat bagian tersebut sulit dikenali

Menemukan Peak dengan Maximum Filter

  • Untuk menemukan peak secara merata, teknik maximum filter dari pemrosesan gambar dapat digunakan
  • Maximum filter mencari nilai maksimum di area tetangga di sekitar setiap pixel, lalu mengganti pixel tersebut dengan nilai local maximum itu
    • Contohnya memeriksa area 3x3 di sekitar setiap pixel
    • Pemrosesan ini memiliki efek memperluas local peak ke area sekitarnya
  • Spectrogram yang telah melalui maximum filter terlihat seperti versi beresolusi rendah dari spectrogram asli
    • Ini karena peak sinyal diperluas dan menempati pixel lain
    • Box dengan warna yang sama berkorespondensi dengan satu local peak pada gambar asli
  • Maximum filter memiliki parameter ukuran box untuk menemukan local maximum
    • Menggunakan box kecil menghasilkan lebih banyak peak
    • Menggunakan box besar menghasilkan lebih sedikit peak
  • Posisi peak dipulihkan dengan mencari titik yang nilainya sama pada spectrogram asli dan spectrogram hasil filtering
    • Titik yang bukan peak berubah menjadi nilai local peak sehingga nilainya berbeda
    • Hanya titik yang nilainya tetap sama yang merupakan peak
  • Jika semua peak dikumpulkan dan digambar, hasilnya menjadi constellation map
    • Nama ini diberikan karena tampilannya seperti gambar langit malam
  • Jumlah peak secara langsung memengaruhi ukuran fingerprint
    • Jika harus menyimpan jutaan lagu, menjaga fingerprint tetap kecil itu penting
    • Mengurangi peak juga menurunkan akurasi dan mengurangi peluang sampel cocok dengan lagu yang benar
  • Ada dua cara untuk mengurangi peak
    • Menggunakan N peak teratas, dengan N harus proporsional terhadap panjang audio agar lagu pendek tidak terambil sampelnya secara berlebihan
    • Menggunakan semua peak yang lebih besar dari threshold tertentu; ini tidak menjamin ukuran fingerprint per satuan waktu, tetapi bisa lebih akurat

Membuat Hash dari Pasangan Peak

  • Jika fingerprint berupa kumpulan peak spectrogram tunggal, duplikasi akan meningkat dengan cepat
    • Jika frekuensi setiap peak direpresentasikan dengan 10bit, 2^10=1024 frekuensi individual dapat direpresentasikan
    • Jika ada ribuan titik per track, pengulangan akan banyak terjadi
  • Keunikan penting untuk fingerprint
    • Semakin tinggi keunikannya, semakin cepat pencariannya
    • Ini membantu mengenali lebih banyak lagu
  • Pendekatan Shazam membuat hash dari pasangan peak, bukan peak tunggal
    • Hash berisi frekuensi dua peak, fA dan fB, serta selisih waktu di antara keduanya, ΔT
    • Jika setiap peak memiliki informasi frekuensi 10bit dan ΔT juga direpresentasikan dengan 10bit, total informasinya menjadi 30bit
    • 2^30=1.073.741.824 kemungkinan jauh lebih besar daripada 1024 kemungkinan dari satu point
  • Pembuatan pair menggunakan anchor point dan target zone
    • Satu point dipilih sebagai anchor point
    • Spectrogram target zone terhadap anchor point dihitung
    • Semua point di dalam target zone dipasangkan dengan anchor point
  • Paper Shazam tidak menjelaskan secara rinci cara memilih target zone
    • Pada gambar di paper, target zone dimulai sedikit setelah waktu anchor point dan ditempatkan di sekitar frekuensi anchor point
  • Pair yang dibuat disimpan di database sebagai hash
    • Komponen hash adalah fA, fB, ΔT
    • Sebagai informasi tambahan, Point A time dan Track ID disimpan
    • Point A time dan Track ID nantinya digunakan pada matching untuk menemukan titik waktu tertentu pada lagu tertentu
  • Kumpulan semua hash dari track tertentu menjadi fingerprint track tersebut

Cara Matching

  • Alur recognise membuat fingerprint dari sample, lalu membandingkannya dengan fingerprint yang sudah tersimpan di database
  • Algoritme matching berjalan dalam empat langkah
    • Mengambil semua hash dari database yang cocok dengan sample fingerprint
    • Mengelompokkan hash berdasarkan lagu
    • Untuk setiap lagu, memeriksa apakah hash-hash tersebut selaras secara waktu
    • Memilih track dengan hash selaras terbanyak
  • abracadabra tidak mencari 3-tuple (fA, fB, ΔT) secara langsung, melainkan menyimpannya sebagai satu nilai yang dikembalikan oleh hash(fA, fB, ΔT)
    • Alih-alih mencari tiga nilai untuk setiap hash, satu nilai saja dapat dicari
  • Setiap hash di database terhubung dengan Track ID, sehingga grouping berdasarkan lagu dapat dilakukan
    • Setelah grouping seperti ini, setiap kandidat track dapat diberi skor
  • Jika sample cocok dengan suatu lagu, hash di dalam sample harus terselaraskan dengan baik ke satu bagian dari lagu asli
    • Noise dapat membuat peak yang terlihat seperti peak dari waktu lain di dalam sample
    • Hash juga bisa cocok dengan lagu yang salah
  • Keselarasan diperiksa dengan menghitung nilai Track time - Sample time untuk setiap hash yang match
    • Hash match yang benar berbagi nilai selisih yang sama
    • Pada contoh, baris dengan nilai selisih 10 adalah true match, sedangkan nilai selisih lain adalah false match
  • Nilai selisih dibuat menjadi histogram, dan bin terbesar digunakan sebagai score lagu
    • Lagu yang bukan match bagus memiliki nilai rendah di semua bin
    • Lagu yang match dengan baik memiliki spike besar pada satu bin
  • Alasan tidak sekadar memilih lagu dengan jumlah hash match terbanyak adalah bias panjang lagu
    • Lagu panjang cenderung memiliki jumlah match lebih banyak daripada lagu pendek
    • Di Spotify ada track berdurasi lebih dari 4 jam, sehingga hasil bisa sangat bias

abracadabra dan Referensi

Bacaan terkait

1 komentar

 
GN⁺ 2023-12-06
Opini Hacker News

  • Wall Street Journal punya video yang dibuat dengan baik yang menjelaskan Shazam
    https://www.wsj.com/video/series/in-depth-features/how-shaza...
    Chris, salah satu pendiri Shazam

    • Saya penasaran apakah alasan Shazam berkantor di Rancho Bernardo, San Diego adalah karena ia memang berasal dari San Diego sebelum pindah ke Inggris
      Lawn Love menyewa suite di lantai atasnya pada 2014–2018, tetapi para pengembang aplikasi mobile Shazam di kantor itu tetap diam-diam saja setelah akuisisi, dan kami bahkan tidak pernah mendengar suara sampanye perayaan

  • Ketika Shazam muncul pada 2008, pendekatan berbasis hash adalah pilihan yang cerdik
    Kalau saya, saya akan mulai dengan membuat cara untuk mengubah semua lagu menjadi hash seefisien mungkin secara komputasi
    Kalau diluncurkan hari ini, arah R&D utamanya mungkin pelatihan model, yang bisa jadi jauh kurang efisien dan lebih mahal untuk di-hosting
    Ini memang terasa seperti masalah yang cocok ditangani model, tetapi karena jumlah lagunya terbatas, metode hash kemungkinan besar jauh lebih unggul kinerjanya

    • Tepatnya, bukan mengubah setiap lagu menjadi satu hash, melainkan mengubah setiap lagu menjadi ratusan hingga ribuan hash
      Strukturnya mencari seberapa banyak hash dari sampel pendek—puluhan, atau paling banyak ratusan rendah—yang cocok, umumnya secara berurutan
      Bahkan sekarang pun rasanya tidak akan dilakukan dengan pelatihan model, karena setiap hari ada sangat banyak lagu baru yang ditambahkan sehingga harus terus dilatih ulang
      Hash masih tampak sebagai pendekatan yang lebih baik bukan hanya dari sisi efisiensi, tetapi juga dari sisi ketangguhan secara keseluruhan
    • Pendekatan cerdik pada 1975 adalah Parsons code, dan ini juga mirip dengan hashing lagu yang bisa dihitung di kepala
      Setelah itu, lagu bisa dicari seperti mencari kata di kamus, dan saya berharap ide ini tidak mudah hilang
      [1]: https://en.wikipedia.org/wiki/Parsons_code
    • Koreksi kecil, Shazam diluncurkan bukan pada 2008, melainkan sebagai layanan sambungan telepon pada 2002, dan hasilnya dikirim lewat SMS
      Aplikasi ponsel pertamanya adalah untuk BREW pada 2006
      2008 hanyalah saat Apple meluncurkan App Store; sebelum itu pihak ketiga tidak bisa membuat aplikasi iPhone
    • Jujur saja, untuk alat seperti Shazam, tidak ada perbedaan mendasar yang besar antara database+algoritma hashing dan model self-supervised
      Keduanya adalah solusi pengindeksan dan kompresi yang hebat, hanya saja skala datanya berbeda
    • Kalau ini dilatih sebagai model, saya penasaran bagaimana menghindari menjalankan ulang seluruh proses pelatihan setiap kali menambahkan lagu baru
      Mungkin ada cara membuat model embedding yang bisa menghitung vektor embedding untuk tiap lagu baru tanpa pelatihan ulang penuh

  • Shazam adalah produk langka yang selama 20 tahun tidak kehilangan rasa ajaibnya
    Benar-benar dekat dengan apa yang seharusnya dituju para teknisi

    • Bagi orang yang paham teknis, ekstraksi fingerprint musik adalah masalah konkret yang bisa dipahami, tetapi kalau masuk ke detail tanpa melihat solusi yang sudah ada, masalahnya cukup sulit
      Tidak seperti fitur yang sekilas mirip, seperti pengenalan gambar hewan atau objek, tetapi kebanyakan lebih menyerupai sihir machine learning yang aneh, ini masuk ke ranah masalah yang jarang tetapi bisa dipahami
    • Pada saat yang sama, aplikasi yang dulu “ketuk, dengarkan, langsung dapat hasil” telah berubah menjadi aplikasi bengkak yang lambat dan penuh iklan
      Saya ingat akhirnya menghapus aplikasinya karena di iPhone generasi sebelumnya pun tidak bisa dimuat tepat waktu
    • Google membawanya selangkah lebih jauh
      Fitur Now Playing terus mendeteksi lagu dan mencatatnya dalam riwayat, dan di Google Assistant Anda bisa mencari lagu hanya dengan bersenandung
      Tidak selalu bekerja stabil, tetapi kadang tepat sekali
    • Malah menjadi lebih ajaib
      Saya pernah mencoba mencari lagu yang dinyanyikan seseorang di America’s Got Talent, dan terkejut karena hasilnya kembali ke penyanyi yang tampil di AGT itu
      Saya jadi bertanya-tanya apakah mereka juga mengindeks acara TV
    • Para teknisi memang menargetkan produk seperti itu
      Tetapi manajer produk, kalau tidak terus merusak produk demi bonus dan cuti, lalu harus melakukan apa?

  • Ada juga Chromaprint, yang bekerja dengan cara agak berbeda
    Ia berbasis pola perubahan nada, bukan nilai maksimum pada spektrum
    Chromaprint digunakan di AcoustID, database publik besar yang menghubungkan fingerprint audio dengan rekaman MusicBrainz
    Menakjubkan bahwa di dalamnya ada begitu banyak musik, meski dukungan komersialnya tidak sebanyak Shazam
    [1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/

    • Sepertinya Chromaprint harus membandingkan keseluruhan lagu
      Bagus untuk deteksi duplikat, tetapi desain fingerprint Shazam memungkinkan potongan pendek dicocokkan dengan keseluruhan lagu

  • Tulisan bagus yang menangkap dengan baik apa yang dilakukan spektrogram, dan nyaris wajib dibaca bagi siapa pun yang ingin memahami bagaimana ekstraksi fingerprint audio bekerja
    Ada algoritma aproksimasi serupa di media lain juga, jadi untuk memahami hashing di dunia nyata, tulisan ini layak dipelajari dengan saksama

    • Teknik spektrogram umum sudah ditemukan Phillips sebelum Shazam
      Yang dilakukan Shazam adalah melakukan hashing secara kombinatorial untuk mengurangi false positive

  • Ada sebuah situs bagus yang menangani bukan lagu, melainkan klasifikasi genre dan percabangan subgenre yang dihasilkan oleh signature lagu baru melalui pencocokan algoritmik
    Ini materi luar biasa yang dijalankan sebagai proyek sampingan pribadi, tetapi tampaknya berisiko hilang karena masalah seperti hosting
    Dulu ada fitur serupa seperti Music DNA dari Pandora atau LastFM, tetapi situs ini terasa seperti jaringan visual yang menghubungkan seluruh musik yang dibuat manusia hingga 2023, jadi jika hilang, itu akan menjadi kerugian bagi seluruh web
    Every Noise At Once
    https://everynoise.com

  • Mengejutkan betapa intuitifnya cara ini, dan betapa cocoknya dengan proses persepsi kita sendiri
    Secara garis besar, caranya adalah mengidentifikasi potongan melodi, lalu mencocokkannya sesuai urutan
    Mirip seperti kita bisa mengenali sesuatu hanya dengan mendengar 5, 7, atau 10 nada
    Saya rasa saya juga pernah membaca metode fingerprinting lagu lain yang bergantung pada hal-hal seperti puncak volume; metode seperti itu mungkin bisa bekerja sama baiknya, tetapi sama sekali tidak sesuai dengan cara kerja otak kita
    Cara ini cukup keren karena pada dasarnya bekerja mirip dengan cara kita melakukannya, bukan bergantung pada “produk sampingan artifisial”
    Secara teknis tidak selalu melodi, tetapi sebagian besar kemungkinan besar memang melodi

  • Saya penasaran bagaimana Shazam menangani kasus ketika sumbu waktunya tidak linear atau tidak konstan
    Misalnya pada pita kaset, wow and flutter, atau situasi ketika tempo terus menjadi lebih cepat lalu lebih lambat
    Sepengetahuan saya, fingerprinting sangat sensitif terhadap waktu, dan memotongnya menjadi potongan sekitar 50 ms pun tidak sepenuhnya menyelesaikan masalah
    Terakhir kali saya melihatnya, teknik umum untuk masalah semacam ini, yaitu Dynamic Time Warping, terlalu mahal secara komputasi

  • Ini tulisan-tulisan terkait. Saya penasaran kalau ada lagi
    How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - Oktober 2022, 1 komentar
    Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - Agustus 2022, 36 komentar
    Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - Agustus 2022, 227 komentar
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - Juli 2020, 7 komentar
    Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - Januari 2019, 186 komentar
    Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - November 2018, 2 komentar
    Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - November 2017, 76 komentar
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - September 2017, 13 komentar
    Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - April 2016, 2 komentar
    How Shazam works - https://news.ycombinator.com/item?id=9870408 - Juli 2015, 48 komentar
    Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - Mei 2015, 18 komentar
    The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - Mei 2015, 37 komentar
    The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - November 2014, 34 komentar
    Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - Oktober 2014, 3 komentar
    Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - Mei 2013, 16 komentar
    Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - Mei 2013, 43 komentar
    An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - Juni 2011, 4 komentar
    Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - Februari 2011, 1 komentar
    How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - Februari 2011, 2 komentar
    Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - September 2010, 23 komentar
    Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - Oktober 2009, 28 komentar

Bagaimana aplikasi pengidentifikasi musik Shazam bekerja dengan ajaib? - https://news.ycombinator.com/item?id=893353 - Oktober 2009, 16 komentar

  • Ini tampak seperti pendekatan arah berlawanan dari rekayasa serupa yang mencoba menciptakan lagu hit berbasis genre dalam industri musik pop