凌財(cái)進(jìn)，曾 婷，張 超，黑霞麗

(1.河源職業(yè)技術(shù)學(xué)院 電子信息工程學(xué)院，廣東 河源 517000 2.美國(guó)特拉華州立大學(xué) 工程學(xué)院，美國(guó) 特拉華 19904)

?

一種改進(jìn)的基于分水嶺的圖像分割算法

凌財(cái)進(jìn)1，2，曾 婷1，張 超2，黑霞麗2

(1.河源職業(yè)技術(shù)學(xué)院 電子信息工程學(xué)院，廣東 河源 517000 2.美國(guó)特拉華州立大學(xué) 工程學(xué)院，美國(guó) 特拉華 19904)

針對(duì)分水嶺算法過(guò)分割現(xiàn)象，提出一種綜合分水嶺算法、中值過(guò)濾算法和歸一化割算法的改進(jìn)算法；該算法首先應(yīng)用改進(jìn)型的中值過(guò)濾算法對(duì)圖像進(jìn)行適當(dāng)?shù)某?；然后通過(guò)分水嶺變換對(duì)圖像進(jìn)行了初步分割，最后使用歸一化割算法進(jìn)行圖像精度分割；算法集合了分水嶺算法、中值過(guò)濾算法及歸一化割算法的優(yōu)點(diǎn)，既較好地解決了分水嶺算法中過(guò)度分割的問(wèn)題，又降低了歸一化割算法的時(shí)間復(fù)雜度；實(shí)驗(yàn)結(jié)果表明該算法是一種切實(shí)可行的圖像分割方法。

圖像分割；分水嶺；歸一化割；中值過(guò)濾

0 引言

圖像分割是圖像分析與模式識(shí)別中的一個(gè)重要問(wèn)題，分割目的就是將圖像根據(jù)一定的規(guī)則劃分為若干個(gè)有意義的區(qū)域，從而實(shí)現(xiàn)圖像高層次的分析和理解。圖像分割的質(zhì)量是圖像處理中的一個(gè)經(jīng)典難題，多年來(lái)眾多學(xué)者進(jìn)行了廣泛和深入的研究。

分水嶺(watershed)法是一種基于數(shù)學(xué)形態(tài)學(xué)發(fā)展起來(lái)的一種圖像分割方法。分水嶺算法對(duì)微弱邊緣具有良好的響應(yīng)，能得到封閉連續(xù)邊緣和較低的時(shí)間復(fù)雜度。傳統(tǒng)的分水嶺算法因?qū)υ肼暶舾卸a(chǎn)生過(guò)分割現(xiàn)象，使得感興趣目標(biāo)淹沒(méi)其中。業(yè)界認(rèn)為傳統(tǒng)的分水嶺算法不能單獨(dú)應(yīng)用于實(shí)踐。因此，本文提出一種融合中值過(guò)濾、分水嶺變換和歸一化割算法優(yōu)點(diǎn)的圖像分割方法，即3IN1-Cuts算法。

1 相關(guān)研究

