[논문 리뷰] PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation

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

https://arxiv.org/pdf/1612.00593

 

 

0. Abstract

 Point cloud는 geometric data structure에서 중요하다. 불규칙적인 형태때문에 대부분의 연구자들은 3D voxel grid나 collection으로 데이터를 변환한다. 그러나 render된 데이터는 불필요하게 방대하고 문제를 일으킨다. 저자들은 point cloud를 바로 사용하는 novel type을 디자인한다. 이는 입력 point의 불변성을 잘 반영한다. PointNet은 scene semantic parsing부터 object classification, part segmentation까지 통합된 아키텍처를 제공한다. 간단하게 PointNet은 굉장히 효율적이고 효과적이다. 특히 최신 기술보다 나은 performance를 보여준다. 이론적으로 저자들은 PointNet이 학습한 것과 입력의 perturbation, corruption으로부터 견고한 이유를 설명한다.

 

1. Introduction

 point cloud나 mesh와 같은 3D geometric data에서 추론할 수 있는 딥러닝 아키텍처에 대해 살펴보자. 특정 convolutional 아키텍처는 weight sharing과 kernel optimization하기 위해 image gird나 3D voxel같은 규칙적인 입력 데이터 format이 필요하다. point cloud나 mesh는 규칙적인 format이 아니기 때문에, 많은 연구자들은 딥러닝 네트워크 아키텍처에 넣기전, 3D voxel grid나 collection of image(e.g, view) 같은 데이터로 전환한다. 하지만, 이런 전환된 representation은 불필요하게 방대하게 render된다. 또한 데이터의 자연스러운 불변성을 모호하게하는 quantization artifact가 반영된다. 

quantization(양자화)이란?

실수형 변수(floating-point type)를 정수형 변수(integer or fixed point)로 변환하는 과정으로 모델을 최적화할 수 있다.

 

https://gaussian37.github.io/dl-concept-quantization/

 이러한 이유로 저자들은 point cloud를 이용한 3D geometry의 다른 입력 representation에 집중했다. 이것이 PointNet이다. Point cloud는 간단하고 통합적인 구조로, mesh의 불규칙성과 복잡성을 피할 수 있고 학습하기 쉽다. 그러나 PointNet은 point cloud가 단지 point들의 집합이기 때문에 permutation이 불변한다는 것을 알아야 한다. 따라서 net computation에서 특정 대칭화가 필요하다. 또한, rigid motion의 불변도 고려해야 한다.

rigid motion(강체운동)이란?

변환 이후에도 물체(강체)의 변형이 일어나지 않는 것으로, 변환 이후에도 물체의 모양이나 길이는 유지된다.

 

https://velog.io/@wilko97/3D-Computer-Vision-Lecture-2-Rigid-body-motion-and-3D-projective-geometry

 

 PointNet은 point cloud를 직접 입력으로 사용하는 통합 아키텍처로, 전체 입력에 대한 class label이나 입력의 각 포인트에 대한 per point segment/part label을 출력한다. 기본적인 아키텍처는 간단하며, 각 point가 동일하고 독립적이게 처리된다. 각 point의 기본 설정은 3개의 좌표(x, y, z)로 표현된다. 추가적인 차원은 local이나 global feature과 normal을 계산하여 추가할 수 있다. 

 single symmetric function인 max pooling을 사용하는 것이 key이다. point cloud의  interesting하거나 informative한 point를 선택하고 선택의 이유를 encode하여 최적화 함수/기준을 효과적으로 학습한다. 최종 fully connected layer는 이런 학습 optimal value를 전체 모양에 대한 global descriptor에 모으거나(shape classification) per point label 예측에 사용한다.(shape segmentation)

 각 point가 독립적으로 전환하면서 rigid하거나 affine한 전환에 쉽게 적용할 수 있다. 그래서 PointNet 처리 전에 데이터를 표준화하는 data-dependent의 spartial transformer network를 추가할 수 있다. 이로 인해 결과가 향상 될 수 있다.

 PointNet은 연속적인 모든 집합 함수에서 근사화할 수 있다. 시각화에 따라 대략 object의 skelton에 해당하는 key point의 spare한 집합으로 point cloud 입력을 요약할 수 있다. 이론적인 분석으로 왜 PointNet이 입력의 small perturbation과 point insertion(outliers)나 deletion(missing data)로부터 온 corruption에 robust한지 이해할 수 있다.

 통합 아키텍처에서 PointNet은 최근 모델보다 빠르고 strong하다.

 

