עבודת הגמר - אפקה המכללה האקדמית להנדסה בת"א

מערכת עיבוד תמונה למעקב רובוטי

Abstract תמצית

מטרות

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

משימות עיקריות
דגימת תמונה

עיבוד תמונה וזיהוי המטרה

הכוונת הרובוט

שילוב מערכות

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



הפתרון שמומש הוא הפעלת אות Trigger בסיום עיבוד כל תמונה, שיסמן "אור ירוק" לרכישה של התמונה הבאה.

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

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

ראשית, היה צורך לבחור, כיצד יזהה הרובוט העוקב את המטרה בתמונה המתקבלת, ועל סמך זה למצוא שיטה לעקיבה.
הועלו מספר אפשרויות:
אפשרות ראשונה [מקור 8] הייתה האפשרות של חיפוש התנועה, על-פי תמונות ההפרשים (Motion Detection–Some of Absolute Differences), אפשרות זאת נפסלה כבר בשלבים הראשונים של המימוש, כיוון שהמצלמה בפרויקט זה אינה נייחת ולכן תמונת ההפרשים בין שני frames עוקבים, אינה תורמת כל מידע על מיקום המטרה בתמונה. יש לזכור, כי לא רק אובייקט המטרה זז במרקע סטטי, אלא כל התמונה שהמצלמה קולטת משתנה בצורה דינאמית בכל איטרציית זמן. ניתן לבצע שיערוך של תנועת המצלמה, אך שערוך זה קשה במקרה זה מכיוון שזאת תנועה לא מדויקת, בגלל מגבלות הדיוק של מנועי הבקר, וכמו-כן, באופן כללי שערוך כזה הוא בסיבוכיות גבוהה יותר מהפתרון האלטרנטיבי.

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

אפשרות שלישית שהתקבלה על סמך מאמרים רבים [[מקור 12][מקור 13][מקור 14] [מקור 15][מקור 16]], הייתה זיהוי המטרה, על-סמך הצבע שלה. הרעיון היה לדאוג לכך, שהמטרה תהיה בצבע שונה (אך לא בהכרח!) מסביבתה, ו-"כל שיהיה" על הרובוט לעשות, הוא למצוא את הצבע המסוים הזה בתמונה. על מנת להקשות את הזיהוי, הוחלט מראש, שלא ניצור עבור הרובוט הרודף, סביבה מלאכותית (כלומר סביבה בעלת צבע אחיד השונה מזו של המטרה).

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

הכוונת הרובוט
החלטת כוון התנועה של הרובוט, מתקבלת ביחס ישיר לתוצאות החיפוש (מציאה / אי מציאה של המטרה בתמונה הנרכשת). הפקודות האפשריות הנם: תנועה ימינה, תנועה שמאלה, תנועה למעלה, תנועה למטה, עצירה. (האלגוריתם מאפשר הרחבה לדרגת חופש נוספת – סיבוב סביב האובייקט).
הבעייתיות במשימה זו היא השליטה בתנועות הרובוט. במידה והמטרה רחוקה מהמצלמה – כל תנועה קטנה של הרובוט, תגרום למטרה, לצאת מרזולוציות המצלמה ולהפך, כאשר המטרה קרובה למצלמה, תנועה לא מספיק ממושכת, לא תאפשר עקיבה רציפה ויעילה ואף עלולה להסתיים בבריחת המטרה מהרובוט.
מכאן נובעת הנחת יסוד נוספת, בהתייחס למרחק האובייקט הנעקב מהמצלמה/רובוט. מרחק זה יקבע בהתאם למבחני Try and False, שיבוצעו לאחר מימוש האלגוריתם.

הרובוט שהינו יחידת RCX – זהו מחשב קטן, המבוסס על שבב הH8- של היטאצ'י. מעבד שמונה ביט זה, מספק serial I/O , מתמיר אנלוגי לדיגיטאלי וטיימרים, ועליו לקבל פקודות רציפות, לכאורה, המציינות את הכיוון שעליו לנוע ,על-מנת לשמר את מעגל העקיבה.

פעולת "הכוונת הרובוט", הינה פעולה, הדורשת משאבים רבים ועל-כן, נמשכת זמן רב ויקר.
כדי לפתור בעייתיות זו, השתמשתי בשפה חדשה Not Quite C NQC המאפשרת תכנות מתקדם ל-RCX ו"הורדת" התכנה לבקר.
הפתרון, עליו ארחיב בהמשך (בשלב תיאור האלגוריתמים), מבוסס על רעיון של יצירת Events (אירועים) ושליחת הודעה לרובוט, אך ורק כאשר ישנו שינוי כיוון או עצירה, ובכך אנו חוסכים תקשורת IR מיותרת, אלא כשזו נדרשת בלבד.

שילוב מערכות
יש צורך בבניית מערכת אחת, המשלבת מערכות תוכנה וחומרה, בעלות ממשקים ומקצבי עבודה שונים, בהתאם למגבלות טכניות שונות.
על-מנת לאפשר רכישת תמונות ממצלמת USB ותקשורת IR עם רובוט RCX, יש צורך בידע מעמיק בתחום MATLAB™ Integration המאפשר יצירת קשר בין MATLAB לתכניות Processes אחרות.

סקר ספרות ומקורות

תיאור מצב קיים

תחום זה של עקיבה בעזרת מצלמה אחר אובייקטים דינאמיים בסביבה לא מדומה, הביא רבים לבניית פרויקטים הדומים לפרויקט זה. לאחר חיפוש נרחב באינטרנט בכלל ובאתרים אקדמיים בפרט, אחר פרויקטים דומים, ניכר כי רובם נבנו בשני שלבים עיקריים:
1. ניסוי ובחינת אלגוריתם לעיבוד תמונה ייעודי למטרת הפרויקט.
2. קידוד האלגוריתם בשפת תכנות כלשהי (לרוב VC++/C).
מכיוון שבתחום עיבוד התמונה, MATLAB הנה תוכנה בעלת פונקציות רבות ויעילות, מרבית מן הפרויקטים מימשו את השלב הראשון בתוכנה זו.
בניגוד לעבודות ההן, פרויקט זה ייכתב ב-MATLAB מתחילתו - רכישת תמונות ממצלמת USB, ועד סופו – תקשורת עם הרובוט והכוונתו למטרה.
אינטגרציה זו בין מספר ממשקים שונים, מצריכה ידע מתקדם ב-MATLAB וכמו-כן, ניסיון בעבודה מול אובייקטים ActiveX, COM Object.

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

כפתרון, בוצעה העברה של הפיקסלים לקואורדינאטות HSV (איור 4.2), אשר בהם תמצית הצבע נמצאת בקואורדינאטת Hue, ושאר הקואורדינאטות מציינות, שינויים ברוויה (Saturation) ובעוצמת הצבע (Value) [[מקור 17][מקור 18]].

לכן, כאשר נרצה לחפש במרחב זה, אחר צבע ספציפי, תוך התרת שינויי הארה, כל שיהיה עלינו לעשות הוא לחפש טווח צר של ערכים בקואורדינאטת ה-Hue שלו.
חיפוש זה מורכב לביצוע, ויש להגביל את ערכי ה-Saturation וה-Value לערכים כאלה, שבהם עוד יש משמעות לצבע. אם נתבונן בפיקסלים, אשר יש להם ערכי V גבוהים מאוד, או נמוכים מאוד, הרי שערכי ה-H שלהם יהיו מאוד לא יציבים: גם העין האנושית מתקשה להבחין למשל בין כחול וירוק בחדר חשוך, או כשהמשטח שלהם חלק ומחזיר את התאורה אל העין, אשר יוצר אפקט סנוור לבן (ובעצם איבד את ערך ה-H המקורי שלו).

כהשלכה ישירה מכך, באלגוריתם אותו אממש בפרויקט זה, אני אתעלם מערכי Hue באותם אינדקסים, בהם ערכי Saturation או Value (בהתאמה) נמצאים באחד הקצוות הקיצוניים.
בתחילת ריצת התכנית, יקבעו מראש ערכי ה-H שאחריהם יעשה חיפוש, במהלך ריצת התוכנית. רק פיקסלים בעלי ערכי H הללו "חשודים" כחלק מאובייקט המטרה.

בתוכנית זו ישנה הגבלה של ערכי V לערכים שבין: 0.1-0.8 (ערכים מתחת ל0.1 הנמצאים בחלק הצר של החרוט גורמים להתקרבות ערכי ה-H, ערכים מעל 0.8 נוצרים כתוצאה מסנוור וחזרת אור לבן) והגבלה של ערכי S לערכים שמעל 0.25 (איור 4.3).

איור 4.3 תחומי קואורדינטות אפשריים.

כל הנאמר לעיל מתבסס על הניסוי הבא:
בניתי סביבה מדומה, המכילה מספר צבעים שונים וצילמתי אותה בשני מצבים: האחד באור חדר מלא, והשני כאשר האור כבוי (אור פלורוסנט בתדר 60Hz).
היסטוגרמת שתי התמונות נתונה באיור 4.5 וניתן לראות כי הקורלציה ביניהם נמוכה, כאשר מקדם המתאם הינו 0.21


איור 4.4 תמונת הזירה לאחר החשכה.
איור 4.5 הסטוגרמת RGB של שתי התמונות
איור 4.6 תמונת הזירה בהארה מלאה

מעניין לראות את השפעת ההצללה על צבעי התמונה. באיור 4.6 מסומן באליפסה אדומה קטע מוצלל ובו ניתן לראות את הבדלי הצבעים, שנוצרו עקב כך.
מתוצאות ההיסטוגרמה ואפקט ההצללה, ברור כי לא ניתן יהיה להסתמך על צבע במרחב RGB על-מנת לבצע מעקב אמין, שכן שינויי תאורה (היכולים לנבוע גם מזוויות צילום שונות, במיוחד בסביבת Indoor), משנים באופן ישיר את עצמת ה-RBG והרי אנו מעוניינים לעקוב אחר צבע מונוטוני.
לעומת זאת, הניסוי מראה כי במרחב HSV התוצאות טובות הרבה יותר.
איור 4.8 מראה את תוצאת ההיסטוגרמה של שתי התמונות (הארה והחשכה), לאחר שעברו טרנספורמציה למרחב תצוגה HSV. ניתן לראות בבירור, כי הקורלציה בין ההיסטוגרמות גבוהה מאוד ומקדם המתאם הינו 0.91 – תוצאה מספקת ביותר.
כמו-כן, ניתן לראות באיור 4.9, כי ההצללה לא השפיעה על ערך ה-Hue של הפיקסל וזאת מהסיבות שהזכרנו לעיל.
שימו לב כי כל segment בתמונה, מבוטא על-ידי צבע אחיד ללא תלות במיקומו ביחס למצלמה או למקור האור – מכאן ניתן ללמוד כי בהינתן ערךHue, המאפיין את האובייקט, אחריו אנו רוצים לעקוב, מוטב לבצע מעקב במרחב HSV על מנת לקבל תוצאות אמינות.

