// 注:本内容为作者原创,禁止在其他网站复述内容以及用于商业盈利,如需引用,请标明出处:/lv-anchoret/
今天我们来介绍用C++算法如何来实现图像分割算法中的区域生长算法
我们解决的是对一整张图像所有内容进行区域生长分类,当然,如果是对图像中的某一类型进行区域生长可能更容易一些
个人理解
区域生长算法需要确定一个阈值,这个值代表同一类图像信息灰度值的差值,比如,我要一个人脸图(假设眼睛是蓝色的),头发是黑色的但是不同光线反射原因或者位置不同,图像中显示的灰度颜色值有5、10、3等,虽然灰度值不一样,但是他们代表的都是黑色,都是头发,区域生长,就是把这些相似灰度值的一类事物统一标注显示,这也就达到了分类识别的目的,关于阈值,比如上述的头发,我们需要将所有是头发的像素点都标注出来,那么我们的阈值就应该设置为10,如果设置为3,可能灰度值为3和5的点会统一识别,但是10就被排除在外了。
算法核心就是一个bfs,设立一个种子点,向四周扩张,如果相邻的点的灰度值相对于种子点在阈值范围之内,那么,我们把它识别并包含统一进来,扩张完毕之后,所有相似的一类图像将被统一标注。
关于标注我们还需要说一下,一开始,想起了四色定理,即用四种颜色就可以吧整个地图分类标注且相邻类别颜色不同,后来想了想还不如把同一类型区域中的所有点都设置为种子点灰度像素值。
之后想起来我们光线追踪一直用的ppm彩色文件格式,索性将灰度值转成rgb彩色图看着更爽
区域生长算法流程
1. 找种子点
2. 扩张原则
3. 终止条件
数据介绍
我们的数据是一张灰度图 : 见 纹理相册夹中的第二张图
我们处理输出的是一张彩色图像,图像格式是我们光线追踪的文件格式 .ppm,用我们光线追踪的图片解析器(ppmviewer)就能打开(没有的也没关系,搜索一下,下载不超过十几秒,超轻量级ppm解读器)
我们都知道,C/C++ 中读取图像麻烦,特别是这种.jpg复杂格式数据,所以,我们用matlab先把图像读出来,输出到一个TXT中,存储为二维矩阵形式,然后用C++代码读取TXT文件内容,存储到一个二维数据序列中。(都有代码在后面)
我们侧重实现算法本身,所以关于图像的读取和写入我们不做过多描述
算法介绍
算法自命名:首次左上区域生长算法
时间复杂度:O(图像大小*种子数量*log(种子数量))
一、区域生长的三大要素确立:
(1)生长合并规则:
用户自定义阈值,根据种子点和当前点的差值,如果在阈值之内,那么合并,将当前点的灰度值设为种子灰度值
(2)种子选取:
将图像左上角第一个点作为第一个种子,在扩张的过程中第一个不符合生长合并规则的位置,作为下一次生长的种子,即首次选定,后期自适应确定。
(3)算法结束:
种子为空
二、优缺点
该算法的优点: 针对大型全局生长而衍生
该算法种子不会将同一个位置作为种子多次重复生长(时间空间复杂度优化)
某个种子在开始生长时,如果已经被包含于另一个种子的生长区域中,那么该种子将不会进行生长(时间复杂度优化)
该算法的缺点: 首次选定法不能用合适的灰度代表整个区域,只能是坐标小的点的灰度值
生长