基于多种聚类的无监督距离融合学习算法研究

侯守明 林晓洁 胡明凯

摘  要：本文针对传统的形状匹配算法的处理计算量过大、消耗时间过长，从而导致无法应用于大量的图像集以及在线的形状匹配场景的问题，在学者提出的距离融合算法的基础上进行了改进，在处理阶段引入无监督学习的方法进行多种聚类。通过引入预处理算法对图像集进行特征提取以及划分，在算法的计算量上做出优化，大幅降低了算法的计算时耗，并且保证其正确率几乎没有降低。

关键词：无监督;形状匹配;多重聚类;距离融合

中图分类号：TP391;TP751.1      文献标识码：A 文章编号：2096-4706（2019）05-0070-04

Abstract：The problem of traditional shape matching algorithm is too large and the consumption time is too long，which can not be applied to a large number of image sets and online shape matching scenes. It is improved on the basis of the distance fusion algorithm proposed by scholars. Introduce unsupervised learning methods in the processing stage to perform multiple clustering. The feature extraction and division of the image set are introduced by introducing the preprocessing algorithm，and the calculation of the algorithm is optimized，which greatly reduces the computational time consumption of the algorithm and ensures that the correct rate is almost not reduced.

Keywords：unsupervised;shape matching;multiple clustering;distance fusion

0  引  言

随着互联网的迅猛发展以及图像资源的日益丰富，形状匹配已经成为计算机视觉领域的一个热门研究方向。如何能够准确、快速地对已有形状进行同类的辨识匹配，找出同类图像以及确定图片中形状所属类别，学者们已经在这一领域提出很多很有效用的算法。

利用形状本身的特征、颜色差异以及图像的纹理特征進行形状区分是形状匹配算法的主要方法，通过不同的特征提取方法得到各形状之间的相似度或者相似距离。例如匡纲要等[1]提出的基于图像纹理特征的提取方法，重点关注纹理特征的分类与分割，并对一般的纹理特征提取方法进行了总结。Zhao等[2]提出的基于颜色空间分布特征的图像检索方法利用颜色之间的对比度的多尺度邻域形成的加权颜色直方图来检索图像。进一步地，Micha?等[3]研究了基于颜色和关键点的特征提取算法在分布式上的应用，将计算任务分发到多个节点，从而提高了算法整体的算力和图像集的容量。Zhu X等[4]利用支持向量机对基于骨架的形状匹配算法进行了研究，使得算法在有噪音的情况下也能展示出良好的性能，同时与图形的旋转缩放平移无关。张桂梅等[5]研究了基于内距离形状上下文特征的形状匹配。

本文基于白翔等[6，7]提出的距离融合协同传导算法，在处理阶段引入无监督学习的方法进行聚类。在算法的计算量上做出优化，大幅降低了算法的计算时间，并且正确率几乎没有降低。

1  距离融合算法介绍

Bai X等提出的距离融合算法基于他们提出的图传导算法。在图传导算法中，他们提出使用图形的转换学习算法来解决传统形状特征匹配算法不能够有效正确地识别有效差异与无效差异的问题，该算法的特点是不专注于计算孤立的每一对形状之间的相似性距离，而是利用现有较多的形状形成的流模型，通过算法中提出的概率转移矩阵。如存在这样一个匹配的场景，利用内距离形状匹配算法计算相似性距离，在计算一个站立的人（记为A）与蹲着的人（记为B）以及站立的猴子（记为C）之间的相似性距离时，我们能够得出这样一个结果，即SAB

图传导算法在很大程度上提高了形状匹配的准确度，但是也存在一定的缺陷，因为图传导算法是在选定的某一种形状匹配算法上进行流模型的计算，进而找出最短路径，所以算法有着事先的潜力限制，还是只关注于某一种特征。基于此，Bai X等又在图传导算法的基础上进行了改进，提出了协同传导算法。

该算法克服了上面提到的单一图传导算法只能关注某一类形状特征的局限，通过利用两种甚至多种特征提取算法计算出的特征矩阵进行协同传导，在迭代过程中利用多种特征提取得到的距离矩阵通过概率转移矩阵进行距离融合传递，关注形状多个方面的特征，从而提高形状匹配的正确率。

