一种传统云纹图案的自动分类方法

技术领域

本发明属于聚类分析、图像分类技术领域，涉及云纹图像预处理，形状上下文特征提取， 近邻关系传递优化相似性矩阵。具体地说是一种结合近邻关系传递与形状上下文特征的多子 类中心近邻传播算法聚类云纹图像的自动分类方法。

背景技术

在中国传统装饰纹样中，云纹是历史久远、造型样式极其丰富、独具东方艺术魅力的一 个大类。云纹流变生动，寓意吉祥，表现形式多样，既有不同单体的变化，又有各类嫁接、 连续的组合结构，自古以来就是各类平面和立体造形之中重要的装饰元素，即使到了今天， 对当代艺术设计与创作仍有很大的借鉴价值。例如大家所熟悉的2008年北京奥运会火炬上就 采用了祥云纹样作为装饰图案，其造型来源于先秦时期就出现的单勾卷云纹。在推崇弘扬优 秀民族传统文化的今天，对传统艺术形式的研究显得犹为重要。其中，对传统图案样式进行 搜寻、采集、归类、分析，发现其中蕴含着的民族智慧、符合东方审美观念的艺术语言，无 论是对于学术研究还是丰富现代艺术设计语汇都极具价值。

中国传统云纹的发展起点可以追溯到新石器时代彩陶纹饰中的原始旋纹。而春秋战国时 期青铜器上的云雷纹被认为是较为明确的最早的成形云纹，后又经历了卷云纹、云气纹、流 云纹、朵云纹、如意云纹、团云纹、叠云纹等样式的繁衍变迁，从最初的单纯抽象发展到拟 形和写意，样式极其丰富多变，即使是同一大类的云纹，随时代、地域、创作者的不同，也 有多种形态的变化。由于云纹艺术形式极其丰富，各类图案样式资料浩如烟海，要做好这项 研究整理工作仅仅依靠人工查找、整理归类，其效率是十分低下的，因此通过引入非监督的 聚类分析方法，在研究图案特征的基础上实现云纹图案的自动分类无疑具有重大意义。

