基于魯棒的余弦歐氏距離度量降維的圖像檢索方法

黃曉冬　孫亮

摘要：為解決主成分分析（PCA）無法處理非線性數據集以及魯棒性差的問題，提出一種魯棒的余弦歐氏距離度量的降維方法（RCEM）。該方法利用余弦度量（CM）能夠處理離群點的特點來提取數據的局部幾何特征，并利用歐氏距離能夠很好地保持樣本的方差信息的特點來刻畫數據集的全局分布，在保留數據局部信息的同時實現了局部和全局的統一，提高了局部降維算法的魯棒性，同時避免了局部小樣本問題。實驗結果顯示，與角度優化全局嵌入（AOGE）方法相比，在Corel-1000數據集下檢索查準率提高了5.61%，相比不降維時檢索時間減少了42%。結果表明，RCEM算法能在不降低圖像檢索精度的同時提高圖像檢索的效率，可以有效應用于基于內容的圖像檢索（CBIR）。

關鍵詞：主成分分析；余弦度量；歐氏距離；局部信息；基于內容的圖像檢索

中圖分類號：TP391.41

文獻標志碼：A

0引言

近年來，隨著多媒體技術和互聯網圖像資源的迅速發展，人們對圖像檢索的需求越來越強烈。圖像檢索技術主要分為基于文本的圖像檢索（Text-Based Image Retrieval， TBIR）和基于內容的圖像檢索（Content-based Image Retrieval， CBIR）方法。CBIR根據圖像所包含的顏色、紋理、形狀和空間位置信息等信息來描述特征，進而對高維低層視覺特征所形成的特征向量進行處理和檢索，成功克服了TBIR中存在的關鍵字描述不準確以及檢索效率不高等問題，是一種具有自動化和智能化特點的圖像檢索方法。圖像特征提取的方法有很多，其中：Ojala等[1]提出將局部二進制模式（Local Binary Pattern， LBP）作為圖像的紋理特征描述子；Liu等[2]提出的微觀結構描述子（Micro-Structure Descriptor， MSD）方法用邊緣定位來提取圖像的微觀結構；Feng等[3]提出了全局相關描述子（Global Correlation Descriptor， GCD）方法用來提取圖像的顏色和紋理特征。然而，雖然圖像特征相對于圖像的原始數據而言數據量小得多，但是這些特征向量仍具有高維的特點，其計算量是巨大的，檢索效率和速度往往讓人無法忍受。因此，對這些高維向量進行降維非常有意義。

維數約簡的本質在于尋找數據集內部固有的性質，以此來保持樣本間的一些重要關系。例如在一些線性模型中，維數約簡的主要思想就是保持樣本間的某個全局關系[4]。經典的主成分分析（Principal Component Analysis， PCA）[5]希望投影到低維PCA子空間的數據方差最大，而多維尺度變換（Multi-Dimensional Scaling， MDS）[6]則希望保持樣本間相似性最大。

針對上述線性算法難以處理非線性數據的問題，下列算法解決了非線性數據集的學習問題：局部線性嵌入（Locally Linear Embedding， LLE）算法[7]假設數據局部是線性的，通過尋找每個樣本的k最近鄰來盡可能保持數據集降維前后的局部線性結構，最終實現了對非線性數據的嵌入；隨后，Zhang等[8]提出的局部切空間排列（Local Tangent Space Alignment， LTSA）算法在LLE的基礎上對每個樣本局部進行PCA降維，對計算出的每個鄰域的局部切空間坐標進行全局排列，得到全局的低維流形。但以上算法由于缺少對數據集全局結構的把握，并且對噪聲比較敏感，容易受到奇異點的干擾，往往導致降維后數據產生嚴重的幾何形變。等距映射Isomap[9-11]在保持MDS中樣本相似性最大的基礎上，利用最短路徑近似樣本間的測地線距離，實現了局部與全局的統一。Laplacian 特征映射（Laplacian Eigenmap， LE）[12]通過利用高斯核函數構造樣本近鄰圖，得到稀疏的鄰接矩陣，使目標函數保持這種圖結構來達到降維的目的。

以上非線性降維算法分別從不同的角度刻畫了高維數據的特征，但由于采用隱式的學習方式，因此沒有明確高維到低維數據的映射關系，限制了這些算法在圖像檢索等領域的應用，導致其學習非線性數據集的優勢無法充分體現。為更好地解決實際應用問題，近幾年相繼提出了局部保持投影（Locality Preserving Projection， LPP）[13]、鄰域保持嵌入（Neighborhood Preserving Embedding， NPE）[14]、正交的鄰域保持投影（Orthogonal Neighborhood Preserving Projection， ONPP）[15]以及線性的局部切空間排列（Linear Local Tangent Space Alignment， LLTSA）算法[16]等能夠提取局部信息的線性降維算法，這些算法與已有的非線性算法相對應，將高維數據映射到低維子空間的非線性隱式映射明確為一種線性映射。

