基于Fisher判別的改進WFCM 分割算法

鄭金志，曾紹華，曾凡玉，龍 穎

（1.重慶師范大學(xué) 計算機與信息科學(xué)學(xué)院，重慶401331；2.重慶師范大學(xué) 模式分析與信息處理研究所，重慶401331）

0 引 言

傳統(tǒng)的FCM 算法分割圖像通常存在幾個缺點［1］：①初始化不當(dāng)導(dǎo)致算法收斂到局部最優(yōu)解；②算法運行耗時，F(xiàn)CM 分割圖像無法滿足工程實踐的實時性要求；③算法沒有考慮聚類像素的空間信息，對噪聲比較敏感。因此，高新波、Abbas Biniaz等學(xué)者提出了改進的FCM 算法［1－7］解決圖像信息量大、分割耗時的問題，取得了一定的效果，不過，改善的效率較為有限。劉健等學(xué)者提出基于GLCM 特征的改進FCM 圖像分割算法［8］，將GLCM 和粒子群優(yōu)化算法引入到FCM 算法中較好解決了初始聚類中心不易確定的問題，但是該算法較為耗時。Zulaikha Beevi、彭代強等學(xué)者提出了改進FCM 算法［9，10］，期望解決算法本身對圖像噪聲敏感的問題。這些的改進算法對每一個像素的空間信息進行處理，一定程度上改善了噪聲對圖像分割結(jié)果的影響，但對正常像素點做抑噪處理浪費了大量的時間，且隨圖像噪聲的增加，分割效果顯著降低。

由于電路板加工、生產(chǎn)等環(huán)境中有很強的靜電脈沖和攝像設(shè)備本身的因素等原因，電路板圖像含有較多的椒鹽噪聲。對噪聲圖像的分割可以在分割前先進行濾噪，但是這種把抑噪和分割分開的方法會增加噪聲圖像的分割時間，無法滿足電路板圖像檢測中對實時性和抑噪能力的要求，尚需進一步改進。

本文基于WFCM 對椒鹽噪聲圖像的分割主要做兩方面的工作：①構(gòu)造最優(yōu)化問題，優(yōu)化初始聚類中心，以期減少算法運行時間和迭代次數(shù)，改善算法的時間效率；②引入噪聲像素點的空間信息，在減少算法對噪聲敏感的同時，盡可能提高算法的時間效率。

1 加權(quán)模糊c均值聚類 （WFCM）算法

高新波等提出一種WFCM （加權(quán)模糊C 均值）聚類算法［2］。其思想是：對于灰度圖像，將像素點的灰度值投影到256個灰度級上，算法聚類的對象不再是像素點，而是圖像在256個灰度級上的投影；每一灰度級對應(yīng)的直方圖函數(shù)值為樣本聚類權(quán)值。

WFCM 算法［2］：設(shè)將有效灰度級集G ＝｛0，1，2，…，255｝分為C 類。定義圖像f（x，y）的歸一化直方圖函數(shù)

建立WFCM 關(guān)于隸屬度矩陣U 和聚類中心V 的最優(yōu)化問題［2］

式中：C——分類數(shù)，H0（g）——灰度級g 的權(quán)值，uig——灰度級g 對第i類的隸屬度，m——模糊指數(shù)，也稱為平滑參數(shù)，用其來調(diào)節(jié)聚類的模糊程度。向量V ＝｛v1，v2，…，vC｝為C 類各自的聚類中心，dik（g，vi）為灰度級g 離第i類聚類中心的距離。

應(yīng)用拉格朗日乘數(shù)法求解，獲得隸屬度矩陣U 和聚類中心向量V 的迭代算子［2］

WFCM 算法描述如下：

算法1：WFCM［2］算法

