تسجيل مجموعة النقاط

عند وجود مجموعتين من النقاط، ينتج عن التسجيل الصلب تحويل صلب يربط إحدى المجموعتين بالأخرى. يُعرَّف التحويل الصلب بأنه تحويل لا يُغيّر المسافة بين أي نقطتين. عادةً ما يتكون هذا التحويل من إزاحة ودوران . ^{[ 12 ]} في حالات نادرة، قد يتم عكس مجموعة النقاط. يُعدّ التسجيل الصلب الأكثر استخدامًا في مجال الروبوتات ورؤية الحاسوب .

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

تستخدم بعض طرق تسجيل مجموعات النقاط خوارزميات لحل مشكلة مطابقة الرسوم البيانية الأكثر عمومية . ^{[ 11 ]} ومع ذلك، فإن التعقيد الحسابي لهذه الطرق يميل إلى أن يكون مرتفعًا، وهي تقتصر على التسجيلات الصلبة. في هذه المقالة، سنقتصر على دراسة خوارزميات التسجيل الصلب، حيث يُفترض أن التحويل يتضمن دورانات وانتقالات ثلاثية الأبعاد (وربما يشمل أيضًا تغييرًا موحدًا في الحجم).

مكتبة PCL (مكتبة السحابة النقطية) هي إطار عمل مفتوح المصدر لمعالجة السحابة النقطية متعددة الأبعاد والهندسة ثلاثية الأبعاد . وهي تتضمن العديد من خوارزميات تسجيل النقاط. ^{[ 15 ]}

في أبسط الحالات، يمكن للمرء أن يفترض أن جميع التطابقات صحيحة، مما يعني أن النقاط${\displaystyle m_{i},s_{i}\in \mathbb {R} ^{3}}$يتم إنشاؤها على النحو التالي:

${\displaystyle s_{i}=lRm_{i}+t+\epsilon _{i},i=1,\dots ,N}$

cb.1

أين${\displaystyle l>0}$هو عامل قياس موحد (في كثير من الحالات)${\displaystyle l=1}$يفترض${\displaystyle R\in {\text{SO}}(3)}$هي مصفوفة دوران ثلاثية الأبعاد مناسبة (${\displaystyle {\text{SO}}(d)}$هي المجموعة المتعامدة الخاصة من الدرجة${\displaystyle d}$)${\displaystyle t\in \mathbb {R} ^{3}}$هو متجه إزاحة ثلاثي الأبعاد و${\displaystyle \epsilon _{i}\in \mathbb {R} ^{3}}$يُحاكي الضوضاء المضافة غير المعروفة ( مثل الضوضاء الغاوسية ). على وجه التحديد، إذا كانت الضوضاء${\displaystyle \epsilon _{i}}$يُفترض أن يتبع توزيعًا غاوسيًا متساوي الخواص بمتوسط ​​صفر وانحراف معياري${\displaystyle \sigma _{i}}$، أي،${\displaystyle \epsilon _{i}\sim {\mathcal {N}}(0,\sigma _{i}^{2}I_{3})}$ثم يمكن إثبات أن عملية التحسين التالية تؤدي إلى تقدير الاحتمالية القصوى للمقياس والدوران والانتقال غير المعروفين:

${\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}{\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2}}$

cb.2

لاحظ أنه عندما يكون عامل القياس 1 ومتجه الإزاحة صفرًا، فإن عملية التحسين تستعيد صياغة مسألة وهبة . على الرغم من عدم تحدب عملية التحسين ( cb.2 ) بسبب عدم تحدب المجموعة${\displaystyle {\text{SO}}(3)}$أظهر العمل الرائد لبيرتولد كيه بي هورن أن المعادلة ( cb.2 ) تقبل في الواقع حلاً مغلقاً، وذلك بفصل تقدير المقياس والدوران والانتقال. ^{[ 16 ]} وقد توصل أرون وآخرون إلى نتائج مماثلة . ^{[ 17 ]} بالإضافة إلى ذلك، من أجل إيجاد تحويل فريد${\displaystyle (l,R,t)}$، على الأقل${\displaystyle N=3}$يلزم وجود نقاط غير متوازية في كل مجموعة نقاط.

في الآونة الأخيرة، قام برياليس وغونزاليس-خيمينيز بتطوير استرخاء شبه محدد باستخدام ازدواجية لاغرانج ، وذلك في حالة مجموعة النموذج${\displaystyle {\mathcal {M}}}$يحتوي على أشكال ثلاثية الأبعاد أولية مختلفة مثل النقاط والخطوط والمستويات (وهو الحال عندما يكون النموذج${\displaystyle {\mathcal {M}}}$(شبكة ثلاثية الأبعاد). ^{[ 18 ]} ومن المثير للاهتمام أن الاسترخاء شبه المحدد محكم تجريبياً، أي أنه يمكن استخراج حل أمثل عالميًا بشكل موثوق من حل الاسترخاء شبه المحدد.

من المعروف أن صيغة المربعات الصغرى ( cb.2 ) تُظهر أداءً سيئًا للغاية في وجود القيم الشاذة . وتُعرف مطابقة القيم الشاذة بأنها زوج من القياسات${\displaystyle s_{i}\leftrightarrow m_{i}}$وهذا يختلف عن النموذج التوليدي ( cb.1 ). في هذه الحالة، يمكن اعتبار نموذج توليدي مختلف على النحو التالي: ^{[ 19 ]}

${\displaystyle s_{i}={\begin{cases}lRm_{i}+t+\epsilon _{i}&{\text{if }}i-{\text{th pair is an inlier}}\\o_{i}&{\text{if }}i-{\text{th pair is an outlier}}\end{cases}}}$

cb.3

أين إذا${\displaystyle i-}$الزوج رقم 1${\displaystyle s_{i}\leftrightarrow m_{i}}$إذا كانت قيمة داخلية، فإنها تخضع لنموذج خالٍ من القيم الشاذة ( cb.1 )، أي${\displaystyle s_{i}}$يتم الحصول عليها من${\displaystyle m_{i}}$عن طريق تحويل مكاني بالإضافة إلى بعض التشويش الطفيف؛ ومع ذلك، إذا${\displaystyle i-}$الزوج رقم 1${\displaystyle s_{i}\leftrightarrow m_{i}}$إذا كان شاذاً،${\displaystyle s_{i}}$يمكن أن يكون أي متجه عشوائي${\displaystyle o_{i}}$بما أنه لا يمكن معرفة أي من التطابقات شاذة مسبقًا، فإن التسجيل القوي في ظل النموذج التوليدي ( cb.3 ) ذو أهمية قصوى لرؤية الحاسوب والروبوتات المستخدمة في العالم الحقيقي، لأن تقنيات مطابقة الميزات الحالية تميل إلى إخراج تطابقات مشوهة للغاية حيثما يتم تجاوز${\displaystyle 95\%}$قد تكون بعض المراسلات قيماً شاذة. ^{[ 20 ]}

بعد ذلك، سنصف العديد من النماذج الشائعة للتسجيل القوي.

أقصى قدر من الإجماع

يسعى التوافق الأقصى إلى إيجاد أكبر مجموعة من التطابقات التي تتوافق مع النموذج التوليدي ( cb.1 ) لبعض خيارات التحويل المكاني${\displaystyle (l,R,t)}$بصورة رسمية، فإن الإجماع الأقصى يحل مسألة التحسين التالية:

${\displaystyle \max _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3},{\mathcal {I}}}\vert {\mathcal {I}}\vert ,\quad {\text{subject to }}{\frac {1}{\sigma _{i}^{2}}}\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}\leq \xi ,\forall i\in {\mathcal {I}}}$

