התמרת האף

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

הַתְמָרַת הָאףאנגלית: Hough transform) היא שיטה למציאת אלמנטים (feature extraction) המשמשת בניתוח תמונה, ראייה ממוחשבת ועיבוד תמונה. מטרת האלגוריתם הוא מציאת מקרים לא מושלמים של אובייקטים בתוך סוג מסוים של צורות על ידי תהליך "הצבעה". הליך הצבעה זה מתבצע במרחב פרמטרים, שממנו אובייקטים "מועמדים" מתקבלים כמקסימום מקומי במרחב סוכם (Accumulator) הנבנה על ידי האלגוריתם. אלגוריתם האף בהגדרתו הראשונית עסק בזיהוי של קווים בתמונה, אך מאוחר יותר הורחב גם לזיהוי מיקומים של צורות כלשהן. הצורות הנפוצות ביותר בהקשר להתמרת האף הן מעגלים או אליפסות. האלגוריתם בצורתו הנוכחית, הומצא על ידי ריצ'רד דודה ופיטר הארט בשנת 1972 אשר נתנו לו את השם "התמרת האף מוכללת" (generalized Hough transform). וזאת לאחר הפטנט של פול האף אשר פורסם בשנת 1962. האלגוריתם צבר פופולריות בקרב מדעני ראייה ממוחשבת על ידי דנה באלארד בשנת 1981.

רקע[עריכת קוד מקור | עריכה]

בניתוח אוטומטי של תמונות דיגיטליות, מתעורר לעיתים קרובות הצורך בזיהוי צורות כגון קווים ישרים, עיגולים או אליפסות. במקרים רבים אלגוריתם לזיהוי קצה (Edge detection) יכול לשמש כשלב עיבוד מקדים כדי לזהות פיקסלים הנמצאים על העקומה הרצויה במרחב התמונה. בשל פגמים בתמונה או בזיהוי הקצוות עשויות להיות חסרות נקודות או פיקסלים על העקומות הרצויות, כמו גם סטיות מרחביות בין הקו / המעגל / האליפסה האידיאלית וכן נקודות רועשות. מסיבות אלה, לעיתים קרובות התאמה של הפיקסלים לקווים, עיגולים או אליפסות איננה משימה טריוויאלית. המטרה של אלגוריתם האף היא לטפל בבעיה זו באמצעות חיבור נקודות בתמונה לקבוצות של אובייקטים "מועמדים" על ידי ביצוע הליך הצבעה על סט של אובייקטי תמונה. המקרה הפשוט של האף הוא ההתמרה הליניארית למציאת קווים ישרים במרחב התמונה. קו ישר יכול להיות מתואר כy = mx + b כאשר m הוא השיפוע של הקו, ו-b היא נקודת המפגש עם ציר ה-y. רעיון מרכזי בהתמרת האף הוא ההתייחסות למאפיינים של הקו הישר לא כנקודות תמונה בדידות אלא במונחים של משוואת הישר הנ"ל. עם זאת, ישנה בעיה להכליל קווים אנכיים במודל זה (מכיוון שהם מתוארים באמצעות שיפוע m אינסופי,מכיוון שייצוג קו אנכי הוא x=a). לפיכך, מסיבות חישוביות, דודה והארט הציעו את השימוש בזוג שונה של פרמטרים, r ותטה עבור ייצוג של קווים באלגוריתם. שני ערכים אלה, מגדירים מרחב קוטבי. הפרמטר r מייצג את המרחק מראשית הצירים ותטא, היא הזווית של הווקטור מראשית הצירים לנקודה הקרובה ביותר אליו בישר. במרחב זה, קו ישר מיוצג על ידי המשוואה:

נסדר מחדש את המשוואה ונקבל:

ניתן, אפוא, לקשר כל קו ישר בתמונה עם זוג (r, θ) הייחודי לו במידה ו

וגם-

או לחלופין:

וגם-

המרחב (r, θ) מכונה לעיתים מרחב האף לקבוצה של קווים ישרים בשני ממדים. ייצוג זה הופך את התמרת האף מבחינת הגדרות לדומה להתמרת ראדון דו-ממדית. (ניתן לראותם כדרכים שונות לייצוג של אותה ההתמרה). תהי (X0, y0) נקודה במרחב התמונה. כל הקווים העוברים דרכה מיוצגים על ידי זוגות (r, θ) המקיימות

או

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

מימוש[עריכת קוד מקור | עריכה]

התמרת האף של קווים ישרים עושה שימוש במערך דו-ממדי, המכונה סוכם (Accumulator), כדי לזהות את קיומו של קו המיוצג על ידי

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]