מעניין לראות את השפעת ההצללה על צבעי התמונה. באיור 4.6 מסומן באליפסה אדומה קטע מוצלל ובו ניתן לראות את הבדלי הצבעים, שנוצרו עקב כך.
מתוצאות ההיסטוגרמה ואפקט ההצללה, ברור כי לא ניתן יהיה להסתמך על צבע במרחב RGB על-מנת לבצע מעקב אמין, שכן שינויי תאורה (היכולים לנבוע גם מזוויות צילום שונות, במיוחד בסביבת Indoor), משנים באופן ישיר את עצמת ה-RBG והרי אנו מעוניינים לעקוב אחר צבע מונוטוני.
לעומת זאת, הניסוי מראה כי במרחב HSV התוצאות טובות הרבה יותר.
איור 4.8 מראה את תוצאת ההיסטוגרמה של שתי התמונות (הארה והחשכה), לאחר שעברו טרנספורמציה למרחב תצוגה HSV. ניתן לראות בבירור, כי הקורלציה בין ההיסטוגרמות גבוהה מאוד ומקדם המתאם הינו 0.91 – תוצאה מספקת ביותר.
כמו-כן, ניתן לראות באיור 4.9, כי ההצללה לא השפיעה על ערך ה-Hue של הפיקסל וזאת מהסיבות שהזכרנו לעיל.
שימו לב כי כל segment בתמונה, מבוטא על-ידי צבע אחיד ללא תלות במיקומו ביחס למצלמה או למקור האור – מכאן ניתן ללמוד כי בהינתן ערךHue, המאפיין את האובייקט, אחריו אנו רוצים לעקוב, מוטב לבצע מעקב במרחב HSV על מנת לקבל תוצאות אמינות.



איור 4.7 תמונת הזירה, לאחר החשכה במרחב צבע Hue בלבד
איור 4.8 הסטוגרמת Hue של שתי הזירות
איור 4.9 תמונת הזירה בהארה מלאה במרחב צבע Hue בלבד

כפי שיוצג בהמשך (חקר ישימות), ישנם הבדלי ביצועים עצומים בין מצלמות ביתיות (lower-end cameras), אשר משתמשות בסנסורים מסוג CMOS, לעומת מצלמות יותר איכותיות (higher-end cameras), אשר משתמשות בסנסורים מסוג CCD.
אלגוריתמים מבוססי צבע, מאוד פגיעים מיעילותם הנמוכה של סנסורים מסוג CMOS, כיוון שאלו דורשים רמת דיוק גבוהה בהצגת הצבעים, בזמן שהמצלמה מספקת רמת דיוק נמוכה יחסית.
כהשלכה ישירה מהנאמר לעיל, מצלמות CCD יקרות בהרבה ממצלמות מסוג CMOS ועל כן יש לבחון היטב את האלגוריתם ולוודא, כי שימוש ב-web cam (CMOS) בפרויקט זה, עדיין יספק תוצאות טובות למטרת עקיבה.

Michael Boyle במאמרו [מקור 19], ערך השוואה בין מצלמת QuickCam לבין מצלמת 1-XL. באיור 4.10 ניתן לראות את התוצאות השונות לקומבינציות המצבים הבאים: רכישת תמונת מקור ע"י כל אחת מהמצלמות וקורלציית תמונה נרכשת, עם תמונת המקור.

בהינתן תמונת מקור, שנרכשה ע"י מצלמה אחת, כאשר ננסה לבצע התאמה (לטובת מעקב) בינה לבין תמונה חדשה, הנרכשת ע"י מצלמה שונה – התוצאות תהיינה גרועות ביותר. כהוכחה, ראה אלכסון באיור 4.11 משמאל למטה לימין למעלה.
לעומת זאת, כאשר תמונת המקור והתמונה הנרכשת, התקבלו ע"י אותה מצלמה, ישנו הבדל די משמעותי באיכות התוצאה וזאת עקב הדיוק הגבוהה של מצלמת 1-XL לעומת QuickCam.
למרות הבדלי התוצאות, עדיין אפשר להסתמך על מצלמת QuickCam, ע"י שיפורים נוספים עליהם ארחיב בהמשך.



איור 4.10 תמונת המקור.
איור 4.11 הסתברויות הצבעים שהתקבלו ע"י שילוב בין הזוגות תמונת מקור / תמונה נרכשת ו- מצלמת CCD / מצלמת CMOS, בשימוש במודל HSV.

במאמרו, מסכם Michael , כי היסטוגרמת ההסתברויות, המתקבלת מתמונת המקור [איור 4.11] ע"י מצלמת CCD טובה הרבה יותר ופחות מורעשת, במידה משמעותית, מאשר זו שנרכשה ע"י מצלמת CMOS.
אמנם תוצאה זו אינה מפתיעה, אך בשל העלות הגבוהה של המצלמה, ממשיך וכותב Michael , כי במידה ונרצה להשתמש במצלמה זולה יותר (CMOS), חשוב להקפיד שתמונת המקור והתמונות הנרכשות בזמן המעקב יהיו מאותה מצלמה – כך התוצאות יהיו מספקות דין.


איור 4.12 הסטוגרמת שכיחות הצבעים בשתי התמונות במרחב הצבע Hue.

איור 4.12 מראה בצורה ברורה ביותר את ההבדלים בין שתי המצלמות.
הקו המודגש יותר, מציין את היסטוגרמת התמונה שנרכשה בעזרת מצלמת CCD.
ניתן לראות, כי רוב הפיקסלים הם בעלי אותו צבע (Hue) ולכן ישנו peak אחד בצבע השכיח ביותר ועוד מספר שכיחויות באותו אזור.
לעומת זאת, הקו החלש מסמן את היסטוגרמת התמונה, שנרכשה בעזרת מצלמה פשוטה יותר (QuickCam). האליפסה הירוקה מסמנת את מרחב הצבעים, שנדגמו ע"י המצלמה.
מכיוון שאליפסה זו רחבה מאוד, משמע שישנם צבעים רבים בתמונה וזאת כתוצאה מריבוי רעשים, שכן התמונה המקורית אינה מורכבת ממספר רב של צבעים ולכן היינו מצפים להיסטוגרמה צפופה יותר, כזו שהתקבלה ע"י מצלמת CCD (אליפסה אדומה).

חקר ישימות

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

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

מתוצאות הטבלה ניתן לראות כי הבחירה במצלמת WebCam[איור 5.3], וברובוט Robot Command System (RCX) module of the LEGO® MINDSTORMSTM Robotics Invention System2.0 [איור 5.1] - הינם הבחירה הטובה ביותר עבור דרישות הפרויקט ועל סמך הקריטריונים המפורטים לעיל.



איור 5.1 בקר RCX
איור 5.2 מגדל שידור IR
איור 5.3 מצלמת QuickCam Pro 4000 של חברת Logitech

יחידת ה-RCX היא, למעשה, מחשב קטן, המבוסס על שבב הH8- של היטאצ'י מעבד שמונה ביט זה מספק serial I/O , מתמיר אנלוגי לדיגיטאלי וטיימרים.
יש 16k של Rom פנימי, ו-32k של RAM חיצוני, בהתחלה הRAM- ריק, אבל עם קבלת ה-RCX יש להטעין על היחידה את ה-firmware, שהיא מעין מערכת הפעלה, כך שנשאר למשתמש רק 6k לשימושו.
ה-firmware נועד לשם אינטרפרטציה של הקוד, שנכתב ליחידה על ידי המשתמש, כך יש באפשרותי לתכנת את הבקר על בסיס דרישות הפרויקט ולהימנע משימוש בתכנות בסיס שהתקבלו עם הבקר, שאינם מתאימות למשימת המעקב של הפרויקט.

על סמך מבחנים שנערכו (ראה פירוט לעיל "תיאור מצב קיים"), נמצא כי שימוש במצלמה ביתית מסוג WebCam עונה, במידה רבה, על צרכי הפרויקט. מצלמה מסוג Logitech Pro 4000, הינה מצלמה יחסית מתקדמת מבין מגוון מצלמות ה-USB.


שקלול תוכנה

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

משך הפיתוח – באיזו מידה, שימוש בתוכנה זו, יקטין את זמן הפיתוח.
מודולאריות – האם התוכנה מאפשרת כתיבת קוד בצורה מודולארית (לדוגמא: טכנולוגית OO) ועד כמה ניתן לעדכן/לשנות מודולים שונים בתוכנה.
סיכון בפיתוח – יציבות התוכנה ופונקציונאליות רבה ואמינה בתחומי הפרויקט (לדוגמא: Image Processing, Communication ועוד).
ניידות התוכנה – קלות התקנה/הרצת התוכנה על פלטפורמות שונות.

יתרונה הגדול של MATLAB, על-פני תוכנות אחרות, הוא בשל שני כלים (Tool Boxes) עיקריים: Image Processing, Image Acquisition.
שני כלים אלו, בנוסף לשאר הפונקציות הבסיסיות בתוכנה, הביאו את MATLAB להיות התוכנה האידיאלית לבחינת אלגוריתם ולמימושו.
הבעייתיות בה נתקלתי, הייתה בעת שילוב התוכנה עם החומרה. על-פניו, נראה היה, כי יתרון גדול לשפות תכנות אחרות, הוא באפשרות להתממשק (Integrate) לחומרה בקלות, יחסית, לעומת MATLAB. לאחר לימוד מעמיק של הנושאים הבאים: "Integrating MATLAB" & "MATLAB External Interfaces/API", הצלחתי לבצע שילוב מלא בין התוכנה והחומרה.

יתר על כן, ישנה אפשרות לשלב קוד C/C++ בתכנית MATLAB, בעזרת פונקציות API, המשווקות עם התכנה.
בשיטה זו עוטפים (wrapper) את הקוד בפונקצית Getaway וכך מתאפשר לקוד MATLAB, להריץ את אותה פונקציה.
בתצורה זו, ישנו יתרון גדול מאוד לתכנת MATLAB, על-פני התוכנות האחרות וזאת משום עליונותה הבלתי ניתנת לערעור, בתחום עיבוד התמונה וכן, היכולת להאיץ את האפליקציה בעזרת פונקציות C/C++, המתאפשרות להרצה מתוך סביבת העבודה ב-MATLAB.
אכן בפרויקט זה, לאחר שלב בחינת האלגוריתם ושיפורו, ביצעתי בדיקה מקיפה בעזרת profiler על-מנת לזהות את הנקודות האיטיות, שמהוות צוואר בקבוק (bottleneck) בריצת התוכנה. לאחר מציאת פונקציות אלו ובמידת האפשר, שכתבתי את אותם קטעים בשפת C ובכך התקבלו שיפורים משמעותיים, בסך זמן ריצת האלגוריתם.


