A sneak peak of the Video Retrieval

안녕하세요. 백지오입니다!

드디어 첫 X-REVIEW를 작성하게 되었습니다. 기념비적인 첫 X-REVIEW로 어떤 글을 쓰면 좋을지 고민하다가, 처음부터 아주 새로운 논문에 도전하는 것보다 제가 지난 한 달간 공부한 저희 팀의 Task에 대한 간단한 소개를 쓰면 좋겠다는 생각이 들어 <Video Retrieval 맛보기> 글을 준비했습니다. 첫 글이기도 하고, Video Retrieval도 꽤 어려워서 여러모로 부족한 글이 될까 걱정이 앞서는데, 많은 피드백 주시면 감사하겠습니다.

이 글은 다음 논문들의 내용을 포함하고 있습니다. 아래 제목들을 클릭하면 각 논문의 리뷰들을 확인하실 수 있습니다.

• Near-Duplicate Video Retrieval by Aggregating Intermediate CNN Layers
• Near-Duplicate Video Retrieval with Deep Metric Learning
• ViSiL: Fine-grained Spatio-Temporal Video Similarity Learning

---

What is Video Retrieval?

Video Retrieval은 직역하면 영상 검색으로, 가지고 있는 전체 영상들의 DB에서 검색을 위해 제시된 쿼리(query)와 유사한 영상들을 찾아내는 Task이다. 쿼리는 다양한 형태로 주어질 수 있는데, 만약 쿼리가 텍스트로 주어진다면 Text to Video Retrieval, 쿼리가 영상으로 주어진다면 Video to Video Retrieval과 같이 부른다.

예를들어, 유튜브 검색엔진은 Text to Video Retrieval의 일종으로 생각할 수 있다. (실제로는 tag나 title같은 메타 정보들을 활용하겠지만, 텍스트로 영상을 검색한다는 맥락에서 생각해보자.) 이 글에서 다루고자 하는 Video Retrieval은 쿼리가 영상으로 주어지는 Video to Video Retrieval을 의미한다.

Challenges of Video Retrieval

Video to Video Retrieval은 아직 선행연구 단계이기에 어떤 분야에서 사용될지 단언하기 어렵지만, 유튜브 등 영상 플렛폼의 추천 시스템 및 검색 시스템이나, 네이버 렌즈와 같은 검색 용도로 활용될 수 있을 것이다.

필자가 공부하며 느낀 Video to Video Retrieval의 어려움은 다음과 같다.

• 너무 크다. 일반적으로 초당 20장 이상의 이미지로 구성되기 때문에, 막대한 저장용량과 연산량이 요구된다.
  • 이러한 특성 상 고품질 데이터의 취득, 저장, 연산 모두가 어렵다.
• 용량이 큰 것에 비해 중복되는 데이터가 아주 많다. 때문에 Sparse한 정보를 갖게 되고, 유의미한 정보를 추출하기가 어렵다.
• 영상은 시간적 정보를 포함한 시계열의 특성을 갖기 때문에 다루기 어렵다.

그러나 이러한 어려움에도 불구하고, 영상 매체의 수요와 유통량이 계속 증가하고, 막대한 연산량을 처리할 수 있는 하드웨어의 발전도 지속되고 있어 영상 검색은 꽤나 유망하다고 생각된다.

How does the retieval works?

검색 모델은 쿼리와 DB의 쌍으로 구성된 데이터셋에서 학습된다. 어떤 쿼리 $q_i\in Q$에 대하여, DB에 속한 샘플 $d_j\in D$가 해당 쿼리와 유관한 샘플인지, 혹은 그렇지 않은지가 라벨 $l$로 주어진다. 만약 $q$가 $d$와 유관하다면 $l_{q, d}=1$이 되고, 무관하다면 $l_{q, d} = 0$이 되는 것이다.

