論文筆記 - Weighted Component Hashing of Binary Aggregated Descriptors for Fast Visual Search

• • Abstract
  • Introduction
    • WeCoHash image search framework
  • Relate Works
    • Aggregated Descriptors
    • Binary Aggregated Descriptors
    • Hashing Binary Vectors for ANN Search
  • weighted component hashing
    • problem definition
    • Binary Aggregated Descriptors
    • Image-Specific Component Selection
    • Globally Optimized Bit Selection
    • Adaptive Relevance Weighting
  • EXPERIMENTS
    • Datasets
    • Evaluation Criteria
    • Comparison Baselines
    • Comparison with the state of the art
    • Implementation Details
    • Impact of Parameters
    • Evaluation of “What to Hash” and “How to Search”
    • Comparison With the State of the Art

Abstract

本文要解決的問題：盡管計算漢明距離速度很快，但是特征比對中的線性搜尋的開銷會随着二進制描述子的長度以及資料集圖檔的數量的增加而增大。

本文提出：WeCoHash算法

解決方案：

• what to hash: 利用 image-specific component (i.e. visual word) redundancy [特定圖像部分備援] 以及 bit dependency within each component [每個部分中的 bit 依賴]，來産生具有區分性的 hash 值 for bucketing [存放hash值]
• how to search: 基于 hash 值的統計資訊，包括0-2階統計資訊，基于這些統計資訊的可适應相關權重 [根據統計資訊生成的相關性權重]

實驗結果：相同的準确度的情況下，比線性搜尋快了至少 20 倍，比 LSH 快至少 10 倍

Introduction

一般最優的圖像搜尋系統都是基于倒序索引結構的 visual vocabulary 結構，将圖像的局部特征量化為 visual words。每一個圖像表示成一個Bow直方圖的形式，并且使用倒叙索引的形式編排這些圖像。

FV 和VLAD 擴充了BoW 方法，利用了局部特征的高階統計特征。與BoW相比，他們需要的 visual vocabulary 都很少 [hundreds of visual words]

對FV和VLAD進行擴充，将FV和VLAD壓縮成為二進制聚合特征描述子，同時保持特征的可區能力，這樣可以加快漢明距離的計算速度并且能夠減少描述子的存儲大小。

為了解決移動端的搜尋問題，首先在移動端直接提取二進制聚合描述子，将其發送到服務端，在服務端使用漢明距離進行線性搜尋。

盡管在這些方式中漢明距離計算速度很快，但是計算開銷會随着描述子的長度以及資料集合的大小的增長而增長，描述子長度的增長帶來的是指數級的線性搜尋開銷。是以本文的目标是設計一種針對大規模搜尋的快速的ANN搜尋算法。

ANN 搜尋方法可以分為三種：

• tree-structured search: randomized KD-trees
• clustering: Hierarchical K-Means, Product Quantization,
• hashing

其中 tree-structured search、clustering 都是針對歐氏空間的實值 (real-valued) 描述子向量，效果不如 二進制 (binary vectors) 向量。

Hash方法，比如LSH，能通過将搜尋空間從整個資料集縮小到一個候選圖像子集的方式，顯著的減少漢明距離的計算開銷。

hash方法包含兩個步驟：離線的hash表的建構，線上搜尋。

每個hash表對應一個hash key，這個 hash key 由整個二進制向量或者二進制向量的一部分構成。每一個 hash key 對應一系列的 buckets 桶，用于倒叙索引，給資料集中的圖像建立索引。線上搜尋的時候，對于給定的搜尋圖像的二進制表示向量，根據 buckets 中的碰撞情況，可以得到圖像集合的一個子集， 然後使用整個二進制向量進行線性搜尋，也就是使用整個查詢向量和得到的圖像子集中的向量比對，得到最終的結果。

可以通過增加hash key的數量來提高準确率，但這無疑增加了搜尋時間和存儲開銷。本文提出的 WeCoHash方法使用了二進制聚合描述子的統計特性，使用這些統計特性來生成 hash keys 以及 優化政策。