上述我們提到傳統(tǒng)分水嶺算法存在著過(guò)分割缺點(diǎn)，因此不能單獨(dú)應(yīng)用于實(shí)踐，于是學(xué)者們進(jìn)行了實(shí)踐與研究，提出了各種改進(jìn)型分水嶺算法，不少已成功應(yīng)用于實(shí)踐和生產(chǎn)中。 文獻(xiàn)[1]中Nguyen 和Worring等人提出能量驅(qū)動(dòng)的Water snakes算法，新算法對(duì)邊界定位準(zhǔn)確度和連續(xù)性有較好的改進(jìn)，但無(wú)法解決過(guò)分割問(wèn)題；文獻(xiàn)[2]中來(lái)自加拿大的Demin Wang提出了應(yīng)用梯度公式對(duì)圖像進(jìn)行預(yù)處理以消除噪音，效果并不理想；文獻(xiàn)[3]崔明等人通過(guò)閾值標(biāo)志法，提出一種基于區(qū)域融合的改進(jìn)型多尺度的快速分水嶺變換算法，并將改進(jìn)分水嶺變換中獲得的多尺度信息作為評(píng)價(jià)邊界強(qiáng)度的指標(biāo)，該算法還是屬于閾值法與分水嶺結(jié)合的范疇，由閾值決定了局限性；文獻(xiàn)[4]中Haris 等人提出通過(guò)區(qū)域合并來(lái)緩解過(guò)分割，但分水嶺變換產(chǎn)生大量區(qū)域，后續(xù)合并過(guò)程運(yùn)算量極大，影響了算法的效率；針對(duì)文獻(xiàn)[4]，也有學(xué)者提出采用對(duì)輸入圖像的梯度取閾值的方法來(lái)降低過(guò)分割，事實(shí)證明采用閾值的方法雖然能解決過(guò)分割問(wèn)題，但同時(shí)也使得圖像中的部分細(xì)節(jié)；文獻(xiàn)[5-6]提出采用分水嶺變換和圖論結(jié)合的分割方法，較好地解決了過(guò)分割問(wèn)題；文獻(xiàn)[7]陳忠和趙忠明通過(guò)一種叫PGF非線性濾波和快速多尺度合并算法有選擇地對(duì)分水嶺變換結(jié)果進(jìn)行合并，實(shí)驗(yàn)結(jié)果表明該算法能獲得良好的分割效果，但沒(méi)從根本上解決過(guò)分割，還是分割后的合并。

從文獻(xiàn)和實(shí)踐中我們推斷，要從根本上解決傳統(tǒng)分水嶺過(guò)分割問(wèn)題，或許應(yīng)盡量減少分割而不是分割后再大量合并。因此，我們認(rèn)為從根本上解決過(guò)分割，主要解決3個(gè)問(wèn)題：1)在不影響分割效果的前提下，分割前盡量減少或抑制噪聲和細(xì)密紋理的影響；2)合理降低區(qū)域數(shù)量，降低運(yùn)算；3)提高算法適用的魯棒性，避免區(qū)域合并或減小合并難度和復(fù)雜度。 因此，針對(duì)問(wèn)題我們提出了一種結(jié)合中值過(guò)濾、分水嶺變換和歸一化割的長(zhǎng)處的圖像分割方法(3IN1-Cuts)，最后分類器根據(jù)提取的圖像特征進(jìn)行相應(yīng)的分類，從而達(dá)到識(shí)別效果[4-5]。

2 相關(guān)理論和推導(dǎo)

在圖像分割的算法中，中值過(guò)濾處理方法、分水嶺分割法和歸一化割法是目前常用的工具，并且它們各自有自己的優(yōu)點(diǎn)和缺陷，下面簡(jiǎn)單介紹相關(guān)理論和其推導(dǎo)過(guò)程。

2.1 中值濾波

中值濾波由Turky在1971年提出，最初用于時(shí)間序列分析，后來(lái)被用于圖像處理，并在去噪復(fù)原中取得了較好的效果。中值濾波器基本原理是把圖像或序列中心點(diǎn)位置的值用該域的中值替代，具有運(yùn)算簡(jiǎn)單、速度快、除噪效果好等優(yōu)點(diǎn)[9]。通過(guò)二維滑動(dòng)模板值濾波輸出為：

g(x,y)=med{f(x-k,y-l),k∈w,l∈w}

其中：f(x,y)，g(x,y)分別表示原始圖像和處理后圖像。傳統(tǒng)的中值濾波算法計(jì)算效率低，要真正在實(shí)踐中應(yīng)用，需對(duì)其進(jìn)行改進(jìn)，提高效果和速度。文章第四部分提出使用改進(jìn)算法進(jìn)行快速除噪。

2.2 分水嶺算法

分水嶺分割算法是一種基于拓?fù)淅碚摰臄?shù)學(xué)形態(tài)學(xué)的分割方法，算法的設(shè)計(jì)思路是把圖像的像素灰度值與地表海拔高度對(duì)應(yīng)起來(lái)，因此“海拔”高度范圍是[0，255]；每一個(gè)區(qū)域局部極小值及其影響區(qū)域稱為集水盆，而集水盆的邊界則形成分水嶺[8-10]。分水嶺比較經(jīng)典的實(shí)現(xiàn)方法有模擬降水過(guò)程和漲水過(guò)程，不同的方法實(shí)現(xiàn)思路和效果各有差別。其中，一個(gè)經(jīng)典計(jì)算方法是Vincent L和Pierre S提出[11]的，在該算法屬于漲水過(guò)程模擬類型，此計(jì)算方法分兩個(gè)步驟，分別是排序過(guò)程和淹沒(méi)過(guò)程。該算法中主要借用了分水嶺算法的物體輪廓線的封閉性和精確性，對(duì)圖像進(jìn)行初步分割，得到封閉且精確的集水盆圖像，并作為歸一化割流程的輸入。

