杜卓明

摘 要：本文提出了改進的SKPCA降維方法。在特征向量稀疏化表達的基礎上，實現(xiàn)了一階降維、二階降維與非線性降維。在增強特征向量表達能力的同時最大限度去除了冗余信息。實驗證明利用改進的SKPCA降維方法獲得的特征向量，檢索效果優(yōu)于SPCA方法。

關鍵字：核主成份分析；降維；稀疏；特征向量

中圖分類號：TP391.4 文獻標識碼：A 文章編號：2095-2163（2014）05-

3D Model Retrieval based on the Improved SKPCA

DU Zhuoming

（School of Computer Engineering， Jiangsu University of Technology， Changzhou Jiangsu 213001，China）

Abstract： The improved SKPCA method for dimensionality reduction is proposed in this paper. This method achieves an order、second-order and nonlinear dimensionality reduction. It can remove redundant information to the maximum extent. Experiments show that retrieval results based on the improved SKPCA is better than SPCA.

Keywords： KPCA； Dimensionality Reduction； Sparse； Feature Vector

0引 言

隨著三維模型應用的普及與推廣，人們對其需求量也出現(xiàn)了顯著攀升，相應地提供檢索的三維模型庫中的模型數(shù)量也日漸增多，并蔚為可觀。而且為了更大程度上的檢索方便，在構(gòu)建模型庫時就要將其中的模型按照類別進行整合劃分，形成諸如動物類，桌椅類等相應類別，并最終呈現(xiàn)為結(jié)構(gòu)化的三維模型庫。

具體地，普通用戶使用三維模型庫，是在模型庫中檢索研究需要的模型；服務器端的管理員則是使用三維模型庫對模型庫進行不斷的豐富與擴充。隨著系統(tǒng)的不間斷運行，模型庫的規(guī)模更在不斷壯大，由此將引發(fā)的直接后果就是模型庫中模型的個數(shù)大于模型特征向量的維數(shù)。將其對應至三維模型庫的特征庫 上，就表現(xiàn)為 。而這將給模型檢索與新模型入庫帶來相當?shù)睦щy。本文正是針對上述情況而提出新的三維模型檢索方法。其中，三維模型經(jīng)特征提取后，就將得到一個與之對應的特征向量。而每個特征向量也就是一個一維信號，因此可以從信號處理的角度重新獲得三維模型檢索方法的研究視角。

1基于稀疏化表達的模型檢索方法

信號的稀疏化表達是指信號可以表示為一組基底信號的線性組合，組合系數(shù)即稱為原始信號在新基底下的信號表達形式，而這組表達系數(shù)絕大部分均將為0。已有研究可知，任何有意義的信號都可以由一組基底來實現(xiàn)稀疏化表達（高斯白噪聲除外）[1]。

2007年后，信號的稀疏化表達已日益突顯其重要，而且已然在眾多方面獲得廣泛應用，舉例來說，則有諸如去除噪聲、壓縮方法、特征提取、模式識別以及信息的盲目分類等領域[2-6]。尤需指出的是，在統(tǒng)計信號處理領域，基于完備字典的信號稀疏化表達也成為業(yè)界的研究熱點之一[7]。進一步地，則有大量的研究足以表明，當信號可以進行充分的稀疏表達后，就可以利用凸優(yōu)化來完成高效的計算[8]。

Wright[9]首次將信號稀疏化表達的方法應用于人臉識別中。本研究將其應用于三維模型的檢索過程中。隨著人們對三維模型需求量的不斷增加，提供三維模型檢索服務的模型庫也變得日漸龐大。例如，西北大學可視化技術研究所建立的三維模型庫中就包含有接近六萬個模型，而且該模型庫的規(guī)模仍然呈現(xiàn)了增長態(tài)勢。隨著三維模型庫容量的不斷增長，其模型的個數(shù)必然大于模型特征信號的維數(shù)，呈現(xiàn)在其特征庫 上，就是 。而且，若將特征庫 展開表示，其結(jié)果為： ，其中 為一個 維向量，表示模型庫中的第 個模型。

三維模型庫的建立是按照模型的類別分類建庫，即模型庫包括人物類、動物類等。因此模型庫的特征庫結(jié)構(gòu)則如圖1所示。

圖1 三維模型庫特征庫的結(jié)構(gòu)圖

