NetVLAD: CNN architecture for weakly supervised place recognition[2]

이전 포스팅에서 이어집니다.

 

지난번 포스팅에서 visual place recognition문제를 image retrieval로 정의하였고 이를 위해서 VLAD가 local image descriptor를 image representation 벡터로 pooling 하는 방법을 수식을 통해서 알아보았습니다.

 

VLAD image representation 벡터 $V$는 다음과 같은 식으로 계산할수 있었습니다.

 

$V(k) = \sum_{i=1}^{N}a_k({\bf{x_i}})(x_i - c_k)$

 

위의 식을 신경망이 backpropagation방식으로 학습하기 위해서는 해결해야 할 문제가 있습니다. backpropagation 방식의 학습은 신경망의 각 노드가 결과에 얼마큼의 영향을 끼쳤는지 그 기여도를 미분을 통해서 계산합니다. 따라서 학습하고자 하는 식이 미분이 가능하여야 합니다(differentiable). 하지만 벡터 $V$를 계산하는 식은 $a_k({\bf {x_i}})$의 정의로 인해 미분이 불가능합니다. 논문에서는 이를 hard assignment라고 부르고  식을 differentiable(미분 가능)하게 바꾸고자 $a_k({\bf {x_i}})$를 다음처럼 다시 정의합니다.

 

$\Large\bar {a}_k({\bf {x}}_i) = {e^{-\alpha\|{\bf {x}}_i - c_k\|^2}\over\sum_{k\prime} e^{-\alpha\|{\bf {x}}_i - c_k\prime\|^2}}$

 

식을 분해해서 하나씩 살펴보면서 무슨 의미인지 알아보겠습니다. 먼저 $\|{\bf{x}}_i - c_k\|^2$는 $i$번째 local image descriptor와 $k$번째 cluster centre 간의 거리를 의미합니다. 따라서 ${\bf {x}}_i$와 $c_k$간의 거리가 짧으면 분자 부분 $e^{-\alpha\|{\bf {x}}_i - c_k\|^2}$ 의 크기가 커지고 거리가 길어지면 $e^{-\alpha\|{\bf {x}}_i - c_k\|^2}$의 크기가 작아짐을 알 수 있습니다. 그리고 $\|{\bf {x}}_i - c_k\|^2$ 앞에 $-\alpha$가 곱해져 있습니다. 본문에서는 $\alpha$를 다음과 같이 설명합니다.

 

$\alpha$ is a parameter (positive constant) that controls the decay of the response with the magnitude of the distance.

 

해석해보면 거리의 크기에 따른 반응의 decay를 조절하기 위한 parameter입니다. $\alpha$가 커지면 커질수록 $\bar{a}_k({\bf{x}}_i)$는 original VLAD의 $a_k({\bf {x}}_i)$처럼 가장 가까운 cluster centre일 때는 1, 그렇지 않을 때는 0을 나타내게 됩니다.

 

그러면 $e^{-\alpha\|{\bf{x}}_i - c_k\|^2}$를 local image descriptor ${\bf {x}}_i$와 cluster centre $c_k$간의 거리에 따른 비율 $p_k$로 바꿔서 식을 표현할 수 있습니다.

 

$\Large\bar {a}_k({\bf {x}}_i) = {p_k \over {\sum_{k\prime} p_{k\prime}}}$

 

이렇게 바꾸어 놓고 보면 분모는 ${\bf{x}}_i$와 모든 $\{c_k\}$간의 거리에 따른 비율을 합산한 것이고 분자는 ${\bf {x}}_i$와 $c_k$간의 거리에 따른 비율입니다. 특정 요소의 값을 전체 요소를 다 더한 것으로 나눈 값은 전체 요소에서 특정 요소가 차지하는 비율입니다. 이렇게 출력을 0과 1 사이의 값으로 정규화하고 출력들의 총합이 1이 되는 함수를 softmax 함수라고 합니다. 수식으로는 다음과 같이 표현합니다.

 

$\Large \sigma_k({\bf{z}}) = { exp(z_k) \over \sum_{k\prime} exp(z_k\prime)}$

 