שקלול אלגוריתם
במטרה למצוא אלגוריתם מהיר ופשוט עבור עקיבה, התמקדתי באלו המבוססים על צבע אובייקט, אולם למרות "פשטותם", לכאורה, הם עדיין מסובכים מבחינה חישובית (ועל כן איטיים בכל CPU נתון) עקב השימוש בקורלציית צבעים, Region Growing, Kalman פילטר, החלקה, ניבוי ואחרים.

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

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

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


בהסתמך על הקריטריונים שלעיל, ועל-סמך ניסויים ראשוניים, נבחר לממש את האלגוריתם בשיטת CAMSHIFT [מקור 7]. שיטה זאת, אינה מבוססת על חישובים סטטיסטיים ותחזיות, אלא מסתמכת על שיפוע גרף הצפיפות, על-מנת למצוא את נקודת השיא, אשר היא הנקודה בה הסתברות התפוצה היא הגבוהה ביותר.
על מנת לייעל את האלגוריתם, השתמשתי באלגוריתם אדפטיבי.

שקלול מסכם

מסיכום הטבלאות ניתן לראות כי השילוב של תוכנת MATLAB כסביבת פיתוח, ושימוש בחומרה רובוט , RCXמגדל שידור Infra Red ומצלמת WebCam, הם השילוב בעל הדירוג הגבוה ביותר ועל-כן נבחרו.

חשוב לציין, כי אחד המדדים בחקר הישימות היה "מודולאריות" - כלומר, היכולת להוסיף, לשנות או להחליף את אחד המודולים בפרויקט בחדש, וכל זאת מבלי לפגוע, יתר על המידה, בזמן פיתוח/ריצת הפרויקט.
משמעות המודולאריות בפרויקט זה, הינה כי כל יחידה (תוכנה או חומרה), יכולה להיות מוחלפת באחרת בקלות רבה. לדוגמא, בחרתי להשתמש בבקר מסוג RCX. במידה וארצה לשנות את הבקר או להחליף את סוג התקשורת (במקרה שלי התקשורת הינה Infra Red), אוכל לבצע זאת בזמן קצר מכיוון שמודל ה-RCX הינו מודל סגור, שאינו תלוי בשאר התוכנה אלא בקוד פרטי הצרוב עליו וכך כאשר ארצה להחליפו, כל שאצטרך, זה לשנות את הקוד, אותו "אוריד" לבקר החדש.

אוסיף ואומר, כי בגרסה החדשה של תוכנת MATLAB (גרסה 7, release 14), ניתנת האפשרות בעזרת כלי (Tool) מתקדם הנקרא MATLAB Compiler, להמיר את הקוד הסופי לקבציי C/C++ וכך לייצר קוד ריצה exe.* שאינו תלוי ב-MATLAB.
כלומר, הפרויקט יוכל לרוץ על כל מחשב, גם במחשבים בהם לא מותקנת תוכנת MATLAB.
זוהי נקודה נוספת לזכות הקונפיגורציה שנבחרה לפרויקט זה, ועל-כך אדון בהרחבה בפרק "שיפורים עתידיים".

תהליכים וזרימת מידע

תוכן הענינים
שלב האתחול חומרה
אתחול משתני תוכנה
Pre Processing
אלגוריתם העקיבה - חיפוש אובייקט בתמונה וחישוב מיקומו היחסי
מציאת מיקום האובייקט ושליחת פקודת מיקום לרובוט
שינוי מיקום הרובוט


איור 6.1 תרשים זרימה כללי של הפרויקט כולו

שלה האיתחול חומרה
שלב האתחול מבוצע פעם אחת בלבד, בתחילת התכנית.
מספר דברים עלינו ללמד את המערכת, בטרם נתחיל את תהליך העקיבה:
· מצלמה – כפי שציינתי ב"חקר ישימות", הפרויקט בנוי באופן מודולארי, כך שיתאים את עצמו למגוון חומרות שונות. כיוון שלכל מצלמה, ישנם פרמטרים שונים, כגון: רזולוציות תמונה, בהירות, Contrast, וכדו', עלינו "לומר" לתוכנה, באיזו מצלמה אנו משתמשים ו"לכוון" את (Configuration) הפרמטרים, לכדי מצב עבודה. בתחילת שלב זה, מתקבל ה-GUI "Image Acquisition Configuration Tool" [איור 6.2]. כלי זה דוגם את חומרת המחשב ולומד את הפרמטרים של המצלמה.

איור 6.2 GUI ראשוני לטובת קונפיגורציות חומרה

כפי שניתן לראות, באיור 6.2 המצלמה הינה מסוג Intel PC Camera CS110, בעלת הפרמטרים הבאים: Brightness, Contrast, Gamma, Hue, Saturation, Sharpness, White Balance ומאפיינים רבים נוספים כגון FramePerTrigger, LoggingMode. פרמטרים אלו, ניתנים לשינוי ב-GUI הנ"ל לפני תחילת העקיבה,

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

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

ליחידה זו, מקום ל-32 משתנים גלובליים, שגודלו של כל אחד מהם עד 16 ביט והם אינם משתנים, כאשר משנים תוכניות והיחידה מסוגלת להחזיק עד לחמש תוכניות.
אחת הבעיות הגדולות ביותר בפרויקט זה, כפי שציינתי בחלק "מטרות הפרויקט", הינה העבודה בעזרת הרובוט. מתוך ניסויים ובדיקות, גיליתי, כי הרובוט אינו מדויק לחלוטין, כאשר העבודה מתבצעת בתקשורת IR. ניתן לומר כי הסיבה לכך, אינה הרובוט, כי אם המחשב עצמו, אשר הוא זה שאינו מדויק. לצורך ההסבר, נדמיין מצב שכל 0.5 שנ', ברצוננו להעביר פקודת תנועה קדימה לרובוט ולאחר 0.7 שנ', נרצה להפסיקו ולכן נשלח פקודה נוספת להפסקת התנועה. Windows, אינה מערכת Real Time ולכן מדובר במשחק מכור מראש, בו אין סיכוי לשלוט בזמנים אלו ולעמוד בדרישות. כתוצאה מכך, התנועה של הרובוט אינה מדויקת לחלוטין, שכן לא ניתן לחזות את האינטרוואלים האמיתיים, בהם תשלח הפקודה לרובוט.
לאחר מספר ניסויים, התגלה, כי תנועת הרובוט שהתקבלה בעת ריצת המקרה, המתואר לעיל, הייתה "מוזרה" ובלתי ניתנת לחיזוי. הפקודות התקבלו בזמנים שונים וכתוצאה מכך, תנועת הרובוט לא הייתה חלקה ועקבית כנדרש.

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

הפתרון שנמצא, הוא שינוי mode העבודה מול הרובוט.

בתחילת התוכנית, "נוריד" (download) לרובוט מספר תוכניות (programs), אותן נכתוב מבעוד מועד, כאשר כל תכנית מבצעת משימה שונה. לדוגמא, תכנית מספר 1 מבצעת תנועה ימינה באינטרוואל זמן של 0.2 שנ' ואילו תכנית מספר 2 מבצעת תנועה שמאלה ולמעלה באינטרוואל זמן של 0.2, 0.5 שנ' בהתאמה.
בקונפיגורציות עבודה אלו, אין חשש לאי דיוק, כיוון שלרובוט טיימרים משלו (מדויקים דיו) ואין זה מושפע מתהליכים (processes) נוספים, העלולים להשפיע על דיוק הזמנים.
כעת, כל שנותר לנו לבצע בעת זיהוי אובייקט, זה לבדוק באיזה מבין התוכניות, הצרובות מראש ברובוט, עלינו להשתמש, על-מנת לבצע מעקב - ולהפעילה.
היתרון כאן הינו כפול, פעם אחת בזה, שאנו מסתמכים על הטיימר של הרובוט ובכך מקבלים דיוק זמנים טוב יותר, כפי שהוסבר לעיל, ופעם נוספת, בכך שהסרנו חלק נכבד מהקוד של הפרויקט, שאמור לרוץ על המחשב, והיה מאט את מהירות האלגוריתם.

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

בכל עת בשלב זה, הודעת שגיאה תינתן, עם זריקת Exception.

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



איור 6.2.1 ממשק המשתמש (GUI) בזמן אתחול המשתנים התוכניתיים

הפרוצדורה החשובה ביותר בשלב זה, היא בניית גרף צפיפות הסתברויות הצבע. (Color Probability Distribution), הסבר מפורט בצורך בגרף זה, יינתן בהמשך כאשר נדון באלגוריתם העקיבה.
לאחר סימון האובייקט ויצירת הגרף, התכנית מאתחלת מספר מאפיינים של המצלמה.
המצלמה בה אני משתמש עובדת במקצב Hz30, כלומר 30fps = 30 תמונות בכל שנייה, כמובן שבכלי התוכנה והחומרה בהם אני משתמש בפרויקט זה, אין סיכוי לבצע מעקב בתדר שכזה, שהרי זמן תשדורת IR + זמן אלגוריתם למציאת אובייקט עבור כל תמונה, גדול בהרבה מ-1/30 שנ'.



מכאן המסקנה, שאין צורך ב-mode עבודה של 30Hz, שהרי אין בכך כל ערך מוסף ואף להיפך, ככל שמאגר התמונות יגדל (עקב איטיות האלגוריתם + תקשורת), נקבל מצב בו, אנו בודקים תמונה, שאינה משקפת את המציאות העכשווית, שהרי היא נרכשה לפני מספר שניות ומאז המציאות השתנתה. לכן, חשוב לעבוד בתדר מדויק, כך שהתמונה עליה אנו "עובדים", היא התמונה המעודכנת ביותר.
בעיה חמורה נוספת, שעלולה להיווצר עקב תדר רכישה גבוה ממהירות חישוב, הינה "סתימת זיכרון".

ניקח, לדוגמא, mode עבודה בתדר 30Hz וזמן חישוב + זמן תשדורת =10Hz . כלומר, בכל שנייה אנו רוכשים 30 תמונות, אולם מספיקים להכניס ל-pipe החישוב רק 10 תמונות, מכאן שישנן עוד 20 תמונות בהמתנה. לאחר 10 דק' מעקב נקבל: , בהנחה, כי כל תמונה בסביבות M70~ קיבלנו: ולאחר שעה של מעקב, "נגנבו" מאתנו מספר Giga's של זיכרון.
מהסיבות שלעיל: 1) "סתימת זיכרון", 2) עדכניות המעקב, אנו מגיעים למסקנה, שקצב דגימת התמונות חייב להיות מסונכרן בדיוק לזמני חישוב האלגוריתם + זמן תשדורת IR.

זמן חישוב אלגוריתם + תשדורת IR


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

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


