05-(1). Image Segmentation

 

 

Contents

1. Principle of Image Segmentation

2. Traditional Method

3. Graph Method

4. Mean Shift

5. Interactive Object Segmentation

---

1. Principle of Image Segmentation

조건 1. 분할된 영역은 서로 겹칠 수 없다.

조건 2. 모든 영역은 전체 입력 영상을 덮어야 한다.

조건 3. 같은 영역에 속한 모든 화소는 비슷한 명암값처럼 비슷한 성질을 가져야 한다.(<=> 이웃한 영역은 서로 다른 성질을 가져야 한다.)

위의 조건을 수식으로 표현하면 이와 같다.

 

Q. 적절한 분할이란?

• Under segmentation(저분할) : 위에 언급한 조건을 엄격하게 적용한 결과, 분할된 영역의 갯수가 너무 적음
• Over segmenation(과분할) : 너무 세밀하게 분할된 경우

Q. 어느 정도까지 세밀하게 분할해야 할까?

결론 : 정답은 없다. 컴퓨터 관점에서 분할은 "인식"을 위한 이전 단계이다. 

영상 분할의 근원적인 어려움을 보여주는 예시는 다음과 같다.

같은 영상을 좌하단에 위치한 영상에서 시작하여 반시계 방향으로 진행하며 점점 확대한 것이다.

 

가장 크게 확대한 좌상단의 영상을 살펴보면, 물체의 경계를 어디로 그어야 적절한지 불명확하다. 인간은 물체에 대한 이전 모델의 지식을 동원하여 인식과 동시에 분할을 수행하지만, 컴퓨터는 그 단계까지 발전하지 못하였다.

 

Edge는 명암값에 급격한 변화가 발생하는 지점에 해당한다. 개념적으로 그러면 영역의 경계와 일치하기 때문에, 단순히 edge detection을 수행하여 얻어진 엣지들로 영역을 구분하면 안될까?라는 의문이 생길 수 있지만

영역(segment)이 형성되기 위해서는 완벽한 폐곡선을 이루어야 한다는 점에서 3장에서 공부한 엣지 검출로 영역분할까지 수행하는 데에는 한계가 있다는 점이다.

 

그렇다면 4장에서 공부한 지역 특징점(Local Feature)로 영역 분할을 수행할 수는 없을까?
영역은 물체를 나타내는 연결된 화소의 집합이기 떄문에, 한 점을 지칭하는 특징점으로 영역 분할을 수행하는 것은 비효율적이다.

그 지역 특징점을 중심으로 일정한 크기의 마스크를 씌워 들어오는 화소들을 보고 영역을 추출할 수 있다. 하지만, 추가적인 해석 과정을 거쳐야만 주어진 목적을 달성할 수 있으며 과정이 복잡하다. 

하지만, 사람은 무언가를 인식할 떄 지역 특징이 아니라, 영역 정보를 사용한다. 인간에 맞먹는 성능을 달성하기 위해서는 높은 품질의 새로운 영상 분할 알고리즘이 필요하다.

 

 

2. Traditional Method

전통적 방법은 특수한 조건을 만족하거나 단순한 영상(ex, 공장 자동화, 문서 인식)에서 잘 작동하지만, 일반적인 자연 영상에서는 아주 낮은 성능을 보인다.

주어진 문제가 쉽다면 굳이 복잡한 알고리즘 대신 그냥 쉬운 전통적 방법을 사용하면 된다.

2- 1. Thresholding

어두운 배경에 밝은 물체가 주어진 경우 (혹은 반대) 이진화를 사용하면 물체 영역과 배경 영역을 쉽게 분할할 수 있다.

이런 경우 2장에서 배운 Otsu's method를 이용하면 효과적이다.

 

하지만, 물체 여러 개가 서로 다른 밝기를 가진다면? 이진화로 해결할 수 없다. 더 많은 threhold를 설정한다.

2-1-1. Double Threshold Otsu's Method

위의 달 사진은 최소 밝기 구간이 3개 이상으로 분할된다. (검정, 회색, 흰) 최소 삼진화가 필요하다

여기서 세 부류는 $t_1$보다 작은 값을 가진 화소 /$ t_1$~$t_2$사이의 화소/ 그리고$ t_2$보다 큰 값을 가지는 화소를 의미한다.

$t_1$ & $t_2$ : 두 개의 임계값이 필요하다.

그리고 이 임계값을 이용하여 부류 간 분산 $v_b(t_1,t_2)$가 계산되어야 한다.

아래 수식을 이용하여 계산할 수 있다. $u_g$는 입력영상 전체 화소의 평균 값이고, $u_i$는 각 부류에서의 평균을 의미한다. $h$는 히스토그램 값을 의미한다. 여기에 hat을 붙이면 정규 히스토그램을 의미한다. i번째 화소에서의 히스토그램 값을 $h_i$로 표기하였다.

각각의 영역이 다를수록 더 좋은 분할이므로, 분산 $v_b$가 최대화될수록 좋은 분할이다.