검색 모델은 주어진 쿼리 $q$와 DB 속 모든 영상들을 어떤 방법을 통해 특성 벡터로 변환한다. 그 다음, 쿼리 영상의 특성 벡터와 DB 속 모든 샘플들의 특성 벡터들 간의 유사도 점수를 계산한다. 그리고 유사도 점수가 높은 순서대로 DB를 정렬하여 검색 결과로써 제공하는 것이다.

Simlarity vs Distance

위에서 유사도 점수를 언급하였는데, 구체적으로는 유사도나 거리를 이용하여 검색 대상들을 정렬하게 된다.
각각을 가볍게 짚고 넘어가보자.

유사도 (Similarity)

유사도는 주로 코사인 유사도를 사용하는데, 말 그대로 값이 높을수록 두 벡터가 유사함을 의미한다. 벡터의 내적 공식을 활용하여 두 벡터의 사잇각의 코사인을 구한다. 두 벡터가 유사할수록 두 벡터가 이루는 사잇각이 작아지고, 1에 가까운 유사도가 나온다. 한편 두 벡터가 다를 수록 사잇각이 커져 -1까지 유사도가 하락한다.

$$ Sim(x, y) = \frac{x\cdot y}{|x||y|} $$

거리 (Distance)

L2 거리로 대표되는 거리는 말 그대로 어떤 벡터들의 거리를 의미한다.
두 벡터의 거리가 낮을수록(가까울수록), 두 벡터가 유사하다고 할 수 있다.

$$ L2(x, y) = \sqrt{\sum_{x_i\in x, y_i\in y}(x_i – y_i)^2} $$

How to make a video into a vector?

비디오는 다양한 가로 세로 해상도에 더하여, 길이(시간)를 갖는 데이터이다. 검색을 수행하기 위해서는 쿼리와 DB 속 요소들의 유사도를 구해야 하기 때문에, 모든 영상을 정해진 크기의 벡터로 만들어야 한다.

영상 검색은 결국, 각기 다른 크기$(W\times H\times T)$를 가진 영상들을 어떻게 검색에 용이한 고정된 크기의 벡터 Descriptor로 만드는 가에 대한 연구라 할 수 있다.

영상 검색에는 크게 3가지 방법이 있다.

1. Video-Level matching: 영상 전체를 하나의 벡터로 변환하여 비교한다.
2. Frame-Level matching: 영상 속의 프레임들, 혹은 프레임의 시퀀스들을 벡터로 변환하여 이들을 비교한다.
3. Hybrid-Level matching: 영상 전체를 비교하여 1차적인 검색을 수행하고, 프레임 단위로 비교를 다시 수행하여 정확도를 높인다.

How to make the frames into the vector?

영상은 일반적으로 초당 24~60장의 프레임(이미지)으로 구성된다.
영상 검색에서는 일반적으로 이 프레임들 중에서 일부를 추출하여 frame-level descriptor로 만들고, 이들을 어떤 방법으로 누적(aggregation)하여 해당 영상을 나타내는 video-level descriptor로 만들어 사용한다.

Maximum Activation of Convolutions, MAC

합성곱의 최대 활성화 값을 이용하는 MAC 방법은 원래 이미지 검색 task에서 먼저 연구되었다. 2014년 Azizpour et al. 은 이미지를 합성곱 신경망에 투입하여 마지막 합성곱 계층을 거치고 출력된 $W\times H \times C$ 크기의 feature maps에 global max-pooling을 적용하여 이미지를 $C$ 크기의 벡터로 만드는 MAC 방법을 제안했다. 이 방법의 장점은 어떤 크기의 입력 이미지라도 $C$ 차원의 벡터로 변환할 수 있다는 점이다. 그러나, 모든 영상의 영역을 하나의 값으로 변경하기 때문에 공간적인(geometric) 정보를 잃는다는 단점이 있다.

Regional MAC, R-MAC

