8.2 連通元件標記#

概念說明#

給定一張二值影像，連通元件標記 (Connected Component Labeling, CCL) 要把所有相鄰的前景像素歸成群組，每群一個編號。輸出是標籤圖 (label map)：與輸入同尺寸，每個像素的值是它所屬元件的編號（0 代表背景）。有了標籤圖，就能對每個物件計算面積、外框、重心、長寬比——這是「數物件」「量測尺寸」等應用的基礎。

關鍵前置決策是連通性：

4-連通：只算上下左右相鄰。斜角接觸不算連通。
8-連通：上下左右加四個對角。

同一張影像兩種定義的元件數可能不同：兩個只在角落相接的方塊，4-連通下是兩個物件、8-連通下是一個。選擇取決於應用（細字體常用 8-連通避免筆畫斜線斷開）；注意一個不成文的規則：前景用 8-連通時背景應配 4-連通，否則拓撲上會出現矛盾（兩區域互相包圍卻不連通）。

三種經典演算法：

1. 洪泛填充 (flood fill / DFS-BFS)：掃描到未標記的前景像素，就從它開始把整個連通區域走遍並標記。最直觀，適合教學與稀疏前景。

2. 兩趟掃描 (two-pass) + 併查集 (union-find)：第一趟從左到右、從上到下掃描，檢查已看過的鄰居（西、北、西北、東北），給臨時標籤；當鄰居標籤不同時，記下「這兩個標籤等價」。第二趟把等價的標籤統一成最小值。併查集用兩個優化：路徑壓縮 + 按 rank 合併，使每次查找近乎 O(1)。這是記憶體友善、適合大影像與串流處理的方法。

3. Row-projection（行程式）：以「連續段落 (run)」為單位處理，把相鄰列中重疊的 run 合併。工業級函式庫（如 OpenCV 的 connectedComponents）用此法，快。

洪泛的迭代深度問題：遞迴 DFS 在大元件上會爆棧（1000×1000 的全白影像需要 10⁶ 層遞迴），必須用明確堆疊或佇列。

演算法步驟（洪泛法）#

建立標籤圖 label（全 0），next_label = 1。
從上到下、從左到右掃描：遇前景且 label 為 0，則以該點為種子。
種子推入堆疊，開始 DFS：彈出 (y, x)，設 label = next_label，把 4 或 8 個鄰居中「前景且未標記」者推入堆疊。
堆疊清空後 next_label += 1，回到掃描。
掃描結束，輸出標籤圖與元件統計。

Python 程式碼範例#

import numpy as np
from collections import deque

def label_components(bin_img, conn=8):
    H, W = bin_img.shape
    label = np.zeros((H, W), np.int32)
    offsets = ([(-1,0),(1,0),(0,-1),(0,1)] if conn == 4 else
               [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)])
    n = 0
    for y in range(H):
        for x in range(W):
            if bin_img[y, x] and label[y, x] == 0:
                n += 1
                q = deque([(y, x)])
                label[y, x] = n
                while q:
                    cy, cx = q.popleft()          # BFS，防爆棧
                    for dy, dx in offsets:
                        ny, nx = cy+dy, cx+dx
                        if 0 <= ny < H and 0 <= nx < W \
                           and bin_img[ny, nx] and label[ny, nx] == 0:
                            label[ny, nx] = n
                            q.append((ny, nx))
    return label, n

# 測試：三個物件，其中兩個對角相觸
b = np.zeros((10, 12), np.uint8)
b[2:5, 2:5] = 1
b[4:7, 6:9] = 1
b[8, 11] = 1; b[1, 10] = 1                # 兩個孤立點

for c in (4, 8):
    lab, n = label_components(b, c)
    print(f"{c}-連通: 元件數 = {n}")
lab8, _ = label_components(b, 8)
print("對角相觸處在 8-連通下同標籤:", lab8[4, 4] == lab8[5, 6])

# 元件統計：面積、外框、重心
lab, n = label_components(b, 8)
for i in range(1, n+1):
    ys, xs = np.where(lab == i)
    print(f"元件 {i}: 面積={len(ys)}, 重心=({ys.mean():.1f},{xs.mean():.1f}), "
          f"外框 y[{ys.min()}:{ys.max()}] x[{xs.min()}:{xs.max()}]")

執行後：4-連通下 5 個元件（兩個方塊對角相觸不算連通，兩個點各自獨立——共 5 個）；8-連通下兩個斜觸的方塊合併為 1，總數變 4。每個元件的面積、重心與外框直接可得，這些正是之後「形狀特徵」與「物件計數」的原料。

複雜度分析#

洪泛法：每個像素至多推入/彈出一次、檢查常數個鄰居，O(N)。空間：標籤圖 O(N)，佇列最壞 O(N)（全白影像 BFS 鋒面可達 O(√N)~O(N)，視形狀而定）。兩趟法同樣 O(N) 但佇列成本為零，alpha（單趟掃描+等價表）更省記憶體。併查集的均攤複雜度是反阿克曼函數 α(N) ≤ 5，視為常數。實務建議：教學與小圖用洪泛；大圖、記憶體受限、或需要增量處理用兩趟法；極致效能用行程式法或 GPU 版。連通性選擇不影響漸進複雜度，只影響常數（8-連通多檢查 4 個鄰居）。

練習#

實作兩趟法（含併查集），對 200×200 隨機二值影像與洪泛法比對標籤結果（允許編號不同，比較分組是否一致）。
把「全白 1000×1000」的影像分別用遞迴 DFS 與 BFS 洪泛跑，驗證遞迴版會棧溢位而 BFS 不會，並說明原因。
在標籤之後計算每個元件的「圓形度 4π·面積/周長²」，找出影像中最圓的物件；思考周長該怎麼在像素網格上定義才穩定。