따라서 이 값이 최대화되는 임계값 $t_1, t_2$를 구한다.

최댓값을 구하는 방법은 가능한 모든 $(t_1, t_2)$ 쌍을 집어넣고 조사하는 것이다. 

 

2-1-2. Adaptive Thresholding

이전의 이중 임계값 오츄 알고리즘은 모두 전역적인(Global) 방법이다. 임계값을 결정하고 전체 영상에 적용하기 떄문이다.

위의 그림(b)는 하나의 임계값으로 이진화한 결과, (c)는 임계값 두 개를 설정하여 삼진화한 결과이다.

효모라는 물체 특성상 효모 내부가 지역적으로 명암이 다르기 때문에, 결과가 만족스럽지 모하다. 이런 경우, 적응적 임계화(Adaptive Thresholding)을 고려할 수 있다.

 

그래서 적응적 임계화는 임계값을 어떻게 정하는가?

우선 임계값 $t$가 $t(j,i)$로 변경된다. 위치에 따라서 임계값이 달라지게 하기 때문에, 단순히 값이 아니라 화소 위치(j,i)에 대한 함수로 표기하는 것이다.

 

임계값을 결정하는 방법은 화소의 위치(j,i)의 이웃을 보고 결정하는데, 이웃은 nxn 정방형 또는 반지름이 r인 원형을 보고 결정한다.

개념적으로 이해는 쉽지만 구현은 쉽지 않다. Adaptive threshold $t(j,i)$를 정하는 방법은 정해진 것이 아니라, 영상의 특성에 따라 방법을 정해야 하기 때문이다. 

 

하지만, 결론적으로 Thresholding을 이용한 영상 분할은 아무리 정교하 방법으로 임계값을 설정하더라도 성능 한계를 보일 수 밖에 없다.

 

2-2. Clustering

화소를 RGB 공간에 매핑한 후, K-means clustering 방법같은 군집화를 수행하는 방법이다.

초기 군집 설정을 개선하고 k값을 조절하여 좀 더 좋은 결과를 얻을 수 있지만, 매우 지루하고 여전히 낮은 수준을 맴돌 것이다.

왜냐하면 군집화 과정은 화소 사이의 지리적 근접성을 무시하고 색깔의 매핑공간만을 이용하기 때문이다.

 

3. Graph Method

그래프란? G=(V,E)

노드 집합 V={v1, v2, …, vn}과 에지 집합 E로 구성되어 있다. 노드의 개수 n은 이미지에서 화소의 개수와 동일하다. 영역 분할 결과 얻어진 각각의 영역을 슈퍼 화소(uper pixel)라고 부른다.

노드 간의 가중치 즉, 두 노드 $v_p$와 $v_q$를 연결하는 에지는 가중치 $w_{pq}$를 갖는다. 이때 가중치는 유사도 또는 거리(다른 정도)를 이용해서 측정할 수 있다.

 

그래프 알고리즘의 기본 원리는 간단하다. 

▷ 유사도가 높아 비슷한 노드 쌍은 같은 연결요소(영역)에 속해야 한다.

▷ 유사도가 낮은 노드 쌍은 다른 연결요소에 속해야 한다.

▶ 유사도가 낮은 에지를 중심으로 분할선을 결정한다.

 

그래프 알고리즘은 지역 최적해가 아니라, 전역 최적해를 추구한다. 그렇기 때문에 지역적으로 유사도가 낮더라도, 전역적으로 판단할 때 자르지 말아야 한다면 분할선으로 취하지 않기 떄문에 바로 분할선이 '된다'가 아니라 '가능성이 더 높다'라고 표현해야 한다.

본격적으로 이러한 그래프를 이용한 영역 분할 알고리즘 두 가지를 소개한다.

 

3-1. Minimum Spanning Tree (최소 신장 트리)

spanning tree를 이용하여 최적의 분할을 찾아내는 방법이다. 즉, 그래프에서 여러 개의 최소 신장트리를 찾아가는 방식이다.

아래의 그림에서 연결요소(영역) $ C = {v_1, v_6, v_7, v_{11}, v_{12}}$를 살펴보자. (진하게 표시된 영역)

빨간 색으로 써진 부분이 노드 간의 엣지를 의미하고, 빨간 숫자는 엣지 가중치(거리)를 의미한다.

여기서 아까 말한 C는 5개의 노드와 5개의 에지로 구성된 부분 그래프이다. 최소 신장트리를 구하면, 그림에서 빨간색으로 표시한 4개의 엣지로 구성된다. 즉, $MST(C) =$  { $(v_1, v_6), (v_6, v_{11}), (v_{11}, v_{12}), (v_{12}, v_7)$ }

 

이 연결요소 C가 하나의 영역으로 형성될 수 있을지를 측정하는 식 intra(C)는 다음과 같이 계산한다.

연결요소 C의 균일성 측정

즉, MST의 에지 중에서 가장 큰 가중치를 취한다. 

1. C에서 노드를 추가하며 영역의 크기를 키워나가는 경우, intra(C)만으로 지역 균일성을 측정하는 데에 무리가 없다.

