PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation[1]

이번에 포스팅할 논문은 2017년 CVPR에 발표된 PointNet이라는 제목의 논문을 리뷰하겠습니다. PointNetVLAD 논문의 핵심이 되는 개념으로 3D Point Cloud 데이터를 신경망의 학습 데이터로 사용하기 위한 문제점들을 해결한 방법론입니다. 해당 논문이 발표된 이후로 3D 데이터를 사용하는 딥러닝 방법론들의 baseline이 된 것으로 알고있습니다. 논문에서 제안하는 모델이 워낙 간단하기 때문에 논문도 모델의 구성보다는 모델의 이론적인 배경과 모델을 사용한 다양한 응용의 결과 위주로 구성되어있습니다. 너무 자세한 수식의 증명은 생략하고 모델을 설명하는 정도의 수식과 이론을 통해서 논문을 살펴보겠습니다.

---

Abstract 

3D 데이터의 불규칙적은 특성 때문에 많은 연구자들이 3D Voxel 혹은 여러 이미지들의 형태로 3D 데이터를 변환하여 사용합니다. 논문에서 제안하는 PointNet은 3D 데이터 중에서도 가장 많이 활용되는 3D Point Cloud 데이터를 Object Classification, Part Segmentation, Scene Semantic Parsing등을 위한 신경망 모델에 사용하기 위해 문제점들을 해결합니다. 즉 3D Point Cloud의 feature를 효과적으로 학습할수 있는 딥러닝 모델을 제안합니다.

 

논문에서 제안하는 PointNet는 구조가 정말 간단하기 때문에 논문은 모델의 구성이나 Lossfunction 보다는 모델을 구성하는 이론적인 이해와 실험적인 이해의 측면을 강조합니다. 크게 두가지 포인트가 있습니다. Permutation invariance과 Translation invariance인데요 이 두가지를 중점으로 리뷰를 해보겠습니다.

---

Introduction

기존의 Convolutional Architecture들은 weight sharing과 kernel 최적화등의 이유로 2D 이미지 혹은 3D Voxel 형태의 regular한 데이터를 입력으로 사용했었습니다. 3D Point Cloud는 irregular한 데이터 특성 때문에 2D 이미지 혹은 3D Voxel 형태로 변환해서 사용하였고 이는 불필요하게 커다란 형태로 표현되거나 정보의 손실이 발생했습니다. 

 

이러한 문제점들을 해결하기 위해 저자들은 3D Point Cloud를 변환하지 않고 directly하게 입력으로 사용하는 신경망 모델PointNet을 제안합니다. key contribution은 다음과 같습니다.

 

• 정렬되지 않은(unordered) 3D Point Cloud 데이터를 위한 Deep Net Architecture 제안
• 제안한 Architecture를 이용한 3D Shape Classification, Shape part segmentation, Scene Semantic Parsing의 성능
• stability와 efficiency 측면에서 실험적 그리고 이론적인 분석
• 3D feature을 시각화하고 Architecture의 성능을 직관적으로 설명

---

Related Work

관련연구는 3D 데이터를 사용한 딥러닝과 Unordered 데이터를 사용하는 딥러닝 크게 두가지로 나눌수 있습니다.  앞서 언급했듯이 3D 데이터를 이용해 딥러닝에 적용시키려는 시도는 입력 데이터의 특성상 3D 데이터를 3D Voxel 혹은 2D 이미지의 형태로 변형해서 사용하였는데 이는 computation cost와 데이터의 sparse volume 문제, 범용성 문제, feature representation power 문제등 데이터의 크기와 정보의 손실에 의해 일어나는 여러가지 문제점들이 있습니다. 또한 Unordered 데이터를 사용하는 딥러닝 연구가 거의 이루어 지지 않았습니다.

---

Problem Statement

Point Cloud는 3D point들로 표현됩니다. $\{ P_i |\ i = 1, ..., n\}$, $P_i$는 각각 $(x,y,z)$ 좌표 정보를 가지고 있습니다. Object Classification에서는 Point Cloud를 입력으로 $k$개의 class에 대해 $k$개의 점수를 출력합니다. Sementic Segmentation에서는 한개의 Object 혹은 3D Scene의 일정 부분이 입력으로 사용되고 $n$개의 point들에 각각 $m$개의 semantic subcatergories 점수를 출력합니다.

---

Deep Learning on Point Sets

PointNet Architecture

그림은 PointNet Architecture의 구조를 표현합니다. 입력으로 사용되는 Point에 대해 설명하면서 입력 데이터가 갖는 문제점들을 시사합니다. 

 

1. Unordered.

첫번째로 Point들은 정렬되어있지 않습니다. 이미지의 픽셀 배열이나 Volumetric grid의 Voxel 배열과 다르게 Point Cloud는 Point들의 집합으로 이루어져 있어 명확한 정렬이 없습니다. 다시말해 Point Cloud를 입력으로하는 Network는 $N$개의 Point들을 입력으로 사용할때 $N!$개의 순열(permutation)이 생기고 연산의 결과가 입력 순서에 불변해야 합니다.

 

 

