一種自適應(yīng)標(biāo)記分水嶺算法的研究

汪 梅，何高明，賀 杰，郭 慧，陳 佳

（1.2.3.5.梧州學(xué)院 計(jì)算機(jī)科學(xué)系，廣西 梧州 543002；

4.梧州學(xué)院 電子信息工程系，廣西 梧州 543002）

一種自適應(yīng)標(biāo)記分水嶺算法的研究

汪 梅1，何高明2，賀 杰3，郭 慧4，陳 佳5

（1.2.3.5.梧州學(xué)院 計(jì)算機(jī)科學(xué)系，廣西 梧州 543002；

4.梧州學(xué)院 電子信息工程系，廣西 梧州 543002）

介紹了分水嶺算法的基本概念和原理，針對(duì)分水嶺算法出現(xiàn)的過(guò)分割問(wèn)題，提出了一種改進(jìn)的標(biāo)記提取的分水嶺算法。該算法首先使用形態(tài)學(xué)梯度，并使用梯度重建技術(shù)，較好地增強(qiáng)了圖像對(duì)比度，同時(shí)使用改進(jìn)的標(biāo)記提取方法對(duì)區(qū)域最小值進(jìn)行標(biāo)定，使用分水嶺算法。從實(shí)驗(yàn)結(jié)果來(lái)看，該方法能有效地控制分水嶺算法的過(guò)分割問(wèn)題。

分水嶺；標(biāo)記提取；形態(tài)學(xué)

1 分水嶺算法原理

分水嶺算法，也被稱為水線算法，20世紀(jì)70年代末由C.Digabel和H.Lantuejoul引入到圖像處理領(lǐng)域的，最初僅用于對(duì)簡(jiǎn)單二值圖像的處理。但由于分水嶺算法的計(jì)算復(fù)雜度過(guò)高，所以一直沒(méi)有得到學(xué)者們的重視。分水嶺思想的真正發(fā)展始于20世紀(jì)90年代初，建立在LucVincent和S.Beucher以及同PierreSoille的共同研究的基礎(chǔ)上，Vincent對(duì)原始分水嶺算法的改進(jìn)使它的計(jì)算速度提高了一個(gè)數(shù)量級(jí)，其思想及實(shí)現(xiàn)至今仍是廣大學(xué)者關(guān)注的研究熱點(diǎn)。分水嶺變換的經(jīng)典實(shí)現(xiàn)算法有很多[1-2]，分水嶺分割算法是一種基于拓?fù)淅碚摵蛿?shù)學(xué)形態(tài)學(xué)的分割方法。其思想來(lái)源于地形學(xué)，顧名思義，就是根據(jù)分水嶺的構(gòu)成來(lái)考慮圖像的分割，采用地形學(xué)作為其描述方法。假設(shè)把圖像當(dāng)成是一幅地形地貌圖，圖像中我們可以利用灰度和地貌的相似性來(lái)研究圖像的灰度在空間上的變化。把圖像中的每個(gè)像素的灰度值當(dāng)成地形中的高度，并用這個(gè)灰度值代表該點(diǎn)在地形中的海拔。如果灰度值大，則海拔高。另外用集水盆表示圖像中局部極小區(qū)域，即灰度的極小值。在采用分水嶺方法進(jìn)行分割時(shí)，首先確定這個(gè)地形圖中的所有局部極小點(diǎn)，并在每個(gè)局部極小點(diǎn)處，或者是盆地的最低處刺穿一個(gè)小孔，使水慢慢上升，隨著時(shí)間的變化，水將勻速地浸入一個(gè)集水盆中。為了防止兩個(gè)不同的局部最小點(diǎn)對(duì)應(yīng)的聚水盆匯合到一起，需要在它們的相接處建筑起一個(gè)水壩，當(dāng)?shù)匦瓮耆唤](méi)在集水盆以下時(shí)，所有的水壩就構(gòu)成了分水嶺。這一過(guò)程可以用圖1來(lái)說(shuō)明。

