基於內容的圖像檢索技術綜述傳統經典方法

08-16

基於內容的圖像檢索技術綜述傳統經典方法

來自專欄 SIGAI人工智慧講堂8 人贊了文章

SIGAI特約作者
manyi
視覺演算法工程師

今天我們來介紹一下圖片檢索技術，圖片檢索就是拿一張待識別圖片，去從海量的圖片庫中找到和待識別圖片最相近的圖片。這種操作在以前依靠圖片名搜圖的時代是難以想像的，直到出現了CBIR(Content-based image retrieval)技術，依靠圖片的內容去搜圖。比較常見的圖搜平台有百度、谷歌、拍立淘等，有些圖搜技術已經能達到非常不錯的效果。接下來我們做個測試，給出一個柯基寶寶的圖片，分別用三家搜索引擎進行搜索：

圖1 原圖

圖2 百度搜索結果

圖3 谷歌搜索結果

圖4 拍立淘搜索結果

早期的圖片檢索技術都是基於文本的，需要按照圖片的名稱去搜索對應的圖片，而這樣有個很明顯的缺陷就是：大量的圖片需要人為事先去命名，這個工作量太大了。隨後漸漸出現了基於內容的圖片檢索技術，較早出現的有哈希演算法LSH(Locality-Sensitive?Hashing)，隨後圖搜這一塊逐漸豐富，從BOF -> SPM -> ScSPm ->LLC 使傳統的圖搜技術逐漸成熟。下面我們就來巴拉一下傳統圖搜技術的前世今生。

一、LSH

LSH(Locality-Sensitive?Hashing)較為官方的理解為：將原始數據空間中的兩個相鄰數據點通過相同的映射後，這兩個數據點在新的數據空間中仍然相鄰的概率很大，而不相鄰的數據點被映射到同一個桶的概率很小。也就是說，如果我們對原始數據進行一些hash映射後，我們希望原先相鄰的兩個數據能夠被hash到相同的桶內，具有相同的桶號。因此，LSH演算法使用的關鍵是針對某一種相似度計算方法，找到一個具有以上描述特性的hash函數，使得經過它們的哈希映射變換後，原始空間中相鄰的數據落入相同的桶內，那麼我們在該數據集合中進行近鄰查找就變得容易，只需要將查詢數據進行哈希映射得到其桶號，然後取出該桶號對應桶內的所有數據，再進行線性匹配即可查找到與查詢數據相鄰的數據。

上面的敘述太過理論化，那麼hash演算法具體怎麼應用到圖搜技術中呢？參照nash_同學我們列舉了三種不同的hash演算法：

(一)、平均哈希演算法(aHash)

此演算法是基於比較灰度圖每個像素與平均值來實現的，最適用於縮略圖搜索。

步驟：

1.縮放圖片：為了保留結構去掉細節，去除大小、橫縱比的差異，把圖片統一縮放到8*8，共64個像素。
2.轉化為灰度圖：把縮放後的圖片轉化為256階的灰度圖
3.計算平均值：計算進行灰度處理後圖片的所有像素點的平均值
4.比較像素灰度值：遍歷64個像素，如果大於平均值記錄為1，否則為0.
5.得到信息指紋：組合64個bit位，順序隨意保持一致性即可。
6.對比指紋：計算兩幅圖片的漢明距離，漢明距離越大則說明圖片越不一致，反之，漢明距離越小則說明圖片越相似，當距離為0時，說明完全相同。(通常認為距離>10 就是兩張完全不同的圖片)

(二)、感知哈希演算法(pHash)

平均哈希演算法過於嚴格，不夠精確，更適合搜索縮略圖，為了獲得更精確的結果可以選擇感知哈希演算法，它採用的是DCT(離散餘弦變換)來降低頻率的方法。

步驟：
1.縮小圖片：32 * 32是一個較好的大小，這樣方便DCT計算
2.轉化為灰度圖：把縮放後的圖片轉化為256階的灰度圖

3.計算DCT:DCT把圖片分離成分率的集合
4.縮小DCT：DCT是32*32，保留左上角的8*8，這些代表的圖片的最低頻率
5.計算平均值：計算縮小DCT後的所有像素點的平均值
6.進一步減小DCT：大於平均值記錄為1，反之記錄為0
7.得到信息指紋：同平均哈希演算法
8.對比指紋：同平均哈希演算法

(三)、差異哈希演算法( dHash)

相比pHash，dHash的速度要快的多，相比aHash，dHash在效率幾乎相同的情況下的效果要更好，它是基於漸變實現的。

步驟：
1.縮小圖片：收縮到9*8的大小，共72個像素點
2.轉化為灰度圖：把縮放後的圖片轉化為256階的灰度圖

3.計算差異值：dHash演算法工作在相鄰像素之間，這樣每行9個像素之間產生了8個不同的差異，一共8行，則產生了64個差異值
4.獲得指紋：如果左邊像素的灰度值比右邊高，則記錄為1，否則為0
5.對比指紋：同平均哈希演算法

