Negative evidences and co-occurences in image retrieval: the benefit of PCA and whitening

Abstract

提出了一種基于短向量表征的大規模圖像檢索方法。研究了主成分分析（PCA）降維方法，并對其不同階段進行了改進。我們展示并明確利用了i)均值減法和negative evidence之間的關系，即，在兩個被比較的描述中相互缺失的視覺詞，以及ii)軸去相關性和共現現象。最后，我們提出了一種減少量化工件的有效方法，即對多個詞匯進行聯合降維。提出的技術是簡單的，但顯著和持續地改善了在壓縮圖像表征的最佳結果。在圖像分類中的補充實驗表明，該方法具有普遍的適用性。

1 Introduction

本文主要解決了文獻[1-4]中很多論文都考慮到的大規模圖像搜索和目標識別問題。更準確地說，該任務包括在大型圖像數據庫中根據視覺相似性查找與查詢圖像最相似的圖像。大多數論文依賴于bag-of-words(BOW)表征[1,5,2,3]或其衍生物，如[4]。由于計算或內存的限制，這些方法只能在一臺機器上搜索幾百萬張圖像。在本文中，我們將主要關注更可擴展的方法，根據最近在壓縮圖像表征方面的工作[6 - 8]，其中圖像描述是一個短向量，隨后使用二值化[6,9]或產品量化技術[10]對其進行壓縮編碼。在這種情況下，表現最好的方法是那些從局部特征[7,8]產生代表圖像的向量的方法，如Fisher向量[11,12,7]或它的非概率版本，即VLAD描述符[8]。與以更直接的方式從像素[13,6]計算出的全局描述技術相比，這些表示在某種程度上繼承了計算它們的局部描述符的不變性屬性(視點變化、裁剪等)。

生成短碼圖像表征的方法通常利用PCA[14]進行降維。觀察到，通過PCA reduction，BOW的性能甚至得到了改善。本文對這一現象進行了研究。主成分分析可以看作是一個兩步過程(1)以數據為中心，(2)選擇一個子空間的去相關(正交)基來最小化降維誤差。我們展示了每個步驟對檢索都有積極的影響，并且我們提供了對這種行為的解釋。在此基礎上，我們提出了簡單而有效的技術，以進一步提高BOW和VLAD表征的質量。首先，我們考慮negative evidence的作用:給定兩個BOW向量，兩個向量中jointly missing的一個視覺詞在相似性度量中應該得到更重要的信息。我們顯示了negative evidence與BOW向量中心(均值減法)的關系。其次，通過利用描述符條目的去相關性，BOW和VLAD表征得到了進一步的改進。提出了兩種補充的方法 1)對向量空間進行白化，從而解決了co-currence問題; 2)通過聯合降維來考慮多個詞匯表?，F有技術考慮了多個詞匯，例如在層次k-means[2]中，或在[15]的rank聚集技術中。相比之下，我們的方法提高了對描述圖像的固定大小的向量的搜索精度。在查詢索引結構時，內存和計算復雜度與考慮唯一詞匯表時相同。

盡管很簡單，但我們在四個流行的基準測試中的結果表明，所提出的技術一致地并顯著地改進了基于短向量的最先進的圖像搜索。最后，我們將通過在PASCAL VOC'07基準上的實驗簡要說明，更好的檢索表征也能轉化為更好的分類結果:我們從BOW獲得的短向量，并與線性分類器相結合，顯著優于與Chi-square kernel相結合的soft BOW。

本文的結構如下:在第2節介紹了上下文之后，第3節展示了co-missing視覺詞的作用，第4節利用白化技術解決了co-currence over-counting的問題。第5節將其擴展到多個詞匯表，并與最新的技術進行了比較。

2 Background and datasets

2.1 Image description Framework

Bag-of-words. 作為基準，我們首先考慮由Sivic和Zisserman[1]提出的傳統的bag-of-words表征。該表征使用以下步驟從圖像中提取全局描述向量。
1. 在圖像中檢測到感興趣的協變（covariant）區域[16,17]，并由局部d維描述符描述。我們聯合使用hessian affine檢測器和SIFT描述符[18]。
2. 產生的描述符使用所謂的“視覺詞匯（visual words）”來量化，這是通過k-means算法學習產生的“視覺詞匯”。
3.使用反文檔頻率(inverse document frequency，idf)術語計算和加權視覺單詞(大小為D = k)的出現直方圖。
4. 得到的向量隨后被歸一化。如[1]中所建議的，我們采用L2歸一化。

VLAD. 局部聚合描述符[8]的向量是Fisher向量[11]的簡化。這種表征只在步驟3中與BOW有所不同:VLAD不是視覺詞出現的直方圖，而是在大小為D = k×d 的輸出向量中積累描述符與其各自質心的差值。

Power-law normalization.VLAD和Fisher向量表征都是通過使用所謂的power-law normalization[7]改進的[19]。該簡單方法后處理了輸出圖像向量。更新后的向量v依次l2歸一化。這種后處理的影響被認為減少了多次匹配和視覺爆發的影響。在下面的例子中，我們將會考慮到β=0.5這種變體的存在，即SSR(signed square rooting)。

2.2 Efficient PCA

BOW向量和VLAD向量是高維的。例如，BOW的典型值D值在1000到100萬個分量之間，而VLAD向量為k×d 維，d為局部描述符的維數。這意味著對于典型參數d = 128和k = 512, D = 65,536。因此，用協方差矩陣法進行主成分分析是無效的，甚至是不可行的。然而，我們只需要方程5中的第一個D’第一特征向量和特征值。通過將學習集Y限制為合理數量的向量(我們使用了在第2節中介紹的學習圖像集)，我們可以使用dual gram方法(見[14]中第12.1.4段)來學習矩陣P和λ₁到λ_D'的特征值。這相當于計算n×n gram矩陣Y^?Y而不是D×D 的協方差矩陣C,并利用了這兩個矩陣之間特征分解的分析關系。特征值分解使用Arnoldi算法執行，該算法使用迭代程序計算D'個期望特征向量，即那些與最大特征值相關的特征向量。

2.3 Datasets

在文獻中廣泛使用的一些流行數據集上評估了提出的技術。

Oxford5k[21]和Paris6k[22]: 這些數據集是來自Flickr的圖片集合。55個查詢對應11個不同的建筑物，由集合中的55幅圖像中的邊界框給出。任務是檢索所有對應的建筑物。性能由[21]中定義的mean average precision(mAP)來衡量。

Holidays(+Flickr1M):此數據集包含INRIA[4]提供的個人假日照片。數據集本身包含1491個圖像。500個圖像的子集用作查詢。每個查詢與其他1490個圖像以leave-one-out的方式進行比較。為了大規模評估性能，還提供了一個從Flickr下載的100萬張圖片的干擾數據集。至于Oxford5k，其性能是通過mAP來衡量的。

University of Kentucky benchmark (UKB)。該圖像集包含10200幅圖像，對應2550個不同的對象和場景(每組4幅圖像)。每幅圖像都與其他圖像進行比較。通常的性能分數是排在前4個位置的圖像的平均數量。

對于Oxford5k和Paris數據集，我們使用了在[23]中使用的檢測器和描述符，同時在線可用的描述符已用于其他數據集。

Dataset for learning stages:我們使用獨立的數據集(與測試集沒有交集)來學習視覺詞匯表，以及用于我們技術中涉及的其他學習階段。在對holiday、Holidays+Flickr1M和UKB進行評估時，獨立數據集由Flickr的10000張圖片組成。Paris6k用于學習與Oxford5k評估相關的元數據。請注意，idf術語不涉及任何學習階段，并且是基于索引數據集統計動態應用的。

3 Exploiting evidences from co-missing words

常規的BOW表征只包含非負值，它是作為視覺詞出現次數的加權直方圖生成的。讓我們考慮BOW向量u和v之間相似度s(u, v)的余弦度量，即:

如果u_i = 0，則v_i等于或大于0時，索引i的視覺詞對個體貢獻是相同的。這兩種情況的差異只被歸一化因子||v||所考慮。這低估了零分量的重要性，其為視覺相似性提供了一些有限但重要的證據。

因此，我們提出了一個簡單的方法，以在BOW向量中更好地考慮該情況。代替從一開始就測量點u和v之間角度的方法,我們考慮在不同點m處測量得到的兩點間的角度。對m來說是meanbag-of-words向量v?的一部分，即m =α·v?是一個不錯的選擇。根據式(1)對變換后的向量計算新的余弦相似度，變換后的向量如下計算：

當α=1時，對應于減去向量均值(從一個學習集產生)。應用這種變換，如果一個特定的視覺詞在兩幅比較的圖像中都不存在(更準確地說，如果它出現的次數少于平均次數)，那么余弦相似度就會對它做出正向貢獻。因此，單詞包之間的相似性得到了改善，如圖1所示。

圖2顯示了在Holidays和Oxford5K基準度量性能時，上面修正的影響，將影響作為一個α的函數?？梢钥吹?，建議的更新提供了一些顯著的改進，特別是對于更小的詞匯表規模來說，而且計算和內存成本可以忽略不計，如下所述。