由于已知的映射關系在很多實際應用中是必要的，上述算法通過全局的線性化成為解決此問題的一種有效途徑，但往往面臨局部小樣本問題，即待分解的矩陣不可逆。PCA作為一種經典的學習方法，能夠避免上述問題；但PCA存在只能局限于處理在幾何上呈線性分布或近似線性分布的數據集以及對含噪聲的數據集的學習效果不理想的問題。

針對PCA的不足，很多學者作出了相關改進。為了提高PCA的魯棒性，De la Torre等[17]提出了Robust PCA，Choulakian[18]提出了L1-范數投影PCA；為了使PCA能夠處理非線性分布的數據集，Schlkopf等[19-20]通過將核函數引入PCA算法，并將數據映射到特征空間計算主成分，以此得到Kernel PCA；Yang等[21]提出的局部PCA（Local Principal Component Analysis， LPCA）算法，在保留數據的局部信息的同時，利用整體的線性化刻畫了數據的全局信息，從而使其能夠處理新樣本。

為了提高局部降維方法的魯棒性，同時避免局部小樣本問題，本文利用角度優化全局嵌入（Angle Optimization Global Embedding， AOGE）算法[22]魯棒性較強的特點，通過局部正交投影方法提出一種魯棒的基于角度余弦和歐氏距離度量的降維方法——RCEM（Robust Cosine-Euclidean Metric）。實驗結果表明，該方法能夠有效應用于CBIR，不僅能夠提高圖像檢索的效率，而且基本沒有降低圖像檢索的精度。

2基于RCEM算法的圖像檢索方法

2.1RCEM理論分析及算法

圖像檢索的特征數據一般采用直方圖量化特征，文獻[22]分析了在含噪聲數據中，基于角度的AOGE比PCA具有更強的抗噪能力，因此，余弦能夠發揮較好的度量效果。進一步，本文提出的RCEM算法主要利用余弦能夠處理離群點，歐氏距離能夠很好地保持樣本方差信息的特點。同時，考慮到數據集分布的復雜性，余弦部分受到LPCA[21]提取數據局部結構方法的啟發，利用局部余弦度量保持數據集度量信息的最大化，而在歐氏距離部分利用全局度量保持數據集度量信息的最大化，進而獲得更好的效果。

2.2基于RCEM算法的圖像檢索

圖2介紹了基于RCEM的CBIR系統的工作流程。CBIR先通過檢索和索引步驟提取每幅圖像的低層視覺特征向量，利用RCEM降維算法得到低維特征向量，然后與數據庫中的對應特征向量進行相似性比較，依據最接近的匹配得分得到相似的檢索圖片，最終在檢索圖片中得到目標圖片。

3實驗結果及分析

利用三種圖像檢索數據集和核AOGE（Kernel AOGE， K-AOGE）、RCEM兩種降維方法以及不降維方法對本文所提出的基于RCEM算法的圖像檢索方法進行評估?？紤]數據集特征的非線性情況，核AOGE在AOGE的基礎上加入高斯核函數。

3.1實驗設置

實驗采用的三種圖像數據集包括Corel-1000、Corel-10000和Coil-100，示例如圖3。Corel-1000包含10類總計1000張圖片，有汽車、恐龍、食物等；Coil-100數據庫共有100個物體，每個物體從0°至360°水平旋轉拍攝，共72幅圖像；Corel-10000和Coil-100比Corel-1000更大。三個數據庫的基本信息如表1所示。

在下面的實驗中，以局部二進制模式（LBP）紋理直方圖作為紋理特征給出每幅圖像的特征向量，維數為256；本文令鄰域參數k=4，d=100，α=0.65，高斯核函數寬度參數σ=1；“DR method”表示降維方法，不降維的方法標記為“DR-Free”；“檢索時間”表示檢索數據集所用的時間。

3.2實驗結果及分析

通過表2，可以看到本文所提方法能夠有效應用于圖像檢索，當選擇LBP特征描述符進行降維并返回20幅圖像時，尤其在Corel-1000數據集中，RCEM比K-AOGE算法的檢索準確率更高，相比不降維時的情況也相差很小，這主要是因為RCEM同時考慮了角度和歐氏距離度量的優化，在提取數據局部信息的同時，較好地實現了局部和全局的統一。通過表3，可以看到RCEM和K-AOGE都能夠顯著提高圖像檢索的效率，而RCEM相比K-AOGE速率略微降低，這主要是因為其需要對數據集的每一個樣本數據的局部信息進行提取和計算，因此時間復雜度有所增加。

4結語

本文深入分析了線性降維算法PCA及局部形式LPCA，針對角度優化的全局嵌入降維算法AOGE提出了一種魯棒的余弦歐氏距離度量的降維算法RCEM，并將其用于CBIR系統中。RCEM采用余弦度量提取數據集的局部信息，并采用歐氏距離刻畫數據集的全局分布，實現了局部和全局的統一?；跇藴蕯祿碌膶嶒灲Y果表明RCEM比AOGE的方法更有效，能夠提高圖像檢索的效率。

參考文獻：

[1]OJALA T， PIETIKINEN M， MENP T. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24（7）： 971-987.

