分水嶺的計(jì)算過程是一個(gè)迭代標(biāo)注過程。分水嶺比較經(jīng)典的計(jì)算方法是L. Vincent提出的。在該算法中，分水嶺計(jì)算分兩個(gè)步驟，一個(gè)是排序過程，一個(gè)是淹沒過程。首先對(duì)每個(gè)像素的灰度級(jí)進(jìn)行從低到高排序，然后在從低到高實(shí)現(xiàn)淹沒過程中，對(duì)每一個(gè)局部極小值在h階高度的影響域采用先進(jìn)先出(FIFO)結(jié)構(gòu)進(jìn)行判斷及標(biāo)注。
分水嶺變換得到的是輸入圖像的集水盆圖像，集水盆之間的邊界點(diǎn)，即為分水嶺。顯然，分水嶺表示的是輸入圖像極大值點(diǎn)。因此，為得到圖像的邊緣信息，通常把梯度圖像作為輸入圖像，即
g(x,y)=grad(f(x,y))={[f(x,y)-f(x-1,y)]2[f(x,y)-f(x,y-1)]2}0.5
式中，f(x,y)表示原始圖像，grad{.}表示梯度運(yùn)算。
分水嶺算法對(duì)微弱邊緣具有良好的響應(yīng)，圖像中的噪聲、物體表面細(xì)微的灰度變化，都會(huì)產(chǎn)生過度分割的現(xiàn)象。但同時(shí)應(yīng)當(dāng)看出，分水嶺算法對(duì)微弱邊緣具有良好的響應(yīng)，是得到封閉連續(xù)邊緣的保證的。另外，分水嶺算法所得到的封閉的集水盆，為分析圖像的區(qū)域特征提供了可能。
為消除分水嶺算法產(chǎn)生的過度分割，通?？梢圆捎脙煞N處理方法，一是利用先驗(yàn)知識(shí)去除無(wú)關(guān)邊緣信息。二是修改梯度函數(shù)使得集水盆只響應(yīng)想要探測(cè)的目標(biāo)。
為降低分水嶺算法產(chǎn)生的過度分割，通常要對(duì)梯度函數(shù)進(jìn)行修改，一個(gè)簡(jiǎn)單的方法是對(duì)梯度圖像進(jìn)行閾值處理，以消除灰度的微小變化產(chǎn)生的過度分割。即
g(x,y)=max(grad(f(x,y)),gθ)
式中，gθ表示閾值。
分水嶺分割技術(shù)是一種很優(yōu)秀的且得到了廣泛應(yīng)用的分割技術(shù)，從本質(zhì)上講，它屬于一種基于區(qū)域增長(zhǎng)的分割方法，但它得到的確是目標(biāo)的邊界，且是連續(xù)、閉合、但像素寬的邊界。在很多領(lǐng)域，這種分割技術(shù)都得到了廣泛的應(yīng)用，但分水嶺分割卻有一個(gè)致命的弱點(diǎn)，那就是容易產(chǎn)生過分割，對(duì)于噪聲和細(xì)密紋理非常敏感，使其常常產(chǎn)生嚴(yán)重的過分割結(jié)果。所以，針對(duì)這個(gè)問題，很多人提出了很多種改進(jìn)的分水嶺分割技術(shù)。綜合來講，大概也就三類。其一，分割預(yù)處理。既在應(yīng)用分水嶺分割之前對(duì)圖像進(jìn)行一些預(yù)處理，諸如除噪，求梯度圖像，形態(tài)學(xué)重建，標(biāo)記前景背景等等，一個(gè)目的，減少小的積水盆，從而減少過分割區(qū)域的數(shù)量。其二，分割后處理。既在應(yīng)用分水嶺分割之后對(duì)結(jié)果圖像進(jìn)行合并處理。如果初始分割產(chǎn)生過多小區(qū)域，合并處理會(huì)具有很大的運(yùn)算量，所以后處理的時(shí)間復(fù)雜度經(jīng)常較高，還有合并準(zhǔn)則的確定，也是一件比較麻煩的事情，通常有基于相鄰區(qū)域的平均灰度信息和邊界強(qiáng)度信息的合并準(zhǔn)則，不同的合并準(zhǔn)則會(huì)得到不同的分割結(jié)果。其三，就是既有預(yù)處理又有后處理的分割技術(shù)了，根據(jù)具體應(yīng)用領(lǐng)域的要求，如果只是采取預(yù)處理或后處理還不能得到滿意的效果，那就把他們都用上試試了。
分水嶺分割算法源代碼:
//Image Watershed Segmentation
//This is the implementation of the algorithm based on immersion model.
// ===========================================================================
// ===== Module: Watershed.cpp
// ===== -------------------------------------------------------------- ======
// ===== Version 01 Date: 04/21/2003
// ===== -------------------------------------------------------------- ======
// ===========================================================================
// ===== Written by Foxhole@smth.org
// ===== e-mail: gong200@china.com
// ===========================================================================
// Permission to use, copy, or modify this software and its documentation
// for educational and research purposes only is hereby granted without
// fee, provided that this copyright notice appear on all copies and
// related documentation. For any other uses of this software, in original
// or modified form, including but not limited to distribution in whole
// or in part, specific prior permission must be obtained from
// the author(s).
//
// THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
// EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
// WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
//
// IN NO EVENT SHALL RUTGERS UNIVERSITY BE LIABLE FOR ANY SPECIAL,
// INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY
// DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
// WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY
// THEORY OF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE
// OR PERFORMANCE OF THIS SOFTWARE.
// ===========================================================================
#include <queue>
#include <vector>
#include <windows.h>
/*====================================================================
函數(shù)名 ： Watershed
功能 ： 用標(biāo)記-分水嶺算法對(duì)輸入圖像進(jìn)行分割
算法實(shí)現(xiàn) ： 無(wú)
輸入?yún)?shù)說明 ： OriginalImage --輸入圖像（灰度圖，0~255）
SeedImage --標(biāo)記圖像（二值圖，0-非標(biāo)記，1-標(biāo)記）
LabelImage --輸出圖像（1-第一個(gè)分割區(qū)域，2-第二個(gè)分割區(qū)域，...）
row --圖像行數(shù)
col --圖像列數(shù)
返回值說明 ： 無(wú)
====================================================================*/
void Watershed(const int **OriginalImage, char** SeedImage, int **LabelImage, int row, int col)
{
using namespace std;
//標(biāo)記區(qū)域標(biāo)識(shí)號(hào)，從1開始
int Num=0;
int i,j;
//保存每個(gè)隊(duì)列種子個(gè)數(shù)的數(shù)組
vector<int*> SeedCounts;
//臨時(shí)種子隊(duì)列
queue<POINT> que;
//保存所有標(biāo)記區(qū)域種子隊(duì)列的數(shù)組
vector<queue<POINT>* > qu;
int* array;
queue<POINT> *uu;
POINT temp;
for(i=0;i<row;i++)
for(j=0;j<col;j++)
LabelImage[j]=0;
int m,n,k=0;
int up,down,right,left,upleft,upright,downleft,downright;
//預(yù)處理,提取區(qū)分每個(gè)標(biāo)記區(qū)域，并初始化每個(gè)標(biāo)記的種子隊(duì)列
//種子是指標(biāo)記區(qū)域邊緣的點(diǎn)，他們可以在水位上升時(shí)向外淹沒（或者說生長(zhǎng)）
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
//如果找到一個(gè)標(biāo)記區(qū)域
if(SeedImage[j]==1)
{
//區(qū)域的標(biāo)識(shí)號(hào)加一
Num++;
//分配數(shù)組并初始化為零
array=new int[256];
ZeroMemory(array,256*sizeof(int));
//
SeedCounts.push_back(array);
//分配本標(biāo)記的優(yōu)先隊(duì)列
uu=new queue<POINT>[256];
//加入到隊(duì)列數(shù)組中
qu.push_back(uu);
//當(dāng)前點(diǎn)放入本標(biāo)記區(qū)域的臨時(shí)種子隊(duì)列中
temp.x=i;
temp.y=j;
que.push(temp);
//當(dāng)前點(diǎn)標(biāo)記為已處理
LabelImage[j]=Num;
SeedImage[j]=127;
//讓種子隊(duì)列中的種子進(jìn)行生長(zhǎng)直到所有的種子都生長(zhǎng)完畢
while(!que.empty())
{
up=down=right=left=0;
upleft=upright=downleft=downright=0;
//隊(duì)列中取出一個(gè)種子
temp=que.front();
m=temp.x;
n=temp.y;
que.pop();
if(m>0)
{
//上方若為可生長(zhǎng)點(diǎn)則加為新種子
if(SeedImage[m-1][n]==1)
{
temp.x=m-1;
temp.y=n;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m-1][n]=Num;
SeedImage[m-1][n]=127;
}else//否則上方為不可生長(zhǎng)
{
up=1;
}
}
if(m>0&&n>0)
{
if(SeedImage[m-1][n-1]==1)//左上方若為可生長(zhǎng)點(diǎn)則加為新種子
{
temp.x=m-1;
temp.y=n-1;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m-1][n-1]=Num;
SeedImage[m-1][n-1]=127;
}else//否則左上方為不可生長(zhǎng)
{
upleft=1;
}
}
if(m<row-1)
{
if(SeedImage[m+1][n]==1)//下方若為可生長(zhǎng)點(diǎn)則加為新種子
{
temp.x=m+1;
temp.y=n;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m+1][n]=Num;
SeedImage[m+1][n]=127;
}else//否則下方為不可生長(zhǎng)
{
down=1;
}
}
if(m<(row-1)&&n<(col-1))
{
if(SeedImage[m+1][n+1]==1)//下方若為可生長(zhǎng)點(diǎn)則加為新種子
{
temp.x=m+1;
temp.y=n+1;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m+1][n+1]=Num;
SeedImage[m+1][n+1]=127;
}else//否則下方為不可生長(zhǎng)
{
downright=1;
}
}
if(n<col-1)
{
if(SeedImage[m][n+1]==1)//右方若為可生長(zhǎng)點(diǎn)則加為新種子
{
temp.x=m;
temp.y=n+1;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m][n+1]=Num;
SeedImage[m][n+1]=127;
}else//否則右方為不可生長(zhǎng)
{
right=1;
}
}
if(m>0&&n<(col-1))
{
if(SeedImage[m-1][n+1]==1)//右上方若為可生長(zhǎng)點(diǎn)則加為新種子
{
temp.x=m-1;
temp.y=n+1;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m-1][n+1]=Num;
SeedImage[m-1][n+1]=127;
}else//否則右上方為不可生長(zhǎng)
{
upright=1;
}
}
if(n>0)
{
if(SeedImage[m][n-1]==1)//左方若為可生長(zhǎng)點(diǎn)則加為新種子
{
temp.x=m;
temp.y=n-1;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m][n-1]=Num;
SeedImage[m][n-1]=127;
}else//否則左方為不可生長(zhǎng)
{
left=1;
}
}
if(m<(row-1)&&n>0)
{
if(SeedImage[m+1][n-1]==1)//左下方若為可生長(zhǎng)點(diǎn)則加為新種子
{
temp.x=m+1;
temp.y=n-1;
que.push(temp);
//新種子點(diǎn)標(biāo)記為已淹沒區(qū)域
LabelImage[m+1][n-1]=Num;
SeedImage[m+1][n-1]=127;
}else//否則左方為不可生長(zhǎng)
{
downleft=1;
}
}
//上下左右只要有一點(diǎn)不可生長(zhǎng)，那么本點(diǎn)為初始種子隊(duì)列中的一個(gè)
if(up||down||right||left||
upleft||downleft||upright||downright)
{
temp.x=m;
temp.y=n;
qu[Num-1][OriginalImage[m][n]].push(temp);
SeedCounts[Num-1][OriginalImage[m][n]]++;
}
}//while結(jié)束
}
}
}
bool actives;//在某一水位處，所有標(biāo)記的種子生長(zhǎng)完的標(biāo)志
int WaterLevel;
//淹沒過程開始，水位從零開始上升
for(WaterLevel=0;WaterLevel<256;WaterLevel++)
{
actives=true;
while(actives)
{
actives=false;
//依次處理每個(gè)標(biāo)記區(qū)域
for(i=0;i<Num;i++)
{
if(!qu[WaterLevel].empty())
{
actives=true;
while(SeedCounts[WaterLevel]>0)
{
SeedCounts[WaterLevel]--;
temp=qu[WaterLevel].front();
qu[WaterLevel].pop();
m = temp.x;
n = temp.y;//當(dāng)前種子的坐標(biāo)
if(m>0)
{
if(!LabelImage[m-1][n])//上方若未處理
{
temp.x=m-1;
temp.y=n;
LabelImage[m-1][n]=i+1;//上方點(diǎn)標(biāo)記為已淹沒區(qū)域
if(OriginalImage[m-1][n]<=WaterLevel)//上方若為可生長(zhǎng)點(diǎn)則加入當(dāng)前隊(duì)列
{
qu[WaterLevel].push(temp);
}
else//否則加入OriginalImage[m-1][n]級(jí)隊(duì)列
{
qu[OriginalImage[m-1][n]].push(temp);
SeedCounts[OriginalImage[m-1][n]]++;
}
}
}
if(m<row-1)
{
if(!LabelImage[m+1][n])//下方若未處理
{
temp.x=m+1;
temp.y=n;
LabelImage[m+1][n]=i+1;//下方點(diǎn)標(biāo)記為已淹沒區(qū)域
if(OriginalImage[m+1][n]<=WaterLevel)//下方若為可生長(zhǎng)點(diǎn)則加入當(dāng)前隊(duì)列
{
qu[WaterLevel].push(temp);
}
else//否則加入OriginalImage[m+1][n]級(jí)隊(duì)列
{
qu[OriginalImage[m+1][n]].push(temp);
SeedCounts[OriginalImage[m+1][n]]++;
}
}
}
if(n<col-1)
{
if(!LabelImage[m][n+1])//右邊若未處理
{
temp.x=m;
temp.y=n+1;
LabelImage[m][n+1]=i+1;//右邊點(diǎn)標(biāo)記為已淹沒區(qū)域
if(OriginalImage[m][n+1]<=WaterLevel)//右邊若為可生長(zhǎng)點(diǎn)則加入當(dāng)前隊(duì)列
{
qu[WaterLevel].push(temp);
}
else//否則加入OriginalImage[m][n+1]級(jí)隊(duì)列
{
qu[OriginalImage[m][n+1]].push(temp);
SeedCounts[OriginalImage[m][n+1]]++;
}
}
}
if(n>0)
{
if(!LabelImage[m][n-1])//左邊若未處理
{
temp.x=m;
temp.y=n-1;
LabelImage[m][n-1]=i+1;//左邊點(diǎn)標(biāo)記為已淹沒區(qū)域
if(OriginalImage[m][n-1]<=WaterLevel)//左邊若為可生長(zhǎng)點(diǎn)則加入當(dāng)前隊(duì)列
{
qu[WaterLevel].push(temp);
}
else//否則加入OriginalImage[m][n-1]級(jí)隊(duì)列
{
qu[OriginalImage[m][n-1]].push(temp);
SeedCounts[OriginalImage[m][n-1]]++;
}
}
}
}//while循環(huán)結(jié)束
SeedCounts[WaterLevel]=qu[WaterLevel].size();
}//if結(jié)束
}//for循環(huán)結(jié)束
}//while循環(huán)結(jié)束
}//for循環(huán)結(jié)束
while(!qu.empty())
{
uu=qu.back();
delete[] uu;
qu.pop_back();
}
while(!SeedCounts.empty())
{
array=SeedCounts.back();
delete[] array;
SeedCounts.pop_back();
}
}
本文來自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/wazdxm1980/archive/2007/07/04/1678275.aspx
本文來自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/byxdaz/archive/2009/07/24/4377753.aspx
聯(lián)系客服
