17. Image Retrieval VLAD - NetVLAD- Triplet Loss

Mở đầu

Tham khảo chính từ bài thuyết trình của anh Nguyễn Tuấn Nghĩa TMA 12/2022

Image Retrieval: dựa vào đặc trưng của image query để tìm các bức ảnh tương ứng trong database và xuất ra output cuối

ví dụ:

- Product Search: Tìm sản phẩm tương tự

- 3D reconstruction: dựa vào tìm vật mà xây dựng lại 3D reconstruction

- Logo Search: Tìm xem thiết kế Logo đã có hay trùng ai không

Logo image -CNN-> Spatial feature map -> flatten -> So sánh với database dạng flattened feature map

Vấn đề: - CNN chỉ trích xuất feature mà không quan tâm location -> Phép tịnh tiến translation làm 2 Logo giống nhau (nhưng 1 ở bên trái 1 ở bên phải) thành 2 feature khác nhau

-> Phụ thuộc vào vị trí (location) và hướng (orientation)

-> Homography

-> Ý tưởng: global descriptor cho toàn bức ảnh mà bỏ qua thông tin không gian (ignoring spatial information)

-> Vector of Aggregated Local Descriptor (VLAD)

VLAD

Ý tưởng: (Predefined Vocal): Bag of features (BOF)

- Ta có trước những data hoàn hảo [a, b, c, d, e]

- So sánh feature vector của tất cả chữ a trong ảnh và feature vector của chữ a hoàn hảo (Euclide distance/NN) rồi normalize lại (mean) -> 0.3 . Tương tự với b,c,d,e -> 0.7, 0.4, 0.6, 0.4

- Thấy rằng vector tổng hợp của bức 1 và bức 4 gần giống nhau -> predict là cùng 1 người (cùng 1 nguồn)

( Define khoảng cách đến những đặc trưng cụ thể)

Ví dụ sử dụng SIFT descriptor:

- Từ database, dùng Kmeans để tạo vocabulary

- Với mỗi image trong database, tính VLAD

- Tính SIFT của query image -> VLAD của query image

- dot product giữa query VLAD và database VLAD -> tìm được ảnh tương ứng (matching)

Về mặt toán:

Implement:

https://github.com/ginofft/VLAD/blob/master/demo.ipynb

Output:

- vlads.h5 : vector của toàn bộ database
- vocabs.joblib : vocabulary

Hạn chế:

- SIFT Descriptor (handcrafted descriptor) -> Khó fine-tuning theo mục đích riêng, accurate cũng kém hơn các data-based

- Nearest Neighbor: Discrete -> Không dùng backpropagation để train được

-> NetVLAD

- Retrieval Eficiency:

+ Storing million of VLAD -> memory constraint -> hashing algorithm hoặc Dimension Reduce (PCA)

+ Đi qua từng ảnh nên lâu -> Approximate Nearest Neighbors hoặc Clustering Models

- Using Local features: chưa dùng đến Local features -> Local feature với spatial information để re-rank images trong tập output VLAD

Fisher Kernel

1 phương hướng khác cho bài toán Global feature vector

1 công cụ hữu ích để biến nhiều vector có size khác nhau à independent samples về cùng 1 size cho trước. Ý tưởng là gradient của sample's likelihood về các tham số, scaled bởi inverse square root của Fisher information matrix. Thay đổi hướng của parameter space để fit hơn với observed data. Vì vậy discriminative classifiers có thể learn trong biểu diễn space mới

https://www.youtube.com/watch?v=iEOcV959J80&ab_channel=DAGMGCPR2021

Còn có thể dùng trong bài toán part features combine hay Fine-grained Recognition

Fisher Vetor Encoding: orderless encoding + variable number of feature

Miêu tả rõ hơn về mặt toán học:

Với trường hợp Gaussian distribution: -> GMM Gaussian Mixture Model

Ta thấy mọi tham số đều differenable (đạo hàm được) -> train được discriminative classifiers

Vậy, tham số ta cần optimized với gradient descent là pui, alpha và s

Đặc biệt ta phân tích về stock gradient descent ở ConvMaps of parts và Fisher vector enoding

3. EMA bias corection (giống Adam update)
Estimated GMM:

Approximate Nearest Neighbors
Tính toán khoảng cách bất đối xứng (Asymmetric distance computation) là 1 phương thức đo lường sự không giống nhau giữa 2 đối tượng

Để có good vector approximatio, k nên lớn (k=2^64 cho 64-bit code)

