Efficient Graph-Based Image Segmentation
[cite]10.1023/B:VISI.0000022288.19776.77[/cite]
Introduction
이 시대의 세그멘테이션의 주요 쟁점은 하이 레벨에서의 컴퓨터 비전 알고리즘을 적용하기 위한 전처리 과정으로의 세그멘테이션에 초점이 맞추어져 있는 듯 하다. 대부분의 논문에 하이 레벨 비전에 대한 언급이 한 두 문장 쯤은 있는 것이 일반적인 분위기인 것 같은데,이 논문 역시 그러한 목적을 서두에 밝히고 있다.
이전에 있던 아이겐벡터 기반의 방법들은 기본적으로 이미지의 픽셀의 2승 만큼의 행렬이 필요했기 때문에 메모리나 실행 시간의 제약이 큰 편이었다. 256 x 256의 이미지만 예로 들더라도 4GB의 용량이 필요하다는 것은 엄청나게 큰 수로 다가오는데 이 행렬의 고유값을 구한다니 비현실적인 방법일런지도 모르겠다. 논문에서는 이러한 문제들을 해결한다며 들고 나온 방법이다.
이 방법은 그래프 기반의 모델을 사용하면서도 반복적이지 않고 한 번의 루프만으로 끝난다는 특징이 있다.
Graph-Based Segmentation
간단한 그래프 모델을 사용한다.
$$G = (V, E)$$
$$v_i \in V $$ 세그멘테이션 될 요소들, 즉 각 픽셀
$$ edge(v_i, v_j) \in E $$ 와 그에 해당하는 $$ weight w(v_i, v_j)$$
여기서 가중치 $ w(v_i, v_j) $ 는 인접한 두 픽셀간의 차이에 대한 정도를 나타낸 값으로 음수가 아닌 값을 사용하는데, 인텐시티나 컬러, 모션, 위치에 대한 차이를 사용할 수 있다.
위와 같이 정의하고, 여기에 추가적으로 하나의 레이블로 묶인 픽셀들의 집합 (Component), $ C $를 정의하자. 이 $ C $들의 집합, $ C \in S $, 즉 세그멘테이션의 상태 $ S $ 도 정의하자.
Pairwise Region comparison Predicate
정의된 그래프로부터 다음으로 더 나아간다. 두 가지를 더 정의할 것인데,
- Internal difference of component $ Int(C) $
- Difference between two components $ Dif(C_1, C_2) $
가 그것이다.
Internal difference of component $ Int(C) $ 는 Component내의 정점과 에지로부터 구해진 Minimum Spanning Tree (MST) 에서 가장 큰 weight를 선택하여 구한다.
Difference between two components $ Dif(C_1, C_2) $ 는 두 컴포넌트를 연결하는 에지의 weight 중 가장 작은 weight로 정의한다.
이 두 가지로부터 콤포넌트가 될 조건을 정의하고 있다.
$$D(C_1, C_2) = {\text{ true, if } Dif(C_1, C_2) > M Int(C1, C_2)} \\ { \text{false otherwise}}$$
$$M Int(C_1, C_2) = min(Int(C_1) + \tau(C_1), Int(C_2) + \tau(C_2) )$$
$$\tau(C) = k/|C|$$
이 때, $$ k $$ 는 파라미터로 이미지가 클 수록 큰 값을 갖도록 한다.
약간 복잡해보이지만, 대충 설명하자면 두 컴포넌트 간의 차이가 둘 각각의 내부 집합도보다 크면 두 컴포넌트는 별도의 컴포넌트라는 뜻이 된다.
The Algorithm and Its Properties
알고리즘은 다음과 같이 실행된다.
- 모든 edge의 weight를 정렬하여 $ \phi = (o_1, ..., o_m ) $ weight가 낮은 순서으로 배열한다.
- 처음 세그멘테이션 상태 $ S^0 $ 는 각 픽셀이 모두 각자의 레이벌을 가진다.
- 4번 단계를 $ q = 1, ..., m $ 만큼 반복한다.
- 직전 상태를 기반으로 현재 weight $ o_q = (v_i, v_j) $ 에 대응하는 컴포넌트 C1, C2를 구하고, 이에 대하여 콤포넌트가 될 조건을 만족하는지를 검사한다. 만족하지 않으면 둘을 하나의 콤포넌트로 통합하고, 만족한다면 그대로 둔다.
- 모든 반복을 마치면 최종 단계의 결과를 결과값으로 마무리한다.
Results
시대가 시대이니만큼 약간 엉성하지만 그래도 나름 썩 괜찮을 결과를 보이곤 한다. $ k $ 값에 영향을 많이 받으나 어찌 정할만한 기준은 없는 것 같다. 더군다나 계산 속도가 느린데, 이것은 파이썬으로 구현한 탓인지 본래 느린 것인지 확실치 않다.