Distance Metric between Point Sets - Chamfer distance(loss) and Earth Mover's distance(loss)

논문을 읽을 때 자주 등장하는 기초 개념 중, 이번 글에서는 Chamfer Distance(CD, Chamfer Loss)와 Earth Mover's Distance(EMD, Earth Mover's Loss)를 알아보려 한다.

 

본 내용은 2017년도 CVPR 학회에 발표된 논문 Haoqiang Fan et al., "A Point Set Generation Network for 3D Object Reconstruction from a Single Image"에서 참고했다.

https://openaccess.thecvf.com/content_cvpr_2017/html/Fan_A_Point_Set_CVPR_2017_paper.html

CVPR 2017 Open Access Repository

 

 

 

 

Introduction

 

두 개념은 Point set 간의 distance를 측정하기 위한 metric이다. 3D vision 분야 연구를 하다보면 예측한 point cloud와 groundtruth를 비교할 loss function이 필요한 경우가 많은데, 이때 distance(loss)는 적어도 다음 세 개의 조건을 만족해야 한다.

1. Point 좌표에 대해 미분이 가능해야 한다.
2. 값이 자주 forward-propagate 혹은 back-propagate되므로, 계산이 효율적이어야 한다.
3. Point set에 (드물게) 존재하는 outlier에도 강인해야 한다. (예를 들어, Hausdorff distance는 이 조건을 충족시키지 못한다.)

 

위 조건을 만족시키면서 두 subset \(S_i^{pred} \in \mathbb{R}^3\), \(S_i^{gt} \in \mathbb{R}^3\) 사이의 distance \(d\)를 찾기 위해 다음과 같은 형태의 loss function을 설정했다.

\( L \left( \left\{ S_i^{pred} \right\}, \left\{ S_i^{gt} \right\} \right) = \sum\limits_{i} d( S_i^{pred}, S_i^{gt} ) \)

여기서 \(i\)는 training sample의 인덱스를, \(S_i^{pred}\)와 \(S_i^{gt}\)는 각 샘플의 prediction과 groundtruth를 나타낸다.

여기에 사용할 수 있는 두 가지 distance 개념이 바로 Chamfer Distance(CD)와 Earth Mover's Distance (EMD)이다.

 

 

 

 

 

Chamfer Distance

 

\(S_1, S_2 \subseteq \mathbb{R}^3\)에 대해 Chamfer distance는 다음과 같이 정의한다.

\( d_{CD}(S_1, S_2) = \sum\limits_{x \in S_1} \underset{y \in S_2}{\min} \lVert x - y \rVert_2^2 + \sum\limits_{y \in S_2} \underset{x \in S_1}{\min} \lVert x - y \rVert_2^2 \)

 

엄밀히 말하면 \(d_{CD}\)는 삼각 부등식이 성립하지 않기 때문에 distance function이 아니다. 하지만 음의 값을 갖지 않기 때문에 개념적으로 distance라는 용어를 사용한다.

수식을 그대로 풀어서 설명해보자면, 각 point에 대해 다른 set에 포함된 점 중 가장 가까운 점과의 거리를 제곱하여 모두 더한 값이다.

 

Chamfer distance의 특징은 다음과 같다.

1. 연속이며, 미분 가능하다.
2. 각 point에 대해 가장 가까운 점을 찾는 과정이 서로 독립적이므로, 병렬 계산이 가능하다.
3. 가까운 점을 빠르게 찾는 KD-tree와 같은 data structure를 사용할 수 있다.
4. 간단하면서도 좋은 결과를 가진다.

 

 

 

Earth Mover's Distance

 

사실 Chamfer distance를 알아보려고 논문을 찾아봤는데, 이 개념도 있어서 간단하게 같이 정리해둔다.

size가 같은, 즉 size가 \(s = \lvert S_1 \rvert = \lvert S_2 \rvert\)인 두 point set \(S_1, S_2 \subseteq \mathbb{R}^3\)에 대해, EMD는 다음과 같이 정의된다.

\( d_{EMD}(S_1, S_2) = \underset{\phi:S_1 \rightarrow S_2}{\min} \sum\limits_{x \in S_1} \lVert x - \phi(x) \rVert_2 \)

여기서 \(\phi : S_1 \rightarrow S_2\)는 bijection(전단사함수, 즉 두 집합 사이를 중복 없이 모두 일대일로 대응시키는 함수)이다.

 

EMD는 optimization problem의 해이다. 값이 0이 아닌 point set 쌍에 대해, optimal bijection \(\phi\)는 유일하며, point가 매우 조금(극소량) 움직여도 값이 변하지 않는다. 따라서 EMD는 거의 모든 상황에서 미분이 가능하다.

실제로 deep learning에 EMD 계산을 정확하게 하는 것은 cost가 너무 많이 든다. 따라서 실 사용 시에는 \((1 + \epsilon)\) approximation 방법을 사용한다. 이 방법을 여기서 자세히 다루지는 않겠다. 이 근사는 error가 1% 정도밖에 되지 않고, GPU를 활용한 병렬 계산이 가능하다.

 

 

 

 

CD vs EMD

 

두 방법을 간단히 비교해보자.

Neural network는 물체의 정밀한 geometry(shape)를 예측할 때 여러 이유로 어느 정도의 uncertainty를 갖게 된다. 이때 neural network는 불완전한 space를 평균낸 mean shape를 예측하게 된다. 이러한 mean shape는 distance의 특징을 나타내 준다.

다음 그림을 살펴보자.

 

CD vs EMD

 

위 그림에서는 synthetic shape distribution에 대해 EMD의 mean-shape behavior와 CD의 mean-shape behavior를 비교하였다.

Mean-shape behavior는 shape distribution \(\mathbb{S}\)가 주어졌을 때, EMD 또는 CD중 하나인 distance function \(L\)에 대해 stochastic gradient descent 방법으로 다음 식을 minimize한다.

\( E_{s \sim \mathbb{S}} \left[ L(x, s) \right] \)

 

(a)와 (b) 경우에는 연속적으로 한 번 변하는 구간이 있다. EMD는 대략적으로 mean에 해당하는 shape을 잡아내고, CD는 흩뿌려진듯한 모양으로 shape의 geometric 구조가 흐릿하게 보인다.

(c)와 (d)의 경우에는 각각 bar의 코너 부분, bar의 옆 부분에 비연속적으로 shape가 변하는 구간이 있다. 여기서는 CD는 적절한 위치에 point 몇 개를 보이지만, EMD는 왜곡된 형태를 보인다.

 

만약 논문을 읽다가 더 깊은 내용이 필요하다면 그 때 더 자세한 내용을 추가할 것이다!