2.3 歸一化割算法

歸一化割(Normalized Cut )法是1997 年由J.Shi 與J.Malik 提出的無(wú)人監(jiān)督圖像分割技術(shù), 用于解決圖像分割與聚類中的問(wèn)題[5]。算法基本思路是將圖像映射為無(wú)向帶權(quán)圖G，圖的節(jié)點(diǎn)V由像素構(gòu)成，圖的邊權(quán)值即為像素之間的相似度，利用最優(yōu)割集準(zhǔn)則對(duì)圖進(jìn)行劃分，從而得到圖像的最優(yōu)劃分[5]。對(duì)于一幅輸入的原始圖像或一個(gè)特征點(diǎn)集F建立一個(gè)帶權(quán)的無(wú)向圖G和節(jié)點(diǎn)V，關(guān)系E，則有G=(V,E)。假設(shè)圖G可以通過(guò)刪去某些邊，將其分為兩個(gè)非連接性的點(diǎn)集A,B，即產(chǎn)生兩個(gè)新的子圖，由圖論定義可知：A∪B=V,A∩B=φ，這兩個(gè)點(diǎn)集之間的不相似程度可以定義為原先連接G圖的兩部分而現(xiàn)在被刪去的所有邊的總和，圖的分割過(guò)程如圖1所示，

圖1 歸一化割算法示意圖

結(jié)合圖論中的“割”的定義，以上描述可以用數(shù)學(xué)表達(dá)為：

字母i和j分別表示兩點(diǎn)，w(i,j)表示連接點(diǎn)i和點(diǎn)j的邊的權(quán)值，也是兩點(diǎn)間的相似度。 由割的定義公式可知，割與對(duì)應(yīng)的割邊的數(shù)目成比例，所以可以推導(dǎo)出新的不同組之間的不相似度量，即歸一化割：

(3)

其中:assoc(A,V),assoc(B,V)分別表示A和B中的點(diǎn)與圖中所有點(diǎn)之間總的聯(lián)系程度。根據(jù)同一組內(nèi)的相似性可推導(dǎo)組內(nèi)相似性函數(shù)Nassoc:

(4)

Assoc(A,A)表示A中所有邊的權(quán)和總和，Assoc(B,B)同理。由公式(3)、(4)得：

NCut(A,B)=2-Nassoc(A,B)

(5)

從公式(5)可知，在圖的劃分算法中，不同分組之間總體最小不相似性(NCut)與同一個(gè)組內(nèi)部總體最大相似性(Nassoc)存在線性關(guān)系。因此，通過(guò)圖像分割問(wèn)題轉(zhuǎn)換為圖的劃分問(wèn)題，通過(guò)以上操作從而可以完成對(duì)圖像的分割。

3 本文算法

3.1 3IN1-Cuts算法概述

3IN1-Cuts算法即中值過(guò)濾算法、分水嶺算法和歸一化割算法三者優(yōu)點(diǎn)相結(jié)合的一個(gè)分割算法。這是為解決分水嶺算法的過(guò)分割問(wèn)題，提出一種綜合的改進(jìn)算法。算法第一步是利用中值濾波方法對(duì)圖像進(jìn)行去噪，并保持照片細(xì)節(jié)和邊緣，以減少噪聲對(duì)圖像初次分割結(jié)果的影響；第二步利用了分水嶺算法對(duì)微弱邊緣具有良好的響應(yīng)并保證其連續(xù)封閉，能為圖像分析提供封閉的集水盆的優(yōu)點(diǎn)，對(duì)去噪后的圖像進(jìn)行分水嶺變換，得到輸入圖像的集水盆，實(shí)現(xiàn)圖像的初步分割；最后，根據(jù)初步分割得到的結(jié)果建立簡(jiǎn)化的無(wú)向網(wǎng)絡(luò)圖G，應(yīng)用歸一化割算法在區(qū)域與區(qū)域之間進(jìn)行精細(xì)的分割，使得算法適應(yīng)性廣，提高算法的魯棒性。算法主要框架如圖2所示，下面就3個(gè)主要過(guò)程進(jìn)行分析。

