Self-supervised Video Retrieval Transformer Network

Video Retrieval 관련 논문 2번째 입니다.

Self-supervised랑 Transformer task에 관심이 많아 이 논문을 보기로 했습니다.

중국회사인 Alibaba 의 DAMO Academy에서 나온 논문이고 링크는 다음과 같습니다.

Self-supervised Video Retrieval Transformer Network

---

1. Introduction

최근에 인터넷을 통해 생성되는 비디오의 양이 증가하는 것을 확인할 수 있고 동시에 다른 사람의 contents를 steal하는 수많은 동영상을 관찰해 비디오 저작권 보호를 만들고 필터링을 중요한 요구로 삼았습니다.

Content-based video retrieval은 주어진 query video와 similar한 contest를 공유하는 large video database에 video의 subset을 identifying하면서 문제를 해결합니다.

near-duplicate video retrieval이랑 fine-grained incident video retrieval이 많은 관심을 끌었습니다.

---

clip-level video representation

clip-level video representation을 설명하는 그림입니다. 뒤에서 나오지만 간단히 설명을 하자면

Video를 shot boundary detection을 통해 shots으로 split을 합니다. 그리고 정해진 시간 간격에 따라 클립으로 divided 됩니다. 그런 다음 SVRTN 접근 방식은 clip-level video representation을 extract하는데 적용됩니다. 마지막으로 효율적인 retreival을 위해 hashing method을 통해 clip-level feature을 이진화 합니다

---

다시 얘기를 하자면 video retreval system을 효과적으로 하기 위해서는 video representation이랑 video search가 중요합니다.

video representation

• supervised deep learning technolo-gies
• training을 위해서는 많은 labeled video가 필요합니다.
• 이러한 방식으로 robust and powerful video representation을 learn 하려면 비용이 많이듭니다.

video search

• a set of frame-level feature로 각각의 video를 represent하는 method
• 두 video 사이의 similarity 계산은 temporal alignment analysis(dynamic programming, temporal network, temporal Hough Voting)으로 결정됩니다.
• 단점 1. 모든 frame-level feature을 저장해야 하므로 storage 비용이 많이듭니다.
• 단점 2. two video의 similarity 측정은 frame간의 similarity 측정을 요구하기 때문에 비용이 많이 듭니다.

이러한 limitation을 해결하기 위한 일반적인 접근법은 각 video를 단일벡터(video-level features)로 표현 하는 것인데

이 방법은 storage 와 계산 비용을 완화 하는데 도움을 주지만 특히 long video 같은 경우 video 각각의 중요한 detail를 잡는거는 충분하지 못합니다.

그래서 논문의 저자는 이러한 문제를 다루기 위해 Self-supervised Video Retrieval Transformer Network을 제안합니다.

2가지 key contribution을 간단히 요약해보자면

Self-supervised video representation learning

• temporal and spatial transformation으로 생성되는 video 쌍과 그 transformation을 학습하기 위해 제안
• manual annotation의 high cost를 피할 수 있습니다.
• leading to better generalization for its learned representation

Clip-level set transformer network

• frame-level feature -> clip-level로 aggreate -> storage space 그리고 search complexity를 상당히 감소시켜줍니다.
• self-attnetion mechanism을 통해 clip frame간의 상호작용으로부터 complementary and variant한 정보를 학습할 수 있습니다.
• frame permutation 이나 누락된 프레임 문제를 처리하는 missing invariant ability를 얻을 수 있습니다.
• 이러한 두 가지 모두 clip-level feature의 discrimination이나 robustness을 증가시킵니다.
• clip-to-clip retreival 그리고 frame-to-clip retreival와 같은 것들을 더 flexi-ble retreival manners 하게 해줍니다.

FIVR-200K and SVD video retrieval datasets(challenging하다고 표현)에서 SVRTN approach가 best performance of video retrieval on accuracy and effi-ciency를 보여줍니다.

---

2. Related Work

존재하는 video retrieval methods를 two categories(frame-level rereival method and video-level retrieval method)로 나눕니다.

2.1. Frame-level Retrieval Methods

이 방법은 일반적으로 CNN을 사용하여 frame-level feature을 extract 하고 대략적인 nearest neighbor search를 통해 관련된 frame을 retreve합니다. frame-to-frame similarity matrix를 video similarity score로 aggregate하기 위해 다양한 post-processing method가 제안되었습니다.

