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

처음으로 포스팅할 논문은 NetVLAD: CNN architecture for weakly supervised place recognition라는 제목으로 IEEE CVPR 2016에 발행된 논문입니다. NAVER LABS에서 진행하고 있는 Mapping & Localization Challenge에서 자체적으로 제작한 데이터셋을 활용한 localization 기법으로 사용한 방법론에 소개되어 있어 읽어보았습니다.

 

NAVER LABS Mapping & Localization Challenge

 

[매핑 & 로컬라이제이션 챌린지] 데이터셋 구축 과정과 베이스라인 측위 기법

 

본 논문에서 다루는 주제는 이미지 기반의 장소 인식(problem of large scale visual place recognition)입니다.

이미지 인식 문제답게 CNN을 기반으로 하고 있습니다.

---

Abstract

 

Abstract에서는 3가지 주요한 포인트를 소개합니다.

 

1. We develop a convolutional neural network (CNN) architecture that is trainable in an end-to-end manner directly for the place recognition task.
2. We develop a training procedure, based on a new weakly supervised ranking loss, to learn parameters of the architecture in and end-to-end manner from images depicting the same places over time downloaded from Google Street View Time Machine.
3. We show that the proposed architecture significantly outperforms non-learnt image representations and off-the-shelf CNN descriptors on two challenging place recognition benchmarks, and improves over current state-of-the-art compact image representations on standard image retrieval benchmarks.

첫 번째로는 저자들이 제안한 장소 인식을 위한 CNN, 그중에서도 이 논문의 주제인 NetVLAD를 소개하고 있습니다.

NetVLAD는 영상 검색(image retrieval)에 사용되는 image representation의 방법론 중 하나인 VLAD(Vector of Locally Aggregated Descriptors)에서 영감을 받았으며 다른 CNN architecture에도 쉽게 채용할 수 있고 backpropagtation으로 학습이 가능하다고 합니다.

 

두 번째는 Google Street View Time Machine에서 추출한 데이터를 이용해 제안한 CNN architecture를 학습하기 위한 weakly supervised ranking loss를 기반으로 한 training procedure입니다.

 

세 번째는 저자들이 제안한 구조가 2개의 benchmark에서 기존의 다른 방법들보다 좋은 성적을 보였다는 것입니다.

---

Introduction

 

Introduction에서는 장소 인식이라는 문제를 조금 더 구체적으로 정의하면서 문제를 해결하기 위한 3가지 challenge와 3가지 innovation을 언급합니다.

 

저자들은 문제를 다음과 같이 정의합니다.

"어떻게 하면 도시나 국가 스케일의 지역에서 조광이나 시간 변화에 상관없이 장소를 인식할 수 있을까"

(How can we recognize the same street-corner in the entire city or on the scale of the entire country despite the fact it can be captured in different illuminations or change its appearance over time?)

 

이 질문을 scientific 하게 나타내 보면

"도시 또는 국가 전체를 대표하면서 비슷한 장소를 구별해 낼 수 있는 장소의 적절한 표현방법은 무엇일까"로 나타낼 수 있습니다.

(The fundamental scientific question is what is the appropriate representation of a place that is rich enough to distinguish similarly looking places yet compact to represent entire cities or countries.)

 

즉, 다시 말해서 특정 장소를 촬영한 image A와 image B를 비교하기 위해서는 이 이미지들을 수학적으로 비교 가능한 방식으로 바꿔야 하는데 이미지를 수학적으로 표현하는 방법들 중 어떤 표현 방식이 visual place recognition의 관점에서 가장 적절한가 라는 뜻으로 해석할 수 있습니다.

 

저자들은  CNN을 이용한 이미지 표현 방식을 제안하고 visual place recognition에 적절한 CNN을 설계하기 위해서 3가지 challenge와 3가지 innovation을 설명합니다.

 

• challenge

1. What is a good CNN architecture for place recognition?
2. How to gather sufficient amount of annotated data for the training?
3. How can we train the developed architecture in an end-to-end manner tailored for the place recognition task?

첫 번째, 장소 인식을 위한 좋은 CNN architecture가 무엇인가?