圖1 分水嶺示意圖

2 分水嶺算法存在的問(wèn)題

標(biāo)準(zhǔn)的分水嶺變換算法是建立在梯度圖像區(qū)域極小值基礎(chǔ)上進(jìn)行的分割，由于圖像噪聲或其他原因的影響，在實(shí)際應(yīng)用場(chǎng)合中，梯度圖像中會(huì)出現(xiàn)很多的區(qū)域極小值，進(jìn)而造成過(guò)分割現(xiàn)象。圖像分割的結(jié)果是要將圖像中感興趣的目標(biāo)區(qū)域分割出來(lái)，但過(guò)分割造成的后果卻往往使分割的結(jié)果變得毫無(wú)用處。因此，在實(shí)際應(yīng)用中，直接運(yùn)用標(biāo)準(zhǔn)的分水嶺變換算法往往難以得到滿意的分割結(jié)果。

如何解決分水嶺算法帶來(lái)的過(guò)分割問(wèn)題，一直是眾多專家學(xué)者研究的熱點(diǎn)問(wèn)題。杜嘯曉等人[3]提出了一種保持邊界的圖像分割方法，該方法引入了非線性擴(kuò)散的方法，即先對(duì)圖像進(jìn)行平滑去噪，從而有效地減少了梯度圖中的最小區(qū)域的個(gè)數(shù)，然后使用區(qū)域灰度相似性和層次融合方法，較好地解決了分水嶺算法中的過(guò)分割問(wèn)題。這種方法能提供較為精確的區(qū)域輪廓線。盧官明[4]提出的圖像分割方法，不是對(duì)梯度圖像進(jìn)行的分水嶺分割，而是直接將分水嶺運(yùn)用在原圖像上，避免了信息的丟失，并采用了分形隊(duì)列結(jié)構(gòu)對(duì)圖像進(jìn)行掃描，將此算法應(yīng)用在運(yùn)動(dòng)圖像上也有較好的效果。

3 自適應(yīng)標(biāo)記提取的分水嶺算法

3.1 算法描述

在對(duì)分水嶺算法的改進(jìn)算法中，標(biāo)記提取方法與區(qū)域合并方法目前被一些學(xué)者廣泛使用，因?yàn)檫@兩種方法能較好地消除分水嶺的過(guò)分割問(wèn)題，以及圖像中包含的噪聲問(wèn)題。另一種改進(jìn)是對(duì)原圖像進(jìn)行預(yù)處理，例如采用濾波方式，但它只能作為一種輔助工具，但是本質(zhì)上沒(méi)有對(duì)分水嶺算法起到實(shí)質(zhì)性的幫助。為了解決分水嶺的過(guò)分割問(wèn)題，本文仍然使用標(biāo)記提取方法。在傳統(tǒng)的形態(tài)分割方法的基礎(chǔ)上，先對(duì)圖像采用形態(tài)學(xué)的方法求取梯度，并進(jìn)行梯度重建，以增強(qiáng)梯度圖像的對(duì)比度，然后對(duì)前景和背景分別進(jìn)行標(biāo)記提取，從而能抑制噪聲所引起的過(guò)分割。但是本文做的改進(jìn)是在原有的標(biāo)記提取方法上采用自適應(yīng)的標(biāo)記提取方法來(lái)提取內(nèi)外標(biāo)記，并進(jìn)行梯度重建，避免了傳統(tǒng)的H-minima標(biāo)記提取方法中對(duì)于閾值的盲目選取，而本文改進(jìn)算法中能根據(jù)圖像的統(tǒng)計(jì)特征選取閾值。最后以形態(tài)梯度圖像的浮點(diǎn)活動(dòng)圖像進(jìn)行分水嶺變換，使過(guò)分割現(xiàn)象減輕，而且邊緣定位更加精確。具體的算法可以用圖2來(lái)表示。