[2]LIU G-H， LI Z-Y， ZHANG L， et al. Image retrieval based on micro-structure descriptor [J]. Pattern Recognition， 2011， 44（9）： 2123-2133.

[3]FENG L， WU J， LIU S， et al. Global correlation descriptor： a novel image representation for image retrieval [J]. Journal of Visual Communication and Image Representation， 2015， 33： 104-114.

https：//www.researchgate.net/publication/282408527_Global_Correlation_Descriptor_A_novel_image_representation_for_image_retrieval

[4]FENG L， LIU S-L， WU Z-Y， et al. Maximal similarity embedding [J]. Neurocomputing， 2013， 99： 423-438.

[5]JOLLIFFE I T. Principal Component Analysis [M]. New York： Springer-Verlag， 1986： 10-28.

Springer Series in Statistics

[6]SUN J， CROWE M， FYFE C. Extending metric multidimensional scaling with Bregman divergences [J]. Pattern Recognition， 2011， 44（5）： 1137-1154.

http：//xueshu.baidu.com/s？wd=paperuri%3A%28ffcd39def00552a137af1f80c7e74053%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fpii%2FS0031320310005406&ie=utf-8&sc_us=1549776567823179089

[7]ROWEIS S T， SAUL L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science， 2000， 290（5500）： 2323-2326.

[8]ZHANG Z， ZHA H. Principal manifolds and nonlinear dimensionality reduction via Tangent space alignment [J]. Journal of Shanghai University （English Edition）， 2004， 8（4）： 406-424.

SIAM Journal on Scientific Computing， 2005， 26（1）： 313-338.

http：//xueshu.baidu.com/s？wd=paperuri%3A%28c94b8b8b1f97b351da7242d84829190f%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fdl.acm.org%2Fcitation.cfm%3Fid%3D1039898%26preflayout%3Dflat&ie=utf-8&sc_us=13023074109172339473

[9]TENENBAUM J B， DE SILVA V， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science， 2000， 290（5500）： 2319-2323.

[10]BALASUBRAMANIAN M， SCHWARTZ E L. The isomap algorithm and topological stability [J]. Science， 2002， 295（5552）： 7.

[11]SAXENA A， GUPTA A， MUKERJEE A. Non-linear dimensionality reduction by locally linear isomaps [C]// ICONIP 2004： Proceedings of the 11th International Conference on Neural Information Processing， LNCS 3316. Berlin： Springer-Verlag， 2004： 1038-1043.

[12]BELKIN M， NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation [J]. Neural Computation， 2003， 15（6）： 1373-1396.

[13]HE X， NIYOGI P. Locality preserving projections [C]// Advances in Neural Information Processing Systems 16. Cambridge， MA： MIT Press， 2004： 153.

http：//www.iipl.fudan.sh.cn/～zhangjp/literatures/MLF/TR-2002-09.pdf

[14]HE X， CAI D， YAN S， et al. Neighborhood preserving embedding [C]// ICCV 2005： Proceedings of the Tenth IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2005： 1208-1213.

[15]KOKIOPOULOU E， SAAD Y. Orthogonal neighborhood preserving projections [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 29（12）： 2143-2156.

ICDM 05： Proceedings of the Fifth IEEE International Conference on Data Mining.

https：//infoscience.epfl.ch/record/87294/files/Kokiopoulou2005_1351.pdf

Pages 234-241

[16]ZHANG T， YANG J， ZHAO D， et al. Linear local tangent space alignment and application to face recognition [J]. Neurocomputing， 2007， 70（7/8/9）： 1547-1553.

[17]DE LA TORRE F， BLACK M J. Robust principal component analysis for computer vision [C]// ICCV 2001： Proceedings of the Eighth IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2001， 1： 362-369.

[18]CHOULAKIAN V. L1-norm projection pursuit principal component analysis [J]. Computational Statistics & Data Analysis， 2006， 50（6）： 1441-1451.

[19]SCHLKOPF B， SMOLA A， MLLER K-R. Kernel principal component analysis [C]// ICANN 97： Proceedings of the 7th International Conference on Artificial Neural Networks， LNCS 1327. Berlin： Springer-Verlag， 1997： 583-588.

[20]SCHLKOPF B， SMOLA A， MLLER K-R. Nonlinear component analysis as a kernel eigenvalue problem [J]. Neural Computation， 1998， 10（5）： 1299-1319.

[21]YANG J， ZHANG D， YANG J-Y. Locally principal component learning for face representation and recognition [J]. Neurocomputing， 2006， 69（13/14/15）： 1697-1701.

[22]劉勝藍，閆德勤.一種新的全局嵌入降維算法[J].自動化學報，2011，37（7）：828-835. （LIU S L， YAN D Q. A new global embedding algorithm[J]. Acta Automatica Sinica， 2011， 37（5）： 828-835.）

[23]AGGARWAL C C， YU P S. Outlier detection for high dimensional data [J]. ACM Sigmod Record， 2001， 30（2）： 37-46.

[24]YAN D， LIU S. An angle optimized global embedding algorithm [C]// FSKD 2010： Proceedings of the Seventh International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway， NJ： IEEE， 2010， 4： 1843-1847.