[Classical Method] Active Contour Model and Level-Set Method

Active Contour Model 와 Level-Set Method 에 대한 개념 및 논문들을 정리한 글입니다.

오늘은 딥러닝 글이 아닌, 딥러닝 이전의 컴퓨터 비전 분야에서 많이 쓰이던 level-set method 에 대해 소개해보려고 합니다.

Active Contour Model

level-set method에 대해 알기 전에 우선 더 큰 개념인 active contour model 부터 알아봅시다.

active contour model은 물체 내부와 외부의 energy minimization 을 통해 변형 가능한 모델을 이미지에 일치시키는 기술입니다. object tracking, shape recognition, segmentation 등의 컴퓨터비전 분야에서 널리 사용되었습니다.

위의 그림처럼 spline 과 energy function 을 정의하고, minimize 하면서 물체의 윤곽을 찾는데 활용할 수 있습니다.

우리는 이제 이것을 segmentation에 활용해보려고 합니다.

위의 그림처럼 curve 위의 n 개의 discrete point들을 정의합니다. 우리는 이 n개의 점을 energy function 에 따라 minimize 하는 방향으로 움직이며 최종적인 edge를 찾을 것입니다.

energy function은 다음과 같이 internal과 external energy로 정의됩니다. 여기서 c는 curve를 말합니다.

\[E(c) = E_{internal}(c) + E_{external}(c)\]

internal energy는 curve의 shape을 조절하는 식으로, 아래식에서 첫번째 term은 stretchy, 두번째 term은 bendy(smoothness)를 의미합니다.

\[E_{int}(c) = \int \alpha \lVert c'(s)^2 \rVert + \beta \lVert c''(s)^2 \rVert ds\]

external energy는 image intensity를 이용하여 edge를 찾도록 도와줍니다. 아래와 같이 gradient를 이용하여 정의할 수 있습니다. 하지만, gradient 만 이용하여 식을 정의하면, curve points들이 너무 edge에서 멀리 정의된 경우에는 제대로 작동하지 않기 때문에, gradient vector flow (GVF) 를 이용한 방법도 있습니다.

\[E_{ext}(c) = \int -\lVert \nabla I(c(s)) \rVert^2 ds\]

지금까지 curve 위의 점들을 정의하여 evolve 시키는 방법으로 segmentation을 하는 방법에 대해 살펴보았는데요, 이러한 방법은 (explicit contour 라고도 말합니다) split, merge 등과 같은 다양한 topological change 들을 다루는데 한계가 있습니다.

이러한 한계점을 극복하기 위해 나온 방법이 바로 implicit contour, level-set method 입니다.

Level-Set Method

Level-set Method에서 에서는 curve를 시간에 따라 evolve 시키는 것이 아닌 surface \(\phi\) 라는 function을 정의하여 이 function을 evolve 합니다.

\[\{x|\phi(x)=c\}\]

그리고 surface \(\phi\)의 c에서 level-set은 위와 같은 식으로 표현합니다. 저희는 주로 c를 0으로 두고, zero-set으로 curve를 정의합니다.

위 그림을 보면 이해가 쉬울 것 같습니다. surface, curve, plane으로 정의가 되어있는데, surface 와 plane이 만나서 생기는 curve를 이용하여 저희가 원하는 segmentation을 하는 것이죠. split 과 merge와 같은 경우에도 잘 작동하는 것을 볼 수 있습니다.

식으로 표현하면 initial \(\phi\) function 과 energy function F를 정의하여, initial function에 t 에 따른 energy function을 더해주면서 function을 evolve 합니다.

따라서 여기서 중요한 것은 initial function \(\phi\) 와 energy function을 잘 정의하는 것입니다.

energy function을 정의하는 방법 두 가지, edge-based와 region-based 관련 대표적인 논문들이 있습니다.

Geodesic Active Contours (1997)

이 논문은 edge-based energy function 방법을 사용한 대표적인 논문입니다.

이 논문에서 t에 따른 \(\phi\)는 다음과 같이 정의가 됩니다.

\[{\partial\phi \over \partial t} = \vert \nabla\phi \vert div({\nabla\phi \over \Vert \nabla\phi \Vert}) + g(I)\Vert\nabla\phi\Vert v + \nabla g(I) \cdot \nabla\phi\] \[g(I) = {1 \over 1+\Vert \nabla I \Vert ^2}\]

첫번째 term은 smoothing term, 두번째 term은 speed controller, 세번째 term은 image attachment term 입니다. g(I)를 정의할 때 image gradient를 사용하여 edge를 찾아갈 수 있도록 하였습니다.

이 논문은 gradient를 사용하여서 edge가 매우 극명하게 나타나는 이미지에서는 결과가 잘 나오지만, noise가 매우 큰 이미지, 아니면 edge가 매우 smooth한 이미지 같은 경우에는 잘되지 않습니다.

Active Contours Without Edges (2001)

edge-based의 단점을 극복하기 위해 나온 방법 region-based energy function을 처음으로 정의한 논문입니다.

energy function은 아래와 같이 정의됩니다.

\[F(c_1, c_2, \phi) = \mu \ \int\delta(\phi(x,y))\vert\nabla\phi(x,y)\vert dxdy + v\int H(\phi(x,y))dxdy + \lambda_1 \int \vert I(x,y) - c_1 \vert ^2 H(\phi(x,y)) dxdy + \lambda_2 \int \vert I(x,y) - c_2 \vert ^2 (1-H(\phi(x,y))) dxdy\]

첫번째 term은 length \({\phi=0}\), 두번째 term은 area \({\phi \ge 0}\), 세번째 term은 inside(C), 네번째 term은 outside(C) 를 의미합니다.

여기에서 inside intensity average, outside intensity average c1 과 c2를 각각 정의하여서 내부의 intensity distribution를 이용하여 segmentation 되도록 하였습니다.

t에 따른 \(\phi\)는 다음과 같이 정의가 됩니다.

\[{\partial\phi \over \partial t} = \delta_\varepsilon(\phi) [ \mu \ div({\nabla\phi \over \vert\nabla\phi\vert}) - v - \lambda_1(I - c_1)^2 + \lambda_2(I-c_2)^2]\]

이 경우 edge가 매우 분명하게 나타나지 않는 경우에도 잘 작동을 합니다. 다만, internal object의 intensity distribution이 일정해야지 잘 된다는 한계점이 있습니다.

---

energy function을 정의하는 방법에 대한 대표적인 논문들을 살펴보았습니다. 더 자세한 내용은 아래 논문 링크에서 더 보시면 좋을 것 같습니다.

energy function 외에도 level-set method를 더 잘 활용할 수 있는 다양한 방법들에 대한 논문들이 있습니다. signed distance function을 유지하기 위해 계속해서 re-initialization을 해줘야 하여 시간이 소요되는 문제를 해결하는 방법을 제안한 논문. interactive 한 방법을 사용하여 segmentation이 잘 되지 않은 부분은 보완해주는 논문. 등이 있습니다.

Reference:
[1] Geodesic Active Contours 논문
[2] Active Contours Without Edges 논문
[3] Level set evolution without re-initialization 논문
[4] Interactive level set segmentation for image-guided therapy 논문
[5] Deep Level Sets for Salient Object Detection 논문
[6] Rich Radke’s Lecture
[7] wiseodd’s blog