基於多哈希表映射誤差最小化的圖像檢索方法
2023-04-24 13:14:41 3
專利名稱：基於多哈希表映射誤差最小化的圖像檢索方法
技術領域：
本發明屬於圖像檢索技術領域，涉及到基於內容的圖像檢索方法，特別涉及到一種基於多哈希表映射誤差最小化的圖像檢索方法。
背景技術：
給定一幅查詢圖像，圖像檢索的任務是從圖像庫中找到與其相似的圖像。傳統的圖像檢索方法是將圖像表示成高維的歐氏向量，採用線性掃描圖像庫的方式進行搜索。對於海量圖像庫而言，所需的特徵存儲空間非常龐大，對圖像庫的線性搜索非常耗時。圖像哈希法通過將高維歐氏特徵編碼成簡潔的二值哈希碼，極大降低了特徵的存儲空間；同時，採用近似最近鄰法搜索相似圖像，有效得提高了搜索效率。目前，哈希方法主要有兩大類基於隨機映射的哈希法和簡潔編碼哈希法。隨機映射哈希法採用服從某種分布的隨機向量作為映射基，構造超平面對特徵空間進行分割，將分割結果作為哈希值。它的特點是，相似性大的高維向量有較大的概率獲得相同的哈希碼。但為了達到此效果，此類哈希方法需要較長的哈希碼。locality-sensitive hashing (LSH)方法[P. Indyk and R. Motwani. Approximate Nearest Neighbors :Towards Removing the Curse of Dimensionality. In ST0C，1998.]，測度學習法[P. Jain，B. Kulis， and K. Grauman. Fast image search for learned metrics. In Proceedings of CVPR, 2008]禾口 Kernelized Local-Sensitive Hashing(KLSH)法[Brian Kulis and Trevor Darrell.Learning to Hash with Binary Reconstructive Embeddings. In Neural Information Processing Systems (NIPS), 2009]是隨機映射哈希法的代表。簡潔編碼哈希法通過在高維數據的主成分方向構造線性或者非線性的哈希函數， 根據設定的閾值，可生成非常簡潔的哈希碼。在檢索時，該類方法將返回以查詢圖像的哈希碼為中心，某一距離為半徑的漢明球內所有哈希碼對應的圖像。有較高召回率要求的情況下，只需增大漢明球的半徑即可。譜哈希法(Spectral Hashing) [Y. Weiss,A. Torrelba, and R. Fergus. Spectral Hashing. In NIPS，2008]，半監督哈希法(S SH) [J. Wang, S. Kumar, and S. Chang. Semi-supervised hashing for scalable image retrieval. In proceedings of CVPR,2010]和序列映射學習哈希法(SPLH) [J. Wang, S. Kumar, and S. Chang. Sequential Projection Learning for Hashing with Compact Codes. In proceedings of ICML,2010] 是簡潔編碼哈希法的代表。
發明內容
本發明要解決的技術問題是針對海量圖像檢索時圖像特徵庫存儲空間大，檢索速度慢的問題，克服已有哈希法在較大召回率時準確率較低的不足，提出一種基於多哈希表映射誤差最小化的圖像檢索方法。本發明的技術方案是對於圖像庫中的圖像，採用特徵描述符提取特徵向量，作為待檢索特徵，並選取部分檢索特徵組成訓練特徵。計算訓練特徵的主成份方向，將訓練特徵投影到這些主成份方向上，採用迭代量化法優化得到正交矩陣，利用該正交矩陣對主成份方向進行旋轉得到新的主成份方向，將檢索特徵投影到旋轉後的主成份方向上，根據設定的閾值對投影后的檢索特徵進行量化得到其對應的哈希碼。對訓練特徵進行能量弱化作為新的訓練特徵，並重複上述過程，得到第二組哈希碼，重複該過程，直到得到第Num組哈希碼。對於查詢圖像的Num組哈希碼與待檢測圖像Num組哈希碼之間的漢明距離，利用距離大小衡量待檢索圖像與查詢圖像之間的相似性，返回相似度高的圖像。具體實現步驟包括(1)給定包含N幅圖像的圖像庫I = U1, I2,..., IN}，包含M(M<N)幅圖像的訓練庫τ = IT1, T2, ... , TJ和查詢圖像q。(2)對於圖像庫I和訓練庫T中的每一幅圖像以及查詢圖像q，利用gist描述符提取圖像的紋理特徵，每一幅圖像用一個d維特徵向量表示；圖像庫對應的所有特徵向量組成圖像特徵庫GI = (GIijGI2,.. . ,GIJ, GI e RNXd，特徵庫中的每個特徵向量GIi (1彡i彡N) 和圖像庫中的每幅圖像Ii(l < i < N) —一對應；訓練庫對應的所有特徵向量組成訓練特徵庫GT = (GT1, GT2, ... , GTmI，GT e RMXd，訓練特徵庫中的每個特徵向量GTi (1彡i彡M) 和訓練庫中的每幅圖像Ti (1彡i彡M) —一對應；查詢圖像q的特徵向量為Gq e Rlxd。(3)對於訓練特徵庫中的M個特徵向量GT，利用PCA主成份分析法提取其前K個最大特徵值對應的特徵向量W= {W1; W2，...，WK}，計算其前K維主成分向量GTp= (GTp1, GTp2, ...，GTpM}，GTp e RMXK。(4)對於GTp，定義誤差函數Er = \H -GTpxvfv其中He {0，1}MXK是二值矩陣，廠I ^irir是正交矩陣，Il · ι |F是Frobenius範數。採用迭代法求解使得Er最小時的H和V H(t) = sgn (GTp X V (t))[U, S,UT] = svd[H{t)T χ GTp)ν{ + \) = υτ其中t表示第t次迭代，sgn (·)表示符號函數，上標T表示轉置，SVd (·)是奇異值分解，[f/, S, Ut』是奇異值分解的結果。(5)對訓練特徵庫GT進行能量弱化，得到新的訓練特徵庫GT GT = GT-GTXW1XW17 (6)給定哈希表數Num，對於i = 1，. . .，Num,重複步驟(3) (5)，得到Num組參數V和R。定義哈希函數H(x) =sgn(xXVXR)。對於GIi和Gq，利用Num組參數V和R可分別獲得其對應的Num組長度為K的哈希碼。(7)定義漢明距離DHx, y = Σ xor (H (χ)，H (y))其中X0r(，)表示按位異或操作，Σ是對按位異或後的結果求和。對於查詢特徵Gq和圖像特徵庫的每個特徵GIi,計算它們Num組哈希碼之間的漢明距離的平均值1 Nwn其中ZW^表示GIi第ρ組哈希碼和Gq的第ρ組哈希碼之間的距離。根據為,，,的大小判斷圖像庫中圖像與查詢圖像之間的相似性。關於gist特徵向量的提取可參考文獻[AudeOliva,Antonio Torralba,Modeling the shape of the scene :a holistic representation of the spatial envelope, International Journal of Computer Vision, Vol.42 (3) : 145-175,2001]。本發明的效果和益處是本發明提出一種基於多哈希表映射誤差最小化的圖像檢索方法，首先根據訓練樣本確定高維向量的主成份方向，通過迭代量化對主成份方向進行旋轉，得到新的主成份方向，哈希函數定義為圖像的高維向量在新的主成份方向上的投影。 根據給定的哈希表數，對訓練樣本進行能量弱化，重複上述過程，得到多組哈希碼。這種哈希函數構造方法生成的哈希碼簡短，同時，又採用多個哈希表在相同哈希碼長的情況下可提高檢索的準確率，所以這種哈希法兼備簡潔哈希和隨機映射哈希的優點。
圖1是一種基於多哈希表映射誤差最小化的圖像檢索方法的流程示意圖。圖2是本發明用於建立訓練圖像庫的樣本圖像圖。圖3是本發明哈希表數為5時，不同哈希比特數對應的1000幅測試圖像在返回圖像數目不同時的平均準確率圖。圖4是本發明不同哈希表數，不同哈希比特數對應的1000幅測試圖像在返回前 500幅圖像時的平均準確率圖。
具體實施例方式以下結合技術方案和附圖詳細敘述本發明的具體實施方式
。步驟1.圖像庫中包含60000幅32X32像素的彩色圖像，共10類，每類6000幅， 來源於公開的CIFAR-10圖像庫。從中取出1000幅圖像作為測試樣本，其他59000幅圖像作為待檢索圖像。另外，從59000幅待檢索圖像中取出8000幅作為訓練樣本。部分圖像如圖2所示。圖像庫網址為:http://www. cs. toronto. edu/ kriz/cifar. html步驟2.將所有彩色圖像轉化為灰度圖像，提取320維的gist特徵，gist特徵主要是描述圖像的紋理屬性。待檢索特徵庫和訓練特徵庫分別為GI = (GI1, GI2, GI59000I， GI e R59000x320 和 GT = (GT1, GT2, ... , GT8000I，GT e R8000x320ogist特徵的提取過程可採用公開的matlab代碼http//people, csail. mit. edu/torralba/code/spatialenvelope/步驟3.對於步驟2中8000幅訓練圖像生成的訓練特徵GT = (GT1，GT2，…， GT8·}，利用PCA主成份分析法提取其前128個最大特徵值對應的特徵向量W= (WijW2,..., W128I，計算 GT 的前 128 維主成分向量 GTp = {GTPl, GTp2, ... , GTp8000I，GTp e R8_X128。步驟4.根據步驟3中求得的訓練樣本的主成份向量GTp，定義誤差函數
權利要求
1. 一種基於多哈希表映射誤差最小化的圖像檢索方法，其特徵在於包括如下步驟1)給定包含N幅圖像的圖像庫I= UpI2,...，IN}，包含M(M<N)幅圖像的訓練庫T =ITnT2,...，TJ和查詢圖像q;2)對於圖像庫I和訓練庫T中的每一幅圖像以及查詢圖像q，利用gist描述符提取圖像的紋理特徵，每一幅圖像用一個d維特徵向量表示；圖像庫對應的所有特徵向量組成圖像特徵庫GI = (GI1, GI2, ...，GIJ , GI e RNXd，特徵庫中的每個特徵向量GlJl彡i彡N) 和圖像庫中的每幅圖像Ii(l < i < N) —一對應；訓練庫對應的所有特徵向量組成訓練特徵庫GT = (GT1, GT2, ... , GTmI，GT e RMXd，訓練特徵庫中的每個特徵向量GTi (1彡i彡M) 和訓練庫中的每幅圖像Ti (1彡i彡M) —一對應；查詢圖像q的特徵向量為Gq e Rixd ；3)對於訓練特徵庫中的M個特徵向量GT，利用PCA主成份分析法提取其前K個最大特徵值對應的特徵向量W= {W1; W2，...，WK}，計算GT的前K維主成分向量GTp= (GTp1, GTp2, · · ·，GTpM}，GTp e Rmxk ；4)對於GTp，定義誤差函數Er = \\H-GTpxVl其中He {0，1}MXK是二值矩陣，Γ I Ririr是正交矩陣，Il · I |F是Frobenius範數；採用迭代法求解使得Er最小時的H和V H(t) = sgn (GTp X V (t))[U,S,Ut] = svd{h(tf XGTp)ν{ +\) = υτ其中t表示第t次迭代，sgn (·)表示符號函數，上標T表示轉置，svd (·)是奇異值分解函數，[ /Λ R]是奇異值分解的結果；5)對訓練特徵庫GT進行能量弱化，得到新的訓練特徵庫 GT = GT-GT XW1XW176)給定哈希表數Num，對於i= 1，. . .，Num,重複步驟(3) (5)，得到Num組參數V和 R ；定義哈希函數H(X) =Sgn(XXVXR)；對於GIi和Gq，利用Num組參數V和R可分別獲得其對應的Num組長度為K的哈希碼；7)定義漢明距離DHxjy = Σ xor(H(x),H(y))其中xor(，)表示按位異或操作，Σ是對按位異或後的結果求和；對於查詢特徵Gq和圖像特徵庫的每個特徵GIi,計算它們Num組哈希碼之間的漢明距離的平均值ι NumCi1 =——TDHfq Num P1其中^L表示GIi第ρ組哈希碼和Gq的第ρ組哈希碼之間的距離^/,，,;根據弋J勺大小判斷圖像庫中圖像與查詢圖像之間的相似性。
全文摘要
一種基於多哈希表映射誤差最小化的圖像檢索方法，屬於圖像檢索技術領域。其特徵是分別提取待檢索圖像、訓練圖像和查詢圖像的gist特徵。計算訓練特徵的主成份方向，採用迭代量化法對主成份方向進行優化，將待檢索特徵和查詢特徵投影到優化後的主成份方向上，得到其對應的哈希碼。對訓練特徵進行能量弱化得到新的訓練特徵，重複該過程，直到得到第Num組哈希碼。計算查詢圖像Num組哈希碼與待檢索圖像Num組哈希碼之間的漢明距離，根據距離大小衡量待檢索圖像與查詢圖像之間的相似性。本發明的效果和益處是克服了單哈希表在召回率較高時漢明球半徑較大的缺點，同時克服了隨機映射哈希在召回率較高時需要過多哈希表的問題。
文檔編號G06F17/30GK102508910SQ201110357850
公開日2012年6月20日 申請日期2011年11月11日 優先權日2011年11月11日
發明者付海燕, 孔祥維 申請人:大連理工大學