分形/複平面的迭代/btm

如何在二維網格點中識別外邊界？

名稱

• 邊界劃分
• 邊緣檢測
• 輪廓追蹤

型別

• 一次一個元件（邊界追蹤）
• 所有元件一次（邊緣檢測）

BTM

邊界追蹤方法 (BTM)

邊界追蹤 二進位制數字區域可以被認為是一種分割技術，它識別數字區域的邊界畫素。邊界追蹤是分析該區域的重要第一步。

定義

邊界是一個拓撲概念。但是，數字影像不是拓撲空間。因此，無法用數學方法精確地定義數字影像中邊界概念。大多數關於追蹤數字影像 I 的子集 S 邊界的出版物描述了演算法，這些演算法找到屬於 S 的一組畫素，並在它們的直接鄰域中包含屬於 S 和其補集 I - S 的畫素。根據這個定義，子集 S 的邊界不同於補集 I – S 的邊界，這是一個拓撲悖論。

為了正確定義邊界，有必要引入一個對應於給定數字影像的拓撲空間。這樣的空間可以是二維抽象細胞複合體。它包含三個維度的單元格：對應於數字影像畫素的二維單元格，表示位於兩個相鄰畫素之間的短線的 一維單元格或“裂縫”，以及對應於畫素角點的 零維單元格或“點”。然後，子集 S 的邊界是裂縫和點的序列，而這些裂縫和點的鄰域與子集 S 和其補集 I – S 都相交。以這種方式定義的邊界完全對應於拓撲定義，也對應於我們對邊界的直觀想象，因為 S 的邊界不應包含 S 的元素，也不應包含其補集的元素。它只應包含位於 S 和補集之間的元素。這些正是複合體中的裂縫和點。

這種邊界追蹤方法在弗拉基米爾·A·科瓦列夫斯基的書中 和網站 中有描述。

演算法

用於邊界追蹤的演算法：

• 方格追蹤演算法
• 摩爾鄰域追蹤演算法
• 徑向掃描
• 西奧·帕夫裡迪斯演算法
• 可以在以下位置找到使用向量代數進行邊界追蹤的通用方法：
• 邊界追蹤的擴充套件，用於將追蹤到的邊界分割成開放和封閉子部分，在以下位置有描述：

方格追蹤演算法

方格追蹤演算法很簡單，但很有效。它的行為完全取決於你是在黑色單元格還是白色單元格中（假設白色單元格是形狀的一部分）。首先，從左上角向右，逐行掃描。當你進入第一個白色單元格時，演算法的核心開始執行。它主要由兩個規則組成

• 如果你在白色單元格中，向左移動。
• 如果你在黑色單元格中，向右移動。

請記住，你如何進入當前單元格很重要，因此可以定義左右。

public void GetBoundary(byte[,] image)
{
    for (int j = 0; j < image.GetLength(1); j++)
        for (int i = 0; i < image.GetLength(0); i++)
            if (image[i, j] == 255)               // Found first white pixel
                SquareTrace(new Point(i, j));
}

public void SquareTrace(Point start)
{
    HashSet<Point> boundaryPoints = new HashSet<Point>();  // Use a HashSet to prevent double occurrences
    // We found at least one pixel
    boundaryPoints.Add(start);

    // The first pixel you encounter is a white one by definition, so we go left. 
    // Our initial direction was going from left to right, hence (1, 0)
    Point nextStep = GoLeft(new Point(1, 0));               
    Point next = start + nextStep;
    while (next != start)
    {
        // We found a black cell, so we go right and don't add this cell to our HashSet
        if (image[next.x, next.y] == 0)
        {
            next = next - nextStep;
            nextStep = GoRight(nextStep);
            next = next + nextStep;
        }
        // Alternatively we found a white cell, we do add this to our HashSet
        else
        {
            boundaryPoints.Add(next);
            nextStep = GoLeft(nextStep);
            next = next + nextStep;
        }
    }
}

private Point GoLeft(Point p) => new Point(p.y, -p.x);
private Point GoRight(Point p) => new Point(-p.y, p.x);

摩爾鄰域追蹤演算法

摩爾鄰域由九個單元格組成：一箇中心單元格和包圍它的八個單元格。