圖2 本文算法流程圖

3.2 算法實(shí)現(xiàn)

3.2.1 梯度計(jì)算

由于通過(guò)分水嶺變換得到的圖像是輸入圖像的集水盆圖像，分水嶺也就是指集水盆之間的邊界點(diǎn)。顯然，分水嶺在圖像中對(duì)應(yīng)的是輸入圖像的極大值點(diǎn)。因此為得到圖像的邊緣信息，通常把梯度圖像作為輸入圖像，即

上式中，f（x,y）表示原始圖像，grad表示梯度運(yùn)算。由于梯度圖能較好地反映圖像的變化情況，在原圖像的梯度圖上進(jìn)行分水嶺變換能取得更好的效果，分割后的結(jié)果更加準(zhǔn)確。本文中采用形態(tài)學(xué)梯度的方法來(lái)求取梯度，因?yàn)樾螒B(tài)學(xué)梯度能使輸入圖像灰度級(jí)變化更大，與前面介紹過(guò)的采用模板求取梯度的方法相比，形態(tài)學(xué)梯度方法對(duì)邊緣的方向性依賴更小。最終的分水嶺變換將在被標(biāo)記圖像修改后的梯度圖像上進(jìn)行，以此獲得最終的分割結(jié)果。常見(jiàn)形態(tài)學(xué)邊緣檢測(cè)算子包含膨脹型、腐蝕型、膨脹腐蝕型。下面是對(duì)這幾種算子的介紹。

上面式（2）、式（3）、式（4）中，X為圖像集合，B為結(jié)構(gòu)元素，+為膨脹運(yùn)算符， I為腐蝕運(yùn)算符。

3.2.2 形態(tài)學(xué)重構(gòu)

在求得梯度圖后，如果直接采用分水嶺算法，梯度圖中每個(gè)獨(dú)立的局部谷底都被劃分為不同區(qū)域，這樣會(huì)導(dǎo)致圖像區(qū)域的過(guò)分割。由于圖像中包含有許多彼此連通但是大小不同的對(duì)象，為使得通過(guò)分水嶺變換后得到的低谷數(shù)目最小，即區(qū)域極小值最少，通常的做法是對(duì)圖像進(jìn)行變換，使我們感興趣的目標(biāo)對(duì)象的對(duì)比度達(dá)到最大，即對(duì)比度增強(qiáng)。一個(gè)常用的方法是應(yīng)用高帽（top－h(huán)at）變換和低帽（bottom-hat）變換。Top-hat變換定義為：

其中·為形態(tài)學(xué)閉運(yùn)算，X為原圖像，B為結(jié)構(gòu)元素。

分水嶺分割通過(guò)從圖像中提取區(qū)域極小值，進(jìn)而確定該極小值對(duì)應(yīng)的分界線。分界線反映的是圖像中強(qiáng)度劇烈變化的分界線，在提取區(qū)域極值時(shí)，通常先對(duì)圖像進(jìn)行對(duì)比度增強(qiáng)處理，以突出圖像中的明暗變化。圖像增強(qiáng)變換定義為：

3.2.3 自適應(yīng)的標(biāo)記提取方法

標(biāo)記概念的提出主要是為了控制分水嶺中的過(guò)度分割。由于在實(shí)際應(yīng)用中，標(biāo)記點(diǎn)的選取往往是從得到的區(qū)域極小值點(diǎn)中間選擇，但是由于噪聲的影響，為了能達(dá)到滿意的分割效果，需要消除因此產(chǎn)生的一些區(qū)域極小值點(diǎn)，采取的方法往往是對(duì)梯度圖像進(jìn)行修正或平滑等預(yù)處理。Soille提出的強(qiáng)制最小技術(shù)已經(jīng)被廣泛用于分水嶺分割的標(biāo)記提取[5]。而標(biāo)記提取方法的基本思想是對(duì)輸入圖像的梯度圖設(shè)置一個(gè)閾值，如果梯度值小于該閾值的點(diǎn)，則將該點(diǎn)作為標(biāo)記點(diǎn)，這樣可以減少分水嶺分割后的區(qū)域數(shù)，能較好地抑制分水嶺的過(guò)分割現(xiàn)象。文獻(xiàn)[5]使用了一種H-minima標(biāo)記技術(shù)來(lái)提取標(biāo)記。H-minima變換是一種有效提取標(biāo)記的方法，H-minima變換的表達(dá)式如下：

