그래프 컷

최적설계 컴퓨터 그래픽스 마지막 수정: 2026-08-01 05:03:19

1. 개요[편집]

그래프 컷 Graph cuts
푸는 것	데이터항 + 쌍별항 에너지의 최소화 (MRF의 MAP 추정)
도구	s-t 최소 절단 = 최대 유량
정확히 풀리는 조건	부분모듈성 V(0,0)+V(1,1) ≤ V(0,1)+V(1,0)
다중 라벨	NP-난해 → α-확장(2배 근사) / α-β 교환
대표 응용	영상 분할(GrabCut), 스테레오 시차, 잡음 제거

그래프 컷(graph cuts)은 라벨링 문제의 에너지 함수를 특별히 설계한 그래프의 s-t 최소 절단으로 번역해 최소화하는 조합 최적화 기법이다. 픽셀마다 “전경이냐 배경이냐”, “시차가 얼마냐” 같은 이산 라벨을 붙이는 문제에서, 국소 탐색이나 담금질로 근사하던 것을 전역 최적해를 정확히(또는 보장된 근사로) 구하는 문제로 바꿔 놓았다.

여기서 최소 절단을 실제로 계산하는 도구는 최대유량-최소절단 정리와 증대 경로 알고리즘인데, 그 정리와 에드먼즈-카프를 포함한 유량 알고리즘 자체는 네트워크 흐름 문서가 다룬다. 이 문서는 그 위층 — 어떤 에너지가 이 도구로 번역 가능한지(부분모듈성), 번역이 안 될 때 무엇을 하는지(α-확장), 그리고 왜 하필 특정 유량 알고리즘이 격자에서 빠른지 — 를 다룬다.

2. 에너지 최소화라는 관점[편집]

영상 분할, 스테레오, 잡음 제거는 형태가 전부 같다. 각 화소 $p$ 에 라벨 $x_p \in \mathcal{L}$ 을 붙이되, 관측과 잘 맞으면서 이웃끼리 매끄럽기를 원한다. 이를 에너지로 쓰면

E(\mathbf{x}) = \sum_{p \in \mathcal{P}} D_p(x_p) + \sum_{(p,q) \in \mathcal{N}} V_{pq}(x_p, x_q)

이다. $D_p$ 는 데이터항으로 라벨이 관측을 얼마나 잘 설명하는지의 벌점(음의 로그가능도)이고, $V_{pq}$ 는 평활항으로 이웃한 화소가 다른 라벨을 가질 때 무는 벌점이다. 이 에너지를 최소화하는 것은 마르코프 확률장의 사후확률을 최대화하는 MAP 추정과 정확히 같다(깁스 분포에서 확률의 음의 로그가 곧 에너지).

문제는 라벨 조합이 $|\mathcal{L}|^{|\mathcal{P}|}$ 개라는 것이다. 512×512 이진 영상만 해도 $2^{262144}$ 가지다. 1980~90년대에는 담금질 모사나 반복 조건부 모드(ICM) 같은 국소 탐색으로 근사했는데, 그래프 컷은 상당수의 경우 이 조합 폭발을 다항 시간에 전역 최적으로 뚫는다.¹

3. 이진 라벨링과 부분모듈성[편집]

라벨이 두 개( $\{0,1\}$ )일 때 그래프를 이렇게 짓는다. 화소마다 정점을 하나 두고, 소스 $s$ 는 라벨 0, 싱크 $t$ 는 라벨 1을 대표하게 한다.

터미널 간선(t-link) — $p$ 와 $s$ , $p$ 와 $t$ 를 잇는 간선에 데이터항 $D_p(1)$ , $D_p(0)$ 를 용량으로 준다.
이웃 간선(n-link) — 이웃 화소 $p,q$ 사이에 평활항에서 유도한 용량을 준다.

이제 $s$ - $t$ 절단은 각 화소를 소스 쪽/싱크 쪽으로 가르므로 라벨링과 일대일 대응하고, 절단 비용이 곧 에너지가 되도록 용량을 맞출 수 있다. 그러면 최소 절단 = 최소 에너지다. 최소 절단은 최대 유량과 같고 다항 시간에 정확히 계산되므로, 조합 폭발이 통째로 사라진다.

단, 이 번역이 항상 되는 것은 아니다. 간선 용량은 음수일 수 없기 때문에, 다음 조건이 필요충분이다.

V_{pq}(0,0) + V_{pq}(1,1) \le V_{pq}(0,1) + V_{pq}(1,0)

이를 부분모듈성(submodularity)이라 하고, 이 조건을 만족하는 에너지를 정규(regular)하다고 부른다. 뜻은 직관적이다. “이웃이 같은 라벨을 갖는 쪽이 다른 라벨을 갖는 쪽보다 싸다” — 즉 평활항이 진짜로 평활을 선호해야 한다는 것이다. 흔히 쓰는 포츠 모형 $V = \lambda\,[x_p \neq x_q]$ 나 잘린 선형·볼록 벌점은 전부 이 조건을 만족한다.

반대로 이웃이 다르기를 선호하는 항(반강자성, 텍스처의 위상 반전 등)이 섞이면 부분모듈성이 깨지고, 그 순간 문제는 최대 절단과 동치가 되어 NP-난해다. 이때는 부분모듈 항만 정확히 풀고 나머지는 미라벨로 남기되 라벨된 화소는 전역 최적해와 일치함이 보장되는(persistency) QPBO 계열, 혹은 문제를 부분모듈이 되도록 근사하는 절단(truncation) 방식을 쓴다.

4. 다중 라벨 — α-확장과 α-β 교환[편집]

라벨이 셋 이상이면 이야기가 달라진다. 포츠 평활항만 있어도 다중 라벨 최소화는 NP-난해다. 여기서 나온 것이 “매 반복 이진 그래프 컷을 한 번씩 부르는” 이동(move-making) 전략이다.

α-확장(α-expansion) — 라벨 $\alpha$ 를 하나 고정하고, 각 화소가 현재 라벨을 유지할지 $\alpha$ 로 갈아탈지만 결정하는 이진 문제를 푼다. 이 부분 문제가 이진 그래프 컷으로 정확히 풀린다. 모든 $\alpha$ 를 한 바퀴 돌아 에너지가 더 이상 줄지 않으면 종료.
α-β 교환(α-β swap) — 현재 라벨이 $\alpha$ 또는 $\beta$ 인 화소들만 골라 둘 사이에서만 재배치한다. 각 이동의 폭이 좁은 대신 조건이 느슨하다.

두 이동의 사용 조건과 보증이 다르다는 점이 실무에서 중요하다. α-확장이 쓰이려면 평활항이 거리 함수(metric) 여야 한다. 즉 $V(a,b)=0 \iff a=b$ , 대칭성 $V(a,b)=V(b,a)$ , 그리고 삼각 부등식 $V(a,c) \le V(a,b)+V(b,c)$ 를 만족해야 한다. 이 조건 아래에서 α-확장은 다음을 보장한다.

E(\hat{\mathbf{x}}) \le 2c \cdot E(\mathbf{x}^*), \qquad c = \frac{\max_{a \neq b} V(a,b)}{\min_{a \neq b} V(a,b)}

포츠 모형은 모든 비대각 값이 같아 $c = 1$ , 따라서 전역 최적의 2배 이내라는 상수 배 근사가 나온다. NP-난해 문제에 이런 보증이 붙는 것은 흔한 일이 아니다. 반면 α-β 교환은 삼각 부등식 없이 준거리(semi-metric)만 있으면 되지만 근사 보증이 없다. 잘린 이차 벌점처럼 삼각 부등식이 깨지는 평활항에는 교환을 쓰되, 결과 품질은 초기값에 의존한다는 것을 감수해야 한다.

라벨이 순서를 갖고 평활항이 볼록이면 이시카와의 층상 그래프 구성으로 다중 라벨을 한 번의 최소 절단으로 정확히 풀 수도 있다. 다만 볼록 벌점은 경계에서 과도하게 매끄러워져 물체 윤곽이 뭉개지므로, 실무에서는 불연속을 허용하는 잘린 벌점 + α-확장 조합이 더 널리 쓰인다.

5. 최대유량 알고리즘의 선택[편집]

이론적으로 최소 절단은 어떤 최대유량 알고리즘으로 구해도 되지만, 실제 속도 차이는 수십 배까지 난다. 영상 문제의 그래프는 형태가 매우 특수하기 때문이다. 정점 수는 수십만~~수백만인데 정점마다 간선은 4~~26개뿐이고(4-이웃, 8-이웃, 3D 26-이웃), 격자라 거의 평면에 가깝고, 소스-싱크 경로가 짧다.

이 구조에 맞춰 나온 것이 보이코프-콜모고로프(BK) 알고리즘이다. 소스에서 자라는 탐색 트리와 싱크에서 자라는 탐색 트리 두 개를 유지하며 증대할 때마다 버리지 않고 재사용하는 것이 핵심으로, 끊어진 가지는 입양(adoption) 단계에서 다시 붙인다. 최악 시간복잡도는 오히려 밀어내기-재라벨(push-relabel)류보다 나쁘지만, 위 특성을 가진 격자 그래프에서는 실측이 압도적으로 빨라 컴퓨터 비전의 사실상 표준이 됐다. 반대로 간선이 조밀하거나 정점이 수천만 개로 커지면 밀어내기-재라벨이나 병렬·GPU 구현이 유리하다.

한 가지 더. 동영상처럼 거의 같은 문제를 프레임마다 다시 푸는 상황에서는 이전 프레임의 유량을 초기값으로 물려주는 동적 그래프 컷이 쓰인다. 바뀐 용량 주변만 다시 증대하면 되므로 프레임당 비용이 한 자릿수로 떨어진다.

6. 응용[편집]

영상 분할 — 사용자가 전경·배경에 몇 획만 그으면 그 화소를 하드 제약으로 걸고 나머지를 최소 절단으로 가른다. 이를 확장한 GrabCut은 사각형 하나만 받고, 색 분포를 가우시안 혼합 모형으로 추정하는 단계와 그래프 컷으로 라벨을 갱신하는 단계를 번갈아 반복한다. 매 반복 에너지가 감소함이 보장된다.
스테레오 시차 — 라벨을 시차값으로 두고, 데이터항은 좌우 영상 정합 비용, 평활항은 잘린 선형 벌점으로 둔다. α-확장의 대표 무대이며, 시차 불연속(물체 경계)을 살리기 위해 영상 기울기가 큰 곳에서 평활 가중치를 낮추는 것이 관행이다.
잡음 제거·복원 — 라벨을 밝기값으로 두는 전형적인 MRF 문제. 전변동(TV) 정칙화의 이산판이 정확히 부분모듈 에너지라 그래프 컷으로 정확히 풀린다.
3차원 재구성·의료영상 — 3D 격자에서 장기·혈관 분할, 다중 시점 스테레오의 표면 추출. 경계를 곡면으로 다루는 레벨셋 방법과 자주 비교되는데, 그래프 컷은 초기값 의존성이 없는 대신 격자 이산화에 따른 계량 오차(metrication error)를 감수한다.

7. 이징 모형과의 동치[편집]

물리 쪽에서 보면 이 모든 것은 이미 알려진 문제다. 스핀 $s_i \in \{-1,+1\}$ 의 이징 모형 해밀토니안

H(\mathbf{s}) = -\sum_{(i,j)} J_{ij} s_i s_j - \sum_i h_i s_i

에서 $s_i$ 를 라벨, $h_i$ 항을 데이터항, $J_{ij}$ 항을 평활항으로 읽으면 위의 이진 라벨링 에너지와 같은 식이다. 그리고 강자성( $J_{ij} > 0$ , 이웃이 같은 방향을 선호)일 때 쌍별항이 정확히 부분모듈 조건을 만족한다. 즉 강자성 이징 모형의 기저상태는 최소 절단으로 다항 시간에 정확히 구할 수 있다. 외부장이 있어도 마찬가지다.

반면 $J_{ij}$ 의 부호가 섞인 스핀글라스는 좌절(frustration)이 생기며 부분모듈성이 깨져, 기저상태 탐색이 최대 절단과 동치인 NP-난해 문제가 된다(외부장이 없는 2차원 평면 격자는 예외적으로 다항 시간). 통계물리의 “좌절”과 최적화의 “비부분모듈”이 같은 말이라는 사실이 이 대응의 요점이다.

한 가지 구분은 짚어 둘 필요가 있다. 그래프 컷이 주는 것은 에너지 최소점 하나, 즉 온도 0 극한의 기저상태다. 유한 온도에서 분포 전체를 다루는 정준 앙상블 계산이나 자유에너지·상관함수는 여전히 표본추출의 영역이며, 최소 절단이 대신해 주지 않는다.² 담금질 모사로 며칠 돌리던 이진 복원 문제가 최소 절단으로 몇 초 만에, 그것도 정확히 풀린다는 사실이 1989년에 이미 지적됐지만 비전 분야가 이를 본격적으로 받아들이는 데는 10년 이상이 걸렸다.³⁴

8. 관련 문서[편집]

“다항 시간에 전역 최적”이라는 표현이 붙는 이산 비전 문제는 손에 꼽는다. 그래서 2000년대 초 이 계열 논문의 결과 그림에는 늘 담금질 모사 결과가 나란히 붙어 있었다 — 같은 에너지를 훨씬 오래 돌려도 더 나쁘다는 것을 보여주기 위한 대조군이었다. ↩
기저상태만 정확히 구해 놓고 “이제 이 계를 다 이해했다”고 말할 수는 없다. 온도가 올라가면 엔트로피가 지형을 재편하고, 최소점 근처의 계곡이 얼마나 넓은지가 물리를 지배하기 시작한다. ↩
Greig, Porteous & Seheult (1989)가 이진 영상 복원의 MAP 해를 최대유량으로 정확히 구할 수 있음을 보이며, 당시 널리 쓰이던 담금질 모사 결과가 최적과 한참 떨어져 있다는 것을 함께 보고했다. 논문은 통계학 저널에 실렸고, 비전 학계는 한동안 이를 모른 채 어닐링 온도 스케줄을 손보고 있었다. 분야 간 장벽의 교과서적 사례. ↩
물론 오늘날 분할 벤치마크 상위권은 신경망이 차지하고 있다. 다만 그래프 컷은 여전히 신경망 출력의 후처리(경계 정련)나 학습 데이터 라벨링 도구로 살아 있다 — 명시적 에너지와 보장된 최적성이 필요한 자리는 아직 남아 있다. ↩