基于最大熵的進化區(qū)域生長分割算法

魏光杏，周獻中，李 華

（1. 滁州職業(yè)技術學院 信息工程學院，安徽 滁州 239000；2. 南京大學 工程管理學院，江蘇 南京 210093）

0 引言

圖像分割是圖像處理和判讀處理中一個非常重要的階段，目前有許多共性的圖像分割方法，其中包括基于區(qū)域的分割［1?4］、基于超像素的分割［5］和基于輪廓的分割［6］。好的分割方法可以更容易得到準確的圖像信息。

按區(qū)域生長進行分割是一種快速、簡單且易于實現(xiàn)的圖像分割算法。蔣秋霖等［1］將區(qū)域生長算法應用到醫(yī)學腦腫瘤圖像分割上，得到較好的分割圖像，但圖像上點的次序對該優(yōu)化算法影響較大，分割出的結果不太穩(wěn)定，容易產生過分割。肖明堯等［2］引入圖像的多尺度概念，提出基于多尺度區(qū)域生長的圖像分割算法，利用圖像多尺度的最大梯度矩陣來獲得準確的分割圖像，但算法的復雜度偏高。劉振宇等［3］提出基于改進區(qū)域生長算法的視杯自動分割算法，該算法依據(jù)圖像灰度直方圖以及閾值法對區(qū)域生長算法中的種子點定位性能進行提高，得到的分割后圖像有較高準確性，但僅適用于視網膜血管分割。文獻［4］給出了優(yōu)化算法，該算法先計算所有像素點的直方圖和鄰域相似度因子，然后根據(jù)鄰域相似度因子的值建立種子選擇規(guī)則、種子生長準則和生長終止準則，通過相關閾值對圖像進行分割。雖然該算法獲得分割圖的質量有較大提高，但它仍存在著不足，如對閾值敏感、對于不同的初始化點（種子點）得到的結果不同。

本研究提出了基于最大熵進化方法的區(qū)域生長分割優(yōu)化算法。在分割之前，以最大熵理論為基礎，從符合條件中的最大熵來確定分割后區(qū)域的數(shù)目，對進化區(qū)域生長算法中的策略進行優(yōu)化，以消除區(qū)域生長分割算法中的不足，提高了分割質量，也加快圖像分割速度。

1 區(qū)域生長算法

1.1 區(qū)域生長算法原理

區(qū)域生長算法是一種基于逼近區(qū)域的分割方法，其實現(xiàn)原理如下：

1）選擇圖像開始修正點（種子），這些點（種子）被稱為搜索區(qū)域的細菌。

2）確定搜索區(qū)域的均勻性（閾值）準則，如灰度或紋理準則等。

3）遞歸過程，滿足相關準則的所有點都包含在區(qū)域中。

這些點（種子）是變化的，但必須滿足作為準則的區(qū)域，種子點的選擇是算法的關鍵部分。生長階段將使用相似性度量來選擇要聚集的像素，當不再有像素滿足加入這個區(qū)域的條件時，區(qū)域生長停止。

1.2 基于進化策略的區(qū)域生長算法優(yōu)化

1.2.1 編碼 所給出的算法是在所有可能的區(qū)域中通過最大化驗證分割的準則來選擇最優(yōu)的區(qū)域，這將產生在該區(qū)域生長中使用的最佳種子（Psj）。因此，這里假設編碼為

式中，chr染色體是C×N圖像點的集合，Psj=(gsj)1≤j≤N=(gs1gs2) =(xs,ys)，基因 (gsj)1≤j≤N是種子Psj的坐標x和y。

1.2.2 約束條件 為避免初始解遠離最優(yōu)解，首選種子點的坐標值滿足下列條件：

式中，m1和m2是圖像的維數(shù)。

在所提出的算法中，如果帶有不滿足此約束條件的基因染色體，則通過基因的變異產生新的變異基因，用此新變異基因代替原基因。

1.2.3 適應度函數(shù) 設chr為細菌(Ps)1≤s≤C形成種群的染色體。為了計算與chr相關的適應度函數(shù)值，定義適應度函數(shù)

式中 ，MoyRi為 當 前 區(qū) 域像素Ps灰 度 的 平 均 值 ，Ngs為區(qū)域Ri中 像 素Ps的 灰 度 ，M表 示區(qū)域Ri中的像素數(shù)。如果F(chr)函數(shù)值最小，則染色體chr最優(yōu)。

1.2.4 進化區(qū)域生長算法（evolutionary region growing，ERG） 進化區(qū)域生長算法步驟如下：

1）圖像初始化，確定圖像中區(qū)域C的數(shù)目，生產種群Pop，

并用約束條件驗證種群Pop中的每個chr。

2）對每個種群Pop中的chr進行區(qū)域生長。

3）計算出每個種群Pop中chr的適應值F(chr)。

4）將計算出來的適應值F(chr)按遞增順序進行排序，選擇最佳染色體chr，也就是確定這一區(qū)域的最優(yōu)chr及其相應適應值F(chr)。

5）對種群Pop中染色體的chr利用標準正態(tài)分布N（0，1）函數(shù)進行變異，