Fig.1 Structure diagram of 3D model library

從圖1中可以看出，三維模型特征庫 中共有 個模型， 個模型分為 類，分別可用 表示，即 。針對待檢索模型，其經(jīng)特征提取后，將表達為 。而且，該模型可由 中的各列進行線性表達。將其用公式表述則如下：

其中， 是待檢索模型的特征信號，是一個 的向量； 是模型特征庫矩陣，是 的矩陣； 則是 在 所對應的新基底下的新坐標，是一個 的向量。相應地，圖2描述了 的形態(tài)。

圖2 待檢索模型在特征庫基下的投影圖

Fig.2 Projection graph of retrieving model under the feature library

依據(jù)聚類原理可知，同類模型的特征信號相似，非同類模型特征信號的差異將會較大?；诖?，即可分為兩種情況進行討論：

（1）情況一：理想化的情況是，模型庫中恰有待檢索模型，即 是 的一列。則：

的稀疏表達 只有在 處為1，其他地方均為0。此時返回檢索結(jié)果即為 所對應的模型。

（2）情況二：由其推理可得，如果模型庫中沒有待檢索模型，即 不是 的一列，則：

由以上前提推理可得， 的稀疏表達 只有在與其相近的模型特征信號前的系數(shù)才非0，而其余各處則均為0。進而可知，返回的檢索結(jié)果為： 中非0值的位置對應的 若干列所表示的模型。

以上兩種情況均需設置閾值 ，如果 ，則賦值 。

至此，問題將轉(zhuǎn)化成為求解 的過程，上述問題中 與 則是已知量。求解 就是求解方程： 。并且，由于 ，可知此方程組中方程的個數(shù)小于未知量的個數(shù)，因此有無窮多組解。利用壓縮感知理論[10-11]，通過最優(yōu)化 的1范數(shù)，得到 的最稀疏解，即：

subject to （2）

通過以上的論述可知，問題的關鍵在于根據(jù)方程 求解而得 。根據(jù)線性代數(shù)的知識可知： 與 是同解的方程。 為一個變換矩陣。經(jīng)變換后 變?yōu)橄∈栊盘?， 變?yōu)橄∈杈仃?，但是 不發(fā)生任何變化。檢索結(jié)果仍然是 中非0值位置對應的 中相應列所表示的模型。因此問題的關鍵將轉(zhuǎn)變?yōu)榍蠼夥匠?。而方程的?shù)學表述為：

（3）

對方程的求解過程則為：

（4）

subject to ， ， 。

此問題求解過程中所有的矩陣與向量均稀疏化，這樣就大大降低了時間復雜度與空間復雜度。

2基于改進SKPCA稀疏化表達的模型檢索方法

假設模型庫中有 個模型，每個模型經(jīng)特征提取后得到 維的特征向量，即得到的數(shù)據(jù)集為 的矩陣。在大多數(shù)情況下 。設數(shù)據(jù)集 ，這是一個 的矩陣， 是一個 維的向量，表示第 個模型。

改進的稀疏KPCA算法的具體描述為：

Step1： 將數(shù)據(jù)集 的每一列轉(zhuǎn)換為稀疏化表達方式 。其中， ，即 。這里的 可以選擇離散小波變換，離散余弦變換，離散傅立葉變換等。經(jīng)過變換后，矩陣 的每一列均為 中每一列的稀疏化表達。

Step2： 計算 中每一行的方差，計算的結(jié)果是得到 個方差 ，其中 。

Step3： 在 中選擇前 個較大的方差對應的行，再以其組成新的數(shù)據(jù)集 。 的選取利用： 。并且， 是一個 的矩陣， ，因此達到了降維的目的。

Step4： 計算 每一行的均值，計算的結(jié)果是得到 個均值 ，其中 。在 中選擇前 個均值較大的行組成新的數(shù)據(jù)集 。 的選取利用： 。 是一個 的矩陣， 。由此達到降維的目的。

Step5： 對 使用KPCA進行降維，并得到最終的數(shù)據(jù)集 。

在KPCA的降維過程中，首先利用核方法將 升維得到 （ 為三維模型庫中模型的個數(shù)）。 中的特征向量對模型具有更好的表達能力，并且其中的列向量構(gòu)成了希爾伯特空間。對 則使用KPCA降維，將去除 中的非線性冗余信息。

