CH6

Preview

• 지난주에 배운 내용
  • 특징점 매칭
• 이번주에 배울 내용 : "영역('화소간의 거리' 고려)" 분할
  • 사람의 뇌
    $\to$ "상자 위에 쌓여있는 형형색색의 파프리카" 라고 해석하는 과정에서, 상자, 파프리카, 가격표, 글자와 같이 의미 있는 영역으로 분할
    $\to$ '분할'과 '인식'이 동시에 일어남
  • 컴퓨터 비전
    $\to$ 현재는 '분할' 후 '인식' 하는 순차 처리(동시 수행을 추구하는 연구도 있으나 초보 단계)
    $\to$ '가장 어려운 문제' 중 하나

---

1

1. 영상 분할의 원리

• 분할의 정의

  • 식 (5,1)은 엄밀성 보다는 개념적인 정의 (즉, 반드시 만족 x)
  • region i 와 region j 는 서로 겹치는 부분이 없고, 이 둘을 합했을때 영상 전체 f가 되어야 함
  • 두 가지 조건이 중요

• 생각해 볼 점

  • 적절한 분할이란?
    • 저분할$_{under-segmentation}$ 과 과분할$_{over-segmentation}$
  • 사람 vs 컴퓨터
    • 사람은 선택적 주의집중과 능동 비전 기능을 가지며, 분할 과정에서 고급 지식 사용
    • (주의 집중) 가격표 인지 $\to$ 파프리카 살 마음이 생김 $\to$ 더 세밀하게 분할
    • (능동 비전) 가격을 확인하고 싶음 $\to$ 멀어서 보이지 않음 $\to$ 가까이 다가감
  • 컴퓨터 비전은 그런 수전에 이르지 못함
    • 분할이 끝나야만 고급 지식을 이용하여 인식을 수행

• 분할의 어려움

  • 이웃 화소 몇 개를 보고 자신이 영역의 내부인지 경계인지 판단할 수있을까?

• 물인지 오리인지 판단하기 어려움 $\to$ 전역 연산이 필요

• 에지 vs 영역

  • 개념적으로는 에지는 영역의 경계에 해당
  • 하지만 에지 검출로는 한계
    • False positive, False negative $\to$ 폐곡선을 이루지 못함

• 영역 vs 지역 특징

  • 사람은 지역 특징보다 영역 분할에 훨씬 뛰어남
  • 반면 컴퓨터 비전은 영역보다 지역 특징으로 문제 해결하는 사례 많음

---

2

2. 전통적 방법

• 동작 조건

  • 특수 조건 만족하거나 단순한 영상에서만 작동
    • 예) 공장 자동화, 문서 인식 등
    • 문제가 쉽다면 굳이 복잡한 알고리즘 쓸 필요 없음
  • 자연 영상에서 매우 낮은 성능

2.1) 임계화$^{threshholding}$를 이용한 영역 분할

• 이진화를 이용한 영역 분할

  • 문서 영상의 경우 오츄 이진화(특정 threshhold t 값 1개)는 훌륭한 영상 분할 알고리즘
  • 하지만 명암 단계가 둘 이상인 경우는 오작동

• 삼진화로 확장

  • 이중 임계값 사용
  • 세 영역이 다른수록 더 좋은 분할

• 알고리즘

  • 이진화를 삼진화로 확장(이중 임계값으로 분할 t1 = 46, t2 = 159)
  • 전체 이미지를 보고 삼진화를 진행한 경우 지역적으로 명암 분포가 다른 경우가 발생.
  • 삼진화를 통해서 달 분리 가능
  • 특정 스레스홀드 두개를 정하여 t1 이하는 0 ,t1 과 t2 사이는 150, t2 이상은 255 로 설정하는 등 명암값을 지정할수있다.

• 적응적 임계화

  • 하나 또는 두 개의 임계값을 영상 전체에 적용하는 전역 방법의 한계

    • 지역적으로 명암 분포가 다른 경우 낮은 분할 품질

  • 적응적 임계화로 해결 : '지역'에 따라 적응적으로 임계값 결정

  • 그러나, $t(j,i)$ 를 어떻게 결정할까? "이웃의 평균/편차" 를 이용하거나 "물체의 모양 정보"

2.2) 군집화$^{Clustering}$를 이용한 영역 분할

