포인트 세트 등록

컴퓨터 비전, 패턴 인식 및 로봇 공학에서 포인트 세트 등록은 포인트 클라우드 등록 또는 스캔 매칭이라고도 하며 두 포인트 클라우드를 정렬하는 공간 변환(예: 스케일링, 회전 및 변환)을 찾는 프로세스입니다.이러한 변환을 찾는 목적에는 여러 데이터 세트를 전체적으로 일관된 모델(또는 좌표 프레임)에 병합하고, 새로운 측정을 알려진 데이터 세트에 매핑하여 특징을 식별하거나 그 자세를 추정하는 것이 포함됩니다.Raw 3D Point Cloud 데이터는 일반적으로 Lidars 및 RGB-D 카메라에서 얻을 수 있으며, 3D Point Cloud는 삼각 측량, 번들 조정, 최근에는 딥 러닝을 이용한 단안 영상 깊이 추정 등의 컴퓨터 비전 알고리즘에서도 생성할 수 있습니다.화상 처리 및 특징 베이스 화상 등록에 사용되는 2D 포인트 세트 등록의 경우, 점 세트는, 예를 들면 코너 검출등의 화상으로부터 특징 추출에 의해서 얻을 수 있는 2D 픽셀 좌표가 되어도 좋다.포인트 클라우드 등록은 자율 주행,^[1] 모션 추정 및 3D 재구성,^[2] 물체 감지 및 포즈 추정,^[3][4] 로봇 조작,^[5] 동시 위치 및 매핑(SLAM),^[6][7] 파노라마 스티치,^[8] 가상 및 증강 현실,^[9] 의료 ^[10]영상 촬영 등에 광범위하게 적용되고 있습니다.

특별한 경우로, 3D 회전만으로 다른 두 점 세트의 등록(즉, 스케일링과 변환이 없음)을 Wahba 문제라고 하며 직교 프로크러스트 문제와도 관련이 있습니다.

공식화

이 문제의 개요는 다음과 같습니다.^[11]$\{{\displaystyle }$ ${\displaystyle M}$、 ${\displaystyle S\mathcal{}}$ $}$ { $displaystyle$\$lbrace${$M$} , { \ $mathcal$$${ $S$$$} \ $rbrace$$}$g$$ 、 M$$（ $displaystyle$ M$$$$） 、 $N{\displaystyle }$ （ \$$displaystyle$$NE ） $の{\displaystyle }$ g,g,g g,g,ggggg,gg ,gg,g,g gg,,gggggggg,g,g gg,ggggg ggggggggg,,${\displaystyle {}^{}}$, R$$displaysty$$ 는 M$(\displaystyle$ {$M$$})$ $및$ S(\$displaystyle${S$})$가 3D 포인트 세트일 $때$의 일반적인 케이스를 복구합니다.문제는 이동$$"$모델$" 점 $집합{\displaystyle \mathcal{}}$M({displaystyle ${$M$})$에 적용할$$ 변환(일반적으로 점 단위 유클리드 거리로 정의됨)을 찾는 것입니다. M$({displaystyle$ {$M$$})$과 정적 "씬(scene$)"$ 집합 S$(\$ 사이의$$ $차이{\displaystyle \mathcal{}}$(일반적으로 점 단위 유클리드 거리로 정의됨)최소화.즉, 변환된 "모델" 세트와 "씬" 세트 간에 최적의 정렬을 얻을 수 있도록 ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$d \ $displaystyle$\ $mathbb${$R$$$} ^ {$d}$ $으로의$ $매핑$이 바람직하다.매핑은 강성 변환 또는 비강성 변환으로 구성될 수 있습니다.변환 모델은 T$${\$displaystyle$ T$\}$로 $표기$할 수 있으며, 변환된 등록된 모델 포인트 세트는 다음과 같습니다.

$({\mathcal {M}})$

(1)

따라서 포인트 세트 등록 알고리즘의 출력은 최적의 $변환{\displaystyle {}^{}}$ T ${\displaystyle (}$$$( \ $displaystyle$ T^ { \ $star$} )입니다$$.$이$를 통해 M$$( \ $displaystyle${ \ $mathcal$${$ $S$$}$ )은$$ 정의된 거리 ${\displaystyle \mathrm{함수}}$ dist ($$( ,${\displaystyle }$)의 개념에 따라 S ( \ $displaystyle$ { S$$} $)$에 가장 적합합니다.$torname {dist}$ (\$cdot,\cdot$) :

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

(2)

$여기$서 T$${\$displaystyle${\$mathcal {T}}$는 최적화가 검색하려는 가능한 모든 변환 집합을 나타내기 위해 사용됩니다.거리 함수의 가장 일반적인 선택은 모든 점 쌍에 대해 유클리드 거리의 제곱을 취하는 것이다.

${\displaystyle \operatorname {dist}(T({\mathcal {M}), {\mathcal {S})=\sum_{m\in T({\mathcal {M}})}\Vert_{2}{2}{2},\displaystyle s_{m=}\mathcal {\in}{\in}{\mathcal {\in}{\cal}{\in}{{\mathcal}{{\cal}{\cal}}{\cal}{{{\$

(3)

여기서 ${\displaystyle {}_{}{2\mathrm{}}_{}}${ $displaystyle$\ \$cdot$ \$_$ {$$2$$} }는 벡터 2-norm, $s{\displaystyle {}_{}}$ ${\displaystyle m_{}}${ $displaystyle s$_ { $m$$$}는$$ $세트{\displaystyle \mathcal{}}$ S$${ \ $displaystyle${ s$}$의 대응점이며 $세트{\displaystyle \mathcal{}}$M { $displaystyle${ s$}$에서 변환 후 지정된 $포인트{\displaystyle }$m {$$$displaystyle$ m$}$에 최단 거리에 도달합니다.이온. 강체 등록에서 이러한 함수를 최소화하는 것은 최소 제곱 문제를 푸는 것과 같다.

의 종류

예를 들어 기능 일치 기법을 사용하여 최적화 전에 대응(${\displaystyle {즉}_{}}$, s ${\displaystyle m}$ m {\$displaystyle s_{$m}\$leftrightarrow$ m$\})$이 주어진 경우 최적화는 변환만 추정하면 됩니다.이런 유형의 등록을 통신 기반 등록이라고 합니다.한편, 대응관계를 알 수 없는 경우, 대응관계와 변환을 함께 발견하기 위해 최적화가 필요하다.이러한 유형의 등록은 동시 포즈와 통신 등록이라고 불립니다.

한 ★★★★★

두 개의 점 세트가 있는 경우 고정 등록은 한 점 세트를 다른 점 세트로 매핑하는 고정 변환을 생성합니다.강성 변환은 두 점 사이의 거리를 변경하지 않는 변환으로 정의됩니다.일반적으로 이러한 변환은 번역과 ^[12]순환으로 구성됩니다.드문 경우지만 점 세트도 대칭될 수 있습니다.로보틱스와 컴퓨터 비전에서는 엄격한 등록이 가장 많은 응용 분야를 가지고 있습니다.

Non-rigid 등록)

두 개의 점 세트가 지정된 경우 비강성 등록은 한 점 세트를 다른 점 세트로 매핑하는 비강성 변환을 생성합니다.비강성 변환에는 스케일링 및 전단 매핑과 같은 아핀 변환이 포함됩니다.그러나 점 세트 등록의 경우 일반적으로 비강성 등록에는 비선형 변환이 포함됩니다.점 집합의 변동에 대한 고유모드가 알려진 경우, 비선형 변환은 고유값에 ^[13]의해 매개변수가 지정될 수 있습니다.비선형 변환은 박판 ^[14][13]스플라인으로서 파라미터화할 수도 있다.

★★★★

포인트 세트 등록에 대한 일부 접근법에서는 보다 일반적인 그래프 매칭 ^[11]문제를 해결하는 알고리즘을 사용합니다.그러나 이러한 방법의 계산 복잡도는 높은 경향이 있으며 엄격한 등록으로 제한됩니다.이 기사에서는 변환에 3D 회전 및 변환(균일한 스케일링 포함)이 포함되어 있다고 가정하는 견고한 등록 알고리즘만 살펴보겠습니다.

PCL(Point Cloud Library)은 n차원 포인트 클라우드 및 3D 지오메트리 처리를 위한 오픈 소스 프레임워크입니다.여기에는 몇 가지 포인트 등록 ^[15]알고리즘이 포함되어 있습니다.

통신 기반 등록

통신 기반 방법은 $모든{\displaystyle }$ 점 m${\displaystyle m\mathcal{}}$M {\$displaystyle$ m\$left arrow$s_${m$}}에$$ 대해 추정 $대응{\displaystyle }$ m ${\displaystyle \leftrightarrow }$ {\$displaystyle$ m$\in {mathcal {$$M$$\}\}\}$이 주어졌다고 가정하므로 두 점 모두 M ${\${$M$$}$과 S$\displaystyle$ {$mathcal}$을 설정하는 설정에 도달한다.}은$($는) $N개$의 {{$displaystyle$ N$$$}$개의 포인트를 가지며 m${\displaystyle {}_{}}$i ↔${\displaystyle {}_{}{s}_{}}$ ${\displaystyle i}$, i${\displaystyle =1}$,${\displaystyle }$…, $N${\$displaystyle m_{$i}\$left arrow s_{i},i=1,\displaystyle$,N$$$}$의 ${\displaystyle {대응}_{}}$이 주어집니다$.$

이상 무등록

가장 간단한 경우, 모든 대응이 올바르다고 가정할 수 있습니다.즉$,$ $\mathbb$ {R$}^{$3}의$$ ${\displaystyle {\mathbb{}}^{}{}_{}}$†$$ 3 \ $displaystyle m_{i$},$s_{$i}\ in \mathbb {R$}의$점이 $다음$과 같이 생성됩니다.

$\displaystyle s_{i}=lRm_{i}+\epsilon_{i},i=1,\display,N}$

(cb.1)

서 l> { $displaystyle$ l > $0$}은 균일한 스케일링 계수($많은{\displaystyle }$ $경우{\displaystyle }$ l ${\displaystyle =}$ { $displaystyle$ l=1}로 가정$),$ R$$${\displaystyle }$), ${\displaystyle \text{SO}}$ ( ${\displaystyle 3}$) { $displaystyle$R \ $in$\$text$}$SO$$}}(3)$는 적절한 3D 회전 ${\displaystyle \text{매트릭스}}$입니다$($ ${\displaystyle \mathrm{SO}}$ ( d$$) \ $displaystyle$ \$$text {$SO}}(d)$는 $d$도(\$displaystyle$ d$)$의 특수 직교군이고, t${\displaystyle }$${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$3(\displaystyle t$\in \mathbb {R}$^{$3})$은 3D 변환 벡터이며, ${\displaystyle i_{}}$R $(\$ _${i}\in \mathbb {R} ^3})$ 모델은$$ 알 수 없는 부가 노이즈입니다.구체적으로 잡음 ${\displaystyle i_{}}$i \ $display$style \ $epsilon$_ {$i$ } ${\displaystyle {is}_{}}$ i \ $display$style \ $sigma$ _ ${ i$} 、 즉, ${\displaystyle i_{}}$i ~${\displaystyle N\mathcal{}}$ (${\displaystyle 0}$ , ${\displaystyle i_{}^{}}$ ${\displaystyle {}_{}^{}{}_{}}$ $3$) { $display$style \ $epsilon$_ $i$} \ $sim${$cal nigma$ } } （ \ cal ） ） 。$I_{3$ 다음 최적화를 통해 미지의 스케일, 회전 및 변환에 대한 최대우도 추정치를 얻을 수 있습니다.

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

(cb.2)

스케일링 계수가 1이고 변환 벡터가 0일 경우 최적화는 Wahba 문제의 공식을 회복합니다.${\displaystyle \text{세트}\mathrm{SO}}$의 볼록하지 않음으로 인해 최적화(cb.2)가 볼록하지 않음에도 불구하고 (3$)\displaystyle\text{$$SO}}(3$ Berthold K.P. Horn의 연구 결과, (cb.2)는 규모, 회전 및 ^[16]변환의 추정치를 분리함으로써 실제로 폐쇄형 솔루션을 인정하는 것으로 나타났다.유사한 결과가 Arun ^[17]등에 의해 발견되었다.또한 고유 변환$({\displaystyle l}$ ,${\displaystyle R}$ ,${\displaystyle t}$) {$displaystyle ( l$ ,$R$ , t ) { displaystyle ( l , R , $t$)$$} 를 찾으려면 각 포인트 세트에서 N ${\displaystyle =}$ ${\displaystyle 3}$ {$displaystyle N=3}$이상의 $비선형{\displaystyle }$ 포인트가$$ 필요합니다.

좀 더 최근에, Briales과 Gonzalez-Jimenez Lagrangian이중성을 사용하여, 모델}}M{\displaystyle{{M\mathcal}설정된 사건에 대해 포함된 semidefinite 완화 다른 3D점들, 라인, 비행기와 같은 원시(이는 모델 M{\displaystyle{\mathcal{M}}}은 3D메시)을 개발했다.[18]흥미롭게도, 반무한 완화는 경험적으로 타이트하다.즉, 반무한 완화의 용액으로부터 증명 가능한 글로벌 최적 용액을 추출할 수 있다.

견고한 등록

최소 제곱 공식(cb.2)은 특이치가 있을 때 임의로 나쁜 성능을 발휘하는 것으로 알려져 있습니다.특이치 대응은 생성 모델(cb.1)에서 출발하는 ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ $(\$ rightarrow $m_{i$})의 측정 쌍입니다.이 경우 다음과 ^[19]같이 다른 생성 모델을 고려할 수 있습니다.

$\displaystyle s_{i}=sbegin{case}lRm_{i}+t+\epsilon_{i}&{\text{case}}i-{\text{case}}\o_{i}&{\text{case}}\text{case}}\end{case}}}}$

(cb.3)

여기서 $i{\displaystyle }$- {\$displaystyle i-}$${\displaystyle {번째}_{}}$ 쌍 i ${\displaystyle {}_{}}$ ${\displaystyle {mi}_{}}${\$displaystyle s_{i$}\$left$ rightarrow $m_{i$$}$가 인리어인 경우, 공간 $변환$에 의해$$${\displaystyle {mi}_{}}${\$displaystyle$$s_{$$i}$에서 얻을 수 있는 특이치 없는 모델(cb.1)에 준거한다.$-$ {\displaystyle $i-}$$번째$ 쌍 ${\displaystyle s_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\displaystyle {}_{}}$ ${\$ $s_{i$}\left$$ $rightarrow m_{i$}}은 특이치이며, $s{\displaystyle {}_{}}${\$displaystyle o_{$i$\}\}$는 ${\displaystyle {임의}_{}}$의 $벡터{\displaystyle {}_{}}$가 될 수 있습니다. 어떤 대응이 특이치인지 사전에 알 수 없으므로 생성 모델(cb3).)는 현재 기능 매칭 기법이 95%$이상$(\$style$ 95$\%)$이 ^[20]특이치일 수 있는 고도로 손상된 대응 관계를 출력하는 경향이 있기 때문에 실제 환경에 배치된 컴퓨터 비전 및 로봇 공학에 가장 중요하다.

다음으로 강력한 등록을 위한 몇 가지 일반적인 패러다임을 설명합니다.

최대 컨센서스

Maximum consensus seeks to find the largest set of correspondences that are consistent with the generative model (cb.1) for some choice of spatial transformation ${\displaystyle (l,R,t)}$. Formally speaking, maximum consensus solves the following optimization:

$\displaystyle \max _{l>0,R\in\text{SO}}(3),t\in \mathbb {R}^{3},{\mathcal {I}}\vert,\quad {text}{{}{\frac {1}{i}{2}\vert s_{i}-lrm_{i}-{2}_vert}_vert {{2}_vert}_vert}_{{{{}}}}\vert}$

(cb.4)

${\displaystyle 여기}$서 I$displaystyle\vert\mathcal {I}\vert)$는 $집합{\displaystyle \mathcal{}}$I(\$displaystyle\mathcal {I$의 카디널리티를 나타냅니다. (cb.4)의 제약에 따라 초기 $집합{\displaystyle \mathcal{}}$ I$(\$$displaystyle$$\mathcal {I})$의 모든 측정 쌍은 사전 정의된 임계값보다 $작아야{\displaystyle }$ 합니다$.$$ystyle \xi$ 불행히도 최근 분석에서는 글로벌 문제 해결(cb.4)은 NP-Hard이며, 글로벌 알고리즘은 일반적으로 최악의 ^{[21][22][23][24][25]}경우 지수 시간 복잡성을 수반하는 분기 및 경계(BnB) 기술에 의존해야 합니다.

컨센서스 최대화를 정확하게 해결하는 것은 어렵지만, 실제로 꽤 잘 작동하는 효율적인 휴리스틱스가 존재합니다.가장 일반적인 휴리스틱 중 하나는 랜덤 샘플 컨센서스(^[26]TRANSAC) 체계입니다.LANSAC은 가설과 검증을 반복하는 방법이다.각 반복에서 메서드를 첫번째 N{N\displaystyle}전문과의 전체 숫자에서 다음 메서드(cb.4) 어떻게 많은 서신들에게 세는 법에 그런 가설이(i. 데 동의한 제약 조건을 평가한다 가설(l, R, t){\displaystyle(l,R,t)}혼의 method,[16]을 사용하여 계산 샘플 3randomlye.,잔차${\displaystyle {}_{}{i}_{}}$ - ${\displaystyle l}$ R ${\displaystyle {}_{}{i}_{}}$ - ${\displaystyle t{\mathrm{}}_{}^{}}$ 2${\displaystyle {}_{}^{}}$/ ${\displaystyle {\delta }_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$( \ $displaystyle \Vert s_{i}$ - $lRm_{i}-t\Vert$_{2$}/\sigma$ _${i}^2}}$를 계산하여 각 측정 쌍에 대한 임계값$\delta {\displaystyle }$ {\$displaystyle \xi}$과 비교합니다.알고리즘은 충분한 대응이 있는 컨센서스 세트를 검출한 후 또는 허용된 총 반복 횟수에 도달한 후에 종료됩니다.LANSAC은 각 반복의 주요 연산이 Horn의 방법으로 폐쇄형 솔루션을 수행하는 것이기 때문에 매우 효율적이다.그러나 LANSAC은 비결정론적이며 실행 시간이 특이치 ^[20]비율에 비해 기하급수적으로 증가하므로 낮은 특이치 비율 체제(예:$$ 50% $미만)$에서만 잘 작동합니다.

빠르지만 부정확한 LANSAC 체계와 정확하지만 포괄적인 BnB 최적화 사이의 격차를 메우기 위해 최근 연구는 합의 극대화를 ^{[21][22][27][23]}해결하기 위한 결정론적 근사 방법을 개발했다.

제거

특이치 제거 방법은 공간 변환을 추정하기 전에 고도로 손상된 대응의 집합을 사전 처리하는 방법을 모색합니다.특이치 제거의 동기는 특이치 대응의 수를 크게 줄이면서 변환에 대한 최적화가 보다 쉽고 효율적이 되도록 하기 위함이다(예: 특이치${\displaystyle \mathrm{}}$비율이 95%$이상일$ 때는 LANSAC가 잘 작동하지 않지만, 특이치 $제거$에서는 상당히 잘 수행된다$).$r 비율이 50%$$입니다(\$displaystyle$ 50$\%).$

파라 외는 기하학적 제약 조건을 사용하여 특이치 ^[20]대응성을 유지하면서 특이치 대응성을 제거하는 GORE(보증된 특이치 제거)라는 방법을 제안했습니다.GORE는 특이치 비율을 대폭 줄일 수 있는 것으로 나타나 LANSAC 또는 BnB를 사용하여 컨센서스 극대화의 성과를 크게 높일 수 있다.Yang과 Carlone은 원래 측정 집합에서 쌍으로 변환-회전-불변량 측정(TRIM)을 구축하고 노드가 3D 지점인 그래프의 모서리로 TRIM을 포함시킬 것을 제안했다.inliers는 척도 측면에서 쌍으로 일관하므로 그래프 내에서 집단을 형성해야 합니다.따라서 그래프의 최대 클리크를 계산하기 위해 효율적인 알고리즘을 사용하면 인라이어를 찾아 ^[4]특이치를 효과적으로 제거할 수 있다.최대 clique 기반 특이치 제거 방법은 실제 포인트 세트 등록 ^[19]문제에서도 매우 유용한 것으로 나타났습니다.유사한 특이치 제거 아이디어도 Parra ^[28]등에 의해 제안되었다.

M-추정은 (cb.2)의 최소 제곱 목적 함수를 특이치에 덜 민감한 강력한 비용 함수로 대체합니다.공식적으로 M-추정은 다음 문제를 해결하려고 합니다.

$l style l^{\star}, display style l^{\star}, t^{\}=\display \ _{\star}SO}}(3),t\in \mathbb {R}^3}\sum _{i=1}^{N}\rho \lefts\frac {1}{i}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right$

(cb.5)

$여기$서 "${\displaystyle }$( ${\displaystyle )}$ )$$\ $displaystyle \rho$( \ $cdot$)"는 견고한 비용함수의 선택을 나타냅니다$$.${\displaystyle (}$ (${\displaystyle x}$ ) $=$ ${\displaystyle {x\mathrm{}}^{}}$2 (\$displaystyle \rho (x$)=$x^{2})$를 선택하면 (cb.2)의 최소 제곱 추정이 반환된다는 점에 유의하십시오.널리 사용되는 강력한 비용 $함수$에는 $§$ ${\displaystyle {1\mathrm{}}_{}}$ \$style \ell$ _${1}$ - norm$$ loss, Huber ^[29]loss, Geman-McClure^[30] loss 및 truncated 최소 제곱 ^[19][8][4]손실이 포함된다.M-추정은 로보틱스와 컴퓨터 ^[31][32]비전 분야에서 강력한 평가를 위한 가장 인기 있는 패러다임 중 하나이다.강력한 목적 함수는 일반적으로 비볼록형(예: 잘린 최소 제곱 손실 v.s. 최소 제곱 손실)이기 때문에, 비볼록형 M-추정을 해결하기 위한 알고리즘은 일반적으로 첫 번째 추측이 제공되는 국소 최적화에 기초하고, 이어서 obj를 계속 감소시키기 위한 변환의 반복적인 미세화가 뒤따른다.everitive function(이피션 기능)로컬 최적화는 초기 추측이 글로벌 최소값에 가까울 때 잘 작동하는 경향이 있지만 초기화가 제대로 이루어지지 않으면 로컬 최소값에 머무르기 쉽습니다.

눈금의

Graded Non-Volvexity(GNC; 단계적 비볼록성)는 초기화 없이 비볼록 최적화 문제를 해결하기 위한 범용 프레임워크입니다.얼리비전 및 머신러닝 ^[33][34]어플리케이션에서 성공을 거두었습니다.GNC의 핵심 아이디어는 쉬운 볼록형 문제부터 시작하여 어려운 비볼록형 문제를 해결하는 것입니다.구체적으로는, 특정의 견고한 코스트 함수${\displaystyle }\mu {\displaystyle }$( 「 ${\displaystyle 」}$ \$$$display$ style \$$$rho$ ( \$cdot$ $)$에 대해서, 하이퍼 $파라미터{\displaystyle }$μ( 「 $display$style \ $mu$ 「 $cdot$」)를$$ 사용해 대리 함수 ${\displaystyle {\mu }_{}}$${\displaystyle {}_{}}$ )를 구축할 수 있기 때문에, 그 조정은 점차적으로 볼록하지 않습니다$.$displaystyle $\rho$ _${\mu$}(\$cdot)}$은(는$)$ 타겟 함수 ${\displaystyle 「」(}$ $「」(\displaystyle$\rho (\$cdot$^[34][35]로 컨버전스 됩니다.따라서 하이퍼 $파라미터{\displaystyle }$ μ$\displaystyle\mu$의 각 레벨에서 다음과 같은 최적화가 해결됩니다.

$, {\mu}^{\star}, R_{\mu}^{\star}=\display_{\star}{\text},SO}}(3), t\in \mathbb {R}^{3}\sum _{i=1}^{N}\rho _{\mu}\left\frac {1}{\fright\Vert s_{i}-lRm_{i}-t\right}\Vert s_{2}\right}$

(cb.6)

블랙과 랑가라잔은 각 최적화(cb.6)의 목적 함수를 가중 최소 제곱의 합과 각 측정 ^[33]쌍에서 최적화의 신뢰도를 결정하는 가중치에 대한 소위 특이치 프로세스 함수로 이원화할 수 있음을 입증했다.Zhou 등은 Black-Rangarajan 이중성과 Generan-McClure 기능에 맞춘 GNC를 사용하여 통신의$$^[30]${\displaystyle \mathrm{약}}$ 80%(\$display style$ 80$\%)$의 특이치에 대해 강력한 고속 글로벌 등록 알고리즘을 개발했다.최근 Yang 등은 GNC(Geman-McClure 함수 및 잘린 최소 제곱 함수에 맞게 조정됨)와 Black-Rangarajan 이중성을 함께 사용하면 포인트 클라우드 및 메시 ^[35]등록을 포함한 강력한 등록 문제에 대한 범용 해결사로 이어질 수 있음을 보여주었다.

Registration cert cert cert cert cert 。

위에서 설명한 강력한 등록 알고리즘 중 거의 어느 것도(최악의 경우 지수 시간 내에 실행되는 BnB 알고리즘 제외) 성능 보증이 포함되어 있지 않습니다.즉, 이러한 알고리즘은 통지 없이 완전히 잘못된 추정치를 반환할 수 있습니다.따라서 이러한 알고리즘은 자율 주행과 같은 안전에 중요한 애플리케이션에 적합하지 않습니다.

아주 최근에, 양 외 연구진.는 Teaser(Truncated 최소 제곱 추정 및 SEMidefinite Relaxation, TEASER)^[19]라는 이름의 인증 가능한 최초의 강력한 등록 알고리즘을 개발했습니다.포인트 클라우드 등록의 경우, TEASER는 변환의 견적을 출력할 뿐만 아니라 주어진 견적의 최적성을 수치화합니다.티저에서는 다음 TLS(최소 제곱수) 추정치를 채택하고 있습니다.

$l style l^{\star}, display style l^{\star}, t^{\}=\display \ _{\star}SO}}(3),t\in \mathbb {R}^{3}\sum _{i=1}^{N}\min \lefts\frac _{i}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{{c}{{c}}}^{{{c}}}}}}}{{{{{}}}}}}}}}}}}}{{{{{{{{c}}}}}}}}}}}}}}}}}}}}}}}}$

