一種改進的二維直方圖均值漂移分割算法

摘 要:改進了二維直方圖的構造方法，利用空間鄰域信息使改進的二維直方圖具有更豐富的噪聲判斷信息，并根據此信息將圖像分為噪聲子圖和非噪聲子圖。采用均值漂移算法對圖像進行聚類分割，并對均值漂移的高斯核函數進行了改造，使算法對噪聲有更好的平滑作用，對非噪聲區域有更準確的分割效果。實驗結果表明，改進的算法對噪聲污染的圖像有更好的抗噪能力，分割也更加準確。

關鍵詞:二維直方圖; 均值漂移; 子圖; 改造高斯核

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3536-03

doi:10.3969/j.issn.1001-3695.2009.09.096

Image segmentation of mean shift based on improved 2D histogram

LENG Lu1，2， LI Ming1， ZHANG Jia-shu2

(1. Key Laboratory of Nondestructive Testing (Ministry of Education)， Nanchang Hangkong University， Nanchang 330063， China; 2. Key Laboratory of Signal Information Processing of Sichuan Province， Southwest Jiaotong University， Chengdu 610031， China)

Abstract:This paper improved the establishment of 2D histogram to contain more detailed information of noise estimation， according to which the image was divided into noise sub-image and non-noise sub-image. Then mean shift was applied to cluster and segment. The modified Gaussian kernel function could smooth noise better and cluster more accurately in non-noise sub-image. The experimental results show that the improved algorithm has better performance of anti-noise and more accurate precision.

Key words:2D histogram; mean shift; sub-image; modified Gaussian kernel

0 引言

圖像分割一直是一個很活躍的研究領域，必須結合具體的研究背景和工程特點進行設計才能取得理想效果。基于閾值的方法是圖像分割中研究較早的一類，但閾值分割的前提是背景和目標圖像的灰度差異明顯。一維直方圖的方法(雙峰法、Otsu法等) 對噪聲污染的圖像都較難確定合適的閾值。二維直方圖結合了灰度和空間鄰域信息使分割更為準確，但算法從一維推廣到二維(二維最大熵[1]、二維FCM[2]、二維Otsu[3]等)，計算量急劇增加。另外，已提出的基于二維直方圖的分割方法對噪聲和邊緣像素的處理不夠準確，默認這些像素的概率分布為0，這明顯是不合適的。

本文針對已提出的二維直方圖分割方法的缺陷對算法進行重新設計。根據像素灰度及其鄰域內的灰度信息將圖像劃分為噪聲子圖和非噪聲子圖，并改進了二維直方圖的建立準則，使二維直方圖也能明顯體現出兩類子圖的對應區域。運算復雜度方面，文獻[4，5]提出了快速算法，還有的方法結合遺傳算法[6]、粒子群算法[7]加快閾值搜索，但這些都是對原有閾值計算方法的改進。本文采用較為快速的均值漂移(MS)算法進行聚類，對兩類子圖區域采用不同的高斯核，既對噪聲進行了平滑，又提高了分割的準確性。

1 改進的二維直方圖

1.1 子圖的劃分

全局圖像可以根據某種原則劃分成多個子圖，文獻[8]采用的雙邊直方圖均衡化即根據全圖的均值將灰度低于和高于均值的像素分成兩部分，構成兩個子圖XL和XU。本文研究的圖像可根據每個像素的特點劃分到三類子圖中，區域內部平坦子圖、邊緣子圖和噪聲子圖。這里將前兩者合并(合并的原因分析見2.2節)，從而只分成非噪聲子圖(non-noise sub-image)和噪聲子圖(noise sub-image)。

X=Xnon-noise∪Xnoise(1)

子圖分類準則采用自適應門限的方法[9]。如圖1所示的5×5模板，將中心像素13與周圍鄰域24鄰域的像素做灰度值差的絕對值，從小到大順序排列成一個矢量b。若中心像素是平坦子圖的點，這個矢量前10個點都很小;若為邊緣像素，則矢量中有約一半的個數差值較大，但前10個點依然很小;若是噪聲點，則與3×3鄰域內的8個點(與中心點棋盤距離為1)差值可能較小，與5×5鄰域內外圍的16個點(與中心點棋盤距離為2)差值較大，因此噪聲點5×5鄰域內有約16個以上的差值較大。于是定義:

Δ(i，j)=[b(4)+b(5)+b(6)+b(7)]/4(2)