결국 이전의 식은 ${\bf{x}}_i$와 가장 가까운 cluster centre $c_k$간의 차이만을 고려하고 그보다 먼 cluster centre와의 차이는 고려하지 않고 pooling 했다면 바뀐 식은 거리에 따른 비율을 사용하여 가장 가까운 cluster centre 뿐만 아니라 그보다 먼 cluster centre 간의 차이도 버리지 않고 사용함으로써 hard assignment $a_k({\bf {x}}_i)$의 불연속성이 제거되어 벡터 $V$를 계산하는 식이  differentiable(미분 가능) 해집니다. 이렇게 불연속성이 제거된 $a_k({\bf {x}}_i)$를 soft-assignment라고 부릅니다.

 

이제 식이 differentiable해졌으니 신경망에 맞게 바꿔보겠습니다. 식 $\bar {a}_k({\bf {x}}_I)$를 전개한 뒤 분자와 분모를 $e^{-\alpha\|{\bf {x}}_i\|^2}$으로 나누고 $2\alpha c_k$를 $w_k$, $-\alpha\|c_k\|^2$를 $b_k$로 바꿉니다. 논문에서는 이를 decoupling이라고 하며 parameter가 $\{c_k\}$ 1개였던 것을 $\{w_k\}$, $\{b_k\}$, $\{c_k\}$ 3개로 늘렸습니다. 이를 통해서 original VLAD보다 높은 flexibility를 가지게 됩니다.

 

$\Large\bar {a}_k({\bf {x}}_i) = { e^{w_{k}^{T}{\bf {x}}_i + b_k} \over \sum_{k\prime} e^{w_{k\prime}^{T}{\bf {x}}_i + b_{k\prime}}}$

 

그리고 최종적으로 $\bar{a}_k({\bf{x}}_i)$를 대입해 NetVLAD 식을 완성합니다.

 

$\Large V(k) = \sum_{i=1}^{N}{ e^{w_{k}^{T}{\bf{x}}_i + b_k} \over \sum_{k\prime} e^{w_{k\prime}^{T}{\bf {x}}_i + b_{k\prime}}}(x_i - c_k)$

 

 

CNN architecture with the NetVLAD layer

 

구조를 그림으로 보면서 위에서 정리한 공식이 실제로 어떻게 적용되는지 보겠습니다.

 

먼저, 이미지를 입력으로 사용하여 convolution layer를 통해 $N \times D$ 크기의 local descriptor ${\bf{x}}$가 출력됩니다. 그림에서 빨간색으로 표시된 부분입니다.

그리고 convolution operation의 parameter $\{w_k\}$와 $\{b_k\}$를 이용하여 convolution 출력 $s_k({\bf{x}}_i) = w_{k}^{T}{\bf {x}}_i + b_k$를 계산할 수 있습니다. 그림에서 파란색으로 표시된 부분입니다.

그 뒤 $s_k({\bf{x}}_i)$를 softmax 함수 $\sigma_k$에 적용시켜 $\bar {a}_k({\bf {x}}_i)$를 계산합니다. 그림에서 초록색으로 표시된 부분입니다.

그리고 각각의 $(x_i - c_k)$와 곱하여 V를 구하고 normalization을 거쳐 최종 출력을 계산합니다. 그림에서 노란색과 보라색으로 표시된 부분입니다.

 

여기까지 저자들이 제안한 CNN architecture 그중에서도 NetVLAD layer가 local descriptor ${\bf{x}}$를 pooling 하는 방식을 수식을 통해 설명하였고 수식이 나타내는 의미를 알아보았습니다. 

---

Learning from Time Machine data

Learning from Time Machine data에서는 앞에서 제안한 CNN architecture를 어떻게 end-to-end 방식으로 학습하는지 설명합니다.

 

두 가지 challenge에 대해서 이야기합니다.

 

1. how to gather enough annotated training data
2. what is the appropriate loss for the place recognition task.

첫 번째는 학습에 사용할 많은 양의 annotate 데이터를 모을 것인가이고 두 번째는 학습에 사용할 적절한 loss는 무엇인가입니다.

