레이블이 tracking인 게시물을 표시합니다. 모든 게시물 표시
레이블이 tracking인 게시물을 표시합니다. 모든 게시물 표시

2014년 8월 12일 화요일

Online boosting



초기에 지정된 영역을 5개 부분으로 나누어 (+1/-1)로 학습. 
물체 추적 시에는 물체 크기의 window를 sliding시켜 ROI 내부를 검색.
현재 위치에 대해 window 내부의 특징을 classifier로 평가하고 confidence 계산.
ROI 내부의 confidence map를 저장하고, map에 대해 integral image를 적용시켜 최대 confidence 영역을 찾아 냄.
최대 영역이 새로운 물체의 위치(+)가 되고, 이 물체의 배경(-)과 함께 다시 학습(update).

   

2014년 1월 7일 화요일

L1 minimization

L1-min 문제는 부족 제한(under-constrained)된 선형 시스템 b=Ax의 해를 구하는 방법 중의 하나이다[1].  관찰 벡터 b의 요소 수가 미지수 벡터 x의 요수 수보다 작기 때문에 A, b가 주어질 때, x를 구하는 것은 non-trivial linear solver 문제이다.

만일 x가 충분히 sparse하다면(즉, 표준 축(canonical coordinate)에서 요소의 대부분이 0이라면) x값은 minimum l1-norm을 계산함에 의해 얻어진다(주1):

min ||x||1, subject to b=Ax
 x

실제로는 observation b는 noise를 포함하므로 equality condition은 다소 완화되고 constrained BPDN (basis pursuit denoising)문제가 된다:

min ||x||1, subject to ||b-Ax||2 <= epsilon
  x

여기서, epsilon>0 은 미리 정해진 noise의 레벨을 나타낸다.  이 식은 가중치 ramda를 도입하면 unconstrained BPDN문제(주2)로 바뀐다:

min (1/2)||b-Ax||^2 + ramda.||x||1.
  x

위 식들에서 ||.||1은 l1-norm, ||.||2는 l2-norm이다. l2 norm은 Euclidean거리이고, l1 norm은 벡터 x의 요소들의 절대치의 합이다.  목표 x는 가능하면 sparse하면서 b=Ax를 만족하는 것이 정답이된다.



An example of L1-min solver

 unconstrained BPDN을 풀어내는 Shrinkage 알고리즘을 살펴 보자. 가림이 존재하는 물체를 L1 tracker를 사용하여 추적하는 예에서 Objective function은 다음과 같다:

min  L(z,e),  where L(z,e)=(1/2)||y-Uz-e||^2 + ramda||e||1
z,e

여기서, y는 관찰(observation) 벡터, U는 PCA 기저(basis), z는 기저에 대한 계수, e는 trivial template에 대한 계수 벡터이다.  이 식에 대한 closed-form 풀이법은 없다.  다음의 2단계로 이것을 푼다[2].

step 1: Given eopt, zopt는 zopt = U'(y-eopt)로 얻어진다.
step 2: Given zopt, eopt  = Sr (y-Uzopt).

여기서 Sr(.)는 shrinkage operator이다. 식의 유도와 증명은 [2]를 참조한다.  알고리즘은 다음과 같다.


아래의 Matlab code를 호출하기 위해서는 W에 PCA기저, srParam에는 미리 정해진 상수 값들을 넘겨 주어야 한다. Wang[2]의 논문에서는 32x32크기의 window patch에 대해 16개의 PCA 기저를 사용하므로 W는 1024x16크기의 행렬이다.
srParam값은 다음과 같다:
srParam.(lambda(0.05), L0(0.05), maxLoopNum(20), tol(10e-3))

data에는 물체를 포함하는 32x32크기의 window patch에서 평균값을 제거한 1024x1 크기의 벡터 값이 넘어가야 한다.  Wang의 코드에서는 이전 프레임까지 추적된 affine계수값의 근방에서 정규분포로 샘플을 600개 발생시킨다. 다음 프레임의 영상에 이렇게 발생된 600개의 affine 계수를 차례로 적용시켜 만들어낸 600개의 이미지에서 평균을 제거하고 남은 값을 차례로 data값으로 넘겨준다.

600번의 pca_L1함수 호출의 결과로 얻어낸 600개의 z,e값을 가지고 각 particle의 confidence를 평가한다.

function alpha = pca_L1(data, W, srParam)
%%  function alpha = pca_L1(data, W, srParam)
%%  Object representation via sparse prototypes 
%%                        (PCA basis vectors +trivial templates)
%%  Input:  
%%          data:   A normalized data vector
%%          W:       PCA basis vectors
%%          srParam:    Parameters for L1 minimization
%%              -srParam.lambda
%%              -srParam.maxLoopNum
%%              -srParam.tol
%%  Output:
%%          alpha:  The representation coefficient
%%

%%1.Initialization:

coeff = zeros(size(W,2),1);  % The coefficients of PCA basis vectors
% size(coeff) = 16x1, size(W)=1024x16 (16 basis for 32x32 window patch)

err   = zeros(size(data));     % The coefficients of trivial templates
% size(err) = 1024x1 for 32x32 window patch

objValue = zeros(1,srParam.maxLoopNum); % The values of objective functions
% size(objValue) = 1x20 for max iteration # 20


%%2.Iterative solution: 

for num = 1:srParam.maxLoopNum % opt.srParam=20
    %(2.1)Fix 'err', slove 'coeff' --(Lemma 1 in Section III; Step 3 in Table)
    coeff = W'*(data-err);   % U'(y-e)
    %(2.1)Fix 'coeff', slove 'err'--(Lemma 2 in Section III; Step 4 in Table)

    y = data-W*coeff;        % Sr(y-Uz)
    err = max(abs(y)-srParam.lambda, 0).*sign(y); % size(abs(y))=1024x1
    % abs(y) 값 중에서 lambda(0.05)보다 작은 잔차를 가진 경우(즉, 가림이나 
    % background clutter가 아니라고 판단)는 err 값을 0으로 만듬.
    % 따라서, err가 살아 있는 부분은 가림이나 clutter에 의한 오차 부분이다.
   
    if num == 1
       alpha = [coeff; err]; % Save the result
       continue;
    end
   
    objValue(num) = (y-err)'*(y-err) + srParam.lambda*sum(abs(err));
    % objValue는 가림은 최소화하면서 data를 잘 근사하는 coeff와 err
    % 값을 구하는 것이 목표이다.
    % 식의 앞 부분에서 y=data-W*coeff는 후보 윈도 패치의 잔차이고, 이 중에서
    % 가림이 존재하는 부분은 err를 빼줌에 의해 제거되어 보상된다. 
    % 뒤의 항은 err벡터 내부에 값을 가진 항을 최소화해서 err가 패치 내에서
    % 작용하는 픽셀의 수를 줄이도록 해준다.  

    if abs(objValue(num)-objValue(num-1)) < srParam.tol
       break;
    else
       alpha = [coeff; err]; % Save the result
    end
end
% 첫번째 호출에서 objVaue=1.4406 1.4247 1.4181 1.4159 1.4151이고
% 5번 반복 후에 수렴하였음. objective func. 값은 점차 작아져서 수렴함. 
% z, e  <--  alpha  for input 'data' 



위 함수를 600번 호출하여 만든 600개의 z,e 집합을 confidence값으로 바꾸어 주어야 한다. 먼저 target template를 표현하는 16개의 target coefficient coeff와 trivial template를 표현하는 1024개의 trivial coefficient err를 얻어 낸다.  또, 원 데이터인 data에서 z,e로 재 생성한 데이터를 빼서 잔차 diff를 만든다.  

600개 중에서 하나만 평가해 보자. err 내의 600개 벡터 중의 하나를 err_i라 하자.  먼저, err_i값을 어떤 임계값(threshold)을 중심으로 분리한다.
confidence가 높아지기 위해서는 err_i 요소 중에서 th보다 큰(즉, occluded되었다고 가정된) 요소의 합이 작아져야 한다. 즉, sparse해야 한다는 것이다.  또한, err_i 요소 중 th보다 작은 요소의 값은 occlusion이나 background clutter가 없는 픽셀이므로 이 경우는 잔차 diff가 가능하면 작아야 한다.
아래의 코드는 이러한 아이디어를 반영하고 있다.  


coeff = alpha(1:size(tmpl.basis,2),:); %The coefficients of PCA basis vectors
% size(coeff)=16x600, tmpl.basis = 16

err = alpha(size(tmpl.basis,2)+1:end,:);  %The coefficients of trivial templates
% size(err) = 1024x600

%% Calucate observation likelihood  
% diff는 600개의 각각의 후보 패치에서 평균 템플릿을 제거한 영상 패치. 
% 하나의 후보 패치는 32x32=1024x1이므로 전체는 1024x600이다.
diff = diff-tmpl.basis*coeff-err;  %Reconstruction, diff=1024x600
diff = diff.*(abs(err)<opt.srParam.L0);  % abs(err)<opt.srParam.L0 = 1024x600                          
param.conf = exp(-(sum(diff.^2)+opt.srParam.L0          
              *sum(abs(err)>=opt.srParam.L0))./opt.condenssig)'; % 0.05
% sum(diff.^2)=1x600, sum은 각 열의 합. 
% 두 항이 다 작아야 되는데, 앞의 항은 err가 작은 항들의 합이므로 가림이 없는 부분
% 뒤 항은 err가 큰 항들의 합이니 가림 부분
% 즉, 비 가림부분은 잔차가 작아야 하고, 가림 부분은 err의 합이 작아야(sparse) 해야 함.






(주1) 원래 Ax=b의 선형시스템 방정식에서 관찰 값 b내의 요소 수가 미지수 x 내의 요소 수보다 작다면 이 식은  부족 제한(under-constrained)이며, 해의 수가 무한개가 되므로 풀 수 없게 된다.

