基于互补特征和类描述的商品图像分类方法

摘要

本发明公开了一种基于互补特征和类描述的商品图像分类方法，包括以下步骤。步骤一取分好类的图像作为训练样本；步骤二使用图片批量编辑工具将所有的标记图像类和测试图片进行分辨率压缩；步骤三提取各标记图像类中图片的塔式梯度方向直方图和塔式关键词直方图互补特征，步骤四提取待分类商品图像的塔式梯度方向直方图和塔式关键词直方图特征；步骤五构造各标记图像类的类描述符；步骤六将以上获得的特征向量使用最近邻分类算法进行分类，通过计算待分类商品图像与各标记图像类类描述符之间的距离，将距离最小的图像类作为分类结果。本发明能充分利用两种互补特征，并使用基于图像-类距离的改进最近邻分类算法，使得分类结果更加精确。

说明书

技术领域

本发明涉及的是一种商品图像自动分类的方法，具体是一种基于互补特征和改进的图像-类的距离算法的商品图像自动分类算法。

背景技术

随互联网的普及和发展，电子商务逐渐进入了一个全新的时代，电子商务网站的数量急剧增长，出现了一批国内外知名的电子商务网站，如Amazon、ebay、淘宝等。电子商务网站需要通过对在线销售商品进行标注以方便用户进行搜索。目前情况下，这些标注仅仅说明商品的基本信息(元信息)，如商品的名称、产地、尺寸、价格等，难以反映商品的完整特征。如：女士皮鞋是圆头还是尖头，T恤衫是圆领口还是V型领口，休闲鞋鞋带是尼龙搭扣型还是细鞋带型等；这些特征都是用户可能感兴趣的潜在信息，但因为缺少进一步的标注，用户只能通过浏览商品图片才能获得这些信息。如果在网站中设置图片分类过滤器，无疑能方便用户进行浏览。如果通过人工完成这些潜在兴趣信息的标注，对于在商品数量和品种规模都很大的电子商务网站来说，无疑是非常费时费力的。

基于内容的图像分类(content-based image classification)是根据图像的视觉特征对图像进行语义分类。近几年图像分类研究的焦点是自然图像的场景分类(scene classification)和物体分类(object classification)，主要采用有监督学习方法，通过对底层特征建模和中间语义分析来实现分类。目前研究文献中常用的测试图像数据库Caltech 101和Caltech 256已经达到101类和256类。与这些库中的自然图像不同，电子商务网站上提供的商品图像一般是比较理想的图片，具有较少背景干扰，目标比较单一；这些特点使基于内容的商品图像分类更容易获得理想的分类正确率，为一种新型商品分类方法提供了可能。

发明内容

本发明针对以上问题的提出，而研制一种基于互补特征和类描述的商品图像分类方法。本发明采用的技术方案如下：

一种基于互补特征和类描述的商品图像分类方法，其特征在于互补特征的提取及改进的图像-类的距离计算方法，具体描述如下步骤：

步骤一、取已分好类的图像作为训练样本；

步骤二、提取各标记图像类中图片的塔式梯度方向直方图和塔式关键词直方图互补特征，其中塔式级数为L(L＝0，1...n)；

步骤三、提取待分类商品图像的塔式梯度方向直方图和塔式关键词直方图特征，其中塔式级数为L(L＝0，1...n)；

步骤四、然后计算各图像类的类描述符，即代表各图像类的塔式梯度方向直方图和塔式关键词直方图特征，其中塔式级数为L；

图像类的类描述符利用下公式求得：

图像类的类特征描述符为{HGC^(l)，HWC^(l)，}l＝0，1，...，L-1

${\mathrm{HGC}}^{\left(l\right)}={\mathrm{HGC}}_j^{\left(l\right)}|\underset{j}{\min }d({\mathrm{HGC}}_j^{\left(l\right)},{\mathrm{HGq}}^{\left(l\right)})$

${\mathrm{HWC}}^{\left(l\right)}={\mathrm{HWC}}_j^{\left(l\right)}|\underset{j}{\min }d({\mathrm{HWC}}_j^{\left(l\right)},{\mathrm{HWq}}^{\left(l\right)})$

l＝0，1，...，L-1，j＝0，1...，N_C

其中：HGq^(l)，HWq^(l)分别表示待分类商品图像的第i级(i＝0，1，...，L-1)塔式梯度直方图和塔式关键词直方图，分别表示图像类中第j幅图像的第i级(l＝0，1，...，L-1)塔式梯度直方图和塔式关键词直方图；另外，L为塔式分解级数，N_C为该图像类中含有的图片的总数。

步骤五、计算待分类商品图像与类描述符之间的距离，即分别计算待分类商品图像与每个图像类之间的塔式梯度方向直方图距离和塔式关键词直方图距离，采用chi-square距离计算方法，将计算出来的两种距离进行线性加权，将线性加权距离最小的图像类作为分类结果。

在步骤二和步骤四之前还包括使用图片批量编辑工具将所有的标记图像类和待分类商品图像的分辨率进行压缩的步骤，其中标记图像类和待分类商品图像压缩的分辨率相同。

步骤五中的线性加权系数通过交叉验证方式获得。

由于采用了上述技术方案，本发明提供的基于互补特征和类描述的商品图像分类方法同现有技术相比其优点是显而易见的；首先，在图像特征提取和描述方面，采用稠密采样方式，形成了两种具有互补特性的多级塔式结构特征：塔式梯度方向直方图和塔式关键词直方图，并通过线性特征融合获得最终的特征表达。这种特征描述既考虑到了图像的形状特征，又考虑到了图像的局部分布信息，通过图像空间多分辨率分解构成的塔式结构和特征加权融合能够更完整、灵活地描述图像特征信息，从而提高图像分类性能。(2)在分类器设计方面，提出了基于图像类特征描述的改进最近邻分类算法，通过计算图像到类(而不是图像到图像)的距离来实现商品图像分类。

附图说明

图1为本发明所述分类方法的流程图；

图2为本发明实施例中商品图库示意图；

图3为本发明实施例中CSAA最高分类正确率表；

图4为本发明实施例中不同标记样本下的分类正确率图；

图5为本发明实施例中不同标记样本下的平均分类测试时间。

具体实施方式

如1所示该基于互补特征和类描述的商品图像分类方法，具体描述如下步骤：

步骤一、取已分好类的图像作为训练样本；

步骤二、提取各标记图像类中图片的塔式梯度方向直方图和塔式关键词直方图互补特征，其中塔式级数为L(L＝0，1...n即为自然数)；

步骤三、提取待分类商品图像的塔式梯度方向直方图和塔式关键词直方图特征，其中塔式级数为L(L＝0，1...n即为自然数)；

步骤四、然后计算各图像类的类描述符，即代表各图像类的塔式梯度方向直方图和塔式关键词直方图特征；其中塔式级数为L；

步骤五、计算待分类商品图像与类描述符之间的距离，即分别计算待分类商品图像与每个图像类之间的塔式梯度方向直方图距离和塔式关键词直方图距离，采用chi-square距离计算方法，将计算出来的两种距离进行线性加权，将线性加权距离最小的图像类作为分类结果。

步骤五中的计算距离具体为：计算分别计算塔级为0，1...L-1时待分类商品图像梯度方向直方图与各图像类中各幅图片梯度方向直方图的chi-square距离，将对应距离最小的图片梯度方向直方图作为该图像类的相应塔级的梯度方向直方图。分别计算塔级为0，1...L-1时待分类商品图像关键词直方图与各图像类中各幅图片关键词直方图的chi-square距离，将对应距离最小的图像关键词直方图作为该图像类的相应塔级的图像关键词直方图。

为了减少处理时间，在步骤二和步骤四之前还包括使用图片批量编辑工具将所有的标记图像类和待分类商品图像的分辨率进行压缩的步骤，其中标记图像类和待分类商品图像压缩的分辨率相同(本实施例以分辨率100×100为例)。

另外，步骤五中的线性加权系数通过交叉验证方式获得。

具体计算过程如下：

所述塔式梯度方向直方图建立方式如下(以L＝3为例)：如：

(1)将图像像素的梯度方向划分为K个区间，每个区间的大小是360/K；

(2)计算整个图像的梯度，形成对应的用梯度幅值加权的梯度方向直方图H0；

(3)将图像进行空间四叉树分解，即将图像划分为为同样大小(或近似大小)的4个矩形单元，分别计算每个矩形单元的梯度幅值加权的梯度方向直方图，从左向右，从上到下依次联结4个单元梯度方向直方图，形成梯度方向直方图H1；

(4)将图像进行二级四叉树分解，即将图像划分为16个同样大小(或近似大小)的矩形单元，分别计算每个单元的梯度幅值加权的梯度方向直方图，从左向右，从上到下依次联结16个单元梯度方向直方图，形成梯度方向直方图H2；

(5)依次联结H0，H1，H2，用整个直方图“能量”(L2范数)对特征向量进行归一化处理，形成图像的塔式梯度方向直方图H。

例如：若梯度方向量化区间数K设为20，塔式梯度方向直方图由3个梯度方向直方图特征向量顺序联结而成。塔级1＝0时不进行空间划分，将整个图像作为1个单元计算梯度方向直方图，其维数为20；塔级1＝1时将图像进行四叉树划分，将图像划分为4个矩形单元计算梯度方向直方图，其维数为20×4＝80；塔级1＝2时将图像分解为16个矩形单元计算梯度方向直方图，其维数为20×16＝320，最终形成的直方图是1＝0，1，2各梯度方向直方图的顺序组合，其维数为20+80+320＝420。对直方图进行归一化处理，可以进一步去除光照变化的影响。

所述塔式关键词直方图建立方式如下(以L＝3为例)：

(1)采用稠密采样(dense sample)方式，采样间隔设为8个像素，每个16×16的像素块使用sift描述符形成128维的特征向量。

(2)将所有训练图像的图像描述符进行K均值量化后形成若干聚类中心，即视觉关键词，取K＝500，则共有500个视觉关键词，即词包大小为500；

(3)依次计算待分类商品图像各sift描述符到各聚类中心的欧氏距离，对应欧式距离最小的聚类中心即此sift描述符对应的视觉关键词；统计待分类商品图像中视觉关键词的出现频数，形成视觉关键词直方图H0；

(4)将图像进行空间四叉树分解，即将图像划分为4个大小相同(或近似大小)的矩形单元，分别计算每个单元的视觉关键词直方图，从左向右，从上到下依次联结4个单元视觉关键词直方图，形成一级视觉关键词直方图H1；

(5)将图像进行二级四叉树分解，即将图像划分为16个大小相同的矩形单元，分别计算每个单元的视觉关键词直方图，从左向右，从上到下依次联结16个单元视觉关键词直方图，形成二级视觉关键词直方图H2；

(6)联结H0，H1，H2，在特征空间形成从低分辨率到高分辨率表示的一系列视觉关键词直方图表示。用整个直方图“能量”(L2范数)对特征向量进行归一化处理，形成图像的塔式视觉关键词直方图H。

设定词包大小K＝500，则最终形成的塔式关键词直方图：500+500×4+500×16＝82500。

所述图像直方图之间的chi-square距离计算方法如下：

图像直方图之间距离的计算采用chi-square距离法，chi-square距离法计算公式如下：

$d(s1,s2)=1-\exp (-{\chi }^2(s1,s2)),{\chi }^2(s1,s2)=\underset{j}{\Sigma }\frac{{\left(s_1\right[j]-s_2[j\left]\right)}^2}{s_1\left[j\right]+s_2\left[j\right]}$

其中，d(s1，s2)表示两个直方图s1与s2之间的chi-square距离。s₁[j]，s₁[j]分别表示两个直方图s1与s2第j个元素的取值。

所述类描述符构造方法如下：

设HGq^(l)，HWq^(l)分别表示待分类商品图像q的第i级(i＝0，1，...，L-1)塔式梯度直方图和塔式关键词直方图，分别表示图像类C中第j幅图像的第i级(l＝0，1，...，L-1)塔式梯度直方图和塔式关键词直方图，则图像类C的类特征描述符{HGC^(l)，HWC^(l)，}l＝0，1，...，L-1应满足以下条件：

${\mathrm{HGC}}^{\left(l\right)}={\mathrm{HGC}}_j^{\left(l\right)}|\underset{j}{\min }d({\mathrm{HGC}}_j^{\left(l\right)},{\mathrm{HGq}}^{\left(l\right)})$

${\mathrm{HWC}}^{\left(l\right)}={\mathrm{HWC}}_j^{\left(l\right)}|\underset{j}{\min }d({\mathrm{HWC}}_j^{\left(l\right)},{\mathrm{HWq}}^{\left(l\right)})$

l＝0，1，...，L-1，j＝0，1...，N_C

其中，L为塔式分解级数，N_C为图像类C中含有的图片的总数

所述待分类商品图像与类描述符之间的距离计算方法如下：

(1)不同分辨率的直方图对分类性能有不同的影响，所以计算直方图距离时应该设置不同的权重系数。一般说来，相对于低分辨率直方图，高分辨率直方图对分类性能的影响更大一些。将塔式关键词直方图和塔式梯度直方图第l级的权重设为(l＝0，1，...，L-1，L是塔式分解级数，本发明取L＝3)：

$d(\mathrm{HGC},\mathrm{HGq})=\underset{l=0}{\overset{L-1}{\Sigma }}\frac{1}{2^{L-1}}d({\mathrm{HGC}}_j^{\left(l\right)},{\mathrm{HGq}}^{\left(l\right)})$

$d(\mathrm{HWC},\mathrm{HWq})=\underset{l=0}{\overset{L-1}{\Sigma }}\frac{1}{2^{L-1}}d({\mathrm{HWC}}_j^{\left(l\right)},{\mathrm{HWq}}^{\left(l\right)})$

(2)待分类商品图像与类描述符之间的距离计算方法如下：

d(HC，Hq)＝α·d(HGC，HGq)+(1-α)d(HWC，HWq)

其中d(HGC，HGq)和d(HWC，HWq)分别表示以塔式梯度方向直方图特征和塔式关键词直方图特征计算的待分类商品图像q与图像类C之间的距离，d(HC，Hq)表示进行特征融合后待分类商品图像q与图像类C之间的距离。线性加权系数α的取值通过五重交叉验证的方法来确定。通过α的选择，获得最具区分能力的特征表示。

所述线性加权系数α的获取方法如下：

(1)将α初值设为0；

(2)采用五重交叉验证方法求得平均分类正确率；

(3)α＝α+0.01

(4)如果α＜＝1，返回(2)，

如果α＞1，将平均分类分类正确率最高的α作为最终的线性加权系数，结束.

所述五重交叉验证方法如下：

(1)将所有标记图像分成5份；

(2)轮流将其中4份做训练1份做测试，记录分类正确率；

(3)记录5次分类结果正确率的均值作为对算法平均分类正确率的估计。

所述最近邻分类算法如下所示：

最终的分类结果由式

$\hat{C}=\underset{C}{\min d}(\mathrm{HC},\mathrm{Hq})$确定

d(HC，Hq)表示进行特征融合后待分类商品图像q与图像类C之间的距离。

本发明能充分利用两种互补特征，并使用基于图像-类距离的改进最近邻分类算法，使得分类结果更加精确。

下面结合附图对本发明的实施例作详细说明：本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

本实施例中采用的图像数据库为Tomasik B，Thiha P and Tumbull D在“Tagging products using image classification”(32nd international ACM SIGIR)使用的的5类图像库(http://www.sccs.swarthmore.edu/users/09/btomasil/tagging-products.html)。这些图像全部是从eBay和Amazon.com网站下载的商品图像，分辨率在280×280左右，示例图2所示。本文实验在配置了Intel Pentium CPU 2.66GHz，1GBRAM，运行Windows XP操作系统和MATLAB7.1软件的计算机上进行。

如图1所示，本实例包含以下步骤：

步骤一.在给定图库中随机选择5、25、50、75幅图像作为训练样本，组成若干标记图像类。另外的图像作为待分类商品图像。

步骤二.使用图片批量编辑工具(如Batch Image Resizer 2.88)将所有的标记图像类和测试库的图片的分辨率压缩为为100×100。

步骤三.提取各标记图像类中图片的塔式梯度方向直方图(K＝80，L＝3)和塔式关键词直方图特征(K＝500，L＝3)。

步骤四，提取待分类商品图像的塔式梯度方向直方图(K＝80，L＝3)和塔式关键词直方图特征(K＝500，L＝3)。

步骤五.计算各图像类的类描述符，即代表各图像类的塔式梯度方向直方图和塔式关键词直方图特征。

步骤六，将以上获得的特征向量使用最近邻分类算法进行分类，通过计算待分类商品图像与类描述符之间的距离，得到待分类商品图像与每个图像类之间的塔式梯度方向直方图和塔式关键词直方图描述符之间的卡方距离，将线性加权距离最小的图像类作为分类结果。线性加权系数通过交叉验证方式获得。

评价分类性能最主要的指标是分类正确率和分类速度。

由于图像测试库中每类图像数目可能有较大的差异，使用总体分类正确率(Overall Accuracy，OA)的计算方法(正确分类图像数占全部图像数的比率)会导致图像数目较少的类别占用的权重较小；所以采用类大小调整正确率(Class-Size-Adjusted Accuracy，CSAA)的计算方法，如下式所示：

$\mathrm{CSAA}=\frac{1}{C}\underset{i=1}{\overset{C}{\Sigma }}\frac{P_i}{N_i}$

其中，C表示图像类别数，P_i表示第i类正确的分类数，N_i表示第i类图像的总数。如在短袖上衣与长袖上衣的分类中，假设100幅长袖上衣有90幅分类正确，而50幅短袖上衣中有30幅分类正确，则总体分类正确率OA＝(90+30)/(100+50)＝80％；而类大小调整分类正确率CSAA＝1/2×(90/100+30/50)＝75％。

分类速度采用平均分类测试时间去描述分类速度。

测试结果如图3、图4和图5所示，从以上测试结果中可以看出：

(1)不同分类任务分类正确率存在较大的差异。如长袖与短袖的分类，在训练样本数为5时就已经达到90％，增加训练样本数分类正确率逐渐接近99％；而尼龙搭扣与鞋带的分类正确率最高不过70％。

(2)从总体上看，基于塔式关键词直方图的分类正确率高于基于塔式梯度直方图的分类正确率。而两者特征融合的的分类正确率又有了1～3个百分点的提高。

(3)相对于Tomasik B等提出的方法，基于两种特征融合的分类正确率都有一定程度的提高。基于尤其是圆领、V型领与套衫的3分类和尼龙搭扣与鞋带的2分类最高分类正确率分别由66％，67％提高到70％和74％。其原因是(a)本发明采用了互补性更有区分力的图像特征，(b)本发明设计了更合理的基于图像类描述的最近邻分类器，通过计算图像到类的距离获得更好的推广性能。

(4)从分类速度上看，随着标记样本数的提高，平均分类测试时间有接近线性的较缓慢的增长，说明测试时间主要取决于待分类商品图像的特征提取过程，类描述符的提取及匹配时间影响较小。当每类标记数达到75时，基于塔式梯度直方图、塔式关键词直方图、两种特征融合的平均分类测试时间分别为0.2s，0.56s和0.76s，都能够达到实时性的要求，其中基于塔式梯度直方图的方法在分类速度上有明显的优势。

本文使用互补的图像特征及基于类描述的改进最近邻分类算法实现了2～3类商品图像的自动分类，正确率达到70％-99％，并且能达到实时性的要求；

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。