cb.4

أين${\displaystyle \vert {\mathcal {I}}\vert }$يشير إلى عدد عناصر المجموعة${\displaystyle {\mathcal {I}}}$يفرض القيد في ( cb.4 ) أن كل زوج من القياسات في مجموعة القياسات الداخلية${\displaystyle {\mathcal {I}}}$يجب أن تكون البواقي أصغر من عتبة محددة مسبقًا${\displaystyle \xi }$لسوء الحظ، أظهرت التحليلات الحديثة أن حل المسألة (cb.4) على مستوى العالم هو مسألة صعبة من نوع NP-Hard ، وعادةً ما تضطر الخوارزميات العالمية إلى اللجوء إلى تقنيات التفرع والتقييد (BnB) التي تتطلب تعقيدًا زمنيًا أُسّيًا في أسوأ الحالات. ^{[ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ]}

على الرغم من صعوبة حل مسألة تعظيم الإجماع بدقة، إلا أن هناك طرقًا استدلالية فعالة تُحقق أداءً جيدًا في التطبيق العملي. ومن أشهر هذه الطرق الاستدلالية طريقة توافق العينة العشوائية (RANSAC) . ^{[ 26 ]} تُعدّ RANSAC طريقة تكرارية تعتمد على افتراض الفرضيات والتحقق منها. في كل تكرار، تقوم الطريقة أولًا بأخذ عينة عشوائية من 3 من إجمالي عدد الفرضيات.${\displaystyle N}$يقوم بحساب المراسلات ووضع الفرضية${\displaystyle (l,R,t)}$باستخدام طريقة هورن، ^{[ 16 ]} تقوم الطريقة بتقييم القيود في ( cb.4 ) لحساب عدد التطابقات التي تتفق فعليًا مع هذه الفرضية (أي أنها تحسب الباقي).${\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}}$ويقارنها بالعتبة${\displaystyle \xi }$لكل زوج من القياسات). تتوقف الخوارزمية إما بعد إيجاد مجموعة توافق تحتوي على عدد كافٍ من التطابقات، أو بعد الوصول إلى العدد الإجمالي المسموح به من التكرارات. تتميز خوارزمية RANSAC بكفاءة عالية لأن الحساب الرئيسي لكل تكرار هو تنفيذ الحل المغلق في طريقة هورن. مع ذلك، فإن RANSAC غير حتمية، ولا تعمل بكفاءة إلا في نطاق نسبة القيم الشاذة المنخفضة ( على سبيل المثال، أقل من${\displaystyle 50\%}$)، لأن وقت تشغيله ينمو بشكل أسي بالنسبة لنسبة القيم الشاذة. ^{[ 20 ]}

لسدّ الفجوة بين مخطط RANSAC السريع ولكنه غير الدقيق، وخوارزمية BnB الدقيقة ولكنها شاملة، طوّرت الأبحاث الحديثة طرقًا تقريبية حتمية لحلّ مسألة تعظيم التوافق. ^{[ 21 ] [ 22 ] [ 27 ] [ 23 ]}

تقدير M

تستبدل طريقة التقدير M دالة الهدف الخاصة بالمربعات الصغرى في ( cb.2 ) بدالة تكلفة قوية أقل حساسية للقيم الشاذة. وبشكل رسمي، تسعى طريقة التقدير M إلى حل المشكلة التالية:

${\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho \left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}$

cb.5

أين${\displaystyle \rho (\cdot )}$يمثل هذا الخيار دالة التكلفة القوية. لاحظ أن اختيار${\displaystyle \rho (x)=x^{2}}$يستعيد تقدير المربعات الصغرى في ( cb.2 ). تتضمن دوال التكلفة القوية الشائعة ما يلي:${\displaystyle \ell _{1}}$خسارة المعيار L1، وخسارة هوبر ، ^{[ 29 ]} وخسارة جيرمان-مكلور، ^{[ 30 ]} وخسارة المربعات الصغرى المقتطعة . ^{[ 19 ] [ 8 ] [ 4 ]} يُعد تقدير M أحد أكثر النماذج شيوعًا للتقدير القوي في مجال الروبوتات ورؤية الحاسوب. ^{[ 31 ] [ 32 ]} نظرًا لأن دوال الهدف القوية عادةً ما تكون غير محدبة ( على سبيل المثال، خسارة المربعات الصغرى المقتطعة مقابل خسارة المربعات الصغرى)، فإن خوارزميات حل تقدير M غير المحدب تعتمد عادةً على التحسين المحلي ، حيث يتم أولًا توفير تخمين أولي، يليه تحسينات متكررة للتحويل لتقليل دالة الهدف باستمرار. يميل التحسين المحلي إلى العمل بشكل جيد عندما يكون التخمين الأولي قريبًا من الحد الأدنى العالمي، ولكنه أيضًا عرضة للتعثر في الحد الأدنى المحلي إذا تم توفير تهيئة سيئة.

عدم التحدب المتدرج