• 군집화

  • 화소를 RGB 3차원 컬러 공간으로 매핑 한후, k-means 로 군집화
    • 왼쪽 원본 영상에 대한 RGB 의 값을 오른쪽 RGB 값으로 매핑 한 후
    • 비슷한 RGB 값이면 비슷한 색으로 군집을 만들기
    • 3-means : 포인트를 3개를 만들기 (k 값에 따라 군집의 형상이 달라지므로 원하는 군집을 못 얻을 수도 있다)

• 알고리즘

• 군집 결과

  • 품질 나쁨 $\to$ 초기 군집 설정 개선, k 값 조절 $\to$ 보다 좋은 결과 도출 가능
  • 그러나, 군집화는 화소 사이의 지리적 근접성을 무시
  • 즉, 컬러값의 유사성만 고려
  • 해결 : 화소의 컬러 또는 명암이 조금 다르더라도 이웃에 있으면, 같은 영역으로 배정할 가능성을 높게 유지

2.3) 분할합병을 이용한 영역 분할

• 원리

  • 영역의 균일성을 측정하는 $Q(r_i)$ 를 이용하여 분할과 합병을 반복
    • 어떤 region$_i$ 에 대한 영역의 균일성 $Q(r_i)$ 가 거짓이면, 균일하지 않다는 말이기 때문에 $r_i$ 를 네 개 영역으로 분할(즉, 저분할 처리)하고 재귀 반복
    • $Q(r_i \cup r_j)$ 가 참이면, 두개의 영역을 합병하는 것이 타당해 보인다는 말이므로, $r_i$ 와 $r_j$ 를 합병(즉, 과분할 처리)
  • 화소간의 거리 일부 반영
  • 분할 결과는 4진 트리로 표현 $\to$ '폐곡선' 보장
  • "이진" 영상의 경우 Q()의 참/거짓 여부가 명확한데, "명암/컬러" 영상인 경우 Q()를 정의하는 것이 쉽지 않음 $\to$ 그래프 방법 등에서 추가 설명
• 설명
  • 영상 전체를 하나로 보아 균일하다고 했을때, 균일하지 않기 떄문에 4등분
  • 1, 2, 3, 4로 분할하고, 이때 1 과 2는 균일하지만, 3 과 4 는 균일하지 않으므로 분할한다.
  • 이때 3, 4의 경우 분할된 영역이 겹친다면 하나로 합병

• 알고리즘

---

3

3. 그래프 방법

• $G(V,E)$
• 노드 집합 $V={v_1, v_2, ..., v_n}$
  • 각 하나의 화소 또는 영역자체(슈퍼 화소)를 노드로 표현
• 에지(영상에서의 '에지'가 아니라 그래프에서 '에지') 집합 $E$
  • 이웃 노드 간에 에지 설정(기본적으로 화소간의 거리 반영)
  • 두 노드 $v_p$ 와 $v_q$ 를 연결하는 에지는 가중치 $w_{pq}$ 를 가짐
  • 가중치는 유사도(같은 정도) 또는 거리(다른 정도)로 측정

• 예제) 영상의 그래프 표현

  • 행렬로 표현하였을떄, 자기 자신으로 가는 거리는 0, - 은 무한대를 의미

• 원리

  • 유사도가 높은 노드 쌍을 같은 영역(연결요소), 낮은 노드 쌍은 다른 영역에 배치
  • 유사도가 낮은 에지가 분할선이 될 가능성 높음
  • '가능성이 높다' 라는 표현의 중요성
    • 지역적으로 유사도가 낮더라도 전역적 판단에서 자르지 말아야 한다면 분할선으로 취하지 않음 $\to$ 전역 최적해 추구 (like Canny)

  • 전역 최적화 문제의 구현

    • 1) 어떤 분할의 좋은 정도를 측정하는 목적 함수 $\to$ 분할 품질 관련
    • 2) 목적 함수를 최대화/최소화 하는 최적해를 찾는 효율적인 탐색 알고리즘 $\to$ 속도 관련

3.1) 최소 신장트리

