基于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-)，女，碩士，主要研究方向：圖像處理。