첫 번째는 Google Street View Time Machine을 통해서 서로 다른 시간과 계절에 촬영된 같은 장소에 대한 데이터를 수집해서 해결하였고 두 번째는 weakly supervised triplet ranking loss라고 하는 loss 함수를 새롭게 설계하여 해결하였습니다.

 

Google Street View Time Mahince는 사진을 촬영한 순간의 GPS 정보를 가지고 있는 training 데이터 정도로 이해하고 loss 함수를 중점적으로 살펴보겠습니다.

 

이전 포스팅의 Method overview에서 제안한 CNN architecture를 학습시켜 함수 $f_\theta$로 사용하고 이미지를 representation 한다고 했습니다. 이러한 과정을 거쳐 이미지를 representation 한 목적은  query 이미지 $q$가 주어졌을 때 데이터베이스의 모든 이미지 $I_i$중에서 가장 비슷한 이미지$I_i*$를 찾기 위해서 $I_i$를 query 이미지 $q$와 가까운 순으로 순위를 매기는 것입니다. 다시 말해서 query 이미지 $q$와 가까운 이미지 $I_i*$ 사이의 Euclidean 거리 $d_\theta(q, I)$ 가 $I_i$의 다른 이미지들과의 거리보다 작아야 합니다. 이를 수식으로 나타내면 다음과 같습니다.

 

$d_\theta(q, I_i*) < d_\theta(q, I_i)$

 

위의 수식을 만족하기 위해 저자들은 ranking loss between training triplets $\{q, I_i*, I_i\}$를 loss 함수로 제안합니다.

loss 함수를 위해서 training 데이터를 다음처럼 tuple로 구성할 수 있습니다. $(q, \{p^{q}_{i}\}, \{n^{q}_{j}\})$ 여기서 $q$는 query 이미지이고 $\{p^{q}_{i}\}$는 potential posivite 이미지, $\{n^{q}_{j}\}$는 definite negative 이미지입니다. positive와 negative가 무엇을 의미할까요? Google Street View Time Machine 데이터는 아까 언급했듯이 GPS 정보를 가지고 있습니다. 이 GPS 정보를 이용하면 training 데이터의 사진을 촬영한 장소가 지리적으로 어디에 위치했는지를 알아낼 수 있습니다. 즉 training데이터를 query 이미지 $q$와 가까운 곳에서 찍힌 이미지 혹은 먼 곳에서 찍힌 이미지로 구분할 수 있고 가까운 곳의 이미지를 potential positive 이미지 먼 곳을 definite negative 이미지라고 합니다. 실험에서는 query 이미지로부터 10 meter 이내에서 찍힌 이미지를 potential positive로 사용하였고 25 meter 밖에서 찍힌 이미지를 defenite negative 이미지로 사용하였습니다.

 

이렇게 구성된 tuple $(q, \{p^{q}_{i}\}, \{n^{q}_{j}\})$의 potential positive 이미지 $\{p^{q}_{i}\}$ 중에서 query 이미지 $q$와 지리적으로 가장 가까운 이미지를 $p_{i*}^{q}$라고 하며 다음과 같은 수식으로 정의합니다.

 

$\Large p_{i*}^{q} = \underset {p_i^q}{argmin} \, d_\theta (q, p_i^q)$

 

위에서 정의한 tuple을 이용해서 학습 목적을 다시 한번 정리해보겠습니다. 결국 $f_\theta$는 query 이미지 $q$와 지리적으로 가장 가까운 이미지 $p_{i*}^q$를 $f_\theta$를 이용해 벡터로 representation 한 것들 $f(q)$, $f(p_{i*}^q)$ 사이의 거리 $d_\theta (q, p_{i*}^q)$가 query 이미지 $q$와 모든 negative 이미지 $n_j^q$를 $f_\theta$를 이용해 벡터로 representation 한 것들 $f(q)$, $f(n_j^q)$ 사이의 거리 $d_\theta ( q, n_j^q)$ 보다 작도록 계산해야 합니다.

이것을 수식으로 표현하면 다음과 같습니다.

 

