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

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

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

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

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

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

: <math>
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
</math>

ניתן להעריך את <math>I(x+\Delta x,y+\Delta y)</math> על ידי הרחבה של טיילור. יהי <math> I_x</math> ו <math> I_y</math>, הנגזרות החלקיות של <math> I</math>, כך ש:

: <math>
I(x+\Delta x,y+\Delta y) \approx I(x,y) + I_x(x,y)\Delta x+I_y(x,y)\Delta y
</math>

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

: <math>
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,
</math>

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

: <math>
f(\Delta x,\Delta y) \approx \begin{pmatrix} \Delta x & \Delta y \end{pmatrix} M \begin{pmatrix} \Delta x \\ \Delta y \end{pmatrix},
</math>

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

: <math>
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}
</math>

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

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

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

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

: <math>\sum_{C\,\in\,\{R,G,B\}} w_C \cdot C</math> ,

לדוגמה,

: <math>w_R=0.299,\ w_G=0.587,\ w_B=1-(w_R+w_G)=0.114.</math>

=== חישוב נגזרת מרחבית ===
לאחר מכן, יש למצוא את הנגזרת ביחס ל-x ואת הנגזרת ביחס ל-y, <math>I_x( x, y)</math> ו <math>I_y( x, y)</math> .

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

<math>\Delta_y = \left [\begin{matrix} 1 \\ 0 \\ -1 \end{matrix} \right ], \Delta_x = \left [\begin{matrix} 1 & 0 & -1 \end{matrix} \right ]</math>

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

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

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

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

<math>I_x( x, y) = \Delta_x\cdot G \cdot I </math>, <math>I_y( x, y) = \Delta_y\cdot G \cdot I
 </math>

=== הגדרת טנזור מבנה ===
עם <math> I_x( x, y)</math>, <math> I_y( x, y) </math>, ניתן ליצר את טנסור המבנה <math> M </math> .

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

: <math> \lambda _{\min} \approx \frac{ \lambda _1 \lambda _2} {(\lambda _1+\lambda _2)} = \frac{\det(M)} {\operatorname{tr}(M)} </math>

עם העקבה <math>\mathrm{tr}(M) = m_{11} + m_{22} </math> .

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

<math> R = \lambda _1 \lambda _2 - k(\lambda _1 + \lambda _2)^2 = \det(M) - k\operatorname{tr}(M)^2</math>

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

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

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

== שדרוגים ==

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

== יישומים ==

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

== ראו גם==
* ראייה ממוחשבת
*
קטגוריה:ראייה ממוחשבת