👩🏼‍💼 🌛 🥢 حساب مركز الكتلة لـ O (1) باستخدام صور متكاملة 🚦 🎚️ ™️

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

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

في هذه المقالة سأقول:

ما نوع هذه المهمة في السؤال ؛
اقرأ المزيد عن الصور المدمجة ؛
N (-);
;
, , .

N

يشير الحل الصارم للتفاعل الثقالي لنظام الأجسام N إلى الخوارزميات ذات التعقيد التربيعي: كل الأجسام الأخرى في النظام لها تأثير جاذبية على كل جسم ^[1] . وبالتالي، فإن قوة الحاجة تفاعل الجاذبية لحساب لكل من N ² الزوج / 2.

لتوضيح مدى استغراق الوقت لحل صارم ، يمكنك محاولة ربط تعقيد حساب نظام حقيقي بأداء أجهزة الكمبيوتر الحديثة.

لحساب قوة الجاذبية بين جسمين في مساحة ثلاثية الأبعاد ، يجب إجراء 20 عملية بنقطة عائمة (FLOP). في النظام الشمسي ، هناك حوالي 100 جثة أكبر من 200 كيلومتر (بما في ذلك الشمس و 9 كواكب وكواكب قزمة وأقمار صناعية) ^[2]. يبلغ العدد التقريبي للكويكبات في مدار قريب من الأرض حوالي 20 ألف ^[3] . في حزام الكويكبات ، هناك ما بين 1.1 إلى 1.9 مليون جثة أكبر من كيلومتر واحد ^[4] وحوالي مليون كويكب مماثل في مجموعات "طروادة" ^[5] والمجموعات "اليونانية" للمشتري. في حزام كويبر ، يوجد حوالي 100 مليون جسم أكبر من 20 كم ^[6] وحوالي 2 تريليون أخرى في سحابة أورت ^[7] .

إن القوة الحسابية المطلوبة لحل مشكلة الجاذبية الأخيرة بدقة ليست سوى ترتيب بحجم أقل من القوة الحسابية المطلوبة لمحاكاة عمل الدماغ البشري على المستوى العصبي (2.5 × 10 ²⁶ ) ^[8]. هذا هو السبب في أن حلها الصارم عادة ما يتم استبداله بحل تقريبي.

واحدة من الخوارزميات الأكثر استخدامًا للحل التقريبي لمشكلة الجاذبية - كود الشجرة - لها تعقيد زمني شبه خطي O (N * logN) ^[9] . يبني كود الشجرة شجرة مكانية ولكل عقدة في هذه الشجرة يحسب الكتلة الكلية ومركز الكتلة لجميع الأجسام التي تقع فيها. علاوة على ذلك ، عند حساب قوى الجاذبية التي تعمل على كل جسم ، يمكن أن يأخذ كود الشجرة في الاعتبار ليس التأثير المباشر للأجسام الأخرى ، ولكن تأثير عقد الشجرة ، واعتمادًا على المسافة ، فإنه يختار عقدًا أكبر من أي وقت مضى تحتوي على معلمات لمجموعة فرعية متزايدة من الأجسام.

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

مشكلة الجاذبية في مجال الزخم

مجال الزخم هو حقل متجه منفصل mv (p) ، يربط زوج سرعة الكتلة مع كل نقطة من الفضاء p قيد النظر . يمكن تعيين مجال النبض لمساحة من أي بعد. يميز زوج السرعة والكتلة الزخم ويمثل متجهًا للبعد R + 1 ، حيث R هو بُعد المساحة التي يُعطى لها مجال النبض. على سبيل المثال ، بالنسبة لـ R = 2 يمكن أن يكون هذا هو المتجه { v _x ، v _y ، m }.

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

جزء صغير من مجال النواقل للبقول: يُشار إلى الكتل باللون واتجاهات الأسهم ،

ومجال النواقل بقياس 729 × 729 عنصر. على اليسار الجماهير. على اليمين نبضات. النبضات في هذا الرسم التوضيحي مشفرة بالألوان بتنسيق HSV (Hue هو اتجاه النبضة ، وتعرض القيمة خطياً قيمتها المطلقة بحيث تكون النبضات الأقل تميزاً (القيمة = 0.05) من 10 إلى ⁷ ، والأكثر نبضة ألمعًا (القيمة = 1 ، 0) من رتبة 10 ³ وما فوق).