두 번째, 학습을 위한 많은 양의 데이터는 어떻게 얻을 것인가?

세 번째, 개발한 CNN architecture를 어떤 방법으로 학습시킬 것인가?

 

 

• innovation

1. We develop a CNN network for place recognition that aggregates mid-level (conv5) convolutional features extracted from the entire image into a compact single vector representation emenable to efficient indexing.
2. To train the architecture for place recognition, we gather a large dataset of multiple panoramic images depicting the same place from different viewpoints over time from the Google Street View Time Machine.
3. We develop a learning procedure for place recognition that learns parameters of the architecture in an end-to-end manner tailored for the place recognition task from the weakly labelled Time Machine imagery.

첫 번째, conv5 단계에서 추출한 convolutional features를 single vector로 표현하는 CNN network를 개발

두 번째, 같은 장소를 다른 시간대, 다른 시각에서 촬영한 Google Street View Time Machine 데이터를 활용

세 번째, weakly labelled Time Machine 데이터를 사용할 수 있는 end-to-end 방식의 학습 절차를 개발

---

Method overview

Method overview에서는 문제를 수식으로 접근하여 설명합니다.

 

앞서 introduction에서 문제를 "장소를 촬영한 이미지의 적절한 표현 방법은 무엇인가"로 정의하였습니다.

여기서 힌트를 얻을 수 있습니다. 이미지를 왜 다른 방법으로 표현해야 할까요? 장소를 촬영한 이미지를 비교하기 위해서였습니다.

사람은 눈으로 이미지를 보고 건물의 모양, 주변 풍경, 표지판 등의 의미 있는 특징과 정보들을 이용해서 자신의 기억 속에 있던 장소와 비교하여 사진 상의 장소가 어떤 곳인지 인식합니다.

반면에 컴퓨터가 보는 이미지는 단순히 Height X Width X 3(RGB) 크기의 3차원 숫자 덩어리입니다.

따라서 이미지를 의미 있는 정보를 포함하고 있는 수학적인 표현방식으로 바꿔줘야 컴퓨터가 이미지를 비교할 수 있습니다. 일반적으로 벡터를 이용해 표현합니다.

이렇게 바뀐 벡터를 이용해서 내가 인식하고자 하는 이미지와 기억하고 있는 이미지들을 비교하여 탐색하는 것을 image retrieval이라고 합니다.

 

저자들은 place recognition을 이 image retrieval 문제로 접근해서 해결합니다.

(we cast place recognition as image retrieval.)

 

이것을 수식으로 표현해봅시다.

알고 있는 이미지들의 집합을 $\{I_i\}$라고 하고 query 이미지를 $q$, 이미지의 표현 방식을 벡터로 바꾸는 함수를 $f$라고 정의합니다.

image retrieval은 query 이미지 $q$가 주어졌을 때, 알고 있는 이미지들의 집합 $\{I_i\}$에서 이미지 $q$와 가장 비슷한 이미지$I_i$를 찾는 것이라고 할 수 있습니다.

이때 이미지 $q$와 $I_i$의 비교를 위해 $f$와 Euclidean distance $d$를 사용합니다.

각각의 이미지를 벡터로 바꾼 $f(q)$ 와 $f(I_i)$는 같은 크기의 벡터로 이 둘 사이의 거리는 $d$를 이용해 $d(q, I_i)$로 표현할 수 있습니다. 즉, 이미지 $q$와 이미지 $I_i$의 비슷한 정도를 벡터 간의 거리로 나타냅니다. 벡터의 거리가 짧으면 두 이미지는 비슷하고 거리가 멀면 두 이미지는 비슷하지 않다고 할 수 있습니다.

 

이미지들을 정확하게 비교하기 위해서는 함수 $f$를 잘 만드는 것이 중요하고 본 논문에서는 NetVLAD를 채용한 CNN architecture를 학습하여 함수 $f$로 사용하였고 CNN의 parameter를 함수 $f$의 $\theta$로 표현합니다.

---

Deep architecture for place recognition

Deep architecture for place recognition에서는 $f_\theta$로 표현한 CNN architecture에 대해서 설명합니다.

 

