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

by Blogger 하얀쿠아
2011. 12. 27. 07:56 소프트웨어 Note/영상처리

Mean-Shift 와 CAMShift 알고리즘

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


(1) Mean-Shift 알고리즘

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

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

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

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



https://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)에서 동작하는 탐색 알고리즘이다.

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


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


https://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



 


이 댓글을 비밀 댓글로
    • 장인태
    • 2012.05.21 15:14
    안녕하세요 ^^ 블로그 잘보고 갑니다. 논문쓰는데 이내용을 참고 하였습니다. 혹시 이내용의 출처를 알수 있을까요?
      • 2012.05.29 01:39
      비밀댓글입니다
  1. 좋은 내용 잘 보았습니다.

    제 카페로 좀 요약해서 퍼갔습니다. 그래도 되겠죠? ㅎㅎ
    • 2014.09.02 02:15
    비밀댓글입니다
    • 이 포스팅은 mean shift와 cam shift 알고리즘의 설명입니다. 이와 관련하여 제가 작성한 소스코드는없습니다. opencv example에 존재하는 코드를 찾아보시면 쉽게 찾을 수 있을 것 같네요.
    • 도경
    • 2014.11.05 21:22
    안녕하세요 과제 중에 mean-shift 알고리즘이 나와서 찾아보다가 들어왔어요. 좋은 글 감사합니다. 이해가 엄청 빨리 됐어요 >.< 복 받으세요~~
    • 제갈현
    • 2015.08.14 15:28
    안녕하세요. 좋은 정보 감사합니다.
    한가지 여쭤보고싶은건 소스코드 다운로드에 링크되있는 홈페이지를 들어가니 이상한 사업창 같은게 뜨더군요. 구입 등의 버튼이 보이던데 소스코드는 구매를 해야되는건가요?
    • 소스코드 다운로드를 제공하던 홈페이지의 도메인주소가 만료되었나 봅니다. 해당 도메인 주소를 매입해서 판매한다는 중국 사이트가 뜨네요 ^^; 해당 링크는 제거했습니다.
    • 양상호
    • 2016.07.01 10:10
    학생인데 정말 좋은내용인듯싶어요! 진짜 도움많이 되었습니다 감사합니다~

OpenCV 2.2 - Visual Studio2010 에 설치하기

by Blogger 하얀쿠아
2011. 5. 24. 19:19 소프트웨어 Note/영상처리

OpenCV 2.2부터는 VS2010용 pre-compiled 버전(VS2008도 사용 가능)이 나온 동시에 OpenCV의 라이브러리들이 대대적으로 정리되고 이름들도 많이 바뀌어서 예전에 만들어둔 프로젝트를 돌리는데 문제가 좀 생기게 되었습니다. 새 버전에 어서 적응하는 방법 밖에 없겠습니다. 허허허헛...

 

2.1에 비해 달라진 점 중 눈에 띄는 몇 가지는 다음과 같습니다.

 - 라이브러리들의 재정리 및 이름 변경

 - 새로운 스테레오비전 알고리즘 등의 최신 기술을 사용한 알고리즘 다수 추가

 - 약 200여 가지의 대대적 버그 수정 (아직 부분적으로 메모리 누수 현상이 있다고 합니다)

 - NVIDIA의 OpenCV에 대한 공식 지원 (CUDA 라이브러리와의 연동으로 데이터 연산에 3D 가속 기능 사용 가능)

 

개인적으로는 3D 가속 기능이 가장 마음에 드는데 CUDA와의 연동을 위해서는 CMake를 이용하여 새로 빌드하는 과정이 필요하므로 여기에서는 다루지 않겠습니다. 나중에 시간이 되면 따로 정리해서 포스팅하죠. 여기에는 VS2010에서 기본적인 코드를 돌리기까지의 방법만 정리해 놓겠습니다. VS2010은 이미 설치되어 있다는 가정 하에 적도록 하겠습니다.

 

*** 설치 정도는 다 알아서 하시는 분들은 바로 PART II VS2010에서의 기본 설정 부분으로 넘어가세요~~

 

PART I   OpenCV 2.2 설치

 