圖2 算法主要框架

3.2 采用中值過(guò)濾進(jìn)行預(yù)處理

1)分割前的準(zhǔn)備工作，包括彩色圖像轉(zhuǎn)換工作和噪聲消除工作。灰度圖像計(jì)算分析不僅計(jì)算速度快，而且計(jì)算誤差少，因此本文把彩色圖像轉(zhuǎn)為灰度圖像進(jìn)行分析和計(jì)算。一般彩色與灰度轉(zhuǎn)換由公式(6)實(shí)現(xiàn)，為避免公式(6)三次的浮點(diǎn)數(shù)運(yùn)算消耗時(shí)間大，因此先放大倍數(shù)再通過(guò)移位來(lái)縮小相應(yīng)倍數(shù)，即公式(7)：

Gray=0299R+0.587G+0.114B

(6)

Gray=(77R+151G+28B)shr8

(7)

2)除噪運(yùn)算?？紤]傳統(tǒng)的中值過(guò)濾排序耗時(shí)多，本文采取了高速排序的方法，對(duì)一個(gè)區(qū)域內(nèi)的像素排序同步進(jìn)行，從而進(jìn)行快速過(guò)濾。在不破壞區(qū)域重要輪廓與圖像細(xì)節(jié)的的前提下采用改進(jìn)后的中值濾波算法來(lái)消除部分噪聲，并對(duì)原始圖像的梯度圖進(jìn)行開(kāi)閉重建運(yùn)算，去除了噪聲。其中，中值濾波運(yùn)算中權(quán)系數(shù)矩陣模板W為：

(8)

3.3 利用分水嶺變換進(jìn)行初步分割

分水嶺第一步是求解每個(gè)相素對(duì)應(yīng)的梯度值，設(shè)f(x,y)表示經(jīng)過(guò)灰度變換和中值過(guò)濾后圖像的像素，由像素計(jì)算梯度值grad(x,y)，計(jì)算方法如下：

令M1,M2,…,Mi為圖像grad(x,y)的局部最小值點(diǎn)的坐標(biāo)的集合，令G(Mi)為位于與局部最小值點(diǎn)坐標(biāo)的集合，相應(yīng)區(qū)域的Mi點(diǎn)的集合在相聯(lián)系的匯水盆地內(nèi)。假設(shè)min和max分別代表g(x,y)的最小值和最大值，同時(shí)令T[n]為坐標(biāo)(s,t)的集合，其中g(shù)(s,t)

(10)

(11)

在幾何上，T[n]是g(x,y)中的點(diǎn)的坐標(biāo)集合，集合中的點(diǎn)均位于平面g(x,y)=n的下方，計(jì)算是個(gè)不斷迭代的過(guò)程，經(jīng)過(guò)比較與排隊(duì)從而完成梯度圖像的排序。

通過(guò)分水嶺變換得到的是經(jīng)過(guò)中值過(guò)濾圖像的集水盆；接著，根據(jù)集水盆與集水盆之間的關(guān)系得到各區(qū)域的分水嶺，即相應(yīng)區(qū)域內(nèi)的圖像極大值點(diǎn)；此外，為得到圖像的邊緣信息，需構(gòu)造梯度值并把梯度圖像作為計(jì)算的輸入；最后，迭代計(jì)算得到較好的圖像邊界信息，為實(shí)驗(yàn)第三步即歸一化割進(jìn)行精細(xì)分割提供了可能。

3.4 采用歸一化割精細(xì)分割

di表示點(diǎn)i與其他點(diǎn)之間的聯(lián)系程度，因此，NCut 可以重寫成如下

設(shè)D=diag(d1,d2,…,dN)，W是N×N的對(duì)稱矩陣, 且W(i,j)=wij。 這樣尋找全局最優(yōu)值簡(jiǎn)化為：

