Shazam कैसे काम करता है (2022)
(cameronmacleod.com)- Shazam कुछ सेकंड की माइक्रोफोन रिकॉर्डिंग से गाना खोजने के लिए पूरे ऑडियो की तुलना नहीं करता, बल्कि ऑडियो fingerprint बनाकर डेटाबेस में खोजता है
- waveform को जस का तस खिसकाते हुए तुलना करने का तरीका 1 करोड़ गानों के पैमाने, माइक्रोफोन noise, volume बदलाव और frequency effects की वजह से व्यावहारिक नहीं है
- मुख्य flow यह है कि ऑडियो को spectrogram में बदला जाता है, मजबूत frequency peaks खोजे जाते हैं, फिर peak pairs को hash के रूप में store करके तेजी से compare किया जाता है
- peaks noise में भी अपेक्षाकृत अच्छी तरह बचे रहते हैं और storage कम करते हैं, लेकिन गाने के किसी भी हिस्से से पहचान हो सके, इसके लिए उन्हें time और frequency में समान रूप से फैला होना चाहिए
- recognition चरण में matching hashes के Track time - Sample time अंतर को histogram में group किया जाता है, और जिस गाने का एक bin सबसे ज्यादा भरा हो उसे सही उत्तर चुना जाता है
Shazam को हल करनी वाली समस्या
- Shazam एक app है जो आसपास चल रहे गाने को कुछ सेकंड तक record करके डेटाबेस में खोजता है और result दिखाता है
- app बनने से पहले Shazam फोन नंबर आधारित service था
- user को एक नंबर पर call करना होता था और mobile phone का microphone संगीत की तरफ रखना होता था
- 30 सेकंड बाद Shazam call काट देता था और सुने जा रहे गाने की जानकारी SMS से भेजता था
- 2002 में mobile phone call quality ने गाना पहचानना और कठिन बना दिया था
- छोटे example में audio clip को पूरे track पर थोड़ा-थोड़ा move करते हुए match check किया जा सकता है
- लेकिन जब यह पता न हो कि कौन सा गाना है और 1 करोड़ गानों के database में search करना हो, तो समय बहुत बढ़ जाता है
- असली microphone samples में background noise, frequency effects और volume changes के कारण waveform shape बदल सकती है, इसलिए साधारण sliding comparison ठीक से काम नहीं करता
पूरा system flow
- Shazam का तरीका register और recognise flows में बंटा है
- register वह flow है जिसमें गाने को बाद में खोजने के लिए store किया जाता है
- recognise वह flow है जिसमें short audio segment किस गाने का है, यह खोजा जाता है
- दोनों flows एक ही preprocessing stages से गुजरते हैं
- audio का spectrogram calculate करना
- spectrogram में सबसे मजबूत frequency components यानी peaks खोजना
- peaks को pairs में जोड़कर hash बनाना
- register flow calculated hashes को database में store करता है
- recognise flow नए audio से बने hashes की तुलना database के hashes से करता है और matching stage में गाने की पहचान करता है
Spectrogram की गणना
- Fourier transform बताता है कि audio में कौन-कौन सी frequencies शामिल हैं
- 20Hz sine wave पर Fourier transform लगाने से 20Hz के आसपास एक बड़ा spike दिखता है
- sine wave में केवल एक frequency होती है, इसलिए इसे pure tone भी कहा जाता है
- Fourier transform का result frequency spectrum होता है
- time axis केंद्रित representation को time domain कहते हैं
- frequency axis केंद्रित representation को frequency domain कहते हैं
- frequency spectrum का Y-axis हर frequency component की strength दिखाता है; component जितना मजबूत होगा, time-domain signal में वह उतना ज्यादा सुनाई देगा
- कई sine waves को जोड़ने पर हर wave के frequency components combine हो जाते हैं
- 20Hz sine wave में आधी strength की 50Hz sine wave जोड़ने पर 20Hz spike और उससे छोटा 50Hz spike दिखता है
- हर audio signal को ऐसी waves से reconstruct किया जा सकता है
- frequency domain वह जानकारी दिखाता है जो time domain में साफ नहीं दिखती
- noise जुड़ने से time-domain shape बदल जाए, तब भी frequency domain में main frequency spikes अक्सर साफ रह सकते हैं
- पूरे गाने पर केवल एक बार Fourier transform लगाने से कुल frequency strength ही दिखती है, लेकिन वास्तविक गानों की frequencies समय के साथ बदलती हैं
- गाने को छोटे segments में बांटकर हर segment पर Fourier transform लगाया जाए और फिर उन्हें जोड़ा जाए, तो spectrogram बनता है
- spectrogram time, frequency और strength को साथ में represent करता है, और strength को color से दिखाया जा सकता है
- उदाहरण “Like a Stone” के spectrogram में सबसे चमकीले points, यानी ज्यादातर मजबूत frequencies, 5000Hz से नीचे दिखते हैं
- संगीत में ऐसा distribution आम है, और ज्यादातर piano frequencies की range 27Hz-4186Hz होती है
Peak आधारित fingerprint
- audio fingerprint spectrogram में peaks खोजने से शुरू होता है
- peak किसी खास समय पर सबसे बड़ा frequency component होता है
- संगीत में guitar solo की तेज note जैसी चीज उस समय की सबसे बड़ी sound होकर peak बन सकती है
- peaks noise से अपेक्षाकृत कम प्रभावित होते हैं
- किसी peak को पहचान से बाहर करने के लिए noise को उस peak से ज्यादा बड़ा होना होगा
- spectrogram peak track का सबसे मजबूत frequency component होता है
- केवल peaks store करने से fingerprint के लिए जरूरी data कम हो जाता है
- सारी frequency information store न करके केवल सबसे बड़े frequency components रखे जाते हैं
- search करने वाला data कम हो जाता है, जिससे fingerprint search तेज होती है
- peaks time और frequency दोनों में समान रूप से distributed होने चाहिए
- अगर वे time में केवल एक तरफ जमा हों, तो गाने के बाकी हिस्सों के samples पहचाने नहीं जा सकेंगे
- अगर frequency band बहुत narrow हो, तो car horn जैसी किसी खास band की तेज noise peak selection बदल सकती है और उस segment को पहचानना मुश्किल बना सकती है
Maximum filter से peaks खोजना
- peaks को समान रूप से खोजने के लिए image processing की maximum filter technique इस्तेमाल की जा सकती है
- maximum filter हर pixel के आसपास के पड़ोसी area में maximum value खोजता है और उस pixel को उस local maximum value से बदल देता है
- example में हर pixel के आसपास 3x3 area देखने का तरीका है
- इस processing का effect local peak को आसपास के area में expand करने जैसा होता है
- maximum-filtered spectrogram असली spectrogram के low-resolution version जैसा दिखता है
- क्योंकि signal के peaks expand होकर दूसरे pixels पर कब्जा कर लेते हैं
- एक ही color के boxes original image के एक local peak से correspond करते हैं
- maximum filter में local maximum खोजने के लिए box size parameter होता है
- छोटा box इस्तेमाल करने पर ज्यादा peaks मिलते हैं
- बड़ा box इस्तेमाल करने पर कम peaks मिलते हैं
- peak locations को original spectrogram और filtered spectrogram की values के बराबर होने वाले points खोजकर restore किया जाता है
- जो points peak नहीं होते, वे local peak value में बदल जाते हैं, इसलिए उनकी value अलग हो जाती है
- जिन points की value वैसी ही बची रहती है, केवल वही peaks हैं
- सभी peaks को इकट्ठा करके plot करने पर constellation map बनता है
- यह रात के आसमान की image जैसा दिखता है, इसलिए इसे यह नाम मिला है
- peaks की संख्या सीधे fingerprint size को प्रभावित करती है
- अगर लाखों गाने store करने हों, तो fingerprint को छोटा रखना जरूरी है
- peaks कम करने से accuracy भी घटती है, और sample को सही गाने से match करने के मौके कम होते हैं
- peaks कम करने के दो तरीके हैं
- top N peaks इस्तेमाल करें, जहां N audio length के proportional होना चाहिए ताकि छोटे गानों का over-sampling न हो
- किसी specific threshold से बड़े सभी peaks इस्तेमाल करें; यह per-time fingerprint size की guarantee नहीं देता, लेकिन ज्यादा accurate हो सकता है
Peak pairs को hash बनाना
- अगर fingerprint सिर्फ individual spectrogram peaks का collection हो, तो duplicates तेजी से बढ़ते हैं
- अगर हर peak की frequency को 10bit से represent करें, तो 2^10=1024 अलग frequencies represent की जा सकती हैं
- हर track में हजारों points हों, तो बहुत repetition होता है
- fingerprint में uniqueness जरूरी है
- uniqueness जितनी ज्यादा होगी, search उतनी तेज होगी
- यह ज्यादा गानों को पहचानने में मदद करता है
- Shazam का तरीका individual peak नहीं, बल्कि peak pairs से hash बनाता है
- hash में दो peaks की frequencies fA, fB और दोनों peaks के बीच time difference ΔT शामिल होता है
- अगर हर peak के पास 10bit frequency information हो और ΔT को भी 10bit से represent किया जाए, तो कुल 30bit information होती है
- 2^30=1,073,741,824 possibilities, single point की 1024 possibilities से बहुत ज्यादा हैं
- pair generation में anchor point और target zone इस्तेमाल होते हैं
- एक point को anchor point के रूप में चुना जाता है
- anchor point के लिए spectrogram target zone calculate किया जाता है
- target zone के अंदर सभी points को anchor point के साथ pair बनाया जाता है
- Shazam paper target zone चुनने का तरीका detail में explain नहीं करता
- paper image में target zone anchor point से थोड़ा बाद के time में शुरू होता है और anchor point की frequency के आसपास centered दिखता है
- बने हुए pairs database में hash के रूप में store होते हैं
- hash components fA, fB, ΔT होते हैं
- extra information के रूप में Point A time और Track ID store किए जाते हैं
- Point A time और Track ID बाद में matching में किसी specific गाने के specific समय को खोजने में इस्तेमाल होते हैं
- किसी specific track के सभी hashes का collection उस track का fingerprint बनता है
Matching तरीका
- recognise flow sample से fingerprint बनाता है और उसकी तुलना database में पहले से stored fingerprints से करता है
- matching algorithm चार steps में चलता है
- sample fingerprint से match करने वाले सभी hashes database से लाए जाते हैं
- hashes को गानों के हिसाब से group किया जाता है
- हर गाने के लिए check किया जाता है कि hashes time में align होते हैं या नहीं
- सबसे ज्यादा aligned hashes वाले track को चुना जाता है
- abracadabra 3-tuple (fA, fB, ΔT) को सीधे search नहीं करता, बल्कि
hash(fA, fB, ΔT)से return होने वाली single value के रूप में store करता है- हर hash के लिए तीन values search करने के बजाय एक value search की जा सकती है
- database के हर hash से Track ID जुड़ा होता है, इसलिए गानों के हिसाब से grouping संभव है
- इस तरह grouping करने के बाद हर candidate track को score दिया जा सकता है
- अगर sample किसी गाने से match करता है, तो sample के hashes original song के एक segment के साथ अच्छी तरह align होने चाहिए
- noise sample में ऐसे peaks बना सकता है जो किसी दूसरे समय के peaks जैसे दिखें
- hash गलत गाने से भी match हो सकता है
- alignment check करने के लिए हर matching hash पर Track time - Sample time value calculate की जाती है
- असली matching hashes एक ही difference value share करते हैं
- example में difference value 10 वाली rows true match हैं, और दूसरी difference values false match हैं
- difference values का histogram बनाया जाता है और सबसे बड़े bin को गाने का score माना जाता है
- अच्छा match न होने वाले गाने में सभी bin values कम होती हैं
- अच्छे match वाले गाने में एक bin में बड़ा spike बनता है
- केवल सबसे ज्यादा matching hashes वाले गाने को न चुनने की वजह song length bias है
- लंबे गानों में छोटे गानों की तुलना में ज्यादा matches होने की संभावना अधिक होती है
- Spotify पर 4 घंटे से भी लंबे tracks हैं, इसलिए result बहुत skew हो सकता है
abracadabra और reference material
- abracadabra एक open-source project है जिसने Shazam paper के तरीके को implement किया है
- Python code में spectrogram, peak finding, hashing और matching process follow किया जा सकता है
- इसे दूसरे projects में library के रूप में भी इस्तेमाल किया जा सकता है
- संबंधित implementations और material
- abracadabra docs: abracadabra documentation
- dejavu: Python में लिखा गया एक और song recognition implementation
- Computer Vision for Music Identification: dejavu तरीके जैसा song recognition approach
- Chromaprint: थोड़ा अलग approach इस्तेमाल करने वाला algorithm
- Musicbrainz: open-source music information encyclopedia में audio fingerprint की explanation
- Playing with Shazam fingerprints: 2009 में Shazam algorithm implement करने का अनुभव
- Alignment of videos of same event using audio fingerprinting: संगीत से आगे, एक ही event के videos align करने में audio fingerprint इस्तेमाल करने का example
1 टिप्पणियां
Hacker News की राय
Wall Street Journal का Shazam को समझाने वाला बहुत अच्छा वीडियो है
https://www.wsj.com/video/series/in-depth-features/how-shaza...
Chris, Shazam के सह-संस्थापक
Lawn Love ने 2014~2018 के बीच उसके ऊपर वाली suite किराए पर ली थी, और उस दफ़्तर के Shazam mobile app developers अधिग्रहण के बाद भी चुपचाप ही रहे, मैंने कभी जश्न की champagne की आवाज़ भी नहीं सुनी
जब Shazam 2008 में आया, तब hash-based approach एक बहुत चतुर विकल्प था
अगर मैं होता, तो पहले यह बनाता कि हर गाने को जितना संभव हो उतनी computational efficiency के साथ hash में कैसे बदला जाए
अगर यह आज लॉन्च होता, तो बुनियादी R&D दिशा शायद model training होती, लेकिन वह कहीं कम efficient और hosting cost में ज़्यादा महंगी हो सकती थी
यह ऐसा problem लगता है जिसमें model अच्छा कर सकता है, लेकिन गानों की संख्या finite होने के लिहाज़ से hash तरीका कहीं बेहतर performance दे सकता है
संरचना ऐसी है कि छोटे sample से निकले दर्जनों, ज़्यादा से ज़्यादा कम सैकड़ों hashes कितनी बार और मोटे तौर पर लगातार match करते हैं, यह देखा जाता है
आज भी शायद मैं इसे model training से नहीं करता। हर दिन बहुत बड़ी संख्या में नए गाने जुड़ते हैं, इसलिए लगातार retraining करनी पड़ेगी
efficiency के अलावा कुल robustness के मामले में भी hash अब भी बेहतर approach लगता है
उसके बाद शब्दकोश में शब्द खोजने की तरह गाने खोजे जा सकते थे, और मैं चाहता हूँ कि यह विचार आसानी से गायब न हो
[1]: https://en.wikipedia.org/wiki/Parsons_code
पहला mobile app 2006 में BREW के लिए था
2008 सिर्फ वह समय था जब Apple ने App Store लॉन्च किया; उससे पहले third party iPhone apps नहीं बना सकती थी
दोनों ही बेहतरीन indexing और compression solutions हैं, बस data scale अलग है
शायद ऐसा embedding model बनाने का तरीका हो जिसमें हर नए गाने के लिए full retraining के बिना embedding vector निकाला जा सके
Shazam उन दुर्लभ products में है जिनमें 20 साल बाद भी जादू जैसा एहसास कम नहीं हुआ
यह सचमुच उस चीज़ के बहुत करीब है जिसकी engineers को ओर बढ़ना चाहिए
जानवरों या वस्तुओं की image recognition जैसी ऊपर-ऊपर मिलती-जुलती लेकिन ज़्यादातर अजीब machine learning magic जैसी लगने वाली features से अलग, यह एक दुर्लभ लेकिन समझ में आने वाले problem domain में फिट बैठती है
याद है कि पुराने generation के iPhone पर यह समय से load भी नहीं हो पाती थी, और मैंने आखिरकार app हटा दी थी
Now Playing feature लगातार गाने पहचानकर history में रखता है, और Google Assistant में सिर्फ गुनगुनाने से भी गाना खोजा जा सकता है
यह स्थिर रूप से काम नहीं करता, लेकिन कभी-कभी बिल्कुल सही पकड़ लेता है
मैं America’s Got Talent में किसी के गाए गाने को ढूँढने की कोशिश कर रहा था, और नतीजा AGT में आए उसी singer पर लौट आया, यह देखकर हैरानी हुई
लगा मानो TV programs तक index किए जा रहे हों
लेकिन product managers, bonus और छुट्टियाँ पाने के लिए अगर product को लगातार खराब न करें, तो फिर वे करेंगे क्या
Chromaprint भी है, और यह थोड़ा अलग तरीके से काम करता है
यह spectrum के maximum values पर नहीं, बल्कि pitch change patterns पर आधारित है
Chromaprint का उपयोग AcoustID में होता है, जो audio fingerprints को MusicBrainz recordings से जोड़ने वाला बड़ा public database है
हैरानी की बात है कि Shazam जितना commercial support न होने पर भी इसमें संगीत की मात्रा बहुत ज़्यादा है
[1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/
यह duplicate detection के लिए अच्छा है, लेकिन Shazam की fingerprint design छोटे टुकड़ों को पूरे गाने से match करने देती है
यह spectrogram क्या करता है, इसे बहुत अच्छी तरह पकड़ने वाला शानदार लेख है, और audio fingerprinting कैसे काम करती है इसे समझना चाहने वालों के लिए लगभग अनिवार्य पढ़ाई जैसा है
दूसरे media में भी ऐसे ही approximate algorithms हैं, इसलिए real-world hashing को समझना हो तो इस लेख को आराम से पढ़ना सार्थक है
Shazam ने जो किया, वह false positives कम करने के लिए combinatorial hashing था
गानों की पहचान नहीं, बल्कि genre classification और नए track signatures से बनने वाली subgenre branching को algorithmic matching के ज़रिए संभालने वाली एक शानदार साइट है
यह एक व्यक्ति के side project के रूप में चलने वाला अद्भुत resource है, लेकिन hosting जैसी समस्याओं की वजह से इसके गायब हो जाने का खतरा लगता है
पहले Pandora का Music DNA या LastFM में इससे मिलते-जुलते features थे, लेकिन यह साइट 2023 तक इंसानियत द्वारा बनाई गई पूरी संगीत दुनिया का एक visual network जैसी लगती है, इसलिए अगर यह गायब हो गई तो वह पूरे web के लिए नुकसान होगा
Every Noise At Once
https://everynoise.com
Every Noise at Once - https://news.ycombinator.com/item?id=26668426 - अप्रैल 2021, 94 comments
Every Noise at Once - https://news.ycombinator.com/item?id=20585447 - अगस्त 2019, 82 comments
Every Noise at Once – an algorithmically-generated scatter-plot of musical genre - https://news.ycombinator.com/item?id=10269685 - सितंबर 2015, 23 comments
An algorithmically-generated scatter-plot of musical genres - with samples - https://news.ycombinator.com/item?id=9315499 - अप्रैल 2015, 3 comments
Spotify में रहते समय वे genre researcher थे
यह मिलते-जुलते गाने दिखाता है, और काफ़ी अच्छा काम करता है
यह तरीका कितना intuitive है, और हमारी अपनी perception process से कितना अच्छी तरह मेल खाता है, यह चौंकाने वाला है
मोटे तौर पर यह melody fragments की पहचान करता है और फिर उन्हें क्रम में मिलाता है
यह वैसा ही है जैसे हम सिर्फ 5, 7 या 10 notes सुनकर भी कुछ पहचान लेते हैं
लगता है मैंने गानों के fingerprinting के दूसरे तरीकों के बारे में भी पढ़ा है जो volume peaks जैसी चीज़ों पर निर्भर करते हैं; वे भी शायद उतने ही अच्छे से काम करें, लेकिन वे हमारे दिमाग़ के काम करने के तरीके से बिल्कुल मेल नहीं खाते
यह तरीका “artificial byproducts” पर निर्भर नहीं करता, बल्कि मूल रूप से हमारे तरीके जैसा काम करता है, इसलिए यह काफ़ी शानदार है
तकनीकी रूप से यह हमेशा melody नहीं होती, लेकिन ज़्यादातर मामलों में उसके melody होने की संभावना ज़्यादा है
यह जानने की जिज्ञासा है कि Shazam उन मामलों को कैसे संभालता है जहाँ time axis linear या स्थिर नहीं होती
जैसे tape, wow and flutter, या ऐसी स्थिति जहाँ चीज़ लगातार तेज़ और धीमी होती रहती है
जहाँ तक मुझे पता है, fingerprinting समय के प्रति बहुत संवेदनशील होती है, और इसे लगभग 50ms के chunks में काट देने से भी समस्या पूरी तरह हल नहीं होती
पिछली बार जब देखा था, तो इस तरह की समस्याओं के लिए सामान्य तकनीक Dynamic Time Warping का computational cost बहुत ज़्यादा था
ये संबंधित लेख हैं। अगर और हों तो जानने में दिलचस्पी होगी
How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - अक्टूबर 2022, 1 टिप्पणी
Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - अगस्त 2022, 36 टिप्पणियाँ
Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - अगस्त 2022, 227 टिप्पणियाँ
How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - जुलाई 2020, 7 टिप्पणियाँ
Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - जनवरी 2019, 186 टिप्पणियाँ
Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - नवंबर 2018, 2 टिप्पणियाँ
Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - नवंबर 2017, 76 टिप्पणियाँ
How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - सितंबर 2017, 13 टिप्पणियाँ
Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - अप्रैल 2016, 2 टिप्पणियाँ
How Shazam works - https://news.ycombinator.com/item?id=9870408 - जुलाई 2015, 48 टिप्पणियाँ
Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - मई 2015, 18 टिप्पणियाँ
The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - मई 2015, 37 टिप्पणियाँ
The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - नवंबर 2014, 34 टिप्पणियाँ
Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - अक्टूबर 2014, 3 टिप्पणियाँ
Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - मई 2013, 16 टिप्पणियाँ
Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - मई 2013, 43 टिप्पणियाँ
An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - जून 2011, 4 टिप्पणियाँ
Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - फ़रवरी 2011, 1 टिप्पणी
How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - फ़रवरी 2011, 2 टिप्पणियाँ
Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - सितंबर 2010, 23 टिप्पणियाँ
Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - अक्टूबर 2009, 28 टिप्पणियाँ
म्यूज़िक की पहचान करने वाला ऐप Shazam अपना जादू कैसे करता है? - https://news.ycombinator.com/item?id=893353 - अक्टूबर 2009, 16 टिप्पणियाँ