基于Hadoop的改進(jìn)聚類算法在圖像修復(fù)上的應(yīng)用

王 林，雷 佳，郝惠惠

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

基于Hadoop的改進(jìn)聚類算法在圖像修復(fù)上的應(yīng)用

王 林，雷 佳，郝惠惠

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

針對(duì)模糊聚類算法在運(yùn)算大數(shù)據(jù)量時(shí)性能差的問題，提出基于Hadoop分布式平臺(tái)的改進(jìn)算法進(jìn)行圖像修復(fù)。對(duì)于受損圖像信息，首先將Canopy算法和模糊聚類相結(jié)合在Hadoop平臺(tái)上進(jìn)行并行化，然后進(jìn)行字典訓(xùn)練獲得修復(fù)圖像。實(shí)驗(yàn)結(jié)果表明，該算法在均方誤差和峰值信噪比上均優(yōu)于改進(jìn)前的圖像修復(fù)算法，提高了圖像修復(fù)質(zhì)量并且減少了算法的運(yùn)行時(shí)間，適合修復(fù)海量圖像。

圖像修復(fù)；聚類；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 引言

圖像技術(shù)在各個(gè)方面都得到廣泛應(yīng)用[1]，但在圖像獲取過程中往往會(huì)造成圖像信息丟失。利用受損圖像信息恢復(fù)出原始圖像信息，即圖像復(fù)原技術(shù)。

2011年，SAHOO S K等人[2]利用局部圖像塊的稀疏近似來解決圖像修復(fù)問題，提出了一個(gè)用于局部稀疏近似的自適應(yīng)窗口選擇步驟來影響底層圖像全局恢復(fù)的框架，此框架提供了一個(gè)基于選擇窗口大小的群集圖像,接著利用稀疏近似算法分別修復(fù)每一個(gè)群集，從而達(dá)到理想的修復(fù)結(jié)果。此外，研究學(xué)者在文獻(xiàn)[3-7]中都對(duì)圖像修復(fù)算法進(jìn)行改進(jìn)，不同程度地提高了修復(fù)效果。但這些算法沒有考慮到圖像之間存在相似性，而且對(duì)于樣本數(shù)據(jù)大的情況，沒有提出有效地提高算法效率的解決方案。

針對(duì)以上缺陷，提出一種運(yùn)行在Hadoop分布式平臺(tái)上的改進(jìn)聚類的字典學(xué)習(xí)算法。首先對(duì)圖像數(shù)據(jù)集中的多類圖像運(yùn)用改進(jìn)的模糊聚類算法(FCM)進(jìn)行分類，同時(shí)在Hadoop分布式平臺(tái)進(jìn)行并行化計(jì)算，然后對(duì)每一類圖像數(shù)據(jù)進(jìn)行字典訓(xùn)練，得到每類圖像的字典再指導(dǎo)圖像修復(fù)。

1 理論基礎(chǔ)

聚類是一種數(shù)據(jù)挖掘算法，基于信息之間的相似性對(duì)數(shù)據(jù)進(jìn)行分類，與分類算法不同的是，聚類在算法開始之前并不知道要將數(shù)據(jù)分為幾類。Canopy算法和FCM都是聚類算法，只是聚類方式不同。兩個(gè)聚類算法各有優(yōu)缺點(diǎn)，本文將兩種算法結(jié)合，充分利用兩個(gè)聚類的優(yōu)勢(shì)對(duì)圖像信息進(jìn)行聚類分析。

1.1 Canopy-FCM算法

Canopy-FCM算法的思路是利用Canopy算法產(chǎn)生聚類中心，從而彌補(bǔ)了 FCM聚類算法對(duì)初始聚類中心敏感的問題。Canopy-FCM算法的基本思路是：首先使用Canopy算法產(chǎn)生若干個(gè)初始聚類中心，然后再刪除那些聚類中心中小于特定閾值的值；之后根據(jù)第一步已經(jīng)產(chǎn)生的聚類中心，再進(jìn)行模糊C均值聚類[7]。

因此可以先使用Canopy算法粗聚類，產(chǎn)生初始聚類中心，再使用FCM算法細(xì)聚類，從而提高算法效率，改善模糊C均值算法的不足。

1.2基于K-SVD字典訓(xùn)練的圖像修復(fù)算法

基于K-SVD字典訓(xùn)練的圖像修復(fù)算法主要是從受損圖像中提取有用信息，然后選擇初始字典D，使用K-SVD算法對(duì)分塊后的圖像進(jìn)行訓(xùn)練，得到新的字典，并計(jì)算出稀疏系數(shù)，再更新對(duì)應(yīng)的圖像，如此便能修復(fù)受損圖像。

具體步驟為：

