连通域的原理与Python实现

二值图像连通域

二值图像分析最基础的也是最重要的方法之一就是连通域标记，它是所有二值图像分析的基础。它通过对二值图像中目标像素的标记，让每个单独的连通区域形成一个被标识的块，进一步的我们就可以获取这些块的轮廓、外接矩形、质心、不变矩等几何参数。

连通区域的定义一般有两种，分为4邻接和8邻接。下面这幅图中，如果考虑4邻接，则有3个连通域，8邻接则是2个连通域。

从连通区域的定义可以知道，一个连通域是由具有相同像素值的相邻像素组成像素集合，因此，我们就可以通过这两个条件在图像中寻找连通区域，对于找到的每个连通域，我们赋予其一个唯一的标识（ Label ），以区别其他连通域。

连通域分析的基本算法有两种：1) Two-Pass 两遍扫描 2) Seed-Filling 种子填充法。

Two-Pass 算法

两遍扫描法（ Two-Pass ），正如其名，指的就是通过扫描两遍图像，将图像中存在的所有连通域找出并标记。

另外，我在代码实现的过程中想到另外一种 Two-Pass 的方式(即扫描两遍图像的方式)实现，就是第二次扫描与 (1) 同样的过程,只是方向换成从右下到左上。我后面的 Two-Pass 代码是使用我自己想到的方法实现的，自己使用了几个例子测试了下，目前没出现啥问题。

Seed-Filling 算法

种子填充方法来源于计算机图形学，常用于对某个图形进行填充。它基于区域生长算法。我的理解就是递归遍历。

附上两种方法的 Python 的实现

python验证码识别教程之利用投影法、连通域法分割图片

接下来文章主要记录一下如何切分验证码，用到的主要库就是Pillow和Linux下的图像处理工具GIMP。首先假设一个固定位置和宽度、无粘连、无干扰的例子学习一下如何使用Pillow来切割图片。

使用GIMP打开图片后，按 加号 放大图片，然后点击View->Show Grid来显示网格线：

其中，每个正方形边长为10像素，所以数字1切割坐标为左20、上20、右40、下70。以此类推可以知道剩下3个数字的切割位置。

代码如下：

那么，如果字符位置不固定怎么办呢？现在假设一种随机位置宽度、无粘连、无干扰线的情况。

第一种方法，也是最简单的方法叫做”投影法”。原理就是将二值化后的图片在竖直方向进行投影，根据投影后的极值来判断分割边界。这里我依然使用上面的验证码图片来进行演示：

通过vertical函数我们就得到了一个包含所有黑色像素在X轴上投影后左右边界的位置。由于验证码没有任何干扰，所以我的阈值设定为0。

所以对于简单粘连的情况，调整阈值也是可以解决的。

第二种方法，叫做CFS连通域分割法。原理就是假定每个字符都由一个单独的连通域组成，换言之就是无粘连，找到一个黑色像素并开始判断，直到所有相连的黑色像素都被遍历标记过后即可判断出这个字符的分割位置。算法如下：

• 将二值化后的图片进行从左到右、从上到下的遍历，如果遇到黑色像素并且这个像素没有没访问过，就将这个像素入栈并标记为已经访问。
• 如果栈不为空，则继续探测周围8个像素，并执行第2步；如果栈空，则代表探测完了一个字符块。
• 探测结束，这样就确定了若干字符。

代码如下：

调用后输出结果和使用投影法是一样的。另外我看网上还有一种叫做“泛洪填充(Flood Fill)”的方法，似乎和连通域是一样的。

参考文章

https://zhuanlan.zhihu.com/p/97689424

https://www.jb51.net/article/141434.htm