Lee Jaewon

7 minute read

Dynamic Graph CNN for Learning on Point Clouds 리뷰(DGCNN)

Introduction

점군은 2D 또는 3D에서 점들이 흩어져 있는 간단한 형태 표현 방식으로, LiDAR 스캐너와 스테레오 재구성을 포함한 3D 감지 기술의 출력물로 사용된다.

빠른 3D Point Cloud 획득의 등장으로 인해 최근에는 그래픽스와 비전 파이프라인에서 비용이 많이 드는 mesh 재구성이나 노이즈 때문에 불안정한 기술을 우회하고,
효율적으로 점군을 직접 처리하는 경우가 많아졌다.

현대적인 응용 사례들은 점군의 고수준의 처리를 요구한다.

모서리와 가장자리와 같은 형상의 중요한 기하학적 특징을 식별하는 대신, 최근의 알고리즘은 의미적 단서(semantic cues)와 적합성(affordances)을 찾는다.

이러한 특징들은 계산 기하학 또는 차분 기하학의 프레임워크에 깔끔하게 들어맞지 않으며 일반적으로 레이블링된 또는 레이블이 없는 데이터셋의 통계적 분석을 통해 관련된 정보를 추출하는 학습 기반 접근 방식이 필요하다.

Deep learning on point cloud

본 논문에서는 Point cloud classification과 segmentation을 고려한다.

이러한 문제를 해결하기 위한 기존의 전통적인 방법은 점군의 기하학적 특성을 캡처하기 위해 수작업(handcrafted)으로 설계된 특징들을 사용한다.

최근에는 이미지 처리에서의 deep neural 네트워크의 성공이 점군에서의 특징 학습에 대한 데이터 기반 접근을 동기로 하여 등장했다.

Deep point cloud 처리와 분석방법은 빠르게 발전하고 다양한 작업에서 기존 방법들을 능가하고 있다.

그러나 딥러닝을 점군 데이터에 적용하는 것은 간단하지 않다.
대부분의 기본적인 딥 뉴럴 네트워크 모델은 정규 구조의 입력 데이터를 요구하지만, 점군은 기본적으로 규칙 없는 데이터이다.

점 위치는 공간에 연속적으로 분포되며, 그들의 순서를 바꿔도 공간 분포는 변하지 않는다.

point cloud 데이터를 neep neural network에 처리하는 한가지 일반적인 방법은 raw data를 3D Grid라 불리는 volumetric한 표현으로 바꾸는 것이다.

(하지만 이 방법은 일반적으로 quantization artifacts와 과도한 메모리 사용을 도입하여 고해상도 또는 미세한 특징을 포착하기 어렵게 만든다.)

이전 연구

SOTA 딥 뉴럴 네트워크는 점군의 규칙 없음을 직접 다루도록 설계되어, 중간 정규 표현(intermediate regular representation)으로 전달하는 대신 원시 점군 데이터를 직접 조작한다.
이 접근 방법은 PointNet에 의해 개척되었으며, 이는 각 점을 독립적으로 처리하고 그 후에 대칭 함수를 적용하여 특징을 누적함으로써 점의 permutation invariance를 달성한다.

PointNet의 여러 확장 버전은 각각 독립적으로 작용하는 대신 점의 이웃들에 대한 정보를 고려한다. 이들은 네트워크가 지역적인 특징을 활용하여 기본 모델의 성능을 개선할 수 있도록 한다.

하지만 이러한 기술들은 점들을 지역적으로 독립적으로 처리하여 permutation invariance를 유지하는데, 이러한 독립성은 점들 사이의 기하학적 관계를 무시하여 지역적인 특징을 포착하지 못하는 근본적인 제한점을 가지고 있다.

제안

이러한 단점들을 극복하기 위해, 본 논문은 지역 기하 구조(local geometric structure)를 캡처하면서도 순서 무관성을 유지하는 새로우며 간단한 연산인 “EdgeConv”를 제안한다.

이는 점의 Embedding에서 직접적으로 점 특징을 생성하는 대신, EdgeConv는 각 점과 이웃들 간의 관계를 설명하는 edge feature를 생성한다.

EdgeConv는 이웃들의 순서에 불변하도록 설계되어 순서 무관성을 보장한다.

