[영상처리] Mean-Shift 와 CAMshift 알고리즘

Mean-Shift 와 CAMShift 알고리즘

많은 사람들이 이들 두 알고리즘이 색상 특징값을 기반으로 한다고 알고 있지만, 사실 이것들은 관심영역의 모든 특징값의 분포를 이용할 수 있는 알고리즘이다.

(1) Mean-Shift 알고리즘

Mean-Shift 알고리즘은 데이터 집합의 밀도분포(특징점,코너,색상)를 기반으로
관심영역(ROI: Region Of Interest) 객체를 고속으로 추적하는 알고리즘이다.

초기의 검색 영역의 크기와 위치를 지정하면
반복되는 색 분할 계산에 의해서 색상 클러스터가 발생되고
초기 지정한 색 영역에 기반하여 경계를 결정하여 관심 물체를 추출할 수 있다고 한다.

이것은 mode seeking 알고리즘이라고도 하며,
특정 데이터들의 중심(mean)으로 이동(shift)하는 알고리즘이다.
이를 이용하여 데이터 분포의 mode 를 찾기도 하고, 트래킹도 한다.
(나는 트래킹을 목적으로 mean-shift 에 대해서 조사하였다.)

아래 링크는 mean-shift 를 구현해서 트래킹을 하는 유튜브 영상이다.

http://www.youtube.com/watch?v=RG5uV_h50b0&feature=related

사진으로 보면 아래와 같은 모습이다.

알고리즘에 의해 추적되는 대상을, 인간이 알아보기 쉽게 파란색 사각형으로 시각화 하고있다.

Mean-shift 알고리즘에 의한 관심영역의 특징값 추적

Mean-shift 알고리즘에 의한 관심영역의 특징값 추적

Mean-shift 알고리즘에 의한 관심영역의 특징값 추적

다음 그림을 보자.

위 그림을 살펴보면,
하늘색원은 임의로 선택된 범위(Region of Interest, ROI, 관심영역)이고,
흩어져 있는 빨간점들은 특징점 혹은 특정값이라고 할수 있다.

1. 임의로 하늘색원으로 된 선택된 범위(ROI,관심영역)를 잡고
2. 선택된 범위 안에 들어있는 특징점들의 밀도가 가장 큰 곳을 찾는다. 
3. 밀도가 가장 큰곳을 중심으로 재설정한다
4. 재설정된 중심을 기준으로 임의의 범위를 다시 잡는다.

1)~4)을 다시금 반복하는데 이렇게 반복하면 전체에서 가장밀도가 많은 부분에서 맴돌고 있게 된다.
이렇게 전체영역에서 특정한 고밀도 부분, 혹은 저밀도 부분을 찾는 알고리즘이다.

어떤 특징점 or 특정값을 찾을것인지, 그리고 고밀도 or 저밀도 부분을 찾을것인지는 코딩 하기 나름이다.
(보통 mean-shift 예제가 색상값을 특정값으로 하여 물체를 추적하기 때문에 mean-shift는 색상 추적 알고리즘이라는 오해가 있는 것 같다.)

앞에서의 설명을 기반으로 하는 동작은 위의 애니메이션과 같다.
여기서 mean-shift의 한계를 알수 있는데, 간단히 살펴봐도 아래에 더 많은 밀도가 있는데 관심영역 window는 중심에 머무르는 모습이 보인다.

(2) CAMShift 알고리즘(Continuously Adaptive Mean-Shift)

CAMShift ( Continuously Adaptive Mean Shift Algorithm ) 알고리즘은

Color Segment 방법의 MeanShift 알고리즘을 Streaming(효과,추적) 환경에서 사용하기 위해 개선한 것으로
탐색윈도우의 크기를 스스로 조정하는 기법을 사용하여 Mean-shift의 답점을 보강한다.

객체를 고속으로 추적하는데 사용되며 조도변화, 잡음이 많은 배경에서는 성능이 좋지않은 특징이 있다.

검출된 객체의 영역의 Hue 값의 분포를 이용하여 변화될 위치를 예측하고 탐지한 후
중심을 찾아 객체를 추적하게 된다.

이름에서 알수 있듯이 '연속적인 적응성 평균이동 알고리즘'이므로
mean-shift 를 사용하며 탐색윈도우 크기를 스스로 조정한다는 것이다.

