一種基于全局和局部特征匹配的流形對齊算法

徐 猛，王 靖

(華僑大學計算機科學與技術學院，福建 廈門 361021)

1 引言

隨著科學技術的飛速發(fā)展，現(xiàn)實中所獲取、存儲和需要處理的數(shù)據(jù)往往以非結構化的形式存在于高維觀察空間中，如高分辨率圖像數(shù)據(jù)、金融統(tǒng)計數(shù)據(jù)、視頻音頻數(shù)據(jù)、全球氣候數(shù)據(jù)及網(wǎng)絡文本數(shù)據(jù)等。這些數(shù)據(jù)不僅數(shù)據(jù)量龐大，而且更新速度快。因此，它們的內在規(guī)律往往難以直接觀察和學習，使得原有的機器學習[1]算法很難對這些數(shù)據(jù)進行有效的處理。

如何在保持信息完整的情況下從大量數(shù)據(jù)中提取有效信息，發(fā)現(xiàn)其內在規(guī)律，一直是模式識別和機器學習研究的熱點問題。

近年來，流形學習[2,3]在高維數(shù)據(jù)降維和數(shù)據(jù)可視化方面取得了巨大成功。這些算法包括等距映射算法(Isomap)[4]、局部線性嵌入算法LLE(Locally Linear Embedding)[5]、局部切空間排列算法LTSA(Local Tangent Space Alignment)[6]、拉普拉斯特征映射LE(Laplacian Eigen maps)[7]等。盡管這些流形學習算法在機器學習、模式識別、計算機視覺等領域得到了廣泛應用，但是只能學習分布于單個流形數(shù)據(jù)的非線性特征。在現(xiàn)實世界的許多應用中，如跨語言信息檢索[8 - 10]、姿態(tài)估計[11]、圖像和文本的匹配[12]等，數(shù)據(jù)分布于多個不同流形，需要同時學習兩個或者更多的數(shù)據(jù)集的非線性特征。此時，傳統(tǒng)的流形學習算法并不適用。

為了解決這個問題，近年來學者們提出了流形對齊算法[13 - 15]。多數(shù)流形對齊算法首先學習每個流形數(shù)據(jù)集的局部幾何結構，如局部近鄰關系[16]、稀疏重構權[17]或基于測地距離的全局幾何結構[18]；然后，利用已知數(shù)據(jù)集之間的對應點信息[19]或樣本點的幾何結構[18,20,21]挖掘不同數(shù)據(jù)集樣本點之間的關聯(lián)性；最后，將不同的流形數(shù)據(jù)集投影到共同的低維空間中，并在低維空間中從特征層[3,18]或實例層[22]保持每個流形的局部幾何結構和不同數(shù)據(jù)集之間樣本點的關聯(lián)性。

雖然流形對齊已在機器學習的許多領域中得到有效應用，但現(xiàn)有的流形對齊算法面臨一個普遍的挑戰(zhàn)。當數(shù)據(jù)集之間的對應點信息不充分時，僅僅利用流形數(shù)據(jù)的局部結構[20,21]或全局結構[18]難以準確挖掘不同數(shù)據(jù)集樣本點之間的關聯(lián)性。而這往往導致了不同流形數(shù)據(jù)集的樣本無法在低維空間中準確對齊。因此，本文提出一種基于全局和局部特征匹配的流形對齊算法。首先，計算不同流形樣本點之間的測地距離，并以此表示樣本點之間的關聯(lián)性；然后，構造每個流形樣本點的局部結構，并基于局部結構計算樣本點之間的相似性；最后，利用樣本點之間局部特征的相似性對不同流形樣本點之間的測地距離進行修正，從而更為準確地挖掘不同流形樣本點之間的關聯(lián)性。

本文其它章節(jié)安排如下：在第2節(jié)中，簡單回顧了一種保持全局結構的流形對齊算法PGGMA(Preserving Global Geometry for Mainfold Alignment)，并提出了該算法的不足之處；在第3節(jié)中，提出了基于PGGMA的改進算法,即基于全局和局部特征匹配的流形對齊算法；在第4節(jié)中，通過實驗驗證了本文算法的有效性；最后，對本文算法進行了總結和展望。

2 保持全局結構的流形對齊算法

2.1 算法回顧

在這一節(jié)中，對PGGMA算法做簡單回顧。給定兩個采自流形X和Y上的數(shù)據(jù)集X={x1,…,xm}，Y={y1,…,yn}，其中X∈Rpx×m,Y∈Rpy×n,px、py分別表示數(shù)據(jù)集X和Y中樣本點的維度。PGGMA為半監(jiān)督流形學習算法，需要預先給定部分樣本點的對應信息作為先驗知識。假設X、Y中給定的對應點表示為，xai?ybi，ai∈[1,m],bi∈[1,n],i∈[1,l],其中l(wèi)是給定的對應點個數(shù)。PGGMA算法首先估計每個樣本點到其余樣本點的測地距離，并以此表示樣本點的全局幾何結構，然后將所有樣本點投影到一個共同的低維空間，并在低維空間中盡可能地保持樣本點的全局幾何結構。算法主要包括下面三個步驟：

