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.