적은 오버랩에서 사용 가능한 3차원 점군 정합 방법

3차원 공간상의 물체에 대하여 카메라로 어느 한 방향에서 점군 (point cloud) 데이터를 얻는다면, 획득한 데이터는 자체적으로 지역 좌표계 (local coordinate system)를 가진다. 하지만 하나의 데이터만을 획득하는 것으로는 물체에 대한 모든 정보를 알 수 없다. 그래서 그 물체에 대해 각기 다른 여러 방향에서 데이터를 얻는 다. 그리고 이 데이터들을 원래 물체처럼 하나로 나타내기 위해 하나의 전역 좌표계(global coordinate system)로 표현한다. 이렇둣, 여러 점군 데이터의 여러 지역 좌표계를 점군 데이터 세트 하나의 전역 좌표계로 표현하는 과정을 정합이라고 한다[1].

정합은 점군 데이터의 개수에 따라, 데이터가 둘이면 이중 정합(pairwise registration), 셋 이상이면 다중 정합(multiview registration)으로 구분할 수 있다. Besl은 알고리즘의 우수성을 입증하기 위한 수단으로 점 (point set)과 곡선 (curve)과 면 (surface) 에 대하여 각각 이중 정합을 수행하였다[3]. 또, Lee는 멀티 센서를 정합에 충분히 활용할수 있음을 보이기 위해 센서들을 부착한 스캐너로 빌딩 외부를 실제로 스캔하였고 이렇게 획득한 점군들로 이중 정합을 완료하였다[4]. 반면, Pulli는 미켈란젤로의 다비드 조각상을 스캔하고 다중 정합을 진행하기에 앞서 이중 정합을 먼저하고 난 뒤 이를 다중 정합의 제약(constraint)으로 적용하였다[5]. 최근에는 Yun은 선체의 블록을 조립하는 조선 현장에서 스캔한 15개의 점군들로 다중 정합을 수행하였다[6]. 본 논문에서는 다중 정합을 고려하지 않은 채 이중 정합만을 다룬다.

m_a개의 점을 포함하는 소스 점군(source point cloud) A를 m_b개의 점을 포함하는 타갯 점군(target point cloud) B에 정합한다고 가정하자. 이 때 ICP 알고리즘은 그림 2처럼 여섯 단계로 이루어져\ 있으며, 각 단계는 다음과 같이 요약할 수 있다.

Figure 2: The Flowchart of Classical Iterative Closest Point(ICP) algorithm [3]

Download Original Figure

첫째, 점 선택(point selection) 단계에서는 알고리즘의 계산량을 줄이기 위하여 노이즈 필터링이나 샘플링을 거쳐 점의 갯수를 줄인다. 둘째, 이웃 선택(neighborhood selection) 단계에서는 각 점의 주변에 분포하는 점들 중 가까운 점 일부를 선택한다. 셋째, 점쌍 매칭(point pair matching) 단계에서는 앞서 선택한 주변 점들로 곡면(surface)[6]이나 평면(plane)[7] 같은 기하학 요소를 만들고, 이를 이용하여 소스 점군 A의 점 에 대응하는(corresponding) 타갯 점군 표의 점을 찾는다. 넷째, 오정합점 제거 (outlier rejection) 단계에서는 소스 점군 A와 타겟 점군 B에서 서로 겹치는 부분, 즉 오버랩 영역(inlier)만 남기고, 겹치지 않는 영역(outlier) 은 정합에 이용하지 않는다. 다섯째, 오차 최소화(error minimization) 단계 에서는 소스 점군 A의 오버랩 영역 A′과 타겟 점군 B의 오버랩 영역 B′ 방향으로 이동하는 동안 각 대응점의 거리 오차가 최소가 되도록 한다. 여섯째, 변환(Transformation) 단계에서 는 소스 오버랩 점군 A′가 타갯 오버랩 점군 B′의 위치로 이동하 는 데에 필요한병진 행렬(translation matrix)과 회전 행렬(rotation matrix)을 구하여 소스 오버랩 점군 A′에 적용한다. 여기서 거리 오차가 일정한 한계치(tolerance, τ) 이하이면 진행을 멈주고 한계치 이상이라면 점쌍 매칭 (point pair matching) 단계로 되돌아가서 알고리즘을 다시 수행한다.

