黃曉冬　孫亮

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

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

中圖分類號：TP391.41

文獻(xiàn)標(biāo)志碼：A

0引言

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

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

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

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

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

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

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

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

2.1RCEM理論分析及算法

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

2.2基于RCEM算法的圖像檢索

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

3實(shí)驗(yàn)結(jié)果及分析

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

3.1實(shí)驗(yàn)設(shè)置

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

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

3.2實(shí)驗(yàn)結(jié)果及分析

通過表2，可以看到本文所提方法能夠有效應(yīng)用于圖像檢索，當(dāng)選擇LBP特征描述符進(jìn)行降維并返回20幅圖像時(shí)，尤其在Corel-1000數(shù)據(jù)集中，RCEM比K-AOGE算法的檢索準(zhǔn)確率更高，相比不降維時(shí)的情況也相差很小，這主要是因?yàn)镽CEM同時(shí)考慮了角度和歐氏距離度量的優(yōu)化，在提取數(shù)據(jù)局部信息的同時(shí)，較好地實(shí)現(xiàn)了局部和全局的統(tǒng)一。通過表3，可以看到RCEM和K-AOGE都能夠顯著提高圖像檢索的效率，而RCEM相比K-AOGE速率略微降低，這主要是因?yàn)槠湫枰獙?shù)據(jù)集的每一個樣本數(shù)據(jù)的局部信息進(jìn)行提取和計(jì)算，因此時(shí)間復(fù)雜度有所增加。

4結(jié)語

本文深入分析了線性降維算法PCA及局部形式LPCA，針對角度優(yōu)化的全局嵌入降維算法AOGE提出了一種魯棒的余弦歐氏距離度量的降維算法RCEM，并將其用于CBIR系統(tǒng)中。RCEM采用余弦度量提取數(shù)據(jù)集的局部信息，并采用歐氏距離刻畫數(shù)據(jù)集的全局分布，實(shí)現(xiàn)了局部和全局的統(tǒng)一。基于標(biāo)準(zhǔn)數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果表明RCEM比AOGE的方法更有效，能夠提高圖像檢索的效率。

參考文獻(xiàn)：

[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]劉勝藍(lán)，閆德勤.一種新的全局嵌入降維算法[J].自動化學(xué)報(bào)，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.