• 원리

  • 에지 가중치가 '거리(다른 정도)'인 그래프로 표현
  • 신장트리를 이용한 최적 분할 찾아냄
    • 그림에서 회색 표시된 부분 그래프의 최소 신장 트리는 빨간 에지 (1-2-1-2-1 선택, 3은
    • 새로운 노드를 추가한다면 어떤 노드(화소)를 고르는 것이 가장 유리할까?

• 영역내부의 연결요소(신장트리) C의 균일성 측정

• [그림 5-9]의 연결요소(신장트리)의 $intra$ 는 2 (회색 표시된 영역 내 빨간색으로 표시된 4개의 에지값 1,2,2,1 중 최대는 2)
• 새로운 노드를 추가한다면 어떤 노드(화소)를 고르는 것이 가장 유리할까?
  • $v_{13}$ 을 추가하면 $intra$ 는 3이 됨, $v_8$ 추가하면 2가 됨 $\to$ 즉, $v_8$ 을 고르는것이 유리
  • 최소 신장 트리에서 가장 큰 간선 가중치가 2 $\to$ $intra(c)$ = 2
  • 거리가 가까울 수록, 즉 최소값을 찾았을떄 새로운 영역을 추가하여 같은 영역으로 표시하기

• 두 연결요소의 균일성 측정

  • 두개의 region 에 대해서 하나라도 균일하지 않으면 큰 값(균일하지 않음)
  • k는 분할의 세밀함 조절하는 매개변수(작을수록 세밀하게 분할. diff와 intra 사이의 차이를 조정)

• 두 연결요소가 적절히 분할되어 있는지 판정

  • $D(C_i, C_j)$ 가 참이면 두 연결요소는 거칠지도 세밀하지도 않은 적당한 상태
  • 멀티 인트라 : 2개의 전체 픽셀의 개수 분의 k(k 는 이미작 크면 클 수록 높은 값)

• 영상 $f$ 의 분할 $S$

  • 컬러 영상에서는 식 (5,10) 의 거리 척도 사용

  • $f$ 를 $r$ 개의 영역 $S={C_1, C_2, ..., C_r}$ 로 분할했을 때, 모든 쌍의 $D(C_i, C_j)$ 가 참이면 분할 $S$ 는 거칠지도(저분할) 세밀하지도(과분할) 않은 적절한 상태

  • 이런 분할을 어떻게 찾을 것인가? $\to$ greedy 알고리즘으로 해결

• 알고리즘) 최소 신장트리를 이용한 영상 분할

  • $V_{p}$ 와 $V_{q}$ 를 잇고 각각이 속한 연결요소(영역) 이 다면 같다면(같은 영역으라면) 각 연결 요소 $C_{p}$, $C_{q}$ 를 하나의 연결요소로 만들기

---

3.2) 정규화 절단

• 유사도 그래프와 Wu 의 분할 품질 척도

  • 행렬은 거리로 표현하는 것이 아닌 유사도로 표현
  • 즉, 회색 부분을 하나의 영역이라고 했을 때, 이 영역을 어떻게 나눌지 좋을지를 판단하는 방법
  • 예) 거리가 $d$ 일때, 유사도 : ($9-d$) 로 계산

• Wu 의 척도 cut $\to$ 작을수록 유리한 분할(즉, 회색 표시된 6개의 화소의 영역에서 6+6=12 인 ❶ 보다 7 인 ❷ 가 유라) $\to$ 과분할 문제

• Shi 의 정규화 절단 [Shi2000]

  • cut 의 문제점을 Shi 로 해결
    • 원래 연결요소를 작은 것과 큰 것으로 분할하는 경향
    • 두 연결요소 간의 에지 개수가 적으므로 cut 이 작아짐
    • 예) 분할 1의 cut 은 12, 분할 2는 7 $\to$ 하지만 직좐적으로 분할 1이 우수
  • Shi 는 정규화 절단 ncut 으로 확장하여 문제를 해결
  • ncut 이 최소가 되는 분할을 찾는 문제는 NP-complete 임을 증명 $\to$ 근사해 구함

• 근사해 탐색 알고리즘

  • W는 그림 5-11 의 인접 행렬이고, D는 $d_{ii} = \sum w_{ij}$ 인 대각선 행렬
  • $\lambda$는 고유값, y는 고유 벡터

• 영상 분할

  • 식 (5.14)의 고유값과 고유벡터를 이용하여 영상 분할
  • [그림 5-11]의 인접행렬 W(화소 사이의 '인접 거리'만 고려) 대신 실제로 쓰이는 유사도 $S_{pq}(0$ ~ $1)$
    • 화소의 특징값(명암 또는 컬러)뿐 아니라 화소 사이의 거리도 같이 사용
    • 즉, 특징값이 비슷할수록 거리가 짧을수록 큼
    • 특징값이 크게 다르더라도 이웃이면 같은 영역이 된다거나 특징값이 비슷하더라도 멀면 다른 영역에 배정할 가능성 확보 $\leftarrow$ 전역 최적화

