基于混合馬爾科夫鏈模型和擴散的圖像檢索

馮 秋 燕

(河南財經政法大學 河南 鄭州 453800)

0 引 言

圖像檢索在信息檢索中占據越來越重要的位置。就目前而言，對圖像檢索過程進行改進或優化的方法有很多，文獻[1]指出對檢索結果進行重排可以顯著提升檢索性能，這方面研究尚不成熟，本文采用混合馬爾科夫鏈模型和擴散方法基于多特征融合對圖像檢索進行研究。圖像檢索的目的是根據給定的目標圖像尋找相同或相似的圖像，其中，給定的目標圖像中并不附帶文本信息，通常是一個特定的對象，而不是一個類屬層，在類屬層面，僅需要識別對象類屬，如屬于人、動物或景色。基于局部特征的BOW[2]、SIFT描述器[3-4]，被廣泛的用于檢索系統。文獻[5-8]討論了基于BOW性能與規模的改進。文獻[9]提出了VLAD來平衡存儲足跡與檢索性能。

1 研究現狀

1.1 通過單一特征的圖像索引

文獻[2]采用了tf-idf方法，計算查詢對象和數據集圖像的BOW特征向量之間的相似性進行檢索。文獻[8]使用了繼承聚類算法構造詞匯樹以減少計算代價，并應用于大規模數據集。文獻[10-11]給予單詞更多可識別的BOW向量而不是量化描述器給一個可視化單詞。為了彌補基于標準BOW方法中空間信息的缺失，文獻[5]提出了使用SIFT描述器做圖像間的匹配。文獻[6-7,12]的查詢擴展已經被廣泛應用于檢索對象的重排。

在特征設計方面，文獻[9]提出了VLAD做聚合描述。當查詢比較少的存儲時，效果比BOW好。文獻[13]提出基于VLAD向量標記平方根，是對VLAD的改進。文獻[12]基于原始SIFT用Hellinger內核提出RootSIFT以解決標準BOW特征的突發性問題。目前還有一些基于這些工作的改進，如數據集特征聚合[14]、HSV顏色直方圖[15]等。

1.2 多重特征的圖像檢索

盡管單一特征能夠達到好的檢索結果，但融合多重特征將得到比較好的性能。因為多重特征能從不同的角度描述圖像。文獻[16]通過具體的特征將初始排列列表轉換為無向圖，對每個圖計算其K-近鄰，這樣每個圖的結點間的邊就代表了數據庫圖像間的關系。圖像間的相似性通過Jaccard相似度評估，但Jaccard相似度太粗糙，無法描述圖像間的組對關系。文獻[17]將從大型數據集中學習的屬性應用于檢索數據庫。

1.3 多重特征學習

文獻[18]利用各個特征的信息，提出了一種分層回歸算法。文獻[19]通過多重特征將多個得分矩陣分解為低秩矩陣，該矩陣附加了特定特征的稀疏誤差。

2 提出的方法

2.1 概 況

本文提出了一種受監督的數據驅動方法，融合多重特征，以圖形表示方式重排數據庫圖像。對每一個特征，給定查詢對象與初始索引圖像，構造一個無向圖，結點代表這些圖像，邊權重是圖像之間組對相似性得分。本文使用混合馬爾科夫鏈模型組合多重圖至一個圖。本文引入概率模型來計算每個特征在樸素貝葉斯公式下的重要性，采用迭代擴散算法，以減少噪聲的影響，進一步提升檢索性能。

2.2 相關概念與定理

2.2.1 相關概念

定義2易處理圖(Gm)。針對特征m，圖像間的組對關系被描述為圖，Gm=(Vm,Em,em)，其中，Vm是圖像結點集合；Em是邊；em是邊的權重，權重em是在特征m下圖像之間的相似性。

定義4轉移矩陣(P)。給定親和力矩陣T，轉移矩陣定義為P=D-1T，其中，D是第i個對角元素的對角矩陣，d(i,i)=d(Vi)，d(Vi)是融合圖中結點Vi的度。

定義5圖間轉移概率(pm′(Vi))。假設從易處理圖Gm中的結點Vi出發，其中Vi∈V，結點Vi在易處理圖Gm′中選擇路徑的概率即圖間轉移概率為pm′(Vi)。