단, x가 sparse하다면 이 식은 BP(basis pursuit)문제가 되고 제한적으로 풀 수 있다.

Ax = b

에서, 0이 아닌 x의 요소는 A(보통 측정행렬이라 부름)내 어떤 열(atom)에 대응한다. x를 결정하는 것이란 신호(measurement) b를 재생성하기 위해 필요한 A행렬 내의 열의 요소를 선택하는 것이다.

이러한 x 내의 0이 아닌 요소의 집합을 basis라고 부른다. 따라서 x 내의 0이 아닌 요소를 찾아 내는 것을 BP(basis pursuit) 라고 부른다.

L1-놈의 사용은 A행렬의 각 atom에 어떤 비용을 할당하는 것이다.  이 비용의 나열이 x벡터이다. 단, 이 비용의 합은 최소화되도록 한다.



(주2) BPDN의 해를 찾는 문제는 convex quadratic problem이다. quadratic은 2차 방정식을 의미하고, convex의 의미는 어떤 제한된 구간 내에서 임의의 직선을 그었을 때, 2차 식과 만나는 두 점 아래의 그래프의 어떤 점도 이 직선 위에 있지 않을 때 convex라 부른다[7]. convex한 형태의 방정식은 gradient-descendant법으로 최적해를 찾았을 때, 항상 전역 최적값을 보장하기 때문에 최적화에 유리하다.
BPDN 문제는 2차 미분 값이 항상 양수이므로 convex이고 전역 최적값을 보장한다[3, 5].  




참고 논문
[1] A. Y. Yang, et. al., Fast l1-minimization algorithms for robust face recognition, IEEE Trans. IP, 2013
[2] D.Wang, et.al., Online object tracking with sparse prototypes, IEEE Trans. IP, 2011.
[3] Basis pursuit, Wikipedia
[4] BPDN, Wikipedia
[5] Convexity of quadratic functions in two variables, Webpage
[6] Kristen Michelle Cheman, OPTIMIZATION TECHNIQUES FOR SOLVING BASIS PURSUIT PROBLEMS, Ph.D. thesis
[7] Convex function, Wikipedia





2014년 1월 5일 일요일

Object tracking with sparse representation (L1 tracker)

Sparse 표현은 최근 cv 분야에서 폭 넓게 인용되고 연구되는 주제이다. 물체 추적 문제에서 가림(occlusion) 문제의 해결은 여전히 어려운데, sparse표현이 이를 다루고 있다.

Mei[1]는 L1 tracker를 제안하여 물체 추적 시 부분 가림을 trivial template를 이용하여 해결 하였다.  목표 물체를 표현하는 방법을 몇 가지 살펴 보자. 


(1) PCA에 의한 관찰 물체 표현


그림은 목표 물체의 영상을 표현하기 위해 pca를 적용한 경우를 보여준다.  주축(pca basis) 몇 개와 주축에서의 좌표 값(target coefficient)이 곱해져서 목표 영상을 생성한다: 

y = Uz +e

여기서, y는 관찰 벡터, U는 기저이고, z는 좌표 값, e는 오차이다.  y를 안다면, z는 z=U'y로 계산 가능하다.  잔차(residual)은 ||y-UU'y||^2이다.  


(2) L1 tracker

Mei는 그림에서 보인 바와 같이 sparse표현을 제안 했다. 물체의 가림을 다루기 위해 trivial template를 도입하였다.  물체에서 가림 없이 보이는 부분은 target template가 나타내고, 가려지는 부분은 trivial template에 곱해지는 trivial 계수가 표현한다.  예를 들면, 얼굴의 크기가 32x32라면 trivial 계수는 1024의 요소를 가진 벡터이다.  target 계수는 여러 템플레이트 중에서 목표 물체와 가장 유사한 템플릿의 인덱스를 나타낸다.  

y=Az+e = [A a][z e]' = Bc

여기서, y는 관찰 벡터, A는 템플릿들의 행렬, z는 템플릿을 선택하는 계수, e는 trivial template에 대한 계수 벡터이다. 행렬 a는 32x32 크기의 trivial 템플릿(즉, 1024크기의 벡터)가 1024개 있는 행렬로(즉, 1024x1024이다) 하나의 벡터에는 해당 픽셀에 대응되는 위치에 1이 저장되어 있고 나머지가 모두 0인 벡터이다.   trivial 템플릿의 계수벡터 e는 1024 벡터이다.  계수 벡터의 값이 occlusion을 표현하게 된다. 
   
수식의 풀이는 L1 minimization을 통한다.  


여기서, ||.||2는 l2놈이고, ||.||1은 l1놈이다.  l1놈은 모든 계수의 절대치의 합의 값으로 생각하면 된다.  식의 의미를 살펴보면, Bc는 가능하면 관찰 벡터 y와 일치해야 하고, c벡터는 sparse(l1놈이 작아지려면 벡터 내에 값이 듬성듬성 들어 있어야 한다)해야 한다는 의미이다.  즉, occlusion은 최소화하면서 y와 잘 일치하도록 계수치들을 결정하면 된다.  단점은 연산량이 크다. 


(3) PCA 기저를 이용한 L1 tracker 

Wang[2]은 SKL과 L1 tracker를 결합하였다.  그림 (c)는 위 그림 (b)의 target 템플릿을 pca 기저(basis)로 바꾼 것이다. 여러 템플릿 영상을 pca의 기저로 표현하면 템플릿의 누적, 갱신 등이 효과적이다.  즉, SKL(sequential KL)을 적용할 수 있다. 

y = Uz+e = [U a][z e]'

여기서, y는 관찰 벡터, U는 pca기저, z는 기저에 대한 계수, e는 trivial 템플릿에 대한 계수벡터이다.    이 식을 다시 쓰면


이다.  위 그림에서 (b)와 (c)를 비교해 보면, (b)의 경우는 물체나 trivial 템플릿 계수 벡터나 둘 다 sparse하다.  즉, target template들은 모두 하나의 물체를 나타내는 영상이므로, 이들 사이에는 상관성이 존재한다. (c)의 경우는 pca기저 벡터가 서로 독립(orthonormal)하기 때문에 기저 계수 벡터는 sparse하지 않고, trivial 계수만 sparse하다.  일반적으로 pca기저는 몇개 안되며(wang논문에서는 16개 사용), trivial template수는 아주 많다(wang에서는 1024개).

식에서 y-Uz는 y가 Uz(pca 기저에 의해 표현되는 템플릿 패치)에 가까와야 한다는 것을 표현하고, y-Uz의 값이 큰 부분(즉, 가림이나 background clutter)은 e에 의해 제거(보상)된다. 단, e가 패치 내의 모든 픽셀에 대해 작용하지 않도록 y-Uz값을 분석해서 잔차가 큰 부분에만 선택적으로 e가 작용하게 한다. 



참고 논문
[1] X.Mei, H. Ling, Robust visual tracking using L1 minimization, CVPR 2009.
[2] D.Wang, et.al., Online object tracking with sparse prototypes, IEEE Trans. IP, 2011.






  

2013년 12월 30일 월요일

Particle filter 소개

물체 추적은 은닉 변수를 가진 Markov모델에 Bayesian 추론을 적용하는 것이다$^{주1}$. 시간 t 프레임에서 관찰 이미지(observation) 집합 $Y_t$={y1,y2,...,yt}가 주어진다고 할 때, 은닉 상태 변수 $x_t$는 recursive하게 추정할수 있다. 


여기서, p(xt|xt-1)은 두 연속 상태 사이의 시스템 동적 모델이다. p(yt|xt)는 상태 xt에서 관찰(observation) 모델의 우도(likelihood)를 나타낸다.

이 식의 우변에서 시간 인덱스 $t-1$을 $t$로($t$는 $t+1$로) 바꾸고 좌변의 $p(x_t|Y_t)$를 다시 대입하면 시간 인덱스만 진전된 동일한 표현이 되므로 위 식은 반복해서 적용 가능한 재귀적(recursive) 표현이다.


Particle filter로 위 식을 표현하면, t프레임까지의 모든 관찰값이 주어질 때 추적 물체의 최적 상태는, 시간 t에서 N개의 샘플에서의 최대 사후확률을 추정하는 것이다.


이 식은 재귀적 형태를 포함하고 있다. $p(x_t^i|x_{t-1})$에 따라 $t-1$시간까지 추정한 상태 값 $x_{t-1}$의 근방에서 $x_t^i$를 확률적으로 발생시키고 각각의 파티클 $x_t^i$에서 관찰 값  $p(y_t^i|x_t^i)$를 얻는다.  시간 $t$에서의 새로운 상태는 두 확률 곱의 최대 값을 주는 $x_t^i$가 된다.


  
Particle filter의 simulation 예
아래 코드는 1차원 운동을 하는 물체를 tracking하는 pf를 보여준다.

움직이는 물체의 운동은 2개의 sine wave와 하나의 linear motion형태의 궤적이 결합되어 있으며 결합부에 모션 불연속부가 존재한다.
불연속이 있어도 pf는 물체를 놓치지 않고 성공적으로 대상을 추적하는 것을 보여준다.


-Green dots: particles (150개)
-Red line: true state
-Blue line: estimated state
-모션 불연속(red line)이 있는 위치가 2군데 있음(위치 데이터는 크게 삼등분 가능)
-특정 위치에서의 거동 설명을 위해 13frame, 53frame 위치가 blue 색의 수직 라인으로 표시되고, 아래 그림에서 설명.



위 그림은 100프레임 동안 물체를 추적한 결과 이다. 수직 위치를 추적하는 것이며, 약 25프레임 근방과 49프레임 근방에서 모션 불연속이 존재한다.
particle들은 운동물체의 궤적을 잘 따라 가고 있다.