其中:b(4)、b(5)、b(6)、b(7)是矢量b的第4～7個元素值;i、 j是中心像素的行列坐標。每個像素都這樣計算后得到全圖的Δ矩陣，再根據式(3)~(5)計算其均值、方差和全圖的閾值。

Δ=1/(M×N)∑Mi=1∑Nj=1Δ(i，j)(3)

σ2=1/(M×N)∑Mi=1∑Nj=1(Δ(i，j)-Δ)2(4)

threshold=Δ+σ(5)

若Δ(i，j)>threshold，認為就是噪聲點，劃分到噪聲子圖;反之則認為是非噪聲點，劃分到非噪聲子圖。

1.2 改進二維直方圖的建立

原先二維直方圖的兩維分別對應中心像素的灰度S和鄰域(如3×3、5×5鄰域)像素灰度均值T。這里將T坐標軸取為1.1節中計算Δ(i，j)時，b(4)、b(5)、b(6)、b(7)對應的四個像素的原灰度值的均值。例如若對應鄰域內四個像素的原灰度記為S(4)、S(5)、S(6)、S(7)，則

T(i，j)=[S(4)+S(5)+S(6)+S(7)]/4(6)

圖2是由此建立的二維直方圖的俯視圖，L-1=255。做兩條與對角線平行的斜線，兩條平行線與對角線的垂直距離為threshold。對于平坦區域的像素，Δ(i， j)≈0，即T(i， j)≈S(i， j)，對應圖中對角線附近，兩條平行線內的區域I。邊緣區域的像素由1.1節的分析與平坦區域像素的結論類似，也對應圖2中區域I。噪聲區域Δ(i， j)>threshold，|T(i，j)-S(i，j)|>threshold，對應圖2中兩條平行斜線以外的區域Ⅱ。

2 均值漂移聚類

2.1 均值漂移原理

給定d維空間Rd中的n個樣本點xi(i=1，…，n)，在x點的MS向量的基本形式定義為

Mh(x)=1/k∑xi∈Sh(xi-x)(7)

其中:Sh是一個半徑為h的高維球區域，滿足以下關系的y點的集合。

Sh(x)≡{y: (y-x)T(y-x)≤h2}(8)

其中:k表示在這n個樣本點xi中，有k個點落入Sh區域中。

X代表一個d維的歐氏空間，x是該空間中的一個點，用一列向量表示。x的模‖x‖2=xTx。R表示實數域。如果一個函數K:X→R存在一個剖面函數k:[0，∞]→R，即

K(x)=k(‖x‖2)(9)

并且滿足:a)k是非負的;b)k是非增的，即如果a

M(x)≡∑ni=1GH(xi-x)w(xi)(xi-x)/∑ni=1GH(xi-x)w(xi)(10)

其中:GH(xi-x)=|H|-1/2G(H-1/2(xi-x))，G(x)是一個單位核函數，H是一個正定的對稱d×d矩陣，一般稱之為帶寬矩陣。w(xi)≥0是一個賦給采樣點xi的權重在實際應用的過程中，帶寬矩陣H一般被限定為一個對角矩陣H=diag[h21，…，h2d]，甚至更簡單地被取為正比于單位矩陣，即H=h2I。由于后一形式只需要確定一個系數h，在MS中常常被采用，本文也采用這種形式，則GH記為G，則式(10)可改寫為

Mh(x)=mh(x)-x(11)

mh(x)=[∑ni=1G((xi-x)/h)w(xi)xi]/[∑ni=1G((xi-x)/h)w(xi)](12)

給定一個初始點x、核函數G(X)、 容許誤差ε，MS算法循環地執行下面三步，直至結束條件滿足:

(a)計算mh(x);

(b)把mh(x)賦給x;

(c)若‖mh(x)-x‖<ε，結束循環;否則繼續執行(a)。

2.2 改造高斯核函數的聚類

通過2.1節的推導可知，核函數G(X)的確定對聚類影響較大，常采用如式(13)的單位高斯核函數。s0、t0是核函數窗口中心像素坐標，s、t是核函數窗口內像素的坐標。

N(x)=e-[(s-s0)2+(t-t0)2](13)

結合本文改進的二維直方圖的構造方法，對非噪聲子圖對應的區域I和噪聲子圖對應的區域Ⅱ采用不同的高斯核函數。改造后的高斯核函數如式(14)的橫截面不再是圓形，而是橢圓形。

N(x)=e-[(s-s0)2/a2+(t-t0)2/b2](14)