전체 네트워크는 다음 그림처럼 크게 두 부분으로 나눌 수 있습니다.

 

CNN architecture with tne NetVLAD layer

 

첫 번째로 convolution layer에는 영상 인식 분야에서 뛰어난 성능을 보이는 AlexNet, VGG16과 같은 미리 학습된 CNN architecture에서  pooling layer를 제외한 convolution layer만을 추출해서 dense descriptor extractor로 사용합니다.

 

이미지를 입력으로 사용하여 $W \times H = N$개의 D크기를 갖는 local descriptors ${\bf {x}}$를 출력합니다.

이와 같은 이미지가 convolutional layer 통과하며 형태가 바뀌는 일련의 과정을 Encoding이라고 합니다.

 

여기서 descriptor란 영상 서술자를 뜻하는데 이미지를 설명해주는 특징 벡터 혹은 해당 연산을 수행하는 알고리즘을 말합니다.

descriptor에 대해 자세하게 설명해주신 글이 있어 링크를 첨부합니다.

 

“책을찍다”의 이미지 검색 시스템2: Image Descriptor

두 번째로 NetVLAD layer입니다.

 

NetVLAD layer는 convolution layer를 통해 출력된 $N$개의 D크기를 갖는 local image descriptor $\{\bf {x}_i\}$를 pooling 하는 역할을 합니다.

CNN에서 pooling layer는 어떤 역할을 할까요?

pooling layer는 overfitting을 방지하기 위해서 feature의 개수를 줄여줍니다. 하지만 feature의 개수가 줄어든다는 것은 그만큼 정보의 손실이 일어남을 의미합니다. 좋은 pooling layer는 정보의 손실은 최소화하면서도 feature의 개수를 효율적으로 줄입니다.

 

즉 NetVLAD는 convolution layer가 출력한 local image descriptor의 정보는 최대한 유지하면서 feature의 갯수를 줄여 벡터로 표현되는 $f_\theta(I)$를 얻을 수 있게 합니다.

 

NetVLAD layer가 local image descriptor를 어떻게 pooling 하는지 이해하려면 VLAD를 알아야 합니다.

 

VLAD는 Vector of Locally Aggregated Descriptors 약자로 단어 그대로 descriptor들을 모아 벡터의 형태로 나타내는 pooling method입니다. 논문에서는 BOVW(Bag of Visual Words)와 비교하여 설명하였는데 VLAD도 BOVW의 visual word라는 개념을 사용합니다.

 

BOVW도 자세하게 설명해주신 글이 있어 링크를 첨부합니다.

 

Bag of Words (BoW) 이해하기

간단하게 설명하면 visual word는 이미지의 지역적인 특징(local image features)입니다. 지역적인 특징이기 때문에 한 개의 이미지에서 여러 개의 visual word를 추출할수 있고 BOVW에서는 이렇게 추출된 여러개의 visual word를 군집시켜 군집의 중심점들을 코드 워드라고 하고 이 코드 워드들로 구성된 코드북을 만들어 이미지들을 분류합니다. 여기까지 local image feature, visual word, local image descriptor 총 3개의 용어가 등장하는데 모두 같은 개념이고 CNN architecture에서 convolution layer의 출력 ${\bf {x}}$라고 생각하면 뒤에 나올 수식을 이해하기 쉽습니다.

 

다시 VLAD로 돌아와서, $N$개의 D크기를 갖는 local image descriptor $\{{\bf {x}}_i\}$와 $K$개의 cluster centres ("visual words") $\{c_k\}$가 주어졌을 때 $K \times D$ 크기를 갖는 VLAD image representation $V$를 수식으로 나타내면 다음과 같습니다.

 

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

 

수식을 분석해 보겠습니다. 먼저 local image descriptor $\{{\bf {x}}_i\}$ 는 $N$개이며 각각의 원소는 D개로 이루어져 있습니다.