定義6結點轉移概率(pm(Vj|Vi))。pm(Vj|Vi)=em(Vi,Vj)/dm(Vi)，其中，dm(Vi)=∑jem(Vi,Vj)是易處理圖Gm中Vi的度，易處理圖Gm的體積為圖中所有邊的權重的和，即volmV=∑Vi,Vj∈Vem(Vi,Vj)=∑Vi∈Vdm(Vi)。

定義7融合圖中結點轉移概率(pG(Vj|Vi))。pG(Vj|Vi)為融合圖G中從結點Vi到Vj的轉移概率。pG(Vj|Vi)=∑mpm(Vj|Vi)pm(Vi)。

定義8結點Vi的靜止狀態(πm(Vi))。πm(Vi)=dm(Vi)/volmV。其中，dm(Vi)是易處理圖Gm中結點Vi的度。volmV是易處理圖Gm的體積。

2.2.2 相關定理

定理1p(Vj|Vi)=e(Vi,Vj)/π(Vi)

(1)

證明：由定義5、定義6、定義7、定義8，可得：

p(Vj|Vi)=∑mpm(Vj|Vi)pm(Vi)

(2)

pm(Vj|Vi)=em(Vi,Vj)/dm(Vi)

(3)

πm(Vi)=dm(Vi)/volmV

(4)

(5)

將式(3)、式(4)、式(5)代入式(2)，可得：

(6)

融合圖中結點Vi與Vj之間邊的權重記為：

(7)

可得式(1)，證明完畢。

2.3 構造易處理圖

從所有r特征的初始檢索結果，本文完全獲得n個圖像。原始數據集可能會包含數百種圖像，由此可為每個檢索圖像得到一個查詢排列列表，由此，得到一個關于該檢索圖像的圖。本文僅選擇每個特征的排序為前L的檢索圖像根據定義2構造易處理圖Gm。前L個檢索圖像的排列列表被認為是短列表。定義所有圖的節點集合為V。對于每個易處理圖Gm，本文添加來自V但不是最初由特征m檢索的結點至圖中，連結先前的缺失結點與圖中初始檢索結點的邊也被添加。以這種方式，本文用缺失結點完成了每個易處理圖，每個易處理圖中都有相同的節點集合V，也包含了短列表中的結點間的組對關系。

因此，對r個特征，有r個圖集：

G={Gi,1≤i≤r}

(8)

根據定義3，有一組相同規模的圖像矩陣：

S={Sj,1≤j≤r}

(9)

2.4 構造多特征融合圖

在2.3節得到親和力矩陣S后，然后用這些矩陣融合圖G中的圖。親和力矩陣應當是完備的并且不是稀疏矩陣，本文采用了基于文獻[20]中啟發的混合馬爾科夫鏈模型的概率方法。

根據定義5、定義6、定義7，從一個結點出發，路徑選擇器首先選擇下一步的圖，然后選擇進入該圖或者留在本圖中，根據圖像矩陣選擇相鄰結點，如圖1所示。直觀地，p(Vj|Vi)與結點Vi和它的鄰居結點的邊相關。根據定義6，本文采用結點的度與圖的體積來計算p(Vj|Vi)。根據定義8，在這些步之后，隨機路徑選擇模型將達到一個靜止狀態。

圖1 基于兩個圖的混合馬爾科夫模型

根據定理1基于無向圖的馬爾科夫鏈模型簡化為常規化的親和力矩陣的結點集合。因此，常規化所有親和力矩陣Sm至Tm，其中：

Tm=Sm/volmV

(10)

則有:

T={Tj,1≤j≤r}

(11)

(12)

式中，p(Ij∈P)與p(Ij∈Q)分別代表圖像Ij是對給定查詢圖像相似性或不相似性的邊緣概率。

(13)

式中：

(14)

(15)

(16)

ωm(Vi)=ρm(Vi)/∑ρm(Vi)

(17)

對圖Gm中的非查詢圖像Vj，本文設置r特征的權重均為：

ωm(Vj)=1/r

(18)

由此，得到權重向量：

