基于空间约束特征选择及其组合的中国剪纸识别方法

摘要

本发明公开了一种基于空间约束特征选择及其组合的中国剪纸识别方法。包括如下步骤：1)采用空间金字塔匹配和上下文相关直方图相结合方法提取样本初始特征，形成样本候选特征；2)利用基于AdaBoost的特征选择和组合技术对候选特征进行处理，得到区别性特征；3)通过每一类中所有组合特征的中心特征向量、区别性特征以及定义其上的距离计算公式来表征该类；4)计算测试集样本在区别性特征上与各类别中心特征的距离，得到剪纸作品分类识别结果。本发明有效地将空间金字塔匹配和上下文相关直方图这两种方法结合起来，克服其在表达图像形状上的局限性，提取和形成具有区别性的剪纸图像形状特征，并在此基础之上实现剪纸作品分类识别。

说明书

技术领域

本发明涉及图像识别领域，尤其涉及一种基于空间约束特征选择及其组合的中国剪纸识别方法。

背景技术

剪纸，又名“刻纸”，是一种以纸为加工对象，以剪刀(或刻刀)为工具进行创作的艺术。剪纸因其讲究刀法，玲珑剔透纸感语言和强调影廓造型而形成一种独特艺术形式。经过几千年发展与积淀，剪纸作品可分为动物、肖像、人物和文字等类别。

剪纸作品包含了丰富语义而难以用文字直接进行表达，大量剪纸作品经过数字化处理后，为了发挥其共享优势，迫切需要研究针对剪纸作品的搜索技术。基于内容图像检索Content-based Information Retrieval(CBIR)方法因其通过图像视觉特征(如颜色、纹理和形状等)实现相似图像检索而引起广泛关注，由于存在底层特征难以表达高层语义这一“语义鸿沟”，使得CBIR这一图像搜索方法面临很大挑战。

CBIR一般采用的视觉特征包括颜色、形状、纹理以及他们的组合。由于形状是表现剪纸作品蕴含语义的重要特征，因此剪纸作品的形状特征提取方法成为剪纸作品识别的关键问题。计算机视觉和模式识别(Computer Vision andPattern Recognition)2006年会议论文集中公布了一种提取图像形状特征及其计算相应相似度的方法——空间金字塔匹配(Spatial Pyramid Matching，SPM)。该方法首先对图像构造尺度大小不同空间金字塔，在空间金字塔的每一层用粒度递增的单元格去对图像进行空间划分，然后统计每一个划分得到的图像单元格子块中视觉单词(Visual Words)出现次数，得到视觉单词直方图。由于在单元格大小变化过程中各视觉单词出现次数随之变化，这一变化可体现图像中形状在不同尺度空间不同，因此用直方图的交来表示每一层金字塔。2009年电气和电子工程师协会关于计算机视觉和模式识别会议(IEEE Conference onComputer Vision and Pattern Recognition)论文集中公布了一种提出了一种基于马尔可夫稳态特性(Markov Stationary Features，MSF)的上下文相关直方图(Contextualizing Histogram，CH)特征提取方法。上述两种特征提取方法都存在一定局限性，空间金字塔匹配反映了图像在不同尺度上的相似性，上下文相关直方图则反映了图像在同一尺度上存在空间上下文约束的相似性。

发明内容

本发明的目的是克服空间金字塔匹配和上下文相关直方图在表达图像形状上的局限性，将其有效结合，提供一种基于空间约束特征选择及其组合的中国剪纸识别方法。

基于空间约束特征选择及其组合的中国剪纸识别方法包括如下步骤：

1)采用空间金字塔匹配和上下文相关直方图相结合的方法提取样本初始特征，形成样本候选特征；

2)利用基于AdaBoost的特征选择和组合技术对样本候选特征进行处理，得到样本区别性特征；

3)通过每一类中所有组合特征的中心特征向量、区别性特征以及定义其上的距离计算公式来表征该类；

4)计算测试集样本在区别性特征上与各类别中心特征的距离，得到剪纸作品分类识别结果；