13프레임의 푸른색 수직선을 보면 물체의 궤적이 연속곡선으로 부드럽게 이동한다. 따라서, particle들은 mean주위에 집중되어 분포한다.
추정된 현재 위치(녹색점) 근방에서 측정치(measurement) 값도 크므로 큰 변화없이 부드러운 추적이 발생한다.




53프레임의 수직 선 위치에서는 직전 49프레임에서의 갑작스러운 불연속 모션으로 인해 파티클들은 수직 위치 -2 근방에 주로 놓여 있고 물체의 현재 궤적은 1 근방이다.  측정치의 pdf를 보면 1 근방에서 확률값이 크므로 이 주변의 파티클들의 가중치가 크지므로 곧 -2 근방에 있던 파티클들이 1 근방으로 모이게 된다.


%
% 1D particle filter tracking a height position
% Summarized by funMV, 12/2013 
% [Ref.] T. Svoboda, J. Kybic, V. Hlavac, Image processing, Analysis, 
%   and Machine Vision, A Matlab companion, Thomson press.
%   pp.232
%   
%   Original version is in http://visionbook.felk.cvut.cz
%
clear all;
clear classes;

% 파라메터 설정
conf.steps = 100; % number of steps(100프레임 동안)
conf.sigma_1 = 0.02; % standard deviation - system
conf.N = 150; % number of samples(파티클)
conf.sigma_2 = 0.5; % standard deviation for the measurement function
conf.Cov = 0.1; % covariance matrix - sampling (scalar for 1D)
conf.alpha = 0.3; % factor for exponential forgetting - motion model


% tracking할 대상 데이터의 생성(true values)
% 크게 3부분의 데이터 생성(첨부 자료 참조)
third = round(conf.steps/4);
X(1) = normrnd(0,conf.sigma_1);
for i = 1:(third-1)
  X(i+1) = X(i) + (sin(2*pi*i/third)-sin(2*pi*(i-1)/third)) + ...
           normrnd(0,conf.sigma_1);
end
X(third) = sin(3*pi/2) + normrnd(0,conf.sigma_1);
for i = third:(2*third-1)
  X(i+1) = X(i) + (sin(2*pi*i/third+3*pi/2)-sin(2*pi*(i-1)/third+3*pi/2)) + ...
           normrnd(0,conf.sigma_1);
end
increment = -2/(conf.steps-2*third);
X(2*third) = 1 + normrnd(0,conf.sigma_1);
for i = (2*third+1):conf.steps
  X(i) = X(i-1) + increment + normrnd(0,conf.sigma_1);
end



% 파티클 값들의 설정
%
S.s   = normrnd( 0, conf.Cov, 1, conf.N ); % initialize samples
% 평균을 0, 분산을 conf.Cov로 한 정규분포의 샘플을 conf.N개 발생
% S.s=1x150, mean(S.s)=-0.0011

S.pi  = ones(1,conf.N) / conf.N;   % set uniform weights
% 처음에는 가중치를 전부 1/N의 값을 가지게 함. size(S.pi)=1x150

S.v   = 0;                                 % initialize motion model
S.est = estimation( S, conf );    % set estimated value
% S.pi*S.s' = -0.001(평균이 0에서 샘플이 발생 했고,
%           모든 가중치는 동일하므로 기대값(가중평균)은 0)


data =[];

% tracking의 실행
for step = 2:conf.steps           % for all generated states
  S.x = X(step);                  % states of the system. 추적할 실제 값
  S = particle_filtering( S, conf ); % run particle filtering

  % 결과 확인을 위한 데이터 저장
  data = [data; step X(step) S.est abs(S.est-X(step))]; % real(true), estimation, error
end





function S = particle_filtering(S,conf)
% PARTICLE_FILTERING Particle filtering (Condensation)
% CMP Vision Algorithms http://visionbook.felk.cvut.cz
% Petr Lhotsky, Tomas Svoboda, 2007
%
% Usage: S = particle_filtering(S,conf)
% Inputs:
%   S  struct  Structure with samples and weights. 
%   .x [dim x 1]  State of the system. This represent the true
%     state of the system. It is used for demonstration purposes
%     only. It is normally unknown. dim denotes dimensionality of
%     the state space.
%   .s    [dim x N]  Matrix containing N samples (particles).
%   .pi   [1 x N]    Weights of the samples.
%   .v    [dim x 1]  Predicted velocity - motion model.
%   .est  [dim x 1]  Estimated value - estimated state of the observed system.
%   conf  struct     Structure with configuration.
%   .N    1x1        Number of samples.
%   .Cov  [dim x dim]Noise covariance matrix.
%   .alpha  1x1      Factor for the exponential forgetting of the
%     motion model; 
%     lower values put the accent on the history and 
%     higher values on the actual movement; 0 turns the motion model off.[-.75ex]
% Outputs:
%   S  struct  The same structure as for input, but at time step k+1.
%
% The filtering procedure consists of the following steps:
% Resample data S_ using importance sampling. The sampling
% procedure draws samples from the set such that samples with higher
% weights are likely to be picked more times. Since the total
% number of samples is preserved, some samples with lower weights might
% not be
% selected at all. Note that we are still using the states at time t-1.
% The importance sampling step is performed by
% function importance_sampling.
S.s = importance_sampling( S.s, S.pi ); % S.s: 정규분포(0-mean), S.pi(weight, 1/N)

% Predict the state for time t, and add noise.
% Prediction is here only a simple motion drift, see drift_samples.
% See function noisify for details of adding noise.
S.s = drift_samples( S, conf );
S.s = noisify( S, conf );

% The correction (measurement) step evaluates the likelihood of how well the samples
% This function depends on the application, see a simple
% measurement1D or a more realistic measurement2D.
S.pi = measurement( S, conf );

% normalize weights
S.pi = S.pi ./ sum(S.pi);

% Compute a pointwise state estimate from the samples. It is worth mentioning
% that the computation of the state estimate may be meaningless in
% some situations, especially for
% multimodal distributions.
S.est_old = S.est;
S.est = estimation( S, conf );

% Update the state velocity which is needed for the simple
% drift. Simple exponential forgetting is applied. The velocity
% does not need to be used in some applications.
S.v = conf.alpha*(S.est-S.est_old) + (1-conf.alpha)*S.v;

return; % end of particle filtering




function s_noise = noisify(S,conf)
%NOISIFY Noisify the samples with normal noise
%CMP Vision Algorithms http://visionbook.felk.cvut.cz
% Usage: s_noise = noisify(S,conf)
% Inputs:
%   S  struct  Structure with samples and weights.
%   conf  struct  Structure with configuration.
% Outputs:
%   s_noise  [1 x N]  Vector with samples.
% Add noise to samples for a given covariance matrix conf.Cov.
% This implementation is based on .
%
%
% Based on:
% About: Statistical Pattern Recognition Toolbox
% (C) 1999-2003, Written by Vojtech Franc and Vaclav Hlavac
% <a href="http://www.cvut.cz">Czech Technical University Prague</a>
% <a href="http://www.feld.cvut.cz">Faculty of Electrical Engineering</a>
% <a href="http://cmp.felk.cvut.cz">Center for Machine Perception</a>

