تستخرج خوارزمية المربعات المتحركة مسارات تساوي القيمة من شبكة ثنائية الأبعاد. تستعمل دالة find_contours في scikit-image هذه الفكرة مع استيفاء خطي. [1]
لن نسأل البرنامج أن يرسم حدًا ثم نقبل شكله. سنحسب نقاطه أولًا، ونرى متى يكون وصلها واضحًا ومتى يحتاج قرارًا معلنًا. سنستخدم قيمًا مؤلفة وكسورًا دقيقة، ونبيّن كيف يتحول مسار مغلق إلى مسار مفتوح بمجرد قص مجال البيانات.
الخلاصة السريعة
- ننظر إلى أربع عينات عند أركان كل خلية، ونبحث عن الأضلاع التي تعبر المستوى المطلوب.
- في مثالنا، الانتقال من القيمة 2 إلى 6 يقطع المستوى 4 عند منتصف الضلع؛ الانتقال من 1 إلى 8 يقطعه عند 3/7 من جهة القيمة 1.
- إذا كانت القيم المرتفعة في زاويتين متقابلتين، فمواضع التقاطع وحدها لا تختار طريقة الوصل.
- شبكتنا الكاملة تعطي 12 قطعة في مسار مغلق؛ نصفها الأيمن يعطي 6 قطع ومسارًا مفتوحًا له طرفان.
- نفذنا 32 حالة لسياسات الخلية و142 تحققًا إجمالًا، باستخدام نموذج مستقل لا تشغيلًا لمكتبة scikit-image.
العينات عند الأركان، وليست ألوان مربعات جاهزة
عرّفنا إحداثي x نحو اليمين وy نحو الأسفل ليتفق الرسم مع ترتيب الصفوف. كل قيمة تقع في نقطة من الشبكة. أربع نقاط متجاورة تحدد خلية حساب واحدة؛ لذلك شبكة 5 × 5 نقاط تحوي 4 × 4 = 16 خلية. لا تخلط عدد العينات بعدد الخلايا التي تمر عليها الخوارزمية.
نختار خلية مربعة طول ضلعها وحدة واحدة، ونكتب الأركان باتجاه دوران عقارب الساعة: أعلى اليسار، أعلى اليمين، أسفل اليمين، أسفل اليسار. سنحافظ على هذا الترتيب في قائمة القيم وفي ترقيم الأضلاع، حتى لا ينتقل تقاطع صحيح عدديًا إلى ضلع خاطئ في الرسم.
| الركن | الإحداثيات | القيمة | مقارنة بالمستوى |
|---|---|---|---|
| أعلى اليسار | (0,0) | 2 | أقل |
| أعلى اليمين | (1,0) | 6 | أعلى |
| أسفل اليمين | (1,1) | 8 | أعلى |
| أسفل اليسار | (0,1) | 1 | أقل |
احسب موضع التقاطع على الضلع
يشرح توثيق ContourPy تصنيف العينات بالنسبة إلى المستوى ثم استيفاء موضع العبور على الأضلاع ذات الطرفين المختلفين في التصنيف. [2]
نفترض على الضلع تغيرًا خطيًا من a إلى b. بعد قطع نسبة t من المسافة تكون القيمة a + t(b−a). نساويها بالمستوى L، فنحصل على t = (L−a)/(b−a). هذه النسبة تخص الضلع واتجاه بدايته، وليست إحداثيًا عالميًا جاهزًا لكل موضع.
على الضلع العلوي لمثالنا: t = (4−2)/(6−2) = 1/2، فيكون التقاطع (1/2,0). وعلى الضلع السفلي، إذا بدأنا من اليسار ذي القيمة 1، فالنسبة (4−1)/(8−1) = 3/7، والتقاطع (3/7,1). أما إذا مررنا الضلع من اليمين إلى اليسار فالنسبة 4/7، لكنها تعطي النقطة نفسها بعد تحويل اتجاه الإحداثي.
الضلع الأيمن طرفاه أعلى من 4، والأيسر طرفاه أقل منها؛ فلا نضع عليهما نقطة عبور في هذا النموذج. نصل النقطتين المحسوبتين بقطعة مستقيمة داخل الخلية. هذه القطعة تقريب اخترناه بين نقطتي الحافة؛ الاستيفاء على الأضلاع لا يكشف وحده شكل حقل مستمر مجهول داخل المربع.
from fractions import Fraction
def crossing_fraction(a, b, level):
if not min(a, b) < level < max(a, b):
raise ValueError("strict crossing required")
return Fraction(level - a, b - a)
print(crossing_fraction(2, 6, 4)) # 1/2
print(crossing_fraction(1, 8, 4)) # 3/7
print(crossing_fraction(8, 1, 4)) # 4/7من قطع محلية إلى مسار واحد
طبقنا الحساب على الشبكة المعروضة في الصورة: صفها الأوسط [0,4,8,4,0]، والصفان المحيطان به [0,2,4,2,0]، والصفان الخارجيان أصفار. عند المستوى 3 أنتج النموذج اثنتي عشرة قطعة. عند جمع نقاط النهايات المتطابقة تكوّن مسار متصل، ولكل نقطة فيه جاران؛ لا توجد نهاية حرة.
الحفاظ على هوية الضلع المشترك يمنع شقوقًا صغيرة بين الخلايا. نقطة تقاطع الحافة اليمنى لخلية هي نفسها نقطة الحافة اليسرى لجارتها. استعملنا الكسور الدقيقة في حساب المثال، فتطابقت الإحداثيات مباشرة. في تنفيذ عشري كبير يمكن تثبيت هوية كل حافة وإعادة استعمال نقطتها بدل حساب نسختين ثم محاولة جمعهما بسماحية عشوائية.
بعد ذلك احتفظنا بالأعمدة ذات الأرقام 2،3،4 فقط. بقيت ست قطع، وصار للمسار طرفان عند حد المجال الجديد. لا يدل فتح المسار هنا على ضياع قطعة من الخوارزمية؛ لقد حُذفت الجهة التي كانت تكمله. هذا اختبار عملي يفصل صحة الحساب عن شرط إغلاق الشكل.
الخلية القطرية تحتاج سياسة وصل
يوضح توثيق scikit-image أن وجود قيم مرتفعة في ركنين متقابلين ومنخفضة في الركنين الآخرين يتيح خيارين للاتصال؛ يحدد المعامل fully_connected أي المجموعتين تُوصل قطريًا. [1]
اخترنا القيم [5,1,5,1] في ترتيب الأركان الذي أعلنّاه، والمستوى 3. كل ضلع يملك نقطة عبور عند منتصفه. إذا أردنا اتصال المنطقة المنخفضة، نصل أعلى المربع بيساره، ويمينه بأسفله؛ تنعزل كل زاوية مرتفعة خلف قطعة. وإذا أردنا اتصال المرتفعة، نصل الأعلى باليمين والأسفل باليسار. النقط الأربع لم تتحرك، لكن هوية الجيران تغيرت.
لهذا يمكن لبرنامجين أن يتفقا في مواضع التقاطعات ثم يختلفا في عدد الأجزاء المتصلة. لا تحاول إصلاح الاختلاف بتقريب الإحداثيات أكثر؛ راجع قاعدة الوصل. نموذجنا يقارن سياستين ثابتتين، ولا ينفذ قرارًا يعتمد على قيمة مركز الخلية أو يعيد بناء تضاريس حقيقية بين العينات.
المساواة بالمستوى والترتيب الإحداثي
يصنف ContourPy القيمة المساوية للمستوى ضمن الجانب غير الأعلى وفق قاعدة z > level. [2]
اخترنا في برنامجنا التعليمي رفض وجود ركن يساوي المستوى تمامًا. هذا تضييق معلن لنطاقه، وليس قاعدة تلزم كل مكتبة. يمنعنا من إدخال حالات نقاط مكررة أو قطع صفرية الطول دون شرح سياستها. لا تغيّر المستوى قليلًا في بيانات حقيقية بصمت؛ سجّل السياسة وسببها قبل تفسير تغير الاتصال.
تعيد find_contours الإحداثيات بترتيب (row, column). [1]
أما نقاط مثالنا فهي (x,y) = (column,row). قلب الترتيب دون قصد قد يعطي صورة متناظرة تبدو مقبولة لبعض الحقول، لذلك اختر اختبارًا غير متناظر مثل خلية القيم 2،6،8،1. كذلك تختلف وحدة القيم عن وحدة المسافات: إذا كانت المسافة الأفقية بين العينات مترين والرأسية ثلاثة، نضرب الإحداثيين بعامليهما عند عرض النتيجة، ولا نضرب قيم الحقل بالطريقة نفسها.
ما الذي تحققت منه الحسابات؟
اختبرنا جميع ترتيبات الأركان العالية والمنخفضة الستة عشر عند سياستي الاتصال، فحصلنا على 32 حالة. في كل حالة راجعنا عدد القطع، واستعمال نقاط التقاطع دون تكرار، ووقوعها على حدود المربع، وكونها في المنتصف عند استعمال قيمتي 1 و5 مع المستوى 3. هذه 128 مراجعة.
أضيفت مقارنة خلية الكسور، وثمانية فحوص لاستيفاء أربعة أضلاع، وفحصا المسار الكامل والمجال المقصوص، وفحصان لتبديل أسماء المرتفع والمنخفض مع السياسة، وفحص رفض المساواة. المجموع 142 تحققًا ناجحًا. لا تعني هذه النتيجة تشغيل scikit-image أو ContourPy؛ نفذنا النموذج المرفق وحده ولم نختبر بيانات ناقصة أو ضوضاء قياس أو أداء مكتبة.
قبل استعمال النتيجة في رسمك، احفظ الشبكة والمستوى وسياسة الاتصال وترتيب الإحداثيات. بهذه المعلومات يستطيع شخص آخر إعادة المثال ومناقشة قراره الهندسي. وللسؤال العددي المختلف عن موضع العتبة وقيمة المساواة، راجع قيمة الصفر والعتبة في دالة الخطوة.
المصادر
البيانات والرسوم والحسابات أُعدت لهذا المقال. أُعد النص بمساعدة الذكاء الاصطناعي، ولا يُنسب إلى خبير بشري مستقل.