[MIT 머신비전 12강] 계산 분자로 미분하고 경계선 다듬기 | 라플라시안·비최대 억제(NMS)·CORDIC

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

한 줄 요약: 이웃 픽셀에 가중치를 매겨 더하는 작은 틀(계산 분자)로 미분을 흉내 낼 수 있고, 간단한 다항식을 대 보면 제대로 만들었는지 확인할 수 있습니다. 여기에 방향을 가리지 않는 라플라시안, 비최대 억제, 치우침 보정, 덧셈만 쓰는 각도 계산(CORDIC)이 모이면 1/40 픽셀까지 재는 경계 검출기가 됩니다.

계산 분자는 제대로 만들었을까?

지난 글에서 이웃 픽셀끼리 빼서 기울기를 구했습니다. 이렇게 이웃 몇 칸에 가중치를 곱해 더하는 작은 틀을 Horn 교수는 계산 분자(computational molecule), 또는 스텐실이라고 부릅니다. 1차 미분 분자 \([-1,\ 1]\)을 한 번 더 겹치면 2차 미분 분자가 나옵니다.

\[[-1,\ 1] \otimes [-1,\ 1] = [1,\ -2,\ 1]\]

\(\otimes\)는 한 틀을 다른 틀 위로 미끄러뜨리며 겹쳐 더하는 연산(합성곱)입니다. 미분은 “모양을 옮겨도 똑같이 동작하고, 더한 것의 미분은 미분의 합”이라는 성질이 있어서, 이렇게 틀을 겹치는 방식으로 계산할 수 있습니다.

그런데 이 분자가 정말 2차 미분을 재는지 어떻게 확인할까요? 가장 쉬운 방법은 답을 아는 함수를 대 보는 것입니다.

세 점에 가중치를 곱해 더하면 \(x^2\)에서는 2, \(x\)와 상수에서는 0이 나옵니다. 진짜 2차 미분과 똑같습니다.

일반적으로 \(N\)차 미분 분자는 0차부터 \(N\)차까지의 다항식을 모두 대 봐서 맞으면 믿을 만합니다. 그리고 미분 분자의 가중치는 항상 더해서 0이어야 합니다. 평평한 곳(상수)에서는 미분이 0이어야 하니까요.

분자를 크게 만들면(더 많은 픽셀을 쓰면) 잡음은 더 잘 걸러지지만, 계산이 늘고 가까이 붙은 두 경계가 서로 간섭하기 시작합니다. 공짜는 없습니다.

라플라시안: 방향을 가리지 않는 분자

경계는 2차 미분이 0을 지나는 곳이기도 했습니다. 2차원에서 그 역할을 하는 게 라플라시안 \(\nabla^2 E = E_{xx} + E_{yy}\)입니다. 라플라시안은 좌표를 어느 방향으로 돌려도 값이 같은, 가장 간단한(차수가 가장 낮은) 선형 연산입니다. 그러니 분자도 방향을 가리지 않아야 좋은 분자입니다.

후보는 둘입니다. 상하좌우 이웃을 쓰는 + 모양, 대각선 이웃을 쓰는 × 모양(이웃까지 거리가 \(\sqrt2\)배라 2로 나눕니다). 그런데 둘 다 방향에 따라 반응이 조금씩 다릅니다. Horn 교수의 요령은 둘을 4 : 1로 섞는 것입니다.

\[\nabla^2 E \approx \frac{1}{6\varepsilon^2} \begin{bmatrix} 1 & 4 & 1 \\ 4 & -20 & 4 \\ 1 & 4 & 1 \end{bmatrix}\]

\(\varepsilon\)은 픽셀 간격입니다. 계산은 조금 늘지만, 오차가 한 단계 더 높은 차수로 밀려나서 훨씬 정확해집니다.

같은 굵기의 물결무늬를 0°부터 360°까지 돌려 가며 대 봤습니다. + 모양은 네모나게, × 모양은 꽃잎처럼 찌그러지는데, 섞은 분자는 거의 동그랗습니다(방향 차이 약 1%).

참고로 픽셀이 육각형으로 놓인 격자라면 더 간단합니다. 가운데 −6, 둘레 여섯 칸 모두 1인 분자가 처음부터 고르게 반응합니다.

비최대 억제: 문턱값으로 자르지 않기

기울기 분자를 사진 전체에 대면 거의 모든 곳에서 작은 값이 나옵니다. 가장 쉬운 생각은 “어떤 값보다 크면 경계”라고 문턱값으로 자르는 것입니다. 하지만 이건 너무 이른 결정입니다. 한번 버린 픽셀은 뒤 단계에서 다시 살아나지 못합니다. 특허의 저자들도 문턱값을 권하지 않습니다.

문턱값만 쓰면 센 경계는 두꺼운 띠가 되고, 대비가 약한 사각형은 통째로 사라집니다. 비최대 억제는 셋 다 한 픽셀 두께로 남깁니다.

대신 비최대 억제를 씁니다. 기울기 방향(8방향 중 가까운 것)으로 앞뒤 이웃과 비교해서, 자기가 가장 클 때만 남깁니다. 조건을 \(G_0 > G_-\), \(G_0 \ge G_+\)처럼 한쪽만 등호를 넣는 건, 두 픽셀 값이 똑같을 때 하나만 고르기 위한 작은 장치입니다.

