连通域的原理与Python实现

2020/08/14 08:28
阅读数 1.8K


向AI转型的程序员都关注了这个号👇👇👇

机器学习AI算法工程   公众号:datayx


二值图像连通域

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


连通区域的定义一般有两种,分为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




阅读过本文的人还看了以下文章:


TensorFlow 2.0深度学习案例实战


基于40万表格数据集TableBank,用MaskRCNN做表格检测


《基于深度学习的自然语言处理》中/英PDF


Deep Learning 中文版初版-周志华团队


【全套视频课】最全的目标检测算法系列讲解,通俗易懂!


《美团机器学习实践》_美团算法团队.pdf


《深度学习入门:基于Python的理论与实现》高清中文PDF+源码


特征提取与图像处理(第二版).pdf


python就业班学习视频,从入门到实战项目


2019最新《PyTorch自然语言处理》英、中文版PDF+源码


《21个项目玩转深度学习:基于TensorFlow的实践详解》完整版PDF+附书代码


《深度学习之pytorch》pdf+附书源码


PyTorch深度学习快速实战入门《pytorch-handbook》


【下载】豆瓣评分8.1,《机器学习实战:基于Scikit-Learn和TensorFlow》


《Python数据分析与挖掘实战》PDF+完整源码


汽车行业完整知识图谱项目实战视频(全23课)


李沐大神开源《动手学深度学习》,加州伯克利深度学习(2019春)教材


笔记、代码清晰易懂!李航《统计学习方法》最新资源全套!


《神经网络与深度学习》最新2018版中英PDF+源码


将机器学习模型部署为REST API


FashionAI服装属性标签图像识别Top1-5方案分享


重要开源!CNN-RNN-CTC 实现手写汉字识别


yolo3 检测出图像中的不规则汉字


同样是机器学习算法工程师,你的面试为什么过不了?


前海征信大数据算法:风险概率预测


【Keras】完整实现‘交通标志’分类、‘票据’分类两个项目,让你掌握深度学习图像分类


VGG16迁移学习,实现医学图像识别分类工程项目


特征工程(一)


特征工程(二) :文本数据的展开、过滤和分块


特征工程(三):特征缩放,从词袋到 TF-IDF


特征工程(四): 类别特征


特征工程(五): PCA 降维


特征工程(六): 非线性特征提取和模型堆叠


特征工程(七):图像特征提取和深度学习


如何利用全新的决策树集成级联结构gcForest做特征工程并打分?


Machine Learning Yearning 中文翻译稿


蚂蚁金服2018秋招-算法工程师(共四面)通过


全球AI挑战-场景分类的比赛源码(多模型融合)


斯坦福CS230官方指南:CNN、RNN及使用技巧速查(打印收藏)


python+flask搭建CNN在线识别手写中文网站


中科院Kaggle全球文本匹配竞赛华人第1名团队-深度学习与特征工程



不断更新资源

深度学习、机器学习、数据分析、python

 搜索公众号添加: datayx  



机大数据技术与机器学习工程

 搜索公众号添加: datanlp

长按图片,识别二维码





本文分享自微信公众号 - 机器学习AI算法工程(datayx)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部