1. Temporal Hough Voting (Vcdb: a large-scale database for partial copy detection in videos.)(Jiang et al.)(ECCV 2014)

- matched frame사이의 상대적인 timestamp를 사용하여 temporal alignments(시간 정렬)를 찾는 방법

2. Graph-based Temporal Network(Scalable detection of partial near-duplicate videos by visual-temporal consistency)(Tan et al.)(ACMM)

- 두 compared videos 사이의 가장 긴 shared path를 detect하는 방법

3. CNN+RNN( Learning spatial-temporal features for video copy detection by the combination of cnn and rnn)(Hu and Lu)(JVCIR)

- partial copied detection 문제를 다루기 위해 temporal network를 CNN+RNN feature encoder와 결합하는 방법

4. Based on Dynamic Programming

- frame-to-frame similarity matrix로 부터 가장 크게 matched되는 diagonal block을 extract 하고 제한된 수평 및 수직 movement를 유연성을 위해 tolerate합니다.

5. Bag-of-Words(Patternbased near-duplicate video retrieval and localization on webscale videos)(Chou et al.)(IEEE 2015)

- frame을 표현 하기 위해 Bag-of words를 적용하고 near duplicate segments를 localize하고 retrived video를 re-rank하기 위한 m-pattern-based dynamic programming 알고리즘을 제안합니다.

하지만 이러한 위의 방법들은 video retrieval의 필수적인 spatial feature invariance 활용을 ignore하는 방법입니다.

최근에 Visil: Fine-grained spatio temporal video similarity learning. In Proceedings of the IEEE International Conference on Computer Vision (ICCV 2019)(Kordopatis-Zilos et al.) 논문에서 나온 방법인데 region-level similarity caculation을 사용하고 세밀한 spatial alignments을 고려하고 높은 retrieval performance 달성하는 frame similarities의 region similarity matrix를 활용합니다.

이런 frame-level retrieval method는 연속적인 frames사이의 redundancy(중복성)을 무시하므로 더 많은 계산 비용이 필요하고 그 결과 retrieval 효율성이 낮아지는 문제가 있습니다.

2.2. Video-level Retrieval Methods

Video-level retrieval methods는 video를 video level로 encode 하고 embedding space에서 query video의 video-level feature에 대해 k-nearest neighbors search 합니다. video-level feature aggregation method는 single video-level representation을 얻기 위해 사용 되었습니다.

1. Deep video hashing(Liong et al.)

- mean average pooling으로 연속적인 frame을 temporal pool-ing layer로 aggregate하는 temporal pooling layer를 제안했습니다.

2. Near-duplicate video retrieval by aggregating intermediate cnn layers(Kordopatis-Zilos et al.)(IEEE)

- 중간 CNN layer에서 개별 frame feature를 추출하고 Bag-of Word를 채택해서 video-level representation으로 압축하여 video similarity을 two video-level representation 사이에 cosine distance를 계산하여 측정합니다.

3. Hash code based methods

- vidoe로부터 통일된 spatial temporal을 encode하는데 사용 됩니다.

4. Self-supervised video hashing with hierarchical binary auto-encoder(Song et al.)(IEEE)

- encoder-decoder 아키텍처를 이용해 frames사이의 temporal 관계를 capture하는 방법입니다.

5. Neighborhood preserving hashing for scalable video retrieval(Li et al.)(IEEE 2019)

- video의 spatial-temporal 구조를 잡기 위해 binary code를 적용합니다.

- neighborhood attention 메커니즘을 RNN 기반 reconstruction scheme로 통합하면서

하지만 이런 Video-level retrieval methods는 일반적으로 frame-level retreival method보다 perform이 worse합니다.

이유는 단일벡터가 video에서 전체적인 spatio-temporal 구조를 캡처하기가 어렵기 때문입니다.

---

3. Self-supervised Viedo Retrieval Transformer Network

Figure 2. Overview of our SVRTN approach.

SVRTN은 위 그림과 같이 2가지 메인 요소로 구성되어 있습니다.

self-supervised video representation learning, clip-level set transformer network

1. temporal and spatial transformation을 통해 videos pairs을 자동적으로 생성합니다.
2. video paris을 supervision으로 활용해서 contrastive learning과 함께 frame-level feature를 학습시킵니다.
3. self-attention 메커니즘을 통해 frame-level features -> clip-level feature로 aggregate하고 마스크된 frame modeling을 통해 robustness을 높입니다