1) 아래의 주소에서 미리 컴파일된 버전인 OpenCV-2.2.0-win32-vs2010.exe를 받습니다. 32비트용이므로 64비트 OS를 쓰시는 분들은 CMake를 사용해서 컴파일 해서 쓰셔야 됩니다.

 http://sourceforge.net/projects/opencvlibrary/files/opencv-win/2.2/



여기에서 맨 아래 38.9메가 짜리를 받으시구요.

 

 

2) 다운받은 설치파일을 실행합니다. 기본값들로 다음,다음,다음.. 버튼들을 마구 눌러주다가~! 아래의 화면에서 'Add OpenCV to the system PATH for all users'를 선택해 줍니다. (현재의 계정에서만 라이브러리를 사용할 경우 for current user를 선택하셔도 됩니다) 라이브러리의 경로가 시스템 환경변수에 등록되어, 프로젝트 실행때마다 dll 파일들을 프로젝트 폴더로 복사해야 하는 수고를 덜어줍니다.

 

** 수동으로 하시려면 첫번째의 Do not ... 이 선택된 상태로 설치하신 후, 내 컴퓨터의 등록정보에서 OpenCV가 설치된 경로의 bin 폴더를 경로로 추가해 줍니다. (기본 경로에 설치시 C:\OpenCV2.2\bin을 추가하시면 되겠죠)

경로 추가에 익숙하지 않은 분들을 위해 조금 더 덧붙이자면...세미콜론을 포함한, ;C:\OpenCV2.2\bin을 붙이시는 겁니다 (아래의 화면을 참고하세요)

Path 부분을 선택하시고...

 


이렇게 입력해 주시면 됩니다.

 

PART II VS2010에서의 기본 설정

 

이제 코드를 작성하기 위한 본격적인 설정 부분입니다. 프로젝트 속성 페이지에 들어가서 뭔가를 만져주고 하던 것들이 2.2에서는 거의 필요가 없습니다. 이전에 VS2008+ OpenCV 2.1 TIPs에 적었던 내용을 응용하면 2.2에서는 더 간단하게 코드에서만 거의 모든 설정을 완료할 수 있습니다. 그걸 설명하려는 것이죠 ㅋ _ㅋ) 일반적인 방법은 뒷부분에 적어두겠습니다.

 

* 설치 경로가 C:\OpenCV2.2 기준이므로 다른 곳에 설치하신 분들은 해당 위치에 맞게 바꿔주시면 됩니다.

 

1) 프로젝트 속성 페이지에서 [구성속성] -> [C/C++] -> [일반] -> [추가 포함 디렉터리] 부분에

 

C:\OpenCV2.2\include

 

라고 적어줍니다. 속성 메뉴에서 해야하는 건 이게 끝입니다. 이전 버전에서 라이브러리 이름을 하나하나 추가해주고 하던 삽질(?)이 이제는 이거 하나로 줄었습니다.

 

 

2) 대신에 코드 부분에서 적어야 하는 분량이 약간 늘었습니다만... 텍스트 파일로 만들어두고 필요할 때 복사해서 쓰시면 되겠네요. 코드 나갑니다. 바뀐 라이브러리들의 이름도 살펴보세요.

 

#include "stdafx.h"
#include "opencv2\\opencv.hpp" // 핵심입니다. 이것 때문에 1) 항목이 있는거죠.

                                                       // 주의 할 점은 stdafx.h 뒤에 붙이셔야 한다는 겁니다.

 

// 여기부터는 복사해서 쓰세요. 라이브러리의 이름들도 바뀌었고, 경로까지 포함해주셔야 합니다.

 

// ----------->8--------------- 절취선 --------------------

#ifdef _DEBUG
    // 디버그 모드에서 사용되는 라이브러리들입니다. (끝에 d가 붙죠)

    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_core220d.lib")
    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_imgproc220d.lib")
    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_highgui220d.lib")
    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_objdetect220d.lib")
    // 필요에 따라 추가할 수 있는 라이브러리들

    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_ml220d.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_features2d220d.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_video220d.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_calib3d220d.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_flann220d.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_contrib220d.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_legacy220d.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_gpu220d.lib")