(1)對(duì)圖像進(jìn)行稀疏編碼。

(2)更新第k類圖像字典Dk。

(3)重復(fù)執(zhí)行步驟(1)和步驟(2)，直到滿足迭代次數(shù)，字典Dk更新完成。

(4)選擇對(duì)應(yīng)的字典Dk(k∈1，…，I)作為基字典，進(jìn)行K-SVD字典訓(xùn)練，計(jì)算稀疏系數(shù)，并利用更新的字典乘以稀疏系數(shù)，修復(fù)受損圖像。

2 本文算法

考慮到圖像之間的相似性，因此修復(fù)圖像之前，首先對(duì)圖像數(shù)據(jù)進(jìn)行聚類，然后將已聚類的圖像進(jìn)行K-SVD字典訓(xùn)練。傳統(tǒng)FCM對(duì)初始值敏感[8]，本文針對(duì)此問題進(jìn)行了改進(jìn)，應(yīng)用Hadoop分布式平臺(tái)并行化算法來提高聚類速率。

Canopy-FCM算法的并行化過程分為兩個(gè)步驟：第一步是對(duì)Canopy算法進(jìn)行Map-Reduce化；第二步是對(duì)FCM算法進(jìn)行Map-Reduce化。

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

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

(1)對(duì)Canopy算法進(jìn)行Map-Reduce化

Canopy算法的并行化分為map過程和reduce過程。Canopy算法的并行化首先將原始數(shù)據(jù)分為若干數(shù)據(jù)分片，并復(fù)制到執(zhí)行任務(wù)的map節(jié)點(diǎn)上，而且所有的map節(jié)點(diǎn)獨(dú)立完成分配的任務(wù)。map過程主要是使用Canopy算法思想對(duì)該節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行串行處理，然后獲得形式的Canopy中心集合。

在串行化的Canopy過程中，需要輸入兩個(gè)閾值T1和T2，因此在map階段和reduce階段要分別設(shè)置兩個(gè)閾值(T1，T2)和(T3，T4)，且T3>T1，T4>T2，然后按照Canopy算法思想設(shè)置filter值。

(2)對(duì)FCM算法進(jìn)行Map-Reduce化

(1)

(2)

式中Nk表示第k個(gè)map節(jié)點(diǎn)的數(shù)量，在reduce階段計(jì)算聚類中心，如公式(3)所示：

(3)

其中p表示map節(jié)點(diǎn)數(shù)。

FCM的Map-Reduce化分為五個(gè)階段，分別是map階段、combine階段、reduce階段、迭代過程及數(shù)據(jù)對(duì)象分類的過程。

并行化的Canopy-FCM算法分為Canopy算法時(shí)間復(fù)雜度和FCM算法時(shí)間復(fù)雜度兩部分，設(shè)數(shù)據(jù)集的數(shù)據(jù)量為N，map階段的節(jié)點(diǎn)數(shù)量為m，reduce階段的節(jié)點(diǎn)數(shù)量為r，迭代次數(shù)用i表示，聚類中心的數(shù)量用c表示，k表示對(duì)象維數(shù)。

map過程的執(zhí)行總時(shí)間為：

(4)

Combine過程執(zhí)行時(shí)間為：

(5)

reduce過程執(zhí)行時(shí)間為：

t3=mck

(6)

迭代過程的執(zhí)行時(shí)間為：

(7)

對(duì)象劃分過程是計(jì)算集合中的數(shù)據(jù)對(duì)簇中心的隸屬程度，并依據(jù)隸屬度的大小將數(shù)據(jù)數(shù)據(jù)對(duì)象歸到合適的類，所以時(shí)間復(fù)雜度與map過程同為：

(8)

綜上所述，并行化的FCM過程執(zhí)行時(shí)間為：

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

(9)

因此并行化的FCM算法復(fù)雜度約為O(ckNi/m)。

Canopy算法產(chǎn)生的Canopy個(gè)數(shù)與聚類中心的個(gè)數(shù)同為c，則并行化的Canopy計(jì)算時(shí)間為：

(10)

則并行化的Canopy-FCM算法的總運(yùn)行時(shí)間為：

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

(11)

因此Canopy-FCM算法時(shí)間復(fù)雜度為O(ckNi/m)。

單機(jī)模式下的FCM算法過程分為屬度計(jì)算過程、迭代過程和數(shù)據(jù)對(duì)象分類三部分，數(shù)據(jù)對(duì)象分類可以通過最后的模糊矩陣計(jì)算。因此總的計(jì)算時(shí)間為：

tsingle=ckNi+cN

(12)

由理論推導(dǎo)得出，單機(jī)模式的FCM算法復(fù)雜度為O(ckNi)，是并行化的m倍。并行化的FCM是在計(jì)算機(jī)集群上并行運(yùn)行，所以加快了算法的運(yùn)行速度。