ωm=(ωm(V1),ωm(V2),…，ωm(Vn))T

(19)

代表Gm中所有結點的權重。融合圖T的常規化親和矩陣由下式計算：

T=∑mdiag(ωm)·Tm

(20)

式中：在diag(ωm)∈Rn×n中的第i行的對角元素與ωm(Vi)相關。

2.5 擴散過程

由2.4節可得新的親和力矩陣T，由T推斷新排序。通過對T進行擴散處理減少噪聲。方法是計算一個結點到它鄰居結點的相似性得分直至達到一種靜止狀態，本文采用迭代擴散過程提高效率。根據定義4，建立一個矩陣：

(21)

(22)

式中，PK是K-NN圖GK的轉移矩陣，PK僅由每個結點與其K個最鄰近結點的相似性得分構建，各邊的權重em(Vi,Vj)=0。

本文的融合方法的整個過程如算法1所示。

算法1基于擴散的多特征重排算法

輸入：r階親和力矩陣S={Sj}，其中，1≤j≤r；查詢圖像Ii

輸出：對Ii的重排結果

1. form=1 tordo

2.常規化Sm至Tm(見2.3節和2.4節)

4.通過式(13)，計算特定查詢置信度ρm(Vi)

5.計算式(19)中的權重向量ωm，其中，對每一個查詢結點，根據式(17)，有ωm(Vi)=ρm(Vi)/∑ρm(Vi)，非查詢結點，根據式(18)，有ωm(Vj)=1/r

6.end for

7.通過式(20)得到融合圖的親和力矩陣T

8.對T使用融合過程

9.通過對查詢結點Ii的相關的行的相似性得分的排序，得出T的新排列。

3 實 驗

3.1 實驗的建立

本文使用4個廣泛使用的數據集，Holidays[22]、UKbench[8]、Oxford5k[5]、Paris6k[10]。本文使用現有的圖像檢索系統中廣泛使用的2個局部特征和2個全局特征。對評估矩陣，在UKbench數據集上使用N-S得分[8]，在Holidays、Oxford5k、Paris6k數據集上使用平均精度(mAP)。

3.2 與已存方法的比較

首先，比較本文方法和已有的方法，見表1。在表1中，在UKbench上使用N-S得分，在其他數據集中使用mAP(in%)。“-”表示結果未報道。B、SV、MA、QE、WGC表示基準(單個特征)、空間認證[5]、多任務分配[10]、查詢擴展[6-7,12]、弱幾何一致性[22]。在本文中，使用單一特征的基準是沒有使用任何其他技術(如，空間認證(SV)，查詢擴充(QE),多重任務分配(MA)或者弱幾何一致性(WGC)等)的組對相似性的初始檢索結果。文獻[16]、文獻[17]使用了多重特征提升檢索性能。與文獻[16]、文獻[17]相比較，本文僅僅使用了相似性得分，但融合算法極大地提高了基礎性能。

表1 與目前方法的比較

在表1中，BOW在不同數據集間的所有基準中獲得了最佳的檢索性能，本文的多特征融合算法提高了所有數據集的檢索性能，并且優于其他算法。在Holidays和UKbench數據集中，得到了88.3%mAP和3.86N-S 得分。與BOW算法相比，本文的融合算法使用簡單的概率模型，將結果在Holidays上提升了14.4%、在UKbench上提升了10.3%。文獻[16]也是基于圖形融合的，在Holidays提升了9.2%(77.5%～84.6%)，在UKbench上提升了6.5%(3.54～3.77)。文獻[17]分別提升了9.6%(73.8%～80.9%)和5.4%(3.42～3.6)。與其他基于單一特征的具有復雜處理過程的方法相比，本文的融合方法僅取決于相似性得分計算查詢特定權重并執行擴散過程，利用更可靠的圖像之間的關系信息，從而產生更好的檢索結果。

