Lee Jaewon

7 minute read

KPConv: Flexible and Deformable Convolution for Point Clouds 리뷰


Introduction

(본론은 여기부터 보셔도 됩니다.)

깊은 학습의 도래로 현대 컴퓨터 비전은 discrete convolution을 기본 구성 요소로 사용하여 크게 발전되었다.

이 연산은 2D 그리드 상의 지역 이웃 데이터를 결합한다.

이러한 정규 구조 덕분에 현대 하드웨어에서 높은 효율성으로 계산될 수 있지만, 이러한 정규 구조를 상실하면 2D 그리드 상에서와 같은 효율성으로 합성곱 연산을 올바르게 정의하기 어렵다.

3D 스캐닝 기술의 발전으로 인해 이러한 정규 그리드가 아닌 데이터에 의존하는 여러 응용 프로그램이 발전해왔다.

예를 들어, 3D 포인트 클라우드 segmentation이나 3D SLAM은 non-grid 구조 데이터인 포인트 클라우드에 의존합니다.

포인트 클라우드는 3D(또는 고차원) 공간의 점들로 구성된 집합입니다. 많은 응용 프로그램에서는 이 점들이 색상과 같은 해당 특성과 결합된다.

본 논문에서 포인트 클라우드는 이러한 두 가지 요소, 즉 점 $P \in \mathbb{R}^{N \times 3}$ (3차원 공간에서의 좌표)와 특성(feature) $F \in \mathbb{R}^{N \times D}$ 를 고려한다.

포인트 클라우드는 순서가 없는 sparse한 구조이므로 그리드와는 매우 다르다. 그러나 합성곱의 정의에 필수적인 공통된 속성이 있다. 바로 공간적으로 지역화(spatially localized)되어 있다는 점이다.

그리드에서는 특성들은 행렬 내에서 인덱스로 지역화되지만 포인트 클라우드에서는 해당 점 좌표에 따라 지역화된다.

따라서 점들은 구조적 요소로 간주되고 특성들은 실제 데이터로 간주되어야 한다.

여러 접근 방법이 제안되었으며,
몇 가지 방법은 그리드 기반 범주에 속하며, 이 방법들은 희소한 3D 데이터를 더 쉽게 다룰 수 있는 정규 구조로 데이터를 투영하거나

다른 접근 방법은 다층 퍼셉트론(MLP)을 사용하여 포인트 클라우드를 직접 처리한다.

더 최근에는 몇 가지 시도가 있어 합성곱을 직접 포인트에 적용하는 방법들이 등장했다. 이러한 방법들은 포인트 클라우드의 공간적 지역화 속성을 활용하여 공간적 커널을 가진 포인트 합성곱을 정의한다.

본 논문에서는 새로운 포인트 합성곱 연산자인 Kernal Point Convolution (KPConv)을 소개한다.

KPConv는 로컬 3D 필터들의 집합으로 구성되지만 관련 작업에서 보여준 이전 포인트 합성곱의 한계를 극복한다.

KPConv는 이미지 기반 합성곱에서 영감을 받았지만, 커널 픽셀 대신에 각 커널 가중치가 적용되는 영역을 정의하는 커널 포인트 집합을 사용한다.

Figure 1.

kernel weight는 input feature와 같이 포인트에 의해 운반되며(carried by points라고 되어있는데 정확히 무슨말인지는 조금 더 봐야할 것 같다.),
그들의 영향영역(area of influenece)는 correlation function에 의해 정의된다.

커널 포인트의 개수는 제약이 없어서 설계가 매우 유연하다.

이전 연구들과 다르게 커널 포인트를 사용하지만 커널에 대한 가중치 없이 지역 기하 패턴을 학습한다.

더 나아가, 또한 변형 가능한 버전의 합성곱을 제안한다.

Figure 3.

이것은 커널 포인트에 적용되는 local shift를 학습하는 것으로, 각 합성곱 위치마다 다른 shift를 생성하여 입력 클라우드의 다양한 영역에 대해 커널의 형태를 조절할 수 있게 한다.