• 영상 분할 알고리즘

---

4

4. 민시프트

• 모드$_{mode}$ 탐색

  • 샘플이 주어진 경우, 어떤 점이 속한 모드(봉우리) 를 찾는 문제
  • y의 모드는? x$_2$(not x$_1$)
  • 만약 함수 p(x) 가 주어진 것이 아니라, 샘플들이 주어지면? y$_2$(not y$_1$) (예를 들어, 함수를 샘플들의 확률밀도함수 pdf로 가정)
    • 주어진 y 의 값만을 가지고 어디가 봉우리인지를 알아보기 위해 y 가 뭉쳐진곳이 봉우리다 라는 모드 탐색으로 가능
    • y1 과 y2 값을 가지고 봤을때 y 는 y1 이 뭉쳐있기 때문에 y1 으로 속해야한다는 결과
  • 실제로는 1차원이 아니라 d차원의 문제

4.1) 군집화

• 파젠 창을 이용한 확률분포 추정

  • 주어진 샘플 집합 X(n개의 d차원 점으로 구성)
  • 어떤 점 x에 커널 k()를 씌우고 커널속에 들어오는 샘플의 가중치 합 계산하여 x에서의 함수값 p(x) 추정
  • h 는 커널의 폭(클수록 많은 샘플이 창 안으로 들어와 매끄러운 함수가 생성됨)
• 차원 d가 커질수록 기하급수적으로 메모리와 계산 시간 증가
  • 2차원 : $(x,y) = 100^2$
  • 3차원 : $(r,g,b) = 100^3$
  • 5차원 : $(x,y,r,g,b) = 100^5 = a[100][100][100][100][100]$
    • 명시적으로 확률 분포 추정하려는 시도는 수학적으로 그럴싸하지만 비현실적임

• 민시프트

  • 우회적으로 소속(모드)을 결정하는 기법
  • $y$ 를 $y_0$ 로 놓고 시작하여, 수렴할 때까지 $y_0 \to y_1 \to y_2 \to ...$ 반복
  • y 값을 이동시키면서 봉우리를 찾는다.

• 민시프트를 이용한 군집화 알고리즘

  • 모든 점에 대해 식 (5.19) 로 수렴점 찾은 후, 군집 배정
  • 뛰어난 군집화 알고리즘
  • 군집 개수 자동 결정, 임의 모양 군집, 설정할 매개변수(h) 적음

• 알고리즘) 민시프트를 이용한 군집화

  • $y_{t}$ 에서 많이 밀집되어있는 오른쪽으로 이동하여 $y_{t+1}$ 로 이동하는 민시프트 수행
  • y를 y1, y2 ... 계속 진행하다가 입실론 값 미만으로 이동이 점점 줄어들다가 결국 한 지점에서 멈추게 된다. 현재값과 이전값을 게산하여 이동값이 입식론이 미만이다 하면 break 하여 해당 값을 v 집합에 넣는 식.

4.2) 영상 분할과 스무딩

• 민시프트를 영상 분할에 어떻게 적용할까? [Comaniciu2002]

  • 영상 $f$ 를 샘플 집합 $X$ 로 변형
    • 화소가 샘플이 됨

• 몇 차원으로 표현할것인가?

  • 컬러만 표현하면 2.2 절의 k-means 와 비슷한 결과 (그림 5-6)
  • 컬러 x$^{r}$ = $(r,g,b)$ 와 화소의 위치 x$^{s}$ = $(y,x)$ 를 같이 표현 $\to$ 5차원 벡터 x = $(r,g,b,y,x)$
  • x$^{r}$ 과 x$^{s}$ 의 스케일 차이를 고려하여 커널을 별도로 표현
  • 즉, 컬러값 뿐만 아니라 위치에 대한 y,x 값을 같이 표현하여 결과적으로 5차원의 벡터로 계산

• 알고리즘) 민시프트를 이용한 영상 분할

  • Luv 라는 컬러 집합을 이용
  • 5차원 공간, $x_{i}$ 는 5개의 차원
  • MN 모든 화소에 대해서 반복
    

---

5

5. 워터셰드

• 워터셰드란?

  • 워터셰드(분수계) : 빗물이 안쪽과 바깥쪽 중 하나로 흐를 수 있는 점(붉은선)
    • 워터셰드(봉우리)를 하나의 영역으로 취급
  • 유역 (물이 차는 부분) : 같은 호수로 빗물이 모이는 점들의 집합
    • 위치 3, 8, 12 는 워터셰드, 1~2, 4~7, 9~11, 13~14 는 유역

