寻找用于查找颜色区域边界的算法。

Question

我有一张画布并在上面绘制了图像。

当用户点击图像时，我需要找到用户点击的颜色区域。一个区域被定义为具有与被点击像素相同颜色的4向连接像素集合。

我需要以一种形式获取该区域，以便在画布上设置剪辑路径，以便我可以使用渐变等来填充该区域。

是否有有效的算法可以找到边界？是否有比泛洪填充算法更优化的算法（我不需要填充，只需要找到我的区域周围的路径）？

- akonsu

---

如果没有单一的边界，例如点击一个环面或笑脸的脸颊，您希望发生什么？ - Phrogz

对于我的应用程序来说，获取描述外部区域的路径就足够了，除非获取同时描述内部和外部区域的路径集合不会更加昂贵。我怀疑我需要某种像素标记算法，然后通过计算连接组件来统一标记的阶段。 - akonsu

Answer 1

我相信 Moore 邻域跟踪算法会满足您的需求。根据定义，Moore 邻域考虑 8 连通性，但您应该可以轻松地将其调整为 4 连通性。如果您测试 8 连通性，则生成的区域可能更好，但您的应用程序可能具有特定要求。

维基百科在这里提供了算法的良好概述here。我过去曾与此一起工作，并取得了巨大成功--它非常快速。

- Xenethyl

---

谢谢。这种方法唯一的问题是如何找到起始像素。在我的情况下，我需要跟踪一个区域的轮廓，而且它不是图像中唯一的区域，所以我不能只从角落开始扫描图像。 - akonsu

如果您从用户鼠标点击的位置开始迭代，得到的轮廓将是所需区域的轮廓。一般的想法是从左到右走，直到遇到不同颜色的像素。找到这样的像素后，您会顺时针方向查看所有邻居，并移动到当前区域的第一个像素。最终您会得到一个轮廓。您不必从角落开始扫描图像。 - Xenethyl

假设我在区域中间的某个白色像素上单击（我想勾画一个白色区域），并且它的邻域中没有黑色像素（我的背景）。那么我该怎么办？ - akonsu

你从给定的位置开始，从左到右走，直到遇到黑色像素。当你碰到那个像素时，你开始顺时针迭代。如果用户在区域中间点击，你必须先到达边缘才能开始定义它。 - Xenethyl

是的，我必须找到一个边缘，并从那里开始，问题在于我的区域可能包含空洞。我可以忽略这些空洞，但我需要找到包含它们的区域的轮廓线。对我来说，找到一个边缘并不容易。 - akonsu

这不是小菜一碟，但也并不是过于复杂。你可以扩展算法来做左右两个方向的扫描。从左到右走一遍并勾勒出一个轮廓。然后从右到左再走一遍，如果你还没有标记到你所触碰到的像素点，则再勾勒出另一个轮廓。如果这两个轮廓不匹配（比如从右到左方向上你触碰到的像素点是新的），那么再运行一个左右扫描。当你的左右扫描勾勒出了同一个轮廓，你就知道已经完全勾勒出了用户选择的区域。需要注意的是，你需要比较多个组合，但每次只涉及一个像素点。 - Xenethyl