基于圖論的圖像分割算法分析研究

楊先花

(閩南理工學院，福建石獅 362700)

現代社會中，數字圖像是人們獲取信息的重要來源。圖像分割是從圖像預處理到圖像識別和分析理解的關鍵步驟，是把圖像分成各具特色的區域并提取出感興趣的目標的技術和過程。圖像分割的新方法不斷出現，但每一種方法都有其側重點，局限性較大，因此，不斷融入新知識對現存圖像分割算法整合優化成為研究的熱點［1－2］。

基于圖論的圖像分割算法是目前圖像處理領域的一個研究熱點，它把數學中的圖的理論應用到圖像分割中，本文對基于圖論的圖像分割算法中歸一化劃分準則與閾值化的圖像分割方法進行結合，將權值計算公式進行改進，較好的體現了像素點間的相似性，通過實驗對比，得到較好地整合效果。

1 基于圖論的圖像分割算法介紹

1.1 基于圖論的圖像分割算法概述

基于圖論的圖像分割算法的基本思想:將圖像映射為帶權的無向圖，從而把圖像的結構與圖的結構一一對應，將圖像的像素點與圖中的頂點對應，在圖像分割中利用圖的最佳劃分理論，從而將復雜的圖像分割問題簡化為最優化分問題［3］。

圖像分割中使用的圖是無向加權圖，這樣的圖G(V，E)由節點V(圖像的像素)和節點間的連接邊E組成的一種拓撲圖形，不同節點間的連接有不同的權值W，權值反映了兩個像素節點間的相似度，即屬于同一區域的可能性。

把圖G劃分為A、B兩部分，且A和B間滿足:A∩B=φA∪B=Vex，A、B之間的差異程度即所有移走的邊的權值總和。

1.2 基于圖論的圖像分割算法的發展

基于圖論的圖像分割算法的研究是近幾年國內外圖像分割領域的一個新研究熱點，主要體現在:最優割集的設計，分割中圖譜方法的應用，以及算法實現上的快速性［4］。目前較為代表性的方法見表1。

表1 基于圖論的圖像分割算法的發展Tab.1 Development of image segmentation algorithms based on graph theory

這3種代表算法都是通過對圖的某種特性研究從而建立相應的能量函數，通過對能量函數取得極小值，即得到圖理論對應圖像的最佳分組。

1.3 常見典型圖割集準則［5］

(1)Minimum Cut(最小割)

最小割集準則簡單常見，適用于較小分割，定義為公式 (1)，通過樹圖縮減的方式來實現該割集的圖像分割，優點是求解簡單，缺點是易造成孤立點的分割。

(2)Average Cut(平均割)

平均割集準則定義為公式 (2)，該割集的實現方式是通過求解方程(D-W)Z=λZ標準特征系統來實現，該割集易出現過分割。

(3)Min－Max Cut(最大最小割)

(4)Normalize Cut(歸一化割)

雨落先表示了歉意，說許姐，非常不好意思，請您來其實不是因為證書，而是想和您商量件事，一件非常重要的事。許沁略顯詫異，笑道，什么事啊，搞得這么緊張兮兮的。玉敏剛要張口，雨落用手止住了，然后平靜地說了。

歸一化割集準則定義為公式 (4)，該準則是通過求解方程(D-W)Z=λZ標準特征系統來實現，特點是能有效克服劃分孤立點的問題，但類間重疊較大時易出現歪斜劃分。

2 閾值化改進分割算法

2.1 閾值化圖像分割方法

閾值分割是一種簡單、經典的圖像分割技術，運算速度快，性能穩定，被應用于血液細胞圖像的分割、產品質量檢測等許多領域［6］。閾值分割的基本原理是通過對圖像的灰度直方圖進行數學統計，選擇一個或多個閾值將像素劃分成若干類。在實際應用中，圖像受噪聲和其他客觀因素的影響較大，圖像質量差，最佳閾值很難確定。因此，如何選取一個最佳閾值是閾值分割法的關鍵和難點。全局分割、局部分割和動態分割是常規三種最佳閾值的選擇方法，但各有弊端，新的方法不斷出現。

2.2 基于Normalized Cut準則的圖像分割方法

Shi和Malik等人提出Ncut準則描述兩類間的分離度，優點是通過對像素點位置和亮度信息的確定避免了劃分孤立點的問題，取得較好的分割效果，缺點是忽略了像素點與其鄰域的空間關系，對噪聲敏感。

2.3 改進的歸一化閾值圖像分割算法

該方法采用Normalized Cut準則與圖像的閾值分割聯合起來區分目標和背景，得到了良好地分割效果。

改進一:將以往描述圖像像素個數的權值矩陣用表示圖像亮度的灰度值的權值矩陣代替，圖像的灰度值更鮮明反映了像素間的亮度差異，圖像的空間信息反映了像素點間相互關聯的信息，大大節約了算法的時間和存儲空間。權值公式定義為:

M(u)是節點u與其四個相鄰點的灰度值的中值，體現像素點與其鄰域的空間信息的值。

改進二:將像素點與其鄰域的空間信息反映到權值計算中，降低了噪聲。

對一幅M×N的數字圖像f(x，y)，圖像灰度級為L，像素點坐標為V，則圖像信息用圖理論描述如下:

圖1 原噪聲圖片Fig.1 Original noise picture

通過分析，體現像素間的相關性的w(u，v)取值影響重大，它決定著圖像分割的質量。Tmin就是閾值分割中的門限閾值，也是改進后基于歸一化的圖譜劃分測度的圖像閾值化分割準則，門限的選取取決于圖頂點之間的邊權值w(u，v)。

在MATLAB環境下，設置數據得到效果圖如圖1～圖3所示，可以看出圖3效果較好，有效減少了噪聲。

圖2 改進前分割圖Fig.2 Segmentation map before improvement

圖3 改進后分割圖Fig.3 Segmentation map after improvement

3 結束語

本文主要介紹分析了基于圖論的圖像分割算法及其優缺點，并對改進的閾值化歸一分割算法進行設計、實驗對比，取得了較好地分割效果，實驗證明，相對于普通圖像閾值分割算法，閾值化歸一分割算法在局部處理和噪聲抑制上有較好的效果;較區域分割算法，不易產生過分割。但是算法也存在不足，比如算法在實現速度上，效果還不是很理想，如何找到快速的求解過程，找到通用性較好的權值計算公式是今后研究的方向。

【參 考 文 獻】

［1］程 偉，梁 萍．數學形態學在施切單板缺陷圖像分割中的研究［J］．林業機械與木工設備，2011，39(2):25 －27．

［2］鄒麗暉，白雪冰．數學形態學在木材表面缺陷圖像分割后處理中的應用［J］．林業機械與木工設備，2006(12):40－42．

［3］石 美．基于圖論的閾值化圖像分割方法研究［D］．合肥:合肥工業大學，2011．

［4］楊 帆，廖慶敏．基于圖論的圖像分割算法的分析與研究［J］．視頻技術．2006(7):80－83．

［5］Jiang M．Digital image processing course［R］．Technical Report，Department of Information Science．School of Mathematics．Peking University，2001．

［6］胡 敏，石 美，汪榮貴．一種具有抗噪性的圖像分割方法［J］．計算機工程．2011，37(8):231 －235．