二、BOW-> BOF

BOW(Bag of Words) 模型最初被用在文本分類中，將文檔表示成特徵矢量。它的基本思想是假定對於一個文本，忽略其詞序和語法、句法，僅僅將其看做是一些不同類別辭彙的集合，而文本中的每個辭彙都是獨立的。簡單說就是將每篇文檔都看成一個袋子，這個袋子裡面裝的是各種類別的辭彙，我們按照類別把整篇文檔的辭彙歸為不同的類，比如這些辭彙的類可以是槍、銀行、船、人、桌子等，然後依據每個類別中辭彙出現的頻率來判斷整篇文檔所描述的大致內容。比如一篇文檔中槍、銀行這兩類辭彙出現的概率比較高，我們就可以判斷這篇文檔和武裝押運有關，或者是關於土匪搶銀行的，兄台們可自行發揮自己的腦洞。

類比到圖像就是BOF(Bag of Features)了，以上所述的「袋子」就相當於是一副完整的圖像，而「辭彙」則相當於圖像的局部特徵(如SIFT、SURF)，先用這些局部特徵來訓練出圖像的聚類中心，訓練聚類中心的過程即相當於按照類別把文檔的辭彙歸為不同的類。在圖片檢索的時候，對圖片的每一個局部特徵用近鄰查找法找到距離它最近的聚類中心，並把此聚類中心上局部特徵的數目加一，依次遍歷每一個局部特徵後就把一副圖片映射到一個聚類中心上，即圖片的量化。最後以這些聚類中心為橫坐標，以每個聚類中心的局部特徵個數為縱坐標可以得到一個直方圖，該直方圖表示的向量就是一副圖片映射到聚類中心的BOF向量。圖片檢索的時候只要依次比較圖像的BOF向量即可找到最相似的圖片。

圖5 基於單詞包模型的圖片特徵示意圖

三、指數權重VLAD

VLAD(Vector of Aggragate Locally Descriptor)相對於BOW的差別就是，BOW是把局部特徵的個數累加到聚類中心上，而VLAD是把局部特徵相對於聚類中心的偏差(有正負)累加到聚類中心上，而且是對最相鄰的k個聚類中心都進行累加(k一般設為4左右)，這樣能很大程度地提高特徵量化的準確度，而且還能減少聚類中心的數目以提高量化速度。在累加每一個局部特徵的偏差時，實際上累加的不是一個數，而是一個局部特徵向量，比如用SIFT特徵時累加的就是一個128維的向量，這樣最終VLAD向量的維度就是128*聚類中心個數。如果聚類中心個數是256，最終的VLAD向量就是32768維。用這麼大的向量去表徵一副圖片，顯然會顯得冗餘，所以我們對直接累加的VLAD向量還要進行PCA降維，作者在使用VLAD向量的時候把它降到了512維，識別速率有了質的提升而識別率卻基本維持不變。

因為PCA降維矩陣是按照特徵值從大到小排列的，所以經過PCA降維處理後特徵向量的前幾個數據所佔的比重會比較大，要遠大於平均值，如圖6所示。這樣對特徵的提取會造成較大幹擾，因為若是前幾個數據出現了差錯，其引起的數據波動也往往比較大，在比較特徵向量相似度時就容易產生較大誤差，所以理想情況是使特徵向量中前幾個過大的數據按一定比例縮小，而使後面變化不大的數據盡量保持不變。

通過觀察特徵向量直方圖可以發現它在二維坐標上的分布類似於指數函數，如圖7a)所示為指數函數 $f(x)=e^{-x}$ ，所以考慮用圖7b)所示的指數函數 $g(x)=1-e^{-x}$

作為權重和特徵向量的每一個數據相乘。

圖6 PCA降維後的VLAD向量

圖7 指數函數

但是在權重和數據相乘的時候還會有一個問題：當x取值很接近0的時候權重值g(x)也很接近0，當權重過小時會抹掉特徵向量的前幾個數據，這樣會造成特徵向量的部分數據無效，在度量特徵向量相似度時反而會增大誤差，所以在取離散g(x)值作權重的時候不能從0開始取值而應當有一個初始值。

將圖6的特徵向量和離散權重相乘可得到新的特徵向量直方圖，如圖8所示，可見特徵向量的前幾個較大的數據被削減，而後續數據基本維持不變。

圖8 指數權重VLAD

針對權重VLAD的提升效果，我們用6類圖片做了識別率的對比：

表1 VLAD與權重VLAD的識別率對比

但是用VLAD向量做圖片檢索也存在很多缺點：首先，作為傳統的圖像識別方法，它需要手動提取特徵，再加上K-means聚類時間長，會使得演算法很繁瑣；其次在向量量化的過程中會損失特徵的精度，模板圖片的設計也顯得很粗糙，而且整個過程沒有設計反饋系統，系統無法自動升級，遷移性很差。