Thường lấy VLAD có k=16 (D =2048), xp là PCA subspace (D' =128) và indexing bởi ADC 16x8 (16-bytes code)

Về tối ưu Gradient Descent:

https://viblo.asia/p/thuat-toan-toi-uu-adam-aWj53k8Q56m
NetVLAD 2016 Generalized VLAD Layer

Mục đích đầu để cho task Large scale visual place recognition

Hướng đến 3 hướng xây dựng chính:

- Xây dựng 1 CNN end-to-end cho place recognition task. Core chính là ý tưởng VLAD cho image retrieval mà để train back propagation

- Xây dựng cơ chế mới, dựa vào weakly supervised ranking loss cho tập dataset từ Google Street View Time Machine

- Xây dựng SOTA cho performance mới

Vậy chúng ta cần giải quyết 3 vấn đề:

- Cấu trúc CNN nào tốt cho place recognition

- Làm sao thu thập đủ dữ liệu đã chú thích phù hợp

- Làm sao để train end-to-end

Method: Image representation extractor: cho ảnh Ii, biến thành fixed size vector f(Ii) -> Biểu diễn cả tập database {Ii} như vậy. Biểu diễn query image thành f(q). Predict d(q,Ii) = NN Euclide distancegiữa f(q) và f(Ii)

VLAD giữ sum of residual (difference vector giữa descriptor và cluster centre) của mỗi visual word

NetVLAD layer có thể biểu diễn như 1 meta-layer (mà có thể phát triển thành nối giữa CNN và directed acyclic graph). softmax function -> soft-assignment: 1 convolution với K filters {wk} có spatial support 1x1 và biases {bk} (1 linear layer)
và 1 convolution output qua softmax -> soft-assignment

Quan hệ với các method khác:

- Với Fisher Network (Fisher Layer + SVM) sử dụng SIFT -> chỉ có hand-crafted features, không đủ làm end-to-end trong khi ta có thể dùng CNN output layers cho NetVLAD

- Có bilinear networks, có thể dùng cho các task khác về fine-grained category-level recognition

Max pooling: VLAD thích hợp với max-pooling hơn L2-normalized

Weakly supervised triplet ranking loss: ta mong rằng image Ii* sát query image q nhất. Tức ddelta(q, Ii*) < ddelta(q, Ii) với mọi i khác. Ta thiết lập 1 ranking loss giữa training triplets {q, Ii*. Ii}

- Ta xây dựng các bộ tuples {q, {pqi}, {npj}}, với mỗi q, ta ó 1 potential positives {pqi} và 1 negative {nqj}

Baseline: là CNN conv5, có ther sử dụng Max Pooling (fmax) hoặc VLAD(fVLAD) kết hợp backbone là AlexNet, CGG-16 và method thiêu,

conv4 tức là weights của layer 4 và trước đó đã learn

Best NetVLAD: VGG16 + fVLAD whitening down size to 256-D

Implement:

Bài toán recommend video

https://www.kaggle.com/competitions/youtube8m-2018/discussion/62781 (First Prize The 2nd YouTube-8M Video Understanding Challenge) https://github.com/miha-skalic/youtube8mchallenge

NetVLAD là core model cho cả First Prize the 2nd và của First Prize của team WILLOW model tại the 1st https://arxiv.org/pdf/1706.06905.pdf

implement của anh Nghĩa: https://github.com/ginofft/NetVLAD

Triplet loss

Là 1 loại loss function dùng trong Computer Vision. Dùng để train neural network từ các biểu diễn compact feature của 1 image bằng cách kéo positives (cùng class) lại gần nhau hơn và đẩy negative (khác class) xa nhau hơn trong feature space. Mục đích là minimize khoảng cách giữa positive và maximize khoảng cách giữa negative, để learning more discriminative representation.

Điều kiện thường dùng:

- slow convergence (hôi tụ chậm)

- Bị stuck tại local minima. Mà nguyên nhân là cách xây dựng bộ triplets

Cho 1 random archor, ta xây dựng theo cặp:

- Easy Positive (Easy Pos): cùng class, gần archor

- Hard Positive (Hard Pos): cùng class, xa archor

- Easy Negative (Easy Neg): khác class, gần archor

- Hard Negative (Hard Neg): khác class, xa archor
Triplet Loss dựa vào bộ (archor, positive, negative), dù vậy không phải mọi triplet bằng nhau

- Nếu (archor, positive) và (anchor, negative) thuộc easy pos/neg -> không learn

- Không hiệu quả nếu tập hard không đủ (tỉ lệ trúng cặp hard kém)

Online Triplet Mining 2017: Để điều chỉnh vấn đề trên, triplet mining đã được sinh ra. Nó tính triplet pái trước khi chọn triplet gần đúng để train. Trong khi Offine tính embedding cảu mọi data trước training thì Online chỉ tính tại run time cho batch hiện tại

Tại sao Batch All sau đó Batch Hard?
Batch Hard:

- Chọn hardest positive

- Chọn hardest negative

- Tính hardest triplet loss cho bộ 3 này

Batch All:

- Chọn all positive

- Chọn all negative

- Tính mọi triplet loss, bỏ loss = 0, tính trung bình phần còn lại

Kinh nghiệm cho thấy nếu xài Batch Hard từ đầu thì model collapse (map đến cùng 1 điểm tại embedding space). Trong khi naive Triplet giảm hiệu quả -> Dùng Batch All đến khi convergence, sau đó dùng Batch Hard cho 1 vài epoch

Kết quả Implement

Ta thử implement và xây dựng 1 demo .ipynb từ dataset 11k ảnh:

- Tập train gồm 11 kiến trúc, mỗi kiến trúc 80 ảnh -> 880 ảnh

- Tập Validation gồm 11 kiến trúc, mỗi kiến trúc 15 ảnh -> 165 ảnh

- Train 1k ảnh này với 100 epochs BatchAll + 100 epochs BatchHard

-> Chỉ nên train 1 ít BatchHard vì corvergence rất nhanh -> có thể dẫn đến đến 1 epoch nào đó loss lên rất cao (do mẫu của adam) và bắt đầu loss khó giảm lại

- Chạy qua GPU trong 10h

Kết quả:

- loss tại epoch 1 của BatchAll