高清彩色图像分割的Mini-batch FCM算法研究

倪翠 李千 玄甲辉

摘  要：模糊C-均值（Fuzzy C-Means，FCM）聚类算法是一种基于划分的无监督聚类算法，也是较为常见的图像分割算法之一，该算法通过寻找0～1之间的模糊隶属度等级来进行图像分割，并通过在特征空间中寻找聚类中心来达到最小化目标函数的目的。它的局限性主要有实时性较差、初始聚类中心的设置对最终结果影响较大、未考虑空间因素导致抗噪性弱。本文将mini-batch方法应用到FCM算法中，加快了FCM算法的收敛速度，提高了算法的效率及时效性，一定程度上解决了当数据特征复杂、集合较大时，FCM算法的实时性不是很理想的问题，继而节省算法运行的时间。

关键词：FCM聚类;mini-batch;图像分割

中图分类号：TP391.41      文献标识码：A 文章编号：2096-4706（2019）19-0015-03

Abstract：Fuzzy C-Means （FCM） clustering algorithm is an unsupervised clustering algorithm based on partition. It is also one of the common image segmentation algorithms. This algorithm conducts image segmentation by looking for the fuzzy membership grade between 0～1. The objective function is minimized by finding the clustering center in the feature space. Its limitations mainly include poor real-time performance，large impact on the final results due to the setting of the initial clustering center，and weak noise resistance due to the absence of space factors. In this paper，the mini-batch method is applied to the FCM algorithm to accelerate the convergence speed of the FCM algorithm，improve the efficiency and timeliness of the algorithm，and to some extent solve the problem that the real-time performance of the FCM algorithm is not ideal when the feature set of data is large，and then save the algorithm time.

Keywords：FCM clustering;mini-batch;image segmentation

1  FCM算法

1957年，Lloyd[1]首次提出了single-linkage層次聚类算法，经典FCM算法是MacQueen[2]1967年提出的，对FCM算法的详细分析和改进是由Dunn[3]和Bezdek[4]完成的。Bezdek等人对FCM进行了完善和推广后，将FCM应用在图像分割方面。并且证明了该算法的收敛性[5]。

FCM是一种将样本点进行分类的聚类算法，是K均值聚类算法的变体，也是最小化所有点到其聚类中心的距离之和，由于引进了介于0和1之间的隶属度变量，将组合优化问题变为连续变量优化问题。

FCM模型的目标函数定义为：

其中，U=（uik），1≤i≤C，1≤k≤m，为隶属度矩阵，uik为k个样本点属于第i类的隶属度，且，V=（vi），1≤i≤C，为样本的聚类中心，1

目标函数值越小，像素点与其所属聚类中心的隶属度值越大;反之，目标函数值越大，像素点与其所属聚类中心的隶属度值越小。目标函数式（1）的最小化是通过不断迭代更新隶属度值uik，然后通过隶属度值uik更新聚类中心vi来实现的。为了防止算法耗费过多的时间，FCM算法的终止准则为当上一步的目标函数和本次的目标函数值之间的差小于某一个值时，算法停止，或者，当算法的迭代步数达到了所给的最大迭代步数时，算法终止。在实际运用中，一般都是先达到第一种准则，即算法收敛。具体算法步骤如算法1（FCM算法）：

Step1 初始化：聚类类别数C，2≤C≤m，样本个数m。迭代停止阈值ε，初始化隶属度矩阵U，迭代计步器b=0;

Step2 用式（8）计算聚类中心vi，1≤i≤C;

Step3 用式（9）更新隶属度值uik，1≤i≤C，1≤k≤m;

Step4 返回Step2继续计算，b=b+1，直到收敛，输出U=（uik），V=（vi）。

2  mini-batch FCM方法

