אינטרפולציה ביליניארית
במתמטיקה, אינטרפולציה ביליניארית היא הרחבה של אינטרפולציה ליניארית עבור פונקציות אינטרפולציה של שני משתנים (למשל, x ו - y) על מרובע מרושת בשני ממדים (2D).
רעיון המפתח הוא לבצע אינטרפולציה ליניארית קודם בכיוון אחד, ואז שוב לכיוון השני. למרות שכל צעד הוא ליניארי בערכו, האינטרפולציה בכללותה אינה ליניארית אלא ריבועית עבור מיקום הדגימה.
אלגוריתם
נניח שאנו רוצים למצוא את הערך של הפונקציה הלא ידועה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} בנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x, y)} . ההנחה היא כי אנחנו יודעים את הערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} בארבע הנקודות:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align}}
ראשית נעשה אינטרפולציה ליניארית בכוון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} . זו מניבה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align}}
נמשיך על ידי אינטרפולציה בכוון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} כדי להשיג את ההערכה הרצויה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align}}
יש לשים לב כי אנו מגיעים לאותה תוצאה אם נעשה אינטרפולציה קודם לאורך כיוון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} ואז לאורך כיוון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} .
אלגוריתם חלופי
דרך חלופית לכתוב את הפתרון לבעיית האינטרפולציה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x,y) \approx a_0 + a_1 x + a_2 y + a_3 xy}
כאשר המקדמים הם פתרון המערכת הליניארית:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}
אם פתרון מועדף מבחינת (f(Q אז אנחנו יכולים לכתוב:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x,y) \approx b_{11} f(Q_{11}) + b_{12} f(Q_{12}) + b_{21} f(Q_{21}) + b_{22} f(Q_{22})}
שבו המקדמים הם פתרון של:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }
רבוע היחידה
אם אנו בוחרים מערכת קואורדינטות בה ארבע נקודות כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} הידועות הן (0, 0), (0, 1), (1, 0), (1, 1), ואז אינטרפולציה הנוסחה מפושטת לכדי:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. }
או באופן שקול, לפעולה המטריציונית:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}.}
לא ליניארי
בניגוד למה שהשם מרמז, אינטרפולציה בילנארית, אינה ליניארית; אלא תוצר של שתי פונקציות ליניאריות.
לחלופין, ניתן לכתוב:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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} x y}
כאשר
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{00} = f(0,0) }
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{10} = f(1,0)-f(0,0)}
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{01} = f(0,1)-f(0,0)}
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{11} = f(1,1)+f(0,0)-(f(1,0)+f(0,1))}
בשני המקרים, מספר הקבועים (ארבעה) תואמים את מספר נקודות הנתונים בהן נתון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} את האינטרפולנט הליניארי לאורך הקווים המקבילים בכוון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} , באופן שקול, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} מוגדר כקבוע. לאורך כל קו ישר אחר, האינטרפולציה היא ריבועית. עם זאת, גם אם אינטרפולציה אינה ליניארי בנקודה (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ו - הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} ), היא ליניארית במשרעת, כפי שיוצא מן המשוואות לעיל: כל מקדם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle bj, j=1..4} , פרופורציונליים לערך של הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(,)} .
התוצאה של אינטרפולציה ביליניארית, אינה תלויה בבחירת הציר הראשון לאינטרפולציה. כלומר אם נבחרלבצע את אינטרפולציה הליניארית קודם בכוון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} ואז ב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , תוצאת הקירוב תהיה זהה.
הרחבה ברורה של אינטרפולציה ביליניארית לשלושה ממדים נקראת אינטרפולציה תרילינארית.
יישומים בעיבוד תמונה
בראייה ממוחשבת ו עיבוד תמונה, אינטרפולציה ביליניארית הוא טכניקה בסיסית של "Resampling".
בתוך מיפוי מרקם, שימוש זה ידוע גם בשם סינון ביליניארי או מיפוי מרקם ביליניארי, ויכול לשמש כדי לייצר תמונה מציאותית סבירה. אלגוריתם משמש למפות מיקום של פיקסל, המקביל לנקודה על מפת המרקם. ממוצע משוקלל של מאפיינים (צבע, אלפא, וכו'.) של ארבעת הרכיבים שמסביב, מחושב, ומיוצר על המסך פיקסל. תהליך זה חוזר על עצמו עבור כל פיקסל ויוצרים את המרקם כולו.[1]
אינטרפולציה ביליניארית מחשיבה את 2x2 הערכים הקרובים של ערכי פיקסל ידועים לפיקסל הלא ידוע. אז נלקח ממוצע משוקלל של 4 הפיקסלים להגיע לערך הסופי של האינטרפולציה. המשקל שעל כל 4 הפיקסלים ערכים מבוסס על מרחק פיקסל מחושב (בשטח 2D) מכל אחת מהנקודות הידועות.[2]
כפי שניתן לראות בדוגמה משמאל, ערך העצמה בפיקסל שחושב להיות בשורה 20.2, וטור 14.5 יכול להיות מחושב על ידי אינטרפולציה ליניארית ראשונה בין הערכים בטור 14 ו-15 על כל שורות 20, 21, הנותנת:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align}}
ואז מבצעים אינטרפולציה באופן ליניארי בין ערכים אלה, הנותנת:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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) לא אינטגרלי, בניגוד לאינטרפולציה "השכן הקרוב", אשר תגרום לקצת פיקסלים להיראות גדולים יותר מאשר אחרים, בתמונה המוגדלת.
ראו גם
הערות שוליים
