基于k-mean聚類與灰度梯度最大熵的樹木圖像分割

白雪冰，陳 凱，郭景秋，祝 賀，張庭亮

(東北林業大學 機電工程學院，哈爾濱 150040)

自20世紀開始，計算機技術得到了長足的進步，數字圖像處理也隨之快速的發展起來。數字圖像處理就是利用計算機或其他數字硬件，對從圖像信息轉換而得的電信號進行某些數學運算，以提高圖像的實用性[1-3]。目前數字圖像處理所處理的圖像信息大多數是二維信息，所以信息量很大，加大了圖像處理的難度，因此也對計算機會有較高的要求，如存儲容量和計算速度等。由于數字圖像中各個像素點之間具有較大的相關性與不獨立性，所以，圖像處理中能夠具有較快的處理速度和精度與圖像信息的壓縮還有很大的發展空間[4-6]。

本文結合目前的彩色圖像處理算法提出了基于k-mean聚類與灰度-梯度最大熵的樹木圖像分割算法，該算法為了更好地區分目標圖像與背景，先采用k-mean聚類初分割，再利用灰度-梯度空間能夠明確的描述圖像中各像素點灰度與梯度的分布規律及圖像中的所需目標圖像與背景之間的邊緣情況[7]，基于灰度-梯度最大熵進行精分割，因此，圖像分割所得到的結果將更為理想，精度得到一定提高，處理速度也有所提高。

1 k-mean聚類初分割

k-means算法是一種經典的基于距離的算法，用距離的遠近來評價其相似性，即認為兩個對象距離越遠，相似性就越小，而距離越近，其相似度就越大，因此該算法最終得到緊湊且獨立的簇。

算法過程如下：

(1)從整體N個類別中任意選出K個類別作為聚類中心。

(2)對其他的每個類別計算其到每個聚類中心的距離，并把該類別歸為最近的聚類中心的類。

(3)再重新計算已經分出的每一個類的聚類中心。

(4)迭代(2)～(3)步直至新的中心與原中心相等或小于指定閾值，算法結束。

K-mean聚類算法將對象分為K個類別C={ck，i=1，2，…，K}每類含ck有一個聚類中心μi，應用歐式距離公式計算類內各點到聚類中心μi的距離平方和：

。

(1)

圖1 K-mean聚類初分割

從圖中看出，圖像被分別聚成了兩類，三類和四類。聚成三類或者四類的時候，出現了目標和背景區域混淆的情況，效果較差。圖1中原圖是一副背景簡單的樹木圖像，聚成兩類比較合適。

2 灰度-梯度最大熵算法

2.1 灰度-梯度共生矩陣

描述圖像的過程中，將灰度分布與梯度信息融合得灰度梯度共生矩陣[2](GGCM)，設一幅M×N灰度圖像f(m,n);m=0,1…M-1,n=0,1,…N-1，則灰度歸一化圖像和梯度歸一化圖像分別為：

(2)

(3)

式中：Lf為最大灰度級；Lg為最大梯度級；fmax為灰度矩陣最大值；gmax為梯度矩陣最大值[4]。

GGCM定義為H=(hxy),x=0,…,Lf-1,y=0,…,Lg-1，其中元素H(x,y)定為F(m,n)與G(m,n)中具有灰度級x和梯度級y的像點數，歸一化圖像為：

(4)

2.2 灰度-梯度最大熵

共生矩陣是Lf×Lg維的矩陣的圖像，設(Lf-1)×(Lg-1)大小的區域為圖像的二維直方圖，如圖2所示，共生矩陣坐標系的原點在左上角，其中橫坐標為圖像的梯度值且橫向遞增，縱坐標為其灰度值且縱向遞增。定義閾值在(s,t)，由于閥值處灰度值與梯度值區分明顯，目標的灰度值較低而背景的灰度值較高，所以共生矩陣就被分為A、B、C、D四個象限。本算法是以灰度-梯度共生矩陣和最大熵基礎，充分結合了圖像的灰度和梯度信息。

圖2 共生矩陣四個區域

物體和背景的灰度值變化不大，所以灰度值比較小：A(0≤i≤s，0≤j≤t)表示物體，D(s+1≤i≤Lf-1,0≤j≤t)表示背景。隨著t值不斷變大，其對應像素點是目標與背景邊界的概率增加，因此共生矩陣在B(0≤i≤s，t+1≤j≤Lg-1)中的元素kij為灰度i屬于物體和梯度j屬于邊緣轉移數目，在C(s+1≤i≤Lf-1,t+1≤i≤Lg-1)中元素的kij為灰度i屬于背景和梯度j屬于邊緣數目，所以4個象限像素和為：

(5)

將pij正規化為：

(6)

由此可知其條件熵為：