이러한 ICP 알고리즘은 병진 3자유도와 회전 3자유도를 다루기 때문에 공간상의 모든 방향으로 적용할 수 있는 것은 물론, 점군 데이터의 국소 특징(local feature)이나 전처리(prepocessing)가 필요 없기 때문에 알고리즘이 비교적 간단하다는 장점을 가지고 있다[3]. 하지만 점쌍 매칭 단계에서 대응점 (corresponding point)을 찾는 과정이 알고리즘 1회 수행하는 데에 최대 O(m_am_b)의 복잡도를 보이는데다가, 오버랩 영역이 매우 적거나 없어 분할된 상태의 점군에 적용하면 정합이 잘못되는 경우가 허다하다[3]. 또, 성게처럼 형상이 복잡하거나[3] 사무용 건물 같이 반복되는 패턴의 경우에도 알고리즘을 적용하기 어렵다.

Besl은 회전 행렬을 구하는 데에 Horn의 최소 자승 사원수 연산(least square quaternion operation)[8]을 이용하여 변환 단계에 적용하였다[3]. 반면, Masuda는 오정합점 제거 단계에서 잔차의 표준 편차(standard deviation of residuals)를 도입하여 이 값의 2.5 배를 거리 임계값(distance threshold)로 설정하였다. 이 때 임계값 이하이면 정합점 (inlier)으로, 초과하면 오정합점 (outlier)으로 구 분하였다[9]. 여기서 Masuda는 샘플링이 일정하지 않은 무작위 샘플링(random sampling)을 사용한 반면, 본 논문에서는 균일 샘플링 (uniform sampling)을 사용하였다. 한편, Pulli는 점쌍 매칭 단계에서 정적 임계값(hard threshold) 내에서 대응점을 찾되, 각 점 군의 법선 벡터(compatible normal vector)의 사잇각이 45도 이하 이고, 대응점이 메시 경계(mesh boundary) 위에 있지 않는다면 오버랩 영역에 해당하는 동적 임계값(dynamic threshold)을 유지한 채 매칭 대칭(matching symmetric)을 만드는 경험적인(heuristic) 방법을 제안하였다[5]. 그러나 임계값들을 조절하며 많은 시행착오를 거쳐야 하기 때문에 원하는 정합을 얻기까지 오랜 시간이 걸린다는 단점을 안고 있다.

점군 정합은 경계 부분에서 이뤄진다는 Wu의 가정[10]을 사용하여 경계 부분의 점만 샘플링하고 나머지 점들은 제거한다. 이러 한 샘플링 단계에서 필요한 것이 적당한 경계점을 찾는 것이다. 본 논문에서는 경계점을 적절히 결정하는 데 있어서 기존의 방법 [10]과 차이를 두었다. 더불어 2.2절에서처럼, 정합을 하는 데 있어서 정합을 위해 움직이는 점군을 소스 점군 A로, 소스 점군 A의 정합에 최종 목적지가 되는 점군을 타겟 점군 B로 명명한다.

그림 3은 샘플링 과정을 나타낸다. 먼저 점군의 테두리에 있는 경계점을 각도 10도씩의 차이를 주며 36개를 선택한다. 그리고 그림 3와 같이 점군에서 2차 곡면과 각 축의 주성분(principal components)을 계산하고, Y축과 Z축로 이루어진 YZ평면을 만든 다. 그리고 아래의 순서를 통해 점군 L을 이루는 점을 선택한다.

Figure 3: Selecting points of point cloud L

Download Original Figure

Wu는 0.9D 거리에 있는 점을 적당한 경계점으로 선택했는데, 이 때 D는 원점 O에서 최대 경계까지의 거리이다[10]. 하지만 실제로 스캔한 물체 주변의 배경에는 노이즈가 존재한다. 이런 상황에서\ Wu의 방법을 사용한다면 0.9D 거리에 있는 점은 스캔한 물체의 경계점이 아니라 배경의 노이즈일 확률이 높다. 그러나 노이즈 필터링을 통해 배경의 노이즈를 제거하고 난 뒤 0.9D 대신에 0.9n을 이용한다면 점들의 밀도가 높은 부분, 즉 스캔한 물체의 점군 안에서 적당한 경계점을 선택하게 된다. 그러므로 본 논문 에서는 0.9n 번째에 해당하는 36개의 점들로 점군 L을 구성하였다. 한편, 타갯 점군 B의 오버랩 부분을 모르므로, 균일 샘플링 (uniform sampling)을 수행한 결과로 점군 U을 구성하였다.

위와 같이, 소스 점군 A로부터 찾은 경계 점군 L과, 타갯 점군 B로부터 균일 샘플링된 점군 U를 구성한 뒤에는, 곡률을 이용하여 오버랩을 찾는다. 먼저 가우시안 곡률(Gaussian curvature, K) 과 평균 곡률(mean curvature, H)을 계산한다. 그리고 표 1의 분류를 이용하여 서로 다른 종류를 가진 점의 쌍을 제거한다. 이 때, 오버랩을 찾는 데에 악영향을 끼치는 평판 요소도 제거한다.