對非噪聲子圖對應的區域I中的元素聚類時，由于像素自身的灰度和鄰域像素相近，自身的灰度占更重要的權重，即主要按照S軸的取值進行聚類，因為改良的核函數采用如式(14)的橢圓形，ab，窗口內更多的點T軸的取值相近，保證了更高的權重按照T軸取值聚類，從而可以起到分割圖像的平滑抗噪效果。聚類結果示意圖如圖3所示。

3 實驗結果

對區域I、Ⅱ采用不同形狀的核函數進行聚類，抗噪性較原有算法有了明顯提高。圖4為不同算法對噪聲污染圖像的分割效果。(a)為測試圖片原圖，背景灰度為100，圓形目標灰度為158;(b)是(a)加入了N(0，400)的高斯噪聲;(c)～ (h)對應的是Otsu法、二維最大熵、二維FCM、二維Otsu、快速二維Otsu法[5]和本文方法的效果對比。

對比可以看出，快速二維Otsu法和本文方法優于前四種方法。其中，二維Otsu法對于目標區域的分割較本文方法更準確，快速二維Otsu對于背景區域分割較本文方法更準確，但綜合背景和目標的分割準確性，本文方法有更明顯的優勢。

4 結束語

二維直方圖的方法綜合了像素的灰度信息和空間鄰域信息，二維的閾值分割算法比一維更為準確，對噪聲污染的圖像二維方法更具優越性，但仍存在一些問題。針對這些問題，本文的主要創新體現在以下幾個方面:

a)重新設計了二維直方圖的構造方法，使二維直方圖不僅兼顧了像素自身的灰度和鄰域灰度，還考慮了像素噪聲的判斷信息，將原圖像根據這些信息分為噪聲子圖和非噪聲子圖。

b)針對不同的圖像都可以計算獲得每幅圖像的閾值threshold，繼而可以準確建立和劃分二維直方圖對應的噪聲子圖區域和非噪聲子圖區域。

c)對應二維直方圖的兩類子圖采用不同形狀的核函數聚類。橢圓形的位置和角度可以起賦予S、T不同權值的作用，使邊緣和平坦區的分割更為準確，噪聲區的平滑效果更好。采用均值漂移算法進行聚類分割，速度較傳統方法也有所提高。

實驗部分體現了本文方法的優勢，但部分問題仍可以繼續改進和鉆研，如設計更快速可靠的分割算法，對復雜圖像均值漂移聚類中心的個數問題，式(14)中a、b的選取還不具備自適應性，這些都可在未來的工作中作進一步探索和完善。

參考文獻:

[1]ZHANG Jun-ping， SUN Wen-bang， TANG Wen-yan. Image change detection algorithm based on clustering characteristic of 2-D histograme[C]// Proc of IEEE International Conference on Geoscience and Remote Sensing. [S.l.]:IEEE Press， 2006:767-770.

[2]WU Jin， LI Juan， LIU Jian， et al. Infrared image segmentation via fast fuzzy C-means with spatial information[C]// Proc of IEEE International Conference on Robotics and Biomimetics. [S.l.]:IEEE Press， 2004:742-745.

[3]WANG Ying-hai， JIANG Xing-hong， LI Zheng-ming. Research on the method of intelligent robot visual recognition and positioning[C]// Proc of IEEE International Conference on Networking， Sensing and Control.[S.l.]:IEEE Press，2008:916-919.

[4]HUANG Ting-lei， BAI Xue. An improved algorithm for medical image segmentation[C]// Proc of the 2nd International Conference on Genetic and Evolutionary Computing. [S.l.]:IEEE Press， 2008:289-292.

[5]汪海洋，潘德爐，夏德深. 二維Otsu自適應閾值選取算法的快速實現[J]. 自動化學報，2007， 33(9):968-970.

[6]杜曉晨，劉建平. 基于二維Otsu和遺傳算法的紅外圖像分割方法[J]. 紅外技術，2005， 27(1):66-69.

[7]WEI Kai-ping， ZHANG Tao， HE Bin. Detection of sand and dust storms from MERIS image using FE-Otsu alogrithm[C]// Proc of the 2nd International Conference on Bioinformatics and Biomedical Engineering. [S.l.]:IEEE Press，2008:3852-3855.

[8]KIM Y T. Contrast enhancement using brightness preserving bi-histogram equalization[J]. IEEE Trans on Consumer Electronics，1997， 43(1):1-8.

[9]閆敬文.數字圖像處理[M].北京:國防工業出版社，2007:82-83.