(13)

假設(shè)y為實(shí)值，則公式可以通過(guò)廣義特征值問(wèn)題對(duì)公式(13)求解：

(14)

由指示向量x的決定了變量y。公式(14)可以寫成規(guī)范特征值問(wèn)題：

(15)

該特征值問(wèn)題的對(duì)應(yīng)具有第二個(gè)最小特征值。同理可求得第三小特征值向量，然后采用遞歸逐個(gè)求解，從而完成圖像的分割。

3.5 本文算法實(shí)現(xiàn)步驟

本文算法實(shí)現(xiàn)主要過(guò)程包括12個(gè)步驟，如表1所示。

表1 3IN1-Cuts算法實(shí)現(xiàn)步驟

4 實(shí)驗(yàn)結(jié)果與性能分析

本實(shí)驗(yàn)環(huán)境為W541型移動(dòng)工作站，處理器為IntelCorei7-4810MQ，內(nèi)存是16G，固態(tài)硬盤256G，軟件環(huán)境VisualC++ 2015，為了驗(yàn)證上述算法的有效性， 實(shí)驗(yàn)對(duì)取自美國(guó)加州大學(xué)伯克利分校電子圖像分割圖庫(kù)中的標(biāo)準(zhǔn)圖像50 幅進(jìn)行了測(cè)試。其中，圖3中的圖像規(guī)格都是481×321，其中(a)為圖庫(kù)編號(hào)119082的原始圖像， (b)、(c)和(d)分別是傳統(tǒng)分水嶺、歸一化割算法及本文算法(3IN1-Cuts)的分割結(jié)果。從圖3四幅圖像的實(shí)驗(yàn)結(jié)果，可以明顯得到本文算法(3IN1-Cuts)的分割效果比傳統(tǒng)分水嶺和歸一化割的結(jié)果要好得多。

圖3 本文算法與傳統(tǒng)算法實(shí)驗(yàn)比較

此外，我們還與分水嶺的部分文獻(xiàn)中提到的改進(jìn)算法進(jìn)行了比較，圖4中的圖像規(guī)格是481×321，(a)為圖庫(kù)編號(hào)42049的原始圖像，圖(b)、(c)和(d)分別是文獻(xiàn)[3]、文獻(xiàn)[5]和本文算法的分割結(jié)果。顯然，文獻(xiàn)[3]算法因閾值導(dǎo)致圖片細(xì)節(jié)丟失，從圖4四幅圖像的實(shí)驗(yàn)結(jié)果，可以明顯得到本文算法(3IN1-Cuts)的分割效果比文獻(xiàn)[3]和文獻(xiàn)[5]的分割結(jié)果要好。

圖4 本文算法與文獻(xiàn)算法實(shí)驗(yàn)比較

此外，我們還對(duì)相應(yīng)的分割時(shí)間進(jìn)行了對(duì)比，以編號(hào)為119082的圖像為例，具體如表2所示。

顯然，除了無(wú)實(shí)用價(jià)值的傳統(tǒng)分水嶺算法外，3IN1-Cuts算法在分割相同的圖像時(shí)消耗時(shí)間是最小的(圖像效果也是最好的，見(jiàn)圖3與圖4)，分別比文獻(xiàn)[3]和文獻(xiàn)[5]的改進(jìn)算法低1.13和0.12秒。從實(shí)驗(yàn)結(jié)果可推斷，利用改進(jìn)后的中值過(guò)濾算法適度除噪，利用分水嶺變換的優(yōu)點(diǎn)進(jìn)行初步分割及歸一化割的穩(wěn)定性，能較好地整合了三者的優(yōu)點(diǎn)，不僅取得較好的分割效果，還在時(shí)間復(fù)雜度方面得到優(yōu)化。

表2 五算法耗時(shí)統(tǒng)計(jì)表

5 結(jié)論

本文針對(duì)傳統(tǒng)分水嶺算法過(guò)分割現(xiàn)象，提出一種基于分水嶺、中值過(guò)濾和歸一化割算法的綜合優(yōu)化算法，該算法綜合3種算法的優(yōu)勢(shì)，較好地解決分水嶺過(guò)分割問(wèn)題，提高了分水嶺算法的分割精度，并且降低了歸一化割算法的時(shí)間復(fù)雜度。文章最后通過(guò)實(shí)驗(yàn)對(duì)比證明本文算法與同類改進(jìn)算法相比在分割效果和時(shí)間消耗方面取得了較好的效果。

