Point-based Method: DGCNN

 

관련 포스팅

Point-based Method: PointNet

 

 

 

DGCNN: Dynamic Graph CNN for Learning on Point Clouds

Dynamic Graph CNN for Learning on Point Clouds

 

Key Contributions

DGCNN은 PointNet과 Graph CNN를 결합한 네트워크로 포인트와 그 포인트에 인접한 포인트들의 관계를 설명하는 edge feature를 추출하는 EdgeConv라는 모듈을 제안한다. PointNet은 각 점들을 독립적으로 처리하여 permutation invariance를 유지하는 대신, 독립성으로 인해 점들 사이의 기하학적 관계를 무시하게 되어 local feature를 포착함에 있어 한계가 있다. DGCNN은 EdgeConv을 통해 local geometic structure 를 포착하면서도 permutation invariance를 유지할 수 있다. point간의 local graph를 구성하고 edge에 대한 embedding을 학습하여 유클리드 공간과 semantic 공간에서 모두 point를 그룹화할 수 있다. EdgeConv는 고정되어있지 않고 layer 간 그래프가 dynamic하게 업데이트되는 방식이다.

 

 

 

EdgeConv

 

Point Cloud

$n$ 개의 points들로 이루어진 F-dimentional point cloud $\mathbf{X}=\{{\mathbf{x}}_i,...,{\mathbf{x}}_n\}\subseteq {\mathbb{R}}^F$을 고려하자.

편의상 $F=3$, 즉 3D point ${\mathbf{x}}_i=(x_i,y_i,z_i)$ 라고 하자.

 

 

Graph

graph를 $\mathcal{G}=(\mathcal{V}\mathcal{,}\mathcal{E})$ 라고 할 때, $\mathcal{V}\mathcal{,}\mathcal{E}$는 각각 vertices와 edges이다.

$\mathcal{V}=\subset {\mathbb{R}}^c,\mathcal{E}=\subseteq \mathcal{V}\times \mathcal{V}$ 로 표현된다.

 

edge feature $e_{ij}=h_{\mathrm{\Theta }}({\mathbf{x}}_i,{\mathbf{x}}_j)$이고

$h_{\mathrm{\Theta }}:{\mathbb{R}}^F\times {\mathbb{R}}^F\to {\mathbf{R}}^{F^{\prime }}$는 학습 가능한 파라미터인  $\mathrm{\Theta }$ 집합을 갖는 nonlinear function이다. 

다시 말해, $h_{\mathrm{\Theta }}$는 두 벡터 ${\mathbf{x}}_i,{\mathbf{x}}_j$를 입력으로 받아 edge feature를 추출한다.

 

 

Edge Conv

그런 다음 각 vertex에서 나오는 edges와 관련된 edge features를 channel-wise symmetric aggregation operation $◻$ (e.g., $\sum$, max)을 적용하여 EdgeConv 연산을 정의한다.

 

최종적으로 $i$-th vertex에서 EdgeConv 연산 결과는 다음과 같다.

$${\mathbf{x}}_i^{{}^{\prime }}=\underset{j:(i,j)\in \mathcal{E}}{◻}h({\mathbf{x}}_i,{\mathbf{x}}_j)$$

 

 

Choice of $h$ and $◻$

이제 ${\mathbf{x}}_i$을 중심으로 주변의 점들 $\{{\mathbf{x}}_j:(i,j)\subseteq \mathcal{E}\}$로부터 ${\mathbf{x}}_i^{{}^{\prime }}$를 추출하기 위해 symmetric aggregation opration $◻$과 edge feature를 추출하는 nonlinear function $h_{\mathrm{\Theta }}$을 선정해야 한다. 이를 선정하기 위한 과정은 다음과 같다.

 

 

1) standard convolution 사용

$$x_{im}^{{}^{\prime }}=\sum _{j:(i,j)\in \mathcal{E}}{\theta }_m\cdot {\mathbf{x}}_j$$

구조적인 한계로 사용 불가능

 

2) PointNet 연산 활용

