분수령 변환

1. 개요[편집]

분수령 변환 Watershed Transform
비유	회색조 영상 = 지형, 국소 최소 = 웅덩이
출력	유역(catchment basin) 분할 + 분수령 선
대표 알고리즘	Vincent–Soille 침수(1991) · 우선순위 홍수
복잡도	계수 정렬 + FIFO 큐로 O(N), 힙 구현은 O(N log N)
고질병	과분할 — 국소 최소 개수 = 영역 개수
처방	마커 기반 분수령 · h-최소 변환 · 계층적 병합

분수령 변환은 회색조 영상을 지형으로 읽고 물을 채워 영역을 나누는 분할 기법이다. 화소값을 고도라고 보면 영상은 산과 골짜기가 있는 지도가 되고, 각 골짜기(국소 최소)마다 빗물이 모이는 범위 — 유역(catchment basin) — 이 정해진다. 유역들의 경계선이 곧 분수령(watershed line)이고, 그것이 분할 결과의 윤곽선이 된다. 뷔셰와 랑퇴줄(1979)이 수학적 형태학 학파에서 제안했다.

핵심 감각은 어디에 물을 채우느냐다. 원본 영상에 그냥 돌리면 “밝기가 비슷한 덩어리”가 나오는데, 대개 원하는 것은 그게 아니라 물체 경계다. 그래서 실무는 거의 항상 기울기 크기 영상 $\lVert \nabla f \rVert$ 위에서 돌린다. 경계는 기울기가 크므로 능선이 되고, 물체 내부는 기울기가 작으므로 골짜기가 된다. 물을 채우면 골짜기(물체 내부)마다 유역이 생기고 능선(경계)에서 갈라지므로, 결과가 곧 물체 윤곽이다.

분수령이 다른 분할 기법과 구별되는 지점은 두 가지다. 첫째, 닫힌 윤곽선이 구조적으로 보장된다 — 유역 분할이라는 정의상 영역은 반드시 완전히 둘러싸인다. 에지 검출기가 뱉는 끊어진 선분을 잇느라 고생할 일이 없다. 둘째, 거의 선형 시간이다. 최적화를 돌리는 그래프 컷이나 마르코프 확률장 계열과 비교하면 계산 비용이 한 자릿수 이상 싸다.

2. 두 가지 정의[편집]

말은 쉬운데 정의를 이산 격자에서 정확히 쓰려면 손이 많이 간다. 표준은 두 가지다.

침수(immersion) 정의. 모든 국소 최소에 구멍을 뚫고 지형을 물에 서서히 담근다. 수위 $h$ 를 올리면서, 서로 다른 최소에서 자란 물이 만나려는 지점마다 댐을 세운다. 댐의 자취가 분수령이다.

낙수(topographic distance) 정의. 각 화소에서 빗방울이 최급강하 방향으로 흘러 도달하는 최소가 그 화소의 소속이다. 마이어(1994)가 이를 지형 거리로 형식화했다 — 경로를 따라 $\lVert\nabla f\rVert$ 를 적분한 값이 최소인 최소점에 화소를 배정한다.

두 정의는 평평한 구간(plateau)이 없으면 일치하지만, 이산 격자에서는 같은 값의 화소가 넓게 붙어 있는 것이 정상이라 정확히 어긋난다. 고원 위의 물방울은 어느 쪽으로 흘러야 할지 알 수 없고, 여러 최소에서 등거리인 화소가 생긴다. 구현들이 서로 다른 결과를 내는 원인의 대부분이 이 고원 처리이며, 그래서 라이브러리마다 “분수령 선을 별도 라벨로 남길지, 아니면 인접 유역에 나눠 줄지”가 옵션으로 붙어 있다.¹

3. Vincent–Soille 침수 알고리즘[편집]

뱅상과 소이유(1991)의 구현이 사실상 표준이 됐다. 침수 정의를 그대로 코드로 옮기되, 수위를 연속적으로 올리는 대신 회색 레벨 단위로 한 칸씩 올린다.