R-MAC은 지역적 정보를 포기하는 MAC의 단점을 조금이나마 보완하는 방법으로, 2016년 논문인 Particular Object retrieval with Integral Max-Pooling of CNN Activations에서 제안되었다. 이 방법 역시 MAC과 같이 Max-Pooling을 통해 특성을 추출하지만, 각 feature map을 $n$개의 영역(region)으로 나누어 MAC을 추출함으로써 조금이나마 지역적 특성을 유지할 수 있다. 이때, pooling layer의 receptive field size가 고정되어 있지 않고, 입력 영상의 크기와 무관하게 항상 $n\times n$개의 영역에서 pooling을 수행하기 때문에, MAC과 마찬가지로 어떤 크기의 입력에 대해서도 고정된 $n^2\times C$크기의 벡터로 만들 수 있다.

$n$을 얼마나 크게 설정하느냐에 따라 보존되는 지역적 정보의 양이 늘어나지만, 그만큼 벡터의 크기 $n^2\times C$가 커지게 되며, 너무 local 한 정보까지 수집하게 되어 오히려 검색에 방해가 될 수도 있다.

Intermediate MAC, I-MAC

I-MAC은 2017년 Near-Duplicate Video Retrieval by Aggregating Intermediate CNN Layers 논문에서 소개된 방법으로, 영상 검색에 CNN 중간 feature들을 응용한 방법이다. 합성곱 신경망의 마지막 계층에서만 MAC feature를 뽑아내는 기존 방법들과 다르게, I-MAC은 합성곱 신경망의 모든 계층에서 feature를 뽑아낸다. (단, 맨 처음 합성곱 계층은 너무 낮은 수준의 특성들을 생성하여 스킵하기도 한다.) 이를 통해 각 이미지에서 더 다양한 수준의 특성을 추출할 수 있지만, 벡터의 크기 자체는 커지게 된다.

From Frame Descriptors to Video Descriptor… And How to Compare them.

위에서 MAC 기반 방법들을 활용해 Frame Descriptor들을 얻었다.
이 Descriptor들을 다양한 방법으로 병합하여 Video Descriptor를 만들고 비교할 수 있는데, 이 글에서는 3개의 방법을 살펴보겠다.

Feature Aggregation

I-MAC을 제안한 논문에서 제안된 방법이다. 논문에서는 Vector Aggregation과 Layer Aggregation이라는 두 방법을 제안하는데, 실험 결과 더 나은 성능을 보인 Layer Aggregation을 기준으로 설명하겠다.

1. 어떤 프레임을 $L$개의 합성곱 계층을 가진 합성곱 신경망에 투입하여 $L$개의 I-MAC feature를 얻는다.
2. 각 계층별로 codebook을 생성하여 bag-of-words representation을 생성한다. 한 프레임은 $L$개의 BoW vector로 변환된다.
3. 이 codebook들을 병합하여, 한 프레임은 $L\times K$ ($K$는 codebook의 크기) 크기의 히스토그램 벡터가 된다.
4. 각 프레임의 벡터를 누적하여 영상에 대한 히스토그램을 만든다. 이 역시 $L\times K$ 크기를 갖는다.

논문에서는 이렇게 구한 Video Descriptor에 TF_IDF 방법을 적용하여 중요한 요소들에 가중치를 부여하고, 코사인 유사도를 구하여 비교한다.

Deep Metric Learning

영상 검색에 Metric Learning을 적용한 Near-Duplicate Video Retrieval with Deep Metric Learning 논문(2017)에서 제안한 방식이다. 먼저, 영상에서 초당 1장의 프레임을 추출해 pre-trained CNN에 입력하여 각 계층으로부터 I-MAC을 뽑아낸다. 이렇게 얻은 frame descriptor들의 평균을 구하고 zero-mean과 l2 noramlization을 적용하여 global video descriptor를 얻는다. 이 descriptor vector를 유사한 영상끼리는 가깝게, 유사하지 않은 영상끼리는 멀게 임베딩하는 DNN 모델을 학습시키고 이 임베딩 벡터들 사이의 거리를 이용해 Retrieval을 수행한다.

