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

:: . ::

מבוא

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

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

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

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

:: . ::

רקע פיזיקלי

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

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

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

:: . ::

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

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

למטרות חסכון, היה רצוי שהגלילים יהיו רחבים והפרוסות דקות כמה שיותר, בכדי שייוצרו מהחומר הנמצא יותר מעגלים. בפועל, שמירה על גבישיות הגליל קשה יותר ככל שהקוטר גבוה יותר. קטרים שנמצאים בשימוש כיום הם בין "1 ל-"12. עובי הפרוסה נקבע על פי חוזק החומר ועמידותו מפני שבירה בשל דקותו. עוביים נפוצים הם בין mµ 275ל-mµ775.

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

:: . ::

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

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

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

:: . ::

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

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

:: . ::

רקע מתמטי

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

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

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

:: . ::

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

:: . ::

התמונה הדיגיטלית
אם יכולנו לתאר תמונה כפי שאנחנו תופסים אותה, היינו מניחים כי היא מוגדרת בכל נקודה ובכל צבע. נקודה היינו מגדירים כזוג קואורדינטות (x,y) במרחב, וצבע בסקאלת גווני אפור היינו מגדירים כקואורדינטה שלישית על האינטרוול [0,1] כאשר 0 הוא הוא המינימום השחור ו-1 הוא המקסימום הלבן. במילים אחרות, היינו מניחים שהתמונה היא רציפה בתחומה על הגוונים, על פי הצורה:

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

כאשר כל רמת אפור תיוצג ב-L סיביות על ידי ההמרה:

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

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

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

:: . ::

סוגיות בדגימת התמונה
בשל מגבלות התמונה הדיגיטלית והצורך בשחזור מירבי שלה, רצויה רזולוציה גבוהה ככל הניתן. רזולוציה כזו תניב יותר נקודות דגימה, ועל ידי כך תיתן אינפורמציה רבה יותר על התמונה ותאפשר אף אחזור ברמות גבוהות יותר של מידע לא מוגדר. אלא שככל שהרזולוציה של התמונה יותר גדולה והיא מיוצגת על ידי יותר פיקסלים, או הפרדה גבוהה יותר של גוונים, שיידרשו יותר מקום אחסון של מידע על המחשב. לשם הדגמה, תמונה ברזולוציה של 320×256 פיקסלים וברמת גיוון של 256 צבעים, תהיה בגודל של 81,920 בתים (כל רמת צבע דורשת סיבית אחת). תמונה ברזולוציה של 640×512 פיקסלים, ברמת גיוון של 512 צבעים תדרוש 655,360 בתים.

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

:: . ::

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

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

1. 1. תמונה בשחור-לבן, רמות אפור בין 0 ל-255
   2. השינויים בתמונה הם גלובליים, ובכלל זה עיוותים והפרעות
   3. עיוותי הקואורדינטות שנעשו בתמונה הם אפיניים (Affine), בהגבלות הבאות:

א. אין שינויי הטיה(Shear), השינויים היחידים הם רק שינויי גודל (Zoom)
ב. השינויים הם בכל ציר בנפרד, בהזזה (Translation) ובשינוי גודל (Zoom)

1. השינויים אמנם אינם מוגדרים אך נתון שאינם גדולים
2. הרעשים המופעלים על התמונה הם רעשים גאוסיים בלבד (רעשים אדיטיביים)
3. התמונות נתונות ברזולוציה של 320×256 פיקסלים, ובהפרדה ל-256 רמות אפור.

:: . ::

ההתמרה האפינית
ההתמרה האפינית היא טרנספורם לינארי שבאמצעותו מתבצעים בתמונה שינויים שכוללים הזזה (Translation), סיבוב (Rotation), הגדלה/הקטנה (Scaling), ושיפוע (Tilt) בלבד. הפעולות אינן קומוטטיביות, ויש להן סדר מוגדר: שינוי גודל, סיבוב והזזה. הטרנספורם מוגדר כפונקציה:

כאשר: I כובע היא הנקודה בתמונת היציאה, I היא נקודה בתמונת הכניסה, S היא המטריצה המתארת שינוי גודל, R היא מטריצה המתארת סיבוב ו-T הוא ווקטור המתאר הזזה. כאשר תטא הוא אפס ו- t הוא אפס , אפקט ההטיה מנוטרל והפעולה תבצע שינויי Zoom בלבד, כאשר () יהיה השינוי בציר x ו-() יהיה השינוי בציר y. אם שני הגדלים שווים, מדובר בשינוי אחיד, שהוא למעשה סקלר ויאפשר שינוי סדר הפעולה לאחר הסיבוב. אם פרמטר יהיה גדול מ-1 תתבצע הגדלה, ואם קטן ממנו, תתבצע הקטנה. בכל מקרה מדובר בשינוי שגדול מ-0.

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