(1)

由于xi與yj的維度不同，無法直接計算兩者之間的距離。在文獻[18]中，利用對應點xau?ybu,u∈[1,l]構造xi與yj間測地距離最短的通路，并以此計算xi與yj的測地距離，即:

(2)

(3)

的最大d個特征值以及對應的特征向量γ=[γ1,…,γd]。記[α,β]T=[γ1,…,γd]，則可以獲得線性映射α和β，以及X和Y在d維空間中的投影坐標αTX和βTY。

2.2 存在的問題

在PGGMA算法中，算法的核心在于如何有效地聯(lián)結兩個不同流形。PGGMA利用式(2)估計兩個流形樣本點之間的測地距離，用于聯(lián)結兩個不同的流形。但是，當給定少量對應點時，這種測地距離的估計方式可能無法準確反映不同流形樣本點之間的關聯(lián)性。接下來，本文以一個模擬例子來說明這個問題。

假設數(shù)據(jù)集X和Y采自于兩條不同的曲線，即:

yi=[0.5sin(tj),0.5cos(tj)]T,

已知兩個數(shù)據(jù)集中有三組對應點x10?y10、x70?y70、x130?y130，如圖1所示。基于這三組對應點并利用式(2)可以計算出所有xi與yi之間的距離。比如，x17和y20、x20和x20之間的距離為:

Figure 1 Manifold curves X and Y圖1 流形曲線X和Y

從計算結果看，x17和y20的距離小于x20和y20之間的距離，即x17和y20更有可能是匹配點。但實際上，x20和y20是對應點。

從這個例子可以看出，當已知的對應點信息不夠充分時，按照式(2)估計的測地距離難以準確聯(lián)結兩個流形。

3 基于全局和局部特征匹配的流形對齊算法

(4)

(5)

其中，φ是正則化參數(shù)，和分別表示曲線和的梯度。在本文的實驗中，φ固定設置為1。從式(4)和式(5)可以看出，如果xi和yj具有相似的局部結構，則會較小，從而減小xi和yj的距離。

Figure 2 Alignment results of several manifold alignment algorithms on FacePix data set圖2 幾種不同流形對齊算法在FacePix數(shù)據(jù)集上的對齊結果

在新的距離計算公式下，x20和y20之間距離小于x17和y20，表明x20比x17更有可能是y20的匹配點。這說明綜合利用樣本點的全局和局部特征，能更好地聯(lián)結兩個不同流形。

4 數(shù)值實驗

為了體現(xiàn)本文算法的有效性，本文在FacePix和COIL-20兩個實際數(shù)據(jù)集上，同三種半監(jiān)督的算法PGGMA[18]、PAMA(Procrustes Analysis for Manifold Alignment)[22]、SSMA(Semi-Supervised Manifold Alignment)[19]和一種非監(jiān)督的算法UNMA(UN-supervised Manifold Alignment)[21]進行實驗對比。

4.1 度量方式和參數(shù)設置

本文實驗目的是對目標領域數(shù)據(jù)集X={xi|i=1,…,m}和輔助領域的數(shù)據(jù)集Y={yj|1,…,n}中的圖像進行匹配。對目標領域中的圖像xi，如果輔助領域數(shù)據(jù)集中的圖像yj是其在低維投影空間的最近點，則yj是xi的匹配圖像。記θxi和θyj為圖像xi與yj中人臉或物體的旋轉角度。如果|θxi-θyj|≤θ，則yj為xi的準確匹配圖像。為了量化圖像匹配的結果，本文提出匹配準確率和平均角度差兩種度量方式：

其中，n是目標領域圖像的數(shù)目。

鄰域參數(shù)k和目標維度d是本文算法和對比算法PGGMA、PAMA、SSMA均涉及的參數(shù)。在本文實驗中，均設置k=10,d=10。

4.2 FacePix人臉圖像數(shù)據(jù)集

在這個實驗中，將流形對齊算法用于人臉姿態(tài)的對齊。所用到的圖像數(shù)據(jù)來自于FacePix人臉圖像數(shù)據(jù)，一共含有30個人不同人臉姿態(tài)下的圖像。本文選取其中兩組男女頭像進行對比實驗。每組數(shù)據(jù)集包含181個128*128規(guī)模的圖像，由攝像機圍繞頭部從-90°旋轉到+90°，每間隔1°拍攝而成。將每張圖像縮小成32*32圖像，再進行向量化，由此得到兩個1024*181的數(shù)據(jù)集。

