استيفاء خطي ثنائي

مثال على الاستيفاء الخطي الثنائي على مربع الوحدة بقيم z 0 و1 و1 و0.5 كما هو محدد. القيم المحرفة بينهما ممثلة باللون.

في علوم الرياضيات، اِسْتِيفَاءْ خطي ثنائي (بالانجليزية: Bilinear Interpolation)، هي طريقة لعمل استيفاء دالتين ذات متغيرين اثنين ( مثال.، س وَع) باستعمال استيفاء خطي متكرر.تُطبّقُ هذه الطريقة عادة على الدوال التي تم أخذ عينات منها على شبكة مستطيلة الشكل ثنائية الأبعاد، على الرغم من أنه يمكن تعميمها للدوال المُعرّفَة على رؤوس رُباعية الأضلاع محدبة الشكل.

الاستيفاء الخطي الثنائي يتم بتطبيق الاستيفاء الخطي أولاً في اتجاه واحد، ثم مرة أخرى في اتجاه آخر. على الرغم من أن كل خطوة تكون خطية في القيم المُعالَجة وفي الموضع، إلا أن الاستيفاء ككل ليس خطيًا بل يكون تربيعيًا في موقع العينة.

الاستيفاء الخطي الثنائي هو واحد من تقنيات إعادة التشكيل الأساسية في رؤية الكمبيوتر ومعالجة الصور، حيث يُعرف أيضًا بمصطلح تصفية ثنائية أو تخطيط ثنائي الأنسجة.

حساب

تُظهر النقاط الحمراء الأربع نقاط البيانات والنقطة الخضراء هي النقطة التي نريد الاستيفاء عندها.

لنفترض أننا نريد إيجاد قيمة الدالة المجهولة f في النقطة (x، y). يُفترض أننا نعرف قيمة f في النقاط الأربعة Q11 = (x1، y1)، Q12 = (x1، y2)، Q21 = (x2، y1)، و Q22 = (x2، y2).

الاستيفاء الخطي المكرر

أولًا نقومُ بإجراء الاستيفاء الخطي في اتّجاه x . ينتج عن هذا

${\begin{aligned}f(x,y_{1})={\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})={\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)&={\frac {y_{2}-y}{y_{2}-y_{1}}}f(x,y_{1})+{\frac {y-y_{1}}{y_{2}-y_{1}}}f(x,y_{2})\\&={\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_{00}+a_{10}x+a_{01}y+a_{11}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_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}},\end{aligned}}$

ينتج لنا

${\begin{aligned}{\begin{bmatrix}a_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-x_{2}y_{1}&-x_{1}y_{2}&x_{1}y_{1}\\-y_{2}&y_{1}&y_{2}&-y_{1}\\-x_{2}&x_{2}&x_{1}&-x_{1}\\1&-1&-1&1\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 w_{11}f(Q_{11})+w_{12}f(Q_{12})+w_{21}f(Q_{21})+w_{22}f(Q_{22}),$

حيث تجمع الأوزان إلى 1 وتفي بالنظام الخطي المنقول

${\begin{bmatrix}1&1&1&1\\x_{1}&x_{1}&x_{2}&x_{2}\\y_{1}&y_{2}&y_{1}&y_{2}\\x_{1}y_{1}&x_{1}y_{2}&x_{2}y_{1}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}w_{11}\\w_{12}\\w_{21}\\w_{22}\end{bmatrix}}={\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},$

ينتج لنا

${\begin{aligned}{\begin{bmatrix}w_{11}\\w_{21}\\w_{12}\\w_{22}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-y_{2}&-x_{2}&1\\-x_{2}y_{1}&y_{1}&x_{2}&-1\\-x_{1}y_{2}&y_{2}&x_{1}&-1\\x_{1}y_{1}&-y_{1}&-x_{1}&1\end{bmatrix}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},\end{aligned}}$

والتي تبسط إلى

${\begin{aligned}w_{11}&=(x_{2}-x)(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{12}&=(x_{2}-x)(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{21}&=(x-x_{1})(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{22}&=(x-x_{1})(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\end{aligned}}$

بالاتفاق مع النتيجة التي تم الحصول عليها عن طريق الاستيفاء الخطي المتكرر. يمكن أيضًا تفسير مجموعة الأوزان على أنها مجموعة من إحداثيات مركز الكتلة المعممة للمستطيل.

وهذا يتفق مع النتيجة التي تم الحصول عليها عن طريق الاستيفاء الخطي المكرر. يمكن أيضًا تفسير مجموع الأوزان كمجموعة من نظام الإحداثيات المرجحية المعممة لمستطيل.

صيغة بديلة للمصفوفة

بدمج ما ذُكر أعلاه، لدينا:

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

على مربع الوِحدة

إذا اخترنا نظام إحداثيات يكون فيه النقاط الأربعة التي تعرف قيمة f عندها هي (0، 0)، (0، 1)، (1، 0)، و (1، 1)، فإن صيغة الاستيفاء تبسط إلى:

$f(x,y)\approx f(0,0)(1-x)(1-y)+f(0,1)(1-x)y+f(1,0)x(1-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}}.$

هنا نتعرف أيضًا على الأوزان:

${\begin{aligned}w_{11}&=(1-x)(1-y),\\w_{12}&=(1-x)y,\\w_{21}&=x(1-y),\\w_{22}&=xy.\end{aligned}}$

غيرَ ذلك، يمكننا كتابة الاستيفاء على مربع الوِحدة على الشكل التالي

$f(x,y)=a_{00}+a_{10}x+a_{01}y+a_{11}xy,$

حيث

${\begin{aligned}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(1,0)-f(0,1)+f(0,0).\end{aligned}}$

في كلا الحالتين، يتوافق عدد الثوابت (أربعة) مع عدد نقاط البيانات حيث تعطى f .

خصائص

قالب:Comparison of 1D and 2D interpolation.svgقالب:Comparison of 1D and 2D interpolation.svgكما يوحي اسمه، فإن الاستيفاء الخطي الثنائي ليس خطيًا؛ ولكنه خطي (أي تآلفي) على طول الخطوط المتوازية إما بالاتجاه x أو y، بالتبادل إذا تم الاحتفاظ بثابت x أو y. على طول أي خط مستقيم آخر، يكون الاستيفاء تربيعي. على الرغم من أن الاستيفاء ليس خطيًا في الموضع (x وَ y)، إلا أنه في النقطة الثابتة فإنه خطي في قيم الاستيفاء، كما يمكن رؤيته في معادلات (المصفوفة) أعلاه.