포인트 클라우드 평가 지표(Evaluation Metric) - Chamfer distance, F-score

Reference

[1] A Point Set Generation Network for 3D Object Reconstruction From a Single Image (CVPR 2017)

[2] Tanks and temples: benchmarking large-scale scene reconstruction

 

 

두 포인트 클라우드가 얼마나 유사한지 평가하는 지표를 정리해본다.

 

3D reconstruction 작업에서 predicted cloud가 ground truth cloud와 얼마나 비슷한지(얼마나 잘 구성되었는지) 평가하기 위한 지표는 다양하다.

 

포인트 클라우드는 순서가 없기 때문에(unordered) 두 포인트 간의 거리를 직접 계산하는 많은 손실 함수($\ell_2$ 거리 등)는 부적절하다.

 

예측 포인트셋 $\mathcal{P}$과 gt 포인트셋 $\mathcal{G}$에 대해,

 

1. Chamfer Distance(CD)

---

엄밀히 말해 $d_{CD}$는 triangle inequality가 만족하지 않으므로 거리 함수는 아니다. 그러나 포인트셋 쌍에 대한 non-negative 함수이므로 ‘거리’라는 단어를 사용한다. CD는 서로에 대한 nearest neighbor를 찾고 그 거리를 더한다. 각 포인트에 대한 range 탐색은 독립이고 따라서 병렬화가 가능하다. KD-tree와 같은 공간 데이터 구조를 사용하면 NN 탐색을 더 빠르게 할 수 있다. 간단하지만 합리적이고 실용적인 지표이다.

 

• $\mathrm{CD}-\ell_1$ : 계산 복잡도 $\mathcal{O}(N \log N)$

$$ d_{C D}(\mathcal{P}, \mathcal{G})=\frac{1}{|\mathcal{P}|} \sum_{p \in \mathcal{P}} \min {g \in \mathcal{G}}\|p-g\|+\frac{1}{|\mathcal{G}|} \sum{g \in \mathcal{G}} \min _{p \in \mathcal{P}}\|g-p\| $$

• $\mathrm{CD}-\ell_2$

$$ d_{C D}(\mathcal{P}, \mathcal{G})=\frac{1}{|\mathcal{P}|} \sum_{p \in \mathcal{P}} \min {g \in \mathcal{G}}\|p-g\|^2_2+\frac{1}{|\mathcal{G}|} \sum{g \in \mathcal{G}} \min _{p \in \mathcal{P}}\|g-p\|^2_2 $$

 

 

2. Earth- Mover’s Distance(EMD)

---

두 집합 사이의 유사성을 측정하는 거리 지표로, 두 집합의 최적 매칭을 통해 계산한다. 두 분포 간의 차이를 최소화하는 방법으로 볼 수 있다.

• 두 포인트셋의 크기는 같다. i.e., $\left|\mathcal{P}\right|=\left|\mathcal{G}\right|$
• $\phi: \mathcal{P} \rightarrow \mathcal{G}$ : 일대일대응(bijection)

$$ d_{E M D}\left(\mathcal{P}, \mathcal{G}\right)=\min {\phi: \mathcal{P} \rightarrow \mathcal{G}} \sum{x \in \mathcal{P}}\|x-\phi(x)\|_2 $$

포인트가 미세하게 움직이더라도 최적 일대일대응은 유일하고 불변이므로 대부분 미분 가능하다. EMD의 정확한 계산은 최적화 문제를 해결하는 것으로, 이는 특히 딥러닝과 같은 응용 분야에서는 계산 비용이 매우 높다. 따라서 실용적으로 근사 알고리즘을 사용하여 EMD를 계산한다.

 

EMD vs. CD

• CD는 계산이 빠르고 로컬 특성을 잘 반영하지만 일부 구조적 정보를 잃고 비균일하다.
• EMD는 전반적인 구조와 분포를 잘 반영하지만 계산 비용이 크다.

 

3. F-score

---

$$ F(d)=\frac{2 P(d) R(d)}{P(d)+R(d)} $$

• precision

$$ P(d)=\frac{100}{|\mathcal{P}|} \sum_{p \in \mathcal{P}}\left[\min _{g \in \mathcal{G}}\|p-g\|<d\right] $$

• recall

$$ R(d)=\frac{100}{|\mathcal{G}|} \sum_{g \in \mathcal{G}}\left[\min _{p \in \mathcal{P}}\|g-p\|<d\right] $$