2  基于多种聚类的算法改进

Bai X等人提出算法，应用LP算法来学习一个新的相似度函数simT，这种方法大大提高了对查询形状x1的查询准确度，但是该算法需要计算任意两个样本之间的相似度，并且不断迭代。当已知样本集很大时，计算查询样本与所有形状的相似度由于耗时问题变得不切实际，而且无法用于在线的图像匹配应用中。

为了算法在大的样本集上同样有着较快的运行速度，本文采用启发式方式，从两个思路入手，第一，对样本集做预处理，以便对查询对象在样本集中做匹配时不需要对数据库中所有图像计算相似度;第二，采用自适应的方式筛选最相似样本，减少需要匹配的样本的数量。

因此算法分为两个步骤：第一步，预处理步骤，对样本集所有样本进行聚类，输出聚类簇和划分查询样本x0的方法;第二步，协同传导步骤，对于查询样本x0，只需要根据聚类模型，将x0分类到聚类形成的簇类别中，x0所属簇类别的所有样本作为查询样本候选匹配样本，然后在候选匹配样本上采用协同传导算法计算最相似样本。

在这种方式下，当查询样本x0落入某两个簇类别的边界，x0的最相似样本可能存在于这两个类别中，而且单一聚类标准的算法鲁棒性并不高，因此，本文选择多种聚类算法，x0在所有聚类算法中落入类别的样本都作为候选匹配样本，然后在这些样本上采用协同传导算法计算最相似样本。

2.1  K均值聚类算法

2.3  AGNES聚类算法

AGNES是一种“自底向上”的层次聚类算法，算法首先将样本集中每一个样本当做一个初始聚类簇，然后开始进行算法迭代，算法的每一次迭代找出两个最相似的聚类簇进行合并，直到达到预设的聚类簇个数。

传统AGNES算法通过度量两个簇之间的距离来进行簇合并，簇Сi与Сj间的距离度量通常有以下三种方式：最小距离、最大距离和平均距离。

聚类结束后，算法输出样本集的簇划分C={C1，C2， …，Ck}。对于查询样本x0，该算法无法确定x0所属的簇。因此，我们在该算法的基础上做一些改进，以便能够确定查询样本x0所属的簇。参考K均值算法确定查询样本所属聚类簇的方式，将每个簇计算一个簇均值，查询样本x0所属的类别就是与对应相似度最高的簇均值对应得到簇，即λ=argmaxi∈{1，2，…，k}sim（x1，μi）。

2.4  预处理算法

基于以上三个聚类算法，我们可以对样本集进行预处理。K均值算法和AGNES使用了sim函数来计算相似度，它应该与协同传导步骤中的sim函数保持一致，协同传导步骤中，将使用两个相似度函数，即sim1和sim2。高斯混合聚类算法没有使用sim函数，而是假设了样本服从高斯分布，因此不存在保持一致的问题，所以预处理算法输出五个聚类簇划分С，和五個划分查询样本到对应分类簇的方法?（x），调用该函数得到给定样本所属的簇标记。预处理算法如图1所示。

2.5  协同传导步骤

2.4节对样本集做出了预处理，每种聚类算法都给出了簇划分和划分查询样本x0的方式。因此，对于查询样本x0，我们可以基于预处理步骤给出的结果快速得到候选匹配样本集，然后在候选匹配样本中采用协同传导算法计算最相似样本。由于预处理步骤大大缩小了候选匹配样本范围，因此协同传导步骤的计算量大大降低。

输入：簇划分С

簇划分方法?（x）

相似度函数sim1，sim2

查询样本x0

过程：

1  初始化候选样本集Dh=?

2  簇划分和簇划分方法个数n=5

3  for j=1，2，…，n do

4  找出查询样本所属类别λ=f j（x0）

5  将该类中的样本划入候选样本集

6  end for

7  使用sim1在样本集Dh上计算每个样本与x0的相似度，基于相似度对样本集排序得到S1，并基于S1计算概率转移矩阵P1

