[MIT 머신비전 11강] 경계선을 픽셀보다 정밀하게 찾기 | 서브픽셀 에지 검출(Subpixel Edge Detection)

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

한 줄 요약: 경계선은 밝기가 가장 가파르게 바뀌는 곳입니다. 이웃 픽셀끼리 빼서 밝기의 기울기를 구하고, 기울기가 가장 큰 곳 근처의 값 세 개에 포물선을 맞추면 픽셀 한 칸보다 훨씬 작은 단위로 경계의 위치를 알 수 있습니다.

공장의 기계는 왜 경계선을 찾을까

강의는 재미있는 사실로 시작합니다. 반도체 회로 기판도, 알약 같은 의약품도 머신비전 없이는 만들 수 없습니다. 부품이 제자리에 놓였는지, 모양이 맞는지 카메라가 쉬지 않고 확인하기 때문입니다.

그때 가장 먼저 하는 일이 경계선 찾기입니다. 사진의 대부분은 밝기가 고른 넓은 영역이고, 정보는 영역과 영역이 만나는 경계에 몰려 있습니다. 그래서 픽셀 수백만 개를 다 들고 다니는 대신 경계선의 위치만 기록하면 훨씬 가볍게 물체를 설명할 수 있습니다.

밝기가 갑자기 바뀌는 곳만 남겨도 부품의 윤곽이 또렷하게 드러납니다. 사진: SparkFun Electronics, Wikimedia Commons (CC BY 2.0)

이번 강의는 실제 산업용 특허 하나(미국 특허 6,408,109)를 교재 삼아, 경계 위치를 픽셀의 1/40 정도까지 정확하게 찾는 방법을 뜯어봅니다.

경계란 무엇인가

어두운 바닥 위에 밝은 종이가 놓인 사진을 생각해 보세요. 종이 가장자리를 가로질러 밝기를 재면 어두운 값에서 밝은 값으로 올라갑니다. 경계는 이 오르막이 가장 가파른 곳입니다. 같은 자리를 세 가지로 말할 수 있습니다.

• 밝기 곡선이 휘는 방향이 바뀌는 곳(변곡점)
• 밝기의 기울기(1차 미분)가 가장 큰 곳
• 밝기의 2차 미분이 0을 지나가는 곳

세 그래프의 특별한 점(가장 가파른 곳, 봉우리, 0을 지나는 곳)이 모두 같은 위치에 있습니다.

재미있게도, 칼로 자른 듯 완벽하게 날카로운 경계는 오히려 위치를 정밀하게 잴 수 없습니다. 픽셀이 한 점씩 밝기를 찍는다면, 경계가 두 픽셀 사이 어디에 있든 값은 똑같이 “어둡다, 밝다”뿐이기 때문입니다(너무 급한 변화가 띄엄띄엄 찍히면서 생기는 앨리어싱 문제). 경계가 살짝 흐려서 한두 픽셀에 걸쳐 중간 밝기가 생겨야, 그 중간값의 비율로 픽셀 안의 위치를 읽어 낼 수 있습니다.

이웃 픽셀끼리 빼서 기울기 구하기

픽셀은 띄엄띄엄 있으니 미분은 이웃 값의 차이로 흉내 냅니다. 방법이 여럿인데, 정확도가 꽤 다릅니다.

앞쪽 이웃만 보거나 뒤쪽 이웃만 보면 곡선이 휜 만큼 한쪽으로 치우칩니다. 양쪽을 같이 보면 치우침이 서로 상쇄됩니다.

앞으로 차이와 뒤로 차이는 곡선이 휘어 있으면(2차 미분이 있으면) 그만큼 틀립니다. 둘을 평균한 가운데 차이는 이 오차가 상쇄되어, 남는 오차가 훨씬 작습니다.

\[f'(x) \approx \frac{f(x+\delta) - f(x-\delta)}{2\delta}, \qquad \text{오차} \approx \frac{\delta^2}{6} f'''(x)\]

\(\delta\)는 픽셀 간격입니다. 오차가 \(\delta\)가 아니라 \(\delta^2\)에 비례하니, 간격이 절반이 되면 오차는 4분의 1로 줄어듭니다. 그래서 꼭 픽셀 위에서 재지 않아도 된다면, 이웃한 두 픽셀로 두 픽셀 사이 한가운데의 기울기를 재는 편이 간격이 반이라 오차가 1/4로 줄어듭니다.

2차원에서 쓰는 작은 계산 틀

사진은 2차원이라 가로 기울기 \(E_x\)와 세로 기울기 \(E_y\)를 따로 구합니다. 이때 쓰는 작은 가중치 표를 커널, Horn 교수의 말로는 계산 분자라고 부릅니다.

로버츠 십자는 대각선 방향으로 뺍니다. 네 픽셀 커널은 네 픽셀 한가운데의 기울기를 재고, 소벨은 거기에 평균(흐리기)을 한 번 더 섞은 것입니다.