تُعدّ طريقة التدرج في عدم التحدب (GNC) إطار عمل عام لحل مسائل التحسين غير المحدبة دون الحاجة إلى تهيئة مسبقة. وقد حققت نجاحًا في تطبيقات الرؤية الحاسوبية والتعلم الآلي المبكرة. ^{[ 33 ] [ 34 ]} وتتمثل الفكرة الأساسية وراء GNC في حل المسائل غير المحدبة المعقدة بالبدء من مسائل محدبة سهلة. وبالتحديد، بالنسبة لدالة تكلفة قوية معينة.${\displaystyle \rho (\cdot )}$يمكن للمرء أن يبني دالة بديلة${\displaystyle \rho _{\mu }(\cdot )}$مع معلمة فائقة${\displaystyle \mu }$، وهو ضبط يمكن أن يزيد تدريجياً من عدم تحدب الدالة البديلة${\displaystyle \rho _{\mu }(\cdot )}$حتى تتقارب مع الدالة المستهدفة${\displaystyle \rho (\cdot )}$^{[ 34 ] [ 35 ]} لذلك ، عند كل مستوى من مستويات المعلمة الفائقة${\displaystyle \mu }$، يتم حل مسألة التحسين التالية:

${\displaystyle l_{\mu }^{\star },R_{\mu }^{\star },t_{\mu }^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho _{\mu }\left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}$

cb.6

أثبت بلاك ورانجاراجان أن دالة الهدف لكل عملية تحسين ( cb.6 ) يمكن تحويلها إلى مجموع المربعات الصغرى الموزونة ودالة عملية القيم الشاذة على الأوزان التي تحدد موثوقية التحسين في كل زوج من القياسات. ^{[ 33 ]} باستخدام ثنائية بلاك-رانجاراجان وGNC المُصممة خصيصًا لدالة جيرمان-مكلور، طور تشو وآخرون خوارزمية التسجيل العالمي السريع التي تتميز بالمتانة ضد حوالي${\displaystyle 80\%}$القيم الشاذة في التطابقات. ^{[ 30 ]} وفي الآونة الأخيرة، أظهر يانغ وآخرون أن الاستخدام المشترك لـ GNC (المصمم خصيصًا لدالة Geman-McClure ودالة المربعات الصغرى المقتطعة) وازدواجية Black-Rangarajan يمكن أن يؤدي إلى حل عام لمشاكل التسجيل القوية، بما في ذلك سحب النقاط وتسجيل الشبكة. ^{[ 35 ]}

تسجيل قوي معتمد

لا تُقدم أيٌّ من خوارزميات التسجيل القوية المذكورة أعلاه (باستثناء خوارزمية BnB التي تعمل في وقت أُسّي في أسوأ الحالات) ضماناتٍ للأداء ، مما يعني أن هذه الخوارزميات قد تُعطي تقديراتٍ خاطئة تمامًا دون سابق إنذار. لذلك، تُعدّ هذه الخوارزميات غير مرغوب فيها للتطبيقات الحساسة للسلامة مثل القيادة الذاتية.

في الآونة الأخيرة، طوّر يانغ وزملاؤه أول خوارزمية تسجيل قوية وموثوقة، تُسمى تقدير المربعات الصغرى المقتطعة والاسترخاء شبه المحدد (TEASER). ^{[ 19 ]} في تسجيل سحابة النقاط، لا تُخرج TEASER تقديرًا للتحويل فحسب، بل تُحدد أيضًا مدى مثالية هذا التقدير. تعتمد TEASER على مُقدِّر المربعات الصغرى المقتطعة (TLS) التالي:

${\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\min \left({\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2},{\bar {c}}^{2}\right)}$

cb.7

والتي يتم الحصول عليها عن طريق اختيار دالة التكلفة القوية لـ TLS${\displaystyle \rho (x)=\min(x^{2},{\bar {c}}^{2})}$، أين${\displaystyle {\bar {c}}^{2}}$هو ثابت مُحدد مسبقًا يُحدد الحد الأقصى المسموح به للبواقي التي تُعتبر نقاطًا داخلية. تتميز دالة الهدف TLS بالخاصية التالية: بالنسبة للتطابقات الداخلية (${\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}}$يتم تطبيق عقوبة المربعات الصغرى المعتادة؛ بينما بالنسبة لتطابقات القيم الشاذة (${\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}>{\bar {c}}^{2}}$لا تُفرض أي عقوبة ويتم تجاهل القيم الشاذة. إذا تم حل مسألة تحسين المربعات الصغرى ( cb.7 ) للوصول إلى الحل الأمثل الشامل، فإنها تُكافئ تطبيق طريقة هورن على نقاط التطابق الداخلية فقط.

مع ذلك، يُعدّ حلّ المعادلة ( cb.7 ) تحديًا كبيرًا نظرًا لطبيعتها التوافقية. يحلّ برنامج TEASER المعادلة ( cb.7 ) على النحو التالي  : (أ) يبني قياسات ثابتة بحيث يمكن فصل تقدير المقياس والدوران والانتقال وحلّها بشكل منفصل، وهي استراتيجية مستوحاة من طريقة هورن الأصلية؛ (ب) يُطبّق تقدير المربعات الصغرى الانتقالية نفسه على كلٍّ من المسائل الفرعية الثلاث، حيث يمكن حلّ مسألة المقياس بدقة باستخدام خوارزمية تُسمى التصويت التكيفي، ويمكن تحويل مسألة الدوران إلى برنامج شبه محدد (SDP) حيث يكون التحويل دقيقًا عمليًا، ^{[ 8 ]} حتى مع وجود عدد كبير من القيم الشاذة؛ ويمكن حلّ مسألة الانتقال باستخدام التصويت التكيفي لكل مكوّن على حدة. يتوفر هنا تطبيق سريع يستفيد من GNC كمصدر مفتوح . عمليًا، يمكن لبرنامج TEASER تحمّل أكثر من${\displaystyle 99\%}$التطابقات والتسلسلات الشاذة بالمللي ثانية.

بالإضافة إلى تطوير برنامج TEASER، أثبت يانغ وآخرون أيضًا أنه في ظل بعض الشروط البسيطة على بيانات السحابة النقطية، فإن التحويل المقدر لبرنامج TEASER له أخطاء محدودة مقارنة بالتحويل الحقيقي. ^{[ 19 ]}

تم تقديم خوارزمية أقرب نقطة تكرارية (ICP) بواسطة بيسل وماكاي. ^{[ 36 ]} تقوم الخوارزمية بتسجيل صلب بطريقة تكرارية عن طريق التناوب في (i) بالنظر إلى التحويل، وإيجاد أقرب نقطة في${\displaystyle {\mathcal {S}}}$لكل نقطة في${\displaystyle {\mathcal {M}}}$و(٢) بالنظر إلى التطابقات، إيجاد أفضل تحويل صلب عن طريق حل مسألة المربعات الصغرى ( cb.2 ). وعلى هذا النحو، يكون ذلك أفضل إذا كانت الوضعية الأولية لـ${\displaystyle {\mathcal {M}}}$قريب بما فيه الكفاية من${\displaystyle {\mathcal {S}}}$في الشفرة الزائفة ، يتم تنفيذ الخوارزمية الأساسية على النحو التالي:

خوارزمية ICP( M , S ) θ := θ 0 طالما لم يتم التسجيل: X := ∅ لكل m i ∊ T ( M , θ ): ŝ i := أقرب نقطة في S إلى m i X := X + ⟨m i, ŝ i⟩ θ : = least_squares ( X ) إرجاع θ

least_squaresهنا، تقوم الدالة بإجراء تحسين المربعات الصغرى لتقليل المسافة في كل من${\displaystyle \langle m_{i},{\hat {s}}_{i}\rangle }$الأزواج، باستخدام الحلول المغلقة التي قدمها هورن ^{[ 16 ]} وأرون. ^{[ 17 ]}

لأن دالة تكلفة التسجيل تعتمد على إيجاد أقرب نقطة في${\displaystyle {\mathcal {S}}}$إلى كل نقطة في${\displaystyle {\mathcal {M}}}$قد يتغير هذا أثناء تشغيل الخوارزمية. ولذلك، يصعب إثبات أن خوارزمية ICP ستتقارب بدقة إلى الحل الأمثل المحلي. ^{[ 37 ]} في الواقع، تجريبياً، لا تتقارب خوارزميتا ICP و EM-ICP إلى الحد الأدنى المحلي لدالة التكلفة. ^{[ 37 ]} ومع ذلك، ولأن خوارزمية ICP سهلة الفهم والتطبيق، فإنها لا تزال الخوارزمية الأكثر شيوعاً لتسجيل مجموعات النقاط. ^{[ 37 ]} وقد تم اقتراح العديد من المتغيرات لخوارزمية ICP، والتي تؤثر على جميع مراحل الخوارزمية بدءاً من اختيار النقاط ومطابقتها وصولاً إلى استراتيجية التصغير. ^{[ 13 ] [ 38 ]} على سبيل المثال، تُطبق خوارزمية التوقع والتعظيم على خوارزمية ICP لتشكيل طريقة EM-ICP، وتُطبق خوارزمية Levenberg-Marquardt على خوارزمية ICP لتشكيل طريقة LM-ICP . ^{[ 12 ]}

طُوِّرت خوارزمية مطابقة النقاط القوية (RPM) بواسطة غولد وآخرون ^{[ 39 ]} . تُجري هذه الطريقة عملية التسجيل باستخدام التلدين الحتمي والتخصيص المرن للتطابقات بين مجموعات النقاط. في حين أن التطابق الناتج عن أقرب جار في خوارزمية ICP يكون ثنائيًا، تستخدم خوارزمية RPM تطابقًا مرنًا حيث يمكن أن يكون التطابق بين أي نقطتين في أي مكان من 0 إلى 1، على الرغم من أنه يتقارب في النهاية إلى 0 أو 1. التطابقات الموجودة في خوارزمية RPM تكون دائمًا تطابقًا واحدًا لواحد، وهو ما لا يكون الحال دائمًا في خوارزمية ICP. ^{[ 14 ]} لنفترض${\displaystyle m_{i}}$كن${\displaystyle i}$النقطة رقم 1 في${\displaystyle {\mathcal {M}}}$و${\displaystyle s_{j}}$كن${\displaystyle j}$النقطة رقم 1 في${\displaystyle {\mathcal {S}}}$مصفوفة المطابقة${\displaystyle \mathbf {\mu } }$يُعرَّف على النحو التالي:

${\displaystyle \mu _{ij}={\begin{cases}1&{\text{if point }}m_{i}{\text{ corresponds to point }}s_{j}\\0&{\text{otherwise}}\end{cases}}}$

rpm.1

تُعرَّف المسألة على النحو التالي: بالنظر إلى مجموعتين من النقاط${\displaystyle {\mathcal {M}}}$و${\displaystyle {\mathcal {S}}}$أوجد التحويل الأفيني${\displaystyle T}$ومصفوفة المطابقة${\displaystyle \mathbf {\mu } }$الذي يربط بينهما على أفضل وجه. ^{[ 39 ]} معرفة التحويل الأمثل تُسهّل تحديد مصفوفة المطابقة، والعكس صحيح. مع ذلك، تُحدد خوارزمية RPM كليهما في آنٍ واحد. يمكن تحليل التحويل إلى متجه إزاحة ومصفوفة تحويل :

${\displaystyle T(m)=\mathbf {A} m+\mathbf {t} }$

المصفوفة${\displaystyle \mathbf {A} }$يتكون في ثنائي الأبعاد من أربعة معلمات منفصلة${\displaystyle \lbrace a,\theta ,b,c\rbrace }$وهي على التوالي: المقياس، والدوران، ومكونات القص الرأسية والأفقية. وتكون دالة التكلفة كما يلي:

${\displaystyle \operatorname {cost} =\sum _{j=1}^{N}\sum _{i=1}^{M}\mu _{ij}\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}+g(\mathbf {A} )-\alpha \sum _{j=1}^{N}\sum _{i=1}^{M}\mu _{ij}}$

2 دورة في الدقيقة

رهناً بـ${\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}\leq 1}$،${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}\leq 1}$،${\textstyle \forall ij~\mu _{ij}\in \lbrace 0,1\rbrace }$. ال${\displaystyle \alpha }$يُؤثر هذا المصطلح على الهدف نحو ارتباط أقوى عن طريق تقليل التكلفة إذا احتوت مصفوفة التطابق على عدد أكبر من القيم 1.${\displaystyle g(\mathbf {A} )}$يُستخدم لتنظيم التحويل الأفيني عن طريق معاقبة القيم الكبيرة لمكونات المقياس والقص:

${\displaystyle g(\mathbf {A} (a,\theta ,b,c))=\gamma (a^{2}+b^{2}+c^{2})}$

لبعض معلمات التنظيم${\displaystyle \gamma }$.