Time. הבעיה היא כיצד יש לדעת באיזה תדר לעבוד? הרי לכל מחשב, יש נתונים שונים (גודל RAM, מהירות מעבד וכדו'), נתונים המשפיעים היישר על יכולות החישוב וזמני
ריצת האלגוריתם. עקב כך, לא ניתן לקבוע חד וחלק באיזה תדר יש לעבוד, שכן למחשב אחד תדר זה יכול להיות הולם, בזמן שלמחשב אחר יהיה זה איטי/מהיר.
הפתרון טמון במאפיינים של המצלמה. ביכולתי להגדיר מתי לרכוש תמונה, כמה תמונות לרכוש באותו רגע, ולמשך כמה זמן.
איור 6.2.3 ממחיש את עניין השליטה ברכישת התמונות ע"י המצלמה.
בדוגמא שלעיל, אנו רואים, כי בכל "Trigger" ברצוני לרכוש 5 תמונות (FramesPerTrigger=5), באינטרוואלים של 2 תמונות (FrameGrabInterval=2), כלומר בכל עליית Trigger, המצלמה תרכוש 5 תמונות מתוך 10 אפשריות, והתוצאה היא רכישת תמונה ולאחר מכן, דילוג על תמונה, רכישה נוספת ודילוג וכן הלאה, עד שבסופו של תהליך, רכשנו 5 תמונות (בעצם עברנו 10 תמונות ורק מחציתם נרכשו באמת).




איור 6.2.3 ציר הזמן לאחר אתחול מספר מאפייני מצלמה.

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


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

מספר חזרות
צורת הפעלת Trigger
מספר תמונות לרכישה בכל Trigger
פונקציה להפעלה בעת Trigger
מאפיין "מספר תמונות בכל Trigger"
מאפיין "מספר חזרות על Trigger"



איור 6.2.4 מאפייני מצלמה בשלב האתחול


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

Pre Processing
לאחר שלבי האתחול (6.2 ו-6.1), ניתן בעצם להתחיל את תהליך העקיבה.
השאלה הנשאלת מיד הנה: "מיהו אותו אובייקט, אחריו אנו רוצים לעקוב?". לשאלה זו אפשר לתת מספר תשובות, האחת (אפשרות למימוש עתידי) היא בעזרת אלגוריתם לזיהוי תנועה – Motion Detection. ישנן שיטות רבות למימוש אלגוריתם MD [[מקור 20], [מקור 21], [מקור 22]], המהירה ביותר היא בדיקה פשוטה בין זוג תמונות ע"י חיסור אחת מהשנייה. בהינתן תוצאה גבוהה מערך מסוים (Threshold) – ניתן לומר, כי ישנה תנועה ברקע ואין זה כתוצאה מרעשים.
לאחר שהגענו למסקנה, כי ישנה תנועה ברקע, אנו יכולים לדעת היכן (אילו פיקסלים) הייתה אותה תנועה, או במונחים לוגיים, אילו פיקסלים שינו את ערכם. פיקסלים אלו, כנראה, הם אותם פיקסלים, שמאפיינים את האובייקט, אחריו אנו מעוניינים לעקוב, וכך סימנו את אובייקט העקיבה.
בפרויקט זה, על-מנת לקבל תוצאות מדויקות יותר, החלטתי שסימון האובייקט למעקב יתבצע על ידי המשתמש.
בשלב זה של התכנית, מתקבל מסך Preview, בו רואים את שהמצלמה מצלמת. בעזרת מקשי החיצים שבמקלדת, או בעזרת כפתורי החיצים שב-GUI, יכול המשתמש להסיט את המצלמה ימינה, שמאלה, למעלה, למטה וכן לכל קומבינציה אלכסונית.
לחיצות אלו מפעילות תשדורת IR לרובוט, וזה יודע על בסיס תוכנה, שהתקבלה בשלב 6.1, לאיזה כיוון עליו לפנות.
ברגע שהמשתמש מזהה את האובייקט במסך ה-Preview, הוא נדרש ללחוץ על כפתור "Snapshot". בעת הלחיצה נסגר מסך ה-Preview ונרכשת תמונת מרקע, בה נמצא האובייקט. סמן העכבר נהפך מצורתו הרגילה (חץ שחור) לסמן פלוס "plus sign", וזאת על-מנת לאפשר למשתמש, לסמן את האובייקט, ביתר קלות.

יש לציין, כי בכל שלב ושלב בתהליכים אותם אני מתאר כאן, ישנו ליווי בכתובית צהובה על ממשק ה-,GUI האומר למשתמש, את שיש עליו לבצע כעת. בצורה כזו, גם משתמש חדש, שאינו מכיר את התוכנה, יכול להפעילה ללא קשיים מיוחדים. [ראה איור 6.2.1]

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


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

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

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

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


מאותה סיבת חסכון, גם תשדורת מסוג שמאלה + למעלה, תיחסך בכך שתשלח כתשדורת אחת, ולא כשתי תשדורות, ובכך מנענו תשדורת מיותרת.

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

כדי לממשק החלטה זו בקוד, יש לבצע מספר רב של if-ים, לטובת השוואות עם המצב הקודם. למניעת מספר רב של בדיקות אלו בכל איטרציה, פיתחתי אלגוריתם, אשר יתואר בחלק הבא, בעזרתו מתבצעים 2 if-ים במקרה הגרוע ביותר (worst case scenario).


שינוי מיקום הרובוט בשלב אתחול חומרה (6.1), בעזרת תוכנת BricxCC מורד קוד בשפת NQC
(NQC stands for Not Quite C), אשר רץ בלולאה אינסופית למשתני מיקום. בעת הזנת משתנים אלו, בעזרת מגדל התקשורת, מחליט הרובוט לאן לפנות (אם בכלל).
ניתן לראות, כי כל עוד לא סיימנו לעבוד עם תמונה מסוימת, אין סיבה לרכוש תמונה חדשה.

אלגוריתמים ומבני נתונים

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

איור 7.1
איור 7.2
איור 7.3
הניסוי הבא ממחיש את שנאמר לעניין צמצום בעיית המסיחים, בעת חיפוש באזור מוגדר. בניסוי נלקחה תמונה של מספר מטבעות, חלקם דומים וחלקם שונים, המטרה היא לעקוב אחר מטבע מסוים מבין אותם מטבעות. לצורך הניסוי, הוגדר מטבע מסוים כמטבע אותו אנו מחפשים (מסומן בריבוע שחור). כמובן, שבעת חיפוש מטבע בתמונה השלמה נקבל מספר תוצאות (כמספר המטבעות!), אולם אנו מעוניינים אך ורק במטבע מסוים, שאינו מובדל במאפיין כלשהו מהאחרים. ניתן לראות כי כאשר הגדרנו "אזור עניין" (Roi) – איתרנו אך ורק מטבע אחד, כלומר שאר המטבעות שהנם מסיחים, לא הפריעו לזיהוי המטבע הרצוי.





איור 7.4

אלגוריתם Camshift
Mean Shift פועל על בסיס "פיזור הסתברויות" (Color Probability Distribution) ערכי הפיקסלים. כל תמונה, הנרכשת על-ידי המצלמה, נמדדת בעזרת היסטוגרמה לקבלת פיזור ההסתברויות. מכיוון שכל תמונה היא בעלת ערכי הסטוגרמה שונים (שהרי המצלמה זזה בכל רגע נתון), האלגוריתם צריך להסתגל דינאמית לפיזור הסתברויות שונה בכל רגע.
האלגוריתם שעונה על דרישות אלו נקרא Camshift.

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

בשלב אתחול משתנים תוכנתיים, מתבקש המשתמש לסמן את האובייקט, אחריו אנו מעוניינים לעקוב (ישנה גם אפשרות שנייה לזיהוי אובייקט ע"י אלגוריתם motion detection, אך לעניינינו אין זה משנה, כיצד מזהים את האובייקט בתחילה, אלא עצם סימון האובייקט). העקוב יעשה מתוך אותה תמונה קטנה יותר (כמובן) של האובייקט בלבד, ממנו אנו מפיקים היסטוגרמת HSV. כפי שהוסבר לעיל, אנו נעבוד עם מימד אחד בלבד של תמונה זו – Hue.
כאשר סימנו את שלב סימון האובייקט ויצירת היסטוגרמת Hue מתוך מרחב הצבע HSV, אנו שומרים את תוצאות ה-Hue.
במהלך התכנית, אותה היסטוגרמה שנשמרה, תשמש לנו למעין Lookup table, כדי להמיר ערכי פיקסלים מתמונות חדשות, הנרכשות תוך כדי ריצה, להתאמת השכיחות שלהם.

כלומר, נניח שהיסטוגרמת האובייקט שנשמרה, מצביעה על ערך 0.8 עבור פיקסל בעל ערך Hue=0.45 (80% מהפיקסלים של האובייקט הינם בצבע 0.45-Hue), כל פיקסל בתמונה החדשה שנרכשה בעל ערך פיקסל 0.45 יקבל ערך חדש 0.8.
בצורה כזו, פיקסלים בעלי הסתברות צפיפות נמוכה, יקבלו ערכים נמוכים ואילו פיקסלים בעלי הסתברות צפיפות גבוהה, יקבלו ערכים גבוהים.
בשיטה כזו, נקבל תמונה חדשה, בה כל פיקסל בעל ערך, המלמד על הסתברותו, להיות חלק מהאובייקט או רקע בלבד. במילים אחרות, במקום בו ישנם פיקסלים עם ערכים גבוהים, מלמד שזה המקום עם ההסתברות הגבוהה שהאובייקט נמצא בו.

צוין קודם, איור 4.2, כשאר ישנה בהירות נמוכה (V קרוב ל-0), מידת הרוויה של הצבע, גם כן תהיה נמוכה (S קרוב ל-0). במצב כזה, Hue הופך למורעש. כיוון שאין מספר גדול של ערכי Hue במקום זה בפירמידה, אי אפשר לציין הבדלים ב-Hue. תופעה זו מביאה לקפיצות חדות בערכי Hue. כדי להימנע ממצב זה, אנו מתעלמים מערכי Hue בפיקסלים, בהם בהירות נמוכה. נובע מכך כי בזירה חשוכה, המצלמה צריכה להסתגל אוטומטית או ידנית, ע"י משתמש, כדי להיות מסוגלת לבצע עקיבה אמיתית.

הדבר נכון גם מהכיוון השני של פירמידת HSV. במקומות מוארים ביותר (מסונוורים), כגון חפץ בוהק שהשמש מאירה עליו, קשה להבדיל בין צבעים בהירים. ולכן גם במקומות בעלי עוצמת צבע גבוהה (V-גבוה), אך רווית הצבע נמוכה (S-נמוך) – H לא מוגדר היטב ומהווה מקור לטעויות זיהוי. מסיבה זו, נתעלם גם ממקומות בעלי פיקסלים עם ערך S-נמוך ו-V גבוהה.
לכאורה, שימוש במרחב צבע RGB היה יכול להיות טוב, אך מכיוון שבמרחב זה אין התייחסות ל-S ( מידת רווית הצבע) התקבלו תוצאות לא מדויקות כלל, במיוחד באזורים חשוכים/בהירים מאוד. בפרויקט מסוג זה, בו המצלמה דינאמית ורוכשת תמונות מזוויות שונות, אין אפשרות להסתמך על מרחב זה (RGB), שכן ערכי האובייקט הנעקב, משתנים תדיר, בהתאם לזווית הצילום.

מקור השם CAMSHIFT.
האלגוריתם הקרוב ביותר לאלגוריתם CAMSHIFT, ידוע בשם mean shift algorithm [[מקור 23], מקור [24]]. אלגוריתם זה אינו מבוסס על טכניקת חיזוי, אלא על מציאת נקודת גובה (peak) בגרף שיפוע גרדיאנט צפיפות הפיקסלים.

How to Calculate the Mean Shift Algorithm
1. Choose a search window size.
2. Choose the initial location of the search window.
3. Compute the mean location in the search window.
4. Center the search window at the mean location computed in Step 3.
5. Repeat Steps 3 and 4 until convergence (or until the mean location moves less than a preset threshold).

הוכחת האלגוריתם מובאת במאמרים רבים, ולכן לא ארחיב
עבור תמונות דו-מימדיות (2D image) של היסטוגרמת הצפיפות, המיקום הממוצע (meanlocation – the centroid) בכל חלון חיפוש (צעדים 3 ו-4) נמצא ע"י המשוואות הבאות.
Find the zeroth moment

Find the first moment for x and y


Then the mean search window location (the centroid) is


כאשר זה ערך הפיקסל (הסתברותית) במקום בתמונה, ו- ו- הם הטווחים בחלון החיפוש.
שלא כמו Mean Shift algorithm, שנועד עבור תמונות סטטיות, CAMSHIFT נועד לסביבה דינאמית ומשתנה בעלת הסתברויות שונות בכל .
כאשר אובייקט ברצף תמונות ווידאו נעקב, וזה משנה את מיקומו בכל רגע נתון, גם חלון החיפוש (מיקומו וגודלו) משתנים עם הזמן. אלגוריתם CAMSHIFT, מסגל את חלון החיפוש, במהלך עבודתו. חלון ראשוני, יכול להיות מאותחל בגודל וערכים כאלו ואחרים. בהמשך הסביר כי עבור תמונות דיגיטאליות, גודלו המינימאלי של חלון החיפוש לא יקטן מ- .
גודלו של חלון החיפוש באלגוריתם זה משתנה בהתאם ל-zeroth moment , שמחושב תוך כדי עבודת האלגוריתם (ראה שלבים לעיל).

How to Calculate the Continuously Adaptive Mean Shift Algorithm
1. Choose the initial location of the search window.
2. Mean Shift as above (one or many iterations); store the zeroth moment.
3. Set the search window size equal to a function of the zeroth moment found in Step 2.
4. Repeat Steps 2 and 3 until convergence (mean location moves less than a present threshold).

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


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

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






איור 7.6

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

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



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

כיצד מחשבים את Coupled CAMSHIFT algorithm (פסואדו קוד).
לפניכם פסאודו קוד של האלגוריתם:

1. First, set the calculation region of the probability distribution to the whole image.
2. Choose the initial location of the 2D mean shift search window.
3. Calculate the color probability distribution in the 2D region centered at the search window location in an area slightly larger that the mean shift window size.
4. Mean shift to convergence or for a set number of iterations. Store the zeroth moment (area or size) and mean location.
5. For the next video frame, center the search window at the mean location stored in Step 4 and set the window size to a function of the zeroth moment found there.
6. Go to Step 3.

עבור כל תמונה, אלגוריתם mean shift, ישאף להתכנס במקום, בו ההסתברות הגבוהה ביותר, ומכאן ש-CAMSHIFT עבור תמונות רציפות, ישאף לעקוב אחרי מרכז אובייקט הנע בזירה.
CAMSHIFT

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

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

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

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

הדמיית ה CAMSHIFT בוידאו

הסרטים מתוך: Computer Vision Face Tracking For Use in a Perceptual User Interface

FaceTrack_Fast.avi 171K
הסרט הראשון מראה את CAMSHIFT עוקב אחר תנועת פנים מהירה
FaceTrack_Distractors.avi 236K
בסרט השני CAMSHIFT עוקב אחר תנועת הפנים עם פנים אחרות בתנועה
FaceTrack_HandOcclusion.avi 317K
בסרט השלישי CAMSHIFT עוקב אחר תנועת הפנים דרך הפרעה (ידיים)

איור 7.7


איור 7.8

הפרויקט משתמש בתמונות דיגיטליות, הנרכשות ע"י מצלמת Web. מכאן נובע כי ייצוג התמונה הוא בדיד.
כיוון ש-CAMSHIFT הוא אלגוריתם המבוסס על גרדיאנט שינוי, גודלו המינימאלי של חלון החיפוש חייב להיות גדול מ-1 כדי לאפשר מציאת גרדיאנט.
מצד שני, כדי לאפשר מרכוז של חלון החיפוש, גודל החלון חייב להיות מספר אי-זוגי. מתוך שתי הנחות אלו נובע, כי גודל החלון המינימאלי חייב להיות 3. מאותה סיבה בדיוק, כאשר האלגוריתם משנה את גודל החלון תוך כדי ריצה, הגודל מעוגל מעלה למספר האי-זוגי הראשון.
למעשה, בזמן אתחול הפרויקט, אנו מחשבים את היסטוגרמת פיזור ההסתברויות של הזירה כולה, ובעזרת zeroth moment אנו מוצאים את גודל החלון ואת מרכזו.

הסתגלות גודל חלון החיפוש.
ההחלטה באיזה פונקציה להשתמש, על-מנת למצוא את ה-zeroth moment ולעדכן את מיקום החלון בשלב 3, תלויה במטרת העקיבה ומשתנה בהתאם לסביבת העבודה.
השיקול הראשוני, הוא כיצד לבצע את הטרנסקציה בין תוצאת ה-zeroth moment ליחידות הגיוניות, לשינוי גודל החלון.
אנו רוצים לעקוב אחר כל האובייקט (במונחים של אלגוריתם – לעקוב אחר כל הצבע), ולכן נצטרך חלון רחב. כלומר את תוצאת החישוב נכפיל ב-2 כדי להכיל את כל הפיקסלים באזור, ונעגל למספר האי זוגי הבא. בתמונת D2 הערך המכסימלי של פיקסל יכול להיות 256 ( ) ולכן נחלק את תוצאת הפונקציה ב-256 וכדי לקבל ערך ב-D1 נבצע פעולת שורש.
לבסוף נקבל את גודל חלון החיפוש לתמונה הבאה:

כסיכום ביניים: אחת הבעיות הקשות של אלגוריתם mean shift, שנפתרה ב-CAMSHIFT, הנה בעיית גודל החלון.
באלגוריתם mean shift, חלון החיפוש הינו בגודל קבוע, כלומר בכל תמונה ותמונה, חלון החיפוש נשאר באותו גודל, ללא תלות במיקום האובייקט ביחס למצלמה. הבעיה שנוצרת כתוצאה מכך ומחוסר התלות במרחק האובייקט, הנה חיפוש רחב מידי, במצב בו האובייקט, נמצא רחוק מהמצלמה, דבר שעלול לגרום לתנועה מהירה של חלון החיפוש, לעומת תנועה איטית (ביחס לעמדת המצלמה) של האובייקט. מצד שני, חיפוש צר מידי, במצב בו האובייקט קרוב למצלמה, דבר שיכול להוביל לבריחת האובייקט עקב תנועה מהירה (שוב – יחסית לעמדת המצלמה) של האובייקט, לעומת תנועה איטית יותר של חלון החיפוש.


איור 7.9

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

אלגוריתם למציאת תשדורת עדכון.
כפי שציינתי מקודם, ישנה בעיה קשה של בזבוז ואי-דיוק בזמנים בכל מה שנוגע למשלוח תשדורות Infra Red.
בנוגע לזמן התשדורת, אין בידי שום אפשרות לשיפור. נתון זה הינו חומרתי בלבד ולא ניתן לשינוי ע"י כתיבת פרוצדורה כזו או אחרת. מצד שני, בעיית אי הדיוק הנובעת מחוסר שליטה מוחלט במערכת ההפעלה, בנוגע לנקודה בה תשלח התשדורת, ישנו פתרון תכנותי.
בקצרה אסביר את בעיית הזמנים שנית: זמן תשדורת IR אורך זמן ממושך, ולכן יש להימנע מתשדורות מיותרות. כהשלכה ישירה מכך, אנו צריכים להעביר אינפורמציה "חדשה" בלבד לרובוט, כדאי למנוע תשדורות חוזרות. לדוגמא, במידה והאובייקט נמצא בכיוון שמאלה + למעלה מהמצלמה, על הרובוט לנוע בכיוון צפון מערב, ולכן זו הפקודה שיקבל לאחר זיהוי האלגוריתם את האובייקט. לאחר מספר מאיות השנייה, שתתקבל התמונה החדשה, עדיין יש לזוז באותו כיוון ועל-כן, אין סיבה ליידע את הרובוט על כך, דבר שיגרום לבזבוז זמן חישוב יקר, (אלא בעת שינוי כיוון העקיבה).
מאותה סיבת חסכון, גם תשדורת מסוג שמאלה + למעלה, תשלח כתשדורת אחת, ולא שתי תשדורות כיוון, בכך תיחסך לנו תשדורת מיותרת.

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

הפתרון שמצאתי, הינו שימוש במבנה נתונים בינארי, בעל 6 ביטים.
כל ביט מאפיין מצב, כאשר '1' מציין מצב פעיל ו-'0' מסמן מצב לא פעיל. בצורה כזאת, במבנה הנתונים בכל מצב נתון יכולים להופיע רק 2 '1'-ים בדיוק, כיוון שלא יתכן תנועה מעבר ל-2 כיוונים.


איור 7.10


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



איור 7.11

כעת, יש בידינו שני מצבים המאופיינים ע"י מבנה נתונים בעל 6 ביטים כל אחד. המטרה היא לדעת מה השתנה בין שני מצבים אלו, ואת המצב שהשתנה בלבד יש לשלוח לרובוט. בצורה כזאת נשלח מינימום תשדורות, וכל תשדורת תכיל מינימום אינפורמציה.

האלגוריתם אומר, שיש לבצע פעולת AND בין שני המצבים, ועל התוצאה לבצע פעולת XOR עם המצב החדש.



איור 7.12

התוצאה הסופית שקבלנו היא: (bin)100000 = (dec)32.
כלומר, קבלנו תוצאה סקלארית המאפיינת את השינוי שחל בין שני המצבים.
ביאור התוצאה: בפעולת ה-AND אנו מבצעים איפוס של כל המצבים שהשתנו, שהרי מצב '0' שהפך ל-'1' או מצב '1' שהפך ל-'0' יניבו תוצאה '0' לאחר פעולת AND. לעומת זאת כל המצבים, אם ישנם כאלו, שלא השתנו, יניבו תוצאה '1'.
כך, יש לנו מבנה נתונים בעל 6 ביטים, בו מצוינים ב'1' המצבים שנשארו בעינם. כעת, נותר לנו לדעת מה מבין המצבים המאופיינים ב-'0' הם המצבים שהשתנו. לשם כך, אנו מבצעים פעולת XOR בין תוצאת פעולת ה-AND לבין המצב הקיים. מכיוון שפעולת ה-XOR, מגלה מצבים הפוכים (לדוגמא: ) ומאפסת (ביט='0') מצבים זהים, נקבל בתוצאה את אותם מקומות שהשתנו בלבד.
מתוך הנאמר לעיל, ננסה להבין את פירוש התוצאה שקבלנו.
המצב ההתחלתי, בו היה הרובוט, הוא תנועה בכיוון Right בציר האופקי, ו-Down בציר האנכי.
כעת, אלגוריתם העקיבה גילה, כי המצב בו צריך להיות הרובוט, הוא המשך תנועה בכיוון Right, אך אי תנועה בציר האנכי. במילים אחרות, עלינו ליידע את הרובוט, אך ורק בשינוי בציר האנכי ממצב של תנועה בכיוון Down ל-אי תנועה=עצירת המנוע האנכי.
ואכן התוצאה שקבלנו מציינת ביט '1' במקום ה-6, כלומר Hold Vertical. מצב זה הוא התשדורת היחידה שעלינו להעביר לרובוט, שהרי הוא נמצא בתנועה ימינה, אותה אנו רוצים לשמר, ואילו עכשיו יידע הרובוט, כי צריך לעצור את המנוע האנכי, וכך תתקבל תוצאה סופית של תנועה בכיוון ימינה בלבד.
אלגוריתם זה מבצע 4 בדיקות בלבד ב-worst case scenario, לעומת מספר רב יותר של בדיקות, בכל אפשרות אחרת.
פתרון זה אפשר לאלגוריתם העקיבה בסופו של דבר, לרוץ בביצועים טובים הרבה יותר.

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

התכנית המפעילה את הרובוט, נכתבה באמצעות תוכנת Bricx Command Center, המאפשרת תכנות דומה מאוד לשפת C (NQC) . תוכנה זו פשוטה מאוד לתכנות והפעלה, ומהווה מעין גרסה מתקדמת לתוכנת ה- Lego MindStorms. היא מאפשרת לאתחל את ה-RCX במערכת ההפעלה שלו, ולטעון עליו תכניות שנכתבו בשפת NQC.
התכנית שכתבתי, פועלת בהתאם לפקודות Real Timeשהיא מקבלת ממגדל השידור.

NQC היא שפת תכנות אשר דומה מאוד בצורתה ל-C (מכאן שמה: Not Quite C) והיא משמשת לתכנות יחידות הRCX. יחידת ה-RCX צריכה להכיל את מערכת ההפעלה (Firmware), באמצעותה ניתן להפעיל את הכלים הסטנדרטיים, שמגיעים עם ערכת הלגו.
ערכת הלגו, מגיעה במקור עם תוכנות, המאפשרות כתיבת והטענת משימות מסובכות בקלות יחסית ובסביבה ויזואלית נחמדה וידידותית. עם זאת, מאחר שהן אינן ממצות את היכולות של יחידות ה-RCX, בחרתי להשתמש בסביבת פיתוח אחרת. דבר זה גורם לכך שיהיו לשפת ה-NQC מגבלות שה-firmware מציב לה.
על מנת לכתוב את התוכניות, לטעון אותן ליחידות הRCX- או לטעון firmware, השתמשתי בפרויקט זה בתוכנה בשם Bricx Command Center, תוכנית ויזואלית וקלה לתפעול.
(http://members.aol.com/johnbinder/bricxcc.htm )
בתוכנה זו השתמשנו לכתיבת התוכנית בלבד, והמשתמש אינו נזקק לה בזמן ההרצה: פעולות הטעינה, ניתנות לביצוע, כבר בשלב אתחול המשתנים.



איור 7.13


איור 7.13 מראה את תרשים הקוד הרץ על הרובוט.
הקוד מכיל פונקצית main ראשית (חלק שמאלי עליון באיור), שרצה בלולאה אין סופית, או במילים אחרות, רצה כל משך התכנית מרגע הפעלתה ועד סוף העקיבה.
פונקציה זו ממתינה לקבלת פרמטרים מ-MATLAB. פרמטרים אלו עוברים בתשדורת IR וכפי שהסברתי באלגוריתם לעיל, כל ערך שישלח הוא בעל משמעות שונה.
בעזרת הערך שמועבר לרובוט, זה יכול לשנות את כיוונו. בתחילת התכנית ערך הפרמטר שווה ל-'0' ולכן לא מתבצעת שום תנועה לכיוון כזה או אחר. עם קבלת ערך ראשוני, מתחיל הרובוט בתנועה על בסיס ערך הפרמטר שהועבר לו. כל זמן שלא התקבל ערך חדש, ממשיך הרובוט בתנועתו, על בסיס ערך הפרמטר האחרון שהועבר, בצורה כזו "ממתין" הרובוט לתשדורת עדכון, וברגע בו מגיעה כזו, מעדכנת פרוצדורת ה-main את ערך speed המועבר לרוטינה הבאה:
רוטינה זו היא לב הקוד הרץ על בקר ה-RCX. (פינה ימנית תחתונה באיור 7.13)
הצגת בעיה: מהירות סיבובי המנוע של בקר ה-RCX, אינם ניתנים לשינוי. בהינתן ערך קבוע למהירות הסיבוב, ישנה בעיה של חוסר דיוק. נניח כי האובייקט נמצא קרוב מאוד לראשית הצירים, אולם מוסט מעט שמאלה, כמובן שהאלגוריתם יזהה זאת וישלח פקודת תנועה שמאלה בלבד לרובוט. בעת קבלת הרובוט את הפקודה לתנועה שמאלה, יפעיל זה את המנוע האופקי ותחל תנועה. כעבור מספר מאיות השנייה, עקב מהירות סיבוב המנוע, ייווצר מצב, שאנו נמצאים הרבה מעבר לאובייקט מצדו הימני !!! כלומר עלינו עכשיו לנוע שמאלה שוב, וכאשר נעשה זאת נגיע לצידו השמאלי ונצטרך לשוב ימינה, וכך שוב ושוב במחזוריות אין סופית, ולא נגיע למצב ייצוב המצלמה מול האובייקט.
תופעה זאת נגרמת עקב חוסר שליטה במהירות הסיבוב, וכך באינטרוואל זמן בין שתי תשדורות (תשדורת תנועה שמאלה והתשדורת הבאה), המצלמה נעה מרחק רב מידי מכפי הרצוי.
על-מנת למנוע מצב אבסורדי זה, עלינו לשלוט במהירות הרובוט בצורה כלשהי.
הדרך לקבלת שליטה היא ,למעשה, תכנות תנועה לא רציפה.
רוטינה זו מבצעת הפעלה והפסקה של המנוע במרווחים של כך, שהתנועה, למעשה, אינה רציפה, אלא מקוטעת. בצורה כזאת אנו שולטים על המהירות, מבלי שהמשתמש מרגיש, כי ישנם הפסקים של קטעי זמן קצרים מאוד בין הפעלה והפסקה של סיבוב המנוע.
רוטינה זו מתבצעת גם-כן בלולאה אין סופית, למשך כל זמן ריצת התכנית, וממתינה לעדכון ערך speed. ערך זה מציין אלו מנועים עלינו להפעיל או להפסיק.
כל זמן שלא התקבל ערך חדש ל-speed מרוטינת ה-main, ממשיך הרובוט בכיוון האחרון, שעודכן לגביו. בעת התקבל ערך חדש, מופסק/ים/מופעל/ים המנוע/ים הרלוונטיים.

דוגמת הרצה

דוגמת הרצה
ניתוח יעילות

דוגמת הרצה
בסעיף תהליכים וזרימת מידע הוצגו המסכים השונים המוצגים במהלך ריצת הפרויקט, ולכן לא אראה אותם בשנית בחלק זה. בסעיף זה, ברצוני להדגיש מספר נקודות בסיסיות ולתת הסברים כלליים על דרך השימוש במערכת והשלבים, אותם אנו עוברים תוך כדי ריצה.
1. רשאית, עלינו לוודא כי התוכנה והחומרה, בהם יש שימוש על ידי המערכת, מותקנים ומחוברים. התוכנות הם: MATLAB (כולל שני כלים נוספים בה Image Processing ו-Image Acquisition), Phantom, BricxCC , דרייברים למצלמה ולמגדל השידור. חומרה: מצלמה פועלת ומחוברת היטב, בקר RCX כולל סוללות חדישות, מגדל שידור תקין ומחובר להתקן USB במחשב. במידה וכל הנ"ל פועלים/מותקנים, אנו יכולים להפעיל את מודל העקיבה.
2. הקובץ הראשי נקרא "ProjGui", אותו יש להריץ לאחר עליית MATLAB.
3. בשלב זה יוצג חלון כניסה ראשוני איור 8.1
ולאחריו נתבקש להזין את נתוני המצלמה
במידה ואלו השתנו איור 6.2
4. לאחר מכן, יתקבל מסף Preview המציג
את שהמצלמה רוכשת, ומצדו הימני מסך
איור 6.2.1, בו אנו יכולים להניע את הרובוט לשם שיפור


איור 8.1 מסך כניסה למערכת

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

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


כאשר ריצת המערכת מסתיימת, יש באפשרותנו להתחיל מהתחלה תהליך חדש, כלומר סימון מחדש של אובייקט וכו', או להציג את סרט העקיבה. לחצן "Show Movie" יציג בפנינו בעזרת Media Player של Windows את הסרט, שנבנה במהלך העקיבה. קובץ זה נקרא ProjectMovie.avi. ישנה אפשרות לא ליצור את הסרט במהלך ריצת הפרויקט, במידה והמשתמש מבחין בעומס יתר על המחשב, שכן פעולת בניית הסרט צורכת משאבים נוספים וכן זיכרון רב לשמירת התמונות.
במידה ונחליט כי ברצוננו לסיים את העבודה, לחצן "Close", יבצע שחרור של כל משתני הסביבה והפרמטרים, שהוגדרו בשלבים הראשונים: "שלב אתחול משתני תוכנה" ו-"שלב אתחול משתני חומרה". פעולה זו חשובה, ואלמלא מתבצעת, המערכת יכולה להיגרר למצב של זליגת זיכרון (Memory leaks). לכן יש להקפיד לסיים את העבודה בצורה מבוקרת.
איור 8.2 מציג את תוכנת Media Player כאשר, זו מראה את הסרט שנבנה במהלך העקיבה. כדאי לשים לב, כי ישנו סימון אדום אנכי ואופקי לאורך כל המסך, המציין את מרכז רזולוציות התמונה. נקודת מפגש הקווים היא נקודת האמצע, אליה הרובוט צריך "להביא" את האובייקט וזאת כדי לשמר את העקיבה. מבחינת המערכת, ברגע שאובייקט העקיבה נמצא בתחום ממרכז התמונה – זהו מצב של "On target" והודעה מתאימה (בצבע צהוב) תופיע בחלון הפרויקט.



איור 8.2 מתוך סרט העקיבה, שימו לב לסימון מרכז התמונה לעומת סימון מרכז המסה של האובייקט.


ניתוח יעילות
שלוש מטרות הפרויקט, שהוגדרו בדו"ח הביניים ובהצעת הפרויקט, הושגו במלואם.
נמצא אלגוריתם לעקיבה, הניתן למימוש במערכת שאינה זמן אמת כגון MATLAB. בעיות סנכרון הזמנים, בין החומרות השונות, נפתרו על-ידי שימוש בתוכנות נוספות (עורכי קוד ופקדים), המאפשרים שליטה נוחה ופרטנית במצלמה, ברובוט ובמגדל השידור.
ביצועי המערכת תלויים מאוד במשאבים, בהם אנו משתמשים. בהינתן מעבד Pentium 4 ומעלה ומצלמה הרוכשת תמונות מעל ל-20fps , ניתן להגיע לביצועי סבירים ואף יותר מכך.
מבדיקות, שערכתי בכלים שברשותי (מחשב ומצלמה), המערכת עובדת בין 10-20fps. תוצאה זו מפתיעה ביותר, ומאפשרת תנועה, כמעט חופשית, לאובייקט בזמן העקיבה. ככל שהמשאבים בהם נשתמש יהיו פשוטים יותר, מהירות הריצה תקטן וכך נקבל אילוץ לתנועת האובייקט במהירות איטית בלבד.
האלגוריתם מניב תוצאות מכסימליות, כאשר זירת המעקב אינה מוארת באור שמש מסנוור ולחלופין אינה חשוכה מידי, למרות שעבור מצבים אלו ניתן פתרון בפרויקט.
כמו-כן, על מנת לקבל תוצאות מהירות במשלוח תשדורות לרובוט, יש להשתמש בסוללות חדישות, המאפשרות תשדורות יחסית חלקות, ללא הפרעות מרחק וזוויות שידור.

מבחן התוצאה של פרויקט זה מתחלק ל-2 חלקים.
האחד הוא מבחן האלגוריתם, או במילים אחרות מבחן מימוש האלגוריתם ב-MATLAB. MATLAB אינה תוכנת Real Time ולכן ראשית, יש לבדוק, האם האלגוריתם מניב תוצאות רצויות, על אף ההאטה שנגרמת כתוצאה מפלטפורמת הפרויקט. כמובן שאחת המטרות החשובות של הפרויקט, הייתה מציאת אלגוריתם כזה, שיושפע במידה מועטה מאיטיות החישוב של תוכנה כגון MATLAB בהשוואה לתוכנות Real Time.
המבחן השני, שיש לבצע הוא מבחן מימוש האלגוריתם, בזמן אמת, תוך כדי שימוש ברובוט נ-RCX.
כפי שציינתי רבות, תקשורת ה-IR בין התוכנה לרובוט, צורכת זמן רב ולכן מעקבת את מחזוריות העקיבה. כלומר ישנה האטה נוספת בקונפיגורציות העבודה בפרויקט זה והיא - זמני השידור לרובוט.
מבחן זה אמור לבדוק את תוצאת העקיבה, כאשר אנו שולחים הודעות עקיבה אמיתית בהתאם לתוצאות האלגוריתם לרובוט.
לאחר חיפושים רבים, מציאת אלגוריתם ומימושו הופקו התוצאות הבאות:
איור9.1
ניתן לראות בברור, כי האלגוריתם עובד בצורה חלקה ומספק תוצאות טובות. באיור 8.1 מסומן ב"+" אדום, מרכז המסה של האובייקט הנעקב. כפי שמעיד האיור, אנו מצליחים לעקוב אחריו בכל תמונה ותמונה מבלי לאפשר לאובייקט לברוח.
בבחינת האלגוריתם בדוגמא הנ"ל הופקו תוצאות במקצבים משתנים בין 20-30 fps. מקצבים אלו גבוהים במיוחד עקב אי-שימוש במגדל השידור לתשדורות IR לרובוט.
במבחן הבא, אבדוק, כיצד עובד האלגוריתם, תוך כדי שליחת הודעות עקיבה לרובוט.
נקודה ראשונה וחשובה מאוד, שהתגלתה מיד בתחילת מבחן המערכת בשימוש עם הרובוט, הייתה עוצמת הסוללות שבבקר ה-RCX. כאשר השתמשתי בסוללות ישנות, חלה ירידה משמעותית במקצבי העבודה ואף בתשדורות שגויות. על-מנת להתגבר על בעיות אלו, יש להשתמש

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

מחשב
RAM
Video Card
מקבצי עבודה
Pentium III
512 M
32 M
5 – 10 fps
Pentium IV
1 G
128 M
10 – 20 fps

איור 9.2

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

איור 9.1 תוצאות אלגוריתם העקיבה לאחר מימושו ב-MATLAB
איור 9.2 טבלת השוואות בין מערכות שונות

ניתוח יעילות

שלוש מטרות הפרויקט, שהוגדרו בדו"ח הביניים ובהצעת הפרויקט, הושגו במלואם.
נמצא אלגוריתם לעקיבה, הניתן למימוש במערכת שאינה זמן אמת כגון MATLAB. בעיות סנכרון הזמנים, בין החומרות השונות, נפתרו על-ידי שימוש בתוכנות נוספות (עורכי קוד ופקדים), המאפשרים שליטה נוחה ופרטנית במצלמה, ברובוט ובמגדל השידור.
ביצועי המערכת תלויים מאוד במשאבים, בהם אנו משתמשים. בהינתן מעבד Pentium 4 ומעלה ומצלמה הרוכשת תמונות מעל ל-20fps , ניתן להגיע לביצועי סבירים ואף יותר מכך.
מבדיקות, שערכתי בכלים שברשותי (מחשב ומצלמה), המערכת עובדת בין 10-20fps. תוצאה זו מפתיעה ביותר, ומאפשרת תנועה, כמעט חופשית, לאובייקט בזמן העקיבה. ככל שהמשאבים בהם נשתמש יהיו פשוטים יותר, מהירות הריצה תקטן וכך נקבל אילוץ לתנועת האובייקט במהירות איטית בלבד.
האלגוריתם מניב תוצאות מכסימליות, כאשר זירת המעקב אינה מוארת באור שמש מסנוור ולחלופין אינה חשוכה מידי, למרות שעבור מצבים אלו ניתן פתרון בפרויקט.
כמו-כן, על מנת לקבל תוצאות מהירות במשלוח תשדורות לרובוט, יש להשתמש בסוללות חדישות, המאפשרות תשדורות יחסית חלקות, ללא הפרעות מרחק וזוויות שידור.

מבחן התוצאה של פרויקט זה מתחלק ל-2 חלקים.
האחד הוא מבחן האלגוריתם, או במילים אחרות מבחן מימוש האלגוריתם ב-MATLAB. MATLAB אינה תוכנת Real Time ולכן ראשית, יש לבדוק, האם האלגוריתם מניב תוצאות רצויות, על אף ההאטה שנגרמת כתוצאה מפלטפורמת הפרויקט. כמובן שאחת המטרות החשובות של הפרויקט, הייתה מציאת אלגוריתם כזה, שיושפע במידה מועטה מאיטיות החישוב של תוכנה כגון MATLAB בהשוואה לתוכנות Real Time.
המבחן השני, שיש לבצע הוא מבחן מימוש האלגוריתם, בזמן אמת, תוך כדי שימוש ברובוט נ-RCX.
כפי שציינתי רבות, תקשורת ה-IR בין התוכנה לרובוט, צורכת זמן רב ולכן מעקבת את מחזוריות העקיבה. כלומר ישנה האטה נוספת בקונפיגורציות העבודה בפרויקט זה והיא - זמני השידור לרובוט.
מבחן זה אמור לבדוק את תוצאת העקיבה, כאשר אנו שולחים הודעות עקיבה אמיתית בהתאם לתוצאות האלגוריתם לרובוט.
לאחר חיפושים רבים, מציאת אלגוריתם ומימושו הופקו התוצאות הבאות:


איור 9.1
ניתן לראות בברור, כי האלגוריתם עובד בצורה חלקה ומספק תוצאות טובות. באיור 8.1 מסומן ב"+" אדום, מרכז המסה של האובייקט הנעקב. כפי שמעיד האיור, אנו מצליחים לעקוב אחריו בכל תמונה ותמונה מבלי לאפשר לאובייקט לברוח.
בבחינת האלגוריתם בדוגמא הנ"ל הופקו תוצאות במקצבים משתנים בין 20-30 fps. מקצבים אלו גבוהים במיוחד עקב אי-שימוש במגדל השידור לתשדורות IR לרובוט.
במבחן הבא, אבדוק, כיצד עובד האלגוריתם, תוך כדי שליחת הודעות עקיבה לרובוט.
נקודה ראשונה וחשובה מאוד, שהתגלתה מיד בתחילת מבחן המערכת בשימוש עם הרובוט, הייתה עוצמת הסוללות שבבקר ה-RCX. כאשר השתמשתי בסוללות ישנות, חלה ירידה משמעותית במקצבי העבודה ואף בתשדורות שגויות. על-מנת להתגבר על בעיות אלו, יש להשתמש

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




איור 9.2

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

טכנולוגיות – סביבת הפרויקט

תקציר
יחידת ה RCX שולטת בתנועה המכאנית של הרובוט. בפרויקט זה, היא מופעלת בתוכנית בשפת NQC. יחידת ה RCX הינה מחשב קטן המבוסס על שבב הH8 של היטאצ'י, מעבד שמונה ביט המספק serial I/O , מתמיר אנלוגי לדיגיטאלי וטיימרים.
כמו כן נבחר שימוש בפקד חדש בשם Phantom.ocx. פקד זה נכתב בשפת C ומאפשר תקשורת ישירה עם מגדל השידור בחיבור USBכיוון ש-MATLAB תומך בקישוריות לפקדים (Activex control), קונפיגורציות העבודה מול פקד זה טריוויאלית ונוחה לשימוש.
מצלמה ביתית מבית Logitech, בעלת יכולות רבות, שחלקן אינן נצרכות לפרויקט זה, כגון: Zoom, Pan ועוד.· רזולוציה 640x480 , 1.3 מיליון מגה פיקסל , חיישן CCD מתקדם , חבור USB.

תוכן הענינים
יחידות ה RCX
מגדל שידור האינפרא אדום TOWER
Phantom Control
מצלמה ביתית , Logitech QuickPro pro 4000
Bricx Command Center 3.3
MATLAB


יחידות ה RCX
יחידת ה RCX-, שולטת בתנועה המכאנית של הרובוט. בפרויקט זה, היא מופעלת בתוכנית בשפת NQC. תוכנית זו מורכבת מלולאה אינסופית הדוגמת ערך של משתנה בודד בזמן אמת. כל ערך של משתנה זה, מכתיב את אופי התנועה של הרובוט (שמאלה ימינה, למעלה, למטה עצירה וכו'), בהתאם לפקודה שנשלחה. פקודות התנועה משודרות לרובוט מהתוכנית המרכזית על מחשב ה-PC, דרך מגדל שידור אינפרא אדום.
מפרט טכני: יחידת ה RCX- הינה מחשב קטן המבוסס על שבב הH8- של היטאצ'י, מעבד שמונה ביט המספק serial I/O , מתמיר אנלוגי לדיגיטאלי וטיימרים.
ליחידה 16k של Rom פנימי, ו32k- של RAM חיצוני, בתחלה הRAM- ריק, אבל עם קבלת ה-RCX, יש להטעין על היחידה את ה-firmware, שהיא מעין מערכת הפעלה, הצורכת זיכרון, כך שנשאר למשתמש רק 6k לשימושו. ה-firmware נועד לשם אינטרפרטציה של הקוד, שנכתב ליחידה, על-ידי המשתמש.
ממשק המשתמש ליחידה כולל ארבעה לחצנים וצג LCD.
ישנה אפשרות להוציא מתח לשלוש יחידות הנעה, בפרויקט זה נעשה שימוש בשתיים מהיציאות הנ"ל לשם הנעת מנועי הגלגלים (אחד עבור כל צד).
יחידת הRCX-, כוללת ארבעה טיימרים, אשר מודדים אינטרוול זמן של 0.1 שנייה, ואשר יכולים להיות מאופסים, על-ידי התוכנית, בכל זמן, באופן בלתי תלוי אחד בשני, והערך שלהם ניתן להצגה על גבי צג ה-LCD.
ליחידה יש מקום ל-32 משתנים גלובליים, שגודלו של כל אחד מהם הוא עד 16 ביט, והם נשארים קבועים כאשר משנים תוכניות, והיחידה מסוגלת להחזיק עד לחמש תוכניות. http://mindstorms.lego.com/



איור 10.1 בקר RCX
דוגמאות נוספות לשימוש בבקר RCX ובמערכת Mindstorms של חברת Lego. [מקור 25].



איור 10.2 דוגמאות לשימוש בבקר RCX.

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



איור 10.3 מגדל שידור אינפרא אדום

פרטים טכניים אודות מגדל השידור ניתן למצוא באתר.
Mindstorms IR-communication

Phantom Control
חברת Lego, מספקת את המוצר Mindstorms 2.0 עם פקד Spirit.ocx. פקד זה מאפשר את התקשורת בין מחשב PC לבין מגדל השידור על בסיס RS232.
מאחר ובפרויקט זה, השתמשתי בגרסה חדשה של מגדל תקשורת, בחיבור USB, אין באפשרותי לתקשר על מגדל זה בעזרת פקד Spirit.ocx.
ישנם שלושה פתרונות: האחד, שימוש במגדל ישן. כמובן שפתרון זה לא התקבל, עקב יתרונותיו הרבים של מגדל תקשורת בחיבור USB מהיר (ראה נתונים לעיל).
הפתרון השני, הוא כתיבת קוד מסובך וקשה לתקשורת בין MATLAB לבין מגדל השידור. פתרון זה גם-כן לא ישים, מפני שזה פרויקט, מורכב וקשה ליישום, בפני עצמו.

הפתרון השלישי והנבחר, הוא שימוש בפקד חדש בשם Phantom.ocx. פקד זה נכתב בשפת C ומאפשר תקשורת ישירה עם מגדל השידור בחיבור USB.
כיוון ש-MATLAB תומך בקישוריות לפקדים (Activex control), קונפיגורציות העבודה מול פקד זה טריוויאלית ונוחה לשימוש.
Phantom , הינו Class , המקשר בין המחשב לתוכנית המפעילה את הרובוט. באמצעותו נשלחים פרמטרים להזנת התכנית הצרובה, על-גבי יחידת ה- RCX. אלה מהווים, למעשה, את הפקודות להנעת הרובוט.
פרטים נוספים וכן הורדת הפקד נמצאים באתר הבא:
Phantom - The Spirit.ocx Replacement
להלן חלק מהפקודות לשימוש בפקד ה-Phantom.

OCX Overview
Communication control commands:
Bool InitComm()
Bool CloseComm()
Variant GetShortTermRetransStatistics( )
Variant GetLongTermRetransmitStatistics( )
Bool SetRetransmitRetries (immidiateRetries,
downloadRetries)
Bool IgnDLerrUntilGoodAnswer()
Firmware control commands:
BSTR UnlockPBrick( )
BSTR UnlockFirmware (UnlockString )
Bool DownloadFirmware) FileName )
Diagnostics commands:
Bool PBAliveOrNot()
Bool TowerAndCableConnected()
Bool TowerAlive()
PBrick system commands:
Bool SelectDisplay (Source, Number )
Bool SetWatch) Hours, Min )
Bool PBPowerDownTime ) Time)
Bool PBTurnOff()
Bool PBTxPower) Number )
Bool PlayTone (Frequency, Time)
Bool PlaySystemSound (Number)
Bool ClearTimer (Number )
Bool SendPBMessage) Source, Number )
Bool ClearPBMessage( )
PBrick output control commands:
Bool On (MotorList )
Bool Off ) MotorList )
Bool Float) MotorList )
Bool SetFwd (MotorList )
Bool SetRwd) MotorList )
Bool AlterDir) MotorList )
Bool SetPower) MotorList, Source, Number ) 61
Bool Wait (Source, Number)
Bool Drive) Number0, Number1 )
Bool OnWait) MotorList, Number, Time )
Bool OnWaitDifferent) MotorList,
Number0, Number1, Number2, Time )
Bool ClearTachoCounter (MotorList(
PBrick input control commands:
Bool SetSensorType (Number, Type )
Bool SetSensorMode) Number, Mode, Slope)
Bool ClearSensorValue) Number )
PBrick program control commands:
Bool SelectPrgm (Number )
Bool DeleteTask (Number )
Bool DeleteAllTasks( )
Bool DeleteSub (Number )
Bool DeleteAllSubs( )
PBrick program execution commands:
Bool StartTask) Number )
Bool StopTask (Number )
Bool StopAllTasks( )
Bool GoSub ) Number )
PBrick flow control commands:
Bool Loop (Source, Number )
Bool EndLoop()
Bool While (Src1, No1, RelOp, Src2, No2)
Bool EndWhile()
Bool If (Src1, No1, RelOp, Src2, No2)
Bool Else()
Bool EndIf()
Bool BeginOfTask) Number )
Short EndOfTask( )
Short EndOfTaskNoDownload( )
Bool BeginOfSub (Number )
Short EndOfSub( )
Short EndOfSubNoDownload( )
PBrick arithmetic/logical commands:
Bool SetVar (VarNo, Source, Number)
Bool SumVar) VarNo, Source, Number )
Bool SubVar (VarNr, Source, Number )
Bool DivVar (VarNr, Source, Number )
Bool MulVar) VarNr, Source, Number )
Bool SgnVar (VarNr, Source, Number )
Bool AbsVar) VarNr, Source, Number )
Bool AndVar) VarNr, Source, Number )
Bool OrVar) VarNr, Source, Number )
PBrick query commands:
Bool SetEvent (Source, Number, Time )
Bool ClearEvent (Source, Number)
Short Poll) Source, Number )
Short PBBattery()
Variant MemMap( )
PBrick data acquisition commands (RCX only):
Bool SetDatalog (Size )
Bool DatalogNext) Source, Number )
Variant UploadDatalog (From, Size )
ActiveX control commands:
Bool SetThreadPriority) threadNo, threadClass,
ThreadPriority)
Void GetThreadPriority) threadNo, threadClass,
ThreadPriority)
ActiveX event dispatch interface:
VariableChange) Number, Value )
DownloadDone (ErrorCode, TaskNo )
DownloadStatus) timeInMS,
sizeInBytes, taskNo )
AsyncronBrickError) Number,
Description )