• 영상 분할에 적용

  • 에지 강도 맵의 워터셰드는 두 영역을 가르는 경계에 해당
  • 에지 강도 맵에서 워터셰드를 어떻게 찾을 것인가?

• 댐 건설 방법

  • 영상 분할 = 에지 강도 맵에서 워터셰드를 찾는 과정 -> 댐 건설 방법
  • 댐 = 워터셰드 = 영상 분할 경계면
  • 위 그림에서 물을 주입하면 수위1에 물이 고인다 $\to$ 유역 1, 2, 4에 호수 생성
  • 물을 더 넣어 수위2까지 채우면 $\to$ 유역 3에 호수 생성
  • 수위가 3이 되면 $\to$ 유역3과 4가 범람해 합쳐짐. $\to$ 댐이 필요!
  • ...
  • 수위가 5가 되면 $\to$ 유역 1과 2, 유역 2와 3, 유역 3과 4가 범람 $\to$ 각각 댐이 필요!
  • 그리고 최고 수위가 되므로 알고리즘 멈춤

• Meyer의 방법 [Meyer93]

  • 우선순위 큐 (힙) 사용
    • 화소값이 낮을수록 우선순위 높음(낮은 화소부터 조사가 이루어지도록)
    • 각 GD 에 대한 에지 강도 맵을 구하여 최솟값을 갖는것부터 하나씩 우선순위 큐에 넣기

• 워터셰드를 영상 분할에 적용하면

  • 에지 강도 맵을 활용하지만 반드시 폐곡선 형성
  • 잡음으로 최저점이 많이 생겨 과분할 경향
  • 워터셰드 적용하여 일부로 과분할한 후, 각 영역을 슈퍼 화소로 간주하고 영상 분할의 초기 입력으로 사용

---

6

6. 대화식 물체 분할

• 물체/배경 분할

  • 관심있는 물체 하나만 잘라내는 분할(예, 의료영상에서 특정 장기만 분할)
  • 사용자가 초기 곡선 지정 $\to$ 대화식 시스템
  • 컴퓨터 비전과 컴퓨터 그래픽스의 협동

6.1) 능동 외각선

• 원리

  • 초기 곡선에서 시작하여, 최적 상태(안정적인 에너지 상태)를 능동적으로 찾아감
  • 폐곡선을 취한 후에 폐곡선이 점점 커지면서 외각이 어디인지를 찾아 객체와 배경을 분리하는 작업

• 외곽선 표현

  • 연속적인 공간에서는 0~1 로 표현 : $g(s) = (y(s), x(s)), 0 \le s \le 1$
  • 디지털 공간에서는 $g(s) = (y(s), x(s)),$ $s=0,1,2,...,n$
  • g(0) = g(6) -> 폐곡선

• 스네이크 [Kass87]

  • 스네이크 알고리즘으로 외각찾기
  • 최초의 능공 외곽선 기법
  • 외곽선의 총 에너지 $E^*$
  • 3가지 영역으로 나누어 각각 계산
    • $E_{internel}$(곡선) : 곡선의 내부 에너지
      • "물체의 경계는 매끄럽다" 는 전제하에, 곡률이 작을수록 큰 값 가짐(즉, 심하게 꼬불꼬불한 곡선 보다 매끄러운 곡선을 선호) $\to$ 정규화
    • $E_{image}$(이미지) : 영상의 명암에 반응하는 항(line/edge/termination 등 sailent feature 측면)
      • 찾고자하는 곳은 물체의 경계이므로 에지 강도가 클수록 작은 값 가짐
    • $E_{constraint}$ : 사용자가 지정한 모양 반영
      
      
  • $E^*$ 가 최소가 되는 곡선을 찾는 최적화 문제
• 외각선의 에너지 총합 E*(g(s))의 계산
• 정답에 가까울수록 에너지가 낮아 뱀이 움직일 필요가 적어지고, 그렇지 않으면 에너지가 높아 뱀이 격렬하게 움직인다.
• 분할뿐 아니라, stereo matching, motion tracking(optical flow) 등에도 적용 가능
• 최적해 탐색 알고리즘
  • 초기 곡선 $g_0(s)$ 에서 시작하여, 수렴할 때 까지 $g_0(s) \to g_1(s) \to g_2(s) \to ...$ 반복
  • 동적 프로그래밍 [Amini1988]
  • 탐욕 알고리즘 [Wiliams1992]
