分水岭分割算法原理与代码

分水岭分割方法，是一种基于拓扑理论的数学形态学的分割方法，其基本思想是把图像看作是测地学上的拓扑地貌，图像中每一点像素的灰度值表示该点的海 拔高度，每一个局部极小值及其影响区域称为集水盆，而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表 面，刺穿一个小孔，然后把整个模型慢慢浸入水中，随着浸入的加深，每一个局部极小值的影响域慢慢向外扩展，在两个集水盆汇合处构筑大坝，即形成分水岭。

分水岭的计算过程是一个迭代标注过程。分水岭比较经典的计算方法是L. Vincent提出的。在该算法中，分水岭计算分两个步骤，一个是排序过程，一个是淹没过程。首先对每个像素的灰度级进行从低到高排序，然后在从低到高实 现淹没过程中，对每一个局部极小值在h阶高度的影响域采用先进先出(FIFO)结构进行判断及标注。

分水岭变换得到的是输入图像的集水盆图像，集水盆之间的边界点，即为分水岭。显然，分水岭表示的是输入图像极大值点。因此，为得到图像的边缘信息，通常把梯度图像作为输入图像，即

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{.}表示梯度运算。

分水岭算法对微弱边缘具有良好的响应，图像中的噪声、物体表面细微的灰度变化，都会产生过度分割的现象。但同时应当看出，分水岭算法对微弱边缘具有良好的响应，是得到封闭连续边缘的保证的。另外，分水岭算法所得到的封闭的集水盆，为分析图像的区域特征提供了可能。

为消除分水岭算法产生的过度分割，通常可以采用两种处理方法，一是利用先验知识去除无关边缘信息。二是修改梯度函数使得集水盆只响应想要探测的目标。

为降低分水岭算法产生的过度分割，通常要对梯度函数进行修改，一个简单的方法是对梯度图像进行阈值处理，以消除灰度的微小变化产生的过度分割。即 g(x,y)=max(grad(f(x,y)),gθ)

式中，gθ表示阈值。

分水岭分割技术是一种很优秀的且得到了广泛应用的分割技术，从本质上讲，它属于一种基于区域增长的分割方法，但它得到的确是目标的边界，且是连续、 闭合、但像素宽的边界。在很多领域，这种分割技术都得到了广泛的应用，但分水岭分割却有一个致命的弱点，那就是容易产生过分割，对于噪声和细密纹理非常敏 感，使其常常产生严重的过分割结果。所以，针对这个问题，很多人提出了很多种改进的分水岭分割技术。综合来讲，大概也就三类。其一，分割预处理。既在应用 分水岭分割之前对图像进行一些预处理，诸如除噪，求梯度图像，形

态学重建，标记前景背景等等，一个目的，减少小的积水盆，从而减少过分割区域的数量。其 二，分割后处理。既在应用分水岭分割之后对结果图像进行合并处理。如果初始分割产生过多小区域，合并处理会具有很大的运算量，所以后处理的时间复杂度经常 较高，还有合并准则的确定，也是一件比较麻烦的事情，通常有基于相邻区域的平均灰度信息和边界强度信息的合并准则，不同的合并准则会得到不同的分割结果。 其三，就是既有预处理又有后处理的分割技术了，根据具体应用领域的要求，如果只是采取预处理或后处理还不能得到满意的效果，那就把他们都用上试试了。

分水岭分割算法源代码:

//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 [email protected]

// ===== e-mail: [email protected]

//

===========================================================================

// 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

#include

#include

/*====================================================================

函数名 ： Watershed

功能 ： 用标记-分水岭算法对输入图像进行分割

算法实现 ： 无

输入参数说明 ： OriginalImage --输入图像（灰度图，0~255）

SeedImage --标记图像（二值图，0-非标记，1-标记） LabelImage --输出图像（1-第一个分割区域，2-第二个分割区域，...）

row --图像行数

col --图像列数

返回值说明 ： 无

====================================================================*/

void Watershed(const int **OriginalImage, char** SeedImage, int **LabelImage, int row, int col)

{

using namespace std;

//标记区域标识号，从1开始

int Num=0;

int i,j;

//保存每个队列种子个数的数组

vector SeedCounts;

//临时种子队列

queue que;

//保存所有标记区域种子队列的数组

vector* > qu;

int* array;

queue *uu;

POINT temp;

for(i=0;i

for(j=0;j

LabelImage[j]=0;

int m,n,k=0;

int up,down,right,left,upleft,upright,downleft,downright; //预处理,提取区分每个标记区域，并初始化每个标记的种子队列

//种子是指标记区域边缘的点，他们可以在水位上升时向外淹没（或者说生长）

for(i=0;i

{

for(j=0;j

{

//如果找到一个标记区域

if(SeedImage[j]==1)

{

//区域的标识号加一

Num++;

//分配数组并初始化为零

array=new int[256];

ZeroMemory(array,256*sizeof(int));

//

SeedCounts.push_back(array);

//分配本标记的优先队列

uu=new queue[256];

//加入到队列数组中

qu.push_back(uu);

//当前点放入本标记区域的临时种子队列中

temp.x=i;

temp.y=j;

que.push(temp);

//当前点标记为已处理

LabelImage[j]=Num;

SeedImage[j]=127;

//让种子队列中的种子进行生长直到所有的种子都生长完毕 while(!que.empty())

{

up=down=right=left=0;

upleft=upright=downleft=downright=0;

//队列中取出一个种子

m=temp.x;

n=temp.y;

que.pop();

if(m>0)

{

//上方若为可生长点则加为新种子

if(SeedImage[m-1][n]==1)

{

temp.x=m-1;

temp.y=n;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m-1][n]=Num;

SeedImage[m-1][n]=127;

}else//否则上方为不可生长

{

up=1;

}

}

if(m>0&&n>0)

{

if(SeedImage[m-1][n-1]==1)//左上方若为可生长点则加为新种子

{

temp.x=m-1;

temp.y=n-1;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m-1][n-1]=Num;

SeedImage[m-1][n-1]=127;

}else//否则左上方为不可生长

{

upleft=1;

}

}

if(m

{

if(SeedImage[m+1][n]==1)//下方若为可生长点则加为新种子

{

temp.x=m+1;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m+1][n]=Num;

SeedImage[m+1][n]=127;

}else//否则下方为不可生长

{

down=1;

}

}

if(m

{

if(SeedImage[m+1][n+1]==1)//下方若为可生长点则加为新种子

{

temp.x=m+1;

temp.y=n+1;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m+1][n+1]=Num;

SeedImage[m+1][n+1]=127;

}else//否则下方为不可生长

{

downright=1;

}

}

if(n

{

if(SeedImage[m][n+1]==1)//右方若为可生长点则加为新种子

{

temp.x=m;

temp.y=n+1;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m][n+1]=Num;

SeedImage[m][n+1]=127;

}else//否则右方为不可生长

{

right=1;

}

}

if(m>0&&n

{

if(SeedImage[m-1][n+1]==1)//右上方若为可生长点则加为新种子

{

temp.x=m-1;

temp.y=n+1;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m-1][n+1]=Num;

SeedImage[m-1][n+1]=127;

}else//否则右上方为不可生长

{

upright=1;

}

}

if(n>0)

{

if(SeedImage[m][n-1]==1)//左方若为可生长点则加为新种子

{

temp.x=m;

temp.y=n-1;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m][n-1]=Num;

SeedImage[m][n-1]=127;

}else//否则左方为不可生长

{

left=1;

}

}

if(m0)

{

if(SeedImage[m+1][n-1]==1)//左下方若为可生长点则加为新种子

{

temp.x=m+1;

temp.y=n-1;

que.push(temp);

//新种子点标记为已淹没区域

LabelImage[m+1][n-1]=Num;

SeedImage[m+1][n-1]=127;

}else//否则左方为不可生长

{

downleft=1;

}

}

//上下左右只要有一点不可生长，那么本点为初始种子队列中的一个

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结束

}

}

}

bool actives;//在某一水位处，所有标记的种子生长完的标志

int WaterLevel;

//淹没过程开始，水位从零开始上升

for(WaterLevel=0;WaterLevel

{

actives=true;

while(actives)

{

actives=false;

//依次处理每个标记区域

for(i=0;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;//当前种子的坐标

if(m>0)

{

if(!LabelImage[m-1][n])//上方若未处理 {

temp.x=m-1;

temp.y=n;

LabelImage[m-1][n]=i+1;//上方点标记为已淹没区域

if(OriginalImage[m-1][n]

{

qu[WaterLevel].push(temp);

}

else//否则加入OriginalImage[m-1][n]级队列 {

qu[OriginalImage[m-1][n]].push(temp); SeedCounts[OriginalImage[m-1][n]]++; }

}

}

if(m

{

if(!LabelImage[m+1][n])//下方若未处理 {

temp.x=m+1;

temp.y=n;

LabelImage[m+1][n]=i+1;//下方点标记为已淹没区域

if(OriginalImage[m+1][n]

{

qu[WaterLevel].push(temp);

}

else//否则加入OriginalImage[m+1][n]级队列 {

qu[OriginalImage[m+1][n]].push(temp); SeedCounts[OriginalImage[m+1][n]]++; }

}

}

if(n

{

if(!LabelImage[m][n+1])//右边若未处理 {

temp.x=m;

temp.y=n+1;

LabelImage[m][n+1]=i+1;//右边点标记为已淹没区域

if(OriginalImage[m][n+1]

{

qu[WaterLevel].push(temp);

}

else//否则加入OriginalImage[m][n+1]级队列 {

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;//左边点标记为已淹没区域

if(OriginalImage[m][n-1]

{

qu[WaterLevel].push(temp);

}

else//否则加入OriginalImage[m][n-1]级队列 {

qu[OriginalImage[m][n-1]].push(temp); SeedCounts[OriginalImage[m][n-1]]++; }

}

}

}//while循环结束

SeedCounts[WaterLevel]=qu[WaterLevel].size(); }//if结束

}//for循环结束

}//while循环结束 }//for循环结束

while(!qu.empty()) {

uu=qu.back();

delete[] uu;

qu.pop_back(); }

while(!SeedCounts.empty()) {

array=SeedCounts.back(); delete[] array;

SeedCounts.pop_back(); }

}