R-MAC: Particular Object retrieval with Integral Max-Pooling of CNN Activations 리뷰

이 논문은 2016년 ICLR에 개제 된 논문으로, Image Retrieval Task에 기존에 사용되던 BoVW 등의 Handcrafted 방법론들 대신, CNN 기반의 R-MAC이라는 새로운 방법론을 적용하여 높은 성능을 달성한 논문이다.

이 논문 이전의 이미지 검색 task에서는 2003년 등장한 Bag-of-Words 기반의 방법론들이 주로 활용되었다.
이들 방법론에서는 이미지에서 특징점들을 추출하여, 이 특징점들을 고정된 크기의 벡터로 만든다.

쿼리 이미지의 벡터와 데이터베이스에 있는 이미지들의 벡터 간의 유사도를 구하여, 유사도가 높은 순서로 re-ranking을 거치면 검색 결과를 얻을 수 있는 것이다.

2013년, Donahue et al.이 합성곱 신경망(CNN)의 중간 계층의 활성화 값들을 이용해 이미지를 벡터화하는 방법을 제안하였는데, 이런 시도에 힘입어 CNN 기반의 이미지 검색 기술도 점차 발전하고 있었다.

특히, Azizpour et al.이 2014년에 발표한 방법에서는, 합성곱 신경망이 출력한 feature를 global max-pooling 하여 벡터화하였는데, 이를 통해 굉장히 좋으면서도 작은 크기의 image representation을 생성할 수 있었다.
그러나 해당 방법은 이미지의 global한 정보를 가져오고 geometric(지역적)한 정보를 잃었기에 아쉬움이 있었다.

이 논문에서는 아래 세 가지의 내용을 기여했다.

1. 합성곱 계층에서 이미지 검색에 용이한 작은 크기의(compact) image representation을 유도하는 방법 제시
2. generalized mean을 사용하여 max-pooling과 함께 이미지의 적분을 가능토록 함. 이를 통해 object localization을 CNN의 2D 출력에서 바로 생성 가능
3. 이 localization을 통해 간단하면서도 효과적인 query expansion을 수행하고 image re-ranking에 사용할 수 있음.

Related work

기존 CNN 기반의 이미지 표현(Representation) 추출법에서는 CNN의 합성곱 계층 및 완전 연결 계층을 통과하고, 활성화함수를 거친 값 혹은 VLAD 형식으로 누적된 값을 사용하였다.

최근 연구들은 활성화 함수를 거친 합성곱 계층의 출력값을 사용한다. 이런 방법은 활성화 값들을 쌓거나(stacking) 공간적 max-pooling, 혹은 sum-pooling을 각 채널에 수행한다. 2014년, Azizpour et al. 의 연구에 따르면 이러한 표현은 training 데이터와 다른 test 데이터에 대한 더 나은 일반화 성능을 보인다.

완전 연결 계층들이 객체 분류 문제를 위한 특성을 생성하며, 컴퓨팅 비용도 많이 요구하기 때문에 retrieval task를 위해 오히려 합성곱 계층의 출력을 사용하는 것에 더 이점이 있다.

Maximum Activations of Convolutions (MAC)

사전학습된 CNN에서 완전 연결 계층을 제거해보자. $W_I \times H_I$ 크기의 입력 이미지 $I$가 주어질 때, 합성곱 계층들의 출력은 ReLU 활성화 함수를 통과한 $W\times H\times K$ 형태의 3D 텐서가 된다. 

출력된 3D 텐서를 2D feature $\mathcal{X}$들의 집합으로 정의하자. $\mathcal{X}=[\mathcal{X}_i], i=1\cdots K$
$\mathcal{X}_i$가 유효한 위치들의 집합 $\Omega$에 대한 $i$번째 특성 채널을 의미할 때, feature vector는 모든 위치에 대한 공간적 max-pooling으로 다음과 같이 정의된다.

$$ f_\Omega = [f_{\Omega, 1}, \cdots, f_{\Omega, i}, \cdots, f_{\Omega, K}]^T , f_{\Omega, i} = \max_{p\in\Omega}\mathcal{X}_i(p).$$

이를 통해 이미지는 $K$ 차원의 벡터로 나타내어질 수 있다. 이 벡터들의 코사인 유사도를 통해서 이미지들을 비교할 수 있는 것이다. 

이 방식을 MAC이라 하는데, 이미지 전체 영역에 대한 global pooling을 수행하기 때문에 위치적인 정보가 사라져 버리는 문제가 있다. 논문에서는 이미지의 크기나 비율을 바꾸거나 이미지를 자르지 않고 단순하게 이미지에서 평균 픽셀 값만을 뺀 후에 MAC를 추출한다.

