[MIT 머신비전 15강] 스프링으로 끌어당겨 맞추기: PatMax와 거리 지도 | 거리 변환(Distance Transform)

MIT OpenCourseWare 6.801 15강 원본 영상 (영어)

한 줄 요약: 대충 찾은 위치에서 출발해, 사진 속 경계 점들을 학습한 모양 쪽으로 스프링처럼 조금씩 끌어당기면 격자 간격보다 훨씬 정밀하게 맞출 수 있습니다. 이때 “경계까지 얼마나 먼가”를 미리 적어 둔 거리 지도가 길잡이가 됩니다. 덤으로, 필터를 아주 빠르게 거는 요령도 하나 배웁니다.

대충 찾은 다음, 정밀하게

13강의 PatQuick은 모든 자세를 일정 간격으로 훑어서 가장 좋은 칸을 고릅니다. 빠르고 튼튼하지만, 정확도가 훑는 간격에 묶입니다. 2픽셀 간격으로 훑었다면 답도 2픽셀 단위로만 나옵니다.

오늘 볼 특허(US 7,065,262, 강의에서는 PatMax라고 부릅니다)는 그다음 단계를 맡습니다.

PatQuick이 고른 “대충 맞는 자세”에서 출발해, PatMax가 몇 번에 걸쳐 진짜 자세로 다가갑니다.

• 처음 추측이 필요합니다. 아무 데서나 시작하지 않고, PatQuick 같은 방법이 준 대략의 자세에서 출발합니다.
• 자세를 칸으로 나누지 않습니다. 그래서 픽셀보다 작은 단위(서브픽셀)까지 맞출 수 있습니다.
• 한 번에 풀지 않고 되풀이합니다. 실제 문제는 깔끔한 공식 답이 없어서, 조금씩 고치기를 수렴할 때까지 반복합니다.

거리 지도: 경계까지 얼마나 먼가

PatMax는 학습할 때 모양의 경계뿐 아니라, 사진의 모든 칸에 가장 가까운 경계까지의 거리와 방향을 적어 둡니다. 등산 지도의 등고선처럼, 경계가 골짜기 바닥이고 멀어질수록 높아지는 지형이라고 생각하면 됩니다.

원과 직선 주변은 단순하지만, 모서리 바깥이 까다롭습니다. 보통의 직선 거리로 재면 모서리를 둥글게 감쌉니다.

모서리 바깥이 어려운 이유는 가장 가까운 경계 “점”이 모서리 꼭짓점 하나로 바뀌기 때문입니다. 가로 거리와 세로 거리를 그냥 더하는 맨해튼 거리(바둑판 길 따라 걷는 거리)라면 계산이 쉽지만, 방향에 따라 거리가 달라져 PatMax는 정확한 직선 거리를 씁니다.

스프링으로 끌어당기기

이제 실제 사진에서 찾은 경계 점들을 거리 지도 위에 올립니다. 각 점은 가장 가까운 경계와 스프링으로 연결되어 있다고 생각합니다. 멀리 있는 점일수록 세게 당겨집니다.

주황 선이 스프링입니다. 평균 거리가 처음 0.282에서 한 번 당긴 뒤 0.156, 여덟 번 뒤 0.078로 줄어듭니다.

점 하나하나를 따로 움직이는 것이 아니라, 모든 스프링의 힘을 모아 점 묶음 전체를 움직입니다.

• 힘의 평균 → 전체를 그쪽으로 이동 (2자유도)
• 돌리려는 힘(돌림힘)의 평균 → 전체를 회전 (1자유도)
• 바깥으로 미는 힘 / 안으로 당기는 힘의 평균 → 전체를 확대·축소 (1자유도)

이동을 예로 들면 식은 그냥 가중 평균입니다.

\[\text{이동량} = \frac{\sum_i w_i\,\vec F_i}{\sum_i w_i}\]

여기서 \(\vec F_i\)는 \(i\)번째 점의 스프링 힘(가장 가까운 경계를 향한 화살표), \(w_i\)는 그 점을 얼마나 믿을지 나타내는 가중치입니다. 회전과 크기도 같은 방식으로, 각 힘에 “중심에서 얼마나 떨어져 있나”를 곱해 평균 냅니다. 이렇게 4자유도를 한꺼번에 고친 뒤, 다시 스프링을 계산하고, 또 고칩니다. 기울임과 가로세로 비율까지 넣으면 6자유도가 됩니다.

이름의 “Max”는 전자기학의 맥스웰에서 따왔고 특허는 점들을 “쌍극자(dipole)”라고 부르지만, Horn 교수는 스프링 비유가 물리적으로 훨씬 맞다고 말합니다. 전체 스프링에 쌓인 에너지가 가장 작아지는 자세를 찾는 문제, 즉 큰 최소제곱(least squares) 문제입니다.

점들에 직선 맞추기, 제대로

강의는 거리 이야기를 이어 점들에 가장 잘 맞는 직선을 찾는 법도 다룹니다. 짧은 경계 조각들을 이어 긴 경계로 만들 때 쓰입니다.

