한라산 정상
올라가는 길
내려가는 길
백록담 정경*
* 인용: http://www.hallasan.go.kr/hallasan/
http://blog.daum.net/wjdgns70/8880532
2014년 6월 3일 화요일
TBB tutorials
TBB설치 (VS 2008)
○ www.threadingbuildingblocks.org
접속->Download메뉴->안정화버전(Stable Release) 선택. 최신버전링크 클릭.
○ 원도 운영체제의 경우: tbb40_20110809oss_win.zip선택
○ 20MB파일을 받아 폴더에 압축 해제. 이 폴더 위치를 잘 기억함.
○ 환경변수 설정: TBB_INSTALL_DIR을 사용. 내컴퓨터->속성->시스템보호->고급->환경변수설정->새로만들기: 변수이름(TBB_INSTALL_DIR), 변수값(d:\tbb\tbb40_20110809oss) 등 설정
실행 디렉토리 설정
○ 속성->구성속성->디버깅->명령->찾아보기. 생성되는 파일, dll 등의 위치 설정.
DLL부분:
○ 속성->구성속성->C/C++->일반->추가 포함 디렉토리: 여기에
\(TBB_INSTALL_DIR)\include , 단 tbb설치가 되어 있고, TBB_INSTALL_DIR키워드는 미리설정, Release/Debug모드 별로 설정
○ 속성->구성속성->링커->일반->출력파일: ../Release/tbbMatch_Parallel_Dll.dll (모드별로 설정)
○ 속성->구성속성->링커->일반->추가 라이브러리 디렉토리:
\$(TBB_INSTALL_DIR)\lib\ia32\vc9 (VC++9버전의 경우)
○ 속성->구성속성->링커->입력->추가종속성: tbb.lib (release), tbb_debug.lib(debug모드)
Run부분:
○ 속성->구성속성->C/C++->일반->추가 포함 디렉토리: 여기에 $(TBB_INSTALL_DIR)\include, 단 tbb설치가 되어 있고, TBB_INSTALL_DIR키워드는 미리설정, Release/Debug모드 별로 설정
○ 속성->구성속성->링커->일반->추가 라이브러리 디렉토리: $(TBB_INSTALL_DIR)\lib\ia32\vc9 (VC++9버전의 경우)
○ 속성->구성속성->링커->입력->추가종속성: ../Release/tbbMatch_Parallel_Dll.lib tbb.lib(Release모드), ../Debug/tbbMatch_Parallel_Dll.lib(Debug모드), (release), tbb_debug.lib(debug모드)
배포시 Debug/Release모드에 맞는 dll/lib파일 생성방법
○ DLL프로젝트부분에서 속성->구성속성->링커->일반->출력파일: ../Debug/visOCV_debug.dll(Debug모드), 또는 ../Release/visOCV.dll(Release모드) 입력하면 해당명의 dll생성
Solution을 통한 DLL과 Run프로젝트 동시 작성
○ 파일->새로만들기->프로젝트->기타프로젝트형식->Visual Studio 솔루션:
빈솔루션/이름(적당한 이름으로 설정해 준다)/위치(적당한 위치로 설정해 준다)
○ 솔루션탐색기의 솔루션을 오른쪽 마우스로 클릭->추가->새프로젝트->Visual C++->Win32->Win32콘솔응용프로그램(이름, 위치 설정), 다음 누르고 옵션에 Dll(D)과 빈프로젝트(E) 선택후 마침
○ 솔루션탐색기의 솔루션을 오른쪽 마우스로 클릭->추가->새프로젝트->Visual C++->Win32->Win32콘솔응용프로그램(이름, 위치 설정), 다음 누르고 옵션에 콘솔응용프로그램(O)와 빈프로젝트(E) 선택후 마침
솔루션에 딸린 두 프로젝트 생성이 되었다면 개별 프로젝트의 설정을 시작한다:
○ Dll 프로젝트의 속성->구성속성->링크->일반->출력파일: 모드별로 ../Release/파일이름.dll과 ../Debug/파일이름_debug.dll 입력. 이 두 파일이 생성된 dll파일들로 모드별로 생성함. 생성된 dll을 사용할 때도 모드에 마추어 사용하여야 한다.
○ Run용 프로젝트 속성->링커->입력->추가종속성: 모드별로 ../Release/파일이름.lib와 ../Debug/파일이름_debug.lib입력. dll이 아니고 lib이다. 즉, Dll프로젝트에서 생성한 dll파일을 실행 프로젝트에서 사용할 것이라는 점을 명시하는 부분이다.
종속성을 설정한다:
○ 솔루션->프로젝트종속성: Run프로젝트가 Dll프로젝트에 종속되어야 한다(왜냐하면 Run프로젝트가 먼저 생성된 dll을 사용하여야 하기 때문). 따라서 프로젝트(R):에 Run프로젝트 선택, 다음에 종속(D):에 Dll프로젝트 체크
○ 코딩후 빌드->전체다시빌드 한다. (debug모드, release모드 각각 실행)
○ 솔루션->Dll프로젝트->속성->구성속성->디버깅->명령: 찾아보기 눌러 솔루션/debug밑에 생성되어 있는 실행파일(debug모드)을 선택, 솔루션/release밑에 생성되어 있는 실행파일(realse모드)을 선택해 준다.
○ 다시 리빌드 하면 완료.
프로그램의 작성
○ Dll 프로젝트 디렉토리 내에 필요한 파일을 다 넣고, Run 디렉토리에는 Run 프로그램만 넣는다.
예를 들면, Dll 프로젝트 내에 header파일과 cpp파일이 있다면, Run 부에는 Dll부의 cpp를 호출하기 위해 Dll부의 header파일을 include하는 Run 프로그램 파일만 넣는다.
// Dll프로젝트 내의 header파일
#define DLLEXPORT
#ifdef DLLEXPORT
#define DLL_MODE __declspec(dllexport)
#define EXPIMP_TEMPLATE
#else
#define DLL_MODE __declspec(dllimport)
#define EXPIMP_TEMPLATE extern
#endif
#pragma once
#include <iostream>
#include <vector>
#include <math.h>
#include <time.h>
#include <conio.h>
using namespace std;
class DLL_MODE visTestDll
{
public:
visTestDll(int a, float b);
visTestDll();
~visTestDll();
};
상기한 header파일의 선행연산자 부분은 그대로 사용하면 된다. 다만 나중에 DLL생성 후, Dll 프로젝트 부분의 소스를 제거하고 사용할 때에는 첫줄의 #define DLLEXPORT 만 제거한 후 사용한다.
// Dll 프로젝트 내의 실행소스 코드
#include "TestDll.h"
visTestDll::visTestDll() {}
visTestDll::visTestDll(int a, float b)
{
printf("%4d, %8.4f\n", a, b);
}
visTestDll::~visTestDll()
{
printf("Destructing...\n");
}
특별한 연산은 하지 않으며 객체 생성 후 인자를 화면에 출력하는 작업을 한다.
Run 프로젝트 내에 존재하는 실행(호출) 파일은 다음과 같다.
// Run 프로젝트 내의 Dll 호출(실행) 파일
#include "../TestDll/TestDll.h"
int main()
{
visTestDll a(10, 20.0f);
return 0;
}
○ www.threadingbuildingblocks.org
접속->Download메뉴->안정화버전(Stable Release) 선택. 최신버전링크 클릭.
○ 원도 운영체제의 경우: tbb40_20110809oss_win.zip선택
○ 20MB파일을 받아 폴더에 압축 해제. 이 폴더 위치를 잘 기억함.
○ 환경변수 설정: TBB_INSTALL_DIR을 사용. 내컴퓨터->속성->시스템보호->고급->환경변수설정->새로만들기: 변수이름(TBB_INSTALL_DIR), 변수값(d:\tbb\tbb40_20110809oss) 등 설정
실행 디렉토리 설정
○ 속성->구성속성->디버깅->명령->찾아보기. 생성되는 파일, dll 등의 위치 설정.
DLL부분:
○ 속성->구성속성->C/C++->일반->추가 포함 디렉토리: 여기에
\(TBB_INSTALL_DIR)\include , 단 tbb설치가 되어 있고, TBB_INSTALL_DIR키워드는 미리설정, Release/Debug모드 별로 설정
○ 속성->구성속성->링커->일반->출력파일: ../Release/tbbMatch_Parallel_Dll.dll (모드별로 설정)
○ 속성->구성속성->링커->일반->추가 라이브러리 디렉토리:
\$(TBB_INSTALL_DIR)\lib\ia32\vc9 (VC++9버전의 경우)
○ 속성->구성속성->링커->입력->추가종속성: tbb.lib (release), tbb_debug.lib(debug모드)
Run부분:
○ 속성->구성속성->C/C++->일반->추가 포함 디렉토리: 여기에 $(TBB_INSTALL_DIR)\include, 단 tbb설치가 되어 있고, TBB_INSTALL_DIR키워드는 미리설정, Release/Debug모드 별로 설정
○ 속성->구성속성->링커->일반->추가 라이브러리 디렉토리: $(TBB_INSTALL_DIR)\lib\ia32\vc9 (VC++9버전의 경우)
○ 속성->구성속성->링커->입력->추가종속성: ../Release/tbbMatch_Parallel_Dll.lib tbb.lib(Release모드), ../Debug/tbbMatch_Parallel_Dll.lib(Debug모드), (release), tbb_debug.lib(debug모드)
배포시 Debug/Release모드에 맞는 dll/lib파일 생성방법
○ DLL프로젝트부분에서 속성->구성속성->링커->일반->출력파일: ../Debug/visOCV_debug.dll(Debug모드), 또는 ../Release/visOCV.dll(Release모드) 입력하면 해당명의 dll생성
Solution을 통한 DLL과 Run프로젝트 동시 작성
○ 파일->새로만들기->프로젝트->기타프로젝트형식->Visual Studio 솔루션:
빈솔루션/이름(적당한 이름으로 설정해 준다)/위치(적당한 위치로 설정해 준다)
○ 솔루션탐색기의 솔루션을 오른쪽 마우스로 클릭->추가->새프로젝트->Visual C++->Win32->Win32콘솔응용프로그램(이름, 위치 설정), 다음 누르고 옵션에 Dll(D)과 빈프로젝트(E) 선택후 마침
○ 솔루션탐색기의 솔루션을 오른쪽 마우스로 클릭->추가->새프로젝트->Visual C++->Win32->Win32콘솔응용프로그램(이름, 위치 설정), 다음 누르고 옵션에 콘솔응용프로그램(O)와 빈프로젝트(E) 선택후 마침
솔루션에 딸린 두 프로젝트 생성이 되었다면 개별 프로젝트의 설정을 시작한다:
○ Dll 프로젝트의 속성->구성속성->링크->일반->출력파일: 모드별로 ../Release/파일이름.dll과 ../Debug/파일이름_debug.dll 입력. 이 두 파일이 생성된 dll파일들로 모드별로 생성함. 생성된 dll을 사용할 때도 모드에 마추어 사용하여야 한다.
○ Run용 프로젝트 속성->링커->입력->추가종속성: 모드별로 ../Release/파일이름.lib와 ../Debug/파일이름_debug.lib입력. dll이 아니고 lib이다. 즉, Dll프로젝트에서 생성한 dll파일을 실행 프로젝트에서 사용할 것이라는 점을 명시하는 부분이다.
종속성을 설정한다:
○ 솔루션->프로젝트종속성: Run프로젝트가 Dll프로젝트에 종속되어야 한다(왜냐하면 Run프로젝트가 먼저 생성된 dll을 사용하여야 하기 때문). 따라서 프로젝트(R):에 Run프로젝트 선택, 다음에 종속(D):에 Dll프로젝트 체크
○ 코딩후 빌드->전체다시빌드 한다. (debug모드, release모드 각각 실행)
○ 솔루션->Dll프로젝트->속성->구성속성->디버깅->명령: 찾아보기 눌러 솔루션/debug밑에 생성되어 있는 실행파일(debug모드)을 선택, 솔루션/release밑에 생성되어 있는 실행파일(realse모드)을 선택해 준다.
○ 다시 리빌드 하면 완료.
프로그램의 작성
○ Dll 프로젝트 디렉토리 내에 필요한 파일을 다 넣고, Run 디렉토리에는 Run 프로그램만 넣는다.
예를 들면, Dll 프로젝트 내에 header파일과 cpp파일이 있다면, Run 부에는 Dll부의 cpp를 호출하기 위해 Dll부의 header파일을 include하는 Run 프로그램 파일만 넣는다.
// Dll프로젝트 내의 header파일
#define DLLEXPORT
#ifdef DLLEXPORT
#define DLL_MODE __declspec(dllexport)
#define EXPIMP_TEMPLATE
#else
#define DLL_MODE __declspec(dllimport)
#define EXPIMP_TEMPLATE extern
#endif
#pragma once
#include <iostream>
#include <vector>
#include <math.h>
#include <time.h>
#include <conio.h>
using namespace std;
class DLL_MODE visTestDll
{
public:
visTestDll(int a, float b);
visTestDll();
~visTestDll();
};
상기한 header파일의 선행연산자 부분은 그대로 사용하면 된다. 다만 나중에 DLL생성 후, Dll 프로젝트 부분의 소스를 제거하고 사용할 때에는 첫줄의 #define DLLEXPORT 만 제거한 후 사용한다.
// Dll 프로젝트 내의 실행소스 코드
#include "TestDll.h"
visTestDll::visTestDll() {}
visTestDll::visTestDll(int a, float b)
{
printf("%4d, %8.4f\n", a, b);
}
visTestDll::~visTestDll()
{
printf("Destructing...\n");
}
특별한 연산은 하지 않으며 객체 생성 후 인자를 화면에 출력하는 작업을 한다.
Run 프로젝트 내에 존재하는 실행(호출) 파일은 다음과 같다.
// Run 프로젝트 내의 Dll 호출(실행) 파일
#include "../TestDll/TestDll.h"
int main()
{
visTestDll a(10, 20.0f);
return 0;
}
2014년 5월 12일 월요일
FFT (Fast Fourier Transform)
작성 중...
fft를 기저함수의 입장에서 살펴 본다.
어떤 함수 $f$가 두 벡터의 선형 결합으로 표시된다고 하자.
$f=c_1v_1+c_2v_2$
<그림 1>
예를 들면 <그림 1>에서
$f= \begin{bmatrix}
2 \\
3
\end{bmatrix}
=2 \begin{bmatrix}1 \\ 0 \end{bmatrix}+3\begin{bmatrix}0 \\ 1 \end{bmatrix}
=2v_1+3v_2$
이다. 여기서 $v_1$과 $v_2$는 상호 수직이고 크기가 1인 어떤 벡터이다. 함수 $f$와 이 벡터의 내적을 취하면
$<f,v_1>=(c_1v_1+c_2v_2)\cdot v_1=c_1<v_1,v_1>+c_2<v_2,v_1>=c_1$
$<f,v_2>=(c_1v_1+c_2v_2)\cdot v_2=c_1<v_1,v_2>+c_2<v_2,v_2>=c_2$
가 된다. 확인해보면
$<f,v_1>=[2, 3][1, 0]^T=2$
$<f,v_2>=[2, 3][0, 1]^T=3$
이다. 여기서 $v_1$과 $v_2$를 정규직교벡터(orthonormal vector) 또는 정규직교기라고 한다.
연속 함수 $f(t)$를 일정한 간격으로 샘플링을 해서 얻은 데이터의 벡터를 $f=[c_1,c_2,...,c_N]^T$라 하자. 이 벡터는 샘플링된 데이터의 형태로 함수를 표현한다.
만일 샘플 수를 무한히 크게하면 이 벡터는 함수 $f(t)$가 되고 이 추상적인 공간을 함수공간이라고 한다.
이때 함수 벡터를 $N$차원의 공간에서 나타낸다면 하나의 점이 된다. 그리고, 이 고차 공간에서 각 축의 방향을 $v_i$벡터로 표현한다고 하자.
<그림 2>
<그림 2>의 샘플된 함수 값을 정규직교기로 표현해 보자. 함수의 샘플 값이 모두 $N$개라면 정규직교벡터를
$v_1=\begin{bmatrix}1\\0\\0\\ \vdots \\0\\0 \end{bmatrix}$, $v_2=\begin{bmatrix}0\\1\\0\\ \vdots \\0\\0 \end{bmatrix}$, $\cdots$, $v_N=\begin{bmatrix}0\\0\\0\\ \vdots \\0\\1 \end{bmatrix}$
$<f,g>={1 \over b-a} \int_{i} f(t)g(t) dt$
이다.
이상에서 살펴본 벡터 공간의 정규직교기를 함수공간으로 도입해 보자.
크기가 1이고 서로 직교하는 함수의 집합(함수족이라 하자)이 있다고 가정하자.
그러면 어떤 함수 값은 함수족 요소의 합으로 표시 가능하다.
다시 말하면 임의의 함수는 미리 성질을 알고 있는 많은 함수 성분으로 분해할 수 있다는 것을 의미한다.
어떤 함수 집합 $\phi_k(t), k=1,2,\cdots$를 생각하자. 함수들의 내적이
$<\phi_{m}(t),\phi_{n}(t)>={1 \over b-a} \int_{a}^{b}\phi_{m}(t) \phi_{n}(t) dt =0, (m \neq n)$
$<\phi_{m}(t),\phi_{m}(t)>={1 \over b-a} \int_{a}^{b}\phi_{m}^2 (t)dt =1, (m = n)$
인 성질을 만족하면 정규직교함수라고 한다.
이를 이용하면 임의의 함수 $f(t)$는
$f(t)=c_0\phi_{0}(t)+c_1\phi_{1}(t)+\cdots=\sum_{k=0}^{\infty} c_k\phi_{k}(t)$
이다. 각 계수 값의 결정은
$<f(t),\phi_k (t)>=(c_0\phi_{0}(t)+c_1\phi_{1}(t)+\cdots)\cdot \phi_k (t)$
$=c_0<\phi_{0}(t),\phi_k (t)>+c_1<\phi_{1}(t),\phi_k (t)>+\cdots$
$=c_k<\phi_k,\phi_k>=c_k$
이다. 따라서,
$c_k=<f(t),\phi_k (t)>={1 \over b-a}\int_{a}^{b} f(t) \phi_k (t) dt$
이다.
(예) 함수계 $\{1, \sin t, \sin 2t, \cdots \}$가 $-\pi \sim \pi$ 구간에서 직교함수계인지 확인하시오.
$<1,\sin nt>={1 \over {2\pi}}\int_{-\pi}^{\pi} \sin nt dt =-{1 \over {2n\pi}}[\cos nt ]_{-\pi}^{\pi}=0$
$<\sin mt,\sin nt>={1 \over {2\pi}}\int_{-\pi}^{\pi} \sin mt \sin nt dt
=-{1 \over {2\pi}} \int_{-\pi}^{\pi} {1 \over 2} (\cos (m+n)t-\cos (m-n)t) dt$
$=-{1 \over {4\pi (m+n)}} [\sin (m+n)t ]_{-\pi}^{\pi}+{1 \over {4\pi (m-n)}}[\sin (m-n)t ]_{-\pi}^{\pi}=0$
$<\sin nt, \sin nt>={1 \over 2\pi} \int_{-\pi}^{\pi} \sin^2 nt dt
={1 \over 2\pi} \int_{-\pi}^{\pi} {1 \over 2}(1-\cos 2nt) dt$
$={1 \over 4\pi}[t]_{-\pi}^{\pi} -{1 \over {4\pi 2n}}[\sin 2nt]_{-\pi}^{\pi}={1 \over 2}, (n=1, 2, 3, \cdots)$
위 함수계는 직교는 맞는데 정규는 아니므로 (즉, 동일 함수의 내적이 ${1 \over 2}$이므로) 각 함수에 $\sqrt 2$를 곱해 준다.
따라서
$\{1, \sqrt 2 \sin t, \sqrt 2 \sin 2t, \cdots \}$
가 정규직교 함수계가 된다.
$\circ$ 예제에서 삼각함수의 반각의 공식이 사용되었다:
$\sin^2 {\alpha \over 2}={ {1-\cos \alpha} \over 2}$
fft를 기저함수의 입장에서 살펴 본다.
어떤 함수 $f$가 두 벡터의 선형 결합으로 표시된다고 하자.
$f=c_1v_1+c_2v_2$
예를 들면 <그림 1>에서
$f= \begin{bmatrix}
2 \\
3
\end{bmatrix}
=2 \begin{bmatrix}1 \\ 0 \end{bmatrix}+3\begin{bmatrix}0 \\ 1 \end{bmatrix}
=2v_1+3v_2$
이다. 여기서 $v_1$과 $v_2$는 상호 수직이고 크기가 1인 어떤 벡터이다. 함수 $f$와 이 벡터의 내적을 취하면
$<f,v_1>=(c_1v_1+c_2v_2)\cdot v_1=c_1<v_1,v_1>+c_2<v_2,v_1>=c_1$
$<f,v_2>=(c_1v_1+c_2v_2)\cdot v_2=c_1<v_1,v_2>+c_2<v_2,v_2>=c_2$
가 된다. 확인해보면
$<f,v_1>=[2, 3][1, 0]^T=2$
$<f,v_2>=[2, 3][0, 1]^T=3$
이다. 여기서 $v_1$과 $v_2$를 정규직교벡터(orthonormal vector) 또는 정규직교기라고 한다.
연속 함수 $f(t)$를 일정한 간격으로 샘플링을 해서 얻은 데이터의 벡터를 $f=[c_1,c_2,...,c_N]^T$라 하자. 이 벡터는 샘플링된 데이터의 형태로 함수를 표현한다.
만일 샘플 수를 무한히 크게하면 이 벡터는 함수 $f(t)$가 되고 이 추상적인 공간을 함수공간이라고 한다.
<그림 2>의 샘플된 함수 값을 정규직교기로 표현해 보자. 함수의 샘플 값이 모두 $N$개라면 정규직교벡터를
$v_1=\begin{bmatrix}1\\0\\0\\ \vdots \\0\\0 \end{bmatrix}$, $v_2=\begin{bmatrix}0\\1\\0\\ \vdots \\0\\0 \end{bmatrix}$, $\cdots$, $v_N=\begin{bmatrix}0\\0\\0\\ \vdots \\0\\1 \end{bmatrix}$
와 같이 정의한다면
$f=c_1v_1+c_2v_2+\cdots+c_Nv_N$
가 된다. 즉, 정규직교기의 선형 결합으로 샘플된 어떤 함수 값의 표현이 가능하다.
$f=c_1v_1+c_2v_2+\cdots+c_Nv_N$
가 된다. 즉, 정규직교기의 선형 결합으로 샘플된 어떤 함수 값의 표현이 가능하다.
여기서 $c_i$ 값은 함수 값과 기저벡터 $v_i$의 내적으로 얻을 수 있다.
$c_i=<f,v_i>$
이다.
$c_i=<f,v_i>$
이다.
$f=[f_1,f_2,\cdots,f_N]^T$라고 하고
$f$의 크기(norm)를 생각해보면
$\lVert f \rVert=\sqrt{{f_1}^2+{f_2}^2+\cdots+{f_N}^2}$
이다. 그런데 sample의 갯수 $N$가 많아지면 $\lVert f \rVert$가 커지므로 갯수에 대해 정규화를 하면
$\lVert f \rVert=\sqrt{{{1}\over{N}}({f_1}^2+{f_2}^2+\cdots+{f_n}^2)}=\sqrt{{1 \over N} \sum_{i} {f_i}^2 }$
이다.
$f$의 크기(norm)를 생각해보면
$\lVert f \rVert=\sqrt{{f_1}^2+{f_2}^2+\cdots+{f_N}^2}$
이다. 그런데 sample의 갯수 $N$가 많아지면 $\lVert f \rVert$가 커지므로 갯수에 대해 정규화를 하면
$\lVert f \rVert=\sqrt{{{1}\over{N}}({f_1}^2+{f_2}^2+\cdots+{f_n}^2)}=\sqrt{{1 \over N} \sum_{i} {f_i}^2 }$
이다.
이를 연속함수로 확장하면
$\lVert f \rVert=\sqrt{{1 \over b-a} \int_{a}^{b} {f(t)}^2 dt}$
이다.
또한 두 vector $f$와 $g$의 내적을 취하면
$<f,g>=f_1g_1+f_2g_2+\cdots+f_Ng_N=\sum_{i} f_ig_i$
이다. 차원 $N$에 좌우되지 않게 하면
$<f,g>={1 \over N} \sum_{i} f_ig_i$
이고, 연속 공간에서 표현하면
$\lVert f \rVert=\sqrt{{1 \over b-a} \int_{a}^{b} {f(t)}^2 dt}$
이다.
또한 두 vector $f$와 $g$의 내적을 취하면
$<f,g>=f_1g_1+f_2g_2+\cdots+f_Ng_N=\sum_{i} f_ig_i$
이다. 차원 $N$에 좌우되지 않게 하면
$<f,g>={1 \over N} \sum_{i} f_ig_i$
이고, 연속 공간에서 표현하면
$<f,g>={1 \over b-a} \int_{i} f(t)g(t) dt$
이상에서 살펴본 벡터 공간의 정규직교기를 함수공간으로 도입해 보자.
크기가 1이고 서로 직교하는 함수의 집합(함수족이라 하자)이 있다고 가정하자.
그러면 어떤 함수 값은 함수족 요소의 합으로 표시 가능하다.
다시 말하면 임의의 함수는 미리 성질을 알고 있는 많은 함수 성분으로 분해할 수 있다는 것을 의미한다.
어떤 함수 집합 $\phi_k(t), k=1,2,\cdots$를 생각하자. 함수들의 내적이
$<\phi_{m}(t),\phi_{n}(t)>={1 \over b-a} \int_{a}^{b}\phi_{m}(t) \phi_{n}(t) dt =0, (m \neq n)$
$<\phi_{m}(t),\phi_{m}(t)>={1 \over b-a} \int_{a}^{b}\phi_{m}^2 (t)dt =1, (m = n)$
이를 이용하면 임의의 함수 $f(t)$는
$f(t)=c_0\phi_{0}(t)+c_1\phi_{1}(t)+\cdots=\sum_{k=0}^{\infty} c_k\phi_{k}(t)$
이다. 각 계수 값의 결정은
$<f(t),\phi_k (t)>=(c_0\phi_{0}(t)+c_1\phi_{1}(t)+\cdots)\cdot \phi_k (t)$
$=c_0<\phi_{0}(t),\phi_k (t)>+c_1<\phi_{1}(t),\phi_k (t)>+\cdots$
$=c_k<\phi_k,\phi_k>=c_k$
이다. 따라서,
$c_k=<f(t),\phi_k (t)>={1 \over b-a}\int_{a}^{b} f(t) \phi_k (t) dt$
이다.
(예) 함수계 $\{1, \sin t, \sin 2t, \cdots \}$가 $-\pi \sim \pi$ 구간에서 직교함수계인지 확인하시오.
$<1,\sin nt>={1 \over {2\pi}}\int_{-\pi}^{\pi} \sin nt dt =-{1 \over {2n\pi}}[\cos nt ]_{-\pi}^{\pi}=0$
$<\sin mt,\sin nt>={1 \over {2\pi}}\int_{-\pi}^{\pi} \sin mt \sin nt dt
=-{1 \over {2\pi}} \int_{-\pi}^{\pi} {1 \over 2} (\cos (m+n)t-\cos (m-n)t) dt$
$=-{1 \over {4\pi (m+n)}} [\sin (m+n)t ]_{-\pi}^{\pi}+{1 \over {4\pi (m-n)}}[\sin (m-n)t ]_{-\pi}^{\pi}=0$
$<\sin nt, \sin nt>={1 \over 2\pi} \int_{-\pi}^{\pi} \sin^2 nt dt
={1 \over 2\pi} \int_{-\pi}^{\pi} {1 \over 2}(1-\cos 2nt) dt$
$={1 \over 4\pi}[t]_{-\pi}^{\pi} -{1 \over {4\pi 2n}}[\sin 2nt]_{-\pi}^{\pi}={1 \over 2}, (n=1, 2, 3, \cdots)$
위 함수계는 직교는 맞는데 정규는 아니므로 (즉, 동일 함수의 내적이 ${1 \over 2}$이므로) 각 함수에 $\sqrt 2$를 곱해 준다.
따라서
$\{1, \sqrt 2 \sin t, \sqrt 2 \sin 2t, \cdots \}$
$\circ$ 예제에서 삼각함수의 반각의 공식이 사용되었다:
$\sin^2 {\alpha \over 2}={ {1-\cos \alpha} \over 2}$
$\cos^2 {\alpha \over 2}={ {1+\cos \alpha} \over 2}$
2014년 4월 26일 토요일
Collaborative filtering
협업 필터링이라고도 부른다. 행렬 분해(matrix decomposition)를 활용한 상품 추천 시스템(recommendation system)에 사용된다. 또는 아주 큰 데이터(big data)에 내재되어 있는 내부 성질을 파악하기 위한 마이닝(mining) 알고리즘으로도 사용될 수 있다.
웹 Market에서 상품을 팔면서 구매자의 만족도를 조사하였다.
6명의 구매자에 대해 5개의 상품을 0~5점으로 나누어 만족도가 높을수록 5점에 가까운 점수를
주게 하였더니 아래와 같은 행렬이 얻어졌다.
>>A=[2 3 5 0 0; 1 2 4 0 0; 4 5 4 0 0; 0 1 0 3 4; 1 0 0 4 5; 0 0 0 5 4];
>> A
A =
2 3 5 0 0
1 2 4 0 0
4 5 4 0 0
0 1 0 3 4
1 0 0 4 5
0 0 0 5 4
행렬에서 행(row)은 구매자이고 열(column)은 개별 상품에 해당한다.
행렬을 보고 대략 추정해보면 1~3번 상품에 대해 호의적인 사용자들과
4~6번의 상품에 호의적인 사용자들의 두 그룹으로 나누어진다는 것을 알 수 있다.
A행렬을 특이값 분해(SVD, singular value decomposition)해보면
>>[u,d,v]=svd(A)
u =
-0.4719 0.3337 -0.4308 0.0716 0.1067 -0.6810
-0.3382 0.2434 -0.5548 0.1188 -0.0594 0.7078
-0.5811 0.3908 0.6720 -0.1899 -0.0353 0.1436
-0.3004 -0.3804 0.0835 0.4957 -0.7101 -0.0901
-0.3610 -0.5078 0.1044 0.3629 0.6803 0.0801
-0.3234 -0.5235 -0.1927 -0.7532 -0.1299 -0.0100
d =
10.6983 0 0 0 0
0 10.1159 0 0 0
0 0 2.4316 0 0
0 0 0 1.1504 0
0 0 0 0 0.9895
0 0 0 0 0
v =
-0.3709 0.1944 0.5659 -0.1171 0.7005
-0.4952 0.3026 0.4284 -0.0013 -0.6925
-0.5643 0.4157 -0.6929 0.0641 0.1564
-0.3704 -0.5724 -0.1216 -0.7190 -0.0592
-0.4020 -0.6084 0.0349 0.6821 0.0419
세개의 행렬 u, d, v가 얻어진다.
d행렬 내의 특이값을 보면 2개의 성분이 크고 나머지는 작다.
즉, A행렬의 내재된 성분이 2개가 중요하다는 의미이다.
2개의 성분과 그에 해당하는 u, v행렬의 값만을 이용하여 A행렬을 다시 재생해 보면
>> vt = v';
>> u(:,1:2)*d(1:2,1:2)*vt(1:2,:)
ans =
2.5285 3.5220 4.2523 -0.0619 -0.0241
1.8206 2.5374 3.0657 -0.0693 -0.0437
3.0741 4.2755 5.1518 0.0396 0.0935
0.4441 0.4272 0.2140 3.3931 3.6334
0.4338 0.3579 0.0438 4.3709 4.6782
0.2538 0.1107 -0.2491 4.3124 4.6127
이고 A행렬과 비교해 보면 값이 비슷하다(잘 재생된다).
내재된 성분의 의미를 파악해 보자.
>> u(:,1:2)*d(1:2,1:2)
ans =
-5.0490 3.3752
-3.6186 2.4625
-6.2169 3.9535
-3.2142 -3.8482
-3.8621 -5.1373
-3.4597 -5.2956
행렬의 행은 사용자를 표현하고, 열은 두개의 내재된 성질에 대한 것이다. 즉, 사용자는 2개의 그룹으로 나누어지며
1~3번 사용자는 첫번째 성질에 속하고, 4~6번 사용자는 두번째 성질에 속하는 정도가 크다 (행렬 요소값의 절대치 크기만 보자).
>> vt(1:2,:)
ans =
-0.3709 -0.4952 -0.5643 -0.3704 -0.4020
0.1944 0.3026 0.4157 -0.5724 -0.6084
5개의 상품(각 열)에 대해 첫번째 성질(사용자 그룹)은 1~3열의 상품에 대한 선호도가 높고, 2번째 성질은 4~5열의 상품에 대한 선호도가 높다.
이상과 같이 행렬을 분해해 주는 방법인 SVD를 이용하면 데이터에 내재되어 있는 의미 파악이 가능하다. 이를 이용하면 상품 추천시스템을 만들 수 있다.
이제 어떤 사람의 구매 만족도를 조사하였더니 아래와 같은 데이터가 주어졌다.
B=[3 ? 4 ? 2]
이 사용자는 상품 2, 4를 아직 구매하지 않았다.
이 사람에게 상품 2와 4 중에서 어떤 것을 추천할 것인지 계산해 보자.
먼저 평가가 있는 세개의 상품에 대해 평균을 구해 '?'위치에 대치하자.
(3+4+2)/3=3이므로 3을 대입한다.
>>B=[3 3 4 3 2];
이 사용자를 A행렬의 마지막 행에 추가하고 SVD를 다시 수행한다.
>> C=[A; B]
C =
2 3 5 0 0
1 2 4 0 0
4 5 4 0 0
0 1 0 3 4
1 0 0 4 5
0 0 0 5 4
3 3 4 3 2
>> [u,d,v]=svd(C)
u =
-0.4049 0.3207 0.4210 -0.1967 -0.0883 0.7109 -0.0642
-0.2900 0.2341 0.5467 -0.2343 0.0295 -0.6759 -0.2227
-0.4980 0.3749 -0.6820 -0.0475 0.1547 -0.0733 -0.3388
-0.2424 -0.3885 -0.0945 -0.6518 0.4371 0.0039 0.4068
-0.2938 -0.5175 -0.1111 -0.1982 -0.7383 -0.0344 -0.2190
-0.2644 -0.5321 0.1912 0.4180 0.4667 0.1088 -0.4540
-0.5376 0.0046 0.0290 0.5151 -0.1157 -0.1394 0.6418
d =
12.6750 0 0 0 0
0 10.1164 0 0 0
0 0 2.4328 0 0
0 0 0 1.4264 0
0 0 0 0 1.0250
0 0 0 0 0
0 0 0 0 0
v =
-0.3943 0.1850 -0.5604 0.3711 -0.5988
-0.4844 0.2896 -0.4361 -0.2823 0.6416
-0.5781 0.4011 0.6907 -0.0352 -0.1635
-0.3816 -0.5814 0.1295 0.6218 0.3360
-0.3606 -0.6188 -0.0456 -0.6282 -0.3004
이제 내재된 2개의 성질을 이용하여 원래 행렬을 재생해 보면
>> vt=v';
>> u(:,1:2)*d(1:2,1:2)*vt(1:2,:)
ans =
2.6239 3.4256 4.2679 0.0722 -0.1568
1.8875 2.4663 3.0746 0.0254 -0.1403
3.1904 4.1556 5.1695 0.2037 -0.0706
0.4845 0.3498 0.1994 3.4574 3.5400
0.5003 0.2878 0.0530 4.4650 4.5828
0.3258 0.0642 -0.2220 4.4083 4.5394
2.6959 3.3143 3.9577 2.5738 2.4292
마지막 사용자의 2, 4번째 상품에 대한 평가치는 3.3143>2.5738이므로 2번째 상품을 추천한다.
References
[1] 한국정보처리학회, Tutorial(빅데이터 분석 및 소셜 컴퓨팅), 2014.
웹 Market에서 상품을 팔면서 구매자의 만족도를 조사하였다.
6명의 구매자에 대해 5개의 상품을 0~5점으로 나누어 만족도가 높을수록 5점에 가까운 점수를
주게 하였더니 아래와 같은 행렬이 얻어졌다.
>>A=[2 3 5 0 0; 1 2 4 0 0; 4 5 4 0 0; 0 1 0 3 4; 1 0 0 4 5; 0 0 0 5 4];
>> A
A =
2 3 5 0 0
1 2 4 0 0
4 5 4 0 0
0 1 0 3 4
1 0 0 4 5
0 0 0 5 4
행렬에서 행(row)은 구매자이고 열(column)은 개별 상품에 해당한다.
행렬을 보고 대략 추정해보면 1~3번 상품에 대해 호의적인 사용자들과
4~6번의 상품에 호의적인 사용자들의 두 그룹으로 나누어진다는 것을 알 수 있다.
A행렬을 특이값 분해(SVD, singular value decomposition)해보면
>>[u,d,v]=svd(A)
u =
-0.4719 0.3337 -0.4308 0.0716 0.1067 -0.6810
-0.3382 0.2434 -0.5548 0.1188 -0.0594 0.7078
-0.5811 0.3908 0.6720 -0.1899 -0.0353 0.1436
-0.3004 -0.3804 0.0835 0.4957 -0.7101 -0.0901
-0.3610 -0.5078 0.1044 0.3629 0.6803 0.0801
-0.3234 -0.5235 -0.1927 -0.7532 -0.1299 -0.0100
d =
10.6983 0 0 0 0
0 10.1159 0 0 0
0 0 2.4316 0 0
0 0 0 1.1504 0
0 0 0 0 0.9895
0 0 0 0 0
v =
-0.3709 0.1944 0.5659 -0.1171 0.7005
-0.4952 0.3026 0.4284 -0.0013 -0.6925
-0.5643 0.4157 -0.6929 0.0641 0.1564
-0.3704 -0.5724 -0.1216 -0.7190 -0.0592
-0.4020 -0.6084 0.0349 0.6821 0.0419
세개의 행렬 u, d, v가 얻어진다.
d행렬 내의 특이값을 보면 2개의 성분이 크고 나머지는 작다.
즉, A행렬의 내재된 성분이 2개가 중요하다는 의미이다.
2개의 성분과 그에 해당하는 u, v행렬의 값만을 이용하여 A행렬을 다시 재생해 보면
>> vt = v';
>> u(:,1:2)*d(1:2,1:2)*vt(1:2,:)
ans =
2.5285 3.5220 4.2523 -0.0619 -0.0241
1.8206 2.5374 3.0657 -0.0693 -0.0437
3.0741 4.2755 5.1518 0.0396 0.0935
0.4441 0.4272 0.2140 3.3931 3.6334
0.4338 0.3579 0.0438 4.3709 4.6782
0.2538 0.1107 -0.2491 4.3124 4.6127
이고 A행렬과 비교해 보면 값이 비슷하다(잘 재생된다).
내재된 성분의 의미를 파악해 보자.
>> u(:,1:2)*d(1:2,1:2)
ans =
-5.0490 3.3752
-3.6186 2.4625
-6.2169 3.9535
-3.2142 -3.8482
-3.8621 -5.1373
-3.4597 -5.2956
행렬의 행은 사용자를 표현하고, 열은 두개의 내재된 성질에 대한 것이다. 즉, 사용자는 2개의 그룹으로 나누어지며
1~3번 사용자는 첫번째 성질에 속하고, 4~6번 사용자는 두번째 성질에 속하는 정도가 크다 (행렬 요소값의 절대치 크기만 보자).
>> vt(1:2,:)
ans =
-0.3709 -0.4952 -0.5643 -0.3704 -0.4020
0.1944 0.3026 0.4157 -0.5724 -0.6084
5개의 상품(각 열)에 대해 첫번째 성질(사용자 그룹)은 1~3열의 상품에 대한 선호도가 높고, 2번째 성질은 4~5열의 상품에 대한 선호도가 높다.
이상과 같이 행렬을 분해해 주는 방법인 SVD를 이용하면 데이터에 내재되어 있는 의미 파악이 가능하다. 이를 이용하면 상품 추천시스템을 만들 수 있다.
이제 어떤 사람의 구매 만족도를 조사하였더니 아래와 같은 데이터가 주어졌다.
B=[3 ? 4 ? 2]
이 사용자는 상품 2, 4를 아직 구매하지 않았다.
이 사람에게 상품 2와 4 중에서 어떤 것을 추천할 것인지 계산해 보자.
먼저 평가가 있는 세개의 상품에 대해 평균을 구해 '?'위치에 대치하자.
(3+4+2)/3=3이므로 3을 대입한다.
>>B=[3 3 4 3 2];
이 사용자를 A행렬의 마지막 행에 추가하고 SVD를 다시 수행한다.
>> C=[A; B]
C =
2 3 5 0 0
1 2 4 0 0
4 5 4 0 0
0 1 0 3 4
1 0 0 4 5
0 0 0 5 4
3 3 4 3 2
>> [u,d,v]=svd(C)
u =
-0.4049 0.3207 0.4210 -0.1967 -0.0883 0.7109 -0.0642
-0.2900 0.2341 0.5467 -0.2343 0.0295 -0.6759 -0.2227
-0.4980 0.3749 -0.6820 -0.0475 0.1547 -0.0733 -0.3388
-0.2424 -0.3885 -0.0945 -0.6518 0.4371 0.0039 0.4068
-0.2938 -0.5175 -0.1111 -0.1982 -0.7383 -0.0344 -0.2190
-0.2644 -0.5321 0.1912 0.4180 0.4667 0.1088 -0.4540
-0.5376 0.0046 0.0290 0.5151 -0.1157 -0.1394 0.6418
d =
12.6750 0 0 0 0
0 10.1164 0 0 0
0 0 2.4328 0 0
0 0 0 1.4264 0
0 0 0 0 1.0250
0 0 0 0 0
0 0 0 0 0
v =
-0.3943 0.1850 -0.5604 0.3711 -0.5988
-0.4844 0.2896 -0.4361 -0.2823 0.6416
-0.5781 0.4011 0.6907 -0.0352 -0.1635
-0.3816 -0.5814 0.1295 0.6218 0.3360
-0.3606 -0.6188 -0.0456 -0.6282 -0.3004
이제 내재된 2개의 성질을 이용하여 원래 행렬을 재생해 보면
>> vt=v';
>> u(:,1:2)*d(1:2,1:2)*vt(1:2,:)
ans =
2.6239 3.4256 4.2679 0.0722 -0.1568
1.8875 2.4663 3.0746 0.0254 -0.1403
3.1904 4.1556 5.1695 0.2037 -0.0706
0.4845 0.3498 0.1994 3.4574 3.5400
0.5003 0.2878 0.0530 4.4650 4.5828
0.3258 0.0642 -0.2220 4.4083 4.5394
2.6959 3.3143 3.9577 2.5738 2.4292
마지막 사용자의 2, 4번째 상품에 대한 평가치는 3.3143>2.5738이므로 2번째 상품을 추천한다.
References
[1] 한국정보처리학회, Tutorial(빅데이터 분석 및 소셜 컴퓨팅), 2014.
2014년 4월 17일 목요일
FastSLAM
EKF SLAM의 문제점
- 2차원 평면상에서 $K$개의 landmark 존재. LM 파라미터: $(x_i, y_i)$
- robot pose: $(x, y, \phi)$
- 합하면 $2K+3$개의 인자
- Kalman filter를 통해 이것들을 추정하면 mean값을 $2K+3$개를 유지
Covariance matrix는 $(2K+3)^2$크기가 요구
- LM의 수가 늘어 감에 따라 유지해야 하는 파라메터의 수가 급격히 증가(계산량 증가)
- LM의 수가 늘어 감에 따라 유지해야 하는 파라메터의 수가 급격히 증가(계산량 증가)
FastSLAM에서의 개선
- Landmark는 로봇의 pose가 주어진다면 상호 독립이라 가정
- 각 landmark에 대해 $2\times2$ covariance matrix
전체 인자의 수: $K(2+2\times2)+3$
Robot poses: $s^t=s_1, s_2, ...,s_t$
Robot actions: $u^t=u_1,u_2,...,u_t$
Observations: $z^t=z_1,z_2,...,z_t$
Landmarks: $\boldsymbol{\theta}=\theta_1,...,\theta_k$
Correspondence: $n^t=n_1,n_2,...,n_t$
- $n_t=k$는 $z_t$가 $\theta_k$의 관찰 값임을 의미
- landmark는 한번에 하나씩 관찰된다고 가정
그림에서 shade영역은 $t_1\sim$현재까지의 로봇의 경로이다.
만일 로봇의 실제 경로를 안다면(즉 shade영역) LM $\theta_1$과 $\theta_2$는 서로 독립이다.
SLAM 문제
- action model: $p(s_t|u^t,s^{t-1})$
- sensor model: $p(z_t|s_t,\boldsymbol{\theta},n_t)$
SLAM 문제는 $z^t, u^t, n^t$가 주어질 때 $\boldsymbol{\theta},s^t$를 추정하는 문제이다. Bayes theory를 이용하면
$p(s^t,\boldsymbol{\theta}|z^t,u^t,n^t)=
{{p(\boldsymbol{\theta},s^t,z^t,u^t,n^t)} \over {p(z^t,u^t,n^t)}}={{p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)p(s^t,z^t,u^t,n^t)} \over {p(z^t,u^t,n^t)}}$
$=p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)p(s^t|z^t,u^t,n^t)$
landmark의 독립가정$^{주1}$에 따라
$p(s^t,\boldsymbol{\theta}|z^t,u^t,n^t)
=p(s^t|z^t,u^t,n^t)\prod_k^{}p(\theta_k|s^t,z^t,u^t,n^t)$
- trajectory 추정 $p(s^t|z^t,u^t,n^t)$
- robot의 자세 추정은 particle filter를 이용하고, 각 particle에 대한 landmark위치와 분산의 갱신의 EKF를 사용
- particle당 $K$개의 Kalman filter가 있으므로 particle의 수가 $M$개라면 갱신과정의 시간 복잡도는 $O(MK)$이다.
(주1) 독립가정에 따라
$p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)=...$
References
[1] M. Montemerlo, FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem With Unknown Data Association, CMU-CS-03, Ph.D. thesis, 2003.
[2] Benjamin Kuipers, FastSlam, lecture notes, CS 344R/393R: Robotics.
Robot actions: $u^t=u_1,u_2,...,u_t$
Observations: $z^t=z_1,z_2,...,z_t$
Landmarks: $\boldsymbol{\theta}=\theta_1,...,\theta_k$
Correspondence: $n^t=n_1,n_2,...,n_t$
- $n_t=k$는 $z_t$가 $\theta_k$의 관찰 값임을 의미
- landmark는 한번에 하나씩 관찰된다고 가정
그림에서 shade영역은 $t_1\sim$현재까지의 로봇의 경로이다.
만일 로봇의 실제 경로를 안다면(즉 shade영역) LM $\theta_1$과 $\theta_2$는 서로 독립이다.
SLAM 문제
- action model: $p(s_t|u^t,s^{t-1})$
- sensor model: $p(z_t|s_t,\boldsymbol{\theta},n_t)$
SLAM 문제는 $z^t, u^t, n^t$가 주어질 때 $\boldsymbol{\theta},s^t$를 추정하는 문제이다. Bayes theory를 이용하면
$p(s^t,\boldsymbol{\theta}|z^t,u^t,n^t)=
{{p(\boldsymbol{\theta},s^t,z^t,u^t,n^t)} \over {p(z^t,u^t,n^t)}}={{p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)p(s^t,z^t,u^t,n^t)} \over {p(z^t,u^t,n^t)}}$
$=p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)p(s^t|z^t,u^t,n^t)$
landmark의 독립가정$^{주1}$에 따라
$p(s^t,\boldsymbol{\theta}|z^t,u^t,n^t)
=p(s^t|z^t,u^t,n^t)\prod_k^{}p(\theta_k|s^t,z^t,u^t,n^t)$
- trajectory 추정 $p(s^t|z^t,u^t,n^t)$
- robot의 자세 추정은 particle filter를 이용하고, 각 particle에 대한 landmark위치와 분산의 갱신의 EKF를 사용
- particle당 $K$개의 Kalman filter가 있으므로 particle의 수가 $M$개라면 갱신과정의 시간 복잡도는 $O(MK)$이다.
(주1) 독립가정에 따라
$p(\boldsymbol{\theta}|s^t,z^t,u^t,n^t)=...$
References
[1] M. Montemerlo, FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem With Unknown Data Association, CMU-CS-03, Ph.D. thesis, 2003.
[2] Benjamin Kuipers, FastSlam, lecture notes, CS 344R/393R: Robotics.
2014년 3월 30일 일요일
Design Pattern
작성 중 ...
Adaptor 패턴
두 클래스의 인터페이스가 서로 맞지 않을 때 클래스들을 연결하는 역할을 한다.
어떤 클래스(client)가 다른 클래스의 객체를 받아 이 객체의 함수를 호출해서 사용한다고 하자. 그런데 이 client는 이미 완성된 클래스라 수정이 불가하다.
그런데, client가 이미 만들어져 있는 또 다른 클래스(adaptee)의 함수를 사용할 필요가 생겼다. adaptee 클래스도 이미 완성되어 수정을 할 수 없다.
이때 사용하는 것이 adaptor이다. client가 넘겨받는 객체 클래스(adaptor)에 adaptee 객체를 선언하고 client가 호출하는 adaptor 함수 내에서 adaptee의 함수를 호출하도록 해 준다.
adaptor 클래스는 adaptee클래스를 상속 받아 만들 수도 있다.
결론적으로 adaptee와 client를 수정할 필요 없이 원하는 목적을 달성할 수 있다.
Adaptor 패턴이 잘 설명
a
Adaptor 패턴
두 클래스의 인터페이스가 서로 맞지 않을 때 클래스들을 연결하는 역할을 한다.
어떤 클래스(client)가 다른 클래스의 객체를 받아 이 객체의 함수를 호출해서 사용한다고 하자. 그런데 이 client는 이미 완성된 클래스라 수정이 불가하다.
그런데, client가 이미 만들어져 있는 또 다른 클래스(adaptee)의 함수를 사용할 필요가 생겼다. adaptee 클래스도 이미 완성되어 수정을 할 수 없다.
이때 사용하는 것이 adaptor이다. client가 넘겨받는 객체 클래스(adaptor)에 adaptee 객체를 선언하고 client가 호출하는 adaptor 함수 내에서 adaptee의 함수를 호출하도록 해 준다.
adaptor 클래스는 adaptee클래스를 상속 받아 만들 수도 있다.
결론적으로 adaptee와 client를 수정할 필요 없이 원하는 목적을 달성할 수 있다.
Adaptor 패턴이 잘 설명
a
(예제) testDuck이라는 함수에서 duck객체를 호출한다고 가정하자.
Mediator(중계자) 패턴
a, b, c
중개자, 조정자 패턴이라고도 하는 Mediator 패턴이다.
각 클래스끼리의 상호 참조나, 서로가 서로에게 영향을 미치는 클래스들을 잘 분리하고 중개해주는 역할을 한다.
각 클래스끼리의 영향이 적으면 적을 수록, 나중에 모듈을 떼어내기도 수월하고 디버깅도 유리하다.
Mediator 패턴을 쓰면 좋은 경우를 예로 들면,
GUI 화면을 구성할 때, 특정 체크박스의 값에 따라 각 버튼의 Enabled/Disabled 속성 변경, 텍스트 박스의 값에 따라 각 컴포넌트의 속성이 변경되거나 하는 등 다양한 상태에 따라 각 컴포넌트들이 서로가 서로에게 영향을 미치는 경우를 예로 들 수 있다.
이 때, 각 버튼 클릭 이벤트나, 체크 박스 이벤트, 텍스트 박스 이벤트에서 각 컴포넌트들에게 바로 접근해서 직접 다룰 경우 서로간의 종속성이 엄청 높아지게 된다.
중간에 코드에 문제가 생겨서 수정해야 할 때 고쳐야 할 부분이 분산되어 있어서 복잡해지기도 하며, 특정 컴포넌트를 삭제하거나 변경할 때 코드 내의 여기저기서 컴파일 오류가 발생하는 등 다양한 문제들이 발생하게 된다.
Mediator 패턴은 크게 Mediator 인터페이스와 Colleague 인터페이스로 구성된다.
물론, Mediator과 Colleague는 인터페이스(추상,부모 클래스)이기 때문에 이를 상속받고 구현받는 클래스가 추가로 필요하다.
GUI 예에서 각 텍스트 박스나 버튼, 체크 박스 등은 Colleague 인터페이스를 상속받아서 구현한다.
그리고 각각의 객체들의 값이 변경될 때마다 Mediator의 colleagueChanged() 메소드를 호출해서 변경을 알려준다.
그러면 Mediator에서는 각 Colleague들의 속성을 체크해서 각각의 객체들에게 속성 변경 명령을 내려주게 된다.
Mediator 패턴의 요지는 각각의 클래스 A, B, C 들이 A ↔ B, B ↔ C, C ↔ A 이런 식으로 서로 통신하거나 영향을 미칠 경우
그 관계를 모두 끊고, 중간에 Mediator을 둬서 한 번 거쳐서 처리하도록 하는 것이다.
단계는 하나 더 증가하지만, 각 모듈간의 종속성을 끊고 보다 깔끔하고 유지보수가 쉽게 하자는 것이 그 목적이다.
#include <iostream>
#include <list>
#include <string>
using namespace std;
//------------------------------------------------------------------
// Mediator 인터페이스
class Colleague; // 전방 선언
class Mediator
{
public:
virtual void AppendUser(Colleague* colleague) = 0;
virtual void RemoveUser(Colleague* colleague) = 0;
virtual void sendMessage(const char* message, Colleague* sender) = 0;
};
//------------------------------------------------------------------
// Colleague 인터페이스
class Colleague
{
public:
Colleague(Mediator* m, const char* name) : pMediator(m), mName(name) {}
public:
virtual void SendMessages(const char* str) = 0;
virtual void ReceiveMessages(const char* str) = 0;
protected:
Mediator* pMediator;
string mName;
};
//------------------------------------------------------------------
// User 상속 클래스
class User : public Colleague
{
public:
User(Mediator* m, const char* name) : Colleague(m, name) {}
public:
// 객체들의 값이 변경될 때마다 Mediator의 colleagueChanged()
// 메소드를 호출해서 변경을 알려줌
void SendMessages(const char* str) override
{
cout << mName << " send : " << str << endl;
pMediator->sendMessage(str, this);
}
void ReceiveMessages(const char* str) override
{
cout << mName << " recv : " << str << endl;
}
};
//------------------------------------------------------------------
// ChatMediator 상속 클래스
class ChatMediator : public Mediator
{
public:
void AppendUser(Colleague* colleague) override
{
mList.push_back(colleague);
}
void RemoveUser(Colleague* colleague) override
{
mList.remove(colleague);
}
// Mediator에서는 각 Colleague들의 속성을 체크해서 각각의 객체들에게
// 속성 변경 명령을 내려주게 됨
void sendMessage(const char* message, Colleague* sender)
{
for (Colleague* object : mList)
{
if (object != sender)
object->ReceiveMessages(message);
}
}
private:
list<Colleague*> mList;
};
//------------------------------------------------------------------
// Main
int main()
{
ChatMediator mChatMediator;
User mUser1(&mChatMediator, "홍길동");
User mUser2(&mChatMediator, "나이스");
User mUser3(&mChatMediator, "디자인");
mChatMediator.AppendUser(&mUser1);
mChatMediator.AppendUser(&mUser2);
mChatMediator.AppendUser(&mUser3);
mUser1.SendMessages("안녕하세요. 홍길동입니다!");
return 0;
}
실행 결과:
홍길동 send : 안녕하세요. 홍길동입니다!
나이스 recv : 안녕하세요. 홍길동입니다!
디자인 recv : 안녕하세요. 홍길동입니다!
Template(템플릿) 패턴
부모 클래스에서 알고리즘의 골격을 정의한다. 알고리즘의 여러 단계 중 일부는 서브(자식)클래스에서 구현한다.
두 쓰레드는 동시에 실행되어야 하며 서로 공통 부분이 많다.
Command 패턴
작업을 요청한 쪽과 처리하는 쪽을 분리한다.
연속된 명령의 삽입, 삭제, undo, do 등을 처리할수 있다.
컴포지트 패턴이란 객체들의 관계를 트리 구조로 구성하여 부분-전체 계층을 표현하는 패턴으로, 사용자가 단일 객체와 복합 객체 모두 동일하게 다루도록 한다.
Leaf이나 Composite모두 Component에서 상속 받아 만든 동일 구상 클래스이다.
container1은 2개의 Leaf노드를 가진다.
container2는 3개의 Leaf노드를 가진다.
container1은 container2도 가지므로 container1 밑에 2개의 Leaf와 3개의 Leaf를 가진 container2를 가진 Tree구조가 형성된다.
Composite클래스의 list명령으로 Tree를 모두 출력해 볼 수 있다.
팩토리메쏘드 패턴
객체 생성은 추상클래스에서 한다.
어떤 객체를 생성할지는 구상클래스에서 결정한다.
즉, 인터페이스에 객체 생성을 요청하지만, 어떤 클래스의 인스턴스를 만들지는 서브클래스에서 결정한다.
//------------------------------------------------------------------
// Product 인터페이스 클래스
class Product
{
public:
virtual void print() = 0;
};
//------------------------------------------------------------------
// Product 상속 클래스
class ConcreteProduct : public Product
{
public:
void print() override { cout << "ConcreteProduct" << endl; }
};
//------------------------------------------------------------------
// Creator 클래스 (구현 인터페이스 클래스)
class Creator
{
public:
Product* AnOperation() { return FactoryMethod(); }
protected:
virtual Product* FactoryMethod() = 0;
};
//------------------------------------------------------------------
// Creator 상속 클래스 (실제 객체 생성 전담)
class ConcreteCreator : public Creator
{
private:
Product* FactoryMethod() { return new ConcreteProduct; }
};
//------------------------------------------------------------------
// Main
void main()
{
ConcreteCreator pCreator;
Product* pProduct = pCreator.AnOperation();
pProduct->print();
delete pProduct;
}
References
Factory Method Pattern: 1, 2
이때 어느 부분도 수정없이 testDuck에서 Turkey라는 객체도 호출(사용)하고 싶다.
(Sol) duck을 상속받은 TurkeyAdaptor를 만든다.
TurkeyAdaptor 멤버로 타겟인 Turkey 객체를 삽입한다.
TurkeyAdaptor 내의 duck가상함수를 구현할때 Turkey의 함수를 호출하게 한다.
(사용) testDuck 함수의 인자에 duck 대신 TurkeyAdaptor객체를 넘겨준다.
Mediator(중계자) 패턴
a, b, c
중개자, 조정자 패턴이라고도 하는 Mediator 패턴이다.
각 클래스끼리의 상호 참조나, 서로가 서로에게 영향을 미치는 클래스들을 잘 분리하고 중개해주는 역할을 한다.
각 클래스끼리의 영향이 적으면 적을 수록, 나중에 모듈을 떼어내기도 수월하고 디버깅도 유리하다.
Mediator 패턴을 쓰면 좋은 경우를 예로 들면,
GUI 화면을 구성할 때, 특정 체크박스의 값에 따라 각 버튼의 Enabled/Disabled 속성 변경, 텍스트 박스의 값에 따라 각 컴포넌트의 속성이 변경되거나 하는 등 다양한 상태에 따라 각 컴포넌트들이 서로가 서로에게 영향을 미치는 경우를 예로 들 수 있다.
이 때, 각 버튼 클릭 이벤트나, 체크 박스 이벤트, 텍스트 박스 이벤트에서 각 컴포넌트들에게 바로 접근해서 직접 다룰 경우 서로간의 종속성이 엄청 높아지게 된다.
중간에 코드에 문제가 생겨서 수정해야 할 때 고쳐야 할 부분이 분산되어 있어서 복잡해지기도 하며, 특정 컴포넌트를 삭제하거나 변경할 때 코드 내의 여기저기서 컴파일 오류가 발생하는 등 다양한 문제들이 발생하게 된다.
Mediator 패턴은 크게 Mediator 인터페이스와 Colleague 인터페이스로 구성된다.
물론, Mediator과 Colleague는 인터페이스(추상,부모 클래스)이기 때문에 이를 상속받고 구현받는 클래스가 추가로 필요하다.
GUI 예에서 각 텍스트 박스나 버튼, 체크 박스 등은 Colleague 인터페이스를 상속받아서 구현한다.
그리고 각각의 객체들의 값이 변경될 때마다 Mediator의 colleagueChanged() 메소드를 호출해서 변경을 알려준다.
그러면 Mediator에서는 각 Colleague들의 속성을 체크해서 각각의 객체들에게 속성 변경 명령을 내려주게 된다.
Mediator 패턴의 요지는 각각의 클래스 A, B, C 들이 A ↔ B, B ↔ C, C ↔ A 이런 식으로 서로 통신하거나 영향을 미칠 경우
그 관계를 모두 끊고, 중간에 Mediator을 둬서 한 번 거쳐서 처리하도록 하는 것이다.
단계는 하나 더 증가하지만, 각 모듈간의 종속성을 끊고 보다 깔끔하고 유지보수가 쉽게 하자는 것이 그 목적이다.
#include <iostream>
#include <list>
#include <string>
using namespace std;
//------------------------------------------------------------------
// Mediator 인터페이스
class Colleague; // 전방 선언
class Mediator
{
public:
virtual void AppendUser(Colleague* colleague) = 0;
virtual void RemoveUser(Colleague* colleague) = 0;
virtual void sendMessage(const char* message, Colleague* sender) = 0;
};
//------------------------------------------------------------------
// Colleague 인터페이스
class Colleague
{
public:
Colleague(Mediator* m, const char* name) : pMediator(m), mName(name) {}
public:
virtual void SendMessages(const char* str) = 0;
virtual void ReceiveMessages(const char* str) = 0;
protected:
Mediator* pMediator;
string mName;
};
//------------------------------------------------------------------
// User 상속 클래스
class User : public Colleague
{
public:
User(Mediator* m, const char* name) : Colleague(m, name) {}
public:
// 객체들의 값이 변경될 때마다 Mediator의 colleagueChanged()
// 메소드를 호출해서 변경을 알려줌
void SendMessages(const char* str) override
{
cout << mName << " send : " << str << endl;
pMediator->sendMessage(str, this);
}
void ReceiveMessages(const char* str) override
{
cout << mName << " recv : " << str << endl;
}
};
//------------------------------------------------------------------
// ChatMediator 상속 클래스
class ChatMediator : public Mediator
{
public:
void AppendUser(Colleague* colleague) override
{
mList.push_back(colleague);
}
void RemoveUser(Colleague* colleague) override
{
mList.remove(colleague);
}
// Mediator에서는 각 Colleague들의 속성을 체크해서 각각의 객체들에게
// 속성 변경 명령을 내려주게 됨
void sendMessage(const char* message, Colleague* sender)
{
for (Colleague* object : mList)
{
if (object != sender)
object->ReceiveMessages(message);
}
}
private:
list<Colleague*> mList;
};
//------------------------------------------------------------------
// Main
int main()
{
ChatMediator mChatMediator;
User mUser1(&mChatMediator, "홍길동");
User mUser2(&mChatMediator, "나이스");
User mUser3(&mChatMediator, "디자인");
mChatMediator.AppendUser(&mUser1);
mChatMediator.AppendUser(&mUser2);
mChatMediator.AppendUser(&mUser3);
mUser1.SendMessages("안녕하세요. 홍길동입니다!");
return 0;
}
실행 결과:
홍길동 send : 안녕하세요. 홍길동입니다!
나이스 recv : 안녕하세요. 홍길동입니다!
디자인 recv : 안녕하세요. 홍길동입니다!
Template(템플릿) 패턴
부모 클래스에서 알고리즘의 골격을 정의한다. 알고리즘의 여러 단계 중 일부는 서브(자식)클래스에서 구현한다.
알고리즘의 구조는 그대로 유지하면서 서브클래스에서 특정 단계를 재정의할 수 있다.
이 패턴은 알고리즘의 틀을 만들기 위한 것이다. 상위 클래스에는 일련의 단계들로 알고리즘을 정의한 메소드가 있다. 여러 단계 가운데 하나 이상이 추상 메소드로 정의되며, 그 추상 메소드는 하위클래스에서 구현된다.
(예제) 머신비전의 일반적인 과정을 보면 두개의 쓰레드가 필요하다.
이 패턴은 알고리즘의 틀을 만들기 위한 것이다. 상위 클래스에는 일련의 단계들로 알고리즘을 정의한 메소드가 있다. 여러 단계 가운데 하나 이상이 추상 메소드로 정의되며, 그 추상 메소드는 하위클래스에서 구현된다.
(예제) 머신비전의 일반적인 과정을 보면 두개의 쓰레드가 필요하다.
하나는 처리할 데이터인 영상정보를 카메라에서 캡춰하는 것이다.
다른 하나는 작업 목적에 따라 영상을 처리하는 알고리즘 부분이다.
두 쓰레드는 동시에 실행되어야 하며 서로 공통 부분이 많다.
상위 클래스는 쓰레드의 동작에 필요한 공통적인 실행절차를 정의하고 두 쓰레드의 상세한 부분은 하위 클래스에서 재 정의 한다.
Command 패턴
작업을 요청한 쪽과 처리하는 쪽을 분리한다.
연속된 명령의 삽입, 삭제, undo, do 등을 처리할수 있다.
단, 호출자에서 하나의 객체로 처리해야 하므로 모든 명령은 하나의 추상(부모)클래스를 이용한다.
작업 처리 쪽:
작업 처리 쪽:
작업 요청 쪽:
(몇 유사 패턴과의 비교)
스테이트(State) 패턴은 상태 그 자체를 클래스화해서 사용하는 것이고,
스트래터지(Strategy) 패턴은 알고리즘 자체를 클래스화해서 사용하는 것이고,
컴포지트(Composite) 패턴은 각 객체들을 동일시해서 사용하는 것이다.
커맨드 패턴은 명령 그 자체를 클래스화해서 사용하는 것이다. 디자인 패턴들은 대부분 그 개념면에서 비슷하다.
커맨드 패턴에서 명령들을 전부 동일시해서 사용하기 위해서는 역시 하나의 인터페이스를 이용해서 구현을 해야한다.
Composite 패턴
스트래터지(Strategy) 패턴은 알고리즘 자체를 클래스화해서 사용하는 것이고,
컴포지트(Composite) 패턴은 각 객체들을 동일시해서 사용하는 것이다.
커맨드 패턴은 명령 그 자체를 클래스화해서 사용하는 것이다. 디자인 패턴들은 대부분 그 개념면에서 비슷하다.
커맨드 패턴에서 명령들을 전부 동일시해서 사용하기 위해서는 역시 하나의 인터페이스를 이용해서 구현을 해야한다.
Composite 패턴
추상클래스를 하나 만들고 상속받은 다양한 자식클래스를 만들어 다양한 자식클래스들을 동일 클래스 다루듯 사용하는 패턴이다.
컴포지트 패턴이란 객체들의 관계를 트리 구조로 구성하여 부분-전체 계층을 표현하는 패턴으로, 사용자가 단일 객체와 복합 객체 모두 동일하게 다루도록 한다.
#include <iostream> #include <vector> #include <string> using std::cout; using std::vector; using std::string; class Component { public: virtual void list() const = 0; virtual ~Component(){}; }; class Leaf : public Component { public: explicit Leaf(int val) : value_(val) { } void list() const { cout << " " << value_ << "\n"; } private: int value_; }; class Composite : public Component { public: explicit Composite(string id) : id_(id) { } void add(Component *obj) { table_.push_back(obj); } void list() const { cout << id_ << ":" << "\n"; for (vector<Component*>::const_iterator it = table_.begin(); it != table_.end(); ++it) { (*it)->list(); } } private: vector <Component*> table_; string id_; }; int main() { Leaf num0(0); Leaf num1(1); Leaf num2(2); Leaf num3(3); Leaf num4(4); Composite container1("Container 1"); Composite container2("Container 2"); container1.add(&num0); container1.add(&num1); container2.add(&num2); container2.add(&num3); container2.add(&num4); container1.add(&container2); container1.list(); return 0; }
Leaf이나 Composite모두 Component에서 상속 받아 만든 동일 구상 클래스이다.
container1은 2개의 Leaf노드를 가진다.
container2는 3개의 Leaf노드를 가진다.
container1은 container2도 가지므로 container1 밑에 2개의 Leaf와 3개의 Leaf를 가진 container2를 가진 Tree구조가 형성된다.
Composite클래스의 list명령으로 Tree를 모두 출력해 볼 수 있다.
팩토리메쏘드 패턴
객체 생성은 추상클래스에서 한다.
어떤 객체를 생성할지는 구상클래스에서 결정한다.
즉, 인터페이스에 객체 생성을 요청하지만, 어떤 클래스의 인스턴스를 만들지는 서브클래스에서 결정한다.
//------------------------------------------------------------------
// Product 인터페이스 클래스
class Product
{
public:
virtual void print() = 0;
};
//------------------------------------------------------------------
// Product 상속 클래스
class ConcreteProduct : public Product
{
public:
void print() override { cout << "ConcreteProduct" << endl; }
};
//------------------------------------------------------------------
// Creator 클래스 (구현 인터페이스 클래스)
class Creator
{
public:
Product* AnOperation() { return FactoryMethod(); }
protected:
virtual Product* FactoryMethod() = 0;
};
//------------------------------------------------------------------
// Creator 상속 클래스 (실제 객체 생성 전담)
class ConcreteCreator : public Creator
{
private:
Product* FactoryMethod() { return new ConcreteProduct; }
};
//------------------------------------------------------------------
// Main
void main()
{
ConcreteCreator pCreator;
Product* pProduct = pCreator.AnOperation();
pProduct->print();
delete pProduct;
}
References
Factory Method Pattern: 1, 2
2D Disjunctive Normal Form (DNF)
기계학습 알고리즘을 물체 추적에 적용해 본다.
물체 추적 문제는 보통 비디오의 첫번째 프레임에서 추적할 대상 물체를 사용자가 사각형 box(ROI, 즉 Region Of Interest라고도 부른다)를 그려 지정해 준다. 이렇게 물체 영역을 지정하면, box 내부의 영역은 학습을 위한 positive 영역, 물체 주위의 배경 영역은 negative 영역으로 간주된다. 이 정보를 이용하여 물체 추적을 위한 분류기를 학습할 수 있다.
먼저, 물체를 포함하는 영역과 배경(물체 영역을 중시으로 물체 영역의 2배 정도) 영역에서 랜덤하게 복수 개의 positive patch$^{주1}$와 negative patch를 추출한다. 이러한 patch들은 분류기(classifier)를 학습할 수 있는 샘플(training samples)이 된다.
1st frame
추적할 대상을 지정해 주는 프레임이다.
사용자의 ROI 지정 $\rightarrow$ ROI 내의 랜덤한 위치에서 정해진 갯수의 patch를 추출한다. 각각의 patch들이 training sample이 된다.
학습
분류기의 학습과 갱신은 adaptive boosting알고리즘을 이용한다.
(임의로 선택된) 두 특징 함수 $h_i$와 $h_j$(특징 함수는 Harr-like feature, LBP, HOG 등이 될 수 있다)에 patch를 입력하면 특징 값 $v_i, v_j$가 계산된다. 모든 샘플에 대해 얻어진 $v$의 가능한 값의 범위를 여러 bin(일정한 간격을 가진 여러 값의 범위)으로 나눈다. 이때, 어떤 하나의 샘플이 주는 $h_i$와 $h_j$ 값은 2차원 공간 상의 하나의 bin(특징 값이 2개이므로 2차원이다)을 가리킨다. 또 각각의 sample은 부류정보(positive or negative)를 가지고 있으므로 이 부류 정보에 따라 bin에 Positive나 Negative로 보팅한다$^{주2}$.
모든 sample에 대한 voting후 각 bin에서 positive로 보팅한 수가 negative로 보팅한 수보다 $r$만큼 더 많다면 이 bin 영역의 위치는 저장된다. $r$은 미리 지정된 상수이다.
특징은 일반적으로 여러 개이고 특징 들의 쌍(pair)은 아주 많이 구성할 수 있다.
가능한 여러 pair중에서 정, 부의 모든 샘플을 고려했을 때 가장 작은 오류를 주는 특징 pair를 선정한다. 이것이 하나의 weak DNF classifier이다.
이러한 과정을 $M$번 반복한다. 모두 $M$개의 weak 2d DNF classifier를 선정하면 학습이 완료되고, 선정된 weak classifier를 선형 결합하여 strong classifier를 만든다.
2nd frame
물체의 2배 확대 영역 내 모든 patch에 대해 strong classifier를 적용하고 confidence map를 작성한다. confidence map의 measure는 strong classifier의 값으로 한다.
계산 방법은 각 patch를 2d DNF weak classifier에 입력하고 계산된 값이 학습 시에 저장된 bin에 포함된다면 이 patch는 positive가 된다.
confidence값을 integral image로 합하고 최대의 confidence값을 가진 영역이 추적 위치가 된다.
아래는 c.m(confidence measure)값을 평가하여 현재 프레임에서 물체가 발견되었는지(FOUND) 또는 잃어버렸는지(LOST)에 대한 모드 평가를 보여준다.
c.m < $th_1$ $\rightarrow$ LOST $\rightarrow$ initial state (전 영역 검색)
c.m > $th_2$ & LOST state $\rightarrow$ FOUND state로 초기화
c.m > $th_2$ & FOUND state $\rightarrow$ Update classifier
실제 구현 시의 strong classifier는 2D DNF만 사용하는 것이 아니라 1차원 weak classifier와 2d DNF classifier의 조합으로 구성된다.
(주1) patch는 8x8 pixels과 같은 특징을 계산할 수 있는 작은 크기의 window이다
(주2) Harr-like 특징을 예를 들어 생각해보면, patch 내 어떤 위치에, 어떤 크기로 두 특징 값 $h_i$와 $h_j$가 정의된다고 가정하자. 하나의 샘플이 선정되고 두 특징에 적용되면 2개의 값이 얻어지고 이것은 두 특징이 정의하는 2차원 평면 상의 좌표 값을 가리키게 된다. 이 좌표 평면은 균등한 간격으로 가로 세로로 나누어진 많은 작은 영역(bin)들이 정의되어 있다면 이 값은 이 영역들 중의 하나로 떨어지게 된다. voting이란 두 특징 값이 가리키는 영역의 counter(초기에는 0) 값을 하나 증가시키는 것이 된다. counter는 샘플의 부류에 따라 positive, negative의 두 개가 존재한다.
참고 논문
[1] Disjunctive Normal Form of Weak Classifiers for Online Learning based Object Tracking, ZhuTeng et. al., VISAPP'2013.
물체 추적 문제는 보통 비디오의 첫번째 프레임에서 추적할 대상 물체를 사용자가 사각형 box(ROI, 즉 Region Of Interest라고도 부른다)를 그려 지정해 준다. 이렇게 물체 영역을 지정하면, box 내부의 영역은 학습을 위한 positive 영역, 물체 주위의 배경 영역은 negative 영역으로 간주된다. 이 정보를 이용하여 물체 추적을 위한 분류기를 학습할 수 있다.
먼저, 물체를 포함하는 영역과 배경(물체 영역을 중시으로 물체 영역의 2배 정도) 영역에서 랜덤하게 복수 개의 positive patch$^{주1}$와 negative patch를 추출한다. 이러한 patch들은 분류기(classifier)를 학습할 수 있는 샘플(training samples)이 된다.
1st frame
추적할 대상을 지정해 주는 프레임이다.
사용자의 ROI 지정 $\rightarrow$ ROI 내의 랜덤한 위치에서 정해진 갯수의 patch를 추출한다. 각각의 patch들이 training sample이 된다.
학습
분류기의 학습과 갱신은 adaptive boosting알고리즘을 이용한다.
(임의로 선택된) 두 특징 함수 $h_i$와 $h_j$(특징 함수는 Harr-like feature, LBP, HOG 등이 될 수 있다)에 patch를 입력하면 특징 값 $v_i, v_j$가 계산된다. 모든 샘플에 대해 얻어진 $v$의 가능한 값의 범위를 여러 bin(일정한 간격을 가진 여러 값의 범위)으로 나눈다. 이때, 어떤 하나의 샘플이 주는 $h_i$와 $h_j$ 값은 2차원 공간 상의 하나의 bin(특징 값이 2개이므로 2차원이다)을 가리킨다. 또 각각의 sample은 부류정보(positive or negative)를 가지고 있으므로 이 부류 정보에 따라 bin에 Positive나 Negative로 보팅한다$^{주2}$.
모든 sample에 대한 voting후 각 bin에서 positive로 보팅한 수가 negative로 보팅한 수보다 $r$만큼 더 많다면 이 bin 영역의 위치는 저장된다. $r$은 미리 지정된 상수이다.
특징은 일반적으로 여러 개이고 특징 들의 쌍(pair)은 아주 많이 구성할 수 있다.
가능한 여러 pair중에서 정, 부의 모든 샘플을 고려했을 때 가장 작은 오류를 주는 특징 pair를 선정한다. 이것이 하나의 weak DNF classifier이다.
이러한 과정을 $M$번 반복한다. 모두 $M$개의 weak 2d DNF classifier를 선정하면 학습이 완료되고, 선정된 weak classifier를 선형 결합하여 strong classifier를 만든다.
2nd frame
물체의 2배 확대 영역 내 모든 patch에 대해 strong classifier를 적용하고 confidence map를 작성한다. confidence map의 measure는 strong classifier의 값으로 한다.
계산 방법은 각 patch를 2d DNF weak classifier에 입력하고 계산된 값이 학습 시에 저장된 bin에 포함된다면 이 patch는 positive가 된다.
confidence값을 integral image로 합하고 최대의 confidence값을 가진 영역이 추적 위치가 된다.
아래는 c.m(confidence measure)값을 평가하여 현재 프레임에서 물체가 발견되었는지(FOUND) 또는 잃어버렸는지(LOST)에 대한 모드 평가를 보여준다.
c.m < $th_1$ $\rightarrow$ LOST $\rightarrow$ initial state (전 영역 검색)
c.m > $th_2$ & LOST state $\rightarrow$ FOUND state로 초기화
c.m > $th_2$ & FOUND state $\rightarrow$ Update classifier
실제 구현 시의 strong classifier는 2D DNF만 사용하는 것이 아니라 1차원 weak classifier와 2d DNF classifier의 조합으로 구성된다.
(주1) patch는 8x8 pixels과 같은 특징을 계산할 수 있는 작은 크기의 window이다
(주2) Harr-like 특징을 예를 들어 생각해보면, patch 내 어떤 위치에, 어떤 크기로 두 특징 값 $h_i$와 $h_j$가 정의된다고 가정하자. 하나의 샘플이 선정되고 두 특징에 적용되면 2개의 값이 얻어지고 이것은 두 특징이 정의하는 2차원 평면 상의 좌표 값을 가리키게 된다. 이 좌표 평면은 균등한 간격으로 가로 세로로 나누어진 많은 작은 영역(bin)들이 정의되어 있다면 이 값은 이 영역들 중의 하나로 떨어지게 된다. voting이란 두 특징 값이 가리키는 영역의 counter(초기에는 0) 값을 하나 증가시키는 것이 된다. counter는 샘플의 부류에 따라 positive, negative의 두 개가 존재한다.
참고 논문
[1] Disjunctive Normal Form of Weak Classifiers for Online Learning based Object Tracking, ZhuTeng et. al., VISAPP'2013.
피드 구독하기:
글 (Atom)