Super 4PCS: تسريع التسجيل العالمي للسحابات النقطية عبر الفهرسة الذكية

يُعد اكتساب البيانات في المشاهد ذات الحجم الكبير عملية تتطلب تجميع المعلومات عبر عدة عمليات تصوير متعددة. إحدى الطرق الشائعة هي محاذاة أزواج من المسحات محليًا باستخدام خوارزمية نقطة التوافق المتكررة (ICP) أو متغيراتها، لكنها تتطلب مشاهد ثابتة وحركات صغيرة بين أزواج المسحات، مما يمنع تجميع البيانات عبر جلسات تصوير متعددة و/أو وسائط اكتساب مختلفة (مثل المسحات الثنائية أو المسحات العميقة). بديلًا لذلك، يمكن استخدام خوارزمية محاذاة عالمية تسمح بأن تكون المسحات في أي وضع ابتدائي. ومع أن الخوارزمية الحديثة في هذا المجال، وهي 4PCS، تُعد الأفضل حاليًا، إلا أنها تمتلك تعقيدًا زمنيًا تربيعيًا بالنسبة لعدد النقاط في البيانات، ما يحد بشكل كبير من تطبيقاتها على اكتساب البيئات الكبيرة. نقدم في هذا العمل خوارزمية Super 4PCS لمحاذاة السحابات النقطية عالميًا، وهي خوارزمية مثلى تُنفَّذ بزمن خطي (بما يتناسب مع عدد النقاط)، كما أنها حساسة للإخراج من حيث تعقيد مشكلة المحاذاة، بناءً على التداخل (المجهول مسبقًا) بين أزواج المسحات. من الناحية التقنية، نُعدّل الخوارزمية كمشكلة "حالة محددة" (instance problem)، ونحلها بكفاءة باستخدام هيكل بيانات فعّال يعتمد على فهرسة ذكية. تتميز الخوارزمية بالبساطة، والكفاءة في استخدام الذاكرة، والسرعة العالية. ونُظهر من خلال التجارب أن Super 4PCS تحقق تحسينًا كبيرًا في السرعة مقارنة بالطرق البديلة، وتتيح اكتسابًا غير منظم وفعال لمشاهد بمقاييس لم تكن ممكنة سابقًا. يُتاح الكود المصدري الكامل والبيانات المستخدمة لأغراض البحث عبر الرابط: http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/.