四、FV

FV(Fisher Vector)是一種類似於BOW詞袋模型的一種編碼方式，如提取圖像的SIFT特徵，通過矢量量化(K-Means聚類)，構建視覺詞典(碼本)，FV採用混合高斯模型(GMM)構建碼本，但是FV不只是存儲視覺詞典的在一幅圖像中出現的頻率，並且FV還統計視覺詞典與局部特徵的差異。可見FV和VLAD的差別就是FV用GMM構建碼本，而VLAD用K-Means構建碼本。

FV其實就是對於高斯分布的變數求偏導！也就是對權重、均值、標準差求偏導得到的結果，其本質上是用似然函數的梯度向量來表達一幅圖像，這個梯度向量的物理意義就是數據擬合中對參數調優的過程，下面我們來說一下GMM。

事實上，GMM和K-means很像，不過GMM是學習出一些概率密度函數來(所以GMM除了用在clustering上之外，還經常被用於density estimation )，簡單地說，K-means 的結果是每個數據點被分配到其中某一個 cluster 了，而 GMM 則給出這些數據點被分配到每個cluster的概率，從而也可以通過設置概率閾值把數據點分配到多個cluster，又稱作 soft assignment 。

但是GMM有個缺點就是計算量很大，GMM 每一次迭代的計算量比 K-means 要大許多，所以有一個更流行的做法是先用 K-means (已經迭代並取最優值了)得到一個粗略的結果，然後將其cluster作為初值傳入GMM函數，再用 GMM 進行細緻迭代。

五、SPM

由於BOW模型完全缺失了空間位置信息，會使特徵的精度降低很多，而SPM(Spatial Pyramid Matching)就在BOW的基礎上加了一個空間位置信息，也相當於在BOW的基礎上加了一個多尺度，盜用一下論文的圖：

圖9 SPM三個尺度示意圖

上圖中的點、菱形和十字架分別代表不同的局部特徵。左邊相當於原圖，中間把原圖分成了四小塊，右邊把原圖分成了16小塊，各圖的小塊大小是不一樣的，所以能體現出多尺度信息，而各小塊的位置體現出空間信息。然後對每一個小塊單獨進行聚類和量化，即相當於在多個尺度上進行BOW操作：

K是維度信息，比如單通道圖像只有行和列兩個維度，那麼K就是2。L是尺度的個數，Xm和Ym代表點集中的點，當L=0時，上式就退化為BOW了。在識別的時候我們把L=0、1、2三個尺度的圖片總共21個小塊的特徵串接起來，1+4+16=21。

關於圖像的稀疏編碼

對於二維數據，我們還可以用圖像壓縮來說明。類似於將圖像的每個像素點當作一個數據，跑一下 K-means 聚類，假設將圖像聚為k類，就會得到每類的質心centroids，共k個，然後用這些質心的像素值來代替對應的類里的所有點的像素值。這樣就起到壓縮的目的了，因為只需要編碼k個像素值(和圖像每個像素點的對這k個值得索引)就可以表示整張圖像了。當然，這會存在失真，失真的程度跟k的大小有關。最偏激的就是原圖像每個像素就是一個類，那就沒有失真了，當然這也沒有了壓縮。

(一)、VQ(vector quantization)

首先我們來巴拉一下VQ，其實VQ就是上面提到的BOW特徵量化，只不過VQ常常被用來稀疏SPM特徵：

上式中，Xi表示第i個局部特徵(如SIFT特徵)，B為聚類中心，Ci表示第i個局部特徵特徵所對應聚類中心的編碼係數。Card (Ci)=1表示每個Xi只用一個B來表示，即Ci只有一個非零分量，其餘分量全為零。雖然VQ方法得到的編碼係數足夠稀疏，但由於它把局部特徵只量化到一個聚類中心上，沒有考慮特徵的多層語義信息，導致很大的編碼誤差。

(二)、SC(Sparse coding)

為了減少向量量化的信息損失，在基於SPM模型的稀疏編碼中提出ScSPM，通過使用B的L2範數鬆弛約束條件，ScSPM的目標函數為：

上式取消了中Ci >= 0的約束條件，因此每個特徵可以用多個聚類中心進行表示。

(三)、LLC(locality-constrained linear coding)

在ScSPM之後是LLC，LLC對ScSPM的改進，在於引入了局部約束，其實也就是上文提到的VLAD向量，LLC是把特徵量化到附近的多個聚類中心，所以才有局部約束這種提法。盜用一下Jinjun Wang 論文里的圖直觀說明VQ、ScSPM和LLC三者的區別：

圖10 VQ、SC、LLC對比

上述列舉的只是傳統的圖片搜索方法，而目前主流的CBIR系統都是結合深度學習去做的，深度學習相對於傳統方法是一個質的提升。

基於內容的圖像檢索技術綜述 傳統經典方法

基於內容的圖像檢索技術綜述傳統經典方法