EdgeConv는 명시적으로 로컬 그래프를 구성하고 edge의 임베딩을 학습하므로, 모델은 유클리드 공간과 semantic space 둘 다에서 점들을 그룹화하는 능력을 갖추고 있다.

EdgeConv는 기존의 딥 뉴럴 네트워크 모델에 쉽게 구현하고 통합하여 성능을 향상시킬 수 있다.

실험에서 EdgeConv를 기본 버전의 PointNet에 어떠한 feature transformation 없이 통합한다.

Key Contributions

  • Point cloud로부터 학습하기 위한 새로운 연산인 EdgeConv를 제시하여, 점군의 지역 기하적 특징을 더 잘 포착하면서도 permutation invariance를 유지할 수 있다.
  • 모델이 층마다 관계 그래프를 동적으로 업데이트함으로써 점들을 의미적으로 그룹화할 수 있음을 보인다.
  • EdgeConv가 여러 기존의 점군 처리 파이프라인에 통합될 수 있음을 보인다.
  • EdgeConv에 대한 포괄적인 분석과 테스트를 제시하며, 벤치마크 데이터셋에서 SOTA 달성을 보인다.
  • 코드를 공개하여 재현성과 향후 연구를 용이하게 한다.

Related Work

  • Hand-Crafted Features
    local similarity between shapes를 어떤 개념으로 정의해야할 필요가 있다.

    전통적으로 이러한 유사성은 local geometric structure를 포착하는 feature descriptor를 구성하여 이룬다.

    컴퓨터 비전과 그래픽 분야의 무수한 논문들은 다른 문제와 데이터 구조에 적합한 포인트 클라우드용 지역 특징 기술자를 제안.

  • Deep learning on geometry
    비전 분야에서 합성곱 신경망(CNN)의 폭발적인 결과 이후, 이러한 방법들을 기하 데이터에 적용하는 것에 큰 관심을 가지고 있다.

    이미지와 달리 기하 데이터는 보통 어떤 기준 격자가 없어서 합성곱과 풀링을 대체하는 새로운 구성 요소가 필요함.

    이 문제를 간단하게 해결하기 위해 volumetric representation, view-based, 혹은 격자 위에 기하 데이터를 배치하는 방법들이 있었다.

    최근에는 PointNet이 기하 데이터 (그래프 및 매니폴드)에 대한 광범위한 클래스의 딥러닝 아키텍처를 보여주며, geometric deep learning이라고 불리는 이러한 방법들이 등장하였다.
    (..등등)

  • Geometry generative models
    기하적 생성 모델은 비-Euclidean 환경에 autoencoder, variational autoencoder (VAE), generative adversarial networks (GAN) [Goodfellow et al. 2014]과 같은 모델들을 일반화하려 한다.
    (..등등)

Our Approach

PointNet과 합성곱 연산에서 영감을 받은 접근 방식을 제안한다.

하지만 PointNet과 달리, 우리는 개별 포인트에 집중하는 대신 지역 기하 구조를 활용하기 위해 지역 이웃 그래프를 구성하며,
인접한 포인트 쌍을 연결하는 edge에 convolution과 같은 유사한 연산(convolution-like operation)을 적용하여 local geometric structure를 활용한다.

이러한 연산을 “EdgeConv”라고 명명하며, 이 연산은 변환 불변성(translation-invariance)과 비지역성(non-locality)에 사이에 기반하는 특성을 가지고 있다.

graph CNNs와 달리, 본 논문의 graph는 고정된 구조가 아니라 network의 each layer마다 동적으로 업데이트 된다.(not-fixed graph)

포인트의 k-nearest neighbors 집합은 네트워크의 각 레이어마다 변경되며, 이는 sequence of embedding으로부터 계산된다.

특징 공간에서의 근접성은 입력 공간에서의 근접성과 달라 포인트 클라우드 전체에 걸쳐 non-local 정보가 확산된다.

Edge Convolution

Point cloud

n개의 point들로 이루어진 F-dimensional point cloud를 고려하자.
$ X = {x_1, …, x_n} $

편의상 F=3, 각 point가 3차원 좌표계 $X_i = (x_i,y_i,z_i)$라고 하자.
(it is also possible to include additional coordinates representing color, surface normal, and so on.)

