만일 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) 해야 함.
단, 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
댓글 없음:
댓글 쓰기