2 puan yazan GN⁺ 2023-12-06 | 1 yorum | WhatsApp'ta paylaş
  • Shazam, birkaç saniyelik mikrofon kaydıyla bir şarkıyı bulmak için sesin tamamını karşılaştırmak yerine veritabanında aranabilecek bir ses parmak izi (fingerprint) oluşturur
  • Dalga biçimini olduğu gibi kaydırarak karşılaştırma yöntemi, 10 milyon şarkı ölçeği ile mikrofon gürültüsü, ses seviyesi değişimleri ve frekans etkileri nedeniyle pratikte uygun değildir
  • Temel akış, sesi spectrogram'a dönüştürmek, güçlü frekans peak'lerini bulmak ve ardından peak çiftlerini hash olarak saklayıp hızlıca karşılaştırmaktır
  • Peak'ler gürültüye rağmen görece iyi korunur ve depolama miktarını azaltır; ancak şarkının her bölümünde tanıma yapılabilmesi için zaman ve frekans boyunca dengeli dağılmış olmaları gerekir
  • Tanıma aşamasında eşleşen hash'lerin Parça zamanı - Örnek zamanı farkı histogramda gruplanır ve tek bir bin'de en çok yoğunlaşan şarkı doğru sonuç olarak seçilir

Shazam'ın çözmesi gereken problem

  • Shazam, çevrede çalan bir şarkıyı birkaç saniye kaydedip veritabanında arayarak sonucu gösteren bir uygulamadır
  • Uygulama olmadan önce Shazam, telefon numarası tabanlı bir hizmetti
    • Kullanıcılar bir numarayı arar ve cep telefonu mikrofonunu müziğe doğru tutardı
    • 30 saniye sonra Shazam aramayı sonlandırır ve dinlenen şarkının bilgisini SMS ile gönderirdi
    • 2002'de cep telefonu görüşme kalitesi, şarkı tanımayı daha da zorlaştırıyordu
  • Küçük bir örnekte, ses parçası tüm parça üzerinde adım adım kaydırılarak eşleşme olup olmadığı kontrol edilebilir
    • Ancak hangi şarkı olduğu bilinmeyen durumda 10 milyon şarkılık bir veritabanında arama yapmak süreyi ciddi biçimde artırır
  • Gerçek mikrofon örneklerinde arka plan gürültüsü, frekans etkileri ve ses seviyesi değişimleri nedeniyle dalga biçimi değişebilir; bu yüzden basit sliding karşılaştırma iyi sonuç vermez

Tüm sistemin akışı

  • Shazam yaklaşımı register ve recognise akışlarına ayrılır
    • register, şarkıyı daha sonra bulunabilecek şekilde kaydetme akışıdır
    • recognise, kısa bir ses bölümünün hangi şarkıya ait olduğunu bulma akışıdır
  • Her iki akış da aynı ön işleme adımlarından geçer
    • Sesin spectrogram'ını hesaplama
    • spectrogram içindeki en güçlü frekans bileşenleri olan peak'leri bulma
    • peak'leri çiftler halinde birleştirerek hash oluşturma
  • register akışı, hesaplanan hash'leri veritabanına kaydeder
  • recognise akışı, yeni sesten üretilen hash'leri veritabanındaki hash'lerle karşılaştırır ve matching aşamasında şarkıyı belirler