$\Large d_\theta (q, p_{i*}^q) < d_\theta (q, n_j^q), \,\, \forall j$

 

이것을 기반으로 weakly supervised ranking loss $L_\theta$를 다음과 같이 정의합니다.

 

$L_\theta = \sum_j l(\underset {i}{min} \, d_\theta^2 (q, p_i^q) + m - d_\theta^2 (q, n_j^q) ) $ 

 

함수 $l$은 $l(x) = max(x, 0)$을 나타내고 $m$은 constant parameter로 margin을 뜻합니다. 수식의 의미를 알아보겠습니다.

$\underset {i}{min}\,d_\theta^2 (q, p_i^q )$는 query 이미지 $q$와 potential 이미지들간의 거리중 가장 짧은 거리이고 $d)\theta^2 (q, n_j^q )$는 query 이미지 $q$와 j번째 negative 이미지의 거리입니다. 따라서 $\underset{i}{min}\,d_\theta^2 (q, p_i^q) + m - d_\theta^2 (q, n_j^q )$는 query 이미지 $q$와 가장 가까운 potential 이미지 간의 거리와 margin을 더한 값이 query 이미지 $q$와 j번째 negative 이미지 사이의 거리보다 작을 경우 계산의 결과가 학습 목적에 부합하기 때문에 신경망을 update 할 필요가 없습니다. 따라서 함수 $l$에 의해 loss는 0이 되고, 이렇게 모든 $n_j^q$에 대해서 각각의 loss를 계산한 후 이를 모두 더하여 최종 loss를 계산합니다. 

 

함수 $f_\theta$의 parameter $\theta$, 즉 신경망의 노드의 parameter들은 Stochastic Gradient Dscent (SGD) 방식으로 학습합니다.

 

여기까지 본 논문에서 제안하는 CNN architecture with the NetVLAD layer의 문제정의, 문제를 해결하는 아이디어, 딥러닝 모델, 학습 데이터 그리고 학습 방법에 대해서 수식을 풀어서 수식이 갖는 의미를 알아보는 방식으로 논문을 읽었습니다.

 

training 데이터와 구현에 관한 자세한 부분은 생략하고 실험 결과와 간략한 결론으로 글을 마치겠습니다.

---

Result and discussion

 

각각의 test 데이터에 대해 여러 방식들을 조합한 결과를 그래프로 나타냈습니다.

 

Comparison of NetVLAD versus off-the-shelf networks and state-of-the-art

convolution layer는 추가 학습이 진행되지 않은 미리 학습된 AlexNet, VGG16, Places205가 사용되었고 pooling layer는 Max pooling과 VLAD를 사용한 비교군을 설정하였습니다.

 

차원 감소(Dimensionality reduction)

PCA(주성분 분석) whitening을 이용해서 VLAD의 출력을 $4096-D$ 차원으로 줄인 결과 full size의 벡터와 성능상 차이가 거의 없습니다.

 

장소 인식을 위한 end-to-end 학습의 장점(Benefits of end-to-end training for place recognition)

end-task 학습을 거치지 않은 off-the-shelf CNN들에 비해서 논문에서 제안한 모델이 더 뛰어난 성능을 보여줬습니다.

이를 통해 두 가지를 확인할 수 있습니다.

첫째, 논문에서 제안한 접근방법은 장소 인식을 위한 풍부하지만 간결한 image representation을 학습할 수 있습니다.

둘째, "off-the-shelf"라고 하는 미리 학습된 network를 사용하는 것은 널리 알려진 아이디어지만 이것은 장소 인식을 위한 end-task 학습을 거치지 않았기 때문에 차선책일 뿐입니다.

 

최신 기법과의 비교(Comparison with state-of-the-art)

magenta $-*-$로 표기된 논문에서 제안한 방식이  현재 가장 좋은 성능을 보여준 RootSIFT+VLAD+whitening 보다 더 좋은 성능을 보여줍니다.

 

VLAD vs Max

