Shazam Nasıl Çalışır? (2022)
(cameronmacleod.com)- 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
- abracadabra, Shazam makalesindeki yaklaşımı uygulayan açık kaynaklı bir projedir
- Python koduyla spectrogram, peak bulma, hashing ve matching süreçleri adım adım incelenebilir
- Başka projelerde library olarak da kullanılabilir
- İlgili uygulamalar ve kaynaklar
- abracadabra docs: abracadabra dokümantasyonu
- dejavu: Python ile yazılmış başka bir şarkı tanıma uygulaması
- Computer Vision for Music Identification: dejavu yaklaşımına benzer bir şarkı tanıma yöntemi
- Chromaprint: biraz farklı bir yaklaşım kullanan algoritma
- Musicbrainz: açık kaynak müzik bilgi ansiklopedisinde ses parmak izi açıklaması
- Playing with Shazam fingerprints: 2009'da Shazam algoritmasını uygulama deneyimi
- Alignment of videos of same event using audio fingerprinting: müziğin ötesinde, aynı etkinliğe ait videoları hizalamada ses parmak izi kullanımına örnek
1 yorum
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
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
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
Sonra sözlükte kelime arar gibi parça aranabiliyordu; umarım bu fikir kolayca kaybolmaz
[1]: https://en.wikipedia.org/wiki/Parsons_code
İ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
İkisi de mükemmel indeksleme ve sıkıştırma çözümleri; yalnızca veri ölçekleri farklı
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
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
Önceki nesil iPhone’da zamanında yüklenemediği için sonunda uygulamayı sildiğimi hatırlıyorum
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
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
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/
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
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
Every Noise at Once - https://news.ycombinator.com/item?id=26668426 - Nisan 2021, 94 yorum
Every Noise at Once - https://news.ycombinator.com/item?id=20585447 - Ağustos 2019, 82 yorum
Every Noise at Once – an algorithmically-generated scatter-plot of musical genre - https://news.ycombinator.com/item?id=10269685 - Eylül 2015, 23 yorum
An algorithmically-generated scatter-plot of musical genres - with samples - https://news.ycombinator.com/item?id=9315499 - Nisan 2015, 3 yorum
Spotify’dayken tür araştırmacısıydı.
Benzer şarkıları gösteriyor; bence epey iyi yapıyor.
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