3. Problem Statement

 저자들은 순서가없는 point 집합을 입력으로 직접 사용하는 딥러닝 프레임워크를 설계했다. point cloud는 각 point가 color, normal 등과 같은 추가적인 feature channel이 있는 (x, y, z)좌표 벡터인 3D point의 집합이다. 간단하고 명확하게 하기 위해 언급이 없는 한 point channel로 (x, y, z)를 사용한다.

normal란?

표면의 특정 점에서 그 표면에 수직인 벡터

(GPT)

 object classification에서 입력 point cloud는 shape로부터 직접 샘플링하거나 scene point cloud로부터 pre-segment한다. PointNet의 출력 k는 모든 k 후보 클래스에 대한 점수이다. semantic segmentation에서, 입력은 part region segmentation을 위한 single object이거나 object region segmentation을 위한 3D scene의 sub volume이다. 모델은 n*m 점수를 출력하는데 각 n개의 point와 m개의 semantic 하위 카테고리이다.

 

4. Deep Learning on Point Sets

4.1. Properties of Point Sets in Rn

 입력은 유클리드 공간으로부터 point의 subset이다.

- Unordered.

이미지의 pixel array나 volumetric grid에서 voxel array와 달리, point cloud는 특정한 순서가 없는 point집합이다. 다시 말해, N개의 3D point 집합을 사용하는 네트워크는 data를 공급하는 순서에서 입력의 N! 순열에 대해 불변해야 한다. 

- Interaction among points.

point는 distance metric이 있는 공간으로부터 왔다. 이는 point는 고립되지 않고 근처의 point는 의미있는 subset을 형성한다는 것을 의미한다. 그래서 모델은 근처의 point로부터 local structure와 local structure간의 조합적인 상호작용을 포착해야 한다.

- Invariance under transformations.

 geometric object로서 point집합의 학습된 representation은 특정 변환으로부터 불변해야 한다. 예를 들어 회전, 변환하는 모든 것은 global point cloud category나 segmentation을 수정해선 안된다. 

 

4.2. PointNet Architecture

 

 PointNet 아키텍처는 classification network와 segmentation network가 많은 구조를 공유한다. 3개의 key module이 있는데 모든 포인트로부터 정보를 모으는 대칭함수인 maxpooling layer, local, global 정보의 조합구조, 입력 point와 point feature를 정렬하는 2개의 정렬 network이다. 

 

Symmetry Function for Unordered Input

 입력 순열이 불변한 모델을 만들기 위해서 3가지 전략이 있다. 1) 입력을 표준순서로 정렬한다. 2) 입력을 RNN으로 학습하는 sequence로 취급하지만 모든 종류의 순열로 학습 데이터를 증가시킨다. 3) 각 point에서 정보를 모으는 대칭함수를 사용한다. 여기서, 대칭함수는 n개의 벡터를 입력으로 사용하여 입력 순서가 불변하는 새로운 벡터를 출력한다. 예를 들어 +와 *는 대칭이진함수이다.

 정렬하는 것은 쉬운 해결책으로 들리지만, 고차원공간에서 사실상 일반적인 의미에서 point perturbation에 대해 안정적인 순서는 존재하지 않는다. 이는 모순을 통해 쉽게 보여줄 수 있다. 만약 이런 순서전략이 존재한다면, 고차원공간과 1차원 실수선 사이의 bijection map을 정의한다. 

bijection map(전단사 함수)이란?

두 집합 사이를 중복 없이 모두 일대일로 대응시키는 함수

 

 