Spectrogram hesaplama

  • Fourier transform, bir sesin hangi frekansları içerdiğini gösterir
    • 20Hz'lik bir sine wave'e Fourier transform uygulandığında 20Hz civarında büyük bir spike görülür
    • sine wave yalnızca tek bir frekans içerdiği için pure tone olarak da adlandırılır
  • Fourier transform sonucuna frequency spectrum denir
    • Zaman ekseni merkezli gösterim time domain'dir
    • Frekans ekseni merkezli gösterim frequency domain'dir
    • frequency spectrum'un Y ekseni, her frekans bileşeninin gücünü gösterir; güçlü bileşenler time-domain sinyalde daha belirgin duyulur
  • Birden fazla sine wave toplandığında, her wave'in frekans bileşenleri birleşir
    • 20Hz'lik bir sine wave'e yarı güçte 50Hz'lik bir sine wave eklenirse 20Hz spike'ı ve daha küçük bir 50Hz spike'ı görülür
    • Tüm ses sinyalleri bu tür wave'lerle yeniden oluşturulabilir
  • frequency domain, time domain'de kolay görünmeyen bilgileri ortaya çıkarır
    • Gürültü eklendiğinde time-domain şekli değişse bile, frequency domain'de ana frekans spike'ları hâlâ belirgin olabilir
  • Tüm şarkıya yalnızca bir kez Fourier transform uygulanırsa sadece genel frekans güçleri görülür; oysa gerçek bir şarkıda frekanslar zamanla değişir
    • Şarkıyı küçük bölümlere ayırıp her bölüme Fourier transform uyguladıktan sonra bunları birleştirmek spectrogram oluşturur
    • spectrogram; zamanı, frekansı ve gücü birlikte gösterir, güç ise renklerle ifade edilebilir
  • Örnek olarak verilen “Like a Stone” spectrogram'ında en parlak noktalar, yani güçlü frekansların çoğu 5000Hz altında görünür
    • Müzikte bu tür dağılım yaygındır; piyanonun frekans aralığının büyük kısmı 27Hz-4186Hz arasındadır

Peak tabanlı fingerprint

  • Ses parmak izi, spectrogram içinde peak bulmakla başlar
    • peak, belirli bir andaki en büyük frekans bileşenidir
    • Müzikte örneğin bir gitar solosundaki güçlü nota, o andaki peak olabilir
  • Peak'ler gürültüden görece daha az etkilenir
    • Bir peak'i tanınamaz hale getirmek için gürültünün o peak'ten daha büyük olması gerekir
    • spectrogram peak'i, parçadaki en güçlü frekans bileşenidir
  • Yalnızca peak'leri saklamak, fingerprint için gereken veri miktarını azaltır
    • Tüm frekans bilgisini saklamak yerine yalnızca en güçlü frekans bileşenleri bırakılır
    • Aranacak veri azaldığı için fingerprint araması hızlanır
  • Peak'ler hem zaman hem frekans boyunca dengeli dağılmalıdır
    • Zamansal olarak tek bir tarafa yığılırsa şarkının diğer bölümlerinden alınan örnekler tanınamaz
    • Frekans bantları dar bir alanda yığılırsa araba kornası gibi belirli banttaki yüksek bir gürültü, peak seçimini değiştirerek o bölümü tanımayı zorlaştırabilir

Maximum filter ile peak bulma

  • Peak'leri dengeli bulmak için görüntü işlemedeki maximum filter tekniği kullanılabilir
  • maximum filter, her pixel'in çevresindeki komşu bölgede en büyük değeri bulur ve ilgili pixel'i o local maximum değere dönüştürür
    • Örnekte her pixel etrafındaki 3x3 alan incelenir
    • Bu işlem, local peak'leri çevredeki alana yayma etkisi yaratır
  • maximum-filtered spectrogram, orijinal spectrogram'ın düşük çözünürlüklü bir sürümü gibi görünür
    • Bunun nedeni sinyaldeki peak'lerin genişleyerek başka pixel'leri kaplamasıdır
    • Aynı renkteki kutular, orijinal görüntüdeki tek bir local peak'e karşılık gelir
  • maximum filter içinde local maximum aramak için bir kutu boyutu parametresi vardır
    • Küçük kutu kullanılırsa daha fazla peak çıkar
    • Büyük kutu kullanılırsa daha az peak çıkar
  • Peak konumları, orijinal spectrogram ile filtrelenmiş spectrogram'da değeri aynı kalan noktalar bulunarak geri elde edilir
    • Peak olmayan noktalar local peak değerine dönüştüğü için değerleri değişir
    • Değeri aynı kalan noktalar peak'tir
  • Tüm peak'ler birlikte çizildiğinde buna constellation map denir
    • Gece gökyüzü görüntüsüne benzediği için bu ad kullanılır
  • Peak sayısı, fingerprint boyutunu doğrudan etkiler
    • Milyonlarca şarkı saklanacaksa fingerprint'i küçük tutmak önemlidir
    • Peak sayısını azaltmak doğruluğu da düşürür ve örneğin doğru şarkıyla matching yapma olasılığını azaltır
  • Peak sayısını azaltmanın iki yolu vardır
    • En üstteki N peak kullanılır; burada N, kısa şarkıların aşırı örneklenmemesi için ses uzunluğuyla orantılı olmalıdır
    • Belirli bir threshold'un üzerindeki tüm peak'ler kullanılır; bu yöntem saat başına fingerprint boyutunu garanti etmez ama daha doğru olabilir