MAC은 global pooling을 통해 translation invariance를 얻는데, 이는 완전 연결 계층이 지역적 정보를 보존하는 것과 대비된다. 그러나 이 논문의 저자들은, CNN의 특성상 위치와 크기 변화에 대한 강건함은 충분히 얻을 수 있다고 한다.

Regional MAC, R-MAC

위에서, 이미지 전체 영역에 대한 global pooling을 수행하여 이미지 표현 벡터를 얻었다. global pooling 대신 이미지의 일부를 다음과 같이 얻어보자. $\mathcal{R} \subseteq \Omega = [1, W] \times [1, H]$

$$ \mathbf{f}_\mathcal{R} = [f_{\mathcal{R}, 1}, \cdots , f_{\mathcal{R}, i}, \cdots, f_{\mathcal{R}, K}]^T$$

$\mathcal{R}$이 입력 이미지의 영역이 아닌 feature map의 유효한 위치 $\Omega$에서 정의되었기 때문에, 이미지를 굳이 두 번 CNN에 넣을 필요가 없어 연산량을 줄일 수 있다.

이제 $\mathcal{R}$ 영역과 입력 이미지 $I$간의 매핑을 생각해보자. receptive field 개념에 의해, $\mathcal{R}$ 영역은 입력 이미지 $I$의 일부 영역에 대응되는 feature이다.

figure 3. of paper

$\mathcal{R}$은 정사각형의 영역으로, 우리는 $L$개의 다양한 크기의 정사각형 영역을 추출하는데, 이때 최대한 큰 크기의 영역을 가져가게 된다. 즉, 가장 큰 스케일 $l=1$에서, 정사각형의 한 변의 길이는 $\min(W, H)$와 같다.

영역은 전체 이미지를 균등하게 나누어 샘플링되며, 각 영역이 겹치는 부분이 40%에 가깝도록 추출된다.

이렇게 이미지에서 생성된 $n$개의 각 region에 대하여 MAC를 수행하여 $K$개의 각 채널에 대한 feature를 얻음으로써, $n\times K$ 크기의 matrix를 얻을 수 있다.

마지막으로, $n$개의 region들의 $K$ size vector들을 모두 누적하고 l2 normalization을 가해 scale을 조정하여 이미지를 $K$ 크기의 vector로 만들어준다. 이렇게 이미지를 $K$라는 낮은 차원의 벡터로 만들 수 있는데, 논문에서는 실험을 통해 이 방법이 낮은 차원에도 불구하고 좋은 성능을 보여준다.

Approximate Integral Max-Pooling

이 논문에서 소개하는 방식은, 이미지 내부의 영역 $\mathcal{R}$들에 대한 Max-Pooling을 여러 차례 수행해야 하기에 컴퓨팅 자원이 많이 요구된다.

저자들은 이를 위해 각 영역의 max-pooling 결과를 approximate 할 수 있는 방법을 제안한다.

$$ \hat{f}_{\mathcal{R}, i} = (\sum_{p\in\mathcal{R}} \mathcal{X}_i(p)^\alpha)^{\frac{1}{\alpha}} \approx \max_{p\in\mathcal{R}} \mathcal{X}_i(p) = f_{\mathcal{R}, i}$$

$\alpha \rightarrow +\infty$일 때, 영역 $\mathcal{R}$ 속 각 픽셀의 $\alpha$ 제곱의 합을 다시 $\alpha$ 제곱근하면, 이는 maxpooling을 한 결과와 근사하다는 것이다.

예를 들어, $(1, 2, 3, 4)$의 값을 갖는 영역에 max-pooling을 수행하면 4가 나오고, $\alpha=10$으로 두고 위 식을 적용해 보면 $(1^{10} + 2^{10} + 3^{10} + 4^{10})^{\frac{1}{10}} = 4.022$가 나온다.

https://kr.mathworks.com/help/images/ref/integralimage.html

이제 위와 같은 Integral Matrix를 정의해 보자.

어떤 integral matrix의 한 점 $g_{x, y}$는 원본 이미지의 픽셀 $i_{0, 0}$부터 픽셀 $i_{x, y}$까지의 값들의 합과 같다.
예를 들어, 위 이미지에서 $g_{2, 2}$의 값 10은 원본 이미지의 $i_{0, 0}$부터 $i_{1, 1}$픽셀까지의 합 $1+2+3+4$와 같다.