Deep neural network 구조에서 각 subsquent layer는 이전 레이어의 출력을 처리한다.

따라서 일반적으로 차원 F는 주어진 layer의 feature dimensionality를 나타낸다.

Graph

Local point cloud structure를 표현하는 directed graph를 $ \mathcal{G=(V,E)} $ 라고 하자.

$ \mathcal{V,E} $ 는 각각 vertices와 edges이다.
이는 $\mathcal{V} = { 1,…,n }$ 과 $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ 로 표현된다.

가장 간단한 경우로, $ \mathcal{G} $ 는 $X \ \ in \ \ \mathbb{R}^F$ 인 k-nearest neighbor(KNN) 그래프로 구성한다.

그래프에는 각 노드가 자신을 가리키는 self-loop을 포함한다.

  • Define edge features
    $ e_{ij}=h_{\Theta}(x_i, x_j) $ 에서
    $h_{\Theta}:\mathbb{R}^F \times \mathbb{R}^F \to \mathbb{R}^{F’}$ 는 학습가능한 parameters인 $\Theta$ 집합을 갖는 nonlinear function이다.



Define EdgeConv operation

Figure 2.

각 정점에서 나오는 모든 edge와 이와 관련된 edge feature에 채널별 symmetric aggregation opeartion $\square$ 을 정의한다.($\square$ 는 $max \ or \ \Sigma$)

$i \ th$ 정점 EdgeConv의 출력은 다음과 같다.
$X_i’= \underset{j:(i,j)\in\mathcal{E}}{\square}h_{\Theta}(x_i, x_j) $

이미지처럼 컨볼루션과 유사하게, $X_i$를 중심 픽셀로, $ {X_j : (i, j) \in \mathcal{E}}$ 를 주변 패치로 간주한다.

또한 전체적으로, n개의 점이 있는 F차원 점 구름이 주어지면, EdgeConv는 같은 수의 점을 가진 F’차원 점 구름을 생성한다.

Choice of h and $\square$.

Edge 함수와 Aggregation 연산의 선택은 에지컨브의 속성에 결정적인 영향을 미친다.

예를 들어, 이미지에 대해서 $X_1, …,X_n$이 regular grid에서 image pixel을 나타내고 그래프 $\mathcal{G}$가 각 픽셀 주변의 fixed size patch를 나타내는 연결성을 표현한다면,
Edge 함수로 $\theta_m \cdot X_j$ 가 선택되고, Aggregation operation으로 sum을 사용하면 Standard convolution을 얻는다.
(굉장히 좋은 비유라 봄. like CNN)
$x_{im}’= \sum_{j:(i,j)\in\mathcal{E}}^{} \theta_{m} \cdot X_j$

여기서 $\Theta=(\theta_1,…,\theta_m)$ 은 M개의 다른 필터의 가중치를 인코딩한다.
각각의 $\theta_m$ 은 $X$ 와 동일한 차원을 가지고 있으며 $\cdot$ 은 유클리디안 내적을 나타낸다.

  1. h의 두 번째 방법

    $h_{\Theta}(X_i,X_j)=h_{\Theta}(X_i)$

    이는, 로컬 이웃 구조를 망각한 오직 global shape 정보만 인코딩한다.

  1. h의 세 번째 방법

    $h_{\Theta}(X_i,X_j)=h_{\Theta}(X_j)$

    $x_{im}’=\sum_{j \in \mathcal{V}}^{} (h_{\theta(X_j)})g(u(X_i,X_j))$

    $g$는 가우시안 커널이고 $u$는 pairwise distance를 계산한다.(in Euclidean space)

  1. h의 네 번째 방법

    $h_{\Theta}(X_i,X_j)=h_{\Theta}(X_j-X_i)$

    이는 오직 local information만 인코딩한다.
    shpae을 small patch의 집합으로 취급하고, 전역 구조를 손실한다.

h의 다섯 번째 방법

이 방법은 본 논문에서 채택한 방법이다.
결국 local과 global을 모두 포착하기 위한 전략이다.

-> Asymmetric edge function

$h_{\Theta}(X_i,X_j)=\bar{h}_{\Theta}(X_i,X_j-X_i)$

이는 patch center $X_i$ 의 좌표에 의해 포착된 전역 모양 구조와 $X_j-X_i$ 에 의해 포착된 지역 이웃 정보를 명시적으로 결합한다.