假設兩個數(shù)據(jù)集已知對應點有6個，采用流形對齊算法將兩個數(shù)據(jù)集投影到共同的10維空間。圖2列出了本文算法和PGGMA、PAMA、SSMA、UNMA的匹配結果。圖中用黑色加粗邊框標注出錯誤匹配的圖像，即與原圖像的角度差大于10°的匹配圖像。本實驗中，由于無監(jiān)督算法UNMA只利用樣本點的局部幾何結構進行匹配，實驗結果并不理想。在半監(jiān)督算法中，本文算法明顯優(yōu)于其余算法，能很好地在輔助領域中尋找到目標領域圖像的匹配點。進一步地，本文設計實驗對匹配結果進行量化。圖3a列出了角度差從0°到10°變化時，幾種算法的圖像匹配準確率。顯然，在不同的角度差下，本文算法的圖像匹配準確率明顯高于其它流形對齊算法。

Figure 5 Alignment results of several manifold alignment algorithms on the objects obj1 and obj13 from the COIL-20 database圖5 幾種流形對齊算法在COIL-20數(shù)據(jù)庫上目標obj1和obj13的對齊結果

Figure 3 Maching accuracies on FacePix data set圖3 FacePix數(shù)據(jù)集上的匹配準確率

衡量半監(jiān)督流形對齊算法性能的一個重要指標是算法對先驗信息的依賴性。本文設計實驗以驗證半監(jiān)督流形對齊算法在給定不同個數(shù)對應點情況下的效果。圖3b列出了幾種半監(jiān)督流形對齊算法在對應點個數(shù)從2到10時的圖像匹配準確率(角度差θ=5)。從圖3中可以看出，PGGMA、PAMA、SSMA對先驗信息有較高的要求。要達到60%的匹配準確率，三種算法分別要求給定9個、6個和10個對應點作為先驗信息。而本文算法在少量先驗信息的情況下(l=3)，圖像匹配準確率就可以超過80%。這主要是因為本文算法綜合樣本點的局部特征和全局特征以聯(lián)結不同流形。當獲取的先驗信息不充分時，這比只依賴給定對應點聯(lián)結流形具有更高的可靠性。

4.3 COIL-20數(shù)據(jù)庫

在這個實驗中,將流形對齊算法用于COIL-20數(shù)據(jù)庫。此數(shù)據(jù)庫由20個不同物體在不同旋轉角度下的圖像構成。相機圍繞物體旋轉360°，每次旋轉5°共拍攝72幅128*128大小的圖像。本實驗選擇7個不同的物體進行實驗，物體圖像見圖4。將每張圖像縮小為32*32規(guī)模，再轉化成一個1 024維向量，這樣得到7個規(guī)模為1024*72的數(shù)據(jù)集。

Figure 4 Seven experiment objects in the COIL-20 database圖4 COIL-20數(shù)據(jù)庫中的七個實驗目標

本文首先用obj1和obj13進行可視化匹配效果實驗。給定7個對應點，采用不同流形對齊算法將兩個數(shù)據(jù)集投影到共同的10維空間。圖5列出了本文算法和PGGMA、PAMA、SSMA、UNMA的匹配結果。圖中用黑色加粗邊框標注了錯誤匹配的圖像，即與原圖像角度差大于15°的匹配圖像。顯然，本文算法能在obj13中找到所列出的obj1匹配圖像。進一步地，本文對匹配結果進行量化實驗。圖6a列出了幾種算法在角度差θ從0°到25°的圖像匹配準確率。如圖6所示，本文算法的匹配準確率高于其它流形對齊算法。當θ=20°時，本文算法的匹配準確率超過90%。

Figure 6 Maching accuracies on COIL-20 database圖6 COIL-20數(shù)據(jù)庫上的匹配準確率

本文算法和PGGMA、PAMA、SSMA、UNMA等算法都涉及到目標維度參數(shù)d。本文設計實驗以驗證不同流形對齊算法對參數(shù)d的敏感性。給定l=7個對應點并固定角度差θ=15°，圖6b列出了不同流形對齊算法在d從5增大到45時的圖像匹配準確率結果。顯然，本文算法在不同d下的結果均明顯優(yōu)于其它算法。更重要的是，當d從10增大到45時，本文算法的結果變化不大。

這表明本文算法對參數(shù)并不敏感。