在Oxford5k和Paris6k數據集中，由于視點變化大、背景混亂、ROI受限約束區域，顏色特征僅僅達到8.5% mAP和8.4%mAP。此外，VLAD和GIST性能也下降。與文獻[16]不同，本文并沒有刪除劣勢特征，無偏見的包含了融合中的所有特征。本文的融合大大提升了檢索性能。實驗揭示了本文的融合是魯棒的，并沒有被單一劣勢特征(如顏色特征)所惡化。在Oxford5k上提升了最佳基準 (BOW)13.1%，達到了76.2%mAP，性能優于文獻[17]。在Paris6k上，本文的融合將mAP從69.3%提升至83.3%，并沒有使用空間認證、查詢擴展和其他技術，相對提升了20.1%。在Oxford5k與Paris6k上，單一特征并不能夠較好地區分不同的圖像和多重特征。重排結果如圖2所示。

圖2 本文融合方法在Holidays數據集上檢索圖像的實例

圖2是由4個特征和本文融合方法在Holidays數據集上檢索圖像的例子，最左邊的圖片是查詢對象。如果檢索到的圖像與查詢具有較高相似性分數，則排名靠前，具有黑邊虛線框的圖像是正確的匹配。

4 討論與分析

4.1 評估組件

首先評估本文方法的各個組件的重要性。添加或刪除組件并測量精度變化。使用多重特征的原始親和力矩陣，可以通過選擇所有基準中最大mAP來測量精度，表示為B。融合方法標記等量權重和特定查詢權重分別為EW和QW，這些結果直接從沒有擴散的組合親和矩陣中推斷。EW和QW方法使用所有的數據集圖像。使用短列表的兩個變體表示為SL+QW和SL+EW。本文的整體框架標記為SL+QW+DP，而使用EW和SL擴散的變體表示為SL+EW+DP。在測試數據集中的比較如表2所示。

表2 本文方法中不同變量的檢索性能

續表2

QW和DP都提升了性能，同時使用適當的SL也提高了精度。具體來說，在大多數情況下，QW的結果比EW更好，顯示了從相似性得分統計得出的概率模型的有效性。并且，如果要查詢大量的相關圖像(Oxford5k和Paris6K)，需要在短列表中包含更多圖像以獲得良好的結果；否則性能會下降到最佳基準以下，因為許多相似的圖像會從融合圖中排除。相比之下，當只有幾個相似的圖像被檢索時，一個小的短列表就足夠了。因此，可以控制短列表的長度以實現計算復雜度與準確度的平衡。

4.2 評估參數

本文方法具有幾個參數需要設置：短列表L的長度，易處理圖中最近鄰居數K和用于將歐氏距離轉換為VLAD，GIST和顏色特征的相似性得分的σ，為了評估本文方法對這些參數的敏感性，本文每次改變一個參數進行實驗。關于不同L的檢索結果如表2所示，圖3(a)、圖3(b)、圖3(c)分別表示擴散過程載VLAD、GIST、顏色特征下不同σ取值的性能。圖3(d)表示擴散過程中K-NN圖中不同K值的性能圖。

圖3 評估參數性能

在表2中，UKbench的N-S得分，其他數據集的mAP(%)。只要這些參數在一個合理的范圍內，本文的方法是魯棒的、對這些參數并不敏感。

4.3 評估特征組合

本節使用不同的特征組合進行實驗，以進一步證明本文融合算法的有效性。B、V、G、C分別代表BOW、VLAD、GIST、顏色特征。圖4(a)-(d)分別表示Holidays、Ukbench、Oxford5k、Paris6k不同K值下不同特征組合的性能。在Holidays、UKbench、Oxford5k和Paris6k數據集中，VLAD+GIST+顏色特征的最佳效果分別為52.4%、2.91%、30.5%、40.3%。在大多數情況下，所有4個特征的融合組合都能獲得最佳效果，這些數據驗證了本文融合算法的有效性，并且不容易受到較差特征(指顏色特征)的影響。本文的融合并不需要對需要融合的特征的數量或者類型進行任何限制。

圖4 評估特征性能

5 結 語

本文將多特征融合與擴散引入了圖像重排算法用于圖像檢索。利用圖像之間的組對相似性得分來推斷其間的關系。基于單一特征的初始排序被描述為一個易處理圖，邊的權重是相似性得分。通過混合馬爾科夫模型將易處理圖融合，利用相似性得分統計的概率模型計算特定查詢權重。將擴散應用于融合圖以減少噪聲。本文的方法顯著并且持續地提升了基準性能，對參數的變化也是魯棒的。