위 이미지에서, 하늘색으로 표시된 영역의 max-pooling값을 알고 싶다면, $g_{4, 4} - g_{4, 2} - g_{2, 4} + g_{2, 2}=46-22-20+10 = 14$를 얻어 쉽게 하늘색 영역의 픽셀들의 합을 알 수 있다.

이때, integral matrix를 단순히 픽셀들의 값이 아닌 픽셀들의 값의 $\alpha$ 제곱으로 정의하는 확장된 integral matrix를 이용하면, 큰 영역의 max-pooling값도 사칙연산 몇 번과 sqrt 연산을 적용해 빠르게 알아낼 수 있는 것이다.

알파값에 따른 maxpooling 근사 오차

저자들은 여러 $\alpha$값에 대한 실험을 거쳐, max-pooling 근사 오차가 작으면서도 많은 연산을 요구하지 않는 $\alpha=10$을 적용하였다.

Retrieval, Localization and Re-ranking

R-MAC의 Image Retrieval은 3단계로 구성된다.

Initial Retrieval. 모든 데이터베이스 이미지에 대해 MAC 또는 R-MAC feature vector를 구한다. 똑같이 쿼리 이미지에 대해서도 feature vector를 추출한 다음, 쿼리와 데이터베이스 이미지들의 코사인 유사도를 구하여 이 순서대로 데이터베이스를 정렬한다. 일반적인 Retrieval과 같은 과정이다.

Re-ranking. 추가적으로 두 번째 Re-ranking 스테이지가 진행된다. 초기 Retrieval에서 얻은 상위 $N$개의 샘플과 쿼리 이미지에 대해서 아래에서 설명할 AML을 수행한다. 이제 쿼리 이미지는 MAC vector로 표현되며, 데이터베이스 이미지들은 $\mathcal{X}$ 형태로 나타난다. 이제 각 DB 이미지들은 쿼리 이미지 속의 영역 $q$와의 유사도 순으로 재정렬된다.

Query expansion (QE). 재정렬 과정을 통해 DB 상단에는 쿼리 이미지와 가장 유사한 positive sample들이 오게 된다. 이때, 상위 5개의 이미지들을 query vector와 더하고, 평균을 구한다. 이렇게 구해진 평균을 이용해 DB의 상위 $N$개 샘플을 다시 재정렬해 준다.

AML: Approximate max-pooling localization

우리는 어떤 이미지 $Q$ 속의 한 영역 $q$와 가장 유사도가 높은 이미지 $I$ 속 영역 $\hat{\mathcal{R}}$을 찾고자 한다.

이때, 이미지 $I$의 모든 영역들과 $q$ 영역을 비교하면 컴퓨팅 자원이 많이 요구되기 때문에, 간단한 방법으로 비교해야 할 영역의 수를 제한한다. 먼저, 탐색해야 할 영역들을 균등한 간격으로 $t$개 샘플링한다. 추가로, 비율이 쿼리 영역 $q$에 비해 $s$배 이상 큰 영역들은 버린다. 

결론

쉽지 않다. 엄청 복잡하고 contribution도 많은 논문이었다.
어떻게든 Image Retrieval Task를 극한까지 해내보겠다는 저자들의 열망이 느껴지는 것 같다.

3번의 ranking을 거치는 과정에서 AML 과정이 잘 이해가 가지 않았다. 나중에 다시 들여다봐야 할 것 같다.

3번의 Retrieval에서 가장 먼저 단순히 MAC 또는 R-MAC feature를 비교하여 검색을 수행하고, 그다음 이미지의 세부적인 지역적 정보를 보고 re-rank 하고, 마지막에 Query Expansion까지 수행하는 방식이 매우 집요하고 창의적이라 느꼈다.

한편 정확도만 상승시킨 것이 아니라 Accumulation을 통해 feature의 차원도 MAC과 같게 유지하고(공간 복잡도), Integral Max-Pooling Approximation을 통해 연산 효율(시간 복잡도)까지 낮춘 것이 놀랍다.

특히 Integral Matrix를 이용한 Max-Pooling Approximation은 이해하기 정말 어려웠는데, 이해하고 나니 소름이 돋았다.
컨디션이 영 안 좋은 하루였는데, 그야말로 엄청난 창의성과 실력을 보고 나니 조금 두려울 정도이다.

언젠가 이런 논문을 쓰는 날이 왔으면 좋겠다.

가보자고!

References

• Particular object retrieval with integral max-pooling of CNN activations
• (논문리뷰) Particular object retrieval with integral max-pooling of CNN activations 설명 및 정리 - Kanghee Lee님 
• Deep Image Retrieval - Kiho Hong님
• Special Thanks to 세종 RCV 조원, 이광진, 김현우 연구원님