[paper] KPConv (Kernel Point Convolution) (2019)

오역, 의역, 생략 및 제 맘대로 해석한 글임에 주의.

---

논문 정보 : 

https://arxiv.org/pdf/1904.08889

 

KPConv는 point cloud에 직접 커널 포인트를 배치해 convolution을 수행하는 방법을 제안한 모델이다.
고정된 격자 대신, 공간 상의 kernel point를 중심으로 이웃 점들의 특징을 가중합하여 local 기하학적 구조를 효과적으로 반영한다.

Rigid Kernel을 쓸 수도 있지만, Deformable Kernel을 도입해 데이터에 따라 커널 위치를 학습함으로써 더 유연한 표현이 가능하다.
Classification과 Segmentation 등 다양한 point cloud task에서 높은 성능을 보인다.

---

KPConv: Flexible and Deformable Convolution for Point Clouds

 

Abstract

KPConv는 Point Cloud에서 중간 표현 없이 직접 처리하는 새로운 Point Convolution이다. 

 

kernel point에 의해 KPConv의 convolution 가중치는 Euclidean space에 위치하며, kernel point들과 인접한 input point에 적용된다.

kernel point의 개수를 자유롭게 조절할 수 있기에, KPConv는 고정된 grid convolution보다 더 유연하다.

또한 이러한 위치는 공간에서 연속적이며 network에 의해 학습될 수 있다.

따라서 KPConv는 로컬 기하학적 구조에 맞춰 커널 포인트를 조정하도록 학습하는 변형 가능한(deformable) 컨볼루션으로 확장될 수 있습니다. 정기적인 서브샘플링 전략 덕분에 KPConv는 효율적이며 다양한 밀도 변화에도 강건합니다. 

 

Classification과 Segmentation에서 기존의 방법들보다 더 좋은 성능을 보였다.

추가로 실험과 시각화를 통해 KPConv가 실제로 무엇을 학습하는지 분석한다.

 

1. Introduction

연구 배경 및 동기

Deep Learning은 2D grid(이미지) 위에서의 discrete convolution을 통해 발전해 왔지만, point cloud와 같은 불규칙한 데이터에서는 기존 convolution을 적용하기 어렵다. 

Point Cloud는 순서가 없고 sparse하지만, grid와 마찬가지로 spatially localized라는 중요한 특징을 가지고 있다.

 

기존 연구의 한계

Point Cloud를 처리하기 위해 데이터를 정규 격자로 projection하는 grid기반 방식이나 MLP는 사용하는 방식이 존재했다.

최근에는 point에 직접 작동하는 convolution 설계 시도들이 있었으나, 공간적 일관성이나 유연성 측면에서 한계가 존재했다.

 

2. Related Work

생략

 

 

3. Kernel Point Convolution

3.1. A kernel Function Defined by Points

기존의 방식들과 동일하게, 이미지 convolution에서 영감을 얻어, KPConv의 식은 아래와 point convolution 식으로  정의된다.

$\displaystyle (F\ast g)(x)=\sum_{x_i \in N_x}g(x_i-x)f_i$

이때 점 $x_i$와 feature $f_i$는 3차원의 점이고, kernel g와 feature f의 곱으로 convolution을 정의했다.

위에서 $N_x$는 radius neighborhoods 결과의 집합이다.

$N_x = \{x_i \in P | \left| x_i-x \leq r \right|\}\quad with\: r \in \mathbb{R}$

수작업으로 labeling된 dataset에서는 KNN보다 radius neiborhood가 더 나은 표현을 제공한다.

 

위의 식에서 kernel $g$의 핵심은, 이미지 convolution이 고정된 격자 위치에서 weight가 있는 것과는 다르게, 반지름 $r$의 구형 영역 안에 불규칙하게 퍼져 있는 점인 kernel points $\tilde{x_k}$에 weight $W_k$를 둔다는 것이다.