輸入（1）M×N 的圖像像素點集合f ＝｛f（x，y）｜f（x，y），x，y ∈N；0≤f（x，y）≤255，1≤x ≤M，1≤x ≤N｝（2）灰度級集合G ＝｛0，1，2，…，255｝初始化（1）終止閾值T、加權(quán)指數(shù)m、聚類數(shù)C、迭代計數(shù)器P＝0；（2）初始聚類中心向量V（p）賦隨機值；過程（1）用式 （1）計算集合f（x，y）的直方圖H0（G）；（2）do｛ 1）用G 和V（p）計算歐氏距離矩陣 D ＝｛dig ＝ g－v（i） ｝； 2）更新迭代計數(shù)器P ＝P＋1； 3）用式 （3）計算隸屬度矩陣U（p）； 4）用式 （4）計算聚類中心V（p）；｝while V（p）—V（p－1） ≥（T ）輸出（1）隸屬度矩陣U ＝U（p）；（2）聚類中心V ＝V（p）；（3）迭代次數(shù)P；

2 改進的WFCM 算法

高新波［2］等提出的WFCM 算法，采用隨機數(shù)初始化聚類中心或隸屬度矩陣，缺乏科學(xué)合理性；存在初始值的不同、分類結(jié)果、迭代次數(shù)可能不一致，運行進程和結(jié)果嚴(yán)重依賴于初始值的問題；算法沒有考慮像素點的空間信息，分割結(jié)果對圖像噪聲敏感。因此，為了滿足含椒鹽噪聲電路圖像分割的工程實踐要求，需要對WFCM 進行改進。

2.1 根據(jù)噪聲圖像粗略復(fù)原直方圖

理論上灰度直方圖應(yīng)是多峰函數(shù)，基于WFCM 的圖像分割算法假定背景和目標(biāo)在直方圖中對應(yīng)不同的波峰［2］，然而實際圖像中，由于噪聲的污染使得直方圖的波峰波谷不再明顯，直方圖的波峰波谷不能很好的代表圖像目標(biāo)與背景的區(qū)分關(guān)系［2］。本文在電路圖像分割前，首先粗略恢復(fù)其直方圖。

2.1.1 計算圖像噪聲率

Kenny等［11］提出對于灰度圖像把灰度值為0和255的像素點定義為椒鹽噪聲點。對M×N 被椒鹽噪聲污染的電路圖像f（x，y），f（x，y）∈ ｛0，1，2，…，255｝是像素點（x，y）處的灰度值。定義噪聲率

2.1.2 直方圖的粗略復(fù)原

蔡利棟提出了一種椒鹽噪聲圖像的原始圖像直方圖粗略復(fù)原方法［12］

式中：H0（g）——噪聲圖像的直方圖函數(shù)，R——圖像的噪聲率。

2.2 初始聚類中心的確定

2.2.1 確定初始聚類中心的思想

根據(jù)電路圖像分割的先驗知識，確定圖像分割的類數(shù)C。采用文獻 ［13，14］的方法構(gòu)造復(fù)原直方圖H（g）勢函數(shù)，找出C－1個波谷點作為勢直方圖分割點，將該直方圖分割為C 段。由于背景和目標(biāo)在直方圖中對應(yīng)不同的波峰［11］，從C 段中分別找出C 類的初始聚類中心有利于避免算法收斂到局部最優(yōu)解處。

假設(shè)直方圖的C 段對應(yīng)C 類分割目標(biāo)，再依據(jù)Fisher［15，16］判別思想 “類間離差盡可能大，類內(nèi)離差盡可能小”構(gòu)造確定C 類重心 （初始聚類中心）的最優(yōu)化問題，最終確定模糊聚類的初始聚類中心V（0）。

設(shè)圖像中的有效灰度級G ＝｛0，1，2，…，255｝為分類樣本，灰度值g 的樣本權(quán)重為H0（g），待定系數(shù)為λ，則每個有效灰度級與λ相乘

總體重心為

則第i類的重心為

第i類的類內(nèi)離差平方和為

類內(nèi)離差平方總和為

類間離差平方總和為

獲得最優(yōu)化問題

求解最優(yōu)化式 （13），將λ帶入式 （9），求出C 類重心Yi，作為初始聚類中心V（0）。

2.2.2 確定初始聚類中心算法

依據(jù)2.2.1的算法思想，確定初始聚類中心算法描述如下：

算法2：確定初始聚類中心的算法

