אינטרפולציה ביליניארית

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

דוגמת אינטרפולציה ביליניארית על יחידה מרובעת עם ערכי z של 0, 1, 1, ו-0.5, כמצוין באיור. ערכי האינטרפולציה מיוצגים על ידי הצבע בכל נקודה.

במתמטיקה, אינטרפולציה ביליניארית היא מקרה פרטי של אינטרפולציה ליניארית עבור פונקציות אינטרפולציה של שני משתנים (למשל, x ו - y) על מרובע מרושת בשני ממדים (2D).

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

אלגוריתם

נניח שאנו רוצים למצוא את הערך של הפונקציה הלא ידועה $f$ בנקודה $(x,y)$. ההנחה היא כי אנחנו יודעים את הערך של $f$ בארבע הנקודות:

${\begin{aligned}Q_{11}=(x_{1},y_{1})\\Q_{12}=(x_{1},y_{2})\\Q_{21}=(x_{2},y_{1})\\Q_{22}=(x_{2},y_{2})\end{aligned}}$

ראשית נעשה אינטרפולציה ליניארית בכיוון $x$. זו מניבה:

${\begin{aligned}f(x,y_{1})&\approx {\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21})\\f(x,y_{2})&\approx {\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22})\end{aligned}}$

נמשיך על ידי אינטרפולציה בכיוון $y$ כדי להשיג את ההערכה הרצויה:

${\begin{aligned}f(x,y)&\approx {\frac {y_{2}-y}{y_{2}-y_{1}}}f(x,y_{1})+{\frac {y-y_{1}}{y_{2}-y_{1}}}f(x,y_{2})\\&\approx {\frac {y_{2}-y}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21})\right)+{\frac {y-y_{1}}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}\left(f(Q_{11})(x_{2}-x)(y_{2}-y)+f(Q_{21})(x-x_{1})(y_{2}-y)+f(Q_{12})(x_{2}-x)(y-y_{1})+f(Q_{22})(x-x_{1})(y-y_{1})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}-x&x-x_{1}\end{bmatrix}}{\begin{bmatrix}f(Q_{11})&f(Q_{12})\\f(Q_{21})&f(Q_{22})\end{bmatrix}}{\begin{bmatrix}y_{2}-y\\y-y_{1}\end{bmatrix}}\end{aligned}}$

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

אלגוריתם חלופי

דרך חלופית לכתוב את הפתרון לבעיית האינטרפולציה:

$f(x,y)\approx a_{0}+a_{1}x+a_{2}y+a_{3}xy$

כאשר המקדמים הם פתרון המערכת הליניארית:

${\begin{aligned}{\begin{bmatrix}1&x_{1}&y_{1}&x_{1}y_{1}\\1&x_{1}&y_{2}&x_{1}y_{2}\\1&x_{2}&y_{1}&x_{2}y_{1}\\1&x_{2}&y_{2}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\a_{2}\\a_{3}\end{bmatrix}}={\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}}\end{aligned}}$

אם פתרון מועדף מבחינת (f(Q אז אנחנו יכולים לכתוב:

$f(x,y)\approx b_{11}f(Q_{11})+b_{12}f(Q_{12})+b_{21}f(Q_{21})+b_{22}f(Q_{22})$

שבו המקדמים הם פתרון של:

${\begin{bmatrix}b_{11}\\b_{12}\\b_{21}\\b_{22}\end{bmatrix}}=\left({\begin{bmatrix}1&x_{1}&y_{1}&x_{1}y_{1}\\1&x_{1}&y_{2}&x_{1}y_{2}\\1&x_{2}&y_{1}&x_{2}y_{1}\\1&x_{2}&y_{2}&x_{2}y_{2}\end{bmatrix}}^{-1}\right)^{T}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}}$

רבוע היחידה

אם אנו בוחרים מערכת קואורדינטות בה ארבע נקודות כאשר $f$ הידועות הן (0, 0), (0, 1), (1, 0), (1, 1), ואז אינטרפולציה הנוסחה מפושטת לכדי:

$f(x,y)\approx f(0,0)(1-x)(1-y)+f(1,0)x(1-y)+f(0,1)(1-x)y+f(1,1)xy.$

או באופן שקול, לפעולה המטריציונית:

$f(x,y)\approx {\begin{bmatrix}1-x&x\end{bmatrix}}{\begin{bmatrix}f(0,0)&f(0,1)\\f(1,0)&f(1,1)\end{bmatrix}}{\begin{bmatrix}1-y\\y\end{bmatrix}}.$

לא ליניארי

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

לחלופין, ניתן לכתוב:

$f(x,y)=\sum _{i=0}^{1}\sum _{j=0}^{1}a_{ij}x^{i}y^{j}=a_{00}+a_{10}x+a_{01}y+a_{11}xy$

כאשר

$a_{00}=f(0,0)$

$a_{10}=f(1,0)-f(0,0)$

$a_{01}=f(0,1)-f(0,0)$

$a_{11}=f(1,1)+f(0,0)-(f(1,0)+f(0,1))$

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

בשני המקרים, מספר הקבועים (ארבעה) תואמים את מספר נקודות הנתונים בהן נתון $f$ את האינטרפולנט הליניארי לאורך הקווים המקבילים בכיוון $x$ או $y$, באופן שקול, אם $x$ או $y$ מוגדר כקבוע. לאורך כל קו ישר אחר, האינטרפולציה היא ריבועית. עם זאת, גם אם אינטרפולציה אינה ליניארי בנקודה ($x$ ו - $y$), היא ליניארית במשרעת, כפי שיוצא מן המשוואות לעיל: כל מקדם $bj,j=1..4$, פרופורציונליים לערך של הפונקציה $f(,)$.

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

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

יישומים בעיבוד תמונה

בראייה ממוחשבת ו עיבוד תמונה, אינטרפולציה ביליניארית הוא טכניקה בסיסית של "Resampling".

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

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

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

כפי שניתן לראות בדוגמה משמאל, ערך העצמה בפיקסל שחושב להיות בשורה 20.2, וטור 14.5 יכול להיות מחושב על ידי אינטרפולציה ליניארית ראשונה בין הערכים בטור 14 ו-15 על כל שורות 20, 21, הנותנת:

${\begin{aligned}I_{20,14.5}&={\tfrac {15-14.5}{15-14}}\cdot 91+{\tfrac {14.5-14}{15-14}}\cdot 210=150.5\\I_{21,14.5}&={\tfrac {15-14.5}{15-14}}\cdot 162+{\tfrac {14.5-14}{15-14}}\cdot 95=128.5\end{aligned}}$

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

$I_{20.2,14.5}={\tfrac {21-20.2}{21-20}}\cdot 150.5+{\tfrac {20.2-20}{21-20}}\cdot 128.5=146.1$

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

ראו גם

• קואורדינטות בריצנטריות

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

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