分形/复平面的迭代/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 的“图像处理的现代算法”的源代码

另请参见

• 寻路
• 曲线绘图
• 链码
• 像素连通性
• 优化问题
• 孔洞检测
• 边界清理：锯齿状边界被清理（平滑）以获得令人愉悦的形状