גלאי פינה האריס

גלאי פינה 'האריס' (Harris corner detector) הוא אופרטור לזיהוי פינות המשמש בדרך כלל באלגוריתמים של ראייה ממוחשבת כדי לחלץ פינות ולהסיק לגבי עצמים (features) של תמונה. אופרטור זה הוצג לראשונה על ידי כריס האריס ומייק סטפנס בשנת 1988 כשיפור של גלאי הפינה של Moravec. בהשוואה לקודמו, לוקח גלאי הפינה של האריס בחשבון את ההפרש של ניקוד הפינה בהתייחסות ישירה לכיוון, במקום להשתמש בטלאים (patches) בהסטה עבור כל 45 מעלות, והוכח כמדויק יותר בהבחנה בין קצוות (edges) לפינות. מאז הוצג הוא שופר ואומץ באלגוריתמים רבים לעיבוד מקדים של תמונות.

מבוא עריכה

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

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

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

פיתוח אלגוריתם זיהוי פינות האריס עריכה

ללא הגבלת הכלליות, נניח שנעשה שימוש בתמונה דו-ממדית בגווני אפור (grayscale). תמונה הזו תסומן על ידי האות $I$ . שקול לקחת טלאי מהתמונה $(x,y)\in W$ (נקרא גם חלון) והזזתו על ידי $(\Delta x,\Delta y)$ . סכום ההבדלים בריבוע (SSD) בין שני הטלאים הללו, מסומן $f$ , ניתן ע"י:

f(\Delta x,\Delta y)={\underset {(x_{k},y_{k})\in W}{\sum }}\left(I(x_{k},y_{k})-I(x_{k}+\Delta x,y_{k}+\Delta y)\right)^{2}

ניתן להעריך את $I(x+\Delta x,y+\Delta y)$ על ידי הרחבה של טיילור. יהי $I_{x}$ ו $I_{y}$ , הנגזרות החלקיות של $I$ , כך ש:

I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y

זה מייצר את הקירוב:

f(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2},

ניתן לכתוב זאת בצורה מטריציונית:

f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},

כאשר M הוא טנזור המבנה ,

M={\underset {(x,y)\in W}{\sum }}{\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}{\underset {(x,y)\in W}{\sum }}I_{x}^{2}&{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}\\{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}&{\underset {(x,y)\in W}{\sum }}I_{y}^{2}\end{bmatrix}}

תהליך של אלגוריתם זיהוי פינות האריס עריכה

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

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

שינוי צבע התמונה לגווני אפור עריכה

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

ניתן לחשב את הערך של פיקסל בקנה מידה אפור כסכומים משוקללים של הערכים R, B ו-G של התמונה הצבעונית,

\sum _{C\,\in \,\{R,G,B\}}w_{C}\cdot C

,

לדוגמה,

w_{R}=0.299,\ w_{G}=0.587,\ w_{B}=1-(w_{R}+w_{G})=0.114.

חישוב נגזרת מרחבית עריכה

לאחר מכן, יש למצוא את הנגזרת ביחס ל-x ואת הנגזרת ביחס ל-y, $I_{x}(x,y)$ ו $I_{y}(x,y)$ .

על מנת לחשב נגזרות יש לבצע קונבולוציה עם מסכת נגזרת. עבור מסכה בגודל 3 יש להשתמש במסכה:

$\Delta _{y}=\left[{\begin{matrix}1\\0\\-1\end{matrix}}\right],\Delta _{x}=\left[{\begin{matrix}1&0&-1\end{matrix}}\right]$

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

$G(x,y;\sigma )={\frac {1}{2\pi \sigma ^{2}}}e^{-{\frac {x^{2}+y^{2}}{2\sigma ^{2}}}}$

עבור מסכת החלקה בגודל 3: $s=\left[{\begin{matrix}1&2&1\end{matrix}}\right]$

לכן מתקבל כי הנגזרות מחושבות לפי:

$I_{x}(x,y)=\Delta _{x}\cdot G\cdot I$ , $I_{y}(x,y)=\Delta _{y}\cdot G\cdot I$

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

עם $I_{x}(x,y)$ , $I_{y}(x,y)$ , ניתן ליצר את טנסור המבנה $M$ .

חישוב תגובת האריס עריכה

עבור $x\ll y$ , כאשר מתקיים ${\tfrac {x\cdot y}{x+y}}=x{\tfrac {1}{1+x/y}}\approx x$ . בשלב זה, אנו מחשבים את הערך העצמי הקטן ביותר של טנזור המבנה באמצעות הקירוב הזה:

\lambda _{\min }\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {\det(M)}{\operatorname {tr} (M)}}

עם העקבה $\mathrm {tr} (M)=m_{11}+m_{22}$ .

חישוב תגובת האריס נפוץ נוסף מוצג להלן,

$R=\lambda _{1}\lambda _{2}-k(\lambda _{1}+\lambda _{2})^{2}=\det(M)-k\operatorname {tr} (M)^{2}$

כאשר $k$ הוא קבוע שנקבע אמפירית, בדרך כלל בעל ערך $k\in [0.04,0.06]$ .

דיכוי לא-מקסימלי עריכה

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

בשלב זה נהוג לעשות שימוש בערך סף (threshold) על מנת לנטרל פינות בעלות עוצמה נמוכה.

שידרוגים עריכה

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

יישומים עריכה

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

ראו גם עריכה

ראייה ממוחשבת

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