Integration within the inverted file system. inverted文件結構通過僅評估等式（1）中內積的非負元素來允許稀疏向量有效的余弦距離評估。從數據庫中所有稀疏向量中簡單地減去非稀疏向量m，會對檢索的效率和內存占用量有嚴重的負面影響。然而，使用與評估(1)相同的inverted文件結構計算新的相似度度量是可能的。相減后的余弦距離表示為：

對于數據庫中的每個文檔v，歸一化因子|| v-m ||是獨立于查詢的，因此能預先計算。因此相似度可重寫為：

點積u^?v的有效計算使用如(1)的原始inverted文件結構。v^?m這個項是獨立于查詢。因此，它是在向索引中添加BOW向量時計算和存儲的。u^?m這個項僅取決于查詢(每個查詢計算一次)，|| m ||²是一個常數。因此，盡管本文的其余部分主要考慮短向量表示，但我們必須指出，我們的shifting方法在考慮常規inverted文件實現時是有效的[1-3]，其內存和計算成本可以忽略不計。

Discussion. 從圖2可以看出，negative evidence（即上面減去均值后，原來出現次數為0或小于平均次數的值就會變為負值，這里就稱之為negative evidence）對小詞匯的影響較大，對大詞匯的影響較小。這有一個直觀的解釋。對于大型(精細)詞匯表，co-missing的視覺詞成為更常見的事件，攜帶較少的evidence，而相同的視覺詞的存在提供了強有力的證據。對于較小的詞匯量，positive evidence和negative evidence的相對權重正在發生變化。這在圖2中可以觀察到(特別是Oxford 5K數據集的圖)，圖中，隨著詞匯量的增加，α的最優值(α值越高，negative evidence的權重越大)向左側移動。

4 Co-occurrence over-counting: the benefit of whitening

利用主成分分析(PCA)直接對BOW (VLAD)向量[8]進行降維是一種獲得更短圖像向量表示的有效方法。這首先執行了數據的隱式中心化（即減去均值），因此考慮了co-missing的視覺詞，從而提高了相似度度量。其次，通過集中第一分量的矢量energy，為降維后的矢量之間的相似性提供了投影前相似度的合理近似。我們采用這種方法從BOW和VLAD表示產生短向量。

但值得注意的是，這種盲目降維忽略了一個重要現象，即co-ocurring問題。Chum等人[24]注意到，在比較兩種圖像向量表征時，co-ocurring會導致對某些視覺模式的over-count。檢測器還可以引入一些人工視覺詞的co-ocurring，例如，當一個圖像區域從不同的方向[25]被多次描述時，產生兩個不同但強烈co-ocurring的描述符。

考慮圖像全局描述符(BOW或VLAD)的學習集，根據均值中心化，用矩陣Y = [Y1 | ... | Yn] 表示。D維協方差矩陣被估計為 C = Y×Y^?。在這個矩陣中捕捉到的co-ocurring的視覺詞產生了強烈的對角響應，并傾向于出現一個特征向量與一個包含這些值的大特征值相關聯。因此，限制co-ocurring影響的一種有效方法是對數據進行白化，就像[26]獨立分量分析中所做的那樣，并通過Mahalanobis距離隱式實現。

在我們的例子中,這個whiten操作與從D到D'維的降維操作共同執行: 一個給定的圖像描述符X(BOW或VLAD)首先進行PCA投射和截斷，然后白化和重歸一化得到新向量，這就是我們的短向量圖像表征。該表征如下所示:

（PCA投射和截斷即P^TX，白化操作即上面的），重歸一化即）

其中D×D'矩陣P是由協方差矩陣C的最大特征向量組成，其中，λ_i為第i個最大特征向量所對應的特征值。因此，將降維后得到的兩個向量用歐幾里得距離進行比較，與使用Mahalanobis距離相似，但不同的是，這些向量被截斷并重新歸一化。利用余弦相似度對簡化后的向量進行比較，可以有效地進行比較。重新歸一化的步驟對于得到一個更好的比較度量來說是至關重要的(在Holidays數據集上使用重新歸一化將mAP提升了10%)。

Impact on performance.為了一致性，本文所有實驗都將矢量維數降至D' =128維。圖3給出了維度降低、SSR組件歸一化的影響，以及我們的白化技術的影響，顯示了比BOW基線有很大的改進。

Remarks:
- idf加權項不能在降維的情況下使用，只能在獨立數據集上學習。