1. 정렬. 화소를 값 순으로 정렬한다. 값이 8비트 정수라 계수 정렬(히스토그램)이면 $O(N)$ 에 끝난다. 이 한 줄이 이 알고리즘이 선형인 이유다.
2. 레벨별 처리. 낮은 레벨부터 올라가며, 값이 $h$ 인 화소들을 꺼낸다.
3. 측지 전파. 이미 라벨이 붙은 이웃이 있는 화소들을 FIFO 큐에 넣고 너비 우선으로 퍼뜨린다. 이때 전파는 값이 $h$ 인 화소 집합 안에서만 일어난다(측지 팽창). 두 개 이상의 서로 다른 라벨이 닿는 화소는 분수령으로 표시한다.
4. 새 최소 발견. 전파가 끝난 뒤에도 라벨이 없는 화소는 새 국소 최소이므로 새 라벨을 부여하고 마찬가지로 퍼뜨린다.

핵심은 3단계의 FIFO 전파가 곧 측지 영향 지대(SKIZ, skeleton by influence zones)를 계산한다는 것이다. 고원 위에서 여러 유역이 동시에 같은 속도로 번지므로, 고원은 각 유역에서의 측지 거리에 따라 공평하게 나뉜다.

우선순위 큐를 쓰는 변형이 우선순위 홍수(priority flood) 또는 계층 큐 분수령이다. 씨앗을 최소 우선순위 큐에 넣고, 값이 가장 낮은 화소를 꺼내 라벨을 확정한 뒤 아직 라벨 없는 이웃들을 큐에 넣기를 반복한다. 코드가 20줄이고 마커 기반으로 바로 확장되며, 힙 때문에 $O(N\log N)$ 이지만 상수가 작아 실무에서 가장 널리 쓰인다. 구조가 다익스트라 알고리즘이나 고속 행진법과 판박이인데, 셋 다 “값이 작은 쪽에서 큰 쪽으로만 정보가 흐른다”는 단조성을 이용해 각 화소를 한 번만 확정한다는 점이 같다. 지형 데이터(DEM)의 웅덩이 메우기와 유역 추출에 쓰이는 알고리즘도 같은 물건이다 — 이 기법의 이름이 왜 하필 수문학 용어인지가 여기서 드러난다.

4. 과분할, 그리고 마커[편집]

분수령을 처음 써 본 사람은 예외 없이 같은 그림을 만난다. 세포 하나가 스무 조각으로 갈라진 결과다.

이유는 정의에 이미 들어 있다. 유역의 개수는 국소 최소의 개수와 정확히 같다. 그런데 실제 기울기 영상에는 센서 잡음과 질감 때문에 국소 최소가 수천, 수만 개 있다. 알고리즘은 시킨 대로 정직하게 그 전부를 유역으로 만들 뿐이다. 즉 과분할은 버그가 아니라 문제 설정의 결과이며, 알고리즘을 바꿔서 고칠 수 있는 게 아니다.

처방은 최소의 개수를 줄이는 것이고, 세 계열이 있다.

h-최소 변환. 깊이가 $h$ 미만인 골짜기를 메운다. 형태학적 재구성으로 쓰면 한 줄이다 — 마스크 $f$ 에 대해 마커 $f+h$ 에서 시작하는 침식에 의한 측지 재구성을 취한다.

$$\mathrm{HMIN}_h(f) \;=\; R^{\varepsilon}_{f}\bigl(f + h\bigr)$$

$h$ 보다 얕은 최소는 흡수되어 사라지고, 깊은 최소는 위치와 모양이 그대로 남는다. 평활화와 결정적으로 다른 점은 남는 구조를 이동시키지 않는다는 것이다. 가우시안을 씌우면 잡음 최소가 줄어드는 대신 경계도 함께 흐려지고 이동한다.

마커 기반 분수령. 가장 강력하고 실무에서 가장 많이 쓴다. “여기가 물체다”, “여기가 배경이다”를 지정하는 마커 집합을 만들고, 최소 강제(minima imposition)로 기울기 영상의 국소 최소를 오직 그 마커 위치에만 남긴다. 그런 다음 분수령을 돌리면 유역 개수가 정확히 마커 개수가 된다. 마커는 사용자가 클릭할 수도 있고, 자동으로 만들 수도 있다.²

계층적 병합. 일단 과분할한 뒤 인접 유역을 병합해 올라간다. 유역들을 노드, 접한 분수령의 낮은 안장점 높이를 간선 가중치로 하는 영역 인접 그래프를 세우고 가중치가 낮은 것부터 합치면, 결과가 계층 구조가 되어 임계값 하나로 원하는 세밀도를 뽑을 수 있다(뷔셰의 waterfall). 이 관점을 끝까지 밀면 분수령이 최소 신장 숲과 같다는 정리가 나온다 — 쿠스티 등(2009)의 “watershed cut” 은 간선 가중 그래프에서 최소들을 뿌리로 하는 최소 신장 숲의 컷이 정확히 분수령임을 보였다. 영상 분할 알고리즘과 그래프 이론 사이의 다리 중 가장 깔끔한 축에 든다.

5. 거리 변환과의 결합 — 붙은 세포 분리[편집]

교과서 예제이자 현미경 영상 계측의 국룰 파이프라인이다. 세포나 알갱이가 서로 닿아 있으면 밝기 임계값만으로는 한 덩어리가 되어 개수조차 셀 수 없다. 절차는 다섯 줄이다.

1. 이진화. 전경/배경을 나눈다(오츠 등).
2. 거리 변환. 전경 내부의 각 화소에서 가장 가까운 배경까지의 거리 $D$ 를 계산한다. 세포 중심이 봉우리가 된다.
3. 마커 추출. $D$ 의 국소 최대(또는 h-최대 변환 후의 최대)를 씨앗으로 삼는다. 세포 하나에 봉우리 하나.
4. 분수령. $-D$ 위에서 마커 기반 분수령을 돌린다. 봉우리가 골짜기로 뒤집히고, 두 세포가 닿는 잘록한 목 부분이 정확히 분수령이 된다.
5. 라벨 부여. 원래 전경 마스크와 교집합을 취해 개체별 라벨을 얻는다.

여기서 왜 하필 잘록한 목에서 갈라지는지가 이 조합의 전부다. 두 원이 겹친 모양에서 $D$ 의 능선을 따라가면 접점 부근에서 값이 가장 낮으므로, $-D$ 에서는 그 지점이 가장 높은 안장점이 되어 침수가 만나는 자리가 된다. 모양의 오목함을 거리장이 고도로 번역하고, 분수령이 그 안장점을 찾아 자른다. 형태학·거리 변환·분수령 세 도구가 한 줄로 꿰이는, 이 바닥에서 가장 자주 인용되는 레시피다.

3단계에서 국소 최대를 그냥 쓰면 세포 하나에 봉우리가 여러 개 잡혀 다시 과분할된다. h-최대 변환으로 얕은 봉우리를 지우거나 $D$ 를 살짝 평활화하는 것이 실무의 정석이고, $h$ 하나를 조율하는 것이 파라미터 열 개를 만지는 것보다 낫다는 게 경험칙이다.

6. 대안들과의 비교[편집]

기법	성격	비용	강점 / 약점
분수령	형태학적, 결정론적	거의 O(N)	닫힌 윤곽 보장, 매우 빠름 / 과분할, 잡음 민감
그래프 컷	에너지 최소화(최대유량)	다항, 무겁다	전역 최적 보장(이진), 매끄러움 항 / 축소 편향, 씨앗 필요
무작위 워커	조화함수 디리클레 문제	희소 선형계	약한 경계에서 강건, 확률 출력 / 느림, 씨앗 필요
능동 윤곽·레벨셋 방법	변분·PDE	반복 진화	매끄러운 곡선, 곡률 제어 / 초기화 의존, 국소해
학습 기반 분할	합성곱 신경망	학습 비용	의미 정보 사용 / 데이터 필요, 개체 분리 별도

무작위 워커(Grady 2006)는 각 화소에서 무작위 보행을 시작해 어느 씨앗에 먼저 닿을 확률을 구하고 최대 확률의 라벨을 준다. 이 확률은 실제로 보행을 시뮬레이션하지 않고 가중 그래프 라플라시안의 디리클레 문제를 풀어 얻는다. 경계가 흐릿하거나 끊어져 있어도 확률이 부드럽게 이어져 분수령보다 강건하지만, 화소 수만큼의 희소 선형계를 풀어야 하니 비용이 다르다.

셋의 관계가 이론적으로 정리되어 있다는 점이 재미있다. 쿠프리 등(2011)의 power watershed 는 간선 가중치의 지수를 $q$, 라벨 변수의 노름 차수를 $p$ 로 둔 공통 에너지를 정의하고, 그 극한에서 $p=1$ 이면 그래프 컷, $p=2$ 면 무작위 워커, $q\to\infty$ 면 분수령이 나옴을 보였다. 세 알고리즘이 각각 다른 학파에서 따로 자라났는데 결국 같은 에너지의 세 모퉁이였다는 결론이다.³

딥러닝 이후에도 분수령은 살아 있다. 합성곱 신경망이 경계 확률맵이나 에너지 지형을 예측하고 그 위에서 분수령으로 개체를 떼어내는 조합이 세포 계수·위성 영상 건물 추출 등에서 표준이다. 신경망은 의미를, 분수령은 “닫힌 영역으로 정확히 나눈다”는 구조적 보장을 맡는 분업이다.

7. 실무에서 조심할 것[편집]

• 입력을 무엇으로 할지가 90%다. 원본, 기울기 크기, $-$거리 변환, 학습된 경계맵 — 이 선택이 결과를 지배한다. 알고리즘 옵션을 만지기 전에 입력 지형부터 그려 보는 것이 정석.
• 마커 없이 쓰지 마라. 자동 분수령의 결과를 그대로 쓸 수 있는 경우는 거의 없다.
• 연결성 규약(4-이웃 vs 8-이웃)이 결과를 바꾼다. 전경과 배경에 같은 연결성을 쓰면 위상적 역설이 생기므로 보통 엇갈려 쓴다.
• 분수령 선의 두께. 구현에 따라 경계가 1화소 두께의 별도 라벨로 남기도 하고, 아예 남지 않고 유역에 흡수되기도 한다. 면적을 재는 계측 코드에서 이 차이가 조용히 오차로 들어간다.

8. 관련 문서[편집]

• 수학적 형태학 · 거리 변환 · 골격화
• 그래프 컷 · 무작위 워커 · 마르코프 확률장 · 이미지 분할
• 레벨셋 방법 · 아이코날 방정식 · 고속 행진법
• 보로노이 다이어그램 · 계산기하학 · 합성곱 신경망

9. Footnotes[편집]

1. 그래서 “분수령을 돌렸는데 다른 툴과 결과가 다르다”는 질문이 끝없이 재생산된다. 대부분 알고리즘이 틀린 게 아니라 고원 처리와 연결성 규약이 다른 것이다. 같은 이름의 함수가 라이브러리마다 미묘하게 다른 물건인 대표적 사례. ↩

2. 마커의 위력은 좀 허무할 정도다. 파라미터를 열 개 조율하며 몇 시간을 태우던 결과가, 세포 중앙에 점 몇 개 찍는 것으로 즉시 해결된다. 형태학 강의에서 “알고리즘을 고치지 말고 최소를 심어라”가 표어처럼 반복되는 이유. ↩

3. 이런 통합 정리는 보통 실용적 이득보다 정신 건강에 도움이 된다. 새 분할 알고리즘 논문을 볼 때 “얘는 저 스펙트럼의 어디쯤인가”를 먼저 묻게 되기 때문이다. 답이 “새 모퉁이”가 아니라 “기존 두 모퉁이 사이”인 경우가 생각보다 많다. ↩