거리 변환

수치해석 컴퓨터 그래픽스 마지막 수정: 2026-08-17 04:33:05

1. 개요[편집]

거리 변환 Distance Transform
입력	이진 영상(전경/배경) 또는 일반 비용 함수
출력	각 화소에서 가장 가까운 전경까지의 거리
정확 유클리드	분리가능 + 하부 포물선 포락 → O(N)
근사	체임퍼 마스크 <3,4> · <5,7,11>, 2패스 래스터 주사
연속 대응	아이코날 방정식의 특수해 (속도 1)
파생물	부호거리장(SDF) · 중심축 · 보로노이 다이어그램

거리 변환은 이진 영상의 각 화소에 가장 가까운 전경 화소까지의 거리를 적어 넣어 만든 스칼라 장이다. 전경 집합을 $S$ , 격자를 $\Omega$ 라 하면

D(p) \;=\; \min_{q \in S} \, d(p, q), \qquad p \in \Omega

이고 $d$ 로는 보통 유클리드 거리를 쓴다. 입력이 0/1 두 값짜리 흑백 그림인데 출력은 매끄러운 언덕 지형이 된다 — 물체 깊숙한 곳일수록 값이 크고, 경계에서 0으로 떨어지는 그 지형이 이후 온갖 알고리즘의 지반이 된다.

거리 변환이 유용한 이유는 “가장 가까운 것까지의 거리”라는 질의를 한 번에 전부 미리 계산해 두기 때문이다. 최근접 질의를 매번 하려면 보로노이 다이어그램이나 kd-트리를 세워야 하는데, 격자 위에서라면 거리 변환 한 번이 그 전부를 대신한다. 실제로 정확한 유클리드 거리 변환은 이산 보로노이 다이어그램과 같은 정보를 담고 있다 — 각 화소가 어느 전경 화소에 배정되었는지를 함께 기록하면 그게 곧 셀 분할이다.

2. 어떤 거리를 쓸 것인가[편집]

격자 위의 거리에는 선택지가 있고, 각각 대가가 다르다.

거리	정의	최대 상대오차
시티블록 $d_4$	가로·세로 이동만, 각 1	약 41.4%
체스보드 $d_8$	대각 포함 모든 이동 1	약 29.3%
체임퍼 $\langle 3,4\rangle$	직선 3, 대각 4 (÷3)	약 8%
체임퍼 $\langle 5,7,11\rangle$	직선 5, 대각 7, 나이트 이동 11 (÷5)	약 2%
유클리드	진짜 $\ell_2$	0

$d_4$ 와 $d_8$ 은 계산이 공짜지만 등거리면이 각각 마름모와 정사각형이라, 방향에 따라 거리가 40% 가까이 틀린다. 회전 불변성이 필요한 곳에서는 쓸 수 없다는 뜻이다.¹

체임퍼 거리 변환은 국소 마스크로 거리를 전파하는 근사법이다. 로젠펠트-팔츠(1966)의 2패스 순차 주사가 뼈대다 — 순방향 래스터 주사에서 이미 지나온 이웃들로부터 $D(p) \leftarrow \min_k \{ D(p + a_k) + w_k \}$ 를 갱신하고, 역방향 주사에서 나머지 절반의 이웃으로 한 번 더 갱신한다. 영상을 딱 두 번 훑으면 끝이고 화소당 연산이 열 번 안쪽이라 지금도 임베디드에서 현역이다. 보리에포시(1986)가 마스크 가중치를 최대 오차 최소화 관점에서 정리했고, 그 결과가 위 표의 $\langle 3,4\rangle$ 와 $5\times5$ 마스크 $\langle 5,7,11\rangle$ 이다.²

3. 정확 유클리드 거리 변환[편집]

체임퍼는 국소 전파라서 원리적으로 유클리드를 정확히 재현할 수 없다. 정확한 답을 선형 시간에 얻는 열쇠는 제곱 유클리드 거리가 축 방향으로 분리가능하다는 사실이다.

D^2(x,y) \;=\; \min_{x'}\Bigl[\ (x-x')^2 \;+\; \underbrace{\min_{y'}\bigl\{ (y-y')^2 + f(x',y') \bigr\}}_{\text{열 방향 1D 변환}} \Bigr]

여기서 $f$ 는 전경이면 0, 배경이면 $+\infty$ 인 지시 비용이다. 즉 열 방향 1차원 변환을 먼저 돌리고, 그 결과에 행 방향 1차원 변환을 돌리면 2차원 정확 결과가 나온다. 3차원 이상도 축을 하나씩 늘리면 그만이다.

남은 것은 1차원 문제

D(p) \;=\; \min_{q}\bigl\{\, f(q) + (p-q)^2 \,\bigr\}