(7)

(8)

所以圖像的條件熵為：

(9)

依據最大熵理論，H獲得最大值的(s*，t*)即是最佳閾值[6]：

(10)

最后對灰度-梯度最大熵的分割結果進行形態學后處理，通過標注連通對象，計算標注的面積，去除面積比較小的部分，可以實現對背景非目標區域信息比較理想的清除，再通過膨脹操作將圖像邊緣中的薄弱斷開處進行連接，通過腐蝕操作將粘連的目標部分斷開。從分割結果看出，獲得了完整的閉合曲線輪廓。

3 實驗結果

基于以上理論基礎，應用計算機，Matla7.0集成環境[11-13]對樹木圖像進行分割，分割過程及其結果分析如圖3所示。

圖3 實驗結果

對經過灰度-梯度最大熵方法的分割后結果進行形態學后處理操作，從分割結果看出，獲得了完整的閉合曲線輪廓，獲得更多的樹木邊緣信息，細節處分割效果較好，對于樹木中的明顯空洞也分割的較為清晰[6]，分割時間為t=102 407.000us。

應用灰度-梯度最大熵對不同圖像分割結果如圖4所示。

圖4 不同背景下樹木圖像分割

從分割結果看出，獲得了完整的閉合曲線輪廓，細節處分割效果較好，對于樹木中的明顯空洞也分割的較為清晰，整個分割過程運行時間可以接受，但是在聚類過程可能會嘗試幾次確定合適的類數，導致分割具有一定程度的復雜性[5]。

二維最大熵與灰度-梯度最大熵分割結果對比如圖5～圖7所示。

圖5 樣本一

圖6 樣本二

圖7 樣本三

兩種分割方法運行時間對比見表1。

表1 兩種分割方法運行時間對比

將之前的分析結果結合表格1可以直觀的看出，對于樹木圖像分割，灰度-梯度最大熵分割結果的分割效果要好于二維最大熵分割結果[7]的分割效果，且運行時間明顯小于其運行時間。結合上述各組實驗的結果圖像的分析可知，灰度-梯度最大熵分割結果可以分割出較為完整的閉合曲線，因為結合了圖像的梯度信息，所以可以獲得較好的邊緣輪廓線。

4 結束語

該算法對彩色樹木圖像的分割具有較好的分割效果。對于背景比較復雜的樹木圖像，運用基于k-mean聚類與灰度-梯度最大熵算法的分割算法對圖像進行分割，可以獲得較完整的閉合曲線，效果較好，再通過形態學后處理可以消除背景非目標區域的干擾，且程序運行速度較快，精度較高。當然這種方法也存在缺點，對于樹木中的空洞繁多，基于k-mean聚類與灰度梯度最大熵算法分割獲得的圖像邊緣和原圖像邊緣會有出入，這樣就可能丟失了部分的樹木信息。

【參 考 文 獻】

[1]王克奇，馬曉明，白雪冰.基于分形理論和數學形態學的木材表面缺陷識別的圖像處理[J].森林工程，2013，29(3)：48-50+53.

[2]梁 建.基于灰度-梯度共生矩陣的植被提取方法[J].海洋測繪，2013，33(1)：29-31.

[3]朱 峰，王海豐，任洪娥.基于Gabo變換的紋理圖像分割算法及應用[J].森林工程，2013，29(5)：60-63.

[4]郭 烈，王榮本，金立生，等.基于二維最大熵閾值分割的坑識別方法[J].計算機工程與應用，2006(21)：226-228.

[5]王曉松.復雜背景下樹木圖像提取研究[D].北京：北京林業大學，2010.

[6]蔡世捷.基于Matlab的樹木圖像分割方法研究[D].南京：南京林業大學，2005.

[7]洪繼光.灰度-梯度共生矩陣紋理分析方法[J].自動化學報，1984，10(1)：22-25.

[8]周德龍，申石磊.基于灰度-梯度共生矩陣模型的最大熵閾值處理算法[J].小型微型計算機系統，2002，23(2)：136-138.

[9]陳 果，左洪福.圖像分割的二維最大熵遺傳算法明[J].計算機輔助與圖形算法，2006，14(6)：530-533.

[10]王再尚.Markov隨機場的樹木表面缺陷模式識別方法的研究[D].哈爾濱：東北林業大學，2012.

[11]蔣慶豐.K-Means聚類算法研究及圖形演示的實現[J].信息技術，2010，10(3)：22-25.

[12]闞江明，李文彬.基于數學形態學的樹木圖像分割方法[J].北京林業大學學報，2006，40(S2)：12-30.

[13]季 虎，孫即祥，邵曉芳，等.圖像邊緣提取方法及展[J].計算機工程與應用，2004，40(14)：70-73.