(cb.7)

이 값은 TLS 로버스트 비용 $함수{\displaystyle }$( (${\displaystyle x}$ ) ${\displaystyle =min}$ ( ${\displaystyle {x\mathrm{}}^{}{\stackrel{}{}}^{}}$, c${\displaystyle {\stackrel{}{}2}^{\mathrm{}}}$2)$${\$displaystyle \rho$ ( x ) =$\min$ ( $x ^$ {2} ${\bar$ {c$}^$2$\}\}\}$을 선택함으로써 얻을 수 있습니다.$여기$서 ${\$ 2 {\$displaystyle {c}$ {c}^{2$}}$는 최대 허용 잔차를 결정하는 사전 정의된 상수입니다.반면 국외자 전문과(s‖ 나는 Rml − TLS는 목적 함수, 속성에 대해 내좌층 전문과(s‖ 나는 Rl 나는 t ‖ 나는 2개체 22/σ − m요리 ¯ 2{\displaystyle\Vert s_{나는}-lRm_{나는}-t\Vert_{2}^{2}/\sigma_{나는}^{2}<>{\bar{c}}^{2}}−)이 평소 최소 자승 페널티 적용된다.i / i > 2 { $displaystyle \Vert$ s$_$ { i} - $lRm$_ { $i$} - $t$\ $Vert$_ { ${2}$ / \ $sigma$_ { $i$}^2} > {\$bar$ {$c}^2}$> 패널티가 적용되지 않고 이상치는 폐기됩니다.TLS 최적화(cb.7)가 글로벌 최적성으로 해결되면 이는 내부 대응에만 Horn의 메서드를 실행하는 것과 같습니다.

그러나 (cb.7)는 조합적인 특성으로 인해 상당히 어렵습니다.TEASER는 다음과 같이 해결한다(cb.7). (i) 규모, 회전, 번역의 추정치를 분리하여 개별적으로 해결할 수 있도록 불변측정을 구축한다. (ii) 규모 TLS의 문제를 해결할 수 있는 3가지 서브문제 각각에 대해 동일한 TLS 추정치를 적용한다.xact적으로는 적응형 투표라고 불리는 알고리즘을 사용하여 회전 TLS 문제는 ^[8]실제로는 이완이 정확한 반확정 프로그램(SDP)으로 완화될 수 있습니다.변환 TLS 문제는 컴포넌트별 적응형 투표를 사용하여 해결할 수 있습니다.GNC를 활용한 신속한 구현은 여기서 오픈소싱됩니다.실제로 TEASER는 99$\%(\backslash displaystyle$ 99$\%)$ 이상의 ${\displaystyle \mathrm{이상}}$ 대응을$$ 허용하고 밀리초 내에 실행할 수 있습니다.

Teaser를 개발하는 것 외에, Yang 등은 포인트 클라우드 데이터에 대한 몇 가지 경미한 조건 하에서 Teaser의 추정 변환이 지상-진실 ^[19]변환의 오류를 제한하고 있음을 증명했다.

및 동시

반복 근접점(ICP) 알고리즘은 Besl과 McKay에 ^[36]의해 도입되었다.알고리즘은 (i)변환이 주어지면 (i) $M$의 모든 $점$에 대해 S$(\$에서 가장 가까운 점을 찾고 (ii) 최소한의 s를 풀어서 최적의 강성 변환을 찾는 반복적인 방식으로 강성 등록을 수행합니다.문제를 해결합니다(cb.2).따라서 M$(\$의 $초기{\displaystyle \mathcal{}}$ $포즈$가 S$(\$displaystyle\$mathcal {S$에 충분히 가까운 것이 가장 효과적이며, 의사 코드에서는 다음과 같이 기본 알고리즘을 구현한다.

알고리즘 ICP(M, S) : : = 등록되지0 않은 경우i: X : = ) T ( M , ) ) : : : = S toi m X : = X + mi m, ŝjj θ : = lest_squares(X)를 반환합니다.

여기서 함수는least_squares는 Horn 및$Arun$의^{[16] [17]}폐쇄형 $솔루션을 사용$하여 각 쌍의 거리를$최소화$하기 ${\displaystyle {위해}_{}}$ ${\displaystyle {최소}_{}}$ 제곱 최적화를 수행합니다$.$

등록비용 함수는 S$(디스플레이$ 스타일)에서 M$($$디스플레이 스타일)$의 모든 점에 가장 가까운 점을 찾는 것에 따라 달라지므로 알고리즘 실행 시 변경될 수 있습니다.따라서 ICP가 실제로 로컬 ^[37]최적치에 정확히 수렴한다는 것을 증명하기는 어렵다.실제로 경험적으로 ICP와 EM-ICP는 비용 ^[37]함수의 로컬 최소값으로 수렴되지 않습니다.그러나 ICP는 이해하기 쉽고 구현이 간단하기 때문에 가장 일반적으로 사용되는 포인트 세트 등록 ^[37]알고리즘으로 남아 있습니다.포인트 선택과 일치에서 최소화 전략에 ^[13][38]이르기까지 알고리즘의 모든 단계에 영향을 미치는 다양한 ICP가 제안되어 왔다.예를 들어 기대 최대화 알고리즘을 ICP 알고리즘에 적용하여 EM-ICP 방식을 형성하고, 레벤버그-마르카트 알고리즘을 ICP 알고리즘에 적용하여 LM-ICP ^[12]방식을 형성한다.

견고한 포인트 매칭

견고한 포인트 매칭(RPM)은 Gold ^[39]등에 의해 도입되었다.이 메서드는 결정론적 어닐링 및 점 세트 간 대응의 소프트 할당을 사용하여 등록을 수행합니다.ICP에서는 가장 가까운 이웃의 휴리스틱에 의해 생성된 대응이 바이너리인 반면, RPM은 두 점 사이의 대응이 0에서 1 사이일 수 있지만 최종적으로 0 또는 1 중 하나로 수렴될 수 있는 소프트 대응이 사용됩니다.RPM 의 대응은 항상 1 대 1 이며, ICP ^[14]에서는 항상 해당되지 않습니다.M$({$${i$$})$에서 m$(\$$displaystyle$ m_{i$})$을 i$(\displaystyle$ $i$$)$의 $점$으로 $,$ s(\$displaystyle s_$${$j$$$})$를 s(\displaystyle j$\})$의 j(\$displaystyle$ j$)$의 $점$으로 $합니다{\displaystyle {}_{}}$$.$ 일치 매트릭스$$$μ$(\$displaystyle$ \$mathbf)$는 다음과 같이$$ 정의됩니다$.$

${\displaystyle \mu _{ij}=cases}1&{\text{if point}}m_{i}{\text{j}\0&{\text{cases}}}m_{i}{\text{cases}}}}$

(rpm.1)

다음으로 문제는 두 개의 포인트 $세트{\displaystyle \mathcal{}}$ M$(\$과 S$$$(\$$displaystyle$${S})$에서 $Affine$ 변환 T(\displaystyle T$})$와 $이들$을 ^[39]가장 잘 관련짓는 매치 $매트릭스{\displaystyle }$μ(\$displaystyle$ \$mathbf {mu})$를 찾는 것으로 정의됩니다.최적의 변환 방법을 알면 일치 매트릭스를 쉽게 결정할 수 있으며, 그 반대의 경우도 마찬가지입니다.단, RPM 알고리즘에 의해 양쪽이 동시에 결정됩니다.변환은 변환 벡터와 변환 매트릭스로 분해할 수 있습니다.

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

2D $매트릭스{\displaystyle \mathbf{}}$ A$(\$$})$는 각각 스케일, 회전, 수직 및 ${\displaystyle \mathrm{수평}}$ 전단 성분인 4개의 파라미터$displaystyle \lbrace$ a$,\theta, b, c\rbrace$로 구성되어 있습니다.비용 함수는 다음과 같습니다.

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

(rpm.2)

$j\mathrm{}$j $\text{∑}\underset{}{\overset{}{}}$ $\underset{}{\overset{}{i}}$ $\underset{}{\overset{}{=}}$ $\underset{}{\overset{}{1}}$ $\underset{}{\overset{}{}}{}_{}$ ${\mu }_{}$ i $j_{}1$1 { $textstyle \forall$ j$~\sum$ _${$$i=1}^{M}\mu$ _${$${\mathrm{ij}}_{}$$}\leq1$$\mathrm{}i$ i $j_{}$ $\underset{}{\overset{}{}}$ $\underset{}{\overset{}{}}{}_{}${ $textstyle$ \$forall$ i$~\sum$_j$= 1$ }^{n$\mu$ leq$}_i}$에 따릅니다.일치 행렬에 더 많은 상관 관계가 있는 경우 비용을 줄임으로써 더 강력한 상관 관계를 지향하는 목표를 제시합니다.$함수{\displaystyle }$ g$)$ {$style$ g$(\mathbf {A})}$는 스케일 및 전단 성분의 큰 값을 벌칙화하여 아핀 변환을 정규화하는 역할을 합니다.

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

(\$displaystyle\$displaystyle\$displays$ $）$ $。$

RPM 방식은 Softassign 알고리즘을 사용하여 비용 함수를 최적화합니다.1D 케이스는 여기서 파생됩니다.변수${\displaystyle }$세트 {${\displaystyle Q_{}}$ j $}$ {\$displaystyle Q_{j}\rbrace}($${\displaystyle Q_{}}$ j$$ R ${\displaystyle {\mathrm{}}^{}}$ { $displaystyle Q_{j}\in \mathbb {R}$$^{1}).$ $변수{\displaystyle {}_{}}$ ${\displaystyle {\mu }_{}}$j$(\displaystyle$ \$mu _{$j$$})는 $각{\displaystyle {}_{}}$ ${\displaystyle Q_{}}$j(\$displaystyle$ Q_j$})$에 관련지어집니다$.\underset{}{\overset{}{}}$$_{j}=1$목표는$\underset{j}{\overset{}{}}$ j $\underset{}{\overset{}{=}}$ $\underset{}{\overset{}{}}$ $\underset{}{\overset{}{}}{}_{}$ ${}_{}{}_{}$ j $Q_{}$j { $textstyle \sum$_ {j$= 1$ }^{$J}\mu$ _ {$j}Q_{j$을$($를) 최대화하는$$μ {$displaystyle \mathbf {mu$}를$$ 찾는 것입니다.이는 제어 β >$(\displaystyle$ \$beta >$ 0을 도입함으로써 연속적인 문제로 공식화할 수 있으며, 결정론적 어닐링 방법에서는 알고리즘이 실행됨에 $따라{\displaystyle }$ 제어 파라미터$$β$(\displaystyle$ \$beta$})를$$ 서서히 증가시킨다.μ$(\$는 다음과 같습니다.

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

(rpm.3)

이것은 softmax 함수라고 불립니다.β$(\displaystyle \beta$})가$$ $증가$하면 식(rpm.1)에서 원하는 이진 값에 접근합니다.이제 이 문제는 2D 사례로 일반화될 수 있습니다. $\underset{}{\overset{}{여기}}$서 δ j$\underset{=}{\overset{}{}}$ $\underset{}{\overset{}{}}$ J ${}_{}{}_{}$ j Q $j_{}${ $textstyle \sum$_ {$j=1$}^{$J}\mu$ _${j}Q_{j$를 최대화하는 대신 다음이 최대화됩니다.

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

(rpm.4)

어디에

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

이제$$μ \$displaystyle \mu$}에 대한 제약조건이 이중 확률행렬 제약조건이라는 점을 제외하고, $\mathrm{\mu j}\mathrm{}$=$\underset{1}{\overset{}{}}${$textstyle \forall$ j$~\sum$ _${i=1}^{M}\$$mu$ _${ij$} =$1$$$ $1$ {$textstyle$ } 및 $\forall \mathrm{}$ i $\underset{}{\overset{}{=}}$ $\underset{}{\overset{}{}}$ {textstyle j = 1 {t}의 제약조건이다.방정식(rpm.3)은 2D 사례에 대해 간단히 표현할 수 없습니다.제약 조건을 만족시키기 위해, 행과 열의 정규화를 번갈아 수행하는 반복 프로세스에 의해 모든 양의 엔트리가 있는 정사각형 행렬에서 이중 확률 행렬을 얻는다는 Sinkhorn ^[39]때문에 결과를 사용할 수 있다.따라서 알고리즘은 다음과 같이 ^[39]기술됩니다.

알고리즘 RPM2D{\displaystyle({{M}},{{S}\mathcal\mathcal})}t:=0ij., θ b, c:=0β:)나는 j β0μ ^:=1+ϵ{\displaystyle{\hat{\mu}}_{ij}:=1+\epsilon}는 동안β<>βf:μ 융합되지 않았다. 업데이트 통신 매개 변수softassign Q에 의해 나는 j//:=−∂ 비용 ∂ μ(M, S)       ${\displaystyle Q_{ij$}:$$$=$$-{\frac${$cost$$}{\frac$\$mu$$$_${$$ij}}}{$$ij$ 0$:=\exp(\displaystyle Q_{ij})///$싱크혼의 메서드를 $적용합니다.$$모든{\displaystyle {\stackrel{}{}}_{}^{}}$ 행에서 malizing:${\displaystyle {\stackrel{}{}\mu }_{}^{}}$ ^ ${\displaystyle i_{}^{}}$ j ${\displaystyle {}_{}^{}}$: ${\displaystyle =\frac{{\stackrel{}{}}_{}^{}}{\underset{}{\overset{}{\mu }}}}$ ^ ${\displaystyle \frac{{\mathrm{}}_{}^{}}{}}$ 0 $=$ ${\displaystyle \frac{\underset{}{\overset{}{}}}{}}$M + ${\displaystyle \frac{\underset{}{\overset{}{}}{\stackrel{}{}\mu }_{}^{}}{}}$ ^ ${\displaystyle \frac{i_{}^{}}{}}$ j$$ { $displaystyle {\hat {\mu }_{ij}^{1$} ${\sum$ _${i=1}^{mu}^{{$0j$}}}^{{{{i$}}}}}^{{{{{{$i}}}}}}}}}}}}{i}}}}}}{$i}}{i}}}{i}}}{i}}}}{i}}}${\displaystyle {}_{}^{}}$i ${\displaystyle {\mathrm{}}_{}^{}}$ 0${\displaystyle {}_{}^{}}$: $=$ ^ i ${\displaystyle \frac{j_{}^{}}{}}$ ${\displaystyle \frac{{}_{}^{}}{\underset{\mu }{\overset{}{}}}}$ j $=$ ${\displaystyle \frac{\underset{}{\overset{}{1}}}{}}$ + ${\displaystyle \frac{\underset{}{\overset{}{}}{\stackrel{}{}\mu }_{}^{}}{}}$ ^ i ${\displaystyle \frac{{\mathrm{}}_{}^{}}{}}$1 { $displaystyle {\hat {{mu }}_{ij}{1}{\sum$_ $n+1}{\hat }{ij}}}{{{{ij}}}}}}{{{{{{{{\hat$ }}}}}}}}}}}}}}}}}{{{{{{{{{{{{{{{{{{{\}}}}}}}}}}}}}$$Newton의 $메서드{\displaystyle }$β : ${\displaystyle =}$ $β$ ${\displaystyle {}_{}}$β : = \ $displaystyle _$ { $r$$}$ $\gamma$${\displaystyle }$ : ${\displaystyle =}$ ${\displaystyle \frac{{\beta }_{}}{}}$ r$$: ${\displaystyle \frac{{}_{}}{}}$ 、 = $displaystyle$\ displaystyle : =$displayfrac${$$} { \$r$ }} {\ display$$ frac $_${ r }}}} } } a a a a 、 a, b, c를 반환합니다.

여기서 결정론적 아닐링 제어 $파라미터{\displaystyle }$ β$(\displaystyle\displaystyle_$${0})$는 처음에 ${\displaystyle {\beta \mathrm{}}_{}}$0(\$displaystyle\displaystyle_$${r$})으로 설정되며 $최대값{\displaystyle {}_{}}$ ${\displaystyle {\beta }_{}}$ f$(\$에 도달할 때까지 $계수{\displaystyle {}_{}}$ ${\displaystyle {\beta }_{}}$ r$(\$만큼$$ $증가$합니다.μ\$displaystyle\mu}$에 $대한{\displaystyle }$ 제약조건이 부등식이기 때문에 정규화 단계의 합계는$$M(\$displaystyle$ M$)$과$$N(\$displaystyle$ N$)$이 아닌${\displaystyle }$M +$$${\displaystyle 1}$(\$displaystyle$ N$+1)$과$$N(\displaystyle N)이 됩니다.$따라서{\displaystyle }$ M${\displaystyle }$+$$ {$displaystyle$ M+$1}번째$ $및{\displaystyle }$N +$$ {$displaystyle$ N$+1$}번째$$ 요소는 느슨한 변수입니다.

또한 알고리즘은 3D 이상의 차원에서의 포인트 세트에 대해서도 확장할 수 있습니다.$(\$의 제약조건은 3D 케이스와 2D 케이스와 동일합니다.따라서 알고리즘의 구조는 변하지 않고 회전행렬과 변환행렬이 ^[39]어떻게 해결되는지가 주요 차이점이다.

박판 스플라인 견고한 포인트 매칭

Chui 및 Rangarajan의 Thin Plate Spline Robust Point Matching(TPS-RPM) 알고리즘은 변환을 박판 스플라인으로 ^[14]매개 변수화함으로써 RPM 방법을 증가시켜 비강성 등록을 수행합니다.그러나 박판 스플라인 파라미터화는 3차원에서만 존재하기 때문에 이 방법을 4차원 이상의 문제로 확장할 수 없습니다.

커널 상관

포인트 세트 등록의 커널 상관(KC) 어프로치는 Tsin과 Kanade에 ^[37]의해 도입되었습니다.ICP에 비해 KC 알고리즘은 노이즈가 많은 데이터에 대해 더욱 견고합니다.모든 모델 점에 대해 가장 가까운 장면 점만 고려하는 ICP와 달리 여기서는 모든 장면 점이 모든 ^[37]모델 점에 영향을 미칩니다.따라서 이는 다중 링크 등록 알고리즘입니다.일부 커널 $함수{\displaystyle }$K(\$displaystyle$ K$)$의 경우 x ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$(\displaystyle $x_{$i$$$}, x_{j$})의 커널 $상관{\displaystyle }$ ${\displaystyle K}$ C$(\$$displaystyle$$$KC)가$$ 다음과 ^[37]같이 정의됩니다.

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

(802.1)

포인트 세트 등록을 위해 선택된 커널 $함수{\displaystyle }$K(\$displaystyle$ K$)$는 일반적으로 파젠 창 밀도 추정에 사용된 것과 유사한 대칭 및 음이 아닌 커널입니다.Epanechnikov 커널 및 Tricube 커널과 같은 다른 커널이 ^[37]대체될 수 있지만, 일반적으로 그 단순성을 위해 사용되는 가우스 커널은 대체될 수 있습니다.$포인트$ 세트 전체의 커널 $상관관계$는 세트 내의 모든 포인트와 세트 ^[37]내의 다른 모든 포인트의 커널 상관관계 합계로 정의됩니다$.$

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

(802.2)

점 집합의 KC 로그는 상수 인자 내에서 정보 엔트로피에 비례합니다.KC가 점 세트의 "콤팩트성"의 척도인지 관찰하십시오. 점 세트의 모든 점이 동일한 위치에 있으면 KC가 큰 값으로 평가됩니다.일부 변환 파라미터$\delta {\displaystyle }$(\$displaystyle \theta)$에 대한 포인트 세트 등록 알고리즘의 비용 함수는 다음과 같이 정의됩니다.

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

(802.3)

일부 대수적 조작은 다음을 산출합니다.

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

(802.4)

$K$ C${\displaystyle }$( ${\displaystyle S\mathcal{}}$) ( \ $displaystyle$ $KC$$$( { \$$$mathcal$ { S$$$}$ ） ${\$ {\ $\{\backslash$ {\ {\ {\ {\ further further further further further further further further further further further further further further further further further further${\displaystyle }$further further further$$ ${\displaystyle \mathrm{ent}}$ {\ {\ ent ent ent ent （ \ $displaystylegistration$（ T ( M ,$$） ）$rigid$ ${\displaystyle rigid\mathcal{}}$ rigid rigid rigid rigid rigid rigid rigid rigid rigid rigid rigid ${\displaystyle \mathrm{rigid}}$ rigid rigid rigid rigid rigid rigid rigid rigid rigid rigid rigid rigid $rigid$e 모든 점 쌍 사이의 유클리드 거리는 강성 변환 하에서 동일하게 유지됩니다.따라서 위의 방정식은 다음과 같이 고쳐 쓸 수 있습니다.

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

(802.5)

커널 밀도 추정치는 다음과 같이 정의됩니다.

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

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

비용 함수는 다음 2개의 커널 밀도 추정치와의 상관관계를 나타낼 수 있습니다.

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

(802.6)

비용 함수를 설정한 알고리즘은 단순히 구배 강하를 사용하여 최적의 변환을 찾습니다.모든 반복에서 비용 함수를 처음부터 계산하는 것은 계산 비용이 많이 들기 때문에 비용 함수 방정식(kc.6)의 이산 버전이 사용됩니다.커널 밀도 $추정치{\displaystyle {}_{}}$ ${\displaystyle P_{}}$M , ${\displaystyle {}_{}}$ ${\displaystyle {S\mathcal{}}_{}}${\$displaystyle P_{\mathcal {M}}, P_{\mathcal {S}}}$는 그리드 포인트에서 평가하여 룩업 테이블에 저장할 수 있습니다.ICP 및 관련 방식과는 달리 가장 가까운 네이버를 찾을 필요가 없기 때문에 KC 알고리즘의 구현이 비교적 간단해집니다.

노이즈가 많은 2D 및 3D 포인트 세트의 ICP 및 EM-ICP에 비해 KC 알고리즘은 노이즈에 덜 민감하여 올바른 등록이 ^[37]더 자주 이루어집니다.

가우스 혼합 모형

커널 밀도 추정치는 가우스 혼합 모델(GMM)^[40]로 나타낼 수 있습니다.지안과 Vemuri는 KC 등록 알고리즘의 GMM 버전을 사용하여 박판 스플라인에 의해 파라미터화된 비강성 등록을 수행합니다.

코히런트 포인트 드리프트

Myronenko와 ^[13][41]Song에 의해 CPD가 도입되었다.알고리즘은 GMM KC 방법과 유사하게 포인트 세트를 정렬하는 데 확률론적 접근방식을 취한다.박판 스플라인 변환 모델을 가정한 비강성 등록에 대한 이전의 접근방식과 달리 CPD는 사용된 변환 모델에 대해 독립적이다.포인트 $세트{\displaystyle \mathcal{}}$M(\$displaystyle\mathcal {M})$은 가우스 혼합 모델(GMM)의 중심을 나타냅니다$$.2개의 포인트세트가 최적으로 정렬되어 있는 경우 대응은 특정 데이터 포인트에 대한 GMM 사후 확률의 최대값입니다.점 집합의 위상 구조를 보존하기 위해 GMM 중심은 그룹으로 일관되게 이동해야 합니다.기대 최대화 알고리즘은 비용 ^[13]함수를 최적화하기 위해 사용됩니다.

M${\displaystyle$ {$M}}$에 M점,$$S {\$display\mathcal {$S$\}\}$에 N점이 있다고 가정합니다. 점 s에 대한 GMM 확률 밀도 함수는 다음과 같습니다.

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

(cpd.1)

여기서 $D차원$에서의${\displaystyle }$p ( ${\displaystyle s}$i$$) { $displaystyle$ p ( $s i$ ) ${\displaystyle m}$ M$$( \ $displaystyle m$_ { $i$} \ $in$\ $mathcal${ $M$}$$${\displaystyle {}_{}}$ $M{\displaystyle {}_{}}$ 을 중심으로 한 가우스 분포입니다.

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

멤버십 $확률{\displaystyle }$P (${\displaystyle i}$ ) ${\displaystyle =}$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ( \ $displaystyle$P ( i ) =$flac${1} {$M}}$ 은$$ 모든 GMM 구성 요소에 대해 동일합니다.균일한 분포의 무게는 w ${\displaystyle [}$ [${\displaystyle 0}$ , $]\displaystyle$ w$\in [ 0$ , $1$로 $표시$됩니다.혼합 모델은 다음과 같습니다.

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

(cpd.2)

GMM 중심은 우도 극대화에 의해 추정된 파라미터 세트$\delta {\displaystyle }$(\$displaystyle \theta)$에 의해 재파라미터화됩니다.이는 음의 로그 우도 함수를 최소화하는 것과 같습니다.

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

(cpd.3)

데이터가 독립적이고 균등하게 분포되어 있다고 가정한다.두 $점{\displaystyle {}_{}}$ $(\$})와 ${\displaystyle s_{}}$ j$(\$ 사이의$$ 대응 확률은 데이터 포인트가 주어진 GMM 중심 후방 확률로 정의된다.

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

기대 최대화(EM) 알고리즘은 $"\displaystyle$ \$theta"$ 및$$ "$\$^{$2$ 를 $검색$하기 위해 사용됩니다.EM 알고리즘은 2개의 스텝으로 구성됩니다.먼저 E단계 또는 추정단계에서 모수 값("오래된" 모수 값")의 값을 추측한 다음 Bayes의 정리를 사용하여 혼합 성분의 ${\displaystyle {\text{사후}}^{}}$ ${\displaystyle \mathrm{확률}}$ 분포 P${\displaystyle {}^{}}$old (${\displaystyle {}_{}}$i ,${\displaystyle s_{}}$ j$$) \ $displaystyle$ P$^{\text{old}}(i$ ,$s_{$j})를 계산한다.둘째, M 단계 또는 최대화 단계에서 완전한 음의 로그 우도 함수, 즉 비용 함수의 기대를 최소화함으로써 "새로운" 매개변수 값을 구한다.

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

(cpd.4)

$§$ {$displaystyle \theta}$ $및$$$§ {$displaystyle \sigma$와 무관한 상수를 무시하면 방정식(cpd.4)은 다음과 같이 나타낼 수 있습니다.

${\displaystyle \operatorname {cost}(\theta,\display ^{2}={j=1}^{N}\sum _{i=1}^{M+1}P^{\text{old}(i s_{j})\lvert s_{j-{T})$

(cpd.5)

어디에

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

N ${\displaystyle =}$ ${\displaystyle {N\mathbf{}}_{}}$ P$${\$style N=$N_{\$mathbf${$P}}}$인 경우 ${\displaystyle \mathrm{w}}$ $=$ 0(\$style$ w$=0$인 $경우$에만 해당됩니다.이전 매개변수 $값{\displaystyle {}^{}}$ ${\displaystyle {\text{P}}^{}}$old {\$displaystyle$ P$^{\text{old}}}$를 사용하여 계산된 GMM 성분의 후방 확률은 다음과 같다.

${\displaystyle P^{\text{old}}(i s_{j})=blvert s_{j}-T(m_{i},\text{old}}}\rvert ^{2}\sum}_xpfrac {\frac {1}_xp\frac {\frac {\frac {\frac {2\frac {2}}}}{\frac {\f}}}}} {\t}}} {\t}}}}} {\lVert sm} {{{{{\t}$

(cpd.6)

등식(cpd.5)에서 비용 함수를 최소화하면 국소 ^[13]최소값이 아닌 한 등식(cpd.3)에서 음의 로그 우도 함수 E가 감소합니다.따라서 알고리즘은 포인트 세트 M({$displaystyle {M})$과$$S$({$는${\displaystyle }$M ×$$({$displaystyle$ M$\times$D}) 및$$${\displaystyle }N{\displaystyle }$ ×$$({$displaystyle$$$N$\times$D}) 행렬$$$M{\displaystyle \mathbf{}}$$({displaystyle S})$로 표현된다.$\$^[13]displaystyle \mathbf {S} 각각$$$:$

알고리즘 CPD:=1σ 2:=1D≤ 0≤ w를 초기화하 θ0{\displaystyle({{M}},{{S}\mathcal\mathcal})}θ(M, S)NM∑ j=1N∑ 나는 갈1M‖ sj− m나는 ‖ 2{\displaystyle \sigma ^{2}:={\frac{1}{지발 중성자 감시기}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{나는}\rVert ^{2}}지 않으나 등록된://E-s.tep, i ∊ [ 1, M ]및 j ∊ [ 1, N ]의 P를 ${\displaystyle {\mathrm{계산}}_{}}$합니다${\displaystyle {}_{}\frac{p}{}}$ i : ${\displaystyle =\frac{exp\frac{\mathrm{}}{}}{}}$ （ - 1 ${\displaystyle \frac{\frac{2\mathrm{}}{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ 2 ${\displaystyle \frac{\frac{{}^{}}{}}{}}$ ${\displaystyle \frac{s_{}}{j_{}}}$- ${\displaystyle \frac{T}{}}$（ ${\displaystyle \frac{{mi}_{}}{{}_{}}}$,${\displaystyle \frac{{2\mathrm{}}^{}}{}}$ 2${\displaystyle \frac{{}^{}{}^{}}{}}$ ${\displaystyle \frac{\sum }{\underset{}{\overset{}{}}}}$ ${\displaystyle \frac{\underset{}{\overset{}{k}}{}_{}\underset{}{\overset{}{=}}}{}}$ ${\displaystyle \frac{\underset{}{\overset{}{}}}{}}$ ${\displaystyle \frac{M}{}}$ exp${\displaystyle \frac{（}{}}$ - ${\displaystyle \frac{\frac{1\mathrm{}}{}}{}}$ 2 ${\displaystyle \frac{2}{}}$ ${\displaystyle \frac{{}_{}}{}}$ 2 ${\displaystyle \frac{2}{}}$ ${\displaystyle \frac{\frac{{}^{}}{}}{}}$ +${\displaystyle \frac{2{}^{}}{}}$$=paramfrac {\exp \frac$ {$1}{2\$frac $^{$2}\$lVert s_{j$}-$T(m_{i$},\theta$)\rVert ^{$2}\$right}{\sum _$ ${k=1$}{$M}\exp \frac${\f}{\$frac$ {\$f}s}s$} s_${{{2}}{{{$bert}}}}}\$lVert$ ^}

$여기$서 벡터 1$(\$은 1의 열 벡터입니다.그solve기능은 수행된 등록 유형에 따라 다릅니다.예를 들어, 강체 등록에서는 출력은 스케일 a, $회전행렬$R$,$ $변환벡터{\displaystyle \mathbf{}}$t {\$displaystyle \mathbf$ {t$\}$입니다.$파라미터{\displaystyle }$ ${\$ {\$displaystyle \theta }$는 다음의 튜플로서 쓸 수 있습니다.

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

이 값은 1의 항등 행렬과 0의 열 벡터로 초기화됩니다.

$\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) NP : = ${\displaystyle {1P1\mu s}_{}}$T : ${\displaystyle =}$ ${\displaystyle \frac{{1N\mathbf{}}_{}}{}}$ P ${\displaystyle {}^{}}$ ${\displaystyle {}^{}{\mathbf{}}^{}}$ ${\displaystyle {}^{}}$ T$$ \ $displaystyle$\ $mu$_ {$$$s$ :$=mathbf${1$}{N_{\mathbf$ {P$}}}\mathbf$ {$S}$ ^{$T}\mathbf$ {$P$${\displaystyle {}_{}}$$}$ ^{T$}\mathbf${1}${\displaystyle \mu m\frac{\mathrm{}}{}}$ := ${\displaystyle \frac{{1P\mathbf{}}_{}}{}}$ ${\displaystyle {}^{}\mathbf{}}$ ${\displaystyle P\mathbf{}}$ 1 {$m}$ : $= frac {mathb$$}{$$N}$$displaystyle$T}}A:)ST^ PTM^{\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(ξ)is는 대각선 매트릭스부터 벡터 ξ R:)UCVT:=tr⁡(ATR)tr. ⁡($^$$})$T}\operatorname{diag}(\mathbf{P}\mathbf{1}){\hat{\mathbf{M}}}})}}}행렬을 t의 tr은 추적:)//μs − aRμm σ 2:=1NPD(tr ⁡(S^ Tdiag ⁡(PT1)S^)− tr ⁡(ATR)){\displaystyle \sigma ^{2}:={\frac{1}{N_{\mathbf{P}}D}}(\operatorname{tr}(\mathbf{{\h.에서${{mathbf {S}}}^{$$T}\operatorname {diag}(\mathbf {P}$^{$T}\mathbf${$1}){\hat {mathbf {S} } )-a\$operatorname ${tr$}(\$mathbf {A}$^{T}\$mathbf${R$}),$ 반환 {A2, T} }

강체 변환 대신 아핀 변환을 찾는 것이 목표인 아핀 등록의 경우 출력은 아핀 변환 $행렬{\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)     NP : = 1P1T     $\displaystyle \mu _{s:=paramfrac {1}{N_{\mathbf {P}}}\mathbf {S}^{T}\mathbf {P}^{T}\mathbf {1}$     ${\displaystyle \mu _{m}:=syslogfrac {1}{N_{\mathbf {P}}}\mathbf {M}^{T}\mathbf {P}\mathbf {1}}$     $(\displaystyle {\mathbf {S}):=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}$     $(\displaystyle {\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\mathbf {2}:=displayfrac {1}{N_{\mathbf {P}}D}}({\hat\mathbf {S}})^{T}\operatorname {diag}(\mathbf {P} ^{T}\mathbf {1}){\hat {mathbf {S}}-\operatorname {tr}(\hat {S} })^{T}\mathbf {P}^{T}{\hat {mathbf {M}}}}\mathbf {B}^{T}}}}}$     {B, t}을2(를) 반환하다 

또한 ^[13]변동 미적분을 사용하여 도출된 매개 변수를 사용하여 CPD를 비강성 등록과 함께 사용할 수도 있습니다.

가우스 분포의 합계는 고속 가우스 변환(FGT)^[13]을 사용하여 선형 시간으로 계산할 수 있습니다.따라서 CPD의 시간 복잡도는 $O{\displaystyle }$${\displaystyle (M}$ ${\displaystyle +}$ ${\displaystyle N}$${\displaystyle )\backslash }$$displaystyle$ O$(M+N)\$displaystyle O(M+N$)\backslash$displaystyle O$(MN)\$^[13]displaystyle O(MN)\보다 $점근적으로 훨씬$ 빠르다.

베이지안 코히런트 포인트 드리프트(BCPD)

베이지안 코히런트 포인트 드리프트(BCPD)라고 불리는 코히런트 포인트 드리프트의 변형은 포인트 세트 등록의 베이지안 공식을 통해 도출되었습니다.[42]BCPD.,(1)과 엄격한 연식의 등록 단일 알고리즘에 수행할 수 있는 알고리즘을 관계 없이 Gaussianity 그람 행렬의 운동 응집을 정의하기가 가속화될 수 있(2), 알고리즘 더 분리된 것들에 대한outlier distribu의 좀 더 합리적인 정의 때문에 견고하다(3)CPD, 예에 대한 여럿의 이점이 있다.회부 등n. 또한 베이지안 공식에서 움직임 일관성은 변위 벡터의 사전 분포를 통해 도입되었으며, 움직임 일관성을 제어하는 조정 매개변수 간에 분명한 차이를 제공한다.BCPD는 (1) 포인트 세트의 다운샘플링, (2) 다운샘플링 포인트 세트의 등록, (3) 변형 필드의 보간으로 구성된 3단계 절차인 BCPD++라는 방법으로 더욱 가속화되었다.^[43] 이 방법은 등록 정확도를 유지하면서 1000만 개 이상의 점으로 구성된 점 세트를 등록할 수 있습니다.

대응 공간(SCS) 정렬

이 알고리즘은 2013년 H. Assalih에 의해 음파 탐지 이미지 ^[44]등록을 수용하기 위해 도입되었습니다.이러한 유형의 이미지에는 노이즈의 양이 많은 경향이 있으므로 일치시킬 점 집합에 특이치가 많을 것으로 예상됩니다.SCS는 특이치에 대한 높은 견고성을 제공하며 특이치가 있는 경우 ICP 및 CPD 성능을 능가할 수 있습니다.SCS는 고차원 공간에서 반복 최적화를 사용하지 않으며 확률적 또는 스펙트럼적이지 않습니다.SCS는 강성 변환과 비강성 변환을 일치시킬 수 있으며 대상 변환이 3에서 6 사이의 자유도일 때 최상의 성능을 발휘합니다.

「 」를 참조해 주세요.

• 점 피쳐 매칭
• 점 세트 삼각 측량
• 정규 분포 변환

레퍼런스

외부 링크

• 박판 스플라인 로버스트 포인트 매칭의 기준 구현
• 커널 상관점 집합 등록 참조 구현
• 일관성 있는 포인트 드리프트의 기준 구현
• ICP 변종 참조 구현
• 베이지안 코히런트 포인트 드리프트의 기준 구현