를 $O(n)$ 에 푸는 것인데, 이것이 펠젠스발브-후텐로허의 하부 포락선 알고리즘이다. 격자점 $q$ 마다 꼭짓점이 $(q, f(q))$ 인 포물선을 하나씩 세워 두고 그 하부 포락선을 읽으면 답이 된다. 포물선들의 폭(2차 계수)이 전부 같으므로 임의의 두 포물선은 정확히 한 번만 만나고, 따라서 교점들이 왼쪽에서 오른쪽으로 단조롭게 배열된다. 스택 하나로 훑으며 가려지는 포물선을 버리면 각 포물선이 최대 한 번 push·pop 되어 총 $O(n)$ 이다. 알고리즘 자체는 하한 합성곱 문서에 더 일반적인 형태(임의의 볼록 커널 $g$ 에 대한 $f \square g$ )로 정리되어 있다.

정리하면 $N$ 화소짜리 $d$ 차원 영상의 정확 유클리드 거리 변환이 $O(dN)$ 에 끝난다. 화소당 상수 시간이라 근사법을 쓸 이유가 거의 없어졌고, 실제로 2000년대 이후 라이브러리들은 대부분 정확 EDT를 기본값으로 삼는다. 같은 복잡도의 정확 알고리즘으로 브뢰 등(1995), 마우러 등(2003)의 보로노이 기반 방식도 있다. 그 이전의 대표 근사법이던 다니엘손(1980)의 벡터 전파(4SED)는 최근접 전경의 좌표 벡터를 함께 전파해 거의 정확한 답을 냈지만, 특정 배치에서 미세한 오차가 남는다는 것이 알려져 있다.

일반화도 자연스럽다. $f$ 를 0/∞ 대신 임의의 비용으로 두면 일반화 거리 변환이 되고, 이것이 동적 계획법 형태의 믿음 전파 메시지 계산이나 부품 기반 물체 검출에서 $O(L^2)$ 를 $O(L)$ 로 떨어뜨리는 그 부품이다.

4. 부호거리장[편집]

물체 안쪽에 음수를 주면 부호거리장(signed distance field, SDF)이 된다.

\phi(p) = \begin{cases} -\,\mathrm{dist}(p, \partial S), & p \in S \\ +\,\mathrm{dist}(p, \partial S), & p \notin S \end{cases}

경계에서 $\phi = 0$ 이고, 미분가능한 곳에서 $\lVert \nabla \phi \rVert = 1$ 이며 $\nabla \phi$ 가 곧 바깥 방향 법선이다. 이 세 성질 때문에 SDF는 형상을 표현하는 방식 중 가장 실용적인 축에 든다.

렌더링. 스피어 트레이싱은 현재 지점에서 $\phi$ 만큼은 아무것도 없다는 보장을 이용해 그 거리만큼 광선을 한 번에 전진시킨다. 삼각형 하나 없이 형상을 그리는 셰이더 데모들이 전부 이 원리이고, 레이 트레이싱의 교차 판정을 거리 질의로 대체한 셈이다.
폰트와 텍스처. 밸브가 2007년에 공개한 SDF 텍스트 렌더링은, 글리프를 저해상도 SDF 텍스처로 굽고 셰이더에서 $\phi = 0$ 을 알파 임계로 잡는다. 쌍선형 보간이 거리장에서는 경계를 흐리게 만드는 대신 그대로 유지하기 때문에, 64×64 텍스처를 수십 배로 확대해도 모서리가 날카롭다. 뾰족한 코너가 둥글게 뭉개지는 약점은 다채널 SDF(MSDF)로 보완한다.³
충돌과 물리. 복잡한 정적 형상을 SDF로 구워 두면 임의 점의 침투 깊이와 밀어내기 방향이 $\phi$ 값과 $\nabla\phi$ 로 즉시 나온다. 입자·천·유체가 복잡한 지형과 부딪히는 처리에 표준적으로 쓰인다.
레벨셋. 레벨셋 방법은 계면을 $\phi = 0$ 등고면으로 나르는데, 이류가 진행되면 $\lVert\nabla\phi\rVert = 1$ 이 깨져 곡률과 법선 계산이 망가진다. 그래서 주기적으로 재초기화, 즉 부호는 유지한 채 거리장을 다시 만드는 작업이 필요하고, 여기에 거리 변환이나 아래의 고속행진법이 들어간다.

5. 아이코날 방정식과의 관계[편집]

거리 변환의 연속 버전은 **아이코날 방정식**이다. 경계 $\Gamma$ 에서 0인 도달시간 $u$ 는

\lVert \nabla u(x) \rVert \;=\; \frac{1}{c(x)}, \qquad u|_{\Gamma} = 0

을 만족하고, 속도가 어디서나 $c \equiv 1$ 인 특수한 경우의 점성해가 정확히 거리함수 $u(x) = \mathrm{dist}(x, \Gamma)$ 다. 그러니 거리 변환은 “등방·등속 파면이 경계에서 출발해 각 지점에 도착한 시각을 적은 표”라고 읽어도 된다.