Peak çiftlerinden hash oluşturma

  • Eğer fingerprint yalnızca tekil spectrogram peak'lerinin kümesiyse tekrarlar hızla artar
    • Her peak'in frekansı 10bit ile ifade edilirse 2^10=1024 farklı tekil frekans temsil edilebilir
    • Parça başına binlerce nokta olduğunda tekrar çok artar
  • fingerprint için benzersizlik önemlidir
    • Benzersizlik arttıkça arama hızlanır
    • Daha fazla şarkının tanınmasına yardımcı olur
  • Shazam yaklaşımı, tekil peak yerine peak çiftlerinden hash üretir
    • hash içinde iki peak'in frekansları fA, fB ve iki peak arasındaki zaman farkı ΔT yer alır
    • Her peak 10bit frekans bilgisi taşıyor ve ΔT de 10bit ile ifade ediliyorsa toplam 30bit bilgi elde edilir
    • 2^30=1,073,741,824 olasılık, tek bir noktanın 1024 olasılığına kıyasla çok daha büyüktür
  • Çift üretiminde anchor point ve target zone kullanılır
    • Bir nokta anchor point olarak seçilir
    • Bu anchor point için spectrogram target zone hesaplanır
    • target zone içindeki tüm noktalar, anchor point ile eşleştirilerek çift oluşturur
  • Shazam makalesi, target zone seçiminin nasıl yapıldığını ayrıntılı açıklamaz
    • Makaledeki görselde target zone, anchor point'in biraz sonrasındaki zamandan başlar ve anchor point'in frekansı etrafında konumlanır
  • Oluşturulan çiftler veritabanında hash olarak saklanır
    • hash'i oluşturan öğeler fA, fB ve ΔT'dir
    • Ek bilgi olarak Point A zamanı ve Track ID saklanır
    • Point A zamanı ve Track ID, daha sonra matching aşamasında belirli bir şarkının belirli anını bulmak için kullanılır
  • Belirli bir parçaya ait tüm hash'lerin toplamı, o parçanın fingerprint'ini oluşturur