본 논문의 operator는 다음과 같이 정의한다.

$e_{ijm}’= ReLU(\theta_{m} \cdot (X_j-X_i) + \phi_{m} \cdot X_i)$

$where, \ \ \Theta=(\theta_1,…,\theta_m,\phi_1,…,\phi_m)$

shared MLP로 구현될 수 있으며, 다음으로 아래 식을 수행한다.

$x_{im}’= \underset{j:(i,j)\in\mathcal{E}}{max}e_{ijm}’$

(해석해보면, 일단 local과 global에 대한 가중치를 달리 두고 비선형 함수인 ReLU를 이용하여 MLP를 수행하는 것 같다. Figure 2를 계속보면서 해야할 것 같다.)

Figure 2.

Dynamic graph update

본 논문에서 실험 결과는 각 layer에서 셍성된 feature space에서 최근접 이웃을 사용하여 graph를 재계산하는 것이 효과적이라는 것을 제시한다.

이것은 고정된 input graph에서 동작하는 graph CNN과 본 논문의 방법과의 중요한 차이점이다.

각 layer마다 다른 그래프 $ \mathcal{G^{(l)}=(V^{(l)},E^{(l)})} $ 가 있다. 여기서 l-th layer의 간선은 $ (i,j_{i1}),…,(i,j_{ik_{l}}) $ 와 같은 형태이다.

이때 $X_{j_{i1}}^{(l)},…,X_{j_{ik_l}}^{(l)}$ 은 $ X_i^{(l)} $ 에 가장가까운 $k_l$개의 점이다.

다시 말해, 아키텍처는 네트워크를 평가하기 전에 고정된 상수로 구성된 그래프 G를 채우는 방법을 학습하는 것이다.

구현에서는 특성 공간에서 쌍별 거리 행렬을 계산하고, 각 포인트에 대해 가장 가까운 k개의 점을 선택한다.

Properties

Permutation Invariance

$X_i’= \underset{j:(i,j)\in\mathcal{E}}{max}h_{\Theta}(x_i, x_j) $


max가 symmetric function이기에 input에 대해 layer $X_i’$의 output은 순서에 대해 invariant하다.

point feature를 aggregate하기 위한 global max pooling operator 또한 permutation-invariance하다.

Translation Invariance

이동량에 대해 불변하다.

$e_{ijm}’= \theta_{m} \cdot (X_j-X_i) + \phi_{m} \cdot X_i$

위 식에 대해 X_i와 X_j에 T로 shift해보면,

$e_{ijm}’= \theta_{m} \cdot (X_j+T-(X_i+T)) + \phi_{m} \cdot (X_i+T)$
$= \theta_{m} \cdot (X_j-X_i) + \phi_{m} \cdot (X_i+T)$

$\phi_{m}=0$ 인 경우 fully invariant to translation.

하지만 이 경우 모델은 패치들의 위치와 방향을 무시하고, 정렬되지 않은 패치들의 집합을 기반으로 객체를 인식하는 데에 그친다.

그러나 xj - xi와 xi를 둘 다 입력으로 고려하는 경우, 모델은 패치들의 지역 기하학을 고려하면서 전역적인 형태 정보를 유지한다.

Classification

Figure 3.

첫 번째 EdgeConv에서는 input space에서 물리적으로 가까이 있는 k 개의 point들을 뽑아서 사용한다면, 그 다음 EdgeConv부터는 feature space에서 distance가 가까운 k 개의 point들을 새롭게 뽑아서 사용하게 된다.

모든 EdgeConv 레이어에서 k의 최근접 이웃 수는 20.

다양한 스케일의 특징을 추출하기 위해 Shortcut connections이 포함

PointNet++ VS DGCNN

(본 논문에 포함된 내용이 아닌 개인적으로 작성한 내용입니다.)

특징 추출에 있어 PointNet++은 계층적으로 진행하며, local feature 추출에 우선 집중한다.

DGCNN은 그래프 컨볼루션을 사용하여 각 포인트의 로컬 및 전역 특징을 동시에 추출한다. 이웃과의 상호 작용을 통해 더 풍부한 특징을 얻을 수 있다.

Leave a comment

You may also enjoy