Shazam ทำงานกันแน่อย่างไร?
(perthirtysix.com/how-the-heck-does-shazam-work)- การรู้จำเพลงทำงานโดยแปลงการสั่นของอากาศที่ไมโครโฟนรับได้ให้เป็น waveform จากนั้นบีบอัดเป็น spectrogram และยอดพีกความถี่ที่เด่นเพียงไม่กี่จุด เพื่อสร้างลายนิ้วมือของเพลง
- เนื่องจาก waveform ดิบเปลี่ยนไปได้ง่ายตามระดับเสียงและสภาพแวดล้อมในการเล่น จึงใช้เป็นเกณฑ์ระบุตัวตนได้ยาก และต้องใช้ FFT กับช่วงสั้น ๆ แต่ละช่วงเพื่อเผยโครงสร้างความถี่ตามเวลา จึงจะเปรียบเทียบได้อย่างเสถียร
- พีกที่เหลืออยู่จะไม่ถูกใช้เป็นจุดเดี่ยว ๆ แต่ถูกจับเป็นคู่ระหว่าง anchor และ target zone แล้วทำเป็นแฮช ซึ่งชุดผสมแบบนี้ทำหน้าที่เป็น fingerprint hash ที่เฉพาะพอจะแยกแยะไฟล์บันทึกเสียงแต่ละเวอร์ชันได้
- การค้นหาไม่ได้เทียบเพลงทีละเพลง แต่ใช้โครงสร้างแบบ hash-first ที่ค้นหาด้วยแฮชเป็นคีย์ได้ทันที และในขั้นสุดท้ายยังตรวจสอบว่า ช่วงเวลาห่างกัน ของแฮชที่ตรงกันสอดคล้องกันด้วย เพื่อเพิ่มความน่าเชื่อถือ
- แม้ฐานข้อมูลขนาดใหญ่บนเซิร์ฟเวอร์กับวิธีแบบ on-device จะมีขนาดและข้อจำกัดต่างกัน แต่แก่นสำคัญคือการทิ้งข้อมูลส่วนใหญ่ไปแล้วเก็บเฉพาะ landmark peak ไว้ เพื่อหาเพลงได้รวดเร็วแม้จากคลิปสั้นและมีเสียงรบกวน
กระบวนการตีความเสียงย้อนกลับ
- ไมโครโฟนในโทรศัพท์ใช้ diaphragm ที่บางมากวัดการสั่นของอากาศ แล้วแปลงเป็นลำดับตัวเลขที่แสดงความดันอากาศตามเวลา หรือก็คือ waveform แล้วเก็บไว้
- แก้วหูของคนเราก็รับคลื่นความดันแบบเดียวกัน แต่โทรศัพท์มองมันไม่ใช่เป็นเสียงโดยตรง หากเป็นลำดับตัวเลข
- เสียงที่เข้ามาจะถูกสุ่มตัวอย่างหลายหมื่นครั้งต่อวินาที โดยทั่วไปใช้ 44,100 Hz
- การระบุเพลงจาก waveform ดิบเพียงอย่างเดียวทำได้ยาก เพราะแม้จะเป็นเพลงเดียวกัน ถ้าเปิดดังขึ้น waveform ก็อาจเปลี่ยนไปอย่างมาก และเพลงคนละเพลงก็อาจมี waveform ที่คล้ายกันได้
- สภาพแวดล้อมการเล่นที่ต่างกันก็ทำให้ waveform ของเพลงเดียวกันต่างออกไปได้ จึงไม่เหมาะจะใช้ waveform เองเป็นเกณฑ์ระบุตัวตน
- เพื่อลดปัญหานี้ ต้องแบ่ง waveform ออกเป็นชิ้นเล็ก ๆ แล้วใช้ FFT เพื่อแยกว่าในแต่ละช่วงเวลามีความถี่ใดอยู่บ้าง
- ถ้าจะพูดเป็นคำถาม ก็คือ "ถ้าจะสร้างเสียงสั้นชิ้นนี้ขึ้นมาใหม่ ต้องเอา pure tone อะไรมาบวกกันบ้าง"
- เมื่อนำผลของแต่ละชิ้นมาเรียงต่อกันด้านข้าง ก็จะได้ spectrogram ที่ประกอบด้วยแกนเวลา แกนความถี่ และแกนความสว่าง
- FFT อาศัยข้อเท็จจริงที่ว่า waveform ที่ซับซ้อนเพียงใดก็สามารถแสดงเป็นผลรวมของคลื่นไซน์ที่มีความถี่ แอมพลิจูด และเฟสต่างกันได้
- ตัวอย่างเช่น ถ้าใส่ 1,024 samples เข้าไป ก็จะได้สเปกตรัมที่บอกว่ามีพลังงานอยู่มากน้อยเพียงใดในแต่ละความถี่
- สำหรับแต่ละ frequency bin จะนำทุก sample ไปคูณกับคลื่นไซน์ของความถี่นั้นแล้วบวกรวมกัน หากความถี่นั้นมีอยู่จริงในสัญญาณ ผลรวมจะสูง แต่ถ้าไม่มีก็จะหักล้างกันไป
- หัวใจของ FFT คือความเร็ว เพราะการแยกองค์ประกอบแบบตรงไปตรงมาจะต้องคำนวณหลายล้านครั้งต่อหนึ่งชิ้น แต่ FFT ใช้สมมาตรทางคณิตศาสตร์เพื่อลดลงเหลือราว n log n
- เร็วพอในระดับที่โทรศัพท์ก็รันได้หลายร้อยครั้งต่อวินาที
- อุปกรณ์จะเลื่อนหน้าต่างนี้ไปบนเสียงอย่างต่อเนื่อง ใช้ FFT กับแต่ละชิ้น แล้วสะสมผลเพื่อสร้าง spectrogram
- ตัวอย่างแบบง่ายมักใช้เสียงสังเคราะห์ที่มีความถี่บริสุทธิ์เพียงค่าเดียว ซึ่งช่วยให้เข้าใจได้ แต่ดนตรีจริงซับซ้อนกว่านั้นมาก
- เมื่อป้อนเพลงจริงหรือเสียงฮัมเข้าไมโครโฟน spectrogram จะดูยุ่งกว่ามาก แต่ FFT ก็ยังดึงโครงสร้างภายในออกมาได้แบบเรียลไทม์
- ในตัวอย่างบนเบราว์เซอร์ เสียงทั้งหมดถูกประมวลผลภายในเบราว์เซอร์เอง โดยไม่บันทึกหรือส่งออกไปภายนอก
ลายนิ้วมือที่ยิ่งน้อยยิ่งแข็งแรง
- ระบบจะไม่เก็บ spectrogram ทั้งหมด แต่จะเก็บไว้เฉพาะพีกที่ใหญ่ที่สุด แล้วบีบอัดเป็น ชุดจุดแบบ sparse
- เมื่อทิ้งสัญญาณที่อ่อนและเหลือไว้เฉพาะจุดที่แรงที่สุด ก็จะเหลือแต่ landmark ที่สำคัญเชิงอะคูสติก
- เหตุผลที่ต้องทิ้งข้อมูลส่วนใหญ่ ก็เพราะการเก็บและค้นหา spectrogram ทั้งชุดนั้นช้าเกินไปแม้สำหรับคอมพิวเตอร์
- ยิ่งตั้งค่า threshold สูง สัญญาณที่จางก็จะยิ่งหายไป และเหลือเพียงพีกใหญ่ ๆ
- วิธีนี้ช่วยเพิ่ม ความทนทานต่อ noise
- เสียงรบกวนพื้นหลังจะเพิ่มพลังงานระดับต่ำกระจายไปทั่ว spectrogram แต่โดยมากจะไม่สามารถสร้างพีกที่แรงที่สุดในบางบริเวณได้
- landmark ที่เหลืออยู่จึงเป็นความถี่เด่นที่โผล่พ้น noise ออกมา
- แต่ในทางกลับกัน วิธีทำลายนิ้วมือแบบนี้มักทำงานได้ไม่ดีนักเมื่อให้คนร้องเพลงเข้ามาโดยตรง
- ต่อให้ร้องได้ดีมาก ก็ยังมีโอกาสสูงที่จะสร้างแฮชที่ต่างจากต้นฉบับ
- นั่นจึงเป็นเหตุผลที่ระบบ machine learning-based รุ่นใหม่กว่านำทำนองมาเป็นหลักแทนความถี่ที่แม่นตรง เพื่อรองรับการฮัมและการร้องเพลง
เชื่อมจุดเข้าด้วยกันเพื่อสร้างแฮช
- จุดเดียวมีพลังในการแยกแยะไม่พอ แต่การจับคู่สองจุดมีโอกาสเกิดขึ้นโดยบังเอิญต่ำกว่ามาก จึงเหมาะจะใช้เป็น fingerprint hash
- ตัวอย่างเช่น 1,200 Hz ณ ช่วงเวลาหนึ่งอาจพบได้ในเพลงหลายพันเพลง แต่ถ้าหลังจาก 1,200 Hz ไป 0.3 วินาทีมี 2,400 Hz ตามมา ชุดคู่นี้จะเฉพาะเจาะจงกว่ามาก
- อัลกอริทึมจะนำแต่ละพีกมาเป็น anchor ทีละจุด จากนั้นกำหนด target zone ทางด้านขวาที่มีช่วงเวลาและช่วงความถี่ แล้วจับคู่กับพีกทุกจุดที่อยู่ในนั้น
- แต่ละคู่จะสร้าง hash แบบสั้นจากตัวเลขสามค่า คือความถี่สองค่าและส่วนต่างของเวลา
- แฮชทำหน้าที่เป็นรหัสสั้นที่ให้ผลลัพธ์เดิมเสมอเมื่อป้อนข้อมูลเดิม และหากเปลี่ยนข้อมูลเพียงเล็กน้อยก็มักได้ค่าที่ต่างไปอย่างสิ้นเชิง
- ระบบแนว Shazam มีวิธีจัดการกับความแปรผันเล็กน้อย แต่โดยพื้นฐานแล้วแฮชถูกสร้างจากความถี่และจังหวะเวลาที่แม่นยำ
- ผลลัพธ์คือแฮชนี้ทำงานคล้ายลายนิ้วมือของ ไฟล์บันทึกเสียงเวอร์ชันหนึ่งโดยเฉพาะ มากกว่าจะเป็นของเพลงในเชิงนามธรรม
- เพราะฉะนั้น cover หรือ remix จึงจับคู่ได้ยากกว่า
- แม้แต่เพลงยาว 3 นาที เพลงเดียวก็อาจสร้าง fingerprint hash ได้หลายพันรายการ และฐานข้อมูลจะเก็บทั้งหมดไว้
- โทรศัพท์จะถือแฮชจำนวนเล็กน้อยที่ได้จากคลิป 5 วินาที ส่วนฐานข้อมูลถือแฮชนับล้านที่ดึงมาจากเพลงจำนวนมหาศาล แล้วจึงเข้าสู่ขั้นตอนการจับคู่
การหาคู่ที่ตรงอย่างแม่นยำ
- แฮชแต่ละตัวถูกใช้เหมือน ที่อยู่ ชนิดหนึ่ง โดยระบบจะเปิดตารางขนาดใหญ่เพื่อค้นหาทันทีว่าเพลงใดบ้างที่มีแฮชเดียวกับแฮชที่ได้จากคลิป
- แทนที่จะไล่ดูทีละเพลง ระบบจะเข้าถึงด้วยตัวแฮชเองในฐานะคีย์
- วิธี song-first แบบตรงไปตรงมาต้องตรวจทุกเพลงทีละเพลงและเช็กว่าแฮชซ้อนทับกันหรือไม่ จึงยิ่งช้าเมื่อจำนวนเพลงเพิ่มขึ้น
- เนื้อหาอธิบายว่าวิธีนี้ใช้เวลาแบบ O(N)
- มีการใช้ฐานข้อมูลตัวอย่างและรายการแฮชจากคลิป 5 วินาทีเพื่อให้เห็นภาพความไม่มีประสิทธิภาพนี้
- คอมพิวเตอร์สามารถพลิกวิธีคิดนี้เป็นแบบ hash-first ได้
- สำหรับแต่ละแฮช ก็ถามตรง ๆ ว่า "มีเพลงไหนบ้างที่มีแฮชนี้"
- เปรียบได้กับดัชนีท้ายหนังสือ ที่พาไปยังคำที่ต้องการได้ทันทีโดยไม่ต้องอ่านทุกหน้าใหม่
- แนวทางนี้ทำให้การค้นหาใกล้เคียงกับ O(1) อย่างมาก
- ไม่ว่าจะมี 100 เพลงหรือ 100 ล้านเพลง เวลาประมวลผลก็ยังใกล้เคียงกัน
- เนื่องจากจำนวนแฮชที่เป็นไปได้มีมหาศาล แม้จะมีเพลงหลายล้านเพลง แต่ในแต่ละที่อยู่ก็มักมีรายการอยู่เพียงไม่กี่รายการเท่านั้น
- แต่การมีแฮชตรงกันเพียงอย่างเดียวก็ยังไม่พอ การตรวจขั้นสุดท้ายจะดูที่ ช่วงเวลาห่างกัน
- ตัวอย่างเช่น ถ้าในคลิป 17403C และ 19A998 ห่างกัน 1.2 วินาที เพลงที่เป็นผู้ต้องสงสัยก็ต้องมีแฮชสองตัวนี้ห่างกัน 1.2 วินาทีเช่นกัน
- เมื่อส่วนต่างของเวลาระหว่างแฮชที่ตรงกันสอดคล้องกัน และมีจำนวนตรงกันมากพอ จึงจะถือเป็นการแมตช์ที่มีความน่าเชื่อถือสูง
- ระบบทั้งหมดถูกออกแบบมาให้สอดรับกับงานที่คอมพิวเตอร์ทำได้ดีเป็นพิเศษ
- เน้นการเปรียบเทียบตัวเลขและการค้นหาตามที่อยู่
- จึงสามารถค้นหาครบทั้งระบบจากเพลงหลายล้านเพลงได้ในเวลา สั้นกว่า 1 วินาทีมาก
แนวทางที่ทันสมัยกว่า
- บริการรู้จำเพลงจำนวนมากแบบ Shazam จะส่งคลิปเสียงไปยังเซิร์ฟเวอร์ แล้วทำการจับคู่กับ ฐานข้อมูลลายนิ้วมือ ขนาดใหญ่ที่อยู่บนเซิร์ฟเวอร์
- โครงสร้างแบบนี้ถูกใช้เพราะฐานข้อมูลมีขนาดใหญ่มาก เปลี่ยนแปลงตลอดเวลา และการค้นหาต้องใช้ทรัพยากรคำนวณพอสมควร
- ในทางกลับกัน การรู้จำบนอุปกรณ์ของ Apple และ Now Playing ของ Google Pixel จะรันทั้งหมดแบบโลคัลภายในโทรศัพท์
- ใช้ฐานข้อมูลที่เล็กกว่าและคัดเลือกมาแล้ว รวมถึงโมเดลที่ปรับแต่งให้เหมาะสม
- แลกความครอบคลุมทั้งหมดกับความเร็ว และยังรวมถึงแนวทาง machine learning ที่ซับซ้อนกว่าซึ่งทนต่อ noise และการเปลี่ยนรูปของเสียงได้ดีกว่า
- วิธี on-device เร็วกว่าและทำงานได้แม้ไม่มีอินเทอร์เน็ต แต่ก็มีข้อจำกัดว่าฐานข้อมูลเพลงที่จับคู่ได้จะเล็กกว่ามาก
- การอัปเดตเพลงใหม่ก็มักช้ากว่าเช่นกัน
- หากตรวจพบการเปลี่ยนตำแหน่งที่อยู่ ก็อาจต้องดึงข้อมูลชุดใหม่กลับมาอีกครั้ง
- ความแตกต่างของเพลงฮิตในแต่ละภูมิภาคก็ส่งผลต่อการจัดชุดข้อมูลแบบ on-device ด้วย
- เพลงฮิตในญี่ปุ่นอาจไม่เหมือนเพลงฮิตในสหรัฐอเมริกา
- ไม่ว่าการจับคู่จะเกิดขึ้นบนเซิร์ฟเวอร์หรือภายในอุปกรณ์ เทคนิคหลักก็ยังเหมือนเดิม
- เมื่อทิ้งข้อมูลส่วนใหญ่ไปและเก็บไว้เพียง landmark peak ไม่กี่จุด คลิป 5 วินาทีจากคาเฟ่ที่มีเสียงดัง ก็จะถูกเปลี่ยนเป็นชุดพิกัดที่แม่นพอจะชี้ไปยังเพลงหนึ่งเพลงจากหลายล้านเพลงได้
- แก่นของการรู้จำจึงไม่ใช่การฟังให้ได้มากที่สุด แต่ใกล้เคียงกับการ ทิ้งสิ่งที่ควรมองข้ามออกไปให้แม่นยำ
งานวิจัยต้นทาง
- เนื้อหาส่วนใหญ่ในบทความนี้อ้างอิงจากงานวิจัยปี 2003 ของ Avery Wang ชื่อ An Industrial-Strength Audio Search Algorithm
- หากต้องการศึกษาทั้งด้าน signal processing และการออกแบบระบบให้ลึกขึ้น งานนี้คือจุดเริ่มต้นโดยตรงที่ดี
- ลำดับภาพรวมทั้งหมดประกอบด้วยการแปลง waveform การเลือกพีก การสร้างแฮชจากคู่พีก การค้นหาด้วย inverted index และการตรวจสอบการจัดแนวตามเวลา
- ขั้นตอนเหล่านี้เมื่อรวมกันแล้ว ทำให้สามารถระบุเพลงได้อย่างรวดเร็วแม้จากคลิปสั้นและมีเสียงรบกวน
1 ความคิดเห็น
ความเห็นจาก Hacker News
น่าจะดีถ้าอ่าน เอกสารเกี่ยวกับ Shazam ไปด้วย มีบทความต้นฉบับ https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf และถ้าสนใจจริง ๆ ก็คุ้มที่จะไปหา presentation ของผู้เขียนบน YouTube ด้วย https://news.ycombinator.com/item?id=18069968 มีโพสต์จากพนักงาน Shazam, https://news.ycombinator.com/item?id=38538996 มีคำอธิบายที่ผู้ร่วมก่อตั้งยืนยันรับรอง, และ https://news.ycombinator.com/item?id=41127726 มีการทำซ้ำอัลกอริทึมด้วย Go สุดท้ายแล้ว ผมคิดว่าหลายครั้ง ML ก็มีมูลค่าที่ ข้อมูล มากกว่าตัวโค้ดเอง
ข้อเดาล่าสุดของผมคือ อาจจะไม่ใช่เลยก็ได้ มันใช้ได้ดีพอสมควรกับเพลงป๊อปทั่วไป แต่ตอนพักการแข่งขันไอซ์สเก็ตผมลอง Shazam เพลง ซินธ์ ที่ค่อนข้างดีหลายเพลงหลายครั้งแล้ว มันหาไม่เจอสักเพลง ก็อาจเป็นเพลงที่ยังไม่ปล่อย หรือเป็นเพลงเฉพาะกลุ่มมาก ๆ แต่ก็ดูเป็นไปได้เหมือนกันว่า Shazam ล้มเหลวแบบชัดเจน
นี่ก็แน่นอนว่าเป็นเทคโนโลยีตระกูลเดียวกับที่ใช้ใน ACR ของทีวี แต่เหตุผลที่ Shazam มีชื่อเสียงบนอินเทอร์เน็ตดีกว่ามาก น่าจะเพราะมันเคารพ เจตนาและความยินยอม ของผู้ใช้ ถ้าทำอะไรคล้ายกันบนทีวีแต่ข้อมูลไม่ได้ถูกส่งไปเพื่อขายโฆษณาอย่างเดียว ก็น่าจะมีรูปแบบที่เป็นประโยชน์กับผู้บริโภคจริง ๆ ได้
บทความนี้น่าจะเป็นหนึ่งในคำอธิบายเชิงภาพของอัลกอริทึม audio fingerprinting ดั้งเดิมจาก บทความ Shazam ปี 2003 ที่ดีที่สุดเท่าที่เคยเห็น แต่ก็คิดว่า ณ ตอนนี้พวกเขาน่าจะเปลี่ยนไปใช้ โมเดล ML กันแล้วในช่วงใดช่วงหนึ่ง
มีอัลกอริทึมชื่อ DTW(dynamic time warping) ซึ่งมักถูกมองข้าม สัญชาตญาณผมบอกว่า Shazam เองก็น่าจะใช้สิ่งนี้อยู่บ้าง
การ รู้จำว่าเป็นไฟล์บันทึกเสียงเดียวกัน ไม่ได้ยากมาก ถ้าเป็นเสียงบันทึกเดียวกัน progression ของคอร์ดและ timing จะทำซ้ำได้อย่างแม่นยำ ดังนั้นเทคโนโลยีแนวนี้มีมานานเกิน 10 ปีมากแล้ว ในทางกลับกัน การเดาว่าเป็นเพลงเดียวกันจาก เวอร์ชันคัฟเวอร์ หรือเสียงบันทึกคนละชุดนั้นยากกว่ามาก Audible Magic อ้างใน https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/ ว่าสามารถระบุได้แม้แต่การแสดงหลายเวอร์ชันของเพลงเดียวกันหรือพารอดี ซึ่งแน่นอนว่าเป็นวิธีที่ใช้ AI และการประมวลผลมากขึ้น
ตอนแรกก็คิดว่าเป็นหัวข้อนี้อีกแล้ว แต่พอดูแล้วเป็น SCP โดเมนนี้ดูน่าสงสัยนิดหน่อย การวิเคราะห์ที่สมบูรณ์กว่าบทความปี 2022 ของ CameronMacLeod คือ https://news.ycombinator.com/item?id=38531428 และบทความปี 2009 ของ Slate คือ https://news.ycombinator.com/item?id=893353
ต้องเพิ่มอันนี้เข้าไปในรายการโปรเจกต์ของผม ถ้าเอา Dinosaur game มาทำให้กระโดดด้วย เสียงขันของไก่ แทนการกดปุ่มก็น่าจะสนุกดี
สงสัยว่ามีวิธีทำให้ แอปแบบ Shazam ตรวจจับไม่ได้ไหม เช่นผสม noise หรือใช้เทคนิคอื่น
ผมเคยทำสิ่งนี้เป็นโปรเจกต์วิทยาศาสตร์บน Apple ][c ตั้งแต่ปี 1986