컴퓨터 비전 & 패턴 인식 - 22. 그래프 기반 영상 분할

그래프 기초

 

그래프 G = (노드 V, 간선 E)로 정의

 

 

 

이미지의 그래프화

 

이미지를 그래프로 표한하면 픽셀 하나가 하나의 노드

 

서로 다른 두 노드 v_p, v_q를 연결하는 에지는 가중치 w_pq를 가짐(무방향 그래프)

 

여기서 가중치 w_pq는 두 노드간 유사도나 거리를 의미

 

함수 f(v)가 노드의 명암을 구하는 함수면, 명암 영상에서의 거리와 유사도는 아래와 같이 구할수 있음

 

 

 

 

명암 이미지를 그래프로 표현하기

 

아래의 그림은 입력 명암 영상이지만 명암 차를 에지로 본다면 그래프로 볼 수 있음.

 

유사도가 높은 경우 같은 연결 요소, 영역에 속한것이고,

 

유사도가 낮은 경우 다른 연결요소, 영역에 속한것으로 볼 수 있음.

 

 

 

 

그래프 알고리즘을 통한 영역 분할

 

그래프 알고리즘은 지역 최적해가 아닌 전역적인 최적해를 구하여야 하므로

 

전역적으로 최적해가 아니라면 분할선으로 판단해선 안됨.

 

그래프 영역 분할 고려 사항 2가지

 

1. 목적 함수

 

2. 목적 함수로 최적해를 찾는 효율적인 탐색 알고리즘

 

 

 

 

최소 신장 트리를 이용한 영역 분할

 

우선 신장 트리 spanning tree란 모든 노드를 연결하면서 트리 조건을 만족하는 그래프

 

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

 

 

최소 신장 트리 Minimal Spanning Tree MST는 간선(에지)의 가중치 합이 최소인 신장트리

 

 

https://velog.io/@dnjscksdn98/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC

 

 

다음의 입력 영상과 연결 요소 C = {v1, v6, v7, v11, v12}가 주어질때

 

 

최소 신장 트리 MST(C) = {(v1, v6), (v6, v11), (v11, v12), (v12, v7)}

 

 

 

 

연결 요소의 균일 정도는 최소 신장 트리의 가장 큰 가중치로 구할 수 있음

 

위 경우 intra(C) = 2

 

 

 

최소 신장 트리를 확장하는 경우 v13보다 v8을 추가할때 intra(C) = 2가 되어 균일성이 유지

 

 

 

 

 

두 연결 요소의 균일성 비교

 

연결 요소 C_i, C_j가 주어질때 multi_intra(C_i, C_j)는 균일하지 않으먄 큰 값을 가짐.

 

diff(C_i, C_j)는 두 연결 요소 사이의 다른 정도를 나타내는 척도

 

 

diff(C_i, C_j) > multi_intra(C_i, C_j)으로 참이면 연결요소가 적절하게 분할된 상태.

 

 

위 식에서 tau(C)는 연결 요소 간의 차이 diff()와 연결 요소의 균일성 intra(C) 사이 차이를 위한 임계값

 

|C|가 작을 수록 tau(C)는 큰 값을 가지게 되고, multi_intra(C_i, C_j) 또한 커지므로

 

diff를 더 키워주는 역활. k는 분할 세밀한 정도 조정

 

 

위 내용을 정리하면 입력 영상 f가 r개 연결 요소로 분할 된 경우

 

D(C_i, C_j) = true 인경우 적절히 분할되었음을 의미하며, 더이상 분할되지 않음.

 

 

 

 

 

최소 신장트리 이용한 영상 분할

 

1. 거리를 가중치로 갖는 그래프 생성

 

2. 에지를 오름차순 정렬 

 

3. 초기 분할 수행(한 픽셀이 하나의 연결 요소로 다룸.)

 

4. 모든 에지에 대해 반복

 - i 번째 에지 e = (v_p, v_q)

 - S_i-1에서 v_p와 v_q가 속한 연결요소를 C_p, C_q라 정의

 - C_p != C_q이며, diff(C_p, C_q) <= multi_intra(C_p, C_q)인 경우

  => C_p와 C_q를 합쳐 하나의 연결 요소 만들어 S_i로 

 ** 두 연결요소간의 거리 <= 두 연결요소 간의 균일성 

       ==>두 연결 요소간의 균일성보다 거리가 가깝다 =>하나의 연결요소로 판단

 - 위 조건이 아닌 경우 S_i = S_i-1

 

 

 

 

 

 

최소 신장 트리를 이용한 영상 분할 예시

 

 

https://www.slideserve.com/monita/an-efficient-image-segmentation-algorithm-using-bidirectional-mahalanobis-distance