8  使用sim2在样本集Dh上计算每个样本与x0的相似度，基于相似度对样本集排序得到S2，并基于S2计算概率转移矩阵P2

9  令Y1=Y2{x0}，X1=X2=Dh

10  repeat

11  使用P1基于图传导算法学习出相似度

12  使用P2基于图传导算法学习出相似度（j=1，…，m是迭代次数的索引）

13  （N1表示X1前p个最相似样本）

14  （N2表示X2前p个最相似样本）

15  X1=X1-Y1，X2=X2-Y2

16  until达到最大迭代次数

17  取N1和N2中相似度最高的前p个样本作为结果R

输出：匹配结果R

对于给定的查询样本，该步骤需要基于预处理步骤的结果，计算出候选样本集Dh，然后再候选样本集上应用协同传导算法，计算出最匹配的样本。算法伪代码如图2所示，其中涉及到的图传导算法已经在背景介绍部分进行了说明。

3  实验结果与分析

实验的图像数据集采用MPEG-7形状数据集，图像形状如图3所示，MPEG-7形状数据集由70个类别，共1400个剪影图像组成，每个类都有20种不同的形状。

对算法运行时间和算法正确率两方面进行实验验证，我们对比本文算法与Bai X提出的协同传导算法，本文算法在聚类方法上可以选择一种、两种或三种，并对这些情况都做了实验验证。

算法运行时间的对比。我们将Bai X的协同传导算法的运行时间定为1，比较我们的算法运行时间和Bai X算法的运行时间，对比了采用一种聚类算法、采用两种聚类算法和三种聚类算法的运行时间，运行时间对比分析如表1所示。从表1中可以看出，算法能夠大幅降低计算时间。

算法的正确率对比。本文算法与协同传导算法采用相同的相似度函数，对比采用不同种类聚类算法时，该算法与协同传导算法的正确率比较，匹配准确度对比分析如表2所示。本文算法的正确率随着聚类算法的增多而接近协同传导算法，从一种聚类算法的95%左右的正确率上升到三种聚类算法时的97.59%，而协同传导算法为97.63%，这意味着只有个别的最相似样本没有被划入候选匹配样本中。

综合以上实验结果可以得出结论，该改进算法能够大幅降低计算时间，使算法能够运行到在线匹配场景下，同时匹配正确度上与协同传导算法几乎相同。

参考文献：

[1] 刘丽，匡纲要.图像纹理特征提取方法综述 [J].中国图象图形学报，2009，14（4）： 622-635.

[2] Zhao Q，Cao J，Hu Y.Image Retrieval Based on Color-Spatial Distributing Feature [J].Journal of Southern Yangtze University，2007，346：79-86.

[3] Micha? ??giewka，Korytkowski M，Scherer R. Distributed image retrieval with color and keypoint features [C]// IEEE International Conference on Innovations in Intelligent Systems & Applications. IEEE，2017.

[4] Zhu X. Shape Recognition Based on Skeleton and Support Vector Machines [C]// International Conference on Intelligent Computing. Springer，Berlin，Heidelberg，2007.

[5] 张桂梅，蔡报丰.基于内距离形状上下文特征的形状匹配研究 [J].南昌航空大学学报（自然科学版），2016，30（2）：1-7.

[6] BAI X，YANG X，LATECKI LJ，et al. Learning context-sensitive shape similarity by graph transduction [J].IEEE transactions on pattern analysis and machine intelligence，2010，32（5）：861-74.

[7] BAI X，WANG B，YAO C，et al. Co-transduction for shape retrieval [J].IEEE Transactions on Image Processing，2012，21（5）：2747-2757.

作者简介：侯守明（1972-），男，汉族，河南博爱人，教授，硕士生导师，博士，研究方向：图形图像处理、虚拟现实与增强现实;通讯作者：林晓洁（1990-），女，汉族，河南濮阳人，硕士研究生，研究方向：系统软件、图像处理;胡明凯（1991-），男，汉族，广东深圳人，硕士，研究方向：数字化工程与仿真。