https://ko.wikipedia.org/wiki/%EC%A0%84%EB%8B%A8%EC%82%AC_%ED%95%A8%EC%88%98

point perturbation에 대해 안정적인 순서를 요구하는 것은 차원축소에서 spatial proximity를 유지해야 한다는 요구와 동일하다. 이 task는 일반적으로 이룰 수 없다. 그래서 정렬은 ordering 문제를 완전한 해결방안이 아니며, ordering 문제가 지속되면 입력으로부터 출력으로 일관된 mapping을 학습하기 어렵다. 정렬된 point set으로 직접 MLP를 적용하는 것은 정렬하지 않은 입력으로 처리하는 것보다 약간 더 나은 성능을 보인다.

MLP(multilayer perceptron)이란?

퍼셉트론을 여러층 쌓은 순방향의 인공 신경망

입력층(input layer)과 은닉층(hidden layer)과 출력층(output layer)으로 구성

각 층에서는 활성함수를 통해 입력 처리

 

https://ko.wikipedia.org/wiki/%EB%8B%A4%EC%B8%B5_%ED%8D%BC%EC%85%89%ED%8A%B8%EB%A1%A0

 RNN을 사용하는 아이디어는 point를 sequential signal로 고려하고 랜덤한 순열 sequence로 RNN을 학습함으로써 RNN이 입력순서에 따라 불변하기를 원한다. 그러나 OrderMatter의 저자는 order은 중요하며 완전히 생략할 수 없음을 보여준다. RNN은 small length sequence의 입력 ordering에 대해 비교적 좋은 robustness를 가지지만, point 집합의 일반적인 사이즈인 수천개의 입력요소에 대해서는 확장하기 어렵다. 또한, RNN 기반의 모델은 저자들이 제시하는 방법만큼 좋은 성능을 보여주지 않는다.

 저자들의 아이디어는 변환된 요소에 대칭함수를 적용함으로써 point 집합에서 정의된 일반함수를 근사하는 것이다.

 기본 모듈은 매우 간단하다. multi-layer perceptron network로 h를 근사화하고 single variable 함수와 max pooling 함수의 구성으로 g로 근사화한다. 이는 실험을 통해 잘 작동하는 것을 확인했다. h 집합을 통해 집합의 다른 속성을 포착하기 위해 여러 f를 학습할 수 있었다.

 key module은 간단해보이지만, 흥미로운 속성을 가지고 있고 몇가지 application에서 좋은 성능을 보여준다.

 

Local and Global Information Aggregation

Local Information / Global Information이란?

데이터에서 특정 지점이 어떤 범위의 정보를 반영하는지에 대한 개념

Local information : 어떤 점이나 객체의 주변 또는 인접한 영역에서 얻을 수 있는 정보

주로 그 점의 근처에 있는 이웃 점들 간의 관계나 패턴을 반영

예) 3D 메쉬의 한 점에서 local information은 그 점의 이웃 점들이나 연결된 면들에서 얻은 기하학적 속성(해당 점의 미세한 형태나 표면의 특성)
한 점의 주변 점들의 위치나 그 점의 인접한 면들에서 유도된 곡률, 노말(normal) 벡터

Global information : 특정 지점이 전체 구조나 전체 맥락에서 어떻게 위치해 있는지에 대한 정보

전체 데이터 세트나 객체의 형태, 패턴 등을 반영
예) 한 점이 3D 메쉬의 전체 형상에서 어떤 역할을 하는지, 그 점이 있는 메쉬가 전체 모델의 어느 부분에 해당하는지 등

위의 section에서 출력은 vector [f1, . . . , fK]의 형태인데, 이는 global signature이다. 우리는 SVM이나 classification을 위한 shape global feature의 MLP classifier를 쉽게 학습시킬 수 있다. 그러나 point segmentation은 local과 global 지식의 조합을 필요로 한다. 이는 간단하지만 매우 효과적인 방식으로 이를 달성할 수 있다.

 global point cloud feature vector를 계산한 후, 각 point feature의 global feature를 합침으로써 per point feature를 줄 수 있다. 그래서 point feature의 조합을 기반으로 새로운 per point feature를 추출할 수 있다. per point feature는 local, global 정보를 둘 다 알 수 있다.

 이 수정을 통해, PointNet은 local geometry와 global semantic 모두에 의존하는 per poing quantity를 예측할 수 있다. 예를 들어 , per point normal를 정확하게 예측하여 network가 point local neighborhood의 정보를 요약할 수 있음을 검증하였다.

 

