点群登録

2 つの点群が与えられた場合、剛体位置合わせは、一方の点群を他方の点群にマッピングする剛体変換を生成します。剛体変換は、2 つの点間の距離を変更しない変換として定義されます。通常、このような変換は、平行移動と回転で構成されます。^{[ 12 ]}まれに、点群がミラーリングされる場合もあります。ロボット工学とコンピュータビジョンでは、剛体位置合わせが最も多くの用途があります。

2 つの点群が与えられた場合、非剛体レジストレーションは、一方の点群を他方の点群にマッピングする非剛体変換を生成します。非剛体変換には、スケーリングやせん断マッピングなどのアフィン変換が含まれます。ただし、点群レジストレーションのコンテキストでは、非剛体レジストレーションは通常、非線形変換を伴います。点群の変動の固有モードがわかっている場合、非線形変換は固有値によってパラメータ化できます。^{[ 13 ]}非線形変換は、薄板スプラインとしてパラメータ化することもできます。^{[ 14 ] [ 13 ]}

点群レジストレーションのアプローチの中には、より一般的なグラフマッチング問題を解決するアルゴリズムを使用するものがあります。^{[ 11 ]}しかし、このような方法の計算複雑度は高くなる傾向があり、剛体レジストレーションに限定されます。この記事では、変換が3D回転と並進（場合によっては均一スケーリングも含む）を含むと想定される剛体レジストレーションのアルゴリズムのみを検討します。

PCL （Point Cloud Library）は、n次元点群と3Dジオメトリ処理のためのオープンソースフレームワークです。これにはいくつかの点位置合わせアルゴリズムが含まれています。^{[ 15 ]}

最も単純なケースでは、すべての対応関係が正しいと仮定できます。つまり、点が${\displaystyle m_{i},s_{i}\in \mathbb {R} ^{3}}$以下のように生成されます。

どこ${\displaystyle l>0}$は均一なスケーリング係数です（多くの場合）${\displaystyle l=1}$（仮定）${\displaystyle R\in {\text{SO}}(3)}$は適切な 3D回転行列です(${\displaystyle {\text{SO}}(d)}$は次数 の特別な直交群です${\displaystyle d}$)${\displaystyle t\in \mathbb {R} ^{3}}$は3D変換ベクトルであり、${\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})}$すると、未知のスケール、回転、並進に対する最尤推定値を得るために、以下の最適化を行うことが示される。

スケーリング係数が 1 で並進ベクトルがゼロの場合、最適化によってWahba 問題の定式化が再現されることに注意してください。集合の非凸性により最適化 ( cb.2 ) は非凸性になりますが、${\displaystyle {\text{SO}}(3)}$ベルトルト・KP・ホーンによる先駆的な研究は、スケール、回転、並進の推定を分離することで、 ( cb.2 )が実際に閉形式解を持つことを示した。^{[ 16 ]}同様の結果はアルンらによって発見された。^{[ 17 ]}さらに、一意の変換を見つけるために${\displaystyle (l,R,t)}$、 少なくとも${\displaystyle N=3}$各点集合には、共線でない点が必要である。

