מי שמביט בי מהצד יודע מי אני
10/09/2020
עיבוד תמונות דיגיטליות כולל ביצוע פעולות מתמטיות על פיקסלים בודדים, בין השאר לטובת ״הבנת״ תוכן התמונה, כמו מציאת שפות של עצמים או אזורים מעניינים אחרים. בפוסט זה נסביר על שיטה מתמטית כזו המאפשרת לבצע התאמה והשוואה בין מספר תמונות של אותה הסצינה, וכיצד היא משמשת ליצירת תמונות פנורמה ושחזור סצנות תלת ממדיות.
היכולת של מערכות ממוחשבות להבין תמונות או סרטי וידאו הופכת ליותר ויותר חשובה ליישומים רבים, ממכוניות אוטונומיות, לזיהוי פנים, ועוד. יכולת זו תלויה, בין השאר, ביכולת לאתר עצם מסויים בכמה תמונות (או פריימים), להסיק שמדובר באותו העצם, ומכאן להפיק מידע על התכונות שלו ומיקומו בסצינה המצולמת. זאת אומרת, עלינו לתכנן אלגוריתם שמסוגל להתאים בין התמונות השונות כך שניתן יהיה ״לחבר״ את המידע מהן לכלל הבנה. אך אם ניקח, למשל, שתי תמונות שבהן מופיע אותו העצם, באופו כללי הוא יופיע במיקומים, זוויות ותנאי תאורה שונים בכל אחת מהן. מאחר ואנחנו לא יודעים מראש מהם העצמים ואיך הם משתנים בין תמונה לתמונה, על האלגוריתם תחילה למצוא במציאת אזורים "מעניינים" בכל תמונה בפני עצמה. מה הם אזורים מעניינים? הם אלו שמופיעים בהם שינויים חדים בערכים המספריים של הפיקסלים (המייצגים צבע ועוצמה, ראו פוסט קודם שלנו על הבנת תמונות דיגיטליות [1]). לדוגמא, נסתכל על תמונה של קובייה הונגרית, וננסה לסמן אזורים בולטים בתמונה שיאפשרו לנו למצוא את הקובייה בתמונה אחרת. פיקסל הנמצא באמצע ריבוע אדום בקובייה, למשל, יהיה מוקף מכל הכיוונים בפיקסלים אדומים נוספים הדומים לו, ולכן יהיה ״לא מעניין״. לעומתו, פיקסל בפינת הריבוע האדום יהיה מוקף בפיקסלים בצבעים אחרים (גבולות של תאים בקובייה הונגרית צבועים בשחור בדרך כלל). ולכן אזור זה יכיל מידע שימושי רב יותר. בסופו של דבר, ניתן יהיה ניתן לזהות אזור עם מאפיינים דומים בתמונה נוספת של הקוביה בקלות יחסית. דוגמא לאלגוריתמים המזהים פינות של עצמים, הוא אלגוריתם בשם האריס [2]. מאחר ופינות של עצמים הן אזורי עניין משמעותיים מאוד מבחינה חזותית, אלגוריתם זה מסייע לנו לאתר את אותו העצם בתמונות שונות בעזרת איתור הפינות שלו.
דוגמא לזיהוי פינות (מסומנות באדום) באמצעות אלגוריתם האריס. מימוש: צבר דולב.לאחר שנמצאו אזורי העניין בכל תמונה, יש צורך לאפיין אותם בצורה מספרית כלשהי, כזו שמחשב יוכל להשתמש בה על מנת למצוא אזור דומה בתמונה אחרת [3]. דבר זה יכול לשמש הן להבנת המבנה התלת מימדי של העצם, או למצוא חפיפה או המשך של אותה הסצנה, לדוגמא, כאשר רוצים לחבר תמונות ליצירת תמונת פנורמה. לשם מציאת אותם איזורי עניין בכמה תמונות, קיימים אלגוריתמים הנקראים דסקריפטורים (מהמילה ״תיאור״ באנגלית). כשהם מופעלים על תמונה, הם מעניקים כל איזור עניין ערכים מספריים המתארים את עוצמות וכיווני שינויי הצבע באיזור זה. לדוגמא, מעבר בין פיקסל צהוב לפיקסל שחור מתאפיין בשינוי גדול, ואילו מעבר בין פיקסל אדום לפיקסל ורוד מתאפיין בשינוי קטן, בגלל הקירבה בין שני הצבעים [4].ישנם מספר דסקריפטורים מוכרים, ואחד הנפוצים מביניהם [5] נקרא SIFT (Scale Invariant Feature Transform). התהליך המבוצע באלגוריתם זה מתרחש במרחב מתמטי דמיוני, מעין מפה בה כל איזור עניין שנמצא בתמונה ממקומם בנקודה אחרת, על פי התכונות שלו, או יותר נכון, על פי אופי השינויים החדים שהוא מכיל. שני אזורים דומים יהיו קרובים במפה זו, ואילו אזורים שונים יפלו במרחקים גדולים זה מזה. כדי למצוא אזורי עניין שהם אותו עצם פיזי בעולם, דמיינו שיש לכם מפה כזו ויש עליה נקודה, המייצגת איזור עניין מסויים, נניח אותה פינה בקוביה ההונגרית. בנוסף לנקודה זו, פזורות במפה עוד נקודות, כל אחת מייצגת איזור עניין אחר שהאלגוריתם מצא בתמונה. אתם מותחים קווים בין הנקודה שלכם לבין שאר הנקודות ומחפשים את המרחק הקצר ביותר, או את הנקודה הקרובה ביותר לנקודה שלכם - ככל הנראה שמדובר באותו העצם (או חלק של עצם). התהליך החישובי הקורה באלגוריתמים מסוג זה הוא מעט יותר מורכב, שכן הוא כרוך בחיפוש נקודות קרובות לא במפה דו מימדית, אלא במרחב בעל ממדים רבים, כאשר כל ממד מייצג סוג מידע אחר על איזורי עניין בתמונות. יש לציין כי לא כל איזורי העניין יופיעו בכל התמונות שביניהן אנו מבצעים התאמה, ועל כן נדרש ערך סף לקירבה בין הנקודות - מרחק גדול ממרחק מסויים יסמן לנו כי הנקודות אולי דומות במקצת אבל אינן מתאימות ואינן מייצגות את אותו העצם במרחב האמיתי שמחוץ לתמונה.
דוגמא למימוש האלגוריתם לשם הבנה של עצם תלת מימדי מופיע בראש כתבה זו. דוגמא של מציאת חפיפה בין שתי תמונות לשם יצירת תמונת פנורמה מצורפת למטה.
מציאת נקודות עניין חופפות בשתי תמונות סמוכות בעזרת אלגוריתם SIFT. מימוש: צבר דולב.
בפוסט זה תיארנו כיצד ניתן לתאר אזורי עניין בתמונות באופן מתמטי כך שנוכל להשוות ולהתאים בין אזורי עניין שונים בתמונות שונות. בדרך זו ניתן לאפיין עצם מסוים בתמונה בעזרת גבולותיו, הגיאומטריה הייחודית שלו וכיצד הוא מתבלט על גבי רקע התמונה. אפיון זה מאפשר את איתור העצם בתמונות דומות ואף חיבורן לתמונת פנורמה או אפילו ליצור מודל תלת ממדי של העצם בעזרת צילומו ממספר רב של זוויות.
[1] לשים גבולות בתמונות, מתוך מדע גדול בקטנה
[2] הסבר כיצד עובד אלגוריתם האריס (Harris)
[3] הסבר נוסף על משפחת האלגוריתמים הנקראת דסקריפטורים
אלגוריתמאי וחוקר ראייה ממוחשבת וגיאומטריה חישובית, בוגר תואר ראשון ושני בהנדסת מכונות בטכניון. בימים אלו עוסק בפיתוח אלגוריתמים לעיבוד תמונה.
מעצב גרפי, מאייר, צלם ועורך וידאו