Deformable convolution은 이미지의 변형 가능한 합성곱과는 다른 방식으로 설계되었다.
데이터의 다른 특성으로 인해 데포메이션 커널이 포인트 클라우드 기하학에 잘 맞도록 도와주는 정규화가 필요하다.
우리는 효과적인 수용 영역(ERF)[22]과 제거 실험을 사용하여 Rigid KPConv와 Deformable KPConv를 비교한다.(Ablation study)

또한 몇 개의 이전 연구들과 달리 k-최근접 이웃(KNN) 대신 반경 이웃(radius neighborhoods)을 선호한다.

13에서 보이듯이, KNN은 non-uniform sampling 설정에서 robust하지 않다.

반경 이웃과 입력 클라우드의 정규 하위 샘플링(regular subsampling)의 조합에 의해 본 논문의 합성곱은 변동되는 밀도에 대해 견고성을 보장한다.

이전 연구들의 정규화 전략과 비교해 본 논문의 접근 방법은 합성곱의 계산 비용도 줄인다.

(.. 이 뒤 내용은 실험 및 성능 향상, 우수성에 관한 이야기라 pass)

Related Work

  • Projection networks
    몇 가지 방법은 포인트를 중간 그리드 구조로 투영
    혹은 Voxel 기반 방법

  • Graph convolution networks

  • Pointwise MLP networks
    PointNet

  • Point convolution networks
    Pointwise CNN
    SpiderCNN
    Flex-convolution
    PCNN

Kernel Point Convolution

A Kernel Function Defined by Points

이전 연구들과 마찬가지로 KPConv는 일반적인 포인트 합성곱의 정의로 표현할 수 있으며, 이미지 합성곱에서 영감을 받았다.

명확성을 위해,
$\mathcal{P} \in \mathbb{R}^{N \times 3}$ 의 점 $x_i$와 이에 해당하는 feature인 $\mathcal{F} \in \mathbb{R}^{N \times D}$ 의 $f_i$로 정의한다.

$(\mathcal{F} *g)(x)=\underset{x_i \in \mathcal{N}_{x}}{\sum} = g(x_i-x)f_i$



Figure 2.

radius neighborhood를 이용하여 변동되는 밀도에 대해 강인함을 보장한다.

따라서

$\mathcal{N}_{x} = (x_i \in \mathcal{P} \mid \Vert x_i-x \Vert <= r)\ \ \cdots \ \ (1)$

$r \in \mathbb{R}$ 은 선택한 반경이다.

Intro에서 언급했듯이 반경 이웃을 사용하여 계산된 손으로 제작된 3D 포인트 특성이 KNN보다 더 나은 표현을 제공한다.

본 논문은 함수 g에 일관된 구 형 도메인이 있으면 네트워크가 의미 있는 표현을 학습하는 데 도움이 될 것으로 믿는다.

식 (1)의 중요한 부분은 커널 함수 g의 정의이며, 이것이 KPConv의 특징이다. g는 x를 중심으로 한 이웃 위치를 입력으로 사용한다.
(이웃 : $y_i=x_i-x$)

g는 $\mathcal{B}_{r}^{3} = (y \in \mathbb{R}^{3} \mid \ \Vert y \Vert <= r )$ 범위로 정의된다.



이미지 합성곱 커널과 유사하게 (이미지 합성곱과 KPConv 사이의 자세한 비교는 Figure 2에서 확인할 수 있다), 본 논문은 g가 이 도메인 내의 다른 영역에 대해 다른 가중치를 적용하는 것을 원한다.