H-minima變換的原理是給定一個(gè)閾值h，通過(guò)與h比較，消除那些深度低于h的局部極小值，提取滿足條件的極小值，最終得到標(biāo)記圖像。這種方法的優(yōu)點(diǎn)是可以直接給定閾值，但這同時(shí)也是它的缺點(diǎn)，就是因?yàn)镠-minima方法給定的閾值是固定的，提取標(biāo)記后的圖像結(jié)果僅僅依賴于此預(yù)先設(shè)定的閾值，而沒(méi)有將集水盆尺度聯(lián)系起來(lái)。但是實(shí)際上，根據(jù)分水嶺算法的原理，圖像中的極小值點(diǎn)的深度為某區(qū)域極大值點(diǎn)與該極小值點(diǎn)之間的差值，而給定的閾值主要是用來(lái)限制由于灰度值的微小變化而引起的過(guò)度分割問(wèn)題，所以這個(gè)閾值應(yīng)該與該區(qū)域的極大值點(diǎn)和極小值點(diǎn)有聯(lián)系[6]。也就是說(shuō)可以根據(jù)極大值點(diǎn)和局部極小值點(diǎn)的相關(guān)特性來(lái)確定相應(yīng)的閾值。本文的做法如下。

1.找出梯度圖像中的極大值點(diǎn)與極小值點(diǎn)集合。根據(jù)梯度計(jì)算方法求取原圖像的梯度圖像，并找出每個(gè)區(qū)域的極大值與極小值，構(gòu)成兩個(gè)集合Imax和Imin。

2.求出極大值點(diǎn)集合的平均值與極小值點(diǎn)集合的平均值，以及其方差。分別求出Imax和Imin的平均值與方差。

3.消除較弱的極大值點(diǎn)，并重新計(jì)算均值，主要方法是如果這些極大值點(diǎn)集合中有灰度值小于其均值的，就將其消除，再用此均值與方差計(jì)算得到最終閾值。通過(guò)確定的閾值能將某區(qū)域中的極大值與極小值聯(lián)系起來(lái)，并且能限制過(guò)度分割問(wèn)題。

4.利用第3步得到的閾值，再采用H-minima標(biāo)記提取方法對(duì)圖像進(jìn)行標(biāo)記，得到標(biāo)記圖像。

使用上述方法后再進(jìn)行分水嶺算法時(shí)，首先對(duì)梯度圖中的區(qū)域極小值進(jìn)行標(biāo)定，然后以這個(gè)極小值作為山谷，搜索這個(gè)極小值的鄰域像素點(diǎn)，如果其灰度值相近，則把它設(shè)置為背景或前景。如果相鄰的兩個(gè)極小值點(diǎn)所對(duì)應(yīng)的區(qū)域像素相遇，就將這兩個(gè)點(diǎn)當(dāng)成區(qū)域輪廓的像素點(diǎn)。使用此方法進(jìn)行迭代，分割結(jié)束時(shí)所有的區(qū)域極小值對(duì)應(yīng)的輪廓像素點(diǎn)全部被確定和標(biāo)記。

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本章算法的可行性，本實(shí)驗(yàn)選取了幾幅有代表性的圖像，用Matlab進(jìn)行仿真，下頁(yè)圖3是實(shí)驗(yàn)結(jié)果圖。