그리고 거리 $y_i=x_i-x$에 대해, $y_i$와 $\tilde{x}$간의 정규화된 거리 $h$를 기준으로 Kernel Point Convolution을 계산할 수 있다.

$\displaystyle h(y_, \tilde{x_k})=\max\left(0, 1-\frac{||y_i-\tilde{x_k}||}{\sigma}\right)$

$\displaystyle g(y_i)=\sum_{k<M}{h(y_i, \tilde{x_k})W_k}$

이때 $\sigma$는 kernel point가 영향을 미치는 거리로, 입력의 밀도에 따라 결정한다. (3.3.에서 더 자세히 설명한다.) 

또한 $h$에서 기존 방법에서 쓰던 gaussian 대신에 linear correlation을 쓴 이유는, kernel deformation에서 gradient backpropagation의 계산을 쉽게 하기 위해서이다. 마치 ReLU처럼.

 

 

 

3.2. Rigid or Deformable Kernel

Rigid KPconv에서, kernel point들의 위치들이 뭉쳐있으면 아주 비효율적이다.

각 점들을 서로 떨어뜨리기 위해, 각 점들에 척력이 있고, 구 안으로는 인력이 작용한다고 가정하여, 최적화 문제를 풀었다.

결과적으로 kernel point들은 평균 반지름의 $1.5\sigma$ 위치에 rescale되었다.

$y_i=x_i-x$  중심과 주변 점들 간의 거리

$\displaystyle h(y_, \tilde{x_k})=\max\left(0, 1-\frac{||y_i-\tilde{x}_k||}{\sigma}\right)$  거리와 kernel point간의 거리

$\displaystyle g(y_i)=\sum_{k<M}{h(y_i, \tilde{x}_k)W_k}$  에 가중치를 부여

$\displaystyle (F\ast g)(x)=\sum_{x_i \in N_x}g(y_i)f_i$  convolution을 계산

 

K가 충분히 클 때, Rigid Kernel은 이미 매우 효율적이지만, kernel point의 위치를 학습하면 성능을 더 올릴 수 있다.

왜냐하면 $g$는 $\tilde{x_k}$에 대해 미분 가능하기 때문이다.

Deformable KPConv에서는 새로운 Network를 추가해서, 모든 점 x마다 kernel point를 얼마나 $\Delta(x)$ shift할 지를 예측하게 한다.

$\displaystyle g_{deform}(y_i, \Delta(x))=\sum_{k<M}{h(y_i, \tilde{x}_k+\Delta_k(x))W_k}$

$\displaystyle (F\ast g)(x)=\sum_{x_i \in N_x}g_{deform}(y_i, \Delta(x))f_i$ deform된 g를 사용한다.

이를 통해 kernel point의 위치가 input위치 x마다 바뀐다.

 

각 kernel point의 이동값 $\Delta_k(x)$는 rigid KPConv가 출력한 값으로, 각 kernel point가 (x, y, z)방향으로 이동해서 3K개의 출력을 낸다.

shift를 만드는 kernel network와 convolution kernel network를 동시에 학습하지만, kernel이 조금만 shift되도록 shift network는 learning rate를 0.1배만큼 줄인다.

 

 하지만 point cloud에서 이렇게 하면 잘 되지 않았다. 왜냐하면 kernel point들이 점점 input point로부터 멀어져. 결국 kernel point 주변에 점이 없어, gradient가 0이 되어 죽은 kernel point가 되어 버린다. 이를 위해 2가지 Loss를 적용할 수 있다.

$L_{reg}=\displaystyle \sum_x L_{fit}(x)+L_{rep}(x)$

 

fitting loss

kernel point가 input 점 근처에 있도록 fitting하는 loss이다.

각 kernel point마다, input point와의 거리의 최소를 다 더했다.

$\displaystyle L_{fit}(x) =\sum_k \min_{y_i} \left( \frac{|| y_i-(\tilde{x}_k+\Delta_k(x)) ||}{\sigma} \right)^2$

 

repilsive loss

kernel point끼리 너무 가까워지지 않도록 한다.

$\displaystyle L_{fit}(x) =\sum_{k \neq l}...$ 너무 길어서 생략.

 

 

3.3. Kernel Point Network Layers

실제로 KPConv를 이용해 Network를 구현한 방법에 대해 설명한다.

 

Subsampling to deal with varing desities

각 layer에서 input 점들의 밀도를 조절하기 위해, subsampling을 사용한다.

점들이 sampling되는 공간적 위치를 확실하게 하기 위해, grid subsampling을 사용한다.

즉, 각 layer에서 특징의 위치를 나타내는 대표 점(support point)들은, 비어있지 않은 모든 grid cell에 포함되는 원래 input 점들의 중심(평균)으로 계산한다.

 

Pooling Layer

다양한 layer scale에서 구조를 만들기 위해서, 순차적으로 point의 수를 줄여야 한다.

위의 grid subsampling에서, 각 pooling layer마다 cell size를 2배로 적용함으로써, 점진적으로 KPConv의 receptive field를 증가시킨다.

각 pooling layer마다 pooling된 feature는 max pooling이나 strided KPConv로 구할 수 있다.

(strided KPConv는 이미지에서 stride convolution와 유사한 개념이다.)

 

KPConv Layer

KPConv Layer는 3차원의 입력 점들 N개 $\boldsymbol{P} \in \mathbb{R}^{N\times 3}$, 그리고 그에 대응되는 features $\boldsymbol{F} \in \mathbb{R}^{N\times D_{in}}$, 그리고 N'개의 각 점마다 $n_{max}$개의 이웃들을 저장하는 행렬 $\boldsymbol{N} \in {[1, N]}^{N'\times n_{max}}$이 있다. 여기서 N'는 실제로 계산되는 이웃 점들의 위치의 수로, stride convolution에서는 N과 다를 수 있다. 이웃 행렬 $boldsymbol{N}$은 일관된 계산을 위해 고정된 $n_{max}$의 크기를 가져야 하는데, 실제로는 많은 점들이 이보다 적은 수의 이웃을 가질 수 있다. 따라서 여기에는 실제로 convolution 계산시에 무시되는 shadow neighbors를 포함시킬 수 있다.

 

Network parameters

Rigid KPConv에서는 convolution 반지름은 $2.5\sigma_j$, 평균 kernel point 반지름은 $1.5\sigma_j$로 고정되지만, 

deformable KPConv에서는 그리드 크기 $dl$에 비례해서 설정된다.

 

 

3.4. Kernel Point Network Architectures

우리는 Classification과 Segmentation 각각을 위한 2개의 network 구조를 설계했다. 

 

 

KP-CNN

KP-CNN은 Classificatoin을 위한 5 layer network이다. 우리의 각 convolution block들은 ResNet block의 bottleneck처럼 설계되었다. 대신 image convolution과 batch normalizatoin, leaky ReLU는 KPConv로 대체햇다.

 

KP-FCNN

KP-FCNN은 Segmentation을 위한 완전한 convolutional network이다. encoder 부분은 KP-CNN과 동일하지만, decoder 부분은 ...생략 

 

4. Experiments

생략

 

5. Conclusion

Point Cloud에서 convolution을 수행할 수 있는 KPConv를 제안했다.

KPConv는 일정 반지름 안의 이웃들을 입력으로 해서, 소수의 kernel point들에 의해 공간적으로 배치된 weight를 사용하여 이를 처리한다.

우리는 local shift를 학습하여 kernel을 point cloud의 기하학적 구조에 맞게 효과적으로 변형시키는 deformable KPConv도 정의했다.

 

dataset의 종류나 network의 구성에 따라 Rigid KPConv와 deformable KPConv 모두 가치가 있다.