C++实现分水岭算法(Watershed Algorithm)
分水岭分割方法(Watershed Segmentation),是一种基于拓扑理论的数学形态学的分割方法,其基本思想是把图像看作是测地学上的拓扑地貌,图像中每一点像素的灰度值表示该点的海拔高度,每一个局部极小值及其影响区域称为集水盆,而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面,刺穿一个小孔,然后把整个模型慢慢浸入水中,随着浸入的加深,每一个局部极小值的影响域慢慢向外扩展,在两个集水盆汇合处构筑大坝,即形成分水岭。
分水岭的计算过程是一个迭代标注过程。分水岭比较经典的计算方法是L. Vincent提出的。在该算法中,分水岭计算分两个步骤,一个是排序过程,一个是淹没过程。首先对每个像素的灰度级进行从低到高排序,然后在从低到高实现淹没过程中,对每一个局部极小值在h阶高度的影响域采用先进先出(FIFO)结构进行判断及标注。
分水岭变换得到的是输入图像的集水盆图像,集水盆之间的边界点,即为分水岭。显然,分水岭表示的是输入图像极大值点。因此,为得到图像的边缘信息,通常把梯度图像作为输入图像,即:
grad(f(x,y))=((f(x-1,y)-f(x+1,y))^2 + (f(x,y-1)-f(x,y+1))^2)^0.5
式中,f(x,y)表示原始图像,grad(.)表示梯度运算。
分水岭算法对微弱边缘具有良好的响应,图像中的噪声、物体表面细微的灰度变化,都会产生过度分割的现象。但同时应当看出,分水岭算法对微弱边缘具有良好的响应,是得到封闭连续边缘的保证的。另外,分水岭算法所得到的封闭的集水盆,为分析图像的区域特征提供了可能。
为消除分水岭算法产生的过度分割,通常可以采用两种处理方法,一是利用先验知识去除无关边缘信息。二是修改梯度函数使得集水盆只响应想要探测的目标。
为降低分水岭算法产生的过度分割,通常要对梯度函数进行修改,一个简单的方法是对梯度图像进行阈值处理,以消除灰度的微小变化产生的过度分割。即:
g(x,y)=max(grad(f(x,y)),gθ)
式中,gθ表示阈值。
程序可采用方法:用阈值限制梯度图像以达到消除灰度值的微小变化产生的过度分割,获得适量的区域,再对这些区域的边缘点的灰度级进行从低到高排序,然后在从低到高实现淹没的过程,梯度图像用Sobel算子计算获得。对梯度图像进行阈值处理时,选取合适的阈值对最终分割的图像有很大影响,因此阈值的选取是图像分割效果好坏的一个关键。缺点:实际图像中可能含有微弱的边缘,灰度变化的数值差别不是特别明显,选取阈值过大可能会消去这些微弱边缘。
下面用C++实现分水岭算法:
#define _USE_MATH_DEFINES #include <cstddef> #include <cstdlib> #include <cstring> #include <climits> #include <cfloat> #include <ctime> #include <cmath> #include <cassert> #include <vector> #include <stack> #include <queue> using namespace std; typedef void GVVoid; typedef bool GVBoolean; typedef char GVChar; typedef unsigned char GVByte; typedef short GVInt16; typedef unsigned short GVUInt16; typedef int GVInt32; typedef unsigned int GVUInt32; typedef long long GVInt64; typedef unsigned long long GVUInt64; typedef float GVFloat32; typedef double GVFloat64; const GVBoolean GV_TRUE = true; const GVBoolean GV_FALSE = false; const GVByte GV_BYTE_MAX = UCHAR_MAX; const GVInt32 GV_INT32_MAX = INT_MAX; const GVInt32 GV_INT32_MIX = INT_MIN; const GVInt64 GV_INT64_MAX = LLONG_MAX; const GVInt64 GV_INT64_MIN = LLONG_MIN; const GVFloat32 GV_FLOAT32_MAX = FLT_MAX; const GVFloat32 GV_FLOAT32_MIN = FLT_MIN; const GVFloat64 GV_FLOAT64_MAX = DBL_MAX; const GVFloat64 GV_FLOAT64_MIN = DBL_MIN; class GVPoint; class GVPoint { public: GVInt32 x; GVInt32 y; public: GVPoint() : x(0), y(0) { } GVPoint(const GVPoint &obj) : x(obj.x), y(obj.y) { } GVPoint(GVInt32 x, GVInt32 y) : x(x), y(y) { } public: GVBoolean operator ==(const GVPoint &right) const { return ((x == right.x) && (y == right.y)); } GVBoolean operator !=(const GVPoint &right) const { return (!(x == right.x) || !(y == right.y)); } }; /* * <Parameter> * <image> image data; * <width> image width; * <height> image height; * <label out> image of labeled watersheds. */ GVVoid gvWatershed( const GVByte *image, GVInt32 width, GVInt32 height, GVInt32 *label) { // Local constants const GVInt32 WSHD = 0; const GVInt32 INIT = -1; const GVInt32 MASK = -2; const GVPoint FICT_PIXEL = GVPoint(~0, ~0); // Image statistics and sorting GVInt32 size = width * height; GVInt32 *image_stat = new GVInt32[GV_BYTE_MAX + 1]; GVInt32 *image_space = new GVInt32[GV_BYTE_MAX + 1]; GVPoint *image_sort = new GVPoint[size]; ::memset(image_stat, 0, sizeof (GVInt32) * (GV_BYTE_MAX + 1)); ::memset(image_space, 0, sizeof (GVInt32) * (GV_BYTE_MAX + 1)); ::memset(image_sort, 0, sizeof (GVPoint) * size); for (GVInt32 i = 0; !(i == size); ++i) { image_stat[image[i]]++; } for (GVInt32 i = 0; !(i == GV_BYTE_MAX); ++i) { image_stat[i + 1] += image_stat[i]; } for (GVInt32 i = 0; !(i == height); ++i) { for (GVInt32 j = 0; !(j == width); ++j) { GVByte space = image[i * width + j]; GVInt32 index = image_stat[space] - (++image_space[space]); image_sort[index].x = j; image_sort[index].y = i; } } for (GVInt32 i = GV_BYTE_MAX; !(i == 0); --i) { image_stat[i] -= image_stat[i - 1]; } // Watershed algorithm GVPoint *head = image_sort; GVInt32 space = 0; GVInt32 *dist = new GVInt32[size]; GVInt32 dist_cnt = 0; GVInt32 label_cnt = 0; std::queue<GVPoint> queue; ::memset(dist, 0, sizeof (GVInt32) * size); ::memset(label, ~0, sizeof (GVInt32) * size); for (GVInt32 h = 0; !(h == (GV_BYTE_MAX + 1)); ++h) { head += space; space = image_stat[h]; for (GVInt32 i = 0; !(i == space); ++i) { GVInt32 index = head[i].y * width + head[i].x; GVInt32 index_l = ((head[i].x - 1) < 0) ? -1 : ((head[i].x - 1) + head[i].y * width); GVInt32 index_r = !((head[i].x + 1) > width) ? -1 : ((head[i].x + 1) + head[i].y * width); GVInt32 index_t = ((head[i].y - 1) < 0) ? -1 : (head[i].x + (head[i].y - 1) * width); GVInt32 index_b = !((head[i].y + 1) > height) ? -1 : (head[i].x + (head[i].y + 1) * width); label[index] = MASK; if ( (!(index_l < 0) && !(label[index_l] < WSHD)) || (!(index_r < 0) && !(label[index_r] < WSHD)) || (!(index_t < 0) && !(label[index_t] < WSHD)) || (!(index_b < 0) && !(label[index_b] < WSHD))) { dist[index] = 1; queue.push(head[i]); } } dist_cnt = 1; queue.push(FICT_PIXEL); while (GV_TRUE) { GVPoint top = queue.front(); GVInt32 index = top.y * width + top.x; GVInt32 index_l = ((top.x - 1) < 0) ? -1 : ((top.x - 1) + top.y * width); GVInt32 index_r = !((top.x + 1) > width) ? -1 : ((top.x + 1) + top.y * width); GVInt32 index_t = ((top.y - 1) < 0) ? -1 : (top.x + (top.y - 1) * width); GVInt32 index_b = !((top.y + 1) > height) ? -1 : (top.x + (top.y + 1) * width); queue.pop(); if (top == FICT_PIXEL) { if (queue.empty()) break; else { ++dist_cnt; queue.push(FICT_PIXEL); top = queue.front(); queue.pop(); } } if (!(index_l < 0)) { if ((dist[index_l] < dist_cnt) && !(label[index_l] < WSHD)) { if (label[index_l] > WSHD) { if ((label[index] == MASK) || (label[index] = WSHD)) label[index] = label[index_l]; else if (!(label[index] == label[index_l])) label[index] = WSHD; } else if (label[index] == MASK) { label[index] = WSHD; } } else if ((label[index_l] == MASK) && (dist[index_l] == 0)) { dist[index_l] = dist_cnt + 1; queue.push(GVPoint(top.x - 1, top.y)); } } if (!(index_r < 0)) { if ((dist[index_r] < dist_cnt) && !(label[index_r] < WSHD)) { if (label[index_r] > WSHD) { if ((label[index] == MASK) || (label[index] = WSHD)) label[index] = label[index_r]; else if (!(label[index] == label[index_r])) label[index] = WSHD; } else if (label[index] == MASK) { label[index] = WSHD; } } else if ((label[index_r] == MASK) && (dist[index_r] == 0)) { dist[index_r] = dist_cnt + 1; queue.push(GVPoint(top.x + 1, top.y)); } } if (!(index_t < 0)) { if ((dist[index_t] < dist_cnt) && !(label[index_t] < WSHD)) { if (label[index_t] > WSHD) { if ((label[index] == MASK) || (label[index] = WSHD)) label[index] = label[index_t]; else if (!(label[index] == label[index_t])) label[index] = WSHD; } else if (label[index] == MASK) { label[index] = WSHD; } } else if ((label[index_t] == MASK) && (dist[index_t] == 0)) { dist[index_t] = dist_cnt + 1; queue.push(GVPoint(top.x, top.y - 1)); } } if (!(index_b < 0)) { if ((dist[index_b] < dist_cnt) && !(label[index_b] < WSHD)) { if (label[index_b] > WSHD) { if ((label[index] == MASK) || (label[index] = WSHD)) label[index] = label[index_b]; else if (!(label[index] == label[index_b])) label[index] = WSHD; } else if (label[index] == MASK) { label[index] = WSHD; } } else if ((label[index_b] == MASK) && (dist[index_b] == 0)) { dist[index_b] = dist_cnt + 1; queue.push(GVPoint(top.x, top.y + 1)); } } } for (GVInt32 i = 0; !(i == space); ++i) { GVInt32 index = head[i].y * width + head[i].x; dist[index] = 0; if (label[index] == MASK) { label_cnt++; label[index] = label_cnt; queue.push(head[i]); while (!queue.empty()) { GVPoint top = queue.front(); GVInt32 index_l = ((top.x - 1) < 0) ? -1 : ((top.x - 1) + top.y * width); GVInt32 index_r = !((top.x + 1) > width) ? -1 : ((top.x + 1) + top.y * width); GVInt32 index_t = ((top.y - 1) < 0) ? -1 : (top.x + (top.y - 1) * width); GVInt32 index_b = !((top.y + 1) > height) ? -1 : (top.x + (top.y + 1) * width); queue.pop(); if (!(index_l < 0) && (label[index_l] == MASK)) { queue.push(GVPoint(top.x - 1, top.y)); label[index_l] = label_cnt; } if (!(index_r < 0) && (label[index_r] == MASK)) { queue.push(GVPoint(top.x + 1, top.y)); label[index_r] = label_cnt; } if (!(index_t < 0) && (label[index_t] == MASK)) { queue.push(GVPoint(top.x, top.y - 1)); label[index_t] = label_cnt; } if (!(index_b < 0) && (label[index_b] == MASK)) { queue.push(GVPoint(top.x, top.y + 1)); label[index_b] = label_cnt; } } } } } // Release resources delete[] image_stat; delete[] image_space; delete[] image_sort; delete[] dist; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25