$$h_{\mathrm{\Theta }}({\mathbf{x}}_i,{\mathbf{x}}_j)=h_{\mathrm{\Theta }}({\mathbf{x}}_i)$$

global shape information만 활용하는 한계 존재

 

3) Gaussian kernel과 pairwise distance 활용

$$h_{\mathrm{\Theta }}({\mathbf{x}}_i,{\mathbf{x}}_j)=h_{\mathrm{\Theta }}({\mathbf{x}}_i),$$

$$x_{im}^{{}^{\prime }}=\sum _{j\in \mathcal{V}}(h_{\theta ({\mathbf{x}}_j)})g(u({\mathbf{x}}_i,{\mathbf{x}}_j))$$

$u$로 유클리드 공간에서 pairwise distance 계산하고 Gaussian kernel $g$를 적용한 결과를 곱함

인접한 point에 대해 적용해서 local 정보는 잘 뽑지만 global structure는 잘 포착하지 못하는 한계 존재

 

4) 상대 거리를 입력으로 사용

$$h_{\mathrm{\Theta }}({\mathbf{x}}_i,{\mathbf{x}}_j)=h_{\mathrm{\Theta }}({\mathbf{x}}_j-{\mathbf{x}}_i)$$

인접한 포인트와의 상대 거리를 이용하여 local feature를 잘 뽑아내지만, global 정보를 포착할 수 없는 한계 존재

 

5) asymmetric edge funtion: point ${\mathbf{x}}_i$ 와 이웃 포인트의 상대 거리 ${\mathbf{x}}_j-{\mathbf{x}}_i$를 모두 입력으로 사용

$$h_{\mathrm{\Theta }}({\mathbf{x}}_i,{\mathbf{x}}_j)={\overline{h}}_{\mathrm{\Theta }}({\mathbf{x}}_i,{\mathbf{x}}_j-{\mathbf{x}}_i)$$

절대적인 위치와 상대 거리 모두 사용하여 local, global feature를 모두 잘 포착

 

수식을 풀어서 쓰면,

절대적 위치 ${\mathbf{x}}_i$와 상대적 거리 ${\mathbf{x}}_j={\mathbf{x}}_i$를 입력으로 받아 edge features를 추출하는 nonlinear funtion $h_{\mathrm{\Theta }}$ (MLP - ReLU)에 넣는다. 그런 다음 symmetric aggregation operation으로 max-pooling을 적용하여 최종 feature $x_{im}^{{}^{\prime }}$을 추출한다.

$$e_{ijm}^{{}^{\prime }}=\text{ReLU}({\theta }_m\cdot ({\mathbf{x}}_j-{\mathbf{x}}_i)+{\varphi }_m\cdot {\mathbf{x}}_i),$$

$${\mathbf{x}}_{im}^{{}^{\prime }}=\underset{j:(i,j)\in \mathcal{E}}{\text{max}}{e}_{ijm}^{{}^{\prime }}$$

$$\text{where }\mathrm{\Theta }=({\theta }_1,...{\theta }_M,{\varphi }_1,...,{\varphi }_M)$$

 

 

Dynamic Graph Update

실험 결과 각 layer에서 생성된 feature space에서 최근접 이웃을 고려하는 k-NN을 사용하여 각 layer를 지날 때마다 graph를 재계산하면 효과적임을 제시한다.

아래 그림에서 볼 수 있듯이 layer를 거쳐갈수록 물리적인 거리보다 의미론적으로 유사한 점들에 더 연결 관계성을 보여 semantic segmentation을 잘해낸다는 점이다.

 

 

 

Evaluation

 

 

 

 

 

 

 

 

 

오래 되어서 자세히 기억은 안 나지만 DGCNN은 KNN으로 인해 계산 복잡도가 높고 graph를 계속 update하기 때문 PointNet보다 학습 시간이 2배 이상 걸렸던 거 같다. 당시 GPU 이슈도 있었어서 괴로웠던 기억밖에... 오랜만에 논문들을 다시 살펴보니 감회가 새롭기도 하다. 다음에 기회가 되면 PointPillars 논문 리뷰도 해보겠다.