基于Hadoop的改进聚类算法在图像修复上的应用

王 林，雷 佳，郝惠惠

(西安理工大学 自动化与信息工程学院，陕西 西安 710048)

基于Hadoop的改进聚类算法在图像修复上的应用

王 林，雷 佳，郝惠惠

(西安理工大学 自动化与信息工程学院，陕西 西安 710048)

针对模糊聚类算法在运算大数据量时性能差的问题，提出基于Hadoop分布式平台的改进算法进行图像修复。对于受损图像信息，首先将Canopy算法和模糊聚类相结合在Hadoop平台上进行并行化，然后进行字典训练获得修复图像。实验结果表明，该算法在均方误差和峰值信噪比上均优于改进前的图像修复算法，提高了图像修复质量并且减少了算法的运行时间，适合修复海量图像。

图像修复；聚类；Hadoop

Abstract: Aiming at the problem that the fuzzy clustering algorithm is poor in computing large data volume, an improved algorithm based on Hadoop distributed platform is proposed for image restoration. For the damaged image information, the Canopy algorithm and the fuzzy clustering are combined on the Hadoop platform for parallelization, and then the dictionary is trained to obtain the repaired image. The experimental results show that the algorithm is superior to the previous image restoration algorithm in terms of mean square error and peak signal to noise ratio, which improves the quality of image restoration and reduces the running time of the algorithm. It is suitable for repairing massive image.

Key words:image inpainting; clustering; Hadoop

0 引言

图像技术在各个方面都得到广泛应用[1]，但在图像获取过程中往往会造成图像信息丢失。利用受损图像信息恢复出原始图像信息，即图像复原技术。

2011年，SAHOO S K等人[2]利用局部图像块的稀疏近似来解决图像修复问题，提出了一个用于局部稀疏近似的自适应窗口选择步骤来影响底层图像全局恢复的框架，此框架提供了一个基于选择窗口大小的群集图像,接着利用稀疏近似算法分别修复每一个群集，从而达到理想的修复结果。此外，研究学者在文献[3-7]中都对图像修复算法进行改进，不同程度地提高了修复效果。但这些算法没有考虑到图像之间存在相似性，而且对于样本数据大的情况，没有提出有效地提高算法效率的解决方案。

针对以上缺陷，提出一种运行在Hadoop分布式平台上的改进聚类的字典学习算法。首先对图像数据集中的多类图像运用改进的模糊聚类算法(FCM)进行分类，同时在Hadoop分布式平台进行并行化计算，然后对每一类图像数据进行字典训练，得到每类图像的字典再指导图像修复。

1 理论基础

聚类是一种数据挖掘算法，基于信息之间的相似性对数据进行分类，与分类算法不同的是，聚类在算法开始之前并不知道要将数据分为几类。Canopy算法和FCM都是聚类算法，只是聚类方式不同。两个聚类算法各有优缺点，本文将两种算法结合，充分利用两个聚类的优势对图像信息进行聚类分析。

1.1 Canopy-FCM算法

Canopy-FCM算法的思路是利用Canopy算法产生聚类中心，从而弥补了 FCM聚类算法对初始聚类中心敏感的问题。Canopy-FCM算法的基本思路是：首先使用Canopy算法产生若干个初始聚类中心，然后再删除那些聚类中心中小于特定阈值的值；之后根据第一步已经产生的聚类中心，再进行模糊C均值聚类[7]。

因此可以先使用Canopy算法粗聚类，产生初始聚类中心，再使用FCM算法细聚类，从而提高算法效率，改善模糊C均值算法的不足。

1.2基于K-SVD字典训练的图像修复算法

基于K-SVD字典训练的图像修复算法主要是从受损图像中提取有用信息，然后选择初始字典D，使用K-SVD算法对分块后的图像进行训练，得到新的字典，并计算出稀疏系数，再更新对应的图像，如此便能修复受损图像。

具体步骤为：

(1)对图像进行稀疏编码。

(2)更新第k类图像字典Dk。

(3)重复执行步骤(1)和步骤(2)，直到满足迭代次数，字典Dk更新完成。

(4)选择对应的字典Dk(k∈1，…，I)作为基字典，进行K-SVD字典训练，计算稀疏系数，并利用更新的字典乘以稀疏系数，修复受损图像。

2 本文算法

考虑到图像之间的相似性，因此修复图像之前，首先对图像数据进行聚类，然后将已聚类的图像进行K-SVD字典训练。传统FCM对初始值敏感[8]，本文针对此问题进行了改进，应用Hadoop分布式平台并行化算法来提高聚类速率。

Canopy-FCM算法的并行化过程分为两个步骤：第一步是对Canopy算法进行Map-Reduce化；第二步是对FCM算法进行Map-Reduce化。

Canopy-FCM算法框架如图1所示。

图1 Canopy-FCM算法的Map-Reduce框架图

(1)对Canopy算法进行Map-Reduce化

Canopy算法的并行化分为map过程和reduce过程。Canopy算法的并行化首先将原始数据分为若干数据分片，并复制到执行任务的map节点上，而且所有的map节点独立完成分配的任务。map过程主要是使用Canopy算法思想对该节点的数据进行串行处理，然后获得形式的Canopy中心集合。

在串行化的Canopy过程中，需要输入两个阈值T1和T2，因此在map阶段和reduce阶段要分别设置两个阈值(T1，T2)和(T3，T4)，且T3>T1，T4>T2，然后按照Canopy算法思想设置filter值。

(2)对FCM算法进行Map-Reduce化

(1)

(2)

式中Nk表示第k个map节点的数量，在reduce阶段计算聚类中心，如公式(3)所示：

(3)

其中p表示map节点数。

FCM的Map-Reduce化分为五个阶段，分别是map阶段、combine阶段、reduce阶段、迭代过程及数据对象分类的过程。

并行化的Canopy-FCM算法分为Canopy算法时间复杂度和FCM算法时间复杂度两部分，设数据集的数据量为N，map阶段的节点数量为m，reduce阶段的节点数量为r，迭代次数用i表示，聚类中心的数量用c表示，k表示对象维数。

map过程的执行总时间为：

(4)

Combine过程执行时间为：

(5)

reduce过程执行时间为：

t3=mck

(6)

迭代过程的执行时间为：

(7)

对象划分过程是计算集合中的数据对簇中心的隶属程度，并依据隶属度的大小将数据数据对象归到合适的类，所以时间复杂度与map过程同为：

(8)

综上所述，并行化的FCM过程执行时间为：

t6=(2ckN/m+mck)i+ckN/m

(9)

因此并行化的FCM算法复杂度约为O(ckNi/m)。

Canopy算法产生的Canopy个数与聚类中心的个数同为c，则并行化的Canopy计算时间为：

(10)

则并行化的Canopy-FCM算法的总运行时间为：

t8=(2ckN/m+mck)i+ckN/m+cN/m+cmc

(11)

因此Canopy-FCM算法时间复杂度为O(ckNi/m)。

单机模式下的FCM算法过程分为属度计算过程、迭代过程和数据对象分类三部分，数据对象分类可以通过最后的模糊矩阵计算。因此总的计算时间为：

tsingle=ckNi+cN

(12)

由理论推导得出，单机模式的FCM算法复杂度为O(ckNi)，是并行化的m倍。并行化的FCM是在计算机集群上并行运行，所以加快了算法的运行速度。

3 实验分析

仿真平台是Apache Mahout，它是运行在Hadoop平台下的针对大数据集的一个机器学习库，通过MapReduce模型进行实现。算法采用的数据集是由加州理工学院提供的Caltech 101，图像修复过程采用其中5组数据。

3.1改进聚类算法实验

聚类实验部分，使用查准率(Precision)、查全率(Recall)和簇间距离评估结果。

(13)

(14)

TP是指在当前簇中被正确聚类的数据对象的个数，FP是指在当前簇中被误聚到该簇的数据，FN是指该簇实际包含的对象的数目。n表示整个数据集的类别，则平均查准率和平均查全率可以表示为：

(15)

(16)

从表1可以看出，Canopy-FCM算法不论是在聚类效果上还是在运算速度上都优于FCM算法。如表2所示，该算法比FCM簇间最大距离、簇间最小距离和归一化距离都降低，可见Canopy-FCM改善了FCM算法的聚类质量。

表1 算法的聚类质量

表2 簇间距离结果

3.2改进的聚类图像修复算法

实验的图像修复部分，采用均方误差(MSE)和峰值信噪比(PSNR)评估算法。均方误差的数值越小，说明与原图像越接近，修复效果越好；峰值信噪比越大，说明图像复原的效果越好。

分析三种不同算法在图像随机丢失50%和70%的信息时的仿真图和评价指标对比结果，验证算法的有效性和可行性，如表3和表4所示。

表3 实验图像丢失50%信息

表4 实验图像丢失70%信息

以上实验的分析结果表明，本文算法在均方误差、峰值信噪比和运行速度上均优于DCT算法和K-SVD算法。

4 结论

本文提出一种基于Hadoop的改进聚类算法，并将其应用于受损图像，尽可能还原图像信息。首先基于图像相似性使用Canopy-FCM聚类算法对图像进行分类，同时在Hadoop分布式平台进行并行化处理，然后对每类图像进行字典训练，并使用获得的字典来修复受损。实验结果证明，本文算法在速度、均方根误差和峰值信噪比上，均优于仅仅利用待修复图像进行字典训练的图像修复算法。

[1] OLSHAUSEN B A, FIELD D J. Emergence of simple-cell receptive field properties by learning a sparse code for natural images[J]. Nature, 1996, 381(6583): 607-609.

[2] SAHOO S K, Lu Wenmiao. Image denoising using sparse approximation with adaptive window selection[C]. Information Communication Signal Processing, 2011: 1-4.

[3] ELAD M, AHARON M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 2006, 15(12):3736-3745.

[4] 何埜,李光耀,肖莽,等.基于深度信息的图像修复算法[J].计算机应用,2015, 35(10): 2955-2958.

[5] 陈泽墅. 基于稀疏表示的图像修复算法研究[D]. 杭州：浙江工业大学, 2015.

[6] 常晨, 何建农. 改进的基于样本块的图像修复方法[J]. 微型机与应用, 2015, 34(23):45-47.

[7] 杨茹, 秦振涛, 杨武年. 基于字典学习的古建筑图像修复研究[J]. 电子技术应用, 2016, 42(12):51-53.

[8] 余长俊,张燃.云环境下基于Canopy聚类的FCM算法研究[J].计算机科学, 2014, 41(s2):316-31.

Application of improved clustering algorithm based on Hadoop in image inpainting

Wang Lin, Lei Jia, Hao Huihui

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

TP391

A

10.19358/j.issn.1674- 7720.2017.18.015

王林，雷佳，郝惠惠.基于Hadoop的改进聚类算法在图像修复上的应用[J].微型机与应用，2017,36(18)：49-51.

2017-03-29)

王林(1963-)，男，博士，教授，主要研究方向：复杂网络、图像处理。

雷佳(1991-)，通信作者，女，硕士研究生，主要研究方向：图像处理。E-mail:754438195@qq.com。

郝惠惠(1989-)，女，硕士，主要研究方向：图像处理。