javascript - 如何将纯黑白图像转换为多边形集合？

Question

我有一堆纯黑白图像，上面有各种文字和形状。我的目标是将每个图像转换为围绕黑色区域的一组多边形（定义为一组顶点）（就像魔术棒工具可以在照片编辑软件中选择区域一样）。

我更喜欢在 JavaScript 中实现它，但我最感兴趣的是从概念上如何去做。谢谢！

Answer 1

魔术棒在简单位图编辑器中的工作方式是：

令颜色 C 为所选原始点的颜色。让最后一个颜色 LC 是任何颜色。

1. 获取选定点 (x,y)
2. 如果 (x,y) = C 的颜色和未访问的像素
   1. 将坐标存储在数组中
   2. 重复算法 (x+1,y), (x-1,y), (x,y+1), (x,y-1)
3. 将像素存储在访问像素数组中
4. 如果 (x,y) 的颜色 != LC
   1. 将像素标记为数组中的边框像素
   2. 设置 LC = (x,y) 的颜色

Answer 2

当只需要扫描周边时，可以产生“右手在墙上”算法。

第一步：沿着图像向右遍历，找到第一个相反颜色的像素。
步骤 2：按顺时针顺序搜索当前像素的所有相邻像素。
第 3 步：移动到第一个可用像素。存储像素索引
步骤4：重复步骤2-3，直到当前像素是步骤​​1中的起始像素

第 5 步：从存储的像素中检测模式，例如
运行 LLLLLLLLLL、[左] 上、右或下，

形式的模式

RRRRRRR U RRRRRRR U RRRRRRRR U RRRRRRR U ...
<-N--->   <--N-->   <--N+1->   <--N-->

可以用一条线来建模，尽管用“inverse bresenham”来检测一条线段的最佳起点和终点并不容易。

无论如何都可以使用蛮力方法从当前像素到 N 个先前像素绘制一条线，并测试 bresenhams 算法是否产生完全相同的像素。

Answer 3

首先，让我解释一下什么是“边缘”。

边缘是两个连续像素之间的虚拟线。

+---+---+
| A | B |  // The middle line is the edge between pixel A and pixel B
+---+---+

边有起点和终点，因此向上、向下、“向左”或“向右”。

为了处理跨越图像边界的多边形，我们将在图像周围添加一个 1 像素的白色边框。

这是算法：

For each row of our image {  
  For each pixel of the row except the last one {  
    If current pixel is white and next pixel is black {
      Create a new upward edge between the two pixels and add it to
      the global edge list.
    }
    Else if current pixel is black and next pixel is white {
      Create a new downward edge between the two pixels and add it to
      the global edge list.
    }
  }  
}
For each column of our image {  
  For each pixel of the column except the last one {  
    If current pixel is white and next pixel is black {
      Create a new "left going" edge between the two pixels and add it to
      the global edge list.
    }
    Else if current pixel is black and next pixel is white {
      Create a new "right going" edge between the two pixels and add it to
      the global edge list.
    }
  }  
}  

For each edge of the global edge list {
  Find the edge starting from the point where your current edge ends
  (for now on, we gonna call it next_edge).
  Connect the two edges to form a linked list
  (edge->next = next_edge; next_edge->previous = edge;)
}

While there is edges in the global edge list {
  Create a new polygon and add it to the polygon list
  Take the first edge of the list (for now on, we gonna call it first_edge)
  For each edge in the linked list starting at first_edge {
     Remove edge from global edge list
     Add edge to polygon's edge list
  }
}

完成，你有一个多边形列表。

编辑

当然，在使用它之前你必须对其进行一些优化，但这真的很容易：具有相同方向的连续边可以替换为单个更长的边。