픽셀 이하 위치를 끝까지 다듬기

봉우리 세 값에 포물선을 맞춘 다음에도 다듬을 거리가 남아 있습니다.

• 방향 보정: 이웃은 8방향으로 반올림해서 골랐으니, 찾은 위치를 진짜 기울기 방향의 선 위로 옮겨 줍니다.
• 치우침 보정: 포물선이나 삼각형으로 찾은 봉우리 위치는 경계가 픽셀 안 어디에 있느냐에 따라 규칙적으로 조금씩 어긋납니다. 특허는 원래 값 \(s\)를 \(s' = s\,\lvert 2s\rvert^{b}\) 꼴의 곡선으로 고치고, 보간 방법에 따라 알맞은 \(b\)를 고릅니다.

흐림이 1픽셀인 경계에서 잰 오차입니다. 포물선은 가운데 쪽으로, 삼각형은 바깥쪽으로 치우칩니다. 치우침이 규칙적이라 곡선 하나로 미리 고쳐 둘 수 있습니다.

치우침의 모양은 경계가 얼마나 흐린지에도 달려 있습니다. 경계가 흐려지는 큰 원인은 초점 어긋남입니다. 초점이 정확히 맞으면 점 하나는 점 하나로 찍히지만, 센서가 초점면에서 조금 벗어나면 점이 작은 원판으로 번집니다. 렌즈가 클수록, 초점이 많이 어긋날수록 원판이 커집니다.

원판이 경계를 가로질러 미끄러지면, 밝은 쪽에 걸친 원판 넓이만큼 밝기가 오릅니다. 이 모양을 계산으로 알 수 있으니 정답과 비교해 오차를 재고 보정할 수 있습니다.

경계는 사진마다 스케일도 다릅니다. 한 픽셀 만에 바뀌는 날카로운 경계가 있는가 하면, 여러 픽셀에 걸쳐 천천히 바뀌는 흐린 경계도 있습니다. 작은 분자 하나로는 둘 다 잘 잡기 어려워서, 사진을 여러 단계로 흐려 가며 경계를 찾는 다중 스케일 방법이 중요해집니다.

CORDIC: 덧셈과 반으로 나누기만으로 각도 구하기

기울기 \((E_x, E_y)\)를 크기와 각도로 바꾸려면 제곱근과 아크탄젠트가 필요한데, 하드웨어에서는 둘 다 비쌉니다. CORDIC은 이걸 덧셈과 뺄셈, 그리고 2로 나누기(비트를 한 칸 밀기)만으로 해냅니다.

방법은 이렇습니다. 화살표를 x축 쪽으로 조금씩 돌리되, 돌리는 각도를 \(\tan\theta = 1/2,\ 1/4,\ 1/8, \dots\)인 것으로만 고릅니다. 그러면 회전 계산의 곱셈이 전부 “반으로 나누기”로 바뀝니다. 화살표가 x축 위에 있으면 시계 방향, 아래에 있으면 반시계 방향으로 돌리고, 돌린 각도를 모두 더하면 원래 각도가 됩니다.

일곱 단계 만에 진짜 각도 33.85°에 0.1° 이내로 다가갑니다. 단계가 하나 늘 때마다 정밀도가 대략 두 배가 됩니다.

이렇게 돌리면 화살표 길이가 매번 조금씩 늘어나는데, 늘어나는 비율은 처음부터 정해져 있습니다(전부 곱하면 약 1.16). 그래서 마지막에 이 값으로 한 번 나누면 크기도 함께 나옵니다. 특허의 장치는 먼저 \(\lvert E_x\rvert\), \(\lvert E_y\rvert\)를 비교해 화살표를 0°~45° 구간으로 접어 넣고 시작합니다.

직접 해 보기

① 계산 분자로 경계 찾기. 분자 종류를 바꾸고, 문턱값·잡음·흐리기 막대를 움직여 보세요. 비최대 억제를 끄면 경계가 두꺼워지고, 라플라시안은 잡음에 더 민감합니다. 오른쪽 아래의 흐릿한 원은 흐리기(스케일)를 올려야 잡힙니다.

② CORDIC 돌려 보기. 주황 화살표의 끝을 끌어 기울기를 정하고, 단계 수를 늘려 보세요. 파란 화살표가 x축으로 붙어 갈수록 각도 추정이 진짜 값에 다가갑니다.

정리

• 계산 분자는 이웃 픽셀에 가중치를 곱해 더하는 작은 틀이고, 다항식을 대 보면 맞게 만들었는지 확인할 수 있습니다. 미분 분자의 가중치 합은 0입니다.
• 라플라시안은 + 모양과 × 모양 분자를 4 : 1로 섞으면 방향에 거의 상관없이 고르게 반응합니다.
• 문턱값으로 일찍 자르기보다 비최대 억제로 봉우리만 남기고, 방향 보정과 치우침 보정으로 위치를 끝까지 다듬습니다.
• CORDIC은 정해진 작은 각도들로만 돌려서, 곱셈 없이 기울기의 각도와 크기를 구합니다.

다음 글: [MIT 머신비전 13강] 사진 속에서 그 물건 찾기: 템플릿 매칭과 PatQuick

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