運用Python3實現Two-Pass算法檢測區域連通性

Posted on by

技術背景

連通性檢測是圖論中常常遇到的一個問題，我們可以用五子棋的思路來理解這個問題五子棋中，橫、豎、斜相鄰的兩個棋子，被認為是相連接的，而一樣的道理，在一個二維的圖中，隻要在橫、豎、斜三個方向中的一個存在相鄰的情況，就可以認為圖上相連通的。比如以下案例中的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算法，該算法可以用如下的一張動態圖來演示：

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

  1. 遍歷網格節點，如果網格的上、左、左上三個格點不存在元素，則為當前網格打上新的標簽，同時標簽編號加一；
  2. 當上、左、左上的網格中存在一個元素時，將該元素值賦值給當前的網格作為標簽；
  3. 當上、左、左上的網格中有多個元素時，取最低值作為當前網格的標簽；
  4. 在標簽賦值時，留意標簽上邊和左邊已經被遍歷過的4個元素，將4個元素中的最低值與這四個元素分別添加到Union的數據結構中（參考鏈接1）；
  5. 再次遍歷網格節點，根據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這樣的數據結構，僅僅用瞭字典來存儲標簽之間的關系，因此效率和代碼可讀性都會低一些，單純作為用例的演示和小規模區域劃分的計算是足夠用瞭。在該代碼實現方案中，還有一點與原始算法不一致的是，本實現方案中打新的標簽是讀取上、上左和左三個方向的格點，但是存儲標簽的映射關系時，是讀取瞭上、上左、上右和左這四個方向的格點。

參考鏈接

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

到此這篇關於運用Python3實現Two-Pass算法檢測區域連通性的文章就介紹到這瞭,更多相關Python3實現Two-Pass算法檢測區域流通內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：