מצלמה ביתית, Logitech QuickPro pro 4000

מצלמה ביתית מבית Logitech, בעלת יכולות רבות, שחלקן אינן נצרכות לפרויקט זה, כגון: Zoom, Pan ועוד.
· רזולוציה 640480 x
· 1.3 מיליון מגה פיקסל
· חיישן CCD מתקדם
· חבור USB


איור 10.4 מצלמת Logitech QuickCam pro 4000

Bricx Command Center 3.3
זוהי תכנת Editor הידועה בשם IDE, לטובת הורדה ותכנות קוד לבקר RCX.
על-מנת להוריד קוד ל-Firmware של הרובוט, ישנם מספר פקודות בסיסיות, המגיעות עם רכישת החומרה. כיוון שבפרויקט זה, ישנו שימוש מאסיבי בבקר וכן, ישנה חשיבות רבה ליעילות הקוד הרץ בבקר, נדרשתי לחפש סביבת עבודה, המאפשרת קידוד מתוחכם יותר, מאשר זה הבסיסי של חברת Lego.
לאחר בירור, הופניתי לתכנה זה המאפשר לכתוב בשפת NQC (Not Quit C) קוד כזה או אחר על-פי רצון המתכנת.
באתר הבא, ניתן להוריד את סביבת העבודה וכן תיעוד מלא של שפת התכנות NQC. כמו כן, ניתן להוריד את הקוד הפתוח של סביבה זו לטובת שיפורים פרטיים, במידה וישנם כאלו.
http://bricxcc.sourceforge.net/