さらに最近では、ブリアレスとゴンザレス＝ヒメネスは、モデルセットの場合にラグランジュ双対性を用いた半正定値緩和法を開発した。${\displaystyle {\mathcal {M}}}$点、線、平面などのさまざまな 3D プリミティブが含まれています (モデルが${\displaystyle {\mathcal {M}}}$は 3D メッシュです。^{[ 18 ]}興味深いことに、半正定値緩和は経験的にタイトであり、つまり、半正定値緩和の解から、確実にグローバルに最適な解を抽出できます。

最小二乗法（cb.2 ）は、外れ値が存在する場合に極めて悪い結果を示すことが知られている。外れ値対応とは、一対の測定値のことである。${\displaystyle s_{i}\leftrightarrow m_{i}}$これは生成モデル（cb.1 ）から逸脱する。この場合、次のような別の生成モデルを考えることができる。^{[ 19 ]}

もし${\displaystyle i-}$thペア${\displaystyle s_{i}\leftrightarrow m_{i}}$がインライアである場合、それはアウトライアフリーモデル（cb.1）に従います。つまり、${\displaystyle s_{i}}$から得られる${\displaystyle m_{i}}$空間変換と若干のノイズによって、${\displaystyle i-}$thペア${\displaystyle s_{i}\leftrightarrow m_{i}}$外れ値である場合、${\displaystyle s_{i}}$任意のベクトルにすることができます${\displaystyle o_{i}}$どの対応関係が外れ値であるかを事前に知ることができないため、生成モデル（cb.3）に基づくロバストな位置合わせは、現実世界に展開されるコンピュータビジョンやロボット工学にとって極めて重要です。なぜなら、現在の特徴マッチング技術は、非常に破損した対応関係を出力する傾向があるからです。${\displaystyle 95\%}$対応関係の中には外れ値が含まれている可能性がある。^{[ 20 ]}

次に、堅牢な位置合わせのためのいくつかの一般的なパラダイムについて説明します。

反復最近点（ICP）アルゴリズムは、BeslとMcKayによって導入されました。^{[ 36 ]}このアルゴリズムは、(i)変換が与えられたときに、最も近い点を見つけるという 手順を交互に繰り返すことで、反復的に剛体位置合わせを実行します。${\displaystyle {\mathcal {S}}}$すべてのポイントにおいて${\displaystyle {\mathcal {M}}}$（ii）対応関係が与えられた場合、最小二乗問題を解くことによって最適な剛体変換を見つける（cb.2）。したがって、初期姿勢が${\displaystyle {\mathcal {M}}}$十分に近い${\displaystyle {\mathcal {S}}}$擬似コードでは、基本アルゴリズムは次のように実装されます。

アルゴリズムICP( M , S ) θ := θ 0 while not registered: X := ∅ for m i ∊ T ( M , θ ): ŝ i := S内でm iに最も近い点X := X + ⟨ m i , ŝ i ⟩ θ := least_squares( X ) return θ

ここでは、関数は最小二乗least_squares最適化を実行して、各距離を最小化します。${\displaystyle \langle m_{i},{\hat {s}}_{i}\rangle }$^{Horn [ 16 ]}と Arun ^{[ 17 ]}による閉形式解を使用してペアを作成します。

登録のコスト関数は最も近い点を見つけることに依存するため${\displaystyle {\mathcal {S}}}$あらゆる点で${\displaystyle {\mathcal {M}}}$アルゴリズムの実行中に変化する可能性があります。そのため、ICP が実際に局所最適解に正確に収束することを証明するのは困難です。^{[ 37 ]}実際、経験的に、ICP とEM-ICP はコスト関数の局所最小値に収束しません。^{[ 37 ]}それにもかかわらず、ICP は直感的に理解でき、実装が簡単なので、最も一般的に使用されている点群レジストレーション アルゴリズムのままです。^{[ 37 ]}点の選択とマッチングから最小化戦略まで、アルゴリズムのすべてのフェーズに影響を与える ICP の多くのバリアントが提案されています。^{[ 13 ] [ 38 ]} 例えば、期待値最大化アルゴリズムが ICP アルゴリズムに適用されて EM-ICP 法が形成され、レーベンバーグ・マルカート アルゴリズムがICP アルゴリズムに適用されてLM-ICP法が形成されます。^{[ 12 ]}

ロバスト点マッチング（RPM）はGoldらによって導入されました^{[ 39 ]} 。この手法は、決定論的アニーリングと点群間の対応関係のソフト割り当てを用いて位置合わせを行います。ICPでは最近傍ヒューリスティックによって生成される対応関係はバイナリですが、RPMではソフト対応関係が用いられ、任意の2点間の対応関係は0から1までの範囲をとりますが、最終的には0または1に収束します。RPMで見つかる対応関係は常に1対1ですが、ICPでは必ずしもそうではありません[ ^{14 ] 。}${\displaystyle m_{i}}$になる${\displaystyle i}$の時点${\displaystyle {\mathcal {M}}}$そして${\displaystyle s_{j}}$になる${\displaystyle j}$の時点${\displaystyle {\mathcal {S}}}$マッチマトリックス${\displaystyle \mathbf {\mu } }$次のように定義される。

問題は次のように定義されます。2つの点集合が与えられた場合${\displaystyle {\mathcal {M}}}$そして${\displaystyle {\mathcal {S}}}$アフィン変換を見つける${\displaystyle T}$マッチマトリックス${\displaystyle \mathbf {\mu } }$それらを最もよく関連付けるもの。^{[ 39 ]}最適な変換が分かれば、マッチ行列を簡単に決定でき、その逆もまた然りです。ただし、RPMアルゴリズムは両方を同時に決定します。変換は、並進ベクトルと変換行列に分解できます。

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

マトリックス${\displaystyle \mathbf {A} }$2Dでは、4つの独立したパラメータで構成されています。${\displaystyle \lbrace a,\theta ,b,c\rbrace }$これらはそれぞれ、スケール、回転、垂直および水平せん断成分である。コスト関数は次のようになる。

対象${\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アルゴリズムを用いてコスト関数を最適化します。ここでは1次元の場合を導出します。変数セットが与えられた場合${\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 \beta }$が増加すると、式（ rpm.1 ）で示したようにバイナリ値に近づきます。この問題は、2D の場合に一般化できます。2D の場合では、最大化する代わりに、${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}$以下が最大化されます。

どこ

${\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 )の分母は2D の場合、単純に表現することはできません。制約を満たすために、Sinkhorn による結果^{[ 39 ]}を使用できます。この結果によると、行と列の正規化を交互に繰り返す反復プロセスにより、すべての要素が正である任意の正方行列から二重確率行列が得られます。したがって、アルゴリズムは次のように記述されます。^{[ 39 ]}

アルゴリズム RPM2D${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$t := 0 a、θ b、c := 0 β := β 0${\displaystyle {\hat {\mu }}_{ij}:=1+\epsilon }$while β < β f : while μが収束していない間:  // ソフトアサインメントによって対応パラメータを更新する${\displaystyle Q_{ij}:=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}$${\displaystyle \mu _{ij}^{0}:=\exp(\beta Q_{ij})}$// Sinkhorn の方法を適用します${\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}$th と${\displaystyle N+1}$th 要素はスラック変数です。

このアルゴリズムは、3D以上の次元の点群にも拡張できます。対応行列の制約${\displaystyle \mathbf {\mu } }$3D の場合も 2D の場合も同じです。したがって、アルゴリズムの構造は変わりませんが、主な違いは回転行列と並進行列の解き方です。^{[ 39 ]}

薄板スプラインの堅牢な点マッチング

ChuiとRangarajanによる薄板スプラインロバストポイントマッチング（TPS-RPM）アルゴリズムは、変換を薄板スプラインとしてパラメータ化することで、RPM法を拡張して非剛体レジストレーションを実行します。^{[ 14 ]} しかし、薄板スプラインのパラメータ化は3次元にしか存在しないため、この方法は4次元以上の問題には拡張できません。

点群レジストレーションのカーネル相関（KC）アプローチは、TsinとKanadeによって導入されました。^{[ 37 ]} ICPと比較して、KCアルゴリズムはノイズデータに対してよりロバストです。ICPでは、各モデル点に対して最も近いシーン点のみが考慮されますが、ここではすべてのシーン点がすべてのモデル点に影響を与えます。^{[ 37 ]}そのため、これは多重リンクレジストレーションアルゴリズムです。あるカーネル関数に対して${\displaystyle K}$カーネル相関${\displaystyle KC}$2つのポイント${\displaystyle x_{i},x_{j}}$は次のように定義される：^{[ 37 ]}

カーネル関数${\displaystyle K}$点群レジストレーションに選択されるカーネルは、通常、パーゼン窓密度推定で使用されるものと同様の、対称かつ非負のカーネルです。ガウスカーネルは、その単純さから一般的に使用されますが、エパネチニコフカーネルやトライキューブカーネルなどの他のカーネルに置き換えることもできます。 ^{[ 37 ]}点群全体のカーネル相関${\displaystyle {\mathcal {\chi }}}$は、セット内のすべての点とセット内の他のすべての点との間のカーネル相関の合計として定義されます。^{[ 37 ]}

点群のKCの対数は、定数係数の範囲内で情報エントロピーに比例します。KCは点群の「コンパクトさ」の尺度であることに注意してください。当然ながら、点群内のすべての点が同じ位置にある場合、KCは大きな値になります。ある変換パラメータに対する点群位置合わせアルゴリズムのコスト関数${\displaystyle \theta }$は次のように定義される。

いくつかの代数操作により、次の結果が得られます。

この式は、次の点に注目することで簡略化される。${\displaystyle KC({\mathcal {S}})}$独立している${\displaystyle \theta }$さらに、固定位置合わせを仮定すると、${\displaystyle KC(T({\mathcal {M}},\theta ))}$不変な場合${\displaystyle \theta }$剛体変換の下では、すべての点のペア間のユークリッド距離は変化しないため、上記の式は次のように書き換えることができます。

カーネル密度推定値は次のように定義されます。

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

すると、コスト関数は2つのカーネル密度推定値の相関として表されることが示される。

コスト関数を確立したら、アルゴリズムは勾配降下法を使用して最適な変換を見つけます。コスト関数を各反復でゼロから計算するのは計算コストが高いため、コスト関数の離散バージョン（kc.6）が使用されます。カーネル密度推定${\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}$グリッドポイントで評価し、ルックアップテーブルに格納することができます。ICPや関連手法とは異なり、最近傍点を見つける必要がないため、KCアルゴリズムは実装が比較的簡単です。

ノイズの多い2Dおよび3D点群に対するICPおよびEM-ICPと比較して、KCアルゴリズムはノイズに対する感度が低く、より頻繁に正しい位置合わせを実現します。^{[ 37 ]}

コヒーレントポイントドリフト（CPD）は、MyronenkoとSongによって導入されました。^{[ 13 ] [ 41 ]}このアルゴリズムは、GMM KC法と同様に、点群の位置合わせに確率的なアプローチを採用しています。薄板スプライン変換モデル を仮定する従来の非剛体位置合わせのアプローチとは異なり、CPDは使用される変換モデルに依存しません。点群${\displaystyle {\mathcal {M}}}$はガウス混合モデル（GMM）の重心を表します。2 つの点群が最適に整列すると、対応関係は、与えられたデータ点に対する GMM事後確率の最大値になります。点群のトポロジー構造を維持するために、GMM の重心はグループとして一貫して移動するように強制されます。期待値最大化アルゴリズムを使用してコスト関数を最適化します。^{[ 13 ]}

M個の点があるとします。${\displaystyle {\mathcal {M}}}$そしてN個の点${\displaystyle {\mathcal {S}}}$点sに対するGMM確率密度関数は次のとおりです。

ここで、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}}}$すべてのGMMコンポーネントで等しい。一様分布の重みは次のように表される。${\displaystyle w\in [0,1]}$混合モデルは次のようになります。

