基于改進(jìn)的SKPCA三維模型檢索方法

杜卓明

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

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

中圖分類(lèi)號(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)地提供檢索的三維模型庫(kù)中的模型數(shù)量也日漸增多，并蔚為可觀。而且為了更大程度上的檢索方便，在構(gòu)建模型庫(kù)時(shí)就要將其中的模型按照類(lèi)別進(jìn)行整合劃分，形成諸如動(dòng)物類(lèi)，桌椅類(lèi)等相應(yīng)類(lèi)別，并最終呈現(xiàn)為結(jié)構(gòu)化的三維模型庫(kù)。

具體地，普通用戶使用三維模型庫(kù)，是在模型庫(kù)中檢索研究需要的模型；服務(wù)器端的管理員則是使用三維模型庫(kù)對(duì)模型庫(kù)進(jìn)行不斷的豐富與擴(kuò)充。隨著系統(tǒng)的不間斷運(yùn)行，模型庫(kù)的規(guī)模更在不斷壯大，由此將引發(fā)的直接后果就是模型庫(kù)中模型的個(gè)數(shù)大于模型特征向量的維數(shù)。將其對(duì)應(yīng)至三維模型庫(kù)的特征庫(kù) 上，就表現(xiàn)為 。而這將給模型檢索與新模型入庫(kù)帶來(lái)相當(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ù)即稱(chēng)為原始信號(hào)在新基底下的信號(hào)表達(dá)形式，而這組表達(dá)系數(shù)絕大部分均將為0。已有研究可知，任何有意義的信號(hào)都可以由一組基底來(lái)實(shí)現(xiàn)稀疏化表達(dá)（高斯白噪聲除外）[1]。

2007年后，信號(hào)的稀疏化表達(dá)已日益突顯其重要，而且已然在眾多方面獲得廣泛應(yīng)用，舉例來(lái)說(shuō)，則有諸如去除噪聲、壓縮方法、特征提取、模式識(shí)別以及信息的盲目分類(lèi)等領(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)化來(lái)完成高效的計(jì)算[8]。

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

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

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

Fig.1 Structure diagram of 3D model library

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

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

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

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

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

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

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

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

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

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

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

subject to （2）

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

（3）

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

（4）

subject to ， ， 。

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

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

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

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

Step1： 將數(shù)據(jù)集 的每一列轉(zhuǎn)換為稀疏化表達(dá)方式 。其中， ，即 。這里的 可以選擇離散小波變換，離散余弦變換，離散傅立葉變換等。經(jīng)過(guò)變換后，矩陣 的每一列均為 中每一列的稀疏化表達(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的降維過(guò)程中，首先利用核方法將 升維得到 （ 為三維模型庫(kù)中模型的個(gè)數(shù)）。 中的特征向量對(duì)模型具有更好的表達(dá)能力，并且其中的列向量構(gòu)成了希爾伯特空間。對(duì) 則使用KPCA降維，將去除 中的非線性冗余信息。

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

（5）

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

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

為了驗(yàn)證本文研究提出算法的有效性，從普林斯頓大學(xué)三維模型庫(kù)中選取100個(gè)模型作為實(shí)驗(yàn)數(shù)據(jù)庫(kù)。100個(gè)模型從4類(lèi)模型中進(jìn)行抽取，分別為人物類(lèi)、動(dòng)物類(lèi)、交通工具類(lèi)以及植物類(lèi)。采用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，因此可以用來(lái)驗(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è)升維的過(guò)程，升維后的維數(shù)是100（等于模型的庫(kù)中模型的個(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é)束語(yǔ)

本文首先介紹了基于稀疏化表達(dá)的模型匹配方法，并在此匹配方法的基礎(chǔ)上介紹了稀疏化主成分分析的降維方法。更重要的則是將稀疏化表達(dá)的模型匹配方法與稀疏化主成分分析降維方法結(jié)合起來(lái)，而相應(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.