2007年Frey等人在science上提出了一种全新的基于簇类中心的聚类算法，即AP聚类 算法(Frey B J:《Clustering by passing messages between data points》[J].science,2007,315(5814): 972-976.)，并将该算法结合不同图像像素点间的欧氏距离对人脸图像进行了聚类研究，取得 了比k-centers更好的聚类效果。之后Frey等人将AP聚类算法结合SIFT特征用于对Caltech101 图像的聚类分析，证明了采用SIFT算法提取图像特征结合AP算法进行图像聚类具有一定的 优越性(Dueck,Frey B J.《Non-metric Affinity Propagation for Unsupervised Image  Categorization》[C]//Proc of 11th International Conference on IEEE Computer Vision.Toronto, Canada,2007:1-8)。王昌栋等人于2013年在PAMI上提出MEAP聚类算法，将AP算法单簇 类中心的模型拓展为多子类中心的聚类模型，并结合SIFT特征对人脸图像、Aaltech101图像 与SceneClass13的聚类进行了研究，提高了算法处理多子类图像的聚类精度(Wang C D: 《Multi-exemplar affinity propagation》[J].IEEE Transactions on Pattern Analysis&Machine  Intelligence,2013,35(9):2223-2237)。目前，对我国传统云纹图案进行自动分类的研究仍是空 白。

发明内容

本发明借鉴Frey与王昌栋等人的研究成果，提出一种基于近邻关系传递的多子类中心近 邻传播聚类算法(neighbor propagation based multi-exemplar affinity propagation,NP-MEAP)，结 合SC特征提取算法实现云纹图案的自动分类。本发明的目的在于克服云纹图像人工分类非 常低效的缺点，设计一种无监督的云纹图像自动分类技术。

实现本发明的技术关键是：云纹图像预处理、提取云纹图像SC相似性矩阵、通过改进 的NP算法优化相似度矩阵、最后采用MEAP传播聚类算法进行自动分类。具体实现步骤包 括如下：

(1)云纹图像预处理，归一化云纹图像尺寸、去除背景噪声、云纹图像线条细化。

(1a)归一化云纹图像尺寸，这样既方便后续图像的统一处理同时不会改变图像线条 分布情况

(1b)去除背景噪声，同时也方便采用数学形态学方法对图像进行细化。

(1c)云纹图像线条细化，因为不同类云纹图像的线条形状不同，而同类云纹图像的 线条形状基本相似，因此主要关注云纹图像线条形状。

(2)提取云纹图像的形状上下文相似度矩阵

(2a)形状上下文算法认为每个图像中的物体可以用图形边界上均匀分布的有限数 目的离散点来近似描述，所以需提取云纹图像的边界上的离散点。

(2b)针对每个离散点计算其形状上下文。

(2c)计算两幅云纹图像中任意两点之间的形状上下文差异。

(2d)计算两幅云纹图像中任意两点之间的正切角差异。

(2e)将两幅云纹图像中任意两点之间的形状上下文差异与正切角差异有机结合。

(2f)计算任意两幅云纹图像之间的形状上下文距离值。

(3)改进的近邻传递算法(NP)优化S_sc矩阵

(3a)计算形状上下文距离矩阵D。

(3b)计算近邻关系传递阈值ε。

(3c)计算云纹图像之间的相似度矩阵S。

(3d)计算近邻关系矩阵N。

(3e)近邻关系传递算法优化相似度矩阵。

(4)将上述优化之后的相似度矩阵作为MEAP算法的输入矩阵，通过调整参考值，获得正 确的分类数，实现云纹图像的自动分类。

本发明对云纹图像进行了预处理，选取了合适的图像特征提取算法，基于流形学习的思 想，采用改进的近邻关系传递算法对相似度矩阵进行优化，最后采用最新的多子类中心近邻 传播聚类算法实现自动分类，填补了云纹图像自动分类的空白，同时保证了云纹图像自动分 类的准确性。

本发明具有以下优点：

(1)通过对云纹图像进行预处理，排除了图像尺寸、背景噪声、线条粗细的影响，保证 自动分类的准确性不受其影响。

(2)针对云纹图像的主要特征在于其线条形状，选取了当前最优越的形状特征提取算法， 形状上下文描述子保证聚类结果比较理想。

(3)本发明采用近邻关系传递算法对形状上下文相似性矩阵进一步优化使得算法取得的 自动分类准确性更高，实现云纹图像的自动分类。

附图说明

图1是本发明的实现流程图；

图2是MEAP的聚类模型；

图3是部分云纹图像示例；

图4是尺寸归一化后的云纹图像示例；

图5是二值化之后的云纹图像；

图6是细化之后的云纹图像；

图7是云纹图像线条上所提取离散点示意图；

图8是云纹图像中某点到其他点的向量示意图；

图9是六种卷云纹图像示例图；

图10是NP-MEAP与SIFT-MEAP、ED-MEAP云纹图像聚类精度对比示意图；

图11是NP-MEAP算法在云纹图像上部分聚类结果示意图；

具体实施方式

一、基础理论介绍

1.多子类中心近邻传播聚类算法

MEAP算法是一个拥有二层结构的聚类算法，如图2所示该算法将所有数据对象分配给 最合适的子类中心，将每个子类中心分配给最合适的超簇类中心，从而实现模型化多子类问 题的目的。

与AP算法类似，MEAP算法为每个数据对象建立与其他数据对象的相似度信息s(i,j)以及 连接度信息l(i,j)。算法为每个数据对象设定偏向参数p＝s(k,k)与pp＝l(k,k)值，p与pp值 越大表示相应的数据对象作为候选的子类中心和超聚类中心的可能性就越大，得到的聚类数 就越多，通常分别设置p与pp值为相似度矩阵与连接度矩阵的中值。MEAP算法的核心步骤 为4类7个公式的交替更新过程，更新公式如下：

${\mathrm{\α}}_{ij}\←\min \[0,\underset{m\∈\{1,...N\}}{max}{{\mathrm{\ρ}}^m}_j+\underset{i^{\′}\∉\{i,j\}}{\Σ}max\[0,{\mathrm{\ρ}}_{i^{\′}j}\]\]$

${\mathrm{\α}}_{ii}\←\underset{i^{\′}\≠i}{\Σ}max\[0,{\mathrm{\ρ}}_{i^{\′}i}\]$

${\mathrm{\γ}}_{kk}\←\underset{i^{\′}\≠i}{\Σ}max\[0,{\mathrm{\φ}}_{i^{\′}k}\]$

${\mathrm{\φ}}_{ik}\←\min \[l_{ik}-\underset{m\≠k}{max}\[l_{im}+{\mathrm{\γ}}_{im}\],{\mathrm{\α}}_{ii}+{{\mathrm{\ρ}}^k}_i-{\mathrm{\γ}}_{ik}\]$

$i\≠j{\mathrm{\ρ}}_{ij}\←s_{ij}-max\[\underset{j^{\′}\∉\{j,i\}}{max}\[{{\mathrm{si}}_j}^{\′}+{\mathrm{\α}}_{ij}\],\underset{m\∈\{1,...,N\}}{max}\[l_{im}+{\mathrm{\γ}}_{im}\]+s_{ii}+{\mathrm{\α}}_{ii}\]$

${\mathrm{\γ}}_{ik}\←min\[0,{\mathrm{\φ}}_{kk}+\underset{i^{\′}\∉\{i,k\}}{\Σ}max\[0,{\mathrm{\φ}}_{i^{\′}k}\]\],k\≠i$

$\∀i=1,...,N,k=1,...,{{\mathrm{N\ρ}}^k}_i\←s_{ii}+l_{ik}-\underset{i^{\′}\≠i}{\max }\[s_{{\mathrm{ii}}^{\′}}+{\mathrm{\α}}_{{\mathrm{ii}}^{\′}}\]+{\mathrm{\γ}}_{ik}$

上述公式中相关参数的具体含义可参见文献multi-exemplar affinity propagation，所有新变 量均初始化为0。MEAP算法在整个迭代更新过程中，各数据对象进行竞争自动地产生相应的 子类中心和超簇类中心，将其他数据对象分配给最近的子类中心，子类中心由超簇类中心结 合在一起形成最终的聚类结果。

二、本发明是一种传统云纹图像自动分类方法

参照图1，本发明的具体实施过程包括以下步骤：

步骤1.云纹图像预处理

图3为多个云纹图案示例，从图3中可以看出从各种资料中采集的不同云纹图案的大小 尺寸不同，线条的粗细不一，同时部分采集的云纹图像包含有灰色背景噪声。因此需要对云 纹图像进行预处理，以取得更加准确的聚类精度。

(1.1)云纹图像的尺寸大小不同，首先将所有图像归一化到85*45的尺寸，这样既方便后 续图像的统一处理同时不会改变图像线条分布情况。归一化到85*45之后的云纹图像如图4 所示。

(1.2)针对云纹图像包含背景噪声的问题，对图像进行二值化处理消除背景噪声，同时也 方便采用数学形态学方法对图像进行细化。采用大津法计算二值化阈值，二值化之后的云纹 图像如图5所示。

(1.3)因为不同类云纹图像的线条形状不同，而同类云纹图像的线条形状基本相似，因此 本发明主要关注云纹图案线条形状。线条的不同粗细与云纹图案的类别并不相关，反而可能 影响聚类的准确性，因此采用数学形态学的方法将线条细化到一像素的宽度。细化之后的云 纹图像如图6所示。

步骤2.计算云纹图像集的形状上下文相似度矩阵

(2.1)SC算法认为每个图像中的物体可以用有限数目的离散点来近似描述，而这些离散点 并不需要是图形中的拐点、极值点等关键点，而是图形边界上均匀分布的离散点即可。图7 为经过预处理后云纹图像线条上所提取离散点示意图，其中图7中a小图对应图6中上排中 间小图，图7中b小图对应图6中上排最右侧小图。从图7中可以看出，云纹图像线条上的 离散点可以较为准确的描述相应的云纹图案线条形状，而且所提取的边界点越多，对图案的 近似描述越精确。但是提取的边界点过多时，则会导致算法的运行时间过长，通常选取100-150 个边界点即可比较准确的描述线条形状，本发明使用n＝100个边界离散点来描述线条形状。

将图7中二幅小图中的某个点用小方框标记。对图7中轮廓点集p＝{p₁,p₂,...,p_n},n＝100 中的某个离散点而言，考虑从该点出发到其他n-1个点的向量，这n-1个向量可以比较准确的 描绘该云纹图像的形状信息。如图8所示为图7中标记的离散点到其他所有点的向量图示。

(2.2)图8中每个点都可以用n-1个起始于该点终止于其余点的向量来描述，每个云纹线条 由n个n-1维的向量描述，由此可以得到每幅云纹图像比较丰富的特征描述矩阵。但是将所有 这些向量都计算出来用以描述云纹图像，计算量会非常大，并不现实。对于形状而言，仅仅 知道并计算出云纹图像线条轮廓上所有离散点相对于该点的位置关系即可。因此将云纹线条 所在的直角坐标系转换到对数极坐标系下，以待计算的离散点为对数极坐标系圆点，将极坐 标系在方向上从0到2π平均分为12份，半径上从极坐标圆点开始向外到2r通过对数空间函数 转换分为5份，其中r为数据集欧氏距离的平均值，这样整个极坐标系就被分为60份(bin)。 计算云纹图像的轮廓点散落到每个bin中的离散点数，形成一个60维的向量，称这个60维的向 量为对应离散点的形状上下文，即离散点的对数极坐标直方图。计算直方图公式如下：

h_i(k)＝#{q≠p_i:(q-p_i)∈bin(k)}

其中k表示极坐标系中第k个bin，取值为1到60，p_i为待计算直方图的云纹图像的边 界点，q为除p_i点之外的其他n-1个边界点，q-p_i为第k个bin中边界点的个数。

(2.3)计算两幅云纹图像中任意两点之间的形状上下文差异，对于云纹图像P中的一个 边界点p_i与云纹图像Q中边界点q_j，用标记这两个点的形状上下文差异，那么 的计算公式如下所示，其中h_i(k)与h_j(k)分别表示p_i与q_j直方图中第k个bin中边界点的个 数。

$C_{ij}^{sc}=C(p_i,q_j)=\frac{1}{2}\underset{k=1}{\overset{K}{\Σ}}\frac{{\[h_i\left(k\right)-h_j\left(k\right)\]}^2}{h_i\left(k\right)+h_j\left(k\right)}$

(2.4)计算两幅云纹图像中任意两点之间的正切角差异。形状上下文差异比较好的捕获了 不同云纹形状上离散点的整体差异，为了使得云纹形状离散点间的差异更加准确，添加离散 点的正切角差异，公式如下，其中θ_i与θ_j分别为p_i与q_j点处的正切角。

$C_{ij}^{\tan }=0.5(1-cos({\mathrm{\θ}}_i-{\mathrm{\θ}}_j))$

(2.5)将两幅云纹图像中任意两点之间的形状上下文差异与正切角差异有机结合，就可以 比较准确的度量不同云纹图像上任意两个点之间的形状上下文距离。公式如下：

$C_{ij}=(1-\mathrm{\β})C_{ij}^{sc}+{\mathrm{\βC}}_{ij}^{tan},\mathrm{\β}=0.1$

(2.6)计算两幅云纹图像之间的形状上下文距离。按上述公式通过计算云纹图像P中的任 意边界点p_i与云纹图像Q中任意边界点q_j之间的形状上下文距离，得到一个n*n(n＝100)的距 离矩阵，将距离矩阵横向与纵向最小值的平均值求和得到两幅云纹图像之间的形状上下文距 离值。计算公式如下：

$D_{sc}(P,Q)=\frac{1}{n}\underset{i=1}{\overset{n}{\Σ}}\underset{j=1,...n}{\arg \min }C(p_i,q_j)+\frac{1}{n}\underset{j=1}{\overset{n}{\Σ}}\underset{i=1,...n}{\arg \min }C(p_i,q_j)$

上述公式所得值越小，两幅图像之间差异越小，相似性越大，反之则相似性越小。将该 值取反作为两幅图像之间的形状上下文相似性度量，记为S_sc(P,Q)＝-D_sc(P,Q)，计算所有图 像之间的形状上下文相似性度量求得云纹图像集的相似性矩阵S_sc。

步骤3.改进的近邻传递算法(NP)优化S_sc矩阵

(3.1)计算形状上下文距离矩阵D＝[d_ij]_n×n，该矩阵用于初始化下文所述的近邻关系矩阵 N，矩阵中的元素d_ij为云纹图像i与j的形状上下文距离，该值取相反数用于更新近邻关系传递 成功之后的相似度矩阵S。

(3.2)计算近邻关系传递阈值，记云纹图像x_i与其第k个近邻点的距离为d_ik，取所有云纹 图像与其第k个近邻距离的平均值作为阈值，该阈值可以一定程度上减弱噪声数据的影响， 同时针对不同的数据集选取不同的k值可以使得近邻关系传递更准确。新阈值公式定义如下：

$\mathrm{\ϵ}=mean\left(\underset{i=1}{\overset{n}{\Σ}}{d}_{ik}\right)$

(3.3)计算云纹图像之间的相似度矩阵，相似度矩阵S＝[s_ij]_n×n，矩阵中第i行第j列元素s_ij的计算公式定义如下：

$s_{ij}=-{d_{ij}}^{\mathrm{\γ}}$

d_ij为形状上下文距离，此处通过指数变换放大所有云纹之间的距离，主要目的是放大位 于不同流形上云纹图像之间的距离，从而缩小其相似度。

(3.4)计算近邻关系矩阵N，如果距离矩阵D中的元素d_ij小于近邻关系传递阈值ε，那么 认为数据对象x_i与x_j互为近邻，表示为(x_i,x_j)∈R，由此定义求得所有云纹图像的近邻关系 矩阵。即当数据对象x_i与x_j互为近邻时，那么矩阵中对应的元素n_ij的值为1，否则取值为0， 对角线元素为0。

(3.5)近邻关系传递优化相似度矩阵，即如果n_ij＝0，而n_ik＝1,n_kj＝1，那么设置 n_ij＝1,n_ji＝1，同时更新s_ij＝s_ji＝-min(d_ik,d_kj)。

步骤4.将上述优化之后的相似度矩阵作为MEAP算法的输入矩阵运行算法，通过调整参 考值，获得正确的分类数，实现云纹图像的自动分类。

本发明的效果可通过以下实验进一步说明。

1.仿真条件

产生于先秦时期的卷云纹由云雷纹的抽象勾卷形拓展变迁出不同结构的曲卷组合。卷云 纹从春秋战国到秦汉时期大量应用于各种器物造型的表面装饰，在青铜器、漆器、玉饰、瓦 当砖雕、织锦刺绣等上都可以看见各种造型的卷云纹。卷云纹造型样式种类丰富，装饰效果 多样，在装饰艺术发展历史和当代设计应用领域都有着重要的地位。

这里选用先秦时期的卷云纹图案作为测试本发明方法的样本图案。数据集包含6种类型 的230幅云纹图案。根据卷云纹曲线形状的不同，分别为单勾式卷云纹、内敛式卷云纹、发 散式卷云纹、综合式卷云纹、S形卷云纹、如意式卷云纹。图9为这6种卷云纹的示例图案。

为了验证本发明所提算法的可行性与有效性，将本发明，即基于近邻传递与SC特征的 MEAP算法(NP-MEAP)与基于SIFT特征的MEAP算法(SIFT-MEAP)以及基于欧氏距离的 MEAP算法(ED-MEAP)进行比较。整个实验过程，设置算法的p与pp的初始值为相似度矩阵 的中值，阻尼系数lam＝0.9，收敛迭代次数convits＝50，最大循环次数maxits＝1000，γ＝3。实 验运行环境如下：处理器为Core(TM)i5-3470，主频3.2GHz，内存4GB，硬盘500GB，操 作系统为Windows 7旗舰版64位操作系统，编程语言为Matlab R2013a。本发明采用常用 的聚类结果评价指标NMI指标与FMI指标。

标准化共信息NMI指标的计算公式如下：

$NMI=\frac{2{\mathrm{\Σ}}_{l=1}^c{\mathrm{\Σ}}_{l=1}^{c^{^}}\frac{n_l^{\left(h\right)}}{n}\log \frac{n_l^{\left(h\right)}n}{{\mathrm{\Σ}}_{i=1}^c{n}_i^{\left(h\right)}{\mathrm{\Σ}}_i^{c^{^}}{n}_i^{\left(i\right)}}}{H\left(\mathrm{\π}\right)+H\left(\mathrm{\ζ}\right)}$

$H\left(\mathrm{\π}\right)=-{\mathrm{\Σ}}_{i=1}^c\frac{n_i}{n}log\frac{n_i}{n}$

$H\left(\mathrm{\ζ}\right)=-{\Σ}_{j=1}^{c^{^}}\frac{n^{\left(j\right)}}{n}\log \frac{n^{\left(j\right)}}{n}$

其中π为聚类算法所得簇类的类标签，ζ为数据集真实分类的类标签，n_i(h)表示簇类l 与真实分类h中数据对象的个数。H(π)为簇类标签π的香农熵，H(ζ)为真实分类标签ζ的 香农熵，n_i与n^(j)分别为簇类i与真实分类j中样本点的个数。NMI的值越大，说明聚类结果 与真实分类越接近。

FMI(Fowlkes-Mallows Index)指标的计算公式如下：

$FMI=\frac{a}{\sqrt{(a+b)(a+c)}}$

设聚类算法的聚类结果用C＝{c₁,c₂,...,c_m}表示，数据集的真实分类用P＝{p₁,p₂,...,p_l}表 示。x_i和x_j为数据集中任意两个数据对象。其中a为x_i和x_j在C与P中同属于一个簇的数目； b为x_i和x_j在C中属于相同簇，而在P中属于不同簇的数目；c为x_i和x_j在C中同属于不同 簇，而在P中属于相同簇的数目；d为x_i和x_j在C与P中同属于不同簇的数目，这里 a+b+c+d＝n(n-1)/2。由此可知FMI取值范围是[0,1]，且值越大，算法聚类准确率越高。

基于云纹图像SIFT特征的MEAP算法在云纹图像预处理之后，将一像素宽度的云纹线 条进行适当膨胀，以保证线条形状不变的情况下使得SIFT算法能更有效的提取到合适的SIFT 特征。基于欧氏距离的MEAP算法在云纹图像预处理之后，同样将一像素宽度的云纹线条进 行适当膨胀，同时将图像恢复到二值化前的图像像素灰度值，以此保证欧氏距离能更加准确 地反映云纹图像间的距离。基于形状上下文与近邻关系传递的MEAP算法提取的离散点具有 一定的随机性，因而每次检测到的离散点有一定的差异，从而使得算法一次运行所得的形状 上下文距离有一定的波动，因此将形状上下文算法运行20次，取20次形状上下文距离的和 作为近邻关系传递算法的输入，优化相似度矩阵，从而保证算法的稳定性。

2.仿真结果

将本发明方法(NP-MEAP)与ED_MEAP和SIFT_MEAP方法作对比。

图10是NP-MEAP与SIFT-MEAP、ED-MEAP的云纹图像聚类精度对比示意图，从图中可 以看到，SIFT-MEAP与ED-MEAP两种算法的聚类精度基本相同，都只能达到40％左右的聚类 准确性，由此可知基于SIFT提取的云纹图像特征匹配数与基于负欧氏距离的云纹图像相似度 都不能很好的反映云纹图像间的相似度。而反观NP-MEAP的聚类准确性却能达到80％以上。 对于十分复杂的云纹图案聚类问题，这样的精度已相当不错，已可以在很大程度上减轻人工 分类的工作强度和效率问题。同时这也说明经过近邻关系传递算法优化的基于形状上下文特 征的相似度矩阵能更好的反映云纹图像间的相似度，因而聚类效果更好。

图11是NP-MEAP算法在云纹图像上聚类结果示意图，其中每个圆角矩形代表一个簇类， 每个圆角矩形中由方格标记的云纹图像为对应簇类的中错误聚类的图像。