為了解決二進制聚合描述子的優化hash政策，主要研究的問題是 what to hash and how to search。

• what to hash

  是為了離線建構hash表，如何生成具有區分性的hash值。

  首先說明的是，每個hash值都是二進制聚合描述子的一個子集，并不是每個bit對于區分性都表現地一樣重要，是以需要去除噪聲hash值，根據 hash 值的資訊量去除那些圖像特定備援[image specific redundancy]

  第二 使用了圖像的全局bit統計特性，那麼bit之間的互相依賴可以忽略了。是以可以降低hash 值的次元。

• how to search

  主要是為了最大化搜尋準确率，同時最小化候選圖像集合

WeCoHash image search framework

1. 提取特征聚合描述子 FV（或者 VLAD）
2. 對提取的描述子二值化，生成高維的二進制聚合描述子

3. 使用 WeCoHash 解決 what to hash and how to search

   3.1. offline: 将二進制聚合描述子分解成不連續的部分。對給定的二進制聚合描述子，挑選出那些統計特性比較靠譜的部分 component selection，然後使用 bit selection 解相關比特選擇[de-correlated bits selection] 來産生降低了次元的哈希值 dim-reduced hash value

   3.2. online: 計算可适應權重 Adaptive Relevance Weighting ，引入 score weighting 提高搜尋性能

Relate Works

Aggregated Descriptors

BoW 利用了局部特征的0-階統計特性，即統計了局部特征的個數形成了直方圖。雖然很多方法對 BoW 進行了改進，但是問題仍然存在：存儲開銷、大的索引表[大規模圖像集合情況下]

FV 利用了局部特征的高階統計特性，使用 GMM 高斯混合模型來估計局部特征的分布特性。對于一個給定的圖像，與高斯函數的參數（平均值和方差）有關的所有局部特征的梯度向量被聚合成一個向量表示。最終通過連接配接所有高斯函數的一階和二階聚合特征得到FV

Binary Aggregated Descriptors

基本想法是先建立一個中間描述子，然後将其二值化。也有直接将原始描述子二值化的方法。

Hashing Binary Vectors for ANN Search

根據二進制向量的長度，hashing 算法可以分為兩類：Single key Hashing and Multiple keys Hashing

• Single key Hashing：向量長度比較小， l≤32 l ≤ 32 ，所有建構一個hash表
• Multiple keys Hashing：建構多個hash表 l>>32 l >> 32

weighted component hashing

problem definition

将一副圖像表示成二進制聚合描述符 b∈{0,1}l b ∈ { 0 , 1 } l ，那麼可以使用漢明距離計算描述符之間的相似性。hashing 的目标就是建構一張或者多張hash表，對得到的二進制聚合描述子建立索引，并且使得再圖像搜尋中更為有效。

• what to hash 生成第 i 個hash key function hi h i ，它是從圖像的聚合描述子 b 中選取一部分 b(i) b ( i ) 得到 hi(b)=b(i),b(i)∈{0,1}z h i ( b ) = b ( i ) , b ( i ) ∈ { 0 , 1 } z

  ，bits 選取的好壞直接影響着搜尋準确度以及hash表的存儲大小

• how to search 是通過比對帶查詢圖像和圖像集合中每個 hash 值 b(i),i∈[1,s] b ( i ) , i ∈ [ 1 , s ] 得到相似值 sj s j , sj=∑i=1ss(bq(i),bj(i)),j∈[1,n] s j = ∑ i = 1 s s ( b q ( i ) , b j ( i ) ) , j ∈ [ 1 , n ]

  ， s 和 n 分别代表 hash keys(hash tables) 的個數以及圖像資料集合的大小。

Binary Aggregated Descriptors

X={x1,...,xt} X = { x 1 , . . . , x t } 表示從圖像中提取到的局部特征集合，本文使用了SIFT (RootSIFT)

RootSIFT 對SIFT中的每個元素使用了平方根。使用 PCA 将 128 維的 RootSIFT 映射到 d 次元。