L과 U에서 남은 점을 각각 p, q라 명명하고, 아래의 식을 만족하지 못하는 (p, q) 쌍을 제거한다.

이때, ϵ₁, ϵ₂은 곡률 임계값(curvature threshold)이다.

마지막으로, 남은 점군 쌍에 zncc(zero mean normalized cross correlation) 방법을 활용하여 이웃한 점 들의 곡률 매칭 (neighborhood curvature matching)을 수행한다[13].

zncc는 포괄적인 이웃 곡률 매칭 지수(comprehensive neighborhood curvature matching degree)이고,${\overline{k}}_1$과 ${\overline{k}}_2$은 k-최근접 이웃 알고리즘(k-nearest neighbor search, k-NN) 으로 얻은 이웃점의 주곡률(principal curvature) 평균이다. 방정식 (1)과 방정식 (2)를 적용한 이후 쌍이 없는 점군 L의 점은 zncc를 0으로 놓는다. 점군 L의 각각의 점에 대해 zncc가 가장 높은 점의 쌍을 선택한다.

zncc는 오버랩 영역을 찾는데 사용된다. zncc의 값이 1보다 큰 점쌍의 개수를 묶는 사슬을 만든다. 그리고 그림 4와 같이 사슬을 구성하는 점 zncc 합이 가장 큰 사슬을 이용하여 O-XYZ 공간을 만들고 O와 사슬을 이어 오버랩 영역을 찾는다. 소스 점군 A의 이러한 오버랩 영역을 소스 오버랩 점군 A′ 으로 명명한다. 이 과정을 타갯 점군 B에도 적용하여 타갯 오버랩 점군 B′을 결정 한다.

Figure 4: Overlapping Region

Download Original Figure

Li의 가속화 방법[11]은 낮은 오버랩의 상황에서는 활용할 수 없다. 하지만 앞서 진행한 샘플링 기법을 적용하면 90% 이상으로 오버랩이 증가하게 된다. 그래서 본 논문의 가속화 기법은 낮은 오버랩에서도 적용할 수 있는 범용성을 가진다. 가속화를 적용하는 순서는 다음과 같다.

위 과정을 d_j,i − d_j+1,i < τ 이 만족될 때까지 반복한다. d_j,i는 j번 반복했을 때의 소스 점군 A와 타갯 점군 B 간의 제곱평균 제곱근 오차(RMSE)이며 τ는 한계치 (tolerance)이다. 위 과정에서 회전행렬 R_j,i과 병진행렬 T_j,i는 점대평면(point-to-plane)을 기반으로 구하되[7], 사원수(quaternion)를 이용하예[8] 회전행렬 R_j,i을 구한 다음에 병진행렬 T_j,i사를 구하였다. 회전행렬 R_j,i과 병진행렬 T_j,i사를 구하는 식은 다음과 같다[8].

이 때, q₀, q_x, q_y, q_z는 사원수 $Q=q_0+\widehat{i}{q}_x+\widehat{j}{q}_y+\widehat{k}{q}_z$ 에 대한 실수부 (real part) 와 허수부 (imaginary part) 이다. 또, ${\overline{A^{\prime }}}_{j-1}$ 와 ${\overline{B^{\prime }}}_{j-1}$는 각각 소스 오버랩 점군 A′과 타켓 오버랩 점군 B′를 구성하는 점들의 평균 좌표값이며, 이는 각 점군의 중심 (centroid)을 의미한다.

한편, δR과 δT는, j번째 회전 및 병진 행렬인 R_j,i과 T_j,i를 적용 하여 단 한 번의 반복횟수(iteration)로 오버랩 점군 A′을 이동시킨 뒤에 그 자리에서 다시 구한 회전 및 병진 행렬로써, (j+1)번째 반복횟수의 회전 및 병진 행렬인 R_j+1,i 및 T_j+1,i과는 다르다.

앞서 사용한 세가지 점군 데이터를 가지고 가속을 적용하기 적용하기 전과 후를 비교하였다. 모든 경우에 대하여 제곱평균제곱근 오차(RMSE)는 거의 변하지 않았지만 반복횟수가 많이 줄어 들었다. 표 5 에 따르면, 기존보다 토끼는 1/3배, 부처는 1/2배, 아르마 딜로는 1/5배로 줄어든 것을 확인할 수 있다.

제곱평균제곱근 오차(RMSE)의 값이 커보이지만, 이 오차는 레퍼런스(reference)에 대한 오차가 아니라, 오차를 계산하는 과정에서 노이즈와의 오차가 포함되었기에 이러한 결과가 나온 것 이다. 레퍼런스와 비교해도 위 점군 데이터들은 정합이 잘 된 것이고, 시각적으로도 확인할 수 있다.