משתמש:לחכםגל/מטריצה יסודית

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.

בראייה ממוחשבת, המטריצה היסודית (essential matrix) היא מטריצה $\mathbf {E}$ בגודל $3\times 3$ המייצגת נקודות מתאימות בתמונות סטריאו בהנחה שהמצלמות עומדות במודל של מצלמת נקב (pinhole) .

מקרה פרטי של המטריצה הבסיסית (fundamental matrix). היסטורית, המטריצה היסודית הוכרה טרם המינוח של מטריצה בסיסית.

ראה גם [1]

הגדרה

תיאור כללי של המצב. שתי מצלמות הממוקמות במרחק מה זו מזו המתבוננות לעבר אותו המקום, ונבדלות ביניהן בהעתק וסיבוב, ומכויילות כהלכה. הנקודות $x,x'$ נקראות קואורדינטות תמונה מתאימות, כהיטלים על שני מישורי התמונה של אותה נקודה $X$

ליתר דיוק, אם $\mathbf {x}$ ו $\mathbf {x} '$ הם קואורדינטות תמונה מנורמלות הומוגניות בתמונה 1 ו-2, בהתאמה, אז

$(\mathbf {x} ')^{\top }\,\mathbf {E} \,\mathbf {x} =0$

כאשר $\mathbf {x}$ ו $\mathbf {x} '$ תואמות לאותה נקודה תלת מימדית בסצנה (לא "אם ורק אם" בגלל העובדה שנקודות שנמצאות על אותו קו אפיקוטבי בתמונה הראשונה ימופו לאותו קו אפיקוטבי בתמונה השנייה).

הקשר לעיל המגדיר את המטריצה פורסם בשנת 1981 על ידי H. Christopher Longuet-Higgins, שהציג את המושג לקהילת הראייה הממוחשבת בעבודת סמינר. ספרם של ריצ'רד הארטלי ואנדרו זיסרמן מדווח שמטריצה מקבילה הופיעה בפוטוגרמטריה הרבה לפני כן. המאמר של Longuet-Higgins כולל אלגוריתם לאומדן המטריצה $\mathbf {E}$ מתוך קבוצה של קואורדינטות תמונה מנורמלות מתאימות (כלומר, זוגות של נקודות מהצורה $\wr (x,y,1),(x\prime ,y\prime ,1)\wr$ במערכות הקואורדינטות של שתי המצלמות המתארות אותה נקודה במציאות).

כמו כן, כלולה שיטה לחישוב המיקום והכיוון היחסי של שתי המצלמות בהתחשב בכך ש $\mathbf {E}$ ידוע. לבסוף, הוא מראה כיצד ניתן לקבוע את הקואורדינטות התלת-ממדיות של נקודות התמונה בעזרת המטריצה הבסיסית.

המטריצה הבסיסית (Fundamental)

ניתן לראות את המטריצה החיונית כמטריצה הבסיסית, $\mathbf {F}$ . ניתן להשתמש בשתי המטריצות לקביעת אילוצים בין נקודות תמונה תואמות, אך ניתן להשתמש במטריצה הבסיסית רק ביחס למצלמות מכוילות - כלומר הפרמטרים (מטריצות $\mathbf {K}$ ו $\mathbf {K} '$ ) חייבים להיות ידועים על מנת להשיג את הנורמליזציה. עם זאת, אם המצלמות מכוילות, המטריצה היסודית יכולה להיות שימושית לקביעת המיקום והכיוון (היחסי) בין המצלמות, והן את המיקום התלת-ממדי של נקודות מתאימות בין תמונות. המטריצה היסודית קשורה למטריצה הבסיסית (fundamental) על ידי פרמטרי כיול (calibration)

$\mathbf {E} =({\mathbf {K} '})^{\top }\;\mathbf {F} \;\mathbf {K} .$

פיתוח והגדרה

פיתוח זה בא בעקבות המאמר של Longuet-Higgins.

שתי מצלמות מנורמלות מקרינות את עולם התלת-ממד על מישורי התמונה שלהן. אם הקואורדינטות התלת-ממדיות של נקודה P הנן $(x_{1},x_{2},x_{3})$ ו $(x'_{1},x'_{2},x'_{3})$ ביחס למערכת הקואורדינטות של כל מצלמה, מכיוון שהמצלמות מנורמלות, קואורדינטות התמונה המתאימות הן

${\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\frac {1}{x_{3}}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}$ ו ${\begin{pmatrix}y'_{1}\\y'_{2}\end{pmatrix}}={\frac {1}{x'_{3}}}{\begin{pmatrix}x'_{1}\\x'_{2}\end{pmatrix}}$

ייצוג הומוגני של שתי קואורדינטות התמונה ניתן לאחר מכן על ידי

${\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}={\frac {1}{x_{3}}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}$ ו ${\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}={\frac {1}{x'_{3}}}{\begin{pmatrix}x'_{1}\\x'_{2}\\x'_{3}\end{pmatrix}}$

שגם ניתן לכתוב בצורה קצרה יותר

$\mathbf {y} ={\frac {1}{x_{3}}}\,{\tilde {\mathbf {x} }}={\frac {1}{x_{3}}}\,{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}$ 

 $\mathbf {y} '={\frac {1}{x'_{3}}}\,{\tilde {\mathbf {x} }}'={\frac {1}{x'_{3}}}\,{\begin{pmatrix}x'_{1}\\x'_{2}\\x'_{3}\end{pmatrix}}$

כאשר $\mathbf {y}$ ו $\mathbf {y} '$ הם ייצוגים הומוגניים של קואורדינטות התמונה הדו-ממדיות ו ${\tilde {\mathbf {x} }}$ ו ${\tilde {\mathbf {x} }}'$ הן קואורדינטות תלת מימדיות נכונות אבל בשתי מערכות קואורדינטות שונות.

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

${\tilde {\mathbf {x} }}'=\mathbf {R} \,({\tilde {\mathbf {x} }}-\mathbf {t} )$

כאשר $\mathbf {R}$ היא מטריצת סיבוב בגודל $3\times 3$ ו $\mathbf {t}$ הוא וקטור הזזה תלת מימדי.

המטריצה היסודית מוגדרת כך:

$\mathbf {E} =\mathbf {R} \,[\mathbf {t} ]_{\times }$

$[\mathbf {t} ]_{\times }={\begin{pmatrix}0&-t_{z}&t_{y}\\t_{z}&0&-t_{x}\\-t_{y}&t_{x}&0\end{pmatrix}}$ כאשר $[\mathbf {t} ]_{\times }$ הוא ייצוג כמטריצה של מכפלה וקטורית עם $\mathbf {t}$, כלומר היא מטריצה אנטי-סימטרית בגודל $3\times 3$ המוגדרת כך

$[\mathbf {t} ]_{\times }={\begin{pmatrix}0&-t_{z}&t_{y}\\t_{z}&0&-t_{x}\\-t_{y}&t_{x}&0\end{pmatrix}}$

הכפלה ב $[\mathbf {R} ^{T}|\mathbf {t} ]$ תהפוך נקודות בתצוגה השנייה לתצוגה הראשונה.

להגדרה של $\mathbf {E}$ אנו מתעניינים רק בכיוונם של קואורדינטות התמונה המנורמלות (מכפלה מעורבת). לכן איננו זקוקים לרכיב התרגום בעת החלפת קואורדינטות תמונה במשוואה החיונית.

ניתן לראות שההגדרה הזו של $\mathbf {E}$ מתארת אילוץ על כפל זוגות נקודות מתאימות בשתי התמונות משמאל ומימין עם הקואורדינטות התלת-ממדיות של נקודה P בשתי מערכות הקואורדינטות השונות:

${\tilde {\mathbf {x} }}'^{T}\,\mathbf {E} \,{\tilde {\mathbf {x} }}\,{\stackrel {(1)}{=}}\,{\tilde {\mathbf {x} }}^{T}\,\mathbf {R} ^{T}\,\mathbf {R} \,[\mathbf {t} ]_{\times }\,{\tilde {\mathbf {x} }}\,{\stackrel {(2)}{=}}\,{\tilde {\mathbf {x} }}^{T}\,[\mathbf {t} ]_{\times }\,{\tilde {\mathbf {x} }}\,{\stackrel {(3)}{=}}\,0$

1. על פי הקשר בין ${\tilde {\mathbf {x} }}'$ ו ${\tilde {\mathbf {x} }}$ וההגדרה של $\mathbf {E}$ במונחים של $\mathbf {R}$ ו $\mathbf {t}$ .
2. $\mathbf {R} ^{T}\,\mathbf {R} =\mathbf {I}$ היות ו $\mathbf {R}$ היא מטריצת סיבוב אורתוגונלית.
3. תכונות המכפלה המעורבת.

לבסוף, ניתן להניח ששניהם $x_{3}$ ו $x'_{3}$ הם > 0, אחרת הם לא נראים בשתי המצלמות. זה נותן

$0=({\tilde {\mathbf {x} }}')^{T}\,\mathbf {E} \,{\tilde {\mathbf {x} }}={\frac {1}{x'_{3}}}({\tilde {\mathbf {x} }}')^{T}\,\mathbf {E} \,{\frac {1}{x_{3}}}{\tilde {\mathbf {x} }}=(\mathbf {y} ')^{T}\,\mathbf {E} \,\mathbf {y}$

שהוא האילוץ שהמטריצה מגדירה בין נקודות תמונה מתאימות.

תכונות

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

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

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

אם המטריצה החיונית $\mathbf {E}$ מוכפלת בסקלר שאינו אפס, התוצאה היא שוב מטריצה חיונית המגדירה בדיוק את אותו אילוץ כמו $\mathbf {E}$. זה אומר שאת $\mathbf {E}$ ניתן לראות כמוגדרת עד כדי כפל בסקלר. זה יכול להיות שימושי, למשל, אם $\mathbf {E}$ מוערכת מתוך זוגות של תמונות. עם זאת, אפשר גם לנקוט בעמדה כזו $\mathbf {E}$ זה מוגדר כ

$\mathbf {E} =[\mathbf {\widetilde {t}} ]_{\times }\,\mathbf {R}$

כאשר $\mathbf {\widetilde {t}} =-\mathbf {R} \mathbf {t}$, ואז $\mathbf {E}$ יש "קנה מידה" מוגדר היטב. תלוי בבקשה איזו משרה רלוונטית יותר.

האילוצים יכולים להתבטא גם כ

$\det \mathbf {E} =0$

$2\mathbf {E} \mathbf {E} ^{T}\mathbf {E} -\operatorname {tr} (\mathbf {E} \mathbf {E} ^{T})\mathbf {E} =\mathbf {0} _{3\times 3}.$

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

למטריצה היסודית יש חמש או שש דרגות חופש, תלוי אם היא נקבעת עד כדי כפל בסקלר. למטריצת הסיבוב הסימטרית $\mathbf {R}$ ולקטור ההזזה $\mathbf {t}$ יש שלוש דרגות חופש לכל אחד, בסך הכל שש. אם המטריצה היסודית מחושבת עד כדי כפל בסקלר, יש לגרוע דרגת חופש אחת הקשורה לכפל סקלרי ולהשאיר חמש דרגות חופש בסך הכל.

אוּמדָן

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

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

חילוץ סיבוב והזזה

בהתחשב בכך שהמטריצה נקבעת עבור stereo imaging - למשל, באמצעות שיטת האומדן לעיל - ניתן להשתמש במידע זה גם לקביעת הסיבוב $\mathbf {R}$ ו$\mathbf {t}$ (כיוון בלבד של הסיבוב) בין מערכות הקואורדינטות של שתי המצלמות. במצב זה $\mathbf {E}$ מחושבת עד כדי סקלר במקום בעלת קנה מידה מוגדר היטב. נציין שהיות ואנו לא יודעים את המרחק בין המצלמות לאובייקט המצולם, אין אפשרות לדעת את $\mathbf {t}$ במדויק אלא רק עד כדי קבוע ("up to scale").

מציאת פתרון

השיטה הבאה לקביעה $\mathbf {R}$ ו $\mathbf {t}$ מבוססת על ביצוע SVD - פירוק לערכים סינגולריים של $\mathbf {E}$ . אפשר גם לקבוע $\mathbf {R}$ ו $\mathbf {t}$ ללא SVD.

פירוק זה של $\mathbf {E}$ הנו

$\mathbf {E} =\mathbf {U} \,\mathbf {\Sigma } \,\mathbf {V} ^{T}$

כאשר $\mathbf {U}$ ו $\mathbf {V}$ הן מטריצות אורתוגונליות בגודל $3\times 3$ מטריצות ו $\mathbf {\Sigma }$ הנה מטריצה אלכסונית עם

$\mathbf {\Sigma } ={\begin{pmatrix}s&0&0\\0&s&0\\0&0&0\end{pmatrix}}$

הערכים האלכסוניים של $\mathbf {\Sigma }$ הם הערכים הייחודיים של $\mathbf {E}$ שעל פי האילוצים הפנימיים של המטריצה היסודית, חייב להיות מורכב משני ערכים זהים וערך אפס אחד. אם נגדיר

$\mathbf {W} ={\begin{pmatrix}0&-1&0\\1&0&0\\0&0&1\end{pmatrix}}$ עם $\mathbf {W} ^{-1}=\mathbf {W} ^{T}={\begin{pmatrix}0&1&0\\-1&0&0\\0&0&1\end{pmatrix}}$

ולעשות את המכפלה הבאה

$[\mathbf {t} ]_{\times }=\mathbf {U} \,\mathbf {W} \,\mathbf {\Sigma } \,\mathbf {U} ^{T}$

$\mathbf {R} =\mathbf {U} \,\mathbf {W} ^{-1}\,\mathbf {V} ^{T}$

היות וייתכן ש $\mathbf {\Sigma }$ לא תמלא לחלוטין את האילוצים כאשר עוסקים בנתונים מהעולם האמיתי (למשל תמונות מצלמה), האלטרנטיבה

$[\mathbf {t} ]_{\times }=\mathbf {U} \,\mathbf {Z} \,\mathbf {U} ^{T}$ עם $\mathbf {Z} ={\begin{pmatrix}0&1&0\\-1&0&0\\0&0&0\end{pmatrix}}$

יכולה לעזור ^{[דרוש מקור][מפני ש...]}

הוכחת נכונות השיטה

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

ראשית, ביטויים אלה עבור $\mathbf {R}$ ו $[\mathbf {t} ]_{\times }$ אכן ממלאים את המשוואה המגדירה עבור המטריצה החיונית

$[\mathbf {t} ]_{\times }\,\mathbf {R} =\left(\mathbf {U} \,\mathbf {W} \,\mathbf {\Sigma } \,\mathbf {U} ^{T}\right)\left(\mathbf {U} \,\mathbf {W} ^{-1}\,\mathbf {V} ^{T}\,\right)=\mathbf {U} \,\mathbf {\Sigma } \,\mathbf {V} ^{T}=\mathbf {E}$

שנית, יש להוכיח ש $[\mathbf {t} ]_{\times }$ הוא ייצוג מטריציוני של תוצר הצלב עבור חלק $\mathbf {t}$ . מאז

$\mathbf {W} \,\mathbf {\Sigma } ={\begin{pmatrix}0&-s&0\\s&0&0\\0&0&0\end{pmatrix}}$

זה המקרה ש $\mathbf {W} \,\mathbf {\Sigma }$ הוא סימטרי הטיה, כלומר, $(\mathbf {W} \,\mathbf {\Sigma } )^{T}=-\mathbf {W} \,\mathbf {\Sigma }$ . זה המצב גם אצלנו $[\mathbf {t} ]_{\times }$, מאז

$([\mathbf {t} ]_{\times })^{T}=\mathbf {U} \,(\mathbf {W} \,\mathbf {\Sigma } )^{T}\,\mathbf {U} ^{T}=-\mathbf {U} \,\mathbf {W} \,\mathbf {\Sigma } \,\mathbf {U} ^{T}=-[\mathbf {t} ]_{\times }$

לפי המאפיינים הכלליים של מכפלה וקטורית מתחייב ש $[\mathbf {t} ]_{\times }$ חייב להיות האופרטור צולב התוצר של וקטור אחד בדיוק $\mathbf {t}$ .

שלישית, יש צורך גם להראות שהביטוי לעיל עבור $\mathbf {R}$ היא מטריצת סיבוב. זה מכפלה של שלוש מטריצות שכולן אורתוגונליות מה שאומר ש $\mathbf {R}$, גם הוא אורתוגונלי, כלומר $\det(\mathbf {R} )=\pm 1$ . כדי להיות מטריצת סיבוב היא חייבת גם לספק $\det(\mathbf {R} )=1$. מאחר שבמקרה זה, $\mathbf {E}$ מוגדרת עד כדי סקלר ולכן ניתן להשיג זאת על ידי היפוך הסימן של $\mathbf {E}$ אם נחוץ.

מציאת כל הפתרונות

עד כאן פתרון אפשרי אחד עבור $\mathbf {R}$ ו $\mathbf {t}$ הוקם נתון $\mathbf {E}$ . עם זאת, זה לא הפתרון האפשרי היחיד ואולי אפילו לא יהיה פתרון תקף מנקודת מבט מעשית. מלכתחילה, היות שקנה המידה של $\mathbf {E}$ אינו מוגדר, קנה המידה של $\mathbf {t}$ הוא גם לא מוגדר. עם זאת, הוא חייב להיות במרחב הפתרונות (גרעין) של $\mathbf {E}$ הואיל ו

$\mathbf {E} \,\mathbf {t} =\mathbf {R} \,[\mathbf {t} ]_{\times }\,\mathbf {t} =\mathbf {0}$

לניתוח הבא שנציג של הפתרונות, לעומת זאת, ערכו המדויק של $\mathbf {t}$ לא כל כך חשוב כמו ה"סימן" שלו, כלומר לאיזה כיוון הוא מצביע. אם ${\hat {\mathbf {t} }}$ הוא וקטור מנורמל בגרעין של $\mathbf {E}$ אז הן ${\hat {\mathbf {t} }}$ ו $-{\hat {\mathbf {t} }}$ הם וקטורי הזזה חוקיים עבור $\mathbf {E}$ . אפשר גם לשנות $\mathbf {W}$ לְתוֹך $\mathbf {W} ^{-1}$ בפיתוחים של $\mathbf {R}$ ו $\mathbf {t}$ מֵעַל. עבור וקטור התרגום זה רק גורם לשינוי סימן, שכבר תואר כאפשרות. עבור הסיבוב, לעומת זאת, זה ייצור טרנספורמציה אחרת, לפחות במקרה הכללי.

לסיכום, בהינתן $\mathbf {E}$ ישנם שני כיוונים מנוגדים אשר ייתכנו עבור $\mathbf {t}$ ושני סיבובים שונים התואמים את המטריצה היסודית הזו. בסך הכל זה נותן ארבעה סוגים של פתרונות לסיבוב והזזה בין שתי מערכות הקואורדינטות של המצלמות. נוסף על כך, יש גם קנה מידה לא ידוע $s>0$ לכיוון ההזזה הנבחר.

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

הקביעה לעיל של $\mathbf {R}$ ו $\mathbf {t}$ מניחה שעל $\mathbf {E}$ לעמוד באילוצים הפנימיים של המטריצה החיונית,מה שלא בהכרח מתקיים במלואו. למשל, אם $\mathbf {E}$ נאמדת מנתוני תמונה אמיתיים (ורועשים), יש להניח שהם עומדים בערך באילוצים הפנימיים. הווקטור ${\hat {\mathbf {t} }}$ לאחר מכן נבחר כווקטור יחיד ימני של $\mathbf {E}$ המתאים לערך הסינגולרי הקטן ביותר.

חישוב נקודות תלת מימדיות

קיימות שיטות רבות לחישוב $(x_{1},x_{2},x_{3})$ על ידי קואורדינטות תמונה מנורמלות מתאימות $(y_{1},y_{2})$ ו $(y'_{1},y'_{2})$, המתבססות על המטריצה היסודית.

ראה גם

• גיאומטריה אפיפולרית
• מטריצה בסיסית
• כיול מצלמה גיאומטרי
• טריאנגולציה (ראייה ממוחשבת)

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

• הערכת מטריקס חיונית ב- MATLAB (מנוליס לוראקיס).

הפניות

[[קטגוריה:ראייה ממוחשבת]] [[קטגוריה:דפים עם תרגומים שלא נסקרו]]