輸入（1）M×N 圖像的像素點集合f ＝｛f（x，y）｜f（x，y），x，y ∈N；0≤f（x，y）≤255，1≤x ≤M，1≤y ≤N｝；（2）灰度級集合G ＝｛0，2，…，255｝；初始化 （1）分類類別數(shù)C，待定系數(shù)為λ；（1）用式 （1）計算集合f（x，y）的直方圖H0（G）；（2）用式 （6）復(fù)原原始直方圖H（G）；（3）用文獻 ［13，14］中方法構(gòu)造復(fù)原直方圖H（G）的勢函數(shù)，找出C－1個波谷點，作為分割點；（4）用式 （7）和式 （8）計算總體重心過程Y；（5）for（i＝1to C）｛ 1）用式 （9）計算第i類的重心Yi； 2）用式 （10）計算第i類的類內(nèi)離差平方和Si；｝（6）用式 （11）計算類內(nèi)離差平方總和F；（7）用式 （12）計算類間離差平方總和E；（8）根據(jù)最優(yōu)化問題 （13），求解λ；（9）for（i＝1to C）｛ 1）將λ帶入式 （7）計算yg； 2）用式 （9）計算第i類的重心Yi；｝輸出 （1）初始聚類重心V（0）＝｛Y1，Y2，…，YC ｝；

2.3 改進WFCM 算法

為了抑制噪聲對分割結(jié)果的影響，一些學(xué)者根據(jù)像素的空間信息提出改進算法［6，7，9，10］，一定程度上降低算法對噪聲的敏感性。但它們未區(qū)分噪聲點和正常點，對噪聲點做迭代聚類、信息點做抑噪處理，會耗費計算時間，因此，WFCM 對椒鹽噪聲圖像的分割效果尚可進一步改進。

2.3.1 改進算法思想

首先按照Kenny等提出的方法［11］，區(qū)分椒鹽噪聲點和正常像素點；使用2.2 的方法確定初始聚類中心。然后，對正常像素點結(jié)合噪聲圖像直方圖用算法1進行聚類分割，得到正常像素點的空間隸屬度矩陣。最后，對噪聲點fg，如果它鄰域內(nèi)的正常像素點離第i類聚類中心vi的距離較近，則視為fg離第i類聚類中心vi的距離也較小。定義噪聲像素點fg隸屬于第i類的隸屬度

式中：uifg——fg對于聚類中心vi的隸屬度，ηg——fg領(lǐng)域中值不為0或255的所有像素點集合。

2.3.2 改進WFCM 算法

依據(jù)2.3.1的算法設(shè)計思想，改進WFCM 算法描述如下：

算法3：改進的WFCM 聚類算法

注：鄰域ηg 的大小為奇數(shù)；算法3中設(shè)定的分?jǐn)?shù)C與算法2中分類數(shù)C是一致的。

利用隸屬度矩陣最大化的原則，硬化軟分割的隸屬度矩陣U ，得到圖像分割結(jié)果。

3 仿真實驗

3.1 仿真實驗樣本的獲取

在實驗室環(huán)境中，將卡西歐EX－ZS26型數(shù)碼相機固定在垂直距離PCB電路板10cm 處，自動對焦的模式下采集兩張PCB圖像作為實驗數(shù)據(jù)，實驗照度范圍129.5－168.8lx。

為了減少計算，從原始圖像中隨機切割出兩張大小分別為256×320和512×640圖像區(qū)域。由于圖像被相機自帶的濾波器處理，實驗樣本圖1 （a）、 （b）和 （c）分別是添加6%、20%和30%隨機椒鹽噪聲的圖像。

圖1 實驗圖像

3.2 仿真實驗

仿真實驗環(huán)境：Win7 （32bit），系統(tǒng)內(nèi)存為4G，CPU為Intel（R）Core（TM）i5，主頻2.60GHz，Intel（R）HD Graphics 4000集成顯卡，MATLAB R2010b（32bit）。

3.2.1 恢復(fù)直方圖、獲取初始聚類中心及實驗分析

