運用Python3實現(xiàn)Two-Pass算法檢測區(qū)域連通性

更新時間：2021年08月18日 17:16:38 作者：DECHIN

如何高效的檢測出連通區(qū)域的流動性是大家一直關(guān)注的話題，這篇文章主要介紹了運用Python3實現(xiàn)Two-Pass算法檢測區(qū)域連通性，感興趣的朋友可以一起來看看

技術(shù)背景

連通性檢測是圖論中常常遇到的一個問題，我們可以用五子棋的思路來理解這個問題五子棋中，橫、豎、斜相鄰的兩個棋子，被認(rèn)為是相連接的，而一樣的道理，在一個二維的圖中，只要在橫、豎、斜三個方向中的一個存在相鄰的情況，就可以認(rèn)為圖上相連通的。比如以下案例中的python數(shù)組，3號元素和5號元素就是相連接的，5號元素和6號元素也是相連接的，因此這三個元素實際上是屬于同一個區(qū)域的：

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

而再如下面這個例子，其中的1、2、3三個元素是相連的，4、5、6三個元素也是相連的，但是這兩個區(qū)域不存在連接性，因此這個網(wǎng)格被分成了兩個區(qū)域：

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

那么如何高效的檢測一張圖片或者一個矩陣中的所有連通區(qū)域并打上標(biāo)簽，就是我們所關(guān)注的一個問題。

Two-Pass算法

一個典型的連通性檢測的方案是Two-Pass算法，該算法可以用如下的一張動態(tài)圖來演示：

該算法的核心在于用兩次的遍歷，為所有的節(jié)點打上分區(qū)的標(biāo)簽，如果是不同的分區(qū)，就會打上不同的標(biāo)簽。其基本的算法步驟可以用如下語言進行概述：

遍歷網(wǎng)格節(jié)點，如果網(wǎng)格的上、左、左上三個格點不存在元素，則為當(dāng)前網(wǎng)格打上新的標(biāo)簽，同時標(biāo)簽編號加一；
當(dāng)上、左、左上的網(wǎng)格中存在一個元素時，將該元素值賦值給當(dāng)前的網(wǎng)格作為標(biāo)簽；
當(dāng)上、左、左上的網(wǎng)格中有多個元素時，取最低值作為當(dāng)前網(wǎng)格的標(biāo)簽；
在標(biāo)簽賦值時，留意標(biāo)簽上邊和左邊已經(jīng)被遍歷過的4個元素，將4個元素中的最低值與這四個元素分別添加到Union的數(shù)據(jù)結(jié)構(gòu)中（參考鏈接1）；
再次遍歷網(wǎng)格節(jié)點，根據(jù)Union數(shù)據(jù)結(jié)構(gòu)中的值刷新網(wǎng)格中的標(biāo)簽值，最終得到劃分好區(qū)域和標(biāo)簽的元素矩陣。

測試數(shù)據(jù)的生成

這里我們以Python3為例，可以用Numpy來產(chǎn)生一系列隨機的0-1矩陣，這里我們產(chǎn)生一個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]]

同時會生成一張網(wǎng)格的圖片：

其實從這個圖片中我們可以看出，圖片的上面部分幾乎都是連接在一起的，只有最下面存在幾個獨立的區(qū)域。

Two-Pass算法的實現(xiàn)

這里需要說明的是，因為我們并沒有使用Union的數(shù)據(jù)結(jié)構(gòu)，而是只使用了Python的字典數(shù)據(jù)結(jié)構(gòu)，因此代碼寫起來會比較冗余而且不是那么美觀，但是這里我們主要的目的是先用代解決這一實際問題，因此代碼亂就亂一點吧。

# 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]]

同樣的我們可以看看此時得到的新的圖像：

這里我們并列的畫了三張圖，第一張圖是原圖，第二張圖是劃分好區(qū)域和標(biāo)簽的圖，第三張是對第二張圖進行二元化的結(jié)果，以確保在運算過程中沒有丟失原本的信息。經(jīng)過確認(rèn)這個標(biāo)簽的結(jié)果劃分是正確的，但是因為涉及到一些算法實現(xiàn)的細節(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)

這個部分是算法的核心框架，在本文中的算法實現(xiàn)流程為：先用first_pass遍歷一遍網(wǎng)格節(jié)點，按照上一個章節(jié)中介紹的Two-Pass算法打上標(biāo)簽，并獲得一個映射關(guān)系；然后用remap將上面得到的映射關(guān)系做一個重映射，確保每一個級別的映射都對應(yīng)到了最根部（可以聯(lián)系參考鏈接1的內(nèi)容進行理解，雖然這里沒有使用Union的數(shù)據(jù)結(jié)構(gòu)，但是本質(zhì)上還是一個樹形的結(jié)構(gòu)，需要做一個重映射）；然后用second_pass執(zhí)行Two-Pass算法的第二次遍歷，得到一組打上了新的獨立標(biāo)簽的網(wǎng)格節(jié)點；最后需要用flatten將標(biāo)簽進行壓平，因為前面映射的關(guān)系，有可能導(dǎo)致標(biāo)簽不連續(xù)，所以我們這里又做了一次映射，確保標(biāo)簽是連續(xù)變化的，實際應(yīng)用中可以不使用這一步。

標(biāo)簽的重映射

關(guān)于節(jié)點的遍歷，大家可以直接看算法代碼，這里需要額外講解的是標(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

這里的算法是先對得到的標(biāo)簽進行遍歷，在字典中獲取當(dāng)前標(biāo)索引所對應(yīng)的值，作為新的索引，直到鍵跟值一致為止，相當(dāng)于在一個樹形的數(shù)據(jù)結(jié)構(gòu)中重復(fù)尋找父節(jié)點直到找到根節(jié)點。

其他的測試用例

這里我們可以再額外測試一些案例，比如增加幾個0元素使得網(wǎng)格節(jié)點更加稀疏：

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的算法來檢測區(qū)域連通性，并給出了Python3的代碼實現(xiàn)，當(dāng)然在實現(xiàn)的過程中因為沒有使用到Union這樣的數(shù)據(jù)結(jié)構(gòu)，僅僅用了字典來存儲標(biāo)簽之間的關(guān)系，因此效率和代碼可讀性都會低一些，單純作為用例的演示和小規(guī)模區(qū)域劃分的計算是足夠用了。在該代碼實現(xiàn)方案中，還有一點與原始算法不一致的是，本實現(xiàn)方案中打新的標(biāo)簽是讀取上、上左和左三個方向的格點，但是存儲標(biāo)簽的映射關(guān)系時，是讀取了上、上左、上右和左這四個方向的格點。

參考鏈接

https://blog.csdn.net/lichengyu/article/details/13986521
https://www.cnblogs.com/riddick/p/8280883.html

到此這篇關(guān)于運用Python3實現(xiàn)Two-Pass算法檢測區(qū)域連通性的文章就介紹到這了,更多相關(guān)Python3實現(xiàn)Two-Pass算法檢測區(qū)域流通內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: