0 引言

图像分类是计算机视觉领域的研究热点，在互联网、人工智能等领域应用广泛^[1]。目前，图像分类方法主要分为两类：基于图像空间的分类方法和基于特征空间的分类方法^[2-5]。前者是指直接利用图像的颜色和纹理等底层特征进行图像分类，如采用灰度共现矩阵描述图像的纹理特征、依据纹理的差异来进行图像分类^[6]。近些年随着深度学习研究的深入，也可以将图像直接输入深度学习网络来进行图像分类，如文献[7]提出一种基于受限玻尔兹曼机与卷积神经网络混合模型迁移学习的图像分类方法，该方法使用受限玻尔兹曼机代替卷积神经网络模型中的全连接层，在目标集上重新训练受限玻尔兹曼机层和Softmax层，消除了数据集间内容差异对迁移学习特征识别能力的影响。深度学习方法提高了图像分类的正确率，但此类方法的运算效率偏低。后者是先对图像进行描述，采用不同的特征来区分图像，然后再借助机器学习方法实现图像分类。如文献[8]提取图像的局部特征描述子，采用一种类似Fisher的核特征以及扩展的词袋模型来描述图像并进行图像分类。文献[9]提出了一种基于稀疏编码的多尺度空间潜在语义分析的图像分类方法，主要思想是利用稀疏编码对图像各个局部块特征进行软量化，构建共生矩阵，然后结合概率潜在语义分析获取每个局部块的潜在语义信息并进行加权融合，最后采用支持向量机（Support Vector Machines，SVM）分类器实现图像分类。

本文提出一种结合图像的多尺度字符串表示以及改进的编辑距离和SVM分类器进行图像分类方法，采用字符串组合来描述多尺度图像，通过字符串之间的编辑距离来测量两幅图像的相似度，作为图像分类的依据。

1 本文方法

本文方法结合图像的多尺度字符串表示以及改进编辑距离和SVM分类方法实现图像分类，基本流程如图1所示。首先，对图像进行多尺度分块，然后提取各个归一化图像子块上的方向梯度直方图（Histogram of Oriented Gradient，HOG）特征，将生成的多尺度特征向量用多个字符串进行表示；接着计算两幅图像对应的两组字符串之间的改进编辑距离，测试两幅图像的相似度。最后采用改进的SVM分类方法进行图像分类，详细过程描述如下。

1.1 多尺度字符串表示

在图像分类之前，首先要提取图像特征，将图像抽象为特征向量。图像特征提取方法很多，如Haar^[10]、局部二元模式^[11]、HOG^[12]等。相对而言，HOG特征的区分能力强于其他两种方法，因此本文采用HOG特征描述图像。

HOG特征提取的基本步骤为：

(1)图像预处理，包括图像灰度化、伽马校正等；

(2)将图像划分为许多细胞单元块；

(3)计算每一个细胞单元块的梯度；

(4)统计每一个细胞单元的块的方向梯度直方图，形成HOG描述子。

HOG特征对几何和光学形变具有鲁棒性，但对尺度的鲁棒性不强。因此，本文在进行图像分类前，先将图像划分为不同尺度的图像子块，然后再提取HOG特征。通过分析同一类别图像中目标出现的位置规律，本文将图像分为如图2所示的33个尺度的图像子块。然后将每一个图像子块都归一化到32×32的尺寸，提取HOG特征向量。其中，HOG特征提取所用的单元格和块尺寸在实验部分讨论。本文将每一个图像子块的HOG特征向量看作一个字符串。那么，一幅图像可以用33个字符串表示。后续通过对字符串进行匹配来实现图像的分类。

1.2 改进的编辑距离计算

传统的编辑距离用于计算两个字符串所对应的符号的最优排列，具体是通过一系列的编辑操作，将输入的字符串X=x₁，x₂，…，x_N转换为输出字符串Y=y₁，y₂，…，y_M。

常用的编辑操作有3种，分别为^[13]：

(1)插入：将符号y_j插入到字符串X中。

(2)删除：从字符串X中删除符号x_i。

(3)替换：用符号y_j替换字符串X中符号x_i。

这样，对于任意两个字符串X和Y，总存在一个有序的编辑操作集合，可以将字符串X变换到Y。

将字符串X转换为字符串Y可以通过多个有序的编辑操作集合来实现，每一种编辑操作集合所对应的代价可能是不同的。将字符串X转换为字符串Y的最小编辑代价定义字符串X与字符串Y之间的编辑距离。这样，字符串X与Y越相似，那么将字符串X转换到字符串Y所需要采用的必要编辑操作的代价越小，也即对应的编辑距离越小。因此，编辑距离可以测量两个字符串之间的相似度。

编辑距离的计算可以看作是一个最优化问题，采用动态规划算法来进行求解。具体地，对于一个包含N个符号的字符串X=x₁，x₂，…，x_N和一个包含M个符号的字符串Y=y₁，y₂，…，y_M，首先需要计算一个维度为N×M的动态规划矩阵，表示为：

得到该矩阵之后，矩阵的最后一项D_N-1，M-1即为将输入的字符串X=x₁，x₂，…，x_N转换为输出字符串Y=y₁，y₂，…，y_M的最小代价，也即字符串X与Y之间的编辑距离。

3个编辑操作可以将任一字符串转换为另一字符串，并测量其相似度。然而，对于不同的应用领域，这些编辑操作的代价的计算方式不同。对于本文所关注的图像分类领域，字符串中的各个符号是图像整体或局部的一个特征描述，因此，本文采用特征向量之间的欧氏距离来描述两个特征向量所对应的符号的替换操作的代价，表示为：

这样，两个特征向量越相似，其欧氏距离越小，从而得到的替换操作的代价也越小。考虑到不同图像以及图像的不同子块的尺度不一，为了便于比较编辑操作的代价，需要将特征向量进行归一化，这样，替换操作的代价可以修正为：

插入和删除操作可以看作是对不匹配的两个符号之间的不相似度的建模。对于图像特征向量所对应的符号而言，如果两个符号需要进行插入或者删除编辑操作，那说明这两个符号是不相似的，因此可以定义一个惩罚因子c，该因子为常量，将其作为插入和编辑操作的固定代价，表示为：

特别地，当特征向量归一化之后，这一固定代价可以看作是两个空向量之间的距离。如果两个特征向量之间的距离低于固定代价，则认为两个特征向量相似。因为当两个特征向量不匹配时，在计算距离时会受到惩罚。基于这一思路，可以采用编辑操作来测量两幅图像是否相似。

对于图像而言，由于可能存在尺度或者平移等几何变换，这样，一幅图像中的某个图像子块可能与另一幅图像中任一图像子块都不相似，而是与另一幅图像中几个相邻图像子块的并集相似。类似地，也可以是一幅图像中的某几个图像子块的并集与另一幅图像中的一个或几个图像子块的并集相似。这种情况下，采用现有的3种编辑操作难以准确测量两幅图像之间的相似度。为此，本文提出一种融合编辑操作，该操作可以对图像区域的融合和分裂操作进行建模，目标是更好地匹配两幅图像。

融合操作在字符串上的两个相邻符号上进行，可以用于将输入字符串中的一个符号对{x_i，x_i+1}与输出字符串中的符号y_j相匹配。或者相反，将输出字符串中的一个符号对{y_j，y_j+1}与输入字符串中的符号x_i相匹配。因为相邻的融合操作既可以作用于输入字符串，也可以作用于输出字符串，因此，符号序列{x_i，x_i+1，…，x_i+k}可以与符号序列{y_j，y_j+1，…，x_j+l}相匹配。可见，融合操作包含了插入和删除操作。从图像的角度来看，融合操作允许一个图像中的一组连续的图像子块与另一幅图像中的一组图像子块相匹配。这意味着如果一个目标被分为许多区域，对应的局部特征可能组合在一起去与另一幅图像中的一个或者多个区域的相同组合的目标特征相匹配。

具体地，给定一个特征向量序列{x_i，x_i+1，…，x_i+k}，融合操作在于创建一个新的特征向量，表示为：

1.3 改进的SVM分类

本文通过对字符串进行分类来实现图像的分类，采用基于编辑距离改进的SVM分类器。具体地，采用编辑距离修改SVM的径向基函数，表示为：

其中，I_X和I_Y分别表示待匹配的两幅图像。依据前面介绍，每一幅图像都可以用33个字符串来表示。

SVM分类器的基本原理和训练过程这里不再赘述，可参考文献[9]。

2 仿真试验

为了定量评价本文方法的性能，下面将本文方法与文献[6]、[7]、[9]所述的图像分类方法进行对比仿真试验，在图像分类领域公开的数据集和相同的计算机平台上测量不同方法的性能指标，给出本文方法的定量评价结果。下面首先介绍本文方法所涉及的数据集，然后介绍本文选用的定量评价指标，接着介绍本文方法的一些参数配置，最后给出性能对比分析结果，详细介绍如下。

2.1 数据集

图像分类领域所用的公开数据集主要有两个：COIL-100和PVOC 2007，简要介绍如下：

(1)COIL-100数据集：该数据集包含图像数量为7 200幅，目标类别数为100。可以分为测试和训练两个子集，其中，训练样本子集包含800图像，测试样本子集包含6 400幅图像。图像的尺寸都是128×128。

(2)PVOC 2007数据集：该数据集包含图像数量为9 963幅，类别数为20。目标包含不同的尺度、视角和光照变化。也可以分为测试和训练两个数据子集，其中，训练样本子集包含5 011图像，测试样本子集包含4 592幅图像。图像的尺寸都是192×192。

本文选用这两个数据集进行图像分类实验，测试4种对比方法的性能。其中，4种方法所用的训练数据集和测试数据集是相同的。对于两类数据集，分别进行训练和测试，计算性能指标。

2.2 评价指标

图像分类主要关注两个方面：(1)分类结果是否正确，(2)分类速度是否够快。这两个方面可以采用两个指标来进行定量测试：

正确率指标定义为：

值得说明的是，分类耗时的测量与所用的计算机硬件平台以及软件环境都密切相关。为保证测量结果的可对比性，本文在同一计算机软硬件平台上测试4种方法的性能指标。具体地，计算机的硬件平台参数为：CPU：Intel I5四核3.2 GHz；内存：16G DDR3；软件环境参数为：Windows 7 64位操作系统，Visual Studio 2013开发环境，OpenCV 2.4.11视觉库。

2.3 参数设置

本文在提取图像的HOG特征时，单元格和块的尺寸不同，得到的图像分类正确率也有差异。在试验过程中，本文设置了8×8和4×4两种单元格尺寸，以及4×4和2×2两种块尺寸，测试不同单元格和块尺寸条件下本文方法在两个数据集下的图像分类正确率，如图3所示。其中，直方图的方向数量设为8。

由图3可见，当单元格尺寸为4×4、块尺寸为2×2时，两个数据集下图像的分类正确率都是最高的。因此，本文设置单元格尺寸为4×4，块尺寸为2×2，直方图方向数量为8。如1.1节所述，多尺度图像块的尺寸都归一化为32×32，因此，在本文的HOG特征参数设置的条件下，每一个图像子块提取的HOG特征向量的维数为（32/8×32/8×2×2×8=512）。

2.4 性能对比

本文采用以上参数匹配进行图像分类实验，并与文献[6]、[7]、[9]所述的图像分类方法进行对比，在COIL-100和PVOC 2007两个数据集下对比测试图像分类性能。其中，图像分类正确率指标的对比结果如图4所示，平均分类耗时的对比结果如表1所示。

由图4可见，本文方法在COIL-100和PVOC 2007两个数据集下的分类正确率指标都高于其他3种方法，尤其是在PVOC 2007数据集下的分类正确率指标优势更明显。这是因为本文方法通过多尺度分块和融合编辑操作来适应同类目标在不同图像上位置、尺寸和视角的变化，对于PVOC 2007数据集中具有不同尺度、视角和光照变化的目标的鲁棒性更好。

由表1可见，本文方法的平均分类耗时是4种方法中最小的，且远小于文献[7]和[9]所述方法。这是因为本文方法的HOG特征提取和改进的编辑距离计算耗时远低于文献[7]的多模式深度学习和文献[9]的潜在语义分析过程。

3 结束语

本文提出了一种结合图像的多尺度字符串表示以及改进的编辑距离和SVM的图像分类方法，主要思想是：提取图像多个尺度的归一化图像子块的HOG特征，采用多个字符串描述图像；针对图像分类需求，提出一种融合编辑操作，并对传统的字符串编辑距离进行改进，将改进的编辑距离作用于径向基函数，采用改进的SVM实现图像分类。在公开测试数据集COIL-100和PVOC 2007上进行图像分类实验，结果表明本文方法的分类正确率高，而且平均分类耗时少。

参考文献

[1] SUDHAKARAN S，JAMES A P.Sparse distributed localized gradient fused features of objects[J].Pattern Recognition，2015，48(4)：1538-1546.

[2] HUANG M，MU Z，ZENG H.Efficient image classification via sparse coding spatial pyramid matching representation of SIFT-WCS-LTP feature[J].Iet Image Processing，2016，10(1)：61-67.

[3] 吕启，窦勇，牛新，等.基于DBN模型的遥感图像分类[J].计算机研究与发展，2014，51(9)：1911-1918.

[4] CHEN J，LI Q，PENG Q，et al.CSIFT based locality-constrained linear coding for image classification[J].Pattern Analysis and Applications，2015，18(2)：441-450.

[5] CHAN T H，JIA K，GAO S，et al.PCANet：A simple deep learning baseline for image classification[J].IEEE Transactions on Image Processing，2014，24(12)：5017-5032.

[6] MANIVANNAN K，AGGARWAL P，DEVABHAKTUNI V，et al.Particulate matter characterization by gray level co-occurrence matrix based support vector machines[J].Journal of Hazardous Materials，2012，223-224(2)：94-103.

[7] 石祥滨，房雪键，张德园，等.基于深度学习混合模型迁移学习的图像分类[J].系统仿真学报，2016，28(1)：167-173.

[8] CINBIS R G，VERBEEK J，SCHMID C.Approximate Fisher kernels of non-iid image models for image categorization[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2015，38(6)：1084-1098.

[9] 赵仲秋，季海峰，高隽，等.基于稀疏编码多尺度空间潜在语义分析的图像分类[J].计算机学报，2014，37(6)：1251-1260.

[10] MOHAMED B，ISSAM A，MOHAMED A，et al.ECG image classification in real time based on the Haar-like features and artificial neural networks[J].Procedia Computer Science，2015，73(5183)：32-39.

[11] NANNI L，LUMINI A，BRAHNAM S.Survey on LBP based texture descriptors for image classification[J].Expert Systems with Applications，2012，39(3)：3634-3641.

[12] BANERJI S，SINHA A，LIU C.HaarHOG：Improving the HOG descriptor for image classification[C].IEEE International Conference on Systems，Man，and Cybernetics.IEEE Computer Society，2013：4276-4281.

[13] MEDNIS M，AURICH M K.Application of string similarity ratio and edit distance in automatic metabolite recon ciliation comparing reconstructions and models[J].Biosystems & Information Technology，2012，1(1)：14-18.

作者信息：

魏艳鸣1，田建立2，郭荣幸3

(1.河南经贸职业学院 计算机工程学院，河南 郑州450018；2.黄河科技学院 信息工程学院，河南 郑州450019；

3.郑州航空工业管理学院 电子通信工程学院，河南 郑州450018）