下一步的工作是減少人工標注，進一步研究基于子模型目標函數的完全無監督的重排算法，可以通過貪心算法進行有效的優化，基于此，研究一個更明確的有針對性的應用程序。

參考文獻

[1] 周曄,張軍平.基于多尺度深度學習的商品圖像檢索[J].計算機研究與發展,2016 54(8):1824-1832.

[2] Sivic J, Zisserman A. Video Google: A Text Retrieval Approach to Object Matching in Videos[C]// IEEE International Conference on Computer Vision. IEEE Computer Society, 2003:1470.

[3] Qin D, Wengert C, Gool L V. Query Adaptive Similarity for Large Scale Object Retrieval[C]// IEEE Conference on Computer Vision and Pattern Recognition. IEEE Computer Society, 2013:1610-1617.

[4] Douze M, Sandhawalia H, Amsaleg L, et al. Evaluation of GIST descriptors for web-scale image search[C]// ACM International Conference on Image and Video Retrieval. 2009:1-8.

[5] Philbin J, Chum O, Isard M, et al. Object retrieval with large vocabularies and fast spatial matching[C]// Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE Conference on. IEEE, 2007:1-8.

[6] Chum O, Mikulik A, Perdoch M, et al. Total recall II: Query expansion revisited[C]// Computer Vision and Pattern Recognition. IEEE, 2011:889-896.

[7] Chum O, Philbin J, Sivic J, et al. Total Recall: Automatic Query Expansion with a Generative Feature Model for Object Retrieval[C]// IEEE, International Conference on Computer Vision. IEEE, 2007:1-8.

[8] Nister D, Stewenius H. Robust Scalable Recognition with a Vocabulary Tree[J]. Proc Cvpr, 2006, 2(10):2161-2168.

[9] Jégou H, Douze M, Schmid C, et al. Aggregating local descriptors into a compact image representation[C]// Computer Vision and Pattern Recognition. IEEE, 2010:3304-3311.

[10] Philbin J, Chum O, Isard M, et al. Lost in quantization: Improving particular object retrieval in large scale image databases[C]// 2008 IEEE Conference on Computer Vision and Pattern Recognition. 2008:1-8.

[11] Jegou H, Douze M, Schmid C. On the burstiness of visual elements[C]// Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009:1169-1176.

[13] Jégou H, Perronnin F, Douze M, et al. Aggregating local image descriptors into compact codes[J]. IEEE Trans Pattern Anal Mach Intell, 2012, 34(9):1704-1716.

[14] Tolias G, Avrithis Y, Jégou H. To Aggregate or Not to aggregate: Selective Match Kernels for Image Search[C]// IEEE International Conference on Computer Vision. IEEE, 2014:1401-1408.

[15] Mikulík A, Perdoch M, Chum O, et al. Learning a Fine Vocabulary[M]// Computer Vision - ECCV 2010. Springer Berlin Heidelberg, 2010:1-14.

[16] Zhang S, Yang M, Cour T, et al. Query specific fusion for image retrieval[C]// European Conference on Computer Vision. Springer-Verlag, 2012:660-673.

[17] Zhang S, Yang M, Wang X, et al. Semantic-Aware Co-indexing for Image Retrieval[C]// IEEE International Conference on Computer Vision. IEEE Computer Society, 2013:1673-1680.

[18] Yang Y, Song J, Huang Z, et al. Multi-Feature Fusion via Hierarchical Regression for Multimedia Analysis[J]. IEEE Transactions on Multimedia, 2013, 15(3):572-581.

[19] Ye Guangnan, Liu Dong, Jhuo I-Hong, et al. Robust late fusion with rank minimization[C]// Computer Vision and Pattern Recognition. IEEE, 2012:3021-3028.

[20] Qin D, Gammeter S, Bossard L, et al. Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[C]// Computer Vision and Pattern Recognition. IEEE, 2011:777-784.

[21] Yang X, Koknar-Tezel S, Latecki L J. Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval[C]// Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009:357-364.

[22] Jegou H, Douze M, Schmid C. Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search[M]// Computer Vision-ECCV 2008.OAI,2008:304-317.