[MIT 머신비전 14강] 점들이 투표해서 직선을 찾는다: 허프 변환 | 허프 변환(Hough Transform)과 호모그래피

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

한 줄 요약: 사진 속 점 하나하나가 “나를 지나는 직선은 이것들이야”라고 투표하면, 표가 가장 많이 모인 칸이 진짜 직선입니다. 선이 끊겨 있거나 잡음 점이 섞여 있어도 잘 찾습니다. 이 글에서는 그 전에 “자세의 가짓수”와 비스듬히 본 평면(호모그래피)도 짧게 짚습니다.

자세는 몇 가지 숫자로 정해질까

지난 글의 PatQuick은 탐침 점을 여러 자세로 옮겨 보며 점수를 매겼습니다. 그런데 “자세”를 정하려면 숫자가 몇 개나 필요할까요?

평면 위 모양을 바꾸는 방법은 이동(2개), 회전, 크기, 기울임, 가로세로 비율(각 1개)로 모두 6개 숫자입니다.

이 6개를 모두 합친 변환을 아핀 변환이라고 합니다. 자유롭게 표현할 수 있지만 대가가 있습니다. 숫자마다 후보를 10개씩만 잡아도 6개면 10의 6제곱, 백만 가지 자세를 시험해야 합니다. 자유도가 하나 늘 때마다 일이 몇 배씩 불어납니다.

한 가지 함정도 있습니다. 이동·회전·크기 변화는 경계의 방향 관계를 그대로 두지만, 기울임과 가로세로 비율은 경계에 수직인 방향을 바꿔 놓습니다. 그래서 PatQuick은 탐침의 방향도 함께 변환해서 비교합니다.

비스듬히 본 평면: 호모그래피

이번에는 3D로 넘어갑니다. 바닥에 놓인 체스판을 카메라로 비스듬히 찍으면, 네모 칸이 사다리꼴로 찌그러져 보입니다.

평면 위의 점이 사진의 어디에 찍히는지는 3×3 행렬 하나로 정해집니다. 주황 점이 어디로 갔는지 따라가 보세요.

보통은 “카메라 기준 위치 = 회전 × 세상 위치 + 이동”을 계산한 뒤 원근으로 나눠야 합니다. 그런데 찍는 대상이 평면 하나(높이 0인 바닥)라면, 회전과 이동을 3×3 행렬 하나로 합칠 수 있습니다. 이 행렬을 호모그래피라고 부릅니다.

• 카메라의 자세는 위치 3개 + 방향 3개, 모두 6자유도입니다.
• 회전 행렬은 숫자가 9개지만 “각 줄은 길이 1, 서로 수직”이라는 조건 6개가 걸려 있어서 실제로는 3자유도입니다.
• 호모그래피는 전체에 같은 수를 곱해도 같은 결과를 줍니다. 원근 투영은 비율만 보기 때문입니다.

호모그래피는 다음 글들에서 3D 위치를 다룰 때 다시 나옵니다.

허프 변환: 점이 직선에 투표한다

이제 오늘의 주인공입니다. 공장 사진에서 직선 모양 모서리를 찾고 싶은데, 선이 군데군데 끊겨 있고 엉뚱한 잡음 점도 섞여 있습니다. 경계 점을 이어 붙이는 방법은 끊긴 곳에서 길을 잃습니다.

허프 변환은 1960년에 특허로 출원된(1962년 등록) 아주 오래된 아이디어입니다. 생각을 뒤집는 것이 핵심입니다.

• 직선은 기울기 \(m\)과 절편 \(c\), 숫자 두 개로 정해집니다(\(y = mx + c\)).
• 점 하나 \((x, y)\)를 지나는 직선은 무수히 많은데, 그 모든 \((m, c)\)를 모으면 \(c = y - xm\), 즉 \((m, c)\) 평면 위의 직선 하나가 됩니다.
• 같은 직선 위의 점들이 만드는 이 직선들은 모두 한 점에서 만납니다. 그 점이 바로 찾는 \((m, c)\)입니다.

① 파란 점은 한 직선 위, 회색 점은 잡음입니다. ② 점마다 선 하나를 그리면 파란 선들이 한 점에 모입니다. ③ 실제로는 각도·거리 투표함을 쓰고, 가장 진한 칸이 답입니다.

컴퓨터는 \((m, c)\) 평면을 바둑판 칸으로 나눈 투표함(누적 배열)을 만들고, 점마다 자기 선이 지나는 칸에 한 표씩 넣습니다. 표가 가장 많이 쌓인 칸이 답입니다. 끊긴 부분이 있어도 남은 점들의 표가 같은 칸에 모이고, 잡음 점의 표는 여기저기 흩어집니다.

한 가지 손질이 필요합니다. 세로로 선 직선은 기울기가 무한대라 칸에 담을 수 없습니다. 그래서 실제로는 직선을 원점에서 직선까지의 거리 \(\rho\)와 그 방향 각도 \(\theta\)로 나타냅니다.