* 머신러닝에서 Robust란?

- 머신러닝에서 일반화(generalization)는 일부 특정 데이터만 잘 설명하는(=overfitting) 것이 아니라 범용적인 데이터도 적합한 모델을 의미한다. 즉, 잘 일반화하기 위해서는 이상치나 노이즈가 들어와도 크게 흔들리지 않아야(=robust) 한다.

 

3.1.Self-supervised Video Representation Learning

기존의 방법들은 manual annotated video paris로 모델을 train하는데 당연히 데이터가 많을수록 좋은 performance를 보여주지만 많은 training data를 annotation하는 비용이 매우 비쌉니다. 단점이죠. 그래서 일반적으로 보통 representation learning은 제한된 양의 training data로 restricted 됩니다.

논문에서는 restriction을 깨려고 self-supervised video representation learning을 제안하고 다양한 video transformation을 defense 하기 위해 spatial-temporal invariant of representation을 이용합니다.

3.1.1 Self-generation of Training Data

먼저 자동으로 video website으로부터 많은 양의 video를 수집하고 그리고 training data를 구성하기 위해 이러한 clips에 대한 temporal and spatial transformation이 sequentially하게 수행됩니다.

Figure 3. Illustration of self-generation of training data

(1) Temporal Transformation

위 그림을 참고하면서 보면 이해가 빠릅니다.

먼저 고정된 time interval r을 가진 N 프레임을 균일하게 샘플링해서 C = {I 1 , I2 , · · · , IN } 로 표현된 anchor clip을 만듭니다. 그리고 frame Im은 anchor clip C 그리고 positive clip C+ 이랑 동일하게 내용으로 anchor clip에서 랜덤하게 선택됩니다. 우리가 선택한 프레임을 C+의 중앙값 프레임으로 간주하고, 다른 샘플 시간 간격 r+를 사용해서 각각 forward and backward의 (N-1)/2 frame을 균일하게 샘플링합니다.

 

(2) Spatial Transformation

각각의 frame마다 spatial transformation을 수행합니다. Figure 3을 보면 (a) Photometric transformation, (b) Geometric transformation, (c) Editing transformation 을 진행합니다. 

 

training stage에서 하나의 transformation을 랜덤하게 선택해서 positive clips에 순차적으로 적용해서 새로운 positive clips을 만듭니다. 

 

3.1.2 Video Representation Learning

 

supervised video paris가 생성되기 때문에 video representation을 학습 할때 frame-level contrastive loss를 사용합니다. feature Encoder로 위 그림과 같이 ResNet50을 사용하고 conv layer로 feature map의 channel number를 감소시킵니다. 마지막으로 average pooling 이랑 L2 normalization을 적용해서 frame-level feature를 얻습니다.

위 그림과 같이 보면 이해가 쉽습니다.

 

video representation learning의 목표는 각각의 frame의 spatial 구조를 capture하는것이고 다양한 transformation의 impact을 무시하는 것입니다. 이걸 위해서 anchor clip frame이랑 positive clip frame 사이의 distance를 최소화하고 마찬가지로 anchor/positive clip frame이랑 negative clip frame의 distance는 maximizing 합니다.

 

video representation learning은 개별 프레임으로부터 spatial structure를 encode하기 위해 사용되고

그 개별 프레임은 다음과 같이 표현합니다.

set of frame-level feature는 다음과 같이 표현합니다.

The loss function은 noise contrastive estimation loss를 사용합니다. 그리고 다음과 같이 정의합니다.

 

Noise-Constrastive Estimation

- NCE 방식은 주로 multi class 분류 문제에서 class가 너무 많아질 경우, data sample과 noise sample을 구분하는 이진 분류 문제로 변환하여 주는 것 입니다.

- 최종적으로 나온 확률을 통해 negative log-posterior distribution을 minimize하는 목적 함수를 사용합니다.

 

Pd는 실제 데이터 분포를 나타내며 Epd=1 은 IT와 IT+가 완전히 동일한 visual semantic 의미를 공유하는 것을 뜻합니다.

 

3.2. Clip-level Set Transformer Network

 

한 클립의 인접한 frame은 유사한 내용을 가지고 있기 때문에 frame-level feature는 각각 서로 높은 redundancy을 가지고 있고 보완적인 정보를 충분히 탐색하지 못합니다. 그러므로 논문에서는 frame-level feature을 clip-level feature로 aggregate합니다.

 