Matching yöntemi

  • recognise akışı, örnekten bir fingerprint oluşturur ve bunu veritabanında kayıtlı fingerprint'lerle karşılaştırır
  • matching algoritması dört adımda ilerler
    • Örnek fingerprint ile eşleşen tüm hash'ler veritabanından alınır
    • hash'ler şarkıya göre gruplanır
    • Her şarkı için hash'lerin zaman içinde hizalanıp hizalanmadığı kontrol edilir
    • Hizalanmış hash sayısı en fazla olan parça seçilir
  • abracadabra, 3-tuple olan (fA, fB, ΔT) değerini doğrudan aramak yerine hash(fA, fB, ΔT) fonksiyonunun döndürdüğü tek bir değer olarak saklar
    • Böylece her hash için üç değeri aramak yerine tek bir değer aranır
  • Veritabanındaki her hash bir Track ID ile bağlantılıdır; bu sayede şarkıya göre gruplama yapılabilir
    • Bu gruplamanın ardından her aday parçaya puan verilebilir
  • Eğer örnek belirli bir şarkıyla eşleşiyorsa, örnekteki hash'ler orijinal parçanın belirli bir bölgesinde iyi şekilde hizalanmalıdır
    • Gürültü, örnekte farklı zamanlardan gelen peak'ler gibi görünen peak'ler oluşturabilir
    • hash'lerin yanlış şarkılarla eşleştiği durumlar da olabilir
  • Hizalanma durumu, her eşleşen hash için Parça zamanı - Örnek zamanı değeri hesaplanarak kontrol edilir
    • Gerçek eşleşen hash'ler aynı fark değerini paylaşır
    • Örnekte fark değeri 10 olan satırlar true match, diğer fark değerleri ise false match'tir
  • Fark değerlerinden histogram oluşturulur ve en büyük bin, şarkının score'u olarak kullanılır
    • İyi eşleşmeyen şarkılarda tüm bin değerleri düşüktür
    • İyi eşleşen bir şarkıda tek bir bin içinde büyük bir spike oluşur
  • En çok eşleşen hash'e sahip şarkının doğrudan seçilmemesinin nedeni şarkı uzunluğu yanlılığıdır
    • Uzun şarkıların kısa şarkılara göre daha fazla eşleşme üretme olasılığı vardır
    • Spotify'da 4 saatten uzun parçalar bile bulunduğu için sonuçlar ciddi biçimde kayabilir

abracadabra ve kaynaklar

