基于改进的SKPCA三维模型检索方法

杜卓明

摘 要：本文提出了改进的SKPCA降维方法。在特征向量稀疏化表达的基础上，实现了一阶降维、二阶降维与非线性降维。在增强特征向量表达能力的同时最大限度去除了冗余信息。实验证明利用改进的SKPCA降维方法获得的特征向量，检索效果优于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引 言

随着三维模型应用的普及与推广，人们对其需求量也出现了显著攀升，相应地提供检索的三维模型库中的模型数量也日渐增多，并蔚为可观。而且为了更大程度上的检索方便，在构建模型库时就要将其中的模型按照类别进行整合划分，形成诸如动物类，桌椅类等相应类别，并最终呈现为结构化的三维模型库。

具体地，普通用户使用三维模型库，是在模型库中检索研究需要的模型；服务器端的管理员则是使用三维模型库对模型库进行不断的丰富与扩充。随着系统的不间断运行，模型库的规模更在不断壮大，由此将引发的直接后果就是模型库中模型的个数大于模型特征向量的维数。将其对应至三维模型库的特征库 上，就表现为 。而这将给模型检索与新模型入库带来相当的困难。本文正是针对上述情况而提出新的三维模型检索方法。其中，三维模型经特征提取后，就将得到一个与之对应的特征向量。而每个特征向量也就是一个一维信号，因此可以从信号处理的角度重新获得三维模型检索方法的研究视角。

1基于稀疏化表达的模型检索方法

信号的稀疏化表达是指信号可以表示为一组基底信号的线性组合，组合系数即称为原始信号在新基底下的信号表达形式，而这组表达系数绝大部分均将为0。已有研究可知，任何有意义的信号都可以由一组基底来实现稀疏化表达（高斯白噪声除外）[1]。

2007年后，信号的稀疏化表达已日益突显其重要，而且已然在众多方面获得广泛应用，举例来说，则有诸如去除噪声、压缩方法、特征提取、模式识别以及信息的盲目分类等领域[2-6]。尤需指出的是，在统计信号处理领域，基于完备字典的信号稀疏化表达也成为业界的研究热点之一[7]。进一步地，则有大量的研究足以表明，当信号可以进行充分的稀疏表达后，就可以利用凸优化来完成高效的计算[8]。

Wright[9]首次将信号稀疏化表达的方法应用于人脸识别中。本研究将其应用于三维模型的检索过程中。随着人们对三维模型需求量的不断增加，提供三维模型检索服务的模型库也变得日渐庞大。例如，西北大学可视化技术研究所建立的三维模型库中就包含有接近六万个模型，而且该模型库的规模仍然呈现了增长态势。随着三维模型库容量的不断增长，其模型的个数必然大于模型特征信号的维数，呈现在其特征库 上，就是 。而且，若将特征库 展开表示，其结果为： ，其中 为一个 维向量，表示模型库中的第 个模型。

三维模型库的建立是按照模型的类别分类建库，即模型库包括人物类、动物类等。因此模型库的特征库结构则如图1所示。

图1 三维模型库特征库的结构图

Fig.1 Structure diagram of 3D model library

从图1中可以看出，三维模型特征库 中共有 个模型， 个模型分为 类，分别可用 表示，即 。针对待检索模型，其经特征提取后，将表达为 。而且，该模型可由 中的各列进行线性表达。将其用公式表述则如下：

其中， 是待检索模型的特征信号，是一个 的向量； 是模型特征库矩阵，是 的矩阵； 则是 在 所对应的新基底下的新坐标，是一个 的向量。相应地，图2描述了 的形态。

图2 待检索模型在特征库基下的投影图

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

依据聚类原理可知，同类模型的特征信号相似，非同类模型特征信号的差异将会较大。基于此，即可分为两种情况进行讨论：

（1）情况一：理想化的情况是，模型库中恰有待检索模型，即 是 的一列。则：

的稀疏表达 只有在 处为1，其他地方均为0。此时返回检索结果即为 所对应的模型。

（2）情况二：由其推理可得，如果模型库中没有待检索模型，即 不是 的一列，则：

由以上前提推理可得， 的稀疏表达 只有在与其相近的模型特征信号前的系数才非0，而其余各处则均为0。进而可知，返回的检索结果为： 中非0值的位置对应的 若干列所表示的模型。

以上两种情况均需设置阈值 ，如果 ，则赋值 。

