تحويل التوزيعات الطبيعية

تحويل التوزيعات الطبيعية ( NDT ) عبارة عن خوارزمية تسجيل سحابة نقطية قدمها Peter Biber و Wolfgang Straßer في عام 2003 ، أثناء العمل في جامعة Tübingen .

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

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

الصياغة

يتم إنشاء وظيفة NDT المرتبطة بسحابة نقطية عن طريق تقسيم المساحة في الخلايا العادية. لكل خلية ، من الممكن تحديد المتوسط

$\textstyle \mathbf {q} ={\frac {1}{n}}\sum _{i}\mathbf {x_{i}}$

والمتغير

$\textstyle \mathbf {S} ={\frac {1}{n}}\sum _{i}\left(\mathbf {x} _{i}-\mathbf {q} \right)\left(\mathbf {x} _{i}-\mathbf {q} \right)^{\top }$

حيث ان $n$ تمثل النقاط السحابة $\mathbf {x} _{1},\dots ,\mathbf {x} _{n}$ التي تقع داخل الخلية. الكثافة الاحتمالية لنقطة ما في موقع مكاني تعطى بتحديد موقع $\mathbf {x}$ داخل الخلية ثم يتم إعطاء التوزيع الطبيعي

$e^{-{\frac {1}{2}}\left(\mathbf {x} -\mathbf {q} \right)^{\top }\mathbf {S} ^{-1}\left(\mathbf {x} -\mathbf {q} \right)}$ .

يمكن تعيين نقطتين سحابيتين من خلال التحول الإقليدي $f$ مع مصفوفة الدوران $\mathbf {R}$ وشعاع التحويل $\mathbf {t}$

$f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )=\mathbf {R} \mathbf {x} +\mathbf {t}$

تلك الخرائط من السحابة الثانية إلى الأولى ، محددة بزوايا الدوران ومكونات التحويل.

تسجل الخوارزمية ذات النقطتين السحابيتين عن طريق تحسين معلمات التحويل التي تعين السحابة الثانية إلى الأولى ، فيما يتعلق بتابع الخسارة على أساس NDT لسحابة النقطة الأولى ، مما يحل المشكلة التالية

$\arg \min _{\mathbf {R} ,\mathbf {t} }\left\{-\sum _{i}\operatorname {NDT} \left(f_{\mathbf {R} ,\mathbf {t} }\left(\mathbf {x_{i}} \right)\right)\right\}$

حيث تمثل دالة الخسارة الاحتمالية المنفية ، التي يتم الحصول عليها من خلال تطبيق التحويل على جميع النقاط في السحابة الثانية وتجميع قيمة NDT في كل نقطة محولة $f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )$ . الخسارة مستمرة وقابلة للتفاضل ، ويمكن تحسينها بطرق قائمة على التدرج (في الصيغة الأصلية ، استخدم المؤلفون طريقة نيوتن ).

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

مصادر

• Biber، Peter؛ Straßer، Wolfgang (2003). "The normal distributions transform: A new approach to laser scan matching". Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453). ج. 3.
• Dong، Zhen؛ Liang، Fuxun؛ Yang، Bisheng؛ Xu، Yusheng؛ Zang، Yufu؛ Li، Jianping؛ Wang، Yuan؛ Dai، Wenxia؛ Fan، Hongchao (2020). "Registration of large-scale terrestrial laser scanner point clouds: A review and benchmark". Elsevier. ج. 163: 327–342. Bibcode:2020JPRS..163..327D. DOI:10.1016/j.isprsjprs.2020.03.013.
• Li، Leihui؛ Wang، Riwei؛ Zhang، Xuping (2021). "A Tutorial Review on Point Cloud Registrations: Principle, Classification, Comparison, and Technology Challenges". Hindawi. ج. 2021.
• Magnusson، Martin. The three-dimensional normal-distributions transform: an efficient representation for registration, surface analysis, and loop detection (Ph.D. thesis). Örebro universitet.

روابط خارجية

• "Register two point clouds using NDT algorithm". MathWorks. مؤرشف من الأصل في 2023-01-28.