:: . ::

שיטות העבודה
ככלל, ניתן להבדיל את האלגוריתמים השונים של הרגיסטרציה לכמה משפחות, על פי שני קריטריונים: סוג האפיון וצורת האפיון. סוג האפיון יכול להיות של נקודות או צורות בודדות, סוג זה של אלגוריתמים נקרא באופן כללי מבוסס-מאפיינים (Feature-Based). סוג אחר של אפיון מפעיל פעולה כלשהיא על איזורים מוגדרים בתמונה, פעולות כמו התמרות, עיבודים סטטיסטיים וכו', סוג זה של אלגוריתמים נקרא באופן כללי מבוסס-איזור (Area-Based). צורת האפיון יכולה לבוא בביצוע פעולה ישירה על התמונה, או באמצעות חיפוש. אלגוריתמים הפועלים על בסיס ניסוי וטעיה מוגדרים מבוססי-חיפוש (Search-Based) ואלגוריתמים המגיעים ישירות לתוצאה על ידי ניתוח סטטיסטי גלובאלי מוגדרים ישירים (Direct Methods). בכל סוג אלגוריתם יתבצע מאמץ להקטין ככל היותר את מרחב הפעולה, על מנת לבצע אותו על תחום מצומצם ולזרז את החישוב. עם זאת ברור כי לכל אלגוריתם יתרונותיו וחסרונותיו, הכרוכים גם כן באורך פעולה, זמן החישוב והדיוק האפשרי.

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

1. קרוס-קורלציה: מציאת ההתאמה המירבית בין שתי התמונות בכלים סטטיסטיים, על בסיס ניסוי וטעיה. פעולות לוקאליות או גלובאליות, איטיות יחסית אך מגיעות לרוב לביצועים מצויינים.
2. שיטות המשתמשות במישור התדר: שימוש בתכונותיה של התמרת פוריה על מנת לבצע התאמה מהירה בין התמונות. ניתוח יחסים בין ההתמרות, למציאת גדלים בלתי תלויים המניבים את הפרמטרים של העיוות. שיטות מהירות אך מוגבלות.
3. Point Mapping: מציאת נקודות משותפות בשתי התמונות, מציאת סוג העיוות שנעשה על פי התאמה ביניהן. השיטות משתמשות בטכניות זיהוי עצמים שונות, מנתחות על פי רוב סביבות פיקסלים שונות בעזרת פעולות קונבולוציה, ומתחשבות בטבע התמונה.
4. Object Mapping: זיהוי תבניות אובייקטים בשתי התמונות והשוואה ביניהם בדרכים סטטיסטיות שונות. שיטה פופולרית בתחום הראיה הממוחשבת.

במאמר זה נתרכז בשיטת Point Mapping לאיתור נקודות זהות בשתי התמונות. נקודות אלה מכונות בספרות המקצועית Control Points (להלן: נקודות אחיזה), ומהוות את האינפורמציה המסייעת במציאת מודל העיוות. בעזרת המודל ההופכי ניתן יהיה לשחזר את התמונה. השיטה עצמה כוללת שני חלקים, האחד שמטפל בהפרעות שונות באמצעות פעולות ישירות על כל התמונה, והשני מטפל בעיוותי קואורדינטות ומשלב חיפוש על פי מאפיינים שאותרו בתמונה.

:: . ::

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

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

:: . ::

אלגוריתם הרגיסטרציה

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

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

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

:: . ::

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

:: . ::

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

:: . ::

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

א. פעולות היסטוגרמה
א.1 – מתיחת קונטרסט – פעולה זו מפעילה בכניסתה LUT לינארי. הפעולה שואפת לפיזור מירבי של רמות האפור על כל התחום, האפקט שנוצר הוא חידוד התמונה והדגשת האובייקטים.
א.2 – שיפור γ – פעולה זו מפעילה בכניסתה LUT אקספוננציאלי. הפעולה שואפת לטשטש הבדלים בקיצון אחד של סקאלת רמות האפור, ולהבליט את הקיצון השני. במידה ש-1< γ, הפעולה מטשטשת את ההבדלים ברמות האפור הנמוכות, והאפקט שנוצר הוא שיפור כהות התמונה, שיפור ניכר ככל שערך γ עולה. האפקט הנלווה לפעולה היא הפחתת מה של רעשים על אובייקטים בהירים. ההפחתה אמנם תלויה בחוזקם של הרעשים, אבל בין כה וכה ההבדלים ברמות אפור אלה, הנמוכות, יטושטשו ויאבדו ממשמעותם, ולכן לא חשובה מידת הרעש. במידה ש-1>γ, ההפך הוא הנכון.
א.3 – השוואת היסטוגרמה – פעולה זו מפעילה LUT עקמומי, שאינו לינארי. הפעולה שואפת להאחיד את ההיסטוגרמה על מנת לשוות לתמונה פיזור אידאלי בין כל הרמות, ולאפיין את ההיסטוגרמה המצטברת כשיפוע מונוטוני. בגלל האופי הבדיד של האות, ההאחדה לא תהיה אידאלית, ועל כן יופעל שיפור הפעולה, השוואת היסטוגרמה מסתגלת. טכניקות שונות מונעות תופעות לוואי של ההשוואה המסתגלת על ידי ריסון הניגודיות של סביבת הפיקסלים. טכניקות אלה נקראות CLAHE, ובהן נשתמש.

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

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

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

:: . ::

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

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

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

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

:: . ::

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

:: . ::

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

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

:: . ::

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

:: . ::

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

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

:: . ::

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

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

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

:: . ::

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

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

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

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

:: . ::

ניסויים, תוצאות ומסקנות

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

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

ברוב המקרים הגיע האלגוריתם לדיוק תת-פיקסל שיורד לרמות של למטה מ-0.1 פיקסל במקרים טיפוסיים, ורץ בזמן של כ-0.6 שניה. יעילות האלגוריתם בתמונה נקיה השתפרה פי 10 ויותר. בהינתן תוצאות אלה ראוי שוב להתחשב בתנאי העבודה ובסביבתה. כאמור, סביבת עבודה בטוחה ומבוקרת תמנע הפרעות קשות, ניתן להניח כי בחדר נקי סביבת העבודה אידאלית, ניתן להניח כי הרזולוציה של התמונות תהיה מיקרוסקופית וגדולה בהרבה וכי מעבדי המחשבים יהיו חזקים פי כמה, ולכן הביצועים עשויים להשתפר בסדרי גודל. עם התמונות שניתנו לנו הצלחנו להגיע לדיוק ממוצע של 0.01 פיקסל, כאשר בתמונות עם רעשים חזקים הגענו לדיוק של 0.07 פיקסל.

:: . ::

דיון

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

:: . ::

ייעול התוצאות והצעות עתידיות
• מציאת קודקודים בדרך יעילה יותר עשויה להניב תוצאות מדויקות יותר. כמה מהדרכים לאיתור נקודות אלה הן חיתוך קווים ישרים שהתגלו ע"י התמרות hough ו- radon, או זיהוי נקודות השפה הקיצוניות ביותר.
• ניתן לזהות מאפיינים ולהשוות אותם על פי מדדים אחרים כגון: דמיון בין זוויות, דמיון בין עקמומיות, טופוגרפיה זהה של התמונה. במקרים אלה הנקודות שיאותרו יהיו שונות ואחרות.
• הרצה בשפת סף, תשפר את ביצועי האלגוריתם משמעותית. הרצה על מהדר משוכלל ולא בסקריפט שלו (C++/Java ולא MATLAB) עשויה להועיל באופן מיידי.
• ניתוח תמונות ברזולוציה גבוהה יותר מזו המינימלית שבה נעשה פרוייקט זה עשוי לתרום לדיוק האלגוריתם. הרצה על מעבד משוכלל יותר, תפתור את בעיית כובד התמונה והאטת זמן ההרצה.
• שימוש בטכניקות מתקדמות יותר של עיבוד תמונה עשויות להועיל בתהליכים כמו שיפור התמונה, הפקת המאפיינים, זיהוי המאפיינים, אינטרפולציה וכו'. טכניקות אלה (Total Variation Filtering, Curvature Flow, Wavelet Pyramids וכו') דורשות רקע תיאורטי נרחב יותר, ומסובכות יותר ליישום בכלים שבהם נעשה פרוייקט זה.
• שימוש בשיטות אינטרפולציה מסובכות מ-Bicubic Spline יהיו אמנם איטיות יותר, אך מדויקות יותר. תכנות של שיטות כאלה מתקדם ומורכב יותר, ואופטימיזציה שלו תהיה קשה יותר.

:: . ::

ביבליוגרפיה
1. אלעד מ., עיבוד תמונות (2003). ספר הקורס, טכניון, 236860
2. טרמין, י., עיבוד תמונה – יישומים (2006). מצגת הקורס, אונ' בר-אילן, 89-670
3. ברלב, א. וגולן ג., התקני מוליכים למחצה ומיקרואלקטרוניקה (2000), האוניברסיטה הפתוחה, ספר הקורס 20403.
4. L. G. Brown, A survey of image registration techniques, ACM Computing Surveys CM Comput. Surv., Vol. 24, No. 4. (December 1992), p. 325-376.
5. Zitova, B. and Flusser, J., Image registration methods: a survey. Image Vis. Comput. v21 i11. 977-1000 (2003)
6. Blanchet G. & Charbit M., Digital Signal & Image Processing Using MATLAB (2006), ISTE Publishing Company, London UK
7. Van Zeghbroeck, Bart J., "Principles of Semiconductor Devices", University of Colorado at Baulder, 1999

