[MIT 머신비전 16강] 찍기 전에 흐려야 하는 이유: 에일리어싱과 적분 영상 | 나이퀴스트·블록 평균·sinc

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

한 줄 요약: 사진을 일정 간격으로 찍으면, 간격보다 빠르게 변하는 무늬는 느린 무늬로 둔갑합니다. 그래서 찍기 전에 살짝 흐려야 하고, 흐리기는 적분 영상(누적합 표)을 쓰면 상자 크기와 상관없이 덧셈·뺄셈 몇 번으로 끝납니다. 다만 상자 모양 흐리기는 완벽하지 않아서, 여러 번 겹치거나 다른 필터와 짝지어 씁니다.

왜 찍기 전에 흐릴까

15강의 PatMax는 사진을 여러 해상도로 줄여 가며 일합니다. 이때 줄이기 전에 꼭 흐리게(저주파 통과 필터) 만들었습니다. 이유는 “찍기”(샘플링) 자체에 함정이 있기 때문입니다.

물결 모양 신호를 일정 간격으로 찍어 봅시다.

한 주기에 1번만 찍으면 매번 같은 높이라 평평한 선으로 보입니다. 2번이면 봉우리를 찍었을 때만 겨우 되고, 2번보다 많이 찍어야 확실합니다.

• 1주기에 1번: 찍을 때마다 물결의 같은 자리라서 값이 늘 같습니다. 물결이 있었다는 사실조차 사라집니다.
• 1주기에 정확히 2번: 봉우리와 골을 찍으면 복원되지만, 운 나쁘게 0을 지나는 자리만 찍으면 전부 0입니다.
• 2번보다 많이: 점들만 보고도 원래 물결을 정확히 다시 그릴 수 있습니다.

이것이 나이퀴스트 샘플링 정리입니다. 가장 빠르게 변하는 성분의 2배보다 빠르게 찍어야 합니다.

\[f_{\text{찍기}} > 2 f_{\max}\]

점들로 다시 그릴 때는 각 점 자리에 sinc 함수(가운데가 솟고 양옆으로 잔물결이 퍼지는 모양)를 하나씩 놓고 모두 더합니다.

빠른 물결이 느린 물결로 둔갑한다

조건을 어기면 어떻게 될까요? 칸마다 한 번씩 찍는데 물결이 칸당 0.8번 출렁인다고 합시다.

주황 점만 보면 빠른 물결(회색)인지 느린 물결(파랑)인지 구별할 수 없습니다.

찍은 점은 빠른 물결과 칸당 0.2번짜리 느린 물결을 정확히 똑같이 지납니다. 점만 가진 사람은 느린 물결이라고 믿게 되죠. 이 현상이 에일리어싱(alias = 가명)입니다. 빠른 성분이 느린 성분의 이름을 빌려 끼어드는 겁니다.

식으로는 이렇습니다. 찍는 간격이 \(1/f_s\)일 때 \(k\)번째 점의 값은

\[s_k = \cos\!\left(2\pi \frac{f_0}{f_s} k\right) = \cos\!\left(2\pi \frac{f_s - f_0}{f_s} k\right)\]

\(k\)가 정수라서 각도에 \(2\pi k\)를 빼도 값이 같고, 코사인은 좌우 대칭이기 때문입니다. 위 그림에서는 \(f_s = 1\), \(f_0 = 0.8\)이니 \(f_s - f_0 = 0.2\)로 보입니다.

중요한 점은 한번 찍고 나면 되돌릴 수 없다는 것입니다. 둔갑한 성분과 원래의 느린 성분이 섞여 버렸기 때문입니다. 그래서 흐리기는 반드시 찍기 전에 해야 합니다.

적분 영상: 상자 평균을 공짜에 가깝게

가장 간단한 흐리기는 상자 평균(블록 평균)입니다. 주변 칸들을 모두 더해 개수로 나누면 됩니다. 문제는 상자가 클수록 더할 칸이 많아진다는 점입니다. 2D에서 반지름을 두 배로 키우면 일은 네 배가 됩니다.

해결책은 누적합 표를 미리 만들어 두는 것입니다. 1D에서는 첫 칸부터 \(i\)번째 칸까지의 합 \(G_i\)를 적어 둡니다.

\[G_i = \sum_{k=1}^{i} g_k\]

그러면 어떤 구간의 합이든 뺄셈 한 번입니다.

\[\sum_{k=i+1}^{j} g_k = G_j - G_i\]

2D에서는 원점부터 \((x, y)\)까지 사각형 안의 합을 적어 둡니다. 이것을 적분 영상(integral image, 다른 분야에서는 summed-area table)이라고 부릅니다.

