本文原载于https://imlogm.github.io，转载请注明出处~

摘要：多种子的区域生长算法，基于C++编写。

关键字：图像处理, 种子生长, 区域生长

1. 题外话

最近需要找一种简单对图像进行分割的算法，作为后续算法的前处理阶段。最开始想到的是聚类，但是聚类会有分割后不保证连通性的问题。

区域生长法可以保证分割后各自区域的连通性。但网上大多数的代码都是单个种子的，用的多是matlab或旧版本的opencv。索性，我照着单种子的思路，写了一个多种子的区域生长算法分享出来。

2. 单种子的区域生长

事实上，我就是参照这篇文章的思路写的代码。这篇文章的代码思路清晰，可惜用的旧版本的opencv，而且是单种子。

大体思路是这样的：

1、遍历全图，寻找是否还有undetermined的点，如有，作为种子

2、进行单种子的区域生长算法，生长出的区域记入矩阵mask

3、如果mask记录的区域面积足够大，把mask中的区域记录到矩阵dest中，状态为determined；如果mask记录的区域面积太小，把mask中的区域记录到矩阵dest中，状态为ignored（忽略分割出来面积过小的区域）

4、重复上述步骤，直到全图不存在undetermined的点

我对现在的算法还不是很满意，其一，我没有做太多优化，代码运行卡卡的；其二，我用的灰度图，以及“差值/阈值”的方式来判断是否相似，阈值不是自适应的。

注：新版本添加了自动寻找阈值的demo，详见本文最后一节

对于图片尺寸越大越卡这个问题，可以在读图片的时候统一resize成256×256，大多数追求速度的图像处理算法都会有这步。

对于彩色图，用3个通道的距离来判断相似度会更好。

以上两个问题，我为了保持算法的原汁原味，就没有添加。（其实是我懒得写了～）

注：关于彩色图那点，最新版本已经添加了相关代码。思路是RGB三个通道的差值取平方和。Delta = R^2 + G^2 + B^2 。

新版本的代码中，已经添加了阈值自适应的demo。想法来自于二值化领域的OTSU（大津法），不懂大津法的可以搜索下，虽然属于不同领域，但算法思想可以借鉴。我在demo中的具体做法如下：

1、threshold的取值在一定范围内，遍历所有可取的threshold

2、对于一个取到的threshold，区域生长算法可以得到分割后的N个区域。计算同一区域内的像素值的方差var(same_region)以及不同区域间像素平均值的差值delta(mean(different_region))

3、用loss表征分割的好坏，公式中a和b是手动设置的参数，loss越小说明分割得越好：$$loss=a \div delta(mean(different-region)) + b \times Var(same-region)$$

4、遍历所有可取的threshold，求出各自的loss，取loss最小值对应的threshold