Joint Alignment Network

point cloud가 rigid transformation같은 특정 geometric transformation을 거친다면, point cloud의 semantic labeling은 불변해야 한다. 그래서 point set에 의해 학습된 representation은 이러한 변환에도 불변할 것으로 예상한다.

 해결책은 feature 추출 전 표준 공간에 모든 입력 집합을 맞추는 것이다. Jaderberg는 sampling과 interpolation을 통해  2D이미지를 맞추는 spatial transformer의 개념을 발표했다. 이는 GPU에 구현된 특별히 맞춤된 layer를 통해 달성했다.

 point cloud 형태의 입력은 훨씬 간단하게 이러한 목표를 달성하게 해준다. 새로운 layer를 추가할 필요 없고, 이미지의 경우처럼 alias(가명)를 도입하지 않는다. mini-0network로 affine transformation matrix를 예측하고 이 변환을 입력 point의 좌표에 직접 적용한다. 이 mini network 자신은 big network와 흡사하고 point independent feature 추출, max pooling, fully connected layer로 basic module가 구성되어 있다.

 이 아이디어는 feature space의 정렬로 확장될 수 있다. 다른 network 정렬을 point feature에 넣을 수 있고, 다른 입력 point cloud의 feature를 정렬하기 위해 feature transformation matrix를 예측할 수 있다. 그러나, feature space에서 transformation matrix는 spatial transform matrix보다 더 고차원이므로 최적화하기 어렵다.  그래서 저자들은 softmax training loss에 regularization을 추가했다. feature transformation matrix를 orthogonal matrix에 가깝게 제한한다.

A는 mini network에 의해 예측된 feature alignment matrix

orthogonal transformation은 입력정보를 잃지 않기 때문에 바람직하다. regularization을 추가함으로써 최적화가 더 안정적이고 모델이 더 나은 수행능력을 달성한다.

 

4.3. Theoretical Analysis

Universal approximation

집합함수의 연속성에 의해, 직관적으로 input point set의 small perturbation은 classfication이나 segmentation 점수같은 함수값이 크게 바꾸어선 안된다.

 f는 max pooling 레이어에 충분한 뉴런을 주어지면 network에서 임의로 근사될 수 있다.

 

Theorem 1.

x1, ..., xn은 임의로 정렬된 S의 모든 원소, Γ(gamma)는 연속함수, MAX는 입력으로 n개의 vector를 받아 요소별 최댓값인 새로운 vector를 반환하는 vector max 연산자

 핵심 아이디어는 최악의 상황에서 network가 동등한 크기의 voxel로 공간을 분리함으로써 point cloud를 volumetric representation으로 변환하는 것을 배우는 것이다. 그러나 network는 point 함수의 시각화에서 볼 수 있듯이 공간을 조사하는 훨씬 똑똑한 전략을 배운다.

 

Bottleneck dimension and stability

 network의 표현력이 max pooling layer의 차원에 크게 영향을 받는다. 

 위의 함수는 f의 sub network로, [0, 1]m에서 point set을 K차원 vector로 매핑한다. small corruption이나 extra noise point는 출력에서 변하지 않을 것이라는 것을 보여준다.

 

Theorem 2.

 (a)는 f(S)가 Cs의 모든 point가 보존된다면 input corruption에 따라 변하지 않는다고 말한다. 또한 Ns의 extra noise point에 따라 변하지도 않는다. (b)는 Cs는 K에 의해 결정된 bounded number of point만 포함한다는 것을 말한다. 다시 말해, f(S)는 K개 이하의 요소를 갖는 유한한 subset Cs에 의해 결정된다. 그래서 저자들은 Cs를 S의 critical point set, K를 f의 bottleneck dimension이라고 부른다.

 h의 연속성과 결합하여, 이는 point perturbation, corruption, extra noise point에 대한 robustness를 설명한다. robustness는 machine learning model에서 sparsity 원리의 분석에 의해 얻어진다. PointNet은 key point의 sparese set으로부터 sahpe를 요약하는 것을 학습한다. 

 

