שיטת לוקאס-קנאדה

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

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

עקרון הפעולה

שיטת לוקאס-קנאדה מניחה כי תזוזה של תוכן התמונה בתוך סביבה של פיקסל p בין שני מופעים (פריימים) סמוכים היא קטנה וכמעט קבועה. לפיכך, ניתן להניח כי משוואת הזרימה האופטית תתקיים עבור כל הפיקסלים בתוך חלון W שממוקם כך ש-p במרכזו. כלומר, ניתן לחשוב על הזרימה האופטית המקומית בתמונה בתור וקטור מהירות $(V_{x},V_{y})$ אשר חייב לקיים $${\displaystyle \forall i\in {1,...,n}:I_{x}(q_{i})V_{x}+I_{y}(q_{i})V_{y}=-I_{t}(q_{i})}$$

כאשר $q_{1},q_{2},\dots ,q_{n}$ הם פיקסלים בחלון W ו-$I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})$ הם הנגזרות החלקיות של התמונה I שמוערכות על הפיקסל $q_{i}$ בנקודת זמן t - ביחס לציר ה-x, ציר ה-y וציר הזמן t, בהתאמה.

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

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

$$\sum _{q\in W}\left(I\left(q\right)-I_{t}\left(q+V\right)\right)^{2}$$

כאשר V הוא וקטור המהירות של התנועה בין התמונה $I$ אל $I_{t}$, ו-q הוא פיקסל כלשהו מתוך החלון W שבו מוערכת הזרימה האופטית. מההנחה שV הוא קטן יחסית בין מופעים סמוכים, ניתן להשתמש בקירוב טיילור מדרגה ראשונה כך ש:

$$I_{t}\left(q+V\right)\cong I_{t}\left(q\right)+{\frac {\partial I_{t}^{T}}{\partial q}}V$$

ומכאן ניתן לרשום את V באופן מפורש:

$$V=\sum _{q\in W}\left(I\left(q\right)-I_{t}\left(q\right)\right){\frac {\partial I_{t}}{\partial q}}\left[\sum _{q\in W}{\frac {\partial I_{t}}{\partial q}}\cdot {\frac {\partial I_{t}^{T}}{\partial q}}\right]^{-1}$$

חלון ממושקל

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

תנאים להצלחה

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

שיפורים והרחבות

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

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

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

• העמוד של טאקאו קנאדה באוניברסיטת Carnegie Mellon.
• קוד ++C המשתמש בשיטת לוקאס קנאדה כדי למצוא זרימה אופטית.
• קוד Python המשתמש בשיטת לוקאס-קנאדה כדי למצוא זרימה אופטית.
• קוד Python המשתמש בשיטת לוקאס קנדה באלגוריתם עקיבה למציאת הומוגרפיה.