實驗假設(shè)圖像噪聲率未知道的情況下，利用算法2對圖1 （a）、圖1 （b）和圖1 （c）復(fù)原直方圖如圖2所示，計算初始聚類中心的相關(guān)數(shù)據(jù)見表1。勢直方圖尋找波峰波谷的過程張新明等學(xué)者都做了詳細論述［13，14］，本文不再對相關(guān)結(jié)論進行論證。

圖2 恢復(fù)直方圖與原始圖像直方圖的比較

圖2顯示，噪聲率較低時噪聲圖像直方圖與原始圖像直方圖較為接近，此時噪聲點對原始圖像直方圖波峰波谷的影響較?。划?dāng)噪聲率較大時，噪聲點對原始圖像直方圖波峰波谷的影響較大，算法2對原始圖像直方圖的復(fù)原能夠較好的模擬原始圖像直方圖，因此有利于波峰波谷的劃分。從表1中的數(shù)據(jù)可以看出，算法2對圖1 （a）確定的4個初始聚類中心，與最終求得聚類中心最大相差3個灰度級；對圖1 （b）和圖1 （c）確定的3個初始聚類中心，與最終獲得的聚類中心也分別最大相差23個和24個灰度級。圖1 （b）和圖1 （c）在獲取初始聚類中心過程中所得的數(shù)據(jù)比較接近，表明算法2有較強的抗椒鹽噪聲能力。

表1 算法2獲取初始聚類中心的相關(guān)數(shù)據(jù)

3.2.2 部分仿真實驗分割圖像及分析

Nikhil等提出，聚類模糊指數(shù)m 的取值范圍一般為［1.5，2.5］，通常取m ＝2時較為合適［17］。本文實驗設(shè)置m ＝2，迭代停止閾值T ＝1×10－5，設(shè)置噪聲點處理的鄰域大小為3×3，圖1 （a）分類數(shù)C ＝4，圖1 （b）和圖1（c）分類數(shù)C ＝3。部分仿真實驗結(jié)果的量化數(shù)據(jù)見表2，分割結(jié)果如圖3所示。

對比圖3與圖1 （a）可以看出WFCM［2］算法沒有任何抑噪的能力，對噪聲比較敏感；對比圖3 （a）與（b）、（d）與圖3 （e）、（g）與圖3 （h）可以看到，圖3 （b）、（e）、（h）的分割結(jié)果要稍微優(yōu)于圖3 （a）、 （d）、 （g） （如，圖 （b）分割結(jié)果集成電路上的黑色噪聲點要少于圖 （a）分割結(jié)果對應(yīng)集成電路上的黑色噪聲點），但是依然有較強的噪聲，由此可以得出，F(xiàn)FCM［18］算法具有一定的抑噪能力，但是抑噪能力十分有限。圖3 （c）是本文算法對圖1 （a）的分割結(jié)果，對比圖3 （a）、（b）與圖3 （c）3幅分割結(jié)果可以看出，當(dāng)噪聲率達到6%時，本文算法能夠正確完成圖像分割任務(wù)。

表2 3種方法對圖像分割結(jié)果及性能的比較

圖3 3種算法對圖1分割效果的對比

由圖3中3種算法對含20%椒鹽噪聲圖1 （b）的分割結(jié)果圖3 （d）、（e）、 （f）可以看到，WFCM［2］算法和FFCM［18］算法雖然仍能完成分割任務(wù)，但是FFCM［18］算法的抑噪能力有較大的衰減，而本文算法不僅能夠完成分割任務(wù)，且其分割結(jié)果幾乎不受噪聲影響。

圖3中 （g）、（h）、（i）是3種算法對含30%椒鹽噪聲的圖1 （c）分割結(jié)果。可以看出WFCM［2］算法和FFCM［18］算法不僅無法對噪聲點進行分割，而且也無法完成對像素信息點的正確分割。此外，F(xiàn)FCM［18］算法的抑噪能力幾乎完全喪失。這是因為在聚類分割過程中噪聲點對信息點造成了干擾。由本文算法對圖1 （c）的分割結(jié)果可以看到，該算法不僅能夠?qū)D像進行正確的分割，而且仍然具有較強的抑噪能力。