所述的采用空间金字塔匹配和上下文相关直方图结合的方法提取样本初始特征，形成样本候选特征步骤包括：对于给定的M幅剪纸图像s_i{1≤i≤M}，分别提取128维的SIFT局部特征，进而用K-means聚类得到32个视觉单词。为了得到这些视觉单词之间存在的空间结构性属性，对训练集样本通过采样得到3层金字塔，l代表空间金字塔的第l层(l≥0)，d代表第l层单元格的总数，d＝2^l×2^l，这样每幅剪纸图像总共得到(4^l-1)/3个子块。对于这些(4^l-1)/3个子块，在其每一个子块内，定义马尔可夫稳态特性，来计算得到表示视觉单词之间共生关系的伴随矩阵。这样，对于每幅图像，可提取出具有空间约束的特征维数为Z，这里Z＝∑_l64×(4^l-1)/3。值得指出的是，本文在提取具有空间约束特征过程中，是按照图像中所包含的视觉单词进行提取，而不是按照像素点颜色值进行提取。同时，每幅图像所提取的特征维数均相同。为了消除每个特征值域变化范围不同对分类造成的影响，给定每一类剪纸图像后，对其相应维特征进行归一化处理。

所述的利用基于AdaBoost的特征选择和组合技术对样本候选特征进行处理，得到样本区别性特征步骤包括：对于第j类剪纸图像每一轮对任意两维特征进行组合，并连同原特征一起作为候选特征。给定N类M幅剪纸图像s_i{1≤i≤M}，其类别标记矩阵记为T：

T＝{t_ij∈{0，1}|1≤i≤M，1≤j≤N}

其中，i和j分别用来表示第i幅剪纸图像和第j个类别；如果第i幅剪纸图像属于第j个类别，则t_ij＝1，否则t_ij＝0。仍然以第j类剪纸图像为例来介绍其对应的区别性特征选择过程。在训练分类器之前，用w_ij表示属于第j个类别的第i幅剪纸加权计算简单分类器误差权重，即W＝{w_ij|1≤i≤M，1≤j≤N}，它表征了简单分类器对总体分类的影响，其初始值定义如下：

$w_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{{\Sigma }_{i=1}^M{t}_{\mathrm{ij}}}{2M}& \mathrm{if}(t_{\mathrm{ij}}=0)\\ \frac{M-{\Sigma }_{i=1}^M{t}_{\mathrm{ij}}}{2M}& \mathrm{if}(t_{\mathrm{ij}}=1)\end{array}\right)$

首先应用AdaBoost的思想，对组合出来的待选择特征V(即特征组合过程中的一种组合特征)中各分量v_ik构造简单分类器，该分类器定义如下：

${\mathrm{FSC}}_{\mathrm{ik}}=\left(\begin{array}{cc}1& \mathrm{if}(\mathrm{sort}\left(\right|v_{\mathrm{ik}}-c_{\mathrm{jk}}\left|\right)<\mathrm{count}\left(t_j\right))\\ 0& \mathrm{if}(\mathrm{sort}\left(\right|v_{\mathrm{ik}}-c_{\mathrm{jk}}\left|\right)>\mathrm{count}\left(t_j\right))\end{array}\right)$

其中sort(|v_ik-c_jk|)的表示分量v_ik与类中心欧氏距离排序后的排名。count(t_j)表示第j类样本数。利用上述分类器对待选择特征V进行分类，得到分类结果集：

R＝{r_ik∈{0，1}|1≤i≤M，1≤k≤K}

每个特征分量计算训练误差定义为：

$E=\{e={\Sigma }_{i=1}^M{w}_{\mathrm{ij}}\times |r_{\mathrm{ik}}-t_{\mathrm{ik}}\left|\right\}$

其计算过程中，每次计算需依照以下公式更新权值w_ij，

$w_{\mathrm{ij}}=\frac{w_{\mathrm{ij}}^{\prime }\times {\left(\frac{e}{1-e}\right)}^{1-|r_{\mathrm{ik}}-t_{\mathrm{ik}}|}}{{\Sigma }_{i=1}^M{w}_{\mathrm{ij}}^{\prime }\times {\left(\frac{e}{1-e}\right)}^{1-|r_{\mathrm{ik}}-t_{\mathrm{ik}}|}}$

得到候选特征V各分量分类误差后，对其按照该分类误差进行排序，选取V中误差最小前Z个分量构成第j类剪纸图像的一种区别性特征。