تعمل طريقة RPM على تحسين دالة التكلفة باستخدام خوارزمية Softassign . سيتم هنا اشتقاق الحالة أحادية البعد. بالنظر إلى مجموعة من المتغيرات${\displaystyle \lbrace Q_{j}\rbrace }$أين${\displaystyle Q_{j}\in \mathbb {R} ^{1}}$متغير${\displaystyle \mu _{j}}$يرتبط بكل${\displaystyle Q_{j}}$بحيث${\textstyle \sum _{j=1}^{J}\mu _{j}=1}$الهدف هو إيجاد${\displaystyle \mathbf {\mu } }$الذي يحقق أقصى قدر${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}$يمكن صياغة ذلك كمشكلة مستمرة عن طريق إدخال مُعامل تحكم${\displaystyle \beta >0}$في طريقة التلدين الحتمية ، يكون معامل التحكم${\displaystyle \beta }$تزداد قيمتها تدريجياً مع تشغيل الخوارزمية. لنفترض${\displaystyle \mathbf {\mu } }$يكون:

${\displaystyle \mu _{\hat {j}}={\frac {\exp {(\beta Q_{\hat {j}})}}{\sum _{j=1}^{J}\exp {(\beta Q_{j})}}}}$

3 دورة في الدقيقة

تُعرف هذه الدالة باسم دالة سوفتماكس .${\displaystyle \beta }$مع ازديادها، تقترب من قيمة ثنائية كما هو مطلوب في المعادلة ( rpm.1 ). يمكن الآن تعميم المشكلة على الحالة ثنائية الأبعاد، حيث بدلاً من تعظيم${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}$، يتم تحقيق أقصى قدر من التالي:

${\displaystyle E(\mu )=\sum _{j=1}^{N}\sum _{i=0}^{M}\mu _{ij}Q_{ij}}$

4 دورة في الدقيقة

أين

${\displaystyle Q_{ij}=-(\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}-\alpha )=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}$

هذا واضح، إلا أن القيود المفروضة على${\displaystyle \mu }$هي قيود مصفوفية عشوائية مزدوجة :${\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}=1}$و${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}=1}$وبالتالي، لا يمكن التعبير عن مقام المعادلة ( rpm.3 ) ببساطة في حالة ثنائية الأبعاد. ولتحقيق هذه الشروط، يمكن الاستعانة بنتيجة سينكهورن ^{[ 39 ]} التي تنص على إمكانية الحصول على مصفوفة عشوائية مزدوجة من أي مصفوفة مربعة جميع عناصرها موجبة، وذلك من خلال عملية تكرارية لتطبيع الصفوف والأعمدة بالتناوب. وعليه، تُكتب الخوارزمية على النحو التالي: ^{[ 39 ]}

خوارزمية RPM2D${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$ر := 0 أ , θ ب , ج := 0 β := β 0${\displaystyle {\hat {\mu }}_{ij}:=1+\epsilon }$بينما β < β f : بينما لم يتقارب  μ : // تحديث معلمات التطابق عن طريق التعيين الناعم${\displaystyle Q_{ij}:=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}$${\displaystyle \mu _{ij}^{0}:=\exp(\beta Q_{ij})}$// تطبيق طريقة سينكهورن بينما${\displaystyle {\hat {\mu }}}$لم يتم التقارب: // تحديث${\displaystyle {\hat {\mu }}}$عن طريق التطبيع عبر جميع الصفوف:${\displaystyle {\hat {\mu }}_{ij}^{1}:={\frac {{\hat {\mu }}_{ij}^{0}}{\sum _{i=1}^{M+1}{\hat {\mu }}_{ij}^{0}}}}$// تحديث${\displaystyle {\hat {\mu }}}$عن طريق التطبيع عبر جميع الأعمدة:${\displaystyle {\hat {\mu }}_{ij}^{0}:={\frac {{\hat {\mu }}_{ij}^{1}}{\sum _{j=1}^{N+1}{\hat {\mu }}_{ij}^{1}}}}$// تحديث معلمات الوضعية باستخدام طريقة الانحدار الإحداثي، وتحديث θ باستخدام الحل التحليلي تحديث t باستخدام الحل التحليلي قم بتحديث a و b و c باستخدام طريقة نيوتن${\displaystyle \beta :=\beta _{r}\beta }$${\displaystyle \gamma :={\frac {\gamma }{\beta _{r}}}}$أعد a و b و c و θ و t

حيث تمثل معلمة التحكم في التلدين الحتمي${\displaystyle \beta }$يتم ضبطه مبدئيًا على${\displaystyle \beta _{0}}$ويزداد بمعامل${\displaystyle \beta _{r}}$حتى تصل إلى القيمة القصوى${\displaystyle \beta _{f}}$مجموع عمليات الجمع في خطوات التطبيع يساوي${\displaystyle M+1}$و${\displaystyle N+1}$بدلاً من مجرد${\displaystyle M}$و${\displaystyle N}$بسبب القيود المفروضة على${\displaystyle \mu }$هي أوجه عدم المساواة. وعلى هذا النحو${\displaystyle M+1}$و${\displaystyle N+1}$العناصر th هي متغيرات ركود .

يمكن أيضًا توسيع نطاق الخوارزمية لتشمل مجموعات النقاط في ثلاثة أبعاد أو أبعاد أعلى. القيود المفروضة على مصفوفة التطابق${\displaystyle \mathbf {\mu } }$تكون القيم متطابقة في الحالة ثلاثية الأبعاد كما هي في الحالة ثنائية الأبعاد. وبالتالي، يبقى هيكل الخوارزمية دون تغيير، مع اختلاف رئيسي في كيفية حل مصفوفات الدوران والانتقال. ^{[ 39 ]}

وصلة رقيقة ذات نقاط تثبيت متينة

تُعزز خوارزمية مطابقة النقاط القوية باستخدام دوال الصفائح الرقيقة (TPS-RPM) التي طورها تشوي ورانجاراجان طريقة RPM لإجراء تسجيل غير صلب من خلال تحديد معلمات التحويل كدالة صفائح رقيقة . ^{[ 14 ]} ومع ذلك، ولأن تحديد معلمات دوال الصفائح الرقيقة يقتصر على ثلاثة أبعاد فقط، فلا يمكن توسيع نطاق هذه الطريقة لتشمل المشكلات التي تتضمن أربعة أبعاد أو أكثر.

قدّم تسين وكانادي ^{[ 37 ]} أسلوب ارتباط النواة (KC) لتسجيل مجموعات النقاط. بالمقارنة مع ICP، فإن خوارزمية KC أكثر مقاومة للبيانات المشوّشة. على عكس ICP، حيث تُؤخذ أقرب نقطة في المشهد فقط في الاعتبار لكل نقطة في النموذج، فإن كل نقطة في المشهد هنا تؤثر على كل نقطة في النموذج. ^{[ 37 ]} ولذلك، تُعدّ هذه خوارزمية تسجيل متعددة الارتباطات . بالنسبة لدالة نواة معينة${\displaystyle K}$، الارتباط الأساسي${\displaystyle KC}$من نقطتين${\displaystyle x_{i},x_{j}}$يتم تعريفها على النحو التالي: ^{[ 37 ]}

${\displaystyle KC(x_{i},x_{j})=\int K(x,x_{i})\cdot K(x,x_{j})dx}$

kc.1

دالة النواة${\displaystyle K}$عادةً ما يتم اختيار نواة متناظرة وغير سالبة لتسجيل مجموعة النقاط، على غرار تلك المستخدمة في تقدير كثافة نافذة بارزن . تُستخدم نواة غاوس عادةً لبساطتها، على الرغم من إمكانية استبدالها بنوى أخرى مثل نواة إيبانشنيكوف ونواة المكعب الثلاثي. ^{[ 37 ]} ارتباط النواة لمجموعة نقاط كاملة${\displaystyle {\mathcal {\chi }}}$يتم تعريفها على أنها مجموع ارتباطات النواة لكل نقطة في المجموعة مع كل نقطة أخرى في المجموعة: ^{[ 37 ]}

${\displaystyle KC({\mathcal {X}})=\sum _{i\neq j}KC(x_{i},x_{j})=2\sum _{i<j}KC(x_{i},x_{j})}$

kc.2

يتناسب لوغاريتم معامل KC لمجموعة نقاط، ضمن عامل ثابت، مع إنتروبيا المعلومات . لاحظ أن معامل KC هو مقياس لـ "تراص" مجموعة النقاط؛ فمن البديهي أنه إذا كانت جميع النقاط في المجموعة في نفس الموقع، فسيكون معامل KC كبيرًا. دالة التكلفة لخوارزمية تسجيل مجموعة النقاط لبعض معلمات التحويل.${\displaystyle \theta }$يُعرَّف على النحو التالي:

${\displaystyle \operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-\sum _{m\in {\mathcal {M}}}\sum _{s\in {\mathcal {S}}}KC(s,T(m,\theta ))}$

kc.3

ينتج عن بعض العمليات الجبرية ما يلي:

${\displaystyle KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=KC({\mathcal {S}})+KC(T({\mathcal {M}},\theta ))-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )}$

kc.4

يتم تبسيط التعبير بملاحظة أن${\displaystyle KC({\mathcal {S}})}$مستقل عن${\displaystyle \theta }$علاوة على ذلك، وبافتراض التسجيل الدقيق،${\displaystyle KC(T({\mathcal {M}},\theta ))}$ثابت عندما${\displaystyle \theta }$يتغير ذلك لأن المسافة الإقليدية بين كل زوج من النقاط تبقى ثابتة تحت التحويل الصلب . لذا يمكن إعادة كتابة المعادلة أعلاه على النحو التالي:

${\displaystyle KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=C-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )}$

kc.5

تُعرَّف تقديرات كثافة النواة على النحو التالي:

${\displaystyle P_{\mathcal {M}}(x,\theta )={\frac {1}{M}}\sum _{m\in {\mathcal {M}}}K(x,T(m,\theta ))}$

${\displaystyle P_{\mathcal {S}}(x)={\frac {1}{N}}\sum _{s\in {\mathcal {S}}}K(x,s)}$

ويمكن بعد ذلك إثبات أن دالة التكلفة هي معامل الارتباط بين تقديري كثافة النواة:

${\displaystyle \operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-N^{2}\int _{x}P_{\mathcal {M}}\cdot P_{\mathcal {S}}~dx}$

kc.6

بعد تحديد دالة التكلفة ، تستخدم الخوارزمية ببساطة خوارزمية التدرج الهبوطي لإيجاد التحويل الأمثل. ونظرًا لأن حساب دالة التكلفة من الصفر في كل تكرار مكلف حسابيًا، يتم استخدام نسخة منفصلة من دالة التكلفة (المعادلة kc.6 ). تقديرات كثافة النواة${\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}$يمكن تقييمها عند نقاط الشبكة وتخزينها في جدول بحث . على عكس خوارزمية ICP والطرق ذات الصلة، ليس من الضروري إيجاد أقرب جار، مما يجعل خوارزمية KC بسيطة نسبيًا في التنفيذ.

بالمقارنة مع خوارزميتي ICP و EM-ICP لمجموعات النقاط ثنائية وثلاثية الأبعاد المشوشة، فإن خوارزمية KC أقل حساسية للضوضاء وتؤدي إلى تسجيل صحيح في أغلب الأحيان. ^{[ 37 ]}

طُوِّرَتْ خوارزمية انحراف النقاط المتماسك (CPD) بواسطة ميرونينكو وسونغ. ^{[ 13 ] [ 41 ]} تعتمد هذه الخوارزمية على نهج احتمالي لمحاذاة مجموعات النقاط، على غرار طريقة GMM KC. وخلافًا للأساليب السابقة للتسجيل غير الصلب التي تفترض نموذج تحويل الشرائح الرقيقة، فإن خوارزمية انحراف النقاط المتماسك لا تتأثر بنموذج التحويل المستخدم.${\displaystyle {\mathcal {M}}}$تمثل هذه القيم مراكز نموذج خليط غاوسي (GMM). عندما تكون مجموعتا النقاط متطابقتين على النحو الأمثل، يكون التطابق هو القيمة القصوى لاحتمالية GMM اللاحقة لنقطة بيانات معينة. وللحفاظ على البنية الطوبولوجية لمجموعات النقاط، تُجبر مراكز GMM على التحرك بشكل متماسك كمجموعة واحدة. تُستخدم خوارزمية تعظيم التوقع لتحسين دالة التكلفة. ^{[ 13 ]}

لنفترض وجود M نقطة في${\displaystyle {\mathcal {M}}}$و N نقطة في${\displaystyle {\mathcal {S}}}$دالة كثافة الاحتمال لنموذج العزوم المعممة (GMM) لنقطة s هي:

${\displaystyle p(s)=\sum _{i=1}^{M+1}P(i)p(s|i)}$

cpd.1

حيث، في الأبعاد D ،${\displaystyle p(s|i)}$هل التوزيع الغاوسي متمركز عند النقطة${\displaystyle m_{i}\in {\mathcal {M}}}$.

${\displaystyle p(s|i)={\frac {1}{(2\pi \sigma ^{2})^{D/2}}}\exp {\left(-{\frac {\lVert s-m_{i}\rVert ^{2}}{2\sigma ^{2}}}\right)}}$