MATLAB
MATLAB הינה התוכנה העיקרית במימוש פרויקט זה. כפי שציינתי, ישנם מספר תוכנות נוספות, אך כולם נקראות מתוך סביבת העבודה הראשית – MATLAB.
הבחירה בתוכנה זו, מתוארת בפרטים בחלק "חקר ישימות", לכן לא ארחיב על כך בשנית.
תוכנה זה מכילה ספריית פונקציות רבות בתחום עיבוד תמונה, למרות שבמימוש פרויקט זה, לא היו כמעט פונקציות ,Build in בהם הייתי יכול להשתמש.
רוב האלגוריתם מבוסס על תחום הסטטיסטיקה ולכן, היה עלי לממש את פונקציות האלגוריתם בקוד אישי.
כהשלכה ישירה משימוש בתוכנת MATLAB, כל מי שירצה להשתמש בקוד הפרויקט, יצטרך לרכוש את התוכנה (MATLAB) כיוון שהקוד המיוצר אינו קוד executable.
בחלק "פיתוחים עתידיים", ארחיב לגבי אפשרות ליצירת קוד exe ובכך לאפשר את ריצת קוד הפרויקט, גם על פלטפורמת stand alone ללא MATLAB.
חשוב לציין בנקודה זו, כי מלבד התוכנה הבסיסית MATLAB, יש צורך לרכשו שני כלים נוספים, המכילים ספריות ייעודיות בתחום עיבוד אות ועיבוד תמונה. הכלים הינם: Image Processing Toolbox, ו-Image Acquisition Toolbox. על-מנת לייצר קוד exe, יש לרכוש כלי נוסף בשם MATLAB Compiler.