式中，fm表示最優(yōu)chr的適應值。

6）重復第2）至第5）步驟，若生長區(qū)域中再沒有新的像素，則結束生長。

2 基于最大熵的進化區(qū)域生長圖像分割

2.1 最大熵計算公式

在圖像分區(qū)問題中，很難確定分區(qū)的數(shù)量C，很多學者采用最大熵的方法，比如文獻［7?8］等。這里選擇文獻［7］侯森提出的最大熵計算公式：

則公式變形為

式中,CLj表示第j聚類的集合是對應于j類的熵，熵S最大的值即為區(qū)域類的最佳數(shù)C。

2.2 進化策略優(yōu)化的最大熵

設FERG(chr)為函數(shù)，其最大熵原理定義為

從（8）式可以看出，當對于給定值C，函數(shù)FERG(chr)的值僅依賴于chr。當C固定，（8）式能計算并提供收斂全局最優(yōu)分區(qū)，也就是區(qū)域中chr最優(yōu)值，這時FERG(chr)的值是最大的，此值滿足Cmax＝max（FERG(chr)）。此時的最大熵就是選擇Cmax這樣的數(shù)值。如果FERG(chr)的計算得到的是局部解，則最大熵將無法正確確定Cmax的最佳數(shù)值。

因此，為了避免在計算給定值C的FERG(chr)時出現(xiàn)局部解，在ERG 算法中，用選擇函數(shù)FERG(chr)代替了適應度函數(shù)F(chr)。FERG(chr)函數(shù)可以針對多個C值進行計算，得到多個不同適應度函數(shù)值，當適應度函數(shù)FERG(chr)的值最大時，對應的C值為Cmax類的最佳數(shù)值。

2.3 基于最大熵的進化區(qū)域生長分割算法流程

首先對輸入的圖像進行初始化，利用最大熵原理計算出圖像中區(qū)域C的數(shù)目，產生種群Pop。在種群Pop中任選一種子點chr，并根據(jù)（8）式計算該chr的適應度FERG(chr)，種子點chr經過正態(tài)分布變異，用中止條件來判斷該種子點是否中止生長，具體流程如圖1 所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

3 實驗結果與分析

為了驗證所提出分割算法的性能，筆者從分割圖像標準庫中選擇3 幅經典圖像，分別采用原區(qū)域生長算法、基于多尺度的區(qū)域生長算法（文獻［2］算法）和本文算法進行圖形分割，并對其結果進行比較（見圖2 ～ 圖4）。實驗環(huán)境：PC 機主頻為2.5 GHz、酷睿I7 處理器，4.0 GB 內存，Windows 10 操作系統(tǒng)，MATLAB 2014b。

從圖2 ～圖4 可以看出，本文提出的基于最大熵的進化區(qū)域生長分割算法分割結果優(yōu)于原區(qū)域生長算法及文獻［2］算法。3 幅（d）圖中的信息點保留更為完整，邊緣線較清晰，分割的質量更優(yōu)，而在 3 幅（b）、（c）圖中，圖像有些關鍵信息點被丟失。

為了進一步驗證本文算法的優(yōu)越性，采用了總體均數(shù)、標準方差、Jaccard 系數(shù)3 種常見的評價指標來進行驗證?？傮w均數(shù)用于查找圖像的平均灰度，值越小，獲得聚類越優(yōu)，相對圖像質量越好；標準方差是指圖像像素灰度值相對于均值的離散程度，標準方差值越大，表明圖像中灰度級分布越分散，圖像質量也就相對越好；Jaccard 系數(shù)是用來比較樣本集的相似性和多樣性的統(tǒng)計量，系數(shù)值越大，獲得聚類也越優(yōu)。

圖2 3 種算法的Lena 圖像分割結果比較Fig.2 Comparison of Lena image segmentation results of three algorithms

圖3 3 種算法的Camera 圖像分割結果比較Fig.3 Comparison of Camera image segmentation results of three algorithms

圖4 3 種算法的Rice 圖像分割結果比較Fig.4 Comparison of Rice image segmentation results of three algorithms

對Lena 圖、Camera 圖以及Rice 圖進行有效性指數(shù)實驗，實驗結果如表1 所示，表中加粗數(shù)字標明為優(yōu)。

表1 用有效性指數(shù)對3 種算法比較Tab.1 Comparison of three algorithms by effectiveness index

4 結語

區(qū)域生長算法是一種簡單且易于實現(xiàn)的圖像分割算法，利用該算法分割圖像能獲得較好的分割圖，但該算法對初始化點的數(shù)目有一定的敏感性。鑒于此，文章提出了基于最大熵的進化區(qū)域生長分割算法，利用進化最大熵原理估計ERG 分割的起始點數(shù)目，克服了該算法的初始化問題。實驗結果表明，本文提出的優(yōu)化分割算法收斂速度較快，分割的質量也較好。使用總體均數(shù)、標準方差和Jaccard 系數(shù)3 種性能評價指標對區(qū)域生長算法及優(yōu)化算法的分割結果進行比較，優(yōu)化算法優(yōu)于原算法。