على غرار هذا - الشبكة - يتم استخدام طرق وصف الأنظمة الفيزيائية على نطاق واسع في الفيزياء الفلكية لمحاكاة تطور السحب الغازية وتشكيل النجوم والمجرات. وتشمل هذه طريقة SAMR ^[10] أو نموذج الشبكة للديناميكا المائية ^[11] .

كما هو الحال بالنسبة لمشكلة الجاذبية للأجسام N ، يجب أن يأخذ تطور المجال المنفصل في الاعتبار تأثير الجاذبية لجميع الكتل التي تشكل هذا المجال على كل عنصر من عناصره المنفصلة. من الضروري أن تأخذ في الاعتبار أن تعقيد المشكلة يعتمد بشكل غير مباشر على أبعاد الفضاء R : على سبيل المثال ، بالنسبة لحقل على مستوى يتكون من 1000 × 1000 عنصر ، سيكون العدد الإجمالي N 10 ⁶العناصر ، وحقل من نفس الحجم في الفضاء ثلاثي الأبعاد سيتضمن بالفعل 10 ⁹ عناصر.

ومع ذلك ، هناك عدد من الحيل التي تجعل من الممكن حل مشكلة الجاذبية لمجال الزخم تقريبًا. يستخدم أسلوب Multigrid تقديرًا هرميًا ، يدعم العديد من الشبكات ذات الأحجام المختلفة ^[12] . يعامل توسع متعدد الأقطاب مجموعات المصادر القريبة من بعضها البعض ككائن واحد ^[13] . Multigrid له تعقيد حسابي شبه خطي وتعقيد الذاكرة اللوغاريتمية. يوضح أحد خيارات التوسع متعدد الأقطاب - FMM - التعقيد الحسابي الخطي في مقابل انخفاض الدقة الحسابية ^[14] .

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

صورة متكاملة

تسمح الصورة المتكاملة بحساب الوقت الثابت لمجموع عناصر الصورة الأصلية في منطقة مستطيلة عشوائية ^[15] . في الرسومات الحاسوبية ، تم اقتراح الصور المدمجة في الأصل كبديل عن الخرائط miping والتصفية متباينة الخواص ^[16] . بالإضافة إلى ذلك ، يتم استخدامها بنجاح لمعالجة الصور الرقمية وتقنيات التعرف على الأنماط.

الصورة المتكاملة هي واحدة من أوضح الأمثلة على المفاضلة بين التعقيد الحسابي وتعقيد الذاكرة. إن الخوارزمية "الساذجة" لحساب مجموع عناصر الصورة لها تعقيد زمني لـ O (M * N) وتعقيد ذاكرة O (1). تتيح لك الصورة المدمجة إجراء نفس الحسابات في وقت O (1) ولديها تعقيد ذاكرة O (M * N).

استخدام الصورة المدمجة لحساب مجموع العناصر في منطقة معينة

خوارزمية حساب الصورة المتكاملة بسيطة للغاية وتتميز بالتعقيد الحسابي الخطي ويمكن موازنتها بسهولة تحت GPGPU ^[17] . يتم تنفيذه كمرشح غاوسي بمرورين ^[18] : في الممر الأول ، تعتبر المبالغ الجزئية للصفوف ، في الثانية ، يتم تجميع هذه المبالغ الجزئية في أعمدة.

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

على اليسار صورة تحتوي على كتل من العناصر. على اليمين هي صورتها المتكاملة. تستخدم الصور على اليسار واليمين مقاييس لوغاريتمية مختلفة.

حل تقريبي لمشكلة الجاذبية باستخدام صورة متكاملة

نظرًا لامتلاكها صورة متكاملة للجماهير ، ليس من الصعب تكييف الخاصية التقنية لرمز الشجرة والتوسع متعدد الأقطاب معها. لذا ، بالنسبة لكل عنصر في الحقل المنفصل:

نحن نأخذ بعين الاعتبار تأثير جماهير العناصر الثمانية المجاورة فقط ؛
نأخذ في الاعتبار تأثير ثماني مناطق مجاورة ، تتكون من تسعة عناصر (3 × 3) ، عن طريق حساب مجموع كتلتها باستخدام صورة متكاملة ؛
في كل خطوة تالية ، نقوم بزيادة حجم المنطقة بمقدار 3 مرات (9 × 9 ، 27 × 27 ، 81 × 81 ، وما إلى ذلك) حتى تتجاوز هذه الخطوة حجم حقل المتجه بأكمله.

حساب تقريبي للقوى التي تعمل على عنصر في المجال المتجه للبقول باستخدام صورة متكاملة للكتل

إن تعقيد الحل التقريبي لمشكلة الجاذبية لمجال من النبضات باستخدام صورة متكاملة ينمو بشكل شبه خطي ، مثل O (N * 8 * log3 (sqrt (N)) لـ R = 2 ومثل O (N * 26 * log3 (cbrt (N))) لـ R = 3.

ومع ذلك ، في هذا النموذج ، فإن هذا الحل له نفس العيب الموجود في تقنية Multigrid ، أي "الصلابة" المنفصلة الملموسة لمكونات التردد المنخفض لوظيفة الجاذبية. من الواضح أن أسهل طريقة لإثبات هذه المشكلة.

القوى في هذا الرسم التوضيحي تم تشفيرها بالألوان بتنسيق HSV (Hue هو اتجاه القوة ، وتعرض القيمة خطياً قيمتها المطلقة بطريقة تجعل القوى الأقل تميزًا (القيمة = 0.05) من 10 إلى ⁷ ، والقوى الأكثر سطوعًا (القيمة = 1 ، 0) من رتبة 10 ³ وما فوق).

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

يُظهر مركز الرسم التوضيحي الحد الأقصى للكتلة مع توزيع كتلي موحد نسبيًا في باقي الحقل.

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

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

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

صورة متكاملة للإحداثيات

، لنأخذ على سبيل المثال المنطقة في الزاوية اليسرى السفلية بالإحداثيات {3؛ 1} وفي الجزء العلوي الأيمن بإحداثيات {7 ؛ 5}. مجموع إحداثيات هذه المنطقة {168؛ 120} - {18 ؛ 45} - {28 ؛ 0} + {3 ؛ 0} هو {125 ؛ 75} ، العدد الإجمالي للعناصر هو 25 ، وبالتالي فإن إحداثيات مركزها ستكون {5 ؛ 3}.

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

صورة متكاملة للإحداثيات المرجحة. الخط الأكبر يشير إلى الأوزان

خذ بعين الاعتبار المنطقة الموجودة في الزاوية اليسرى السفلية بإحداثيات {2؛ 1} وفي الجزء العلوي الأيمن بإحداثيات {5 ؛ 4}. مجموع معاملات الترجيح لهذه المنطقة 4.8 - 1.0 - 0.6 + 0.2 هو 3.4 ، ومجموع إحداثياتها المرجحة {11.1 ؛ 13.2} - {0.5 ؛ 2.0} - {1.5 ؛ 0،0} + {0،1 ؛ 0،0} يساوي {9،2؛ 11.2}. وبذلك تكون الإحداثيات المرجحة لمركز هذه المنطقة {2.7 ؛ 3.3}.

للتأكد من أن هذه الدائرة تعمل حقًا ، يمكنك بصريًا - عن طريق تحويل الصورة المدمجة بإحداثيات مرجحة إلى حقل مسافة باستخدام تحويل المسافة ^[19] .

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

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

تلخيص كل ما سبق:

, , ( , R = 3) ― , , .
.
O(1).
O(M*N).

. ― . ― .

حان الوقت للانتباه إلى إحدى الميزات الرئيسية للصور المتكاملة ، والتي لا تزال تحد من نطاق تطبيقها ، أي استهلاك الموارد والاستقرار العددي. لذلك ، اعتمادًا على نطاق القيم التي تحتويها الصورة الأصلية ، قد يلزم نوع بيانات أطول لصورتها المتكاملة. على سبيل المثال ، عند حساب الانحرافات المعيارية ، بالإضافة إلى الصورة الأصلية (نطاق القيمة 0.255) ، يتم استخدام صورة تحتوي على مربعات للقيم المقابلة (نطاق القيمة 0.65535). في هذه الحالة ، الدقة ليست كافية لحساب صور متكاملة واسعة النطاق لـ 32 بت ^[20] .

لوحظت حالة مماثلة في حالة الصور المدمجة مع الإحداثيات المرجحة. في حد ذاتها ، تزيد قيمة مجموع الإحداثيات التي يجب تخزينها في الصورة المدمجة اعتمادًا على حجم الصورة N: بشكل تربيعي للحالة أحادية البعد 0 + 1 + 2 + ... + N - 1 = (N - 1) * N / 2 ومكعبًا لـ ثنائي الأبعاد N * (N - 1) * N / 2. على سبيل المثال ، لتخزين مجموع إحداثي صحيح لصورة بحجم 2048 × 2048 (يساوي 4292870144) ، فإن العدد الصحيح غير الموقّع 32 بت (القيمة القصوى 4294967295) بالكاد يكفي. عند حساب صور متكاملة أكبر ، يحدث تجاوز السعة.

يؤدي استخدام أرقام الفاصلة العائمة 32 بت في الصور المدمجة إلى تأخير مشكلة تجاوز السعة بمسافة فلكية (10 ³⁸ - 10 ¹⁰) ، ولكن في نفس الوقت ، تم تقليل دقة الحسابات مع الإحداثيات المرجحة بشكل كبير بسبب خطأ الاقتطاع المتراكم أثناء الجمع ^[21] .

القيمة المطلقة للخطأ في حساب مركز الكتلة الموزون لمنطقة بحجم 4 × 4 عناصر. تحتوي الصورة المدمجة على أرقام دقيقة واحدة (32 بت).

القيمة المطلقة للخطأ في حساب مركز الكتلة الموزون لمنطقة بحجم 32 × 32 عنصر. تحتوي الصورة المدمجة على أرقام دقيقة واحدة (32 بت).

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

لا تؤثر الزيادة في نطاق الأوزان على القيمة المطلقة للخطأ في حساب مركز الكتلة الموزون. يوضح الرسم البياني أخطاء المنطقة "الأسوأ" (في الزاوية العلوية اليمنى من الصورة المدمجة). حجم الصورة المدمجة 256 × 256 عنصر.

تنخفض القيمة المطلقة للخطأ في حساب المركز المرجح للكتلة مع زيادة حجم المنطقة. يوضح الرسم البياني أخطاء المنطقة "الأسوأ" (في الزاوية العلوية اليمنى من الصورة المدمجة).

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

أما بالنسبة للصور الأكبر حجمًا ، فيمكنك استخدام إحداثيات مرجحة مزدوجة الدقة أو إضافة مستوى آخر من التمييز: تقسيم الصورة الأصلية إلى عدة أجزاء وقراءة الصور المتكاملة بشكل منفصل لكل جزء من هذه الأجزاء. من وجهة نظر التعقيد الحسابي ، إذا تم استخدام أكثر من صورة متكاملة لحساب مجموع عناصر المنطقة ، ولكن هذا "أكثر من واحد" هو ثابت ، فإن تعقيد خوارزمية حساب المجموع لا يتغير.

استنتاج

من المحتمل أن يتم تكييف المثال أعلاه لاستخدام صورة متكاملة لتطوير خوارزمية مثالية O (1) لأخذ العينات حسب الأهمية (أخذ عينات الأهمية). الخوارزميات الحالية - والمستهلكة بشدة للموارد من وجهة نظر GPU - لها تعقيد خطي O (N) وتجد التطبيق في الأساليب الحديثة للإضاءة العالمية ^{[22 ، 23]} .

بشكل عام ، في رأيي ، تعتبر الصور المتكاملة واحدة من أكثر الخوارزميات استخفافًا. يمكن أن تكون بديلاً ممتازًا للخرائط المتعددة والتصفية متباينة الخواص في نفس الوقت ، ومع الأخذ في الاعتبار كيفية تنفيذ هذا الأخير على وحدة معالجة الرسومات ^{[24 ، 25]} ، فمن المحتمل جدًا أنها بالفعل إجراء أكثر فعالية.

المراجع

عرض القائمة

حساب مركز الكتلة لـ O (1) باستخدام صور متكاملة

N

مشكلة الجاذبية في مجال الزخم

صورة متكاملة

حل تقريبي لمشكلة الجاذبية باستخدام صورة متكاملة

استنتاج

المراجع

More articles: