ในด้านคอมพิวเตอร์วิชั่นการรู้จำรูปแบบและหุ่นยนต์การลงทะเบียนชุดจุดหรือที่เรียกว่าการลงทะเบียนกลุ่มจุดหรือการจับคู่สแกนคือกระบวนการค้นหาการแปลง เชิงพื้นที่ ( เช่นการปรับขนาดการหมุนและการเลื่อน ) ที่จัดเรียงกลุ่มจุด สองกลุ่มให้ตรงกัน จุดประสงค์ของการค้นหาการแปลงดังกล่าวรวมถึงการรวมชุดข้อมูลหลายชุดเข้าเป็นแบบจำลองที่สอดคล้องกันทั่วโลก (หรือกรอบพิกัด) และการแมปการวัดใหม่ไปยังชุดข้อมูลที่รู้จักเพื่อระบุคุณลักษณะหรือเพื่อประมาณท่าทางข้อมูลกลุ่มจุด 3 มิติแบบดิบมักได้มาจากLidarและกล้อง RGB-Dกลุ่มจุด 3 มิติยังสามารถสร้างได้จากอัลกอริธึมคอมพิวเตอร์วิชั่น เช่นการสร้างสามเหลี่ยมการปรับกลุ่มและล่าสุดคือการประมาณความลึกของภาพแบบโมโนคูลาร์โดยใช้การเรียนรู้เชิงลึก สำหรับการลงทะเบียนชุดจุด 2 มิติที่ใช้ในการประมวลผลภาพและ การลงทะเบียนภาพตามคุณลักษณะชุดจุดอาจเป็นพิกเซลพิกัด 2 มิติที่ได้จากการสกัดคุณลักษณะจากภาพ ตัวอย่างเช่นการตรวจจับมุมการลงทะเบียนจุดคลาวด์มีการใช้งานอย่างกว้างขวางในการขับขี่อัตโนมัติ [ ^{1 ]}การประมาณการเคลื่อนไหวและการสร้าง 3 มิติ [ ^{2 ] การ} ตรวจจับวัตถุ และการประมาณท่าทาง^{[ 3 ] [ 4 ] การ}จัดการหุ่นยนต์ [ ^{5 ]}การระบุตำแหน่งและการสร้างแผนที่พร้อมกัน (SLAM) ^{[ 6 ] [ 7 ]}การต่อภาพพาโนรามา [ ^{8 ]}ความเป็นจริงเสมือนและความเป็นจริงเสริม^{[ 9 ] และ}การถ่าย^ภาพทางการแพทย์^{[ 10 ]}

ในกรณีพิเศษ การลงทะเบียนชุดจุดสองชุดที่แตกต่างกันเพียงแค่การหมุนสามมิติ ( กล่าวคือไม่มีการปรับขนาดและการเลื่อน) เรียกว่าปัญหา Wahbaและมีความเกี่ยวข้องกับปัญหา procrustes แบบตั้งฉากด้วย

ปัญหาอาจสรุปได้ดังนี้: ^{[ 11 ]} ให้เป็นเซตจุดสองเซตที่มีขนาดจำกัดในปริภูมิเวกเตอร์จริงมิติจำกัดซึ่งประกอบด้วย จุด และตามลำดับ ( เช่นกู้คืนกรณีทั่วไปของ เมื่อและเป็นเซตจุด 3 มิติ) ปัญหาคือการหาการแปลงที่จะนำไปใช้กับเซตจุด "โมเดล" ที่เคลื่อนที่เพื่อให้ความแตกต่าง (โดยทั่วไปกำหนดในแง่ของระยะทางแบบยุคลิด ระหว่างจุด ) ระหว่างและเซต "ฉาก" ที่คงที่นั้นมีค่าน้อยที่สุด กล่าวอีกนัยหนึ่ง ต้องการการแมปจากไปยังซึ่งให้การจัดเรียงที่ดีที่สุดระหว่างเซต "โมเดล" ที่แปลงแล้วกับเซต "ฉาก" การแมปอาจประกอบด้วยการแปลงแบบแข็งหรือแบบไม่แข็ง โมเดลการแปลงอาจเขียนได้เป็น โดยใช้ ซึ่งเซตจุดโมเดลที่แปลงและลงทะเบียนแล้วคือ: ${\displaystyle \lbrace {\mathcal {M}},{\mathcal {S}}\rbrace }$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle M}$${\displaystyle N}$${\displaystyle d=3}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle T}$

${\displaystyle T({\mathcal {M}})}$

1

ดังนั้น ผลลัพธ์ของอัลกอริธึมการลงทะเบียนชุดจุดจึงเป็นการแปลงที่เหมาะสมที่สุด เพื่อให้จุดนั้นจัดเรียงได้ดีที่สุดกับจุด นั้น ตามแนวคิดของฟังก์ชันระยะทางที่กำหนดไว้: ${\displaystyle T^{\star }}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle \operatorname {dist} (\cdot ,\cdot )}$

${\displaystyle T^{\star }=\arg \min _{T\in {\mathcal {T}}}{\text{dist}}(T({\mathcal {M}}),{\mathcal {S}})}$

2

โดยใช้สัญลักษณ์ เพื่อแสดงถึงเซตของการแปลงที่เป็นไปได้ทั้งหมดที่การปรับให้เหมาะสมพยายามค้นหา ตัวเลือกที่นิยมที่สุดสำหรับฟังก์ชันระยะทางคือการหาค่ากำลังสองของระยะทางแบบยุคลิดสำหรับทุกคู่ของจุด: ${\displaystyle {\mathcal {T}}}$

${\displaystyle \operatorname {dist} (T({\mathcal {M}}),{\mathcal {S}})=\sum _{m\in T({\mathcal {M}})}\Vert m-s_{m}\Vert _{2}^{2},\quad s_{m}=\arg \min _{s\in {\mathcal {S}}}\Vert sm\Vert _{2}^{2}}$

3

โดยที่แทนค่านอร์ม 2 ของเวกเตอร์และคือจุดที่สอดคล้องกันในเซตที่มีระยะทางสั้นที่สุดไปยังจุดที่กำหนดในเซตหลังจากการแปลง การลดค่าฟังก์ชันดังกล่าวในการลงทะเบียนแบบแข็งเกร็งเทียบเท่ากับการแก้ปัญหา แบบกำลังสองน้อยที่สุด${\displaystyle \|\cdot \|_{2}}$${\displaystyle s_{m}}$${\displaystyle {\mathcal {S}}}$${\displaystyle m}$${\displaystyle {\mathcal {M}}}$

เมื่อมีการกำหนดจุดจับคู่ ( เช่น ) ไว้ก่อนการปรับให้เหมาะสม เช่น โดยใช้ เทคนิค การจับคู่คุณลักษณะการปรับให้เหมาะสมจึงจำเป็นต้องประมาณค่าการแปลงเท่านั้น การลงทะเบียนประเภทนี้เรียกว่าการลงทะเบียนตามจุดจับคู่ในทางกลับกัน หากไม่ทราบจุดจับคู่ การปรับให้เหมาะสมจะต้องค้นหาจุดจับคู่และการแปลงไปพร้อมกัน การลงทะเบียนประเภทนี้เรียกว่า การลง ทะเบียน ท่าทางและจุดจับคู่พร้อมกัน${\displaystyle s_{m}\leftrightarrow m}$

เมื่อกำหนดชุดจุดสองชุด การลงทะเบียนแบบแข็งจะให้การแปลงแบบแข็งซึ่งแมปชุดจุดหนึ่งไปยังอีกชุดหนึ่ง การแปลงแบบแข็งถูกกำหนดให้เป็นการแปลงที่ไม่เปลี่ยนแปลงระยะห่างระหว่างจุดสองจุดใดๆ โดยทั่วไปการแปลงดังกล่าวประกอบด้วยการแปลและการหมุน [ ^{12 ] ใน}บางกรณี ชุดจุดอาจถูกสะท้อนด้วย ในด้านหุ่นยนต์และคอมพิวเตอร์วิชั่น การลงทะเบียนแบบแข็งมีการใช้งานมากที่สุด

เมื่อกำหนดชุดจุดสองชุด การลงทะเบียนแบบไม่แข็งตัวจะให้การแปลงแบบไม่แข็งตัวซึ่งแมปชุดจุดหนึ่งไปยังอีกชุดหนึ่ง การแปลงแบบไม่แข็งตัวรวมถึงการแปลงเชิงเส้นเช่นการปรับขนาดและการแมปเฉือนอย่างไรก็ตาม ในบริบทของการลงทะเบียนชุดจุด การลงทะเบียนแบบไม่แข็งตัวมักเกี่ยวข้องกับการแปลงแบบไม่เชิงเส้น หาก ทราบ โหมดลักษณะเฉพาะของการเปลี่ยนแปลงของชุดจุด การแปลงแบบไม่เชิงเส้นอาจกำหนดพารามิเตอร์โดยค่าลักษณะเฉพาะ^{[ 13 ]}การแปลงแบบไม่เชิงเส้นอาจกำหนดพารามิเตอร์เป็นสปลายแผ่นบางได้ เช่นกัน ^{[ 14 ] [ 13 ]}

วิธีการลงทะเบียนชุดจุดบางวิธีใช้อัลกอริธึมที่แก้ ปัญหาการจับคู่กราฟทั่วไป^{[ 11 ]}อย่างไรก็ตาม ความซับซ้อนในการคำนวณของวิธีการดังกล่าวมีแนวโน้มสูง และจำกัดเฉพาะการลงทะเบียนแบบแข็ง ในบทความนี้ เราจะพิจารณาเฉพาะอัลกอริธึมสำหรับการลงทะเบียนแบบแข็ง ซึ่งการแปลงจะถือว่ามีการหมุนและการแปลแบบ 3 มิติ (อาจรวมถึงการปรับขนาดแบบสม่ำเสมอด้วย)

PCL (Point Cloud Library)เป็นเฟรมเวิร์กโอเพนซอร์สสำหรับการประมวลผลจุดคลาวด์ n มิติและเรขาคณิต 3 มิติ ประกอบด้วยอัลกอริธึมการลงทะเบียนจุดหลายรายการ^{[ 15 ]}

วิธีการที่ใช้การจับคู่สมมติว่ามีการจับคู่ที่คาดการณ์ไว้สำหรับทุกจุดดังนั้น เราจึงได้สถานการณ์ที่ทั้งเซตของจุดและมีจุดและมีการจับคู่ที่กำหนดไว้แล้ว ${\displaystyle m\leftrightarrow s_{m}}$${\displaystyle m\in {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle N}$${\displaystyle m_{i}\leftrightarrow s_{i},i=1,\dots ,N}$

ในกรณีที่ง่ายที่สุด เราสามารถสมมติได้ว่าการจับคู่ทั้งหมดถูกต้อง ซึ่งหมายความว่าจุดต่างๆถูกสร้างขึ้นดังนี้:${\displaystyle m_{i},s_{i}\in \mathbb {R} ^{3}}$

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

ซีบี.1

โดยที่เป็นตัวประกอบการปรับขนาดแบบสม่ำเสมอ (ในหลายกรณีถือว่า ) เป็น เมทริกซ์การหมุน 3 มิติที่เหมาะสม( เป็นกลุ่มเชิงตั้งฉากพิเศษที่มีดีกรี) เป็นเวกเตอร์การแปล 3 มิติ และจำลองสัญญาณรบกวนแบบบวกที่ไม่ทราบค่า ( เช่นสัญญาณรบกวนแบบเกาส์เซียน ) โดยเฉพาะอย่างยิ่ง หากสมมติว่าสัญญาณรบกวนเป็นไปตามการแจกแจงแบบเกาส์เซียนแบบไอโซโทรปิกที่มีค่าเฉลี่ยเป็นศูนย์และส่วนเบี่ยงเบนมาตรฐานนั่นคือแล้วการปรับให้เหมาะสมต่อไปนี้สามารถแสดงให้เห็นว่าให้ค่าประมาณความน่าจะเป็นสูงสุดสำหรับมาตราส่วน การหมุน และการแปลที่ไม่ทราบค่า:${\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}}$

ซีบี.2

โปรดทราบว่าเมื่อปัจจัยการปรับขนาดเป็น 1 และเวกเตอร์การแปลเป็นศูนย์ การปรับให้เหมาะสมจะกลับคืนสู่สูตรของปัญหา Wahbaแม้ว่าการปรับให้เหมาะสม ( cb.2 ) จะไม่นูนเนื่องจากเซตไม่นูน แต่ผลงานสำคัญของBerthold KP Hornแสดงให้เห็นว่า ( cb.2 ) ยอมรับวิธีแก้ปัญหาแบบปิดได้จริง โดยการแยกการประมาณค่าของมาตราส่วน การหมุน และการแปล^{[ 16 ]} Arun et al . ^{[ 17 ]}ค้นพบผลลัพธ์ที่คล้ายกันนอกจากนี้ เพื่อที่จะหาการแปลงที่ไม่ซ้ำกันจำเป็นต้องมีจุดที่ไม่เรียงกัน อย่างน้อย ในแต่ละเซตของจุด${\displaystyle {\text{SO}}(3)}$${\displaystyle (l,R,t)}$${\displaystyle N=3}$

เมื่อไม่นานมานี้ Briales และ Gonzalez-Jimenez ได้พัฒนาการผ่อนคลายแบบกึ่งกำหนดโดยใช้ความเป็นคู่ของลากรางจ์สำหรับกรณีที่ชุดแบบจำลองประกอบด้วยรูปทรงพื้นฐาน 3 มิติที่แตกต่างกัน เช่น จุด เส้น และระนาบ (ซึ่งเป็นกรณีที่แบบจำลองเป็นตาข่าย 3 มิติ) ^{[ 18 ]}ที่น่าสนใจคือ การผ่อนคลายแบบกึ่งกำหนดนั้นมีความกระชับเชิงประจักษ์ กล่าว คือ สามารถดึงโซลูชัน ที่เหมาะสมที่สุดทั่วโลกที่รับรองได้จากโซลูชันของการผ่อนคลายแบบกึ่งกำหนด ${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

สูตรกำลังสองน้อยที่สุด ( cb.2 ) เป็นที่ทราบกันดีว่าทำงานได้แย่มากเมื่อมีค่าผิด ปกติ การจับคู่ค่าผิดปกติคือคู่ของการวัดที่เบี่ยงเบนจากแบบจำลองการสร้าง ( cb.1 ) ในกรณีนี้ เราสามารถพิจารณาแบบจำลองการสร้างที่แตกต่างกันได้ดังนี้: ^{[ 19 ]}${\displaystyle s_{i}\leftrightarrow m_{i}}$

${\displaystyle s_{i}={\begin{cases}lRm_{i}+t+\epsilon _{i}&{\text{ถ้าคู่ที่ }}i เป็นค่าภายใน}}\\o_{i}&{\text{ถ้าคู่ที่ }}i เป็นค่าภายนอก}}\end{cases}}}$

ซีบี.3

โดยที่ถ้าคู่ที่ th เป็นค่าภายใน ก็จะเป็นไปตามแบบจำลองที่ปราศจากค่าภายนอก ( cb.1 ) กล่าวคือได้มาจากการแปลงเชิงพื้นที่บวกกับสัญญาณรบกวนเล็กน้อย อย่างไรก็ตาม ถ้าคู่ที่ th เป็นค่าภายนอก ก็อาจเป็นเวกเตอร์ใดๆ ก็ได้เนื่องจากไม่ทราบว่าการจับคู่ใดเป็นค่าภายนอกล่วงหน้า การลงทะเบียนที่แข็งแกร่งภายใต้แบบจำลองการสร้าง ( cb.3 ) จึงมีความสำคัญอย่างยิ่งสำหรับคอมพิวเตอร์วิชั่นและหุ่นยนต์ที่ใช้งานในโลกแห่งความเป็นจริง เพราะเทคนิคการจับคู่คุณลักษณะในปัจจุบันมักจะสร้างการจับคู่ที่เสียหายอย่างมาก โดยที่การจับคู่มากกว่า 1 ใน 2 อาจเป็นค่าภายนอก^{[ 20 ]}${\displaystyle i-}$${\displaystyle s_{i}\leftrightarrow m_{i}}$${\displaystyle s_{i}}$${\displaystyle m_{i}}$${\displaystyle i-}$${\displaystyle s_{i}\leftrightarrow m_{i}}$${\displaystyle s_{i}}$${\displaystyle o_{i}}$${\displaystyle 95\%}$

ต่อไป เราจะอธิบายรูปแบบทั่วไปหลายประการสำหรับการลงทะเบียนที่มีประสิทธิภาพ

การหา ฉันทามติสูงสุดมุ่งที่จะค้นหาชุดการจับคู่ที่ใหญ่ที่สุดซึ่งสอดคล้องกับแบบจำลองการสร้าง ( 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}}}$

ซีบี.4

โดยที่แสดงถึงจำนวนสมาชิกของเซตข้อจำกัดใน ( cb.4 ) บังคับให้การวัดทุกคู่ในเซต inlier ต้องมีค่าตกค้างน้อยกว่าเกณฑ์ที่กำหนดไว้ล่วงหน้าน่าเสียดายที่การวิเคราะห์ล่าสุดแสดงให้เห็นว่าการแก้ปัญหา (cb.4) ทั่วโลกนั้นเป็นปัญหาNP-Hardและโดยทั่วไปแล้วอัลกอริทึมทั่วโลกจะต้องใช้ เทคนิค branch-and-bound (BnB) ซึ่งมีความซับซ้อนของเวลาแบบเลขชี้กำลังในกรณีที่เลวร้ายที่สุด^{[ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ]}${\displaystyle \vert {\คณิตศาสตร์ {I}}\vert }$${\displaystyle {\คณิตศาสตร์ {I}}}$${\displaystyle {\คณิตศาสตร์ {I}}}$${\displaystyle \xi }$

แม้ว่าการแก้ปัญหาการเพิ่มความเห็นพ้องให้มากที่สุดอย่างแม่นยำจะเป็นเรื่องยาก แต่ก็มีฮิวริสติกที่มีประสิทธิภาพซึ่งทำงานได้ดีในทางปฏิบัติ หนึ่งในฮิวริสติกที่เป็นที่นิยมมากที่สุดคือแบบแผนRandom Sample Consensus (RANSAC) ^{[ 26 ]} RANSAC เป็นวิธีการตั้งสมมติฐานและตรวจสอบแบบวนซ้ำ ในแต่ละรอบการวนซ้ำ วิธีการนี้จะสุ่มเลือก 3 จากจำนวนการจับคู่ทั้งหมดก่อน แล้วคำนวณสมมติฐานโดยใช้วิธีของ Horn ^{[ 16 ]}จากนั้นวิธีการจะประเมินข้อจำกัดใน ( cb.4 ) เพื่อนับจำนวนการจับคู่ที่สอดคล้องกับสมมติฐานดังกล่าว (กล่าวคือ คำนวณค่าตกค้างและเปรียบเทียบกับค่าเกณฑ์สำหรับแต่ละคู่ของการวัด) อัลกอริทึมจะสิ้นสุดลงเมื่อพบชุดความเห็นพ้องที่มีการจับคู่เพียงพอ หรือเมื่อถึงจำนวนรอบการวนซ้ำทั้งหมดที่อนุญาต RANSAC มีประสิทธิภาพสูงเนื่องจากการคำนวณหลักในแต่ละรอบการวนซ้ำคือการดำเนินการแก้ปัญหาแบบปิดในวิธีของ Horn อย่างไรก็ตาม RANSAC ไม่สามารถกำหนดได้แน่นอนและทำงานได้ดีเฉพาะในสภาวะที่มีอัตราส่วนค่าผิดปกติต่ำ ( เช่นต่ำกว่า) เนื่องจากเวลาทำงานจะเพิ่มขึ้นแบบเลขชี้กำลังตามอัตราส่วนค่าผิดปกติ^{[ 20 ]}${\displaystyle N}$${\displaystyle (l,R,t)}$${\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}}$${\displaystyle \xi }$${\displaystyle 50\%}$

เพื่อเติมเต็มช่องว่างระหว่างวิธีการ RANSAC ที่รวดเร็วแต่ไม่แม่นยำ และการเพิ่มประสิทธิภาพ BnB ที่แม่นยำแต่ครอบคลุม งานวิจัยล่าสุดได้พัฒนาวิธีการประมาณค่าแบบกำหนดเพื่อแก้ปัญหาการเพิ่มความเห็นพ้องสูงสุด^{[ 21 ] [ 22 ] [ 27 ] [ 23 ]}

วิธีการกำจัดค่าผิดปกติมีเป้าหมายเพื่อประมวลผลชุดข้อมูลการจับคู่ที่ผิดเพี้ยนสูงก่อนที่จะประเมินการแปลงเชิงพื้นที่ แรงจูงใจในการกำจัดค่าผิดปกติคือการลดจำนวนการจับคู่ที่ผิดปกติลงอย่างมาก ในขณะที่ยังคงรักษาการจับคู่ที่ถูกต้องไว้ เพื่อให้การปรับให้เหมาะสมกับการแปลงทำได้ง่ายและมีประสิทธิภาพมากขึ้น ( เช่น RANSAC ทำงานได้ไม่ดีเมื่ออัตราส่วนค่าผิดปกติสูงแต่ทำงานได้ค่อนข้างดีเมื่ออัตราส่วนค่าผิดปกติต่ำกว่า) ${\displaystyle 95\%}$${\displaystyle 50\%}$

Parra และคณะได้เสนอวิธีการที่เรียกว่า Guaranteed Outlier Removal (GORE) ซึ่งใช้ข้อจำกัดทางเรขาคณิตเพื่อตัดการจับคู่ที่ผิดปกติออกไป ในขณะที่ยังคงรับประกันว่าจะรักษาการจับคู่ที่ปกติไว้^{[ 20 ]} GORE ได้รับการพิสูจน์แล้วว่าสามารถลดอัตราส่วนของค่าผิดปกติได้อย่างมาก ซึ่งสามารถเพิ่มประสิทธิภาพของการเพิ่มประสิทธิภาพฉันทามติโดยใช้ RANSAC หรือ BnB ได้อย่างมีนัยสำคัญ Yang และ Carlone ได้เสนอให้สร้างการวัดแบบคู่ที่ไม่เปลี่ยนแปลงตามการแปลและการหมุน (TRIMs) จากชุดการวัดดั้งเดิม และฝัง TRIMs เป็นขอบของกราฟที่มีโหนดเป็นจุด 3 มิติ เนื่องจากค่าปกติมีความสอดคล้องกันเป็นคู่ในแง่ของมาตราส่วน จึงต้องสร้างกลุ่มภายในกราฟ ดังนั้น การใช้อัลกอริทึมที่มีประสิทธิภาพในการคำนวณกลุ่มสูงสุดของกราฟสามารถค้นหาค่าปกติและตัดค่าผิดปกติได้อย่างมีประสิทธิภาพ^{[ 4 ]}วิธีการกำจัดค่าผิดปกติโดยใช้กลุ่มสูงสุดยังแสดงให้เห็นว่ามีประโยชน์อย่างมากในปัญหาการลงทะเบียนชุดจุดในโลกแห่งความเป็นจริง^{[ 19 ]} Parra et al.เสนอแนวคิดการกำจัดค่าผิดปกติที่คล้ายกันเช่นกัน^{[ 28 ]}

การประมาณค่าแบบ 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)}$

ซีบี.5

โดยที่แทนการเลือกฟังก์ชันต้นทุนที่แข็งแกร่ง โปรดทราบว่าการเลือกจะกู้คืนการประมาณค่ากำลังสองน้อยที่สุดใน ( cb.2 ) ฟังก์ชันต้นทุนที่แข็งแกร่งที่เป็นที่นิยม ได้แก่การสูญเสียแบบนอร์มการสูญเสียแบบ Huber ^{[ 29 ]}การสูญเสียแบบ Geman-McClure ^{[ 30 ]}และการสูญเสียกำลังสองน้อยที่สุดแบบตัดทอน^{[ 19 ] [ 8 ] [ 4 ]}การประมาณค่า M เป็นหนึ่งในกระบวนทัศน์ที่เป็นที่นิยมมากที่สุดสำหรับการประมาณค่าที่แข็งแกร่งในด้านหุ่นยนต์และคอมพิวเตอร์วิชั่น^{[ 31 ] [ 32 ]}เนื่องจากฟังก์ชันวัตถุประสงค์ที่แข็งแกร่งมักจะไม่เป็นแบบนูน ( เช่นการสูญเสียกำลังสองน้อยที่สุดแบบตัดทอนเทียบกับการสูญเสียกำลังสองน้อยที่สุด) อัลกอริทึมสำหรับการแก้ปัญหาการประมาณค่า M ที่ไม่นูนมักจะขึ้นอยู่กับการเพิ่มประสิทธิภาพเฉพาะที่โดยที่การคาดเดาเริ่มต้นจะถูกให้ไว้ก่อน จากนั้นจึงทำการปรับปรุงการแปลงซ้ำ ๆ เพื่อลดฟังก์ชันวัตถุประสงค์ลงเรื่อย ๆ การหาค่าเหมาะสมที่สุดในระดับท้องถิ่นมักจะได้ผลดีเมื่อค่าเริ่มต้นที่คาดเดาไว้ใกล้เคียงกับค่าต่ำสุดโดยรวม แต่ก็มีแนวโน้มที่จะติดอยู่ในค่าต่ำสุดเฉพาะที่หากค่าเริ่มต้นที่ให้มานั้นไม่เหมาะสม ${\displaystyle \rho (\cdot )}$${\displaystyle \rho (x)=x^{2}}$${\displaystyle \ell _{1}}$

ความไม่นูนแบบไล่ระดับ (GNC) เป็นกรอบงานอเนกประสงค์สำหรับการแก้ปัญหาการเพิ่มประสิทธิภาพที่ไม่นูนโดยไม่ต้องเริ่มต้น ซึ่งประสบความสำเร็จในการใช้งานด้านการมองเห็นและการเรียนรู้ของเครื่องในยุคแรกๆ^{[ 33 ] [ 34 ]}แนวคิดหลักเบื้องหลัง GNC คือการแก้ปัญหาที่ไม่นูนที่ยากโดยเริ่มจากปัญหาที่นูนง่าย โดยเฉพาะอย่างยิ่ง สำหรับฟังก์ชันต้นทุนที่แข็งแกร่งที่กำหนดเราสามารถสร้างฟังก์ชันตัวแทนด้วยพารามิเตอร์ไฮเปอร์ซึ่งการปรับแต่งสามารถเพิ่มความไม่นูนของฟังก์ชันตัวแทนได้ทีละน้อยจนกว่าจะลู่เข้าสู่ฟังก์ชันเป้าหมาย[ ^{34 ] [ 35 ] ดังนั้น}ในแต่ละระดับของพารามิเตอร์ไฮเปอร์จะมีการแก้การเพิ่มประสิทธิภาพดังต่อไปนี้:${\displaystyle \rho (\cdot )}$${\displaystyle \rho _{\mu }(\cdot )}$${\displaystyle \mu }$${\displaystyle \rho _{\mu }(\cdot )}$${\displaystyle \rho (\cdot )}$${\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)}$

ซีบี.6

Black และ Rangarajan พิสูจน์ว่าฟังก์ชันวัตถุประสงค์ของการเพิ่มประสิทธิภาพแต่ละครั้ง ( cb.6 ) สามารถแปลงเป็นผลรวมของกำลังสองน้อยที่สุดแบบถ่วงน้ำหนักและฟังก์ชันกระบวนการค่าผิดปกติบนน้ำหนักที่กำหนดความเชื่อมั่นของการเพิ่มประสิทธิภาพในแต่ละคู่ของการวัด^{[ 33 ]}โดยใช้ความเป็นคู่ของ Black-Rangarajan และ GNC ที่ปรับแต่งสำหรับฟังก์ชัน Geman-McClure นั้น Zhou และคณะ ได้ พัฒนาอัลกอริทึมการลงทะเบียนทั่วโลกที่รวดเร็วซึ่งมีความทนทานต่อค่าผิดปกติในการจับคู่^{[ 30 ]}เมื่อไม่นานมานี้ Yang และคณะได้แสดงให้เห็นว่าการใช้ GNC ร่วมกัน (ที่ปรับแต่งสำหรับฟังก์ชัน Geman-McClure และฟังก์ชันกำลังสองน้อยที่สุดแบบตัดทอน) และความเป็นคู่ของ Black-Rangarajan สามารถนำไปสู่ตัวแก้ปัญหาอเนกประสงค์สำหรับปัญหาการลงทะเบียนที่ทนทาน รวมถึงการลงทะเบียนจุดเมฆและตาข่าย^{[ 35 ]}${\displaystyle 80\%}$

อัลกอริทึมการลงทะเบียนที่มีประสิทธิภาพที่กล่าวมาข้างต้นเกือบทั้งหมด (ยกเว้นอัลกอริทึม BnB ที่ใช้เวลาประมวลผลแบบเลขชี้กำลังในกรณีที่เลวร้ายที่สุด) ไม่มีข้อรับประกันประสิทธิภาพซึ่งหมายความว่าอัลกอริทึมเหล่านี้อาจให้ค่าประมาณที่ไม่ถูกต้องโดยสิ้นเชิงโดยไม่แจ้งให้ทราบล่วงหน้า ดังนั้น อัลกอริทึมเหล่านี้จึงไม่เหมาะสมสำหรับแอปพลิเคชันที่สำคัญต่อความปลอดภัย เช่น การขับขี่อัตโนมัติ

เมื่อไม่นานมานี้ Yang และคณะได้พัฒนาอัลกอริทึมการลงทะเบียนที่แข็งแกร่งที่ได้รับการรับรองเป็นครั้งแรก ซึ่งมีชื่อว่าTruncated least squares Estimation And SEmidefinite Relaxation (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)}$

ซีบี.7

ซึ่งได้มาจากการเลือกฟังก์ชันต้นทุนที่แข็งแกร่งของ TLS โดยที่เป็นค่าคงที่ที่กำหนดไว้ล่วงหน้าซึ่งกำหนดค่าความคลาดเคลื่อนสูงสุดที่อนุญาตให้พิจารณาว่าเป็นค่าภายใน ฟังก์ชันวัตถุประสงค์ของ TLS มีคุณสมบัติที่ว่าสำหรับการจับคู่ค่าภายใน ( ) จะใช้ค่าปรับกำลังสองน้อยที่สุดตามปกติ ในขณะที่สำหรับการจับคู่ค่าภายนอก ( ) จะไม่มีการใช้ค่าปรับและค่าภายนอกจะถูกทิ้งไป หากการเพิ่มประสิทธิภาพ TLS ( cb.7 ) ได้รับการแก้ไขจนได้ค่าเหมาะสมที่สุดทั่วโลก ก็จะเทียบเท่ากับการใช้วิธีของ Horn กับการจับคู่ค่าภายในเท่านั้น ${\displaystyle \rho (x)=\min(x^{2},{\bar {c}}^{2})}$${\displaystyle {\bar {c}}^{2}}$${\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 ) ค่อนข้างท้าทายเนื่องจากลักษณะเชิงการจัดเรียง TEASER แก้ปัญหา ( cb.7 ) ดังนี้: (i) สร้างการวัดที่ไม่เปลี่ยนแปลงเพื่อให้การประมาณค่ามาตราส่วน การหมุน และการแปลสามารถแยกออกจากกันและแก้ไขแยกกันได้ ซึ่งเป็นกลยุทธ์ที่ได้รับแรงบันดาลใจจากวิธีการของ Horn ดั้งเดิม (ii) ใช้การประมาณค่า TLS เดียวกันสำหรับปัญหาย่อยทั้งสาม โดยที่ปัญหา TLS ของมาตราส่วนสามารถแก้ไขได้อย่างแม่นยำโดยใช้อัลกอริทึมที่เรียกว่าการลงคะแนนแบบปรับตัว ปัญหา TLS ของการหมุนสามารถผ่อนคลายเป็นโปรแกรมกึ่งกำหนด (SDP) ซึ่งการผ่อนคลายนั้นแม่นยำในทางปฏิบัติ^{[ 8 ]}แม้จะมีค่าผิดปกติจำนวนมาก ปัญหา TLS ของการแปลสามารถแก้ไขได้โดยใช้การลงคะแนนแบบปรับตัวตามส่วนประกอบ การใช้งานที่รวดเร็วโดยใช้ GNC เปิดเผยเป็นโอเพนซอร์สที่นี่ในทางปฏิบัติ TEASER สามารถทนต่อการจับคู่ค่าผิดปกติได้มากกว่าและทำงานในเวลาไม่กี่มิลลิวินาที ${\displaystyle 99\%}$

นอกจากการพัฒนา TEASER แล้ว Yang et al.ยังพิสูจน์ได้ว่าภายใต้เงื่อนไขที่ไม่รุนแรงบางประการเกี่ยวกับข้อมูลจุดคลาวด์ การแปลงที่ประมาณการโดย TEASER มีข้อผิดพลาดที่จำกัดจากการแปลงความจริงพื้นฐาน^{[ 19 ]}

อั ลกอริทึม จุดที่ใกล้ที่สุดแบบวนซ้ำ (ICP) ได้รับการแนะนำโดย Besl และ McKay ^{[ 36 ]} อัลกอริทึมนี้ทำการลงทะเบียนแบบแข็งในลักษณะวนซ้ำโดยสลับกันใน (i) เมื่อกำหนดการแปลงแล้ว ให้หาจุดที่ใกล้ที่สุดในสำหรับทุกจุดในและ (ii) เมื่อกำหนดการจับคู่แล้ว ให้หาการแปลงแบบแข็งที่ดีที่สุดโดยการแก้ ปัญหา กำลังสองน้อยที่สุด ( cb.2 ) ดังนั้นจึงทำงานได้ดีที่สุดหากท่าทางเริ่มต้นของอยู่ใกล้กับ มากพอในรหัสเทียมอัลกอริทึมพื้นฐานจะถูกนำไปใช้ดังนี้: ${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {M}}}$${\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จะทำการ เพิ่มประสิทธิภาพ กำลังสองน้อยที่สุดเพื่อลดระยะห่างในแต่ละคู่ โดยใช้โซลูชันแบบปิดของ Horn ^{[ 16 ]}และ Arun ^{[ 17 ]}${\displaystyle \langle m_{i},{\hat {s}}_{i}\rangle }$

เนื่องจากฟังก์ชันต้นทุนของการลงทะเบียนขึ้นอยู่กับการค้นหาจุดที่ใกล้ที่สุดในกับทุกจุดในจึงสามารถเปลี่ยนแปลงได้ในขณะที่อัลกอริทึมกำลังทำงาน ดังนั้นจึงเป็นการยากที่จะพิสูจน์ว่า ICP จะลู่เข้าสู่ค่าเหมาะสมที่สุดเฉพาะที่อย่างแม่นยำ^{[ 37 ]}ในความเป็นจริง จากประสบการณ์ ICP และEM-ICPไม่ลู่เข้าสู่ค่าต่ำสุดเฉพาะที่ของฟังก์ชันต้นทุน^{[ 37 ]}อย่างไรก็ตาม เนื่องจาก ICP เข้าใจง่ายและนำไปใช้งานได้ง่าย จึงยังคงเป็นอัลกอริทึมการลงทะเบียนชุดจุดที่ใช้กันทั่วไปมากที่สุด^{[ 37 ]}มีการเสนอ ICP หลายรูปแบบ ซึ่งส่งผลกระทบต่อทุกขั้นตอนของอัลกอริทึม ตั้งแต่การเลือกและการจับคู่จุด ไปจนถึงกลยุทธ์การลดค่า^{[ 13 ] [ 38 ]} ตัวอย่างเช่น อัลกอริทึม การเพิ่มประสิทธิภาพความคาดหวังถูกนำไปใช้กับอัลกอริทึม ICP เพื่อสร้างวิธีการ EM-ICP และอัลกอริทึม Levenberg-Marquardtถูกนำไปใช้กับอัลกอริทึม ICP เพื่อสร้างวิธีการLM-ICP ^{[ 12 ]}${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {M}}}$

การจับคู่จุดที่แข็งแกร่ง (RPM) ได้รับการแนะนำโดย Gold et al. ^{[ 39 ]}วิธีนี้ดำเนินการลงทะเบียนโดยใช้การอบอ่อนเชิงกำหนดและการกำหนดการจับคู่แบบอ่อนระหว่างชุดจุด ในขณะที่ใน ICP การจับคู่ที่สร้างขึ้นโดยฮิวริสติกเพื่อนบ้านที่ใกล้ที่สุดเป็นแบบไบนารี RPM ใช้ การจับคู่ แบบอ่อนซึ่งการจับคู่ระหว่างจุดสองจุดใดๆ สามารถเป็นได้ตั้งแต่ 0 ถึง 1 แม้ว่าในที่สุดจะลู่เข้าสู่ 0 หรือ 1 การจับคู่ที่พบใน RPM จะเป็นแบบหนึ่งต่อหนึ่งเสมอ ซึ่งไม่เป็นเช่นนั้นเสมอไปใน ICP ^{[ 14 ]}ให้เป็นจุดที่ ในและเป็นจุดที่ ใน เมทริกซ์ การจับคู่ถูกกำหนดดังนี้: ${\displaystyle m_{i}}$${\displaystyle i}$${\displaystyle {\mathcal {M}}}$${\displaystyle s_{j}}$${\displaystyle j}$${\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}}}$

รอบต่อนาที 1

ปัญหาจึงถูกกำหนดดังนี้: กำหนดชุดจุดสองชุดและค้นหาการแปลงแบบ Affineและเมทริกซ์การจับคู่ที่เชื่อมโยงจุดทั้งสองได้ดีที่สุด^{[ 39 ]}การทราบการแปลงที่เหมาะสมที่สุดทำให้ง่ายต่อการกำหนดเมทริกซ์การจับคู่ และในทางกลับกัน อย่างไรก็ตาม อัลกอริทึม RPM จะกำหนดทั้งสองอย่างพร้อมกัน การแปลงอาจถูกแยกออกเป็นเวกเตอร์การแปลและเมทริกซ์การแปลง : ${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle T}$${\displaystyle \mathbf {\mu } }$

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

เมทริกซ์ใน 2 มิติประกอบด้วยพารามิเตอร์แยกกันสี่ตัวได้แก่ ขนาด การหมุน และส่วนประกอบการเฉือนในแนวตั้งและแนวนอนตามลำดับ ฟังก์ชันต้นทุนจึงเป็นดังนี้: ${\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

ภายใต้เงื่อนไข, , . เงื่อนไขนี้จะเอนเอียงเป้าหมายไปสู่ความสัมพันธ์ที่แข็งแกร่งขึ้นโดยการลดต้นทุนหากเมทริกซ์การจับคู่มีเลข 1 มากขึ้น ฟังก์ชันนี้ทำหน้าที่ปรับการแปลงเชิงเส้นแบบ Affine โดยลงโทษค่าขนาดใหญ่ของส่วนประกอบมาตราส่วนและแรงเฉือน: ${\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 }$${\displaystyle g(\mathbf {A} )}$

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

สำหรับ พารามิเตอร์การปรับค่าบางอย่าง${\displaystyle \gamma }$

วิธีการ RPM ปรับฟังก์ชันต้นทุนให้เหมาะสมที่สุดโดยใช้ อัลกอริธึม Softassignกรณี 1 มิติจะถูกนำมาแสดงที่นี่ กำหนดให้ชุดตัวแปรโดยที่ . ตัวแปรหนึ่งจะเชื่อมโยงกับแต่ละ ตัวแปร โดยที่. เป้าหมายคือการหาตัวแปร ที่ทำให้ มีค่าสูงสุด. สามารถกำหนดเป็นปัญหาต่อเนื่องได้โดยการแนะนำพารามิเตอร์ควบคุม. ใน วิธี การอบอ่อนแบบกำหนด (Deterministic Annealing ) พารามิเตอร์ควบคุมจะค่อยๆ เพิ่มขึ้นเมื่ออัลกอริธึมทำงาน ให้เป็น: ${\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

นี่คือสิ่งที่เรียกว่าฟังก์ชัน softmaxเมื่อเพิ่มขึ้น มันจะเข้าใกล้ค่าไบนารีตามที่ต้องการในสมการ ( rpm.1 ) ปัญหาสามารถขยายไปสู่กรณี 2 มิติได้แล้ว โดยแทนที่จะหาค่าสูงสุดของจะทำการหาค่าสูงสุดของสิ่งต่อไปนี้: ${\displaystyle \beta }$${\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}}}}$

นี่เป็นเรื่องตรงไปตรงมา ยกเว้นว่าตอนนี้ข้อจำกัดบนเป็น ข้อจำกัด เมทริกซ์สุ่มสองชั้น : และ. ดังนั้น ตัวส่วนจากสมการ ( rpm.3 ) จึงไม่สามารถแสดงสำหรับกรณี 2 มิติได้ง่ายๆ เพื่อให้เป็นไปตามข้อจำกัด สามารถใช้ผลลัพธ์ของ Sinkhorn ^{[ 39 ]} ซึ่งระบุว่าเมทริกซ์สุ่มสองชั้นได้มาจาก เมทริกซ์จัตุรัสใดๆที่มีค่าบวกทั้งหมดโดยกระบวนการวนซ้ำของการทำให้แถวและคอลัมน์เป็นมาตรฐานสลับกัน ดังนั้นอัลกอริทึมจึงเขียนได้ดังนี้: ^{[ 39 ]}${\displaystyle \mu }$${\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}=1}$${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}=1}$

อัลกอริทึม RPM2D ${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$t  := 0 a , θ b , c  := 0 β  := β 0 ในขณะที่β < β f : ในขณะที่μยังไม่บรรจบกัน:  // อัปเดตพารามิเตอร์การจับคู่โดย softassign // ใช้ Sinkhorn's method ในขณะที่ยังไม่บรรจบกัน: // อัปเดตโดยการทำให้เป็นมาตรฐานทั่วทุกแถว: // อัปเดตโดยการทำให้เป็นมาตรฐานทั่วทุกคอลัมน์: // อัปเดตพารามิเตอร์ท่าทางโดยการลดพิกัด อัปเดต θ โดย ใช้วิธีแก้ปัญหาเชิงวิเคราะห์${\displaystyle {\hat {\mu }}_{ij}:=1+\epsilon }$${\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โดยใช้วิธีของนิวตันส่งคืนค่าa, b, c, θและt${\displaystyle \beta :=\beta _{r}\beta }$${\displaystyle \gamma :={\frac {\gamma }{\beta _{r}}}}$

โดยที่พารามิเตอร์ควบคุมการอบชุบแบบกำหนดค่าเริ่มต้นจะถูกตั้งไว้ที่และเพิ่มขึ้นตามปัจจัยจนกระทั่งถึงค่าสูงสุดผลรวมในขั้นตอนการทำให้เป็นมาตรฐานจะรวมกันเป็นและแทนที่จะเป็นเพียงและเนื่องจากข้อจำกัดบนเป็นอสมการ ดังนั้น องค์ประกอบ ที่ และจึงเป็นตัวแปรส่วนเกิน ${\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}$

อัลกอริทึมยังสามารถขยายสำหรับชุดจุดใน 3 มิติหรือมิติที่สูงกว่าได้ ข้อจำกัดของเมทริกซ์การจับคู่จะเหมือนกันในกรณี 3 มิติเช่นเดียวกับในกรณี 2 มิติ ดังนั้นโครงสร้างของอัลกอริทึมจึงยังคงไม่เปลี่ยนแปลง โดยความแตกต่างหลักอยู่ที่วิธีการแก้เมทริกซ์การหมุนและการแปล^{[ 39 ]}${\displaystyle \mathbf {\mu } }$

อัลกอริทึมการจับคู่จุดที่แข็งแกร่งของสปลายแผ่นบาง (TPS-RPM) โดย Chui และ Rangarajan เสริมวิธีการ RPM เพื่อทำการลงทะเบียนแบบไม่แข็งตัวโดยการกำหนดพารามิเตอร์การแปลงเป็นสปลายแผ่นบาง^{[ 14 ]} อย่างไรก็ตาม เนื่องจากพารามิเตอร์สปลายแผ่นบางมีอยู่เฉพาะในสามมิติเท่านั้น วิธีนี้จึงไม่สามารถขยายไปยังปัญหาที่เกี่ยวข้องกับสี่มิติขึ้นไปได้

วิธีการหาความสัมพันธ์ของเคอร์เนล (KC) สำหรับการลงทะเบียนชุดจุดได้รับการแนะนำโดย Tsin และ Kanade ^{[ 37 ]} เมื่อเปรียบเทียบกับ ICP อัลกอริทึม KC มีความทนทานต่อข้อมูลที่มีสัญญาณรบกวนมากกว่า ต่างจาก ICP ที่สำหรับแต่ละจุดโมเดล จะพิจารณาเฉพาะจุดฉากที่ใกล้ที่สุดเท่านั้น แต่ในที่นี้ ทุกจุดฉากจะมีผลต่อทุกจุดโมเดล^{[ 37 ]}ด้วยเหตุนี้ นี่จึงเป็น อัลกอริทึมการลงทะเบียนแบบ เชื่อมโยงหลาย จุด สำหรับ ฟังก์ชันเคอร์เนล บางฟังก์ชัน ความสัมพันธ์ของเคอร์เนลระหว่างสองจุดจะถูกกำหนดดังนี้: ^{[ 37 ]}${\displaystyle K}$${\displaystyle KC}$${\displaystyle x_{i},x_{j}}$

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

เคซี.1

ฟังก์ชันเคอร์เนล ที่เลือกสำหรับการลงทะเบียนชุดจุดโดยทั่วไปจะเป็นเคอร์เนลสมมาตรและไม่เป็นลบ คล้ายกับที่ใช้ในการประมาณความหนาแน่นของหน้าต่าง Parzen โดยทั่วไปจะใช้ เคอร์เนลเกาส์เซียนเนื่องจากความเรียบง่าย แม้ว่าอาจใช้เคอร์เนลอื่นๆ เช่นเคอร์เนล Epanechnikovและเคอร์เนลไตรคิวบ์แทนได้^{[ 37 ]}ความสัมพันธ์ของเคอร์เนลของชุดจุดทั้งหมดถูกกำหนดให้เป็นผลรวมของความสัมพันธ์ของเคอร์เนลของทุกจุดในชุดกับทุกจุดอื่นๆ ในชุด: ^{[ 37 ]}${\displaystyle K}$${\displaystyle {\mathcal {\chi }}}$

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

เคซี.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 )}$

เคซี.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}$

เคซี.6

เมื่อกำหนดฟังก์ชันต้นทุน แล้ว อัลกอริทึมจะใช้การลดระดับความชันเพื่อค้นหาการแปลงที่เหมาะสมที่สุด การคำนวณฟังก์ชันต้นทุนตั้งแต่เริ่มต้นในทุกรอบนั้นมีค่าใช้จ่ายในการคำนวณสูง ดังนั้นจึงใช้ ฟังก์ชันต้นทุนแบบไม่ต่อเนื่องตามสมการ ( kc.6 ) การประมาณความหนาแน่นของเคอร์เนล สามารถประเมินได้ที่จุดกริดและจัดเก็บไว้ในตารางค้นหาซึ่งแตกต่างจาก ICP และวิธีการที่เกี่ยวข้อง ตรงที่ไม่จำเป็นต้องค้นหาเพื่อนบ้านที่ใกล้ที่สุด ซึ่งทำให้อัลกอริทึม KC มีความเรียบง่ายในการใช้งานมากกว่า ${\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}$

เมื่อเปรียบเทียบกับ ICP และ EM-ICP สำหรับชุดจุด 2 มิติและ 3 มิติที่มีสัญญาณรบกวน อัลกอริทึม KC มีความไวต่อสัญญาณรบกวนน้อยกว่าและส่งผลให้การลงทะเบียนถูกต้องบ่อยขึ้น^{[ 37 ]}

การประมาณความหนาแน่นของเคอร์เนลเป็นผลรวมของเกาส์เซียน ดังนั้นจึงสามารถแสดงเป็นแบบจำลองส่วนผสมเกาส์เซียน (GMM) ได้^{[ 40 ]} Jian และ Vemuri ใช้เวอร์ชัน GMM ของอัลกอริธึมการลงทะเบียน KC เพื่อทำการ ลง ทะเบียนแบบไม่แข็งตัวโดยใช้พารามิเตอร์สปลายแผ่นบาง

การเคลื่อนตัวของจุดที่สอดคล้องกัน (CPD) ได้รับการแนะนำโดย Myronenko และ Song ^{[ 13 ] [ 41 ]} อัลกอริทึมนี้ใช้แนวทางความน่าจะเป็นในการจัดเรียงชุดจุด คล้ายกับวิธี GMM KC แตกต่างจากแนวทางก่อนหน้านี้ในการลงทะเบียนแบบไม่แข็งตัวซึ่งใช้ แบบจำลองการแปลง สปลายแผ่นบาง CPD ไม่ขึ้นอยู่กับแบบจำลองการแปลงที่ใช้ ชุดจุดแสดงถึงจุดศูนย์กลางของแบบจำลองส่วนผสมเกาส์เซียน (GMM) เมื่อชุดจุดทั้งสองได้รับการจัดเรียงอย่างเหมาะสม การจับคู่จะเป็นค่าสูงสุดของ ความน่าจะเป็นภายหลังของ GMM สำหรับจุดข้อมูลที่กำหนด เพื่อรักษาโครงสร้างทางโทโพโลยีของชุดจุด จุดศูนย์กลางของ GMM จะถูกบังคับให้เคลื่อนที่อย่างสอดคล้องกันเป็นกลุ่ม อัลกอริทึม การเพิ่มประสิทธิภาพความคาดหวังถูกใช้เพื่อเพิ่มประสิทธิภาพฟังก์ชันต้นทุน^{[ 13 ]}${\displaystyle {\mathcal {M}}}$

ให้มี จุด Mจุดในและ จุด Nจุดในฟังก์ชันความหนาแน่นความน่าจะเป็น GMM สำหรับจุดsคือ: ${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$

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

กองที่ 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)}}$

ความน่าจะเป็นของการเป็นสมาชิกนั้นเท่ากันสำหรับส่วนประกอบ GMM ทั้งหมด น้ำหนักของการแจกแจงแบบเอกรูปจะถูกกำหนดโดย. ดังนั้นแบบจำลองผสมจึงเป็นดังนี้: ${\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)}$

กองที่ 2

จุดศูนย์กลางของ GMM จะถูกกำหนดพารามิเตอร์ใหม่ด้วยชุดพารามิเตอร์ที่ประมาณค่าโดยการเพิ่มค่าความน่าจะเป็นสูงสุด ซึ่งเทียบเท่ากับการลดค่าฟังก์ชันลอการิทึมความน่าจะเป็น เชิงลบให้เหลือน้อยที่สุด : ${\displaystyle \theta }$

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

กองที่ 3

โดยถือว่าข้อมูลเป็นอิสระต่อกันและมีการกระจายแบบเดียวกันความน่าจะเป็นของการจับคู่ระหว่างสองจุดและถูกกำหนดให้เป็นความน่าจะเป็นภายหลังของจุดศูนย์กลาง GMM เมื่อกำหนดจุดข้อมูล: ${\displaystyle m_{i}}$${\displaystyle s_{j}}$

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

อั ลกอริทึม Expectation Maximization (EM) ใช้ในการค้นหาค่าและอัลกอริทึม EM ประกอบด้วยสองขั้นตอน ขั้นแรก ในขั้นตอน E หรือ ขั้นตอน การประมาณค่า จะเดาค่าของพารามิเตอร์ ("ค่าพารามิเตอร์เก่า") จากนั้นใช้ทฤษฎีบทของเบย์สในการคำนวณการแจกแจงความน่าจะเป็นภายหลังของส่วนประกอบแบบผสม ขั้นที่สอง ในขั้นตอน M หรือ ขั้นตอนการหาค่า สูงสุดจะค้นหาค่าพารามิเตอร์ "ใหม่" โดยการลดค่าคาดหวังของฟังก์ชันลอการิทึมความน่าจะเป็นเชิงลบที่สมบูรณ์ นั่นคือ ฟังก์ชันต้นทุน: ${\displaystyle \theta }$${\displaystyle \sigma ^{2}}$${\displaystyle P^{\text{old}}(i,s_{j})}$

${\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))}$

กองที่ 4

หากไม่พิจารณาค่าคงที่ที่ไม่ขึ้นกับและสมการ ( cpd.4 ) สามารถแสดงได้ดังนี้: ${\displaystyle \theta }$${\displaystyle \sigma }$

${\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}}}$

กองที่ 5

ที่ไหน

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

โดยที่. ความน่าจะเป็นภายหลังของส่วนประกอบ GMM ที่คำนวณโดยใช้ค่าพารามิเตอร์ก่อนหน้าคือ: ${\displaystyle N=N_{\mathbf {P} }}$${\displaystyle w=0}$${\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}}}}}$

กองที่ 6

การลดฟังก์ชันต้นทุนในสมการ ( cpd.5 ) จะทำให้ฟังก์ชันลอการิทึมความน่าจะเป็นเชิงลบEในสมการ ( cpd.3 ) ลดลงอย่างแน่นอน เว้นแต่ว่ามันจะอยู่ที่ค่าต่ำสุดเฉพาะที่อยู่แล้ว^{[ 13 ]}ดังนั้น อัลกอริทึมสามารถแสดงได้โดยใช้รหัสเทียมต่อไปนี้ โดยที่เซตจุดและถูกแทนด้วยเมทริกซ์และตามลำดับ: ^{[ 13 ]}${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle M\times D}$${\displaystyle N\times D}$${\displaystyle \mathbf {M} }$${\displaystyle \mathbf {S} }$

อัลกอริทึม CPD ${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$θ  := θ 0เริ่มต้น 0 ≤ w ≤ 1 ในขณะที่ยังไม่ได้ลงทะเบียน:  // ขั้นตอน E คำนวณPสำหรับi ∊ [1, M ] และj ∊ [1, N ]: // ขั้นตอน M แก้ปัญหาการแปลงที่เหมาะสมที่สุด{ θ , σ 2 } := solve ( S , M , P ) ส่งคืนθ${\displaystyle \sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}}$${\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}}}}}$

โดยที่เวกเตอร์เป็นเวกเตอร์คอลัมน์ที่มีค่าเป็นหนึ่งทั้งหมดฟังก์ชันจะแตกต่างกันไปตามประเภทของการลงทะเบียนที่ดำเนินการ ตัวอย่างเช่น ในการลงทะเบียนแบบแข็ง (rigid registration) ผลลัพธ์ที่ได้คือมาตราส่วนaเมทริกซ์การหมุนและเวกเตอร์การแปลพารามิเตอร์สามารถเขียนได้ในรูปของทูเปิลของค่าเหล่านี้: ${\displaystyle \mathbf {1} }$solve${\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สำหรับการลงทะเบียนแบบแข็งสามารถเขียนได้ดังต่อไปนี้ โดยมีการอธิบายการหาพีชคณิตในบทความของ Myronenko ในปี 2010 ^{[ 13 ]}

solve_rigid ( S , M , P ) N P  := 1 T P1 U , V  := svd ( A ) // การแยกส่วนค่าเอกลักษณ์ของA = UΣV T C  := diag(1, …, 1, det( UV T )) // diag( ξ )คือเมทริกซ์แนวทแยงที่สร้างจากเวกเตอร์ ξ R  := UCV T // tr คือร่องรอยของเมทริกซ์t  := μ s − a R μ m return { a , R , t }, σ 2${\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} }}}$${\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} }}} )}}}$${\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} ))}$

สำหรับการลงทะเบียนแบบแอฟฟิน ซึ่งเป้าหมายคือการหาการแปลงแบบแอฟฟินแทนที่จะเป็นการแปลงแบบแข็ง ผลลัพธ์ที่ได้คือเมทริกซ์การแปลงแบบแอฟฟินและการเลื่อนตำแหน่งเพื่อให้ชุดจุดที่จัดเรียงแล้วเป็นดังนี้: ${\displaystyle \mathbf {B} }$${\displaystyle \mathbf {t} }$

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

ฟังก์ชันsolve_affineสำหรับการลงทะเบียนแบบแข็งสามารถเขียนได้ดังต่อไปนี้ โดยมีการอธิบายการหาพีชคณิตในบทความของ Myronenko ในปี 2010 ^{[ 13 ]}

solve_affine ( S , M , P ) N P  := 1 T P1 t  := μ s − B μ m return { B , t }, σ 2${\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}}$${\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}))}$

นอกจากนี้ยังสามารถใช้ CPD กับการลงทะเบียนแบบไม่แข็งตัวโดยใช้การกำหนดพารามิเตอร์ที่ได้มาจากแคลคูลัสของการแปรผันได้ อีกด้วย ^{[ 13 ]}

ผลรวมของการกระจายแบบเกาส์เซียนสามารถคำนวณได้ในเวลาเชิงเส้นโดยใช้การแปลงเกาส์แบบเร็ว (FGT) ^{[ 13 ]}ด้วยเหตุนี้ความซับซ้อนของเวลาของ CPD จึงเป็นซึ่งเร็วกว่าวิธีการ อื่นๆ มากในเชิงอะซิมโทติก ^{[ 13 ]}${\displaystyle O(M+N)}$${\displaystyle O(MN)}$

รูปแบบหนึ่งของการเคลื่อนตัวของจุดที่สอดคล้องกัน เรียกว่า การเคลื่อนตัวของจุดที่สอดคล้องกันแบบเบย์เซียน (BCPD) ได้มาจากการกำหนดสูตรแบบเบย์เซียนของการลงทะเบียนชุดจุด ^{[ 42 ]} BCPD มีข้อดีหลายประการเหนือ CPD เช่น (1) การลงทะเบียนแบบไม่แข็งตัวและแบบแข็งตัวสามารถทำได้ในอัลกอริทึมเดียว (2) อัลกอริทึมสามารถเร่งความเร็วได้โดยไม่คำนึงถึงความเป็นเกาส์เซียนของเมทริกซ์แกรมเพื่อกำหนดความสอดคล้องของการเคลื่อนไหว (3) อัลกอริทึมมีความทนทานต่อค่าผิดปกติมากขึ้นเนื่องจากคำจำกัดความที่สมเหตุสมผลมากขึ้นของการกระจายค่าผิดปกติ นอกจากนี้ ในการกำหนดสูตรแบบเบย์เซียน ความสอดคล้องของการเคลื่อนไหวได้รับการแนะนำผ่านการกระจายก่อนหน้าของเวกเตอร์การกระจัด ซึ่งให้ความแตกต่างที่ชัดเจนระหว่างพารามิเตอร์การปรับแต่งที่ควบคุมความสอดคล้องของการเคลื่อนไหว BCPD ได้รับการเร่งความเร็วเพิ่มเติมโดยวิธีที่เรียกว่า BCPD++ ซึ่งเป็นขั้นตอนสามขั้นตอนประกอบด้วย (1) การสุ่มตัวอย่างชุดจุด (2) การลงทะเบียนชุดจุดที่สุ่มตัวอย่างลดลง และ (3) การประมาณค่าสนามการเปลี่ยนรูป ^{[ 43 ]} วิธีนี้สามารถลงทะเบียนชุดจุดที่ประกอบด้วยจุดมากกว่า 10 ล้านจุดในขณะที่ยังคงรักษาความแม่นยำในการลงทะเบียน

รูปแบบหนึ่งของการเคลื่อนจุดที่สอดคล้องกันเรียกว่า CPD ที่มีเรขาคณิตพื้นผิวท้องถิ่น (LSG-CPD) สำหรับการลงทะเบียนจุดคลาวด์แบบแข็ง^{[ 44 ]}วิธีการนี้จะเพิ่มการลงโทษจุดต่อระนาบในระดับต่างๆ เข้ากับการลงโทษจุดต่อจุดตามความเรียบของพื้นผิวท้องถิ่น ส่งผลให้ส่วนประกอบ GMM มีความแปรปรวนร่วมแบบไม่สมมาตร แทนที่จะเป็นความแปรปรวนร่วมแบบสมมาตรใน CPD ดั้งเดิม^{[ 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 ในชุดเป้าหมายคือเวกเตอร์ปกติที่สอดคล้องกับจุดเดียวกันคือเมทริกซ์เอกลักษณ์ ทำหน้าที่เป็นตัวควบคุม ดึงปัญหาออกจากภาวะไม่เสถียรคือสัมประสิทธิ์การลงโทษ (ฟังก์ชันซิกมอยด์ที่ดัดแปลง) ซึ่งตั้งค่าแบบปรับได้เพื่อเพิ่มระดับการลงโทษจุดต่อระนาบที่แตกต่างกันขึ้นอยู่กับความเรียบของพื้นผิวท้องถิ่น สิ่งนี้เกิดขึ้นได้จากการประเมินความแปรผันของพื้นผิว^{[ 45 ]}ภายในบริเวณใกล้เคียงของจุดเป้าหมายที่ m คือขอบเขตบนของการลงโทษ ${\displaystyle \mathbf {n} _{m}}$${\displaystyle \mathbf {I} }$${\displaystyle \alpha _{m}}$${\displaystyle \kappa _{m}}$${\displaystyle \alpha _{max}}$

การลงทะเบียนจุดคลาวด์ถูกกำหนดให้เป็นปัญหาการประมาณค่าความน่าจะเป็นสูงสุด (MLE) และแก้ไขด้วยอัลกอริธึม Expectation-Maximization (EM) ในขั้นตอน E การคำนวณการจับคู่จะถูกแปลงเป็นการจัดการเมทริกซ์แบบง่ายและคำนวณได้อย่างมีประสิทธิภาพบน GPU ในขั้นตอน M การเพิ่มประสิทธิภาพแบบไม่มีข้อจำกัดบนกลุ่ม Lie ของเมทริกซ์ได้รับการออกแบบมาเพื่ออัปเดตการแปลงแบบแข็งของการลงทะเบียนอย่างมีประสิทธิภาพ การใช้ประโยชน์จากความแปรปรวนร่วมทางเรขาคณิตในท้องถิ่น วิธีการนี้แสดงให้เห็นถึงประสิทธิภาพที่เหนือกว่าในด้านความแม่นยำและความทนทานต่อสัญญาณรบกวนและค่าผิดปกติ เมื่อเทียบกับ CPD พื้นฐาน^{[ 46 ]}คาดว่าจะได้ประสิทธิภาพการทำงานที่ดีขึ้นเนื่องจากการคำนวณการจับคู่ที่เร่งความเร็วด้วย GPU การใช้งาน LSG-CPD เป็นแบบโอเพนซอร์สที่นี่

อัลกอริทึมนี้ได้รับการแนะนำในปี 2013 โดย H. Assalih เพื่อรองรับการลงทะเบียนภาพโซนาร์^{[ 47 ]}ภาพประเภทนี้มักมีสัญญาณรบกวนสูง ดังนั้นจึงคาดว่าจะมีจุดผิดปกติจำนวนมากในชุดจุดที่จะจับคู่ SCS มีความทนทานสูงต่อจุดผิดปกติและสามารถเหนือกว่าประสิทธิภาพของ ICP และ CPD ในกรณีที่มีจุดผิดปกติ SCS ไม่ใช้การเพิ่มประสิทธิภาพแบบวนซ้ำในพื้นที่มิติสูง และไม่ใช่ทั้งแบบความน่าจะเป็นหรือแบบสเปกตรัม SCS สามารถจับคู่การแปลงแบบแข็งและไม่แข็งได้ และทำงานได้ดีที่สุดเมื่อการแปลงเป้าหมายอยู่ระหว่างสามถึงหกองศา อิสระ

• การจับคู่คุณลักษณะจุด
• การสร้างสามเหลี่ยมโดยใช้ชุดจุด
• การแปลงการแจกแจงปกติ

วิกิมีเดียคอมมอน ส์มีสื่อที่เกี่ยวข้องกับการลงทะเบียนชุดคะแนน

• การใช้งานอ้างอิงของการจับคู่จุดที่แข็งแกร่งของเส้นโค้งแผ่นบาง
• การใช้งานอ้างอิงของการลงทะเบียนชุดจุดสหสัมพันธ์เคอร์เนล
• การใช้งานอ้างอิงของการเคลื่อนตัวของจุดที่สอดคล้องกัน
• การนำ ICP เวอร์ชันต่างๆ ไปใช้เป็นข้อมูลอ้างอิง
• การใช้งานอ้างอิงของการเคลื่อนตัวของจุดที่สอดคล้องกันแบบเบย์เซียน
• ตัวอย่างการใช้งาน LSG-CPD