Python3实现TwoPass算法检测区域连通性
目录 技术背景 Two-Pass算法 测试数据的生成 Two-Pass算法的实现 算法的执行流程 标签的重映射 其他的测试用例 总结概要 版权声明 参考链接 技术背景
连通性检测是图论中常常遇到的一个问题，我们可以用五子棋的思路来理解这个问题五子棋中，横、竖、斜相邻的两个棋子，被认为是相连接的，而一样的道理，在一个二维的图中，只要在横、竖、斜三个方向中的一个存在相邻的情况，就可以认为图上相连通的。比如以下案例中的python数组，3号元素和5号元素就是相连接的，5号元素和6号元素也是相连接的，因此这三个元素实际上是属于同一个区域的：array([[0, 3, 0], [0, 5, 0], [6, 0, 0]])
而再如下面这个例子，其中的1、2、3三个元素是相连的，4、5、6三个元素也是相连的，但是这两个区域不存在连接性，因此这个网格被分成了两个区域：array([[1, 0, 4], [2, 0, 5], [3, 0, 6]])
那么如何高效的检测一张图片或者一个矩阵中的所有连通区域并打上标签，就是我们所关注的一个问题。Two-Pass算法
一个典型的连通性检测的方案是Two-Pass算法，该算法可以用如下的一张动态图来演示：
该算法的核心在于用两次的遍历，为所有的节点打上分区的标签，如果是不同的分区，就会打上不同的标签。其基本的算法步骤可以用如下语言进行概述：遍历网格节点，如果网格的上、左、左上三个格点不存在元素，则为当前网格打上新的标签，同时标签编号加一；当上、左、左上的网格中存在一个元素时，将该元素值赋值给当前的网格作为标签；当上、左、左上的网格中有多个元素时，取最低值作为当前网格的标签；在标签赋值时，留意标签上边和左边已经被遍历过的4个元素，将4个元素中的最低值与这四个元素分别添加到Union的数据结构中（参考链接1）；再次遍历网格节点，根据Union数据结构中的值刷新网格中的标签值，最终得到划分好区域和标签的元素矩阵。测试数据的生成
这里我们以Python3为例，可以用Numpy来产生一系列随机的0-1矩阵，这里我们产生一个20*20大小的矩阵：# two_pass.py import numpy as np import matplotlib.pyplot as plt if __name__ == ＂__main__＂: np.random.seed(1) graph = np.random.choice([0,1],size=(20,20)) print (graph) plt.figure() plt.imshow(graph) plt.savefig(＂random_bin_graph.png＂)
执行的输出结果如下：$ python3 two_pass.py [[1 1 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0] [0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0] [1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 0] [0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0] [1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1] [1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0] [0 1 1 1 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1] [1 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0] [1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0] [0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0] [0 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0] [1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1] [1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1] [1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1] [0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1] [0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0] [0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1] [0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0] [1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0] [0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1]]
同时会生成一张网格的图片：
其实从这个图片中我们可以看出，图片的上面部分几乎都是连接在一起的，只有最下面存在几个独立的区域。Two-Pass算法的实现
这里需要说明的是，因为我们并没有使用Union的数据结构，而是只使用了Python的字典数据结构，因此代码写起来会比较冗余而且不是那么美观，但是这里我们主要的目的是先用代解决这一实际问题，因此代码乱就乱一点吧。# two_pass.py import numpy as np import matplotlib.pyplot as plt from copy import deepcopy def first_pass(g) -> list: graph = deepcopy(g) height = len(graph) width = len(graph[0]) label = 1 index_dict = {} for h in range(height): for w in range(width): if graph[h][w] == 0: continue if h == 0 and w == 0: graph[h][w] = label label += 1 continue if h == 0 and graph[h][w-1] > 0: graph[h][w] = graph[h][w-1] continue if w == 0 and graph[h-1][w] > 0: if graph[h-1][w] <= graph[h-1][min(w+1, width-1)]: graph[h][w] = graph[h-1][w] index_dict[graph[h-1][min(w+1, width-1)]] = graph[h-1][w] elif graph[h-1][min(w+1, width-1)] > 0: graph[h][w] = graph[h-1][min(w+1, width-1)] index_dict[graph[h-1][w]] = graph[h-1][min(w+1, width-1)] continue if h == 0 or w == 0: graph[h][w] = label label += 1 continue neighbors = [graph[h-1][w], graph[h][w-1], graph[h-1][w-1], graph[h-1][min(w+1, width-1)]] neighbors = list(filter(lambda x:x>0, neighbors)) if len(neighbors) > 0: graph[h][w] = min(neighbors) for n in neighbors: if n in index_dict: index_dict[n] = min(index_dict[n], min(neighbors)) else: index_dict[n] = min(neighbors) continue graph[h][w] = label label += 1 return graph, index_dict def remap(idx_dict) -> dict: index_dict = deepcopy(idx_dict) for id in idx_dict: idv = idx_dict[id] while idv in idx_dict: if idv == idx_dict[idv]: break idv = idx_dict[idv] index_dict[id] = idv return index_dict def second_pass(g, index_dict) -> list: graph = deepcopy(g) height = len(graph) width = len(graph[0]) for h in range(height): for w in range(width): if graph[h][w] == 0: continue if graph[h][w] in index_dict: graph[h][w] = index_dict[graph[h][w]] return graph def flatten(g) -> list: graph = deepcopy(g) fgraph = sorted(set(list(graph.flatten()))) flatten_dict = {} for i in range(len(fgraph)): flatten_dict[fgraph[i]] = i graph = second_pass(graph, flatten_dict) return graph if __name__ == ＂__main__＂: np.random.seed(1) graph = np.random.choice([0,1],size=(20,20)) graph_1, idx_dict = first_pass(graph) idx_dict = remap(idx_dict) graph_2 = second_pass(graph_1, idx_dict) graph_3 = flatten(graph_2) print (graph_3) plt.subplot(131) plt.imshow(graph) plt.subplot(132) plt.imshow(graph_3) plt.subplot(133) plt.imshow(graph_3>0) plt.savefig(＂random_bin_graph.png＂)
完整代码的输出如下所示：$ python3 two_pass.py [[1 1 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0] [0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0] [1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 0] [0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0] [1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1] [1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0] [0 1 1 1 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1] [1 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0] [1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0] [0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0] [0 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0] [1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1] [1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1] [1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1] [0 1 0 2 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1] [0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0] [0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1] [0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0] [3 0 3 0 4 0 0 0 0 0 0 5 0 0 0 1 0 1 1 0] [0 3 3 0 4 0 6 0 7 7 0 0 5 0 0 0 0 0 1 1]]
同样的我们可以看看此时得到的新的图像：
这里我们并列的画了三张图，第一张图是原图，第二张图是划分好区域和标签的图，第三张是对第二张图进行二元化的结果，以确保在运算过程中没有丢失原本的信息。经过确认这个标签的结果划分是正确的，但是因为涉及到一些算法实现的细节，这里我们还是需要展开来介绍一下。算法的执行流程if __name__ == ＂__main__＂: np.random.seed(1) graph = np.random.choice([0,1],size=(20,20)) graph_1, idx_dict = first_pass(graph) idx_dict = remap(idx_dict) graph_2 = second_pass(graph_1, idx_dict) graph_3 = flatten(graph_2)
这个部分是算法的核心框架，在本文中的算法实现流程为：先用first_pass 遍历一遍网格节点，按照上一个章节中介绍的Two-Pass算法打上标签，并获得一个映射关系；然后用remap 将上面得到的映射关系做一个重映射，确保每一个级别的映射都对应到了最根部（可以联系参考链接1的内容进行理解，虽然这里没有使用Union的数据结构，但是本质上还是一个树形的结构，需要做一个重映射）；然后用second_pass 执行Two-Pass算法的第二次遍历，得到一组打上了新的独立标签的网格节点；最后需要用flatten将标签进行压平，因为前面映射的关系，有可能导致标签不连续，所以我们这里又做了一次映射，确保标签是连续变化的，实际应用中可以不使用这一步。标签的重映射
关于节点的遍历，大家可以直接看算法代码，这里需要额外讲解的是标签的重映射模块的代码：def remap(idx_dict) -> dict: index_dict = deepcopy(idx_dict) for id in idx_dict: idv = idx_dict[id] while idv in idx_dict: if idv == idx_dict[idv]: break idv = idx_dict[idv] index_dict[id] = idv return index_dict
这里的算法是先对得到的标签进行遍历，在字典中获取当前标索引所对应的值，作为新的索引，直到键跟值一致为止，相当于在一个树形的数据结构中重复寻找父节点直到找到根节点。其他的测试用例
这里我们可以再额外测试一些案例，比如增加几个0元素使得网格节点更加稀疏：graph = np.random.choice([0,0,0,1],size=(20,20))
得到的结果图片如下所示：
还可以再稀疏一些：graph = np.random.choice([0,0,0,0,0,1],size=(20,20))
得到的结果如下图所示：
越是稀疏的图，得到的分组结果就越分散。总结概要
在本文中我们主要介绍了利用Two-Pass的算法来检测区域连通性，并给出了Python3的代码实现，当然在实现的过程中因为没有使用到Union这样的数据结构，仅仅用了字典来存储标签之间的关系，因此效率和代码可读性都会低一些，单纯作为用例的演示和小规模区域划分的计算是足够用了。在该代码实现方案中，还有一点与原始算法不一致的是，本实现方案中打新的标签是读取上、上左和左三个方向的格点，但是存储标签的映射关系时，是读取了上、上左、上右和左这四个方向的格点。版权声明
本文首发链接为：https://www.cnblogs.com/dechinphy/p/two-pass.html
作者ID：DechinPhy
更多原著文章请参考：https://www.cnblogs.com/dechinphy/
打赏专用链接：https://www.cnblogs.com/dechinphy/gallery/image/379634.html
腾讯云专栏同步：https://cloud.tencent.com/developer/column/91958参考链接https://blog.csdn.net/lichengyu/article/details/13986521https://www.cnblogs.com/riddick/p/8280883.html
电脑常见的问题电脑是个好东西，但是也有出问题的时候，就像我们是怎么处理的就要靠我们怎么去摸索了。（以下是网络截图）就比如这个，这种情况就很有可能是CMOS的电池没电了，需要自行更换。第一个是运行
电脑小常识3最经工作比较忙，各位见谅，不多说，直奔话题。相信各位小伙伴应该遇到过以下问题你是逗遇到过呢？这是因为我们在装不同的主板的同时另一个硬盘的数据和外设硬件驱动不同就会导致蓝屏，还有可能
电脑小常识3现在的市面上CPU种类太繁杂，有些DIY用户不知道还如何选择，其实呢我们一般用户选择i54590也够用了，像有些发烧友都会选择好点的处理器，英特尔i76700k或i76800k。不
国产消费电子弯道超车，内容种草是未来趋势商家降本提效，消费者喜新厌旧。文吴鹤鸣编辑范婷婷加加减减了几个月的购物车，眼巴巴等着满减，在双11这天清空，已经成了很多人的习惯。尤其是消费电子3C类产品，消费偏好以新品高端商品为
食品生鲜商家看过来！今年双11怎么玩才能打爆产品？和去年一样，今年天猫双11依旧保持双节棍，分两个阶段售卖，分别是11月13日和11月11日。昨日，阿里巴巴副总裁天猫副总裁吹雪公布了今年双11节奏。此外，两波预售时间也纷纷出炉10
固态硬盘简单评测现如今固态硬盘的种类是非常多的，就比如今天要评测的就是一款用了接近一年的英特尔760p的硬盘，咱们来看看它的表现力如何。这是它的缓存颗粒，也是TLC原厂颗粒，采用的南亚512mb的
2021国庆黄金周数据分析花的钱少了，玩的样多了，你开心了吗？国庆七天假期结束，在疫情防控常态化的背景下，国人算是渡过了一个不错的假日，除了去新疆霍尔果斯的游客有点麻烦。总体来看，疫情态势稳定，各方给出的假期消费数据也倾向乐观。不过，就出游来
大数据人工智能烹饪新餐饮新经济横空出世日前阿里巴巴集团超1000亿人民币成立达摩院的消息又为大数据人工智能这两个原本就火爆的话题添了一把柴。事实上，这一消息不仅仅揭示了我国科技对于技术提高的刚需，也表明正是由于当下互联
俞敏洪数据比人工智能更重要TechWeb11月1日，在出席鲸媒体举办的2018TEC教育创想大会时，新东方董事长俞敏洪就对现在教育培训领域的AI焦虑吐槽了一番。同时他也透露，腾讯阿里等都希望和新东方共享数据
大数据杀熟你会相信吗？日前，作家王小山的一篇怀疑被互联网订票网站大数据杀熟的微博再次引起热议，尽管网站及时出面澄清，不少网友依旧对价格波动较大的机票表示不满，机票价格变化如此之快，真的不是航空公司在捣鬼
树莓派3强有力的对手来了，高性能低功耗，63美元起大家好，我是小月月，说到树莓派，燃起了不少人的diy的热情，但它显然并不适用于所有项目。Hardkernel（韩国的开发板厂商）意识到一些人会寻求更强大的替代品，于是推出了最新款的
硬盘数据如何安全复制？有了它，轻松搞定1。前言为什么，买什么样的需求（SATA硬盘一对多克隆，5盘位同时读写）2。包装，外观，材质（塑料金属底座），大小（大小适中，重量轻，方便移动），视觉（黑色），触感（周围磨砂塑料，批量数据复制，有了这个神器，轻松搞定前言为什么买这个产品，出于什么样的需求（硬盘对拷，一拖三，硬盘读写）产品包装，外观，材质，大小，视觉，触感，配件安装安装拆卸（即插即用）功能功能特性突出卖点（一拖三，安装方便，脱机创意街拍，轻松上阵，飞宇G6MAX稳定器，不止是稳CiaoBello，我是老房。年底了，年假不用就废啦，抓紧和土豪老板夫妇俩来个说走就走的游玩，一游就游去了泉州。土豪朋友给我的理由也很土豪，我想去吃正宗的佛跳墙。为了旅拍，他横竖纠手机壳也可硬核给华为Mate30Pro手机穿上Defense外衣CiaoBella，我是老房。曾经有一份真挚的感情摆在我的面前我没有珍惜，等我失去的时候才追悔莫及，人间最痛苦的事莫过于此老房的剧情是主力机iPhone叉一直是裸奔，去年被家里的皮一二三步走，轻松玩转小米智能家居CiaoBella，我是老房。得益于小米生态链的强大布局，以及米家APP丰富的功能和拓展性，目前小米系的智能家居也成为了越来越多家庭的选择。智能家居到底智能在哪里？使用起来方便不方优雅绽放健康生活Jeep女士智能小红表开箱CiaoBella，我是老房。其实以前也想给老婆买块智能手表，但市面上的智能手表大多数造型还都较为硬朗，虽然功能丰富但也另一方面使得手表的体积偏大且略有分量，并不是非常适合对手表智有线转无线高性价比直选耳机OPPOEncoW31上手CiaoBella，我是老房。近年来，随着越来越多的手机取消3。5毫米耳机接口，真无线（TWS）蓝牙耳机得到了飞速的发展，市场竞争也愈发的激烈。充分的竞争使得技术得到飞速发展，产品要人造凉爽更要天然舒适米家直流变频落地扇1XCiaoTutti，我是老房。当回家锁上家门的时候还是冬天，还没过春节。当能出门的时候，油菜花都开了！一样的，等到荷花开也是很快的事了。减缓熵增，减少能耗，利国利民。降低感染的风险绘本网课做手工，健康方便耐折腾的儿童学习桌面分享CiaoBella，我是老房。家里小朋友已经4岁，是时候给他准备一套属于自己的桌面空间了。和咱们大人不一样，小朋友的儿童书桌要以结实耐用为主，桌面布局要以健康抗造为重，要关注功能性健康升级玩法多，办公娱乐两不误，多功能双屏办公桌面及灯光布局CiaoBello，我是老房。在公司的时候其实老房一直在使用双显示器办公，不过主要是一台笔记本电脑外加一台15寸的老款显示器。虽然配置稍微差了点，但多一个屏幕的便利性以及对工作效率从意式浓缩到卡布奇诺，德龙全自动咖啡机，一键满足你的咖啡需求CiaoBella，我是老房。这句开篇词其实是一句意大利语，意为你好美女。是的，当年在意大利的留学经历，也对老房的咖啡饮食观产生了深远的影响。是的，在意大利这个发明摩卡壶的国家，当