3 實(shí)驗(yàn)分析

仿真平臺(tái)是Apache Mahout，它是運(yùn)行在Hadoop平臺(tái)下的針對(duì)大數(shù)據(jù)集的一個(gè)機(jī)器學(xué)習(xí)庫(kù)，通過MapReduce模型進(jìn)行實(shí)現(xiàn)。算法采用的數(shù)據(jù)集是由加州理工學(xué)院提供的Caltech 101，圖像修復(fù)過程采用其中5組數(shù)據(jù)。

3.1改進(jìn)聚類算法實(shí)驗(yàn)

聚類實(shí)驗(yàn)部分，使用查準(zhǔn)率(Precision)、查全率(Recall)和簇間距離評(píng)估結(jié)果。

(13)

(14)

TP是指在當(dāng)前簇中被正確聚類的數(shù)據(jù)對(duì)象的個(gè)數(shù)，F(xiàn)P是指在當(dāng)前簇中被誤聚到該簇的數(shù)據(jù)，F(xiàn)N是指該簇實(shí)際包含的對(duì)象的數(shù)目。n表示整個(gè)數(shù)據(jù)集的類別，則平均查準(zhǔn)率和平均查全率可以表示為：

(15)

(16)

從表1可以看出，Canopy-FCM算法不論是在聚類效果上還是在運(yùn)算速度上都優(yōu)于FCM算法。如表2所示，該算法比FCM簇間最大距離、簇間最小距離和歸一化距離都降低，可見Canopy-FCM改善了FCM算法的聚類質(zhì)量。

表1 算法的聚類質(zhì)量

表2 簇間距離結(jié)果

3.2改進(jìn)的聚類圖像修復(fù)算法

實(shí)驗(yàn)的圖像修復(fù)部分，采用均方誤差(MSE)和峰值信噪比(PSNR)評(píng)估算法。均方誤差的數(shù)值越小，說明與原圖像越接近，修復(fù)效果越好；峰值信噪比越大，說明圖像復(fù)原的效果越好。

分析三種不同算法在圖像隨機(jī)丟失50%和70%的信息時(shí)的仿真圖和評(píng)價(jià)指標(biāo)對(duì)比結(jié)果，驗(yàn)證算法的有效性和可行性，如表3和表4所示。

表3 實(shí)驗(yàn)圖像丟失50%信息

表4 實(shí)驗(yàn)圖像丟失70%信息

以上實(shí)驗(yàn)的分析結(jié)果表明，本文算法在均方誤差、峰值信噪比和運(yùn)行速度上均優(yōu)于DCT算法和K-SVD算法。

4 結(jié)論

本文提出一種基于Hadoop的改進(jìn)聚類算法，并將其應(yīng)用于受損圖像，盡可能還原圖像信息。首先基于圖像相似性使用Canopy-FCM聚類算法對(duì)圖像進(jìn)行分類，同時(shí)在Hadoop分布式平臺(tái)進(jìn)行并行化處理，然后對(duì)每類圖像進(jìn)行字典訓(xùn)練，并使用獲得的字典來修復(fù)受損。實(shí)驗(yàn)結(jié)果證明，本文算法在速度、均方根誤差和峰值信噪比上，均優(yōu)于僅僅利用待修復(fù)圖像進(jìn)行字典訓(xùn)練的圖像修復(fù)算法。

[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] 何埜,李光耀,肖莽,等.基于深度信息的圖像修復(fù)算法[J].計(jì)算機(jī)應(yīng)用,2015, 35(10): 2955-2958.

[5] 陳澤墅. 基于稀疏表示的圖像修復(fù)算法研究[D]. 杭州：浙江工業(yè)大學(xué), 2015.

[6] 常晨, 何建農(nóng). 改進(jìn)的基于樣本塊的圖像修復(fù)方法[J]. 微型機(jī)與應(yīng)用, 2015, 34(23):45-47.

[7] 楊茹, 秦振濤, 楊武年. 基于字典學(xué)習(xí)的古建筑圖像修復(fù)研究[J]. 電子技術(shù)應(yīng)用, 2016, 42(12):51-53.

[8] 余長(zhǎng)俊,張燃.云環(huán)境下基于Canopy聚類的FCM算法研究[J].計(jì)算機(jī)科學(xué), 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ìn)聚類算法在圖像修復(fù)上的應(yīng)用[J].微型機(jī)與應(yīng)用，2017,36(18)：49-51.

2017-03-29)

王林(1963-)，男，博士，教授，主要研究方向：復(fù)雜網(wǎng)絡(luò)、圖像處理。

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

郝惠惠(1989-)，女，碩士，主要研究方向：圖像處理。