GMMの重心は、一連のパラメータによって再パラメータ化される。${\displaystyle \theta }$尤度を最大化することによって推定される。これは負の対数尤度関数を最小化することと同等である。

データは独立かつ同一の分布に従うと仮定する。2点間の対応確率${\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アルゴリズムは2つのステップから構成されます。まず、Eステップ（推定ステップ）では、パラメータの値（「古い」パラメータ値）を推測し、次にベイズの定理を使用して事後確率分布を計算します。${\displaystyle P^{\text{old}}(i,s_{j})}$混合成分の。次に、Mステップまたは最大化ステップでは、完全な負の対数尤度関数、すなわちコスト関数の期待値を最小化することによって、「新しい」パラメータ値が求められる。

定数を無視して${\displaystyle \theta }$そして${\displaystyle \sigma }$式（cpd.4）は次のように表すことができます。

どこ

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

式（ cpd.5 ）のコスト関数を最小化すると、式（cpd.3 ）の負の対数尤度関数Eは、既に局所最小値に達していない限り、必然的に減少します。^{[ 13 ]}したがって、このアルゴリズムは、点集合が以下の擬似コードで表現できます。${\displaystyle {\mathcal {M}}}$そして${\displaystyle {\mathcal {S}}}$は次のように表されます${\displaystyle M\times D}$そして${\displaystyle N\times D}$行列${\displaystyle \mathbf {M} }$そして${\displaystyle \mathbf {S} }$それぞれ: ^{[ 13 ]}

アルゴリズム CPD${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$θ := θ 0初期化 0 ≤ w ≤ 1${\displaystyle \sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}}$登録されていない間: // Eステップ、i ∊ [1, M ] およびj ∊ [1, N ]に対してPを計算する:${\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} }$は、1 の列ベクトルです。このsolve関数は、実行されるレジストレーションの種類によって異なります。たとえば、剛体レジストレーションでは、出力はスケールaと回転行列です。${\displaystyle \mathbf {R} }$、および並進ベクトル${\displaystyle \mathbf {t} }$パラメータ${\displaystyle \theta }$これらは、以下の要素のタプルとして記述できます。

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

これは、1、単位行列、およびゼロの列ベクトルで初期化されます。

${\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${\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ΣV T C := diag(1, …, 1, det( UV T )) // diag( ξ )はベクトル ξ から形成される対角行列ですR := UCV T${\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} ))}$return { 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次のように記述でき、代数の導出はMyronenkoの2010年の論文で説明されている。^{[ 13 ]}

solve_affine ( 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 ]}

このアルゴリズムは、ソナー画像レジストレーションに対応するために、2013 年に H. Assalih によって導入されました。^{[ 47 ]}これらのタイプの画像はノイズが多い傾向があるため、マッチングする点群に多くの外れ値が存在することが予想されます。SCS は外れ値に対して高い堅牢性を提供し、外れ値が存在する場合、ICP および CPD のパフォーマンスを上回ることができます。SCS は高次元空間での反復最適化を使用せず、確率的でもスペクトル的でもありません。SCS は剛体変換と非剛体変換をマッチングでき、ターゲット変換の自由度が 3 ～ 6 の場合に最高のパフォーマンスを発揮します。