图像的连通域标记算法及工具详情
注:本文大部分内容来源于网络,尤其是原理部分图片一律非本人所作
简介
之前在CSDN上详情过一个关于如何使用skimage以及opencv标记二值图像的连通域问题。实际上预计不是太多的人懂得标记连通域的原理,加上在医学图像解决中,我们常常用到3维图像,而上述工具只处理了2维图像上的情况,并不支持3维图像的标记(目前还不支持),因而有必要这个连通域标记进行进一步说明。
本文主要详情两点,一是详情一种连通域标记的算法,中文翻译过来我给它叫两阶段法(two pass); 另一个方面在2维连通域标记的基础上详情一个新的高效的3维连通域标记工具。
通过这个简单的原理,相信读者可以根据需求自己去写一个更高效的连通域标记算法。
原理
如图1所示,对于一个二值图像,其前景为1,背景为0,我们希望给其相连的前景部分标记为同一个label,不同的连通域标记为不同的label,我们希望得到的最终结果如图2所示(我是真的不知道简书该怎样并排显示图像…)。
图1 简单示例
图2 连通域标记最终结果
一种标记连通域的方法叫两阶段法,也就是说,通过遍历两次图像上的点即可以完成标记工作,下面我们主要看看它是怎样工作的。
第一阶段
从图3开始,我们从图像的左上角点遍历整个图像。对于第一个黄点(0,0),我们检查它的上边和左边有没有已经标记好的label,显然没有,因而给其标记为1. 如图3.
图3 label-step1
接下来看第二个像素(0, 1), 继续检查它的左边和上边能否有标记好的像素,因为它左边的一个像素已经标记为1, 因而第二个像素也标记为1. 因为第三个像素(0, 2)是一个背景点,因而直接跳过。再看第4个像素(0, 3),因为其左边是背景,因而认为其左边没有标记,同时上边也没有标记,因而需要给它一个新的label,2. 如图4.
图4 label-step2
接下来同理,直到第一行的最后一个像素,我们有了三个标记。如图5.
图5 label-step3
第二行同理,我们看到目前为止还没有出现什么意外,只需检查一个像素的左边和上边能否有标记,假如有,就给它打上同样的标记就可。如图6.
图6 label-step4
到了第三行的第四个元素(2, 3),我们发现了一个意外情况,就是该像素的上边有了一个label 2,而它的左边同样也有一个label 1,这怎样办呢? 这种情况下,我们给该像素标记为两个label中较小的那个,也就是1,同时还要有另一个操作,就是让label 2隶属于 label 1,如图7.
图7 label-step5
有了上述解决矛盾的情况,我们即可以继续往下标记了。始终坚持以下准则:
- 假如遇上一个背景点,直接跳过,不做解决。
- 假如对于一个像素点,其上面和左边都没有标记好的label,那么就从小到达给它一个新的label。
- 假如对于一个像素点,其上面或者者/并且左边已经有了标记好的label,且label不冲突,那就把这个像素也标记成同样的label
- 假如对于一个像素,其上面和左边都有了label,且两个label冲突了,那么就把该像素标记为较小的那个label,同时记住较大的label隶属于较小的label。
遵循上述准则可以得到图8-12的结果:
图8 label-step6
图9 label-step7
图10 label-step8
图11 label-step9
图12 label-step10
至此我们标记完了图像上的每一个像素,并给他们赋了一个值,唯一的问题在于有些连通域我们看着是一个,但是却给了它两个label,但是好在我们知道他们label的继承关系,因而第二遍就是把具备继承关系的部分给合并成为一个。
第二阶段
仍然从左上角点开始遍历,每遍历一个label,都要查查该像素能否具备继承关系。比方第一个像素(0, 0),因为它是1,发现了它有继承关系,但是好在他是父label,因而不用管他;当到了第三个像素(0, 2),是个背景,不需要管它,直接跳过,也不用查继承关系;当到了第四个像素,查到了label 2
具备继承关系,且label 2 隶属于label 1, 不好心思,我们就不要label 2了,直接把它改为label 1,后面的以此类推。图13-16都遵循上述准则。
图13 label-step11
图14 label-step12
图15 label-step13
图16 label-step14
至此,我们第二次遍历完了整个图像,同时也把所有的连通域标记完了。
至此,我们大概理解了两阶段法标记连通域的基本原理,希望能够对读者有所帮助。
工具详情
这方面的工具很多,我自己常用的有这么3个:一个是scikit image, 一个是opencv3,这两个工具目前只支持2维图像的连通域标记。还有一个是github上的一个开源工具,比较高效的完成了3维图像的连通域标记,也是近期发现的,感谢作者吧,哈哈。
- skimage的连通域标记算法
skimage.messure.label - opencv3的连通域标记算法
connectedComponents - 一个高效的3d连通域标记算法
connected-components-3d
参考
1. github-connected-components-3d
2. Connected Component Labelling
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 图像的连通域标记算法及工具详情