학교에서 배우는 \(y = mx + b\) 맞추기는 세로 방향 차이만 줄입니다. 그래서 거의 수직인 직선에서는 엉뚱한 답을 내고, 좌표축을 돌리면 답이 바뀝니다.

왼쪽은 세로 차이만 줄여서 직선이 눕고, 오른쪽은 직선까지의 수직 거리를 줄여서 점들을 제대로 따라갑니다.

대신 직선을 14강에서 본 각도 \(\theta\)와 거리 \(\rho\)로 나타내고, 각 점에서 직선까지의 수직 거리 제곱합을 줄이면 깔끔한 답이 나옵니다.

1. 최적의 직선은 반드시 점들의 평균 위치(무게중심)를 지납니다.
2. 무게중심을 원점으로 옮긴 좌표 \(x', y'\)로 각도를 바로 계산합니다.

\[\tan 2\theta = \frac{2\sum x'y'}{\sum (x'^2 - y'^2)}\]

이 답은 좌표계를 어떻게 잡든 똑같고, 수직선에서도 문제가 없습니다.

빠른 필터: 빼서 듬성듬성하게 만들기

PatMax처럼 여러 해상도에서 일하려면 사진을 줄이기 전에 흐리게(저주파 통과 필터) 해야 합니다. 그러지 않으면 가짜 무늬가 생깁니다(에일리어싱). 문제는 넓은 필터일수록 계산이 오래 걸린다는 점입니다.

강의 후반에 나오는 또 다른 특허(US 6,457,032)의 요령은 이렇습니다.

상자 모양 필터를 이웃끼리 빼면(차분) 양 끝의 바늘 두 개만 남습니다. 바늘과 계산한 뒤 누적해 더하면 원래 결과와 똑같습니다.

1. 필터를 이웃 값끼리 빼면(차분) 대부분 0이 되고 바늘 몇 개만 남습니다. 상자 모양은 한 번, 삼각형 모양은 두 번 빼면 됩니다.
2. 신호를 그 바늘 몇 개와만 계산합니다. 덧셈 몇 번이면 끝납니다.
3. 마지막에 누적해서 더하기를 뺀 횟수만큼 하면, 빼기를 정확히 되돌려 원래 필터 결과가 나옵니다.

빼기와 더하기가 서로를 지우고, 컨볼루션은 순서를 바꿔도 결과가 같기 때문에 가능한 일입니다. 강의는 이것을 “빼기로 압축하고, 더하기로 압축을 푼다”고 설명합니다. 가장 좋은 점은 필터 폭과 상관없이 일의 양이 같다는 것입니다. 폭이 10칸이든 300칸이든 바늘 개수는 그대로라서, 여러 해상도에 딱 맞습니다. 2D 사진에서는 가로로 한 번, 세로로 한 번 1D 필터를 걸어 같은 효과를 냅니다.

직접 해 보기

① PatMax 당기기. 주황 점 묶음(사진에서 찾은 경계)을 끌어 옮기거나 회전·크기 슬라이더로 흐트러뜨린 뒤, “한 번 당기기”를 몇 번 누르거나 “계속 당기기”를 눌러 보세요.

처음 상태에서 30번쯤 당기면 스프링 평균 길이가 1픽셀 아래로 내려가고, 회전은 0°, 크기는 1.00 근처로 돌아옵니다. 반대로 회전을 90° 넘게 돌려 놓고 당기면 엉뚱한 자세에 멈추기도 합니다. PatMax가 좋은 처음 추측을 필요로 하는 이유입니다. “크기도 맞추기”를 끄면 3자유도로만 맞춥니다.

② 바늘로 필터 걸기. 필터 모양과 폭을 바꿔 보세요. 파란 선(그냥 계산)과 주황 점선(바늘 + 누적합)은 항상 겹치는데, 아래 숫자를 보면 계산량은 전혀 다릅니다.

폭을 아무리 넓혀도 바늘 방식의 계산 횟수는 상자 3번, 삼각형 5번 그대로입니다. 두 결과의 차이는 컴퓨터의 반올림 오차 수준입니다.

정리

• PatMax는 PatQuick이 준 대략의 자세에서 출발해, 칸으로 나누지 않고 반복해서 고쳐 서브픽셀 정확도를 얻습니다.
• 학습 때 만든 거리 지도가 “경계가 어느 쪽에, 얼마나 멀리 있는지”를 알려 줍니다.
• 경계 점마다 스프링을 달고 힘·돌림힘·확대 힘의 평균으로 이동·회전·크기를 한꺼번에 고칩니다.
• 필터를 차분해 바늘 몇 개로 만들면, 필터 폭과 상관없이 같은 비용으로 흐리기를 할 수 있습니다.

지금까지 공부한 내용은 여기까지입니다. 다음 강의를 공부하는 대로 이어서 올리겠습니다.

참고: MIT 6.801/6.866 Machine Vision (Fall 2020), Berthold Horn · Ryan Sander · Tadayuki Yoshitake 강의 노트 (MIT OpenCourseWare, CC BY-NC-SA 4.0)