CAMSHIFT 는 널리 알려진 meanshift algorithm의 변형으로 임의의 물체를 추출하기 위해
경험적 분포 (empirical distribution)에서 동작하는 탐색 알고리즘이다.

아래 링크의 유튜브 영상은 캠시프트로 실시간 트래킹 하는 영상이다.

http://www.youtube.com/watch?v=iBOlbs8i7Og

http://www.youtube.com/watch?v=brCMBymdxv4&feature=related 

영상에서 조도의 변화는 휘도에 가장크게 나타난다.
따라서 상대적으로 Hue 값을 사용하면 조명의 영향에 덜 민감하므로 Hue값을 사용한다.
CAMShift의 알고리즘 동작은 아래와 같다

1. 관심영역(ROI)이 주어지면 HSV 색 모델의 Hue값으로 변환한다. 
2. ROI에서 1차원 histogram을 구축하여 저장하고 추적 모델로 사용한다.
3. ?

영상 내에서 여러 개의 윈도우를 설정한다.
각 윈도우의 크기 및 중심점의 위치를 반복적으로 변화시키느데, 이때 윈도우 중심점의 위치는 윈도우 내에 분류된 화소값들의 평균이 되며,

크기는 화소 값들의 합에 비례해 증가한다.

이 과정을 모든 윈도우가 수렴할 때 까지 반복하는데, 윈도우의 수렴여부는 윈도우의 위치와 크기의 변화량에 의해서 결정된다.

즉 변경된 윈도우의 위치와 크기가 이전값과 차이가 없을 때 해당 윈도우는 수렴하게 된다.
영역내의 모든 윈도우가 수렴하면, 최대 윈도우를 출력하는데 실패판정은 다양하다.
예를들면 윈도우의 크기가 30´30 이하인 경우에는 물체영역추출이 실패한 것으로 간주하는등의 방법같이...

물체영역을 추출하기 위해서 CAHSMIFT 는 탐색 윈도우를 설정하고 윈도우 내에 존재하는 화소들의 분류결과에 따라서 윈도우의 크기와 위치를 반복적으로 변화시키며 탐색이 종료되면 최종 윈도우를 물체영역으로 결정한다.

CAMSHIFT는 경사 상승 (gradient ascent)알고리즘으로 부분적 최적해에 수렴될 수 있는데
이를 극복하기 위해 입력 영상내에 여러 개의 윈도우를 설정하는 방법을 사용하기도 한다.
CAMSHIFT 는 지역적으로 window 를 조절하며 동작하므로 모든 영상의 화소를 분류할 필요가 없이
각 window 내의 화소들만 분류하면 된다는 잇점이 있다.

CAMSHIFT가 수렴한 후의 윈도우는
배경부분에 위치한 윈도우의 경우 크기가 변하지 않거나 줄어든 반면, 탐색물체부분에 위치한 윈도우는
크기와 위치가 물체영역을 포함하도록 바뀐 것을 볼 수 있다.

 CamShift 예제는 OpenCV 를 설치하면 Sample로 주어진다. (sample 폴더에 camshiftdemo.c 가 있을것이다.)

처음에 관심영역(ROI)이 주어지면 HSV 색 모델의 Hue값으로 변환한다.
이를 바탕으로 1D histogram을 구축한다.
이 저장된 Histogram은 얼굴 추적 모델로 사용된다.
2D 영상 확률분포에 대해 가 좌표에서의 분포 확률값을 나타낼 때 CAMShift 알고리즘은 다음과 같이 동작한다.

1. 초기에 탐색창(search window)의 크기를 정하고, 탐색창을 초기 중심점(mean location)의 중앙에 오도록 위치시킨다.
2. 새로운 중심점(mean location)은 다음의 알고리즘으로 구해진다. 즉, 먼저 0차 Moment를 구한다. 또, x와 y에 대한 1차 moment를 각각 구한다. 이때, 새로운 탐색창의 중심점(mean location)의 좌표도 구한다.
3. 새로운 탐색창에 대하여 위의 과정을 MeanShift 알고리즘이 수렴할 때까지 반복한다. 

몇가지 Camshift 예제프로그램 실행동영상을 첨부한다.

https://youtu.be/CigGvt3DXIw

http://www.youtube.com/watch?v=6rcTz1IuPGw&feature=player_embedded