最后，本文將obj1對應的數(shù)據(jù)集作為目標數(shù)據(jù)集，obj2、obj3、obj4、obj7、obj9、obj13等6個物體對應的數(shù)據(jù)集作為輔助數(shù)據(jù)集進行對齊實驗。給定l=5,8,11等不同個數(shù)的對應點，表1列出了本文算法和PGGMA、PAMA、SSMA、UNMA在這6個輔助數(shù)據(jù)集上的平均角度差。顯然，越小的平均角度差意味著越好的對齊效果。從表1可以看出，所有算法在6個輔助數(shù)據(jù)集上的平均角度差都隨著l的增大而減小。這表明對應點個數(shù)的增加能幫助流形對齊算法更好地聯(lián)結不同流形。值得注意的是，當只給定很少的對應點時(l=5)，本文算法在6個輔助數(shù)據(jù)集上都能取得較小的平均角度差。這進一步說明了本文算法在少量先驗信息情況下的有效性。

5 結束語

本文提出了一種新的算法，利用測地距離構造不同流形樣本點之間的關聯(lián)性，再利用樣本點之間局部幾何結構的相似性進行修正，以更為準確地挖掘不同流形樣本點之間的關聯(lián)性。在本文提出的半監(jiān)督流形對齊算法中，需要利用給定點的信息構造兩個流形樣本點之間的測地距離。如何擴展到在無監(jiān)督流形對齊算法下，保持全局和局部特征樣本點關系，是將來本文需要研究的內容。此外，當流形采樣比較稀疏或數(shù)據(jù)存在噪聲時，基于局部距離度量流形樣本之間的相似性可能并不準確。如何挖掘更魯棒的局部結構以衡量流形樣本點之間的相似性，也是將來的研究內容。

Table 1 Average errors of matching angles of several manifold alignment algorithms on six different objects from the COIL-20 database

[1] Martinez A M,Kak A C. PCA versus LDA[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(2):228-233.

[2] Seung H S,Lee D D.The manifold ways of perception[J].Science,2000,290(5500):2268-2269.

[3] Wang C,Mahadevan S.A general framework for manifold alignment[C]∥Proc of AAAI,2009:101-109.

[4] Tenenbaum J,Silva V,Langford J.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[5] Roweis S T, SaulL K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[6] Zhang Z.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].Scientific Computing,2005,6(1):313-333.

[7] Belkin M. Laplacian eigen maps for dimensionality reduction and data representation[J].Neural Computation,2003,15 (6):1373-1396.

[8] Blei D,Ng A,Jordan M.Latent dirichletallocation[J].Journal of Machine Learning Research,2003,3(9):993-1022.

[9] Deerwester S,Dumais S T,Furnas G W,et al.Indexing by latent semantic analysis[J].Journal of the American Society for Information Science,1990,41(6):391-407.

[10] Diaz F,Metzler D.Pseudo-aligned multilingual corpora[C]∥Proc of International Joint Conference on Artificial Intelligence,2007:2727-2732.

[11] Bradski G R,Davis J W.Motion segmentation and pose recognition with motion history gradients[J].Machine Vision and Applications,2002,13(3):174-184.

[12] Nigam K,Ghani R.Analyzing the effectiveness and applicability of cotraining[C]∥Proc of the 9th International Conference on Information and Knowledge Management,2000:86-93.

[13] Zhen C,Hong C,Shiguang S,et al.Generalized unsupervised manifold alignment[C]∥Proc of NIPS,2014:2429-2437.

[14] Dan L P,Yun Q T,Jun Z.Visualization of hyperspectral imaging data based on manifold alignment[C]∥Proc of International Conference on Pattern Recognition,2014:1051-1057.

[15] Heili A.Improving head and body pose estimation through semi-supervised manifold alignment[C]∥Proc of IEEE International Conference on Image Processing,2014:1912-1916.

[16] He X.Locality preserving projections[C]∥Proc of the 16th Advances in Neural Information Processing Systems,2003:153-160.

[17] Jian C L,Zhang Y.Manifold alignment based on sparse local structures of more corresponding pairs[C]∥Proc of the 23rd International Joint Conference on Atificial Intelligence,2013:2862-2868.

[18] Wang C,Mahadevan S.Manifold alignment preserving global geometry[C]∥Proc of the 23rd International Joint Conference on Artificial Intelligence,2013:1743-1749.

[19] Ham J,Lee D,Saul L.Semi-supervised alignment of manifolds[C]∥Proc of International Workshop on Artificial Intelligence and Statistics,2005:120-127.

[20] Yu P,Feng H C,Fu S H,et al.Unsupervised image matching based on manifold alignment[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(8):1658-1664.

[21] Wang C,Mahadevan S.Manifold alignment without correspondence[C]∥Proc of the 21st International Joint Conference on Artifical Intelligence,2009:1273-1278.

[22] Wang C,Mahadevan S.Manifold alignment using procrustes analysis[C]∥Proc of the 25th International Conference on Machine Learning,2008:1120-1127.

[23] Perth W A, Mian A,Lin L,et al.Unsupervised iterative manifold alignment via local feature histograms[C]∥Proc of IEEE Winter Conference on Applications of Computer Vision,2014:572-579.