• Wiliams 알고리즘
  • 개선된 에너지 수식 사용

• 알고리즘) 스네이크(탐욕 알고리즘)

  • 초기 곡선을 사용자가 입력한 후에, 스네이크 곡선 $g(t)$ 에서 $g(t+1)$ 로 이동할떄 알고리즘을 적용한다
  • 물체의 경계면에서의 이동이 더뎌지기 때문에 그 값이 $T$ 보다 작으면 break

즉, 에너지가 높으면 뱀이 막 움직이면서 외곽선이 움직이다가, 에너지가 최소가 되면 뱀의 움직임이 최소회 되면서 멈춘다는 느낌

6.2) 그래프 절단

• 네트쿼크 흐름 문제 [Ahuja94]

  • 교통 흐름, 전기 흐름 등 많은 응용
  • $S$ 에서 출발하여 $T$ 로 흐르는 최대 용량은?
    • 병목으로 인해 어떤 에지는 최대 용량 발휘 못함
    • 아래 그래프의 최대 흐름 은 6 (2 1 1 2 로 자르면 올바르게 자른것)

• 영상 분할과 어떻게 관련 되나?

  • 영상을 그래프로 변환
    • 영상의 화소를 노드로 간주하고, 유사도를 에지 가중치로 설정
    • 예) [그림-20] 의 절단은 최소 그래프 절단임
      • $S$ 와 $T$ 사이에 있는 4개의 노드가 화소 $S={v_1, v_2, v_3, v_4}$
      • 이 절단은 최적의 영상 분할임
  • 최소 절단을 어떻게 찾을 것인가?
    • Ford 의 정리 [Ford62] 에 따르면, 네트워크 최대 흐름은 그래프의 최소 절단 과 같음
    • 최대 흐름 찾는 효율적인 알고리즘이 존재

• 영상 분할 알고리즘

  • 최대 흐름을 찾으면, Ford의 정리에 따라 그것이 바로 최소 절단이다.
  • 최소 절단은 최적의 영상 분할 정보를 가진다.

• 그래프 $G=(V+\{S,T\},E)$ 를 구축하는 방법 (알고리즘 5-11의 1행)

  • 에지 가중치(유사도)는 아래 수식 사용
  • 객체와 배경 구분
  • 어떤 부분은 객체이다, 어떤 부분은 배경이다 라고 초기 값을 제공한다음 게산할수도있다.
  • 총 9+2 = 11 개의 노드들이 그래프에 존재하게된다.
    $\to$ 3x3 행렬에서 가장 큰 값이 9 니까 에지 가중치 수식을 사용
    $\to$ 아래 그림에서는 간단히 $9-[f(v_q) - f(v_q)]$ 가정 (화소 노드간 수평 에지)
• S 는 물체와, T는 배경과 연결(S & T 와 화소 노드간 "수직" 에지)
  $\to$ 용자가 지정한 물체 (O) 와 배경(B) 지정

• 사용자가 지정한 물체 (Object) 와 배경(Background) 정보 반영

  • O로 지정된 화소는 노드 $S$ 와 큰 값, 노드 $T$ 와 0
  • B로 지정된 화소는 노드 $S$ 와 0, 노드 $T$ 와 큰 값
  • 나머지 화소 $p$ 는

• 최소 절단 탐색 (2행)

  • [Ford62] 와 같은 일반적인 알고리즘 대신, 영상의 특성을 감안한 [Boykov2004] 이용
  • 예) 그림 5-22 에서 얇은 선이 최소 절단에 해당하는 에지

• 촤소 절단을 영상 분할로 변환 (3행)

  • 모든 화소는 $S$ 와 $T$ 중 하나에만 굵은 선으로 연결됨
  • $S$ 에 굵은 선으로 연결된 노드는 물체, $T$ 에 굵은 선으로 연결된 노드는 배경으로 구분

• 그래프 절단 알고리즘의 특성

  • 에지는 $S$ 와 $T$ 에 연결된 에지 그룹, 화소끼리 연결된 에지 그룹으로 구분
  • 두 종류의 에지는 상호 보완적으로 동작
    • $\{S, T\}$ 와 연결된 에지는 사용자가 지정한 정보에 충실
    • 화소 노드를 연결하는 에지는 영상이 가진 정보에 충실
    • $\lambda$ 를 크게 (또는 극단적으로는 화소끼리 연결 값을 0)하면, 사용자가 지정한 정보에 충실