至此，问题将转化成为求解 的过程，上述问题中 与 则是已知量。求解 就是求解方程： 。并且，由于 ，可知此方程组中方程的个数小于未知量的个数，因此有无穷多组解。利用压缩感知理论[10-11]，通过最优化 的1范数，得到 的最稀疏解，即：

subject to （2）

通过以上的论述可知，问题的关键在于根据方程 求解而得 。根据线性代数的知识可知： 与 是同解的方程。 为一个变换矩阵。经变换后 变为稀疏信号 ， 变为稀疏矩阵 ，但是 不发生任何变化。检索结果仍然是 中非0值位置对应的 中相应列所表示的模型。因此问题的关键将转变为求解方程。而方程的数学表述为：

（3）

对方程的求解过程则为：

（4）

subject to ， ， 。

此问题求解过程中所有的矩阵与向量均稀疏化，这样就大大降低了时间复杂度与空间复杂度。

2基于改进SKPCA稀疏化表达的模型检索方法

假设模型库中有 个模型，每个模型经特征提取后得到 维的特征向量，即得到的数据集为 的矩阵。在大多数情况下 。设数据集 ，这是一个 的矩阵， 是一个 维的向量，表示第 个模型。

改进的稀疏KPCA算法的具体描述为：

Step1： 将数据集 的每一列转换为稀疏化表达方式 。其中， ，即 。这里的 可以选择离散小波变换，离散余弦变换，离散傅立叶变换等。经过变换后，矩阵 的每一列均为 中每一列的稀疏化表达。

Step2： 计算 中每一行的方差，计算的结果是得到 个方差 ，其中 。

Step3： 在 中选择前 个较大的方差对应的行，再以其组成新的数据集 。 的选取利用： 。并且， 是一个 的矩阵， ，因此达到了降维的目的。

Step4： 计算 每一行的均值，计算的结果是得到 个均值 ，其中 。在 中选择前 个均值较大的行组成新的数据集 。 的选取利用： 。 是一个 的矩阵， 。由此达到降维的目的。

Step5： 对 使用KPCA进行降维，并得到最终的数据集 。

在KPCA的降维过程中，首先利用核方法将 升维得到 （ 为三维模型库中模型的个数）。 中的特征向量对模型具有更好的表达能力，并且其中的列向量构成了希尔伯特空间。对 则使用KPCA降维，将去除 中的非线性冗余信息。

经过降维以后，再使用第2节中提出的匹配方法检索模型。其检索原理的表达形式变为：

（5）

得到的 仍然是 维的稀疏向量。设置阈值 ，按照 中分量的大小返回检索结果。

3算法验证与讨论

为了验证本文研究提出算法的有效性，从普林斯顿大学三维模型库中选取100个模型作为实验数据库。100个模型从4类模型中进行抽取，分别为人物类、动物类、交通工具类以及植物类。采用Suzuki[14]的方法对三维模型提取特征，即：使用立方体对模型进行包裹，并对立方体进行切割，分成 个小的立方体格子，统计落在每个格子中的顶点数目，作为模型的特征。这一设计的优点在于可以对模型进行等分分割。实验中提取的特征为30维的特征向量。由于30<100，因此可以用来验证本文检索方法的有效性。

研究中采用了改进的SKPCA方法，其在检索效果方面优于SPAC方法。具体地，SPAC方法是首先进行预降维，再采用传统的PCA方法进行降维即连续进行两次降维的操作；而改进的SKPCA在预降维阶段增加了对一阶量均值的处理，因此预降维后模型的特征维数低于SPAC预降维后的结果，但是在使用KPCA降维时，首先是一个升维的过程，升维后的维数是100（等于模型的库中模型的个数），而高维空间中的向量则是线性可分的（对三维模型的表达能力增强），再对高维空间中的特征进行非线性降维，降至与SPAC相同的维数。因此采用改进的SKPCA方法得到的特征向量优于SPAC方法得到的特征向量，具体如图3所示。

图3 实验的检索结果对比图

Fig.3 Comparison chart of retrieval results of experiments

4结束语

本文首先介绍了基于稀疏化表达的模型匹配方法，并在此匹配方法的基础上介绍了稀疏化主成分分析的降维方法。更重要的则是将稀疏化表达的模型匹配方法与稀疏化主成分分析降维方法结合起来，而相应地提出了改进的稀疏核主成分分析的方法。实验证明，改进的稀疏核主成分分析的模型检索效果良好，查全率与查准率均高于稀疏化主成分分析的方法。

参考文献

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