2. 하지만 연결요소가 2 개 있을 때를 생각해보자.

각각의 연결요소를 $C_i$, $C_j$라고 하고, 이 둘을 같이 고려할 때 이들이 얼마나 균일한지 측정하는 multi_intra값을 아래처럼 계산하는 방법을 사용한다. 둘 중 하나라도 균일하지 않다면, multi_intra(.)는 큰 값을 가짐으로써 균일하지 않음을 알려준다. (작아야 좋은 것)

 

여기서 매개변수 k는 연결요소 간의 차이 diff(.)와 연결요소 간의 균일성 intra(.)사이의 차이를 위한 일종의 임계값 역할을 한다. 따라서 분할의 세밀함을 조정한다. k가 작으면 더 세밀하게 영역을 분할하면서 많은 수의 작은 영역을 생성한다.

이제 분할 알고리즘이 multi_intra값을 이용해서 분할을 수행했다고 가정하자.

분할이 잘 이루어졌는지 평가하기 위해선 아래의 $D(C_i, C_j)$ 를 이용한다. 참을 가지면, 두 연결요소는 거칠지도 세밀하지도 않은 적당한 상태로 분할되었다고 판정한다.

D가 참을 가지면, 두 연결요소는 거칠지도 세밀하지도 않은 적당한 상태로 분할되었다고 판정한다.

 

컬러 영상의 경우, RGB 세 개의 채널을 독립적으로 분할한 후, 그들을 하나로 합친다. 세 채널 모두에서 같은 연결요소에 속할 떄만 같은 연결요소로 취한다.

또 다른 방법으로는, 세 채널을 벡터로 취급하여 벡터 간의 거리(다른 정도)를 사용하는 것이다.

분할 결과

시그마는 분할 이전에 수행한 가우시안 스무딩의 크기 의미

 

3-2. 정규화 절단

3-2-1. Wu의 방법

그래프를 구성할 때, 거리 대신 유사도를 에지 가중치(w)로 사용한 점이 다르다.

오른쪽의 W행렬은 에지가중치를 그래프 표현에 맞게 행렬로 나타낸 것

Wu는 cut(.)이라는 함수를 제안한다.

여기서 w는 에지 가중치 즉, 여기서는 유사도(9-거리)를 의미하기 때문에, 값이 작을수록 유리한 분할이다. 왜냐하면 분할결과로 생성되는 두 연결요소가 서로 다를수록 좋다는 그래프 알고리즘의 기본 원칙 때문이다.

따라서 위의 cut(.)함수값은 일종의 목적 함수 역할을 하게 된다.

 

하지만, 원래 연결요소를 작은 것과 큰 것으로 분할하는 경향이 있으며 즉, 두 연결요소 간의 에지 개수가 적어지게 학습되기 떄문에 분할된 영역들의 크기가 작다는 경향을 띌 수 밖에 없다. 

이런 문제점을 보완하기 위해 Shi의 방법이 등장했다.

 

3-2-2. Shi의 방법

ncut(.)을 제안한다. 거의 비슷하지만, $assoc(C_i, C)$가 분모로 정규화하는 역할을 해준다는 점이 다르다.

이때 $assoc(C_i, C)$는 연결요소 $C_i$와 분할 이전의 연결요소 $C$ 사이의 가중치 합이다.

 

이렇게 개선된 ncut(.)은 작은 크기의 연결요소를 선호하지도 배척하지도 않고 중립적인 특징을 띈다.

 

그래서, 이렇게 목적함수를 설정했는데 이값이 최소가 되는 연결요소들은 어떻게 찾는것인가?

Shi는 ncut(.)을 사용하여 최적해를 찾는 문제는 NP_complete임을 증명하였다고 한다.(뭐 어쩌란거지)

하지만 다행히 근사해를 구할 수 있음을 보였고 알고리즘을 다음과 같이 제시했다.

알고리즘 상에 있는 식 5.14는 아래와 같다. 

D는 d_ii=∑_j▒w_ij 인 대각선 행렬이고, W는 위에서 보인 가중치 인접 행렬이다. 고유값 계산을 해야 한다.

마치 통계학의 스펙트럼 분해와 비슷하게 생긴 듯 하다.

이렇게 해서 구해진 고유 벡터는 최적 분할 정보를 갖고 있다. 

예를 들어 행렬 A가 25x25행렬이라고 할 떄, 25개의 고유값과 그에 상응하는 고유벡터를 얻을 텐데, 이때 2번째로 작은 고유값에 해당하는 고유벡터를 취한다.

 

식 5.15는 실제 명암 영상에서 사용할 수 있는 유사도를 식으로 나타낸 것이다. 이것들을 각각의 노드에서 유사도를 측정해 w행렬 즉, 인접 가중치 행렬을 계산할 수 있다.

f(.)는 노트의 특징 값(화소값), x(.)는 화소의 위치을 의미하고 분모의 시그마는 가우시안 스무딩

 

알고리즘 5-5로 분할한 결과이다