[논문 리뷰] Model Globally, Match Locally (Point Pair Features)
- 논문: Model Globally, Match Locally: Efficient and Robust 3D Object Recognition
- 저자: Bertram Drost, Markus Ulrich (MVTec Software), Nassir Navab, Slobodan Ilic (TU Munich)
- 학회: CVPR 2010
한 줄 요약
모델 위 모든 점 쌍의 거리와 법선 각도를 해시 테이블에 미리 넣어 두고, 장면에서 뽑은 점 쌍으로 그 표를 찾아 투표해서 3D 물체의 자세를 찾는 논문. 장면 점 하나를 기준으로 잡으면 남는 자유도가 “모델 위 점 하나와 법선 둘레 회전각 하나”뿐이라서, 투표를 2차원 표에서 끝낸다. 초기 자세 없이 6자유도 자세를 바로 찾는다.
배경
점군에서 자유곡면 물체를 찾는 방법은 크게 둘이었다. 전역 방법은 평면·원기둥·구 같은 기본 도형만 찾거나, 장면을 먼저 물체별로 나눠야 했다. 6자유도를 일반화 허프 변환으로 다 뒤지는 건 계산량이 너무 컸다.
지역 방법은 점마다 주변 표면을 요약한 기술자(spin image, tensor 등)를 만들고, 모델과 장면의 기술자를 비교해 대응점을 찾는다. 그다음 RANSAC 같은 단계로 대응점을 묶어 자세를 구한다. 문제는 기술자가 주변 표면에 기대고 있다는 점이다. 가려짐, 잡음, 주변 잡동사니에 약하다.
더 근본적인 약점도 있다. 평면, 구, 원기둥처럼 어디를 봐도 비슷한 면은 지역 기술자로 구별이 안 된다. 반경을 키우면 구별은 잘 되지만, 이번에는 가려진 부분에 더 약해진다. 기술자를 계산하려면 표면이 촘촘해야 해서 속도도 느렸다.
ICP는 대략적인 자세가 있어야 출발할 수 있다. 이 논문은 그런 초기값 없이 자세를 찾는 문제만 다룬다.
제안 방법
점 쌍 특징
모델과 장면 모두 법선이 붙은 점들의 집합으로 본다. 두 점 $m_1, m_2$와 법선 $n_1, n_2$에 대해 $d = m_2 - m_1$로 두고 특징을 이렇게 정의한다.
\[F(m_1, m_2) = \big(\lVert d \rVert_2,\ \angle(n_1, d),\ \angle(n_2, d),\ \angle(n_1, n_2)\big)\]거리 하나와 각도 셋이다. 두 점의 상대 위치와 방향만 담기 때문에, 물체를 어떻게 돌리고 옮겨도 값이 같다. 점 순서를 바꾸면 값이 달라지는 비대칭 특징이라는 점이 앞선 surflet pair와 다르다.
전역 모델 기술
오프라인 단계에서 모델의 모든 점 쌍에 대해 $F$를 계산한다. 거리는 $d_{dist}$ 간격, 각도는 $2\pi / n_{angle}$ 간격으로 양자화하고, 양자화한 값이 같은 쌍끼리 묶는다.
결과는 “특징 값 → 그 특징을 갖는 모델 점 쌍 목록”인 해시 테이블이다. 장면에서 특징 하나를 계산하면, 모델 어디에 그런 쌍이 있는지 상수 시간에 찾는다. 제목의 “Model Globally”가 이 부분이다. 모델 전체의 점 쌍 분포를 한 표에 담는다.
지역 좌표와 투표
장면에서 기준점 $s_r$을 하나 고르고, 이 점이 찾는 물체 위에 있다고 가정한다. 그렇다면 대응하는 모델 점 $m_r$이 있다. 두 점과 법선을 맞추고 나면 남은 자유도는 법선 축 둘레 회전 $\alpha$ 하나다.
그래서 자세를 $(m_r, \alpha)$로 쓸 수 있고, 논문은 이걸 지역 좌표라고 부른다. 모델 표면 위 점(2자유도)과 각도(1자유도)를 합쳐 3자유도다. 장면 점 $s_i$는 아래처럼 모델 점 $m_i$로 연결된다.
\[s_i = T_{s \to g}^{-1}\, R_x(\alpha)\, T_{m \to g}\, m_i\]$T_{m \to g}$는 $m_r$을 원점으로 옮기고 법선을 x축에 맞추는 변환이다. $T_{s \to g}$는 장면 쪽에 같은 일을 한다. 남은 어긋남은 x축 회전 $R_x(\alpha)$로 맞춘다.
투표는 2차원 누적 배열에서 한다. 행은 모델 점 개수, 열은 각도 칸 개수 $n_{angle}$다.
- 기준점 $s_r$을 장면의 다른 모든 점 $s_i$와 짝지어 $F(s_r, s_i)$를 계산한다.
- 해시 테이블에서 특징이 비슷한 모델 쌍 $(m_r, m_i)$들을 꺼낸다.
- 꺼낸 쌍마다 위 식을 만족하는 $\alpha$를 구하고 $(m_r, \alpha)$ 칸에 한 표를 준다.
- 다 돌고 나면 표를 가장 많이 받은 칸이 가장 그럴듯한 자세다. 안정성을 위해 최고점 대비 일정 비율 이상 받은 칸도 후보로 남긴다.
일반화 허프 변환과 같은 구조인데, 공간이 3자유도로 줄어서 계산이 감당할 만해졌다. 제목의 “Match Locally”가 이 부분이다.
α를 둘로 쪼개기
모든 쌍마다 $\alpha$를 새로 풀면 느리다. 논문은 $\alpha = \alpha_m - \alpha_s$로 나눈다. $\alpha_m$은 모델 쌍에만, $\alpha_s$는 장면 쌍에만 달려 있다.
$\alpha_m$은 오프라인에서 미리 계산해 해시 테이블에 같이 넣어 둔다. 온라인에서는 장면 쌍마다 $\alpha_s$를 한 번만 구하고 빼기만 하면 된다.
자세 군집화
투표는 기준점이 실제로 물체 위에 있을 때만 맞는다. 그래서 기준점을 여러 개 고르고, 각 기준점에서 나온 자세 후보를 모은다. 후보들은 양자화 때문에 정답 근처에 흩어져 있다.
이동과 회전 차이가 정해 둔 값보다 작은 자세끼리 묶고, 묶음 점수는 들어 있는 자세들이 받은 표의 합으로 한다. 점수가 가장 높은 묶음의 자세를 평균 내서 최종 자세로 쓴다. 혼자 동떨어진 후보는 걸러지고, 평균 덕분에 정확도도 오른다. 묶음을 여러 개 돌려주면 같은 물체 여러 개도 찾을 수 있다.
실험 결과
아래는 모두 논문에 실린 실험이다. 저자들은 거리 간격을 모델 지름에 비례하게 $d_{dist} = \tau_d \cdot \mathrm{diam}(M)$로 두었고, 기본값은 $\tau_d = 0.05$다. 각도는 $n_{angle} = 30$이라 법선이 12°까지 틀려도 같은 칸에 들어간다. 모델과 장면 모두 점 사이 거리가 $d_{dist}$ 이상이 되게 줄였고, 장면 점의 1/5을 기준점으로 썼다.
저자들은 Java 단일 스레드로 구현해 2.00GHz Core Duo 노트북에서 돌렸다. ICP로 다듬지 않은 결과이고, 모델 표를 만드는 데는 모델마다 몇 분이 걸렸다.
- 합성 장면, 물체 하나: 물체 4개를 50방향에서 렌더링해 점군 200개를 만들고 가우시안 잡음을 넣었다. 이동 오차가 지름의 1/10, 회전 오차가 12° 안이면 검출로 쳤다. 잡음이 지름의 5%인 토끼 장면에서 0.96초 만에 자세를 찾았다.
- 합성 장면, 물체 여러 개: 장면 50개에 물체 347개를 무작위로 놓았다. 장면 점 1/5을 기준점으로 쓰면 전체의 89.3%를 찾았고, 표면이 15% 넘게 보이는 물체는 98%를 찾았다.
- 기준점을 1/40로 줄이면 77.2%(15% 넘게 보이는 물체는 89.1%)로 떨어졌지만 약 4배 빨라졌다.
실제 데이터는 Mian 등이 공개한 레인지 스캐너 장면 50개(장면마다 물체 4~5개)를 썼다. 앞선 비교 논문처럼 코뿔소는 뺐다. spin image가 어느 장면에서도 코뿔소를 못 찾았기 때문이다.
| 방법 | 84% 미만 가려진 물체 인식률 | 물체당 시간 |
|---|---|---|
| Spin images | 87.8% | 약 2시간 |
| Tensor matching | 96.6% | 약 90초 |
| PPF ($\tau_d = 0.025$) | 97.0% | 약 85초 |
| PPF ($\tau_d = 0.04$, 기준점 1/10) | 89.2% | 약 2초 |
$\tau_d$를 키우면 인식률을 조금 내주고 40배 넘게 빨라진다. 그래도 spin image보다는 높다. 직접 만든 레이저 스캐너 장면에서는 이상치 제거나 스무딩 없이도 가려지고 어지러운 장면 속 클램프를 찾았다. 저자들은 이 정도 자세면 집어서 옮기는 작업에 충분해 보인다고 적었다.
느낀 점
- 핵심은 “기준점 하나를 맞추면 남는 건 회전 하나”라는 관찰이다. 6차원 자세 공간을 다 뒤지는 대신 (모델 점, 각도) 2차원 표에서 투표하니, 허프 변환이 현실적인 크기로 줄어든다.
- ICP와 이어서 보면 역할이 갈린다. PPF는 초기값 없이 대략 맞추지만, 정밀도는 양자화 간격(법선 12°, 지름의 5%)에 묶인다. 논문도 ICP로 다듬으면 더 좋아질 거라고 적었다. PPF로 후보를 찾고 ICP로 다듬는 두 단계가 자연스럽다.
- 지역 기술자가 평면·원기둥처럼 비슷한 면을 구별 못 한다는 지적은 기계 부품에 그대로 해당한다. 기계 부품은 대부분 평면과 원기둥의 조합이라, 점 쌍의 상대 관계만 쓰는 쪽이 더 맞을 것 같다.
- 2010년 방법인데 오래 버텼다. 2018년 BOP 벤치마크 논문은 최근 방법 15개를 비교했는데, 점 쌍 특징 기반 방법이 학습 기반 방법을 제치고 가장 좋은 성적을 냈다. 딥러닝이 이 자리를 언제 어떻게 넘어섰는지가 다음에 볼 논문들의 관심사다.