所述的通过每一类中所有组合特征的中心特征向量、区别性特征以及定义其上的距离计算公式来表征该类步骤包括：通过特征组合和选择可得到每一类的区别性特征，以此作为每一类中所有组合特征的类中心特征向量，然后选择得到的区别性特征，并利用定义其上的距离计算公式来表征该类；距离计算公式定义为其中t为测试集样本特征向量，s为训练集样本特征向量。据此，可以计算测试集样本在判别性特征上与各类别中心特征的距离，从而实现对剪纸作品的分类识别。

所述的计算测试集样本在区别性特征上与各类别中心特征的距离，得到剪纸作品分类识别结果步骤包括：对测试集样本进行预处理，提取SIFT特征，采用K-Means聚类算法提取视觉单词，形成样本初始特征；然后采用空间金字塔匹配和上下文相关直方图结合的方法处理样本初始特征，形成样本候选特征；利用距离计算公式计算测试集样本在区别性特征上与各类别中心特征的距离，其中t为测试集样本特征向量，s为训练集样本特征向量；最终得到测试集分类识别结果，比较测试集分类结果与真实分类结果。

本发明有效地将空间金字塔匹配和上下文相关直方图这两种方法结合起来，克服其在表达图像形状上的局限性，提取和形成具有区别性的剪纸图像形状特征，并在此基础之上实现剪纸作品分类识别。

附图说明

图1是本发明金字塔子块划分示意图。

图2是剪纸作品集各类别示例图。

图3是不同区别性特征维数下本发明与单独使用空间金字塔匹配以及单独使用上下文相关直方图的AUC得分比较。

具体实施方式

基于空间约束特征选择及其组合的中国剪纸识别方法包括如下步骤：

1)采用空间金字塔匹配和上下文相关直方图相结合的方法提取样本初始特征，形成样本候选特征；

2)利用基于AdaBoost的特征选择和组合技术对样本候选特征进行处理，得到样本区别性特征；

3)通过每一类中所有组合特征的中心特征向量、区别性特征以及定义其上的距离计算公式来表征该类；

4)计算测试集样本在区别性特征上与各类别中心特征的距离，得到剪纸作品分类识别结果；

所述的采用空间金字塔匹配和上下文相关直方图结合的方法提取样本初始特征，形成样本候选特征步骤包括：对于给定的M幅剪纸图像s_i{1≤i≤M}，分别提取128维的SIFT局部特征，进而用K-means聚类得到32个视觉单词。为了得到这些视觉单词之间存在的空间结构性属性，对训练集样本通过采样得到3层金字塔，l代表空间金字塔的第l层(l≥0)，d代表第l层单元格的总数，d＝2^l×2^l，这样每幅剪纸图像总共得到(4^l-1)/3个子块。对于这些(4^l-1)/3个子块，在其每一个子块内，定义马尔可夫稳态特性，来计算得到表示视觉单词之间共生关系的伴随矩阵。这样，对于每幅图像，可提取出具有空间约束的特征维数为Z，这里Z＝∑_l64×(4^l-1)/3。值得指出的是，本文在提取具有空间约束特征过程中，是按照图像中所包含的视觉单词进行提取，而不是按照像素点颜色值进行提取。同时，每幅图像所提取的特征维数均相同。为了消除每个特征值域变化范围不同对分类造成的影响，给定每一类剪纸图像后，对其相应维特征进行归一化处理。

所述的利用基于AdaBoost的特征选择和组合技术对样本候选特征进行处理，得到样本区别性特征步骤包括：对于第j类剪纸图像每一轮对任意两维特征进行组合，并连同原特征一起作为候选特征。具体实施步骤如下：

输入：候选特征集候选特征集V＝{v_ik|1≤i≤M，1≤k≤Z}；标注矩阵T＝{t_ij∈{0，1}|1≤i≤M，1≤j≤N}

输出：组合后特征集V′＝{v′_ik|1≤i≤M，1≤k≤H}

步骤：

1.初始化V_r＝φ

2.对k＝1 to K重复如下操作：

a)设V_c＝φ

b)设V_r＝V_r∪V

c)对V_r中每两个列向量V_a和V_b重复如下操作：

i.计算V_c＝V_c∪{V_na+V_nb}

d)应用改进的AdaBoost方法在V_c选择h个最合适的分量存储于V_r

3.应用改进的AdaBoost方法在V_r选择H个最合适的分量得到组合后特征集

