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

مثال على الاستيفاء الخطي الثنائي على مربع الوحدة بقيم 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.^[1]

الاحتواء متعدد الحدود

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

كطريقة بديلة هي كتابة الحل لمشكلة الاستيفاء على شكل متعدد الحدود

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 .

خصائص

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

نتيجة الاستيفاء الخطي الثنائي لا تتأثر بأي محور يتم الاستيفاء عليه أولاً وأيهم ثانيًا. إذا قمنا أولاً بتنفيذ استيفاء الخطي في اتجاه y ومن ثم في اتجاه x، فإن التقريب الناتج سيكون متطابقًا.

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

عكس وتعميم

بشكل عام، سيقوم الاستيفاء بأخذ أي قيمة (في انغلاق محدب من قيم النقاط الرئيسية) في عدد لانهائي من النقاط (والتي تشكل فروعاً للقطع الزائدة^[2])، لذا الاستيفاء غير قابل للعكس.

مع ذلك، عندما يتم تطبيق استيفاء خطي ثنائي على دالتين بشكل متزامن، مثل عند استيفاء حقل متجهات، فإن الاستيفاء قابل للعكس (تحت شروط معينة). وبشكل خاص، يمكن استخدام هذا العكس للعثور على "إحداثيات مربع الوحدة" لنقطة داخل أي رباعي أضلاع محدب (عن طريق النظر إلى إحداثيات رباعي أضلاع كحقل متجهات يتم استيفاءه خطيًا ثنائيًا على مربع الوحدة). باستخدام هذا الإجراء، يمكن توسيع الاستيفاء الخطي الثنائي إلى أي رباعي أضلاع محدب، على الرغم من أن الحسابات تكون أكثر تعقيدًا بشكل ملحوظ إذا لم يكن رباعي الأضلاع متوازي الأضلاع.^[3] الخريطة الناتجة بين الرباعيات تُعرف باسم تحويل خطي ثنائي، أو التشويه الثنائي.

بديلًا عن ذلك، يمكن استخدام تجانس الشكل بين رباعي أضلاع وَمربع الوحدة، ولكن الاستيفاء الناتج لن يكون خطيًا ثنائيًا.

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

التمديد الواضح للاستيفاء الخطي الثنائي إلى ثلاثة أبعاد يُعرف بالاستيفاء الثلاثي.

حساب عكسي

ليكن ${\textstyle F}$ حقلًا ناقلًا يتم استيفاؤه ثنائيًا على مربع الوحدة المعلم بواسطة ${\textstyle \mu ,\lambda \in [0,1]}$ . يتطلب عكس الاستيفاء حل نظام من معادلتين كثيرة الحدود: $A+B\lambda +C\mu +D\lambda \mu =0$ حيث ${\begin{aligned}A&=F_{00}-F\\B&=F_{10}-F_{00}\\C&=F_{01}-F_{00}\\D&=F_{11}-F_{01}-F_{10}+F_{00}\end{aligned}}$ تطبيق الضرب التقاطعي (انظر جبر خارجي) على النظام باستخدام نواتج متجهات مختارة بعناية يسمح لنا بالتخلص من الحدود: ${\begin{aligned}(A+B\lambda +C\mu )&\times D&=0\\(A+B\lambda )&\times (C+D\lambda )&=0\\(A+C\mu )&\times (B+D\mu )&=0\\\end{aligned}}$ التي توسع إلى ${\begin{aligned}c+e\lambda +f\mu &=0\\b+(c+d)\lambda +e\lambda ^{2}&=0\\a+(c-d)\mu +f\mu ^{2}&=0\\\end{aligned}}$ حيث ${\begin{aligned}a&=A\times B\\b&=A\times C\qquad d=B\times C\\c&=A\times D\qquad e=B\times D\qquad f=C\times D\end{aligned}}$ يمكن حل المعادلات التربيعية باستخدام الصيغة التربيعية. لدينا المحددات المعادلة $\mathbb {D} =(c+d)^{2}-4eb=(c-d)^{2}-4fa$ والحلول $\lambda ={\frac {-c-d\pm {\sqrt {\mathbb {D} }}}{2e}}\qquad \mu ={\frac {-c+d\mp {\sqrt {\mathbb {D} }}}{2f}}$ (يتم فرض العلامات المعاكسة بواسطة العلاقة الخطية). يجب التعامل مع الحالات عندما $e=0$ أو $f=0$ بشكل منفصل. بناءً على الشروط المناسبة، ينبغي أن يكونَ أحد الحلين داخلَ مربع الوحدة.

استعمالاته في معالجة الصور

في رؤية الحاسوب ومعالجة الصور، يُستخدم الاستيفاء الخطي الثنائي لإعادة تحجيم الصور والإكساء. يتم استخدام خوارزمية لتعيين موقع بكسل الشاشة إلى نقطة مقابلة على خريطة الإكساء. يُحسب المتوسط المرجح للسمات (اللون، الشفافية، إلخ) للتكسلات الأربع المحيطة ويُطبق على بكسل الشاشة. يُكرر هذا العملية لكل بكسل يشكل الكائن المنسوج.^[4]

عندما تحتاج الصورة إلى تكبير الحجم، يجب نقل كل بكسل من الصورة الأصلية في اتجاه معين بناءً على ثابت المقياس. ومع ذلك، عند تكبير الصورة بمعامل مقياس غير صحيح، هناك بكسلات (مثلاً ثقوب) لن يتم تعيين قيم بكسل مناسبة لها. في هذه الحالة، يجب تعيين قيم آر جي بي أو تدرج رمادي مناسبة لتلك الثقوب بحيث لا تحتوي الصورة الناتجة على بكسلات دونَ قيم.

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