FV 在訓練集上使用了有 k 個高斯函數 (visual word) 的GMM來估計局部特征的分布。 qi={wi,μi,σ2i} q i = { w i , μ i , σ i 2 }

對于每個高斯函數，關于 μi μ i 的梯度向量被聚合成一個 d 次元的向量

g(i)=∑x∈Xγ(x,i)σ−1i(x−μi) g ( i ) = ∑ x ∈ X γ ( x , i ) σ i − 1 ( x − μ i )

其中 γ(x,i)=ωipi(x)/∑kj=iωjpj(x) γ ( x , i ) = ω i p i ( x ) / ∑ j = i k ω j p j ( x )

是以 g=(g(1),...,g(k)) g = ( g ( 1 ) , . . . , g ( k ) )

可以通過将FV中的GMM替換為k-means聚類得到VLAD。相應的， g(i)=∑x∈Xi(x−μi) g ( i ) = ∑ x ∈ X i ( x − μ i )

将得到的聚合描述子二值化可得

sgn(gi)=1, s g n ( g i ) = 1 , if gi>0 g i > 0 otherwise 0

可得二進制聚合描述子 b=(b(1),...,b(k) b = ( b ( 1 ) , . . . , b ( k ) with l=kd l = k d

Image-Specific Component Selection

并不是所有的hash值都可以表示圖檔，是以要選擇其中的一部分hash key的值。

g(i)=∑x∈Xγ(x,i)σ−1i(x−μi) g ( i ) = ∑ x ∈ X γ ( x , i ) σ i − 1 ( x − μ i )

如公式中表示的，聚合特征描述子包含有針對每個 visual word 的殘差向量 g(i) g ( i ) ，每個殘差向量是根據配置設定給每個 visual word μi μ i 的局部特征聚合得到。

但是 配置設定給每個 visual word μi μ i 的局部特征 的個數會不同，配置設定給其的局部特征越少，那麼認為其包含的區分能力越小。極端情況下，沒有配置設定給其的局部特征，是以該殘差向量則全零，那麼這中情況下不應該考慮這個 visual word。由此可以引出 g(i)b(i) g ( i ) b ( i ) 都不同

那麼一個直覺的想法就是從得到的 b(i) b ( i ) 中選取一個子集，這個子集中的元素具有較高的可信度，也就是區分度。可信度定義為 soft-weighted occurence of the i-th visual word qi q i

r(i)=o(qi) r ( i ) = o ( q i )

for i-th visual word

對于連續的FV， o(qi) o ( q i ) 被定義為局部特征的後驗機率的和。

o(qi)=γ(x,i) o ( q i ) = γ ( x , i ) ， γ(x,i)=ωipi(x)/∑kj=iωjpj(x) γ ( x , i ) = ω i p i ( x ) / ∑ j = i k ω j p j ( x )

對于離散的VLAD， o(qi)=∑cj=1wj∗#(qi,j) o ( q i ) = ∑ j = 1 c w j ∗ # ( q i , j )

給定一個局部特征，根據這個局部特征對所有的 visual word 排序，第 j 個位置的 visual word 叫做 j-th 近鄰 visual word，

#(qi,j) # ( q i , j ) 代表第 j∈[1,c] j ∈ [ 1 , c ] 個最近鄰visual word 是 qi，i∈[1,k] q i ， i ∈ [ 1 , k ] 的局部特征的個數。 wj w j 是權重，本文設定為 w1=4,w2=2,w3=1 w 1 = 4 , w 2 = 2 , w 3 = 1

通過實驗驗證了， 元件的選擇對圖像比對對或者不比對對的漢明距離分布的影響。

經過元件選擇之後，更能區分比對/不比對圖像對。比對和不比對的重疊區域變小了，也就是更能區分了[為什麼區分圖像對]，證明了去除那些沒有作用 noisy 的元件是有必要的。

離線建構 hash tables，對于圖像集合中的每個圖像，它可以被表示為 b=(b(1),...,b(k)) b = ( b ( 1 ) , . . . , b ( k ) ) ，每個元件對應一個 visual word， 根據 r(i)=o(qi) r ( i ) = o ( q i ) 計算針對每個 visual word 的可信度，選取可信度較高的幾個 visual word，然後将這些 visual word 對應的 hash keys (b(i)) 用相同的hash碼存儲該圖像的 image ID，這樣就将 圖像集合中的每個圖像與 visual word 聯系起來了，每個圖像可得一張表。

線上搜尋。對待查詢圖像同樣執行元件選擇操作，然後使用選擇之後的元件執行查詢操作，在實際中，對于所有的圖像，選取的元件的個數是相同的。

Globally Optimized Bit Selection

經過元件的選擇之後，每個元件（visual word）可以被認為是一個 hash key 并且每個 hash key 的次元與 visual word 的次元相同。理想情況下， d維的 hash key 對應的hash 表中有 2d 2 d 個hash values （buckets） 如果d比較大，計算開銷和存儲開銷都會很大。是以提出了 bit選擇 進一步降低元件的次元。

一種解決方案是運用 random bit selection, 忽略了 bit 之間的相關性。

如果bit之間的相關性越小，那麼這系列bit攜帶的資訊會更多，也就是更能表示這個圖像， 類似于 “基”

給定一個元件 b(i)=(b1,...,bd) b ( i ) = ( b 1 , . . . , b d ) , 内部的bit之間的相似性為

c(bi,bj)=I(bi;bj)H(bi,bj) c ( b i , b j ) = I ( b i ; b j ) H ( b i , b j )

H(bi,bj) H ( b i , b j ) 和 I(bi;bj) I ( b i ; b j ) 分别表示 連接配接熵(joint entropy) 和 bit對 的互動資訊(mutual information)。【附錄有定義】

從 圖a中可以看出，每個bit或多或少都與其他的bit相關。

本文基于mutual information minimization [47]提出了一種 bit選擇 的全局優化方法。

對于一副圖像的第 i 個元件 b(i)∈Rd b ( i ) ∈ R d 目标是 選擇其中的 z (z<d) ( z < d ) 個bit 生成一個 hash key hi h i 。

hi={u(1),...,u(z)} h i = { u ( 1 ) , . . . , u ( z ) } 其中， u(j)∈[1,...,d] u ( j ) ∈ [ 1 , . . . , d ] （是原來的二進制描述子的下标）

全局優化的 bit 選擇問題 可以公式化為最大熵問題

hi=∗argmaxu∗(1),...,u∗(z)H(bu∗(1),...,bu∗(z)),u∗(j)∈[1,...,d] h i = ∗ a r g m a x u ∗ ( 1 ) , . . . , u ∗ ( z ) H ( b u ∗ ( 1 ) , . . . , b u ∗ ( z ) ) , u ∗ ( j ) ∈ [ 1 , . . . , d ]

也就是說找到使得熵最大的取自 原來二進制描述子中的 元件的 z 個值。

u∗(j) u ∗ ( j ) 表示從一個元件中選擇的bit的下标

bu∗(j) b u ∗ ( j ) 表示相應的bit值

這是一個組合優化問題，是以使用貪心算法進行求解

首先從元件中選擇使得熵最大的單個 bit u(1) u ( 1 )

u(1)=∗argmaxiH(bi),i∈[1,...,d] u ( 1 ) = ∗ a r g m a x i H ( b i ) , i ∈ [ 1 , . . . , d ]

然後進行疊代選擇（a+1）個bit u(a+1)=∗argmaxi∉{u(j)|1≤j≤a}∑j=1aI(bi;bu(j)),1≤a<z u ( a + 1 ) = ∗ a r g m a x i ∉ { u ( j ) | 1 ≤ j ≤ a } ∑ j = 1 a I ( b i ; b u ( j ) ) , 1 ≤ a < z

從圖4(b) 中可以看出，經過mutual information minimization 方法選取的 bit 之間的相關性更小了。

總結算法：

更詳細的了解：

Adaptive Relevance Weighting

為了解決 how to search 的問題，提出了Adaptive Relevance Weighting方法提高線上搜尋的性能，主要研究了待查詢圖像和圖像集合中圖像的hash value 之間的相關性。

有必要介紹一下 EWH(error weighted hashing) 方法：與LSH不同的是候選圖像的選擇方式不同，LSH方法中至少在一個 hash key 中，存在一個 資料圖像與待查詢圖像有相同的hash value 才能作為候選圖像【hash value 與 hash key 之間的關系？是一種東西碼】，也就是 e=0。但是 EWH方法使用的是允許hash value 之間存在 e-bit 的不同。

對每個 hash table， EWH 首先枚舉出所有的 hash values {b(r)},0≤r≤e { b ( r ) } , 0 ≤ r ≤ e ，這些hash value 與待查詢圖像 hash value 之間存在 r-bit 的不同，然後給 {b(r)} { b ( r ) } 的bucket 中的所有圖像增加一個 權重相似分數 ，對所有的 hash table 都執行這個操作，這樣就産生了 根據相似性分數排序得到的圖像清單，最後選擇相似分數最高的一些圖像作為候選圖像。但是 相似性權重隻與 漢明距離e 有關，而且是是根據經驗固定的，hash values 的統計資訊也被忽略了。

是以在此基礎上，本文提出了一種包含了 hash values 的統計資訊的賦權方式。

經過 bit選擇之後的 hash value(dim-reduced hash value) bq(i),bj(i) b q ( i ) , b j ( i ) 針對的是待查詢圖像的第 i 個元件

s(bq(i),bj(i))=∑r=0ewr(bq(i),bj(i)) s ( b q ( i ) , b j ( i ) ) = ∑ r = 0 e w r ( b q ( i ) , b j ( i ) )

其中，如果 兩個向量之間的漢明距離為 r Ha(bq(i),bj(i))=r H a ( b q ( i ) , b j ( i ) ) = r

那麼 wr(bq(i),bj(i))=log(n#(bq(i),r)) w r ( b q ( i ) , b j ( i ) ) = l o g ( n # ( b q ( i ) , r ) )

其中 #(bq(i),r) # ( b q ( i ) , r ) 表示的是在第 i 個元件相對應的hash value 的 bucket 中的 圖像的個數，這個hash value 與 bq(i) b q ( i ) 有 r bit 不同。n 是圖像集合的數目。

否則

wr(bq(i),bj(i))=0 w r ( b q ( i ) , b j ( i ) ) = 0

如圖所示：

• 【圖中下方的 表 不明白 bj(i) b j ( i ) 的實體意義是什麼？】

  指的是，計算出 wr(bq(i),bj(i)) w r ( b q ( i ) , b j ( i ) ) 之後，将這個值 加給 在這個 bucket 種的所有圖像， 也就是{x, y, z } 上，最後得到的是 圖像集合中所有圖像的相似度表

對于每個被選擇的元件，這個過程根據與 bq(i) b q ( i ) 有 r bit 不同生成的所有 hash value ，重複多次。

然後以上過程根據 被選擇的元件 重複多次，因為以上過程隻是針對被選的一個元件。

這樣就會得到 對應元件之間 的相似度

s(bq(i),bj(i))=∑r=0ewr(bq(i),bj(i)) s ( b q ( i ) , b j ( i ) ) = ∑ r = 0 e w r ( b q ( i ) , b j ( i ) )

最後根據

sj=∑i=1ss(bq(i),bj(i)),j∈[1,n] s j = ∑ i = 1 s s ( b q ( i ) , b j ( i ) ) , j ∈ [ 1 , n ]

s分别代表 hash value 的個數，也就是元件的個數，計算該圖像的相似度，

最後的最後，設定一個門檻值，然後根據門檻值選擇候選圖像，然後在候選圖像中，使用原來的 二進制描述子 計算相似度，得到最為相近的圖像。

算法總結：

算法中 Compute using look-up table and add it to that are within the corresponding buckets of hash table 表示給圖像集合中的 所有圖像 累加 相似度

.

- 關于 look-up table

因為線上搜尋中，我們需要對 所有的 漢明距離 r 以及對所有的 選取的元件 進行疊代計算，不可避免地降低了搜尋速度。是以提出了 fast look-up table 方法。

對于每個元件，枚舉所有 可能的 hash values，然後計算 不同 漢明距離 r 情況下的權重

s(bq(i),bj(i))=∑r=0ewr(bq(i),bj(i)) s ( b q ( i ) , b j ( i ) ) = ∑ r = 0 e w r ( b q ( i ) , b j ( i ) )

這樣共有 k∗2z∗(e+1) k ∗ 2 z ∗ ( e + 1 ) 個元素在表中。（ 怎麼得到的？？ k 個元件，（e+1）個bit不同，每個元件對應的hash次元為 z，是以有 2z 2 z 種選擇）

這樣線上搜尋的時候，根據給定的 query 的hash value 以及 r 可以很快得到 權重 adaptive relevance weight。

EXPERIMENTS

Datasets

• UKbench - 10,200 images with 2,550 objects， all used for reference images
• INRIA Holidays - 1,491 holiday photos, 500 for query, 991 for reference
• Stanford Mobile Visual Search (SMVS) dataset - 4,500 phone camera images, 2,800 queries and 1,700 reference
• FLICKR1M - 作為幹擾項, 1 million distractor images, merged with the reference images
• Oxford used for training ‘

Evaluation Criteria

• Search Accuracy:
  • mAP
  • STM = (number of times the top retrieved image is relevant)/( number of queries).
• Search time cost
  • T=Tbuckets+Tcandidates T = T b u c k e t s + T c a n d i d a t e s
• Memory cost
  • S=Sbuckets+Sindices S = S b u c k e t s + S i n d i c e s

Comparison Baselines

Comparison with the state of the art

• the exhaustive linear search
• the LSH algorithm
• the Uniform LSH algorithm
• the EWH algorithm
• the MIH algorithm
• the HKM
• the PQ

Implementation Details

Impact of Parameters

• Number of selected components s, fix z and e
  • 随着選擇的元件的增多， mAP增大，同時 time cost 也增大
• Number of selected bits z， fix s and e
  • 随着 z 的減小，search time 顯著減小。當 z 比較小的時候，那麼buckets （hash key）的個數就會少，那麼每個 bucket 中的圖像就會增多，就會給 最後的線性搜尋帶來很大開銷；如果 z 比較大，那麼查詢圖像和dataset圖像 沖突可能性就會降低，就會造成 mAP 降低。
  • 同時發現，當e設定比較小的時候，可以通過設定門檻值 t 來緩和 線性搜尋的開銷
• search radius e， fix s and z
  • 從0增加到2，mAP增加的效果很明顯，但是從2到3，mAP增加就不是很明顯，同時計算效率大幅度降低(計算時間增加了)。
• on the SMVS dataset

Evaluation of “What to Hash” and “How to Search”

Comparison With the State of the Art

• Performance comparison
  • mAP vs search time on INRIA Holidays, SMVS and UKbench

• Effects of the dimensionality of binary aggregated descriptors on search efficiency
  • search time vs descriptor dimensionality of WeCoHash, LSH, Uniform LSH, EWH and Linear Search over the UKbench dataset combined with 1 million FLICKR1M.
  • component(visual word) k =128, d = {16,32, 48, 64}

• Effects of database size on search efficiency
  • growth of search time with the database size
• Performance evaluation over large-scale experiments.
  • the retrieval accuracy, mAP, Top Match (STM), search time
  • LSH, Uniform LSH, EWH, MIH, HKM, PQ and Linear Search combined with 1 million FLICKR1M

    

• Memory cost
  • Table III
• Accuracy versus efficiency.

  

refer

• Weighted Component Hashing of Binary Aggregated Descriptors for Fast Visual Search