摩爾鄰域公式背後的想法是找到給定圖的輪廓。這個想法對 18 世紀的大多數分析家來說是一個巨大的挑戰，結果，從摩爾圖推匯出一個演算法，後來被稱為摩爾鄰域演算法。

演算法：

• 以行方式遍歷二維矩陣
• 將第一個非零畫素設定為 S（邊界起點）
• 將當前畫素設定為 p；將這個非零畫素新增到邊界畫素列表中
• 將 p 進入的先前畫素設定為 b（回溯畫素）
• 取 p 的 3 * 3 鄰域，並在順時針方向上從 b 開始，順時針搜尋下一個非零畫素
• 重複步驟 3 到 5，直到 p 與 S 相同

摩爾鄰域追蹤演算法的虛擬碼是

Input: A square tessellation, T, containing a connected component P of black cells.
Output: A sequence B (b1, b2, ..., bk) of boundary pixels i.e. the contour.
Define M(a) to be the Moore neighborhood of pixel a.
Let p denote the current boundary pixel.
Let c denote the current pixel under consideration i.e. c is in M(p).
Let b denote the backtrack of c (i.e. neighbor pixel of p that was previously tested)
 
Begin
  Set B to be empty.
  From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
  Insert s in B.
  Set the current boundary point p to s i.e. p=s
  Let b = the pixel from which s was entered during the image scan.
  Set c to be the next clockwise pixel (from b) in M(p).
  While c not equal to s do
    If c is black
      insert c in B
      Let b = p
      Let p = c
      (backtrack: move the current pixel c to the pixel from which p was entered)
      Let c = next clockwise pixel (from b) in M(p).
    else
      (advance the current pixel c to the next clockwise pixel in M(p) and update backtrack)
      Let b = c
      Let c = next clockwise pixel (from b) in M(p).
    end If
  end While
End

終止條件

最初的終止條件是在第二次訪問起點畫素後停止。這限制了演算法將完全遍歷的輪廓集。雅各布·埃里奧索夫提出的一個改進的停止條件是在以你最初進入的方向第二次進入起點畫素後停止。

BSM/J

BSM = 邊界掃描方法

當動力學平面由兩個或多個吸引盆地組成時，使用此演算法。例如，對於 c=0。

當填充的朱利亞集的內部為空時，它不適合，例如對於 c=i。

演算法描述

• 對於動力學平面的每個畫素 $z$ 執行以下操作
  • 計算畫素的四個角點（頂點）$z_{lt},z_{rt},z_{rb},z_{lb}$ （其中 lt 表示左上角，rb 表示右下角，等等）
  • 檢查角點屬於哪個盆地（標準逃逸時間和退出測試）
  • 如果角點不屬於同一個盆地，則將其標記為朱利亞集

程式碼示例

• Pascal 程式
• 透過使用核心進行卷積

字典

• 影像
  • 二維
  • “分割”影像（前景畫素標記為 1，背景畫素標記為零）= 二值影像
• 連通性和鄰域
  • 4
  • 8
• 邊界 = 邊界輪廓 = 輪廓
  • 內邊界（前景的最外畫素）
  • 外邊界（背景的最內畫素）
• 軌跡（跟蹤）
  • Abeer George Ghuneim 的輪廓跟蹤演算法

論文

• 二值影像中的邊界跟蹤
• Wilhelm Burger · Mark J. Burge：數字影像處理 使用 Java 的演算法介紹

影片

• Gnarly Charley 的曼德博集動畫（邊界跟蹤/遞迴）

程式碼

• fractint
• Gnarly Charley (charlesk26) 的 Java 程式碼（來自影片）
• Udaya K Unnikrishnan 的使用 C++ 中的 Moore 鄰域方法的二維影像邊界跟蹤
• ERIK SMISTAD 的 C++ 中的 Moore 鄰域輪廓跟蹤演算法
• Potrace(TM) 是 Peter Selinger 用來跟蹤點陣圖的工具
• 跟蹤一組點的邊界（python）
• Vladimir Kovalevsky 的“影像處理的現代演算法”的原始碼

另請參見

• 尋路
• 曲線繪圖
• 鏈碼
• 畫素連通性
• 最佳化問題
• 孔洞檢測
• 邊界清理：鋸齒狀邊界被清理（平滑）以獲得令人愉悅的形狀