تخزن الصورة التكاملية مجاميع مناطق تبدأ من زاوية الصورة. يتيح جمع وطرح أربع قيم منها استخراج مجموع مستطيل محاذٍ للمحاور. [1]
سنؤلف شبكة من عشرين عددًا ونبني جدولها خطوة بخطوة. ثم نستخرج تسع خانات داخلية، ونتحقق من كل مستطيل ممكن في الشبكة. المثال عددي؛ لا نحتاج صورة فوتوغرافية أو مكتبة رؤية حاسوبية حتى نرى أين تذهب كل قيمة.
الخلاصة السريعة
- شبكتنا أربعة صفوف وخمسة أعمدة، ومجموعها الكامل 49.
- نضيف صفًا وعمودًا صفريين؛ يصبح جدول المجاميع بخمسة صفوف وستة أعمدة، مع بقاء القيم الأصلية عشرين.
- للمستطيل rows[1:4],cols[1:4] نحسب 40−8−9+3=26، وهو مجموع تسع خانات.
- فحصنا 315 نافذة تشمل الفارغة، ثم 2916 نافذة على شبكات صغيرة موقعة؛ وافقت النتائج الجمع المباشر.
- تعديل قيمة في الشبكة لا يحدث الجدول القديم تلقائيًا؛ تجربة الزيادة بعشرة تترك الجواب القديم خاطئًا حتى إعادة البناء.
ثبّت الفهرسة قبل الجمع
هذه شبكة المثال. الصف صفر في الأعلى، والعمود صفر في اليسار كما في المصفوفات المعروضة. الأرقام ليست درجات سطوع مأخوذة من ملف، بل قيم تعليمية اخترناها لنراجع الحساب يدويًا.
| الصف / العمود | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 3 | 1 | 4 | 0 | 2 |
| 1 | 2 | 5 | 1 | 3 | 4 |
| 2 | 0 | 2 | 6 | 1 | 3 |
| 3 | 4 | 1 | 2 | 5 | 0 |
نكتب حدود النافذة على صورة r0,c0,r1,c1. البداية مشمولة، والنهاية مستبعدة. لذلك [1:4] تختار الفهارس 1،2،3، ولا تضيف فهرس أربعة. عدد الخانات في السؤال الرئيسي (4−1)×(4−1)=9.
في اصطلاح الجدول ذي الحافة الصفرية، تمثل P[r,c] مجموع الصفوف الأصغر من r والأعمدة الأصغر من c. يزيد كل بُعد خانةً عن المدخل. [1]
إذن P[1,1]=3، وP[1,3]=3+1+4=8. أما P[2,3] فتشمل صفين وثلاثة أعمدة: 3+1+4+2+5+1=16. الصفر عند P[0,c] يعني أننا لم نأخذ أي صف، لا أن الصف الأول في البيانات كله أصفار.
ابنِ جدولًا يمكن مراجعته صفًا صفًا
في تنفيذنا نجمع قيم الصف الجاري من اليسار إلى اليمين. نضيف إلى ذلك المجموع قيمة الجدول الموجودة فوق موضع الكتابة. عند قراءة الخانة الأصلية A[1,2]=1 يصبح مجموع صفها الجزئي 2+5+1=8. فوق موضع الناتج نجد P[1,3]=8، فنكتب P[2,3]=16.
نفعل ذلك للعشرين خانة. في الصف الأخير تبدأ المجاميع المحلية بـ4،5،7،12،12. بإضافة القيم التي فوقها 5،13،24،28،37 نحصل على 9،18،31،40،49. يوضح الصف الأخير أن المجموع التراكمي المحلي وحده ليس جدول مناطق ثنائي الأبعاد.
| r / c | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 3 | 4 | 8 | 8 | 10 |
| 2 | 0 | 5 | 11 | 16 | 19 | 25 |
| 3 | 0 | 5 | 13 | 24 | 28 | 37 |
| 4 | 0 | 9 | 18 | 31 | 40 | 49 |
لماذا نطرح مرتين ثم نضيف؟
صيغة المستطيل في هذا الاصطلاح هي P[r1,c1]−P[r0,c1]−P[r1,c0]+P[r0,c0]. [1]
نريد الصفوف من واحد إلى ثلاثة والأعمدة من واحد إلى ثلاثة. خذ أولًا P[4,4]=40، وهي كل الكتلة اليسرى العليا حتى تلك الحدود. أزل الصف الأعلى حتى العمود الثالث، ومجموعه P[1,4]=8. وأزل العمود الأيسر حتى الصف الثالث، ومجموعه P[4,1]=9.
الخانة العلوية اليسرى وقيمتها ثلاثة كانت ضمن الجزأين المحذوفين، فطرحت مرتين. نضيف P[1,1]=3 مرة واحدة لنحذفها مرة واحدة فقط من الكتلة الأصلية. الناتج 40−8−9+3=26. من دون الإضافة الأخيرة يظهر 23، ونستطيع تحديد مصدر الفرق بدل نسبته إلى خطأ تقريبي.
للتحقق المباشر، صفوف المستطيل المختار هي [5,1,3] و[2,6,1] و[1,2,5]. مجاميعها 9،9،8، ومجموعها 26. متوسط هذه الخانات في نموذجنا هو 26/9، نحو 2.889؛ لا نقسمه على عشرين، لأنها ليست مساحة النافذة.
جرّب الأطراف والنافذة الفارغة
للشبكة كلها نستعمل (0,0,4,5). قيم الطرح والإضافة على الحافتين صفر، فيبقى 49. وللخانة الأخيرة وحدها (3,4,4,5) تعطينا الصيغة 49−37−40+28=0، موافقةً لبياناتها. الصفر هنا نتيجة نافذة ذات مساحة واحد، وليس دليلًا على أنها فارغة.
أما الحدود (2,1,2,4) فتعطي نافذة بلا صفوف، وتلغي حدود الصيغة بعضها إلى صفر. اخترنا قبول هذه النوافذ الفارغة في دالتنا، ورفض الحد السالب أو النهاية خارج الشبكة أو ترتيب نهاية يسبق البداية. لا نصحح هذه الحالات بصمت، لأن تغيير الحدود سيغير السؤال.
توثق scikit-image اصطلاحًا آخر: الناتج بحجم المدخل، ويشمل موضعه في الجمع التراكمي. لا تخلط فهارسه بفهارس الجدول ذي الحافة الصفرية. [2]
حسبنا ذلك التمثيل الشامل مستقلًا للمثال، فوافقت كل خانة S[r,c] الخانة P[r+1,c+1] من جدولنا. هذه عشرون مقارنة منفذة. عند نقل صيغة بين برنامجين، اكتب أولًا هل النهاية مشمولة وهل أضيفت حافة، ثم اختبر نافذة من خانة واحدة ونافذة تبدأ عند الصفر.
ماذا يحدث إذا تغيرت البيانات؟
غيرنا الخانة A[2,2] من ستة إلى ستة عشر. تغيرت ست خانات في جدولنا عند إعادة بنائه: الصفان 3،4 والأعمدة 3،4،5. كل منطقة تراكمية تشمل الموضع المعدل زاد مجموعها بعشرة؛ المناطق الأخرى لم تتغير.
المستطيل الرئيسي يشمل تلك الخانة، فأصبح مجموعه 36. استعمال الجدول القديم أعاد 26 كما كان. هذه تجربة لكلفة الفصل بين البيانات الأصلية والملخص المحسوب: احفظ ارتباطهما، وأعد البناء عند التعديل إذا كان هذا هو المسار الذي يدعمه تطبيقك.
ما نطاق الاختبارات المنفذة؟
للأربعة صفوف عشرة أزواج حدود غير فارغة، وللخمسة أعمدة خمسة عشر زوجًا؛ أي 150 مستطيلًا غير فارغ. بإضافة النوافذ ذات البعد الصفري يرتفع العدد إلى 315. قارنا كل نتيجة مع حلقة تجمع عناصر النافذة مباشرة، ولم نستعمل جدول المجاميع لبناء المرجع.
أنشأنا أيضًا جميع شبكات 2×2 ذات القيم من المجموعة −1،0،2، وعددها 3⁴=81. لكل واحدة ستة وثلاثون اختيارًا للحدود مع النوافذ الفارغة، فبلغت المقارنات 2916. نجحت كلها، مع اختبارات التعديل والتحويل بين الاصطلاحين ورفض سبعة مدخلات غير صالحة.
كل الحسابات بأعداد بايثون الصحيحة؛ لم نشغّل OpenCV أو scikit-image ولم نقس زمنًا. أربع قراءات من جدول جاهز لا تعني أن بناءه أو تخزينه مجاني. يشرح مثال التراكم والبداية مشكلة المسار في بعد واحد؛ هنا أضفنا البعد الثاني وحدود المناطق، وهي المعلومات التي تجعل سؤال المستطيل محددًا.
المصادر
الأمثلة العددية والرسوم والاختبارات أصلية لهذا المقال ومنفذة برمجيًا. أُعدت الصياغة والمراجعة الأولية بمساعدة الذكاء الاصطناعي، دون ادعاء مراجعة بشرية مستقلة.