-作為降維的一個副作用，兩個模糊的視覺詞i和j在協方差矩陣中比其他元組產生更高的值，這有利于這些視覺詞在投影向量中的相同分量的投影。從主成分分析投影重建BOW向量時可以觀察到這種現象:另一個視覺詞的分量是“幻覺”。

-對于較大的D'值，白化階段通過放大低energy分量的噪聲對性能產生負面影響。這個問題通過使用一種魯棒的PCA/whiten方法來解決。

5 Joint de-correlation of multiple vocabularies

量化效應對檢索質量的影響是眾所周知的。針對這一問題，提出了不同的解決方法，包括層次量化[2]、軟分配[22]和Hamming嵌入[4]。我們證明了多重 量化可以減輕量化效應。然而，簡單的BOW表征的串聯不僅線性地增加了內存需求，而且只略微提高了檢索結果，見圖4或[15]。不同的BOW表征具有很強的相關性。我們證明主成分分析除去了相關性，同時保留了來自不同量化的額外信息。結果超過了短圖像表征的最新效果。

（意思是簡單地將多個BOW表征串聯的優化效果是有限的，但是如果對多個詞匯表進行聯合降維到一個固定大小（128），去掉相關的詞匯，這時候的BOW表征串聯的優化效果更好）

5.1 Related work on multiple vocabularies

一些現有技術提出使用多個詞匯表來提高搜索質量，但代價是降低效率和增加內存的使用。例如，一種常見而簡單的策略就是簡單地考慮將不同的BOW向量串聯起來作為圖像表征，就像Nister等人[2]所做的那樣，他們考慮了一種層次量化方法，其中中間節點對應較小的詞匯表。[15]提出了一種基于rank聚集的后期融合技術，但需要并行存儲和查詢多個inverted文件。此外，這些技術沒有考慮詞匯表之間的關系:它們的輸出被獨立處理，而沒有考慮量化器之間的依賴關系。

一個更流行的替代方案包括使用multiple[15]或soft[22]分配。當使用inverted文件執行搜索時，這也增加了查詢時間。由于我們對大型數據庫中的圖像搜索更感興趣，因此，為了在內存中保持索引結構，關注表征的內存大小是至關重要的。

5.2 Joint reduction of multiple vocabularies

多詞匯方法的關鍵是它為不同的詞匯執行BOW向量的聯合降維,并依次應用前面章節中提到的白化技術去修正由于使用多詞匯表導致的artifacts。實際上，不同的詞匯表是冗余的:如果兩個描述符在一個詞匯表中分配給同一個視覺詞，那么有很大的概率在另一個詞匯表，他們也會被分配給同一個視覺詞，從而導致第4小節中提到的那些co-currences。

與[2]和[27]的另一個區別是我們考慮了overlapping量化器。其聯合降維，能夠比使用multiple或soft量化技術[15、22]的這些方法更好地解決量化artifacts的問題, 通過將使用Fisher向量(soft assignment based on a Gaussian mixture model)或使用VLAD（hard assignment）的多詞匯表和單一詞匯表比較得到下面展示的結果(表2)。

因此，我們建議對多詞匯表進行以下簡化:

1.BOW或VLAD向量使用SSR component-wise歸一化獨立生成(參見第2節)。忽略idf項，因為它的影響在多詞匯表中是有限的。應用SSR component-wise的歸一化方法，并對串聯的矢量進行歸一化。

2. 根據第4小節的指導原則，對不同的向量進行聯合降維和白化。

圖4顯示，多詞匯表與我們的降維技術一起使用，對BOW和VLAD表示都提供了顯著的改進，這對于固定的輸出向量D'來說也是如此。BOW使用較大的詞匯表并不一定比較小的詞匯表好:雖然在Holidays中使用單一詞匯表時，k=32k的效果更好，但是我們觀察到使用多詞匯表的效果會相反。

5.3 Merging vocabularies of different sizes

本小節的目標是解決絕對搜索質量(對于給定的向量大小)和量化代價之間的權衡問題，并提供與文獻的類似方法的比較。下面的分析主要針對BOW，因為VLAD通常使用較小的詞匯表(例如，k=256)。盡管量化成本并不依賴于數據集的大小，但它會延遲查詢(與從圖像中提取描述符一起)，這對于某些應用程序來說可能非常關鍵。參考一下，量化一個查詢圖像的2000個局部描述符成4個詞匯，每個詞匯包含k = 8,192個質心，使用高效的多線程窮舉搜索(exact)，在12個核上花費0.45秒。在這種情況下，時間與k成比例。

為了降低量化代價，我們考慮不同大小的詞匯表，使用分級k-means方法[2]和pyramid match kernel [27]方法。不同大小的詞匯具有不同的重要性，因此應適應其各自的貢獻。我們比較了四種不同的方法來調整詞匯的貢獻:

1. 所有詞匯均采用相同的單位權重。

2. 與[27]類似，詞匯表的權重與它的大小(與bins的數量)成比例。

3.我們認為權重與詞匯表大小的對數成正比。

4. 與[2]類似，在串聯所有詞匯表后，權重由idf確定。

在前三種方法(稱為“1”、“k”和“log k”)中，每個詞匯表的每個描述符首先通過SSR和L2歸一化方法進行轉換，然后乘以詞匯表的權重。將不同詞匯表的描述符進行級聯，最后對級聯后的向量進行L2歸一化。在第四種加權方案中，按照[2]中提出的方法，對詞匯表拼接后的向量進行idf加權。

表1顯示了在考慮多個固定和不同大小的詞匯表時的結果，并比較了不同的加權技術。對于固定的量化成本，在本實驗中，最佳選擇是使用不同大小的詞匯表和我們的log加權技術。但是請注意，與所有大小相同的權重相比，后者的改進僅為1%。

5.4 Comparison with the state-of-the-art

表2將我們的方法與最先進的短向量表征方法相比較。用所提出的短向量構造方法得到的結果始終優于參考結果。當我們的方法應用于BOW時比應用于VLAD時得到了更高的改進。與將20k個centroids的BOW縮減為128維[19]相比，我們的方法在使用4個大小為8k的詞匯量的BOW時，Holidays的mAP增加了14.8%，Oxford5k的mAP增加了21.9%。UKB的分數是3.19/4 (BOW reference:2.95)。因此，基于BOW的表征法與PCA-reduced的VLAD和Fisher表征法的最佳結果相比具有競爭力，而在[19]中，這些表征法的表現明顯優于BOW。通過將我們的方法應用到VLAD表征上，我們仍然獲得了比現有水平提高5.7%的效果。對UKB的改進并不顯著。

5.5 Encoding our short vectors with compact codes

使用壓縮域近似近鄰搜索技術[10]對向量進行進一步編碼時，向量越短得到的結果越好，如表3所示。使用16字節的代碼，我們在Holidays中將BOW基線的mAP增加了3.6%。在Holidays中使用VLAD(4×k=256)，我們的表現比最先進的Fisher向量[19]的mAP好2.5%。

5.6 Large scale experiments

通過合并Holidays數據集和Flickr1M干擾集，我們已經對100萬幅圖像評估了我們的方法，如[4,8]中所做的那樣。我們的方與BOW(k=200k)表征相比較(從[19]的曲線)。

結果如圖5所示。我們的方法顯著優于基線，這是通過使用僅為128維向量的圖像表征來實現的，也就是說，使用的內存比sparse BOW要少得多，后者通常每個編碼的局部描述符需要4字節。效率也比BOW好得多。通過窮舉搜索的有效實現，使用一臺3Ghz機器的12核查詢Holidays的全部500個查詢圖像需要3.08秒，這相當于每次查詢要6毫秒。這比BOW[4]報告的時間要快兩個數量級。

5.7 Improving BOW for classification

雖然本文的主要目標是考慮使用短向量進行大規模的圖像檢索，但我們報告了一些初步結果，顯示了我們的方法在使用非常短的向量和高效的線性分類器進行分類的情況下的效果。為此，我們使用我們的方法(SSR, 白化4個詞匯的聯合去相關)對BOW基線進行了改進，并與結合線性分類器的方法進行了比較。在Pascal VOC'07[28]上，在與[29]相同的協議下，我們的技術明顯優于相應的BOW:在D'=256維情況下，我們得到的mAP=46.9%，而在4k維情況下，BOW得到的mAP= 41.4%。與采用線性分類器的空間金字塔匹配(SPM，[30])的結果基本一致，但其矢量比線性分類器短100倍。

6 Conclusion

針對大尺度圖像檢索中的PCA降維問題，提出了不同的改進方法。首先，提出了一個解決方案，給予聯合non-curring的視覺詞更多的重要性，以微不足道的內存和計算復雜度代價來提高bag-of-words的圖像搜索質量。這種方法也可以集成到一個inverted文件中。然后，我們考慮了co-occurring和相關視覺詞的問題，以及降維和多詞匯的使用。這種方法產生的短向量(128維，即單個SIFT局部描述符的大小)具有很高的檢索精度，我們在流行的圖像搜索基準上的結果證明了這一點。最后，在圖像分類方面表明了該方法的通用性。

總結

以上是生活随笔為你收集整理的图像检索 PCA Whiten的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。