連通分量標記

連通分量標記（或者稱連通分量分析,連通區域標記）是圖論應用中的一種算法，給二值圖像中的每個連通區域標上一個特定的標號。該算法可用來對圖像的目標進行定位和計數。該算法不要和圖像分割相混淆。

連通分量標記通常在計算機視覺領域中對二值圖像的連通區域進行檢測，也可以處理彩色圖像和更高維的數據。當將其集成到圖像識別系統或者是人機互動系統時，該算法也起到重要作用。

概述

4-鄰域

8-鄰域

中間像素和它周圍像素的位置決定了是幾鄰域連接，4鄰域連接是周圍像素處在中間像素的上下左右的位置，8鄰域連接則還包括其對角的4個像素的位置。

算法

兩次掃描算法的圖形解釋

以一個8領域的例子來說明兩次掃描算法。 該算法的資料結構為併查集。 1，第一次掃描： 將0視為背景像素，1為目標像素。原始圖像如下。

從左往右從上到下掃描，背景像素保持0不變，遇到1值時，分析它的8鄰域（只考慮已被掃描的的像素點，即左邊、左上、上和右上這四個方向的像素值）

1. 如果這四個方向的值都是0，那麼該位置就創建一個新的標號（在原標號上加1）；
2. 如果這四個方向的非0值（即標號）都一樣，那麼該位置標號就是其領域的非0標號；
3. 如果這四個方向的非0值有兩個不同的標號，那麼該位置標號就選其中之一，並記錄這兩個不同的標號（因為這兩個標號是連通的，故視為等同的標號）；

第一次掃描結束後得到如下標好號的圖：

並且同時得到哪些標號相同的。

Set ID	Equivalent Labels
1	1,2
2	1,2
3	3,4,5,6,7
4	3,4,5,6,7
5	3,4,5,6,7
6	3,4,5,6,7
7	3,4,5,6,7

2，第二次掃描： 合併這些相同的標號，得到結果

最後可以將這兩個區域以不同顏色顯示出來

其偽代碼如下：

 algorithm TwoPass(data)
   linked = []
   labels = structure with dimensions of data, initialized with the value of Background

   First pass

   for row in data:
       for column in row:
           if data[row][column] is not Background

               neighbors = connected elements with the current element's value

               if neighbors is empty
                   linked[NextLabel] = set containing NextLabel
                   labels[row][column] = NextLabel
                   NextLabel += 1

               else

                   Find the smallest label

                   L = neighbors labels
                   labels[row][column] = min(L)
                   for label in L
                       linked[label] = union(linked[label], L)

   Second pass

   for row in data
       for column in row
           if data[row][column] is not Background
               labels[row][column] = find(labels[row][column])

   return labels