이 관점의 이득은 속도를 상수가 아니게 만들 수 있다는 것이다. $c(x)$ 를 매질에 따라 바꾸면 굴절이 들어간 최소 도달시간이 나오고, 그러면 같은 코드가 지진파 초동 주시 계산, 최단 경로, 광선 추적으로 확장된다. 수치해법은 고속 행진법이 대표적인데, 정보가 값이 작은 쪽에서 큰 쪽으로만 흐른다는 단조성을 이용해 우선순위 큐로 한 번만 훑어 $O(N \log N)$ 에 끝낸다 — 다익스트라 알고리즘의 연속판이다. 고속 스위핑법은 방향을 바꿔 가며 몇 번 훑는 방식으로 $O(N)$ 을 낸다. 자세한 것은 해밀턴-야코비-벨만 방정식 문서 쪽에 정리되어 있다.

다만 속도가 상수라면 고속행진법을 쓸 이유가 없다. 분리가능 정확 EDT가 더 빠르고 더 정확하다(고속행진법은 상류 차분의 이산화 오차가 남는다). 고속행진법은 속도장이 변하거나 격자가 비정규일 때 꺼내는 카드다.

6. 응용[편집]

중심축과 골격. 물체 내부 거리 변환의 능선(ridge), 즉 가장 가까운 경계점이 둘 이상인 점들의 자취가 중심축(medial axis)이다. 여기에 거리값을 붙이면 원래 형상을 복원할 수 있어(최대 내접원들의 합집합) 형상 압축·골격화의 근거가 된다. 다만 경계의 작은 요철이 긴 가지를 만들어 내는 불안정성이 악명 높고, 그래서 가지치기가 사실상 필수다.⁴
붙어 있는 물체 분리. 세포·알갱이 사진처럼 개체들이 서로 닿아 있으면 단순 임계값으로는 하나의 덩어리가 된다. 거리 변환의 국소 최대를 씨앗으로 삼고 $-D$ 위에서 분수령 변환을 돌리면 접점에서 깔끔하게 갈라진다. 영상 계측의 국룰 파이프라인이다.
여유 거리 기반 경로계획. 장애물 거리 변환은 곧 “이 지점에서 벽까지 얼마나 여유가 있는가”라서, 최단 경로에 $-\lambda D$ 같은 항을 얹으면 벽을 스치지 않는 경로가 나온다. 내비게이션 메시나 격자 기반 계획의 비용지도가 대개 이렇게 만들어진다.
형태학 가속. 반지름 $r$ 인 원판에 의한 침식은 거리 변환 값이 $r$ 이상인 화소 집합과 같다. 즉 거리 변환 한 번을 계산해 두면 모든 반지름에 대한 원판 침식·팽창이 임계값 한 번으로 나온다. 수학적 형태학의 입도 분석이 이 성질로 대폭 싸진다.
체임퍼 정합. 템플릿 윤곽을 목표 영상의 거리 변환 위에 올려놓고 값의 평균을 읽으면 그것이 곧 정합 점수다. 미분가능하고 부드러워 최적화가 잘 먹혀, 초기 물체 검출 알고리즘의 주력이었다.

7. 관련 문서[편집]

최대 상대오차는 정의와 정규화 방식에 따라 소수점 아래가 조금씩 달리 보고된다. $d_4$ 의 41.4%는 대각선 방향에서 $\sqrt2$ 대신 2를 세기 때문이고, $d_8$ 의 29.3%는 같은 방향에서 $\sqrt2$ 대신 1을 세기 때문이다. 둘 다 “대각선 한 칸을 몇으로 칠 것인가”라는 질문 하나에서 나오는 오차라는 게 포인트. ↩
체임퍼 마스크의 가중치를 정수로 쓰는 이유는 순전히 정수 연산이 싸서였다. 부동소수점 유닛이 흔해진 지금은 최적 실수 가중치를 그냥 쓰면 오차가 절반 이하로 떨어진다. 그럼에도 교과서가 여전히 3-4를 가르치는 것은, 3-4가 손으로 굴려 보기 좋은 숫자라서라는 설이 유력하다. ↩
“거리장을 텍스처에 구워서 확대해도 안 뭉개진다”는 아이디어가 게임 업계에 퍼지는 데 논문 한 편이 아니라 SIGGRAPH 코스 노트 몇 쪽이면 충분했다. 요즘 UI 프레임워크들이 벡터 폰트 래스터라이저 대신 SDF 아틀라스를 쓰는 이유도, 텍스트 크기가 바뀔 때마다 다시 굽지 않아도 되기 때문이다. ↩
중심축의 불안정성은 이론적으로도 정직하다. 경계를 하우스도르프 거리로 아무리 조금 흔들어도 중심축은 임의로 크게 변할 수 있다. 그래서 실무의 골격 추출 코드는 대부분 “중심축을 구한다”가 아니라 “중심축을 구하고 90%를 버린다”에 가깝다. ↩