[cite]10.1186/1744-9081-8-53[/cite]

오래 전 글의 백업입니다.

2011년 12월 5일
1. Introduction
이 알고리즘은 기본적으로 에너지 미니마이제이션 방법을 사용하고 있습니다. 이 때 에너지는 세그멘테이션이 될 경계선, 즉 Object를 둘러싸는 곡선의 각 지점에서의 에너지를 말합니다. 이 경계(곡선)을 이동시켜가며 에너지가 최소로 되는 경계의 위치을 찾고, 그러할 때 세그멘테이션이 잘 되었다고 판단합니다. 이러한 에너지는 특정 함수를 이용하여 표현할 수 있으며, 에너지 함수를 어떻게 정의하느냐에 따라 성능이나 특징이 달라지게 될 것입니다.
논문에서는 경계를 Snake라고 지칭하며, 반복적으로 알고리즘을 수행할 때마다 경계를 이동시켜가게 되기 때문에 저자는 active라고 표현하였습니다.

2. Basic Snake Behavior
논문에서 사용된 곡선을 정의하는 방법은 Controlled continuity spline 방법[19](레퍼런스를 구할 수가 없습니다.)을 사용합니다. 이러한 spline 곡선 위에서, Internal force와 Image force, External constraint force 세가지의 force를 정의하고 이를 이용하여 에너지를 계산합니다. Internal force는 piecewise smoothness constraint를 제공하고, Image force는 snake를 이미지 피쳐(line, edge, subjective contours)로 이동시켜갑니다. External constraint force는 snake를 local minimum으로 이끄는 효과를 가지고 있습니다.
Spline 곡선의 수식에 따라서, Snake를 정의히자면,

$$ E_{\text{snake}}^* = \int_{0}^{1} E_{\text{snake}} (v(s)), ds $$
$$ = \int_{0}^{1} E_{\text{int}} (v(s)) + E_{\text{image}} (v(s)) + E_{\text{con}} (v(s)) , ds $$
$E_{int}$는 Interal energy를, $E_{image}$는 image force를, $E_{con}$는 external force를 가리킵니다.
아래에서 하나씩 살펴보겠습니다.

2.1 Internal Energy
internal spline energy는 아래와 같이 정의됩니다.

$$ E_{int} = (\alpha(s)|v_s(s)|^2 + \beta(s)|v_{ss}(s)|^2)/2 $$

a(s)에 의해 조절되는 first-order term과 b(s)에 의해 조절되는 second-order term으로 구성됩니다. 이것들은 각각 s에 대하여 v(s)를 한번, 두번 미분한 것으로 보입니다. 글의 맨 아래 제공하는 위키주소를 참고하시면 도움이 됩니다. 곡률이 커지거나 곡선의 변화가 많으면 에너지가 커지게 되어있기 때문에 곡선들이 최대한 얌전한(?) 모양으로 수축하는데 도움이 되는 식으로 보입니다.

2.2 Snake Pit
초기값으로 주어질 Snake는 사람이 마우스로 클릭하여 지정하도록 되어있습니다. 처음 지정한 Snake로부터 출발하여 Minimization 과정을 시작하게 됩니다. 사용자는 Spline 곡선 위의 점과 따로 고정된 점, 두개의 점을 쌍으로 지정하게 되어있습니다(그림 2 참조). 그리고 그것들은 스프링으로 연결되어있습니다. 이 때, x1과 x2에 해당하는 곳에서 E_con 에너지를 할당하게 됩니다.

$$ E_{con} = -k(x1 - x2)^2 $$

3. Image Forces
image forces는 다시 3가지 에너지 함수의 weight mean으로 계산됩니다. 이들은 각각 line, edge, termination입니다.

$$ E_{image} = w_{line} E_{line} + w_{edge} E_{edge} + w_{term} E_{term} $$

이들의 각 weight를 조절하여 snake의 동작을 조절할 수 있습니다.

3.1 Line functional
가장 간단한 이미지에서 사용할 수 있는 함수로 이미지 픽셀의 값을 사용할 수 있습니다.

$$ E_{line} = I(x, y) $$

이를 에너지 함수로 사용하면 weight의 부호에 따라서, snake가 밝은 쪽이나 혹은 어두운 쪽을 지향하게 됩니다. 왜냐하면, 각각 밝은/어두운 곳에서 적은 에너지를 갖게 되기 때문입니다.

3.2 Edge functional
또다른 에너지 함수로 사용할 수 있는 것은 edge(=gradient)입니다.

$$ E_{edge} = -|\nabla I(x, y) |^2 $$

이 식을 사용하면 gradient가 높은 쪽, 즉 edge 쪽으로 snake가 지향하게 됩니다. gradient가 가장 큰 곳에서 가장 낮은 에너지를 갖게 될 것입니다.

3.3 Scale space
3.1의 Line functional을 찾는데, 스케일의 문제로 원하지 않는 결과가 나올 때, 가우시안 함수로 컨볼루션을 한 다음, 0인 지점을 찾으면 다른 스케일에 대하여 찾을 수 있다는 내용 같은데 정확히 이해가 되질 않습니다.

3.4 Termination functional
Curvature를 이용하여 Termination을 구합니다. 정확히 이해가 되질 않스니다. 수식을 이용하면 뾰족한 부분에서 높은 에너지를 갖게 될 것이라 예상됩니다.
이렇게 정의된 각각의 에너지 함수를 이용하여, Snake의 각 픽셀 위치에 대하여 에너지를 계산합니다. 그리고 반복적으로 Snake를 움직여가며, 에너지가 낮은 곳을 찾아 이동하며 minimum 지점을 찾게 됩니다.
논문에서 minimum을 찾는 방법은 Euler method를 이용하여 구해진다고 되어있는데, Gradient descent 방법과 유사하거나 동일한 것으로 보입니다. 전체 에너지 식을 함수 꼴로 만든 다음 함수의 gradient 방향에 따라 지정한 step씩 이동해가며 값을 확인하는 방법입니다. gradient 방뱡의 반대로 이동하기 떄문에 시간이 지나면 local minimum에 도달하는 것은 보장됩니다. 다만, 초기값과 step의 크기에 따라 소요시간에 유의해야합니다.

논문에서는 실험으로 스테레오비전에서의 매칭과 동영상에서의 트래킹을 보여주고 있지만, 따로 다루지 않겠습니다.

참고자료
http://en.wikipedia.org/wiki/Active_contour_model
http://en.wikipedia.org/wiki/Euler_method
http://en.wikipedia.org/wiki/Gradient_Descent