Point Cloud를 구성하는 Point에는 순서가 없기 때문에 그림의 왼쪽 데이터와 오른쪽 데이터는 같다는 뜻입니다.

 

2. Interaction among points

두번째로 Point들은 distance metric 공간에 있습니다. 이것은 Point들이 독립적으로 의미를 갖는것이 아니라 근접한 Point들과 Subset으로 구성됨에 따라 의미를 갖는다는 것을 뜻합니다. 이를 local feature라고 합니다. 따라서 모델은 인접한 Point들의 local structure를 학습해야하고 또한 local structure들 사이의 결합도 학습해야 합니다.

 

3. Invariance under transformations.

마지막으로 기하학적인 Object로써 Point set의 학습된 표현(learned representation)은 특정한 변환에 대해 불변해야합니다. 예를 들어서 Point 전체에 대한 회전 변환이나 이동 변환은 global Point Cloud의 category나 Point들의 segmentation을 변화시키지 않습니다.

 

입력 데이터가 갖는 3가지 문제를 해결할수 있는 모델을 그림과 같이 제안하였고 모델을 구성한 이유를 이론적인 근거를 통해 설명합니다.

---

Symmetry Function for Unordered Input

모델을 입력 데이터의 permutation에 불변하도록 하는 전략은 3가지가 있습니다 1) 입력 데이터를 canonical order로 정렬하는 법 2) 입력 데이터를 RNN을 통해 sequence하게 학습하고 이때 입력 데이터가 가질수 있는 모든 permutation에 대해서 같은 결과가 나오도록 학습하는 법 3) 각각의 Point의 정보를 통합하는 symmetric function을 사용하는 법. 여기서 canonical order는 정규 형식 또는 표준 형식을 따르는 정렬방법을 의미하고 어떠한 특정한 정렬 알고리즘을 뜻하지는 않습니다. symmetric function의 예로는 입력의 순서에 상관없이 일정한 결과를 출력하는 더하기(+) 연산과 곱하기 연산(x)이 있습니다.

 

입력 데이터를 canonical order로 정렬하는 법이 쉬운 해결책으로 보이지만 높은 차원의 경우 stable한 정렬방법이 존재하지 않습니다. 예를 들어 $(x,y,z)$ 3차원으로 이루어진 Point 데이터를 일정한 기준으로 정렬한다는 것은 3차원 데이터를 1차원으로 mapping 하는 방법이 존재한다는 뜻이고 차원의 감소에 의해 일반적으로는 이루어질수 없는 방법입니다. 저자들은 정렬된 Point set을 통해 실험했을때 정렬되지 않은 Point set과 비교하여 아주 약간의 성능 향상이 이루어졌다고 나타냅니다.

 

RNN을 이용해 학습하는 경우를 생각해 보겠습니다. Point set의 permutation에 따라 다양한 sequence를 학습하게 되면 RNN이 입력 순서에 불변성을 갖을수 있을것으로 예상할수 있습니다. 하지만 RNN은 sequence가 Point Cloud에 비해 상대적으로 작은 수십개 정도일때 강력한 성능을 발휘하지만 평균적으로 수천개 혹은 수만개로 이루어진 Point Cloud의 경우 학습하기 매우 어렵습니다. 이또한 RNN을 기반으로한 모델을 실험하였고 논문에서 제안한 PointNet에 비해 떨어지는 성능을 보입니다.

 

논문은 마지막 전략 symmetric function을 통해 문제를 해결합니다. 메인 아이디어는 다음의 수식과 같이 symmetric function을 적용하여 일반 함수를 근사하는 방식을 사용하는 것입니다.

 

$ f( \{ x_1, ..., x_n\}) \approx g(h(x_1), ..., h(x_n))$

 

$ f : 2^{\mathbb{R}^N} \rightarrow \mathbb{R}$, $ h : \mathbb{R}^N \rightarrow \mathbb{R}^K $ and $ g : \mathbb{R}^k \times \cdots \times \mathbb{R}^K \rightarrow \mathbb{R}$

 

$h$는 $N$차원 벡터를 $K$차원의 벡터로 Mapping하는 함수입니다. 현재 다루고 있는 데이터에서는 3차원의 Point를 $K$차원의 벡터로 mapping하는 함수라고 할수 있고 $h$에 의해 출력되는 $\mathbb{R}^K$를 Point 한개에 대한 local feature라고 볼수있습니다. $g$는 symmetric function입니다. $g$의 입력으로 사용되는 $h(x_1)$, $h(x_3)$, $h(x_n)$들의 순서가 바뀌어도 출력이 일정합니다. 즉 $n$개의 Point들로 이루어진 데이터의 Subset을 입력으로 사용하는 일반함수 $f$를 함수 $h$와 $g$를 사용하여 근사합니다. $h$는 multi-layer perceptron network(MLP)를 사용하여 근사할수 있고 $g$는 max pooling을 사용하여 근사합니다.

 

