運(yùn)用Python3實(shí)現(xiàn)Two-Pass算法檢測(cè)區(qū)域連通性
技術(shù)背景
連通性檢測(cè)是圖論中常常遇到的一個(gè)問題，我們可以用五子棋的思路來理解這個(gè)問題五子棋中，橫、豎、斜相鄰的兩個(gè)棋子，被認(rèn)為是相連接的，而一樣的道理，在一個(gè)二維的圖中，只要在橫、豎、斜三個(gè)方向中的一個(gè)存在相鄰的情況，就可以認(rèn)為圖上相連通的。比如以下案例中的python數(shù)組，3號(hào)元素和5號(hào)元素就是相連接的，5號(hào)元素和6號(hào)元素也是相連接的，因此這三個(gè)元素實(shí)際上是屬于同一個(gè)區(qū)域的：
array([[0, 3, 0], [0, 5, 0], [6, 0, 0]])
而再如下面這個(gè)例子，其中的1、2、3三個(gè)元素是相連的，4、5、6三個(gè)元素也是相連的，但是這兩個(gè)區(qū)域不存在連接性，因此這個(gè)網(wǎng)格被分成了兩個(gè)區(qū)域：
array([[1, 0, 4], [2, 0, 5], [3, 0, 6]])
那么如何高效的檢測(cè)一張圖片或者一個(gè)矩陣中的所有連通區(qū)域并打上標(biāo)簽，就是我們所關(guān)注的一個(gè)問題。
Two-Pass算法
一個(gè)典型的連通性檢測(cè)的方案是Two-Pass算法，該算法可以用如下的一張動(dòng)態(tài)圖來演示：
該算法的核心在于用兩次的遍歷，為所有的節(jié)點(diǎn)打上分區(qū)的標(biāo)簽，如果是不同的分區(qū)，就會(huì)打上不同的標(biāo)簽。其基本的算法步驟可以用如下語言進(jìn)行概述：
- 遍歷網(wǎng)格節(jié)點(diǎn)，如果網(wǎng)格的上、左、左上三個(gè)格點(diǎn)不存在元素，則為當(dāng)前網(wǎng)格打上新的標(biāo)簽，同時(shí)標(biāo)簽編號(hào)加一；
- 當(dāng)上、左、左上的網(wǎng)格中存在一個(gè)元素時(shí)，將該元素值賦值給當(dāng)前的網(wǎng)格作為標(biāo)簽；
- 當(dāng)上、左、左上的網(wǎng)格中有多個(gè)元素時(shí)，取最低值作為當(dāng)前網(wǎng)格的標(biāo)簽；
- 在標(biāo)簽賦值時(shí)，留意標(biāo)簽上邊和左邊已經(jīng)被遍歷過的4個(gè)元素，將4個(gè)元素中的最低值與這四個(gè)元素分別添加到Union的數(shù)據(jù)結(jié)構(gòu)中（參考鏈接1）；
- 再次遍歷網(wǎng)格節(jié)點(diǎn)，根據(jù)Union數(shù)據(jù)結(jié)構(gòu)中的值刷新網(wǎng)格中的標(biāo)簽值，最終得到劃分好區(qū)域和標(biāo)簽的元素矩陣。
測(cè)試數(shù)據(jù)的生成
這里我們以Python3為例，可以用Numpy來產(chǎn)生一系列隨機(jī)的0-1矩陣，這里我們產(chǎn)生一個(gè)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')
執(zhí)行的輸出結(jié)果如下：
$ 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]]
同時(shí)會(huì)生成一張網(wǎng)格的圖片：
其實(shí)從這個(gè)圖片中我們可以看出，圖片的上面部分幾乎都是連接在一起的，只有最下面存在幾個(gè)獨(dú)立的區(qū)域。
Two-Pass算法的實(shí)現(xiàn)
這里需要說明的是，因?yàn)槲覀儾]有使用Union的數(shù)據(jù)結(jié)構(gòu)，而是只使用了Python的字典數(shù)據(jù)結(jié)構(gòu)，因此代碼寫起來會(huì)比較冗余而且不是那么美觀，但是這里我們主要的目的是先用代解決這一實(shí)際問題，因此代碼亂就亂一點(diǎn)吧。
# 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]]
同樣的我們可以看看此時(shí)得到的新的圖像：
這里我們并列的畫了三張圖，第一張圖是原圖，第二張圖是劃分好區(qū)域和標(biāo)簽的圖，第三張是對(duì)第二張圖進(jìn)行二元化的結(jié)果，以確保在運(yùn)算過程中沒有丟失原本的信息。經(jīng)過確認(rèn)這個(gè)標(biāo)簽的結(jié)果劃分是正確的，但是因?yàn)樯婕暗揭恍┧惴▽?shí)現(xiàn)的細(xì)節(jié)，這里我們還是需要展開來介紹一下。
算法的執(zhí)行流程
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)
這個(gè)部分是算法的核心框架，在本文中的算法實(shí)現(xiàn)流程為：先用first_pass遍歷一遍網(wǎng)格節(jié)點(diǎn)，按照上一個(gè)章節(jié)中介紹的Two-Pass算法打上標(biāo)簽，并獲得一個(gè)映射關(guān)系；然后用remap將上面得到的映射關(guān)系做一個(gè)重映射，確保每一個(gè)級(jí)別的映射都對(duì)應(yīng)到了最根部（可以聯(lián)系參考鏈接1的內(nèi)容進(jìn)行理解，雖然這里沒有使用Union的數(shù)據(jù)結(jié)構(gòu)，但是本質(zhì)上還是一個(gè)樹形的結(jié)構(gòu)，需要做一個(gè)重映射）；然后用second_pass執(zhí)行Two-Pass算法的第二次遍歷，得到一組打上了新的獨(dú)立標(biāo)簽的網(wǎng)格節(jié)點(diǎn)；最后需要用flatten將標(biāo)簽進(jìn)行壓平，因?yàn)榍懊嬗成涞年P(guān)系，有可能導(dǎo)致標(biāo)簽不連續(xù)，所以我們這里又做了一次映射，確保標(biāo)簽是連續(xù)變化的，實(shí)際應(yīng)用中可以不使用這一步。
標(biāo)簽的重映射
關(guān)于節(jié)點(diǎn)的遍歷，大家可以直接看算法代碼，這里需要額外講解的是標(biāo)簽的重映射模塊的代碼：
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
這里的算法是先對(duì)得到的標(biāo)簽進(jìn)行遍歷，在字典中獲取當(dāng)前標(biāo)索引所對(duì)應(yīng)的值，作為新的索引，直到鍵跟值一致為止，相當(dāng)于在一個(gè)樹形的數(shù)據(jù)結(jié)構(gòu)中重復(fù)尋找父節(jié)點(diǎn)直到找到根節(jié)點(diǎn)。
其他的測(cè)試用例
這里我們可以再額外測(cè)試一些案例，比如增加幾個(gè)0元素使得網(wǎng)格節(jié)點(diǎn)更加稀疏：
graph = np.random.choice([0,0,0,1],size=(20,20))
得到的結(jié)果圖片如下所示：
還可以再稀疏一些：
graph = np.random.choice([0,0,0,0,0,1],size=(20,20))
得到的結(jié)果如下圖所示：
越是稀疏的圖，得到的分組結(jié)果就越分散。
總結(jié)概要
在本文中我們主要介紹了利用Two-Pass的算法來檢測(cè)區(qū)域連通性，并給出了Python3的代碼實(shí)現(xiàn)，當(dāng)然在實(shí)現(xiàn)的過程中因?yàn)闆]有使用到Union這樣的數(shù)據(jù)結(jié)構(gòu)，僅僅用了字典來存儲(chǔ)標(biāo)簽之間的關(guān)系，因此效率和代碼可讀性都會(huì)低一些，單純作為用例的演示和小規(guī)模區(qū)域劃分的計(jì)算是足夠用了。在該代碼實(shí)現(xiàn)方案中，還有一點(diǎn)與原始算法不一致的是，本實(shí)現(xiàn)方案中打新的標(biāo)簽是讀取上、上左和左三個(gè)方向的格點(diǎn)，但是存儲(chǔ)標(biāo)簽的映射關(guān)系時(shí)，是讀取了上、上左、上右和左這四個(gè)方向的格點(diǎn)。
參考鏈接
- https://blog.csdn.net/lichengyu/article/details/13986521
- https://www.cnblogs.com/riddick/p/8280883.html
到此這篇關(guān)于運(yùn)用Python3實(shí)現(xiàn)Two-Pass算法檢測(cè)區(qū)域連通性的文章就介紹到這了,更多相關(guān)Python3實(shí)現(xiàn)Two-Pass算法檢測(cè)區(qū)域流通內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信