즉 $\{{\bf{x}}_i\} = \{{\bf {x}}_1, {\bf {x}}_2, {\bf {x}}_3, \dots, {\bf {x}}_N\}$이고 이 집합의 모든 원소 local image descriptor ${\bf {x}}_i$는 각각 $D$개의 요소를 가지고 있습니다. 그림의 CNN architecture에서는 convolution layer의 출력 ${\bf {x}}$에 해당합니다.

 

다음으로 cluster centres ("visual words") $\{c_k\}$입니다. 본문에 언급은 안되어있지만 수식에서도 알 수 있듯이 ${\bf {x}}_i$와 마찬가지로 D개로 이루어져 있습니다. 즉 $\{c_k\} = \{c_1, c_2, c_3, \dots, c_K\}$이고 집합의 모든 원소 cluster centre $c_k$는 각각 $D$개의 요소를 가지고 있습니다.

 

앞에서 cluster centre는 visual word라고 했습니다. BOVW에서는 이미지의 visual words가 어떤 군집에 몇 개가 포함되는지 count 하여 이미지를 표현한 것에 반해 VLAD에서는 이미지의 visual word와 군집의 중심 점간의 차이를 계산하여 이미지를 표현합니다. 이것을 수식에서는 $(x_i(j) -c_k(j))$로 표현합니다. 논문을 구현한 코드에서는 미리 학습된 vgg16 모델의 convolution layer에 training 이미지들 중 일부를 입력으로 사용하여 visual word 추출하고 이것들을 군집화 시킨 후 각 군집의 중심점들을 cluster centre로 사용합니다. BOVW에서 training 이미지들을 이용해 코드북을 구성하는 것과 같습니다.

수식이 어떤 의미를 가지는지 알아보기 위해 차원을 하나 줄입니다. 수식에 사용되는 local image descriptor $\{{\bf {x}}_i\}$와 cluster centres $c_k$ 그리고 VLAD representation $V$는 요소의 개수는 다르지만 각각의 요소는 모두 같은 $D$개로 이루어져 있기 때문에 수식을 다음과 같이 변경해서 알아보겠습니다.

 

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

 

수식에서 $\sum$을 풀면 $V(k) = a_k({\bf {x}}_1)(x_1-c_k) + a_k({\bf {x}}_2)(x_2-c_K) + \dots + a_k({\bf {x}}_N)(x_N-c_k)$ 로 나타낼 수 있습니다. 위 식의 의미는 $V$의 $k$번째 요소는 모든 local image descriptor $\{{\bf {x}}_i\}$에 대해 $k$번째 cluster centre $c_k$와의 차이를 계산하고 계산된 결과를 각각 $a_k({\bf {x}}_i)$와 곱한 후 모두 더한 값이라는 것입니다. 그러면 $a_k({\bf{x}}_i)$는 무엇일까요. 논문에서는 $a_k({\bf{x}}_i)$를 다음과 같이 정의합니다. 

 

$a_k({\bf{x}}_i)$ denotes the membership of the descriptor  ${\bf {x}}_i$ to $k$-th visual word, i.e. it is 1 if cluster $c_k$ is the closeset cluster to descriptor  ${\bf{x}}_i$ and 0 otherwhise.

 

$a_k({\bf {x}}_i)$는 $x_i$가 모든 $\{c_k\}$ 중에서 $c_k$가 가장 가까운 cluster centre 일 때는 1이고 그 외에는 0이 됩니다. 즉 $x_i$와 $c_k$가 같은 군집에 해당될 때만 1이고 서로 다른 군집에 속해있다면 0이 됩니다. 이것을 고려해서 수식을 다시 생각해 보면 결국 $V(k)$는 $\{{\bf {x}}_i\}$ 중에서 $k$번째 군집에 해당하는 $x_i$들과 그 군집의 cluster centre 간의 차이를 모두 더한 것이 됩니다. 

 

여기까지 VLAD가 local image descriptor$\{{\bf {x}}_i\}$를 벡터 $V$로 어떻게 pooling 하는지 수식을 통해서 이해했습니다. 이제 이 VLAD를 어떻게 하면 신경망의 형태로 바꿔 CNN architecture에 채용할 수 있는지 알아보겠습니다.

 

다음 포스팅에서 계속

 

[참고자료]

[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.