4

我有一个 64x64 的灰度图像。我通过一个简单的算法找到了轮廓的点：

  • 找到最亮的点（例如：100）
  • 除以 2 (100/2 = 50)
  • 在结果周围定义一个带（50-5=45 到 50+5=55）
  • 标记带中所有有价值的点（45到55之间）

现在的问题是，我如何决定连接点的顺序？

（所有参考资料、链接、想法等都将被接受）

4

6 回答 6

4

您的算法允许整个图像（除了一个像素）成为“轮廓”。我不确定这正是您想要的。通常，轮廓是两个不同区域之间的边界。您的方法的问题在于，您可以获得没有特别明显的遍历顺序的大量像素。如果你有一个单像素厚的轮廓，那么遍历顺序就更明显了：顺时针或逆时针。

考虑下图。

........
..%%%%..
.%%%%...
...%%%%.
....%...
........

在这里，我将所有“暗”（可能小于 50）标记为%，将所有亮标记为.. 现在您可以选择两个区域之间边界上的任何像素（我将选择黑暗的一面；您也可以在明亮的一面绘制轮廓，或者做更多的工作，直接在光明和黑暗的一面之间。 )

........
..%%%%..
.*%%%...
...%%%%.
....%...
........

现在您尝试沿着黑暗区域的外边缘移动，一次一个像素。首先，你看向明亮事物的方向（例如，直接向左）。然后你旋转——比方说逆时针——直到你碰到一个暗像素。

........
..%%%%..
1*5%%...
234%%%%.
....%...
........

一旦你点击 position 5，你就会看到它是黑暗的。因此，您将其标记为轮廓的一部分，然后尝试通过从您刚刚来自的像素开始四处扫描来找到轮廓上的下一块

........
..%%%%..
.0*%%...
.123%%%.
....%...
........

这0就是你来自的地方——你不会回到那里——然后你尝试像素1和2（都是亮的，这不好），直到你点击像素3，这是黑暗的。

通过这种方式，您可以逐个像素地围绕轮廓走动——既可以识别轮廓，又可以获取像素的顺序——直到你与开始时的同一个像素发生碰撞，然后离开它，这样你就碰到了相同的像素你第一次离开的时候就这么做了。然后轮廓闭合。在我们的示例中，我们正在制作一个 8 连接的轮廓（即，我们查看 8 个邻居，而不是 4 个），我们会得到以下内容（其中@表示轮廓点）。

........
..@@@@..
.@@%@...
...@%@@.
....@...
........

（你必须有这个两行标准，或者如果你有一个单像素宽的黑暗区域，你会向上走，但不能沿着它往下走。）

至此，您已经覆盖了整个边界。但可能还有其他人。继续寻找亮像素旁边的暗像素，直到在所有像素之上绘制轮廓。现在，您已将两级图片（暗像素和亮像素）转换为一组轮廓。

如果轮廓最终过于嘈杂，请考虑先模糊图像。这将使轮廓平滑。（或者，您可以先找到轮廓，然后使用移动窗口平均坐标。）

于 2010-08-16T13:55:49.783 回答
1

I have also tried to create an algorithm that will connect contour dots into the smooth curve. See my open-source project http://outliner.codeplex.com. The idea is the same as proposed by FUZxxl but I do not understand his worries about complexity: the time of processing is proportional to the total length of all contour strokes.

于 2010-12-24T08:05:33.083 回答
1

一般来说，一组给定的点可以以多种方式连接以形成不同的形状。

例如，考虑一组由正方形的角及其中心组成的 5 个点。这些点可以连接起来形成一个正方形，其中一侧“凹陷”到中心。但是哪一边？没有唯一的答案。

其他形状可能要复杂得多，没有明显的方法来连接这些点。

如果允许您将一组点减少到一个凸包，那么它会容易得多。

于 2010-08-16T13:03:41.110 回答
0

我不知道收集这些积分是否会让你走得更远。（我可以想出一些几乎不可能告诉他们应该进入哪个顺序的情况。）

去最亮的地方怎么样。
转到该点周围的亮度点，例如 360 个点，距离例如 5 个像素。
从那里继续，但要确保你不要回到你来自的地方:)

于 2010-08-16T12:44:31.307 回答
0

另请参阅SO mapping-a-branching-tile-path下的Flood fill 和可爱的小程序 。

于 2010-11-05T10:14:13.207 回答
0

也许尝试：

  1. 从一个开始
  2. 找到最近的点 b
  3. 连接 a 和 b
  4. 等等。

可能不好，因为复杂性类似于 O(n²)。正如 aioobe 建议的那样，您可以通过仅查找开始附近的点来简化此操作。这个算法很好，如果点之间的距离只有 2-3px，但可能会创建非常奇怪的网格。

于 2010-08-16T12:57:44.263 回答