$f_{VLAD} (-o-)$와 $f_{max} (-{\bf {x}}-)$를 비교해보면 VLAD pooling이 Max Pooling에 비해 월등이 좋은 성능을 보입니다. 정답률을 기준으로 했을 때 비슷한 성능을 보이는 구간에서 VLAD pooling의 representation 벡터가 4배 적습니다.

 

어떤 layer를 학습해야 하나(Which layers should be trained?)

표는 부분 학습의 결과를 보여줍니다. 예를 들어 conv4의 경우, conv4 layer를 포함해 그 뒤쪽 layer들만 학습시키고 conv4 layer 앞쪽의 conv1, conv2, conv3 layer는 미리 학습된 그대로 사용한 결과입니다.

 

 

 

 

 

 

 

 

표에서도 볼 수 있듯이 성능의 가장 큰 변화는 NetVLAD layer를 학습시키는 것이지만 convolution layer를 학습시키면 추가적인 개선이 이루어집니다. conv1 layer에서 overfitting이 일어나 약간의 성능이 하락된 것을 볼 수 있습니다.

 

Time Machine 학습의 중요성(Importance of Time Machine Training)

Time Machine 데이터 없이도 학습이 되는지 확인하기 위해 query 이미지와 training 이미지가 같은 시간에 찍힌 데이터를 사용하여 학습한 결과 38.7%의 정확도를 보였고 Time Machine을 사용했을 경우에 68.5%의 정확도를 보였습니다. Time Machine 데이터는 네트워크가 일반화되지 않기 때문에 장소 인식 문제를 해결하는데 아주 중요한 역할을 합니다. 예를 들어서 차나 사람 같은 일시적인 object들은 장소를 인식하는 데에 불필요한 요소이지만 같은 시간에 찍힌 데이터의 경우 한자리에 주차된 차가 지속적으로 등장해, 네트워크가 장소를 인식하는데에 차가 중요한 역할을 할 가능성이 높아집니다.

 

질적 평가(Qualitative evaluation)

 

다음 그림은 입력 이미지에 따라 각각의 모델이 입력 이미지의 어떤 부분을 중요하다고 판단해서 학습을 했는지 heatmap으로 나타냅니다.

 

 

미리 학습된 AlexNet은 ImageNet 카테고리에 등장하는 12가지 볼 유형을 구분해야 하기 때문에 원형 모양과 같은 특정 모양에 중점을 둡니다. Place205는 특정 장소를 인식하는 것이 아니라 scene-level 카테고리를 인식하기 때문에 모든 패치에 대해서 반응이 없습니다. 반면에 논문에서 제안한 모델은 장소 인식에 혼란을 줄 수 있는 차나 사람 같은 요소들은 배제하고 건물의 표면이나 스카이라인 등에 중점을 둡니다.

---

Conclusions

본 논문에서는 Google Street View Time Machine 데이터셋과 weakly supervised learning을 사용한 end-to-end 방식으로 훈련된 새로운 CNN architecture를 제안합니다. 제안한 모델은 3가지 benchmark에서 기존의 방법론들보다 월등히 뛰어난 성능을 보였습니다.  architecture는 두 가지 중요한 요소가 있습니다. 첫 번째 NetVLAD pooling layer, 두 번째 weakly supervised ranking loss. NetVLAD pooling layer는 어떤 CNN architecture에도 적용 가능한 강력한 pooling mechanism을 제공하고 weakly supervised ranking loss는 많은 양의 weakly labelled 데이터를 end-to-end 방식으로 학습할 수 있게 합니다.

 

[참고자료]

[1] R. Arandjelovic, P. Gronat, A. torri, T.pajdla and J.Sivic. NetVLAD: CNN archintecture for weakly supervised place recognition. In Proc. CVPR, 2016.

[2] 네이버랩스 Mapping & Localization Challenge

[3] 네이버랩스 데이터셋 구축 과정과 베이스라인 측위 기법

[4] "책을 찍다"의 이미지 검색 시스템 2 : Image Descriptor

[5] Bag of Words (BoW) 이해하기

[6] Bag of Words 기법

[7] Implementation of NetVLAD in PyTorch, including code for training the model on the Pittsburgh dataset.