오른쪽: 큰 사각형에서 위쪽 띠와 왼쪽 띠를 빼면 왼쪽 위 구석이 두 번 빠지므로 한 번 더해 줍니다.

상자 합은 네 모서리 값으로 끝납니다.

\[\text{상자 합} = G(\text{오른쪽 아래}) - G(\text{오른쪽 위}) - G(\text{왼쪽 아래}) + G(\text{왼쪽 위})\]

• 표를 만드는 비용은 처음 한 번뿐입니다.
• 그 뒤로는 상자가 3×3이든 300×300이든 덧셈·뺄셈 3번입니다.
• 밝기뿐 아니라 기울기, 기울기 방향 히스토그램(HoG) 같은 값에도 똑같이 쓸 수 있고, 차원이 늘어도 일반화됩니다.

상자 평균은 얼마나 좋은 필터일까

상자로 흐리면 빠른 물결이 얼마나 줄어들까요? 이걸 보려면 필터를 주파수 쪽에서 봐야 합니다. 폭 \(\delta\)인 상자를 푸리에 변환하면 sinc 함수가 나옵니다.

\[H(\omega) = \frac{\sin(\delta\omega/2)}{\delta\omega/2}\]

여기서 \(\omega\)는 물결의 빠르기(각주파수)이고, \(H(\omega)\)는 그 빠르기의 물결이 필터를 지난 뒤 몇 배로 남는지입니다.

이상적인 필터(점선)는 느린 물결은 그대로, 빠른 물결은 0으로 만듭니다. sinc는 그 근처에 가지만 잔물결이 남습니다.

이상적인 필터에 비하면 아쉬운 점이 두 가지입니다.

1. 빠른 물결이 완전히 사라지지 않습니다. 잔물결이 계속 남고, 음수 쪽으로 뒤집혀 나오기도 합니다.
2. 첫 0점이 늦게 옵니다. \(\delta\omega/2 = \pi\), 즉 \(\omega = 2\pi/\delta\)에서야 처음 0이 됩니다.

카메라도 사실 이런 상자 평균을 하고 있습니다. 픽셀마다 넓이가 있어서 그 안에 들어온 빛을 모두 더하기 때문입니다. 하지만 이것만으로는 에일리어싱을 막기에 부족한 경우가 많습니다.

여러 번 겹치면 나아진다

상자 필터를 두 번 걸면 어떨까요? 상자 두 개를 합성곱하면 삼각형이 되고, 공간에서 합성곱은 주파수에서 곱하기이므로 응답은 \(\text{sinc}^2\)이 됩니다.

\[y_2 = (f \otimes b) \otimes b = f \otimes (b \otimes b) \quad\longleftrightarrow\quad Y_2 = F \cdot B^2\]

• 빠른 물결이 \(1/\omega\)이 아니라 \(1/\omega^2\)로 줄어듭니다.
• \(N\)번 겹치면 \(1/\omega^N\)로 줄어듭니다.
• 다만 너무 많이 겹치면 살려야 할 느린 물결까지 깎이니 적당히 멈춥니다.

삼각형 필터는 15강의 바늘 요령으로 두 번 빼고 두 번 누적합하면 되고, 상자는 적분 영상으로 하면 되니 어느 쪽이든 빠릅니다.

미분과 적분도 같은 틀로 볼 수 있습니다. 미분은 주파수에서 \(j\omega\)를 곱하는 것이라 빠른 성분을 키우고, 적분(계단 함수와의 합성곱)은 \(1/(j\omega)\)를 곱하는 것이라 빠른 성분을 줄입니다. 둘을 같은 횟수만큼 걸면 서로 지워져 원래 신호로 돌아옵니다. 15강의 “빼서 압축하고 더해서 푼다”가 바로 이 원리였습니다.

컴퓨터로 푸리에 변환할 때의 함정

이산 푸리에 변환(DFT, 빠른 버전이 FFT)은 신호를 끝없이 반복되는 것으로 취급합니다. 그래서 신호의 끝과 처음이 다른 높이라면, 이어 붙인 자리에 없던 절벽이 생깁니다.

절벽은 높은 주파수를 잔뜩 만들어 냅니다. 거울처럼 뒤집어 붙이면 이어지는 자리가 매끄러워집니다.

강의에 재미있는 일화가 나옵니다. 한때 “자연 사진의 세기는 주파수가 올라갈수록 \(1/\omega\)로 줄어든다”고 믿었는데, 알고 보니 이 이어 붙이기 절벽 때문에 생긴 착시였다고 합니다. 대처법은 두 가지입니다.