소벨 커널은 “네 픽셀 차이”에 “네 픽셀 평균”을 한 번 겹친 것입니다. 평균을 섞으면 잡음에는 강해지지만 사진이 살짝 흐려지는 대가가 있습니다. 양날의 검입니다.

두 기울기를 얻으면 크기와 방향으로 바꿉니다.

\[E_0 = \sqrt{E_x^2 + E_y^2}, \qquad \theta = \arctan\frac{E_y}{E_x}\]

\(E_0\)는 얼마나 가파른지, \(\theta\)는 어느 쪽으로 밝아지는지입니다. 특허의 장치는 제곱근과 아크탄젠트를 직접 계산하지 않고, 덧셈과 비트 밀기만으로 이 값을 구하는 CORDIC이라는 요령을 씁니다. 다음 강의에서 직접 돌려 봅니다.

전체 흐름: 기울기에서 봉우리까지

특허 속 장치는 크게 세 부분입니다. 기울기 추정기, 봉우리 검출기, 픽셀 이하 보간기.

기울기 크기는 경계 주변에 두툼한 띠로 나옵니다. 기울기 방향으로 이웃과 비교해 봉우리만 남기면 한 픽셀 두께의 선이 됩니다.

봉우리를 고를 때는 기울기 방향으로 앞뒤 이웃과 비교해서 자기가 가장 클 때만 남깁니다(비최대 억제, non-maximum suppression). 픽셀은 격자에 놓여 있으니 방향은 8개(정사각 격자)나 6개(육각 격자)로 반올림해서 이웃을 고릅니다.

봉우리에 포물선 맞추기

봉우리로 뽑힌 픽셀의 기울기를 \(G_0\), 기울기 방향 앞뒤 이웃을 \(G_+\), \(G_-\)라고 합시다. 진짜 봉우리는 대개 픽셀 한가운데가 아니라 그 사이 어딘가에 있습니다. 세 점을 지나는 포물선은 딱 하나뿐이니, 그 꼭대기를 경계 위치로 삼습니다.

\[s = \frac{G_+ - G_-}{2\,(2G_0 - G_+ - G_-)}\]

\(s\)는 가운데 픽셀에서 얼마나 떨어졌는지(픽셀 단위)입니다. \(G_0\)이 이웃보다 크다는 조건 덕분에 \(s\)는 늘 \(-\tfrac12\)에서 \(\tfrac12\) 사이입니다. 오른쪽 이웃이 더 크면 봉우리가 오른쪽으로 기울어지는, 아주 직관적인 식입니다. 포물선 대신 뾰족한 삼각형을 맞추는 방법도 있습니다.

막대 세 개만으로 진짜 봉우리(점선) 근처를 꽤 잘 맞힙니다. 그래도 조금 어긋나는데, 이 어긋남에는 규칙이 있습니다.

포물선만으로는 대략 1/10 픽셀 정도가 한계입니다. 1/40까지 가려면 렌즈가 얼마나 흐린지, 센서 픽셀이 면적의 얼마를 덮는지, 초점이 맞는지, 경계가 얼마나 부드럽게 바뀌는지까지 따져서 남은 치우침을 보정해야 합니다.

직접 해 보기

① 경계 위치 맞히기. 맨 위의 흰 원을 좌우로 끌어 진짜 경계를 옮겨 보세요. 픽셀 밝기 → 기울기 → 포물선 꼭대기 순서로 추정이 따라옵니다. 맨 아래 그래프는 경계가 픽셀 안 어디에 있느냐에 따라 오차가 어떻게 변하는지 보여 줍니다. 흐림, 잡음, 봉우리 모양을 바꿔 보세요.

오차가 0 근처에서 S자로 오르내리는 게 보이나요? 잡음이 없어도 생기는 이 규칙적인 치우침이 다음 강의에서 다룰 편향 보정의 대상입니다.

② 기울기 추정 비교. 곡선 위의 흰 점을 끌고, 픽셀 간격 \(\delta\)를 바꿔 보세요. 간격을 줄이면 가운데 차이의 오차가 다른 둘보다 훨씬 빨리 줄어듭니다.

정리

• 경계는 밝기가 가장 가파르게 바뀌는 곳이고, 기울기의 봉우리이자 2차 미분이 0을 지나는 곳입니다.
• 기울기는 이웃 픽셀의 차이로 구합니다. 양쪽을 같이 보는 가운데 차이가 한쪽만 보는 차이보다 훨씬 정확합니다.
• 기울기 크기와 방향을 구하고, 방향을 따라 봉우리만 남긴 뒤, 세 값에 포물선을 맞추면 픽셀보다 작은 단위로 경계를 찾습니다.
• 포물선만으로는 1/10 픽셀 정도이고, 남은 규칙적인 치우침까지 보정해야 1/40 픽셀에 이릅니다.

다음 글: [MIT 머신비전 12강] 계산 분자로 미분하고 경계선 다듬기

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