传统的FCM算法是用所有训练集更新隶属度值uik和聚类中心vik，这样大部分时间浪费在计算隶属矩阵U和聚类中心V时的矩阵之间的运算上。为了能够减少矩阵之间运算所消耗的时间。本文提出一种mini-batch FCM算法。mini-batch[6]通常和梯度下降法结合用来处理深度学习和机器学习中的大规模问题。mini-batch的思想是将训练集分组，分组之后，分别对每组进行计算，然后进行下一步迭代。假如将数据分为n组，则每次迭代将会做n次计算，这样减少了大规模矩阵之间的运算时间，同时提升了收敛速度。

mini-batch FCM算法的思想为：为了让每次计算的数据分布均匀，首先随机打乱数据，然后将打乱后的数据分组，用每一组数据去更新隶属度矩阵U和聚类中心V。这样减少了隶属矩阵U和聚类中心V在每次更新时所消耗的时间，同时使目标函数得到了充分的下降，提升了FCM的收敛速度。因此，mini-batch FCM算法比传统的FCM省时。具体算法步骤如算法2（mini-batch FCM）：

Step1 给定m个样本x1，…，xm，选取分组数n«m，一般有32、64、128等;

Step2 随机分组：将m样本随机分成n组，前n-1组有[m/n]（向上取整）个样本，第n组有m-[m/n]×（n-1）个样本;

Step3 计算：用每一组样本更新FCM算法中的隶属度矩阵U和聚类中心V;

Step4 返回Step2继续计算，直到收敛停止。

mini-batch FCM算法通过每次计算不同batch的样本，能够在一定程度上加速FCM算法收敛，使得达到相同精度，mini-batch FCM算法所用的时间更少，在相同的时间下，mini-batch FCM算法达到的精度更高。

3  mini-batch FCM实验结果

在实验中，取q=2，ε=10-8，C=2，mini-batch-size= 2048。图1中的图片采用高清彩色图片。其中Image 1图片的大小为473*1200*3。Image 2图片的大小为1607*1600*3，Image 3图片的大小为1600*1600*3，Image 4图片的大小为1027*1600*3。

从表1可以看出传统的FCM算法与mini-batch FCM算法相比，传统FCM算法在处理图像分割时所消耗的时间约是mini-batch FCM算法所消耗时间的2倍，尤其是处理尺寸大的高清彩色图像时，效果更显著。实验表明，mini-batch FCM算法效率比传统的FCM算法效率高。

4  结  论

在大数据时代，很多样本的规模都很大，但是，当数据的特征复杂、集合较大时，FCM算法的实时性不是很理想，于是，本文提出mini-batch FCM算法，在相同精度要求下，mini-batch FCM比FCM算法先收敛;在相同的时间下，mini-batch FCM的精度更高;因此，mini-batch FCM能够加快FCM算法的收敛，同时避免了大型矩阵之间运算的耗时。

参考文献：

[1] LLOYD S. Least squares quantization in PCM [J].IEEE Transactions on Information Theory，1982，28（2）：129-137.

[2] MACQUEEN J. Some methods for classification and analysis of multivariate observations [C]//Proc. of 5th Berkeley Symposium on Mathematical Statistics and Probability，USA：University of California Press，1967：281-297.

[3] DUNN J C. Well-Separated Clusters and Optimal Fuzzy Partitions [J].Journal of Cybernetics，2008，4（1）：95-104.

[4] BEZDEK J C. A convergence theorem for the fuzzy ISODATA clustering algorithm [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1980，2（1）：1-8.

[5] BEZDEK J C，EHRLICH R，FULL W. FCM：The fuzzy c-means clustering algorithm [J].Computers & Geosciences，1984，10（2-3）：191-203.

[6] DEKEL O，GILAD-BACHRACH R，SHAMIR O，et al. Optimal Distributed Online Prediction using Mini-Batches [J].2012，13：165-202.

作者簡介：倪翠（1992-），女，汉族，宁夏中卫人，助理工程师，硕士研究生，研究方向：机器学习中的优化方法;李千（1970-），男，汉族，江苏灌云人，副教授，硕士，研究方向：网络大数据分析、嵌入式系统应用;玄甲辉（1987-），男，汉族，山东泰安人，工程师，硕士研究生，研究方向：智能装备系统与电子信息系统。