杜卓明

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

關(guān)鍵字：核主成份分析；降維；稀疏；特征向量

中圖分類號(hào)：TP391.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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引 言

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

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

1基于稀疏化表達(dá)的模型檢索方法

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

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

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

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

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

Fig.1 Structure diagram of 3D model library

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

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

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

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

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

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

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

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

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

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

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

subject to （2）

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

（3）

對(duì)方程的求解過程則為：

（4）

subject to ， ， 。

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

2基于改進(jìn)SKPCA稀疏化表達(dá)的模型檢索方法

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

改進(jìn)的稀疏KPCA算法的具體描述為：

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

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

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

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

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

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

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

（5）

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

3算法驗(yàn)證與討論

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

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

圖3 實(shí)驗(yàn)的檢索結(jié)果對(duì)比圖

Fig.3 Comparison chart of retrieval results of experiments

4結(jié)束語

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

參考文獻(xiàn)

[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.