Rigid 3D Pointcloud Resgistration Algorithms[1] - PCA

지금 연구하고 있는 논문의 주제에서 밀접한 관련이 있는 알고리즘이다. 하나의 물체를 여러 방면에서 보았을 때의 pointcloud들을 구하였다고 했을 때, 이 pointcloud를 하나로 통합하는 과정에서 필요한 알고리즘이 3D Pointcloud Registration Algorithm이다. 사실 내가 해야하는 부분은 삼차원 자료에 대해 서로간의 Affine Transformation을 구하여야 하는게 맞지만 처음 접근하는데 있어서 Affine부터 시작하려면 어려우니까... 일단 Rigid Transformation 부터 이해한 후 Affine에 대해 알아보려고 한다.

일단은 처음 좌표계를 통합하기위해 수식을 세우려고 이리저리 자료도 찾고 논문을 찾아보려는데 이와 관련된 논문들의 제목에 전부 Registration이라는 단어가 들어가 있는 것이다. 어 뭐지..내가 알고 있는 Registration은 사전적인 의미로 '등록'이라는 영어단어인데, 또 다른 뜻이 있나 해서 영어사전을 찾아봐도 궁금증을 해결해 주는 답이 나오지 않았다. Pointcloud를 등록? 어디다 등록하지? 등록하는 알고리즘이 뭐지?? 라고 이리저리 구글링을 한 결과 Image registration이라는 위키피디아에 설명이 되어 있었다.

Image registration is the process of transforming different sets of data into one coordinate system
출처: https://en.wikipedia.org/wiki/Image_registration

한마디로 Image registration은 다른 집합에 있는 데이터들을 하나의 좌표계로 변환하기 위한 과정. 비록 이거는 이미지에 대해 2D 변환관계를 설명한 위키지만 3D에서도 똑같겠지 뭐..

Rigid 3D Pointcloud Registration Algorithm

일단 나는 지금 AMBIENT 2014에서 발표된 A Survey of Rigid 3D Pointcloud Registration Algorithms(doi: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.251.2708) 이라는 논문을 바탕으로 이글을 쓰고 추가적으로 이해가 가지 않는 부분은 다른 논문을 인용할 생각이다. (이 학회이름은 처음 들어보지만 찾아보니 이 conference에서 Best paper award까지 받은 논문임..오...)

여기서는 최신기술의 Registration algorithm들을 리뷰하였는데, Principal Component Analysis(PCA), Singular Value Decomposition(SVD), Iterative Closest Point(ICP)를 설명하고 비교하였다. PCA는 학부나 대학원 수업에서도 많이 접했었고 ICP는 같은 연구실의 선배가 종종 설명해 주셔서 자세하게 이해는 못했지만 이름이라도 알고 뭐하는 건지는 대충 알고 있었는데, SVD는 처음 보는 알고리즘이었다.(OpenCV에 관련 함수가 있는건 봤었지만 대체 이게 뭔지는 몰라) 대충 찾아보니 어려워.... 그래서 이번기회에 이 세개를 완벽히 공부해야겠다.

1. Principle Component Analysis(PCA)

PCA는 처음 Image processing 시간에 얼굴 인식을 배울때 처음 들었던 것 같다. 그 이후에도 주로 PCA를 접할 때에는 얼굴인식에서 많이 들었었는데, 뭐 처음엔 Eigen face가 어쩌니 Covariance matrix가 뭐니 하면서 배웠었는데 사실 그땐 시험을 보기 위해 달달 외웠으니 당연히 의미는 이해도 못하고 시험을 마친 후엔 까먹은 것이 당연... 그나마 대학원에 진학한 후 세미나를 들었을 때 의미를 이해했던 것 같다.

PCA는 주로 dataset이 있을 때 얼굴인식과 같이 Classification을 하는데 사용되거나, 차원을 수를 줄여 데이터의 크기를 줄이는 Compression을 하는데 많이 사용되는 방법이다. PCA 알고리즘의 주요 기법은 어떤 Dataset의 분포를 가장 잘 표현하는 주 성분을 찾는 것이다. 예를 들어 이차원에서의 어떤 데이터가 아래 그림과 같이 있을 때 이 분포를 가장 잘 나타내는 주축은 e1과 e2일 것이다. 

주성분을 찾기 위해 먼저 필요한 것이 Covariance matrix이다. Covariance matrix는 여러 벡터들의 각 성분들마다의 관계를 나타낸 행렬을 말한다. 그러니까 Covariance matrix의 (2, 3)좌표에 해당하는 값은 2번 데이터와 3번 데이터가 얼마나 상관있느냐 정도가 값으로 표현 되어 있는 것이다.

*Covariance Matrix 
1) 데이터들의 평균(Mean)
$$\boldsymbol{\bar{x}}=\frac{1}{n}\displaystyle\sum_{i=1}^{n} \boldsymbol{x}_i$$
2) Covariance matrix
$$\boldsymbol{C}_x=\frac{1}{n-1}\displaystyle\sum_{i=1}^{n}{(x_i - \bar{x}) (x_i - \bar{x}) ^T}$$
3) Eigenvector와 Eigenvalue 구하기
여기서 말하는 Eigenvector는 데이터들의 분포를 표현할 수 있는 축들을 나타낸 것이고, 각 Eigenvector에 해당하는 Eigenvalue는 Eigenvector의 scale정도라고 할 수 있겠다. 그러니까 Eigenvalue가 큰 Eigenvector일 수록 그 분포를 잘 표현하는 주축이라고 할 수 있는 것이다. PCA에서는 어쨋든 그 분포를 가장 잘 나타내는 주축을 찾는 것이 목적이니까 결국에는 Covariance Matrix에서 Eigenvalue와 Eigenvector들을 뽑아낸 다음 Eigenvalue가 가장 큰 순서대로 Eigenvector들을 표현하면 된다.
Eigenvalue와 Eigenvector를 구하는 문제는 다음 포스팅에....(언젠간 하겠지)

자 그렇다면 다시 원 문제로 돌아가서, 우리가 풀어야 하는 문제는 삼차원 데이터들(Pointcloud) Set이 있을 때 서로 다른 두 Set을 어떻게 하나의 좌표계로 통합하느냐하는 문제이다. 여기서 PCA를 사용한다면 각각의 Pointcloud를 대표하는 좌표축(x, y, z) 세개의 축이 나온다. 비슷하게 생긴 Pointcloud를 정합하는 문제이기 때문에 이 좌표축이 pos만 다르다고 가정한다면 Target Pointcloud의 Eigen vector들을 Source Pointcloud의 Eigen vector로 Align 하는 함수만 만들어 주면 되는 것이다. (응? 생각보다 간단한 아이디어였음..)

그렇지만 내가 생각해도 이 방법은 Correspondence 정보를 사용하지도 않고 각 Pointcloud의 분포가 정확하게 일치하지 않는 이상 Eigenvector들도 완벽하게 일치하지 않을 것이라 생각된다. 그러니까 정확하지 않은 데이터를 가지고 align을 한들 결과가 정확할까라는 생각이 들었다.

SVD와 ICP는 다음 포스팅에 이어서...