• 가장자리 줄이기(apodizing): 해밍 창처럼 양 끝이 0으로 가는 모양을 곱해 끝을 부드럽게 만듭니다.
• 거울 붙이기: 신호를 뒤집어 이어 붙여 끊김을 없앱니다. 그러면 세기가 \(1/\omega^2\)로 줄어드는 제 모습이 보입니다.

렌즈 앞에서 미리 흐리기: 복굴절판

찍기 전에 흐려야 한다면, 디지털 계산으로는 이미 늦습니다. 센서에 닿는 순간 찍히니까요. 그래서 카메라는 빛 단계에서 흐립니다.

복굴절판은 들어온 빛을 살짝 어긋난 두 갈래로 나눕니다. 점 하나가 \(\epsilon\)만큼 떨어진 두 점으로 찍히는 셈입니다.

\[h(x) = \tfrac{1}{2}\delta\!\left(x + \tfrac{\epsilon}{2}\right) + \tfrac{1}{2}\delta\!\left(x - \tfrac{\epsilon}{2}\right) \quad\longleftrightarrow\quad H(\omega) = \cos\!\left(\frac{\epsilon\omega}{2}\right)\]

\(\delta(x)\)는 한 점에만 몰린 바늘 모양 함수(임펄스)입니다.

코사인은 \(\omega = \pi\)에서, 픽셀 평균은 \(2\pi\)에서 0이 됩니다. 둘을 곱하면 샘플링 한계 너머가 고르게 눌립니다.

픽셀 평균과 복굴절판을 함께 쓰면 서로의 빈틈을 메워 줍니다. 사진에서는 가로·세로 두 방향이 필요하니 판 두 장을 90° 돌려 겹칩니다.

그 밖의 이야기

• 보간도 합성곱입니다. 가장 가까운 점 값 쓰기(최근접 보간)는 상자와의 합성곱, 점들을 직선으로 잇기(선형 보간)는 삼각형과의 합성곱입니다. 3차 보간처럼 넓은 필터는 더 매끄럽지만 이웃을 더 많이 봐야 합니다.
• 둥근 저주파 필터를 2D에서 거꾸로 변환하면 베셀 함수 \(J_1\)이 들어간 모양이 나옵니다. 현미경의 점 퍼짐 함수가 이 모양이고, 초점이 흐려진 렌즈(둥근 원반)의 주파수 응답도 같은 꼴입니다.
• 좋은 필터일수록 폭(0이 아닌 구간, support)이 넓어 계산이 비싸집니다. 그래서 0이 아닌 값의 개수를 줄이는 요령(바늘, 적분 영상)이 중요합니다.

직접 해 보기

① 둔갑하는 물결. 물결 빠르기를 0.5 위로 올려 보세요. 초록 선(점들만 보고 그린 신호)이 원래보다 느린 물결로 바뀝니다. 그다음 “찍기 전 상자 필터 횟수”를 1, 2로 올려 보세요.

0.8번/칸에서 필터 없이 찍으면 0.2번/칸짜리 물결이 세기 1.000 그대로 나타납니다. 상자 한 번이면 세기가 0.234, 두 번이면 0.055로 줄어 둔갑한 물결이 거의 안 보입니다. 1.0번/칸에서는 상자 필터가 정확히 0을 만들어 아예 사라집니다.

② 적분 영상으로 흐리기. 왼쪽 영상을 끌어 아무 상자나 그려 보고, 반지름 슬라이더를 움직여 보세요.

상자를 아무리 크게 그려도 적분 영상 쪽 계산은 네 모서리 값 세 번의 덧셈·뺄셈입니다. 반지름 20이면 그냥 더할 때 한 칸에 41×41 = 1681번이지만 적분 영상은 여전히 3번입니다.

정리

• 가장 빠른 성분의 2배보다 빠르게 찍어야 하고, 그러지 못하면 빠른 성분이 느린 성분으로 둔갑합니다. 찍은 뒤에는 되돌릴 수 없습니다.
• 그래서 찍기 전에 흐립니다. 상자 평균은 적분 영상을 쓰면 상자 크기와 상관없이 몇 번의 계산으로 끝납니다.
• 상자의 주파수 응답은 sinc라서 완벽하지 않습니다. 여러 번 겹치면 \(1/\omega^N\)로 더 잘 눌립니다.
• DFT의 이어 붙이기 절벽, 렌즈 앞 복굴절판처럼 “언제, 어디서 흐리는가”도 중요합니다.

다음 글부터는 저수준 영상 처리에서 벗어나 사진으로 위치와 방향을 재는 문제(사진 측량)로 넘어갑니다.

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