5. Experiment

5.1. Applications

 

 새로운 데이터 representation(point set)을 위해 노력하고 있음에도 불구하고, 여러 benchmark에서 경쟁력있는 성과를 달성했다.

 

3D Object Classification

 PointNet은 object classification에서 사용할 수 있는 global point cloud feature를 학습한다. 그전의 방법은 volumetric, multi-view image representation에 집중하였지만, 저자들은 처음으로 raw point cloud를 바로 학습시켰다.

 mesh faces에서 face area에 따라 1024개 point를 균일하게 샘플링하고 unit sphere로 정규화했다. 학습동안, 저자들은 point cloud를 랜덤하게 상향축에 따라 object를 회전시키고, 평균이 0, 표준 편차가 0.02인 Gaussian noise로 각 point의 위치를 jitter함으로써 증강시켰다.

 Table 1에서 이전의 연구와 point cloud(point density, D2, shape contour 등)로 추출한 traditional feature에서 MLP를 사용한 our baseline을 비교해보자. 저자들의 모델은 3D input(volumetric, point)를 기반으로 한 방법들 사이에서 가장 좋은 성능을 달성했다. fully connected layer와 max pooling만으로 PointNet은 inference spped에서 우위를 가지고 CPU에서 쉽게 병렬화할 수 있다. 여전히 our method와 multi view based method(MVCNN)에 작은 차이가 있지만, 이는 render된 이미지에서 포착되는 fine geometry detail의 소실 때문인 것으로 생각된다.

 

3D Object Part Segmentation

 Part segmentation은 fine grained 3D recognition task에서 도전적이다.3D scan이나 mesh model이 주어지면, 이는 각 point나 face를 part category label(ex. chair leg, cup handle)로 배정한다.

 

 Table 2에서 pre category와 mean IoU 점수를 보여준다. 2.3% mean IoU 향상과 대부분의 category에서 baseline method보다 우수한 것을 보여준다.

 

 simulated Kinect scans를 통해 robustness도 시험해보았다. 오직 5.3% mean IoU만 소실된 결과를 확인했다. Fig 3에서 complete와 partial data에서 정성적인 결과를 보여준다. partial data는 상당히 까다롭기 때문에 이 예측은 합리적이다.

 

Semantic Segmentation in Scenes

 part segmentation에서 PointNet은 semantic scene segmentation으로 쉽게 확장할 수 있었다.point label은 object part label대신 semantic object class가 된다.

 

 Table 3을 보면, PointNet은 baseline method보다 상당히 뛰어나다. Figure 4에서, 정성적인 결과를 볼 수 있다. PointNet은 부드러운 출력이 가능하며, missing point와 occlusion에 robust하다.

 PointNet으로부터 나온 semantic segmentation 출력을 기반으로, 우리는 object proposal을 위한 connected component를 이용하여 3D object detection system을 만들 수 있다. Table 4에 이전의 최신 방법들과 비교하였다. 이전의 방법들은 local geometric feature와 voxel gird에서 global room context feature를 학습한 SVM과 sliding shape method(with CRF post precossing)를 기반으로 하였다. 저자들의 방식은 furniture category에서 큰 차이로 이를 능가한다.

 

5.2. Architecture Design Analysis

Comparison with Alternative Order-invarian Methods

 정렬되지 않은 입력집합을 사용하기 위해서 적어도 3가지 옵션이 있다. 

 비교할 baseline에는 정렬되지 않은, 정렬된 point(n*3 array) multi layer perceptron, sequence로 입력 point를 간주하는 RNN 모델, 대칭함수를 기반으로 하는 모델이 포함되어있다. 대칭연산에는 max pooling, average pooling, 가중치 합을 기반으로 하는 attention이 포함되어 있다. 이 attention 방법은 scalar 점수를 각 point feature에서 예측하는 방법과 비슷하고, 이 점수는 softmax에서 계산함으로써 정규화된다. 이 가중치 합은 정규화된 점수와 point feature로 계산된다. Figure 5와 같이, max pooling 연산은 큰 차이를 두고 좋은 수행을 달성했다.

 

Effectiveness of Input and Feature Transformations

 Table 5에서 입력과 feature transformation의 긍정적인 효과를 보여준다. 가장 basic architecture가 이미 제법 합리적인 결과를 달성한 것은 흥미롭다. 입력 변환을 사용함으로써 0.8%의 성능향상을 줄 수 있다. 표준 손실은 더 높은 차원 변환을 위해 필요하다. 변환과 표준화를 합침으로써 가장 좋은 수행을 달성한다.

 

Robustness Test

 PointNet은 간단하고 효과적이면서 다양한 종류의 입력 corruption로부터 robust하다.  Figure 5의 max pooling 구조를 똑같이 사용하고 입력 point를 unit sphere로 정규화한다. 결과는 Figure 6과 같다.

 missing point에 대해 50% point를 잃었을 때, 정확도는 가장 먼 랜덤한 입력 샘플링과 관련하여 2.4%, 3.8%만 떨어졌다. PointNet은 또한 학습동안 이상치가 있다면, 이상치에도 robust하다. 2가지 모델을 평가해보자. 하나는 (x, y, z)좌표의 포인트를 학습한 것, 하나는 (x, y, z)와 density를 학습한 것. PointNet은 point의 20%가 이상치이더라도 80% 이상의 정확도를 가진다. Figure 6은 point perturbation에 robust하다는 것을 보여준다.

 

5.3. Visualizing PointNet

Figure 7에서, critical point set Cs와 upper bound shape Ns를 시각화한다. 2 shape사이에서 point set는 같은 global shape feature f(S)를 준다.

 Figure 7에서 critical point set Cs를 볼 수 있다. 이는 max pooled feature에 기여한 것이 shape의 skeleton을 요악한다는 것을 알 수 있다. upper bound shapes Ns는 input point cloud S와 동일한 global shape feature f(S)를 제공하는 가장 가능성이 높은 point cloud를 시각화 한다. Cs와 Ns는 PointNet의 robustness를 반영한다. 이는 약간의 non critical point를 잃는 것은 global shape signature f(S)를 바꾸지 않는다는 것을 의미한다. Ns는 edge-length-2 cube에서 모든 point를 네트워크를 통해 전달하고 point function values(h1(p), h2(p), ..., hk(p)는 global shape descriptor보다 크지 않은 point p를 선택하여 구성되어있다.

 

5.4. Time and Space Complexity Analysis

 Table 6에서 공간(number of parameter)과 시간(floating-point perations/sample) 복잡성을 요약한다.

 MVCNN과 Subvolume(3D CNN)이 좋은 성과를 달성하는 동안, PointNet은 computational cost에서 더욱 효율적이다. 게다가 PointNet은 param인 부분에서 MVCNN보다 훨씬 공간효율적이다. PointNet은 더욱 확장성이 뛰어나다. 공간, 시간 복잡도가 O(N)이다. 그러나, convolution이 computing time을 지배하기 때문에 multi-view 방법의 시간 복잡도는 이미지 해상도에 따라 제곱하게 증가하고 volumetric convolution을 기반으로 한 방법은 volume 크기에 따라 세제곱적으로 커진다.

 PointNet은 point cloud classification이나 semantic segmentation에서 초당 100만 point 이상을 처리할 수 있다.

 

6. Conclusion

 저자들은 point cloud를 직접 사용하는 PointNet이라는 novel한 deep neural network를 제시하였다. PointNet은 object classification, part segmentation, semantic segmentation을 포함한 3D recognition의 통합접근 방식을 제공한다. 또한 이는 최근 standard benchmark 결과보다 우수하다.