single clip-level feature x는 다음과 같이 정의합니다.

Figure 5. Architecture of our clip-level set transformer network

clip-level feature를 encdoe 하는 걸 Figure 5에 나오는 clip-level set transformer network를 이용합니다. 

Transformer를 다이렉트로 쓰는게 아니고 position embedding 없이 8개의 attention head를 가지고 있는 하나의 encoder layer만 사용합니다.(이 이유를 모르겠네요......실험적인 부분인가...효과만 나옵니다.)

 

이러한 접근?방법?으로 SVRTN은 2가지 abilities를 얻을 수 있다고 합니다.

1) More robust - frame permutation과 missing invariant을 통해 학습된 clip-level feature의 robustness이 증가합니다.

2) More flexbile - 더 많은 retrieval 방식을 지웒바니다. (clip-to-clip retreival 이나 frame-to-clip retrieval)

 

3.2.1 Clip-level Encoding

 

frame-level encoding이랑 비슷하게 set of clip-level features는 다음과 같이 정의 합니다.

B는 batch에 clip 개수이고 clip-level constrastive learning을 사용합니다.

loss function은 다음과 같습니다.

Pd는 실제 데이터 분포를 나타내고 Epd=1은 anchor clip과 positive clip의 visual semantic이 완전히 동일하다는 것을 의미합니다. P(D = 1|x b , xb +)는 실제 데이터 분포로부터 x와 x+의 posterior probability입니다.

Clip-level encoding은 transformer의 self-attention mechanism을 통해 video clip으로부터 frame의 보완적으로 정보를 학습 할 수 있습니다. 

 

3.2.2 Clip-level Encoding with Masked Frame Modeling

 

학습된 clip-level feature 의 robustness을 증가시키기 위해 논문에서는 한 clip의 frame을 set으로 처리하고 clip-level encoding에서 랜덤하게 일부 프레임을 마스크합니다. 프레임 블러나 클립 컷의 영향을 제거하고, 클립에 있는 임의의 프레임을 조합하여 해당 클립을 검색할 수 있도록 모델을 구동하는 것이 목표입니다. 특히 clip-level feature x가 주어지면 마스크된 프레임 모델링을 수행한 후 새로운 feature는 x0으로 표현합니다.

 

그래서 clip-level set transformer network의 final loss function은 다음과 같이 정의됩니다.

3.3. Video Similarity Calculation

1. 각 비디오에 대해 먼저 shot boundary detection을 수행하여 비디오를 shot으로 분할 한 다음 정해진 시간 간격(N초)에 따라 clpi을 shot으로 나눕니다. 
2. 연속 frame sequence는 clip-level set transformer network를 통해 clip-level feature를 생성합니다.
3. 마지막으로 clip-level feature는 이진화(In Advances in Neural Information Processing System 방법) 되어 storage cost 및 search cost를 감소시킵니다.

retrieving할때 hamming distance를 통해 clip-to-clip similarities를 계산할 수 있습니다.

M * N clip-to-clip similarity matrix이 주어지면 video similarity socre는 다음 식으로 계산이 됩니다. 

CS(i,j)는 clip i and j사이의 similarity를 나타내고 다음과 같이 계산 할 수 있습니다.

K는 전체 clip set을 가리키고 H는 hamming distance calculation을 가리킵니다.

 

*Hamming distance

- 곱집합 위에 정의되는 거리 함수이다. 대략 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지를 센다.

Ex)

• '1011101'과 '1001001'사이의 해밍 거리는 2이다. (1011101, 1001001)

• "toned"와 "roses"사이의 해밍 거리는 3이다. (toned, roses)

 

---

5. Conclusion

 

SVRTN approach을 제안한 이 논문은 video를 self-supervised learning과 함께 clip-level representation으로 encode 해서 manual annotation cost와 storage space 그리고 similarity search를 줄이는 방법을 제안합니다.

 

(1) Self-supervised video representation learning

(2) Clip-level set transformer network

 

이 두가지가 핵심 요소였습니다. 자세한 설명은 위에 있으니 생략하겠습니다.

 

논문에서 말하는 future work를 설명하자면 두가지 측면이 있습니다.

 

(1) How do design more efficinet self-supervised learning?

(2) How to transfer the motion information to RGB frames in training, but only use RGB frames in retrieval.