احتمالات العضوية${\displaystyle P(i)={\frac {1}{M}}}$تكون متساوية لجميع مكونات نموذج العزوم المعممة. ويُرمز إلى وزن التوزيع المنتظم بـ${\displaystyle w\in [0,1]}$إذن، يكون نموذج الخليط كما يلي:

${\displaystyle p(s)=w{\frac {1}{N}}+(1-w)\sum _{i=1}^{M}{\frac {1}{M}}p(s|i)}$

cpd.2

يتم إعادة تحديد معلمات مراكز GMM بواسطة مجموعة من المعلمات${\displaystyle \theta }$يتم تقديرها عن طريق تعظيم الاحتمالية. وهذا يعادل تقليل دالة الاحتمالية اللوغاريتمية السالبة :

${\displaystyle E(\theta ,\sigma ^{2})=-\sum _{j=1}^{N}\log \sum _{i=1}^{M+1}P(i)p(s|i)}$

cpd.3

حيث يُفترض أن البيانات مستقلة وموزعة توزيعًا متطابقًا . احتمال التطابق بين نقطتين${\displaystyle m_{i}}$و${\displaystyle s_{j}}$يُعرَّف بأنه الاحتمال اللاحق لمركز GMM بالنظر إلى نقطة البيانات:

${\displaystyle P(i|s_{j})={\frac {P(i)p(s_{j}|i)}{p(s_{j})}}}$

تُستخدم خوارزمية تعظيم التوقع ( EM) لإيجاد${\displaystyle \theta }$و${\displaystyle \sigma ^{2}}$تتكون خوارزمية EM من خطوتين. أولاً، في خطوة التوقع (E-step) أو خطوة التقدير ، تُخمّن قيم المعلمات ("القيم القديمة" للمعلمات)، ثم تستخدم نظرية بايز لحساب توزيعات الاحتمال اللاحق.${\displaystyle P^{\text{old}}(i,s_{j})}$من مكونات الخليط. ثانيًا، في خطوة M أو خطوة التعظيم ، يتم إيجاد قيم المعلمات "الجديدة" عن طريق تقليل القيمة المتوقعة لدالة الاحتمالية السالبة الكاملة، أي دالة التكلفة:

${\displaystyle \operatorname {cost} =-\sum _{j=1}^{N}\sum _{i=1}^{M+1}P^{\text{old}}(i|s_{j})\log(P^{\text{new}}(i)p^{\text{new}}(s_{j}|i))}$

cpd.4

تجاهل الثوابت المستقلة عن${\displaystyle \theta }$و${\displaystyle \sigma }$يمكن التعبير عن المعادلة ( cpd.4 ) على النحو التالي:

${\displaystyle \operatorname {cost} (\theta ,\sigma ^{2})={\frac {1}{2\sigma ^{2}}}\sum _{j=1}^{N}\sum _{i=1}^{M+1}P^{\text{old}}(i|s_{j})\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}+{\frac {N_{\mathbf {P} }D}{2}}\log {\sigma ^{2}}}$

cpd.5

أين

${\displaystyle N_{\mathbf {P} }=\sum _{j=0}^{N}\sum _{i=0}^{M}P^{\text{old}}(i|s_{j})\leq N}$

مع${\displaystyle N=N_{\mathbf {P} }}$فقط إذا${\displaystyle w=0}$الاحتمالات اللاحقة لمكونات نموذج خليط غاوسي (GMM) المحسوبة باستخدام قيم المعلمات السابقة${\displaystyle P^{\text{old}}}$يكون:

${\displaystyle P^{\text{old}}(i|s_{j})={\frac {\exp \left(-{\frac {1}{2\sigma ^{{\text{old}}2}}}\lVert s_{j}-T(m_{i},\theta ^{\text{old}})\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{{\text{old}}2}}}\lVert s_{j}-T(m_{k},\theta ^{\text{old}})\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}}$

cpd.6

يؤدي تقليل دالة التكلفة في المعادلة ( cpd.5 ) بالضرورة إلى تقليل دالة الاحتمالية اللوغاريتمية السالبة E في المعادلة ( cpd.3 ) ما لم تكن قد وصلت بالفعل إلى قيمة دنيا محلية. ^{[ 13 ]} وبالتالي، يمكن التعبير عن الخوارزمية باستخدام الشفرة الزائفة التالية، حيث تمثل مجموعات النقاط${\displaystyle {\mathcal {M}}}$و${\displaystyle {\mathcal {S}}}$يتم تمثيلها على النحو التالي:${\displaystyle M\times D}$و${\displaystyle N\times D}$المصفوفات${\displaystyle \mathbf {M} }$و${\displaystyle \mathbf {S} }$على التوالي: ^{[ 13 ]}

خوارزمية التطوير المهني المستمر${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$θ := θ 0 تهيئة 0 ≥ ث ≥ 1${\displaystyle \sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}}$بينما لم يتم التسجيل: // خطوة التوقع، احسب P لـ i ∊ [1, M ] و j ∊ [1, N ]:${\displaystyle p_{ij}:={\frac {\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{k},\theta )\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}}$// خطوة M، حل التحويل الأمثل { θ , σ 2 } := solve ( S , M , P ) return θ

حيث المتجه${\displaystyle \mathbf {1} }$هو متجه عمودي مكون من وحدات. solveتختلف الدالة باختلاف نوع التسجيل المُجرى. على سبيل المثال، في التسجيل الصلب، يكون الناتج عبارة عن مقياس a ، ومصفوفة دوران.${\displaystyle \mathbf {R} }$، ومتجه إزاحة${\displaystyle \mathbf {t} }$المعلمة${\displaystyle \theta }$يمكن كتابتها على شكل مجموعة من هذه العناصر:

${\displaystyle \theta =\lbrace a,\mathbf {R} ,\mathbf {t} \rbrace }$

والتي يتم تهيئتها إلى واحد، وهي مصفوفة الوحدة ، ومتجه عمودي من الأصفار:

${\displaystyle \theta _{0}=\lbrace 1,\mathbf {I} ,\mathbf {0} \rbrace }$

مجموعة النقاط المتراصفة هي:

${\displaystyle T(\mathbf {M} )=a\mathbf {M} \mathbf {R} ^{T}+\mathbf {1} \mathbf {t} ^{T}}$

ويمكن كتابة دالة solve_rigidالتسجيل الصلب على النحو التالي، مع شرح اشتقاق الجبر في ورقة ميرونينكو لعام 2010. ^{[ 13 ]}