(중간정리 : KPConv는 격자 kernel이 아닌 일정한 반지름 r을 가지는 구 형태의 kernel을 사용한다. 2D Kernel의 grid 역할을 수행하는 것이 구 형태의 kernel 내부의 kernel point이다. 이 때 KNN보다 그냥 정해진 r값을 통한 구 형태의 kernel이 밀도에 대해 강인하고 네트워크가 의미 있는 표현을 학습하는 데 도움이 된다고 한다.)
(출처 : https://shvblog.tistory.com/10)

Kernel 속의 kernel point는 정해진 위치에서 각각의 weight를 가지고 존재한다.

하지만 격자처럼 완벽히 인덱스가 맞는 것이 아니기에 input point feature와 이와 곱해질 kernel point weight를 결정하기 위해 위 식에 이어 아래의 식들을 통해 상관관계를 정의하고 새로운 feature를 생성한다.
(출처 : https://shvblog.tistory.com/10)

Kernel point :

$( \tilde{x}_{k} \mid k < K ) \in \mathcal{B}_r^3 $

특성을 차원 Din에서 Dout로 매핑하는 것에 관련된 가중치 행렬 :

$( W_k \mid k < K ) \in \mathbb{R}^{D_{in} \times D_{out}}$

Kernel function :

$g(y_i)=\underset{k<K}{\sum} h(y_i,\tilde{x}_{k})W_k$



$h$ 함수는 $\tilde{x_k}$ 와 $y_i$ 간의 상관관계이다. 이것은 $\tilde{x}_{k}$ 가 $y_i$ 에 가까울수록 커진다.
(Inspired by the bilinear interpolation)

linear correlation은 다음과 같다.

$ h(y_i,\tilde{x_k})=max(0, \ 1-\frac{\Vert y_i-\tilde{x_k} \Vert}{\sigma}) $

$\sigma$는 kernel point의 영향 거리(influence distance)이다.
이것은 input density에 따라 선정될 것이다.

가우시안 상관 함수와 비교하면, 선형 상관 함수는 더 간단한 표현이다. 본 논문은 간단한 상관 함수를 권장하여 커널 변형을 학습할 때 그라디언트 역전파를 쉽게한다.
(선형 함수를 사용하면 미분이 간단해진다. 예를 들어, 선형 상관 함수의 미분은 상수이며, 입력에 따라 변하지 않는다. 이는 역전파 과정에서 그라디언트를 효율적으로 전달할 수 있음을 의미한다)

Figure 1.

Figure 1을 다시 확인해보면 kernel point와 입력 point가 가까울 때 더 큰 feature값을 가지는 것을 설명하는 것을 확인할 수 있다.

Rigid or Deformable Kernel

Rigid

Kernel point의 위치는 convolution 연산에 매우 중요하다.

본 논문의 rigid kernel은 효율을 위해 반드시 규칙적으로 배열되어야한다.

KPConv의 유연성이 강점이라고 주장했기 때문에 어떤 K에 대해서도 규칙적인 배열을 찾아야한다.

본 논문은 각 포인트가 다른 포인트들에게 밀어내는 힘을 가하는(repulsive petential) 최적화 문제를 해결함으로써 커널 포인트를 배치하기로 결정한다.
(kernel point 간의 거리가 멀수록 작아지는 repulsive petential)

이 포인트들은 attractive force에 의해 구를 중심으로 제한된 공간에 머무르도록 하고, 그 중 하나의 포인트는 중심에 위치하도록 제한된다.
(구의 중심에서 kernel point가 무한히 멀어지는 것을 막기 위해 중심에서 가까울수록 작아지는 attractive potential을 정의)

이는 구 내에서 명확하게 포인트들을 규칙적으로 배치하는 것이 어렵기 때문에,
최적화 문제로 변환하여 해결하려 했다.

문제는 간단하다고 언급하며,
주어진 구 내에서 K개의 포인트 $\tilde{x_k}$ 들이 가능한 한 서로 멀리 떨어지도록 하게 하기 위하여 repulsive petential과 attractive potential을 위 수식처럼 정의하고, 이 두 값의 합을 최소화하는 포인트 개수 별 배치를 구했다.

적절하게 초기화된 커널에서는 KPConv의 강성 버전이 매우 효율적이다.

특히 충분히 큰 K가 주어지면 g의 구 형 도메인을 커버할 수 있다.

그러나 커널 포인트 위치를 학습하여 용량을 더욱 증가시킬 수도 있다.

커널 함수 g는 $\tilde{x_k}$ 에 대해 미분 가능하기에 이들은 학습 가능한 매개변수이다.

각 컨볼루션 층에 대해 하나의 전역 $(\tilde{x_k})$ 집합을 학습하는 것도 고려할 수 있지만, 이는 고정된 규칙적인 배열보다 더 많은 설명력을 가져오지 않을 것이다.

Deformable

대신 네트워크는 각 컨볼루션 위치 $x \in \mathbb{R}^3$ 마다 K개의 shift $\Delta(x)$ 집합을 생성하고, 이를 이용하여 deformable KPConv를 정의한다.

$(\mathcal{F} *g)(x)=\underset{x_i \in \mathcal{N}_{x}}{\sum} = g_d(x_i-x, \Delta(x))f_i$

$y_i = x_i-x$

$g_d(y_i, \Delta(x))=\underset{k < K}{\sum} h(y_i, \tilde{x_k}+\Delta_{k}(x))W_k$

다음과 같은 식을 통해 offset $\Delta_{k}(x)$ 을 부여하였다.

Figure 3.

Figure 3처럼 offset $\Delta_{k}(x)$ 를 입력특징을 x,y,z 총 3K개의 값으로 매핑하는 Rigid KPConv의 출력으로 정의한다.

훈련 중 네트워크는 시프트를 생성하는 rigid 커널과 출력 기능을 생성하는 deformable 커널을 동시에 학습하지만,
첫 번째 커널의 학습 속도는 global network 학습 속도의 0.1배로 설정된다.

정규화

하지만, 이러한 deformable 컨볼루션의 적용은 point cloud에 맞지 않는다.

실제로, 커널 포인트들은 입력 포인트들로부터 떨어져 있게 되어버린다.

이러한 커널 포인트들은 네트워크에 의해 손실되며,
이유는 이동된 kernel point 주변에 input point가 없다면 이 kernel point가 사용되지 않으므로 gradient가 null이 되어 point가 사라지게 된다.

이를 해결하기 위해, Fitting regularization과 Repulsive regularization을 제시한다.

Fitting regularization은 커널 포인트와 입력 이웃들 중 가장 가까운 이웃과의 거리를 이용하며, 가까울수록 작은 값을 가지게 된다.

Repulsive regularization은 모든 커널 포인트 쌍들 사이에 추가하여, 커널 포인트들이 서로 축소되지 않도록 한다.
kernel point들이 같이 잘못된 위치에 빠지지 않도록 한다.

Kernel Point Network Architectures

KPConv를 이용해서 KP-FCNN이라는 segmentation network와 KP-CNN이라는 classification network를 만들었다.

KP-FCNN

KP-FCNN에서 인코더 부분은 KP-CNN과 동일하며, 디코더 부분은 최종 포인트 단위 특징을 얻기 위해 nearest upsampling을 사용한다.

스킵 링크는 인코더와 디코더 사이의 중간 레이어 간의 특징을 전달하는 데 사용된다.
이러한 특징들은 업샘플된 특징과 연결되며, 단항 합성곱(unary convolution)으로 처리되며, 이는 이미지에서의 1x1 합성곱 또는 PointNet에서의 공유 MLP와 동등하다.

KP-CNN

convolutional blocks은 bottleneck ResNet 블록과 유사한 디자인을 가지고 있으며,
이미지 합성곱, 배치 정규화(batch normalization),
그리고 leaky ReLu 활성화 함수가 KPConv로 대체되었다.

마지막 레이어 이후에는 전역 평균 풀링(global average pooling)으로 특징들이 집계되고, 이후에는 이미지 CNN과 유사하게 완전 연결 계층과 소프트맥스 계층으로 처리되어 label을 분류한다.

Experiments

두 네트워크 모두 classification과 segmentation task에서 SOTA를 달성하며 좋은 결과를 보였다.

참고 자료

Leave a comment

You may also enjoy