ViSiL

ViSiL은 2019년 제안된 방식으로 영상의 공간적 정보와 시간적 정보를 모두 사용하기 위해 복잡한 모델을 사용한다. 개념이 상당히 복잡하기 때문에 여기서는 간단하게 흐름만 살펴보고, 자세한 내용은 해당 논문의 리뷰 글을 참고해 주시기 바란다.

1. 영상의 한 프레임에 대해 R-MAC, I-MAC을 적용하여 $N\times N\times C^k$ 크기의 feature map들을 얻는다.
   • $C^k$는 각 합성곱 계층의 출력 채널 수이다.
2. 위에서 얻은 feature map은 모두 같은 $N\times N$ 해상도를 갖기에, 채널 축으로 쌓을 수 있다.
   • 이제 feature map $\mathcal{M}\in\mathbb{R}^{N\times N\times C}, (C=C^1 + C^2 + \cdots + C^k)$이 되었다.
3. 이렇게 얻은 feature map에 PCA whitening, L2 Normalization을 적용한다.
4. 여기에 어텐션 기법을 적용해 각 프레임의 중요한 영역에 가중치를 부여해 준다.
5. 이렇게 얻은 feature map $\mathcal{M}\in \mathbb{R}^{N\times N\times C}$을 채널 축만 유지하고 평탄화해서 $(N^2, C)$ 크기로 바꿔준다.
6. 두 영상의 프레임 $d, b$에 대하여, 5까지 진행하여 얻은 feature들의 유사도를 계산하여 유사도 행렬을 생성한다. 이 유사도 행렬은 $(N^2 \times N^2)$ 크기의 행렬이 된다. (frame-to-frame similarity matrix)
   • 요약하자면, 두 영상에서 추출한 프레임 $d, b$의 모든 영역들 $d_{ij}, d_{kl}$ 사이의 조합 간에 유사도를 담은 행렬을 구한다.
7. 이 행렬에서, 각 프레임의 각 영역에 대하여 가장 유사도가 높은 다른 영상의 영역의 유사도의 평균을 구한다.
   • $d$의 어떤 영역 $d_{ij}$와 가장 유사한 $b$ 속 영역 $b_{kl}$을 찾는다.
   • 이걸 모든 영역에 대해 진행하고, 매칭된 영역들의 유사도의 평균을 구한다.
   • 이를 통해 두 영상의 어떤 프레임간의 유사도를 하나의 값으로 나타낼 수 있다.
8. $d, b$가 각각 $X, Y$개의 프레임을 가지고 있을 때, 모든 프레임의 조합 $X\times Y$에 대하여 위 값을 구하여 $X\times Y$크기의 유사도 행렬을 만든다. (video-to-vdieo similarity matrix)
9. 이 행렬을 CNN에 입력하여 유사도를 구하도록 학습시킨다. 이 CNN은 triplet을 이용해 비슷한 영상들에는 높은 값, 비슷하지 않은 영상들에는 낮은 값을 부여하도록 학습한다.

---

Conclusion

지금까지 Video-to-Video Retrieval이 무엇인지, 어떤 과정으로 진행되는지 알아보고 초기 연구 3가지의 접근 방식을 간단하게 다루었습니다. 논문을 읽고, 요약하고, 다시 리뷰를 작성하고 검토하는 과정에서 매번 지난 번에 잘못 이해한 부분을 발견하거나 이해가 깊어지고 있어 아마 이 글에도 검토를 많이 하기는 하였지만 틀린 부분이 있을 수도 있겠다는 생각이 듭니다.

혹시 궁굼한 점이나 글에서 잘못된 점, 혹은 가독성 등을 고려해 고쳐야 할 점이 보이시면 댓글로 알려주시면 감사하겠습니다.

리뷰 마치겠습니다. 감사합니다!