solve_rigid ( S , M , P ) N P := 1 T P1${\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }$${\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }$${\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}$${\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}$${\displaystyle \mathbf {A} :={\hat {\mathbf {S} ^{T}}}\mathbf {P} ^{T}{\hat {\mathbf {M} }}}$U , V := svd ( A ) // تحليل القيم المفردة للمصفوفة A = UΣVT C := diag(1, …, 1, det( UVT ) ) // diag (ξ) هي المصفوفة القطرية المُشكّلة من المتجه ξ R := UCVT${\displaystyle a:={\frac {\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} )}{\operatorname {tr} (\mathbf {{\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }}} )}}}$// tr هو أثر المصفوفة t := μ s − a R μ m${\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} (\mathbf {{\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }}} )-a\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} ))}$إرجاع { a , R , t }, σ 2

في عملية التسجيل الأفيني، حيث يكون الهدف هو إيجاد تحويل أفيني بدلاً من تحويل صلب، يكون الناتج عبارة عن مصفوفة تحويل أفيني.${\displaystyle \mathbf {B} }$وترجمة${\displaystyle \mathbf {t} }$بحيث تكون مجموعة النقاط المتراصفة هي:

${\displaystyle T(\mathbf {M} )=\mathbf {M} \mathbf {B} ^{T}+\mathbf {1} \mathbf {t} ^{T}}$

ويمكن كتابة دالة solve_affineالتسجيل الصلب على النحو التالي، مع شرح اشتقاق الجبر في ورقة ميرونينكو لعام 2010. ^{[ 13 ]}

حل_المعادلة_الخطية ( S , M , P ) N P := 1 T P1${\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }$${\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }$${\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}$${\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}$${\displaystyle \mathbf {B} :=({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }})({\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }})^{-1}}$t := μ s − B μ m${\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }})-\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }}\mathbf {B} ^{T}))}$إرجاع { B , t }, σ 2

من الممكن أيضًا استخدام CPD مع التسجيل غير الصلب باستخدام معلمات مشتقة باستخدام حساب التفاضل والتكامل . ^{[ 13 ]}

يمكن حساب مجاميع التوزيعات الغاوسية في زمن خطي باستخدام تحويل غاوس السريع (FGT). ^{[ 13 ]} وبالتالي، فإن التعقيد الزمني لـ CPD هو${\displaystyle O(M+N)}$وهو أسرع بكثير من الناحية التقاربية من${\displaystyle O(MN)}$الأساليب. ^{[ 13 ]}

الانجراف النقطي المتماسك مع هندسة السطح المحلية (LSG-CPD)

يُعدّ انحراف النقاط المتماسك مع هندسة السطح المحلي (LSG-CPD) أحد أنواع تسجيل سحابة النقاط الصلبة. ^{[ 44 ]} تُضيف هذه الطريقة، بشكلٍ تكيفي، مستوياتٍ مختلفة من عقوبة النقطة إلى المستوى فوق عقوبة النقطة إلى النقطة، وذلك بناءً على استواء السطح المحلي. ينتج عن ذلك مكونات GMM ذات تباينات غير متناحية، بدلاً من التباينات المتناحية في انحراف النقاط المتماسك الأصلي. ^{[ 13 ]} يتم نمذجة مصفوفة التباين غير المتناحية على النحو التالي:

${\displaystyle \Sigma _{m}^{-1}={\frac {1}{\sigma ^{2}}}\left(\alpha _{m}\mathbf {n} _{m}\mathbf {n} _{m}^{T}+\mathbf {I} \right)}$

lsg-cpd.1

أين

${\displaystyle \alpha _{m}={\frac {1-\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}{1+\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}}\alpha _{max}}$

lsg-cpd.2

${\displaystyle \Sigma _{m}}$هي مصفوفة التغاير غير المتناحية للنقطة رقم m في المجموعة المستهدفة؛${\displaystyle \mathbf {n} _{m}}$هو المتجه العمودي المقابل لنفس النقطة؛${\displaystyle \mathbf {I} }$هي مصفوفة الوحدة، تعمل كمنظم، وتسحب المشكلة بعيدًا عن حالة عدم التحديد.${\displaystyle \alpha _{m}}$يمثل معامل الجزاء (دالة سيجمويد معدلة)، والذي يتم ضبطه بشكل تكيفي لإضافة مستويات مختلفة من الجزاء بين النقطة والمستوى اعتمادًا على مدى استواء السطح المحلي. ويتحقق ذلك من خلال تقييم تباين السطح.${\displaystyle \kappa _{m}}$^{[ 45 ]} ضمن نطاق الجوار لنقطة الهدف رقم m.${\displaystyle \alpha _{max}}$يمثل الحد الأعلى للعقوبة.

تُصاغ عملية تسجيل السحابة النقطية كمسألة تقدير الاحتمال الأقصى (MLE) وتُحل باستخدام خوارزمية التوقع والتعظيم (EM). في خطوة التوقع (E)، يُعاد صياغة حساب التطابق إلى عمليات تلاعب بسيطة بالمصفوفات، ويُحسب بكفاءة على وحدة معالجة الرسومات (GPU). في خطوة التحسين (M)، يُصمم تحسين غير مقيد على زمرة لي المصفوفية لتحديث التحويل الصلب للتسجيل بكفاءة. بالاستفادة من التغايرات الهندسية المحلية، تُظهر الطريقة أداءً فائقًا من حيث الدقة والمتانة في مواجهة الضوضاء والقيم الشاذة، مقارنةً بطريقة CPD الأساسية. ^{[ 46 ]} من المتوقع تحسين أداء وقت التشغيل بفضل تسريع حساب التطابق بواسطة وحدة معالجة الرسومات. يتوفر تطبيق LSG-CPD كمصدر مفتوح هنا .

طُوِّرت هذه الخوارزمية عام ٢٠١٣ بواسطة ح. عساليه لتسهيل عملية تسجيل صور السونار. ^{[ ٤٧ ]} تتميز هذه الأنواع من الصور باحتوائها على مستويات عالية من التشويش، لذا من المتوقع وجود العديد من القيم الشاذة في مجموعات النقاط المراد مطابقتها. توفر خوارزمية SCS متانة عالية في مواجهة القيم الشاذة، ويمكنها التفوق على أداء خوارزميتي ICP وCPD في وجودها. لا تستخدم خوارزمية SCS التحسين التكراري في الفضاءات عالية الأبعاد، وهي ليست احتمالية ولا طيفية. تستطيع خوارزمية SCS مطابقة التحويلات الصلبة وغير الصلبة، وتُحقق أفضل أداء عندما يكون التحويل المستهدف بين ثلاث وست درجات حرية .