[영상추적#1] Mean Shift 추적

영상에서 물체를 추적하고자 할 때, 보통 가장 먼저 떠오르는게 mean-shift 방법일 것이다. 하지만 막상 mean-shift를 이용하여 영상 추적을 하려면 실제 어떻게 해야 하는지 막막한 경우가 많다. 가장 기본적인 방법임에도 불구하고 처음에는 헤매기 쉽다 (저도 그랬습니다 ^^).

1. Mean Shift 란?

시력이 매우 나쁜 사람을 산에다가 던져놓고 산 정상을 찾아오라고 하면 어떻게 될까? 당연히 눈이 보이는 한도 내에서는 가장 높은 쪽으로 걸음을 옮길 것이고, 이렇게 가다보면 산 정상에 다다를 수 있을 것이다. 이러한 탐색 방법을 힐 클라임(Hill Climb) 탐색 방법이라고 부르는데, Mean Shift도 Hill Climb 탐색 방법의 일종이다.

Mean Shift는 어떤 데이터 분포의 peak 또는 무게중심을 찾는 한 방법으로서, 현재 자신의 주변에서 가장 데이터가 밀집된 방향으로 이동한다. 그러다 보면 언젠가는 분포 중심을 찾을 수 있을 거라는 방법이다.

예를 들어, 2차원 평면상에 데이터들이 분포되어 있는데 Mean Shift를 이용하여 이 데이터들이 가장 밀집된 피크(peak) 점을 찾는다고 하자. Mean Shift의 탐색반경을 r이라 했을 때, Mean Shift 알고리즘은 다음과 같다.

1. 현재 위치에서 반경 r 이내에 들어오는 데이터들을 구한다: (x1,y1), (x2,y2), ..., (xn,yn)
2. 이들의 무게중심의 좌표 (∑xi/n, ∑yi/n)로 현재 위치를 이동시킨다.
3. 1~2 과정을 위치변화가 거의 없을 때까지, 즉 수렴할 때까지 반복한다.

Mean Shift란 용어는 평균(mean)을 따라 이동(shift)시킨다는 뜻이다. Shift란 용어는 어떤 것이 현재 상태 그대로 위치만 변할 때 사용된다. 마이클 잭슨의 빌리지인~ 춤을 생각하기 바란다. 여기서는 크기가 고정된 탐색 윈도우를 이동시킨다는 의미이다.

2. Mean Shift 에 대해 좀 더 알아보기

앞서, Mean Shift는 Hill Climb 탐색 방법의 일종이라고 했는데, 비슷한 뜻으로 gradient descent search, blind search, greedy search 등이 있다. 이러한 류의 탐색 방법은 효과적이기는 하지만 local minimum에 빠지기 쉽다는 문제점이 있다. 예를 들어 앞의 산의 정상을 찾는 문제에서 던져진 사람은 바로 옆에 높은 산이 있더라도 처음 출발한 산의 정상만을 찾게 될 것이다. 만일 처음에 매우 완만한 구릉에서 출발했다면 그 구릉 꼭대기에서 멈춰버릴 것이고 그 옆의 진짜 높은 산 정상은 가지 못할 것이다.

Mean Shift와 같은 Hill Climb 방식은 global minimum을 찾지 못하며, 초기위치(출발위치)에 따라서 최종적으로 수렴하는 위치가 달라질 수 있다. 초기 위치는 문제에 따라 미리 주어지거나, 아니면 무작위로 임의의 위치에서 시작하거나, 혹은 전체 데이터의 평균 위치에서 출발하는 등의 방법이 있을 수 있다.

Mean Shift에서는 기본적으로 주변의 지역적인(local) 상황만 보고 진행방향을 결정하기 때문에, Mean Shift를 적용하기 위해서는 먼저 탐색반경(search radius)의 설정이 필요하다. 탐색반경을 너무 크게 잡으면 정확한 피크(peak) 위치를 찾지 못하게 되며, 반대로 너무 작게 잡으면 local minimum에 빠지기 쉬워진다.

Mean Shift의 가장 큰 단점 중의 하나는 탐색 윈도우(탐색 반경)의 크기를 정하는 것이 쉽지 않다는 것이다. 특히 영상 추적의 경우 대상 물체의 크기, 형태 변화에 따라 탐색 윈도우의 크기나 형태를 적절히 변경해 주어야 하는데 이게 적절히 변경되지 않으면 추적 성능에 많은 영향을 끼치게 된다.

Mean Shift는 물체추적(object tracking) 외에도 영상 세그멘테이션(segmentation), 데이터 클러스터링(clustering), 경계를 보존하는 영상 스무딩(smoothing) 등 다양한 활용을 갖는다. 구체적 활용 예 및 보다 심도깊은 이론적 내용에 대해서는 "Mean shift: a robust approach toward feature space analysis", PAMI 2002년도 논문을 참조하기 바란다.

3. Mean Shift를 이용한 영상 이동체 추적

영상추적을 하는 사람들은 Mean Shift를 하나의 추적방법인 것처럼 생각하지만, Mean Shift는 하나의 일반적인 방법론적 도구일 뿐이다. 따라서, Mean Shift를 가지고 영상 추적을 하는 것은 사실은 별개의 얘기이다.

Mean Shift를 이용한 영상추적 방법은 사실 Comaniciu, Ramesh, Meer, "Real-time tracking of non-rigid objects using mean shift", CVPR 2000 논문에 있는 방법을 지칭한다 (저자들은 mean-shift에 대해 특허도 걸어 놓았다). 여기서 설명하고자 하는 mean shift 추적 방법도 기본적으로는 이 논문에 있는 방법이다.

기본 아이디어는 아래 그림과 같이 추적하고자 하는 대상 물체에 대한 색상 히스토그램(histogram)과 현재 입력 영상의 히스토그램을 비교해서 가장 유사한 히스토그램을 갖는 윈도우 영역을 찾는 것이다.

그런데 이렇게 직접 히스토그램을 비교할 경우에는 모든 가능한 윈도우 위치에 대해 각각 히스토그램을 구하고 또 비교해야 하기 때문에 시간이 너무 오래 걸린다.

따라서 실제로는 아래 그림과 같이 histogram backprojection 기법과 mean shift를 결합한 방법을 사용하는 것이 일반적이다 (이렇게 해도 가장 유사한 히스토그램 영역을 찾을 수 있다는게 위 CVPR 2000 논문의 핵심 내용이며, 논문에 그 증명이 나와있다)

먼저, 영상에서 추적할 대상 영역이 정해지면 해당 윈도우 영역에 대해 히스토그램을 구하여 객체 모델로 저장한다. 이후 입력 영상이 들어오면 histogram backprojection을 이용해서 입력 영상의 픽셀값들을 확률값으로 변경시킨다. 이렇게 구한 확률값 분포에 대해 mean shift를 적용하여 물체의 위치를 찾는다. 만일 물체의 크기 변화까지 따라가고 싶은 경우에는 찾아진 위치에서 윈도우의 크기를 조절해 가면서 저장된 모델과 가장 히스토그램 유사도가 큰 스케일(scale)을 선택한다.

4. Mean Shift 추적 구현

[히스토그램 구하기]

색상 모델은 RGB, HSV, YCbCr 등 어느것을 써도 된다 (큰 차이가 없다). 또는 그레이(gray)를 사용하거나 HSV의 H(Hue)만 사용해도 된다. 히스토그램은 윈도우에 들어오는 픽셀들에 대해 각 색상별로 픽셀 개수를 센 다음에 확률적 해석을 위해 전체 픽셀수로 나눠주면 된다.

[히스토그램 백프로젝션(backprojection)]

현재 입력 영상에 있는 픽셀 색상값이 추적하고자 하는 객체 모델에 얼마나 많이 포함되어 있는 색인지를 수치화하는 과정이다. 모델 히스토그램을 Hm, 입력 이미지 I의 픽셀 x에서의 색상값을 I(x)라 하면 백프로젝션 값은 w(x) = Hm(I(x)) 와 같이 구할 수 있다. 그런데, 보통은 현재 입력 영상에 대한 히스토그램 H를 구한 후 w(x) = sqrt{Hm(I(x))/H(I(x))}와 같이 모델 히스토그램 값을 현재 영상 히스토그램 값으로 나누는 것이 일반적이다. 이렇게 값을 나누어 주면 모델에 포함된 색상값들이 그 비율에 관계없이 일정하게 높은 w값을 갖게 하는 효과가 있다. 예를 들어, 추적하고가 하는 물체가 빨간색 영역이 10%, 파란색 영역이 90%로 구성된 경우를 생각해 보기 바란다.

[Mean Shift 적용]

히스토그램 백프로젝션을 통해 얻은 w값들을 일종의 확률값처럼 생각하고 mean shift를 적용하는 것이다. 이전 영상 프레임(frame)에서의 물체의 위치를 초기 위치로 해서 다음과 같이 mean shift를 적용한다.

즉, w를 가중치(weight)로 해서 현재 윈도우(window)내에 있는 픽셀 좌표들의 가중평균(무게중심) 위치를 구하는 것이다. 이렇게 구한 x_new가 새로운 윈도우의 중심이 되도록 윈도우를 이동시킨 다음에 수렴할 때까지 이 과정을 반복하는 것이다. 식에 있는 K(ri)에서 K는 커널(kernel) 함수, ri는 현재 윈도우 중심에서 xi까지의 거리를 나타낸다. 커널함수는 배경의 영향을 줄이기 위한 목적으로 사용하는데, 윈도우 중심에서 가장 높은 값을 갖고 중심에서 멀어질수록 값이 작아지는 방사형의 symmetric 함수가 주로 사용된다. 아무래도 윈도우의 경계 부근에서는 배경 픽셀이 포함될 확률이 높기 때문에 경계로 갈수록 가중치를 낮춰주는 것이다. 실제 커널 함수로는 Epanechnikov 함수가 주로 사용된다.

아니면 그냥 윈도우에 내접하는 타원에 대해 타원 내부에 있으면 1, 외부면 0인 함수를 커널로 사용해도 된다.

[히스토그램 유사도 측정]

두 히스토그램 H1 = {p1,...,pn}, H2 = {q1,...,qn} 사이의 유사도는 보통 Bhattacharyya 계수(coefficient)를 이용해서 계산한다.

Bhattacharyya 계수는 두 히스토그램이 일치할 때 최대값 1, 상관성이 하나도 없으면 최소값 0을 갖는다.

[물체의 크기(scale) 결정]

일단 mean shift로 위치를 찾은 다음에 윈도우의 크기를 조금씩 변경시켜 보면서 모델 히스토그램과 현재 윈도우 영역에 대한 히스토그램을 비교한다. Bhattacharyya 계수가 가장 큰 경우를 찾으면 된다.

5. Mean Shift 샘플 동영상

직접 구현한 Mean Shift 추적기를 실제 영상추적에 적용한 샘플 동영상이다. 녹색이 배경과 잘 구분되기 때문에 초반에는 비교적 잘 추적하지만 후반부에는 같은 팀 선수들 사이로 여기저기 옮겨다니는 걸 볼 수 있다.

6. Mean Shift 추적에 대한 생각

Mean Shift 추적은 일단은 가장 기본적인 방법이기 때문에 영상 추적을 한다면 한번 정도는 직접 해 볼 필요가 있다. 하지만 성능은 그다지 기대하지 않는 것이 좋다. 추적하고자 하는 물체와 배경이 유사한 색상을 가지면 실패하기 쉽상이기 때문이다. 또한 물체의 크기가 변하는 경우도 큰 문제이다. Mean Shift 추적은 윈도우 크기가 잘못되면 성능이 형편없어진다.

그럼에도 불구하고 Mean Shift 추적은 대상의 형태가 변하는 경우에 유용하며, 가볍고 빠르기 때문에 나름 유용하다. 일반적인 실외환경이 아니라 제한된 환경 및 응용에서는 Mean Shift가 매우 강력한 방법이 될 수도 있다. 또는 Mean Shitf를 다른 추적 방법과 상호 보완적으로 결합하여 사용하는 것도 좋은 방법이 될 것이다.

아래 동영상은 유투브에서 발견한 것인데 mean shift가 성공적으로 적용되는 경우들을 보여준다. 후반부에 나오는 경찰 추격신이 꽤나 흥미롭다.

by 다크 프로그래머