对于第i类剪纸图像每一轮对任意两维特征进行组合，并连同原特征一起作为候选特征。给定N类M幅剪纸图像s_i{1≤i≤M}，其类别标记矩阵记为T：

T＝{t_ij∈{0，1}|1≤i≤M，1≤j≤N}

其中，i和j分别用来表示第i幅剪纸图像和第j个类别；如果第i幅剪纸图像属于第j个类别，则t_ij＝1，否则t_ij＝0。仍然以第j类剪纸图像为例来介绍其对应的区别性特征选择过程。在训练分类器之前，用w_ij表示属于第j个类别的第i幅剪纸加权计算简单分类器误差权重，即W＝{w_ij|1≤i≤M，1≤j≤N}，它表征了简单分类器对总体分类的影响，其初始值定义如下：

$w_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{{\Sigma }_{i=1}^M{t}_{\mathrm{ij}}}{2M}& \mathrm{if}(t_{\mathrm{ij}}=0)\\ \frac{M-{\Sigma }_{i=1}^M{t}_{\mathrm{ij}}}{2M}& \mathrm{if}(t_{\mathrm{ij}}=1)\end{array}\right)$

首先应用AdaBoost的思想，对组合出来的待选择特征V(即特征组合过程中的一种组合特征)中各分量v_ik构造简单分类器，该分类器定义如下：

${\mathrm{FSC}}_{\mathrm{ik}}=\left(\begin{array}{cc}1& \mathrm{if}(\mathrm{sort}\left(\right|v_{\mathrm{ik}}-c_{\mathrm{jk}}\left|\right)<\mathrm{count}\left(t_j\right))\\ 0& \mathrm{if}(\mathrm{sort}\left(\right|v_{\mathrm{ik}}-c_{\mathrm{jk}}\left|\right)>\mathrm{count}\left(t_j\right))\end{array}\right)$

其中sort(|v_ik-c_jk|)的表示分量v_ik与类中心欧氏距离排序后的排名。count(t_j)表示第j类样本数。利用上述分类器对待选择特征V进行分类，得到分类结果集：

R＝{r_ik∈{0，1}|1≤i ≤M，1≤k≤K}

每个特征分量计算训练误差定义为：

$E=\{e={\Sigma }_{i=1}^M{w}_{\mathrm{ij}}\times |r_{\mathrm{ik}}-t_{\mathrm{ik}}\left|\right\}$

其计算过程中，每次计算需依照以下公式更新权值w_ij，

$w_{\mathrm{ij}}=\frac{w_{\mathrm{ij}}^{\prime }\times {\left(\frac{e}{1-e}\right)}^{1-|r_{\mathrm{ik}}-t_{\mathrm{ik}}|}}{{\Sigma }_{i=1}^M{w}_{\mathrm{ij}}^{\prime }\times {\left(\frac{e}{1-e}\right)}^{1-|r_{\mathrm{ik}}-t_{\mathrm{ik}}|}}$

得到候选特征V各分量分类误差后，对其按照该分类误差进行排序，选取V中误差最小前Z个分量构成第j类剪纸图像的一种区别性特征。具体实施方式如下：

输入：训练样本集S＝{s_k|1≤k≤M}；标注矩阵T＝{t_ij∈{0，1}|1≤i≤M，1≤j≤N}；待选择特征集V＝{v_ik|1≤i≤M，1≤k≤L}

输出：特征集V中Z个最具判别性分量

步骤：

1.初始化权重W＝{w_ij|1≤i≤M，1≤j≤N}

2.计算样本候选特征算术平均值C＝{c_k|1≤k≤L}

3.从k＝1 to L重复如下操作：

a)计算：

${\mathrm{FSC}}_{\mathrm{ik}}=\left(\begin{array}{cc}1& \mathrm{if}(\mathrm{sort}\left(\right|v_{\mathrm{ik}}-c_{\mathrm{jk}}\left|\right)<\mathrm{count}\left(t_j\right))\\ 0& \mathrm{if}(\mathrm{sort}\left(\right|v_{\mathrm{ik}}-c_{\mathrm{jk}}\left|\right)>\mathrm{count}\left(t_j\right))\end{array}\right)$

b)得到分类结果集R＝{r_ik∈{0，1}|1≤i≤M，1≤k≤K}