:: . ::

נספח א' – הפוטו-ליתוגרפיה

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

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

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

השלבים לא מבוצעים בסדר מסוים, וכל אחד מהם נעשה בהתאם לצרכים:
1. ציפוי בפוטו-רזיסט: הפרוסה מצופה בחומר הרגיש לאור, שנקרא photo-resist. חומר זה ישנה את תכונותיו בהתאם לחשיפתו לאור, צריבה שלו תשנה את תכונותיו החשמליות של האיזור שנחשף. על מנת לחסום את החלק שרוצים "להגן" עליו מפני שימוש, מניחים עליו מסכה מותאמת.
2. צריבה: כאמור, לאחר הציפוי והשמת המסיכה, מבצעים את הצילום עצמו. הצילום הוא למעשה חשיפה לאור, צעד אשר ישפיע על התכונות החשמליות של חצי-המוליך.
3. חמצון תרמי: פעולה זו מגדלת שכבה מבודדת דקה על פני הפרוסה, על ידי חימצון הסיליקון והפיכתו לסיליקון דו-חמצני (SiO2). בכדי לזרז את התהליך מבצעים חמצון תרמי, בטמפרטורה גבוהה מאוד.
4. איכול: חומר מאכל רק את החלקים הרצויים בפוטו-רזיסט, ובתוך כך גם את שכבת המבודד. בצורה זו נוצרים חללים בשכבת המבודד, שדרכם יוטבעו הטרנזיסטורים ויושמו החיבורים המוליכים.
5. סימום: על ידי הוספת זיהומים לשכבת המוליך למחצה, בדרך כלל באמצעות השתלת יונים, יוצרים דיפוזיה שתשנה את המוליכות, ותיצור את מרכיבי הטרנזיסטורים.
6. דפוזיציה: להשלמת התהליך משימים שכבות נוספות של חומרים שונים, על פני הבסיס. שערים נוצרים על ידי פוליסיליקון, החיבורים על ידי מתכות מוליכות.
7. סילוק פסולת: תהליך זה "שוטף" את הפרוסה משאריות וסיבים של השכבות הנוספות. הניקוי הכרחי למטרות החלקה של השכבה, אי החלקה תפגע במתאר ותפריע השמת שכבות נוספות.

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

:: . ::

נספח ב' – אינטרפולציית Bicubic Spline

אחת משיטות האינטרפולציה המתקדמות והפופולריות ביותר היא Bicubic Spline (לפעמים: Cubic B-Spline). מה שהופך אותה לפופולרית כל כך הוא בעיקר הדיוק הטוב שלה לעומת שיטות פולינומיאליות אחרות, והפשטות היחסית שלה לעומת שיטות מתקדמות אחרות. קל לתכנת אותה, הדיוקים שלה סבירים, היא רובסטית לרעשים, והתמונה שהיא נותנת חלקה בהרבה מאינטרפולציות "פשוטות".

מהו Spline ; זוהי פונקציה פולינומיאליות בחלקים, המרכיבה עקומה המשחזרת את הרצף בין ארבע נקודות הקצה של הפיקסל. הרצף כאמור יהיה "חלק" יחסית, חלקות תתבטא בנגזרת שניה בעלת עקמומיות מוקטנת. פולינומי ה-Spline הם ממעלה מסויימת M, ביניהם קיימות נקודות חיבור (knot) והתנאי הנדרש הוא רציפות בכל הנגזרות עד למעלה M-1. דרגה שכיחה של הפולינומים הללו היא סדר שלישי (כלומר M=3), ו-Splines מסוג זה נקראים קוביים (cubic). הכללה של אלה לשני מימדים תקרא בי-קובי (bicubic). אינטרפולציית ספליין בי-קובית, תשתמש בצורת קירוב זו על מנת להגדיר את הסריג ברמת תת הפיקסל.

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

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

:: . ::

נספח ג' – רעש ומסננים

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

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

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

כאשר x הוא המרחק מהגרעין, ו-σ הוא "סטיית התקן", שתקבע את עוצמת המסנן. העוצמה המקסימלית, כלומר ∞→σ תשאיף את המסנן למסנן ממוצע, והעוצמה המינימלית 0→σ תהפוך אותו למעשה לחסר השפעה, מסנן יחידה שנותן משקל רק לפיקסל הגרעין ולא מסנן בכלל. דוגמא ממסנן ברוחב 3×3.

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

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

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

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

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