由圖3 （c）、（f）、 （i）可以得出：當(dāng)噪聲率達到20%時，本文算法的分割結(jié)果幾乎不受噪聲的影響；當(dāng)噪聲率達到30%時，本文算法的抑噪能力有所衰減，但是依然表現(xiàn)出了較強的抑噪性能，這證明隨著噪聲率的快速增加，本文算法的抑噪性能衰減較少。

表2中的運行時間為算法整體運行時間，包括預(yù)處理階段和循環(huán)迭代階段的時間總和；其中WFCM 算法［2］和FFCM 算法［18］因初始聚類中心的隨機化使得每次運行時間不同，表2中的數(shù)據(jù)是各自運行20次的平均值。

仿真結(jié)果表2中數(shù)據(jù)顯示：算法3因從更科學(xué)合理的初始聚類中心出發(fā)，迭代次數(shù)減少；因做抑噪處理，比WFCM［2］算法運行時間稍高，但僅犧牲較少的時間效率，增強了算法的抗噪能力。

算法3相對于FFCM［18］算法，不僅從更科學(xué)合理的初始聚類中心出發(fā)減少迭代步驟、提高算法的時間效率、使分割結(jié)果收斂到全局最優(yōu)解；同時還省去了對正常像素點進行抑噪和對噪聲點進行迭代聚類的冗余處理，進一步減少了迭代次數(shù)，提高了算法的時間效率。

4 結(jié)束語

針對在工業(yè)生產(chǎn)加工過程中電路板 （PCB）圖像含有較多椒鹽噪聲這一特性，本文提出了基于Fisher思想的改進WFCM 圖像分割算法。針對FCM 算法迭代較為耗時以及對噪聲較為敏感等缺點，根據(jù)Fisher判別的思想建立優(yōu)化初始聚類中心的模型，合理地初始化WFCM 聚類中心。然后，對圖像信息點和噪聲點進行初步判別，精簡參加迭代聚類的數(shù)據(jù)集，提高迭代聚類的時間效率。最后，根據(jù)噪聲點空間信息，對噪聲點進行分割處理，完成對整幅圖像的分割。改進算法不僅能避免噪聲點對信息點迭代聚類的干擾，而且能抑制噪聲點對圖像分割的影響，具有較強的抑噪能力和較高的時間效率。仿真結(jié)果表明，本文算法相對于經(jīng)典WFCM 算法和FFCM 算法［18］，具有更高的時間效率和抑噪性能。

［1］CUI Zhaohua，GAO liqun，OUYANG Haibin，et al.Improved fuzzy c－means clustering combined with the global best harmony search algorithm for image segmentation ［J］.Journal of Image and Graphics，2013，18 （19）：1133－11141 （in Chinese）.［崔兆華，高立群，歐陽海濱，等.融合全局最好和聲搜索算法的模糊C 均值聚類圖像分割 ［J］.中國圖象圖形學(xué)報，2013，18 （19）：1133－1141.］

［2］GAO Xinbo，LI Jie，JI Hongbing.A multi－threshold image segmentation algorithm based on weighting fuzzy C－means clustering and statistical test［J］.Acta Electronica Sinica，2004，32 （4）：661－664 （in Chinese）.［高新波，李潔，姬紅兵.基于加權(quán)模糊C均值聚類與統(tǒng)計檢驗指導(dǎo)的多閾值圖像自動分割算法 ［J］.電子學(xué)報，2004，32 （4）：661－664.］

［3］Mohamed Ali Mahjoub.Improved FCM algorithm applied to color image segmentation ［J］.Canadian Journal on Image Processing and Computer Vision，2011，2 （2）：16－19.

［4］LI Xuchao，LIU Haikuan，WANG Fei，et al.The survey of fuzzy clustering method for image segmentation ［J］.Journal of Image and Graphics，2012，17 （4）：447－458 （in Chinese）.［李旭超，劉海寬，王飛，等.圖像分割中的模糊聚類方法［J］.中國圖象圖形學(xué)報，2012，17 （4）：447－458.］

［5］Ji Zexuan，Sun Quansen，Xia Deshen.A framework with modified fast FCM for brain MR images segmentation ［J］.Pattern Recognition，2011，44 （5）：999－1013.