الاستيفاء الخطي الثنائي يأخذ بعين الاعتبار أقرب جوار 2 × 2 من قيم البكسل المعروفة المحيطة بالموقع المحسوب للبكسل المجهول. يأخذ بعد ذلك المتوسط المرجح لهذه البكسلات الأربعة للوصول إلى استيفاء قيمته النهائية.^[5]^[6]

Bilinear interpolation — مثال عن استيفاء خطي ثنائي بقيم التدرج الرمادي.

مثال

كما هو موضح في المثال على اليسار، يمكن حساب قيمة الكثافة في البكسل المحسوب ليكون في الصف 20.2، العمود 14.5 عن طريق الاستيفاء الخطي أولاً بين القيم في العمود 14 و 15 على كل من الصفوف 20 و 21، مما يعطي ${\begin{aligned}I_{20,14.5}&={\frac {15-14.5}{15-14}}\cdot 91+{\frac {14.5-14}{15-14}}\cdot 210=150.5,\\I_{21,14.5}&={\frac {15-14.5}{15-14}}\cdot 162+{\frac {14.5-14}{15-14}}\cdot 95=128.5,\end{aligned}}$

ثم استيفاء خطي بين هذه القيم، مما يعطي

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

هذا الخوارزمية تقلل من بعض التشويهات البصرية الناتجة عن تصغير الصورة إلى معامل تكبير غير صحيح، بالمقارنة مع التقنية التي تعتمد على استيفاء الجار الأقرب، والتي قد تجعل بعض البكسلات تبدو أكبر من البعض الآخر في الصورة المُغيَّرة الحجم.

أنظر أيضا

استيفاء
استيفاء خطي
استيفاء الجار الأقرب
استيفاء الدرج
استيفاء ثنائي التكعيب ^{[الإنجليزية]}
استيفاء ثلاثي الخط ^{[الإنجليزية]}
استيفاء شريحة
إعادة تشكيل لانكزوس ^{[الإنجليزية]}
استيفاء ثنائي التكعيب ^{[الإنجليزية]}
استيفاء الدرج
نظام الإحداثيات المرجحية - للاستيفاء داخل مثلث أو رباعي السطوح

المراجع

^ Press، William H.؛ Teukolsky، Saul A.؛ Vetterling، William T.؛ Flannery، Brian P. (1992). Numerical recipes in C: the art of scientific computing (ط. 2nd). New York, NY, USA: Cambridge University Press. ص. 123-128. ISBN:0-521-43108-5.
^ Monasse, Pascal (10 Aug 2019). "Extraction of the Level Lines of a Bilinear Image". Image Processing on Line (بالإنجليزية). 9: 205–219. DOI:10.5201/ipol.2019.269. ISSN:2105-1232. Archived from the original on 2023-01-27.
^ Quilez، Inigo (2010). "Inverse bilinear interpolation". iquilezles.org. مؤرشف من الأصل في 2010-08-13. اطلع عليه بتاريخ 2024-02-17.
^ Bilinear interpolation definition (popular article on www.pcmag.com. نسخة محفوظة 2024-03-30 على موقع واي باك مشين.
^ Khosravi, M. R. (19 Mar 2021). "BL-ALM: A Blind Scalable Edge-Guided Reconstruction Filter for Smart Environmental Monitoring Through Green IoMT-UAV Networks". IEEE Transactions on Green Communications and Networking (بالإنجليزية). 5 (2): 727–736. DOI:10.1109/TGCN.2021.3067555. S2CID:233669511. Archived from the original on 2022-02-24.
^ "Web tutorial: Digital Image Interpolation". نسخة محفوظة 2024-03-31 على موقع واي باك مشين.

[1] Press، William H.؛ Teukolsky، Saul A.؛ Vetterling، William T.؛ Flannery، Brian P. (1992). Numerical recipes in C: the art of scientific computing (ط. 2nd). New York, NY, USA: Cambridge University Press. ص. 123-128. ISBN:0-521-43108-5.

[2] Monasse, Pascal (10 Aug 2019). "Extraction of the Level Lines of a Bilinear Image". Image Processing on Line (بالإنجليزية). 9: 205–219. DOI:10.5201/ipol.2019.269. ISSN:2105-1232. Archived from the original on 2023-01-27.

[3] Quilez، Inigo (2010). "Inverse bilinear interpolation". iquilezles.org. مؤرشف من الأصل في 2010-08-13. اطلع عليه بتاريخ 2024-02-17.

[4] Bilinear interpolation definition (popular article on www.pcmag.com. نسخة محفوظة 2024-03-30 على موقع واي باك مشين.

[5] Khosravi, M. R. (19 Mar 2021). "BL-ALM: A Blind Scalable Edge-Guided Reconstruction Filter for Smart Environmental Monitoring Through Green IoMT-UAV Networks". IEEE Transactions on Green Communications and Networking (بالإنجليزية). 5 (2): 727–736. DOI:10.1109/TGCN.2021.3067555. S2CID:233669511. Archived from the original on 2022-02-24.

[6] "Web tutorial: Digital Image Interpolation". نسخة محفوظة 2024-03-31 على موقع واي باك مشين.

[1]

[2]

[3]

[4]

[5]

[6]