圖3 實(shí)驗(yàn)結(jié)果分析圖

從上面的實(shí)驗(yàn)圖可以看出，在原圖上直接運(yùn)用標(biāo)準(zhǔn)分水嶺變換，存在明顯的過(guò)分割現(xiàn)象，導(dǎo)致分割后的結(jié)果幾乎無(wú)意義。本文通過(guò)局部極大值平均值與極小值點(diǎn)集合方差計(jì)算出來(lái)的閾值來(lái)消除一些偽區(qū)域，并獲得更加適量的區(qū)域。該文獻(xiàn)中預(yù)先設(shè)定了進(jìn)行標(biāo)記提取前的閾值T為50，當(dāng)然這一數(shù)值可以改變，本文分別選取了閾值50、80即200進(jìn)行實(shí)驗(yàn)，該算法的不足也體現(xiàn)出來(lái)，即當(dāng)閾值不同時(shí)，經(jīng)過(guò)分水嶺計(jì)算后結(jié)果也不同，閾值越大，分割區(qū)域越大，區(qū)域數(shù)目越少，但是細(xì)節(jié)體現(xiàn)得越不明顯。而本文算法中，不用預(yù)先設(shè)定閾值，在標(biāo)記提取時(shí)，會(huì)自動(dòng)根據(jù)圖像的特性統(tǒng)計(jì)出閾值。和文獻(xiàn)[7]的方法對(duì)比，本文算法得到的結(jié)果圖中偽區(qū)域個(gè)數(shù)更少，能較為正確地將目標(biāo)從背景中分離出來(lái)，因此本文算法效果更好。

[1]廖毅.基于顯著性分析的分水嶺分割算法[J].系統(tǒng)仿真學(xué)報(bào),2007,19（2）：232-237.

[2]Gonzalez C R,Woods R E．Digital Image Processing[M].Seconded ition.Beijing：Publishing House of Electronics Industry,2002：618-626.

[3]杜嘯曉,楊新,施鵬飛.一種新的基于區(qū)域和邊界的圖象分割方法[J].中國(guó)圖象圖形學(xué)報(bào),2001,6（8）：755-759.

[4]盧官明.區(qū)域生長(zhǎng)型分水嶺算法及其在圖像序列分割中的應(yīng)用[J].維普資訊,2000,20（3）：51-54.

[5]Sonka M,H lavacV Boyle R.Image processing,analysi,and machine vision（2nded）[M].Books／Cole Publishing,1999：576-577.

[6]譚洪波.基于自適應(yīng)標(biāo)記提取的分水嶺彩圖分割算法[J].計(jì)算機(jī)工程,2010,36（19）：229-231.

[7]王國(guó)權(quán),周小紅.基于分水嶺算法的圖像分割方法研究[J].計(jì)算機(jī)仿真,2009,26（5）：255-258.

O243

A

1673-8535（2012）01-0059-06

2011－12-08

汪梅（1981-），女，湖北洪湖人，梧州學(xué)院計(jì)算機(jī)科學(xué)系講師，廣西師范大學(xué)研究生，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)、圖像處理。

何高明（1980-），男，湖北通城人，梧州學(xué)院計(jì)算機(jī)科學(xué)系講師，廣西師范大學(xué)研究生，研究方向：嵌入式系統(tǒng)。

賀杰（1982-），男，湖南桃江人，梧州學(xué)院計(jì)算機(jī)科學(xué)系講師，廣西師范大學(xué)研究生，研究方向：圖像處理。

郭慧（1981-），女，廣西梧州人，梧州學(xué)院電子信息工程系講師，廣西師范大學(xué)研究生，研究方向：圖像處理。

陳佳（1982-），女，重慶大足人，梧州學(xué)院計(jì)算機(jī)科學(xué)系講師，廣西師范大學(xué)研究生，研究方向：圖像處理。

覃華巧）