［6］Xu Shaoping，LIU Xiaoping，LI Chunquan et al.An improved fast FCM image segmentation algorithm base on region feature analysis［J］.Pattern Recongnition and Artificial Intellignece，2012，25 （6）：987－995.

［7］Abbas Biniaz，Ataollah Abbasi，Mosa Shamsi.Fast FCM algorithm for brain MR image segmentation ［C］／／6th International Conference on Fuzzy Information and Engineering，2012：1－8.

［8］LIU Jian，CHENG Yinglei，SUN Jida.Modified FCM SAR image segmentation method based on GLCM feature［J］.Computer Engineering and Design，2012，33 （9）：3502－3506 （in Chinese）.［劉建，程英蕾，孫紀(jì)達.基于GLCM 特征的改進FCM 的SAR 圖像分割方法 ［J］.計算機工程與設(shè)計，2012，33 （9）：3502－3506.］

［9］Zulaikha Beevi S，Mohammed Sathik M，Senthamer Aikannan K.A robust fuzzy clustering technique with spatial neighborhood information for effective medical image segmentation ［J］.International Journal of Computer Science and Information Security，2010，7 （3）：132－138.

［10］WANG Haijun，LIU Ming.Generalized fuzzy c－means algorithm with improved fuzzy partition based on local membership and neighbor information ［J］.Journal of Computer Applications，2013，33 （8）：2355－2358 （in Chinese）. ［王海軍，柳明.基于局部隸屬度和鄰域信息的GIFP－FCM 圖像分割算法 ［J］.計算機應(yīng)用，2013，33 （8）：2355－2358.］

［11］Kenny KVT，Nor AM Isa.Noise adaptive fuzzy switching median filter salt and pepper noise reduction ［J］.IEEE Signal Processing Letters，2010，17 （13）：281－284.

［12］CAI Lidong.Behavior of image histogram under pepper－andsalt noise ［J］.Computer Engineering＆Science，2008，30（11）：25－27 （in Chinese）. ［蔡利棟.椒鹽噪聲下圖像直方圖的行為 ［J］.計算機工程與科學(xué)，2008，30 （11）：25－27.］

［13］ZHANG Xinming，LI Zhenyun，ZHENG Ying.Multi－threshold image segmentation based on combining Fisher criterion and potential function ［J］.Journal of Computer Applications，2012，32 （10）：2843－2847 （in Chinese）. ［張新明，李振云，鄭穎.融合Fisher準(zhǔn)則和勢函數(shù)的多閾值圖像分割 ［J］.計算機應(yīng)用，2012，32 （10）：2843－2847.］

［14］BAY H，ESS A，Tuytelaarst.Speeded－up robust features［J］.Computer Vision and Image Understanding，2008，110（3）：346－359.

［15］WEN Qiaonong，WAN Suiren，XU Shuang.Noise image segmentation using Fisher criterion and regularization level set method ［J］.Journal of Computer Research and Development，2012，49 （6）：1339－1347 （in Chinese）.［文喬農(nóng)，萬遂人，徐雙.Fisher準(zhǔn)則和正交化水平集方法分割噪聲圖像 ［J］.計算機研究與發(fā)展，2012，49 （6）：1339－1347.］

［16］WANG Xin，LIU Ying，F(xiàn)AN Jiulun.Face feature extraction based on weighed multiple kernel Fisher discriminant analysis［J］.Computer Science，2012，39 （9）：262－247 （in Chinese）.［王昕，劉穎，范九倫.基于多核Fisher判別分析的人臉特征提取 ［J］.計算機科學(xué)，2012，39 （9）：262－247.］

［17］PR Nikhin JC Bezdek.On cluster validity for fuzzy C－means model［J］.IEEE Transactions on Fuzzy Systems，1995，3（3）：370－379.

［18］LI Zhimei，XIAO Degui.An improved image segmentation algorithm of fast fuzzy clustering ［J］.Computer Simulation，2009，26 （8）：212－215 （in Chinese）. ［李志梅，肖德貴.改進的快速模糊聚類圖象分割算法 ［J］.計算機仿真，2009，26 （8）：212－215.］