모델의 구조도에서 Input Points $ (n \times 3)$는 $(x,y,z)$로 이루어진 3차원 Point가 $n$개라는 의미입니다. 그리고 이 Point들이 Input Transform과 MLP 그리고 Feature Transform을 거쳐 $(n \times 1024)$의 Feature로 바뀌게 됩니다. 결국 각각의 Point에 대해서 3차원의 정보를 1024차원의 정보로 확장했다는 의미로 해석할수 있습니다. 이 부분이 수식에서 $N$차원의 벡터를 $K$차원의 벡터로 Mapping하는 함수 $h$ 라고 볼수 있겠습니다. Symmetric 함수 $g$는 $(n \times 1024)$를 입력으로 하는 Max Pooling에 해당합니다.

---

Local and Global Information Aggregation

수식 $ f(\{x_1, ..., x_n\}) \approx g(h(x_1), ..., h(x_n))$ 의 입력이 Subset이기 때문에 집합 $\{x_1, ..., x_n\}$으로 만들수 있는 Subset중 $K$개를 입력으로 사용할 경우 출력은 $f_1, ..., f_K$로 총 K개의 실수가 됩니다. 이를 벡터 형태 $[f_1, ..., f_K]$로 구성하고 $n$개의 Point에 대한 global feature라고 합니다. 모든 Point에 대한 global feature를 벡터 형태로 나타낼수 있으므로 이를 이용해서 SVM이나 MLP를 통해서 간단히 Classification을 수행할수 있습니다. 하지만 Segmentation은 local feature와 global feature를 모두 필요로 하기 때문에 그림에서 볼수있듯이 Classification Network의 local feature와 global feature를 병합하여 Segmentation Network의 입력으로 사용합니다.

PointNet Architecture

이 방법을 통해서 Network가 Point의 지역적인 정보를 학습할수 있습니다. 실험적으로도 Segmentation 분야에서 state-of-the-art 성능을 보여줍니다.

---

Joint Alignment Network

앞서 언급했던 3가지의 문제중 1. Unordered와 2. Interaction among points는 함수 $h$와 $g$를 이용해 함수 $f$를 근사하는 방법으로 해결했습니다. 3. Invariance under transformation 문제는 Affine Transformation을 추정하는것으로 해결합니다. Affine Transformation은 벡터 공간에서 직선과 평행을 보존하는 변환을 뜻합니다. 모델의 구조도에서 Input Transform과 Feature Transform에 해당하는 Mini-Network 부분입니다. 모델이 추정하는 Affine Transformation은 입력 Point를 Canonical Space의 한 Point로 변환하는 역할을 합니다. Canonical Space란 표준 공간으로 Affine Transformation을 통해 Point를 Canonical Space의 Point로 변환한다는 것은 Point들 간의 직선성과 평행성을 보존하면서 정규화된 공간으로 옮긴다는 것으로 이해했습니다. 다시말해 Point가 위치하는 공간에 대한 정보는 Transformation에 의해 변화할수 있는것이지만 Point들간의 관계에 대한 정보는 Transformation에 의해 변화하지 않기때문에 Classification이나 Segmentation을 수행할때 Transformation에 의해 변화하지 않는 정보를 활용하기 위함으로 보입니다.

mini network

논문에서는 이러한 Affine Transformation matrix를 추정하는 Network를 T-Net이라고 부르며 T-Net 또한 전체 Network와 유사하게 MLP와 Max Pooling으로만 구성되어 있습니다. 이러한 과정을 Point를 Alignment하는 Transform이라고 표현합니다. 유사한 방식으로 Local Feature에도 Alignment를 적용합니다. 

feature transform

Feature의 크기에 따라 Input Transform의 경우 3 x3 Matrix를 근사하였고 Feature Transform은 64 x 64 크기의 Matrix를 근사합니다. 하지만 Feature Transform에서 근사하는 Matrix의 경우 크기가 64 x 64로 Input Transform의 Matrix에 비해 차원이 엄청나게 높기 때문에 Optimization하기에 어렵습니다. 따라서 Feature Transform의 Matrix를 $A$라고 하고 다음과 같은 수식으로 Loss Function을 설정하여 제약을 둡니다.

 

$L_{reg} = \left\Vert I - AA^T \right\Vert_F^2$

 

Matrix A가 직교행렬이 되도록하는 Loss Function입니다. 직교행렬의 정의에 의해 각 행벡터와 열벡터의 크기가 1이 되므로 Matrix를 구성하는 원소들의 범위가 제한적입니다. Input에 대한 Alignment, Feature에 대한 Alignment 총 두번의 Alignment를 거치므로 Transformation에 더욱 Invariant한 모델을 학습합니다.

 

여기까지 모델의 구조도를 통해서 3D 데이터의 정보를 효율적으로 학습하기 위해 3D 데이터를 딥러닝에 적용할때 발생하는 3가지 문제점을 해결하는 딥러닝 Architecture를 살펴봤습니다.  다음 포스팅에서는 모델의 이론적인 분석과 모델의 Classification, Segmentation 결과를 간단하게 리뷰하겠습니다.

 

[참고자료]

[1] C.R.Qi, H.Su, K.Mo and L.J.Guibas. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In Proc. CVPR, 2017.

[2] Affine transformation

[3] cvpr17_pointnet_slides

[4] PointNet(-ing)