\[\rho = x\cos\theta + y\sin\theta\]

이렇게 하면 점 하나는 투표함에 직선 대신 물결 모양 곡선을 그리지만, 원리는 똑같습니다.

원도 찾을 수 있다

허프 변환은 직선 전용이 아닙니다. 숫자 몇 개로 정해지는 모양이면 무엇이든 됩니다. 원이 좋은 예입니다.

왼쪽: 반지름을 알면 점마다 “중심이 있을 수 있는 원”을 그리고, 원들이 겹치는 곳이 중심입니다. 오른쪽: 반지름까지 모르면 점마다 원뿔이 생기고, 원뿔들이 만나는 곳이 답입니다.

강의에서는 휴대폰 위치 찾기를 예로 듭니다. 기지국까지 신호가 오가는 시간을 재면 “기지국에서 몇 km 떨어져 있다”는 것만 압니다. 가능한 위치는 원 하나입니다. 기지국 하나로는 위치를 못 정하지만, 원 하나가 후보를 크게 줄여 줍니다. 기지국 세 곳의 원이 겹치는 곳이 내 위치입니다.

반지름도 모르면 투표함이 (중심 x, 중심 y, 반지름) 3차원이 됩니다. 점 하나는 위로 벌어지는 원뿔 모양으로 표를 던지고, 원뿔들이 겹치는 곳이 답입니다. 차원이 하나 늘었으니 칸 수도, 일도 그만큼 늘어납니다.

작게 줄여서 빠르게: 여러 해상도

모든 일을 원본 크기로 하면 느립니다. 그래서 사진을 반씩 줄인 여러 크기(피라미드)를 만들어, 작은 사진에서 대충 찾고 큰 사진에서 다듬습니다. 어떤 특징은 오히려 작은 사진에서 더 또렷하게 보이기도 합니다.

줄인 사진을 끝없이 만들어도 전체 일은 원본의 4/3배(1/2씩) 또는 2배(1/√2씩)에 그칩니다.

한 번 줄일 때 면적이 \(r\)배가 된다면, 모든 층을 합친 일의 양은 다음과 같습니다.

\[1 + r + r^2 + \cdots = \frac{1}{1 - r}\]

가로세로를 반씩 줄이면 \(r = 1/4\)이라 4/3배, 면적을 반씩만 줄이면 \(r = 1/2\)이라 2배입니다. 반씩 줄이기는 너무 과격해서 무늬가 뭉개지거나 가짜 무늬(에일리어싱)가 생길 수 있습니다. 면적만 반으로 줄이려면 체스판의 검은 칸만 골라 쓰면 되는데, 45° 돌려 보면 그것도 반듯한 격자입니다. 강의 노트는 SIFT 같은 특징점 알고리즘이 이런 덜 과격한 줄이기를 쓴다고 소개합니다.

직접 해 보기

① 직선 찾기. 왼쪽 사진을 눌러 점을 찍거나 점을 끌어 보세요. 오른쪽 투표함에 곡선이 하나씩 더해지고, 곡선이 가장 많이 겹친 곳(주황 원)이 왼쪽의 주황 직선이 됩니다. 투표함 위에 마우스를 올리면 그 칸에 해당하는 직선이 점선으로 보입니다.

직선 위 점 몇 개를 멀리 끌어내 선을 더 끊어 보세요. 남은 점만으로도 봉우리가 그대로 남습니다. “직선 두 개”를 누르면 봉우리도 두 개 생깁니다.

② 원 찾기. 원의 일부만 보이는 점들과 잡음 점이 있습니다. “찾는 반지름” 슬라이더를 움직여 보세요. 반지름이 맞으면 투표 원들이 한 점에 모이고, 동의하는 점 수가 확 늘어납니다.

슬라이더를 움직이는 것이 바로 3차원 투표함의 “반지름” 축을 한 층씩 훑어보는 일입니다.

정리

• 평면 위 자세는 이동·회전·크기·기울임·가로세로 비율, 모두 6개 숫자(아핀 변환)로 정해지고, 숫자가 늘수록 시험할 자세가 폭발적으로 늘어납니다.
• 평면을 비스듬히 찍은 사진은 3×3 행렬 하나(호모그래피)로 설명되며, 이 행렬은 전체 크기를 뺀 비율만 의미가 있습니다.
• 허프 변환은 점마다 “나를 지나는 모양들”에 투표하게 하고, 표가 가장 많이 모인 칸을 답으로 고릅니다. 끊긴 선과 잡음에 강합니다.
• 줄인 사진을 여러 층 쌓아도 전체 일은 원본의 4/3배나 2배 정도면 됩니다.

다음 글: [MIT 머신비전 15강] 스프링으로 끌어당겨 맞추기: PatMax와 거리 지도

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