GraphVid: It Only Takes a Few Nodes to Understand a Video, סקירה

סקירה זו היא חלק מפינה קבועה בה אנחנו סוקרים מאמרים חשובים בתחום ה-ML/DL, וכותבים גרסה פשוטה וברורה יותר שלהם בעברית. במידה ותרצו לקרוא את המאמרים הנוספים שסיכמנו, אתם מוזמנים לבדוק את העמוד שמרכז אותם תחת השם deepnightlearners.

לילה טוב חברים, היום אנחנו שוב בפינתנו deepnightlearners עם סקירה של מאמר בתחום הלמידה העמוקה. היום בחרנו לסקירה את המאמר שנקרא:

GraphVid: It Only Takes a Few Nodes to Understand a Video

פינת הסוקר:  

     המלצת קריאה מאברהם ומייק: מאמר מומלץ למי שעוסק בתחום עיבוד וידאו וגם כן לחסידי GNNs.

     בהירות כתיבה: גבוהה 

     ידע מוקדם: נדרשת הבנה בסיסית בעיבוד תמונה ווידאו. גם ידע בסיסי ברשתות נוירונים על גרפים נחוצה להבנת המאמר

   יישומים פרקטיים אפשריים: ניתן להשתמש בארכיטקטורה שהוצעה במאמר בתור backbone לחילוץ מאפיינים חזקים מווידאו עבור מגוון משימות downstream

פרטי מאמר:

     לינק למאמר: זמין להורדה

     לינק לקוד: לא פורסם

    פורסם בתאריך: 20.07.22, בארקיב.

    הוצג בכנס: ECCV2022

תחומי מאמר:

• עיבוד וידאו
• רשתות נוירונים על גרפים (GNNs)
  

  ---

מבוא: 

בתקופה האחרונה אנו עדים לעלייה ניכרת בדרישה לפיתוח אלגוריתמים יעילים לעיבוד וידאו כגון תיוג (של אנשים או עצמים) בוידאו, זיהוי פעולה או זיהוי אנומליות בוידאו. סיבה לעלייה זו היא הפופולריות הרבה של הפורמט הזה, הרי כל יום מועלים לאינטרנט מיליוני סרטונים ברשתות החברתיות בלבד. הגישות המודרניות לעיבוד וידאו מבוססות ברובן על רשתות נוירונים עמוקות. מאחר וודיאו הוא למעשה סדרה של תמונות (פריימים) הארכיטקטורות הסטנדרטיות שהפגינו ביצועים גבוהים במשימות עיבוד תמונה (למשל רשתות קונבולוציה) עברו מתיחת פנים ו״נרתמו״ למשימה זו. באופן טבעי, הקרנל הדו-ממדי שנלמד לזהות מאפיינים בתמונה, הורחב לקרנל תלת ממדי, כאשר בכל פעם הוא עובר על מקטעי תמונות מכמה פריימים עוקבים. חלופה אחרת לעיבוד וידאו הינה שימוש בטרנספורמרים, וגם בו ה-attention מתבצע בכל פעם על אזורי תמונות מכמה פריימים עוקבים. אחד האתגרים המשמעותיים בשימוש ברשתות נוירונים מסוג זה למשימות עיבוד וידאו היא העומס החישובי, כיוון שאימון ואבלואציה של קרנלים תלת-ממדיים או טרנספומרים הינם יקרים בכמות חישובים, וממילא גם ב-latency. אתגר זה העלה את הצורך בפיתוח גישות אלטרנטיביות לעיבוד וידאו, ואכן יש לא מעט עבודות המשתמשות ברשתות קונבולוציה רגילות (2D), ומבצעות את המידול הטמפורלי בדרכים אחרות וחסכוניות יותר תוך ניסיון לשמור על רמת דיוק כמה שיותר קרובה לזו של הרשתות הכבדות יותר.

הרעיון המרכזי של המאמר: 

המאמר שנסקור היום מציע שיטה להפקת פיצ'רים מוידאו, על ידי מידול וידאו כגרף ואז שימוש ברשתות נוירונים על גרפים (Graph Neural Network: GNN). ישנן לא מעט רשתות שמספקות ביצועים טובים בניתוח גרפים, והחידוש העיקרי כאן הוא כיצד לנסח וידאו כגרף שיכול לחסוך חישובים. באופן הכי פשטני ניתן לקחת כל פיקסל ולמדל אותו כקודקוד, וכל שני פיקסלים סמוכים לחבר בקשת. לאחר מכן יש להוסיף קשתות בין כל שני פיקסלים בעלי אותו אינדקס אך בפריימים שונים, ובכך נקבל גרף תלת ממדי המחבר בין כל תמונה לעצמה ובין כל שתי תמונות עוקבות. גישה זו למעשה יוצרת גרף המכיל חיבוריות מרחבית ועתית(טמפורלית) בו זמנית, ואף שהיא יכולה לעבוד טוב, היא ודאי לא תוכל לחסוך חישובים, כיוון שהחישובים מתבצעים על כל הפיקסלים בוידאו. בכדי להשתמש ברעיון זה ויחד עם זאת לחסוך בחישובים, המחברים מבצעים שלב מקדים, בו כל פריים מהוידאו מחולק לאוסף של Superpixels, כאשר כל Superpixel מייצג אוסף של פיקסלים הדומים אחד לשני. שלב זה למעשה מבצע דחיסה של התמונה, ובהמשך נסביר כיצד בדיוק תהליך זה מתבצע ומדוע הוא מצליח להיות יעיל. לאחר מכן בונים גרף המחבר בין סופרפיקסלים של כל פריים ובין סופרפיקסלים של פריימים עוקבים, כאשר מבחינים בין קשתות מרחביות המחברות סופרפיסקלים מאותו פריים לבין קשתות עתיות המחברות סופרפיסקלים מפריימים עוקבים. בשלב האחרון מגדירים רשת נוירונים מעל הגרף, ומשתמשים בה לצורך ביצועי משימת קצה (למשל Action Recognition). המחברים ניסו כמה ארכיטקטורות של GNN כמו GCN, GAT ואף גישה המשלבת Node Embedding, והם מראים הצלחה גדולה בחיסכון של חישובים תוך שמירה על רמת דיוק של הרשתות המובילות.

בקצרה ניתן לומר שהרעיון מחולק לשלושה חלקים:

• דחיסת הפריימים באמצעות ייצוג של סופרפיקסלים
• יצירת הגרף המייצג את הוידאו
• הפעלת רשת נוירונים על הגרף עבור משימת קצה

כעת נעבור על כל אחד מהחלקים באופן מפורט.

הסבר מעמיק הרעיון העיקרי:  

ייצוג תמונה באמצעות סופרפיקסלים:

השלב הראשון הינו דחיסת המידע של הפריימים באמצעות סופרפיקסלים. הרעיון אינו עיקר המאמר והמחברים מסתמכים על שיטה קיימת הנקראת SLIC, ועל כן נזכיר אותו רק בקצרה. המטרה כאמור היא לאפשר ייצוג של פריים באמצעות הרבה פחות פיקסלים מהמקור. כאשר מחברים אזורים דומים ומייצגים אותם על ידי ערך יחיד (שהוא נניח הממוצע שלהם), ניתן לקבל תמונה קצת מרוחה אך עם זאת היא שומרת באופן די טוב את התוכן שלה. אלגוריתם SLIC מאפשר לבחור את מספר הסופרפיקסלים הרצוי, ולאחר מכן משתמש בהיוריסיטקה די פשוטה המאחדת פיקסלים דומים ומייצגת את התמונה המקורית על ידי אותו מספר סופרפיקסלים שהמשתמש בחר.

בניית הגרף:

לאחר שדחסנו את הפריימים וקיבלנו ייצוג שלהם באמצעות סופרפיקסלים, נוכל להגדיר באמצעותם את הגרף הרצוי המייצג את הוידאו השלם. בפתיחה הזכרנו בקצרה שכל סופרפיקסל מיוצג בגרף על ידי קודקוד, ושני סופרפיקסלים סמוכים (באותו פריים או בפריימים עוקבים) מחוברים באמצעות קשת. כעת נרחיב על ההגדרות המדויקות של חלקי הגרף:

למעשה, כל קודקוד (=סופרפיקסל) מייצג פאץ' של פריים, והוא מקבל כערך התחלתי את הצבע הממוצע של הסופרפיקסל. באופן פורמלי: כל סופרפיקסל מאותחיל על ידי וקטור פיצ'רים R_t,i.c, המהווה הצבע הממוצע של הסופרפיקסל כאשר t הוא מספר הפריים, i מייצג את האינדקס המרחבי של הסופרפיקסל בפריים (בקוארדינטות קרטזיות, כלומר הוא מורכב מ-(x,y)).

לאחר שבנינו את כל הקודקודים, נוכל להגדיר את הקשתות, וכאמור יש שני סוגים של קשתות: קשתות מרחביות (spatial) וקשתות טמפורליות. הקשתות המרחביות מוגדרות באמצעות המרחק המרחבי הבא בין שני סופרפיקסלים t_p ו- t_q בפריימים i ו- j:

כאשר R_t,i.x ו- R_t,i.y מסמנים את הקואורדינטות x ו- y של הסנטרויד (centroid) של הסופרפיקסל ו- H,W הם המימדים של תמונה. במילים אחרות, d מתאר את המרחק (במישור התמונה) של הסופרפיקסלים. הקשתות המרחביות מוגדרות רק לסופרפיקסלים(קודקודים) מאותו פריים t; הקודקודים השייכים לפריימים שונים לא מחוברים בקשתות מרחביות. שימו לב שהמרחק המרחבי הינו אינווריאנטי לסיבוב ולהזזה של פריימים. 

הקשתות הטמפורליות מוגדרות באופן די דומה לקשתות המרחביות, אלא שכעת המרחק הנמדד הוא בין סופרפיקסלים מפריימים עוקבים ולא מאותו פריים. המרחק העתי הוא די דומה למרחק המרחבי אך במקום הקואורדינטות של הסופרפיקסל מחשבים את מרחק L2 בין צבעם הממוצעים R_t2,i.c ו- R_t1,j.c. המאמר בוחר להוסיף קשת בין שני קודקודים i ו-j השייכים לפריימים סמוכים t ו-t+1 רק אם המרחק L2 בין הצבעים הממוצעים שלהם R_t,i.c ו-R_t+1,j.c הוא קטן מהסף [d_proximity ∈ (0, 1 (הייפרפרמטר):

הפקת פיצ'רים של וידאו מהגרף:

אחרי שבנינו את הגרף נותר לנו לבנות רשת נוירונים על גרף זה שבאמצעתה נבנה את הפיצ'רים של הוידאו, וכאן המחברים מסתמכים על הארכיטקטורות המרכזיות הקיימות בתחום (למי שלא מכיר את עקרונות הבסיסיים של GNN מומלץ לקרוא את הבלוג המצוין הזה). הגישה הבולטת ביותר בתחום של GNN היא message passing, והיא מאפשרת העברת מידע בין הקודקודים/הקשתות של הגרף בצורה איטרטיבית ובכך לעדכן את הפיצ'רים של כל אלמנט בגרף על בסיס אינפורמציה בחלקים אחרים בגרף.

• הגישה הפשוטה ביותר (GCN) – עבור כל קודקוד מבצעים אגרגציה של המידע מכל השכנים, מכפילים במשקל נלמד ומעדכנים את הפיצ'ר וקטור של אותו קודקוד.
• GAT – רעיון דומה ל-GCN, אלא שבתהליך האגרגציה מבצעים Attention בין ייצוגים של כל זוג קודקודים סמוכים ומעבירים מידע מקודקוד לקודקוד אחרי שכופלים את הייצוג שלו באותו מקדם Attention שחושב.
• RGCN – שימוש גם במידע על הקשתות. בגרף במאמר יש שני סוגי קשתות, ויש משמעות לסוג הקשת המחברת בין קודקודים. טבעי ששימוש במידע זה ישפר את ביצועי הרשת.

המודלים השונים מבצעים את העדכון בכל שכבה באופן די דומה, על בסיס הנוסחה הבאה:

h_i^(l) הינו סט הפיצ'רים של קודקוד i בשכבה מספר l של ה-GNN ו- N_i^r הינו סט השכנים של קודקוד i עבור יחס שכנות (relation) r. עבור GAT יש הוספה של מקדם α_i,j המחושב עבור כל זוג קודקודים שכנים, ועבור RGCN מתווסף גם משקל התלוי בפיצ'רים של הקשתות המחברות בין הקודקודים.

כמו בכל GNN, בכדי לבצע את משימת הקצה (שבמקרה של המאמר היא זיהוי הפעולה המתרחשת בוידאו) לוקחים את הפיצ'רים של השכבה האחרונה של GNN ומקבלים באמצעותם החלטה.

ניתוח תוצאות:  

המשימה עליה אומן המודל היא זיהוי פעולה בוידאו (action recognition), והמחברים משווים את עצמם לרשתות SOTA על שני דאטהסט – Kinetics-400 ו-Charades. ראשית, המודל שלהם הוא הרבה יותר קומפקטי מבחינת מספר פרמטרים. בנוסף, עם הרבה פחות FLOPs ביחס למודלים אחרים ניתן להגיע לרמת accuracy תחרותית, שמשתווה ואף עוקפת את מרבית המודלים. אמנם יש מודלים שמגיעים לרמת דיוק טובה יותר, אך הם דורשים הרבה יותר FLOPs.

המחברים מספקים ablation study רחב הבא לבחון פרטים שונים וחשובים במודל, כמו למשל סוג ה-GNN, מספר הסופרפיקסלים והשפעתם על הביצועים, שימוש באוגמנטציות שונות ועוד.

ראוי לציין שאמנם כמות החישובים קטנה משמעותית ביחס למודלים אחרים, אך יש לכך מחיר – יש לבצע preprocessing לכל תמונה על מנת לקבל ייצוג שלה באמצעות סופרפיקסלים ובאמצעותם לבנות את הגרף, וזה לוקח זמן. המחברים כמובן מתייחסים לכך ומציגים גרף המראה את זמן הריצה הדרוש ליצרת גרף עבור הוידאו, כתלות במספר הסופרפיקסלים של כל פריים.

סיכום:  

המאמר מציע גישה מעניינת להפקה של פיצ'רים מהותיים מוידאו באמצעות דחיסה של הוידאו באמצעות סופרפיקסלים ובניית GNN בהתבסס על הקשרים המרחביים והעתיים בין הסופרפיקסלים. לאחר מכן ניתן להשתמש בפיצ'רים אלו למגוון משימות downstream.

הפוסט נכתב על ידי מיכאל (מייק) ארליכסון, PhD, Michael Erlihson ואברהם רביב.

מיכאל עובד בחברת הסייבר Salt Security בתור Principal Data Scientist. מיכאל חוקר ופועל בתחום הלמידה העמוקה, ולצד זאת מרצה ומנגיש את החומרים המדעיים לקהל הרחב.

אברהם סטודנט לתארים מתקדמים בתחום של Data Science ועובד בחברת סמסונג. מתעניין בלמידה עמוקה ובראייה ממוחשבת. מחבר ספר על למידת מכונה ולמידה עמוקה בעברית.