יחידה 3 · Shazam ופרצופים עצמיים: תדרים, PCA וייצוג חזותי
זיהוי שיר מתוך קטע קצר ורועש בעזרת נקודות שיא בספקטרוגרמה
מאיפה באנו, ומה הפרק הזה מוסיף
בפאב מתנגן שיר. הטלפון מקליט ממנו כמה שניות, עם רעש של אנשים, ואחרי שנייה חוזר שם השיר. איך? במסד מיליוני שירים, ואי אפשר להשוות את ההקלטה לכל אחד מהם צליל מול צליל: הרעש והמיקרופון שינו כל מספר בה, והקטע יכול להתחיל בכל נקודה בשיר. הרעיון של אייברי ואנג (2003), שעליו בנוי Shazam, הוא לא לשמור את השיר עצמו אלא טביעת אצבע שלו: מפרקים את הצליל לתדרים, רגע אחר רגע, שומרים מכל רגע רק את נקודות השיא הבודדות, ומחפשים אותן בטבלה. זה המעבר של היחידה הזאת: במקום הייצוג האקראי של הפרספטרון, ייצוג מושכל. את טביעת האצבע לא בחרה מכונה; אנשים עיצבו אותה, מתוך הבנה מה בצליל שורד רעש ומה לא, ואפשר לומר שבחירת ייצוג חכם היא חצי מהלמידה.
מבוסס על המאמר:
Wang, A. L.-C. (2003). An industrial-strength audio search algorithm. Proceedings of the 4th International Conference on Music Information Retrieval (ISMIR), 7–13.
הסיפור הבסיסי
שיר הוא רצף של אירועים בזמן: בכל רגע נשמעים כמה תדרים בולטים, ואחריהם אחרים. ואנג שומר מכל שיר רק את מבנה האירועים הזה, רשימה של נקודות [math]\displaystyle{ (t,f) }[/math], זמן ותדר, בלי העוצמה: רעש משנה את העוצמות אבל אינו מוחק את השיאים. אבל אירוע אחד אינו מזהה כלום, אותו תדר מופיע בהרבה שירים. מה שמזהה הוא היחס בין אירועים: תדר כזה, ואחריו, במרווח זמן כזה, תדר אחר. לכן המילה של טביעת האצבע היא זוג של אירועים סמוכים, מקודד למספר שלם אחד של 32 סיביות: שני התדרים והפרש הזמן ביניהם. המספר אינו תלוי במקום של הזוג בשיר, רק במרחק בין שני האירועים, ולכן אותו מספר יוצא גם מהקלטה שמתחילה באמצע.
ברמת החישוב, המספר הזה הוא מפתח בטבלת גיבוב (hash table): לכל מפתח רשומה, ובה כל השירים והזמנים שבהם הוא מופיע. איתור הרשומה הוא פעולה אחת, [math]\displaystyle{ O(1) }[/math], שאינה תלויה במספר השירים במסד, ולכן החיפוש כולו עולה כמספר הזוגות שבהקלטה, גם במסד של מיליוני שירים, ואף שיר אינו מושווה להקלטה. זוג שנמצא בטבלה הוא חשד: שיר מסוים, והמקום בשיר שבו ההקלטה מתחילה, לפי הפרש הזמן בין הופעת הזוג בשיר להופעתו בהקלטה. מכאן פשוט: לוקחים את אירועי השיא של השיר החשוד מאותו מקום והלאה ובודקים כמה מהם מופיעים בהקלטה. בשיר הנכון רבים מהם שם (לא כולם, הרעש מחק חלק); בחשד מקרי כמעט אף אחד.
מהאות לספקטרוגרמה
מה עושים כאן. מחליפים את ייצוג ההקלטה, מרשימת דגימות של עוצמת לחץ האוויר כפונקציה של הזמן, לרשימת עוצמות של תדרים. מחלקים את החלפת הייצוג לחלונות קצרים בזמן, שהרי תדר מסוים אינו מופיע לאורך זמן.
ההקלטה, כפי שהיא יוצאת מהמיקרופון, היא רשימה ארוכה של מספרים: לחץ האוויר בכל רגע (בפרק על מהעולם אל הדאטה). בגרף שלה לאורך הזמן, השורה העליונה באיור, רואים מתי הצליל חזק ומתי חלש, ולא רואים אילו תווים נוגנו. ביחידה 1 ראינו שכל צליל הוא צירוף של גלי סינוס בתדרים שונים, והתמרת פורייה מוצאת את הצירוף: היא מקבלת קטע של דגימות ומחזירה, לכל תדר, כמה ממנו יש בקטע. זה ייצוג אחר של אותו קטע, לא לפי זמן אלא לפי תדר.
אבל שיר אינו תדר אחד לאורך זמן: תו נכנס, מחזיק רגע ונעלם. לכן חותכים את ההקלטה לחלונות קצרים, חלון אחרי חלון, ומחשבים את התמרת פורייה של כל חלון בנפרד (החישוב המהיר שלה נקרא FFT, ושיר שלם לוקח לו שבריר שנייה). מסדרים את התוצאות זו ליד זו, חלון ליד חלון, ומקבלים את הספקטרוגרמה: תמונה שבה הזמן רץ לרוחב, התדר עולה למעלה, והצבע של כל תא אומר כמה חזק אותו תדר באותו רגע (השורה התחתונה באיור). נסמן ב־[math]\displaystyle{ S[m,k] }[/math] את העוצמה של התדר ה־[math]\displaystyle{ k }[/math] בחלון ה־[math]\displaystyle{ m }[/math]; זה הייצוג שעליו Shazam עובד.
3 שניות מתוך "חתמתי על קבע" (ארז שיינר), מהשנייה ה־8.5, פעמיים אותו צליל. למעלה הדגימות לאורך הזמן: רואים מתי חזק ומתי חלש, ולא יותר. למטה הספקטרוגרמה, בתקריב על התדרים 350–1050 הרץ: הזמן לרוחב, התדר למעלה, וככל שהתא כהה יותר התדר חזק יותר באותו רגע. קו אופקי הוא תדר שמחזיק, צליל שנמשך; קו שמתעקל הוא תו שמשתנה.
מפת הכוכבים
מה עושים כאן. זורקים כמעט הכול. מהתמונה נשארות רק הנקודות הבולטות, השיאים המקומיים, בלי העוצמה שלהן. זה מה שעמיד לרעש.
הגדרה 1נקודות השיא
יהיו [math]\displaystyle{ \Delta_m,\Delta_k\in\mathbb N }[/math] ו־[math]\displaystyle{ P\in\mathbb N }[/math]. נקודה [math]\displaystyle{ (m,k) }[/math] היא שיא מקומי של [math]\displaystyle{ S }[/math] אם [math]\displaystyle{ S[m,k]\ge S[m',k'] }[/math] לכל [math]\displaystyle{ |m'-m|\le\Delta_m }[/math] ו־[math]\displaystyle{ |k'-k|\le\Delta_k }[/math]. מפת הכוכבים של [math]\displaystyle{ x }[/math] היא קבוצת השיאים המקומיים, כאשר בכל מסגרת נשמרים לכל היותר [math]\displaystyle{ P }[/math] השיאים בעלי [math]\displaystyle{ S }[/math] הגדול ביותר (קריטריון הצפיפות של המאמר). נקודה במפה היא זוג [math]\displaystyle{ (t,f) }[/math] של מסגרת ותדר, בלי העוצמה.
אותה ספקטרוגרמה, ועליה השיאים: 18 תאים שכל אחד חזק מכל סביבתו ([math]\displaystyle{ \pm0.26 }[/math] שניות, [math]\displaystyle{ \pm47 }[/math] הרץ) ועוצמתו לפחות עשירית מהחזק ביותר ברצועה. למטה מפת הכוכבים: אותן נקודות, באותם מקומות, בלי העוצמה ובלי כל השאר. זה כל מה שנשמר מהשיר.
המאמר מנמק: שיא נשאר שיא גם אחרי סינון ואחרי הוספת רעש בינוני (הרעש צריך לעלות על השיא כדי למחוק אותו, ושיאים הם בהגדרה הנקודות הגבוהות), ושיא בספקטרוגרמה הוא בקירוב "ליניארי": כשמוסיפים שני צלילים, שיאי כל אחד מהם מופיעים בסכום. קריטריון הצפיפות מבטיח שגם קטע שקט במוזיקה יתרום נקודות.
הניחוש הטבעי: להשוות את מפות הכוכבים
אפשר לשים את מפת ההקלטה על מפת השיר כשקף, להזיז עד שהנקודות מתלכדות, ולספור. זה נכון ואיטי: לכל שיר ולכל היסט אפשרי צריך לספור התלכדויות, ונקודה בודדת, 9 סיביות של תדר, מתלכדת במקרה עם המון נקודות במסד. הצעד הבא של המאמר מציג אלגוריתם חיפוש יעיל הרבה יותר, בעזרת הקשרים בין זוגות של נקודות.
מילים: זוגות של נקודות
מה עושים כאן. כוכב אחד אינו מזהה שיר. לוקחים שני כוכבים, כוכב וכוכב שבא אחריו, וזה זוג; כל זוג הוא מילה אחת שאפשר לחפש בטבלה, והזוגות ששני כוכביהם של השיר הם שמזהים אותו מתוך הרעש.
בפאב ההקלטה אינה השיר לבדו: על מפת הכוכבים של השיר יושבות המפות של כל מה שנשמע סביב. באיור הבא מונחות זו על זו מפות הכוכבים של שלושה שירים, "חתמתי על קבע" ושני שירים אחרים, באותו קטע ובאותו תקריב כמו קודם. המפה של השיר שלנו היא בדיוק זו מהאיור הקודם; השאר של האחרים, ואין על הכוכב שום סימן למי הוא שייך. כוכב בודד, תדר ברגע מסוים, גם לא אומר כלום: אותו תדר מופיע בהרבה שירים. מה שמייחד שיר הוא הסדר: אחרי הכוכב הזה, במרווח הזה, בא הכוכב ההוא.
לכן עובדים בזוגות. בוחרים כוכב כעוגן, ומצרפים אליו כל אחד מהכוכבים הבאים אחריו בזמן, עד מרחק קבוע קדימה: הקווים הדקים שיוצאים מהעוגן באיור. רוב הזוגות האלה הם זבל, כוכב של השיר עם כוכב של שיר אחר, וזוג כזה לא יופיע באף שיר במסד. אבל זוג אחד, העוגן עם הכוכב הבא של השיר עצמו, הקו הבולט, הוא בדיוק מה שמופיע בשיר שבמסד: אותם שני תדרים ואותו מרווח זמן. הזוג הזה הוא שמזהה את השיר מתוך הערבוב, וכך גם כל זוג אחר ששני כוכביו הם של השיר.
למעלה: הספקטרוגרמה של שלושה שירים שמתנגנים יחד, "חתמתי על קבע" ושני שירים אחרים (Hava Nagila ו־The House of the Rising Sun) באותה עוצמה, באותו קטע ובאותו תקריב כמו קודם; כך נשמע הפאב, ועליו מסומנים כל הכוכבים של שלוש המפות. למטה: איחוד של שלוש מפות הכוכבים, כל אחת מחושבת לשיר שלה לבדו: המפה של "חתמתי על קבע" בדיוק כפי שהיא באיור הקודם, ואיתה המפות של שני האחרים, 56 כוכבים יחד; המקרא אומר מי של מי, אבל על הכוכב עצמו אין שום סימן. כוכב אחד של השיר נבחר כעוגן, והקווים הדקים יוצאים ממנו אל 10 הכוכבים הבאים אחריו בזמן: אלה הזוגות שלו. הקו הבולט הוא הזוג עם הכוכב הבא של השיר עצמו: זוג כזה נמצא גם בשיר שבמסד, והוא שמזהה אותו מתוך הערבוב.
הגדרה 2אזור המטרה; גיבוב; טביעת אצבע
יהיו [math]\displaystyle{ T_z,F_z,F\in\mathbb N }[/math]. לנקודה [math]\displaystyle{ (t_1,f_1) }[/math] במפת הכוכבים, אזור המטרה הוא קבוצת הנקודות [math]\displaystyle{ (t_2,f_2) }[/math] במפה עם [math]\displaystyle{ t_1<t_2\le t_1+T_z }[/math] ו־[math]\displaystyle{ |f_2-f_1|\le F_z }[/math], ומתוכן לוקחים את [math]\displaystyle{ F }[/math] הראשונות בזמן (מקדם הפריסה, fan-out). לכל נקודה כזאת, הגיבוב של הזוג הוא השלשה
וטביעת האצבע של [math]\displaystyle{ x }[/math] היא אוסף הזוגות [math]\displaystyle{ (h,t_1) }[/math] על פני כל הנקודות [math]\displaystyle{ (t_1,f_1) }[/math] במפה.
הזוג הבולט מהאיור הקודם, במספרים: העוגן במסגרת [math]\displaystyle{ t_1=5 }[/math] ובתדר [math]\displaystyle{ f_1=76 }[/math] (0.16 שניות, 594 הרץ), והכוכב הבא של השיר במסגרת [math]\displaystyle{ t_2=17 }[/math] ובתדר [math]\displaystyle{ f_2=61 }[/math] (0.54 שניות, 477 הרץ). הגיבוב שלו הוא [math]\displaystyle{ h=(f_1,f_2,t_2-t_1)=(76,61,12) }[/math], והזמן [math]\displaystyle{ t_1=5 }[/math]; המאמר כותב [math]\displaystyle{ [f_1:f_2:\Delta t]:t_1 }[/math]. אותו [math]\displaystyle{ h }[/math] בדיוק יוצא מהשיר שבמסד, כי שני התדרים והפרש הזמן אינם תלויים במקום שבו ההקלטה התחילה.
[math]\displaystyle{ h }[/math] אינו תלוי ב־[math]\displaystyle{ t_1 }[/math] עצמו, רק בהפרש הזמנים; זו הנקודה. במאמר [math]\displaystyle{ f_1,f_2 }[/math] הם 10 סיביות כל אחד ו־[math]\displaystyle{ t_2-t_1 }[/math] עוד 10, ואפשר לארוז את [math]\displaystyle{ h }[/math] במספר שלם של 32 סיביות; עם [math]\displaystyle{ F=10 }[/math] לכל נקודה יש כ־10 גיבובים.
הגדרה 3מסד הנתונים
בהינתן שירים [math]\displaystyle{ x^{(1)},\dots,x^{(S)} }[/math], מסד הנתונים הוא טבלת גיבוב שמתאימה לכל ערך גיבוב [math]\displaystyle{ h }[/math] את רשימת הזוגות [math]\displaystyle{ (s,t_1) }[/math] של כל הופעה של [math]\displaystyle{ h }[/math] בטביעת האצבע של השיר [math]\displaystyle{ s }[/math] בזמן [math]\displaystyle{ t_1 }[/math]. הטבלה נבנית פעם אחת: כל שיר מעובד רק כשהוא נכנס למסד, ובזמן החיפוש אף שיר לא מעובד מחדש.
החיפוש
את ההקלטה מעבדים כמו שיר ומוצאים את הכוכבים שלה. כל כוכב בהקלטה הוא עוגן, ולכל עוגן בודקים אם יש באזור המטרה שלו כוכב שהזוג שלו עם העוגן מופיע באחד השירים במסד. כל בדיקה כזאת היא פנייה אחת לטבלה, לפי הגיבוב של הזוג, וזמנה אינו תלוי במספר השירים במסד. כשאחד משני הכוכבים בא מהרעש, הזוג בדרך כלל לא יימצא, ולפעמים יימצא במקרה בשיר שאינו קשור להקלטה.
זוג שנמצא הוא חשד: שיר מסוים, והמקום בשיר שבו ההקלטה מתחילה, לפי הפרש הזמן בין הופעת הזוג בשיר להופעתו בהקלטה. את החשד בודקים על הכוכבים הבאים: כמה מהכוכבים של השיר החשוד, מאותו מקום והלאה, מופיעים גם בהקלטה, באותו תדר ובאותו זמן יחסית לתחילתה. בשיר הנכון רבים (לא כולם, הרעש מחק חלק); בחשד מקרי כמעט אף אחד. התשובה היא השיר שעבר את הסף. אם לא היה אף חשד, או אף שיר לא עבר את הסף, אז לא זוהה שיר.
החיפוש כתרשים זרימה: מההקלטה אל השיר, או אל "לא זוהה שיר" כשאף זוג של עוגן לא נמצא בטבלה, או כשלחשד מעט מדי מהכוכבים הבאים בהקלטה.
טביעת אצבע
מקור מרכזי.Wang (2003), An Industrial-Strength Audio Search Algorithm, למעלה מ־1,500 ציטוטים.
הבעיה. לזהות שיר מתוך הקלטה של שניות אחדות, רועשת, מתוך מסד של מיליוני שירים, בתוך שנייה.
הרעיון המרכזי. לשמור מכל שיר רק את השיאים של הספקטרוגרמה שלו, ולקודד אותם בזוגות: שני תדרים והפרש זמן.
איך הרעיון פותר את הבעיה. שיאים שורדים רעש, ולכן זוגות של השיר מופיעים גם בהקלטה; זוג הוא מילה נדירה, ולכן חיפושו בטבלת גיבוב מחזיר מעט חשודים, בפנייה אחת לזוג; והחשד נבדק מול הכוכבים הבאים של השיר.
מה לזכור. ייצוג מושכל שאנשים עיצבו: שומרים רק את מה שבצליל שורד רעש, וזורקים את כל השאר.