1 yorum

 
GN⁺ 2023-12-06
Hacker News yorumları
  • Wall Street Journal’ın Shazam’ı anlatan iyi hazırlanmış bir videosu var
    https://www.wsj.com/video/series/in-depth-features/how-shaza...
    Shazam’ın kurucu ortağı Chris

    • Shazam’ın San Diego’daki Rancho Bernardo’da ofis açmasının nedeninin, İngiltere’ye gitmeden önce aslında San Diego’lu olması olup olmadığını merak ediyorum
      Lawn Love 2014–2018 arasında üst kattaki süiti kiralamıştı; o ofisteki Shazam mobil uygulama geliştiricileri satın alma sonrasında da sessiz sakin kaldılar, kutlama şampanyası sesi bile duymadık
  • Shazam 2008’de çıktığında hash tabanlı yaklaşım akıllıca bir seçimdi
    Ben olsam önce tüm parçaları mümkün olduğunca hesaplama açısından verimli şekilde hash’e dönüştürmenin bir yolunu geliştirirdim
    Bugün piyasaya çıksaydı temel Ar-Ge yönü muhtemelen model eğitimi olurdu; bu da çok daha az verimli ve barındırma maliyeti daha yüksek olabilirdi
    Modelin iyi iş çıkaracakmış gibi hissettirdiği bir problem olsa da, parça sayısının sonlu olması bakımından hash yönteminin çok daha iyi performans göstermesi muhtemel

    • Daha doğrusu her parçayı tek bir hash’e çevirmek değil, her parçayı yüzlerce–binlerce hash’e çevirmek söz konusu
      Kısa bir örnekten çıkan onlarca, en fazla düşük yüzler mertebesindeki hash’in ne kadarının ve genel olarak ne kadar ardışık biçimde eşleştiğini arayan bir yapı
      Bugün bile bunu model eğitimiyle yapacaklarını sanmıyorum. Çünkü her gün muazzam sayıda yeni parça ekleniyor ve sürekli yeniden eğitim gerektirirdi
      Hash, yalnızca verimlilik açısından değil, genel sağlamlık açısından da hâlâ daha iyi bir yaklaşım gibi görünüyor
    • 1975’teki akıllıca yaklaşım Parsons code idi; bu da kafadan hesaplanabilen bir şarkı hash’lemesine yakındı
      Sonra sözlükte kelime arar gibi parça aranabiliyordu; umarım bu fikir kolayca kaybolmaz
      [1]: https://en.wikipedia.org/wiki/Parsons_code
    • Küçük bir düzeltme: Shazam 2008’de değil, 2002’de telefonla aranan bir servis olarak çıktı ve sonuçları SMS ile gönderiyordu
      İlk cep telefonu uygulaması 2006’da BREW içindi
      2008 yalnızca Apple’ın App Store’u çıkardığı zamandı; ondan önce üçüncü taraflar iPhone uygulaması yapamıyordu
    • Açıkçası Shazam gibi araçlarda veritabanı + hash algoritması ile özdenetimli model arasında temelde büyük bir fark yok
      İkisi de mükemmel indeksleme ve sıkıştırma çözümleri; yalnızca veri ölçekleri farklı
    • Bunu modelle eğitecek olsaydık, her yeni parça eklendiğinde tüm eğitim sürecini yeniden çalıştırmaktan nasıl kaçınılacağını merak ediyorum
      Her yeni parça için tam yeniden eğitim gerekmeden gömme vektörü hesaplayabilen bir embedding modeli yapmanın bir yolu olabilir mi, emin değilim
  • Shazam, 20 yıldır büyülü hissini kaybetmeyen nadir ürünlerden biri
    Teknoloji insanlarının hedeflemesi gereken şeye gerçekten çok yakın

    • Teknik bilgisi olan biri için müzik parmak izi çıkarma anlaşılabilir, somut bir problem; ama daha önce çözülmüş yöntemi görmeden ayrıntılarına girince oldukça zor bir problem
      Hayvan ya da nesne görseli tanıma gibi dışarıdan benzer görünen ama çoğunlukla tuhaf makine öğrenimi büyüsüne yakın özelliklerin aksine, nadir ama anlaşılabilir bir problem alanına uyuyor
    • Aynı zamanda “dokun, dinlesin ve hemen sonuç gelsin” olan uygulama, yavaş ve reklam dolu şişkin bir uygulamaya dönüştü
      Önceki nesil iPhone’da zamanında yüklenemediği için sonunda uygulamayı sildiğimi hatırlıyorum
    • Google bunu bir adım ileri taşıdı
      Now Playing özelliği sürekli şarkıları algılayıp geçmişe kaydediyor; Google Assistant’ta ise yalnızca mırıldanarak parça arayabiliyorsunuz
      Güvenilir çalışmıyor ama bazen tam isabet ediyor
    • Hatta daha da büyülü hâle geldi
      America’s Got Talent’ta birinin söylediği şarkıyı bulmaya çalıştım; sonuç AGT’deki o şarkıcı olarak dönünce şaşırdım
      Acaba TV programlarını da mı indeksliyorlar diye düşündüm
    • Teknoloji insanları böyle ürünleri hedefler
      Ama ürün yöneticileri bonus ve tatil almak için ürünü sürekli bozmazsa başka ne yapacaklar ki diye insan düşünüyor
  • Chromaprint de var ve biraz farklı şekilde çalışıyor
    Spektrumdaki maksimumlara değil, perde değişim örüntülerine dayanıyor
    Chromaprint, ses parmak izlerini MusicBrainz kayıtlarıyla ilişkilendiren büyük açık veritabanı AcoustID’de kullanılıyor
    Shazam kadar ticari destek almamasına rağmen içinde inanılmaz miktarda müzik olması şaşırtıcı
    [1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/

    • Chromaprint’in tüm parçayı karşılaştırması gerekiyor olabilir diye düşünüyorum
      Yinelenenleri tespit etmek için iyi, ama Shazam’ın parmak izi tasarımı kısa bir parçayı tüm şarkıyla eşleştirmeyi mümkün kılıyor
  • Spektrogramın ne yaptığını iyi yakalayan harika bir yazı; ses parmak izi çıkarmanın nasıl çalıştığını anlamak isteyenler için neredeyse okunması şart
    Başka medyalarda da benzer yaklaşık algoritmalar var; gerçek dünyadaki hash’lemeyi anlamak için bu yazıyı sakin sakin incelemeye değer

    • Genel spektrogram tekniğini Shazam’dan önce Phillips zaten icat etmişti
      Shazam’ın yaptığı şey, yanlış pozitifleri azaltmak için bunu kombinatoryal olarak hash’lemekti
  • Şarkının kendisinden ziyade tür sınıflandırmasını ve yeni şarkı imzalarının oluşturduğu alt tür dallanmalarını algoritmik eşleştirmeyle ele alan harika bir site var.
    Kişisel bir yan proje olarak yürütülen şaşırtıcı bir kaynak; ancak barındırma sorunları gibi nedenlerle yok olma riski var gibi görünüyor.
    Eskiden Pandora’nın Music DNA’sı veya LastFM’in benzer bir özelliği vardı, ama bu site 2023’e kadar insanlığın ürettiği tüm müziğin görsel bir bağlantı ağı gibi; kaybolursa tüm web için bir kayıp olur.
    Every Noise At Once
    https://everynoise.com

  • Bu yöntemin ne kadar sezgisel olduğu ve kendi algılama sürecimizle ne kadar iyi örtüştüğü şaşırtıcı.
    Kabaca melodi parçalarını tanımlayıp sonra bunları sırayla eşleştirmeye dayanan bir yöntem.
    Sadece 5, 7, 10 nota duyduğumuzda bile bir şeyi fark etmemize benziyor.
    Ses seviyesi tepe noktaları gibi şeylere dayanan başka şarkı parmak izi çıkarma yöntemleri de okuduğumu hatırlıyorum; onlar da aynı derecede iyi çalışabilir, ama beynimizin yaptığı işle hiç uyuşmuyor.
    Bu yöntem “yapay bir yan ürüne” yaslanmak yerine temelde bizim yaptığımıza benzer şekilde çalışıyor; bu yüzden oldukça havalı.
    Teknik olarak her zaman melodi değil, ama büyük olasılıkla çoğu durumda melodidir.

  • Shazam’ın zaman ekseninin doğrusal ya da sabit olmadığı durumları nasıl ele aldığını merak ediyorum.
    Teyp, wow and flutter, sürekli hızlanıp yavaşlama gibi durumlar.
    Bildiğim kadarıyla parmak izi çıkarma zamana karşı çok hassas ve 50 ms civarında parçalara bölmek bile bunu tamamen çözmüyor.
    Son baktığımda, bu tür sorunlar için genel teknik olan Dinamik Zaman Bükme (Dynamic Time Warping) hesaplama açısından fazla maliyetliydi.

  • İlgili yazılar. Daha fazlası varsa merak ederim
    How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - Ekim 2022, 1 yorum
    Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - Ağustos 2022, 36 yorum
    Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - Ağustos 2022, 227 yorum
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - Temmuz 2020, 7 yorum
    Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - Ocak 2019, 186 yorum
    Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - Kasım 2018, 2 yorum
    Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - Kasım 2017, 76 yorum
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - Eylül 2017, 13 yorum
    Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - Nisan 2016, 2 yorum
    How Shazam works - https://news.ycombinator.com/item?id=9870408 - Temmuz 2015, 48 yorum
    Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - Mayıs 2015, 18 yorum
    The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - Mayıs 2015, 37 yorum
    The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - Kasım 2014, 34 yorum
    Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - Ekim 2014, 3 yorum
    Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - Mayıs 2013, 16 yorum
    Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - Mayıs 2013, 43 yorum
    An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - Haziran 2011, 4 yorum
    Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - Şubat 2011, 1 yorum
    How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - Şubat 2011, 2 yorum
    Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - Eylül 2010, 23 yorum
    Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - Ekim 2009, 28 yorum

Müzik tanımlama uygulaması Shazam bunu nasıl başarıyor? - https://news.ycombinator.com/item?id=893353 - Ekim 2009, 16 yorum

  • Pop müzik endüstrisinin türe dayalı hit şarkılar üretmeye çalışırken benzer bir mühendisliğin ters yöndeki yaklaşımı gibi görünüyor