[1]NguyenHT,WorringM,BoomgaardRVD.Watersnakes:energy-drivenwatershedsegmentation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2003, 25(3):330-342.

[2]WangD.Amultiscalegradientalgorithmforimagesegmentationusingwatersheds[J].PatternRecognition, 1997, 30(12): 2043-2052.

[3] 崔 明, 孫守遷, 潘云鶴. 基于改進(jìn)快速分水嶺變換的圖像區(qū)域融合[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005,17(03)：546-552.

[4]HarisK,EfstratiadisSN.Hybridimagesegmentationusingwatershedsandfastregionmerging[J].IEEETransactionsonImageProcessing, 1998, 7(12): 1684-1698

[5] 楊衛(wèi)莉, 郭 雷. 基于分水嶺算法和圖論的圖像分割[J]. 計(jì)算機(jī)工程與應(yīng)用, 2007, 43(7):28-30.

[6] 馮 林, 孫 燾, 吳振宇, 等. 基于分水嶺變換和圖論的圖像分割方法[J]. 儀器儀表學(xué)報(bào), 2008,29(3):649-653.

[7] 陳 忠, 趙忠明. 基于分水嶺變換的多尺度遙感圖像分割算法[J]. 計(jì)算機(jī)工程, 2006，12(23):186-187.

[8] 李海濱, 杜益福, 劉 彬. 基于圖割和分水嶺變換的圖像分割方法[J]. 燕山大學(xué)學(xué)報(bào), 2013, 37(2):143-147.

[9] 黃思博. 基于計(jì)算機(jī)視覺(jué)的異常駕駛行為檢測(cè)方法研究[D]. 廣州:華南理工大學(xué),2011.

[10] 高 欣. 基于彩色超聲圖像的血管內(nèi)膜中層厚度測(cè)量算法的研究[D].哈爾濱:哈爾濱工業(yè)大學(xué), 2010.

[11]VincentL,PierreS.Watershedsindigitalspaces:Anefficientalgorithmbasedonimmersionsimulations[J].IEEETrans.onPatternAnalysisandMachineIntelligence, 1991, 13(6):583-598.

An Image Segmentation Based on Improved Watershed

Ling Caijin1,2, Zeng Ting1, Zhang Chao2, Hei Xiali2

(1.College of Electronic Information Engineering, Heyuan Polytechnic, Heyuan 517000, China;2.College of Engineering, Delaware State University, Dover 19904, USA)

In order to overcome the shortcoming in over-segmentation of traditional watershed algorithm, this paper presented an improved image segmentation method, which is having performance advantage of watershed, median filter and normalized cuts. Firstly, an improved median filter is applied to reduce the image noise. Secondly, watershed transform is used to pre-segmentation. Finally, normalized cuts is employed to deal with detail segmentation. Segmentation experiments show that this method which contains good performance of the three steps, can not only effectively avoid the over-segmentation of watershed, but also reduce the time complexity of normalized cuts.

image segmentation; watershed; normalized cut; median filter

2015-08-27；

2015-09-25。

廣東省教育科學(xué)“十二五”規(guī)劃教育信息課題(13JXN035)，廣東省教育教學(xué)改革項(xiàng)目(201401232)，廣東省高職高專校長(zhǎng)聯(lián)席會(huì)議課題(GDXLHYB037) 。

凌財(cái)進(jìn)(1983-)，男，廣東河源人，碩士，講師，主要從事虛擬現(xiàn)實(shí)、圖像處理與識(shí)別、物聯(lián)網(wǎng)安全、計(jì)算機(jī)視覺(jué)等方向的研究。

黑霞麗(1981-),女,博導(dǎo),主要從事計(jì)算機(jī)視覺(jué)、物聯(lián)網(wǎng)安全方向的研究。

1671-4598(2016)06-0214-04

10.16526/j.cnki.11-4762/tp.2016.06.059

TP391.41

A