התמרת האף

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

רקע

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

$y=\left(-{\cos \theta \over \sin \theta }\right)x+\left({r \over {\sin \theta }}\right)$

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

$r=x\cos \theta +y\sin \theta$

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

$r\in \mathbf {R}$ וגם- $\theta \in [0,\pi )$

או לחלופין:

$\theta \in [0,2\pi )$ וגם- $r\geq 0$

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

$r(\theta )=x_{0}\cos \theta +y_{0}\sin \theta$

או

$r(\theta )=|x_{0}\cos \theta +y_{0}\sin \theta |$

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

מימוש

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

$r=x\cos \theta +y\sin \theta$

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

ראו גם

• התמרת ראדון
• התמרת פורייה

קישורים חיצוניים

• המאמר המקורי של דודה והארט
• המאמר A short introduction to the Radon and Hough transforms and how they relate to each other באתר CiteSeerX.
• הסבר פשוט עם מימוש ודוגמה ויזואלית מהאתר של OpenCV
• הסבר קצר עם הדגמה אינטראקטיבית