# 技术背景

```array([[0, 3, 0],
[0, 5, 0],
[6, 0, 0]])```

```array([[1, 0, 4],
[2, 0, 5],
[3, 0, 6]])```

# Two-Pass算法

1. 遍历网格节点，如果网格的上、左、左上三个格点不存在元素，则为当前网格打上新的标签，同时标签编号加一；
2. 当上、左、左上的网格中存在一个元素时，将该元素值赋值给当前的网格作为标签；
3. 当上、左、左上的网格中有多个元素时，取最低值作为当前网格的标签；
4. 在标签赋值时，留意标签上边和左边已经被遍历过的4个元素，将4个元素中的最低值与这四个元素分别添加到Union的数据结构中（参考链接1）；
5. 再次遍历网格节点，根据Union数据结构中的值刷新网格中的标签值，最终得到划分好区域和标签的元素矩阵。

# 测试数据的生成

```# 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算法的实现

```# 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:
graph[h][w] = label
label += 1
continue
if w == 0:
if graph[h-1][min(w+1, width-1)] > 0:
graph[h][w] = graph[h-1][min(w+1, width-1)]
continue
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)```

## 标签的重映射

```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```

## 其他的测试用例

`graph = np.random.choice([0,0,0,1],size=(20,20))`

`graph = np.random.choice([0,0,0,0,0,1],size=(20,20))`

# 参考链接

0 条评论

• ### two Pass方法连通域检测

原理： Two-Pass方法检测连通域的原理可参见这篇博客：http://blog.csdn.net/lichengyu/article/details/139...

• ### 连通域的原理与Python实现

二值图像分析最基础的也是最重要的方法之一就是连通域标记，它是所有二值图像分析的基础。它通过对二值图像中目标像素的标记，让每个单独的连通区域形成一个被标识的块，进...

• ### Python 版 LeetCode 刷题笔记 #1 两数之和

学 Python 也有一段时间了，一直维持在入门阶段，最近想集中精力精进下编码能力，所以把刷题当作一个练习，也看看自己能坚持几道题。

• ### ​愉快地迁移到Python3

原文链接:https://github.com/arogozhnikov/python3_with_pleasure

• ### ​[Github高赞文章]愉快地迁移到Python3

最近在把编程教室的网站和小程序从python2升级到python3，踩了不少坑。正好看到一篇关于迁移python3的文章，里面总结了一些可能遇到的问题，对比了版...

• ### Python基础之(八)类

当类中变量引用的是可变对象是，类属性和实例属性都能直接修改这个对象，从而影响另一方的值。

• ### NumPy 将停止支持 Python 2，这里有一份给数据科学家的 Python 3 使用指导

Python 已经成为机器学习和数据科学的主要编程语言，同时 Python 2 和 Python 3 共存与 Python 的生态体系内。不过，在 2019 年...

• ### NetLogon 域内提权漏洞（CVE-2020-1472）复现过程

CVE-2020-1472是一个windows域控中严重的远程权限提升漏洞，攻击者通过NetLogon，建立与域控间易受攻击的安全通道时，可利用此漏洞获取域管访...

• ### 经典 | 10 分钟速成 Python3

Python 是由吉多·范罗苏姆(Guido Van Rossum)在 90 年代早期设计。 它是如今最常用的编程语言之一。它的语法简洁且优美，几乎就是可执行的...

• ### 干货 | 7 步快速入门 Python3

Python 是由吉多·范罗苏姆(Guido Van Rossum)在 90 年代早期设计。 它是如今最常用的编程语言之一。它的语法简洁且优美，几乎就是可执行的...

• ### 37道Python经典面试题（附答案），看完面试不愁了

python多线程有个全局解释器锁（global interpreter lock），这个锁的意思是任一时间只能有一个线程使用解释器，跟单cpu跑多个程序一个意...

• ### Leetcode【120、611、813、915】

容易想到用动态规划求解，dp[i][j] 存储累加到位置 (i, j) 的最小路径和。

• ### 基于PyTorch的计算机视觉框架

http://www.tensorinfinity.com/paper_156.html

• ### 目标检测最新总结与前沿展望

从 2006 年以来，在 Hilton、Bengio、LeChun 等人的引领下，大量深度神经网络的论文被发表，尤其是 2012 年，Hinton课题组首次参加...

• ### 目标检测综述

这张图清楚说明了image classification, object detection, semantic segmentation, instance...

• ### 深度学习「一键P图」：为原画无缝添加新元素

选自arXiv 作者：栾福军等 机器之心编译 参与：路、张倩 把照片中的一个元素「复制粘贴」到绘画作品上，很简单？Nonono… 要想成品不像拼贴画，二者风格一...