2015, Vol. 32
2006年在MIT首次召开的场景理解研讨会(Scene Understanding Symposium)上，学者们明确提出场景描述与理解, 特别是场景分类将会是图像理解的一个新的有前途的研究方向[1].
场景通常被定义为按可命名的人类视觉方法表示的现实环境，具有语义一致性[2].基于语义的场景分类通过采用语义来表示图像，以解决语义鸿沟的问题[3]，成为当前场景分类研究的热点.其中，利用词包模型(Bag of Words, BoW)构建视觉字典，而后采用生成模型实现场景分类是主流方法之一[4].
采用生成模型实现场景分类的经典流程：首先通过对图像的尺度不变特征转换(Scale-invariant Feature Transform, SIFT)特征[5]进行K-means聚类[6]得到容量为M的视觉字典，然后基于该视觉字典构建图像SIFT特征与视觉字典的词频矩阵，最后采用生成模型实现场景分类.由于采用K-means聚类算法在获取视觉字典容量的过程中，需要人为设定聚类数目即视觉字典容量，必须反复试验以摸索确定分类精度最高情况时对应的视觉字典容量，因此效率极其低下.
为此，本文提出一种高效获取视觉字典容量的方法，并研究了该方法与LDA[7-11]模型相结合情况下场景分类的性能.在构建场景图像SIFT特征矩阵的基础上，首先，采用吸引子传播方法(Affinity Propagation, AP)[12]自动获取视觉字典容量，并构建视觉字典；接着，采用所构建视觉字典中的词汇描述场景图像；最后，利用LDA模型对场景图像实现分类.
1 视觉字典容量自动获取的LDA场景分类框架传统的基于LDA模型进行场景分类的经典做法是对场景图像的SIFT特征进行K-means聚类，通过不断改变聚类中心数目来寻找最佳视觉字典容量，形成视觉字典，然后通过LDA模型得到场景图像的混合主题分布矩阵，从而完成场景分类.虽然K-means聚类算法能获取较高质量的视觉字典，但该算法需要人为设定聚类数目，通过不断试验才能确定合理容量的视觉字典，花费时间比较长.
针对以上问题，本文提出采用AP聚类算法自动获取合理容量的视觉字典，该算法可以自动确定聚类中心数目，即视觉字典容量，生成合理容量的视觉字典，从而提高LDA模型的场景分类效率.图 1所示为本文LDA模型的场景分类的总体框架.
|
图 1 本文场景分类的框架 Figure 1 Proposed framework of scene classification |
本文选用主流的SIFT特征构建图像特征矩阵.SIFT特征是由David Lowe于1999年提出的局部特征描述子，并于2004年做了完善[5].
SIFT特征提取算法主要包括4个步骤：尺度空间的极值检测; 关键点的精确定位, 关键点主方向的确定，关键点描述子的生成.由于关键点的个数与图像的梯度[13]等因素有关，因此每幅图像的关键点个数不同，为了获得统一维度的特征矩阵，本文采用致密网格法定义每幅图像的关键点为100个，则350幅图像可生成一个大小为35 000×128维的SIFT特征矩阵.
2.2 吸引子传播方法AP算法是Frey等人于2007年在Science上提出的一种新的无监督聚类算法[12]，该算法的基础是数据点之间的相似度，不需要事先指定聚类数目, 初始时将所有数据点看作潜在聚类中心，通过数据点间的“消息传递”来实现数据集的聚类.
AP算法的消息传递机制主要包含两种信息：吸引度R(Responsibility)和归属度A(Availability).吸引度R(i, k)表示点k适合作为点i的聚类中心的程度；归属度A(i, k)表示点i选择点k作为其聚类中心的适合程度.该算法的输入是N个数据点之间的相似度矩阵S，以矩阵S对角线上的数值S(k, k)作为点k能否成为聚类中心的评判标准，称之为参考度(Preference).算法的关键步骤是R(i, k)和A(i, k)的迭代更新，如公式(1)和(2)所示.
| $ \mathit{R}\left( {\mathit{i}{\rm{, }}\mathit{k}} \right){\rm{ = }}\mathit{S}\left( {\mathit{i}{\rm{, }}\mathit{k}} \right){\rm{ - }}\mathop {{\rm{max}}}\limits_{\mathit{j} \ne \mathit{k}} {\rm{(}}\mathit{A}{\rm{(}}\mathit{i}{\rm{, }}\mathit{j}{\rm{) + }}\mathit{S}{\rm{(}}\mathit{i}{\rm{, }}\mathit{j}{\rm{)), }} $ | (1) |
| $ \mathit{A}{\rm{(}}\mathit{i}{\rm{, }}\mathit{k}{\rm{) = min\{ 0, }}\mathit{R}{\rm{(}}\mathit{k}{\rm{, }}\mathit{k}{\rm{) + }}\sum\limits_{\mathit{j} \ne \mathit{i}{\rm{, }}\mathit{j}} {{\rm{max\{ 0, }}\mathit{R}{\rm{(}}\mathit{j}{\rm{, }}\mathit{k}{\rm{)\} }}} {\rm{\} }}{\rm{.}} $ | (2) |
Step1：提取所有场景图像的SIFT特征向量，生成场景图像集的SIFT特征矩阵；
Step2：利用AP算法对场景图像集的SIFT特征矩阵进行聚类，生成字典容量为M的视觉字典.
3 场景分类的生成模型LDA模型是Blei等在2003年提出的一个三级层次结构的贝叶斯模型.该模型以狄利克雷分布来描述主题与单词的生成，使得要估算的模型参数数量不会随着文档集的增多而线性增长，解决了pLSA模型[14]中参数随着数据集的容量增长而过拟合的情况[15].LDA模型作为完备的生成模型，对图像与主题、主题与单词两个层次都进行了建模，该模型的图表示如图 2所示.
|
图 2 LDA图模型 Figure 2 Graph model of LDA |
其中，阴影部分的w是已知数据，z是隐含变量，N, M代表重复选择的次数.
LDA模型的概率表示为
| $ \mathit{P}\left( {\mathit{\theta }{\rm{, }}\mathit{z}{\rm{, }}\mathit{w}{\rm{|}}\mathit{\alpha }{\rm{, }}\mathit{\beta }} \right){\rm{ = }}\mathit{P}\left( {\mathit{\theta }{\rm{|}}\mathit{\alpha }} \right)\prod\limits_{\mathit{n}{\rm{ = 1}}}^\mathit{N} {\mathit{P}\left( {{\mathit{z}_\mathit{n}}{\rm{|}}\mathit{\theta }} \right)\mathit{P}{\rm{(}}{\mathit{w}_\mathit{n}}{\rm{|}}{\mathit{z}_\mathit{n}}{\rm{, }}\mathit{\beta }{\rm{)}}} {\rm{.}} $ | (3) |
对于整个图像集D，其似然值为
| $ \begin{array}{l} \mathit{P}\left( {\mathit{D}{\rm{|}}\mathit{\alpha }{\rm{, }}\mathit{\beta }} \right){\rm{ = }}\prod\limits_{\mathit{d}{\rm{ = 1}}}^\mathit{M} {\int {\mathit{P}\left( {{\mathit{\theta }_\mathit{d}}{\rm{|}}\mathit{\alpha }} \right)} } {\rm{ \times }}\\ {\rm{}}\left( {\prod\limits_{\mathit{n}{\rm{ = 1}}}^\mathit{N} {\sum\limits_{{\mathit{Z}_{\mathit{dn}}}} {\mathit{P}\left( {{\mathit{z}_{\mathit{dn}}}{\rm{|}}{\mathit{\theta }_\mathit{d}}} \right)} \mathit{P}\left( {{\mathit{w}_{\mathit{dn}}}{\rm{|}}{\mathit{z}_{\mathit{dn}}}{\rm{, }}\mathit{\beta }} \right)} } \right){\rm{d}}{\mathit{\theta }_\mathit{d}}{\rm{.}} \end{array} $ | (4) |
在构建LDA模型时, 参数推理通常采用吉布斯抽样[11]方法，其目的是构造收敛于某目标概率的马尔科夫链.在LDA模型中，对于一个视觉单词来说，它归属于哪个主题取决于其他所有单词对当前主题的归属情况，计算归属过程的条件概率如式(5)所示：
| $ \begin{array}{l} \mathit{p}\left( {{\mathit{z}_\mathit{i}}{\rm{ = }}\mathit{k}{\rm{|}}{\mathit{z}_{{\rm{ - }}\mathit{i}}}{\rm{, }}\mathit{w}} \right) \propto \\ \frac{{\mathit{n}_{\mathit{m}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{k}{\rm{)}}}{\rm{ + }}{\mathit{\alpha }_\mathit{k}}}}{{\sum\nolimits_{\mathit{k}{\rm{ = 1}}}^\mathit{K} {\left( {\mathit{n}_{\mathit{m}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{t}{\rm{)}}}{\rm{ + }}{\mathit{\alpha }_\mathit{k}}} \right)} }} \times \frac{{\mathit{n}_{\mathit{k}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{t}{\rm{)}}}{\rm{ + }}{\mathit{\beta }_\mathit{t}}}}{{\sum\nolimits_{\mathit{t}{\rm{ = 1}}}^\mathit{V} {\left( {\mathit{n}_{\mathit{k}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{t}{\rm{)}}}{\rm{ + }}{\mathit{\beta }_\mathit{t}}} \right)} }}{\rm{, }} \end{array} $ | (5) |
其中, nm, -i(k)是除当前迭代过程外，第m个文档中被归结到第t个语义的单词数；nk, -i(t)是迭代过程中除当前迭代外，第k个词被归结到第t个语义的次数.
综上所述，LDA模型对图像集建模的吉布斯抽样方法的具体过程如下：
(1) 初始化：对图像集中每个单词w随机分配一个主题z，这是马尔科夫链的初始状态；
(2) 更新状态：根据式(5)重新采样它的主题，并在图像集中更新数据；
(3) 迭代步骤(2)足够多次，直到吉布斯抽样收敛到稳定状态.
在吉布斯抽样方法迭代结束之后，可间接获得估算θ和φ的推导公式
| $ {\mathit{\theta }_{\mathit{mk}}}{\rm{ = }}\frac{{\mathit{n}_{\mathit{m}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{k}{\rm{)}}}{\rm{ + }}{\mathit{\alpha }_\mathit{k}}}}{{\sum\nolimits_{\mathit{k}{\rm{ = 1}}}^\mathit{K} {\left( {\mathit{n}_{\mathit{m}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{t}{\rm{)}}}{\rm{ + }}{\mathit{\alpha }_\mathit{k}}} \right)} }}{\rm{, }} $ | (6) |
| $ {\mathit{\varphi }_{\mathit{kt}}}{\rm{ = }}\frac{{\mathit{n}_{\mathit{k}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{t}{\rm{)}}}{\rm{ + }}{\mathit{\beta }_\mathit{t}}}}{{\sum\nolimits_{\mathit{t}{\rm{ = 1}}}^\mathit{V} {\left( {\mathit{n}_{\mathit{k}{\rm{, - }}\mathit{i}}^{{\rm{(}}\mathit{t}{\rm{)}}}{\rm{ + }}{\mathit{\beta }_\mathit{t}}} \right)} }}{\rm{.}} $ | (7) |
本文实验数据集来源于15类数据集[16]中的卧室、楼群、工厂、厨房、海滩、森林和公路共7类场景图像，每类场景随机选择50幅图像，7类场景共计350幅图像.从每一类中随机抽取35幅图像作为训练集，其余15幅图像作为测试集.
实验测试的硬件环境：CPU为Intel(R) Core(TM) i7-3.4GHz，内存为32G，操作系统为Windows7旗舰版64位系统，编程软件为MATLAB R2013a.LDA模型的超参数设为α=50/K, β=0.1.
4.1 基于K-means算法的LDA模型的场景分类在进行LDA模型场景分类时，设主题数T=10，为了确定合理的视觉字典容量，视觉字典容量从100到2000每间隔50进行一次实验，共进行39次基于K-means聚类的LDA模型场景分类实验.该实验过程的总运行时间为75 020.1 s，其结果如图 3所示.
|
图 3 基于K-means的LDA模型的场景分类性能曲线 Figure 3 The scene classification performance curve of LDA based on K-means |
由图 3所示曲线可知，随着视觉字典容量的增大，场景分类准确率的变化并无规律可循, 而是存在多个波峰与波谷的交替.根据该曲线，难以判断视觉字典的合理容量取多少是最佳的.
4.2 基于AP算法的LDA模型的场景分类为了与基于K-means的实验结果进行对比，本文基于AP算法的LDA模型的场景分类方法的参数与基于K-means算法的LDA模型的场景分类方法的相关参数一致.
实验结果显示, AP算法自动获取的视觉字典容量为1100，利用该视觉字典的单词描述整个图像集，最后实现LDA模型的场景分类，得到分类准确率为79.05%，整个过程运行时间为15 781.3 s.
4.3 实验结果对比分析本节对前两个小节的两种建模方法的分类性能进行比较，其中，基于K-means算法的LDA场景分类方法列出了字典容量为1100的分类准确率以及3个分类准确率较高的字典容量的情况，其结果如表 1所示.
|
表 1 两种方法的实验结果对比 Table 1 The experimental results comparison of two methods |
由表 1可知，当两种建模方法的视觉字典容量都为1 100时，基于AP算法的LDA建模方法的分类准确率比基于K-means算法的LDA建模方法得到的分类准确率高出了4.76%.基于K-means算法的LDA建模方法确定合理视觉字典容量的经典方法是取字典容量较少, 且分类准确率尽量高的情况作为视觉字典容量，则本实验中取950作为视觉字典容量，其与AP算法自动获取的视觉字典容量的大小较接近，而且基于AP算法的LDA建模方法的分类准确率比基于K-means算法的LDA建模方法得到的最高分类准确率还高出了1.19%左右，但整个实验过程的时间却减少了78.96%.这说明采用AP算法自动获取视觉字典容量而后实现LDA模型的场景分类方法不仅是可行的、正确的，而且提高场景分类准确率的同时，显著提高场景分类效率.
5 结论本文提出使用AP算法自动获取视觉字典的容量，而后实现LDA模型的场景分类.本文的贡献在于：基于AP算法的LDA场景分类方法能自动获取合理容量的视觉字典，不用花费大量时间反复试验去寻找合理容量的视觉字典.结果表明，该方法的场景分类准确率比基于K-means的建模方法提高1%左右，实验运行时间减少78.96%，分类效率显著提高，是一种有效提高场景分类性能和效率的方法.
| [1] |
谢昭, 高隽. 基于高斯统计模型的场景分类及约束机制新方法[J].
电子学报, 2009, 37(4): 733-738.
Xie Z, Gao J. A novel method for scene categorization with constraint mechanism based on gaussian statistical model[J]. Acta Electronica Sinca, 2009, 37(4): 733-738. |
| [2] |
王中锋, 王志海, 解文杰. 基于树型贝叶斯网络的场景分类引擎训练算法[J].
仪器仪表学报, 2012, 33(4): 863-869.
Wang Z F, Wang Z H, Xie W J. Tree structured Bayesian network learning algorithmfor scene classification[J]. Chinese Journal of Scientific Instrument, 2012, 33(4): 863-869. |
| [3] |
唐颖军, 须德, 解文杰. 一种基于类主题空间的图像场景分类方法[J].
中国图象图形学报, 2010, 15(7): 1067-1073.
Tang Y J, Xu D, Xie W J. A Novel image sceneclassification method based on category topic simplex[J]. Journal of Image and Gr-aphics, 2010, 15(7): 1067-1073. DOI: 10.11834/jig.090704. |
| [4] |
刘硕研, 须德, 冯松鹤. 一种基于上下文语义信息的图像块视觉单词生成算法[J].
电子学报, 2010, 38(5): 1156-1161.
Liu S Y, Xu D, Feng S H. A novel visual words definition algorithm of image patch based on contextual semantic information[J]. Acta Electronica Sinca, 2010, 38(5): 1156-1161. |
| [5] | Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110. DOI: 10.1023/B:VISI.0000029664.99615.94. |
| [6] |
刘洪伟, 石雅强, 梁周扬. 面向聚类挖掘的局部旋转扰动隐私保护算法[J].
广东工业大学学报, 2012, 29(3): 28-34.
Liu H W, Shi Y Q, Liang Z Y. Partial rota-tion perturbation for privacy-preservingclustering mining[J]. Journal of GuangDong University of Technology, 2012, 29(3): 28-34. |
| [7] | Blei D, Ng A, Jordan M. Latent dirichlet allocation[J]. Journal of Machine Learning Research, 2003, 3: 993-1022. |
| [8] | Heinrich G. Parameter estimation for text analysis[EB/OL]. [2012-07-25]. http://www.arbylon.net/publications/text-est.pdf. |
| [9] | Rasiwasia N, Vasconcelos N. Latent dirichlet allocation models for image classification[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2665-2679. DOI: 10.1109/TPAMI.2013.69. |
| [10] | Corina V, Inge G, Mihai D. Latent dirichlet allocation for spatial analysis of satellite images[J]. Geoscience and Remote Sensing, 2013, 51(5): 2770-2786. DOI: 10.1109/TGRS.2012.2219314. |
| [11] |
唐颖军. 基于LDA图像场景分类方法的增量学习研究[J].
小型微型计算机系统, 2013, 34(5): 1194-1197.
Tang Y J. Research on increment learning way to LDA based image scene classification[J]. Journal of Chinese Computer Systems, 2013, 34(5): 1194-1197. |
| [12] | Frey B, Dueck D. Clustering by passing messages between data points[J]. Science, 2007, 315(5184): 972-976. |
| [13] |
吴建宏, 李伟彤, 廖捷. 一种基于小波-Contourlet的改进图像融合算法[J].
广东工业大学学报, 2011, 28(1): 12-15.
Wu J H, Li W T, Liao J. An improved image fusion algorithm based on wavelet-based Contourlet tranfform[J]. Journal of Guangdong University of Technology, 2011, 28(1): 12-15. |
| [14] |
江悦, 王润生. 基于多特征扩展pLSA模型的场景图像分类[J].
信号处理, 2010, 26(4): 539-544.
Jiang Y, Lin R S. Scene classification based on a multi-feature extended pLSA model[J]. Signal Processing, 2010, 26(4): 539-544. |
| [15] |
杨赛, 赵春霞. 基于隐含狄利克雷分配模型的图像分类算法[J].
计算机工程, 2012, 38(14): 181-183.
Yang S, Zhao C X. Image classification algorithm based on latent dirichlet allocation model[J]. Computer Engineering, 2012, 38(14): 181-183. DOI: 10.3969/j.issn.1000-3428.2012.14.054. |
| [16] | Lazebnik S, Schmid C, Ponce J. A dataset of fifteen natural scene categories that expands[DB/OL]. http://www.datatang.com/datares/detail.aspx?id=6438, 2011-08-16. |