משתמשת:NA 2013/טיוטה

זיהוי וגילוי עצמים

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

משימות עיקריות

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

תהליך הפתרון

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

אלגוריתמים

• מודל Deformable Parts
• אלגוריתמים המכילים סגמנטציה
• מודלים המכילים את ההקשר (context) של העצם בזמן הגילוי

סטי בדיקה

• PASCAL VOC - The PASCAL Visual Object Classes

סט זה מכיל בגרסתו האחרונה (2012) 11,530 תמונות לאימון וולידציה, המכילות 27,450 עצמים מסומנים ומתוייגים מ-20 קטגוריות. קטגויות האובייקטים בסט זה הם: אדם, ציפור, חתול, פרה, כלב, סוס, כבשה, מטוס, אופניים, סירה, אוטובוס, רכב, אופנוע, רכבת, בקבוק, כסא, שולחן אוכל, עציץ, ספה ומסך טלויזיה/מחשב. בין השנים 2005 ל-2012 נערכו תחרויות על בסיס הסט, והוחרזו מנצחים בשלושה אתגרים עיקריים: זיהוי עצמים, גילוי אובייקטים וסגמנטציה. סט זה משמש לאימון ובדיקה של אלגוריתמים רבים ונחשב לסטנדרט בתחום.

ראו גם

• ראייה ממוחשבת
• גרפיקה ממוחשבת
• סגמנטציה (מחשוב)
• מודל bag of words בראייה ממוחשבת
• Histogram of oriented gradients

הערות שוליים

אלגוריתם RANSAC

באנגלית RANdom SAmple Consensus, הינה שיטה איטרטיבית להערכת פרמטרים של מודל מתמטי מתוך סט דגימות נתון, המכיל גם outliers (דוגמאות שאינן מגיעות מהמודל). האלגוריתם אינו דטרמינסטי, מכיוון שהפתרון יהיה נכון רק בהסתברות מסויימת, העולה ככל שמספר האיטרציות גדל. האלגוריתם פורסם לראשונה ע"י Fischler and Bolles בשנ

ת 1981.

ההנחה המרכזית של האלגוריתם, היא שסט הדוגמאות מכיל inliers , כלומר דוגמאות המתאימות למודל מתמטי, וכן מכיל outliers שאינן מתאימות למודל. הנחה נוספת היא שבהינתן מספר קטן של דוגמאות השייכות למודל המתמטי, ניתן למצוא את הפרמטרים המתאימים לו בצורה טובה ובהתאמה לדוגמאות הנתונות.

האלגוריתם

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

שלב 1

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

שלב 2

המודל שחושב בשלב 1 נבדק על כלל סט הדוגמאות. עבור כל דוגמא, נקבע אם היא inlier או outlier ע"פ התאמתה למודל. ההתאמה צריכה להיות במסגרת השגיאה שהוגדרה מראש.

חוזרים על שני השלבים באופן איטרטיבי, עד שמגיעים למודל שעבורו מספיק דוגמאות נחשבות inliers. הדוגמאות שנחשבות inliers נקראות "סט הקונסנזוס".

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

דוגמא

דוגמא פשוטה לעבודת האלגוריתם היא התאמה של קו ישר בדו-מימד עבור סט של נקודות (x,y). כפי שניתן לראות באיורים, חלק מהנקודות יושבות על קו (inliers) וחלק לא (outliers). שערוך הקו בשיטת least squares תוביל לפתרון לא אופטימלי עבור נקודות ה-inliers מכיוון שהיא תנסה להתאים קו לכל הנקודות הנתונות, כולל אלו שאינן שייכות לקו הישר כלל. באמצעות הRANSAC, יחושב מודל באמצעות נקודות inliers בלבד (בהינתן שההסתברות לבחירה של נקודות inlier גבוה מספיק).

שימושים

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

הערות שוליים

קטגוריה: מדעי המחשב