c)计算训练误差$E=\{e={\Sigma }_{i=1}^M{w}_{\mathrm{ij}}\times |r_{\mathrm{ik}}-t_{\mathrm{ik}}\left|\right\}$

d)更新权重w_ij

4.对E升序排序，取前Z个分量构成判别性特征

所述的通过每一类中所有组合特征的中心特征向量、区别性特征以及定义其上的距离计算公式来表征该类步骤包括：通过特征组合和选择可得到每一类的区别性特征，以此作为每一类中所有组合特征的类中心特征向量，然后选择得到的区别性特征，并利用定义其上的距离计算公式来表征该类；距离计算公式定义为其中t为测试集样本特征向量，s为训练集样本特征向量。据此，可以计算测试集样本在判别性特征上与各类别中心特征的距离，从而实现对剪纸作品的分类识别。

所述的计算测试集样本在区别性特征上与各类别中心特征的距离，得到剪纸作品分类识别结果步骤包括：对测试集样本进行预处理，提取SIFT特征，采用K-Means聚类算法提取视觉单词，形成样本初始特征；然后采用空间金字塔匹配和上下文相关直方图结合的方法处理样本初始特征，形成样本候选特征；利用距离计算公式计算测试集样本在区别性特征上与各类别中心特征的距离，其中t为测试集样本特征向量，s为训练集样本特征向量；最终得到测试集分类识别结果，比较测试集分类结果与真实分类结果。

实施例1：

1)构造剪纸数据集：从互联网收集了246幅中国剪纸图像。根据这些剪纸艺术题材，如图2所示将数据集分为四种类别：动物、肖像、人物以及文字。将80％的样本作为训练集，20％作为测试集；

2)对训练集样本进行训练，具体步骤如下：

a)对训练集样本进行预处理，提取SIFT特征，采用K-Means聚类算法提取视觉单词，形成样本初始特征；

b)采用空间金字塔匹配和上下文相关直方图结合的方法处理样本初始特征，形成样本候选特征；

c)利用基于AdaBoost的特征选择和组合技术对样本候选特征进行处理，得到样本区别性特征；

d)通过每一类中所有组合特征的类中心特征向量、选择得到的区别性特征以及定义其上的距离计算公式来表征该类。

3)对测试集样本进行测试，具体步骤如下：

a)对测试集样本进行预处理，提取SIFT特征，采用K-Means聚类算法提取视觉单词，形成样本初始特征；

b)采用空间金字塔匹配和上下文相关直方图结合的方法处理样本初始特征，形成样本候选特征；

c)计算测试集样本在区别性特征上与各类别中心特征的距离，得到测试集分类识别结果；

4)比较测试集分类结果与真实分类结果。

  AUC  Macro-F1  SPM-CH AdaBoost  0.6342  0.4022  SPM AdaBoost  0.599  0.3723

  AUC  Macro-F1  CH AdaBoost  0.5056  0.1603  SPM SVM  0.5  0.1033  CH SVM  0.5235  0.1147  SPMK  0.6262  0.4145  CH  0.5  0.1582

上表给出了本发明与其他传统分类识别方法在AUC得分和Macro-F1得分上的比较。图3给出了不同区别性特征维数下本发明与单独使用空间金字塔匹配以及单独使用上下文相关直方图的AUC得分比较。其中本发明称为SPM-CHAdaBoost。其他传统分类识别方法包括：

1)SPMK：这一方法基于金字塔模型提取剪纸图像特征，然后采用空间金字塔匹配算法进行分类。

2)CH：这一方法基于图像上下文相关视觉单词提取特征，对于得到的特征按照欧式距离进行分类。

3)SPM AdaBoost：这一方法先通过金字塔模型提取剪纸图像特征，然后直接应用AdaBoost进行分类。

4)CHAdaBoost：这一方法先通过上下文相关视觉单词提取剪纸图像特征，然后直接应用AdaBoost进行分类。

5)SPM SVM：这一方法先通过金字塔模型提取剪纸图像特征，然后应用线性核函数的支持向量机进行分类。

6)CH SVM：这一方法先通过上下文相关视觉单词方法提取特征，然后应用线性核函数的支持向量机进行分类。

结果表明：本发明整体分类识别效果好于其他传统分类识别方法，并且本发明对空间金字塔匹配和上下文相关直方图的具有良好的改进。