經(jīng)過降維以后，再使用第2節(jié)中提出的匹配方法檢索模型。其檢索原理的表達形式變?yōu)椋?/p>

（5）

得到的 仍然是 維的稀疏向量。設置閾值 ，按照 中分量的大小返回檢索結(jié)果。

3算法驗證與討論

為了驗證本文研究提出算法的有效性，從普林斯頓大學三維模型庫中選取100個模型作為實驗數(shù)據(jù)庫。100個模型從4類模型中進行抽取，分別為人物類、動物類、交通工具類以及植物類。采用Suzuki[14]的方法對三維模型提取特征，即：使用立方體對模型進行包裹，并對立方體進行切割，分成 個小的立方體格子，統(tǒng)計落在每個格子中的頂點數(shù)目，作為模型的特征。這一設計的優(yōu)點在于可以對模型進行等分分割。實驗中提取的特征為30維的特征向量。由于30<100，因此可以用來驗證本文檢索方法的有效性。

研究中采用了改進的SKPCA方法，其在檢索效果方面優(yōu)于SPAC方法。具體地，SPAC方法是首先進行預降維，再采用傳統(tǒng)的PCA方法進行降維即連續(xù)進行兩次降維的操作；而改進的SKPCA在預降維階段增加了對一階量均值的處理，因此預降維后模型的特征維數(shù)低于SPAC預降維后的結(jié)果，但是在使用KPCA降維時，首先是一個升維的過程，升維后的維數(shù)是100（等于模型的庫中模型的個數(shù)），而高維空間中的向量則是線性可分的（對三維模型的表達能力增強），再對高維空間中的特征進行非線性降維，降至與SPAC相同的維數(shù)。因此采用改進的SKPCA方法得到的特征向量優(yōu)于SPAC方法得到的特征向量，具體如圖3所示。

圖3 實驗的檢索結(jié)果對比圖

Fig.3 Comparison chart of retrieval results of experiments

4結(jié)束語

本文首先介紹了基于稀疏化表達的模型匹配方法，并在此匹配方法的基礎上介紹了稀疏化主成分分析的降維方法。更重要的則是將稀疏化表達的模型匹配方法與稀疏化主成分分析降維方法結(jié)合起來，而相應地提出了改進的稀疏核主成分分析的方法。實驗證明，改進的稀疏核主成分分析的模型檢索效果良好，查全率與查準率均高于稀疏化主成分分析的方法。

參考文獻

[1] HUANG K， AVIYENTE S. Sparse representation for signal classification[J]. Advances in Neural Information Processing Systems， 2007， 19： 609-616.

[2] ELAD M， AHARON M. Image denoising via learned dictionaries and sparse representation[C]//Proc. of CVPR， 2006，1：895 – 900.

[3] ELAD M， MATALON B， ZIBULEVSKY M. Image denoising with shrinkage and redundant representation[C]//Proc. of CVPR， 2006， 2：1924 – 1931.

[4] LI Y， CICHOCKI A， AMARI S. Analysis of sparse representation and blind source separation[J]. Neural Computation， 2004， 16（6）：1193–1234.

[5] OLSHAUSEN B， SALLEE P， LEWICKI M. Learning sparse image codes using a wavelet pyramid architecture[C]//NIPS， 2001：887–893.

[6] STARCK J， ELAD M， DONOHO D. Image decomposition via the combination of sparse representation and a variational approach[C]//IEEE Trans. on Image Processing， 2005，14（10）： 1570–1582.

[7] WRIGHT J， YANG A Y， GANESH A， et al. Robust face recognition via sparse representation[C]//IEEE Trans. on PAMI， 2009，31：210-227.

[8] DONOHO D L. For most large underdetermined systems of linear equations the minimal 1 l -norm solution is also the sparsest solution[J].Comm. Pure and Applied Math.， 2006， 59（6）：797- 829.

[9] WRIGHT J， YANG A Y， GANESH A， et al. Robust face recognition via sparse representation[J].IEEE Trans. on PAMI， 2009， 31：210-227.

[10] CANDES E， TAO T. Near-optimal signal recovery from random projections： universal encoding strategies[J].IEEE Trans. Information Theory， 2006， 52（12）：5406-5425.

[11] DONOHO D L. De-noising by soft-thresholding[J].IEEE Trans. on Information Theory， 1995， 41（3）：613–627.