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

（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)的過分割問題，提出了一種改進(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é)果來看，該方法能有效地控制分水嶺算法的過分割問題。

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

1 分水嶺算法原理

分水嶺算法，也被稱為水線算法，20世紀(jì)70年代末由C.Digabel和H.Lantuejoul引入到圖像處理領(lǐng)域的，最初僅用于對(duì)簡單二值圖像的處理。但由于分水嶺算法的計(jì)算復(fù)雜度過高，所以一直沒有得到學(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é)的分割方法。其思想來源于地形學(xué)，顧名思義，就是根據(jù)分水嶺的構(gòu)成來考慮圖像的分割，采用地形學(xué)作為其描述方法。假設(shè)把圖像當(dāng)成是一幅地形地貌圖，圖像中我們可以利用灰度和地貌的相似性來研究圖像的灰度在空間上的變化。把圖像中的每個(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ù)匦瓮耆唤]在集水盆以下時(shí)，所有的水壩就構(gòu)成了分水嶺。這一過程可以用圖1來說明。

圖1 分水嶺示意圖

2 分水嶺算法存在的問題

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

如何解決分水嶺算法帶來的過分割問題，一直是眾多專家學(xué)者研究的熱點(diǎn)問題。杜嘯曉等人[3]提出了一種保持邊界的圖像分割方法，該方法引入了非線性擴(kuò)散的方法，即先對(duì)圖像進(jìn)行平滑去噪，從而有效地減少了梯度圖中的最小區(qū)域的個(gè)數(shù)，然后使用區(qū)域灰度相似性和層次融合方法，較好地解決了分水嶺算法中的過分割問題。這種方法能提供較為精確的區(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)檫@兩種方法能較好地消除分水嶺的過分割問題，以及圖像中包含的噪聲問題。另一種改進(jìn)是對(duì)原圖像進(jìn)行預(yù)處理，例如采用濾波方式，但它只能作為一種輔助工具，但是本質(zhì)上沒有對(duì)分水嶺算法起到實(shí)質(zhì)性的幫助。為了解決分水嶺的過分割問題，本文仍然使用標(biāo)記提取方法。在傳統(tǒng)的形態(tài)分割方法的基礎(chǔ)上，先對(duì)圖像采用形態(tài)學(xué)的方法求取梯度，并進(jìn)行梯度重建，以增強(qiáng)梯度圖像的對(duì)比度，然后對(duì)前景和背景分別進(jìn)行標(biāo)記提取，從而能抑制噪聲所引起的過分割。但是本文做的改進(jìn)是在原有的標(biāo)記提取方法上采用自適應(yīng)的標(biāo)記提取方法來提取內(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)行分水嶺變換，使過分割現(xiàn)象減輕，而且邊緣定位更加精確。具體的算法可以用圖2來表示。

圖2 本文算法流程圖

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

3.2.1 梯度計(jì)算

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

上式中，f（x,y）表示原始圖像，grad表示梯度運(yùn)算。由于梯度圖能較好地反映圖像的變化情況，在原圖像的梯度圖上進(jìn)行分水嶺變換能取得更好的效果，分割后的結(jié)果更加準(zhǔn)確。本文中采用形態(tài)學(xué)梯度的方法來求取梯度，因?yàn)樾螒B(tài)學(xué)梯度能使輸入圖像灰度級(jí)變化更大，與前面介紹過的采用模板求取梯度的方法相比，形態(tài)學(xué)梯度方法對(duì)邊緣的方向性依賴更小。最終的分水嶺變換將在被標(biāo)記圖像修改后的梯度圖像上進(jìn)行，以此獲得最終的分割結(jié)果。常見形態(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ū)域的過分割。由于圖像中包含有許多彼此連通但是大小不同的對(duì)象，為使得通過分水嶺變換后得到的低谷數(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)元素。

分水嶺分割通過從圖像中提取區(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)記概念的提出主要是為了控制分水嶺中的過度分割。由于在實(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ù)，能較好地抑制分水嶺的過分割現(xiàn)象。文獻(xiàn)[5]使用了一種H-minima標(biāo)記技術(shù)來提取標(biāo)記。H-minima變換是一種有效提取標(biāo)記的方法，H-minima變換的表達(dá)式如下：

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

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

從上面的實(shí)驗(yàn)圖可以看出，在原圖上直接運(yùn)用標(biāo)準(zhǔn)分水嶺變換，存在明顯的過分割現(xiàn)象，導(dǎo)致分割后的結(jié)果幾乎無意義。本文通過局部極大值平均值與極小值點(diǎn)集合方差計(jì)算出來的閾值來消除一些偽區(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)出來，即當(dāng)閾值不同時(shí)，經(jīng)過分水嶺計(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)從背景中分離出來，因此本文算法效果更好。

[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].中國圖象圖形學(xué)報(bào),2001,6（8）：755-759.

[4]盧官明.區(qū)域生長型分水嶺算法及其在圖像序列分割中的應(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]王國權(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é)研究生，研究方向：圖像處理。

覃華巧）