התמרת האף

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

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

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

רקע

בניתוח אוטומטי של תמונות דיגיטליות, מתעורר לעיתים קרובות הצורך בזיהוי צורות כגון קווים ישרים, עיגולים או אליפסות. במקרים רבים אלגוריתם לזיהוי קצה (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$ שיוצא מראשית הצירים בזווית $\theta$ הוא מאונך לישר שאותו אנו רוצים לייצג. קל לראות שנקודת המפגש בין הקו האנכי והישר היא $(r\cos \theta ,r\sin \theta )$. נסמן נקודה זו כ-$P_{0}$. נשים לב כי $P_{0}$ היא גם וקטור שמייצג את הקו באורך $r$, שכן הוא יוצא מראשית הצירים. כעת, נשים לב כי לכל נקודה $P=(x,y)$ על הישר, הווקטור מהנקודה $P_{0}$ לנקודה $P$, כלומר, הווקטור $P-P_{0}$, חייב להיות אנכי לוקטור $P_{0}$, מפני שהוא נמצא על הישר. לכן, מפני ששני הווקטורים הם אורתוגונליים, נקבל $(P-P_{0})\cdot P_{0}=0$. לאחר פתיחת הסוגריים והעברת אגף, נקבל $P\cdot P_{0}=P_{0}\cdot P_{0}$. נציב את ערכי הנקודות ונקבל $r(x\cos \theta +y\sin \theta )=r^{2}(\cos ^{2}\theta +\sin ^{2}\theta )$. לאחר שנצמצם ב-$r$ משני הצדדים ונשתמש בזהות $\sin ^{2}\theta +\cos ^{2}\theta =1$, נקבל את הנוסחה הסופית, שהיא $x\cos \theta +y\sin \theta =r$.

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

ניתן, אפוא, לקשר כל קו ישר בתמונה עם זוג (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 וציר נוסף המייצג את θ. לכל תא במערך ערך מסוים והתאים בעלי הערכים הגבוהים ביותר מייצגים את הקווים האינדיקטיביים ביותר בתמונה.

ראו גם

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

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

מדיה וקבצים בנושא התמרת האף בוויקישיתוף

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