[dim N] = size( S.s );   % get dimension
[U,L] = eig( conf.Cov ); % compute eigenvalues and eigenvectors
s_noise = S.s + inv(U')*sqrt(L)*randn(dim,N); % dewhitening transform
% S.s를 빼고 생각해 보면, Cov행렬을 고유값분해 해서 고유벡터 U와 그 기저에서의
% 좌표 값 L을 얻었다. 좌표 값 L은 Cov행렬의 크기이다. 여기에 곱해 평균 0과 분산 1을
% 가진 정규분포에서 샘플을 N개 생성한다면 평균 0근방에서 분산 L을 가진 분포의
% 샘플을 얻는 것이다.
% U'.a는 U기저로 어떤 벡터 a를 표현하는 것이다. U'a는 U기저에서의 벡터 a의 좌표
% 값이다. 따라서,
% U'a = sqrt(L)*randn(dim,N)에서 sqrt(L)*randn(dim,N)는 U기저에서의
% a벡터의 좌표 값이다.
% a = inv(U')*sqrt(L)*randn(dim,N)는 표준 기저에서의 좌표벡터를 얻는 것이다.
% (원래 상태 벡터의 값들은 표준 기저에서의 값들이었다)
% 정리하면, 샘플 분포는 기저 U에 대한 정규분포를 갖도록 발생시키고
% 표준 기저의 벡터로 다시 변환해 주는 것이다.
return





function [w] = measurement(S,conf)
%MEASUREMENT Evaluation of the samples
%CMP Vision Algorithms http://visionbook.felk.cvut.cz
% Usage: w = measurement(S,conf)
%  S  struct  Structure with samples and weights. 
%  conf  struct  Structure with configuration. 
%   .sigma_2  [1]  Standard deviation of the noise.
%  w  [1 x N] Vector with measurements for each sample. 
% Function measurement evaluates each sample according to a measurement
% function and returns a likelihood of each sample.
% The measurement function is modeled by a Gaussian centered around the 
% true value and a small constant is added to represent a non-zero
% response of a real measurement function.
% This is an approximation of an ideal which should be smooth and
% peak at the true value. The non-zero observation likelihood further away from the true state
% also prevents samples from dying prematurely. 
% See demo2D/measurement for a more
% realistic measurement function.
%

w = normpdf((S.s-S.x),0,conf.sigma_2) + 0.1;
return




function [x_res,freq] = importance_sampling(x,p,varargin)
% IMPORTANCE_SAMPLING importance sampling
% CMP Vision Algorithms http://visionbook.felk.cvut.cz
% Tomas Svoboda, 2007
%
% Usage: [x_res,freq] = importance_sampling(x,p,Nnew,show,fid,save)
% Inputs:
%   x  [dim x N]  Matrix of N samples of dimension .
%   p  [1 x N]  Probabilities of samples.
%   Nnew  (default N)  Number of new samples.
%   show  (default 0)  If set to 1 the sampling steps are
%     graphically visualized. It works only for 1D data.
%   fid   (default gcf)  Figure handle for the graphical visualization.
%   save  (default 0)  Save the graphically visualized steps to disk. 
% Outputs:
%   x_res  [dim x Nnew]  Selected (sampled) samples from x.
%   freq  [1 x N]  Frequencies of selections, giving the number of
%     times a particular sample from x was selected.

Nnew = length(x);

cum_prob = cumsum(p);    % cumulative probability, cum_sum=1x150
x_res = zeros( size(x,1), Nnew); % space for resampled samples, x_res=1x150(전부 0)
freq = zeros( size(x) );    % selection frequency of the old samples, freq=1x150, 전부 0


for i = 1:Nnew
  % selection sample from a uniform density 0...1
  r = rand; % 0과 1사이의 난수 발생
  j = find( cum_prob==min(cum_prob(cum_prob>r)), 1 );
  % cum_prob>r이 되는 cum_prob요소중 최소 값을 주는 index계산
  % take the j-sample to the new sample set
  x_res(:,i) = x(:,j); % j인덱스에 있는 값을 저장
  % x_res에는 더 많이 샘플링된 j인덱스가 주는 x값이 더 여러번 저장됨.
  % increment the frequency table
  freq(j) = freq(j) + 1; % j인덱스의 count를 증가
end
return; % end of importance_sampling, x_res만 리턴됨.




function est = estimation(S,conf);
%ESTIMATION The best guess for the state of the system - estimated value
%CMP Vision Algorithms http://visionbook.felk.cvut.cz
% Usage: est = estimation(S,conf)
%  S  struct  Structure with samples and weights. 
%  conf  struct  Structure with configuration. 
%  est  [dim x 1] Value of the predicted state. 
% Computes the best guess for the state of the system 
% as the weighted average of the samples 
% x = sum_i^N,
% which is implemented as a scalar product of vectors 
%  and s.
%

est = [S.pi]*[S.s]';
% 평균을 구한다고 보면 됨. 샘플이 S.s에 들어 있고, 각 샘플의 가중치가 S.pi
% 이므로 각 샘플들의 가중 합이 계산. 즉, 기대값, 평균임.
return % end of estimation



function s_drift = drift_samples(S,conf)
%DRIFT_SAMPLES Drift samples according to the velocity of the motion model
%CMP Vision Algorithms http://visionbook.felk.cvut.cz
% Usage: s_drift = drift_samples(S,conf)
%  S  struct  Structure with samples and weights. 
%  conf  struct  Structure with configuration. 
%  s_drift  [dim x N] Drifted samples. 
% Drift samples according to the velocity model. 
% This is a simple demonstration function.
% A more general predictor is naturally possible.
%

s_drift = S.s + S.v;
return





(주1) 은닉변수(hidden variable)는 시스템에 숨겨져 있는 상태 변수(vector) $x$를 의미한다. 즉 관찰 값 $Y$를 이용하여 숨겨진 $x$를 추정하는 문제이다.  Markov 모델이란 측정 값이 서로 독립적이지 않은 연속 값의 체인으로 발생한다는 것이다.  서로 인접한 값은 상관성이 크고 멀어질 수록 상관성이 작아진다.  Bayesian 추론이란 수식 자체가 Bayesian theory를 이용하여 얻어지기 때문에 이렇게 표현한다.

















2013년 12월 29일 일요일

Quaternion matrix

% Simulation for rotation matrix
% Coded by funMV. 12/2013
clear; clc;

% x축에 대해 45도 회전
% 회전 행렬은 표준 축이 회전된 방향 벡터(unit vector)이다.

alpa = 45; % x축 기준
beta = 30; % y축
gama = 60; % z축

p2a = pi/180;

% (1) 직접 3x3크기의 R행렬을 만듬
rr1 = rot(alpa*p2a, beta*p2a, gama*p2a);

% (2) rx, ry, rz로 만드나 결과는 동일
ssx = sin(alpa*p2a);
csx = cos(alpa*p2a);
ssy = sin(beta*p2a);
csy = cos(beta*p2a);
ssz = sin(gama*p2a);
csz = cos(gama*p2a);

rx = [1 0 0; 0 csx -ssx; 0 ssx csx];
%{
rx =

    1.0000         0         0
         0    0.7071   -0.7071
         0    0.7071    0.7071
%}
% x축을 중심으로 회전 시키므로 x축 방향은 불변
% 회전 각의 방향은 오른손 나사 방향으로 45도 회전
% 기존 y축은 [0 1 0]에서 [0  0.7071 0.7071]로 변경
% 기존 z축은 [0 0 1]에서 [0 -0.7071 0.7071]로 변경
% 회전 행렬 rx는 회전 후의 세 축의 방향 벡터(unit three vectors)

ry = [csy 0 ssy; 0 1 0; -ssy 0 csy];
rz = [csz -ssz 0; ssz csz 0; 0 0 1];
rr2 = rz*ry*rx;

% R(3x3)행렬에서 다시 3개의 각도 벡터를 추출
v = rpy(rr2);
v/p2a  % 45, 40, 60이 나옴


% 3개의 각도 벡터에서 quaternion을 계산 
q = angle2quat(v(1),v(2),v(3)); % angle to quaternion
% norm(q) = 1

% quaternion에서 다시 3개의 각도를 추출
rpy(q2r(q))/p2a % 세개의 각도 값 출력 순서: 60,30,45도로 나옴)

% matlab내부 함수를 이용해 각도 값 추출
[r1,r2,r3] = quat2angle(q); %  45,30,60도 나옴
r1/p2a
r2/p2a
r3/p2a



% 두 연속 회전에 의한 각도 값 비교
% quaternion의 연속 적용과 R회전 행렬의 연속 적용 후
% 결과 값이 같은지를 비교한다. 
% 새로운 3개의 각도 벡터 정의
dom = [2, 5, 7]*p2a;
rr3 = rot(dom(1),dom(2),dom(3)); % 회전 행렬 생성

q2 = angle2quat(dom(1), dom(2), dom(3)); % quaternion 계산
qp1 = quatmultiply(q, q2); % 두 quaternion의 곱
%qp2 = qprod(q,q2); % 두 quaternion의 곱
[r4,r5,r6] =quat2angle(qp1); % quaternion에서 각도 추출
r4/p2a
r5/p2a
r6/p2a     % 51.1953, 30.6278, 70.0420   

rr4 = rr3*rr2; % 하나의 강체에 두 회전의 연속 적용
v3 = rpy(rr4); % 즉, R행렬의 연속 적용이나 quaternion의 곱에 의한
v3/p2a         % 회전의 연속 적용이나 결과는 동일함 









function v_rot=rpy(m_rot)
% function v_rot=rpy(m_rot)
%
% Description
%  Computes the orientation vector (in rads) corresponding
%  to a rotation matrix. (dim 3)
%  [psi, theta, phi]
%  R -> (alpa, beta, gama)로 변환 함수 
%  v_rot1 = alpa(x), v_rot2=beta(y), v_rot3=gama(z)
%  에 대응되는 각도임 
% The input datum is:
% - m_rot.- a rotation matrix
%
% The return value is:
%  the rpy vector
v_rot(3)=angle(m_rot(2,1)*i+m_rot(1,1));
v_rot(2)=angle(-m_rot(3,1)*i+m_rot(1,1)*cos(v_rot(3))+m_rot(2,1)*sin(v_rot(3)));
v_rot(1)=angle(m_rot(3,2)*i+m_rot(3,3));
return;



function r=rot(psi,theta,phi);
% function r=rot(psi,theta,phi)
%
% Description
%  Computes the rotarion matrix corresponding to a oritentation vector
% The input data are:
% - psi   .- the psi angle (radians)
% - theta .- the theta angle (radians)
% - phi   .- the phi angle (radians)
%
% The return value is
% the rotation matrix (dim 3x3)
% Coded by 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Programmer   : Jose Maria Martinez                                       
%% Languaje     : Matlab 4.2 c                                              
%% Date         : February 1996                                             
%% Status       : Prueba                                                    
%% History : 16-8-95 creation                                       
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cosphi=cos(phi);
sinphi=sin(phi);
costheta=cos(theta);
sintheta=sin(theta);
cospsi=cos(psi);
sinpsi=sin(psi);

r=zeros(3,3);
r(1,1)=cosphi*costheta;
r(1,2)=cosphi*sintheta*sinpsi-sinphi*cospsi;
r(1,3)=cosphi*sintheta*cospsi+sinphi*sinpsi;
r(2,1)=sinphi*costheta;
r(2,2)=sinphi*sintheta*sinpsi+cosphi*cospsi;
r(2,3)=sinphi*sintheta*cospsi-cosphi*sinpsi;
r(3,1)=-sintheta;
r(3,2)=costheta*sinpsi;
r(3,3)=costheta*cospsi;
return;



%-----------------------------------------------------------------------
% Authors:  Javier Civera -- jcivera@unizar.es 
%           J. M. M. Montiel -- josemari@unizar.es
% Robotics, Perception and Real Time Group
%           Institute of Engineering Research (I3A)
% Universidad de Zaragoza, 50018, Zaragoza, Spain
% Date   :  May 2010
%-----------------------------------------------------------------------
function R=q2r(q)

x=q(2);
y=q(3);
z=q(4);
r=q(1);

R=[r*r+x*x-y*y-z*z  2*(x*y -r*z)     2*(z*x+r*y)
   2*(x*y+r*z)      r*r-x*x+y*y-z*z  2*(y*z-r*x)
   2*(z*x-r*y)      2*(y*z+r*x)      r*r-x*x-y*y+z*z];



% Product of two quaternion
function qp=qprod(q,p)
a=q(1);
v=reshape(q(2:4),3,1);
x=p(1);
u=reshape(p(2:4),3,1);

qp = [a*x-v'*u, (a*u+x*v)' + cross(v,u)'];





References
[1] 오일러각과 회전행렬(Euler Angles and Rotation Matrix)
[2] 각속도(Angular Velocity)와 오일러각, 회전행렬 간의 관계
[3] 쿼터니언(Quaternion)과 오일러각, 회전행렬 간의 관계
[4] 회전 보간: 쿼터니언(Quaternion)을 사용한 Slerp(구면 선형 보간)

2013년 11월 27일 수요일

이미지의 affine 변형 함수

이미지의 affine 변형을 계산. 입력 프레임 img 내에서 p파라메터에 있는 affine계수에 따라 일정 부분을 취해 sz(예를 들면, 32x32)크기의 영상으로 만들어 리턴. p 행렬 내에 복수개의 affine 계수가 넘어가면 복수 개의 sz 크기 영상들이 생성되어 리턴.


function wimg = warpimg(img, p, sz)
% function wimg = warpimg(img, p, sz)
%
%    img(h,w)   :   입력 프레임
%    p(6,n)     :   Affine 인자 행렬(n은 affine 인자 set의 갯수)
%    sz(th,tw)  :  입력 영상 내에서 취할 template 크기
%
%    이미지의 affine변형을 고속으로 처리하기 위한 함수

%% Copyright (C) 2005 Jongwoo Lim and David Ross.
%% All rights reserved.

if (nargin < 3)
    sz = size(img);
end
if (size(p,1) == 1) % size(param0,1)=1
    p = p(:); % param0는 행벡터인데 열벡터로 만들어 줌
end
w = sz(2); % 32
h = sz(1); % 32
n = size(p,2); % size(p,2)=1
[x,y] = meshgrid([1:w]-w/2, [1:h]-h/2);
% x=[ -15 ... 16;
%     -15 ... 16;
%        ...
%     -15 ... 16], size(x)=32x32
% y=[ -15 .... -15;
%     -14 ...  -14;
%         ...
%      16 ...   16]; size(y)=32x32
pos = reshape(cat(2, ones(h*w,1),x(:),y(:)) ...
              * [p(1,:) p(2,:); p(3:4,:) p(5:6,:)], [h,w,n,2]);
% size(ones(h*w,1))=1024, size(x(:))=1024
% CAT Concatenate arrays.
%    CAT(DIM,A,B) concatenates the arrays A and B along
%    the dimension DIM.
%    CAT(2,A,B) is the same as [A,B].
%    CAT(1,A,B) is the same as [A;B].
% cat(2, ones(h*w,1),x(:),y(:)) =
%  [ 1 -15 -15; 1 -15 -14; 1 -15 -14; ...; 1 16 15; 1 16 16]: 1024x3
% [p(1,:) p(2,:); p(3:4,:) p(5:6,:)]
%  177.0000  147.0000
%    0.1166   -0.6368
%   -0.6368    3.4771
% p1=cat(2, ones(h*w,1),x(:),y(:))*[p(1,:) p(2,:); p(3:4,:) p(5:6,:)]
% size(p1)=1024x2
% size(pos)=32x32x1x2
%
% (Example) For one pixel and one set of affine params:
% (1 x y).(tx ty; a11 a21; a12 a22)=(tx+a11.x+a12.y   ty+a21.x+a22.y)
% For all pixels in sz (32x32=1024 pixels) and one set of affine parameters:
% [1 x1 y1; 1 x2 y2; ....].[tx ty; a11 a21; a12 a22]
%      = [tx+a11.x+a12.y   ty+a21.x+a22.y; tx+a11.x+a12.y   ty+a21.x+a22.y; ...]
% *size: (1024x3).(3x2) = (1024x2)
% For all pixels & n sets of affine parameters:
% [1 x1 y1; 1 x2 y2; ....].[tx(1)  tx(2)  ... tx(n)     ty(1)     ty(2)  ... ty(n);
%                                 a11(1) a11(2) ...a11(n)    a21(1) a21(2) ...a21(n);
%                                 a12(1) a12(2) ...a12(n)    a22(1) a22(2) ...a22(n)];
% * size: (1024x3).(3xnx2)=(1024xnx2) --> (32x32xnx2)

wimg = squeeze(interp2(img, pos(:,:,:,1), pos(:,:,:,2)));
% size(wimg)=32x32
% interp2(z,x1,y1): bilinear interpolation for the values of the
%    underlying 2-D function z at points in matrices x1 and y1.
                                %%pos(:,:,:,1)    :   x麟깃앤黎
                                %%pos(:,:,:,2)    :  y麟깃앤黎
wimg(find(isnan(wimg))) = 0;    %%nan인 값을 찾아 0으로 만들어 줌
%ISNAN  True for Not-a-Number.
%    ISNAN(X) returns an array that contains 1's where
%    the elements of X are NaN's and 0's where they are not.
%    For example, ISNAN([pi NaN Inf -Inf]) is [0 1 0 0].

%   B = SQUEEZE(A) returns an array B with the same elements as
%   A but with all the singleton dimensions removed.  A singleton
%   is a dimension such that size(A,dim)==1;

2013년 11월 22일 금요일

Particle filter에 의한 영역 추적

연속 이미지에서 미리 설정해준 물체 영역(patch)을 particle filters에 의해 추적한다.  이 때, 파티클의 발생 방법에 대해 알아 본다.

먼저 사용자가 영상 내에서 물체 영역을 설정한다. 구체적으로 예를 들어 보면,

                                 (figure from [2])
-image size: 352(가로)x288(세로)
-red window 중심 위치, 크기:  (177(col_center) 147(row_center)), [115(col_length)x 145(row_length)]

(1) 처음 사용자가 설정해 준 영역은 추적 대상이 된다.  현재 설정 영역의 크기는 너무 크므로 가로,세로 폭을 줄여 32x32크기로 만든다. 이를 templates로 한다.

(2) 목표 물체는 3차원 운동을 할 수 있지만 이미지에 맺히는 2D 운동은 affine motion이라 가정한다. 물체의 2d운동을 표현하기 위해 geometric affine parameter를 설정한다.

% 추적 사각영역의 상태변수:
% col-center, row-center, 수직 스케일, 회전각 theta, 가로세로비, 각도 파이
% state=(tx, ty, s1, theta, s2/s1, phi)
geo_param = [177, 147, 115/32, 0, 145/115, 0]; % geometric affine 인자

% 가중치를 가진 particle들을 발생시켜 보자
n =  600;  % 샘플의 갯수는 600개로 한다.
N = 1024;  % 32x32 템플릿을 1차원 벡터로 표현하면 32x32=1024이다.

params = repmat(geo_param, [1,n]);  % geo affine param을 600개 복사. 6x600행렬 생성
randMatrix = randn(6,n); % 6x600개 정규 분포의 행렬 생성,
          % 정규 분포이니 평균은 0이다: mean(randMatrix,2)=(0.023 0.042 ...-0.036)

% affsig = [4 4 0.02 0.02 0.005 0.001]: 즉, center 위치 변화는 크다.
% 나머지 인자는 약간 변화한다 가정
params = params + randMatrix.*repmat(affsig(:),[1,n]); % 600개의 parameters생성

% 입력 영상을 600개의 affine 인자에 따라 변형 시킴. 즉, 입력 frame을 변형 시킨다.
% 출력은 32x32 크기의 템플릿 600개
wimgs = warpimg(frame, affparam2mat(params), [32,32]);

% template에서 600개 각각을 빼서 잔차 이미지를 구한다.
% template이미지는 기준영상으로 첫번째영상에서 물체
% 이미지, PCA영상, 모델 영상 등이다.
diff = repmat(template(:),[1,n]) - reshape(wimgs,[N,n]);

% 잔차 값을 이용하여 confidence를 계산
confidence = exp(-sum(diff.^2)./condenssig)'; %condenssig=0.25(잔차 분산 값)

% confidence를 확률 분포(pdf)로 만들기 위해 정규화한다.
confidence  = confidence ./ sum(confidence);

% 확률 값이 가장 큰 후보를 선택
[maxprob, maxidx] = max(confidence); % maxprob=0.2233(130번째)

% 이 샘플에 대한 affine para 값을 저장
affine_est = affparam2mat(params(:,maxidx)); %[a11 a12 tx; a21 a22 ty]

% 최적 이미지도 저장한다
timgs = [timgs wimgs(:,:,maxidx)];



참고 문헌

[1] D.A. Ross, J. Lim, et al., Incremental Learning for Robust Visual Tracking
[2] Dong Wang et. al., Online Object Tracking with sparse prototypes


2013년 11월 19일 화요일

Affine transformation

Affine 변환은 위치 이동과 선형변환(linear transformation)의 결합이다.

(x' y' 1)' = [a11 a12 tx; a21 a22 ty; 0 0 1].(x y 1)'

로 표현된다.  행렬로 더 축약해서 표현하면

x' = H.x = [A t; 0' 1].x

이다. 여기서 행렬 A는 2x2 크기의 비 특이(non-singular) 행렬이다.  평면상에서 일어나는 affine 변환은 6자유도를 가진다 (행렬 내에 6개의 미지수가 있다).  만일 3개의 대응점이 있다면 하나의 대응점이 2개의 식을 주므로 affine변환의 6개 인자 결정이 가능하다.

선형 변환 행렬 A는 2개의 기하 변환으로 설명할 수 있다.

(1) 회전
(2) 비 등방성(non-isotropic) 크기변화

아래 그림은 강체 회전과 shearing 변형의 2가지 기하 변환을 보여준다.



기하 변환의 값들은 2x2 크기의 A행렬을 특이값 분해하면 얻을 수 있다:



(예1) 파이 각 적용 여부에 따른 차이 점

>> clear all
>> fi=30*pi/180; % phi을 30도로
>> th=60*pi/180; % theta를 60도로
>>
>> Rf=[cos(fi) -sin(fi); sin(fi) cos(fi)];
>> Rt=[cos(th) -sin(th); sin(th) cos(th)];
>> D=[1.5 0; 0 1.0];
>>
>> A=Rt*Rf'*D*Rf
>> [u,d,v]=svd(A);
>> % d는 D이다. Rt==uv', Rf=v'이다.
>>
>> % 실제 변형을 테스트 해보자.
     % (아래 그림에서 원형점(정사각형))
>> pts=[1 1 -1 -1; 1 -1 -1 1];
>> pts =
     1     1    -1    -1
     1    -1    -1     1
>> D*pts =
    1.5000    1.5000   -1.5000   -1.5000
    1.0000   -1.0000   -1.0000    1.0000
    % shearing 변형 없이 스케일링만 일어남 (아래 그림에서 삼각점)

>> Rf'*D*Rf*pts
    1.1585    1.5915   -1.1585   -1.5915
    0.9085   -1.3415   -0.9085    1.3415
    % shearing 변형이 일어남 (아래 그림에서 사각점)






(예2) tracking에 적용하기 위한 geometric parameter로 변환.

영상에서 물체를 추적할 때 보통 물체 영역을 둘러싸는 작은 사각의 윈도(window patch)를 가정한다.
물체가 크기 변화, 회전, 이동 할 때, 이에 따라 윈도 영역도 크기변화, 회전, 이동해야 한다. 이러한 기하학적 변화를 나타내는 parameter를 affine 변환에서 유도한다.

즉, 일반적으로 알고 있는 affine 변환의 6개의 parameter를 geometric affine 인자로 변환하는 matlab코드는 아래와 같다. Geometric parameter 6개는
(x, y, scale, th, aspect, skew) 이다.
여기서, (x,y)는 윈도의 중심 위치, scale은 수직방향 스케일, th는 회전 각, aspect는 수직-수평 비, skew는 파이 각을 나타낸다.

이러한 변환을 통해 추적되는 물체의 상태 변수(state variable)는 물체를 둘러싸는 윈도의 상태를 나타내는 6개의 geometric parameter가 된다.

function q = affparam2geom(p)
% function q = affparam2geom(p)
%
%   입력  : p,2x3의 affine 계수;
%   출력  : q,geometric affine 계수로 각도 스케일비 등을 나타냄;
% The functions affparam2geom and affparam2mat convert a 'geometric'
% affine parameter to/from a matrix form (2x3 matrix).
%
% affparam2geom converts a 2x3 matrix to 6 affine parameters
% (x, y, scale, th, aspect, skew), and affparam2mat does the inverse.
%
%    p(6) : [p(1) p(3) p(4); p(2) p(5) p(6)]
%
%           x'              p(3)   p(4)   p(1)           x
%           y'      =       p(5)   p(6)   p(2)     *     y
%           1                 0        0        1            1
%
%                           p(3)   p(4)
%           A       =      
%                           p(5)   p(6)
%
%    q(6) : [dx dy sc th sr phi]
%           dx,dy   :   left,top의 원점을 기준으로 box의 중심 위치 표현
%           sc,sr   :   ramda1(수직방향으로 스케일), ramda2/ramda1 (길이 비율)
%                       수직 방향 스케일은 box크기가 32이므로 32의 배수로 주어짐
%           th      :  각도 theta
%           phi     :  각도 phi
%
% Reference "Multiple View Geometry in Computer Vision" by Richard
% Hartley and Andrew Zisserman.
% 출력은 [tx, ty, ramda1, theta, ramda2/ramda1, phi]
% MVG 책의 39~40페이지에 설명

% Copyright (C) Jongwoo Lim and David Ross.  All rights reserved.

A = [ p(3), p(4); p(5), p(6) ]; % A=[3.594 0; 0 4.531]: y(col)크기가 더 큼
%%  A = USV' = (UV')(VSV') = R(th)R(-phi)SR(phi)

[U,S,V] = svd(A);
% (Ex.) 축의 순서 결정. For example,
% S=[4.53 0; 0 3.59]; U=[0 1; 1 0];
% 영상내 설정은 x축(col), y축(row) 순서임. Row가 더 크니
% U가 (0 1)', (1 0)' 벡터의 순서로 나옴(즉, y축이 먼저 나옴)
% 따라서, x축이 우선되게 축 순서 조정 필요

if (det(U) < 0) % 항상 x축이 우선되게 하기 위함
  U = U(:,2:-1:1);  V = V(:,2:-1:1); % 2열을 1열로
  S = S(2:-1:1,2:-1:1); % 2행을 1행으로, 2열을 1열로
  % U=[1 0; 0 1], S=[3.59 0; 0 4.53]로 수정 됨
end

%%*******중심 위치*******%%
q(1) = p(1);
q(2) = p(2);
%%*******(col, row)*******%%

% [cos(th) -sin(th); sin(th) cos(th)]=uv'
%   =[u11 u12; u21 u22][v11 v21; v12 v22]
%   =[u11.v11+u12.v21 ...; u21.v11+u22.v12 ...]-->
q(4) = atan2(U(2,1)*V(1,1)+U(2,2)*V(1,2), U(1,1)*V(1,1)+U(1,2)*V(1,2)); % theta


phi = atan2(V(1,2),V(1,1)); % angle phi
if (phi <= -pi/2) % phi가 -90도 이하면 그냥 -90도로
  c = cos(-pi/2); s = sin(-pi/2);
  R = [c -s; s c];  V = V * R;  S = R'*S*R;
end
if (phi >= pi/2) % phi가 90도 이상이면 그냥 90도로 둠
  c = cos(pi/2); s = sin(pi/2);
  R = [c -s; s c];  V = V * R;  S = R'*S*R;
end

%%*******크기비율*******%%
q(3) = S(1,1); % ramda1
q(5) = S(2,2)/S(1,1); % ramda2/ramda1
%%*******각도파이*******%%
q(6) = atan2(V(1,2),V(1,1)); % phi

q = reshape(q, size(p));
% 출력은 [tx, ty, ramda1, theta, ramda2/ramda1, phi]




(예3) Geometric affine parameters를 2x3크기의 affine 행렬로 변환하는 코드

function q = affparam2mat(p)
% function q = affparam2mat(p)
%
% The functions affparam2geom and affparam2mat convert a 'geometric'
% affine parameter to/from a matrix form (2x3 matrix).
%
%   입력  : q,기하학적 affine 계수;
%   출력  : p,2x3행렬에서의 affine 계수;
%
% affparam2geom converts a 2x3 matrix to 6 affine parameters
% (x, y, th, scale, aspect, skew), and affparam2mat does the inverse.
%
%    p(6,n) : [dx dy sc th sr phi]'
%    q(6,n) : [q(1) q(3) q(4); q(2) q(5) q(6)]
%
% Reference "Multiple View Geometry in Computer Vision" by Richard
% Hartley and Andrew Zisserman.
%
% Copyright (C) Jongwoo Lim and David Ross.  All rights reserved.


sz = size(p); % size(p)=1x6
if (length(p(:)) == 6) % p(:)= (177.0000; 147.0000; 3.5938; 0; 1.2609; 0)
  p = p(:);            % length(p(:))=6
                       % p = (177.0000; 147.0000; 3.5938; 0; 1.2609; 0)
end
s = p(3,:);  th = p(4,:);  r = p(5,:);  phi = p(6,:);
cth = cos(th);  sth = sin(th);  cph = cos(phi);  sph = sin(phi);
ccc = cth.*cph.*cph;  ccs = cth.*cph.*sph;  css = cth.*sph.*sph;
scc = sth.*cph.*cph;  scs = sth.*cph.*sph;  sss = sth.*sph.*sph;
q(1,:) = p(1,:);  q(2,:) = p(2,:);
q(3,:) = s.*(ccc +scs +r.*(css -scs));  q(4,:) = s.*(r.*(ccs -scc) -ccs -sss);
q(5,:) = s.*(scc -ccs +r.*(ccs +sss));  q(6,:) = s.*(r.*(ccc +scs) -scs +css);
q = reshape(q, sz);





참고 문헌

[1] Hartley and Zisserman, Multiple View Geometry, Cambridge press



2013년 11월 9일 토요일

차원 축소(dimensionality reduction)

크기가 32x32인 얼굴 영상이 50장 있다.  한장의 영상은 픽셀이 1024개가 있는 하나의 벡터이다.
따라서 1024개의 벡터가 50개 이다.  즉, 행렬 A의 크기는 1024x50이다. 

각각의 벡터는 1024차원에서 하나의 점이다.  50개가 있으므로 1024차원의 공간에서 50개의 점을 정의한다. 

점 하나에 1024개의 좌표가 필요하다. 점 표현을 위해 사용되는 주축이 1024개이기 때문이다. 


데이터를 압축해서 표현하기 위해 주축의 수를 줄여본다. 

50개 점의 분포, 즉 분산이 가장 큰 축을 몇 개  찾으면 된다.  분산이 큰 방향이 데이터의 변량을 잘 표현하는 방향이다.
5개을 찾아 보자. 

데이터는 크기가 1024x50인 행렬이다.  먼저 평균을 구하자.  즉, 데이터의 중심점을 지나는 주축을 구할 것이다.

mu = mean(data,2); 

각 데이터에서 평균을 제거하자. 

data = data-repmat(mu, [1,50]);

data를 특이값 분해한다. 

[u,d,v] = svd(data); % data=udv'

d 행렬은 특이값이 들어 있는 대각 행렬이다. 
u 행렬의 1~5열을 취한다. 

u1=u(:,1:5); 



주축 5개를 구했으므로 첫번째 데이터를 새 축에서 표시해 보자. 

c1=u1'*data(:,1); % 5x1=(5x1024).(1024x1)

5개의 값이 나오는데 이는 5개의 주축에서 좌표 값이다. 
즉, 데이터의 표현이 1024개에서 5개로 줄었다.   

이제 5개의 좌표 값 만으로 원 데이터를 재생해보자.  

o1=c1(1)*u1(:,1)+c1(2)*u1(:,2)+...+c1(5)*u1(:,5)

이다. matlab 명령으로

o1 = u1*c1; % 1024x1=(1024x5).(5x1).  o1=u1*c1=u1*u1'*data(:,1)

이다. 원 데이터와 재생 데이터의 차이는 

res1=data(:,1)-o1;

이다.



모든 데이터를 새 축에서 표시해 보자.

c = u1'*data;  % (5x50) = (5x1024).(1024x50)
o = u1*c; % (1024x50) = (1024x5).(5x50)
res = data-o; % (1024x50)-(1024x50)



행렬 c는 [5x50]으로,  50장의 영상을 각기 5개의 계수치로 표현한 것이다.

mean(c,2)를 통해 5개 계수치의 평균을 구해서 m2에 저장한다.
어떤 새로운 이미지 t1를 템플릿과 비교할 때는 c2=u1'*t1으로 5개의 계수를 구하고 norm(m2-c2)로 거리를 계산하면 된다.

 



Sequential KL 변환

영상 내에 있는 특정 물체(예를 들면 얼굴)를 추적 한다고 하자. 이 때, 물체를 표현하기 위해 여러 개의 영상 템플릿을 사용하는 PCA(principal component analysis)을 적용할 수 있다.

물체의 외관은 추적 동안 여러가지 원인으로 크게 변한다. PCA 기법을 통해 물체를 추적할 때, 물체를 표현하는 주축(principal axis)을 효과적으로 갱신하는 것이 필요하다.

연속 영상에서 물체 추적동안 새로 얻어지는 프레임들을 고려하여 주축을 갱신할 필요가 있을 때 sequential KL 알고리즘을 사용할 수 있다. (Sequential PCA 또는 Sequential visual tracking으로 부를 수도 있다.)


skl 변환은 sequential kl 변환이다.  연속 신호에서 데이터가 차례로 도착한 것을 처리하거나, 큰 행렬의 SVD를 계산해야 할 때, 큰 행렬을 작은 행렬로 분할하여 여러번 반복 처리할 때 사용한다.

예를 들면, A'=[A E] 행렬을 생각해 보자. A행렬은 10장의 영상 템플릿으로 이루어진 행렬이다. E행렬은 새로 매칭된 5장의 프레임에서 추출된 5장의 영상 템플릿으로 이루어진 행렬이다.
이 때, 이용할 수 있는 템플릿이 모두 15개가 되었으므로, 이것 모두가 포함된 A' 행렬에 대해 새로 주축을 구하는 것이 필요하다. 그런데, A행렬에 대해서는 특이값 분해를 통해 이미 구해 놓은 주축이 있다고 가정하자.
효율적 계산을 위해서는 A'행렬을 다시 특이값 분해를 하는 일 없이, 새롭게 추가된 E행렬에 대해서만 특이값 분해를 하고, 그 결과를 A행렬에 대한 특이값 분해의 결과와 결합한다. 이렇게 결합된 결과가 A'행렬에 대한 특이값 분해의 값과 동일하도록 만드는 일이 SKL이다.    

R-SVD[2]는 A의 분해에 기반하여 효과적으로 행렬 A'의 분해 A' = [A|E] = U'D'V''를 계산할 수 있다.  [U,D,V]=svd(A)이라고 가정하자.  이 때, A'의 특이값 분해는


과 같이 구해진다.  이 알고리즘을 해석해 보자.





MxL크기의 행렬 B가 있다.  특이값 분해하면

B = UDV'

이다.  U는 왼쪽 특이 벡터들로 구성된 MxL크기의 직교(orthonormal) 행렬이다. D는 LxL 크기의 행렬이다. 대각요소가 B행렬의 특이 값이다.
V는 각 열이 오른쪽 특이 벡터인 LxL의 직교 행렬이다.


이 때, 분해해야 할 더 큰 행렬 B*가

B*=(B|E)

로 주어 졌다.
E는 P개의 추가 (이미지)데이터가 있는 MxP 크기의 행렬이다.  B*의 특이값 분해를 수행하자.

(Step 1) 행렬 (U|E)에 직교화(orthonormalization) 과정(주3)을 수행한다.  직교 행렬 Ua = (U|Et)를 만든다. E에서 Et를 구하기 위해 QR분해[1]를 이용한다.    (참고: 표기에서 Et(E tilt)는 E'(transpose)가 아님. 직교 행렬임)

(Step 2) (L+P)x(L+P)크기의 Va행렬을 만든다.


Ip는 PxP의 단위 행렬이다. Va는 직교 행렬이다.

(Step 3) B*=Ua.Da.Va' 이므로, Da = Ua'.B*.Va 이다. 대입하면


이다.
Et'.B.V = 0(주1)이고, U'.B.V=D이다. 따라서


이다. Da는 D 행렬에 오른쪽 P개의 열이 추가된 새로운 행렬이다.

Da 행렬의 각 요소에 대해 살펴 보자.

.D는 기저 U로 표현 했을 때의 B 행렬에 대한 좌표 값이다.
.U'E는 새 데이터 E가 U기저에 투영된 좌표이다.  즉, U기저에서 E의 표현이다.
.Et'E는 새 데이터가 Et 기저에 투영된 좌표이다. 즉, Et기저에서 E의 표현이다.
즉, 새로 추가된 데이터를 새로 확장된 기저 (U|Et)에 대해 표현한 좌표 값이 (U'E; Et'E)이다.  이를 다시 쓰면 (U'; Et').E이다.

대각요소가 아닌 요소들이 있으므로 Da를 SVD하자.

Da = Ub.Db.Vb'

이고, B*의 SVD는

B* = Ua.Da.Va'= Ua.(Ub.Db.Vb').Va' = (Ua.Ub).Db.(Va.Vb)'

이다.
여기서, Db는 (L+P)x(L+P)의 대각 형렬이다. (Ua.Ub)는 Mx(L+P)의 column-orthonormal 행렬이고, (Va.Vb)는 (L+P)x(L+P)크기의 orthonormal 행렬이다.

상기한 바와 같이 B*의 SVD는 Ua, Da, Va의 계산과 작은 크기인 Da행렬의 SVD만을 요구한다.  Ua, Da, Va의 계산은 B행렬의 SVD에서 얻어진 데이터를 사용한다.



(예1) 간단한 행렬에서 테스트

>> clear; clc;
>> A = rand(10,5); % 행렬 A를 10x5크기로 생성(old 데이터로 가정)
>> B = rand(10,4); % 행렬 B를 생성 (new 데이터로 가정)

>> [u0,d0,v0] = svd([A B]); % 두 행렬의 결합 확장 행렬의 특이값 분해
     % 기존 데이터와 새 데이터의 모든 데이터가 결합된 행렬의 기저벡터를 얻을 수 있음
     % A, B가 합해진 전체 데이터이고, 이에 대한 u0, d0가 필요.
     % 그런데, 비디오처리를 할 경우, 계속 새 영상
     % 데이터가 입력된다고 보면, [A B C ...]로 행렬 계속 커짐
     % 큰 행렬의 svd는 계산량, 메모리 문제가 있음


%*** (1) skl 변환 [2]
%     원래의 고전적 방법
>> [ua,da,va]=svd(A); % A를 특이값 분해 (기존 데이터)
>> [q,r]=qr([ua*da B]); % new 데이터 B의 직교벡터 추출
     % q행렬 내에는 직교벡터 ua 5개와 B의 직교벡터 4개가 얻어짐
     % A대신 직교행렬과 특이행렬의 곱 ua*da 넣음
>> [u1,d1,v1]=svd(r); % q*r = q*u1*d1*v1'이므로
     % *** u0 == q*u1, d0 == d1 ***
     % A에서 ua, da만 사용했으므로 q*r는 [A B]가 아님

>> ua=q*u1; % 다음 단계를 위해 ua 갱신
>> da=d1; % 다음 단계를 위해 da 갱신
     % 즉 기존 데이터의 u,d만 유지하면 새 데이터가 입력될 때 계산량, 메모리 문제 해결



%*** (2) 보다 개선된 방법
%  [ua*da B]를 qr분해하는 것은 비효율적
% (이미 ua는 직교행렬로 분해되어 있기 때문)
% 따라서 추가되는 B만 qr분해 하면 됨
>> o1=B-ua*ua'*B; % B를 ua기저에 사영하고, 기저 ua로 표현되지 않는 B의 요소 추출(주4)
>> [q1,r1]=qr(o1); % 잔차를 가지고 새로운 직교벡터 q1을 얻음
>> rr=[da   ua'*B; zeros(10,5)   q1*o1];
     % ua'*B: B를 ua기저에서 표현, q1*o1: 잔차의 q1기저 표현
>> [u2,d2,v2]=svd(rr); % rr(20x20)
>> uu = [ua q1]*u2; % uu=10x20. 결합 데이터의 기저
>> dd = d2;  % u2=20x20. 결합 데이터의 특이값
>> ua = uu(:,1:10); % u0와 같음
>> da = dd(1:10,1:9); % d0와 같음





위 알고리즘은 새로운 데이터가 도착해서 이용가능한 데이터가 늘어났을 때, 기존 행렬과 새로 추가되는 행렬 모두에 대해 zero mean을 가정한다. 즉, 평균 값의 변화를 고려하지 않았다.   따라서 sample mean의 변화를 고려하면서 주축을 갱신하는 것이 필요하다.

다시 말하면, C=[A B]행렬의 특이 값 분해를 할 때, C행렬에 대해 C의 평균을 제거한 후, 특이값 분해를 수행해야 한다.  A 및 B행렬의 특이 값 분해도 마찬가지이다. 그런데, A행렬, B행렬의 평균은 모두 C행렬의 평균과 다르며 제 각각이다.  즉, 평균은 항상 달라진다. 이를 고려하여 특이값 분해를 할 필요가 있다.


%*** (3) 평균 변화를 고려한 방법 [3]
%   평균 변화를 고려한 방법. 새로운 데이터가 추가되면 (즉, 기존 A
%   행렬에 B행렬이 추가되어 C행렬이 되었다면
%   A평균, B평균, C평균 값이 다 다르다) 평균도 달라지므로 이를
%   고려해야 한다 [3].
>> C = [A B];
>> n = size(A,2); m = size(B,2);
>> ma = mean(A,2); mb=mean(B,2);
>> mc = n*ma/(n+m) + m*mb/(n+m);
>> Ma = repmat(ma,[1,5]);
>> Mb = repmat(mb,[1,4]);
>> Mc = repmat(mc,[1,9]);
>> Am = A-Ma; % A 행렬을 zero-mean으로
>> Bm = B-Mb; % B            "
>> Cm = C-Mc; % C            "
>>
>> [u0,d0,v0]=svd(Cm); % 목표값(true).
                            % 즉, Am, Bm에 skl 적용으로 u0, d0를 구해야 함.


참고문헌 [3]은 평균변화를 고려한 Sequential KL변환에 대해 잘 설명하고 있다.  참고문헌에서 scatter matrix Sc가 나오는데 covariance matrix와 다음의 관계가 있다:

Sc = (n+m).cov(C);
cov(C) = Sc/(n+m);
cov(C) = CC'=(UDV')(VDU')=U(D^2)U';

따라서 C행렬의 scatter 행렬 Sc의 svd를 구하는 것은 어떤 행렬 C의 U와 D^2을 구하는 것과 같다.


그런데, 참고문헌 [3]의 appendix에 따르면 평균이 제거된 C행렬의 scatter행렬은

Sc = Sa+Sb+ sqrt(.)(Ib-Ia)
   = [(A-Ia) (B-Ib) sqrt(.)(Ib-Ia)] [(A-Ia) (B-Ib) sqrt(.)(Ib-Ia)]'
   = Bt.Bt';

임이 증명되어 있다.

즉, C의 제곱(C.C')이 행렬 Bt의 제곱으로 이루어져 있다.  따라서 C의 svd는 Bt행렬의 svd로 구하면 된다.  Bt 행렬은 (A-Ia)부분과 [(B-Ib) sqrt(.)(Ib-Ia)]의 두 부분의 결합으로 이루어져 있으며, skl을 적용할 수 있다. 즉, (A-Ia)의 svd 결과와 추가되는 [B-Ib sqrt(.)(.)]행렬의 svd를 결합한다.


>> [ua,da,va]=svd(Am);
>> v1 = sqrt((n*m)/(n+m))*(mb-ma);
>> Bh = [Bm v1];
>> o1 = Bh-ua*ua'*Bh; % Bh를 기저 ua로 표현 후의 잔차
>> [q1,r1]=qr(o1); % 잔차에서 새로운 기저 추출
>> rr = [da   ua'*Bh; zeros(10,5)   q1*o1];
>> [u2,d2,v2]=svd(rr);
>> dd = d2;
>> uu = [ua q1]*u2;

% C는 열이 9개이나 d2의 의미 있는(0이 아닌) 특이값이 9개가 안되는 경우
% 이 경우는 8개만 나옴
% uu의 1~8열까지만 유의미 함
>> dd = diag(dd);
>> cutoff = sum(dd.^2)*1e-6; % 임계치 정의
>> keep = find(dd.^2>=cutoff);
>> da = dd(:,keep);
>> ua = uu(:,keep);




(주1) Et'BV = Et'(UDV')V = (Et'U)D(V'V) = (0)D=0
(주2) SVD(X,0) 명령은 SVD(X)보다 더 작은 크기의 U, D, V행렬을 만든다.  만일 크기 mxn의 X 행렬에서 m>n이면 U의 첫번째 n열만 계산한다.  S의 크기는 nxn이다.   만일 m<=n이면 SVD(X,0)는 SVD(X)와 같다.
(주3) [U|E]행렬을 직교화해야 한다. U는 이미 직교행렬이다. E는 새로 추가된 행렬이고 직교행렬이 아니다.  직교화를 위해 qr분해를 이용하는데, qr분해는 기존 벡터들에 수직한 새로운 벡터를 추가해 나가는 방식으로 직교 벡터를 만들어 간다.  svd와 qr분해에서 만들어내는 직교 벡터들 사이의 관계를 통해 이해한다 (보충 설명 필요).
(주4) o1=B-ua*ua'*B:  기저 ua로 표현되지 않는 B의 요소 추출한다는 의미를 살펴보자. svd를 통한 행렬의 주축은 데이터의 산포(scatter)가 큰 몇 개의 축을 선택한다는 의미이다. 이 축들의 아닌 방향으로는 데이터의 산포가 없다는 의미이다.  그런데, 새로운 데이터 B는 기존 주축으로 표현이 되는 데이터도 있고 그러지 않은 데이터도 있을 것이다. 따라서, 기저 ua를 따르지 않는 데이터는 이를 표현하기 위한 새로운 주축이 필요하다.  즉, 잔차 o1에 대한 주축을 새로 선정하면 된다.  



[1] QR분해: A행렬을 QR 분해하면 각 열이 서로 수직이고 열벡터의 크기가 1인 직교(orthonormal) Q행렬과 상삼각행렬(upper triangular matrix) R의 곱으로 분해 할 수 있다. 즉, A=Q.R을 얻는다.
[2] A. Levy and M. Lindenbaum, Sequential Karhunen-Loeve Basis Extraction and its application to Images, IEEE Trans. Image Processing 9(8), 2000.
[3] D.A. Ross, J. Lim, et al., Incremental Learning for Robust Visual Tracking

KL 변환

먼저 차원축소 부분을 읽기 바란다.

Karhunen-Loeve (KL) transform으로 불린다. 저 차원의 부분 공간으로 아주 큰 영상이나 벡터의 집합을 근사하는 방법이다.

mxn 크기의 2차원 배열로 주어지는 영상은 M(=mxn) 크기의 벡터 하나로 바꿀 수 있다. 만일 영상이 N개가 있다면, 전체 데이터의 크기는 MxN이다.
MxN 데이터에 대해 기저를 찾아보자.

일반적으로 MxN 벡터 집합에 대한 KL 기저(basis)를 계산하는 것은 O(MN^2)의 연산과 O(MN)의 메모리를 요구한다.  이러한 계산량은 데이터의 실시간 처리를 위해서는 상당히 크다.


KL 변환: N개의 (images) 벡터 (Ai),i=1...N가 주어질 때, K (K<N)개의 직교(orthonomal) 기저벡터의 집합을 찾는 것이다. 단, 기저 Uj에 의해 확장(span)된 공간에 사영(projection)된 원 데이터의 좌표로 재생한 데이터는 원 데이터를 잘 근사해야 한다.

행렬 A는 크기가 MxN (M>>N)이다.
A의 특이값 분해(SVD: Singular Value Decomposition)를 이용하여 기저벡터를 얻는다.  이때, KL 기저는 (특이값이 0이 되지 않는) K개의 왼쪽 특이 벡터(U의 첫번째 K개의 열)이다.

R-SVM[1]은 SVD를 수정한 것으로 M>>N일 때 효과적이다:

(1) A = QR: qr분해를 통해 (열)직교(column-orthonormal) Q(MxN) 행렬, 상 삼각 행렬 R(NxN)을 얻는다. 계산량은 4MN^2이다.
(2) R = Ua.Da.Va': 표준 SVD알고리즘으로 R을 특이값 분해 한다. 계산량은 O(N^3)이다.
(3) U = Q.Ua, 계산량은 2MN^2이다.

정리해서 다시 쓰면,

A = QR = Q(Ua.Da.Va') = (Q.Ua).Da.Va' = UDV'

이다. 따라서, U = Q.Ua이다.

계산량을 살펴보면 (1)과 (3)이 6MN^2이고, (2)가 N^3이다. 즉 (1),(3)번이 좌우하고 (2)는 무시할 만하다.


(예1) 간단하게 테스트해 보자.

>> clear; clc;
>> A = rand(10,9); % 행렬 A를 10x9크기로 생성
>> [u0,d0,v0] = svd(A); % 행렬의 특이값 분해
>>
>> [q,r] = qr(A); % A 행렬의 QR 분해
>> [u1,d1,v1] = svd(r); % r의 특이값 분해
>> q*u1 % u0와 같음, 즉, u0.d0.v0' = (q*u1).d1.v1'이다.
>> d1 % d0와 같음


[1] G. Golub and C. Van Loan, Matrix Computation. Johns Hopkins Univ. Press, 1992.