#else
    // 릴리즈 모드용

    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_core220.lib") 
    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_imgproc220.lib")
    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_highgui220.lib")
    #pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_objdetect220.lib")
    // 필요에 따라 추가할 수 있는 라이브러리들

    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_ml220.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_features2d220.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_video220.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_calib3d220.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_flann220.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_contrib220.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_legacy220.lib")
    //#pragma comment(lib,"C:\\OpenCV2.2\\lib\\opencv_gpu220.lib")
#endif

// ----------->8--------------- 절취선 --------------------

 

// 아래는 샘플 폴더에 있는 레나 할머니의 리즈시절 사진을 띄워서 가우시안 스무딩 처리를 해주는 예제입니다.


int _tmain(int argc, _TCHAR* argv[])
{

    IplImage* src_img = cvLoadImage("C:\\OpenCV2.2\\samples\\c\\lena.jpg", CV_LOAD_IMAGE_ANYDEPTH | CV_LOAD_IMAGE_ANYCOLOR);
    if (src_img == NULL){
        return 0;
    }

    cvNamedWindow("src");
    cvNamedWindow("dst");

    IplImage* dst_img = cvCreateImage(cvGetSize(src_img), src_img->depth, src_img->nChannels);

    cvSmooth(src_img, dst_img, CV_GAUSSIAN, 9);

    cvShowImage ("src", src_img);
    cvShowImage ("dst", dst_img);

    cvWaitKey (0);

    cvDestroyAllWindows();

    cvReleaseImage(&src_img);
    cvReleaseImage(&dst_img);


 return 0;
}

 

** 타이핑도 귀찮으므로 ( ㅋ _ㅋ);; 위의 코드를 첨부파일로 넣었습니다.  

 

결과>>

 

 

PART II-2 다른 설정 방법

 

OpenCVWiki에 있는 내용의 번역 수준이지만 적어두겠습니다.

 

1) [프로젝트 속성 페이지]->[VC++ 디렉터리]->[포함 디렉터리]에 다음을 추가합니다.

 

      C:\OpenCV2.2\include

      C:\OpenCV2.2\include\opencv

 

2) [프로젝트 속성 페이지]->[VC++ 디렉터리]->[라이브러리 디렉터리]에 다음을 추가합니다.

 

      C:\OpenCV2.2\lib

 

3) [프로젝트 속성 페이지]->[링커]->[입력]->[추가 종속성] 부분에 아래의 파일들을 입력합니다.

 

    - [구성]을 Debug에 놓고 아래를 입력합니다.

      C:\OpenCV2.2\lib\opencv_core220d.lib
      C:\OpenCV2.2\lib\opencv_highgui220d.lib
      C:\OpenCV2.2\lib\opencv_video220d.lib
      C:\OpenCV2.2\lib\opencv_ml220d.lib
      C:\OpenCV2.2\lib\opencv_legacy220d.lib
      C:\OpenCV2.2\lib\opencv_imgproc220d.lib

 

    - [구성]을 Release에 놓고 아래를 입력합니다.

      C:\OpenCV2.2\lib\opencv_core220.lib
      C:\OpenCV2.2\lib\opencv_highgui220.lib
      C:\OpenCV2.2\lib\opencv_video220.lib
      C:\OpenCV2.2\lib\opencv_ml220.lib
      C:\OpenCV2.2\lib\opencv_legacy220.lib
      C:\OpenCV2.2\lib\opencv_imgproc220.lib

 

 

 이렇게 하고 #include "stdafx.h"와 main 함수 사이의 내용을 아래로 바꾸면 동일한 결과를 얻을 수 있습니다.

 

#include <cv.h>
#include <cxcore.h>
#include <highgui.h>

출처 : http://blog.naver.com/hamstery?Redirect=Log&logNo=110102815307

이 댓글을 비밀 댓글로
    • 둔산동 프리덤
    • 2011.06.14 23:03
    꺅 전영호다~!
    • 둔산동 프리덤
    • 2011.06.14 23:03
    꺅 전영호다~!
    • 둔산동 베이베
    • 2012.03.11 01:32
    ㅋㅋㅋㅋ 영호 블로그다